基于PSO的信息熵数据融合非均匀分簇路由算法

蔡明伟 刘佳

摘 要：针对无线传感器网络分簇算法中能量分布不均衡导致的“热区”和簇头负载过重问题，提出了一种基于PSO算法优化簇头选举的非均匀分簇算法。在候选簇头选举和竞争半径计算过程中综合考虑节点动态能量、节点密度和节点距基站距离，将网络进行非均匀分簇，并引入PSO算法进行最终簇头选举。根据节点能量、节点密度和距基站距离确定簇间单跳多跳结合的路由规则，选取代价函数小的节点作为下一跳节点。基于节点信息熵确定融合阈值，进行簇内数据融合剔除冗余数据。仿真结果表明，改进算法的数据传输量比EEUC算法和UCRA算法分别提高了20%和10%，提升了数据的融合效率，有效延长了网络生命周期，簇头能量消耗得到均衡，减少了网络能量消耗，网络的整体性能显著优于其他对比算法。

关键词：计算机网络;无线传感器网络;非均匀分簇算法;PSO算法;路由规则;信息熵

中图分类号：TP273 文献标志码：A

doi： 10.7535/hbgykj.2019yx06008

文章编号：1008-1534（2019）06-0415-07

Abstract： Aiming at solving the 'hot spots' and cluster head energy consumption problem in wireless sensor networks（WSNs） caused by unbalanced energy consumption， an uneven clustering routing algorithm based on adaptive particle swarm optimization （PSO） is proposed. The node energy， node density and the distance to the BS are considered during the cluster head election and competition radius calculation. Network is divided into clusters of unequal size. The PSO is used to select the final cluster heads according to the cluster size. Meanwhile， hybrid routing rules of hop routing and multi-hop routing are adopted based on node energy， node destiny and the distance to BS， and the cluster heads of minimum cost function are chosen as the next hop. Data fusion in the cluster is conducted to eliminate redundant data based on entropy theory. Simulation results show that the data transmission amount of the improved algorithm is 20% and 10% higher than those of EEUC and UCRA algorithms. The lifetime of the improved algorithm is extended， the energy consumption of cluster head is balanced， the network energy consumption is effectively reduced， and the performance of the network is significantly better than the other comparison algorithms.

Keywords：computer network; wireless sensor network（WSN）;uneven clustering algorithm; PSO algorithm; routing rules; entropy theory

無线传感器网络（wireless sensor network，WSN）是由大量的静止或移动的传感器以自组织和多跳的方式构成的无线网络[1]。在传统的无线传感器网络中主要是采用电池进行整个网络的运行供应，因此如何减少网络中的能量消耗和平衡整个网络中的能量消耗分布已经成为无线传感器网络的研究热点。无线传感器网络中的分簇策略是将节点按照簇进行分类，簇头将簇内的信息进行融合之后发送给基站，能够有效减少网络通信能量消耗，延长网络生命周期。国内外学者提出了多种分簇路由协议来延长网络生命周期。HEINZELMAN等[2]提出的经典低能耗自适应路由协议LEACH（low energy adaptive clustering hierarchy）能够有效延长网络生命周期，但是由于簇头选择不合理和路由单跳导致簇头过早死亡。卢先领等[3]针对LEACH算法簇头分布不均匀问题，基于节点能量和通信代价问题选择簇头，由于采用的迭代方式增大了能量消耗造成网络寿命缩短。非均匀分簇算法（energy-efficient unequal clustering，EEUC）针对网络中存在的“热区”问题，根据节点和基站的距离建立相应范围的簇以解决问题[4]。但EEUC算法中对候选簇头的选举过于随机，簇头规模较大时，簇头选举不当会出现网络能量消耗不均衡。潘继强等[5]引入簇半径动态确定方式进行簇头选举，相对于LEACH延长了网络的生命周期，但是算法采用簇间单跳路由方式导致簇头能量消耗过重。SINHA等[6]在非均匀分簇的基础上簇间采用多跳路由规则，但在候选簇头选举和竞争半径计算过程中没有综合考虑节点能量、距基站距离和节点密度，不能很好地改善网络“热区”问题。张瑞华等[7]提出一种基于非均匀分簇的能量有效的无线传感路由算法（UCRA），该算法采用加权进行非均匀分簇和簇间最小能量消耗多跳路由算法，但算法参数设置的局限性不能确定其最优值。

