基于雞群算法的無線傳感器網(wǎng)絡(luò)定位研究*

李 鵬,陳桂芬,胡文韜

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

無線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)是當前信息科學技術(shù)領(lǐng)域研究的熱點之一,可實現(xiàn)特殊情況下信號的收集、處理和發(fā)送。由于其獨特的學科交叉性,成為了二十一世紀極具發(fā)展?jié)摿Φ年P(guān)鍵技術(shù)。無線傳感器網(wǎng)絡(luò)是僅次于互聯(lián)網(wǎng)的第二大網(wǎng)絡(luò),具有低成本、體積小、傳輸距離遠等優(yōu)勢,廣泛應(yīng)用于軍事、醫(yī)療環(huán)境監(jiān)測等方面[1]。定位技術(shù)作為無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù),在很多領(lǐng)域發(fā)揮重要作用?？梢詭椭藗儗崟r獲取所需的位置信息和實時情況,同時獲取傳感器節(jié)點的確切位置還確保了無線傳感器網(wǎng)絡(luò)后續(xù)的路由及覆蓋算法的高效執(zhí)行。因此研究無線傳感器網(wǎng)絡(luò)定位意義深遠。

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

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

1 定位節(jié)點模型的建立

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

(1)

將式(1)變?yōu)榫€性方程組,如式(2):

AX=b

(2)

其中:

(3)

(4)

(5)

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

X=(ATA)-1ATb

(6)

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

(7)

節(jié)點間的距離測量誤差公式如下:

|ri-di|<εi

(8)

εi為節(jié)點間的測距誤差。ri是網(wǎng)絡(luò)中參考節(jié)點i與未知節(jié)點的實際距離。i=1,2,…,n。即:

(9)

(10)

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

2 雞群算法

2.1 雞群算法介紹

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

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

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

(11)

(12)

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

(13)

(14)

S2=exp(fr2-fi)

(15)

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

③小雞個體的更新方式為

(16)

2.2 適應(yīng)值函數(shù)

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

(17)

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

2.3 雞群算法的改進

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

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

(18)

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

F(x)=F*+dmin

(19)

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

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

(20)

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

2.3.2 母雞的隨機游走策略

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

(21)

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

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

(22)

(23)

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

2.3.3 引入凈能量增益

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

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

Gij=|Ej-Ei|

(24)

(25)

Si,j=ri,jωkc

(26)

δij=eGi,j-eSi,j

(27)

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

(28)

2.4 基于改進雞群算法的節(jié)點定位

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

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

步驟2設(shè)雞群規(guī)模N,根據(jù)pareto距離分級分配雞群比例,迭代次數(shù)Gmax和其他參數(shù)。

步驟3初始化雞群位置。

步驟4按照2.3.1節(jié)內(nèi)容,將雞群比例進行劃分。

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

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

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

3 算法仿真

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

表1 仿真環(huán)境參數(shù)

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

(29)

①不同性能參數(shù)比較

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

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

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

②不同節(jié)點定位誤差比較

三種算法對無線傳感器網(wǎng)絡(luò)節(jié)點優(yōu)化定位后的誤差波動曲線如圖1。

圖1 定位誤差對比圖

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

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

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

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

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

圖3 不同節(jié)點密度的定位誤差比較

④節(jié)點密度對平均定位精度的影響

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

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

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

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

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

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

⑥定位區(qū)域面積對平均定位精度的影響

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

圖5 不同區(qū)域長度的定位誤差比較

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

4 結(jié)論

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