基于非对称广义中心化矩阵的多维尺度定位算法

程飞，章平，周祺，秦心静，杨彩凤

（安徽工程大学 计算机与信息学院，芜湖 241000）

随着传感器和通信设备尺寸、成本等限制迅速降低，无线传感网络不断渗透到一些新的应用领域，如精准农业、工业自动化、汽车导航等［1-2］。在这些领域中，无线传感器节点能够对温度、压力和速度等物理量进行测量，结合节点位置信息，实现与位置有关的各类服务［3］。事实上，在很多现代的通信系统中，位置信息的价值几乎等同于通信数据本身的信息价值［4］。考虑到在对无线传感器节点进行部署的时候，大多数节点的位置很难被事先确定，因此，节点定位问题始终是无线传感网络中需要研究的重要课题。

根据测量的物理量不同，基于节点的定位方法可以分为两类：基于测距（Range-based）和非测距（Range-free）的定位方法。Range-based算法通过测量节点之间的距离来实现定位，有三边算法［5］、多边算法［6］等。Range-free算法则无需测量节点之间的距离，而是根据网络的连通性等信息来实现定位［7］，包括距离向量-跳段（Distance Vector-hop，DV-hop）定位［8］、凸规划（Convex Op‐timization）定位以及质心定位等算法［9，10］。其中，多维尺度（Multidimensional Scaling Map，MDS-MAP）算法［11］可以在Range-based的环境下，通过测量节点间距离实现定位；也能在Range-free的情况下，根据节点间的连通信息进行位置估计，因此该算法在实际生活中被广泛应用。

最早将MDS算法引入无线传感器网络定位领域的是 Yi Shang等人［11］，其提出的 MDS-MAP算法首先使用经典MDS算法获得相对位置信息，然后通过MAP迭代，进行集中式优化。后来他们又提出了一种改进的MDS-MAP（P）算法［12］，该算法的MAP部分可以通过分布式算法来计算位置，有利于降低能耗和提高鲁棒性［13］。与MDS-MAP相同，该算法也存在MAP的迭代优化，分布式可以降低算法复杂度，却比较容易陷于局部极值。文献［14］则是在MDS算法的基础上，提出了一种距离自调整的MDS定位算法。该算法运用3种方法对节点的两跳距离进行估算，然后自动调整节点间的估计距离，从而提高定位精度。文献［15］提出了一种基于MDS的改进算法，通过构建每个节点的局部地图（相邻节点构成），然后拼接成全局地图。其缺点是合并局部地图存在误差累积的问题。文献［17］中通过考虑一般的中心化矩阵推广了MDS算法，通过寻找满足条件的中心化矩阵抑制多跳距离误差，进而提高定位精度。该算法存在两个缺陷，一方面，该算法提出来的中心化矩阵是要求对称的，但对称性要求在构造矩阵时会带来额外的计算量，增加了算法的时间复杂度；另一方面，实际应用中，如何构造或者选择合适的中心化矩阵尚未明确。

针对以往算法存在的不足，本文提出一种基于非对称广义中心化矩阵的多维尺度定位算法。该算法为了解决测量过程中产生的“测距错误”距离矩阵对定位结果造成的影响，构造了一般的行和为0的中心化矩阵，无需对称。该方法既增加了对中心化矩阵的可选数量，也降低了构造中心化矩阵的计算复杂度。对于一般的中心化矩阵，本文所提出的算法能很好地适应网络连通度不高和不规则的环境，获得更高精度的定位结果。

特别地，对于测量过程中经常出现的一些“测距错误”节点，本文设计了相应的中心化矩阵，降低“测距错误”节点对全局的影响，提高其他节点定位精度。

1 MDS定位算法

假设m维空间中（一般m取2或3），随机分布n个节点，i点坐标为Xi=(Xi1,Xi2,…,Xim)T，j点坐标为Xj=(Xj1,Xj2,…,Xjm)T，则节点i和节点j之间的欧氏距离为：

定义n×m维坐标矩阵：

距离平方矩阵：

在不考虑测量误差的情况下：

对B进行特征值分解［18］，则：

其中，Λ为n阶对角矩阵。

经过旋转变换后的坐标为：

2 非对称广义中心化矩阵的MDS定位算法

在经典MDS算法中，采用的是已经定义好的双中心化矩阵，当存在少量误差较大的距离估计时，整体定位精度会受到这些误差较大的距离估计的影响而降低。在文献［17］中重新对中心化矩阵H1进行约束，需满足H1en=0，并要求H1对称。

本文考虑到测距环节出现的一些“测距错误”节点会影响定位精度，提出一类非对称广义中心化矩阵H，定义为k×n随机矩阵，满足He=0，其中e为全1矩阵。对H重新进行约束，一是放宽了约束条件增加了H的可选数量，可以找到符合高定位精度需求的H；二是H无需对称，能够在构造时减少计算量，降低时间复杂度。

根据以上约束条件，若：

则满足：

任一满足行和为0的矩阵都是非对称中心化矩阵H的选择。

将式（3）两端同时左乘H，右乘HT，得到：

对A进行SVD分解，可以得到

