基于三维Voronoi图划分的加权混合回归定位算法

doi:10.11959/j.issn.2096-3750.2022.00273

物联网学报 ›› 2022, Vol. 6 ›› Issue (2): 106-116.doi: 10.11959/j.issn.2096-3750.2022.00273

基于三维Voronoi图划分的加权混合回归定位算法

李芬芳¹, 党小超¹^,², 郝占军¹^,²

¹ 西北师范大学计算机科学与工程学院，甘肃兰州 730070
² 甘肃省物联网工程研究中心，甘肃兰州 730070

修回日期:2022-05-01 出版日期:2022-06-30 发布日期:2022-06-01
作者简介:李芬芳（1990− ），女，西北师范大学讲师，主要研究方向为机器学习、无线网络定位技术和无线感知技术等
党小超（1963− ），男，西北师范大学教授、硕士生导师，主要研究方向为物联网、传感器网络、无线感知技术等
郝占军（1979− ），男，博士，西北师范大学教授、硕士生导师，主要研究方向为位置服务、无线定位技术等
基金资助:
国家自然科学基金资助项目(61762079);甘肃省科技重点研发项目(20YF8GA048);甘肃省科技创新基地和人才计划项目(20JR10RA096);西北师范大学青年教师科研能力提升计划项目(NWNU-LKQN2019-28)

Weighted mixed regression localization method based on three-dimensional Voronoi diagram division

Fenfang LI¹, Xiaochao DANG¹^,², Zhanjun HAO¹^,²

¹ College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China
² Gansu Province Internet of Things Engineering Research Center, Lanzhou 730070, China

Revised:2022-05-01 Online:2022-06-30 Published:2022-06-01
Supported by:
The National Natural Science Foundation of China(61762079);The Key Science and Technology Development Program of Gansu Province(20YF8GA048);The Science and Technology Innovation Base and Talent Plan Program of Gansu Province(20JR10RA096);The Young Teachers' Scientific Research Ability Improvement Program of Northwest Normal University(NWNU-LKQN2019-28)

摘要/Abstract

摘要：

随着无线通信技术和感知技术的发展，基于无线传感器网络的各种技术应运而生，这些技术被广泛应用在智慧农业、智慧交通、消防救援等领域。节点定位技术是无线传感器网络的基础技术之一，位置信息是感知数据的一部分，它决定了下一步要采取的具体措施。由于三维空间定位环境的复杂性，将平面上的定位方法应用在三维空间会有一定的局限性。针对以上问题，研究了基于三维空间Voronoi图的加权混合回归定位算法WMR-SKR。该定位算法分为离线训练和在线测试两个阶段。根据网络中的锚节点对定位空间进行三维Voronoi图划分，离线训练阶段将锚节点和 Voronoi cell 顶点的坐标组成的序列作为训练集进行训练。在线测试阶段通过训练好的定位模型对网络中未知节点的坐标进行预测。仿真实验结果表明，所提算法可有效降低三维空间中的节点定位误差，同时有效提高节点定位速度。

关键词: 节点定位, Voronoi图划分, 加权混合回归, WMR-SKR

Abstract:

With the development of the wireless communication technology and sensing technology, various technologies based on wireless sensor networks are applied.These technologies are widely used in the fields of intelligent agriculture, intelligent transportation, fire rescue and so on.Node localization technology is one of the basic technologies of wireless sensor networks.Location information is a part of the sensing data, which determines the specific measures to be taken in the next step.Due to the complexity of the three-dimensional (3D) space localization environment, the application of the plane positioning method in 3D space will have some limitations.Aiming at above problems, the weighted hybrid regression location algorithm WMR-SKR based on a 3D Voronoi diagram was studied.The localization algorithm was divided into two stages: offline training and online testing.The 3D space was divided into Voronoi diagrams according to the anchor nodes in the network.In the offline training stage, the sequence composed of the coordinates of the anchor nodes and Voronoi cell vertices was used as the training set for training.In the online test stage, the coordinates of unknown nodes in the network were predicted through the trained localization model.Simulation results show that the WMR-SKR algorithm can effectively reduce the node localization error and improve the node localization speed in 3D space.

