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

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

1 引言

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

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

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

2 RSS測量模型

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

在實際應用中，無線電傳播路徑損耗模型十分復雜，由于陰影效應的隨機特性，接收功率的測量值不同于計算得到的平均接收功率，測量值與平均值之間的差可以由對數(shù)正態(tài)分布來描述，因而傳感器i所接收到的來自傳感器j的接收功率Pij(dBm)是遵循高斯分布的一個隨機變量[9]，這里是傳感器i所接收到的總的平均接收功率(dBm)，δdB是陰影衰落標準差（dB），它是關(guān)于距離的一個常量。設P0表示在參考距離d0時的接收功率(dBm)，假設傳感器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的接收功率。

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

3 基于RSS的MCL方法

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

3.1 位置預測

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

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

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

3.2 位置更新

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

3.3 重采樣

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

4 仿真與分析

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

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

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

由于蒙特卡羅定位算法多數(shù)的處理時間消耗在采樣過程中，這里對不同錨節(jié)點和未知節(jié)點數(shù)量下的采樣過程進行仿真，如圖3所示。從圖3可以看出，非測距MCL要花費大量的采樣嘗試次數(shù)才能采集到符合要求的樣本，對任何數(shù)量的錨節(jié)點，該算法大概需要采樣17 500次，這是由于從采樣區(qū)域中采集的樣本并不都是有效的，因而增加了重復采樣次數(shù)。而基于RSS的MCL方法僅需要50次采樣，就能夠完成有效采樣。從仿真結(jié)果可以看出，基于RSS的MCL方法需要的計算代價遠小于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)絡的移動節(jié)點定位方法中，傳統(tǒng)的蒙特卡羅算法的重采樣增大了節(jié)點的計算量，增加了傳感器節(jié)點能量消耗，本文在測得RSS值的基礎上，利用MCL方法降低節(jié)點計算量，仿真表明，在錨節(jié)點和未知節(jié)點數(shù)量一定的情況下，基于RSS的MCL改進算法的定位精度高于傳統(tǒng)的MCL方法，而且改進的算法樣本采樣次數(shù)少、通信開銷小，對降低無線傳感器網(wǎng)絡能耗有著積極作用。

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)