基于半径递增有向成簇的WSN路由算法

李长庚，于澄澄，陈东海

（中南大学物理与电子学院，长沙410083）

无线传感器网络［1］实现了计算机世界、自然世界与人类社会三元世界的无缝连接［2-4］，是一个全新的信息获取平台，其节点一般部署在无人值守地域，资源能量有限，因而在相关研究和设计时必须突出考虑能量因素，以获得更长的网络生命周期。

分簇路由算法（如LEACH［5］）采用划区组簇的方式，减小了与基站直接通信的节点数量，降低了通信开销，其簇头轮换机制能有效均衡簇头的能耗消耗。其缺点在于簇头地位关键，能量消耗大，容易出现“热点”，簇头选举成本大，算法复杂度高，另外，簇规模与位置难以控制。

链式路由算法（如PEGASIS［6］）通过减小节点间的平均通信距离，降低了网络通信成本。其不足之处包括：一是链式结构层级众多，通信延时较大；二是每个节点都承担融合数据的任务，使得全网在数据融合方面的能量消耗偏大；三是由于采用贪婪算法寻找下一跳节点，在组网后期容易出现下一跳节点的距离较远的情况；四是链式结构不能对低能量节点进入筛选，结构中任何一个低能量节点的死亡都将导致结构重组，增大了重组频率。

LEACH算法是经典的分簇路由算法，所有节点等概率地随机担当簇头，不考虑节点能量问题。HEED［7］算法和TEEN［8］算法在选择簇头时考虑了能量因素，使得能量较大的节点担任簇头的概率较高。EEUC［9］算法、EOUCP［10］算法、CHTD算法、LDB⁃PL［11］算法引入了竞选半径非均匀、竞选时间延迟、分层次成链等概念，文献［12］还提出了代理簇头的思想，这些算法改进了选举簇头过程，其结果更趋合理，但依然存在一定的随机性，且选举过程受到多个约束条件限制，这增加了算法复杂度，同时提高了节点成簇组网过程的能耗。

基于以上分簇算法和链式算法优点与不足，设计一种半径递增有向成簇路由算法，其基本思想为“向基站方向成链，链中尽量成簇”，在操作程序上，各节点以较小半径值R0组簇，然后簇头和未进入网络的其他节点以更大的半径2R0，在其前向传输区域内选择下一跳节点，之后再增大组网半径，直至所有节点加入网络。最后通过与LEACH算法和目前较典型的EEUC算法进入仿真实验比较，验证算法性能并进行参数分析。

1 系统模型与理论描述

1.1 网络模型

无线传感器网络是一个面向应用的系统，不同的应用环境需要不同的网络模型。假定N个传感器节点随机均匀分布在一个面积为M×M的区域A内，并且有如下性质：①所有节点部署后不移动，能量不补充；②基站部署在区域A内或边界外一个固定位置，并且是唯一的；③无线信道满足对称性，即正向传输和反向传输等量的数据消耗的能量相同；④节点同构，具有相同的处理和通信能力，在网络中地位平等；⑤节点无线发射功率可控，可根据距离调整发射功率；⑥节点可以获取无线接收信号的强度［13］；⑦采用数据融合技术减少传输的数据量。

1.2 无线通信能量模型

网络中节点通信采用Heinzelman等人在文献［14，15］中提出的无线通信模型。当发送节点与接收节点的距离小于阈值d0时，采用自由空间模型，否则采用多路衰减模型［16.17］。发送方发送长度为lbit的数据到距离为d的位置消耗的能量为：

而接收方接收lbit的数据所需能量为

其中，发射电路系数与接收电路系数数值相等，ETx-elec=ERx-elec=Eelec=50 nJ/bit，自由空间模型发射放大器εfs=10 pJ/bit/m2，多径衰减模型发射放大器εmp=0.0013 pJ/bit/m4，数据融EDA=5 nJ/（bit/signal），阈值。

1.3 前向传输概念

