基于測距權(quán)重的蒙特卡羅定位改進(jìn)算法

周春月, 張洪婷

(北京交通大學(xué) 電子信息工程學(xué)院，北京 100044)

?

基于測距權(quán)重的蒙特卡羅定位改進(jìn)算法

周春月, 張洪婷

(北京交通大學(xué) 電子信息工程學(xué)院，北京 100044)

針對傳統(tǒng)蒙特卡羅定位算法采樣效率低，對錨節(jié)點密度要求高的特點，本文基于蒙特卡羅定位算法MCL提出一種改進(jìn)的移動傳感器網(wǎng)絡(luò)的節(jié)點定位算法IMCB.該算法利用歷史錨節(jié)點信息和RSSI測距,以及運動模型的改進(jìn)對待定位節(jié)點的位置采樣范圍進(jìn)行了進(jìn)一步限制，對有效采樣點的權(quán)重進(jìn)行了區(qū)分.仿真結(jié)果表明：該算法的定位精度相比MCB算法提高了16.6%.

無線傳感器網(wǎng)絡(luò)；蒙特卡羅定位算法；接收信號強(qiáng)度指示；運動模型

無線傳感器網(wǎng)絡(luò)現(xiàn)今在很多需要監(jiān)測與控制的環(huán)境中得到廣泛應(yīng)用，如環(huán)境監(jiān)測、農(nóng)業(yè)監(jiān)測、智能交通和安全監(jiān)控等.很多應(yīng)用都依賴于傳感器節(jié)點的位置信息，如應(yīng)用中的一些監(jiān)測信息，如果沒有了位置信息就毫無意義.傳感器節(jié)點定位即傳感器節(jié)點確定自身位置的過程.最簡單的辦法就是在每個傳感器節(jié)點上安裝GPS，但由于無線傳感器網(wǎng)絡(luò)節(jié)點本身資源有限，對能耗限制苛刻，而且這種解決方案工程量大且成本高，在實際應(yīng)用中不可行.大多數(shù)算法是基于錨節(jié)點的定位算法，在這種算法中，錨節(jié)點通過GPS或人工配置事先獲得自身的位置，其余的未知節(jié)點則根據(jù)錨節(jié)點的位置及網(wǎng)絡(luò)拓?fù)浠蛘吖?jié)點之間的距離信息推算出自己的位置.

無線傳感器網(wǎng)絡(luò)節(jié)點的定位算法可以分為基于測距的定位算法和非測距的定位算法兩種：1)基于測距的定位算法通過TOA[1]、TDOA[2]、AOA[3]及

RSSI[4]等測距技術(shù)獲得普通節(jié)點與錨節(jié)點之間的距離，然后利用空間幾何規(guī)則通過三角定位算法、三邊定位算法、多邊定位算法和最大似然估計算法等推算出未知節(jié)點的位置.2)非測距的定位算法不需要測量節(jié)點之間的距離，而是通過未知節(jié)點與周圍節(jié)點的連接度計算得到未知節(jié)點的位置，如質(zhì)心定位[5]、DV-Hop[6]定位、凸規(guī)劃[7]和APIT[8]定位等.

固定的無線傳感器網(wǎng)絡(luò)已有諸多相對成熟的定位算法,但不能直接應(yīng)用于移動傳感器網(wǎng)絡(luò).文獻(xiàn)[9]針對無線移動傳感器網(wǎng)絡(luò)的節(jié)點定位提出了蒙特卡洛定位算法.在該算法中未知節(jié)點根據(jù)運動模型在自身可能存在的位置范圍內(nèi)進(jìn)行位置采樣，再依據(jù)網(wǎng)絡(luò)中已知的錨節(jié)點位置信息過濾掉不符合實際條件的采樣點，通過這一系列的位置采樣來估計未知節(jié)點的位置.

