文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.171111
中文引用格式: 蔣從元,,楊杰. 基于分布式多跳誤差估計(jì)目標(biāo)位置感知算法[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ú)線傳感器網(wǎng)絡(luò)定位算法[1-6]的研究上,譚志等[7]提出一種基于節(jié)點(diǎn)間覆蓋關(guān)系的改進(jìn)DV-Hop算法,,該方法根據(jù)兩節(jié)點(diǎn)間的通信覆蓋率引入跳數(shù)系數(shù),,降低了每跳距離產(chǎn)生的誤差,在一定程度上降低了DV-hop算法的定位誤差,。趙雁航等[8]提出一種基于跳距修正粒子群優(yōu)化的WSN 定位算法,,該算法通過(guò)對(duì)錨節(jié)點(diǎn)廣播的數(shù)據(jù)分組結(jié)構(gòu)進(jìn)行了改進(jìn),來(lái)對(duì)定位誤差進(jìn)行加權(quán)處理并對(duì)定位的迭代過(guò)程進(jìn)行優(yōu)化,,提高了無(wú)線傳感器網(wǎng)絡(luò)的定位精度,。吳玉成等[9]提出一種基于最優(yōu)節(jié)點(diǎn)通信半徑的改進(jìn)DV-Hop定位算法,該算法通過(guò)分析網(wǎng)絡(luò)節(jié)點(diǎn)分布特性得到最優(yōu)節(jié)點(diǎn)通信半徑,,并獲得受擾動(dòng)影響最小的錨節(jié)點(diǎn)優(yōu)化分布方案,,采用加權(quán)方法修正未知節(jié)點(diǎn)位置,改善了節(jié)點(diǎn)隨機(jī)分布的無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位性能,。朱敏等[10]提出一種基于DV-HOP改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)定位算法,,該算法采用新的方式計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離,,提出錨節(jié)點(diǎn)信任度的概念,并利用加權(quán)最小二乘法計(jì)算節(jié)點(diǎn)坐標(biāo),。該方法在提高定位精度的同時(shí),,減少了節(jié)點(diǎn)的通信量和計(jì)算量。JIANG K等[11]提出一種基于最小二乘法和DV-Hop算法的無(wú)線傳感器網(wǎng)絡(luò)的目標(biāo)定位算法,,移動(dòng)信標(biāo)節(jié)點(diǎn)引入DV-Hop,,允許在預(yù)先安排的方式下移動(dòng)信標(biāo)節(jié)點(diǎn),并連續(xù)廣播其位置信息,,形成多個(gè)虛擬信標(biāo),。該算法可以減少網(wǎng)絡(luò)的定位成本和復(fù)雜性。ZHANG Q G等[12]提出一種基于改進(jìn)粒子群優(yōu)化算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法,,通過(guò)將DV-Hop算法和簡(jiǎn)單的粒子群優(yōu)化(tsPSO)算法結(jié)合在一起,,該算法迭代地搜索未知節(jié)點(diǎn),抑制對(duì)定位精度的距離估計(jì)誤差,,可以實(shí)現(xiàn)比DV-Hop算法更高的定位精度[13-15],。
1 NFDV-Hop定位算法
為了減少計(jì)算中的傳播誤差和提高定位精度,通過(guò)劃分最接近錨節(jié)點(diǎn)的距離方程,,未知節(jié)點(diǎn)再通過(guò)從方程組利用獲得的信息更新位置信息,。步驟如下:
(1)在這個(gè)步驟中,每個(gè)錨節(jié)點(diǎn)廣播信標(biāo)包與它的位置(坐標(biāo))并且跳數(shù)的值初始化為1,。當(dāng)節(jié)點(diǎn)接收到信標(biāo)數(shù)據(jù)包,,將生成一個(gè)表(xi,yi,,n(hop)),,這個(gè)表代表著節(jié)點(diǎn)所接收到的每個(gè)錨節(jié)點(diǎn)的位置坐標(biāo)以及跳數(shù)信息。如果接收到的數(shù)據(jù)包中關(guān)于達(dá)到一個(gè)特定的錨節(jié)點(diǎn)是包含較少的跳數(shù)值,,則表中的跳數(shù)值被替換為收到的數(shù)據(jù)包的跳數(shù)值,,并且在網(wǎng)絡(luò)中如果數(shù)據(jù)包被轉(zhuǎn)發(fā),則跳數(shù)值增加1,,否則該數(shù)據(jù)包將被丟棄,。通過(guò)這種機(jī)制,網(wǎng)絡(luò)中的所有未知節(jié)點(diǎn)從每個(gè)錨節(jié)點(diǎn)獲得錨節(jié)點(diǎn)的坐標(biāo)和最小的跳數(shù)值,。
(2)未知節(jié)點(diǎn)從步驟(1)中獲得的錨節(jié)點(diǎn)的坐標(biāo)后,,未知節(jié)點(diǎn)計(jì)算錨節(jié)點(diǎn)跳數(shù)的大小,,在這里假設(shè)節(jié)點(diǎn)的通信范圍為R,,用d(i,j)表示節(jié)點(diǎn)i到錨節(jié)點(diǎn)j的歐幾里得距離,,由于節(jié)點(diǎn)的跳距離是一定小于其通信距離,,因此節(jié)點(diǎn)到錨節(jié)點(diǎn)所需的最小跳數(shù)為:
計(jì)算跳數(shù)后,,未知節(jié)點(diǎn)使用跳數(shù)和錨節(jié)點(diǎn)之間的信息距離計(jì)算出錨節(jié)點(diǎn)的跳距離。為了使跳距離更加接近于實(shí)際跳距離的大小,,未知節(jié)點(diǎn)采取錨節(jié)點(diǎn)之間的平均距離之比以及平均跳數(shù)來(lái)計(jì)算跳距離,,得到:
而錨節(jié)點(diǎn)每一跳所產(chǎn)生的誤差,則與跳數(shù)以及錨節(jié)點(diǎn)i與錨節(jié)點(diǎn)j之間的距離有關(guān):
一旦未知節(jié)點(diǎn)計(jì)算平均跳數(shù)的大小,,則開始通過(guò)使用平均跳距離和各自的錨節(jié)點(diǎn)的最小跳數(shù)來(lái)估計(jì)與錨節(jié)點(diǎn)的距離,,未知節(jié)點(diǎn)估計(jì)與第i個(gè)錨節(jié)點(diǎn)的距離為:
通過(guò)每一次的距離劃分來(lái)得到最接近錨節(jié)點(diǎn)真實(shí)距離的距離方程,假設(shè)第j個(gè)錨節(jié)點(diǎn)是最接近未知節(jié)點(diǎn)的錨節(jié)點(diǎn)i,,首先得到距離的劃分方程為:
2 實(shí)驗(yàn)仿真及分析
在仿真實(shí)驗(yàn)中主要進(jìn)行定位誤差和計(jì)算成本的分析,,算法是在Matlab7.0仿真軟件上進(jìn)行編程和運(yùn)行,在模擬的仿真環(huán)境中,,包括了對(duì)100個(gè)隨機(jī)生成的傳感器節(jié)點(diǎn)部署,,并且模擬的部署環(huán)境為一個(gè)面積為200×200的區(qū)域,每個(gè)節(jié)點(diǎn)都具有50 m的通信半徑,,在仿真中,,定位誤差定義為:
為了更好地驗(yàn)證本文所提出算法的性能,在實(shí)驗(yàn)中分別與文獻(xiàn)[11]的基于最小二乘法的DV-Hop算法以及文獻(xiàn)[12]的基于改進(jìn)粒子群優(yōu)化的DV-Hop算法進(jìn)行了對(duì)比,,并得到了仿真結(jié)果的比較圖,。
圖1定位誤差是衡量定位算法性能的關(guān)鍵,為了驗(yàn)證算法的定位誤差情況,,實(shí)驗(yàn)中在初始的節(jié)點(diǎn)數(shù)量的情況下增加節(jié)點(diǎn)數(shù)量,,從初始的100個(gè)節(jié)點(diǎn)增加到300個(gè),并得到在節(jié)點(diǎn)數(shù)量增加的過(guò)程中算法的定位誤差情況,。從圖1的結(jié)果可以看出,,節(jié)點(diǎn)數(shù)量越多,定位誤差越小,,這是由于節(jié)點(diǎn)數(shù)量增多后,,節(jié)點(diǎn)間的距離計(jì)算的誤差就相對(duì)減小,因此定位精度變高,。從與基于最小二乘法的DV-Hop算法以及基于改進(jìn)粒子群優(yōu)化的DV-Hop算法的對(duì)比情況可以看出,,本文方法的定位誤差保持在27.5%以下,定位誤差最低時(shí)僅為5.7%,。而對(duì)比算法的定位誤差最低時(shí)分別為17.8%和14.7%,。因?yàn)榛谧钚《朔ǖ腄V-Hop算法以及基于改進(jìn)粒子群優(yōu)化的DV-Hop算法都是專注于修改其估計(jì)平均跳距離,通過(guò)減小平均跳距離誤差來(lái)提高未知節(jié)點(diǎn)距離的估算精度,,再通過(guò)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的位置關(guān)系來(lái)實(shí)現(xiàn)坐標(biāo)定位,。然而平均跳距離作為估算距離始終存在一定的誤差,因此提高精度的能力有限,。而NFDV-Hop算法除了通過(guò)多個(gè)錨節(jié)點(diǎn)的平均距離之比以及各自的錨節(jié)點(diǎn)的最小跳數(shù)來(lái)提高的平均跳距離的估算精度,,而且估計(jì)的跳距離采用距離的劃分方程來(lái)得到未知節(jié)點(diǎn)的估計(jì)坐標(biāo),,并引入位置比值來(lái)提高位置坐標(biāo)的估算精度。
為了驗(yàn)證算法的節(jié)能性能,,在實(shí)驗(yàn)中通過(guò)逐漸增加節(jié)點(diǎn)數(shù)量,,得到網(wǎng)絡(luò)的平均節(jié)點(diǎn)能耗情況。從圖2的結(jié)果可以看出,,本文的平均節(jié)點(diǎn)能耗相比對(duì)比算法少了很多,,最高時(shí)僅為0.768 J,最低時(shí)為0.529 J,,而兩種對(duì)比算法的最低平均節(jié)點(diǎn)能耗則分別為0.754 J和0.696 J,,因此相比之下本文算法的節(jié)能性能更加顯著。
當(dāng)錨節(jié)點(diǎn)在總的節(jié)點(diǎn)數(shù)量的占比增加時(shí),,意味著可以用來(lái)作為距離測(cè)量的錨節(jié)點(diǎn)數(shù)量增多,,即定位精度會(huì)有一定提升。該組實(shí)驗(yàn)即在錨節(jié)點(diǎn)占比提升的情況下,,驗(yàn)證算法的定位誤差,。從圖3的結(jié)果可以看出,3種算法的定位誤差都隨著錨節(jié)點(diǎn)占比的提升而減少,,定位精度有所提升,。從曲線的分布情況來(lái)看,定位誤差最低的為本文的NFDV-Hop定位算法,,其次為改進(jìn)粒子群優(yōu)化的DV-Hop算法,,而基于最小二乘法的DV-Hop算法的定位誤差最高。
圖4為錨節(jié)點(diǎn)在總的節(jié)點(diǎn)數(shù)量的占比增加時(shí)的平均節(jié)點(diǎn)能耗情況,,由于本文算法的錨節(jié)點(diǎn)只需廣播一次自身的位置信息,,因此錨節(jié)點(diǎn)占比的提升,意味著節(jié)點(diǎn)的總的通信成本降低,,即平均節(jié)點(diǎn)能耗也降低,。因此在錨節(jié)點(diǎn)在總的節(jié)點(diǎn)數(shù)量的占比增加時(shí),本文算法的平均節(jié)點(diǎn)能耗的降低趨勢(shì)較為明顯,,而另外兩種算法的能耗降低并不多,,在錨節(jié)點(diǎn)占比為30%,本文算法的平均節(jié)點(diǎn)能耗為0.706 J,,另外兩種算法分別為0.842 J和0.805 J,。因?yàn)榛谧钚《朔ǖ腄V-Hop算法在廣播消息上與DV-Hop算法相同,并沒有起到節(jié)能效果,,而基于改進(jìn)粒子群優(yōu)化的DV-Hop算法需要多次迭代,,節(jié)能效果不理想。而NFDV-Hop定位算法專注于減小通信成本,,通過(guò)有效減少信息的廣播次數(shù)減少節(jié)點(diǎn)的能量消耗,,從實(shí)驗(yàn)結(jié)果來(lái)看起到了一定的效果。
3 結(jié)論
本文提出了一種分布式多跳誤差估計(jì)的能量高效目標(biāo)位置鎖定算法,,該算法在DV-Hop算法的基礎(chǔ)上,,針對(duì)DV-Hop算法定位精度不高、通信成本較大的問(wèn)題,,采用節(jié)能非測(cè)距優(yōu)化方法,,錨節(jié)點(diǎn)只需廣播一次自身位置坐標(biāo)信息,有效減少通信能耗,。使用錨節(jié)點(diǎn)的平均跳數(shù)的大小以及錨節(jié)點(diǎn)間的平均跳距離來(lái)求得未知節(jié)點(diǎn)的位置坐標(biāo),。在實(shí)驗(yàn)中,通過(guò)驗(yàn)證和對(duì)比的方法來(lái)體現(xiàn)本文算法在減小定位誤差和能量消耗上的有效性,。
參考文獻(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é)點(diǎn)間覆蓋關(guān)系的改進(jìn)DV-Hop算法[J].北京郵電大學(xué)學(xué)報(bào),2014,,37(1):35-38.
[8] 趙雁航,,錢志鴻,,尚小航,等.基于跳距修正粒子群優(yōu)化的WSN定位算法[J].通信學(xué)報(bào),,2013,,34(9):105-114.
[9] 吳玉成,李江雯.基于最優(yōu)節(jié)點(diǎn)通信半徑的改進(jìn)DV-Hop定位算法[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),,2012,,40(6):36-41.
[10] 朱敏,劉昊霖,,張志宏,,等.一種基于DV-HOP改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].四川大學(xué)學(xué)報(bào)(工程科學(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.