基于地形修正的無(wú)線傳感器網(wǎng)絡(luò)陷阱空洞檢測(cè)

劉 曄,傅忠謙

(中國(guó)科技大學(xué)信息科學(xué)技術(shù)學(xué)院,合肥 230027)

?

基于地形修正的無(wú)線傳感器網(wǎng)絡(luò)陷阱空洞檢測(cè)

劉 曄,傅忠謙*

(中國(guó)科技大學(xué)信息科學(xué)技術(shù)學(xué)院,合肥 230027)

無(wú)線傳感器網(wǎng)絡(luò)中覆蓋空洞大小的識(shí)別直接影響陷阱空洞的判斷。現(xiàn)有陷阱空洞檢測(cè)算法均基于理想圓盤(pán)覆蓋模型,在起伏地形條件下不能準(zhǔn)確識(shí)別空洞實(shí)際大小,導(dǎo)致算法失效。本文針對(duì)丘陵地形特點(diǎn),提出一種基于數(shù)字高程地圖坡度信息的地形修正方法,通過(guò)構(gòu)建傳感器節(jié)點(diǎn)方向梯度感知模型,實(shí)現(xiàn)起伏地形下的陷阱空洞檢測(cè)。在此基礎(chǔ)上,進(jìn)一步研究了節(jié)點(diǎn)間距、坡度和坡向?qū)ο葳蹇斩礄z測(cè)結(jié)果的影響規(guī)律,找到一種根據(jù)地形確定節(jié)點(diǎn)部署間距的近似計(jì)算方法。通過(guò)仿真實(shí)驗(yàn),驗(yàn)證了本文方法的有效性,并得出了在保證陷阱空洞的發(fā)生概率低于5%時(shí)的節(jié)點(diǎn)間距取值。該結(jié)果為在起伏地形下部署傳感器網(wǎng)絡(luò)提供了參考。

無(wú)線傳感器網(wǎng)絡(luò);陷阱空洞;起伏地形;坡度

覆蓋性能是衡量無(wú)線傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量的關(guān)鍵指標(biāo),不斷改進(jìn)和提高覆蓋性能成為近年來(lái)研究的主要課題[1-3],覆蓋空洞的修復(fù)是其中的一個(gè)重要研究?jī)?nèi)容。覆蓋空洞指區(qū)域內(nèi)未被任何一個(gè)傳感器監(jiān)測(cè)范圍覆蓋的點(diǎn)的集合?？斩葱迯?fù)就是通過(guò)移動(dòng)、喚醒現(xiàn)有節(jié)點(diǎn)或者增加新節(jié)點(diǎn)等方式使空洞區(qū)域被傳感器監(jiān)測(cè)范圍所覆蓋。然而,修復(fù)空洞達(dá)到全覆蓋,有時(shí)不僅受到實(shí)際條件限制無(wú)法完成,而且也是不必要的[4],因此允許空洞存在的“陷阱覆蓋”方式被提出和研究[5]:監(jiān)測(cè)區(qū)域中的任一覆蓋空洞的直徑不超過(guò)某一閾值D,則稱傳感器網(wǎng)絡(luò)可以對(duì)這個(gè)區(qū)域提供D-陷阱覆蓋?？斩粗睆绞窃摽斩磪^(qū)域中兩點(diǎn)間歐氏距離中的最大值,直徑大于D的覆蓋空洞為陷阱空洞。

