一種基于坐標(biāo)改正的改進(jìn)DV-Hop定位算法*

王 興,聶云峰,徐飛飛

(南昌航空大學(xué)信息工程學(xué)院,南昌 330063)

項目來源:國家自然科學(xué)基金項目(41101426)

2017-04-18修改日期2017-06-09

一種基于坐標(biāo)改正的改進(jìn)DV-Hop定位算法*

王 興,聶云峰*,徐飛飛

(南昌航空大學(xué)信息工程學(xué)院,南昌 330063)

為有效提高DV-Hop算法在拓?fù)潆S機網(wǎng)絡(luò)中的定位精度,提出一種利用錨節(jié)點定位誤差修正未知節(jié)點坐標(biāo)的新方法(PEDV-Hop)。首先定義偽距誤差因子剔除對平均跳距計算產(chǎn)生較大誤差的錨節(jié)點,從而有效抑制網(wǎng)絡(luò)拓?fù)潆S機分布影響,提高平均跳距計算精度;其次,視錨節(jié)點為未知節(jié)點,在計算平均跳距的同時,運用三邊或多邊測量法評估自身定位坐標(biāo),從而可計算得到錨節(jié)點坐標(biāo)改正值,并將平均跳距與坐標(biāo)改正值向網(wǎng)絡(luò)廣播;最后,未知節(jié)點根據(jù)接收到各錨節(jié)點的坐標(biāo)改正值來修正自身定位誤差,從而有效提高節(jié)點定位精度。仿真結(jié)果表明,PEDV-Hop算法實現(xiàn)簡單,有效提高了節(jié)點的定位精度。

DV-Hop算法;節(jié)點定位;平均跳距;偽距誤差因子

無線傳感網(wǎng)絡(luò)WSN(Wireless Sensor Networks)是由部署在監(jiān)測區(qū)域內(nèi)的大量微型并裝備低能耗收發(fā)器和有限數(shù)據(jù)處理能力的感知節(jié)點通過無線通信形成的多跳自組織網(wǎng)絡(luò)[1]。節(jié)點定位是WSN的關(guān)鍵技術(shù)之一[2],定位算法按測距與否可分為:基于測距(Range-based)和免測距(Range-free)兩種[3]。其中,基于測距的定位方法對硬件有較高要求,一般需借助特定硬件測量出相鄰節(jié)點間的角度或距離,計算和通信開銷大;而免測距定位算法,只需依靠網(wǎng)絡(luò)連通性或網(wǎng)絡(luò)拓?fù)潢P(guān)系就可以實現(xiàn)定位[4-5],具有成本低、定位過程簡單且能提供較理想定位精度等優(yōu)勢,因此更適合大規(guī)模無線傳感網(wǎng)絡(luò)節(jié)點定位的實際應(yīng)用需求[6]。

DV-Hop定位算法作為一種經(jīng)典的免測距定位方法,以其過程簡潔,效果較好得到廣泛的應(yīng)用,目前國內(nèi)外研究者針對該算法的優(yōu)化提出大量具有參考價值的改進(jìn)算法,大致可分為以下3類:

①錨節(jié)點選取優(yōu)化類算法。文獻(xiàn)[7]基于引入RSSI測距技術(shù)提出限制機制以減少節(jié)點的通信量和能耗,并通過優(yōu)化參與定位的錨節(jié)點組合和質(zhì)心算法有效降低定位誤差;文獻(xiàn)[8]通過Min-Max算法對未知節(jié)點進(jìn)行初始位置的估計,然后通過未知節(jié)點和錨節(jié)點間的位置關(guān)系將未知節(jié)點升級為錨節(jié)點來增加錨節(jié)點的密度,從而提高網(wǎng)絡(luò)中其他節(jié)點的定位精度;文獻(xiàn)[9]通過設(shè)置未知節(jié)點接收錨節(jié)點信息數(shù)量的閾值,選擇距離較近的部分錨節(jié)點作為參考節(jié)點,減少定位誤差和計算量,提高效率和定位精度。

②平均跳距修正類算法,如:文獻(xiàn)[10]采用Cayley-Menger行列式給出的距離幾何約束條件對未知節(jié)點和錨節(jié)點間的估計距離進(jìn)行處理,提高定位精度;文獻(xiàn)[11]采用最小二乘法和加權(quán)處理法修正錨節(jié)點間的平均跳距,并通過迭代求解法提高未知節(jié)點的定位準(zhǔn)確性和精度的穩(wěn)定性;文獻(xiàn)[12]通過最小均方差準(zhǔn)則改進(jìn)平均跳距的公式,并在最佳指數(shù)值下,修正錨節(jié)點的平均跳距,以此來提高節(jié)點定位的精度。

