Global error-tolerant algorithms for location discovery in ad-hoc wireless Netoworks

We address location discovery problem in ad-hoc wireless Networks. Location discovery is a task with fundamental role in multi-hop wireless networks since many other middleware tasks, such as coverage, tracking and routing, as well as many applications need accurate location of nodes. We have developed simple, yet accurate mathematical abstraction of the problem. We have also developed an atomic tri-lateration procedure for calculating the position of a node in presence of measurements errors. We have statistically analyzed the procedure with respect to a number of parameters, such as error distribution and relative positions of the nodes and used that information for improving effectiveness of the location discovery procedure. Furthermore, we have developed randomized iterative improvement algorithm for fast location discovery in wireless ad-hoc networks. We experimentally verified the exceptional effectiveness of the procedure in presence of errors for both cetralized and localized version of the algorithm.