则：

令ξ1,ξ2,…,ξr是H的零空间的一组基向量，即：

3 仿真实验结果及分析

为了研究基于非对称广义中心化矩阵的MDS算法的定位性能，本文通过仿真实验和经典MDS算法［16］、修正 MDS算法［17］进行了对比。实验环境与场景：矩形随机网络、C型随机网络；随机分布50个节点的2-D平面50m×50m区域。实验参数：节点间通信半径r。节点分布如图1所示。

图1 节点分布图

本文使用相对误差［19］评价算法性能。通过Procrustes方法将相对地图拟合到真实坐标上面，消除相对坐标通过反转、平移、正交旋转等操作带来的不确定性，从而得到绝对坐标。实验评价算法性能的准则是通过计算节点真实坐标与得到的估计坐标间的均方误差：

本文提出了利用节点间距离误差作为评价算法的另一准则。根据不同算法生成的相对地图得到两两节点间的距离D͂，和两两节点间的真实距离D作差（这里只考虑直接连通节点间距离，不考虑多跳距离），对所有节点间的距离误差绝对值求和，然后比较距离误差和定位误差之间的关系来进行验证。表示为：

（1）非对称广义中心化矩阵H的可行性验证

图2 特定网络拓扑

仿真结果显示，经典MDS算法利用Procrustes方法得到前3个节点坐标为，A（-0.289 1，-0.123 6），B（4.178 8，0.070 7），C（3.110 4，4.052 9），相对误差为0.050 3。本文所提算法通过Procrustes方法得到的结果为，A（0，0），B（4，0），C（3，4），前3个节点相对误差为0。由此可以看出，非对称中心化矩阵H能够对前3个节点精准定位，完全消除了测距错误节点带来的负面影响。

在实际定位过程中，会有外界因素干扰导致测得的距离矩阵并不完全正确，从而影响整体的定位精度。在构造H时可以通过合理的设计，假设第n个节点和其他节点连通度不高，其多跳距离估计误差较大，则可以减小H最后一列的值，降低与第n个节点相关的距离对整体的影响。极限情况就是假设H最后一列全是0，则第n个节点的测量完全不采用，最终定位后，等价于对前n-1个节点使用MDS算法定位，完全消除最后一个节点带来的负面影响。

（2）距离误差和定位精度的相关性验证

该实验主要比较三种算法在不同网络拓扑下，随着通信半径的不同，距离误差和定位精度的关系。在实验场景的矩形网络拓扑下，利用图1的节点分布图进行实验。该实验的距离误差和定位误差关系如图3、图4所示。图3为三种算法分别在通信半径r=10 m、r=11 m、r=12 m、r=15 m的情况下运行的结果；图4为三种算法分别在通信半径r=15 m、r=18 m、r=20 m、r=24 m的情况下运行的结果。

图3 矩形网络不同通信半径下距离误差和定位误差关系图

由实验结果可以看出，在同种网络拓扑，不同通信半径下，与经典MDS算法相比，非对称MDS算法的距离误差会比修正MDS算法的结果更小，更集中，同时在定位性能方面提升更为显著。图4中，在C型网络下r=15、r=18 m、r=20 m时，修正MDS算法平均定位误差分别为：223.608 4，183.714 7，160.647 1；非对称 MDS算法平均定位误差分别为：202.745 1，177.604 3，150.902 5。因此，非对称MDS算法能够适应不同的网络拓扑及通信半径，有效地抑制节点间距离误差，以此提升定位精度。

图4 C型网络不同通信半径下距离误差和定位误差关系图

（3）连通度对定位精度的影响

该实验主要比较3种算法在不同连通度下的性能。在实验场景的矩形网络和C型网络下，节点部署如图1所示，矩形网络连通度分别为5.84，7.08，8.32，11.92，16.72，C 型网络连通度为11，14.04，17.20，21.20，23.32。实验结果如图 5、图6所示（连通度=节点间连通次数/节点数）。

图5 矩形网络连通度的影响

图6 C型网络连通度的影响

图5、图6可以看出，在不同的网络连通度下，非对称MDS算法定位性能优于经典MDS算法和修正MDS算法。在连通度较低的情况下，本文提出的算法定位精度有明显的提高，尤其在C型网络环境下，定位精度提升幅度会更大。因此，与经典MDS算法和修正MDS算法相比，非对称MDS算法在连通度不高和不规则网络拓扑下适应性更高，在实际定位中具有明显的优势。

4 结论

针对以往算法容易受到“错误”距离估计影响的问题，本文提出了基于非对称广义中心化矩阵的MDS算法。该算法推广了已有的中心化矩阵，构造了一类中心化矩阵用于“测距错误”节点的筛选，降低其对整体定位效果的影响；在距离误差和定位精度相关性验证的算法仿真对比实验中，非对称MDS算法表现出了比修正MDS更好的性能，能更好地抑制距离误差，以此提升定位精度；在连通度对定位精度影响的算法仿真对比实验中，本文提出的算法通过选择有助于抑制“错误”距离的中心化矩阵，有效地提高了节点对连通度不高和不规则网络的适应性，改善了定位性能。