基于Monte-Carlo方法的井下无线传感网络定位算法

赵 明，乔钢柱，介 婧

太原科技大学 复杂系统与智能计算研究所，太原 030024

基于Monte-Carlo方法的井下无线传感网络定位算法

赵 明，乔钢柱，介 婧

太原科技大学 复杂系统与智能计算研究所，太原 030024

1 意义

无线传感器网络（Wireless Sensor Network，WSN）成本低廉、布放简单，被广泛应用于军事、医疗、环境监测、物流运送、空间探测等多个领域。在大多数的无线传感器网络应用中，传感器网络节点的位置信息是不可或缺的，缺乏了位置数据，传感器网络采集到的数据将失去意义。传感器网络节点自身定位技术是WSN应用中的重要组成部分，也是无线传感器网络研究领域中的关键性支撑技术之一。

在井下，环境条件总是在不断地变化，在这样的环境里面定位需要稳定、精确、且能长期有效。井下定位主要面临如下问题，首先区域空间狭窄，巷道环境差异大，在地面上的一些定位方法在这里容易受限制。其次，井下可见度低，湿度大，并伴有烟雾及粉尘，无线通信易受影响。无线传感器网络的Monte-Carlo定位方法是用后验概率模型来进行定位的一种方法，有较好的定位精度，有很好的健壮性，且能充分利用巷道空间狭窄的环境特点来做进一步的改进。

2 背景

无线传感网络定位按是否基于测距分为基于测距的定位算法和无须测距的定位算法。基于测距的定位通过测量节点到节点间的距离、角度信息，然后利用三边测距、三角测距或最大似然估计的方法进行节点自身定位。典型的基于测距的定位算法有RSSI[1]，TOA[2]，TDOA[3]，AOA[4-5]等。这些算法大部分都需要增加额外的硬件设备，增加了节点的成本，同时又增加了节点的能耗。基于测距技术的定位在定位精度上有一定的优势，但在低功耗、低成本的应用中还存在一些问题。无须测距技术的定位则不需要测量距离和角度，而是依据网络的连通性来进行定位，典型算法的有DV-Hop[6-7]、凸规划[8-9]、MDS-MAP[10]等。而对于井下环境，无需测距的定位方法更有优势。

在井下，无线定位目前主要分为两类，一类是基于射频识别（Radio Frequency Identification，RFID）技术，如文献[11]介绍了一种井下RFID读卡器防碰撞算法，文献[12]介绍了一种矿山井下RFID人员定位系统的定位原理实现过程，文献[13]介绍了RFID井下人员定位在应用上的几个关键问题，并给出了适当的解决方法。一类是通过传感器节点来实现定位，如文献[14]介绍了信标节点链式部署的井下无线传感器网络定位算法，文献[15]介绍了井下无线传感器网络结构自适应的系统。一般来讲RFID定位时都是在区域入口或关键通道设置读卡器，来记录相关人员进出记录，实时性及精度上不如传感器节点。而井下，人员的位置都是在劫态变化的，因此井下无线传感器网络需要能够进行移动定位。

移动无线传感网定位无须测距的MCL（Monte-Carlo Location）定位算法最早由文献[16]提出，其定位精度较好，能利用节点的移动性提高算法的精度。本文便是结合井下环境的特点对MCL进行了改进提出了中心蒙特卡洛（Center Monte-Carlo Location，CMCL）算法。

3 MCL和MCB定位原理及过程

Hu和Evans提出的MCL（Monte-Carlo Location）定位算法[16]是用后验概率模型来进行定位的一种方法，定位精度和效率很出色。MCL定位方法当中分为初始化，采样和过滤三部分，而把时间分为一个个时间片，对每个节点反复执行进行采样和过滤来不断地更新所在的位置。具体方法如下：把时间分成离散的时间片，用t表示其中某一个单独的时间片，用lt表示当前未知节点在时间片t时所在的位置，用Ot表示锚节点在时间t和时间t-1之间所观测到的当前未知节点的坐标值。公式 p(lt/lt-1)表示当前未知节点的通过在t-1时间片所在的位置来预测在时间t时所在的位置，公式 p(lt/ot-1)表示当前未知节点的通过在t-1时间片观测的位置来预测在时间t时所在的位置。用Lt表示一组样本位置的集合，即样本集合中每一个样本的位置lt在一起组成了Lt。每一个时间片开始第一步，算法都会递归地运算出样本集，Lt-1表示时间t-1时的位置，那么借助于Ot和lt-1可以计算出lt来。每个样本是从当前节点的第一个邻居锚节点的通信范围当中抽取的，但是对于每个时间片中的样本集Lt，算法最多可能要经过2次过滤，即若第一次抽取的样本经过过滤个数不足时，便进行第二次样本抽取过滤。而每个样本的过滤则是要经过两次遍历，第一次遍历所有的一跳邻居锚节点，第二次遍历所有的二跳邻居锚节点。即检查该样本是否是在当前这个邻居锚节点的通讯范围之内，如果是两次遍历所有的邻居锚节点通讯范围内都有该样本节点，那么这个样本节点是合格的，如果这个过程中有一个邻居锚节点通讯范围内没有该样本节点，那么这个样本节点不合格。要重新抽取样本。整个过程中过滤是MCL定位方法中耗时较多的部分。

