一种基于动态竞争半径的非均匀分簇路由算法∗

余修武李 佩刘 永肖人榕张 可

(1.南华大学资源环境与安全工程学院,湖南 衡阳421001；2.铀矿冶放射性控制技术湖南省工程研究中心,湖南 衡阳421001；3.湖南省铀尾矿库退役治理工程技术研究中心,湖南 衡阳421001)

无线传感器网络(WSNs,wireless sensor networks)节点能量有限,且不易更换电源,如何合理高效利用能量,延长网络寿命成为其研究的核心问题之一[1－3]。分层路由采用传感器节点网络分簇和利用簇首进行数据融合的思路,大大减少数据传输过程中对节点的能量消耗,延长网络的生存时间。近些年,逐渐成为各国学者在路由协议层面的研究热点。

LEACH算法作为均匀分簇路由算法的典型代表,采用节点等概率成为簇首的方式平衡网络节点的能耗,但易出现“热区”现象,造成网络过早失效。李成法等[4]利用非均匀竞选半径的概念,使靠近基站的簇相对较小,这样基站附近簇首转发数据的能耗相应降低,从而缓解节点间的能量消耗不均的问题(EEUC)。Sarkar[5]等利用Firefly算法,通过选择最佳簇头来最大化网络的能量效率和节点的寿命,以此提高网络性能。潘蕾娜等[6]提出了一种基于信任与能耗均衡的安全分簇路由协议(SCR-TBE),采用模糊评判模型提升网络的能耗均衡性和可靠性。刘伟等[7]提出了一种基于节点间相关性的能量有效分簇路由协议(BCCP),利用节点间位置相关性与节点剩余能量降低簇内能耗。牛玉刚等[8]提出一种带有重叠区域的路由算法(OMU),该算法中簇首只用于簇内数据的接收与融合,由此减少簇首的能量消耗。以上算法虽在一定程度上缓解节点间能量消耗不均等问题,但其均衡节点间能耗的能力仍有待提升。其他的一些分层路由还有LEACHimproved[9], EIRNG[10], HCRA[11], GECR[12],CHRA[13]。

本文作者结合了LEACH算法的选举簇首的方法,对阈值T(n)做出改进。引入节点与基站距离和节点能量等因素,使得靠近基站的节点成为候选簇首的几率更大,从而靠近基站的候选簇首数更多。对EEUC算法的竞争半径的公式做出改进,引入继任簇首能量消耗因子和前任簇首能量消耗因子,提出一种基于动态竞争半径的非均匀分簇路由协议(Non-uniform clustering routing protocol based on dynamic competitive radius,NCRP)。根据簇内节点和簇首节点的消耗情况,动态的改变簇的的大小,使得簇首间的能量消耗尽可能的均匀,大幅延长网络的生存时间。

1 网络能耗与模型

1.1 网络模型假定

本文假定WSNs具备以下特征:①节点随机地分布在监测区域内,且具有唯一ID。②所有节点同构且初始能量相同,基站位于监测区域外,能量无限且位置固定。③所有节点能够根据接收信息的信号强度值判断与信息发送者的近似距离,从而选取自身的发射功率。④节点能够进行数据融合降低数据传输量。⑤节点能够获知当前自身剩余能量

1.2 能耗模型

发送数据能耗主要分为发送电路和功率放大电路两部分。功率放大电路能耗主要由发射者与接收者之间的距离所决定,依据两者之间距离大小与临界距离的关系可分别采用自由空间模型和多路径衰退模型[14],发送数据能耗如式(1)所示:

式中:d发射距离；l为发送的二进制位数；Eelec(nJ/bit)为射频能耗系数；Efs为采用自由信道模型下的功率放大电路能耗系数；Emp为采用多路径衰退模型下的功率放大电路能耗系数；dinit为临界距离,dinit＝87 m。

式(2)为接收数据能耗

本文所使用的仿真参数设置为:Eelec＝50 nJ/bit；Efs＝10(pJ/bit)/m2；Emp＝0.0013(pJ/bit)/m4；dinit＝87 m。

1.3 数据融合模型

通过数据融合技术减少数据传输量,从而降低簇首转发数据的能量消耗,进而达到降低整个网络的能耗的目的。由于不同区域中数据有较大的差异,在本文仿真中不考虑簇间的数据融合。假设簇内的数据融合模型为:簇首接收每个节点发送的lbit数据,压缩为lbit数据；数据融合能耗设定为ED＝5 nJ/bit。

2 NCRP算法

