基于IMCL算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位

摘要：節(jié)點(diǎn)定位是無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)基本和關(guān)鍵的問(wèn)題。針對(duì)無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位方法計(jì)算量大，硬件要求高和信標(biāo)節(jié)點(diǎn)數(shù)目需較多等難點(diǎn)。本文研究蒙特卡洛定位方法，并提出一種改進(jìn)的蒙特卡羅節(jié)點(diǎn)定位方法(IMCL)，利用插值法預(yù)測(cè)運(yùn)動(dòng)軌跡結(jié)合采樣盒來(lái)進(jìn)行采樣。仿真結(jié)果表明，該方法能夠提高采樣的效率，提高節(jié)點(diǎn)的定位精度。

引言

　　隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用越來(lái)越廣泛，而無(wú)線傳感器網(wǎng)絡(luò)的研究和應(yīng)用依賴于整個(gè)系統(tǒng)對(duì)節(jié)點(diǎn)的準(zhǔn)確位置信息的獲取，位置的精度直接影響著網(wǎng)絡(luò)的性能和優(yōu)化的手段。在無(wú)線傳感器網(wǎng)絡(luò)的許多應(yīng)用中節(jié)點(diǎn)定位算法扮演著非常重要的角色^[1-2]。目前無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位研究大部分針對(duì)靜態(tài)無(wú)線傳感器網(wǎng)絡(luò)，但在實(shí)際應(yīng)用中傳感器節(jié)點(diǎn)處于動(dòng)態(tài)的應(yīng)用卻十分廣泛，如監(jiān)視動(dòng)物的移動(dòng)、醫(yī)院病人的監(jiān)護(hù)等。因此，移動(dòng)節(jié)點(diǎn)定位技術(shù)的研究對(duì)無(wú)線傳感器網(wǎng)絡(luò)技術(shù)具有重要的理論意義和應(yīng)用價(jià)值。在移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用中如何實(shí)現(xiàn)低成本、低功耗和高精度的節(jié)點(diǎn)定位，已成為節(jié)點(diǎn)研究的重點(diǎn)問(wèn)題^[3-5]。針對(duì)無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)的一些定位算法：如DLS定位算法、DRL定位算法等，由于存在計(jì)算量大、硬件要求高和需要較多信標(biāo)節(jié)點(diǎn)數(shù)目等特點(diǎn)，難以滿足實(shí)際的應(yīng)用。文獻(xiàn)[6]借鑒機(jī)器人領(lǐng)域中的蒙特卡羅定位方法，并將其應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)中移動(dòng)節(jié)點(diǎn)的定位。蒙特卡羅定位方法(Monte Carlo Localization，簡(jiǎn)稱MCL)利用節(jié)點(diǎn)的移動(dòng)性來(lái)幫助定位，能夠提高定位的精度，減小定位的代價(jià)，給移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問(wèn)題的解決提供了一個(gè)新的思路，使越來(lái)越多的研究者在此算法的基礎(chǔ)上衍生出自己的改進(jìn)方法。Baggio提出了MCB定位算法^[7] (Monte Carlo Localization Boxed)，該算法通過(guò)信標(biāo)節(jié)點(diǎn)盒子和樣本盒子把采樣區(qū)域限制在一個(gè)樣本盒子中，提高采樣成功率，從而改善定位性能;于是Dual-MCL和Mixer-MCL定位算法^[8]被提出，通過(guò)限制樣本的采樣范圍等方法在預(yù)測(cè)和濾波階段進(jìn)行改進(jìn)，改進(jìn)了原有MCL定位算法;RSS-Based MCL定位方法[9]研究了將MCL與RSSI測(cè)距信息相結(jié)合。李敏等提出了一種基于參考節(jié)點(diǎn)選擇模型的蒙特卡羅定位算法^[10]，能夠在較少信標(biāo)節(jié)點(diǎn)的情況下利用相鄰節(jié)點(diǎn)參與定位，但定位誤差較大。

　　本文研究了一種改進(jìn)的蒙特卡羅定位算法(IMCL)，該方法利用插值法預(yù)測(cè)節(jié)點(diǎn)的運(yùn)動(dòng)軌跡并結(jié)合采樣盒來(lái)進(jìn)行采樣，該方法能夠提高節(jié)點(diǎn)采樣的效率，提高節(jié)點(diǎn)定位的精度。

1 IMCL定位方法實(shí)現(xiàn)

1.1 方法概述

　　MCL定位算法中，Vmax越大，則采樣的區(qū)域越大，節(jié)點(diǎn)位置的不確定性也隨之增大。由于事先不知道節(jié)點(diǎn)運(yùn)動(dòng)方向，需要在整個(gè)圓內(nèi)采樣，這也增加了節(jié)點(diǎn)的不確定性。通過(guò)構(gòu)建節(jié)點(diǎn)運(yùn)動(dòng)模型，選取節(jié)點(diǎn)的位置和采樣盒相結(jié)合來(lái)進(jìn)行過(guò)濾，以此來(lái)減小節(jié)點(diǎn)可能的范圍和預(yù)測(cè)工作量，來(lái)提高節(jié)點(diǎn)定位精度和工作效率。

