近邻传播聚类无线传感器网络分簇路由算法

黄建清，王卫星，胡月明，雷 刚，欧国成，4

（1.华南农业大学 工程学院，广东 广州510642；2.海南大学 应用科技学院，海南 儋州571737；3.华南农业大学 信息学院，广东 广州510642；4.罗定职业技术学院 电子信息系，广东 罗定527200）

0 引 言

无线传感器网络中节点具有分布区域广、数量大、能量有限等特点，因此，其通常采用普通干电池供电，节点的能量难以及时补充，如何高效地使用能量是传感器网络的研究重点［1］，其中，路由算法对于降低节点能量消耗、延长网络生命周期具有重要作用，已成为学术界的研究热点［2，3］。

路由算法分为分簇路由算法和平面路由算法，分簇路由算法具有简单的拓扑管理机制、高效的能量利用效率、全面的数据融合规则等优点，更适合用于无线传感器网络［4］。经典的分簇路由算法LEACH 以循环随机选择簇头的方式，将网络总能量负载均分到每个各传感器节点中，进一步降低网络各节点能量消耗，整个网络生命周期得以延长。而LEACH 算法并未考虑网络中节点状态和网络的拓扑结构，容易产生一些较差的分簇方案。同时，每一轮都要重新组织簇类，簇头开销较大［5，6］。针对LEACH 算法的不足，国内外研究学者研究出许多改进算法，如DCHS算法将能量因素考虑进来，使剩余能量较多的节点优先当选簇头，但DCHS算法并未考虑传感器网络节点随机分布、簇头分布不均匀的问题［7］。LEACH－CLUSTER 算法采用K－means聚类算法将传感器网络静态分簇，以产生最优的分簇结构［8］，但采用K－means聚类算法对初始值很敏感，易陷入局部极小点而不能准确求出整体最优解。本文提出一种近邻传播聚类的分簇路由算法 （affinity propagation clustering routing algorithm，APCRA），通过近邻传播聚类算法将传感器网络优化分簇，使聚类结果更稳定，簇结构更均匀，进一步综合考虑各节点剩余能量和被选簇头节点至簇内其他节点的平均距离。

1 近邻传播AP算法

近邻传播AP算法是一种非常有效的基于划分的聚类方法，它将所有数据点都作为潜在的聚类中心，以数据点之间的相似度关系矩阵为基础，通过迭代过程中数据点间信息的传递，寻找最优的类代表点集合，使网络能量函数达到 最小 化［9－11］。

假设数据集X ＝｛x1，x2，…xn｝，数据点相似度矩阵S＝［s（i，j）］n×n，其中，s i，（ ）j 表示点xi和xj的相似度，偏向参数P 表示每个点成为聚类中心的可能程度，s i，（ ）j 和P的计算公式如下

式中：θ——调整参数，0＜θ＜1。数据点之间的信息由吸引度矩阵R ＝［r（i，j）］n×n和归属度矩阵A ＝［a（i，j）］n×n来表示，其中，r i，（ ）j 表示点xj适合作为xi的聚类代表的程度，a i，（ ）j 表示点xi选择xj作为其聚类代表的程度，r i，（ ）j 和a i，（ ）j 的计算公式如下

式中：t——迭代次数。在每次迭代过程中R 和A 矩阵都会不断更新，迭代结束后，通过判断决策矩阵E＝R＋A 中E（k，k）＞0来确定聚类中心，普通节点根据与聚类中心相似度最大划分到相应的聚类中。另外，为了消除迭代过程中发生的震荡，在迭代过程中引入阻尼因子λ ∈ 0，［ ）1 对r i，（ ）j 和a i，（ ）j 值进行修正，修正值为当前迭代值与上一步值的加权和，加权公式为

2 基于AP聚类的分簇路由算法

2.1 算法思想

汇聚节点根据节点的密集程度和最优簇类数，利用AP算法将传感器网络划分成优化的簇结构，划分好的簇结构在整个网络生命周期内固定不变，以减少频繁组簇的能量消耗。簇头选择时综合考虑各节点剩余能量和被选簇头节点至簇内其他节点的平均距离，选择网络中节点能量剩余多和与簇内其它节点通信代价较小的节点担任簇头，降低节点能量消耗。

