基于RSSI等級的蒙特卡羅定位算法應用研究

吳世通，陳良，李云飛，曹紅飛

1.蘇州大學計算機科學與技術學院，江蘇蘇州 215006

2.蘇州大學機電工程學院，江蘇蘇州 215006

基于RSSI等級的蒙特卡羅定位算法應用研究

吳世通1，陳良2，李云飛1，曹紅飛1

1.蘇州大學計算機科學與技術學院，江蘇蘇州 215006

2.蘇州大學機電工程學院，江蘇蘇州 215006

感知節(jié)點的定位是無線傳感網應用的基礎。現(xiàn)有的靜態(tài)定位算法無法應用于動態(tài)傳感網。針對一類目標節(jié)點移動而錨節(jié)點靜止的傳感網應用，提出了一種RRMCL（RSSI Rank Monte Carlo Localization）定位算法。該算法以蒙特卡羅算法為基礎，利用RSSI（

Signal Strength Indication）值與距離的單調遞減關系劃分通信域，減少采樣區(qū)域大小。為了避免錨節(jié)點共線出現(xiàn)定位失效的情況，引入共線影響角度，提出了一種約束策略。仿真結果表明，提出的RRMCL與現(xiàn)有的MCL和MCB定位算法相比，能有效縮小采樣區(qū)域，提高了定位精度和速度。

無線傳感網絡；移動定位；蒙特卡羅；接收信號強度指示

1 引言

無線傳感網已被大量運用于軍事、工業(yè)控制、環(huán)境監(jiān)測中。WSN是由大量感知節(jié)點組成的，其Ad-hoc通信方式導致WSN具有分布式架構，因此獲得感知節(jié)點的準確位置較困難。然而，作為WSN應用的關鍵技術，節(jié)點的定位往往和數(shù)據(jù)本身一樣重要；同時無線傳感網的其他相關研究，如基于地理位置的信息路由技術，需要節(jié)點的位置作為支撐。因此，尋找WSN下合適的感知節(jié)點定位算法已成為許多高校和研究機構的研究熱點。

目前，已有的文獻方法多為靜態(tài)定位算法，主要分為基于測距的定位[1]和無須測距的定位[2]。前者主要包括TOA（Time Of Arrival）定位[3]、TDOA（Time Difference Of A rrival）定位[4]、AOA（Angle Of A rrival）定位[5]、RSSI（Received Signal Strength Indicator）定位[6]等。無須測距定位算法主要包括Centroid定位算法[7]、DV-Hop定位算法[8]、Amorphous定位算法[9]等。然而，在實際的WSN應用中，存在大量移動傳感節(jié)點。在該類網絡中，靜態(tài)算法由于沒有考慮節(jié)點的移動性，易受環(huán)境擾動因素影響，定位效果不佳。

由于節(jié)點的移動，造成網絡拓撲結構的頻繁變化，通信和響應能力下降，使得定位更加困難。現(xiàn)有的移動目標定位算法主要有基于濾波方法的定位和基于Monte Carlo方法的定位。基于Monte Carlo方法的代表性算法有MCL（Monte Carlo Localization）和MSL（M obile and Static Sensor Network Localization）[10]以及其改進算法MCB（Monte Carlo Localization Boxed）[11]，該算法限制采樣范圍，解決了MCL算法中采樣效率低的問題。

為了提出高效，易于應用的定位算法，對移動傳感網進行分析，發(fā)現(xiàn)大部分網絡存在如下特性，即錨節(jié)點固定，而未知節(jié)點移動，如機器人足球比賽、汽車移動物聯(lián)網定位等。受此啟發(fā)本文針對目標節(jié)點移動而錨節(jié)點靜止的傳感網應用，提出了一種基于RSSI等級的MCL感知定位算法RRMCL。主要思想是：將RSSI值運用到蒙特卡羅算法采樣區(qū)域的計算過程中，作為初步定位；在此基礎上通過采樣和濾波進行細定位。同時考慮到RSSI值存在誤差，當采樣區(qū)域條件不匹配時，將采樣區(qū)域的范圍擴大一倍，減小RSSI值誤差給定位結果帶來的影響。相比MCL、MSL和MCB，RRMCL算法具有以下優(yōu)勢：（1）利用RSSI與距離的單調遞減關系，將通信區(qū)域劃分成M個同心圓，進一步縮小采樣區(qū)域，提高了采樣效率。（2）針對鄰居錨節(jié)點共線或接近共線時容易產生定位失效的情況，引入共線影響角度，通過限制角度大小的方法，給出了一種約束策略。

