基于节点轮换的无线传感器网络节能策略研究

高 洁,吴宪海,文琼瑶

(1.西昌学院预科教育学院,四川 西昌 615000;2.63798部队,四川 西昌 615000)

无线传感器网络多应用在环境危险,面积空旷的野外作业。用电池供电的节点一旦部署组成网络开始工作,将无法在部署环境中更换电池[1-2]。节点的主要作用是完成信息的传输,通过多跳传输方式最终将信息传输到基站。大量研究表明,节点无线通信模块的能量消耗水平直接决定了节点的使用寿命[3-4]。大量学者致力于如何均衡整个网络的能源消耗研究,优化无线传感器网络结构,延长整个网络的生命周期[2-3,5-6]。Jiang[5]基于构造节点的最大独立集提出冗余节点休眠的思想。利用最少数量的节点达到网络的全覆盖。作者提出利用构造最小生成树寻找节点最大独立集的多项式时间近似算法。当删除最大独立集中的节点后,网络中剩余节点可以保证整个网络的全覆盖。Yang[6]将网络中节点的剩余能量作为点的权值。利用改进的贪婪算法寻找最小加权独立集。保证最小加权独立集中的冗余节点首先休眠,而网络中工作的节点剩余能量水平相对较高,并且满足整个网络的全覆盖。在延长网络生命周期的前提下,同时使得网络中每个节点的能量消耗得到均衡。有向传感器网络由于在节点属性上增设了有向属性而使其拥有更为广阔的实用意义。针对重点区域覆盖不足的问题,Tan等提出了一种改进的非均匀有向传感器网络节点部署方法,引入部署中心和矢量引力的概念,增加斥力的非均匀部署属性,从而加强区域内的覆盖质量[7]。文献[8]对网络节点均衡性进行准确合理的控制,可保障网络在入侵后还能保持良好的运行状态。利用局部最小生成树理论控制网络结构,将选择链路节点的权值视为新的加权函数,在组建网络拓扑模型时考虑了节点间的通信消耗和节点剩余能量,依据节点能量的变化对网络拓扑结构进行动态调节,利用通信损耗链路作为衡量标准,同时考虑中继节点的剩余能量情况,避免了网络入侵后部分节点能量过早耗尽。Tian等[9]提出了自发的检测节点休眠算法。当节点的探测范围可以由其邻居节点的探测范围所覆盖,这个节点可以认为是冗余的,就自动进入休眠状态。在一个时间周期内,节点自发的醒来检测是否有邻居节点覆盖其探测区域,从而决定是否休眠。但是这种算法中,邻居节点由于自发地醒来检测导致能量的浪费。针对无线传感器网络节点覆盖不均匀导致覆盖率低下的问题,Wu[10]提出了一种基于改进自适应粒子群优化算法的覆盖优化方法。建立WSN 覆盖优化的数学模型;然后将进化因子和聚合因子引入粒子群优化(PSO)算法中的惯性权重系数,接着在算法迭代过程中引入碰撞回弹策略保证粒子群的多样性,克服改进粒子群优化算法在优化后期容易陷入局部最优的弱点。文献[11]提出了一种工作量加权路由模型以提高无线自组织网络的生存时间。在网络信息传输的过程中,综合每条链路的业务工作量对网络链路进行加权,建立最小代价传输数学模型。该模型通过降低工作较为繁忙节点的信息转发概率,从而到达均衡节点能耗、延长网络生存时间的目的。文献[12]引入覆盖率均衡思想,将各传感器节点对目标区域覆盖率的均衡性与节点剩余能量的均衡性作为筛选因子,且通过调节传感器节点的剩余能量与其平均覆盖率的比例关系,筛选出最大不相关且代价最小的网络覆盖子集,以尽可能少的节点实现对区域的覆盖。文献[13]针对多冗余通路设计的无线传感器网络故障预防方法存在工作状态冗余节点过多、能量大量浪费的问题,提出一种基于节点健康度的冗余通路控制方法。该方法利用汇聚节点收集网络内所有节点能量状态,计算节点健康度等相关参数,使用A-Star算法选择最优工作通路,控制其余冗余通路分批轮流休眠,从而达到减少和均衡网络工作过程能量消耗、预防某些节点能量提前耗尽导致网络能量故障发生的目的。文献[14]提出位于基站周围的节点由于负责所有探测数据的转发任务而能量消耗水平较高。为了均衡基站周围节点的能量消耗,提出一种合理有效的节点轮换休眠机制。使得网络中大量冗余节点处于休眠状态,从而减少基站周围重要节点的负载。