目前針對(duì)陷阱空洞的相關(guān)算法研究相對(duì)較少,文獻(xiàn)[6]利用圖論技術(shù)調(diào)整空洞直徑達(dá)到陷阱覆蓋要求,此方法會(huì)引起網(wǎng)絡(luò)拓?fù)涞妮^大變化。文獻(xiàn)[7]在全覆蓋網(wǎng)絡(luò)基礎(chǔ)上進(jìn)行優(yōu)化形成陷阱覆蓋,適用于節(jié)點(diǎn)密度和冗余較大的網(wǎng)絡(luò)。文獻(xiàn)[8]采用的空洞檢測(cè)方法基于最大復(fù)形子網(wǎng),在節(jié)點(diǎn)探測(cè)半徑和通信半徑存在特定關(guān)系時(shí),可用于檢測(cè)一定闕值的陷阱空洞。文獻(xiàn)[9]中提出基于有效弧檢測(cè)的陷阱空洞檢測(cè)方法(THDA算法),通過(guò)計(jì)算邊界弧段查找陷阱空洞,但是起伏地形條件下的弧段描述和計(jì)算較復(fù)雜,不便于應(yīng)用。而且,這些研究均是基于圓盤(pán)覆蓋模型,而起伏的地形條件會(huì)影響節(jié)點(diǎn)實(shí)際探測(cè)距離,因此圓周覆蓋模型并不能真實(shí)反映實(shí)際地形條件下的節(jié)點(diǎn)覆蓋范圍。由于陷阱空洞的判斷依賴空洞大小的精確計(jì)算,一旦節(jié)點(diǎn)覆蓋范圍不規(guī)則,算法因不能準(zhǔn)確獲取空洞大小而失效,所以需要對(duì)陷阱空洞檢測(cè)算法進(jìn)行地形修正。

地形修正方法在無(wú)線傳感器網(wǎng)絡(luò)中已有應(yīng)用,文獻(xiàn)[10]在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署中考慮大地圓的影響,用球面距離代替直線距離,但大地圓與地形起伏相比還是比較簡(jiǎn)單。文獻(xiàn)[11-12]研究了利用三維定位算法解決在起伏地形下的無(wú)線傳感器網(wǎng)絡(luò)問(wèn)題,用三維計(jì)算替代二維計(jì)算能有效反映網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),但是三維空間計(jì)算的運(yùn)算量大,算法相對(duì)復(fù)雜,尤其是三維空洞大小的計(jì)算非常復(fù)雜,也不便于解決陷阱覆蓋問(wèn)題。本文引入目前常用的數(shù)字高程模型(DEM)坡度、坡向數(shù)據(jù),針對(duì)丘陵地形特點(diǎn),通過(guò)構(gòu)建傳感器節(jié)點(diǎn)方向梯度感知模型,對(duì)一種基于邊界端點(diǎn)計(jì)算的陷阱空洞檢測(cè)算法進(jìn)行地形修正,實(shí)現(xiàn)起伏地形下的陷阱空洞檢測(cè)。并在此基礎(chǔ)上,進(jìn)一步研究了地形坡度、坡向和節(jié)點(diǎn)間距對(duì)陷阱空洞檢測(cè)結(jié)果的影響,通過(guò)仿真實(shí)驗(yàn)找到根據(jù)地形條件確定節(jié)點(diǎn)部署間距的近似方法,為實(shí)際地形條件下部署傳感器網(wǎng)絡(luò)提供參考。

1 陷阱空洞檢測(cè)算法的地形修正

傳感器網(wǎng)絡(luò)部署區(qū)域的地形起伏變化,對(duì)傳感器節(jié)點(diǎn)實(shí)際探測(cè)效果產(chǎn)生的影響主要表現(xiàn)在兩個(gè)方面:地形起伏和地物地貌。地形起伏影響傳感器實(shí)際探測(cè)范圍的外形,在不同方向上可能造成實(shí)際探測(cè)距離的縮小,從而導(dǎo)致各向異性;而地物地貌影響傳感器地點(diǎn)的選擇,水洼、植被的存在會(huì)導(dǎo)致某些位置并不能實(shí)際部署傳感器節(jié)點(diǎn)。

1.1 陷阱空洞算法描述

