Skip to main content
Open Access Publications from the University of California

Coalescence for Mobile Sensor Networks


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, memory less 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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View