Algorithms and bounds for range-free localization in wireless sensor networks

Assistant Professor Suprakash Datta, Department of Computer Science and Engineering, York University in Toronto

Thursday, October 23, 2008
11 a.m.

CSB 209


A fundamental problem in the design of wireless sensor networks is that of localization -- the determination of the geographical locations of sensors. Manual configuration or adding GPS capabilities is usually not feasible for large networks. A more realistic assumption is that a small fraction of the sensor nodes (called seeds) know their locations. The remaining nodes estimate their locations by exchanging information with other nodes and seeds. Some algorithms assume that nodes are equipped with hardware to measure signal strengths, angles of arrival of signals, or distances to other nodes. These algorithms are called ranging algorithms. Algorithms that assume no such capabilities are called range-free algorithms. Range-free algorithms are desirable because they work with nodes that have lower cost and complexity. However, it is more challenging to design efficient range-free algorithms that have good performance, since they operate with less information than ranging algorithms.

Sensor network nodes can be static or mobile. Most existing localization algorithms were designed to work well either in static networks or networks in which all sensors are mobile. In this talk I will describe several different range-free localization algorithms that work for both static and mobile sensor networks. I will present simulation results that demonstrate that our algorithms outperform comparable existing algorithms like DV-hop and MCL in terms of localization error in very different mobility conditions. I will also present a lower bound for range-free localization algorithms. Finally, I will outline preliminary results in proving upper bounds on the localization error of some of our algorithms.

This is joint work with my students Chris Klinowski, Shaker Khaleque, Masoomeh Rudafshani and Stuart Maclean.

Speaker Biography

Suprakash Datta got his B.Tech. and M.Tech. from IIT (India) in ECE and CSE respectively and a PhD in Computer Science from UMass Amherst. He is an Assistant professor in Computer Science and Engineering at York University in Toronto. His research interests include wired and wireless networks and Genomic Signal Processing. He is currently at the University of Rochester visiting Professor Gaurav Sharma's Lab in the ECE department.