基于能量和密度的WSNs动态分区成簇路由算法

史雨雨，郁进明，李　雪

(东华大学 信息科学与技术学院，上海 201620)

基于能量和密度的WSNs动态分区成簇路由算法

史雨雨，郁进明，李雪

(东华大学 信息科学与技术学院，上海 201620)

摘要针对传统的层次型网络存在的分簇不合理和能耗不均衡等问题，提出了一种基于能量和密度的动态非均匀分区成簇路由算法。该算法先根据节点与基站之间的距离将网络合理地进行动态的区域划分，在区域内成簇，使靠近基站的簇规模小于距离基站较远的簇，减少靠近基站的簇首负担和能量消耗；通过综合考虑节点剩余能量和节点密度等因素来优化簇的非均匀划分和簇首的选择，簇首间采取基于数据聚合的多跳传输机制。仿真结果表明，与经典路由算法LEACH相比，该算法能有效均衡节点能耗，延长网络生命周期。

关键词无线传感器网络；动态区域划分；能量；密度；LEACH

大量微小的传感器节点通过无线通信方式形成一个自组织的网络系统，协作地感知、采集并处理监测区域内的信息，便形成了一个无线传感器网络[1-2]。传感器网络也面临多种独特的挑战和约束：传感器节点能量有限、缺乏设施支持或维护、需要更小的且廉价有效的器件、敏感数据的传输，因此，为提高网络性能和延长网络寿命，提出了分簇路由协议。LEACH(LowEnergyAdaptiveClusteringHierarchy)算法是无线传感器网络中提出的第一个层次型路由协议[3-4]。LEACH协议的执行过程是周期性的，每轮分为簇建立阶段和数据通信阶段，该协议循环随机选择簇首，路由算法采用一跳通信，不适合大规模网络且存在簇划分、簇首分布不合理等缺点[5]。

本文提出了一种基于能量和密度的动态非均匀分区成簇路由算法。首先根据节点到基站的距离进行动态的非均匀区域划分，使得靠近基站的区域具有较小的规模，减少需要承担数据转发任务的区内通信开销，为簇间的数据转发节省更多的能量；综合考虑节点自身的剩余能量、邻居节点数等因素构成节点的竞争值，选取竞争值大的节点作为簇首；在数据传输阶段，簇首间的数据传输采取数据聚合优先的多跳传输，减少过远传输带来的巨大能量消耗；该算法的动态区域划分能均衡网络的能耗，有效的解决能量空洞问题，簇首的选举采用由节点剩余能量、邻居节点数目、距离等因素构成的竞争值比较方法，分簇比较合理，在数据传输阶段采用的簇首间基于数据聚合的多跳传输机制则节省了网络的能耗和带宽，实验结果表明，该算法可有效均衡整个网络的能耗、延长网络的生命周期。

1算法模型

1.1网络模型

本文中对无线传感器网络作如下假设：(1)节点随机分布，Sink节点及普通节点位置均固定；(2)Sink节点能量供应持续，具有较强的计算和存储能力，并可向全网发送数据；(3)普通节点能量有限，同质同构，具有相同的初始能量E0；(4)每个节点都有一个唯一的ID标识，能够检查自己的剩余能量Er；(5)节点间的通信链路是对称的，节点可自由调整发射功率，可根据接收信号的强度计算发送者到自身的近似距离；(6)节点之间有冗余性，采用数据聚合模型计算数据聚合度。

1.2数据聚合模型

传感器网络节点部署密集，信息冗余性大，大量的数据传输会过多消耗网络能量，所以采用数据聚合非常有必要。文献[6]提出一种数据聚合模型，节点i与j之间的距离为dij，簇内节点j采集的数据为Dj，节点j将数据发送至所在簇Ch的簇首，那么在簇首h与本簇所有节点进行数据聚合之后节点j采集的数据Dj变为

(1)

数据聚合之后簇首h收集到的数据为

(2)

1.3能量模型

传感器节点的能耗集中在感知数据、处理数据、发送数据和接收数据方面，所有节点感知并产生1bit数据能耗一般均等，记为Es，节点处理1bit数据耗能为ED，本文采用与文献[7]相似的一阶无线电模型来模拟传感器节点的数据收发。由一个节点发送至另一个节点的能耗包括在电路上的消耗和传输路径上的消耗

(3)

2算法路由协议

