1、無線傳感器網絡覆蓋技術譚慧婷 150400241. 覆蓋技術理論基礎 覆蓋問題是無線傳感器網絡配置首先要面對的基本問題，它反映了一個無線傳感器網絡某區域被檢測和跟蹤的狀況。現有的研究結果，很多都是致力于解決傳感器網絡的部署和檢測以及覆蓋與連接的關系等方面的問題。 覆蓋問題可以表述成不同的理論模型，甚至在平面幾何里就能找到相應的解決方案。即使簡單地只從數學上來考慮，在部署傳感器節點的時候，我們必須知道怎樣用相同的節點數覆蓋盡可能大的區域。 為了對網絡的覆蓋問題先有一個初步的認識，這里我們提出一個幾何問題-藝術館問題來理解。 假設藝術館的主人想在場館內放置監視器來防止盜竊。假定相機可以有360度的

2、視角而且可以極大速度旋轉，相機可以監視任何位置，視線不受影響。 關于實現這個想法存在兩個問題需要回答：首先就是到底需要多少臺相機；其次，這些相機應當放置在哪些地方才能保證館內每個點至少被一臺相機監視到。 一個簡單的辦法就是將多邊形分成不重疊的三角形，每個三角形里面放置一個相機。通過這個方法，我們可以得到最佳分布應該如下圖，放置兩個相機相機足以覆蓋整個藝術館。我們可以知道無線傳感器網絡的覆蓋問題在本職上和上面的幾何問題是一致的：需要知道是否某個區域被充分覆蓋以及完全處于監視之下。 但我們也必須認識到，幾何研究的結果為理解傳感器覆蓋問題提供了一個理論背景，但這樣的求解辦法是無法直接應用到無線傳感器

3、網絡。因為：1. 監視器可以看到無窮遠的地方只要沒有障礙物阻擋，但是傳感器節點存在最大感應范圍；2. 無線傳感器網路沒有類似監視器之間固定的基礎設施，其拓撲結構可能隨時變化。2.覆蓋的感知模型在討論節點如何布置之前，需要先知道傳感器節點的感知模型。目前主要是兩種。a.布爾感知模型布爾感知模型是以一個節點為圓心，以感知距離為半徑的圓形區域，只有落在該圓形區域內的點才能被該節點覆蓋，這種模型也被稱為0-1模型。其數學表達式為pij=1,d(i,j)r0,d(i,j)>rb.概率感知模型概率感知模型中，目標被感知的概率不再是常數，而是由目標到節點間距、節點物理特性等諸多因素決定的變量。在節點i

