面向异构网络的基于k-覆盖的休眠调度算法*

王自力,郑 鑫

(1.驻马店职业技术学院信息工程系,河南 驻马店 463000;2.黄淮学院信息工程学院,河南 驻马店 463000)

面向异构网络的基于k-覆盖的休眠调度算法*

王自力1*,郑 鑫2

(1.驻马店职业技术学院信息工程系,河南 驻马店 463000;2.黄淮学院信息工程学院,河南 驻马店 463000)

异构无线传感网络WSNs(Wireless Sensor Networks)的多数监测应用要求兴趣区域FoI(Field of Interest)是k覆盖(k-cover),且k≥1。而冗余节点被安排为休眠,进而最小化能量消耗。为此,提出面向异构网络的基于k-覆盖的冗余节点休眠算法k-CRSS(k-cover based sleep Scheduling algorithm for redundant node)。k-CRSS算法引用概率方法判断节点是否为冗余节点,并推导判断一个节点是否为冗余节点的概率表述式。然后,引用调度算法识别所有冗余节点,并让它们进行休眠,且在FoI内不出现覆盖空洞。k-CRSS算法属分布式算法,并无需任何地理信息,仅通过少量控制消息收集邻居节点信息。实验数据表明,k-CRSS算法通过调度算法减少了活动节点数,进而延长了网络寿命。

无线传感网;覆盖;冗余节点;调度算法;网络寿命

无线传感网络WSNs(Wireless Sensor Networks)由多个微型传感节点构成,这些节点通过感测环境,实现检测兴趣区域FoI(Field of Interest)的目的。目前,WSNs广泛应用于康复医疗、战场监测等。由于WSNs常部署于野外恶劣环境,当节点能量消耗殆尽,也不便以更换电池或充电。因此,常通过密集部署传感节点,进而延长WSNs的网络寿命[-4]。

依据传感节点感测距离或通信半径的不同,可将传感节点划分不同类型,这类WSNs也称为异构WSNs[5]。在异构WSNs中,由于节点通信范围不同,可能节点间的能量殆尽时间也不同,这有利于延长网络寿命,因此,本文以异构WSNs为研究对象。

任何WSNs应用都涉及对FoI的监测,而覆盖是衡量WSNs服务质量的重要参数之一。FoI内任何事件若能被监测,当FoI内事件发生地在传感节点的感测范围内时,传感节点就能感测该事件。如果FoI内点被k个活动节点感测,则此点称为k覆盖(k-cover)[6]。如果FoI内每个点均为k-cover,则将FoI称为k-cover[7]。

在维持FoI的k-cover的同时,最小化能量消耗,进而延长网络寿命是非常重要的。延长网络寿命常采用的方法就是识别网络内的冗余节点,然后将冗余节点休眠[8-11]。当节点的感测范围内每点已k-cover时,则认为该节点为冗余节点。

此外,多数文献常假定每个传感节点均知道自己位置信息,而实际上这是不切实际的。基于全球定位系统GPS或三角定位算法的位置获取方法要么是成本高,要么是在多数应用场景不具有可操作性。

据此,本文在无需获取传感节点的位置信息或相关信息条件下,提出面向异构网络的基于k-cover的冗余节点休眠算法k-CRSS。k-CRSS算法引用概率方法量化FoI内点的覆盖冗余,然后再推导出传感节点的覆盖冗余概率,最后再针对冗余节点,采用分布式休眠调度算法。实验数据表明,提出的k-CRSS算法在保证FoI是k-cover的同时,减少了活动节点数,降低了能耗,进而延长网络寿命。

1 系统模型

假定传感节点分布于3-D FoI区域ψ[8-9],且ψ呈正方形。在ψ中,依据传感节点的感测距离或通信半径,将它们划分t类。假定Ni为第i类传感节点的节点数,且网络内总的节点数N:

(1)

类似地,假定节点si的通信区域也为圆形区域,且表示为R(si,Ci),其中Ci为节点的通信半径。

定义1感测邻居,通信邻居和双邻居 对于任何两个传感节点si、sj,且1≤i,j≤t。如果i≠j,并且Si≠Sj或者Ci≠Cj。如果si与sj间距离d(i,j)小于Si+Sj,则将sj称为si的感测邻居,或者si称为sj的感测邻居。类似地,如果d(i,j)小于Ci+Cj,则将sj称为si的通信邻居,或者si称为sj的通信邻居。如果它们既是感测邻居又是通信邻居,则它们就称为双邻居。

