Toggle Main Menu Toggle Search


Consensus in Sparse, Mobile Ad Hoc Networks

Lookup NU author(s): Dr Khaled Alekeish, Dr Paul Ezhilchelvan


Full text for this publication is not currently held within this repository. Alternative links are provided below where available.


Ad-hoc networking is the only means available for collaboration amongst mobile users in terrains (e.g., deserts or disaster-struck areas) that are devoid or deprived of wireless infrastructures. Consensus is at the heart of any collaboration, as it solves the problem of two or more entities (e.g., mobile users) proposing possibly different alternatives and agreeing unanimously on a single proposed alternative for the next action step. The problem however is fundamentally unsolvable using a deterministic solution, if an entity can remain incommunicable with others for brief, albeit unknown, durations. Scenarios of incommunicability are more likely as a mobile user goes outside the wireless range of his peers; also, the duartions of such temporary 'absences' are harder to predict as they are determined mainly by the purposes of user movements. The paper develops and a randomized consnsus protocol for contexts where users can frequently remain dispersed over a large area, frequently resulting in sparse patches containing fewer users per unit area. It is the first of its kind to address consensus for sparse ad-hoc networks. It establishes the liveness condition any ad-hoc network must satisfy for consensus to be solvable using the randomized approach. In a nutshell, user movements and wireless range must allow any two sub-groups of mobile users to communicate eventually when the information hopped over all available wireless links. When the maximum number of hops necessary is bounded by a small and known constant, by a large and known constant, or by an unknown constant, an adhoc network is classified as dense, sparse and delay-tolerant. Existing protocols are argued not to have been built for sparse networks. Performance of the developed protocol for sparse networks is evaluated simulations which show the effects of randomization in speeding up the consensus when network gets sparser.

Publication metadata

Author(s): Alekeish K, Ezhilchelvan P

Publication type: Article

Journal: IEEE Transactions on Parallel and Distributed Systems

Year: 2012

Volume: 23

Issue: 3

Pages: 467-474

Print publication date: 23/06/2011

ISSN (print): 1045-9219

ISSN (electronic): 1558-2183

Publisher: IEEE Computer Society


DOI: 10.1109/TPDS.2011.182


Altmetrics provided by Altmetric


    Link to this publication