在分簇结构中，簇内和簇间时常会出现某节点距离基站的距离比其下一跳节点距离基站更近的情况，即数据传送到了距离基站更远的节点，为避免这种数据“回流”现象，这里引入前向传输的概念。如图1，节点i只把数据传输给在其通信范围内距离基站更近的邻节点中的一个，其可能位置为：以基站为中心、dtoBS(i)为半径的圆和以节点i为中心、以节点i通信距离参数dR为半径的圆的重合区域，这排除了节点向后传输数据的可能。

图1 前向传输区域示意图

在前向传输区域内选择一个最终的节点作为节点的下一跳节点，引入节点度、剩余能量、节点间距、节点与汇聚节点的距离等参数，构建节点i到节点j的通信链路的前向传输因子FTF(ij)（Forward Transmission Factor）：

其中，Dback(j)为节点j的反向节点度（即由其节点度减去其可能的下一跳节点个数），E(j)为节点j当前的剩余能量，dtoBS(i)和dtoBS(j)为节点i和节点j到基站的距离，d(i,j)为节点i与节点j之间的距离。

1.4 链中成簇思想

如图2（a）所示，链式结构层级众多，导致时延较大，同时，每个节点都承担有融合数据的任务，造成额外能量消耗，再者，链式结构无法考虑能量因素，低能量节点也进入链中，一旦某个节点过早消亡，链路即遭到破坏。图2（b）和图2（c）为不同能量条件下链中尽量成簇示意图，即在链式结构基础上，较为密集的节点或个别能量较低的节点，以簇的方式加入网络。这种混合结构保证了数据传输距离趋向最近，而传输层次也较少，且参与数据融合的节点也较少，最重要的是可以将低能量的节点以簇内成员节点或者子节点的形式加入网络，避免该节点进入主路径后由于过快消亡后导致大片区域数据丢失。

图2 链中尽量成簇示意图

1.5 平均剩余能量估计

为提高能量消耗均衡性，便于节点了解自身剩余能量在全网络中所处的水平，通常需要对节点的平均能量进行计算，但平均能量的计算需要统计全网的剩余能量信息，这对分布式路由算法是非常困难的，这里引入估计方法，对平均能量进行相应估计。首先粗略估计全网每一轮消耗的能量Eround

式（4）中，Etotal为全网初始总能量，r0为估计轮数，即网络理论生存周期，在实验过程中可采用递归的方法取得，这里不作论述。估计全网剩余能量的平均值为

其中，N为节点数目，r为实验轮数。

2 半径递增有向成簇路由算法

根据本文算法的步骤，首先进行初始化；然后在半径R0内组簇；然后若有节点尚未接入网络则增加半径，在新的半径内组簇；最后直至所有节点接入网络，算法结束。

2.1 初始化

算法开始时，各节点自动获得一个唯一的节点ID，基站首先以额定的功率向全网广播消息，节点根据接收消息的信号强度确定自身与基站的近似距离di-BS(i)［18］，并通过限定的功率与周围节交换信息，分别确定半径R0，2R0，3R0内的节点度Ddegree1，Ddegree2，Ddegree3，反向节点度Dback1，Dback2，Dback3，并更新邻节点信息表、缓存表等信息，如图3所示。

2.2 半径R0内组簇

算法中，在半径R0内选择簇头和半径2R0以上选择下一跳节点时，引入了一个能量阈值，即要求节点能量必须大于，才有可能被选为簇头或者下一跳节点。这里，为平均能量估计值，由式（4）～式（5）得到，w为调节参数，取值范围为［0，1］。

图3 随机分布的传感器节点

根据初始化数据，采用投票机制竞选簇头。在未对全网节点划分区域的情况下，各节点在包含自身在内的半径R0范围内，根据式（6）计算权值，将票投给权值最大的节点，使其成为备选簇头，各备选簇头统计自身被投票次数，并检查半径R0范围内有无其它备选簇头，若有，则再次进行权值比较，权值小的节点退出簇头竞选，若无，则宣布自身成为簇头，并召集簇内成员。

