一种能量高效的分布式非均匀分簇路由算法*

孙彦景，林昌林，江海峰

(1.中国矿业大学信息与电气工程学院，江苏徐州221116；2.江苏省煤矿电气与自动化工程实验室，江苏徐州221008；3.中国矿业大学计算机科学与技术学院，江苏徐州221116)

一种能量高效的分布式非均匀分簇路由算法*

孙彦景1，2*，林昌林1，江海峰3

(1.中国矿业大学信息与电气工程学院，江苏徐州221116；2.江苏省煤矿电气与自动化工程实验室，江苏徐州221008；3.中国矿业大学计算机科学与技术学院，江苏徐州221116)

针对分布式分簇路由多跳通信方式中出现的“热区”问题，在现有的分布式分簇路由协议的基础上改进，并提出了能量均衡前行路由算法（EBFA）。该算法采用非均匀分簇和簇间多跳转发策略，在多跳转发阶段，引入社会福利函数预先评估数据转发路径上节点间的能量均衡程度，选择能量均衡程度较好的作为转发节点。仿真结果表明：相比于LEACH和EEUC，此算法最大程度上延长了网络的生存周期，较好地均衡了节点间的能量，解决了多跳路由中热区的问题。

WSNs；非均匀分簇；社会福利函数；多跳转发

无线传感器网络(Wireless Sensor Networks，WSNs)分簇路由协议按照控制方式可分为集中式路由协议［1-3］和分布式路由协议［4-10］。相比于集中式算法，分布式分簇路由协议只需获得网络的局部信息，并且具有良好的拓展性，适合大规模的WSNs网络。在以分簇方式自组织的WSNs网络中，节点被分为簇头和簇成员，簇头作为簇的中心负责簇的的构建，收集和融合簇成员新数据并转发给基站，这使得簇头的能量消耗速度远远高于其他簇成员。为解决这一问题，LEACH［4］协议采用随机分簇和周期性簇头轮换策略，把簇头的负载分散到网络中；文献［5］［6］在LEACH的基础上改进了分簇算法，将剩余能量、节点度等考虑在内，克服了LEACH中簇头产生的随机性，保证了簇头的质量。上述协议中，簇头与基站均采用单跳方式直接通信，远离基站的簇头具有较大的能耗，易造成这些节点较早失效。然而，在簇头与基站采用多跳方式通信的网络中，距离基站较近的节点由于需要大量转发其他簇头的数据给基站，能耗较高，也容易较早失效，影响整个网络的性能。

因此分簇路由中无论采用单跳或多跳方式转发数据，簇首间能耗不均衡的问题仍然存在。针对这一问题，UCS［7］采用了非均匀分簇和簇间多跳的思想，在簇头产生后首先构造簇间多跳路由，根据期望转发负荷，通过调整簇的大小的方式，减小簇头间能耗的差距，解决能耗不均衡的问题；EEUC［8］则根据距基站的远近来调整簇的大小，距基站较近的簇具有较小的规模，从而节省能量用来转发其他簇头的数据。以上方法通常是在评估当前网络状态后做出选择，对于节点执行后的网络状态没有预先考虑。

因此，本文在EEUC非均匀分簇的基础上，对簇头的产生和多跳路径的建立进行了改进，依据经济学领域度量收入分配不平等程度的社会福利函数预先评估下一跳中继节点选择后的网络状态，从而选择下一跳簇头节点，提出能量均衡前行算法(Energy Balanced Forwarding Algorithms，EBFA)，解决多跳通信方式中节点的能耗不均衡的问题，以延长WSNs网络的生存时间。

1 网络模型与假设

1.1 网络模型和定义

本文中路由协议的应用场景为周期性数据收集，即在一个M×M二维正方形区域A的随机部署N个传感器节点，区域A中的传感器节点定时地将采集到的数据（如温度，湿度和气压等）汇聚到基站。假设该网络有如下几个特性：①基站（汇聚节点）位于一个正方形监测区域A的外侧，地理位置固定，计算能力较强，能量不受限制；②所有节点结构相同，随机分布在监测区域内，具备数据融合功能和唯一的标识(ID)，并且能保证时间同步；③链路是对称的。若已知对方发射功率，节点可以根据接收信号的强度计算出发送者到自己的近似距离；④节点可以根据与接收者的传输距离，自由调整其通讯功率，既能满足通讯的需求，也可以节省节点的能量消耗。

