基于分而治之的快速多维尺度定位算法

摘要

Due to traditional MDS-MAP algorithm extracts the distance information from all the nodes in the network, it’s time complexity will be very high that hinders the speed of the positioning. To solve this problem, this paper proposes the DMDS-MAP localization algorithm which based on divide and conquer with traditional MDS-MAP, it can effectively improve the positioning speed through eliminating the redundant data. By DMDS-MAP algorithm, the distance matrix is divided into several sub matrices, then using singular value decomposition to decompose and extract the feature of the sub matrices in specified dimension to obtain it’s relative coordinates, next melt results of each sub distance matrix to get all nodes’relative coordinates, at last global absolute coordinates are obtained through the anchor node. The experimental results indicate that with the similar positioning accuracy, as the increase of density of nodes which participating in the transform, compared with DMDS-MAP algorithm, MDS-MAP algorithm has significant improvement in running time.%传统MDS-MAP算法通过同时提取网络中所有节点间距离信息的特征来实现定位，计算时间复杂度相对较高，影响了算法的定位速度。针对该问题，提出了基于分而治之的快速多维尺度定位算法DMDS-MAP，剔除参与转换的冗余数据，可有效提高原始MDS-MAP算法的定位速度。DMDS-MAP算法将距离矩阵进行划分，选取对角阵作为子矩阵以剔除冗余数据，通过奇异值分解从各子矩阵中提取指定维数的特征转化为相对坐标，融合由各子矩阵求得节点的相对坐标，得到所有节点的相对坐标，最后，根据锚节点坐标信息得到所有节点的全局绝对坐标。实验结果表明，在定位精度相似的情况下，随着参与运算的节点密度的增加，DMDS-MAP算法较MDS-MAP算法在运行时间上有明显的提升。