Improvement over DV-Hop Localization Algorithm for Wireless Sensor Networks

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.

Authors:

• Shrawan Kumar
• D. K. Lobiyal

Keywords:

• Wireless sensor networks
• Error term
• DV-Hop algorithm
• Localization.

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.