无线传感器网络中多重覆盖算法的研究*

张 蕾

(北京建筑大学计算机系,北京 100044)



无线传感器网络中多重覆盖算法的研究*

张 蕾*

(北京建筑大学计算机系,北京 100044)

在无线传感网器络中的硬件资源普遍受限的情况下,形成优秀的覆盖控制策略己成为无线传感器网络研究领域的热点课题。本文提出了一种能量有效的多重物理覆盖算法,在保障覆盖与连通性的前提下,以能量、覆盖度为衡量指标,采用调度机制实现节点轮换活跃与休眠,有效地提高网络生存时间。仿真实验结果表明,与目前典型算法相比,提出的算法在网络生存时间、能量消耗与消亡节点数上具有显著的优势。

无线传感器网络;覆盖;物理覆盖;连通性

近年来,随着现代传感器技术、微机电技术、无线通信技术、嵌入式计算技术和分布式信息处理技术的飞速发展,由这五大技术相互融合形成的无线传感网络技术得到了较快的发展。由于具有体积小、价格低廉以及彼此之间可以在近距离内进行无线通信等良好特性,无线传感器网络WSNs(Wireless Sensor Networks)在国防军事、反恐抗灾、智能家居、环境监测、地震与气候预测、交通管理、医疗卫生、制造业等许多方面都具有广泛应用前景,是国内外的热点研究领域[1-2]。

要实现对分布区域内的各种环境或对象进行感知与监测,首要的问题就是必须对监控区域进行有效的覆盖控制[3-5]。覆盖问题是任何类型的WSN中的基本问题。覆盖定义为对于监控区域内的任何一点,都满足至少在一个传感器节点的感知范围之内,则称该区域被覆盖。WSN的覆盖控制问题,可以看作是在传感器网络节点能量、无线网络通信带宽、网络计算处理能力等资源普遍受限情况下,通过网络传感器节点放置以及路由选择等手段,最终使WSN的各种资源得到优化分配,进而使感知、监视、传感、通信等各种服务质量得到改善[6-7]。

针对节能覆盖问题,目前的研究大多存在无法保证期望覆盖度的问题,并且网络生存时间不能显著提高。本文提出了能量有效的多重物理覆盖算法,主要考虑二维平面监控区域的连通性、能量有效性与覆盖度问题,适合于对监控区域可靠性高、覆盖度高、节点布置随机、网络密度变化的应用场景,解决可靠度要求高的WSN监控问题,为密度不均匀WSN节能多重覆盖提供有效的途径。

1 WSN覆盖问题概述

覆盖问题是WSN中的一个基本问题,它能反映网络提供的“感知”服务质量。覆盖问题的基本意义就是在传感器网络的节点能量、无线通信能力、处理器处理能力等资源受到限制的情况下,通过优化传感器节点的部署位置或者优化路由选择等方式,达到传感器网络的资源优化配置,增强网络的感知能力、监测能力、传感能力和通信能力[8]。

给定一个WSN,覆盖控制可以这样概括:传感器节点之间不同的协作方式可以产生对监控区域不同的管理和感知效果。覆盖控制和实际应用是密切相关的,国内外针对覆盖控制问题已经展开了大量的研究工作。文献[9]中,节点采用自调度方法阶段检查之前执行一个退避机制,以有效地控制网络“活跃”节点的密度,但这种方法存在的问题是无法保证期望覆盖度。为了避免因为节点调度为休眠状态而导致的覆盖区域盲点问题,文献[10]提出了一种覆盖有效的调度方法CPNS(Coverage Preserving Node Scheduling),其思想是在节点调度为休眠状态之前,可以通过逐一询问的方式以确保该区域能有效覆盖,但不足之处是这种询问方式的通信开销过大。尽管当前这方面的研究较多,但如何对现有的联合优化节能与多重覆盖两类节能覆盖方式的优点进行有效的结合,在保障覆盖与连通性的前提下,以轮换“活跃”和“休眠”节点的节能覆盖方案,不仅是一种有效且有吸引力的方法,而且具有相当的挑战性。

本文针对多重物理覆盖问题,提出了一种能量有效的多重覆盖算法MCA(Multiple Coverage Algorithm),实现覆盖区域的盲点消除,延长网络生存时间。MCA通过对节点所覆盖的范围进行判断,实现节点的合法性检测。当节点与其周围的节点之间满足一定的覆盖关系以及覆盖度满足给定的阈值要求时,将保持节点活跃,否则关闭该节点;以感知监测方式和协作交互的方式避免盲点的出现;以能量、覆盖度为衡量指标,采用一定的调度机制实现节点轮换活跃与休眠,最大化网络生命周期。

2 能量有效的多重覆盖算法

