Efficient Motion Planning Strategies for Large-Scale Sensor Networks

In this paper, we develop a suite of motion planning strategies suitable for large-scale sensor networks. These solve the problem of reconfiguring the network to a new shape while minimizing either the total distance traveled by the nodes or the maximum distance traveled by ally node. Three network paradigms are investigated: centralized, computationally distributed, and decentralized. For the centralized case, optimal solutions are obtained in O(m) time in practice using a logarithmic-barrier method. Key to this complexity is transforming the Karush-Kuhn-Tucker (KKT) matrix associated with the Newton step sub-problem into a mono-banded system solvable in O(m) time. These results are then extended to a distributed approach that allows the computation to be evenly partitioned across the m nodes in exchange for O(m) messages in the overlay network. Finally, we offer a decentralized, hierarchical approach whereby follower nodus are able to solve for their objective positions in O(1) time from observing the headings of a small number (2-4) of leader nodes. This is akin to biological systems (e.g. schools of fish. flocks of birds, etc.) capable of complex formation changes using only local sensor feedback. We expect these results will prove useful in extending the mission lives of large-scale mobile sensor networks.