融合跳數(shù)修正與動態(tài)布谷鳥搜索的改進 DV?Hop 算法

任克強，溫曉珍

（江西理工大學 信息工程學院，江西 贛州 341000）

0 引 言

無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN）部署的各種應用中，所有傳感器節(jié)點共同完成一個特定任務。這些傳感器節(jié)點通過感知周圍的環(huán)境現(xiàn)象，收集所需的環(huán)境信息送到監(jiān)測人員處進行適當?shù)奶幚韀1]。由于能獲取客觀的物理信息，WSN 在森林監(jiān)測、醫(yī)療及智能交通等諸多領(lǐng)域得到了廣泛的應用[2]。在WSN 應用中，傳感器感知到的環(huán)境數(shù)據(jù)需在事件發(fā)生位置已知的前提下才有實際意義[3]。因此，節(jié)點定位是WSN 應用中的一項關(guān)鍵技術(shù)，其定位精度直接關(guān)系到WSN 系統(tǒng)的整體性能。根據(jù)是否測量實際距離可將節(jié)點定位算法分為基于距離和距離無關(guān)兩種算法[4]。TOA、TDOA、AOA和RSSI 是主要的基于距離的定位算法[5?7]，測距階段易受環(huán)境因素的影響，并且需要增加額外的硬件開銷，在資源受限的應用中是不實用的。相比基于距離的算法，距離無關(guān)算法無需實際測量節(jié)點間距離，硬件開銷較小，主要分為質(zhì)心算法、APIT 和 DV?Hop 等[8?10]。

DV?Hop 定位算法是一種應用廣泛的距離無關(guān)的定位算法，具有復雜性低、可擴展性好等優(yōu)點[11]。在傳統(tǒng)的DV?Hop 算法中，跳數(shù)、跳距的處理誤差和未知節(jié)點坐標的計算誤差是導致定位不理想的主要原因。針對DV?Hop 算法定位精度不理想的問題，國內(nèi)外相關(guān)文獻給出了相應的解決策略，文獻[12]提出一種基于布谷鳥優(yōu)化的DV?Hop 算法，利用兩種優(yōu)化算法同時搜索，動態(tài)調(diào)整布谷鳥算法的概率參數(shù)，減小了距離誤差在定位階段的累加，有效提高了定位精度，但雙種群并行搜索增加了算法復雜度。文獻[13]提出一種基于誤差距離加權(quán)與跳段算法選擇的遺傳優(yōu)化DV?Hop 定位算法，利用最優(yōu)節(jié)點通信半徑對算法進行改進，并通過誤差分析優(yōu)化信標節(jié)點的分布，采用加權(quán)法求未知節(jié)點的位置，相對于傳統(tǒng)DV?Hop 算法，減小了定位誤差。文獻[14]在未知節(jié)點已知所有信標節(jié)點之間的距離時，利用布谷鳥搜索方法估計節(jié)點的位置，該方法將定位問題轉(zhuǎn)化為全局優(yōu)化問題，減小了跳數(shù)誤差積累。文獻[15]提出一種改進的DV?Hop 無線傳感器網(wǎng)絡定位算法，將接收信號強度指示RSSI 加入定位系統(tǒng)對原算法進行改進，對節(jié)點間跳數(shù)進行修正，但RSSI 測距易產(chǎn)生誤差，對定位精度的提高不夠明顯。文獻[16]基于加權(quán)二乘的DV?Hop 定位算法，通過利用信標節(jié)點的影響力大小不同，確定最小二乘法的權(quán)重值，再運用加權(quán)似然估計方法和三邊測量定位法，求得未知節(jié)點的位置坐標，定位精度有一定的提高。文獻[17]提出了改進的布谷鳥算法（MCS）和共軛梯度（CG）作為二次優(yōu)化技術(shù)，采用改進的布谷鳥算法進行權(quán)重選擇，該融合算法具有較高的收斂速度和較好的性能，但計算復雜度較高。

