无线传感器网络能量均衡分簇路由协议

卫 琪

（中北大学 电子与计算机科学技术学院，山西 太原 030051）

0 引言

无线通信技术和电子技术的发展使得无线传感器网络(Wireless Sensor Networks, WSN)方面的研究受到越来越多的重视。WSN可实现数据的采集量化、处理融合和传输应用，它是信息技术中的一个新的领域，在人们生产、生活的各个领域都有广阔的应用前景[1-3]。

WSN的一个基本功能就是将监测区域内发生的事件或感知到的数据传送到基站供进一步分析使用，WSN路由协议对这项功能的实现起着至关重要的作用[4]。通常情况下，传感器节点能量有限且无法补充，因此降低能量损耗、延长网络的生命周期是WSN中设计有效路由算法的核心目标。WSN的路由协议作为一项关键技术已成为目前研究热点。

本文在对LEACH协议研究的基础上，结合其优点、针对其不足，提出一种基于剩余能量且负载均衡的无线传感器网络能量有效分簇路由协议(LEACH-improved)，可以更好地均衡网络负载，延长网络生存时间。

1 相关工作

LEACH ( Low-Energy Adaptive Clustering Hierachy)[5]低功耗自适应分簇路由协议，是最早提出的分簇路由算法。它的核心思想是通过周期性的随机选举产生簇头，使网络能耗平均分配到每个传感器节点上，进而延长网络的生存时间。 LEACH协议有许多优点，通过动态分簇，使所有节点平均分担中继通信业务[6]；在簇内进行的本地融合技术减少了发往sink的数据量，特别是处理具有高度相关性的数据时，冗余数据被大量消除[7]；作为一种分布式的分簇路由协议，节点既不需要全局的网络信息[8]，也不需要来自基站的任何控制信息。但是，LEACH在簇头选择时仅依靠节点产生随机数，而未考虑参选节点的能量水平；频繁的簇重构，且每次网络的拓扑结构都会较大改变；要求所有簇头与sink一跳通信，为远离sink的簇头带来很大数据传输能耗，同时造成簇头间能量消耗不均衡。

2 系统模型

2.1 网络模型

LEACH-improved协议采用如下网络模型：考虑一个具有N的传感器节点的传感器网络，节点周期性的收集数据，相应的节点集合可表示为S= {s1，s2， …，sn} 。假设网络和传感器节点具有以下性质：

（1）N个传感器节点随机、均匀地分布在M×M的正方形区域中，节点足够密集，保证一个节点的有效发射半径内存在其他节点。节点部署之后不再发生位置变化。

（2）sink节点位于观测区域外的某一固定位置，且没有能量和发射功率的限制。

（3）传感器网络为同构网络，即所有传感器节点初始能量相等，都有计算能力、信号处理能力和数据融合功能，且在网络中地位平等。每个节点都有唯一的标识（ID）。

（4）节点不知道自身的位置信息。

（5）节点可以感知当前自身的能量。

（6）节点的无线发射功率可控，即节点可以根据接收者的距离远近来调整其发射功率以节约能量。

（7）各节点间的链路对称。若已知对方发射功率，节点可以根据接收信号的强度RSSI计算发送者到自己的近似距离。

2.2 能量模型

LEACH-improved协议采用LEACH协议使用的无线通信模型。节点发射k bit的数据到距离为d的接收方，消耗的能量由发射电路损耗和功率放大损耗两部分组成，如公式（1）所示。

其中,Eelec表示发射电路损耗的能量，与编码、调制、滤波等相关；它与mp分别表示自由空间和多径衰落信道模型下功率放大器的能量消耗常数。节点在传输数据时具体采用哪种信道是由发送节点和接收节点之间的距离d决定的。如果两者之间的距离小于距离阈值d0，则采用自由空间信道模型；若距离大于d0，则采用多径衰落信道模型。很明显，后者消耗的能量比前者大得多。

节点接收k bit数据消耗的能量为：

此外，数据融合也会消耗一定能量，用EDA表示融合单位比特数据所消耗的能量。

3 LEACH-improved协议