為了研究地形起伏對(duì)傳感器網(wǎng)絡(luò)陷阱空洞檢測(cè)算法的影響,選取一種適合起伏地形條件下應(yīng)用的陷阱空洞算法。由于依賴弧段檢測(cè)的方法在實(shí)際地形條件下應(yīng)用困難,因此,采用一種基于空洞邊界端點(diǎn)計(jì)算的陷阱空洞檢測(cè)算法,描述如下:①以傳感器節(jié)點(diǎn)為頂點(diǎn)對(duì)監(jiān)測(cè)區(qū)域進(jìn)行delaunay三角形[13-14]劃分,如圖1(a)所示;②計(jì)算相鄰節(jié)點(diǎn)覆蓋范圍邊界的交點(diǎn)坐標(biāo),根據(jù)該交點(diǎn)是否被其他節(jié)點(diǎn)檢測(cè)到,判斷這對(duì)相鄰節(jié)點(diǎn)的連線是否為空洞邊界,如圖1(a),點(diǎn)P不被Si、Sj之外的節(jié)點(diǎn)所覆蓋,則SiSj為空洞邊界,P為空洞的一個(gè)邊界端點(diǎn);③根據(jù)②的結(jié)果對(duì)三角形網(wǎng)進(jìn)行聚類(lèi),去掉不是空洞邊界的三角形邊,形成多邊形網(wǎng)。如圖1(b),根據(jù)區(qū)域內(nèi)是否存在一個(gè)邊界端點(diǎn)P,判斷其是連通區(qū)域(Ⅰ區(qū)域)還是空洞(Ⅱ區(qū)域),從而找到空洞的邊界節(jié)點(diǎn)鏈。④對(duì)找出的空洞,根據(jù)②得到的邊界端點(diǎn)坐標(biāo),計(jì)算兩兩之間的最大距離,按照陷阱空洞的定義判斷其是否陷阱空洞。

圖1 陷阱空洞檢測(cè)算法示意圖

1.2 方向梯度感知模型

如無(wú)特殊申明,本文均基于以下假設(shè):①傳感器節(jié)點(diǎn)的探測(cè)能力各向同性,理想探測(cè)半徑為r;②為了接近實(shí)際應(yīng)用,本文中坐標(biāo)如未特別說(shuō)明,均指大地坐標(biāo);③不考慮地形曲面的影響造成的衍射變化。

在地學(xué)研究中,用坡度描述地表單元陡緩的程度。通常把坡面的垂直高度h和水平距離l的比叫做坡度(或坡比),用字母i表示,坡向是斜坡面對(duì)的方向,亦即高程下降最快的方向[15]。

如圖2所示,該地形的坡度i為:

i=h/l=tanθ

(1)

其中,θ為坡面與水平面的夾角。

圖2 坡度概念與方向梯度感知模型示意圖

為了區(qū)別,本文把沿坡面上任一方向上高程變化的程度稱為沿該方向上的方向梯度,用g表示。由數(shù)學(xué)中方向?qū)?shù)的計(jì)算方法可知,坡面上點(diǎn)P(x0,y0)處沿ωp方向的方向梯度g為:

(2)

其中,ωp為方向角,h(x,y)為坐標(biāo)(x,y)處的高程,通過(guò)GIS軟件可以方便地從DEM地圖數(shù)據(jù)中提取高程數(shù)據(jù)和坡度信息。顯然,當(dāng)ωp方向與該點(diǎn)的坡向方向一致時(shí),方向梯度等于坡度,即在坡向上的方向梯度等于坡度。

下面基于坡度和方向梯度這兩個(gè)概念,求解起伏地形下的傳感器節(jié)點(diǎn)沿任意方向的實(shí)際感知距離。為了方便計(jì)算,以坡向?yàn)槠鹗挤较?并按順時(shí)針?lè)较蚨攘?將任一方向與坡向的夾角ω作為該方向的方向角。

我國(guó)南方多為丘陵地形,這種地形起伏變化平緩,適宜部署無(wú)線傳感器監(jiān)控網(wǎng)絡(luò)。丘陵地形的特點(diǎn)是二階坡面因子坡度變率和坡向變率較小,對(duì)于每個(gè)節(jié)點(diǎn),在其探測(cè)范圍內(nèi),可近似看成理想坡面,即范圍內(nèi)各點(diǎn)的坡度和坡向一致。如圖2所示,在這樣的近似下,沿ω方向上的方向梯度[15]g為:

g=tanβ

(3)

其中,β稱為沿ω方向的方向梯度角。由式(1)、式(3),可知:

g=icosω

(4)

節(jié)點(diǎn)沿ω方向的實(shí)際探測(cè)半徑r′受到地形影響,與理想探測(cè)半徑r存在關(guān)系:

r′=rcosβ

(5)

將式(3)、式(4)代入式(5),得:

r′=rcos(arctan(g))=rcos(arctan(icosω))

(6)

特別的,當(dāng)ω=0時(shí),β=θ,則r′=rcosθ。

令A(yù)=cos(arctan(icosω)),式(6)表示為:

r′=rA

(7)

