基于多移動信標的DV-Hop定位算法

任明明,謝志軍,金 光,何加銘

(寧波大學信息科學與工程學院浙江省移動網應用技術重點實驗室,浙江寧波315211)

基于多移動信標的DV-Hop定位算法

任明明,謝志軍,金 光,何加銘

(寧波大學信息科學與工程學院浙江省移動網應用技術重點實驗室,浙江寧波315211)

針對傳統DV-Hop定位算法嚴重依賴拓撲結構的問題,提出一種基于多移動信標和DV-Hop的定位算法MMB-DV-Hop。利用多個移動信標遍歷整個DV-Hop定位網絡,并且這些信標保持一定的相對位置關系,使用RSSI技術測距并為未知節點提供距離信息以輔助定位,從而有效結合基于測距和基于非測距2種算法的優勢。仿真結果表明,與傳統算法相比,該算法能減少約10%～15%的歸一化平均定位誤差,不僅降低對網絡拓撲結構的依賴,而且減少了距離估計誤差對定位精度的影響,從而提高平均定位精度。

無線傳感器網絡;定位;DV-Hop算法;多移動信標;非測距;誤差

1 概述

無線傳感器網絡(Wireless Sensor Networks, WSN)是由部署在監測區域內的大量廉價微型傳感器節點通過無線通信方式形成的一個多跳的自組織網絡系統[1]。

WSN是一種比較新穎的信息獲取、處理技術,它在工農業控制、環境監測、危險區域遠程控制、物流管理、汽車工業等許多領域都有著廣闊的應用前景[2];對于這些應用,位置信息可使感知數據具有意義;位置信息可輔助進行WSN的路由管理、拓撲管理等,因此,研究節點定位技術對無線傳感器網絡應用意義重大[3]。

本文對無線傳感器網絡定位算法進行研究,介紹傳統的DV-Hop算法,指出該算法的問題所在,在此基礎上,提出一種基于多移動信標的DV-Hop定位算法,通過實驗仿真和數據統計的結果分析對改進算法進行性能評價。

2 相關工作

根據WSN定位的機制是否需要測距設備,定位算法可分為兩大類:基于測距(Range-based)和基于非測距的(Range-free)定位方法[4]。Range-based定位測量節點之間的距離或者角度信息,之后使用三角測量、三邊測量或最大似然估計定位法計算節點坐標。常用測距技術有RSSI[5]、TOA[6]、TDOA[7]和AOA[8];Range-free定位無需節點距離和角度信息,通過網絡連通性信息就可實現定位。常用的Rangefree定位算法有 Centroid、APIT(Approximate Point in Triangle Test)、DV-Hop[9]、Amorphous、APS(Ad Hoc Positioning System)等。

DV-Hop算法巧妙地將網絡的連通信息和距離矢量信息轉化為近似的距離測量,是目前研究最廣泛的算法之一。文獻[10]修正平均每跳距離的角度,分別用最小二乘法校正平均每跳距離、加權處理平均每跳距離等方法優化改進 DV-Hop算法;文獻[11]提出了一個錨節點信任度的概念,最后通過加權最小二乘法計算得到未知節點坐標,但是改進算法的通信量和計算量還是比較大的。錨節點之間的跳數一般都為整數,每跳之間距離不盡相同,必然偏離實際距離,因此文獻[12]對錨節點之間的跳數進行了修正,使得跳數不再只是整數。

與無信標方法相比,基于移動信標的定位方法能得到更高的定位精度。MBL(Mobile Beaconassisted Localization Algorithm Based on Networkdensity Clustering)算法[13]首先對傳感區域內未知節點分簇,計算簇內各個未知節點相對位置坐標,然后使用移動信標信息對簇頭節點進行輔助定位,從而得到其他未知節點位置。使用多個移動信標輔助定位可獲得更高定位效果。虛擬尺方法將2個信標放在長度固定的車輛上進行輔助定位,車輛移動期間測量各個未知節點之間的距離信息,從而計算得到未知節點位置[14]。

