一种新的传感器节点分布式定位算法

doi:10.19665/j.issn1001-2400.2022.02.011

西安电子科技大学学报 ›› 2022, Vol. 49 ›› Issue (2): 89-96.doi: 10.19665/j.issn1001-2400.2022.02.011

一种新的传感器节点分布式定位算法

徐莎莎¹(),周芳²(),李杨剑¹(),蒋俊正^1,³()

1.桂林电子科技大学信息与通信学院,广西壮族自治区桂林 541004
2.桂林电子科技大学生命与环境科学学院,广西壮族自治区桂林 541004
3.桂林电子科技大学广西无线宽带通信与信号处理重点实验室,广西壮族自治区桂林 541004

收稿日期:2020-09-06 出版日期:2022-04-20 发布日期:2022-05-31
通讯作者: 周芳
作者简介:徐莎莎(1998—),女,桂林电子科技大学硕士研究生,E-mail: 19022201050@mails.guet.edu.cn;|李杨剑(1993—),男,桂林电子科技大学硕士研究生,E-mail: 907383163@qq.com;|蒋俊正(1983—),男,教授,E-mail: jzjiang@guet.edu.cn
基金资助:
国家自然科学基金(61761011);广西自然科学基金(2017GXNSFAA198173)

New distributed positioning algorithm for sensor nodes

XU Shasha¹(),ZHOU Fang²(),LI Yangjian¹(),JIANG Junzheng^1,³()

1. School of Information and Communication,Guilin University of Electronic Technology,Guilin 541004,China
2. School of Life and Environmental Sciences,Guilin University of Electronic Technology,Guilin 541004,China
3. Guangxi Key Laboratory of Wireless Wideband Communication and SignalProcessing, Guilin University of Electronic Technology,Guilin 541004,China

Received:2020-09-06 Online:2022-04-20 Published:2022-05-31
Contact: Fang ZHOU

摘要/Abstract

摘要：

大规模无线传感器网络中节点定位问题可以归结为高度非线性非凸的优化问题。该问题在大规模无线传感器网络中难以直接求解,因此提出了一种新的传感器节点分布式定位算法。首先将大规模无线传感器网络构成的全局无向图分解为一系列部分重叠的子图,进而将全局的优化问题分解为一系列小规模的子图内优化问题,每个子图内的优化问题可以独立进行迭代求解。新的传感器节点分布式定位算法每步迭代包含两个步骤,首先使用Barzilai-Borwein梯度法估计出划分好的部分重叠子图中节点的位置,使用的Barzilai-Borwein梯度法具备收敛速度较快,计算复杂度较低的特点,然后再对不同部分重叠的子图内的同一个传感器节点进行融合求平均。通过理论分析和仿真结果表明,新的传感器节点分布式定位算法与已有算法相较,具有较高的扩展性,在大规模无线传感器网络中有较高的定位精度,能满足大规模的无线传感器网络节点的定位需求。

关键词: 无线传感器网络, 定位, 分布式算法, 图模型, Barzilai-Borwein梯度法

Abstract:

The node localization problem in large scale wireless sensor networks can be formulated into a highly nonlinear nonconvex optimization problem which is hard to solve directly in large scale sensor networks.This paper proposes a new distributed localization algorithm to solve this problem.First,the global undirected graph composed of the large scale wireless sensor network is decomposed into a series of partially overlapping subgraphs,and then the global optimization problem is decomposed into a series of small scale subproblems for iterative solutions.The optimization problem in each subgraph can be solved iteratively independently.The new distributed localization algorithm for sensor nodes consists of two steps in each iteration,First,the Barzilai-Borwein gradient method is used to estimate the location of the node in the divided partially overlapping subgraph.The gradient method has a low computational cost and greatly speeds up the convergence.Second,the same sensor nodes in different partially overlapping subgraphs are fused and averaged.Theoretical analysis and simulation results show that compared with the existing methods,the proposed new distributed localization algorithm has a higher scalability and localization accuracy in large scale wireless sensor networks,and can be used for localization in large scale sensor networks.

Key words: wireless sensor networks, localization, distributed algorithm, graph model, Barzilai-Borwein gradient method

中图分类号:

TN911.7

徐莎莎,周芳,李杨剑,蒋俊正. 一种新的传感器节点分布式定位算法[J]. 西安电子科技大学学报, 2022, 49(2): 89-96.

