張 磊， 黃 如， 袁偉娜

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

基于粒子群算法的傳感器網(wǎng)絡(luò)室內(nèi)定位系統(tǒng)優(yōu)化*

張 磊， 黃 如， 袁偉娜

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

通過接收信號強(qiáng)度指示(RSSI)和歐氏距離的非線性函數(shù)映射關(guān)系來進(jìn)行弱移動(dòng)目標(biāo)的距離估計(jì)。以最大似然估計(jì)(MLE)法為基礎(chǔ)，結(jié)合電磁波在自由空間中的傳播特性，重新構(gòu)建基于粒子群優(yōu)化(PSO)定位算法的適應(yīng)度函數(shù)來提高無線定位精度。并提出了一種慣性權(quán)重優(yōu)化的自適應(yīng)學(xué)習(xí)機(jī)制來優(yōu)化全局搜索能力和局部搜索精度，提升定位算法的容錯(cuò)能力。測試結(jié)果表明：本室內(nèi)定位算法具有抗干擾強(qiáng)、魯棒性好和無線定位精度高等優(yōu)點(diǎn)。

接收信號強(qiáng)度指示(RSSI)測距； 最大似然估計(jì)法； 粒子群優(yōu)化算法； 無線定位

0 引 言

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

1 基于PSO的定位算法

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

(1)

式中 m為迭代次數(shù)。圖1為MLE-PSO定位算法的粒子狀態(tài)更新迭代圖。

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

迭代終止條件是達(dá)到最大迭代次數(shù)，或者滿足適應(yīng)度函數(shù)最小允許誤差。此外為了使本系統(tǒng)能更加適應(yīng)室內(nèi)復(fù)雜環(huán)境下的定位要求，MLE-PSO定位算法在標(biāo)準(zhǔn)PSO算法的基礎(chǔ)上做了如下兩點(diǎn)改進(jìn)：

1)慣性權(quán)重自適應(yīng)學(xué)習(xí)機(jī)制

由于標(biāo)準(zhǔn)PSO算法運(yùn)用于復(fù)雜環(huán)境下的室內(nèi)定位系統(tǒng)存在早熟收斂、后期進(jìn)化慢等不足[10]，因此，對粒子更新公式中的部分參數(shù)作適當(dāng)調(diào)整是非常必要的。MLE-PSO成為高效定位算法的前提是：前期具有較強(qiáng)的全局搜索能力和后期具有較高的局部搜索精度。而慣性權(quán)重w正是調(diào)節(jié)全局和局部搜索能力的關(guān)鍵因子。因此，本文提出了慣性權(quán)重w隨迭代次數(shù)在不同區(qū)間做線性規(guī)律變化的自適應(yīng)學(xué)習(xí)方法，它能使慣性權(quán)重w在搜索前期很長時(shí)間內(nèi)保持較大值，提高全局搜索能力；在搜索后期很長時(shí)間內(nèi)維持較小值，提高局部搜索精度。慣性權(quán)重的數(shù)學(xué)表達(dá)式如下

(2)

式中 w∈[wmin,wmax]；m為當(dāng)前迭代次數(shù)；M為最大迭代次數(shù)。

2)基于MLE改進(jìn)的適應(yīng)度函數(shù)

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

圖2 MLE模型圖

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

AX+R=B

(3)

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

(4)

PSO定位算法的適應(yīng)度函數(shù)可選為MLE算法的均方誤差‖R‖2，即

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

(5)

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

(6)

式中 ri和rk分別為第i個(gè)和第k個(gè)錨節(jié)點(diǎn)到盲節(jié)點(diǎn)之間的測距值。由于R(i)是ri和rk的函數(shù)，可用δi來約束R(i)為測量不太精確的測距值在適應(yīng)度函數(shù)計(jì)算中所占的權(quán)重。因此可得到改進(jìn)后的適應(yīng)度函數(shù)如下

(7)

2 系統(tǒng)軟件設(shè)計(jì)

2.1 基于RSSI的測距方案

經(jīng)典的基于RSSI測距的信號在自由空間中的傳播模型具有對數(shù)衰減特性，將信號強(qiáng)度轉(zhuǎn)化為距離r的函數(shù)，得到如下公式

(8)

2.2MLE-PSO定位算法的實(shí)現(xiàn)

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

1)基于高斯濾波的RSSI測距，計(jì)算得到盲節(jié)點(diǎn)與錨節(jié)點(diǎn)間的距離值集合；

2)在定位活動(dòng)范圍內(nèi)，初始化l個(gè)粒子，及其速度和位置；

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

