Optimal backbone generation for robotic relay networks


Event International Conference on Computer Communications and Networks


Zhang, Ying
Technical Publications
July 31st 2011
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.


Zhang, Y.; Quilling, M. Optimal backbone generation for robotic relay networks. IEEE International Conference on Computer Communications and Networks (ICCCN); 2011 July 31 - August 4; Maui, HI.

Additional information

Focus Areas

Our work is centered around a series of Focus Areas that we believe are the future of science and technology.

Licensing & Commercialization Opportunities

We’re continually developing new technologies, many of which are available for¬†Commercialization.


PARC scientists and staffers are active members and contributors to the science and technology communities.