图1显示了节点si和sj的感测区域和通信区域范围,其中黑色虚线圈是通信区域,而黑色实线圈是感测区域。

图1 不同节点的感测和通信示意图

定义2对于两个邻居传感节点si和sj,取δij=min(Si+Sj,Cj)称为有效协调距离。以si为圆心以δij为半径的区域R(si,δij)称为有效协调圆。

定义3k-覆盖率 FoI的k-覆盖率表示为ηk,其等于FoI区域内被k-覆盖的面积与FoI区域总面积之比。

2 k-CRSS算法

2.1 点覆盖冗余

任意两个相近的传感节点,它们间覆盖区域可能存在交叉重叠,如图2所示的黑色的阴影部分,其中q表示事件发生点,且q∈R(si,Si),离si距离为d。而点q也同时被节点sj覆盖。为此,用Aj(q)表示此类事件。

图2 覆盖交叉重叠示意图

(2)

注意到P[Aj(q)]依赖于q和sj的位置和有效协调圆R[si,min(Cj,Si+Sj)]。

P[Aj(q)]仅反映了只有一个双邻居节点sj与节点si发生了覆盖重叠的概率。接下来,推导当有多个双邻居节点发生覆盖重叠的概率Bj,ω(q)。

由于假定节点均匀随机分布,n个双邻居节点中有r个节点是属于j类型的事件发生概率ρr,n为:

(3)

式中:nj/n表示节点为j类型的概率。

类似地,点位置q被r个j类型节点中的ω个节点覆盖的概率ρω,r,且ω≤r≤n,可定义为:

(4)

因此,Bj,ω(q)的概率可表述为:

(5)

接下来,令Ck(q)表示在第i类传感节点的区域范围内点q至少被它的k个任意类型的邻居节点覆盖。例如,当k=2时,事件C2(q)的概率:

P[C2(q)]=1-P(n)-P(1)

(6)

式中:P(n)表示点q没有被任何邻居节点覆盖的概率,而P(1)表示点q被一个邻居节点覆盖的概率。

由于传感节点间彼此独立,可得:

P(n)=P[B1,0(q)]P[B2,0(q)]…P[Bt,0(q)]

(7)

而P(1):

P(1)=P[B1,1(q)]P[B2,0(q)]…P[Bt,0(q)]+
P[B1,0(q)]P[B2,1(q)]…P[Bt,0(q)]+
⋮
P[B1,0(q)]P[B2,0(q)]…P[Bt,1(q)]

(8)

(9)

(10)

(11)

2.2 传感节点的冗余

(12)

2.3 状态切换

k-CRSS算法将时间划分不同的轮,每个轮由两阶段构成:初始阶段和感测阶段。在感测阶段,所有的活动节点一直感测环境数据,直到下一轮。

此外,传感节点有3种状态,分别为活动Active、等待Wait和休眠Sleep。在活动状态时,传感节点负责感测数据,并与邻居进行通信。当节点是冗余的,但仍处于通信状态时,它就进入等待状态。而处于休眠状态的节点不感测环境,也不进行通信,即进入保存能量阶段。

2.3.1 邻居表的建立

在每一轮开始,所有节点均为活动状态。它们给所有邻居节点广播HELLO消息,其包括ID和类型。若节点收到HELLO消息,就将该节点ID和相应的类型存入邻居表中,如表1所示。

表1 邻居表格式

图3 活动状态节点的工作流程

2.3.2 活动状态节点

2.3.3 等待状态节点

当进入等待状态后,该节点继续跟踪HELLO消息,同时启用随机退避定时器。当定时结束后,节点就广播SLEEP消息,其包含自己的ID,通告邻居节点,它即将进入休眠状态。定时时间与节点的剩余能量和随机数有关。传感节点si的定时时间Timeri:

(13)

式中:Einit、Ei分别为节点初始能量和剩余能量,而R为节点产生随机数,且R∈(0,1)。而T为定时时间的基时。

等待状态节点的工作流程如图4所示。

