基于改進布谷鳥搜索算法的DV-Hop定位算法研究?

楊曉琴

（太原廣播電視大學 太原 030002）

1 引言

隨著科技發展，以傳感器和智能識別終端為代表的信息自動生成設備可以實時地對物理世界感知、測量和監控。微電子技術、計算機技術和無線通信技術的發展推動了低功耗、多功能傳感器的快速發展，現已研制出了具有感知能力、計算能力和通信能力的微型傳感器。物理世界的聯網需求和信息世界的擴展需求催生出一類新型網絡——無線傳感器網絡（Wireless Sensor Network，WSN）。

無線傳感器網絡已經在許多領域得到了應用，比如商業、軍事、醫療等［1］。無線傳感器網絡由大量部署在作用區域內的、具有無線通信與計算能力的傳感器節點組成。無線傳感器網絡所研究的熱門話題就是如何精確地對傳感器節點進行定位。目前無線傳感器網絡的定位算法主要是分兩類。第一類是基于測距的定位算法［2～3］，該種算法對硬件裝置有一定的局限性，費用很高；第二類是無需測距的定位算法［4～5］，該種算法對硬件要求并不高，并且費用也不高。所以無需測距的定位算法具有很強的研究價值。

DV-Hop 定位算法［4～5］是一個典型的無需測距的定位算法。但是它的定位精度比較低，為了能夠改善定位精度，許多解決優化問題的方法相繼提出。智能優化算法就是解決優化問題的一個主要方法。群體智能和仿生計算在許多文獻里被提及，已經引起了很多的關注。在優化的領域，計算智能，計算機科學，仿生算法，尤其是基于群體智能的算法已經非常普遍了。這些基于自然的元啟發式算法被廣泛應用于優化和計算智能算法。相對于傳統的算法，基于群體智能的算法目前已經產生了許多優化算法，并且都已經得到了廣泛的應用。比如，粒子群算法［6］、蟻群算法［7］、人工蜂群算法［8］等。

2009年，Yang等提出了布谷鳥搜索算法（Cuckoo Search，CS）［9］。該算法的靈感來自布谷鳥巢的寄生行為和Levy飛行的啟示。布谷鳥算法簡單、容易實現，在一些優化問題上明顯優于其他啟發式算法。目前，已經將CS算法應用到許多領域［10～14］，部分學者也已經把布谷鳥搜索算法應用到DV-Hop中獲得了不錯的效果［15～16］。文獻［15］將標準的CS算法應用到DV-Hop中，文獻［16］則是對標準的CS算法中的參數進行自適應調整，然后應用到DV-Hop中。

本文提出一種改進的布谷鳥搜索算法，該算法可以有效提高算法的搜索精度，接下來將該改進算法應用于DV-Hop算法。通過仿真實驗說明本文所提出的方法明顯改善了DV-Hop算法的定位精度，并且計算的開銷也很小。

2 DV-Hop定位算法

DV-Hop算法是一個很典型的無需測距的定位算法。在該算法中，信標節點和未知節點的距離是由跳數及平均跳數距離來表達的。節點之間的實際距離則是由跳數距離來替代，以便計算未知節點的位置坐標。

標準的DV-Hop算法主要由三步組成。首先，對網絡中節點間的最小跳數進行計算。所有的信標節點都會傳播信標信息，也就是信標節點的坐標和初始值為0的跳數信息。之后上述信息在網絡中傳播使用的是泛洪的方式。當信標節點發送一次信息到網絡中的其它節點，跳數就會加一。接收的信標節點發送的信標信息的節點則會保存這些信息的最小跳數值。

然后，信標節點和未知節點之間的距離將會被估計。為了將跳數信息轉換成物理距離，則會估計平均跳數距離。當一個信標節點得到了其它信標節點的坐標和跳數，則會計算平均跳數距離，然后它將會傳播到整個網絡進行糾正。平均跳數距離則由下式得出：

其中，(xi，yi)和 (xj，yj)分別是信標節點 i和 j的坐標，hj是信標節點i和 j之間的跳數。

最后，則是估計未知節點的坐標。當未知節點得到三個或更多信標節點距離信息以后，一般則會通過三邊測量法等方法計算它們的位置。

