一种优化的移动无线传感器网络三维定位算法研究

王照宇

【摘 要】在许多应用中，无线传感器网络中节点的位置信息往往决定着网络的功能和性能。为了解决移动无线传感器网络三维定位问题，提出了一种优化的移动无线传感器网络定位算法。该算法在三维空间中利用在监测区域内随机分布的固定锚节点，移动未知节点通过判断是否是第一次收到或第一次没有收到锚节点的位置信息，同时结合前一定位时刻移动未知节点的位置及距移动未知节点一跳和两跳的固定锚节点的位置，缩小移动未知节点可能所在的区域范围，进而减小节点的定位误差。通过计算机仿真发现与扩展到三维空间的蒙特卡洛（MCL）定位算法相比，本算法具有较高的定位精度。

【关键词】无线通信技术 定位 三维空间 无线传感器网络

Research on an Optimized Three-Dimensional Localization Algorithm in

Mobile Wireless Sensor Network

[Abstract] In many applications， the function and performance of wireless sensor network （WSN） depend on the location information of sensor nodes. In order to deal with the three-dimensional localization in WSN， an optimized localization algorithm for WSN was proposed in this paper. In the proposed algorithm， fixed anchor nodes are deployed randomly in the monitoring zone of the three-dimensional space. The mobile sensor node judges whether it is the first time that it receives or not receives the position information from anchor nodes. It also utilizes the position of itself in the previous localization time and the position information of anchor nodes that one hop and two hops apart from itself to reduce the location error. Simulation results show that， compared with the three-dimensional Monte Carlo localization （MCL） localization algorithm， the proposed localization algorithm has higher localization accuracy.

[Key words]wireless communication localization three-dimensional space WSN

1 引言

随着无线通信和硬件技术的发展，无线传感器网络在现实中的应用范围越来越广。在环境监测、矿井安全、农业生产、疾病监护、车辆交通等许多领域都能找到它的身影[1-2]。在一些应用中，节点是大量随机部署在监测区域内并实时移动的，节点的地理位置信息无法获得，然而许多时候只有明确了传感器节点自身的位置，才能为用户提供有用的监测数据，为路由和拓扑结构的规划提供依据，节点的位置信息是许多研究的基础[3]。

早期的无线传感器网络定位算法主要针对二维平面空间的静态网络，节点位置固定不变，节点坐标也只有X和Y两个维度，没有考虑到节点的移动性和三维空间的情况。然而在许多传感器应用领域，例如野生动物追踪、洋流监测、车载网等，传感器节点的位置是随时间变化的，对节点位置的测量也要提供三维坐标。因此对移动传感器网络三维定位算法的研究非常重要[4-5]。

在移动传感器网络中比较常见的定位方法是为一部分固定节点装配GPS全球定位系统，称之为固定锚节点，其余的移动未知节点利用这些锚节点的位置信息来估算自身的位置。例如，有文献提出在监测区域内随机部署一定数量的固定锚节点，基于蒙特卡罗算法，移动节点首先根据上一时刻的位置对当前自身的位置进行预测，估算移动节点可能所在的位置区域当作样本，然后利用距该移动节点一跳和两跳范围内的固定锚节点的位置信息对样本进行过滤，筛选出满足锚节点限定条件的样本值，再进行交叉操作和变异操作，对采样进行优化，最后对筛选出的样本坐标取平均，记作移动节点当前的位置坐标[6]。还有文献提出移动节点根据自身的移动速度，生成相对距离约束，然后利用侦听到的固定锚节点的位置信息和信息传输范围来估算移动节点的位置，避免了蒙特卡罗算法中反复采样的问题[7]。

在现有的移动传感器网络定位技术中，移动节点的采样区域较大，节点的定位精度较低，并且主要针对二维平面空间，因此本文综合考虑这些问题，提出了一种优化的移动传感器网络三维定位算法。本算法把传统的移动传感器网络定位算法扩展到了三维空间中，利用移动未知节点是否是第一次收到和第一次没有收到固定锚节点的位置信息，并综合两跳锚节点的位置信息，提高移动未知节点的定位精度。经过仿真发现与扩展到三维空间的蒙特卡罗定位算法相比，本算法可以有效提高移動未知节点的三维空间定位精度。

2 蒙特卡罗定位算法

