自适应Ad hoc分布式互斥算法

Adaptive Distributed Mutual Exclusion Algorithm for Ad Hoc Networks

Ad hoc网络的动态拓扑结构和节点自组织给分布式算法的实现带来了诸多困难.针对Ad hoc分布式互斥算法研究滞后的现状,提出了一种自适应的Ad hoc分布式算法ADMUTEX.ADMUTEX算法基于令牌查询方法,它采用Lamport逻辑时戳保证消息的时序性,避免了节点饿死.同时,它在消息复杂度与同步延迟之间作了折衷,而且它不需要节点了解系统的全局信息,能够适应Ad hoc网络的动态拓扑结构和节点频繁出入的情况.分析与仿真结果表明该算法具有较低的消息复杂度、小响应延迟和公平性.

Ad hoc networks posses dynamic topologies and self-organized nodes, which stunts the implement of distributed mutual exclusion algorithms. Aiming at the comparatively laggard level of the distributed mutual exclusion algorithms for Ad hoc networks, an adaptive algorithm for Ad hoc networks was presented as ADMUTEX algorithm. Based on the token-asking algorithms, the novel algorithm guaranteed the time sequence and prevents nodes from starvation by Lamport logical timestamps. Furthermore, it made a trade-off between the message complexity and the synchronization delay. And the nodes did not initially need the global information of all the others in ADMUTEX algorithm, which adapted it to the dynamic topology structures in Ad hoc networks. Analysis and simulation results show that it has lower message complexity, shorter response delay and better fairness than the traditional algorithms.