鑒于蒙特卡羅定位算法的位置采樣效率低，文獻(xiàn)[10]在MCL算法的基礎(chǔ)上提出了蒙特卡羅盒定位算法，該算法通過構(gòu)造錨箱更快地獲取有效位置采樣，提高了節(jié)點定位的精度和效率.文獻(xiàn)[11]提出了基于RSSI的蒙特卡羅定位算法，利用錨節(jié)點與未知節(jié)點間的RSSI測距縮小錯箱范圍.文獻(xiàn)[12]提出權(quán)重蒙特卡羅定位(Weighted Monte Carlo Localization，WMCL)算法，充分利用普通鄰居節(jié)點在t-1時刻的估計位置信息對t時刻的位置估計采樣區(qū)域進(jìn)行限制及對位置采樣進(jìn)行過濾.除了以上改進(jìn)策略，還有諸多對基于蒙特卡羅定位算法的無線移動傳感器網(wǎng)絡(luò)節(jié)點定位算法的研究，如自適應(yīng)權(quán)重[13]和虛擬錨節(jié)點[14]等.

本文作者基于蒙特卡羅定位算,提出了一種新的移動傳感器網(wǎng)絡(luò)的節(jié)點定位算法IMCB.該算法利用歷史錨節(jié)點結(jié)合RSSI測距縮小待定位節(jié)點的位置采樣范圍，并通過當(dāng)前鄰居節(jié)點的RSSI測距區(qū)分了有效采樣點的權(quán)重，此外，改進(jìn)的運動模型有利于節(jié)點運動方向的預(yù)測.

1 MCL算法

1)初始化階段，每個普通節(jié)點構(gòu)造一個自身的可能位置采樣集Lt.

(1)

3)過濾階段，普通節(jié)點根據(jù)收到的一跳及兩跳錨節(jié)點的觀測值對Lt中的無效位置采樣點進(jìn)行過濾，收到消息的一跳鄰居普通節(jié)點應(yīng)當(dāng)在以該錨節(jié)點為圓心，以r為半徑的圓內(nèi)，而兩跳鄰居普通節(jié)點應(yīng)當(dāng)在以該錨節(jié)點為圓心，半徑為(r，2r)的圓環(huán)內(nèi)，不符合該條件的位置抽樣為無效采樣，即：

(2)

(3)

2 基于MCL的改進(jìn)算法——IMCB

針對MCL算法的位置采樣效率低的問題， MCB算法通過充分利用未知節(jié)點能“聽”到的一跳(兩跳)錨節(jié)點信息建立錨箱限制位置預(yù)測的采樣范圍，有效提高了節(jié)點定位的精度和效率[10].但是MCB仍然存在一些問題：1)在位置估計階段，MCB將所有可用采樣點進(jìn)行平均得到最后估計位置，沒有很好的區(qū)分各可用采樣點的權(quán)重;2)MCB與MCL算法中所采用的運動模型均為改進(jìn)的隨機(jī)中間點運動模型(Random Waypoint Mobility Model)，節(jié)點在每個時隙內(nèi)的運動方向任意選取，然而在實際的節(jié)點運動中，節(jié)點的運動方向范圍應(yīng)該是有限的.為了更進(jìn)一步改善MCB算法的抽樣效率和解決如上兩個問題，本文作者利用歷史錨節(jié)點更進(jìn)一步縮小未知節(jié)點的位置采樣區(qū)域；利用未知節(jié)點與鄰居節(jié)點之間的接收信號強(qiáng)度指示信息，對采樣集中的樣點進(jìn)行權(quán)重優(yōu)化；并在采樣階段根據(jù)節(jié)點的可能運動方向?qū)?jié)點進(jìn)行動態(tài)的運動預(yù)測.

2.1 建立采樣箱

MCL進(jìn)行位置采樣時有兩個區(qū)域：1)位置采樣區(qū)域，即根據(jù)Lt-1和vmax建立的節(jié)點可能的運動范圍，用于抽取待過濾的位置樣點；2)有效樣點區(qū)域，是根據(jù)一跳錨和兩跳錨建立的節(jié)點實際位置存在的范圍，用于過濾不合格的位置樣點.當(dāng)vmax增大時，位置采樣區(qū)域面積變大，或者當(dāng)錨節(jié)點密度增加時，可用樣點區(qū)域面積減小，此時就會造成大量的無效采樣.為了減少無效采樣次數(shù)， Baggio 和 Langendoen[10]通過建立錨箱來減小位置采樣區(qū)域，將位置采樣范圍限制在以未知節(jié)點能“聽”到的一跳(兩跳)錨節(jié)點為中心，邊長為2r(4r)的矩形的重疊部分，即錨箱，如圖1陰影部分.

