基于二叉树的有向双环网络的最短路径算法

定义了有向双环网络G(N;r,s)新的路由模型--二叉树模型,给出了O节点到二叉树模型任意一层节点的最短路径的路南策略.证明了有向双环网络的直径等于其二叉树的树高,研究了任意两节点之问的最短路径与其所在层及其相应位置的关系,给出有向双环网络任意两节点最短路径的算法.运用此算法,只需简单的算术运算和关系运算,就能快速求出任意两节点的最短路径.     

基于树的无向双环网络G(N;±r,±s)寻径策略

提出了新的无向双环网络G(N;±r,±s)的直径求解方法,将其图论模型中的节点进行了重新排列,得到了一种基于树的路由模型,研究了该树型结构中与路由相关的一些性质;给出了计算无向双环嘲络G(N;±r,±s)直径d(N;±r,±s)的显式公式;证明了无向双环网络G(N;±r,±s)的直径等于树高;验证了Boe-sch和Wang等提出的无向双环网络G(N;±r,±s)直径的下界.     

有向双环网络的容错路由及容错直径

提出有向双环网络G(N;r,s)的容错路由及容错直径的概念,根据L-型瓦的叠加原理,研究了容错节点所对应的最优等价节点的分布规律.利用L-型瓦的4个参数a,b,p和q,给出有向双环网络G(N;r,s)的容错路由算法及其容错直径的计算公式.根据该算法进行容错路由,当有向双环网络G(N;r,s)中出现故障时,网络的可靠性和信息传输延迟将达到最佳状态.     

有向双环网络G(N;r,s)双紧优分布特性研究

提出双紧优的概念来构造高效的有向双环网络G(N;r,s),给出了任意有向双环网络的直径(D(N))和宽直径(D2(N))的定义及相关证明,得出了它们之间的关系D2(N)≥D(N)+1.给出了任意有向双环网络G(N;r,s)的双紧优点的仿真分布图.结果表明,有向双环网络G(N;r,s)的紧优点不一定是双紧优点,且双紧优点的分布无规律.     

无向双环网络G(N;±r,±s)直径求解方法

提出新的无向双环网络G(N;±r,±s)的直径求解法———分步法;并得到一种新的直观图———螺旋环,研究了螺旋环的性质;给出了无向双环网络的直径d(N;±r,±s)的显式公式;给出了N,s都固定的直径算法;在N固定,且2≤r相似文献   

关于非单位步长的紧优双环网络G(N;r,s)

双环网络是计算机互连网络或通讯系统的一类重要拓扑结构,其图论模型是指一个有向图G(N;r,s):每个顶点记为0,1,2,…,N-1,并从每个顶点I发出两条有向边I→I r(mod N)和I→I s(mod N),其中r和s是自然数,且1≤r≠s＜N.若G(N;r,s)存在k紧优双环网络,G(N;1,s)存在k1紧优双环网络,且满足k1＞k,称G(N;r,s)为非单位步长双环网络.在L形瓦理论的基础上,给出一个求非单位步长双环网络的方法,求得两个关于模型G(N;r,s)的紧优双环网络无限族;结合中国余数定理和数论中的素数理论,给出一个求非单位步长双环网络无限族(k1-k≥1且k＞0)的方法;作为具体应用,求得两个非单位步长双环网络无限族(k1-k≥2且k＞0).     

直角坐标系下双环网络G(N;r,s)容错路由研究

将直角坐标系引入双环网络,通过直角坐标系,系统研究双环网络G(N;r,s)的容错路由,提出将双环网络和直角坐标系结合起来,使节点可视可控.基于直角坐标系研究双环网络G(N;r,s)的容错路由,解决多节点故障时源节点如何快速建立和目的节点之间的路由.首次提出故障节点封闭区和节点逃逸区,在此基础上提出多节点故障时容错路由最优算法,并用实例验证算法的正确性.     

双环网络G(N;1,s)等价生成树

提出研究双环网络G(N;1,s)的抽象模型--等价生成树,并对其性质进行了研究,给出了双环网络G(N;1,s)等价生成树的构造方法.提出基于等价生成树G(N;1,s)的直径d(N;1,s)的求解算法,并给出了其显式公式,利用C语言编程对等价生成树的结构模型进行了仿真.结果表明:算法不仅可在有限时间内求出G(N;1,s)的所有直径,而且可方便地得到源结点到所有其他结点的最短路径.算法的复杂度为O(N).     

关于有向双环网络G(N;r,s)平均直径的研究

针对有向双环网络的最小路径图,给出了一个快速计算有向双环网络平均直径的高效算法.根据该算法,只要知道有向双环网络G(N;r,s)的3个参数N,r和s,就能计算出L-型瓦的4个参数a,b,p和q,从而计算出平均直径.对直径与平均直径之间的关系进行了仿真研究,结果表明:在一个无限族中,直径与平均直径的分布呈轴对称图形;同一网络的平均直径约等于直径的一半;在任意无限族中,当直径达到下界值时,平均直径不一定达到下界值,但当平均直径达到下界值时,直径一定达到下界值.最终表明平均直径比直径能更好地衡量网络传输效率.     

无向双环网络G(N;±r,±s)直径的研究

将直角坐标系引入无向双环网络的研究,通过直角坐标系构造无向双环网络的最小路径图,在详细分析无向双环网络最小路径图性质的基础上,系统研究无向双环网络G(N;±r,±s)的直径、平均直径,验证直径的下界,得出平均直径的下界.最后给出直角坐标系下无向双环网络最小路径图的仿真方法及直径、平均直径的计算方法.