這表明平面距離和坡面距離的轉(zhuǎn)換關(guān)系,A為轉(zhuǎn)換因子,且0

同時(shí),受地物地貌因素影響,某些位置即使理論計(jì)算結(jié)果很好,也不能在此部署節(jié)點(diǎn)。因此,增加二值部署可行性因子p,在不適合部署節(jié)點(diǎn)的位置值為0,否則為1。

因此,得到傳感器節(jié)點(diǎn)在ω方向上的實(shí)際探測(cè)半徑r′的計(jì)算公式如下:

r′=prcos[arctan(icosω)]

(8)

1.3 陷阱空洞檢測(cè)算法實(shí)現(xiàn)

傳感器節(jié)點(diǎn)圓周覆蓋模型修改為方向梯度模型,陷阱空洞檢測(cè)算法進(jìn)行相應(yīng)修正,主要有以下兩個(gè)方面:

①相鄰節(jié)點(diǎn)覆蓋邊界的交點(diǎn)

由1.2的丘陵地形特點(diǎn)分析,可近似認(rèn)為相鄰節(jié)點(diǎn)的覆蓋范圍平面在同一個(gè)切空間內(nèi)[16],即節(jié)點(diǎn)相鄰節(jié)點(diǎn)的覆蓋圓近似在同一個(gè)切平面上,因此,無(wú)論整體地形變化多大,在考慮相鄰節(jié)點(diǎn)間的相關(guān)計(jì)算時(shí),均可近似按照平面處理。對(duì)于節(jié)點(diǎn)Si、Sj,其公共切平面的坡度取Si、Sj兩點(diǎn)的坡度平均值,坡向取Si、Sj兩點(diǎn)的坡向夾角的角平分線方向。如圖3所示,Si、Sj兩點(diǎn)大地坐標(biāo)為(xi,yi)、(xj,yj),Si、Sj公共的切平面坡度為i,則:

(9)

圖3 山坡地形交點(diǎn)和距離計(jì)算示意圖

(10)

其中,A為轉(zhuǎn)換因子,由(7)定義。

在加入地形因素前,Si、Sj兩節(jié)點(diǎn)覆蓋范圍交點(diǎn)P的計(jì)算式為:

(11)

將式(11)代入式(10),得到交點(diǎn)P的坡面坐標(biāo)(x′,y′),將其映射回大地坐標(biāo)系得到P的大地坐標(biāo)(x,y):

(12)

②點(diǎn)是否被傳感器節(jié)點(diǎn)感測(cè)范圍所覆蓋的判斷

理想圓盤(pán)覆蓋模型中,根據(jù)點(diǎn)到傳感器節(jié)點(diǎn)位置的距離是否小于r來(lái)判斷該點(diǎn)是否被這個(gè)傳感器節(jié)點(diǎn)所覆蓋,而受地形坡度影響,用實(shí)際探測(cè)半徑r′替換r。如圖3所示,為判斷Sj是否被Si探測(cè)范圍所覆蓋,先求SiSj的水平投影方向上的方向角ω:

(13)

代入式(6)求出Si在SiSj的水平投影方向上的實(shí)際探測(cè)半徑r′,以此判斷Sj是否在Si的探測(cè)范圍內(nèi)。

2 地形修正的影響及仿真分析

引入方向梯度感知模型對(duì)陷阱空洞檢測(cè)算法進(jìn)行地形修正后,節(jié)點(diǎn)實(shí)際探測(cè)距離縮小且各向異性。為研究對(duì)檢測(cè)結(jié)果的影響,進(jìn)行實(shí)驗(yàn)仿真。本文仿真均是基于MATLAB 2012仿真平臺(tái),在處理器為Intel Core i3-2330M 2.2 GHz、內(nèi)存2 GB的計(jì)算機(jī)環(huán)境下運(yùn)行。

2.1 地形修正前后檢測(cè)結(jié)果比較

在50 m×50 m的區(qū)域內(nèi),部署傳感器節(jié)點(diǎn)數(shù)目N=40,節(jié)點(diǎn)的理想探測(cè)半徑r=6 m,陷阱空洞闕值dmax=2r=12 m,進(jìn)行陷阱空洞檢測(cè)算法仿真。

