基于坐標優化的FOA-Amorphous節點定位算法

彭 鐸,張 倩,張騰飛,陳江旭

(蘭州理工大學 計算機與通信學院,甘肅 蘭州 730050)

0 引 言

無線傳感器網絡[1-2](Wireless Sensor Networks,WSN)是由數量眾多的無線傳感器節點構成,這些節點以自組織的方式相互協調工作,傳感器節點之間可以傳輸信息并協作感知環境。無線傳感器網絡在軍事偵察、環境監測、搶險救災、醫療保障等許多領域都有著廣泛的應用[3]。在這些應用中,獲取的數據必須要有相應的位置信息,如果沒有位置信息,相互傳遞的數據就毫無價值,失去了采集數據的意義,因此節點定位也是WSN的關鍵支撐技術之一[4-5]。近些年來,諸多學者對距離無關的定位算法展開研究,希望提高定位精度,使得未知節點在定位過程中能獲得更為準確的位置信息[6]。

Amorphous算法定位精度不高,諸多學者對其進行了數學優化,或者加入改進后的群體智能算法力求有效降低未知節點的定位誤差。文獻[7]提出了一種新的算法來優化Amorphous定位算法。首先,通過傳統算法得到未知節點位置的初始解;然后,利用遺傳禁忌搜索算法優化初始解,從而得到未知節點的最優位置。文獻[8]分析Amorphous定位算法的缺點,對節點間跳數進行修正,引用質心算法加權,提出改進的算法模型,仿真結果表明該算法可獲得較為精確的定位結果。文獻[9]提出了基于KNN算法的指紋室內定位技術,解決了基于距離相關的RSSI定位算法中定位節點遺漏問題。文獻[10]提出基于RSS閾值模型的Amorphous算法,在Amorphous算法離線計算網絡平均連通度的基礎上,建立了四種RSS閾值模型來抑制Amorphous算法在不同通信模型下的定位誤差。文獻[11]引用了雙通信半徑對節點之間最小跳數進行細化,修正平均跳距則引入了最小均方差準則以及歸一化加權因子,最后,采用優化的麻雀搜索算法估算未知節點的位置。

文獻[12]通過增加通信半徑,將距離信標節點較近的未知節點獲得的最小跳數更新為較小的跳數,并保持距離較遠的未知節點的最小跳數信息。該方法以跳數的形式反映了實際距離之間的差距,在一定程度上解決了跳數相同但實際距離差異較大的問題。因此,可以估計更準確的平均跳躍距離,計算出它們之間更精確的距離,得到未知節點更精確的坐標。文獻[13]提出了一種基于粒子群優化(PSO)的DV-Hop定位算法。在所提出的算法中,錨節點的跳數使用校正因子進行修改,通過更新校正因子,提高了節點之間距離測量的準確性。為了進一步提高準確性,使用PSO算法,因為WSN中的定位是一個優化問題。在有界種群可行域的幫助下,使用PSO對未知節點的定位更加準確,收斂速度相對較高。仿真結果表明,該算法的定位誤差顯著降低。

上述研究通過不同的方法對傳統算法的不足之處進行了不同程度的改進,但改進算法仍然存在定位誤差較大或算法復雜度高等問題。針對這些不足,該文提出了一種基于坐標優化的FOA-Amorphous節點定位算法。該算法在計算跳數值時用多通信半徑細化跳數,利用網絡平均連通度對節點的平均跳距進行重算,果蠅優化算法將極大似然估計法計算得到的未知節點坐標作為每個果蠅的初始位置,通過此初始位置產生每個果蠅的初始種群,代入適應度函數對解進行更新迭代,直到找到具有最佳適應度的解,將此解作為未知節點的坐標。

1 相關理論

1.1 Amorphous算法介紹與定位誤差分析

Amorphous算法[14]是基于非測距的定位算法,該算法通過以下三步實現對未知節點的定位:

步驟1:計算未知節點距各錨節點的最小跳數。

每個錨節點將含有其位置坐標信息的數據包廣播到全網,錨節點的初始跳數為0,數據包每經過一個節點,跳數加1,當一個節點收到多個跳數信息時,保存跳數值最小的一條信息。

步驟2:計算未知節點到各錨節點的距離。

在第一階段,每個錨節點記錄了到其他錨節點的最小跳數,通過公式(1)計算它和錨節點之間的距離di,j:

di,j=R×hopi,j

(1)

其中,di,j表示錨節點i和未知節點j之間的距離,R為節點的通信半徑,hopi,j表示錨節點i和未知節點j之間的最小跳數。

步驟3:利用極大似然估計法計算自身位置。

