基于粒子群算法的傳感器網絡室內定位系統優化*

張 磊， 黃 如， 袁偉娜

(華東理工大學 信息科學與工程學院，上海 200237)

基于粒子群算法的傳感器網絡室內定位系統優化*

張 磊， 黃 如， 袁偉娜

(華東理工大學 信息科學與工程學院，上海 200237)

通過接收信號強度指示(RSSI)和歐氏距離的非線性函數映射關系來進行弱移動目標的距離估計。以最大似然估計(MLE)法為基礎，結合電磁波在自由空間中的傳播特性，重新構建基于粒子群優化(PSO)定位算法的適應度函數來提高無線定位精度。并提出了一種慣性權重優化的自適應學習機制來優化全局搜索能力和局部搜索精度，提升定位算法的容錯能力。測試結果表明：本室內定位算法具有抗干擾強、魯棒性好和無線定位精度高等優點。

接收信號強度指示(RSSI)測距； 最大似然估計法； 粒子群優化算法； 無線定位

0 引 言

目前,基于無線傳感器網絡(WSNs)節點定位技術主要有兩類：基于測距的定位算法；距離無關的定位算法[1]?；跍y距的定位算法是通過接收信號強度指示(RSSI)、到達時間(TOA)、到達時間差(TDOA)或到達角(AOA)[2～5]等測度方式獲得節點間的相對位置關系(如距離、角度)，然后根據三邊測量[6]、三角測量[7]或最大似然估計 (maximum likelihood estimation,MLE) 法[8]等定位算法計算盲節點位置。由于復雜環境下測距誤差較大，上述依賴于測距精準度的定位算法的定位精度將達不到要求。文獻[9]采用了粒子群優化(PSO)定位算法，提升定位精度，但是適應度函數的選擇對于粒子優劣程度的評估至關重要，文獻[9]只是簡單地將測距誤差函數引入適應度函數，其抗干擾性能較弱。本文提出MLE與傳統PSO相結合的(MLE and classic PSO，MLE-PSO)定位算法，以MLE為基礎結合電磁波在自由空間中的傳播特性，重構基于PSO定位算法的適應度函數，可有效地評估粒子優劣性。并提出了一種慣性權重優化的自適應學習機制，優化全局搜索能力和局部搜索精度，以改善算法性能，提高盲節點的定位精度和系統可靠性。

1 基于PSO的定位算法

將盲節點抽象為一個粒子，把每個粒子的位置集合作為盲節點潛在坐標估計值解集，并在該解集中搜索最優盲節點坐標。設在2維平面上，隨機初始化 l 個粒子，記為Xi=(xi1,xi2)，i=1,2,…,l。粒子的矢量速度記為Vi=(vi1,vi2)，每個粒子搜索自己的平面，在搜索中通過適應度函數f(Xi)值計算自己局部最優坐標值pbest=(pi1,pi2)，從群體中選出全局最優坐標值gbest=(pg1,pg2)。根據式(1)更新粒子飛行速度和位置

(1)

式中 m為迭代次數。圖1為MLE-PSO定位算法的粒子狀態更新迭代圖。

圖1 MLE-PSO定位算法更新迭代圖

迭代終止條件是達到最大迭代次數，或者滿足適應度函數最小允許誤差。此外為了使本系統能更加適應室內復雜環境下的定位要求，MLE-PSO定位算法在標準PSO算法的基礎上做了如下兩點改進：

1)慣性權重自適應學習機制

由于標準PSO算法運用于復雜環境下的室內定位系統存在早熟收斂、后期進化慢等不足[10]，因此，對粒子更新公式中的部分參數作適當調整是非常必要的。MLE-PSO成為高效定位算法的前提是：前期具有較強的全局搜索能力和后期具有較高的局部搜索精度。而慣性權重w正是調節全局和局部搜索能力的關鍵因子。因此，本文提出了慣性權重w隨迭代次數在不同區間做線性規律變化的自適應學習方法，它能使慣性權重w在搜索前期很長時間內保持較大值，提高全局搜索能力；在搜索后期很長時間內維持較小值，提高局部搜索精度。慣性權重的數學表達式如下

(2)

式中 w∈[wmin,wmax]；m為當前迭代次數；M為最大迭代次數。

2)基于MLE改進的適應度函數

圖2為MLE模型圖，設平面上k(k>3)個不共線的錨節點坐標分別為(x1,y1),(x2,y2)，…，(xk,yk)，盲節點 O 坐標為(x,y)，它到各錨節點的距離分別為r1,r2，…，rk。

圖2 MLE模型圖

由歐氏距離公式建立方程組，并引入測距誤差量，得到實際的線性模型為[11]

AX+R=B

(3)

式中R為k-1維隨機誤差向量；X為盲節點坐標。求均方誤差‖R‖2=(B-AX)T(B-AX)的極值點，解得X的最大似然估計值為

