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

李麗娜，王 越，張曉東，雷昊東

(遼寧大學(xué) 物理學(xué)院，遼寧 沈陽)

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

李麗娜，王 越，張曉東，雷昊東

(遼寧大學(xué) 物理學(xué)院，遼寧 沈陽)

針對(duì)DV-hop定位算法定位精度不高的問題，提出了一種改進(jìn)的DV-hop算法，并詳細(xì)介紹了改進(jìn)的基本原理.在算法第二階段融入了RSSI算法修正平均每跳距離，第三階段采用先減后平方的方法對(duì)極大似然估計(jì)法計(jì)算步驟進(jìn)行了改進(jìn)，減小了計(jì)算誤差.并利用matlab對(duì)改進(jìn)算法進(jìn)行了仿真分析.仿真結(jié)果表明：與傳統(tǒng)的dv-hop定位算法相比，改進(jìn)算法定位誤差降低了21.8%，使定位精度有了較大的提高，且不需要增加額外的硬件開銷.

DV-Hop定位算法；無線傳感網(wǎng)絡(luò)；極大似然法

0 引言

DV-Hop定位算法是將距離矢量路由與GPS原理相結(jié)合的一種非測距分布式定位算法，其優(yōu)點(diǎn)是功耗小，成本低，計(jì)算速度快等，但是由于DV-Hop屬于非測距的定位算法，受外界環(huán)境影響較大，其定位精度還不夠高.近幾年關(guān)于此算法的研究逐漸深入，本文在原有的基礎(chǔ)上，對(duì)平均每跳距離進(jìn)行修正并調(diào)整算法第三階段的計(jì)算方式，最終使算法定位更精準(zhǔn)，實(shí)驗(yàn)驗(yàn)證了本文算法的有效性.

1 基于距離矢量的定位算法

距離矢量的概念是由有線網(wǎng)絡(luò)的路由協(xié)議中引入的，將距離矢量視為設(shè)備間傳遞數(shù)據(jù)包需要經(jīng)過的跳數(shù)，用距離矢量來衡量數(shù)據(jù)包從一個(gè)節(jié)點(diǎn)傳送到另一個(gè)節(jié)點(diǎn)需要花費(fèi)的成本，由此可確定距離矢量與節(jié)點(diǎn)間的物理距離沒有直接聯(lián)系[1].

將距離矢量引入到無線傳感網(wǎng)絡(luò)中，定義傳感器節(jié)點(diǎn)間傳輸數(shù)據(jù)包需要經(jīng)過的跳數(shù)為距離矢量.無線傳輸模式下，無線節(jié)點(diǎn)間數(shù)據(jù)包傳輸?shù)奶鴶?shù)與節(jié)點(diǎn)距離間存在一定關(guān)系，因此可以基于距離矢量對(duì)節(jié)點(diǎn)進(jìn)行定位，本文就是基于距離矢量的DV-hop定位算法，并對(duì)算法的每個(gè)階段可能產(chǎn)生的誤差原因進(jìn)行仔細(xì)分析，對(duì)其不足之處進(jìn)行了研究，進(jìn)而得出基于距離矢量算法普遍存在的問題以及改進(jìn)的方向.

2 DV-Hop定位算法研究和分析

2.1 傳統(tǒng)的DV-Hop 定位算法原理

DV-Hop定位算法具有方法簡單，定位精度較高的特點(diǎn).DV-Hop 定位算法無需獲得節(jié)點(diǎn)之間的實(shí)際距離，僅僅需要利用網(wǎng)絡(luò)連通性估計(jì)距離.它的定位過程分以下三個(gè)階段：

1)計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的最小跳數(shù)值

網(wǎng)絡(luò)中的各錨節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播包括自身信息的數(shù)據(jù)包，跳數(shù)初始值置為0.未知節(jié)點(diǎn)記錄每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)值，并將跳數(shù)值加1轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn).

2)每個(gè)錨節(jié)點(diǎn)利用其他參考節(jié)點(diǎn)的位置信息及最小跳數(shù)來計(jì)算平均每跳的距離，并將其作為校正值廣播至網(wǎng)絡(luò)中.當(dāng)接收到校正值后，節(jié)點(diǎn)根據(jù)式(1)計(jì)算與錨節(jié)點(diǎn)之間的距離.

