Please wait a minute...
浙江大学学报(工学版)  2019, Vol. 53 Issue (8): 1525-1535    DOI: 10.3785/j.issn.1008-973X.2019.08.011
计算机与控制工程     
基于Bregman散度的无线传感器网络定位
刘春生(),单洪*(),王斌,黄郡
国防科技大学 电子对抗学院,安徽 合肥 230037
Wireless sensor network localization via Bregman divergence
Chun-sheng LIU(),Hong SHAN*(),Bin WANG,Jun HUANG
College of Electronic Engineering, National University of Defense Technology, Hefei 230037, China
 全文: PDF(662 KB)   HTML
摘要:

现有算法难以处理脉冲噪声,导致无线传感器网络(WSN)中节点定位精度较低,为此提出基于Bregman散度的WSN定位算法. 该算法分为2个阶段:欧氏距离矩阵(EDM)恢复阶段和坐标映射阶段. 基于EDM的自然低秩性,将EDM恢复问题转化为噪声环境下的矩阵补全问题;采用L1,2范数显式平滑脉冲噪声,建立正则化矩阵补全模型;为了有效求解该模型,定义多元函数Bregman散度,将分裂Bregman迭代拓展到矩阵空间,结合交替最小化算法,得到EDM的估计;在此基础上,基于多维标度法对节点位置进行估计. 实验结果表明,在不同噪声条件下,该算法在保证高效性的同时,在定位精度和鲁棒性方面优于其他算法,特别是当采样率达到一定程度时,定位误差不到其他算法的1/4.

关键词: 无线传感器网络定位矩阵补全Bregman散度脉冲噪声    
Abstract:

The impulse noise is difficult to deal with by using the existing algorithms. A WSN localization algorithm based on the Bregman divergence was proposed to improve the node positioning accuracy of the wireless sensor network (WSN). The proposed algorithm is divided into two stages, the stage of Euclidean distance matrix (EDM) recovery and the stage of coordinates mapping. The problem of EDM recovery is transformed to an issue of matrix completion in a noisy environment, based on the natural low-rank character of the EDM. A regularized matrix completion model is established by using L1,2-norm explicit smoothing the pulse noise. To solve the model effectively, the multivariate function Bregman divergence was defined, then the split Bregman iteration was extended to the matrix space, and the alternating minimization method was combined to obtain the EDM estimator. Furthermore, node localization was available based on the multi-dimensional scaling method. Experiments demonstrate that under different noise conditions, the proposed algorithm outperforms other algorithms in terms of positioning accuracy and robustness while ensuring high efficiency. Notably, the localization error of the proposed algorithm was less than a quarter of those of other algorithms, when the sampling rate reached a certain level.

Key words: wireless sensor network    localization    matrix completion    Bregman divergence    impulse noise
收稿日期: 2017-06-23 出版日期: 2019-08-13
CLC:  TN 92  
通讯作者: 单洪     E-mail: the_springliu@163.com;HongShanWN@163.com
作者简介: 刘春生(1992—),男,博士生,从事无线网络研究. orcid.org/0000-0001-7476-7472. E-mail: the_springliu@163.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
刘春生
单洪
王斌
黄郡

引用本文:

刘春生,单洪,王斌,黄郡. 基于Bregman散度的无线传感器网络定位[J]. 浙江大学学报(工学版), 2019, 53(8): 1525-1535.

Chun-sheng LIU,Hong SHAN,Bin WANG,Jun HUANG. Wireless sensor network localization via Bregman divergence. Journal of ZheJiang University (Engineering Science), 2019, 53(8): 1525-1535.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2019.08.011        http://www.zjujournals.com/eng/CN/Y2019/V53/I8/1525

