(1.浙江郵電職業(yè)技術(shù)學(xué)院,浙江 紹興 312016; 2.中國科學(xué)技術(shù)大學(xué) 軟件學(xué)院,江蘇 蘇州 215123)
無線傳感網(wǎng)絡(luò)協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中被感知對象的信息,并發(fā)送給觀察者。由于其成本低、功能多、融合多門技術(shù),被譽(yù)為21世紀(jì)最具有影響力的技術(shù)之一。其應(yīng)用包括視頻監(jiān)控、航空交通控制、機(jī)器人學(xué)、汽車、智能家居、健康檢測和工業(yè)自動化等,成本較低且實現(xiàn)簡單,因此在國內(nèi)外得到了廣泛的關(guān)注。
節(jié)點定位是無線傳感網(wǎng)絡(luò)(wireless sensor network,WSN)重要的支撐技術(shù)[1],其精確性是衡量無線傳感網(wǎng)絡(luò)性能優(yōu)劣的一個重要的標(biāo)準(zhǔn)。
根據(jù)是否需要測量距離,目前無線傳感器網(wǎng)絡(luò)節(jié)點定位算法可以分為兩種定位機(jī)制,基于測距和無需測距[2]?;跍y距的定位通過距離確定節(jié)點的位置[2],無需測距近似估計節(jié)點的位置而不用知道節(jié)點的距離和方向,顯然基于測距的定位性能高于無需測距的方法,本文主要研究基于測距技術(shù)的定位。測距定位的基本方法包括接收信號強(qiáng)度指示(received signal strength indication, RSSI)[3]、到達(dá)時間差(time difference of arrival, TDOA)[4]、到達(dá)角度(angel of arrival, AOA)[5]。其中TDOA、AOA等都需要其他硬件支持,比方說:紅外線發(fā)射器、天線陣列、超寬帶(UWB)以及脈沖器等,雖然它們的精度高于RSSI的測距方法,但同時也對硬件具有較高的要求。RSSI通過利用無線通信芯片,且不需要額外的設(shè)備,使用起來十分方便,因此其是無線傳感器網(wǎng)絡(luò)節(jié)點定位中經(jīng)常應(yīng)用的測距技術(shù),但在實際的測距過程中存在著較大誤差,通過將無線傳感器的定位問題轉(zhuǎn)換成求測距誤差最小值的優(yōu)化問題來降低誤差成為研究熱點,當(dāng)前有許多學(xué)者利用智能優(yōu)化算法來提高節(jié)點定位的精度。
于泉等人改進(jìn)粒子速度、慣性權(quán)重等,增強(qiáng)算法跳出局部最優(yōu)能力,提高迭代后期算法的搜索速度,提出利用粒子群算法(particleswarmoptimization,PSO)求解WSN定位問題[6],仿真表明該方法不僅可以提高精度而且可以提高穩(wěn)定性。張健等人[7]利用動態(tài)步長機(jī)制控制果蠅種群尋優(yōu)范圍DFOA,然后通過質(zhì)心定位得出最終結(jié)果,仿真表明該算法有較抗誤差能力。
以上算法雖然在一定程度上提升了定位性能,但是在定位精度上仍然有提升空間,研究一種性能好、效率高的智能算法至關(guān)重要,PSO和差分進(jìn)化(differentialevolution,DE)是兩種經(jīng)典的智能優(yōu)化算法,PSO模擬鳥類覓食的過程,通過不斷向種群中優(yōu)秀個體靠攏,進(jìn)而快速尋找到食物。DE模擬生物界染色體通過交叉、變異和選擇保留優(yōu)秀基因的過程。然而這兩種算法都存在一定的不足,因此本文首先改進(jìn)二種算法,然后提出混合粒子群和差分進(jìn)化的HPSO-DE算法,并和文獻(xiàn)[6]的PSO、文獻(xiàn)[7]的HBPGA等方法進(jìn)行比較,證明本文算法在定位精度和尋優(yōu)速度上的優(yōu)勢。
在WSN中,設(shè)錨節(jié)點P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)與未知節(jié)點P(x,y)之間的實際真實距離分別為r1,r2,…,rn,實際測量距離分別為d1,d2,…,dn,測距誤差分別為ε1,ε2,…,εn,則滿足|ri-di|<εi,其中i=1,2,…,n,那么未知節(jié)點P(x,y)的位置可由式(1)約束條件表示為:
(1)
解(x,y),使得:
(2)
由于測距誤差的存在,需要對第二步根據(jù)式(2)計算,其整體取得最小值的情況即坐標(biāo)(x,y)為未知點最優(yōu)解的情況。由此節(jié)點定位問題可以轉(zhuǎn)化成求式(2)所示對適應(yīng)度函數(shù)最小的多約束優(yōu)化問題。由于智能算法具有較快的尋優(yōu)速度和較高的尋優(yōu)精度,因此本文擬用智能算法求解節(jié)點定位問題。
粒子群優(yōu)化算法[8]受鳥類群體活動啟發(fā),將尋找問題最優(yōu)解的過程看作是鳥類(抽象成粒子)尋找食物的過程。具有并行性、分布式和收斂速度快等特點[8],且沒有許多參數(shù)需要進(jìn)行調(diào)整。目前,已經(jīng)廣泛應(yīng)用于工程設(shè)計、分類、模糊聚類、預(yù)測和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域。
它們根據(jù)式(3)和式(4)更新速度Vei=(vi1,vi2,…,viD)和位置Xi=(xi1,xi2,…,xiD),D是搜索空間維度,vij和xij分別表示第i個粒子第j維的速度和位置。
vid(t+1)=w·vid(t)+c1*r1*(pid(t)-
xid(t))+c2*r2*(gd(t)-xid(t))
(3)
xij(t+1)=xij(t)+vij(t)
(4)
其中:w是慣性因子,t表示第t次迭代;c1和c2是學(xué)習(xí)因子;r1和r2是2個在[0,1]上服從均勻分布的隨機(jī)變量;pi(t)=(pi1(t),pi2(t),…,piD(t))和g(t)=(g1(t),g2(t),…,gD(t))分別表示截至t代時第i個粒子搜索的局部最優(yōu)解和所有粒子搜索的全局最優(yōu)解。
在粒子群算法中,由公式(3)可以看出,粒子會向全局最優(yōu)個體和個人局部最優(yōu)個體靠攏,雖然能夠較快的獲得較優(yōu)秀的解同時也很容易陷入局部最優(yōu)。
差分進(jìn)化算法[9]在解決全局最優(yōu)解的問題上有獨(dú)特的優(yōu)點,模擬了自然過程,有著廣闊的發(fā)展前景,目前已經(jīng)廣泛應(yīng)用到工程應(yīng)用和學(xué)習(xí)研究中。它利用兩條染色體的向量差值產(chǎn)生新解,指導(dǎo)算法進(jìn)化方向,主要由變異、交叉和選擇操作構(gòu)成。
變異:在第t次迭代中,隨機(jī)選擇兩個染色體Xr2(t)和Xr3(t),將兩者的差值加到第三個隨機(jī)個體Xr1上,產(chǎn)生第i個變異個體Hi(t)。F為變異因子。
Hi(t)=Xr1(t)+F*(Xr2(t)-Xr3(t))
(5)
交叉:將Hi(t)=[hi1(t),hi2(t),…,hiD(t)]按式(6)交叉,產(chǎn)生交叉?zhèn)€體Vi(t)。其中cr為交叉概率。
(6)
選擇:選擇的目標(biāo)是第t+1代的染色體不差于t代的個體,如式(7)所示:
(7)
差分進(jìn)化算法中的變異、交叉和選擇機(jī)制保證了該算法具有較強(qiáng)的全局尋優(yōu)能力,但是這種機(jī)制是完全隨機(jī)的,因此該算法經(jīng)常需要進(jìn)化很多代才能得到較優(yōu)秀的解。
在第二節(jié)中,對PSO算法和DE算法進(jìn)行描述和分析,PSO算法具有較強(qiáng)的局部尋優(yōu)能力但是全局尋優(yōu)能力差,DE算法具有較強(qiáng)的全局尋優(yōu)能力但是局部尋優(yōu)能力差,本章將對PSO和DE算法分別改進(jìn),并結(jié)合兩者的優(yōu)勢,提出了基于節(jié)點定位的HPSO-DE算法。
在PSO算法中,慣性權(quán)重w用于平衡全局和局部搜索能力[6],式(3)所示的固定慣性權(quán)重難以獲得較好效果,因此本文提出一種隨著迭代次數(shù)自適應(yīng)變化的慣性因子,更新公式如式(8)所示。其中a、b、c和d是常數(shù)。
w=a·ebt+c·edt
(8)
這樣設(shè)計的思路是:在迭代初期和中期,應(yīng)該盡可能減小w,獲得局部最優(yōu)解,加快尋優(yōu)速度,在迭代后期,為了防止陷入局部最優(yōu),應(yīng)增大w值,跳出當(dāng)前解空間,以探索全局最優(yōu)解。
在DE算法的變異過程中,Hi(t)受Xr1(t)影響很大,算法容易陷入搜索停滯,為了解決這個問題,本文利用式(9)對其變異。
(F2-F1)(Xr1(t)-Xr2(t))+(F2-F3)(Xr3(t)-Xr2(t))+
(F1-F3)(Xr3(t)-Xr1(t))
(9)
由于粒子群算法具有較強(qiáng)的局部尋優(yōu)能力,尋優(yōu)速度快,因此先用粒子群進(jìn)行優(yōu)化,這樣可以更快速地尋找到較優(yōu)秀的解,將個體適應(yīng)度值高于種群平均適應(yīng)度閾值favg的個體(說明該個體估計的節(jié)點位置和實際節(jié)點位置誤差較大)利用DE繼續(xù)進(jìn)行進(jìn)化,從而使得陷入局部最優(yōu)的這些個體盡快跳出當(dāng)前區(qū)域,去更大的空間尋找優(yōu)秀的解。由此得到本文節(jié)點定位的HPSO-DE算法。主要步驟如下:
1)初始化:設(shè)置種群NP的規(guī)模N,迭代總次數(shù)I,設(shè)置當(dāng)前迭代次數(shù)t=1,對種群中每個個體的位置Xi(1)和速度Vei(1)隨機(jī)初始化。
2)適應(yīng)度值更新:利用式(2)求每個粒子的適應(yīng)度值f(Xi(t))。
3)種群更新:利用式(8)計算w,然后帶入到式(3)更新粒子速度,利用式(4)更新粒子位置。計算閾值favg。
4)種群分級:若f(Xi(t))≤favg,將Xi(t)加入高級群NPsup中,否則加入劣等群NPwor。
5)劣解更新:將NPwor中的劣質(zhì)個體利用公式(9)、(6)和(7)進(jìn)行變異、交叉和選擇。
6)將經(jīng)過DE更新后的劣解NPwor和NPsup合并為NP,并確定種群最優(yōu)個體g(t)。
7)判斷t是否滿足終止條件,如果是轉(zhuǎn)(8),否則轉(zhuǎn)(2)。
8)輸出種群最優(yōu)個體g(t),作為對未知節(jié)點P(x,y)的位置估計。
本節(jié)分析提出的HPSO-DE算法的節(jié)點定位性能,并和文獻(xiàn)[6]的PSO算法、文獻(xiàn)[7]的DFOA算法進(jìn)行對比分析。
在PSO算法中,參考[6]設(shè)置學(xué)習(xí)因子c1=c2=1.4945,在DFOA算法中,參考[7],設(shè)置搜索步長radiusX為0.1,本文HPSO-DE算法中,設(shè)置常數(shù)a=0.445,b=d=-8.5E-06,c=0.13,交叉概率cr=0.6。3種算法中設(shè)置種群規(guī)模大小為30,最大迭代次數(shù)設(shè)置為80。
仿真環(huán)境參數(shù)設(shè)置參考文獻(xiàn)[10],設(shè)置節(jié)點通信半徑為10 m,在30 m×30 m的仿真環(huán)境中,隨機(jī)分布30個傳感器。
WSN節(jié)點定位性能評價標(biāo)準(zhǔn)[11]主要有定位精度、規(guī)模、錨節(jié)點密度、節(jié)點密度、容錯性和自適應(yīng)性、功耗和代價等7種。定位精度即定位精確度,細(xì)分為絕對精度和相對精度;規(guī)模即定位的范圍;錨節(jié)點的成本較高,且當(dāng)其密度達(dá)到一定值后,定位精度不再隨之增加;節(jié)點密度用網(wǎng)絡(luò)的平均連通度來表示;容錯性和自適應(yīng)性較強(qiáng)即故障處理能力較強(qiáng),能夠減小各種誤差帶來的影響;功耗即各個傳感器節(jié)點上的電池能量消耗,與其關(guān)系比較密切的有計算量、時間復(fù)雜性和通信開銷等;代價包括時間代價與空間代價。
本文參考文獻(xiàn)[12]和[13]以平均定位誤差(averagelocationerror,AVE)為評價標(biāo)準(zhǔn)。其公式如式(10)所示:
(10)
式中,M為已知節(jié)點的總個數(shù),(x,y)為預(yù)測位置,(xi,yi)為實際位置。
圖1給出了在錨節(jié)點為10個時,3種算法的平均定位誤差與測距誤差的關(guān)系,圖中每個數(shù)據(jù)都是20次仿真結(jié)果的平均。由圖可知:(1)隨著測距誤差的減小,3種算法的平均定位誤差也在減小,說明3種智能優(yōu)化算法的有效性;(2)在測距誤差較小,即0~5%時,BA、CBA和HM-BA的平均定位誤差幾乎接近于0,3種方法均能達(dá)到較高的定位精度,但相比較而言,HM-BA的定位精度更高。但當(dāng)定位誤差不斷增大,尤其是在15%~30%時,3種方法的差距明顯變大,體現(xiàn)出了HM-BA在定位精度上的優(yōu)勢;(3)本文在改進(jìn)粒子群和差分進(jìn)化算法的同時,又結(jié)合兩者的優(yōu)勢,使得HPSO-DE算法定位性能最好,在測距誤差為30%時,HPSO-DE的定位誤差比PSO和DFOA分別少2.1 m和1.1 m;(4)當(dāng)定位誤差不斷增大,尤其是在15%~30%時,3種方法的差距明顯變大,相對來說HPSO-DE的誤差增長的較為緩慢,體現(xiàn)出了HPSO-DE算法在定位精度上的優(yōu)勢。
圖1 測距誤差對定位性能的影響
圖2給出了在定位誤差為10%時,3種算法的平均定位誤差與錨節(jié)點個數(shù)的關(guān)系。由圖可知,3種算法的平均定位誤差隨著錨節(jié)點個數(shù)的增加而減小,說明3種智能優(yōu)化算法均能適應(yīng)于節(jié)點定位中,同時本文在達(dá)到相同的定位誤差時需要最少的錨節(jié)點,例如當(dāng)定位誤差為1.5 m時,HPSO-DE、PSO和DFOA算法需要的錨節(jié)點分別為3、5和7個。這意味著本算法僅需要較小的硬件成本就能實現(xiàn)較高精度的定位。
圖2 錨節(jié)點個數(shù)對定位性能的影響
圖3給出了在定位誤差為10%,錨節(jié)點個數(shù)為10個時,3種算法的平均定位誤差與迭代次數(shù)的關(guān)系。由圖可以看出,隨著迭代次數(shù)的增加,更優(yōu)的位置被發(fā)現(xiàn),因此3種算法的定位誤差都在逐漸減小,HPSO-DE、PSO和DFOA算法在達(dá)到穩(wěn)定時需要的迭代次數(shù)依次為20、20和47次。PSO算法雖然尋優(yōu)速度快,但是很快陷入局部最優(yōu),因此平均定位誤差較大,而HPSO-DE算法結(jié)合了PSO的局部尋優(yōu)能力強(qiáng)和DE的全局探索能力高的優(yōu)勢,在保持較快尋優(yōu)性能的同時具有最小的定位誤差。
圖3 種群規(guī)模大小對定位性能的影響
節(jié)點定位是無線傳感網(wǎng)絡(luò)重要的支撐技術(shù),針對由測量誤差造成的無線傳感器網(wǎng)絡(luò)節(jié)點定位精度不高的問題,本文首先改進(jìn)粒子群算法的固定慣性權(quán)重為自適應(yīng)慣性權(quán)重,增強(qiáng)了粒子群算法的全局搜索能力,然后改進(jìn)差分進(jìn)化算法的變異策略,增強(qiáng)DE算法的局部尋優(yōu)能力,然后將經(jīng)過粒子群優(yōu)化后的較差個體繼續(xù)通過差分進(jìn)化算法優(yōu)化,得到混合粒子群與差分進(jìn)化的HPSO-DE算法,仿真實驗表明,HPSO-DE算法不僅提高了定位精度而且減少了定位需要消耗的時間。