基于ASGSO算法的改進DV-Hop算法*

趙曉青，毛永毅

（西安郵電大學 電子工程學院，陜西 西安 710061）

基于ASGSO算法的改進DV-Hop算法*

趙曉青，毛永毅

（西安郵電大學 電子工程學院，陜西 西安 710061）

針對無線傳感器網(wǎng)絡定位技術中DV-Hop算法在最后階段計算待定位節(jié)點坐標時定位精度低的問題，提出了一種基于自適應步長螢火蟲優(yōu)化算法的改進DV-Hop算法（ASGSODV-Hop）。該算法將DV-Hop算法在估算節(jié)點坐標階段所使用的最小二乘法用ASGSO算法代替，采用ASGSO智能算法的自適應迭代尋優(yōu)對DV-Hop算法定位求解的問題建立特定的適應度函數(shù)并進行多次迭代計算實現(xiàn)優(yōu)化，最終使待定位節(jié)點坐標與真實值更為接近。仿真結果表明，該算法的平均定位誤差約為23.58%；相比于傳統(tǒng)DV-Hop算法，ASGSODV-Hop算法可在無需附加通信開銷的情況下使定位誤差降低約46.49%，提高了節(jié)點的定位精度。

無線傳感器網(wǎng)絡；DV-Hop算法；ASGSO算法；自適應迭代；定位精度

0 引言

無線傳感器網(wǎng)絡 （Wireless Sensor Networks，WSNs）是一種集信息采集、處理和傳輸于一身的智能網(wǎng)絡信息系統(tǒng)［1］，可在任何時間、地點和環(huán)境下獲取各種詳細、精確的目標信息，實現(xiàn)人與物理世界的通信和信息交互，節(jié)點定位技術為WSN的關鍵技術。目前與定位相關的算法可分為測距和非測距兩種，測距定位算法通常有很高的精度，但需要較大的通信開銷和能耗；非測距定位算法是通過網(wǎng)絡連通性來實現(xiàn)定位，無需附加的硬件支持，是目前定位機制的研究重點。傳統(tǒng)的非測距定位算法有質心算法［2］、DV-Hop算法［3-4］、近三角形內點測試法（Approximate Point-in-triangulation Test，APIT）［5］等。

DV-Hop算法采取距離向量—跳段機制，由于其實現(xiàn)難度低，是一種常見的非測距定位算法。目前很多學者提出了一些改進算法以提高定位精度：文獻［6］采用改進的加權最小二乘法得到待定位節(jié)點的坐標以提高定位精度，但通信量過大；文獻［7］采用蝙蝠算法（Bat Algorithm，BA）對DV-Hop算法的定位結果進行優(yōu)化，但消耗了過多的資源；文獻［8］采用誤差跳距加權策略修正平均跳距，并利用自適應步長粒子群優(yōu)化（Self-adaptive Step Particle Swarm Optimization，ASPSO） 算法對DV-Hop算法的估計位置進行優(yōu)化，精度有所提升，但增加了計算量和通信開銷。本文采用自適應步長螢火蟲優(yōu)化 （Self-adaptive Step Glowworm Swarm Optimization，ASGSO）算法［9］對估算位置進行優(yōu)化。仿真結果表明，在無需附加通信量和計算開銷的基礎上可減少定位誤差，經(jīng)過優(yōu)化后算法的定位精度遠大于DV-Hop算法的精度。

1 DV-Hop算法

DV-Hop算法是由Rutgers大學的 Dragons等人依據(jù)距離矢量路由和全球定位系統(tǒng) （Global Positioning System，GPS）提出的一種非測距定位算法。其原理是采用距離矢量路由法得到待定位節(jié)點與信標節(jié)點間的跳數(shù)最小值，同時計算出平均跳距，以平均跳距與跳數(shù)最小值的乘積作為信標節(jié)點和待定位節(jié)點的估算間距，并通過極大似然估計法計算出待定位節(jié)點的坐標。DV-Hop算法可大體分為以下 3個階段：

（1）獲取待定位節(jié)點和信標節(jié)點間的最小跳數(shù)

