MDS与三边定位相结合的多点相对定位算法

,,

(1.卫星导航系统与装备技术国家重点实验室，石家庄 050081；2.中国电子科技集团公司第五十四研究所，石家庄 050081)

0 引言

PNT体系即定位(Positioning)、导航(Navigation)、授时体系(Timing)组成的时空体系，是我们得以在纷繁信息中准确描述时间和空间的关键技术。而定位导航的核心是准确，及时，全面地获得待测目标的位置信息和运动参数，并为其提供下一时刻的路径规划，为了实现这一目的，需要定位导航系统具有精准定位能力和抗干扰能力。传统的PNT信息大多由全球卫星导航系统提供，如美国的GPS、欧洲的伽利略、俄罗斯的格洛纳斯，还有中国的北斗。近几十年来，卫星导航不断发展，应用广泛，PNT对卫星导航系统形成了强烈依赖性，但卫星导航存在一些固有的缺点，如信号强度弱、穿透能力差、易被干扰欺骗和易受攻击等。一旦卫星导航系统受到攻击，停止工作，己方编队将失去空中协同运作能力。因此，为了构建完整的PNT体系，发展备份导航定位显得尤为重要。

近年来，PNT技术体系的发展对备份导航技术提出了更高的要求，而集群的相对定位技术是备份导航的关键技术之一。开展拒止环境下动态网络集群定位技术的研究是发展备份导航领域的硬性需求，具有突出的研究价值。实现集群相对定位的方式之一就是多维标度法。

多维标度法(Multidimensional-Scaling，MDS)是一种把空间中物体的相似性转换为空间坐标的数据分析方法，它是利用各节点间的相似性信息来确定坐标。最早由Shang等人提出了将MDS用于定位的MDS-MAP算法，利用节点间的距离信息代替相似性，构造相应的距离平方矩阵，然后中心化，求特征值、特征向量，进而得到相对坐标[1]。不难发现，MDS-MAP算法的基础是要获得所有节点之间的距离信息，但在实际中，由于测量设备和外部环境的影响，很难获得所有距离信息，而用最短路径等方法估计得出的距离矩阵存在较大误差，降低了定位精度。为了提高定位精度，本文提出一种MDS与三边定位相结合的定位方式，以此弥补传统MDS在距离信息上的硬性需求，这种方法兼顾考虑了MDS的最短路径问题和三边定位的误差传递层数问题，是一种对二者的优势结合算法。

1 MDS-MAP算法

多维标度技术源于心理测量学和精神物理学，最早被心理测量学家或数学家和统计学家运用于心理测量领域。作为一种数据分析技术，MDS通过构建一个或多个矩阵来表示物体间的距离或相异程度，并在低维空间中(一般为二维或者三维)寻找一个合适的点间距离分布[2]。多维标度分析技术的主要优势是，即使在少量锚节点的情况下，也可以使用该技术获得精确地位置估计。但其也有本身的缺陷，包括集中式的算法对中心节点能耗较大等等[3]。

经典的度量多维标度技术中，假设已知各实体间的欧氏距离，距离值即代表实体间的相异性，其根本思想是对相异性矩阵进行数学方法上的重构，使其满足胁强系数的要求[4]。

对传统的MDS用于定位的MDS-MAP算法原理进行深入推导。

首先由已知的实体间的距离信息确定集群的距离平方矩阵:

其中:dij,i=1,2,3,…，n,j=1,2,3,…,n为节点i与节点j之间的距离，n为区域内节点的个数。

设节点i的坐标为(xi,yi,zi)，则有：

dij2=(xi-xj)2+(yi-yj)2+(zi-zj)2=

xi2+yi2+zi2+xj2+yj2+zj2-2xixj-2yiyj-2zizj

在此，不防构造两个矩阵R，X：

其中:Ii2=xi2+yi2+zi2

X即为节点的坐标矩阵，则有:

D(2)=R+RT-2XTX

对D(2)进行双重中心化，即在D(2)的两边同时乘以中心矩阵J，用矩阵B表示D2的双中心形式，得到:

其中:

所以:

易知:

RJ=0,JRT=0

所以:

所以:

其中:U、V分别为对B进行特征值分解的特征值组成的对角阵及其对应的特征向量组成的矩阵。

JXT即为中心化后的各节点的相对坐标。

