一种能耗均衡的无线传感器网络分簇路由算法

张诗悦，吴建德，2，王晓东，2，范玉刚，2，冷婷婷

(1.昆明理工大学a.信息工程与自动化学院;b.土木工程学院，昆明 650500;2.云南省矿物管道输送工程技术研究中心，昆明 650500)

1 概述

路由技术是无线传感器网络研究的热点，也是核心技术之一。由于节点多采用能量有限的电池进行供电，如何最大限度地平衡能耗以延长网络生命周期就成为了研究的重点。分簇式路由协议由于实际应用效果优于平面型路由协议，已经逐渐成为了研究的热点方向，其中，LEACH［1］就是最典型的分簇式路由协议。然而，LEACH 协议存在簇头随机选取、簇头分布不均以及簇头同基站单跳通信、能耗过大容易死亡等缺点，针对这些问题，目前已经提出了很多改进的路由算法。文献［2］分析指出，在单跳情况下，节点同基站距离越远其通信能耗越大，越容易死亡［3］;在多跳情况下，同基站距离越近其能耗越大，越容易失效［4］。为此，EECS 算法［5］让距离基站较远的簇的尺寸较大，距离基站较近的簇的尺寸较小，以此平衡簇头能耗。EEUC 算法［6］在非均匀分簇的基础上，考虑节点剩余能量和同基站的距离来选择中继节点进行多跳路由，同时计算非均匀分簇的竞争半径，距离基站远的簇的竞争半径较大，这一点类似EECS 算法。ACOUC 算法［7］在非均匀分簇的基础上加入基于定向的蚁群优化算法优化多跳路径，在首轮节点全部参与竞选簇头、后续轮内自行更换的方法来节省能耗。CEB-UC 算法［8］将网络分成不同的区域，使距离基站近的分区内簇的数量多，而簇内节点数目较少，以此平衡网络开销。此外，研究者利用将已有的优化算法加入到路由算法的设计中，如遗传算法［9］、贝叶斯游戏［10］等，从而达到提高网络性能的目的。本文则提出一种基于能量和距离因子的非均匀分簇的能耗均衡路由算法(ECRED)。

2 网络模型与能耗分析

2.1 网络模型

本文所采用的模型设定如下:(1)基站位于监控区域外部，位置固定，能量无限且只有一个;(2)所有节点同构且具有唯一ID，位置一旦固定则不再移动;(3)节点能量有限且初始能量相同;(4)节点发射功率可调;(5)无线链路是对称的;(6)节点均具有相应的计算处理等能力。

2.2 能耗模型

文献［11］研究表明:进行无线电收发时所消耗的电量要远大于节点休眠时消耗的电量。每传输1 bit数据所消耗的电量可以执行数千条CPU 指令，且消耗的时间也更少［12］。假设发射电路能耗为Eelec(nJ/bit)，计算能耗为Eda(nJ/bit)，数据包长度为l(bit)，消息长度k(bit)，d0为选择空间模型的划分阈值，小于d0选择自由空间模型，功率放大能耗为Efs;大于d0选择多路径衰减模型，功率放大能耗为Emp。若忽略空闲和休眠的能耗，则簇成员数为N 的单簇建簇所消耗的能量为Eone，计算公式如下:

簇成员数为N 的簇在计算分配时隙所消耗的能量为Est，计算公式如下:

3 ECRED 算法

3.1 最优簇头数

在分簇路由协议中，簇头所占比例p 的确定对于网络的能耗有很大的影响［13］，很多学者针对最优的p 值进行了研究［14］，多数文献倾向于取该值为0.05，即100 个节点中选择5 个节点作为簇头。采用均匀分簇即每个簇节点数目相同，非均匀分簇则簇内节点数目不均等。本文根据节点到基站距离的远近来进行非均匀分簇，第i 个簇的簇内节点总数Nopt(CHi)的计算公式如下:

其中，ceil 是向上取整函数;Dis是第i 个簇头到基站的距离;Dmin是所有节点到基站距离的最小值;Dmax是所有节点到基站距离的最大值;p 是簇头占节点总数的百分比。本文设定单簇最少节点数为8，小于8则解散该簇。

3.2 簇头选择

