無線傳感網絡部分覆蓋技術研究展望

宋 剛，黃 科

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

0 引言

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

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

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

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

1 覆蓋問題評估

覆蓋評估就是對覆蓋度的評價和估算。評價原則是以最少的傳感器節點覆蓋目標區域。在監視區域中，有效覆蓋區域和監視區域的特定值稱為網絡覆蓋率。網絡覆蓋率的意義是覆蓋率越大，覆蓋質量越好。

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

但當覆蓋率大到超過有效監視區域的時候，就產生了有效覆蓋率的概念。它是傳感器節點有效面積與監視區域中傳感器節點面積的比值。

1.1 全覆蓋與部分覆蓋定義

全覆蓋定義為目標區域內每個監視區域至少被一個傳感器節點覆蓋。即監視區域要大于目標區域：

部分覆蓋定義為目標區域內至少有一個監視區域沒有被任何一個傳感器節點覆蓋。即監視區域與目標區域的交集小于目標區域：

1.2 國外部分覆蓋技術研究展望

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

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

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

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

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

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

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

2 文獻分析

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

3 結語

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