基于測(cè)距的蒙特卡羅定位算法研究

王迎云　鹿建銀　谷敏玲

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

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

中圖分類號(hào)： TP212.9；TN929.5 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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é)點(diǎn)組成，以無線通信方式組成的分布式自組織網(wǎng)絡(luò)，傳感器布置在監(jiān)測(cè)區(qū)域內(nèi)，能夠自主采集和處理監(jiān)測(cè)區(qū)域內(nèi)的信息，并最終發(fā)送給觀察者，是一種全新的信息獲取和處理技術(shù)[1]。無線傳感器網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都有能源、有限的計(jì)算能力和存儲(chǔ)空間。且它們能夠?yàn)楂@取信息的定位提供依據(jù)。

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

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

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

1 定位算法

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

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

2 RSSI-MCL算法

RSSI-MCL算法主要有三個(gè)步驟：

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

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

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

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

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

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

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

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

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

（3）重采樣階段

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

3 仿真分析

4 總結(jié)

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

【參考文獻(xiàn)】

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

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

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

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

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