2 Monte Car lo算法原理

Monte Carlo定位算法是一種貝葉斯濾波算法，將移動定位分為離散的時間段，若設t表示定位時刻，St表示t時刻節(jié)點位置分布，Wt表示從t-1時刻到t時刻收集到的錨節(jié)點的信息，條件概率p(st|st-1)表示從t-1時刻到t時刻位置預測的概率，p(st|wt)表示通過收集到的錨節(jié)點信息所預測的節(jié)點位置分布的可能性。一般來說，預測節(jié)點位置應利用所有以前階段的觀測值，即p(st|w0，w1，…，wt)，達到濾波的目的。

在預測階段，假設節(jié)點可能的最大速度為vmax，節(jié)點t-1時刻位置為St-1，則節(jié)點t時刻位置分布只可能是以St-1為中心，以vmax為半徑的圓，圓中采樣點符合均勻分布即

其中，d(st|st-1)表示點st到st-1的歐式距離。由式（1）可以得到采樣點集合。

過濾階段，未知節(jié)點進行廣播，若該節(jié)點能與錨節(jié)點進行直接通信，即獲得未知節(jié)點的一跳路由，如圖1所示。

圖1 MCL一跳濾波區(qū)域選擇

使用T代表此集合，對位置信息有如下過濾條件：

若節(jié)點與錨節(jié)點不能直接通信，但為兩跳鄰居，使用Q代表與該節(jié)點為兩跳距離的錨節(jié)點集合，如圖2所示。則對位置信息有過濾條件式（3）：

圖2 MCL兩跳濾波區(qū)域選擇

滿足上述條件的采樣點則保留，不滿足上述條件的則從集合filt(s)中去除，若集合中的采樣點數(shù)目不滿足要求則重新采樣，重新過濾，直到達到要求為止，最后求出集合中采樣點組成的多邊形的重心坐標即為未知點的坐標。

3 RRMCL算法描述

RRMCL算法是MCL的一種改進算法，其基本思想是：首先將一跳和兩跳錨節(jié)點的通信區(qū)域根據(jù)RSSI值遞減劃分成M個同心圓；其次，選擇其中若干個錨節(jié)點，根據(jù)圓環(huán)的重疊區(qū)域計算采樣區(qū)域；最后在采樣區(qū)域采樣，使用MCL算法定位。

3.1 利用RSSI等級確定采樣區(qū)域

文獻[12]給出了ROCRSSI算法，其是指用RSSI排序的方法將以通信半徑為半徑的圓劃分成諸多圓環(huán)，通過求若干圓環(huán)的交集方式，得到未知節(jié)點的位置，屬于靜態(tài)定位算法。本文將此思想運用到移動定位中，建立同心圓模型后，利用未知節(jié)點移動的特征（遠離錨節(jié)點或者靠近錨節(jié)點），以及t-1時刻的RSSIt-1值，選擇RSSI1和RSSI2的同心圓組成圓環(huán)，其中RSSI1＜RSSIt-1＜RSSI2且彼此最鄰近，則未知節(jié)點的下一位置在此圓環(huán)中。使用多個錨節(jié)點的RSSI值形成多個圓環(huán)，圓環(huán)的重疊區(qū)域即為采樣區(qū)域。

3.1.1 RSSI同心圓模型建立

基于RSSI測距的定位算法，是無線定位技術中代表性算法。文獻[13]給出的RSSI與距離的經驗對應關系式，如下所示：

