基于改进近邻传播算法的无线传感网分簇与节能

卫岚宁 林 海 王 磊

(武汉大学国际软件学院 湖北 武汉 430000)

0 引 言

无线传感器网络WSN由一定量具有感知、计算和无线通信能力的节点组成，这些传感器采集周围的数据，并将信息发送给基站。节点具有一定的能量，信息的采集、计算，通信侦听，发送都需要消耗能量，能量耗尽则节点死亡，对数据采集有很大的影响。因此无线传感网的节能控制一直是无线传感网的核心问题[1]。

网络层的路由技术在无线传感网中起着关键作用，从网络拓扑结构的角度可将其分为平面路由和分簇路由两种[2]。

在分簇路由中：网络被划分成簇，每个簇都有自己的簇头和多个普通成员。低一级网络的簇头是高一级网络中的簇内成员，由最高层的簇头与基站BS通信[2]。

聚类过程大致分为三个阶段：簇头的产生、簇的形成和稳定运行阶段。簇头应该尽可能在簇的中央以提高簇的内聚度，相邻簇之间的覆盖应该尽可能小以减小簇的耦合度。LEACH( Low Energy Adaptive Clustering Hierarchy)协议[3]假设所有的节点之间都可以相互通信，通过一定的概率来随机循环产生簇头，其余的非簇头节点选择一个最近的簇头，加入该簇。分布式的LEACH有利于网络的扩展，但是这种随机选举簇头的方式会导致簇的结构不合理，簇头分布不均，并且没有考虑到能量因素，簇头很快就会死亡。LEACH-C[3]是集中式的LEACH算法，由基站指定能量较高节点作为簇头。这种方式保证簇头节点不会过快死亡，但是仍是要求节点之间可以直接通信。

HEED(A Hybrid Energy-Efficient Distributed Clustering Approach)协议[4]是可用于大型异构分布式网络的算法，针对LEACH算法簇头分布不均的问题进行了改良。算法有两个参数[5]：参数AMRP是簇内成员节点和簇头通信消耗的平均能量；参数CHprob的值和节点自身能量有关，能量高的节点CHprob值也大，成为临时簇头的可能性也更大，簇重叠区域的节点根据AMRP值选择簇加入。

CPAP(Clustering Based on P-Changed Affinity Propagation)[2]算法中提出修改参考度p来使网络达到预计的最优簇头数目。每次信息采集完后由基站重新规划新的簇，但是新簇的能量开销太大，且文中并未明确指出选举间隔。APCRA(Affinity Propagation Clustering Routing Algorithm)算法[6]中提出，由基站规划初始簇和簇头，随后每次新的簇头由上一任簇头根据节点的剩余能量和位置决定。这种方法减小了新簇产生时的开销，但是文中采用的是小型网络，节点之间通信没有距离限制，不适用于大型网络。

基于上述问题，本文在原始AP算法的基础上提出新的改进方法 EAPCP。针对大型网络，对分簇方法进行优化，提高网络能量利用率；针对网络中通信距离的限制，对AP算法中的数据交换对象进行筛选；对参考度p进行修改，综合考虑网络整体的能耗、节点的剩余能量、节点的分布情况和最优簇头数的大小，并计算分簇完成后网络稳定运行轮数。

1 AP算法

近邻传播聚类算法[7]AP(Affinity Propagation)于2007年由Frey等在《Science》上提出，该算法一经提出一直受到各个研究领域的广泛关注，特别是在无线传感网领域有着很大的研究价值。

AP算法是一种聚类算法，其本质是一种基于因子图的信念传播和最大化算法[8]，最初是用于数据挖掘和统计。和其他需要指定初始簇头并进行优化的聚类算法不同[9]，AP算法不需要事先指定聚类数目，而是将所有的数据点都作为潜在的聚类中心。

假设有x1到xn，n个数据节点，节点之间的结构是随机的，定义S(i,k)为节点xi和节点xk之间的相似度并且S的值由节点之间的欧氏距离决定，即S(i,k)=-‖xi-xk‖2，所有节点之间的S值可以构成一个矩阵，称为相似矩阵。

矩阵对角线上的值S(i,i)表示的是一个节点成为簇头的可能性，也称为参考度p，p值越大，表明该节点成为簇头的可能性越大。p值决定了簇的数目，p值越大，簇的数目越多，一般p值取所有节点之间相似度的平均值。

