基于迭代協作的改進DV-Hop定位算法

新華社音視頻部 邰劍秋

介紹

在無線傳感器網絡中，節點準確地進行自身定位對其有效性起著關鍵的作用。為了適應無線傳感器網絡中節點低能耗的特性要求，充分利用節點資源，在節點定位中引入協作技術，以獲得更高定位的性能，即協作定位[1]。

對于無線傳感器網絡節點定位算法主要可以分為兩大類：基于測距的定位算法和無需測距的定位算法。測距技術主要包括基于TOA的定位、基于TDOA的定位、基于AOA的定位、基于RSSI的定位等[1][2]。無需測距的算法主要包括以下幾種：質心算法[3]、APIT算法[4]、MDS-MAP算法[5]、DV-Hop算法[6]等。上述算法中，DV-Hop算法具有方法簡單、定位精度較高等優點，但其定位性能受節點分布影響大，僅在密集網絡中，才能達到較高定位精度，當網絡拓撲不規則時，定位誤差較大。

文獻[7]通過加入接收信號強度指示器（RSSI）測距模塊輔助定位，對算法進行改進，提高了定位精度和系統穩定性。但是需要增加額外的測距模塊，使硬件復雜度增大，有悖于無需測距算法簡單易行、成本低的特點。文獻[8]提出了一種選擇邊界錨節點的算法，通過減少參與洪泛的錨節點個數來減少能量消耗，但是該方法對定位精度改善甚小，且網絡拓撲稀疏、信標節點較少或分布不規則時，對算法性能影響較大。文獻[9]從獲得跳數的方法上對DV-Hop算法進行改進，利用節點接收到的信號能量對節點間跳數進行量化。文獻[10]利用節點與其鄰近節點間的測量距離優化定位性能，但其定位精度主要依賴于求精階段節點間距離測量的精度，當距離誤差較大時，定位誤差反而增大。同時，[9][10]還分別需要得到能量和待測節點間距離等額外信息，使通信開銷和硬件復雜度增大。文獻[11]從求平均每跳距離、校正值的選取上對算法作改進，且引入未知節點到參考節點的距離作為節點定位的約束條件，提高了定位性能且節約了成本。但是，由于DV-Hop算法使用跳段距離代替實際距離來估算未知節點的定位坐標，跳數越大則誤差越大。且定位精度還受節點拓撲關系影響，當信標節點位置近似于一直線時，定位誤差較大。同時，傳統的DV-Hop定位算法覆蓋范圍還受到信標節點個數的限制，即當信標節點較少時，將有很大一部分未知節點無法實現定位。

本文針對以上問題，提出了一種優化的DV-Hop定位算法，即ICDV-Hop算法。通過設置跳數門限來控制節點間的距離誤差，并且利用共線度測試對信標節點之間、信標節點與未知節點間的幾何位置關系加以約束，以選擇最優的信標三角形來降低定位誤差，并引進了迭代協作[12]增加定位覆蓋。該算法使用3個信標對未知節點進行位置估計，有效降低了定位時的計算能耗。仿真結果表明，ICDV-Hop算法的平均誤差和定位覆蓋均有明顯改善，表現出良好的可靠性，并且有更好的穩定性和魯棒性。

系統模型

DV-Hop算法整個定位過程不依賴于昂貴的測距方法，利用了多跳信標節點信息來參與節點定位，使其定位覆蓋率大大提高。其主要思想是采用跳段距離之和代替實際距離。整個網絡結構如圖1，實線為跳段，說明相應節點間可以實現通信。

圖1 網絡拓撲結構

圖中B1, B2, B3, B4為信標節點(Beacon)，其余為未知節點。X1, X2代表剩余節點，即無法實現位置估計的節點。

傳統DV-Hop算法由三個階段組成。第1階段，使用典型的距離矢量交換協議，通過節點間的信息交換，使網絡中所有節點獲得與信標節點間的跳數。如圖1中，節點A獲得與信標節點B1、B2、B3、B4間的跳數分別為3、2、3、2.第2階段，在獲得其他信標節點的位置信息和條數信息后，信標節點計算節點間的平均每跳距離，并將其作為一個校正值（correction）廣播至網絡中。未知節點利用校正值和記錄的跳數計算與各信標節點的距離。第3階段，根據未知節點與每個信標節點的距離和信標節點的位置坐標，利用多邊測量或極大似然估計法計算未知節點坐標。

ICDV-hop算法

