摘要
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.
出处
《小型微型计算机系统》
CSCD
北大核心
2007年第8期1387-1392,共6页
Journal of Chinese Computer Systems
基金
四川应用基础研究项目(04JY029-017-2)资助
科技型中小企业技术创新基金(04C26225110223)资助