覆盖首页被k

首页被k 时间:2021-01-30 阅读:()

ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,Vol.
17,No.
3,March2006,pp.
422433http://www.
jos.
org.
cnDOI:10.
1360/jos170422Tel/Fax:+86-10-625625632006byJournalofSoftware.
Allrightsreserved.
无线传感器网络中覆盖控制理论与算法(任彦+,张思东,张宏科(北京交通大学电子信息工程学院,北京100044)TheoriesandAlgorithmsofCoverageControlforWirelessSensorNetworksRENYan+,ZHANGSi-Dong,ZHANGHong-Ke(SchoolofElectronicsandInformationEngineering,BeijingJiaotongUniversity,Beijing100044,China)+Correspondingauthor:Phn:+86-10-51685677,E-mail:yren@center.
njtu.
edu.
cn,http://www.
njtu.
edu.
cnRenY,ZhangSD,ZhangHK.
Theoriesandalgorithmsofcoveragecontrolforwirelesssensornetworks.
JournalofSoftware,2006,17(3):422433.
http://www.
jos.
org.
cn/1000-9825/17/422.
htmAbstract:Oneofthemostfundamentalproblemsinwirelesssensornetworksisthecoveragecontrolproblem,whichreflectshowwellaregionisapperceived.
Thecoveragecontroltheoriesandalgorithmscanresultinnotonlynetworkresources'optimialallocationbutalsoefficientsensingandcollectingoftheenvironmentalinformation,andcommunicatingwithneighboringnodesbywirelesssensornetworks.
Inthispaper,thecoveragecontrolproblemiscaptured.
Somerecentnoveltheoriesandalgorithmsforwirelesssensornetworkscoveragecontrolproblemsarereviewed,andthetaxonomyisdescribed.
Morespecifically,severaltypicalalgorithmsandprotocolsarediscussedindetail.
Intheend,advantagesanddisadvantagesofthealgorithmsaresummarized.
Theopenresearchissuesinthisfieldarealsopointedout.
Keywords:wirelesssensornetworks;coveragecontrol;energyefficiency;algorithm摘要:覆盖控制作为无线传感器网络中的一个基本问题,反映了网络所能提供的"感知"服务质量,可以使无线传感器网络的空间资源得到优化分配,进而更好地完成环境感知、信息获取和有效传输的任务.
立足于无线传感器网络的覆盖控制问题,分类总结了近年来提出的各种覆盖控制问题的思想和有代表性的研究成果,着重讨论了一些典型的无线传感器网络覆盖控制算法与协议.
最后进行了各种算法的比较性总结,深入分析了目前无线传感器网络覆盖控制亟待解决的问题,并展望了其未来的发展方向.

关键词:无线传感器网络;覆盖控制;能量有效;算法中图法分类号:TP393文献标识码:A近年来,随着微机电系统(micro-electro-mechanismsystem,简称MEMS)、无线通信、信息网络与集成电路等技术的迅速发展,新兴的无线传感器网络(wirelesssensornetworks,简称WSN)应运而生[1,2].
WSN中的传感器节点一般都具备数据处理和通信能力,并通过无线链路或直接或间接地将收集到的信号转化为数据发送到一个指令中心(sink).
这种协作分布式传感器网络的一种自然组织结构,就是在各传感器节点间以无线多跳方式组成一个自组织网络[3,4].
集成了网络技术、嵌入式技术及传感器技术的WSN将逻辑上的信息世界与真实的物理世界融合在一起,同时深刻改变了人与自然的交互方式.

WSN的覆盖控制问题,可以看作是在传感器网络节点能量、无线网络通信带宽、网络计算处理能力等资源普遍受限情况下,通过网络传感器节点放置以及路由选择等手段,最终使WSN的各种资源得到优化分配,进而使感知、监视、传感、通信等各种服务质量得到改善.
这一点与传统adhoc网络有很大的不同.
如何根据不同的应用环境需要,对WSN进行不同级别的覆盖控制就成了WSN中一个基本但亟待解决的问题.
给定一个传感器网络,覆盖控制也可以一般性地总结为通过各个传感器节点协作而达到对监视区域的不同管理或感应效果[5].
与此同时,WSN中还有一些与覆盖控制密切相关的应用属性,它们依旧属于覆盖控制问题的范畴并极大地丰富了WSN覆盖控制的"内涵".

近年来,已有一些学者开展了WSN优化覆盖控制方面的研究工作,并取得了一定的进展.
本文综述了近年来在这一领域所取得的研究成果.
第1节分析了WSN覆盖控制问题面临的挑战(即性能评价标准).
在第2节中对现有覆盖控制理论和协议算法进行了分类.
第3节详细介绍和讨论了一些典型的覆盖控制协议算法.
第4节进行了覆盖控制各种算法间的比较性总结,并指出该领域亟待解决的问题.
第5节进行了总结.

无线传感器网络覆盖控制问题面临的挑战WSN覆盖控制策略及算法的应用,有助于网络节点能量的有效控制、感知服务质量的提高和整体生存时间的延长,但另一方面也会带来网络相关传输、管理、存储和计算等代价的提高.
因此,WSN覆盖控制的性能评价标准对于分析一个覆盖控制策略及算法的可用性与有效性至关重要.
通过从不同的角度总结出覆盖控制算法所面临的挑战,有助于清楚地比较出各种算法之间的优缺点.
这里归纳出以下几点:(1)覆盖能力以环境感知、目标监测、信息获取和有效传输为主要目标的WSN需要关心对传感区域或监测目标的覆盖能力,无线传感器网络覆盖控制问题也正是由此而来.
因此,网络对目标区域或是目标点的覆盖程度是衡量一个WSN覆盖控制算法是否优劣的首要标准.

(2)网络的连通性由于WSN是一种无基础设施的网络,大量节点采用自组织方式协同完成指令中心的查询、搜集等指令,网络节点之间需要通过无线多跳方式或直接或间接地相互通信来协同工作.
网络的连通性将有效保证自身无线多跳自组织通信的开展,并直接决定了WSN感知、监视、传感、通信等各种服务质量的达到.

(3)能量有效性(即延长网络生存时间)由于WSN节点硬件平台资源受限、网络节点数量巨大、实际应用的环境条件复杂且大多不允许对"失效"节点进行电池更换,因此,如何节约各节点有限的电池能量并尽力延长整体网络的生存时间已成为WSN的重要性能指标[6].
能量的有效性将是WSN覆盖控制所面临的一个主要挑战.

(4)算法精确性由于受实际部署条件差异、网络资源有限和覆盖目标特性等多方面的影响,使得WSN覆盖控制在很多情况下是一个NP完全问题[7,8],只能达到近似优化覆盖[9],势必会造成覆盖控制算法执行结果产生误差,甚至不能保证算法的有效执行.
如何减小误差,提高算法的精确性成为优化覆盖控制算法的一项重要内容.

(5)算法复杂性不同WSN覆盖控制协议及算法其实现方式不同导致算法复杂程度也有较大差别.
衡量一个WSN覆盖控制算法是否优化的一项重要标准就是其算法的复杂性程度.
算法的复杂性程度通常包括时间复杂度、通信复杂度以及实现复杂度等,需要综合考虑.

(6)网络动态性一些特殊的应用环境,如运动目标监测覆盖[10,11]、网络动态覆盖[12]等,需要网络的覆盖控制协议与算法考虑节点具有运动能力、网络整体或传感目标运动等网络动态特性.
因此,WSN覆盖控制的网络动态特性也成为一项必要的评价标准.

(7)网络可扩展性支持保证网络的可扩展性是WSN覆盖控制的另一项关键需求.
没有网络可扩展性保证,网络的性能会随着网络规模的增加而显著降低.
针对不同的应用需求,WSN的网络规模相差较大,网络的可扩展性需求在WSN中尤为明显.

(8)算法实施策略WSN覆盖控制算法的执行可以有分布式、集中式以及两者的混合式3种方式.
通常来说,由于WSN自身的能量消耗、协议操作代价、网络性能和精度等要求,使得利用本地信息执行的分布式算法更为适用.
在一些特殊的网络操作环境下,分布式、集中式两种方式混合执行则更为有效.

除了上面列出的一些所面临的挑战之外,WSN覆盖控制协议算法还会存在是否需要知道网络节点位置、是否需要专门的覆盖控制消息等差别.
同样,它们也是我们设计、分析具体协议和算法时要考察的内容.

无线传感器网络覆盖控制问题分类WSN从诞生之初就与应用密切相关,WSN覆盖控制更是如此.
如今的WSN覆盖控制问题不仅包括单纯的覆盖含义,更是与节能通信、路径规划、可靠通信和目标定位等具体应用紧密相连.
为了对WSN覆盖控制问题有更加全面的认识,本文分别从配置方式和相关应用属性两个角度进行WSN覆盖控制问题分类.

配置方式分类按照无线传感器网络节点不同配置方式(即节点是否需要知道自身位置信息),我们可以将WSN的覆盖问题分为确定性覆盖、随机覆盖两大类.
下面逐一对这两类覆盖控制类型加以总结.

确定性覆盖如果WSN的状态相对固定或是WSN环境已知,就可以根据预先配置的节点位置确定网络拓扑情况或增加关键区域的传感器节点密度,这种情况被称为确定性覆盖问题.
此时的覆盖控制问题,就成为一种特殊的网络或路径规划问题.
典型的确定性覆盖有确定性区域/点覆盖、基于网格(grid)的目标覆盖和确定性网络路径/目标覆盖3种类型.

确定性区域/点覆盖是指已知节点位置的WSN要完成目标区域或目标点的覆盖,文献[7,1316]研究的都是此类问题.
与确定性区域/点覆盖相关的两个著名计算几何问题为艺术馆走廊监控问题(artgalleryproblem)[17]以及圆周覆盖问题(circlecoveringproblem)[17].
基于网格的目标覆盖是指当地理环境情况预先确定时,使用二维(也可以为三维)的网格进行网络的建模,并选择在合适的格点配置传感器节点来完成区域/目标的覆盖.
文献[9,18,19]中对这一问题进行了有益的研究.

确定性网络路径/目标覆盖同样也是考虑WSN传感器节点位置已知情况,但这类问题特别考虑了如何对穿越网络的目标或其经过的路径上各点进行感应与追踪.
相关研究包括文献[10,20].

随机覆盖在许多实际自然环境中,由于网络情况不能预先确定且多数确定性覆盖模型会给网络带来对称性与周期性特征,从而掩盖了某些网络拓扑的实际特性.
再加上WSN自身拓扑变化复杂,导致采用确定性覆盖在实际应用中具有很大的局限性,不能适用于战场等危险或其他环境恶劣的场所.
因此,我们需要进一步对节点随机分布在传感区域而预先没有得到自身位置的情况进行讨论,这正是WSN随机覆盖所要解决的问题.
目前,WSN的随机覆盖已成为WSN覆盖控制的一个热点问题,我们可大致将这类问题具体分为随机节点覆盖和动态网络覆盖两类.

随机节点覆盖考虑在WSN中传感器节点随机分布且预先不知道节点位置的条件下,网络完成对监测区域的覆盖任务.
学者关于此类问题的研究内容较多,主要包括文献[8,11,2127].

与一般WSN一旦部署则网络中的传感器节点的位置就固定不变有所不同,动态网络覆盖则是考虑一些特殊环境中部分传感器节点具备一定运动能力的情况[12].
该类网络可以动态完成相关覆盖任务.

相关应用属性分类作为一种源于应用而又服务于应用的现实、可行的网络技术,无线传感器网络在军事以及民用都具有非常广阔的应用前景[28],WSN覆盖控制也是如此.
如今,WSN覆盖控制问题不仅包括单纯的覆盖含义,更与节能通信、路径规划、可靠通信和目标定位等具体应用紧密相连,并依旧属于覆盖控制的范畴.
因此,我们还可以从WSN相关应用属性这一新的视角对WSN覆盖控制问题进行重新分类和研究.

节能覆盖由于WSN中传感器节点自身体积较小、电池能量资源有限,如何保证大规模网络环境下传感器节点能量的有效使用就成为需要关注的一项重要研究内容,它直接影响到整个网络生存时间能否充分延长.
如文献[7,8,14,15,21]所述,采用轮换"活跃"和"休眠"节点的节能覆盖方案,可以有效地提高网络生存时间.
而轮换活跃/休眠节点的节能覆盖方案关键,就是要在保证一定网络覆盖要求的条件下,最大化轮换节点集合数目.

栅栏覆盖WSN中有一类与覆盖控制密切相关的特殊问题——栅栏覆盖,它考察了目标穿越WSN时被检测或是没有被检测的情况,反映了给定WSN所能提供的传感、监视能力.
这类覆盖控制问题的目标是找出连接出发位置(记为S)和离开位置(记为D)的一条或多条路径,使得这样的路径能够在不同模型定义下提供对目标的不同传感/监视质量.
根据目标穿越WSN时所采用模型的不同,栅栏覆盖又可以具体分为"最坏与最佳情况覆盖"和"暴露穿越"两种类型.

"最坏与最佳情况覆盖"问题中,对于穿越网络的目标而言,最坏情况是指考察所有穿越路径中不被网络传感器节点检测的概率最小情况;对应的最佳情况是指考察所有穿越路径中被网络传感器节点发现的概率最大情况.
此问题相关研究包括文献[10,12,20,23].

与单纯考虑离传感器节点距离的"最坏与最佳情况覆盖"不同,"暴露穿越"同时考虑了"目标暴露(targetexposure)"的时间因素和传感器节点对于目标的"感应强度"因素.
这种覆盖模型更为符合实际环境中,运动目标由于穿越WSN区域的时间增加而"感应强度"累加值增大的情况.
文献[11,22,29,30]就考察了这类问题.

连通性覆盖连通性覆盖问题也是WSN覆盖控制相关应用属性中的一个重要组成部分,它同时考虑了WSN的覆盖能力和网络连通性这两个相互联系的属性.
连通覆盖问题所要解决的是如何同时满足网络一定的传感覆盖和通信连通性需求,这对于一些要求可靠通信的应用至关重要.
根据具体的连通性要求,连通性覆盖又可具体分为两类:活跃节点集连通覆盖[13,25],是针对采用活跃节点集轮换机制的情况,考虑如何保证指定传感区域的覆盖和网络的连通性;而连通路径覆盖[16,18,27],则是考虑通过选择可能的连通传感器节点路径来得到最大化的网络覆盖效果.

目标定位覆盖在某些特殊环境下,WSN覆盖配置"伴随而来"的是WSN的目标定位问题,我们可称此时的WSN覆盖为目标定位覆盖.
例如在前面提到的网格条件下,网络的目标定位问题即为及时查询出目标所在网格被周围哪些传感器格点所覆盖.
文献[9,19]就专门进行了此方面的研究.

由以上WSN覆盖控制分类我们不难看出:配置方式和相关应用属性两种分类方法既有各自特殊的分类角度,又同时会有具体研究内容上的重叠.
基于本部分内容,图1进行了WSN覆盖控制问题各种协议和算法的分类总结.

Fig.
1ProtocolsandalgorithmsofcoveragecontrolforWSN:Ataxonomy图1无线传感器网络覆盖控制协议和算法分类典型的无线传感器网络覆盖控制算法与协议基于前一部分对WSN覆盖控制问题各种协议和算法进行的分类和总结,本节将详细介绍一些典型的覆盖控制协议算法研究成果,并深入分析各种协议算法的优缺点.

基于网格的覆盖定位传感器配置算法[9]基于网格的覆盖定位传感器配置算法是基于网格的目标覆盖类型(确定性覆盖)中的一种,同时也属于目标定位覆盖的内容.
Lin等人在文献[9]中将此优化覆盖定位问题转化为最小化距离错误问题,并加以改进,提出了一种在有限代价条件下最小化最大错误距离的组合优化配置方法.

考虑网络传感器节点以及目标点都采用网格形式配置,传感器节点采用0/1覆盖模型,并使用能量矢量来表示格点的覆盖.
如图2所示,网络中的各格点都可至少被一个传感器节点所覆盖(即该点能量矢量中至少一位为1),此时区域达到了完全覆盖.
例如,格点位置8的能量矢量为(0,0,1,1,0,0).
在网络资源受限而无法达到格点完全识别时,就需要考虑如何提高定位精度的问题.
而错误距离是衡量位置精度的一个最直接的标准,错误距离越小,则覆盖识别结果越优化.

我们设计了一种模拟退火算法来最小化距离错误.
初始时刻假设每个格点都配置有传感器.
若配置代价上限制没有达到就循环执行以下过程:首先试图删除一个传感器节点,之后进行配置代价评价.
如果评价不通过就将该节点移动到另外一个随机选择的位置,之后再进行配置代价评价.
循环得到优化值后同时保存新的节点配置情况.
最后,改进算法停止执行的准则.
在达到模拟退火算法的冷却温度tf时,优化覆盖识别的网络配置方案也同时达到.

优点:(1)算法结果表明:与采用随机配置达到完全覆盖的方案相比,该算法更为有效,具有鲁棒性并易于扩展;(2)适用于不规则的传感器网络区域.
缺点:(1)网格化的网络建模方式会掩盖网络的实际拓扑特征;(2)网络中均为同质节点,不适用于网络中存在节点配置代价和覆盖能力有差异的情况.

轮换活跃/休眠节点的NodeSelf-Scheduling覆盖协议[15]采用轮换"活跃"和"休眠"节点的NodeSelf-Scheduling[15]覆盖控制协议可以有效延长网络生存时间,该协议同时属于确定性区域/点覆盖和节能覆盖类型.

协议采用节点轮换周期工作机制,每个周期由一个self-scheduling阶段和一个working阶段组成.
在self-scheduling阶段:各节点首先向传感半径内邻居节点广播通告消息,其中包括节点ID和位置(若传感半径不同则包括发送节点传感半径).
节点检查自身传感任务是否可由邻居节点完成,可替代的节点返回一条状态通告消息,之后进入"休眠状态",需要继续工作的节点执行传感任务.
在判断节点是否可以休眠时,如果相邻节点同时检查到自身的传感任务可由对方完成并同时进入"休眠状态",就会出现如图3所示的"盲点".

(a)b)Fig.
3The"blindpoint"inWSN图3网络中出现的"盲点"在图3(a)中,节点e和f的整个传感区域都可以被相邻的邻居节点代替覆盖.
e和f节点满足进入"休眠状态"条件之后,将关闭自身节点的传感单元进入"休眠状态",但这时就出现了不能被WSN检测的区域即网络中出现"盲点",如图3(b)所示.
为了避免这种情况的发生,文献[15]中,节点在self-scheduling阶段检查之前执行一个退避机制:每个节点在一个随机产生的Td时间之后再开始检查工作.
此外,退避时间还可以根据周围节点密度而计算,这样就可以有效地控制网络"活跃"节点的密度.
为了进一步避免"盲点"的出现,每个节点在进入"休眠状态"之前还将等待Tw时间来监听邻居节点的状态更新.
该协议是作为LEACH分簇协议[31]的一个扩展来实现的,有关仿真结果证明:WSN的平均网络生存时间较LEACH分簇协议延长了1.
7倍.

