基于非均匀分簇和信息熵的无线传感网络路由算法*

2015-08-24范书瑞刘艳萍刘建龙彭明莎郭海红

传感技术学报 2015年12期

刘　佳，范书瑞，2，刘艳萍*，刘建龙，彭明莎，郭海红

（1.河北工业大学电子信息工程学院，天津300401；2.昆士兰大学信息技术与电气工程系，澳大利亚昆士兰4072；3.中国石油华北石化公司三联合运行部，河北任丘62550）

刘佳1，范书瑞1，2，刘艳萍1*，刘建龙3，彭明莎1，郭海红1

针对无线传感网络分簇算法中能量分布不均衡导致的“热区”问题，提出一种基于非均匀分簇和信息熵的路由算法。在簇头选举和竞争半径计算过程中综合考虑节点能量、节点密度和节点距基站距离，均衡簇头能耗以延长生存时间。采用簇间单跳多跳混合通信的路由规则，减少簇间通信能耗。对节点信息熵进行数据融合，引入融合权重系数减小数据融合的不确定性，提高数据融合效率。仿真结果表明，与LEACH、EEUC和EBUCA相比，该算法能够有效均衡网络能耗，延长网络生命周期。

无线传感网络；能量高效；非均匀分簇；路由协议；信息熵

EEACC：6250doi：10.3969/j.issn.1004-1699.2015.12.023

无线传感网络WSNs（Wireless Sensor Networks）是由分布在被监测区域内的大量廉价的传感器节点以自组织的形式构成的网络，其目的是协作地感知、采集和处理网络覆盖区域内被监测对象的信息，并发送给远端的基站。由于无线传感网络节点能源的有限性对网络性能造成严重影响，很多文献通过调度控制优化［1-2］。但是延长网络生命周期是WSNs协议的重要设计目标，主要方法之一就是设计高效节能的路由协议［3］。已有研究结果表明［4］，分簇路由协议可有效降低网络能量消耗和延长网络生命周期。LEACH［5］（Low Energy Adaptive Clustering Hierarchy）是较早提出的低能量自适应分簇路由算法，有效的延长了网络的生命周期，但是其单跳通信方式使远离基站的簇头能量消耗不均衡。文献［6］采用多跳路由通信方式节省节点能量，但基站附近节点由于大量任务转发，导致能耗过多出现能量空洞（energy hole）。针对这一问题，文献［7］提出了EEUC（Energy-Efficient Unequal Clustering）算法，根据节点到基站的距离不同构造不同规模的簇，缓解基站附近节点“热区”问题。EEUC算法候选簇头的选择具有随机性，不能从整体上减少全网能量消耗从而缓解“热区”问题。文献［8］提出EBUCA算法基于节点能量、密度对阈值改进，并引入簇头密度和到基站距离进行簇的设计，均衡网络能耗。文献［9］基于最小生成树构造传输路径，文献［10］对簇间路由进行优化提出改进的簇头多跳路由协议。这两种算法优化了路由路径减少了通信能耗，但是都没有考虑数据发送之前簇头进行数据融合所造成的能耗。为此文献［11］采用信息熵确定数据融合阈值，进行簇内数据融合，节约节点能耗。

综合以上算法所存在的问题，本文提出一种基于非均匀分簇和信息熵数据融合方法的路由算法。算法根据节点能量、节点距基站距离和节点密度三种参数，设计权衡系数α平衡三者之间的关系。基于权衡系数设计权值公式，选择权值大的节点作为簇首。减少基站附近节点能量消耗，均衡全网能量负载。并对竞争半径公式基于节点距离、能量和密度进行改进，减少簇头能耗并延长网络生命周期。簇间采用单跳多跳的混合通信方式选择簇头下一跳的最优路径，进一步减轻簇头的负担。利用节点信息熵进行数据融合，引入融合权重系数减小数据融合的不确定性，提高算法数据融合效率以减少节点能耗。

1　系统模型

1.1网络模型

本文对网络模型做如下假设：①N个传感器节点随机分布在网路检测区域，汇聚节点位于检测区域附近。②每个节点有自己的ID，节点通过信号强度指示（RSSI）可感知自身的能量和坐标信息，汇聚节点sink可感知所有节点的位置。③网络以轮为周期，每轮包括分簇阶段和数据传输阶段。簇头选择之后，簇内节点采集数据传输给簇头进行数据融合之后发送给汇聚节点Sink。

1.2能量消耗模型

文中采用经典的无线通信模型［12］，节点发送kbit数据时消耗的能量为：

节点接收kbit数据时的能耗为：

其中，d为节点间传输距离，εfs、εamp为信道模型功率放大系数。选择哪种损耗模型是由β值决定。若节点传输距离较近d＜d0，则β=2，采用空间信道模型；当节点传输距离较远d＞d0，则β=4，采用多径衰落信道模型。d0为传输距离阈值系数

