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

0 引言

無線傳感網(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)勢。

1 節(jié)點定位問題建模

在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é)點定位問題。

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

2.1 粒子群算法(PSO)

粒子群優(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)。

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

差分進(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)秀的解。

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

在第二節(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)的位置估計。

4 仿真實驗與分析

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

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

在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。

4.2 實驗仿真分析

仿真環(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ī)模大小對定位性能的影響

5 結(jié)語

節(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算法不僅提高了定位精度而且減少了定位需要消耗的時間。