①?gòu)木W(wǎng)上下載的SRTM DATA VERSION 4.1地圖數(shù)據(jù)我國(guó)東南部(緯度25 N～30 N,經(jīng)度115°～120°E)地圖中隨機(jī)選取大小為50 m×50 m的方格為例,如圖4所示,其中,圖4(a)為三維地形圖,圖4(b)為等高線地形圖。

圖4 仿真區(qū)域地形示意圖

圖5 地形修正的陷阱空洞檢測(cè)示意圖

②隨機(jī)產(chǎn)生傳感器節(jié)點(diǎn)部署圖,如圖5(a)所示。圖中圓形表示傳感器節(jié)點(diǎn)的覆蓋范圍。

分別在是否加入地形修正的情況下進(jìn)行仿真,結(jié)果如圖5(b)、(c)、(d)所示。其中,圖5(b)、(c)分別為加入地形修正前、后陷阱空洞檢測(cè)情況,圖中粗線表示檢測(cè)過(guò)程中的封閉多邊形邊界;圖5(d)為檢測(cè)結(jié)果比較圖,圖中實(shí)線表示加入地形修正前檢測(cè)出的陷阱空洞外形,虛線表示加入地形修正后檢測(cè)出的陷阱空洞外形的增加部分。通過(guò)比較可以看出:

①原有陷阱空洞直徑增加。修正前后雖然均能檢測(cè)出陷阱空洞Ⅰ、Ⅱ,但直徑大小并不相同。修正后檢測(cè)到的空洞范圍增加了一部分,直徑變大,如圖3(d)中A、B所示。

②產(chǎn)生新的陷阱空洞。陷阱空洞Ⅲ在修正前的空洞檢測(cè)過(guò)程中由于直徑較小并不是陷阱空洞,修正后直徑超過(guò)陷阱空洞闕值,成為新的陷阱空洞。

2.2 坡度、坡向及節(jié)點(diǎn)間距的影響

地形修正改變了節(jié)點(diǎn)間的相鄰關(guān)系。通常將覆蓋范圍相交的傳感器節(jié)點(diǎn),即節(jié)點(diǎn)間的距離d與節(jié)點(diǎn)探測(cè)半徑滿足:

d≤2r

(14)

稱為相鄰節(jié)點(diǎn)。加入地形修正后,由式(6)知相鄰節(jié)點(diǎn)需要滿足的條件轉(zhuǎn)變?yōu)?

d≤2r′=2rA=2rcos[arctan(icosω)]=f(i,ω)

(15)

式中,若i一定,f(i,w)在ω=kπ時(shí)取得最小值。因此,在坡度為i的坡面上等間距部署的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn),節(jié)點(diǎn)間距d應(yīng)滿足的必要條件為:

d≤2rcos(arctani)

(16)