簇头选择过程基本同LEACH 协议一样，本算法稍作改进。采用备择簇头更替策略，当簇头能量小于最低能量阈值，则转交簇头权限给备择簇头，减少建簇次数。首先基站广播竞选信息，收到消息的节点随机产生一个(0，1)随机数，如果该数大于阈值T(n)则标记为备择簇头，等待时间T 后广播当选信息，标记为簇头;如果在等待时间T 内收到其他节点的当选信息，则加入与其通信代价最小的簇头所在的簇。改进后的阈值公式为:

其中，r 为当前的轮数;Ecur为节点剩余能量;dis为节点到基站距离;G 为在1/p 轮中未当选为簇头的节点集合。改进后的公式使得当节点的剩余能量Ecur越大、节点到基站的距离dis越小，阈值T(n)越大，从而该节点当选为簇头的几率越大，反之当选为簇头的几率越小。

3.3 簇的建立和簇间路由

由于单簇的规模有限，簇成员节点同簇头以单跳方式通信即可，为避免信号冲突，簇内通信采用TDMA 机制。由于部分簇头可能距离基站较远，而通信能耗随距离的增加呈几何增长，因此簇间路由采用多跳方式，簇间通信采用CSMA 机制。节点在分配的时隙之内发送数据，在其他时隙则进入休眠状态，从而降低能耗。

由于部分节点距离基站较近，单跳同基站通信的能耗要小于通过簇头转发的能耗，因此设定单跳距离阈值，当节点同基站的距离小于该单跳阈值时直接发送数据到基站。这样可以节约网络能耗，减少“热点”压力。

簇头需要知道其通信范围内一跳邻居簇头的相关信息，选择中继权值最大的簇头作为下一跳中继簇头。节点i 同一跳邻居节点j 的中继权值的计算公式如下:

其中，Ecur_j表示簇头j 的剩余能量;di，j表示簇头i 到簇头j 的距离;dis_j表示簇头j 到基站的距离;簇头i从所有一跳邻居节点里面选择中继权值最大的作为中继簇头，直到所有的簇头都加入到路由链当中为止。如果簇头i 在通信范围内没有找到其他簇头，则提高发射功率广播，并重新计算中继权值。

4 算法仿真与性能验证

4.1 仿真参数设定

为验证ECRED 算法的性能，将EECS 和ECRED算法进行仿真对比。仿真参数如下:忽略信道通信干扰和信号碰撞等因素，将100 个节点随机部署到100 ×100 的监控区域当中，基站坐标(50，175)，数据包长度4 000 bit，距离阈值d0=877 058 m，发送/接收电路能耗Eelec=50 nJ/bit，数据融合能耗Eda=5 nJ/bit/signal。

4.2 仿真结果分析

4.2.1 对网络密度的适应性

当初始能量Einitial=0.5 J，节点总数N=100 时，ECRED 算法和EECS 算法的网络生命曲线如图1所示;当Einitial=0.5 J，N=200 时，2 种算法的生命曲线如图2 所示。从图中可以看出，相对EECS 算法，ECRED 算法的网络生命周期都有所延长，当N=100时，网络寿命延长了8.4%，而当N=200 时，网络寿命延长了8.0%，由此可见，ECRED 算法对网络密度具有很好的适应性。

图3 是2 种算法的网络能耗对比，可以看出，开始时两者能耗差别极小，但随着轮数的增加，ECRED算法的网络能耗相对EECS 算法更小，通过对比可以发现，网络密度对网络能耗稍有影响。

图1 Einitial=0.5 J，N=100 时的网络生命曲线

图2 Einitial=0.5 J，N=200 时的网络生命曲线

图3 Einitial=0.5 J，N=100 时的网络能耗

4.2.2 对初始能量的适应性

为验证ECRED 算法对网络密度的适应性，本文将初始能量Einitial作为自变量，分别取0.5 J 和1 J，节点数N=100，其他参数同上，得到生命曲线和网络能耗如图4 和图5 所示。

图4 Einitial=1 J，N=100 时的生命曲线

图5 Einitial=1 J，N=100 时的网络能耗