APCRA 算法分为3个阶段，簇区划分、簇建立和数据传输。簇区划分阶段由汇聚节点采用AP 算法将传感器网络划分，在簇建立阶段和数据传输阶段之前完成。簇建立阶段和数据传输阶段采用轮的方式运行，每一轮簇建立阶段完成簇头选择和TDMA 时隙表建立两部分。数据传输阶段完成成员节点数据发送、簇头融合成员节点数据并发送数据到汇聚节点。

2.2 簇区域划分

在首轮运行前，每个节点将自己的位置信息和ID 号发送给汇聚节点，汇聚节点根据节点的位置信息，利用AP算法将整个网络划分为最优簇头数个区域，并且每个节点隶属于一个簇，然后汇聚节点为每个簇区域选择聚类中心作为初始簇头，并将分簇结构的信息广播至每个节点。这样，在首轮运行前每个节点通过一次与汇聚节点的交互后获得了分簇结构信息，在接下来每轮运行中，这个分簇结构固定不变，以减少频繁组簇的能量消耗。簇区域划分流程如图1所示，具体的工作过程如下：

步骤1 每个节点发送自己的位置信息和ID 号给汇聚节点；

步骤2 汇聚节点计算最优的簇头数目mopt，计算公式如下［12］

式中：n——网络中 节点个 数，L——网 络 区 域 边 长，εfs——自由空间传输模式下，信道衰减放大指数，εmp——多径传播模式下，信道衰减放大指数，dtobs——汇聚节点到簇头节点的距离。

步骤3 设置调整参数θ、最大迭代次数tmax和稳定次

图1 簇区域划分流程

数tsmax的值，根据式 （1）、式 （2）计算相似度矩阵S和偏向参数P ；

步骤4 设置迭代次数t＝1，稳定次数ts＝0，初始化R 和A 为全0阵；

步骤5 根据式 （3）、式 （4）计算吸引度矩阵R 归属度矩阵A；

步骤6 根据式 （5）、式 （6）修正吸引度矩阵R 和归属度矩阵A；

步骤7 计算决策矩阵E，生成聚类中心集合cluster，然后将cluster与cluster0比较，若相等，稳定次数ts＝ts＋1，否则，ts＝0，cluster0＝cluster；

步骤8 迭代次数t加1，重复步骤5～步骤8，直至t＝tmax，或在ts＝tsmax时聚类中心不变为止；

步骤9 输出聚类数，如果达到最优的簇头数，转到步骤10，否则调整θ值，转到步骤4重新迭代；

步骤10 生成分簇结构，每个簇的聚类中心为初始簇头；

步骤11 汇聚节点向每个节点发送分簇结构信息，包括节点所在的簇区域号、簇内各节点的位置信息和簇头节点ID 号。

2.3 簇建立阶段

在网络中，簇头要承担更多的通信任务，消耗更多的能量，因此，簇头选择采取轮换的方法，使能量消耗分散在簇内区域的各节点上，避免单一节点快速失效。在首轮运行前，汇聚节点为每个簇指定初始簇头，接下来各轮的簇头由前一轮簇头指定。在每一轮运行中，当成员节点将采集数据发送至簇头时，同时也附带了自己的剩余能量信息，各成员节点的数据发送完毕后，簇头计算它们的剩余能量和至簇内其他节点平均距离的加权值，选择权值较大的节点成为下一轮的簇头。假设L×L 区域的网络分成m个簇，簇 集 合V ＝ ｛V（1），…，V（i），…，V（m）｝ ，其中簇V（i）＝ ｛xj｜j＝1，2，…，Ni｝，则V（i）中xj节点担任簇头的权值为

前一轮簇头根据簇内成员节点当选簇头的权值大小来选择下一轮簇头，然后向簇内成员节点发送新簇头产生消息，消息内容为新簇头的ID 号，然后转入成员节点状态，收到这个消息的成员节点根据自己的ID 号判断是否当选为新簇头，若当选，则建立TDMA 时隙表并发送给成员节点，然后进入数据传输阶段；若未当选，则接收新簇头发送时隙表信息后，进入数据传输阶段。

2.4 数据传输阶段

数据传输阶段包括成员节点数据发送、簇头数据融合以及簇头与汇聚节点间数据传输。为减少能量开销，各成员节点仅在各自时隙内打开其无线发送模块，将采集的数据发送给本簇的簇头，其它时隙内均处于睡眠状态。另外，成员节点发送的数据包含有它的剩余能量信息，使簇头能够感知本簇所有成员节点的剩余能量，从而在下一轮簇头选择时可以产生出新簇头。簇头必需在整个TDMA 时隙内打开无线接收模块，以保证能接收到本簇所有成员节点发送的数据，然后对接收数据进行融合并发送到汇聚节点，发送完后进入下一轮选择新簇头，开始新一轮工作。

