分布式能量高效的WSN非均匀分簇路由多跳算法

吴玉成，谢 璐

(1.重庆大学通信工程学院，重庆400030;2.国家保密科技测评中心，北京100044)

无线传感器网络［1］(wireless sensor networks，WSN)通过大量部署在监测区域内的传感器节点，以多跳的无线通信方式，将采集的感知信息汇聚于sink节点，传输给终端用户.因此sink附近区域的节点将承担大量数据转发，其能量消耗水平高于其他区域而被称为“热区”，热区内的节点过早消耗完自己的能量死亡导致网络失效称为能量空洞［1］现象.

当前避免能量空洞的方法主要是最大限度地均衡网络负载［2］，许多文献从不同方面采取应对策略，例如:节点初始能量不均匀配置［3］;控制节点功率［4］;节点非均匀部署［5］，以上策略可以使“热区”能量充足，但对传感器节点要求较高，需特定部署，不易操作.文献［6］采用动态sink;文献［7］通过部署多个sink，但是改变sink的位置或增加其数量都需耗费大量成本.为此许多学者提出采用灵活高效易实现的分簇路由策略来均衡网络负载，但以LEACH［8］为代表的均匀分簇路由协议无法解决“热区”问题.S.Soro等［9］首次提出采用非均匀分簇的思想来克服“热区”问题，但所提协议簇首需事先设计，网络扩展性较差.文献［8］中提出经典的非均匀分簇路由协议EEUC，候选簇首通过非均匀的竞争范围构造大小不等的簇来缓解“热区”问题，随后在此基础上对簇间路由进行改进提出UCR［10］，以节约中继节点的能量.但在EEUC和UCR中，节点部署及候选簇首选择的随机性，以及仅局部比较节点剩余能量来选择最终簇首无法从整体上协调全网的能量消耗来避免能量空洞;所采取的就近入簇和固定路由方式也不利于均衡簇间能量消耗.

文中提出能量空洞避免的分布式能量高效的非均匀分簇多跳路由算法.该算法基于平衡全网能量选择出的候选簇首通过自适应校正竞争半径进行非均匀分簇;节点根据基于能量和距离的能耗函数选择最佳簇加入;簇首采用动态路由与sink实现高效数据传输.

1 网络模型及能量消耗模型

1.1 网络模型

文中对网络模型做如下假设:

1)N个传感器节点随机部署在二维平面观测区域上，sink节点位于观测区外，网络一经部署不再移动.

2)所有节点同构，具备数据融合、自适应功率控制等功能，且节点ID号唯一但位置未知.文中用si表示第i个节点，i为节点的ID.

3)网络链路是对称的.

1.2 能量消耗模型

文中采用与文献［10］相同的无线通信能量消耗模型.节点发送kbit数据到距离为d处所消耗的能量由发射电路损耗和功率放大损耗两部分组成，即:

式中:Eelec为发射电路损耗的能量;当传输距离小于阈值d0时，功率放大损耗采用自由空间模型;当传输距离大于等于阈值d0时，采用多路径衰减模型;εfs，εmp分别为这2种模型中功率放大所需的能量.

传感器节点接收kbit数据所消耗的能量为

数据融合也消耗一定的能量，用EDF表示融合1 bit数据消耗的能量.

2 能量高效的非均匀分簇路由算法

文中提出的基于全网平均能量和节点位置的候选簇首选择算法，使得能耗水平低，距离sink近的节点优先成为簇头，有效地平衡了全网能量.节点加入哪个簇，以及簇间通信路由方式也是平衡全网能量的关键因素，为此文中提出了基于能量和距离的能耗函数入簇机制和动态路由.

网络运行以“轮”为单位，每一轮包括网络建立阶段和数据传输阶段.其中网络建立阶段又分为3个时间段:T1为候选簇首产生阶段;T2为最终簇首选择阶段;T3为成簇阶段.数据传输阶段包括簇内数据传输阶段和簇间数据传输阶段.

2.1 网络建立阶段

在网络建立初始化阶段，sink以特定的发送功率向网络广播信号，每个传感器节点接收此信号并根据其强度计算自己到sink的近似距离.随后，每个传感器节点以rhop为半径广播信号以统计自己一跳范围内的邻居节点数目

2.1.1 候选簇首产生阶段T1

