Cadence Silver Medal - 2005
Best M.Tech. Thesis in the Departments of Computer Science & Engineering and Electrical Engineering for Good Academic Performance, Innovation in Thesis, Development of New Technology and/or Substantial Betterment of Existing Technology
Title: Three Beacon Sensor Network Localization through Self Propogation
Abstract: This thesis describes a distributed algorithm for estimating node positions in a sensor network. The approach makes use of three stationary beacons (with knowledge of their position apriori) to localize a few neighboring nodes in the network. These freshly localized nodes in turn propagate the location information to their neighbors and the process continues until the entire network is localized. The sensor nodes make use of the geometric constraints induced by their neighbors both in terms of radio connectivity and its negativity to decrease the uncertainty of their position and thus achieve localization. Fixed beacon placement approaches deploying a large number of beacons often result in being inadequate and non realizable practically considering the environments in which sensor networks may be expected to operate (with high terrain uncertainties).
In this thesis, we therefore motivate the need for self propagation of localization information in a sensor network without having to strategically deploy a large number of beacons. The proposed scheme provides an extremely low cost (in money, and power consumption) solution to the localization problem. We design, evaluate and analyze this novel self localization algorithm using simulations. Also, in simulation, we demonstrate that the algorithm scales to large networks and handles real-world deployment scenarios in presence of noise and gray areas. We also compare our approach to Bulusu et al"s Max approach and show that the our proposed algorithm requires reasonably lesser resources to localize the nodes in the network with same average localization error. Further, in order to study the performance of the model in more realistic scenarios we have developed an in-house platform of sensor nodes using Atmel AT89C52 microcontroller and radiometrix TX/RX. We implemented the algorithm on a physical sensor network of such nodes and empirically assessed its accuracy and performance. Our on-ground implementation of the scheme and our results show the effectiveness of our localization mechanism.