趙宏才+趙曉杰+王茂勵+孟慶龍

摘 要： 為了解決無線傳感器網絡依靠DV?Hop算法定位過程中存在誤差偏高的問題，將人工蜂群算法和差分進化算法融合，引入傳統DV?Hop算法中，提出一種HDV?Hop算法。該算法在繼承經典DV?Hop算法的前提下，獲取錨節點的信息及平均跳距距離，在未知節點定位階段引入混合策略的目標函數，優化搜索算法，提高定位精度，完成對未知節點的定位。仿真分析表明，該算法相比于DV?Hop算法和基于人工蜂群的定位算法能有效降低定位誤差，提高穩定性。

關鍵詞： DV?Hop算法； 人工蜂群； 差分進化； 定位

中圖分類號： TN911?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2017）15?0129?04

Abstract： In order to solve the big error of the wireless sensor network （WSN） relying on DV?Hop algorithm in position process， the artificial bee colony algorithm and differential evolution algorithm are fused， and introduced into the traditional DV?Hop algorithm to propose a HDV?Hop algorithm. Under the premise of inheriting the classic DV?Hop algorithm， the objective function of the mixed strategy is introduced into the positioning stage of unknown node after getting the anchor node information and average hop distance， the search algorithm is optimized， and the positioning accuracy is improved to locate the unknown nodes. The simulation analysis results show that， in comparison with the DV?Hop algorithm and positioning algorithm based on artificial bee colony， the proposed algorithm can reduce the positioning error effectively， and improve the stability.

Keywords： DV?Hop algorithm； artificial bee colony； differential evolution； positioning

0 引 言

智能控制技術的發展極大地帶動了智能傳感器的發展，由大量傳感器節點自組而形成的無線傳感器網絡（WSNs）成為控制領域的研究熱點。無線傳感器網絡節點的位置信息對傳感器網絡的監測活動至關重要，沒有位置信息的監測是毫無意義的[1]。DV?Hop算法依靠其不用測距的特點成為無線網絡定位技術中重點關注的算法，但其定位精度較低，無法滿足高精度需求的場所，提高精度是該算法亟需解決的問題[2]。近年來，大量專家和學者已經針對這一問題提出了一系列提高精度的改進方法[3?7]。本文在文獻[7]研究的基礎上，在算法的節點定位階段，采用將差分進化算法（DE算法）和人工蜂群算法（ABC算法）融合的混合人工蜂群算法（HABC）[8]來優化目標函數，進行定位信息計算，從而提高DV?Hop算法的定位精度。

1 算法描述

1.1 DV?Hop算法

DV?Hop定位算法的定位過程分為以下三個階段[2，9]：

（1） 計算未知節點的最小跳數。錨節點不斷向通信區域內鄰居節點廣播包含跳數（定義初始值為0）、錨節點標志以及坐標等的相關信息。未知節點記錄自同一個錨節點發出的最小跳數，丟棄其余數據，并將跳數值加1后繼續廣播給鄰居節點。

（2） 錨節點與未知節點的實際每跳跳距。錨節點利用步驟（1）中接收到的跳數與位置信息，通過式（1）計算自己的平均每跳距離：

式中：是錨節點的坐標；是錨節點之間的跳數。

平均每跳的距離被錨節點通過可控洪泛法廣播到網絡中，每個節點記錄下來自錨節點的第一個平均跳距并在丟掉之后接收到的跳距信息。未知節點根據接收到的信息，利用式（2）計算與錨節點之間的距離：

（3） 計算未知節點的坐標。未知節點將計算后的與錨節點之間的距離信息通過極大似然估計法或三邊測量法來獲取未知節點的坐標信息，最終實現節點定位。

1.2 差分進化算法

差分進化算法（DE算法）是一種高效的隨機并行搜索算法，能有效解決復雜的優化難題。算法尋優求解的思想概括為：對當前種群進行變異和交叉運算，衍生出一個新的種群；進而利用貪婪策略從兩個種群中選優并保留至下一代，形成新一代種群。差分改進算法始終保持種群的規模不變，算法過程如下[8，10]：

在問題的可行解空間對種群進行初始化為種群規模，個體表征問題解，為解空間的維數。然后對當前種群通過式（3）和式（4）進行變異和交叉操作，生產新種群。然后進行選擇操作，將優于父個體的子代個體保留，否則，父個體保留至下一代。變異和交叉運算公式如下：