由信標節(jié)點向相鄰節(jié)點傳送自身信標信息，包含信標節(jié)點的標識符、位置及跳數(shù)值，將跳數(shù)初始化為0。記錄并更新所接收信標信息的鄰居節(jié)點到每一信標節(jié)點的最小跳數(shù)并忽略較大的信標信息，跳數(shù)的值增加 1，繼續(xù)向其鄰居節(jié)點廣播自身信息。當網(wǎng)路中的全部待定位節(jié)點均記下距每一信標節(jié)點的跳數(shù)最小值后此階段終止。

（2）待定位節(jié)點與信標節(jié)點間距離的估計

經(jīng)過第一階段，信標節(jié)點 i得到與其余信標節(jié)點之間的位置信息和最小跳數(shù)后，用式（1）可計算出信標節(jié)點i與其余信標節(jié)點之間的平均跳距：

其中，（xi，yi），（xj，yj）分別表示信標節(jié)點 i、j的坐標，hj表示i距 j的跳數(shù)。

然后，信標節(jié)點將平均跳距分組擴散至整個網(wǎng)絡內，可通過最小跳數(shù)和式（2）獲取待定位節(jié)點與其他信標節(jié)點的間距。

（3）待定位節(jié)點自身位置的估算

已知（xi，yi）是第 i個信標節(jié)點的坐標，它到待定位節(jié)點M的距離為di，設（x，y）是待定位節(jié)點M的坐標，則有：

將式（3）變換成線性方程組 AX=b的形式，其中：

2 改進的DV-Hop算法

WSN定位問題實質上是對非線性方程組進行求解，為NP難解問題。DV-Hop算法在計算待定位節(jié)點和信標節(jié)點的間距時，由于待定位節(jié)點認為它到信標節(jié)點的平均跳距是相同的，會造成較大的定位誤差。目前為止，已有學者提出用元啟發(fā)式算法對定位后期的位置進行優(yōu)化，如前文提到的BA算法和ASPSO算法。本文采用ASGSO算法對DV-Hop算法求出的待定位節(jié)點位置進行優(yōu)化。

2.1 ASGSO算法

2.1.1 自適應步長調整策略

螢火蟲群優(yōu)化 （Glowworm Swarm Optimization，GSO）算法［10］是一種群智能算法，利用螢火蟲發(fā)光吸引同伴這一現(xiàn)象進行模擬，發(fā)光越強便可吸引越多的同伴，每個螢火蟲通過移向目標區(qū)域內最亮螢火蟲尋求最優(yōu)解。

原始GSO算法存在易陷入局部最優(yōu)的缺陷，其計算精度較低，且最后階段收斂速度較慢，這些問題與步長密切相關。尋優(yōu)時螢火蟲的移動步長越大則越容易尋求到全局最優(yōu)解，但其尋優(yōu)精度隨之降低，甚至會出現(xiàn)震蕩；移動步長小會造成尋優(yōu)速度慢，但尋優(yōu)精度得到提高。

針對此問題提出的ASGSO算法解決了原始GSO算法中存在的問題，有極好的尋優(yōu)能力和尋優(yōu)精度。引入熒光因子：

其中，Xi為第 i只螢火蟲的狀態(tài)，Xext為熒光素濃度最大的螢火蟲的狀態(tài)，dmax為最優(yōu)螢火蟲與剩余螢火蟲的最大距離。

自適應步長調整辦法為：

式中，smax和 smin為尋優(yōu)步長的最大值和最小值，Hi為熒光因子。

根據(jù)式（7）、（8）自適應變換迭代步長，當螢火蟲個體與目標螢火蟲距離較近時，Hi值減小，則 si值相應減小，使用略小的步長si可使螢火蟲接近目標個體，精度得以提高；當螢火蟲與目標螢火蟲距離較遠時，Hi值的增大會造成 si值增大，可使螢火蟲在步長略大時實現(xiàn)快速尋優(yōu)。ASGSO通過靈活調整搜索步長提升了尋優(yōu)的速度和精度。

