劉國(guó)繁， 肖 勇

(1.湖南工程學(xué)院 電氣信息學(xué)院，湖南 湘潭 411104； 2.湘潭大學(xué) 信息工程學(xué)院，湖南 湘潭 411105)

0 引 言

在測(cè)距誤差客觀存在情況下，如何獲得更接近實(shí)際未知節(jié)點(diǎn)位置的估計(jì)位置坐標(biāo)并提高定位算法的穩(wěn)定性，是無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的主要考慮點(diǎn)。接收信號(hào)強(qiáng)度指示(received signal strength indication,RSSI)定位算法大致可分為兩個(gè)階段，第一階段，獲得未知節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的RSSI距離測(cè)量值，第二階段，通過節(jié)點(diǎn)之間的距離約束關(guān)系求解未知節(jié)點(diǎn)位置。大多數(shù)RSSI定位算法在第二階段通常使用最小二乘法[1]進(jìn)行未知節(jié)點(diǎn)坐標(biāo)求解。然而，在實(shí)際應(yīng)用中發(fā)現(xiàn)，測(cè)距誤差對(duì)最小二乘解的精度影響很大，當(dāng)測(cè)距誤差較大時(shí)，其定位精度較低，不能滿足定位要求。近年來，學(xué)者們考慮將定位問題轉(zhuǎn)化為約束優(yōu)化問題，采用群智能優(yōu)化算法進(jìn)行優(yōu)化求解，如粒子群優(yōu)化(particle swarm optimization,PSO)算法[2]、蟻群算法[3]、蝙蝠算法[4]等，將求解的最優(yōu)值作為未知節(jié)點(diǎn)位置坐標(biāo)的估算值?；ㄊ诜鬯惴?flower pollination algorithm,FPA)算法[5]是2012年由英國(guó)劍橋大學(xué)楊新社學(xué)者提出一種新型啟發(fā)式群智能優(yōu)化算法，該算法結(jié)構(gòu)簡(jiǎn)單、參數(shù)較少、無需梯度信息，具有較好的全局搜索和局部搜索平衡性。在2013年，楊學(xué)者利用該算法求解多目標(biāo)求解問題[6]，驗(yàn)證了花授粉算法相較于粒子群算法、遺傳算法等其他群智能算法擁有更好尋優(yōu)性能。但同時(shí)花授粉算法存在易陷入局部最優(yōu)值、后期收斂速度慢等不足。為獲得更精確和更穩(wěn)定的定位結(jié)果，本文提出一種基于改進(jìn)花授粉算法的RSSI定位方法。

1 RSSI優(yōu)化問題描述[7]

1)根據(jù)信號(hào)傳播衰減模型即可估算出兩節(jié)點(diǎn)之間RSSI距離測(cè)量值。本文采用對(duì)數(shù)—常態(tài)分布模型[8]

(1)

(2)

式中Pr(d)為信號(hào)接收強(qiáng)度；單位距離d0的信號(hào)接收強(qiáng)度為P(d0)，一般取d0=1 m；np為信道衰減指數(shù)，不同環(huán)境下np不同，dij為節(jié)點(diǎn)i和j之間通信距離；Xσ為高斯分布噪聲，通常采用正態(tài)分布Xσ～N(0,σ2)表示。

2)利用極大似然法構(gòu)建RSSI求解約束條件。假設(shè)在網(wǎng)絡(luò)中存在N個(gè)錨節(jié)點(diǎn)，坐標(biāo)分別表示為B1(x1,y1)，B2(x2,y2)，…，BN(xN,yN)，未知節(jié)點(diǎn)為P(x,y)，錨節(jié)點(diǎn)與未知節(jié)點(diǎn)P之間的RSSI距離測(cè)量值，分別表示為d1，d2，d3，…，dN，假設(shè)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間實(shí)際距離分別為r1，r2，…，rN，測(cè)距誤差分別為e1，e2，…，eN，則滿足。|ri-di|

(3)

