動(dòng)態(tài)WSN中基于改進(jìn)的蒙特卡羅盒子定位算法

趙 強(qiáng)

(蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

動(dòng)態(tài)WSN中基于改進(jìn)的蒙特卡羅盒子定位算法

趙 強(qiáng)

(蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

針對蒙特卡羅盒子定位算法在動(dòng)態(tài)WSN定位方面所存在的計(jì)算量大，精確度不高以及耗時(shí)等缺點(diǎn)。提出一種量子粒子群算法優(yōu)化蒙特卡羅盒子的定位算法(QPSO-MCB)。該算法不僅減小了解空間的搜索時(shí)間，同時(shí)提高了采樣效率，有效改善了蒙特卡羅盒子定位算法的高誤差和低效率。仿真結(jié)果表明，與蒙特卡羅盒子算法相比，平均采樣效率有了明顯提高，特別當(dāng)移動(dòng)速度增加的情況下，定位誤差反而下降。

動(dòng)態(tài)的無線傳感器網(wǎng)絡(luò)；定位；量子粒子群優(yōu)化算法；蒙特卡羅盒子定位算法

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)由于強(qiáng)大的數(shù)據(jù)獲取和處理能力被廣泛應(yīng)用。因此，WSN發(fā)展前景已得到越來越多的關(guān)注[1-2]。定位技術(shù)在WSN中是重要研究領(lǐng)域，被廣泛應(yīng)用于環(huán)境監(jiān)測、國防軍事、預(yù)防控制等。在WSN中，網(wǎng)絡(luò)節(jié)點(diǎn)定位是對所有應(yīng)用的先決條件，只有已知傳感器節(jié)點(diǎn)接收數(shù)據(jù)位置，才有利用價(jià)值。目前節(jié)點(diǎn)定位方法主要分為兩種，一種是基于測距定位，另外一種是基于非測距定位[3-5]?；跍y量距離方法包括接受信號強(qiáng)度(RSSI)[6-7]，到達(dá)時(shí)間(TOA)，到達(dá)時(shí)間差(TDOA)[8]，到達(dá)角度測量(AOA)[9]等。非測距算法不需要距離信息和角度信息，這種算法是基于網(wǎng)絡(luò)連接和其他信息來實(shí)現(xiàn)定位，如三角形內(nèi)點(diǎn)信息APIT算法[10]，質(zhì)心算法[11]，節(jié)點(diǎn)間跳數(shù)信息DV-HOP算法等[12]。

上述定位算法適合在靜止的傳感網(wǎng)絡(luò)中，具有較高的定位效率和定位精度。但當(dāng)WSN中節(jié)點(diǎn)移動(dòng)進(jìn)行時(shí)，由于造成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化，節(jié)點(diǎn)之間距離也會(huì)發(fā)生動(dòng)態(tài)變化，上述算法定位精確度也會(huì)隨著節(jié)點(diǎn)移動(dòng)驟然下降。所以為了使能傳感器網(wǎng)絡(luò)在不同環(huán)境下進(jìn)行定位，特別是在移動(dòng)環(huán)境下，可以進(jìn)行精確的定位，已經(jīng)是一個(gè)熱點(diǎn)話題。Hu和Evans在2004年文獻(xiàn)[13]提出一種MCL(Monte Carlo Localization)算法，該算法適用于動(dòng)態(tài)傳感網(wǎng)定位算法。但是傳統(tǒng)的蒙特卡羅要求較大的計(jì)算量和能量。在MCL算法基礎(chǔ)上，文獻(xiàn)[14]又提出了MCB，MCB算法相對于MCL在有效樣本區(qū)域做了改進(jìn)，但依舊延續(xù)MCL缺點(diǎn)。學(xué)者們又提出了RSS-MCL[15]、MMCL[16]等定位算法。

為了克服蒙特卡羅盒子定位算法的缺點(diǎn)，本文提出用量子粒子群算法去改進(jìn)蒙特卡羅盒子算法，該改進(jìn)的算法可以提高采樣效率低，減少重采樣的次數(shù)，降低能量的消耗以及增加粒子多樣性。

1 相關(guān)工作

1.1 TDOA測量法

同步測量法[17]是通過兩種不同信號到達(dá)時(shí)間差，根據(jù)已知兩種信號傳播速度，乘以信號傳播時(shí)間，直接把時(shí)間差轉(zhuǎn)為為距離差?；赥DOA測量，建立公式為

(1)

上式中，(x,y)是錨節(jié)點(diǎn)的坐標(biāo)；(Xi,Yi)是移動(dòng)未知節(jié)點(diǎn)不同位置坐標(biāo)；v是信號傳播速度，Pi,m是第m個(gè)錨節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)i的距離。由式(1)得到初始的一個(gè)觀測值，與未知節(jié)點(diǎn)的通信半徑比得到一個(gè)定位誤差 ,假設(shè)Vmax是移動(dòng)未知節(jié)點(diǎn)的通信半徑。這種形式要求未知節(jié)點(diǎn)與錨節(jié)點(diǎn)時(shí)間嚴(yán)格同步。但是現(xiàn)實(shí)中很難出現(xiàn)這種同步，所以本文直接引用TDOA定位采用約束性最小二乘(CLS)算法，這種算法讓測量誤差達(dá)到最小。