1.2 節(jié)點(diǎn)的運(yùn)動(dòng)模型和運(yùn)動(dòng)預(yù)測(cè)

　　節(jié)點(diǎn)在移動(dòng)過(guò)程中使用的移動(dòng)模型對(duì)算法定位精度有密切關(guān)系，不同的移動(dòng)模型導(dǎo)致不同的節(jié)點(diǎn)移動(dòng)軌跡，在無(wú)線傳感器網(wǎng)絡(luò)中常用的移動(dòng)模型有：Random Walk移動(dòng)模型、Rand Waypoint移動(dòng)模型、Random Direction移動(dòng)模型[8]、Reference Point Mobility model、Voltage of mobile model、高斯-馬爾科夫模型。本算法假設(shè)是應(yīng)用在一個(gè)二維的平面上，節(jié)點(diǎn)的運(yùn)動(dòng)平滑而連續(xù)，因此可以借助歷史的位置數(shù)據(jù)，利用插值法對(duì)節(jié)點(diǎn)的運(yùn)動(dòng)進(jìn)行預(yù)測(cè)。開(kāi)始時(shí)讓每個(gè)移動(dòng)節(jié)點(diǎn)根據(jù)MCL算法獲取自己的前幾個(gè)時(shí)刻位置信息，并存放在一個(gè)歷史的記錄隊(duì)列里，然后根據(jù)記錄來(lái)預(yù)測(cè)移動(dòng)節(jié)點(diǎn)下一時(shí)刻的運(yùn)動(dòng)趨勢(shì)。假設(shè)節(jié)點(diǎn)存儲(chǔ)了先前n-1個(gè)時(shí)間點(diǎn)的位置信息。t₁,t₂…t_n-1時(shí)刻的位置分別為(x₁, y₁)、(x₂, y₂)…(x_n-1,y_n-1)。采用拉格朗日插值法^[7]可以得到節(jié)點(diǎn)在t_n時(shí)刻x方向和y方向的運(yùn)動(dòng)預(yù)測(cè)計(jì)算式。分別為：

　(1)

(2)

　　由式(1)和(2)分別對(duì)時(shí)間t求導(dǎo)，可以預(yù)測(cè)到t_n時(shí)刻節(jié)點(diǎn)在x方向和y方向的運(yùn)動(dòng)速度。分別為：

(3)

(4)

　　由式(1)和(3)可得到節(jié)點(diǎn)在t_n時(shí)刻的運(yùn)動(dòng)速度為：

(5)

　　有x軸和y軸方向上的速度，可以得到節(jié)點(diǎn)在t_n的運(yùn)動(dòng)方向?yàn)椋?/p>

(6)

1.3 節(jié)點(diǎn)位置的選取

　　在構(gòu)建采樣區(qū)域時(shí)，為了計(jì)算方便，使用通信圓的外切正方形代替理想圓周通信模型。采樣盒可以消除部分通信覆蓋范圍并不是一個(gè)理想圓所帶來(lái)的影響。采樣盒示意圖如圖1所示。

　　采樣盒由(x_min, x_max)和(y_min, y_max)計(jì)算得到，其中x_min、x_max、y_min和y_max由公式(7)得到。

(7)

　　(x_j, y_j)為信標(biāo)節(jié)點(diǎn)的坐標(biāo)。為了獲取較大的采樣盒，來(lái)獲取較為豐富的樣本，在保證定位精度的前提下，盡量選擇距離定位節(jié)點(diǎn)較近的信標(biāo)節(jié)點(diǎn)來(lái)構(gòu)成采樣盒，在同等均勻的分布下，距離定位節(jié)點(diǎn)較遠(yuǎn)的信標(biāo)節(jié)點(diǎn)構(gòu)成采樣區(qū)域小于距離節(jié)點(diǎn)較近的信標(biāo)節(jié)點(diǎn)構(gòu)成的采樣區(qū)域。由于節(jié)點(diǎn)運(yùn)動(dòng)的連續(xù)性，本文利用上一刻的值預(yù)測(cè)節(jié)點(diǎn)的位置并結(jié)合采樣盒來(lái)進(jìn)行采樣。在預(yù)測(cè)節(jié)點(diǎn)位置時(shí)采用以下的方式，如圖2所示。

　　以上一時(shí)刻為坐標(biāo)原點(diǎn)，以V_max為半徑，沿節(jié)點(diǎn)運(yùn)動(dòng)方向的順時(shí)針和逆時(shí)針各展開(kāi)θ角的一個(gè)扇形(θ值由公式(6)得到);在圖2扇形和圖1采樣盒交集的區(qū)域隨機(jī)選取N個(gè)點(diǎn)作為預(yù)測(cè)值;如果濾波后符合要求的預(yù)測(cè)點(diǎn)的個(gè)數(shù)達(dá)不到N，可以將扇形的θ角加倍后用上面相同的方法重新進(jìn)行選取和濾波，直到找到滿足要求的點(diǎn)。所有滿足上述情況的節(jié)點(diǎn)集合為：

(8)

1.4 濾波計(jì)算