3 能量模型

网络能量损耗是指网络中所有节点能量损耗的总和，采用无线电能量损耗模型来度量网络中各节点能量损耗［13］。当节点发送k bit数据至距离为d的节点时，所消耗的能量为

当节点接收k bit数据所消耗的能量为

式中：Eelec——接收电路的能耗，EDA——数据融合的能耗，即融合1bit数据消耗的能量。

4 仿真分析

4.1 仿真环境与参数设置

采用Matlab 对APCRA 算法进行仿真，同时对比LEACH、DCHS算法和LEACH－CLUSTER 算法，比较四种算法的分簇结构、网络生命周期和网络总能耗的性能。仿真参数设置如下：在200m×200m 场景中随机布置100个节点，汇聚节点位于 （100，280），传感器节点的初始能量E0＝0.5J，发送或接收电路的消耗能量Eelec＝0.5nJ／bit，自由空间模型放大倍数εfs＝10pJ／b／m2，多路径衰减模型放大倍数εmp＝0.0013pJ／b／m4，数据融合的消耗能量EDA＝5nJ／bit，数据包长度4000bit，控制包长度100bit。

根据场景中节点的分布情况，可计算出簇头与汇聚节点的距离为80!dtobs!297，所以由式 （7）得到最优簇头个数为0＜mopt＜11，本文选取mopt＝7。

4.2 仿真结果分析

图2为4种算法的网络分簇结构图，其中，·表示簇头，其它形状表示簇内成员节点。从图2 中可以看出，LEACH 和DCHS算法随机分簇，不能产生最优簇头数的分簇结构，分簇结构较差。LEACH－CLUSTE、APCRA 算法能产生最优簇头数的分簇结构，分簇结构和簇头在网络中的分布都很均匀。采用最大簇内距离方差max C｛ ｝i 作为评价分簇结构的指标［14］，选择最小的最大簇内距离方差min max ｛Ci｝作为最优的分簇结构，其中Ci为第i 个簇的簇内距离方差，定义为

式中：n——第i个簇中节点的个数，dj——第i个簇中第j个成员节点与簇头的距离。经计算，LEACH、DCHS、LEACH－CLUSTE、APCRA 算法最大簇内距离方差分别为1215.1、1220、516.05、295.19，APCRA 算法最大簇内距离方差最小，为最优的分簇方案。

图3和图4为4种算法的网络生命周期图和生命周期柱状图，从图中可以看出，APCRA 算法生命周期最长，其中，第1个节点死亡时间，APCRA 算法为216轮，分别比LEACH （143 轮）、DCHS （159 轮）、LEACH－CLUSTE（108轮）延长了51%、36%、100%；半数节点死亡时间，APCRA 算法为639轮，分别比LEACH （456轮）、DCHS（379 轮）、LEACH－CLUSTE （569 轮）延 长 了40%、69%、12%；全部节点死亡时间，APCRA 算法为968 轮，分别 比LEACH （783 轮）、DCHS （868 轮）、LEACHCLUSTE （873轮）延长了24%、12%、11%。仿真结果表明，APCRA 算法能更有效地均衡簇内能量损耗，延长了网络的生命周期。

图5为4种算法的网络总能量变化图。图5 中，当网络运行200 轮时，APCRA 算法网络总能量还有28.457J，分别比LEACH、DCHS、LEACH－CLUSTE算法多5.52J、5.68J、1.18J；当网络运行783轮时，LEACH 算法生命周期已结束，网络总能量耗尽，此时APCRA 算法网络总能量剩余最多，为2.104J，而DCHS、LEACH－CLUSTE 算法网络总能量只有0.038J、1.81J；当网络运行900轮时，DCHS、LEACH－CLUSTE算法生命周期均已结束，而APCRA 算法网络总能量还有0.559J。仿真结果表明，APCRA 算法的网络总能量消耗均低于LEACH、DCHS、LEACH－CLUSTE算法，这是因为APCRA 采用AP聚类算法能产生最优的分簇结构，使簇头节点在网络中分布均匀而减少了能耗损失，同时采用静态固定分簇策略，不需要每一轮重新组织簇类，减少了频繁组簇的能量消耗。并且簇头选取时综合考虑了节点的剩余能量和至簇内其他节点距离，从而可以均衡节点的能耗和减少簇内通信消耗。