LEACH-improved协议的思想是利用分簇和建立簇间多跳路径，来达到均衡网络负载、延长网络寿命的目的。在首轮成簇时，协议借鉴了LEACH的随机簇头选举机制，简单、快速地将网络分簇并选出首轮簇头节点。随着网络的运行，进入非首轮成簇阶段，协议考虑了每个簇内参选节点的剩余能量，选择剩余能量较多的节点担当下一任簇头，从而避免了能量已经不足的节点担当簇头。

簇形成之后，LEACH-improved协议借鉴了泛洪算法的思想，各簇头通过转发来自sink的包含跳数信息的广播包，在簇头节点间建立和选择多跳传输路径，使得远离sink的簇头不再使用长距离单跳通信方式传输数据到sink。

LEACH-improved协议中，簇头节点承担着数据采集、数据融合以及数据转发3项任务，能量消耗比普通节点大。为了平衡节点能量损耗，延长网络寿命，本协议也以“轮”为单位周期性执行，每轮循环分为簇形成阶段、簇间多跳路径建立和选择阶段以及数据传输阶段。其中，簇形成阶段根据实际情况又可分为首轮簇形成阶段和非首轮簇形成阶段。

3.1 簇形成阶段

3.1.1 首轮簇形成阶段

本阶段协议借鉴LEACH的簇头选举及成簇机制。因为初始状态下所有节点的能量相同，所以首轮成簇时不需要考虑节点的能量状况。每个节点产生一个0～1之间的随机数，与相应的阈值T(n)作比较，若产生的随机数小于T(n)则此节点当选为首轮簇头节点(FCH)，未当选的节点处于空闲状态。T(n)的计算方法如公式（1）所示。

其中，p为期望的簇头节点在所有传感器节点中的百分比，r表示当前轮数，n代表某个节点，G为第r轮之前尚未成为簇头的节点集合。

节点一旦成为首轮簇头节点，则向全网用CSMA(Carrier-Sense Multiple Access)的MAC协议广播其当选消息，该广播消息中包含了自己的ID。非簇头节点根据收到消息的信号强弱，选择信号最强的消息发送源节点作为自己的簇头，并向该簇头节点发送消息，请求成为该簇成员，消息中包含了自身ID和首轮簇头ID。首轮簇头节点收到成员节点的加入请求后，将各成员节点的信息保存在自己的路由表中。当簇头收到所有加入请求消息后，向各成员节点发送确认加入消息，消息中包含了本簇使用的CDMA编码、TDMA时隙表以及要求进入休眠状态的消息。不同的簇内部通信采用不同的CDMA编码，避免了相互之间的通信干扰。TDMA时隙表告知了成员节点何时可以传送数据到簇头。收到休眠状态消息后，成员节点即由工作状态转换到休眠状态，节省了能量，也利于簇间多跳路径的建立。

至此，首轮成簇阶段结束，网络运行进入下一阶段。

3.1.2 非首轮簇形成阶段

如果网络不是首轮成簇，那么本轮的簇头节点由上一轮的簇头指定。以第二轮簇形成过程为例来说明。

在首轮数据传输的最后一帧，各簇的成员节点会将自身剩余能量（Eresidual）信息连同采集到的数据一起发送给相应簇头，由簇头计算出本簇当前平均剩余能量(Eave)。簇头将计算结果发送给簇内各成员节点，各节点比较簇内平均剩余能量和自身当前能量的大小，满足Eresidual >Eave的成员节点均可参与竞争第二轮本簇的簇头节点，并向当前簇头发送竞选消息。若竞选节点不唯一，那么簇头节点指定距离自己最近的竞选节点成为第二轮的簇头（NCH），这里的距离可以根据收到竞选消息的信号强弱来判断。

第二轮簇头选定之后，当前簇头将成员节点包括自身的信息转交给第二轮簇头，并向本簇成员广播簇头转变的消息，随后，当前簇头状态转换为簇成员节点，第二轮簇头的状态转为簇头节点。新当选的簇头将选定的CDMA码、TDMA时隙表和进入休眠要求，以消息的形式广播给本簇成员。依此类推，以后各轮的簇形成过程均与第二轮相同。

3.2 簇间多跳路径建立和选择阶段

