接收信號強度指示測距模型修正與粒子群算法權重優化的節點定位算法

任克強， 溫曉珍

(江西理工大學信息工程學院， 贛州 341000)

無線傳感器網絡(wireless sensor network，WSN)是由大量成本低廉、體積微小、分布密集的傳感器節點組成的網絡系統，這些傳感器節點耗能低，能夠收集特定事件的信息送到監測人員處進行進一步的處理[1]。WSN由于能獲取客觀的物理信息被廣泛運用于軍事、工業及環境監測等諸多領域[2]。在實際的應用中，準確的位置信息在WSN監測活動中必不可少，沒有位置信息的監測活動無實際價值可言[3]。節點定位作為WSN中的一項重要應用，是監測事件的前提，在定位算法中，通常可分為基于距離和距離無關兩大類[4]。質心算法、APIT(approximate point-in-triangulation test)和DV-Hop(distance vector-hop)等是較常用的距離無關的定位算法[5-6]，無需實際測量節點間距離，硬件開銷較小。相較于距離無關的算法，基于距離的定位算法可實現更高的精度[7-8]。

接收信號強度指示(received signal strength indicator，RSSI)作為一種較為常用的距離估計方法，因其較低的設備部署開銷，在WSN的定位算法中得到了廣泛的應用與研究[9]。然而RSSI測距具有一定的局限性，易受環境干擾，影響定位的準確性。在一些文獻中，定位問題視作是一個非線性無約束的優化問題。粒子群算法(particle swarm optimization, PSO)因其參數少、計算簡便、收斂快速等優點受到相關學者關注，以離散粒子群算法(DPSO)為基礎，一些相關改進算法相繼被提出。在粒子群算法中，當搜索空間較大時，自適應差的權重難以在搜索速度和搜索精度之間達到平衡，因此中外學者提出了相應的改進策略。文獻[10]提出一種基于粒子群優化的自定位算法，該算法將學習因子設置為線性遞減模式，利用分量變異法跳出自定位搜索停滯時的局部最優，該方法雖然提高了定位性能，但計算復雜度也顯著提高。文獻[11]提出一種貝葉斯概率模型，提高了RSSI測量的精度，但在復雜的實際環境中，所選模型的經驗參數作用不大。文獻[12]提出一種基于混合粒子群優化算法的室內和室外軌道自行車無線傳感器精確定位技術，利用對數正態陰影模型進行參數估計并測距，然后結合混合粒子群優化-人工神經網絡(PSO-ANN)算法降低測距誤差，與傳統對數正態陰影模型相比，定位準確度更高。文獻[13]提出一種基于節點間測距的改進PSO算法，該算法在基本PSO算法中引入了動態干擾因子和罰函數，提高了算法的收斂性，避免了在無效的搜索空間中耗費時間。文獻[14]提出一種優化罰函數的改進粒子群定位算法，根據種群密度改變懲罰因子用于提升收斂速度，然后對誤差進行加權處理，進一步提高定位算法準確度。文獻[15]提出一種自適應優化粒子群算法，根據適應度函數確定的粒子適應值調節慣性權重與學習因子的取值，并用異步變化法改進學習因子，但該算法難以跳出局部極值點，較難改善測試點定位精度。

針對復雜環境下RSSI波動較大及標準PSO算法易陷入局部極值點的問題，采用兩種優化策略對定位算法進行改進：一是考慮RSSI測距誤差易積累至定位階段，利用最小化誤差平方和原則，修正RSSI的模型參數；二在PSO算法中引入非線性慣性權重，平衡算法的全局與局部探索能力，減少尋優過程中的不必要消耗，防止算法收斂于局部極值點，實現定位性能的優化。

1 RSSI定位及誤差分析

1.1 RSSI定位

基于接收信號強度指示(RSSI)的測距理論為：依據無線電波或聲波在介質中傳播，信號功率隨距離衰減的原理，將信號的損耗通過衰減模型轉變成距離，一般分成經驗模型和理論模型兩類[16]。

