基于粒子群優(yōu)化算法的井下目標(biāo)定位方法

張 蕊，李 暉，劉賽男(沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽 110870)

近年來無線傳感器網(wǎng)絡(luò)飛快發(fā)展，被廣泛應(yīng)用于管道監(jiān)測、精細(xì)農(nóng)業(yè)、智能交通及井下采礦等領(lǐng)域[1]。然而在井下環(huán)境中，傳感器采集到的信息在不知道其具體位置信息的情況下是沒有意義的，要快速準(zhǔn)確地獲得人員的位置信息才能為營救獲得更多的時間。

無線傳感器網(wǎng)絡(luò)定位算法可劃分為兩類，即測距算法和非測距算法。非測距算法在成本和功耗上有一定優(yōu)勢，但定位精度相對較低，而且對節(jié)點(diǎn)密度要求較高[2]。所以在礦井環(huán)境中適合使用基于測距的定位算法，其中RSSI(Receive Signal Strength Indicator)算法不需要額外的硬件設(shè)備，能量損耗、成本低，比較適合應(yīng)用在井下巷道中[3]。由于井下巷道狹長且環(huán)境復(fù)雜，測得的RSSI值誤差較大，為提高定位精度，很多學(xué)者提出了改進(jìn)方法。文獻(xiàn)[4]提出了一種3DL-RD煤礦井下無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)三維定位算法，通過RSSI測距方式得到信標(biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離，將信標(biāo)節(jié)點(diǎn)投影到與未知節(jié)點(diǎn)同一高度的水平面，再利用三邊測量法進(jìn)行平面定位，雖然能夠得到較高的定位精度，但忽略了巷道頂部對定位精度的影響，會使對頂部微弧位置節(jié)點(diǎn)的定位出現(xiàn)較大誤差；劉暢[5]提出井下無線傳感器網(wǎng)絡(luò)的RSSI比例差分定位算法，利用目標(biāo)節(jié)點(diǎn)附近的信標(biāo)節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的比例差分信息，修正未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離信息，并結(jié)合四邊定位法定位，雖然提高了未知節(jié)點(diǎn)的坐標(biāo)精度，卻一定程度上增加了算法的復(fù)雜度，并使無線傳感器網(wǎng)絡(luò)系統(tǒng)的開銷增多；文獻(xiàn)[6]提出了一種基于礦井三維建模WSNs(Wireless Sensor Networks)多重覆蓋和RSSI加權(quán)質(zhì)心定位算法，該方法完全基于網(wǎng)絡(luò)連通性，而且井下環(huán)境的傳輸模型與質(zhì)心算法理想的球型模型有很大差別；李寧等[7]提出基于改進(jìn)遺傳算法的礦井人員定位新算法，即以無線傳輸信號理論模型為基礎(chǔ)，周期性獲取信號傳輸路徑衰減指數(shù)的加權(quán)平均值，并結(jié)合遺傳算法進(jìn)行優(yōu)化，該方法是研究的熱點(diǎn)問題智能群體算法[8-9]，在井下環(huán)境下遺傳算法大量的計算導(dǎo)致在進(jìn)化后期搜索效率較低，穩(wěn)定性差。

本研究針對井下的復(fù)雜環(huán)境提出一種基于粒子群優(yōu)化算法的井下目標(biāo)定位方法。結(jié)合井下巷道[10-11]的特點(diǎn)規(guī)則放置信標(biāo)節(jié)點(diǎn)，將未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)間的估計距離和測量距離的均方誤差作為粒子群算法優(yōu)化的目標(biāo)函數(shù)，并引入慣性權(quán)重[12-13]，再通過算法的迭代運(yùn)算找到適應(yīng)性強(qiáng)的粒子，提高算法精度。該方法收斂速度快，計算量小，可靠穩(wěn)定，在提高測距精度的同時也增加了對井下巷道復(fù)雜環(huán)境的適應(yīng)性。

1 相關(guān)原理

1.1 三維信標(biāo)節(jié)點(diǎn)布置

