宋 剛，黃 科

(重慶城市管理職業(yè)學(xué)院，重慶 401331)

0 引言

無(wú)線傳感網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）是一種按空間分布的計(jì)算機(jī)無(wú)線網(wǎng)絡(luò)，在網(wǎng)絡(luò)終端是可以感知周圍環(huán)境的傳感器。它是由成千上萬(wàn)的傳感器以自組織、混合、多跳的方式連接起來(lái)的。它實(shí)現(xiàn)了數(shù)據(jù)的采集、計(jì)算、通信、存儲(chǔ)等操作。隨著信息技術(shù)的飛速發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)逐步由軍事領(lǐng)域應(yīng)用到民用領(lǐng)域。

覆蓋范圍是無(wú)線傳感網(wǎng)絡(luò)中最重要的問(wèn)題之一。覆蓋范圍的定義，一般認(rèn)為需要在監(jiān)測(cè)區(qū)域內(nèi)，每個(gè)信息節(jié)點(diǎn)位置需要用到多少個(gè)傳感器，來(lái)保證節(jié)點(diǎn)范圍能被至少一個(gè)傳感器覆蓋。覆蓋問(wèn)題反映了傳感器網(wǎng)絡(luò)對(duì)監(jiān)測(cè)區(qū)域的監(jiān)測(cè)范圍的響應(yīng)密度，也是從根本上評(píng)價(jià)整個(gè)網(wǎng)絡(luò)服務(wù)質(zhì)量的依據(jù)。在各傳感器能量損耗、網(wǎng)絡(luò)通信容量、計(jì)算處理能力等資源受到限制消耗的情況下，盡可能地優(yōu)化傳感節(jié)點(diǎn)的位置，進(jìn)而獲取優(yōu)化的無(wú)線傳感覆蓋率。

在描述無(wú)線傳感器網(wǎng)絡(luò)覆蓋模型中，一般分成確定性覆蓋模型和隨機(jī)性覆蓋模型這兩大類。在確定性覆蓋中覆蓋區(qū)域不隨著時(shí)間發(fā)生變化，傳感器的位置相對(duì)固定。而在隨機(jī)性覆蓋中，覆蓋區(qū)域環(huán)境惡劣，人員難以進(jìn)入，只能代以空投等方式布放傳感器，形成隨機(jī)性覆蓋。

覆蓋模型又可以按照覆蓋程度，分為完全覆蓋與部分覆蓋。完全覆蓋指的是對(duì)興趣區(qū)域的監(jiān)測(cè)需要100%的覆蓋率，而部分覆蓋指的是對(duì)興趣區(qū)域的覆蓋率大于0小于100%即可。

1 覆蓋問(wèn)題評(píng)估

覆蓋評(píng)估就是對(duì)覆蓋度的評(píng)價(jià)和估算。評(píng)價(jià)原則是以最少的傳感器節(jié)點(diǎn)覆蓋目標(biāo)區(qū)域。在監(jiān)視區(qū)域中，有效覆蓋區(qū)域和監(jiān)視區(qū)域的特定值稱為網(wǎng)絡(luò)覆蓋率。網(wǎng)絡(luò)覆蓋率的意義是覆蓋率越大，覆蓋質(zhì)量越好。

其中P是覆蓋率，Area(S)表示監(jiān)視區(qū)域面積，∪i=1,2,…,NSi是傳感器節(jié)點(diǎn)的覆蓋面積之和，Si是第i個(gè)傳感器節(jié)點(diǎn)。

但當(dāng)覆蓋率大到超過(guò)有效監(jiān)視區(qū)域的時(shí)候，就產(chǎn)生了有效覆蓋率的概念。它是傳感器節(jié)點(diǎn)有效面積與監(jiān)視區(qū)域中傳感器節(jié)點(diǎn)面積的比值。

1.1 全覆蓋與部分覆蓋定義

全覆蓋定義為目標(biāo)區(qū)域內(nèi)每個(gè)監(jiān)視區(qū)域至少被一個(gè)傳感器節(jié)點(diǎn)覆蓋。即監(jiān)視區(qū)域要大于目標(biāo)區(qū)域：

部分覆蓋定義為目標(biāo)區(qū)域內(nèi)至少有一個(gè)監(jiān)視區(qū)域沒(méi)有被任何一個(gè)傳感器節(jié)點(diǎn)覆蓋。即監(jiān)視區(qū)域與目標(biāo)區(qū)域的交集小于目標(biāo)區(qū)域：

1.2 國(guó)外部分覆蓋技術(shù)研究展望

部分覆蓋技術(shù)按拓?fù)湫螤罘譃闊狳c(diǎn)覆蓋、路徑覆蓋、陷阱覆蓋。下面分別探究國(guó)外的研究進(jìn)展。

