無線傳感器網絡覆蓋控制問題

摘要：無線傳感器網絡具有廣泛的應用背景，目前已經發展成為一個重要的計算平臺。但是，由于無線傳感器網絡自身的特點，使其也面臨許多問題，如何有效地進行覆蓋控制，在保證網絡覆蓋質量的前提下，減少能量消耗，延長網絡壽命是其中最重要的問題之一。本文主要討論無線傳感器網絡的覆蓋控制的問題。

關鍵詞：無線傳感器網絡；覆蓋控制；區域覆蓋

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)08-10ppp-0c

1 引言

近年來，隨著微機電系統（micro-electro-mechanism system，簡稱MEMS）、無線通信、信息網絡與集成電路術的迅速發展，新興的無線傳感器網絡（wireless sensor networks，簡稱WSNs）應運而生。WSNs中的傳感器一般都具備數據處理和通信能力，并通過無線鏈路或直接或間接地將收集到的信號轉化為數據發送到一個指令中心（sink）。這種協作分布式傳感器網絡的一種自然組織結構，就是在各傳感器節點間以無線多跳方式組成一個自組織網絡。

與傳統的無線移動通信網絡和一般的自組織網（AdHoc）相比，存在著許多不同之處，WSNs有很多自身的特點。為了讓WSNs能夠完成目標監測和信息獲取的任務，必須保證無線傳感器節點能有效地覆蓋被監測的區域。目標覆蓋控制就是應用于解決上述問題，即在保證一定的服務質量（QoS）條件下，達到網絡覆蓋范圍最大化，提供可靠的區域監測和目標跟蹤服務。如何達到網絡覆蓋的最優化并且在優化的過程中考慮到與其相關的屬性（如節能、連通性、路由選擇等）成為目前研究覆蓋控制方面的主要課題。

2 無線傳感器網絡覆蓋控制問題分類

WSNs從誕生之初就與應用密切相關，WSNs覆蓋控制更是如此.如今的WSNs覆蓋控制問題不僅包括單純的覆蓋含義，更是與節能通信、路徑規劃、可靠通信和目標定位等具體應用緊密相連。為了對WSNs覆蓋控制問題有更加全面的認識，本文分別從節點的部署情況和節點能否運動兩個角度進行WSNs覆蓋控制問題分類。

2.1 根據節點的部署情況分類

根據節點的部署情況，我們可以將WSNs的覆蓋問題分為確定性覆蓋、隨機覆蓋兩大類。下面逐一對這兩類覆蓋控制類型加以總結。

2.1.1 確定性覆蓋

如果 WSN 的狀態相對固定或是WSNs環境已知，就可以根據預先配置的節點位置確定網絡拓撲情況或增加關鍵區域的傳感器節點密度，這種情況被稱為確定性覆蓋問題.此時的覆蓋控制問題，就成為一種特殊的網絡或路徑規劃問題.典型的確定性覆蓋有確定性區域/點覆蓋、基于網格（grid）的目標覆蓋和確定性網絡路徑/目標覆蓋3種類型。

確定性區域/點覆蓋是指已知節點位置的WSNs要完成目標區域或目標點的覆蓋，與確定性區域/點覆蓋相關的兩個著名計算幾何問題為藝術館走廊監控問題（art gallery problem）以及圓周覆蓋問題（circle covering problem）。

基于網格的目標覆蓋是指當地理環境情況預先確定時，使用二維（也可以為三維）的網格進行網絡的建模，并選擇在合適的格點配置傳感器節點來完成區域/目標的覆蓋。

確定性網絡路徑/目標覆蓋同樣也是考慮WSNs傳感器節點位置已知情況，但這類問題特別考慮了如何對穿越網絡的目標或其經過的路徑上各點進行感應與追蹤。

2.1.2 隨機覆蓋

在許多實際自然環境中，由于網絡情況不能預先確定且多數確定性覆蓋模型會給網絡帶來對稱性與周期性特征，從而掩蓋了某些網絡拓撲的實際特性。再加上WSNs自身拓撲變化復雜，導致采用確定性覆蓋在實際應用中具有很大的局限性，不能適用于戰場等危險或其他環境惡劣的場所。因此，我們需要進一步對節點隨機分布在傳感區域而預先沒有得到自身位置的情況進行討論，這正是WSNs隨機覆蓋所要解決的問題。

2.2 根據節點能否運動分類

2.2.1 靜態網絡覆蓋