假設 (x，y)是未知節點的坐標，(xn，yn)是第n個信標節點的坐標，dn是未知節點與第n個信標節點的距離。那么就可以得到：

式（2）可以進一步由線性等式AX=b表示，其中：

3 基于改進的布谷鳥搜索算法的DV-Hop算法

3.1 布谷鳥搜索算法

2009年，英國劍橋大學學者Xin-She Yang提出了一種新的啟發式優化算法——布谷鳥搜索算法（CS）［9］。該算法模擬了布谷鳥尋找鳥窩的行為，并引入了鳥類的Levy飛行行為模式。CS算法使用鳥窩位置代表解。假設每個鳥窩只有一個蛋，每一個蛋代表一個解。這樣可以用更好的解來代替不好的解?？梢酝ㄟ^三個理想化條件來對CS做一個簡單概括：

1）每只布谷鳥一次只產一個蛋，并會隨機選擇一個鳥窩來放置它產下的蛋；

2）通過隨機選擇的方式尋找到的一組鳥窩中，將最好的一個鳥窩（解）保留到下一代；

3）鳥窩數量n固定不變，另外鳥窩主人能夠發現鳥窩中鳥蛋是外來的概率是Pa，其中Pα∈[0，1]。如果鳥蛋被鳥窩主人發現，鳥窩主人可以把該鳥蛋丟棄，也可以直接拋棄這個鳥窩，在其它地方建一個新的鳥窩。

上述三個理想化條件表明每一個鳥巢只包含一個鳥蛋，并不會發生一個鳥巢有很多鳥蛋的情況。每一代只會保留最好的鳥巢位置，然后通過隨機更新的方式更新其它的鳥巢位置，如果更新后的新位置優于舊位置，就保留新位置，舍棄舊位置。此外，還設定了一個宿主鳥發現鳥蛋的概率Pa，也就是說，如果宿主鳥發現某個鳥巢中的鳥蛋的概率大于Pa，就說明宿主鳥發現這個鳥巢中的鳥蛋不是自己所產鳥蛋的概率很大，然后就會扔掉自己鳥巢中的鳥蛋或者放棄鳥巢并建立一個新的鳥巢。

布谷鳥搜索算法的主要核心是兩個位置更新公式，其中一個進行的是局部搜索，另一個進行的是全局搜索。

全局搜索位置更新公式為

其中μ和ν服從標準正態分布，β=1.5。

通過Levy飛行進行完全局搜索之后，還會有一部分解再次進行一次局部搜索更新位置。最后比較保留好的一組解。隨機搜索的位置更新公式是

3.2 改進的布谷鳥搜索算法

因此，為了改善算法的局部搜索能力，本文對局部搜索公式進行修改，布谷鳥個體在搜索時向全局最優位置搜索，如下式所示：

如果讓個體用式（10）進行局部搜索，較差個體會始終朝最優位置飛行，局部搜索能力會有所加強；較優個體則會一直朝著歷史最優的個體方向搜索，使得較優個體一直在歷史最優個體附近搜索，從而陷入局部最優，而周圍可能會有比這個最優個體更好的個體。因此為了算法陷入局部最優，我們在此基礎上做了進一步改進。

將所有個體從優到差進行排序，排序后分為兩個種群。前一部分較優個體按照式（9）進行局部搜索，因為這些個體當前位置相對較優，所以進行局部搜索時可以不受歷史最優位置的限制進行局部搜索，這樣可能會尋找到優于當前歷史最優位置的位置。后一部分較差個體按照式（10）進行局部搜索，因為這些個體當前位置相對較差，所以考慮在進行局部搜索時提供歷史最優位置的信息。根據以上搜索方式，整體布谷鳥種群的局部搜索能力有效增強，而且還會避免較優個體陷入局部最優的問題。通過大量的實驗分析，當較優個體的數量與較差個體的比例為1∶9時，性能最佳。

3.3 基于改進布谷鳥搜索算法的DV-Hop算法

