基于双焦点离心测距的移动无线传感网定位算法

赵丽芬，申 毅，田 波，王 中

(1.铜仁学院 大数据学院，贵州 铜仁 554300；2.东南大学 信息科学与工程学院，江苏 南京 211189)

0 引 言

就移动无线传感网(mobile wireless sensor network，M-WSN)定位技术而言，可分为直接测距和间接测距两种定位方法[1-4]。直接测距方法在实践中一般利用多普勒位移来直接计算定位节点与基准节点的距离及角度，从而获取节点的定位坐标[5]。但是，直接测距方法需要频繁进行数据定位及频率测量。间接测序方法主要借助DV-Hop机制来实现定位，但也存在因频繁进行邻域迭代而出现精度不高的问题。

综合直接测距和间接测距方法的特点，当前国内外研究者提出了一系列的解决方法。如Li等[6]引入信号直测方法来改善DV-Hop算法的锚节点定位精度，特别是采取迭代模式来进一步优化待测角度，可将待定位节点坐标精度提升至1跳邻域内。但是，该方法在节点移动速度较高时，需要频繁针对节点距离进行测量，使得节点能量消耗较高。Zou等[7]提出通过设置两组正交锚节点来实时捕捉节点坐标。然而，该算法的定位过程中双源节点具有定位对称效应，定位坐标存在严重的漂移现象。Jeba等[8]通过sink节点控制来建立锚节点粒子群移动模型，使用周期递归方法来消除移动过程中的锚节点移动性过高带来的频率及坐标抖动问题。然而，该算法存在控制机制复杂所带来的能量消耗较快等难题，运行过程中稳定性较差。

为此，本文提出了一种基于双焦点离心测距机制的移动传感网高效定位算法。该算法将多跳定位拓扑链路视为弧线链路，通过优化最小跳数及定位拓扑获取定位椭圆横向半径和纵向半径并计算离心率，达到精密化圆周弧线的目的。借助椭圆纵半径跳数优化方法来设计动态测距模式，扩大定位椭圆的覆盖范围，增强对待定位节点的覆盖能力。最后，采用NS2仿真实验环境，验证了本文算法的性能。

1 网络模型概述

考虑网络节点分布区域为矩形，面积为m×nm2，区域内按随机模式来分布A个传感节点与B个锚节点，如图1所示。则网络net可用如下模型表示

net=G(Ai,Bj,E)

(1)

式中：Ai表示传感节点集，Bj表示锚节点集，E表示节点间的拓扑链接链路。

图1 传感节点分布

若第i个节点与第j个节点之间拓扑距离小于网络节点最低覆盖距离l，说明节点间可以建立数据传输链路。由于各节点在运行过程中覆盖能力可能存在差异，使得覆盖距离难以在网络中进行统一，估计各传感节点坐标时均需要依赖于式(1)所示的拓扑链接链路，若节点处于锚节点覆盖之外，则将会出现失联现象。因此，对节点进行定位过程中需要关注失联节点，若某个节点在通信过程中发现自己成为失联节点，需要使用sink节点对该节点进行能量补充，以便扩大覆盖范围，从而降低定位失效现象。

一般而言，无论直接测距算法还是间接测距算法均需要使用图1所示的锚节点进行定位，其中锚节点位置已知，待定位节点与锚节点进行数据交互，以便利用待定位节点与锚节点之间的链路估计相应的拓扑跳数，从而实现定位。

图2描述了间接测距算法的实现过程。待定位节点获取网络中锚节点信息，当待定位节点与3个及以上锚节点同时建立起传输链路。锚节点B1与锚节点B2、锚节点B3之间距离分别为10 m、20 m，相应跳数分别为3跳和6跳，因此锚节点B1可获取平均覆盖距离l1

l1=(10+20)/(3+6)=3.33 m

(2)

图2 间接测距

当待定位节点i与锚节点B1与锚节点B2、锚节点B3之间的拓扑跳数为1、2、4时，则该节点与锚节点B1与锚节点B2、锚节点B3之间的距离d(i,B1)、d(i,B2)、d(i,B3)满足

d(i,B1)=1×3.33=3.33 m

(3)

d(i,B2)=2×3.33=6.66 m

(4)

d(i,B3)=4×3.33=13.32 m

(5)

由式(2)～式(5)及图2可知，间接测距算法需要首先估计锚节点的平均覆盖距离，并利用平均覆盖距离估计各锚节点与待定位节点之间的拓扑长度。考虑到待定位节点覆盖能力与锚节点相比存在一定的差异，因此需要针对估计过程进行改进，以便提高定位准确度，修正估计过程中存在的误差。对拓扑路径进行估计时，应考虑多跳情况下路径析构过程中存在的裁弯取直现象，用弧度模型替代直线距离，从而更好匹配实际距离，提高算法的对多跳环境的适应能力。