式中：為個體生成的變異個體；為種群中互不相同的3個個體；是縮放比例因子，用來決定差向量的影響比重；為之間的隨機數；為雜交參數。

1.3 人工蜂群算法

文獻[11]提出人工蜂群算法（ABC算法），其能夠有效地解決群體智能優化的問題。該算法尋求最優解的過程概括為：采蜜蜂依據其存儲的蜜源信息在蜜源的一定范圍內發現一個新的蜜源，然后將蜜源位置發送給跟隨蜂，跟隨蜂通過貪婪策略確定一個蜜源，并依據當前蜜源信息在其鄰域內搜尋新的蜜源，依次循環，最終尋得最優解[12]。

ABC算法中跟隨蜂通過觀察采蜜蜂傳遞的信息來判斷蜜源的收益率，并確定蜜源。收益率通過適應度值來表示，選擇概率如下：

式中是第個目標函數。

根據貪婪機制選擇收益度較大的個體作為新的蜂群，依次循環，循環次數達到limit限定參數后，這個解依然沒有得到優化，則這個解陷入局部最優，這些采蜜蜂則轉變為偵查蜂。

2 改進的DV?Hop算法

基于人工蜂群的定位算法主要存在以下問題：

（1） 人工蜂群算法尋優過程中容易出現“早熟”的收斂性缺陷，從而陷入局部最優，進而影響算法的性能；

（2） 局部搜索能力差，收斂速度比較慢。

針對人工蜂群算法的不足，本文將人工蜂群算法和差分進化算法融合，以期提高人工蜂群算法的搜索精度和收斂速度，從而提高DV?Hop算法的定位精度。

由式（1）可知，未知節點與錨節點距離滿足公式考慮到實際測量及外部因素的影響，與實際距離存在一定的誤差，將影響定位的準確性。令為實際誤差，則。將的計算融入到人工蜂群算法的適應度值的計算中，以期將誤差降為最小，從而提高定位精度。定義適應度函數如下：

算法的基本思路是：首先利用DV?Hop算法計算出未知節點與錨節點之間的最小跳數和每跳距離。利用人工蜂群算法優化出一個新的搜索策略，并擴大個體的搜索區間，從而提高搜索能力；然后，通過淘汰規則來提高算法的收斂能力，滿足規則后，依次抽取一個個體，與最優個體的變異或算術雜交來更新自己，以加快適應度向最優更新；最后，對未知節點進行差分操作，優化處理后完成定位。改進的定位算法基本步驟如下：

（1） 計算未知節點最小跳數。

（2） 設置規模閾值以及DE算法和ABC算法的初始相關參數，隨機生成個解構成初始蜜源的位置。

（3） 按照人工蜂群搜索策略式（8）搜索一個新解，并計算其適應度，如果新解優于原先的解，則用新解替換原先的解。

（4） 偵查蜂根據蜜源的花蜜含量，依概率大小選擇一個蜜源位置，并根據式（8）產生一個新位置，評價該位置，如果新解優于偵查蜂所選的解，則用新蜜源替換所選蜜源。

（5） 判斷是否需要放棄該解。若存在放棄的解，則跳轉到步驟（3），用新解替換原來的解。

（6） 經過次循環后，最優適應值下降量小于閾值時，隨機選擇一個個體，按照式（9）和式（10）產生兩個新的解，并評價他們的適應度值，用貪婪選擇機制進行更新。

（7） 對未知節點進行差分變異、交叉和選擇操作，更新未知節點的位置，并記錄下當前的最優位置及適應值，判斷是否都滿足終止條件，若滿足條件則輸出最優解，否則跳轉到步驟（5）。

3 仿真實驗及性能分析

本文通過Matlab工具軟件對算法進行仿真來驗證改進算法的性能，設定錨節點和未知節點隨機分布在200 m2的正方形區域內；錨節點的坐標已經確定；節點通信半徑設定為25 m。設置種群數量循環實驗次數為并定義為未知節點的實際坐標，為未知節點的估計坐標，定位節點的個數用表示。則基于次仿真結果統計的評價指標定義為：