由于节点部署的随机性，随机竞选候选簇首的方式可能造成处于网络边缘的节点竞选成功，而能量高的节点反而竞选失败，这无疑不利于平衡全网能量进而影响网络寿命.文中算法引用位置因子和平均能量因子来平衡全网能量，使得离汇聚点越近，剩余能量占全网平均能量比重越大的节点成为候选簇首的概率越大.每个节点根据式(3)计算自己成为候选簇首的概率Psi，若节点si产生的随机数μ＜Psi，μ∈(0，1)，则成为候选簇首，否则进入睡眠状态以节省能量.计算式如下:

成为候选簇首的节点其竞争半径计算式为

式中:dmax和dmin分别表示网络中的节点到sink距离的最大值和最小值为si的初始能量;Negsi为si一跳范围内的邻居节点数目;Rmax为候选簇首竞争半径的最大值，文中由文献［11］根据MEC(minimum energy consumption)，将其取值为c2，c3都是处于(0，1)的常数，其最优取值由试验仿真得出.由式(4)可知网络运行过程中，候选簇首折中考虑簇内负担和自身能量消耗自适应地调节竞争半径的大小.

2.1.2 最终簇首选择阶段T2

每个候选簇首si根据式(5)设定其等待时间Tsi参与最终簇首的竞选，等待时间一到则成为最终簇首并以为半径广播竞选成功消息，若在其等待时间到前收到其他候选簇首的竞选成功消息，则退出竞选进入睡眠状态.计算式为

式中:Crandom是处于(0.9，1)的随机数，该参数的设置是为了避免多个候选簇首在同一时间广播竞选成功消息造成信息碰撞;α是处于(0，1)的常数.文中最终簇首的选择采用定时器竞争机制，综合考虑节点的剩余能量和邻居节点数，避免出现无法覆盖整个网络，造成网络失衡的情况.

2.1.3 成簇阶段T3

T2阶段结束后，所有非簇首节点从睡眠状态唤醒选择簇加入.节点加入哪个簇关系到平衡当前簇头地区的能量消耗.现有分簇路由算法几乎都采取就近入簇，可能造成离sink近的簇规模反而比离sink远的簇规模大，导致处于“热区”的簇首簇内负担过重，不利于平衡全网能量消耗.为此文中提出基于能量和距离的能耗函数入簇机制，使得节点会尽量选择与簇首距离近，簇首剩余能量多，且簇规模大的簇(离 sink远的簇)加入，平衡了簇内和簇间负载.

式中:1≤i≤CH，CH为簇首数目;1≤j≤CM，CM为非簇首节点数目;d(i，j)表示节点sj与簇首si之间的物理距离;β是处于(0，1)的权重常数.

2.2 数据传输阶段

数据传输阶段包括簇内数据传输阶段和簇间数据传输阶段.其中簇内数据传输时，各成员节点采取TDMA方式，在各自分配的时间内将其传感数据传输给簇首，簇首接收完所有数据后进行数据融合处理，压缩成一个数据包后再进行簇间数据传输.簇间数据传输采用多跳动态路由的方式.路由构建时，所有非簇首节点进入睡眠状态.每个簇首以相同概率广播其状态信息，若簇首si到sink的距离dsi小于阈值TD_MAX，则直接与sink通信，否则在自己的路由转发集合中随机动态选取一个簇首作为转发节点多跳传送给汇聚点，且

若簇首si的Rsirouter为空，则与sink直接通信.采取动态路由方式虽然不及每次选取最优的转发节点，但可避免固定的转发路径导致转发节点因能量消耗过快而死亡，均衡了中继簇首节点的能量消耗，进而均衡了全网能量消耗.

3 仿真及结果分析

3.1 试验参数设置

采用Matlab对文中算法和UCR算法进行仿真分析比较.文中算法所用参数因受网络规模，节点密度等因素的影响，通过上千次随机试验获取其最优值如下:P=0.4，c1=0.25，c2=0.3，c3=0.2，α =(与 UCR 选取一样).UCR算法的参数是基于文献［8］选取的最优值，试验中其他参数设置如下:网络覆盖区域，(0，0)～ (200，200)，单位为 m;汇聚点位置，(250 m，100 m);节点总数N，400;节点初始能量，1 J;Eelec，50 nJ·bit-1;εfs，10 pJ·(bit·m2)-1;εmp，0.001 3 pJ·(bit·m2)-1;d0，87 m;EDA，5 nJ·(bit·signal)-1;数据包大小，4 000 bit.

3.2 仿真结果分析

文中所有仿真结果是1 000次随机试验结果的平均值.图1和2分别比较各轮候选簇首数目和随机抽取60轮簇首消耗能量的方差.

图1 候选簇首数目比较

