基于校正矢量的分布式DV-Hop求精算法

林維維 姚英彪 鄒 柯 馮 維 嚴軍榮

(杭州電子科技大學通信工程學院 杭州 310018) (lsy001h@126.com)

無線傳感器網絡(wireless sensor networks，WSNs)是由多個傳感器節點組成的自組織網絡，用于在部署區域內進行信息采集、處理和傳輸等.WSNs的許多應用需要知道傳感器節點的位置信息[1-2]，例如目標區域感興趣事件的實時檢測和目標追蹤、環境監測等.此外，位置信息還可以提高網絡中路由的效率[3-4]，實現網絡拓撲自配置等.因此，位置信息在WSNs的應用中極其重要，節點定位技術已經成為當前WSNs研究的熱點之一[5-6].

1 相關工作

根據定位過程中是否需要測距可以將定位算法分為基于測距(range-based)定位和無需測距(range-free)定位2類[7-8].在基于測距的定位中，節點需要配備特殊硬件獲得其與已知位置的節點之間的距離或角度信息，然后根據距離或角度信息計算自己的位置，代表性的測距算法有TOA(time of arrival)[9]，AOA(angle of arrival)[10]，RSSI(received signal strength indication)[11]等.在無需測距的定位中，節點僅僅通過網絡連接信息來計算自己的位置，代表性的算法如APIT(approximate point-in-triangulation)[12]，DV-Hop(distance vector hop)[13-21]，LAEP(a novel range-free localization algorithm using expected hop progress)[22]等.相對于基于測距定位，無需測距定位簡單易行、成本低廉，但是定位精度相比前者較低.

本文主要針對DV-Hop定位算法進行位置求精.DV-Hop是一種經典的無需測距定位算法，具有算法簡單、易實現等優點，但定位精度一般.DV-Hop自提出之后有許多文獻都對其進行了改進.基于調節鄰居信息的DV-Hop改進算法(an improved DV-Hop localization algorithm, DV-RND)[13]改進了DV-Hop節點之間的距離估計方法，它是采用2個鄰居節點之間的共同鄰居節點的個數來表示它們的相近程度，進而估計出距離.基于優化算法的DV-HOP改進算法(an improved DV-Hop localization algorithm based on evolutionary)[14]利用3種進化算法改進DV-Hop，包括用蛙跳算法(shuffled frog leaping algorithm， SFLA)優化DV-Hop每個錨點的每跳距離，利用遺傳算法(genetic algorithm, GA)和粒子流優化算法(particle swarm optimization, PSO)求精DV-Hop計算得到的位置節點坐標.文獻[15]提出用平均每跳距離代替所有錨點的每跳距離，再用2維雙曲算法代替DV-Hop中用幾何方法求解節點坐標，最后利用PSO算法繼續求精DV-Hop.文獻[16]研究多通信半徑條件下的DV-Hop算法設計問題.文獻[17]提出了一種基于蝙蝠算法的DV-Hop改進定位算法(improved DV-Hop localization algorithm based on bat algorithm in WSNs, IBDV-Hop)，不僅提高了平均跳距的精度，還引入了非線性動態慣性權重方法來擴展算法的全局搜索范圍以及局部搜索精度.文獻[18]提出基于鄰居節點信息梯度化的距離估計算法(a distance estimating algorithm based on gradient neighbors in wireless sensor net-works, DV-GNN)，通過將鄰居節點信息梯度化來提高節點距離測量.文獻[19]通過跳距修正和粒子群優化來提高DV-Hop的定位精度.文獻[20]提出用GA優化提高DV-Hop的定位精度.文獻[21]將傳統意義上的跳數換成用來指示未知節點相對于錨點的接近度，最后利用鄰近算法得出未知節點的坐標.

本文所提算法與上述DV-Hop改進算法的區別在于，本文不是改進DV-Hop的計算過程，而是對DV-Hop的定位結果進行位置求精，因此本文算法與上述DV-Hop改進算法是互補關系.文獻[14-15，20]雖然也對DV-Hop的定位結果求精，但是它們是以錨點為參考節點；本文是以未知節點周圍的鄰居節點為參考節點對DV-Hop的定位結果進行求精.本文算法借鑒基于測距的Malguki[23]定位算法：利用節點間定位距離和測距距離構建校正矢量，然后在校正矢量方向通過迭代方式得到節點的定位位置.本文將Malguki算法思想應用到DV-Hop改進中，提出一種基于校正矢量的分布式迭代求精算法(CVLR)，它可以解決DV-Hop的定位模糊問題，從而大幅度改進DV-Hop的定位精度.CVLR和Malguki的區別在于：1)Malguki是基于RSSI測距的定位算法，而CVLR是基于DV-Hop的無需測距定位算法；2)CVLR與Malguki的目標函數不一樣；3)搜索方法不一樣，CVLR提出一種簡單的基于校正矢量的搜索方法.CVLR的貢獻主要有3個方面：