2.1 定义

对于监控二维区域E内的一系列传感器节点的集合C

(1)

|C|=N

(2)

其中N为节点数量,每个节点ni(i∈[1,N])的位置Li为

Li=(xi,yi)

(3)

节点ni(i∈[1,N])的感知范围为Ri,即对于任何位置Pi,如果其与ni的距离dPi,ni满足

dPi,ni≤Ri

(4)

则节点ni能覆盖该位置并监控其信息。

定义1对于监控二维区域E内的任何位置Pi,如果其位于节点ni的感知范围内,即满足式(4),则称点Pi被节点ni覆盖。

定义2对于监控二维区域E内的任何位置Pi,如果其同时位于节点集合Ci感知范围内,即有

Ci⊆C

(5)

则称点Pi被节点集合Cik重覆盖,k为覆盖度。

定义3对于监控二维区域E内的任意位置Pi,Pi的覆盖度为m,给定正整数K,通过有效地调度传感器节点集合C内的节点的休眠,使得位置Pi被节点集合Ci覆盖,并满足

Ci⊂C,|Ci|=k,m>k≥K

(6)

称其为能量有效的K重覆盖。

显然,为了使监控区域E内的任意位置达到能量有效的K重覆盖,首先必须获取当前节点的覆盖度k,如果有k>K,则表明当前的覆盖度高于期望值,可以将部分节点调度到休眠状态,节省能量,并延长网络的生命期,但是由于节点的休眠,可能造成实际的覆盖度低于期望覆盖度,因此需要判断并避免调度后出现覆盖盲点的问题;否则,如果有k>K,需要将部分休眠节点唤醒,提高覆盖度。

定义4重叠覆盖弧段:对于任意两个感知范围有重叠的节点ni与nj,sij表示节点nj感知范围内的边界弧段位于节点ni的感知范围内的部分,即为两个节点的重叠覆盖弧段。如图1所示,双实线为重叠覆盖弧段sij。

图1 2个节点的重叠覆盖弧段

定义5节点nj的邻居节点集合Neib(ni),

Neib(ni)={nj|dni,nj≤ri+rj,nj≠ni,∀nj∈Π}

(7)

其中dni,nj表示节点ni与nj的距离。

2.2 算法描述

为了在保证不同应用的所需的覆盖度的前提下实现节能的功能,每个节点根据当前的覆盖情况,周期性自适应地调整自己的状态,调度到休眠状态。为了实现期望的覆盖度,提出的能量有效的K重覆盖算法MCA包括3个部分:一是节点合法性检测算法。通过对节点所覆盖的范围进行判断,当节点与其周围的节点之间满足一定的覆盖关系以及覆盖度满足给定的阈值要求时,将保持节点活跃,否则关闭该节点。二是覆盖区域的盲点消除算法。以一定的感知监测方式和协作交互的方式避免因为节点的关闭导致感知区域盲点的出现。三是休眠节点激活算法。对当前活动节点覆盖范围内的其他节点,以能量、覆盖度为衡量指标,采用一定的调度机制实现节点轮换活跃与休眠,最大化网络生命周期。

2.2.1 节点合法性检测算法

对节点进行合法性检测的目的是在保证监控区域覆盖度的前提下,尽可能减少当前活跃节点的数量,实现能量节省的功能。考虑到每个节点可能处于一下3种模式之一:休眠、活跃与工作状态,其中工作状态的节点完成监控区域的数据感知与数据传输的功能;其他节点则准备从休眠模式切换到活跃模式,实现对即将消亡的节点或有故障节点的替换。

节点合法性检测算法

输入:传感器节点集合C

输出:调度为休眠状态的节点集合Cs

begin对每个节点ni

begin对ni的每个sij(j∈[1,N(ni)])

查找由邻居节点N(ni)∩N(nj)所覆盖的节点nj所有的弧段

用升序对所有弧段进行排序

根据弧段截断sij,并计算弧段sij的覆盖度k

if(k>K)

将ni加入到集合Cs

end

end

2.2.2 盲点消除算法

由于节点调度为休眠状态后,可能造成部分覆盖区域无法再有效覆盖的问题,即覆盖出现盲点(Blind Point)。为了避免盲点的产生,在将节点调度为休眠状态之前,最安全的方法是向该节点的所有邻居节点发送询问消息,然后确定是否执行调度,但该方法的缺陷在于开销太大。而采用随机等待的检测方法存在无法保证期望的覆盖度的问题。

盲点消除算法

输入:传感器节点集合C,Cs

begin对每个节点ni

begin对ni的每个sij(j∈[1,N(ni)])

ifSubsij-|PC(sij)|≤K

将节点ni加入候选检测列表

