| Ad hoc distributed mutual exclusion algorithm based on token-asking |
| |
| 基金项目： | 四川省应用基础研究计划 |
| |
| 摘 要： | 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.
|
| 收稿时间： | 29 November 2005 |
Ad hoc distributed mutual exclusion algorithm based on token-asking |
| |
| Authors: | Wang Zheng Liu Xin song Li Mei'an |
| |
| Institution: | 1. 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
2. 8010 R&D Computer Science and Engineering College, Univ. of Electronic Science and Technology,Chengdu 610054, P.R.China |
| |
| Abstract: | 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. |
| |
| Keywords: | Ad hoc Distributed mutual exclusion Token-asking Logical timestamp |
| 本文献已被 万方数据 ScienceDirect 等数据库收录！ |
| 点击此处可从《系统工程与电子技术(英文版)》浏览原始摘要信息 |
| 点击此处可从《系统工程与电子技术(英文版)》下载免费的PDF全文 |
