Encounter-based message propagation in mobile ad-hoc networks

A family of message propagation protocols for highly mobile ad-hoc networks is defined, and is studied analytically and by simulation. The coverage of a message (the fraction of nodes that receive it), can be made arbitrarily close to 1, at a moderate cost of extra message traffic. Under certain simplifying assumptions, it is shown that a high coverage is achieved by making a total of O(n ln n) broadcasts, where n is the number of nodes, and the time to propagate a message is O(ln n). Mechanisms for making the protocols more efficient, by reducing the number of redundant transmissions without affecting the achievable coverage, are presented and evaluated. The generalisation to multiple broadcasts proceeding in parallel is derived. Finally, an attempt to validate the proposals in the context of a real-life mobile ad-hoc network is described. Results of this validation exercise and simulations point out that the proposed protocols can cost-effectively achieve high coverage in networks of varying degrees of node densities and mobilities. We acknowledge the financial support from the UK EPSRC Projects “Networked Computing in Inter-organisation Settings” (EP/D037743/1) and “Protocols for Ad-hoc Collaborative Environments” (GR/S02082/01).