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

楊曉琴

（太原廣播電視大學(xué) 太原 030002）

1 引言

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

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

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

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

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

2 DV-Hop定位算法

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

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

然后，信標(biāo)節(jié)點和未知節(jié)點之間的距離將會被估計。為了將跳數(shù)信息轉(zhuǎn)換成物理距離，則會估計平均跳數(shù)距離。當(dāng)一個信標(biāo)節(jié)點得到了其它信標(biāo)節(jié)點的坐標(biāo)和跳數(shù)，則會計算平均跳數(shù)距離，然后它將會傳播到整個網(wǎng)絡(luò)進行糾正。平均跳數(shù)距離則由下式得出：

其中，(xi，yi)和 (xj，yj)分別是信標(biāo)節(jié)點 i和 j的坐標(biāo)，hj是信標(biāo)節(jié)點i和 j之間的跳數(shù)。

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

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

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

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

3.1 布谷鳥搜索算法

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

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

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

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

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

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

全局搜索位置更新公式為

其中μ和ν服從標(biāo)準(zhǔn)正態(tài)分布，β=1.5。

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

3.2 改進的布谷鳥搜索算法

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

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

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

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

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

式（2）中的dn為估計距離，它和實際距離肯定有一定的誤差εn，所以式（2）則轉(zhuǎn)變?yōu)?/p>

當(dāng)ε的值越小，未知節(jié)點(x，y)的坐標(biāo)就越優(yōu)。未知節(jié)點定位問題的實質(zhì)則是一個優(yōu)化問題，如下：

那么改進的CS算法的目標(biāo)函數(shù)可表示為

4 仿真實驗

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

1）通信半徑與平均定位誤差的關(guān)系

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

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

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

2）信標(biāo)節(jié)點數(shù)量與平均定位誤差的關(guān)系

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

圖2 不同信標(biāo)節(jié)點數(shù)量的平均定位誤差

3）節(jié)點數(shù)量與平均定位誤差的關(guān)系

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

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

4）迭代次數(shù)與平均定位誤差的關(guān)系

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

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

5 結(jié)語

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