1) 提出一種基于DV-Hop的定位過程的偽測距方法，它利用節點保存的每跳距離的校正值去估計其與1跳或2跳鄰居節點之間的距離；

2) 提出一種基于節點間的偽測距距離和定位距離(定位位置之間的距離)的位置校正矢量構建方法，并將求精過程建模為使這2個距離的差值的平方和在校正矢量方向上的最小化問題，通過一種簡單的搜索方法來求解這個最小化問題；

3) 提出利用節點的1跳鄰居節點信息的CVLR1和利用1跳與2跳鄰居節點信息CVLR2求精算法.

2 DV-Hop定位過程及其定位模糊問題

2.1 DV-Hop定位過程

DV-Hop定位主要包括3個階段：1)未知節點通過廣播保存到錨點跳數最小的數據并轉發給鄰居節點；2)廣播結束后錨點每跳距離的校正值由式(1)確定；3)未知節點根據保存的校正值和到錨點的最小跳數值就可以計算到相應錨點的距離.當得到3個以上距離時，可以用3邊定位等幾何算法求得未知節點坐標.

(1)

其中，(xi,yi),(xj,yj)表示錨點i和j的坐標，hi j表示錨點i和j之間的最小跳數值.

2.2 DV-Hop定位模糊問題

DV-Hop的定位模糊問題[13]是導致DV-Hop定位算法精度低的原因之一.如圖1所示，A1，A2，A3是錨點，其余的都是未知節點，dA1A2，dA1A3，dA2A3分別為錨點A1，A2，A3之間的物理距離.那么可以得到A1，A2，A3的校正值為：cA1=(dA1A2+dA1A3)(4+4)，cA2=(dA1A2+dA2A3)(4+4)，cA3=(dA1A3+dA1A3)(4+4).未知節點B2距離錨點A3較近，所以節點B2將會保存A3的校正值，相應的節點B3距離A2較近，所以將會保存A2的校正值，由此可以得到節點B2到3個錨點的距離為：相應的節點B3到3個錨點的距離為：那么當dA1A2≈dA1A3≈dA2A3時，cA1≈cA2≈cA3，進而因此節點B2和節點B3的最終定位將會十分接近(如圖1中節點p，q)，甚至如果節點B2和節點B3接收到的校正值相同，它們的最終定位將會重疊.

Fig. 1 The hop-distance ambiguity problem of DV-Hop圖1 DV-Hop定位模糊問題

現有DV-Hop改進算法都不能很好地解決以上DV-Hop算法的定位模糊問題.我們注意到DV-Hop定位過程中僅利用了錨點的信息，但沒有利用本地的鄰居節點的信息.因此，我們提出在DV-Hop定位完成后，再繼續利用節點的1跳或2跳鄰居節點信息去進行位置求精，從而解決DV-Hop定位模糊問題.

3 CVLR算法

針對第2節描述的問題，本節提出CVLR算法，它包括3個步驟：1)根據每個節點保存的校正值計算得到它與1跳和2跳鄰居節點的距離，我們稱之為“偽測距距離”(pseudo ranging distance, PRD)；2)利用“偽測距距離”和“定位距離”(利用節點定位坐標計算得到的距離)構建校正矢量，將定位結果求精建模為使這2個距離的差值的平方和在校正矢量方向上最小；3)使用一種簡單的搜索算法對這個最小化問題進行迭代求解.

3.1 偽測距距離

偽測距距離根據節點和它的1跳鄰居節點各自所保存的校正值的平均值來進行計算，具體表示為

(2)

相應的節點i和它任意的2跳鄰居節點的偽測距距離被定義為

(3)

3.2 位置校正矢量

(4)

(5)

進而節點i和節點j之間的位置校正矢量可以被定義為

(6)

(7)

Fig. 2 The principle of correction vector圖2 位置校正矢量的原理

節點i的位置校正矢量的合成矢量可以表示為

(8)

3.3 基于搜索的求精方法

在知道節點i的位置校正矢量的方向之后，我們設置了一個目標函數，目的是使偽測距距離和定位距離的差值的平方和在校正矢量方向上最小，然后提出一種簡單的搜索方法來求解上述最小化問題.CVLR的目標函數定義為

(9)

(10)

3.4 CVLR算法定位流程