4、不存在鄰居節點的前提下，節點i對檢測區域內目標j的感知概率有以下三種定義形式：pij=e-d(i,jpij=1,d(i,j)r1e-d(i,j)-r,r1<d(i,j)r20,d(i,j)>r2pij=11+d(i,j),d(i,j)r0,d(i,j)>r其中d(i,j)為節點i到目標j之間的歐式距離，和是和傳感器物理特性有關的類型參數。從以上的3種形式可以看出，任一點的覆蓋概率是介于0和1之間的數。如果節點i存在N個鄰居節點，節點j落在和相鄰節點交疊傳感區域內，節點j的感知概率便會受到節點i與相鄰節點共同影響。假設節點i與相鄰節點感知區域的重疊區域為M，而且每個節點對目標的

5、感知是相互獨立的，那么M中任意節點j的感知概率為3.覆蓋算法分類a節點部署方式分類 按照無線傳感器網絡節點的不同配置方式(即節點否需要知道自身位置信息)，可以將無線傳感器網絡的覆蓋算法分為確定性覆蓋、隨機覆蓋兩大類。 (1)確定性覆蓋 這是已知節點位置的無線傳感器網絡要完成目標區域或目標點的覆蓋。 (2)隨機覆蓋 隨機覆蓋考慮在網絡中傳感器節點隨機分布且位置未知的條件下，完成對監測區域的覆蓋任務。b覆蓋目標分類 根據無線傳感器網絡不同的應用，覆蓋需求通常不同。根據覆蓋目標不同，目前覆蓋算法可以分為面覆蓋、點覆蓋及柵欄覆蓋。 (1)面覆蓋 目標是在大量冗余節點中尋找能覆蓋同樣區域大小并保證網絡連

6、通的最小節點集合。 (2)點覆蓋 覆蓋一些離散的目標點，并使每一個目標點至少能被一個節點覆蓋。 (3)柵欄覆蓋 目標是找出連接出發位置和離開位置的路徑，使這樣的路徑能在不同模型定義下提供對目標的不同傳感質量。根據目標穿越網絡時所用的不同模型，柵欄覆蓋可以分為最壞與最佳情況覆蓋以及暴露覆蓋。 最壞情況是指考察所有路徑中不被傳感器節點檢測的概率最小情況； 最佳情況是指考察所有路徑中被傳感器節點檢測的概率最大情況；暴露穿越同時考慮了目標暴露的時間因素和傳感器節點對于目標的感應強度的因素，反映了運動目標穿越網路區域的時間增加而感應強度累加值增大的情況。4.經典覆蓋算法a.基于網格的覆蓋定位傳感器配置算

7、法考慮傳感器節點及目標點都采用網格形式配置，節點采用布爾覆蓋模型，并使用能量矢量來表示格點的覆蓋。如右圖，各格點都可至少被一個傳感器節點覆蓋，此時區域達到了完全覆蓋，例如格點位置8的能量矢量為（0,0,1,1,0,0）。當網絡資源受限無法達到格點完全覆蓋時，需要根據配置代價上限進行相關的節點布置。基于網格的覆蓋定位傳感器配置算法設計了一種模擬退火算法來最小化距離錯誤。首先假設每個格點都配置有傳感器，然后循環執行以下過程，試圖刪除一個傳感器節點，然后進行配置代價評價，如果評價不通過，就將該節點移到另外一個隨機選擇的位置，然后再進行配置代價評價。循環得到優化值同時保存新的配置節點情況。最后，改進算

8、法停止執行的準則。在達到模擬退火算法的冷卻溫度時，優化覆蓋識別的網絡配置方案也同時達到。b.分布式貪婪的連通傳感器覆蓋方法該算法屬于連通性覆蓋中的連通路徑覆蓋及確定性面點覆蓋類型。假設已選擇的傳感器節點集合為M,選擇與M有相交的傳感區域的節點稱為候選節點。集中式算法初始節點隨機選擇構成M之后，在所有從初始節點集合出發到候選節點的路徑中選擇一條可以覆蓋更多未覆蓋子區域的路徑。將該路徑經過的節點加入M，算法繼續執行到網絡查詢區域可以完全被更新后的M覆蓋。如圖所示為該貪婪算法執行的方式。在圖A中，貪婪算法會選擇路徑得到b，這是因為在所有備選路徑中，C3和C4組成的路經P2可以覆蓋更多子區域。c.輪換

9、活躍/休眠節點的覆蓋方法采用輪換活躍和休眠節點的覆蓋協議可以有效延長網絡生存時間，該協議屬于確定性和節能覆蓋協議采用節點輪換工作機制，每個周期由一個Self-Scheduling階段和一個Working階段組成。在第一個階段，各節點首先向傳感半徑內鄰居節點廣播通告消息，其中包括節點ID和位置。節點檢查自身傳感任務是否可以可由鄰居節點完成，可替代的節點返回一條狀態通告消息，之后進入休眠狀態，需要繼續工作的節點執行傳感任務。但是這種機制存在一個問題,如果鄰居節點同時檢查到自身的傳感任務可由對方完成，并同進入休眠狀態，就會出現下圖所示的盲點。節點e和f的整個傳感區域都可以被相鄰的鄰居節點代替覆蓋，但

10、如果e和f進入休眠狀態，就出現了不能檢測的陰影區域，即盲點。為了避免這種情況的發生，節點在第一個階段檢查之前執行一個退避機制。每一個節點在隨機產生的時間之后再檢查工作。為了進一步避免盲點的出現，每個節點在進入休眠狀態之前還將等待一定的時間來監聽鄰居節點的狀態更新。d.最壞情況覆蓋方法最壞情況覆蓋屬于確定性網絡路徑/目標覆蓋和柵欄覆蓋類型，算法考慮如何對穿越網絡的目標或其所在路徑上的各店進行感應與追蹤，體現了一種網絡覆蓋性質。這里我們定義最大突破路徑，分別使得路徑上的點到周圍傳感器的最小距離最大化。顯然，這條路徑代表了無線傳感器網絡最壞（不被檢測的概率最小）。文中分別采用計算幾何中的Vornoi

11、圖與Delaunay三角形來完成最大突破路徑的構造和查找。其中， Vornoi圖是由所有Delaunay三角形邊上的垂直平分線形成的，Delaunay三角形各頂點為網絡的傳感器節點，并滿足子三角形外接圓不包括其他節點，由于Vornoi圖中的線段具有到最近的傳感器節點距離最大的性質，因此最大突破路徑一定是由Vornoi圖中的線段組成。5.覆蓋性能評價指標假設無線傳感器網絡布置在二維平面空間內，由移動、固定兩種無線傳感器節點構成，各節點具有相同的測量范圍、測量可信度和通信半徑。固定節點采用隨機布置方式，通過全球定位系統獲取自身位置信息，并在網絡中發布共享。a.無線傳感器網絡的覆蓋指標由于節點布置的

12、固有冗余性，網絡覆蓋評價采用了可靠度的概念，對一定區域，若在t時刻處于n個節點測量范圍內，該區域綜合可靠度表示為待測區域中所有綜合可靠度大于測量可靠性要求的區域成為有效測量區域。將有效測量區域面積占待測總面積的比例定義為覆蓋指標C。b.無線傳感器網絡的能耗指標無線信號在傳播過程中隨著傳播距離增加而發生衰減，采用自由空間模型計算傳播損耗如下：式中，LP為路徑損耗，D為傳播距離。假設無線傳感器網絡通信能耗模型為：運行發送器或者接收器的無線花費為Eelec=50nj/b ，發送放大器容許放大倍率的無線花費為Eamp=100pj/b 。二維空間內，坐標分別為（xi,yi),xj,yj的無線傳感器節點i,j,通信時信號傳播距離計算如下：若節點i向節點j發送長度為kb的數據包，則節點i能耗為：節點j接收此數據包傳輸所消耗的能耗是所消耗的總能量是無線傳感器網絡的覆蓋能效優化可以擴大無線傳感器網絡的有效測量區域面積，從而提高網絡整體測量性能。節點通信范圍通常遠大于其感知范圍，且儲存能量有限，因此提高能效性成為無線傳感器網絡測量的關鍵。無線傳感器節點的通信能耗與測量和數據處理能耗相比高許多，通信能耗的優化對提高無線傳感器網絡能效十分重要。6.總結覆蓋問題是無線傳感器網絡配置首先面臨的基