無(wú)線傳感器網(wǎng)絡(luò)中改進(jìn)的DV-Hop定位算法*

李鳳超，高美鳳

(江南大學(xué) 輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫 214122)

0 引 言

目前，無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位技術(shù)在理論上取得了很大進(jìn)展，提出了很多定位算法。

距離矢量跳(distance vector hop,DV-Hop)定位算法是一種非測(cè)距定位算法，具有復(fù)雜度低、可擴(kuò)展性好等優(yōu)點(diǎn)[1]，但其定位精度較低，針對(duì)這一問(wèn)題，進(jìn)行了很多方面的改進(jìn)和研究，例如：TMCD-DV-Hop算法[2]在傳統(tǒng)DV-Hop定位算法中加入閾值機(jī)制進(jìn)行錨節(jié)點(diǎn)篩選，并對(duì)平均每跳距離(簡(jiǎn)稱平均跳距)進(jìn)行校正。同一未知節(jié)點(diǎn)對(duì)不同的錨節(jié)點(diǎn)采用不同的平均跳距且利用Quasi-Newton方法對(duì)定位結(jié)果進(jìn)行優(yōu)化[3]。利用RSSI測(cè)距技術(shù)進(jìn)行改進(jìn)，通過(guò)將未知節(jié)點(diǎn)升級(jí)為次錨節(jié)點(diǎn)，根據(jù)非線性共軛梯度法進(jìn)行逼近以減小誤差，有效提高了定位精度[4,5]。對(duì)未知節(jié)點(diǎn)接收到的錨節(jié)點(diǎn)平均跳距加權(quán)處理以提高精度[6]。文獻(xiàn)[7]使用蝙蝠算法(bat algorithm,BA)對(duì)DV-Hop定位的結(jié)果進(jìn)行優(yōu)化。文獻(xiàn)[8]使用三角形內(nèi)點(diǎn)測(cè)試(approximate point-in-triangulation test,APIT)與DV-Hop相結(jié)合以減小定位誤差。上述改進(jìn)算法存在的問(wèn)題有：1)需要額外投入硬件成本;2)引入迭代算法增加了時(shí)間和能量的消耗，3)重點(diǎn)對(duì)錨節(jié)點(diǎn)平均跳距的改進(jìn)而忽略了距離計(jì)算時(shí)的誤差。

本文在DV-Hop定位算法的基礎(chǔ)之上，通過(guò)對(duì)錨節(jié)點(diǎn)平均跳距、未知節(jié)點(diǎn)平均跳距的改進(jìn)，同時(shí)利用平均跳距作用域減小計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間距離時(shí)產(chǎn)生的誤差。仿真結(jié)果表明，本文所提改進(jìn)算法在一定程度上提高了節(jié)點(diǎn)的定位精度。

1 傳統(tǒng)DV-Hop定位算法[9]誤差分析

1)平均跳距誤差：錨節(jié)點(diǎn)通過(guò)無(wú)線傳感器網(wǎng)絡(luò)中的其他錨節(jié)點(diǎn)坐標(biāo)和相互之間的跳數(shù)得到平均跳距，未知節(jié)點(diǎn)直接選取距離最近的錨節(jié)點(diǎn)的平均跳距作為本身的平均跳距；在這個(gè)過(guò)程中，傳統(tǒng)DV-Hop算法并未對(duì)錨節(jié)點(diǎn)平均跳距計(jì)算以及未知節(jié)點(diǎn)平均跳距選取過(guò)程產(chǎn)生的誤差作處理，直接參與最小二乘法的計(jì)算會(huì)造成誤差累積。

2)距離計(jì)算誤差：DV-Hop算法通過(guò)未知節(jié)點(diǎn)的平均跳距與最小跳數(shù)的乘積來(lái)估計(jì)未知節(jié)點(diǎn)和錨節(jié)點(diǎn)間的直線距離，在這個(gè)過(guò)程中誤差的產(chǎn)生有2方面：利用折線距離代替直線距離所產(chǎn)生的不可消除誤差；在計(jì)算折線距離時(shí)忽略每個(gè)跳段距離的差異，統(tǒng)一用未知節(jié)點(diǎn)的平均跳距代替所產(chǎn)生的誤差。后者可以通過(guò)本文提出的平均跳距作用域減小或消除。

