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

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

引言

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

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

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

1.1 方法概述

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

1.2 節(jié)點的運動模型和運動預(yù)測

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

　(1)

(2)

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

(3)

(4)

　　由式(1)和(3)可得到節(jié)點在t_n時刻的運動速度為：

(5)

　　有x軸和y軸方向上的速度，可以得到節(jié)點在t_n的運動方向為：

(6)

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

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

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

(7)

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

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

(8)

1.4 濾波計算

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

(9)

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

(10)

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

　(11)

　　最后計算得到待定位節(jié)點的坐標：

(12)

2 仿真實驗與結(jié)果分析

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

　　本文從以下幾個方面對IMCL算法進行仿真分析：

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

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

　　(3) 研究移動節(jié)點的最大運動速度對定位誤差的影響。

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

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