条件BC网络上独立生成树及其性质的研究

独立生成树（IST）在提高互连网络数据传输的可靠性和效率方面具有重要的作用，但在一般网络上独立生成树的存在性问题迄今仍是一个猜想。BC网络包含超立方体及其若干个性质优越的变型，但除超立方体和局部扭立方体之外，其它BC网络上IST的存在性和构造问题仍然没有得到解决，主要表现在：现有方法不适用于所有现存的超立方体的变型并且缺乏IST性质（高度与同构性）方面的研究；在超立方体及其变型上缺乏有关IST应用的研究。本项目的研究内容包括：研究几种特殊BC网络上的IST的存在性及构造问题；总结这些构造方法的共性，提出包含超立方体及其所有现存变型的一类BC网络- - 条件BC网络的定义，给出在条件BC网络上IST的存在性证明和相应的构造算法；改进上述算法，使所得到的IST的高度和结构得到优化；将由优化构造方法得到的特殊BC网络上的IST应用到结构化P2P系统中，并与文献中的相关P2P系统的运行性能进行比较。

独立生成树（IST）在提高互连网络数据传输的可靠性和效率方面具有重要的作用，但在一般网络上IST的存在性问题迄今仍是一个猜想。BC网络包含超立方体及其若干个性质优越的变型，但除超立方体Qn和局部扭立方体LTQn之外，其它BC网络上IST的存在性和构造问题仍然没有得到解决，主要表现在：现有方法不适用于所有现存的Qn的变型并且缺乏IST性质（高度与同构性）方面的研究；在Qn及其变型上缺乏有关IST应用的研究。. 我们采用从特殊到一般的方法研究了条件BC网络上IST的构造问题，主要研究成果包括：.1. 交叉立方体CQn上IST的构造. 提出了地址变换方法并用其证明了CQn上存在以任一顶点为根的n棵IST并给出了IST的串行构造算法；依据维扩散性质给出了优化的IST（结构均同构于类二项树，高度均为n+1）的并行构造算法。.2. 扭立方体TQn上IST的构造. 将TQn的维从奇数扩展到全体正整数，证明其上存在以任一顶点为根的n棵IST并给出了其串行构造算法；基于邻接拉丁方的思想给出了TQn上IST的并行构造算法。.3. 莫比乌斯立方体Mn上IST的构造. 揭示了Mn上顶点之间的维邻接关系，证明了Mn上存在以任一顶点为根的n棵IST并给出了相应的串行构造算法；通过引入圆排列的概念给出了IST的并行构造算法。.4. 奇偶立方体PQn上IST的构造. 扩展了PQn的定义，提出划分子树的概念以及根据顶点度数选取划分点集的方法，在此基础上证明了PQn上存在以任一顶点为根的n棵IST并给出了其串行构造算法。.5. 条件BC网络XCn上IST的构造. 研究了基于特殊BC网络如Qn、CQn、TQn、Mn等的共性来构造其上IST的一般性方法：给出了条件BC网络XCn的定义并证明其上存在以任一顶点为根的n棵优化的IST（结构均同构于类二项树，高度均为n+1）；针对任意BC网络Xn，提出维的V排列的定义并用其构造Xn上多组两两独立的IST。.6. 将Qn、CQn、LTQn、Mn等上的IST应用到结构化P2P系统中，并从平均路由延时、动态维护开销等方面通过模拟实验与现有文献进行了比较。. 此外，我们还根据该方向近年来新的研究动态，增加了与BC网络相关的一些新的研究内容，如PQn和Mn上的完全二叉树构造、LTQn网络上的完全独立生成树构造等。