Achieving Connectivity through Coalescence in Mobile Robot Networks

Sameera Poduri; Gaurav S. Sukhatme Sukhatme

1st International ICST Conference on Robot Communication and Coordination

Research Article

Achieving Connectivity through Coalescence in Mobile Robot Networks

Download471 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/ICST.ROBOCOMM2007.2272,
    author={Sameera Poduri and Gaurav S. Sukhatme Sukhatme},
    title={Achieving Connectivity through Coalescence in Mobile Robot Networks},
    proceedings={1st International ICST Conference on Robot Communication and Coordination},
    proceedings_a={ROBOCOMM},
    year={2010},
    month={5},
    keywords={robot networks connectivity coalescence},
    doi={10.4108/ICST.ROBOCOMM2007.2272}
}

Sameera Poduri
Gaurav S. Sukhatme Sukhatme
Year: 2010
Achieving Connectivity through Coalescence in Mobile Robot Networks
ROBOCOMM
ICST
DOI: 10.4108/ICST.ROBOCOMM2007.2272

Sameera Poduri¹^,*, Gaurav S. Sukhatme Sukhatme²^,*

1: Department of Computer Science University of Southern California Los Angeles, CA-90089
2: 1Department of Computer Science,Department of Electrical Engineering University of Southern California Los Angeles, CA-90089

*Contact email: sameera@usc.edu, gaurav@usc.edu

Abstract

Coalescence is the problem of isolated mobile robots independently searching for peers with the goal of forming a single connected network. This paper analyzes coalescence time for a worst-case scenario where the robots do not have any knowledge about the environment or positions of other robots and perform independent, memoryless search. Using the random direction mobility model, we show that coalescence time has an exponential distribution which is a function of the number of robots, speed, communication range, and size of the domain. Further, as the number of robots (N) increases, coalescence time decreases as O(1/sqrt(N)) and Omega(log(N)/N). Simulations validate our analysis and also suggest that the lower bound is tight. This paper is an extension of [1] where we studied a simplified setting with a stationary base station that the robots search for and coalesce to.

Keywords: robot networks connectivity coalescence

Published: 2010-05-16
Modified: 2010-05-16

: http://dx.doi.org/10.4108/ICST.ROBOCOMM2007.2272