趙宏才+趙曉杰+王茂勵(lì)+孟慶龍

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

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

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

1 算法描述

1.1 DV?Hop算法

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

（1） 計(jì)算未知節(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)記錄自同一個(gè)錨節(jié)點(diǎn)發(fā)出的最小跳數(shù)，丟棄其余數(shù)據(jù)，并將跳數(shù)值加1后繼續(xù)廣播給鄰居節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

1.3 人工蜂群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)及性能分析

本文通過(guò)Matlab工具軟件對(duì)算法進(jìn)行仿真來(lái)驗(yà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í)驗(yàn)次數(shù)為并定義為未知節(jié)點(diǎn)的實(shí)際坐標(biāo)，為未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，定位節(jié)點(diǎn)的個(gè)數(shù)用表示。則基于次仿真結(jié)果統(tǒng)計(jì)的評(píng)價(jià)指標(biāo)定義為：

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

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

對(duì)算法進(jìn)行100次仿真，對(duì)比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)占比對(duì)定位誤差影響減小，表明錨節(jié)點(diǎn)數(shù)占比在一定區(qū)間內(nèi)有利于減小定位誤差，但是當(dāng)錨節(jié)點(diǎn)數(shù)占比超過(guò)定值之后，對(duì)定位誤差的影響就會(huì)保持穩(wěn)定。通過(guò)仿真可知，本文算法相比于傳統(tǒng)定位誤差平均減小24.44%，相對(duì)于ABDV?Hop算法的定位誤差平均減小17.22%。

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

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

從圖2中可以看出：三種定位算法的定位誤差隨著通信半徑的增大而減小，并且最終趨于穩(wěn)定；定位算法在通信半徑為40 m之后，通信半徑長(zhǎng)度對(duì)定位誤差的影響基本不變，所以不能一味地通過(guò)增加通信半徑來(lái)提高定位誤差；本文定位算法相對(duì)于傳統(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逐漸增加，對(duì)比三種算法歸一化平均定位誤差，結(jié)果如圖3所示。通過(guò)仿真結(jié)果可知，三種算法隨著節(jié)點(diǎn)總數(shù)的增加，定位誤差逐漸減小并且最終趨于穩(wěn)定；本文定位算法，在節(jié)點(diǎn)總數(shù)不同的條件下，平均定位誤差較傳統(tǒng)定位算法平均減小了13.71%，較人工蜂群定位算法降低了8.21%。

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[1] 孫利民，李建中，陳渝，等.無(wú)線傳感器網(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].電子測(cè)量與儀器學(xué)報(bào)，2013，27（5）：389?390.

[4] 金純，葉誠(chéng)，韓志斌，等.無(wú)線傳感器網(wǎng)絡(luò)中DV?Hop定位算法的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，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ì)算機(jī)科學(xué)，2013，40（1）：33?36.

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

[9] 張偉.面向精細(xì)農(nóng)業(yè)的無(wú)線傳感器網(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é)報(bào)，2014，9（2）：127?132.