（通信与信息系统专业论文）wdm网络中基于分层图的静态rwa算法研究.pdf

l笾丝型丝 l 墅! 丝! 篓哆 l g r a n d 和l g 模型，并对三种 算法进行了改进，并对改进前后的算法做了比较，仿真结果证明改进后的算法台黟一 节省更多的光纤。 ，其中w e 形，p p 。 l w ，p ，l e p 最小阻塞通路优先( f i r s tp a t hl e a s tc o n g e s t ，f p l c ) ：该算法可具体分为 w t f p l c 和l p f p l c 。其中w t f p l c 计算每条通路上的可用波长数，选择可用波 1 4 重庆邮电大学硕士论文第二章w d m 网络中的r w a 问题 长数最多的通路建立连接： p 。2 警，善u 睁劬，们】) ， 譬0 孑翟三：其中删为单位阶跃函数，满 足。而l p f p l c 是设计多纤网络的一种算法，它计算每条通路上的可用信道数， 选择可用信道数最多的通路：p - m 。a p x i 出 c ( 缈，w ) 】。在单纤网络中l p f p l c 将退化成w t f p l c ，而在多纤网络中l p f p l c 的性能优于w t f p l c 。 整数线性规划法( i l p ) 3 0 , 3 2 , 3 3 1 ：这是一种常用的选路和波长分配算法，可分为 基于流的i l p 和基于通道的i l p 。在这种方法下选路灵活，适用于有或无波长变换 功能的小型网络，网络可以具有或不具有故障恢复机制。 2 3 2 波长分配子问题 由于r w a 问题本身是一个整体，只是为了简化研究而被拆分为路由选择和波 长分配两个子问题，因此路由选择的策略和波长选择策略对于r w a 算法性能都有 很大的影响。所以，在此也把波长分配的问题作简要介绍。 假设网络中共有条链路，每条链路支持的光纤数为只每根光纤支持的波长 数为肌三例代表通路p 的链路集合。l c ( t ，z ，代表链路j 上波长九剩余的可用信 道数。p c 俨，a ) 代表通路尸上波长为九的最小可用信道数，称为通路尸上波长兄的 瓶颈数。尸，为新到达的呼叫对应路由。彳伊= j 代表尸骼由上对应的可用波长集。g 俨夕 代表与通路p 具有公共链路的固定路由集合。称通路p ( p g ( p s ) 为通路尸的相邻 通路。文献【3 i 】提出的常用动态波长分配算法主要有： ( 1 ) 随机波长分配( r a n d o m ，r ) 算法：首先遍历所有波长，确定在选定路由 上的可用波长集合，再从中随机选取一个分配给光通道。这种算法不必考虑当前 网络资源的占用情况，所以时间复杂度低，为d 仰，但对于网络性能的改善不明 显。 ， ( 2 ) 首次命中( f i r s t f i t ，f f ) 算法：该算法将波长在可用波长集a 俨，中按固定 顺序排列( 如按波长由小到大顺序排列) ，对新到达业务通路尸，每次选择波长时均 从彳俨 中按固定顺序选择可用波长。与随机波长分配算法相比，f f 不必搜索全部 波长，而是找到可用波长就停止，计算量更小，且算法的阻塞性能要好于随机分 配。其时间复杂度为o ( - w ) 。 ( 3 ) 最小使用( l e a s t u s e d ，l u ) 算法：该算法统计全网所有波长的使用率， 并选择波长使用率最小的可用波长分配给尸。这种算法的出发点是平衡所有波长 的负载，将网络流量均匀分摊到各个波长上，需要利用网络资源的占用情况。假 设所有链路上光纤数的上界为凡则其时间复杂度为o ( w l f ) ，高于r 和f f 。 重庆邮电大学硕士论文第二章w d m 网络中的r w a 问题 ( 4 ) 最大使用( m o s t u s e d ，m u ) 算法：这种算法与l u 正相反，优先选取使 用率最高的可用波长，其时间复杂度同l u 一样，为o ( w l f ) 。实践证明该算法的效 率明显优于前三种算法，它有助于将网络负载集中在少数波长上，这样可以减少 网络的波长需求。 ( 5 ) 最大总和( m a x s u m ，m s ) 算法：经该算法选择波长后，全网其它通路 的剩余可用信道数总和最大其优化目标函数为： 矧m a x ( p 磊，蹦尸，) 其中，凡伊，兄) 代表分配波长旯后，通路尸上波长为旯的最小可用信道数。 这是一种既适用于单纤网又适用于多纤网的算法。其基本思想是对于一个光路连 接请求，除了待分配的连接本身外( 因无论分配哪个空闲波长，对本身所产生的 影响都是只减少一个信道) ，计算对该连接分配某波长后网络其它通路所剩余的 可用信道数的总和，取其中最大值对应的波长来建立连接。该算法的目标是保证 分配该波长后全网所有通路的可用信道数最大。 ( 6 ) 最小影响( l e a s ti n f l u e n c e ，l i ) 算法：经该算法选择波长后，对全网其它 通路的影响最小( 对相关通路造成的瓶颈总和最小) 。其优化目标函数为： ( d ( l c ( t ，a ) ，p c ( p ，兄) ) ) 鼽 。( l c n 唧埘) _ 嬲主黝。 ( 7 ) 相对容量损失( r e l a t i v ec a p a c i t yl o s s ，r c l ) 算法，该算法选取的优化目 标函数为： 耐毛 u ( d ( l c ( 1 ，a ) ，p c ( p ，力) ) ) p c ( p ，z ) 式中，) 为单位阶跃函数，当a 0 时取值为l ，否则取值为0 。该算法基于 m s ，m s 致力于将绝对空闲容量最大化，而r c l 则致力于将相对空闲容量最大化。 具体为对所有的波长，依次计算为该通路分配该波长后，其它各通道上减少的可 用信道数与其相应的可用信道总数的比值，累加此比值，从中选取比值最小的波 长。 m s 算法虽然在一定程度上考虑了网络的状态，但是它只考虑了各相关业务( 即 与新光路有共享链路的通路) 上减少的总信道数这一绝对值。但是各相关业务之间 的情况也是不同的，比如说各个相关业务各自所剩余的信道总数就可能各不相同。 而r c l 算法则考虑到了这一点，用相对值来描述新光路的建立对全网状态的影响， 较m s 的描述更加精确，且在性能上也优于m s 。 1 6 重庆邮电大学硕士论文第二章w d m 网络中的r w a 问题 ( 8 ) 相对最小影响( r e l a t i v el e a s ei n f l u e n c e ，r l i ) 算法。该算法选择的优化 目标函数为： i乏：d ( l e q ，a ) ，p e ( p ，a ) ) i m i a ；4 ( p n 9 懦专丽矿一l ， l | p e 6 ( p 厶1o ，i 肌。( l c n 唧卅，= ：；，嚣裘麓 目前，已有的算法中，性能较好的算法为r c l 和r l i 算法。在r c l 算法中，分 配波长给p 时，优化目标中考虑了相对的容量损失，故能区分尸的所有相邻固定路 由中具有相同容量损失的情形。因此，相对值比绝对值更准确地描述了网络的状 态，r c l 算法优于其之前的算法。r l i 算法在r c l 算法的基础上，记录了当分配波 长给尸时，所有瓶颈链路造成影响的相对值，因此，r l i 算法描述的网络状态比r c l 更准确，其性能也优于r c l 算法。 在以上这些经典的波长分配算法中，为了集中研究波长分配策略，简化网络 的控制和管理，通常采用预先固定选路的方法，即：先采用简单的最短路由法( 如 d i j k s t r a 算法) 找出最短路由之后，再分配波长。在网络通信中，路由选择的策略一 般是以降低路由代价为优化目标。 总之，算法依据的信息越多，其性能就越好，但性能的改善是以存储量和处 理时间的增加为代价的。 2 4r w a 算法总结 2 4 1 约束条件与目标函数 在无波长变换器的w d m 波长路由网络中，求解r w a 问题时主要受以下两个条 件约束： 1 ) 波长连续性限制，即每一个光通路所使用的波长在从源节点到宿节点的所 有链路上都是相同的，这一限制是由物理规律造成，它是透明光网络中的基本要 求。 2 ) 同一光纤中的不同光通路必须分配不同的波长，这是保证网络能够正常运 行的限制条件。 r w a 的目标是完成网络物理拓扑和逻辑拓扑之间的最佳映射，即给定网络资 源而最大化网络的某些特性，如可以建立的连接数、波长的复用率等，或者给定 光连接数目而最小化所需要的网络资源数目或代价。由于问题的复杂性现有的 1 7 重庆邮电大学硕士论文第二章w d m 网络中的r w a 问题 算法通常只以网络中许多需要优化的特性中的一个作为目标函数，由此来评价算 法的性能，因此在不同的算法中选择的目标函数可能不同，理想的目标函数应当 是给定网络元素( 如设备) 的费用或价格后寻求最小的网络代价。 2 4 2 r w a 算法分类 目前已有大量的r w a 算法按照算法所共有的特征对其进行分类，以总结研究 的现状，对进步研究更优性能的算法也有启发意义。 算法分类结果如图2 4 所示，首先按照实际中的求解过程把问题分成选路和波 长分配两部分。每一个子问题中又分成两步，即寻找与选择，最后按照所用的具 体算法进行分类。当采用最短路或加权最短路算法时，为每一个光连接寻找到一 选路与波长分配 算法( r w a ) 整体分析 算法 拆分分析 算法 整曩蔷性i 分层图if 其它算法| i 选路算法if 波长分配算法 l 型f ! 垄苎竺兰f 鬯 图2 4r w a 算法分类 表2 1 选路算法 混合算法 顺序算法( 贪婪算法)启发式算 法 优化算法 选择顺 随机固定 最长路优最短路优 整数线性规 序先先 随机循环 划( 多商品流 选择规 随机 以概链路权最f i r s tf i t 问题) 则 率小( f f ) 1 8 重庆邮电大学硕士论文第二章w d m 网络中的r w a 问题 表2 2 波长选择算法 混合算法 顺序算法( 贪婪算法) 启发式算法优化算法 选择 邻居可用波业务量路由路由随机循环 最多长最大最大优最长最短遗传算法 顺序 优先优先先优先优先模拟退化算穷尽式搜 法 索 选择 随机 最少使最多使 f i r s tf i t ( f f )禁忌搜索算 规则用优先用优先 法 条路由时，就得到了选路子问题的解。当采用k - 最短路时，得到了k 条路由。需 要从中选择一条最佳路由。在波长分配中，所有可用的波长都是选择对象。表2 1 和表2 2 中分别给出了一些主要算法在选路和波长分配中所采用的具体实现方法。 2 5附加问题 r w a 问题是w d m 波长路由光网络设计中的一项关键技术，它不但影响网络中 波长的利用率，而且会影响网络的其它特性，如业务容量、设备端口数、传输时 延等。从目前的研究水平来看，r w a 算法设计中仍有以下问题需要解决。 2 5 1波长变换器问题 引入波长变换可使在一条光路上分配波长时更灵活，动态建立光路时阻塞率 减小。文献【4 7 】研究了各种不同的配置情况一网络中只有少数节点配置有全波长变 换o x c ，称为稀疏波长变换；o x c 只有部分端口具有波长变换( 如只能在几个波 长间变换) ，即波长变换范围有限。上述两种情况可互相组合。对于不同的配置， 除了要解决r w a 问题外，还要解决如何实现最佳配置问题。由于波长变换器价格 昂贵，而且技术上有限制，因此波长变换在网络中的作用仍是一个争论的焦点， 波长变换对r w a 问题结果的影响以及怎样在网络中引入波长变换以达到性能最佳 等问题的研究还需要进一步深入，以便得出更确切的结论。 波长连续限制很容易造成波长阻塞，即空闲的路由上没有一条端到端的空闲 波长。w d m 光传送网中，在网络节点处引入波长变换可以消除波长连续性限制， 从而能够避免波长阻塞，提高网络性能。目前文献中关于静态业务下波长变换对 网络性能的改善程度( 增益) 并无定论。比较一致的看法是：波长变换的增益与网络 1 9 重庆邮电大学硕士论文第二章w d m 网络中的r w a 问题 拓扑、网络大小、业务分布、波长数以及光路的长度等因素都有关m j 。对于必须 支持所有业务的单光纤网，有无波长变换对应的波长数之间的差距很小，低于 2 【2 引。而对于多光纤网【2 6 1 ，在每根光纤的波长数较少( 例如波长数为4 ) 时，波 长变换只能减少不到1 0 的光纤端口；而波长数较大( 例如波长数为1 8 ) 时，则 能减少8 0 。随着备用选路和重选路的引入，波长变换的增益迅速下降。文献1 3 即”研 都表明，波长变换的增益与网络的连通度也有密切关系：对于连通度较小( 如环 形网) 和较大( 如全连通网络) 的网络，增益较小；而对于中等连通度( 如网状 结构) 的网络，增益达到最大。并且增益随着平均网络距离的增加或者随着波长 数的增加而缓慢增加，但是却随着业务强度的增加或光纤数的增加而迅速下降 2 5 3 9 , 4 8 】。理论分析 4 9 - 5 1 】也得出了类似的结论。采用部分波长变换( 如变换能力仅 2 5 的波长变换 4 9 1 、稀疏波长变换以及有限数目( 1 0 ) 的波长变换器 s q ) 就能达到 或逼近采用全功能全范围的波长变换所带来的增益。 理论分析和模拟结果都表明，在动态业务条件下，采用波长变换获得的增益 与静态业务下类似，也是与网络连通度、网络大小、波长数、业务强度以及链路 光纤数密切相关。尽管有波长变换时单跳和多跳连接的公平性较好，但是，如果 在无波长变换的情况下为多跳光路准备多条备用路由，得到的平均阻塞率就会小 于允许波长变换的固定选路算法。文献【4 1 】考察了1 6 1 0 0 0 个节点的随机网络：如 果采用固定选路和首次命中波长分配算法，引入波长变换能使波长重用因子增加 1 0 3 9 。但是由于设定的阻塞率高达1 0 。2 ，其结论对于设计实际网络意义不大。 与静态业务下的情况类似，在动态业务时引入部分波长变换，如固定选路下有限 数目的波长变换器，固定选路加上有限范围波长变换器，固定选路加上有限数目 的有限范围波长变换器，备用选路加上部分节点配置数目有限的波长变换器，也 能达到或逼近所有节点均配置全功能全范围的波长变换器时的增益p 引。 在没有波长转换器的情况下，波长连续性限制可能会造成波长阻塞。引入波 长变换能够减少波长阻塞，提高网络性能。引入波长变换与无波长变换相比的得 益程度与网络拓扑、业务分布、波长数等因素有关 3 9 , 5 1 , 5 2 】。这些都是值得进一步研 究的。对于波长转换器的不同配置，除了要解决r w a 问题外，还要解决如何最佳 配置问题。 2 5 2 性能优化问题 网络设计需要优化的目标【4 7 】j 艮多，但现有的文献大多仅考虑其中的一个，其 结果虽然在某一个网络特性上达到了最优，但由于缺少各个特性之间的均衡与折 中，网络的代价并没有因为r w a 算法的优化而降低。因此，需要研究基于提高网 重庆邮电大学硕士论文第二章w d m 网络中的r w a 问题 络综合性能( 如业务分级优化、公平性等) 的合理的r w a 算法。 2 5 3 多光纤网络的r w a 问题 目前很多算法是针对单光纤网络提出的。多光纤链路为算法提供了在空间域 的对光纤的多个选择，多光纤网络的r w a 算法将被逐渐重视。 多光纤w d m 网络的存在主要基于以下原因：首先，从光网络的生存性与保 护光路的角度出发，几乎所有实际的光纤网络的干线都是多光纤的；再者，由于 光纤的损耗以及节点设备的插入损耗，必须引入e d f a 进行补偿，但是级联多个 e d f a 后总的有效增益带宽会下降，光纤复用的有效的波长通道减少，需要增加光 纤数来满足通道数的要求。最后，在多光纤网络中，使用同一条链路的不同光纤 上的相同波长是完全等效的，可以部分缓解波长连续性限制所引起的算法计算量 大甚至光路连接请求被拒的情况。 2 5 4 光信号的传输损伤 通常来讲，光纤传输的信号质量相对于铜导线或无线传输要好得多，但是由 于波长路由光网络覆盖的地理面积很大，光信号的传输需要经过大量的中间节点 和长距离的光纤段。为使光信号能够在特定的光路传输，在中间节点，无源的交 叉连接器进行光交换，虽然光电的控制机制是有源的，但仍然导致信号功率的损 失。e d f a 在补偿长距离光纤传输产生的功率损耗的同时，引入了放大的自发辐射 ( a s e ) 噪声，并且不同波长不同的放大增益及增益饱和导致e d f a 的增益与流量 有关而变得不可确定。另外，光纤中的色散、交叉连接器中的串扰等都能导致光 信号质量的下降。这些因素统称为传输损伤【7 0 - 7 2 1 。 传输损伤会造成信号质量的下降，当信号到达接收端时，它的信噪比过高时， 就会造成信号的误码率过高。当信号的误码率超过某特定门限值时，业务信号将 因识别不出而被接收端丢弃。 为了防止出现这种现象，这里我们在研究w d m 网络的r w a 算法时，将信号 的传输损伤考虑到算法中来，尽量使信号的传输距离不要太远，通过限制业务的 传输距离来达到保护信号的目的。 2 5 5 服务质量问题 选路和波长分配过程所选择的光通路一般都没有考虑物理层传输系统的约束 2 1 重庆邮电大学硕士论文第二章w d m 网络中的r w a 问题 和高层业务的要求，但网络实际运营时要引入各种策略，例如引入优先级d 3 1 ，某 些光路必须经过某节点，某些光路不能经过某节点，选择的光通路必须满足w d m 传输系统通路最大长度约束等。要解决这些额外要求必须有相应的r w a 算法。 优先权属性主要反映业务流主干的相对重要性。当在g m p l s 中采用基于约束 的路由方案时，优先权就显得更重要。因为根据优先权属性可以决定业务流主干 建立光路时可以选用的资源集合，也就是应该首先满足优先权高的业务流主干的 光路建立需求。另外，优先权在通路抢占中也起着关键作用。抢占属性规定在网 络资源紧张时，高优先权的业务流主干可以去抢占比较低的优先级业务流主干对 应的资源。根据业务流主干的优先权属性的不同，在光层提供的服务也应该有等 级差别，可以通过光路的传输质量以及光路建立请求的阻塞率等指标来衡量。 在研究w d m 光传送网中的r w a 问题时，应该将光层所能提供的传输质量以 及业务量工程中网络操作者直接给业务流主干配置的基本业务量工程属性等约束 条件加以考虑。考虑上述约束的光路建立问题都属于支持约束的r w a ( c o n s t r a i n e dr w a ，c r w a ) 问题。c r w a 问题是指建立光路时考虑一定约束条件 的r w a 问题，它是一个涵盖范围很广的问题，比如传统文献中讨论的满足跳数、 链路分离等限制的r w a 问题都可纳入c r w a 范畴，甚至遵循波长连续性限制的 r w a 问题也看作是c r w a 问题的一种，此时其约束条件就是波长连续性要求。 将光路可能经过的所有网元或光器件( 如发射机、链路、节点以及接收机等) 的影响都加以考虑，以判断光路是否满足上层业务的q o s 要求。其主要思想就是 要根据上层业务的q o s 要求( 主要考虑传输质量要求) 选择满足信号质量的合适 路由和波长来建立光路。比如对于低速率的s d h 信号( 如s t m 1 6 ) 所要求的信 噪比就低于高速率的s d h 信号( 如s t m 6 4 ) ，这样建立光路时，前者所允许经过 的链路数就可以多于后者。 重庆邮电大学硕士论文第三章基于分层图的静态r w a 算法 第三章基于分层图的静态r w a 算法 静态r w a 问题即给定业务矩阵和网络拓扑，要求为每个业务建立光路。该问 题已被广泛研究，且已被证明是个n p c 问题。关于该问题的算法主要有：整数 线性规划( i l p ) 2 8 1 法、将该问题拆被分为路由选择和波长分配两个子问题【5 5 ，5 8 5 9 】 以及分层图的应用等。本章中，我们首先将分层图模型应用到单光纤w d m 光网络 的静态r w a 问题中，并提出了三种基于该模型的同时进行选路和波长分配的r w a 算法。而后，我们对这三种算法做了改进，使之适用于多光纤网络。 为证明算法的优越性，我们对所述算法在m a t l a b 环境下进行了仿真，通过 建立数学模型，构造仿真模块等步骤来实现对所述算法的论证。仿真分析表明， 基于分层图的静态r w a 算法能很好的解决r w a 问题，且能有效优化网络资源。 3 1单光纤w d m 网络中的r w a 问题 w d m 光网络是由网络节点和连接节点的光纤链路构成的，不同波长的光信道 复用在同一根光纤中传输。当客户层业务到达时，w d m 光网络需要给每条业务选 择路由和分配波长，建立光路传送业务。这就是w d m 网络的关键技术：路由与 波长分配( r 、凇) 问题。虽然w d m 光网络已经取得了巨大的进步，但由于各种 物理的、技术的限制因素，光网络还不能提供我们所要求的物理性能，因此就存 在对现有可用资源的高效利用和优化问题，r w a 问题是最优化网络性能的核心问 题之一。 w d m 网络中，为给定静态业务矩阵选路并分配波长，建立光路的r w a 问题叫 做静态r w a 问题。与动态r w a 问题不同，静态r w a 问题的主要优化目标是尽可能 的合理优化资源( 如波长、光纤等) ，以节省成本。由于光纤上的可用波长数目总 是有限的，所以，这里我们把算法的主要优化目标定位为最小化波长使用数目。 作为w d m 网络的核心问题，静态r w a 问题已被广泛研究，且已被证明是一个n p c 问题。整数线性规划( i l p ) 法是将网络中的各种因素考虑到算法内，针对某优化 目标，利用线性规划来求出最优解。该算法的优点是对问题考虑得比较详尽，但 算法复杂度较高，且随着网络规模急剧增大。部分研究将静态r w a 算法拆被分为 路由选择和波长分配两个子问题来分别加以解决。这种将r w a 问题拆分的方法比 较易于计算，且采用的路由选择算法和波长分配算法都能得到局部最优解。但这 种对r w a 问题的描述并不一定完全贴切，所以拆分后的局部最优解不等于全局最 重庆邮电大学硕士论文 第三章基于分层图的静态r w a 算法 优解。 为了避免以上算法的不足，本文中我们主要采用波长分层图模型来解决静态 r 、凇问题。波长分层图可以同时解决r w a 问题中的选路和波长分配问题，从而避 免了选路和波长分配的拆分。同时，为了有效节省波长资源，我们还将分层图模 型与最大边不相关理论【5 7 ，5 9 j 结合起来，共同解决静态r w a 问题。上述方法的结合 主要是为了有效地节省网络资源。这种二者结合的r w a 算法可兼具两者的优点： 既能同时进行选路和波长分配，又能有效优化网络资源。这里，我们提出了基于 波长分层图的三种算法：基于分层图的最短路径算法( l a y e r e d g r a p hb a s e ds h o r t e s t p a t h ，l g s p ) ，基于分层图的随机选取算法( l a y e r e d g r a p hr a n ds l e c t i o n ，l g r a n d ) 和基于分层图的长路优先算法( l a y e r e d g r a p hb a s e dl o n g e s ts h o r t e s t p a t hf i r s t ， l g l p f ) 。最后，通过仿真证明了基于波长分层图的r w a 算法的合理性和有效性。 3 1 1波长分层图模型 在w d m 光网络中，以g 似l w ，刀表示网络的物理拓扑，其中表示节点集； 三表示链路集；肜代表每条光纤可用的波长集：f 表示每条链路的光纤集。物理拓 扑图阐述了网络的物理连接状况，为了进一步明确网络的通道连接状况，我们又 构造出了w d m 光网络的逻辑拓扑图。即首先按下述方法构造物理拓扑图的逻辑 拓扑图g 仍习，其中，y 代表顶点集合，其顶点标号与中节点的标号保持一致， 是对图g 中节点集的复制，即v = n ；e 代表边集合，若g 中节点n 与m 之间存 在链路乙。l ，则g 中对应的顶点n 和肌之间存在有( i 形i i f i ) 条边。记各边的 标号为p n 加m ，其中f 1 ，2 ，吲) ，w 1 ，2 ，l 形l 。根据此定义，图3 1 ( a ) 所示的物 理拓扑对应的逻辑拓扑图可用图3 1 ( b ) 表示。 ( a ) ：6 ，1 w i = i f i = 2 的物理拓扑g ( b ) 逻辑拓扑图l g 图3 1 网络的逻辑拓扑示例图 分层图模型 5 7 , 5 9 1 是一个三维模型，其基本思想是将原始网络拓扑图g 似：职 习复制w 次，转换为波长图三g 五0 ，然后在这个三维波长图上来计算源节 点到目的节点之间的最短路径。分层图上的每一层对应一个波长，也称为波长平 面。光网络的分层图对业务的路由和波长选择是在不同的波长层面上完成的，即 重庆邮电大学硕士论文 第三章基于分层图的静态r w a 算法 在同一波长层面上完成了路由和波长的选择。当有波长变换器时，可通过分层图 中不同波长层面的相同节点间的链路相连来表示波长间的变换，并用波长转换的 权值来表示该链路的权值。这里，我们假设解决静态r w a 问题的波长分层图中不 含波长变换器。 网络的物理拓扑为g 形e 彬刀，v 表示节点集合，e 表示两条光纤形成的双向 链路集合。设单根光纤中共有矿个波长。则分层图模型的生成方法是： 将物理拓扑复制份，形成分层图中的形层。物理拓扑中的节点y ，就对应各个分 层图中的，w 夕，链路e ；就对应彩，彳，夕。并且原来的双向链路变成 方向相反的两条有向链路。y ，v ，乞e 这样，分层图l g ( v * ，e ) 的每一层都 代表一个波长，我们从上到下对每一层所对应的波长进行编号，依次为a ，旯旷。 如图1 ( a ) 所示的物理网络变成分层图就如图1 ( b ) 所示，其中w = 3 ，波长分层图 的每一层所对应的波长依次为a 。，a ，a ，。 v 4 ( a ) 物理拓扑( b ) 波长分层图模型 波长九l 层 波长地层 波长幻层 图3 。2 波长分层图模型 在波长分层图模型中，光路从源节点到目的节点必须要在同一个波长分层内， 即满足波长连续性限制。对于一个连接请求，在波长分层图上进行选路，它所经 过的路径，就是该光连接在物理拓扑上经过的路径，路径所在的波长分层，就是 它所占用的波长。如图l ( b ) 中，光连接( 1 ，j ，1 ，) 的路径是谚专谚一谚一谚，即 该请求在物理拓扑中的实际路径为 ，专，一v ，寸v 。，且该路径被分配的波长为 a ，。上面的例子充分证明，波长分层图模型可以同时解决w d m 网络中的选路和 波长分配问题。 3 1 2 算法描述 网络状态假设： 重庆邮电大学硕士论文 第三章基于分层图的静态r w a 算法 1 ) 假设网络中的物理层处于理想状态，光信号在传输过程中不存在损伤； 2 ) 网络的物理拓扑中各条链路包含单根光纤数、且波长数相等； 3 ) 假设网络中的光纤长度相等，这样就可以把路径距离简化为跳数； 4 ) 假设网络中的每个节点所到达的业务量相同，并且业务之间无差别； 5 ) 光路节点处( 输入输出) 能力不受限制，即节点处收发器的数目足够多，光 路建立请求的阻塞不会由节点引起； 6 ) 允许一对节点之间同时存在多条光路，一旦连接建立请求被拒绝，则立即 被丢弃，无等待队列； 7 ) 网络各个节点处无波长变换能力。由于采用波长变换器会增加设备成本， 且已有研究证明，波长变换器的应用对静态r w a 问题的解决帮助有限，完 全可以通过改善r w a 算法来达到其效果； 8 ) 建立新光路时，已经建立的光路连接不能被破坏； 问题描述： ， 1 1 网络中，壤示节点集合，e 表示两条光纤形成的双向链路集合。设单根光 纤中共有阶波长，每条链路上有f 根光纤，庐，。 2 ) 物理拓手b g w , e , 形刀所对应的分层图模型为l g ( v ，e 宰) ，y 表示节点集 合，e 掌表示链路( 单向) 集合。 3 ) 网络中的业务请求集合为d ，单个节点上的业务量为i a i ，则全网业务总量 为：i d n a i 吲。设集合中的某业务请求为口= 侮，珥) ，0 ，吃为路径只上的 中间节点。业务请求集合d 所对应的路径集合为尸。 5 ) 通路尸f 使用i j 链路中光纤则尺品为1 ，否则为o 。 6 ) 设办爿y 卜l ，通路p ，的长度为h ，则要求通路只的长度满足h i h ，其中， i 矿i 表示网络中节点的个数。 7 ) 如果业务口的路径只在波长分层图的彳棚层，则五朋= l ，否则为o 。 8 ) 设路径集合尸在波长分层图上所占的总层数为f ，则1 f w 。 数学模型： 目标： m i n i m i z e ：f 约束条件：f = m a x ( m ) ( 3 1 ) 这里： 。 r 蠹- i l l - ( 3 2 ) n 0 r 当- 1 w i ( 3 3 ) 重庆邮电大学硕士论文第三章基于分层图的静态r w a 算法 r 当- 1 ，则随机选取一条即可。若口在前a 。一层均不存在可用 路径，但第旯。层可以找到可用路径仍，则将业务口以路径b 分配在 兄。层上。更新g ，e 0 和d ，使f = f 一露，d = d 一口。若f 册， 贝j j f = m ，否则，腺持不变。 s t e p6 ：i fd ，贝0 返回s t e p5 。 s t e p7 ：i fd = 矽，则算法完毕，返回f ，即业务在网络中占用的波长数。 上述算法的基本思路主要是将图论知识应用到r w a 算法中，使各业务都尽可 能地使用分层图中比较靠上的波长层，从而减少波长使用数。三个算法中，l g s p 算法的主要特点是业务在分层图上分配波长时都采用最短路径，这样的好处是减 少传输时延，以及减少业务信号在传输过程中所受的物理损伤，但该算法所消耗 的波长数较大。l g r a n d 主要是从业务集合d 中随机选取业务，然后为所选取的 业务均在波长分层图上对其进行选路。l g l p f 算法的最大特点是对业务矩阵d 的 排序处理，将最短路径最长的业务排在前面处理，可以减小算法的难度，使算法 更加灵活。 3 1 3 仿真分析 为了对我们所提出的基于分层图模型的三中静态r w a 算法进行性能验证，本 小节我们将对上述算法在计算机上进行建模与仿真验证。在m a t l a b 7 1 环境下， 我们对基于分层图的静态r w a 算法进行建模分析，将之分解为：物理拓扑与波长 分层图建模分析、业务矩阵建模分析、选路建模分析、波长分配建模分析等模块。 通过对各模块的分析建立起整个基于分层图的静态r w a 分析系统，在系统上对我 们提出的三个算法进行仿真实现。 l 、计算机仿真与仿真环境 随着计算机技术和网络技术的飞速发展计算机仿真技术得到了广泛应用计 算机仿真是分析和研究系统运行行为、揭示系统动态过程和运动规律的一种重要 重庆邮电大学硕士论文 第三章基于分层图的静态r w a 算法 手段和方法，是系统仿真就是建立系统的模型，并在模型上进行实验的过程。系 统仿真技术实质上就是建立仿真模型并进行仿真实验的技术。因此，通俗的说， 计算机仿真就是指在实体尚不存在、或者不易在实体上进行实验的情况下，对考 察对象进行建模然后通过计算机编程考察对象在系统参数以及内外环境条件改 变的情况。达到全面了解和掌握考察对象特性的目的。 一般计算机仿真的步骤扣o j 为： ( 1 ) 建立数据模型。建立数据模型主要是通过演绎法、归纳法、综合集成法等 分析方法，建立一个特定对象的有限边界的数学模型。 ( 2 ) 数学模型的实现。也称为数据模型的程序化。数学模型的实现包括两个方 面的内容：即设计仿真算法及编制仿真程序。 ( 3 ) 仿真实验。仿真实验是系统仿真另一个十分重要的活动，它主要是按照预 先设置的实验方案来运行仿真模型，得到一系列的仿真结果。 由于m a t l a b 强大的矩阵处理能力，这里我们选择m a t l a b7 1 作为我们的 仿真验证平台。“m a t l a b ”代表m a t r i xl a b o r a t o r y ( 矩阵实验室) 。m a t l a b 语言 的显著特点【6 1 】是：1 、具有强大的矩阵运算能力，使得矩阵运算非常简单。2 、是 一种演算式语言：m a t l a b 的基本数据单元是既不需要指定维数，也不需要说明 数据类型的矩阵( 向量和标量为矩阵的特例) ，而且数学表达式和运算规则与通常 的习惯相同。 2 、基于分层图的静态r w a 问题仿真分析系统 静态r w a 问题的定义：给定业务矩阵和网络物理拓扑，要求为每个业务进行 选路计算，并对所选路径进行波长分配，以建立光路来传送该业务。并且业务的 r w a 计算服从波长连续性的限制。根据定义，我们可以将整个r w a 问题拆分为 如下的功能模块，并分别进行建模。 系统仿真就是建立系统的模型，并在模型上进行实验的过程。基于分层图的 静态r w a 问题仿真模型可以拆分为以下模块：1 、分层图生成模块；2 、静态业务 生成模块：3 、选路与波长分配模块；首先通过在m a t l a b 中建立这些子模块， 然后组合起来构成模基于分层图的静态r w a 问题分析模型，最后在该模型基础上 对l g s p 算法进行仿真验证。 网络拓扑与分层图的建模： 网络g = 以目由两个非空有穷集合组成：节点集合y 和链路集合e 。m a t l a b 环境中，若拓扑g = 仍习中有个节点，则它可以被抽象为二维n x n 方阵g 。矩 阵的行f 和列，分别对应网络的节点f 和节点j ，c o , j ) 表示节点f 与节点_ ，之间的链 接状况。图l ( a ) 表示6 个节点7 条光纤链路的网络拓扑，该拓扑可以被表示为图 l ( b ) 的矩阵。 重庆邮电大学硕士论文第三章基于分层图的静态r w a 算法 2 图3 1 ( a ) 网络拓扑示例图3 1 ( b ) 网络拓扑的矩阵表示 图3 2 路径图 矩阵中g ；，= 0 时，表示网络拓扑中节点f 、，之间不相连。当瓯= 1 表示i ， 之间相连。这里，也可以使g ，1 表示节点厶，之间存在的光纤或波长数。 波长分层图由物理拓扑图构建而成，因此，在m a t l a b 中，我们可以通过对 物理拓扑所对应的矩阵的扩充来建立分层图模型。若物理拓扑g = 形习中的波长 数为彤矩阵为g 。则其对应的分层图可以表示为n x n x w 的三维矩阵l g ，其中： 行列矩阵代表网络的物理拓扑，形页矩阵代表按形个波长数对物理拓扑进行 的扩充。在矩阵l g 中，要求l g ( = = ，l 产砸：，2 户= l g c ，邺? 以网络拓扑图l 为例，设网络中有两个波长，则相应的分层图模型可以表示为6 x 6 x 2 的矩阵三g ， 且l g ( ：，：，1 产l g c ，：，2 即。 静态业务集合d 的生成： 假设网络中业务分布均匀，每个节点上到达的业务均为肘个，则总的业务个 数为：n x m 业务矩阵d 可以构造为一个n x m 行2 列的矩阵。首先构造一个n x m 的二维过渡矩阵s ，其中，行代表网络的个节点，m 代表单节点上的业务量。 对于节点i ，业务从i 节点到其它节点的概率均等，即服从均匀分布。可以用 r a n d p e r m ( n ) 命令生成服从均匀分布的数组r ，然后随机从r 中选取一个元素r ( r ) ， 令眠j 脉纠，则s ( f ，矽表示为业务i 生成的一个目的节点。利用上述方法为每个 节点生成个目的节点后，矩阵s 构造完毕。设口为第i 次生成的业务矩阵，口 为行2 列二维方阵，且对于i _ l ：l l ，d 化1 ) = f ，d ( ：，2 ) = s c ，f ) 。网络总的业务 矩阵为：d = 【q ；0 2 ；d ，】以图1 中的拓扑为例，设网络的每个节点上业务个 数胪2 ，则可以构建业务矩阵d 为： 茎|，d-=耋i，岛=f萎i 一：，= 4 33 4 ：! ：；：矧 广17 值得注意的是，过渡矩阵s 中的值是随机生成的，且s 以f ，即业务的源 节点和目的节点不能相同。 业务选择模块的建立： 首先判断是否有d = 矽，若不存在，则对于生成的业务请求矩阵为d ，每次都 随机选取d 中的某一行d 亿。令墨= d f j l 矽，4 = d 似2 。 l o l o l o o l o l o l o ooo o l o l o l l o l o l o o ，o 0 o l 重庆邮电大学硕士论文 第三章基于分层图的静态r w a 算法 业务选路问题的建模分析： 设需要为业务口= ( s i ，d ，) 进行选路。选路之前，首先检查网络的连接状况， 根据网络当前的连接状态，刷新网络拓扑矩阵g 。然后，以逐跳累计的原则按下 列步骤构造出该业务的路由矩阵尺，首先初始化r 为： 路由首先从源节点l 出发，查看网络拓扑矩阵g 中的第s ，行向量g 囟，。 若对于1 j n ，存在g 佤， 0 ，则表示源节点墨与点相连，可以将_ 节点纳入 路由矩阵r 。若，节点的个数为n l ，则将矩阵r 扩充为n 2 的二维矩阵，矩阵中元 素的值为：r 阮j j ：f ，r ( k ，2 ) = t ，1 七拧；此时，为业务增加了一跳路由。 路径每增加一跳，都要对路由矩阵r 的行向量进行回路检测：若某行向量 中存在两个元素相同的情况，则表示路径产生了回路，删除该行向量；否则保持足 不变。 路径每增加一跳，都要对路由矩阵r 进行目的节点检测：对路径新到达的 节点进行目的节点检测。若此时路由矩阵r 为p 行m 列，若对于1 k e ，存在 n ( k ，所) ：西，则说明路径经过m j 跳后到达目的节点，假设源到目的节点的m j 路由矩阵为r ”1 ，则尺”1 由所有矩阵r 中r ( k ，m ) = d ，所在的行向量组成。对路 径矩阵进行更新，即从r 删除r ( k ，m ) = d i 所在的行向量。 设路径增加了弘j 跳，则此时路由矩阵r 共有x 列；令c = s i z e o f ( r , 1 ) ，则c 为路由矩阵的行数。设l j c ，为节点r ( j ，x ) 寻找下一跳，检查g 中第尺( ，工) 行 的向量。若对于1 v n ，存在g 俾( ，x ) ，1 ；) 0 ，则将y 节点纳入矩阵r 。若存在m 1 个满足条件的节点1 ，则将矩阵r 的第，行扩充为m 行、x + l 列的新矩阵母，该矩 阵前x 列的值保持不变，对于1 f m ，令尺煎，x + 1 ) = v ，将原业务矩阵r 的第， 行删除；若肌：0 ，则r j ；矽，r 保持不变。为向量r ( ：，工) 的每一个值所代表的中间 节点寻找下一跳路由，则可以构造出m 个新路由矩阵r t ，尺：凡。，令路由矩阵 r = 【r ：r 一：r ：。：凡】，则r 为增加了一跳的路由矩阵。 令l - ，l i 蠲f l 1 w l ，1 j n 。 ， 。 3 7 重庆邮电大学硕士论文 第三章基于分层图的静态r w a 算法 2 ) 在第f 行，若原始顶点，与k 之间有边相连，并且波长f 是可用的，则咐 与v 瞳之间用一条边相连。构造好的分层图共有ifi 1 w i 层，其中if1 个光纤分层， i w l 个波长分层。 与单光纤网络不同的是，多光纤网络的分层图模型有两种形式：光纤一波长 、分层图模型与波长一光纤分层图模型。光纤一波长分层图模型是首先按照网络中 的光纤数分为if1 个光纤层，然后按照单根光纤的波长数将每个光纤层分为l w l 个 波长分层。波长一光纤分层图模型则是首先按照网络中的波长数分为1 w 1 个波长分 层，然后按照光纤数将每个波长层分为if1 个光纤分层。然