A localized algorithm for bi-connectivity of connected mobile robots

Shantanu Das*, Hai LIU, Amiya Nayak, Ivan Stojmenović

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

41 Citations (Scopus)


Teams of multiple mobile robots may communicate with each-other using a wireless ad-hoc network. Faulttolerance in communication can be achieved by making the communication network bi-connected. We present the first localized protocol for constructing a fault-tolerant biconnected robotic network topology from a connected network, in such a way that the total movement of robots is minimized. The proposed distributed algorithm uses p-hop neighbor information to identify critical head robots that can direct two neighbors to move toward each other and bi-connect their neighborhood. Simulation results show that the total distance of movement of robots decreases significantly (e.g. about 2.5 times for networks with density 10) with our localized algorithm when compared to the existing globalized one. Proposed localized algorithm does not guarantee bi-connectivity, may partition the network, and may even stop at connected but not bi-connected stage. However, our algorithm achieved 100% success on all networks with average degrees ≥ 10, and over 70% success on sparse networks with average degrees ≥ 5.

Original languageEnglish
Pages (from-to)129-140
Number of pages12
JournalTelecommunication Systems
Issue number3-4
Publication statusPublished - Apr 2009

Scopus Subject Areas

  • Electrical and Electronic Engineering

User-Defined Keywords

  • Distributed algorithm
  • Fault tolerance
  • Localized movement control
  • Mobile sensors
  • Robot networks


Dive into the research topics of 'A localized algorithm for bi-connectivity of connected mobile robots'. Together they form a unique fingerprint.

Cite this