2　算法

2.1簇头选举与簇的建立

算法通过节点簇头的竞争方式选举簇头，基于节点剩余能量、节点到基站距离和节点密度的权衡系数设计簇头的选举公式。在无线传感网络中距离汇聚节点近的簇首由于承担数据转发任务重而过早死亡，形成“热区”问题。本文通过权衡节点的动态能量、节点到基站距离和节点密度进行簇头竞争选举，均衡网络负载能量，防止汇聚节点附近的节点过早死亡。

2.1.1网络初始化

首先对网络进行初始化，汇聚节点通过RSSI感知自身位置和节点的位置，节点距离汇聚节点的最远距离dmax和最近距离dmin。假设监测区域内节点经历轮数为n，初始能量为E0，节点当前能量为Ei，距离基站的距离为di，节点密度为Qi。

2.1.2簇头选举

节点剩余能量与节点距离基站的距离和节点密度三者的权衡系数α为：

其中节点密度Qi的定义为：

其中，Neighbor（i）为节点i的邻居节点个数，Neighbor（alive）为当前网络的存活节点。

权衡系数α为节点剩余能量、距基站距离、节点密度之间的融合系数，取值（0，1）。权衡系数是为了对能量、密度、距离三个参数起到相对平衡的作用。节点能量大但距基站远的节点，可能比能量较小但距基站较近的节点有更大的概率当选为簇头。可以减少基站附近节点能量消耗过多，避免“热区”效应。同样距基站距离相同但节点密度高、剩余能量小的节点，有可能比节点密度小、剩余能量高的节点当选簇头的概率大。权衡系数α可以平衡节点的能量、距离和密度之间的关系，减少汇聚节点附近节点的能量消耗，均衡全网能量负载。

在簇头选择阶段，如果节点收到一个簇头的消息则加入，如果收到多个簇头节点信息则计算各簇头节点的竞争权值，选择竞争权值大的簇头节点加入簇。簇头竞争权值公式为：

其中Wi为节点竞争簇头的权值，α为节点、能量、密度的权衡系数，α1+α2+α3=α，α1=0.4α，α2=0.3α，α3=0.3α。权值Wi分别由三项构成，第一项为节点剩余能量和初始能量的比值项，使剩余能量大的节点当选为簇头的概率大，为簇头通信提供更多的能量。第二项为节点距基站距离项，使节点距基站距离近的节点当选为簇头的概率大，从而减少簇头与基站之间的通信能耗。第三项为节点密度项，使得密度大的节点当选为簇头的概率大，减少簇内通信能量消耗。Ei为节点当前动态能量，E0为节点初始能量，Qi为节点密度，di为节点距基站距离，dmax为网络节点距基站的最远距离，N为传感器节点总数，Kc为一定区域内节点最优簇头数［13］，根据网络覆盖范围，选择合理的簇首数，降低整个网络的簇间通信和簇内通信的能耗，从而减少整个网络能耗，以达到延长网络生存时间的目的。

N为节点数量，εfs、εamp为能量损耗系数，M为覆盖区域面积，dtoBS表示网络中心点到汇聚节点的距离。

2.1.3竞争半径

簇头根据竞争半径形成新的簇，竞争半径的设计基于节点的剩余能量和节点距基站距离以及节点密度。为了减少基站附近节点的能量消耗过多导致的“热区”问题，靠近基站的节点承担的数据转发任务重，因此为了防止节点过早死亡在保证节点剩余能量高的同时，缩小竞争半径。同时节点密度越大，簇内能量消耗会越多，为了防止簇头节点过早死亡，竞争半径就越小。竞争半径RC的计算公式为：

其中：R为传感器节点的最大覆盖半径，c为（0，1）之间的常数，系数最优值由仿真实验得出。

2.2路由规则

为了避免“热区”问题和减少簇间数据传输能耗，本算法采用簇内单跳通信，簇间单跳多跳的通信方式。若簇头和基站之间距离小于单跳通信阈值d0则选择单跳方式，否则采用多跳通信方式。在簇头向基站传输数据的过程中，簇头先对簇内数据进行融合处理，然后从邻居节点中选择一个簇头作为中继节点，中继节点负责将融合好的数据转发到基站。主要路由规则为：

①首先，簇头给竞争范围内的节点广播消息。消息包括广播簇头ID、簇内节点数、节点剩余能量和距基站的距离。

②对于传感器节点i和j，若节点i位于节点j的通信范围内，并且节点j位于节点i的通信范围内，则称节点i和j互为邻居节点。邻居簇头节点根据接收到的广播信息，建立一张簇头与邻居簇头距离的信息表，如表1所示。

表1　R邻居簇头节点信息表

