王廣超　王振榮　楊軍

【摘要】 覆蓋控制是無線傳感器網(wǎng)絡(luò)的一個基本問題，可以使無線傳感網(wǎng)絡(luò)的空間資源得到優(yōu)化分配，進而更好地完成環(huán)境感知、信息獲取和有效傳輸?shù)娜蝿?wù)；覆蓋控制決定了傳感器網(wǎng)絡(luò)對物理世界的監(jiān)測性能，分析了網(wǎng)絡(luò)覆蓋技術(shù)在國內(nèi)外研究的現(xiàn)狀與發(fā)展，指出了傳感器網(wǎng)絡(luò)能量受限、規(guī)模大、動態(tài)性強，給覆蓋控制的研究帶來了巨大挑戰(zhàn)?？偨Y(jié)覆蓋控制基本概念，最后提出當前亟待解決的問題，并對其未來的發(fā)展趨勢進行展望。

【關(guān)鍵詞】 無線傳感器網(wǎng)絡(luò) 覆蓋控制 服務(wù)質(zhì)量 覆蓋度

引言

近年來，隨著無線通信、傳感技術(shù)、嵌入式應(yīng)用和微電子技術(shù)的日趨成熟，孕育了一種新興的信息獲取技術(shù)——無線傳感器網(wǎng)絡(luò)[1]（Wireless Sensor Networks，WSN）。WSN是由部署在監(jiān)測區(qū)域內(nèi)大量傳感器節(jié)點相互通信形成的多跳自組織網(wǎng)絡(luò)系統(tǒng)，可以在任何時間、任何地點、任何環(huán)境條件下獲取人們所需信息，它在軍事、環(huán)境監(jiān)測、智能家居、工業(yè)控制、城市交通和現(xiàn)代農(nóng)業(yè)等方面都有重要的研究意義和使用價值。

覆蓋控制作為傳感器網(wǎng)絡(luò)的一個基本問題，是衡量傳感器網(wǎng)絡(luò)監(jiān)測性能的重要指標之一優(yōu)化網(wǎng)絡(luò)部署以提高覆蓋對于合理分配網(wǎng)絡(luò)的空間資源，保證服務(wù)質(zhì)量（QoS， quality of service），更好地完成環(huán)境感知、信息獲取以及延長網(wǎng)絡(luò)的生存時間都具有重要的意義。

近年來，已有一些文章對WSN覆蓋控制方面做過綜述，但國內(nèi)外學(xué)者對WSN優(yōu)化覆蓋控制取得新的進展。本文綜述了近年來在這一領(lǐng)域取得的研究成果。

第1節(jié)簡要回顧分析WSN的概述；在第2節(jié)中對現(xiàn)有覆蓋控制技術(shù)國內(nèi)外研究現(xiàn)狀進行了詳細分析；第3節(jié)中對覆蓋控制技術(shù)基本概念闡述；第4節(jié)分析了WSN覆蓋控制問題面臨的挑戰(zhàn)和該領(lǐng)域亟待解決的問題；第5節(jié)進行了總結(jié)和展望。

一、無線傳感網(wǎng)絡(luò)概述

無線傳感器網(wǎng)絡(luò)作為一個全新的研究領(lǐng)域，在基礎(chǔ)理論和工程技術(shù)兩個層面向科技工作者提出了大量的挑戰(zhàn)性研究課題。無線傳感器網(wǎng)絡(luò)已經(jīng)成為一個十分重要和非常熱烈的新的研究領(lǐng)域。近年來，國內(nèi)外開展了大量研究，取得了很多研究成果[2]。

無線傳感器網(wǎng)絡(luò)是指部署在監(jiān)測區(qū)域里的大量微型傳感器節(jié)點通過無線通信方式形成一個多跳的自組織網(wǎng)絡(luò)，節(jié)點之間通過協(xié)作方式對網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)被監(jiān)測對象的信息進行感知、采集和處理，并將有效數(shù)據(jù)發(fā)送到數(shù)據(jù)收集節(jié)點（sack node）或基站（ base station），最后，再傳送到用戶終端。從而實現(xiàn)物理世界、計算世界以及人類社會三元世界的連通。WSNs被認為是對21世紀產(chǎn)生巨大影響力的技術(shù)之一[3]。