图5 网络总能耗

5 结束语

为解决传统无线传感器网络路由算法在分簇上存在不均匀分簇问题，提出了一种近邻传播聚类的分簇路由算法。该算法利用近邻传播聚类算法产生最优的分簇结构，同时采用静态固定分簇策略，减少了频繁组簇引发的能耗。选择簇头时综合考虑网络中各节点的剩余能量以及节点至簇内其他节点的平均距离权值的选择机制，均衡节点的能耗和减少了簇内通信消耗。该算法相比LEACH、DCHS、LEACH－CLUSTE在分簇结构、网络生命周期、网络总能量消耗等方面都有显著提高。

［1］Willig A.Wireless sensor networks：Concept，challenges and approaches［J］.Elektrotechnik ＆Informationstechnik，2006，123 （6）：224－231.

［2］Zabin F，Misra S，Woungang I，et al.REEP：Data－centric，energy－efficient and reliable routing protocol for wireless sensor networks［J］.IET Communications，2008，2 （8）：995－1008.

［3］Zhou G，He T，Krishnamurthy S，et al.Models and solutions for radio irregularity in wireless sensor networks ［J］.ACM Transactions on Sensor Networks，2006 （2）：221－262.

［4］ZHOU Yue，LI Gang，GAO Yu，et al.Cluster－head selection method based on node's density for wireless senosr networks［J］.Journal of Shenyang Jianzhu University （Natural Science），2008，24 （3）：499－502（in Chinese）.［周悦，李钢，高宇，等.基于节点密度的无线传感器网络簇首选取机制 ［J］.沈阳建筑大学学报 （自然科学版），2008，24 （3）：499－502.］

［5］WANG Zhigang.The research on cluster－based routing protocols for wireless sensor networks［D］.Wuhan：Wuhan University of Technology，2009：28－31（in Chinese）.［王志刚.无线传感器网络分簇路由协议的研究 ［D］.武汉：武汉理工大学，

2009：28－31.］

［6］Kim J，Park S，Han Y，et al.CHEF：Cluster head election mechanism using fuzzy logic in wireless sensor networks［C］／／The 10th International Conference on Advanced Communication Technology.Korea：IEEE，2008：654－659.

［7］Yuhua L，Jingju G，Yongcan J，et al.A cluster maintenance algorithm based on LEACH－DCHS protocol［C］／／IEEE International Conference on Networking，Architecture and Storage，2008：165－166.

［8］XIA Xinfeng.Research of hierarchical routing protocol based on clustering in wireless sensor networks ［D］.Nanjing：Nanjing Normal University，2008：21－29（in Chinese）.［夏心锋.无线传感器网络中基于聚类的层次路由协议研究 ［D］.南京：南京师范大学，2008：21－29.］

［9］Frey B J，Dueck D.Clustering by passing messages between data points［J］.Science，2007，315 （5814）：972－976.

［10］Frey B J，Dueck D.Response to comment on“Clustering by passing messages between data points” ［J］.Science，2008，319 （5864）：726.

［11］XIAO Yu，YU Jian.Semi－supervised clustering based on affinity propagation algorithm ［J］.Journal of Software，2008，19 （11）：2803－2813（in Chinese）.［肖宇，于剑.基于近邻传播算法的半监督聚类［J］.软件学报，2008，19 （11）：2803－2813.］

［12］Kumar D，Aseri T C，Patel R B.EEHC：Energy efficient heterogeneous clustered scheme for wireless sensor networks［J］.Computer Communications，2009，32 （4）：662－667.

［13］Ran G，Zhang H，Gong S.Improving on LEACH protocol of wireless sensor networks using fuzzy logic［J］.Journal of Information ＆Computational Science，2010，7 （3）：767－775.

［14］YANG Haibo，HUA Jiangyu，LIU Banteng.Research on clustering routing algorithm for wireless sensor networks based on the improved subtractive clustering algorithm ［J］.Chinese Journal of Sensors and Actuators，2012，25 （11）：1603－1606（in Chinese）.［杨海波，华惊宇，刘半藤.基于减聚类优化算法的无线传感网络分簇路由协议研究 ［J］.传感技术学报，2012，25 （11）：1603－1606.］