Title: Fault tolerant mutual and k-mutual exclusion algorithms for single-hop mobile ad hoc networks

Authors: Romain Mellier, Jean-Frederic Myoupo

Addresses: LaRIA, CNRS FRE 2733, Universite de Picardie Jules Verne, 33, rue Saint-Leu 80039, Amiens Cedex 1, France. ' LaRIA, CNRS FRE 2733, Universite de Picardie Jules Verne, 33, rue Saint-Leu 80039, Amiens Cedex 1, France

Abstract: Previous mutual exclusion (MUTEX for short) protocols for mobile ad hoc networks are based on the token circulation technique. They assume that the network is reliable to avoid starvation. Considering that the MUTEX issue is to share a communication channel, we have designed an average-case-analysis protocol for single-hop networks which is based on the fully distributed construction of a random binary tree. Contrarily to other papers, the stations are not identified and their number (n) is unknown. Assuming that time is slotted, our algorithm runs in approximately n/log 2 slots. The derived k-MUTEX protocol runs in n/log k slots.

Keywords: mutual exclusion; k-mutual exclusion; ad hoc networks; mobile networks; wireless networks; fault tolerant algorithms.

DOI: 10.1504/IJAHUC.2006.009885

International Journal of Ad Hoc and Ubiquitous Computing, 2006 Vol.1 No.3, pp.156 - 166

Published online: 24 May 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article