其中p(d)表示未知節(jié)點接收到錨節(jié)點的信號強度，p(d0)表示在距離錨節(jié)點為d0處的信號強度，k表示傳輸距離和信號強度損耗之間的比例因子，該值一般和所處環(huán)境和傳輸媒介相關，d表示未知節(jié)點和錨節(jié)點間的距離度量，nW表示錨節(jié)點與未知節(jié)點間需要穿過墻壁的數(shù)目，C表示事先確定信號能穿過墻壁個數(shù)的閾值，WAF表示信號穿透墻壁的衰減比例因子，該值和墻壁材料和結構相關。于是，在得到某RSSI強度后，可用上述經驗公式反推出節(jié)點間的距離。本文不直接利用RSSI值求出的距離值來定位，而是作為MCL算法中縮小采樣區(qū)域的手段。另外無線傳感網中，節(jié)點往往計算能力和資源有限，因此本文采用廣泛接受的近似關系式（5），降低計算復雜度，提高定位效率。

p(d)=-(10n lg 10d+p(1))（5）其中d表示未知節(jié)點到錨節(jié)點的距離，p(1)表示1 m距離的RSSI值。使用式（5）計算出距離，繼而用此距離作為參數(shù)，將錨節(jié)點的通信區(qū)域分為M個不同半徑的同心圓，其中各個圓環(huán)等距，從而將通信區(qū)域分為各個RSSI等級區(qū)域，如圖3所示。

圖3 RSSI等級區(qū)域圖

為了控制計算復雜度，保證樣本覆蓋率，同時考慮節(jié)點移動速度。因此等級區(qū)域不能過多，本文經過大量實驗驗證，選定M=100vmax，其中vmax為節(jié)點最大移動速度。

3.1.2 采樣區(qū)域的計算

為了描述方便，令S為兩跳范圍內的錨節(jié)點集合，則根據(jù)錨節(jié)點情況，可以分為以下四種情況討論：

（1）S為空，則采樣區(qū)域為以未知節(jié)點上一時刻(t-1)的坐標為圓心，以vmax為半徑的圓。

（2）若S中為一個錨節(jié)點，記為s1，則未知節(jié)點選取收到此錨節(jié)點上一時刻的RSSI值，根據(jù)3.1.1節(jié)中的同心圓模型查詢最鄰近RSSI1和RSSI2(RSSI1＜RSSI＜RSSI2)，確定未知節(jié)點所在的RSSI等級圓環(huán)即為此時的采樣區(qū)域，如圖4（a）所示。

（3）若1＜S＜4，首先如（2）中所述，計算出各自的等級區(qū)域，然后，計算出這些等級圓環(huán)的重疊區(qū)域，即為采樣區(qū)域。如圖4（b）和（c）。

（4）若S≥4，計算等級區(qū)域的代價太大，不適合無線傳感網中的節(jié)點，此外，錨節(jié)點過多會出現(xiàn)采樣區(qū)域獲取失敗情況。因此，本文只考慮（1）、（2）、（3）三種情況。

若上述均定位失效，則將RSSI等級圓環(huán)擴大一倍，重新采樣。

圖4 采樣區(qū)域的計算圖

圖4（c）表明：區(qū)域覆蓋時會產生無效的交點，會影響采樣區(qū)域的確定，本文使用如下步驟，排除無效交點。

（1）任選兩個錨節(jié)點，求出其相交的區(qū)域所形成的圓環(huán)段。

（2）判斷第三個錨節(jié)點形成的交點是否在圓環(huán)段內，若否，則排除無效交點。

（3）重復（2）操作直至排除所有無效節(jié)點。

3.2 共線約束策略

計算采樣區(qū)域時，會發(fā)生錨節(jié)點共線導致定位失效的情況。文獻[14]中采用四種方法描述了共線問題，但沒有提出一種系統(tǒng)化的解決方案，文獻[15]提出了一種錨節(jié)點共線解決方案，引入共線限制因子（Collinearity Lim iting Factor，CLF），根據(jù)CLF的值，改變錨節(jié)點分布。但需要比較各邊長度，計算復雜，同時本文研究以錨節(jié)點靜止為前提從而難于運用。因此本文提出一種新的共線約束策略，通過向量公式求夾角，引入共線影響角度（Collinearity Im pact Angle，CIA）降低了計算復雜度.同時若錨節(jié)點共線或接近共線，重新選擇錨節(jié)點，提高采樣區(qū)域成功率，具體方法如下：

