一種改進(jìn)的蒙特卡羅定位算法研究

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

（1.沈陽航空航天大學(xué) 沈陽110136；2.東軟飛利浦醫(yī)療設(shè)備系統(tǒng)有限責(zé)任公司 沈陽110179）

1 引言

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

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

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

2 RSS測量模型

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

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

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

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

3 基于RSS的MCL方法

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

3.1 位置預(yù)測

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

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

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

3.2 位置更新

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

3.3 重采樣

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

4 仿真與分析

構(gòu)建一個500 m×500 m的具有N個未知節(jié)點和M個錨節(jié)點的無線傳感器網(wǎng)絡(luò)。未知節(jié)點隨機(jī)地分布于網(wǎng)絡(luò)中，并且其移動特性遵循隨機(jī)移動模型，其移動速度從l m/s(vmin)到20 m/s(vmax)中選擇，移動方向未知，同時錨節(jié)點假定處于靜止?fàn)顟B(tài)。

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

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

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

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

5 結(jié)束語

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

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)