由图1可知，文中算法中各轮候选簇首的数目约为UCR的一半且无需维护邻簇首集合，节约了大量控制开销;最优候选簇首呈非均匀分布，离汇聚点越近分布越多，有利于最终簇首的竞选和分布.

图2 簇首消耗能量的方差比较

由图2可知，文中算法簇首消耗能量的方差比UCR低，且波动不大较稳定，相比UCR更好地均衡了簇首能量消耗.图3是随机抽取20轮，各轮簇首消耗的能量之和比较.

图3 簇首消耗的能量之和比较

由图3可见，文中算法每轮簇首消耗的能量之和小于UCR，所以文中算法比UCR更能实现能量高效.图4是网络中存活的节点数随时间变化的情况比较.

图4 网络存活节点数比较

由图4可见，文中算法与UCR算法第1个节点死亡的时间分别为1 251轮，1 670轮，即文中算法的网络生命周期较UCR提高了34%;且文中算法第1个节点死亡与全网节点死亡的时间跨度比UCR小，即网络能耗均衡性较好.这是由于文中算法选取候选簇首基于平衡全网剩余能量的考虑;所采取的入簇机制和动态路由降低处于“热区”的簇首能量消耗速度.图5比较网络运行到第600轮和第1 000轮时热区内节点的剩余能量.

图5 “热区”内节点的剩余能量比较

文中定义与sink距离为TD_MAX的区域为热区［8］.由图5可见，文中算法中热区内节点剩余能量大于UCR热区内节点剩余能量，并且随着网络的运行，剩余能量差距越大，说明文中算法缓解“热区”问题的效果比 UCR好，能有效避免能量空洞.

4 结论

针对无线传感器网络中存在的能量空洞问题，在已有分簇路由协议的基础上提出一种分布式能量高效的WSN非均匀分簇路由多跳算法，结论如下:

1)算法在选择候选簇首时引入位置因子和平均能量因子，无需维护邻簇首集合，节约了大量控制开销，均衡了全网能耗.

2)文中算法簇首消耗能量的方差比UCR算法低，且波动不大较稳定，相比UCR算法更好地均衡了簇首能量消耗.

3)文中算法能有效地避免能量空洞，与UCR算法相比，延长了网络生命周期，缓解“热区”问题的效果更为显著.

References)

［1］Li Changle，Zhang Hanxiao，Hao Binnin，et al.A survey on routing protocols for large-scale wireless sensor networks［J］.Sensors，2011，11(4):3498-3526.

［2］Anastasi G，Conti M，Di Francesco M，et al.Energy conservation in wireless sensor networks:a survey［J］.Ad Hoc Networks，2009，7(3):537-568.

［3］Chen Changwen，Wang Yu.Chain-type wireless sensor network for monitoring long range infrastructures:architecture and protocols［J］.International Journal of Distributed Sensor Networks，2008，4(4):287-314.

［4］Zheng Liqiang，Wang Wensi，Mathewson Alan，et al.An adaptive transmission power control method for wireless sensor networks［C］∥Proceedings of IET Signal and Systems Conference.Cork，Ireland:Institution of Engineering and Technology，2010:261-265.

［5］Wu Xiaobing，Chen Guihai，Das Sajal K.Avoiding energy holes in wireless sensor networks with nonuniform node distribution［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19(5):710-720.

［6］Yun Y S，Xia Y.Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applications［J］.IEEE Transactions on Mobile Computing，2010，9(9):1308-1318.

［7］Marta M，Cardei M.Improved sensor network lifetime with multiple mobile sinks［J］.Pervasive and Mobile Computing，2009，5(5):542-555.

［8］李成法，陈贵海，叶 懋，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007，30(1):27-36.Li Chengfa，Chen Guihai，Ye Mao，et al.An uneven cluster-based routing protocol for wireless sensor networks［J］.Chinese Journal of Computers，2007，30(1):27-36.(in Chinese)

［9］Soro S，Heinzelman W B.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］∥Proceedings of19th IEEE International Conference on Parallel and Distributed Processing Symposium.Denver:IEEE Computer Society，doi:10.1109/IPDPS.2005.365.

［10］Chen Guihai，Li Chengfa，Ye Mao，et al.An unequal cluster-based routing protocol in wireless sensor networks［J］.Wireless Networks，2009，15(2):193-207.

［11］Yuan Huiyong，Liu Yongyi，Yu Jianping.A new energy-efficient unequal clustering algorithm for wireless sensor networks［C］∥Proceedings of2011IEEE International Conference on Computer Science and Automation Engineering.Shanghai:IEEE Computer Society，2011:431-434.