优点:(1)不会出现覆盖"盲点",因而可以保持网络的充分覆盖;(2)该算法可以有效控制网络节点的冗余,同时保持一定的传感可靠性;(3)节点轮换机制周期工作有效地延长了网络生存时间;(4)仿真实验表明:节点轮换机制对位置错误、包丢失以及节点失效具有鲁棒性,依然可以保持网络的充分覆盖.

缺点:(1)需要预先确定节点位置并要求整个网络同时具有时间同步支持,给网络带来了附加实现代价;(2)该机制无法使WSN区域上的边界节点"休眠",这就影响了整个网络的生存时间延长效果;(3)节点轮换机制只能适用于传感器节点覆盖区域为圆周(或圆球),不适用于不规则节点感应模型;(4)需要综合优化考虑活跃节点数量和网络覆盖效果.
最坏与最佳情况覆盖[10,20]最坏与最佳情况覆盖算法同时属于确定性网络路径/目标覆盖和栅栏覆盖类型.
算法考虑如何对穿越网络的目标或其所在路径上各点进行感应与追踪,体现了一种网络的覆盖性质.

Meguerdichian等人先后在文献[20]和文献[10]中定义了"最大突破路径(maximalbreachpath)"和"最大支撑路径(maximalsupportpath)",分别使得路径上的点到周围最近传感器的最小距离最大化以及最大距离最小化.
显然,这两种路径分别代表了WSN最坏(不被检测概率最小)和最佳(被发现的概率最大)的覆盖情况.
文中分别采用计算几何中的Voronoi图与Delaunay三角形来完成最大突破路径和最大支撑路径的构造和查找.
其中,Voronoi图是由所有Delaunay三角形边上的垂直平分线形成;而Delaunay三角形的各顶点为网络的传感器节点,并满足子三角形外接圆中不含其他节点,如图4所示.