　　濾波階段，節(jié)點(diǎn)根據(jù)當(dāng)前接收到的觀測(cè)值來(lái)去掉那些不滿足要求的預(yù)測(cè)位置。節(jié)點(diǎn)使用上一時(shí)刻的節(jié)點(diǎn)預(yù)測(cè)位置結(jié)合節(jié)點(diǎn)運(yùn)動(dòng)模型來(lái)進(jìn)行濾波。信標(biāo)節(jié)點(diǎn)向通信半徑內(nèi)廣播其當(dāng)前時(shí)刻的位置坐標(biāo)，待定位的未知節(jié)點(diǎn)在通信半徑內(nèi)接收信標(biāo)節(jié)點(diǎn)的位置并轉(zhuǎn)播。根據(jù)在時(shí)刻k到k+1觀測(cè)到的廣播信息，如果Ds為1跳信標(biāo)節(jié)點(diǎn)的集合，I_s為2跳信標(biāo)節(jié)點(diǎn)的集合，則濾波公式為：

(9)

　　根據(jù)公式(8)進(jìn)行濾波，濾掉不滿足要求的粒子后，保留滿足要求的粒子，如滿足要求的粒子數(shù)達(dá)不到要求，則繼續(xù)在采樣區(qū)域內(nèi)采樣、濾波，直到找到滿足要求的粒子數(shù)目。假設(shè)滿足濾波公式的預(yù)測(cè)值的權(quán)值為1，不滿足的權(quán)值為0。設(shè)預(yù)測(cè)值的權(quán)值為ωi，則需要重新預(yù)測(cè)采樣的數(shù)目N’:

(10)

　　利用上面的采樣規(guī)則，重新采樣N’，然后重復(fù)上面的過(guò)程直到找到滿足的粒子數(shù)，因?yàn)檎业降?每個(gè)粒子的權(quán)重都一致，所以有：

　(11)

　　最后計(jì)算得到待定位節(jié)點(diǎn)的坐標(biāo)：

(12)

2 仿真實(shí)驗(yàn)與結(jié)果分析

　　為了驗(yàn)證IMCL定位算法的有效性，根據(jù)MCL定位算法，對(duì)MCL-Simulator仿真器進(jìn)行擴(kuò)展，利用擴(kuò)展的仿真器來(lái)驗(yàn)證IMCL算法的性能，設(shè)置仿真區(qū)域大小為200×200正方形，所有節(jié)點(diǎn)隨機(jī)分布在其中，信標(biāo)節(jié)點(diǎn)與待定位的節(jié)點(diǎn)的通信半徑r為20m。本文主要研究信標(biāo)節(jié)點(diǎn)靜止且均勻分布，未知節(jié)點(diǎn)移動(dòng)的模型采用了Rand Waypoint移動(dòng)模型，為了控制節(jié)點(diǎn)的移動(dòng)范圍不超過(guò)傳感區(qū)域的邊界，節(jié)點(diǎn)移動(dòng)的最大移動(dòng)速度在0.2r～2r之間，且不考慮移動(dòng)節(jié)點(diǎn)的運(yùn)動(dòng)方向。

　　本文從以下幾個(gè)方面對(duì)IMCL算法進(jìn)行仿真分析：

　　(1) 采樣數(shù)目的選擇。不同的采樣數(shù)目對(duì)應(yīng)的定位精度和需要的存儲(chǔ)條件不同，需要選擇合理的采樣數(shù)目。

　　(2) 研究信標(biāo)節(jié)點(diǎn)的密度對(duì)定位誤差的影響。

　　(3) 研究移動(dòng)節(jié)點(diǎn)的最大運(yùn)動(dòng)速度對(duì)定位誤差的影響。

　　(4) 研究信標(biāo)節(jié)點(diǎn)的比例對(duì)節(jié)點(diǎn)定位覆蓋率的影響。

　　利用蒙特卡羅方法定位時(shí)，采樣數(shù)目的選取與定位的定位誤差有很大的關(guān)系，采樣數(shù)目越多，得到的節(jié)點(diǎn)定位的精度就越高。但是采樣數(shù)目多意味著存儲(chǔ)空間的增大和計(jì)算量的加大，但是節(jié)點(diǎn)本身的存儲(chǔ)不可能做得很大。為了不占用更大的存儲(chǔ)空間和計(jì)算時(shí)間，需要同時(shí)保證定位精度的要求，因此選擇合理的采樣數(shù)目很關(guān)鍵。圖3 顯示了采樣數(shù)目與節(jié)點(diǎn)定位誤差的關(guān)系，由此可以看出隨著采樣數(shù)目的增加，節(jié)點(diǎn)的定位誤差在下降。當(dāng)采樣數(shù)目在100左右時(shí)，節(jié)點(diǎn)的定位誤差就開(kāi)始變得平緩，直到采樣數(shù)目達(dá)到1000，定位誤差變化也不大。本文仿真實(shí)驗(yàn)的采樣數(shù)目選擇了100個(gè)，這樣既能保證節(jié)點(diǎn)定位的精度要求，又能夠減少節(jié)點(diǎn)的存儲(chǔ)空間和計(jì)算的時(shí)間。