高性能并行计算机互联网络容错模型及其路由算法研究

摘要

由于均具有正则性、对称性、可嵌入性、并行性、以及良好的容错性与网络通信能力的可扩展性等优良特性，超立方体(Hypercube)和彼特森图(PetersenGraph)互联网络受到了研究者们的广泛关注，是迄今为止最为重要和最具吸引力的并行计算机互联网络拓扑结构之一。随着现在的并行计算机互联网络规模越来越大，网络中出现处理机故障或处理机间的链路故障的可能性也越来越大；这就使得并行计算机互联网络的容错性及其研究也变得越来越重要，因此，设计具有较好容错性的路由算法对并行计算机互联网络有着重要意义。 到目前为止，人们已经对超立方体或彼特森图互联网络的拓扑特性及其容错模型与容错路由算法方面分别进行了深入的研究，并基于超立方体或彼特森图互联网络的拓扑特性分别建立了一些容错模型及其容错路由算法，但上述研究均是针对超立方体或彼特森图互联网络单独进行的，缺乏对这两种互联网络系统的综合研究。超立方体和彼特森图互联网络虽然在本质上各不相同，但由于它们均具有正则性、对称性、可嵌入性、并行性、以及良好的容错性与网络通信能力的可扩展性等优良特性，在拓扑特性上具有很大程度的相似性，而且还可以通过相互结合形成具有某些特殊性质的新型互联网络拓扑结构，因此，将超立方体和彼特森图互联网络综合起来进行系统深入的研究，将比对其中的单个网络进行孤立研究具有更好的效果，能更进一步地促进对这两种互联网络乃至整个高性能并行计算机互联网络的研究发展，特别地，取两个网络拓扑特性之长来弥补各自之短，研究如何利用超立方体互联网络的可扩展性和彼特森图互联网络的短直径特性来构造出具有更优特性的新型并行计算机互联网络，将具有重要的研究价值。综上所述，本文综合系统地研究超立方体和彼特森图这两种具有相似拓扑特性的高性能并行计算机互联网络的拓扑特性及其容错模型与容错路由算法。 在对超立方体互联网络的拓扑特性及其容错模型与容错路由算法方面，本文首先综述了目前国内、国际上在超立方体互联网络研究方面所做的主要研究工作，并基于已有的一些研究成果，提出了三种新的超立方体互联网络的容错模型及其容错路由算法：即基于极大安全通路向量的容错模型MSPV(MaximalSafetyPathVector)及其容错路由算法、基于极大安全通路矩阵的容错模型MSPM(MaximalSafetyPathMatrix)及其容错路由算法，以及基于两类子连通性的超立方体互联网络容错模型及其容错路由算法；证明了上述超立方体互联网络的容错模型及其容错路由算法分别是基于安全向量的容错模型SV(SafetyVector)、基于扩展安全向量的容错模型ESV(ExtendedSafetyVector)、基于最优通路矩阵的容错模型OPM(OptimalPathMatrix)、基于扩展最优通路矩阵的容错模型EOPM(ExtendedOptimalPathMatrix)、以及基于两类子立方体局部连通性的超立方体互联网络容错模型及其容错路由算法的极大扩展，因此具有比它们更强的容错能力。 在对彼特森图互联网络的拓扑特性及其容错模型与容错路由算法方面，本文首先综述了目前国内、国际上在彼特森图互联网络研究方面所做的主要研究工作，并基于已有的一些研究成果，提出了两种新的彼特森图互联网络及其容错模型与容错路由算法：即双环彼特森图互联网络DLCP(k)(Double-LoopsConnectedPetersenGraph)及其容错模型与容错路由算法、层次双环彼特森图互联网络HDLCP(k)(HierarchicalDouble-LoopsConnectedPetersenGraph)及其容错模型与容错路由算法；并对DLCP(k)和HDLCP(k)互联网络的连接度、网络直径、以及网络的可扩展性与可分组性等特性进行了分析，证明了DLCP(k)和HDLCP(k)互联网络在网络直径、可分组性、以及网络节点的连接度等性能指标上，具有比二维Torus互联网络以及超立方体互联网络更优的拓扑性能。另外，本文还分别给出了DLCP(k)和HDLCP(k)互联网络上的容错路由算法，仿真实验表明，算法具有良好的容错性能。 另外，本文还对超立方体和彼特森图互联网络进行了综合研究，结合彼特森图的短直径和超立方体互联网络的可扩展性，提出了一种基于彼特森图连接的新型超立方体互联网络HCPG(k)(Hyper-cubesConnectedPetersenGraph)，并对其特性进行了研究。证明了HCPG(k)互联网络在保持超立方体和彼特森图互联网络所共有的正则性和对称性等优良特性的情况下，而且还兼具有超立方体互联网络的可扩展性与彼特森图互联网络所特有的短直径等良好特性：即HCPG(k)互联网络不但比现有的超立方体互联网络Qk(Hypercube)、环彼特森图互联网络RP(k)(Ringed-Petersen)，以及超彼特森图互联网络HP(k)(Hyper-Petersen)等具有更多的节点数，且其构造开销更小。因此，HCPG(k)是一种具有比上述互联网络更好可扩展性的新型高性能并行计算机互联网络拓扑结果。另外，本文还基于HCPG(k)互联网络设计了其上的容错路由算法，证明了其具有良好的容错性能。 最后，本文对超立方体模型的应用进行了研究，提出了一种新的层次超立方体模型，并将其应用到传感器网络的对偶密钥建立过程，基于超立方体模型的强容错性能，提出了一种新型基于层次超立方体模型的传感器网络对偶密钥建立算法。理论分析与实验结果表明，新算法具有良好的加密性能，低的通信和存储开销，较高的直接对偶密钥建立概率，因此是一种适合传感器网络特点的新型对偶密钥建立算法。

