Near-Optimal Location Tracking Using Sensor Networks

Abstract

We consider the problem of tracking mobile objects using a sensor network. We present a distributed tracking algorithm, called Mobile Object Tracking using Sensors (MOT), that scales well with the number of sensors and also with the number of mobile objects. MOT maintains a hierarchical structure of detection lists of objects that can efficiently track mobile objects and resolve object queries at any time. MOT guarantees that the cost to update (or maintain) its data structures will be at most O(min{log n, log D}) times the optimal update cost and query cost will be within O(1) of the optimal query cost in the constant-doubling graph model, where n and D, respectively, are the number of nodes and the diameter of the network. MOT achieves polylogarithmic approximations for both costs in the general graph model. MOT balances the object and bookkeeping information load at each node in the expense of only O(logn) increase in the update and query costs. The experimentation evaluation in both one by one and concurrent execution situations shows that MOT performs well in practical scenarios. To the best of our knowledge, MOT is the first algorithm for this problem in a distributed setting that is traffic-oblivious, i.e. agnostic to a priori knowledge of objects movement patterns, mobility and query rate, etc., and is load balanced. All previous solutions for this problem assumed traffic-consciousness in constructing the tracking data structure.