通過前兩個步驟的計算可以得到未知節點到錨節點之間的距離,因此,可以得到以下方程組:

(2)

其中,(x,y)為未知節點的坐標,(xi,yi)為信標節點的坐標,di為估計距離。通過解上式方程組可以得到未知節點的坐標。

Amorphous算法與DV-Hop算法在某些方面具有相似性,均是通過計算出的最小跳數乘以平均跳距來估計未知節點至錨節點的距離。不同之處是,Amorphous算法將通信半徑作為錨節點的平均跳距來估算節點間的距離,而DV-Hop算法中錨節點的平均跳距是由兩個錨節點間的距離除以跳數得到。

下面將分析Amorphous算法定位誤差產生的主要原因:

①算法在計算節點間的最小跳數時,結果都是整數,但是現有的實驗證明這大約增加了0.5個平均跳數的誤差,導致算法的定位誤差增大。

②由于網絡節點分布的不規則性,兩節點之間的距離或大或小,以節點通信半徑來估算兩節點間的距離會導致定位誤差過大。

③利用極大似然估計法求解未知節點坐標時,受初始值測量誤差影響較大,小的測量誤差就會導致較大的位置估計誤差。

1.2 果蠅優化算法

果蠅優化算法(Fruit Fly Optimization Algorithm,FOA)是由潘文超博士[15]提出的一種演化式群智能優化算法,其基本思想來自于果蠅在自然界中的覓食行為。相較于其他物種,果蠅在嗅覺和視覺上更為敏感。因此,在覓食過程中,果蠅可以利用自身獨特的嗅覺發現食物氣味,并分享給周圍的果蠅,比較后可以得到氣味最優的果蠅個體位置,同時其他果蠅均會向該位置飛去,通過不斷地迭代更新最后得到果蠅群體中的最佳位置。

由文獻[15]可知果蠅優化算法是一種更簡單、更魯棒的優化算法;該算法不僅具有易于理解的特點,而且易于寫入程序代碼。同時,與其他算法相比,程序代碼不會太長,很容易用于處理各種優化問題。其算法步驟如下:

(1)給定果蠅種群規模(Sizepop)、群體最大迭代次數(Maxgen),隨機初始化果蠅個體初始位置X_axis、Y_axis。

(2)根據式(3)確定每個果蠅個體尋找食物的隨機距離和方向。

(3)

式中,RValue為果蠅隨機搜索距離和方向的隨機數。

(3)計算果蠅個體與原點距離Di和果蠅個體的味道濃度判定值Si,Si為距離Di的倒數。

(4)

Si=1/Di

(5)

(4)將味道濃度判定值Si代入適應度函數,求解出該種群中果蠅個體的味道濃度Smell(i)。

Smell(i)=Function(Si)

(6)

(5)找出種群當前味道濃度最優個體(即味道濃度最小值),記錄其坐標和味道濃度值。

[bestSmell,bestIndex]=min(Smell)

(7)

(6)記錄最優味道濃度值及對應的橫縱坐標,群體中的其他果蠅均利用視覺向該位置飛去,形成新的果蠅群體。

X-axis=X(bestIndex)

(8)

Y-axis=Y(bestIndex)

(9)

bestSmell=Smellbest

(10)

(7)迭代尋優階段,重復執行步驟(2)～步驟(5),判斷當前迭代次數是否小于最大迭代次數,當前味道濃度是否優于所記錄的最優味道濃度,若成立,執行步驟(6)。

2 基于多通信半徑和FOA-c的節點定位算法

2.1 自適應權重因子優化果蠅算法(FOA-c)

FOA迭代尋優時,由式(3)可知,每只果蠅個體移動的距離是固定范圍的隨機值,在接近最優果蠅時,果蠅的搜索范圍具有局限性,易陷入局部最優,收斂精度低,出現早熟收斂。該文借鑒文獻[16]中粒子群優化算法的認知因子和引導因子,在算法迭代過程中引入了個體認知因子c1和群體引導因子c2,其中,個體認知因子控制著果蠅個體對自己和其他果蠅個體位置的認知,群體引導因子控制著整個果蠅群體目前的最優位置對果蠅個體的引導。這將有助于算法迅速收斂于全局最優,避免算法早熟,提高了算法的收斂精度。

(11)

迭代尋優階段,將式(3)可更換為:

(12)

其中,mean(X)和mean(Y)表示上次迭代中所有果蠅個體的平均值,(X(i,:),Y(i,:))表示上次迭代中果蠅的位置。