2.1.2 算法描述

ASGSO算法流程如下：

（1）初始化。n只螢火蟲組成螢火蟲群，設定搜索維數(shù)m，感知最大半徑rs及其變化系數(shù)β，最大迭代次數(shù)itermax，熒光素揮發(fā)系數(shù) ρ及其更新率 γ，優(yōu)秀螢火蟲個體數(shù) nt，原始位置 xi（0），原始熒光素大小 l0和感知范圍r0，原始步長 si（0），最大步長 smax，最小步長 smin。

（2）熒光素更新。 J（xi（t））為迭代位置 xi（t）的目標函數(shù)。將螢火蟲在 t次迭代位置 xi（t）相對應的 J（xi（t））轉換成熒光素值 li（t）=（1-ρ）li（t-1）+γJ（xi（t）），螢火蟲選取比自身熒光素高的個體組成鄰域集 Ni（t），其中，0＜rdi（t）≤rs，rs為螢火蟲的感知半徑。

（3）概率選擇。 個體 i移至鄰域集個體 j的概率 pij用輪盤賭選取個體 j。

（4）自適應步長改變。利用式（7）計算每個個體的熒光因子，用式（8）計算出步長值。

（5）位置更新。根據(jù)xi（t+1）=xi（t）+s更新位置。

（6）更替決策域。 由 rdi（t+1）=min｛rs，max｛0，rdi（t）+ β（ni-|Ni（t）|）｝｝更新動態(tài)決策域半徑。

（7）迭代結束。判斷是否完成所設定的迭代次數(shù)，如果是則輸出結果；否則轉至步驟（2）。

2.2 基于ASGSO算法的改進DV-Hop算法

DV-Hop算法進行定位時，由于距離的不確定性導致誤差存在。定位問題的要點是使誤差達到最小，即提高定位精度，因此提出一種基于 ASGSO算法的改進DV-Hop算法，即ASGSODV-Hop算法。

設待定位節(jié)點的坐標為（x，y），利用式（2）可得待定位節(jié)點與第 i個信標節(jié)點的估算間距為 di，信標節(jié)點的估計間距與真實間距的偏差為 εi，則式（3）可改為：

通過觀察式（9）可以看出，當（|ε1|+|ε2|+…+|εn|）的值最小時，所求得的未知節(jié)點（x，y）與真實節(jié)點位置最為接近。由于信標節(jié)點與待定位節(jié)點間的跳數(shù)越多會導致兩者間距的估計偏差越大，故將其跳數(shù)的倒數(shù)當作權重設置ASGSO算法的適應度函數(shù)，如式（10）所示。完成所設定的運算次數(shù)后即可結束 ASGSO算法，以所尋求的最優(yōu)值當作優(yōu)化后的估算值。

其中，hi為待定位節(jié)點（x，y）與信標節(jié)點（xi，yi）間的跳數(shù)，1/hi為權重。

3 仿真實驗

為評估ASGSODV-Hop算法的性能，分別對DVHop算法改進前后進行仿真，分析比對仿真得到的結果。將若干節(jié)點散播在 100m×100m正方形感知區(qū)域內，信標節(jié)點占 10%，待定位節(jié)點占 90%。為了降低隨機性誤差，在同等參數(shù)條件下進行 100次仿真，取其均值作為實驗結果。

本文選取文獻［11］提到的定位誤差作為性能評價指標，如式（11）所示：

其中，R為通信半徑，（xr，yr）為待定位節(jié)點的真實坐標，（xi，yi）為使用ASGSODV-Hop算法得出的待定位節(jié)點坐標，N為待定位節(jié)點的個數(shù)。

3.1 算法參數(shù)設置

設定種群規(guī)模 n=50，維數(shù)m=2，揮發(fā)系數(shù) ρ=0.4，更新率 γ=0.6，初始熒光素大小 l0=5，感知范圍 r0=10，初始步長 si（0）=0.03，變化系數(shù) β=0.08，最大迭代次數(shù)itermax=200。

3.2 算法仿真結果分析