煤礦井下巷道是狹長的，頂部呈微弧型，可以近似地看做長方體。分別在各對角上布置一對信標(biāo)節(jié)點(diǎn)，并在每個小區(qū)塊的微弧頂部中間布置一個信標(biāo)節(jié)點(diǎn)，這樣每個小區(qū)塊僅布置5個信標(biāo)節(jié)點(diǎn)。這樣的布置方法可以將定位區(qū)域區(qū)塊化，避免區(qū)塊內(nèi)節(jié)點(diǎn)布置過密，減小節(jié)點(diǎn)間通信干擾，使節(jié)點(diǎn)測距更準(zhǔn)確。信標(biāo)節(jié)點(diǎn)布置規(guī)則如圖1。

圖1 信標(biāo)節(jié)點(diǎn)布置規(guī)則

1.2 RSSI測距模型

本文采用在復(fù)雜環(huán)境中廣泛應(yīng)用的對數(shù)-常態(tài)分布模型和井下巷道RSSI測距分析[14]得出的參數(shù)，對井下無線信號傳播進(jìn)行建模和估計。對數(shù)-常態(tài)分布模型的表達(dá)式為

(1)

式中：PL(d) 為經(jīng)過距離d后的路徑損耗；PL(d0) 為經(jīng)過單位距離后的路徑損耗；d0表示單位距離，一般設(shè)為1 m；n表示為路徑損耗因子，它取決于無線信號傳播的環(huán)境；Xσ表示均值為0、標(biāo)準(zhǔn)差為σ的高斯噪聲，其值受周圍環(huán)境和障礙物影響，一般為4～10。接收端的信號強(qiáng)度為

PR(d)=PT-PL(d) 。

(2)

式中：PR(d)即為接收信號強(qiáng)度指示RSSI；PT為信號的發(fā)射功率，文獻(xiàn)[14]給出的參數(shù)為0 dBm。

綜上有式(1)和式(2)可以得出RSSI值與距離的關(guān)系為

RSSI=-10nlgd+A。

(3)

式中：d為參考節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離；A為常數(shù)。文獻(xiàn)[10]將實(shí)驗(yàn)所得的數(shù)據(jù)通過處理再進(jìn)行線性擬合,得出擬合直線方程

y=-24.494x-37.200 4 。

(4)

式中：y表示RSSI值；x表示距離d的對數(shù)；路徑損耗因子n為2.449 4。因此信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)間距離與RSSI的關(guān)系可以表示為

(5)

2 粒子群優(yōu)化算法

2.1 粒子群算法原理

粒子群優(yōu)化算法(Partical Swarm Optimization,PSO)是模擬鳥群覓食過程中的集體協(xié)作行為而提出的一種基于群體智能的全局隨機(jī)搜索算法[15]。在PSO算法中，每個優(yōu)化問題的解都是搜索空間中的一只“鳥”，稱之為粒子。首先初始化一群隨機(jī)粒子，然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索，即通過迭代找到最優(yōu)解[16]。假設(shè)d維搜索空間中的第i個粒子的位置和速度分別為Xi=(xi,1xi,2…xi,d)和Vi= (vi,1vi,2…vi,d)，在每一次迭代中,粒子通過跟蹤兩個最優(yōu)解來更新自己，第一個就是粒子本身所找到的最優(yōu)解，即個體極值pbest，Pi= (pi,1pi,2…pi,d)；另一個是整個種群目前找到的最優(yōu)解，即全局最優(yōu)解gbest,Pg。在找到這兩個最優(yōu)值時，粒子根據(jù)式(6)、(7)來更新自己的速度和新的位置。

vi,j(t+1)=wvi,j(t)+c1r1[pi,j-xi,j(t)]+c2r2[pg,j-xi,j(t)] ；

(6)

xi,j(t+1)=xi,j(t)+vi,j(t+1),j=1,2,…,d。

(7)

