能量优化的非均匀分簇路由的改进算法*

黄 鹏，封志宏，童宇行

0 引 言

无线传感器网络通常是由大量随机部署在复杂环境中的传感器节点和用于收集数据的基站（Sink）节点组成，并通过自组网的方式采集数据。传感器节点能量采取电池供电的方式，在复杂环境中充电或者更换电池无法实现，因此研究热门之一就是设计出一种能量高效的WSN路由算法[1-2]。

最早提出的LEACH[3]路由采用分簇协议，有效延长了整个网络的存活时间。但是，由于簇头节点到基站的通信采用单跳的方式进行，会使距离Sink节点较远的簇头消耗过多的能量。从一些仿真结果中可以看出，通过多跳方式完成簇头到Sink节点间的数据传输更能节省能耗[4]。然而，近基站的簇头需要中转其他簇的数据，会造成近Sink节点的簇消耗过多能量，致使能耗不均衡。同时，在推选簇头的过程中，没有考虑有些节点当前能量不足而再次当选为簇头的情况，从而加快了部分节点的失效，使邻居节点的能耗加快，呈现出大片节点失效的问题。文献[5]提出了一种能量高效的算法UCPO，解决了LEACH算法中随机得到簇头节点以及簇头节点直接与Sink节点通信的问题，有效降低了网络能耗。文献[6]提出了分布式分簇路由算法DEEC，采用时间广播机制选举簇头节点，采用权值函数完成多跳路径选择，最终均衡了网络能耗。文献[7]提出了EBFA协议，应用社会福利函数完成预估，某种程度上减少了WSN中的“热区”。文献[8]提出了LEACH-GPF算法，通过应用遗传算法并对结合概率准则，更好地平衡了网络能耗。文献[9]提出的EEUC算法通过非均匀分簇的方式，有效均衡了WSN网络的消耗，但其簇头选择过程中应用随机函数与门限值确定，所选簇头并不一定最佳。文献[10]则在簇头路由中引入蚁群算法，能够延长WSN的生命周期，但蚁群算法只能保证部分路由路径的效果最优。文献[11]通过构建最小生成树完成多跳路由，但构建过程中只考虑了多跳消耗和簇头的当前能量值。

分析分簇协议中可能出现的问题，提出了能耗优化的WSN分簇算法。算法将WSN划分为不均匀的簇，簇头选择阶段引入簇首等待时间，计算过程中考虑节点当前的能量、节点到Sink节点的距离、邻居表中的数目等因素，通过单跳的方式完成簇内数据的收集；在簇间多跳路由选择阶段，利用簇头剩余能量、距离、簇内剩余能量均值等影响因子选择中继节点，构建数据传输路由树，从而进行数据转发。该协议能够有效均衡节点能耗，延长WSN网络的生命周期。

1 相关模型

1.1 网络模型

首先，假设WSN具有以下性质：

①检测区域内随机部署了N个节点，之后这些节点在网络中的相对位置不会变化，Sink节点能量变化忽略不计且其在网络中的相对位置不再变化；

②每个节点的起始能量一定并配有唯一的身份编号ID，发射功率可根据网络要求进行变化；

③通过收到的信号强弱RSSI来估算发送节点到接收节点的距离；

④Sink节点可以覆盖其余所有节点，链路对称，节点可以知道当前的能量，并具有一定的数据融合能力。

1.2 能耗模型

该能耗优化的非均匀分簇路由协议采用如图1所示的无线通信能耗模型[12]。

图1 本路由协议的无线通信能耗模型

该模型发送数据时的能耗公式如下：

式中：k表示收发数据的长度，单位bit；Eelec为节点发送/接收每比特数据消耗的能量，d为该数据传输的距离；εamp为多径衰落模式下传递每比特数据消耗的能量；εfs为自由空间模式下传递每比特数据消耗的能量；d0的计算公式为是划分空间模型的临界值；当发送者与接收者的距离d小于d0时，采用自由空间的计算公式；当发送者与接收者的距离d大于等于d0时，采用多径衰落的计算公式。

接收m bit数据节点消耗的能量为：

所以，簇头的能耗为接收簇内其余节点采集的数据能耗、将采集到的数据融合后发出去的能耗以及做为其他簇的中继节点的能耗。综合式（1）、式（2）可以得到：

由式（3）可知，簇头的能量消耗是通过簇内其余节点的数量、收集到的数据以及下一跳距离d决定的，所以选择更优的簇头和选择最佳的传输路由可以减少能耗，均衡网络负载。

2 能耗优化的非均匀分簇路由算法

本算法采用LEACH协议中“轮”的方式进行。每“轮”根据簇内节点间距离、簇首的邻居数目以及节点的当前能量计算非均匀成簇的竞争半径，簇首的选取利用时间等待机制，簇中采用TDMA的方式传递，簇间的路由根据构造的路由树传输到基站节点。

