A dual-token-based fault tolerant mutual exclusion algorithm for MANETs

Weigang Wu, Jiannong Cao, Michel Raynal

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

12 Citations (Scopus)

Abstract

Most existing mutual exclusion algorithms for mobile ad hoc networks (MANETs) adopt a token-based approach. In traditional wired networks, timeout-based mechanisms are commonly used to detect token losses. However, in MANETs, it is difficult to set a proper timeout value due to the network dynamics. In this paper, we propose a dual-token-based mutual exclusion algorithm, which can tolerate token losses without using timeout. Two tokens are concurrently circulated in the system to monitor each other by using sequence numbers. If one token is lost, the other token can detect the loss and regenerate a new token. Simulations have been carried out to evaluate the effectiveness and performance of the proposed algorithm in comparison with the timeout-based approach. The results show that the timeout-based algorithm may falsely claim the loss of a token, thus cannot guarantee the correctness of mutual exclusion algorithms. On the contrary, our proposed algorithm can avoid false detection of token losses and satisfy all the correctness requirements of mutual exclusion, though it costs a bit more messages and longer time.
Original languageEnglish
Title of host publicationMobile Ad-hoc and Sensor Networks - Third International Conference, MSN 2007, Proceedings
Pages572-583
Number of pages12
Publication statusPublished - 1 Dec 2007
Event3rd International Conference on Mobile Ad-hoc and Sensor Networks, MSN 2007 - Beijing, China
Duration: 12 Dec 200714 Dec 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4864 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Conference on Mobile Ad-hoc and Sensor Networks, MSN 2007
Country/TerritoryChina
CityBeijing
Period12/12/0714/12/07

Keywords

  • Distributed algorithm
  • MANET
  • Mobile computing
  • Mutual exclusion
  • Token loss

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this