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

　　關鍵詞： 無線傳感器網絡；DV-Hop算法；ASGSO算法；自適應迭代；定位精度

0 引言

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

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

1 DV-Hop算法

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

　　（1）獲取待定位節點和信標節點間的最小跳數

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

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

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

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

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

　　di=HopSizei×hi（2）

　　（3）待定位節點自身位置的估算

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

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

　　最后，由標準的最小二乘法即可得到節點M的坐標：

2 改進的DV-Hop算法

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

　　2.1 ASGSO算法

　　2.1.1 自適應步長調整策略

　　螢火蟲群優化（Glowworm Swarm Optimization，GSO）算法[10]是一種群智能算法，利用螢火蟲發光吸引同伴這一現象進行模擬，發光越強便可吸引越多的同伴，每個螢火蟲通過移向目標區域內最亮螢火蟲尋求最優解。

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

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

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

　　自適應步長調整辦法為：

　　si=smin+（smax-smin）Hi（8）

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

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

　　2.1.2 算法描述

　　ASGSO算法流程如下：

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

　　（2）熒光素更新。J（xi（t））為迭代位置xi（t）的目標函數。將螢火蟲在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）位置更新。根據更新位置。

　　（6）更替決策域。由rdi（t+1）=min{rs，max{0，rdi（t）+（ni-|Ni（t）|）}}更新動態決策域半徑。

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

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

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

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

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

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

3 仿真實驗

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

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

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

　　3.1 算法參數設置

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

　　3.2 算法仿真結果分析

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

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

　　（1）不同通信半徑

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

　　（2）不同節點數

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

　　（3）不同網絡連通度

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

4 結論

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

　　參考文獻

　　[1] 鄭軍，張寶賢.無線傳感器網絡技術[M].北京：機械工業出版社，2012.

　　[2] BULUSU N， HEIDEMANN J， ESTRIN D. GPS-less low cost outdoor localization for very smal devices[J]. IEEE Personal  Communications  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， BRIAN M 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] 歐陽喆，周永權.自適應步長螢火蟲優化算法[J].計算機應用，2011，31（7）：1804-1807.

　　[10] 呂聰穎.智能優化方法的研究及其應用[M].北京：中國水利水電出版社，2014.

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