2.1 簇首选择算法

2.1.1 非均匀竞争半径的计算

定义1 在改进的算法中给定除Sink节点外其余节点的最大通信半径Rmax，对于WSN中的节点i，其邻居节点定义如下：

i的邻居节点的数目为：

EEUC算法中，在构建节点竞争半径时只考虑了本簇首到Sink节点的距离，如式（6）所示。改进算法通过文献[13]中对非均匀竞争半径的计算进行完善，构建的竞争半径考虑了簇首到Sink节点的d、邻居表中的数目、每轮能耗的平均值以及节点当前的能量等因素。邻居节点的数目已经由上述定义给出，每轮能耗的平均值由式（7）给出，所以非均匀成簇的竞争半径计算公式由式（8）得到。

其 中 u1、u2、u3、u4为 参 数 控 制 因 子， 且u1+u2+u3+u4=1；dmin表示候选的簇首节点到Sink节点的最小d；dmax表示候选的簇首节点到Sink节点的最大d，r表示当前的轮数，Nnbc为候选簇首的邻居个数。可见，成簇规模与候选簇首的邻居个数、每轮平均能耗成反比，与该簇首当前能量、该簇首到邻居节点的d成正比例。u3、u4两个参数可以对剩余能量过多而消耗速率快的情况进行权衡，以决定最终的成簇大小。

2.1.2 簇首的竞选

为后续流程的描述，对算法的概念说明如下：

①竞选半径。节点竞选非均匀成簇的半径，具体如式（8）所示。

②邻居表。邻居节点根据定义1得到每个节点的邻居表来保存节点信息，具体如表1所示。

表1 节点邻居表的内容

③剩余能量比PEi。PEi表示节点si的所有邻居节点的当前平均当前能量与该节点的当前能量的比。PEi越小，说明节点si的当前的能量相比邻居节点的当前能量更多。

④平均距离davg。依据邻居表中的内容得到候选簇头到其邻居节点的距离的平均值。

⑤簇首竞争等待时间t。从节点收到Sink节点通知簇首竞争到本节点发出簇首竞争消息的时间。

其中：α为[0.9，1]中的任意值，T为指定的簇首竞争时间，β、γ为距离调节因子。因此可知，节点剩余能量低、距离基站远和平均距离增大，都会使簇首竞争的持续时间变长。

2.1.3 簇首的竞选流程

在WSN分簇路由协议算法中，簇首的能量和能耗影响着整个网络的性能。当采用簇间多跳路由时，簇首不仅要对其所在簇的数据进行接收和融合，还要做为中继节点参与其他簇的信息传递。本文以非均匀分簇算法为基础，改进簇头选举公式。每轮开始时，WSN中所有的节点都参与到簇头选举的竞争中，之后应用时序的方式完成最终簇首的确定。

簇头选举的算法流程：

（1）WSN中的所有的节点以Rmax为半径传递Ne_MSG消息，接收到该内容的其他节点加入到此节点的邻居节点表中。

（2）Sink节点向全网广播一个分簇信号Par_CLU，通过收到的信号强弱RSSI，每个节点估算Sink节点到节点的距离，并根据此时邻居节点表中的信息，结合式（8）计算各自的竞选半径。

（3）各节点在其半径Rc/2的范围内发送竞选的消息，其内容主要有节点的ID和当前的能量。

（4）各节点收到来自其他节点的竞选消息，根据收到的信号强度RSSI计算节点间的距离，并更新此时的邻居节点表。

（5）各节点根据此时邻居节点表中的信息，结合式（9）、式（10）计算PEi、davg，从而得到式（11）的各自簇首竞争等待的时间。

（6）Sink节点发出同步信号Tim_MSG，以同步各个节点的时间。

（7）各个节点收到时间同步信号后，开始计时并监听其他节点的信息。

（8）如果节点在自身簇首竞争等待时间t到达前并没有收到其余节点的簇首竞争成功的消息Succ_MSG，则该节点发送Succ_MSG消息，并成为成为簇头。

（9）如果节点在自身簇首竞争等待时间t到达前收到了其余节点的竞选成功消息Succ_MSG，则此节点广播Fail_MSG，退出簇头的竞选。

（10）当节点收到其余节点的Fail_MSG后，就把这个节点从邻居节点表中删除。

（11）选举流程结束后，没有成为簇头的节点依据节点表中的信息，选择最近的簇头并加入其中。

（12）分簇结束后，各个簇头以Rmax为半径广播消息，消息包括簇头ID、剩余能量、到基站的距离以及簇内剩余能量均值，并收集其他簇头的消息。

