基于改進花授粉算法的RSSI定位方法*

劉國繁， 肖 勇

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

0 引 言

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

1 RSSI優化問題描述[7]

1)根據信號傳播衰減模型即可估算出兩節點之間RSSI距離測量值。本文采用對數—常態分布模型[8]

(1)

(2)

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

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

(3)

3)估算未知節點位置坐標。采用群智能算法進行未知節點位置求解，通過個體的適應度值判斷個體所在位置的優劣并不斷調整搜索方向進行迭代求精

(4)

式中m為錨節點個數。花粉位置坐標為(x，y)，錨節點坐標為(xi，yi)，di為未知節點到錨節點的RSSI距離測量值。當求得最優解使得fitness(x,y)取得最小值時，節點定位總誤差最小，此時的坐標(x,y)則為最優值，即最接近未知節點真實位置坐標。

將RSSI定位問題轉換為RSSI優化求解問題，在一定程度上可抑制測距誤差對定位精度的影響。如式(4)所示，RSSI約束優化求解問題為非線性問題，采用傳統數學方法難以求解，本文考慮采用改進后的花授粉算法求解。

2 改進花授粉定位算法

2.1 花授粉算法

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

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

(5)

(6)

式中Γ(λ)為標準的伽馬函數[11]。

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

(7)

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

2.2 步長的改進

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

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

(8)

式中wmax和wmin為最大權重和最小權重，t為當前迭代次數，T為最大迭代次數。分析可知，權重系數為遞減函數，當t=0時，w=wmax；反之，當t=T時，w=wmin，因此可以很好地根據迭代次數在算法的前后期進行步長的分配。經過實驗對比，本文設置wmax為0.96，wmin為0.36。

改進后的全局授粉過程如下所示

(9)

2.3 局部變異改進

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

(10)

同時考慮到FPA缺乏變異機制，在迭代過程中難以跳出局部最優。考慮引入高斯變異策略[12]對陷入局部最優最優個體執行變異操作。高斯變異就是在原有個體上加以一個服從高斯分布的隨機擾動向量來取代原先個體

xi=xi+bN(0,1)xi

(11)

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

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

(12)

2.4 改進花授粉算法的RSSI定位步驟

步驟1：通過RSSI測距方法獲取目標區域內未知節點與錨節點之間的RSSI距離測量值d。

步驟2：設置初始參數：種群大小N、最大迭代次數T、參數維數D、轉換因子p值、變異因子ε初始值等。在目標區域內隨機產生N個D維初始花粉個體，每個花粉個體代表未知節點位置的一個候選解。

步驟3：通過式(4)計算每個花粉個體的適應值，通過比較，保存當前群體最優位置x*及最優適應值fitness(x*)。

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

步驟5：判斷是否滿足結束條件(達到迭代次數)，滿足則結束；否則，轉向步驟3。

步驟6：輸出全局最優解對應的個體位置，即未知節點的估計位置坐標。

3 仿真分析

3.1 仿真環境設定

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

(13)

3.2 收斂速度

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

3.3 測距誤差變化

由圖1(b)可知，隨著測距誤差的增加，幾種算法的定位誤差均呈現上升狀態，這是因為定位算法受RSSI距離測量值誤差影響，基于群智能優化算法的定位算法相較于RSSI定位算法在一定程度上抑制測距誤差對定位精度的影響。本文算法伴隨測距誤差的增大仍優于其他算法，擁有較好的穩定性。

3.4 錨節點數量變化

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

3.5 通信半徑變化

對不同通信半徑進行仿真，仿真結果如圖1(d)所示，當錨節點數量達到一定閾值后，網絡連通度達到飽滿，定位精度提升有限。相對于最小二乘法，PSO，FPA，本文算法定位更為準確，當通信半徑越大時，本文算法擁有較明確的優勢。

圖1 仿真測試結果

3.6 總節點數變化

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

4 結 論

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