1.2 无线通信能耗模型

本文采用与文献［4］相同的无线通信能耗，在该模型中，发送端所消耗的能量用于无线电通信发送和功率放大两部分，而接收端消耗的能量仅仅用于无线电通信接收。该模型如1图所示。

图1 无线通信模型

无线信号的能量衰减根据接收端和发送端的距离的不同，分别使用Friss自由空间模型(Friss Free Space Model)和多径衰落信道模型(Multi-path Fading Channel Model)。若两者间的距离小于d0使用自由空间模型，传播能量损失与d2成反比；若距离大于d0则使用多径衰落信道模型，传播能量损失与d4成反比。为了保证接收方正常接收数据，发送方必须具有功率控制能力，以抵消无线信号在传播过程中的能量损耗。因此，发一个l比特的数据包到距离发送端d的节点需要消耗的能量为：

而接收到这个数据包需要消耗的能量为：

本文考虑簇内数据有较大冗余，可以数据融合，簇间转发则不考虑数据融合。数据融合消耗的能量EDA为5 nJ·bit-1·signal-1，εfs为10 pJ·bit-1·m-2，εmp为0.001 3 pJ·bit-1·m-4），Eelec为50 nJ·bit-1，d0=87 m。

2 算法详述

EBFA协议采用经典的轮循机制，每一轮包括四个阶段：簇头竞争，簇间多跳路由路径建立，簇的形成和稳定阶段。

2.1 簇首竞争算法

EBFA协议在簇头竞选阶段采用计时广播［9］代替EEUC的协商机制。为了控制候选簇头的比例，网络中的节点在每轮开始时以概率T选择自己作为候选簇头，其他节点则进入休眠状态直到被唤醒。候选簇头Vi根据公式计算等待时间ti，等待时间ti到达则广播FINAL_HEAD_MSG消息，宣布自己成为簇头，在其竞争范围内的其他簇头则退出竞选。

式中：λ是在0.9～1.0之间的随机数，用于避免广播消息发生冲突；TCH是预先定义的簇头竞争所需要的最大时间；Ei是Vi的剩余能量；E0是Vi节点的初始能量。根据上述公式，广播时间ti很大程度上取决于节点的剩余能量。如果节点比其所处区域的其他节点具有较大的能量，则它成为簇头的等待时间较短，概率较大。但是，当网络运行了相当一段时间之后，所有节点的剩余能量Ei变得非常低，等待时间ti则会变得相当大。为此我们又改进了ti的计算方法：

这样，等待时间会在（0.5～1.0）TCH之间变化，尽可能地减少了网络的延时。根据公式，在簇头的竞争的竞争阶段，只有少量候选簇头广播竞选成功消息，这样在簇头竞选阶段候选簇头之间的通信减少，可以有效减少簇头的通信消耗。

簇头选举的伪代码如下：

同时，每个候选簇头设置一个竞争范围Rcomp，它是该节点与基站距离的函数［8］，用于控制簇头在网络中的分布。假设是预先定义的最大竞争半径，候选簇头Vi的Rcomp为：

式中：dmax和dmin分别代表节点和基站的最大距离和最小距离，d(Vi，BS)代表Vi和基站的距离，c是位于0和1之间的常数。根据上述公式，候选簇头的竞争范围在(1-c)到之间变化，并且随着候选簇头到基站距离的减小，其竞争半径应该随之减少。因此距离基站较近的区域选举簇头簇头较多，簇的几何尺寸也较小。较小的几何尺寸是为了减少簇内通信消耗，节省下来的能量则用于簇间转发，避免过早死亡。

下图给出了一张候选簇头的竞争示意图，其中圆圈表示候选簇头的竞争区域。由公式可知，V1和V2不互为邻居节点，V3位于V4的竞争范围内，而V4不位于V3的竞争范围，所以V1和V2可以同时成为簇头，当V4首先成为簇头后，V3则不能成为簇头。

图2 候选簇头的竞争区域

2.2 簇间多跳路由协议

EBFA协议采用簇内单跳和簇间多跳相结合的数据传输方式。每个成功竞选的簇头选择其他簇头作为中继节点，转发数据分组至基站，这就需要提前建立多跳传输路径。我们假设数据冗余度有限，中继节点无法融合其他簇头和自身数据，只能简单转发来自其他簇头的数据。