向邻居节点发送候选检测列表及剩余能量

收到信息的节点检测如果位于候选检测列表,则发送确认帧,并保持活跃状态

发送节点收到所有候选列表的确认后,根据确认信息实现相应的调度,并保证无盲点。

end

end

2.2.3 休眠节点激活算法

对于调度为休眠的节点,必须采用一定的调度机制实现节点轮换活跃,并根据网络的状态,实现节点替换或保证覆盖区域的多重覆盖,同时延长网络生命周期。假设所有节点已实现时钟同步功能,一个周期内每个节点包括调度与感知两个阶段。其中调度阶段包括两部分功能:主动期与被动期。

当节点处于活跃状态时,在每个周期内,主动期实现信标帧的发送。如果节点处于休眠状态,则在调度为休眠状态时,在主动期其发送的信标信息中包含了休眠时间长度,以便让其他节点知道该节点仍为有效节点,且已知其可能调度为活跃状态的时间。

每个节点周期性地醒来接收信标帧,通过接收到信标帧,节点可以被动地检测覆盖度。通过收到的信标帧,可以知道一些节点在其调度期内已经有多次没有发送信标帧,或覆盖度低于预期值K。或者当该节点的能量不够时,该节点可以计算出实际的覆盖度k,并确定是否应该唤醒其他节点由休眠状态转换到活跃状态。

休眠节点激活算法

输入:传感器节点集合C,Cs

repeat

do对每个活跃节点ni

begin对ni的每个sij(j∈[1,N(ni)])

计算其覆盖度k

ifk≥K

++j;

else

对所有sij中覆盖度小于K的子弧段求和得S

end

对节点ni调度表中的休眠节点,选择能覆盖S最多的节点作为唤醒节点

until准备休眠节点待覆盖区域弧段全覆盖

3 仿真结果与分析

本文仿真实验PC硬件配置为Intel 2.8 GHz CPU,内存1 GB,硬盘250 GB,仿真实验平台是OMNeT 3.0[11-12]。

仿真实验考虑在300 m×300 m的正方形区域内随机布置一定数量的节点,每个节点的感知范围可变。当一个节点调度为休眠状态时,将通过提出的MCA算法的调度过程,使其所有邻居节点获知该信息。为了验证提出的MCA方法的有效性,与节点自调度覆盖方法NSS以及覆盖有效的调度方法CPNS进行性能比较。

3.1 覆盖度性能

为了对3种算法的覆盖度性能进行比较,以增加布置节点数量的方式增加覆盖区域的节点密度,并定义平均覆盖度为所有节点覆盖度之和与节点数量的比值;实际覆盖度为所有节点中覆盖度的最小值。当以随机方式对节点进行布置后,分别计算出上述两个覆盖度。考查在相同的情况下,分别采用3种覆盖算法进行休眠调度后,网络实际的覆盖度。仿真结果如图2所示。

图2 不同覆盖度时的生存时间

图2所示为不同覆盖度时,提出的MCA算法的生存时间。其中节点的能量从500到3 000个单元随机分布。生存时间指的是只要当任意节点的覆盖度无法满足给定的期望覆盖度时的时间。

从图中可以看出覆盖度越高,生存时间越短,这与时间情况是吻合的;而且布置的节点数量越多,生存时间越长。当布置节点数量从100增加到300个时,覆盖度为2之前的生存时间从380增加到600,增长率仅为58%;而覆盖度为1之前的生存时间从510增加到820,增长率为61%。这表明,生存时间并不会随网络密度的成倍增加而同比增长。其原因在于,在部分监控区域,只有一部分的节点符合调度到休眠状态的条件,而部分关键节点无法实现休眠,因此即便增加覆盖密度,但并不能保障这些节点节省能量,因而导致生存时间无法大比例增加。

3.2 生存时间

图3所示为布置节点数量的增加时3种算法的生存时间。随着网络中节点密度将逐渐加大,3种算法生存时间都随之增加。但很显然,NSS算法生存时间最短,而且随着节点密度的增加,其生存时间增加的趋势并不明显,仅从100个节点时的580个增加到300个节点时的980个,即节点密度增加3倍时,生存时间仅增加了69%。与CPS算法相比,CPNS算法生存时间具有明显的优势,随着节点密度的增加,其生存时间从710增加到1 960,比NSS算法长1倍。提出的MCA算法的性能最优,其生存时间最长,且随着节点密度的增加,其增加趋势显著,从800增加到3 570,即节点密度增加3倍时,整个网络的生存时间增加了3.4倍。其原因在于,NSS由于其存在无法保证期望覆盖度的问题,总是使大量的冗余节点处于活跃状态,因此导致节点能量消耗迅速。而CPNS则以逐一询问的方式以确保该区域能有效覆盖,虽然可以有效的避免节点的冗余,但其开销较大。而提出的MCA算法不仅通过合法性检测避免冗余节点的存在,而且以节点能量剩余为依据,以能量、覆盖度为衡量指标,按优先级进行休眠调度,有力地减少了节点等能耗,因此显著地延长了网络的生存时间。