针对以上算法存在的不足，本文提出了一种基于PSO算法优化簇头选举的非均匀分簇算法，以解决“热区”问题和延长网络的生命周期。在文献[7]的基础上综合考虑节点能量、节点距基站距离和节点密度，完成非均匀分簇，最后在规模较大的簇内引入PSO优化算法选举最终簇头，簇间采用单跳多跳结合的路由规则，并利用节点信息熵进行数据融合。

1 网络系统

1.1 网络模型

对本文中的网络系统提出以下设定。

1）网络中的各个工作节点随机分布在整个网络中，其中汇聚节点sink设置在待测网络附近。

2）网络中的各个传感器节点都有其独立ID，节点根据信号强度指示（RSSI）来感应其节点的位置信息和节点能量，其中sink节点能够获得网络全部节点的位置信息。

3）路由算法周期为轮，每轮分为节点分簇和数据通信传输2个阶段。首先进行簇头选举，然后对网络中每个簇内的节点进行数据采集，经过处理融合之后将信息传输给sink节点。

1.2 能量消耗模型

采用经典的无线通信系统模型来作为路由算法的能量消耗模型，网络中的节点根据需要通信的距离选择相应的模型[8]，算法通信过程中节点每发送k bit数据所需要消耗的能量为

同样，节点每接受k bit的数据信息时需要消耗的能量为

式中：Eelec为无线模块电路的能量;d为待测区域中节点之间的通信距离;Efs，Emp为路由通信系统中信道模型功率放大系数。

传输距离阈值系数：

2 算 法

为解决基站附近簇头任务过重导致的“热区”问题和均衡网络节点能量消耗以延长网络生命周期，提出的基于PSO算法的非均匀分簇算法分为基于粒子群优化选举簇头的非均匀分簇阶段;单跳多跳结合的路由通信阶段;基于节点信息熵的数据融合阶段。

2.1 非均匀分簇阶段

非均匀分簇阶段又分为簇头选举阶段和成簇阶段。首先在待检测区域的全部节点中选择簇头，并综合节点和基站距离、节点密度以及能量计算候选簇头节点的竞争半径，完成簇的建立。候选簇头节点的选举方法采用LEACH算法的簇头选举方法：网络中的传感器节点在算法的初始化阶段分别随机生成一个随机数μ，若0<μ<1，设置节点当选为簇头的阈值T[9];若μ<T则节点被选举为候选簇头，非候选簇头节点休眠，直到算法中的初始簇头选择阶段结束。对算法中阈值T进行改进，基于网络中的各种因素，综合考虑节点能量、节点密度、节点距基站距离3个因素进行改进。

式中：p是待测区域中的节点被选为簇头的概率;r为算法的轮数;G为网络中最近1/p轮被选为簇头的所有传感器节点的集合;dmin和dmax分别为在网络所有节点中和sink节点最近的距离和最远的距离;di为节点与sink节点的距离;E0和Ei为网络中节点的初始能量和当前能量;Qi为节点附近网络范围内的密度。Neighbor（i）alive为节点附近存活节点数目;Networkalive为网络存活节点数目。

为了实现非均匀分簇，对候选簇头节点引入不同的竞争半径。根据网络中节点的当前剩余能量、一定范围内的节点密度以及节点距基站距离设计竞争半径。为了减少基站附近节点的能量消耗过多导致的“热区”问题，剩余能量相同的情况下，距离基站越近的节点成簇半径越小[10]。簇半径的减小可使基站附近的簇内能量减少，簇头有更多的能量进行簇间通信。另外，节点簇中能量的消耗还和节点密度有关系，密度越大能量消耗越快，相应的竞争半径也就越小。

