Consensus in Sparse, Mobile Ad Hoc Networks

  1. Lookup NU author(s)
  2. Dr Khaled Alekeish
  3. Dr Paul Ezhilchelvan
Author(s)Alekeish K, Ezhilchelvan P
Publication type Article
JournalIEEE Transactions on Parallel and Distributed Systems
ISSN (print)1045-9219
ISSN (electronic)1558-2183
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.
PublisherIEEE Computer Society
Actions    Link to this publication

Altmetrics provided by Altmetric