式中：w為慣性權(quán)重；c1和c2為正的學(xué)習(xí)因子，常設(shè)c1=c2=2；r1和r2是介于0到1之間均勻分布的隨機(jī)數(shù)；t為當(dāng)前迭代次數(shù)。

粒子群算法的性能很大程度上受算法的控制參數(shù)影響，w的合適選擇可以使粒子具有均衡的全局搜索能力和局部搜索能力，w較小有利于提高算法的局部搜索能力，w較大可以提高算法的全局搜索能力。因此采用線性遞減的慣性權(quán)重方法[8-9]，即線性遞減權(quán)重粒子群算法(Linear Degression Weight,LinWPSO)，權(quán)值公式為

(8)

式中：T是終止迭代次數(shù)；wmax和wmin為慣性權(quán)重w的最大值和最小值。

2.2 目標(biāo)函數(shù)的設(shè)定

目標(biāo)函數(shù)是衡量粒子優(yōu)劣的標(biāo)準(zhǔn)，在算法每一次迭代的過程中，需要根據(jù)目標(biāo)函數(shù)值來更新粒子的位置。假設(shè)定位區(qū)域內(nèi)部署了m個信標(biāo)節(jié)點(diǎn)，其坐標(biāo)為(xi，yi，zi)，i=1,2…，m，未知節(jié)點(diǎn)坐標(biāo)為(x，y，z)，通過RSSI方法測量得到的距離為di。為了降低測距誤差，將未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)的測量距離和估算距離的均方誤差作為優(yōu)化的目標(biāo)函數(shù)，目標(biāo)函數(shù)為

f(x,y,z)=

(9)

2.3 方法流程

(1)在目標(biāo)區(qū)域部署5個傳感器信標(biāo)節(jié)點(diǎn)，通過RSSI方法得到未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離di。

(2)初始化種群。初始粒子i的位置Xi=(xi,1xi,2…xi,d)，速度為Vi= (vi,1vi,2…vi,d)。

(3)評價每個粒子的適應(yīng)度(即目標(biāo)函數(shù)值)，將當(dāng)前粒子的位置和適應(yīng)值存儲在各粒子的pbest中，將所有pbest中適應(yīng)值最優(yōu)個體的位置和適應(yīng)值存儲于gbest中。

(4)用式(7)和式(8)來更新粒子的速度和位置。

(5)對于每個粒子，將其適應(yīng)值與其經(jīng)歷過的最好位置作比較，如果較好，則將其作為當(dāng)前的最好位置。

(6)比較當(dāng)前所有pbest和gbest的值，更新gbest。

(7)若滿足迭代終止條件，輸出全局歷史最優(yōu)解，否則返回步驟(4)繼續(xù)尋優(yōu)。

3 仿真結(jié)果及分析

為了驗(yàn)證和分析本文方法的定位精度、抗噪等性能，進(jìn)行了Matlab仿真實(shí)驗(yàn)，并與四邊測量法、加權(quán)最小二乘法以及文獻(xiàn)[6]提出的RSSI加權(quán)質(zhì)心算法進(jìn)行了對比。由于在井下特殊環(huán)境下，RSSI測距精度受其影響，將仿真環(huán)境設(shè)為長5 m、寬5 m、高6 m的長方體三維區(qū)域。RSSI測距模型中的高斯噪聲標(biāo)準(zhǔn)差為8，信標(biāo)節(jié)點(diǎn)密度為33%。定位誤差為單次實(shí)驗(yàn)得出的估計節(jié)點(diǎn)與未知節(jié)點(diǎn)間距離的差值。平均定位誤差則為實(shí)驗(yàn)重復(fù)30次得出的定位誤差的均值。

3.1 平均定位誤差

本文方法定位效果圖如圖2。節(jié)點(diǎn)總數(shù)為15，其中信標(biāo)節(jié)點(diǎn)5個，按照本文節(jié)點(diǎn)部署規(guī)則布置；未知節(jié)點(diǎn)10個，隨機(jī)分布在三維區(qū)域內(nèi)。未知節(jié)點(diǎn)與估計節(jié)點(diǎn)間的連線表示定位誤差。定位的仿真數(shù)據(jù)見表1，平均定位誤差為0.877 m。

