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

Fast multidimensional scaling localization algorithm based on divide and conquers

作　　者：吕宏达[1,2] 李克清[2] 戴欢[2] LV Hongda;LI Keqing;DAI Huan(School of Computer Science and Technology, Soochow University, Suzhou, Jiangsu 215000, China;School of Computer Science and Engineering, Changshu Institute of Technology, Changshu, Jiangsu 215500, China)

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215000 [2]常熟理工学院计算机科学与工程学院,江苏常熟215500

出　　处：《计算机工程与应用》2016年第19期102-106,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61300186);校科研项目(No.XZ1301);苏州市物联网工程应用重点实验室项目(No.SZS201407)

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

关 键 词：定位 分而治之 距离矩阵 奇异值分解 无线传感器网络 

分 类 号：TP393.1[自动化与计算机技术—计算机应用技术]