基于地形修正的無線傳感器網絡陷阱空洞檢測

劉 曄,傅忠謙

(中國科技大學信息科學技術學院,合肥 230027)

?

基于地形修正的無線傳感器網絡陷阱空洞檢測

劉 曄,傅忠謙*

(中國科技大學信息科學技術學院,合肥 230027)

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

無線傳感器網絡;陷阱空洞;起伏地形;坡度

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

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

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

1 陷阱空洞檢測算法的地形修正

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

1.1 陷阱空洞算法描述

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

圖1 陷阱空洞檢測算法示意圖

1.2 方向梯度感知模型

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

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

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

i=h/l=tanθ

(1)

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

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

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

(2)

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

下面基于坡度和方向梯度這兩個概念,求解起伏地形下的傳感器節(jié)點沿任意方向的實際感知距離。為了方便計算,以坡向為起始方向,并按順時針方向度量,將任一方向與坡向的夾角ω作為該方向的方向角。

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

g=tanβ

(3)

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

g=icosω

(4)

節(jié)點沿ω方向的實際探測半徑r′受到地形影響,與理想探測半徑r存在關系:

r′=rcosβ

(5)

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

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

(6)

特別的,當ω=0時,β=θ,則r′=rcosθ。

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

r′=rA

(7)

這表明平面距離和坡面距離的轉換關系,A為轉換因子,且0

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

因此,得到傳感器節(jié)點在ω方向上的實際探測半徑r′的計算公式如下:

r′=prcos[arctan(icosω)]

(8)

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

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

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

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

(9)

圖3 山坡地形交點和距離計算示意圖

(10)

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

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

(11)

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

(12)

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

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

(13)

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

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

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

2.1 地形修正前后檢測結果比較

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

①從網上下載的SRTM DATA VERSION 4.1地圖數據我國東南部(緯度25 N～30 N,經度115°～120°E)地圖中隨機選取大小為50 m×50 m的方格為例,如圖4所示,其中,圖4(a)為三維地形圖,圖4(b)為等高線地形圖。

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

圖5 地形修正的陷阱空洞檢測示意圖

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

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

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

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

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

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

d≤2r

(14)

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

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

(15)

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

d≤2rcos(arctani)

(16)

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

d≤2krcos(arctani)

(17)

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

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

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

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

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

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

③以坡度46.6為例,間隔0.05取不同k值,按式(16)計算相應d值,在不同空投方向下重復100次實驗,結果如表2。

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

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

為驗證之,將k=0.8代入其他坡度情況,即

d≤1.6rcos(arctani)

(18)

在不同的坡度和空投方向下,各重復100次仿真實驗,結果如表3。

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

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

3 結論

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

[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]胥楚貴,鄧曉衡,鄒豪杰.無線傳感器網絡覆蓋空洞修復策略[J].傳感技術學報,2010,23(2):256-259.

[9]王力立,吳曉蓓.傳感器網絡中陷阱空洞的分布式檢測及修復[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三維定位算法研究與在地形建模上的應用[J].傳感技術學報,2012,25(5):651-658.

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

[13]武曉波,王世新,肖春生.Delaunay三角網的生成算法研究[J].測繪學報,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]劉學軍,任志峰,王彥芳,等.基于DEM的任意方向坡度計算方法[J].地域研究與開發(fā),2009,28(4):139-141.

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

劉曄(1982-),男,安徽安慶人,中國科技大學信息科學技術學院碩士研究生,研究方向為無線傳感器網絡,liuye114@mail.ustc.edu.cn;

傅忠謙(1959-),男,江蘇南京人,中國科技大學信息科學技術學院副教授,從事復雜系統(tǒng)和復雜網絡理論、系統(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