本文將進(jìn)一步縮小節(jié)點的位置采樣區(qū)域.假設(shè)已經(jīng)按MCB算法建立好了錨箱，根據(jù)待定位節(jié)點在t-1時刻的錨節(jié)點信息縮小節(jié)點的位置采樣區(qū)域面積，從而進(jìn)一步提高采樣效率.如圖2 (a)所示，nt-1是待定位節(jié)點在t-1時刻的位置，nt是待定位節(jié)點在t時刻的位置，st-1是待定位節(jié)點在t-1時刻的鄰居錨節(jié)點.因為nt-1一定在st-1的通信范圍內(nèi)，即d(nt-1,st-1)一定小于r，且nt的最大移動距離為vmax，所以nt一定在以st-1為圓心，r+vmax為半徑的圓內(nèi).

如圖2(b)所示，通過接收信號強(qiáng)度可計算nt-1到st-1的距離drss，根據(jù)如上原理，可以將nt限制在以st-1為圓心，drss+vmax為半徑的圓內(nèi)，更進(jìn)一步縮小了st-1對nt-1的限制范圍.如此，與MCB同理，建立該圓的外切正方形，X(st-1,j),Y(st-1,j)分別為t-1時刻的第j個錨節(jié)點的橫縱坐標(biāo)，則可求其與錨箱的重疊部分如下：

(4)

式中,m是待定節(jié)點在t-1時刻鄰居錨節(jié)點個數(shù).

如上建立好采樣箱之后，即可在采樣箱中對待定位節(jié)點進(jìn)行位置采樣.

2.2 過濾

在過濾階段，普通節(jié)點根據(jù)收到的一跳及兩跳錨節(jié)點的觀測值對Lt中的無效位置樣本進(jìn)行過濾，基本方法與MCL算法相同，加入歷史錨節(jié)點的限制條件即：

(5)

式中：H表示歷史錨節(jié)點集合.

關(guān)于運動模型對采樣點的限制，見2.4節(jié).為了獲取足夠的位置樣本，當(dāng)樣本集中的無效樣本被過濾后，重復(fù)前面的預(yù)測抽樣和過濾過程，直到滿足樣本數(shù)或到達(dá)抽樣輪次上限.

2.3 基于RSSI的采樣權(quán)重優(yōu)化

接收信號強(qiáng)度裝置成本低且容易實現(xiàn)，因此，本文作者提出了基于RSSI的權(quán)重算法對已經(jīng)獲得的采樣集中的有效采樣點進(jìn)行權(quán)重優(yōu)化.

RSSI權(quán)重位置估計分為無權(quán)重位置估計和有權(quán)重位置估計兩個階段.在無權(quán)重位置估計階段，普通節(jié)點根據(jù)已經(jīng)過濾的有效采樣點進(jìn)行平均位置估計，并將該位置估計與其誤差衡量發(fā)送給普通鄰居節(jié)點；在有權(quán)重位置估計階段，普通節(jié)點根據(jù)鄰居錨節(jié)點信息及鄰居節(jié)點的位置估計和其誤差衡量通過RSSI距離計算權(quán)重，更新估計位置.

(6)

(7)

2.4 基于運動模型的采樣預(yù)測優(yōu)化

基于運動模型的采樣預(yù)測優(yōu)化的基本思想是：運動模型對節(jié)點的運動方向進(jìn)行了限制，未知節(jié)點的預(yù)測采樣點也應(yīng)該限制在可能的運動方向范圍內(nèi).

2.4.1 運動模型的改進(jìn)