(1)

式中(xi,yi)，(xj,yj)為錨節(jié)點(diǎn)i與錨節(jié)點(diǎn)j的坐標(biāo)，Hopsi為錨節(jié)點(diǎn)i和j之間的跳數(shù).

3)未知節(jié)點(diǎn)收到其到至少三個(gè)錨節(jié)點(diǎn)的估計(jì)距離后，利用極大似然估計(jì)或三邊測量法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)[2].

錨節(jié)點(diǎn)和未知節(jié)點(diǎn)算法流程圖分別如圖1及圖2所示.

2.2 DV-Hop算法誤差分析

DV-Hop算法的第一階段，由于傳感器節(jié)點(diǎn)隨機(jī)分布且廣播分組過程中可能存在沖突等因素，節(jié)點(diǎn)到錨節(jié)點(diǎn)的最小跳數(shù)存在有一定偏差.第二階段，在錨節(jié)點(diǎn)估算平均每跳距離時(shí)，利用的是除本節(jié)點(diǎn)外所有其他錨節(jié)點(diǎn)，所以得到的是全網(wǎng)范圍內(nèi)的平均每跳距離，不能反映本錨節(jié)點(diǎn)局部范圍內(nèi)的網(wǎng)絡(luò)密度分布情況，因此采用該方法得出的平均每跳距離在密度均勻的網(wǎng)絡(luò)中影響不大，但在密度不均勻的網(wǎng)絡(luò)中，會(huì)造成較大誤差[3]. 第三階段，極大似然與三邊定位等傳統(tǒng)定位算法仍存在較大誤差，所以在計(jì)算階段可考慮對(duì)傳統(tǒng)數(shù)學(xué)算法的改進(jìn).

圖1 錨節(jié)點(diǎn)算法流程圖

圖2 未知節(jié)點(diǎn)算法流程圖

3 DV-HOP算法的改進(jìn)

第一階段，為了減小環(huán)境變化對(duì)算法產(chǎn)生的影響，可由人工布置錨節(jié)點(diǎn)，增加系統(tǒng)定位準(zhǔn)確度.

第二階段，未知節(jié)點(diǎn)和錨節(jié)點(diǎn)如果是以單跳方式通信，它們之間的距離即視為平均每跳距離.在通信范圍內(nèi)無論其相距多遠(yuǎn)，都將其跳數(shù)估計(jì)為一跳，而每跳的距離不同，用跳數(shù)乘以平均跳距來計(jì)算錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離，必然偏離實(shí)際距離，造成節(jié)點(diǎn)定位出現(xiàn)較大的誤差.如圖3中的錨節(jié)點(diǎn)L1與錨節(jié)點(diǎn)L2之間的最短路徑，其中每跳的長度都不同，只有最后一跳的長度接近于實(shí)際值，即節(jié)點(diǎn)的通信半徑[4].

圖3 節(jié)點(diǎn)路徑示意圖

為了避免實(shí)際距離與平均每跳距離之間出現(xiàn)較大的誤差，可以根據(jù)RSSI損耗模型估算出兩個(gè)節(jié)點(diǎn)之間的實(shí)際距離.如果平均每跳距離在損耗模型值范圍內(nèi)，則將平均每跳距離視為兩通信節(jié)點(diǎn)間的距離，否則取模型值為兩通信節(jié)點(diǎn)間的距離.

在實(shí)際應(yīng)用中，往往節(jié)點(diǎn)間的距離都是曲線路程，所以，算法存在一定的誤差.同時(shí)，距離錨節(jié)點(diǎn)路程越遠(yuǎn)的未知節(jié)點(diǎn)的DV-Hop 定位的精度就越差.本文的思想是采用取多個(gè)錨節(jié)點(diǎn)的平均每跳距離的均值來代替原算法中的平均每跳距離.改進(jìn)策略為：對(duì)于選定的一個(gè)未知節(jié)點(diǎn)A，在其通信范圍內(nèi)有n個(gè)錨節(jié)點(diǎn)，則未知節(jié)點(diǎn)從通信范圍內(nèi)的每個(gè)錨節(jié)點(diǎn)處獲得一個(gè)平均每跳距離，然后取平均值作為該未知節(jié)點(diǎn)的平均每跳距離.然后則可以用三邊測量法或極大似然估計(jì)法來計(jì)算出未知節(jié)點(diǎn)的位置.根據(jù)未知節(jié)點(diǎn)在定位過程中可以找到的錨節(jié)點(diǎn)的個(gè)數(shù)，可以分為以下2種情況：

