張紅艷

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

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

張紅艷

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

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

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

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

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

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

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

1　　相關(guān)理論

1.1模型和算法

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

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

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

1.2計(jì)算幾何Voronoi圖和Delaunay三角

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

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

圖1　　離散點(diǎn)的Voronoi圖和Delaunay三角

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

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

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

2　　最大逼近突破路徑算法

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

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

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

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

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

2.2問題描述

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

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

2.3最大逼近突破路徑算法

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

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

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

圖2　　最大路徑查找算法

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

3　　實(shí)驗(yàn)結(jié)果

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

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

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

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

圖4　　第一組實(shí)驗(yàn)結(jié)果

圖5　　第二組實(shí)驗(yàn)結(jié)果

TP391

A

2095-7726（2016）12-0037-04

2016-07-10

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

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