基于模糊理论的无线传感器网络簇首选举算法

陶志勇，蒋守凤

（辽宁工程技术大学a.电子与信息工程学院；b.研究生学院，辽宁葫芦岛125105）

·移动互联与通信技术·

基于模糊理论的无线传感器网络簇首选举算法

陶志勇a，蒋守凤b

（辽宁工程技术大学a.电子与信息工程学院；b.研究生学院，辽宁葫芦岛125105）

无线传感器网络中分簇协议算法按轮工作，但多数分簇算法每轮都要进行簇首选举，造成网络节点能量消耗过多，而且占用大量时间。针对该问题，提出基于模糊理论的无线传感器网络簇首选举算法。在网络部署阶段确定簇首竞争半径，保证簇首均匀分布。在簇首选举阶段，通过与簇首竞争半径内节点的通信，构造节点邻域表，采用模糊理论综合评判法生成簇首序列，节点依据序列次序轮流担任簇首。簇建立完成后，簇首采用多跳方式与Sink通信，均衡远近簇首的能耗。仿真结果表明，该算法可降低网络节点的能量消耗，延长网络生存时间。

无线传感器网络；分簇算法；模糊理论；竞争半径；簇首序列；多跳路由

1 概述

无线传感器网络（Wireless Sensor Netw ork，WSN）作为新型的自治测控网络，通过随机部署各类微型传感器来协同感知、采集和处理网络监测区域内的感知数据［1］，最终以多跳方式通过无线自组网将感知到的信息传输至Sink节点。传感器网络执行具体任务时，完成的质量由网络生存时间、网络负载平衡性等网络性能决定。

在无线传感器网络中，分簇路由算法相比平面路由算法具有更好的节能性［2］，基于簇的路由协议是研究的重点。大量的研究表明，分簇路由算法可较大限度地降低网络中的数据通信量、节约节点的能量消耗，是延长网络寿命的有效方法［3］。网络建立时，通过分簇算法将网络划分为逻辑上的若干个簇，每个簇由一个簇首和若干成员节点组成，各成员节点负责采集、处理和向簇首传递数据，簇首负责管理簇内资源分配和簇间的通信［4］。是否合理的簇首选举方法和簇间通信模式能够决定网络的总体性能是否可靠。

本文提出基于模糊理论的无线传感器网络簇首选举算法（Cluster Head election algorithm in WSN Based on Fuzzy Theory，CHBFT）。在网络部署阶段，根据区域面积和网络节点数等确定监测区域最佳簇首个数，再通过公式计算出簇首竞争半径；在簇首选举阶段，构造节点邻域表，利用模糊理论综合评判法选取簇首，并广播其作为簇首的信息；在簇建立阶段，普通节点选择相距最近的簇首加入簇，传输自身ID和评判结果值，由簇首建立一个簇首序列（簇首可选度），簇内节点按照该序列轮流作簇首；最后采用簇首间多跳路由的方法将数据传输至Sink节点，实现簇首与Sink节点的理想通信。

2 相关工作

簇结构在很大程度上影响着网络的性能，因此，对无线传感器网络分簇算法的研究在帮助提高网络整体性能方面有着重要的意义。分簇路由协议思想源于LEACH算法［5］，它的成簇方法贯穿于之后被提出的众多层次路由协议中，很多文献对簇组织问题进行了专门研究，如LEACH-E［6］，TEEN［7］和HEED［8］算法等，以上算法通过对簇首选举的方式进行的改进，实现了簇首在监测区域内的合理、均匀分布。

而后被提出的各种分簇算法在选举簇首时更是将节点剩余能量、节点聚合度及节点地理位置等因素作为参考条件。由于无线传感器网络的规模与拓扑结构的不断变化，网络中各类因素对网络寿命的影响是无法确定的，具有一定的模糊性，那么在分簇过程中节点是否能够胜任簇首这一要职也具有模糊性。事物的模糊性是指边界不清楚，含义在表达时不能明确的区别是和非，在论域上无法划分他的界限。这种模糊性与无线传感器网络分簇算法中多因素制约簇首选举上十分契合［9］，针对于此，本文将模糊聚类的思想应用于WSN分簇算法的研究［10］。

3 CHBFT算法

CHBFT算法与LEACH分簇算法相同，共分为3个阶段：簇首选举，簇建立，簇间通信。而在簇首选举阶段哪些因素作为模糊理论综合评判法的参数是考虑的重点：

