基于雞群算法的無線傳感器網絡定位研究*

李 鵬,陳桂芬,胡文韜

(長春理工大學電子信息工程學院,長春 130022)

無線傳感器網絡WSNs(Wireless Sensor Networks)是當前信息科學技術領域研究的熱點之一,可實現特殊情況下信號的收集、處理和發送。由于其獨特的學科交叉性,成為了二十一世紀極具發展潛力的關鍵技術。無線傳感器網絡是僅次于互聯網的第二大網絡,具有低成本、體積小、傳輸距離遠等優勢,廣泛應用于軍事、醫療環境監測等方面[1]。定位技術作為無線傳感器網絡的關鍵技術,在很多領域發揮重要作用。可以幫助人們實時獲取所需的位置信息和實時情況,同時獲取傳感器節點的確切位置還確保了無線傳感器網絡后續的路由及覆蓋算法的高效執行。因此研究無線傳感器網絡定位意義深遠。

針對各種定位算法的不足之處很多學者提出了不同的改進優化算法。文獻[2]通過篩查參考節點共線問題,盡量避免該情況影響定位精度,但增加了算法復雜度;文獻[3]通過構造RSSI比值來修改跳數信息,并且通過系數加權方法來校正跳距長短,減少了估計誤差,但造成多余的能耗;文獻[4]將兩代節點取平均值并用改進的粒子群算法優化節點定位,效果較明顯,卻存在一定誤差;文獻[5]改變節點通信半徑,影響跳數,提高定位精度,效果不是特別明顯;文獻[6]通過改善最小均方誤差的指標值來改變平均跳距,并獲得最佳指標值,對提高定位精度起著重要作用,同樣不可避免誤差問題;文獻[7]提出了一種結合RSSI技術校正通信半徑周圍節點跳距誤差的新方法;文獻[8]將改進后的雞群算法應用于無線傳感器網絡定位,提高了收斂速度和定位精度,算法有待進一步完善;文獻[9]提出RSSI測距與累計誤差相結合的算法,相比原算法提高較大精度,但算法相對復雜;文獻[10]通過分析理想和真實環境中的RSSI定位算法,研究了各種環境因素對定位精度的影響;文獻[11]提出一種新的目標檢測算法,實現了分布式一致性目標定位,并用信號強度估測在通信鏈路失效情況下的目標距離,并且相鄰節點之間的信息交換縮短了定位時間。近年來,隨著在傳統算法的基礎上衍生出來的群智能算法的興起,再結合仿生學原理,研究人員根據生物進化機制對群智能算法進行數學建模,并利用群體間的默契合作,簡單整體高效的求解復雜難懂的數學模型。而無線傳感器網絡定位問題一定程度上也可看做復雜的數學模型,因此群智能算法更適用于無線傳感器網絡定位問題。幾年前提出的雞群算法作為新興的群智能算法,在收斂性、魯棒性以及準確性方面較其他算法有著很大的優勢,且很少有要調整的參數,為無線傳感器網絡定位算法的誤差優化提供了新的解決思路。

考慮到上述算法優缺點,本文提出了一種將改進的雞群算法與總結出的定位模型相結合的ICSO算法,首先提出基于pareto距離分級的適應度計算方法合理分配雞群,并在此基礎上優化母雞位置公式,最后在小雞位置公式中引入凈能量增益,全面提高定位精度。仿真結果表明,與改進后的粒子群算法和其他改進后的雞群算法相比,ICSO算法在多種條件下均能有效提高定位精度。

1 定位節點模型的建立

在眾多經典的非測距算法中,DV-Hop算法以其簡單易實現及定位精度較高而被備受關注。該算法經常使用最小二乘法計算節點坐標。但定位精度會受到累計誤差的影響。針對這一問題總結一種節點定位模型,并對可能存在的誤差進行分析。假設網絡區域中(x,y)為未知節點坐標,(xi,yi)為參考節點坐標。參考節點和未知節點間的距離為di,i=1,2,…,n。則di可表示如下;

(1)

將式(1)變為線性方程組,如式(2):

AX=b

(2)

其中:

(3)

(4)

(5)

以上公式是在理想情況下構造的,而在實際問題中,距離測量的誤差問題難以避免。即AX+N=b,N代表n-1維誤差向量。要想讓X更加準確,則應使N取最小值。求得:

X=(ATA)-1ATb

(6)