3 改進的DV-Hop定位算法

3.1 傳統的DV-Hop算法

DV-Hop定位算法是一種分布式、逐跳計算的節點定位算法[15]。

這種算法分為以下3個步驟:

(1)使用距離矢量交換協議,使網絡中所有未知節點獲得距離錨節點的跳數。

(2)錨節點獲得其他錨節點位置、相隔跳距后,可以計算網絡平均每跳距離,然后將其作為一個校正值采用可控洪泛法廣播至網絡中。當接收到校正值后,節點根據跳數計算與錨節點之間的距離。

(3)當未知節點獲得與3個或更多錨節點的距離時,則在第3階段執行三邊測量定位。

如圖1所示,已知錨節點N1與N2,N3之間的距離、跳數。N2計算得到校正值(45+76)/(2+5)= 17.29,即平均每跳距離。假設A從N2獲得校正值,則它與3個錨節點之間的距離分別為A-N1:3× 17.29,A-N2:2×17.29,A-N3:3×17.29,最后使用三邊測量法確定未知節點A的位置。

圖1 DV-Hop定位算法示意圖

由于DV-Hop算法的定位精度主要由估計的平均每跳距離的精確度決定,因此它的定位精度很大程度上依賴于路線彎曲程度和網絡的拓撲結構[16]。在各向同性的密集網絡下,DV-Hop才可以得到較好的性能表現。否則,在網路拓撲不規則的隨機分布網路下,DV-Hop無法得到合理的平均每跳距離,導致定位精度的急劇下降。

3.2 MMB-DV-Hop定位算法

Range-based定位方法的性能很大程度上依賴于距離測量中產生的誤差大小,因此受環境的影響較大[16]。而Range-free定位方法,如DV-Hop方法能夠彌補基于測距定位方法的不足,但是它只有在各向同性的密集網絡下才能發揮比較好的性能。因此,可以通過結合Range-based和Range-free算法降低測量的精度和環境變化對Range-based算法的影響,以及DV-Hop對路線彎曲程度和網絡拓撲結構的依賴。

本文通過在DV-Hop網絡中引入3個移動信標,結合Range-based和Range-free 2種定位方法,彌補2種方法的不足之處。一個未知節點至少需要接收到 3個非共線虛擬信標信息,才可通過基于Range-based方法實現定位,如果使用一個移動信標的定位方法,則需要信標多次經過一個未知節點。因此本文提出一種基于多移動信標的DV-Hop定位算法(MMB-DV-Hop),同一時刻可以產生多個虛擬信標,且移動信標經過未知節點可以實現一次性定位該節點,同時在移動信標定位的過程中,實施基于Range-free的DV-Hop定位。

3.2.1 定位方法

移動信標通常攜帶 GPS(Global Positioning System)以獲取自身位置,假定未知節點有RSSI測距能力。接收信號強度指示(RSSI)是通過接收到的信號強度衰減來估算距離的一種測距定位技術,其理論路徑耗散函數如下:

其中,PL(d)表示信號在傳播距離d后的強度衰減,以dB為單位;η是耗散系數,通常取值為2～4,用于指示耗散相對路徑的增加速率;d0是從發射端附近測量的一個參考距離;Xσ是隨機環境噪聲值,遵循X～N(0,σ2)。

假定s是一個未知節點,真實位置為(xs,ys),估計位置為(x^s,y^y^s);信標節點Bi(i=1,2,3)的坐標值為Bi(xi,yi),它的傳輸范圍在半徑為R的圓內。當網絡中的一個未知節點有效距離范圍內,只存在一個信標信息,通過此信標信息無法定位該未知節點,因此需采用2個或者2個以上的信標節點。

本文采用文獻[17]所使用的3個信標節點的位置關系,將3個信標排列成邊長為R的等邊三角形,如圖2所示。

圖2 3個信標之間的位置關系

設di(i=1,2,3)是S與Bi之間的距離,即:

