基于校正矢量的分布式DV- Hop求精算法
|
摘要
节点定位技术是当前无线传感器网络研究的热点之一.基于跳距估计的DV-Hop(distance vector hop)定位算法是无需测距定位算法的典型代表,它具有算法简单、易实现等优点,但也存在定位模糊、定位精度不高的缺点.针对DV-Hop算法的定位模糊问题,提出一种基于校正矢量的分布式迭代求精算法(correction vector based distributed localization refinement algorithm, CVLR).在DV-Hop定位完成后,CVLR利用节点与其邻居节点间的伪测距距离和定位距离构建位置校正矢量,然后将求精过程建模为使这2个距离的差值的平方和在校正矢量方向上的最小化问题,最后用一种简单的迭代搜索算法求解该最小化问题.CVLR实现过程中,分为仅利用1跳邻居节点信息的CVLR1和同时利用1跳和2跳邻居节点信息的CVLR2.仿真结果表明:与DV-Hop,DV-RND (an improved DV-Hop localization algorithm based on regulated neighborhood distance),DV-EA (an improved DV-Hop localization algorithm based on evolutionary algorithm)相比,CVLR1的定位精度平均提高30%,25%,20%,CVLR2的定位精度平均提高45%,42%,40%.
Node location technology is one of the hot topics in current wireless sensor networks(WSNs). The DV-Hop(distance vector hop) localization algorithm, based on the hop distance estimation, is a typical representation of range-free localization algorithm. The advantages of DV-Hop is simple and easy implementation, and its disadvantage is low positioning accuracy which is resulting from the hop-distance ambiguity problem. Focusing on the hop-distance ambiguity problem of the traditional DV-Hop localization algorithm, this paper proposes a correction vector based distributed localization refinement algorithm(CVLR). Firstly, based on the localization results of DV-Hop, CVLR constructs the position correction vector using the pseudo ranging distance and the positioning distance between neighbors and unknown nodes. Secondly, the refinement process is modeled to minimize the square sum of the difference between the two distances in the direction of correction vector. Finally, a simple iterative search method is proposed to solve above minimization problem. In practice, CVLR consists of CVLR1 and CVLR2. CVLR1 can make full use of the information of 1-hop neighbors, and CVLR2 can make full use of the information of 1-hop and 2-hop neighbors. The simulation results show that, compared with DV-Hop, DV-RND(an improved DV-Hop localization algorithm based on regulated neighborhood distance), and DV-EA(an improved DV-Hop localization algorithm based on evolutionary algorithm), CVLR1 improves the positioning accuracy by about 30%, 25%, and 20%, and CVLR2 improves the positioning accuracy by about 45%, 42%, and 40%, on average.
Node location technology is one of the hot topics in current wireless sensor networks(WSNs). The DV-Hop(distance vector hop) localization algorithm, based on the hop distance estimation, is a typical representation of range-free localization algorithm. The advantages of DV-Hop is simple and easy implementation, and its disadvantage is low positioning accuracy which is resulting from the hop-distance ambiguity problem. Focusing on the hop-distance ambiguity problem of the traditional DV-Hop localization algorithm, this paper proposes a correction vector based distributed localization refinement algorithm(CVLR). Firstly, based on the localization results of DV-Hop, CVLR constructs the position correction vector using the pseudo ranging distance and the positioning distance between neighbors and unknown nodes. Secondly, the refinement process is modeled to minimize the square sum of the difference between the two distances in the direction of correction vector. Finally, a simple iterative search method is proposed to solve above minimization problem. In practice, CVLR consists of CVLR1 and CVLR2. CVLR1 can make full use of the information of 1-hop neighbors, and CVLR2 can make full use of the information of 1-hop and 2-hop neighbors. The simulation results show that, compared with DV-Hop, DV-RND(an improved DV-Hop localization algorithm based on regulated neighborhood distance), and DV-EA(an improved DV-Hop localization algorithm based on evolutionary algorithm), CVLR1 improves the positioning accuracy by about 30%, 25%, and 20%, and CVLR2 improves the positioning accuracy by about 45%, 42%, and 40%, on average.
引文
[1]Xu Yang, Liu Fugui. Application of wireless sensor network in water quality monitoring [C] //Proc of the 20th IEEE Int Conf on Computational Science and Engineering. Piscataway, NJ: IEEE, 2017: 368- 371
[2]Wang Haohan, Dong Linxi, Wei Wei, et al. The WSN monitoring system for large outdoor advertising boards based on ZigBee and MEMS sensor [J]. IEEE Sensors Journal, 2018, 18(3): 1314- 1323
[3]Gurumoorthy K B, Kumar A N. Mutual constraint based GA suggested routing algorithm for improving QoS in clustered MANETS [J]. Wireless Personal Communications, 2018, 98(3): 2975- 2991
[4]Manap Z, Ali BM, Ng CK, et al. A Review on hierarchical routing protocols for wireless sensor networks [J]. Wireless Personal Communications, 2013, 72 (2): 1077- 1104
[5]Mao Keji, Fan Congling, Ye Fei, et al. Node localization algorithm in wireless sensor networks based on SVM [J]. Journal of Computer Research and Development, 2014, 51(11): 2427- 2436 (in Chinese)(毛科技, 范聪玲, 叶飞, 等. 基于支持向量机的无线传感器网络节点定位算法[J]. 计算机研究与发展, 2014, 51(11): 2427- 2436)
[6]Xiao Fu, Sha Chaoheng, Chen Lei, 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 (in Chinese)(肖甫, 沙朝恒, 陈蕾, 等. 基于范数正则化矩阵补全的无线传感网定位算法[J]. 计算机研究与发展, 2016, 53(1): 216- 227)
[7]Yao Yingbiao, Jiang Nanlan. Distributed wireless sensor network localization based on weighted search[J]. Computer Networks, 2015, 86(5): 57- 75
[8]Ahmadi Y, Neda N, Ghazizadeh R. Range free localization in wireless sensor networks for homogeneous and non-homogeneous environment[J]. IEEE Sensors Journal, 2016, 16(22): 8018- 8026
[9]Yeredor A. Decentralized TOA-based localization in non-synchronized wireless networks with partial, asymmetric connectivity[C] //Proc of the 15th IEEE Int Workshop on Signal Processing Advances in Wireless Communications. Piscataway, NJ: IEEE, 2014: 165- 169
[10]Shao Huajie, Zhang Xiaoping, Wang Zhi. Efficient closed-form algorithms for AOA based self-localization of sensor nodes using auxiliary variables[J]. IEEE Transactions on Signal Processing, 2014, 62(10): 2580- 2594
[11]Yao Yingbiao, Han Qi, Xu Xiaorong, et al. A RSSI-based distributed weighted search localization algorithm for WSNs [J]. International Journal of Distributed Sensor Networks, 2015: Article ID 293403
[12]Tang Wenliang, Zhou Linying. An improved APIT localization algorithm based on triangle-circumcircle cover [J]. Chinese Journal of Sensors and Actuators, 2015, 28(1): 121- 125 (in Chinese)(汤文亮, 周琳颖. 基于三角形外接圆覆盖的改进APIT定位算法[J]. 传感技术学报, 2015, 28(1): 121- 125)
[13]Wu Guang, Wang Shu, Wang Bang, et al. A novel range-free localization based on regulated neighborhood distance for wireless ad hoc and sensor networks[J]. Computer Networks, 2012, 56(16): 3581- 3593
[14]Mehrabi M, Taheri H, Taghdiri P. An improved DV-Hop localization algorithm based on evolutionary algorithms [J]. Telecommunication System, 2017, 64(4): 639- 647
[15]Singh S P, Sharma S C. A PSO based improved localization algorithm for wireless sensor network [J]. Wireless Personal Communications, 2018, 98(1): 487- 503
[16]Ma Shuli, Zhao Jianping. Multi communication ranges DV-Hop localization algorithm for wireless sensor network [J]. Chinese Journal of Sensors and Actuators, 2016, 29(4): 593- 600 (in Chinese)(马淑丽, 赵建平. 多通信半径的无线传感器网络DV-Hop定位算法[J]. 传感技术学报, 2016, 29(4): 593- 600)
[17]Liu Yuan, Chen Junjie, Xu Zhenfeng. Improved DV-Hop localization algorithm based on bat algorithm in wireless sensor networks [J]. KSII Transactions on Internet & Information Systems, 2017, 11(1): 215- 236
[18]Zheng Mingcai, Zhang Dafang, Zhao Jinqin, et al. Distance estimating algorithm based on gradient neighbors in wireless sensor networks [J]. Journal on Communications, 2008, 29(11): 237- 245 (in Chinese)(郑明才, 张大方, 赵晋琴, 等. 基于梯度化邻居节点信息的传感器网络节点距离测量[J]. 通信学报, 2008, 29(11): 237- 245)
[19]Zhao Yanhang, Qian Zhihong, Shang Xiaohang, et al. PSO localization algorithm for WSN nodes based on modifying average hop distances [J]. Journal on Communications, 2013, 34(9): 105- 114 (in Chinese)(赵雁航, 钱志鸿, 尚小航, 等. 基于跳距修正粒子群优化的 WSN 定位算法[J]. 通信学报, 2013, 34(9): 105- 114)
[20]Peng Bo, Li Lei. An improved localization algorithm based on genetic algorithm in wireless sensor networks [J]. Cognitive Neurodynamics, 2015, 9(2): 249- 256
[21]Gurung S, Hossain A K, Kanchanasut K. A hop-count based positioning algorithm for wireless ad-hoc networks [J]. Wireless Networks, 2014, 20(6): 1431- 1444
[22]Wang Yun, Wang Xiaodong, Wang Demin, et al. Range-free localization using expected hop progress in wireless sensor networks [J]. IEEE Transactions on Parallel & Distributed Systems, 2009, 20(10): 1540- 1552
[23]Arias J, Zuloaga A, Lazaro J. Malguki: An RSSI based ad hoc location algorithm [J]. Microprocessors and Microsystems, 2004, 28(8): 403- 409
[2]Wang Haohan, Dong Linxi, Wei Wei, et al. The WSN monitoring system for large outdoor advertising boards based on ZigBee and MEMS sensor [J]. IEEE Sensors Journal, 2018, 18(3): 1314- 1323
[3]Gurumoorthy K B, Kumar A N. Mutual constraint based GA suggested routing algorithm for improving QoS in clustered MANETS [J]. Wireless Personal Communications, 2018, 98(3): 2975- 2991
[4]Manap Z, Ali BM, Ng CK, et al. A Review on hierarchical routing protocols for wireless sensor networks [J]. Wireless Personal Communications, 2013, 72 (2): 1077- 1104
[5]Mao Keji, Fan Congling, Ye Fei, et al. Node localization algorithm in wireless sensor networks based on SVM [J]. Journal of Computer Research and Development, 2014, 51(11): 2427- 2436 (in Chinese)(毛科技, 范聪玲, 叶飞, 等. 基于支持向量机的无线传感器网络节点定位算法[J]. 计算机研究与发展, 2014, 51(11): 2427- 2436)
[6]Xiao Fu, Sha Chaoheng, Chen Lei, 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 (in Chinese)(肖甫, 沙朝恒, 陈蕾, 等. 基于范数正则化矩阵补全的无线传感网定位算法[J]. 计算机研究与发展, 2016, 53(1): 216- 227)
[7]Yao Yingbiao, Jiang Nanlan. Distributed wireless sensor network localization based on weighted search[J]. Computer Networks, 2015, 86(5): 57- 75
[8]Ahmadi Y, Neda N, Ghazizadeh R. Range free localization in wireless sensor networks for homogeneous and non-homogeneous environment[J]. IEEE Sensors Journal, 2016, 16(22): 8018- 8026
[9]Yeredor A. Decentralized TOA-based localization in non-synchronized wireless networks with partial, asymmetric connectivity[C] //Proc of the 15th IEEE Int Workshop on Signal Processing Advances in Wireless Communications. Piscataway, NJ: IEEE, 2014: 165- 169
[10]Shao Huajie, Zhang Xiaoping, Wang Zhi. Efficient closed-form algorithms for AOA based self-localization of sensor nodes using auxiliary variables[J]. IEEE Transactions on Signal Processing, 2014, 62(10): 2580- 2594
[11]Yao Yingbiao, Han Qi, Xu Xiaorong, et al. A RSSI-based distributed weighted search localization algorithm for WSNs [J]. International Journal of Distributed Sensor Networks, 2015: Article ID 293403
[12]Tang Wenliang, Zhou Linying. An improved APIT localization algorithm based on triangle-circumcircle cover [J]. Chinese Journal of Sensors and Actuators, 2015, 28(1): 121- 125 (in Chinese)(汤文亮, 周琳颖. 基于三角形外接圆覆盖的改进APIT定位算法[J]. 传感技术学报, 2015, 28(1): 121- 125)
[13]Wu Guang, Wang Shu, Wang Bang, et al. A novel range-free localization based on regulated neighborhood distance for wireless ad hoc and sensor networks[J]. Computer Networks, 2012, 56(16): 3581- 3593
[14]Mehrabi M, Taheri H, Taghdiri P. An improved DV-Hop localization algorithm based on evolutionary algorithms [J]. Telecommunication System, 2017, 64(4): 639- 647
[15]Singh S P, Sharma S C. A PSO based improved localization algorithm for wireless sensor network [J]. Wireless Personal Communications, 2018, 98(1): 487- 503
[16]Ma Shuli, Zhao Jianping. Multi communication ranges DV-Hop localization algorithm for wireless sensor network [J]. Chinese Journal of Sensors and Actuators, 2016, 29(4): 593- 600 (in Chinese)(马淑丽, 赵建平. 多通信半径的无线传感器网络DV-Hop定位算法[J]. 传感技术学报, 2016, 29(4): 593- 600)
[17]Liu Yuan, Chen Junjie, Xu Zhenfeng. Improved DV-Hop localization algorithm based on bat algorithm in wireless sensor networks [J]. KSII Transactions on Internet & Information Systems, 2017, 11(1): 215- 236
[18]Zheng Mingcai, Zhang Dafang, Zhao Jinqin, et al. Distance estimating algorithm based on gradient neighbors in wireless sensor networks [J]. Journal on Communications, 2008, 29(11): 237- 245 (in Chinese)(郑明才, 张大方, 赵晋琴, 等. 基于梯度化邻居节点信息的传感器网络节点距离测量[J]. 通信学报, 2008, 29(11): 237- 245)
[19]Zhao Yanhang, Qian Zhihong, Shang Xiaohang, et al. PSO localization algorithm for WSN nodes based on modifying average hop distances [J]. Journal on Communications, 2013, 34(9): 105- 114 (in Chinese)(赵雁航, 钱志鸿, 尚小航, 等. 基于跳距修正粒子群优化的 WSN 定位算法[J]. 通信学报, 2013, 34(9): 105- 114)
[20]Peng Bo, Li Lei. An improved localization algorithm based on genetic algorithm in wireless sensor networks [J]. Cognitive Neurodynamics, 2015, 9(2): 249- 256
[21]Gurung S, Hossain A K, Kanchanasut K. A hop-count based positioning algorithm for wireless ad-hoc networks [J]. Wireless Networks, 2014, 20(6): 1431- 1444
[22]Wang Yun, Wang Xiaodong, Wang Demin, et al. Range-free localization using expected hop progress in wireless sensor networks [J]. IEEE Transactions on Parallel & Distributed Systems, 2009, 20(10): 1540- 1552
[23]Arias J, Zuloaga A, Lazaro J. Malguki: An RSSI based ad hoc location algorithm [J]. Microprocessors and Microsystems, 2004, 28(8): 403- 409