research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:ichatz
TitleAn Efficient Communication Strategy for Ad-hoc Mobile Networks
Bibtex cite IDRACTI-RU1-2001-8
Booktitle 15th Symposium on Distributed Computing (DISC)
Series Lecture Notes in Computer Science
Year published 2001
Month October
Volume 2180
Pages 285-299
Publisher Springer Verlag
Location Lisbon, Portugal
Keywords Mobile Adhoc Networks
We investigate the problem of 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 for 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 that avoids message flooding. Our protocol manages to establish communication between any pair of mobile hosts in small, a-priori guaranteed expected time bounds even in the worst case of arbitrary motions of the hosts that not in 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.
Chatzigiannakis, Ioannis
Nikoletseas, Sotiris
Spirakis, Paul
disc01ichatz.pdf (main file)
Publication ID242