移動無線傳感器網絡節點合成蒙特卡羅定位算法

梁小滿，陳堅禎，許瓊方

（衡陽師范學院 計算機科學系，湖南 衡陽 421008）

0 引 言

無線傳感器網絡節點的位置信息對網絡監測活動至關重要，事件發生的位置或獲取信息的節點位置是傳感器節點監測消息中包含的重要內容，沒有位置信息的監測消息往往毫無意義［1］。所以，節點的自定位在傳感器網絡中的意義非同一般。節點獲得位置信息的最直接的做法是利用全球定位系統（Global Positioning System，GPS）來實現［2］。可是，使用GPS來獲得傳感器網絡中所有節點的位置信息卻受到價格、體積、功耗以及可擴展性等多種因素的限制。因此，利用傳感器網絡中少量已知位置的節點（錨節點）來獲得其它未知節點的位置信息成了當前主要的研究工作［3－4］。

2004年，Hu和Evans在文獻［5］中把蒙特卡羅定位算法（Monte Carlo Localization，MCL）應用到移動傳感器網絡，利用加權粒子表示節點位置的后驗分布來實現節點定位。算法具有較高的運算效率和定位精度，但它的采樣成功率不高，且易出現粒子退化現象。這需要對退化粒子重新抽樣才能保證定位精度，可又要耗費大量計算時間。為解決該問題，陸續出現了多種改進的蒙特卡羅定位方法。Baggio等在文獻［6］中提出了 MCB算法，采用定義錨節點盒和樣本盒的方法構建近似觀測模型與運動模型，將文獻［5］中運動模型的距離運算轉變成比較運算，減少了運算時間，并且由于在采樣階段運用觀測模型的信息，使采樣成功率得到了一定程序的提高。不過在錨節點盒中觀測數據所占比重很小時，采樣成功率仍然不盡人意。還有，MCB算法在重采樣階段看重觀測模型卻忽略了運動模型，當錨節點密度較低時節點的定位精度反而會降低。石朝俠等人在文獻［7］中給出了Mixture－MCB算法，該算法引入了混合采樣的思想，提高采樣成功率的同時使定位精度得到了有效提高。Yi等人在文獻［8］中給出了多跳蒙特卡羅定位算法（MMCL），該算法將錨節點信息在全網泛洪，使得接收不到錨節點信息的未知節點數量大大減少，于是，在錨節點密度較低情形下可降低定位誤差。但是，上述這些改進的方法在單獨使用時也都有其局限性，因此，我們給出一種集聚上述改進方法優勢且適應性更強的新方法——合成蒙特卡羅定位算法（Synthesized Monte Carlo Localization，SMCL）。

1 合成蒙特卡羅定位算法（SMCL）

移動傳感器網絡中的節點由于運動速率和運動方向不總相同，而且運動沒有規律，導致網絡的拓撲結構時常發生變化，使得錨節點的分布不均勻，一些地方稠密，一些地方稀疏。利用前面提到的在某特定情況下具有自身優勢的定位方法不能解決這種由于節點運動使得拓撲結構不斷發生變化的實際問題。合成蒙特卡羅定位算法就是適應這種情況變化的需要而提出的新的方法。它每隔一定時長的時間周期對感知區域進行一次錨節點分布情況統計，針對錨節點的不同分布，合理運用相應的MCL算法，對未知節點進行有效定位。這樣做不但可以提高定位精度，還可以縮短計算時間，節省通信開銷。在未知節點的單跳通信范圍內，如果錨節點數滿足采樣需求，就運用Mixture－MCB算法，以節省計算時間；如果錨節點數不足，就使用MMCL算法，通過多跳范圍內的錨節點進行采樣來提高定位精度。設NA表示錨節點，NN表示未知節點，NAT表示錨節點信息表，ID表示節點身份標識符，x，y分別表示節點在笛卡兒坐標系中的橫坐標和縱坐標，c表示位置校正系數，h表示跳數，s表示節點標志符。i，j，k為節點序號，t用來計時，L表示位置集合。具體算法表示如下：

2 仿真實驗

2.1 實驗場景及假設

仿真實驗在LabVIEW 2011軟件開發平臺進行。假設二維平面場景設在一個邊長為500m的無障礙正方形區域，節點（包括500個普通節點和最多150個錨節點）隨機部署在該區域內，所有節點都可移動，所有節點的通信半徑r＝50m。實驗在一種理想狀態下進行，所有仿真結果都取50次獨立仿真的平均值。且設定信息傳遞瞬時完成，在信息傳遞的過程中，不考慮通信延遲，節點間的碰撞，信息丟失；在節點移動時，不考慮移動誤差；在未知節點定位瞬間，所有節點都處于靜止狀態，即當一個節點收到NAi的位置信息時，NAi的位置還沒改變，同時不考慮錨節點的定位誤差。