协议的执行过程是周期性的，将一个执行周期定义为一轮，在每一轮中，分为3个阶段：动态非均匀分区阶段、簇的形成阶段和数据传输阶段。协议执行过程如下：首先根据节点到基站的距离将传感器节点以基站为圆心划分为大小不等的非均匀圆环区域，不同轮数之间的相邻圆环间隔之差受上一轮剩余能量系数的影响而动态变化，通过引入剩余能量系数在每轮算法周期之前对网络进行合理的动态非均匀分区，使得距离基站较近的区域面积较小；然后在区域内成簇，由Sink节点根据节点的密度和能量选取簇首，选择剩余能量高、邻居节点多、该节点做为簇首本簇整体能耗低的节点为簇首；最后进入稳定的数据传输阶段，簇首间采取基于数据聚合的分组转发机制进行多跳传输，使得距离基站较远的簇首减少能量消耗。

图1　算法原理结构图

2.1动态非均匀区域的划分

本协议将整个区域以基站为圆心划分为多个不同间隔的同心圆环区域，由内到外依次记为1环，2环，…，n环，随着环数i的增加，圆环间隔Ri依次递增，在每一轮中Ri-Ri-1的值是固定的，将第r轮中相邻同心圆间隔的差值Ri-Ri-1记为d(r)，如图3所示为同心圆网络拓扑。

图2　同心圆网络拓扑

不同轮数r之间的圆环间隔之差d(r)受上一轮剩余能量系数的影响动态变化，剩余能量系数代表着本轮中区域平均剩余能量和区域原始平均能量的关系，第r轮中剩余能量系数记为λ(r)，由剩余能量系数的定义得到λ(r)的计算公式为

(5)

其中，dini为第一轮中的圆环间隔初始化差值；dini以及第1环的半径R1由基站确定。在算法初始化时，由基站感知网络所有节点，并向全网广播初始化分区信息，网络中节点根据接收信号的强度RSSI计算出节点到基站的距离l，节点根据距离l判定自身所在的区域。同时，网络中节点以广播的方式将自己的ID信息发送出去，节点通过收到的广播得到周围节点信息，从而得知网络中节点的密度。

2.2簇的划分

簇首的数目对传感器网络的整体能耗和性能有很大影响，文献[8]的研究结果表明，将簇首的个数控制在整个网络节点的50%时，可使得整个网络的能量消耗最低，所以在区内成簇时，每个区域选择区内存活节点数的5%作为簇首的数目。

2.3簇首的竞争

节点的密度越大则在此区域成簇的可能性越大，节点的剩余能量越高则数据的采集转发有效性越大，节点作为簇首时整个簇的能耗越低则网络的能耗越小，所以在簇首的竞争过程中，需要综合考虑候选簇首节点的密度、剩余能量以及节点作为簇首时整个簇的能耗等因素，节点的密度越大、剩余能量越高、作为簇首时整个簇的能耗越低，节点成功竞选簇首的可能性越大。

估算节点i假设自身作为簇首时簇的整体能耗为

(6)

则簇的平均能量为

(7)

簇的平均能耗为

(8)

节点i成为簇首的竞争值为

(9)

其中，c1，c2和c3为比例系数；Nneigh(i)为节点i的邻居节点个数；Nalive为当前网络的存活节点个数。节点根据收到的候选簇首的信息计算出竞争值，选举竞争值大的作为簇首，在选择出簇首节点以后，簇首向自己所在的区域内进行广播，普通节点根据收到的簇首广播信息选择合适的簇首加入，并向所在簇的簇首发送加入信息，簇首接收普通节点发送的信息，最终在各个区域内形成簇。

2.4数据传输

本协议采用簇内单跳通信、簇首间多跳通信的数据传输方式。对于簇内通信，成功选举出簇首之后，簇首向所在簇发送成员消息Cluster_Message，Cluster_Message中包括簇内节点的ID、节点的状态及节点的邻居节点信息表，簇内普通节点收到Cluster_Message后向簇首发送回复消息Re_Message，包括节点到簇首的能耗、发送数据的长度、节点的状态等。簇首节点根据收到的Re_Message给需要发送数据的节点分配发送时隙表。数据采集完成后，由簇首将收到的所有数据进行聚合。对于簇首间通信，首先，簇首发送广播信息告知周围簇首自身的剩余能量、到基站的距离及所在簇的节点个数，簇首根据收到的广播，将邻居簇首中相比自身到基站距离较近的簇首信息保存并且为之建立邻居簇首节点信息表，簇首将在邻居簇首节点信息表中选取下一跳节点，综合考虑剩余能量和所在簇节点个数，选择剩余能量较大、簇内节点个数较少的邻居簇首作为下一跳节点。由于本协议的动态划分区域，使得靠近基站的簇的范围减小，为簇首间的数据转发预留了更多的能量，均衡了网络的整体能耗，从而有效延长网络寿命。

3仿真结果及分析

为评估本文算法的有效性，采用Matlab对本算法和LEACH进行仿真和分析。其中假设节点在休眠和空闲时的能耗均为0，仿真环境用到的参数如表1所示。

表1　仿真参数

