一種基于移動信標節點加余弦定理的DV-Hop改進算法

胡平霞 丁鋒 鄧阿琴 曾斯 朱鵬

摘? ?要：為提高無線傳感器網絡節點定位精度，文章提出了一種基于移動信標節點加余弦定理的MCDV-Hop改進算法。該算法從改變移動信標節點移動軌跡基礎上通過余弦定理修正跳距，在模擬WSN場景下，通過仿真實驗表明，MCDV-Hop改進算法提高了網絡資源利用率，在一定程度上表現出較穩定的定位精度。

關鍵詞：無線傳感器網絡;定位;移動信標節點;余弦定理

中圖分類號： TP393? ? ? ? ? 文獻標識碼：A

1 引言

無線傳感器網絡（Wireless Sensor Networks， WSN）作為一個新的網絡模型在軍事、民用及商用領域都有著巨大的應用價值，逐漸成為國內外學者的研究熱點。由于無線傳感器網絡應用的復雜性，網絡節點的位置信息顯得尤為重要，節點定位技術成為WSN的關鍵技術之一。節點定位技術是指在無線傳感器網絡中，通過已知節點位置信息估算未知節點位置信息的一種技術。在無線傳感器網絡中，已知節點稱為信標節點，由于相對未知節點來說信標節點成本高，且需硬件支持，因此通常根據實際應用部署少量的信標節點，通過信標節點的位置信息來測算未知節點的位置。

根據節點定位過程中是否需要測量信標節點和未知節點間的距離，將定位算法分成免測距定位算法（Range-free）和基于測距定位算法（Range-based）兩種。其中，無需測距定位算法由于在不增加硬件開銷的情況下其定位精度基本上能滿足實際應用，具有較大的研究價值，引起國內外學者的關注。文獻[1～8]就不同的思路對非測距定位技術進行不同的研究，提出了不同的解決方案。其中，文獻[5]介紹了一種利用最鄰近信標節點的平均跳距以及加權后的M跳內信標節點的平均跳距，來測算未知節點的位置信息，M為增設的門限值。文獻[6]介紹了通過信標節點的功率控制，通過信標節點的輔助提出了基于全網信標節點修正單個信標節點的平均跳距。文獻[7]在經典DV-Hop算法的基礎上，對節點間的跳數值和平均每跳跳距進行校正和修正。文獻[8]使用加權雙曲線定位算法（WH）思想及加權DV-Hop（WDV-Hop）思想相結合的思路。非測距定位算法，不論是在理論方面，還是技術應用方面，都是未來的重要研究方向，高精度的定位成為研究關鍵技術之一。本文所做的工作就是以提高定位精度為目標提出改進的DV-Hop算法。

2 介紹經典算法

2.1經典DV-Hop算法

經典DV-Hop算法根據網絡中的跳數測算未知節點到信標節點直線距離，從而得到未知節點的位置信息。經典DV-Hop算法由于不需要增加額外硬件開銷且計算量相對較小、容易實現等特點得到國內外研究者的關注。經典DV-Hop算法對未知節點的定位過程為三點。

（1）確定未知節點與網絡中信標節點間的最小跳數值

信標節點全網廣播本節點位置信息，其它傳感節點收到信息后保存自身到信標節點數據信息，信標節點i的位置信息表示為，未知節點到網絡中其它信標節點i的最小跳數值表示為，該數據信息記為。

（2）估算未知節點與信標節點間的距離

①信標節點自身平均跳距估算

公式1

通過公式1計算信標節點間的平均跳距，，分別表示是信標節點i、j的坐標，是信標節點i和信標節點j之間的最小跳數。

②未知節點到信標節點距離估算

公式2

通過公式2來估算未知節點到信標節點的距離，是未知節點選擇最近的信標節點i的跳距平均值，是未知節點u到信標節點v的最小跳數值。

（3）確定未知節點位置

網絡中的未知節點根據第（2）步的估算結果，建立自身的位置矩陣，形成線性方程式，最后通過最小二乘法計算未知節點位置。

2.2 基于移動信標節點的DV-Hop改進算法

MADV-Hop[9]是一種基于移動信標節點的DV-Hop改進算法，通過在固定位置配置移動信標節點，移動信標節點按一定軌跡移動構建出多個虛擬信標節點、采用多個虛擬信標節點的位置信息來估算未知節點位置，取多次估算的平均值。仿真結果表明，該算法在降低成本和提高定位精度方面都有不錯的表現。

3 MCDV-Hop改進算法