在MCL算法仿真中采用的運動模型是改進(jìn)的隨機(jī)中間點運動模型，該運動模型以節(jié)點的當(dāng)前位置為起始位置，在節(jié)點部署區(qū)域范圍內(nèi)任意選取一個位置作為目的位置以確定節(jié)點的運動方向，以(最小速率，最大速率)范圍內(nèi)任意值作為節(jié)點的運動速率向目的位置運動.該算法認(rèn)為在不同時間段內(nèi)的運動是相互獨立的，這就有可能造成節(jié)點有一些不切實際的運動行為，例如急轉(zhuǎn)180°.為此，本文在隨機(jī)中間節(jié)點運動模型的基礎(chǔ)上對節(jié)點的運動模型進(jìn)行改進(jìn)，將節(jié)點的運動方向限制在一個可實現(xiàn)的范圍內(nèi)，即節(jié)點所選擇的下一時刻的運動方向與原運動方向的夾角應(yīng)小于可實現(xiàn)的最大夾角.見圖5，圖5中nt-2、nt-1分別是前兩個時刻節(jié)點所在位置，nt是節(jié)點即將到達(dá)的位置.α是向量nt-1nt與nt-2nt-1的夾角，表示節(jié)點運動的轉(zhuǎn)角，Δφ是α的最大值.由此將α限制在Δφ范圍內(nèi)，避免了節(jié)點在運動過程中出現(xiàn)不切實際的過大轉(zhuǎn)角.

2.4.2 基于運動模型的采樣點預(yù)測優(yōu)化

定義估計最大轉(zhuǎn)向角Δφ為實際最大轉(zhuǎn)向角Δφ與修正角θ的和：

Δφ=Δφ+θ

(8)

(9)

σ1+σ2=1

(10)

3 IMCB定位算法仿真結(jié)果

本文基于文獻(xiàn)[9]的蒙特卡羅定位算法仿真器MCL-simulator對第2節(jié)提出的IMCB定位算法進(jìn)行了仿真驗證，并將其性能與MCL和MCB進(jìn)行了對比.仿真節(jié)點分布在500 m×500 m的正方形區(qū)域內(nèi)，區(qū)域內(nèi)隨機(jī)分布320個節(jié)點，其中包含若干個錨節(jié)點，錨節(jié)點數(shù)量根據(jù)仿真需要的錨節(jié)點密度而定，其余為普通節(jié)點.假設(shè)所有節(jié)點的通信半徑恒定為50 m.節(jié)點依據(jù)如2.4節(jié)的優(yōu)化運動模型在部署區(qū)域內(nèi)隨機(jī)運動，實際最大轉(zhuǎn)向角Δφ=60°.進(jìn)行方向預(yù)測時,取σ1=0.8，σ2=0.2，k=1.本文設(shè)定δ=120°，即當(dāng)mt-2mt-1σ1+gt-2gt-1σ2=0時，由于參考方向準(zhǔn)確度太低，估計最大轉(zhuǎn)向角Δφ=Δφ+θ=180°.執(zhí)行運動模型時，節(jié)點從(0,vmax)內(nèi)隨機(jī)選擇.sd是錨節(jié)點密度，表示在節(jié)點的一跳通信范圍內(nèi)的平均錨節(jié)點數(shù)為

(11)

式中：seed_num表示部署區(qū)域內(nèi)的錨節(jié)點總數(shù)；S是部署區(qū)域的總面積；本文仿真S等于500×500 m2,r等于50 m.

3.1 定位誤差

節(jié)點的定位誤差ER用節(jié)點的估計位置坐標(biāo)與真實位置坐標(biāo)的距離表示，計算方法如下

(12)

圖7為vmax= 0.2r，sd=1時節(jié)點定位誤差隨時間的變化曲線.節(jié)點的定位分為初始化階段和穩(wěn)定階段.在初始化階段，節(jié)點的定位誤差迅速降低，IMCB和MCB算法相對MCL更快進(jìn)入穩(wěn)定階段，IMCB定位誤差有明顯改善.此外，在第45時隙之后定位誤差呈上升趨勢，MCL由于誤差累積容易導(dǎo)致節(jié)點定位預(yù)測樣點數(shù)目不足，而使定位誤差繼續(xù)增加.相反，MCB和IMCB由于在位置預(yù)測時有錨箱的限制，防止了節(jié)點定位誤差的惡化. IMCB利用了歷史錨節(jié)點限制條件并對節(jié)點的運動方向進(jìn)行了預(yù)測，使抽樣范圍進(jìn)一步減小，同時RSSI權(quán)重優(yōu)化有效區(qū)分了位置采樣點接近真實位置的可能性，從而獲得比MCB更準(zhǔn)確的定位精度，定位誤差平均降低了16.6%.

