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

Adaptive Distributed Mutual Exclusion Algorithm for Ad Hoc Networks

作　　者：王征[1] 刘心松[1] 李美安[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,四川成都610054

出　　处：《小型微型计算机系统》2007年第8期1387-1392,共6页Journal of Chinese Computer Systems

基　　金：四川应用基础研究项目(04JY029-017-2)资助;科技型中小企业技术创新基金(04C26225110223)资助

摘　　要：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.

关 键 词：AD HOC 分布式互斥算法 令牌查询 逻辑时戳 消息复杂度 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]