竞争半径的计算公式为

式中：R为传感器节点的最大覆盖半径;c为（0～1）之间的常数;候选簇头i以Rc为半径广播网络中传感器节点的数据信息，分别为节点ID，节点当前剩余能量，节点竞争半径R。其中候选节点通过接收到的数据信息建立节点信息集，并且根据所接收的信息选择邻居节点中剩余能量最多的节点作为初始簇头。一旦初始簇头被选择，则网络中其周围Rc范围内的所有候选节点都不可再被选为初始簇头。

初始簇头确定之后广播簇头信息，非候选簇头停止休眠，选择通信代价最小的簇头加入，完成簇的建立。

2.2 PSO优化簇头选举阶段

进行初始簇头的选举之后，在PSO算法的基础上选择最终簇头来降低路由算法的复杂度[11]。对阈值k进行区分，如果网络中簇的半径大于阈值k，则引用PSO算法对簇头选取进行最终优化。对PSO基本算法进行改进使其适用于本算法中，并对适值函数进行改进。

传感器节点分布于平面坐标内，网络节点的位置由x，y坐标上的分量决定：

適应值函数的确定主要考虑以下几个要素。

1）簇头能量因子

选簇时应首先考虑簇头的能量问题，簇头负责本簇全网通信部分，相对消耗的能量较多。现考虑节点剩余能量和网络中所有节点的能量关系，将簇头能量因子引入适应值函数中：

2）分簇紧凑性因子

网络节点成簇过程中，应给予位置较优的节点更多成为簇头的机会，簇头距离簇内节点的平均距离越小，则通信消耗越小。考虑节点分布，将分簇紧凑性因子引入适应值函数中：

3）簇头距离基站因子

f3（pj）为网络中各个簇头之间距离的评价因子，表示基站到各个簇首的平均欧氏距离与基站到网络区域中心的欧氏距离的比值。

2.3 路由通信阶段

本算法采用簇内单跳，簇间单跳多跳结合的路由规则[12]来避免路由通信中“热区”问题和减少数据传输能量消耗问题。簇头对成员节点的数据进行融合处理之后，如果簇头和基站之间距离小于单跳通信阈值d0，则选择单跳方式，否则采用多跳通信方式。在数据传输之前，簇内的簇头节点先广播自己的信息，其中包括簇头节点ID、簇内包含节点数、网络内当前节点的能量和位置信息。簇头节点根据接收到的广播信息建立一张邻居簇头信息表[13]。

簇头Hi根据贪婪算法在网络中邻居簇头群中进行下一跳节点的选择，选择算法节点中代价函数最小的节点为算法的下一跳节点。如式（14）所示：

式中：dCHi为簇头Hi到基站的距离;max dCH为各个邻居簇头节点到基站距离的最大值;ECHi为簇头Hi的当前剩余能量;max ECH为邻居簇头节点中当前剩余能量的最大值;NCHi为簇头Hi的簇内节点数;max NCH为邻居簇头节点中簇内节点数的最大值;α，β，γ为权重因子，α+β+γ=1。代价函数的设计基于节点的剩余能量、距基站的距离和节点密度，簇头节点剩余能量越大、距离基站越近、节点密度越大则其代价函数值越小，被选为下一跳节点的可能性越大。

2.4 数据融合阶段

基于节点的信息熵对簇内数据进行融合处理，有效剔除簇内节点冗余数据，提高节点数据信息融合效率。信息熵是一种基于信息表现特征的统计形式，反映信息中平均信息量的多少[14]。在本算法中节点的信息熵值所体现的是网络中节点之间数据信息的相似程度，为算法的数据融合提供有效依据。通常来说信息熵越小系统越有序，信息熵越大系统越无序。

