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

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)絡中覆蓋控制理論與算法 ? 任彥+,張思東，張宏科 (北京交通大學電子信息工程學院，北京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)絡中的一個基本問題，反映了網(wǎng)絡所能提供 的 感知”服務質(zhì)量，可以使無 線傳感器網(wǎng)絡的空間資源得到優(yōu)化分配，進而更好地完成環(huán)境感知、信息獲取 和有效傳輸

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

8、N應運而生1,2.WSN中的傳感器 節(jié)點一般都具備數(shù)據(jù)處理和通信能力，并通過無線鏈路或直接或間接地將收集 到的信號轉(zhuǎn)化為數(shù)據(jù)發(fā)送到一 ? Supported by the National Natural Science Foundation of China under Grant Nos.60473001,60572037 國家自然科學基金；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 （北京交通大學優(yōu)秀博士生科技創(chuàng)新基金 Received 2005-06-17; Accepted 2005-12-01 任彥等:無線傳感器網(wǎng)絡中覆蓋控制理論與算法 423 個指令中心（sink.這種協(xié)作分布式傳感器網(wǎng)絡的一種自然組織結(jié)構(gòu)，就是在各 傳感器節(jié)點間以無線多跳方式組 成一個自組織網(wǎng)絡3,4.集成了網(wǎng)絡技術(shù)、嵌入 式技術(shù)及傳感器技術(shù)的WSN將邏輯上的信息世界與真實的物理世界融合在一起 同時深刻改變了人與自然的交互方式 WSN的覆蓋控制問題，可以看作是在傳感器網(wǎng)絡節(jié)點能量、無線網(wǎng)絡通信帶 寬、網(wǎng)絡計算處理能力等資源普遍受限情況下，通過網(wǎng)絡

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

