面向非完全序列的水下三维传感网定位算法

doi:10.11772/j.issn.1001-9081.2017071968

计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 31-37.DOI: 10.11772/j.issn.1001-9081.2017071968

• 2017年全国开放式分布与并行计算学术年会(DPCS 2017)论文 • 上一篇下一篇

面向非完全序列的水下三维传感网定位算法

车迪, 牛强

中国矿业大学计算机科学与技术学院, 江苏徐州 221116

收稿日期:2017-08-11 修回日期:2017-08-25 出版日期:2018-01-10 发布日期:2018-01-22
通讯作者: 车迪
作者简介:车迪(1994-),女,江苏徐州人,硕士研究生,主要研究方向:传感网、海洋观测网;牛强(1974-),男,辽宁沈阳人,教授,博士,主要研究方向:机器学习、数据挖掘。
基金资助:
国家重点研发计划项目（2016YFC060908）；国家自然科学基金资助项目（51674255）；江苏省产学研前瞻性联合研究项目（BY2014028-09）。

Non-full sequence-based localization algorithm for 3D underwater sensor networks

CHE Di, NIU Qiang

School of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221116, China

Received:2017-08-11 Revised:2017-08-25 Online:2018-01-10 Published:2018-01-22
Supported by:
This work is partially supported by the National Key Research and Development Program of China (2016YFC060908), the National Natural Science Foundation of China (51674255), the Production-Study-Research Joint Prospective Research Project of Jiangsu Province (BY2014028-09).

摘要/Abstract

摘要： 针对三维空间节点定位精度低以及算法复杂度高的问题，提出一种面向非完全序列的水下三维传感网定位（NFSL）算法。该算法区别于传统基于序列定位算法，考虑更切实际的信标节点通信范围非全网覆盖的情况。首先，利用3D Voronoi图对三维定位空间进行区域划分，并确定虚拟信标节点以及其阶次序列；然后，根据由接收的信号强度指示（RSSI）所得的未知节点序列与信标节点序列的阶次相关系数得到"最邻近"信标节点并构建最邻近序列表；其次，设计针对非等长序列相似度的算法并利用该算法得到未知节点的非完全序列与最邻近序列表中各序列的阶次相关系数；最后，将该阶次相关系数作为权重实现对未知节点位置的加权估计。仿真实验以信标节点比例、通信半径、节点总数以及网络规模作为变量对NFSL与DV-Hop和质心算法的定位精度进行比较，仿真结果证明了该算法的有效性，且其定位精度随信标节点数的增加而大幅提高，与传统定位算法相比该算法定位精度最大可提高约23%。

关键词: 水下传感器网络, 定位, 非完全序列, 加权估计, 3D Voronoi图

Abstract: Aiming at the problems of low accuracy and high complexity of localization algorithm in three-dimensional space, a Non-Full Sequence-based Localization (NFSL) algorithm for 3D underwater sensor networks was proposed. Different from traditional sequence-based localization algorithms, a more realistic situation where communication range of beacon nodes is not entire network was taken into consideration by NFSL. Firstly, 3D Voronoi diagram was used to divide the 3D location space and thus virtual beacon nodes as well as their rank sequences were determined. Secondly, the nearest beacon node was obtained according to the rank correlation coefficient between the unknown node sequence based on Received Signal Strength Indication (RSSI) and the beacon node sequence, and the nearest sequence table was constructed. Next, an algorithm which aimed at the similarity of sequences with unequal lengths was designed and utilized to obtain the rank correlation coefficients between the non-full sequence of unknown nodes and each sequence in the nearest sequence table. Finally, the weighted estimation of the unknown node's location was realized by taking the rank correlation coefficient as the weight. In simulation experiments, the localization accuracy of NFSL was compared with that of DV-Hop and Centroid by taking the ratio of beacon nodes, communication range, total number of nodes and network scale as variables. The extensive simulation results verified the effectiveness of the proposed algorithm. Besides, its localization accuracy significantly improves with the increasing number of beacon nodes. Compared with traditional localization algorithms, the localization accuracy of NFSL is improved by as much as 23%.

Key words: underwater sensor network, localization, non-full sequence, weighted estimation, 3D Voronoi diagram

中图分类号:

TP311
TP393

车迪, 牛强. 面向非完全序列的水下三维传感网定位算法[J]. 计算机应用, 2018, 38(1): 31-37.

CHE Di, NIU Qiang. Non-full sequence-based localization algorithm for 3D underwater sensor networks[J]. Journal of Computer Applications, 2018, 38(1): 31-37.

