Improvement over DV-Hop Localization Algorithm for Wireless Sensor Networks

Authors: Shrawan Kumar, D. K. Lobiyal

Abstract:

In this paper, we propose improved versions of DVHop algorithm as QDV-Hop algorithm and UDV-Hop algorithm for better localization without the need for additional range measurement hardware. The proposed algorithm focuses on third step of DV-Hop, first error terms from estimated distances between unknown node and anchor nodes is separated and then minimized. In the QDV-Hop algorithm, quadratic programming is used to minimize the error to obtain better localization. However, quadratic programming requires a special optimization tool box that increases computational complexity. On the other hand, UDV-Hop algorithm achieves localization accuracy similar to that of QDV-Hop by solving unconstrained optimization problem that results in solving a system of linear equations without much increase in computational complexity. Simulation results show that the performance of our proposed schemes (QDV-Hop and UDV-Hop) is superior to DV-Hop and DV-Hop based algorithms in all considered scenarios.

Keywords: Wireless sensor networks, Error term, DV-Hop algorithm, Localization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1080066

References:

[1] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: a survey," Computer Networks, vol. 38, issue 4, pp. 393-422, 2002.
[2] S-M. Lee, H. Cha, and R. Ha, "Energy aware location Error handling for object tracking applications in wireless sensor networks," Computer Communications, vol. 30, issue 7, pp. 1443-1450, 2007.
[3] Q. Xiao-gang and Q. Chen-xi, "An Improvement of GAF for Lifetime Elongation in Wireless Sensor Networks," Journal of Convergence Information Technology, vol. 5, no. 7, pp. 112-119, 2010.
[4] M. Broxton, J. Lifton, and J. Paradiso, "Localizing a Sensor Network via Collaborative Processing of Global Stimuli," In Proc. of the 2nd European Workshop on Wireless Sensor Networks, pp. 321-332, 2005.
[5] B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins, Global Positioning System: Theory and Practice. 2nd edition, Springer-Verlag, New York, 1993.
[6] J. Lee, W. Chung, and E. Kim, "A new range-free localization method using quadratic programming," Computer Communications. vol. 34, issue 8, pp. 998-1010, 2011.
[7] H. Lee, M. Wicke, B. Kusy, and L. Guibas, "Localization of mobile users using trajectory matching. In MELT '08," Proceedings of the first ACM International Workshop on Mobile Entity Localization and Tracking in GPS-less Environments, New York, USA, pp. 123-128, 2008.
[8] T. He, C. Huang, B.M. Blum, J.A. Stankovic, and T. Abdelzaher, "Range-Free Localization Schemes for Large Scale Sensor Networks," In Proceedings of the 9th annual international conference on Mobile computing and networking, pp. 81-95, 2003.
[9] G. Q. Gao, and L. Lei, "An Improved node Localization Algorithm based on DV-Hop in WSN," In 2nd International Conference on Advanced Computer Control (ICACC), vol. 4, pp. 321-324, 2010.
[10] A. Savvides, C. Han, and M.B. Strivastava, "Dynamic fine grained localization in ad- hoc networks of sensors," Proceedings of the International Conference on Mobile Computing and Networking, pp.166-179, 2001.
[11] S. Yun, J. Lee, W. Chung, E. Kim, and S. Kim, "A soft computing approach to localization in wireless sensor networks," Expert Systems with Applications, vol. 36, issue 4, pp. 552-7561, 2009.
[12] C.-R. Li, "The Self-Location Technology Research for Wireless Sensor Network," SOUTHWEST JIAOTONG UNIVERSITY, Master-s Paper, 2006.
[13] S. Capkun, M. Hamdi, and J.-P. Hubaux, "Gps-free positioning in mobile Ad Hoc networks," In Proceedings of Hawaii International Conference System Sciences, pp. 3481-3490, 2001.
[14] R. Nagpal, "Organizing a global coordinate system from local information on an amorphous computer," A.I. Memo 1666, MIT A.I. Laboratory, 1999.
[15] D. Niculescu, and B. Nath, "Ad Hoc Positioning System (APS)," In Proceeding of IEEE Global Telecommunications Conference. San Antonio: IEEE Communication Society, vol. 5, pp. 2926-2931, 2001.
[16] H. Chen, K. Sezaki, P. Deng, and H. CheungSo, "An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks," In 3rd IEEE International Conference on Industrial Electronics and Application (ICIEA), pp. 1557-1561, 2008.
[17] H. Chen, K. Sezaki, P. Deng, and H. CheungSo, "An Improved DV-Hop Localization Algorithm with Reduced Node Location Error for WSNs. IEICE TRANS. FUNDAMENTALS, E 91 A(8), pp. 2232-2236, 2008.
[18] S. Hou, X. Zhou, and X. Liu, "A Novel DV-Hop Localization Algorithm for Asymmetry Distributed WSNs," In 3rd IEEE International Conference on Computer Science and Information Technology (ICCSIT), vol. 4, pp. 243-248, 2010.
[19] Y.Y. Li, "Improved DV-Hop Localization Algorithm Based on Local Estimating and Dynamic Correction in Location for WSNs," International Journal of Digital Content Technology and its Applications, vol. 5, issue 8, pp. 196-202, 2011.
[20] S. Tian, X. Zhang, P. Liu, P. Sun, and X. Wang, "A RSSI-based DV-hop algorithm for wireless sensor networks," Wireless Communications, Networking and Mobile Computin, pp. 2555 - 2558, 2007.
[21] K. Benkic, M. Malajner, P. Planinsic, and Z.K. Cucej, "Using RSSI value for distance estimation in wireless sensor networks based on ZigBee," In Proc. of 15th International Conference on Systems, Signals and Image Processing, pp. 303-306, 2008.
[22] L. Gui, and T. Val, "A Novel Two-Class Localization Algorithm in Wireless Sensor Networks," Laboratory CNRS-IRIT-UT2, University of Toulouse, vol. 3, issue 3, 2011.
[23] Q. Qian, X. Shen, and H. Chen, "An Improved Node Localization Algorithm Based on DV-Hop for Wireless Sensor Networks," Computer Science and Information Systems, vol. 8, issue 4, pp. 953-972, 2011.
[24] Y.T. Chan, and K.C. Ho, "A simple and efficient estimator for hyperbolic location," IEEE Transactions on Signal Processing. vol. 42, issue 8, pp. 1905-1915, 1994.
[25] D.G. Luenberger, Linear and Non-Linear Programming, 2nd Edition, Kluwer Academic Publishers, London, 2003.