移动无线传感器网络节点合成蒙特卡罗定位算法

梁小满，陈坚祯，许琼方

（衡阳师范学院 计算机科学系，湖南 衡阳 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.