不難看出,參數b對X的求解起著至關重要的作用。確定b的最重要因素是dn。若dn的值較大,用于計算具體節點坐標的最小二乘法不能有效應用。針對這一弊端,將誤差較大環境下的定位問題轉換為函數約束優化問題。上式改寫為:

(7)

節點間的距離測量誤差公式如下:

|ri-di|<εi

(8)

εi為節點間的測距誤差。ri是網絡中參考節點i與未知節點的實際距離。i=1,2,…,n。即:

(9)

(10)

分析式(10),f(x,y)的值越小代表要求解的坐標值與實際值越接近。這樣,將網絡節點定位問題轉換成多維約束優化方程。利用全局優化的雞群算法迭代尋優特性,求解所求節點的具體位置。逐步迭代減小差值,直到獲得最佳值。

2 雞群算法

2.1 雞群算法介紹

雞群算法(Chicken Swarm Optimization,CSO)是在2014年由MENG Xianbing等[12]提出的一種基于雞群覓食行為的智能搜索算法,將雞群搜索行為和階級制度歸納為求固定區域內最佳值的優化問題。成立前提如下:①雞群分為若干子種群,每個種群由一只公雞,較少數量的母雞和較多的小雞組成。②根據適應值不同分配公雞、母雞和小雞。③雞群中上下級制度到達某一代后再重新分配。④雞群按分級制度覓食,小雞可以其他個體發現的食物為食。

當使用雞群算法解決優化問題時,雞群中每只雞看作該問題的解。N為整個種群的所有雞個體數。假設NR、NH、NC、NM分別代表了公雞、母雞、小雞以及雞媽媽的個數。雞群中個體尋食的位置更新公式與子群分配的角色有關[13]。三種雞的位置更新公式分別如下:

①公雞個體位置更新公式為:

(11)

(12)

②母雞個體位置更新公式為:

(13)

(14)

S2=exp(fr2-fi)

(15)

其中,rand是[0,1]之間均勻分布的隨機數;r1是第i只母雞所在子群中的公雞;r1是整個雞群中的所有公雞和母雞中的任意個體,且r1≠r2。S1=0,第一只母雞會追隨其他雞搜索而搜索。S2=0,小雞只會在自己的周圍搜索食物,不會表現出從其他群體搶奪偷竊以獲取食物的行為。

③小雞個體的更新方式為

(16)

2.2 適應值函數

雞群搜索算法將定位問題中每個可能解視為搜索空間中雞的位置。在雞群搜索的每次迭代中,要設置一個適應值函數來評判當前雞個體位置的優劣,引導其向位置較優的雞靠攏。具體適應值函數設定為:

(17)

式中,要測量的節點位置由(x,y)表示,且第i個已知節點位置由(xi,yi)表示。因此可以通過求解fitness(i)的最小值來測算節點位置。

2.3 雞群算法的改進

2.3.1 對雞群個體選取方法的改進

傳統雞群算法中最好適應值個體是公雞,較優的一些是母雞,余下的是小雞。總體而言,應使種群中公雞數遠小于母雞,母雞數遠小于小雞。傳統雞群算法只能保證公雞個體一定會被選擇出來,而不同實際情況下種群適應值往往相差很多,無法合理分配比例。針對這一問題,提出關于距離的pareto雞群算法DPCSOA(Distance-based Pareto Chicken Swarm Optimization Algorithm)。該算法將每個子種群細分為兩個種群:一個是使用標準雞群算法種群Cn,另一個是從種群迭代至今得到的所有非劣解集的最優種群En。

(18)

第i只雞尋找所有對于m=1,2,…,M的最小d(m)(i),即d(min)=mind(m)(i),記該最小距離的索引為m*,記F(e(m*))為F*。此后,如果第i只雞劣于當前最佳組,則它進入最佳組,計算其適應值為距該雞最小距離的最佳個體的適應值與該最小距離之和,即;

F(x)=F*+dmin

(19)

如果有比i只雞更好的個體,則將所有這些個體從最佳組中移除。此外,如果第i只雞不如任何最優解,那么將其阻止到最佳組并計算其適應值:

F(x)=max[0,(F*-dmin)]

(20)

采用以上方法計算雞群每只個體適應值并評定優劣時,每只雞個體可根據該位置個體的適應值和距最優解的距離綜合考慮選擇合適的母雞與小雞,使得雞群等級配比更加合理化,有助于更準確尋找最佳解。

2.3.2 母雞的隨機游走策略

