無線自組網(wǎng)中一種蒙特卡羅定位新算法

王丹 齊理 王帥

【摘要】 在無線Ad Hoc網(wǎng)絡(luò)中，本文提出一種基于測距的序列蒙特卡羅定位算法，使定位精度大大提高，對于比傳感器節(jié)點(diǎn)能夠攜帶更多硬件與電源的無線自組網(wǎng)節(jié)點(diǎn)來說，這種新的定位算法有很強(qiáng)的實(shí)用意義。

【關(guān)鍵詞】 Ad Hoc 定位 蒙特卡羅 無線傳感器網(wǎng)絡(luò)

【Abstract】 A new algorithm of Sequential Monte Carlo localization based on distance measurement is presented in this paper. The localization accuracy is greatly improved. For the ad hoc nodes which can carry more hardware and electricity than wireless sensor network nodes. This new localization algorithm has a strong practical significance.

【Key words】 localization；Monte Carlo；wireless sensor networks

一、引言

目前除了蒙特卡羅定位算法，幾乎沒有專門為動態(tài)傳感器網(wǎng)絡(luò)設(shè)計(jì)的定位算法。在絕大多數(shù)文獻(xiàn)中，為了支持動態(tài)傳感器網(wǎng)絡(luò)的定位，僅僅提出了將靜態(tài)環(huán)境下適用的定位算法每間隔一段時間執(zhí)行一次從而實(shí)現(xiàn)對動態(tài)節(jié)點(diǎn)的定位。在很多情況下，因?yàn)樵摲椒〞鼓切┬枰揽縼碜暂^遠(yuǎn)處的節(jié)點(diǎn)的信息的定位算法遭受到非常嚴(yán)重的數(shù)據(jù)延遲的限制，很有可能當(dāng)遠(yuǎn)處節(jié)點(diǎn)所需的信息到達(dá)它時，整個網(wǎng)絡(luò)的結(jié)構(gòu)以及拓?fù)涠及l(fā)生了變化，這樣節(jié)點(diǎn)的定位將失去精確性。因此，上述方法并不適用于動態(tài)環(huán)境下的傳感器網(wǎng)絡(luò)定位。分析發(fā)現(xiàn)，上述方法不適用于動態(tài)環(huán)境的主要原因并不是信息的稀缺或是算法本身的不精確，而是由于定位算法收集信息的方式，導(dǎo)致了定位算法的可靠性大大降低。為了提高定位算法的精確度和可靠性，本文基于蒙特卡羅方法提出一種序列蒙特卡羅定位方法，解決了在動態(tài)環(huán)境情況下傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位問題。

二、序列蒙特卡羅算法原理

由于傳感器節(jié)點(diǎn)以及定位精度的原因，使得移動無線自組網(wǎng)中的定位比機(jī)器人定位難得多。但是，使用這種定位方法，在網(wǎng)絡(luò)中節(jié)點(diǎn)間可以通過合作來共享位置信息來實(shí)現(xiàn)定位。

將時間分成離散的時間片，因?yàn)楣?jié)點(diǎn)都在相對于之前的位置移動，所以在每個時間單元內(nèi)都需要對節(jié)點(diǎn)進(jìn)行重新定位。想要得到節(jié)點(diǎn)可能位置的概率分布，從而協(xié)助定位。因?yàn)楣?jié)點(diǎn)在網(wǎng)絡(luò)中持續(xù)運(yùn)動，之前的位置信息對目前的位置來講將會越來越無用。從另一方面來說，可以根據(jù)從錨節(jié)點(diǎn)新收到的觀察信息濾除不正確的估計(jì)位置估計(jì)。在移動并接收了觀察信息之后，節(jié)點(diǎn)之前可能位置的概率分布就更難確定了。除了一些特殊的情況（線性高斯?fàn)顟B(tài)模型 卡爾曼濾波器），想要用數(shù)值法解出之前的分布幾乎是不可能的。