综上所述,本文提出的MCA算法在覆盖度和网络生存时间等方面都具有良好的性能。

图3 不同算法的生存时间

4 总结

针对WSN中兼顾能量效率与物理连通性的两个关键因素提出了一种能量有效、保证多重覆盖度的优化MCA算法。详细给出了能量有效多重覆盖的问题描述,从节点合法性检测、覆盖区域的盲点消除与休眠节点激活3个方面详细给出了算法描述。仿真实验结果及与NSS、CPNS算法的比较表明,提出的MCA算法在网络密度变化时,有效地保障了物理覆盖度,延长了网络生存时间。

[1] Huang C F,Tseng Y C.A Survey of Solutions to the Coverage Problems in Wireless Sensor Networks[J].Journal of Internet Technology,2005,6(1):1-8

[2]臧哲,齐建东,张晓武,等.基于智能算法的层次型多链WSN路由协议[J].传感技术学报,2013,26(4):558-563

[3]Ke W C,Liu B H,Tsai M J.Constructing a Wireless Sensor Network to Fully Cover Critical Grids by Deploying Minimum Sensors on Grid Points is NP-Complete.IEEE Transactions on Computers,2007,56(5):710-715

[4]Andrea Bottino,Dipartimento di Automatica e Informatica,Corso Duca degli.A Nearly Optimal Sensor Placement Algorithm for Boundary Coverage[J].Pattern Recognition,2008,41(11):3343-3355

[5]任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7):1282-1291.

[6]Pyun Sung-Yeop,Cho Dong-Ho.Power-Saving Scheduling for Multiple-Target Coverage in Wireless Sensor Networks[J].IEEE Communications Letters,2009,13(2):130-132

[7]Zhang Chi,Zhang Yanchao,Fang Yuguang.Localized Algorithms for Coverage Boundary Detection in Wireless Sensor Networks[J].Wireless Networks,2009,15(1):3-20

[8]舒坚,刘琳岚,董海星,等.机会网络数据收集中的转发控制[J].传感技术学报,2012,25(1):129-134

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

[10]Tian D,Georganas N D.A Coverage-Preserving Node Scheduling Scheme for Large Wireless Sensor Networks[J].ACM Int’l Workshop on Wireless Sensor Networks and Applications,2002

[11]况晓辉,赵刚,郭勇.网络模拟器NS2中仿真功能的问题分析及改进[J].系统仿真学报,2009,21(2):427-431.

[12]黄化吉,冯穗力,秦丽蛟.NS网络模拟和协议仿真[J].人民邮电出版社,2010

张蕾(1981-),女,博士,北京建筑大学计算机专业教师,中国计算机学会会员。主要研究泛在业务环境、智能建筑无线传感器网络、网络资源管理等。2004.9--2009.7在北京邮电大学泛网无线通信教育部重点实验室(博士生导师:张平教授)攻读博士学位。作为年青科研业务骨干,主持北京高等学校“青年英才计划”项目、北京市教委面上项目“智能建筑无线传感器网络能量均衡及安全路由技术研究”等。近五年内,在国内外期刊和国际学术会议上发表论文30余篇(其中SCI检索2篇,EI检索14篇);参编教材2本,lei.zhang@bucea.edu.cn。

ResearchonMultipleCoverageAlgorithminWirelessSensorNetworks*

ZHANGLei*

(School of Computer Science,Beijing University of Civil Engineering and Architecture,Beijing 100044,China)

Coverage has become one of the hottest topics in this field,for the hardware and energy is always limited in wireless sensor networks(WSNs).This paper presents an efficient power multiple coverage algorithm.By measuring energy and coverage degree,it puts redundant sensor nodes to sleep mode to save energy while maintain the sensing field sufficient coverage degree with precondition of coverage and connective of WSN.Detailed simulation results and compared to existing schemes indicate that the proposed algorithm not only guarantees the network coverage degree,but also prolongs the network lifetime.

wireless sensor networks;coverage;physical coverage;connectivity

项目来源:北京高等学校“青年英才计划”项目(21271413117);智能建筑无线传感器网络能量均衡及安全路由技术研究项目(KM201410016007);计算中心学生实践创新基地建设研究项目(J12-16)

2014-03-16修改日期:2014-05-04

10.3969/j.issn.1004-1699.2014.06.018

TP212

:A

:1004-1699(2014)06-0802-05