無線傳感器網(wǎng)絡覆蓋問題

近年來，無線傳感器網(wǎng)絡引起了業(yè)界極大關注，其應用環(huán)境通常是由價格便宜的傳感器節(jié)點組成的，每個節(jié)點都能夠采集、存儲和處理環(huán)境信息，并且能和鄰居節(jié)點通過無線鏈路保持通信。覆蓋問題是無線傳感器網(wǎng)絡配置首先面臨的基本問題，因為傳感器節(jié)點可能任意分布在配置區(qū)域，它反映了一個無線傳感器網(wǎng)絡某區(qū)域被監(jiān)測和跟蹤的狀況。隨著無線傳感器網(wǎng)絡應用的普及，更多的研究工作深入到其網(wǎng)絡配置的基本理論方面，其中覆蓋問題就是無線傳感器網(wǎng)絡設計和規(guī)劃需要面臨的一個基本問題之一。隨著深入研究的角度不同，覆蓋問題也表述成不同的理論模型，甚至在計算幾何里面就能找到與覆蓋相關的解決方案。盡管這些辦法并不能直接應用到無線傳感器網(wǎng)絡中，但是研究這些問題有助于建立讀者對無線傳感器網(wǎng)絡覆蓋問題相關的理論背景。

1  無線傳感器網(wǎng)絡覆蓋理論基礎

在現(xiàn)有的研究成果當中，很多都是致力于解決傳感器網(wǎng)絡的部署和監(jiān)測及覆蓋與連接的關系等方面問題。另外，也有一些研究致力于特定的應用需求，但其核心思想都是與覆蓋問題有關的。例如，減少傳感器節(jié)點的有效工作時間，那些共享感應區(qū)域和任務的傳感器節(jié)點可以關掉電源以節(jié)省能量，從而可以延長網(wǎng)絡的壽命。為此，必須確定關閉哪些傳感器節(jié)點及如何調度分配節(jié)點的工作時間，以至于當關掉節(jié)點時網(wǎng)絡不存在覆蓋的盲點。

本小節(jié)將著重討論一下與無線傳感器網(wǎng)絡覆蓋相關的兩個計算幾何問題。第一個就是藝術館問題(Art Gallery Problem)。設想藝術館的業(yè)主想在館內放置照相機，以便能夠預防小偷盜竊。關于實現(xiàn)這個想法存在兩個問題需要回答：首先就是到底需要多少臺相機；其次，這些相機應當放置在哪些地方才能保證館內每個點至少被一臺相機監(jiān)視到。假定相機可以有360°的視角而且可以極大速度旋轉。此外，相機可以監(jiān)視任何位置，視線不受影響。問題優(yōu)化要實現(xiàn)的目標就是所需相機的數(shù)目應該最小化。在這個問題當中，藝術館通常建模成一個二維平面的簡單多邊形。一個簡單的解決辦法就是將多邊形分成不重疊的三角形，每個三角形里面放置一個相機。通過三角測量法將多邊形分成若干個三角形，這樣可以實現(xiàn)任何一個多邊形都可被

個相機所監(jiān)視到，這里n表示多邊形所包含的三角形的數(shù)目。這也是最糟糕情況下的最佳結果。如圖2-8所示是將一個簡單多邊形用三角測量法拆分的例子，放置兩個監(jiān)視相機足以覆蓋整個藝術館。盡管這個問題在二維平面可以得到最優(yōu)解，然而擴展到三維空間，這個問題就變成了NP-hard問題了。   

另外一個與無線傳感器網(wǎng)絡覆蓋相關的幾何問題是圓覆蓋問題，即在一個平面上最多需要排列多少個相同大小的圓，才使其能夠完全覆蓋整個平面。換個角度說，也就是給定了圓的數(shù)目，如何使得圓的半徑最小。參考文獻就矩形平面區(qū)域的圓覆蓋問題做了詳細的探討。A.Heppes和J.B.M.Melissen實現(xiàn)了矩形平面的圓最優(yōu)覆蓋問題，分為最多用5個圓和7個圓來完成覆蓋兩種情況。如圖2-9所示給出了一個7個圓最優(yōu)覆蓋的一個例子。參考文獻[10]給出了6個和8個圓的最優(yōu)覆蓋辦法，并且基于一種模擬退火方法提出了一種全新的用11個圓的覆蓋解決方案。多達30個圓的覆蓋問題在文獻[11]中也做了詳細的探討。

