移動無線傳感器網(wǎng)絡(luò)節(jié)點合成蒙特卡羅定位算法

梁小滿，陳堅禎，許瓊方

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

0 引 言

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

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

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

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

2 仿真實驗

2.1 實驗場景及假設(shè)

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

2.2 實驗結(jié)果分析

圖1 錨節(jié)點速度與定位誤差的關(guān)系Fig 1 Relation of location errors estimation and velocity of anchor nodes

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

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

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

圖2 錨節(jié)點密度與定位誤差的關(guān)系Fig 2 Relation of location errors estimation and density of anchor nodes

3 結(jié) 論

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

［1］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［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－h(huán)oc and Sensor Systems （MASS 2004），F(xiàn)ort 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］石朝俠，王燕清，洪炳镕，等.基于蒙特卡羅箱方法的移動感知網(wǎng)節(jié)點定位方法［J］.高技術(shù)通信，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.