將 200個節(jié)點隨機部署在上述網(wǎng)絡拓撲結構中，通信半徑設置為R=30m，圖1和圖2分別為DV-Hop算法和 ASGSODV-Hop算法的定位誤差圖，圖中‘*’表示信標節(jié)點，‘o’ 表示待定位節(jié)點估計位置，‘▽’ 表示待定位節(jié)點實際位置，‘o’和‘▽’之間的連線表示待定位節(jié)點的定位誤差，線段越長，定位誤差越大，反之越小。從圖中可看出，改進算法的估計位置和實際位置之間的線段更短，即它們之間的定位誤差更小。通過DV-Hop算法得出的平均定位誤差為 17.48， 定位精度為 34. 96%，ASGSODV-Hop算法的平均定位誤差為 10.62，定位精度為21.24%。由此可知ASGSODV-Hop算法的平均定位誤差和定位精度明顯優(yōu)于傳統(tǒng)DV-Hop算法。

圖1 傳統(tǒng)DV-Hop定位誤差

圖2 ASGSODV-Hop定位誤差

在定位技術中，通信半徑、節(jié)點數(shù)及網(wǎng)絡連通度的變化都會影響定位精度，下面分別討論兩種算法在不同通信半徑、不同信標節(jié)點數(shù)以及不同網(wǎng)絡連通度條件下的定位精度。

（1）不同通信半徑

圖3表示通信半徑從 15m～40m時兩種算法的平均定位誤差曲線圖，在區(qū)域內隨機部署 200個節(jié)點，20個信標節(jié)點。從圖中可知，在同樣參數(shù)條件下，兩種算法的平均定位誤差均隨通信半徑的不斷增加逐漸降低，并且當通信半徑在 15m～30m范圍內時，平均定位誤差下降速率較快；通信半徑在 30m以后時，平均定位誤差趨于穩(wěn)定，并且在穩(wěn)定區(qū)域內，ASGSODV-Hop算法的平均定位誤差比 DV-Hop減小約35.28%。在整個通信半徑變化區(qū)域內，與DV-Hop算法相比較，ASGSODV-Hop算法的平均定位誤差可降低約 43.51%，使精度明顯提升。

圖3 不同通信半徑下平均定位誤差曲線圖

（2）不同節(jié)點數(shù)

圖4表示通信半徑為 R=30m、信標節(jié)點數(shù)為 20時，節(jié)點總數(shù)由 100變化至 400的平均定位誤差曲線。從圖中可看出，在相同條件下兩種算法的平均定位誤差均隨節(jié)點數(shù)的增大而減小，并且當節(jié)點數(shù)在 200～400之間時，待定位節(jié)點誤差趨于穩(wěn)定。經(jīng)分析可知 ASGSODV-Hop算法的平均定位誤差比 DV-Hop算法降低了約47.98%；當節(jié)點數(shù)小于200時兩種算法的定位誤差下降幅度較大，此時與傳統(tǒng)DV-Hop算法相比，ASGSODV-Hop算法的平均定位誤差可下降約52.73%。

圖4 不同節(jié)點數(shù)下平均定位誤差曲線圖

（3）不同網(wǎng)絡連通度

由于 DV-Hop算法是根據(jù)網(wǎng)絡連通性來進行定位的，網(wǎng)絡連通度這個概念一定意義上可反映定位區(qū)域中節(jié)點間的相互位置、節(jié)點通信半徑以及節(jié)點數(shù)量間的相互關系。圖5為不同網(wǎng)絡連通度下兩種算法的平均定位誤差曲線，從圖中可清晰看出隨著網(wǎng)絡連通度參數(shù)值的升高定位誤差逐漸減小，當網(wǎng)絡連通度大于20時，兩種算法的定位誤差值變化都比較平緩。與傳統(tǒng)DV-Hop算法相比，ASGSODV-Hop算法的平均定位誤差降低約51.76%。

4 結論

圖5 不同網(wǎng)絡連通度下平均定位誤差曲線圖