在熱點(diǎn)覆蓋中，區(qū)域內(nèi)某些節(jié)點(diǎn)會(huì)出現(xiàn)比其他節(jié)點(diǎn)更高的優(yōu)先級(jí)應(yīng)用，這就要求覆蓋算法能靈活調(diào)度傳感器的優(yōu)先權(quán)。由Li等[1]提出了兩個(gè)傳感器覆蓋調(diào)度算法：貪婪優(yōu)先（GA）和貪婪-旋轉(zhuǎn)-貪婪算法（GRG）。采用等邊三角形布置傳感器覆蓋目標(biāo)區(qū)域，在覆蓋調(diào)度隊(duì)列中以貪婪算法作為調(diào)度優(yōu)先級(jí)，最大化保證熱點(diǎn)區(qū)域的覆蓋率，并給以最大的網(wǎng)絡(luò)帶寬資源。并且這兩個(gè)算法對(duì)節(jié)點(diǎn)失效有一定的冗余措施，即使有少量傳感器節(jié)點(diǎn)失效，仍能正常工作，整個(gè)網(wǎng)絡(luò)突然完全失效的可能性很小。然而，該算法并沒(méi)有保證目標(biāo)區(qū)域各節(jié)點(diǎn)的最大覆蓋半徑。

當(dāng)固定節(jié)點(diǎn)不能滿足突發(fā)熱點(diǎn)覆蓋時(shí)，研究人員也在探索采用移動(dòng)傳感器節(jié)點(diǎn)位置去覆蓋熱點(diǎn)。例如，F(xiàn)alcon等[2]提出了利用無(wú)人載具搭載傳感器去填補(bǔ)覆蓋漏洞。他提出一種新的覆蓋增強(qiáng)協(xié)議CBCA。該協(xié)議通過(guò)無(wú)人載具運(yùn)輸新的傳感器節(jié)點(diǎn)到覆蓋失效位置，頂替原先的傳感器職責(zé)，從而修復(fù)覆蓋漏洞。該協(xié)議需要預(yù)先安排部分傳感器節(jié)點(diǎn)作為后備節(jié)點(diǎn)，其后備節(jié)點(diǎn)的多少會(huì)影響整個(gè)網(wǎng)絡(luò)成本。

利用傳感器的移動(dòng)特性，還可以保證對(duì)已知位置的目標(biāo)節(jié)點(diǎn)做連續(xù)覆蓋。在R.Tan等[3]中，作者考慮到了傳感器相應(yīng)的滯后性，盡量移動(dòng)節(jié)點(diǎn)位置來(lái)保證覆蓋目標(biāo)檢測(cè)的即時(shí)性。提出了新的移動(dòng)算法來(lái)減小傳感器的時(shí)延。該算法的特點(diǎn)是將固定節(jié)點(diǎn)作為移動(dòng)節(jié)點(diǎn)的后備，減小了后備移動(dòng)節(jié)點(diǎn)的需求。不久，Mathew等[4]針對(duì)已知位置的靜態(tài)目標(biāo)，提出了新的譜線多間距覆蓋算法。Mathew等[5]又區(qū)分了移動(dòng)目標(biāo)的覆蓋與靜態(tài)目標(biāo)覆蓋，并提出了動(dòng)態(tài)譜線多間距覆蓋算法。Liao等[6]提出了基于移動(dòng)節(jié)點(diǎn)自主移動(dòng)的覆蓋算法。移動(dòng)節(jié)點(diǎn)在有需求時(shí)，會(huì)自主根據(jù)算法移動(dòng)到指定位置，提高覆蓋度，填補(bǔ)覆蓋漏洞。

在軍事領(lǐng)域中，存在邊界巡邏和入侵檢測(cè)的應(yīng)用。針對(duì)這種應(yīng)用，路徑覆蓋中的柵欄覆蓋能滿足需求。在這類應(yīng)用中，當(dāng)一個(gè)無(wú)線傳感網(wǎng)絡(luò)按K-Barrier進(jìn)行覆蓋時(shí)，以未知路徑行進(jìn)的闖入者不論如何變換行進(jìn)路徑，當(dāng)進(jìn)入傳感器覆蓋區(qū)的帶狀(belt)區(qū)域時(shí)，都會(huì)被至少K個(gè)傳感器發(fā)現(xiàn)。Kong等[7]探討在帶狀區(qū)域是否為K-Barrier覆蓋的問(wèn)題，他們將區(qū)域內(nèi)節(jié)點(diǎn)重迭覆蓋的關(guān)系，重組成一個(gè)帶有虛擬節(jié)點(diǎn)的覆蓋圖，將區(qū)域內(nèi)覆蓋問(wèn)題等價(jià)為覆蓋圖上連通性是否存在的問(wèn)題。此外，Cheng等[8]提出一個(gè)局限性的柵欄算法，在闖入者的行進(jìn)路徑寬度是有限的前提下，讓一個(gè)節(jié)點(diǎn)判斷其鄰近區(qū)域是否具有局限覆蓋特性，并可求出形成邊界覆蓋節(jié)點(diǎn)布設(shè)密度。