Key words: node localization, Voronoi diagram, weighted mixed regression, WMR-SKR

中图分类号:

TP391.9

李芬芳, 党小超, 郝占军. 基于三维Voronoi图划分的加权混合回归定位算法[J]. 物联网学报, 2022, 6(2): 106-116.

Fenfang LI, Xiaochao DANG, Zhanjun HAO. Weighted mixed regression localization method based on three-dimensional Voronoi diagram division[J]. Chinese Journal on Internet of Things, 2022, 6(2): 106-116.

图/表 9

图1

图2

表1

图3

图4

图5

图6

图7

图8

参考文献 34

[1]	MOHAMED R E , SALEH A I , ABDELRAZZAK M ,et al. Survey on wireless sensor network applications and energy efficient routing protocols[J]. Wireless Personal Communications, 2018,101(2): 10191055.
[2]	彭铎, 杨雅文, 高玉蔚 ,等. 基于多通信半径和麻雀搜索的节点定位算法[J]. 传感技术学报, 2021,34(11): 1523-1529.
	PENG D , YANG Y W , GAO Y W ,et al. Node localization algorithm based on multi-communication radius and sparrow search algorithm[J]. Chinese Journal of Sensors and Actuators, 2021,34(11): 1523-1529.
[3]	徐莎莎, 周芳, 李杨剑 ,等. 一种新的传感器节点分布式定位算法[J]. 西安电子科技大学学报, 2022,49(2): 1-9.
	XU S S , ZHOU F , LI Y J ,et al. New distributed positioning algorithm for sensor nodes[J]. Journal of Xidian University, 2022,49(2): 1-9.
[4]	HAN G J , JIANG J F , ZHANG C Y ,et al. A survey on mobile anchor node assisted localization in wireless sensor networks[J]. IEEE Communications Surveys ＆ Tutorials, 2016,18(3): 2220-2243.
[5]	唐德红, 王一多, 马新国 . 斯蒂芬森迭代改进 DV-Hop 的无线传感器节点定位[J]. 吉林大学学报(工学版), 2021: 1-7.
	TANG D H , WANG Y D , MA X G . Sensor node localization mechanism based on improved DV-Hop algorithm[J]. Journal of Jilin University (Engineering and Technology Edition), 2021: 1-7.
[6]	TOMIC S , BEKO M , DINIS R,etal . On target localization using combined RSS and AoA measurements[J]. Sensors (Basel,Switzerland), 2018,18(4): 1266.
[7]	HAN G J , YANG X , LIU L ,et al. A disaster management-oriented path planning for mobile anchor node-based localization in wireless sensor networks[J]. IEEE Transactions on Emerging Topics in Computing, 2020,8(1): 115-125.
[8]	刘云萍 . 无线传感网络中基于锚节点动态路径规划的节点定位算法研究[D]. 重庆:重庆邮电大学, 2020.
	LIU Y P . Research on node localization algorithm based on dynamic path planning of anchor node in wireless sensor networks[D]. Chongqing:Chongqing University of Posts and Telecommunications, 2020.