算法的运行主要包括传递两种类型的消息来更新两个矩阵：

1) 由r消息(responsibility)构成的R矩阵：r(i,k)表示候选节点xk作为节点xi的簇头的合适程度。

2) 由a消息(availability)构成的A矩阵：a(i,k)表示节点xi选候选节点xk作为它的簇头的合适程度。

两个矩阵初始值都为0，算法更新过程如下：

1) 首先，节点之间更新交换r消息：

(1)

2) 然后根据r消息来更新交换a消息：

(2)

3) 对矩阵A和R进行迭代，直到两个矩阵的数值保持不变或者达到指定的迭代次数，迭代过程更新公式如下：

Ri=(1-λ)Ri+λRi-1

(3)

Ai=(1-λ)Ai+λAi-1

(4)

4) 根据a(k,k)+r(k,k)的值选出簇头，非簇头节点选择最近的簇头，加入该簇。

2 EAPCP算法

2.1 优化简介

原始的AP算法中只是一种聚类算法，无线传感网中节点有通信距离和能量的限制，所以对原始的AP算法做了改进。

1) 基于能量的簇头选择：p值体现了节点成为簇头的能力，通过调整p值选择一个能量较高的节点作为簇头，这样能够有效延长网络寿命。

2) 最优簇数目的选择：分簇结果的好坏关系到网络寿命，选择一个合理的簇的个数能够有效延长网络寿命。LEACH中簇头可以直接和基站通信，在大型网络中簇头通过簇间路由将数据包发送至基站，基于此优化LEACH中提出的最优簇个数算法。

3) 稳定运行轮数的计算：聚类的第三部分是稳定运行阶段，簇建立阶段和稳定运行阶段所持续的时间总和为一个周期，网络需要定期重新选举以保证节点不会很快死亡。为了减少协议开销，稳定运行阶段的持续时间要比选举过程长。根据当前簇头的能耗计算网络此次的稳定运行轮数，合理利用节点能量。

4)a、r消息的改进：原始的a、r消息需要计算本节点和其他所有节点之间的数值，但是在传感网中节点有通信距离限制，消息只是在邻居之间传播，因此将之优化为：

(5)

(6)

式中：用N(i)表示i的邻居集合。

2.2 基于能量的簇头选择

参考度p体现了节点成为簇头的能力，在原始的AP算法中，参考度p的取值通常为S矩阵的均值，并且所有节点都相同，这就表明所有节点成为簇头的能力相同。但是在无线传感网中，通常选择能量较高的节点作为簇头，这样能延长网络寿命。因此将能量因素加入其中，同时考虑网络的密度，选取的簇头数达预计最优，减少网络能耗。其中：

(7)

S(i,i)=pi

(8)

(9)

2.3 最优簇数目的选择

簇个数对网络能量消耗有很重要的作用，簇数太多会导致数据融合效率低，冗余数据消耗能量；簇数目过少则簇内成员过多，簇头接收数据包消耗的能量也增多，能量消耗快容易导致网络提前崩溃。

簇内的成员只需要将采集的信息发送给簇头，簇头整合后发送给汇聚节点(Sink)。

假定在M×M区域内均匀分布N个节点，网络的最优簇头数为Kopt，用Heinzelman提出的一阶无线通信模型[3]来模拟节点通信。则整个网络的能量消耗为：

(10)

式中：l是数据包的长度，Eelec是收发1 bit数据消耗的能量，EDA是数据融合时消耗的能量，k是簇个数,dCH-CH表示的是两个簇头间的平均距离,dtoCH是簇内成员到簇头的平均距离，Rc表示簇内通信距离，Rr表示簇间通信距离。因为节点是均匀分布的，所以：

(11)

将式(11)代入式(10)，对k求偏导数，并令该偏导数为零，则最优簇头数Kopt：

(12)

因为簇头间的距离必须小于簇间通信范围，即dCH-CH2Rc，那么可以得到：

2Rc

(13)

根据式(13)可以求得最优簇头数Kopt的范围，但是这个范围很大，需要进行进一步的缩小。

簇内通信距离Rc有一定限制，假定簇形成的圆之间均不重合，为了保证所有的节点都能分到簇内，Kopt需要满足：

