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

楊曉琴

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

1 引言

隨著科技發(fā)展，以傳感器和智能識(shí)別終端為代表的信息自動(dòng)生成設(shè)備可以實(shí)時(shí)地對(duì)物理世界感知、測(cè)量和監(jiān)控。微電子技術(shù)、計(jì)算機(jī)技術(shù)和無線通信技術(shù)的發(fā)展推動(dòng)了低功耗、多功能傳感器的快速發(fā)展，現(xiàn)已研制出了具有感知能力、計(jì)算能力和通信能力的微型傳感器。物理世界的聯(lián)網(wǎng)需求和信息世界的擴(kuò)展需求催生出一類新型網(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)的、具有無線通信與計(jì)算能力的傳感器節(jié)點(diǎn)組成。無線傳感器網(wǎng)絡(luò)所研究的熱門話題就是如何精確地對(duì)傳感器節(jié)點(diǎn)進(jìn)行定位。目前無線傳感器網(wǎng)絡(luò)的定位算法主要是分兩類。第一類是基于測(cè)距的定位算法［2～3］，該種算法對(duì)硬件裝置有一定的局限性，費(fèi)用很高；第二類是無需測(cè)距的定位算法［4～5］，該種算法對(duì)硬件要求并不高，并且費(fèi)用也不高。所以無需測(cè)距的定位算法具有很強(qiáng)的研究?jī)r(jià)值。

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

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

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

2 DV-Hop定位算法

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

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

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

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

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

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

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

3 基于改進(jìn)的布谷鳥搜索算法的DV-Hop算法

3.1 布谷鳥搜索算法

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

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

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

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

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

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

全局搜索位置更新公式為

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

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

3.2 改進(jìn)的布谷鳥搜索算法

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

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

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

3.3 基于改進(jìn)布谷鳥搜索算法的DV-Hop算法

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

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

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

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

4 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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