基于測距的蒙特卡羅定位算法研究

王迎云　鹿建銀　谷敏玲

【摘 要】無線傳感器網絡已經對人們的生活產生了極大的影響，本文主要分析了無線傳感器網絡的定位關鍵技術，比較了傳統蒙特卡羅定位算法及基于測距的RSSI蒙特卡羅定位算法，并通過實驗驗證了RSSI-MCL比MCL的定位準確性高。

【關鍵詞】無線傳感器網絡；MCL；RSSI

中圖分類號： TP212.9；TN929.5 文獻標識碼： A 文章編號： 2095-2457（2018）30-0107-003

DOI：10.19694/j.cnki.issn2095-2457.2018.30.046

Research on Monte Carlo Location Algorithm Based on Ranging

WANG Ying-yun1 LU Jian-yin2 GU Min-ling3

（1.Anhui Xinhua University，Hefei Anhui 230088，China

2.Chaohu University，Hefei Anhui 238000，China

3.Anhui Xinhua University，Hefei Anhui 230088，China）

【Abstract】Wireless sensor networks have a great impact on people's lives.This paper mainly analyzes the key technologies of wireless sensor networks positioning，compares the traditional Monte Carlo positioning algorithm and the RSSI Monte Carlo positioning algorithm based on ranging，and verifies the positioning accuracy of RSSI-MCL than MCL through experiments.

【Key words】Wireless Sensor Network；MCL；RSSI

0 引言

無線傳感器網絡WSN，即Wireless Sensor Network，是由大量部署在監控區域的低成本%低功耗的微型傳感器節點組成，以無線通信方式組成的分布式自組織網絡，傳感器布置在監測區域內，能夠自主采集和處理監測區域內的信息，并最終發送給觀察者，是一種全新的信息獲取和處理技術[1]。無線傳感器網絡中的每個節點都有能源、有限的計算能力和存儲空間。且它們能夠為獲取信息的定位提供依據。

無線傳感器網絡最初由美國軍方提出，最早被應用與國防軍事后，在國內外的迅速發展，如今，WSN在環境監測、國家安全、天氣預測、城市交通、醫療護理、智能家居、目標跟蹤、生物研究、反恐救災等領域都有著很廣泛的應用，給人們的生活帶來了極大的方便。對于大部分應用來說，采集到的數據必須知道傳感器的具體位置，只有在知道了傳感器位置信息的前提下，采集到的數據才有意義，才能知道事件所發生的位置[2]。

在傳感器網絡的各種應用中，監測到事件之后關心的一個重要問題就是該事件發生的位置[3]。如在城市交通應用中需要知道交通堵塞信息所對應的具體區域位置；在反恐救災中需要知道災害發生的現場位置等。在判斷結果位置前，傳感器節點必須要先精確定位自身所在的位置，然后才能為最終的結果判定提供依據。但是，在傳感器網絡中，傳感器節點往往是處于移動的狀態，如何在移動狀態下能夠精確定位出節點的位置信息，成為了大家關心熱點。

全球定位系統GPS，采用衛星定位，雖然是一個定位精確、高效的定位技術，但其通常應用在空曠的外部環境中，且應用在傳感器網絡中成本很高，因此非常不適用，研究一種適用于無線傳感器網絡移動節點狀態下的低成本、高效、精確定位的技術成為了無線傳感網絡的關鍵。

1 定位算法

2004年，Lingxuan Hu和Evans根據機器人定位技術中廣泛應用的序列蒙特卡羅方法，將其應用在無線傳感網絡，并提出了一種移動傳感器定位算法，即序列蒙特卡羅定位算法（稱為MCL算法）[4]。該算法雖然能夠實現移動節點的目標定位，但是算法采樣次數非常多且成功率低。Baggio等人在MCL的基礎上提出了蒙特卡羅盒定位MCB算法，該算法在錨箱里采樣，相對于序列蒙特卡羅定位算法來說，采樣范圍變小了，采樣成功率提高，但是當信標在錨箱內的分布密度很低時，絕大部分的采樣都是無效的，成功率也會降低。后期又提出把測距信息應用到MCL算法中，但其具體測量又需要硬件的支持。

