Range-Free Localization Schemes for Wireless Sensor Networks

Authors: R. Khadim, M. Erritali, A. Maaden

Abstract:

Localization of nodes is one of the key issues of Wireless Sensor Network (WSN) that gained a wide attention in recent years. The existing localization techniques can be generally categorized into two types: range-based and range-free. Compared with rang-based schemes, the range-free schemes are more costeffective, because no additional ranging devices are needed. As a result, we focus our research on the range-free schemes. In this paper we study three types of range-free location algorithms to compare the localization error and energy consumption of each one. Centroid algorithm requires a normal node has at least three neighbor anchors, while DV-hop algorithm doesn’t have this requirement. The third studied algorithm is the amorphous algorithm similar to DV-Hop algorithm, and the idea is to calculate the hop distance between two nodes instead of the linear distance between them. The simulation results show that the localization accuracy of the amorphous algorithm is higher than that of other algorithms and the energy consumption does not increase too much.

Keywords: Wireless Sensor Networks, Node Localization, Centroid Algorithm, DV–Hop Algorithm, Amorphous Algorithm.

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

References:

[1] Linqing Gui, Improvement of Range-free Localization Systems in Wireless Sensor Networks, PhD thesis, 13 February 2013
[2] Y. Lee, W. Chung “Wireless sensor network based wearable smart shirt for ubiquitous health and activity monitoring”, Sensors and Actuators B: Chemical, vol: 140, issue: 2, pp: 390-395, 16 July 2009.
[3] G. López, V. Custodio, J. Moreno, "LOBIN: E-Textile and Wireless- Sensor-Network Based Platform for Healthcare Monitoring in Future Hospital Environments," IEEE Transactions on Information Technology in Biomedicine, vol.14, no.6, pp.1446-1458, Nov. 2010.
[4] G. Werner-Allen, K. Lorincz, et al. “Deploying a wireless sensor network on an active volcano”. IEEE Internet Computing, vol. 10, no. 2, pp. 18-25, Mar. 2006.
[5] J. Li, M. Yu, “Sensor coverage in wireless ad hoc sensor networks”, International Journal of Sensor Networks, vol. 2, no. 3/4, pp. 218-229, Jun. 2007.
[6] M. L. Lazos, R. Poovendran, “SeRLoc: Robust localization for wireless sensor networks”, ACM Transactions on Sensor Networks, vol. 1, no. 1, pp. 73-100, Aug. 2005.
[7] A. Terzis, A. Anandarajah, K. Moore, et al. “Slip surface localization in wireless sensor networks for landslide prediction”, In Proceedings of the 5th international Conference on information Processing in Sensor Networks (IPSN ‘06), Nashville, Tennessee, USA, April 19-21, 2006, pp. 109-116.
[8] S. Basagni, I. Chlamtac, V. Syrotiuk, et al. “A distance routing effect algorithm for mobility (DREAM)”, In Proceedings of the 4th Annual ACM/IEEE international Conference on Mobile Computing and Networking (MobiCom ‘98), Dallas, Texas, USA, Oct. 25-30, 1998, pp. 76-84.
[9] B. Karp, H. Kung, “GPSR: greedy perimeter stateless routing for wireless networks”, In Proceedings of the 6th Annual international Conference on Mobile Computing and Networking (MobiCom ‘00), Boston, Massachusetts, USA, Aug. 06-11, 2000, pp. 243-254.
[10] Y. Kim, R. Govindan, B. Karp, et al. “Geographic routing made practical”, In Proceedings of the 2nd Conference on Symposium on Networked Systems Design and Implementation (NSDI ‘05), May 02- 04, 2005, Berkeley, CA, USA, pp. 217-230.
[11] K. Alzoubi, X. Li, Y. Wang, et al. “Geomet IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 4, Apr. 2003, pp. 408-421.
[12] N. Li, J. Hou, “Localized topology control algorithms for heterogeneous wireless Networks”, IEEE/ACM Transactions on Networking, vol. 13, no 6. 2005, pp. 1313-1324.
[13] Y. Xu, J. Heidemann, D. Estrin, “Geography-informed energy conservation for Ad Hoc routing”. In Proceedings of the 7th Annual international Conference on Mobile Computing and Networking (MobiCom ‘01), Rome, Italy, Jul. 16-21, 2001, pp. 70-84.
[14] F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: a survey,” Computer Networks, vol. 38, no. 4, pp. 393– 422, 2002.
[15] L. Haibo, W. Yingna, and P. Bao, “A Localization method of Wireless sensor network based on two-hop focus,” Procedia Engineering, vol. 15, pp. 2021–2025, 2011.
[16] V. Chandrasekhar, et al. “Localization in underwater sensor networks: survey and challenges”. In Proceedings of the 1st ACM international Worksh(WUWNet ‘06), Los Angeles, CA, USA, Sep. 25, 2006, pp. 33- 40.
[17] G. Mao, B. Fidan, B. Anderson, “Wireless sensor network localization techniques”. Computer Networks, vol. 51, no. 10, Jul. 2007, pp. 2529- 2553.
[18] I. Amundson, and X. Koutsoukos, “A survey on localization for mob networks”. In Proceedings of the 2nd international Conference on Mobile Entity Localization and Tracking in GPS-Less Environments, Orlando, FL, USA, Sep. 30, 2009, pp. 235-254.
[19] Y. Liu, Z. Yang, X. Wang, et al. “Location, Localization, Localizability”. Journal of Computer Science and Technology, vol. 25, no. 2, Mar. 2010, pp. 247-297.
[20] R. Ouyang, A. Wong, K. Woo, "GPS Localization Accuracy Improvement by Fusing Terrestrial TOA Measurements", IEEE International Conference on Communications (ICC), pp. 1-5, May 2010.
[21] P. Kumar, L. Reddy, S. Varma, “Distance measurement and error estimation scheme for RSSI based localization in Wireless Sensor Networks,” Fifth IEEE Conference on Wireless Communication and Sensor Networks (WCSN), Allahabad, India, pp. 1-4, Dec. 2009
[22] P. Voltz, D. Hernandez, “Maximum likelihood time of arrival estimation for real-time physical location obile stations in indoor environments,” Position Location and Navigation Symposium (PLANS), California, USA, pp. 585-591, April 2004.
[23] L. Kovavisaruch, and K. Ho, “Alternate source and receiver location estimation using TDOA with receiver position uncertainties,” IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '05), Pennsylvania, USA, pp. iv/1065 - iv/1068, March 2005.
[24] P. Rong, and M. Sichitiu, “Angle of arrival localization for wireless sensor networks,” Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks, USA, 2006, vol.1, pp.374-382.
[25] J. Yao, J. Li, L. Wang, and Y. Han, “Wireless sensor network localization based on improved particle swarm optimization,” in Proceedings of the International Conference on Computing, Measurement, Control and Sensor Network (CMCSN ’12), pp. 72–75, July 2012.
[26] Linqing GUI, Thierry VAL, Anne WEI, “An Adaptive Range-free Localization Protocol in Wireless Sensor Networks”, International Journal of Ad Hoc and Ubiquitous Computing, in review, submitted on 20 December 2012.
[27] Linqing Gui, Thierry Val, Anne Wei, Réjane Dalce, “Improvement of Range-free Localization Systems Realized by a DV-hop Protocol in Wireless Sensor Networks”, Ad Hoc & Sensor Wireless Networks, in review, submitted on 5 July 2012.
[28] Linqing Gui, Anne Wei, Thierry Val, “A Range-Free Localization Protocol for Wireless Sensor Networks”, International Symposium on Wireless Communications Systems, Paris, August 2012
[29] N. Bulusu, J. Heidemann and D. Estrin, GPS-less Low Cost Outdoor Localization for Very Small Devices, IEEE Personal Communications Magazine, 7(5):28-34, October 2000.
[30] D. Niculescu and B. Nath, DV Based Positioning in Ad hoc Networks, In Journal of Telecommunication Systems, 2003.
[31] R. Nagpal, H. Shrobe, J. Bachrach, Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network, In the 2nd International Workshop on Information Processing in Sensor Networks (IPSN '03), Palo Alto, April, 2003.
[32] Y. Liu, “An adaptive multi-hop distance localization algorithm in WSN,” Manufacturing Automation, vol. 33, pp. 161–163, 2011