無線傳感器網絡中的最大逼近突破路徑算法

張紅艷

（安徽建筑大學 電子與信息工程學院，安徽 合肥230601）

無線傳感器網絡中的最大逼近突破路徑算法

張紅艷

（安徽建筑大學 電子與信息工程學院，安徽 合肥230601）

在無線傳感器網絡中，感知覆蓋的服務質量最重要的指標是感知覆蓋區域和整個監測區域的比率。為此，提出一種解決覆蓋問題的方法：首先引用覆蓋問題(包括確定性覆蓋和隨機性覆蓋)的概念，接著定義最大逼近突破路徑的概念，然后利用Voronoi理論解決溫度檢測過程中的最大逼近突破路徑問題，最后用實驗仿真結果評估所提出算法的性能并討論其在傳感器網絡覆蓋領域的發展方向。

無線傳感器網絡；感知覆蓋；最大逼近突破路徑；Voronoi圖

近些年，無線傳感器網絡技術被越來越多地使用，而且有望被應用在如健康、軍事、家庭和環境監測等更多領域中。無線傳感器網絡由一些微小的傳感器節點組成，每個節點都有感知環境的能力［1］，將這些節點部署在目標監測領域中，就可以組成一個無線傳感器網絡。

無線傳感器網絡中節點的部署、追蹤以及覆蓋問題是根本性問題，而感知覆蓋和感知連通性則是兩個基本問題［1-2］。其中，感知覆蓋問題的研究已經應用到許多領域中，如在藝術畫廊問題［3］中，要準確知道觀看者的人數和位置，傳感器就要覆蓋整個畫廊。

雖然許多研究者對無線傳感器網絡覆蓋的問題都做過研究，但應用計算幾何和Voronoi圖來解決問題的卻比較少。Meguerdichian等解決了特定傳感器網絡中針對服務質量的覆蓋問題［4-5］：他們用多項式時間集中式算法來解決最壞覆蓋的問題，而在解決最佳覆蓋的問題時，研究空間定義成相對鄰域圖。該算法具有一些優勢，如：（1）對最佳和最壞的情況分別采取了兩種措施，得到了網絡路徑的關鍵規劃結果，可指導網絡節點的部署，提高網絡的覆蓋率；（2）適用于解決規劃網絡路徑、觀察物體以及其他許多方面的問題。但它也有如下缺點：（1）這是一種集中式的計算方法，故需要事先知道每個節點的位置信息；（2）算法不考慮實際的障礙、環境噪聲等因素；（3）網絡節點是同構的，不適用于實現具有不同覆蓋能力節點的網絡。因此，Meguerdichian等設傳感器的感知能力隨著距離的增加而減小，并據此提出了基于曝光的模型［6］。

在本文中，筆者描述了這樣一個無線傳感器網絡：使用概率傳感模型，由溫度傳感器檢測室內溫度，這里假設傳感器的感知能力與距離成反比。

1　　相關理論

1.1模型和算法

（1）傳感器網絡概率感知模型。網絡由分布在空間的自主式傳感器節點組成，這些節點協同監測環境信息，如溫度、聲音、震動和壓力等，每個節點都裝有無線通信設備、微型控制器和電源（通常是電池）。網絡成本取決于網絡的規模和單個傳感器節點的復雜程度，而這種成本約束會導致通信受到如能量、內存、運算速度和帶寬等因素的限制。

概率感知模型［7］假設目標被檢測到的概率和目標到傳感器之間的距離呈指數關系，即Pij=e-ad（i,j），其中，d是目標與傳感器之間距離，a表示傳感器檢測到目標的概率隨距離減小的速度。

（2）傳感器定位算法。本文使用歐式算法來確定節點位置，這種算法的優點是在特定條件下可以達到很高的精度，而且節點位置確定之后無需再修正。文中假設節點有接收信號強度（RSSI）測距能力，單個節點可以根據RSSI模型獲得相鄰節點與其自身之間的距離。

1.2計算幾何Voronoi圖和Delaunay三角

Voronoi圖是由一組離散的點定義的基本構造。圖1a為二維平面上一組離散點的Voronoi圖，其中的離散點被劃分為一系列凸多邊形區域，每個多邊形內的點都組成了相互間距離最近的一個網絡。

Delaunay三角與Voronoi圖直接相關，都是計算幾何領域的典型問題。圖1b顯示的是一組隨機放置的節點的Delaunay三角和對應的Voronoi圖，其中虛線表示Delaunay三角，實線表示Voronoi圖。

圖1　　離散點的Voronoi圖和Delaunay三角

1.3集中式與分布式實現方式

集中式計算是將所需信息發送到中央節點（如服務器）的一種計算方法，而分布式計算則依賴于節點之間的信息交換和節點位置坐標。