首先，竞选成功的簇头CHi(i=1，2，3，4，...，K，K为簇头数量)，已经广播一条FINAL_HEAD_MSG消息，广播功率覆盖xi,yi倍簇头竞争半径范围内的节点。这条消息包括簇头ID，剩余能量Ei，竞争半径Rcomp和到基站距离dtoBS等。簇头CHi接收到簇头CHj信息后，计算CHi到CHj的大概距离，建立一个候选中继节点信息表，如表1所示：在多跳路由建立过程中，簇首CHi的中继候选节点集合N(i)为：

式中：k∈［1，3］，k取值越大，中继候选节点集合中节点越多。簇头CHi运用贪婪算法在其候选中继集合中，选择其中中继节点N(i)，中继节点N(i)在所有候选节点中具有最小的代价函数。

代价函数参考阿特金森福利函数设计［11］。社会福利函数是经济学领域度量收入分配不平等程度的一种方法，社会收入差距越小，阿特金森指数值也就越小。阿特金森指数值的取值范围为［0，1］，其中0代表了社会达到了收入的完全公平分配。代价函数如下：

EUB描述了节点在单跳通信可达区域范围H内的能量平衡状态，其中n是区域内的节点的个数，E(i)表示节点的剩余能量，Eˉ表示区域内所有节点的平均剩余能量。nj≥2,j=1,2,3,4是不平等厌恶指数，在0到正无穷取值，常用的取值为1.5、2.0、2.5。

在选择中继节点时，簇头CHi运用贪婪算法在其候选簇头节点中，计算将数据传给其中一个候选中继节点的EUB的预测值，最终代价函数值最小的一个候选中继节点将作为中继节点。详述其过程：我们假定将候选中继节点k作为下一跳的中继节点，并假设将数据分组传给候选中继节点k，我们能计算出候选中继节点k预期中的剩余能量为：

候选中继节点k接收到数据分组后，还要将数据分组传送给基站，则它预期中的剩余能量为：

而其他的候选中继节点则没有消耗能量，它们的剩余能量为：

根据上述公式，估算作为当前CHi节点的候选中继节点集合N(i)中每一个节点的EUBik，即阿特金斯福利指数：

其中

当前节点CHi从中继节点集合N(i)中选择阿特金斯福利指数EUBik最小的节点作为下一跳节点。

下面对此代价函数做几点说明：

①单跳通信可达区域范围H即可与簇头通信的候选中继节点集合，候选中继节点到基站都比簇头到基站的距离小，最终的中继节点都是从候选中继节点选取出来的，所以每一跳数据分组都是向基站方向单向流动。不可能出现为了消除区域内的能量不平衡状态，数据分组在一个回路上反复转发；②多跳路由的最终目的是将数据转发到基站，供用户使用。有两种情况簇头会将数据发送给基站，完成多跳路由的建立：一是簇头距离基站较近，候选中继节点为空；二是假若基站在簇头可通信范围(本文中簇头的可通信范文半径为)内，预先评估将数据分组直接发送给基站的EUB值，若其代价函数最小则簇头发送给基站。

2.3 分簇算法

簇间的多跳路径建立完成后，簇头广播公告消息，普通节点从休眠状态被唤醒，进入分群阶段。公告消息是控制信息短消息，包含发送节点的ID，剩余能量（簇间转发后的预期值）和到基站距离等，消息的广播半径是簇头竞争半径的δ倍，其中δ∈［1，3］。每个普通节点按照以下方法确定自己本轮的簇头：节点接收簇头的广播信息后，在竞争半径覆盖到自己的几个簇头中，选择剩余能量较大的节点加入；若没有簇头覆盖到自己，则主动广播请求消息并加入首先回复确认消息的簇头。

2.4 稳定阶段

稳定阶段，非簇头的无线通讯模块关闭，直到分配的传输数据时间到来，这样可以节约节点能量。簇首完成所有节点数据收集后，进行数据融合，然后经由簇间多跳路由传送数据至基站。

3 仿真结果及分析

为了验证EBFA协议的性能，利用MATLAB在相同条件下仿真LEACH、EEUC和EBFA协议并对比多项性能。仿真参数如表1所示，其中网络参数取自文献［8］，协议中的参数通过运行多次实验来找出其最优值。

