Collaborative And Distributed Algorithms For Localization In Wireless Sensor Networks Based On The Solution Of Spatially Constrained Local And Sub-Local Problems

In this research we present algorithms for the distributed and collaborative localization of nodes for applications in wireless sensor networks. The algorithms are distributed in the sense that each node can estimate its own position using only range information and position estimates from neighboring nodes. The algorithms aim at achieving good accuracy with low computational complexity and low energy consumption. We consider the full localization process consisting of an initialization stage followed by a refinement stage. For initialization, we propose a \emph{bilateration} algorithm where each node uses a set of anchors and their respective ranges to solve a set of circle intersection problems. These problems are solved through a purely geometric formulation with low computational complexity. The resulting circle intersections are processed to pick those that cluster together and then take their average to produce an initial node location. For the refinement stage, we develop an iterative collaborative variation of multilateration where all sensors solve a spatially-constrained optimization program to find position updates which are used on the next refinement iteration. We introduce two types of objective functions: local and sub-local. In the local case, each sensor tries to minimize the mean absolute range error with all its neighbors simultaneously. In the sub-local case, a node sets a separate objective function with each of it neighbors and produces a set of solutions which are averaged to produce a final update. Our distributed algorithms are characterized by a spatial constraint that limits the solution space to some region around the current position estimate. This constraint allows all the nodes to update their position simultaneously while achieving convergence. In general, simulations show the local objective function performs better than the sub-local case. We note that the proposed approach has computational characteristics that allow its deployment on real mote hardware. Furthermore, we introduce a simple stop criteria based on a local threshold $\tau$ that relaxes the absolute distance change between position updates. We also introduce a realistic energy model that models consumption at the processor cycle and bit transmission levels. The model characterizes energy consumption for the localization process over the complete network. Combining $\tau$ with the energy model, experimental results show that we can determine the best tradeoff between energy and accuracy performance for a given energy budget. We conclude that there is a strong dependance on the initialization scheme, and that the use of local objective functions provides a better accuracy-energy tradeoff in our simulations. As far we know, there is not a research in WSN localization that presents such a detailed analysis of energy consumption in the localization process. Finally, we develop schemes for location refinement based on the observation that nodes inside the convex hull formed by the anchors tend to provide position estimates with smaller error. This work leads to a novel refinement step that applies to all the nodes in the network, and achieves an excellent tradeoff between accuracy and energy consumption. The refinement step solves another multilateration optimization problem using the Levenberg Marquardt algorithm. Evidence shows that even for large values of $\tau$ the algorithm finds a solution that provides significant improvements on accuracy with minimal energy costs