2 本文算法设计

由上文可知，间接测距过程将锚节点与待定位节点间距离看作直线拓扑，由于传输链路实际存在一定的弧度，采用直线拓扑测距需要将链路弧度进行裁弯取直，因此定位过程存在一定的误差，使得算法定位精度不理想。为此，本文设计了基于双焦点离心测距机制的移动传感网高效定位算法(efficient positioning scheme for mobile sensor networks based on double focus centrifugal ranging algorithm)。该算法由两部分构成：①基于弧度路径析构的节点椭圆定位。通过采用弧线估测进行定位拓扑优化，结合锚节点来增加定位精度。②基于椭圆纵半径跳数优化的动态测距。主要针对移动无线传感网拓扑变动频繁的特点进一步提升椭圆覆盖范围，降低定位漂移现象，从而提高算法定位精度。

2.1 基于弧度路径析构的节点椭圆定位

由图2可知，间接测量方法需要计算最小跳数并进行距离估计，但距离估计过程均依赖直线模型，使其具有较大的定位误差。此外，传统的间接测距方法在最小跳数计算过程中也存在一定的弊端，特别是采用待定位节点与锚节点交互方式进行直接通信，会导致式(1)所示的拓扑链接链路E难以建立。因此，本文对最小跳数及距离估计过程进行优化，设计了基于弧度路径析构的椭圆定位方法。

(1)最小跳数的获取

首先，锚节点向sink节点进行数据报文发送，将与各节点间的跳数及自身ID通过sink节点进行全网广播。网络中除锚节点外的传感节点(含待定位节点)在接收到sink节点发送的数据报文后，记录锚节点的ID并将跳数加1，如图3所示。待定位节点接收到各锚节点发送的数据报文后，可获取各锚节点的ID及相应跳数，由于一定传输周期内待定位节点可能同时接收到若干个锚节点所发送的分组报文，因此可从这些分组报文中过滤出最小跳数对应的锚节点，记最小跳数Hop(min)如下

图3 最小跳数的获取

(6)

式中：Bn表示第n个锚节点，hop表示分组报文中所对应的跳数。

(2)确定椭圆定位范围

考虑到网络中待定位节点与各锚节点间拓扑链路存在多跳特性，由于待定位节点与锚节点间链路可能存在断裂现象，如图4所示。为保证链路的可用性，对链路中通信能力较强的节点进行能量补充，扩大覆盖范围，以便链路保持畅通状态如图5所示。

图4 拓扑链路图(断裂状态)

图5 拓扑链路图(覆盖范围扩大)

节点覆盖区域扩大后，显然链路整体长度与锚节点-待定位节点直线距离存在误差，如图5所示。为了精确获取待定位节点与锚节点间距离，须对链路整体长度进行优化。

首先，建立待定位节点与锚节点间的弧度路径，如图6所示，且该弧度看作是一个纵半径2x和横半径2y的定位椭圆，并按如下模型获取定位椭圆的离心率ε

(7)

据此，椭圆定位范围得以确立，如图6所示。

图6 椭圆定位

2.2 基于椭圆纵半径跳数优化的动态测距

椭圆定位范围确立后，由于椭圆存在两个焦点，因此按式(7)计算的椭圆离心率，即可按图6对椭圆覆盖范围进行精确划分。由于定位椭圆的纵半径2x和横半径2y可能存在变动，因此需要考虑到路径变化，以实现动态测距，特别是尽量缩减定位椭圆的纵半径2x，以便能够对定位拓扑进行动态化评估，以提升测距结果的精度。

(8)

式中：hop(Bi,Ci)表示待定位节点Ci与锚节点Bi间的跳数，Mj表示待定位节点Ci与锚节点Bi间的中间节点。

由式(8)可知，待定位节点Ci与锚节点Bi间链路整体长度G可由如下公式获取

G=G×hop(Bi,Ci)

(9)

随后，利用图6所示的椭圆定位方法，结合式(9)及式(7)，即可计算待定位节点Ci与锚节点Bi间的距离P

P=G/πx(1-ε2/4)

(10)

式中：ε为式(7)确定的离心率。

联立式(7)和式(10)，将待定位节点Ci与锚节点Bi间的跳数hop(Bi,Ci)替换式(7)中的2y，令自变量为x，则定位椭圆的纵半径方程如下

12πx2+πhop(Bi,Ci)2=G

(11)

式中：G为待定位节点Ci与锚节点Bi间链路整体长度。

再根据式(11)来求取x的最小值为

minx=G/2

(12)

