一種改進的蒙特卡羅定位算法研究

邵清亮，李玉峰，屈樂樂，王 鵬

（1.沈陽航空航天大學 沈陽110136；2.東軟飛利浦醫療設備系統有限責任公司 沈陽110179）

1 引言

在無線傳感器網絡的許多應用中，節點位置至關重要，離開位置信息，監測事件或者感知數據也失去了實際應用價值。若僅為每個傳感器節點均配置GPS收發器，其成本和能耗較高，不符合無線傳感器網絡各方面的約束，若沒有位置信息，傳感器節點所采集的數據幾乎是沒有應用價值的。因此，在無線傳感器網絡的應用中，節點定位成為關鍵的問題。

目前，節點的定位方法主要有基于測距（range-based）的定位和無須測距(range-free)的定位兩種。測距方法利用接收信號強度指示(RSSI)、信號到達時間（TOA）[1]，不同信號到達的時間差分(TDOA)[2]以及到達角度(AOA)[3]等測量相鄰節點的距離。非測距定位算法則不需要距離和角度信息，算法根據網絡連通性等信息來實 現 節 點 定 位，如 質 心 算 法、DV-Hop、Amorphous、MDS-MAP和APIT算 法 等[4～6]，在以上的算法中沒有很好的能夠針對移動節點的定位，傳統的蒙特卡羅方法能夠較好地解決移動節點定位，但其估計誤差較大，而且在采樣的過程中，為了避免粒子退化，計算量非常大，造成傳感器節點能量的大量消耗。

本文提出了一種基于接收信號強度的蒙特卡羅算法，縮小了傳統蒙特卡羅算法采樣的范圍，降低了重復采樣率以及節點的能量消耗。

2 RSS測量模型

測量節點的RSS[7]是一種指示當前介質中電磁波能量大小的數值。RSS值隨距離增加而減小，錨節點可以通過RSS值計算出未知節點與它的距離。雖然傳感器節點自身具備通信能力，借助的硬件設備較少，相對其他測距技術而言是一種低功率、廉價的測距技術，但是無線電傳播過程中由于多徑、繞射、障礙物等因素對RSS定位算法的定位精度有很大影響[8]，所以單獨使用RSS方法很難對節點進行較精確的定位。

在實際應用中，無線電傳播路徑損耗模型十分復雜，由于陰影效應的隨機特性，接收功率的測量值不同于計算得到的平均接收功率，測量值與平均值之間的差可以由對數正態分布來描述，因而傳感器i所接收到的來自傳感器j的接收功率Pij(dBm)是遵循高斯分布的一個隨機變量[9]，這里是傳感器i所接收到的總的平均接收功率(dBm)，δdB是陰影衰落標準差（dB），它是關于距離的一個常量。設P0表示在參考距離d0時的接收功率(dBm)，假設傳感器j的發射功率Pt(dBm)，P0可依據自由空間環境下路徑損耗條件計算得到P0=Pt-20lg(4πd0λ)，其中λ是信號載波的波長。根據上式，接收功率的期望值依賴于傳感器節點i的位置mi=(xi,yi)，用dij表示發射點(xi,yi)和接收點(xj,yj)之間的歐幾里德幾何距離，因而，傳感器i在位置mi具有接收功率P的條件概率為：

式（1）給出了節點i在位置mi的接收功率。

假設在時刻k時某未知節點有L個鄰居錨節點，通常得到的L×1的測量向量nk與未知節點的位置mk是相互獨立的。在不同時刻，對不同的未知節點，其鄰居錨節點的數量可能不同。因而，重新改寫式(1)得到：

3 基于RSS的MCL方法

蒙塔卡羅定位MCL算法是一種無須測距的分布式算法，相對于其他算法而言有著較大的優勢，但是在參考文獻[10]中指出MCL仍存在不足，主要體現在：采樣區域很大，導致采樣的效率過低，同時也降低了定位精度。若MCL算法在以每個樣本點為圓心、最大移動速度為半徑的圓內隨機采樣，這樣會導致很多采樣點不符合過濾條件，在過濾階段被過濾掉。為了取得足夠的樣本數，抽樣過程需要不斷重復，抽樣次數大大增加，有時甚至達到設置的最大抽樣次數后，還抽不到足夠的樣本，導致抽樣失敗，降低了定位效率和定位精度，采用改進的蒙特卡羅算法可以提高采樣率，縮短采樣時間。

3.1 位置預測

假設有一傳感器網絡，其中有N個未知節點和M個錨節點，錨節點的位置已知。未知節點處于移動狀態，并且彼此之間的移動相互獨立，基于傳感器節點的移動特性和RSS測量模型，用mk～P(mk|mk-1),k≥0表示給定節點在前一時刻的位置為mk-1時，當前時刻在mk的概率，該方程稱為轉移方程。用nk～P(nk|nk-1),k≥0描述在給定位置時對RSS測量的似然度，該方程成為觀測方程。

若未知節點隨機地從最大速度vmax和最小速度vmin之間選取一個值進行移動，其移動方向隨機地從[0,2π]選出，則給定未知節點在前一時刻的位置，其當前時刻位置估計的概率，即轉移分布P(mk|mk-1)，形成一個以mk-1為圓心、內半徑為vmin、外半徑vmax的圓環，如下：