式中：error為定位誤差，在仿真實驗中作為定位精度的評價指標；為定位的節點個數；為節點的通信半徑。

3.1 不同錨節點數條件下定位結果比較

對算法進行100次仿真，對比DV?Hop算法、基于ABC算法的DV?Hop算法（ABDV?Hop算法）以及本文基于差分進化和人工蜂群融合的改進DV?Hop算法（HDV?Hop算法），由圖1可以看出，這三種算法的平均定位誤差均隨著錨節點占總數的比例增大而減小，而且在占比達到35%之后，錨節點占比對定位誤差影響減小，表明錨節點數占比在一定區間內有利于減小定位誤差，但是當錨節點數占比超過定值之后，對定位誤差的影響就會保持穩定。通過仿真可知，本文算法相比于傳統定位誤差平均減小24.44%，相對于ABDV?Hop算法的定位誤差平均減小17.22%。

3.2 不同通信半徑條件下定位結果比較

在仿真區域隨機分布200個節點，錨節點數為30個，對三種算法在通信半徑為30～70 m的區間內對歸一化的平均定位誤差進行對比，實驗結果如圖2所示。

從圖2中可以看出：三種定位算法的定位誤差隨著通信半徑的增大而減小，并且最終趨于穩定；定位算法在通信半徑為40 m之后，通信半徑長度對定位誤差的影響基本不變，所以不能一味地通過增加通信半徑來提高定位誤差；本文定位算法相對于傳統定位算法和人工蜂群定位算法，定位誤差平均減小了10.33%和1.22%。

3.3 不同節點總數條件下定位結果比較

設定通信半徑為20 m，初始錨節點總數為20且始終占總節點數的10%，在仿真區域內，節點總數從100～400逐漸增加，對比三種算法歸一化平均定位誤差，結果如圖3所示。通過仿真結果可知，三種算法隨著節點總數的增加，定位誤差逐漸減小并且最終趨于穩定；本文定位算法，在節點總數不同的條件下，平均定位誤差較傳統定位算法平均減小了13.71%，較人工蜂群定位算法降低了8.21%。

4 結 語

本文針對ABDV?Hop算法在定位過程中容易出現局部最優、收斂速度慢和定位精度低的問題，引進差分進化算法，在未知節點坐標的計算過程中將兩種算法融合，進行了優化求解，在原有資源的前提下提高定位精度和穩定性。仿真結果表明，本文提出的HDV?Hop算法在解決傳感器網絡定位上提供了一種高精度、易實現的定位方案。

參考文獻

[1] 孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京：清華大學出版社，2005：146?168.

[2] NICOLESCU D， NATH B. Ad Hoc positioning system （APS） [C]// Proceedings of the 2001 IEEE Global Telecommunications Conference. [S.l.]： IEEE， 2001： 1?11.

[3] 周玲，康志偉，何怡剛.基于三角不等式的加權雙曲線定位DV?HOP算法[J].電子測量與儀器學報，2013，27（5）：389?390.

[4] 金純，葉誠，韓志斌，等.無線傳感器網絡中DV?Hop定位算法的改進[J].計算機工程與設計，2013，34（2）：401?402.

[5] 胡鵬莎.WSN中DV?Hop節點定位算法的改進研究[D].南京：南京林業大學，2013.

[6] HU Yu， LI Xuemei. An improvement of DV?Hop localization algorithm for wireless sensor networks [J]. Telecommunication systems， 2013， 53（1）： 13?18.

[7] 李牧東，熊偉，郭龍.基于人工蜂群算法的DV?Hop定位改進[J].計算機科學，2013，40（1）：33?36.

[8] 高衛峰，劉三陽，姜飛，等.混合人工蜂群算法[J].系統工程與電子技術，2011，33（5）：1167?1170.

[9] 張偉.面向精細農業的無線傳感器網絡關鍵技術研究[D].杭州：浙江大學，2013：48?49.

[10] 劉波，王凌，金以慧.差分進化算法研究進展[J].控制與決策，2007，22（7）：721?722.

[11] KARABOGA D. An idea based on honey bee swarm for numerical optimization [R]. Erciyes： Erciyes University， 2005.

[12] 秦全德，程適，李麗，等.人工蜂群算法研究綜述[J].智能系統學報，2014，9（2）：127?132.