11、.本文綜述了近年 來在這一領域所取得的研究成果.第1節(jié)分析了 WSN覆蓋控制問題面臨的挑戰(zhàn)(即性能評價標準.在第2節(jié)中對現(xiàn)有覆蓋控制理 論和協(xié)議算法進行了分類.第3節(jié)詳細介紹和討論了一些典型的覆蓋控制協(xié)議算法 第4節(jié)進行了覆蓋控制各種算法間的比較性總結(jié) ，并指出該領域亟待解決的問題. 第5節(jié)進行了總結(jié). 1無線傳感器網(wǎng)絡覆蓋控制問題面臨的挑戰(zhàn) WSN覆蓋控制策略及算法的應用,有助于網(wǎng)絡節(jié)點能量的有效控制、感知服 務質(zhì)量的提高和整體生存時 間的延長，但另一方面也會帶來網(wǎng)絡相關(guān)傳輸、管理、 存儲和計算等代價的提高.因此,WSN覆蓋控制的性能評 價標準對于分析一個覆蓋 控制策略及算法的可用性與有效性

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

13、信的開展，并 直接決定了 WSN感知、監(jiān)視、傳感、通信等各種服務質(zhì)量的達到. (3能量有效性(即延長網(wǎng)絡生存時間 由于WSN節(jié)點硬件平臺資源受限、網(wǎng)絡節(jié)點數(shù)量巨大、實際應用的環(huán)境條 件復雜且大多不允許對 失效”節(jié)點進行電池更換，因此，如何節(jié)約各節(jié)點有限的 電池能量并盡力延長整體網(wǎng)絡的生存時間已成為 WSN的重要 性能指標6.能量的 有效性將是WSN覆蓋控制所面臨的一個主要挑戰(zhàn). (4算法精確性 由于受實際部署條件差異、網(wǎng)絡資源有限和覆蓋目標特性等多方面的影響，使 得WSN覆蓋控制在很多情 況下是一個NP完全問題7,8,只能達到近似優(yōu)化覆蓋 9,勢必會造成覆蓋控制算法執(zhí)行結(jié)果產(chǎn)生誤差，甚至不能保

14、證算法的有效執(zhí)行. 如何減小誤差，提高算法的精確性成為優(yōu)化覆蓋控制算法的一項重要內(nèi)容. (5算法復雜性 不同WSN覆蓋控制協(xié)議及算法其實現(xiàn)方式不同導致算法復雜程度也有較大差 別.衡量一個WSN覆蓋控制算法是否優(yōu)化的一項重要標準就是其算法的復雜性程 度.算法的復雜性程度通常包括時間復雜度、通信復雜度以及實現(xiàn)復雜度等，需要 綜合考慮. (6網(wǎng)絡動態(tài)性 一些特殊的應用環(huán)境,如運動目標監(jiān)測覆蓋10,11 、網(wǎng)絡動態(tài)覆蓋12等,需 要網(wǎng)絡的覆蓋控制協(xié)議與算法考 424 Journal of Software軟件學報 Vol.17, No.3, March 2006 慮節(jié)點具有運動能力、網(wǎng)絡整體或傳感目標

15、運動等網(wǎng)絡動態(tài)特性因此,WSN 覆蓋控制的網(wǎng)絡動態(tài)特性也成為 一項必要的評價標準. (7網(wǎng)絡可擴展性支持 保證網(wǎng)絡的可擴展性是 WSN覆蓋控制的另一項關(guān)鍵需求.沒有網(wǎng)絡可擴展性 保證，網(wǎng)絡的性能會隨著網(wǎng)絡規(guī)模的增加而顯著降低.針對不同的應用需求，WSN 的網(wǎng)絡規(guī)模相差較大，網(wǎng)絡的可擴展性需求在 WSN中尤為明顯. (8算法實施策略 WSN覆蓋控制算法的執(zhí)行可以有分布式、集中式以及兩者的混合式3種方式. 通常來說，由于WSN自身的能量消耗、協(xié)議操作代價、網(wǎng)絡性能和精度等要求， 使得利用本地信息執(zhí)行的分布式算法更為適用在一些特殊的網(wǎng)絡操作環(huán)境下，分 布式、集中式兩種方式混合執(zhí)行則更為有效 除了上面

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

17、可以將WSN的覆蓋問題分為確定性覆蓋、隨機覆蓋兩大類.下面逐一對這兩 類覆蓋控制類型加以總結(jié). 2.1.1確定性覆蓋 如果WSN的狀態(tài)相對固定或是 WSN環(huán)境已知,就可以根據(jù)預先配置的節(jié)點 位置確定網(wǎng)絡拓撲情況或增加關(guān)鍵區(qū)域的傳感器節(jié)點密度，這種情況被稱為確定性 覆蓋問題.此時的覆蓋控制問題，就成為一種特殊的網(wǎng)絡 或路徑規(guī)劃問題.典型的 確定性覆蓋有確定性區(qū)域/點覆蓋、基于網(wǎng)格（grid的目標覆蓋和確定性網(wǎng)絡路徑/ 目標覆蓋3種類型. 確定性區(qū)域/點覆蓋是指已知節(jié)點位置的 WSN要完成目標區(qū)域或目標點的覆 蓋,文獻7,13-16研究的都是 此類問題.與確定性區(qū)域/點覆蓋相關(guān)的兩個著名計 算幾何

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

19、型會 給網(wǎng)絡帶來對稱性與周期 性特征，從而掩蓋了某些網(wǎng)絡拓撲的實際特性再加上 WSN自身拓撲變化復雜，導致采用確定性覆蓋在實際應 用中具有很大的局限性， 不能適用于戰(zhàn)場等危險或其他環(huán)境惡劣的場所因此，我們需要進一步對節(jié)點隨機 分布在傳感區(qū)域而預先沒有得到自身位置的情況進行討論，這正是WSN隨機覆蓋 所要解決的問題目前，WSN的隨機覆蓋已成為 WSN覆蓋控制的一個熱點問題， 我們可大致將這類問題具體分為隨機節(jié)點覆蓋和動態(tài)網(wǎng)絡覆蓋兩類. 隨機節(jié)點覆蓋考慮在WSN中傳感器節(jié)點隨機分布且預先不知道節(jié)點位置的條 件下，網(wǎng)絡完成對監(jiān)測區(qū)域 的覆蓋任務學者關(guān)于此類問題的研究內(nèi)容較多，主要 包括文獻8,11,

20、21-27. 與一般WSN一旦部署則網(wǎng)絡中的傳感器節(jié)點的位置就固定不變有所不同，動 態(tài)網(wǎng)絡覆蓋則是考慮一些特 任彥等：無線傳感器網(wǎng)絡中覆蓋控制理論與算法 425 殊環(huán)境中部分傳感器節(jié)點具備一定運動能力的情況12.該類網(wǎng)絡可以動態(tài)完 成相關(guān)覆蓋任務. 2.2相關(guān)應用屬性分類 作為一種源于應用而又服務于應用的現(xiàn)實、可行的網(wǎng)絡技術(shù)，無線傳感器網(wǎng)絡 在軍事以及民用都具有非常 廣闊的應用前景28,WSN覆蓋控制也是如此.如 今,WSN覆蓋控制問題不僅包括單純的覆蓋含義，更與節(jié)能通信、路徑規(guī)劃、可靠 通信和目標定位等具體應用緊密相連，并依舊屬于覆蓋控制的范疇.因此，我們還 可以從WSN相關(guān)應用屬性這一新的

21、視角對WSN覆蓋控制問題進行重新分類和研 究. 2.2.1節(jié)能覆蓋 由于WSN中傳感器節(jié)點自身體積較小、電池能量資源有限，如何保證大規(guī)模 網(wǎng)絡環(huán)境下傳感器節(jié)點能量的有效使用就成為需要關(guān)注的一項重要研究內(nèi)容，它直 接影響到整個網(wǎng)絡生存時間能否充分延長.如文獻7,8,14,15,21所述,采用輪換 活躍”和休眠”節(jié)點的節(jié)能覆蓋方案，可以有效地提高網(wǎng)絡生存時間.而輪換 活躍/休眠節(jié)點的節(jié)能覆蓋方案關(guān)鍵，就是要在保證一定網(wǎng)絡覆蓋要求的條件下， 最大化輪換節(jié)點集合數(shù)目. 222柵欄覆蓋 WSN中有一類與覆蓋控制密切相關(guān)的特殊問題 一一柵欄覆蓋,它考察了目標 穿越WSN時被檢測或是沒有被檢測的情況,反映了

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

23、露穿越” 同時考慮了 “目標暴露（target exposure的時間因素和傳感器節(jié)點對于目標的感 應強度”因素.這種覆蓋模型更為符合實際環(huán)境中，運動目標由于穿越WSN區(qū)域 的時間增加而感應強度”累加值增大的情況.文獻11,22,29,30就考察了這類問 題. 2.2.3連通性覆蓋 連通性覆蓋問題也是WSN覆蓋控制相關(guān)應用屬性中的一個重要組成部分，它 同時考慮了 WSN的覆蓋能力和網(wǎng)絡連通性這兩個相互聯(lián)系的屬性.連通覆蓋問題 所要解決的是如何同時滿足網(wǎng)絡一定的傳感覆蓋和通信連通性需求，這對于一些要 求可靠通信的應用至關(guān)重要.根據(jù)具體的連通性要求，連通性覆蓋又可具體分為兩 類:活躍節(jié)點集連通覆蓋

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

25、內(nèi)容上的重疊基于本部分內(nèi) 容,圖1進行了 WSN覆蓋控制問題各種協(xié)議和算法的分類 總結(jié). 426 Journal of Software 軟件學報 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爭 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)絡覆蓋控制協(xié)議和算法分類 3典型的無線傳感器網(wǎng)絡覆蓋控 制算法與協(xié)議 基于前一部分對WSN

27、覆蓋控制問題各種協(xié)議和算法進行的分類和總結(jié)，本節(jié) 將詳細介紹一些典型的覆蓋控制協(xié)議算法研究成果，并深入分析各種協(xié)議算法的優(yōu) 缺點 3.1基于網(wǎng)格的覆蓋定位傳感器配置算法9 基于網(wǎng)格的覆蓋定位傳感器配置算法是基于網(wǎng)格的目標覆蓋類型（確定性覆蓋 中的一種，同時也屬于目標 定位覆蓋的內(nèi)容 丄in等人在文獻 9中將此優(yōu)化覆蓋定位問題轉(zhuǎn)化為最小化距離錯誤問題，并加以改進，提出了 一種在有限代價條件下最小化最大錯誤距離的組合優(yōu)化配置方法 考慮網(wǎng)絡傳感器節(jié)點以及目標點都采用網(wǎng)格形式配置，傳 感器節(jié)點采用0/1覆蓋模型,并使用能量矢量來表示格點的覆 蓋.如圖2所示，網(wǎng)絡中的各格點都可至少被一個傳感器節(jié)點所 覆

28、蓋（即該點能量矢量中至少一位為1,此時區(qū)域達到了完全覆 蓋例如,格點位置8的能量矢量為（0,0,1,1,0,0在網(wǎng)絡資源受限 而無法達到格點完全識別時，就需要考慮如何提高定位精度的 問題.而錯誤距離是衡量位置精度的一個最直接的標準，錯誤距離越小，則覆 蓋識別結(jié)果越優(yōu)化 我們設計了一種模擬退火算法來最小化距離錯誤初始時刻假設每個格點都配 置有傳感器若配置代價上限制沒有達到 就循環(huán)執(zhí)行以下過程：首先試圖刪除一個 傳感器節(jié)點，之后進行配置代價評價如果評價不通過就將該節(jié)點移動到另外一個 隨機選擇的位置，之后再進行配置代價評價循環(huán)得到優(yōu)化值后同時保存新的節(jié)點 配置情況.最后，改進算法停止執(zhí)行的準則.在達

29、到模擬退火算法的冷卻溫度t f時, 優(yōu)化覆蓋識別的網(wǎng)絡配置方案也同時達到. 優(yōu)點： (1算法結(jié)果表明：與采用隨機配置達到完全覆蓋的方案相比，該算法更為有效， 具有魯棒性并易于擴展； (2適用于不規(guī)則的傳感器網(wǎng)絡區(qū)域. 缺點： (1網(wǎng)格化的網(wǎng)絡建模方式會掩蓋網(wǎng)絡的實際拓撲特征；(2網(wǎng)絡中均為同質(zhì)節(jié) 點，不適用于網(wǎng)絡中存在節(jié)點配置代價和覆蓋能力有差異的情況 point Fig.2 An example of complete covered field 圖2區(qū)域完全覆蓋示意圖 任彥等:無線傳感器網(wǎng)絡中覆蓋控制理論與算法427 3.2輪換活躍/休眠節(jié)點的Node Self-Scheduling覆蓋協(xié)

30、議15 采用輪換 活躍”和 休眠”節(jié)點的Node Self-Scheduling15覆蓋控制協(xié)議可 以有效延長網(wǎng)絡生存時間，該協(xié)議同時屬于確定性區(qū)域/點覆蓋和節(jié)能覆蓋類型. 協(xié)議采用節(jié)點輪換周期工作機制,每個周期由一個self-scheduling階段和一個 worki ng階段組成.在self-scheduli ng階段：各節(jié)點首先向傳感半徑內(nèi)鄰居節(jié)點廣播 通告消息，其中包括節(jié)點ID和位置(若傳感半徑不同則包括發(fā)送節(jié)點傳感半徑.節(jié) 點檢查自身傳感任務是否可由鄰居節(jié)點完成 ，可替代的節(jié)點返回一條狀態(tài)通告 消 息，之后進入 休眠狀態(tài)”需要繼續(xù)工作的節(jié)點執(zhí)行傳感任務.在判斷節(jié)點是否可 以休眠時，如

31、果相鄰節(jié)點同時 檢查到自身的傳感任務可由對方完成并同時進入 休眠狀態(tài)”就會出現(xiàn)如圖3 所示的盲點 (a (b Fig.3 The “ bli nd poi nt ” in WSN 圖3網(wǎng)絡中出現(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)絡中出現(xiàn)盲點”如圖3(b所 示為了避免這種情況的發(fā)生,文獻15中,節(jié)點在self-scheduling階段檢查之前執(zhí) 行一個退避 機制：每個節(jié)點在一個隨機產(chǎn)生的T d時間之后再開始檢查工作.此外, 退避

32、時間還可以根據(jù)周圍節(jié)點密度而計算，這樣就可以有效地控制網(wǎng)絡活躍”節(jié) 點的密度.為了進一步避免 盲點”的出現(xiàn),每個節(jié)點在進入 休眠狀態(tài)”之前還 將等待T w時間來監(jiān)聽鄰居節(jié)點的狀態(tài)更新.該協(xié)議是作為LEACH分簇協(xié)議31 的一個擴展來實現(xiàn)的,有關(guān)仿真結(jié)果證明:WSN的平均網(wǎng)絡生存時間較LEACH分 簇協(xié)議延長了 1.7倍. 優(yōu)點： (1不會出現(xiàn)覆蓋盲點”因而可以保持網(wǎng)絡的充分覆蓋; (2該算法可以有效控制網(wǎng)絡節(jié)點的冗余，同時保持一定的傳感可靠性； (3節(jié)點輪換機制周期工作有效地延長了網(wǎng)絡生存時間； (4仿真實驗表明：節(jié)點輪換機制對位置錯誤、包丟失以及節(jié)點失效具有魯棒 性,依然可以保持網(wǎng)絡的充分覆

33、蓋. 缺點： (1需要預先確定節(jié)點位置并要求整個網(wǎng)絡同時具有時間同步支持，給網(wǎng)絡帶來 了附加實現(xiàn)代價； (2該機制無法使 WSN區(qū)域上的邊界節(jié)點休眠”這就影響了整個網(wǎng)絡的生存 時間延長效果； (3節(jié)點輪換機制只能適用于傳感器節(jié)點覆蓋區(qū)域為圓周(或圓球，不適用于不 規(guī)則節(jié)點感應模型； (4需要綜合優(yōu)化考慮活躍節(jié)點數(shù)量和網(wǎng)絡覆蓋效果. 3.3最壞與最佳情況覆蓋10, 20 最壞與最佳情況覆蓋算法同時屬于確定性網(wǎng)絡路徑/目標覆蓋和柵欄覆蓋類型 算法考慮如何對穿越網(wǎng)絡的目標或其所在路徑上各點進行感應與追蹤，體現(xiàn)了一種 網(wǎng)絡的覆蓋性質(zhì). 428 Journal of Software 軟件學報 Vol.

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

35、角形的各頂點為網(wǎng)絡的傳感器 節(jié)點，并滿足子三角 形外接圓中不含其他節(jié)點，如圖4所示. 由于Voronoi圖中的線段具有到最近的傳感器節(jié)點距離 最大的性質(zhì),因此最大突破路徑一定是由 Voronoi圖中的線段組 成.最大突破路徑查找過程如下：（1基于各節(jié)點的位置產(chǎn)生網(wǎng)絡 Voro noi圖； （2給每一條邊賦予一個權(quán)重來代表到最近傳感器節(jié)點的距離； (3在最小和最大的權(quán)重之間執(zhí)行二進制查找算法：每一步 操作之前給出一個參考權(quán)重標準，然后進行寬度優(yōu)先查找 (breadth-first-search檢查是否存在一條從 S到D的路徑,滿足路 徑上線段的權(quán)重都比參考權(quán)重標準要大.如果路徑存在，則增加參考權(quán)

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

37、覆蓋控制算法,適用于網(wǎng)絡路徑規(guī)劃、目標觀測等許 多應用場所. 缺點： (1算法是集中式的計算方式，需要預先知道各節(jié)點的位置信息； (2算法沒有考慮實際中障礙、環(huán)境和噪聲等可能造成的影響； (3網(wǎng)絡中均為同質(zhì)節(jié)點，不適用于網(wǎng)絡中存在節(jié)點覆蓋能力有差異時算法的執(zhí) 行情況. 3.4暴露穿越11 暴露穿越覆蓋同時屬于隨機節(jié)點覆蓋和柵欄覆蓋的類型.如前所述，目標暴露 (target exposure覆蓋模型同時考慮時間因素和節(jié)點對于目標的感應強度”因素, 更為符合實際環(huán)境中，運動目標由于穿越網(wǎng)絡時間增加 而“感應強度”累加值增大 的情況.節(jié)點s的傳感模型定義為 K p s d p s S ,(,(入 其

38、中p為目標點，正常數(shù)入和K均為網(wǎng)絡經(jīng)驗參數(shù).最小暴露路徑代表了 WSN最壞的覆蓋情況,而一個運動目標 沿著路徑p (t在時間間隔t 1, t 2內(nèi)經(jīng)過 WSN監(jiān)視區(qū)域的暴露路徑在文獻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運動時被相應傳感器 (有最近距離傳感器和全部傳感器兩種S Fig.4 Examples of the Voronoi diagram and the Dela unay tria ngulati on 圖4 Voronoi圖和Delaunay

39、三角形示意圖 任彥等：無線傳感器網(wǎng)絡中覆蓋控制理論與算法429 感應的效果.我們提出了一種數(shù)值計算的近似方法來找到連續(xù)的最小暴露路徑 首先，將傳感器網(wǎng)絡區(qū)域進行網(wǎng) 格劃分，并假設暴露路徑只能由網(wǎng)格的邊與對角線 組成；之后，為每條線段賦予一定的暴露路徑權(quán)重；最后，執(zhí)行Djikstra算法得到近 似的最小暴露路徑. 優(yōu)點： (1暴露覆蓋模型更為符合目標由于穿越WSN區(qū)域的時間增加而被檢測概率增 大的實際情況； (2分布式的算法執(zhí)行方式，不需要預先知道整個網(wǎng)絡的節(jié)點配置情況； (3根據(jù)需要可以選擇不同的感應強度模型和網(wǎng)格劃分，從而得到精度不同的暴 露路徑 缺點： (1暴露精度與算法運行時間是一對矛盾

40、，需要平衡考慮； (2算法沒有考慮實際中障礙、環(huán)境以及傳感器節(jié)點本身運動等可能造成的影 響 3.5圓周覆蓋24, 26 Hua ng在文獻24中將隨機節(jié)點覆蓋類型的圓周覆蓋歸納為決策問題 ：目標區(qū) 域中配置一組傳感器節(jié)點，看看該區(qū)域能否滿足k覆蓋,即目標區(qū)域中每個點都至 少被k個節(jié)點覆蓋.我們考慮每個傳感節(jié)點覆蓋區(qū)域的圓周 重疊情況，進而根據(jù)鄰 居節(jié)點信息來確定是否一個給定傳感器的圓周被完全覆蓋,如圖5所示17. 2n 0 n (a (b s perimeter Fig.5 Coverage of the sen sor S 圖5傳感器節(jié)點S圓周的覆蓋情況 該算法可以用分布式方式實現(xiàn)：傳感器S

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

42、法，在不增加計算復雜性的前提下使用 分布式方式解決了三維圓球體覆蓋的問題 優(yōu)點： (1算法考慮了傳感器具有不同覆蓋傳感能力以及不規(guī)則傳感范圍的情況，具有 較好的適用性； (2分布式的算法執(zhí)行方式，減小了整個網(wǎng)絡的通信與計算負載； (3算法可以適用于二維以及三維的網(wǎng)絡環(huán)境. 缺點： (1該算法只考察了區(qū)域內(nèi)各點的覆蓋情況，并未考慮各點如何被網(wǎng)絡傳感器節(jié) 點所覆蓋； 430 Journal of Software 軟件學報 Vol.17, No.3, March 2006 (2缺少相應優(yōu)化網(wǎng)絡節(jié)點配置及改善網(wǎng)絡覆蓋進一步的協(xié)議和算法. 3.6 連通傳感器覆蓋(connected sensor co

43、ver 16 Gupta在文獻16中設計的算法通過選擇連通的傳感器節(jié)點路徑來得到最大化 的網(wǎng)絡覆蓋效果，該算法同時屬于連通性覆蓋中的連通路徑覆蓋以及確定性區(qū)域/ 點覆蓋類型.當指令中心向 WSN發(fā)送一個感應區(qū)域查詢 消息時，連通傳感器覆蓋 的目標是選擇最小的連通傳感器節(jié)點集合并充分覆蓋WSN區(qū)域.文獻16分別設 計了集中與分布式兩種貪婪算法假設已選擇的傳感器節(jié)點集為 M,剩余與M有 相交傳感區(qū)域的傳感器節(jié)點稱為候選節(jié)點集中式算法初始節(jié)點隨機選擇構(gòu)成M 之后，在所有從初始節(jié)點集合出發(fā)到候選節(jié)點的路徑中選擇一條可以覆蓋更多未覆 蓋子區(qū)域的路徑.將該路徑經(jīng)過的節(jié)點加入 M,算法繼續(xù)執(zhí)行直到網(wǎng)絡查詢區(qū)

44、域可 以完全被更新后的M所覆蓋.圖6表示了該貪婪算法執(zhí)行的方式在圖6(a中,貪 婪算法會選擇路徑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é) 點開始執(zhí)行,在一定范圍內(nèi) 廣播候選路徑查找消息(CPS;收到CPS消息的節(jié)點判斷 自身是否為候選節(jié)點，如果是，則單播方式返回發(fā)起者一個候選路徑響應消息 (CPR; 發(fā)起者選擇

45、可以最大化增加覆蓋區(qū)域的候選路徑；更新各參數(shù)，算法繼續(xù)執(zhí)行 直到網(wǎng)絡查詢區(qū)域可完全被更新后的M所覆蓋. 優(yōu)點： (1本算法的節(jié)點傳感區(qū)域模型可以是任意凸形區(qū)域，更加符合實際環(huán)境； (2可以靈活地選擇使用集中式或分布式方式實現(xiàn)； (3在保證網(wǎng)絡覆蓋任務的同時，考慮了網(wǎng)絡的連通性，算法周期執(zhí)行降低了網(wǎng) 絡通信代價，并可以延長網(wǎng) 絡的生存時間 缺點： (1雖然同時考慮了連通性與網(wǎng)絡的覆蓋性，但不能保證查詢返回結(jié)果的精度 (2沒有考慮實際無線信道中出現(xiàn)的通信干擾和消息丟失，是一種單純考慮消息 傳遞的理想情況. 4無線傳感器網(wǎng)絡覆蓋控制算法比較與亟待解決的問題 4.1覆蓋控制算法比較 為了對已有算法進行

46、相互間的比較性總結(jié)，本節(jié)對照本文第1節(jié)給出的WSN 覆蓋控制所面臨的挑戰(zhàn)進行了各種算法的優(yōu)缺點總結(jié)和比較，見表1. 任彥等：無線傳感器網(wǎng)絡中覆蓋控制理論與算法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,我們可以從整體上 對無線傳感器網(wǎng)絡中的覆蓋控制問題的各種算法有一個比較清晰的認識此外,對 照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 與負

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

54、究課題; (3提供移動性的支持.目前,WSN覆蓋控制理論與算法大都假定傳感節(jié)點或者 網(wǎng)絡是靜態(tài)的，但在戰(zhàn)場等應用中可能需要節(jié)點或網(wǎng)絡具有移動性12,因此，新 的覆蓋控制理論與算法需要提供對移動性的支持； (4符合WSN與In ternet交互的相應 WSN覆蓋控制方案.由于WSN將邏輯上 的信息世界與真實的物理世界融合在一起，因此會在一些實際應用中大量出現(xiàn) WSN與In ternet之間數(shù)據(jù)與信息的交互，這就需要未來研 究相應的WSN覆蓋控制 (5開發(fā)和設計更多結(jié)合 WSN覆蓋控制的應用.覆蓋控制問題涉及到 WSN通 信、感應、計算和存儲等許多方面，將會在戰(zhàn)場偵查、陣地防御和情報獲取等軍 事環(huán)

55、境以及林場/牧場監(jiān)視、災難救護、環(huán)境監(jiān)測和醫(yī)療 觀察等很多民用項目中有 廣泛應用因此，如何利用WSN覆蓋控制理論與各種算法，開發(fā)和設計更多結(jié)合 WSN覆蓋控制的應用,將會給人類生活帶來進一步的改善 432 Journal of Software軟件學報 Vol.17, No.3, March 2006 5 總 結(jié)無線傳感器 網(wǎng)絡將邏輯上的信息世界與真實的物理世界融合在一起，極大地提高了人們認識和 改造世界 的能力.而網(wǎng)絡覆蓋控制作為 WSN實施過程中的一個基本問題，反映了網(wǎng) 絡所能提供的 感知”服務質(zhì)量.本文立足于WSN的覆蓋控制問題，對近年來提出 的各種覆蓋控制問題的新思想和代表性研究成果進

56、行歸納并加以介紹，隨后結(jié)合 WSN覆蓋控制評價標準進行了比較性總結(jié)，進而深入分析了目前 WSN覆蓋控制亟 待解決的問 題,并展望了其未來可能的發(fā)展方向致謝在此，我們向曾經(jīng)對本文提出 寶貴建議的審稿專家以及曾參與本文內(nèi)容討論的所有同學、老師表示衷心 的感謝. 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