3)估算未知節(jié)點(diǎn)位置坐標(biāo)。采用群智能算法進(jìn)行未知節(jié)點(diǎn)位置求解，通過個(gè)體的適應(yīng)度值判斷個(gè)體所在位置的優(yōu)劣并不斷調(diào)整搜索方向進(jìn)行迭代求精

(4)

式中m為錨節(jié)點(diǎn)個(gè)數(shù)?；ǚ畚恢米鴺?biāo)為(x，y)，錨節(jié)點(diǎn)坐標(biāo)為(xi，yi)，di為未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的RSSI距離測(cè)量值。當(dāng)求得最優(yōu)解使得fitness(x,y)取得最小值時(shí)，節(jié)點(diǎn)定位總誤差最小，此時(shí)的坐標(biāo)(x,y)則為最優(yōu)值，即最接近未知節(jié)點(diǎn)真實(shí)位置坐標(biāo)。

將RSSI定位問題轉(zhuǎn)換為RSSI優(yōu)化求解問題，在一定程度上可抑制測(cè)距誤差對(duì)定位精度的影響。如式(4)所示，RSSI約束優(yōu)化求解問題為非線性問題，采用傳統(tǒng)數(shù)學(xué)方法難以求解，本文考慮采用改進(jìn)后的花授粉算法求解。

2 改進(jìn)花授粉定位算法

2.1 花授粉算法

為更好模擬全局授粉和局部授粉過程，做出假設(shè)[9]：1)生物異花授粉視為全局授粉過程，其中攜帶花粉的傳粉生物通過Levy飛行[10]進(jìn)行傳播；2)非生物自花授粉是局部授粉過程；3)花的常性被認(rèn)為是繁衍概率，其中繁衍概率與參與授粉的兩朵花之間的相似性成比例關(guān)系；4)轉(zhuǎn)換概率p∈[0,1]控制全局授粉和局部授粉之間的轉(zhuǎn)換?？紤]實(shí)際環(huán)境中花授粉的臨近性及其它因素影響，p值設(shè)定需略偏向于局部授粉，因此p值一般設(shè)定在[0.6,1]區(qū)間。在文獻(xiàn)[10]中提出，p值設(shè)置為0.8時(shí)花授粉算法取得較好表現(xiàn)性能。

根據(jù)假設(shè)(1)和假設(shè)(3),全局授粉過程可表示為

(5)

(6)

式中Γ(λ)為標(biāo)準(zhǔn)的伽馬函數(shù)[11]。

根據(jù)假設(shè)(2)和假設(shè)(3),局部授粉過程可表示為

(7)

針對(duì)花授粉算法易陷入局部最優(yōu)值、在迭代后期收斂速度慢、缺乏變異機(jī)制的問題，分別從步長(zhǎng)權(quán)重、局部變異兩方面進(jìn)行改進(jìn)，增加種群的多樣性，提高算法的全局尋優(yōu)能力并避免種群個(gè)體陷入局部最優(yōu)。

2.2 步長(zhǎng)的改進(jìn)

花授粉算法在全局授粉部分雖然因Levy飛行機(jī)制的隨機(jī)性和較大移動(dòng)步長(zhǎng)能夠在一定程度上避免個(gè)體陷入局部最優(yōu)，但是缺乏自適應(yīng)性。通過優(yōu)化算法原理分析可知，在算法初期，需求較大的步長(zhǎng)使算法快速收斂到最優(yōu)位置附近，同時(shí)避免個(gè)體陷入局部最優(yōu)；算法后期，需求較小步長(zhǎng)進(jìn)行精準(zhǔn)迭代以獲得更高收斂精度，并加快收斂速度。本文對(duì)步長(zhǎng)因子加以一個(gè)根據(jù)迭代次數(shù)變動(dòng)的動(dòng)態(tài)權(quán)重w進(jìn)行合理分配。w設(shè)計(jì)公式如下

w=wmax-(wmax-wmin)t/T

(8)

