弹性光网络中基于图着色理论的资源分配算法

Resource allocation algorithm based on graph coloring theory in elastic optical network

传统的波分复用网络采用固定栅格,已无法满足网络需求。提出一种改进的基于图着色理论的路由选择频谱分配(GT-RSA)算法。首先,使用前k条最短路径算法确定备选路由集合,根据各备选路由集合建立备选路由关系图;然后,使用图着色理论的混合整数线性规划模型进行选路,根据分支定界的饱和度最大优先算法得到优解,同时完成频谱的路由着色分区分配;最后,采用分区前后适配(PAR-FLF)算法对业务完成频谱资源的分配。仿真结果表明:GT-RSA算法具有更低的频谱资源消耗、阻塞率以及更高的平均链路连续率。

The traditional WDM network uses fixed grid,which can not meet the network requirements.An improved graph coloring based routing spectrum allocation(GT-RSA)algorithm is proposed.Firstly,the first k shortest path algorithm is used to determine the candidate route set,and the candidate route graph is established according to each candidate route set.Then,the mixed integer linear programming model of graph coloring theory is used to select the route,and the optimal solution is obtained according to the maximum saturation priority algorithm of branch boundary.At the same time,the coloring partition allocation of spectrum is completed.Finally,partition first-last-fit(PAR-FLF)algorithm is used to allocate spectrum resources.The simulation results show that GT-RSA algorithm has lower spectrum resource consumption,lower blocking rate and higher average link continuity rate.