如果S測得了3個虛擬信標的距離信息,未知節點便可使用三邊測量法進行定位。如圖3所示,如果S通過測量只得到2個虛擬信標的距離,假設S測得到B2的距離為d1,到B3的距離為d2,但卻未收到來自B1的信號,通過式(3)可得到2個對稱的位置S和S′,由于S必定在△B2B3A2內,可把S′排除,那么S的位置便確定。如果此時只有2個移動信標,S則無法確認自身位置(有可能是S′)。當信標節點到達3個以上,最終可能進一步提高精度,但是成本明顯提高。因此,本文采用3個移動信標進行輔助定位:

圖3 S的2種可能位置

算法 MMB-DV-Hop算法

算法主要分為2個階段:

(1)3個移動信標節點以固定的位置關系,按照指定的信標移動路徑在傳感區域移動并周期性地廣播信息包,信息包中有自身位置坐標和初始跳計數1。每個節點都記錄并更新表{ki,(xi,yi)},其中, (xi,yi)為信標節點的坐標;ki為信標節點i到該節點的跳數,只保留一跳和二跳節點信息。通信半徑內所有未知節點都不斷檢查是否接收到2個或者2個以上的信標節點信息包,如果接收到3個信標信息則可以通過三邊測量法進行定位,接收到2個信標信息則可以按式(3)進行定位,這些未知節點定位成功成為虛擬信標。

(2)當3個移動信標遍歷整個傳感區域,如果仍有未知節點,則采用DV-Hop算法進行定位。當移動信標穿越整個傳感區域或者設置的閾值達到最大值,DV-Hop定位算法啟動。可以設置閾值為信標的數目。

3.2.2 信標移動路徑的設計

對于依賴于移動信標的定位應用中,找到一條最優的移動路徑對提高定位性能有很大幫助。而MMB-DV-Hop算法主要是通過移動信標產生大量的最優虛擬信標,并且結合三邊測量法和DV-Hop來提高定位精度,移動信標的運動路徑應該要保障在最短時間里盡量走完傳感區域。因此,MMB-DV-Hop算法可以采用網格掃描(Scan)模型,如圖4所示。

圖4 網格掃描移動模型

圖5 移動路徑的覆蓋情況

4 性能仿真

為了驗證改進算法MMB-DV-Hop的有效性和可行性,利用Matlab7.8對本文改進算法、文獻[18]基于RSSI的Range-free算法和傳統DV-Hop算法進行仿真對比研究。

4.1 仿真環境與參數選擇

在不同錨節點比例、不同節點個數的條件下對比文獻[18]、傳統DV-Hop和改進算法,從以下2個方面分析算法的性能:

其中,K為仿真次數;Un為未知節點的總數。歸一化平均定位誤差為平均誤差error與通信半徑R的比值:

(2)歸一化的平均定位誤差的均方差。所有未知節點的平均定位誤差的均方差δ為:

歸一化的平均定位誤差的均方差為:

4.2 結果分析

向目標傳感區域隨機部署100個節點,節點密度平均為10.18,節點通信半徑R為20 m,移動信標按照指定的路徑走完傳感區域,分析算法在不同在錨節點比例下的情況。在節點總數保持不變情況,在比例為0.05,0.15,0.20,0.25,0.30,0.35,0.40等不同錨節點比例下,節點歸一化平均定位誤差如圖6所示,節點歸一化定位誤差的均方差關系對比如圖7所示。

圖6 歸一化平均定位誤差與錨節點的關系

圖7 歸一化定位誤差的均方差與錨節點的關系

從圖6中3條曲線的走勢可以看出,3種定位算法的歸一化平均定位誤差都隨著錨節點比例的增加而減小,最后趨于平穩狀態;本文改進算法從錨節點為0.2開始,歸一化平均誤差就保持在0.3左右,相比傳統 DV-Hop算法和文獻[18]基于 RSSI的Range-free算法有明顯的改進;MMB-DV-Hop的歸一化平均定位誤差相比傳統DV-Hop算法降低了約10% ～15%。