由于Voronoi图中的线段具有到最近的传感器节点距离最大的性质,因此最大突破路径一定是由Voronoi图中的线段组成.
最大突破路径查找过程如下:(1)基于各节点的位置产生网络Voronoi图;(2)给每一条边赋予一个权重来代表到最近传感器节点的距离;(3)在最小和最大的权重之间执行二进制查找算法:每一步操作之前给出一个参考权重标准,然后进行宽度优先查找(breadth-first-search),检查是否存在一条从S到D的路径,满足路径上线段的权重都比参考权重标准要大.
如果路径存在,则增加参考权重标准来缩小路径可选择的线段数目,否则就降低参考权重标准.

(4)最后得到一条从S到D的路径,也就是最大突破路径,图4中用Pmax_breach表示.

类似地,由于Delaunay三角形是由所有到最近传感器节点距离最短的线段组成,因此最大支撑路径必然由Delaunay三角形的线段构成.
给每一条边赋予一个权重来代表路径上所有到周围最近传感器节点的最大距离,查找算法同上.
图4中用Pmax_support表示了算法执行后得到的一条最大支撑路径.

优点:(1)在最佳与最差两种度量条件下,分别得到了临界的网络路径规划结果,可以指导网络节点的配置来改进整体网络的覆盖;(2)作为一种特殊的WSN覆盖控制算法,适用于网络路径规划、目标观测等许多应用场所.