選取三個錨節(jié)點A，B，C，任選其中兩個節(jié)點組成向量，如圖5所示，假設為AB，AC向量，其夾角即為共線影響角度（CIA）。若三點共線，則CIA值為0或者180，若不共線，則其取值范圍為(0＜CIA＜180)，當(0＜CIA＜90)時，隨著CIA的增加，共線度越低。當(90＜CIA＜180)時，隨著CIA的增加，共線度越高，為了保持統(tǒng)一，此時采用（180-CIA）。

圖5 共線度影響角度取值范圍圖

其中CIA由向量點乘公式（6）、式（7）求得：

在錨節(jié)點固定的情況下，選取某個共線影響角度作為最小閾值，計算一跳和兩跳內的錨節(jié)點的共線影響角度，若小于閾值，則重新選擇錨節(jié)點，重新判斷，直至CIA大于閾值。

3.3 RRMCL算法

MCL算法過程可分為預測、采樣和濾波三個階段，RRMCL算法針對預測和采樣階段進行改進，通過減少采樣區(qū)域，提高采樣階段成功率。算法初始化，即t=0時刻，使用RSSI值所得出的同心圓所相交的區(qū)域作為采樣區(qū)域S0，未知節(jié)點從S0中選取N個樣本，將這N個樣本加權平均得到初始坐標值。當t＞0時，根據(jù)上一時刻未知節(jié)點坐標、錨節(jié)點信息、節(jié)點最大速度預測下一時刻位置節(jié)點的坐標。算法代碼如下：

上述算法分為采樣區(qū)域計算、樣本獲取、樣本過濾和未知節(jié)點坐標的計算四個過程；其中采樣區(qū)域計算過程中討論了四種可能（見3.1.2節(jié)），并結合3.2節(jié)所討論的錨節(jié)點共線影響角度，最終得出采樣區(qū)域。樣本獲取即從已計算過的采樣區(qū)域中隨機選擇若干個樣本。樣本過濾是根據(jù)MCL算法中的濾波條件（式（2）、式（3））將不符合條件的樣本去除。最終將符合條件的樣本點加權平均得到未知節(jié)點的坐標。

4 仿真實驗分析

為了驗證本算法的性能，基于MCL算法仿真器MCL-SIMULATOR（文獻[10-11]均使用此仿真器）進行了仿真研究，250個節(jié)點隨機地分布在400×400的矩形區(qū)域內，其中錨節(jié)點數(shù)為50，錨節(jié)點以及未知節(jié)點的通信半徑為40 m，RSSI取值范圍為（-95，-10）（單位：dB），其中-10 dB為距離為1 m時的RSSI值，-95 dB為距離40 m時的值。vmax表示未知節(jié)點移動的最大速度，算法的樣本數(shù)目為40，系統(tǒng)每次仿真時間為600個時間單位。定位誤差如式（8）所示：

其中l(wèi)表示實際位置，li表示估計位置，r表示通信半徑。

本文是MCL算法的改進算法，同時主要針對采樣區(qū)域進行改進，因此本實驗選擇MCL和MCB算法與RRMCL算法作比較，從共線度、采樣次數(shù)、節(jié)點移動速度、節(jié)點密度四個方面分析性能。

4.1 共線度影響角度

RRMCL算法的核心在于縮小采樣區(qū)域，錨節(jié)點共線對計算采樣區(qū)域影響較大，為了分析控制共線度影響角度對節(jié)點定位的影響，通過改變CIA的值，分析定位效果。