歸一化定位誤差的均方差度量了節點與平均定位誤差的偏離程度,均方差值越小,說明網絡節點定位結果越穩定,則定位誤差就集中分布在平均定位誤差的兩側,均方差值越大,則定位結果越難以確定。在圖7中,本文改進算法的歸一化平均定位誤差在對比的錨節點比例下都比其他2種定位算法小,最后趨于穩定值。當錨節點比例為0.4時,本文改進算法MMB-DV-Hop的歸一化定位差的均方差值為0.207 8,而傳統DV-Hop算法為0.278 4。由此說明本文改進算法的未知節點定位計算更穩定,不會出現節點定位誤差偏離平均定位誤差較大的情況,有更高的可信度。

向目標傳感區域部署節點數分別為100,150, 200,250,300,350,400個,而且保持錨節點比例為10%,節點通信半徑R為20 m的情況下,節點歸一化平均定位誤差、歸一化定位誤差的均方差與總節點個數的對比關系如圖8和圖9所示。由圖8的結果可以看出,2種定位算法的歸一化平均定位誤差隨著總節點個數的增加而減少,最后趨于穩定。由于在傳感區域不變的情況下,節點總數的增加使得網絡的平均網絡連通度增大,即節點密度增大,定位精度相應提高了;當總結點個數為100時,本文改進算法的歸一化平均定位誤差為0.362 1,比傳統DVHop算法減少15%左右。在圖9的結果中,改進算法比傳統DV-Hop的定位誤差均方差平均少2%～10%,比文獻[18]基于RSSI的Range-free算法平均少3%～14%,由此可知本文改進算法相對穩定。由圖8和圖9可知,與傳統DV-Hop定位算法相比,在節點數相對較少的情況下,改進算法的性能相對突出。

圖8 歸一化平均定位誤差與總節點個數的關系

圖9 歸一化定位誤差的均方差與總節點個數的關系

5 結束語

本文通過分析傳統DV-Hop算法的優缺點,將多個移動信標引入DV-Hop網絡,給出一種基于多移動信標的無線傳感網絡定位算法MMB-DV-Hop。仿真結果表明,與傳統的DV-Hop和基于測距的質心定位算法相比,MMB-DV-Hop定位方法具有良好的定位精度,定位性能穩定性較高,MMB-DV-Hop比較適合在節點數相對較少情況下進行定位。然而基于移動信標的定位方法就不適用于需要快速定位的網絡,因此,如何規劃移動信標的移動路徑,從而快速覆蓋傳感網絡區域將是進一步研究的方向。

[1] 孫利明,李建中,陳 瑜,等.無線傳感器網絡[M].北京:清華大學出版社,2005.

[2] Trigoni N,Krishnamachari B.Sensor Network Algorithms and Applications[J].Philosophical Transactions of the Royal Society A:Mathematical,Physical and Engineering Sciences,2012,370(1958):5-10.

[3] 崔煥慶,王英龍,郭 強,等.多移動信標輔助的分布式節點定位方法[J].通信學報,2012,33(3):103-111.

[4] 王福豹,史 龍,任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報,2005,16(5):857-868.

[5] Huang C T,Wu C H,Lee Y N,et al.A Novel Indoor RSS-based Position Location Algorithm Using Factor Graphs[J]. IEEE Transactions on Wireless Communications,2009,8(6):3050-3058.

[6] Jeon N R,Lee H B,Park C G,et al.Super Resolution TOA Estimation with Computational Load Reduction [J].IEEE Transactions on Vehicular Technology,2010, 59(8):4139-4144.

[7] Matin R K,Yan Chunpeng,Fan H H,et al.Algorithms and Bounds for Distributed TDOA-based Positioning Using OFDM Signals[J].IEEE Transactions on Signal Processing,2011,59(3):1255-1268.

[8] Yu Kegen,Guo Yingjie.Statistical NLOS Identification Based on AOA,TOA and Signal Strength[J].IEEE Transactions on Vehicular Technology,2009,58(1): 274-286.

