Geometric Algorithms for Target Localization and Tracking Under Location Uncertainties in Wireless Sensor Networks

Since the onset of wireless sensor networks, target localization and tracking have received much attention in a wide range of applications including battle field surveillance, wildlife monitoring and border security. However, little work has been done that addresses the realistic considerations of uncertainties in sensor locations and evaluates their impacts on the accuracy of target localization and tracking. In this paper, we carry out a rigorous study of these problems using a computational geometry approach. We introduce the geometric structures of order- $k$ max and min Voronoi Diagrams (VDs) and propose an algorithm to construct these diagrams. Based on order-k max and min VDs, efficient algorithms are developed to evaluate the likelihood of noisy sensor readings and $k{\bf NN}$ queries, which serve as building blocks in target localization and tracking under sensor location uncertainties.