1)定位時(shí)，當(dāng)未知節(jié)點(diǎn)可以找到的錨節(jié)點(diǎn)個(gè)數(shù)在三個(gè)或者三個(gè)以下時(shí)，或找到的錨節(jié)點(diǎn)共線時(shí)，則不執(zhí)行極大似然法計(jì)算其位置.

2)定位時(shí)，未知節(jié)點(diǎn)D可以找到錨節(jié)點(diǎn)A1,A2,…，An(n>3)，則未知節(jié)點(diǎn)D平均每跳距離如公式(2)所示:

(2)

然后未知節(jié)點(diǎn)根據(jù)DV-Hop算法第一階段中記錄的到錨節(jié)點(diǎn)A1,A2,…，An的最小跳數(shù)就可以計(jì)算出未知節(jié)點(diǎn)到這n個(gè)錨節(jié)點(diǎn)的距離估計(jì)值，這樣使網(wǎng)絡(luò)充分利用了錨節(jié)點(diǎn)，定位更加精準(zhǔn)[5].

傳統(tǒng)的極大似然算法是采用多個(gè)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)進(jìn)行定位，當(dāng)節(jié)點(diǎn)的數(shù)目較多而且連通性比較好的情況下，就可更準(zhǔn)確計(jì)算未知節(jié)點(diǎn)坐標(biāo).如圖所示，假設(shè)己知節(jié)點(diǎn)1,2,3…n的坐標(biāo)為(xi，yi)，他們到未知節(jié)點(diǎn)的距離為Si(i=1,2,3…n)，令未知節(jié)點(diǎn)P的坐標(biāo)為(x,y).

則根據(jù)兩點(diǎn)間距離公式可得公式(3)：

(3)

依次用前n-1個(gè)方程去減第n個(gè)方程得到公式(4):

(4)

則公式可用線性方程AX=B表示，其中:

(5)

通過計(jì)算最小方差得待測節(jié)點(diǎn)的坐標(biāo)X為:X=(ATA)-1ATB.

通過對(duì)上式得分析可知：由于式1中Si本身存在誤差，在式2中又對(duì)其平方，會(huì)導(dǎo)致誤差更大，所以本文采取先用第n個(gè)式子減去前n-1個(gè)式子，再對(duì)兩邊進(jìn)行平方，這樣一來，可以在一定程度減小定位誤差，達(dá)到改善定位精度效果[6].

4 仿真實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證算法的可行性，在matlab中進(jìn)行了DV-hop定位仿真實(shí)驗(yàn).仿真實(shí)驗(yàn)選取場景為100 m*100 m大小的空間，信標(biāo)節(jié)點(diǎn)個(gè)數(shù)為8個(gè)，未知節(jié)點(diǎn)個(gè)數(shù)90個(gè)，進(jìn)行仿真測試，結(jié)果如圖4-圖7所示.

圖4是定位節(jié)點(diǎn)分布圖，圖5為采用傳統(tǒng)DV-hop對(duì)未知節(jié)點(diǎn)進(jìn)行定位解算的誤差曲線.

圖4 節(jié)點(diǎn)位置示意圖

圖5 傳統(tǒng)DV-hop定位誤差

圖6所示是基于平均跳距修正后的誤差結(jié)果.圖7是在基于平均跳距修正基礎(chǔ)上對(duì)極大似然估計(jì)法改進(jìn)后得到的最終改進(jìn)結(jié)果.

圖6 基于平均跳距修正的誤差仿真結(jié)果

圖7 改進(jìn)的極大似然估計(jì)法仿真結(jié)果

由上述圖片分析計(jì)算得，改進(jìn)的DV-Hop算法精度比傳統(tǒng)的DV-Hop算法精度提升21.8%，并且一般來說，網(wǎng)絡(luò)中節(jié)點(diǎn)密度越大，定位精度越高.DV-Hop算法只能在節(jié)點(diǎn)分布比較密集的無線傳感器網(wǎng)絡(luò)中才能合理地估算平均每跳距離，然后才能較準(zhǔn)確地估算出節(jié)點(diǎn)的位置[7].經(jīng)多次實(shí)驗(yàn)證明，本改進(jìn)算法可將定位誤差控制在0.7 m以內(nèi)，符合大部分高精度室內(nèi)定位應(yīng)用的研究.