二、覆蓋控制技術(shù)國內(nèi)外研究現(xiàn)狀

近年來，一些國內(nèi)外學(xué)者開展了傳感器網(wǎng)絡(luò)覆蓋控制方面的探索性研究，陸續(xù)在IEEE 系列會議（如INFOCOM，GLOBECOM，ICC，SECON 等）、ACM 傳感器網(wǎng)絡(luò)相關(guān)會議（MOBICOM，SENSYS 等）發(fā)表了一系列前沿的研究成果。根據(jù)不同的性質(zhì)覆蓋控制問題可以劃分為不同的類型（如，靜態(tài)覆蓋和動態(tài)覆蓋、確定性覆蓋和隨機性覆蓋）。

覆蓋控制技術(shù)是無線傳感器網(wǎng)絡(luò)中的關(guān)鍵技術(shù)，其本質(zhì)就是在給定節(jié)點數(shù)目的前提下如何最大化物理環(huán)境覆蓋感知區(qū)域或者如何用盡量少的節(jié)點達到預(yù)期給定的覆蓋質(zhì)量和要求。

Veltri等人在文獻[4]中提出了覆蓋控制算法NSS （Node Self-Scheduling），算法中通過輪換“活躍”和“睡眠”節(jié)點，可以有效地延長網(wǎng)絡(luò)生存時問，該算法采用周期性節(jié)點輪換的工作機制，每個周期由狀態(tài)調(diào)度階段和工作階段組成。

Zhang等人在文獻[5]設(shè)計了一種分布式的最優(yōu)地理密度控制算法OGDC （ Optimal Geographical Density Control ），討論了如何使用最少數(shù)量的節(jié)點，來保持無線傳感器網(wǎng)絡(luò)的覆蓋質(zhì)量以及維持網(wǎng)絡(luò)的連通性。算法給出了兩個判定條件：首先給出了通信半徑大于或等于2倍的覆蓋半徑RS（RC≥2RS）的條件下，只要保證完全覆蓋就可以保證網(wǎng)絡(luò)區(qū)域的連通性。其次，又給出了完全覆蓋的最少節(jié)點數(shù)量的充要條件：網(wǎng)絡(luò)中任意3個相鄰節(jié)點都要構(gòu)成一個以它們?yōu)轫旤c，邊長為行的等邊三角形。

Ye等人在文獻[6]中提出了基于探測的密度控制算法PEAS （Probing Environment and Adaptive Sleeping）。 PEAS算法通過關(guān)閉冗余節(jié)點的方法來節(jié)省能量。它的顯著優(yōu)點是節(jié)點不需要保存任何相鄰節(jié)點的信息，無須先獲知節(jié)點的地理位置信息。體眠節(jié)點醒來后只需探測周圍一定區(qū)域RP內(nèi)是否存在工作節(jié)點來決定本節(jié)點是否需要工作。

Gupta等人在文獻[7]中設(shè)計的CSCSO算法（Connected Sensor Cover Self Organization）通過選擇連通的傳感器節(jié)點路徑來得到最大化的網(wǎng)絡(luò)覆蓋效果。該算法同時屬于連通性覆蓋中的連接路徑覆蓋及確定性區(qū)域/點覆蓋類型。當管理端向無線傳感器網(wǎng)絡(luò)發(fā)送一個感應(yīng)區(qū)域查詢消息時，連通傳感器覆蓋的目標是選擇最小的連通傳感器節(jié)點集合并充分覆蓋網(wǎng)絡(luò)區(qū)域。

任秀麗等人在文獻[8]提出一個分布的、與節(jié)點位置無關(guān)的無線傳感器網(wǎng)絡(luò)覆蓋控制算法（ a Location Independent Coverage Control Algorithm for Wireless Sensor Networks， LICA）。L ICA 采用基于節(jié)點分層成簇的思想，節(jié)點與鄰居交換信息，并通過節(jié)點距離與覆蓋模型找出覆蓋節(jié)點。在保證覆蓋性能的前提下，關(guān)閉覆蓋節(jié)點的通信設(shè)備。LICA 算法不僅可以提供高質(zhì)量的覆蓋性能，而且具有良好的節(jié)能性能，特別適合低成本、資源缺乏、工作在惡劣環(huán)境中的分布式無線傳感器網(wǎng)絡(luò)。

