分布式计算中的选举问题和时钟同步问题的研究

摘要

选举问题和时钟同步问题是分布式计算中的两个基本问题。本文主要围绕这两个问题展开研究，提出了一个自稳定的选举算法和一个基于AdHoc网络的时钟同步算法。 选举问题一直受到广泛关注，先后发表了一大批研究论文。但是，现有的研究较少涉及选举算法的自稳定性，已经提出的自稳定选举算法的性能还不能令人满意。本文针对两个经典的自稳定选举算法——AG算法和DIM算法进行了分析。AG算法适用于基于标识的网络，算法虽然简单，但算法需要假设网络的大小是己知的并且时间复杂度为O(n2)，其中n表示网络结点数目。DIM算法虽不需要网络大小假设是已知的，但其时间复杂度仍然需要O(△Dlogn)，其中△和D分别表示结点最大的度和树的深度。我们利用DIM算法的思想，在AG算法的基础上，提出了基于命名网络的自稳定选举算法。该算法不需要知道网络的大小，而且时间复杂度为O(δ)(δ为网络直径)。此外，所有自稳定选举算法都未能考虑现实中的分层网络结构(主机接入在子网中，而子网又接入主干网)，互连的拓扑结构不是“一般的图”。在设计实际的网络协议时，可以利用这个实际情况，比如分层的DNS和NTP以及分层路由等。显然，现实需要更灵活的算法，要求这些算法能够适应网络配置的变化。为了构造这样的算法，我们使用附加的逻辑结构，使得分布式算法能够适应不同种类的网络配置，提高了原来自稳定的选举领导人算法的时间效率并允许系统包含故障。 有线网络中的时钟同步算法日臻完美，无论是在效率还是容错方面，但是，基于AdHoc网络的时钟同步问题却很少有人研究。随着AdHoc网络的发展，对QoS的要求越来越高。由于AdHoc网络不具备传统蜂窝网络中的基站，所有结点是对等的，所以，如何对AdHoc网络提供QoS保障问题具有很大的挑战性。网络时钟同步是其中很重要的部分，它对AdHoc网络提供QoS保障具有十分重要的作用。目前，AdHoc网络的许多时钟同步协议都是基于IEEE802.11中提出的时钟同步功能TSF来进行改进的。TSF实现了AdHoc网络时钟同步的方法，但是该方法随着网络规模的增大，时钟精度急剧下降，严重限制了AdHoc网络的可扩展性。 L.Huang和T.H.Lai提出的ATSP和T.H.Lai和D.Zhou提出的算法，都对TSF进行了改进，在一定程度上解决了网络结点数量增大时TSF性能急剧下降的问题。但是，随着网络规模的继续扩大，这些算法仍存在较大的时钟偏差，而且可扩展性问题会逐渐恶化。他们进一步改进的ABTSF算法采用TSF和令牌轮询混合模式，当运行TSF模式的结点数较多时，性能较差，同时它的时间是双向同步的，会使较快的时钟时间后退，与IEEE802.11TSF同步模式不兼容。目前，许多AdHoc网络的时钟同步协议都没能很好地解决可扩展性问题，而解决这个问题最主要的方法就是采用适当的分簇算法构造分层的网络拓扑结构。其中，相互邻近的一组结点构成一个簇，簇内的成员可分簇首、簇成员、网关三种。簇成员之间的通信通过簇首进行，簇与簇之间的通信则经过网关转发。本文基于这个思想，在原来算法的基础上，提出了基于分层AdHoc网络的时钟同步算法。

目录

文摘

英文文摘

厦门大学学位论文原创性声明及著作权使用声明

第一章绪论

1.1分布式系统与分布式算法

1.2分布式计算中的选举和时钟同步

1.3论文的主要工作

1.4论文的结构

第二章分布式计算中的选举算法和时钟同步算法的研究现状

2.1选举算法及自稳定性

2.2自稳定选举算法的研究现状

2.3基于Ah Hoc网络的时钟同步

2.4基于Ad Hoc网络的时钟同步的研究现状

第三章自稳定选举算法

3.1自稳定选举算法

3.2AG算法的改进

3.3基于分层网络的自稳定选举算法

3.4小结

第四章基于分层Ad Hoc网络的时钟同步算法

4.1问题的描述

4.2基于Ad Hoc网络的时钟同步算法

4.3基于分层Ad Hoc网络的时钟同步算法

4.4小结

第五章结论

参考文献

后记