缺点:(1)算法是集中式的计算方式,需要预先知道各节点的位置信息;(2)算法没有考虑实际中障碍、环境和噪声等可能造成的影响;(3)网络中均为同质节点,不适用于网络中存在节点覆盖能力有差异时算法的执行情况.

暴露穿越[11]暴露穿越覆盖同时属于随机节点覆盖和栅栏覆盖的类型.
如前所述,"目标暴露(targetexposure)"覆盖模型同时考虑时间因素和节点对于目标的"感应强度"因素,更为符合实际环境中,运动目标由于穿越网络时间增加而"感应强度"累加值增大的情况.
节点s的传感模型定义为.
其中p为目标点,正常数(和K均为网络经验参数.
最小暴露路径代表了WSN最坏的覆盖情况,而一个运动目标沿着路径p(t)在时间间隔[t1,t2]内经过WSN监视区域的暴露路径在文献[11]中被定义为.
其中I(F,p(t))代表了在传感区域F中沿着路径p(t)运动时被相应传感器(有最近距离传感器和全部传感器两种)感应的效果.
我们提出了一种数值计算的近似方法来找到连续的最小暴露路径:首先,将传感器网络区域进行网格划分,并假设暴露路径只能由网格的边与对角线组成;之后,为每条线段赋予一定的暴露路径权重;最后,执行Djikstra算法得到近似的最小暴露路径.

优点:(1)暴露覆盖模型更为符合目标由于穿越WSN区域的时间增加而被检测概率增大的实际情况;(2)分布式的算法执行方式,不需要预先知道整个网络的节点配置情况;(3)根据需要可以选择不同的感应强度模型和网格划分,从而得到精度不同的暴露路径.

缺点:(1)暴露精度与算法运行时间是一对矛盾,需要平衡考虑;(2)算法没有考虑实际中障碍、环境以及传感器节点本身运动等可能造成的影响.

圆周覆盖[24,26]Huang在文献[24]中将随机节点覆盖类型的圆周覆盖归纳为决策问题:目标区域中配置一组传感器节点,看看该区域能否满足k覆盖,即目标区域中每个点都至少被k个节点覆盖.
我们考虑每个传感节点覆盖区域的圆周重叠情况,进而根据邻居节点信息来确定是否一个给定传感器的圆周被完全覆盖,如图5所示[17].

(a)b)Fig.
5CoverageofthesensorS'sperimeter图5传感器节点S圆周的覆盖情况该算法可以用分布式方式实现:传感器S首先确定圆周被邻居节点覆盖的情况,如图5(a)所示,3段圆周[0,a],[b,c],[d,π]分别被S的3个邻居节点所覆盖.
再将结果按照升序顺序记录在[0,2π]区间,如图5(b)所示,这样就可以得到节点S的圆周覆盖情况:[0,b]段为1,[b,a]段为2,[a,d]段为1,[d,c]段为2,[c,π]段为1.
文献[24]给出证明:"传感器节点圆周被充分覆盖等价于整个区域被充分覆盖".
每个传感器节点收集本地信息来进行本节点圆周覆盖判断,并且该算法还可以进一步扩展到不规则的传感区域中使用.