針對DV?Hop 算法因跳數(shù)誤差、平均每跳距離誤差與未知節(jié)點坐標計算誤差等因素導致的定位精度低的問題，本文采用了兩種優(yōu)化策略對定位算法進行改進。一是提出利用修正因子調(diào)整跳數(shù)，并引進虛擬交圓估計平均每跳距離，以減小由于不準確的跳數(shù)和平均每跳距離的偏移而導致的誤差積累；二是在DV?Hop 定位的第三階段，采用混合布谷鳥搜索方法進行優(yōu)化，首先定義適應度函數(shù)并計算適應度值，將適應度值分為三類并進行動態(tài)計算，得出三類細分的最優(yōu)搜索公式，協(xié)調(diào)以達到布谷鳥搜索的局部與全局最優(yōu)，提高定位的精度。

1 DV?Hop 算法及分析

1.1 DV?Hop 算法實現(xiàn)步驟

DV?Hop 定位算法的實現(xiàn)包括三個步驟，具體如下：

1）計算節(jié)點間的最小跳數(shù)

信標節(jié)點將自身位置信息的分組進行廣播，接收節(jié)點記錄到的每個信標節(jié)點的最小跳數(shù)，然后將跳數(shù)值加1 后轉(zhuǎn)發(fā)給鄰居節(jié)點，以近似同心圓的方式使網(wǎng)絡中所有節(jié)點能夠記錄到每個信標節(jié)點的最小跳數(shù)。

2）計算節(jié)點間的實際跳距

根據(jù)第一階段記錄的跳數(shù)信息，利用式（1）計算平均每跳的實際距離。

式中：(xi,yi)與 (xj,yj)為信標節(jié)點i,j的坐標；hij為信標節(jié)點間的最小跳數(shù)。

信標節(jié)點將計算的平均每跳距離進行廣播，未知節(jié)點接收后，根據(jù)記錄的跳數(shù)，計算到每個信標節(jié)點的跳轉(zhuǎn)距離。

3）計算未知節(jié)點坐標

根據(jù)記錄到的每個信標節(jié)點的跳轉(zhuǎn)距離，利用三邊測量法或極大似然估計法計算未知節(jié)點坐標。

1.2 DV?Hop 算法分析

分析DV?Hop 算法定位的三個階段可知，影響DV?Hop 算法定位精度的主要因素有三個：跳數(shù)誤差、平均每跳距離和節(jié)點位置計算方法。

1）跳數(shù)跳距誤差分析

在DV?Hop 算法中，在估計信標節(jié)點間的跳數(shù)時，通信區(qū)域內(nèi)所有鄰居節(jié)點都被記為一跳，而實際每一跳的長度是不一致的，在計算節(jié)點間的最小跳數(shù)階段，它們?nèi)员唤y(tǒng)一記為一跳，這種計數(shù)方法對跳數(shù)計數(shù)和平均每跳距離的估計都有較大的影響，易產(chǎn)生較大的誤差。

2）未知節(jié)點坐標計算方法誤差分析

在DV?Hop 算法中，通常采用三邊測量法或極大似然估計法進行節(jié)點定位計算，然而三邊測量法對測距誤差較為敏感，容易影響最終定位精度；在極大似然估計法中，矩陣的誤差偏移也會影響節(jié)點坐標的精度，增加算法的定位誤差。

2 布谷鳥算法分析

2.1 布谷鳥搜索算法原理

布谷鳥搜索（Cuckoo Search，CS）算法是一種仿生群體智能算法[18]，具有結(jié)構(gòu)簡單、參數(shù)少、易于實現(xiàn)等優(yōu)點，可有效平衡算法局部與全局搜索能力。通過分析布谷鳥的繁衍習性，部分布谷鳥不筑巢，它們將卵產(chǎn)于其他鳥窩，以寄生方式由其他鳥代為育雛，若這些鳥蛋被宿主發(fā)現(xiàn)，宿主便會丟棄它們或者重新筑巢。

實現(xiàn)CS 算法需滿足三個條件：

1）布谷鳥每次只產(chǎn)一個卵，且隨機選擇一個鳥巢放置；

2）在這組隨機選擇的鳥巢中，最好的那一個將被留至下一代；

3）可選擇的鳥巢數(shù)量是不變的，宿主發(fā)現(xiàn)外來鳥蛋的概率是Pa，其中0 ≤Pa≤ 1。

設(shè)表示第i個鳥巢在第t代的位置，L(λ)為隨機搜索路徑，則布谷鳥尋巢的位置更新公式為：