圖2 定位效果圖

表1 定位仿真數(shù)據(jù)

3.2 性能對比分析

在本文設(shè)定的仿真環(huán)境中將本文方法與四邊測量法、加權(quán)最小二乘法和RSSI加權(quán)質(zhì)心法的性能進(jìn)行對比，實(shí)驗(yàn)重復(fù)30次得出的平均定位誤差的數(shù)據(jù)特征見表2，單次實(shí)驗(yàn)誤差仿真圖如圖3。

表2 平均定位誤差對比

(a) 四邊測量法 (b) 加權(quán)最小二乘法

(c) RSSI加權(quán)質(zhì)心法 (d) 本文方法

分析表2中的數(shù)據(jù)可知本文方法標(biāo)準(zhǔn)差最小，即圍繞均值波動的幅度最小，算法最穩(wěn)定，四邊測量法標(biāo)準(zhǔn)差與均值相比波動最大，定位性能最不穩(wěn)定；本文算法極差最小，也就是誤差變化幅度最穩(wěn)定，而四邊測量法和RSSI加權(quán)質(zhì)心法極差較大，因?yàn)镽SSI加權(quán)質(zhì)心算法受網(wǎng)絡(luò)連通度影響較大，誤差波動最不穩(wěn)定。圖3定位誤差值中可以看出，四邊測量法的定位誤差最大，四邊測量法和加權(quán)最小二乘法都是通過測距來估計未知節(jié)點(diǎn)的，所以易造成誤差積累。RSSI加權(quán)質(zhì)心算法定位誤差比四邊測量法和加權(quán)最小二乘法稍小，但是當(dāng)部分信標(biāo)節(jié)點(diǎn)失效時，該算法穩(wěn)定性會急劇下降。而本文算法是在四邊測量法的基礎(chǔ)上對測距誤差進(jìn)行優(yōu)化，由上圖可知定位誤差明顯小于其他三種方法，平均定位誤差可降至0.877 m，對于定位精度和穩(wěn)定性綜合考慮，本文算法更優(yōu)。

由于在巷道中無線傳輸信號受到惡劣環(huán)境影響，為分析算法性能，仿真得出四種定位算法在不同噪聲強(qiáng)度下的平均定位誤差如圖4。高斯白噪聲標(biāo)準(zhǔn)差取值從5遞增到20，所有平均定位誤差都隨著噪聲強(qiáng)度的升高而增加，當(dāng)噪聲強(qiáng)度超過13之后誤差增加的幅度均有明顯提升。四邊測量法的平均定位誤差從2.15 m增加到9.45 m，增長幅度最高，因?yàn)樗倪厹y量法受測距影響較大。本文算法平均定位誤差由1.21 m增長到4.65 m，增長幅度最小，因此抗噪性最好。

圖4 噪聲強(qiáng)度對定位誤差的影響

定位誤差與信標(biāo)節(jié)點(diǎn)密度關(guān)系如圖5。信標(biāo)節(jié)點(diǎn)密度由10%增加到40%，RSSI加權(quán)質(zhì)心法的平均定位誤差由4.75 m下降到0.95 m，誤差下降幅度較大，這是由于質(zhì)心算法對網(wǎng)絡(luò)連通度要求較高。四邊測量法只用四個信標(biāo)節(jié)點(diǎn)定位，隨著信標(biāo)節(jié)點(diǎn)密度的增加定位精度無明顯提高。本文算法平均定位誤差從2.82 m下降到0.76 m，定位精度明顯好于其他三種算法，穩(wěn)定性好于RSSI加權(quán)質(zhì)心算法，當(dāng)部分節(jié)點(diǎn)失效時，網(wǎng)絡(luò)連通性下降，仍然可以保持良好的定位精度。

圖5 定位誤差與信標(biāo)節(jié)點(diǎn)密度的關(guān)系

4 結(jié) 語