王換招等人在文獻[9]分析了實際環(huán)境中隨機部署傳感器網(wǎng)絡(luò)的感知特性，給出了節(jié)點感知半徑服從正態(tài)分布的無須地理位置信息的節(jié)點冗余度計算模型，以及保證網(wǎng)絡(luò)覆蓋質(zhì)量所需要的最少工作節(jié)點數(shù)的計算模型。在此模型的基礎(chǔ)上，提出了高效節(jié)能的無線傳感器網(wǎng)絡(luò)覆蓋保持協(xié)議（energy efficient coverage conserving protocol，簡稱EECCP），實現(xiàn)了均衡節(jié)點能量消耗的分布式協(xié)作調(diào)度，該協(xié)議保留最少的工作節(jié)點以保證要求的覆蓋質(zhì)量，從而達到節(jié)約網(wǎng)絡(luò)能量的目的。EECCP 不僅能夠保證要求的覆蓋質(zhì)量，而且能夠減少網(wǎng)絡(luò)能量消耗，有效地延長了網(wǎng)絡(luò)的有效壽命。

趙春江等人在文獻[10]提出了一種基于Voronoi 有效覆蓋區(qū)域的空洞偵測修復(fù)策略。該策略以滿足一定網(wǎng)絡(luò)區(qū)域覆蓋質(zhì)量為前提，在空洞區(qū)域內(nèi)合理增加工作節(jié)點以提高網(wǎng)絡(luò)覆蓋率為優(yōu)化目標，采用幾何圖形向量方法對節(jié)點感知范圍和Voronoi 多邊形的位置特性進行理論分析，力求較準確地計算出空洞面積，找尋最佳空洞修復(fù)位置，部署較少的工作節(jié)點保證整個網(wǎng)絡(luò)的連通性。

該策略能有效地減少網(wǎng)絡(luò)總節(jié)點個數(shù)和感知重疊區(qū)域，控制網(wǎng)絡(luò)中冗余節(jié)點的存在，同時其收斂速度較快，能夠獲得比現(xiàn)有算法更高的目標區(qū)域空洞修復(fù)率，實現(xiàn)網(wǎng)絡(luò)覆蓋控制優(yōu)化。

三、覆蓋控制技術(shù)基本概念

覆蓋控制技術(shù)通過傳感器網(wǎng)絡(luò)節(jié)點放置以及路由選擇等手段使得部署在傳感器網(wǎng)絡(luò)中的各個節(jié)點相互協(xié)作，從而達到對目標監(jiān)測區(qū)域的感知和管理，在達到預(yù)期覆蓋要求的同時，盡可能地降低傳感器節(jié)點的能量消耗，從而延長網(wǎng)絡(luò)生存時間。

目前在傳感器網(wǎng)絡(luò)覆蓋問題的研究中，經(jīng)常涉及到鄰居節(jié)點，覆蓋度、覆蓋重數(shù)、覆蓋效率、覆蓋時間等基本概念。

3.1鄰居節(jié)點

在節(jié)點的傳感范圍內(nèi)的節(jié)點，在傳感范圍內(nèi)相鄰的兩個節(jié)點一般會相交或相切，即通過相鄰的節(jié)點在傳感范圍內(nèi)連接起來，這樣才能完全覆蓋被檢測區(qū)域。

3.2覆蓋度

節(jié)點覆蓋的總面積與目標區(qū)域總面積的比值。其中節(jié)點覆蓋的總面積取集合概念中的并集，所以覆蓋程度一般是小于或等于1的。

其中P代表覆蓋程度，Ai表示第i個節(jié)點的覆蓋面積，N代表節(jié)點的數(shù)目，A表示整個目標區(qū)域的面積。

3.3覆蓋重數(shù)

如果監(jiān)測區(qū)域中的每一點至少被K個傳感器所覆蓋，則稱為K重覆蓋問題。覆蓋重數(shù)表示某個區(qū)域的覆蓋的冗余程度，如果這個區(qū)域在K個節(jié)點的傳感覆蓋范圍之內(nèi)，那么它的覆蓋重數(shù)就是K。

，

這里KA表示A區(qū)域的覆蓋重數(shù)，Ai節(jié)點i傳感范圍，Ki表示第i個節(jié)點傳感范圍是否覆蓋A區(qū)域，覆蓋時Ki為1，否則為0。