實(shí)際應(yīng)用中對(duì)于人員不便進(jìn)入的野外環(huán)境隨機(jī)部署傳感器節(jié)點(diǎn)通常采取空投方式進(jìn)行,而空投布撒的節(jié)點(diǎn)實(shí)際落點(diǎn)往往具有隨機(jī)性,一般認(rèn)為服從以理想落點(diǎn)為中心的二維正態(tài)分布。這種隨機(jī)性增加了出現(xiàn)覆蓋空洞的可能性。為了抵消這個(gè)影響,加入修正因子k(0

d≤2krcos(arctani)

(17)

如果當(dāng)k取某值時(shí),使得按均勻間距d空投布撒,單位面積區(qū)域內(nèi)出現(xiàn)陷阱空洞的概率pt小于某個(gè)百分比p,則認(rèn)為符合要求。下面通過(guò)仿真實(shí)驗(yàn)進(jìn)行研究,找出合適的k值。

假設(shè)傳感器節(jié)點(diǎn)探測(cè)半徑r=6 m,按照間距d0=10 m均勻部署40個(gè)節(jié)點(diǎn),陷阱空洞的闕值仍為dmax=2r=12 m,考慮落點(diǎn)的隨機(jī)性,其分布規(guī)律按照標(biāo)準(zhǔn)正態(tài)分布計(jì)算,對(duì)陷阱空洞檢測(cè)算法進(jìn)行仿真,結(jié)果如下:

①在無(wú)起伏的理想平面上,進(jìn)行100次仿真實(shí)驗(yàn),出現(xiàn)陷阱空洞的次數(shù)為2次。

②在坡向一致、坡度均為i的山坡地形下,是否會(huì)出現(xiàn)陷阱空洞,與坡度i的大小以及空投方向與坡向的夾角有關(guān)。地學(xué)研究中,通常以坡度25°即46.6%為界,將丘陵按坡度陡峻程度分為陡丘陵和緩丘陵,故在不同區(qū)間內(nèi)取3種具有代表性的坡度值,進(jìn)行100次實(shí)驗(yàn),結(jié)果如表1。

表1 空投間距為10 m時(shí)出現(xiàn)陷阱空洞次數(shù)

結(jié)果表明,加入地形修正后,陷阱空洞出現(xiàn)概率大幅度提高,驗(yàn)證了地形因素對(duì)陷阱空洞檢測(cè)的顯著影響。并且在相同空投間距下,坡度越大,空投方向與坡向方向越不一致,出現(xiàn)陷阱空洞的可能性也越大。

③以坡度46.6為例,間隔0.05取不同k值,按式(16)計(jì)算相應(yīng)d值,在不同空投方向下重復(fù)100次實(shí)驗(yàn),結(jié)果如表2。

表2 坡度46.6時(shí)不同空投間距下出現(xiàn)陷阱空洞的次數(shù)

可見(jiàn),若取p=5%,當(dāng)k=0.8時(shí),出現(xiàn)陷阱空洞的概率pt低于p,明顯改善了網(wǎng)絡(luò)覆蓋性能,滿足要求。且k值越小,pt越小。

為驗(yàn)證之,將k=0.8代入其他坡度情況,即

d≤1.6rcos(arctani)

(18)

在不同的坡度和空投方向下,各重復(fù)100次仿真實(shí)驗(yàn),結(jié)果如表3。

表3 按k=0.8調(diào)整間距出現(xiàn)陷阱空洞的次數(shù)

如表3所示,當(dāng)k=0.8時(shí),在不同的坡度條件和空投方向下,出現(xiàn)陷阱空洞的概率pt均低于p,滿足要求。因此,k=0.8是通過(guò)實(shí)驗(yàn)仿真得到的較為理想的取值。

3 結(jié)論

本文結(jié)合丘陵地形實(shí)際特點(diǎn),建立了節(jié)點(diǎn)方向梯度感知模型,實(shí)現(xiàn)了起伏地形下的陷阱空洞檢測(cè)。仿真實(shí)驗(yàn)驗(yàn)證了方法的有效性,同時(shí)也反映了地形因素對(duì)陷阱空洞檢測(cè)的影響非常明顯,證明了地形修正的必要性。實(shí)驗(yàn)得出了按照式(18)調(diào)整節(jié)點(diǎn)間距能有效降低出現(xiàn)陷阱空洞的可能,當(dāng)k=0.8時(shí),可將出現(xiàn)陷阱空洞的概率控制在5%以內(nèi)。該結(jié)果適用于坡度變化平緩的起伏地形,為在這種地形條件下隨機(jī)部署傳感器網(wǎng)絡(luò)提供了有益的參考。下步可考慮坡度變化較大、更加復(fù)雜的地形條件下的模型修改,對(duì)于節(jié)點(diǎn)探測(cè)范圍內(nèi)不能近似作為理想坡面處理的地形,用曲面代替平面進(jìn)行兩點(diǎn)距離計(jì)算,提高檢測(cè)算法的準(zhǔn)確性,增強(qiáng)其對(duì)復(fù)雜地形的適用能力。

[1] Jia J,Chen J,Chang G,et al.Energy Efficient Coverage Control in Wireless Sensor Networks Based on Multi-Objective Genetic Algorithm[J].Computers and Mathematics with Applications,2009,57(11):1756-1766.

[2]Younis M,Akkaya K.Strategies and Techniques for Node Placement in Wireless Sensor Networks:A Survey[J].Ad Hoc Networks,2008,6(4):621-655.

[3]Yao J,Zhang G,Kanno J,et al.Decentralized Detection and Patching of Coverage Holes in Wireless Sensor Networks[C]//SPIE Defense,Security,and Sensing.International Society for Optics and Photonics,2009:73520V-73520V-10.

[4]Liu Y,Liang W.Approximate Coverage in Wireless Sensor Networks[C]//Local Computer Networks,2005.30th Anniversary.The IEEE Conference on IEEE,2005:68-75.

[5]Balister P,Zheng Z,Kumar S,et al.Trap Coverage:Allowing Coverage Holes of Bounded Diameter in Wireless Sensor Networks[C]//Infocom 2009,IEEE.IEEE,2009:136-144.

[6]Dogruel M,Ozgunzer U.Distributed Coverage in Wirelessad Hoc and Sensor Networks by Topological Graphapproaches[C]//Proc of IEEE Int Conf on ICDCS.Genova:IEEE Press,2010:106-115.

[7]Li J,Chen J,He S,et al.On Energy-Efficient Trap Coverage in Wireless Sensor Networks[C]//Real-Time Systems Symposium(RTSS),2011 IEEE 32nd.IEEE,2011:139-148.

[8]胥楚貴,鄧曉衡,鄒豪杰.無(wú)線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)策略[J].傳感技術(shù)學(xué)報(bào),2010,23(2):256-259.

