I I′. Begin.pdf

1000-9825/2002/13(08)1456-09 ©2002 Journal of Software 软 件 学 报 Vol.13, No.8 有固定波长转换器的全光环网波长分配算法 1,2 1,2 1,2 3 万颖瑜 , 陈国良 , 许胤龙 , 顾 钧 1( 中国科学技术大学 计算机科学与技术系,安徽 合肥 230027); 2( 国家高性能计算中心(合肥),安徽 合肥 230027); 3(香港科技大学 计算机科学系,香港) E-mail: yywan@ 摘要: 采用波分复用技术的全光网是目前宽带网络研究的方向之一,波长分配是其中主要的算法问题,具有重 要的理论和应用价值.研究了具有任意固定波长转换器的环形光网上的波长分配问题.首先,提出了两个对环网 上的请求集合预处理的算法,这两个算法可以将请求集合分解成一些连续的循环序列;然后,采用置换群来描述 具有固定波长转换器的光环网,基于这种数学表示,提出了对环网上的波长信道进行分解的算法;基于这些算法, 进一步提出了一个波长分配算法,该算法对于环形光网上的任意固定转换模式都能给出一个较好的波长分配 方案. 关 键 词: 全光网;波分复用;波长分配; 固定转换;置换群 中图法分类号: TP393 文献标识码: A 全光网是一种新兴的光纤通信网技术,在这种网络中,数据由源节点到目的节点的传输和交换过程都在光 域内进行, 中间不存在任何光电之间的转换,从而避免了由电子器件产生的“ 电子瓶颈”现象.全光网具有高带 宽、信号透明、兼容性好、可扩放、可重构、结构简单、可靠性高等优点,从而成为宽带通信网发展的方向. 为了充分利用全光网中的高带宽,通常都采用某种多址复用技术, 目前在全光网中应用最广泛最成熟的技术就 是波分复用(wavelength division multiplex,简称WDM).这种技术的基本原理是:在发送端将多个不同波长的信 号复用到一根光纤上传输,在接收端再将复用的信号按波长分开并送入不同的终端.这样就将一根物理链路分 成了多个通信信道,从而将光纤的传输容量扩大了几倍、几十甚至上百倍.尽管现在基于波分复用技术的全光 网还没有达到完全实用化,但是关于这方面的研究已经成为当前网络研究的一个主要方向. 采用波分复用技术的全光网中存在多个不同波长的通信信道, 由于受到目前技术的限制,一根光纤中可以 容纳的波长数是有限的,所以波长就成为光网中的一种重要的资源.如何充分利用已有的波长是全光网研究中 的一个重要问题.给定网络中的通信请求,如何给每个请求分配波长以实现通信, 同时保证不同的请求在同一条 边上分配不同的波长,并使所用的总波长数尽可能少,该问题称为波长分配问题.为了提高波长的利用率,通常 在交换节点上增加波长转换的能力, 即交换节点能够将一种波长的信号通过波长转换器转换成另一种波长的 信号.波长转换器的转换能力越强,波长的利用率也会越高. 已经有研究表明, 当交换节点上波长之间可以任意 转换时,波长的利用率最高[1] .但是,转换能力越强,技术上实现的难度就越大,而且成本也越高,所以目前研究的 都是有限转换能力情况下的波长分配问题.文献[2~8]研究了交换节点没有转换能力时各种网络拓扑结构上的 收稿日期: 2001-09-01; 修改日期: 2002-02-04 基金项目: 国家自然科学基金资助项目; 国家重点基础研究发展规划973 资助项目(G 1998030403) 作者简介: 万颖瑜(1976 －), 男,江西南昌人,博士生,主要研究领域为算法设计,组合优化,并行分布式计算;陈国良(1938 －), 男, 安徽颍上人,教授,博士生导师,主要研究领域为并行算法,并行机体系结构,格点计算;许胤龙(1963 －), 男,安徽庐江人,副教授,主要研 究领域为复杂性理论,算法设计,并行计算;顾钧(1956 －),男,江苏盐城人,教授,博士生导师,主要研究领域为复杂性理论,算法设计. 万颖瑜 等:有固定波长转换器的全光环网波长分配算法 1457 波长分配问题.其中对于环形网络,文献[5]证明了,当网络负载为L 时,2L−1种波长是充分且必要的.文献[5,9~12] 研究了交换节点上具有波长转换能力时的波长分配问题,其中文献[9]针对环形网络设计了几种固定和有限波 长转换器,并给出了相应的分配