无线传感器网络分簇路由协议的研究与应用*

(福建师范大学 闽南科技学院，泉州 362332)

引 言

无线传感器网络是一种新型的监测技术，该系统包括传感器节点、汇聚节点以及管理节点三部分。在实际应用中，大量的传感器节点被无人飞机等飞行器抛洒在指定的监测区域或者监测区域附近的区域，然后这些节点可以用自组织的方式来构建出一个无线网络，再通过相互合作的方式来进行数据的实时监测，并在网络覆盖区域内收集和处理信息。传感器节点所监测的数据是通过多跳通信传输的，在这个过程中，会有多个节点处理监测到的数据，然后将该监测信息通过卫星和互联网传送到管理节点。此时，用户就可以根据传送来的数据进行下一步的操作，可以传达监测与收集整理数据的任务，当收到这些任务后，大量的节点就开始探测数据，并传送给用户。

1 无线传感网络路由协议

无线传感网络中进行数据交换时都是通过与传统网络不同的无线通信方式，这就导致传统的通信技术不能直接应用到无线传感网络中。而对于传统的无线网络而言，网络协议的首要任务是在通信目标移动的情况下，仍然能够保证网络的服务质量，在无线传感网络中，网络协议设计的目标最重要的一点就是降低网内节点的通信能耗，从而延长网络的工作寿命。此外，无线传感网络的应用场景众多，各种应用都有不同的侧重。在无线传感网络的研究中，需要对其路由协议进行设计与优化，使之能够更好地适应无线传感网络的各类应用[13]。传感器节点分为多个簇，每个簇都有自己的簇首，用于收集处理并传送数据。这些簇首将收集到的数据再直接传送给基站。

由于分簇路由协议将无线传感网络的路由机制化繁为简，将一个网络划分为若干个子网络，能够很好地解决网络通信过程中因为有节点失效而退出网络、节点的移动或者是有新节点加入而带来的拓扑变化带来的问题，同时具有很好的可扩展性。除了网络的可扩展性比较好之外，分簇路由协议还有一些其它优势。

因为簇内通信的路由是在每个簇内建立起来的，所以每个节点所存储的路由表也大大减少，这样就节省了节点的存储空间。其次，由于簇内的普通节点只需和簇首节点通信，这样就节省了网内带宽。由此可见，分簇路由协议对于无线传感网络的路由设计有很大的帮助。对于传感器的供电装置，在进行替换或者在传感器任务周期内，能够保证传感器的正常工作。任务周期取决于应用背景，例如监视火山活动，需要传感器工作数年之久，而鸟类孵化监视该类应用中，也许只要数月。以前的WSN数据采集网络采集的数据格式较为单一，信息量少，因此在数据处理上所采用的方式也较为简单。后来图像、音频等也被纳入监测范围。这些多媒体应用，在采集、处理和传输上，需要更大的数据处理能力，大存储容量设备，同时也消耗更多的网内能量资源。

通常情况下，WSN网内传感器由电池供电，当能量耗尽时必须更换电池或者对电池进行充电才能保证传感器的正常工作。现阶段，有参考文献讨论使用太阳能、风能等作为WSN的能源续航，但是这些方法转换率低，且受环境因素限制。就硬件成本而言，给所有网内节点更换电池也不切实际。因此，WSN的生存周期主要取决于电源的生存周期。而研究也表明，路由协议的优化对于降低网内通信能耗、延长网络寿命有着相当显著的效果[11]。从图1中可以看出，传感器在不同模式下的能耗是不同的，而且在数据收发阶段和节点空闲的时候，能耗明显高于其它状态，所以在不使用时，最好让节点在休眠状态下。

图1 传感器不同状态能耗示意图

2 无线传感器分簇协议分析和比较

