基于差分進(jìn)化和人工蜂群混合策略的DV—Hop改進(jìn)算法

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

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

關(guān)鍵詞： DV?Hop算法； 人工蜂群； 差分進(jìn)化； 定位

中圖分類號： TN911?34； TP393 文獻(xiàn)標(biāo)識碼： 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 引 言

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

1 算法描述

1.1 DV?Hop算法

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

（1） 計算未知節(jié)點(diǎn)的最小跳數(shù)。錨節(jié)點(diǎn)不斷向通信區(qū)域內(nèi)鄰居節(jié)點(diǎn)廣播包含跳數(shù)（定義初始值為0）、錨節(jié)點(diǎn)標(biāo)志以及坐標(biāo)等的相關(guān)信息。未知節(jié)點(diǎn)記錄自同一個錨節(jié)點(diǎn)發(fā)出的最小跳數(shù)，丟棄其余數(shù)據(jù)，并將跳數(shù)值加1后繼續(xù)廣播給鄰居節(jié)點(diǎn)。

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

式中：是錨節(jié)點(diǎn)的坐標(biāo)；是錨節(jié)點(diǎn)之間的跳數(shù)。

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

（3） 計算未知節(jié)點(diǎn)的坐標(biāo)。未知節(jié)點(diǎn)將計算后的與錨節(jié)點(diǎn)之間的距離信息通過極大似然估計法或三邊測量法來獲取未知節(jié)點(diǎn)的坐標(biāo)信息，最終實現(xiàn)節(jié)點(diǎn)定位。

1.2 差分進(jìn)化算法

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

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

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

1.3 人工蜂群算法

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

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

式中是第個目標(biāo)函數(shù)。

根據(jù)貪婪機(jī)制選擇收益度較大的個體作為新的蜂群，依次循環(huán)，循環(huán)次數(shù)達(dá)到limit限定參數(shù)后，這個解依然沒有得到優(yōu)化，則這個解陷入局部最優(yōu)，這些采蜜蜂則轉(zhuǎn)變?yōu)閭刹榉洹?/p>

2 改進(jìn)的DV?Hop算法

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

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

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

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

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

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

（1） 計算未知節(jié)點(diǎn)最小跳數(shù)。

（2） 設(shè)置規(guī)模閾值以及DE算法和ABC算法的初始相關(guān)參數(shù)，隨機(jī)生成個解構(gòu)成初始蜜源的位置。

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

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

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

（6） 經(jīng)過次循環(huán)后，最優(yōu)適應(yīng)值下降量小于閾值時，隨機(jī)選擇一個個體，按照式（9）和式（10）產(chǎn)生兩個新的解，并評價他們的適應(yīng)度值，用貪婪選擇機(jī)制進(jìn)行更新。

（7） 對未知節(jié)點(diǎn)進(jìn)行差分變異、交叉和選擇操作，更新未知節(jié)點(diǎn)的位置，并記錄下當(dāng)前的最優(yōu)位置及適應(yīng)值，判斷是否都滿足終止條件，若滿足條件則輸出最優(yōu)解，否則跳轉(zhuǎn)到步驟（5）。

3 仿真實驗及性能分析

本文通過Matlab工具軟件對算法進(jìn)行仿真來驗證改進(jìn)算法的性能，設(shè)定錨節(jié)點(diǎn)和未知節(jié)點(diǎn)隨機(jī)分布在200 m2的正方形區(qū)域內(nèi)；錨節(jié)點(diǎn)的坐標(biāo)已經(jīng)確定；節(jié)點(diǎn)通信半徑設(shè)定為25 m。設(shè)置種群數(shù)量循環(huán)實驗次數(shù)為并定義為未知節(jié)點(diǎn)的實際坐標(biāo)，為未知節(jié)點(diǎn)的估計坐標(biāo)，定位節(jié)點(diǎn)的個數(shù)用表示。則基于次仿真結(jié)果統(tǒng)計的評價指標(biāo)定義為：

式中：error為定位誤差，在仿真實驗中作為定位精度的評價指標(biāo)；為定位的節(jié)點(diǎn)個數(shù)；為節(jié)點(diǎn)的通信半徑。

3.1 不同錨節(jié)點(diǎn)數(shù)條件下定位結(jié)果比較

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

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

在仿真區(qū)域隨機(jī)分布200個節(jié)點(diǎn)，錨節(jié)點(diǎn)數(shù)為30個，對三種算法在通信半徑為30～70 m的區(qū)間內(nèi)對歸一化的平均定位誤差進(jìn)行對比，實驗結(jié)果如圖2所示。

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

3.3 不同節(jié)點(diǎn)總數(shù)條件下定位結(jié)果比較

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

4 結(jié) 語

本文針對ABDV?Hop算法在定位過程中容易出現(xiàn)局部最優(yōu)、收斂速度慢和定位精度低的問題，引進(jìn)差分進(jìn)化算法，在未知節(jié)點(diǎn)坐標(biāo)的計算過程中將兩種算法融合，進(jìn)行了優(yōu)化求解，在原有資源的前提下提高定位精度和穩(wěn)定性。仿真結(jié)果表明，本文提出的HDV?Hop算法在解決傳感器網(wǎng)絡(luò)定位上提供了一種高精度、易實現(xiàn)的定位方案。

參考文獻(xiàn)

[1] 孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，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] 周玲，康志偉，何怡剛.基于三角不等式的加權(quán)雙曲線定位DV?HOP算法[J].電子測量與儀器學(xué)報，2013，27（5）：389?390.

[4] 金純，葉誠，韓志斌，等.無線傳感器網(wǎng)絡(luò)中DV?Hop定位算法的改進(jìn)[J].計算機(jī)工程與設(shè)計，2013，34（2）：401?402.

[5] 胡鵬莎.WSN中DV?Hop節(jié)點(diǎn)定位算法的改進(jìn)研究[D].南京：南京林業(yè)大學(xué)，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ìn)[J].計算機(jī)科學(xué)，2013，40（1）：33?36.

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

[9] 張偉.面向精細(xì)農(nóng)業(yè)的無線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)研究[D].杭州：浙江大學(xué)，2013：48?49.

[10] 劉波，王凌，金以慧.差分進(jìn)化算法研究進(jìn)展[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].智能系統(tǒng)學(xué)報，2014，9（2）：127?132.