1、无线传感器网络多维定标算法综述摘 要：阐述了无线传感器多维定标技术的原理，给出了两种典型算法的推导，分析了三维坐标的转换。 关键词：多维定标算法 本文系 2011 年院级自然科学基金“集中式无线传感器网络三维定位算法研究” （XYKJ2011013）和 2012 年院级教改项目“基于 proteus 的单片机原理虚拟教学平台的研究与应用” （JY1208）的阶段性研究成果。一、多维技术原理 假设空间上 n 个对象点的任意第 i 个点和第 j 个点之间的相异（似）性以 ij 来表示，则可构成一个相异（似）性矩阵ij，设空间上 n个对象点的坐标矩阵为 X，则 X 是一个 np 的矩阵，每一行对应一
2、个点的 p 维坐标。多维空间上对象点 i 和 j 的距离用 dij 表示，多维标度技术就是利用各对象点间的相异（似）性来构造多维空间上点的相对图，并使得相异（似）性 ij 与距离 dij 尽可能的接近，即使得 f（ij）dij，系数函数为 Stress=（f（ij）-dij）2 二、基于 Metric MDS 的定位算法 假设有 n 个对象点，对应的节点坐标为 X=（x1，x2，xn）p，其中 X 是一个 np 的矩阵，表示 n 个节点的 p 维坐标，p=3。任意两个节点间的距离已经获得，则可以得到距离矩阵 D=dij是一个 nn 的方阵，表示点 xi 和 xj 之间的估算距离。若 i=j 则
3、有 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） 其中，为中心矩阵，Inn 为 n 阶单位矩阵， e1n1，1，1。对矩阵 B 进行特征值分解，如式 2-5： B=XXT=UVUT （2-5） 并保留三个最大的特征值和对应的特征向量来计算节点的三维坐标，设 u1u2u3 和 v1v2v3 分别
4、为三个最大的特征向量和特征值，按式 2-6计算节点的三维坐标： （2-6） 其中 U 是由特征向量 u1，u2，u3 按列排列组成的矩阵，V 是以， ，为主对角元，其他元素为零的矩阵，则 X 即为节点的三维坐 标矩阵。 三、基于 Non-metric MDS 的定位算法 假设 n 个对象点在多维空间中的坐标用矩阵 X 表示，X 是一个 np维的矩阵，其中 n 表示对象点的数目，p 代表坐标点的维数，则矩阵 X 中的第 i 行表示第 i 个对象点的 p 维坐标。 基于 Non-metric MDS 的定位算法根据给定的对象点之间的相异（似）性重构多维空间上各对象点的坐标和它们之间的距离，是一个反
5、复迭代的计算过程，共分为三个阶段：第一阶段为初始化阶段，可以采用某种算法粗略地计算节点的坐标只要保证对象点的初始坐标不相同即可，根据计算获得的初始坐标从任意一个对象点的坐标 X0 开始计算对象点之间的欧式距离 dij0。第二阶段为非定标阶段，根据第一阶段获得的欧式距离可以得到一个等级值，该值的意义为，如是通过构 建 i 和 dij0 的单调回归关系时产生的。i 和 dij0 必须满足弱单调性要求：对于任意 i，j，k，l，如果有 ijkl 则。为了得到可以采用一 种近似方法，例如 PAV（pool adjacent violators）算法。PAV 算法的过程为，首先由相异（似）性用 ij 的
6、最小值开始，把邻近的与每一个 ij 比较来确定是否满足与对应的 ij 满足单调关系。当存在一组连续的 值违背了与 ij 的单调关系时，就取这些值的平均值。第三阶段为定标阶段，根据 X0 和计算新坐标 X1，再计算它们之间的欧式距离dij1，不 断地重复第二和第三阶段，直到满足一定的系数要求即可。由此可见 Non-metric MDS 也可以看作是一种对 Metric MDS 的优化算法。 Non-metric MDS 算法也采用类似于 Metric MDS 的系数方程来衡量计算结果与给定相异性的吻合度，其中 Kruskal 系数如式 3-1： 其中表示平均距离。 四、三维坐标转换 在分布式的无
7、线传感器网络定位中，多数情况计算出的坐标是局部相对坐标，每一个局部小区域内有各自的相对坐标。为了得到统一的全局坐标，必须将局部坐标转换到全局坐标系中去。 对于两个不同的坐标系 R1 和 R2 而言，设点 Xi1R1，Xi2R2，要将 Xi1 转换到坐标系 R2 中，也就是要对目标坐标系进行相异的平移，旋转和缩放，即需要三个变量，分别是平移向量，比例因子和旋转矩阵。对于两个三维坐标系而言，能够将其互相转换的前提条件是，需要已知至少四个点分别在两个坐标系中的坐标，即 Xi1 和 Xi2 中至少有 4 个点同时属于坐标系 R1 和 R2。 参考文献 1 H. Chen， D.Ping， Y.Xu，
8、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. 4362. 作者简介 闵辉（1983-） ，男，江西南昌人，江西科技学院商学院，本科，讲师。研究方向：无线传感器网络。