路徑覆蓋，它是由一個(gè)或數(shù)個(gè)具有移動(dòng)能力的偵測(cè)節(jié)點(diǎn)所組成，這些節(jié)點(diǎn)會(huì)在偵測(cè)區(qū)域內(nèi)來(lái)回移動(dòng)，并在移動(dòng)的過(guò)程中不斷偵測(cè)區(qū)域內(nèi)是否有目標(biāo)物。Li等[9]提出POI興趣點(diǎn)的概念。每一個(gè)POI是移動(dòng)節(jié)點(diǎn)必須經(jīng)過(guò)的點(diǎn)，POI重要性較低的點(diǎn)可容忍較長(zhǎng)的等待時(shí)間等待移動(dòng)節(jié)點(diǎn)的覆蓋。而Xi等[10]對(duì)隨機(jī)產(chǎn)生的動(dòng)態(tài)興趣點(diǎn)的掃描問(wèn)題進(jìn)行了分析。此外，Chu[11]提出讓每個(gè)移動(dòng)中的感測(cè)節(jié)點(diǎn)互相交換位置信息和來(lái)回時(shí)間，并由節(jié)點(diǎn)決定是否改變現(xiàn)有移動(dòng)路徑。Du等[12]提出了兩個(gè)啟發(fā)式算法：MinExpand和OSweep。在Gorain等[13]中作者提出縮短掃描點(diǎn)停留時(shí)間比增加移動(dòng)速度能更有效地減少掃描時(shí)間。此外，Chang等[14]提出了基于時(shí)限目標(biāo)掃描算法。該算法給每個(gè)興趣點(diǎn)分配一個(gè)優(yōu)先級(jí)，當(dāng)掃描的時(shí)候，移動(dòng)節(jié)點(diǎn)會(huì)按照興趣點(diǎn)的優(yōu)先程度掃描每個(gè)目標(biāo)節(jié)點(diǎn)。該算法的主要缺點(diǎn)是當(dāng)各點(diǎn)是不規(guī)則分布在監(jiān)測(cè)區(qū)域內(nèi)，移動(dòng)節(jié)點(diǎn)會(huì)出現(xiàn)順序先后的問(wèn)題，性能受到巡邏路徑的影響。為此，Chang等[15]還提出了Chang等[14]的另一個(gè)不足，移動(dòng)節(jié)點(diǎn)所須經(jīng)過(guò)的掃描點(diǎn)數(shù)量和掃描點(diǎn)之間的距離不相等，導(dǎo)致各移動(dòng)節(jié)點(diǎn)在掃描時(shí)間上的不同會(huì)導(dǎo)致覆蓋質(zhì)量的差異。

部分覆蓋中若存在一個(gè)覆蓋范圍上的空洞，則就是Balister等[16]提出的陷阱覆蓋。當(dāng)空洞直徑不能超過(guò)一個(gè)預(yù)設(shè)的閾值時(shí)，則傳感器網(wǎng)絡(luò)可以穩(wěn)定提供陷阱覆蓋。Chen[17]則提出了一個(gè)優(yōu)化的陷阱覆蓋，核心是當(dāng)網(wǎng)絡(luò)冗余度較大，節(jié)點(diǎn)數(shù)量足夠豐富的情況下，陷阱覆蓋可以建立在全覆蓋基礎(chǔ)上。

2 文獻(xiàn)分析

現(xiàn)在從覆蓋度（1、K）、特性（集中、分布）、傳感節(jié)點(diǎn)類型（移動(dòng)、混合、機(jī)器人）以及網(wǎng)絡(luò)拓?fù)洌ㄆ教?、簇）方面分析現(xiàn)存的部分覆蓋相關(guān)的文獻(xiàn)工作，如表1所示。

3 結(jié)語(yǔ)

本文首先闡述了無(wú)線傳感網(wǎng)絡(luò)的覆蓋問(wèn)題的由來(lái)及其重要性，分析覆蓋問(wèn)題的評(píng)估方法以及分類方法，然后對(duì)國(guó)外近期無(wú)線傳感網(wǎng)絡(luò)的部分覆蓋技術(shù)進(jìn)展進(jìn)行了分別討論。對(duì)其中的技術(shù)特點(diǎn)和進(jìn)行分析和比較。從中可以看出部分覆蓋技術(shù)的發(fā)展方向應(yīng)該是：在滿足覆蓋度的情況下，強(qiáng)調(diào)分布式、平坦的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；傳感器節(jié)點(diǎn)可以移動(dòng)部署，對(duì)突發(fā)熱點(diǎn)、興趣點(diǎn)能保證及時(shí)覆蓋；網(wǎng)絡(luò)健壯性強(qiáng)，具備一定的冗余度等。綜上所述，國(guó)外近期對(duì)無(wú)線傳感網(wǎng)絡(luò)中的部分覆蓋問(wèn)題提出了眾多的解決辦法，為我們的進(jìn)一步研究提供了方向。