算法完成后，依据邻居表中的信息，整个网络被划分为大小不等的簇，有利于能耗均衡；在得到簇头竞争时间的过程中，通过平衡当前能量、节点到Sink节点的距离以及簇内节点的平均距离等因素得到其值，最终得到综合性能最优的簇头。

2.2 簇间路由的选择与数据传输

首先，簇头节点根据之前的RSSI得到其与Sink节点的距离d，如果d，则通过单跳的方式，该簇头直接与Sink节点进行通信。如果d ＞则此时采用多跳的方式。

中继节点的选择如下。在成簇阶段，簇头存储其通信范围内其余簇的簇头ID、当前能量、到Sink节点的距离和簇内当前能量均值。根据贪婪算法，簇头节点在其邻居簇头节点集合中。然后，根据最小代价函数得到下一跳的中继节点RN。参考文献[14]中代价函数的定义为：

式中，Eave表示簇头节点si所有邻居簇头节点的剩余能量均值；Ere表示簇头节点si当前剩余的能量；Nnbc( j )表示簇头sj中成员节点的数目；Nnei(i)表示簇头si的邻居簇头其簇内节点的均值；表示两节点间的距离；表示节点s距离jSink节点的距离；表示节点s距离Sink节点i的距离；α、β、γ表示加权因子，且α+β+γ=1。因此，cost(RN)=min{cost(i, j)}。当所有簇头节点完成中继节点RN的选择后，开始簇间路由的传输。

当路由规则确定后，节点就可以传输数据。首先，簇内的非簇头节点按照时分多路复用即TDMA方式，把数据传递给簇首节点；簇内节点都在其分配的时隙内工作，其余时间处于休眠状态，以降低能耗；簇头节点接收来自簇内所有节点采集的信息，并对接收信息进行数据融合，然后再选择簇间中继节点将融合后的信息以多跳、单跳相结合的路由方式传递给Sink节点。改进的路由协议采用分布式策略，目的是找到一条最优路径，以减少簇间数据传输所消耗的能量，最终达到均衡网络能耗、延长生命周期的目的。

3 实验仿真

本文通过仿真对改进算法、EEUC协议以及LEACH协议进行比较和模拟。实验参数如表2所示，传感器节点随机分布在检测区域内，忽略簇头节点融合数据的能量，协议中其他参数的取值都是通过多次运行模拟得到的最优值。

表2 实验仿真参数设置

3.1 簇首能耗均衡的分析

簇首能量的消耗是无线传感器网络中能量消耗的最主要部分。随机选取20轮，3种协议的簇首数目相同，对比统计3种协议簇首消耗的能量，结果如图2所示。

实验对比结果显示，本文的路由算法簇头能耗较为均衡、消耗的能量最低，LEACH协议簇头能量消耗波动最大，EEUC协议能耗明显高于改进的协议。究其原因，在于改进的路由协议在簇首选举过程中综合考虑了剩余能量、节点到基站的距离以及簇内节点的平均距离等因素，最大程度地保证了选出的簇首节点最优。同时，在不均匀簇划分过程中综合考虑了簇首到汇聚节点的距离、邻居节点的数目、每轮消耗的平均能量以及节点当前的剩余能量等因素，保证了簇首节点能耗的减少。实验结果表明，改进的路由协议能耗波动最小，有效解决了“热区”问题，降低了簇首负载，簇首能耗更均衡。

3.2 网络生命周期的分析

存活节点的变化情况如图3所示。

图2 簇首节点能耗的均衡性

图3 存活节点变化情况

图3 显示了3种不同的路由协议随着仿真时间的增加，网络中节点存活数量随轮数增长的变化情况。可以看出，由于节点能耗不均，LEACH协议早早出现了死亡节点，且其第一个死亡的节点与最后一个死亡的节点的时间跨度远远大于EEUC和改进协议；EEUC协议优于LEACH协议，但其时间跨度也大于改进的路由协议。时间跨度的大小，表明了整个网络的均衡程度。可见，改进的路由算法有效均衡了网络能耗，解决了“热区”问题，同时改进了WSN内节点的能耗，均衡了簇内网络能耗，其第一个死亡节点和最后一个死亡节点相对于其他两个协议都有所延长，延长了整个网络的寿命。

4 结 语

本文针对“热区”影响网络均衡、降低网络寿命的问题，提出了一种改进的路由协议。改进的路由协议在非均匀分簇半径的选取中，综合考虑了簇首到汇聚节点的距离、邻居节点的数目、每轮消耗的平均能量以及节点当前的剩余能量等因素，更好地控制了簇规模的大小；在簇首选举过程中，引入时间竞争机制，使竞争时间的大小依据剩余能量、节点到基站的距离以及簇内节点的平均距离等因素来确定，使簇头选举过程更加合理，簇头分布更加均匀，更加均衡了整个簇内的能耗；在簇间路由选择阶段，运用单跳、多跳相结合的方式，其中多跳依据代价函数选择下一跳节点；同时，引入阈值控制，保证了能量少的节点不会当选中继节点。仿真结果表明，本文的路由算法很好地解决了网络“热区”问题，均衡了网络能耗，延长了WSN的寿命。