3.2 最大速率對定位誤差的影響

誤差值是對特定速率值進(jìn)行多次定位后的平均誤差.圖8為sd=1時節(jié)點的定位誤差隨節(jié)點運動速率的變化曲線.可以看出，隨著vmax增大，在0.2r～0.4r區(qū)間，定位誤差有明顯的下降,之后MCB和MCL定位誤差都有明顯的上升趨勢;雖然本文算法的定位誤差也隨之增大，但趨勢明顯較緩.這是因為MCB和MCL的位置預(yù)測采樣范圍都會因為vmax增大而增大，而對于IMCB，除了錨箱和vmax的限制，還增加了方向預(yù)測，方向預(yù)測是與vmax無關(guān)的預(yù)測，當(dāng)vmax增大到對限制位置預(yù)測采樣范圍無效時，也就是說當(dāng)根據(jù)vmax構(gòu)造的正方形完全覆蓋錨箱時，方向預(yù)測的范圍限制作用仍然有效.因此，隨著vmax增加，IMCB的定位誤差上升趨勢平緩，且定位精度優(yōu)于MCB.

3.3 錨節(jié)點密度對定位誤差的影響

圖9為vmax= 0.2r時節(jié)點定位誤差隨錨節(jié)點密度變化的曲線圖，提高錨節(jié)點密度有利于降低定位誤差，但是這無疑也會增加網(wǎng)絡(luò)的部署成本.由圖9可見，IMCB定位誤差低于MCB.這是因為錨節(jié)點數(shù)量的增加一方面使基于RSSI的權(quán)重優(yōu)化更加有效；另一方面，錨節(jié)點的增加提高了定位精度，也使得在下一時刻定位時的方向預(yù)測角范圍更小，從而縮小了位置預(yù)測范圍，進(jìn)一步提高定位精度.此外，歷史錨節(jié)點的條件限制使得IMCB在錨節(jié)點密度較低時，定位精度優(yōu)于MCL和MCB.

3.4 采樣次數(shù)

基于MCL的定位算法中大部分的能量消耗來自于為了獲得足夠有效位置采樣點而產(chǎn)生的采樣次數(shù)，降低采樣次數(shù)有利于降低能量消耗，提高節(jié)點的定位效率.圖10為vmax= 0.2r，sd=1時節(jié)點定位采樣次數(shù)隨時間變化的曲線圖.如圖10可見，IMCB算法通過歷史錨節(jié)點和運動模型對采樣范圍的限制明顯降低了節(jié)點定位所需的采樣次數(shù).相比MCB算法，IMCB平均定位采樣次數(shù)降低了74%.

4 總結(jié)

本文作者設(shè)計出一種基于歷史錨節(jié)點并結(jié)合RSSI測距的權(quán)重定位算法——IMCB，它具有如下優(yōu)點：1)利用歷史錨節(jié)點及歷史RSSI測距進(jìn)一步縮小了未知節(jié)點的位置采樣范圍，在一定程度上緩解了錨節(jié)點密度的問題；2)基于RSSI的權(quán)重優(yōu)化有效區(qū)分了采樣點的權(quán)重；3)對運動模型的改進(jìn)有利于節(jié)點在定位中進(jìn)行方向預(yù)測，縮小了節(jié)點定位時預(yù)測采樣的范圍.最終，IMCB算法比MCB算法的定位精度提高了16.6%，平均定位采樣次數(shù)降低了74%.

[1] JAMALABDOLLAHI M， ZEKAVAT S. Time of arrival estimation in wireless sensor networks via OFDMA [C] .Vehicular Technology Conference, 2015:1-5.