XU Shasha,ZHOU Fang,LI Yangjian,JIANG Junzheng. New distributed positioning algorithm for sensor nodes[J]. Journal of Xidian University, 2022, 49(2): 89-96.

图/表 5

图1

表1

图2

表2

文中算法与文献[5,7-8]算法在不同参数下实验结果对比"

参数设置					$e ¯$
N	p	R	τ₁	τ₂	文中算法	文献[5]	文献[7]	文献[8]
100	0.15	0.40	0.10	0	0.010 0	0.010 7	0.089 2	0.074 0
100	0.15	0.40	0.10	0.10	0.022 6	0.053 6	0.090 0	0.095 1
200	0.15	0.20	0.10	0	0.006 5	0.009 1	0.048 7	0.031 4
200	0.15	0.20	0.10	0.10	0.024 6	0.034 5	0.053 8	0.043 1
500	0.15	0.15	0.10	0	0.005 4	*	0.028 0	0.014 7
500	0.15	0.15	0.10	0.10	0.019 5	*	0.035 3	0.029 5
800	0.15	0.13	0.10	0	0.004 0	*	0.029 9	0.015 4
800	0.15	0.13	0.10	0.10	0.016 8	*	0.035 1	0.026 1
1 000	0.15	0.11	0.10	0	0.004 1	*	0.021 4	0.011 0
1 000	0.15	0.11	0.10	0.10	0.017 0	*	0.027 3	0.024 8

表2

图3

参考文献 14

[1]	LI X, LI D, WAN J, et al. A Review of Industrial Wireless Networks in the Context of Industry 4.0[J]. Wireless Networks, 2017, 23(1):23-41. doi: 10.1007/s11276-015-1133-7
[2]	ALHAJRI M, GOIAN A, DARWEESH M, et al. Accurate and Robust Localization Techniques for Wireless Sensor Networks(2018)[J/OL].[2018-06-14]. https://arxiv.org/abs/1806.05765.pdf.
[3]	GIVENS R M, KINCAID R K, MAO W, et al. Mixed-Weight Open Locating-Dominating Sets(2018)[C/OL].[2018-06-01]. https://core.ac.uk/display/235415115.pdf.
[4]	YANG X, WANG X, WANG W. An Improved Centroid Localization Algorithm for WSN(2018)[C/OL].[2018-12-16]. https://ieeexplore.ieee.org/document/8740471.pdf.
[5]	赵海兵, 蒋俊正. 基于图模型的传感器节点定位方法[J]. 桂林电子科技大学学报, 2019, 39(1):28-34.
	ZHAO Haibing, JIANG Junzheng. A Method for Sensor Node Localization Based on Graph Model[J]. Journal of Guilin University of Electronic Technology, 2019, 39(1):28-34.
[6]	BISWAS P, LIANG T C, TOH K C, et al. Semidefinite Programming Approaches for Sensor Network Localization with Noisy Distance Measurements[J]. IEEE Transactions on Automation Science and Engineering, 2006, 3(4):360-371. doi: 10.1109/TASE.2006.877401
[7]	SRIRANGARAJAN S, TEWFIK A, LUO Z Q. Distributed Sensor Network Localization Using SOCP Relaxation[J]. IEEE Transactions on Wireless Communications, 2008, 7(12):4886-4895. doi: 10.1109/T-WC.2008.070241
[8]	SOARES C, XAVIER J, GOMES J. Simple and Fast Convex Relaxation Method for Cooperative Localization in Sensor Networks Using Range Measurements[J]. IEEE Transactions on Signal Processing, 2015, 63(17):4532-4543. doi: 10.1109/TSP.2015.2454853
[9]	SANYAL R, JAISWAL M, CHAUDHURY K N. On A Registration-Based Approach to Sensor Network Localization[J]. IEEE Transactions on Signal Processing, 2017, 65(20):5357-5367. doi: 10.1109/TSP.2017.2726990
[10]	蒋俊正, 赵海兵. 基于超级节点的分布式传感器节点定位算法[J]. 控制与决策, 2020, 35(12):2898-2906.
	JIANG Junzheng, ZHAO Haibing. A Distributed Sensor Node Localization Algorithm Based on Super Nodes[J]. Control and Decision, 2020, 35(12):2898-2906.