圖6描述了共線影響角度對定位誤差的影響，由于MCL算法中采樣區(qū)域不受共線影響角度的影響，本文只分析了CIA對MCB和RRMCL算法的影響。由圖6可知，當CIA＜30時，CIA對定位影響較大；當CIA＞45時，定位誤差趨于穩(wěn)定，CIA的值繼續(xù)增大，對定位結果影響較小。故本文下面的仿真約定CIA的值為45（其下限閾值為30）。

圖6 共線影響角度與定位誤差

4.2 采樣次數(shù)

設定采樣樣本數(shù)量后，MCL、MCB、RRMCL定位算法達到滿足定位要求的樣本數(shù)量時，所要采樣的次數(shù)如圖7所示。MCB算法和RRMCL算法均采用縮小采樣區(qū)域手段，故采樣次數(shù)明顯比MCL算法少。RRMCL算法因為采用RSSI等級將采樣區(qū)域進一步縮小，同時控制共線影響角度，減少共線所造成的定位失效情況。故采樣次數(shù)少于MCB算法。

圖7 不同方法的采樣次數(shù)

4.3 節(jié)點移動速度

本文研究的是移動節(jié)點的定位，則節(jié)點的移動速度對算法的影響是衡量RRMCL好壞的關鍵。圖8給出了節(jié)點移動速度vmax(vmax≤2 m/s)對定位精度的影響，從仿真結果可以看出，RRMCL算法優(yōu)于MCB算法和MCL算法，定位精度和可靠性更好。這是由于MCL算法采樣時，所選擇的采樣區(qū)域是以vmax為半徑的圓，隨著速度的增加，采樣區(qū)域也隨著增加，采樣成功率降低。MCB算法雖然采用區(qū)域也會增大，但使用了錨盒子縮小采樣區(qū)域，較MCL算法定位更好。RRMCL算法使用RSSI等級圓環(huán)計算采樣區(qū)域，速度對其采樣區(qū)域影響較小。故RRMCL優(yōu)于MCB和MCL算法。

圖8 節(jié)點速度與定位誤差

4.4 錨節(jié)點密度的影響

在保持速度一致前提下，圖9反映了節(jié)點密度與定位誤差的關系，從圖9可以看出，MCL、MCB、RRMCL算法隨著錨節(jié)點密度的增加，定位精度都在提高。當節(jié)點密度很小時，定位誤差較大，但節(jié)點密度達到0.1之后，則定位精度保持穩(wěn)定。同樣的節(jié)點密度時，RRMCL算法精度高于MCB和MCL算法，計算復雜度較低，定位效率高。

圖9 節(jié)點密度與定位誤差

5 總結

本文提出一種MCL改進算法RRMCL，給出一種計算采樣區(qū)域的方法（RSSI等級圓環(huán)法）；同時討論了錨節(jié)點數(shù)目變化時不同的計算方案。通過改變不同的仿真條件，分別分析了三種算法的定位精度和穩(wěn)定性，RRMCL算法均表現(xiàn)出了良好的定位效果。另外，本文引入共線度影響角度(CIA)，并分析了CIA對定位效果的影響。仿真結果顯示，通過控制CIA的大小，減少了錨節(jié)點共線的可能，繼而減少了定位失效的可能，使得算法在錨節(jié)點數(shù)目較少和速度較大時表現(xiàn)出了良好的適應性。

[1]Frankie K W，So H C.Accurate distributed range-based positioning algorithm for wireless sensor networks[J]. IEEE Transactions on Signal Processing，2009，57（10）：4100-4105.

[2]Wang Y，Wang X D，Wang D M，et al.Range-free localization using expected hop progress in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed System，2009，20（10）：1540-1552.

[3]Ward A，Jones A，Hopper A.A new location for the active office[J].IEEE Personal Communication，1997，4（5）：42-47.

[4]Savvides A，Han C C，Srivastava M B.dynamic fine-grained localization in Ad-hoc networks of sensors[C]//Annual International Conference on Mobile Computing and Networking，New York，USA，2001：166-179.

[5]Niculescu D，Naith B.Ad-hoc Positioning System（APS）using AOA[C]//ACM INFOCOM，California，USA，2003，3：1734-1743.