近年来研究人员就提出不同的无线传感器网络分簇路由协议。Heinzelman 等人最先提出均匀的分簇路由协议，称为 LEACH协议[2]。这是针对无线传感网络提出的第一种分簇路由协议，在LEACH协议中，每轮数据收集开始前的阶段,其中的小部分节点会被随机地选为簇首[3]。数据收集时，簇首直接把自己的信息以单跳方式传送至汇聚点。Lindsey 等人提出一种节点为链状的算法，称之为 PEGASIS 算法，在该算法中，数据先在链上处理，再传输至汇聚点[4]，该算法需要知道每个节点的位置信息。为了能够最大化地延长网络的存活时间，Dasgupta 等人就提出一种基于分簇的启发式算法 ,但该算法比较繁冗，需要事先知道节点的位置与能量的信息[5]。Choi 等人提出两阶段分簇协议 TPC，在簇内构造多跳路由链路以节约能量[6]。Younis 等人提出一种HEED[7]算法，这是一种混合式的分簇协议，第一步是根据节点剩余能量的多少概率性地选取一部分候选簇首 ,第二步通过计算候选簇首在簇内通信时消耗能量的高低来最终确定簇首。后来，研究人员通过研究发现传感器网络多跳路由中的“热区”问题，为了解决这一问题，Soro等人首次提出非均匀分簇的思想，通过非均匀分簇来解决这个问题[8]。

[8]中,假设网络的拓扑结构是两个环绕汇聚点同心圆，在这两层圆中，内圆环需要承担更多的数据接收与转发的任务，因为在多条路由方式中，它离汇聚点的距离最近。在EECS[9]中，节点在选择簇首时就不是简简单单地选择距离自身最近的簇首节点，而且还要考虑候选簇首到汇聚点的距离远近 ，构造出大小非均匀的簇，均衡簇首的能耗。在最小生成树[10](UCRAMST)中，非均匀分簇簇首的选择是根据剩余能量和距离来考量的，通过对路径搜索建立最优传输途径。在基于梯度的非均匀分簇算法中[11]，根据设置的梯度来设定竞争半径，从而获得密度并不均匀的簇头分布，在节点密集的地方，簇头也会密集一些。基于助理簇头的持久化路由协议[12](ACPCR)首次提出最优助理簇头的思想，助理簇头可以代替簇首完成数据转发等任务，来节省簇首的能量消耗。基于蚁群算法[13](ACA)的网路由协议通过蚂蚁包发送的方式，所有节点都能够获得最新的网络情况，并根据这一情况选择下一步动作。

后来，Intanagonwiwat等人提出一种反向查询的路由机制[14]。Schurgers等人提出一个基于梯度的路由算法——GBR ,并依据此算法设计一些节点调整的策略，以此来实现流量分布均衡[15]。但是这些查询协议都有一定的局限性，它们只适用于单一数据的传送，不适用于“多对一”的数据传输，因此，就不适合簇首与簇首之间数据的转发使用。

下面就选取国内外一些典型的分簇路由协议，对其所采用的路由形成机制、路由特点进行分析与比较。

(1)LEACH(Low-EnergyAdaptiveClusteringHierarchy)

LEACH协议是针对无线传感网络提出的第一个分簇路由协议。在选取簇首节点的过程中，每个候选节点都会自发地在[0,1]之间产生一个随机数，而网内又会生成一个阈值T(n)，若是产生的随机数小于阈值T(n)，那么这个节点就会成为簇首节点。LEACH-C协议在簇首选举上采用集中选举的方式，并采用模拟退火算法来为网内选择更加适合的簇首节点。

(2)HEED(HybridEnergy-EfficientDistributedClustering)

HEED协议在簇间通信上，采取了与LEACH协议不同的簇间多跳的路由方式来传递簇之间收集到的信息，这种簇间通信方式更加适合用于大规模的网站[16]。此外，HEED协议对于节点的拓扑结构和具体位置没有提出特殊的需求。该协议主要完成以下4个任务：① 均衡网内能耗，延长网络的工作寿命；② 分簇过程完成得比较快；③ 使得通信开销尽可能得少；④ 簇首节点在网内合理分布，簇的分布比较紧凑。

在选取簇首节点的过程中，HEED协议需要参考两个参数。一个参数与网内剩余能量相关，一个参数与簇群内部的通信开销有关，称之为平均可到达能量。根据第一个参数可以在网内选取出候选簇首节点，再通过第二个参数计算簇群内的通信开销，选择开销比较小的进行成簇。

(3)APTEEN(AdaptivePeriodicThershold-sensitiveEnergyEfficientSensorNetwork,APTEEN)

