Optimal backbone generation for robotic relay networks

There has been a growing interest in robotic relay networks for applications in dangerous and hazardous environments. In particular, a team of robots with onboard radios deployed in an unknown environment would coordinate to form an ad-hoc relay network that maximizes the connectivity to transmit data from a set of unknown data sources to a gateway. In this paper, we present a problem and solutions to minimize the number of stationary relay nodes given a set of unknown but stationary sources. The goal is to maximize the number of free robots to search for more unknown sources to extend the connectivity of the network, while keeping the communications to the existing connected sources. We present two types of algorithms: OLQ (Optimal Link Quality) and AST (Approximate Steiner Tree), and analyze their performance in various routing metrics. The algorithms have been developed in a real robotic platform and demonstrated in multi-floor indoor environments.