[9]王力立,吳曉蓓.傳感器網(wǎng)絡(luò)中陷阱空洞的分布式檢測(cè)及修復(fù)[J].控制與決策,2012,27(12):1810-1815.

[10]Pescaru D,Curiac D I.Anchor Node Localization for Wireless Sensor Networks Using Video and Compass Information Fusion[J].Sensors,2014,14(3):4211-4224.

[11]夏明,毛科技,何文秀,等.基于空間角度傳遞的多跳AOA三維定位算法研究與在地形建模上的應(yīng)用[J].傳感技術(shù)學(xué)報(bào),2012,25(5):651-658.

[12]胡中棟,曾珽,肖紅.基于地形改正的無(wú)線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感器與微系統(tǒng),2013,32(6):147-149.

[13]武曉波,王世新,肖春生.Delaunay三角網(wǎng)的生成算法研究[J].測(cè)繪學(xué)報(bào),1999,28(1):28-35.

[14]Tsai V J D.Delaunay Triangulations in TIN Creation:An Overview and a Linear-Time Algorithm[J].International Journal of Geographical Information Science,1993,7(6):501-524.

[15]劉學(xué)軍,任志峰,王彥芳,等.基于DEM的任意方向坡度計(jì)算方法[J].地域研究與開(kāi)發(fā),2009,28(4):139-141.

[16]曹文明,王瑞.傳感器網(wǎng)絡(luò)覆蓋定位模糊信息處理方法[M].北京:電子工業(yè)出版社2010:113-115

劉曄(1982-),男,安徽安慶人,中國(guó)科技大學(xué)信息科學(xué)技術(shù)學(xué)院碩士研究生,研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò),liuye114@mail.ustc.edu.cn;

傅忠謙(1959-),男,江蘇南京人,中國(guó)科技大學(xué)信息科學(xué)技術(shù)學(xué)院副教授,從事復(fù)雜系統(tǒng)和復(fù)雜網(wǎng)絡(luò)理論、系統(tǒng)仿真研究。

DetectionofTrapCoverageHolesinWSNsBasedonTopographicCorrection

LIUYe,FUZhongqian*

(School of Information,University of Science and Technology of China,Hefei 230027,China)

How to get the size of the holes in wireless sensor networks directly affects trap hole detection.Previous hole detection algorithms always base on the disk coverage model,and it can not get the actual size of the holes in rugged terrain.For the case of hilly terrain,this paper put forward a topographic correction algorithm based on the slope information in digital elevation maps to detect trap holes in rugged terrain by constructing directional sensing model for the sensor nodes.Based on this method,this paper further studies on the influence on trap holes detection of slope,aspect and node spacing,and finds a approximate method to determine the node spacing according to the terrain.The simulation result demonstrates the algorithm and help to find out the value of the node spacing to make the rate of trap holes below 5%.This result can provide reference for the deployment of sensor networks in rugged terrain.

wireless sensor networks;trap holes;rugged terrain;slope

2014-03-20修改日期:2014-05-13

10.3969/j.issn.1004-1699.2014.06.015

TP393

:A

:1004-1699(2014)06-0785-06