无线传感器网络中覆盖控制理论与算法概要

ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],Vol.17,No.3,March2006,pp.422−433:[phone]©2006byJournalofSoftware.Allrightsreserved.无线传感器网络中覆盖控制理论与算法∗任彦+,张思东,张宏科(北京交通大学电子信息工程学院,北京100044TheoriesandAlgorithmsofCoverageControlforWirelessSensorNetworksRENYan+,ZHANGSi-Dong,ZHANGHong-Ke(SchoolofElectronicsandInformationEngineering,BeijingJiaotongUniversity,Beijing100044,China+Correspondingauthor:Phn:[phone],E-mail:[e-mail],(3:422−433.: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中的传感器节点一般都具备数据处理和通信能力,并通过无线链路或直接或间接地将收集到的信号转化为数据发送到一∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.60473001,60572037(国家自然科学基金;theInnovationFoundationofScienceandTechnologyforExcellentDoctorialCandidatesofBeijingJiaotongUniversityunderGrantNo.48013(北京交通大学优秀博士生科技创新基金Received2005-06-17;Accepted2005-12-01任彦等:无线传感器网络中覆盖控制理论与算法423个指令中心(sink.这种协作分布式传感器网络的一种自然组织结构,就是在各传感器节点间以无线多跳方式组成一个自组织网络[3,4].集成了网络技术、嵌入式技术及传感器技术的WSN将逻辑上的信息世界与真实的物理世界融合在一起,同时深刻改变了人与自然的交互方式.WSN的覆盖控制问题,可以看作是在传感器网络节点能量、无线网络通信带宽、网络计算处理能力等资源普遍受限情况下,通过网络传感器节点放置以及路由选择等手段,最终使WSN的各种资源得到优化分配,进而使感知、监视、传感、通信等各种服务质量得到改善.这一点与传统adhoc网络有很大的不同.如何根据不同的应用环境需要,对WSN进行不同级别的覆盖控制就成了WSN中一个基本但亟待解决的问题.给定一个传感器网络,覆盖控制也可以一般性地总结为通过各个传感器节点协作而达到对监视区域的不同管理或感应效果[5].与此同时,WSN中还有一些与覆盖控制密切相关的应用属性,它们依旧属于覆盖控制问题的范畴并极大地丰富了WSN覆盖控制的“内涵”.近年来,已有一些学者开展了WSN优化覆盖控制方面的研究工作,并取得了一定的进展.本文综述了近年来在这一领域所取得的研究成果.第1节分析了WSN覆盖控制问题面临的挑战(即性能评价标准.在第2节中对现有覆盖控制理论和协议算法进行了分类.第3节详细介绍和讨论了一些典型的覆盖控制协议算法.第4节进行了覆盖控制各种算法间的比较性总结,并指出该领域亟待解决的问题.第5节进行了总结.1无线传感器网络覆盖控制问题面临的挑战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]等,需要网络的覆盖控制协议与算法考424JournalofSoftware软件学报Vol.17,No.3,March2006虑节点具有运动能力、网络整体或传感目标运动等网络动态特性.因此,WSN覆盖控制的网络动态特性也成为一项必要的评价标准.(7网络可扩展性支持保证网络的可扩展性是WSN覆盖控制的另一项关键需求.没有网络可扩展性保证,网络的性能会随着网络规模的增加而显著降低.针对不同的应用需求,WSN的网络规模相差较大,网络的可扩展性需求在WSN中尤为明显.(8算法实施策略WSN覆盖控制算法的执行可以有分布式、集中式以及两者的混合式3种方式.通常来说,由于WSN自身的能量消耗、协议操作代价、网络性能和精度等要求,使得利用本地信息执行的分布式算法更为适用.在一些特殊的网络操作环境下,分布式、集中式两种方式混合执行则更为有效.除了上面列出的一些所面临的挑战之外,WSN覆盖控制协议算法还会存在是否需要知道网络节点位置、是否需要专门的覆盖控制消息等差别.同样,它们也是我们设计、分析具体协议和算法时要考察的内容.2无线传感器网络覆盖控制问题分类WSN从诞生之初就与应用密切相关,WSN覆盖控制更是如此.如今的WSN覆盖控制问题不仅包括单纯的覆盖含义,更是与节能通信、路径规划、可靠通信和目标定位等具体应用紧密相连.为了对WSN覆盖控制问题有更加全面的认识,本文分别从配置方式和相关应用属性两个角度进行WSN覆盖控制问题分类.2.1配置方式分类按照无线传感器网络节点不同配置方式(即节点是否需要知道自身位置信息,我们可以将WSN的覆盖问题分为确定性覆盖、随机覆盖两大类.下面逐一对这两类覆盖控制类型加以总结.2.1.1确定性覆盖如果WSN的状态相对固定或是WSN环境已知,就可以根据预先配置的节点位置确定网络拓扑情况或增加关键区域的传感器节点密度,这种情况被称为确定性覆盖问题.此时的覆盖控制问题,就成为一种特殊的网络或路径规划问题.典型的确定性覆盖有确定性区域/点覆盖、基于网格(grid的目标覆盖和确定性网络路径/目标覆盖3种类型.确定性区域/点覆盖是指已知节点位置的WSN要完成目标区域或目标点的覆盖,文献[7,13−16]研究的都是此类问题.与确定性区域/点覆盖相关的两个著名计算几何问题为艺术馆走廊监控问题(artgalleryproblem[17]以及圆周覆盖问题(circlecoveringproblem[17].基于网格的目标覆盖是指当地理环境情况预先确定时,使用二维(也可以为三维的网格进行网络的建模,并选择在合适的格点配置传感器节点来完成区域/目标的覆盖.文献[9,18,19]中对这一问题进行了有益的研究.确定性网络路径/目标覆盖同样也是考虑WSN传感器节点位置已知情况,但这类问题特别考虑了如何对穿越网络的目标或其经过的路径上各点进行感应与追踪.相关研究包括文献[10,20].2.1.2随机覆盖在许多实际自然环境中,由于网络情况