Ad hoc distributed mutual exclusion algorithm based on token-asking

作     者：Wang Zheng Liu Xin'song Li Mei'an 

作者机构：School of Economic Information Engineering Southwestern Univ. of Finance and Economics Chengdu 610074 P.R.China 8010 R&D Computer Science and Engineering College Univ. of Electronic Science and Technology Chengdu 610054 P.R.China 

出 版 物：《Journal of Systems Engineering and Electronics》 (系统工程与电子技术（英文版）)

年 卷 期：2007年第18卷第2期

页      面：398-406页

核心收录：

学科分类：07[理学] 08[工学] 070104[理学-应用数学] 0701[理学-数学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：the Application Fundamental Research Foundation of Sichuan Province, China(04JY029-017-2) the Innovation Fund for Small Technology-based Firms China(04JY029-017-2) 

主　　题：Ad hoc Distributed mutual exclusion Token-asking Logical timestamp. 

摘      要：The solution of distributed mutual exclusion is difficult 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 the fixed 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.