图4 等待状态节点的工作流程

图5 休眠状态节点的工作流程

2.3.4 休眠状态节点

当节点是休眠状态,它就随机设置一个休眠时间。当休眠时间结束,就是广播一个HELLO消息,并进入活动状态。休眠状态节点的工作流程如图5所示。

3 性能仿真

为了更好地分析k-CRSS算法的性能,利用NS-2.34仿真软件建立仿真平台[13]。N个传感节点分布于体积V的FoI,节点的初始能量为60 J,覆盖率ηk=0.99[14]。

3.1 网络寿命随FoI区域变化

本次实验分析k-CRSS算法的网络寿命。实验中,考虑k-覆盖,且k=1,2。依据k-覆盖的定义,k-覆盖是指网络内每个位置点同时由k个传感节点覆盖。

N=1 800个节点随机分布于FoI区域内,同时,只考虑两类节点,即t=2。这两类节点数比表示为N1∶N2。此外,V从803m3到1003m3变化。实验数据如图6所示,其中No-Scheduling表示未引用休眠调度算法。

图6 网络寿命

从图6可知,没有引用k-CRSS算法(No-Scheduling)的网络寿命最低。当不引入k-CRSS算法时,所有节点均处于活动状态,它们的能量消耗过快,因此,网络寿命最低。而k-CRSS算法通过引用休眠机制,有效地提高能量利用率,进而延长了网络寿命。

此外,从图6可知,随着FoI区域体积的增加,网络寿命下降。这主要是因为:在节点数一定的情况下,体积的增加,为了保证覆盖率,需要更多的节点保持活动节点,这增加了节点能量的消耗。观察到N1∶N2对网络寿命的影响:当N1∶N2=0∶1时,网络寿命最大,依次是N1∶N2=1∶3、N1∶N2=1∶1。这主要是类型2节点的感测距离和通信半径均大于类型1节点。那么,类型2节点数越多,越有利于节省能量。

3.2 网络寿命随节点数的变化

本次实验分析在固定FoI区域体积内节点数的增加对网络寿命的影响。实验中,k=1,2,V为803m3,N从1 200至20 000变化。实验数据如图7所示。

从图7可知,在固定的803区域内,节点数的增加,提高了网络寿命。原因在于:当区域固定,在维持同等覆盖率时,节点数越多,就有越多的节点处于休眠状态,这必然有利于网络寿命的提高。与未引入k-CRSS算法相比,k-CRSS算法通过轮流切换节点状态,节省能量,进而提高了网络寿命。

图7 网络寿命

3.3 同类算法的比较

选择分布式的k-覆盖算法DCP[15]作为参照,且传感节点数N为5 000。V从803m3至1003m3变化,实验数据如图8所示。

图8 活动节点数

图8显示了活动节点数随FoI区域体积的变化情况。从图8可知,在维持同等覆盖率的同时,k-CRSS算法的活动节点数更少,这说明k-CRSS算法通过少的活动节点就能满足覆盖要求,这有利于网络寿命的增加。

4 总结

针对异构网络的FoI区域的k-cover问题,提出基于k-cover的冗余节点休眠算法k-CRSS。k-CRSS算法旨在保证FoI内的k-cover同时,最小化活动节点数,即让冗余节点休眠,进而保存能量,延长网络寿命。k-CRSS算法先引用概率模型,估计传感节点成为冗余节点的概率。然后,进行节点状态转换,进而保存节点能量。实验数据表明,提出的k-CRSS算法有效地延长网络寿命。

[1] Ammari H M,Das S K. A Study ofk-Coverage and Measures of Connectivity in 3-D Wireless Sensor Networks[J]. IEEE Trans Comput 2010,59(2):243-257.

[2] 陈东海,李长庚. 基于簇头功能分化的无线传感器网络成簇算法[J]. 传感技术学报,2015,28(2):244-248.

[3] Lu Z,Li W,Pan M. Maximum Lifetime Scheduling for Target Coverage and Data Collection in Wireless Sensor Networks[J]. IEEE Trans Veh Technol,2015,64(2):714-727.

[4] 门顺治,孙顺远,徐保国. 基于PSO的非均匀分簇双簇头路由算法[J]. 传感技术学报,2014,27(9):1281-1286.