(14)

结合式(13)、式(14)可以进一步缩小Kopt的范围，在此范围内进行进一步的筛选，即可得出网络的最优簇头数。

2.4 簇的稳定运行轮数

无线传感网中应当尽可能延长节点的使用时间，使节点尽可能在同一时间死亡，尽可能的将网络消耗的能量平摊到每个节点身上。节点有两种状态，一种是簇头状态，另一种是非簇头状态。两种状态下消耗的所有的能量就是节点的初始能量。

假定节点当前剩余能量为Ei，节点成为簇头时每轮消耗的能量为ECH,节点不是簇头时，每轮消耗的能量是EnonCH。从当前状态一直到节点死亡，节点作为簇头会运行m轮，作为非簇头会运行n轮，则：

mECH+nEnonCH=Ei

(15)

网络的预期运行轮数是m+n，每轮预期的簇头数是k，则共需(m+n)×k个簇头，均分到每个节点身上则每个节点成为簇头的轮数m应当为：

(16)

由式(15)，式(16)得到了m的预估值：

(17)

因为每次分簇的结果不同，每个节点的ECH和EnonCH值会和上次分簇结果中的数值有偏差。

如果根据某一次的分簇结果确定了m的值，并且在之后的过程中不再改变，那么将无法达到最优的情况，节点无法合理利用。在每次分簇完之后，根据式(17)计算本次的稳定运行轮数，只有这样才能更好地利用和分配能量。

2.5 算法运行过程

(1) 设置S矩阵。计算任意两点之间的S(i,j)。

(2) 计算参数z。根据式(12)-式(14)计算Kopt的范围，调整z使簇数目在这个范围之内，在所有符合条件的z中选择一个使网络能耗最小的z。具体的数据见3.1节。

(3) 根据式(7)、式(8)计算S矩阵的对角线值。

(4) 根据式(5)、式(6)计算r矩阵和a矩阵。

(5) 迭代产生新的簇。根据式(3)、式(4)进行迭代直到数值不再发生改变，此时新一轮的簇已经形成。

(6) 计算本次稳定运行轮数m。根据当前网络能量情况选举出新的簇，根据式(17)得到簇的稳定运行轮数m；根据文献[1]的数据，HEED的稳定运行轮数设为60轮。

(7) 稳定运行。在AP算法运行m轮之后，重新进行步骤(4)-步骤(6)，直至计算中网络死亡。

(8) 信息分发。通过平面路由，sink将每次分簇时步骤(5)中簇的信息和步骤(6)中m信息整合为一个数据包，通过平面路由的方式路由给每个节点。

3 仿真及分析

在MATLAB平台上进行仿真，模拟一个300 m×300 m的一个区域，内有1 000个节点随机分布。假定基站在该区域的中心，在一轮的运行中，节点将数据包发送给簇头，簇头整合之后路由给基站。

将改进的AP算法与HEED算法进行对比，忽略无用侦听、数据包丢失、形成簇头时交换的数据包，具体参数如表1所示。

表1 仿真参数

3.1 调整参数z

由式(12)-式(14)得最优簇数目是452时，簇头数稳定在60左右，且一轮的能量消耗基本相同，故本文取z=2.5来计算。

图1 参数z的选择

3.2 性能分析

性能分析基于六个标准：分簇的情况、存活节点数量、网络剩余能量、每轮网络的消耗能量、选举过程能耗,网络规模。

(1) 网络成簇比较 取一次成簇结果进行比较，如图2、图3所示，可见EAPCP的簇头数较少，且簇的内聚度高，耦合度低，簇头都在簇的中央位置。而HEED的分簇结果并不如EAPCP理想，簇间耦合度较高，且簇头位置并不如前者选择的恰当，说明单从分簇结果上EAPCP算法的分簇方法还是优于HEED算法。

图2 EAPCP某轮成簇图

图3 HEED某轮成簇图

(2) 存活节点数量 在无线传感器网络中，第一个死亡节点出现的时间是衡量网络寿命的一个重要参数，为了提高网络性能，应该尽量推迟第一个死亡节点出现的时间[10]，要使所有节点接近同时死亡。

