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

计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (19): 102-106.

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

吕宏达1，2，李克清2，戴欢2

1.苏州大学计算机科学与技术学院，江苏苏州 215000
2.常熟理工学院计算机科学与工程学院，江苏常熟 215500

出版日期:2016-10-01 发布日期:2016-11-18

Fast multidimensional scaling localization algorithm based on divide and conquers

LV Hongda1，2, LI Keqing2, DAI Huan2

1.School of Computer Science and Technology, Soochow University, Suzhou, Jiangsu 215000, China
2.School of Computer Science and Engineering, Changshu Institute of Technology, Changshu, Jiangsu 215500, China

Online:2016-10-01 Published:2016-11-18

摘要/Abstract

摘要： 传统MDS-MAP算法通过同时提取网络中所有节点间距离信息的特征来实现定位，计算时间复杂度相对较高，影响了算法的定位速度。针对该问题，提出了基于分而治之的快速多维尺度定位算法DMDS-MAP，剔除参与转换的冗余数据，可有效提高原始MDS-MAP算法的定位速度。DMDS-MAP算法将距离矩阵进行划分，选取对角阵作为子矩阵以剔除冗余数据，通过奇异值分解从各子矩阵中提取指定维数的特征转化为相对坐标，融合由各子矩阵求得节点的相对坐标，得到所有节点的相对坐标，最后，根据锚节点坐标信息得到所有节点的全局绝对坐标。实验结果表明，在定位精度相似的情况下，随着参与运算的节点密度的增加，DMDS-MAP算法较MDS-MAP算法在运行时间上有明显的提升。

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

Abstract: 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.

Key words: location, divide and conquer, distance matrix, singular value decomposition, wireless sensor networks

吕宏达1，2，李克清2，戴欢2. 基于分而治之的快速多维尺度定位算法[J]. 计算机工程与应用, 2016, 52(19): 102-106.

LV Hongda1，2, LI Keqing2, DAI Huan2. Fast multidimensional scaling localization algorithm based on divide and conquers[J]. Computer Engineering and Applications, 2016, 52(19): 102-106.

[1]	王博，宋丹，王洪玉. 无人机自主巡检系统的关键技术研究[J]. 计算机工程与应用, 2021, 57(9): 255-263.
[2]	徐少杰，曹雏清，王永娟. 视觉SLAM在室内动态场景中的应用研究[J]. 计算机工程与应用, 2021, 57(8): 175-179.
[3]	周彦，旷鸿章，牟金震，王冬丽，刘宗明. 面向半稠密三维重建的改进单目ORB-SLAM[J]. 计算机工程与应用, 2021, 57(8): 180-184.
[4]	马巧梅，王明俊，梁昊然. 复杂场景下基于改进YOLOv3的车牌定位检测算法[J]. 计算机工程与应用, 2021, 57(7): 198-208.
[5]	李中道，刘元盛，常飞翔，张军，路铭. 室内环境下UWB与LiDAR融合定位算法研究[J]. 计算机工程与应用, 2021, 57(6): 260-266.
[6]	赵凡，张琳，闻治泉，杨林林，蔺广逢. 一种直接高效的自然场景汉字逼近定位方法[J]. 计算机工程与应用, 2021, 57(6): 159-167.
[7]	蔡冬丽，钟清华，朱永升，廖金湘，韩劢之. 三维输入卷积神经网络脑电信号情感识别[J]. 计算机工程与应用, 2021, 57(5): 161-167.
[8]	於小杰，贺勇，刘盛华. 一种用于无人机室内定位的改进ORB光流算法[J]. 计算机工程与应用, 2021, 57(4): 266-271.
[9]	程帅，吴华锋，梅骁峻. 交替非负约束框架的海洋传感网协同定位[J]. 计算机工程与应用, 2021, 57(23): 129-136.
[10]	谢兄，杨金鹏. YOLO-wLU：考虑定位不确定性的目标检测算法[J]. 计算机工程与应用, 2021, 57(22): 223-231.
[11]	杨世强，白乐乐，赵成，王国栋，李德信. 一种改进的Qtree_ORB算法[J]. 计算机工程与应用, 2021, 57(20): 82-89.
[12]	陈金鑫，沈文忠. 基于EL-YOLO的虹膜图像人眼定位及分类算法[J]. 计算机工程与应用, 2021, 57(17): 217-223.
[13]	杨世强，范国豪，白乐乐，赵成，李德信. 基于几何约束的室内动态环境视觉SLAM[J]. 计算机工程与应用, 2021, 57(16): 203-212.
[14]	杨信民，董红斌，谭成予，周雯. 采用奇异值分解和信息增益的树突状细胞模型[J]. 计算机工程与应用, 2021, 57(15): 156-162.
[15]	成立明，陈建新，陈瑞，陈志敏. 融合自监督单目图像深度估计的视觉里程计[J]. 计算机工程与应用, 2021, 57(15): 230-236.