基于改進DV—Hop算法的無線傳感網節點定位算法研究

王亞芳　蔡暢　劉俊杰

摘要：無線傳感器網絡節點定位技術是無線傳感器網絡重要的技術之一，而如何最大限度提高節點定位精度是無線傳感器網絡定位研究領域的一個難點。本文首先研究了傳統的DV-Hop定位算法，提出一種基于RSSI修正的DV-Hop并可以升級輔助錨節點定位算法。仿真結果表明，在相同網絡連通度的情況下，改進算法提高了定位覆蓋率，同時具有更高的定位精度。

關鍵詞：無線傳感網；借點定位；DV-Hop算法

中圖分類號：TP3

文獻標識碼A

文章編號2095-6363（2017）04-0080-02

無線傳感網是由大量設置在研究區域的傳感器節點，通過無線網絡組成的一個多跳組織網絡，集數據采集、數據處理和數據傳輸于一身。無線傳感網絡能應用到很多方面，而位置信息是解決很多問題的前提，只有了解傳感器節點的位置信息，才能對事件做出應對措施。定位技術是無線傳感器網絡的重要研究方向，該技術通過網絡中一些已知位置的節點使用這些節點相互交換信息，運用某種已經存在算法求得未知節點的位置信息。無線傳感器通常由兩種借點構成，一種節點是已經確定自己在網絡中位置，也就是錨節點（AnchorNode），另一種是未知節點（unknow），這種節點需要通過其他錨節點來最終確認自己的位置信息。

無線傳感網定位算法大概可以分為基于測距的定位算法和基于非測距的定位算法。基于測距的定位算法是根據測量節點之間的角度或者直接顯示的距離來實現的，這種算法在定位方面能夠表現的比較精確，但對于硬件要求較高。基于非測距的定位算法根據節點與節點之間的相互連通關系就可以實現對目標節點的鎖定，對于硬件要求低。DV-Hop定位算法不依賴于測距方法，利用多跳錨節點信息直接參與節點定位，大大提高了定位覆蓋率，故本文采用DV-Hop算法對無線傳感網節點進行定位。

1.改進的DV-Hop定位算法

在無線傳感網中進行定位時，DV-Hop算法可以通過少量的錨節點比例進行定位，為定位節省成本。如果錨節點比例太低，不存在足夠多的錨節點為未知節點進行定位，那就必須利用通信范圍外的錨節點進行距離估算，就會出現誤差。改進DV-Hop算法主要從定位精度和定位覆蓋率這兩個評價指標入手，在跳段距離和升級錨節點兩方面進行改進，以達到減小誤差、提高定位精度及覆蓋率的目的。

1.1修正一跳跳距

一跳跳距在整個網絡定位過程中起著至關重要的作用，本文的改進算法借助于RSSI測距技術對第一跳測距結果進行校正。具體步驟如下。1）監測網絡中節點互相廣播信息包，獲得傳感器節點間連通性，同時得出節點間的跳數值hopij以及任意鄰居節點間的RSSI。2）對網絡中的節點間的跳數值進行修正。本文舍棄傳統算法中跳數均為整數的思想，對RSSI進行歸一化處理，隨后把這些值當作節點間的跳數值。3）計算全網平均跳距。4）計算未知節點與錨節點距離。在選擇錨節點時，選擇跳數值最小的錨節點。5）未知節點坐標計算。

1.2升級輔助錨節點

在無線傳感網中，錨節點的不規則存在，使某些未知節點不能接收到錨節點的信息，導致這些未知節點難以實現定位。本文采用輔助錨節點技術來提高整個定位算法的覆蓋率。引入優先級Pri的概念，采用優先級把已經實現定位的未知節點升級為錨節點，再把這些錨節點應用到后續的定位中。

網絡中的錨節點廣播自身信息給未知節點，未知節點接收信息，計算優先級并排序。未知節點的優先級pri的大小由信息包數量不同來決定，當未知節點接收到不同錨節點的信息包時，優先級pri加l，依次計算出所有未知節點的優先級，并設置一個鏈表，鏈表的表頭即鏈表中最大的優先級Pri。升級為錨節點的未知節點從鏈表中刪除，輔助錨節點和網絡中原本的錨節點再次進行廣播，然后再次按優先級重新排列鏈表，直到循環完最后一個未知節點就結束。

2.仿真與分析

本文使用MATLAB軟件對改進算法和傳統DV Hop定位算法進行仿真比較，驗證改進DV Hop定位算法是否具有更好的定位性能。

對整體定位誤差進行分析，在同一網絡連通度（取20）情況下進行仿真。

由圖1可知，在錨節點的密度由小到大的整個過程中，改進算法的定位誤差在逐漸減小，并且改進算法的總體定位誤差值始終低于傳統DV-Hop算法。

如圖2所示，隨著錨節點比例的增大，改進算法和傳統算法的定位覆蓋率都在增大，但是在錨節點比例低于8%時，傳統算法的定位覆蓋率始終低于改進算法的定位覆蓋率。

3.結論

本文針對無線傳感網的借點定位問題，在傳統DVHop定位算法基礎上，利用RssI技術修正一跳跳距，并根據定位需求升級輔助錨節點。通過MATLAR對改進后的算法進行仿真，驗證了改進算法的有效性，經過仿真并分析，改進DV-Hop定位算法可以有效降低定位誤差，同時提高定位精度，在覆蓋率方面也有優良的表現。