ALCOMFT-TR-01-62

Ioannis Chatzigiannakis, Sotiris Nikoletseas and Paul Spirakis
An Efficient Routing Protocol for Hierarchical Ad-hoc Mobile Networks
Patras. Work packages 2 and 5. May 2001.

Abstract: We introduce a new model of ad-hoc mobile networks, which we call hierarchical, that are comprised of dense subnetworks of mobile users (corresponding to highly populated geographical areas, such as cities), interconnected across access ports by sparse but frequently used connections (such as highways).

For such networks, we present an efficient routing protocol which extends the idea (introduced in [WAE00]) of exploiting the co-ordinated motion of a small part of an ad-hoc mobile network (the ``support'') to achieve very fast communication between any two mobile users of the network. The basic idea of the new protocol presented here is, instead of using a unique (large) support for the whole network, to employ a hierarchy of (small) supports (one for each city) and also take advantage of the regular traffic of mobile users across the interconnection highways to communicate between cities.

We combine here theoretical analysis (average case estimations based on random walk properties) and experimental implementations (carried out using the LEDA platform) to claim and validate results showing that such a hierarchical routing approach is, for this class of ad-hoc mobile networks, significantly more efficient than a simple extension of the basic ``support'' idea presented in [WAE00].

Postscript file: ALCOMFT-TR-01-62.ps.gz (132 kb).