目录

文摘

英文文摘

论文说明：插图索引、附表索引

湖南大学学位论文原创性声明及版权使用授权书

第1章绪论

1.1超立方体与彼特森图互联网络简介

1.1.1超立方体互联网络简介

1.1.2彼特森图互联网络简介

1.1.3超立方体与彼特森图互联网络的比较

1.2课题的研究意义

1.3国内外研究现状分析

1.3.1超立方体与彼特森图网络拓扑特性研究

1.3.2超立方体和彼特森图网络容错模型研究

1.3.3超立方体和彼特森图网络容错路由研究

1.4课题的主要研究内容

1.5论文的组织结构

第2章极大安全通路向量容错模型及路由

2.1概述

2.2基于极大安全通路向量的容错模型

2.2.1容错模型的构造

2.2.2容错模型的性质

2.3基于极大安全通路向量容错模型的容错路由算法

2.4算法性能分析及实验结果

2.5本章小结

第3章极大安全通路矩阵容错模型及路由

3.1概述

3.2基于极大安全通路矩阵的容错模型

3.2.1容错模型的构造

3.2.2容错模型的性质

3.3基于极大安全通路矩阵容错模型的容错路由算法

3.4算法性能分析及实验结果

3.5本章小结

第4章两类子连通性容错模型及路由算法研究

4.1概述

4.2基于两类子连通性的容错模型

4.2.1容错模型的构造

4.2.2容错模型的性质

4.3基于两类子连通性容错模型的容错路由算法

4.4算法性能分析及实验结果

4.5本章小结

第5章双环彼特森图互联网络及路由研究

5.1概述

5.2双环彼特森图互联网络

5.2.1双环彼特森图互联网络的构造

5.2.2双环彼特森图互联网络的性质

5.3双环彼特森图互联网络的路由算法研究

5.4算法性能分析及实验结果

5.4.1单播路由算法的性能分析

5.4.2广播路由算法的性能分析

5.4.3容错路由算法的性能分析

5.5本章小结

第6章 层次双环彼特森图互联网络及路由

6.1概述

6.2层次双环彼特森图互联网络

6.2.1层次双环彼特森图互联网络的构造

6.2.2层次双环彼特森图互联网络的性质

6.3层次双环彼特森图互联网络的路由算法研究

6.4算法性能分析及实验结果

6.4.1单播路由算法的性能分析

6.4.2广播路由算法的性能分析

6.4.3容错路由算法的性能分析

6.5本章小结

第7章 超立方体连接的彼特森图互联网络

7.1概述

7.2超立方体连接的彼特森图互联网络

7.2.1超立方体连接的彼特森图互联网络的构造

7.2.2超立方体连接的彼特森图互联网络的性质

7.3超立方体连接的彼特森图网络路由研究

7.3.1超立方体连接的彼特森图网络的单播路由算法

7.3.2超立方体连接的彼特森图网络的广播路由算法

7.3.3超立方体连接的彼特森图网络的容错路由算法

7.4算法性能分析及实验结果

7.4.1单播路由算法的性能分析

7.4.2广播路由算法的性能分析

7.4.3容错路由算法的性能分析

7.5本章小结

结论

参考文献

致谢

附录A攻博期间参与科研项目情况及发表论文情况

附录B传感器网络中基于层次超立方体模型的对偶密钥建立算法

B.1概述

B.2预备知识

B.3层次超立方体模型

B.4传感器网络中的基于H2模型的对偶密钥算法

B.5算法分析

B.6小结