参考文献

[1] DU X D, JI J T, YAN D P. Application research of wireless sensor network in intelligent transportation system[J]. Advanced Materials Research, 2010, 108/109/110/111:1170-1175.
[2] LIU L, WU X, ZHU Z, et al. A localization algorithm based on beacon error problem in underwater wireless sensor network[C]//Proceedings of the 15th IEEE International Conference on Communication Technology. Piscataway, NJ:IEEE, 2013:478-482.
[3] WALDMEVER M, TAN H P, SEAH W K G. Multi-stage AUV-aided localization for underwater wireless sensor networks[C]//Proceedings of the 25th IEEE International Conference on Advanced Information Networking and Applications Workshops. Washington, DC:IEEE Computer Society, 2011:908-913.
[4] BAHL P, PADMANABHAN V N. RADAR:an in-building RF-based user location and tracking system[C]//Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ:IEEE, 2000:775-784.
[5] 肖竹,谭光华,李仁发,等.无线传感器网络中基于超宽带的TOA/AOA联合定位研究[J].计算机研究与发展,2013,50(3):453-460.(XIAO Z, TAN G H, LI R F, et al. Joint TOA/AOA localization based on UWB for wireless sensor networks[J]. Journal of Computer Research and Development, 2013, 50(3):453-460.)
[6] 吴绍华,张钦宇,张乃通.UWB无线传感器网络中基于匹配滤波检测的TOA估计[J].软件学报,2009,20(11):3010-3022.(WU S H, ZHANG Q Y, ZHANG N T. TOA estimation based on match-filtering detection for UWB wireless sensor networks[J]. Journal of Software, 2009, 20(11):3010-3022.)
[7] 陈鸿龙,李鸿斌,王智.基于TDoA测距的传感器网络安全定位研究[J].通信学报,2008,29(8):11-21.(CHEN H L, LI H B, WANG Z. Research on TDOA-based secure localization for wireless sensor networks[J]. Journal on Communications, 2008, 29(8):11-21.)
[8] ADEMUWAGUN A, FABIO V. Reach centroid localization algorithm[J]. Wireless Sensor Network, 2017, 9:87-101.
[9] HOSSEINIRAD S M, POURDEILAMI J, NIAZI M, et al. On improving APIT algorithm for better localization in WSN[J]. Journal of AI & Data Mining, 2013, 2(2):97-104.
[10] ZHANG A, YE X, HU H, et al. Improved DV-HOP positioning algorithm based on one-hop subdivision and average hopping distance modification[J]. Chinese Journal of Scientific Instrument, 2012, 33(11):2552-2559.
[11] YEDAVALLI K, KRISHNAMACHARI B. Sequence-based localization in wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2007, 7(1):81-94.
[12] 刘志华,陈嘉兴,陈霄凯.无线传感器网络中序列定位新算法的研究[J].电子学报,2010,38(7):1552-1556.(LIU Z H, CHEN J X, CHEN X K. A new algorithm research of sequence-based localization technology in wireless sensor networks[J]. Acta Electronica Sinica, 2010, 38(7):1552-1556.)
[13] 裴忠民,邓志东,徐硕,等.一种基于N-最优阶次序列的无线传感器网络节点定位方法[J].自动化学报,2010,36(2):199-207.(PEI Z M, DENG Z D, XU S, et al. A new localization method for wireless sensor network nodes based on N-best rank sequence[J]. Acta Automatica Sinica, 2010, 36(2):199-207.)
[14] 刘影,钱志鸿,孙大洋.基于参考点序列的无线传感器网络节点定位算法[J].吉林大学学报(工学版),2012,42(2):489-493.(LIU Y, QIAN Z H, SUN D Y. Node localization scheme for wireless sensor networks based on reference node sequence[J]. Journal of Jilin University (Engineering and Technology Edition), 2012, 42(2):489-493.)
[15] LIU J, YAN F, YANG X. 3D localization algorithm based on Voronoi diagram and rank sequence in wireless sensor network[J]. Scientific Programming, 2017, 2017(4):Article No. 4.
[16] ZHONG Z, HE T. RSD:a metric for achieving range-free localization beyond connectivity[J]. IEEE Transactions on Parallel & Distributed Systems, 2011, 22(11):1943-1951.
[17] ALMASHOR M, KHALIL I. Reducing network load in large-scale, peer-to-peer virtual environments with 3D Voronoi diagrams[C]//Proceedings of the 17th International Conference on High Performance Computing. Washington, DC:IEEE Computer Society, 2010:1-10.
[18] HWANG G J, ARUL J M, LIN E, et al. Design and multithreading implementation of the wave-front algorithm for constructing Voronoi diagrams[C]//ICA3PP:Proceedings of the 6th International Conference on Algorithms and Architectures for Parallel Processing. Berlin:Springer, 2005:257-266.
[19] LIU J Y, LIU S. A survey on applications of Voronoi diagrams[J]. Journal of Engineering Graphics, 2004, 25(2):125-132.
[20] DU Q, GUNZBURGER M, JU L L. Advances in studies and applications of centroidal Voronoi tessellations[J]. Numerical Mathematics:Theory, Methods and Applications, 2010, 3(2):119-142.
[21] 陈嘉兴,刘志华.无线传感器网络节点的三维序列内心定位算法[J].南京理工大学学报(自然科学版),2011, 35(3):371-375.(CHEN J X, LIU Z H. 3D Sequences and incenters localization algorithm for nodes in WSN[J]. Journal of Nanjing University of Science & Technology, 2011, 35(3):371-375.)
[22] 胡敏.基于阶次序列加权的无线传感器定位算法[J].计算机工程与应用,2014,50(10):116-119.(HU M. Node localization algorithm of wireless sensor networks based on optimal weighted rank sequences[J]. Computer Engineering and Applications, 2014, 50(10):116-119.)
[23] YANG X, LIU J. Sequence localization algorithm based on 3D Voronoi diagram in wireless sensor network[J]. Applied Mechanics & Materials, 2014, 644-650:4422-4426.

