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