式中：α表示步長控制量，取α0=0.01；⊕表示點對點乘法；L(λ)表示 Lévy 飛行隨機搜索路徑，充分利用 Lévy飛行可有效避免局部極值的吸引。

Lévy 飛行隨機搜索路徑與時間t的關(guān)系服從概率密度函數(shù) Lévy 分布：

CS 算法通過式（3）對鳥巢位置進行更新，并且計算目標函數(shù)的適應度值，若該值優(yōu)于上一代目標函數(shù)值，則更新位置，否則不變。模擬布谷鳥鳥蛋被宿主發(fā)現(xiàn)并移開的思想機制，用隨機產(chǎn)生的服從0～1 分布的隨機數(shù)r與Pa比較，若r＞Pa，則對進行改變，反之不變，最后保留較好的一組鳥巢位置。判斷算法是否滿足最大迭代次數(shù)，若滿足，迭代結(jié)束，輸出全局最優(yōu)值；否則，繼續(xù)尋優(yōu)。

2.2 CS 算法存在的問題

目前，CS 算法面臨的一個主要問題是算法在后期求解函數(shù)問題時收斂速度偏慢、求解精度不高和易陷入局部最優(yōu)解。在求解實際問題時，對于具體的特定問題和問題的不同階段，對算法的全局探索和局部開發(fā)能力的要求也不同，因此，要求在收斂速度快的同時，平衡算法的全局與局部搜索能力，加強個體間信息的傳遞，能夠在前期快速確定全局最優(yōu)解的范圍，后期精準收斂到全局最優(yōu)解，擺脫局部最優(yōu)解的束縛，將是提高算法適應性的關(guān)鍵。

通過分析以上標準DV?Hop 算法定位誤差較大及CS 算法易陷入局部最優(yōu)的問題，本文利用修正因子和虛擬交圓對跳數(shù)、跳距進行修正，并引入動態(tài)搜索步長優(yōu)化CS 算法，提出一種跳數(shù)修正與自適應布谷鳥搜索的改進DV?Hop 定位算法。

3 本文算法

3.1 跳數(shù)跳距修正

3.1.1 跳數(shù)計數(shù)方式改進

在DV?Hop 算法中，跳數(shù)計數(shù)方式的不合理會引起較大的定位誤差。如圖1 所示，未知節(jié)點x，y都在信標節(jié)點A的通信半徑內(nèi)，在DV?Hop 算法進行定位過程中，未知節(jié)點x，y到A的距離都被記為一跳，而實際這兩個距離存在一定的誤差。

圖1 通信范圍內(nèi)單跳誤差

針對這一情況，本文引入理想跳數(shù)、節(jié)點偏差系數(shù)以及跳數(shù)差值修正系數(shù)，提出一種全局節(jié)點跳數(shù)修正的方法。對信標節(jié)點的跳數(shù)計數(shù)方式進行修正，當節(jié)點間的跳數(shù)hij＞2 時，利用理想跳數(shù)δij對信標節(jié)點間跳數(shù)hij進行修正，定義hij與通信半徑R的比值為理想跳數(shù)δij：

比較信標節(jié)點間跳數(shù)hij與理想跳數(shù)δij之間的誤差，定義εij為節(jié)點偏差系數(shù)：

εij越大，表明hij與δij之間的偏差越大。在通信半徑R不變的情況下，估算跳數(shù)將大于或等于理想跳數(shù)，定義跳數(shù)差值修正系數(shù)為σij，以優(yōu)化跳數(shù)信息，減少誤差的累積：

信標節(jié)點間跳數(shù)計數(shù)公式修正為：

3.1.2 平均每跳距離修正

若DV?Hop 算法記錄的未知節(jié)點的跳數(shù)值為1，則表明該節(jié)點位于信標節(jié)點的通信半徑R區(qū)域內(nèi)，在平均每跳距離估計時，這類節(jié)點的跳數(shù)被計算為1 個，而實際每跳距離卻有很大的不同，這將給定位帶來較大的誤差。本文提出一種虛擬分區(qū)法計算信標節(jié)點間距離，如圖2 所示。

圖2 虛擬分區(qū)法計算距離

