混合粒子群和差分進化的定位算法

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

0 引言

無線傳感網絡協作地感知、采集和處理網絡覆蓋區域中被感知對象的信息，并發送給觀察者。由于其成本低、功能多、融合多門技術，被譽為21世紀最具有影響力的技術之一。其應用包括視頻監控、航空交通控制、機器人學、汽車、智能家居、健康檢測和工業自動化等，成本較低且實現簡單，因此在國內外得到了廣泛的關注。

節點定位是無線傳感網絡(wireless sensor network，WSN)重要的支撐技術[1]，其精確性是衡量無線傳感網絡性能優劣的一個重要的標準。

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

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

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

1 節點定位問題建模

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

(1)

解(x,y)，使得：

(2)

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

2 粒子群算法及差分進化算法

2.1 粒子群算法(PSO)

粒子群優化算法[8]受鳥類群體活動啟發，將尋找問題最優解的過程看作是鳥類(抽象成粒子)尋找食物的過程。具有并行性、分布式和收斂速度快等特點[8]，且沒有許多參數需要進行調整。目前，已經廣泛應用于工程設計、分類、模糊聚類、預測和神經網絡等領域。

它們根據式(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是學習因子；r1和r2是2個在[0,1]上服從均勻分布的隨機變量；pi(t)=(pi1(t),pi2(t),…,piD(t))和g(t)=(g1(t),g2(t),…,gD(t))分別表示截至t代時第i個粒子搜索的局部最優解和所有粒子搜索的全局最優解。

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

2.2 差分進化算法(DE)

差分進化算法[9]在解決全局最優解的問題上有獨特的優點，模擬了自然過程，有著廣闊的發展前景，目前已經廣泛應用到工程應用和學習研究中。它利用兩條染色體的向量差值產生新解，指導算法進化方向，主要由變異、交叉和選擇操作構成。

變異：在第t次迭代中，隨機選擇兩個染色體Xr2(t)和Xr3(t)，將兩者的差值加到第三個隨機個體Xr1上，產生第i個變異個體Hi(t)。F為變異因子。

Hi(t)=Xr1(t)+F*(Xr2(t)-Xr3(t))

(5)

交叉：將Hi(t)=[hi1(t),hi2(t),…,hiD(t)]按式(6)交叉，產生交叉個體Vi(t)。其中cr為交叉概率。

(6)

選擇：選擇的目標是第t+1代的染色體不差于t代的個體，如式(7)所示:

(7)

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

3 節點定位的HPSO-DE算法

在第二節中，對PSO算法和DE算法進行描述和分析，PSO算法具有較強的局部尋優能力但是全局尋優能力差，DE算法具有較強的全局尋優能力但是局部尋優能力差，本章將對PSO和DE算法分別改進，并結合兩者的優勢，提出了基于節點定位的HPSO-DE算法。

在PSO算法中，慣性權重w用于平衡全局和局部搜索能力[6]，式(3)所示的固定慣性權重難以獲得較好效果，因此本文提出一種隨著迭代次數自適應變化的慣性因子,更新公式如式(8)所示。其中a、b、c和d是常數。

w=a·ebt+c·edt

(8)

這樣設計的思路是：在迭代初期和中期，應該盡可能減小w，獲得局部最優解，加快尋優速度，在迭代后期，為了防止陷入局部最優，應增大w值，跳出當前解空間，以探索全局最優解。

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

由于粒子群算法具有較強的局部尋優能力，尋優速度快，因此先用粒子群進行優化，這樣可以更快速地尋找到較優秀的解，將個體適應度值高于種群平均適應度閾值favg的個體(說明該個體估計的節點位置和實際節點位置誤差較大)利用DE繼續進行進化，從而使得陷入局部最優的這些個體盡快跳出當前區域，去更大的空間尋找優秀的解。由此得到本文節點定位的HPSO-DE算法。主要步驟如下：

1)初始化：設置種群NP的規模N，迭代總次數I，設置當前迭代次數t=1，對種群中每個個體的位置Xi(1)和速度Vei(1)隨機初始化。

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

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

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

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