(4)

PSO定位算法的適應度函數可選為MLE算法的均方誤差‖R‖2，即

f(X)=‖R‖2=(B-AX)T(B-AX)

(5)

f(X)值越小，粒子越接近實際位置。但根據電磁波在自由空間中的傳播特性，基于RSSI的測距中，當兩節點間距離越近，測距誤差越小，越遠誤差也就越大。因此,需重新配置測距值集合中的各測距值的權重。設定權重公式如下

(6)

式中 ri和rk分別為第i個和第k個錨節點到盲節點之間的測距值。由于R(i)是ri和rk的函數，可用δi來約束R(i)為測量不太精確的測距值在適應度函數計算中所占的權重。因此可得到改進后的適應度函數如下

(7)

2 系統軟件設計

2.1 基于RSSI的測距方案

經典的基于RSSI測距的信號在自由空間中的傳播模型具有對數衰減特性，將信號強度轉化為距離r的函數，得到如下公式

(8)

2.2MLE-PSO定位算法的實現

MLE-PSO定位算法的基本流程如下：

1)基于高斯濾波的RSSI測距，計算得到盲節點與錨節點間的距離值集合；

2)在定位活動范圍內，初始化l個粒子，及其速度和位置；

3)根據式(7)以及步驟(1)測得的距離集合，設定適應度函數；

4)計算粒子初始適應度值，設置個體和全局優化坐標的初始化值；

5)根據式(1)進行粒子速度和位置更新，并計算粒子的適應度值；

6)比較適應度值，進行個體最優坐標和全局最優坐標更新，判斷終止條件是否滿足，如滿足將結束尋優，該全局最優坐標值即為盲節點的最優坐標估計值；否則轉到步驟(5)。

2.3 定位系統軟件實現框架

1)盲節點向空間廣播數據；

2)錨節點接收廣播信號并記錄該信息，提取RSSI值，計算之間距離值；

3)通過網絡路由，將距離值集合及錨節點自身坐標信息傳遞給控制中心；

4)控制中心利用多點MLE-PSO定位算法估算出盲節點坐標。

3 定位系統數值驗證

驗證系統采用以CC2530芯片為核心的硬件開發平臺，以Z-Stack為核心的ZigBee協議棧方案[12]，來實現室內定位系統。實驗是在實驗室地面上完成的，實驗初始化參數設置：節點發送功率為-14dBm；接收靈敏度為-90dBm；休眠模式PM3功耗為540μA；16位短地址為每個節點配置不同的16位短地址，0xFFFF為廣播地址；錨節點坐標值為(-2，1)，(-2，-1)，(2，-1)，(2，1)；測試場景大小為6m×4m。

3.1 基于RSSI測距實驗驗證

基于RSSI測距實驗中需注意：當發射器的發射功率設置過大時，近距離處得不到較高分辨率；過小時，遠距離處將收不到信號。發射功率應根據運用場景的不同進行調整，使其達到高分辨率和可靠通信的平衡點。對于小范圍內的室內定位系統，能滿足10m內的正常通信即可。圖3為測距結果擬合曲線圖。

圖3 RSSl與距離的擬合曲線

計算得到擬合公式如下

(9)

3.2 定位系統驗證

設定表1為定位測試的數據結果。MLE-PSO算法的參數：粒子群規模l為50；最大迭代次數M為100；學習因子c1,c2為1.496 2；初始慣性權重wmax為0.9；終止慣性權重wmin為0.1；粒子最大飛行速度vmax為0.5m/步；適應度函數的最小容許誤差為10-6。

表1 MLE和MLE-PSO測量坐標值對比 m

由表1可以看出，MLE-PSO定位算法計算的定位值大部分優于MLE定位算法。從表1中任選幾組測量值(包括定位值、RSSI測量值和測距值)，導入Matlab數據分析工具，以對比驗證不同算法、不同參數情況下，MLE-PSO定位算法的優越性。又由于實際的應用環境可能比實驗室測試環境復雜得多，因此在已測得數據基礎上疊加7個等級(每個等級代表測距值疊加上限為7 %的隨機比例誤差，即0 %～7 %之間)的隨機誤差，再次對比其性能，得到幾組對比圖如圖4～圖6，其中誤差單位為m。

圖4 MLE-PSO，MLE和三邊測量算法性能對比圖

圖5 不同慣性權重函數的PSO算法對比圖

圖6 不同適應度函數的PSO算法對比圖

圖4中參與對比的三種定位算法分別是MLE-PSO定位算法、MLE定位算法和三邊測量算法。圖5中參與對比的慣性權重函數分別是本文采用的分段函數、二次函數及線性遞減函數。圖6中參與對比的適應度函數1,2,3分別是本文采用的適應度函數式(7)，式(5)及測距誤差函數

(10)