Fig. 3 The distributed refinement procedure of unknown node in CVLR 圖3 CVLR算法流程圖

圖3為CVLR算法的定位求精流程圖，整個CVLR算法分為2個階段：初始化階段和迭代求精階段.圖3中的DV-Hop Initialization是算法的初始化階段，進行DV-Hop定位，其余部分是算法的迭代求精階段，下面依次詳細介紹：

Step1. 每個節點廣播自身初始位置坐標(DV-Hop定位結果)和自身保存的校正值給鄰居節點.

Step2. 根據自身的校正值和接收到的鄰居節點的校正值，每個節點由式(2)(3)計算出它和鄰居節點的偽測距距離.

Step3. 根據自身和鄰居節點的定位坐標，每個節點由式(5)計算出它和鄰居節點之間的定位距離.

Step4. 根據Step2的偽測距距離和Step3的定位距離，每個節點由式(6)～(8)計算出自己的合成位置校正矢量.

Step5. 根據Step4的合成位置校正矢量，每個節點由式(9)(10)計算出自己的求精坐標.

Step6. 如果迭代次數k小于設定的閾值，每個節點廣播各自的求精坐標給鄰居節點并且重復Step3～Step6.如果迭代次數k達到設定的閾值則結束算法.

如果所用到的鄰居節點僅包含1跳鄰居節點，我們把這種算法稱作CVLR1；如果包含1跳和2跳鄰居節點，我們稱作CVLR2.

3.5 復雜度分析

4 CVLR性能仿真分析

4.1 仿真環境和參數設置

(11)

(12)

默認的實驗參數為：我們考慮在100m ×100 m的區域隨機部署N個未知節點，默認在區域的4個角落上布置錨點，它們的坐標分別為(0,0)，(0,100)，(100,0)，(100,100).

4.2 CVLR性能研究

1) 校正因子β設置

式(8)中的β值是不確定的，本節我們將通過實驗來確定β的取值.圖4顯示了CVLR算法中不同仿真環境下β值對定位誤差的影響，其中仿真參數為：圖4(a)未知節點數量從190～290之間變化，所有節點通信半徑都是22 m，β值從0.5～3之間變化；圖4(b)未知節點數量都為190個，所有節點通信半徑從16～28 m之間變化，β值從0.5～3之間變化.

從圖4中我們可以看到，當β值從1.5～2.5之間變化時，定位誤差相差不大，且比其他值的誤差要小，尤其在不同數量的未知節點環境中體現更明顯.此外，我們通過大量仿真實驗發現，當β=1.5時算法收斂速度較慢，當β值為2或2.5時算法收斂速度不相上下，且均比1.5時快.但從圖4中還可以看到，當β=2.5時，在未知節點數過少或者通信半徑過小的仿真環境下定位誤差反而上升，具有不穩定性.綜合考慮，我們在仿真實驗中取β=2.

Fig. 4 Influence of β on positioning error圖4 β對定位誤差的影響

2) 理想測距和偽測距下的收斂性

Fig. 5 The CVLR algorithm under ideal ranging condition圖5 理想測距條件下的CVLR算法

考慮一種特殊的理想情況：相鄰節點之間的偽測距距離等于它們之間的真實距離.如圖5所示，隨著迭代次數的增加，歸一化平均定位誤差逐漸趨向于0，這意味著如果知道節點間的真實距離，CVLR能夠對DV-Hop的定位結果進行位置求精.同時，也可以看到CVLR2的收斂性能是要好于CVLR1.

Fig. 6 The relation between the number of iterations and the positioning error圖6 迭代次數與定位誤差之間的關系

圖6給出了CVLR在偽測距條件下的收斂性情況，其中迭代次數為0時表示DV-Hop的定位結果，N表示未知節點數量.從圖6中可以看到：1)偽測距條件下，CVLR仍然能收斂，只是不能收斂到0；2)CVLR的歸一化定位誤差隨著迭代次數和未知節點數量的增加而減少；3)CVLR2的收斂速度和定位精度優于CVLR1.從圖6還可以看到，CVLR1和CVLR2的定位誤差在迭代次數12次和5次之后基本收斂，因此在之后的仿真中本文設置CVLR1和CVLR2的最大迭代次數分別為12次和5次.

3) 理想測距和偽測距下的性能對比

為展示CVLR在偽測距PRD下與理想測距(ideal ranging distance, IRD)的性能差異，以及相對于DV-Hop的定位性能優勢，圖7中比較了DV-Hop，CVLR-PRD，CVLR-IRD在相同場景下的歸一化定位誤差.仿真實驗中，未知節點數量設為190，通信半徑從15～35 m之間變化.