本文提出了一種基于移動信標節點加余弦定理的MCDV-Hop算法，優化了移動信標節點位置及移動軌跡，在一定程度上降低了信標節點廣播浪費，通過余弦定理修正跳距[10]提高定位精準度。

3.1 改進思路

（1）優化移動信標節點部署及移動軌跡

MADV-Hop算法部署的移動信標節點呈矩形分布，如圖1所示，在中心位置、四個角及區域內部署Q、A1-A4、B1-B4共9個移動信標節點。其中，四個角的移動信標節點在廣播時，有一半的廣播信息面向區域外，存在廣播浪費現象，因此對移動信標節點位置和移動軌跡的優化十分必要。

改進后的算法在的監測區域中的固定位置部署9個移動信標節點，如圖2所示。其中，信標節點G部署在位置（），且為唯一的固定的信標節點，a1-a4 4個移動信標節點分別部署在正方形監測區域的4邊的中間（即）位置，而b1-b4 4個移動信標節點分別部署在距離4個邊緣的中間部分。

以移動信標節點a1、b1為例，它們各自按一定的間距△d沿著外圓和內圓逆時針移動，會形成一定數量的虛擬信標節點。每次移動到新位置就廣播一次位置信息，為減少浪費，每次移動的新位置不能與之前廣播過的虛擬信標節點位置重復。當全部移動信標節點所形成的虛擬信標節點對自身位置廣播達到一定次數（一般取4次）或更多時，停止移動。由于移動信標節點是沿圓形軌跡運動，移動后的新位置坐標在原位置基礎上，通過余弦定理和移動距離△d進行計算。

（2）余弦定理校正平均跳距

由于網絡中節點的分布存在緊密和稀疏的差異，當節點稀疏且呈不均勻分布時經典DV-Hop算法的定位結果會出現較大概率的誤差，從而影響了定位精度，通過余弦定理對估算后的平均跳距離進行修正，減少誤差，提高定位精度。

根據連接到每個信標節點最小跳數的傳輸路線，選擇路線中間節點。如圖3和圖4所示，為奇數時，選擇路徑的中間節點即可;為偶數時，選擇路徑中間的兩跳都將作為中間節點。其中，中間節點和信標節點連接所形成的夾角為。

可以證明[10]當為奇數時：

公式3

當為偶數時：

公式4

是兩個信標節點間的跳次，是兩個信標節點間的跳數。最后的校正調整值correct_ value可由平均跳距、實際跳距和跳數得出：

公式5

通過上述跳距校正值來校正跳距。

3.2 MCDV-Hop算法定位思想

改進算法偽代碼描述如圖5所示，定位過程描述為八點。

（1）啟動網絡并完成初始化。初始化工作包括節點信息、移動信標節點移動軌跡。

（2）信標節點使用洪泛算法廣播自身位置信息，廣播次數為4次。

（3）鄰節點處理到達的數據包。鄰節點判斷到達的數據包是不是首次來自該信標節點，若是首次收到則直接保存;不是則比較當前數據包的最小跳數和已經保存數據包的最小跳數，選擇跳數較小的數據包保存。

（4）計算平均跳距，并計算未知節點到信標節點的距離。

（5）修正平均跳距。選擇中間節點，獲得角度，使用余弦定理修正跳距，見公式3、公式4、公式5，使用修正后的平均跳距計算未知節點距離。

（6）估算未知節點位置坐標。根據信標節點坐標信息和未知節點到信標節點間的距離信息建立位置矩陣，采用最小二乘法計算未知節點坐標。

（7）信標節點按△d移動，更新位置后返回第（2）步。

（8）在未知節點至少得到3次以上自身坐標后，取平均值。

4 模擬仿真實驗

4.1 仿真環境及參數說明

仿真實驗在Matlab2016a環境下進行，仿真參數如表1所述。

模擬WSN場景為二維平面區域，節點分布見圖6，其中三角形代表信標節點，菱形代表未知節點。在100m×100m的正方形區域內布置100個未知節點和9個移動信標節點，其中未知節點坐標隨機，移動信標節點坐標預設，初始化后所有節點均能正常工作?？紤]未知節點坐標的隨機性，選擇100次仿真計算的平均值作為對比結果。

平均相對定位誤差計算公式為：

公式6

其中U是節點數，v 是信標節點數，M為通信半徑，truei為坐標真實值，cali為坐標估算值。

4.2 仿真實驗結果

（1）定位誤差分析

改進算法的定位誤差如圖7所示，縱軸為估算的節點坐標與實際坐標的偏差，橫軸為未知節點個數，最小誤差在5%以下，最大誤差約為25%。

（2）通信半徑對定位精度影響分析

