基于覆盖率的无线传感器网络LEACH协议研究及改进*

马杰良，王 垚，顾蕾蕾

(1.南京信息工程大学电子与信息工程学院，南京210044;)

2.南京信息工程大学信息与控制学院，南京210044

随着信息技术的不断发展，人们对移动通信的要求越来越高。移动通信技术的发展和普及不仅方便了人们的生活，同时也推动了无线通信技术的发展。

无线传感器网络(WSN)是一种新型的网络和计算技术。它能够实时监测、感知和采集监测对象的信息并对其进行处理，再将信息传送到用户。随着无线传感器网络的日益成熟和普及，人们的生产、生活方式和工作效率也会随之得到不断的改善和提高。

路由协议是无线传感器网络层的核心技术。目前，WSN路由协议的种类已有很多，其目的是要节省系统的能量，延长系统的生命周期，提高系统的性能，主要有平面路由协议和层次路由协议两种［1－2］。

LEACH协议是第一个在无线传感器网络中提出的分簇式路由协议，在无线传感器网络路由协议中占有重要地位，具有分簇协议的基本特点。近年来，许多文章针对LEACH的分簇算法进行改进。随着人们对WSN路由协议的研究深入，以生存节点的个数来衡量WSN生命周期长短已无法满足人们对系统性能的高要求。于是以生存节点的覆盖率来衡量WSN生命周期这一新概念顺理成章地被现在的大部分学者所认可了［3－4］。覆盖率反映了网络区域被监测的状况，它的应用，有助于网络节点能量的有效控制、感知服务质量的提高和整体生存时间的延长。

文献［5］中算法根据节点的位置信息来计算节点与其邻居节点的覆盖关系，从而选取工作节点。为了避免产生覆盖盲区，采取了后退机制，该算法使网络保持完全覆盖，但算法运行复杂度较高。文献［6］中证明了当节点的通信半径大于等于两倍的感知半径时，若工作节点能够覆盖整个区域，则工作节点集合一定是连通的。并提出了OGDC算法，该算法按轮次运行，每轮开始时随机选择开始节点并广播消息。节点根据其邻居信息，自己的位置，计算是否被邻居节点覆盖。文献［7］中提出了根据节点密度信息来选择工作节点的算法SCOM，由节点周围邻居节点与骨干节点交互信息来决定节点是否为工作节点。文献［8］中提出了基于覆盖度的覆盖控制算法DSP，每个节点计算本地节点的覆盖度，针对应用对覆盖质量的精确要求，通过根据节点覆盖度来选择工作节点。

本文主要是在LEACH协议的基础上，根据检测到的邻居节点的数量，提出一种有效的算法，该算法通过对簇头节点分布及簇内实际覆盖率的优化来提高整个网络寿命。

1 LEACH协的分析

1.1 LEACH协议算法分析

LEACH协议是以循环的方式随机选择簇头节点，将整个网络的能量负载平均分配到每个传感器节点中，从而达到降低网络能源消耗、提高网络整体生存时间的目的。

根据文献［9］中所述，LEACH协议在运行过程中不断的循环执行簇的重构过程，每个簇重构过程可以用回合的概念来描述。其选取簇头的原则是:传感器节点随机的生成一个0，1之间的数，如果小于阈值T(n)，则该节点当选为簇头，T(n)按下列式(1)计算:

其中p为每轮节点成为簇头的百分比即p=k/N，k为一轮中成为簇头的个数，N为总的传感器个数，r为当前轮数，G是在过去的轮内未成为簇头的节点集合。这个算法可以保证每个节点在1/p轮内仅仅当选成为簇头一次。

选定簇头节点后，其通过广播告知整个网络。网络中的其他节点根据接收信息的信号强度决定从属的簇，并通知相应的簇头节点，完成簇的建立。

进入稳定阶段后，普通节点将采集的数据传送至簇头节点。簇头节点对簇中所有节点所采集的数据进行信息融合后再传送给汇聚节点。稳定阶段持续一段时间后，网络重新进入簇的建立阶段，进行下一回合的簇重构，不断循环，直至整个传感器网络的生命周期结束。

1.2 LEACH协议算法不足

LEACH协议的精华内容是分布式的成簇技术和自适应的成簇算法以及簇首位置的轮换算法。其中分布式的成簇技术保证了大数目的节点的自组织行为。自适应的成簇算法以及簇首位置的轮换算法保证所有节点公平地承担能量消耗的负担，最终可以延长整个系统的生存时间，但是LEACH协议还是有很多不足之处:

(1)LEACH协议的簇头选举是随机的，可能出现簇头分布不均而造成的信息传递时的能量损失。

(2)各节点担任簇头节点的机会均等，但因剩余能量的不同，可能会因某簇头能量过低而引起网络中断。

(3)LEACH协议的选簇及信息传递一般只考虑到用生存节点的个数来衡量传感器生命周期的长短及协议性能的好坏，并未从覆盖率的角度考虑，造成了重复的信息采集时的能量损失。

2 LEACH协议改进—LEACH-C协议

