基于改進DV-Hop算法的無線定位技術

盛偉輝，涂超，董昊軒,李樂

(1.長安大學 汽車學院,陜西 西安 710064;2.茵卡動力新能源江蘇有限公司，江蘇 南通 226000)

無線傳感器網絡是指由部署在監測區域內的大量微型傳感器節點組成，以協作感知、采集和處理網絡監測區域內監測對象狀態信息為目的，通過無線通信方式形成的一個多跳的、自組織的網絡系統[1]。無線傳感器網絡因為具有功耗低、可遠程監控和實時監控等優點，越來越多地應用在環境監測、國防軍事、交通管理和醫療衛生等領域[2-5]，基于無線傳感器網絡的無線定位技術得到越來越多的應用。

現有的無線定位技術分為基于測距的定位和無需測距的定位。基于測距的定位技術通過測量相鄰節點之間的絕對距離，并利用節點之間的實際距離計算未知節點的位置。比較成熟的基于測距的定位技術有基于信號傳播時間的定位(TOA)、基于信號傳播時間差的定位(TDOA)、基于接收信號強度的定位(RSSI)等[6-10]。基于測距的定位精度高，但需要昂貴的硬件設備做支撐，定位耗費比較大，一般不適合大型場合。無需測距的定位技術是根據網絡連通性等信息，利用節點之間的估計距離和跳數進行定位。現有無需測距的定位技術主要有DV-Hop定位技術、Amorphous定位技術、質心算法定位技術等[11-16]。其中，DV-Hop定位技術因為較易實現、無需節點具有測距能力、對信標節點比例要求低等優點，成為一種經典的無需測距的定位技術。本文基于傳統DV-Hop算法，分析定位過程中產生偏小誤差的原因，引入信標節點比例、信標節點平均跳距最大值和信標節點平均跳距平均值對算法進行修正。

1 DV-Hop算法

DV-Hop算法是利用距離矢量路由和GPS定位的思想提出的一系列分布式定位方法之一，是依賴節點間的信息交換和協調，由節點自行計算出位置的一種定位方式。其定位過程可以分成三個階段[17]。

1)計算未知節點與每個信標節點最小跳數

網絡中每個信標節點向它的鄰近節點廣播自己的位置信息，接收節點接收信標節點的跳數信息，同時忽略來自同一信標節點的跳數較大的數據，接收節點接收到信標節點跳數信息進行自加1，并轉發給下一節點。通過這種方式，網絡中的每個節點都可以計算出到該信標節點的距離。

圖1 小型傳感器網絡

圖1所示為一小型傳感器網絡示意圖，該網絡由共計9個節點組成。其中L1、L2、L3為信標節點，其余都為未知節點，對節點A進行定位，di為信標節點之間的距離。

2) 計算未知節點與信標節點之間距離

每個信標節點根據第一階段記錄的其他信標節點的位置信息和最小跳數信息估算平均每跳距離

(1)

式中：(xi,yi)，(xj,yj)是信標節點i，j的坐標；hij是信標節點i和j(i≠j)之間的跳數。

之后，信標節點把計算得到的平均每跳距離分組廣播到整個網絡中。未知節點只記錄接收到的第一個平均跳距信息并轉發到下一個鄰近節點。這種帶有生存期的分組廣播保證了每個未知節點僅接收到來自最近的信標節點的平均跳距信息。此后，未知節點根據平均每跳距離計算到每個信標節點之間的距離。

3)計算未知節點自身位置

未知節點獲得第三階段計算出的3個以上信標節點的平均跳距信息，通過三邊測量法或極大似然估計法計算自身位置。三邊測量法是根據某未知節點到三個信標節點的距離，通過幾何方法計算未知節點的坐標，這種測量方法非常依賴未知節點到信標節點的測量準確度，在實際應用中很少使用。以下是極大似然估計法求未知節點坐標的基本原理[18]：

圖2 極大似然估計法

如圖2所示，已知n個節點的坐標及到未知節點D的距離，計算未知節點D的位置。

