布谷鳥算法在無線傳感器網(wǎng)絡(luò)中的定位研究

李 娜，賈 偉

（陜西理工大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，漢中，723000）

引 言

無線傳感器網(wǎng)絡(luò)（Wireless sensor network,WSN）是當(dāng)今在國(guó)際上備受關(guān)注、多學(xué)科高度交叉和知識(shí)高度集成的前沿?zé)狳c(diǎn)研究領(lǐng)域[1]。WSN是由大量小型或者微型傳感器組成的互聯(lián)網(wǎng)絡(luò)，這些微型傳感器一般稱之為感知節(jié)點(diǎn)。WSN中感知節(jié)點(diǎn)的定位具有特殊的意義，只有這些節(jié)點(diǎn)明確自身的位置，才能為用戶提供有用的信息。因此，節(jié)點(diǎn)定位技術(shù)是WSN中許多應(yīng)用的關(guān)鍵支撐技術(shù)之一，是目標(biāo)跟蹤與導(dǎo)向、定向信息的查詢與傳遞、協(xié)助路由并實(shí)現(xiàn)路由協(xié)議、網(wǎng)絡(luò)拓?fù)淇刂坪途W(wǎng)絡(luò)覆蓋控制等技術(shù)的重要基礎(chǔ)，節(jié)點(diǎn)的定位信息非常重要[2-4]。

目前，在無線傳感器網(wǎng)絡(luò)中存在各種各樣的節(jié)點(diǎn)定位方法。在定位過程中，如果借助于特定硬件測(cè)量出節(jié)點(diǎn)間的角度或者距離，那么稱其為基于測(cè)距的定位方法；不通過測(cè)距，而是直接使用節(jié)點(diǎn)之間跳數(shù)的定位，稱其為非測(cè)距的定位方法[5]。采用的測(cè)距技術(shù)主要有接收信號(hào)強(qiáng)度指示（Received signal strength indicator，RSSI）[6]，接收信號(hào)傳播時(shí)間（Time of arrival，TOA）和接收信號(hào)傳播時(shí)間差（Time difference of arrival，TDOA）[7]等，它們的定位精度較高，但成本、功耗也相對(duì)較大，在實(shí)際應(yīng)用中并無太大優(yōu)勢(shì)；相反，不需要測(cè)距硬件的定位方法，可以節(jié)約成本，應(yīng)用也較廣泛，其最常用的方法有質(zhì)心定位[8]、基于距離向量跳數(shù)的（Distance vector hop,DV-HOP）定位[9-11]等算法，但它們存在定位精度相對(duì)較低或者通信開銷過大等缺點(diǎn)。

許多研究人員為降低誤差并提高定位精度提出引入群體智能優(yōu)化算法對(duì)非測(cè)距方法進(jìn)行改進(jìn)。文獻(xiàn)[12]利用和聲搜索算法(Harmony search，HS)實(shí)現(xiàn)節(jié)點(diǎn)定位，其仿真數(shù)據(jù)表明該算法在定位精度、運(yùn)行性能方面的效果較好。文獻(xiàn)[13]混合粒子群和差分進(jìn)化算法實(shí)現(xiàn)節(jié)點(diǎn)定位，實(shí)驗(yàn)結(jié)果表明該方法有更高的定位精度和更強(qiáng)的抗誤差性能。文獻(xiàn)[14-17]利用布谷鳥算法以及布谷鳥算法的變體實(shí)現(xiàn)節(jié)點(diǎn)定位，均取得了一定的效果。這幾種算法在一定程度上提升了定位性能并降低誤差，但是定位精度和誤差方面仍然可以進(jìn)一步改進(jìn)。因此，研究一種性能較好、效率較高的智能算法尤其重要。

本文提出一種基于布谷鳥搜索（Cuckoo search,CS）算法[18]的WSN節(jié)點(diǎn)定位智能優(yōu)化算法。通過引入全局和局部搜索能力較強(qiáng)的CS算法，并對(duì)步長(zhǎng)和拒絕概率參數(shù)進(jìn)行改進(jìn)，求得未知節(jié)點(diǎn)位置坐標(biāo)的估算與修正。最后通過MATLAB仿真實(shí)驗(yàn)，從多個(gè)方面與其他算法進(jìn)行比較，結(jié)果表明本文算法與DV-HOP算法、文獻(xiàn)[17]中（Self-adaption cuckoo search and distance vector hop,SACSDV-HOP）算法相比,可以有效地提高WSN中未知節(jié)點(diǎn)的定位精度，降低定位誤差，是一個(gè)較好的WSN節(jié)點(diǎn)定位解決方法。

1 WSN中未知節(jié)點(diǎn)定位模型

