无线传感器网络(WSN)成为当今生活诸多领域的前沿技术，如栖息地监测、卫生保健[1]、精准农业[2]、动物追踪、森林火灾探测、早期滑坡探测和地震探测等．WSN是由多个传感器节点组成的多跳自组织无线通信系统[3]，其中传感器节点的位置信息至关重要．为了确定传感器节点的位置，人们提出了许多定位算法，包括质心定位算法、DV-HOP定位算法[4]及其改进算法[5-6]．这些算法是针对静态无线传感器网络的方案，不考虑传感器节点的移动性．然而，在许多应用场景下，传感器节点是移动的，例如野生动物追踪[7]和地底矿工定位[8]等．在以上各种应用的需求下，移动WSN节点定位变得越来越重要．一些移动WSN节点定位的算法使用静态节点定位算法周期性计算，但此类算法没有利用节点的移动性并且计算量大，通信成本过高．文献[9]提出的蒙特卡罗节点定位算法(MCL)其核心思想是利用N个离散样本估计后验概率，利用重要性抽样迭代更新．该算法充分利用节点的移动性来提高精度，在有限的存储空间下能够取得较好的定位效果，且在一定范围内定位精度会随着速度的增大而提高．但此定位算法中存在过多依赖锚节点数量和采样效率低下的问题．为解决上述问题，学者从不同角度对蒙特卡罗节点定位算法做出了改进．文献[10]提出蒙特卡罗盒子定位算法(MCB)，引入了锚盒和样本盒来缩小采样区域；文献[11]提出的MSL*算法引入一跳和两跳普通节点与锚节点共同定位；文献[12]将蒙特卡罗节点定位算法与RSSI相结合；文献[13]提出基于时序的蒙特卡罗节点定位，该算法利用一跳范围内锚节点反馈信号的顺序构成采样区域；文献[14]提出基于马氏链的蒙特卡罗节点定位算法，该算法在预测过滤的过程中使用马氏链计算粒子的权重；文献[15]提出了一种基于牛顿插值的蒙特卡罗移动节点定位算法；文献[16]提出小波变换预测移动节点定位算法，利用小波变换的方法通过历史轨迹来预测节点位置；文献[17]将差分进化算法与蒙特卡罗节点定位算法相结合．上述改进算法仍存在以下问题：节点的定位精度过于依赖锚节点，在锚节点数量较少的情况下定位结果不理想；高的定位精度是以大量的通信能耗为基础的，不符合WSN的低成本、低能耗原则．为此，本研究提出基于临时锚节点的改进蒙特卡罗节点定位算法．1 基于RSSI的蒙特卡罗节点定位算法(RMCL)MCL算法利用运动信息和上一时刻的位置信息来构造采样区域，而RMCL算法则采用运动信息、上一时刻的位置信息和未知节点与锚节点之间的距离来约束采样区域．该算法利用RSSI的衰减程度来估计未知节点与一跳和两跳锚节点之间的距离．假设：i为未知节点编号；j为未知节点一跳和两跳范围内锚节点编号；xr和yr分别为部署区域的最大x和y坐标；Ati为t时刻未知节点i的采样区域；Lti为t时刻未知节点i的样本集合；N为常数，表示在一个集合中要保持的最大样本数；g为在样本集合中第g个样本；xmin，ymin，xmax，ymax分别为在一个采样区域中x，y坐标的最小值和最大值；Oti为t时刻未知节点i的锚节点集合；ltg为未知节点i在t时刻第g个样本；(xtg，ytg)为第g个样本的坐标；P(Otiltg)为样本ltg在锚点Oti的观测区域中的概率；Lt为过滤后的样本集合．使用R暂存样本信息，Rf为过滤后的样本信息．算法过程如下算法1 基于RSSI的蒙特卡罗节点定位初始化 最初没有上一时刻的样本集合，所有节点的采样区域均设置为节点的部署区域A0i={(x,y)|0xxr,0yyr}．步骤1 每一个未知节点i都利用锚节点信息构建采样区域Ati={(xmin,xmax);(ymin,ymax)}．步骤2 从采样区域随机抽取新的样本，用新的观测值进行过滤．当样本数量小于N时，R={ltg|ltg=(xtg,ytg)}．使用锚节点信息过滤样本：Rf=(ltg∈R)⋂(p(Oti|ltg))0；Lti=Lt⋃Rf．步骤3 计算出节点位置为(∑ltg)/N．构建采样区域(xj,yj)为锚节点j的坐标，rij为未知节点i和锚节点j之间的距离．则距离盒子为：xmin=max(xj-rij);xmax=min(xj+rij);ymin=max(yj-rij);ymax=min(yj+rij). (1)在得到距离盒子之后，将距离盒子与以未知节点上一时刻的位置坐标为圆心、以节点运动的最大速度vmax的值为半径的矩形重合部分作为采样区域．xt-1i，yt-1i为未知节点i在t-1时刻的坐标．建立采样区域：xmin=max(xmin,xt-1i-vmax);xmax=min(xmax,xt-1i+vmax);ymin=max(ymin,yt-1i-vmax);ymax=min(ymax,yt-1i+vmax). (2)然后在采样区域中随机采取样本，对其进行过滤，即从样本集中移除不可能的样本．假设：r为通信距离；St1为t时刻一跳范围内锚节点的集合；Tt为t时刻两跳锚节点的集合；d(ltg,S)为参考节点S和样本ltg之间的汉明距离．将所得样本与一跳锚节点之间距离大于r、与两跳锚节点之间距离大于2r的样本剔除，即P(Oti|ltg)=1    (s∈St1,d(ltg,S)≤r);1    (s∈Tt,rd(ltg,S)≤2r);0    (其他).如前所述，基于RSSI的蒙特卡罗节点定位算法的过程主要包括采样区域的构造、采样和过滤．算法首先基于未知节点和锚点的距离估计来构造采样区域，从中抽取样本；然后对样本进行过滤；最后用这些过滤样本的平均值来估计位置．2 基于临时锚节点的蒙特卡罗移动节点定位算法2.1　算法设计基于临时锚节点的改进蒙特卡罗节点定位算法(TANRMCL)与RMCL算法最大的不同就是选择普通节点作为临时锚节点，并与锚节点共同作为未知节点的参考节点．TANRMCL算法提出新的重采样方法，避免算法陷入采样过滤的死循环．在锚节点数量比较少的情况下，利用临时锚节点和锚节点组合定位，来提升定位精度．算法2 基于临时锚节点的改进蒙特卡罗节点定位初始化 最初没有上一时刻的样本集合Lt-1和上一时刻的位置信息，仅使用锚节点构造采样区域A0i={(x,y)|0xxr,0yyr}．步骤1 利用锚节点和临时锚节点构建采样区域Ati={(xmin,xmax);(ymin,ymax)}．步骤2 从构建的采样区域中采样．当样本集Lt中的样本数量小于N时，采集新样本R={ltg|ltg=(xtg,ytg)}．步骤3 利用Ot值过滤不符合条件的样本：Rf=(ltg∈R)⋂(p(Oti|ltg)0);Lti=Lt⋃Rf．步骤4 重采样当采样次数达到最大值且样本集Lt中的样本数量小于N时，进行重采样操作．步骤5 计算出节点位置为(∑ltg)/N．2.2　算法详细说明2.2.1　临时锚节点的选择临时锚节点为未知节点一跳范围内的普通节点．这些普通节点将自身上一时刻的位置作为自身的位置信息，和锚节点有一样的参考价值．假设：rik为未知节点i与可通信范围普通节点k之间的距离；ns为一跳范围内锚节点的数量．根据锚节点的数量决定临时锚节点的数量；根据普通节点与未知节点的距离，选择一个或几个距离未知节点最近的普通节点作为临时锚节点．当未知节点一跳范围内锚节点的数量ns≥3时，无须选择临时锚节点；当ns=2时，最多选择一个一跳范围内距离未知节点最近的普通节点k作为临时锚节点进行定位；当ns=1时，最多选择两个一跳范围内距离未知节点最近的普通节点k作为临时锚节点进行定位；当ns=0时，最多选择三个一跳范围内距离未知节点最近的普通节点k作为临时锚节点进行定位．图1为当ns=2时临时锚节点的选择．10.13245/j.hust.210215.F001图1ns=2时临时锚节点的选择2.2.2　采样区域构建假设：(xj,yj)为锚节点j的坐标；(xk,yk)为临时锚节点k的坐标；rij为未知节点i和锚节点j之间的距离；rik为未知节点i与临时锚节点k之间的距离．使用锚节点和临时锚节点构造距离盒子，具体方法如下：若锚节点的数量ns≥3，则完全使用锚节点观测值进行参考定位，不选择可使用的临时锚节点，距离盒子为式(1)．若锚节点的数量ns3，则要选择合适的临时锚节点和锚节点一同作为参考节点，距离盒子为：xmin=max(xmin,xk-r);ikxmax=min(xmax,xk+rik);ymin=max(ymin,yk-rik);ymax=min(ymax,yk+rik).距离盒子构造完成以后，若上一时刻的样本集为空，则距离盒子为采样区域；若上一时刻的样本集不为空，则采样区域为在距离盒子的基础上加入节点的运动信息，即式(2)．2.2.3　修正半径临时锚节点的坐标为该节点上一时刻的位置坐标．若对上一时刻坐标位置信息不进行修正，则会出现比较大的误差．由于这些误差会随着算法的迭代不断累积，因此使用修正半径来减少误差的不利影响，修正半径设为节点运动的最大速度vmax的值．如图2所示，若不考虑修正半径，则会失去一部分有效的采样区域．图3为添加修正半径构建的采样区域．10.13245/j.hust.210215.F002图2无修正半径构建的采样区域10.13245/j.hust.210215.F003图3添加修正半径构建的采样区域2.2.4　过滤假设r为通信距离；St1为t时刻一跳范围内锚节点的集合；St2为t时刻一跳范围内临时锚节点的集合；dltg,S为参考节点S和样本ltg之间的汉明距离，移除与未知节点距离大于通信距离r的样本节点，具体方法为P(Otiltg)=1    (s∈St1,d(ltg,S)≤r);1    (s∈St2,d(ltg,S)≤r);0    (其他).2.2.5　重采样设nn为一跳范围内普通节点数量．在RMCL算法中，每一个样本都是经过采样和过滤所得，不但耗费较大的计算开销，还可能陷入采样过滤的死循环当中．TANRMCL算法将最大采样次数设置为2N次，若经过2N次采样依旧没有得到足够数量的样本，则使用以下方法进行重新采样：a. 随机选择两个有效样本(xo,yo),(xp,yp)，计算两个样本的平均位置坐标((xo+xp)/2,(yo+yp)/2)即为重新采样的样本坐标；b. 重复计算，直到得到足够的有效样本．2.3　算法通信开销分析RMCL算法定位时通信开销计算如下：首先锚节点广播自身的位置信息，向相邻节点发送数据包sdata(sdata中包括自身位置信息、锚节点编号和待转发节点之间的距离信息)；然后普通节点收到锚节点信息转发数据包ndata．因此RMCL算法的通信开销为nssdata+ndata．MSL*算法中普通节点和锚节点均广播自身的位置，普通节点的数据包还包含了上一时刻的样本adata，一跳范围内的普通节点转发两跳锚节点和两跳普通节点的数据信息．因此MSL*算法的通信开销为nssdata+(nn+1)(ndata+Nadata)．TANRMCL算法中一跳范围内的普通节点和锚节点均广播自身的位置信息，包括节点位置信息(普通节点为上一时刻位置信息)、节点编号和未知节点之间的距离信息．因此TANRMCL算法的通信开销为nssdata+nnndata．与RMCL算法相比，TANRMCL算法增加了通信开销，与MSL*算法相比，TANRMCL算法较大幅度地减少了算法通信开销．3 仿真实验与分析仿真实验是在Intel(R) Core(TM) i5-2450M CPU，主频1.60 GHz、1.80 GHz，8 GiB内存平台，Matlab2015b仿真环境中进行的．在仿真实验中，220个传感器节点随机部署在一个500 m×500 m的矩形区域内．传感器节点中有20个锚节点知道自己的位置信息，其他为不知道自己位置信息的未知节点．假设所有的传感器节点都具有相同的通信距离(50 m)．一个节点可以听到无线电通讯距离范围内的另一个节点，并直接与其通信．一个节点可以判断另一个节点是否在无线电通讯距离范围内，并且可以通过RSSI测量距离．为了模拟节点的可移动性，假设所有节点都遵循随机路径点模型(RWP)．RWP为移动自组织网络中常用的移动模型．移动WSN中的节点在每个时间步内且速度在0～vmax之间时可以随机改变．为了合理比较定位结果，三个对比算法采用了相同的RWP模型．在后续的时间步长中，首先本地化节点，然后根据RWP模型移动节点．3.1　定位误差本实验模拟在50个时间步内三个定位算法的定位误差变化．把定位误差定义为一个节点的真实位置与其估计位置之间的距离．节点最大移动速度的值设为0.2r(10 m/s)．仿真结果如图4所示，图中e为定位误差．10.13245/j.hust.210215.F004图4不同算法的定位误差与RMCL算法相比，TANRMCL算法在理论上定位时有更多的约束条件去构建采样区域，特别是在锚节点较少的情况下，使用临时锚节点和锚节点作为参考节点，会较大程度地缩小和精确采样区域，使得最后的位置估计更加精确．与MSL*算法相比，两个算法都使用普通节点进行定位，但是TANRMCL算法根据未知节点与锚节点、临时锚节点的距离来构建采样区域，而非节点之间的通信距离，因此缩小了采样区域，还对临时锚节点进行位置修正，使得采样区域更加准确．结合2.3节可以得出，TANRMCL算法牺牲了较小的通信开销而大幅度提高了采样效率和定位精度．图4中RMCL算法、MSL*算法和TANRMCL算法经过几个时间步长后，定位误差在最小值附近波动．可以看出：TANRMCL算法在大部分时间步长的定位误差小于其他两个定位算法．当vmax的值为0.2r时，定位误差比RMCL算法的低60%，比MSL*算法的低20%．3.2　锚节点密度对定位误差的影响锚节点密度d表示在通信范围内锚节点的个数．从图5可以看出：在锚节点密度较低的情况下，由于锚节点过少，定位困难，误差较大，随着锚节点密度的增加，RMCL算法、MSL*算法和TANRMCL算法的误差逐渐减小．但是TANRMCL算法总是比RMCL算法和MSL*算法定位误差更小．RMCL算法在定位时只依赖于锚节点，锚节点数量的减少会大大影响定位精度，而TANRMCL算法在定位时不仅依赖于锚节点，而且所选择的临时锚节点须一同定位，因此锚节点密度的变化对定位精度影响较小．当锚节点密度低时，MSL*算法和TANRMCL算法的定位精度基本相同，但当锚节点密度增加时，TANRCML算法中可用于参考定位的节点增多，定位精度迅速提升．10.13245/j.hust.210215.F005图5不同锚节点密度的定位误差3.3　未知节点的定位覆盖率从图6可以看出：TANRMCL算法的覆盖率除了定位起始点外，始终大于RMCL算法，这意味着TANRMCL算法可以比RMCL算法获得更多的定位节点．在RMCL算法中，一跳和两跳范围内若没有锚节点，则定位失败，但是在TANRMCL算法中，只要一跳范围内存在节点，就可以进行定位．因此TANRMCL算法比RMCL算法定位覆盖率高，与MSL*算法相比，付出更少的通信代价可以得到同样高的定位覆盖率．图中Pl为不同算法在t时刻的定位覆盖率．10.13245/j.hust.210215.F006图6不同算法的定位覆盖率3.4　节点最大运动速度对定位精度的影响从图7可以看出：RMCL算法和MSL*算法在最大速度vmax下的值为0.6r时获得最小误差，TANRMCL算法在最大速度vmax下的值为0.7r时获得最小误差．TANRMCL算法与RCML算法和MSL*算法相比，平均定位误差分别减少了60%和30%．10.13245/j.hust.210215.F007图7节点最大运动速度对定位精度的影响4 结语本研究首先选择临时锚节点，利用临时锚节点与锚节点一起定位其他节点，间接增加锚节点的数量；然后使用修正半径对临时锚节点进行修正，以减少误差；最后提出新的重采样方法．仿真结果表明：TANRMCL算法提升了节点的定位精度和定位覆盖率，尤其在锚节点稀疏的环境下．TANRMCL算法虽然是一种基于测距的定位算法，但是其硬件要求不高，可以满足低成本，高精度的移动WSN定位要求．由于传感器节点会处于不同的运动状态，因此下一步将对本研究算法在其他节点运动模型下进行研究．