Ad hoc distributed mutual exclusion algorithm based on token-asking*

The solution of distributed mutual exclusion is dificult in Ad hoc networks owing to dynamic topologies and mobility. Based on the analysis of the properties of Ad hoc networks and the disadvantages of the traditional algorithms, an improved Ad hoc system model was given and a novel algorithm was presented as AHDME (Ad Hoc Distributed Mutual Exclusion);it was based on the token-asking algorithms. It utilized broadcast to search for the token and to decrease the message complexity of multi-hop Ad hoc networks. Lamport's timestamp was improved to ensure the time sequence and to prevent nodes from starvation. When compared to traditional algorithms, AHDME does not require theffxed size of request queues and the global system information, which adapts itself to the frequent arrival/departures and the limited computing capability of nodes in Ad hoc networks. Performance analysis and simulation results show that the AHDME algorithm has low message complexity, small space complexity, and short response delay.