其中，E(i)为节点剩余能量，为全网节点平均剩余能量，Ddegree1(i)为节点的节点度，w为调节系数。该权值综合了节点能量和节点位置两个因素，第一项反映了节点的能量因素，其对节点竞选簇头设置了一个阈值，在达到这个阈值的条件下，节点能量越高，权值也会越大；式中第二项反映了节点的位置因素，即节点的节点度越大，其成为簇头的权值也会越大。

如图4，节点7和节点8在半径R0范围内互为唯一邻节点，在能量相同区别不大的情况下，由于节点8离基站更近，故而成为簇头；又如节点6、节点9、节点10三个节点中，由于节点10的后向节点度大于节点6和节点9，更容易成为区域簇头。

图4 节点在半径R0内组簇示意图

2.3 半径2R0范围内组网

在半径R0范围内完成组簇的路由结构是不完整的，仍然存在较多的节点和簇头未接入网络，这些节点可以扩大组簇半径至2R0进行组簇，其步骤和与前面相似。未接入网络的节点i（或簇头）查看半径至2R0范围内邻节点信息，若存在距离基站更近的邻节点j（或簇头），则根据根据公式（7）确定一个节点作为自身的簇头并加入。

该权值计算式的前提是节点i必须位于节点j的前向传输区域内（见图1），即节点i必须位于以基站为中心、dtoBS(i)为半径的圆和以节点i为中心、以通信距离参数dR=2R0为半径的圆的重合区域，这排除了节点向后传输形成“回流”或“环路”的可能性。权值计算式的第一项为节点能量参考因素，它设置了一个阈值，即能量低于的节点不能成为备选节点；第二项为位置参考因素，它能保证更加靠近节点i和基站连线的节点具有更高的权值；第三项是基于尽量成簇思想（见图2）的权重因子，它能保证反向节点度较大的节点同时接收更多的子节点，节省数据融合的成本，减少路由层次。图5为节点在半径2R0内组簇示意图。

图5 节点在在半径2R0内组簇示意图

针对仍未接入网络的节点或者簇头，继续采取增加组簇半径至3R0，4R0的方式，直至所有节点均接入网络，构成一个连通的簇树。如图6是半径为3R0时的网络图，图7为最终路由结构。

图6 节点在半径3R0内组簇示意图

图7 最终路由结构图

3 仿真实验与参数分析

3.1 仿真实验

仿真场景参数设置为：在边长M=100 m的区域内随机分布N=100个传感器节点，节点初始能量E=0.5 J，部署后不移动，基站位于（150，50），其能量不受限制，初始成簇概率p=0.05，基准半径R0=22 m，假设节点每次发送或接收数据长度为l=4 000 bits。在相同的条件下，对LEACH、EEUC和本案算法三者进行比较，得到三种算法死亡节点个数随仿真轮数的变化图，见图8。

图8 N=100时生命周期比较图

由图8可以看出，LEACH算法在750轮左右开始出现死亡节点，到1350轮左右全部节点死亡，时间跨度约为600轮；EEUC算法在1200轮左右时节点开始死亡，在1600轮左右全部死亡，跨度约为400轮；本案算法在1500轮左右出现第一个死亡节点，到1800轮左右节点全部死亡，时间跨度约为300轮。这说明新算法在能够保证各节点的能量消耗速度更加平衡，即有能耗均衡性能上有较大提高。能量均衡性能提高带来的直接结果是网络生命周期的延长，尤其是第一个节点死亡的时间延迟效果明显。在上述仿真条件下重复实验50次，统计其第一个节点死亡时间（FD）和全部节点死亡时间（AD），得到如表数据，从数据结果可知，新算法在第一个节点死亡时间和全部节点死亡时间上比EEUC分别提高了17%、9%。

表1 网络生命周期