（1）剩余能量。

网络节点的剩余能量值是节点能否工作的先决条件，无论是传输数据还是广播信息，都需要消耗节点的存储能量，节点剩余能量多少直接影响着其工作时间的长短。

（2）到Sink节点距离及到邻居节点的距离均值。

由能量消耗模型［11］看出，发送数据的能量消耗与通信节点间距离成反比。通信距离越短，能量消耗则越低，对发送数据的节点具有节省能量的作用；那么无论是到Sink节点的通信距离还是到邻居节点的通信距离，其值越小越有利。

通过以上分析可知，利用模糊理论综合评判法对簇首选举的因素值为：节点剩余能量值，到Sink节点距离倒数值以及到邻居节点距离均值倒数值。

3.1 簇首选举

3.1.1 网络最佳簇首个数及簇首竞争半径

在网络部署阶段，Sink节点用一个特定的发送功率向监测区域广播一个信号，网络中的传感器节点在接收到该信号后，根据接收信号的强度计算它到Sink节点的近似距离dχ-ch（χ为各节点ID编号）。此时可知网络区域边长M、网络节点数目N及区域内节点到Sink节点的最大、最小距离。

根据文献［12］可知，网最优簇首数mK值的计算公式为：

其中，εfs和εamp分别表示信号放大器在自由空间模型和多路衰减模型下将1 bit数据传送单位距离时的能量消耗。通过式（1）可计算出网络最优簇首数目的范围；簇首竞争面积Sch近似为网络总面积与簇首个数的比值，即：

3.1.2 节点信息获取

之后监测区域中节点在簇首竞争半径范围内广播其ID、位置信息、剩余能量及到Sink节点的距离，所有的竞争半径内邻居节点都会收到该信息，建立一个节点邻域表。节点再计算到所有邻居节点的距离及距离均值。节点邻域表如表1所示。

表1 节点邻域表

3.1.3 簇首选举

在簇首选举过程，CHBFT算法采用模糊理论的综合评判法选举簇首，首先要确定各因素的隶属函数，建立隶属度，再与参数权重集加权平均得出簇首可选度。

（1）隶属函数与隶属度

通过分析可知，节点的剩余能量越多、距离Sink节点越近，与邻居节点距离均值越小，越是簇首的最佳选择。本文采用如下隶属函数的计算方式，将各参数归为0～1的数值：

剩余能量的隶属函数为：

其中，R_Ei为节点i的剩余能量；Einit为网络节点的初始能量。

到Sink节点距离倒数的隶属函数为：

其中，di-ch为节点i到Sink节点的距离；和为网络中节点到Sink节点距离倒数的最大值和最小值。

到邻居节点的距离均值的隶属函数为：

其中，di-avg为节点i到所有邻居节点距离的平均值；与为与邻居节点相距均值倒数最小值及最大值。

节点通过以上3项参数隶属函数得到节点的隶属度Q：

（2）综合评判

B=（bχ，…，by）为簇首选举的综合评判标准，也为簇首可选度；A=（a1，a2，a3）为3项参数的权重集，利用加权平均模型计算：

3.2 簇建立

成为簇首的节点向普通节点广播自己成为簇首的信息，普通节点利用接收到的簇首广播信息，计算出与自己距离最近的簇首，然后向该簇首发送请求加入簇的消息，待簇首再次返回一个确认成功加入的消息，则该节点加入簇成功。当网络中所有节点均成功加入簇，簇建立阶段完成。

同时各簇簇首更新其节点邻域表中簇内成员的簇首可选度，生成一个簇首序列，以便下面“轮”时簇首选择。

3.3 簇首间多跳路由

在簇首将数据传输到Sink节点这个阶段，簇首对簇成员的数据进行融合处理，然后将数据以多跳通信的方式发送至Sink点。

由于网络中各簇首距离Sink的距离不同，距离较近的簇首传输数据的能量消耗低，距离较远的簇首传输数据时能量消耗较高［13］，因此本文采取簇间多跳路由的方式，让距Sink节点较近的簇首协助距Sink节点较远的簇首，以此平均各簇首传递数据时的能量差距。

引入阈值若簇首到Sink节点的距离小于d′，则它直接与Sink节点进行通信；否则该簇首以较大的功率向全网簇首广播一条消息，包含其ID、当前剩余能量和它到汇聚点的距离，选择一个簇首节点协助他进行簇间多跳传输。网络中簇首j收到簇首i广播的消息，则计算出它们之间的近似距离。假设簇首j是簇首i向Sink节点传输数据的中继节点，则2个节点的能量消耗为：