1 网络能量优化策略研究

考虑网络中存在高密度的静态传感器节点集V={vi|i=1,2,…,N}和唯一的基站BS。位于基站周围且直接与基站通信的节点由于向基站转发全部数据的任务,能量消耗比其他节点快,这样的节点被称作瓶颈节点。本文中采取M. Bhardwaj[15]对网络生命周期的定义,认为网络的生命周期为网络中出现第1个覆盖漏洞的时间。

为了便于研究并简化模型,提出以下假设:①节点以密度为ρ的泊松分布随机布撒在一个圆心为O半径为R的圆形网络区域G中,基站位于圆心O上。②传感器节点的最大通信半径为Rc,最大探测半径为Rs,且有Rc,Rs≪R。那么,节点vi的探测范围可表示为Pi={p∈R2|d(p,vi)≤Rs},其中d(p,vi)表示点p到vi的欧氏距离。③节点可以通过一定的方法(如GPS全球定位系统)知晓基站及自身地理位置。

网络中的数据流均来自于区域S1和S2并必须经过S2才能传输到基站。因此,瓶颈节点大多位于中心,如图1所示。为了平衡整个网络的能量消耗,关键是平衡瓶颈节点的能量消耗。

R=10,r=1,ρ=4/π,λ=1,ε=1,p=0.5图1 位于基站周围节点的能量消耗