簇形成之后，sink将自己的跳数置为0，其余簇头节点将自身跳数置为最大值。然后，sink以发射半径d0向全网广播多跳路径建立消息，消息中包含了sink的跳数信息。收到消息的簇头节点，将sink节点加入自己的中继节点集中，同时将自身的跳数置为1，并向外转发来自sink的广播消息。利用传感器节点可以调节自身无线发射功率的特点，调整簇头的发射能量，使簇头节点之间的通信距离大于簇内通信的范围[9]。其他未收到过来自sink的广播消息的簇头，在收到相邻簇头转发来的消息后，将发送该消息的簇头加入到自己的中继节点集中，同时将收到的跳数值加1，更新为自身跳数信息，然后再进一步转发sink的广播消息。若某个簇头收到多个具有相同跳数值的簇头转发来的消息，则将它们都加入到中继节点集中。若簇头收到跳数值大于自身跳数值的消息，则丢弃该消息。依此类推，广播结束后，每个簇头节点都保存了通往sink的中继节点集，簇间多跳路径建立完毕。

簇头到sink的数据传输已经建立了多条通信路径，接下来在此基础上为每个簇头选择一条通往sink的最优路径。各簇头节点在其中继节点集中，选择距离自己最近的簇头作为其下一跳转发节点。这里的距离可以根据收到广播消息的信号强度来衡量。若最优转发节点失效，则可选择中继节点集中的其他簇头节点。

3.3 数据传输阶段

簇头为簇内成员节点分配好TDMA时隙，簇间多跳路径建立并选择好之后，各簇头向成员节点发送唤醒消息，使它们转换到工作状态，开始采集监测区域的数据，并在TDMA时隙表为其分配的时间槽内直接向簇头发送数据。簇头节点收集到所有成员发来的数据后，与自身采集的数据进行融合处理，再沿着已建立好的多跳路径传送给sink。

各成员节点在向簇头发送采集数据时，将自身的剩余能量“捎带”发送给簇头，以便簇头节点计算出下一轮簇头选举所需的本簇平均剩余能量。

为了节省资源开销，数据传输阶段的持续时间要比前两个阶段长得多。

4 性能分析

(1)LEACH协议单纯地依靠随机方式产生簇头，缺乏对簇头节点能量水平的考虑。虽然一个节点在1/p轮内仅有一次当选簇头的机会，但如果某些剩余能量已经很少的节点被选为簇头，它们必然会因大量消耗能量而过早失效，那么其所属簇内节点采集的数据就不能进一步传送到sink节点，此时网络的生存周期结束，网络中遗留大量未被充分利用的能量资源。这种部分节点因为过早耗尽自身能量导致网络原有覆盖区域缺失或者数据无法送达sink节点的现象叫作“能量空洞”[10]现象。

由于初始状态下网络中所有节点的能量均充足且相等，LEACH-improved协议在首轮采用了LEACH的随机簇头选举方式，简捷、快速的将网络分簇。之后每轮的簇头节点都由本簇内剩余能量大于簇内平均剩余能量的节点竞争产生，有效避免了能量较低的节点当选簇头，使网络负载更加均衡，防止了“能量空洞”现象的发生，继而延长了网络寿命。

（2）LEACH协议每轮都要重新建簇，且每轮簇重构时，网络的拓扑结构都会发生较大变化，同时全网所有节点都要参与此过程，由此带来的控制和通信开销是很可观的。

LEACH-improved协议每轮在不改变簇结构的基础上，重新选择簇头节点和成簇。各簇的成员只需参加本簇的簇头选举和成簇，不参与网络中其他簇的重建过程。因此避免了频繁簇重构带来的能量开销。

（3）LEACH协议要求所有簇头节点均与sink直接通信，sink附近的簇头向sink传送数据基本可以采用自由空间信道模型，距离sink较远的簇头很可能因采用多径衰落信道模型传输数据消耗大量能量，造成簇头节点间能耗的不均衡。

LEACH-improved协议通过在簇头间建立多跳传输路径，使得所有簇头之间的数据传输都可采用自由空间信道模型，从而大大节省了距sink较远的簇头节点的通信能耗，同时簇间负载也得到了均衡。