2.2 實驗結果分析

圖1 錨節點速度與定位誤差的關系Fig 1 Relation of location errors estimation and velocity of anchor nodes

圖1給出了SMCL算法在不同密度下，錨節點的運動速率與定位誤差間的關系。從圖中可以看出，錨節點密度高（Ad值大）的定位誤差較低，無論在什么時候，密度Ad＝1.25個／跳的定位誤差總比比它密度值小的其它三種密度的定位誤差低。此 外，對于任何一根曲線，在錨節點移動速度加快時，定位誤差沒有隨之增大，而是在總體上基本趨于穩定的前提下略有減少。原因應該是在錨節點移動速度加快時，單位時間內未知節點獲得的錨節點信息的數量增多，好似靜態時未知節點周圍擁有多一些的錨節點，從而能更快速、更準確地確定需定位的節點的位置。

圖2給出的是 MCL算法、MCB算法、Mixture－MCB算法、MMCL算法和SMCL算法等多種不同蒙特卡羅算法的錨節點密度與定位誤差的關系。從圖中可以看出，伴隨節點密度值的增大，定位誤差值總的趨勢是變小。在錨節點達到3個／跳的密度值時，MCB、Mixture－MCB的定位準確度明顯高于MMCL，但MMCL在錨節點密度不超過2個／跳時的定位精度總體上要比 MCL算法、MCB算法、Mixture－MCB算法高。所有有關蒙特卡羅算法隨節點密度值的增大定位更加準確，但SMCL算法效果最好。

實驗結果印證了我們設計SMCL算法時，1跳范圍內錨節點數不超過2時使用MMCL算法，超過2時使用Mixture－MCB算法的做法較好地吸收了Mixture－MCB算法和MMCL算法的優點，合理地規避了上述兩種算法弱點，很大程度上擺脫了節點密度和有效采樣數量的束縛。從而使SMCL成為了一種能根據錨節點數量進行自適應的分布式移動節點自定位算法。

圖2 錨節點密度與定位誤差的關系Fig 2 Relation of location errors estimation and density of anchor nodes

3 結 論

移動傳感器網絡節點自定位是傳感器網絡的關鍵技術，是傳感器網絡推廣應用的前提。有關蒙特卡羅定位方法是一類實用性比較強的方法，特別適用于錨節點數量少、密度低的情況。本文提出的SMCL方法根據節點一跳范圍內的錨節點的數量分情況處理，在數量不超過2時，使用MMCL算法，在數量大于2時，使用Mixture－MCB算法，擺脫了錨節點數量小、密度低的限制。在移動無線傳感器網絡節點自定位時具有良好的自適應性，在移動無線傳感器網絡的推廣應用中能起到積極的作用。

［1］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京：清華大學出版社，2005.

［2］Bulusu D.E N，Heidenmann J.GPS－less low cost outdoor localization for very small devices［J］.IEEE Personal Communications Magazine，2000，7（5）：28－34.

［3］Galstyan A，Krishnamachari B，Lerman K，et al.Distributed online localization in sensor networks using a moving target［C］.Proceedings of the Third International Symposium on Information Processing in Sensor Networks（IPSN），Berkeley，California：USA，2004：61－70

［4］Peng R，Sichitiu M L.Localization of wireless sensor networks with a mobile beacon［C］.Proceedings of the First IEEE Conference on Mobile Ad－hoc and Sensor Systems （MASS 2004），Fort Lauderdale：FL，USA，2004：174－183

［5］Hu L，Evans D.Localization for mobile sensor networks［C］.Proceedings of the 10th International Conference on Mobile Computing and Networking.Philadelphia：Pennsylvania，USA，2004：45－57

［6］Baggio A，Langendoen K.Monte Carlo localization for mobile wireless sensor networks［J］.Lecture Notes in Computer Science，2006，4325（11）：317－328

［7］石朝俠，王燕清，洪炳镕，等.基于蒙特卡羅箱方法的移動感知網節點定位方法［J］.高技術通信，2007，17（8）：809－813

［8］YiJ，Yang S，Cha H.Muliti－Hop Based Monte Carlo localization for mobile wireless sensor networks ［C］.Proceedings of the 4th annual IEEE Communications Society conference on sensors，Mesh，and Ad Hoc Communications and Networks Korea，2007：162－171.