由于DV-Hop算法節點間的距離由平均每跳距離與跳數相乘求得，如圖1所示，定位精度主要由平均每跳距離的精度決定，而跳數越大估計得到的平均每跳距離越不準確，導致節點間距離誤差過大，最終影響定位精度；定位精度受到節點間位置關系影響，當用于定位的信標節點處于同一直線時，定位誤差較大；定位覆蓋范圍受到信標節點個數的限制，而實際網絡中信標節點往往較少，導致較多未知節點無法實現定位。因此本文針對以上三點對DV-hop算法作出改進，ICDV-Hop算法主要由5個步驟組成：

1. 通過節點間信息交換，獲得未知節點與跳數門限內信標節點的跳數信息；

2. 根據信標節點校正值與跳數信息計算未知節點到信標節點的距離；

3. 進行信標節點共線度測試，選擇最優的信標三角形；

4. 未知節點利用信標三角形進行位置估計；

5. 判斷每個已定位節點的定位誤差，若其小于設定的閾值，則轉化成信標節點；

6. 重復第1-4步對剩余的未知節點進行定位，直至沒有新的信標節點產生。

3.1 未知節點獲得跳數信息

通過節點間的信息交換，能使網絡中所有節點獲得與信標節點之間的跳數。但由于DV-Hop算法采用跳段距離之和代替實際距離，跳段數增加將使累計誤差增大，所以一般情況下，未知節點若只接收距離較近的局部范圍內的信標節點信息，將會減少這種累計誤差的疊加，提高定位精度并從整體上降低網絡通信量。因此，我們設置一個跳數門限N，限制未知節點接收大于此門限跳數的信標節點信息。

如圖1所示，信標節點Bi向鄰居節點廣播自身位置信息，包括跳數字段(Hops)、坐標值和ID號。當未知節點與信標存在不同路徑時，選取最小的跳數值計算。未知節點收到某一信標節點的跳數值后，將其與門限N比較，若小于門限N，節點將跳數值加1，并轉發給鄰居節點，否則丟棄此分組。

門限N與節點傳播半徑、網絡區域面積和信標節點個數有關。可以根據(1)式計算N值

其中，area為正方形網絡的邊長，R為節點傳播半徑，BeaconAmount為信標節點的個數，m為每個未知節點定位需要的信標數。

3.2 計算跳距

利用跳數和平均每跳距離，計算未知節點與限定跳數內的信標節點的距離。

首先計算每個信標節點的校正值。設信標節點共有k個，位置信息坐標為(xi, yi) (i=1,2,…,k)，每個信標節點根據記錄的與其它信標節點的位置信息和相距跳數，估算如圖1所示的平均每跳距離HopSize，即每個信標的校正值。信標間的距離為

其中h i , j是對應信標節點間的跳數值。

信標節點得到自身校正值后，將其作為一個跳距校正值(correction)廣播至網絡中。未知節點僅記錄收到的第一個校正值作為平均每跳距離或跳段數最小的作為平均每跳距離。使用這種方法可以使未知節點從最近的信標接收校正值。未知節點獲得該校正值后，根據(4)式計算第n個未知節點到各信標節點的距離：

其中cn為未知節點n接收到的校正值，hn , j為未知節點n與信標節點j間的跳數。

3.3 信標三角形的選擇

傳統算法中，與未知節點通信的信標達到三個時，即可實現位置估計。然而當信標節點接近于同一直線時，會導致較大的位置估計誤差。因此將信標節點的位置關系引入到ICDV-Hop算法中，提出共線度概念，如圖2所示。

圖2 共線度

其中，設平面上任意三點所形成的三角形中最長邊的邊長為lmax，該邊所對應的高即為hmin，定義hmin與lmax的比值為該三角形的共線度，用DC表示為：

共線度的取值范圍為[0,1]，共線度值越小表示3個點越接近共線，而當三點完全共線時，三角形退化，此時的共線度為0。在實際的信標節點選擇過程中，可以通過設定某一閾值來約束信標節點之間的拓撲關系，即DC< thre_c。其中thre_c為設置的共線度閾值。

盡管通過信標節點的坐標可以方便地計算出它們之間的拓撲關系，但是僅僅考慮信標節點之間的關系是不夠的，在未知節點的位置估算過程中，還需要考慮信標節點與未知節點之間的關系。圖1中，對于未知節點A，若信標三角形B1B2B3與B1B3B4共線度相等且最優，但A處于三角形B1B2B3中，因此應選擇其作為信標。

為了約束未知節點與信標節點之間的關系，需要在設置共線度閾值時考慮未知節點與信標節點之間的位置關系。ICDV-Hop算法通過判斷未知節點是否在信標三角形內，選擇合適的信標三角形。即先根據共線度測試找出所有可用的信標三角形組合；接著根據步驟2中得到的未知節點到信標三角形各頂點的距離和信標三角形各邊長，可以判斷出該未知節點是否在相應的信標三角形內，找出符合條件的信標三角形；若此時符合條件的組合有多個，則選取未知節點到信標三角形三個頂點跳數和最小的組合，此做法也與步驟1中增加跳數門限相對應，目的也在于盡可能的減小距離誤差。按照這種規則，圖1中將選擇使用信標B1B2B3來估計A點位置。