式中wmax和wmin為最大權(quán)重和最小權(quán)重，t為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)。分析可知，權(quán)重系數(shù)為遞減函數(shù)，當(dāng)t=0時(shí)，w=wmax；反之，當(dāng)t=T時(shí)，w=wmin，因此可以很好地根據(jù)迭代次數(shù)在算法的前后期進(jìn)行步長(zhǎng)的分配。經(jīng)過實(shí)驗(yàn)對(duì)比，本文設(shè)置wmax為0.96，wmin為0.36。

改進(jìn)后的全局授粉過程如下所示

(9)

2.3 局部變異改進(jìn)

花授粉算法的局部授粉的位置更新過程只抽取兩個(gè)隨機(jī)花粉位置差的信息，在搜索最優(yōu)解的過程具有盲目性和不定向性。在此，首先考慮將歷史全局最優(yōu)值引入到局部授粉過程中，產(chǎn)生一種定向位置更新，可表示如下

(10)

同時(shí)考慮到FPA缺乏變異機(jī)制，在迭代過程中難以跳出局部最優(yōu)?？紤]引入高斯變異策略[12]對(duì)陷入局部最優(yōu)最優(yōu)個(gè)體執(zhí)行變異操作。高斯變異就是在原有個(gè)體上加以一個(gè)服從高斯分布的隨機(jī)擾動(dòng)向量來取代原先個(gè)體

xi=xi+bN(0,1)xi

(11)

式中b=(T-t)/T，t為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)，N(0，1)服從μ=0，σ2=1的標(biāo)準(zhǔn)高斯分布。分析可知，在算法初期，加以較大高斯變異向量以獲得更快收斂速度，在算法后期，加以較小高斯變異向量提升收斂精度，當(dāng)算法后期陷入局部最優(yōu)時(shí)，說明在當(dāng)前值附近必有更好的全局值，通過高斯變異向量達(dá)到跳出局部最優(yōu)并檢測(cè)周圍個(gè)體適應(yīng)值的效果。

通過式(10)、式(11)改進(jìn)后的局部授粉過程

(12)

2.4 改進(jìn)花授粉算法的RSSI定位步驟

步驟1：通過RSSI測(cè)距方法獲取目標(biāo)區(qū)域內(nèi)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的RSSI距離測(cè)量值d。

步驟2：設(shè)置初始參數(shù)：種群大小N、最大迭代次數(shù)T、參數(shù)維數(shù)D、轉(zhuǎn)換因子p值、變異因子ε初始值等。在目標(biāo)區(qū)域內(nèi)隨機(jī)產(chǎn)生N個(gè)D維初始花粉個(gè)體，每個(gè)花粉個(gè)體代表未知節(jié)點(diǎn)位置的一個(gè)候選解。

步驟3：通過式(4)計(jì)算每個(gè)花粉個(gè)體的適應(yīng)值，通過比較，保存當(dāng)前群體最優(yōu)位置x*及最優(yōu)適應(yīng)值fitness(x*)。

步驟4：如果randp，根據(jù)式(12)更新個(gè)體空間位置，計(jì)算新解的適應(yīng)值fitness，并與保存的最優(yōu)適應(yīng)值做比較，如果新解的適應(yīng)值更優(yōu)，則保留新解，并將新解的空間位置及適應(yīng)值更新為群體最優(yōu)位置x*及最優(yōu)適應(yīng)值fitness(x*)值，否則，仍保持原值不變。

步驟5：判斷是否滿足結(jié)束條件(達(dá)到迭代次數(shù))，滿足則結(jié)束；否則，轉(zhuǎn)向步驟3。

步驟6：輸出全局最優(yōu)解對(duì)應(yīng)的個(gè)體位置，即未知節(jié)點(diǎn)的估計(jì)位置坐標(biāo)。

3 仿真分析

3.1 仿真環(huán)境設(shè)定