序列蒙特卡羅法提供了一種基于仿真的方法用于估計(jì)之前的非線性離散時間動態(tài)模型的位置分布。序列蒙特卡羅法的核心思想就是通過一系列，N個帶有權(quán)重的采樣，使用“重要性采樣”（importance sampling）法，遞歸的對這N個帶有權(quán)重的采樣進(jìn)行更新。序列蒙特卡羅定位法已經(jīng)成功地應(yīng)用在目標(biāo)跟蹤，機(jī)器人定位與計(jì)算圖形學(xué)中。

三、基于測距的序列蒙特卡羅定位算法

序列蒙特卡羅方法雖然相對于其它現(xiàn)有的定位算法更適于動態(tài)傳感器網(wǎng)絡(luò)，但是這種算法仍然存在定位精度較低的不足。針對這個問題，這部分基于序列蒙特卡羅算法，提出一種基于測距的蒙特卡羅定位算法，解決了動態(tài)傳感器網(wǎng)絡(luò)定位精度較低的問題。

基于以上的序列蒙特卡羅定位算法，再考慮到無線自組網(wǎng)節(jié)點(diǎn)相對于傳感器節(jié)點(diǎn)存在著能夠攜帶更多電能，機(jī)能相對強(qiáng)大等優(yōu)勢，在節(jié)點(diǎn)上加裝測距模塊的可行也相對更高，本文提出一種基于測距的序列蒙特卡羅算法，算法與傳統(tǒng)序列蒙特卡羅算法類似，但由于位置生成步驟相對簡單了許多，于是與前一步驟合并，故步驟分為三步：

⑴位置預(yù)測：根據(jù)濾波后的位置估計(jì)，對下一步可能位置進(jìn)行預(yù)測，在N個估計(jì)點(diǎn)周圍以本步估計(jì)位置為圓心，v為半徑的圓形區(qū)域內(nèi)生成N個預(yù)測點(diǎn)。

⑵收取觀測信息：由于是基于測距的定位算法，故未知節(jié)點(diǎn)可直接測得在自身測距半徑d內(nèi)的錨節(jié)點(diǎn)到自己的距離r，并將此距離保存。

⑶位置濾波與位置生成：根據(jù)以上觀察信息，將不可能的位置估計(jì)從估計(jì)矩陣中刪除，刪除后根據(jù)觀測信息將刪除的估計(jì)點(diǎn)數(shù)與預(yù)測點(diǎn)數(shù)補(bǔ)齊，假設(shè)r為測得距離，e為測距誤差，刪除與預(yù)測策略如下：

Ⅰ.若在自身測距半徑d內(nèi)只有一個錨節(jié)點(diǎn)，則將預(yù)測中不在以該錨節(jié)點(diǎn)為圓心，r為半徑，e為測距誤差的圓環(huán)上的預(yù)測點(diǎn)及下步位置估計(jì)刪除，并在該圓環(huán)中隨機(jī)生成本步估計(jì)點(diǎn)坐標(biāo)，并根據(jù)運(yùn)動模型預(yù)測下步坐標(biāo)。

Ⅱ.若在自身測距半徑d內(nèi)有兩個錨節(jié)點(diǎn)，則根據(jù)兩圓相交關(guān)系可求出該未知節(jié)點(diǎn)的兩個可能存在的位置，將位置預(yù)測中不在以這兩個位置為圓心，測距誤差為半徑的小圓外的預(yù)測點(diǎn)及下步位置估計(jì)刪除，并在這兩個小圓內(nèi)生成位置估計(jì)點(diǎn)坐標(biāo)，并根據(jù)運(yùn)動模型預(yù)測下步坐標(biāo)。

Ⅲ.若在自身測距半徑d內(nèi)有兩個以上錨節(jié)點(diǎn)，根據(jù)多圓相交關(guān)系，可以確定出未知節(jié)點(diǎn)的位置，再將以該位置為圓心，測距誤差為半徑的小圓外的預(yù)測點(diǎn)及下步位置估計(jì)刪除，并在此小圓內(nèi)生成位置估計(jì)點(diǎn)坐標(biāo)，并根據(jù)運(yùn)動模型預(yù)測下步坐標(biāo)。