6)將經過DE更新后的劣解NPwor和NPsup合并為NP，并確定種群最優個體g(t)。

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

8)輸出種群最優個體g(t)，作為對未知節點P(x,y)的位置估計。

4 仿真實驗與分析

本節分析提出的HPSO-DE算法的節點定位性能，并和文獻[6]的PSO算法、文獻[7]的DFOA算法進行對比分析。

4.1 算法參數設置

在PSO算法中，參考[6]設置學習因子c1=c2=1.4945，在DFOA算法中，參考[7],設置搜索步長radiusX為0.1，本文HPSO-DE算法中，設置常數a=0.445，b=d=-8.5E-06,c=0.13，交叉概率cr=0.6。3種算法中設置種群規模大小為30，最大迭代次數設置為80。

4.2 實驗仿真分析

仿真環境參數設置參考文獻[10]，設置節點通信半徑為10 m，在30 m×30 m的仿真環境中，隨機分布30個傳感器。

WSN節點定位性能評價標準[11]主要有定位精度、規模、錨節點密度、節點密度、容錯性和自適應性、功耗和代價等7種。定位精度即定位精確度，細分為絕對精度和相對精度；規模即定位的范圍；錨節點的成本較高，且當其密度達到一定值后，定位精度不再隨之增加；節點密度用網絡的平均連通度來表示；容錯性和自適應性較強即故障處理能力較強，能夠減小各種誤差帶來的影響；功耗即各個傳感器節點上的電池能量消耗，與其關系比較密切的有計算量、時間復雜性和通信開銷等；代價包括時間代價與空間代價。

本文參考文獻[12]和[13]以平均定位誤差(averagelocationerror，AVE)為評價標準。其公式如式(10)所示：

(10)

式中，M為已知節點的總個數，(x,y)為預測位置，(xi,yi)為實際位置。

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

圖1 測距誤差對定位性能的影響

圖2給出了在定位誤差為10%時，3種算法的平均定位誤差與錨節點個數的關系。由圖可知，3種算法的平均定位誤差隨著錨節點個數的增加而減小，說明3種智能優化算法均能適應于節點定位中，同時本文在達到相同的定位誤差時需要最少的錨節點，例如當定位誤差為1.5 m時，HPSO-DE、PSO和DFOA算法需要的錨節點分別為3、5和7個。這意味著本算法僅需要較小的硬件成本就能實現較高精度的定位。

圖2 錨節點個數對定位性能的影響

圖3給出了在定位誤差為10%，錨節點個數為10個時，3種算法的平均定位誤差與迭代次數的關系。由圖可以看出，隨著迭代次數的增加，更優的位置被發現，因此3種算法的定位誤差都在逐漸減小，HPSO-DE、PSO和DFOA算法在達到穩定時需要的迭代次數依次為20、20和47次。PSO算法雖然尋優速度快，但是很快陷入局部最優，因此平均定位誤差較大，而HPSO-DE算法結合了PSO的局部尋優能力強和DE的全局探索能力高的優勢，在保持較快尋優性能的同時具有最小的定位誤差。

圖3 種群規模大小對定位性能的影響

5 結語

節點定位是無線傳感網絡重要的支撐技術,針對由測量誤差造成的無線傳感器網絡節點定位精度不高的問題，本文首先改進粒子群算法的固定慣性權重為自適應慣性權重，增強了粒子群算法的全局搜索能力，然后改進差分進化算法的變異策略，增強DE算法的局部尋優能力，然后將經過粒子群優化后的較差個體繼續通過差分進化算法優化，得到混合粒子群與差分進化的HPSO-DE算法，仿真實驗表明，HPSO-DE算法不僅提高了定位精度而且減少了定位需要消耗的時間。