本文在充分研究DV-Hop算法的基礎上，針對定位精度較低這一缺點，在無需附加硬件和通信量的條件下采用ASGSO算法對DV-Hop算法的待定位節(jié)點坐標進行優(yōu)化。通過理論分析和算法仿真實驗證明，經(jīng)ASGSO算法優(yōu)化后的 DV-Hop算法使定位誤差下降約46.49%，定位精度得到明顯提高。此外，ASGSO算法的高效運行可有效提高 DV-Hop算法在 WSN中的適用性，使其應用更為廣泛。

［1］鄭軍，張寶賢.無線傳感器網(wǎng)絡技術［M］.北京：機械工業(yè)出版社，2012.

［2］BULUSU N，HEIDEMANN J，ESTRIN D.GPS-less low cost outdoor localization for very smal devices［J］.IEEE PersonalCommunications Magazine，2000，7（5）：28-34.

［3］NICULESCU D，NATH B.DV-based positioning in ad hoc networks［J］.Journal of Telecommunication Systems，2003，22（1）：267-280.

［4］NICOLESCU D，NATH B.Ad-Hoc positioxung systems（APS）［C］.Proc.of the 2001 IEEE Global Telecommunications Conference，San Antonio，USA，2001：2926-2931.

［5］He Tian，Huang Chengdu，BRIANm B，et al.Range-free localization schemes for large scale sensor networks［C］.In Proceedings of the 9th Annual International Conference on Mobile Computing and Networking，New York，USA，ACM Press，2003：81-95.

［6］涂巧玲，宋佳，胡濤.一種加權的DV-Hop定位改進算法［J］.通信技術，2013，46（9）：58-60.

［7］曹欲曉，張倩，李艷冰，等.基于蝙蝠算法的 DV-Hop定位改進［J］.計算機測量與控制，2015，23（4）：1273-1275.

［8］李仁和，丁勤，王洪元，等.基于自適應粒子群算法的改進DV-Hop定位算法 ［J］.計算機與應用化學，2014，31（10）：1201-1204.

［9］歐陽喆，周永權.自適應步長螢火蟲優(yōu)化算法［J］.計算機應用，2011，31（7）：1804-1807.

［10］呂聰穎.智能優(yōu)化方法的研究及其應用［M］.北京：中國水利水電出版社，2014.

［11］張萬里，宋啟祥.遺傳算法的 DV-Hop算法改進［J］.重慶大學學報，2015，38（3）：159-166.

The improved DV-Hop algorithm based on ASGSO algorithm

Zhao Xiaoqing，Mao Yongyi
（School of Electronic Engineering，Xi′an University of Posts and Telecommunications，Xi′an 710061，China）

Aiming at the coordinate′s low accuracy of unlocated node at the last step of DV-Hop algorithm in wireless sensor network，an improved DV-Hop algorithm （ASGSODV-Hop）based on self-adaptive step glowworm swarm optimization algorithm is adopted.Using ASGSO algorithm at the step of estimating the nodes coordinate of DV-Hop algorithm instead of the Least Square Method，the adaptive iteration optimization of ASGSO algorithm is adopted to construct a particular fitness function for the problem to be solved when using DV-Hop algorithm at the process of locating，and the optimization can be realized by multiple iteration which make the unlocated node more closed with the true value.The simulation result indicates that the average location error is about 23.58%.Compared with traditional DV-Hop algorithm，ASGSODV-Hop algorithm makes the location error reduced by 46.49%without adding communication cost and improves the location accuracy of the node.

wireless sensor network；DV-Hop algorithm；ASGSO algorithm；adaptive iteration；positional accuracy

TP393

A

1674-7720（2015）23-0058-04

趙曉青，毛永毅.基于ASGSO算法的改進DV-Hop算法［J］.微型機與應用，2015，34（23）：58-61.

2015-08-07）

趙曉青（1989-），女，碩士研究生，主要研究方向：衛(wèi)星導航與定位。

陜西省自然科學基金資助項目（2014JM2-6088）

毛永毅（1969-），男，博士，教授，主要研究方向：移動臺定位、無線傳感器網(wǎng)絡定位。