本文根據(jù)井下巷道的復(fù)雜環(huán)境提出一種基于粒子群優(yōu)化的井下目標(biāo)定位方法。結(jié)合井下巷道的特點(diǎn)規(guī)則放置信標(biāo)節(jié)點(diǎn)，減小節(jié)點(diǎn)間通信干擾，合理分配資源。在井下RSSI測距模型的基礎(chǔ)上引入線性遞減權(quán)重粒子群優(yōu)化算法對測距誤差進(jìn)行優(yōu)化。將未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)間的估計距離和測量距離的均方誤差作為粒子群算法優(yōu)化的目標(biāo)函數(shù)，再通過算法的迭代運(yùn)算找到適應(yīng)性強(qiáng)的粒子。仿真實(shí)驗(yàn)顯示該算法較對比算法定位精度更高，抗噪性更好，可靠穩(wěn)定，在井下巷道環(huán)境中適應(yīng)性更強(qiáng)。

參考文獻(xiàn)：

[1] HU Q S，ZHANG S，WU L X，et al. Localization techniques of mobile objects in coal mine：challenges，solutions and trends[J] .Journal of China Coal Society,2016,41(5):1059-1068.

[2] 王剛剛，王正.無線傳感器網(wǎng)絡(luò)定位算法原理與研究進(jìn)展概述[J] .木工機(jī)床，2016(2)：18-20.

[3] 任子暉，顧靚雨，周萌萌.基于無線傳感器網(wǎng)絡(luò)的改進(jìn)RSSI井下定位算法的礦井人員定位系統(tǒng)設(shè)計[J].煤礦開采，2015，20(3)：136-139.

[4] 朱曉娟，王軍號，孟祥瑞.煤礦井下無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)三維定位算法[J].計算機(jī)應(yīng)用，2012，32(4)：927-931.

[5] 劉暢.井下無線傳感器網(wǎng)絡(luò)的RSSI比例差分定位算法[J].電腦知識與技術(shù)，2017，13(6)：44-46.

[6] 方旺盛，雷高祥，李寧.基于礦井三維WSNs多重覆蓋和RSSI的加權(quán)質(zhì)心算法[J].傳感器與微系統(tǒng)，2016，35(5)：128-131.

[7] 李寧，王李管，賈明濤，等.基于改進(jìn)遺傳算法的礦井人員定位新算法[J].中南大學(xué)學(xué)報，2016,47(3)：930-935.

[8] DU W B ，GAO Y ，LIU C，et al.Adequate is better：partical swarm optimization with limited-information[J].Applied Mathematics & Computation,2015,268：832-838.

[9] TAHERKHANI M ，SAFABAKHSH R .A novel stability-based adaptive intertia weight for partical swarm optimization[J].Applied Soft Computing,2016,38：281-295.

[10] 孫波，劉冬陽，徐奉，等.基于RSSI的煤礦井下巷道定位技術(shù)誤差分析[J].煤炭學(xué)報，2014，39(S2)：609-614.

[11] ZHANG B H，F(xiàn)AN J，DAI G J,et al.A hybrid localization approach in 3D wireless sensor network[J].International Journal of Distributed Sensor Networks，2015:20.

[12] SHI Y，EBERHART R C.A modified particle swarm optimizer[J].Proceedings of IEEE International Conference on Evolutionary Computation，Anchorage,1998:69-73.

[13] 楊英杰.粒子群算法及其應(yīng)用研究[M].北京：北京理工大學(xué)出版社，2017：14-20.

[14] 郭雁一夫，劉宏立，徐琨，等.基于WSN的井下巷道RSSI性能分析[J].計算機(jī)工程與應(yīng)用，2016,52(17)：128-132.

[15] ZHANG Y D，WANG S H，JI G L. A comprehensive survey on partical swarm optimization algorithm and its applications[J]. Mathematical Problems in Engineering,2015(1)：1-38.

[16] TRELEA I .The partical swarm optimization algorithm：convergence analysis and parameter selection[J].Information Processing Letters，2016，85(6)：317-325.