随后Baggio，A和K.Langendoen提出了一种改进的MCB（Monte-Carlo Boxed Location）定位方法[17]，定位精度有了进一步的提升，计算量进一步下降，且充分利用了二跳邻居节点，但在井下环境当中其过滤方法效果不明显，且计算量也不小。MCB定位方法改进了MCL抽取样本的区域，即是从所有邻居锚节点通信重叠区域当中抽取样本。多加了创建或更新锚盒的部分，锚盒的边界如下：

式（1）中i是当前节点第i个一跳邻居节点，邻居节点的个数为m个，其中m大于等于0。在抽样阶段，MCB在锚盒当中抽取样本。虽然过滤方法和MCL相同，但无效样本的数量因为抽样区缩小而大为减少，极大地提高了定位方法的速度。虽然MCB定位方法有较大的改进，但在井下环境当中，MCB能够利用井下环境的特点进一步做改进。

4 MCL和MCB定位在井下的问题及改进算法方法

本文针对于矿井这种特定的环境条件，结合以上两种方法提出蒙特卡洛中心定位算法CMCL，充分利用Monte-Carlo方法精度高且定位方法简单的优势，去除了在井下定位当效果不明显和没有效果的部分。

4.1 MCL和MCB定位在井下的问题

在矿井当中，安全问题首当其冲。为了能减少安全事故，就需要加强人员和设备的管理。人员及设备的实时定位，为精细的实时管理成为可能。通常的全球定位设备（Global Positioning System，GPS）成本高，且在矿井里无法使用，无线传感器网络的不断发展，又为人员及设备的实时定位提供了技术支持。

无线传感器网络在煤矿井下的定位是通过在巷道中布放已知自身位置的节点（锚节点，anchor node），在人员和设备上配带上未知当前位置的节点（未知节点，unknown node），当未知节点在布有锚节点的巷道里时，通过锚节点的位置来计算出自身的位置，并将位置数据实时传给管理中心从而实现矿井中人员和设备的实时定位跟踪。矿井环境下的无传感器网络节点定位问题是无线传感器网络在矿井环境中应用需要解决的关键技术问题，为矿井安全生产提供技术支持，为无线传感器网络的定位技术提供理论验证。矿井巷道狭长，一般巷道的宽度远远小于巷道的长度，巷道的宽度一般为2～10 m，如神华宁煤集团石炭井二矿21053工作面回风巷道全长692 m，宽度3 m[18]。锚节点在巷道当中均匀部署，固定在矿井巷道的一侧。人员及设备上可配带未知节点，当人员或设备在巷道当中移动时，通过对人员（设备）所携带未知节点的定位，实现对人员的实时定位及跟踪。传感器网络定位算法与应用环境极为相关，每种定位算法都有各自的特点和应用范围，没有哪种算法能够保证在各种条件下都是最好的[19]，同一种的定位算法在不同应用环境下其定位性能相差可能会很大。因此，需结合应用实际情况进行无线传感器网络定位算法的设计。

在矿井环境条件当中，MCL和MCB定位方法计算量都较大，不利于节点在井下长期使用，且定位过程相对复杂。可以充分利用矿井巷道狭长的特点，将抽样区域都建立在一跳邻居锚节点的信号重叠区中，这样所有样本都将是合格的样本，就可以省去耗时的过滤部分。其中，MCL和MCB未知节点移动模型都是随机移动模型，节点可能会向各个方向移动，文献[20]是根据节点前几个点的位置预测节点的运动来定位，而矿井巷道只有两个方向，节点只能沿两个方向中的一个方向移动，这样随机沿两个方向进行定位比MCL、MCB和文献[20]定位方法更简单。每种基于MCL的定位算法取得节点位置都需要先抽样，然后过滤掉样本坐标不在锚节点信号重叠覆盖区的点，再看是否有足够了的样本点，如果样本点不够则重复抽样并扩大抽样区域，最后再根据样本点的权值算出节点的位置。这些方法具体到矿井当中单个节点的计算量有点大，不利于节点的长期使用。巷道采样区域本身很小，本文省去了对样本过滤这一步，在实际应用当中可能会更有效。