③跳數(shù)修正類算法,如:文獻(xiàn)[13]通過提出非整數(shù)的錨節(jié)點間跳數(shù),使用跳數(shù)偏離因子對未知節(jié)點與錨節(jié)點間跳數(shù)進(jìn)行修正,使得節(jié)點間距離估計更加準(zhǔn)確;文獻(xiàn)[14]通過RSSI值對1跳鄰居節(jié)點進(jìn)行分級,細(xì)化跳數(shù),然后將節(jié)點間的距離比值作為跳數(shù)修正的權(quán)值,從而抑制跳數(shù)值計算誤差帶來的定位偏差較大的問題;文獻(xiàn)[15]根據(jù)跳數(shù)信息對錨節(jié)點進(jìn)行了分類,設(shè)定不同跳數(shù)閾值,只選擇大于或等于跳數(shù)閾值的節(jié)點參與距離估算,以實現(xiàn)定位精度的提升。

在DV-Hop族系算法中,錨節(jié)點平均跳距的估算對定位精度有至關(guān)重要影響,對于節(jié)點分布均勻、各項同性的密集型網(wǎng)絡(luò),通?？傻玫捷^合理的平均跳距,從而達(dá)到適當(dāng)?shù)亩ㄎ痪?但對于網(wǎng)絡(luò)拓?fù)洳灰?guī)則、隨機分布的傳感網(wǎng)絡(luò)來說,錨節(jié)點到未知節(jié)點間往往不是直線路徑,用跳段距離代替直線距離誤差較大,因此定位精度較低[16-17]。為解決上述問題,提出一種利用錨節(jié)點定位誤差修正未知節(jié)點坐標(biāo)的新方法——PEDV-Hop(Pseudo-Range Error DV-Hop)。該算法首先定義偽距誤差因子剔除對平均跳距計算產(chǎn)生較大誤差的錨節(jié)點,從而有效抑制網(wǎng)絡(luò)拓?fù)潆S機分布影響,提高平均跳距計算精度;其次,視錨節(jié)點為未知節(jié)點,在計算平均跳距的同時,運用三邊或多邊測量法評估自身定位坐標(biāo),從而可計算得到錨節(jié)點坐標(biāo)改正值,并將平均跳距與坐標(biāo)改正值向網(wǎng)絡(luò)廣播;最后,未知節(jié)點根據(jù)接收到各錨節(jié)點的坐標(biāo)改正值來修正自身定位誤差,從而有效提高節(jié)點定位精度。

1 DV-Hop算法

DV-Hop是Dragos Niculescu等人根據(jù)距離矢量路由原理提出的定位算法[18-20],主要包括3個階段:第1階段,使用典型的距離矢量交換協(xié)議,通過節(jié)點間的信息交換,使網(wǎng)絡(luò)中所有節(jié)點獲得與錨節(jié)點之間的跳數(shù)及錨節(jié)點位置信息;第2階段,錨節(jié)點計算平均跳距,然后將其作為一個跳距校正值廣播至網(wǎng)絡(luò)中,其中校正值采用可控洪泛法在網(wǎng)絡(luò)中傳播,這意味著一個節(jié)點僅接受獲得的第1個校正值,而丟棄所有后來者,這個策略確保了絕大多數(shù)節(jié)點可從最近的錨節(jié)點接收校正值。當(dāng)未知節(jié)點接收到該校正值之后,用該校正值乘以到附近各錨節(jié)點之間的跳數(shù),從而得出估計的歐氏距離;第3階段,當(dāng)未知節(jié)點獲得與3個或更多錨節(jié)點間的歐氏距離時執(zhí)行三邊或多邊測量定位法對未知節(jié)點進(jìn)行定位。

傳統(tǒng)DV-Hop算法使用平均跳距與跳數(shù)相乘來計算實際距離,用節(jié)點間的直線距離來估算節(jié)點間信息通路的曲線距離。在計算最小跳距時,無論相近節(jié)點間物理距離的遠(yuǎn)近,跳數(shù)值均加一,并不能反映出實際距離的差別,并且對于節(jié)點隨機分布的傳感網(wǎng)絡(luò)而言,錨節(jié)點到定位節(jié)點往往不是直線路徑,故采用經(jīng)典DV-Hop算法可能會帶來較大的距離計算誤差。

