ALCOMFT-TR-01-117

Ioannis Chatzigiannakis, Sotiris Nikoletseas and Paul Spirakis
An Efficient Communication Strategy for Ad-hoc Mobile Networks
Patras. Work packages 2 and 4. May 2001.

Abstract: We investigate here the problem of establishing communication in an ad-hoc mobile network, that is, we assume the extreme case of a total absense of any fixed network infrastructure (for example a case of rapid deployment of a set of mobile hosts in an unknown terrain). We propose, in such a case, that a small subset of the deployed hosts (which we call the support) should be used to manage network operations. However, the vast majority of the hosts are moving arbitrarily according to application needs.

We then provide a simple, correct and efficient protocol for communication establishment that avoids message flooding. Our protocol manages to establish communication between any pair of mobile hosts in small, a-priori guaranteed time bounds even in the worst case of arbitrary motions of the hosts that do not belong to the support (provided that they do not deliberately try to avoid the support). These time bounds, interestingly, do not depend, on the number of mobile hosts that do not belong in the support. They depend only on the size of the area of motions. Our protocol can be implemented in very efficient ways by exploiting knowledge of the space of motions or by adding more power to the hosts of the support.

Our results exploit and further develop some fundamental properties of random walks in finite graphs.

Postscript file: ALCOMFT-TR-01-117.ps.gz (98 kb).