图 1  LBD_MDS算法与其他3种算法收敛情况的比较
图 2  不同噪声条件下欧式距离矩阵的恢复误差
图 3  信标节点数量对定位误差的影响
图 4  不同噪声条件下采样率对定位误差的影响
图 5  不同噪声条件下采样率对定位误差方差的影响
EDM 维度 算法 REs LEs t/s
100×100 LBD_MDS 1.298 7×10?2 3.538 9×10?2 1.416
IALM 7.322 8×10?2 1.635 1×10?1 3.619
OptSpace 2.251 6×10?1 5.807 1×10?1 4.730
ScGrassMC 7.850 9×10?2 2.311 8×10?1 1.391
200×200 LBD_MDS 8.711 1×10?4 3.684 4×10?3 6.746
IALM 3.413 0×10?3 6.771 8×10?2 13.211
OptSpace 8.178 8×10?2 3.229 1×10?1 17.066
ScGrassMC 8.929 0×10?3 5.417 5×10?2 2.865
500×500 LBD_MDS 8.243 4×10?5 7.195 4×10?4 49.334
IALM 6.697 3×10?4 9.545 0×10?3 144.020
OptSpace 1.117 0×10?3 1.541 8×10?2 151.890
ScGrassMC 8.378 9×10?4 1.155 0×10?2 23.648
表 1  不同规模WSN中各算法的性能比较
图 6  不同噪声条件下定位误差累积分布
图 7  噪声污染程度对算法性能的影响
1 ASSAF A E, ZAIDI S, AFFES S, et al Low-cost localization for multihop heterogeneous wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2016, 15 (1): 472- 484
doi: 10.1109/TWC.2015.2475255
2 XIAO F, LIU W, LI Z, et al Noise-tolerant wireless sensor networks localization via multi-norms regularized matrix completion[J]. IEEE Transactions on Vehicular Technology, 2018, 67 (3): 2409- 2419
doi: 10.1109/TVT.2017.2771805
3 FENG C, VALAEE S, AU W S A, et al. Localization of wireless sensors via nuclear norm for rank minimization [C]// Global Telecommunications Conference. Miami: IEEE, 2010: 1-5.
4 XIAO F, SHA C, CHEN L, et al. Noise-tolerant localization from incomplete range measurements for wireless sensor networks [C]// International Conference on Computer Communications. Kowloon: IEEE, 2015: 2794-2802.
5 NGUYEN T L, SHIN Y Matrix completion optimization for localization in wireless sensor networks for intelligent IoT[J]. Sensors, 2016, 16 (5): 722
doi: 10.3390/s16050722
6 SHANG Y, RUML W, ZHANG Y, et al. Localization from mere connectivity [C]// ACM International Symposium on Mobile Ad Hoc Networking and Computing. Annapolis: ACM, 2003: 201-212.
7 FANG X, JIANG Z, NAN L, et al Noise-aware localization algorithms for wireless sensor networks based on multidimensional scaling and adaptive Kalman filtering[J]. Computer Communications, 2017, 101 (3): 57- 68
8 BHASKAR S A Localization from connectivity: a 1-bit maximum likelihood approach[J]. IEEE/ACM Transactions on Networking, 2016, 24 (5): 2939- 2953
doi: 10.1109/TNET.2015.2495171
9 WANG M, ZHANG Z, TIAN X, et al. Temporal correlation of the RSS improves accuracy of fingerprinting localization [C]// International Conference on Computer Communications. San Francisco: IEEE, 2016: 1-9.
10 FANG X, JIANG Z, NAN L, et al Optimal weighted K-nearest neighbour algorithm for wireless sensor network fingerprint localization in noisy environment[J]. IET Communications, 2018, 12 (10): 1171- 1177
doi: 10.1049/iet-com.2017.0515
11 GUO X, CHU L, ANSARI N Joint localization of multiple sources from incomplete noisy Euclidean distance matrix in wireless networks[J]. Computer Communications, 2018, 122 (6): 20- 29
12 SINGH P, KHOSLA A, KUMAR A, et al Computational intelligence based localization of moving target nodes using single anchor node in wireless sensor networks[J]. Telecommunication Systems, 2018, 69 (3): 397- 411
doi: 10.1007/s11235-018-0444-2
13 ARORA S, SINGH S Node localization in wireless sensor networks using butterfly optimization algorithm[J]. Arabian Journal for Science and Engineering, 2017, 42 (8): 3325- 3335
doi: 10.1007/s13369-017-2471-9
14 SAHOTA H, KUMAR R Maximum-likelihood sensor node localization using received signal strength in multimedia with multipath characteristics[J]. IEEE Systems Journal, 2018, 12 (1): 506- 515
doi: 10.1109/JSYST.2016.2550607
15 XIAO F, CHEN L, SHA C, et al Noise tolerant localization for sensor networks[J]. IEEE/ACM Transactions on Networking, 2018, 26 (4): 1707- 1714
16 BI D, XIE Y, MA L, et al Multifrequency compressed sensing for 2-D near-field synthetic aperture radar image reconstruction[J]. IEEE Transactions on Instrumentation and Measurement, 2017, 66 (4): 777- 791
doi: 10.1109/TIM.2017.2654578
17 CAI J F, OSHER S, SHEN Z Linearized Bregman iterations for frame-based image deblurring[J]. SIAM Journal on Imaging Sciences, 2009, 2 (1): 226- 252
doi: 10.1137/080733371
18 HUA X, FAN H, CHENG Y, et al Information geometry for radar target detection with total Jensen-Bregman divergence[J]. Entropy, 2018, 20 (4): 256
doi: 10.3390/e20040256
19 FISCHER A Quantization and clustering with Bregman divergences[J]. Journal of Multivariate Analysis, 2010, 101 (9): 2207- 2221
doi: 10.1016/j.jmva.2010.05.008
20 BRèGMAN L M The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming[J]. USSR Computational Mathematics and Mathematical Physics, 1967, 7 (3): 200- 217
doi: 10.1016/0041-5553(67)90040-7
21 FU X, SHA C, LEI C, et al Localization algorithm for wireless sensor networks via norm regularized matrix completion[J]. Journal of Computer Research and Development, 2016, 53 (1): 216- 227
22 GOLDSTEIN T, OSHER S The split Bregman method for L1-regularized problems[J]. SIAM Journal on Imaging Science, 2009, 2 (2): 323- 343
doi: 10.1137/080725891
23 PARIKH N, BOYD S Proximal algorithms[J]. Foundations and Trends in Optimization, 2014, 1 (3): 127- 239
doi: 10.1561/2400000003
24 BRUCKSTEIN A M, DONOHO D L, ELAD M From sparse solutions of systems of equations to sparse modeling of signals and images[J]. SIAM Review, 2009, 51 (1): 34- 81
doi: 10.1137/060657704
25 COMBETTES P L Signal recovery by proximal forward-backward splitting[J]. Multiscale Modeling and Simulation, 2005, 4 (4): 1168- 1200
doi: 10.1137/050626090
26 CAI J F, CANDES E J, et al A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20 (4): 1956- 1982
doi: 10.1137/080738970
27 GONG P, YE J, ZHANG C. Robust multi-task feature learning [C]// International Conference on Knowledge Discovery and Data Mining. Beijing: ACM, 2012: 895-903.
28 LIN Z, LIU R, SU Z. Linearized alternating direction method with adaptive penalty for low rank representation [C]// International Conference on Neural Information Processing Systems. Granada: Curran Associates Inc, 2011: 612-620.
29 KESHAVAN R H, OH S, MONTANARI A Matrix completion from a few entries[J]. IEEE Transactions on Information Theory, 2010, 56 (6): 2980- 2998
doi: 10.1109/TIT.2010.2046205
[1] 郑英杰,吴松荣,韦若禹,涂振威,廖进,刘东. 基于目标图像FCM算法的地铁定位点匹配及误报排除方法[J]. 浙江大学学报(工学版), 2021, 55(3): 586-593.
[2] 马鑫,梁新武,蔡纪源. 基于点线特征的快速视觉SLAM方法[J]. 浙江大学学报(工学版), 2021, 55(2): 402-409.
[3] 曾煌尧,李丹丹,马严,丛群. 园区网风险账号评估方法[J]. 浙江大学学报(工学版), 2020, 54(9): 1761-1767.
[4] 黄文锦,黄妙华. 激光雷达与路侧摄像头的双层融合协同定位[J]. 浙江大学学报(工学版), 2020, 54(7): 1369-1379.
[5] 桑高丽,王国滨,朱蓉,宋佳佳. 基于级联形状回归的多视角人脸特征点定位[J]. 浙江大学学报(工学版), 2019, 53(7): 1374-1379.
[6] 张政,周学军,王希晨,周媛媛. 缆系水下信息网恒流远供系统短路故障诊断及区间定位方法[J]. 浙江大学学报(工学版), 2019, 53(6): 1190-1197.
[7] 席志鹏,楼卓,李晓霞,孙艳,杨强,颜文俊. 集中式光伏电站巡检无人机视觉定位与导航[J]. 浙江大学学报(工学版), 2019, 53(5): 880-888.
[8] 成翔昊,达飞鹏,汪亮. 基于融合约束局部模型的三维人脸特征点定位[J]. 浙江大学学报(工学版), 2019, 53(4): 770-776.
[9] 王凯, 岳泊暄, 傅骏伟, 梁军. 基于生成对抗网络的图像恢复与SLAM容错研究[J]. 浙江大学学报(工学版), 2019, 53(1): 115-125.
[10] 袁琪, 马春光, 姚建盛, 于海涛. 基于w-BIBD的异构传感网密钥预分配方案[J]. 浙江大学学报(工学版), 2019, 53(1): 126-136.
[11] 李劲林, 王佳斌, 何闻. 非接触式定位隔振平台机电联合仿真分析[J]. 浙江大学学报(工学版), 2019, 53(1): 146-157.
[12] 刘洲洲, 李士宁, 李彬, 王皓, 张倩昀, 郑然. 基于弹性碰撞优化算法的传感云资源调度[J]. 浙江大学学报(工学版), 2018, 52(8): 1431-1443.
[13] 柯显信, 张文朕, 杨阳, 温雷. 仿人机器人多传感器定位系统[J]. 浙江大学学报(工学版), 2018, 52(7): 1247-1252.
[14] 汤雪萍, 鲁天龙, 黄平捷, 侯迪波, 张光新. 行为规划和浓度梯度法联合的河道污染源追踪定位方法[J]. 浙江大学学报(工学版), 2018, 52(3): 543-551.
[15] 赖晓翰, 文昊翔, 陈隆道. 潮间带无线传感器网络路由算法[J]. 浙江大学学报(工学版), 2018, 52(12): 2414-2422.