由于环境等各种因素给采集节点数据造成一些误差，所以利用格罗贝斯准则对数据进行预处理（格罗贝斯准则可以有效剔除疏失误差，从而将远离真实值的数据相对减少），这样就可以采用信息熵进行数据融合，提高数据融合的精确性。

选择所接收节点的加权数据均值为空间特征量，并根据所接收数据计算网络节点i的加权数据均值di和簇内节点的加权数据均值d′i，组成二元特征组（di，d′i）。联合概率密度为

设定二维信息熵的阈值H0，当H<H0时，数据中存在异变极值数据。当簇内传感器节点数据有趋同性时，求出簇内节点数据阈值{L，H}，对节点数据进行有序融合。其中L为网络节点数据群中的下限阈值，H为网络节点数据群中的上限阈值。当簇内传感器节点具有趋异性时，根据阈值{L，H}對趋同数据进行数据融合。

3 算法仿真结果

在Matlab平台上进行改进算法、EEUC算法和UCRA算法的多项性能对比。将400个传感器节点随机分布在200 m×200 m的区域中，实验参数如表1所示。

3.1 网络生命周期对比

首先对3种算法的生命周期和稳定期进行比较，如图1所示，改进算法比EEUC算法和UCRA算法有效延长了网络的生命周期。图2选择了网络中死亡节点分别为1，100，200，300，400时网络算法的运行轮数。

3.2 网络能量消耗对比

图3对EEUC算法、UCRA算法和改进算法的网络中总剩余能量进行了对比， EEUC算法的能量最先耗尽，UCRA算法也在1 400余轮耗尽。相比于EEUC算法和UCRA算法，改进算法的剩余能量最多，而且能量消耗趋近于直线。改进算法在非均匀分簇阶段引入PSO算法优化了选举簇头，减少了簇内节点的能量消耗，且簇头采用单跳和多跳结合的路由规则，减少了簇头能量消耗。采用基于信息熵的数据融合方法，降低簇内节点能量消耗，使整个网络生命周期中的能量消耗较为均衡，网络生命周期得到显著延长。

3.3 引入PSO算法后的成簇效果对比

图4为EEUC算法的成簇效果，图5为改进算法的成簇效果。改进算法采用PSO算法进行簇头选举，修正了簇头分布不均的不足，簇内节点分布合理，节点位置更加接近簇的几何中心。

3.4 簇头能量消耗对比

在网络中随机选择其中10轮的运行结果，对网络中所有簇头节点的总能量消耗进行对比。如图6所示，EEUC算法因其网络中簇头节点的分布不均匀使簇首能量消耗较高，UCRA算法基于加权的非均匀分簇相对减少了簇头的能量消耗，改进算法在UCRA算法的基础上采用簇头选举方法和路由规则，更有效地降低了簇头能量消耗。

3.5 基站接收数据量

图7为算法稳定期结束网络中产生第1个死亡节点时，基站在4次运行时的接收数据量。仿真结果显示，改进算法的数据传输量比EEUC算法和UCRA算法分别提高了约20%和10%，表明了改进算法采用信息熵进行数据融合提高了数据的融合效率，使算法在数据传输方面具有优越性。

4 结 语

提出了基于PSO算法的信息熵数据融合非均匀分簇路由算法。算法主要分为基于粒子群优化选举簇头的非均匀分簇阶段;单跳多跳结合的路由通信阶段;基于节点信息熵的数据融合阶段。对簇头选举和非均匀分簇的优化均衡网络的能量消耗进行改进，有效改善了“热区”问题。仿真结果表明，该算法有效地延长了网络稳定期和生命周期，减少了网络中节点能量消耗，并体现了数据传输的优越性。本文的不足之处是在基于节点信息熵进行数据融合阶段的复杂度过高，在今后的工作中将主要对其进行研究改进，进一步提高数据的融合效率。

参考文献/References：

[1]孙利民. 无线传感器网络[M]. 北京： 清华大学出版社，2005.