通过式(12)获取定位椭圆的横半径x后，令(x,y)表示待定位节点的坐标，(xj,yj)表示锚节点坐标，并设待定位节点坐标与各锚节点坐标间距离为dj。则可建立定位方程Q

(13)

再对式(13)进行系数分离，可得

(14)

(15)

(16)

联立式(14)～式(16)可得

TZ=J

(17)

显然，Z满足

Z=(TTU)-1TJ

(18)

式中：U表示矩阵转秩。

通过式(18)即可精确获取待定位节点坐标(x,y)。由于待定位节点与锚节点间链路整体长度可通过式(9)来获取，其相应的最小跳数可通过式(8)进行动态评估，结合定位椭圆弧形边与待定位节点坐标(x,y)之间的对应关系，即可在定位椭圆上快速通过路径回溯待定位节点，从而达到动态测距的目的。

3 本文算法的复杂度分析

本文算法主要由基于弧度路径析构的节点椭圆定位和基于椭圆纵半径跳数优化的动态测距两部分构成。不妨设网络中传感节点数量为m，锚节点个数为n。在基于弧度路径析构的节点椭圆定位过程中，所提算法首先需要通过逐个过滤传感节计算获取最小跳数，并通过分组报文中过滤出最小跳数对应的锚节点，其复杂度为o(m)。基于椭圆纵半径跳数优化的动态测距机制在获取最小跳数的基础上，按式(13)建立定位方程组，方程组建立过程中将通过锚节点逐个建立定位方程，由于锚节点个数为n，因此复杂度为o(n)。因此，综合上述2个过程，本文算法的复杂度为o(m)+o(n)。

为了突出所提算法的优势，将文献[14]和文献[15]视为对照组。文献[14]算法在遍历网络锚节点的基础上，逐项计算各节点间的平均跳数，该过程的复杂度为o(m)，随后需要对符合要求的信标节点进行迭代，迭代次数为n，考虑到匹配信标节点的过程需要遍历全部传感节点，此过程复杂度为o(m×n)，因此文献[14]算法复杂度为o(m)+o(m×n)，显然要高于本文所提算法。文献[15]通过构建罚函数模型来记录定位过程中性能较差节点坐标，记录过程中均遍历全部传感节点并得到学习样本，随后将动态学习该样本，得到样本获取过程对应的算法复杂度为o(m2)，学习过程按照水波算法进行迭代，迭代次数为n，该过程复杂度为o(m×n)。因此，文献[15]算法复杂度为o(m2)+o(m×n)。考虑到传感网络中锚节点个数一般要少于传感节点个数，因此，文献[15]算法的算法复杂度亦要远远高于本文算法。综上所述，本文算法在复杂度方面具有一定的优势，具有定位过程较为简单的特点，能够以较快的速度获取待定位节点的坐标。

4 仿真实验

为便于验证本文算法性能，采取NS2平台(network simulator version 2)进行仿真实验。实验区域为矩形区域，面积为1000×1000 m2。由于移动无线传感网具有拓扑变动较快的特性，针对待定位节点均将重复进行10次定位过程，将10次定位结束后获取的坐标平均值视为标准结果，以便降低网络拓扑频繁变动所造成的定位误差。传感节点制式采用5G移动通信模型，使用64ASP调制方式，其余实验参数见表1。另外，为了突出所提算法的先进性，将当前移动无线传感网领域中常用的基于跳数修正和改进粒子群优化DV-Hop定位算法[14](DV-Hop localization algorithm based on hop number modification and improved particle swarm optimization，HNM-IPS算法)、基于罚函数与水波优化的WSN定位算法[15](WSN location algorithm based on penalty function and water wave optimization，PF-WWO算法)和基于三维离散混沌映射的无线传感器网络定位算法[16](A WSN positioning algorithm based on 3D discrete chaotic mapping，3D-DCM算法)作为对照组。

表1 仿真参数

实验开始后，通过统计各算法的定位精度及定位次数来客观评价。定位精度测试过程中，考虑到多个待定位节点坐标记录在不同周期内存在一定的变动，因此将待定位节点设置为静止状态，sink节点作为测量节点，沿矩形分布区域周围以10 m/s的速度移动并捕捉待定位节点坐标，最终形成定位精度仿真记录图，其中锚节点保持静止状态。定位次数测试过程中，sink节点和锚节点均保持静止，待定位节点按不同速度进行游走，达到某定位精度后即记录其定位次数。

4.1 定位精度测试