表1 网络环境与参数

3.1 簇头数量

在网络拓扑结构相对稳定的情况下，一个优秀的分簇算法每轮选出的簇头数量应该比较稳定，集中于簇头数量最优值的附近，以优化网络的结构。在没有任何节点死亡的情况下，图3比较了LEACH、EEUC和EBFA路由协议算法随机选取的100轮种的簇头数量的分布情况。

图3 簇头的数量分布统计

由图3可见，LEACH的簇头数量波动范围较大，而EEUC和EBFA的波动范围较小，其中EBFA产生的簇头成正态分布更为稳定。这样的结果与算法的簇头选举算法密切相关，LEACH的簇头选举采用随机数和阀值的控制机制，难以控制每轮生成的簇头数量，而EEUC和EBFA采用了候选簇头局部竞争的方法，所生成的簇头的数量得到很好的控制，并使之分布于簇头最优数量作于很小的邻域内。相比EEUC，EBFA采用计时广播的方式代替了竞争协商，减少了用于控制信息的开销；并且EBFA不再维护候选簇头的邻居候选节点，竞选成功的簇头只需要通知其竞争半径范围的其他候选推出竞选。

3.2 网络生命周期

本协议的思想之一就是利用非均匀分簇的思想来解决热点问题，延长网络的存存时间。下面首先通过网络生存周期来验证3种协议的能量有效性。

图4显示了存活节点数随着仿真周期的变化情况。从图中可以看出，本协议相对于LEACH和EEUC明显提高了网络生存周期。由于采用了非均匀分簇和簇间多跳路由有机结合的方式，本协议有效地平衡了靠近基站的簇和远离基站的簇之间的数据传输能耗。LEACH的网络生命周期与另外两种协议相差很大这是因为LEACH只适合小型网络不适合本文仿真的网络环境。相比于EEUC，本协议采用计时广播方式代替协商机制，有效减少了簇头竞争阶段的通信耗能；并且依据阿特金森福利函数建立的簇间优化路由不仅有效的平衡了不同位置簇头的能耗，也减少了网络的整体能量消耗。

图4 三种协议存活节点数随着时间的变化曲线

表2是三种协议的网络生命周期。EBFA与LEACH、EEUC相比，在LT1上分别提高了169.3%和54.5%，在LT2上分别提高了90.8%和39.4%，网络生命周期最大程度上得到延长。

表2 网络生命周期

3.3 网络的能量均衡性

本文主要从节点剩余能量方差、节点剩余能量分布和死亡节点分布来衡量网络的能量均衡性［12］。

图5 网络节点剩余能量方差变化曲线

图5给出了三种协议节点能量方差随时间变化的比较，本协议的网络节点能量方差一直都很低变化不大，表明本协议能有效的均衡网络及节点能量，从图5可以看出，LEACH簇头的产生具有随机性，且不同位置的簇头能量消耗差异很大，所以均衡性较差；EEUC采用非均匀分簇的思想来平衡簇头之间的能耗，达到了较好的均衡效果；EBFA协议同样采用非均匀分簇，但能量均衡性能表现最好，这说明通过福利函数评价建立的簇间多跳路径在平衡能量消耗方面发挥了较好的作用。

本文还比较了节点剩余能量的分布情况。图6中三图是当网络中第一个节点死亡时，网络中所有节点剩余能量的数量分布，直观显示了网络中节点之间剩余能量的差距。LEACH协议中，当第一个节点死亡时，仍有大量节点剩余较多的能量，能量均衡性较差；EEUC中引入非均匀分簇的多跳路由机制，较好解决了这个问题，当第一个节点死亡时，没有节点仍剩余较多能量，其他节点剩余能量差距不大；EBFA中，当网络中出现第一个死亡节点时，网络已经运行了相当一段时间，并且节点剩余能量都都在20%左右，节点间的能量均能最好。

图6 剩余节点能量分布

图7中三图是网络中死亡节点到达20%时，死亡节点的分布情况，图中‘o’代表存活节点，‘x’表示死亡节。从图中我们可以看出：LEACH死亡节点全都集中在距离基站较远的区域，这是因为它们需要消耗大量能量转发簇内节点收集的信息，EEUC则由于靠近基站的节点承担过量的转发任务而大量死亡，EBFA协议很好地解决了能量均衡性的问题，死亡节点分布比较均匀，网络未出现严重的“能量空洞”现象。