節點定位算法分為距離相關的定位算法和距離無關的定位算法兩類，距離相關的定位算法（range-based），是指通過直接或間接的獲取節點之間的距離信息或角度信息，使用三邊、三角或極大似然等定位算法來估計未知節點的坐標值[5]。主要的測距算法有：接收信號強度指示（Received Signal Strength Indication，RSSI）、到達時間（Angle of Arrival，AOA）、到達時間差（Time Difference of Arrival，TDOA）等，RSSI算法通過信號衰減模型將信號衰減轉化為與之相匹配的距離，算法相對簡單且其成本較低，而其他距離相關的方法都需要額外配備昂貴的硬件模塊來接收信號極大增加了投資成本，基于RSSI算法進行測距的定位系統主要有：Calamari、Microsoft's RADAR、SpotON；距離無關的定位算法無需測量距離和角度信息，根據網絡連通度、多跳路由等信息來實現節點定位，其成本較低但定位精度不高，常用的距離無關的算法有：質心、APIT（Approximate Point-In-Triangulation Test）、DV–Hop、DV-Distance、凸規劃等定位算法。

2 RSSI-MCL算法

RSSI-MCL算法主要有三個步驟：

（1）位置預測階段

設定某一位置未知節點處于不停移動的狀態，根據節點的移動特性，可以用m ～P（m |m ）表示該節點在前一時刻的位置為m 時，當前時刻位置在m 的概率，該概率分布稱為轉移分布。

若該節點隨機從最大速度vmax和最小速度vmin之間選取某一個值作為運動速度，并隨機從0，2？仔中選取某一個值作為運動方向，那么轉移分布P（m |m ）便形成了一個以mk-1為圓心，vmin為內半徑，vmax為外半徑的圓環，表示如下：

在位置預測階段，利用前一時刻的位置信息對當前時刻的位置進行預測，節點可能的位置從上述的圓環形區域中隨機采樣獲得，圓環區域就是采樣區域。

根據k時刻觀測值位置信息，未知的節點濾除不滿足條件的樣本，并根據權值更新剩余樣本中的位置數據。使用n ～P（n |m ）描述在給定位置的RSSI的測量值的概率分布，該概率為觀測分布。

具體地，設定位置未知節點從采樣區域中采集一組樣本m ，i=1，2，L，N，其中N是樣本數量。每一個樣本都存在一個非負的權值w ，其定義為：

式中w 表示樣本i在k時刻的權重，根據觀測分布，其計算公式為：

根據樣本和對應權值的集合 ，可以得到節點位置的后驗分布為：

通過節點位置預測和權值更新的反復計算之后，可得到最終的后驗分布 。

（3）重采樣階段

計算當前的位置需要反復進行上述的預測和濾波階段，但在多次迭代之后，由于算法退化問題的存在，可能出現大多數樣本的權值都趨近0，而只有一個樣本的權值趨近1的現象。退化現象意味著大量的計算浪費在了那些對后驗分布貢獻很小的粒子上，為了避免這種現象的發生，需要檢測算法是否發生退化現象，并在檢測到算法退化的時候，進行重采樣。

3 仿真分析

4 總結

RSSI-MCL算法雖然能夠在一定程度上提高算法的定位精度，但是以犧牲算法的運算效率為代價的，這使得數據量較大時，對于節點的定位時間花銷較高，今后將從提高算法的運算效率、降低時間復雜度入手進行研究，以更進一步優化算法。

【參考文獻】

[1]游曉鵬等.RSSI輔助的蒙特卡羅盒定位算法[J].計算機 技術與發展，2013，12（23）：11-15.

[2]徐彥.基于WSN的目標定位技術的研究[D].南京：南京航空航天大學，2016.

[3]孫正章.基于蒙特卡羅的無線傳感器網絡移動節點定位算法研究[D].長沙：湖南大學.2009.

[4]姚放吾.WSN中一種基于重疊區域的蒙特卡羅定位算法[J].計算機技術與發展.2012，5（22）：165-168.

[5]李建坡，鐘鑫鑫，徐純.無線無線傳感器網絡靜態節點定位算法綜述[J].東北電力大學學報，2015，02：73-82.