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
TitleSelf-Organizing Ad-Hoc Mobile Networks: The problem of end-to-end communication
Bibtex cite IDRACTI-RU1-2001-6
Booktitle 20th ACM Symposium on Principles of Distributed Computing (PODC)
Year published 2001
Month August
Pages 320-322
Publisher ACM Press
Organization ACM
Location Rhode Island, USA
Note Brief Announcement
Keywords Mobile Adhoc Networks
We investigate here the problem of establishing communication in an ad-hoc mobile network, that is, we assume the extreme case of a total absence 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.
Chatzigiannakis, Ioannis
Nikoletseas, Sotiris
Spirakis, Paul
podc01ichatz.pdf (main file)
Publication ID237