3.4 位置估計

當信標節點通過共線度驗證后，進行位置估計。

設未知節點A坐標為(x, y),可與其通信的所有k個信標節點的位置信息用(x1, y1), (x2, y2),…,(xk, yk)表示，未知節點到信標節點的距離分別為r1,r2,…,rk,則可建立線性方程組：

其中，

在傳統DV-Hop算法中，未知節點在實現自身定位時使用了所有可以與它通信的信標。而由于未知節點與信標節點的距離通過跳數估計得出，多個距離方程構成的超定方程組，當方程個數增加時，它的解并不一定最接近真實坐標值。相反，當跳數過大時，用多個信標定位反而有可能造成誤差的擴大，且計算復雜度增加。而ICDV-Hop算法利用跳數門限結合共線度測試，挑選出最優的三個信標節點組合，有效避免了上述情況，且定位誤差受網絡拓撲影響小。同時，改進算法只使用三個信標節點進行位置估計，與傳統算法相比，可以大大節省定位時的計算能耗。

3.5 迭代協作

信標節點的個數直接影響算法定位覆蓋范圍，而實際網絡中信標節點往往較少，致使很大一部分未知節點無法實現定位。針對此問題，本文在ICDVHop算法中引入迭代協作技術。即對于收到足夠多信息的節點，用現有算法直接定位；然后已定位節點轉化為信標節點，并將自己的位置信息廣播出去，剩余節點可以利用該信息定位。

該方法能有效提高定位覆蓋，使原本不在信標節點傳播范圍內的未知節點也能被定位。但是若定位出的未知節點位置與實際位置誤差較大，則在將它轉化成信標節點供其他節點使用并進行多次迭代時會造成誤差傳播，使整個網絡的定位性能受影響。因此本文在將定位出的未知節點轉化成信標節點時加入一定的限制。即：設定一個閾值err_thred，在某未知節點實現自身定位后，計算其歸一化定位誤差，若誤差小于這一閾值，則可轉化為信標節點以供下一輪定位，若誤差超過這一閾值，則不轉化。

迭代協作過程如下：

1. 定位出所有收集到足夠信息的未知節點；

2. 計算出上一步中每一個已定位未知節點的定位誤差，與閾值err_thred比較，將定位誤差小于該值的節點轉化為信標節點，其余不轉化；

3. 利用轉化的信標節點結合原有信標節點，重復1、2對剩下的未知節點再次進行定位，直至沒有新的信標節點可以轉化。

算法仿真

本文基于圖1的系統模型用Matlab軟件對ICDV-Hop算法進行蒙特卡洛仿真。仿真過程中網絡區域為100m×l00m的矩形區域，信標節點和未知節點的坐標隨機產生，隨機分布。在相同條件下，分別通過改變信標節點個數和節點密度、節點傳播半徑等條件來實現對新算法的性能評估。

本文對算法的評估指標主要有兩個：歸一化平均定位誤差err和定位剩余。其中err由節點平均定位誤差與傳播半徑R的比值得出，即

其中(x0, y0)為節點實際位置坐標，($x,$y)為估計坐標。定位剩余是指定位完成后無法定位的未知節點個數占未知節點總個數的比例。值得注意的是最終實驗結果通過將多次仿真的數據求平均得到。

圖3、圖4中區域內總節點數為150，可見在相同信標個數條件下，ICDVHop算法與傳統算法相比定位誤差降低了約30%，定位剩余也明顯減少，表現出優越的定位性能。圖3中隨著信標節點的增加，定位誤差所受影響較小，并逐漸趨于穩定。因為DV-Hop算法使用跳段距離代替節點間的實際距離進行定位估計，信標節點個數增加并不一定能提高定位精度。ICDV-Hop算法只選取3個信標節點用于最后位置估計，當信標節點個數增加到一定程度后，對所選擇的信標三角形的優越性影響很小，即定位精度也逐漸趨于穩定。

圖3 歸一化平均定位誤差

圖4 剩余節點比例

圖5、圖6顯示了定位精度與節點密度的關系。圖5是保持信標節點個數不變（15個）的情況，改變節點密度相當于只增加未知節點個數；圖6是保持信標百分比不變（10%）的情況，改變節點密度相當于信標節點與未知節點均按比例增加。總體上，改進算法比原算法有更小的平均定位誤差，尤其是在節點密度較低即網絡較稀疏情況下，改進程度尤為明顯。在節點密度為0.01而其他條件均相同的情況下，平均定位誤差減小了約50%。隨著節點密度的增加，傳統算法和改進算法定位精度均隨之改善，因為節點的增加能提高跳段距離估計精度，從而降低定位誤差。且改進算法隨著節點密度增加其定位誤差相對穩定，表現出良好的魯棒性，這是由于跳數門限的應用限制了未知節點與信標節點間的條數，從而減小了節點密度對定位性能的影響。