在文献[24]中的二维圆周覆盖问题基础上,Huang进一步在文献[26]中使用将三维圆球覆盖影射为二维圆周覆盖的类似方法,在不增加计算复杂性的前提下使用分布式方式解决了三维圆球体覆盖的问题.

优点:(1)算法考虑了传感器具有不同覆盖传感能力以及不规则传感范围的情况,具有较好的适用性;(2)分布式的算法执行方式,减小了整个网络的通信与计算负载;(3)算法可以适用于二维以及三维的网络环境.
缺点:(1)该算法只考察了区域内各点的覆盖情况,并未考虑各点如何被网络传感器节点所覆盖;(2)缺少相应优化网络节点配置及改善网络覆盖进一步的协议和算法.
连通传感器覆盖(connectedsensorcover)[16]Gupta在文献[16]中设计的算法通过选择连通的传感器节点路径来得到最大化的网络覆盖效果,该算法同时属于连通性覆盖中的连通路径覆盖以及确定性区域/点覆盖类型.
当指令中心向WSN发送一个感应区域查询消息时,连通传感器覆盖的目标是选择最小的连通传感器节点集合并充分覆盖WSN区域.
文献[16]分别设计了集中与分布式两种贪婪算法.
假设已选择的传感器节点集为M,剩余与M有相交传感区域的传感器节点称为候选节点.
集中式算法初始节点随机选择构成M之后,在所有从初始节点集合出发到候选节点的路径中选择一条可以覆盖更多未覆盖子区域的路径.
将该路径经过的节点加入M,算法继续执行直到网络查询区域可以完全被更新后的M所覆盖.
图6表示了该贪婪算法执行的方式.
在图6(a)中,贪婪算法会选择路径P2得到图6(b),这是由于在所有备选路径中选择C3和C4组成的路径P2可以覆盖更多未覆盖子区域.

