無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題

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

1  無(wú)線傳感器網(wǎng)絡(luò)覆蓋理論基礎(chǔ)

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

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

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

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

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

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

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

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

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

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

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

2.2.2  無(wú)線傳感器網(wǎng)絡(luò)覆蓋的計(jì)算

關(guān)于無(wú)線傳感器網(wǎng)絡(luò)覆蓋的計(jì)算主要是介紹現(xiàn)有的配置和覆蓋相關(guān)的算法及一般的無(wú)線傳感器網(wǎng)絡(luò)覆蓋設(shè)計(jì)準(zhǔn)則。

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

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