[9]	LI Q Y , CHU B Y , WU Z ,et al. RMDS:Ranging and multidimensional scaling-based anchor-free localization in large-scale wireless sensor networks with coverage holes[J]. International Journal of Distributed Sensor Networks, 2017,13(8): 155014771772465.
[10]	ZHANG L P , YANG Z Y , ZHANG S L ,et al. Three-dimensional localization algorithm of WSN nodes based on RSSI-TOA and single mobile anchor node[J]. Journal of Electrical and Computer Engineering, 2019:4043106.
[11]	TABAAM , DIOUC , SAADANER ,et al. LOS/NLOS identification based on stable distribution feature extraction and SVM classifier for UWB on-body communications[J]. Procedia Computer Science, 2014,32: 882-887.
[12]	KUMARR , KUMARS , SHUKLAD ,et al. Geometrical localization algorithm for three dimensional wireless sensor networks[J]. Wireless Personal Communications, 2014,79(1): 249-264.
[13]	WU J Z , YUAN J M , RUAN Y J ,et al. Optimal planning for energy stations and networks in distributed energy systems based on voronoi diagram and load characteristics[J]. Applied Sciences, 2021,11(16): 7526.
[14]	张勇, 黄杰, 徐科宇 . 基于PCA-LSSVR算法的WLAN室内定位方法[J]. 仪器仪表学报, 2015,36(2): 408-414.
	ZHANG Y , HUANG J , XU K Y . Indoor positioning algorithm for WLAN based on principal component analysis and least square support vector regression[J]. Chinese Journal of Scientific Instrument, 2015,36(2): 408-414.
[15]	陈飞彦, 田宇驰, 胡亮 . 物联网中基于KNN和BP神经网络预测模型的研究[J]. 计算机应用与软件, 2015,32(6): 127-129,202.
	CHEN F Y , TIAN Y C , HU L . Study on KNN and BP neural network-based prediction model in IoT[J]. Computer Applications and Software, 2015,32(6): 127-129,202.
[16]	党小超, 李芬芳, 郝占军 . Delaunay 三角剖分的节点模糊信息三维定位方法[J]. 计算机工程与应用, 2016,52(23): 115-122,243.
	DANG X C , LI F F , HAO Z J . Method of node's fuzzy information localization about Delaunay triangulation in three-dimensional space[J]. Computer Engineering and Applications, 2016,52(23): 115-122,243.
[17]	王继春, 黄刘生, 徐宏力 ,等. 基于Voronoi图的无需测距的无线传感器网络节点定位算法[J]. 计算机研究与发展, 2008,45(1): 119-125.
	WANG J C , HUANG L S , XU H L ,et al. A novel range free localization scheme based on voronoi diagrams in wireless sensor networks[J]. Journal of Computer Research and Development, 2008,45(1): 119-125.
[18]	李芬芳, 党小超, 郝占军 . 基于 Voronoi 图划分的节点模糊信息定位算法[J]. 计算机工程, 2019,45(1): 78-83,90.
	LI F F , DANG X C , HAO Z J . Node fuzzy information localization algorithm based on voronoi diagram partition[J]. Computer Engineering, 2019,45(1): 78-83,90.
[19]	LASLA N , DERHAB A , OUADJAOUT A ,et al. Half-symmetric lens based localization algorithm for wireless sensor networks[C]// Proceedings of 37th Annual IEEE Conference on Local Computer Networks. Piscataway:IEEE Press, 2012: 320-323.
[20]	SONG J , LIU M . A hidden Markov model approach for voronoi localization[C]// Proceedings of 2013 IEEE International Conference on Robotics and Biomimetics. Piscataway:IEEE Press, 2013: 462-467.
[21]	YANG X , LIU J . Sequence localization algorithm based on 3D voronoi diagram in wireless sensor network[J]. Applied Mechanics and Materials, 2014,644/645/646/647/648/649/650:4422-4426.
[22]	孙大洋, 钱志鸿, 韩梦飞 ,等. 无线传感器网络中多边定位的聚类分析改进算法[J]. 电子学报, 2014,42(8): 1601-1607.
	SUN D Y , QIAN Z H , HAN M F ,et al. Improving multilateration algorithm by cluster analysis in WSN[J]. Acta Electronica Sinica, 2014,42(8): 1601-1607.