4.2 算法提出

MCB定位算法比MCL定位精度更好时间更短，得益于MCB限定了采样区域，有着比MCL更小的采样区，这样MCB定位算法的采样和过滤的效率更高，之所以还要过滤采样点是因为并不能完全保证所有的样本都能落在信号的重叠区当中。MCB定位方法使用锚盒将它的抽样效率变得更高，那么能不能进一步提高抽样的效率，让所抽取的样本都是合格的样本，进而能够省去过滤的部分。本文就是本着这样的思考，结合井下的坏境条件进一步的抽样区域缩小，使得在这个区域当中抽取的样本都是合格的样本，就可以完全省去过滤和重复抽样，定位的效率会大大提高。本文算法以此为出发点，作如下分析。

如图1在矿井当中，巷道狭长，巷道宽度为w；A、B两点为锚节点，节点通讯半径为r，锚节点相隔d布放在巷道的一侧，d小于2r即任意两个锚节点间通讯半径有重叠；将锚盒宽度限定为巷道宽度，长度也限定为巷道宽度。当节点在这两个锚节间移动，根据位置不同会在三个位置上形成锚盒（以当前节点的一跳邻居节点为参照，计算出这些节点的中心，以中心坐标为原点上下左右各向外加巷道的宽度的一半，形成锚盒的边界），即在锚节点附近时会以锚节点为中心形成锚盒，在靠近两个锚节点中心点时会以中心点坐标为中心形成一个锚盒。如果把能形成锚盒的区域称为锚盒区的话，当未知节点位于两个锚盒区的中间时误差最大，这个未知节点最大可能误差为d/4+w/2。

例如r=50 m，宽w=5 m，巷道内每隔d=25 m布放一个锚节点，100 m内可以布放4个锚节点，未知节点在这100 m内移动时会在七个位置上形成锚盒，这样未知节点的理论最大可能误差为25/4+5/2=8.75 m，即移动节点的定位精度小于等于8.75 m，在实际定位中会比这个小。

误差公式为：锚节点的间隔d/4+巷道宽度/2。

锚盒个数：（巷道长度/锚节点的间隔+1）+（巷道长度/锚节点的间隔+1）/2。

图1 锚盒个数示意图

通过分析可知，100 m内通讯半径为50 m时，锚节点密度为1、2、4时能形成的锚盒个数如表1。

表1 未知节点100 m内所能生成锚盒个数

形成锚盒后，在锚盒当中进行样本点的抽取，若当前邻居节点列表为空，则看上次抽样的样本点数是否为零，如果不为零，则以上次估计位置作为未知节点的位置；如果上次抽样的样本点数也是零，就说明上次未知节点通讯范围内也没有锚节点，则以区域的几何中心作为未知节点的位置。

邻居节点为空的情况只有在锚节点以相隔100 m布放于巷道一侧时会产生，即未知节点在两锚节点间的中点且在巷道的另一侧，此时未知节点离两个锚节点的距离都会超过50 m的通讯距离而收不到信号。而当锚节点以小于100 m布放时，未知节点的邻居列表中至少会有一个锚节点。

相比于MCL和MCB这个方法对采集好的样本不进行过滤，也就是说只要能生成锚盒，那么这个未知节点的坐标就能确定下来，进而加快了定位的速度，节省了运算量。

未知节点在移动中位置不停地改变，反复运行这个定位方法便能不停地取得变更的位置。考量的参照锚节点只是这个未知节点能够接受到信号的一跳邻居锚节点。

整个CMCL定位算法流程如下：

预测阶段：

（1）首先，更新邻居列表，计算出一跳邻居列表的中心坐标，如果一跳邻居中有节点与未知节点的距离小于四分之一的锚节点间距，以这个邻居节点的坐标为中心坐标，以中心坐标为原点左右各向外加巷道的宽度的一半，以巷道的宽度为锚盒的宽，形成锚盒的边界。

（2）从锚盒当中抽取出50个样本点。

更新阶段：

（3）如果当前样本点数不为零，执行（6）；点数为0则看前次样本数是否为0如果是执行（4）否则执行（5）。

（4）取区域的几何中心作为未知节点的当前位置；执行（1）。

（5）以上次估计位置作为未知节点的当前位置；执行（1）。

（6）取所有样本点的几何中心作为未知节点的当前位置。执行（1）。

图2中A、B和C都是锚节点，按50 m相隔布放在巷道的一侧，节点的通讯半径为50 m，其中，生成锚盒过程如下（如图2）：

