一种能量高效的无线传感器网络拓扑控制算法

江禹生，李 萍，马 超

（重庆大学通信工程学院，重庆市 400030）

0 引言

无线传感器网络低功耗、低成本、自组织与分布式等特点使其成为信息获取的重要技术，然而资源受限使得对无线传感器网络的应用面临着巨大的挑战。减少能量消耗，延长网络生命周期是无线传感器网络领域的重要研究方向。拓扑控制作为无线传感器网络中减少能量消耗、延长网络生命周期的重要技术［1］，近年来成为了无线传感器网络领域研究的热点与难点之一。

现有的拓扑控制算法主要集中于节点功率控制和分簇的层次型拓扑控制2个方面，本论文主要针对分簇的层次型拓扑控制算法进行深入研究。LEACH（low-energy adaptive clustering hierarchy）［2］是比较经典的层次型拓扑算法，其他的算法:HEED（hybrid energy-efficient distributed）［3］，DEEUC（distributed energy-efficient unequal clus-tering）［4］等，几乎都是在LEACH算法基础上做的改进。

由于LEACH是随机等概率的选择簇头，没有考虑节点的剩余能量，簇头数量和质量都得不到保证。针对簇头能耗过大的问题，Yassein M B等人在文献［5］中提出了VLEACH（vice-LEACH）算法，该算法簇头的选择过程中设置了候选簇头以均衡全网的能量消耗，但该算法未考虑全网的能量分布情况;在文献［6］中，王伟超等人提出了LEACH-H算法，该算法在簇头选择过程中考虑了能量因素，但其涉及到邻居节点ID、邻居节点剩余能量、被选作为簇头的次数、是否是邻居节点4个数据项，增加了节点间的通信量，因而增加了能量的消耗;在文献［7］中，周治平等人提出了EB-LEACH（energy balance LEACH）算法，该算法在簇头的选择过程中增加了能量阈值这一约束条件，但该算法只能平衡簇头地区的能量分布，缺乏对全网能量消耗的平衡;通过对网络中最佳簇头数目的考虑，Thein M C M等人在文献［8］中提出了能量有效的簇头选择算法，但该算法忽略了稳定阶段的能量消耗。

本文在LEACH分簇算法的基础上结合EB-LEACH的一些优秀思想，分别从建立阶段和稳定阶段进行改进，提出了一种能量高效的拓扑控制算法（energy efficient topology control algorithm，EETCA）。其基本思想是:在簇头的选举中，考虑节点的剩余能量，保证每轮选举最佳节点当选簇头;簇的形成综合考虑了簇的规模，防止簇头节点因为簇的规模过大而过早死亡;数据稳定传输阶段，簇头与Sink节点间的通信采用多跳路由方式，平衡网络负载。

1 相关理论

1.1 能耗模型

通常传感器节点的能量消耗模型采用文献［2］中提出的无线电能量消耗模型，如图1所示。

图1 无线电能量消耗模型Fig 1 Radio energy dissipation model

在该模型中，传感器节点发送kbit的数据包到距离为d的另一个传感器节点，所消耗的能量由发射电路损耗和功率放大损耗两部分组成，用ETx（k，d）表示

节点接收kbit数据包消耗的能量用ERx（k）为接收数据主要是电路能量消耗，具体见式（2）所示

1.2 最优簇数目

在EATC算法中，簇头与Sink节点的通信采用多跳方式，结合文献［2］中对LEACH算法最优簇数目的推导，可以对最优簇数目的计算公式进行调整。

则整个网络的能量消耗Etotal为

其中，EDA为簇头进行数据融合所消耗的能量，dCH-to-CH为簇头与相邻其他簇头之间的平均距离。

对式（5）求导并令导数等于0，可得出改进的最优簇的数目mopt，计算如式（6）所示

1.3 多跳通信

大量研究表明，当网络规模较大时，簇头与Sink节点的通信采用多跳方式可以显著降低能量消耗［9］。

对于节点多跳通信，如图2所示，数据在线性网络链路上转发。其中相邻2个传感器节点间的平均距离为d，最后一个节点B到汇聚节点的距离也为d。假设节点A发送一个kbit的数据包，数据包数据经过n跳传输到达汇聚节点，所消耗的能量为

式（7）对n求导，并令导数为0，可以求出簇头发送信息到基站的最优跳数nopt。