5 結(jié)論與展望

本文在原有的DV-Hop定位基礎(chǔ)上，對(duì)其進(jìn)行仔細(xì)分析與改進(jìn)，從該算法的每一階段探尋改進(jìn)策略，使算法實(shí)用性更加完善，定位結(jié)果更加準(zhǔn)確，為無線傳感網(wǎng)絡(luò)定位方案做了進(jìn)一步的鋪墊.

另外，該成果是在創(chuàng)客教育教學(xué)實(shí)踐中及大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃中通過研究生與本科生結(jié)對(duì)互助及本科生參與教師科研等方式完成的，論文也主要由學(xué)生整理及撰寫，是一次有益的創(chuàng)新教學(xué)嘗試.

[1] Wu G,Wang S,Wang B,et al.A novel range-free localization based on regulated neighborhood distance for wireless ad hoc and sensor networks[J].Computer Networks,2012,56(7):3581-3593.

[2] 趙昭，陳小慧.無線傳感器網(wǎng)絡(luò)中基于 RSSI 的改進(jìn)定位算法[J].傳感器技術(shù)學(xué)報(bào)，2009，22(3):391-392.

[3] 林金朝，劉海波，李國軍，等.無線傳感器網(wǎng)絡(luò)中 DV-HOP 節(jié)點(diǎn)定位改進(jìn)算法的研究[J].計(jì)算機(jī)應(yīng)用研究，2009，26(4):1272-1275.

[4] 解慧英.無線傳感器網(wǎng)絡(luò)中一種改進(jìn)的DV-Hop定位算法[D].武漢：武漢科技大學(xué)，2008.

[5] 張品，徐智福，孫巖.基于無線傳感器網(wǎng)絡(luò)的一種改進(jìn) DV-Hop 算法[J].電子器件， 2009，32(6)：1091-1093.

[6] Balogh L,Kollar I,Michaeli L,et al.Full information from measured ADC test data using maximum likelihood estimation[J].Measurement,2012,45(2):164-169.

[7] Pan W H,Liu X D.Wireless sensor networks based on the DV-hop localization algorithm[C].Proceedings of 2012 Fourth International Conference on Computational and Information Sciences,2012:1073-1075.

(責(zé)任編輯鄭綏乾)

ImprovedDV-HopLocalizationAlgorithmforWirelessSensorNetworks

LI Li-na,WANG Yue,ZHANG Xiao-dong,LEI Hao-dong

(Collegeofphysics,LiaoningUniversity,Shenyang,Liaoning,110036,China)

Aiming at the problem of low positioning accuracy of DV-hop positioning algorithm,proposed an improved DV-hop algorithm,and the basic principle of improvement is introduced in detail.In the second phase of the algorithm,the RSSI algorithm is used to correct the average hop distance,and the third stage uses the method of reducing the square after the first,and improves the calculation procedure of the maximum likelihood estimation method,thus reducing the computational error.The improved algorithm is simulated and analyzed by using matlab.The simulation results show that compared with the traditional DV-Hop localization algorithm,the localization of the improved algorithm is decreased by 21.8%,and the positioning accuracy is greatly improved without additional hardware overhead.

DV-Hop location algorithm;Wireless sensor networks;Maximum likelihood method

TN 929.5

A

1000-5846(2017)04-0320-05

2017-08-15

遼寧大學(xué)教學(xué)改革項(xiàng)目(JG2016YB0043)；遼寧省大學(xué)生創(chuàng)新創(chuàng)業(yè)項(xiàng)目(201710140000188)

李麗娜(1973-)，女，滿族，遼寧本溪人，副教授，碩士研究生導(dǎo)師，主要從事物聯(lián)網(wǎng)感知層相關(guān)技術(shù)研究；

王越(1993-)，男，漢族，遼寧本溪人，碩士研究生，主要從事無線傳感網(wǎng)絡(luò)技術(shù)及應(yīng)用研究.