Wireless sensor networks allow us to instrument our world in novel ways providing detailed insight that had not been possible earlier. Since these networks provide an interface to the physical world, it is necessary for each sensor node to learn its location in the physical space. The availability of location information at individual sensor nodes allows the network to provide higher layer services such as location stamped event reporting, geographic routing, in-network processing etc. A wide range of these sensor network protocols do not require absolute node coordinates and can work with relative node positions. This motivates for the need of anchor free localization algorithms that localize the individual sensor nodes with respect to each other in a local coordinate system. Such algorithms allow the sensor networks to be decoupled from external infrastructure and become truly place and play systems. The primary contributions of this thesis include two anchor free localization algorithms and one location refinement algorithm for ad-hoc wireless sensor networks. Our distributed anchor free localization algorithms do not require any external infrastructure in the form of landmark or manually initialized anchor nodes. These algorithms use measured inter-node distances among some node pairs and localize the entire network in a local coordinate system up to a global translation, rotation and reflection. The relative or virtual coordinates assigned by these algorithms can be readily used with a range of sensor network services like geographic routing, data aggregation, topology control etc. Our first localization algorithm is based on a distributed collaborative approach where all of the nodes in the network collaborate with each other to select a set of nodes. These nodes are localized and then used as reference nodes for the remaining sensor nodes. The novelty of this approach is that instead of solving the localization problem for the entire network upfront, first a small well-formed localization problem is solved and then these results are used to solve the localization problem for the remaining nodes in the network. Our second localization algorithm borrows ideas from the data visualization field and exploits the general undirected graph drawing theory to solve the sensor network localization problem. This algorithm divides the network into a large number of small overlapping clusters and creates local coordinate systems for each of the clusters. These clusters are then merged together in a single coordinate system using a novel distributed algorithm that seeks to minimize the error during this merge process. Our final contribution is a distributed location refinement algorithm that can be used with any of the range based localization algorithms to refine the sensor node coordinates to conform to the measured inter-node distances. We model this coordinate refinement problem as an unconstrained non-linear optimization problem and then transform this optimization problem into an aggregate computation problem. We propose two different approaches to solve this aggregate computation problem in a distributed manner. We evaluate our algorithms with detailed simulations using both Matlab and TinyOS simulator TOSSIM. We also validate our simulation results with experimentation carried out on a real network of MIT Cricket motes. We conclude this thesis with lessons learned during this research and discuss some future directions which can be explored to advance the research in sensor network localization.
| Identifer | oai:union.ndltd.org:ADTP/230367 |
| Date | January 2008 |
| Creators | Nawaz, Sarfraz, Computer Science & Engineering, Faculty of Engineering, UNSW |
| Publisher | Publisher:University of New South Wales. Computer Science & Engineering |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | http://unsworks.unsw.edu.au/copyright, http://unsworks.unsw.edu.au/copyright |
Page generated in 0.0018 seconds