改进的LEACH—C协议主要针对LEACH协议分簇时簇头在网络中的分布不均问题及簇内覆盖冗余问题两方面进行优化。通过对邻居节点的测量排除每轮中不必要的工作节点以保证网络覆盖率并降低整个网络的能耗。

2.1 网络模型

假设所有传感器节点随机均匀地部署在一个正方形区域A中，节点密度足够大，若所有节点都处于工作状态，则可以覆盖整个区域A，且该网络具有以下性质:

(1)相对于节点的感知范围而言，监测区域A足够大，边界因素可以忽略;

(2)所有节点部署后不再移动，且无需人为进行维护;

(4)所有节点是同构的;

(5)每个节点无需装备GPS，且不能通过测量或定位方法获得其具体的物理位置;

(6)能量消耗满足LEACH协议的能耗模型

2.2 簇头节点的竞选

LEACH-C协议中，为保证簇头节点分布均匀并防止簇头节点处于监测区域A的边缘地段，根据仿真经验，首先规定两个簇头节点之间的距离不得小于2倍的Rs，且当某节点的剩余能量低于Emin时，该节点将失去簇头的竞选权以保证被选簇头有足够能量完成一轮的信息融合及传输工作，Emin按下列式(2)计算:

其中，Nact是簇内工作节点的平均个数，l为传输数据包长度，Eelec表示无线收发电路所消耗的能量，EDA表示数据融合所消耗的能量，εfs和εamp分别表示自由空间模型和多路衰减模型的放大器消耗的能量，d是簇头到Sink节点的距离，d0为常数，取决于传感器网络应用的环境。

在整个生命周期的初始阶段，以Rs为半径对外广播并接收周边节点的信息以确定自己的邻居节点个数nn，当nn小于1时默认取1。并以优先级pc1选出第1个簇头从而确保整个网络分布的相对密集区域附近有簇头节点存在。pc1按下列式(3)计算:

2.3.1 上消化道出血发生率 3项研究[3，5，19]报道了上消化道出血发生率，各研究间无统计学异质性（P＝0.62，I2＝0），采用固定效应模型进行分析，详见图2。Meta分析结果显示，试验组患者上消化道出血发生率显著低于对照组，差异有统计学意义[RR＝0.16，95%CI（0.07，0.34），P＜0.01]。

其中，nn为该节点的邻居节点个数，Ecurrent为该节点当前能量，E为节点初始能量，N为监测区域节点总数。

其余节点若与当前簇头的距离大于2倍Rs且其剩余能量不低于Emin，则其成为簇头的概率pcc按下列式(4)计算，成为簇头的概率与节点自身的剩余能量有关:

2.3 簇内工作节点的竞选

簇头选举结束后，在该轮成功当选的簇头节点以广播的方式告知整个网络，普通节点收到广播后，根据到各簇头的距离及各簇头当前能量为条件选择适当簇头入簇，其优先级pntoc按下列式(5)计算:

其中，dtoc为普通节点到簇头的距离，Ec为各簇头当前能量。

当普通节点入簇结束后，将广播告知簇头节点自己已加入该簇。簇头节点接收通知并计算出该簇当前簇内成员总个数，若簇内成员个数大于Nact个，则根据优先级pwork选择本轮簇内的工作节点。

根据文献［10］提出，假设工作节点密度为ρ，定义为一个单位区域内工作节点的数量。由于节点是随机均匀分布的，故可推得传感器网络中，平均工作节点密度ρ公式如下式(6):

即，实际情况下，若要使整个簇内区域被完全覆盖则平均需要的工作节点个数Nact可按下式(7)计算，其中A为整个检测区域面积:

由文献［11］可知，邻居节点的个数与该节点的被完全覆盖率及覆盖面积成正比，即一个节点的邻居节点个数越多，其感知区域被完全覆盖的概率及多余面积的百分比就越高，邻居节点个数与节点的覆盖关系如表1所示。

表1 邻居节点个数与节点覆盖关系

由上表可知，邻居节点多的节点，其感知区域同时被其他节点覆盖的几率越高，其收集到的信息冗余率也就越高。

故，成为簇内工作节点的优先级pwork可根据该节点的邻居个数及剩余能量得出，按下式(8)计算，竞选出Nact个工作节点:

工作节点竞选结束后，该轮未被选出的节点将进入休眠状态，不进行数据采集工作，而选出的工作节点将广播告知簇头，开始收集信息并传送给簇头节点，簇头节点对接受到的信息进行簇内融合后传递给Sink节点，该回合结束。

由上所述，簇内工作节点竞选算法伪码如下:

2.4 节点低能耗处理

当网络中，某节点的剩余能量低于Edead时，认为该节点死亡，死亡节点将向半径为Rs内的节点广播告知其死亡消息，收到广播的节点将自己的邻居

3 改进后的性能仿真及分析

3.1 模拟实验环境设置和参数

节点数nn减1(nn小于1时默认取1)。Edead按下列式(9)计算，其中cm为广播数据包长度:

我们用Matlab作为仿真实验平台，并使用与文献［12］中相同的能量模型。发送数据和接收数据的无线通信模型分别为:

其中，Eelec表示无线收发电路所消耗的能量;εfs和εamp分别表示自由空间模型和多路衰减模型的放大器消耗的能量;d0是常数，取决于传感器网络应用的环境。各项实验参数如表2所示。

表2 仿真参数

3.2 簇头分布分析

为了验证LEACH-C协议选出的簇头分布良好，在100 m×100 m区域中，随机部署100个节点，并随机取样验证LEACH协议簇头与LEACH-C协议簇头的分布情况，其对比图如图1所示。

由上图可以看出，因LEACH协议对簇头的选举并未考虑簇的平均分布，故LEACH协议选出的簇头易在一小部分区域内密集分布，导致传输信息时不必要的能量消耗。而LEACH-C协议的首簇头选举被要求为邻居节点较多的节点，这样就保证了在节点分布相对密集的区域附近必有簇头，并使得在两倍的Rs半径内不再有其他簇头分布，从而达到使网络中的簇分布较为均匀的效果。

3.3 仿真结果分析

图2是基站位置为(50，180)，监测区域A大小为100 m×100 m，节点数量为100时生存节点数与网络工作时间(轮数)之间的关系图.可以看到，图2

图1 LEACH协议与LEACH-C协议簇头分布对比图

中表示LEACH协议的曲线在第700轮开始出现节点死亡，最后一个节点的死亡时间为1 800轮。而LEACH-C协议的第一个死亡节点出现在第1 300轮，到2 500轮后节点的全部死亡。由此可知，从以生存节点数为网络寿命的定义出发，相比LEACH协议，LEACH-C协议使得网络寿命提高了24%(第1个节点死亡)。

图2 生存节点数与轮数关系图

图3 网络覆盖率与轮数关系图

图3是基站位置为(50，180)，监测区域A大小为100 m×100 m，节点数量为100时生存节点网络覆盖率与网络工作时间(轮数)之间的关系图。因为LEACH中所有节点都处于工作状态，能量消耗较快，又由于选取簇头时没有考虑节点能量大小，导致节点快速死亡，网络覆盖率迅速下降。而LEACH-C协议由于每轮簇头分布相对均匀且按优先级选取工作节点，并非每轮中每个节点都在工作，故在网络寿命初期，网络覆盖率并没LEACH协议高，但网络寿命后期LEACH-C协议覆盖率明显处于平稳下降状态。从以网络覆盖率为网络寿命的定义出发，与LEACH协议相比，LEACH-C协议使整个网络寿命提高了28%(网络覆盖率为0)。

4 结论

本文提出了一个基于LEACH协议的无线传感器网络覆盖率算法－－－LEACH-C协议。在LEACHC算法中，节点通过与邻居节点交换信息，根据邻居节点的个数及剩余能量选择簇头节点及工作节点。仿真实验结果表明:在不需要节点的位置信息的前提下，LEACH-C算法不仅可以提供良好的覆盖性能，而且在减少整体能量消耗，网络能量均衡方面也具有良好的性能。

［1］李梦娥，张登银.无线传感器网络簇类路由协议的研究［J］.电子工程师，2008(4):60－63.

［2］吴臻，金心宇.无线传感器网络的LEACH算法的改进［J］.传感技术学报，2006，19(1):34－36.

［3］王伟，林锋，周激流.无线传感器网络覆盖问题的研究进展［J］.计算机应用研究，2010，27(1):32－35.

［4］王燕莉，安世全.无线传感器网络的覆盖问题研究［J］.传感技术学报，2005，18(2):401－406.

［5］Tian D，Georganas N.A Coverage Preserved Node Scheduling Scheme for Large Wireless Network［J］.Proc.of First International Workshop on Wireless Sensor Network and Applications(WSNA’02)，Atlanta USA，2002，September，32－41.

［6］Zhang H，Hou J C.Maintaining Sensing Coverage and Connectivity in Large Sensor Networks［J］.International Journal of Ad Hoc and Sensor Wireless Networks，2005，1(1):89－124.

［7］Lu Jun，Wang Jin-su，Tatsuya Suda.Scalable Coverage in Maintenance for Dense Wireless Sensor Networks［J］.IEEE 2006，651－660.

［8］Luo Han-mei，Wang Huan-zhao.A Precise Coverager Control Protocol with Limited Communication in Wireless Sensor Networks［C］//IEEE International Symposium on Embedded Computing，2008，149－154.

［9］单晓娜，李力.LEACH路由协议技术的分析及改进［J］.计算机与现代化，2009(9):81－83.

［10］毛莺池，刘明，陈力军，等.DELIC一种高效节能的与节点位置无关的传感器网络覆盖协议［J］.计算机研究与发展，2006，43(2):187－195.

［9］任秀丽，教传亮，薛建生，等.与节点位置无关的无线传感器网络覆盖控制算法［J］.小型微型计算机系统，2011，32(1):121－125.

［10］刘明，龚海刚，毛莺池，等.高效节能的传感器网络数据收集和聚合协议［J］.软件学报，2005，16(12):2106－2116.