直观上看，若网络中节点j位于节点i与Sink节点之间，这是链路能量消耗较小，则有利于节约能量。为了综合考虑网络节点的剩余，本文的簇间路由策略为：节点i在网络中所有可以通信的簇首节点中，在小的2个节点中，选择剩余能量最高的节点作为其路由的下一跳节点。

当数据传输完成，簇首通知在簇首可选度中值仅低于自身的节点为下一轮簇首，该簇首接到信息后，广播自身为簇首的信息，首轮该簇成员则将数据传递给该簇首，再进行一轮数据的传输。

4 仿真结果与分析

为了验证本文提出的路由算法的网络性能，对LEACH算法、HEED算法和CHBFT算法进行比较。仿真中所用的参数如表2所示。

表2 仿真参数

网络仿真环境如图1所示，其中网络中工作节点分布于100 m×100 m的区域内，Sink节点远离网络区域。

图1 网络仿真环境

4.1 网络簇首数目

参考式（1），结合网络仿真参数，可计算出：1≤mK≤6.2。另根据文献［14］，对网络环境进行仿真可见，当簇首数为5时，协议每一轮网络平均消耗的能量相对最少；同时，此时网络出现首个死亡节点以及全部节点死亡的轮数相对最多。由此可知，在本文设置的仿真环境下，簇首个数为5时，网络各方面性能较为理想，可作理想簇首个数。再由式（2）计算出，簇首竞争半径为R=25.3 m。

本文对LEACH算法、HEED算法和CHBFT算法200轮运行过程中簇首个数进行汇总，LEACH算法、HEED算法的簇首个数如图2和图3所示。

图2 LEACH算法中簇首个数分布

图3 HEED算法中簇首个数分布

CHBFT算法每轮簇首数目均与首轮数目相同，通过多次仿真，簇首数目集中于5或者6。

LEACH算法的不足之处就在于簇首随机产生，簇首数目不稳定，且数目也不能保证接近最优簇首个数；HEED算法通过各节点间动态交换信息来控制了簇首个数，保证簇首数目多处于理想簇首数，但是在动态交换过程中造成大量能量消耗；CHBFT算法通过竞争半径来控制簇首数目，而且首轮簇建立后，接下来“轮”的簇首数目将不会改变，因此，簇首数目更加稳定。

4.2 簇首能量消耗

簇首的能量消耗对网络整体性能的影响非常大，它肩负收集、融合簇内成员数据，更需要将最终数据传递给Sink节点，无论是在数据量方面还是在传输距离方面都比普通节点更加耗能。为了验证CHBFT算法在簇首耗能方面上的优越性，从仿真中随机选取10轮中的簇首能耗，结果见图4。

图4 簇首消耗能量总和

对于簇首数目时常过多的LEACH算法，簇首能耗自然最大；HEED算法簇首数目与CHBFT算法簇首数目相差不大，但是CHBFT算法存在首“轮”产生簇首序列、以后“轮”无须广播的优势，无请求加入、确认加入簇的重复过程，在一定程度上节省了簇首及普通节点的能耗。

4.3 网络生存寿命

网络寿命定义为整个无线传感器网络里第一个传感器节点的能量完全消耗完时的时间。表3为3种算法网络寿命的比较。

表3 3种算法的网络寿命比较

由于CHBFT算法减少了每轮广播、重组簇的能耗及采用多跳簇间路由方式均衡簇首能耗，因此网络节点的生存寿命更加长久。

5 结束语

在无线传感器网络分簇算法中，簇首的选取决定了整个网络的性能。鉴于簇首选取过程中多因素的不确定性，本文提出基于模糊理论的无线传感器网络簇首选举算法。该算法使各节点在竞争半径内交换自身信息，构造节点邻域表，计算出簇首可选度，生成簇首序列，然后选举可选度最高的节点做簇首，形成无线网络的层次结构。仿真结果表明，与LEACH算法以及HEED算法相比，CHBFT算法每轮产生的簇首数目集中于该网络环境下的理想簇首数目，可保证网络平均能量消耗少；同时簇首能量消耗更少，能有效延长无线传感器网络的生命周期。

［1］ Akyildiz IF，Su W，Sankarasubram aniam Y，et al.A Survey on Sensor Networks［J］.IEEE Communications Magazine，2002，40（8）：102-114.