图7(a)为待定位节点实际分布，图7(b)～图7(d)为本文算法、HNM-IPS算法、PF-WWO算法在进行10次定位后所测的坐标分布结果。由图可知，本文算法所测坐标分布与待定位节点的实际分布契合度最高，而HNM-IPS算法、PF-WWO算法的所测坐标分布均与待定位节点实际分布存在较大的偏离。这是由于本文算法设计了椭圆定位机制，将定位过程中的直线跳距进行椭圆曲线化处理，可将直线架构拓扑修正为精度更高的弧度化曲线拓扑，特别是在处理过程中基于离心模式对椭圆弧边进行精度修正，可有效平滑待定位节点与锚节点间所测拓扑链路，降低测序过程中因弧度误差而导致定位漂移现象的发生概率，因此具有较高的定位精度。HNM-IPS算法主要通过计算锚节点之间平均拓扑定位跳数，并利用该跳数修正定位过程中出现的邻域裁定误差，没有考虑所测距离存在的直线拓扑测距误差，虽然采用粒子群方法来修正进行定位误差，但难以消除多跳环境中的测距误差，特别是拓扑更迭频繁时期误差将更为明显，因此其定位精度较低。PF-WWO算法采用动态学习策略来优化定位过程，并设计罚函数来记录定位过程中性能较差节点坐标，从而获取信号强度较高的锚节点，然而该算法亦对移动无线传感环境存在的拓扑变动考虑不够，迭代过程中需要预设次数，难以对节点坐标进行精确匹配，因此所测链路在拓扑变动频繁时存在较高的剧烈变动概率，导致直线拓扑与实际所测链路出现匹配困难的问题，因此定位精度难以进一步提升，使得该算法定位精度亦要低于本文方法。3D-DCM算法主要采取最小二乘估计模式估测坐标，从通信半径及拓扑结构两个方面优化节点定位精度，且构造三维离散混沌映射，将混沌优化算法引入到定位误差精度提高之中，一定程度上解决了节点移动过程中出现的定位漂移现象。然而，该算法对节点运动速度方面限制性较高，特别是在三维离散混沌映射过程中严重依赖线性映射方法，使其仅能针对已定路径上的节点进行精度估计，因此，在拓扑出现变动时将因映射失效而导致精度会出现较大幅度下降，降低了节点坐标匹配程度。

4.2 定位次数测试

图8为本文算法与HNM-IPS算法、PF-WWO算法在达成相同定位精度时所花费的定位次数的测试结果，其中，定位误差数值越低说明定位精度也就越高。由图可知，所提算法在达成相同定位精度条件下所耗费的定位次数更短，说明本文算法具有很强的定位能力，对移动无线传感网高拓扑流动特性适应能力更强。这是由于本文算法在弧度路径析构的基础上，针对定位椭圆存在的半径抖动情形，设计了基于椭圆纵半径跳数优化的动态测距机制，可迅速捕捉待定位节点，算法运行过程中仅需要针对锚节点与传感节点进行遍历并解析最小跳数，无需采用粒子群模式进行多次迭代，因此具有定位次数较低的特点。HNM-IPS算法采用粒子群模式逐次迭代定位坐标，迭代次数与定位精度具有显著的正相关特性，当定位精度难以满足需求时需要频繁迭代坐标，因此达到相同定位精度所耗次数较高。PF-WWO算法所提罚函数机制虽然能够增强待定位节点在定位过程中对锚节点的搜寻能力，然而由于该算法并未对移动无线传感环境中存在的多跳路径进行弧形优化，因此对路径适应能力较低，使得达到相同定位精度所耗的次数要高于本文算法。3D-DCM算法从通信半径及拓扑结构两个方面对节点定位精度进行提升，并采取最小二乘估计模式对坐标进行进一步优化。然而，该算法进行定位过程中需要采集的样本数较多，在拓扑结构变动频繁的情况下样本精确度易出现下降，此外，该算法对网络资源进行优化时单纯依赖于能量因素，频繁进行映射过程中容易导致定位节点出现能量受限，致使出现重定位现象较为突出，使得在定位次数上要高于本文算法。

图7 不同算法的定位精度

图8 定位次数

5 结束语

为解决移动传感网在拓扑流动性较高情形下存在的定位精度不高、数据传输能力较差、抗干扰性较弱等不足，提出了一种基于双焦点离心测距机制的移动传感网高效定位算法。通过设计椭圆定位机制，对直线拓扑进行椭圆弧形优化处理，提高测距过程中的首次定位精度。随后，通过椭圆覆盖范围来应对网络拓扑变动频繁的情形，从而解决因拓扑测距失真而导致定位精度下降的问题，提高节点频繁移动情形下的定位效率。

下一步，将针对本文算法对立体传感网络适应性不足的问题，拟引入超流体拓扑评估方式，将定位椭圆扩充为基于三维曲面机制的立体定位椭球，以便能够适用于诸如无人机、战术数据链组网等实际应用场景，进一步提高本文算法的部署价值。