面向非完全序列的水下三维传感网定位算法

Non-full sequence-based localization algorithm for 3D underwater sensor networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	栾佳宁, 张伟, 孙伟, 张奥, 韩冬. 基于二维码视觉与激光雷达融合的高精度定位算法[J]. 计算机应用, 2021, 41(5): 1484-1491.
[2]	张齐林, 李方伟, 王明月. 基于时间反演的到达时间定位[J]. 计算机应用, 2021, 41(3): 820-824.
[3]	惠飞, 邢美华, 郭静, 唐书宇. 基于车车通信的前向碰撞预警策略[J]. 计算机应用, 2021, 41(2): 498-503.
[4]	孙琳, 袁玉波. 基于人眼状态的瞌睡识别算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3213-3218.
[5]	付豪, 徐和根, 张志明, 齐少华. 动态场景下基于语义和光流约束的视觉同步定位与地图构建[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3337-3344.
[6]	郑思诚, 孔令华, 游通飞, 易定容. 动态环境下基于深度学习的语义SLAM算法[J]. 计算机应用, 2021, 41(10): 2945-2951.
[7]	张驰, 李铸洪, 刘舟, 沈未名. 基于场景图划分的无人机影像定位算法[J]. 计算机应用, 2021, 41(10): 3004-3009.
[8]	韩鑫, 余永维, 杜柳青. 基于改进单次多框检测算法的机器人抓取系统[J]. 计算机应用, 2020, 40(8): 2434-2440.
[9]	张健铭, 施元昊, 徐正蓺, 魏建明. 基于误差预测的自适应UWB/PDR融合定位算法[J]. 计算机应用, 2020, 40(6): 1755-1762.
[10]	卫文乐, 金国栋, 谭力宁, 芦利斌, 陈丹琪. 利用惯导测量单元确定关键帧的实时SLAM算法[J]. 计算机应用, 2020, 40(4): 1157-1163.
[11]	王亚杰, 张云博, 吴燕燕, 丁傲冬, 祁冰枝. 不均匀光照下的通用棋子定位方法[J]. 计算机应用, 2020, 40(12): 3490-3498.
[12]	赵宏, 刘向东, 杨永娟. 基于RGB-D图像的室内机器人同时定位与地图构建[J]. 计算机应用, 2020, 40(12): 3637-3643.
[13]	席志红, 王洪旭, 韩双全. 基于ORB-SLAM2系统的快速误匹配剔除算法与地图构建[J]. 计算机应用, 2020, 40(11): 3289-3294.
[14]	王艺皓, 丁洪伟, 李波, 保利勇, 张颖婕. 基于深度学习的蛋白质亚细胞定位预测[J]. 计算机应用, 2020, 40(11): 3393-3399.
[15]	费大胜, 宋慧慧, 张开华. 基于多层特征增强的实时视觉跟踪[J]. 计算机应用, 2020, 40(11): 3300-3305.