蒙特卡罗定位算法在定位初始化阶段，系统首先从网络区域内随机选择N个样本点形成初始的样本集合L0={l10，l20，…，lN0}，然后重复预测阶段和过滤阶段实现移动未知节点的定位。在预测阶段，移动未知节点根据节点的最大移动速度预测节点的位置，假设移动未知节点自身的实时移动速度未知，节点最大移动速率不超过Vmax。设在t-1时刻节点的位置是，则在t时刻节点的位置位于以为圆心，Vmax为半径的圆内。其中Vmax越大，则采样区域就越大，节点可能所在的位置区域也随之增大。该算法通过在圆内反复采样，便可由t-1时刻的样本集合Lt-1得到t时刻的样本集合Lt。在过滤阶段，该算法利用距移动未知节点一跳和两跳的固定锚节点的位置信息把不符合条件的样本过滤掉。假设R是节点的通信半径，则移动未知节点的样本值位于距一跳锚节点距离为R的圆内，位于距两跳锚节点距离为R和2R的圆环内。当过滤阶段结束后，由于移动未知节点的一部分定位样本被过滤掉，采集到的样本数可能小于系统阈值，该算法将重复预测和过滤过程，直到移动未知节点采集到足够的样本值，最后计算这些样本坐标的平均值作为移动未知节点当前的位置坐标[8]。

3 优化的移动无线传感器网络三维定位

算法

在传统的基于蒙特卡罗算法的移动传感器网络节点定位中，移动未知节点可能所在的位置区域较大，节点的定位精度较低，并且目前的算法都是针对二维平面区域，在三维空间中无法应用。本文所提出的一种优化的移动传感器网络三维定位算法充分利用移动未知节点是否是第一次收到和第一次沒有收到固定锚节点的位置信息，满足高精度定位的要求。

在该算法中无线传感器网络由在监测区域内部署的固定锚节点和移动未知节点组成。固定锚节点存储有自身及一跳范围内的邻居锚节点的位置信息，其余的移动未知节点在网络内随机移动，固定锚节点在每个定位时刻广播其存储的锚节点位置信息。当移动未知节点进入到某个固定锚节点的通信区域内时，则认为移动未知节点可以接收到该锚节点广播的位置信息，移动未知节点基于此信息来计算自身的实时坐标。

3.1 初始定位区域的确定

当固定锚节点在监测区域内部署完毕后，移动未知节点开始在网络内自由移动，移动速度不固定。假设所有节点的通信距离为R，移动未知节点最大移动速度为Vmax，系统间隔时间T对移动未知节点进行一次定位，则移动未知节点在每个定位间隔内最大的移动距离为Smax=T*Vmax。为了保证本算法的有效性，需要限定系统的定位间隔，使Smax

假设移动未知节点在上一定位时刻的位置为M，因为在每个定位间隔内移动未知节点最大移动距离为Smax，则在当前定位时刻，移动未知节点N位于以点M为球心，以Smax为半径的球内，如图1所示：

3.2 定位区域的筛选及确定

固定锚节点在每个定位时刻广播其自身的位置信息及距该锚节点一跳范围内的邻居锚节点的位置信息和节点ID号。移动未知节点在收到固定锚节点广播的信息后，记录该固定锚节点和其邻居锚节点的信息，这些锚节点都是该移动未知节点的一跳或两跳锚节点。如果某锚节点仅是移动未知节点的两跳锚节点，则把该锚节点记为两跳锚节点，否则记为一跳锚节点。然后移动未知节点判断当前收到的一跳锚节点ID号与前一定位时刻收到的一跳锚节点ID号是否存在不相同的ID号。如果存在不同的ID号，则把当前定位时刻新侦听到的一跳锚节点记作第一次侦听到的一跳锚节点，前一定位时刻侦听到而在当前定位时刻没有侦听到的一跳锚节点记作第一次没有侦听到的一跳锚节点。

在当前定位时刻，如果移动未知节点不是第一次收到或第一次没有收到某一跳锚节点广播的信息，则移动未知节点N位于以该一跳锚节点A为球心，R为半径的球内。同时移动未知节点N还位于以距其两跳距离的固定锚节点B为球心，半径为R和2R的球壳内，如图2所示：

如果移动未知节点在当前定位时刻第一次侦听到某一跳锚节点广播的信息，则移动未知节点距该一跳锚节点最近的距离为R-Smax（上一定位时刻移动未知节点刚好位于该锚节点的通信区域外），最远的距离为R（当前定位时刻移动未知节点刚好位于该锚节点的通信区域内），移动未知节点N位于以该固定锚节点C为球心，半径为R-Smax和R的球壳内。如果移动未知节点在当前定位时刻第一次没有侦听到某一跳锚节点广播的信息，则移动未知节点距该固定锚节点最近的距离为R（当前定位时刻移动未知节点刚好位于该锚节点通信区域外），最远的距离为R+Smax（上一定位时刻移动未知节点刚好位于该锚节点的通信区域内），移动未知节点N位于以该固定锚节点D为球心，半径为R和R+Smax的球壳内，如图3所示。

移动未知节点在综合考虑以上限定因素后，取这些限定区域的交集区域作为移动未知节点可能所在的区域范围，采用网格扫描法[9]计算该交集区域中心的坐标，记作当前定位时刻移动未知节点的位置坐标。