種群中的母雞是隨著公雞位置的變動而移動的。隨著迭代的進行,雞群算法尋優得到的最佳解會逐漸減小,迭代計算量的增加并不能有效提高算法的尋優精度,為此對母雞的移動采取跟隨公雞與隨機游走相結合的策略,每當母雞朝期望方向行走一段距離后,會在自身一定范圍內隨機移動以在母雞個體周圍產生新解。隨著迭代的進行,母雞對公雞的跟隨程度減弱,這時增強母雞個體的隨機游走。正常在應用母雞公式對母雞定位以后,在母雞周圍隨機搜索公式如下:

(21)

rand值在1和-1之間,在覓食的最初階段,這種隨機性可以被接受。一旦母雞接近食物,進一步修改公式增加母雞的移動能力,以展開更大范圍的局部搜索。優化后的公式如下:

xnew=xi+θ1rand(xr1-xr2)+θ2εxold

(22)

(23)

式中,r1、r2是1到NH之間的隨機數,r1≠r2。NH為母雞數量。θ1+θ2=1,θmax為1,θmin為0,Gmax為最大迭代次數,t為當前迭代次數。

2.3.3 引入凈能量增益

由于雞群中的小雞個體可以隨意偷取其他個體發現的食物,且整個雞群個體是由若干個子雞群組成的,因此很容易出現小雞偷食其他個體的食物后迷失方向、找不到自己的雞媽媽等情況而造成的搜索誤差問題。針對該問題本文修改了小雞的位置公式,在公式中引入凈能量增益系數,使小雞更容易到達理想位置。

凈能量增益的具體原理為:雞群搜索食物依照嚴格的等級制度,覓食過程中所耗費的能量較高。雖然較大的食物會提供更高能量。但可能分布稀疏或距雞群較遠,而較小的食物雖獲得的能量較少,卻可能分布較多且距離較近。小雞在搜索食物的過程中也會對能量進行取舍,即優先在本種群距離近的雞媽媽周圍搜尋能為其提供最大能量增益的食物,每當有一只小雞在此覓食,將有更多同類型的小雞被吸引過來。

Gij=|Ej-Ei|

(24)

(25)

Si,j=ri,jωkc

(26)

δij=eGi,j-eSi,j

(27)

Ei,Ej為小雞ith與jth的目標函數值。Gi,j為小雞覓食后可能獲得的能量增益。Si,j為小雞移動路徑rij所消耗的能量。ri,j是第i只小雞與第j只小雞的笛卡爾距離。而實際情況中,小雞的移動不可能是直線的,故引入變量w。kc為小雞單位距離的能量消耗。δij給出凈能量增益。引入凈能量增益的小雞位置公式如下:

(28)

2.4 基于改進雞群算法的節點定位

鑒于雞群算法優秀的尋優能力,結合上述三點定位模型,進行節點定位研究,用解決函數約束優化問題的思想確定待測節點的位置問題。然后使用雞群算法進行智能搜索來確定待測節點的確切位置。具體步驟如下:

步驟1建立第一章提到的定位模型,用雞群算法解決該模型轉化成的尋優問題。

步驟2設雞群規模N,根據pareto距離分級分配雞群比例,迭代次數Gmax和其他參數。

步驟3初始化雞群位置。

步驟4按照2.3.1節內容,將雞群比例進行劃分。

步驟5母雞和小雞按照2.3.2和2.3.3節進行局部搜索。

步驟6當所有子雞群完成指定次數的局部搜索時,重新分配個體并更新最佳個體信息。

步驟7如果滿足終止條件,則算法結束并輸出全局最佳值。該值即待測節點最優位置的近似值。否則轉到第四步,迭代次數加1。

3 算法仿真

為了驗證ICSO算法在提高定位精度方面比其他算法具有明顯的效果和優勢,選取了應用于無線傳感器網絡定位的兩種改進后的典型算法作為對比,分別是文獻[4]改進的粒子群算法(MPSO)和文獻[8]改進的雞群算法(BIDCSO)。MPSO算法首先把上一代和當代節點位置的平均值作為下一代目標節點的參考節點,再優化粒子群算法的全局最優點位置,并利用改進粒子群算法優化定位結果,提高定位精度。BIDCSO在算法初期建立定位模型,并在改進雞群算法中公雞、母雞以及小雞的搜索方式后應用于總結好的定位模型,一定程度上減小了誤差。主要比較對定位精度影響較大的定位時間、節點密度、通信半徑等因素。假設理想條件下,在正方形監測區域中,具體參數如表1所示。

表1 仿真環境參數