2 DV-Hop定位算法的改進(jìn)

2.1 錨節(jié)點(diǎn)平均跳距的改進(jìn)[10]

本文改進(jìn)策略包括首先剔除會(huì)引入較大誤差的錨節(jié)點(diǎn)，其次將參與計(jì)算的錨節(jié)點(diǎn)進(jìn)行加權(quán)處理。

對(duì)于矩形分布區(qū)域來(lái)說(shuō)，定義最大理想跳數(shù)k為

(1)

式中d1～d4為錨節(jié)點(diǎn)i距離矩形分布范圍4個(gè)頂點(diǎn)的距離。在理想情況下平均跳距與通信半徑接近，當(dāng)錨節(jié)點(diǎn)接收到距離其他錨節(jié)點(diǎn)的最小跳數(shù)超出了節(jié)點(diǎn)分布范圍的最大理想跳數(shù)說(shuō)明該路徑中錨節(jié)點(diǎn)間的共線度較低，將其剔除。

采用加權(quán)處理的方法計(jì)算錨節(jié)點(diǎn)i的平均跳距。定義

(2)

式中dij為錨節(jié)點(diǎn)i和j之間的實(shí)際距離；R為通信半徑；hopsij為錨節(jié)點(diǎn)i和j之間的最小跳數(shù)。錨節(jié)點(diǎn)j在參與錨節(jié)點(diǎn)i平均跳距計(jì)算過(guò)程中，其權(quán)重為

(3)

式中m為參與錨節(jié)點(diǎn)i平均跳距計(jì)算的錨節(jié)點(diǎn)個(gè)數(shù)。錨節(jié)點(diǎn)i的平均跳距為

(4)

2.2 未知節(jié)點(diǎn)平均跳距的改進(jìn)

本文基于文獻(xiàn)[3，11]對(duì)未知節(jié)點(diǎn)平均跳距進(jìn)行了改進(jìn)，當(dāng)錨節(jié)點(diǎn)和未知節(jié)點(diǎn)在一跳范圍內(nèi)時(shí)，未知節(jié)點(diǎn)直接取最近的錨節(jié)點(diǎn)的平均跳距作為自己的平均跳距；未知節(jié)點(diǎn)和錨節(jié)點(diǎn)間最小跳數(shù)在1～M跳之間時(shí)取M跳內(nèi)的所有錨節(jié)點(diǎn)平均跳距的均值；未知節(jié)點(diǎn)和錨節(jié)點(diǎn)之間最小跳數(shù)在M跳之外，取全局平均跳距。即未知節(jié)點(diǎn)k的平均跳距為

(5)

式中m為未知節(jié)點(diǎn)k周圍M跳范圍內(nèi)的錨節(jié)點(diǎn)個(gè)數(shù)；n為整個(gè)無(wú)線傳感器網(wǎng)絡(luò)中的錨節(jié)點(diǎn)個(gè)數(shù)。閾值M為

式中A為整個(gè)無(wú)線傳感器網(wǎng)絡(luò)覆蓋區(qū)域面積；Lh為每個(gè)未知節(jié)點(diǎn)定位需要的平均錨節(jié)點(diǎn)個(gè)數(shù)；Tn為節(jié)點(diǎn)總數(shù)；Lp為錨節(jié)點(diǎn)比例；Hmax為錨節(jié)點(diǎn)和未知節(jié)點(diǎn)之間最小跳數(shù)的最大值。在滿足網(wǎng)絡(luò)中所有未知節(jié)點(diǎn)定位的情況下，M選取最小值參與運(yùn)算；在節(jié)點(diǎn)分布不均的場(chǎng)合，閾值M需要選擇略大一些，以滿足整個(gè)網(wǎng)絡(luò)的覆蓋[11]。