(a)b)Fig.
6Greedyalgorithmoftheconnectedsensorcover图6连通传感器覆盖的贪婪算法连通传感器覆盖的分布式贪婪算法执行过程是:首先从M中最新加入的候选节点开始执行,在一定范围内广播候选路径查找消息(CPS);收到CPS消息的节点判断自身是否为候选节点,如果是,则单播方式返回发起者一个候选路径响应消息(CPR);发起者选择可以最大化增加覆盖区域的候选路径;更新各参数,算法继续执行,直到网络查询区域可完全被更新后的M所覆盖.

优点:(1)本算法的节点传感区域模型可以是任意凸形区域,更加符合实际环境;(2)可以灵活地选择使用集中式或分布式方式实现;(3)在保证网络覆盖任务的同时,考虑了网络的连通性,算法周期执行降低了网络通信代价,并可以延长网络的生存时间.

缺点:(1)虽然同时考虑了连通性与网络的覆盖性,但不能保证查询返回结果的精度;(2)没有考虑实际无线信道中出现的通信干扰和消息丢失,是一种单纯考虑消息传递的理想情况.

无线传感器网络覆盖控制算法比较与亟待解决的问题覆盖控制算法比较为了对已有算法进行相互间的比较性总结,本节对照本文第1节给出的WSN覆盖控制所面临的挑战进行了各种算法的优缺点总结和比较,见表1.

Table1Comparisonofcoveragecontrolalgorithmsinwirelesssensornetworks表1WSN覆盖控制算法比较ArticleCoverageabilityNetworkconnectivityAccuracyComplexityNetworkmobilityEnergyefficiencyNetworkscalabilityDeploymentmodelLocation-BasedNegotiation-Based[13]StrongStrongModerateLowWeakLowModerateCentralizedYesNo[18]ModerateStrongHighModerateWeakLowStrongCentralizedYesNo[19]ModerateModerateHighModerateWeakModerateModerateCentralizedYesNo[9]StrongModerateHighHighWeakModerateStrongCentralizedYesNo[14]ModerateWeakLowHighWeakHighModerateDistributedYesYes[7]ModerateStrongModerateModerateWeakHighModerateCentralizedYesNo[15]StrongModerateModerateModerateModerateHighStrongDistributedYesYes[21]WeakModerateLowLowStrongHighStrongDistributedNoYes[8]StrongStrongLowHighWeakHighWeakCentralizedYesNo[12]StrongModerateModerateHighStrongModerateStrongHybridNoNo[20]StrongStrongModerateHighWeakLowStrongCentralizedYesYes[10]StrongStrongModerateHighWeakLowStrongCentralizedYesYes[11]ModerateWeakHighModerateStrongModerateWeakCentralizedYesNo[22]StrongModerateHighModerateStrongModerateModerateDistributedYesYes[29]StrongStrongHighLowModerateModerateModerateDistributedYesNo[30]StrongStrongHighModerateModerateHighStrongHybridYesYes[23]StrongStrongHighHighWeakHighModerateDistributedYesYes[24]StrongStrongHighModerateWeakLowStrongHybridYesYes[26]StrongStrongHighModerateWeakLowStrongDistributedYesYes[25]StrongStrongHighHighWeakHighStrongDistributedYesYes[16]StrongStrongModerateLowStrongModerateStrongCentralizedNoYes[27]StrongStrongHighModerateWeakModerateStrongDistributedNoYes通过表1,我们可以从整体上对无线传感器网络中的覆盖控制问题的各种算法有一个比较清晰的认识.
此外,对照WSN覆盖控制评价标准进行的相关研究成果优缺点比较,有助于我们更加全面地了解已有协议算法,并进一步发现和考虑其中一些亟待解决的问题.