图7 死亡节点分布图

4 总结

本文汲取EEUC非均匀分簇和簇间多跳路由的算法思想，提出了改进的分布式非均匀分簇路由算法，即EBFA。EBFA协议在簇头竞争阶段采用计时广播机制，降低了控制消息的开销；簇间多跳的建立引入依据社会福利函数设计的代价函数，优化了中继节点的选择。仿真结果表明，EBFA能够有效均衡网络能量消耗，延长网络的生命周期。

［1］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.

［2］雷霖，李伟峰，王厚军.基于遗传算法的无线传感器网络路径优化［J］.电子科技大学学报，2009，38(2)：227-230.

［3］陈晓娟，王卓，吴洁.一种基于LEACH的改进WSN路由算法［J］.传感技术学报，2013(1)：116-121.

［4］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000.IEEE，2000：10 pp.vol.2.

［5］Younis O，Fahmy S.Distributed Clustering in Ad-Hoc Sensor Networks：A Hybrid，Energy-Efficient Approach［C］//INFOCOM 2004.Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE，2004，1.

［6］蔡镔，陈向东，杨英.节点密度自适应的传感器网络加权分簇算法［J］.传感技术学报，2009，22(4)：558-562.

［7］Soro S，Heinzelman W B.Prolonging the Lifetime of Wireless Sensor Networks Via Unequal Clustering［C］//Parallel and Distributed Processing Symposium，2005.Proceedings.19th IEEE International.IEEE，2005：8.

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

［9］蒋畅江，石为人，唐贤伦，等.能量均衡的无线传感器网络非均匀分簇路由协议［J］.软件学报，2012，23(5)：1222-1232.

［10］曾华圣，熊庆宇，杜敏，等.一种分布式能量高效的WSNs非均匀分簇路由协议［J］.传感器与微系统，2014，33(3)：146-149.

［11］Jiang H，Sun Y，Sun R，et al.Fuzzy-Logic-Based Energy Optimized Routing for Wireless Sensor Networks［J］.International Journal of Distributed Sensor Networks，2013.

［12］黄丹.无线传感器网络分簇路由协议研究［D］.大连：大连海事大学，2013.

孙彦景(1977-)，男，山东滕州，博士，教授，博士生导师，主要研究领域为矿井无线通信与监控，矿山物联网等，yanjingsun_cn@163.com；

林昌林（1990-），男，硕士研究生，主要研究领域为无线通信和自组织网络，mymail1991@163.com

An Energy Efficient Distributed Uneven Clustering Routing Algorithm for WSNs*

SUN Yanjing1，2*，LIN Changlin1，JIANG Haifeng3
(1.School of Information and Electrical Engineering，China University of Mining and Technology，Xuzhou Jiangsu 221116，China；2.Coal Mine Electrical Engineering and Automation Laboratory in JiangSu Province，Xuzhou Jiangsu 221008，China；3.School of Computer Science and Technology，China University of Mining and Technology，Xuzhou Jiangsu 221116，China)

To solve the"hot zone"problem appearing in distributed clustering routing multi-hop communication，this paper proposes an energy balanced forwarding algorithm(EBFA)based on distributed clustering routing protocols.EBFA adopts the uneven clustering techniques and multi-hop inter-cluster strategy.During the multi-hop forwarding，the social welfare function is introduced to pre-assess the extent of energy balance between nodes in the data forwarding path，and the node with a better energy balance is chosen as the forwarding node.Simulation results show that：Compared to LEACH and EEUC，EBFA prolongs the lifetime of the network and balances the energy consumption among sensor nodes，which solves the hot zone problem in the multi-hop routing.

WSNs；uneven clustering；social welfare function；multi-hop forwarding

TP92

A

1004-1699(2015)08-1194-07

��7230；6150P

10.3969/j.issn.1004-1699.2015.08.016

项目来源：国家自然科学基金面上项目(51274202)；中央高校基本科研业务费专项资金项目(2013RC11)；江苏省科技成果转化项目(子课题)(BA2012068)；江苏省自然科学基金面上项目(BK20130199，BK20131124)；江苏省产学研前瞻性联合研究项目(BY2014028-01)；中国矿业大学重大项目培育专项(2014ZDPY16)

2015-02-12 修改日期：2015-05-28