Ⅳ.若沒有任何消息，則不刪除位置估計(jì)與位置預(yù)測。

四、基于測距的序列蒙特卡羅定位算法仿真分析

在仿真環(huán)境中，節(jié)點(diǎn)被隨機(jī)的撒在一個250m x 250m的矩形區(qū)域，我們給節(jié)點(diǎn)設(shè)定一個固定的通信半徑r，錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的通信半徑r都等于25m，節(jié)點(diǎn)采用自由隨機(jī)運(yùn)動模型，可以變化的各項(xiàng)參數(shù)如下：

⑴錨節(jié)點(diǎn)與未知節(jié)點(diǎn)最大速度v：每個節(jié)點(diǎn)的速度都服從[0，v]的均勻分布

⑵未知節(jié)點(diǎn)密度：在1倍通信半徑范圍內(nèi)的平均未知節(jié)點(diǎn)數(shù)?？梢杂孟率接?jì)算：

由以上一組圖可以發(fā)現(xiàn)，在錨節(jié)點(diǎn)密度較低，如sd=1時，定位精度較差，結(jié)果并不比傳統(tǒng)非測距序列蒙特卡羅算法好很多，但當(dāng)錨節(jié)點(diǎn)密度提高時，定位精度增加比較明顯，在其他條件不變，sd=4時，其定位精度13.13%要遠(yuǎn)好于傳統(tǒng)序列蒙特卡羅方法的40%左右，雖然由于測距模塊的引進(jìn)可能引起網(wǎng)絡(luò)節(jié)點(diǎn)的體積增加以及耗電量增大等結(jié)果，但對于通常情況下的無線自組網(wǎng)節(jié)點(diǎn)，如PDA，筆記本電腦等來說，這樣的體積增加與耗電量增大一般來說是可以接受的，故這種定位算法具有較強(qiáng)的實(shí)用性。

3.2測量誤差

當(dāng)sd=4，nd=10，v=d=25，N=10，e=0時，如圖4所示。

由返回誤差數(shù)據(jù)計(jì)算得到，當(dāng)測距誤差為0時，定位穩(wěn)定后的平均定位誤差約為13.13%。

當(dāng)sd=4，nd=10，v=d=25，N=10，e=5%時，如圖5所示。

由返回誤差數(shù)據(jù)計(jì)算得到，當(dāng)測距誤差為5%時，定位穩(wěn)定后的平均定位誤差約為24.95%。

當(dāng)sd=4，nd=10，v=d=25，N=10，e=15%時，如圖6所示。

由返回誤差數(shù)據(jù)計(jì)算得到，當(dāng)測距誤差為15%時，定位穩(wěn)定后的平均定位誤差約為31.90%。

由以上一組圖以及數(shù)據(jù)可以發(fā)現(xiàn)，測距誤差也是影響定位精度的一個重要參數(shù)，當(dāng)測距誤差提高后，精度下降的比較明顯，原因是很顯然的，如果測距出現(xiàn)誤差，那么之后的對節(jié)點(diǎn)位置計(jì)算估計(jì)等都會出現(xiàn)誤差，由于誤差的重疊積累導(dǎo)致了結(jié)果的誤差，所以高精度測距模塊的選擇也是提高定位精度的一個有效方法。

五、結(jié)語

本文在傳統(tǒng)序列蒙特卡羅定位算法的基礎(chǔ)上提出了一種基于測距的序列蒙特卡羅定位算法，從而在條件相似的情況下，明顯地提高了動態(tài)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位精度。仿真結(jié)果表明，這部分提出算法的定位精度將遠(yuǎn)高于序列蒙特卡羅算法，從而有效解決了動態(tài)傳感器網(wǎng)絡(luò)定位精度較低的問題。