亟待解决的问题虽然WSN覆盖控制研究已经取得了一定的成果,但是仍有很多问题需要解决,集中体现在以下几点:(1)感知模型种类的完善.
从本文综述的各种WSN覆盖成果不难看出:目前使用的传感器节点感知模型包括圆形区域感知[7,9,10,15,16,19,20]与负指数距离感知[11,22,29,30]两种感知模型,不能适用于实际WSN环境的感知模型多样化需要.
此外,目前节点感知模型大多没有考虑实际无线信道中出现的通信干扰,是一种理想模型[16].
因此,还需要进一步考虑更加完善的感知模型种类;(2)三维空间的覆盖控制.
从文本第3节的讨论不难看出:尽管目前许多方案都很好地解决了二维平面的覆盖控制问题[10,11,20,23],但由于三维空间的覆盖控制在计算几何与随机图论等数学理论上仍是一个NP难问题[17],因此,现有的三维空间覆盖控制只能得到近似优化的结果[26,27].
如何针对具体的WSN三维空间应用需要设计出有效的算法与协议,将会是一个很有意义的研究课题;(3)提供移动性的支持.
目前,WSN覆盖控制理论与算法大都假定传感节点或者网络是静态的,但在战场等应用中可能需要节点或网络具有移动性[12],因此,新的覆盖控制理论与算法需要提供对移动性的支持;(4)符合WSN与Internet交互的相应WSN覆盖控制方案.
由于WSN将逻辑上的信息世界与真实的物理世界融合在一起,因此会在一些实际应用中大量出现WSN与Internet之间数据与信息的交互,这就需要未来研究相应的WSN覆盖控制方案;(5)开发和设计更多结合WSN覆盖控制的应用.
覆盖控制问题涉及到WSN通信、感应、计算和存储等许多方面,将会在战场侦查、阵地防御和情报获取等军事环境以及林场/牧场监视、灾难救护、环境监测和医疗观察等很多民用项目中有广泛应用.
因此,如何利用WSN覆盖控制理论与各种算法,开发和设计更多结合WSN覆盖控制的应用,将会给人类生活带来进一步的改善.

总结无线传感器网络将逻辑上的信息世界与真实的物理世界融合在一起,极大地提高了人们认识和改造世界的能力.
而网络覆盖控制作为WSN实施过程中的一个基本问题,反映了网络所能提供的"感知"服务质量.
本文立足于WSN的覆盖控制问题,对近年来提出的各种覆盖控制问题的新思想和代表性研究成果进行归纳并加以介绍,随后结合WSN覆盖控制评价标准进行了比较性总结,进而深入分析了目前WSN覆盖控制亟待解决的问题,并展望了其未来可能的发展方向.

致谢在此,我们向曾经对本文提出宝贵建议的审稿专家以及曾参与本文内容讨论的所有同学、老师表示衷心的感谢.