APTEEN协议在成簇过程中采用集中式的控制思想，由基站来决定网内的簇首节点，簇首节点一旦决定，就可以通过广播参数信息来成簇，且APTEEN经常形成多层簇结构[17]。APTEEN协议的优势在于可以实现周期性的数据采集和及时响应特殊事件的应用场合。但是也存在不足，主要体现在构建多层簇在实际应用中难以实现，同时，协议内部的查询机制和基于属性的命名会给网络带来不小的通信能耗。

(4)CM[18](ClusteringwithMobility)协议

参考文献[18]对LEACH协议进行改进。首先在成簇过程中，算法首先预测节点之间的距离，并根据簇群内节点之间的距离尽可能小这一原则将网内的非簇首节点分配给簇首节点。除此之外，该参考文献还发现，当簇内没有簇首节点产生的轮数中，LEACH协议的能耗会变得非常大，所以提出的协议通过两种方法来解决这个问题：一种方案是只要监测到该轮没有簇首节点被选举出来，那么整个网络直接跳过这一轮；另外一种就是固定每轮需要的簇首节点个数，并在簇内准备完成之前在此核对网内的簇首节点个数。

(5)DSC[19](Dynamic/StaticClusteringprotocol)协议

DSC协议是在LEACH-C的基础上提出的一种协议，该协议规定，簇内的簇首节点每经过10轮才进行一次替换。通过仿真显示，该协议在通信能耗、能量分布和网络寿命等方面均优于LEACH-C协议。

(6)PBEACP[20](Priority-basedEnergyAwareandCoveragePreserving)

PBEACP根据网内节点的剩余能量为参考来选择簇首节点，同时它会考虑节点的地理分布，来保证网内通信消耗能够均衡。同时，它也保证即使在簇内节点死亡的情况下，也能保证簇首节点对网络的覆盖。但是它并未解决簇首节点死亡发生中的数据采集。

(7)2CRNDC[21](2-ConnectedRelayNodeDoubleCover)

2CRNDC通过给每个节点配备一个备用接力节点来保证，即时有节点死亡，剩余节点也能保证将采集到的数据传出。

(8)EAFTICC[22](Energy-AwareandFaultTolerantInter-ClusterCommunicationbasedProtocol)

EAFTICC算法利用备用路径来保证网内的通信在最大程度上不受节点死亡的影响。这个算法保证每个簇内至少有两个节点来负责簇内通信，如果一个节点死亡，那么另一个节点就接替那个节点工作。该算法的独特性在于使用了多路径通信，如果一条通路上的节点发生错误，立刻启用网内的备用节点来保证数据通道的畅通无阻。

(9)EERNT[23](Energy-EfficientRedundantNodesTree)

EERNT也是利用冗余节点来保证数据传输的可靠性。该算法通过在网内冗余节点之间生成树，并将簇首节点收集到的数据传送至离其位置最近的冗余节点。

(10)EDETA[24](Energy-efficientaDaptivehiErarchicalandrobusTArchitecture)

如果簇首节点死亡或者通信出问题的话，网内其余节点就不能及时将收集到的数据发送出去。于是EDETA协议根据其余节点的剩余能量和到簇首节点的距离，在簇内引入簇首节点的代替节点。该节点在簇内的任务就是时刻监视簇首节点的工作，如果簇首节点发生问题，它会立刻发现，于是它会在簇内广播自己成为新的簇首节点。

(11)FLOC[25](FastLOcalClusteringservice)

FLOC采用分布式的方法产生网内簇首节点。它通过普通节点到簇首节点的距离将这些节点分为内部节点和外部节点。内部节点和簇首节点通信不受任何影响，但是外部节点的数据经常发生丢包。在FLOC中，通过心跳监听的方式来判断簇首节点是否正常工作。簇首节点在簇内周期性地广播一条信息，如果网内有簇内节点没能收到这个信息，那么此簇内节点就自动脱离这个簇群。等到所有簇内节点都脱离簇群后，选择在新一轮组成新的簇群，或者就近加入别的簇群。

(12)EQoSa[26](EnergyandQoSawareMACforwirelesssensornetworks)

首先该算法通过线性规划的方式，对安放中继路由节点的位置进行最优化，以保证每个节点的覆盖区域都至少有一个中继路由节点。其次，该算法通过设定中继节点的个数Ks来保证网络的容错性，这就保证了每个节点在数据传输过程中，即使有(Ks-1)个节点失效，那么仍旧有1个中继节点可以继续提供服务。

