Toggle Main Menu Toggle Search


Encounter-Based Message Propagation in Mobile Ad-Hoc Networks

Lookup NU author(s): Dr Paul Ezhilchelvan, Emeritus Professor Isi Mitrani



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.

Publication metadata

Author(s): Cooper DE, Ezhilchelvan P, Mitrani I

Publication type: Article

Journal: Ad Hoc Networks

Year: 2009

Volume: 7

Issue: 7

Pages: 1271-1284

ISSN (print): 1570-8705

ISSN (electronic): 1570-8713

Publisher: Elsevier B.V.


DOI: 10.1016/j.adhoc.2008.12.003

Notes: Published online January 2009, in print September 2009. 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).


Altmetrics provided by Altmetric


    Link to this publication