信標節(jié)點的通信半徑是R，根據(jù)R3，2R3 將該信標節(jié)點的單跳通信區(qū)域劃分為3 個互不相交的子區(qū)域，通信半徑R中的節(jié)點以R3 為半徑構(gòu)造虛擬圓，m1,m2,m3,m4為通信半徑內(nèi)的未知節(jié)點，A為信標節(jié)點，以未知節(jié)點m1為例，m1的虛擬圓與3 個子區(qū)域的相交部分分別記為S11,S12,S13。假設(shè)節(jié)點到信標節(jié)點的距離已知，則可通過幾何方法計算出相交面積的大??；反之，當相交面積已知時，節(jié)點到信標節(jié)點的距離也可計算得出。

假設(shè)節(jié)點到信標節(jié)點的距離為di，通過幾何分析，各相交部分面積為：

假設(shè)n個節(jié)點不均勻分布，通信區(qū)域面積為S，3 個子區(qū)域內(nèi)的節(jié)點總數(shù)分別為ni1,ni2,ni3，則可得出每個相交區(qū)域的面積分別如下：

面積估計法可求出未知節(jié)點到信標節(jié)點間的距離，采用非線性方程di=f(Si)計算節(jié)點間距離。分析的節(jié)點均在通信半徑R內(nèi)，因此此方法計算出來的節(jié)點間距離即為修正的單跳距離。

3.2 動態(tài)分組自適應CS 算法

傳統(tǒng)的隨機游動機制的布谷鳥搜索算法對優(yōu)化性能有較大的影響，步長相對較大時，算法較容易地找到全局最優(yōu)值，但搜索精度難以達到要求；反之，當步長較小時，搜索精度相對提高，但全局搜索能力相應降低。因此，本文提出一種改進的自適應動態(tài)調(diào)整步長的改進CS 策略，根據(jù)個體與種群的適應度值，將種群劃分為3 個組，通過控制步長實現(xiàn)局部搜索與全局搜索的相對平衡。

設(shè)置種群數(shù)目為n，xk表示第k代個體，適應度值記為為平均適應度值，最好的適應度值記為fbest，當最優(yōu)適應度值優(yōu)于平均適應度值時，將最優(yōu)適應度值記為，根據(jù)適應度函數(shù)值將種群劃分為三種類型。

類型1：將適應度值優(yōu)于的劃分為第一組，其相應的步長控制調(diào)整方程為：

式中：αmin是預先設(shè)定的步長控制量的最小分量；αk,i表示第k次迭代的第i個個體對應的步長控制向量分量。

類型3：將適應度值低于的劃分為第三組，其相應第k次迭代的第i個個體對應的步長控制為：

式中：h1,h2,Δ為控制參數(shù)當個體分布越分散時，Δ值越大，當個體分布越集中時，Δ值相應減小。

本文提出的改進自適應動態(tài)調(diào)整步長的布谷鳥搜索策略的適應度函數(shù)取為：

式中：f(x,y)為適應度值；n為信標節(jié)點數(shù)目；di為未知節(jié)點到信標節(jié)點的距離。

3.3 本文算法描述

本文算法將DV?Hop 定位問題用混合布谷鳥搜索最優(yōu)距離的方法來解決：利用動態(tài)調(diào)整搜索步長策略將種群劃分為三個類型，當最佳精度達不到設(shè)定值時，依次更改控制步驟，每次迭代更新后，用新的解決方案替代舊的解決方案，最后保持最優(yōu)解。算法流程如下：

Step1：網(wǎng)絡初始化。初始區(qū)域為M×M，信標節(jié)點數(shù)量為N1，未知節(jié)點數(shù)量為N2，通信半徑為R。信標節(jié)點廣播自己的信息{ID，(x,y)，hop}，其他節(jié)點接收信標節(jié)點信息。

Step2：節(jié)點進行跳數(shù)計算，信標節(jié)點計算平均每跳距離Hopsizei和平均每跳校正誤差，利用面積估計法修正平均每跳距離Hopsizei。

Step3：生成適應度函數(shù)值f(x,y)并初始化CS種群。

Step4：計算目標函數(shù)值，并根據(jù)上述改進的CS 算法自動調(diào)整三類種群步長的控制。