1.2 量子粒子群算法

量子粒子群(Quantum Behaved Particle Swarm Optimization，QPSO)[18]算法是粒子群算法的改進(jìn)，它提高了尋找全局最優(yōu)解，全局搜索能力遠(yuǎn)遠(yuǎn)優(yōu)于PSO算法。QPSO算法簡單易行，計(jì)算量小且參數(shù)少，克服了局部最優(yōu)解，收斂速度快，精度高。QPSO算法為保證所有粒子的收斂性，主要迭代公式

(2)

(3)

(4)

P=(C1×Pid+C2×Pgd)/(C1+C2)

(5)

其中，u和C1和C2是[0,1]之間的隨機(jī)數(shù)；n是粒子的種群數(shù)；d是維數(shù)，Pbest是此時(shí)刻搜索平均最優(yōu)位置，pid表示的是所有粒子搜索最優(yōu)位，pgd表示全局搜索最好位置。β表示是收縮擴(kuò)張系數(shù)。β經(jīng)驗(yàn)值一般在[0.5,1]之間。根據(jù)收縮因子變化的值，β的值也會(huì)隨著迭代次數(shù)變化而變化。它關(guān)系到尋優(yōu)過程花費(fèi)時(shí)間，若它的值過小，造成陷入局部最優(yōu)。

2 改進(jìn)MCB算法

2.1 蒙特卡羅盒子定位算法

蒙特卡羅盒子定位算法是一種迭代的貝葉斯濾波，根據(jù)傳感器此時(shí)位置的信息，通過后驗(yàn)概率分布和樣本點(diǎn)的選取，預(yù)測節(jié)點(diǎn)下一時(shí)刻位置。MCB與蒙特卡羅定位算法類似，區(qū)別在于在初始化和預(yù)測階段。

(2)采樣階段。這個(gè)過程是從t-1時(shí)刻選擇樣本集L0，錨盒子的產(chǎn)生根據(jù)以下公式

上式，(xi,yi)是錨節(jié)點(diǎn)i的坐標(biāo)，ci是i跳的錨節(jié)點(diǎn)的個(gè)數(shù)，r是錨節(jié)點(diǎn)的通信半徑。在錨盒子內(nèi)采樣有效節(jié)點(diǎn)。由于不知道下一時(shí)刻的速度和運(yùn)動(dòng)方向，采用隨機(jī)運(yùn)動(dòng)模式，移動(dòng)節(jié)點(diǎn)在區(qū)間內(nèi)服從均勻分布則有

(6)

