無線傳感網(wǎng)絡(luò)部分覆蓋技術(shù)研究展望

宋 剛，黃 科

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

0 引言

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

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

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

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

1 覆蓋問題評估

覆蓋評估就是對覆蓋度的評價和估算。評價原則是以最少的傳感器節(jié)點覆蓋目標區(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é)點的覆蓋面積之和，Si是第i個傳感器節(jié)點。

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

1.1 全覆蓋與部分覆蓋定義

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

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

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

部分覆蓋技術(shù)按拓撲形狀分為熱點覆蓋、路徑覆蓋、陷阱覆蓋。下面分別探究國外的研究進展。

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

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

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

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

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

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

2 文獻分析

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

3 結(jié)語

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