基于距离分簇算法的WSN组网方法

华江锋,吕艳辉，付 垚，刘洁琳

(沈阳理工大学 信息科学与工程学院，沈阳 110159)

基于距离分簇算法的WSN组网方法

华江锋,吕艳辉，付 垚，刘洁琳

(沈阳理工大学 信息科学与工程学院，沈阳 110159)

针对无线传感器网络中传感器节点能量受限不能及时供给的问题，提出一种基于距离分簇算法的无线传感器网络组网方法，旨在均衡节点负载，提高通信效率。算法由Sink节点发起，主要通过设置Sink节点的不同通信距离来划分传感器网络，根据网络层数设定每个簇的最大节点数目，引入簇首轮换机制保证网络存活周期，根据多跳通信路由函数选取簇间通信最佳路由。仿真结果验证了算法能够有效降低网络能耗和延长网络生存周期。

无线传感器网络；分簇组网；均衡负载

无线传感器网络(WSN)是一种由大量随机分布的低成本、低功耗的微小传感器节点组成的分布式网络，它通常采用节点多跳路由和自组织的方式构成网络系统，被广泛应用于军事侦察、环境监测、医疗监护、商业开发等领域[1]。

目前，无线传感器网络的分簇算法研究主要集中在均衡节点能量负载和延长网络生存周期两个方面。针对这些问题，国内外展开了大量的理论与实践研究。LEACH(Low-Energy Adaptive Cluster Hierarchy)协议[2]采用周期循环随机选举的方式产生簇首节点，通过簇首轮换机制来均衡WSN中节点能耗，簇首单跳通信将数据传送给Sink节点。该协议避免了节点能量过分消耗，但随机产生的簇首个数和位置无法确定；另外，簇首的频繁选举会造成较大的数据传输量，单跳通信需要节点支持射频功率动态调整。PEGASIS(Power-Efficient Gathering in Sensor Information System)协议[3]中普通节点采用簇间多跳通信的方式，将数据传送给最高层级的簇首，然后由该簇首将数据单跳传送给Sink节点。该协议避免了因簇首频繁选举造成的通信开销，但由于要传递大量的数据信息，距离Sink节点较近的簇首负载过重，会导致网络提前死亡，同样也会影响整个网络的数据监测和生存周期。苏金树等人提出负载均衡感知的容错分簇算法，采用自适应离散粒子群优化的簇首选举机制确保簇首负载均衡与能耗最低，但没有解决簇首因距离不同造成的负载不均衡问题[4]。周东鑫等人提出基于分层多跳的WSN分簇路由算法。与其他算法相比，它具有更好的数据传输效率与网络生存周期，但该算法的分层阈值选取偏大，且没有对簇首的分布进行合理布局[5]。Busse等人分析了在不同能量消耗模型下的网络生命周期最大化问题，给出了传输功率特定时的线性算法，但没有考虑到大部分场景下该算法是一个NP完全问题[6]。

从上述分析可以看出，现有研究在设计组网时并未充分考虑节点能耗均衡与网络生存周期的问题。因此，本文提出的DCA(Distance-Clustering Algorithm)算法在节点负载相对均衡、最优网络能耗和提高数据传输效率的基础上建立了无线传感器网络的分簇组网方案。

1 组网模型

1.1 能耗模型

无线通信能耗是基于Heinzelman[7]的研究成果。首先确定模型的距离阈值d0，如果发送节点到目标节点的距离d

(1)

节点j接收节点i发送的kbit数据能耗为

ERX(k,d)=Eelec·k

(2)

式中：Eeleck表示无线收发电路的能耗；Eampk,d表示放大器消耗的能量；εamp和εfs分别是信号放大器的多径放大倍数和自由放大倍数。

1.2 网络设定

本文假设无线传感器网络具有如下性质：

(1) 网络监测区域范围已知，传感器节点随机部署；

(2) 网络观测区域外围只有一个Sink节点，位置固定已知；

(3) 所有节点具有相同的初始能量，部署好后不可移动；

(4) 节点采用数据融合技术减少数据传输流量，融合度为100%；

(5) 节点通信模块能耗远远大于其他模块，故只考虑数据通信能耗。

2 算法概述

2.1 相关定义

本文所涉及的相关定义描述如下：

(1) 网络层级NLvl：网络中各节点通过与Sink节点的距离值划分到不同的层级，层级值记为i.NLvl=k，其中1≤k≤K，K为最大层级值，1≤i≤N，i为网络中某节点，N为网络中节点总数，NLvl值根据Sink节点圆心不同辐射半径计算得到；

(2) 节点标识NodeId：用于标识网络中的传感器节点；

(3) 节点剩余能量值NodeEn：用于记录传感器节点的剩余能量值；

(4) 簇首标志IsCH：用于记录节点是否为簇首，若该值为0，则为普通节点，该值若为1，则为簇首；