3.4覆蓋效率

覆蓋效率是衡量節(jié)點覆蓋范圍的利用率，用來反映整個網(wǎng)絡(luò)能量的消耗情況。定義為所有節(jié)點的有效覆蓋范圍的并集與所有節(jié)點覆蓋范圍之和的比值。

其中CE代表覆蓋效率，Ai表示第i個節(jié)點的覆蓋面積，N代表節(jié)點的數(shù)目。

3.5覆蓋時間

目標區(qū)域被完全覆蓋或者跟蹤時，所有工作節(jié)點從啟動到就緒所需要的時間（在有移動節(jié)點的覆蓋中是指移動節(jié)點移動到最終位置所需要的時間）。覆蓋時間在營救或者突發(fā)事件監(jiān)測中是一個很重要的節(jié)點覆蓋衡量指標，可以通過算法優(yōu)化和改進硬件設(shè)施來減少覆蓋時間。

四、覆蓋控制技術(shù)面臨的問題與挑戰(zhàn)

4.1感知模型種類改進

目前，己有的節(jié)點感知模型均為理想模型，并未考慮到實際應(yīng)用中存在于無線通信信道中的信號干擾、障礙物以及監(jiān)測區(qū)域內(nèi)的天氣影響等要素，因此針對無線傳感器網(wǎng)絡(luò)的實際應(yīng)用需要對于節(jié)點感知模型的種類進行改進，達到更好的效果。

4.2提供移動性的支持

目前，傳感器網(wǎng)絡(luò)覆蓋控制算法和協(xié)議大都假定傳感節(jié)點是靜態(tài)的。對于戰(zhàn)場、救援等復(fù)雜應(yīng)用場景，如何通過引入移動節(jié)點建立靜態(tài)節(jié)點與移動節(jié)點、多個移動節(jié)點之間的協(xié)作感知，以及對熱點區(qū)域或移動目標的持續(xù)性跟蹤覆蓋，仍將是今后關(guān)注的一個研究問題。

4.3三維空間的覆蓋控制

目前，無線傳感器網(wǎng)絡(luò)覆蓋控制的研究是針對二維空間展開的，然而，在實際應(yīng)用中傳感器節(jié)點的感知多數(shù)是在三維空間中進行的。因此，對于三維空間的無線傳感器網(wǎng)絡(luò)覆蓋控制可以作為進一步的研究工作。

4.4存在障礙物的覆蓋控制

目前的研究僅考慮到監(jiān)測區(qū)域內(nèi)存在的“熱點區(qū)域”，沒有考慮障礙物的存在對無線傳感器網(wǎng)絡(luò)覆蓋控制的影響，這種假設(shè)是與實際應(yīng)用有所偏差的。因此，對于區(qū)域內(nèi)存在障礙物的網(wǎng)絡(luò)覆蓋控制是值得進一步研究的。

4.5大規(guī)模網(wǎng)絡(luò)覆蓋控制

在一些特定的應(yīng)用場合，如軍事偵查、生態(tài)環(huán)境監(jiān)測等，節(jié)點通常是通過高空拋灑方式高密度、大面積的隨機部署，因此會產(chǎn)生許多冗余節(jié)點。該問題可以通過加入部分可移動節(jié)點，節(jié)點布撒后，根據(jù)獲取的地域信息，動態(tài)改變網(wǎng)絡(luò)拓撲結(jié)構(gòu)，同時結(jié)合現(xiàn)己有節(jié)點調(diào)度策略，實現(xiàn)大規(guī)模網(wǎng)絡(luò)的覆蓋控制算法更為復(fù)雜。

五、總結(jié)展望

覆蓋控制作為體現(xiàn)傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量的主要指標之一，覆蓋控制理論及方法的研究近年來得到國內(nèi)外研究學(xué)者的廣泛關(guān)注。本文綜述了無線傳感器網(wǎng)絡(luò)覆蓋控制領(lǐng)域積累的國內(nèi)外新近的研究現(xiàn)狀，并指出當前亟待解決的問題和進一步的研究方向，期望本文的介紹能夠推動同行學(xué)者對這一領(lǐng)域的關(guān)注與研究。