Analysis and experimental evaluation of an innovative and efficient routing protocol for ad-hoc mobile networks

An ad-hoc mobile network is a collection of mobile hosts, with wireless communication capability, forming a temporary network without the aid of any established fixed infrastructure. In such a (dynamically changing) network it is not at all easy to avoid broadcasting (and flooding). In this paper we propose, theoretically analyse and experimentally validate a new and efficient protocol for pairwise communication. The protocol exploits the co-ordinated motion of a small part of the network (i.e. it is a semi-compulsory protocol) in order to provide to various senders and receivers an efficient support for message passing. Our implementation platform is the LEDA system and we have tested the protocol for three classes of graphs (grids, random graphs and bipartite multi-stage graphs) each abstracting a different "motion topology". Our theoretical analysis (based on properties of random walks) and our experimental measurements indicate that only a small fraction of the mobile stations are enough to be exploited by the support in order to achieve very fast communication between any pair of mobile stations. © Springer-Verlag Berlin Heidelberg 2001.