2 MDS与三边定位相结合定位算法

传统的MDS-MAP算法虽然可以实现网络集群定位，但通过上述分析仍存在一些问题：

需要知道所有节点之间的相对测量距离，但在实际中由于资源的限制很难实现，而为了解决这个问题最常用的一种方法就是用最短路径代替多跳之间的距离，但这种方法存在不确定性，偏差较大，会对定位精度造成很大影响[5-6]。

图1 算法流程图

为了解决最短路径带来的不确定性问题，提出一种MDS与三边定位相结合的定位方式，这种方法的基本原理是先对一部分单跳节点使用MDS进行相对定位，然后这些节点作为锚节点，对其他节点进行三边定位，逐层扩展，直至实现全网的定位。这种方法有效的解决了最短路径代替多跳距离所带来的误差问题，相较于全部使用三边定位，也减小了误差扩展层数，对定位精度有很大提升，具体步骤如下：

第一步：根据节点间测量的欧氏距离得出距离矩阵：

若i、j两点间距离不可测，则直接令dij=0，不再以最短路径替代。

第二步：寻找包含最多节点的区域，使得该区域内所有节点都相互连通，即所有节点间距均可测量。即在矩阵D中选取m行和对应序号相同的m列，使得选取行列在矩阵D中的交点除对角元素外全部不为零，选取使m值最大的行列，并将其交点按在D中的排列提出，构成新的距离矩阵：

对D′使用MDS，得到所选取节点的相对位置坐标X。

这一步的目的是为了找到集群中最大的全连通结构，并确定其相对位置，但在实际操作中，寻找最大全连通结构的算法复杂，运行时间长，若根据测距信息逐个遍历，耗时久，计算资源消耗大[7]，因此为了简化算法，降低计算时间，采用一种从概率上进行优化的方法：

1)在获得距离矩阵D后，根据集群包含的节点数量，设置一个阀值ε，当找到ε个全连通节点时，则停止寻找，执行下一步三边定位算法。

2)在矩阵D中舍弃与其他节点连通度最低的节点所对应的行列[8]，检查剩余D矩阵是否为除对角元素外全不为零矩阵，若满足则判断其中节点数是否大于阀值ε，若小于，则在此基础上对以舍弃节点进行搜索，若大于，则执行MDS算法，若不满足则重复此步骤。

这样可以在定位精度和运行时间之间有一个权衡，是算法趋向最优化。

而由于下一步的三边定位算法是逐层向外扩展，所以定位误差也会逐层积累，越来越大，所以这就要求使用MDS算法定位的作为下一步的锚节点的节点具有较高的定位精度，因此在执行MDS算法之后在此处进行一次迭代校正[9]，具体方法如下：

设置压力函数:

化简为:

其中:δij表示距离估计量，可由MDS定位结果的坐标计算得出，dij(X)为测量距离。

写作矩阵形式：

对此，采用smacof算法，取辅助函数为：

g(X,Z)=C+trXTVX-2trXTB(Z)Z

其中：

令g(X,Z)一阶导数为零，即可得到{XK}序列的更新公式：

Xk+1=V+B(Xk)Xk

第三步：对剩余节点进行搜索，找出与上述已定位区域存在两个或两个以上连通的节点，并利用三边定位的方法对其进行定位，得出定位结果后将其归于该区域内，然后继续对剩余节点进行搜索，直到包含所有节点。

若与区域内两个以上的节点连通，连接的节点坐标分别为(x1,y1)、(x2,y2)、…、(xn,yn)，待求节点的坐标为(xc,yc)，则有以下方程组：

这里可以使用最小二乘估计来估计待测节点的坐标，这样得出的估计值比只选用其中两个节点进行三边定位的结果要准确，误差更小。

而当作为要定位的节点的锚节点数量较多时，由于我们采用的MDS与三边定位相结合的算法架构上是从中间向周围蔓延的，所以相较于锚节点分布在节点四周的情况，这种方法会使锚节点分布在一侧，在使用三边定位时，更有可能会出现共线和定位误差较大的情况，最小二乘也无法有效解决此类问题，因此，在这里采用一种改进的组合三边定位算法，具体步骤如下：

1)从要定位节点的邻居锚节点中多次选择不同节点进行三边定位，获得一系列候选节点。

2)对候选节点集进行过滤，滤除由于共线和非正常测距误差造成的异常定位结果[10]，对剩余节点求均值作为最终定位结果。

这样的处理方式有效解决了三边定位的不稳定性，将定位误差稳定在较低水平，大大缓解了其误差传播与积累问题，剔除了误差较大的异常定位结果，增加了算法稳定性。

在扩展到最外层节点的时候，有可能会出现外层节点只与区域内一个节点连通，此时在只获得距离信息，没有其他技术支持的条件下，可以使用最短路径来获得间距，然后局部使用MDS或者三边定位，这样虽然会造成个别节点的定位结果偏离，但整体而言，影响较小。

如图2所示，若整个集群中最多包含5个节点可以两两连通，则先对虚线内的这5个节点使用MDS，得出相对坐标后，再对其他和区域内节点两个或两个以上连通的节点进行三边定位，依次进行。

图2 方法示意

3 仿真验证

针对本文提出的MDS与三边定位相结合的定位方式，考虑在不同环境下，算法的适应性，分别在随机分布和U型分布两种分布条件下，对比传统的使用最短路径代替多跳距离的定位方式，进行节点的布置，验证算法性能，分析算法的优越性和不足，确定算法的后续优化方向。

参数设置：在200×200的区域内设置20个随机分布的节点来模拟集群分布，规定节点的有效测距范围是50，分别对其使用最短路径代替多跳的传统MDS和本文提出的MDS，三边定位相结合的方式进行定位，并从定位精度，计算复杂度和适用条件等方面对比分析本文所提算法的优劣性。仿真结果如图3～5所示。

图3 随机分布定位结果

图4 随机分布定位误差

图5 U型分布定位结果

图6 U型分布定位误差

图3和图5中，节点表示各节点的真实位置，△表示使用最短路径代替多跳距离的传统MDS定位结果，O表示使用本文提出的MDS和三边定位结合的定位结果，从图3中可以直观看出，在随机分布的区域中，本文所提出的方法定位精度明显优于传统MDS，且不会出现大幅度的偏移。从图5中可以看出，在U型分布的区域中，本文所提方法的定位结果依然与节点实际位置保持一致，偏差不大，而传统的MDS算法较之随机分布的情况，在U型分布的条件下，定位结果出现较大偏离。

图4和图6表示两种方法的定位结果和节点真实位置的欧氏距离差的分布情况，可以看出本文所提出的方法的误差相对较小，且平稳维持，而传统MDS的误差较大，且波动幅度较大。且本文所提算法在随机分布和U型分布的区域内定位误差基本保持一致，算法的适应能力强，而传统的MDS在U型分布下由于分布更为极端导致了连通度的降低，相较于随机分布的构型，误差整体增大，适应能力差。

表1显示了MDS三边定位算法与传统MDS定位算法的性能比较，从表中可以看出，无论是随机分布网络还是U型分布网络，所提算法的定位性能都明显高于传统MDS，且对网络构型的影响不敏感。但是从算法的执行时间来看，所提算法的运行时间略高于传统MDS，而且随着拓扑结构的变化会产生较大波动，这是由于固有的集中式计算架构所决定的，其计算复杂度相较于传统MDS-MAP算法有所增加，所以造成了算法运行时间的增长，若是用于高动态的集群网络的定位，则无法满足实时性的要求，所以，也为后续算法的优化提供了方向。

表1 算法性能对比

4 结束语

本文所提出的MDS与三边定位相结合的定位方法定位精度较高，适应能力强，相较于传统的MDS-MAP算法，解决了由于最短路径带来的较大定位误差问题，相较于传统的三边定位算法，减小了其误差传递层数，将MDS和三边定位进行优势互补，用尽可能简洁的算法实现高精度定位。但该算法仍存在一些不足：

在寻找包含连通节点最多的区域时，本文所采用的算法循环次数多，计算时间较长。

在三边定位向外扩展时，会逐层传递误差，增加定位结果不确定性。

该算法依然属于一种集中式算法，计算负担大，资源消耗多，与传统的MDS-MAP算法在定位时间和计算速度上无显著优势，甚至会偏慢。

针对上述的三点不足，后续将继续在简化算法计算量和减小定位误差方面做深入研究，推导更简洁的寻优算法，寻求一种适用于算法的分布式计算架构，完善本文所提算法，进一步提升定位精度。