2 PEDV-Hop算法

針對傳統(tǒng)DV-Hop定位算法在節(jié)點隨機分布、拓?fù)洳灰?guī)則傳感網(wǎng)絡(luò)中的定位精度較差的問題,提出PEDV-Hop算法通過定義偽距誤差因子對第2階段平均跳距進(jìn)行修正,并利用錨節(jié)點坐標(biāo)改正值對第3階段未知節(jié)點坐標(biāo)進(jìn)行修正,從而有效提高節(jié)點定位精度。

2.1 平均跳距修正

設(shè)隨機分布的網(wǎng)絡(luò)中錨節(jié)點的個數(shù)為N。通過典型的距離矢量交換協(xié)議,使網(wǎng)絡(luò)中所有節(jié)點獲得與錨節(jié)點之間的跳數(shù)及錨節(jié)點位置信息,錨節(jié)點Ni利用式(1)估算平均跳距:

(1)

定義Ni與Nj之間的偽距為:

(2)

定義Ni與Nj之間的偽距誤差因子為:

(3)

在隨機分布的網(wǎng)絡(luò)中,Ni與Nj之間的偽距與真實距離的誤差可能很大,將Ni與Nj之間的偽距誤差因子按升序排列。取前K(K≥3)個節(jié)點參與Ni平均跳距的計算,目的是剔除對測距誤差影響較大的錨節(jié)點,從而有效抑制拓?fù)潆S機分布的影響,則Ni的平均跳距修正為:

(4)

2.2 錨節(jié)點坐標(biāo)改正值計算

(5)

2.3 未知節(jié)點坐標(biāo)改正

未知節(jié)點記錄接收到的錨節(jié)點的平均跳距及坐標(biāo)改正值,根據(jù)記錄的跳數(shù),計算到每個錨節(jié)點的跳段距離,采用三邊測量或最小二乘法計算自身的估計坐標(biāo)。

(6)

式中:N為錨節(jié)點總數(shù)。

2.4PEDV-Hop算法流程

Step 1 網(wǎng)絡(luò)初始化;

Step 2 使用典型的距離矢量交換協(xié)議,錨節(jié)點Ni在網(wǎng)絡(luò)中廣播包含自身位置信息的數(shù)據(jù)包{IDi,(xi,yi),hop},通過節(jié)點間的信息交換,使網(wǎng)絡(luò)中所有節(jié)點獲得與錨節(jié)點之間的跳數(shù);

Step 5 算法結(jié)束。

3 仿真分析

仿真場景為100 m×100 m的感知區(qū)域,節(jié)點總數(shù)為150,錨節(jié)點總數(shù)為N,K取值見3.2節(jié),未知節(jié)點和錨節(jié)點隨機產(chǎn)生。定義平均定位誤差ave_error作為算法性能的評價標(biāo)準(zhǔn),ave_error計算方法如式(7)所示:

(7)

式中:(xi,yi)、(Xi,Yi)分別為節(jié)點i的估計坐標(biāo)和真實坐標(biāo),R為通信半徑,n為未知節(jié)點數(shù)。

3.1 結(jié)果分析

圖1給出了DV-Hop算法、文獻(xiàn)[17]算法、DDV-Hop算法、PEDV-Hop_1算法和PEDV-Hop算法在不同錨節(jié)點比例及通信半徑下定位誤差的比較結(jié)果。

圖1 錨節(jié)點比例、節(jié)點通信半徑變化下各算法定位誤差比較

圖1表明:①在相同的通信半徑下,上述算法的定位誤差隨著錨節(jié)點比例增加而減小,并逐漸趨于平穩(wěn)。當(dāng)錨節(jié)點比例小于20%時,隨著錨節(jié)點比例增加,PEDV-Hop算法定位精度提高明顯、變化幅度較大,比DV-Hop算法降低19%～25%,比PEDV-Hop_1算法降低8%～14%,比文獻(xiàn)[17]定位算法降低4%～10%,比DDV-Hop算法降低2%～12%;當(dāng)錨節(jié)點比例大于20%時,PEDV-Hop算法定位精度提升較慢,趨于平穩(wěn),比DV-Hop算法降低17%～26%,比PEDV-Hop_1算法降低7%～13%,比文獻(xiàn)[17]定位算法降低5%～15%,比DDV-Hop算法降低1%～6%。