[5] Mahboubi H,Moezzi K,Aghdam A,et al. Distributed Deployment Algorithms for Efficient Coverage in a Network of Mobile Sensors with Nonidentical Sensing Capabilities[J]. IEEE Trans Veh Technol,2014,63(8):3998-4016.

[6] Adulyasas A,Sun Z,Wang N. Connected Coverage Optimization for Sensor Scheduling in Wireless Sensor Networks[J]. IEEE Sensors J,2015,15(7):3877-3892.

[7] Yan F,Vergne A,Martins P,et al. Homology Based Distributed Coverage Hole Detection in Wireless Sensor Networks[J]. IEEE/ACM Trans Netw,2015,23(6):1705-1718.

[8] Ammari H M,Das S K. Jointk-Coverage and Hybrid Forwarding in Duty-Cycled Three-Dimensional Wireless Sensor Networks[C]//Proc IEEE SECON,2012:170-178.

[9] Huang C F,Tseng Y C,Lo L C. The Coverage Problem in Three-Dimensional Wireless Sensor Networks[J]. J Interconnect Netw,2012,8(3):209-227.

[10] Ammari H M,Das S K. Centralized and Clusteredk-Coverage Protocols for Wireless Sensor Networks[J]. IEEE Trans Comput,2012,61(1):118-133.

[11] Gupta H P,Rao S V,Venkatesh T. Analysis of the Redundancy in Coverage of a Heterogeneous Wireless Sensor Network[C]//Proc IEEE ICC,2013:1904-1909.

[12] Wang B. Coverage Problems in Sensor Networks:A Survey[J]. ACM Comput Surveys,2011,43(4):32-53.

[13] The Network Simulator—ns-2.34.[Online]. Available:http://www.isi.edu/nsnam/ns.

[14] Jin Y. EECCR:An Energy-Efficientm-Coverage andn-Connectivity Routing Algorithm under Border Effects in Heterogeneous Sensor Networks[J]. IEEE Trans Veh Technol,2014,58(3):1429-1442.

[15] Ammari H M,Das S K. Jointk-Coverage and Hybrid Forwarding in Duty-Cycled Three-Dimensional Wireless Sensor Networks[C]//Proc IEEE SECON,2012:170-178.

王自力(1978-),男,汉族,河南驻马店人,硕士,副教授,研究方向为计算机应用及物联网技术;

郑鑫(1977-),女,汉族,河南驻马店人,硕士,副教授,研究方向为计算机应用及物联网技术。

k-CoverBased-SleepSchedulingAlgorithmforRedundantNodeinHeterogeneousWSNs*

WANGZili1*,ZHENGXin2

(1.Department of Information Engineering,Zhumadian Career Technical College,Zhumadian He’nan 463000,China; 2.Information Engineering Institute,Huanghuai University,Zhumadian He’nan 463000,China)

Some monitoring applications in heterogeneous wireless sensor networks(WSNs)may require the Field of Interest(FoI)bek-covered,k≥1,while redundant sensors must be scheduled to sleep to minimize energy consumption. Therefore,k-cover based sleep Scheduling algorithm(k-CRSS)for redundant node is proposed in this paper.k-CRSS algorithm has used probabilistic approach to determine if a sensor redundant to meet the desired coverage requirement of FoI. We derived an expression to determine the probability of the region covered by a sensor of any type being redundantly covered by the neighbors. We proposed a scheduling protocol to identify all the redundant sensor nodes and schedule them to sleep without creating a coverage hole in the FoI. The proposed protocol is completely distributed,does not use any geographic information,and uses only the information gathered about the neighbors using a few control messages. Simulation results demonstrated that the number of active sensors is reduced due to the scheduling protocol,and hence,the network lifetime is increased.

wireless sensor network;coverage;redundant node;scheduling algorithm;network lifetime

项目来源:河南省高等学校青年骨干教师计划项目(2015GGJS-300)

2017-03-06修改日期:2017-05-31

TP393

:A

:1004-1699(2017)09-1422-05

10.3969/j.issn.1004-1699.2017.09.021

概率方法,先推导点覆盖冗余概率表达式,然后再推导传感节点覆盖冗余表达式,最后采用分布式的休眠调度算法。