（计算机软件与理论专业论文）双环网络的仿真研究.pdf

摘要 摘要 图论是离散数学和组合数学领域较为活跃的分支之一。二十世纪六十年代以 来，由于生产管理、军事、交通运输、计算机网络等方面提出的实际问题的需要， 特别是许多离散性问题的出现，以及由于有了大型电子计算机，从而使大规模问 题的求解成为可能，图论及其应用的研究得到了飞速的发展。 图的某些参数如连通度和直径，因为其在图论和组合中固有的重要性及其与 通信网络的容错性和传输延迟的关系而得到广泛研究。 双环网络是图的一种重要形式，是计算机互连网络或通讯系统的一类重要拓 扑结构，广泛应用于计算机局域网和各种并行处理结构。 二十世纪七十年代以来，人们利用数学的方法研究了双环网络的直径、紧优 性、路由和容错性，取得了不少成果。 本文将双环网络的寻径过程看成一个遍历节点的过程，提出了利用宽度优先 法( b f s ) 来求解双环网络的直径，由此将计算机仿真引入了双环网络的研究之 中。本论文的主要工作包括： 1 双环网络直径和紧优性。利用宽度优先法求得双环网络的直径和紧优性。 对某个变化其步长，s 所形成的一族双环网络( 一向m 咖) 直径具有最大值、 最小值和对称分布的特点；紧优双环网络广泛存在，且对称分布。无向双环网络 的直径大约是有向双环网络直径的一半。双环网络的直径求解过程可以生成一个 等价的螺旋环。 2 双环网络紧优分布特性。对某个变化其步长，s 所形成的一族双环网 络( 一励砂) 具有的紧优双环网络数随着的增大而呈现平稳的波动性，紧 优数与的比值随着的增大而波动性下降。 3 双环网络平均直径。利用宽度优先法求得双环网络的平均直径。 一伽咖中紧优双环网络的平均直径并不一定是最小的，具有最小平均直径的 紧优双环网络称为双优双环网络。 4 双环网络形瓦仿真。通过等价的三形瓦可以得到双环网络的直径。随着 的增大和步长的增多，手工构造三形瓦是不可能的，本文利用计算机仿真生成 三形瓦，并研究了其形状和参数的分布特征。 5 双环网络等价生成树。双环网络是种网状拓扑结构，为了求其直径， 往往将其转换为其它等价的拓扑结构。树是一种典型的数据结构，将双环网络生 成等价树，并分析生成树的特征，通过生成树可以得到双环网络的直径。 摘要 6 双环网络【+ 办】边优先寻径策略。针对有向单位步长双环网络g ( ；l ，乃) ， 提出了一种 + 明边优先的寻径策略，并得到一种新的竹筏型三形瓦，“竹筏”中 节点之间的【+ 明边优先最短路径存在递推关系；由节点的【+ 办】边优先最短路径推 出双环网络的直径公式。 7 建立了一个仿真平台。将宽度优先( b f s ) 搜索的遍历法引入双环网络的 研究中，有利于我们进行仿真研究，因此建立了一个仿真平台。仿真平台极大的 帮助了我们的研究工作，直径、平均直径、紧优性、螺旋环、生成树、三形瓦、 竹筏型三形瓦等都得到很好的仿真。 关键词：图；双环网络；遍历法；l 形瓦；直径；紧优性 a b s 仃a c t a b s t r a c t c 咖hn e o d ，i sa 白v o t eb 珈1 c hi nd i s c r e t em a t h e m a t i c sa n dc o m b i n a t o 巧 m 础e m a t i c s s i n c el9 6 0 sb e c a u s eo f l ep r a c t i c er e q u i r e m e n t sa r o u s e df o m p r o d u c t i o nm a l l a g e m e n t ，m i l i 戗酊a 胁i r s ，缸锄s p o r t a t i o na n dc o i n p u t e rn e t w o r k s ，a l l d e s p e c i a ll o t so fd i s c r e t ep r o b l e m sr l e e d i i 培b er e s o l v e d ，o n l eo 1 e rh a l l d ，b e i n gt h e a d v e n to fl a 玛em a i r 锄ec o m p u t e r l a tc a nc a l c u l a t el 鹕es c a j e c o m p l i c a t e p b l e r i l s ，g f a p ht h e o 巧锄da p p l i c a t i o nh a v em a d er a p i dp 】孕e s s g r a p hp a r 锄e t e r s s u c h舔 c o n n e c t i v i 锣觚dd i a m e t e r h a ：v eb e e ns t u d i e d e x t e i l s i v e l yd u et 0t l l e i r 蛐i ci l p o r t a n c ei i lg r a p hm e o c o n l b i 彻r t o r ) ra n dm e i r r e l a t i o 璐t 0f a l mt o l 咖c ea i l d 的n s m i s s i o nd e l a yi l lc o 蛐n u i l i c a t i o 嬲咖f i 【s d o u b l e - 1 0 0 p 咖d ( s ( d l n s ) 盯ei n l p o r t a n tf o mo f 铲a p h ，a i l di i n p o r t a 呲 t o p o l o 百c a l 咖c t u r eo fc o m p u t e rn e t v v o r k sa n dc o r n m u l l i c a t i o ns y s t e m sh a v eb e e n 诵d e l ys n l d i e da sa r c h i t e c 眦f o rl o c 甜a r e an e 铆o d 【s 觚dl 鹕es c a l ep a m l l e l c o m m 砌c a t i o ns y s t e m s s i n c e19 7 0 ，s ，m u c he 舶nh a v eb e 朗m a d et o 咖d yt 1 1 ed i 锄e t e r o p t i m 烈i 识 r o u t i n gp a t l la i l d 矗m l tt o l e r a i l c eo fd l n s ，锄dl o t so fc o n t r i b u t i o l l sh a v eb e e nm a d e n l ep r o c e s so fs e e k i n gm ed i 锄e t e ro fad u 、ii sv i e w e da st h et r a v e r s a lf o ra l l n o d e si l lm ed l ni nt 1 1 i st l l e s i s ，s 0 廿1 eb f s ( b r e a d t l l f i r s t - s e a r c h ) i sp r o p o s e dt 0 o b t a i nn l ed i 锄e t e ro fad l n ，胁h e 肌o r e l es i m u l a t i o ni s 印p l i e dt os t u d yd l n s m a i nw o r k si n “sm e s i sa 1 es u m m a r i z e da sf i o u o w s 1 1 1 l ed i a m e t e ra i l do p t i m a l 时o fd l n s t h ed i 锄e t e ra i l do p t 曲a l 埘o fd l n s a r eo b t a i n e db yu s eo fb f s ( b r e a d t i l f i r s t - s e a r c h ) 一伽砂r e f e r st 0a 细m i l yo f d l n sm a t i sf i e db u ti t s 鼬e p s1 ，s 一la 1 1 dg c d ( ，s ) = 1 t h e r ea r c m a x i m 呦v a l u e ， m i 血叭l i i lv a l u e ，a 1 1 ds y n m e 缸yd i s t r i b u t i o ni nd i 锄e 屯e ri i l 一加砂1 1 1 e r cw i d e l ye x i s t e dt i g h to p t i m a ld o u b l e1 0 0 pn e 铆o r l 【sa n d l e y s ) ，i l m e t r i c a l l ya p p e 弛t h ed i 锄e t e ro fu d l n ( 吼d i r e c t e dd o u b l el o 叩n e 似0 r b ) i s 印p r o x i ma _ t e l yh a l fo ft l l a to fd l n ( d i r e c t e dd o u b l el o o pn e t 、 r o r k s ) a ne q u i v a l e n t t o p o l 晒c a ls t m c n 聆- s p i r a j 咖g - i sf 0 加e db yb f s 2 7 r h ed i s t r i b u t i o na t t 舶u t i o no ft i 曲to p t i m a ld l n 1 1 1 e 锄。蚰to ft i g h to p t i m 2 l l d l ni n 一扣肌渺i sn a tf l u c t u a t e dw i t l l ，w h i l et h er a t i oo f t h e mi sn u c t u a t i n g d e c r e a s e dw i t h 3 7 n l ea v e r a g ed i a m e t e ro fd l n 1 1 1 ea v e r a g ed i 锄1 e t e ro fd l nc a i la l s ob e l l l a b s t r a c t c a l c u l a t i 耐b yb f s t h ea v e r a g ed i 锄e t e ro fat i g h to p t i i i l a ld l n i sn o tc e r t a i l l l ym e s m a l l e s ti 1 1 一知肌砂，s oat i g h to p t i m a ld l nw i t l lt l l es m a l l e s ta v e r a g ed i 锄e t e ri n 一加砂i sc a l l e dad u 甜- o p t i m a ld o u b l e 1 0 0 pn e t 、r k 4 s i m u l a t i o no n 三一s h a p e dt i l eo fd l n 1 1 1 ed i 锄e t e ro fd l nc a i lb eo b t a i n e d b yi t se q i l i v a l e n t 三- s h a p e dt i l e w i t l lt 1 1 ei n c r e a s i n go f a r l di t ss t e p s ，三一s h 印e d n l ec 锄n o tb ec o n s t n l c t e db ym a nh a n d c o m p u t e rs i n m l a t i o ni s 印p l i e di i l c 0 璐仇l c t i o no f 三- s h a p e dt i l e ，a i l dt l l ed i s t r i b u t i o no ft 1 e i rs h 印e 觚dp a r 锄e t e r sa r e s t u d i e di i lt l l i s 廿l e s i s 5 b q m v 2 l l e n tb 呻t r e eo fd l n d l ni sak 砌o f 玳帅旧r kt o p o l o 萄c a ls 伽t u r e i no r d e rt 0a c q u i t sd i 锄e t e r d l ni su s u a l l y 衄l s f e r r e d 硫o0 t h e rl 【i 1 1 do f t o p o l o g i c a l 舭d l ni s 吣f o m e di n t oe q u i v a l e n tb i 瑚r ) r 仃e ei nt h j st l l e s i s n ed i 锄e t e ro f d l nc a l lb eo m n e db y 恤e q u i v a l e n tb i r m r ) r 骶e 6 + 明一l i i l kp r i o rr o u t i n gs t m t e g ) rf o rd l n 【+ 明- l 址附o rr 0 u t i n gs 仃a t e g ) r f o rd o u b l e - l o o pn e t w o r ki sp r o p o s e d 1 1 1 es h o n e s t 【+ 明- l i n kp r i o rp a ma i l dt l l e b 锄1 b 0 0r ：m ( an e wl ( i n do f 三- s h 印e dt i l e ) f o rad o u b l e - 1 0 0 pn 酿o r ka r eo b t a i n e d 1 1 1 e r ei si n f e n 啦r e l a t i o n s m p s 锄o n gn o d e si nm eb 锄b o o 硼1 1 1 ed i 锄e t e ro fa d l nc 趾b ed e r i v e d 舶mm es h o n e s t 【+ 明- l i i l l ( p r i o rp a m 7 as i m u l a t i o np l a t f o mi sc o 玎s t n l c t e d b a s e do nb f s ，as i m u l a t i o np l a t f o m li s c o i l s 协j c t e d t h es i m u l a t i o np l a t f o mi sh e l p m lf o ru st 0s i m u l a t et 1 1 ed i a m e t e r ， a v e r a g ed i 锄e t e r o p t i m a l i 劬s p i r a lr i n g ，b i n a 巧仃e e ，三- s h 印e dt i l e ，a i l db 锄b 0 0m 三一s h 印e dt i l e k e yw o r d s ：g r a p h ；d o u b l e1 0 0 pn c t w o 幽；仃a v e r s a l ；三- s h a p e dt i l e ；d i 锄e t e r ； 0 p t i m a i i t y l v 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：粗签字日期： 纠 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 口公开口保密( 年) 作者签名： 签字日期：幽：型 导师签 签字同期：犁 第l 章绪论 第l 章绪论 1 1 研究背景 1 7 3 6 年，欧拉采用图的方式解决了哥尼斯堡七桥问题，成为图论( 及拓 扑学】的创始人。此后的一个世纪内图论处于萌芽阶段。 1 8 5 9 年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二 面体，它的2 0 个顶点标出世界著名的2 0 个城市，要求游戏者找一条沿着 各边通过每个顶点刚好一次的闭回路，即“绕行世界”。用图论的语言来说， 游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈 密顿问题。1 8 5 2 年，毕业于伦敦大学的弗南西斯格思里来到一家科研单位 搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四 种颜色着色，使得有共同边界的国家都被着上不同的颜色”。1 8 7 2 年，英国 当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色 猜想成了世界数学界关注的问题。此后的一个世纪内图论问题大量出现。 二十世纪中叶以后( 侯新民，2 0 0 2 ) 1 ，由于军事、生产管理、交通运输、计 算机网络等方面提出的实际问题的需要，特别是许多离散性问题的出现，以及由 于有了大型电子计算机，从而使大规模问题的求解成为可能，图论及其应用的研 究得到了飞速的发展。 图论成为近年来离散数学和组合数学领域较为活跃的分支之一( 侯新民， 2 0 0 2 ) 1 。图的某些参数如连通度和直径，因为其在图论和组合中固有的重要性 及其与通信网络的容错性和传输延迟的关系而得到广泛研究。超大规模集成电路 技术和光纤材料科学的发展使我们有能力设计大型并行处理计算机系统和快速、 复杂的通信网络。这些系统不仅要求我们研究网络的连通度和直径，而且要研究 连接两个节点或两个点集间的内部点不交的多条路径。 双环网络是具有个节点和出度为2 的对称循环图，是计算机互连网络或 通讯系统的一类重要拓扑结构，广泛应用于计算机局域网和各种并行处理结构。 这里所讨论的互连网络和通讯系统具有广泛的含义( 陈宝兴，2 0 0 4 ) 1 ，泛指组件 ( 计算机子网络，计算机，计算机内部的处理器，存储器，通信设备，其它元件 或设备) 集合与通信信道( 有线或无线的) 集合按一定的点对点方式相互连接所形 第l 章绪论 成的系统。组件之间的连接方式是决定网络性能和价格比的一个重要因素，因此 研究网络之间的连接方式显得尤为重要。 网络中组件和组件之间的连接方式称为网络的拓扑结构( 陈宝兴，2 0 0 4 ) 1 。 网络的拓扑结构是设计计算机互连网络或制造超大规模并行计算机系统的第一 步，也是实现各种协议的基础，它对网络的性能、系统可靠性和费用都有重大影 响。在分析网络拓扑结构时，人们通常把网络中组件抽象成一个点，把通信信道 抽象成两点之间的连线，那么该网络的拓扑结构就被抽象成一个图。 从2 0 世纪7 0 年代至今，国内外有关双环网络研究的论文可以分为七类：直 径下界问题、直径上界问题、直径问题、平均直径问题、紧优性问题、最优路由 问题和容错性问题。长期来人们利用离散数学和组合数学的知识进行研究，近年 来计算机仿真的手段也逐步引用。 w - o n g 和c o p p e r s i i l i m ( 1 9 7 4 ) 最早研究了下述优化问题：对每一个4 ， 确定并找出最优的双环网络。针对有向双环网络删：，回，w ，0 n g 和c o p p e r s r i l i 廿l 给出了d 的一个下界是硒= l 3 | - 2 。针对无向双环网络g i ( 1 v ；= 打，埘，w r o n g 和c o p p e r s m 油给出了吠忉的一个下界是：场( ) = ( 2 一3 ) 2 。b o e s c h 和w 觚g ( 1 9 8 5 ) 以及y e b r a 等( 1 9 8 5 ) 将上述结果改进为：似加= l ( 2 一l 一1 ) 2l ， 这里lxl 表示不小于x 的最小整数。直径下界问题已经得到很好的解决。 对于有向双环网络g ( ；1 ，s ) ，f k h w a n g 与y h x u ( 1 9 8 7 ) 证明了当n = 6 3 4 8 时。其上界为3 甩+ 2 3 刀+ 5 ，r o d s e t h ( 1 9 9 6 ) 证明了当n = 1 2 0 0 时，其上界 为3 以+ 3 聆+ 2 5 。这两个上界公式显然是冲突的。 对于有向双环网络g ( ；l ，s ) ，我们在文献( 方木云等，2 0 0 5 ) 中指出：当 为奇数时，s = ( + 1 ) 2 是中心，直径吠；l ，d 在j = 2 ，( + 1 ) 2 ，一1 ( 即最左端， 中间点，最右端) 取得最大值疗= ( 一1 ) 2 ：当为偶数时，s = 2 和s = ( 2 ) + l 两点是中心，直径故1 ，d 在s = 2 ，2 ，( 2 ) + l ，一l ( 即最左端，中间两点， 最右端) 取得最大值刀= 2 ；这是由有向双环网络自身的对称性决定的。 对于无向双环网络g ( 1 ，埘，我们在文献( 方木云等，2 0 0 7 ) 中指出：当 为奇数( 4 刀1 ) 时，s = ( + 1 ) 2 和s = ( 一1 ) 2 两点是中心，直径批1 ，虹) 在 s = 2 ，( + 1 ) 2 ，( 一1 ) 2 ，一2 ( 即最左端，中间两点，次右端) 取得次大值 以= ( 1 ) 4 ：当为偶数( 4 疗，4 刀一2 ) 时，s = 2 点是中心，直径吠啦l ，盘) 在 s = 2 ，2 ，一2 ( 即最左端，中间点，次右端) 取得次大值玎= 4 或( + 2 ) 4 ； 这是由无向双环网络自身的对称性决定的( 为大于1 的自然数) 。当s = 一l 时， 由同余方程可知，无向双环网络变为有向双环网络，其直径才取得最大值：当 2 第1 章绪论 为偶数时，取得最大值刀= 2 ；当为奇数时，取得最大值珂= ( 一1 ) 2 。 f k h w a n g 和r o d s e t h 是从所有的角度来考虑双环网络的直径上界，我们 是从每个，然后变化其步长来找出这一族双环网络的直径上界，有些区别。 w r o n g 和c o p p e r s m i t h ( 1 9 7 4 ) 提出下述几何构图：把e u c l i d 平面上第一象 限的所有格点排成序列，q ，0 ) ，( o d ，q 0 ) ，q ，d ，蛾2 ) ，虢肪，q 乩d ， ，酝一f ，f ) ，q 七一d ， 七) ，。每个格点用以它为左下角的单位方 格代表，并依次在每一方格q ，j ，) 处安置数后 0 卜，一l ，其中后量耵+ 咖( m o d 叻。 如在此之前数七已出现过，则空出此格，考察下一格，直到数0 l ，一l 都出现 为止。易知若数后位于方格如力处，则删；， 国中从结点o 到结点七的距离是x + y 。 图1 1 是g l ，7 ) 所确定的构图。已经证明，由删：协所确定的个方格组 成的构图呈图1 2 所示的三形区域，称为三形瓦( 三一s h a p et i l e ) 。下面介绍形 瓦的一些参数。 ， n = l h 一列 y 工 图1 1 l ，7 ) 所确定的构图图1 2 三形瓦 如图1 2 所示的三形区域称为具有参数以鬼五力的一个三形瓦，其中己髓五) ，都 是整数，并规定， 办2 ，o x z ，l y = o ) 紧优双环网络。传统思路是用离散的方法来构造k ( k = o ) 紧优双环网络，无限 变化，是从纵向的角度来研究。方木云等用连续的方法来构造k ( k = 0 ) 紧优双环 网络，不变化，是从横向的角度来研究( 邰伟鹏，方木云等，2 0 0 7 ，2 0 0 8 ) 。 直径上下界、直径、平均直径和紧优性都是从双环网络的所有节点来考虑的， 那么任意两个节点如何以最优的路线进行信息传输? 这属于最优路由算法的问 题。 yc h e n g f k h w a n g 等( 1 9 9 2 ，1 9 9 8 ) 研究了路由算法。 陈协彬( 2 0 0 4 ) 、冯斐玲等( 1 9 9 4 ) 通过路由算法来求得特定双环网络的直 径。 陈忠学( 2 0 0 1 a ) 提出了双环网络 + 1 边优先最短路径及其寻径策略，还研 究了特定双环网络的最短路径问题( 2 0 0 l b ，2 0 0 1 c ) 。方木云，赵保华等( 2 0 0 8 ) 提出了双环网络 + h 边优先最短路径及其寻径策略。陈宝兴( 2 0 0 4 ) 提出了一类 无向双环网络的最优路由算法。 以上研究都是假设节点j 下常的情况，如果出现节点损坏等不正常现象的时 候，这需要研究双环网络的容错性问题。双环网络是出度小且度固定的对称循环 网络，具有一定的容错性。 国夕 f k h w a i l g ，x d h u ，e t a l ( 1 9 8 5 ，1 9 8 9 ，1 9 9 5 ，1 9 9 7 ，1 9 9 9 ，2 0 0 0 ，2 0 0 1 ) 对容错性进行了研究。陈宝兴( 2 0 0 4 ) 在其博士论文中定义了厂一容错和极大容 错的概念。游德有( 2 0 0 7 ) 5 在其硕士论文中研究了容错平均距离。李晓明( 1 9 9 0 ) 和聂晓冬( 2 0 0 2 ) 也对容错性进行了研究。 近年来，国内影响双环网络学术研究发展趋势的相关作者和关注度的曲线图 ( 来自c n k i ) 。如下页图1 3 。 从图1 3 看出方木云作了一些影响双环网络学术研究发展趋势的工作。 由于双环网络是一个图论的问题，长期以来多是数学工作者从事其研究，尽 管在直径上下界、直径、平均直径、紧优性、路由算法和容错性等方面做出了丰 硕的成果，但仍然存在以下不足的地方： 通用的、显式的直径公式还没研究出来，目前的直径求解公式都是针对某些 特例的双环网络。三形瓦只能隐式地求解有向双环网络的直径，不能求解无向双 环网络。刘焕平等通过同余方程来构造了有向双环网络的直径公式。陈协彬、冯 斐玲，陈忠学等提出的路由算法也只针对特定的双环网络。 第1 章绪论 。麓蓬薹鬣霪：j 嬲 c n k i 脚l 黼酽! 。 学术趋势：a i 蟊氍i 菇蔺翻i 目鹾遴i ：羔。瀣 妒 尘 相* 储。 膳元陈皇* 棣惶明自文慢恿艟h 方耘靳善辱 更$ 登雾 m f * k 镕镕* ；g t d 女 t 娃i 撕i 目q 啪 ，j 工i 啦互龟班砸嗡蝴啦i 殳j 土 镕蚩* 女# 2 1 女 i p 耍班啮趟世血盘影氆皿盟筋瞳 镕0 靳瞢一# 赫6 p 生瞄隧封盥受翻璺刿醚盟直簋洼 睬协w 一被 【数8 班 - # 图1 3 般环网络学术研究发展趋势 紧优双环网络的寻找方法被动。基本上都是找到一个紧优双环网络，然后构 造其无限族。或找到一个 d 紧优双环网络，然后构造其无限族。不能作到任 给一个双环网络，判断其紧优性。用离散的方法柬研究双环网络的紧优性，不能 利用连续的方法来研究其紧优性。 双环网络的平均直径很少研究。平均直径表示双环网络中信息传输的平均延 迟，是度量其性能优劣的另一重要特征参数，因此值得研究。到目前为止，直径 只有隐式数学表达式，而平均直径只有定义式的数学表达式，难以求解，这也许 是平均直径没有得到广泛研究的原因之一。 研究手段单一，局限在数学方法仅用离散和组合数学的知识来进行研究。 1 2 研究方法和内容 宽度优先搜索( b f s ) 是很多重要的图的算法的原型。d u k s ”a 单源最短路 径算法和p m 最小生成树算法都采用了和宽度优先搜索类似的思想。之所以称 之为宽度优先算法，是因为算法自始至终一直通过已找到和束找到顶点之间的边 界向外扩展，就是说，算法首先搜索和顶点距离为 的所有顶点，然后再去搜索 和顶点距离为女+ l 的其它节点。宽度优先搜索( b f s ) 显然可以用于二双环网络直 径的求解。 第l 章绪论 基于宽度优先搜索( b f s ) 这一核心思想，本文采用仿真方法来进行实验研 究，并运行数学方法来对实验结果进行理论证明。建立了一个仿真系统平台，用 于分析研究双环网络的直径、平均直径、紧优性和等价拓扑结构；制订双环网络 一系列直径、平均直径、紧优性手册，供局域网和并行计算设计者参考。 本文以g ( ；，j ) ( 固定，而步长，s 变化，即：1 ，s ) 这样一族双 环网络为研究单元来进行研究。对双环网络的直径、平均直径、紧优性、三形瓦、 路由算法和几种等价拓扑结构等问题进行了研究，容错性方面没有进行研究。 1 3 论文安排 第二章到第七章的内容都是我们分别发表在华中科技大学学报、通信学报、 计算机工程、系统仿真学报和计算机学报等刊物上的成果。 第二章，直径和紧优性分别是双环网络最基本和最重要的问题，如何设计直 径到达下界的紧优双环网络是双环网络领域研究的核心问题。本章提出了双环网 络直径和紧优性求解的通用算法一遍历法。这是本文的核心思想，是其它工作研 究的基础。 第三章，紧优性一直是双环网络研究的重要方向，传统思路是寻找一个紧优 双环网络，然后构造其无限族。本文是固定，变化其步长，然后寻找紧优的双 环网络。本章研究对某个固定的值，能够构造多少个紧优双环网络? 随着值 的增大，能够构造紧优双环网络的比率是增大还是减小? 本章研究结论：紧优双 环网络的个数并不随值的增大而增加，而是在一定范围中波动出现；当值较 小时，能构造紧优双环网络的比率大，当值变大时，能构造紧优双环网络的比 率逐渐下降。 第四章，双环网络的直径表示双环网络中信息传输的最大延迟，是衡量双环 网络性能优劣的重要特征参数。双环网络的平均直径表示双环网络中信息传输的 平均延迟，是度量双环网络性能优劣的另一重要特征参数。一个直径和平均直径 同时达到最小的双环网络才是信息传输性能最好的双环网络。本章研究发现紧优 双环网络的平均直径在一细沙中不一定最小，所以我们应该设计比紧优双环 网络更优的双优双环网络。 第五章，三形瓦是双环网络直径求解的一种等价拓扑结构，是双环网络直径 的空间解表达形式。早期研究一般通过等价形瓦的直径来得到双环网络的直 径，因此对任意一个双环网络，如何快速准确地得出其等价的三形瓦是一个值得 7 第l 章绪论 研究的问题。随着的增大和步长的增多，手工构造形瓦是不可能的，借助计 算机来生成三形瓦并研究其形状和参数的分布特征是很有意义的工作。本章仿真 绘制了有向单位步长和有向非单位双环网络的三形瓦。 第六章，双环网络是一种网状拓扑结构，为了求其直径，往往将其转换为其 它等价的拓扑结构。传统的上形瓦是其中一种。树是一种典型的数据结构，本章 研究将双环网络生成等价树，并分析生成树的特征，通过生成树可以得到双环网 络的直径。 第七章，遍历法适合所有双环网络的寻径，对于特定的双环网络还有一些寻 径策略。针对有向单位步长双环网络g ( ；1 ， ) ，提出了一种 + 明边优先的寻径策 略，并得到一种新的竹筏型三形瓦。 第八章，总结了本文的研究内容和主要创新点，提出了今后的研究方向：信 息阻塞、容错性和更好的仿真算法。 第2 章双环网络直径和紧优性 第2 章双环网络直径和紧优性 2 1 基本概念 双环网络的直径是指任意结点对之间的最小距离中的最大者，因此，它表 示双环网络中信息传输的最大延迟，是双环网络信息传输的重要特征参数，是 双环网络研究的最基本问题。直径达到下界的双环网络称为紧优的，寻找和构 造紧优双环网络是双环网络研究的最重要问题。 本论文将双环网络的寻径问题处理成数据结构中的遍历问题。由于双环网 络的对称性，双环网络中任意结点间的最短距离，可以看成o 到其它结点之间 的最短距离。通过宽度优先( b f s ) 的遍历方法可以求得0 到其它结点之间的 最短距离，这些最短距离的最大者就是双环网络的直径。 遍历法适合于有向双环网络和无向双环网络中的任意网络，易于理解、便 于计算机编程实现，是本论文的核心思想。本章成果发表在华中科技大学学报 和通信学报( 方木云，赵保华，2 0 0 6 ，2 0 0 7 ) 等刊物上。 2 2 有向单位步长双环网络 有向单位步长双环网络的图论模型是指这样一个有向图g ( ；1 ，s ) ：它的每 个顶点记为o ，l ，2 ，一l ，并从每个顶点f 发出两条有向边f 专f + 1 ( m o d ) 和 f f + s ( m o d ) ，分别记为【+ 1 】边，【+ s 】边，其中s 是自然数，且l s 。 2 2 1 遍历寻径法 定义2 1 有向图g ( ；l d ，它的每个节点记为0 ，l ，一l ，从节点f 发出两条 有向边f 专f + l ( m o d 7 v ) 、f 专f + 文m o d 7 v ) ，分别记为【+ 1 】边和 + s 】边，其中s 为自然 数，且l s ，由引理1 知：o 到其它节点距离最短的集 合是 垅吗，甜 ，显然m 垃吗 甜 _ ”，因此诫；1 ，d = “。 遍历法得到双环网络直径的显式公式矾m 1 ，回= 甜。它的核心思想是：从节点 0 出发，寻找第坛，甜步首次能够到达的节点。 2 2 2 寻径算法 根据分步法求双环网络g ( 1 ，s ) 的直径，有如下算法2 1 ： 算法2 1 ：分步法寻径 p r o c e d u r es t e p s e a r c h d i a m e t e r ( ，s ，f ，刀矗9 1 ，7 豫2 ) 加g l ，月唱2 代表节点状态，分别表示已访问和刚访问 s t e pl ：初始化，给定和j ，循环变量汪l ，o 节点作为起始点，其月昭l = 0 ， 乃孵2 = 1 ：其余各点以穆1 = o 、月唱2 = o 。 s t e p2 ：从0 点出发，发出 1 】、 s 】两条边去访问其它点，置o 节点的月唱1 = 1 ， 被访问的两点刀唱2 = 1 。 l o 第2 章双环网络直径和紧优性 s t e p3 ：从刚才刀曙2 = l 的两点分别发出 1 】、【s 】两条边去访问其它点，置 这两节点的加g l = 1 ，检查被访问点是否已访问( 是否脚= 1 ) ，若是，空过； 若不是，置其伽9 2 = l 。检查所有节点是否加9 2 = l ，若是，到s t e p 5 ；若不是， 到s t e p 4 。 s t e p4 ：从乃曙2 = l 的所有点分别出发，发出 1 】、【s 】两条边去访问其它点， 检查被访问点是否已访问( 是否乃昭l = 1 ) ，若是，空过；若不是，置其月曙2 = 1 。 检查所有节点是否乃踞2 = 1 ，若是，到s t e p 5 ：若不是，到s t e p 4 。 s t e p5 ：退出循环，输出f ，f 即为双环网络的直径。 e n ds t e p s e a r c h d i a m e t e r 该算法存在两重循环，外层f 从1 到f 2 循环，内层循环是在刚访问节点 集个数上循环，时间复杂度为0 ( 玎2 ) 。 该算法需要空间存储节点及节点的两种状态，空间复杂度为d ( 刀) 。 2 2 3 寻优算法 在实际应用中，可能关心固定，2 s 一1 这样一族双环网络的直径， 找出取得紧优的s 值，下面给出其求解算法。 算法2 2 ：分步法寻找紧优双环网络 p r o c e d u r es t e p s e a r c h 一0 p t i m a l ( ，j f ，f ，7 1 7 矗9 1 ，7 1 7 矗9 2 ，场( ) ) ，6 = r 3 1 2 1 0 0 p _ ，= 2 ：，+ + ：一1 s2 j c a l ls t e p s e a r c h d i a m e t e r ( ，s ，f ，_ ，死瑶1 ，皿培2 ) i f ( f = 肠) 输出j r e p e a t e n ds t e p s e a r c h o p t i m a l 该算法存在三重循环，外层从2 到一1 循环，中层f 从1 到f 2 循环， 内层循环是在刚访问节点集个数上循环，时间复杂度为d 0 3 ) 。 该算法需要空间存储节点、节点的两种状态和s 值，空间复杂度为d ( ，z ) 。 应用分步法可以计算出这样一族双环网络的直径，并找出使双环网络取得紧优 或几乎紧优的s 值。 第2 章职环网络直径和紧优性 2 24 仿真实倒 根据上面的两个算法在我们研制的仿真平台上进行了直径和紧优性的仿 真。固定_ ，变化步长s 的值这样一族双环网络的直径和紧优性图形化显示出 来。限于篇幅，下面仅列举了= 1 0 0 和= 1 0 0 0 的两个实例。 ( 1 ) = 1 0 0 号o ，r = ，1 4 。9 2 0 o o o o o o o 一一。 l 一r 4 j 一 _ ( 2 ) ，= 1 0 0 0 圈2i 烈环网络g ( 1 0 啦0 直径和紧优分布图 _ 一j m 一j - - 一口 图22 戕环网络g ( 1 0 0 q l ，j ) 直释和紧优分布图 图2l 和图22 中，横坐标为步长，纵坐标为每个双环网络的直径。直径 第2 章双环网络直径和紧优性 曲线的下面打点处是紧优双环网络。从仿真图我们可以得出： 1 双环网络g ( ；l ，d 的直径d ( ；l ，s ) 以s 的中心对称分布。当为奇数时， s = ( + 1 ) 2 是中心，直径d l ，s ) 在s = 2 ，( + 1 ) 2 ，一1 ( 即最左端，中间点， 最右端) 取得最大值疗= ( 一1 ) 2 ；当为偶数时，s = 2 和s = ( 2 ) + 1 两点 是中心，直径烈；l ，s ) 在s = 2 ，2 ，( 2 ) + l ，一l ( 即最左端，中间两点，最右 端) 取得最大值疗= 2 ；这是由有向双环网络自身的对称性决定的。 2 对任何j l + s 2 = + l ，则有以1 ，s i ) = 以；l ，s 2 ) ，因此对任何，其紧优、 几乎紧优和七紧优双环网络是成对出现。 2 2 5 等价螺旋环 分步法的特点是：寻找每步首次能够达到的节点集，即寻找第l ，2 ，甜步可 到节点集，这些发射边和节点集可以构成一个新的直观模型一螺旋环。 螺旋环三g ( ，1 ，j ) 构造如下： 1 ) 第0 环放节点o ，发出【1 】边和【s 】边； 2 ) 第l 环放节点1 ，s ，连上两条有向边，从l ，s 两点分别发出 1 】边和 s 】 边。 3 ) 若 ，= x 【1 】+ j ， s 】( m o d ) ，x + y = c 2 ，x 0 ，少0 且1 ，在o 至c 一1 环中 都没有出现过，则把1 ，放在第c 环，且连上有向边，从第c