Fig. 7 The influence of the communication radius on positioning error圖7 節點通信半徑對定位誤差的影響

從圖7中可以看到，CVLR-PRD的定位精度相對于DV-Hop要提高許多.平均而言，相對于DV-Hop，CVLR1-PRD和CVLR2-PRD的定位精度分別提高31.83%和47.59%.另外，相對于對應的CVLR-IRD，CVLR1-PRD和CVLR2-PRD的定位精度分別有37.33%和22.06%的差距.

4.3 CVLR與其他定位算法的性能比較

圖8比較了DV-Hop，CVLR1，CVLR2，DV-RND，DV-EA的定位性能.DV-RND[13]和DV-EA[14]都是基于DV-Hop的改進定位算法.DV-RND主要解決DV-Hop中定位模糊問題，這與CVLR要解決的問題一致；DV-EA利用3種優化算法來提高DV-Hop定位精度，特別是它也包括對DV-Hop的定位結果進行位置求精，這點與CVLR一致.圖8(a)中，未知節點數量為190，通信半徑從15～35 m變化；圖8(b)中，節點通信半徑是22 m，未知節點數量從100～400變化.

Fig. 8 The performance comparison among CVLR, DV-Hop, DV-RND and DV-EA圖8 CVLR，DV-Hop，DV-RND，DV-EA的定位誤差比較

從圖8中我們可以看到：1)DV-RND，DV-EA，CVLR的定位精度都優于DV-Hop；2)CVLR1和CVLR2的定位性能明顯比DV-Hop，DV-RND，DV-EA好，CVLR2定位性能最好.具體來說，在圖8(a)中，CVLR1和CVLR2較DV-Hop的定位精度平均提高31.83%和47.59%，較DV-RND的定位精度平均提高21.20%和39.31%，較DV-EA的定位精度平均提高21.26%和39.45%；在圖8(b)中，CVLR1和CVLR2較DV-Hop的定位精度平均提高34.23%和48.54%，較DV-RND的定位精度平均提高30.64%和45.60%，較DV-EA的定位精度平均提高22.30%和39.26%.

CVLR性能優于DV-RND和DV-EA的原因在于：1)DV-RND僅優化了未知節點到錨點的距離估計，它不能完全解決節點定位模糊問題.2)DV-EA雖然既優化了錨點的每跳距離，也對DV-Hop的定位結果進行了位置求精.但是，它與DV-RND一樣，僅僅利用了錨點的消息，因而它要取得好的性能需要較多的錨點.3)CVLR在求精過程中，能夠利用未知節點的周圍鄰居節點的信息，通過多輪迭代方式對每個節點定位位置進行優化，因而能夠如2.2節所描述的那樣，較好地解決DV-Hop的定位模糊問題.同樣，CVLR2性能高于CVLR1也是因為這個原因.

5 結束語

本文針對典型的無需測距算法DV-Hop存在的定位模糊問題，提出了一種基于校正矢量的分布式迭代求精CVLR算法.CVLR能充分利用節點的1跳鄰居節點和2跳鄰居節點信息對節點的位置進行求精，其基本思想為利用節點接收到的錨點的校正值來計算節點間偽測距距離，然后通過定位距離和偽測距距離的偏差來構建位置校正矢量，最后利用一種簡單的搜索算法來獲得求精坐標.仿真實驗顯示，CVLR1和CVLR2較好地解決DV-Hop的定位模糊問題，其定位精度遠高于DV-Hop算法，也優于DV-RND和DV-EA.

具體仿真結果表明：在相同通信半徑不同未知節點數量下，CVLR1和CVLR2較DV-Hop的定位精度平均提高31.83%和47.59%，較DV-RND的定位精度平均提高21.20%和39.31%，較DV-EA的定位精度平均提高21.26%和39.45%；在相同未知節點數量不同通信半徑下，CVLR1和CVLR2較DV-Hop的定位精度平均提高34.23%和48.54%，較DV-RND的定位精度平均提高30.64%和45.60%，較DV-EA的定位精度平均提高22.30%和39.26%.

在未來工作中，可以從3個方面繼續改進本文的工作：1)結合其他DV-Hop改進算法，改進本文提出的節點之間的偽測距距離的估計，從而提高定位精度； 2)利用其他優化方法來解決本文提出的最小化問題，減少迭代次數，從而降低定位能耗；3)本文算法雖然用MATLAB進行仿真實驗得出的結果較好，但是畢竟不是真實場景，后續也可以考慮使用ZigBee進行組網，在真實場景中測試和改進本文提出的算法.