列方程組：

使用標準的最小二乘法得到未知節點的坐標

DV-Hop定位方法可以利用網絡中廣播的大量重復信息進行距離修正，同時不需要成本高昂的硬件設施支撐，因此DV-Hop定位方法在各種場合廣泛應用，但其也存在一些不足，如：①實際環境定位過程中，存在遮蔽物或部分區域節點分布稀疏，都會使未知節點距離信標節點的最短通信路徑發生偏折，而位于稀疏區域的節點則成為不良節點。②如圖1所示，在DV-Hop算法第二階段，信標節點L2在利用式(1)計算平均跳距時，用L2和L3之間的直線距離d2代表折線距離L2-A-L3，而兩直線之間的直線距離總小于折線距離，并且當折線的彎曲程度越大，利用公式計算的平均跳距偏差越大。同時在信標節點L1、L2、L3之間，用實際距離d1、d2、d3代替每跳距離，總比實際偏小。③DV-Hop定位是依靠泛洪廣播傳遞的大量冗余數據實現的精確定位，其信息傳遞過程中會出現信息量大、信息沖突和信息內爆等諸多問題，無疑增加了通信開銷。

基于上述DV-Hop算法定位的不足，本文提出了通過引入信標節點比例、信標節點平均跳距的最大值和所有信標節點平均跳距的平均值對階段二的平均跳距進行修正。

2 DV-Hop算法的改進

信標節點的比例定義為傳感器網絡中信標節點的數量占全體節點總數量的比例。假設網絡中布置的總節點個數為Q，信標節點的數量為q，則信標節點的比例

當傳感器網絡中節點總數固定時，ρ反映了網絡中信標節點的個數，ρ越大，網絡中信標節點數量越多，網絡定位誤差也越大。

網絡信標節點平均跳距均值指整個網絡中所有信標節點的平均跳距的平均值。假設網絡中信標節點個數為n，則網絡平均跳距均值

由于網絡平均跳距均值Ha是對整個網絡所有信標節點的平均跳距進行運算，所以它在一定程度上反映了整個網絡的平均跳距信息。

則整個網絡所有信標節點的平均跳距的最大值

Hmax=max(Hi)。

網絡平均跳距的最大值可以在網絡節點數量較多時修正算法的偏小誤差，而網絡節點數量不多時，可能造成修正過量。

本文提出的算法修正過程是把網絡平均跳距的均值作為網絡平均跳距修正值的最小值，網絡平均跳距的最大值作為網絡平均跳距修正值的最大值，使網絡平均跳距修正值在Ha～Hmax變化，對網絡定位進行修正。修正值與ρ的具體關系如圖3所示。

圖3 網絡平均跳距修正

在信標節點占總節點數量為0時，網絡平均跳距修正值為Ha；網絡信標節點比例為0～50%時，網絡平均跳距修正值與信標節點比例ρ成正比例關系；當信標節點比例大于50%時，網絡平均跳距修正值取網絡平均跳距的最大值Hmax。平均跳距修正值

3 改進算法仿真及分析

3.1 DV-Hop算法參數選擇

Matlab仿真軟件具有友好開發環境，程序語言簡單易用,數據、圖形處理能力強大等優點，在通信領域得到廣泛的運用。本文基于Matlab仿真平臺，為體現仿真結果的一般性，設置在100×100的方形區域內隨機布置傳感器節點，首先設置傳感器通信半徑為50、40和30，并設置信標節點比例為25%，對傳統DV-Hop定位算法分析傳感器節點通信半徑和信標節點比例對定位精度的影響，并最終選取一組理想組合進行改進仿真。本文對節點的定位精度是絕對誤差對節點通信半徑的比值，具有相對性，因此不設置單位。

基于傳統DV-Hop算法，信標節點比例為25%時的仿真結果如圖4所示。

a)通信半徑為50 b)通信半徑為40 c)通信半徑為30圖4 傳統DV-Hop定位算法節點誤差