图2 多跳转发网络模型Fig 2 Multi-hop transmit network model

2 EETCA实现策略

2.1 网络模型

为了便于控制策略的描述和分析，先做如下假设:

1）监测区域为规则正方形，基站在监测区域的中心位置，能量没有限制;

2）节点均匀分布在监测区域中，所有节点都知道自己的位置信息，节点位置固定不动;

3）每个节点具有相同的初始能量，且能够获得自身的剩余能量，都可以与基站直接通信;

4）链路是对称的，可以根据源节点的发射功率和接收信号的RSSI估计到源节点的距离;

5）忽略真实环境中存在障碍物等影响通信质量的因素，所有节点的数据包都能够进行可靠传输。

2.2 EETCA 设计思路

2.2.1 簇头选择阶段

在此过程中，各节点首先选取一个［0，1］之间的随机数，如果节点n产生的随机数小于阈值T（n），则将节点n选为候选簇头。然后继续计算此时候选节点的剩余能量，并与能量阈值Eth进行比较，当节点的剩余能量大于该轮的能量阈值Eth时，则该节点当选为簇头，然后簇头节点向网络中发送广播信息［9］。其中T（n）的计算公式为

其中，p为节点当选簇头的概率;r为选举轮数;G为最近1/p轮中还未当选过簇头的节点集合。

第r轮节点的能量阈值Eth的计算公式为

其中，L为网络预计要运行的轮数，E0为节点的初始能量。

通过引入能量阈值，有效地防止了低能量的节点成为簇头，避免了因为簇头死亡造成的数据丢失和网络空洞，使网络能量得到均衡的利用，显著地延长网络的寿命。

2.2.2 簇的建立阶段

离Sink节点近的簇头承担了转发其他簇头数据信息的任务，其能量消耗比离Sink节点远的簇头大，为了保证各簇头节点的能量消耗达到均衡，离Sink节点近的簇的规模应适当的减小［2］。

假定簇头节点都以一定的功率进行通信，其传输半径为R，非簇头节点根据式（10）加入相应的簇

其中，dj-to-CHi为节点j到簇头i的距离，di-t--Sink为簇头i到Sink节点间的距离，NCHi为簇头i的一跳邻居数，γ为权重。

节点在入簇过程中，综合考虑了簇头的邻居数与传感器节点到簇头的距离，防止某个簇的规模过于庞大，均衡簇头能量消耗。当所有传感器节点都已成簇之后，簇头节点为簇内节点分配通信时隙和进行簇内通信的直接序列扩频码，然后进入稳定数据传输阶段。

2.2.3 稳定数据传输

基站根据网络规模使用式（7）算得最优跳数nopt。簇内节点以单跳方式把数据发送到簇头，簇头进行数据融合，然后查询路由表，若Sink节点在其通信范围之内，则直接将数据信息发送给Sink节点;若不在，则根据最优跳数选择转发代价Etotal最小的簇头作为下一跳，间接将数据传送到Sink节点。

3 仿真实验与结果分析

本文采用Matlab建立了网络仿真模型，对EETCA进行仿真分析，并从网络整体剩余能量、存活节点数等方面与LEACH，EB-LEACH算法进行比较。

3.1 仿真模型与参数设置

100个传感器节点随机分布在100 m×100 m的监测区域内，Sink节点部署在坐标为（50，50 m）的点上，如图3。

图3 网络中随机分布100个节点的示意图Fig 3 Schematic diagram of 100 sensor nodes are scattered randomly in networks

实验的其他参数如表1所示。

表1 实验参数Tab 1 Experimental parameters

3.2 结果分析

3.2.1 最优跳数

图4是当跳数n取不同值时，一个数据包经过网络传输到达基站时所消耗的能量关系图。从图中可以看出:当n从1变化到2时，能量急剧下降，这主要是因为n=1时节点无线通信模块的能耗与通信距离的四次方成正比;n=2时，网络能耗达到最小值。随着n的增大，增加了网络对数据的转发，网络能耗也随之增加。

图4 能量消耗与传输跳数关系图Fig 4 Transmission hop number vs energy dissipation

3.2.2 网络剩余能量

图5是网络整体剩余能量随网络运行轮数的变化曲线。从图中可以看出:本文提出的EETCA每轮剩余的总能量最多，其次是EB-LEACH算法，最差的是LEACH算法。主要因为EETCA中簇头的选举、簇的形成以及数据的传输方式更加合理，减少了节点的能量消耗，使网络每轮的剩余能量随之增加。