WSN是由許許多多的無線傳感器節(jié)點(diǎn)組成。在節(jié)點(diǎn)的定位過程中，找到未知節(jié)點(diǎn)的具體位置坐標(biāo)常采用的算法是：由少量的已知其位置的節(jié)點(diǎn)（即錨節(jié)點(diǎn)）和節(jié)點(diǎn)間的距離來估算。假設(shè)WSN中未知節(jié)點(diǎn)U的坐標(biāo)為U(x,y)，錨節(jié)點(diǎn)Ai的坐標(biāo)為Ai(xi,yi)，U和Ai之間的距離為di，其中i=1,2,3,…,n,那么存在

式中的方程組做減法后可表示為線性方程組AX=b，其中A為矩陣，b，X為向量，分別由式（2）―（4）計(jì)算。

利用最小二乘法可以得到未知節(jié)點(diǎn)U的坐標(biāo)為

式中：b向量中每一個(gè)元素均包括距離dn，要使未知節(jié)點(diǎn)的坐標(biāo)位置準(zhǔn)確，dn值的誤差就必須達(dá)到最小，即(b-AX)的取值應(yīng)為最小。為了提高網(wǎng)絡(luò)中未知節(jié)點(diǎn)的定位精度并求解出U，目標(biāo)函數(shù)可以定義為

通過式（6）可以看出，當(dāng)函數(shù)值越接近于0，所對(duì)應(yīng)的解越接近未知節(jié)點(diǎn)的具體坐標(biāo)位置。相應(yīng)地，在WSN中未知節(jié)點(diǎn)定位實(shí)際上就是在式（6）的一組可行解中求解最優(yōu)解的過程。

2 基于CS算法的節(jié)點(diǎn)定位過程

CS算法借助模擬布谷鳥的寄生育雛的繁殖策略，利用隨機(jī)或者類似隨機(jī)的飛行方式進(jìn)行全局搜索，尋得問題的最優(yōu)解。

2.1 CS算法

Yang等[18]模擬布谷鳥尋找鳥巢的策略，即通過隨機(jī)或者類似隨機(jī)的飛行方式，大自然中的布谷鳥來找尋適合自己產(chǎn)卵的鳥巢位置。首先需要假設(shè)3個(gè)理想狀態(tài)規(guī)則[18-19]：(1)每1只布谷鳥每一次只產(chǎn)1個(gè)卵，隨機(jī)選擇1個(gè)鳥巢堆放并孵化；(2)從隨機(jī)選擇的1組鳥巢中選擇位置最優(yōu)的，這個(gè)最優(yōu)的鳥巢會(huì)被保留到下一代；(3)在尋找鳥巢的過程中，可供選擇的鳥巢數(shù)量N是固定的，一個(gè)鳥巢的主人會(huì)發(fā)現(xiàn)外來鳥蛋的概率為Pa∈[0,1]。在這種情況下，鳥巢的主人可以有兩種策略：“丟棄該蛋”或者“放棄舊巢并另建新巢”。

由以上3條理想化規(guī)則，可以用式(7)表示布谷鳥尋找鳥巢的位置和路徑的更新，即

2.2 布谷鳥求解WSN定位問題分析

從上述描述中可以看到，CS算法包含參數(shù)較少，容易實(shí)現(xiàn)。其核心是利用萊維飛行機(jī)制尋找鳥巢位置，有著很好的全局和局部搜索能力。萊維飛行是一個(gè)隨機(jī)游走的過程，主要是由小步長(zhǎng)短距離飛行和大步長(zhǎng)的長(zhǎng)距離飛行構(gòu)成，前者頻率高，后者具有偶然性。因此，最優(yōu)的鳥巢即最優(yōu)解與步長(zhǎng)大小、Pa有密切關(guān)系，會(huì)直接影響算法性能。假如Pa值低，步長(zhǎng)值大，則可能將新的布谷鳥蛋放置于邊界之外，從而使CS算法效率低、收斂速度較慢。如果Pa值高，步長(zhǎng)值小，CS算法會(huì)很快收斂，但是在迭代過程中新解和上一個(gè)解的位置比較接近，會(huì)有很大的風(fēng)險(xiǎn)避開最優(yōu)解，陷于局部最優(yōu)。為了得到質(zhì)量好的最優(yōu)解，有大量研究人員對(duì)算法進(jìn)行改進(jìn)，彌補(bǔ)標(biāo)準(zhǔn)CS算法的不足。特別是標(biāo)準(zhǔn)CS算法沒有任何參數(shù)控制策略，自適應(yīng)參數(shù)化CS算法[20-27]得到了研究者的廣泛關(guān)注。其中文獻(xiàn)[23]能有效避免陷入局部最優(yōu)，顯著減少進(jìn)化過程并提高收斂速度；文獻(xiàn)[27]得到優(yōu)于其他自適應(yīng)CS算法的解決方案。

