宋 剛，黃 科

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

0 引言

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

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

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

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

1 覆蓋問題評估

覆蓋評估就是對覆蓋度的評價(jià)和估算。評價(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個傳感器節(jié)點(diǎn)。

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

1.1 全覆蓋與部分覆蓋定義

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

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

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

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

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

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

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

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

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

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

2 文獻(xiàn)分析

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

3 結(jié)語

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