本文前面已經提到，DV-Hop算法的第三步一般是通過三邊測量法等方法計算未知節點的坐標。這些方法在計算每一步時都會不可避免地產生誤差，計算累積的誤差必然會使定位精度降低。本文則采用改進的布谷鳥搜索算法來計算未知節點的坐標，從而有效改善定位精度。

式（2）中的dn為估計距離，它和實際距離肯定有一定的誤差εn，所以式（2）則轉變為

當ε的值越小，未知節點(x，y)的坐標就越優。未知節點定位問題的實質則是一個優化問題，如下：

那么改進的CS算法的目標函數可表示為

4 仿真實驗

其中N是未知節點的個數，R是傳感器通信半徑(x，y)是未知節點估計的位置，(xi，yi)是真實位置。本文將從不同的角度分析本文所提方法的性能。

1）通信半徑與平均定位誤差的關系

如果節點的數量為100，信標節點的數量為20，算法的種群大小為10，迭代次數為50，通信半徑從15～40變化時的平均定位誤差如圖1所示。從圖1可以看出三種方法隨著通信半徑的增加，平均定位誤差都會減小，基于改進的布谷鳥搜索算法的DV-Hop定位算法（MCS-DVHop）具有最好的性能。當通信半徑是20m的時候，基于改進的布谷鳥搜索算法的DV-Hop定位算法依然能保持較低的平均誤差，而傳統的DV-Hop定位算法需要通信半徑為30m時，才能達到同樣的效果。

本文的實驗是在Matlab2016a上進行仿真實驗，將傳感器隨機分布在100*100m2的矩形區域內。在這個區域內，初步設定有20個信標節點，80個未知節點。為了評價本文所提方法的性能，本文將平均定位誤差作為評價標準。平均定位誤差的公式為

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

2）信標節點數量與平均定位誤差的關系

如果節點的數量為100，通信半徑為25m，算法的種群大小為10，迭代次數為50，信標節點的數量從5～30時的平均定位誤差如圖2所示。從圖2可以看出信標節點數量的增加會降低平均定位誤差，而MCS-DVHop表現出最好的性能。當信標節點數量是15的時候，基于改進的布谷鳥搜索算法的DV-Hop定位算法依然能保持較低的平均誤差，而傳統的DV-Hop定位算法大約需要25個信標節點，才能達到同樣的效果。

圖2 不同信標節點數量的平均定位誤差

3）節點數量與平均定位誤差的關系

如果信標節點的數量為20，通信半徑為25m，算法的種群大小為10，迭代次數為50，節點的數量從50～100時的平均定位誤差如圖3所示。從圖3可以看出節點數量的變化對標準的DV-Hop算法有很大的影響，對CS-DVHop和MCS-DVHop的影響并不大，且一直比較低也很穩定。特別是MCS-DVHop表現出最好的性能。

圖3 不同節點數量的平均定位誤差

4）迭代次數與平均定位誤差的關系

如果節點的數量為100，信標節點的數量為20，通信半徑為25m，算法的種群大小為10，迭代次數從10～80時的平均定位誤差如圖4所示。從圖4可以看出當迭代次數小于30時，兩種算法的平均定位誤差都比較高；當迭代次數大于30時，兩個算法的平均定位誤差趨于穩定。特別是MCS-DVHop在30代時就已經可以達到很好的效果，而CS-DVHop需要40代以后才能基本穩定下來。另外迭代次數的增加也會使算法的復雜度增加，并且時間也會增加。所以MCS-DVHop不管是在定位的穩定性上，還是在計算復雜度上都要優于CS-DVHop。

圖4 不同迭代次數下的平均定位誤差

5 結語

本文針對DV-Hop算法定位精度低的問題，提出了一種基于改進布谷鳥搜索算法的DV-Hop定位算法?？紤]到標準的布谷鳥搜索算法容易陷入局部最優，為了避免較優個體在局部搜索時陷入局部最優，提出了改進的布谷鳥搜索算法 然后使用改進的布谷鳥搜索算法對未知節點的位置進行估計。通過仿真實驗可以看出本文所提出的方法相比于標準的DV-Hop定位算法和基于標準布谷鳥搜索算法的DV-Hop算法具有更好的定位精度，并且更穩定。