论文部分内容阅读
选举问题和时钟同步问题是分布式计算中的两个基本问题。本文主要围绕这两个问题展开研究,提出了一个自稳定的选举算法和一个基于Ad Hoc网络的时钟同步算法。选举问题一直受到广泛关注,先后发表了一大批研究论文。但是,现有的研究较少涉及选举算法的自稳定性,已经提出的自稳定选举算法的性能还不能令人满意。本文针对两个经典的自稳定选举算法——AG算法和DIM算法进行了分析。AG算法适用于基于标识的网络,算法虽然简单,但算法需要假设网络的大小是已知的并且时间复杂度为O (n~2),其中n表示网络结点数目。DIM算法虽不需要网络大小假设是已知的,但其时间复杂度仍然需要O ( ?D log n),其中?和D分别表示结点最大的度和树的深度。我们利用DIM算法的思想,在AG算法的基础上,提出了基于命名网络的自稳定选举算法。该算法不需要知道网络的大小,而且时间复杂度为O (δ)(δ为网络直径)。此外,所有自稳定选举算法都未能考虑现实中的分层网络结构(主机接入在子网中,而子网又接入主干网),互连的拓扑结构不是“一般的图”。在设计实际的网络协议时,可以利用这个实际情况,比如分层的DNS和NTP以及分层路由等。显然,现实需要更灵活的算法,要求这些算法能够适应网络配置的变化。为了构造这样的算法,我们使用附加的逻辑结构,使得分布式算法能够适应不同种类的网络配置,提高了原来自稳定的选举领导人算法的时间效率并允许系统包含故障。有线网络中的时钟同步算法日臻完美,无论是在效率还是容错方面,但是,基于Ad Hoc网络的时钟同步问题却很少有人研究。随着Ad Hoc网络的发展,对QoS的要求越来越高。由于Ad Hoc网络不具备传统蜂窝网络中的基站,所有结点是对等的,所以,如何对Ad Hoc网络提供QoS保障问题具有很大的挑战性。网络时钟同步是其中很重要的部分,它对Ad Hoc网络提供QoS保障具有十分重要的作用。目前,Ad Hoc网络的许多时钟同步协议都是基于IEEE 802.11中提出的时钟同步功能TSF来进行改进的。TSF实现了Ad Hoc网络时钟同步的方法,但是该方法随着网络规模的增大,时钟精度急剧下降,严重限制了Ad Hoc