(3)過濾。從時(shí)刻k-1到k,根據(jù)未知節(jié)點(diǎn)獲得一跳和兩跳的錨節(jié)點(diǎn)信息，可以過濾樣本和刪除無效的樣本?？梢酝ㄟ^以下條件進(jìn)行過濾

filter(l)=?a∈A1,d(l,a)≤r∧?a∈A2,r

(7)

式中，A1是錨節(jié)點(diǎn)接受未知節(jié)點(diǎn)一跳信息；A2是錨節(jié)點(diǎn)鄰居節(jié)點(diǎn)接受點(diǎn)二跳信息；d(l,a)是未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離；

(4)重采樣。由于經(jīng)過第2、3步時(shí)，過濾后的樣本數(shù)已經(jīng)不足N，所以必須重復(fù)以上兩個(gè)步驟，直到樣本數(shù)可以達(dá)到N；

(8)

(9)

根據(jù)式(8)和式(9)計(jì)算未知節(jié)點(diǎn)的估位置。

2.2 QPSO-MCL算法

本文是以蒙特卡羅盒子定位算法為基礎(chǔ)，由于MCB定位算法本身采樣不高，計(jì)算量大耗時(shí)間，并且粒子多樣性不夠。而量子粒子群搜索能力強(qiáng)，收斂速度快，在一定程度上恰好達(dá)到了互補(bǔ)。并且為防止脫離粒子搜索空間，設(shè)搜索范圍[0,L]。

假設(shè)有M個(gè)粒子，每一個(gè)粒子存儲(chǔ)測量距離與算法的誤差，這樣就會(huì)組成一個(gè)M×N的矩陣，利用式(3)～式(5)搜索空間最小誤差，因此目標(biāo)函數(shù)為

(10)

2.3 QPSO-MCB算法設(shè)計(jì)

根據(jù)蒙特卡羅盒子定位算法，采樣區(qū)域是由Vmax為采樣半徑的圓。在采樣范圍內(nèi)，QPSO首先利用適應(yīng)度函數(shù)，搜索空間內(nèi)最優(yōu)的粒子，并且保證粒子數(shù)目達(dá)到N。具體算法步驟如下：

(1)初始化。在移動(dòng)節(jié)點(diǎn)運(yùn)動(dòng)前，先設(shè)置未知節(jié)點(diǎn)的定位誤差error值、初定坐標(biāo)和最大速度；

(2)采樣階段。在錨節(jié)點(diǎn)多跳信息構(gòu)造矩形錨節(jié)點(diǎn)盒子選取樣本點(diǎn)，根據(jù)TDOA測距公式，得到此時(shí)刻測量距離，利用式(9)～式(11)得到QPSO每一個(gè)粒子代表采樣粒子的誤差。此時(shí)，當(dāng)?shù)玫絋DOA與通信距離誤差，和蒙特卡羅盒子定位所產(chǎn)生的誤差相比較，得到最小的誤差作為量子粒子群的粒子；

(3)過濾階段。從20個(gè)粒子當(dāng)中選取最小的誤差。從而尋求出最好的錨節(jié)點(diǎn)，并且給錨節(jié)點(diǎn)賦予相應(yīng)的權(quán)值；

(4)估計(jì)位置。在經(jīng)過步驟(2)和步驟(3)后利用k-1時(shí)刻的位置與采樣的錨節(jié)點(diǎn)估測k時(shí)刻的位置；

(5)利用QPSO-MCL算法更新Pk-1時(shí)刻節(jié)點(diǎn)的估計(jì)位置。

3 算法仿真與分析