（1）利用当前未知节点的一跳领居锚节点（指当前节点通讯范围内的锚节点，图2中未知节点的一跳邻居锚节点有A和B）计算出中这些锚节点的几何中心。

（2）以几何中心为中点左右各加巷道宽度的一半，上下以巷道宽度为边界；几何中心的坐标为（centX，centY）：

式（2）中n为当前未知节点一跳邻居锚节点的个数，第i个（i从1到n）锚节点的x坐标是Axi，y坐标是Ayi。

式（3）中tunnelwidth是当前巷道的宽度。

图2 锚盒计算示意图

图3 锚节点按100 m间隔时对比图

5 实验验证

为了对CMCL定位算法的性能进行评价，采用了文献[16]中开发的用于基于Monte Carlo方法的传感器网络定位算法仿真工具MCL-simulator对CMCL算法进行了仿真，并在相同的条件下与MCL和MCB算法的性能进行了比较。

实验模拟矿井环境，巷道的长度设为1 000 m，巷道的宽度分别设为3 m、5 m和10 m。锚节点固定在巷道的一边，在巷道中分别相隔10 m、20 m、25 m、40 m、50 m和100 m布设。未知节点在巷道中随机沿一个方向移动，当未知节点到达巷道的两个端点时，改变方向向另一个方向移动，移动的速度从0/每个时间片开始到2倍的通讯半径/每个时间片。每个节点的通讯半径为50 m，MCL、MCB和CMCL的采样数都设定为50个样本点。

不同锚节点密度时定位精度比较，以巷道为1 000 m长5 m宽，锚节点间隔分别为100 m、50 m、25 m和10 m，结果如图3～6。

图4 锚节点按50 m间隔时对比图

图5 锚节点按25 m间隔时对比图

图6 锚节点按10 m间隔时对比图

图7 巷道宽度3 m时对比图

图8 巷道宽度5 m时对比图

图9 巷道宽度10 m时对比图

图10 算法运行时间对比图

从上边锚节点间隔分别为100 m、50 m、25 m和10 m时的对比图看节点移动速度从0 m到100 m的精度变化，CMCL的定位精度是最好的，可以看到在100 m时的定位精度大约是在50%左右，50 m时精度在30%以下，25 m时精度完全在17%以下，10米在10%以下。

不同巷道宽度条件下定位精度比较，巷道长度固定为1 000 m，巷道宽度分别设置为3 m、5 m和10 m，锚节点间隔固定为25 m。

如图7～9所示，在巷道宽度为3 m、5 m、10 m条件下，精度仍然是CMCL精度最好。可以看到在覆盖面积远远大于巷道宽度，随着巷道宽度的变小，所有的定位方法的定位精度都有所提高精度都在10%左右。

定位时间比较，比较三种定位算法在巷道长度固定为1 000 m，巷道宽度设置为5 m，锚节点间隔固定为25 m，未知节点数为10，30，50时的定位时间。

从图10中可以看出，红色为MCL的定位运行时间，绿色为MCB的定位运行时间，蓝色为CMCL的定位运行时间。从中可以看出，CMCL远远小于另外两种定位方法。MCL从一个一跳邻居锚节点的通讯区域当中抽取样本，每抽取一个样本都要用一跳和二跳锚节点来对这个样本进行过滤，最差情况下抽取20 000次，并且不能保证取到足够的样本，这就使MCL定位较慢。MCB对抽样的区域进行了缩小，这使得它的抽样效率更高，它有着MCL同样的过滤方式，它比MCL快了不少，但是比CMCL还是要慢很多。CMCL抽样是从固定大小的区域中抽取样本，并且抽取的样本不进行过滤，这使得CMCL的抽样只要运行一遍，计算量远远小于上两种定位方法。这样更简单，且精度更高，更能适应于低功耗的要求。

6 结论及展望

本文算法实现步骤简洁，计算量少，很适合于移植到传感器节点芯片当中。从实验结果看，本文算法在模拟巷道环境当中较MCL和MCB定位精度高、定位稳定、计算时间较短、不受未知节点密度的影响。CMCL定位方法更简单运算量少，且精度更高，更适合于在井下环境中应用。

[1]Girod L，Bychkovskiy V，Elson J，et al.Locating tiny sensors in time and space：a case study[C]//IEEE International Conference on Computer Design：VLSI in Computers and Pocessors，2002：214-219.

[2]Harter A，Hopper A，Steggles P，et al.The anatomy of a contextaware application[C]//MobiCom’99，1999：59-68.

[3]Girod L，Estrin D.Robust range estimation using acoustic and multimodalsensing[C]//IEEE/RSJ InternationalConference on Intelligent Robots and Systems，2001：1312-1320.