4)計(jì)算粒子初始適應(yīng)度值，設(shè)置個(gè)體和全局優(yōu)化坐標(biāo)的初始化值；

5)根據(jù)式(1)進(jìn)行粒子速度和位置更新，并計(jì)算粒子的適應(yīng)度值；

6)比較適應(yīng)度值，進(jìn)行個(gè)體最優(yōu)坐標(biāo)和全局最優(yōu)坐標(biāo)更新，判斷終止條件是否滿足，如滿足將結(jié)束尋優(yōu)，該全局最優(yōu)坐標(biāo)值即為盲節(jié)點(diǎn)的最優(yōu)坐標(biāo)估計(jì)值；否則轉(zhuǎn)到步驟(5)。

2.3 定位系統(tǒng)軟件實(shí)現(xiàn)框架

1)盲節(jié)點(diǎn)向空間廣播數(shù)據(jù)；

2)錨節(jié)點(diǎn)接收廣播信號并記錄該信息，提取RSSI值，計(jì)算之間距離值；

3)通過網(wǎng)絡(luò)路由，將距離值集合及錨節(jié)點(diǎn)自身坐標(biāo)信息傳遞給控制中心；

4)控制中心利用多點(diǎn)MLE-PSO定位算法估算出盲節(jié)點(diǎn)坐標(biāo)。

3 定位系統(tǒng)數(shù)值驗(yàn)證

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

3.1 基于RSSI測距實(shí)驗(yàn)驗(yàn)證

基于RSSI測距實(shí)驗(yàn)中需注意：當(dāng)發(fā)射器的發(fā)射功率設(shè)置過大時(shí)，近距離處得不到較高分辨率；過小時(shí)，遠(yuǎn)距離處將收不到信號。發(fā)射功率應(yīng)根據(jù)運(yùn)用場景的不同進(jìn)行調(diào)整，使其達(dá)到高分辨率和可靠通信的平衡點(diǎn)。對于小范圍內(nèi)的室內(nèi)定位系統(tǒng)，能滿足10m內(nèi)的正常通信即可。圖3為測距結(jié)果擬合曲線圖。

圖3 RSSl與距離的擬合曲線

計(jì)算得到擬合公式如下

(9)

3.2 定位系統(tǒng)驗(yàn)證

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

表1 MLE和MLE-PSO測量坐標(biāo)值對比 m

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

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

圖5 不同慣性權(quán)重函數(shù)的PSO算法對比圖

圖6 不同適應(yīng)度函數(shù)的PSO算法對比圖

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

(10)

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

4 結(jié) 論

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

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

[2] 文春武,宋 杰,姚家振.基于RSSI校正的無線傳感器網(wǎng)絡(luò)定位算法[J].傳感器與微系統(tǒng),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] 黃中林,鄧 平,梁甲金,等.無線傳感器網(wǎng)絡(luò)定位技術(shù)研究進(jìn)展[J].傳感器與微系統(tǒng),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] 邵 磊,趙 京,張乃龍.基于超寬頻距離傳感器的移動(dòng)目標(biāo)定位系統(tǒng)[J].傳感器與微系統(tǒng),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] 張 秀,申曉紅,閆永勝,等.基于無線傳感器網(wǎng)絡(luò)的自適應(yīng)聲源定位算法[J].傳感器與微系統(tǒng),2015,34(4):115-118.

[9] 彭 燕.無線傳感器網(wǎng)絡(luò)定位優(yōu)化算法及其仿真[J].計(jì)算機(jī)與數(shù)字工程,2011(3):9-11.

[10] 尹 呈,郭觀七,李文彬,等.基于自適應(yīng)學(xué)習(xí)的多目標(biāo)粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(9):3232-3235.

[11] 王曉樂,徐家品.基于粒子群優(yōu)化算法的WSNs節(jié)點(diǎn)定位研究[J].計(jì)算機(jī)應(yīng)用,2009,29(2):494-495.

[12] 黃 如,張 磊.物聯(lián)網(wǎng)工程應(yīng)用技術(shù)實(shí)踐教程(物聯(lián)網(wǎng)工程與技術(shù)規(guī)劃教材)[M].北京：電子工業(yè)出版社,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

國家自然科學(xué)基金資助項(xiàng)目(61501187)；教育部基本科研業(yè)務(wù)基金資助項(xiàng)目(WH1315009)；國家級大學(xué)生創(chuàng)新實(shí)踐基金資助項(xiàng)目(201410251044)

TN 919

A

1000—9787(2017)04—0061—04

張 磊(1990-)，男，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。