③簇头Hi采用贪婪算法在邻居簇头集合中选择下一跳节点，候选节点中具有最小代价函数的节点被选为下一跳节点。代价函数定义如式（8）所示：

其中，簇头Hj为簇头Hi的邻居簇头，dCHj为簇头Hj到基站的距离，maxdCHi为簇头Hi邻居簇头中到基站距离的最大值。ECHj为簇头Hj的当前剩余能量，maxECHi为簇头Hi邻居簇头中当前剩余能量的最大值。NCHj为簇头Hj簇内节点数，maxNCHi为簇头Hi邻居簇头中簇内节点数的最大值。α、β、γ为权重因子，α+β+γ=1。代价函数的设计主要考虑到：（a）第一项首先考虑的是下一跳节点的位置，为了减少通信能耗，多跳路由应该尽量选择较短路径。（b）第二项选择剩余能量较大的簇头作为下一跳节点，因为数据转发需要消耗更多的能量，所以尽量选择能量大的簇头作为下一跳节点。（c）第三项选择簇内成员节点较少的节点作为下一跳，簇内节点少则簇内通信能量少，簇头有更多的能量用来完成数据转发。

④如果簇头Hi的下一跳节点为节点本身，则直接发送数据到基站；否则，簇头将数据发送到下一跳节点，所有簇头都找到下一跳节点后，簇间多跳路由建立完成。

2.3基于信息熵的数据融合

本文基于节点的信息熵对簇内数据进行融合，引入融合权重系数减小数据融合的不确定性，提高算法数据融合效率。信息熵是一种基于信息表现特征的统计形式，它反映信息中平均信息量的多少［14］。信息熵为信源全局的统计特征，表示总体的不确定性。节点的信息熵值反映节点数据的相似程度，是节点数据融合的有效依据。

2.3.1对数据进行预处理

首先，由于环境等各种因素会给节点数据造成误差，对数据进行预处理。采集节点数据，利用格罗贝斯准则对数据进行处理。设数据x1，x2，x1，…，xn服从正态分布。

格罗贝斯统计分布为：

根据所给定的显著水平（α=0.05）通过查表法得出统计量临界值g0（n，α）。若节点数据测量值的统计量满足g0≤g0（n，α），则测量数据值有效；反之，无效。

2.3.2计算节点二维信息熵

设C为传感网络中的一个簇，簇内节点数为N，簇内节点数据采集时间长度为M。节点数据预处理后将符合条件的数据传送给簇头，簇头接收到的数据为Cij=（ci1，ci2，…，cim；其中i=1，2，…，n；j=1，2，…m）。选择簇内节点的加权数据均值作为空间特征量，分别计算节点i的加权数据均值di和簇内节点的加权数据均值di'，组成二元特征组（di，di'）。联合概率密度为：

簇内的二维信息熵为：

其中Hmax为簇内节点二维信息熵的最大值，Hmin为簇内节点二维信息熵的最小值。

2.3.3对数据进行融合处理

利用信息熵融合系数对数据进行融合，对于确定性不同的数据分配不同融合权重系数。发生概率大的数据则其不确定性小，分配大的权重系数；发生概率小的数据则其不确定性大，分配小的权重系数。为不同的数据分配不同的融合权重系数，减小融合结果的不确定性。

①簇内节点的自信息量为：

信息量比率为：

②信息熵融合权重系数为：

③对数据进行融合

3　算法仿真及分析

为了验证改进算法的性能，对改进算法和LEACH算法、EEUC算法、EBUCA算法进行多项性能对比。本文在MATLAB平台下进行仿真分析，将400个节点随机分布在200 m×200 m的区域中。实验参数如表2所示。

表2　R实验参数

首先对4种算法的生命周期进行比较，如图1所示，改进算法比LEACH算法、EEUC算法和EBUCA算法有效延长了网络生命周期。改进算法的生命周期比LEACH算法延长约2.5倍，比EEUC算法延长约50%，比EBUCA算法延长约14%。

图2给出了4种算法的死亡节点分别为1，100，200，300，400时所对应网络周期运行轮数。LEACH、EEUC、EBUCA算法和改进算法出现首个死亡节点的轮数分别为304轮、530轮、600轮和780轮，改进算法有效的延长了网络的稳定期（首个节点死亡时间）。改进算法最后一个节点死亡轮数为1 610轮，LEACH、EEUC和EBUCA分别为630轮、1 080轮和1 410轮。改进算法有效延长了网络的稳定期和生命周期。

图1　R网络生命周期对比

图2　R死亡节点对比

随机选取10轮运行结果对比4种算法的全网簇头能耗之和。如图3所示，LEACH算法能耗最高，因为其采用单跳路由且簇头分布不均匀。EEUC算法、EBUCA和改进算法簇首能耗较低，EEUC算法采用多跳路由规则减少簇头能量消耗，EBUCA算法基于节点密度优化簇首选择，使簇首能耗减少。本文改进算法中簇头采用单跳和多跳结合的路由规则，降低了簇头能耗。

