任意拓扑结构Ad hoc网络的分布式一致性算法
A Distributed Consensus Algorithm for Ad hoc Networks in Arbitrary Topologies
作者：王征(电子科技大学 计算机科学与工程学院, 四川 成都 610054)；刘心松(电子科技大学 计算机科学与工程学院, 四川 成都 610054)；李美安(电子科技大学 计算机科学与工程学院, 四川 成都 610054)
Author：(School of Computer Sci. and Eng.,Univ. of Electronic Sci. and Technol. of China,Chengdu 610054,China)；(School of Computer Sci. and Eng.,Univ. of Electronic Sci. and Technol. of China,Chengdu 610054,China)；(School of Computer Sci. and Eng.,Univ. of Electronic Sci. and Technol. of China,Chengdu 610054,China)
收稿日期：2005-08-31 年卷（期）页码：2006,38(2):125-131
期刊名称：工程科学与技术
Journal Name：Advanced Engineering Sciences
关键字：Ad hoc；分布式一致性；互斥；任意拓扑结构；令牌查询；时戳
Key words：Ad hoc; distributed consensus; mutual exclusion; arbitrary topology; token-asking; timestamp
基金项目：四川省应用基础研究项目(04JY029-017-2)；科技型中小企业技术创新基金资助项目(04C26225110223)
中文摘要
为了解决Ad hoc网络中的分布式一致性问题，在对其特性分析的基础上，提出了新的Ad hoc模型以及新的Ad hoc分布式一致性算法ADC (Ad hoc Distributed Consensus)。这种算法基于传统的令牌查询，使用广播在任意拓扑结构的网络中查找令牌,同时，该算法使用带有Lamport时戳的请求消息和动态队列。较之传统算法，它能够较好的适应Ad hoc网络中节点频繁出入的情况。仿真与分析结果表明：该算法具有较低的消息复杂度、较小的空间复杂度和较短的响应延迟。
英文摘要
In order to solve the problem of distributed consensus in Ad hoc networks, the properties of Ad hoc were analyzed and a novel Ad hoc system model was proposed. Then a novel Ad hoc Distributed Consensus algorithm was put forward as ADC. Based on traditional token-asking algorithms, ADC utilizes broadcast to search the token in arbitrary topology networks, and emploies the request message with Lamport's timestamps and dynamic queues. Compared with traditional algorithms, ADC adapts itself to the frequent arrival/departures of nodes in Ad hoc networks. Simulation and analysis results showed that the ADC algorithm has low message complexity, small space complexity and short response delay.
【关闭】