(13)FEED[27](Faulttolerant,EnergyEfficient,Distributedclustering)

FEED算法在每个簇群中都选取了一个簇首节点、一个枢纽节点(PCH, pivot CH)和一个监督节点(SN, Supervisor Node)。PCH是网内的异构节点，其所包含的能量更多。网内所有的PCH能覆盖大部分的网络，所以具备寻找网内路由的功能。SN是用来监督簇首节点或者PCH节点的，能够在簇首节点或者PCH失效的时候及时替代它们的功能。

(14)MCAR[28](MAC-Congestion-AwareRouting)

该算法讨论了在分簇网络内出现拥塞的时候该如何处理网内拥塞。该算法中，网内时刻监视着是否有拥塞发生。若在网内某处有大量数据爆发的时候，网络会为这些数据及时形成一条高优先级数据流量通道。通过牺牲网内低优先级数据的通信来缓解网内的拥塞。

(15)CEECA[29](ClusteringbasedEnergyEfficientCongestionAwareprotocol)

通过对数据包设置不同的优先级，再根据优先级的高低分配不同的路由表，通过这种方式，提高网内能量利用效率，并且能够解除网内出现的拥塞。

(16)MOCA[30](Multi-hopOverlappingClsuteringAlgorithm)

MOCA算法中将网内的簇群组织设置为互相重叠的簇群，这么做的目的在于，无论这个节点的身份如何，都能保证此节点在n跳之内将数据传送给一个簇首节点，而n跳的距离为预设的簇半径。

上述各类分簇协议比较如表1所列。

表1 上述各类分簇协议比较

续表1

从表中的分簇协议对比中可以看出，这些常见的无线传感网络分簇协议都存在各自的优点和缺点，但是并不存在哪个路由协议在各方面的表现都是最好的，具体选用何种路由协议，还要参考具体的应用场景。就簇间路由而言，直接通信虽然算法实现简单，但是考虑到有些簇首节点离基站比较远，传感器节点在发射功率上又存在一定的限制，其总体上的能耗小于使用直接通信的方式，但是导致靠近基站的簇首节点会承担更多的转发任务，所以这些区域的能量较其它区域而言下降得更加迅速，从而导致这些区域的节点因为能量耗尽而过早失效，网内连通性变差。而就路由协议的目的而言，(1)～(8)提出的协议目的在于如何在联通网络获取最佳的数据传输路径，而(9)～(16)的路由协议更注重无线传感网络服务质量的问题，即当网内通信出现问题时候，如何及时发现问题并解决。

3 无线传感器网络设计的关键问题

无线传感网络的工作周期被记为“轮”(round)，每一轮被进一步分为簇阶段和稳定阶段。在每一轮中，每个簇都是新生成的，簇首节点从此前未担任过簇首的候选节点中产生。根据仿真可知，该簇首节点选择机制可以很好地保证网内都有足够的候选节点来充当簇首节点，在每轮当中，未当选为簇首节点的候选节点都有很大的几率会被选为簇首节点。目前传感器网络设计中关键技术主要包含以下几点：

(1)网络拓扑控制

因为无线传感网络为自组织网络，网络拓扑会因为多种因素而随机改变。所以，对于无线传感网络的拓扑控制有特别的意义。由于无线传感网络的分布具有随机性，其面对的应用场景有所不同，所以一般不存在一个最优拓扑能够适应所有无线传感网络的应用，在不同的应用场景下需要对无线传感网络的拓扑做不同的优化。

(2)时钟同步技术

时钟同步技术是无线传感网络的一项主要支撑技术。无线传感网络的时钟同步技术一般情况下会面临网内有限能耗、节点制作成本和节点体积大小等多方面的约束，所以在研究时钟同步技术的同时，一般也应该考虑技术的节能型、可扩展性等要求。

(3)网络覆盖与网络规划