在相同實驗條件下,選取了與式(18)維度一致的基測函數對FOA-c算法和FOA算法進行了尋優性能的對比,如圖1所示。從圖中不難看出,FOA-c算法相比較FOA算法,收斂速度更快,尋優精度更高。

圖1 算法收斂曲線

2.2 FOA-Amorphous算法

FOA-Amorphous算法首先通過多通信半徑對最小跳數進行細化;接著采用網絡平均連通度對平均每跳距離進行重算;最后將極大似然估計法計算到的未知節點坐標作為每個果蠅的初始位置,利用FOA-c算法求得最佳未知節點的位置坐標。

2.2.1 多通信半徑細化跳數

如圖2所示,假設在錨節點A的通信半徑范圍內有B、C、D三個未知節點,由Amorphous算法可知,錨節點A到B、C、D之間的跳數均為1跳,若用Amorphous算法的實現步驟來計算節點間的距離,則AB=AC=AD,但從圖中來看,未知節點B、C、D到錨節點A的實際距離卻不相同。

圖2 通信半徑內節點分布

因此,該文利用多通信半徑來細化跳數:

(13)

其中,R為節點的通信半徑,h為跳數;d為錨節點與其鄰居節點的實際距離。

(14)

2.2.2 重新計算平均每跳距離

由于網絡節點分布的隨機性,兩節點之間的跳段距離通常不是兩者的直線距離,用通信半徑乘以最小跳數過大地估計了跳段距離。

FOA-Amorphous算法先用式(15)計算網絡平均連通度:

nlocal=NπR2/S

(15)

式中,N為網絡節點總數,R為節點的通信半徑,S為網絡區域面積。

用式(16)計算平均每跳距離:

(16)

2.2.3 定位計算優化

由于節點間的距離都是通過跳數乘以平均跳距估計出來的,由Amorphous算法的誤差分析得知估計距離與節點間的實際距離有較大誤差。假設未知節點(x,y)與錨節點(xi,yi)之間的距離為di,估計誤差為τi,則有以下約束條件:

(17)

越小的τi將使得未知節點的估計坐標與實際值更加接近。因此,將節點定位問題轉化為求最優值問題,則有以下適應度函數:

(18)

通過FOA-c算法迭代尋優找到使得函數值F(即估計誤差τi)趨近于0的適應度值的坐標,此坐標更接近未知節點的實際坐標,提高了算法的定位精度。

算法將極大似然估計法計算到的未知節點位置坐標作為每個果蠅的初始位置,利用式(3)產生每個未知節點的初始種群,代入適應度函數得到初始適應度值,再用式(12)產生的新種群進行更新迭代,直到找到具有最佳適應度的解,將此解作為未知節點的位置。

算法的具體步驟如下:

Step1:利用多通信半徑的方法細化跳數;

Step2:利用公式(16)重新計算節點的平均每跳距離;

Step3:由平均跳距乘以細化跳數得到未知節點與錨節點之間的跳距;

Step4:利用極大似然估計法計算每個未知節點的坐標,將此坐標作為每個果蠅的初始位置;

Step5:利用式(3)產生每個果蠅(即每個未知節點)的初始種群,代入適應度函數得到個體的初始適應度值;

Step6:利用式(12)產生新的種群代入適應度函數,通過迭代找到最佳適應度的解,將輸出的最佳解作為未知節點的坐標;

Step7:循環多次步驟5和步驟6,直到找到所有的最佳未知節點的坐標為止。

3 算法仿真及結果分析

3.1 算法參數設置

為了驗證算法的定位性能,利用MATLAB2016b對文中算法(FOA-Amorphous)、Amorphous算法、文獻[12]提出的雙通信半徑算法以及文獻[13]提出的PSO-IDV-Hop算法,從錨節點個數、通信半徑大小、總節點個數以及時間復雜度等四個方面進行仿真實驗分析。在100 m×100 m的仿真區域內,隨機產生一定數量的網絡節點。

算法的參數設置如表1所示。

表1 算法相關參數設置

算法中每個未知節點的定位誤差計算公式如下:

(19)

算法的歸一化定位誤差計算公式如下:

(20)

3.2 定位誤差仿真實驗分析

設置總節點個數為100,錨節點個數為20,通信半徑為30。該文提出的算法與傳統算法的定位效果如圖3所示,從圖中不難看出,該文提出的算法估計的節點位置與傳統算法相比更加靠近真實位置。

圖3 算法的定位效果

3.2.1 未知節點平均定位誤差比較

在監測區域內隨機部署100個節點,其中錨節點個數為20,未知節點個數為80個,通信半徑為30,四種算法各運行100次后的平均定位誤差如圖4所示, PSO-IDV-Hop算法和文獻[12]的算法的平均定位誤差大約分別為13.4 m和6.5 m,該文提出算法的未知節點的平均定位誤差大約為4.3 m,與其他三種算法相比,定位誤差更低。