图5 网络整体剩余能量与网络运行轮数关系图Fig 5 Network running number of sheaves vs overall residual energy of network

图6是3种算法节点剩余能量的标准差随网络运行轮数变化的曲线图。EETCA的节点剩余能量标准差比LEACH算法和EB-LEACH算法的都小，且随着轮数的增加有明显的下降趋势。其根本原因在于，EETCA在均衡簇头节点和普通节点能耗的同时，还通过减小离Sink节点近的簇的规模均衡了簇头之间的能耗，使网络总体能量消耗更加均衡。

图6 节点剩余能量标准差与网络运行轮数关系图Fig 6 Network running number of sheaves vs standard deviation of residual energy of node

3.2.3 网络生命周期

图7是随着网络运行轮数的推移，在相同的环境条件下，3种算法的存活节点个数与网络运行轮数关系图。由于EETCA与EB-LEACH算法在簇头选择阶段都充分考虑了节点的剩余能量，因此，在同样规模的环境下网络生命周期明显较LEACH算法长。又由于EETCA在簇的形成时考虑了簇的规模，在稳定数据传输阶段采用单、多跳相结合的方式传输数据，所以，EETCA与EB-LEACH算法相比，网络生命周期又有一定延长。

图7 存活节点个数与网络运行轮数关系图Fig 7 Network running number of sheaves vs number of nodes alive

表2统计了3种算法在第一个节点死亡、10%的节点死亡和剩余节点为节点总数10%时的轮数。如果以网络剩余节点为节点总数10%作为网络生命周期判断，3种算法网络生命周期分别为707，1484，1633，可以看出:EETCA有效地延长了网络生命周期。

表2 3种算法节点死亡轮数比较Tab 2 Death number of rounds comparison of three algorithms of node

4 结束语

本文提出了一种能量高效的拓扑控制算法，该算法主要从簇头的产生、簇的形成以及稳定阶段数据传输3个方面对LEACH进行了改进，并与LEACH和EB-LEACH算法进行比较。仿真实验验证了EETCA算法在网络整体剩余能量、存活节点数方面均优于LEACH和EB-LEACH算法。

［1］Mahfoudh S，Minet P.Survey of energy efficient strategies in wireless Ad Hoc and sensor networks［C］//The Seventh International Conference on Networking，Cancun:IEEE，2008:1-7.

［2］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）:660-670.

［3］Younis O，Fahmy S.HEED:A hybrid，energy-efficient，distributed clustering approach for Ad Hoc sensor networks［J］.IEEE Trans on Mobile Computing，2004，3（4）:660-669.

［4］尚凤军，Mehran Abolhasan，Tadeusz Wysocki.无线传感器网络的分布式能量有效非均匀成簇算法［J］.通信学报，2009，30（10）:34-43.

［5］Yassein M B，Al-zou'bi A，Khamayseh Y，et al.Improvement on LEACH protocol of wireless sensor networks（VLEACH）［J］.International Journal of Digital Content Technology and Its Applications，2009，3（2）:1-5.

［6］王伟超，代增全，徐启建.LEACH协议簇头选择算法的改进［J］.无线电工程，2010，40（3）:1-3.

［7］周治平，王 亭，张明亮.传感器网络中一种能量有效的簇头选择机制［J］.计算机工程与应用，2012，48（8）:105-108.

［8］Thein M C M，Thein T.An energy efficient cluster-head selection for wireless sensor networks［C］//2010 International Conference on Intelligent Systems，Modelling and Simulation（ISMS），2010:287-291.

［9］Li C F，Chen G H，Ye M，et al.An uneven cluster-based routing protocol for wireless sensor networks［J］.Chinese Journal of Computer，2007，30（1）:27-36.

［10］Rashed M G，Kabir M H，Ullah S E.WEP:An energy efficient protocol for cluster-based heterogeneous wireless sensor networks［J］.International Journal of Distributed and Parallel Systems（IJDPS），2011，2（2）:54-60.

［11］Saini P，Sharma A K.Energy efficient scheme for clustering protocol prolonging the lifetime of heterogeneous wireless sensor networks［J］.International Journal of Computer Applications，2010，6（2）:30-36.