衡量网络的最重要性能指标之一是网络生命周期，图4是对本算法及LEACH算法网络生命周期的比较，由图可知，LEACH算法的第一个节点死亡是在302轮，本算法第一个节点死亡是在847轮，最后一个节点死亡分别是在896轮和1580轮，本算法延迟了节点的死亡时间，将网络的生命周期延长了38%。观察节点死亡的趋势可看出，由于LEACH算法节点能量分布不均匀问题，导致了某些节点的过早死亡和某些节点的存活时间较长的情况。本算法中，节点能量耗尽的轮数基本相同，证明了本算法有效地提高了能量的均衡性。

图3　网络存活节点数比较

图5为LEACH算法和本算法的簇数目和轮数的关系，如图所示，由于LEACH协议中簇首的选择是随机的，并且动态成簇，所以每一轮中簇首节点个数的变化范围很大，不能保证簇数目一致保持最佳，增加了网络的开销。本算法始终将簇首的数目控制在存活节点数的5%，保证网络簇数目一致维持在最佳状态，同时采用动态划分区域，然后在区域内选择簇首，使得簇的分布较为均匀。

图4　簇首个数比较

图6对LEACH算法和本算法在每轮数据采集过后的网络剩余能量进行了对比，由图可看出，两种算法协议的网络剩余能量基本呈线性下降趋势，但本算法每轮能量的消耗明显低于LEACH，从而节省了网络的能量，延长了网络生命周期。

图5　网络剩余能量比较

4结束语

本文在分析研究无线传感器网络经典路由算法的基础上，提出了基于能量和密度的动态分区成簇路由算法本算法。首先根据节点与基站之间的距离将网络合理地进行区域划分，使靠近基站的簇规模小于距离基站较远的簇，减少靠近基站的簇头负担和能量消耗，为簇间数据转发节省能量，然后通过综合考虑节点剩余能量和节点密度等因素来优化簇的非均匀划分和簇首的选择，同时簇首间采取基于数据聚合的分组转发机制。仿真和分析结果表明，本算法能够有效的均衡节点能耗，延长网络生命周期。

参考文献

[1]PerilloM,HeinzelmanW.Wirelesssensornetworkprotocols[M].Netherlands:KluwerAcdemicPublishers,2004.

[2]CaiiawayEH.Wirelesssensornetworks:architecturesandprotocols[M].Londan:CRCPress,2004.

[3]HeinzelmanWR,ChandrakasanA,BalakrishnanH.Anapplicationspecificprotocolarchitectureforwirelessmicro-sensornetworks[J].IEEETransactionsonWirelessCommunications,2002,1(4) :660-670.

[4]LuanWeiping,ZhuChanghua,SuBo.AnimprovedroutingalgorithmonLEACHbycombiningnodedegreeandresidualenergyforWSNs[C].Persi:ICSPS,2011.

[5]李芳芳,王靖.一种基于LEACH协议的无线传感器网络路由算法[J].传感技术学报,2012(10):1445-1451.

[6]VonRickenbachP,WattenhoferR.GatheringcorrelateddatainSensornetworks[C].CA,USA:DiscreteAlgoritmsandMethodsforMOBILEComputingandCommunications,2004.

[7]WendiRabinerHeinzelman,AnanthaChandrakasan,HariBalakrishnan.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[C].HI,USA:ProceedingsoftheHawaiiInternationalConferenceonSystemSciences,2000.

[8]付菁波.基于分簇的无线传感器网络路由算法[J].电子科技,2013,26(6):124-127.

Dynamic Partitioned Clustering Routing Algorithm Based on Energy and Density for WSNs

SHIYuyu，YUJinming，LIXue

(CollegeofInformationScience&Technology,DonghuaUniversity,Shanghai201620,China)

AbstractAiming at problems such as unreasonable clustering and imbalance of energy consumption, which exist in traditional hierarchical network, a dynamic partitioned clustering routing algorithm based on energy and density(DPC-ED) was proposed. In DPC-ED, the entire network is divided dynamically according to the distance between normal nodes and the sink node, making the regions closer to the sink node with smaller nodes to reduce the cluster heads’ burden and energy consumption. By considering factors such as residual energy and density to optimize the clusters’ uneven partition and the selection of cluster heads, and information is transmitted with mode of multiple hops based on data aggregate. Simulation results show that compared with the classical routing algorithm LEACH, DPC-ED can balance the nodes’ energy consumption and prolong lifetime of the network effectively.

Keywordswireless sensor networks；dynamic partition；energy；density；LEACH

收稿日期:2015-10-17

作者简介:史雨雨(1990-)，女，硕士研究生。研究方向：ZigBee无线通信系统，路由算法与协议等。

doi:10.16180/j.cnki.issn1007-7820.2016.06.014

中图分类号TN926；TP393

文献标识码A

文章编号1007-7820(2016)06-047-04