基于IMCL算法的無線傳感器網絡節點定位

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

引言

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

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

1 IMCL定位方法實現

1.1 方法概述

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

1.2 節點的運動模型和運動預測

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

　(1)

(2)

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

(3)

(4)

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

(5)

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

(6)

1.3 節點位置的選取

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

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

(7)

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

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

(8)

1.4 濾波計算

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

(9)

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

(10)

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

　(11)

　　最后計算得到待定位節點的坐標：

(12)

2 仿真實驗與結果分析

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

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

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

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

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

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

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