按照式(5)，未知節(jié)點(diǎn)在不同情況下，根據(jù)與錨節(jié)點(diǎn)之間的最小跳數(shù)選擇不同的平均跳距，克服了傳統(tǒng)DV-Hop算法中單純采用最近的錨節(jié)點(diǎn)的平均跳距帶來(lái)的誤差，同時(shí)，當(dāng)未知節(jié)點(diǎn)和錨節(jié)點(diǎn)在1跳范圍內(nèi)時(shí)又保證了平均跳距的精度。

2.3 平均跳距作用域改進(jìn)

當(dāng)錨節(jié)點(diǎn)和未知節(jié)點(diǎn)附近的節(jié)點(diǎn)密度差別較大時(shí)，二者的平均跳距差別較大，單純采用未知節(jié)點(diǎn)的平均跳距計(jì)算距離會(huì)造成較大誤差。本文提出了平均跳距作用域，根據(jù)前述得到錨節(jié)點(diǎn)平均跳距和未知節(jié)點(diǎn)平均跳距，在計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離時(shí)靠近未知節(jié)點(diǎn)的一半跳數(shù)采用未知節(jié)點(diǎn)平均跳距計(jì)算距離，另一半采用錨節(jié)點(diǎn)平均跳距。計(jì)算過(guò)程如下

dik=Hopsizei×hopsit+Hopsizek×hopstk

(6)

式中Hopsizei為錨節(jié)點(diǎn)i的平均跳距；Hopsizek為未知節(jié)點(diǎn)k的平均跳距，且滿足

hopsit=hopstk=hopsik/2

改進(jìn)后的DV-Hop定位算法具體步驟如下：

1)錨節(jié)點(diǎn)通過(guò)未知節(jié)點(diǎn)的轉(zhuǎn)發(fā)得到其他錨節(jié)點(diǎn)的坐標(biāo)及與其他錨節(jié)點(diǎn)間的最小跳數(shù)；

2)按照2.1節(jié)的篩選原則選取參與平均跳距計(jì)算的錨節(jié)點(diǎn)并進(jìn)行加權(quán)處理得到錨節(jié)點(diǎn)平均跳距；

3)按照2.2節(jié)的選取原則決定每個(gè)未知節(jié)點(diǎn)的平均跳距；

4)根據(jù)平均跳距作用域計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離；

5)未知節(jié)點(diǎn)利用最小二乘法完成定位。

3 仿真分析

為了驗(yàn)證本文算法的有效性，在MATLAB平臺(tái)仿真分析，同時(shí)與文獻(xiàn)[3，11]中的改進(jìn)策略進(jìn)行對(duì)比。仿真模型為100個(gè)節(jié)點(diǎn)隨機(jī)分布于100 m×100 m的區(qū)域內(nèi)，考慮不同錨節(jié)點(diǎn)比例、節(jié)點(diǎn)通信半徑對(duì)定位誤差的影響。未知節(jié)點(diǎn)k的定位誤差為

(7)

每個(gè)實(shí)驗(yàn)重復(fù)進(jìn)行100次，取平均值作為最終結(jié)果，在通信半徑R=30 m時(shí)比較錨節(jié)點(diǎn)比例對(duì)定位誤差的影響，結(jié)果如圖1所示。隨著錨節(jié)點(diǎn)比例的增大，4種算法的定位誤差均減??；錨節(jié)點(diǎn)比例較小時(shí)，無(wú)線傳感器網(wǎng)絡(luò)區(qū)域中錨節(jié)點(diǎn)分布不均勻，隨機(jī)性大，文獻(xiàn)[3，11]改進(jìn)方案中大部分未知節(jié)點(diǎn)選取全局平均跳距作為自身跳距，而本文算法通過(guò)1跳和閾值M的雙重分割具有明顯效果。當(dāng)錨節(jié)點(diǎn)比例在15 %～30 %時(shí)，文獻(xiàn)[11]中利用閾值M的定位效果優(yōu)于文獻(xiàn)[3]中單純1跳分割的方案，而本文算法在閾值基礎(chǔ)上再次分開處理，效果更好。錨節(jié)點(diǎn)比例超過(guò)30 %時(shí)，定位誤差隨著錨節(jié)點(diǎn)增大不再明顯減小，本文算法仍優(yōu)于其他算法。