[2] WANG Y, HO K C. TDOA source localization in the presence of synchronization clock bias and sensor position errors[J]. IEEE Transactions on Signal Processing, 2013, 61(18):4532-4544.

[3] CUI W, WU S C, WANG Y Z. A gossip-based AOA distributed localization algorithm for wireless sensor networks [J]. Applied Mechanics and Materials,2014, 577:841-846.

[4] YAGHOUBI F, ABBASFAR A A，MAHAM B. Energy-efficient RSSI-based localization for wireless sensor networks [J].IEEE Communications Letters, 2014, 18(6)：973-976.

[5] BAI Y, LI C M, XUE Y. A centroid localization algorithm for wireless sensor networks based on RSSI[J]. Applied Mechanics & Materials, 2013, 303-306;197-200.

[6] AGASHE A A, AGASHE A A, PATIL R S. Evaluation of DV hop localization algorithmin wireless sensor networks[C]. International Conference on Advances in Mobile Network, Communication and ITS Applications，2012:79-82.

[7] REN P, LIU W, SUN D， et al. Node localization based on convex optimization in wireless sensor networks [C].Fuzzy Systems and Knowledge Discovery , 2015: 2169-2173.

[8] ZHANG A, YE X, HU H. Point in triangle testing based trilateration localization algorithm in wireless sensor networks [J]. Internet and Information Systems, 2012, 6: 2567-2586.

[9] HU L, EVANS D. Localization for mobile sensor networks [J]. Wireless Communication, 2004:45-57.

[10] BAGGIO A, LANGENDOEN K. Monte-Carlo localization for mobile wireless sensor networks[M]. Berlin: Springer Berlin Heidelberg, 2006:718-733.

[11] ZHU H, ZHONG X , YU Q, et al. A localization algorithm for mobile wireless sensor networks [C]. International Conference on Intelligent System Design and Engineering Applications, 2013: 81-85.

[12] ZHANG S, CAO J, CHEN L J, et al. Accurate and energy-efficient range-free localization for mobile sensor networks[J]. IEEE Transactions on Mobile Computing, 2010, 9(6):897-910.

[13] 李建坡, 時明, 鐘鑫鑫. 自適應(yīng)蒙特卡羅無線傳感器網(wǎng)絡(luò)移動節(jié)點定位算法[J]. 吉林大學(xué)學(xué)報(工學(xué)版), 2014, 44(4):1191-1196. LI Jianpo, SHI Ming, ZHONG Xinxin. Self-adaptive Monte Carlo localization algorithm of mobile nodes in WSN[J]. Journal of Jilin University(Eng and Technol Ed), 2014, 44(4):1191-1196. (in Chinese)

[14] LUAN J, ZHANG R, ZHANG B， et al. An improved Monte Carlo localization algorithm for mobile wireless sensor networks [C]. 7th International Symposium on Computational Intelligence and Design , 2014: 477-480.

An improved Monte Carlo localization algorithm based on ranging weights

ZHOUChunyue,ZHANGHongting

(School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044,China)

Traditional Monte Carlo localization (MCL) algorithms for mobile wireless sensor networks (WSNs) usually suffer from low sampling efficiency or high anchor density for high localization accuracy. To address these issues, a new localization algorithm based on MCL which called IMCB (Improved Monte Carlo Localization Boxed) is proposed. IMCB fully utilizes the historical anchors information, RSSI ranging, and the improved motion model to further constrain the sampling area and distinguish weights of the effective samples. Simulation results show that the positioning accuracy of the proposed algorithm is improved by 16.6% compared with MCB (Monte Carlo Localization Boxed) algorithm.

wireless sensor networks; Monte Carlo localization; received signal strength indication; motion model

2016-05-10

北京市教育委員會共建項目資助(W15H100040)

周春月(1973—)，女，黑龍江大慶人，高級工程師，博士.研究方向為下一代通信網(wǎng)絡(luò)技術(shù)和信息安全. email：chyzhou@bjtu.edu.cn.

TP393

A

1673-0291(2016)05-0063-07

10.11860/j.issn.1673-0291.2016.05.011