(1)信號傳播的經驗模型。首先設置一個關聯數據庫，錄入并存放測試點的信號強度和它們對應的坐標(x,y,s1,s2,s3)，然后在定位時，將測試點所測得的信號強度(s′1,s′2,s′3)與之前數據庫中保存的記錄值進行對比，所測信號強度與數據庫記錄值之間的均方差sqrt[(s1-s′1)2+(s2-s′2)2+(s3-s′3)2]最小的點即為所求未知節點的坐標，可進行多次測量以減小誤差。

(2)信號傳播的理論模型。考慮實際復雜環境對信號傳輸的干擾，確定信號衰減與傳輸距離間的關系式，根據測量的信號強度，利用對數正態陰影模型(log-normal shadowing model，LNSM)計算未知節點與發射節點間的距離：

(1)

式(1)中：pd為傳輸距離d的信號強度；pd0為傳輸距離d0的信號強度；n為路徑損耗指數；d0為參考距離，取d0=1 m；Xσ為均值是0的高斯隨機變量。

1.2 RSSI測距存在的問題

在基于RSSI的定位中，通常選用對數正態陰影模型來描述信號強度與節點距離的關系，但由于實際應用中外在因素的影響，信號強度與節點距離之間并沒有明確的對應關系，這使得基于測距的RSSI定位算法存在一定的局限性[17]。RSSI測距過程受環境影響較大，理論上信號強度值進行有規律的變化，距離增大，強度值不斷衰減，而事實上由于存在溫度、反射及障礙物的干擾，這些環境的不穩定因素會導致獲取的信號強度值波動較大，隨著環境的改變，信號強度測量的不穩定性增大，所得測量值的準確度隨之降低。若針對不同的實際特定環境仍選用傳統模型，而不考慮環境干擾，則易造成測距誤差。

因此，在原有的對數正態陰影模型基礎上，針對環境變化時RSSI理論測距模型導致的定位精度不高的問題，對測距的模型參數進行修正，可有效改善以上問題，減小定位誤差，提高定位精度。

2 粒子群算法分析

2.1 PSO算法原理

粒子群算法是一種啟發式的優化技術[18]。因參數少、收斂快、計算簡便而被廣泛應用。該算法依靠粒子間相互傳遞信息來改變自身的飛行狀態，能夠產生自組織行為從而進行快速有效的收斂。標準PSO算法種群中的每個成員被量化為一個粒子，粒子的速度根據本身的歷史信息以及群體的共享信息進行動態地調整。在n維空間中，第i個粒子的位置和速度分別描述為xi=(xi,1,xi,2,…,xi,n)、v=(vi,1,vi,2,…,vi,n)，粒子個體與粒子種群所經歷的歷史最佳位置分別描述為pbi=(pi,1,pi,2,…,pi,n)、gb=(g1,g2,…,gn)。PSO算法是一種基于迭代的優化技術，在二維搜索范圍中，第t+1次搜索時粒子將由pb、gb和擾動產生新的飛行速度和位置，其更新公式分別為

(2)

(3)

式中：w為慣性權重；c1、c2為學習因子；r1、r2為服從均勻分布的隨機數，取值范圍為0～1。

2.2 PSO算法存在的問題

目前，粒子群算法面臨的一個主要問題是算法在進行優化定位的過程中不能有效實現對目標空間的全局搜索，對于有多個局部極值點的函數，容易導致算法陷入這些點中，得不到正確的結果，從而降低算法的優化性能。在標準PSO算法中，最優粒子的位置信息向其他成員進行分享，強調了一個共同最優信息的處理，而忽略了個體間信息的傳遞。隨著迭代的進行，種群中每個成員間的距離逐漸縮小，粒子急速收斂到所獲得的最優位置處，造成算法早熟失效。如何引入相應策略處理這類問題，將是提高算法適應性的關鍵。

針對以上RSSI在復雜環境中測距誤差較大及標準PSO算法易陷入局部最優的問題，利用不同參考點的差值對RSSI測距模型的參數進行修正，并對粒子群算法的權重進行非線性化，提出一種RSSI測距模型修正及PSO權重優化的定位算法。

3 本文算法

3.1 LNSM參數估計及修正

