ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (1): 216-227.doi: 10.7544/issn1000-1239.2016.20148087

• 网络技术 • 上一篇    

基于范数正则化矩阵补全的无线传感网定位算法

肖甫1,2,3,沙朝恒1,陈蕾1,2,孙力娟1,2,3,王汝传1,2,3   

  1. 1(南京邮电大学计算机学院 南京 210003); 2(江苏省无线传感网高技术研究重点实验室(南京邮电大学) 南京 210003); 3(宽带无线通信与传感网技术教育部重点实验室(南京邮电大学) 南京 210003) (xiaof@njupt.edu.cn)
  • 出版日期: 2016-01-01
  • 基金资助: 
    国家自然科学基金项目(61373137,61373017,61171053,61373139);江苏省高校自然科学研究计划重大项目(14KJA520002);江苏省“六大人才高峰”基金项目(2013-DZXX-014);江苏省“青蓝工程”项目;江苏高校优势学科建设工程项目-信息与通信工程

Localization Algorithm for Wireless Sensor Networks via Norm Regularized Matrix Completion

Xiao Fu1,2,3, Sha Chaoheng1, Chen Lei1,2, Sun Lijuan1,2,3, Wang Ruchuan1,2,3   

  1. 1(School of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing 210003); 2(Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks (Nanjing University of Posts and Telecommunications), Nanjing 210003); 3(Key Laboratory of Broadband Wireless Communication and Sensor Network Technology (Nanjing University of Posts and Telecommunications), Ministry of Education, Nanjing 210003)
  • Online: 2016-01-01

摘要: 节点定位是实现无线传感器网络(wireless sensor networks, WSNs)应用的重要前提之一.针对传统基于测距的定位方法需要大量节点距离信息以及多径效应、噪声干扰等导致的节点测距误差问题,提出了一类基于L1范数正则化矩阵补全(L1-norm regularized matrix completion, L1NRMC)的WSNs节点定位方法.该方法基于传感网节点间距离矩阵低秩特性,将部分采样信息下的距离恢复问题建模为稀疏野值噪声(outlier)情形下的矩阵补全问题,然后采用交替方向乘子法(alternating direction method of multipliers, ADMM)结合算子分裂技术(operator splitting technology)对该问题进行求解,所设计的非精确L1范数正则化矩阵补全(InExact-L1NRMC)算法不仅能显式解析采样矩阵中的稀疏野值噪声,也可隐式平滑常见的高斯随机噪声.仿真结果表明:相比已有的同类定位方法,该算法只需进行部分测距采样即可实现精准的节点定位,且对各类测距噪声具有很好的抗干扰能力,适用于资源受限的WSNs.

关键词: 无线传感器网络, 定位, 野值噪声, 矩阵补全, L1范数正则化

Abstract: Localization is one of the important preconditions for wireless sensor networks (WSNs) applications.Traditional range-based localization algorithms need large amounts of pair-wise distance measurements between sensor nodes.However, noise and data missing are inevitable in distance ranging, which may degrade localization accuracy drastically. To address this challenge, a novel localization algorithm for WSNs based on L1-norm regularized matrix completion (L1NRMC) is proposed in this paper. By utilizing the natural low rank feature of the Euclidean distance matrix (EDM) between nodes, the recovery of partly sampled noisy distance matrix is formulated as an L1-norm regularized matrix completion problem, which is solved by alternating direction method of multipliers (ADMM) and operator splitting technology.Based on the reconstructed EDM, the classical MDS-MAP algorithm is applied to obtain the coordinates of all the unknown nodes.This algorithm can not only detect and remove outliers, but also smooth the common Gaussian noise implicitly. Simulation results demonstrate that compared with traditional node localization algorithms, our algorithm achieves high accuracy from only small fraction of distance measurements and resists various types of ranging noise, which makes our algorithm suitable for resource-limited WSNs.

Key words: wireless sensor networks (WSNs), localization, outlier, matrix completion, L1-norm regularization

中图分类号: