混合粒子群和差分進(jìn)化的定位算法

(1.浙江郵電職業(yè)技術(shù)學(xué)院，浙江 紹興 312016; 2.中國(guó)科學(xué)技術(shù)大學(xué) 軟件學(xué)院，江蘇 蘇州 215123)

0 引言

無(wú)線傳感網(wǎng)絡(luò)協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中被感知對(duì)象的信息，并發(fā)送給觀察者。由于其成本低、功能多、融合多門(mén)技術(shù)，被譽(yù)為21世紀(jì)最具有影響力的技術(shù)之一。其應(yīng)用包括視頻監(jiān)控、航空交通控制、機(jī)器人學(xué)、汽車(chē)、智能家居、健康檢測(cè)和工業(yè)自動(dòng)化等，成本較低且實(shí)現(xiàn)簡(jiǎn)單，因此在國(guó)內(nèi)外得到了廣泛的關(guān)注。

節(jié)點(diǎn)定位是無(wú)線傳感網(wǎng)絡(luò)(wireless sensor network，WSN)重要的支撐技術(shù)[1]，其精確性是衡量無(wú)線傳感網(wǎng)絡(luò)性能優(yōu)劣的一個(gè)重要的標(biāo)準(zhǔn)。

根據(jù)是否需要測(cè)量距離，目前無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法可以分為兩種定位機(jī)制，基于測(cè)距和無(wú)需測(cè)距[2]?；跍y(cè)距的定位通過(guò)距離確定節(jié)點(diǎn)的位置[2]，無(wú)需測(cè)距近似估計(jì)節(jié)點(diǎn)的位置而不用知道節(jié)點(diǎn)的距離和方向，顯然基于測(cè)距的定位性能高于無(wú)需測(cè)距的方法，本文主要研究基于測(cè)距技術(shù)的定位。測(cè)距定位的基本方法包括接收信號(hào)強(qiáng)度指示(received signal strength indication, RSSI)[3]、到達(dá)時(shí)間差(time difference of arrival, TDOA)[4]、到達(dá)角度(angel of arrival, AOA)[5]。其中TDOA、AOA等都需要其他硬件支持，比方說(shuō)：紅外線發(fā)射器、天線陣列、超寬帶(UWB)以及脈沖器等，雖然它們的精度高于RSSI的測(cè)距方法，但同時(shí)也對(duì)硬件具有較高的要求。RSSI通過(guò)利用無(wú)線通信芯片，且不需要額外的設(shè)備，使用起來(lái)十分方便，因此其是無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中經(jīng)常應(yīng)用的測(cè)距技術(shù)，但在實(shí)際的測(cè)距過(guò)程中存在著較大誤差，通過(guò)將無(wú)線傳感器的定位問(wèn)題轉(zhuǎn)換成求測(cè)距誤差最小值的優(yōu)化問(wèn)題來(lái)降低誤差成為研究熱點(diǎn)，當(dāng)前有許多學(xué)者利用智能優(yōu)化算法來(lái)提高節(jié)點(diǎn)定位的精度。

于泉等人改進(jìn)粒子速度、慣性權(quán)重等，增強(qiáng)算法跳出局部最優(yōu)能力，提高迭代后期算法的搜索速度，提出利用粒子群算法(particleswarmoptimization，PSO)求解WSN定位問(wèn)題[6]，仿真表明該方法不僅可以提高精度而且可以提高穩(wěn)定性。張健等人[7]利用動(dòng)態(tài)步長(zhǎng)機(jī)制控制果蠅種群尋優(yōu)范圍DFOA，然后通過(guò)質(zhì)心定位得出最終結(jié)果，仿真表明該算法有較抗誤差能力。

以上算法雖然在一定程度上提升了定位性能，但是在定位精度上仍然有提升空間，研究一種性能好、效率高的智能算法至關(guān)重要，PSO和差分進(jìn)化(differentialevolution，DE)是兩種經(jīng)典的智能優(yōu)化算法，PSO模擬鳥(niǎo)類(lèi)覓食的過(guò)程，通過(guò)不斷向種群中優(yōu)秀個(gè)體靠攏，進(jìn)而快速尋找到食物。DE模擬生物界染色體通過(guò)交叉、變異和選擇保留優(yōu)秀基因的過(guò)程。然而這兩種算法都存在一定的不足，因此本文首先改進(jìn)二種算法，然后提出混合粒子群和差分進(jìn)化的HPSO-DE算法，并和文獻(xiàn)[6]的PSO、文獻(xiàn)[7]的HBPGA等方法進(jìn)行比較，證明本文算法在定位精度和尋優(yōu)速度上的優(yōu)勢(shì)。

1 節(jié)點(diǎn)定位問(wèn)題建模

在WSN中，設(shè)錨節(jié)點(diǎn)P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)與未知節(jié)點(diǎn)P(x,y)之間的實(shí)際真實(shí)距離分別為r1,r2,…,rn，實(shí)際測(cè)量距離分別為d1,d2,…,dn，測(cè)距誤差分別為ε1,ε2,…,εn，則滿足|ri-di|<εi，其中i=1,2,…,n，那么未知節(jié)點(diǎn)P(x,y)的位置可由式(1)約束條件表示為：

(1)

解(x,y)，使得：

(2)

由于測(cè)距誤差的存在，需要對(duì)第二步根據(jù)式(2)計(jì)算，其整體取得最小值的情況即坐標(biāo)(x,y)為未知點(diǎn)最優(yōu)解的情況。由此節(jié)點(diǎn)定位問(wèn)題可以轉(zhuǎn)化成求式(2)所示對(duì)適應(yīng)度函數(shù)最小的多約束優(yōu)化問(wèn)題。由于智能算法具有較快的尋優(yōu)速度和較高的尋優(yōu)精度，因此本文擬用智能算法求解節(jié)點(diǎn)定位問(wèn)題。

2 粒子群算法及差分進(jìn)化算法

2.1 粒子群算法(PSO)

粒子群優(yōu)化算法[8]受鳥(niǎo)類(lèi)群體活動(dòng)啟發(fā)，將尋找問(wèn)題最優(yōu)解的過(guò)程看作是鳥(niǎo)類(lèi)(抽象成粒子)尋找食物的過(guò)程。具有并行性、分布式和收斂速度快等特點(diǎn)[8]，且沒(méi)有許多參數(shù)需要進(jìn)行調(diào)整。目前，已經(jīng)廣泛應(yīng)用于工程設(shè)計(jì)、分類(lèi)、模糊聚類(lèi)、預(yù)測(cè)和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域。

它們根據(jù)式(3)和式(4)更新速度Vei=(vi1,vi2,…,viD)和位置Xi=(xi1,xi2,…,xiD)，D是搜索空間維度，vij和xij分別表示第i個(gè)粒子第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個(gè)在[0,1]上服從均勻分布的隨機(jī)變量；pi(t)=(pi1(t),pi2(t),…,piD(t))和g(t)=(g1(t),g2(t),…,gD(t))分別表示截至t代時(shí)第i個(gè)粒子搜索的局部最優(yōu)解和所有粒子搜索的全局最優(yōu)解。

在粒子群算法中，由公式(3)可以看出，粒子會(huì)向全局最優(yōu)個(gè)體和個(gè)人局部最優(yōu)個(gè)體靠攏，雖然能夠較快的獲得較優(yōu)秀的解同時(shí)也很容易陷入局部最優(yōu)。

2.2 差分進(jìn)化算法(DE)

差分進(jìn)化算法[9]在解決全局最優(yōu)解的問(wèn)題上有獨(dú)特的優(yōu)點(diǎn)，模擬了自然過(guò)程，有著廣闊的發(fā)展前景，目前已經(jīng)廣泛應(yīng)用到工程應(yīng)用和學(xué)習(xí)研究中。它利用兩條染色體的向量差值產(chǎn)生新解，指導(dǎo)算法進(jìn)化方向，主要由變異、交叉和選擇操作構(gòu)成。

變異：在第t次迭代中，隨機(jī)選擇兩個(gè)染色體Xr2(t)和Xr3(t)，將兩者的差值加到第三個(gè)隨機(jī)個(gè)體Xr1上，產(chǎn)生第i個(gè)變異個(gè)體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代的個(gè)體，如式(7)所示:

(7)

差分進(jìn)化算法中的變異、交叉和選擇機(jī)制保證了該算法具有較強(qiáng)的全局尋優(yōu)能力，但是這種機(jī)制是完全隨機(jī)的，因此該算法經(jīng)常需要進(jìn)化很多代才能得到較優(yōu)秀的解。

3 節(jié)點(diǎn)定位的HPSO-DE算法

在第二節(jié)中，對(duì)PSO算法和DE算法進(jìn)行描述和分析，PSO算法具有較強(qiáng)的局部尋優(yōu)能力但是全局尋優(yōu)能力差，DE算法具有較強(qiáng)的全局尋優(yōu)能力但是局部尋優(yōu)能力差，本章將對(duì)PSO和DE算法分別改進(jìn)，并結(jié)合兩者的優(yōu)勢(shì)，提出了基于節(jié)點(diǎn)定位的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è)計(jì)的思路是：在迭代初期和中期，應(yīng)該盡可能減小w，獲得局部最優(yōu)解，加快尋優(yōu)速度，在迭代后期，為了防止陷入局部最優(yōu)，應(yīng)增大w值，跳出當(dāng)前解空間，以探索全局最優(yōu)解。

在DE算法的變異過(guò)程中，Hi(t)受Xr1(t)影響很大，算法容易陷入搜索停滯，為了解決這個(gè)問(wèn)題，本文利用式(9)對(duì)其變異。

(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)秀的解，將個(gè)體適應(yīng)度值高于種群平均適應(yīng)度閾值favg的個(gè)體(說(shuō)明該個(gè)體估計(jì)的節(jié)點(diǎn)位置和實(shí)際節(jié)點(diǎn)位置誤差較大)利用DE繼續(xù)進(jìn)行進(jìn)化，從而使得陷入局部最優(yōu)的這些個(gè)體盡快跳出當(dāng)前區(qū)域，去更大的空間尋找優(yōu)秀的解。由此得到本文節(jié)點(diǎn)定位的HPSO-DE算法。主要步驟如下：

1)初始化：設(shè)置種群NP的規(guī)模N，迭代總次數(shù)I，設(shè)置當(dāng)前迭代次數(shù)t=1，對(duì)種群中每個(gè)個(gè)體的位置Xi(1)和速度Vei(1)隨機(jī)初始化。

2)適應(yīng)度值更新：利用式(2)求每個(gè)粒子的適應(yīng)度值f(Xi(t))。

3)種群更新：利用式(8)計(jì)算w，然后帶入到式(3)更新粒子速度，利用式(4)更新粒子位置。計(jì)算閾值favg。

4)種群分級(jí)：若f(Xi(t))≤favg，將Xi(t)加入高級(jí)群NPsup中，否則加入劣等群NPwor。

5)劣解更新：將NPwor中的劣質(zhì)個(gè)體利用公式(9)、(6)和(7)進(jìn)行變異、交叉和選擇。

6)將經(jīng)過(guò)DE更新后的劣解NPwor和NPsup合并為NP，并確定種群最優(yōu)個(gè)體g(t)。

7)判斷t是否滿足終止條件，如果是轉(zhuǎn)(8)，否則轉(zhuǎn)(2)。

8)輸出種群最優(yōu)個(gè)體g(t)，作為對(duì)未知節(jié)點(diǎn)P(x,y)的位置估計(jì)。

4 仿真實(shí)驗(yàn)與分析

本節(jié)分析提出的HPSO-DE算法的節(jié)點(diǎn)定位性能，并和文獻(xiàn)[6]的PSO算法、文獻(xiàn)[7]的DFOA算法進(jìn)行對(duì)比分析。

4.1 算法參數(shù)設(shè)置

在PSO算法中，參考[6]設(shè)置學(xué)習(xí)因子c1=c2=1.4945，在DFOA算法中，參考[7],設(shè)置搜索步長(zhǎng)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。

4.2 實(shí)驗(yàn)仿真分析

仿真環(huán)境參數(shù)設(shè)置參考文獻(xiàn)[10]，設(shè)置節(jié)點(diǎn)通信半徑為10 m，在30 m×30 m的仿真環(huán)境中，隨機(jī)分布30個(gè)傳感器。

WSN節(jié)點(diǎn)定位性能評(píng)價(jià)標(biāo)準(zhǔn)[11]主要有定位精度、規(guī)模、錨節(jié)點(diǎn)密度、節(jié)點(diǎn)密度、容錯(cuò)性和自適應(yīng)性、功耗和代價(jià)等7種。定位精度即定位精確度，細(xì)分為絕對(duì)精度和相對(duì)精度；規(guī)模即定位的范圍；錨節(jié)點(diǎn)的成本較高，且當(dāng)其密度達(dá)到一定值后，定位精度不再隨之增加；節(jié)點(diǎn)密度用網(wǎng)絡(luò)的平均連通度來(lái)表示；容錯(cuò)性和自適應(yīng)性較強(qiáng)即故障處理能力較強(qiáng)，能夠減小各種誤差帶來(lái)的影響；功耗即各個(gè)傳感器節(jié)點(diǎn)上的電池能量消耗，與其關(guān)系比較密切的有計(jì)算量、時(shí)間復(fù)雜性和通信開(kāi)銷(xiāo)等；代價(jià)包括時(shí)間代價(jià)與空間代價(jià)。

本文參考文獻(xiàn)[12]和[13]以平均定位誤差(averagelocationerror，AVE)為評(píng)價(jià)標(biāo)準(zhǔn)。其公式如式(10)所示：

(10)

式中，M為已知節(jié)點(diǎn)的總個(gè)數(shù)，(x,y)為預(yù)測(cè)位置，(xi,yi)為實(shí)際位置。

圖1給出了在錨節(jié)點(diǎn)為10個(gè)時(shí)，3種算法的平均定位誤差與測(cè)距誤差的關(guān)系，圖中每個(gè)數(shù)據(jù)都是20次仿真結(jié)果的平均。由圖可知：(1)隨著測(cè)距誤差的減小，3種算法的平均定位誤差也在減小，說(shuō)明3種智能優(yōu)化算法的有效性；(2)在測(cè)距誤差較小，即0～5%時(shí)，BA、CBA和HM-BA的平均定位誤差幾乎接近于0，3種方法均能達(dá)到較高的定位精度，但相比較而言，HM-BA的定位精度更高。但當(dāng)定位誤差不斷增大，尤其是在15%～30%時(shí)，3種方法的差距明顯變大，體現(xiàn)出了HM-BA在定位精度上的優(yōu)勢(shì);(3)本文在改進(jìn)粒子群和差分進(jìn)化算法的同時(shí)，又結(jié)合兩者的優(yōu)勢(shì)，使得HPSO-DE算法定位性能最好，在測(cè)距誤差為30%時(shí)，HPSO-DE的定位誤差比PSO和DFOA分別少2.1 m和1.1 m；(4)當(dāng)定位誤差不斷增大，尤其是在15%～30%時(shí)，3種方法的差距明顯變大，相對(duì)來(lái)說(shuō)HPSO-DE的誤差增長(zhǎng)的較為緩慢，體現(xiàn)出了HPSO-DE算法在定位精度上的優(yōu)勢(shì)。

圖1 測(cè)距誤差對(duì)定位性能的影響

圖2給出了在定位誤差為10%時(shí)，3種算法的平均定位誤差與錨節(jié)點(diǎn)個(gè)數(shù)的關(guān)系。由圖可知，3種算法的平均定位誤差隨著錨節(jié)點(diǎn)個(gè)數(shù)的增加而減小，說(shuō)明3種智能優(yōu)化算法均能適應(yīng)于節(jié)點(diǎn)定位中，同時(shí)本文在達(dá)到相同的定位誤差時(shí)需要最少的錨節(jié)點(diǎn)，例如當(dāng)定位誤差為1.5 m時(shí)，HPSO-DE、PSO和DFOA算法需要的錨節(jié)點(diǎn)分別為3、5和7個(gè)。這意味著本算法僅需要較小的硬件成本就能實(shí)現(xiàn)較高精度的定位。

圖2 錨節(jié)點(diǎn)個(gè)數(shù)對(duì)定位性能的影響

圖3給出了在定位誤差為10%，錨節(jié)點(diǎn)個(gè)數(shù)為10個(gè)時(shí)，3種算法的平均定位誤差與迭代次數(shù)的關(guān)系。由圖可以看出，隨著迭代次數(shù)的增加，更優(yōu)的位置被發(fā)現(xiàn)，因此3種算法的定位誤差都在逐漸減小，HPSO-DE、PSO和DFOA算法在達(dá)到穩(wěn)定時(shí)需要的迭代次數(shù)依次為20、20和47次。PSO算法雖然尋優(yōu)速度快，但是很快陷入局部最優(yōu)，因此平均定位誤差較大，而HPSO-DE算法結(jié)合了PSO的局部尋優(yōu)能力強(qiáng)和DE的全局探索能力高的優(yōu)勢(shì)，在保持較快尋優(yōu)性能的同時(shí)具有最小的定位誤差。

圖3 種群規(guī)模大小對(duì)定位性能的影響

5 結(jié)語(yǔ)

節(jié)點(diǎn)定位是無(wú)線傳感網(wǎng)絡(luò)重要的支撐技術(shù),針對(duì)由測(cè)量誤差造成的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位精度不高的問(wèn)題，本文首先改進(jìn)粒子群算法的固定慣性權(quán)重為自適應(yīng)慣性權(quán)重，增強(qiáng)了粒子群算法的全局搜索能力，然后改進(jìn)差分進(jìn)化算法的變異策略，增強(qiáng)DE算法的局部尋優(yōu)能力，然后將經(jīng)過(guò)粒子群優(yōu)化后的較差個(gè)體繼續(xù)通過(guò)差分進(jìn)化算法優(yōu)化，得到混合粒子群與差分進(jìn)化的HPSO-DE算法，仿真實(shí)驗(yàn)表明，HPSO-DE算法不僅提高了定位精度而且減少了定位需要消耗的時(shí)間。