［2］ 解志斌，于 谦，沈 斌，等.一种新的基于粒子群优化的双簇头分簇路由算法［J］.传感技术学报，2013，26（8）：1135-1139.

［3］ 苏金树，郭文忠，余朝龙，等.负载均衡感知的无线传感器网络容错分簇算法［J］.计算机学报，2014， 37（2）：445-456.

［4］ 刘 群，白全炜，曾宪华，等.能量感知的WSN节点分类控制路由算法［J］.传感技术学报，2011，24（7）：1053-1059.

［5］ Heinzelman W，Chandrakasan A，Balakrishnan H.Energy Efficient Communication Protocol for Wireless Sensor Networks［C］//Proceedings of Hawaii International Conference on System Sciences.Hawaii，USA：IEEE Press，2000：1-10.

［6］ Heinzelman W，Chandraksan A，Balakrishnan H.An Application-specific Protocol Architechture for Wireless Micro-sensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

［7］ M anjeshwar A，Grawal D P.TEEN：A Protocol for Enhanced Efficiency in Wireless Sensor Networks［C］// Proceedings of the 15th Parallel and Distributed Processing Symposium.San Francisco，USA：IEEE Computer Society，2001：2009-2015.

［8］ Younis O，Fahm y S.HEED：A Hybrid Energy-efficient Distributed Clustering Approach for Ad Hoc Sensor Networks［J］.IEEE Transactions on Mobile Computing，2004，3（4）：660-669.

［9］ Degrauwe D，Roeck G D，Lombaert G.Uncertainty Quantification in the Dam age Assessment of a Cablestayed Bridge by Means of Fuzzy Numbers［J］. Computers&Structures，2009，87（17）：1077-1084.

［10］ 张海娟.基于蚁群算法的无线传感器网络分簇路由算法［D］.西安：西北大学，2010.

［11］ 田 勇，唐祯安，喻 言.能量均衡的室内无线传感器网络自适应分簇路由算法［J］.电子与信息学报，2013，35（12）：2992-2998.

［12］ 张 品，徐智福，孙 岩.一种新的基于簇头优化的WSN路由协议［J］.传感技术学报，2009，22（7）：1013-1017.

［13］ 孙 亭，杨永田，芦东昕，等.一种基于聚合度的动态分层路由协议［J］.电子学报，2008，36（4）：794-799.

［14］ 蒋 阳，孙柳林，敖文钧，等.WSN中LEACH路由协议簇头数优化研［J］.计算机应用研究，2010，27（11）：4251-4253.

编辑金胡考

C luster Head Election Algorithm in Wireless Sensor Network Based on Fuzzy Theory

TAO Zhiyonga，JIANG Shoufengb
（a.School of Electronic and Information Engineering；b.Institute of Graduate，Liaoning Technical University，Huludao 125105，China）

Wireless Sensor Network（WSN）clustering algorithm works by‘round'.M any clustering algorithms carry out cluster head election in each round，causing excessive energy and time consumption.For this problem，this paper proposes Cluster Head election algorithm in WSN Based on Fuzzy Theory（CHBFT）.It determines the competition radius of cluster head in the network deployment phase to ensure the uniform distribution of cluster heads.In cluster head election phase，it communicates with the node in the com petition radius and structure node's neighborhood list，then uses fuzzy comprehensive evaluation method to generate a sequence of cluster heads，based on the sequence nodes become clusters in line.After the establishment of the clusters，the clusters use multi-hop to communicate with Sink to balance the energy consumption of cluster heads in different distance.Simulation results show that network energy consumption can be reduced and network survival time is extended by this algorithm.

Wireless Sensor Network（WSN）；clustering algorithm；fuzzy theory；com petition radius；sequence of cluster head；multi-hop routing

陶志勇，蒋守凤.基于模糊理论的无线传感器网络簇首选举算法［J］.计算机工程，2015，41（9）：115-119.

英文引用格式：Tao Zhiyong，Jiang Shoufeng.Cluster Head Election Algorithm in Wireless Sensor Network Based on Fuzzy Theory［J］.Computer Engineering，2015，41（9）：115-119.

1000-3428（2015）09-0115-05

A

TP393.02

10.3969/j.issn.1000-3428.2015.09.020

陶志勇（1978-），男，副教授、博士研究生，主研方向；多媒体通信；蒋守凤，硕士研究生。

2014-09-29

2014-10-31 E-m ail：jsf_0116@163.com