环形全光WDM网络的波长分配

我们考虑的问题来自于基于波分复用技术(WDM)的全光环形网络．给定环形网络中一个路(通讯请求)的集合，将每一条路分配一个波长，使得经过相同连接的路必须分配不同的波长我们的目标就是找一个波长分配方案使所需的波长数目最小．令ω表示为路集中最大两两相交路的个数．本文我们设计了一个可以保证指派到路集的波长数目不超过1．5ω的近似算法．因为ω是路集所需波长最小数目的一个下界，所以该算法的近似比不超过1．5．

WAVELENGTH ASSIGNMENT IN ALL-OPTICAL WDM NETWORKS WITH RING TOPOLOGY

The problem we consider arises in an all-optical communications network with wavelength division multiplexing (WDM) configured as a ring. Given a set of paths (requests) over a ring, wavelengths must be assigned to the corresponding paths such that paths that use the same link are assigned different wavelengths. The goal is to minimize the number of required wavelengths. In this article, we design an approximation algorithm that assure the number of wavelengths assigned into the set of paths is no more than 1.5w, where w is the cardinality of the maximum set of pairwise intersecting paths. Since w is a lower bound of the minimum possible number of wavelengths for the set of paths, the algorithm guarantees that the performance ratio is no more than 1.5.