利用AHS-RW雙策略優化的節點定位算法

吳 斌，張 煜

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

0 引 言

近來，由于微機電技術、微處理器技術、通信技術以及操作系統的飛快發展，無線傳感器（Wireless Sensor Network，WSN）技術也取得了巨大進步[1]。WSN網絡需要眾多其他技術的支撐，節點定位便是其中一項關鍵的技術。目前，總體上可將定位算法歸為基于測距的定位算法和無需測距的定位算法兩類[2]。基于測距的算法有較高的定位精度，但是功耗高，難以適應野外無源場景；無需測距的算法具有較少的硬件設備和計算量，功耗低，但是定位誤差較大，因此，眾多專家學者提出利用智能優化算法提高其定位精度[3-7]，將節點定位問題轉換成利用智能優化算法求測距誤差最小的優化問題。

LI PAN等人提出一種混合粒子群和變領域搜索的SNPSO算法，每次迭代中對粒子的速度和位置更新，再利用變鄰域搜索增加算法探索的深度和廣度，實驗結果顯示該方法可以有效提高定位精度。ZHOU F[4]等人設計一種修正粒子群定位算法，通過更新個體的慣性權重和加速度系數來平衡算法局部開采和全局搜索能力。盡管以上兩種算法定位誤差小，但是時間復雜度高，ZHANG等人[5]嘗試將差分進化算法應用于定位場景中，證明其有效性，但是定位精度不高。閆俊伢[6]等人把多徑距離和節點位置作為神經網絡的輸入，訓練該網絡得到網絡模型，不僅減小了定位誤差而且增強了網絡的魯棒性，但是該方法需要大量的訓練集。肖曉麗[7]等人提出一種基于布谷鳥搜索的算法，在不同實驗場景下的仿真結果表明該算法的全局和局部搜索能力強，但是無法保證該算法的穩定性。

針對以上問題，為了兼顧節點定位的精度和定位速度，提出一種融合隨機行走和自適應更新雙策略的和聲搜索算法AHS-RW，并和文獻[3]的SNPSO算法和文獻[8]的IHS算法進行實驗對比，分析算法定位性能。

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)的約束條件為：

解 (x,y)，使得：

由于測距誤差客觀存在，因此求未知節點的坐標就轉化成求式（2）所示的函數值最小的優化問題。得益于智能優化算法的快速尋優和收斂的特性，本文將AHS-RW算法應用于該多約束優化問題中，將式（2）作為適應度評判函數，將使式（2）最小即測距誤差最小的點P(x,y)作為對未知節點的坐標估計。

2 基于AHS-RW雙策略優化的節點定位算法

2.1 標準和聲搜索（HS）算法

和聲搜索算法是GEEM等人受調音師調音過程的啟發而提出的一種新型啟發式算法[9]，它依照概率將和聲從空間中取出，經過微調后形成一首美妙的歌曲。該算法具有魯棒性強和有效性高的優點，其基本實現步驟如下：

（1）初始化目標函數和HS算法參數。目標函數是需要解決的優化問題，HS算法參數包括和聲空間HM、和聲空間大小HMS，空間選中概率HMCR、音調調整概率PAR，微調帶寬BW以及迭代次數I等。

（2）初始化和聲記憶空間HM。HM矩陣由服從[0，1]均勻隨機生成的解向量X1,X2,…,XHMS填充。

（3）從HM中創作新和聲Xnew，首先產生一個[0，1]上的隨機數r1，若r1＜HMCR，則從空間中隨機選擇一個和聲并以PAR概率按照式（3）進行微調。否則，隨機生成一個解向量作為Xnew。

（4）更新和聲空間，計算Xnew的適應度值f(Xnew)，與和聲空間中最差的和聲Xworse比較，若f(Xnew)優于f(Xworse)，則用Xnew取代Xworse。

（5）判斷算法是否滿足終止條件。若滿足終止條件，則終止運算并輸出結果，否則重復執行步驟（3）和步驟（4）。

2.2 雙策略優化的AHS-RW算法

2.2.1 基于和聲空間相似度的動態PAR更新策略

由于HS算法中的音調調整概率PAR控制了算法的收斂速度和微調能力[10]，而標準HS算法中PAR設定為常數，導致尋優結果不理想，因此很多文獻[11-13]提出了動態更新PAR值的措施。本文設計一種根據和聲空間維度多樣性動態更新PAR值的方法。

首先定義和聲空間中第i個和聲第d維的多樣性為：

式中：表示HMS個和聲第d維的平均值。之后PAR的更新公式如式（5）所示，其圖像如圖1所示。

圖1 PAR與H（d）關系

當和聲空間種群多樣性較大時，PAR的值較小，此時有利于在空間里進行全局尋優，快速找到最優解附近區域。當和聲空間種群多樣性較小時，PAR值較大，此時將會對空間已有的和聲進行微調，并將前一代的信息遺傳給下一代，從而增強了HS的局部開采能力，獲得更高精度的解。

2.2.2 隨機行走擾動的新和聲更新策略

2.2.1 節所述的PAR動態更新策略可以很好地平衡算法的全局尋優和局部開采，并提升迭代速度，但是無法從根本上解決算法容易陷入局部最優解的缺點。當所有的粒子都趨向同一性即維多樣性下降時，算法從以全局尋優為主轉為以局部尋優為主，但是群體智能優化算法本身有陷入局部最優的缺陷[14-15]，因此本文在原有和聲更新的基礎上加入隨機行走策略，如式（6）所示：

式中：N(μ,σ2)表示均值為μ、方差為σ2的高斯分布，本文設置μ=0,σ2=|Xnew-Xbest|；Xbest表示當前空間里面最好的和聲；α稱為隨機行走觸發因子，計算公式如式（7）所示：