本协议采用LEACH协议的“轮”循环机制,一“轮”即为一个数据采集周期。每轮可分为非均匀分簇阶段、簇间多跳路由构建阶段和数据转发阶段,其中非均匀分簇阶段又可分为簇首产生和簇的形成两部分,在完成节点的非均匀分簇和簇间多跳路由构建之后再进行数据转发。数据转发阶段可分为簇内单跳传输和簇间多跳传输两部分。由于靠近基站的簇首在完成簇内数据收集后还需承担转发较远簇首数据的任务,导致其能量消耗的速度更快。故本协议对Younis提出的LEACH算法做出改进,使得越靠近基站的节点成为候选簇首的概率更大。间接使得靠近基站形成更多的簇,从而达到均衡离基站远近不同的节点之间的能量消耗,延长整个无线传感器网络的生存时间。

2.1 第一轮非均匀分簇

根据LEACH算法提出的概率式,加入节点与基站距离等因素对产生候选簇首的概率进行调节,即:

式中:r表示当前的回合数,G是r前1/P回合未当选候选簇首的节点集合,P表示候选簇首数占总节点数的比例,dmax和dmin分别表示无线传感器网络之中节点与基站的最大距离和最小距离,d(Ni,BS)表示节点与基站的距离,Et(i)表示节点Ni初始总能量,Er(i)表示节点当前所剩能量。采用该概率计算公式,越靠近基站的节点,成为候选簇首的概率越大,从而使得靠近基站的区域形成更多的簇,簇的规模也越小,间接达到非均匀分簇的目的。

在网络部署完成后,基站以给定的功率向全网广播一个信号,用以各节点计算与基站的大致距离。节点Ni使用式(3)计算其自身成为候选簇首的概率,而后节点Ni随机选取一个介于0～1之间的数,若该数小于Tn(i)则Ni当选为候选簇首,否则进入睡眠状态,待簇的形成阶段被唤醒。

定义1定义一继任簇首能量消耗因子,为

式中:Et(i)表示候选簇首Si初始总能量,Er(i)表示节点当前所剩能量。

定义2定义一前任簇首能量消耗因子σ,根据上一轮的同一簇的簇内节点与簇首能量消耗情况对下一轮的簇的规模进行调节。σ与上一任簇首的能量消耗Ec(j)成正比关系,与上一轮簇内成员节点消耗能量的均值成反比关系,为

式中:Ec(j)表示前任簇首Sj在上一轮数据采集周期所消耗的能量,表示上一轮以Sj为簇首的簇内成员节点消耗能量的平均值。

为了使距离基站较近的簇具有较小规模,在距离基站较近的区域应生成更多的簇首。因此,候选簇头节点的竞争半径应正比于它与基站的距离的函数关系.预先给定一Ro用于控制候选簇首的竞争半径处于一个合理的范围,以防产生过小或者过大规模的簇,进而使得簇内数据转发能耗趋于合理。综合考虑候选簇首当前所剩能量和上一轮的簇内能量消耗情况,重新定义候选簇首Ci的竞争半径Rc(i)计算公式为

定义3

式中:dmax和dmin分别表示无线传感器网络之中节点与基站的最大距离和最小距离,d(Ci,BS)表示候选簇首与基站的距离,c1、c2和c3都是介于0～1之间的常数,且满足关系c1＋c2＋c3＝1,可知Rc(i)介于0～Ro之间。

由于候选簇首竞选成为最终簇首采用的局部竞争的方式,参与竞选的候选簇首都保有一个邻簇首信息表,详见表1。

表1 候选簇首邻居节点信息表