同时，LEACH-improved协议仅通过发送查询广播数据包进行寻路过程，并不进行采集数据的传输，并且通过调节簇头发射功率限制了消息的转发半径，因而也不存在泛洪算法固有的“内爆”和“重叠”问题。

（4）LEACH-improved的多跳传输路径使得簇头在向sink转发数据时，每一跳都可以充分地进行数据融合，从而减少了网络中的数据传输量，降低了节点的通信能耗。

5 仿真实验和分析

本文在TinyOS操作系统的TOSSIM仿真平台下对LEACH-improved协议进行仿真实验，演示新协议的工作过程。通过对比LEACH协议来验证它的有效性。

在100m×100m的正方形区域内随机部署100个节点，每个节点的初始能量为2J，其余参数设置为：Eelec=50nJ/b，EDA=5 nJ/b，d0=87，fs=10pj/bit/m2，mp=0.0013pJ/bit/m，数据包的大小是2000b，报头和广播包的大小是20b。

本文通过第一个节点的死亡时间（FND）和最后一个节点的死亡时间（LND），来衡量两种协议下网络的生命周期。仿真实验分别采用LEACH协议和LEACH-improved协议进行传感器网络的运行，得到了两种协议下网络运行轮数随死亡节点个数的变化关系，如图1所示。

由图1可见，LEACH-improved协议下FND比LEACH协议的延迟了近32% ，LND比LEACH协议的延迟了近24%。这是因为LEACH-improved协议在簇头选择时考虑了节点的能量状况，在簇头节点间通过构造中继节点集并选择最佳路径进行数据发送，使网络中节点能量能耗更加均衡，网络寿命得到了延长。

图1 LEACH-improved与LEACH的网络生命周期比较图

5 结论

本文通过对LEACH协议的分析，针对其在簇头选择、成簇及数据传输方面存在的不足，提出了一种基于能量且负载均衡的路由协议LEACH-improved，用节点剩余能量来约束簇头的选举，在簇头和sink间建立并选择多跳传输路径，保证距离较远的簇头采用多跳方式发送数据到sink。仿真结果表明，与LEACH协议相比，LEACH-improved协议平衡了簇间负载，节约了网络能量，网络寿命得到了延长。但LEACH-improved协议仍存在不足之处，比如，没有考虑到簇头在网络中是否均匀分布，各簇的大小是否合理等。这两点对于网络生命周期的延长都有很大影响，今后还需做进一步的研究和完善。

[1]杨文国，郭田德，赵彤.基于动态规划的无线传感器网络的路由算法[J].计算机研究与发展，2007,44(5):890-897.

[2]李建中，高宏.无线传感器网络的研究进展[J].计算机研究与发展，2008,45(1):1-15.

[3]陈力军，毛莺池，陈道蓄，等.平均度约束的无线传感器网络拓扑控制[J].计算机学报，2007,30(9):1544-1549.

[4]OK CS, LEE S, MITRA P, et al.Distributed energy balanced routing for wireless sensor networks[J].Computers & Industrial Engineering, 2009, 57(1):125-135.

[5]HEINJZELMAN W，CHANDRAKSAN A，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transcations on Wireless Communications, 2002,1(4):660-670.

[6]刘昕，王全玉，金旭亮.基于能量感知的数据汇聚和路由协议[J].计算机研究与发展，2008，45(1):83-89.

[7]GAUTAM N, LEE WI, PYUN JY.Dynamic clustring and distance aware routing protocol for wireless sensor networks[C]//Proceedings of the 6th ACM symposium on Performance evaluation of wireless ad hoc, sensor,and ubiquitous networks.Tenerife,Canary Islands,Spain:ACM Press, 2009:9-14.

[8]徐建波，李仁发.无线传感器网络中一种新型的混合型数据收集协议[J].计算机研究与发展，2008，45(2):254-260.

[9]乐世成，王培康.无线传感器网络中的节能路由算法[J].计算机工程，2008，34(7)：113-117.

[10]吴小兵，陈贵海.无线传感器网络中节点非均匀分布的能量空洞问题[J].计算机学报，2008,31(2):253-261.