由于传感节点的随机布散，在传感监测区域中会存在监测“空洞”或者监测区域重叠的问题，这些都会降低无线传感网络在监测应用中的表现。同时，节点能源有限、软件错误或者其它外界因素，都有可能会导致网内节点的死亡，这样网内的联通度就会降低，同时网络监测区域的范围也会减小。所以网络覆盖性这一指标对于无线传感网络的有效性非常重要，保证网络的覆盖对于网络的鲁棒性也非常重要。

(4)数据融合技术

在建立无线传感网络的时候，为了保证网络的覆盖、数据采集的实时性与网络的鲁棒性，常常会在某区域内遍布大量传感器节点，以保证检测的区域能够相互重叠，但这也导致在传感器密度比较高的区域，采集到的信息具有很高的相关性。如果将这些采集到的数据不加处理就直接传送，就会占用大量网络资源，而数据融合就是采用一定的算法，强化公共信号，滤去不相关的噪声信息，使来自不同信息源的数据进行聚合以产生更加精确的信息，同时也能节约一部分网内能量。

(5)网络安全技术

网络安全因素也是在设计无线传感网络过程中需要考虑的因素之一。无线传感网络必须引入有效的安全机制以防止网络被未授权的接入或者恶意攻击而破坏，而有些对网络最底层的物理攻击方式更为直接粗暴，而这些手段对网络造成的危害也难以在短时间内修复。综上所述，网络攻击的方式纷繁复杂，而攻击的对象都有各自的侧重。

分簇路由协议通信主要分为以下几个步骤：①簇首节点选择;②成簇阶段;③簇间路由形成;④能量控制。LEACH协议是最早提出的分簇路由协议，主要存在“能量热区”问题，因为簇首节点承担过多通信任务，能耗总是急遽下降，主要存在几个问题：

① 协议中簇首节点的生成过程过于随机，导致簇首节点可能在网内部分不均匀。簇首节点分布不均匀导致的后果就是，如果簇首节点所在区域的节点部分过于稀疏，就会大量增加簇内通信的开销；若是簇首节点之间的距离过于紧密，网内簇群的划分对网内通信的改善并无多大的效果。

② 簇首节点的个数是指定的，这在小型的网络中可以适用，但是对于大型的网络，网内拓扑复杂多变，再对簇首节点的个数进行指定就不合适。

③ 簇首节点与基站之间能够直接通信，若是选举出的簇首节点在远离基站的位置，而此时簇首节点将簇内手机的大量数据直接发送给基站的话，该簇首节点的通信能耗会非常巨大，从而导致节点迅速死亡。

结 语

参考文献

[1] 詹杰,刘宏立,张杰.面向复杂环境监测的无线传感网络技术研究[M].北京:人民邮电出版社,2014.

[2] Heinzelman WR,Chandrakasan A,BalakrishnanH.Energy-Efficientcommunication protocol for wireless microsensor networks[C]//Proc. of the 33rd Hawaii Int’l Conf. on System Science,2000.

[3] Heinzelman W,Chandrakasan A,Balakrishnan H.An application specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[4] Lindsey S,Raghavendra C,Sivalingam K M.Data gathering algorithms in sensor networks using energy metrics[J].IEEET actions on Parallel and Distributed Systems,2002,13(9):924-935.

[5] Dasgupta K,Kalpakis K,Namjoshi P.An efficient clustering based heuristic for data gathering and aggregation in sensor networks[C]//Proceedings of the IEEE Wireless Communications and Networking Conference(WCNC),New Orle-ans,LA,2003:1948-1953.

[6] Choi W,Shah P,Das S K.A framework for energy2saving data gathering using two2phase clustering in wireless sensor networks[C]//Proceedings of the International Conference on Mobile and Ubiquitous Systems:Networking and Services(MOBIQUITOUS),Boston,MA, 2004:203-212.

[7] Younis O,Fahmy S.HEED:A hybrid, energy2efficient,distributed clustering approach for ad hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4):660-669.

[8] Soro S,Heinzelman W.Prolonging the lifetime of wirelesssensor networks via unequal clustering[C]//Proceedings of the 5th International Workshop on Algorithms for Wireless,Mobile,Ad Hoc and Sensor Networks,Denver,CO,2005.

[9] Ye M,Li C F,Chen G H,et al.An energyefficient clustering scheme in wireless sensor networks[C]//Ad Hoc&Sensor Wireless Networks.