因此，使用一種性能較好、效率較高的自適應(yīng)CS算法來提升定位精度并降低誤差是必要的。本文通過文獻(xiàn)[27]的方法來調(diào)整步長(zhǎng)參數(shù)，即由式（8）來改變步長(zhǎng)stepi。

式中：disti為第i個(gè)鳥巢到具有最佳適應(yīng)值的布谷鳥巢的當(dāng)前距離；distmax為這一代中的一個(gè)鳥巢到最佳布谷鳥巢的最大距離；Rank為被定義的相對(duì)于整個(gè)種群適應(yīng)值的等級(jí)；t為當(dāng)前迭代次數(shù)；n為種群的大小。

步長(zhǎng)公式改變后，布谷鳥巢位置更新可由式（9）計(jì)算。

式中：rand為一個(gè)隨機(jī)數(shù)，根據(jù)當(dāng)代種群和最優(yōu)個(gè)體，產(chǎn)生對(duì)應(yīng)的新種群，最終實(shí)現(xiàn)迭代優(yōu)化；xgbest為最佳種群。

2.3 參數(shù)Pa的改進(jìn)

Pa參數(shù)的選取直接影響算法的性能，涉及到布谷鳥巢是否要更新。文獻(xiàn)[23]采用一種靜態(tài)學(xué)習(xí)策略：根據(jù)每個(gè)個(gè)體在前一階段中的更新成功率來選取一個(gè)合適的參數(shù)Pa。兩個(gè)參數(shù)Pa的選取可以由以表示為

式（10）參數(shù)Pa的取值較小，可能會(huì)增強(qiáng)算法搜索停滯的可能性，減慢搜索速度；式（11）中參數(shù)Pa的取值較大，可以提高算法中種群的多樣性，并加快收斂速度。在WSN節(jié)點(diǎn)定位中,根據(jù)需要選取一個(gè)合適的Pa來提高定位性能。在算法執(zhí)行初期，等概率選擇式（10）或式（11）作為個(gè)體的變異選擇概率Pa，隨后統(tǒng)計(jì)每個(gè)個(gè)體根據(jù)式（10）或式（11）進(jìn)行變異操作的更新成功率，由不同的成功率來決定下一次迭代中每個(gè)個(gè)體選擇采用式（10）或式（11）作為新參數(shù)Pa的概率。

2.4 布谷鳥搜索節(jié)點(diǎn)定位算法

根據(jù)上述過程，利用CS節(jié)點(diǎn)定位，就是求解搜索區(qū)域中的一個(gè)鳥巢位置，即函數(shù)優(yōu)化問題中每一個(gè)可行解。在CS的每一次迭代中，必須設(shè)定一個(gè)適應(yīng)值函數(shù)來判定鳥巢位置的優(yōu)劣，可設(shè)置適應(yīng)值函數(shù)為

要使所求的未知節(jié)點(diǎn)越接近真實(shí)節(jié)點(diǎn)的位置，問題轉(zhuǎn)化為智能優(yōu)化問題，當(dāng)函數(shù)值最小時(shí)，未知節(jié)點(diǎn)的估計(jì)位置越接近真實(shí)位置，定位精度越大。其算法描述如下：

Step 1定義問題和參數(shù)值。主要參數(shù)包括發(fā)現(xiàn)概率Pa和鳥巢的數(shù)量N。其中N個(gè)鳥巢的位置隨機(jī)生成，鳥巢的位置對(duì)應(yīng)傳感器的坐標(biāo)。

Step 2初始化鳥巢的位置，根據(jù)式（6）計(jì)算出當(dāng)前最好的鳥巢位置和其對(duì)應(yīng)的最優(yōu)適應(yīng)值，并保存下來。

Step 3根據(jù)式（9）產(chǎn)生新一代鳥巢的位置xt。計(jì)算出新的鳥巢適應(yīng)值與上一代最優(yōu)適應(yīng)值進(jìn)行比較，將適應(yīng)值最好的鳥巢位置xT保留至下一代。

Step 4發(fā)現(xiàn)概率Pa和所產(chǎn)生的均勻隨機(jī)數(shù)r做對(duì)比。如果r＜Pa,則保留當(dāng)前的最優(yōu)解xT；否則，通過隨機(jī)擾動(dòng)產(chǎn)生一個(gè)新的解xA。

Step 5評(píng)估f(xT)和f(xA)的優(yōu)劣。用較少的定位誤差的鳥巢位置代替誤差較大的鳥巢位置，留下質(zhì)量最優(yōu)的鳥巢位置。