靜態網絡覆蓋通常又被劃分為區域覆蓋（area coverage）、點覆蓋（point coverage）和柵欄覆蓋（barrier coverage）如圖。區域覆蓋是目前研究最多的領域，此時，WSNs主要用于監測某個區域即目標區域的每個點至少被一個傳感器節點覆蓋，同時，還要保證網絡內各節點的通信連接。如圖1（a）所示點覆蓋則是要求覆蓋一組給定的地點。圖1（b）中，黑色節點覆蓋了一組用小方形塊代表的目標地點；柵欄覆蓋主要用在戰場環境中，用來監測敵軍的車輛、坦克或步兵是否正在穿越某個區域。

圖1 靜態網絡覆蓋

2.2.2 動態網絡覆蓋

動態網絡覆蓋與靜態網絡覆蓋相反，無線傳感器節點具有一定的移動能力，即節點被初始部署后，可根據網絡對監測區域的覆蓋情況，移動節點而進行重部署。可見動態網絡覆蓋能更好地對區域進行監測服務。

3 覆蓋控制中核心的問題

WSNs覆蓋控制技術的應用，有助于節點能量的有效控制、感知服務質量的提高和網絡壽命的延長。另一方面，也會帶來數據傳輸、管理、存儲和計算等代價的提高。所以WSNs覆蓋控制協議的性能評價標準對于分析一個覆蓋控制算法的可用性與有效性非常重要。

3.1 覆蓋能力

WSNs最基本的功能是利用節點監測部署區域的情況，進行數據收集，因此網絡覆蓋能力是評價網絡服務質量的重要指標之一，也是衡量一個WSNs覆蓋控制協議是否優劣的首要標準。對于區域覆蓋而言，若網絡中的節點可以監測整個區域，則稱為1重覆蓋。若整個監測區域至少被k個不同的節點同時監測，則稱為k重覆蓋。某些應用并不要求網絡提供完全覆蓋，當網絡的覆蓋率大于某個閾值時，即可滿足要求，這稱為部分覆蓋。

3.2 網絡連通性

由于WSNs是一種無基礎設施的網絡，大量節點采用自組織方式協同完成數據查詢、搜集等任務，因此，網絡節點之間需要能夠以無線多跳的方式直接或間接地通信。網絡的連通性將有效地保證網絡自身以無線多跳自組織地方式協同工作，并直接決定了WSNs感知、監視、傳感、通信等各種服務質量。

3.3 能量有效性

由于傳感器節點能力受限、節點數量巨大、實際應用的環境條件復雜且大多不允許對節點進行電池更換，因此如何減少節點的能量消耗，延長整體網絡的生存時間已成為WSNs

的重要性能指標。現有的覆蓋控制技術通常采用減小節點通信發射功率、節點狀態調度、減少節點間消息交換開銷、減少節點信息維護開銷等方法減少網絡能耗，使網絡壽命最大化。

3.4 能耗負載平衡

在WSNs中，若某些節點能耗負載過大，會導致節點過早死亡，使網絡監控產生盲點或使網絡產生分割，節點數據不能轉發到基站，因此節點能耗負載平衡也是覆蓋控制協議設計的目標之一。覆蓋控制協議通常采用定期按輪運行的方式，實現節點能耗負載平衡。

3.5 算法復雜性

不同WSNs覆蓋控制算法其實現方式不同導致算法復雜程度也有較大差別。衡量一個WSNs覆蓋控制算法是否優化的一項重要標準就是其算法的復雜性程度，通常包括時間復雜度、通信復雜度以及實現復雜度等。

3.6 網絡可擴展性

可擴展性是WSNs覆蓋控制的一項關鍵需求。通常WSNs采用大規模地隨機部署方式，若沒有網絡可擴展性的保證，網絡的性能會隨著網絡規模的增加而顯著降低。因此網絡的可擴展性需求在WSNs中尤為明顯。

4 結束語

無線傳感器網絡將邏輯上的信息世界與真實的物理世界融合在一起，極大地提高了人們認識和改造世界的能力。而網絡覆蓋控制作為WSN實施過程中的一個基本問題，反映了網絡所能提供的“感知”服務質量。本文立足于WSN的覆蓋控制問題，對覆蓋問題的特點和要控制策略要解決的核心問題進行了說明。

參考文獻：

[1]趙旭，等.無線傳感器網絡的覆蓋控制[J].傳感器與微系統，2007，26(8):62-65.

[2]毛鶯池，等.無線傳感器網絡覆蓋控制技術研究[J].計算機科學，2007，34(3):20-26.

[3]任彥，等.無線傳感器網絡中覆蓋控制理論與算法[J].Journal of Software，2006，17(3):422-433.