Range-Free Localization Schemes for Wireless Sensor Networks

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.

Authors:

• R. Khadim
• M. Erritali
• A. Maaden

Keywords:

• Wireless Sensor Networks
• Node Localization
• Centroid Algorithm
• DV–Hop Algorithm
• Amorphous Algorithm.

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