無線自組網中一種蒙特卡羅定位新算法

王丹 齊理 王帥

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

【關鍵詞】 Ad Hoc 定位 蒙特卡羅 無線傳感器網絡

【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

一、引言

目前除了蒙特卡羅定位算法，幾乎沒有專門為動態傳感器網絡設計的定位算法。在絕大多數文獻中，為了支持動態傳感器網絡的定位，僅僅提出了將靜態環境下適用的定位算法每間隔一段時間執行一次從而實現對動態節點的定位。在很多情況下，因為該方法會使那些需要依靠來自較遠處的節點的信息的定位算法遭受到非常嚴重的數據延遲的限制，很有可能當遠處節點所需的信息到達它時，整個網絡的結構以及拓撲都發生了變化，這樣節點的定位將失去精確性。因此，上述方法并不適用于動態環境下的傳感器網絡定位。分析發現，上述方法不適用于動態環境的主要原因并不是信息的稀缺或是算法本身的不精確，而是由于定位算法收集信息的方式，導致了定位算法的可靠性大大降低。為了提高定位算法的精確度和可靠性，本文基于蒙特卡羅方法提出一種序列蒙特卡羅定位方法，解決了在動態環境情況下傳感器網絡節點的定位問題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⑵未知節點密度：在1倍通信半徑范圍內的平均未知節點數。可以用下式計算：

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

3.2測量誤差

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

由返回誤差數據計算得到，當測距誤差為0時，定位穩定后的平均定位誤差約為13.13%。

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

由返回誤差數據計算得到，當測距誤差為5%時，定位穩定后的平均定位誤差約為24.95%。

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

由返回誤差數據計算得到，當測距誤差為15%時，定位穩定后的平均定位誤差約為31.90%。

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

五、結語

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