張紅艷

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

無線傳感器網(wǎng)絡(luò)中的最大逼近突破路徑算法

張紅艷

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

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

無線傳感器網(wǎng)絡(luò)；感知覆蓋；最大逼近突破路徑；Voronoi圖

近些年，無線傳感器網(wǎng)絡(luò)技術(shù)被越來越多地使用，而且有望被應(yīng)用在如健康、軍事、家庭和環(huán)境監(jiān)測等更多領(lǐng)域中。無線傳感器網(wǎng)絡(luò)由一些微小的傳感器節(jié)點組成，每個節(jié)點都有感知環(huán)境的能力［1］，將這些節(jié)點部署在目標監(jiān)測領(lǐng)域中，就可以組成一個無線傳感器網(wǎng)絡(luò)。

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

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

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

1　　相關(guān)理論

1.1模型和算法

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

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

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

1.2計算幾何Voronoi圖和Delaunay三角

Voronoi圖是由一組離散的點定義的基本構(gòu)造。圖1a為二維平面上一組離散點的Voronoi圖，其中的離散點被劃分為一系列凸多邊形區(qū)域，每個多邊形內(nèi)的點都組成了相互間距離最近的一個網(wǎng)絡(luò)。

Delaunay三角與Voronoi圖直接相關(guān)，都是計算幾何領(lǐng)域的典型問題。圖1b顯示的是一組隨機放置的節(jié)點的Delaunay三角和對應(yīng)的Voronoi圖，其中虛線表示Delaunay三角，實線表示Voronoi圖。

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

1.3集中式與分布式實現(xiàn)方式

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

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

2　　最大逼近突破路徑算法

2.1選擇節(jié)點部署模型

根據(jù)傳感器網(wǎng)絡(luò)中節(jié)點分布的不同，可以將傳感器網(wǎng)絡(luò)的覆蓋問題分為兩大類：確定性覆蓋和隨機性覆蓋。

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

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

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

2.2問題描述

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

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

2.3最大逼近突破路徑算法

給Voronoi圖的每一條邊都賦予一個權(quán)重值，用來表示它與相鄰節(jié)點間的最小距離。構(gòu)建一個無向圖T，其中的每個節(jié)點和每條邊都對應(yīng)Voronoi圖中的一個頂點和一個線段。

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

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

圖2　　最大路徑查找算法

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

3　　實驗結(jié)果

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

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

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

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

圖4　　第一組實驗結(jié)果

圖5　　第二組實驗結(jié)果

TP391

A

2095-7726（2016）12-0037-04

2016-07-10

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

張紅艷（1986-），女，安徽合肥人，碩士，研究方向：無線傳感器網(wǎng)絡(luò)技術(shù)及其應(yīng)用。