②在相同的錨節(jié)點比例下,隨著通信半徑增大,PEDV-Hop算法、PEDV-Hop_1算法、DV-Hop算法定位精度變化平穩(wěn),DDV-Hop算法及文獻(xiàn)[17]算法的誤差曲線變化波動較大;而且隨著通信半徑增大,PEDV-Hop算法定位精度總體呈下降趨勢,但比DV-Hop算法定位誤差減小幅度變大。這是因為隨著通信半徑的增大,網(wǎng)絡(luò)連通性變強,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)更加復(fù)雜,導(dǎo)致平均跳距的估計誤差變大[21],而PEDV-Hop算法通過定義偽距誤差因子修正平均跳距,有效的抑制網(wǎng)絡(luò)拓?fù)潆S機分布影響,提高了平均跳距計算精度,從而提高了節(jié)點定位精度。

③在相同的通信半徑及通信半徑下,PEDV-Hop_1算法定位精度比DV-Hop算法平均高11%,說明PEDV-Hop算法第1步修正的有效性;但比PEDV-Hop算法定位精度平均低13%,說明PEDV-Hop算法第2步修正的有效性。

3.2 K取值分析

在PEDV-Hop算法中,K的取值決定參與平均跳距計算錨節(jié)點數(shù)量,對平均跳距估算有一定的影響。本節(jié)通過實驗觀察K取值對PEDV-Hop定位精度的影響。實驗結(jié)果如圖2所示。

圖2 K取值對定位誤差的影響

圖2表明,K值的變化直接影響算法定位精度?？傮w上,當(dāng)3≤K≤?N/3」時定位精度呈波動上升趨勢;當(dāng)?N/3」≤K≤?N/3」時定位精度最優(yōu);當(dāng)?N/2」≤K≤N時定位精度呈波動下降趨勢。因此,當(dāng)?N/3」≤K≤?N/2」時,PEDV-Hop算法定位精度最優(yōu)。

4 結(jié)語

本文介紹了DV-Hop算法的原理及實現(xiàn)過程,分析了DV-Hop在節(jié)點隨機分布、網(wǎng)絡(luò)拓?fù)洳灰?guī)則網(wǎng)絡(luò)中定位精度較低的問題,提出PEDV-Hop改進(jìn)算法,通過定義偽距誤差因子修正平均跳距,并利用錨節(jié)點坐標(biāo)改正值修正未知節(jié)點坐標(biāo),從而有效提高節(jié)點定位精度。仿真實驗對比了在不同通信半徑及錨節(jié)點比例下PEDV-Hop算法同傳統(tǒng)DV-Hop算法以及部分改進(jìn)算法的定位精度差異,并對K取值進(jìn)行探究。結(jié)果表明:PEDV-Hop算法穩(wěn)定有效的提高了節(jié)點的定位精度;隨著通信半徑的增大,PEDV-Hop算法對傳統(tǒng)DV-Hop算法的改進(jìn)效果更加明顯;總體上,當(dāng)?N/3」≤K≤?N/2」時,PEDV-Hop算法精度最高。

[1] 孫立明,李建中,陳瑜,等. 無線傳感器網(wǎng)絡(luò)[M]. 北京:清華大學(xué)出版社,2005:149-151.

[2] Han G,Chao J,Zhang C,et al. The Impacts of Mobility Models on DV-Hop Based Localization in Mobile Wireless Sensor Networks[J]. Journal of Network and Computer Applications(S1084-8045),2014,42(4):70-79.

[3] Zhao J,Zhao Q,Li Z,et al. An improved Weighted Centroid Localization Algorithm Based on Difference of Estimated Distances for Wireless Sensor Networks[J]. Telecommunication Systems(S1018-4864),2013,53(1):25-31.

[4] Shang Y,Run I W,Zhang Y. Localization from Mere Connectivity[C]//Proc of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing Anna-Polis,USA:ACM,2003:201-211.

[5] Niculescu D,Nath B. Ad Hoc Positioning System(APS)Using AOA[C]//Proc of the 22nd Annual Joint Conf of the IEEE Computer and Communications Societies(INFOCOM’2003),2003(3):1734-1743.

[6] Bulusu N,Heidemann J,Estrin D. GPS-Less Low Cost Outdoor Localization for Very Small Devices[J]. IEEE Personal Communications Magazine,2000,7(5):28-34.

