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

1、ISSN 1000-9825, CODEN RUXUEW E-mail: josiscas.ac.c n Journal of Software, Vol.17, No.3, March 2006, pp.422-433 .c n DOI: 10.1360/jos170422 Tel/Fax: +86-10-62562563 ? 2006 by Journal of Software. All rights reserved. 無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法 ? 任彥+,張思東，張宏科 (北京交通大學(xué)電子信息工程學(xué)院，北京100044 Theories a

2、nd Algorithms of Coverage Con trol for Wireless Sen sor Networks REN Yan+, ZHANG Si-D ong, ZHANG Hon g-Ke (School of Electronics and Information Engineering, Beijing Jiaotong University, Beijing 100044, Chi na + Corresponding author: Phn: +86-10-51685677, E-mail: , .cin Ren Y, Zhan

3、g SD, Zhang HK. Theories and algorithms of coverage con trol for wireless sen sor n etworks. Journal of Software, 2006,17(3:422-433. http:/ 9825/17/422.htm Abstract : One of the most fun dame ntal problems in wireless sen sor n etworks is the coverage con trol problem, which reflects how well a regi

4、 on is apperceived. The coverage con trol theories and algorithms can result in not only n etwork resources optimial allocati on but also efficie nt sensing and collecti ng of the en vir onmen tal in formati on, and com muni cat ing with n eighbori ng no des by wireless sen sor n etworks. In this pa

5、per, the coverage con trol problem is captured. Some rece nt no vel theories and algorithms for wireless sen sor n etworks coverage con trol problems are reviewed, and the tax onomy is described. More specifically, several typical algorithms and protocols are discussed in detail. In the end, adva nt

6、ages and disadva ntages of the algorithms are summarized. The ope n research issues in this field are also poin ted out. Key words: wireless sen sor n etworks; coverage con trol; en ergy efficie ncy; algorithm 摘要：覆蓋控制作為無線傳感器網(wǎng)絡(luò)中的一個(gè)基本問題，反映了網(wǎng)絡(luò)所能提供 的 感知”服務(wù)質(zhì)量，可以使無 線傳感器網(wǎng)絡(luò)的空間資源得到優(yōu)化分配，進(jìn)而更好地完成環(huán)境感知、信息獲取 和有效傳輸

7、的任務(wù).立足于無線傳 感器網(wǎng)絡(luò)的覆蓋控制問題，分類總結(jié)了近年來提出的各種覆蓋控制問題的思想 和有代表性的研究成果，著重討 論了一些典型的無線傳感器網(wǎng)絡(luò)覆蓋控制算法與協(xié)議最后進(jìn)行了各種算法的 比較性總結(jié)，深入分析了目前無 線傳感器網(wǎng)絡(luò)覆蓋控制亟待解決的問題，并展望了其未來的發(fā)展方向 關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；覆蓋控制；能量有效；算法 中圖法分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A 近年來,隨著微機(jī)電系統(tǒng)（micro-electro-mechanism system簡(jiǎn)稱MEMS、無線 通信、信息網(wǎng)絡(luò)與集成電路 等技術(shù)的迅速發(fā)展,新興的無線傳感器網(wǎng)絡(luò)（wireless sensor networks簡(jiǎn)稱 WS

8、N應(yīng)運(yùn)而生1,2.WSN中的傳感器 節(jié)點(diǎn)一般都具備數(shù)據(jù)處理和通信能力，并通過無線鏈路或直接或間接地將收集 到的信號(hào)轉(zhuǎn)化為數(shù)據(jù)發(fā)送到一 ? Supported by the National Natural Science Foundation of China under Grant Nos.60473001,60572037 國(guó)家自然科學(xué)基金；the Inno vati on Foun dati on of Science and Tech no logy for Excelle nt Doctorial Can didates of Beiji ng Jiaot ong Uni versi

9、ty un der Grant No.48013 （北京交通大學(xué)優(yōu)秀博士生科技創(chuàng)新基金 Received 2005-06-17; Accepted 2005-12-01 任彥等:無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法 423 個(gè)指令中心（sink.這種協(xié)作分布式傳感器網(wǎng)絡(luò)的一種自然組織結(jié)構(gòu)，就是在各 傳感器節(jié)點(diǎn)間以無線多跳方式組 成一個(gè)自組織網(wǎng)絡(luò)3,4.集成了網(wǎng)絡(luò)技術(shù)、嵌入 式技術(shù)及傳感器技術(shù)的WSN將邏輯上的信息世界與真實(shí)的物理世界融合在一起 同時(shí)深刻改變了人與自然的交互方式 WSN的覆蓋控制問題，可以看作是在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量、無線網(wǎng)絡(luò)通信帶 寬、網(wǎng)絡(luò)計(jì)算處理能力等資源普遍受限情況下，通過網(wǎng)絡(luò)

10、傳感器節(jié)點(diǎn)放置以及路由 選擇等手段，最終使WSN的各種資源得到優(yōu)化分配，進(jìn)而使感知、監(jiān)視、傳感、 通信等各種服務(wù)質(zhì)量得到改善這一點(diǎn)與傳統(tǒng)ad hoc網(wǎng)絡(luò)有很大的不同.如何根據(jù) 不同的應(yīng)用環(huán)境需要,對(duì)WSN進(jìn)行不同級(jí)別的覆蓋控制就成了 WSN中一個(gè)基本 但亟待解決的問題.給定一個(gè)傳 感器網(wǎng)絡(luò)，覆蓋控制也可以一般性地總結(jié)為通過各 個(gè)傳感器節(jié)點(diǎn)協(xié)作而達(dá)到對(duì)監(jiān)視區(qū)域的不同管理或感應(yīng)效果5.與此同時(shí) WSN 中還有一些與覆蓋控制密切相關(guān)的應(yīng)用屬性，它們依舊屬于覆蓋控制問題的范疇并 極大地豐富了 WSN覆蓋控制的 內(nèi)涵”. 近年來，已有一些學(xué)者開展了 WSN優(yōu)化覆蓋控制方面的研究工作，并取得了 一定的進(jìn)展

11、.本文綜述了近年 來在這一領(lǐng)域所取得的研究成果.第1節(jié)分析了 WSN覆蓋控制問題面臨的挑戰(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)域亟待解決的問題. 第5節(jié)進(jìn)行了總結(jié). 1無線傳感器網(wǎng)絡(luò)覆蓋控制問題面臨的挑戰(zhàn) WSN覆蓋控制策略及算法的應(yīng)用,有助于網(wǎng)絡(luò)節(jié)點(diǎn)能量的有效控制、感知服 務(wù)質(zhì)量的提高和整體生存時(shí) 間的延長(zhǎng)，但另一方面也會(huì)帶來網(wǎng)絡(luò)相關(guān)傳輸、管理、 存儲(chǔ)和計(jì)算等代價(jià)的提高.因此,WSN覆蓋控制的性能評(píng) 價(jià)標(biāo)準(zhǔn)對(duì)于分析一個(gè)覆蓋 控制策略及算法的可用性與有效性

12、至關(guān)重要.通過從不同的角度總結(jié)出覆蓋控制算 法所面臨的挑戰(zhàn)，有助于清楚地比較出各種算法之間的優(yōu)缺點(diǎn).這里歸納出以下幾 占： 八、 (1覆蓋能力 以環(huán)境感知、目標(biāo)監(jiān)測(cè)、信息獲取和有效傳輸為主要目標(biāo)的WSN需要關(guān)心對(duì) 傳感區(qū)域或監(jiān)測(cè)目標(biāo)的覆 蓋能力，無線傳感器網(wǎng)絡(luò)覆蓋控制問題也正是由此而來 個(gè)WSN覆蓋控制算法是否 因此，網(wǎng)絡(luò)對(duì)目標(biāo)區(qū)域或是目標(biāo)點(diǎn)的覆蓋程度是衡量 優(yōu)劣的首要標(biāo)準(zhǔn) (2網(wǎng)絡(luò)的連通性 由于WSN是一種無基礎(chǔ)設(shè)施的網(wǎng)絡(luò)，大量節(jié)點(diǎn)采用自組織方式協(xié)同完成指令 中心的查詢、搜集等指令，網(wǎng)絡(luò)節(jié)點(diǎn)之間需要通過無線多跳方式或直接或間接地相 互通信來協(xié)同工作網(wǎng)絡(luò)的連通性將有效保證自身無 線多跳自組織通

13、信的開展，并 直接決定了 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完全問題7,8,只能達(dá)到近似優(yōu)化覆蓋 9,勢(shì)必會(huì)造成覆蓋控制算法執(zhí)行結(jié)果產(chǎn)生誤差，甚至不能保

14、證算法的有效執(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é)議與算法考 424 Journal of Software軟件學(xué)報(bào) Vol.17, No.3, March 2006 慮節(jié)點(diǎn)具有運(yùn)動(dòng)能力、網(wǎng)絡(luò)整體或傳感目標(biāo)

15、運(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)鍵需求.沒有網(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種方式. 通常來說，由于WSN自身的能量消耗、協(xié)議操作代價(jià)、網(wǎng)絡(luò)性能和精度等要求， 使得利用本地信息執(zhí)行的分布式算法更為適用在一些特殊的網(wǎng)絡(luò)操作環(huán)境下，分 布式、集中式兩種方式混合執(zhí)行則更為有效 除了上面

16、列出的一些所面臨的挑戰(zhàn)之外，WSN覆蓋控制協(xié)議算法還會(huì)存在是否 需要知道網(wǎng)絡(luò)節(jié)點(diǎn)位置、是否需要專門的覆蓋控制消息等差別同樣，它們也是我 們?cè)O(shè)計(jì)、分析具體協(xié)議和算法時(shí)要考察的內(nèi)容 2無線傳感器網(wǎng)絡(luò)覆蓋控制問題分類 WSN從誕生之初就與應(yīng)用密切相關(guān),WSN覆蓋控制更是如此.如今的WSN覆 蓋控制問題不僅包括單純的 覆蓋含義，更是與節(jié)能通信、路徑規(guī)劃、可靠通信和目 標(biāo)定位等具體應(yīng)用緊密相連為了對(duì)WSN覆蓋控制問題 有更加全面的認(rèn)識(shí)，本文 分別從配置方式和相關(guān)應(yīng)用屬性兩個(gè)角度進(jìn)行 WSN覆蓋控制問題分類. 2.1配置方式分類 按照無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)不同配置方式 （即節(jié)點(diǎn)是否需要知道自身位置信息， 我們

17、可以將WSN的覆蓋問題分為確定性覆蓋、隨機(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)密度，這種情況被稱為確定性 覆蓋問題.此時(shí)的覆蓋控制問題，就成為一種特殊的網(wǎng)絡(luò) 或路徑規(guī)劃問題.典型的 確定性覆蓋有確定性區(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,13-16研究的都是 此類問題.與確定性區(qū)域/點(diǎn)覆蓋相關(guān)的兩個(gè)著名計(jì) 算幾何

18、問題為藝術(shù)館走廊監(jiān)控問題 （art gallery problem17以及圓周覆蓋問題（circle coveri ng problem17. 基于網(wǎng)格的目標(biāo)覆蓋是指當(dāng)?shù)乩憝h(huán)境情況預(yù)先確定時(shí)，使用二維（也可以為三 維的網(wǎng)格進(jìn)行網(wǎng)絡(luò)的建模，并選擇在合適的格點(diǎn)配置傳感器節(jié)點(diǎn)來完成區(qū)域/目標(biāo) 的覆蓋.文獻(xiàn)9,18,19中對(duì)這一問題進(jìn)行了有益的研究確定性網(wǎng)絡(luò)路徑/目標(biāo)覆蓋 同樣也是考慮WSN傳感器節(jié)點(diǎn)位置已知情況，但這類問題特別考慮了如何對(duì)穿越 網(wǎng)絡(luò)的目標(biāo)或其經(jīng)過的路徑上各點(diǎn)進(jìn)行感應(yīng)與追蹤相關(guān)研究包括文獻(xiàn)10,20. 2.1.2隨機(jī)覆蓋 在許多實(shí)際自然環(huán)境中，由于網(wǎng)絡(luò)情況不能預(yù)先確定且多數(shù)確定性覆蓋模

19、型會(huì) 給網(wǎng)絡(luò)帶來對(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ù)先沒有得到自身位置的情況進(jìn)行討論，這正是WSN隨機(jī)覆蓋 所要解決的問題目前，WSN的隨機(jī)覆蓋已成為 WSN覆蓋控制的一個(gè)熱點(diǎ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)于此類問題的研究?jī)?nèi)容較多，主要 包括文獻(xiàn)8,11,

20、21-27. 與一般WSN一旦部署則網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)的位置就固定不變有所不同，動(dòng) 態(tài)網(wǎng)絡(luò)覆蓋則是考慮一些特 任彥等：無線傳感器網(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ǎng)絡(luò) 在軍事以及民用都具有非常 廣闊的應(yīng)用前景28,WSN覆蓋控制也是如此.如 今,WSN覆蓋控制問題不僅包括單純的覆蓋含義，更與節(jié)能通信、路徑規(guī)劃、可靠 通信和目標(biāo)定位等具體應(yīng)用緊密相連，并依舊屬于覆蓋控制的范疇.因此，我們還 可以從WSN相關(guān)應(yīng)用屬性這一新的

21、視角對(duì)WSN覆蓋控制問題進(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ù)目. 222柵欄覆蓋 WSN中有一類與覆蓋控制密切相關(guān)的特殊問題 一一柵欄覆蓋,它考察了目標(biāo) 穿越WSN時(shí)被檢測(cè)或是沒有被檢測(cè)的情況,反映了

22、給定WSN所能提供的傳感、 監(jiān)視能力這類覆蓋控制問題的目標(biāo)是找出連接出發(fā)位置 （記為S和離開位置（記為 D的一條或多條路徑，使得這樣的路徑能夠在不同模型定義下提供對(duì)目標(biāo)的不同傳 感/監(jiān)視質(zhì)量.根據(jù)目標(biāo)穿越 WSN時(shí)所采用模型的不同,柵欄覆蓋又可以具體分為 最壞與最佳情況覆蓋”和暴露穿越”兩種類型. 最壞與最佳情況覆蓋”問題中,對(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)的概率最大情況此問題相關(guān)研究包 括文獻(xiàn)10,12,20,23. 與單純考慮離傳感器節(jié)點(diǎn)距離的最壞與最佳情況覆蓋”不同，暴

23、露穿越” 同時(shí)考慮了 “目標(biāo)暴露（target exposure的時(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就考察了這類問 題. 2.2.3連通性覆蓋 連通性覆蓋問題也是WSN覆蓋控制相關(guān)應(yīng)用屬性中的一個(gè)重要組成部分，它 同時(shí)考慮了 WSN的覆蓋能力和網(wǎng)絡(luò)連通性這兩個(gè)相互聯(lián)系的屬性.連通覆蓋問題 所要解決的是如何同時(shí)滿足網(wǎng)絡(luò)一定的傳感覆蓋和通信連通性需求，這對(duì)于一些要 求可靠通信的應(yīng)用至關(guān)重要.根據(jù)具體的連通性要求，連通性覆蓋又可具體分為兩 類:活躍節(jié)點(diǎn)集連通覆蓋

24、13,25,是針對(duì)采用活躍節(jié)點(diǎn)集輪換機(jī)制的情況，考慮如何 保證指定傳感區(qū)域的覆蓋和網(wǎng) 絡(luò)的連通性；而連通路徑覆蓋16,18,27,則是考慮通 過選擇可能的連通傳感器節(jié)點(diǎn)路徑來得到最大化的網(wǎng)絡(luò)覆蓋效果. 2.2.4目標(biāo)定位覆蓋 在某些特殊環(huán)境下 WSN覆蓋配置 伴隨而來”的是WSN的目標(biāo)定位問題, 我們可稱此時(shí)的 WSN覆蓋為目標(biāo)定位覆蓋.例如在前面提到的網(wǎng)格條件下,網(wǎng)絡(luò) 的目標(biāo)定位問題即為及時(shí)查詢出目標(biāo)所在網(wǎng)格被周圍哪些傳感器格點(diǎn)所覆蓋.文獻(xiàn) 9,19就專門進(jìn)行了此方面的研究 由以上WSN覆蓋控制分類我們不難看出：配置方式和相關(guān)應(yīng)用屬性兩種分類 方法既有各自特殊的分類角 度，又同時(shí)會(huì)有具體研究

25、內(nèi)容上的重疊基于本部分內(nèi) 容,圖1進(jìn)行了 WSN覆蓋控制問題各種協(xié)議和算法的分類 總結(jié). 426 Journal of Software 軟件學(xué)報(bào) Vol.17, No.3, March 2006 Piatocds and algoiitlnis of covet st gt ccchci f de 口曾N Appiicatioii p opsity Detenniartic Stochastic covei age cov?tage H Ca/igurt liiftiTtMi Ai get location Connectivity cove】(t爭(zhēng) tTVTt 1 *f* Deteiini

26、mstic nj亡呦out ccjveiH 乎 Deenniistic petMftigftt CDVseiags GtiilBased tai get coverage Stochastic node cover 嚕 Dynaiiiic covtiage Worst and best ca!* caveragt Exposire c milage Collected acttre oode set coverngp Ccmected 1 path Ener 朗 efficiency ) 圖1無線傳感器網(wǎng)絡(luò)覆蓋控制協(xié)議和算法分類 3典型的無線傳感器網(wǎng)絡(luò)覆蓋控 制算法與協(xié)議 基于前一部分對(duì)WSN

27、覆蓋控制問題各種協(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)容 丄in等人在文獻(xiàn) 9中將此優(yōu)化覆蓋定位問題轉(zhuǎn)化為最小化距離錯(cuò)誤問題，并加以改進(jìn)，提出了 一種在有限代價(jià)條件下最小化最大錯(cuò)誤距離的組合優(yōu)化配置方法 考慮網(wǎng)絡(luò)傳感器節(jié)點(diǎn)以及目標(biāo)點(diǎn)都采用網(wǎng)格形式配置，傳 感器節(jié)點(diǎn)采用0/1覆蓋模型,并使用能量矢量來表示格點(diǎn)的覆 蓋.如圖2所示，網(wǎng)絡(luò)中的各格點(diǎn)都可至少被一個(gè)傳感器節(jié)點(diǎn)所 覆

28、蓋（即該點(diǎn)能量矢量中至少一位為1,此時(shí)區(qū)域達(dá)到了完全覆 蓋例如,格點(diǎn)位置8的能量矢量為（0,0,1,1,0,0在網(wǎng)絡(luò)資源受限 而無法達(dá)到格點(diǎn)完全識(shí)別時(shí)，就需要考慮如何提高定位精度的 問題.而錯(cuò)誤距離是衡量位置精度的一個(gè)最直接的標(biāo)準(zhǔn)，錯(cuò)誤距離越小，則覆 蓋識(shí)別結(jié)果越優(yōu)化 我們?cè)O(shè)計(jì)了一種模擬退火算法來最小化距離錯(cuò)誤初始時(shí)刻假設(shè)每個(gè)格點(diǎn)都配 置有傳感器若配置代價(jià)上限制沒有達(dá)到 就循環(huán)執(zhí)行以下過程：首先試圖刪除一個(gè) 傳感器節(jié)點(diǎn)，之后進(jìn)行配置代價(jià)評(píng)價(jià)如果評(píng)價(jià)不通過就將該節(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á)

29、到模擬退火算法的冷卻溫度t f時(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à)和覆蓋能力有差異的情況 point Fig.2 An example of complete covered field 圖2區(qū)域完全覆蓋示意圖 任彥等:無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法427 3.2輪換活躍/休眠節(jié)點(diǎn)的Node Self-Scheduling覆蓋協(xié)

30、議15 采用輪換 活躍”和 休眠”節(jié)點(diǎn)的Node Self-Scheduling15覆蓋控制協(xié)議可 以有效延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間，該協(xié)議同時(shí)屬于確定性區(qū)域/點(diǎn)覆蓋和節(jié)能覆蓋類型. 協(xié)議采用節(jié)點(diǎn)輪換周期工作機(jī)制,每個(gè)周期由一個(gè)self-scheduling階段和一個(gè) worki ng階段組成.在self-scheduli ng階段：各節(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í)，如

31、果相鄰節(jié)點(diǎn)同時(shí) 檢查到自身的傳感任務(wù)可由對(duì)方完成并同時(shí)進(jìn)入 休眠狀態(tài)”就會(huì)出現(xiàn)如圖3 所示的盲點(diǎn) (a (b Fig.3 The “ bli nd poi nt ” in WSN 圖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)生的T d時(shí)間之后再開始檢查工作.此外, 退避

32、時(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)”之前還 將等待T w時(shí)間來監(jiān)聽鄰居節(jié)點(diǎn)的狀態(tài)更新.該協(xié)議是作為L(zhǎng)EACH分簇協(xié)議31 的一個(gè)擴(kuò)展來實(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ò)的充分覆

33、蓋. 缺點(diǎn)： (1需要預(yù)先確定節(jié)點(diǎn)位置并要求整個(gè)網(wǎng)絡(luò)同時(shí)具有時(shí)間同步支持，給網(wǎng)絡(luò)帶來 了附加實(shí)現(xiàn)代價(jià)； (2該機(jī)制無法使 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ì). 428 Journal of Software 軟件學(xué)報(bào) Vol.

34、17, No.3, March 2006 Meguerdichian等人先后在文獻(xiàn)20和文獻(xiàn)10中定義了 最大突破路徑 （maximal breach path和”最大支撐 路徑（maximal support path 分別使得路徑上的 點(diǎn)到周圍最近傳感器的最小距離最大化以及最大距離最小化.顯然，這兩種路徑分 別代表了 WSN最壞（不被檢測(cè)概率最小和最佳（被發(fā)現(xiàn)的概率最大的覆蓋情況. 文中分別采用計(jì)算幾何中的V oronoi圖與Delaunay三角形來完成最大突破路徑和 最大支撐路徑的構(gòu)造和查找.其中，Voronoi圖是由所有Delaunay三角形邊上的垂 直平分線形成；而Delaunay三

35、角形的各頂點(diǎn)為網(wǎng)絡(luò)的傳感器 節(jié)點(diǎn)，并滿足子三角 形外接圓中不含其他節(jié)點(diǎn)，如圖4所示. 由于Voronoi圖中的線段具有到最近的傳感器節(jié)點(diǎn)距離 最大的性質(zhì),因此最大突破路徑一定是由 Voronoi圖中的線段組 成.最大突破路徑查找過程如下：（1基于各節(jié)點(diǎn)的位置產(chǎn)生網(wǎng)絡(luò) Voro noi圖； （2給每一條邊賦予一個(gè)權(quán)重來代表到最近傳感器節(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)

36、重標(biāo)準(zhǔn) 來縮小路徑可選擇的線段數(shù)目，否則就降低參考權(quán)重標(biāo)準(zhǔn) (4最后得到一條從S到D的路徑，也就是最大突破路徑，圖4中用P max_breach 表示. 類似地，由于Delau nay三角形是由所有到最近傳感器節(jié)點(diǎn)距離最短的線段組 成，因此最大支撐路徑必然由Delaunay三角形的線段構(gòu)成給每一條邊賦予一個(gè)權(quán) 重來代表路徑上所有到周圍最近傳感器節(jié)點(diǎn)的最大距離，查找算法同上圖4中用 P max_support表示了算法執(zhí)行后得到的一條最大支撐路徑. 優(yōu)點(diǎn)： (1在最佳與最差兩種度量條件下，分別得到了臨界的網(wǎng)絡(luò)路徑規(guī)劃結(jié)果，可以 指導(dǎo)網(wǎng)絡(luò)節(jié)點(diǎn)的配置來改進(jìn)整體網(wǎng)絡(luò)的覆蓋; (2作為一種特殊的 WSN

37、覆蓋控制算法,適用于網(wǎng)絡(luò)路徑規(guī)劃、目標(biāo)觀測(cè)等許 多應(yīng)用場(chǎng)所. 缺點(diǎn)： (1算法是集中式的計(jì)算方式，需要預(yù)先知道各節(jié)點(diǎn)的位置信息； (2算法沒有考慮實(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)暴露 (target exposure覆蓋模型同時(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的傳感模型定義為 K p s d p s S ,(,(入 其

38、中p為目標(biāo)點(diǎn)，正常數(shù)入和K均為網(wǎng)絡(luò)經(jīng)驗(yàn)參數(shù).最小暴露路徑代表了 WSN最壞的覆蓋情況,而一個(gè)運(yùn)動(dòng)目標(biāo) 沿著路徑p (t在時(shí)間間隔t 1, t 2內(nèi)經(jīng)過 WSN監(jiān)視區(qū)域的暴露路徑在文獻(xiàn)11中被定義為 t t t p t p F I t t t p E t t d d (d (,(,(1 221 /芙中I (F , p (t代表了在傳感區(qū)域F中沿著路徑p (t運(yùn)動(dòng)時(shí)被相應(yīng)傳感器 (有最近距離傳感器和全部傳感器兩種S Fig.4 Examples of the Voronoi diagram and the Dela unay tria ngulati on 圖4 Voronoi圖和Delaunay

39、三角形示意圖 任彥等：無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法429 感應(yīng)的效果.我們提出了一種數(shù)值計(jì)算的近似方法來找到連續(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ì)矛盾

40、，需要平衡考慮； (2算法沒有考慮實(shí)際中障礙、環(huán)境以及傳感器節(jié)點(diǎn)本身運(yùn)動(dòng)等可能造成的影 響 3.5圓周覆蓋24, 26 Hua ng在文獻(xiàn)24中將隨機(jī)節(jié)點(diǎ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)信息來確定是否一個(gè)給定傳感器的圓周被完全覆蓋,如圖5所示17. 2n 0 n (a (b s perimeter Fig.5 Coverage of the sen sor S 圖5傳感器節(jié)點(diǎn)S圓周的覆蓋情況 該算法可以用分布式方式實(shí)現(xiàn)：傳感器S

41、首先確定圓周被鄰居節(jié)點(diǎn)覆蓋的情況， 如圖5(a所示,3段圓周0,a ,b , c ,d ,分別被n勺3個(gè)鄰居節(jié)點(diǎn)所覆蓋.再將結(jié) 果按照升序順序記錄在0,2 n區(qū)間,如圖5(b所示,這樣就可以得到節(jié)點(diǎn)S的圓周 覆蓋情況：0,b 段為1,b , a 段為2,a , d 段為1,d , c 段為2,c ,段為1.文獻(xiàn)24 給出證明：傳感器節(jié)點(diǎn)圓周被充分覆蓋等價(jià)于整個(gè)區(qū)域被充分覆蓋”每個(gè)傳感器 節(jié)點(diǎn)收集本地信息來進(jìn)行本節(jié)點(diǎn)圓周覆蓋判斷，并且該算法還可以進(jìn)一步擴(kuò)展到不 規(guī)則的傳感區(qū)域中使用. 在文獻(xiàn)24中的二維圓周覆蓋問題基礎(chǔ)上,Huang進(jìn)一步在文獻(xiàn)26中使用將 三維圓球覆蓋影射為二維圓周覆蓋的類似方

42、法，在不增加計(jì)算復(fù)雜性的前提下使用 分布式方式解決了三維圓球體覆蓋的問題 優(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)所覆蓋； 430 Journal of Software 軟件學(xué)報(bào) Vol.17, No.3, March 2006 (2缺少相應(yīng)優(yōu)化網(wǎng)絡(luò)節(jié)點(diǎn)配置及改善網(wǎng)絡(luò)覆蓋進(jìn)一步的協(xié)議和算法. 3.6 連通傳感器覆蓋(connected sensor co

43、ver 16 Gupta在文獻(xiàn)16中設(shè)計(jì)的算法通過選擇連通的傳感器節(jié)點(diǎn)路徑來得到最大化 的網(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)過的節(jié)點(diǎn)加入 M,算法繼續(xù)執(zhí)行直到網(wǎng)絡(luò)查詢區(qū)

44、域可 以完全被更新后的M所覆蓋.圖6表示了該貪婪算法執(zhí)行的方式在圖6(a中,貪 婪算法會(huì)選擇路徑P 2得到圖6(b,這是由于在所有備選路徑中選擇 C 3和C 4組成 的路徑P2可以覆蓋更多未覆蓋子區(qū)域. (a (b Fig.6 Greedy algorithm of the conn ected sen sor cover 圖6連通傳感器覆蓋的貪婪算法 連通傳感器覆蓋的分布式貪婪算法執(zhí)行過程是：首先從M中最新加入的候選節(jié) 點(diǎn)開始執(zhí)行,在一定范圍內(nèi) 廣播候選路徑查找消息(CPS;收到CPS消息的節(jié)點(diǎn)判斷 自身是否為候選節(jié)點(diǎn)，如果是，則單播方式返回發(fā)起者一個(gè)候選路徑響應(yīng)消息 (CPR; 發(fā)起者選擇

45、可以最大化增加覆蓋區(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沒有考慮實(shí)際無線信道中出現(xiàn)的通信干擾和消息丟失，是一種單純考慮消息 傳遞的理想情況. 4無線傳感器網(wǎng)絡(luò)覆蓋控制算法比較與亟待解決的問題 4.1覆蓋控制算法比較 為了對(duì)已有算法進(jìn)行

46、相互間的比較性總結(jié)，本節(jié)對(duì)照本文第1節(jié)給出的WSN 覆蓋控制所面臨的挑戰(zhàn)進(jìn)行了各種算法的優(yōu)缺點(diǎn)總結(jié)和比較，見表1. 任彥等：無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法431 Table 1Comparis on of coverage con trol algorithms in wireless sen sor n etworks 表1 WSN覆蓋控制算法比較 Article Coverage ability Network conn ectivity Accuracy Complexity Network mobility En ergy efficie ncy Network scalabili

47、ty Deployme nt model Locatio n- Based Negotiati on-Based 18 Moderate Stro ng High Moderate Weak Low Stro ng Cen tralized Yes No 19 Moderate Moderate High Moderate Weak Moderate Moderate Ce ntralized Yes No 9 Stro ng Moderate High High Weak Moderate Stro ng Cen tralized Yes No 14 Moderate Weak Low Hi

48、gh Weak High Moderate Distributed Yes Yes 7 Moderate Strong Moderate Moderate Weak High ModerateCe ntralized Yes No 15 Stro ng Moderate Moderate ModerateModerate High Stro ng Distributed Yes Yes 21 Weak Moderate Low Low Stro ng High Stro ng Distributed No Yes 8 Stro ng Stro ng Low High WeakHigh Weak

49、 Cen tralized Yes No 12 Stro ng Moderate Moderate High Stro ng Moderate Stro ng Hybrid No No 20 Stro ng Stro ng Moderate High Weak Low Stro ng Cen tralized Yes Yes 10 Stro ng Stro ng Moderate High Weak Low Stro ng Cen tralized Yes Yes 11 Moderate Weak High Moderate Stro ng Moderate Weak Cen tralized

50、 Yes No 22 Stro ng Moderate High ModerateStro ng Moderate Moderate Distributed Yes Yes 29 Stro ng Stro ng High Low Moderate Moderate Moderate Distributed Yes No 30 Stro ng Stro ng High ModerateModerate High Stro ng Hybrid Yes Yes 23 Stro ng Stro ng High High Weak High Moderate Distributed Yes Yes 24

51、 Stro ng Stro ng High ModerateWeak Low Stro ng Hybrid Yes Yes 26 Stro ng Stro ng High ModerateWeak Low Stro ng Distributed Yes Yes 25 Stro ng Stro ng High High Weak High Stro ng Distributed Yes Yes 16 Stro ng Stro ng Moderate Low Stro ng Moderate Stro ng Cen tralized No Yes 27 Stro ng Stro ng High M

52、oderateWeak Moderate Stro ng Distributed No Yes通過表 1,我們可以從整體上 對(duì)無線傳感器網(wǎng)絡(luò)中的覆蓋控制問題的各種算法有一個(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)和考慮其中一些亟待解決的問題 4.2亟待解決的問題 雖然WSN覆蓋控制研究已經(jīng)取得了一定的成果,但是仍有很多問題需要解決 集中體現(xiàn)在以下幾點(diǎn)：(1感知模型種類的完善.從本文綜述的各種 WSN覆蓋成果 不難看出：目前使用的傳感器節(jié)點(diǎn)感知模型包 括圓形區(qū)域感知7,9,10,15,16,19,20 與負(fù)

53、指數(shù)距離感知11,22,29,30兩種感知模型，不能適用于實(shí)際 WSN環(huán)境的感知 模型多樣化需要.此外，目前節(jié)點(diǎn)感知模型大多沒有考慮實(shí)際無線信道中出現(xiàn)的通 信干擾，是一種理想模型16.因此，還需要進(jìn)一步考慮更加完善的感知模型種類； (2三維空間的覆蓋控制.從文本第3節(jié)的討論不難看出：盡管目前許多方案都 很好地解決了二維平面的 覆蓋控制問題10,11,20,23,但由于三維空間的覆蓋控制 在計(jì)算幾何與隨機(jī)圖論等數(shù)學(xué)理論上仍是一個(gè) NP難問題17,因此，現(xiàn)有的三維 空間覆蓋控制只能得到近似優(yōu)化的結(jié)果 26,27.如何針對(duì)具體的 WSN三維空間應(yīng) 用需要設(shè)計(jì)出有效的算法與協(xié)議，將會(huì)是一個(gè)很有意義的研

54、究課題; (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與In ternet交互的相應(yīng) WSN覆蓋控制方案.由于WSN將邏輯上 的信息世界與真實(shí)的物理世界融合在一起，因此會(huì)在一些實(shí)際應(yīng)用中大量出現(xiàn) WSN與In ternet之間數(shù)據(jù)與信息的交互，這就需要未來研 究相應(yīng)的WSN覆蓋控制 (5開發(fā)和設(shè)計(jì)更多結(jié)合 WSN覆蓋控制的應(yīng)用.覆蓋控制問題涉及到 WSN通 信、感應(yīng)、計(jì)算和存儲(chǔ)等許多方面，將會(huì)在戰(zhàn)場(chǎng)偵查、陣地防御和情報(bào)獲取等軍 事環(huán)

55、境以及林場(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ì)給人類生活帶來進(jìn)一步的改善 432 Journal of Software軟件學(xué)報(bào) Vol.17, No.3, March 2006 5 總 結(jié)無線傳感器 網(wǎng)絡(luò)將邏輯上的信息世界與真實(shí)的物理世界融合在一起，極大地提高了人們認(rèn)識(shí)和 改造世界 的能力.而網(wǎng)絡(luò)覆蓋控制作為 WSN實(shí)施過程中的一個(gè)基本問題，反映了網(wǎng) 絡(luò)所能提供的 感知”服務(wù)質(zhì)量.本文立足于WSN的覆蓋控制問題，對(duì)近年來提出 的各種覆蓋控制問題的新思想和代表性研究成果進(jìn)

56、行歸納并加以介紹，隨后結(jié)合 WSN覆蓋控制評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行了比較性總結(jié)，進(jìn)而深入分析了目前 WSN覆蓋控制亟 待解決的問 題,并展望了其未來可能的發(fā)展方向致謝在此，我們向曾經(jīng)對(duì)本文提出 寶貴建議的審稿專家以及曾參與本文內(nèi)容討論的所有同學(xué)、老師表示衷心 的感謝. References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Akyildiz IF, Su W, San karasubrama niam Y, Cayirci E. Wireless sen sor n etworks: A survey. Computer Networks, 2002,38(4

57、: 393-422. Ren FY, Hua ng HN, Lin C. Wireless sen sor networks. Journal of Software, 2003,14(2:1148-1157 (in Chinese with English abstract. http:/ Pottie GJ, Kaiser WJ. Wireless in tegrated network sen sors. Commu ni catio ns of the ACM, 2000,43(5:51-58. Sohrabi K, Gao J Ailawadhi V, Pottie GJ. Prot

58、ocols for self-orga ni zati on of a wireless sen sor n etwork. IEEE Perso nal Commu ni cati ons, 2000,7(5:16-27. Cardei M, Wu J. Coverage in wireless sen sor n etworks. In: Ilyas M, Magboub I, eds. Han dbook of Sen sor Networks, chapter 19. CRC Press, 2004. Li JZ, Li JB, Shi SF. Con cepts, issues an

59、d adva nee of sen sor n etworks and data man ageme nt of sen sor networks. Journal of Software, 2003,14(10:1717-1727 (in Chi nese with En glish abstract. .c n/1000-9825/14/1717.htm Slijepcevic S, Potkonjak M. Power efficie nt orga ni zati on of wireless sen sor n etworks. In: Glisic

60、 S, ed. Proc. of the IEEE Int l Conf. on Communications (ICC. Helsinki: IEEE Press, 2001.472-476. Cardei M, Du DZ. Improvi ng wireless sen sor network lifetime through power aware organi zatio n. Wireless Networks, 2005,11(3: 333-340. Lin FYS, Chiu PL. A n ear-optimal sen sor placeme nt algorithm to