實(shí)驗(yàn)在 Intel(R) Core(TM) i5-2450M CPU，主頻 2.80 GHz、2.80 GHz，4 GB 內(nèi)存平臺(tái)，Matlab7.0仿真環(huán)境中進(jìn)行的。本文從錨節(jié)點(diǎn)密度、移動(dòng)節(jié)點(diǎn)運(yùn)動(dòng)速度以及定位精度3個(gè)方面對MCL、MCB和QPSO-MCB這3種算法進(jìn)行對比分析。實(shí)驗(yàn)仿真中，隨機(jī)分布在100 m×100 m矩形區(qū)域內(nèi)，未知節(jié)點(diǎn)移動(dòng)采用隨機(jī)移動(dòng)模型，錨節(jié)點(diǎn)通信范圍設(shè)置為10 m。實(shí)驗(yàn)中用到錨節(jié)點(diǎn)密度、節(jié)點(diǎn)密度，未知節(jié)點(diǎn)速度、定位誤差等參數(shù)定義。默認(rèn)仿真參數(shù)：錨節(jié)點(diǎn)個(gè)數(shù)為20，最大速度為20 m/s,節(jié)點(diǎn)的規(guī)模為80，粒子的個(gè)數(shù)為20。

定位的精確度直接與錨節(jié)點(diǎn)的數(shù)量有關(guān)，在圖1顯示錨節(jié)點(diǎn)密度對定位誤差的影響，密度增加定位誤差減小，并且當(dāng)密度數(shù)達(dá)到2時(shí)，定位誤差已經(jīng)趨近于平穩(wěn)，因?yàn)殄^節(jié)點(diǎn)密度是指在一跳和兩跳范圍內(nèi)平均錨節(jié)點(diǎn)的個(gè)數(shù)，所以在錨節(jié)點(diǎn)稀少情況，QPSO-MCB算法的定位誤差要小于其他兩個(gè)算法。

圖1 仿真結(jié)果1

節(jié)點(diǎn)的最大運(yùn)行速度被當(dāng)做未知節(jié)點(diǎn)的通信半徑，以這個(gè)通信半徑所形成圓，來預(yù)測下一時(shí)刻未知節(jié)點(diǎn)的位置，因?yàn)樗俣仍娇欤A(yù)測區(qū)域越大，監(jiān)聽到的錨節(jié)點(diǎn)數(shù)量越多，所以對定位精度就會(huì)越高，圖2顯示節(jié)點(diǎn)的移動(dòng)速度對節(jié)點(diǎn)誤差影響。速度雖然在變化，但是所有算法定位精度最后只是趨近一個(gè)范圍。在MCB的基礎(chǔ)上提出QPSO-MCB算法，無論速度怎么樣變化，它一直保持在MCB定位精度以下，其他兩個(gè)定位算法則變化趨勢相似。由圖4可知，最大速度4 m/s之前，所有算法趨于下降，隨后稍微上升，變化也不是很大，說明蒙特卡羅算法適于移動(dòng)節(jié)點(diǎn)定位。

圖2 仿真結(jié)果2

標(biāo)準(zhǔn)誤差是估測的位置與實(shí)際位置的誤差。圖3是標(biāo)準(zhǔn)誤差與時(shí)間關(guān)系圖。圖3顯示所有算法在前4 s，定位誤差都是急速下降，原因是初始時(shí)，設(shè)置一個(gè)真實(shí)的位置，在后來的定位時(shí)，由于定位方法不同以及速度、方向的不確定性，所以會(huì)出現(xiàn)誤差不同，但是本文提出的方法，在縮小估測區(qū)域前提下，又對樣本點(diǎn)精確地選取，QPSO-MCB定位誤差始終小于上面兩種算法。圖3也顯示，在一段時(shí)間后，定位誤差會(huì)在一個(gè)最小的值上下浮動(dòng)。

圖3 仿真結(jié)果3

4 結(jié)束語

為了使MCB定位算法能更好的適用于動(dòng)態(tài)WSN，本文在MCB定位算法的基礎(chǔ)上，提出了一種MCB算法與量子粒子群算法相結(jié)合優(yōu)化算法，即QPSO-MCB算法。該算法雖然在搜索空間時(shí)消耗能量，但同時(shí)加快了收斂速度，提高了樣本的多樣性，使得定位精度有所提高，仿真表明，節(jié)點(diǎn)在移動(dòng)速度逐漸增加和錨節(jié)點(diǎn)的密度高的情況下，QPSO-MCB算法相對于其他兩種算法，定位精確度逐漸增加。

