0 引言

互联网的快速发展使得网络业务的种类和数量持续快速地增长，对基础承载光网络的带宽供给能力提出了更高的要求。传统的波分复用（WDM）光网络以固定栅格波长作为最小颗粒度进行业务带宽分配，在动态复杂且多样性的业务环境下，难以适应不同颗粒度的业务请求，导致其频谱利用率较低和网络灵活度差。在此背景下，弹性光网络（EON）应运而生，被认为是下一代光网络的主要发展方向之一[1]。

由于频谱的动态分配和释放会导致频谱碎片化，影响后续服务的分配和网络的频谱资源利用率。因此，路由和频谱分配（RSA）[2]成为EON中的关键问题。

图论是数学中重要的一个分支，通信网络中的选路、资源分配、生存性等问题都可以转换为图论中的上色问题来加以解决[3]。图论中上色问题的目标是使用最少的颜色完成对图的着色，这与EON中频谱分配使用最小资源的目的是一致的。近年来，一些研究者开始尝试用图论方法来解决频谱分配问题。文献[4-5]提出了在认知无线电频谱分配中引入图着色模型，并证明了图论方法具有更好的鲁棒性。文献[6]对颜色敏感的图论着色算法进行了优化，提高了算法的频谱利用率。FADINI W等人[7]提出了一种基于频谱着色分类的思路，形成了图着色模型。上述文献虽然针对图论在频谱分配中的应用开展了不少研究，但是仍存在许多尚待解决的问题，比如如何选取适宜的着色算法和在算法中设置合适的指标来提升网络的性能等。本文基于EON的图着色模型提出2种RSA改进的着色算法，有效降低网络的频谱碎片程度和阻塞率。

4 结束语

　　本文针对EON中的频谱分配问题，基于图论建立了一种图着色模型，并提出2种改进的着色算法，即链式搜索法和改进的贪心算法，完成了对图着色模型的上色（完成了频谱分配的任务）。仿真结果表明：基于图着色模型的2种改进算法比传统度最大着色算法的频谱利用率更好、阻塞率更低。其中，改进的贪心算法性能稍逊但是更加简单，运行较快。