Near-optimal location tracking using sensor networks

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 that can efficiently track mobile objects and resolve object queries at any time. MOT guarantees that the cost to update 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. Moreover, MOT achieves polylogarithmic approximations for both costs in the general graph model and performs well in practical scenarios. To our best 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.