Abstract
Teams of multiple mobile robots may communicate with each-other using a wireless ad-hoc network. Fault-tolerance in communication can be achieved by making the communication network bi-connected. We present the first localized protocol for constructing a fault-tolerant bi-connected 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bahramgiri, M., Hajiaghayi, M., & Mirrokni, V. (2002). Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks. In Proc. IEEE int. conf. on computer communications and networks (ICCCN02) (pp. 392–398).
Basu, P., & Redi, J. (2004). Movement control algorithms for realization of fault-tolerant ad hoc robot networks. IEEE Network, 18(4), 36–44.
Chow, R., & Johnson, T. (1997). Distributed operating systems & algorithms. Reading/New York: Addison Wesley/Longman.
Cheriyan, J., Vempala, S., & Vetta, A. (2003). An approximation algorithm for the minimum-cost k-vertex connected subgraph. SIAM Journal Computing, 32(4), 1050–1055.
Dynia, M., Kutylowski, J., Lorek, P., & Meyer auf der Heide, F. (2006). Maintaining communication between an explorer and a base station. In IFIP conf. on biologically inspired cooperative computing (BICC’06) (Vol. 216, pp. 137–146).
Jorgic, M., Stojmenovic, I., Hauspie, M., & Simplot-Ryl, D. (2004). Localized algorithms for detection of critical nodes and links for connectivity in ad hoc networks. In Proc. 3rd ann. med. ad-hoc networking workshop (Med-Hoc-Net) (pp. 360–371).
Li, N., & Hou, J. C. (2004). Topology control in heterogeneous wireless networks: problems and solutions. In Proc. IEEE INFOCOM (pp. 232–243).
Li, N., & Hou, J. C. (2004). FLSS: a fault-tolerant topology control algorithm for wireless networks. In Proc. 10th ann. int. conf. on mobile computing and networking (pp. 275–286).
Liu, H., Wan, P. J., & Jia, X. (2005). Fault-tolerant relay node placement in wireless sensor networks. In Proc. COCOON (pp. 230–239).
Ramanathan, R., & Rosales-Hain, R. (2000). Topology control of multihop wireless networks using transmit power adjustment. In Proc. IEEE Infocom (Vol. 2, pp. 404–413).
Vass, D., & Vidács, A. (2005). Positioning mobile base station to prolong wireless sensor network lifetime. CoNEXT 2005 student workshop (pp. 300–301).
Younis, O., Fahmy, S., & Santi, P. (2004). Robust communications for sensor networks in hostile environments. In Proc. 12th IEEE int. workshop on quality of service (IWQoS) (pp. 10–19).
Author information
Authors and Affiliations
Corresponding author
Additional information
Most of this work was done while the first and second authors were at the School of Information Technology and Engineering, University of Ottawa, Canada.
Rights and permissions
About this article
Cite this article
Das, S., Liu, H., Nayak, A. et al. A localized algorithm for bi-connectivity of connected mobile robots. Telecommun Syst 40, 129–140 (2009). https://doi.org/10.1007/s11235-008-9134-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11235-008-9134-9