（计算机应用技术专业论文）交叉立方体网络路由算法与图嵌入问题的研究.pdf

摘要 并行计算机互连网络的拓扑结构直是国际上的研究热点。人们已提出了多 种互连网络拓扑结构，其中超立方体是最流行的互连网络拓扑结构之一而且已被 广泛用于商业并行计算机系统。但它并不是各方面拓扑性质最好的互连网络，于 是人们开展了对超立方体的一类变型，即交叉立方体及其性质的研究。研究表明， 交叉立方体的某些性质优于超立方体，尤其是它的直径几乎是超立方体的一半， 因此是一种值得人们研究并推广应用的互连网络拓扑结构。本文对交叉立方体网 络的最短路径路由、并行路由、广播路由、无死镆路由、结点不相交路径长度以 及交叉立方体环网络的嵌入闻题展开了研究。本文的主要研究工作和贡献如下： ( 1 ) 针对已有的交叉立方体网络最短路径路由算法只能将部分最短路径作 为候选路径进行输出且不具有根据结点的繁忙程度进行选择路径能力的缺点，给 如了结点各边可进行最短路径路瘫的充要条件，提出了一种可根据结点的繁忙程 度进行择路时间复杂度为d ( 矿) 的完全国适应最短路径路由算法，其中投为交叉立 方体网络的维数。算法在进行路由的每一步，都从所有可进行最短路径路由的邻 边中选择繁忙程度最低的计算机结点对应的边进行路嘲，因此是将全部最短路径 作为候选路径，从面可输出任意一条最短路径。仿真实验结采验证了算法的有效 性。 ( 2 ) 对交叉立方体的顶点不相交路径迸行了研究，证明了以下结论：在，z 维 交叉立方体a g 中任意两顶点闻存在露条顶点不相交的路径，并且满足最短路 径的长度= 两顶点间的距离，所有路径中最长路径的长度竖两顶点闻的距离 + 4 。这说明交叉立方体互连网络具有很好的并行通信性能和容错性能。同时提出 了一种时间复杂度为阢行2 ) 的以维交叉立方体网络并行路由算法，可输出源结点到 睡的结点的三条结点不相交路径岛，a ，恐，并且满足峨产源结点到露的结点 的距离，i p , l - 螺结点到目的结点的距离+ 3 ( 卢l ，2 ) 。 ( 3 ) 在全端1 2 虫洞模型下，利用递归方法将交叉立方体网络分解为互不相交 的子交叉立方体网络，提出了栉维交叉立方体网络的广播路由算法，其所需路由 步数为o ( n l o g e ( n + l 势，在常数乘积因子范豳内是优化的。仿真实验结果验证了 算法的有效性。 ( 4 ) 证明了在不使用虚通道的情况下以( 眨3 ) 维交叉立方体网络中不存在无死 锁的最短路径路由算法，通过将一个物理通道分成三个虚逶道提出了一种时闻复 杂度为) 的无死锁最短路径虫洞路由算法。理论分析和仿真实验结果表明了 算法的有效性。 ( 5 ) 交叉立方体网络具有规模难以扩展( 不易升级) 的性质，而交叉立方体环 网络可以有效克服升级困难的缺点。本文证明了交叉立方体环网络仍然保持了交 叉立方体网络具有的哈密顿连通性和泛圈性。 本文通过对交叉立方体网络的路由算法和图嵌入问题的研究，提出了完全自 适应最短路径路由算法、并行路由算法、广播路由算法以及无死锁路由算法，同 时证明了交叉立方体环网络仍然保持了交叉立方体网络具有的哈密顿连通性和 泛圈性，从而推动了交叉立方体网络的研究与应用。 关键词互连网络，交叉立方体网络，路由算法，无死锁路由，图嵌入 i i a b s t r a c t t h er e s e a r c ho ni n t e r c o n n e c t i o nn e t w o r k st o p o l o g yo f p a r a l l e lc o m p u t e rs y s t e m s i sah o tt o p i ci nt h ew o r l d ，a n dm a n yn e t w o r kt o p o l o g i e sh a v eb e e np r o p o s e d a m o n g t h o s et o p o l o g i e s ，h y p e r c u b ei so n eo ft h em o s tp o p u l a rn e t w o r kt o p o l o g i e sa n dh a s b e e nw i d e l yu s e di nc o m m e r c i a lp a r a l l e lc o m p u t e rs y s t e m s 。b u ts o m et o p o l o g i c a l p r o p e r t i e so ft h eh y p e r c u b ea r ei n f e r i o rt ot h o s eo fo t h e rn e t w o r k st o p o l o g i e s , s o p e o p l eb e g i nt or e s e a r c hi n t oc r o s s e dc u b ew h i c hi sav a r i a t i o no fh y p e r c u b e r e c e n t r e s e a r c h e sr e v e a lt h a ts o m ep r o p e r t i e so fc r o s s e dc u b ea l es u p e r i o rt ot h o s eo f h y p e r c u b e ，e s p e c i a l l yt h ed i a m e t e ro ft h ef o r m e ri sa p p r o x i m a t e l yh a l ft h a to ft h e l a a e lt h e r e f o r e ，c r o s s e dc u b en e t w o r k sa r ew o r t hs t u d y i n ga n dp r o m o t i n gt h e i r a p p l i c a t i o n s i nt h ed i s s e r t a t i o n , w ed e s i g ns h o r t e s tp a t hr o u t i n ga l g o r i t h m ，p a r a l l e l r o u t i n ga l g o r i t h m , b r o a d c a s tr o u t i n ga l g o r i t h ma sw e l la sd e a d l o c k - f r e er o u t i n g a l g o r i t h mi nc r o s s e dc u b en e t w o r k s w ea l s os t u d yt h el e n g t h so fc r o s s e dc u b e n o d e - d i s j o i n tp a t h sa n de m b e d d i n gp r o b l e mi nc r o s s e dc u b e - c o n n e c t e dr i n gn e t w o r k s 甜l em a i nw o r k sa n dc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： 1 ) d u et ot h es h o r t a g et h a tt h es h o r t e s tp a t hr o u t i n ga l g o r i t h m sp r e v i o u s l y p r e s e n t e df o rn - d i m e n s i o n a lc r o s s e dc u b en e t w o r k sc a no n l yt a k ep a r t i a ls h o r t e s t p a t h sa sc a n d i d a t ep a t h st ob eo u t p u ta n dh a v en oa b i l i t yt or o u t ea c c o r d i n gt ot h e b u s y n e s sd e g r e eo f n o d e ，w ef i r s ti n t r o d u c et h es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n sf o r e a c hl i n ko fo n en o d eb e i n gac a n d i d a t el i n ko fas h o r t e s tp a t h , a n dd e s i g naf u l l y s e l f - a d a p t i v es h o r t e s tp a t hr o u t i n ga l g o r i t h mi nn - d i m e n s i o n a lc r o s s e dc u b e ，w h i c h h a sat i m ec o m p l e x i t yo fd ( ，力a te a c hr o u t i n gs t e p ，t h ea l g o r i t h mi sc a p a b l eo f c h o o s i n go n el i n kc o n n e c t i n gt h ei d l e s tn o d ef r o ma l lt h ec a n d i d a t el i n k st h a tb e l o n g t os h o r t e s tp a t h s , t h u si tt a k e sa l lt h es h o r t e s tp a t h sa si t sc a n d i d a t ep a t h sa n dc a n o u t p u ta n ys h o r t e s tp a t h s i m u l a t i o ne x p e r i m e n t a lr e s u l t ss h o wt h ea l g o r i t h mi s e f f i c i e n t ( 2 w es t u d yt h el e n g t h so fc r o s s e dc u b ev e r t e x - d i s j o i n tp a t h sa n dd r a wa c o n c l u s i o nt h a tf o ra n yp a i ro fv e r t e x e si na nn - d i m e n s i o n a lc r o s s e dc u b ec q 哮，t h e r e e x i s t 靠v e r t e x d i s j o i n tp a t h s 。s u c ht h a t t h el e n g t ho ft h es h o r t e s tp a t h t h e d i s t a n c eo ft h ep a i rv e r t e x e s , t h el e n g t ho fe a c hp a t hst h ed i s t a n c eo ft h ep a i r v e r t e x e s + 4 t h e r e f o r e ，c r o s s e dc u b ei n t e r c o n n e c t i o nn e t w o r k sh a v eh i g hp e r f o r m a n c e o f c o m m u n i c a t i o na n df a u l tt o l e r a n c e w ep r o p o s eap a r a l l e lr o u t i n ga l g o r i t h mw i t l l i i i t i m ec o m p l e x i t yo fo ( n 2 ) i nn - d i m e n s i o n a lc r o s s e dc u b en e t w o r k s ，w h i c hc a l lo u t p u t t h r e en o d e d i s j o i n tp a t h sp 融p l ，p 2b e t w e e ns o u r c en o d ea n dd e s t i n a t i o nn o d e ，s u c h t h a t l p 0 l = t h ed i s t a n c eb e t w e e nt h es o u r c en o d ea n dt h ed e s t i n a t i o nn o d e ， f b i 哈密顿连通的熙l ，即一个长度为2 蓐磊的环可以嵌入一个有磊个故障顶点和磊 个故障边的c 蜴中，其慨勤一2 ，n 2 。换而言之，当故障数为，1 2 时，c 珐仍然 是哈密顿的；当故障数为捍3 ，在任意顶点对间仍然存在哈密顿路径。 2 0 0 3 年y a n g 等人证明了只莲磊顸勘2 ( 矗表示故障结点数，磊表示故障边数) ， 长度为任意水s 逛l v ( c 魏) | 一勋的圈可嵌入有故障的c 编中【蚓。2 0 0 5 年f a n 等人证明 了当月墅，对于任意一个c 办上的顶点，都存在长度为任意婵蝴的圈包含该 顶点，即结点泛圈性( n o d e - p a n c y c l i c i t y ) ；对于任意一个c i 磊上的边，都存在长度 为任意群受受勺的圈包含该边，即边泛露性( e d g e p a n c y c l i c i t y ) ；同时证明了超立 方体也同样具有这鹾个性质【舛l 。 2 0 0 0 年樊建席用图嵌入技术讨论了s c c 模拟环网络的能力，证明了长度为4 到挖的任一圈都能以扩张l 嵌入具有n 个顶点的s c c p s i ，从而证明了s c c 模拟环网 络的能力与交叉立方体完全相阕。 综上所述，尽管对互连网络的研究取得了一定的研究成果，但仍然处于较低 的水平，尤其是对交叉立方体网络的路由算法和拓扑结构方面的研究还很少且存 在许多不足，因此需要进一步加强这方面的研究。 1 4 论文研究内容 通过1 3 节对立方体网络的拓扑结构、路由算法以及可嵌入性研究的综合评 价和分析，可以发现交叉立方体网络有一些特性优予其它霹络( 如超立方体) ，是 一种值得研究并推广应用的互连网络：同时也可发现对交叉立方体网络的研究很 少且存在很多不足。因此，本文将从以下五个方面进行研究。 ( 1 ) 交叉立方体网络最短路径路由算法。琶有豹算法在路由的每一步仅将部 分可进行最短路径路由的边作为侯选边，因此输出的路径是全部最短路径的子 集。并且这些算法都没有考虑网络结点的繁忙程度，不具有根据结点的繁忙程度 进行选择路径的能力。本文给出结点各边可进行最短路径路由的充要条件，提出 1 4 审南大学禧士学位论文 第一章绪论 一种可根据结点的繁忙程度进行择路的完全自适应最短路径路毒算法，并对算法 进行了性煞分析。 ( 2 ) 交叉立方体网络结点不相交路径的长度分析及并行路由算法。并行计算 机系统的网络拓扑结构中，信息是通过若干条结点不相交的路径并行传输，并且 网络中的结点和链路如错是不可避免的。当菜条路径的链路或结点击错后，将用 其它的结点不交路来代替它，因此结点不交路的个数越多，即连通度越高，容纳 出错结点和或链路的能力越强。但是对于这样网络的通信性能，仅孤立地考虑 连通度和直径是不够的，因为网络虽然有高的连通度和小的直径，但当消息通过 该网络中若干条结点不穗交的路径进行并行传输时，其中某些路径可畿很长，会 带来大的通信延迟。本文对交叉立方体的顶点不相交路径长度进行了研究，提出 了交叉立方体网络并行路由算法，并对算法输出的路径长度进行了分析。 ( 3 ) 交叉立方体网络广播路由算法。广播是并行计算祝系统中基本的通信模 式之一。许多数值计算算法，包括矩阵一向量乘、矩阵一矩阵乘、高斯消元、l u - 分解等的性能都依赖予广播算法的好坏。已有的交叉立方体网络的广播算法是基 于传统的存储转发交换模式的，而新一代的并行计算机系统都采用虫洞交换模 式。虫漏交换模式与存储庳发交换模式相比，大大减少了消息的传输延迟，因 此本文对交叉立方体阏络基于虫洞交换模式的广播路由进行了研究，提出了一种 有效的广播路由算法，并对算法进行了性能分析。 ( 4 ) 交叉立方体网络的无死锁路由算法。在设计路由算法时，必须考虑算法 的安全性，而安全性主要是保障算法的无死锁性。已有的交叉立方体网络路盘算 法都没有考虑死锁。本文对交叉立方体网络的死锁问题进行了研究，提出了基于 虚通道技术的无死锁最短路径虫洞路由算法，并对算法进行了性能分析。 ( 5 ) 交叉立方体环网络的哈密顿( h a m i l t o n ) 连通性和泛圈性( p a n c y c l i c i t y ) 性。 潮络模拟问题的实质是网络嵌入的问题，网络的哈密顿性和泛圈性反映的是线性 阵列、环等网络结构的可嵌入性，它是网络拓扑可嵌入性的主要内容。因此本文 对交叉立方体环网络的哈密顿连通性和泛圈性进行了研究。 1 5 论文的结构 论文共分七章。第一章已经介绍了本课题的研究背景及意义、并行计算机系 统的体系结构和立方体网络( 超立方体网络和交叉立方体网络) ，综述了立方体网 络的拓扑结构、路由算法以及可嵌入性的研究现状和水平，阐述了本文的研究内 容和主要研究工作。论文各章安排如下： 第二章是完全自适应最短路径路由算法。提出了交叉立方体网络各边可进行 最短路径路由的充要条件，并在此基础上提出了一种具有完全自适应能力的交叉 1 5 中南大学博士学位论文 第一章绪论 立方体最短路径路由算法，最后通过理论和仿真实验结果分析了算法的性能。 第三章是结点不相交路径的长度分析及并行路由算法。分析了交叉立方体网 络结点间不相交路径的长度与结点间距离的关系，并提出了一种可输出三条结点 不相交路径的算法，最后通过仿真实验结果分析了算法输出的路径长度。 第四章是广播路由算法。在全端口虫洞模型下，利用递归的方法将交叉立方 体网络分解为互不相交的子交叉立方体网络，提出了交叉立方体网络的广播路由 算法，并分析了其所需路由步数在常数乘积因子范围内是优化的，最后通过仿真 实验结果进一步验证算法的性能。 第五章是无死锁的路由算法。首先证明了 ( 庀3 ) 维交叉立方体网络在不使用 虚通道的情况下不存在无死锁的最短路径路由算法，然后在虫洞交换模式下提出 了一种基于三个虚通道的交叉立方体网络无死锁最短路径路由算法，并通过理论 和仿真实验结果分析了算法的性能。 第六章是交叉立方体环网络的哈密顿连通性和泛圈性。首先介绍了交叉立方 体环网络的拓扑结构，然后证明了交叉立方体环网络具有哈密顿连通性和泛圈性 性。 第七章是全文总结与工作展望。对本文的研究工作所取得的研究成果进行总 结，并就未来的研究工作提出一些设想。 1 6 中南大学博士学位论文第二章完全自适应最短路径路由算法 第二章完全自适应最短路径路由算法 在并行计算机系统中，各结点计算机需要相互传递信息，而找出源结点到目 的结点的最短路径进行消息传递能减少通信延迟和网络阻塞，从而提高系统的通 信性能。本章给出了结点各边可进行最短路径路由的充要条件，并提出了一种具 有完全自适应能力的交叉立方体网络最短路径路由算法f a s p a 。其基本思想是， 在进行路由的每一步，都从所有可进行最短路径路由的邻边中选择繁忙程度最低 的计算机结点对应的边进行路由，因此是将全部最短路径作为候选路径，从而可 输出任意一条源结点到目的结点的最短路径。仿真实验结果验证了算法的有效 性。 2 1 引言 交叉立方体网络的寻径方式直接影响着计算机并行处理的性能，建立一种有 效的路由方式无疑将为大规模交叉立方体网络的高效并行处理提供坚实的基础。 并行计算机系统的通信交换模式主要有包交换( p a c k e ts w i t c h i n g ) 、电路交换 ( c n u i ts w i t c h i n g ) 、虫洞路由交换( w o r m h o l er o u t i n gs w i t c h i n g ) 和虚切入交换 ( v i r t u a lc u t - t h r o u g hs w i t c h i n g ) 。新一代的并行计算机大多采用虫洞路由交换模 式。 路由算法有多种分类方式。按照路径的确定方式可以将路由算法分为确定式 路g t ( d e t e r m i n i s t i cr o u t i n g ) 算法、随机路由( r a n d o m i z e d r o u t i n g ) 算法和自适应路 f l 了( a d a p t i v er o u t i n g ) 算法。在确定式路由算法中，路径完全由源结点和目的结点 确定，只能输出源结点到目的结点的同一条路径；在随机路由算法中，路径由随 机数生成器随机确定；在自适应路由算法中，路径根据网络的流量以及链路的状 态来确定以避免阻塞或故障区域；随机路由和自适应路由可以输出源结点到目的 结点不同的路径。按照路径长度可以将路由算法分为最短最d 、( s h o r t e s v m i n i m a l ) 路径路由算法和非最短最小路径路由算法。最短路径算法总是输出源结点到目 的结点的最短路径，而非最短最小路径算法允许使用更长的路径。无论采用哪 种交换模式，找出源结点到目的结点的最短路径进行消息传递都能减少通信延迟 和网络阻塞，从而提高系统的通信性能。自适应最短路径路由算法分为完全自适 应( f u l l ya d a p t i v e ) 最短路径路由算法和部分自适应( p a r t i a l l ya d a p t i v e ) 最短路径 路由算法。完全自适应最短路径路由算法可以输出所有源结点到目的结点最短路 径中的任意一条，而部分自适应路由算法只能输出部分源结点到目的结点最短路 径中的任意一条。 1 7 中南大学博士学位论文第二章完全自适应最短路径路由算法 在交叉立方体网络的最短路径路由算法研究中，e f e 在文【6 】提出的算法在路 由的每一步最多只有两条边作为寻路选择，c h a n g 等人在文【3 1 】中扩展了e f e 的 算法，路由的每一步可以有更多边作为寻路选择。但这些边并非全部可进行最短 路径路由的边，因此它只能将部分最短路径作为候选路径进行输出。此外，以上 两种算法都不具有根据网络结点的繁忙程度进行自适应路由的能力。本文给出了 结点各边可进行最短路径路由的充要条件，并提出了一种具有完全自适应能力的 交叉立方体网络最短路径路由算法。其基本思想是，在进行路由的每一步，都从 所有可进行最短路径路由的邻边中选择繁忙程度最低的计算机结点对应的边进 行路由，因此是将全部最短路径作为候选路径，从而可输出任意一条最短路径。 需要指出，以上三种算法只是找出最短路径，并未对通信模式进行描述，因此对 包交换、电路交换、虫洞路由交换和虚切入交换四种通信交换模式均适用。仿真 实验结果验证了算法的有效性。 2 2 交叉立方体两顶点间的相邻关系与距离 本节给出了交叉立方体两顶点相邻的充要条件以及两顶点的距离计算公式， 为本章中后续的引理、推论以及定理的证明做准备。 2 2 1两顶点相邻的充要条件 下面的引理给出了交叉立方体中两顶点相邻的充要条件。 引理2 1 6 1 设铲l u o ，1 ，= l 为c g 的两个顶点，“和1 ，在它们的第，条 边相邻当且仅当 ( 1 ) u n - l u l + 1 - - - - v n 1 肌l ， ( 2 ) u # - v l ， ( 3 ) 如果z 是奇数，1 1 = l ， ( 4 ) 当。冬k 匕j 时，x 2 州x 2 r - y 2 件蚴。 2 2 2 两顶点的距离 设甜为g g 上的一个顶点，当畦逛匕j 1 ，材的第f 个二进制位对，定义为眈升l 眈f ； 当卢b j 且刀为奇数，定义为眈f 。如果甜的力厶1 个前缀与1 ，的前刀厶1 个前缀值相同， 中南大学博士学位论文 第二章完全自适应最短路径路由算法 & 0 u n - 1 船l = v n - 1 悟l ，且甜砌，称，是甜和，的最重要位；令广= 匕j ，称f 为甜和1 ，的 最重要位对。下面给出位对距离p ，( “，) 的定义： 定义2 1 3 1 1 鸵f + l ， p j ( 4 , v ) 2 0 ； 匈= 广， f 2若”2 | + l 2 一：；2 阳；2 产 p j ( u ， ，) 2 l 若材2 p + i ”2 一；2 产+ l ；2 ， 其中记号“一刀表示位取反操作；当心， ，o 若材2 p i u 2 j 弄f i 1 v 2 j + i v 2 _ ，是距离保持位对 p j ( u ，1 ，) 2t l 若甜2 ，+ l “2 ，和v 2 _ ，+ l v 2 ，不是距离保持位对。 兰班广，满足下面条件之一，称z 协l 吻和吩+ l 吩是距离保持位对。 ( 1 ) ( 呦嘞，协l 蚴 ( 0 l ，0 1 ) ，( 1 1 ，1 1 ) 且：势( ) 是偶数， 例n - i ( 2 ) ( 断l 吻，协l 蚴 ( 0 1 ，1 1 ) ，( 1 l ，0 1 ) 且。萎p 甜，d 是奇数， ( 3 ) ( u 2 j + i z 2 j ，1 协l 蚴 ( o o ，0 0 ) ，( 1 0 ，1 0 ) 。 若z 峥l 嗡和附l 吩是距离保持位对，记作l 盼l 哟d 二，v 2 j + l 吻；否则记作 u 2 y + , u 2 j d i p ，坍l 崎。 i 刊 我们用电( “，1 ) 表示“到v 在c 蜴上的距离，用以甜，v ) = 荟见( ，d 表示甜和晓 间的位对距离和，存在下列引理。 引理2 2 叫p ( u ，v ) = 电( 甜， ，) 2 3 最短路径寻路的充要条件 本节首先对路由过程中位对距离的变化情况进行了分析，得出了引理2 3 、 引理2 4 ，并在此基础上给出了本章的主要结论边属于最短路径的充要条件( 定 理2 1 一定理2 4 ) 。 1 9 中南大学博士学位论文 第二章完全自适应最短路径路由算法 2 3 1 路由过程中位对距离的变化分析 下面的引理2 3 、引理2 4 分情况给出了路由过程中位对距离的变化规律，为 本章的主要结论定理2 1 定理2 4 的证明做准备。 引理2 3 当从结点“沿第2 m + l 或2 聊条边到达结点甜，g e i t f f z 意i ( o i m _ h i i + ) ， l2j2 假设荟p “v ) 与薹扛( ，v ) 的奇偶性不同，若肛( 材，) = o ，则肛( 矿，) = o ； 若 肛 ，v ) = 1 且f 不是“与v 的最重要位对，则房似，功= 1 ；若p ，( 材，v ) = l 且f 是“与v 的 最重要位对，则p ，( 甜，1 ，) = 1 或2 。 证明：当从材沿第2 m + l 或2 m 条边到达“7 ，对于任意i ( o 2 i + 1 ； ( 2 ) 边的维= 2 i 、2 i + 1 ； ( 3 ) 边的维q 广且p ，( 甜，d = 1 ( 其中m 是边的维对应的位对序号) ； ( 4 ) 边的维 i + ) ，甜的第2 ，件1 、2 聊条边属于“到1 ，的最短路径的 充分必要条件是：p f ( 甜，) - 2 ，且存在一个j f 使得p ，( 甜，1 ，) = l ，j = m a x i l u 2 j + l u 2 耽什l 屹f 。 证明：首先证明定理的充分性： 当，l 广，有 中南大学博士学位论文第二章完全自适应最短路径路由算法 u 2 m + l u 2 m = 1 ，2 m + i v 2 m , p ，( 甜，) = o 。 当从u 沿第2 m + l 或2 m 条边到达u ，m 变成了l ，和 ，的最重要位对，易见 e r e ( u l , v ) = 1 。 当m i i 时， ( u 2 丹i u 2 , ，v 2 i + l v 2 _ i f ) ( o o ，o o ) ，( 0 1 ，0 1 ) ，( 1 0 ，1 0 ) ，( 1 1 ，1 1 ) ) ， 根据引理2 1 有 ( u p 2 斗l 甜乞，v 2 什w 2 t ) ( 0 0 ，o o ) ，( 11 ，0 1 ) ，( 1 0 ，1 0 ) ，( 0 1 ，11 ) 。 h 因为所( 甜，v ) 是奇数，利用数学归纳法易证明 p l ( “， ，) = o ( 广 k 聊) 。 由办( “，1 ，) = 2 ，有 ( u 2 i * + l u 2 i ，v 2 i * + i v 2 i ) ( 0 0 ，1 1 ) ，( 1 1 ，o o ) ，( 0 1 ，1 0 ) ，( 1 0 ，0 1 ) ) ， 根据引理2 1 有 ( “，2 ，+ l 材么，v 2 i * + i v 2 i * ) ( 0 0 ，l1 ) ，( 0 1 ，o o ) ，( 11 ，l o ) ，( 1 0 ，0 1 ) ) ， 又根据定义2 1 有 ”o + lu s i , 弘v 2 i * + l v 2 f ， 即 肛 ，) = l 。 易见寥似。：黔归。奇偶性，又由于存在一个歹使m 闩， 卢硼锨 目地一l 呦：v 2 件l 屹f ，根据定义2 2 及引理2 3 易证 p f ( 甜，1 ，) = p f ( 甜7 ，1 ，) ( 广 手与) ， p ( 甜，1 ，) = 0 ， n ，) = p ，似，1 ，) ( 0 9 劝。 易见 p ( u ，叻= p ( u ，d + l 。 根据推论2 1 知u 的第2 ，时l 、2 m 条边属于材到1 ，的最短路径。 中南大学博士学位论文 第二章完全自适应最短路径路由算法 必要性： 利用反证法只需证明在( 1 ) p 产( 材，1 ，) 2 ；( 2 ) p 产( 甜，v ) - - - 2 且不存在i ( o i i + ) 使得 u 2 i + 1 l d 2 i ：v 2 i + i v 2 i ；( 3 ) p f ( 材，) 2 且存在一个，使得p ( “，1 ，) 2 0 ，j = m a x i i u 2 斗i u 2 f ：v 2 f + l v 2 f ) 三种情况下，当从u 沿第2 ，时l 或2 m 条边到达u ，则 p ( u ，v ) p ( “，d + l 。类似定理充分性的证明，这里从略。证毕。 下面的定理2 2 给出了情况2 中的边属于最短路径的充要条件。 定理2 2 u 的第2 i + 1 ( 2 i ) 条边属于u 到1 ，的最短路径的充要条件是： ( 1 ) 肛( 甜，1 ，) = 2 或 ( 2 ) u2 p + i u 2 f 一- - - - v 2 i * + i v 2 f ( p t 。( z ，叻= l 且u2 i * = v 2 ，) ，且不存在i ( o i i ) 使得 肛( “，v ) = l 或 ( 3 ) 五2 * + 1 2 f f 耽 l y e f p i ( 甜，v ) = l 且五2 产= 屹，d ，且存在m 使得 1 1 2 耐l 五2 | ，l 一；肛v 2 m + i v 2 m ，r e = m a x i p f ( 村，v ) = l 且。垫以或 ( 4 ) 玉2 t * + 1 2 f 珧f * + i v 2 f p i 。( 材，叻= l 且玉2 i * = v 2 ，) ，且存在一个m 使得 屹耐l 五加d 二p 咻1 1 ，锄，r e = m a x i l p , ( u ，d = 1 且眶i 广) ，存在一个j 使得p j ( u ，叻= l ， 卢硼a x i lu 2 i + l u 2 i ：v 2 什i v 2 1 且呦) 。 证明：这里只证明”的第2 i * + 1 条边属于材到i ，的最短路径的充要条件的正 确性，材的第2 产条边属于甜到1 ，的最短路径的充要条件的正确性证明类似。 充分性： 假设条件( 1 ) a 。( 甜，叻= 2 成立，当从甜沿第2 i * + 1 条边到达u ，可知 伟( “，) = l o 易见 【垂- c v ，：【蓁- 。以v ，+ 。差_ c 以v ，与譬_ ，叻奇偶性不同， 由引理2 3 有 只( 甜，d = 肛( “，叻( 0 5 _ i i ) 。 中南大学博士学位论文第二章完全自适应最短路径路由算法 易见， p ( u ，v ) = p ( u ，d + 1 ， 则u 的第2 i * + 1 条边属于甜到1 ，的最短路径。 假设p f ( 材，功= 1 ，u2 f + l u 2 f 同协* + i v 2 f 成立，当从u 沿第2 产+ 1 条边到达u ，可 知 尼。( 材7 ，v ) - - o ， 易见 。蓁_ c 材：【蓁_ c 儿。+ 。【差- c v ，与。萋- c 乩v ，奇偶性不同，。 下面分三种情况进行讨论： 第一种情况：不存在i ( 0 5 _ i i ) 使得a ( “，v ) = l 。由引理2 3 有 p ，( 1 t ：, ，) = p f ，v ) ( 0 9 产) 。 易见， p ( u ，) = p ( u ，力+ l 。 第二种情况：存在m 使得u 2 m + l u2 m d v 2 m + i v 2 m ，m = m a x i l p f ( “，1 ，) = 1 且 o ， 由于m 是材与1 ，的最重要位对，故 p m ( u l , v ) 吃。 易见 。差- c 砺v ，：。薹- 。矩，v ，。奇偶性相同， 又由乃( 豁，磅= l ，j = m a x i lu 2 1 + l 沈f ：晚挣w 2 i 且0 s m ，有 届 ，1 ，) 一p f ，v ) 扩 f 班) ， p j ( u ，v ) - - - o ， n ，v ) = 肛 ，) ( 啤劝。 易见， p ( u ，v ) = p ( u 7 ，d + 1 因此，甜的第2 i * + i 条边属于材到1 ，的最短路径。 必要性： 只需证明条件( 1 ) ，( 2 ) ，( 3 ) 均不满足时，当从甜沿第2 i * + i 条边到达甜7 ，则 尸( 甜， ，) 以z ，d + l ，这里存在以下三种情况： 第一种情况：u 2 j 五劣妒= v 2 i * + i v 2 j 。易证办( 甜，v ) 宅，( 材，1 ，) 一只( 蚝v ) ( 争) ， 故从材，) p ( u ，v ) + l 。 第二神情况： 2 i * + l 蚴产强q l 强，且存在删研拳) 使褥现科l 五2 搿乞只v 锄+ l v ， m = m a x i lp , ( u ，= 薹且喇 ，并且不存在删，使得嗡l 吻：协l 吻。 中南大学博士学位论文第二章完全自适应最短路径路由算法 易证办( 甜，1 ，) = o ，辟( ”，1 ，) = 只( 甜， ，) - 0 ( 聊 k 产) ，成( “，v ) _ 2 ， 房( 材，1 ，) = 岛 ，力( o s _ i m ) ，故p ( u ，) p ，d + 1 。 第三种情况：u2 t * + i u 2 f ：v 2 * + i v 2 j ，且存在m ( 搠 产) 使得甜孙+ l 五2 j ，l d 二，v 锄+ l v 2 j ，i ， m = m a x i l 岛( z ，1 ，) = l 且o i i ) ，并且存在一个胸) ，使得p j ( u ，力= o ，y = m a x i l 1 a 2 升l u 2 f ：场+ j 场且畦翩) 。 易证辟。( 甜， ，) 印，肛( 甜7 ，) = 岛( 甜，1 ，) = o ( 聊 产) ，成( “，1 ，) _ 2 ，辟( 甜，1 ，) = 肛( “，1 ，) ( ， k m ) ，p j ( u 7 ，力2 l ，肛( “， ，) = 肛 ，v ) ( o 鲫，p ( u ，力p ，v ) + 1 。证毕。 下面的定理2 3 给出了情况3 中边属于最短路径的充要条件。 定理2 3 对任意m ( m 。 证明：这里只证明1 , 的第2 耐1 条边属于, 到1 ，的最短路径的充要条件的 正确性，“的第2 m 条边属于材到v 的最短路径的充要条件的正确性证明类似。 充分性： 假设五加+ i 2 m d - p 。v 2 m + l v 2 m 成立。当从材沿第2 m + l 条边到达甜，有 由 有 易见 甜k + 1 甜。j 彳= 以2 m + i ， 鼽巩参力。奇偶性必， 玉2 j ，l + l ? + l ， “k + 1 “k d ，l v 2 m ，即岛( 甜，1 ，) = 0 。 中南大学博士学位论文第二章完全自适应最短路径路由算法 孰小l 孰，群( ，v ) + 1 ：岛( ) ， 根据引理2 3 易证 易见， 尼( “，) = 展 ，1 ，) ( o 篓k 掰) 。 p ( u ，v ) = p ( “，+ 1 。 假设存在一个歹使艚p j ( u ，崎= 1 ，j = m a x i u 2 挣= u 2 i , v 2 i + l v 2 i唧 = 重。 易见 茎_ t 功。5 差乞。以叻，根据定义2 2 有 易见 只 ，v ) 一砖囊，) ( 删劝， 砖做谚翎。 篆- 纸谚：i i 季2j k ；t 磅+ ，。l t 季zj - 敏谚与。著乞秘乞磅奇偶性不相同， 又根据引理2 3 有 岛 ，v ) 一肛q ，v ) ( o 竖f 劝。 易见， 以甜，谚- - , o ( u ，+ l 。 因此，封的第2 m + l 条边属于甜到v 的最短路径。 中南大学博士学位论文第二章完全自适应最短路径路由算法 必要性： 只需证明当m 。易证尼( 甜，) 2 肛 ，1 ，) ( 水呦，p j ( u ，d2 l ，肛 ，1 ，) = 肛( 材，1 ，) ( 0 矧 易见， p ( u ，1 ，) + 1 - - p ( u ，力， 则甜的第2 刖- l 条边不属于材到v 的最短路径。证毕。 下面的定理2 4 证明了情况4 中的边是不属于最短路径的。 定理2 4 对任意m ( 聊 广，且以( 甜，) = 0 ) ，的第2 ，时l 、2 坍条边不属于砧 到v 的最短路径。 证明；对任意m 伽q ，且氏 ，) = 0 ) ，当从“沿第2 ，时l 或2 m 条边到达 “，易见 中南大学博士学位论文第二章完全自适应最短路径路由算法 由以下三式： 只 ，v ) = 麒( ，v ) ( 黼) 。 u 2 脚+ l 阮辨叠，毪肿l 毪搠， 嚣2 辫+ l 王1 2 牌籍2 穰+ i u 拼， ! 萋- 。：i 差乞函，力， ” l = _ + l 有 u s = + iu h s 7 p ，2 埘+ l ， 即成( “，) = 1 。 从而有 赴乳咀l ， 即譬与塾蝴奇雠不矾勰蚴有 露妇，d = 砖( 掰，v ) 斑兰i _ 锄) 。 易觅， 夕( 钍，d = 烈豁，力1 ， 则u 的第2 时l 、2 m 条边不属子嚣到v 的最短路径。证毕。 2 4 路由算法f a s p a 及其输出路径范围分析 本节在2 3 节给崽的定理2 1 定理2 4 的基础上提出了完全皇适应最短路径 路由算法f a s p a ，同时论证了算法的正确性并分析了算法的时间复杂度，最后 对算法输出的路径范围进行了分析。 2 4 1 完全自适应最短路径路由算法f a s p a 我们指出，以上