在其它仿真參數不變的情況下改變通信半徑，對DV-Hop算法、MADV-Hop算法及改進后的算法MCDV-Hop的定位精度進行對比，定位半徑分別為20m、25m、30m、35m、40m、45m。圖8表明3種算法的定位精度在較大通信半徑情況下表現良好，隨著通信半徑增加定位誤差呈下降趨勢。DV-Hop算法定位精度受通信半徑變化的影響相對較小;通信半徑有30m以下時，改進算法MCDV-Hop的定位精度由于移動信標節點按圓形軌跡運動，以減少廣播資源浪費為前提犧牲少許覆蓋率，因此定位精度略小于原MCDV-Hop算法;MCDV-Hop改進算法在通信半徑30m處開始保持平緩下降趨勢，因此當通信半徑較大時，MCDV-Hop算法表現出比DV-Hop算法、MADV-Hop算法較優的定位精度。

5 結束語

通過定位誤差仿真實驗及通信半徑對定位精度仿真實驗影響仿真實驗可以看出，改進算法MCDV-Hop仿真環境下保持較穩定的定位誤差，對比DV-Hop算法和MADV-Hop算法，在節約資源降低成本前提下當通信半徑達到一定值時，表現出穩定、較小的定位精度。

基金項目：

1.衡陽市科技計劃項目（項目編號：2016KJ20）;

2.湖南省教育廳科學研究項目（項目編號：16C0565）;

3.衡陽市社會科學聯合會項目（項目編號：2017D107）;

4.湖南環境生物職業技術學院支柱工程項目（項目編號：湘環院教字〔2017〕46號）。

參考文獻

[1] Koen Langendoen，Niels Reijers.Distributed localization in wireless sensor networks： a quantitative comparison [J]. Computer Networks， 2003， 43（4）： 499-518.

[2] Zhongmin Pei，Zhidong Deng，Shuo Xu，Xiao Xu.Anchor-Free localization methord for moblie targets in coal mine wireless sensor networks[J].SENSORS， 2009， 9（4）：2836-2850.

[3] Yun Wang， Xiaodong Wang， Demin Wang，and Dharma P. Agrawal. Range-free localization algorithm using expected[J].IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS， 2009， 20（10）：1540-1552.

[4] He Yuanhua， Li Hongsheng.A distributed node localization algorithm based on believable factor wireless sensor network[A].Proceedings-5th International Conference on wireless Communications， Networking and Mobile Computing （WiCOM 2009） [C]. Beijing， 2009：1-4.

[5] HU Y，LI X. An improvement of DV-Hop localization algorithm for wireless sensor networks [J]. Telecommunication Systems，2013，53（1）：13-18.

[6] 陶志勇，魏強，劉影.多功率錨節點輔助的DV-Hop定位算法[J].計算機工程與應用，2014（21） ：121-124，156.

[7] 夏少波，鄒建梅，朱曉麗，等.無線傳感器網絡DV-Hop定位算法的改進[J].計算機應用，2015（2） ：340-344.

[8] MASS-SANCHEZ J，RUIZ-IBARRA E，et al. Weighted Hyperbolic DV-Hop Positioning Node Localination Algorithm in WSNs[J].Wireless Personal Communications，2017，96（1-23）：5011-5033.

[9] 馮友兵，馬艷，魏玉婷.基于移動錨節點的改進DV-Hop算法[[J].計算機科學，2015， 42（s2）：277-279.

[10] Wu H， Deng M， Xiao L， et al. Cosine Theorem-based DV-Hop Localization Algorithm in Wireless Sensor Networks[J]. Information Technology Journal， 2011，10（2）：239-245.

作者簡介：

胡平霞（1984-），女，漢族，湖南永州人，廣西師范大學，碩士，湖南環境生物職業技術學院，副教授;主要研究方向和關注領域：計算機軟件與理論、職業教育教學改革。

丁鋒（1984-），男，漢族，湖南常德人，中南林業科技大學，本科，湖南環境生物職業技術學院，助理研究員;主要研究方向和關注領域：計算機軟件與理論。

鄧阿琴（1980-），女，漢族，湖南醴陵人，南華大學，碩士，湖南環境生物職業技術學院，副研究員;主要研究方向和關注領域：網絡理論基礎研究。

曾斯（1984-），女，漢族，湖南衡陽人，衡陽師范學院，碩士，湖南環境生物職業技術學院，講師;主要研究方向和關注領域：網絡基礎理論研究、計算機教育。

朱鵬（1981-），男，漢族，湖南衡陽人，東華理工大學，本科，湖南環境生物職業技術學院，實驗師;主要研究方向和關注領域：計算機網絡應用。