定义4在NCRP簇首竞选算法中,候选簇首Ci的邻居簇首集合NCi为NCi＝{Cj｜Cj是候选簇首,且d(Ci,Cj)

规则1在竞选中,候选簇首Ci必须先比较邻簇首集合NCi中的节点和自身的剩余能量的大小,需等待剩余能量比自身大的候选簇首先做出是否成为最终簇首的决定,而后Si才做出决定。

规则2在竞选过程中,若候选簇首Ci的邻簇首集合NCi中的节点都退出竞选,则簇首Si宣布竞选获胜直接成为最终簇首。

规则3在竞选过程中,若候选簇首Ci宣布其竞选获胜,则在Ci的竞争半径内的所有候选簇首均要退出竞选过程。

候选簇首竞选出最终簇首参照参考文献[4],所有候选簇首以Ro为半径,采用相同的频率广播竞选消息COMPETE_HEAD_MSG,该消息包含节点的ID、节点的竞争半径以及节点当前所剩余的能量,候选簇首根据收到的相邻候选簇首竞选消息的强度判断两节点之间的近似距离,而后节点依据定义1构建邻簇首集合NC,并保有邻簇首信息表。节点等待邻簇首集合中所有能量比自身高的节点先做出是否担任最终簇首的决策。若Ci发现邻簇首集合中的节点能量都小于自身,则Ci直接成为最终簇首并广播消息FINAL_HEAD_MSG。若候选簇首Ci收到来自Cj广播的竞选获胜消息FINAL_HEAD_MSG,首先判断自身与候选簇首Cj之间的距离是否大于候选簇首Cj的竞争半径Rc(j)。若大于,节点Ci将Cj从邻居簇首集合中移除,继续等待邻簇首集合中比自身能量高的节点做出是否担任最终簇首的决策。若小于,则Ci立刻退出竞选并广播消息QUIT_ELECTION_MSG告知它的邻簇首。若Ci收到来自Cj退出竞选的消息,则Ci将Cj从邻居簇首集合中移除,并继续等待。若Ci的邻簇首集合中所有能量比自身高的节点都退出了竞选,Ci直接成为最终簇首并广播消息FINAL_HEAD_MSG。

在第一轮最终簇首产生后,之前未成为候选簇首被唤醒,所有竞选出来的簇首以Ro为半径,采用相同的频率广播招募簇成员消息RECRUIT_MSG。其他节点根据收到的消息RECRUIT_MSG的信号强度,选择信号强度最强的簇,并广播消息JOIN_CLUSTER_MSG用于通知该簇首。

由于第一轮非均匀分簇比较繁琐,其中成簇算法产生过多的信息开销。故之后的非均匀分簇在第一轮分簇形成的基本格局下简化候选簇首的产生,以降低数据转发以外的算法开销,延长网络生存时间。

2.2 第二轮及后续轮次非均匀分簇

在第一轮数据采集周期结束后,在第一轮后的每一轮数据采集周期前设定一个等待时间用于簇首判断是否需要重新产生候选簇首。若在等待时间过后簇首未收到消息ELECT_MSG,那么将由每个簇首在簇内r前1/P回合未当选簇首成员节点中,选择能量最高的个节点成为下一轮簇首,并广播FINAL_HEAD_MSG通知簇内节点。为减少节点能耗开销,在数据采集周期内的最后一次数据采集时,选择簇首所需的节点信息采用“捎带”的方式与采集的数据一起传输。若簇内不存在r前1/P回合未当选簇首成员节点,分簇过程参照第一轮分均匀分簇。通过该方式可减小非均匀分簇的能量开销,延长网络生存时间。

2.3 簇间多跳路由

NCRP协议采用簇内单跳和簇间多跳的方式进行数据传输。每个簇首需要从邻居簇首中选择一个作为其中继节点,转发至基站。由于不同簇之间的数据差异性较大,本协议簇间通信不进行数据融合,只转发接收到簇首数据的完整数据包。

NCRP的簇间多跳路由建立采用文献[14]中的贪婪算法建立最小代价函数来建立簇间多跳路由。簇首Sj运用贪婪算法在其邻居簇首中选择中继节R Ni,中继节点RNi在所有候选节点中具有最小代价函数,代价函数定义如下:

式中:neighor(si)表示簇首Si的邻居簇首剩余能量均值,Ecurrent(sj)表示簇首Sj的剩余能量；Nnon－CH(Sj)表示簇首Sj的成员节点数,Nnon－CH(si)表示簇首Si的邻居簇首成员节点数量的均值；dsi－sj表示簇首Si到簇首Sj的距离,dsj－BS表示簇首Sj到基站的距离,d0表示簇首到基站的临界值；α,β,γ为加权系数,且满足α＋β＋γ＝1。因此,cost(RNi)＝min{cost(i,j)}。如果簇首Si的中继节点是本身,则直接发送数据到基站；否则,簇首Si发送数据到中继节点RNi,当每个簇首都找到中继节点,簇间多跳路由建立。

2.4 数据转发阶段

数据转发包括簇内单跳和簇间多跳两部分,在簇间多跳路由建立后,簇成员节点将采集的数据转发给簇首,簇首再将收到的数据进行融合后转发至其中继节点。直至所有簇首将接收到的数据转发到对应的中继节点,表示数据转发完成,数据采集周期结束。算法流程图如图1所示。

图1 流程图

3 算法分析

性质1NCRP协议的消息复杂度为O(N),N为总节点数。

证明在非均匀分簇算法中,节点成为候选簇首的概率为T,共有N×T个节点成为候选簇首并广播N×T条COMPETE_HEAD_MSG消息。设共竞选出K个最终簇首,广播K条FINAL_HEAD_MSG消息,(N×T－K)个候选簇首退出竞选并广播(N×T－K)条QUIT_ELECTION_MSG消息。K个簇首广播K条RECRUIT_MSG消息,(N－K)个节点广播(N－K)条JOIN_CLUSTER_MSG消息。所有总的消息开销为

即消息复杂度为O(N),此处分析的是第一轮分簇的消息复杂度,实际上只有满足特定条件才会选取该分簇方式,通常情况会选取消息复杂度更低的后续轮次分簇的方式。尽管消息复杂度分析主要在分簇阶段,但在实际应用中还应考虑簇间多跳路由和数据转发的信息开销。

4 实验结果及分析

本文利用MATLAB R2017a对NCRP算法进行模拟,与LEACH和EEUC进行对比。400个节点被随机分布在200 m×200 m的正方形区域内,为了更好与LEACH和EEUC做对比,本文选取与EEUC相同的参数设置,详见表2。

表2 模拟参数表

为了评价NCRP算法的性能,分别从簇首的分布、簇首消耗能量的方差、死亡节点的分布和网络的生存时间等方面与LEACH和EEUC算法进行对比分析。

4.1 簇首的分布

如图2(a)、图2(c)可以看出,由于LEACH和EEUC都是采用阈值的方式产生簇首,节点的成为簇首的概率都相等故产生的簇首随机分布在网络中。反观图2(b),由于NCRP算法引入节点与基站的距离因素和节点能量对阈值公式进行改进,靠近基站的节点有更大的几率成为簇首。进而使得更多靠近基站的节点成为簇首,担负起转发外围簇首数据的任务。

图2 簇首分布图

4.2 簇首消耗能量的方差

图3为三种算法的簇首消耗能量的方差。在仿真实验中,随机抽取三种算法未出现死亡节点的前的10轮,用簇首消耗能量的方差衡量三种算法的簇首间能量消耗的均衡情况。发现三种算法中LEACH算法的方差最大,说明LEACH并没用采取相应的方法对簇首间的能量消耗均衡。EEUC和NCRP算法相比于LEACH算法方差都小很多,说明EEUC和NCRP算法在簇首间能量消耗均衡方面远优于LEACH算法。NCRP算法方差略低于EEUC,说明NCRP在处理簇首间能耗差异方面优于EEUC算法。

图3 簇首消耗能量的方差

4.3 死亡节点的分布

节点间能量消耗不均是致使无线传感器网络过早失效的原因,图4为三种算法在50%节点死亡时的死亡节点分布图(×为死亡节点)。

从图4(a)可以看出,LEACH算法远离基站的死亡节点数量大于靠近基站的死亡节点数量,这说明LEACH算法节点间能耗均衡能力较差。反观图4(b)和图4(c),死亡节点分布较为均匀。说明NCRP和EEUC算法在均衡节点能耗方面远优于LEACH算法,更有利于延长网络的生存时间。

图4 死亡节点分布图

4.4 网络生存时间

图5为三种算法的网络生存时间,LEACH算法第一个死亡节点出现在第268回合,EEUC算法是第742回合,而NCRP算法第一个死亡节点出现在第986回合,性能较LEACH提升了189.93%,较EEUC提升了32.88%。LEACH算法节点死亡50%出现在第423回合,EEUC是在第762回合,而NCRP算法节点死亡50%出现在第1023回合,性能较LEACH提升了88.42%,较EEUC提升了34.25%。这说明NCRP算法在竞争半径的公式引入距离和能量等因素,使得竞争半径RC更加趋于合理,有效地均衡了网络中节点的能耗,延长了网络的寿命。

图5 网络生存时间

5 结论

本文提出一种动态竞争半径的非均匀分簇路由协议,在第一轮选举候选簇首利用改进过的阈值公式可以使靠近基站区域产生更多的簇首用于转发其他簇首的数据,有效均衡了整个传感器网络能量消耗。在NCRP算法中,在竞争半径的计算中引入继任能量消耗因子和前任能量消耗因子,使得竞争半径更加合理。仿真实验表明,NCRP能够有效均衡节点间能耗,延长整个网络的存活时间。