对比图1 和图4 可以看出，初始能量越大，网络性能越好。当Einitial=0.5 J 时，ECRED 算法的生命周期相对于EECS 算法提高了7.4%;而当Einitial=1 J时，性能提高了11.9%。可见，ECRED 算法的性能和初始能量成正比，且性能要相对优于EECS算法。

5 结束语

本文提出一种基于能量和距离因子的非均匀分簇的能耗均衡路由算法(ECRED)。该算法采用能量和距离双因子确定簇头，在广播时增加等待时间以便接收其他节点建簇信息，增加备择簇头，减少建簇次数，降低网络能耗;同时采用单跳和多跳路由方法降低“热区”节点能耗。文中给出了非均匀分簇的簇内节点数计算公式，使得距离基站近的簇规模相对较小，而距离基站较远的簇规模较大，同时避免了极小簇的存在。通过仿真实验表明，ECRED 算法可以有效地平衡网络能耗，延长网络寿命。

虽然本文提出的ECRED 算法在平衡网络能耗上有一定的优势，但仍有一些问题需要深入研究。未来的研究主要包括:(1)在节约能耗的基础上增加对分簇路由算法安全性能的考虑，设计一种安全的路由算法;(2)对簇头数目进行优化，进一步减少能耗损失。

［1］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy Efficient Communication Protocol for Wireless Sensor Networks［C］//Proceedings of the 33rd Hawaii International Conference on System Science.Hawaii，USA:［s.n.］，2000:3005-3014.

［2］Perillo M，Zhao Cheng，Heinzelman W.On the Problem of Unbalanced Load Distribution in Wireless Sensor Networks［C］//Proceedings of IEEE GLOBECOM'04.Dallas，USA:IEEE Press，2004:74-79.

［3］Soro S，Heinzelman W.Prolonging the Lifetime of Wireless Sensor Network via Unequal Clustering［C］//Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium.Denver，USA:IEEE Press，2005:365.

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

［5］Ye Mao，Li Chengfa，Chen Gguihai，et al.An Energy Efficient Clustering Scheme in Wireless Sensor Networks［C］//Proceedings of IEEE International Performance Computing and Communications Conference.Phoenix，USA:IEEE Press，2005:535-540.

［6］Li Chengfa，Ye Mao，Chen Guihai，et al.An Energyefficient Unequal Clustering Mechanism for Wireless Sensor Networks ［C］//Proceedings of 2005 IEEE International Conference on Mobile Ad-hoc and Sensor Systems.Washington D.C.，USA:IEEE Press，2005:597-604.

［7］Zhang Rongbo，Cao Jianfu.Uneven Clustering Routing Algorithm for Wireless Sensor Networks Based on Ant Colony Optimization［J］.Journal of Xi'an Jiaotong University，2010，44(6):33-38.

［8］Wang Yi，Zhang Deyun，Liang Taotao.Cell Energy Balanced Uneven Clustering Hierarchy Scheme for Wireless Sensor Networks［J］.Journal of Xi'an Jiaotong University，2008，42(4):389-394.

［9］Noyouzi A，Babanir F S，Zaim A H.A New Clustering Protocol for Wireless Sensor Networks Using Genetic Algorithm Approach［J］.Wireless Sensor Network，2011，3(11)，362-370.

［10］Zheng Gengzhong，Liu Sanyang，Qi Xiaogang.Clustering Routing Algorithm of Wireless Sensor Networks Based on Bayesian Game［J］.Journal of Systems Engineering and Electronics，2012，23(1):154-159.

［11］Larios D F，Barbancho J，Rodríguez G，et al.Energy Efficient Wireless Sensor Network Communications Based on Computational Intelligent Data Fusion for Environmental Monitoring［J］.IET Communications，2012，6(14):2189-2197.

［12］Min R，Bhardwaj M，Cho S H，et al.Energy-Centric Enabling Technologies for Wireless Sensor Networks［J］.IEEE Wireless Communications，2002，9 (4):28-39.

［13］Heinzelman W，Chandrakasan A，Balakrishnan H.An Application-specific Protocol Architecture for Wireless Sensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［14］Bandyopadhyay S，Coyle E J.An Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks［C］//Proceedings of IEEE INFOCOM'03.San Francisco，USA:IEEE Computer Society，2003:1713-1723.