基于RSSI測距的定位方法往往受到環境因素的影響，如果在不同環境中仍按照給定的經驗值設置傳播模型參數，節點間距離越大，誤差越大。對數正態陰影模型的理想曲線在距離較小時接近實際測量的RSSI值，在距離較遠時，由于穿透損失和阻塞效應，RSSI的測量值通常比LNSM所對應的理想值更小。因此，通過對測距模型參數進行修正，來減小環境因素對測距誤差的影響。

在本文算法中，L個參考點的RSSI值是在已知坐標的m個測試點上測量的，式(1)的可測量pd設為Y，已知量-10lgd設為x，傳播模型參數pd0和n分別設為a和b，則測距模型可擬合為

Y=a+bX+Xσ

(4)

LNSM的參數估計是基于最大限度地最小化誤差平方和原則，使得所擬合的函數值與實際測量數據之間的誤差最小化：

(5)

要使每個偏差都盡可能小，可令R最小來實現，即求函數R=R(a,b)在所測數據處取得最小值。

(6)

由此計算出a、b的表達式為

(7)

考慮L個不同參考節點之間的差異，修正公式(1)中的傳播模型參數pd0和n為

(8)

根據LNSM參數估計，確定了本文算法的RSSI測距模型參數，利用RSSI修正模型進行測距，得出信標與未知節點之間的距離。

假設A、B和C3個信標節點的坐標分別為(xa,ya)、(xb,yb)和(xc,yc)，以及它們到未知節點D(x,y)的距離為da、db和dc，則可通過三邊測量法來求出(x,y)的取值：

(9)

由此可得出未知節點D的坐標為

(10)

3.2 非線性遞減權重優化

慣性權重w的取值大小對PSO算法的尋優過程起著關鍵的控制作用，粒子飛行速度的升降依賴于權重的取值。若給定較高的w，粒子可提速向更大范圍尋找最優目標，使粒子群體得到發散，加快算法運行的速度，有利于在前期搜索中探測最優目標所在的區域。但若整個迭代過程均賦予較高的w值，粒子飛行速度過快，極易飛越過所尋找的目標，不利于在后期靠近目標時，降低速度進行細致的探索。由此可見，w參數大小的取值十分關鍵。目前，采用較多的經典線性遞減慣性權重為

w(k)=wmax-k(wmax-wmin)/Tmax

(11)

式(11)中：wmax、wmin分別為慣性權重的最高與最低值；Tmax為最大迭代次數。

線性遞減權重難以避免帶來一些問題，粒子在后期搜索中與最優目標的距離逐漸縮小，需賦予持續較小的慣性權重值w來減緩粒子的飛行速度，使粒子不斷靠近最優目標所在位置，而線性遞減權重的下降趨勢過于陡峭，粒子容易飛越過最優解。

(12)

式(12)中：wmax、wmin為慣性權重的最高與最低值，取wmax=0.9、wmin=0.4；t為當前迭代次數；Tmax為最大迭代次數；λ為收斂因子，當λ取值較大時，粒子速度減小，有助于粒子的探索在極值點附近進行；當λ取值較小，慣性權重值增大，粒子速度加快，能夠擴大搜索范圍。當迭代次數t=0時，函數值為初始權重值wmax=0.9，隨著搜索的進行，權重值呈非線性遞減趨勢，當達到最大迭代次數Tmax時，權重降為0.4，有利于局部搜索。本文所提出的非線性遞減權重策略符合尋優過程，具有較理想的尋優性能。

已知未知節點D(x,y)周圍有N個信標節點，第q個信標節點坐標為(xq,yq)，本文優化粒子群算法的適應度函數取為

(13)

4 仿真結果與分析

為測試本文定位算法的性能，采用MATLAB R2016b仿真平臺對本文定位算法的測距模型參數pd0和n進行確定；分析不同的慣性權重對算法的影響；并從測距誤差、信標節點密度、迭代次數3個方面對DPSO算法、文獻[14]的PSOAPF算法和本文算法的性能進行仿真實驗對比。仿真的空間取100 m×100 m的二維區域，節點總數為100，信標節點占30%，通信半徑為R=30 m，粒子群各參數設為M=30，c1=1.5，c2=1.2，各實驗分別進行100次測試，結果取平均值。