無線傳感器網(wǎng)絡的覆蓋問題在本質上和上面的幾何計算問題是一致的：需要知道是否某個特定的區(qū)域被充分覆蓋和完全處于監(jiān)視之下。就成本而言，配置的傳感器節(jié)點的數(shù)量是非常重要的。盡管計算幾何研究的結果對理解傳感器網(wǎng)絡覆蓋問題提供了一個理論背景，但僅僅是計算幾何問題的求解辦法是不能直接應用于無線傳感器網(wǎng)絡的。主要有以下幾個方面的原因：首先，所做的前提假設不同。例如，藝術館問題的照相機可以看到無窮遠處，除非中間有障礙物遮擋。事實上剛好相反，傳感器節(jié)點存在最大的感應范圍。其次，無線傳感器網(wǎng)絡通常沒有固定的基礎設施，并且其拓撲可能隨時變化。因此，很多決策必須通過分布式方式來完成。然而，大多數(shù)幾何問題都是通過集中式來解決的。

在典型的無線傳感器網(wǎng)絡應用當中，放置或配置一些傳感器節(jié)點來監(jiān)視一個區(qū)域或點集。一些應用中可以選擇傳感器配置場地，如定點部署和配置，這種方式稱為確定性配置：而另外一些應用(如敵方區(qū)域或非常惡劣等人員不能到達的環(huán)境)，只能通過隨機部署(如空投撒播方式)足夠多的傳感器節(jié)點到監(jiān)視區(qū)域，希望空投后未遭破壞的傳感器足以監(jiān)視目標區(qū)域，這種方式稱為非確定性的配置或隨機配置。如果可以選取部署場地，可采用確定性的傳感器配置方法；否則，該配置就是隨機配置。在上面兩種配置情況下，都希望部署的傳感器集合能夠彼此通信，或者直接或者間接通過多跳方式通信。因此，除了要覆蓋感應的區(qū)域或點集外，通常需要配置的傳感器集合能夠形成一個互聯(lián)的網(wǎng)絡。對于已經(jīng)放置好的傳感器，很容易地就能檢測是否配置的傳感器集合覆蓋了目標區(qū)域或點集，而且也能判斷是否該集合相互連通。就覆蓋特性而言，需要知道各個傳感器節(jié)點的感應范圍(假設傳感器能夠感應距離r之內發(fā)生的事件，其中，r為傳感器的感應半徑)。就連接特性而言，需要知道傳感器的通信半徑，記為c。Zhang和Lou在文獻[12]中給出了包含連接的覆蓋的充分必要條件，滿足定理1：

定理1：當傳感器的密度(即單位區(qū)域的傳感器數(shù)目)為有限時，c≥2r是覆蓋包含連接性的充分必要條件。

X.Wang等人也證明了在k階覆蓋(每個點至少被k個傳感器覆蓋)和k階連接性(配置傳感器的通信圖是尼階連接的)情況下的一個類似的結論，滿足定理2。

定理2：當c≥2r，一個凸區(qū)域的k階覆蓋必定包含了k階連接性。

注意到k>1的k階覆蓋提供了一定的容錯度，能夠監(jiān)視所有的點，只要不多于k-1個傳感器故障或失效。

當然，除了上面介紹的典型的無線傳感器網(wǎng)絡配置問題外，也可能出現(xiàn)其他形式的無線傳感器配置問題。例如，不必要求傳感器節(jié)點間彼此通信。相反，每個傳感器可直接和一個位于所有傳感器通信半徑范圍內的基站通信。還有一種情況就是傳感器是移動和自我配置的無線傳感器。移動傳感器集合可以部署到一個未知的和有潛在危險的環(huán)境中。根據(jù)初始的配置，這種傳感器可以重新確定位置以便實現(xiàn)未知環(huán)境的最大覆蓋。它們再將采集到的信息發(fā)給感應環(huán)境外面的一個基站。

