SONET/WDM(Synchronous Optical NETwork/Wavelength Division Multiplexing的简称)环网络中业务流量的疏导是光网络研究领域的一个重要的前沿和热点问题，也是一个科技含量和商业价值并重的较新的研究课题。业务流量的高效疏导能有效地降低网络的建造成本和费用，因而自从它在1998年被提出后就引起了国际上众多著名研究机构和工商领域的研究人员的广泛关注。由于这一问题的NP-难的特性，目前对它的研究还主要集中在环形网中，通过设计出各种启发性算法进行求解。 本文对单向和双向SONET／WDM环网络中的静态和动态流量疏导问题进行了系统的研究，将这一问题表示成一组严格的数学规划方程，并提出了遗传算法和禁忌搜索算法来求解这一问题。本文的主要贡献是：1)用一组多目标整数非线性规划方程对SONET／WDM环网络中静态与动态流量疏导问题进行了统一的严格的数学描述；2)对动态业务疏导问题按阻塞特性进行了详细的分类；3)提出了遗传算法和禁忌搜索算法及其与局部启发性算法相结合的方法对环网络中各类业务疏导问题进行求解，在计算机中实现了这些算法，给出了疏导结果并进行了较为详细的讨论。本文较次要的贡献为：1)在遗传算法中提出了顺序映射杂交算符及自适应染色体的概念；2)得出了环网络中较紧凑的ADM数和波长数的理论上、下限；3)提出了一些用于判断静态和动态疏导结果的参数。 本文的主要内容如下。 在流量疏导的研究中，如何在数学上对其进行描述是一个重要的问题。本文中我们首次将SONET／WDM环网络中的流量疏导问题用一组多目标整数非线性规划方程进行了统一的描述。这组方程对环中的流量疏导问题具有普遍的意义，它既可以优化网络中的ADM数，也可以优化波长数，还可以对它们进行混合优化；既适用于业务量有分叉时的情况，也适用于没有分叉时的疏导；既可用于单向环，也可用于双向环；既适用于各业务的路径固定的情况，也适用于各业务的路径与目标函数同时优化的情况。并且这组方程中对网络中的业务需求没有任何附加的要求。当环中只有一组业务需求时，这一方程组可用于描述静态流量疏导问题，若环中具有多组业务需求，它又适用于动态流量的疏导，并可用于描述不同阻塞特性的疏导。我们还证明了，当环中各业务请求具有固定路径时，这组方程可简化为多目标整数线性规划方程。总之，这一方程组的得出有助于环网络中流量疏导问题的规范化表述。11 徐永：SONET／WDM光环网中业务流量的智能疏导 在研究动态流量的疏导问题时，我们首次对动态流量疏导按阻塞特性进行了详细的分类。分析表明，在不考虑业务分叉且网络中为全请求连接的情况下，只存在严格无阻塞和可重构无阻塞两种疏导方式，而不存在广义无阻塞疏导方式，并且在严格无阻塞疏导中，不同时刻的业务需求中相同节点间的业务请求必须被分配到相同的放长中，但在可重构无阻塞疏导中，不同时刻的业务需求中相同节点间的业务请求则可以被分配到不同的波长中。我们还证明了在某种部分请求连接的情况下，或者在疏导过程中引入业务量的分叉，则存在着广义无阻塞疏导类型。这一分类方式有助于对不同的阻塞类型设计不同的疏导算忠 本文还就静态和动态情况分别推导了环中波长数的理论上下限，并为ADM数推导了两个上下限，得出了较紧凑的理论上下限。计算机模拟结果表明，我们所得出理论下限在某些情况下就是所求问题的下确界。 为了对静态和动态疏导问题进行求解，我们设计了适合于这类问题的独特的遗传算法和禁忌搜索算法，我们还设计了高效的局部启发性算法对每个个体进行解码，使整个群体在不断迭代的过程中进化到全局最优。对于禁忌搜索算法我们设计了独特的邻域结构，以减少邻域数量并在每次移动时都使邻域较当前解有所改善。与传统的启发性算法相比，遗传算法和禁忌搜索算法具有较强的通用性并能获得更好的优化解。对于可重构无阻塞疏导问题，我们提出了混合遗传算法并专门设计了二萝染色体结构。在初步解码后，我们对每个个体分三步进行调整和优化，以便获得最佳的优化效果。此外，对十动态业务疏导问题，本文所设计的算法可以在一次运行时对环中的M套业务需求进行一次性优化，从而避免了由十分步优化使最终结果依赖十各次运行的结果并导致运行时问的增加。 为了证实上述算沧的有效性，我们对单。双向环中的静、动怂疏导问题均给出了详细的0算机模拟结果，并对模拟结果中所出现的各种恬况进行了详细的比较和讨论，同时还分析了动态疏导的优越性。结果表明，本文所设训的算法取得了很好的忧化效果，在某些情况下达到了所求问题的理论下限。 最后，我们定义了用十评估静态和动态业务流量疏导结果的若十参数，这些参数对于评价疏导结果，选择不问的疏导方式，以便最大限度地利用每一波长所提供的容量，都有一定的指导意义。