傳統的DV-Hop算法中，當設置網絡節點通信半徑為50，在總計75個未知節點中，有近30%的未知節點的定位誤差超過50，甚至有5個節點的定位誤差超過了60，且只有5個未知節點定位誤差在10左右，各未知節點定位誤差精度相差大，所有未知節點誤差均方差也較大，定位誤差波動性明顯，且總體誤差平均值也不理想。

當傳感器節點通信半徑設置為40和30時，定位誤差的最小值甚至下降到10以下，網絡所有未知節點定位誤差主要集中在20～50，定位精度相較通信半徑為50時，有了部分改善，同時整個網絡所有未知節點定位誤差的均方差也下降，定位誤差的波動性降低，定位更加穩定。

信標節點比例越大，信標節點平均跳距的誤差會累計增加，計算平均跳距時，誤差增大，導致增加未知節點定位誤差，因此本論文考慮將信標節點比例分別設置為25%和20%，節點通信半徑設置為40和30對算法定位誤差進行討論。

3.2 改進算法仿真分析

采用改進的DV-Hop定位算法，其中信標節點比例ρ為25%，網絡節點通信半徑40和30，在100×100區域進行仿真的結果如圖5所示。

a)通信半徑為40 b)通信半徑為30圖5 改進DV-Hop算法節點定位誤差

從圖5a)可以看出，整個網絡未知節點的定位誤差主要集中在5～20，有6個未知節點誤差小于5，4個未知節點誤差大于20，且僅有一個未知節點定位誤差為25，而比較圖4b)，通信半徑40的傳統DV-Hop算法定位誤差主要集中在30～60，僅有少數節點誤差小于20，甚至有5個節點定位誤差大于60。同時，改進后的DV-Hop算法定位誤差也比傳統DV-Hop算法集中，誤差波動性比較小。可以看出，改進后的DV-Hop算法定位誤差顯著降低，定位穩定性顯著提升，可以滿足大多數應用場合要求。

從圖5b)可知，通信半徑為30的定位誤差主要集中在0～15，有17個未知節點誤差小于5，僅有3個節點誤差大于15，這主要是由于仿真模型隨機分布網絡節點時分布不均勻，出現分布稀疏區域的不良節點所致。而比較圖4c),通信半徑30的傳統DV-Hop定位算法定位誤差主要集中在10～60，甚至有6個節點誤差大于60，僅有3個節點誤差小于10。可以看出，改進后的DV-Hop算法在定位精度和定位穩定性方面都有顯著提升，且整個定位過程中通信開銷無明顯增加。改進后的定位算法比較可靠地完成了定位需求。

設定信標節點比例為20%，比較傳統DV-Hop算法與改進DV-Hop算法節點定位誤差，結果如圖6、7所示。

a)通信半徑為40 b)通信半徑為30 a)通信半徑為40 b)通信半徑為30 圖6 傳統DV-Hop算法節點定位誤差 圖7 改進DV-Hop算法節點定位誤差

比較圖6a)、7a)可以看出，傳統DV-Hop定位算法誤差主要集中在20～60，有兩個節點誤差超過60，而改進的DV-Hop算法定位誤差主要在5～20，有5個未知節點誤差超過20；對于圖6b)、7b)的情況，改進后的DV-Hop算法定位誤差也顯著下降，但由于信標節點比例較低，出現不良節點，導致少數未知節點定位誤差偏大。

4 結語

針對傳統的無需測距的DV-Hop定位算法，詳細分析了其定位過程的三個階段，并分析了其第二階段計算信標節點平均跳距時產生誤差的原因和傳統DV-Hop算法的不足，針對這些不足，提出在算法中添加信標節點比例、網絡平均跳距均值和平均跳距最大值，同時考慮平均跳距應反應網絡節點分布情況，對算法進行修正和仿真。仿真結果表明，改進后的DV-Hop算法在改變信標節點比例、節點通信半徑時，均使未知節點定位誤差顯著下降，且網絡定位誤差波動較小、穩定性好，可以滿足大部分定位場合的應用需求。