[23]	汤文华, 傅明 . 基于SVM的WSN移动节点定位算法[J]. 计算机工程, 2012,38(22): 76-79,83.
	TANG W H , FU M . Localization algorithm of mobile nodes in WSN based on SVM[J]. Computer Engineering, 2012,38(22): 76-79,83.
[24]	蒋华, 蔡晨, 王慧娇 ,等. 基于改进加权最小二乘支持向量机的UWSN定位[J]. 计算机测量与控制, 2021,29(8): 250-254.
	JIANG H , CAI C , WANG H J ,et al. UWSN location based on improved weighted least squares support vector machine[J]. Computer Measurement ＆ Control, 2021,29(8): 250-254.
[25]	吴艳玲 . 一种基于局部信息最小二乘法的节点定位算法[J]. 吉林大学学报(理学版), 2017,55(4): 952-956.
	WU Y L . A node localization algorithm based on local information least square method[J]. Journal of Jilin University (Science Edition), 2017,55(4): 952-956.
[26]	ZHU F , WEI J F . Localization algorithm for large scale wireless sensor networks based on fast-SVM[J]. Wireless Personal Communications, 2017,95(3): 1859-1875.
[27]	毛科技, 范聪玲, 叶飞 ,等. 基于支持向量机的无线传感器网络节点定位算法[J]. 计算机研究与发展, 2014,51(11): 2427-2436.
	MAO K J , FAN C L , YE F ,et al. Node localization algorithm in wireless sensor networks based on SVM[J]. Journal of Computer Research and Development, 2014,51(11): 2427-2436.
[28]	闫燕 . 无线传感器网络三维定位精度优化方法研究[D]. 兰州:西北师范大学, 2020.
	YAN Y . An optimization method for three-dimensional location accuracy of wireless sensor network[D]. Lanzhou:Northwest Normal University, 2020.
[29]	赵银龙, 安胜彪 . 基于核化K-means和SVM分类回归的Wi-Fi室内定位算法[J]. 信息技术, 2018,42(1): 113-117.
	ZHAO Y L , AN S B . Wi-Fi indoor localization algorithm based on kernel K-means and SVM classification regression[J]. Information Technology, 2018,42(1): 113-117.
[30]	FANG X M , JIANG Z H , 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: 57-68.
[31]	曾碧, 毛勤 . 改进的室内三维模糊位置指纹定位算法[J]. 山东大学学报(工学版), 2015,45(3): 22-27.
	ZENG B , MAO Q . Improved indoor 3-D fuzzy position fingerprint localization algorithm[J]. Journal of Shandong University (Engineering Science), 2015,45(3): 22-27.
[32]	王瑞 . 基于模糊信息处理的传感器网络覆盖定位方法研究[D]. 西安:西安电子科技大学, 2009.
	WANG R . Study of coverage and localization methods based on fuzzy information processing in sensor networks[D]. Xi'an:Xidian University, 2009.
[33]	石柯, 陈洪生, 张仁同 . 一种基于支持向量回归的802.11无线室内定位方法[J]. 软件学报, 2014,25(11): 2636-2651.
	SHI K , CHEN H S , ZHANG R T.Indoor location method based on support vector regression in 802 . 11 wireless environments[J]. Journal of Software, 2014,25(11): 2636-2651.
[34]	周锦, 李炜, 金亮 ,等. 基于KNN-SVM算法的室内定位系统设计[J]. 华中科技大学学报(自然科学版), 2015,43(S1): 517-520.
	ZHOU J , LI W , JIN L ,et al. Indoor positioning system based on KNN-SVM algorithm[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2015,43(S1): 517-520.

参数	值
仿真区域长、宽/m	1 000
仿真区域高/m	50
传感器网络节点总数N	300
节点通信半径/m	50
锚节点占比	0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9
RBF核函数参数	1

基于三维Voronoi图划分的加权混合回归定位算法

Weighted mixed regression localization method based on three-dimensional Voronoi diagram division

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 34

相关文章 1

Metrics

推荐阅读 0