圖4(a)、圖5(a)、圖6(a)可看出，本設計提出的MLE-PSO定位算法計算的盲節點位置更接近實際位置。隨著測距誤差的逐步增加，圖4(b)中3種定位算法的定位精度都在下降，但是MLE-PSO算法對誤差的控制效果較好。驗證MLE-PSO具有良好的容錯性和較強適應性。圖5(b)中采用二次函數和線性遞減函數作為慣性權重的PSO算法，在干擾環境下定位不夠穩定，而本文采用的分段函數卻相對較穩定。驗證了本文采用的慣性權重函數提升了粒子的搜索能力，可很好地排除環境干擾。圖6(b)表明本文采用的適應度函數能更準確選出優秀的粒子，驗證本設計的適應度函數符合實際電磁波在自由空間中的傳播特性，更能有效區分粒子的優劣程度，因此,提高了搜索速度和搜索效率。

4 結 論

采用基于RSSI的測距技術為室內無線定位算法提供距離信息。提出了MLE-PSO定位算法，設計了更符合電磁波傳輸特性的適應度函數，可更高效地評估粒子的優劣程度。以分段函數作為慣性權重的自適應學習機制引入到MLE-PSO算法的設計中，提高粒子的搜索能力，進而提升盲節點在干擾環境下的定位精度。實驗測試并結合Matlab數據分析工具，對比和分析了不同定位算法、不同參數下MLE-PSO定位算法的性能，驗證了MLE-PSO定位算法具有抗干擾能力強、定位精度高的優點。

[1] 陳錫劍,程良倫.基于RSSI的功率匹配定位算法的研究與實現[J].傳感技術學報,2013(5):709-714.

[2] 文春武,宋 杰,姚家振.基于RSSI校正的無線傳感器網絡定位算法[J].傳感器與微系統,2014,33(12):134-136.

[3] Zhu G,Zhang H,Ye J Z,et al.An anchor-free position algorithm for evenly deployed wireless sensor networks[C]∥2014 the Sixth International Conference on Measuring Technology and Mechatronics Automation,IEEE,2011:379-382.

[4] 黃中林,鄧 平,梁甲金,等.無線傳感器網絡定位技術研究進展[J].傳感器與微系統,2009,28(11):4-7.

[5] Brida P,Machaj J,Benikovsky J,et al.A new complex angle of arrival location method for Ad Hoc networks[C]∥2010 the 7th Workshop on Positioning Navigation and Communication(WPNC),IEEE,2010:284-290.

[6] 邵 磊,趙 京,張乃龍.基于超寬頻距離傳感器的移動目標定位系統[J].傳感器與微系統,2013,32(11):63-65.

[7] Niculescu D,Nath B.Ad Hoc positioning system(APS)using AoA[C]∥Proceedings of IEEE INFOCOM,2003:1734-1743.

[8] 張 秀,申曉紅,閆永勝,等.基于無線傳感器網絡的自適應聲源定位算法[J].傳感器與微系統,2015,34(4):115-118.

[9] 彭 燕.無線傳感器網絡定位優化算法及其仿真[J].計算機與數字工程,2011(3):9-11.

[10] 尹 呈,郭觀七,李文彬,等.基于自適應學習的多目標粒子群優化算法[J].計算機應用研究,2012,29(9):3232-3235.

[11] 王曉樂,徐家品.基于粒子群優化算法的WSNs節點定位研究[J].計算機應用,2009,29(2):494-495.

[12] 黃 如,張 磊.物聯網工程應用技術實踐教程(物聯網工程與技術規劃教材)[M].北京：電子工業出版社,2014.

Optimization of indoor positioning system for sensor networks based on particle swarm optimization algorithm*

ZHANG Lei, HUANG Ru, YUAN Wei-na

(College of Information Science and Engineering，East China University of Science and Technology，Shanghai 200237，China)

The nonlinear function mapping relationship between RSSI and Euclidean distance is used to estimate distance of weak mobile target.This system improves positioning precision by rebuilding fitness function based on PSO positioning algorithm,on the basis of maximum likelihood estimation(MLE)and combines with characteristics of electromagnetic wave propagation in free space.Besides,an adaptive learning mechanism of inertia weight optimization is put forward to optimize global searching ability and local searching precision.The fault tolerance of localization algorithm is promoted.With experiment on CC2530,it is proved to have the advantages of strong anti-interference,good robustness and high precision of wireless localization.

received signal strength indication(RSSI); maximum likelihood estimation(MLE); particle swarm optimization(PSO)algorithm; wireless localization

10.13873/J.1000—9787(2017)04—0061—04

2016—05—13

國家自然科學基金資助項目(61501187)；教育部基本科研業務基金資助項目(WH1315009)；國家級大學生創新實踐基金資助項目(201410251044)

TN 919

A

1000—9787(2017)04—0061—04

張 磊(1990-)，男，碩士研究生，研究方向為無線傳感器網絡。