Step 6判斷是不是滿足WSN節(jié)點(diǎn)定位的預(yù)測(cè)精度要求。若滿足，此次搜索完成，輸出全局最優(yōu)解對(duì)應(yīng)的鳥巢位置坐標(biāo)；否則，返回Step 3重新搜索到最大迭代次數(shù)tmax并輸出最優(yōu)解。

3 仿真實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證CS算法在WSN節(jié)點(diǎn)定位中的有效性，將其與DV-HOP和SACSDV-HOP算法的定位性能進(jìn)行比較。數(shù)值仿真實(shí)驗(yàn)通過Windows 10操作系統(tǒng)平臺(tái)上的MATLAB2014b進(jìn)行。實(shí)驗(yàn)中，設(shè)有多個(gè)無線傳感器隨機(jī)分布在200 m×200 m的二維區(qū)域中，其中包括多個(gè)錨節(jié)點(diǎn)和未知節(jié)點(diǎn)。相關(guān)算法重復(fù)運(yùn)行100次之后取平均值，定位結(jié)果優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)采用平均定位誤差。采用式（12）進(jìn)行定位誤差計(jì)算。

式中：R為節(jié)點(diǎn)間的最大通信距離，n為傳感器總節(jié)點(diǎn)數(shù)，m為錨節(jié)點(diǎn)個(gè)數(shù)，n-m為未知節(jié)點(diǎn)個(gè)數(shù)，Pi為節(jié)點(diǎn)i的實(shí)際坐標(biāo)，Pi′為算法求出的節(jié)點(diǎn)坐標(biāo)。

當(dāng)錨節(jié)點(diǎn)為20、未知節(jié)點(diǎn)為180以及最大通信距離為30 m的情況下，3種算法從定位誤差對(duì)比而言，通過修改CS算法的參數(shù)，可以減少傳感器的定位誤差，其結(jié)果如圖1所示。

從圖1可以看出，在相同的通信半徑、錨節(jié)點(diǎn)數(shù)目和總節(jié)點(diǎn)數(shù)據(jù)的情況小，本文算法在總體平均定位精度和定位穩(wěn)定性方面均優(yōu)于其他兩種算法。此外，為比較各個(gè)算法在不同通信狀況下的定位性能，分別從：（1）在節(jié)點(diǎn)間的不同通信距離；（2）不同錨節(jié)點(diǎn)數(shù)；（3）不同節(jié)點(diǎn)數(shù)的情況下，仿真了各個(gè)算法的定位誤差情況，結(jié)果如圖2―4所示。

圖1 不同算法的定位誤差比較Fig.1 Localization error comparison of different algorithms

圖2 不同通信距離定位誤差比較Fig.2 Comparison of localization errors in different communication distances

圖3 不同錨節(jié)點(diǎn)數(shù)與定位誤差Fig.3 Points of different anchor nodes and localization errors

圖4 不同節(jié)點(diǎn)數(shù)與定位誤差Fig.4 Different node numbers and localization errors

在圖2中，當(dāng)節(jié)點(diǎn)總數(shù)和錨節(jié)點(diǎn)數(shù)不變時(shí)，平均定位誤差都隨著通信半徑的增大而逐漸減小，本文提出算法的定位精度優(yōu)于DV-HOP和SACSDV-HOP算法。在圖3中，當(dāng)通信半徑和節(jié)點(diǎn)總數(shù)保持不變時(shí)，算法的定位誤差均隨著信標(biāo)節(jié)點(diǎn)數(shù)的增多而減小，但本文所提算法的定位精度優(yōu)于DV-HOP和SACSDV-HOP算法。在圖4中，在保持節(jié)點(diǎn)總數(shù)和通信半徑不變時(shí)，算法的定位誤差均隨著節(jié)點(diǎn)總數(shù)的增多而減小，同樣，本文所提算法的定位精度優(yōu)于DV-HOP和SACSDV-HOP算法。

綜上所述，可以得出在不同通信距離、不同錨節(jié)點(diǎn)數(shù)和不同總節(jié)點(diǎn)數(shù)的情況下，本文所提算法的定位精度都優(yōu)于DV-HOP和SACSDV-HOP算法。

4 結(jié)束語

節(jié)點(diǎn)定位技術(shù)是WSN的核心技術(shù)之一。由于使用最小二乘法在求解未知節(jié)點(diǎn)位置過程中會(huì)導(dǎo)致定位精度較低，因此本文提出一種基于改進(jìn)步長(zhǎng)和Pa的CS算法的WSN節(jié)點(diǎn)定位算法。仿真實(shí)驗(yàn)結(jié)果表明：相對(duì)于DV-HOP和SACSDV-HOP算法，本文算法平均定位誤差更小，并在一定程度上達(dá)到理想的定位精度和效果，具有較高的實(shí)用價(jià)值。