2.2.2  無線傳感器網(wǎng)絡覆蓋的計算

關于無線傳感器網(wǎng)絡覆蓋的計算主要是介紹現(xiàn)有的配置和覆蓋相關的算法及一般的無線傳感器網(wǎng)絡覆蓋設計準則。

Andrew Howard等專門針對移動無線傳感器網(wǎng)絡提出了一種增量自我配置的貪婪算法(Greedy and Incremental Self-deployment Algorithm)。移動無線傳感器網(wǎng)絡是一個分布式的節(jié)點集合，每個節(jié)點都有感應、計算、通信和局部移動等功能。而配置區(qū)域通常都是惡劣或未知的環(huán)境區(qū)域。該增量自我配置的貪婪算法的基本思想就是每次配置一個節(jié)點到未知區(qū)域，每個加入的節(jié)點都充分利用先前配置的節(jié)點收集到的信息來確定其最佳目標位置。算法設計的目的就是使網(wǎng)絡的覆蓋最大化，而同時又確保節(jié)點彼此保持視距通信，即本地化。實現(xiàn)本地化可以通過Mesh結構的方式實現(xiàn)，節(jié)點可以在完全未知的環(huán)境下通過使用其他節(jié)點作為路標來實現(xiàn)本地化，從而確定節(jié)點之間的相互位置和保證可靠通信。該算法的核心就是貪婪和增量。貪婪一詞來自于該算法嘗試為每個節(jié)點都尋找能使網(wǎng)絡覆蓋最大化的位置。事實上，尋找節(jié)點的最優(yōu)位置是一個相當困難的問題，因此不得不采用大量的初始化操作來指導選擇的過程，如邊界初始化和覆蓋初始化等。增量一詞主要是因為每次配置只增加一個節(jié)點到配置區(qū)域。該算法的復雜度為O(n2)，其中n為配置的傳感器節(jié)點數(shù)目。

A.Howard等提出了基于電勢場技術的未知環(huán)境移動傳感器網(wǎng)絡的部署配置方法。這種移動傳感器網(wǎng)絡可通過簡易的初始配置就可實現(xiàn)網(wǎng)絡的自我配置。網(wǎng)絡內的節(jié)點可以隨意擴展，使得網(wǎng)絡覆蓋最大化。該配置算法的基本思想就是將傳感器節(jié)點當做假想的物粒子，且受到勢力場的勢力。勢力壓迫節(jié)點彼此之間和障礙物之間發(fā)生作用力。通過節(jié)點的初始簡易配置快速地在整個網(wǎng)絡擴散，從而最大化網(wǎng)絡的覆蓋。節(jié)點之間除了相互的排斥力外，還受到一個黏性摩擦力。該力用來確保網(wǎng)絡最終達到一個靜態(tài)平衡狀態(tài)，也就是說所有節(jié)點最后都能夠完全停止下來。然而，黏性摩擦力不能阻止網(wǎng)絡對環(huán)境變化的反應。如果節(jié)點發(fā)生移動，網(wǎng)絡就會為變化后的環(huán)境自動重新配置，直到再次達到一個靜態(tài)平衡狀態(tài)。這樣，節(jié)點僅僅當需要的時候才改變位置，從而可以節(jié)省大量的寶貴能量資源。該算法的核心就是利用了電勢場技術，但依賴于一個重要的假設：每個節(jié)點的安裝傳感器都能夠確定它的鄰居節(jié)點及障礙物的距離和方位(可利用掃描激光距離探測儀或全息相機配置適當?shù)膫鞲衅?。利用該信息，節(jié)點就可知道作用的電勢力的大小，并將其轉換為控制矢量信息發(fā)給傳感器的發(fā)動機。該算法不需要其他信息，最大的優(yōu)點就是不需要考慮環(huán)境的建模、節(jié)點的局部定位和節(jié)點彼此之間的通信。因此，該算法具有較高的魯棒性和擴展性。