王丹 齊理 王帥

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

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

【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)絡設(shè)計的定位算法。在絕大多數(shù)文獻中，為了支持動態(tài)傳感器網(wǎng)絡的定位，僅僅提出了將靜態(tài)環(huán)境下適用的定位算法每間隔一段時間執(zhí)行一次從而實現(xiàn)對動態(tài)節(jié)點的定位。在很多情況下，因為該方法會使那些需要依靠來自較遠處的節(jié)點的信息的定位算法遭受到非常嚴重的數(shù)據(jù)延遲的限制，很有可能當遠處節(jié)點所需的信息到達它時，整個網(wǎng)絡的結(jié)構(gòu)以及拓撲都發(fā)生了變化，這樣節(jié)點的定位將失去精確性。因此，上述方法并不適用于動態(tài)環(huán)境下的傳感器網(wǎng)絡定位。分析發(fā)現(xiàn)，上述方法不適用于動態(tài)環(huán)境的主要原因并不是信息的稀缺或是算法本身的不精確，而是由于定位算法收集信息的方式，導致了定位算法的可靠性大大降低。為了提高定位算法的精確度和可靠性，本文基于蒙特卡羅方法提出一種序列蒙特卡羅定位方法，解決了在動態(tài)環(huán)境情況下傳感器網(wǎng)絡節(jié)點的定位問題。

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

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

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

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

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

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

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

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

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

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

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

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

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

Ⅳ.若沒有任何消息，則不刪除位置估計與位置預測。

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

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

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

⑵未知節(jié)點密度：在1倍通信半徑范圍內(nèi)的平均未知節(jié)點數(shù)?？梢杂孟率接嬎悖?/p>

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

3.2測量誤差

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

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

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

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

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

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

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

五、結(jié)語

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