A Non-Token-Based-Distributed Mutual Exclusion Algorithm for Single-Hop Mobile Ad Hoc Networks

Romain Mellier; Jean-Frederic Myoupo; Vlady Ravelomanana

doi:10.1007/0-387-23150-1_25

A Non-Token-Based-Distributed Mutual Exclusion Algorithm for Single-Hop Mobile Ad Hoc Networks

Romain Mellier, Jean-Frederic Myoupo, Vlady Ravelomanana

Source

IFIP — The International Federation for Information Processing > Mobile and Wireless Communication Networks > 287-298

Abstract

This paper presents a simple mutual exclusion algorithm for ad hoc mobile networks. Our algorithm does not use the token circulation technique. A station which requests a Critical Section (CS) competes in order to be alone to use the unique channel dedicated to this CS. To reach this goal, we derive a Markov process which guarantees that each station will enter the CS. More precisely, we show that, in presence of collision detection, n/ln2 broadcast rounds are necessary in the average case to satisfy n (n unknown) stations wishing to enter the same CS.