(5) 节点距离标识SinkDis：用于记录传感器节点与Sink节点的距离值；

(6) 簇首能量阈值ENgate：用以判定节点是否可以成为簇首；

(7) 簇首节点的成员信息MemberInfo：用于存储其成员节点的具体信息，包括成员节点的节点距离标识、网络层级标识和剩余能量值；

(8) 簇成员数最大值CMemberNumi：用于设置每层级网络簇的成员数目；

(9) 簇首竞争消息ClusterHead：用于标明节点竞选簇首，包含该节点的网络层级、节点标识、节点剩余能量值和节点距离标识等信息。

具体算法流程如图1所示。

图1 DCA算法流程

2.2 基于距离分簇

2.2.1 网络分层

系统初始阶段，Sink节点向网络发送广播消息。网络中的传感器节点根据接收Sink节点的RSSI值(接收信号强度指示)计算出自身到Sink节点之间的距离，然后系统按照距离值将节点进行网络层级分类，具体工作如下：

(1) Sink节点向网络广播初始化DLHello消息；

(2) 网络中的传感器节点i收到DLHello消息后，根据RSSI值求出自身与Sink节点之间的距离i.SinkDis；

(3) 节点i根据预先设定的K值和各层距离阈值Li，依定义与i.SinkDis进行计算比较，求出节点的网络层级值i.NLvl。

分层后的传感器网络如图2所示。

图2 传感器网络分层

2.2.2 网络分簇

对传感器网络进行分层后，进入分簇阶段。具体过程如下：

(1)所有节点在竞争簇首之前，将自身的簇首标志值设为0，即i.IsCH=0；

(2)判断节点剩余能量是否大于阈值ENgate，即if(i.NodeEn>ENgate)，只有大于阈值的节点才可以竞选簇首；

(3)满足竞选簇首条件的节点设置簇首竞争周期t，广播簇首竞争消息，即i.ClusterHead(i.NLvl,i.NodeEn,i.NodeId,i.SinkDis)；

(4)若节点在簇首周期内收到其他节点的簇首竞争消息，比较它们的网络层级数，即if(i.NLvl!=j.NLvl)，若层级值不同，丢弃该消息，若层级值相同，引入簇首评价函数竞选：

(3)

式中：α、β为比例因子；P是簇首在本轮所有节点中所占的百分比；r是选举轮数；rmod(1/P)为这一轮循环中当选为簇首的节点个数；D是节点与Sink节点的距离值；E是节点本轮剩余能量，具体计算公式为

E=Erest(r)-ETX(k,d)-ERX(k,d)

(4)

Erest(r)代表第r轮该节点的初始能量，ETX(k,d)和ERX(k,d)分别与式(1)、式(2)中参数一致；

(5)若节点在竞争周期内没有收到竞选值高于自身的消息，将IsCH值改为1，设置建簇周期t，然后在本网络层级内广播建簇消息，声明自己为簇首；

(6)普通节点收到建簇消息后，向信号最强的簇首发送申请加入信息，申请加入该簇，如果此时该簇节点数目没有超过设置的簇成员数最大值CMemberNumi，则簇首同意该节点加入，如果该簇已满则向其他簇首发送信息申请加入；

(7)若建簇周期结束或簇已满员，则建簇完毕。

通过上述工作，传感器网络被划分成多个层级。在每一层级中，选举剩余能量值高且距离Sink近的节点为簇首，然后以它为核心构建新簇，分簇后的网络拓扑如图3所示。

图3 网络分簇拓扑

2.3 节点通信

2.3.1 簇内通信

网络分簇后，需要进行簇内通信，通过以下步骤实现：

(1)簇首生成一个TDMA时隙表，向簇内成员节点广播发送时隙信息；

(2)簇内成员节点接收信息，在相应的时隙进行数据传输，其他时间则进入休眠状态，以便减少能量消耗和数据冲突；

(3)簇首接收并融合所有成员节点的数据信息后转发给下一跳簇首。

2.3.2 簇间通信

簇首与Sink节点之间的数据传输采用多跳通信的方式，具体步骤如下：

(1) 基于距离分簇完成后，从网络层级值最大的簇首开始进行数据传输；

(2) 根据多跳通信路由函数P依次计算上一层网络区域内簇首的函数值p，函数公式为：

(5)

式中：φ、θ是权重系数；i.SinkDis是簇首到Sink节点的距离；Eelec和E分别与式(1)、式(4)中参数一致；

(3)选取p值最大的簇首作为下一跳转发节点，若p值相等，则选择距离本次转发节点较近的簇首作为下一跳转发节点，然后转向(2)；

(4)当网络层级NLvl=1时，下一跳直接转发给Sink节点。

簇间通信的过程如图4所示。

图4 簇间通信

