基于自適應采樣的移動 WSN定位算法

黃中林, 鄧平

(西南交通大學信息編碼與傳輸重點實驗室,四川 成都 610031)

0 引言

節點定位是無線傳感器網絡(WSN)的關鍵技術之一。近年來已經提出了很多定位算法,這些算法主要分為兩類：一類是靜態WSN定位,另一類是移動WSN定位。前者只需定位一次,后者需要隨著時間變化不斷地進行定位。如果將傳統的靜態WSN定位算法應用于移動WSN定位,由于不能充分利用移動節點間的有用信息,定位精度較低,定位計算復雜性也較高。為此,需要研究適用于移動WSN的有效定位算法。

2004年Hu等根據序列蒙特卡羅方法在機器人定位中的應用,提出一種基于序列蒙特卡羅方法的移動 WSN定位算法——序列蒙特卡羅定位(MCL)[1]。文獻[2]針對 MCL采樣效率低的缺點,根據兩跳范圍內的鄰居錨節點信息構建錨盒子和采樣盒子,提出了MCB算法,該算法有效的減少了采樣次數和定位時間。文獻[3]利用節點的所有鄰居位置信息來對采樣點進行加權,提出了 MSL算法,提高了定位精度。文獻[4]結合DV_hop和 MCL算法的優點,利用整個監測區域內的錨節點信息提出了多跳蒙特卡羅定位(MMCL)算法,該算法不需要知道節點的通信半徑,在錨節點密度低時定位精度高于MCL和 MCB,但由于錨節點在整個監測區域內進行信息洪泛,通信量較大。文獻[5]利用一階鄰居節點的采樣集合里的采樣點提高了MCB算法的定位精度。

1 序列蒙特卡羅定位

MCL的實質是用一個具有大量加權粒子的樣本集來表征待估狀態的后驗概率分布。MCL是一種有效的適用于移動環境下的節點定位算法。但該算法需要不斷的重復采樣,獲得有效樣本點的采樣次數非常大,實時性差,計算量也比較大。

MCB分為預測和濾波兩個階段。

預測階段：節點利用前一時刻的樣本集 Lt-1、錨盒子和采樣盒子產生新的樣本集 Lt。

假設某個時間單元,未知節點共接收到 n個錨節點發出的坐標信息。則每個錨節點可以計算出其周圍距離為通信半徑 r的矩形坐標,n個矩形區域的疊加,即為所構建的錨盒子,其坐標[2]如式(1)所示：

錨節點為未知節點的二跳鄰居錨節點時,式(1)中的r替換為 2r。式(1)中分別表示矩形區域四個頂點的坐標。

其中,vmax為節點運動最大速度。在定位初始階段節點尚未保存任何時刻的樣本集合,因此,在 t=0時刻,未知節點僅根據式(1)計算采樣區域。

濾波階段：MCB采用連通性約束條件[2]。

其中,d(l,s)為采樣點l與錨節點s的歐氏距離。如果樣本點滿足濾波條件,采樣點有效,不滿足則去除該采樣點。

濾波后 Lt中的樣本個數可能小于N,重復上述預測和濾波過程,直到采樣集中含有N個樣本點為止。當采樣集合中的樣本數為 N時,采樣集合中的樣本點的平均位置為節點的估計位置。

MCB利用一跳和二跳鄰居錨節點構建錨盒子來限制采樣區域。利用錨盒子減小采樣區域,一方面可以快速地獲得樣本點,降低了總的采樣次數;另一方面可以防止無休止的采樣卻不能得到足夠的樣本點的情況,從而節省了節點計算量,也節約了定位時間。當節點接收到的信息越多,錨盒子就越小,采樣階段得到樣本點的有效性就越高,在濾波階段去除的樣本點也就越少,從而能夠以較少的迭代周期計算出更為精確的節點坐標。

2 自適應采樣蒙特卡羅盒定位算法

MCB算法在錨節點密度較大時,錨節點交叉范圍比較小,在滿足定位精度的前提下,僅需獲得少數幾個樣本點就可以達到一定精度的定位,MCB算法此時仍然采用固定數目的樣本數N,定位精度幾乎沒有提高,浪費了計算量。在錨節點密度比較小時,錨節點交叉范圍比較大,需要獲得一定數量的樣本點才能達到需要的定位精度。

MCL、MCB算法都是設置固定樣本點數為N,造成了計算量的浪費。對于能量受限的 WSN來說,必須盡量節約定位帶來的能量消耗,特別是移動 WSN,每個時間單元都需要對每個未知節點進行定位,減少采樣次數可以大量節約節點的能量。因此,根據節點周圍的錨節點觀測信息,自適應地設置樣本數,在保證定位精度基礎上可以減少總的采樣次數,節約計算量,減少定位時間。樣本數計算方法如下：