[2]HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]// Proceedings of the 33rd Hawaii International Conference on System Sciences.[S.l.]：[s.n.]，2000：3005-3014.

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

LU Xianling， WANG Yingying， WANG Hongbin， et al.Energy-balanced unequal clustering algorithm in wireless sensor network[J].Computer Science，2013，40（5）：78-81.

[4]MHATRE V， ROSENBERG C. Design guidelines for wireless sensor networks： Communication， clustering and aggregation[J].Ad Hoc Networks，2004，2（1）：45-63.

[5]潘繼强，冯永政.改进LEACH的传感器网络分簇路由算法[J]吉林大学学报（理学版），2018，56（6）：1476-1482.

PAN Jiqiang， FENG Yongzheng. Improved LEACH clustering

routing algorithm of sensor network[J].Journal of Jinlin University

（Science Edition）， 2018，56（6）：1476-1482.

[6]SINHA A， LOBIYAL D K. An entropic approach to data aggregati

on with divergence measure based clustering in sensor network[J].

Advances in Computing and Communications，2011，192（7）：132-142.

[7]张瑞华，贾智平，程合友.基于非均匀分簇和最小能耗的无线传感网络路由算法[J].上海交通大学学报，2012，46（11）：1774-1778.

ZHANG Ruihua，JIA Zhiping，CHENG Heyou. The routing algorithm for WSNs based on unequal clustering and minimum energy consumption[J].Journal of Shanghai Jiaotong University，

2012，46（11）：1774-1778.

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

JIANG Changjiang， SHI Weiren， TANG Xianlun， et al. Energy-

balanced unequal clustering routing protocol for wireless sensor networks[J].Journal of Software，2012，23（5）：1222-1232.

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

HOU Hua， LIU Chao， ZHOU Wuyang. Design of a clustering and dynamic routing based on energy efficient and balanced[J].Journal of Beijing University of Posts and Tele-communications，

2013，36（3）：54-59.

[10]徐晶晶，张欣慧，许必宵，等.无线传感器网络分簇算法综述[J].计算机科学，2017，44（2）：31-37.

XU Jingjing，ZHANG Xinhui，XU Bixiao，et al. Survey of clustering algorithms for wireless sensor networks[J].Computer Science，2017，44（2）：31-37.

[11]邹杰，史长琼，姬文燕. 基于粒子群优化的非均匀分簇路由算法[J].计算机应用，2012，32（1）：131-133.

ZOU Jie， SHI Changqiong， JI Wenyan. Uneven clustering routing

algorithm based on particle swarm optimization[J].Journal of

Computer Applications，2012，32（1）：131-133.

[12]MAO Song， ZHAO Chenlin， ZHOU Zheng， et al. An improved fuzzy unequal clustering algorithm for wireless sensor network[J].

Mobile Networks and Applications，2013，18（2）：206-214.

[13]尚静，董增寿，康琳.基于非均匀分环与最小通信代价的路由算法[J].传感技术学报，2018，31（3）：449-455.

SHANG Jing， DONG Zengshou， KANG Lin. A routing algorithm based on unequal ring and minimum communication cost[J].Chinese Journal of Sensors and Actuators， 2018，31（3）：449-455.

[14]刘雅娜，黄战华.负载均衡的高效传感器网络非均匀路由算法[J].计算机工程与设计，2018，39（6）：1546-1552.

LIU Yana， HUANG Zhanhua. High efficiency non-uniformed load-balanced routing algorithm of WSN[J]. Computer Engineering and Design，2018，39（6）：1546-1552.

[15]LEE S，CHOE H， PARK B， et al. LUCA： An energy-efficient unequal clustering algorithm using location information for wireless sensor networks[J].Wireless Personal Communications，2011，56（4）：715-731.

[16]BAGCI H， ADNAN Y. An energy aware fuzzy approach to unequal clustering in wireless sensor networks[J].Applied Soft Computing，2013，13（4）：1741-1749.