修改仿真场景参数：在边长M=100 m的方形区域内部署节点N=200个，其他条件不变，即不改变监控区域大小而将节点密度增加1倍，得到数据如图9。与图8相比，图9所示各算法的生命周期均有所延长，这是由于当节点密度增加后，各节点间的通信距离减小，使得通信能耗也随之降低。从网络生命周期来看，本案算法比EEUC算法在FD和AD上分别提高约24%和9%。从时间跨度上来讲，LEACH和EEUC算法相对于低密度节点场景均有一定程度的增加，这是由于随着节点密度的增大，整个网络的层次结构和簇成员数量也相应增加，致使簇头能量消耗加快，使网络能耗的均衡性能下降。而本案算法在节点密度增大时，第一个节点死亡和全部节点死亡的时间跨度增加较小，这说明算法在节点高密度条件下的能量均衡性能和能量效率更优。

图9 N=200时生命周期比较图

3.2 参数分析

此节分析了基准半径R0与调节参数w对本文算法的影响。首先是对R0的分析。

半径递增有向成簇算法的提出中，引入了一个新的参数——基准半径R0，算法的的一个核心内容是在半径R0的范围内组簇，R0直接决定了簇的大小和簇的数量，所以在应用和仿真中应该首先给出参数R0的值。在具体的应用与仿真中，由于监控区域的规模、节点的密度等条件的不同，R0的最优值并不是固定不变的。

在上述M=100 m，E=0.5J，基站（150，50）条件下，分别对N=100和N=200两个场景仿真，R0从10 m到40 m按步长2 m递增，对每个值进行10次实验，得到其第一个节点死亡的平均时间（轮数）的变化，如图10和图11。

图10 N=100时第一个节点死亡时间随R0变化图

图11 N=200时第一个节点死亡时间随R0变化图

从图10和图11中可以看到，当基准半径R0的取值从10 m到25 m左右时，第一个节点死亡的时间逐渐延迟，这是因为随着基准半径R0的增大，簇类结构在路由结构中所占的比例也越来越高，分簇路由的优势在算法中的优势得到更多体现。当基准半径R0的取值从25 m左右继续增大时，第一个节点死亡的时间是逐渐提前的，尤其是在R0=30 m左右时，出现断崖式的下降，原因在于随着基准半径R0的继续增加，分簇结构在网络路由中所占比例过大，挤压了链式结构的比重，前文所述的前向传输思想的应用范围逐渐缩小，导致网络生命周期大大缩短。尤其是当R0=30 m以后，路由结构中簇在直径达到60 m以上，这跟LEACH算法已经十分类似。

通过对比还可以看到，图11比图10在相同的基准半径条件下第一个节点死亡的时间均有所延迟，即网络生命周期延长，原因是在于节点密度增大后，节点间的通信距离减小，通信能耗也相应减小，利于延长网络生命周期。另外，在节点数量N=100条件下，基准半径在20 m～24 m左右时第一个节点死亡时间最迟，最佳基准半径为R0=22 m；在节点数量N=200条件下，基准半径在22 m～26 m左右时网络生命周期是长，最佳基准半径R0=24 m。说明随着节点密度的增大，最佳基准半径也有所增大，这是由于密度增大时，相同半径内的邻节点也会越多，各个簇内的成员节点也越多，由于数据融合而节省的能量也更多，在相同总能量的条件下，节省的这部分能量可以使节点将数据发送到更远的距离，基准半径的值也相应的增大。

然后分析了w对算法的影响。w调节参数，取值范围为［0，1］。w越小，对被选节点能量要求越低，那么符合条件的备选节点数量也就越多，反之亦然。为确定w对算法的影响，采用前述M=100 m仿真场景，令w从0按步长0.05增加到1时，记录其第一个节点死亡的平均时间（轮数）的变化，如图12。

图12 第一个节点死亡时间随参数w变化图