[4]Priyantha N B，Miu A K L，Balakrishnan H，et al.The cricket compass for context-aware mobile applications[C]//Mobi-Com’01，2001：1-14.

[5]Niculescu D，Nath B.Ad hoc Positioning System（APS）using AOA[C]//INFOCOM，2003：1734-1743.

[6]Niculescu D，Nath B.Ad hoc Positioning System（APS）[C]// GLOBECOM’01，2001：2926-2931.

[7]Niculescu D，Nath B.DV based positioning in ad hoc networks[J].Telecommunication Systems，2003，22：267-280.

[8]Doherty L.Algorithmsforposition and datarecovery in wireless sensornetworks[M].Berkeley，CA：University of California Press，2000.

[9]Doherty L，El Ghaoui L.Convex position estimation in wireless sensor networks[C]//INFOCOM，2001：1655-1663.

[10]Shang Y，Ruml W，Zhang Y，et al.Localization from mere connectivity[C]//MobiHoc’03，2003：201-212.

[11]胡圣波，郑志平.一种井下RFID定位系统的读卡器防碰撞算法[J].工矿自动化，2006（2）：4-7.

[12]傅智河.基于RFID的矿山井下人员定位系统设计[J].龙岩学院学报，2007，25（6）：50-52.

[13]任晓强，贾瑞生.井下RFID定位系统的实用技术研究[J].山东轻工业学院学报，2008，22（3）：84-85.

[14]乔钢柱，曾建潮.信标节点链式部署的井下无线传感器网络定位算法[J].煤炭学报，2010（7）.

[15]Li M，Liu Y.Underground structure monitoring with wireless sensor networks[C]//IPSN，2007：69-78.

[16]Hu L，Evans D.Localization for mobile sensor networks[C]// Proceedings of the 10th Annual International Conference on Mobile Computing and Networking，2004：45-57.

[17]Baggio A，Langendoen K.Monte Carlo localization for mobile wireless sensor networks[J].Ad Hoc Networks，2008，6（5）：718-733.

[18]奚家米，毛久海，杨更社，等.沿空掘巷合理煤柱宽度综合分析与确定[J].煤田地质与勘探，2008，36（4）：42-45.

[19]Wang F B，Shi L，Ren F Y.Self-localization systems and algorithms for wireless sensor networks[J].Chinese Journal of Software，2005，16（5）：857-868.

[20]汪炀，黄刘生，吴俊敏，等.一种基于Monte Carlo的移动传感网络精确定位算法[J].小型微型计算机系统，2008，29（9）.

ZHAO Ming,QIAO Gangzhu,JIE Jing

Laboratory of Complex System and Computational Intelligence,Taiyuan University of Science and Technology,Taiyuan 030024,China

For most wireless sensor network applications,position data is one of key information.How to make the positioning algorithm more stable and robust,more accurate,more efficient with the minimum cost is a direction which wireless sensor network localization algorithm to pursue.Applications of wireless sensor network are attached great relevence to application.It takes tunnel environment as the background,designs an improved localization algorithm based on the Monte-Carlo localization（Center Monte-Carlo Location,CMCL）,CMCL method is simple and uses bitty computation.Compared and analyzed the CMCL and Monte-Carlo localization though the experiment of simulation,the result reveals that the CMCL has strong stability and better accuracy.

wireless sensor network;Monte-Carlo;localization algorithm

在无线传感器网络应用当中，位置数据向来是关键信息之一。怎样用最小的代价，使得定位算法更加稳定健壮、更精确、更高效，是目前无线传感网定位算法追求的一个方向。因为无线传感网络有着很强的应用相关性，Monte-Carlo中心定位算法以井下环境为背景，设计的一种基于Monte-Carlo算法的改进的定位算法，定位方法简单，定位计算量小。最后通过实验将该算法和Monte-Carlo算法进行了仿真，结果显示在井下环境条件下，该算法有很强的稳定性和更好的精度。

无线传感网；Monte-Carlo；定位算法

A

TP393

10.3778/j.issn.1002-8331.1202-0217

ZHAO Ming,QIAO Gangzhu,JIE Jing.Monte-Carlo method based localization algorithm for underground wireless sensor network.Computer Engineering and Applications,2013,49（23）：81-85.

国家自然科学基金（No.60975074）。

赵明（1979—），男，硕士研究生，主研方向：无线传感器网络；乔钢柱，副教授；介婧，博士后，副教授。E-mail：zmovocs@gmail.com

2012-02-13

2012-07-25

1002-8331（2013）23-0081-05

◎数据库、数据挖掘、机器学习◎