圖1 不同錨節(jié)點(diǎn)比例下的定位誤差

在錨節(jié)點(diǎn)比例為20 %時(shí)，比較通信半徑對(duì)定位誤差的影響，結(jié)果如圖2所示。隨著通信半徑的增大，各種算法的定位誤差均減?。划?dāng)通信半徑小于25 m時(shí)，1跳距離小，文獻(xiàn)[3]相比本文改進(jìn)算法和文獻(xiàn)[11]有更多的未知節(jié)點(diǎn)選取全局平均跳距作為自身平均跳距帶來(lái)了誤差的累積，當(dāng)通信半徑大于28m時(shí)，錨節(jié)點(diǎn)經(jīng)過(guò)篩選與加權(quán)后得到平均跳距取得了較好的效果，同時(shí)，平均跳距作用域進(jìn)一步減小了誤差，本文算法相比其他改進(jìn)算法均有不同程度的優(yōu)勢(shì)。

圖2 不同通信半徑下的定位誤差

4 結(jié)束語(yǔ)

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)自定位誤差較大的問(wèn)題，對(duì)傳統(tǒng)DV-Hop定位算法進(jìn)行了改進(jìn)，仿真結(jié)果表明：在錨節(jié)點(diǎn)比例適中、通信半徑較小的情況下本文算法可以減小定位誤差，提高定位精度，適用于低功耗、大范圍的無(wú)線傳感器網(wǎng)絡(luò)環(huán)境。

[1] Niculescu D,Nath B.Ad hoc positioning system (APS) using AOA[C]∥The Twenty-Second Annual Joint Conference of the IEEE Computer and Communications,IEEE Societies,INFOCOM 2003,LEEE,2003:1734-1743.

[2] 向滿天,王 勝,楊友華.基于閾值機(jī)制與距離校正的 WSN s改進(jìn) DV-Hop 定位算法[J].傳感技術(shù)學(xué)報(bào),2016,29(6):920-926.

[3] Shi Q,Zhou J,Zhang J,et al.An improved scheme for DV-Hop in WSNs[C]∥11th International Conference on Wireless Communications,Networking and Mobile Computing,WiCOM 2015,IET,2015:1-4.

[4] 宋倩雯,郭松濤,柏艾林,等.無(wú)線傳感器網(wǎng)絡(luò)中一種改進(jìn)的DV-Hop定位算法[J].重慶大學(xué)學(xué)報(bào),2015,38(4):128-136.

[5] Shen S,Yang B,Qian K,et al.An efficient localization algorithm in wireless sensor networks[C]∥International Symposium on Computing & Networking,IEEE,2015:291-294.

[6] 趙芝璞,吳 棟,王 艷,等.基于平均跳距和位置優(yōu)化的改進(jìn) DV-Hop 定位算法[J].系統(tǒng)仿真學(xué)報(bào),2016,28(6):1273-1280.

[7] 白 偉,李鳳英,鄭海洋,等.基于BADV-Hop的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法[J].傳感器與微系統(tǒng),2014,33(10):118-120.

[8] 何登平,范茂林.一種基于APIT的無(wú)線傳感器網(wǎng)絡(luò)混合型定位算法[J].傳感器與微系統(tǒng),2015,34(2):133-135.

[9] Kumar S,Lobiyal D K.An advanced DV-Hop localization algorithm for wireless sensor networks [J].Wireless Personal Communications,2013,71 (2):1365-1385.

[10] Wang Y,Qian K.An improved DV-Hop positioning algorithm based on Hop distance correction[C]∥2014 11th International Computer Conference on Wavelet Active Media Technology and Information Processing (ICCWAMTIP),IEEE,2014:415-418.

[11] Hu Y,Li X.An improvement of DV-Hop localization algorithm for wireless sensor networks[J].Telecommunication Systems,2013,53(1):13-18.