基于簇结构的无线传感器网络路由研究综述*

李 尧，滑 楠，田罗庚，王 荃

(1.空军工程大学信息与导航学院，西安 710077;2.解放军95482部队，成都 610081;3.西安通信学院，西安 710106;4.解放军93995部队，西安 710306)

1 引言

无线传感器网络(Wireless Sensor Network，WSN)的最初设想是由美国军方于1978年提出，它是由具备一定的运算、存储和无线通信能力的体积小、资源极端受限的传感器节点构成的。WSN融合了传感器技术、嵌入式计算技术、分布式信息处理和通信技术[1］，能够通过节点对复杂环境进行实时的监测、感知并对采集的数据进行融合处理从而得到准确的信息。无线传感器网络具有广泛的应用前景，包括了医疗、军事、家庭等许多领域[2］。作为物联网的关键技术，也被认为是21世纪最重要的技术之一。

与其他已有的信息网络不同，WSN规模较大，动态性较强，传感器节点的能量、通信能力、计算和存储能力等有限，很难由人工对大量传感器节点进行精确的部署和管理，需要结合其特性，利用一种合适的模型和方法对其进行设计和分析，以提高其可靠性和运行效率，完成既定应用目标。目前WSN的主要研究内容集中在无线传感器网络的路由协议方面，其主要目标是在保证数据可靠传输的基础上通过合理的路由协议来降低节点的能量消耗，从而达到延长网络生命周期的目的。本文从优化方式、适用场景、监测类型等方面对部分分簇路由协议进行分析，并提出对路由协议影响最为重要的几个因素，对无线传感器网络路由协议的设计提供一定参考。

2 无线传感器网络路由协议分类

无线传感器网络主要是由sink节点和大量传感器节点组成，传感器节点将感知到的信息通过一定的路由协议汇集到sink节点，如图1所示。用户只需要从sink节点来获取有用的信息。

图1 无线传感器网络结构Fig.1 The structure of wireless sensor network

无线传感器网络与传统的Ad Hoc网络和蜂窝网络在路由协议方面有较大区别和更多的要求，这是由无线传感器网络的特点所决定的:

(1)传感器节点受到能量、处理能力和存储空间的严格限制，因此节点需要精细的资源管理;

(2)无线传感器网络需要将节点感知到的数据传输到sink节点;

(3)路由协议的设计需要根据具体的应用;

(4)当传感器节点部署好后，其位置基本不发生变化，因此网络的拓扑结构一般不会改变;

(5)在无线传感器网络中，采集到的数据有很高的概率会存在冗余，必须通过路由协议来消除，以提高能量和带宽利用率。

因此，设计无线传感器网络路由协议时要充分考虑它的这些特点，同时尽量降低能量消耗提高网络的生存时间。在目前的路由协议研究中，从网络结构方面看可以分为平面路由协议和分簇路由协议两大类。

在平面路由协议中，节点的地位是平等的。其优点是网络中不存在特殊的节点，路由协议的鲁棒性较好，通信流量平均分散在整个网络中;缺点是可扩展性较差，并且网络规模受限。

在分簇路由协议中，网络被划分为簇的结构，每一个簇都是由一个簇头和多个簇节点构成，簇头是由不用的选举算法选举产生，它负责将簇内的信息进行融合处理后向更高一级传递，以此来减少通信开销。簇结构可以扩展到不止两层，但是要保证每一层都遵守相同的通信原则。

分簇路由具有的可扩展性强、能量利用高效、数据融合简单等优点[3］使其成为当前的研究重点，本文也主要对分簇路由协议进行研究。

3 分簇路由协议研究成果

目前，无线传感器网络相关方面的分簇路由协议研究主要有以下几种类型:一是专门对无线传感器网络路由的研究，提出了明确的路由协议或者对已有路由协议进行优化，如文献[4－7，9－11，13－16］;二是研究无线传感器网络的其他问题时对路由中的一些问题进行讨论，如文献[17－22］，这虽然不是路由研究的主要目的，但是讨论的成果可以在路由协议的设计中进行借鉴。本文主要对第一类中有代表性的文献进行分析。在专门针对WSN路由的研究又可以分为两类，一类偏重于对路由拓扑算法和协议的设计上，另一类偏重于对路由协议的优化。

3.1 网络路由拓扑方面研究成果

LEACH(Low－Energy Adaptive Clustering Hierarchy)[4］是最早提出的分簇路由协议，也是最为经典的WSN路由协议。LEACH协议中，节点通信按轮进行，每轮开始从节点中随机产生多个簇头(簇头轮流担任)，从而使节点能量消耗均匀。节点担任簇头后向所有节点广播自己成为簇头的消息，每个节点根据接收到广播信号的强弱来决定加入哪个簇，并将数据传给簇头，再由簇头将数据融合后转发给sink节点，这样既降低了数据量又缩短了单跳的传输距离。但是，LEACH算法也有不足之处:由于簇头随机产生导致簇头分布不均匀有可能发生“热区”现象或者某些节点附近没有簇头;簇头选择时没有考虑节点的剩余能量，可能某个当选簇头的剩余能量不足以完成整个通信过程，使整个簇的数据丢失;簇头与sink节点直接进行通信，当簇头远离sink节点时通信开销会很大，导致簇头节点过早死亡。

PEGASIS(Power－Efficient Gathering in Sensor Information Systems)[5］是在 LEACH 协议基础上进行的改进，它利用贪婪算法将所有传感器节点连接成一条链，在链上选取一个节点作为簇头，簇头两侧的链将数据融合后通过簇头传输给sink节点。PEGASIS协议将缩短单跳距离的原则做到了极致，节点只与离自己最近的节点成链。仿真结果表明，PEGASIS与LEACH协议相比，网络的寿命可以延长1倍，但是远端节点的数据要传到sink节点需要经过许多中间节点，这会引起较大的传输延迟，不适用于实时性要求比较高的环境。同时，整个网络只有一个簇头，所有数据都要从此簇头传输，对簇头节点的能量消耗会非常大，尤其是对距离sink节点较远的簇头节点来说。

LEACH－P[6］算法结合了 LEACH协议和 PEGASIS协议的优点，簇头选择依照LEACH协议的原则，并加入一个阀值，从而避免了簇头节点在通信过程中死亡的情况。簇头之间利用PEGASIS协议成链的思想，簇头根据贪婪算法成链，这样也解决了大规模网络部署情况下簇头距离sink节点过远导致的开销过大的问题，同时克服了PEGASISI协议实时性差的问题。

文献[7］根据网络规模较大时按正六边行进行分簇效果更佳[8］的特点，以合适的边长完成初步的六边形分簇，如图2所示，根据簇内的节点数进行分簇优化，再由节点的剩余能量选择簇头以及传输路径。

图2 正六边形分簇结构Fig.2 The regular hexagon structure of cluster

文献[9］提出了一种新的网络分簇和数据汇聚方法，即CABSM算法，将整个网络划分为正方形的单元格，每个单元格为一个簇并生成一个一级簇头，簇头由剩余能量最多的节点担任，负责簇内数据收集和融合。一级簇头通过簇间数据汇聚方法将数据发送给二级簇头，二级簇头选取时综合考虑节点的剩余能量和与sink节点的通信能耗，二级簇头再将整个网络的数据发送给sink节点。

3.2 路由协议优化方面研究成果

HEED[10］(Hybrid Energy － efficient Distributed Clustering)是对LEACH协议的优化，它指出了一种能量消耗模型，当节点成功发送n比特数据到距离为d的位置时，消耗的能量为

式中，Eelec表示节点发射装置发送和接收单位比特数据时消耗的能量，d0表示单跳通信的距离阀值，Efs表示d＜d0条件下节点放大器将单位比特数据传送单位距离所消耗的能量，Emp表示d≥d0条件下节点放大器将单比特数据传送单位距离所消耗的能量。

从公式可以看出，节点的能量消耗既跟传输的比特数有关，也跟传输的距离有关，并且当传输距离较近时，能量消耗与d2成正比，当传输距离较远时，能量消耗与d4成正比。它还提出延长生命周期、可扩展性和负载平衡是WSN中3个重要的需求，可以通过平均整个网络的能量消耗来延长网络的生命周期。HEED主要是对簇头的选择进行优化，依据主、次两个参数:主参数是剩余能量，用来决定簇头集合，剩余能量多的节点成为簇头的概率也较大;次参数主要是簇内通信代价，决定节点最终属于哪个簇。

文献[13］根据节点的剩余能量和整个网络的平均剩余能量来选择簇头，剩余能量多的节点当选簇头的概率较大，以达到均衡各节点能耗的目的。文献[14］提出了一种能量自适应的无线传感器网络协议，使得在sink节点附近的区域内，每个簇由较少的节点构成，在保证了转发其他簇信息的同时降低了本簇内收集数据的能量消耗，较好地解决了“热区”问题。

文献[15］和文献[16］描述的算法与传统的sink节点被动接收数据不同，文献[15］提出了一种具有移动sink节点的无线传感器网络协议，将整个网络被划分为若干个网格，每个网格选取自己的簇头，簇头负责收集簇内兴趣事件，进行数据融合后发给sink节点。选取簇头是为避免出现簇头出现在网格边缘的情况以网格中心为基准，建立一个簇头候选区域，并结合节点剩余能量、与网格中心的距离和邻居节点数综合选取簇头。sink节点在网络中随机移动，当到达一个网格时通知该网格的簇头更新其位置信息，然后该簇头再将位置信息分发给其他簇头，sink节点的随机移动均衡了各个簇头的能量消耗。

还有一种思想是sink节点固定不动，为实现特定的功能派出移动Agent(Mobile Agents，MA)。MA为一段可以实现自治功能的代码，其沿着设计好的方式移动，在经过的传感器上实现数据的压缩和融合。文献[16］在此基础上提出了一种数据分流的策略，当MA携带的数据达到一定量之后把MA携带的数据发送给sink，而MA仅带一个头部继续访问接下来的节点，从而降低了由于数据量过大对传输能量的浪费。

上述分簇路由协议的详细对比见表1。

表1 分簇路由协议对比Table 1 The comparison of cluster routing protocols

4 对分簇路由协议的进一步研究

路由协议从应用的角度可以在可扩展性和性能特点方面进行区分。如表1所示，有些协议设计的比较适合大型网络，如文献[6－7，9，15－16］，有些用在小型网络中效果明显，如文献[4－5，10－11，13－14］;有些协议可扩展性较强，如献[4－7，9－10，15－16］;有些协议的可扩展性一般，如文献[10－11，13］，由此可以看出实际中没有适合所有情况的路由协议。因此，在设计路由协议时应当首先考虑实际的应用情况，在此基础上再考虑对路由协议影响最为重要的几个因素。

(1)能量因素

能量的大小直接影响着网络的生存时间，如何合理的利用有限的能量，延长网络的生存时间是评价一个路由协议优劣的重要指标。

(2)网络节点的运动性

在绝大多数的无线传感器网络中，节点部署到位后就不会再移动了，但是在一些特殊的环境下如军事方面，节点不但会运动，而且有可能会以较高速度移动，这就对路由协议的设计提出了更高的要求。

(3)网络的规模

网络的规模可以从覆盖范围和节点数量两个方面来看，覆盖范围主要是关系着节点之间的距离，节点数量主要关系着网络中的数据量。

(4)节点的部署方式

主要是指节点在部署的时候在确定的位置部署还是随机部署，这就牵扯到网络的位置信息。如果节点是在确定的位置进行部署，那么就不需要再讨论位置信息的问题。如果是随机部署的话，那么还需要利用路由协议得到节点的位置信息。

(5)数据的传输方式

数据按照传输的方式从基站的角度来看可以分为主动式和被动式两种:主动式协议中，基站只对自己感兴趣的节点信息进行采集;而在被动式协议中，节点采集到的所有信息都被送到基站处。

(6)数据传输的可靠性

无线传感器网络是以采集数据为目的的，得到及时准确的数据是对所有路由协议的共同要求，数据能否可靠的传输在军事、灾害预防和抢险救灾等领域显得尤为重要。

由前面的分析可以发现，在对分簇无线传感器网络路由协议的研究中，几乎所有的协议都是从如何提高节点的能量利用率方面考虑的，但是却忽视了对其他因素的考虑，例如节点拓扑结构和路由的可靠性。具有最优跳数的路由有可能会包含不可靠路径，从而降低数据传输的可靠性[23］。并且随着科学技术的不断发展，无线传感器网络已经从同构型网络，即所有节点都具有相同的结构和功能，发展到由许多功能各异的节点构成的异构型网络[24－26］。与之相适应，路由协议也应该向着各节点之间相互协作的方向发展，这样既能提高数据传输的可靠性也能高效的发挥各个节点的功能。此外，在研究节点协作的协议时可以用多Agent系统模型来考虑。

无线传感器网络协作主要包括协作资源的使用、协作信号与信息处理、协作任务的分配与执行等[27］，其中协作资源的使用主要是利用通信协议来提高无线传感器网络的性能，协作信号与信息处理是解决如何进行数据融合，为协作提供基本数据，协作任务的分配与执行是指任务的描述、分配、调度与执行。在设计路由协议时主要从协作任务的分配与执行方面研究。

多Agent系统(Multi－agentSystem，MAS)[28－30］是一种分布式的并发系统，是由多个A-gent组成的Agent社会，具有自治性、分布性、协调性和自适应性，并且具有自组织能力、学习能力和推理能力，Agent之间可以通过协商和协作解决大规模的复杂问题。在多Agent系统中，每个Agent都不具备解决问题的完整知识，没有全局系统控制，数据是分散的，计算是异步的[26］。多Agent系统的这些特性与无线传感器网络的特点十分相似，因此MAS就非常适合被运用到无线传感器网络协作路由的设计中。将之结合到簇结构的路由协议中，将簇内的所有节点集合看成是一个小型的Agent社会，每个节点是具有不同功能的Agent成员，节点之间由某种路由协议相连并且可以通过协作的方法来解决复杂的问题，而不需要由用户来控制。

所有的无线传感器网络路由协议都是为了达到一个共同的目标，那就是通过一定的传输路径获取网络中各传感器节点采集到的信息，为了保证能够更好的达到这个目标，在设计路由协议时一般还会遵循以下几个原则:提高网络的生存时间，有效的能量消耗控制，具有完成多样化任务的能力，降低数据的传输延时和增强整个无线传感器网络的性能[31］。

5 总结

随着科学技术的不断发展，无线传感器网络可以帮助人类在各种复杂环境和难以到达的环境下采集和传输数据，在未来的生活中将扮演越来越重要的角色。无线传感器网络结构和运行非常复杂，这就需要高效的路由协议来支撑。分簇结构的路由协议作为最适合无线传感器网络的形式得到了广泛研究。随着无线传感器网络在各领域广泛的应用，对路由协议的要求已经不仅仅是节约能量了，既要求可靠的传输数据，还需要它能对突发事件做出正确的响应，但是无线传感器网络节点受到体积、能量等限制，不可能独立完成这些任务，因此需要多节点之间进行相互协作，而多Agent系统与无线传感器网络协作路由的特点十分相似，因此它是描述、设计和分析无线传感器网络的一种自然而有效的方法。

[1]Ren Feng－ yuan，Huang Haining，Lin Chuang.Wireless sensor network [J］.Journal of Software，2003，14(7):1282－1291.

[2]Akyildiz I F，Su W，Sankarasubramaniam Y，et al.A survey on sensor networks[J］.IEEE Communications Magazine，2002，40(8):102 －114.

[3]Boyinbode O，Hanh L，Mbogho A，et al.A survey on clustering algorithms for wireless sensor networks[C］//Proceedings of 201013th International Conference on Network－Based Information System.Takayama:IEEE，2010:358－364.

[4]Heinzelman W，Chandrakasan A，Balakrishman H.Energy－Efficient communication protocol for wireless microsensor networks[C］//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.Hawaii，USA:IEEE，2000:3005 －3014.

[5]Lindsey S，Raghavendra C S.PEGASIS:Power efficient gathering in sensor information systems[C］//Proceedings of the IEEE Aerospace Conference.San Francisco:IEEE，2004.

[6]张震，闫连山，潘炜，等.基于 LEACH和 PEGASIS的簇头成链可靠路由协议研究[J］.传感器技术学报，2010，23(8):1173 －1178.ZHANG Zhen，YAN Lian － shan，PAN Wei，et al.Routing Protocol Based on Cluster－Head－Chainin g Incorporating LEACH and PEGASIS[J］.Chinese Journal of Sensors and Actuators，2010，23(8):1173 －1178.(in Chinese)

[7]李桢，陈健，阔永红.WSN中六边形集中式分簇多跳路由协议[J］.西安电子科技大学学报(自然科学版)，2012，39(3):20 －26.LI Zhen，CHEN Jian，KUO Yong－ hong.Hexagon － al centralized cluster－based multi－hop routing protocol for WSN[J］.Journal of Xidian University(Natural Science Edition)，2012，39(3):20 －26.(in Chinese)

[8]Salzmann J，Behnke R，Timmermann D.Tessellating Cell Shaoes for Geographical Clutering[C］//Proceedings of 201010th IEEE International Conference on Computer and Information Technology.Bradford:IEEE，2010:2891 －2896.

[9]衣晓，邓露，刘瑜.基于基站划分网格的无线传感器网络分簇算法[J］.控制理论与应用，2012，29(2):145－150.YI Xiao，DENG Lu，LIU Yu.A Centroid Localization Algorithm Based on PIT for Wireless Sensor Network[J］.Chinese Journal of Sensors and Actuators，2012，29(2):145－150.(in Chinese)

[10]Younis O，Fahmy S.Heed:A hybrid，energy － efficient，distributed clustering approach for ad－hoc sensor networks[J］.IEEE Transactions on Mobile Computing，2004，3(4):660 －669.

[11]赵小敏，毛科技，王正莉，等.基于能量和距离的分簇式WSN路由协议设计[J］.解放军理工大学学报(自然科学版)，2012，13(4):393 －396.ZHAO Xiao － min，MAO Ke － ji，WANG Zheng － li，et al.Design of energy － distance based cluster routing protocol in WSN[J］.Journal of PLA University of Science and Technology(Natural Science Edition)，2012，13(4):393－396.(in Chinese)

[12]Wang Xiao － ping，Cao Li－ ming.Genetic algorithm:theory，application and software impelement[M］.Xi'an:Xi'an Jiaotong University Press，2002.

[13]Qing L，Zhu Q，Wang M.Design of a distributed energy－efficient clustering algorithm for heterogeneous wireless sensor networks[J］.Computer Communications，2006，29(3):2230 －2237.

[14]李树华，刘振宇，李迎秋.能量自适应的无线传感器网络分簇路由协议[J］.计算机工程与设计，2010，31(3):504－507.LI Shu－hua，LIU Zhen－yu，LI Ying－qiu.Energy adaptive cluster－based routing protocol for wireless sensor networks[J］.Computer Engineering and Design，2010，31(3):504 －507.(in Chinese)

[15]钟智，罗大庸，刘少强，等.具有移动sink的无线传感器网络能量均衡分簇路由协议[J］.控制与决策，2012，27(8):1211 －1220.ZHONG Zhi，LUO Da － yong，LIU Shao － qiang，et al.Energy－balanced clustering routing protocol in wireless sensor networks with a mobile sink[J］.Control and Decision，2012，27(8):1211 －1220.(in Chinese)

[16]胡晓敏.无线传感器网络Agent数据分流粗略[J］.软件学报，2012，23(11):2946 －2954.HU Xiao－min.Agent Data Separation Strategy for Wireless Sensor Networks[J］.Journal of Software，2012，23(11):2946 －2954.(in Chinese)

[17]鲍培明，朱庆保.无线传感器网络中多基站定位的多目标蚁群算法[J］.上海交通大学学报，2009，43(3):449－454.BAO Pei－ming，ZHU Qing－ bao.A Multi－ objective Ant Algorithm for Multi－base Station Placement in Wireless Sensor Networks[J］.Journal of Shanghai Jiaotong University，2009，43(3):449 －454.(in Chinese)

[18]张莉，李金宝.无线传感器网络中基于多路径的可靠路由协议研究[J］.计算机研究与发展，2011，48(增):171－175.ZHANG Li，LI Jin － bao.Multi－ Path Based Reliable Routing in Wireless Sensor Network[J］.Journal of Computer Research and Development，2011，48(Suppl.):171 －175.(in Chinese)

[19]杨歆豪，李泽.无线传感器网络中基于领导者的拥塞控制算法[J］.控制与决策，2012，27(9):1348－1352.YANG Xin －hao，LI Ze.Congestion control algorithm based on leader for wireless sensor network[J］.Control and Decision，2012，27(9):1348 －1352.(in Chinese)

[20]李明维，井元伟，陈向勇.一种无线传感器网络跨层拥塞控制算法[J］.东北大学学报(自然科学版)，2012，33(1):10 －12.LI Ming－ wei，JING Yuan － wei，CHEN Xiang － yong.A Cross－Layer Congestion Control Algorithm for Wireless Sensor Network[J］.Journal of Northeastern University(Natural Science Edition)，2012，33(1):10 － 12.(in Chinese)

[21]蒋毅，张若南，史浩山.一种基于地理位置的无线传感器网络安全路由协议[J］.西北工业大学学报，2012，30(1):12 －15.JIANG Yi，ZHANG Ruo － nan，SHI Hao － shan.A New and Better Geography Based Security Routing Protocol for Wireless Sensor Network s[J］.Journal of Northwestern Polytechnical University，2012，30(1):12 －15.(in Chinese)

[22]白恩健，葛华勇，杨阳.分簇无线传感器网络安全多路径路由协议[J］.哈尔滨工程大学学报，2012，33(4):507－527.BAI En － jian，GE Hua － yong，YANG Yang.A secure multipath routing protocol for hierarchical wireless sensor networks[J］.Journal of Harbin Engineering University，2012，33(4):507 －527.(in Chinese)

[23]Hu Zhigang，Ma hao，Wang Guojun，et al.A reliable routing algorithm base on fuzzy Petri net in mobile ad hoc networks[J］.Journal of Central South University，2005，12(6):714 －719.

[24]Lin Y，Hu X M，Zhang J.An ant－colony system － based activity scheduling method for the lifetime maximization of heterogeneous wireless sensor networks[C］//Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation.Portland:IEEE，2010:23 －30.

[25]Lin Y，Zhang J，Chung H S，et al.An ant colony optimization approach for maximizing the lifetime of heterogeneous wireless sensor networks[J］.IEEE Transactions on System，Man，and Cybernetics － Part C，2012，42(3):408－ 420.

[26]Lin Y，Hu X M，Zhang J.Optimal node scheduling for the lifetime maximization of two－tier wireless sensor networks[C］//Proceedings of 2010 IEEE Congress on Evolutionary Computation.Barcelona:IEEE，2010:1 －8.

[27]于海斌，曾鹏，梁韡.智能无线传感器网络系统[M］.北京:科学出版社，2006.YU Hai － bin，ZENG Peng，LIANG Wei.Intelligent Wireless Sensor Network System[M］.Beijing:Science Press，2006.(in Chinese)

[28]Jennings N R，Sycara K，Wooldridge M J.A roadmap of agent research and development[J］.Autonomous A-gents and Multi－ Agent Systems，1998，1(1):7 －38.

[29]Zambonelli F，Omicini A.Challenges and rese－ arch directions in agent－oriented software eng－ ineering[J］.Autonomous Agents and Multi－ Agent Systems，2004，9(3):253 －283.

[30]Pechoucek M，Marik V.Industrial deployment of multi－agent technologies review and selected case studies[J］.Autonomous Agents and Multi－ Agent Systems，2008，17(3):397 －431.

[31]Pantazis N A，Nikolidakis S A，Vergados D D.Energy－Efficient Routing Protocols in Wireless Sensor Networks:A Survey[J］.IEEE Communications Surveys ＆ Tutorials，2013，15(2):551 －590.