如果上一定位时刻移动未知节点的定位误差较大，则在当前定位时刻移动未知节点基于侦听到的固定锚节点的限定区域和基于上一定位时刻位置的限定区域可能没有交集，无法计算移动未知节点的位置坐标。因此当以上限定区域没有交集区域时，则首先利用距移动未知节点一跳和两跳的固定锚节点的坐标计算移动未知节点可能所在的区域范围，然后计算该区域中心的坐标作为移动未知节点当前定位时刻的位置坐标。如果移动未知节点在当前定位时刻没有侦听到固定锚节点，则把移动未知节点上一定位时刻的位置坐标记作当前定位时刻的位置坐标。

4 仿真结果和分析

因为MCL定位算法是一种二维空间定位算法，而本文提出的一种优化的移动传感器网络三维定位算法针对三维空间，所以本文将MCL定位算法扩展到三维空间中，增加定位维度，通过改变不同的系统参数，在移动未知节点定位精度方面和本算法进行对比。

在仿真模型中假设节点部署区域为100 m×100 m

×100 m，固定锚节点和移动未知节点的通信半径均为R，固定锚节点个数为m个，移动未知节点个数为n个，则固定锚节点密度为Ad=m/（n+m），所有节点随机部署在网络区域内。移动未知节点采用随机步行移动模型[10]，在网络区域内随机移动，在两个定位时刻之间，移动未知节点的移动速度在[0， Vmax]范围内随机变化，移动方向随机选择，在每个定位间隔内的最大移动距离小于R。在仿真结果分析中为了方便起见，将Smax和平均定位误差均用R表示，例如当节点通信半径R=30 m，Smax=9 m时，则将Smax用0.3R表示。仿真中的移动未知节点的定位误差为所有移动未知节点定位误差的平均值。

当改变移动未知节点的最大移动距离时，取所有节点的总数为300个，固定锚节点密度为10%，本算法和扩展MCL定位算法的移动未知节点平均定位误差如图4所示。从图4可以看出当最大移动距离为0.7R时，扩展MCL定位算法的平均定位误差为0.529R，本算法的平均定位误差为0.496R，比扩展MCL定位算法减少了6.37%。

当改变固定锚节点密度时，取所有节点的总数为300个，移动未知节点在每个定位间隔内最大移动距离为0.4R，本算法和扩展MCL定位算法的移动未知节点平均定位误差如图5所示。从图5可以看出当固定锚节点数量较少时，在本算法中每个定位时刻第一次收到和第一次没有收到的固定锚节点数量很小，定位误差和扩展MCL定位算法相比优势不明显。随着固定锚节点数量的增加，本算法的定位误差明显减小，当固定锚节点密度为20%时，本算法的定位误差为0.171R，比扩展MCL定位算法减少了11.6%。

5 结束语

本文针对移动传感器网络MCL定位算法中节点定位精度较低和定位范围为二维空间的问题，提出了一种优化的移动传感器网络三维定位算法，引入了移动未知节点对第一次收到和第一次没有收到固定一跳锚节点信息的判断，减小了未知节点的所在区域范围。在与扩展MCL定位算法的仿真结果对比中，本文提出的定位算法在定位精度方面要优于扩展MCL定位算法，尤其当移动未知节点在每个定位间隔内的最大移动距离较小时，定位精度的优势体现的更为明显。

参考文献：

[1] Akyildiz I F， Su W， Sankarasubramaniam Y. A Survey on Sensor Networks[J]. IEEE Communications Magazine， 2002，40（8）： 535-539.

[2] 周正. 无线传感器网络的节点自定位技术[J]. 中兴通讯技术， 2005，11（4）： 51-56.

[3] V Potdar， A Sharif， E Chang. Wireless Sensor Networks： A Survey[A]. International Conference on Advanced Information Networking and Applications Workshops[C]. 2009： 393-422.

[4] P Amitangshu. Localization Algorithms in Wireless Sensor Networks Current Approaches and Future Challenges[J]. Network Protocols and Algorithms， 2010（1）： 45-74.

[5] C H Ou， K F Su. Sensor Position Determination with Flying Anchors in Three-Dimensional Wireless Sensor Networks[J]. IEEE Transactions on Mobile Computing， 2008（9）： 1084-1097.

[6] 宋琛，罗娟. 无线传感器网络移动节点的定位算法[J]. 计算机工程， 2008，34（20）： 107-108.

[7] 黄梅根，常新峰. 一种基于蒙特卡罗法的无线传感器网络移动节点定位算法研究[J]. 传感技术学报， 2010，23（4）： 562-566.

[8] Hu L， Evans D. Localization for Mobile Sensor Networks[A]. In Proceedings of the10th Annual International Conference on Mobile Computing and Networking[C]. 2004： 45-47.

[9] 朱红霞，陈曙. 一种新的基于非测距的无线传感器网络三维定位算法[J]. 傳感技术学报， 2009，22（11）： 1655-1660.

[10] Davies V A， Vanessa C， Davies A. Evaluating Mobility Models within an Ad Hoc Network[D]. Colorado School of Mines， 2000.