針對以上參數每種仿真實驗重復進行100次取平均值,再根據平均誤差對比各種定位算法的優劣,具體公式如下:

(29)

①不同性能參數比較

三種算法分別運行100次的性能參數對比如表2。

表2 MPSO、BIDCSO、ICSO算法的性能比較

由表2可見,在同等情況下與另外兩種算法相比,ICSO算法具有更小的誤差,且迭代時間更短,更容易快速、精確的定位未知節點位置,恰好體現了無線傳感器網絡高效、精確的定位特點。

②不同節點定位誤差比較

三種算法對無線傳感器網絡節點優化定位后的誤差波動曲線如圖1。

圖1 定位誤差對比圖

可以看出ICSO定位誤差明顯小于另兩種算法。且圖像波動范圍明顯較小,即在節點定位過程中節點位置的估測距離與實際距離相差更小,在復雜的網絡中ICSO算法具有更好的定位穩定性。

③參考節點比例對平均定位精度影響

隨著參考節點比例增加三種算法定位誤差變化曲線如圖2。

圖2 不同參考節點比例的定位誤差比較

總體看來,隨著參考節點比例的升高,定位效果都趨于更優。ICSO算法的定位精度較MPSO算法和BIDCSO算法分別提高了19.2%和6%。可以看出當參考節點比例從5%提升至20%的過程中,誤差降低效果最為明顯。由于優化了雞群的速度與位置更新公式,所以定位效果更優于文獻[8]改進的算法。參考節點比例逐步增大到一定比例后,三種算法的定位誤差均逐步趨于平穩。

圖3 不同節點密度的定位誤差比較

④節點密度對平均定位精度的影響

隨著節點密度增加三種算法定位誤差變化曲線如圖3。

顯而隨著節點密度變大,三種定位算法均可不同程度的減小定位誤差。ICSO算法的定位精度較MPSO算法和BIDCSO算法分別提高了22.1%和10.5%。當總節點數介于40和80之間誤差下降最為明顯。在網絡節點多的情況下,需要種群具有高效的移動性以提高尋優精度,所以本文算法較優于文獻[8]算法。但當節點總數增大到80以后定位精度并沒有大幅度提升,這是由于節點過于密集,增加了節點間不必要的通信,損耗了更多能量。所以我們應根據實際情況合理選擇節點數量。同時,可以看出,當待測區域密度較小時,ICSO算法具有明顯的優點和良好的穩定性。因此在節點密度方面改進的雞群算法可有效提高定位精度。

⑤通信半徑對平均定位精度的影響

隨著通信半徑增加三種算法定位誤差變化曲線如圖4。

圖4 不同通信半徑的定位誤差比較

根據每條曲線的趨勢,通信半徑對三種算法的節點定位誤差影響都較大。ICSO算法的定位精度較MPSO算法和BIDCSO算法分別提高了12.1%和4.4%,優勢較明顯。由于非測距算法與節點間距離無關,因此通信半徑對定位誤差影響很大,當通信半徑很小時,有效錨節點數量較少,定位效果不理想,但是本文改進的算法具有更完善的速度位置尋優公式,所以比另兩種算法在通信半徑小的條件下具有更高的精度。由此可見,該算法同樣適用于節點稀疏的環境。

⑥定位區域面積對平均定位精度的影響

隨著定位區域面積增加三種算法定位誤差變化曲線如圖5。

圖5 不同區域長度的定位誤差比較

根據圖5可以看出,待測區域面積越大,定位誤差越高。ICSO算法的定位誤差較MPSO算法和BIDCSO算法分別下降了8.5%和4.7%,在定位區域較大的環境下ICSO算法依然能保持較好的定位精度。隨著區域面積的變大,對雞群多樣性有著更高的要求,本文改進的算法相比文獻[8]的多樣性有一定程度的提高,且不易陷入局部最優,因此本文改進的算法會更好的適用于定位區域面積較大的環境。

4 結論

針對無線傳感器網絡定位誤差較大的問題,本文提出了一種將三點定位模型與改進雞群算法相結合的ICSO算法。該算法用pareto距離分級思想分配雞群比例,并引入隨機游走策略優化母雞的位置,擴大搜索范圍,再用凈能量增益改進小雞的位置,綜合提高定位精度。仿真結果顯示,本文提出的算法有效提高了節點的定位精度,且該算法迭代次數少,收斂性好,易于實現。由于本算法沒有考慮障礙物密集度較高的情況,下一步工作中將隨機設置一定數量的障礙物,使該算法應用范圍更廣。