無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法概要

ISSN1000-9825,CODENRUXUEWE-mail:jos@JournalofSoftware,Vol.17,No.3,March2006,pp.422-433DOI:10.1360/jos170422Tel/Fax:+86-10-62562563?2006byJournalofSoftware.Allrightsreserved.無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法任彥+,張思東，張宏科(北京交通大學(xué)電子信息工程學(xué)院，北京100044TheoriesandAlgorithmsofCoverageControlforWirelessSensorNetworksRENYan+,ZHANGSi-Dong,ZHANGHong-Ke(SchoolofElectronicsandInformationEngineering,BeijingJiaotongUniversity,Beijing100044,China+Correspondingauthor:Phn:+86-10-51685677,E-mail:yren@,RenY,ZhangSD,ZhangHK.Theoriesandalgorithmsofcoveragecontrolforwirelesssensornetworks.JournalofSoftware,2006,17(3:422-433./1000-9825/17/422.htmAbstract:Oneofthemostfundamentalproblemsinwirelesssensornetworksisthecoveragecontrolproblem,whichreflectshowwellaregionisapperceived.Thecoveragecontroltheoriesandalgorithmscanresultinnotonlynetworkresources5optimialallocationbutalsoefficientsensingandcollectingoftheenvironmentalinformation,andcommunicatingwithneighboringnodesbywirelesssensornetworks.Inthispaper,thecoveragecontrolproblemiscaptured.Somerecentnoveltheoriesandalgorithmsforwirelesssensornetworkscoveragecontrolproblemsarereviewed,andthetaxonomyisdescribed.Morespecifically,severaltypicalalgorithmsandprotocolsarediscussedindetail.Intheend,advantagesanddisadvantagesofthealgorithmsaresummarized.Theopenresearchissuesinthisfieldarealsopointedout.Keywords:wirelesssensornetworks;coveragecontrol;energyefficiency;algorithm摘要:覆蓋控制作為無線傳感器網(wǎng)絡(luò)中的一個基本問題，反映了網(wǎng)絡(luò)所能提供的“感知”服務(wù)質(zhì)量，可以使無線傳感器網(wǎng)絡(luò)的空間資源得到優(yōu)化分配，進而更好地完成環(huán)境感知、信息獲取和有效傳輸?shù)娜蝿?wù).立足于無線傳感器網(wǎng)絡(luò)的覆蓋控制問題，分類總結(jié)了近年來提出的各種覆蓋控制問題的思想和有代表性的研究成果，著重討論了一些典型的無線傳感器網(wǎng)絡(luò)覆蓋控制算法與協(xié)議.最后進行了各種算法的比較性總結(jié)，深入分析了目前無線傳感器網(wǎng)絡(luò)覆蓋控制亟待解決的問題,并展望了其未來的發(fā)展方向.關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);覆蓋控制；能量有效;算法中圖法分類號:TP393文獻標識碼：A近年來,隨著微機電系統(tǒng)（micro-electro-mechanismsystem,簡稱MEMS、無線通信、信息網(wǎng)絡(luò)與集成電路等技術(shù)的迅速發(fā)展，新興的無線傳感器網(wǎng)絡(luò)（wirelesssensornetworks,簡稱WSN應(yīng)運而生[1,2].WSN中的傳感器節(jié)點一般都具備數(shù)據(jù)處理和通信能力，并通過無線鏈路或直接或間接地將收集到的信號轉(zhuǎn)化為數(shù)據(jù)發(fā)送到一SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.60473001,60572037（國家自然科學(xué)基金；theInnovationFoundationofScienceandTechnologyforExcellentDoctorialCandidatesofBeijingJiaotongUniversityunderGrantNo.48013（北京交通大學(xué)優(yōu)秀博士生科技創(chuàng)新基金Received2005-06-17;Accepted2005-12-01任彥等:無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法423個指令中心（sink.這種協(xié)作分布式傳感器網(wǎng)絡(luò)的一種自然組織結(jié)構(gòu),就是在各傳感器節(jié)點間以無線多跳方式組成一個自組織網(wǎng)絡(luò)[3,4].集成了網(wǎng)絡(luò)技術(shù)、嵌入式技術(shù)及傳感器技術(shù)的WSN將邏輯上的信息世界與真實的物理世界融合在一起,同時深刻改變了人與自然的交互方式.WSN的覆蓋控制問題，可以看作是在傳感器網(wǎng)絡(luò)節(jié)點能量、無線網(wǎng)絡(luò)通信帶寬、網(wǎng)絡(luò)計算處理能力等資源普遍受限情況下,通過網(wǎng)絡(luò)傳感器節(jié)點放置以及路由選擇等手段,最終使WSN的各種資源得到優(yōu)化分配,進而使感知、監(jiān)視、傳感、通信等各種服務(wù)質(zhì)量得到改善.這一點與傳統(tǒng)adhoc網(wǎng)絡(luò)有很大的不同.如何根據(jù)不同的應(yīng)用環(huán)境需要,對WSN進行不同級別的覆蓋控制就成了WSN中一個基本但亟待解決的問題.給定一個傳感器網(wǎng)絡(luò),覆蓋控制也可以一般性地總結(jié)為通過各個傳感器節(jié)點協(xié)作而達到對監(jiān)視區(qū)域的不同管理或感應(yīng)效果[5].與此同時,WSN中還有一些與覆蓋控制密切相關(guān)的應(yīng)用屬性,它們依舊屬于覆蓋控制問題的范疇并極大地豐富了WSN覆蓋控制的“內(nèi)涵”.近年來，已有一些學(xué)者開展了WSN優(yōu)化覆蓋控制方面的研究工作,并取得了一定的進展.本文綜述了近年來在這一領(lǐng)域所取得的研究成果.第1節(jié)分析了WSN覆蓋控制問題面臨的挑戰(zhàn)(即性能評價標準.在第2節(jié)中對現(xiàn)有覆蓋控制理論和協(xié)議算法進行了分類.第3節(jié)詳細介紹和討論了一些典型的覆蓋控制協(xié)議算法.第4節(jié)進行了覆蓋控制各種算法間的比較性總結(jié),并指出該領(lǐng)域亟待解決的問題.第5節(jié)進行了總結(jié).1無線傳感器網(wǎng)絡(luò)覆蓋控制問題面臨的挑戰(zhàn)WSN覆蓋控制策略及算法的應(yīng)用，有助于網(wǎng)絡(luò)節(jié)點能量的有效控制、感知服務(wù)質(zhì)量的提高和整體生存時間的延長，但另一方面也會帶來網(wǎng)絡(luò)相關(guān)傳輸、管理、存儲和計算等代價的提高.因此,WSN覆蓋控制的性能評價標準對于分析一個覆蓋控制策略及算法的可用性與有效性至關(guān)重要.通過從不同的角度總結(jié)出覆蓋控制算法所面臨的挑戰(zhàn)，有助于清楚地比較出各種算法之間的優(yōu)缺點.這里歸納出以下幾點-八、、?(1覆蓋能力以環(huán)境感知、目標監(jiān)測、信息獲取和有效傳輸為主要目標的WSN需要關(guān)心對傳感區(qū)域或監(jiān)測目標的覆蓋能力,無線傳感器網(wǎng)絡(luò)覆蓋控制問題也正是由此而來.因此，網(wǎng)絡(luò)對目標區(qū)域或是目標點的覆蓋程度是衡量一個WSN覆蓋控制算法是否優(yōu)劣的首要標準.(2網(wǎng)絡(luò)的連通性由于WSN是一種無基礎(chǔ)設(shè)施的網(wǎng)絡(luò),大量節(jié)點采用自組織方式協(xié)同完成指令中心的查詢、搜集等指令，網(wǎng)絡(luò)節(jié)點之間需要通過無線多跳方式或直接或間接地相互通信來協(xié)同工作.網(wǎng)絡(luò)的連通性將有效保證自身無線多跳自組織通信的開展,并直接決定了WSN感知、監(jiān)視、傳感、通信等各種服務(wù)質(zhì)量的達到.(3能量有效性(即延長網(wǎng)絡(luò)生存時間由于WSN節(jié)點硬件平臺資源受限、網(wǎng)絡(luò)節(jié)點數(shù)量巨大、實際應(yīng)用的環(huán)境條件復(fù)雜且大多不允許對“失效”節(jié)點進行電池更換，因此,如何節(jié)約各節(jié)點有限的電池能量并盡力延長整體網(wǎng)絡(luò)的生存時間已成為WSN的重要性能指標[6].能量的有效性將是WSN覆蓋控制所面臨的一個主要挑戰(zhàn).(4算法精確性由于受實際部署條件差異、網(wǎng)絡(luò)資源有限和覆蓋目標特性等多方面的影響，使得WSN覆蓋控制在很多情況下是一個NP完全問題[7,8],只能達到近似優(yōu)化覆蓋[9],勢必會造成覆蓋控制算法執(zhí)行結(jié)果產(chǎn)生誤差,甚至不能保證算法的有效執(zhí)行.如何減小誤差,提高算法的精確性成為優(yōu)化覆蓋控制算法的一項重要內(nèi)容.(5算法復(fù)雜性不同WSN覆蓋控制協(xié)議及算法其實現(xiàn)方式不同導(dǎo)致算法復(fù)雜程度也有較大差別.衡量一個WSN覆蓋控制算法是否優(yōu)化的一項重要標準就是其算法的復(fù)雜性程度.算法的復(fù)雜性程度通常包括時間復(fù)雜度、通信復(fù)雜度以及實現(xiàn)復(fù)雜度等，需要綜合考慮.(6網(wǎng)絡(luò)動態(tài)性一些特殊的應(yīng)用環(huán)境，如運動目標監(jiān)測覆蓋［10,11］、網(wǎng)絡(luò)動態(tài)覆蓋［12］等，需要網(wǎng)絡(luò)的覆蓋控制協(xié)議與算法考424JournalofSoftware軟件學(xué)報Vol.17,No.3,March2006慮節(jié)點具有運動能力、網(wǎng)絡(luò)整體或傳感目標運動等網(wǎng)絡(luò)動態(tài)特性.因此,WSN覆蓋控制的網(wǎng)絡(luò)動態(tài)特性也成為一項必要的評價標準.(7網(wǎng)絡(luò)可擴展性支持保證網(wǎng)絡(luò)的可擴展性是WSN覆蓋控制的另一項關(guān)鍵需求.沒有網(wǎng)絡(luò)可擴展性保證，網(wǎng)絡(luò)的性能會隨著網(wǎng)絡(luò)規(guī)模的增加而顯著降低.針對不同的應(yīng)用需求,WSN的網(wǎng)絡(luò)規(guī)模相差較大，網(wǎng)絡(luò)的可擴展性需求在WSN中尤為明顯.(8算法實施策略WSN覆蓋控制算法的執(zhí)行可以有分布式、集中式以及兩者的混合式3種方式.通常來說，由于WSN自身的能量消耗、協(xié)議操作代價、網(wǎng)絡(luò)性能和精度等要求，使得利用本地信息執(zhí)行的分布式算法更為適用.在一些特殊的網(wǎng)絡(luò)操作環(huán)境下,分布式、集中式兩種方式混合執(zhí)行則更為有效.除了上面列出的一些所面臨的挑戰(zhàn)之外,WSN覆蓋控制協(xié)議算法還會存在是否需要知道網(wǎng)絡(luò)節(jié)點位置、是否需要專門的覆蓋控制消息等差別.同樣，它們也是我們設(shè)計、分析具體協(xié)議和算法時要考察的內(nèi)容.2無線傳感器網(wǎng)絡(luò)覆蓋控制問題分類WSN從誕生之初就與應(yīng)用密切相關(guān),WSN覆蓋控制更是如此.如今的WSN覆蓋控制問題不僅包括單純的覆蓋含義,更是與節(jié)能通信、路徑規(guī)劃、可靠通信和目標定位等具體應(yīng)用緊密相連.為了對WSN覆蓋控制問題有更加全面的認識,本文分別從配置方式和相關(guān)應(yīng)用屬性兩個角度進行WSN覆蓋控制問題分類.按照無線傳感器網(wǎng)絡(luò)節(jié)點不同配置方式（即節(jié)點是否需要知道自身位置信息，我們可以將WSN的覆蓋問題分為確定性覆蓋、隨機覆蓋兩大類.下面逐一對這兩類覆蓋控制類型加以總結(jié).2.1.1確定性覆蓋如果WSN的狀態(tài)相對固定或是WSN環(huán)境已知，就可以根據(jù)預(yù)先配置的節(jié)點位置確定網(wǎng)絡(luò)拓撲情況或增加關(guān)鍵區(qū)域的傳感器節(jié)點密度,這種情況被稱為確定性覆蓋問題.此時的覆蓋控制問題,就成為一種特殊的網(wǎng)絡(luò)或路徑規(guī)劃問題.典型的確定性覆蓋有確定性區(qū)域/點覆蓋、基于網(wǎng)格（grid的目標覆蓋和確定性網(wǎng)絡(luò)路徑/目標覆蓋3種類型.確定性區(qū)域/點覆蓋是指已知節(jié)點位置的WSN要完成目標區(qū)域或目標點的覆蓋,文獻［7,1316］研究的都是此類問題.與確定性區(qū)域/點覆蓋相關(guān)的兩個著名計算幾何問題為藝術(shù)館走廊監(jiān)控問題（artgalleryproblem［17］以及圓周覆蓋問題（circlecoveringproblem［17］.基于網(wǎng)格的目標覆蓋是指當?shù)乩憝h(huán)境情況預(yù)先確定時，使用二維（也可以為三維的網(wǎng)格進行網(wǎng)絡(luò)的建模,并選擇在合適的格點配置傳感器節(jié)點來完成區(qū)域/目標的覆蓋.文獻［9,18,19］中對這一問題進行了有益的研究.確定性網(wǎng)絡(luò)路徑/目標覆蓋同樣也是考慮WSN傳感器節(jié)點位置已知情況，但這類問題特別考慮了如何對穿越網(wǎng)絡(luò)的目標或其經(jīng)過的路徑上各點進行感應(yīng)與追蹤.相關(guān)研究包括文獻［10,20］.2.1.2隨機覆蓋在許多實際自然環(huán)境中，由于網(wǎng)絡(luò)情況不能預(yù)先確定且多數(shù)確定性覆蓋模型會給網(wǎng)絡(luò)帶來對稱性與周期性特征,從而掩蓋了某些網(wǎng)絡(luò)拓撲的實際特性.再加上WSN自身拓撲變化復(fù)雜，導(dǎo)致采用確定性覆蓋在實際應(yīng)用中具有很大的局限性，不能適用于戰(zhàn)場等危險或其他環(huán)境惡劣的場所.因此,我們需要進一步對節(jié)點隨機分布在傳感區(qū)域而預(yù)先沒有得到自身位置的情況進行討論,這正是WSN隨機覆蓋所要解決的問題.目前,WSN的隨機覆蓋已成為WSN覆蓋控制的一個熱點問題,我們可大致將這類問題具體分為隨機節(jié)點覆蓋和動態(tài)網(wǎng)絡(luò)覆蓋兩類.隨機節(jié)點覆蓋考慮在WSN中傳感器節(jié)點隨機分布且預(yù)先不知道節(jié)點位置的條件下，網(wǎng)絡(luò)完成對監(jiān)測區(qū)域的覆蓋任務(wù).學(xué)者關(guān)于此類問題的研究內(nèi)容較多，主要包括文獻［8,11,21-27］.與一般WSN一旦部署則網(wǎng)絡(luò)中的傳感器節(jié)點的位置就固定不變有所不同，動態(tài)網(wǎng)絡(luò)覆蓋則是考慮一些特任彥等:無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法425殊環(huán)境中部分傳感器節(jié)點具備一定運動能力的情況［12］.該類網(wǎng)絡(luò)可以動態(tài)完成相關(guān)覆蓋任務(wù).2.2相關(guān)應(yīng)用屬性分類作為一種源于應(yīng)用而又服務(wù)于應(yīng)用的現(xiàn)實、可行的網(wǎng)絡(luò)技術(shù),無線傳感器網(wǎng)絡(luò)在軍事以及民用都具有非常廣闊的應(yīng)用前景［28］,WSN覆蓋控制也是如此.如今,WSN覆蓋控制問題不僅包括單純的覆蓋含義,更與節(jié)能通信、路徑規(guī)劃、可靠通信和目標定位等具體應(yīng)用緊密相連,并依舊屬于覆蓋控制的范疇.因此,我們還可以從WSN相關(guān)應(yīng)用屬性這一新的視角對WSN覆蓋控制問題進行重新分類和研究.2.2.1節(jié)能覆蓋由于WSN中傳感器節(jié)點自身體積較小、電池能量資源有限,如何保證大規(guī)模網(wǎng)絡(luò)環(huán)境下傳感器節(jié)點能量的有效使用就成為需要關(guān)注的一項重要研究內(nèi)容,它直接影響到整個網(wǎng)絡(luò)生存時間能否充分延長.如文獻［7,8,14,15,21］所述，采用輪換“活躍”和“休眠”節(jié)點的節(jié)能覆蓋方案,可以有效地提高網(wǎng)絡(luò)生存時間.而輪換活躍/休眠節(jié)點的節(jié)能覆蓋方案關(guān)鍵,就是要在保證一定網(wǎng)絡(luò)覆蓋要求的條件下，最大化輪換節(jié)點集合數(shù)目.2.2.2柵欄覆蓋WSN中有一類與覆蓋控制密切相關(guān)的特殊問題——柵欄覆蓋，它考察了目標穿越WSN時被檢測或是沒有被檢測的情況,反映了給定WSN所能提供的傳感、監(jiān)視能力.這類覆蓋控制問題的目標是找出連接出發(fā)位置（記為S和離開位置（記為D的一條或多條路徑，使得這樣的路徑能夠在不同模型定義下提供對目標的不同傳感/監(jiān)視質(zhì)量.根據(jù)目標穿越WSN時所采用模型的不同,柵欄覆蓋又可以具體分為“最壞與最佳情況覆蓋”和“暴露穿越”兩種類型.“最壞與最佳情況覆蓋”問題中，對于穿越網(wǎng)絡(luò)的目標而言,最壞情況是指考察所有穿越路徑中不被網(wǎng)絡(luò)傳感器節(jié)點檢測的概率最小情況；對應(yīng)的最佳情況是指考察所有穿越路徑中被網(wǎng)絡(luò)傳感器節(jié)點發(fā)現(xiàn)的概率最大情況.此問題相關(guān)研究包括文獻［10,12,20,23］.與單純考慮離傳感器節(jié)點距離的“最壞與最佳情況覆蓋”不同,“暴露穿越”同時考慮了“目標暴露（targetexposure”的時間因素和傳感器節(jié)點對于目標的“感應(yīng)強度”因素.這種覆蓋模型更為符合實際環(huán)境中，運動目標由于穿越WSN區(qū)域的時間增加而“感應(yīng)強度”累加值增大的情況.文獻［11,22,29,30］就考察了這類問題.2.2.3連通性覆蓋連通性覆蓋問題也是WSN覆蓋控制相關(guān)應(yīng)用屬性中的一個重要組成部分,它同時考慮了WSN的覆蓋能力和網(wǎng)絡(luò)連通性這兩個相互聯(lián)系的屬性.連通覆蓋問題所要解決的是如何同時滿足網(wǎng)絡(luò)一定的傳感覆蓋和通信連通性需求,這對于一些要求可靠通信的應(yīng)用至關(guān)重要.根據(jù)具體的連通性要求,連通性覆蓋又可具體分為兩類:活躍節(jié)點集連通覆蓋［13,25］,是針對采用活躍節(jié)點集輪換機制的情況,考慮如何保證指定傳感區(qū)域的覆蓋和網(wǎng)絡(luò)的連通性;而連通路徑覆蓋［16,18,27］,則是考慮通過選擇可能的連通傳感器節(jié)點路徑來得到最大化的網(wǎng)絡(luò)覆蓋效果.2.2.4目標定位覆蓋

在某些特殊環(huán)境下,WSN覆蓋配置“伴隨而來”的是WSN的目標定位問題，我們可稱此時的WSN覆蓋為目標定位覆蓋.例如在前面提到的網(wǎng)格條件下，網(wǎng)絡(luò)的目標定位問題即為及時查詢出目標所在網(wǎng)格被周圍哪些傳感器格點所覆蓋.文獻[9,19]就專門進行了此方面的研究.由以上WSN覆蓋控制分類我們不難看出：配置方式和相關(guān)應(yīng)用屬性兩種分類方法既有各自特殊的分類角度,又同時會有具體研究內(nèi)容上的重疊.基于本部分內(nèi)容，圖1進行了WSN覆蓋控制問題各種協(xié)議和算法的分類總結(jié).426JournalofSoftware軟件學(xué)報Vol.17,No.3,March2006PiatacclsandalgorithmscfcnveiagecoiiidlforApplicMaipiopeityDeteniiinsticStochasticIEnet即effitiencyBEiriieiConnectfi/ity

cnveragfTaiget

location廠Tt1—DeteiministicaieanointcowDeteniiinsticStochasticIEnet即effitiencyBEiriieiConnectfi/ity

cnveragfTaiget

location廠Tt1—Deteiministicaieanointcow磨IDetemiiiifjtiiipath/taiget1ctr/ieidgeGiicl-Bassdtai^tcoverageStacliPisticimdecavem國Dytiaimccaveiagfco\retfige—廠尸TWorstandExposureCumectedCmilected1bestcas&-Bas&dftctiv?nodepathcoveragectK^iagesetcmieiEigecovei?咿Tt■匚9卷人料23/，乎"CDVfitai圖1無線傳感器網(wǎng)絡(luò)覆蓋控制協(xié)議和算法分類3典型的無線傳感器網(wǎng)絡(luò)覆蓋控制算法與協(xié)議基于前一部分對WSN覆蓋控制問題各種協(xié)議和算法進行的分類和總結(jié),本節(jié)將詳細介紹一些典型的覆蓋控制協(xié)議算法研究成果,并深入分析各種協(xié)議算法的優(yōu)缺點.3.1基于網(wǎng)格的覆蓋定位傳感器配置算法[9]基于網(wǎng)格的覆蓋定位傳感器配置算法是基于網(wǎng)格的目標覆蓋類型（確定性覆蓋中的一種，同時也屬于目標定位覆蓋的內(nèi)容.Lin等人在文獻[9]中將此優(yōu)化覆蓋定位問題轉(zhuǎn)化為最小化距離錯誤問題,并加以改進,提出了一種在有限代價條件下最小化最大錯誤距離的組合優(yōu)化配置方法.考慮網(wǎng)絡(luò)傳感器節(jié)點以及目標點都采用網(wǎng)格形式配置，傳感器節(jié)點采用0/1覆蓋模型,并使用能量矢量來表示格點的覆蓋.如圖2所示，網(wǎng)絡(luò)中的各格點都可至少被一個傳感器節(jié)點所覆蓋（即該點能量矢量中至少一位為1,此時區(qū)域達到了完全覆蓋.例如,格點位置8的能量矢量為（0,0,1,1,0,0.在網(wǎng)絡(luò)資源受限而無法達到格點完全識別時,就需要考慮如何提高定位精度的問題.而錯誤距離是衡量位置精度的一個最直接的標準,錯誤距離越小，則覆蓋識別結(jié)果越優(yōu)化.我們設(shè)計了一種模擬退火算法來最小化距離錯誤.初始時刻假設(shè)每個格點都配置有傳感器.若配置代價上限制沒有達到就循環(huán)執(zhí)行以下過程:首先試圖刪除一個傳感器節(jié)點，之后進行配置代價評價.如果評價不通過就將該節(jié)點移動到另外一個隨機選擇的位置,之后再進行配置代價評價.循環(huán)得到優(yōu)化值后同時保存新的節(jié)點配置情況.最后，改進算法停止執(zhí)行的準則.在達到模擬退火算法的冷卻溫度tf時,優(yōu)化覆蓋識別的網(wǎng)絡(luò)配置方案也同時達到.優(yōu)點:(1算法結(jié)果表明：與采用隨機配置達到完全覆蓋的方案相比,該算法更為有效，具有魯棒性并易于擴展；(2適用于不規(guī)則的傳感器網(wǎng)絡(luò)區(qū)域.缺點：(1網(wǎng)格化的網(wǎng)絡(luò)建模方式會掩蓋網(wǎng)絡(luò)的實際拓撲特征;(2網(wǎng)絡(luò)中均為同質(zhì)節(jié)點,不適用于網(wǎng)絡(luò)中存在節(jié)點配置代價和覆蓋能力有差異的情況.pointFig.2Anexampleofcompletecoveredfield圖2區(qū)域完全覆蓋示意圖任彥等:無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法4273.2輪換活躍/休眠節(jié)點的NodeSelf-Scheduling覆蓋協(xié)議[15]采用輪換“活躍”和“休眠”節(jié)點的NodeSelf-Scheduling[15]覆蓋控制協(xié)議可以有效延長網(wǎng)絡(luò)生存時間，該協(xié)議同時屬于確定性區(qū)域/點覆蓋和節(jié)能覆蓋類型.協(xié)議采用節(jié)點輪換周期工作機制，每個周期由一個self-scheduling階段和一個working階段組成.在self-scheduling階段:各節(jié)點首先向傳感半徑內(nèi)鄰居節(jié)點廣播通告消息,其中包括節(jié)點ID和位置(若傳感半徑不同則包括發(fā)送節(jié)點傳感半徑.節(jié)點檢查自身傳感任務(wù)是否可由鄰居節(jié)點完成，可替代的節(jié)點返回一條狀態(tài)通告消息,之后進入“休眠狀態(tài)”,需要繼續(xù)工作的節(jié)點執(zhí)行傳感任務(wù).在判斷節(jié)點是否可以休眠時,如果相鄰節(jié)點同時檢查到自身的傳感任務(wù)可由對方完成并同時進入“休眠狀態(tài)”,就會出現(xiàn)如圖3所示的“盲點(a(bFig.3The“blindpoint”inWSN圖3網(wǎng)絡(luò)中出現(xiàn)的“盲點”在圖3(a中,節(jié)點e和f的整個傳感區(qū)域都可以被相鄰的鄰居節(jié)點代替覆蓋.e和f節(jié)點滿足進入“休眠狀態(tài)”條件之后,將關(guān)閉自身節(jié)點的傳感單元進入“休眠狀態(tài)”,但這時就出現(xiàn)了不能被WSN檢測的區(qū)域即網(wǎng)絡(luò)中出現(xiàn)“盲點”,如圖3(b所示.為了避免這種情況的發(fā)生,文獻［15］中,節(jié)點在self-scheduling階段檢查之前執(zhí)行一個退避機制:每個節(jié)點在一個隨機產(chǎn)生的Td時間之后再開始檢查工作.此外,退避時間還可以根據(jù)周圍節(jié)點密度而計算，這樣就可以有效地控制網(wǎng)絡(luò)“活躍”節(jié)點的密度.為了進一步避免“盲點”的出現(xiàn)，每個節(jié)點在進入“休眠狀態(tài)”之前還將等待Tw時間來監(jiān)聽鄰居節(jié)點的狀態(tài)更新.該協(xié)議是作為LEACH分簇協(xié)議［31］的一個擴展來實現(xiàn)的，有關(guān)仿真結(jié)果證明:WSN的平均網(wǎng)絡(luò)生存時間較LEACH分簇協(xié)議延長了1.7倍.優(yōu)點：(1不會出現(xiàn)覆蓋“盲點”,因而可以保持網(wǎng)絡(luò)的充分覆蓋；(2該算法可以有效控制網(wǎng)絡(luò)節(jié)點的冗余，同時保持一定的傳感可靠性；(3節(jié)點輪換機制周期工作有效地延長了網(wǎng)絡(luò)生存時間；(4仿真實驗表明：節(jié)點輪換機制對位置錯誤、包丟失以及節(jié)點失效具有魯棒性，依然可以保持網(wǎng)絡(luò)的充分覆蓋.缺點：(1需要預(yù)先確定節(jié)點位置并要求整個網(wǎng)絡(luò)同時具有時間同步支持，給網(wǎng)絡(luò)帶來了附加實現(xiàn)代價；(2該機制無法使WSN區(qū)域上的邊界節(jié)點“休眠”,這就影響了整個網(wǎng)絡(luò)的生存時間延長效果；(3節(jié)點輪換機制只能適用于傳感器節(jié)點覆蓋區(qū)域為圓周(或圓球，不適用于不規(guī)則節(jié)點感應(yīng)模型；(4需要綜合優(yōu)化考慮活躍節(jié)點數(shù)量和網(wǎng)絡(luò)覆蓋效果.3.3最壞與最佳情況覆蓋［10,20］最壞與最佳情況覆蓋算法同時屬于確定性網(wǎng)絡(luò)路徑/目標覆蓋和柵欄覆蓋類型.算法考慮如何對穿越網(wǎng)絡(luò)的目標或其所在路徑上各點進行感應(yīng)與追蹤，體現(xiàn)了一種網(wǎng)絡(luò)的覆蓋性質(zhì).428JournalofSoftware軟件學(xué)報Vol.17,No.3,March2006Meguerdichian等人先后在文獻［20］和文獻［10］中定義了“最大突破路徑（maximalbreachpath”和“最大支撐路徑（maximalsupportpath”,分別使得路徑上的點到周圍最近傳感器的最小距離最大化以及最大距離最小化.顯然，這兩種路徑分別代表了WSN最壞（不被檢測概率最小和最佳（被發(fā)現(xiàn)的概率最大的覆蓋情況.文中分別采用計算幾何中的Voronoi圖與Delaunay三角形來完成最大突破路徑和最大支撐路徑的構(gòu)造和查找.其中,Voronoi圖是由所有Delaunay三角形邊上的垂直平分線形成；而Delaunay三角形的各頂點為網(wǎng)絡(luò)的傳感器節(jié)點，并滿足子三角形外接圓中不含其他節(jié)點,如圖4所示.由于Voronoi圖中的線段具有到最近的傳感器節(jié)點距離最大的性質(zhì)，因此最大突破路徑一定是由Voronoi圖中的線段組成.最大突破路徑查找過程如下：（1基于各節(jié)點的位置產(chǎn)生網(wǎng)絡(luò)Voronoi圖;（2給每一條邊賦予一個權(quán)重來代表到最近傳感器節(jié)點的距離；(3在最小和最大的權(quán)重之間執(zhí)行二進制查找算法:每一步操作之前給出一個參考權(quán)重標準，然后進行寬度優(yōu)先查找(breadth-first-search，檢查是否存在一條從S到D的路徑，滿足路徑上線段的權(quán)重都比參考權(quán)重標準要大.如果路徑存在，則增加參考權(quán)重標準來縮小路徑可選擇的線段數(shù)目，否則就降低參考權(quán)重標準.(4最后得到一條從S到D的路徑,也就是最大突破路徑，圖4中用Pmax_breach表示.類似地，由于Delaunay三角形是由所有到最近傳感器節(jié)點距離最短的線段組成，因此最大支撐路徑必然由Delaunay三角形的線段構(gòu)成.給每一條邊賦予一個權(quán)重來代表路徑上所有到周圍最近傳感器節(jié)點的最大距離，查找算法同上.圖4中用Pmax_support表示了算法執(zhí)行后得到的一條最大支撐路徑.優(yōu)點:(1在最佳與最差兩種度量條件下，分別得到了臨界的網(wǎng)絡(luò)路徑規(guī)劃結(jié)果，可以指導(dǎo)網(wǎng)絡(luò)節(jié)點的配置來改進整體網(wǎng)絡(luò)的覆蓋；(2作為一種特殊的WSN覆蓋控制算法，適用于網(wǎng)絡(luò)路徑規(guī)劃、目標觀測等許多應(yīng)用場所.缺點：(1算法是集中式的計算方式，需要預(yù)先知道各節(jié)點的位置信息；(2算法沒有考慮實際中障礙、環(huán)境和噪聲等可能造成的影響；(3網(wǎng)絡(luò)中均為同質(zhì)節(jié)點，不適用于網(wǎng)絡(luò)中存在節(jié)點覆蓋能力有差異時算法的執(zhí)行情況.3.4暴露穿越［11］暴露穿越覆蓋同時屬于隨機節(jié)點覆蓋和柵欄覆蓋的類型.如前所述,“目標暴露(targetexposure”覆蓋模型同時考慮時間因素和節(jié)點對于目標的“感應(yīng)強度”因素，更為符合實際環(huán)境中，運動目標由于穿越網(wǎng)絡(luò)時間增加而“感應(yīng)強度”累加值增大的情況.節(jié)點s的傳感模型定義為KpsdpsS］,(［,(X其中p為目標點，正常數(shù)X和K均為網(wǎng)絡(luò)經(jīng)驗參數(shù).最小暴露路徑代表了WSN最壞的覆蓋情況,而一個運動目標沿著路徑p(t在時間間隔［t1,t2］內(nèi)經(jīng)過WSN監(jiān)視區(qū)域的暴露路徑在文獻［11］中被定義為tttptpFItttpEttdd(d(,(,,((1221卜.其中I(F,p(t代表了在傳感區(qū)域F中沿著路徑p(t運動時被相應(yīng)傳感器(有最近距離傳感器和全部傳感器兩種SFig.4ExamplesoftheVoronoidiagramandtheDelaunaytriangulation圖4Voronoi圖和Delaunay三角形示意圖任彥等:無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法429感應(yīng)的效果.我們提出了一種數(shù)值計算的近似方法來找到連續(xù)的最小暴露路徑:首先,將傳感器網(wǎng)絡(luò)區(qū)域進行網(wǎng)格劃分,并假設(shè)暴露路徑只能由網(wǎng)格的邊與對角線組成;之后，為每條線段賦予一定的暴露路徑權(quán)重；最后，執(zhí)行Djikstra算法得到近似的最小暴露路徑.優(yōu)點：(1暴露覆蓋模型更為符合目標由于穿越WSN區(qū)域的時間增加而被檢測概率增大的實際情況；(2分布式的算法執(zhí)行方式,不需要預(yù)先知道整個網(wǎng)絡(luò)的節(jié)點配置情況；(3根據(jù)需要可以選擇不同的感應(yīng)強度模型和網(wǎng)格劃分，從而得到精度不同的暴露路徑.缺點：(1暴露精度與算法運行時間是一對矛盾，需要平衡考慮；(2算法沒有考慮實際中障礙、環(huán)境以及傳感器節(jié)點本身運動等可能造成的影響.3.5圓周覆蓋［24,26］Huang在文獻［24］中將隨機節(jié)點覆蓋類型的圓周覆蓋歸納為決策問題：目標區(qū)域中配置一組傳感器節(jié)點,看看該區(qū)域能否滿足k覆蓋，即目標區(qū)域中每個點都至少被k個節(jié)點覆蓋.我們考慮每個傳感節(jié)點覆蓋區(qū)域的圓周重疊情況,進而根據(jù)鄰居節(jié)點信息來確定是否一個給定傳感器的圓周被完全覆蓋,如圖5所示［17］.2n0n(a(bFig.5CoverageofthesensorS’sperimeter圖5傳感器節(jié)點S圓周的覆蓋情況該算法可以用分布式方式實現(xiàn):傳感器S首先確定圓周被鄰居節(jié)點覆蓋的情況,如圖5(a所示,3段圓周［0,a］,［b,c］,［d,n］分別被S的3個鄰居節(jié)點所覆蓋.再將結(jié)果按照升序順序記錄在［0,2n］區(qū)間，如圖5(b所示，這樣就可以得到節(jié)點S的圓周覆蓋情況:［0,b］段為1,［b,a］段為2,［a,d］段為1,［d,c］段為2,［c,n］段為1.文獻［24］給出證明：“傳感器節(jié)點圓周被充分覆蓋等價于整個區(qū)域被充分覆蓋”.每個傳感器節(jié)點收集本地信息來進行本節(jié)點圓周覆蓋判斷，并且該算法還可以進一步擴展到不規(guī)則的傳感區(qū)域中使用.在文獻［24］中的二維圓周覆蓋問題基礎(chǔ)上,Huang進一步在文獻［26］中使用將三維圓球覆蓋影射為二維圓周覆蓋的類似方法，在不增加計算復(fù)雜性的前提下使用分布式方式解決了三維圓球體覆蓋的問題.優(yōu)點：(1算法考慮了傳感器具有不同覆蓋傳感能力以及不規(guī)則傳感范圍的情況，具有較好的適用性；(2分布式的算法執(zhí)行方式,減小了整個網(wǎng)絡(luò)的通信與計算負載；(3算法可以適用于二維以及三維的網(wǎng)絡(luò)環(huán)境.缺點：(1該算法只考察了區(qū)域內(nèi)各點的覆蓋情況,并未考慮各點如何被網(wǎng)絡(luò)傳感器節(jié)點所覆蓋；430JournalofSoftware軟件學(xué)報Vol.17,No.3,March2006(2缺少相應(yīng)優(yōu)化網(wǎng)絡(luò)節(jié)點配置及改善網(wǎng)絡(luò)覆蓋進一步的協(xié)議和算法.3.6連通傳感器覆蓋(connectedsensorcover［16］Gupta在文獻［16〕中設(shè)計的算法通過選擇連通的傳感器節(jié)點路徑來得到最大化的網(wǎng)絡(luò)覆蓋效果,該算法同時屬于連通性覆蓋中的連通路徑覆蓋以及確定性區(qū)域/點覆蓋類型.當指令中心向WSN發(fā)送一個感應(yīng)區(qū)域查詢消息時,連通傳感器覆蓋的目標是選擇最小的連通傳感器節(jié)點集合并充分覆蓋WSN區(qū)域.文獻［16］分別設(shè)計了集中與分布式兩種貪婪算法.假設(shè)已選擇的傳感器節(jié)點集為M,剩余與M有相交傳感區(qū)域的傳感器節(jié)點稱為候選節(jié)點.集中式算法初始節(jié)點隨機選擇構(gòu)成M之后,在所有從初始節(jié)點集合出發(fā)到候選節(jié)點的路徑中選擇一條可以覆蓋更多未覆蓋子區(qū)域的路徑.將該路徑經(jīng)過的節(jié)點加入M,算法繼續(xù)執(zhí)行直到網(wǎng)絡(luò)查詢區(qū)域可以完全被更新后的M所覆蓋.圖6表示了該貪婪算法執(zhí)行的方式.在圖6(a中，貪婪算法會選擇路徑P2得到圖6(b,這是由于在所有備選路徑中選擇C3和C4組成的路徑P2可以覆蓋更多未覆蓋子區(qū)域.(a(bFig.6Greedyalgorithmoftheconnectedsensorcover圖6連通傳感器覆蓋的貪婪算法連通傳感器覆蓋的分布式貪婪算法執(zhí)行過程是:首先從M中最新加入的候選節(jié)點開始執(zhí)行，在一定范圍內(nèi)廣播候選路徑查找消息(CPS;收到CPS消息的節(jié)點判斷自身是否為候選節(jié)點,如果是，則單播方式返回發(fā)起者一個候選路徑響應(yīng)消息(CPR;發(fā)起者選擇可以最大化增加覆蓋區(qū)域的候選路徑；更新各參數(shù)，算法繼續(xù)執(zhí)行,直到網(wǎng)絡(luò)查詢區(qū)域可完全被更新后的M所覆蓋.優(yōu)點：(1本算法的節(jié)點傳感區(qū)域模型可以是任意凸形區(qū)域,更加符合實際環(huán)境；(2可以靈活地選擇使用集中式或分布式方式實現(xiàn)；(3在保證網(wǎng)絡(luò)覆蓋任務(wù)的同時,考慮了網(wǎng)絡(luò)的連通性,算法周期執(zhí)行降低了網(wǎng)絡(luò)通信代價,并可以延長網(wǎng)絡(luò)的生存時間.缺點：(1雖然同時考慮了連通性與網(wǎng)絡(luò)的覆蓋性，但不能保證查詢返回結(jié)果的精度；(2沒有考慮實際無線信道中出現(xiàn)的通信干擾和消息丟失，是一種單純考慮消息傳遞的理想情況.4無線傳感器網(wǎng)絡(luò)覆蓋控制算法比較與亟待解決的問題4.1覆蓋控制算法比較為了對已有算法進行相互間的比較性總結(jié),本節(jié)對照本文第1節(jié)給出的WSN覆蓋控制所面臨的挑戰(zhàn)進行了各種算法的優(yōu)缺點總結(jié)和比較，見表1.任彥等:無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法431Table1Comparisonofcoveragecontrolalgorithmsinwirelesssensornetworks表1WSN覆蓋控制算法比較ArticleCoverageabilityNetworkconnectivityAccuracyComplexityNetworkmobilityEnergyefficiencyNetworkscalabilityDeploymentmodelLocationBasedNegotiation-Based[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,我們可以從整體上對無線傳感器網(wǎng)絡(luò)中的覆蓋控制問題的各種算法有一個比較清晰的認識.此外，對照WSN覆蓋控制評價標準進行的相關(guān)研究成果優(yōu)缺點比較,有助于我們更加全面地了解已有協(xié)議算法,并進一步發(fā)現(xiàn)和考慮其中一些亟待解決的問題.4.2亟待解決的問題雖然WSN覆蓋控制研究已經(jīng)取得了一定的成果，但是仍有很多問題需要解決,集中體現(xiàn)在以下幾點：(1感知模型種類的完善.從本文綜述的各種WSN覆蓋成果不難看出：目前使用的傳感器節(jié)點感知模型包括圓形區(qū)域感知［7,9,10,15,16,19,20］與負指數(shù)距離感知［11,22,29,30］兩種感知模型，不能適用于實際WSN環(huán)境的感知模型多樣化需要.此外，目前節(jié)點感知模型大多沒有考慮實際無線信道中出現(xiàn)的通信干擾，是一種理想模型［16］.因此，還需要進一步考慮更加完善的感知模型種類；(2三維空間的覆蓋控制.從文本第3節(jié)的討論不難看出：盡管目前許多方案都很好地解決了二維平面的覆蓋控制問題［10,11,20,23］，但由于三維空間的覆蓋控制在計算幾何與隨機圖論等數(shù)學(xué)理論上仍是一個NP難問題［17］,因此,現(xiàn)有的三維空間覆蓋控制只能得到近似優(yōu)化的結(jié)果［26,27］.如何針對具體的WSN三維空間應(yīng)用需要設(shè)計出有效的算法與協(xié)議,將會是一個很有意義的研究課題；(3提供移動性的支持.目前,WSN覆蓋控制理論與算法大都假定傳感節(jié)點或者網(wǎng)絡(luò)是靜態(tài)的，但在戰(zhàn)場等應(yīng)用中可能需要節(jié)點或網(wǎng)絡(luò)具有移動性［12］,因此,新的覆蓋控制理論與算法需要提供對移動性的支持；(4符合WSN與Internet交互的相應(yīng)WSN覆蓋控制方案.由于WSN將邏輯上的信息世界與真實的物理世界融合在一起，因此會在一些實際應(yīng)用中大量出現(xiàn)WSN與Internet之間數(shù)據(jù)與信息的交互,這就需要未來研究相應(yīng)的WSN覆蓋控制方案；(5開發(fā)和設(shè)計更多結(jié)合WSN覆蓋控制的應(yīng)用.覆蓋控制問題涉及到WSN通信、感應(yīng)、計算和存儲等許多方面,將會在戰(zhàn)場偵查、陣地防御和情報獲取等軍事環(huán)境以及林場/牧場監(jiān)視、災(zāi)難救護、環(huán)境監(jiān)測和醫(yī)療觀察等很多民用項目中有廣泛應(yīng)用.因此，如何利用WSN覆蓋控制理論與各種算法，開發(fā)和設(shè)計更多結(jié)合WSN覆蓋控制的應(yīng)用,將會給人類生活帶來進一步的改善.432JournalofSoftware軟件學(xué)報Vol.17,No.3,March20065總結(jié)無線傳感器網(wǎng)絡(luò)將邏輯上的信息世界與真實的物理世界融合在一起，極大地提高了人們認識和改造世界的能力.而網(wǎng)絡(luò)覆蓋控制作為WSN實施過程中的一個基本問題，反映了網(wǎng)絡(luò)所能提供的“感知”服務(wù)質(zhì)量.本文立足于WSN的覆蓋控制問題,對近年來提出的各種覆蓋控制問題的新思想和代表性研究成果進行歸納并加以介紹，隨后結(jié)合WSN覆蓋控制評價標準進行了比較性總結(jié),進而深入分析了目前WSN覆蓋控制亟待解決的問題，并展望了其未來可能的發(fā)展方向.致謝在此，我們向曾經(jīng)對本文提出寶貴建議的審稿專家以及曾參與本文內(nèi)容討論的所有同學(xué)、老師表示衷心的感謝.References:[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16]AkyildizIF,SuW,SankarasubramaniamY,CayirciE.Wirelesssensornetworks:Asurvey.ComputerNetworks,2002,38(4:393-422.RenFY,HuangHN,LinC.Wirelesssensornetworks.JournalofSoftware,2003,14(2:1148-1157(inChinesewithEnglishabstract./1000-9825/14/1148.htmPottieGJ,KaiserWJ.Wirelessintegratednetworksensors.CommunicationsoftheACM,2000,43(5:51-58.SohrabiK,GaoJ,AilawadhiV,PottieGJ.Protocolsforself-organizationofawirelesssensornetwork.IEEEPersonalCommunications,2000,7(5:16-27.CardeiM,WuJ.Coverageinwirelesssensornetworks.In:IlyasM,MagboubI,eds.HandbookofSensorNetworks,chapter19.CRCPress,2004.LiJZ,LiJB,ShiSF.Concepts,issuesandadvanceofsensornetworksanddatamanagementofsensornetworks.JournalofSoftware,2003,14(10:1717-1727(inChinesewithEnglishabstract./1000-9825/14/1717.htmSlijepcevicS,PotkonjakM.Powerefficientorganizationofwirelesssensornetworks.In:GlisicS,ed.Proc.oftheIEEEInt’lConf.onCommunications(ICC.Helsinki:IEEEPress,2001.472-476.CardeiM,DuDZ.Improvingwirelesssensornetworklifetimethroughpowerawareorganization.WirelessNetworks,2005,11(3:333-340.LinFYS,ChiuPL.Anear-optimalsensorplacementalgorithmtoachievecompletecoverage/discriminationinsensornetworks.IEEECommunicationsLetters,2005,9(1:43-45.MegerianS,KoushanfarF,PotkonjakM,SrivastavaMB.Worstandbest-casecoverageinsensornetworks.IEEETrans.onMobileComputing,2005,4(1:84-92.MeguerdichianS,KoushanfarF,QuG,PotkonjakM.Exposureinwirelessad-hocsensornetworks.In:RoseC,ed.Proc.oftheACMInt’lConf.onMobileComputingandNetworking(MobiCom.NewYork:ACMPress,2001.139-150.CortesJ,MartinezS,KaratasT,BulloF.Coveragecontrolformobilesensingnetworks.IEEETrans.onRoboticsandAutomation,2004,20(2:243-255.KarK,BanerjeeS.Nodeplacementforconnectedcoverageinsensornetworks.In:CrowcroftJ,ed.Proc.oftheModelingandOptimizationinMobile,AdHocandWirelessNetworks.Sophia-Antipolis:IEEEPress,2003.50-52.YanT,HeT,StankovicJA.Differentiatedsurveillanceforsensornetworks.In:AkyildizIF,EstionD,eds.Proc.oftheACMInt’lConf.onEmbeddedNetworkedSensorSystems(SenSys.NewYork:ACMPress,2003.51-62.TianD,GeorganasND.Anodeschedulingschemeforenergyconservationinlargewirelesssensornetworks.WirelessCommunicationsandMobileComputing,2003,3(2:271-290.GuptaH,DasSR,GuQ.Connectedsensorcover:Self-Organizationofsensornetworksforefficientqueryexecution.In:GerlaM,ed.Proc.oftheACMInt’lSymp.onMobileAdHocNetworkingandComputing(MobiHOC.NewYork:ACMPress,2003.189-200.[17][18]HuangCF,TsengYC.Asurveyofsolutionstothecoverageproblemsinwirelesssensornetworks.JournalofInternetTechnology,2005,6(1:1-8.ShakkottaiS,SrikantR,ShroffN.Unreliablesensorgrids:Coverage,connectivityanddiameter.In:BauerF,ed.Proc.oftheIEEEInfocom.SanFrancisco:IEEEPress,2003.1073-1083.任彥等:無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法433[19][20][21]ChakrabartyK,LyengarSS,QiH,ChoE.Gridcoverageforsurveillanceandtargetlocationindistributedsensornetworks.IEEETrans.onComputers,2002,51(12:1448-1453.MeguerdichianS,KoushanfarF,PotkonjakM,SrivastavaMB.Coverageproblemsinwirelessad-hocsensornetwork.In:SenguptaB,ed.Proc.oftheIEEEINFOCOM.Anchorage:IEEEPress,2001.1380-1387.YeF,ZhongG,ChengJ,LuSW,ZhangLX.PEAS:Arobustenergyconservingprotocolforlong-livedsensornetworks.In:StankovicJ,ZhaoW,eds.Proc.oftheInt’lConf.onDistributedComputingSystems(ICDCS.Providence:IEEEPress,2003.28-37.[22]MeguerdichianS,SlijepcevicS,KarayanV,PotkonjakM.Localizedalgorithmsinwirelessad-h