如图4所示，经测试，在给定的条件下，EAPCP算法在3 000轮时候出现第一个死亡节点，此时网络的能量消耗了72%，在4 600轮时全部节点能量耗尽。HEED算法800轮左右出现第一个死亡节点，1 500轮时一半的节点死亡，证明EAPCP算法可以有效地推迟节点的死亡时间出现。

图4 两种算法存活节点数量比较

(3) 每轮能量消耗 每轮能量消耗体现的是分簇结果的好坏，分簇合理时，每轮能耗自然会比较小，大型网络的每轮能耗比小型网络每轮能耗大。由于HEED算法选举簇时需要消耗能量，此处计算的每轮能耗只考虑簇形成之后传输数据包的能耗，不考虑簇形成的能耗。

如图5所示，在1 500轮之前，HEED的每轮能耗要比EAPCP大很多，说明EAPCP算法在分簇上更优。在1 500轮之后因为HEED算法中节点死亡过半而能耗减少，EAPCP算法中节点尚未死亡，自然能耗要比HEED大。

图5 两种算法每轮能量消耗比较

(4) 剩余能量 网络剩余能量体现的是网络能量消耗的速度，不同于分析(3)，这条分析是把HEED中选举簇头的能量也考虑在内。如图6所示，因为分簇结果不佳，HEED前期网络能耗增加，曲线斜率很大，1 500轮之后因为网络规模减小，消耗能量少，斜率降低。EAPCP算法在前3 000轮每轮能耗基本相同，因此曲线趋于一条直线。3 000轮之后因为节点数目减小，每轮能耗降低，因此曲线的斜率逐渐下降。在3 800轮左右两个网络的剩余能量相同，因为EAPCP算法始终以稳定的较低的能量运行，而HEED算法先是因分簇效果不佳而能耗高，后因节点数量少而较低，因而两者会在此处能量相同。

图6 两种算法网络剩余能量比较

(5) 选举能量消耗比较 HEED利用节点间相互通信选举生成每轮的簇，整个网络选举时消耗的能量是150 J，EAPAP算法第8步中消耗的能量是2.970 4 J，由此可见， 集中式的EAPCP算法要比分布式的HEED算法要好。

(6) 不同网络规模比较 HEED算法随着网络规模的扩大，簇的个数无法控制，过多的簇导致信息采集效率不高，能量利用率低，网络的死亡时间不断推前。如图7所示。

图7 不同网络规模下两种算法的比较

4 结 语

本文提出了一种考虑能量的改进近邻传播聚类算法，并且给出了簇选定之后的稳定运行轮数的计算方法。经仿真检测，该算法在以上两个方面具有较好的性能。尽管在分簇时考虑了能量因素，但是最终的簇内，簇头的能量可能仍然偏低，如何在成簇之后综合考虑簇头位置和簇的能量，对簇头节点进行调整，将是下一步的工作。

参 考 文 献

[1] Lin Hai,Wang Lusheng,Kong Ruoshan.Energy efficient clustering protocol for large-scale sensor networks[J].IEEE Sensors Journal,2015,15(12):7150-7160.

[2] 钟伟民,王月琴,梁毅,等.基于改进近邻传播聚类的异构无线传感器网络分簇算法[J].江南大学学报:自然科学版,2012,11 (4):423-427.

[3] 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.

[4] Younis O,Fahmy S.HEED:A Hybrid, energy-efficient,distributed clustering approach for Ad Hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4):366-379.

[5] 尹安,汪秉文,戴志诚,等.无线传感器网络HEED分簇协议的研究与改进[J].小型微型计算机系统,2010,31(10):2002-2006.

[6] 黄建清,王卫星,胡月明,等.近邻传播聚类无线传感器网络分簇路由算法[J].计算机工程与设计,2014,35(2):406-410.

[7] Fery B J,Dueck D.Clustering by passing messages between data points[J].Science,2007,315(5814):972-976.

[8] 甘月松,陈秀宏,陈晓晖.一种AP算法的改进:M-AP聚类算法[J].计算机科学,2015,42(1):232-235.

[9] 朱兰,张晓焱.基于近邻传播算法的K-means聚类优化算法[J].信息技术与信息化,2015(2):138-142.

[10] 陈静,张晓敏.无线传感器网络簇头优化分簇算法及其性能仿真[J].计算机应用,2006,26(12):2787-2788.