文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.171111
中文引用格式： 蔣從元，楊杰. 基于分布式多跳誤差估計目標位置感知算法[J].電子技術(shù)應(yīng)用，2017，43(11)：95-98.
英文引用格式： Jiang Congyuan，Yang Jie. Energy efficiency target position aware algorithm with distributed multi-hop error estimates[J].Application of Electronic Technique，2017，43(11)：95-98.
0 引言
在無線傳感器網(wǎng)絡(luò)定位算法[1-6]的研究上，譚志等[7]提出一種基于節(jié)點間覆蓋關(guān)系的改進DV-Hop算法，該方法根據(jù)兩節(jié)點間的通信覆蓋率引入跳數(shù)系數(shù)，降低了每跳距離產(chǎn)生的誤差，在一定程度上降低了DV-hop算法的定位誤差。趙雁航等[8]提出一種基于跳距修正粒子群優(yōu)化的WSN 定位算法，該算法通過對錨節(jié)點廣播的數(shù)據(jù)分組結(jié)構(gòu)進行了改進，來對定位誤差進行加權(quán)處理并對定位的迭代過程進行優(yōu)化，提高了無線傳感器網(wǎng)絡(luò)的定位精度。吳玉成等[9]提出一種基于最優(yōu)節(jié)點通信半徑的改進DV-Hop定位算法，該算法通過分析網(wǎng)絡(luò)節(jié)點分布特性得到最優(yōu)節(jié)點通信半徑，并獲得受擾動影響最小的錨節(jié)點優(yōu)化分布方案，采用加權(quán)方法修正未知節(jié)點位置，改善了節(jié)點隨機分布的無線傳感器網(wǎng)絡(luò)的節(jié)點定位性能。朱敏等[10]提出一種基于DV-HOP改進的無線傳感器網(wǎng)絡(luò)定位算法，該算法采用新的方式計算未知節(jié)點與錨節(jié)點的距離，提出錨節(jié)點信任度的概念，并利用加權(quán)最小二乘法計算節(jié)點坐標。該方法在提高定位精度的同時，減少了節(jié)點的通信量和計算量。JIANG K等[11]提出一種基于最小二乘法和DV-Hop算法的無線傳感器網(wǎng)絡(luò)的目標定位算法，移動信標節(jié)點引入DV-Hop，允許在預(yù)先安排的方式下移動信標節(jié)點，并連續(xù)廣播其位置信息，形成多個虛擬信標。該算法可以減少網(wǎng)絡(luò)的定位成本和復(fù)雜性。ZHANG Q G等[12]提出一種基于改進粒子群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法，通過將DV-Hop算法和簡單的粒子群優(yōu)化（tsPSO）算法結(jié)合在一起，該算法迭代地搜索未知節(jié)點，抑制對定位精度的距離估計誤差，可以實現(xiàn)比DV-Hop算法更高的定位精度[13-15]。
1 NFDV-Hop定位算法
為了減少計算中的傳播誤差和提高定位精度，通過劃分最接近錨節(jié)點的距離方程，未知節(jié)點再通過從方程組利用獲得的信息更新位置信息。步驟如下：
(1)在這個步驟中，每個錨節(jié)點廣播信標包與它的位置（坐標）并且跳數(shù)的值初始化為1。當節(jié)點接收到信標數(shù)據(jù)包，將生成一個表(xi，yi，n(hop))，這個表代表著節(jié)點所接收到的每個錨節(jié)點的位置坐標以及跳數(shù)信息。如果接收到的數(shù)據(jù)包中關(guān)于達到一個特定的錨節(jié)點是包含較少的跳數(shù)值，則表中的跳數(shù)值被替換為收到的數(shù)據(jù)包的跳數(shù)值，并且在網(wǎng)絡(luò)中如果數(shù)據(jù)包被轉(zhuǎn)發(fā)，則跳數(shù)值增加1，否則該數(shù)據(jù)包將被丟棄。通過這種機制，網(wǎng)絡(luò)中的所有未知節(jié)點從每個錨節(jié)點獲得錨節(jié)點的坐標和最小的跳數(shù)值。
(2)未知節(jié)點從步驟(1)中獲得的錨節(jié)點的坐標后，未知節(jié)點計算錨節(jié)點跳數(shù)的大小，在這里假設(shè)節(jié)點的通信范圍為R，用d(i，j)表示節(jié)點i到錨節(jié)點j的歐幾里得距離，由于節(jié)點的跳距離是一定小于其通信距離，因此節(jié)點到錨節(jié)點所需的最小跳數(shù)為：
計算跳數(shù)后，未知節(jié)點使用跳數(shù)和錨節(jié)點之間的信息距離計算出錨節(jié)點的跳距離。為了使跳距離更加接近于實際跳距離的大小，未知節(jié)點采取錨節(jié)點之間的平均距離之比以及平均跳數(shù)來計算跳距離，得到：
而錨節(jié)點每一跳所產(chǎn)生的誤差，則與跳數(shù)以及錨節(jié)點i與錨節(jié)點j之間的距離有關(guān)：
一旦未知節(jié)點計算平均跳數(shù)的大小，則開始通過使用平均跳距離和各自的錨節(jié)點的最小跳數(shù)來估計與錨節(jié)點的距離，未知節(jié)點估計與第i個錨節(jié)點的距離為：
通過每一次的距離劃分來得到最接近錨節(jié)點真實距離的距離方程，假設(shè)第j個錨節(jié)點是最接近未知節(jié)點的錨節(jié)點i，首先得到距離的劃分方程為：
2 實驗仿真及分析
在仿真實驗中主要進行定位誤差和計算成本的分析，算法是在Matlab7.0仿真軟件上進行編程和運行，在模擬的仿真環(huán)境中，包括了對100個隨機生成的傳感器節(jié)點部署，并且模擬的部署環(huán)境為一個面積為200×200的區(qū)域，每個節(jié)點都具有50 m的通信半徑，在仿真中，定位誤差定義為：
為了更好地驗證本文所提出算法的性能，在實驗中分別與文獻[11]的基于最小二乘法的DV-Hop算法以及文獻[12]的基于改進粒子群優(yōu)化的DV-Hop算法進行了對比，并得到了仿真結(jié)果的比較圖。
圖1定位誤差是衡量定位算法性能的關(guān)鍵，為了驗證算法的定位誤差情況，實驗中在初始的節(jié)點數(shù)量的情況下增加節(jié)點數(shù)量，從初始的100個節(jié)點增加到300個，并得到在節(jié)點數(shù)量增加的過程中算法的定位誤差情況。從圖1的結(jié)果可以看出，節(jié)點數(shù)量越多，定位誤差越小，這是由于節(jié)點數(shù)量增多后，節(jié)點間的距離計算的誤差就相對減小，因此定位精度變高。從與基于最小二乘法的DV-Hop算法以及基于改進粒子群優(yōu)化的DV-Hop算法的對比情況可以看出，本文方法的定位誤差保持在27.5%以下，定位誤差最低時僅為5.7%。而對比算法的定位誤差最低時分別為17.8%和14.7%。因為基于最小二乘法的DV-Hop算法以及基于改進粒子群優(yōu)化的DV-Hop算法都是專注于修改其估計平均跳距離，通過減小平均跳距離誤差來提高未知節(jié)點距離的估算精度，再通過未知節(jié)點與錨節(jié)點的位置關(guān)系來實現(xiàn)坐標定位。然而平均跳距離作為估算距離始終存在一定的誤差，因此提高精度的能力有限。而NFDV-Hop算法除了通過多個錨節(jié)點的平均距離之比以及各自的錨節(jié)點的最小跳數(shù)來提高的平均跳距離的估算精度，而且估計的跳距離采用距離的劃分方程來得到未知節(jié)點的估計坐標，并引入位置比值來提高位置坐標的估算精度。
為了驗證算法的節(jié)能性能，在實驗中通過逐漸增加節(jié)點數(shù)量，得到網(wǎng)絡(luò)的平均節(jié)點能耗情況。從圖2的結(jié)果可以看出，本文的平均節(jié)點能耗相比對比算法少了很多，最高時僅為0.768 J，最低時為0.529 J，而兩種對比算法的最低平均節(jié)點能耗則分別為0.754 J和0.696 J，因此相比之下本文算法的節(jié)能性能更加顯著。
當錨節(jié)點在總的節(jié)點數(shù)量的占比增加時，意味著可以用來作為距離測量的錨節(jié)點數(shù)量增多，即定位精度會有一定提升。該組實驗即在錨節(jié)點占比提升的情況下，驗證算法的定位誤差。從圖3的結(jié)果可以看出，3種算法的定位誤差都隨著錨節(jié)點占比的提升而減少，定位精度有所提升。從曲線的分布情況來看，定位誤差最低的為本文的NFDV-Hop定位算法，其次為改進粒子群優(yōu)化的DV-Hop算法，而基于最小二乘法的DV-Hop算法的定位誤差最高。
圖4為錨節(jié)點在總的節(jié)點數(shù)量的占比增加時的平均節(jié)點能耗情況，由于本文算法的錨節(jié)點只需廣播一次自身的位置信息，因此錨節(jié)點占比的提升，意味著節(jié)點的總的通信成本降低，即平均節(jié)點能耗也降低。因此在錨節(jié)點在總的節(jié)點數(shù)量的占比增加時，本文算法的平均節(jié)點能耗的降低趨勢較為明顯，而另外兩種算法的能耗降低并不多，在錨節(jié)點占比為30%，本文算法的平均節(jié)點能耗為0.706 J，另外兩種算法分別為0.842 J和0.805 J。因為基于最小二乘法的DV-Hop算法在廣播消息上與DV-Hop算法相同，并沒有起到節(jié)能效果，而基于改進粒子群優(yōu)化的DV-Hop算法需要多次迭代，節(jié)能效果不理想。而NFDV-Hop定位算法專注于減小通信成本，通過有效減少信息的廣播次數(shù)減少節(jié)點的能量消耗，從實驗結(jié)果來看起到了一定的效果。
3 結(jié)論
本文提出了一種分布式多跳誤差估計的能量高效目標位置鎖定算法，該算法在DV-Hop算法的基礎(chǔ)上，針對DV-Hop算法定位精度不高、通信成本較大的問題，采用節(jié)能非測距優(yōu)化方法，錨節(jié)點只需廣播一次自身位置坐標信息，有效減少通信能耗。使用錨節(jié)點的平均跳數(shù)的大小以及錨節(jié)點間的平均跳距離來求得未知節(jié)點的位置坐標。在實驗中，通過驗證和對比的方法來體現(xiàn)本文算法在減小定位誤差和能量消耗上的有效性。
參考文獻
[1] YU C B，YU L，TAN J，et al.DV-Hop localization algorithm in WSN based on weighted of correction in hop distance[J].Applied Mechanics and Materials，2013，303：143-148.
[2] GUO Z，MIN L，LI H，et al.Improved DV-Hop localization algorithm based on RSSI value and hop correction[M].Advances in Wireless Sensor Networks.Springer Berlin Heidelberg，2013：97-102.
[3] CHAO J，HAN G，ZHU C，et al.Performance evaluation of DV-hop localization algorithm with mobility models for Mobile Wireless Sensor Networks[C].Wireless Communications and Mobile Computing Conference(IWCMC)，2013 9th International.IEEE，2013：1827-1832.
[4] HU Y，LI X.An improvement of DV-Hop localization algorithm for wireless sensor networks[J].Telecommunication Systems，2013，53(1)：13-18.
[5] ZHANG J，WANG H B，QIAO X G，et al.Node localization algorithm based on DV-HOP in wireless sensor networks[J].Applied Mechanics and Materials，2014，440：289-292.
[6] KUMAR S，LOBIYAL D K.Improvement over DV-Hop localization algorithm for wireless sensor networks[J].World Academy of Sciences, Engineering and Technology，2013：282-292.
[7] 譚志，張卉.基于節(jié)點間覆蓋關(guān)系的改進DV-Hop算法[J].北京郵電大學(xué)學(xué)報，2014，37(1)：35-38.
[8] 趙雁航，錢志鴻，尚小航，等.基于跳距修正粒子群優(yōu)化的WSN定位算法[J].通信學(xué)報，2013，34(9)：105-114.
[9] 吳玉成，李江雯.基于最優(yōu)節(jié)點通信半徑的改進DV-Hop定位算法[J].華南理工大學(xué)學(xué)報(自然科學(xué)版)，2012，40(6)：36-41.
[10] 朱敏，劉昊霖，張志宏，等.一種基于DV-HOP改進的無線傳感器網(wǎng)絡(luò)定位算法[J].四川大學(xué)學(xué)報(工程科學(xué)版)，2012，44(1)：93-98.
[11] JIANG K，YAO L，F(xiàn)ENG J.Wireless sensor networks target localization based on least square method and DV-Hop algorithm[J].Journal of Networks，2014，9(1)：176-182.
[12] ZHANG Q G，CHENG M.A node localization algorithm for wireless sensor network based on improved particle swarm optimization[M].Mechatronics and Automatic Control Systems.Springer International Publishing，2014：135-144.
[13] CHANDRASEKHAR V，SEAH W K G，CHOO Y S，et al.Localization in underwater sensor networks：survey and challenges[C].Proceedings of the 1st ACM international workshop on Underwater networks.ACM，2006：33-40.
[14] LIN J Z，LIU H，LI G，et al.Study for improved DV-Hop localization algorithm in WSN[J].Application Research of Computers，2009，26(4)：1272-1274.
[15] WANG Y，WANG X，WANG D，et al.Range-free localization using expected hop progress in wireless sensor networks[J].Parallel and Distributed Systems，IEEE Transactions on，2009，20(10)：1540-1552.