[6]Bahl P，Padmanabhan V.RADAR：an in-building RF-based user location and tracking system[C]//ACM INFOCOM，Tel Aviv，Israel，2000，2：775-784.

[7]Bulusu N，Heidemann J，Estrin D.Density adaptive algorithm s for beacon placement in wireless sensor networks[C]//IEEE ICDCS，2001：489-498.

[8]Bulusu N，Heidemann J，Estrin D.GPS-less low-cost outdoor localization for very small devices[J].IEEE Personal Communications，2000，7（5）：28-34.

[9]Nagpal R，Shrobe H，Bachrach J.Organizing a global coordinate system from local information on an ad-hoc sensor network[J].Information Processing in Sensor Networks，2003，2634：333-348.

[10]Hu L，Evans D.Localization for mobile sensor networks[C]//Proceedings of the 10th Annual International Conference on Mobile Com puting and Networking，2004：45-47.

[11]A line B，Koen L.Monte-carlo localization for mobile wireless sensor networks[C]//Lecture Notes in Computer Science，2006，4325：1317-1328.

[12]Liu C，Wu K，He T.Sensor localization with ring overlapping based on comparison of received signal strength indicator[C]//Mobile Ad-hoc and Sensor System s，2004：516-518.

[13]Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless sensor networks：a survey[J].Computer Networks，2002，38（4）：393-422.

[14]Fidan B，Drake S P，Anderson B D O，et al.Collinearity problems in passive target localization using direction finding sensors[C]//5th International Conference on Intelligent Sensors，Sensor Networks and Information Processing，Melbourne，Australia，2009：114-220.

[15]劉克中，崔永強，張金奮，等.基于Monte Carlo的多能量級移動節(jié)點定位算法研究[J].計算機科學，2011：61-64.

WU Shitong1,CHEN Liang2,LI Yunfei1,CAO Hongfei1

1.School of Computer Science & Technology, Soochow University, Suzhou, Jiangsu 215006, China
2.School of Mechanical and Electric Engineering, Soochow University, Suzhou, Jiangsu 215006, China

The localization of perceptive nodes is the foundation for WSN（Wireless Sensor Network）applications. The existing static localization algorithms can not be used in dynamic sensor networks. In this paper, the so-called RRMCL（RSSI Rank Monte Carlo Localization）localization algorithm is proposed, which is about WSN applications where target nodes are moving while anchor nodes are static. The algorithm based on MCL divides communication region to reduce the size of sampling area by using the monotonic decreasing relation between RSSI value and the distance. In order to avoid localization failure caused by anchor node collinearity, the algorithm puts forward a constraint strategy which brings collinearity impact angle. The simulation results show that the proposed RRMCL can effectively reduce sampling area and improve the localization accuracy and speed, comparing with existing MCL and MCB algorithms.

Wireless Sensor Network（WSN）; mobile localization; Monte Carlo; Received Signal Strength Indication（RSSI）

WU Shitong, CHEN Liang, LI Yunfei, et al. Application and research on Monte Carlo localization algorithm based on RSSI rank. Computer Engineering and Applications, 2014, 50（17）：114-119.

A

TP391

10.3778/j.issn.1002-8331.1210-0074

國家自然科學基金（No.60775045，No.61003259）；江蘇省科技計劃項目（No.BC2011084）；蘇州市科技計劃項目（No. SG201101）。

吳世通（1989—），男，碩士生，主要研究領域為無線傳感網；陳良（1981—），男，博士，副教授，研究方向為基于物聯(lián)網的優(yōu)化與控制；李云飛（1958—），男，教授，研究方向為無線傳感網和虛擬現(xiàn)實；曹紅飛（1987—），男，碩士研究生，研究方向為虛擬現(xiàn)實。E-mail：liyf@suda.edu.cn

2012-10-10

2012-12-20

1002-8331（2014）17-0114-06

CNKI網絡優(yōu)先出版：2013-01-11,http://www.cnki.net/kcm s/detail/11.2127.TP.20130111.0951.007.htm l