[1] 崔莉,鞠海玲,苗勇,等.無線傳感器網(wǎng)絡(luò)研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展, 2005, 42(1):163-174.

[2] 焦磊.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的分析與研究[D].濟(jì)南：山東大學(xué),2008.

[3] 吳大中,張蒙蒙.基于移動(dòng)節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)定位算法[J].物聯(lián)網(wǎng)技術(shù),2012(5):43-46.

[4] 王魯佳,田龍強(qiáng),胡超.無線定位技術(shù)綜述[J].先進(jìn)技術(shù)研究通報(bào),2010,4(3):2-7.

[5] 趙靈鍇.無線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法研究[D].成都:成都理工大學(xué),2011.

[6] Li X.RSS-based location estimation with unknown pathloss model[J].IEEE Transactions on Wireless Communications, 2006,5(12)：3626-3633.

[7] 閆馳.基于PSO-BP神經(jīng)網(wǎng)絡(luò)的無線傳感器網(wǎng)絡(luò)定位算法[J]. 電子科技,2016,29(4): 56-58.

[8] Girod L,Estrin D. Robust range estimation using acoustic

and multimodal sensing[C].Hawaii，USA：Proceeding ofthe IEEE/RSJ Inernational Conference on Intelligent Robots and Systems(IROS 01), 2001.

[9] Niculescu D, Nath B. Ad hoc positioning system (APS) using AoA[C].San Francisco California,USA:IEEE Infocom,2003.

[10] Cheng W,Li J,Li H.An improved APIT location algorithm for wireless sensor networks[J].Advances in Electrical Engineering and Automation,2012,139(2): 113-119．

[11] 何艷麗.無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法研究[J].計(jì)算機(jī)仿真,2011,28(5):163-166.

[12] 石為人,賈傳江,梁煥煥.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào)，2011,24(1):83-87.

[13] Hu L, Evans D. Localization for mobile sensor networks[C].Philadelphia, PA, USA：International Conference on Mobile Computing and Networking,2004.

[14] Baggio A, Langendoen K. Monte Carlo localization for mobile wireless sensor networks[J]. Ad Hoc Networks,2008,6(5):718-733.

[15] Yu Q, Wang W, Qin Z, et al. RSS-based Monte Carlo nodes localization in wireless ad hoc networks[C].Xi’an:International Conference on Communications, Circuits and Systems,IEEE,2009.

[16] Yi J, Yang S, Cha H. Multi-hop-based monte carlo localization for mobile sensor networks[C].Chengdu:IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks,2007.

[17] 張健,李鷗. 改進(jìn)的無線傳感器網(wǎng)絡(luò)TDOA定位算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2010, 46(16):117-120.

[18] 王新芳,張冰,馮友兵. 基于量子粒子群優(yōu)化的WSN節(jié)點(diǎn)定位改進(jìn)[J]. 計(jì)算機(jī)科學(xué),2012,39(51):129-131.

Improved Monte Carlo Boxed Localization for Mobile Wireless Sensor Networks

ZHAO Qiang

(School of Electronics and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

A new node localization algorithm QPSO-MCB is proposed for mobile WSNs to reduce the time in the search space and improve the sampling efficiency of the Monte Carlo localization algorithm. Simulation results demonstrate that compared with the Monte Carlo algorithm boxes, the proposed QPSO-MCB algorithm improve the sampling speed. Especially with the moving speed increasing, the positioning error is decreased.

mobile WSN; localization; QPSO algorithm; MCB algorithm

2016- 06- 27

趙強(qiáng)(1990-)，男，碩士研究生。研究方向：交通物聯(lián)網(wǎng)。

10.16180/j.cnki.issn1007-7820.2017.05.005

TN926

A

1007-7820(2017)05-016-04