以節點平均定位誤差Eave作為算法的評價標準：

(14)

首先通過實驗建立RSSI的測距模型，在本文實驗環境中，在距離為di=0.2i(i=1,2,…,50)的4個參考點和40個測試點間對RSSI值測量100次，得到各個間距di處的RSSI值，取測試的平均值與di進行擬合，得出校正的pd0值和n值，圖1為通過MATLAB平臺得到的擬合曲線。

圖1 RSSI測試值的擬合曲線Fig.1 The fitting curve of the RSSI test value

在實驗測試中，RSSI測距模型參數修正為pd0=-37.02；n=2.04。如果干擾因素發生改變，可重新調整參數值。

圖2為迭代過程中兩種慣性權重取值大小的變化情況，wa為線性權重，wb為本文提出的非線性權重。

圖2 慣性權重的變化比較Fig.2 Comparison of performance changes of w

由圖2可見，隨著迭代的進行，兩種慣性權重值均不斷降低，在迭代次數0≤t≤15時，wb的下降速度大于wa，隨著搜索的進行，迭代后期wb曲線逐漸趨向水平，在15

圖3通過仿真實驗測試在信標節點密度為15%時，測距誤差變化情形下DPSO算法、文獻[14]的PSOAPF算法及本文算法的平均定位誤差情況。

圖3 測距誤差與平均定位誤差的關系Fig.3 The relationship between the ranging error and the mean positioning error

由圖3可見，測距誤差越大，3種算法的平均定位誤差也越大，表明測距誤差的積累容易對定位階段產生不利影響。其中，DPSO算法的整體平均定位誤差最大，PSOAPF算法次之，本文算法的平均定位誤差最低。在測距階段產生20%的誤差時，實驗得出DPSO與PSOAPF兩種算法的平均定位誤差為31.3%和26.2%，而本文算法低至19.8%，在相同測距誤差下，本文算法的平均定位誤差低于DPSO算法與PSOAPF算法，定位性能更佳。

圖4通過仿真實驗比較DPSO算法、文獻[14]的PSOAPF算法以及本文算法在不同的信標節點密度下的性能表現。

圖4 不同信標節點密度的平均定位誤差Fig.4 Mean positioning error of different beacon node density

圖4表明，3種算法在仿真空間信標節點數目越多時，所獲未知節點的信息越全面，定位越精確。其中，當控制仿真區域內信標節點占比為14%時，DPSO的平均定位誤差最高，達到28.01%，相比之下，PSOAPF和本文算法的平均定位誤差值下降明顯，分別為23.3%和20.01%。由此可知，DPSO算法的平均定位誤差雖有下降趨勢，但誤差值整體較高，效果最差；PSOAPF算法次之，本文算法的平均定位誤差最小，表現的性能最好。

圖5表示在不同迭代次數下，當測距誤差為20%時，DPSO算法、文獻[14]的PSOAPF算法以及本文算法的適應值比較情況。由圖5可見，迭代至10～20次時，3種算法相繼收斂。其中DPSO算法的收斂性能最差，在迭代約18次才趨于收斂，PSOAPF算法則在迭代約12次適應度值曲線就呈水平狀態，出現收斂趨勢，比DPSO算法收斂性能更良好，而本文算法在迭代大約10次則迅速收斂，在3種算法中收斂性能最優。

圖5 不同迭代次數的適應度比較Fig.5 Fitness comparison of different iterations

5 結論

提出一種融合RSSI測距模型參數修正與PSO權重優化的改進定位算法，采用不同參考點的差值對RSSI測距模型的參數進行修正以及對粒子群算法的權重進行非線性化兩種策略來提升改善算法性能。為了測試驗證本文改進策略的成效，在不同條件下對算法進行了仿真測試比較。仿真結果顯示，在硬件條件不變的情況下，本文定位算法的表現優于DPSO算法與PSOAPF算法，具有更好的收斂性能及更高的節點定位精度。如何進一步改善提升算法的性能，是后期要重點研究的工作。