[10] 张明才,薛安荣,王伟.基于最小生成树的非均匀分簇路由算法[J].计算机应用,2012,32(3):787-790.

[11] 黄河清,沈杰,马奎,等.无线传感网基于梯度的非均匀分簇[J].光学精密工程,2009,17(8):2053.

[12] 邓亚平,徐军帅.一种基于助理簇头的持久化分簇路由协议[J].小型微型计算机系统,2013,34(11):2538-2541.

[13] 缪聪聪,陈庆奎,曹剑炜,等.基于蚁群的无线传感器网络能量均衡非均匀分簇路由算法[J].计算机应用,2013,33(12):3410-3414.

[14] Intanagonwiwat C,Govindan R,Estrin D. Directed diffusion:A scalable and robust communication paradigm for sen2sor networks[C]//Proceedings of the ACM Mobile Computing and Networking (MobiCom),Boston,MA,2000:56-67.

[15] Schurgers C,Srivastava M B.Energy efficient routing in wireless sensor networks[C]//Proceedings of the IEEE Military Communications Conference(MILCOM),McLean,VA,001:357-361.

[16] Zungeru A M,Ang L M,Seng K P.Classical and swarm intelligence based routing protocols for wireless sensor networks: A survey and comparison[J].Journal of Network and Computer Applications,2012,35(5):1508-1536.

[17] 孙雨耕,张静,孙永进,等.无线自组传感器网络[J].传感技术学报,2004,17(2):331-335.

[18] Liu C M,Lee C H.Power efficient communication protocols for data gathering on mobile sensor networks[C]//Vehicular Technology Conference,2004. 2004 IEEE 60th.IEEE,2004:4635-4639.

[19] Bai H,Atiquzzaman M.Error modeling schemes for fading channels in wireless communications:A survey[J].Communications Surveys & Tutorials,IEEE,2003,5(2):2-9.

[20] Dong Y,Quan Q,Zhang J.Priority-based energy aware and coverage preserving routing for wireless sensor network[C]//Vehicular Technology Conference,2008.

[21] Hao B,Tang J,Xue G.Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation[C]//High Performance Switching and Routing, 2004. HPSR.2004 Workshop on.IEEE,2004:246-250.

[22] Boukerche A,Martirosyan A.An energy-aware and fault tolerant inter cluster communication based protocol for wireless sensor networks[C]//Global Telecommunications Conference,2007.GLOBECOM'07.IEEE. IEEE,2007:1164-1168.

[23] Zhen j Z,Yun L.An energy-efficient redundant nodes tree mechanism for wireless sensor networks[C]//Systems and Networks Communications,2006ICSNC'06.International Conference on.IEEE,2006:63-65.

[24] Capella J V,Bonastre A,Serrano J J,et al.A new robust,energy-efficient and scalable wireless sensor networks architecture applied to a wireless fire detection system[C]//Wireless Networks and Information Systems,2009.WNIS'09. International Conference on.IEEE,2009:395-398.

[25] Demirbas M,Arora A,Mittal V.Floc:A fast local clustering service for wireless sensor networks[C]//Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS/DSN 2004).2004:1-6.

[26] Baroudi U. EQoSa: energy and QoS aware MAC for wireless sensor networks[C]//Signal Processing and Its Applications,2007. ISSPA 2007. 9th International Symposium on. IEEE,2007:1-4.

[27] Mehrani M,Shanbehzadeh J,Sarrafzadeh A,et al.FEED:Fault tolerant,energy efficient,distributed Clustering for WSN[C]//Advanced Communication Technology (ICACT),2010 The 12th International Conference on.IEEE,2010,1:580-585.

[28] Kumar R,Crepaldi R,Rowaihy H,et al.Mitigating performance degradation in congested sensor networks[J].Mobile Computing,IEEE Transactions on,2008,7(6): 682-697.

[29] Sabarish B A,SashiRekha K.Clustering based energy efficient congestion aware protocol for Wireless Sensor Networks[C]//Emerging Trends in Electrical and Computer Technology (ICETECT),2011 International Conference on.IEEE,2011:1129-1135.

[30] Youssef A M,Younis M F,Youssef M,et al.Distributed Formation of Overlapping Multi-hop Clusters in Wireless Sensor Networks[C]//GLOBECOM,2006.