無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制技術(shù)綜述

王廣超　王振榮　楊軍

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

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

引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1鄰居節(jié)點(diǎn)

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

3.2覆蓋度

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

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

3.3覆蓋重?cái)?shù)

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

，

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

3.4覆蓋效率

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

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

3.5覆蓋時(shí)間

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

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

4.1感知模型種類改進(jìn)

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

4.2提供移動(dòng)性的支持

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

4.3三維空間的覆蓋控制

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

4.4存在障礙物的覆蓋控制

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

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

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

五、總結(jié)展望

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