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

王迎云　鹿建銀　谷敏玲

【摘 要】無線傳感器網(wǎng)絡(luò)已經(jīng)對人們的生活產(chǎn)生了極大的影響，本文主要分析了無線傳感器網(wǎng)絡(luò)的定位關(guān)鍵技術(shù)，比較了傳統(tǒng)蒙特卡羅定位算法及基于測距的RSSI蒙特卡羅定位算法，并通過實驗驗證了RSSI-MCL比MCL的定位準(zhǔn)確性高。

【關(guān)鍵詞】無線傳感器網(wǎng)絡(luò)；MCL；RSSI

中圖分類號： TP212.9；TN929.5 文獻(xiàn)標(biāo)識碼： 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 引言

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

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

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

全球定位系統(tǒng)GPS，采用衛(wèi)星定位，雖然是一個定位精確、高效的定位技術(shù)，但其通常應(yīng)用在空曠的外部環(huán)境中，且應(yīng)用在傳感器網(wǎng)絡(luò)中成本很高，因此非常不適用，研究一種適用于無線傳感器網(wǎng)絡(luò)移動節(jié)點狀態(tài)下的低成本、高效、精確定位的技術(shù)成為了無線傳感網(wǎng)絡(luò)的關(guān)鍵。

1 定位算法

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

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

2 RSSI-MCL算法

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

（1）位置預(yù)測階段

設(shè)定某一位置未知節(jié)點處于不停移動的狀態(tài)，根據(jù)節(jié)點的移動特性，可以用m ～P（m |m ）表示該節(jié)點在前一時刻的位置為m 時，當(dāng)前時刻位置在m 的概率，該概率分布稱為轉(zhuǎn)移分布。

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

在位置預(yù)測階段，利用前一時刻的位置信息對當(dāng)前時刻的位置進(jìn)行預(yù)測，節(jié)點可能的位置從上述的圓環(huán)形區(qū)域中隨機(jī)采樣獲得，圓環(huán)區(qū)域就是采樣區(qū)域。

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

具體地，設(shè)定位置未知節(jié)點從采樣區(qū)域中采集一組樣本m ，i=1，2，L，N，其中N是樣本數(shù)量。每一個樣本都存在一個非負(fù)的權(quán)值w ，其定義為：

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

根據(jù)樣本和對應(yīng)權(quán)值的集合 ，可以得到節(jié)點位置的后驗分布為：

通過節(jié)點位置預(yù)測和權(quán)值更新的反復(fù)計算之后，可得到最終的后驗分布 。

（3）重采樣階段

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

3 仿真分析

4 總結(jié)

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

【參考文獻(xiàn)】

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

[2]徐彥.基于WSN的目標(biāo)定位技術(shù)的研究[D].南京：南京航空航天大學(xué)，2016.

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

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

[5]李建坡，鐘鑫鑫，徐純.無線無線傳感器網(wǎng)絡(luò)靜態(tài)節(jié)點定位算法綜述[J].東北電力大學(xué)學(xué)報，2015，02：73-82.