式（3）表示了在前一時刻的位置mk-1時，當前位置的分布情況。在蒙特卡羅算法預測階段，基于前一時刻的位置估計，節點在任意時刻可能的位置即可從該圓中隨機地采樣，稱該圓形區域為采樣區域。由于并不知道未知節點的移動速度和移動方向，其位置的隨機采樣增加了不確定性，因而需要通過從RSS的觀測信息中采樣來減小其不確定性。

3.2 位置更新

通過節點位置預測和權重值更新的反復計算，可得到后驗分布p(mk|n1:k)。

3.3 重采樣

在以上的計算過程中，若經過多次迭代后，所有歸一化的權重值除其中的一個，其余的均非常接近于0。由于重要性權重的方差隨著時間的推移而增長，退化現象無法避免[11]。退化現象意味著大量的計算資源花在了那些對后驗分布估計貢獻很小的粒子上面。因而，在采用重采樣時結合RSS值，提高采樣的有效性，同時設定有效樣本數量為一固定閾值，低于此值則開始啟動重采樣。

4 仿真與分析

構建一個500 m×500 m的具有N個未知節點和M個錨節點的無線傳感器網絡。未知節點隨機地分布于網絡中，并且其移動特性遵循隨機移動模型，其移動速度從l m/s(vmin)到20 m/s(vmax)中選擇，移動方向未知，同時錨節點假定處于靜止狀態。

假定未知節點和錨節點的通信半徑r均為100 m，樣本數量設為50個，錨節點設為25個。通過仿真對比，從圖1中可以看出，在單位時間內，基于RSS的MCL方法比傳統MCL方法的定位精度高。

大多數基于錨節點的定位算法，定位精度通常受錨節點數量的影響。隨著錨節點數量的增加，定位精度也增加，較高的錨節點密度可以產生較高的定位精度，但當錨節點數量到達一定數量，如圖2所示，達到80個時，定位精度改善非常小。仿真表明，數量一定的錨節點情況下，基于RSS的MCL的定位精度比非測距的MCL定位精度要高。

由于蒙特卡羅定位算法多數的處理時間消耗在采樣過程中，這里對不同錨節點和未知節點數量下的采樣過程進行仿真，如圖3所示。從圖3可以看出，非測距MCL要花費大量的采樣嘗試次數才能采集到符合要求的樣本，對任何數量的錨節點，該算法大概需要采樣17 500次，這是由于從采樣區域中采集的樣本并不都是有效的，因而增加了重復采樣次數。而基于RSS的MCL方法僅需要50次采樣，就能夠完成有效采樣。從仿真結果可以看出，基于RSS的MCL方法需要的計算代價遠小于MCL方法。

將節點位置在每次定位過程中所發送的消息作為定位通信開銷。由于未知節點的兩跳鄰居錨節點的發現需要未知節點發送較多的消息，所以MCL方法比基于RSS的MCL需要更多的開銷，仿真結果如圖4所示。從圖4可以看出，未知節點一定的錨節點變化的情況下，MCL方法比基于RSS的MCL方法多發送11個消息。

5 結束語

無線傳感器網絡的移動節點定位方法中，傳統的蒙特卡羅算法的重采樣增大了節點的計算量，增加了傳感器節點能量消耗，本文在測得RSS值的基礎上，利用MCL方法降低節點計算量，仿真表明，在錨節點和未知節點數量一定的情況下，基于RSS的MCL改進算法的定位精度高于傳統的MCL方法，而且改進的算法樣本采樣次數少、通信開銷小，對降低無線傳感器網絡能耗有著積極作用。

1 Harter A,Hopper A,Steggles P，et al.The anatomy of a con-textaware application.MobiCom,Seattle,Washington,USA，1999

2 Girod L,Estrin D.Robust range estimation using acoustic and multimodal sensing.Proceedings of the IEEE/RSJ Int'l Conf on Intelligent Robots and Systems(IROS 01),Maui,Hawaii,USA,2001

3 Niculescu D,Nath B.Ad Hoc positioning system(APS)using AOA.IEEE INFOCOM,San Francisco California,USA，2003

4 Niculescu D,Nath B.Ad Hoc positioning systems(APS).Proceedings of the 2001 IEEE Global Telecommunications Conference,IEEE Communications Society,2001

5 Niculescu D,Nath B.DV based positioning in Ad Hoc networks.Journal of Telecommunication Systems,2003,22(1):267～280

6 Bahl P,Padmanabhan V N.RADAR:an in-building RF-based user location and tracking system.Proceedings of the 19th Annual Joint Conference on IEEE Computer and Communications Societies,Aviv,Israel:IEEE Press,2000

7 Girod L,Bychovskiy V,Elson J,et al.Locating tiny sensors in time and space:a case study.IEEE ICCD,Freiburg,Germany,2002

8 Elnahrawy E,Li X,Martin R P.The limits of localization using signal strength:a comparative study.IEEE SECON,Santa Clara,CA,USA,2004

9 Neal Patwari,Nciycr S C,Robert J.Relative location estimation in wireless sensor network．IEEE Transaction on Signal Processing,2003,l51(8):2 137～2 148

10 Hu L,Evans D.Localization for mobile sensor networks.Proceedings of the 10th Annual International Conference on MobileComputingandNetworking,Philadelphia：ACMsociety,2004

11 Doucet A,Godsill S,Andrieu C.On sequential monte carlo sampling methods for bayesian filtering.Statistics and Computing,2000(10)