Step5：更新適應度值，并保留較好的值。

Step6：判斷當前迭代次數(shù)t是否大于最大迭代次數(shù)Tmax，若t＜Tmax，繼續(xù)迭代；否則，輸出最優(yōu)值。

4 仿真結(jié)果與分析

為測試本文定位算法的性能，采用Matlab R2016b仿真平臺對本文定位算法的性能進行測試，從通信半徑、信標節(jié)點密度、節(jié)點總數(shù)三個方面對DV?Hop 算法、文獻[12]的CS?D 算法和本文算法的性能進行仿真實驗對比。采用歸一化平均定位誤差作為算法的評價標準：

式中：xi為節(jié)點的實際位置；n為測試區(qū)域節(jié)點總數(shù)為算法對未知節(jié)點的估計位置；R是通信半徑。

圖3 為在信標節(jié)點密度為20%時，不同通信半徑下DV?Hop 算法、文獻[12]的 CS?D 算法和本文算法的歸一化平均定位誤差比較情況，其中，總節(jié)點數(shù)目為100。

圖3 不同通信半徑的平均定位誤差

由圖3 可以看出，通信半徑由15 m 增至40 m 的過程中，三種算法的平均定位誤差均呈下降趨勢，表明節(jié)點通信半徑越大，定位的精度越高。其中，DV?Hop 算法的整體平均定位誤差最大，文獻[12]的CS?D 算法次之，本文算法的平均定位誤差最低。在通信半徑增加至40 m時，實驗得出 DV?Hop 與 CS?D 兩種算法的平均定位誤差為34%和27.2%，而本文算法低至19.3%，在相同通信半徑下，本文算法誤差低于 DV?Hop 算法與 CS?D 算法，定位性能更佳。

圖4 為節(jié)點總數(shù)M=100，通信半徑R=25 m 時DV?Hop 算法、文獻[12]的 CS?D 算法和本文算法在不同的信標節(jié)點密度下的性能表現(xiàn)。由圖4 可以看出，信標節(jié)點數(shù)目越多，三種算法的平均定位誤差越低，表明信標節(jié)點越密集，定位信息越全面、定位精度越高。其中，當控制仿真區(qū)域內(nèi)信標節(jié)點密度為10%時，三種算法的平均定位誤差都有明顯降低，在節(jié)點密度高于15%后，三種算法的定位性能趨于穩(wěn)定，在信標節(jié)點密度不變的情況下，DV?Hop 算法的平均定位誤差雖有下降趨勢，但誤差值整體較高，效果最差；CS?D 算法次之，本文算法的定位誤差明顯低于其他兩種算法，定位精度最高，表現(xiàn)的性能最好。

圖4 不同信標節(jié)點密度的平均定位誤差

圖5 為通信半徑R=25 m，信標節(jié)點密度為10%時，DV?Hop 算法、CS?D 算法以及本文算法的平均定位誤差比較情況。

圖5 不同節(jié)點總數(shù)的平均定位誤差

由圖 5 可以看出，DV?Hop 算法、文獻[12]的 CS?D 算法和本文算法的平均定位誤差均隨著節(jié)點總數(shù)的增加而降低，其中，本文算法的誤差下降趨勢最明顯，在節(jié)點總數(shù)高于200 后，本文算法的優(yōu)越性更突出，在節(jié)點總數(shù)不變時，相比較 DV?Hop 算法和 CS?D 算法，本文算法的平均定位誤差更低，定位性能最好。

5 結(jié) 論

本文提出一種融合跳數(shù)修正與自適應布谷鳥搜索優(yōu)化的改進DV?Hop 定位算法，利用修正因子修正跳數(shù)誤差，對單跳區(qū)域的子區(qū)域進行劃分以修正跳距，并通過自適應動態(tài)調(diào)整步長的布谷鳥搜索測距對定位進行優(yōu)化。為了測試驗證本文改進策略的成效，在不同條件下對算法進行仿真測試比較。仿真結(jié)果顯示，在硬件條件不變的情況下，本文定位算法的表現(xiàn)優(yōu)于DV?Hop 算法和文獻[12]的CS?D 算法，具有更高的節(jié)點定位精度。如何進一步提升算法的性能，是后期要重點研究的方向。