圖4 四種算法每個未知節點的定位誤差對比

3.2.2 錨節點對定位誤差的影響

圖5是節點總數為100,通信半徑為30時,錨節點比例變化對未知節點定位誤差的影響。

圖5 錨節點個數對定位誤差的影響

由圖5可知,四種算法定位誤差均隨錨節點所占比例的增大而減小,是因為在總節點個數不變的情況下,錨節點的個數增加,則其密度增大,一個未知節點可以獲得的錨節點的位置信息增多,使其定位誤差降低。在相同的條件下,文中算法的誤差一直都是最小的,與PSO-IDV-Hop算法相比,其歸一化定位誤差降低了30%左右,與文獻[12]改進的算法相比,其歸一化定位誤差降低7%左右,與Amorphous算法相比,歸一化誤差降低了53%左右。從整體來看,無論錨節點的比例是多是少,該文提出的算法都具有更好的定位效果。

3.2.3 通信半徑對定位誤差的影響

圖6是在總節點個數為100,錨節點個數為30的條件下,通信半徑從25變化到50的誤差變化圖。

圖6 通信半徑對定位誤差的影響

由圖6可見,文中算法與文獻[12]中算法的定位誤差均隨通信半徑的增大而穩定減小,而PSO-IDV-Hop算法在通信半徑大于45之后定位誤差略有增加,這是由于隨著通信半徑增大,一跳范圍內的節點數增多,導致算法的跳數誤差增大,而文中算法和文獻[12]的算法對跳數進行了細化,使誤差隨著通信半徑的增加平穩減小。與其他三種算法相比,文中算法的歸一化定位誤差始終最低,相比較文獻[12]的算法、PSO-IDV-Hop算法和Amorphous算法歸一化定位誤差分別降低了8%、24%和44%左右。

3.2.4 節點總數對定位誤差的影響

圖7是在錨節點比例為30%,通信半徑為30的條件下,定位誤差隨節點總數的變化圖。

圖7 節點總數對定位誤差的影響

從圖中可以看出,隨著節點總數的增加,Amorphous算法的定位誤差呈現上升的趨勢,這是因為當仿真區域面積不變的情況下,節點個數增加,節點密度增大,則節點的平均鄰居節點數增多,用通信半徑代替平均跳距計算距離時本來就有誤差產生,當鄰居節點增多,這種誤差將會累積增大。然而,文中算法與PSO-IDV-Hop算法以及文獻[12]算法的定位誤差穩定下降,是因為算法對跳數進行了優化,且文中算法和PSO-IDV-Hop算法加入了智能優化算法,優化了未知節點的坐標。與其他三種算法相比,文中算法的歸一化定位誤差最低,低于文獻[12]算法7%左右,低于PSO-IDV-Hop算法和Amorphous算法分別為23%和66%左右。

3.3 時間復雜度與計算開銷分析

時間復雜度反映了算法執行的時間長短。假設未知節點個數為n,錨節點的個數為m(m

將算法的平均運行時間作為算法開銷指標進行分析。圖8為相同實驗條件下所統計的四種算法的運行時間比較。

圖8 四種算法的平均運行時間

由實驗結果可知,文中算法的運行時間比Amorphous算法和文獻[12]算法的運行時間大,是因為文中算法加入了智能優化算法,使得算法的運行時間增加;但比PSO-IDV-Hop算法的運行時間小,這是因為FOA算法比PSO算法更簡單、更魯棒[10],且文中算法加入了個體認知因子和群體引導因子,使算法快速收斂到全局最優,提高了算法的收斂精度。從整體來說,文中算法的運行時間略有增加,但算法的定位精度得到了很好的提升。

4 結束語

主要針對Amorphous算法存在的誤差分析,提出了一種新的FOA-Amorphous算法。該算法通過對通信半徑劃分實現了跳數的細化,利用網絡平均連通度對錨節點的平均跳距進行重算,然后用極大似然估計法計算得到的未知節點坐標值作為果蠅算法中每個果蠅的的初始位置,通過此初始位置產生每個果蠅的初始種群,代入適應度函數對解進行更新迭代,直到找到具有最佳適應度的值,將此解作為未知節點的最終位置坐標。仿真實驗表明,雖然算法的運行時間略有增加,但從整體來看,無論錨節點、通信半徑、總節點數如何變化,該算法都具有更好的定位性能。未來主要的研究熱點可能是移動節點、不規則拓撲網絡和三維地形中的研究。