集中式計算的優點是全局規劃，這使計算和存儲能力方面不會受到過多限制，而且很容易得到相對準確的位置估計，不過，它會使靠近中心位置的節點由于通信開銷過大而過早地消耗完電能，從而引起網絡與中心節點之間的通信中斷，無法實現實時定位。可見，分布式算法比集中式算法更具優勢，特別是在降低通信成本方面，而設計無線網絡的一個關鍵問題就是節約能源，因此，本文選擇了分布式算法來實現無線傳感器網絡。

2　　最大逼近突破路徑算法

2.1選擇節點部署模型

根據傳感器網絡中節點分布的不同，可以將傳感器網絡的覆蓋問題分為兩大類：確定性覆蓋和隨機性覆蓋。

確定性覆蓋指的是傳感器網絡相對穩定或傳感器網絡是預設的特定形狀，在節點位置已知的條件下完成覆蓋目標區域或目標點的任務，關于3D藝術畫廊的問題就是確定性覆蓋問題的案例［3］。不過，在許多情況下，確定性部署都是不可行的，需要選擇隨機部署傳感器的方法。

在目標監測應用中，移動目標沿任意路徑通過部署區域時被檢測到或不被檢測到的概率屬于柵欄覆蓋問題。這種覆蓋問題就是要最大限度地減小目標穿過檢測區而未被發現的概率。

本文需要在某區域內使用溫度傳感器構成的網絡中找到一個最大逼近突破路徑，即穿過該區域而未被檢測到的路徑。在區域內隨機部署傳感器的同時還提出了一種分布式計算方法，即利用Voro n o i圖和D elau n ay三角的特性去解決最大逼近突破路徑的問題。

2.2問題描述

已知：在一個給定的目標區域A內，有一組傳感器S，每個傳感器節點Si的位置都可以通過位置算法得出，位置I和F是根據任務確定的，可以定義在傳感區域的內部或外部。

問題：在區域A內找出始于I終于F的最大逼近突破路徑PA。PA上任一點都具有從該點到與其最近傳感器的距離是最大的屬性。

2.3最大逼近突破路徑算法

給Voronoi圖的每一條邊都賦予一個權重值，用來表示它與相鄰節點間的最小距離。構建一個無向圖T，其中的每個節點和每條邊都對應Voronoi圖中的一個頂點和一個線段。

最大路徑查找算法如圖2所示。在圖2中，矩陣P用來存儲最大路徑的結果，矩陣D用來存儲最大路徑的權重。WUG是加權無向圖，其中的元素是從某一節點到對應Voronoi圖的邊的垂直平分線之間的距離。在一次循環搜索過程中，設v和w均為Voronoi圖中的頂點，I0為起點，V為終點。若P（v,w）=true，表明w是從I0到V中間所獲得的頂點；如果Final（v）=true，那就是得到了從I0到V的最大路徑。

在搜索過程結束后，可以找到一條從起點I到終點F的路徑，這個路徑就是最大逼近突破路徑。圖3是最大逼近突破算法，它調用了圖2所描述的算法。

圖2　　最大路徑查找算法

圖3　　最大逼近突破路徑算法

3　　實驗結果

實驗采用Matlab來仿真算法，所有傳感器節點的感知范圍都使用相同半徑的圓形區域來表示。為了使查找算法找到比較合理的最大逼近突破路徑，假設起點I所在邊的權值為0，終點F所在邊的權值為所有權值中最大的值。

第一組實驗對象是在2維歐幾里得空間內給定的30個點，并且在相應的Voronoi圖中不考慮權值。圖4a所示為30個給定點的Voronoi圖、Delaunay三角圖以及最大逼近突破路徑，其中粗線即為最大逼近突破路徑。圖4b為對應圖4a中傳感器節點的圓形感知區域。

第二組實驗對象同樣是在2維歐幾里得空間內給定的30個點，但是在相應的Voronoi圖中賦予權值。圖5a所示為30個給定點的Voronoi圖、Delaunay三角圖以及最大逼近突破路徑，其中粗線即為最大逼近突破路徑。圖5b為對應圖5a中傳感器節點的圓形感知區域。

通過對比圖4b和圖5b可以看出，第二組實驗的結果要優于第一組實驗。在已知傳感器感知半徑的前提下，圖5b顯示的從起點I到終點F的最大逼近突破路徑基本是在傳感器感知半徑范圍之外的，圖4b顯示的最大逼近突破路徑有一部分是穿過傳感器感知范圍的，也就是說，選用第一組實驗最大逼近突破路徑穿過檢測區被檢測到的概率要比第二組大。

圖4　　第一組實驗結果

圖5　　第二組實驗結果

TP391

A

2095-7726（2016）12-0037-04

2016-07-10

安徽省教育廳自然科學項目（KJ2016A821），安徽建筑大學青年科研基金項目（2016XQZ12）

張紅艷（1986-），女，安徽合肥人，碩士，研究方向：無線傳感器網絡技術及其應用。