References:AkyildizIF,SuW,SankarasubramaniamY,CayirciE.
Wirelesssensornetworks:Asurvey.
ComputerNetworks,2002,38(4):393422.
RenFY,HuangHN,LinC.
Wirelesssensornetworks.
JournalofSoftware,2003,14(2):11481157(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/14/1148.
htmPottieGJ,KaiserWJ.
Wirelessintegratednetworksensors.
CommunicationsoftheACM,2000,43(5):5158.
SohrabiK,GaoJ,AilawadhiV,PottieGJ.
Protocolsforself-organizationofawirelesssensornetwork.
IEEEPersonalCommunications,2000,7(5):1627.
CardeiM,WuJ.
Coverageinwirelesssensornetworks.
In:IlyasM,MagboubI,eds.
HandbookofSensorNetworks,chapter19.
CRCPress,2004.
LiJZ,LiJB,ShiSF.
Concepts,issuesandadvanceofsensornetworksanddatamanagementofsensornetworks.
JournalofSoftware,2003,14(10):17171727(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/14/1717.
htmSlijepcevicS,PotkonjakM.
Powerefficientorganizationofwirelesssensornetworks.
In:GlisicS,ed.
Proc.
oftheIEEEInt'lConf.
onCommunications(ICC).
Helsinki:IEEEPress,2001.
472476.
CardeiM,DuDZ.
Improvingwirelesssensornetworklifetimethroughpowerawareorganization.
WirelessNetworks,2005,11(3):333340.
LinFYS,ChiuPL.
Anear-optimalsensorplacementalgorithmtoachievecompletecoverage/discriminationinsensornetworks.
IEEECommunicationsLetters,2005,9(1):4345.
MegerianS,KoushanfarF,PotkonjakM,SrivastavaMB.
Worstandbest-casecoverageinsensornetworks.
IEEETrans.
onMobileComputing,2005,4(1):8492.
MeguerdichianS,KoushanfarF,QuG,PotkonjakM.
Exposureinwirelessad-hocsensornetworks.
In:RoseC,ed.
Proc.
oftheACMInt'lConf.
onMobileComputingandNetworking(MobiCom).
NewYork:ACMPress,2001.
139150.
CortesJ,MartinezS,KaratasT,BulloF.
Coveragecontrolformobilesensingnetworks.
IEEETrans.
onRoboticsandAutomation,2004,20(2):243255.
KarK,BanerjeeS.
Nodeplacementforconnectedcoverageinsensornetworks.
In:CrowcroftJ,ed.
Proc.
oftheModelingandOptimizationinMobile,AdHocandWirelessNetworks.
Sophia-Antipolis:IEEEPress,2003.
5052.
YanT,HeT,StankovicJA.
Differentiatedsurveillanceforsensornetworks.
In:AkyildizIF,EstionD,eds.
Proc.
oftheACMInt'lConf.
onEmbeddedNetworkedSensorSystems(SenSys).
NewYork:ACMPress,2003.
5162.
TianD,GeorganasND.
Anodeschedulingschemeforenergyconservationinlargewirelesssensornetworks.
WirelessCommunicationsandMobileComputing,2003,3(2):271290.
GuptaH,DasSR,GuQ.
Connectedsensorcover:Self-Organizationofsensornetworksforefficientqueryexecution.
In:GerlaM,ed.
Proc.
oftheACMInt'lSymp.
onMobileAdHocNetworkingandComputing(MobiHOC).
NewYork:ACMPress,2003.
189200.
HuangCF,TsengYC.
Asurveyofsolutionstothecoverageproblemsinwirelesssensornetworks.
JournalofInternetTechnology,2005,6(1):18.
ShakkottaiS,SrikantR,ShroffN.
Unreliablesensorgrids:Coverage,connectivityanddiameter.
In:BauerF,ed.
Proc.
oftheIEEEInfocom.
SanFrancisco:IEEEPress,2003.
10731083.
ChakrabartyK,LyengarSS,QiH,ChoE.
Gridcoverageforsurveillanceandtargetlocationindistributedsensornetworks.
IEEETrans.
onComputers,2002,51(12):14481453.
MeguerdichianS,KoushanfarF,PotkonjakM,SrivastavaMB.
Coverageproblemsinwirelessad-hocsensornetwork.
In:SenguptaB,ed.
Proc.
oftheIEEEINFOCOM.
Anchorage:IEEEPress,2001.
13801387.
YeF,ZhongG,ChengJ,LuSW,ZhangLX.
PEAS:Arobustenergyconservingprotocolforlong-livedsensornetworks.
In:StankovicJ,ZhaoW,eds.
Proc.
oftheInt'lConf.
onDistributedComputingSystems(ICDCS).
Providence:IEEEPress,2003.
2837.
MeguerdichianS,SlijepcevicS,KarayanV,PotkonjakM.
Localizedalgorithmsinwirelessad-hocnetworks:Locationdiscoveryandsensorexposure.
In:VaidyaNH,ed.
Proc.
oftheACMInt'lSymp.
onMobileAdHocNetworkingandComputing(MobiHOC).
NewYork:ACMPress,2001.
106116.
LiXY,WanPJ,FriederO.
Coverageinwirelessadhocsensornetworks.
IEEETrans.
onComputers,2003,52(6):753763.
HuangCF,TsengYC.
Thecoverageprobleminawirelesssensornetwork.
In:SivalingamKM,RaghavendraCS,eds.
Proc.
oftheACMInt'lWorkshoponWirelessSensorNetworksandApplications(WSNA).
NewYork:ACMPress,2003.
115121.
WangX,XingG,ZhangY,LuC,PlessR,GillC.
Integratedcoverageandconnectivityconfigurationinwirelesssensornetworks.
In:AkyildizIF,EstionD,eds.
Proc.
oftheACMInt'lConf.
onEmbeddedNetworkedSensorSystems(SenSys).
NewYork:ACMPress,2003.
2839.
HuangCF,TsengYC,LoLC.
Thecoverageprobleminthree-dimensionalwirelesssensornetworks.
In:ShahR,ed.
Proc.
oftheGLOBECOM.
Dallas:IEEEPress,2004.
31823186.
RavelomananaV.
Extremalpropertiesofthree-dimensionalsensornetworkswithapplications.
IEEETrans.
onMobileComputing,2004,3(3):246257.
SunLM,LiJZ,ChenY,ZhuHS.
WirelessSensorNetworks.
Beijing:TsinghuaUniversityPress,2005(inChinese).
VeltriG,HuangQ,QuG,PotkonjakM.
Minimalandmaximalexposurepathalgorithmsforwirelessembeddedsensornetworks.
In:AkyildizIF,EstionD,eds.
Proc.
oftheACMInt'lConf.
onEmbeddedNetworkedSensorSystems(SenSys).
NewYork:ACMPress,2003.
4050.
AdlakhaS,SrivastavaM.
Criticaldensitythresholdsforcoverageinwirelesssensornetworks.
In:TachikawaK,ed.
Proc.
oftheIEEEWirelessCommunicationsandNetworking(WCNC).
NewOrleans:IEEEPress,2003.
16151620.
HeinzelmanW,ChandrakasanA,BalakrishnanH.
Energy-Efficientcommunicationprotocolforwirelesssensornetworks.
In:NunamakerJ,SpragueR,eds.
Proc.
ofthe33rdHawaiiInt'lConf.
SystemSciences.
Washington:IEEEPress,2000.
300304.
附中文参考文献:[2]任丰原,黄海宁,林闯.
无线传感器网络.
软件学报,2003,14(2):11485757.
http://www.
jos.
org.
cn/1000-9825/14/1148.
htm[6]李建中,李金宝,石胜飞.
传感器网络及其数据管理的概念、问题与进展.
软件学报,2003,14(10):17171727.