基于CC2510 的DV-Hop 定位算法的改進*

裴菊靜，王經卓，許紅艷

(1.中國礦業大學 信息與電氣工程學院，江蘇 徐州221116;2.淮海工學院 電子工程學院，江蘇 連云港222005)

0 引 言

無線傳感器網絡是是由大量未知節點隨機部署形成的自組織網絡。由于這些未知節點的位置是未知的，如果要采集、處理未知節點的信息，必須要知道它們的位置，因此，定位技術是無線傳感器網絡現在研究的重點。

在定位算法中根據定位過程是否需要測量節點之間的實際距離，把定位算法分為無需測距(range－free)的定位算法和基于測距［1］(range－based)的定位算法。前者不需要測量節點間的實際距離，而是利用節點間的估計距離計算節點間的實際距離，后者需要測量相鄰節點間的實際距離來計算未知節點的位置。基于測距的定位算法雖然定位精度較高，但它并不適用于低功耗、低成本的應用領域。距離無關的定位算法精度較低，但能滿足大部分無線傳感器網絡的要求，因此，在實際應用中普遍使用。常用的無需測距的定位算法有質心定位算法、DV－Hop 算法、MDS－MAP 算法、Bounding－Box 定位算法、近似三角形內點測試法(APIT)等。

1 DV-Hop 和改進的算法

1.1 DV－Hop 算法

DV－Hop［2］算法是由 Niculescu 和 Nath 提出來的，它的基本思想是通過運用節點間的跳數和每跳的距離來估計節點間的實際距離。具體算法分為3 個步驟:1)使用經典的距離矢量交換協議，信標節點發送自己的位置信息和跳數，是所有節點獲得信標節點的最小跳數;2)信標節點根據自身記錄的其他信標節點的位置和跳數根據公式計算平均每跳距離，則未知節點可以計算到相對應的信標節點之間的距離;3)當未知節點收到不小于3 個到信標節點的距離時，可以根據三邊定位或最小二乘法計算自身坐標

式中 ci為平均每跳距離;(xi，yi)，(xj，yj)為錨節點 i 和 j的坐標，hi為跳數。

1.2 改進的算法

Chipcon 公司的CC2510 芯片是一種內嵌8051 單片機的低功耗的芯片，內部具有無線定位引擎，它的定位功能是基于接收信號強度指示(RSSI)測距［3］。在RSSI 定位過程中，未知節點根據接收到的信號強度值計算信號的傳播損耗，根據對應的傳播模型可以將傳播損耗轉換成距離。未知節點可以把自己獲得的坐標和RSSI 值傳送到CC2510 組成的定位模塊，然后由內部的定位引擎計算得到自身坐標。在改進的算法中，用CC2510 設計硬件節點［4］。

在DV－Hop 算法的第一階段中要用到洪泛法，使節點能量開銷很大，在估算未知節點到信標節點之間跳數時，當跳數為1 跳時，可以直接通過RSSI 測距法來計算1 跳距離，這樣會降低整個網絡的功耗和減小定位誤差。在第二階段中，信標節點廣播自己的位置信息，未知節點收到不小于3個信標節點的位置信息時，通過RSSI 測距法［5］的信號強度值選取離自己最近的3 個信標節點存入自己的數據包，當信標節點繼續發送信息，未知節點從接收到的信息中比較，當RSSI 值大于自己存儲的數據時，則存入數據包;否則，丟棄。然后選取3 個最大RSSI 值的信標節點計算平均每跳距離。在第三階段當用三邊測量計算自身坐標時，未知節點就用第二階段獲得的3 個信標節點計算。

改進的算法降低了第一階段洪泛法的能量損耗，當距離為1 跳距離時直接用測得的RSSI 求出距離。還可以減小第二階段求平均每條距離帶來的誤差，因為未知節點計算距離時不再統一用固定的平均每跳距離，而是根據自身儲存的信息選取合適的信標節點來計算。改進的算法流程［6］如圖 1。

圖1 改進算法的流程圖Fig 1 Flow chart of improved algorithm

2 仿真實驗

為了驗證上述改進算法的有效性，用CC2510 設計的節點硬件進行了模擬實驗，并且對定位算法進行了Matlab 仿真［7］，在100 m×100 m 的正方形區域隨機部署100 個節點，其中，信標節點為10 個，通信半徑為50 m。圖2 和圖3 分別為節點的隨機分布和未知節點的定位誤差，實驗結果可以得到定位誤差降低到20%左右，證明了本算法可以適當減小定位誤差。

圖2 節點的分布Fig 2 Distribution of nodes

圖3 節點的定位誤差Fig 3 Localization error of nodes

通過改變信標節點的數目，再次驗證算法的精確度，測量改進算法的誤差和原來的算法相比較得到圖4。從圖中可以看出:隨著信標節點的增加，定位誤差逐漸減小，并且改進后的DV－Hop 算法對于信標節點的變化具有較好的穩定性［8］。

圖4 改進算法前后的定位誤差圖Fig 4 Localization error diagram before and after the algorithm is improved

3 結 論

針對DV－Hop 算法的特點，本文提出了基于 CC2510 定位引擎的RSSI 測距技術的改進的定位算法，在第一階段當跳數為1 時，直接采用RSSI 測距，減少了第二階段的能量開銷，降低了誤差，在第二階段采用RSSI 測距技術選取合適的信標節點求平均每跳距離，并且在三邊測量求未知節點的坐標時，可以參照第二階段選取的信標節點。仿真結果表明:改進的定位算法比傳統的DV－Hop 顯示出了優越的性能，且定位的精度得到提高。

［1］ 王汝傳，孫力娟.無線傳感器網絡技術及其應用［M］.北京:人民郵電出社，2011.

［2］ 劉文遠，王恩爽，陳子軍.無線傳感器網絡中DV－Hop 定位算法的改進［J］.小型微型計算機系統，2011，6(6):1072 －1073.

［3］ Wu Lingfei，Meng Qinghu，Liang Huawei.A collinearity－based localization algorithm for wireless sensor networks［J］.Chinese Journal of Sensors and Actuators，2009，22(5):722 －727.

［4］ Yang Zheng，Liu Yunhao.Quality of trilateration:Confidencebased iterative localization［J］.IEEE Transactions on Parallel and Distributed Systems，2009，99(2):631 － 640.

［5］ Huw W，Qin H B，Huang H Y.A mobile beacon－based method for wireless sensor networks localization［C］//Proceedings of The 11th IEEE International Conference on Communication Technology，2008:1 －4.

［6］ 史洪宇，燕 莎.WSNs 中一種改進的DV－Hop 節點定位算法電光與控制［J］.電光與控制，2011，18(4):93 －95.

［7］ Wu Xiaobing，Chen Guihai，Das S K.The energy hole problem of non－uniform sensor distribution［J］.Chinese Journal of Computers，2008，31(2):253 －261.

［8］ Chen H，Kaoru S，Deng P，et al.An improved DV－Hop localization algorithm with reduced node location error for wireless sensor networks［J］.Communications and Computer Sciences，2008，91(8):2232 －2236.