Network Formation

From RSN
Jump to: navigation, search

Probabilistic Network Formation through Coverage and Freeze-Tag

We address the problem of propagating a piece of information among robots scattered in an environment. Initially, a single robot has the information. This robot searches for other robots to pass it along. When a robot is discovered, it can participate in the process by searching for other robots. Since our motivation for studying this problem is to form an ad-hoc network, we call it the Network Formation Problem. In this paper, we study the case where the environment is a rectangle and the robots' locations are unknown but chosen uniformly at random. We present an efficient network formation algorithm, Stripes, and show that its expected performance is within a logarithmic factor of the optimal performance. We also compare Stripes with an intuitive network formation algorithm in simulations. The feasibility of Stripes is demonstrated with a proof-of-concept implementation.

The videos below show an implementation of the algorithm presented in the paper above.

Related Project

For more recent work on a closely related problem, see: Robotic Routers.

Related Publications

2012
6O. Tekdas, Y. Kumar, V. Isler, R. Janardan
Building a Communication Bridge With Mobile Hubs
IEEE Tran. on Automation Science and Engineering, 9(1): 171--176, 2012.
pdf,prelim.version,.bib
2011
5E. Stump, N. Michael, V. Kumar, V. Isler
Visibility-Based Deployment of Robot Formations for Communication Maintenance.
In Proc. IEEE Int. Conf. on Robotics and Automation, 2011.
pdf,.bib
2010
4O. Tekdas, W. Yang, V. Isler
Robotic Routers: Algorithms and Implementation
Int. Journal of Robotics Research, 29(1), 2010.
pdf,.bib
2009
3O. Tekdas, Y. Kumar, V. Isler, R. Janardan
Building a Communication Bridge with Mobile Hubs
In 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), 2009.
pdf,.bib
2008
2E. Meisner, W. Yang, V. Isler
Network Formation through Coverage and Freeze-Tag
In Eighth International Workshop on the Algorithmic Foundations of Robotics, 2008.
pdf,.bib
1O. Tekdas, V. Isler
Robotic Routers
In Proc. IEEE Int. Conf. on Robotics and Automation, 2008.
pdf,.bib