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

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

引言

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

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

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

1.1 方法概述

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

1.2 節點(diǎn)的運動(dòng)模型和運動(dòng)預測

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

　(1)

(2)

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

(3)

(4)

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

(5)

　　有x軸和y軸方向上的速度，可以得到節點(diǎn)在t_n的運動(dòng)方向為：

(6)

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

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

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

(7)

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

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

(8)

1.4 濾波計算

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

(9)

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

(10)

　　利用上面的采樣規則，重新采樣N’，然后重復上面的過(guò)程直到找到滿(mǎn)足的粒子數，因為找到的 每個(gè)粒子的權重都一致，所以有：

　(11)

　　最后計算得到待定位節點(diǎn)的坐標：

(12)

2 仿真實(shí)驗與結果分析

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

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

　　(1) 采樣數目的選擇。不同的采樣數目對應的定位精度和需要的存儲條件不同，需要選擇合理的采樣數目。

　　(2) 研究信標節點(diǎn)的密度對定位誤差的影響。

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

　　(4) 研究信標節點(diǎn)的比例對節點(diǎn)定位覆蓋率的影響。

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