Near-optimal deterministic Steiner tree maintenance in sensor networks

We consider the group-communication maintenance problem between a set of k mobile agents that are tracked by a static sensor network.We develop a scalable deterministic distributed algorithm formaintaining a Steiner tree of the agents so that group communication between them can be provided with the minimum total cost possible. The main idea is that our algorithm maintains a virtual tree of mobile agents that can be immediately converted to an actual Steiner tree at all times. Our algorithm achieves the Steiner tree with total length at most O(log k) times the length of the optimal Steiner tree in the constant-doubling graph model. The total communication cost (the number of messages) to maintain the Steiner tree is only O(min{log n, log D}) times the optimal communication cost, where n and D, respectively, are the number of nodes and the diameter of the constant-doubling network. We also develop improved algorithms for the mobile k-center, sparse-aggregation, and distributed-matching problems. Experimental evaluation results show the benefits of our algorithms compared to previous algorithms. These four problems are NP-hard and, to the best of our knowledge, our algorithms are the first near-optimal deterministic algorithms for maintaining approximate solutions to these important network problems with low maintenance costs in a distributed setting.