基于OMNeT++平臺的DV-Hop 定位算法改進

劉 排，武 一，南京婭，劉建民

(1.河北工業大學 信息工程學院，天津300401;2.天津現代職業技術學院 機電工程學院，天津300350)

0 引 言

無線傳感器網絡(WSNs)中，位置信息對無線傳感網絡的監控活動至關重要，事件發生的位置是無線傳感器節點監控消息中所包含的重要信息，沒有位置信息的監控消息往往毫無意義。因此，確定事件發生的位置對無線傳感網絡應用的有效性起著關鍵作用［1］。

根據定位機制可將現有無線傳感器網絡自身定位算法分為基于測距的和無需測距的定位算法兩類。無需測距的算法不需要節點自身的測距設備，通過跳數或是其他信息估計自身到選定的信標節點的距離值。由于是估計得到的數值，相對于基于測距的算法獲得的距離值誤差偏大。常用的定位算法有質心法、凸規劃、DV-Hop 算法、Amorphous算法、MDS-MAP 和APIT 算法等，DV-Hop 算法因憑借其定位過程實現簡單，對節點硬件要求不高，在各向同性的網絡中性能良好等優勢，成為了目前應用最廣泛的算法之一。

但是DV-Hop 算法的未知節點依靠測量與鄰近信標節點之間的距離來推算自身位置產生的誤差較大，為此，本文提出了通過定位出離信標節點距離較近的未知節點升級為信標節點的方法來減小定位中的誤差，并且采用自由搜索算法取代誤差較大的三邊測量法來計算未知節點坐標，并在仿真平臺OMNET++上驗證。

1 DV-Hop 算法過程

傳統的DV-Hop 算法的實現過程大致分為三步驟:

1)網絡中的各個節點采用典型的距離矢量交換協議，信標節點發起第一次泛洪廣播，廣播的信息包括自己的ID，坐標信息和初始跳數。直到網絡中的所有節點都獲得信標節點的廣播信息。

2)當信標節點獲得其他信標的位置和相隔跳數后，信標節點利用下面公式來計算平均毎跳距離

式中 (xiyi)為信標節點的坐標，hi為信標節點i 與j(j≠i)之間的跳段數。信標節點發起第二次泛洪廣播，將計算出的平均跳距廣播到網絡中，未知節點利用接收到的平均跳數值和第一階段中得到的距各個錨節點跳數來近似計算到各個參考節點之間的距離［2］。

3)當未知節點獲得距離錨節點的估算距離后，利用三邊測量法或極大似然法來估計節點的二維坐標值，實現節點的定位［3］。

2 DV-Hop 算法的改進

DV-Hop 算法在計算未知節點與信標節點的距離時，使用折線距離代替直線距離，這樣就會導致在拓撲結構不均勻的傳感網絡中定位誤差很大［4］。在對未知節點的坐標進行估算時，通常用的三邊測量法和極大似然法也存在極大誤差。針對DV-Hop 算法的以上不足，本文提出了以下的改進方法。

2.1 基于RSSI 測距增加信標節點的改進方法

大量實驗表明:定位誤差較大的未知節點通常是那些遠離信標節點的節點，增加信標節點的數目是最直接而有效的方法，但信標節點價格昂貴，能耗大，這種方法并不可取。因此，本文提出了基于RSSI 測距增加信標節點的改進方法。首先讓所有信標節點利用可控范洪進行廣播，信標節點發出的消息后只經過一跳，就將消息刪掉不再轉發，利用RSSI 測距的方法，計算出信標節點與未知節點的距離，如果有未接節點接知到三個及以上信標節點發來的消息，便可用三邊測量法確定出此未知節點的位置［5］，確定出位置的未知節點便可升級為信標節點。

如圖1 中，其中，●代表信標節點模塊，○代表未知節點模塊，A，B，C，D，E 節點都接收到了三個臨近信標節點的消息，利用RSSI 測距的方法分別計算出與信標節點的距離，考慮到增加信標節點在進行泛洪廣播的能耗會增加，所以，當增加信標節點時要進行選擇，圖中A，B 節點都接收到了信標節點2 發來的消息，所以，A，B 只將其中一個升級為信標節點即可，再利用三邊測量法，計算出未知節點的坐標，這些計算出坐標的節點便可升級為信標節點。這樣可在不增加額外硬件的基礎上，便可增加定位的精度。

2.2 基于加權的自由搜索

圖1 傳感器網絡節點分布圖Fig 1 Distribution of WSNs node

自由搜索(free search，FS)算法是一種吸收了GA，ACO算法，PSO 算法等算法的優勢的新型智能優化算法，FS 算法具有較快的全局收斂性和較強的自適應性能力，在解決DV-Hop 算法定位的優化問題顯示出了優勢。在FS 算法模型中，一個種群包含有m 個個體，m 個個體在半徑為R 的搜索空間內移動，每個個體的移動包括全局內的搜索和局部范圍內的搜索［6］，一次迭代個體移動一個搜索步，每個搜索步包含T 小步，個體對搜索步內找到的較優解進行記錄，稱為標記信息素，其大小與目標函數的適應度呈正比，每完成一次迭代，信息素將會被完全更新。個體的搜索本質上是一種標記信息素的過程，這些信息素將做為所有個體在下一次搜索開始時，選擇起始點的依據之一，另一個依據則是個體的靈敏度［7］。當個體的靈敏度小于信息素時，個體受其影響改變搜索起點，選擇搜索步T 中的最佳位置做為下一次搜索的起點;否則，個體不改變搜索起點，仍使用上一次迭代的搜索起點。

