Optimal nearest neighbor queries in sensor networks

• A distributed algorithm for the nearest neighbor problem in sensor networks is proposed.
• It attains constant approximation for query cost in constant-doubling graph model.
• It attains log approximation for update cost in the constant-doubling graph model.
• It attains polylog approximations for both query and update cost in general graph model.
• It is scalable as both cost approximations do not depend on the number of mobile objects.

Given a set of m mobile objects in a sensor network, we consider the problem of finding the nearest object among them from any node in the network at any time. These mobile objects are tracked by nearby sensors called proxy nodes. This problem requires an object tracking mechanism which typically relies on two basic operations: query and update  . A query is invoked by a node each time when there is a need to find the closest object from it in the network. Updates of an object's location are initiated when the object moves from one location (proxy node) to another. We present a scalable distributed algorithm for tracking these mobile objects such that both the query cost and the update cost are small. The main idea in our algorithm is to maintain a virtual tree of downward paths pointing to the objects. Our algorithm guarantees an asymptotically optimal O(1)O(1) approximation for query   cost and an O(min⁡{log⁡n,log⁡D})O(min⁡{log⁡n,log⁡D}) approximation for update cost in the constant-doubling graph model, where n and D, respectively, are the number of nodes and the diameter of the network. We also give polylogarithmic approximations for both query and update cost in the general graph model. Our algorithm requires only polylogarithmic bits of memory per node. To the best of our knowledge, this is the first algorithm that is asymptotically optimal in handling nearest neighbor queries with low update cost in a distributed setting.