从图中可知，w从0增加到0.2的过程中，第一个节点死亡的平均时间逐渐延迟，这是由于算法对簇头或父节点具有一定的能量要求，过低能量的节点担任簇头或父节点会快速死亡，增加网络重组频率；随着w从0.2继续增大，越来越多的节点达不到该能量阈值，使得一些能量较高但位置不合理的节点被选为簇头或下一跳节点，增加了节点间的通信距离，从而影响了网络生命周期，所以0.2为在该应用场景条件下的最优值。

4 结束语

文中通过对分簇路由和链式路由的优、缺点进行分析，提出一种基于半径递增有向成簇的无线传感器网络路由算法。算法按照“向基站方向成链，链中尽量成簇”的基本思路，生成一种簇、链、树相结合的混合路由结构。实验证明，新算法能够有效优化路由结构，在能量效率和均衡性能两个方面更具优势，能够将网络生命周期提高9-17%，且在传感器节点高密度部署的无线传感器网络中表现更优。

［1］Akvildiz I F，Su W，Sankarasubramaniam Y，et al.A Survey on Se⁃nor Networks［J］.IEEE Communications Magazine，2002，40（8）：102-114.

［2］倪文亚，刘庆威，刘漫丹.基于能量和距离的无线传感器网络路由协议［J］.2015，41（1）：84-88.

［3］靳淑娟.无线传感器网络中的能量均衡路由协议研究［D］.大连：大连理工大学，2009.

［4］王汝传，孙力娟，黄海平，等.无线传感器网络中间件技术［M］.北京：科学出版社，2011.

［5］Heinzelman W，Handrakasan A，Alakrishnan H.Energy-Efficient Communication Protocol for Wireless Micro Sensor Networks［C］//Proceedings of the Hawaii Internationnal Conference on System Sciences，LosAlamitos，CA，USA：IEEE Computer Society，2000：3005-3014.

［6］Lindsey S，Raghavendra C.PEGASIS：Power Efficient Gathering in Sensor Information Systems［C］//Proceedings of the IEEE Aero⁃space Conference，Vol.3，May 2002.1125-1130.

［7］Ossama Y，Sonia F.HEED：A Hybird，Energy-Efficient，Distribut⁃ed Clustering Approach for Ad Hoc Sensor Networks［J］.IEEE Transactions on Mobile Computing，2004，3（4）：366-379.

［8］Manjeshwar A，Agrawal D P.TEEN：A Routing Protocol for En⁃hanced Efficiency in Wireless Sensor Networks［C］//Proceedings of the15th International Parallel and Distributed Processing Sym⁃posium（IPDPS），San Francisco，2001：2009-2015.

［9］李成法，陈贵海，叶懋，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007，30（1）：27-36.

［10］刘铁流，巫永群.基于能量优化的无线传感器网络分簇路由算法研究［J］.传感技术学报，2011，24（5）：764-770.

［11］严英，郭丽，许建真.一种基于LEACH与PEGASIS协议的分层成链优化路由算法［J］.传感技术学报，2011，24（9）：1311-1316.

［12］刘东江，贾卓生.基于分簇的无线传感器网络路由协议的研究［J］.计算机学报，2012，39（10）：23-38.

［13］史久根，胡小博.高效节能的无线传感器网络数据收集协议［J］.电子测量与仪器学报，2012（5）：437-445.

［14］Heinzelman W B，Chandrakasan A，Balakrishman H.An Applica⁃tion-Specific Protocol Architecture for Wireless Microsensor Net⁃works［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

［15］Soro S，Einzelman W B.Prolonging the Lifetime of Wireless Sen⁃sors Networks Via Unequal Clustering［J］.Proc of the 19th IEEE International on Parallel and Distributed Processing Symposium.San Francisco：IEEE Computer Society Press，2005：236-240.

［16］张德干，张晓丹，李光.无线传感与路由技术［M］.北京：科学出版社，2013.

［17］周则顺，李腊元，许毅，等.无线传感器网络中能量有效分簇路由算法［J］.武汉理工大学学报，2011，35（6）：1157-1160.

［18］韩万强，刘云.WSN中基于分簇的路由改进协议［J］.计算机工程，2012，38（5）：105-113.