2.4 簇首轮换

在网络通信中，当簇首节点的剩余能量低于阈值时，触发簇首轮换机制。具体实现过程如下：

(1)当前簇首检查其簇内成员信息，调用簇首选举函数，选举能量值大且距离Sink节点近的成员节点为新簇首；

(2)若选举成功，则建立新簇，若该簇中所有节点的能量值都低于ENgate，则告知Sink节点进行漏洞修补。

3 仿真与性能分析

本文采用Matlab对LEACH、PEGASIS和DCA算法进行仿真实验，从网络能量消耗、网络生存周期两个方面进行对比，同时对簇首选举权重系数、多跳通信路由系数进行仿真试验，选定最终系数值。仿真参数设置见表1。

表1 仿真参数设置

图5为在LEACH、PEGASIS和DCA三种算法下，网络能耗随时间变化的仿真情况。

图5 网络能耗

从图5可以看出，随着时间的推移，DCA算法相比其他两种算法的网络能耗更低。DCA算法由于采用基于距离的节点分簇和多跳路由数据转发技术，使得节点间的通信量大幅度减少，从而降低了网络能耗。

图6为网络生存周期算法仿真比较图。

图6 网络生存周期

由图6可知，采用LEACH算法的传感器节点在网络运行到500轮时已经全部死亡；PEGASIS算法下的节点最多可以存活到700轮；而DCA算法的节点最大存活时间为1000轮。通过对比可以发现，DCA算法大大增加了网络中的存活节点个数，提高了网络生存周期。

4 结论

本文以无线传感器网络为研究对象，针对WSN中节点能量有限，数据通信传输效率低的问题，提出一种基于距离分簇的无线传感器网络组网方法。根据节点剩余能量、与Sink节点通信距离等指标来选取簇首，通过簇首轮换机制与设定每个簇的最大节点数目来均衡节点能耗，以合理选取簇间通信路由来提高网络通信效率。最后，仿真结果从网络能耗、网络生存周期两个方面验证本文所提出算法的有效性。

[1] 蒋畅江,石为人,唐贤能,等.能量均衡的无线传感器网络非均匀分簇路由协议[J].软件学报,2012,23(5):1222-1232.

[2] HEINZELMAN W,CHANDRAKASAN A.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Scineces.Muai:IEEE Computer Society,2000:3005-3014.

[3] LINDSEY S,RAGHAVENDRA C S.PEGASIS:Power-Efficient Gathering in Sensor Information Systems[J].IEEE Aerospace and Electronic Systems Society,2002(3):1125-1130.

[4] 苏金树,郭文忠,余朝龙.负载均衡感知的无线传感器网络容错分簇算法[J].计算机学报,2014,37(2)445-456.

[5] 周东鑫,金文光,容志能.基于分层的无线传感器网络多跳分簇路由算法[J].传感器技术学报,2011,24(1):73-78.

[6] Busse M,Haenselman T,Effelsberg W.A Comparison of Lifetime-efficient Forwarding Strategies for Wireless Sensor Networks[C]//Proceedings of the 4th International Symposium on Information Proceesing in Sensor Networks.New York,USA:[s.n.],2005:13-19.

[7] W B Heinzelman.Application specific protocol architecture for wireless microsensor networks[J].IEEE Transaction on Wireless Communications,2002,1(4):660-670.

[8] 李萌,孙恩昌,张延华.无线信道模型研究与展望(一)[J].中国电子科学研究院学报,2012,7(4):362-364.

[9] 李腊远,李方云.一种基于低能量的双簇首WSN路由算法[J].武汉理工大学学报,2009,33(3):450-453.

NetworkingMeasureBasedonDistance-clusteringAlgorithminWirelessSensorNetwork

HUA Jiangfeng,LV Yanhui,FU Yao,LIU Jielin

(Shenyang Ligong University，Shenyang 110159，China)

In order to solve the problem that the sensor nodes in the wireless sensor network can not supply the energy in time,a new method based on distance clustering algorithm in wireless sensor networks is proposed.Its purpose is to balance the node load and improve communication efficiency.The algorithm is initiated by the Sink node,setting up the different communication distance of the Sink node,sensor networks is divided.According to maximum number of nodes per cluster based on network layer,the network survival period is ensured by cluster head change mechanism.The inter cluster communication optimal routing is selected according to the multi hop routing function.The simulation results show that the algorithm can effectively reduce the network energy consumption and prolong the network lifetime.

wireless sensor network；clustering network；load balancing

2017-01-12

辽宁省自然科学基金资助项目(20170540777)

华江锋(1991—),男，硕士研究生；通讯作者：吕艳辉(1971—)，女，教授，博士，研究方向：无线传感器网络、数据融合、系统仿真技术。

1003-1251(2017)06-0031-06

TP393

A

马金发)