[7] 夏少波,鄒建梅,朱曉麗,等. 基于跳數(shù)區(qū)域劃分的DV-Hop改進(jìn)算法[J]. 傳感技術(shù)學(xué)報,2014,27(7):964-969.

[8] 王翥,郝曉強,王玲. 基于錨節(jié)點選擇的無線傳感網(wǎng)絡(luò)器定位算法[J]. 計算機研究與發(fā)展,2010,47(S):31-34.

[9] 申鉉京,李成岳,王碩. 基于最優(yōu)錨節(jié)點的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法[J]. 吉林大學(xué)學(xué)報(工學(xué)版),2011,41,增刊:208-214.

[10] 鄭君剛,吳成東,秦好,等. 基于DV-Hop和距離幾何約束的定位算法[J]. 東北大學(xué)學(xué)報(自然科學(xué)版),2011,32(4):457-459.

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

[12] 馬淑麗,趙建平. 多通信半徑的無線傳感網(wǎng)絡(luò)DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報,2016,29(4):593-600.

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

[14] 溫江濤,范學(xué)敏,吳希軍. 基于RSSI跳數(shù)修正的DV-Hop改進(jìn)算法[J]. 傳感技術(shù)學(xué)報,2014,27(2):502-507.

[15] 祝宇鴻,歷彥愷,王魯娜,等. 基于跳數(shù)閾值和節(jié)點分類的DV-Hop改進(jìn)算法[J]. 吉林大學(xué)學(xué)報(信息科學(xué)版),2014,32(4):407-412.

[16] Hou S F,Zhou X J,Liu X X. A Novel DV-Hop Localization Algorithm for Asymmetry Distributed Wireless Sensor Networks[C]//3rd IEEE International Conference on Computer Science and Information Technology(ICCSIT),2010,4:243-248.

[17] Chen H Y,Karo S,Deng P,et al. A Improved DV-Hop Localization Algorithm for Wireless Sensor Networks[C]//IEEE ICIEA,2008:1557-1561.

[18] Niculescu D. Positioning in Ad Hoe Sensor Networks[C]//IEEE Network,2004,18(4):24-29.

[19] Niculescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J]. Journal of Telecomm-Unications Systerns,2003,22(1/4):267-280.

[20] Kumar S,Lobiyal K. An Advanced DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications,2013,71:1365-1385.

[21] 嵇瑋瑋,劉中. DV-Hop定位算法在隨機分布傳感器網(wǎng)絡(luò)中的應(yīng)用研究[J]. 電子與信息學(xué)報,2008,30(4):970-974.

AnImprovedDV-HopLocalizationAlgorithmBasedonCoordinateCorrection*

WANGXing,NIEYunfeng*,XUFeifei

(School of Information Engineering,Nanchang Hangkong University,Nanchang 330063,China)

In order to improve the localization accuracy of DV-Hop algorithm in the random topology network scenario,a novel algorithm named PEDV-Hop is put forward. PEDV-Hop uses the localization error of anchor nodes to correct the coordinates of unknown nodes. Firstly,the pseudo-range error factor is defined to remove anchor nodes which may cause a larger calculation error of the average hop distance,through this way to improve the calculation accuracy of average hop distance,and to decrease the influence of topology random distribution. Secondly,the anchor node broadcasts the updated average hop distance together with its coordinate correction values calculated by trilateral or multilateral measurement with the premise of being treated as the unknown node. Lastly,the coordinates of each unknown node are corrected through the weighted average value of the coordinate correction values of the

anchor nodes. The simulation results show that PEDV-Hop algorithm has better localization accuracy and stability than the tradiDV-Hop algorithm and some existing improved algorithms,and it is easy to implement.

DV-Hop algorithm;node localization;average hop distance;pseudo-range error factor

TP393

A

1004-1699(2017)10-1560-05

10.3969/j.issn.1004-1699.2017.10.018

王興(1992-),男,碩士研究生,主要研究方向為無線傳感網(wǎng)絡(luò),地理信息系統(tǒng),Jwangxing0719@163.com;

聶云峰(1980-),男,博士,副教授,主要研究方向為無線傳感網(wǎng)絡(luò),遙感與地理信息系統(tǒng),nieyunf@gmail.com;

徐飛飛(1992-),男,碩士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò),1032074982@qq.com。