其中,sd為錨節點密度,r為節點通信半徑,S為監測區域的面積,M為錨節點個數,Sbox為根據式(1)和式(4)計算出的錨盒子的面積。η為樣本因子,調整可以設置定位所需要的樣本數。

提出的自適應采樣蒙特卡羅盒定位(AMCB)算法步驟和MCB[2]步驟一樣。初始化階段：利用錨盒子進行采樣;預測階段：根據錨盒子和采樣盒子進行采樣;濾波階段：根據錨盒子的大小設置樣本數為min(n,N),其中 N是固定樣本數。重復預測和濾波過程,當樣本數超過 min(n,N)時,停止采樣。當采樣集合中的樣本點滿或達到最大采樣次數時,計算節點的位置。

3 算法仿真與性能分析

將 8個錨節點,72個普通節點隨機部署在一個 500 m×500 m的平面區域內,錨節點和普通節點通信半徑都為 r。錨節點和普通節點的運動最大速度已知,節點按照改進 Random Waypoint模型[1]運動,每個節點在每個時間間隔速度都可以變化,運動方向任意,節點停止時間設置為 0,最小運動速度設置為 0.5 m/s。節點間不計算距離信息,僅根據一跳和二跳鄰居間的連通信息進行移動節點位置確定。不考慮定位算法處理時間、信息時間延遲、錨節點位置誤差、非視距誤差等環境影響。節點的位置信息廣播之間的時間間隔為固定值T(T=1),節點在每一時間段 T內節點的移動速度用r的倍數關系表示。

為了驗證改進AMCB算法的節約計算量的性能,從時間變化定位精度、采樣次數和錨節點密度變化定位精度、采樣次數進行仿真。

在η=3,r=100,Vmax=Smax=10,固定樣本數 N=50,DOI=0,錨節點密度 sd=1,節點密度 nd=10情況下對質心[6]、MCL、MCB和 AMCB算法用 MATLAB仿真 100次求平均值,得到隨時間變化的定位誤差如圖 1所示,采樣次數如圖2所示。從仿真結果可以看出,MCB和AMCB定位精度略高于 MCL。MCL、MCB和AMCB算法 60秒內平均每個節點定位的采樣次數分別為：160、90、74。MCL采樣次數在初始時刻最大,因為在整個監測區域內進行采樣;MCL平均采樣次數比MCB和AMCB都要大,因為 MCL沒有利用當前時刻的觀察信息。MCB為 90,采樣次數明顯低于MCL。AMCB為74,在MCB的基礎上得到有效的減小,節約了計算量。

sd變化情況下的定位誤差如圖 3所示,采樣次數如圖 4所示。在采樣次數方面,sd增大,MCB和 MCL算法的采樣次數都增加,但 AMCB隨錨nd增加采樣次數減少,比MCB和MCL都少。因此,AMCB節約了計算量,減少了定位時間。

圖1 定位誤差

圖 2 采樣次數

圖 3 錨節點密度sd變化定位誤差

圖 4 錨節點密度 sd變化采樣次數

4 結語

序列蒙特卡羅定位在移動WSN定位中是一種有效的定位方法,但一般都設置固定的樣本數,對于能量受限的移動WSN來說是一種計算量的浪費。在 MCB的基礎上,充分利用錨節點觀測信息,根據錨盒子的大小動態設置樣本數。提出的AMCB算法在保證定位精度的基礎上減少了采樣次數。AMCB算法定位精度高,計算量小,定位實時性好,對WSN具有較高的應用價值。

[1]HU L,EVANS D.Localization for Mobile Sensor Networks[C].USA：Pennsylvania,2004：45-57.

[2]BAGGIO A,LANGENDOEN K.Monte-Carlo Localization for Mobile Wireless Sensor Networks[J].Ad Hoc Networks,2006,6(05)：718-733.

[3]RUDAFSHANIM,DATTA S.Localization in Wireless Sensor Networks[C].USA：Massachusetts,2007：51-60.

[4]YI J,YANG S,CHA H.Multi-Hop-based Monte Carlo Localization for Mobile Sensor Networks[C].USA：LEEE,2007：162-171.

[5]王妮,蔣鈴鴿.移動無線傳感器網絡節點的定位[J].通信技術,2009,42(09)：127-129.

[6]BULUSU N,HEIDEMANN J,FARM D.GPS-Less Low Cost Outdoor Localization for very Small Devices[J].IEEEPersonal Communications,2000,71(5)：28-34.