ALCOMFT-TR-02-72

Ioannis Chatzigiannakis, Sotiris Nikoletseas and Paul Spirakis
On the Average and Worst-case Efficiency of Some New Distributed Algorithms for Communication and Control in Ad-hoc Mobile Networks
Patras. Work packages 2 and 4. May 2002.

Abstract: An ad-hoc mobile network is a collection of mobile hosts, with wireless communication capabilities, forming a temporary network without the aid of any established fixed infrastructure.

In such networks, topological connectivity is subject to frequent, unpredictable change. Our work focuses on networks with high rate of such changes to connectivity. For such dynamic changing networks we propose protocols which exploit the co-ordinated (by the protocol) motion of a small part of the network. We show that such protocols can be designed to work correctly and efficiently even in the case of arbitrary (but not malicious) movements of the hosts not affected by the protocol.

We also propose a methodology for the analysis of the expected behaviour of protocols for such networks, based on the assumption that mobile hosts (whose motion is not guided by the protocol) conduct concurrent random walks in their motion space.

Our work examines some fundamental problems such as pair-wise communication, election of a leader and counting, and proposes distributed algorithms for each of them. We provide their proofs of correctness, and also give rigorous analysis by combinatorial tools and also via experiments.

Postscript file: ALCOMFT-TR-02-72.ps.gz (165 kb).