[11]	TOMIC S, BEKO M, DINIS R, et al. Efficient Estimator for Distributed RSS-Based Localization in Wireless Sensor Networks[C]// 2015 International Wireless Communications and Mobile Computing Conference.Piscataway:IEEE, 2015:1266-1271.
[12]	李俊. 无线传感器网络定位及匹配算法的研究[D]. 西安: 西安电子科技大学, 2019.
[13]	RAYDAN M, SVAITER B F. Relaxed Steepest Descent and Cauchy-Barzilai-Borwein Method[J]. Computational Optimization and Applications, 2002, 21(2):155-167. doi: 10.1023/A:1013708715892
[14]	BARZILAI J, BORWEIN J M. Two-Point Step Size Gradient Methods[J]. IMA Journal of Numerical Analysis, 1988, 8(1):141-148. doi: 10.1093/imanum/8.1.141

参数名称	符号或数值	备注
平面区域	[-0.5,0.5]²	采用与参考文献[5,7]相同的分布区域
节点规模	m+n	采用MATLAB生成随机均匀分布的m个LA节点和n个LU节点
LA节点所占比例	p=m/(m+n)	在WSN中,考虑到部署成本的问题,一般LA节点所占比例较小
距离噪声因子	τ₁	仿真时用于控制距离噪声的强度
LA节点位置噪声因子	τ₂	仿真时用于控制LA节点位置的噪声强度
通信半径	R	选择合理值,使得算法可以收敛并控制每个子图内的节点数目不要太多

[1]	孙泽宇,兰岚,曾操,廖桂生. 一种面向最小能耗自适应汇聚路由判定算法[J]. 西安电子科技大学学报, 2022, 49(2): 11-20.
[2]	李明,胡江平,曹晓莉. 异构传感网成本优化的节点部署策略[J]. 西安电子科技大学学报, 2021, 48(4): 11-19.
[3]	秦宁宁,吴忆松,杨乐. 动态模糊匹配下的多元相似度定位算法[J]. 西安电子科技大学学报, 2021, 48(4): 27-35.
[4]	丁硕,杨海彦,杨旭海,张喆,赵坤娟. 二阶电离层延迟对GPS PPP时间传递的影响[J]. 西安电子科技大学学报, 2021, 48(4): 50-56.
[5]	王平,江雨泽,赵光辉. 目标检测的多尺度定位提升算法[J]. 西安电子科技大学学报, 2021, 48(3): 85-90.
[6]	秦宁宁,王超. 时序测量信息触发的递归贝叶斯定位算法[J]. 西安电子科技大学学报, 2020, 47(4): 10-17.
[7]	周杰,徐梦颖,王娇娇,卢毅. 认知无线传感器网络频谱分配的一种改进方法[J]. 西安电子科技大学学报, 2020, 47(3): 80-85.
[8]	黄影,华雨晴. 能量与路径约束的无线传感网络路由优化[J]. 西安电子科技大学学报, 2020, 47(3): 113-120.
[9]	杨杰,蒋俊正. 利用联合图模型的传感器网络数据修复方法[J]. 西安电子科技大学学报, 2020, 47(1): 44-51.
[10]	田强,冯大政,胡豪爽. 一种TOA联合同步与定位的CWLS算法[J]. 西安电子科技大学学报, 2019, 46(5): 1-7.
[11]	王博远,刘学林,蔚保国,贾瑞才,甘兴利,黄璐. WiFi指纹定位中改进的加权k近邻算法[J]. 西安电子科技大学学报, 2019, 46(5): 41-47.
[12]	田强,冯大政,李进,胡豪爽. 一种利用声音能量的两步SDR定位算法[J]. 西安电子科技大学学报, 2019, 46(4): 16-21.
[13]	甄岩,赵虎. 层次型软件定义无线传感器网络资源调度策略[J]. 西安电子科技大学学报, 2019, 46(4): 87-98.
[14]	卢毅,周杰,万连城. 一种无线传感器网络二维目标覆盖的改进方法[J]. 西安电子科技大学学报, 2019, 46(2): 101-106.
[15]	周成,满欣,周志文. 一种利用MIMO雷达的CWLS目标定位算法[J]. 西安电子科技大学学报, 2019, 46(1): 124-129.

一种新的传感器节点分布式定位算法

New distributed positioning algorithm for sensor nodes

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 14

相关文章 15

Metrics

本文评价

推荐阅读 10