无线传感器网络多维定标算法综述

摘 要：阐述了无线传感器多维定标技术的原理，给出了两种典型算法的推导，分析了三维坐标的转换。

关键词：多维定标算法

本文系2011年院级自然科学基金“集中式无线传感器网络三维定位算法研究”（XYKJ2011013）和2012年院级教改项目“基于proteus的《单片机原理》虚拟教学平台的研究与应用”（JY1208）的阶段性研究成果。一、多维技术原理

假设空间上n个对象点的任意第i个点和第j个点之间的相异（似）性以δij来表示，则可构成一个相异（似）性矩阵[δij]，设空间上n个对象点的坐标矩阵为X，则X是一个n×p的矩阵，每一行对应一个点的p维坐标。多维空间上对象点i和j的距离用dij表示，多维标度技术就是利用各对象点间的相异（似）性来构造多维空间上点的相对图，并使得相异（似）性δij与距离dij尽可能的接近，即使得f（δij）≈dij，系数函数为Stress=Σ（f（δij）-dij）2

二、基于Metric MDS的定位算法

假设有n个对象点，对应的节点坐标为X=（x1，x2，…，xn）p，其中X是一个n×p的矩阵，表示n个节点的p维坐标，p=3。任意两个节点间的距离已经获得，则可以得到距离矩阵D=[dij]是一个n×n的方阵，表示点xi和xj之间的估算距离。若i=j则有dii=0，对于任意i和j有dij=dji，由欧氏距离公式得到距离平方矩阵D2=[d2ij]，如式2-1所示：

设有矩阵B，，可以得到矩阵D和矩阵B的关系，如式2-2：

（2-2）

对矩阵D2二次中心化，即对相应的坐标矩阵X中心化，使得

，即，由此可推导出式2-3：

上式可以写成矩阵形式，即式2-4：

（2-4）

其中，为中心矩阵，In×n为n阶单位矩阵，

e1×n[1，1，…，1]。对矩阵B进行特征值分解，如式2-5：

B=XXT=UVUT （2-5）

并保留三个最大的特征值和对应的特征向量来计算节点的三维坐标，设u1>u2>u3和v1>v2>v3分别为三个最大的特征向量和特征值，按式2-6计算节点的三维坐标：

（2-6）

其中U是由特征向量u1，u2，u3按列排列组成的矩阵，V是以，，为主对角元，其他元素为零的矩阵，则X即为节点的三维坐

标矩阵。

三、基于Non-metric MDS的定位算法

假设n个对象点在多维空间中的坐标用矩阵X表示，X是一个n×p维的矩阵，其中n表示对象点的数目，p代表坐标点的维数，则矩阵X中的第i行表示第i个对象点的p维坐标。

基于Non-metric MDS的定位算法根据给定的对象点之间的相异（似）性重构多维空间上各对象点的坐标和它们之间的距离，是一个反复迭代的计算过程，共分为三个阶段：第一阶段为初始化阶段，可以采用某种算法粗略地计算节点的坐标只要保证对象点的初始坐标不相同即可，根据计算获得的初始坐标从任意一个对象点的坐标X0开始计算对象点之间的欧式距离dij0。第二阶段为非定标阶段，根据第一阶段获得的欧式距离可以得到一个等级值，该值的意义为，如是通过构

建δi和dij0的单调回归关系时产生的。δi和dij0必须满足弱单调性要求：对于任意i，j，k，l，如果有δij<δkl则。为了得到可以采用一

种近似方法，例如PAV（pool adjacent violators）算法。PAV算法的过程为，首先由相异（似）性用δij的最小值开始，把邻近的与每一个δij比较来确定是否满足与对应的δij满足单调关系。当存在一组连续的

值违背了与δij的单调关系时，就取这些值的平均值。第三阶段为定标阶段，根据X0和计算新坐标X1，再计算它们之间的欧式距离dij1，不

断地重复第二和第三阶段，直到满足一定的系数要求即可。由此可见Non-metric MDS也可以看作是一种对Metric MDS的优化算法。

Non-metric MDS算法也采用类似于Metric MDS的系数方程来衡量计算结果与给定相异性的吻合度，其中Kruskal系数如式3-1：

其中表示平均距离。

四、三维坐标转换

在分布式的无线传感器网络定位中，多数情况计算出的坐标是局部相对坐标，每一个局部小区域内有各自的相对坐标。为了得到统一的全局坐标，必须将局部坐标转换到全局坐标系中去。

对于两个不同的坐标系R1和R2而言，设点Xi1∈R1，Xi2∈R2，要将Xi1转换到坐标系R2中，也就是要对目标坐标系进行相异的平移，旋转和缩放，即需要三个变量，分别是平移向量，比例因子和旋转矩阵。对于两个三维坐标系而言，能够将其互相转换的前提条件是，需要已知至少四个点分别在两个坐标系中的坐标，即Xi1和Xi2中至少有4个点同时属于坐标系R1和R2。■

参考文献

[1] H. Chen， D.Ping， Y.Xu， X.Li. A Novel Localization Scheme Based on RSS Data for Wireless Sensor Networks， Advanced Web and Network Technologies， and Applications， LNCS 2006.

[2] H. Chen， D.Ping， Y.Xu， X.Li. A robust location algorithm with biased extended kalman filtering of TDOA data for wireless sensor networks. In： Proceedings of International Conference on Wireless Communictions， Networking and Mobile Computing 2005， 883-886.

[3] 袁文燕， 刘慧， 姜冬青. 矩阵论及应用. 化学工业出版社.2003.9. 43～62.

作者简介

闵辉（1983-），男，江西南昌人，江西科技学院商学院，本科，讲师。研究方向：无线传感器网络。