為驗(yàn)證改進(jìn)花授粉算法的RSSI定位方法性能，設(shè)在100 m×100 m的二維區(qū)域內(nèi)，隨機(jī)部署100個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的通信半徑為30 m，錨節(jié)點(diǎn)比例為10 %。分別對(duì)RSSI定位算法(最小二乘法)、PSO算法的定位算法、基于FPA的定位算法在不同錨節(jié)點(diǎn)密度、不同通信半徑、不同節(jié)點(diǎn)數(shù)量條件下的定位精度進(jìn)行仿真比較。粒子群算法參數(shù)設(shè)置為：種群大小N=20，c1=c2=2，Wmax=0.9，Wmin=0.4，Vmax=5，算法的最大迭代次數(shù)為300次?；ㄊ诜鬯惴▍?shù)設(shè)置為：種群大小N=20，λ=1.5，p=0.8，改進(jìn)花授粉算法參數(shù)設(shè)置與花授粉算法相同。每組不同條件下的算法均仿真運(yùn)行100次，對(duì)結(jié)果取平均值進(jìn)行分析比較。采用平均定位誤差對(duì)定位算法優(yōu)劣進(jìn)行評(píng)價(jià)

(13)

3.2 收斂速度

PSO與FPA、本文算法的定位過程適應(yīng)值迭代變化曲線如圖1(a)所示。由圖可知，PSO，F(xiàn)PA的收斂速度分別為80,150次。而本文提出的改進(jìn)FPA算法只需60次左右就可收斂到更低適應(yīng)度值，驗(yàn)證本文算法改進(jìn)有效性，收斂速度提高，定位精度提升。

3.3 測(cè)距誤差變化

由圖1(b)可知，隨著測(cè)距誤差的增加，幾種算法的定位誤差均呈現(xiàn)上升狀態(tài)，這是因?yàn)槎ㄎ凰惴ㄊ躌SSI距離測(cè)量值誤差影響，基于群智能優(yōu)化算法的定位算法相較于RSSI定位算法在一定程度上抑制測(cè)距誤差對(duì)定位精度的影響。本文算法伴隨測(cè)距誤差的增大仍優(yōu)于其他算法，擁有較好的穩(wěn)定性。

3.4 錨節(jié)點(diǎn)數(shù)量變化

對(duì)不同的錨節(jié)點(diǎn)數(shù)量進(jìn)行仿真對(duì)比，仿真結(jié)果如圖1(c)所示。在相同錨節(jié)點(diǎn)數(shù)量情況下，本文算法誤差最小。考慮在給定定位精度要求前提下，可利用本文算法采用較少的錨節(jié)點(diǎn)數(shù)量完成定位，減少定位成本。

3.5 通信半徑變化

對(duì)不同通信半徑進(jìn)行仿真，仿真結(jié)果如圖1(d)所示，當(dāng)錨節(jié)點(diǎn)數(shù)量達(dá)到一定閾值后，網(wǎng)絡(luò)連通度達(dá)到飽滿，定位精度提升有限。相對(duì)于最小二乘法，PSO，F(xiàn)PA，本文算法定位更為準(zhǔn)確，當(dāng)通信半徑越大時(shí)，本文算法擁有較明確的優(yōu)勢(shì)。

圖1 仿真測(cè)試結(jié)果

3.6 總節(jié)點(diǎn)數(shù)變化

從圖1(e)中可以看出，在節(jié)點(diǎn)數(shù)相同的情況下，本文算法的平均定位誤差小于最小二乘法和PSO定位算法、FPA定位算法，相較于其他算法擁有更好的收斂性。

4 結(jié) 論

本文對(duì)于在測(cè)距誤差存在情況下，RSSI定位算法中采用最小二乘法求解未知節(jié)點(diǎn)位置受測(cè)距誤差影響較大這一情況，使用改進(jìn)FPA算法替代最小二乘法，降低測(cè)距誤差影響，獲得更好的定位精度。在測(cè)距誤差、錨節(jié)點(diǎn)所占比例、通信半徑、總節(jié)點(diǎn)數(shù)目變化的情況下，本文算法的誤差更小，對(duì)測(cè)距誤差影響起到一定抑制作用，證明本文算法適用于無線傳感器網(wǎng)絡(luò)的定位算法。但在定位求解時(shí)間和能量消耗方面，對(duì)網(wǎng)絡(luò)有一定的要求。