假设S1区域的节点均采取多跳传输的方式。由于S2区域中的同时存在多跳传输节点和一跳传输的节点,为了清楚地计算区域S2中采用一跳传输方式的节点的数量和其他多跳传输的节点数量,本文定义网络中的直接传输概率p(0

接下来,将对节点的平均能量消耗进行数学描述,首先提出以下假设:

ε(D):位于距离基站D的节点将每单位数据传递到基站所需的能量。

λ:节点向基站发射信号的频率。在本文中,认为节点发射数据的频率为常数。

由于越靠近基站的节点将承担更多的转发任务,其能量消耗越快。对于S2中的瓶颈节点,取距离基站最远的瓶颈节点的距离计算节点平均能量消耗才能得到S2中可休眠的冗余节点的下界。

在Luo J[16]几何模型的基础上,节点ni的平均能量消耗与区域S1和S2的面积有关,如图2所示,S1和S2的面积可表示为:

(1)

S1=π[R2-r(D)2]

S2=πr(D)2D

(2)

所以,S2区域中的节点在一段时间内的平均能量消耗可以表达为:

(3)

式中:β(D)=2arcsin(r/D)。在本文中,假设网络中所有节点的通信半径都相同Rc=r。

D表示节点n到圆心O的距离,r为探测半径图2 网络模型

从图1中所示,位于基站周围的瓶颈节点大量死亡后,通过瓶颈节点传输的数据将无法传递到基站,将使网络中出现覆盖空洞。因此瓶颈节点的使用寿命直接影响整个网络的生命周期。如图3所示,由于网络中的节点密度高,多个节点同时探测到相同的数据信息并以频率λ传输给S2区域内中的瓶颈节点,这些节点休眠后并不影响网络的连通性。大量冗余节点加重S2区域中瓶颈节点的负载,不利于网络的生存。

图3 瓶颈节点数据转发模型

最优的能量均衡模式是在网络运行状态下,目标区域的任意位置当且仅当被一个节点的探测区域覆盖。网络中大部分节点相继失效时,网络中同时出现大面积的覆盖空洞,网络寿命宣告结束。而在实际情况下,总是存在部分节点由于能量消耗水平高而先行死亡,网络中同一区域被多个节点的探测范围同时覆盖。

那么,如果可以寻找到网络中最大数量的冗余节点并使其休眠,将极大的降低瓶颈节点转发数据的负载,进而降低其能量消耗。同时整个网络的能量达到最大程度的均衡。

因此,基于式(3),将可休眠的冗余节点数量作为变量,建立本文研究的优化模型,通过优化算法即可找到可休眠的节点集。

为了可以寻找到休眠节点集,将位于S2区域中的节点进行编号,Vneck={ni}(i=1,…,n)。

Dni=d(ni,BS):表示节点ni与基站之间的距离。

xni={0,1}:节点ni的状态变量。xni=1表示ni处于休眠状态;xni=0表示ni此时处于唤醒状态。

fni(x):表示距离基站Dni的节点ni的平均能量消耗。

Etotal(ni):节点的工作初始的总能量。

Eremnant(ni):持续工作t时间后,节点的剩余能量。

位于S2区域中的瓶颈节点的实际平均能量消耗可以表示为:

(4)

除了考虑均衡整个网络的能量消耗,在本文中还考虑延长单一节点的使用寿命。所以在寻找可休眠的冗余节点时,选择剩余能量较少的节点首先休眠,可以有效地延长单个节点的使用寿命。

令ω=(ω1,ω2,…,ωn)T为节点剩余能量权值。在初始状态时ω=(ω1,ω2,…,ωn)T=(1,1,…,1)T。

对于节点ni的剩余能量权值wi可以表示为:

建立同时优化整个网络寿命和单一节点寿命的多目标优化模型为:

(5)

s.t.

Coverage(G)≥C

(6)

xj={0,1}

(7)

xj≠N(xj)

(8)

j∈S1

(9)

式中:x(Dni)=(x1,x2,…,xn)T表示节点状态的0-1矩阵,winf为所有节点剩余能量指标的最小值。

式(6)表示网络的覆盖集coverage(G)满足不小于决策者所需的最小覆盖常数指标C(0

研究多目标优化问题的一个基本途径是将多目标优化问题转化为单目标优化问题,利用已成熟的单目标优化问题求解方法解决问题。这种处理方法称为多目标规划问题的标量化处理[17]。

引入权向量α=(α1,α2)T,且满足α1,α2≥0,α1+α2=1。记极小化问题为:

定理1[14]设X⊆Rn,f:X→Rn,α=(α1,α2)T是常数向量。

式中:E(f,X)为全体Pareto有效点构成的集合,Ew(f,X)为全体Pareto弱有效点构成的集合。

②与①证明过程类似。

由定理1可知,求解极小化问题(Pw)和原问题是等价的。

首先,将优化问题(5)进行标量化处理,对多目标优化问题(5)进行线性加权。

模型中将网络的平均能量消耗和单一节点寿命作为优化目标。在问题中,希望降低网络的平均能量,也需要降低单一节点的寿命。在优化问题中,自然可以认为两个目标的重要度相同。由于可以认为多目标规划问题的两个方面权重是相同的,设α=(α1,α2)T=(0.5,0.5)T。

(10)

(11)

(12)

s.t. (winf-w)Txnj≤ε

(13)

Coverage(G)≥πR2

(14)

xnj∈{0,1}

(15)

nj∈S1

(16)

2 节点轮换休眠能量优化策略算法

提出的能量优化策略算法用以求解以上NP-难问题,使得大量可休眠节点进入休眠状态,也就是求解以上优化模型的方法,如图4所示。

图4 冗余节点休眠的能量优化策略算法流程图

3 算法复杂度分析

定理2算法的复杂度为O(nk)。

证明标记节点和剩余能量的复杂度是多项式的O(n),判别节点度的复杂度是O(n),在最小节点度的节点集中判别能量为最小的复杂度为O(n),即找到最小节点度最小能量的节点复杂度为O(n3)。重复调用算法复杂度为O(nk)。

值得说明的是,当节点密度越大时,算法收敛的速度反而越快。也就是说k值是可控的。算法依然可以在多项式时间内完成。

4 仿真分析

为了试验模型应用节点轮换策略是否对于网络延长生命周期起到一定的作用,本文采用MATLAB 7.0作为仿真工具,运行环境为内存512 Mbyte,操作系统为win7的PC机。

仿真试验1 设置节点的探测半径为1,节点数为n=1 225个,网络区域为半径R=50的圆形区域。

表1中,选取位于节点不同位置的节点,对应的可休眠冗余节点数量不同。而且遵循以下规律:随着节点与基站的距离D越大,其对应的冗余节点的数量会越少。瓶颈节点位于基站周围,距离基站较近的可休眠的冗余节点的数量较多,当这些冗余节点休眠后,瓶颈节点的负载明显减少。当整个网络的可休眠节点周期性的处于休眠状态,网络的生命周期将会明显延长。

表1 距离基站不同距离节点对应可休眠冗余节点个数

仿真试验2 设置节点探测半径为1,节点与基站的距离越远,节点的能量节约率越高,因为节点与基站距离越近,虽然大量节点休眠,但唤醒的次数也增加,而距离基站较远的节点,休眠的节点数量较少,休眠后唤醒次数降低,能量节约较多。但距离基站较近的节点也有20%以上的能量得到节约。

图5 相同探测半径节点对应可休眠节点数与能量节约率

仿真实验3 如图6所示,运行节点休眠策略前后的网络平均能量消耗情况比较。虚线条表示网络中原本节点的能量消耗情况。实线条表示网络中节点休眠后的平均能量消耗情况。那么,网络的平均能量消耗明显降低。

图6 节点能量消耗比较

仿真实验4 对瓶颈节点的能量进行衡量,从图7可以发现,瓶颈节点的能量在网络相同运行时间,有节点休眠策略的网络瓶颈节点的能量消耗更慢。

图7 两种情况下瓶颈节点能量变化图

4 结束语

为了确保网络具有更长的工作时间,本文同时考虑到单一节点的工作时间和整个网络的生命周期,提出了多目标决策网络优化模型,并将其单一目标化。设计了一种最小能量节点轮换休眠策略,解决了多目标决策网络优化的NP难问题,算法复杂度为多项式的,可以有效的延长网络的生存时间和单一节点的寿命,通过试验表明,本文算法可以使WSN的能量节约20%以上,距离基站更近的节点,大量的冗余节点通过算法轮换休眠,大大降低了瓶颈节点的通信次数,使其能量消耗更加均衡。因此,本文设计的算法在一定程度砂锅内有效的提高了整个网络的性能。

[1] Geoffrey Werner Allen,Jeff Johnson. Monitoring Volcanic with a Wireless Sensor Network[C]//Proceeedings of the Second European Workshop on. 2005,1:108-120.

[2] Ma C,Liu H W,Zuo D C,et al. Tsinghua Univ. In Chinese,2011,51:1418.

[3] Akyildiz I F,Su W,Sanakamaniam Y,et al. Wireless Sensor Networks:A Survey[J]. IEEE Computer Networks,2002,40(4):102-114.

[4] Hill J,Szewczyk R,Woo A,et al. System Architecture Directions for Networked Sensors[C]//International Conforence on Architectural Support for Programming Languages and Operating Systems. USA. 2000,9:93-104.

[5] 蒋杰,方力,张鹤颖,等. 无线传感器网络最小连通覆盖集问题求解算法[J]. 软件学报,2006,17(2):175-184.

[6] 阳娣兰,谢政,陈挚,等. 无线传感器网络中能耗均衡的覆盖控制算法[J]. 计算机工程与科学,2008,30(12):15-18.

[7] 谭励,杨朝玉,杨明华,等. 改进的非均匀有向传感器网络节点部署方法[J]. 传感技术学报,2015,25(12):1835-1840.

[8] 徐力,车念. 网络节点均衡性优化控制模型仿真研究[J]. 计算机仿真,2017,34(4):271-275.

[9] Di T,Georganas N D. A Node Scheduling Scheme for Energy Conservation in Large Wireless Sensor Networks[J]. Wireless Communications and Mobile Computing,2003,3(2):271-290.

[10] 吴意乐,何庆,徐同伟. 改进自适应粒子群算法在WSN覆盖优化中的应用[J]. 传感技术学报,2016,29(4):559-565.

[11] 刘半藤,周莹,陈友荣. 基于加权路由思想的无线自组织网络生存时间优化算法研究[J]. 传感技术学报,2017,30(3):463-466.

[12] 秦宁宁,陈家乐,丁志国. 覆盖率均衡区域覆盖算法[J]. 传感技术学报,2015,28(4):578-584.

[13] 宋佳,罗清华,彭喜元. 基于节点健康度的无线传感器网络冗余通路控制方法[J]. 物理学报,2014,12(63):(128401)1-11.

[14] 高洁,吴延红,白建侠,等. 无线传感器网络最小覆盖能量优化算法[J]. 传感技术学报,2016,29(9):1435-1440.

[15] Bhardwaj M,Chandrakasan A P. Bounding the Lifetime of Sensor Networks via OPTIMAL ROLE ASSIGNments[C]//Proc of the 21st IEEE INFOCOM. 2002,3(3):1587-1596.

[16] Luo J,Hubaux J P. Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks[C]//Proceedings of IEEE INFOCOM,2005,3:1735-1746.

[17] 徐玖平,胡志能,中级运筹学[M]. 北京,科学出版社,2008.