1)初始化

需要初始化的變量有:種群包含的個體m，空間維數d，搜索步中的搜索小步數T，搜索半徑R，搜索空間的范圍［Vmin，Vmax］，最大迭代次數Gmax。m 個個體被隨機分散到搜索空間內

式中 rand(0～1) 為0～1 之間的隨機實數。

2)搜索過程

所有個體在一個搜索步內行走T 小步，搜索到T 個新的位置。搜索過程中，目標函數的適應度記作

式中 fk為個體k 搜索到的T 個新位置中，對應的目標函數最佳值。信息素的定義如下

式中 min(fk)為所有個體中找到的最佳適應值。靈敏度的定義如下

式中 Smax為Smin靈敏度的最大和最小值，Pmax和Pmin為信息素的最大和最小值，并規定Smax=Pmax，Smin=Pmin;一個搜索步完成后，確定下一個搜索步，即下一次迭代的起始點

式中 Xhk為個體k 在搜索步T 內搜索到的最佳位置。

3)終止判斷

FS 算法的判斷標準有三種:

a.達到全局最優解:fmin＜fopt

b.當前迭代數g 大于最大迭代次數Gmax:g ＞Gmax

c.上述條件滿足其中之一即可。

目標函數的獲得:

由未知節點到信標節點的距離可得

其中xi，yi分別信標節點i 的x，y 坐標，di為未知節點到信標節點i 的距離。由上式可得

目標函數為

其中，wi為權值，n 為信標節點的個數。

3 仿真結果與分析

為了驗證改進算法的有效性，采用OMNeT++進行仿真，仿真結果導入到Matlab 中進行提取和分析。仿真面積是400m×400 m 的正方形區域，節點間的通信半徑為100 m，未知節點和信標節點在仿真區域內隨機分布，平均誤差作為評定定位精度的標準，其公式如下

自由搜索算法的參數設定:種群包含的個體數量m=60，最大迭代次數Gmax=600，搜索小步總數T=60，搜索半徑R=0.1 m，x，y 坐標的搜索范圍均為0～400 m。

3.1 算法穩定性能仿真結果

為了得到更加合理、接近于實際的仿真數據，對100 個傳感器節點其中信標節點比例為5%的定位進行仿真22 次。

從圖2 可得出，傳統的DV-Hop 算法在仿真次數小于10 次時，誤差的波動較大，在仿真次數大于10 次后，雖相對穩定但也有小幅度的波動。而改進的DV-Hop 算法則一直處在比較穩定的狀態。經仿真數據計算可得，傳統的DV-Hop 算法的均方差為4.36，改進后的均方差為1.35。改進后的節點的定位在穩定性能上要優于原始的DV-Hop算法。

圖2 仿真次數對定位精度的影響Fig 2 Effect of simulation numbers on positioning precision

3.2 算法在精度上的仿真結果

為了驗證改進后算法在精度上的提高，對100 個傳感器節點進行仿真，傳統的DV-Hop 算法與改進后的DV-Hop算法誤差對比圖如圖3 所示。

圖3 不同信標比例下的定位誤差Fig 3 Localization error of different beacon ratio

從上圖得出，無論上傳統的DV-Hop 算法還是改進的DV-Hop 算法在整體上都是隨著信標比例的增大，誤差會越來越小。傳統DV-Hop 算法在信標比例大于15%后，誤差減小的幅度越來越小。改進后的DV-Hop 算法在誤差會隨著信標比例的增多而平穩下降，且在信標比例較小時，改進的DV-Hop 算法的優勢表現的更加明顯。

圖4 節點個數對定位精度的影響Fig 4 Effect of node numbers on localization precision

由圖4 可得，相較于傳統的DV-Hop 算法，改進的算法在不同節點數目下的平均誤差都普遍減小。其中在節點個數為240 時，改進后的DV-Hop 算法在精度上提高了15.3%，說明了改進后的DV-Hop 算法在提高算法精度上有了很大提高。

4 結 論

針對傳統的DV-Hop 算法定位精度較低、算法穩定不高的缺點，本文提出了用RSSI 測距增加信標的改進方法，在不增加節點能耗的基礎上，提高了算法的精度，并且用自由搜索算法取代了原來誤差較大的三邊測量法，自由搜索算法具有較快的全局收斂性和較強的自適應性能力，恰好符合了DV-Hop 算法的定位要求，仿真結果表明:改進后的定位算法在定位穩定性上有了明顯的提高，相較于傳統的DV-Hop 算法，改進的DV-Hop 算法性能穩定，其定位誤差率減小了13.5%左右。

［1］ 方光偉.基于OMNeT+ +平臺Gossiping 協議的仿真實現［J］.科技信息，2010(22):208－209.

［2］ 王福豹，史 龍，任豐原.無線傳感器網絡中的自身定位系統和算法［J］.軟件學報，2005，16(5):857－868.

［3］ 楊石磊，樊曉平，劉少強，等.一種改進的無線傳感器網絡DV-Hop 定位算法［J］.計算機測量與控制，2008，16(9):1356－1358.

［4］ 劉 杰，董淑福，溫 東，等.基于移動信標的改進DV-Hop算法［J］.傳感器與微系統，2013，32(5):142－145.

［5］ Penev K，Littlefair G.Free search—A comparative analysis［J］.Information Sciences，2005，172(1/2):173－193.

［6］ 周 暉.自由搜索算法及其在傳感器網絡中的應用［D］.上海:東華大學，2010.

［7］ Pottie G J，Kaiser W J.Wireless integrated sensor networks［J］.Communications of the ACM，2000，43(5):51－58.