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

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

cnveragfTaiget

location廠Tt1—DeteiministicaieanointcowDeteniiinsticStochasticIEnet即effitiencyBEiriieiConnectfi/ity

cnveragfTaiget

location廠Tt1—Deteiministicaieanointcow磨IDetemiiiifjtiiipath/taiget1ctr/ieidgeGiicl-Bassdtai^tcoverageStacliPisticimdecavem國(guó)Dytiaimccaveiagfco\retfige—廠尸TWorstandExposureCumectedCmilected1bestcas&-Bas&dftctiv?nodepathcoveragectK^iagesetcmieiEigecovei?咿Tt■匚9卷人料23/，乎"CDVfitai圖1無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制協(xié)議和算法分類3典型的無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制算法與協(xié)議基于前一部分對(duì)WSN覆蓋控制問(wèn)題各種協(xié)議和算法進(jìn)行的分類和總結(jié),本節(jié)將詳細(xì)介紹一些典型的覆蓋控制協(xié)議算法研究成果,并深入分析各種協(xié)議算法的優(yōu)缺點(diǎn).3.1基于網(wǎng)格的覆蓋定位傳感器配置算法[9]基于網(wǎng)格的覆蓋定位傳感器配置算法是基于網(wǎng)格的目標(biāo)覆蓋類型（確定性覆蓋中的一種，同時(shí)也屬于目標(biāo)定位覆蓋的內(nèi)容.Lin等人在文獻(xiàn)[9]中將此優(yōu)化覆蓋定位問(wèn)題轉(zhuǎn)化為最小化距離錯(cuò)誤問(wèn)題,并加以改進(jìn),提出了一種在有限代價(jià)條件下最小化最大錯(cuò)誤距離的組合優(yōu)化配置方法.考慮網(wǎng)絡(luò)傳感器節(jié)點(diǎn)以及目標(biāo)點(diǎn)都采用網(wǎng)格形式配置，傳感器節(jié)點(diǎn)采用0/1覆蓋模型,并使用能量矢量來(lái)表示格點(diǎn)的覆蓋.如圖2所示，網(wǎng)絡(luò)中的各格點(diǎn)都可至少被一個(gè)傳感器節(jié)點(diǎn)所覆蓋（即該點(diǎn)能量矢量中至少一位為1,此時(shí)區(qū)域達(dá)到了完全覆蓋.例如,格點(diǎn)位置8的能量矢量為（0,0,1,1,0,0.在網(wǎng)絡(luò)資源受限而無(wú)法達(dá)到格點(diǎn)完全識(shí)別時(shí),就需要考慮如何提高定位精度的問(wèn)題.而錯(cuò)誤距離是衡量位置精度的一個(gè)最直接的標(biāo)準(zhǔn),錯(cuò)誤距離越小，則覆蓋識(shí)別結(jié)果越優(yōu)化.我們?cè)O(shè)計(jì)了一種模擬退火算法來(lái)最小化距離錯(cuò)誤.初始時(shí)刻假設(shè)每個(gè)格點(diǎn)都配置有傳感器.若配置代價(jià)上限制沒(méi)有達(dá)到就循環(huán)執(zhí)行以下過(guò)程:首先試圖刪除一個(gè)傳感器節(jié)點(diǎn)，之后進(jìn)行配置代價(jià)評(píng)價(jià).如果評(píng)價(jià)不通過(guò)就將該節(jié)點(diǎn)移動(dòng)到另外一個(gè)隨機(jī)選擇的位置,之后再進(jìn)行配置代價(jià)評(píng)價(jià).循環(huán)得到優(yōu)化值后同時(shí)保存新的節(jié)點(diǎn)配置情況.最后，改進(jìn)算法停止執(zhí)行的準(zhǔn)則.在達(dá)到模擬退火算法的冷卻溫度tf時(shí),優(yōu)化覆蓋識(shí)別的網(wǎng)絡(luò)配置方案也同時(shí)達(dá)到.優(yōu)點(diǎn):(1算法結(jié)果表明：與采用隨機(jī)配置達(dá)到完全覆蓋的方案相比,該算法更為有效，具有魯棒性并易于擴(kuò)展；(2適用于不規(guī)則的傳感器網(wǎng)絡(luò)區(qū)域.缺點(diǎn)：(1網(wǎng)格化的網(wǎng)絡(luò)建模方式會(huì)掩蓋網(wǎng)絡(luò)的實(shí)際拓?fù)涮卣?(2網(wǎng)絡(luò)中均為同質(zhì)節(jié)點(diǎn),不適用于網(wǎng)絡(luò)中存在節(jié)點(diǎn)配置代價(jià)和覆蓋能力有差異的情況.pointFig.2Anexampleofcompletecoveredfield圖2區(qū)域完全覆蓋示意圖任彥等:無(wú)線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法4273.2輪換活躍/休眠節(jié)點(diǎn)的NodeSelf-Scheduling覆蓋協(xié)議[15]采用輪換“活躍”和“休眠”節(jié)點(diǎn)的NodeSelf-Scheduling[15]覆蓋控制協(xié)議可以有效延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間，該協(xié)議同時(shí)屬于確定性區(qū)域/點(diǎn)覆蓋和節(jié)能覆蓋類型.協(xié)議采用節(jié)點(diǎn)輪換周期工作機(jī)制，每個(gè)周期由一個(gè)self-scheduling階段和一個(gè)working階段組成.在self-scheduling階段:各節(jié)點(diǎn)首先向傳感半徑內(nèi)鄰居節(jié)點(diǎn)廣播通告消息,其中包括節(jié)點(diǎn)ID和位置(若傳感半徑不同則包括發(fā)送節(jié)點(diǎn)傳感半徑.節(jié)點(diǎn)檢查自身傳感任務(wù)是否可由鄰居節(jié)點(diǎn)完成，可替代的節(jié)點(diǎn)返回一條狀態(tài)通告消息,之后進(jìn)入“休眠狀態(tài)”,需要繼續(xù)工作的節(jié)點(diǎn)執(zhí)行傳感任務(wù).在判斷節(jié)點(diǎn)是否可以休眠時(shí),如果相鄰節(jié)點(diǎn)同時(shí)檢查到自身的傳感任務(wù)可由對(duì)方完成并同時(shí)進(jìn)入“休眠狀態(tài)”,就會(huì)出現(xiàn)如圖3所示的“盲點(diǎn)(a(bFig.3The“blindpoint”inWSN圖3網(wǎng)絡(luò)中出現(xiàn)的“盲點(diǎn)”在圖3(a中,節(jié)點(diǎn)e和f的整個(gè)傳感區(qū)域都可以被相鄰的鄰居節(jié)點(diǎn)代替覆蓋.e和f節(jié)點(diǎn)滿足進(jìn)入“休眠狀態(tài)”條件之后,將關(guān)閉自身節(jié)點(diǎn)的傳感單元進(jìn)入“休眠狀態(tài)”,但這時(shí)就出現(xiàn)了不能被WSN檢測(cè)的區(qū)域即網(wǎng)絡(luò)中出現(xiàn)“盲點(diǎn)”,如圖3(b所示.為了避免這種情況的發(fā)生,文獻(xiàn)［15］中,節(jié)點(diǎn)在self-scheduling階段檢查之前執(zhí)行一個(gè)退避機(jī)制:每個(gè)節(jié)點(diǎn)在一個(gè)隨機(jī)產(chǎn)生的Td時(shí)間之后再開始檢查工作.此外,退避時(shí)間還可以根據(jù)周圍節(jié)點(diǎn)密度而計(jì)算，這樣就可以有效地控制網(wǎng)絡(luò)“活躍”節(jié)點(diǎn)的密度.為了進(jìn)一步避免“盲點(diǎn)”的出現(xiàn)，每個(gè)節(jié)點(diǎn)在進(jìn)入“休眠狀態(tài)”之前還將等待Tw時(shí)間來(lái)監(jiān)聽鄰居節(jié)點(diǎn)的狀態(tài)更新.該協(xié)議是作為L(zhǎng)EACH分簇協(xié)議［31］的一個(gè)擴(kuò)展來(lái)實(shí)現(xiàn)的，有關(guān)仿真結(jié)果證明:WSN的平均網(wǎng)絡(luò)生存時(shí)間較LEACH分簇協(xié)議延長(zhǎng)了1.7倍.優(yōu)點(diǎn)：(1不會(huì)出現(xiàn)覆蓋“盲點(diǎn)”,因而可以保持網(wǎng)絡(luò)的充分覆蓋；(2該算法可以有效控制網(wǎng)絡(luò)節(jié)點(diǎn)的冗余，同時(shí)保持一定的傳感可靠性；(3節(jié)點(diǎn)輪換機(jī)制周期工作有效地延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間；(4仿真實(shí)驗(yàn)表明：節(jié)點(diǎn)輪換機(jī)制對(duì)位置錯(cuò)誤、包丟失以及節(jié)點(diǎn)失效具有魯棒性，依然可以保持網(wǎng)絡(luò)的充分覆蓋.缺點(diǎn)：(1需要預(yù)先確定節(jié)點(diǎn)位置并要求整個(gè)網(wǎng)絡(luò)同時(shí)具有時(shí)間同步支持，給網(wǎng)絡(luò)帶來(lái)了附加實(shí)現(xiàn)代價(jià)；(2該機(jī)制無(wú)法使WSN區(qū)域上的邊界節(jié)點(diǎn)“休眠”,這就影響了整個(gè)網(wǎng)絡(luò)的生存時(shí)間延長(zhǎng)效果；(3節(jié)點(diǎn)輪換機(jī)制只能適用于傳感器節(jié)點(diǎn)覆蓋區(qū)域?yàn)閳A周(或圓球，不適用于不規(guī)則節(jié)點(diǎn)感應(yīng)模型；(4需要綜合優(yōu)化考慮活躍節(jié)點(diǎn)數(shù)量和網(wǎng)絡(luò)覆蓋效果.3.3最壞與最佳情況覆蓋［10,20］最壞與最佳情況覆蓋算法同時(shí)屬于確定性網(wǎng)絡(luò)路徑/目標(biāo)覆蓋和柵欄覆蓋類型.算法考慮如何對(duì)穿越網(wǎng)絡(luò)的目標(biāo)或其所在路徑上各點(diǎn)進(jìn)行感應(yīng)與追蹤，體現(xiàn)了一種網(wǎng)絡(luò)的覆蓋性質(zhì).428JournalofSoftware軟件學(xué)報(bào)Vol.17,No.3,March2006Meguerdichian等人先后在文獻(xiàn)［20］和文獻(xiàn)［10］中定義了“最大突破路徑（maximalbreachpath”和“最大支撐路徑（maximalsupportpath”,分別使得路徑上的點(diǎn)到周圍最近傳感器的最小距離最大化以及最大距離最小化.顯然，這兩種路徑分別代表了WSN最壞（不被檢測(cè)概率最小和最佳（被發(fā)現(xiàn)的概率最大的覆蓋情況.文中分別采用計(jì)算幾何中的Voronoi圖與Delaunay三角形來(lái)完成最大突破路徑和最大支撐路徑的構(gòu)造和查找.其中,Voronoi圖是由所有Delaunay三角形邊上的垂直平分線形成；而Delaunay三角形的各頂點(diǎn)為網(wǎng)絡(luò)的傳感器節(jié)點(diǎn)，并滿足子三角形外接圓中不含其他節(jié)點(diǎn),如圖4所示.由于Voronoi圖中的線段具有到最近的傳感器節(jié)點(diǎn)距離最大的性質(zhì)，因此最大突破路徑一定是由Voronoi圖中的線段組成.最大突破路徑查找過(guò)程如下：（1基于各節(jié)點(diǎn)的位置產(chǎn)生網(wǎng)絡(luò)Voronoi圖;（2給每一條邊賦予一個(gè)權(quán)重來(lái)代表到最近傳感器節(jié)點(diǎn)的距離；(3在最小和最大的權(quán)重之間執(zhí)行二進(jìn)制查找算法:每一步操作之前給出一個(gè)參考權(quán)重標(biāo)準(zhǔn)，然后進(jìn)行寬度優(yōu)先查找(breadth-first-search，檢查是否存在一條從S到D的路徑，滿足路徑上線段的權(quán)重都比參考權(quán)重標(biāo)準(zhǔn)要大.如果路徑存在，則增加參考權(quán)重標(biāo)準(zhǔn)來(lái)縮小路徑可選擇的線段數(shù)目，否則就降低參考權(quán)重標(biāo)準(zhǔn).(4最后得到一條從S到D的路徑,也就是最大突破路徑，圖4中用Pmax_breach表示.類似地，由于Delaunay三角形是由所有到最近傳感器節(jié)點(diǎn)距離最短的線段組成，因此最大支撐路徑必然由Delaunay三角形的線段構(gòu)成.給每一條邊賦予一個(gè)權(quán)重來(lái)代表路徑上所有到周圍最近傳感器節(jié)點(diǎn)的最大距離，查找算法同上.圖4中用Pmax_support表示了算法執(zhí)行后得到的一條最大支撐路徑.優(yōu)點(diǎn):(1在最佳與最差兩種度量條件下，分別得到了臨界的網(wǎng)絡(luò)路徑規(guī)劃結(jié)果，可以指導(dǎo)網(wǎng)絡(luò)節(jié)點(diǎn)的配置來(lái)改進(jìn)整體網(wǎng)絡(luò)的覆蓋；(2作為一種特殊的WSN覆蓋控制算法，適用于網(wǎng)絡(luò)路徑規(guī)劃、目標(biāo)觀測(cè)等許多應(yīng)用場(chǎng)所.缺點(diǎn)：(1算法是集中式的計(jì)算方式，需要預(yù)先知道各節(jié)點(diǎn)的位置信息；(2算法沒(méi)有考慮實(shí)際中障礙、環(huán)境和噪聲等可能造成的影響；(3網(wǎng)絡(luò)中均為同質(zhì)節(jié)點(diǎn)，不適用于網(wǎng)絡(luò)中存在節(jié)點(diǎn)覆蓋能力有差異時(shí)算法的執(zhí)行情況.3.4暴露穿越［11］暴露穿越覆蓋同時(shí)屬于隨機(jī)節(jié)點(diǎn)覆蓋和柵欄覆蓋的類型.如前所述,“目標(biāo)暴露(targetexposure”覆蓋模型同時(shí)考慮時(shí)間因素和節(jié)點(diǎn)對(duì)于目標(biāo)的“感應(yīng)強(qiáng)度”因素，更為符合實(shí)際環(huán)境中，運(yùn)動(dòng)目標(biāo)由于穿越網(wǎng)絡(luò)時(shí)間增加而“感應(yīng)強(qiáng)度”累加值增大的情況.節(jié)點(diǎn)s的傳感模型定義為KpsdpsS］,(［,(X其中p為目標(biāo)點(diǎn)，正常數(shù)X和K均為網(wǎng)絡(luò)經(jīng)驗(yàn)參數(shù).最小暴露路徑代表了WSN最壞的覆蓋情況,而一個(gè)運(yùn)動(dòng)目標(biāo)沿著路徑p(t在時(shí)間間隔［t1,t2］內(nèi)經(jīng)過(guò)WSN監(jiān)視區(qū)域的暴露路徑在文獻(xiàn)［11］中被定義為tttptpFItttpEttdd(d(,(,,((1221卜.其中I(F,p(t代表了在傳感區(qū)域F中沿著路徑p(t運(yùn)動(dòng)時(shí)被相應(yīng)傳感器(有最近距離傳感器和全部傳感器兩種SFig.4ExamplesoftheVoronoidiagramandtheDelaunaytriangulation圖4Voronoi圖和Delaunay三角形示意圖任彥等:無(wú)線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法429感應(yīng)的效果.我們提出了一種數(shù)值計(jì)算的近似方法來(lái)找到連續(xù)的最小暴露路徑:首先,將傳感器網(wǎng)絡(luò)區(qū)域進(jìn)行網(wǎng)格劃分,并假設(shè)暴露路徑只能由網(wǎng)格的邊與對(duì)角線組成;之后，為每條線段賦予一定的暴露路徑權(quán)重；最后，執(zhí)行Djikstra算法得到近似的最小暴露路徑.優(yōu)點(diǎn)：(1暴露覆蓋模型更為符合目標(biāo)由于穿越WSN區(qū)域的時(shí)間增加而被檢測(cè)概率增大的實(shí)際情況；(2分布式的算法執(zhí)行方式,不需要預(yù)先知道整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)配置情況；(3根據(jù)需要可以選擇不同的感應(yīng)強(qiáng)度模型和網(wǎng)格劃分，從而得到精度不同的暴露路徑.缺點(diǎn)：(1暴露精度與算法運(yùn)行時(shí)間是一對(duì)矛盾，需要平衡考慮；(2算法沒(méi)有考慮實(shí)際中障礙、環(huán)境以及傳感器節(jié)點(diǎn)本身運(yùn)動(dòng)等可能造成的影響.3.5圓周覆蓋［24,26］Huang在文獻(xiàn)［24］中將隨機(jī)節(jié)點(diǎn)覆蓋類型的圓周覆蓋歸納為決策問(wèn)題：目標(biāo)區(qū)域中配置一組傳感器節(jié)點(diǎn),看看該區(qū)域能否滿足k覆蓋，即目標(biāo)區(qū)域中每個(gè)點(diǎn)都至少被k個(gè)節(jié)點(diǎn)覆蓋.我們考慮每個(gè)傳感節(jié)點(diǎn)覆蓋區(qū)域的圓周重疊情況,進(jìn)而根據(jù)鄰居節(jié)點(diǎn)信息來(lái)確定是否一個(gè)給定傳感器的圓周被完全覆蓋,如圖5所示［17］.2n0n(a(bFig.5CoverageofthesensorS’sperimeter圖5傳感器節(jié)點(diǎn)S圓周的覆蓋情況該算法可以用分布式方式實(shí)現(xiàn):傳感器S首先確定圓周被鄰居節(jié)點(diǎn)覆蓋的情況,如圖5(a所示,3段圓周［0,a］,［b,c］,［d,n］分別被S的3個(gè)鄰居節(jié)點(diǎn)所覆蓋.再將結(jié)果按照升序順序記錄在［0,2n］區(qū)間，如圖5(b所示，這樣就可以得到節(jié)點(diǎn)S的圓周覆蓋情況:［0,b］段為1,［b,a］段為2,［a,d］段為1,［d,c］段為2,［c,n］段為1.文獻(xiàn)［24］給出證明：“傳感器節(jié)點(diǎn)圓周被充分覆蓋等價(jià)于整個(gè)區(qū)域被充分覆蓋”.每個(gè)傳感器節(jié)點(diǎn)收集本地信息來(lái)進(jìn)行本節(jié)點(diǎn)圓周覆蓋判斷，并且該算法還可以進(jìn)一步擴(kuò)展到不規(guī)則的傳感區(qū)域中使用.在文獻(xiàn)［24］中的二維圓周覆蓋問(wèn)題基礎(chǔ)上,Huang進(jìn)一步在文獻(xiàn)［26］中使用將三維圓球覆蓋影射為二維圓周覆蓋的類似方法，在不增加計(jì)算復(fù)雜性的前提下使用分布式方式解決了三維圓球體覆蓋的問(wèn)題.優(yōu)點(diǎn)：(1算法考慮了傳感器具有不同覆蓋傳感能力以及不規(guī)則傳感范圍的情況，具有較好的適用性；(2分布式的算法執(zhí)行方式,減小了整個(gè)網(wǎng)絡(luò)的通信與計(jì)算負(fù)載；(3算法可以適用于二維以及三維的網(wǎng)絡(luò)環(huán)境.缺點(diǎn)：(1該算法只考察了區(qū)域內(nèi)各點(diǎn)的覆蓋情況,并未考慮各點(diǎn)如何被網(wǎng)絡(luò)傳感器節(jié)點(diǎn)所覆蓋；430JournalofSoftware軟件學(xué)報(bào)Vol.17,No.3,March2006(2缺少相應(yīng)優(yōu)化網(wǎng)絡(luò)節(jié)點(diǎn)配置及改善網(wǎng)絡(luò)覆蓋進(jìn)一步的協(xié)議和算法.3.6連通傳感器覆蓋(connectedsensorcover［16］Gupta在文獻(xiàn)［16〕中設(shè)計(jì)的算法通過(guò)選擇連通的傳感器節(jié)點(diǎn)路徑來(lái)得到最大化的網(wǎng)絡(luò)覆蓋效果,該算法同時(shí)屬于連通性覆蓋中的連通路徑覆蓋以及確定性區(qū)域/點(diǎn)覆蓋類型.當(dāng)指令中心向WSN發(fā)送一個(gè)感應(yīng)區(qū)域查詢消息時(shí),連通傳感器覆蓋的目標(biāo)是選擇最小的連通傳感器節(jié)點(diǎn)集合并充分覆蓋WSN區(qū)域.文獻(xiàn)［16］分別設(shè)計(jì)了集中與分布式兩種貪婪算法.假設(shè)已選擇的傳感器節(jié)點(diǎn)集為M,剩余與M有相交傳感區(qū)域的傳感器節(jié)點(diǎn)稱為候選節(jié)點(diǎn).集中式算法初始節(jié)點(diǎn)隨機(jī)選擇構(gòu)成M之后,在所有從初始節(jié)點(diǎn)集合出發(fā)到候選節(jié)點(diǎn)的路徑中選擇一條可以覆蓋更多未覆蓋子區(qū)域的路徑.將該路徑經(jīng)過(guò)的節(jié)點(diǎn)加入M,算法繼續(xù)執(zhí)行直到網(wǎng)絡(luò)查詢區(qū)域可以完全被更新后的M所覆蓋.圖6表示了該貪婪算法執(zhí)行的方式.在圖6(a中，貪婪算法會(huì)選擇路徑P2得到圖6(b,這是由于在所有備選路徑中選擇C3和C4組成的路徑P2可以覆蓋更多未覆蓋子區(qū)域.(a(bFig.6Greedyalgorithmoftheconnectedsensorcover圖6連通傳感器覆蓋的貪婪算法連通傳感器覆蓋的分布式貪婪算法執(zhí)行過(guò)程是:首先從M中最新加入的候選節(jié)點(diǎn)開始執(zhí)行，在一定范圍內(nèi)廣播候選路徑查找消息(CPS;收到CPS消息的節(jié)點(diǎn)判斷自身是否為候選節(jié)點(diǎn),如果是，則單播方式返回發(fā)起者一個(gè)候選路徑響應(yīng)消息(CPR;發(fā)起者選擇可以最大化增加覆蓋區(qū)域的候選路徑；更新各參數(shù)，算法繼續(xù)執(zhí)行,直到網(wǎng)絡(luò)查詢區(qū)域可完全被更新后的M所覆蓋.優(yōu)點(diǎn)：(1本算法的節(jié)點(diǎn)傳感區(qū)域模型可以是任意凸形區(qū)域,更加符合實(shí)際環(huán)境；(2可以靈活地選擇使用集中式或分布式方式實(shí)現(xiàn)；(3在保證網(wǎng)絡(luò)覆蓋任務(wù)的同時(shí),考慮了網(wǎng)絡(luò)的連通性,算法周期執(zhí)行降低了網(wǎng)絡(luò)通信代價(jià),并可以延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間.缺點(diǎn)：(1雖然同時(shí)考慮了連通性與網(wǎng)絡(luò)的覆蓋性，但不能保證查詢返回結(jié)果的精度；(2沒(méi)有考慮實(shí)際無(wú)線信道中出現(xiàn)的通信干擾和消息丟失，是一種單純考慮消息傳遞的理想情況.4無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制算法比較與亟待解決的問(wèn)題4.1覆蓋控制算法比較為了對(duì)已有算法進(jìn)行相互間的比較性總結(jié),本節(jié)對(duì)照本文第1節(jié)給出的WSN覆蓋控制所面臨的挑戰(zhàn)進(jìn)行了各種算法的優(yōu)缺點(diǎn)總結(jié)和比較，見表1.任彥等:無(wú)線傳感器網(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通過(guò)表1,我們可以從整體上對(duì)無(wú)線傳感器網(wǎng)絡(luò)中的覆蓋控制問(wèn)題的各種算法有一個(gè)比較清晰的認(rèn)識(shí).此外，對(duì)照WSN覆蓋控制評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行的相關(guān)研究成果優(yōu)缺點(diǎn)比較,有助于我們更加全面地了解已有協(xié)議算法,并進(jìn)一步發(fā)現(xiàn)和考慮其中一些亟待解決的問(wèn)題.4.2亟待解決的問(wèn)題雖然WSN覆蓋控制研究已經(jīng)取得了一定的成果，但是仍有很多問(wèn)題需要解決,集中體現(xiàn)在以下幾點(diǎn)：(1感知模型種類的完善.從本文綜述的各種WSN覆蓋成果不難看出：目前使用的傳感器節(jié)點(diǎn)感知模型包括圓形區(qū)域感知［7,9,10,15,16,19,20］與負(fù)指數(shù)距離感知［11,22,29,30］兩種感知模型，不能適用于實(shí)際WSN環(huán)境的感知模型多樣化需要.此外，目前節(jié)點(diǎn)感知模型大多沒(méi)有考慮實(shí)際無(wú)線信道中出現(xiàn)的通信干擾，是一種理想模型［16］.因此，還需要進(jìn)一步考慮更加完善的感知模型種類；(2三維空間的覆蓋控制.從文本第3節(jié)的討論不難看出：盡管目前許多方案都很好地解決了二維平面的覆蓋控制問(wèn)題［10,11,20,23］，但由于三維空間的覆蓋控制在計(jì)算幾何與隨機(jī)圖論等數(shù)學(xué)理論上仍是一個(gè)NP難問(wèn)題［17］,因此,現(xiàn)有的三維空間覆蓋控制只能得到近似優(yōu)化的結(jié)果［26,27］.如何針對(duì)具體的WSN三維空間應(yīng)用需要設(shè)計(jì)出有效的算法與協(xié)議,將會(huì)是一個(gè)很有意義的研究課題；(3提供移動(dòng)性的支持.目前,WSN覆蓋控制理論與算法大都假定傳感節(jié)點(diǎn)或者網(wǎng)絡(luò)是靜態(tài)的，但在戰(zhàn)場(chǎng)等應(yīng)用中可能需要節(jié)點(diǎn)或網(wǎng)絡(luò)具有移動(dòng)性［12］,因此,新的覆蓋控制理論與算法需要提供對(duì)移動(dòng)性的支持；(4符合WSN與Internet交互的相應(yīng)WSN覆蓋控制方案.由于WSN將邏輯上的信息世界與真實(shí)的物理世界融合在一起，因此會(huì)在一些實(shí)際應(yīng)用中大量出現(xiàn)WSN與Internet之間數(shù)據(jù)與信息的交互,這就需要未來(lái)研究相應(yīng)的WSN覆蓋控制方案；(5開發(fā)和設(shè)計(jì)更多結(jié)合WSN覆蓋控制的應(yīng)用.覆蓋控制問(wèn)題涉及到WSN通信、感應(yīng)、計(jì)算和存儲(chǔ)等許多方面,將會(huì)在戰(zhàn)場(chǎng)偵查、陣地防御和情報(bào)獲取等軍事環(huán)境以及林場(chǎng)/牧場(chǎng)監(jiān)視、災(zāi)難救護(hù)、環(huán)境監(jiān)測(cè)和醫(yī)療觀察等很多民用項(xiàng)目中有廣泛應(yīng)用.因此，如何利用WSN覆蓋控制理論與各種算法，開發(fā)和設(shè)計(jì)更多結(jié)合WSN覆蓋控制的應(yīng)用,將會(huì)給人類生活帶來(lái)進(jìn)一步的改善.432JournalofSoftware軟件學(xué)報(bào)Vol.17,No.3,March20065總結(jié)無(wú)線傳感器網(wǎng)絡(luò)將邏輯上的信息世界與真實(shí)的物理世界融合在一起，極大地提高了人們認(rèn)識(shí)和改造世界的能力.而網(wǎng)絡(luò)覆蓋控制作為WSN實(shí)施過(guò)程中的一個(gè)基本問(wèn)題，反映了網(wǎng)絡(luò)所能提供的“感知”服務(wù)質(zhì)量.本文立足于WSN的覆蓋控制問(wèn)題,對(duì)近年來(lái)提出的各種覆蓋控制問(wèn)題的新思想和代表性研究成果進(jìn)行歸納并加以介紹，隨后結(jié)合WSN覆蓋控制評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行了比較性總結(jié),進(jìn)而深入分析了目前WSN覆蓋控制亟待解決的問(wèn)題，并展望了其未來(lái)可能的發(fā)展方向.致謝在此，我們向曾經(jīng)對(duì)本文提出寶貴建議的審稿專家以及曾參與本文內(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ú)線傳感器網(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