图3　簇首能耗对比

图4R对比了4种算法的网络节点剩余能量均值随网络周期的变化情况，改进算法的节点剩余能量均值一直明显高于其他三种算法，而且能量消耗趋近于直线。这表明改进算法整个网络生命周期中的能量消耗较为均衡，有效避免某些节点负载过度导致的“热区”问题。

图4　R网络节点剩余能量均值对比

4　结论

本文提出一种基于非均匀分簇和信息熵的无线传感网络路由算法，主要包括簇头权衡系数和权值公式的设计、竞争半径的改进、路由规则的设计、基于信息熵的数据融合，算法在延长网络生命周期的同时能够减少节点能耗。通过仿真结果表明，改进算法减少了簇头能耗，显著延长了网络的稳定期和生命周期，能够均衡节点能耗有效避免“热区”问题。

［1］Bachir A，Dohler M，Watteyne T，et al.MAC Essentials for Wireless Sensor Networks［J］.IEEE Communications Surveys&Tutorials，2010，12（2）：222-248.

［2］任苗苗，范书瑞，王悦良.一种时分簇调度算法的实现［J］.传感技术学报，2015，28（7）：1073-1077.

［3］Shuang-Hua Yang.Wireless Sensor Networks：Principles，Design and Applications［M］.London：Springer，2014：7-47.

［4］Santar Pal Singh，Sharma S C.A Survey on Cluster Based Routing Protocols in Wireless Sensor Networks［J］.Procedia Computer Scienc，2015（45）：687-695.

［5］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocols for Wirelesss Microsensor Networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.Washington，DC：IEEE，2000：3005-3014.

［6］Mhatre V，Rosenberg C.Design Guidelines for Wireless Sensor Networks：Communication，Clustering and Aggregation［J］.Ad Hoc Networks，2004，2（1）：45-63.

［7］Chengfa Li，Mao Ye，Guihai Chen，et al.An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks［C］// Proceedings of the IEEE 15th International Conference on Mobile Ad Hoc and Sensor Systems.Washington DC：IEEE，2005：7-10.

［8］卢先领，王莹莹，王洪斌，等.无线传感网络能量均衡的非均匀分簇算法［J］.计算机科学，2013，40（5）：78-81.

［9］张文梅，廖福保.改进的无线传感器网络非均匀分簇路由算法［J］.传感技术学报，2015，28（5）：739～743.

［10］陈炳才，么华卓，杨明川.一种基于LEACH协议改进的簇间多跳路由协议［J］.传感技术学报，2014，27（3）：373～377.

［11］李怀俊，张学习.基于二维信息熵的无线传感网络簇内数据融合方法的研究［J］.计算机应用研究，2014，31（7）：2171-2174.

［12］彭铎，黎锁平，杨喜娟.一种能量高效的无线传感网络非均匀分簇路由协议［J］.传感技术学报，2014，27（12）：1687-1691.

［13］侯华，刘超，周武旸.能量高效均衡的动态分簇路由设计［J］.北京邮电大学学报，2013，36（3）：54-59.

［14］唐晨，王汝传，黄海平，等.基于信息熵的无线传感网络数据融合方案［J］.东南大学学报，2008，38（3）：275-279.

A Routing Algorithm for Wsns Based on Uneven Clustering and Entropy Theory*

LIU Jia1，FAN Shurui1，2，LIU Yanping1*，LIU Jianlong3，PENG Mingsha1，GUO Haihong1
（1.School of Electric Information Engineering，Hebei University of Technology，Tianjin 300401，China；2.Information Technology and Electrical Engineering，The University of Queensland，Queensland 4072，Australia；3.PetroChina Huabei Oilfield Company，Three combined operations，Renqiu Hebei 062550，China）

An energy efficient routing algorithm is the major concern in wireless sensor networks（WSNs），especially the hot spot，because of unbalanced energy consumption.Based on uneven clustering and entropy theory，a kind of improved routing algorithm is proposed for solving that problem.In the process of cluster head election and competition radius calculation，node energy，density and distance to BS are considered to effectively balance energy consumption and prolong the life cycle of cluster head nodes.Meanwhile the hybrid rules of single-hop and multi-hop routing is adopted to reduce the energy consumption among clusters.Introducing fusion weight coefficient，information entropy mechanism is used for reducing the uncertainty and improving the efficiency of data fusion.Simulation results show that compared with LEACH，EEUC and EBUCA，the new algorithm can balance energy consumption and prolong the life cycle of wireless sensor networks.

wireless sensor network；energy efficient；uneven clustering；routing protocol；entropy theory