從圖7可以看出，隨著R的增大，傳統算法和改進算法定位誤差都隨之減小。而在相同條件下，改進算法比傳統算法表現出更優越的性能，尤其在R較小時，定位誤差改進程度尤為明顯。因為在R較小的情況下，使用傳統算法定位時，未知節點必須通過較多跳數獲得與信標節點的信息，跳段距離誤差大導致定位誤差過大。而改進算法中由于使用了跳數門限，避免了這種情況。且根據公式（1），條數門限N隨著R的增大而減小，限制了節點通信半徑對定位精度的影響，因此ICDV-Hop算法具有良好的穩定性。

圖5 歸一化平均定位誤差（信標不變）

圖6 歸一化平均定位誤差（信標10%）

圖7 歸一化平均定位誤差

結論

DV-Hop算法是一種無需測距的分布式節點定位算法，受環境因素的影響小，且節點不用附加額外的測距模塊，因而節點簡單、費用低、易于實現，適合大規模的無線傳感器網絡應用。但是由于未知節點到錨節點之間的距離用網絡平均每跳距離和兩者之間跳數的乘積表示，在密集的規則布局的網絡中可以得到合理的平均每跳距離,從而能夠達到適當的定位精度，但在稀疏或不規則的網絡中精確度不高。

本文針對無線傳感器網絡特點和傳統DV-Hop定位算法的局限性，對其提出了3點改進措施。通過設置跳數門限來控制節點間的平均每跳距離誤差；并且利用共線度測試對信標節點、信標節點與未知節點間的幾何位置關系加以約束，以選擇最優的信標三角形來降低定位誤差；引進了迭代協作技術，將定位誤差小于設定閾值的已定位節點轉化成信標，進行多次迭代定位，從而避免誤差傳播并增加定位覆蓋。從分析與仿真結果可以看出，改進算法在平均定位誤差及算法覆蓋等方面比傳統的DV-Hop方法有較大改善，表現出了更加優越的性能，在網絡中信標節點比率較低及網絡稀疏的情況下，改進程度尤為明顯。且改進算法性能受網絡條件影響較小，具有良好的魯棒性。

[1] Patwari N, Ash J N, Kyperountas S,et al. Locating the Nodes: Cooperative localization in wireless sensor networks.IEEE Signal Proccesing Magazine, 2005,22(4):54-89

[2] Della R F, Ardhy W S, Gianluca S, et al. Experimental Activity on Cooperative Mobile Positioning in Indoor Environments. In: IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks. Espoo, Finland: 2007. 1-6[3] Bulusu N, Heidemann J, Estdn D.GPS-less Low-cost Outdoor Localization for Very Small Devices. IEEE Personal Communications, 7(5): 28-34

[4] Tian H, Chengdu H, Blum B M,et al. Range-free Localization Scheme for Large Scales sensors Networks.In: Proceedings of the 9th Annual International Conference on Mobile Networking. New York, USA: 2003.81-95

[5] Shang Y, Ruml W. Improved MDS-based localization. IEEE Computer and Communications Societies, 2004, 4: 2640-2651

[6] Nicolescu D, Nath B. DV based positioning in ad-hoc Telecom.Systems. Telecom. System, 22(1),2003: 267-280

[7] 劉艷文，王福豹，段渭軍等.基于DV—Hop定位算法和RSSI測距技術的定位系統.計算機應用，2007，27(3):516-518

[8] 姜山，李建波.一種改進的DV-Hop傳感器網絡定位算法.計算機工程與應用，2007，43(34): 141-143

[9] Li X, Shi H, Shang Y. A partialrange-aware localization algorithm for ad-hoc wireless sensor networks.In: Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN). Tampa,USA: 2004. 77-83

[10] Savarese C, Rabaey J, Langendoen K. Robust positioning algorithm for distributed ad-hoc wireless sensor networks. In: Proceedings of the USENIX Technical Annual Conference.Monterey, California: 2002. 317-327

[11] 嵇瑋瑋，劉中.DV-Hop 定位算法在隨機傳感器網絡中的應用研究.電子與信息學報，2008，30(4):970-974

[12] Savvides A, Han C C, Srivastava M B. Dynamic fine-grained localization in ad-hoc networks of sensors.In: Proceedings of the 7th Annual International Conference on Mobile Computing and Networking. New York, USA: 2001. 166-179