在迭代初期，和聲空間中多樣性較大，此時α=0。當進化到中后期，空間中較優的和聲出現，并引導其他和聲向其靠攏，空間中和聲相似度增加，此時易陷入局部最優，設置和聲空間更新比例τ作為算法陷入局部最優的標志。當空間中和聲更新的比例低于某個值時說明原有算法的局部開采能力不足，此時觸發隨機行走策略。經過實驗仿真發現τ=0.2時，算法的定位精度和收斂速度較優，因此第4節實驗仿真中設置τ=0.2。綜上，可以得到AHS-RW的算法流程，如圖2所示。

圖2 AHS-RW算法流程

3 算法仿真與性能分析

本節搭建仿真平臺分析所提AHS-RW算法的定位性能。首先在一個30×30的矩形中，均勻分布30個節點，每個節點有效通信距離為10 m，并隨機挑選10個節點為錨節點（參考節點）。SNPSO中設置w=0.7，c1=c2=1.494[3]。IHS和 AHS-RW 中設置PARmin=0.01，PARmax=0.99，BW=0.01。

利用式（8）所示的平均定位誤差AVE衡量3種算法的定位性能。結果圖中每個數據是20次獨立重復實驗的平均值。

3.1 算法收斂性能比較

圖3描述了IHS、SNPSO及AHS-RW這3種算法在設置和聲空間大小HMS為60時，定位精度與迭代次數的關系。由圖3可見，IHS算法在迭代次數大于100、SNPSO算法在迭代次數大于50、AHS-RW算法在迭代次數大于30次后，3種算法逐漸收斂至最優值。盡管IHS算法在迭代初期和中期表現出很強的全局搜索能力，但是局部開采能力差，因此最終定位精度低于SNPSO和AHS-RW算法。此外，隨著迭代次數的增加，3種算法的定位誤差都在減小，從最后收斂的結果看，AHS-RW算法具有最小的定位誤差，SNPSO次之，IHS最差。

圖3 算法收斂性對比

3.2 平均定位時間比較

圖4對比了IHS、SNPSO及AHS-RW這3種算法的平均定位時間。由圖4可見，IHS算法、SNPSO算法及AHS-RW算法完成一次未知節點定位所需要的時間分別為75 ms、54 ms及31 ms。參照3.1節的3條曲線的斜率可知，AHS-RW算法尋優最快，定位時間最短，SNPSO算法次之，HIS算法尋優速度最慢，所需定位時間也最長。

圖4 算法定位時間對比

3.3 錨節點數量對定位性能影響

圖5給出了IHS、SNPSO和AHS-RW這3種算法在設置HMS=60、I=200時，WSN網絡中平均定位誤差與參考節點個數的關系。由圖5可以看出，隨著參考節點數量的增加，有更多的參考信息可以用來估計未知節點的坐標信息，因此平均定位誤差也逐漸下降。由3條曲線的走向可以看出，3種算法的整體定位性能優劣依次是：AHS-RW＞SNPSO＞IHS。當設置6個錨節點時，AHS-RW、SNPSO及IHS算法的定位誤差分別是0.95 m、1.3 m及1.8 m。

圖5 平均定位誤差與錨節點數量關系

3.4 和聲空間對定位性能的影響

圖6仿真了IHS、SNPSO及AHS-RW三種算法在設置I=200時平均定位誤差與和聲空間大小的關系。由圖6可以看出：

圖6 平均定位誤差和和聲空間的關系

（1）在3種算法中，和聲空間增大時，種群多樣性增加，因此可以尋找到更高精度的定位結果，降低了定位誤差。

（2）和IHS算法相比，AHS-RW算法加入了PAR自適應更新策略和隨機行走策略，因此在迭代初期進行全局探索和迭代初中后期進行局部精細開發的時候，尋優速度更快，尋優精度更高。

（3）盡管SNPSO算法在種群規模達到30后就開始收斂到最大精度值，但是隨后就陷入局部最優，當種群規模繼續增加時，尋優精度不再提升；而AHS-RW算法雖然前期尋優速度慢于SNPSO，但是在后期尋優精度上更優。

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

圖7描述了給定測距誤差前提下3種算法的定位性能。由圖7可見，隨著測距誤差的減小，3種算法的定位誤差也在減小。在測距誤差由10%增大到30%的過程中，IHS算法的定位誤差顯著增加，說明該算法魯棒性差；而SNPSO和AHS-RW算法則更耐誤差一些，相較而言，AHS-RW的定位精度更高。

圖7 平均定位誤差和測距誤差的關系

3.6 AHS-RW算法穩定性分析

圖8給出了IHS、SNPSO及AHS-RW三種算法在設置HMS=60、I=200時的穩定性。為了避免偶然性，進行20組次獨立重復實驗，每次實驗取值均是在MATLAB平臺運行1 000次算法程序的平均值。由圖8可見，SNPSO算法的波動性較大，穩定性相對較弱，其次是IHS算法，而AHS-RW算法的波動幅度最小，穩定性最好，這是因為AHS-RW加入的動態更新和隨機擾動雙策略保證了算法的定位效率更高，穩定性增強。

圖8 算法穩定性對比

4 結 語

在和聲搜索算法HS的基礎上，提出兩種優化策略，分別是基于和聲空間相似度的動態PAR更新策略和隨機行走擾動的新和聲更新策略，并將其應用于無線傳感器網絡節點定位場景中。從實驗結果可以看出，所提的AHS-RW算法可以兼顧節點定位精度和定位速度，并且在測距誤差較大的情況下仍有較強的定位性能。下一步將在實際物理環境中搭建平臺檢測所提算法的實際定位性能。