[1] 李亚男,徐夫田,陈学鑫.基于LEACH的WSNs分簇路由优化策略[J].传感技术学报,2014,27(05):670-674.LI Ya-nan,CHEN Fu-tian,CHEN Xue-xin.WSNs Cluster Routing Optimization Strategy Based on LEACH’s[J].Chinese Journal of Sensors and Actuators,2014,27(05):670-674.

[2] 李建洲,王海涛,陶安.一种能耗均衡的WSN分簇路由协议[J].传感技术软件学报,2013,26(03):396-401.LI Jian-zhou,WANG Hai-tao,TAO An.A WSN Clustering Routing Protocol for Energy Consumption Equilibrium[J].Journal of Sensors and Software,2013,26(03):396-401.

[3] Heinzelman W,Chandrakasan A,Balakrishnam H.Energy-Efficient Communication Protocol for Wireless Micro-sensor Networks[C].Proc of the 33rd Conf on System Sciences.Piscataway,2000:3005-3014.

[4] Mhatre V,Rosenberg C.Design Guidelines for Wireless Sensor Networks:Communication,Clustering and Aggregation[J].Ad Hoc Networks,2004,2(01):45-63.

[5] 刘国繁,许多.基于非均匀分簇与路径优化的WSN路由协议[J].计算机工程与科学,2015,37(08):1492-1497.LIU Guo-fan,XU Duo.WSN Routing Protocol Based on Uneven Clustering and Path Optimization[J].Computer Engineering and Science,2015,37(08):1492-1497.

[6] 魏春娟,杨俊杰,张志美.一种分布式能量有效的无线传感器网络协议[J].传感技术学报,2013,26(07):1014-1018.WEI Chun-juan,YANG Jun-jie,ZHANG Zhi-mei.A Distributed Energy Efficient Wireless Sensor Network Protocol[J].Chinese Journal of Sensors and Actuato rs,2013,26(07):1014-1018.

[7] 孙彦景,林昌林,江海峰.一种能量高效的分布式非均匀分簇路由算法[J].传感技术学报,2015,28(08):1994-1200.SUN Yan-jing,LIN Chang-lin,JIANG Hai-feng.A Distributed Uneven Clustering Routing Algorithm with High Energy Efficiency[J].Chinese Journal of Sensors and Actuators,2015,28(08):1994-1200.

[8] 陈海南,刘广聪,吴晓鸽.一种基于遗传算法与概率转发的分簇协议[J].计算机科学,2015,42(03):71-73.CHEN Hai-nan,LIU Guang-cong,WU Xiao-ge.A Clustering Portocol Based on Genetic Algorithm and Probability Forwarding[J].Computer Science,2015,42(03):71-73.

[9] 李成法,陈贵海,叶懋.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报,2007,30(01):27-36.LI Cheng-fa,CHEN Gui-hai,YE Mao.A Wireless Sensor Networks Routing Protocol Based on Uneven Clustering[J].Chinese Journal of Computers,2007,30(01):27-36.

[10] 张荣博,曹建富.利用蚁群优化的非均匀分簇无线传感器网络路由算法[J].西安交通大学学报,2010,44(06):33-38.ZHANG Rong-bo,CAO Jian-fu.An Uneven Distributed Cluster Wireless Sensor Network Routing Algorithm Using Ant Colony Optimization[J].Journal of Xi’an Jiaotong University,2010,44(06):33-38.

[11] 陆晶,马悦,吴晓军.一种基于最小生成树的非均匀分簇路由算法[J].小型微型计算机系统,2012,33(10):33-38.LU Jing,MA Yue,WU Xiao-jun.A Uneven Clustering Routing Algorithm Based on Minimum Spanning Tree[J].Journal of Chinese Mini-Micro Computer Systems,2012,33(10):33-38.

[12] Jangs,Kimhy,Kimnu,et al.Energy-Efficient Clustering Scheme with Concentric Hierarchy[C].2011 IEEE International RF and Micro wave Conference(RFM),2011:79-82.

[13] 王伟.长距离带状无线传感器网络路由协议设计[J].计算机工程,2014,40(03):132-136.WANG Wei.Routing Protocol for Long-Distance Ribbon Wireless Sensor Network[J].Computer Engineering,2014,40(03):132-136.

[14] 尚风军.无线传感器网络的分布式能量有效非均匀成簇算法[J].通信学报,2009(10):34-43.SHANG Feng-jun.The Distributed Energy Efficiency Uneven Algorithm of Wireless Sensor Network[J].Journal on Communications,2009(10):34-43.