异质传感网中基于自适应簇半径的高效组网算法*
2019-09-21秦宁宁张伟杰
秦宁宁,张伟杰
(江南大学轻工过程先进控制教育部重点实验室,江苏 无锡 214122)
无线传感网WSN(Wireless Sensor Network)中节点能量的利用效率直接影响网络的生命周期。由于节点分布式的选簇、入簇以及路由的规范划分在网络节能中更具优势,使得网络的分簇组网与逐级传输的工作模式,更适合以电池为能量供给的WSN中。目前同构组网算法已经相对成熟,但实际应用中,由于各种干扰因素的存在,网络的异构化普遍存在,因此设计面向异构网络的组网方案对均衡网络能耗、提高节点能量的利用率以及延长网络生命周期,具有更重要的现实意义。
分簇组网过程中的能量利用效率,主要受簇首选举和分簇结构两方面影响。尤其对于异构的WSN而言,由于节点之间存在能量差异,以高能量节点作为数据转发的枢纽,显然可以有效避免个别节点由于负荷过大提前死亡,确保网络稳定运行,提高能量利用率。文献[1]采用了一种分布式节能分簇算法,综合考虑了节点初始能量以及剩余能量对簇首的影响,保证每轮选出的簇首能量最优,降低了簇首节点提前死亡的概率。廖福保等人[2]在簇首选取时综合考虑节点剩余能量、节点度和节点的能量消耗速度等因素的影响,进一步优化簇首选举,降低了簇首节点提前死亡的概率。簇首选举时需要全网进行数据收发,每轮选举会消耗一定的能量,减少簇首选举次数,也是减少能量消耗的一种有效手段。文献[3]提出簇首轮换的概念来减少簇首选举时的能量损耗。冯咲[4]在此基础上提出簇首轮换间隔的优化算法,能够进一步自适应的实现簇首轮换。
优化分簇结构对均衡网络能耗也具有正向的激励作用,调整合理的簇内成员数量和通信范围,可以有效控制簇内能量的消耗速度,从而均衡网络能耗。兼顾最优簇首数量的条件下,文献[5]为控制成员数目,以邻居节点数为参考,回避过多邻居节点入簇,缩小簇范围来缩短簇内通信距离,提高能量利用率。文献[6]根据相邻节点的数量来选取簇首,通过计算簇内通信代价来调整簇半径,缩小簇范围以提高能量利用率。Park等人[7]采用K-means方法对网络中的节点进行均匀分簇,选择每个簇中最靠近几何中心的节点担任簇首,通过均匀簇的大小实现了均衡簇首能耗。李成法等人[8]反其道行之,提出了一种非均匀分簇算法,通过非均匀分簇来保证簇首能耗均衡,提高能量利用率。余修武等人[9]提出了一种以竞争半径来配置簇首,设置簇首竞争半径与到Sink节点的距离成反比,使得离Sink节点近的簇首具有较小的竞争半径,缩小Sink周围的簇规模,避免节点由于过劳中转数据引发提早死亡。
利用几何知识进行簇首选择,从物理空间上规划簇范围,也是一种提高能量利用效率的有效手段。将网络在同心圆的基础上划分单元格,以单元格为单位进行节点能量分级管理[10]。基于同心圆区域的理念,胡源等人[11]将圆划分为等扇区,保证同环簇具有相同的通信范围,均衡网络能耗。为避免长距单跳通信引发的能量陡降,文献[12]将以最小单跳距离配置环间距,对每环进行等面积划分指导成簇,均衡了不同环之间簇的规模和结构,保证网络能耗平衡,一定程度上延长了网络生命周期。
客观上讲,已有研究成果中关于能量引导簇首选举和均衡带动成簇结构的理念,在本论文的研究中也有体现,但已有研究结论均为针对同构或者单一元素异构的传感器网络,而对于实际网络应用场景中,由于工作环境、网络负荷、物理器件等随机因素的影响,节点更多的呈现出多元素化且随机化的异构特性。这使得从簇首选举-分簇组网-结构配置-路由规划的组网全流程中,都应面向传感器网络异构性的多级化和随机化特征展开。
论文面向随机多级异构传感器,提出了一种基于自适应簇半径的高效组网算法ARCN(Adaptive Radius Cluster Networking algorithm)。能量与邻居联合影响下的簇首选举机制,打破概率选举中节点能力不等,却机会均等当选簇首的不合理局面;引入适应值半径的概念,动态控制簇首通信距离,以调节簇的结构与规模;计算簇首间的通信代价,作为通信路径选择的依据,实现通信能耗的降低。
1 网络模型
在数据型传感器网络中,为缩短通信路径的长度,可以充分利于RF信号的全向特征,将数据的汇聚中心Sink安置在网络的物理中心位置。对于Sink而言,形成一个发散形式的全向数据收集网络,可以提高数据收集的效率。因此,不失一般性,论文将研究场景设定为以Sink为中心的监测区域,并引入参考圆将网络场景虚拟为一个圆形区域,如下图1所示。场景的虚拟划分,仅为了控制成簇的规模,并不干涉算法的运行,因此基于本场景的研究结论,可以扩展到其他不存在中空区域的网络场景中。
图1 网络模型图
1.1 节点的随机异构性
给定监测区域I,以Sink为中心o点,依次向外将I划分为共计M个准等间距的同心圆环,监测区域内的任意点∂∈I,同心圆环的标记:
(1)
式中:c0圆半径为Ro,其余环间距为Rk,设定Rk=Ro/2,do∂表示任意点∂与中心Sink点之间的距离。
给定随机异构传感器节点μ={μi(xi,yi)|i=1,2,…,N}随机部署在I内,(xi,yi)表示节点的位置信息,μ的初始能量E={Ei|i=1,2,…,N}和初始半径r={ri|i=1,2,…,N}满足Ei∈[Emin,Emax]和ri∈[rmin,rmax]。以环间距离的最大跨度为参考,节点的初始通讯距离ri应满足rmin≥2Rk=Ro。
1.2 能耗模型
节点通信能耗在固有能耗的基础上,随着数据量和通信距离的增长呈正比增长[13]。当节点μi向其通信范围内的某一接收节点μj传输mbit数据,μi与μj之间距离为d,μi所消耗的能量为:
(2)
节点μj接收mbit数据时能耗为:
Erv(m)=mEelec
(3)
融合数据的能耗仅与簇首节点有关,簇首节点μj融合mbit数据时的能耗为:
Eag(m)=mEDA
(4)
式中:EDA是节点数据融合的单位比特能耗。
2 算法的思想与关键
2.1 算法思想
无线传感器网络中能量的消耗主要集中在数据传输阶段,如何均衡网络中节点能量消耗,对提高网络能量的利用效率以及延长网络生命周期尤为重要。为提高能量利用效率,设计了ARCN算法。节点基于邻居信息进行簇首选举并确定簇的结构规模,采用基于能效的自适应簇规模组网模式,在满足通信距离的同时缩小簇的物理半径,使得节点的单跳通信距离短小且有效,有利于缩小簇内数据对簇首节点负荷;寻找最优通信路径以减小数据转发时能量消耗,不仅保证了网络的连通性还减缓了簇首节点能量消耗速度,避免个别节点提前死亡。
2.2 相关定义
定义1(最大可达节点集)节点μi和μj之间若存在通信链路,则互为邻居节点,定义μi关于ri的最大可达节点集
T(μi,ri)={μj|dμiμj≤ri&&i≠j,μj∈μ}
(5)
定义2(适应值半径)节点μi的适应值半径为受所在ck影响的动态通信范围,可定义为:
ri_ck=2γe1/k
(6)
式中:γ为调节参数,且γ∈[0,1]。
2.3 单/多跳通信模式的选择机制
在分簇组网形成的网络中,c0环内节点通过单跳或多跳的方式将信息转发给Sink节点。在理论上,同等距离情况下,多跳通信比单跳通信节能,但在Sink节点周围,经簇首转发信息给Sink节点构成多跳通信,与未经簇首转发的单跳通信相比,节能优势有待考量;并且在Sink周围的簇首由于半径小、数量少容易使转发负荷过大,造成个别节点(簇首)的业务量过大而过早死亡。因此,为降低c0内部分节点负荷,需要对c0内节点的通信模式(单跳/多跳)进行定性分析,为网络选择更为匹配的通信方式。
以Sink为圆心的c0圆内,p、q两个节点为例,点p到Sink所在o点的通信方式分为两种:一种是单跳通信模式,即p→o直接通信;另一种是由节点q作为中转节点形成p→q→o多跳通信模式。
由式(2)可得,传输mbit数据量时,单跳p→o通信能耗为Esh,多跳p→q→o通信能耗为Emh,多跳与单跳的能耗差距为:
(7)
定理在给定形如式(1)网络的c0区域内,基于无固有能耗的自由空间能耗模型,节点向位于o的Sink点发送相同量的数据,存在在一定的区域内,使得节点间采用单跳通信所消耗的能量小于区域内两跳通信的能耗。
证明
由于节点通信半径存在ri≥rmin≥Ro,若以Ro/2为半径将c0圆划分为内圆(标记为⊙2)和外环(标记为c0/⊙2),c1环内的簇首节点向Sink节点传输数据时,最差时必须在c0的外环处应存在某簇首p为其转发数据。为中和Sink周边节点的负荷,c0内所有节点q∈⊙2均应作为簇首参与数据通信。
基于无固有能耗的自由空间能耗模型(Eelec=0)和式(7),定理只需证明存在式(8)成立的区域,即
(8)
式中:dpo、dpq和dqo分别表示节点p、q和o之间的距离。
不失一般性,建立Sink节点所在的o点为原点,以op为纵轴的坐标系如图2所示,设定p(xp,yp),q(xq,yq),由于点p位于y轴上,最差情况位于(0,Ro),将其代入式(8),可得式(9):
(9)
同理,最优情况下p位于内圆圆周上,坐标为(0,Ro/2),可得式(10):
(10)
式(9)～式(10)的等效几何区域如图2中圆⊙3和圆⊙1,圆心分别为(0,Ro/2)和(0,Ro/4),半径分别为Ro/2和Ro/4。节点p的初始半径为rp≥R0,故圆⊙4表示点p以R0为半径的通信范围。
(11)
图2 c0内节点通信模式几何等效图
基于无固有能耗的自由空间模型,存在一定的区域且存在[11%,43%]的概率,节点间采用单跳通信的能耗小于两跳通信的能耗。
证毕。
结合上述定理,不考虑固有能量消耗时,在c0内,为c1环转接数据的簇首p∈c0/⊙2存在[11%,43%]的概率,以单跳p→o通信更为节能,且该比例随固有能耗的加入而增高。
同理,若为c1环转接数据的簇首p∈⊙2会存在大于43%的概率以单跳p→o通信更为节能。故,论文将⊙2内的节点全部设置为簇首,不仅在通信模式上进行了节能优化,又避免了节点因转发数据量较大过早死亡,缓解Sink中心区域节点沦陷问题。
3 自适应半径的分簇组网算法
3.1 组网阶段
①动态簇首竞争
网络中能量消耗主要与簇的物理空间大小和簇内成员数目有关,簇首的管理半径关系着簇的物理空间大小,因此引入适应值半径,用以调控簇的跨度大小。考虑到簇首作为簇内和簇间数据的转发枢纽,因此应尽可能地选择高能量节点担当。鉴于上述两个因素,定义簇首的选举公式:
(12)
W(i)体现了μi成为簇首的配重价值,值越高则越容易当选簇首。其中调节参数α、β用来调整μi的可达节点集以及其剩余能量对簇首选举的影响程度,存在α+β=1;|TN(μi,ri_ck)|表示μi关于适应值半径ri_ck范围内可达节点集内的邻居节点数量;|TN(μi,ri)|表示μi关于通信半径ri范围内最大可达节点集内的邻居节点数量。
基于W(i)的配重公式,可以看出该选举公式综合考虑了节点的剩余能量Ei以及邻居节点数量|TN(μi,ri_ck)|对μi当选簇首的积极影响。
②簇架构
对任意节点μi∈TN(μj,rj_ck),若满足W(j)>W(i),则节点μj当选为簇首;当选节点μj广播一条簇首消息Message_header(uj,Ej)。普通节点μi收到Message_header(uj,Ej)后,在其通信范围内选择距离最近的μj入簇,需要说明的是对于相同距离的簇首,μi优先加入具有高能簇首的簇。具体流程如下。
Join-cluster(μi,ri)Line 1distance=riLine 2μi wait for receive MessageLine 3while Message_header(uj,Ej)Line 4 if distance>distance(μj,μi)Line 5 distance=distance(μj,μi)Line 6 μi_header=μjLine 7end ifLine 8if distance==distance(μj,μi)Line 9μi_header=μfind(max(Eμi_header,Ej))Line 10 end ifLine 11end whileLine 12return μi_header
算法中Line4～7表示μi收到uj的Message_header(uj,Ej)后,选择距离最近的簇加入;Line8～10在两个相等距离的簇中,μi选择具有高能剩余能量簇首的簇加入,其中find[max(Eμi_header,Ej)]表示高能剩余能量簇首的编号。
3.2 数据通信阶段
簇首节点负责数据转发工作,路由决定着数据被转发次数,因此选择一条最优路径进行数据通信,将有利于减缓簇首节点的能耗。ARCN算法采用单跳与多跳结合的路由方式进行数据通信。成员节点首先将采集到数据传输给簇首节点,簇首节点进行数据融合并进行数据转发,选择一条最优路径将数据发送至Sink。
c0内⊙2内的簇首节点可以直接与Sink节点进行通信,c0/⊙2内的簇首节点多跳的通信方式更加占据节能优势。任意两个可通信的簇首μi,μj∉⊙2之间的通信代价为
(13)
对任意簇首节点μi收到消息Message_header(uj,Ej)后,采用最短路径Dijkstra算法,计算簇首间的通信代价,可以找出向Sink节点数据传输的最优路径,具体流程如下。
Communication(μi,ri)Line 1header_dis=riLine 2μi wait for receive MessageLine 3while μi receive Message_header(uj,Ej)Line 4 if distance(μi,Sink)≥Ro/2Line 5 if distance(μi,Sink)>distance(μj,Sink)Line 6 if header_dis>distance(μj,μi)Line 7 header_dis=distance(μj,μi)Line 8 μi_communication_header=μjLine 9 end ifLine 10 if header_dis==distance(μj,μi)Line 11 μi_communication_header=μfind(max(Eμi_header,Ej))Line 12 end ifLine 13 end ifLine 14 else μi_communication_header=SinkLine 15 end ifLine 16end whileLine 17return μi_communication_header
算法中Line6～9表示簇首节点μi收到其他簇首节点μj广播的消息后,选择靠近Sink节点且距离最近的簇作为中转簇首;Line10～12在两个相等距离中转簇首中,选择剩余能量较高的簇首为中转簇首;如果节点位于Sink节点周围Ro/2内,则直接与Sink节点通信。
3.3 算法流程
作为一种分布式工作的算法,ARCN在网络初始阶段,根据簇首选举公式将节点区分为簇首与普通节点;普通节点根据与簇首节点之间的距离,并参考能量,择优加入最近的簇。对于每个节点μi通过ARCN算法的调度,最终可以实现对一个随机异构传感器网络的快速、效优的组网,对于网络中的任意节点μi可采用ARCN算法实现自适应半径的分簇组网,具体工作流程如下。
ARCN(μi,ck,ri.Ei)Line 1Calculateri_ck,TN(μi,ri_ck),TN(μi,ri),W(i)Line 2Path(μi)=μiLine 3Broadcast(μi,W(i))Line 4for each μj∈TN(μi,ri)Line 5 μi wait for receiver messageLine 6 if (W(i)
算法Line4～9首先判断节点μi是否可以当选为簇首节点,若不能当选则运行Join-cluster算法,得到普通节点μi的通信链路Path(μi);当选簇首的节点μi则执行Communication算法,得到簇间通信的链路信息Path(μi)。通过ARCN算法可用得到全局节点的通信链路Path(μ),完成对随机异构传感器网络的快速分簇组网与路由配置。
4 仿真实验
4.1 场景配置
论文采用MATLAB R2016a平台进行试验,为验证算法的性能,实验在随机异构网络中进行分簇组网。通过与LEACH[5]、URCP[9]及EBCP[12]3种经典方法的对比实验,验证ARCN在提高能量利用率,减缓节点死亡速度以及延长网络生命周期方面的效果。算法假设传感器节点随机部署在S=πR2(R=500 m)的圆形区域内,环数k=3。节点剩余能量与其通信半径成正比例关系。场景与网络参数如表1所示。
为验证网络的寿命,引入网络周期Ts的概念,用于统计网络的寿命。在每个Ts周期内,网络更新运行ARCN算法进行分簇、组网,并设定每个节点在Ts内向Sink通信m=4 000 bit数据,簇首节点的能耗分为两种:一是负责簇内数据的融合和转发;二是作为其他簇首的中转节点,能量消耗采用式(2),参数如表1。当节点μi无法与任何节点构成通信链路时,则认定μi死亡。考虑到试验场景和网络配置的随机性,所有实验数据均采用20次独立实验的平均值,并且保证不同算法间单次实验具有一致的初始场景。
表1 实验参数
4.2 ARCN的分簇效果
对于论文给定的以物理中心位置作为Sink的随机异构传感器网络而言,网络的分簇情况,直接影响着节点数据的通信效率和能量消耗。图3给出了500个初始能量(0.250 J～0.375 J)和通信半径(100 m～150 m)均为异构的传感器网络,在ARCN分簇组网算法的调控下,首轮Ts=1工作时形成的网络结构和通信链路的情况。
图3 分簇效果图(Ts=1)
ARCN中的节点仅在各自单跳范围内,基于邻居信息进行分布式操作,使得簇在位置上应尽可能地分散,从c1～c3环分别形成了9、12和15个簇,基本保证了同环单位空间内具有近似相当数量的簇。作为簇首的高能节点通过适应值半径控制其管理范围,保证簇的大小相对均匀,避免簇内过度长跳。c0中心圆内的簇首数量适度增加为20,以更多簇首来均衡靠近Sink区域的高通信负荷。
随着工作时长的增加,网络周期内能参与通信的节点数量越多,表明网络越稳定,节点的能量利用越均衡,效率越高,因此本实验分别使用LEACH、URCP、EBCP和论文提出的ARCN,通过统计网络在每个时间周期Ts内的能量利用效率,比较4种算法在组网和通信策略设置时,对节点能耗利用的有效性,实验数据统计如图4所示。其中,以当前网络周期内全网总能耗与全网初始总能量的比值,作为当前周期内能量效率的统计量。
图4 能量利用率图
图4给出了全网能量利用率随时间变化的情况。在初始阶段(Ts<40)时,4种算法彼此相对稳定的运行,全网能量利用率没有明显差距。当Ts>40时,由于在LEACH与URCP的簇首选举过程中,缺少对能量Ei的考虑,导致低能节点占据簇首角色提前死亡,能量利用率近似维持在个自的峰值(LEACH峰值为38%,URCP为35%)不再增长,间接表明参与网络的节点过少导致链路不完整,网络已经无法稳定运行。EBCP算法通过代价函数的作用,持续到Ts=50时,达到43%的效率峰值,此后由于缺少组网的可用节点,网络也停止通信工作。ARCN算法能够稳定运行到Ts=70轮左右,是由于引入适应值半径来管理分簇跨度,降低单跳能耗,避免簇首节点能耗过大导致剩余能量过低而无法参与网络构成,从而有效的保证网络的连通性,延长了网络的生命周期。
4.3 节点死亡数量
节点是组成传感器网络的重要因素,若参与组成网络的节点过少,则网络无法稳定运行。本实验分别统计每个网络周期内死亡节点数量(如图5(a))以及中心区域(Sink节点附近)高能耗节点死亡比率(如图5(b)),比较4种算法的剩余节点数量对网络生命周期的影响。
图5 网络剩余节点与中心区域死亡率图
图5(a)可以看出,在Ts<10时,4种算法基本没有节点死亡,表明节点初始能量大于0.25J与高密度的配置方式,使得网络中即使存在高耗能节点也能够维持将近Ts=10轮的生命周期。在Ts>10 轮后,由于没有对高能耗节点进行优化选择,LEACH、URCP和EBCP3种算法开始有节点死亡;ARCN算法节点在Ts>20之后才开始有节点死亡,表明算法在簇首选举时综合考虑了剩余能量以及邻居节点集,能够有效的避免高能耗节点参与较多的数据转发,延缓死亡;在Ts>60轮之后,LEACH、URCP和EBCP3种算法的节点已经全部死亡,而ARCN算法中的节点运行Ts>70轮后才全部能量耗尽死亡,说明算法的选簇、入簇以及簇间通信的方法能够有效的均衡节点能耗,减缓节点死亡速度,延长网络的生命周期。
对于中心⊙2区域的节点寿命情况如图5(b)中所示,可以看出在Ts>10后LEACH、URCP和EBCP3种算法节点死亡速率攀升较快,ARCN算法在20轮之后中心区域的节点开始死亡,且死亡速度相对缓慢,主要在于ARCN算法在中心区域⊙2采用单跳与多跳混合的方法,改善了高能耗节点过早死亡问题,不会出现因中心区域沦陷而造成网络中出现大规模节点不连通的现象。
4.4 网络生命周期
网络的稳定性也是评估一个算法的重要指标,由于节点能量与半径的随机性,网络寿命也随机波动。本实验统计了4种算法的网络生命周期的分布情况,来验证算法的稳定运行能力,实验数据如图6所示。
图6 网络生命周期箱型图
图中可以明显看出LEACH与URCP算法的中值大概在Ts=40轮左右,EBCP算法的寿命中值在Ts=45轮左右,而ARCN算法中值均在Ts=55轮左右;原因在于EBCP与ARCN算法将网络区域等效为一个圆形的检测区域,并且引入了参考圆的概念,使得簇大小以及簇数量相对稳定,从而保证了网络的稳定性。此外 ARCN算法的寿命波动范围与其他3种算法相比相对较小,并且异常值较少,表明ARCN算法对于场景有着较好的普适性。
5 总结
针对网络能耗不均衡、能量利用效率低等问题,论文提出了一种基于自适应簇半径的高效组网算法ARCN。充分利用异构性能引发的邻居数目和剩余能量的双重差异,并作为选举指标,保证高能和服务范围更广的优势节点担当簇首。引入的适应值半径、簇首代价函数矩阵和内环通信模式调整,实现了从簇内到簇间能量优化。由于ARCN算法不依赖于全局信息,利用节点间的异构性能作为分簇组网的基础,提高了方法的适用性。但客观上讲,网络初始阶段对于环数的确定需要预先对服务场景进行了解,未来的研究中,对于自适应环数配置和间距调整也将值得研究。