[9] 張 震,閆連山,劉江濤,等.基于DV-Hop的無線傳感器網絡定位算法研究[J].傳感技術學報,2011,24 (10):1469-1472.

[10] 林金朝,陳曉冰,劉海波.基于平均跳距修正的無線傳感器網絡節點迭代定位算法[J].通信學報,2009, 30(10):107-113.

[11] 朱 敏,劉昊霖,張志宏,等.一種基于DV-Hop改進的無線傳感器網絡定位算法[J].四川大學學報:工程科學版,2012,44(1):93-98.

[12] 肖麗萍,劉曉紅.一種基于跳數修正的DV-Hop定位算法[J].傳感技術學報,2012,25(12):1726-1730.

[13] 趙 方,馬 嚴,羅海勇,等.一種基于網絡密度分簇的移動信標輔助定位方法[J].電子與信息學報, 2009,31(12):2988-2992.

[14] Ding Yong,Wang Chen,Xiao Li.Using Mobile Beacons to Locate Sensors in Obstructed Environments[J]. Journal of Parallel and Distributed Computing,2010,70 (6):644-656.

[15] Niculescu D,Nath B.DV Based Positioning in Ad Hoc Networks[J].Telecommunication Systems,2003,22(1-4):267-280.

[16] Sichitiu M L,Ramadurai V.Localization of Wireless Sensor Networks with a Mobile Beacon[C]//Proc.of IEEE International Conference on Mobile Ad-hoc and Sensor Systems.[S.l.]:IEEE Press,2004:174-183.

[17] Zhang Zusheng,Yu Fengqi.Collaborative Localization Algorithm for Wireless Sensor Networks Using Mobile Anchors[C]//Proc.of Asia-Pacific Conference on Computational Intelligence and Industrial Applications [S.l.]:IEEE Press,2009:309-312.

[18] 劉 鋒,章登義.基于RSSI的無線傳感器網絡質心定位算法[J].計算機科學,2012,39(6):96-98.

編輯 任吉慧

DV-Hop Localization Algorithm Based on Multi-mobile Beacon

REN Ming-ming,XIE Zhi-jun,JIN Guang,HE Jia-min
(Key Laboratory of Mobile Internet Application Technology of Zhejiang Province, College of Information Science and Engineering,Ningbo University,Ningbo 315211,China)

Due to the serious dependence on the topology of the network in DV-Hop algorithm,a DV-Hop localization algorithm based on multi-mobile beacon called MMB-DV-Hop is proposed in this paper.The algorithm incorporates Range-based and Range-free algorithms by introducing multi-mobile beacons into the DV-Hop positioning network,and the beacons keep a certain relative position while traversing the entire network and ranging with RSSI to provide information to unknown nodes to estimate locations.Simulation results show that the proposed algorithm has better locating performance in positioning accuracy by reducing the dependence on the topology of the network and the influence of distance estimation error on the positioning accuracy.

Wireless Sensor Networks(WSN);localization;DV-Hop algorithm;multi-mobile beacon;Range-free; error

1000-3428(2014)10-0092-06

A

TP393

10.3969/j.issn.1000-3428.2014.10.018

國家自然科學基金資助項目(60902097);浙江省自然科學基金資助項目(LY12F02013);浙江省科技廳重大科技專項基金資助重點工業項目(2011C11042);寧波市自然科學基金資助項目(2012A610013,2012A610014);寧波大學研究生重點課程建設基金資助項目(zdkc2012004)。

任明明(1986-),男,碩士研究生,主研方向:無線傳感器網絡;謝志軍,副教授、博士;金 光、何加銘,教授、博士。

2013-08-28

2013-11-05E-mail:lieque1130@163.com

中文引用格式:任明明,謝志軍,金 光,等.基于多移動信標的DV-Hop定位算法[J].計算機工程,2014, 40(10):92-97.

英文引用格式:Ren Mingming,Xie Zhijun,Jin Guang,et al.DV-Hop Localization Algorithm Based on Multi-mobile Beacon[J].Computer Engineering,40(10):92-97.