基于图着色的光网络路由与波长分配问题研究

Wavelength Division Multiplexing (WDM) Optical networks are well suited to fulfill the ever-increasing demand of bandwidth. Developing efficient algorithms of routing and wavelength assignment is crucial to the design optimization and resource utilization in large-scale optical networks. This project intends to return to the essence of the routing and wavelength assignment problem in optical networks and translates this problem into the partition coloring problem of graphs. For this, we conduct our research mainly from three aspects, including the construction of the evaluation system for vertex selection, the design of solutions to the coloring problem, and the realization and application of the coloring algorithms. First, we analyze the connection between the structures of graphs and the properties of partition coloring. Based on the graph theories such as connectivity, covering, contracting and expending of graphs, independent set and integer flows, etc., we figure out the key parameters of vertex selection. By this, we design an evaluation system for vertex selection by leveraging the theories of function, matrix, probability, deep learning and data mining, etc. Then, we develop efficient algorithms to deal with the partition coloring problem for large-scale networks on the basis of three approaches including static coloring, dynamic coloring and their combination respectively, by employing the optimization strategies of local search, dynamic programming and pruning, etc. Finally, we apply the designed algorithms to the routing and wavelength assignment problem for large-scale real optical networks and carry out the experimental analysis. This research is hoped to be helpful in optimizing the resource utilization of optical networks, and consequently improve the communication efficiency of optical networks.

波分复用技术为满足人们日益增涨的网络带宽需求提供了一种有效途径。面向大规模光网络的路由与波长分配算法对于网络优化设计及网络资源利用至关重要。本项目拟回归问题的本质，基于图的划分着色理论来研究光网络的路由与波长分配问题。主要从顶点选取的评估体系构建、着色方案设计以及着色算法的应用与实现等三个方面展开。首先，通过探讨着色与图的结构之间的关系，基于图的连通性、覆盖、图的收缩与扩展、独立集和网络流等理论，分析影响顶点选取的关键参数，从而利用函数、矩阵、概率与数理统计等理论和深度学习、数据挖掘等技术，设计出一套顶点选取的评估体系。其次，分别基于静态、动态和动静结合的思想，利用局部搜索、动态规划、剪枝等优化策略，设计可用于求解大型网络划分着色问题的高效算法。最后，将所提算法应用于大规模光网络的路由与波长分配问题中。该研究有助于实现光网络资源的优化利用以及光网络通信效率的提高。

项目在波分复用光网络的路由与波长分配问题的背景下，围绕图的划分着色问题展开了一系列的研究，主要内容包括三个方面：顶点影响力刻画、着色方案设计以及算法实现与实验测试。首先，为了刻画顶点的影响力，在理论上研究了图的控制集和度量维度，解决了这方面的六个国际公开问题；在算法上研究了图的控制集问题，独立集问题和影响最大化问题，分别给出了求解这些问题的高效非精确算法，并进行了实验验证。特别地，提出了划分独立集的概念，并研究了它的计算复杂性，给出了刻画顶点影响力的启发式策略。其次，为了设计高效精准的图着色算法，理论上研究了多种着色问题，包括图的全色数、星边着色、邻点积可区别全色数、Smarandachely邻点可区别全色数，并给出一种求解3-着色计数问题的精确算法，改进了近十五年的一个最好算法。最后，在上述研究的基础上，提出了一种可求解大图的启发式划分着色算法HotPGC。所提算法主要包含两个关键技术：图的划分独立集和l-CDBOS图缩减规则，其中划分独立集可用来生成高质量的初始解，而l-CDBOS可用来对大图进行递归缩减，然后通过反复扩展小图的划分着色来得到原图的划分着色，这为在大图上高效求解划分着色提供了一种可行的方案。通过在标准集和现实实例上进行实验，与目前最好的算法相比，HotPGC可以得到更有竞争力的结果。尽管目前的研究成果还处于理论研究阶段，但是所提出了方法体系和算法框架，在一定程度上推进了相关领域基础理论的发展。基于上述研究成果，在国内外重要学术期刊共发表学术论文21篇（SCI收录17篇），申请发明专利3项（授权1项）。