趙 強

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

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

趙 強

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

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

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

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)由于強大的數(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é)點定位是對所有應(yīng)用的先決條件，只有已知傳感器節(jié)點接收數(shù)據(jù)位置，才有利用價值。目前節(jié)點定位方法主要分為兩種，一種是基于測距定位，另外一種是基于非測距定位[3-5]?；跍y量距離方法包括接受信號強度(RSSI)[6-7]，到達(dá)時間(TOA)，到達(dá)時間差(TDOA)[8]，到達(dá)角度測量(AOA)[9]等。非測距算法不需要距離信息和角度信息，這種算法是基于網(wǎng)絡(luò)連接和其他信息來實現(xiàn)定位，如三角形內(nèi)點信息APIT算法[10]，質(zhì)心算法[11]，節(jié)點間跳數(shù)信息DV-HOP算法等[12]。

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

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

1 相關(guān)工作

1.1 TDOA測量法

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

(1)

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

1.2 量子粒子群算法

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

(2)

(3)

(4)

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

(5)

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

2 改進MCB算法

2.1 蒙特卡羅盒子定位算法

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

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

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

(6)

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

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

(7)

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

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

(8)

(9)

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

2.2 QPSO-MCL算法

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

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

(10)

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

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

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

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

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

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

(5)利用QPSO-MCL算法更新Pk-1時刻節(jié)點的估計位置。

3 算法仿真與分析

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

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

圖1 仿真結(jié)果1

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

圖2 仿真結(jié)果2

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

圖3 仿真結(jié)果3

4 結(jié)束語

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

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

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

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

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

[5] 趙靈鍇.無線傳感器網(wǎng)絡(luò)移動節(jié)點定位算法研究[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].計算機仿真,2011,28(5):163-166.

[12] 石為人,賈傳江,梁煥煥.一種改進的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報，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] 張健,李鷗. 改進的無線傳感器網(wǎng)絡(luò)TDOA定位算法[J]. 計算機工程與應(yīng)用, 2010, 46(16):117-120.

[18] 王新芳,張冰,馮友兵. 基于量子粒子群優(yōu)化的WSN節(jié)點定位改進[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

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

10.16180/j.cnki.issn1007-7820.2017.05.005

TN926

A

1007-7820(2017)05-016-04