1 引言

随着网络技术和业务需求的快速发展,大容量、高利用率、低阻塞率的弹性全光网络的相关技术成为未来的发展趋势。然而,同时利用正交频分复用的子载波多路复用技术和灵活可变的频谱分配,使得弹性光网络架构的选路及频谱分配问题较传统网络变得更为复杂^[1-3]。多纤芯弹性光网络可以有效地增加网络的容量,提高网络的性能,但如何进行高效的纤芯分配也成了巨大挑战。

目前已有很多文献研究了弹性光网络中的选路和频隙分配问题的解决策略及算法,如文献[ 4]提出的选路基于K最短路径、频谱分配采用首次命中策略的启发式算法,文献[ 5]提出的请求频隙最多的业务优先的算法和文献[ 6]提出的最长路径的业务优先的算法。这些算法以最小化资源消耗为优化目标,但是频谱利用率并不是很高,并且不能保证较低的业务阻塞率。文献[ 7-9]研究静态选路和频谱问题,建立了一个整数线性优化模型,并基于自适应频谱分配和冲突避免的算法、基于禁忌捜索的算法和基于分支定界的求解算法高效地求解所建模型。考虑到弹性光网络的维护周期,文献[ 10]研究了线下和线上选路问题与频谱分配的问题,首先构建了基于路径和结点的整数线性规划模型,然后利用列生成和启发式算法解决线下选路与频谱分配问题,最后提出两种启发式算法以解决在线选路与频谱分配问题。考虑到网络中能量的消耗,文献[ 11]研究了静态业务选路、调制格式选择以及频谱分配问题,并通过线性化高斯模型提出了最优解的显示表达式和具有较低复杂度的选路、调制格式选择以及频谱分配方案。为求解文献[ 11]建立的整数线性规划模型,文献[ 12]设计了距离自适应的双种群协同算法以确定最优的选路、频谱分配方案。文献[ 13]考虑到频谱分配方案会在光纤上产生频谱碎片,提出了一种频谱碎片化和对齐性感知算法,可以有效地降低光纤上频谱碎化的程度。

多纤芯弹性光网络的研究相对较少,文献[ 14]考虑了调制格式对频谱资源的影响,研究了多纤芯弹性光网络中选路、纤芯分配、调制格式选择及频谱分配问题,提出了基于距离自适应的调制格式选择策略。为解决资源有限的多纤芯弹性光网络中最小化业务的阻塞率问题,文献[ 15]提出了一种启发式纤芯分配算法;文献[ 16]提出了一种频谱分配策略以减少不同纤芯上业务的串扰值;文献[ 17]将纤芯分配问题分为白盒和黑盒问题,针对不同的问题进行研究得到了不同的纤芯分配方案;文献[ 18]研究了未考虑纤芯之间串扰情况下的多纤芯弹性网络中的选路和纤芯分配问题,并设计了一种基于纤芯轮换选择的启发式策略以最小化网络中的最大占用频隙号;文献[ 19]研究了多纤芯弹性光网络中选路、纤芯分配问题且考虑了纤芯之间的串扰值,基于遗传算法的求解算法设计了一个较好的纤芯分配方案。

本文研究了资源有限的多纤芯弹性光网络中的选路及纤芯分配问题,以最小化阻塞业务请求占用的频隙数最少为优化目标,建立了全局约束优化模型。模型中考虑到业务所占用的纤芯可交换,故提高了网络的性能,同时也增加了问题的难度。为求解所建立的模型,设计了具有局部搜索算子的遗传算子,以得到最优的选路和纤芯分配方案。

2 全局约束优化模型

2.1 网络描述

多纤芯弹性光网络是一条光纤中包含多个纤芯的弹性光网络,可以有效地增加网络的容量,降低网络中业务的阻塞率,提高网络的性能。如图1所示,每个光纤中有若干个纤芯且这几个纤芯均能够独立地进行信息传输(fiber是光纤,core是光纤中的纤芯)。不同纤芯之间存在串扰,影响信息的传输,已有相关文献对降低纤芯间串扰进行了研究^[19-21]。本文研究的是纤芯可交换的弹性光网络中的选路、选纤芯以及频谱分配问题,如图2所示,在多纤芯弹性光网络的结点中,每个结点中若干个纤芯之间通过硬件互连^[17],能够实现纤芯与纤芯的交换,即业务在不同链路上占用的纤芯号可以不同(in是输入端,out是输出端,add ports是上业务端口,drop ports是下业务端口)。用无向图G=(V,E)表示网络拓扑,V={v₁,v₂,…,v_NV}表示结点的集合,其中v_i是第i个结点,N_V是网络中结点的个数。E={l_ij|v_i,v_j∈V}表示网络中链路的集合,l_ij是连通结点v_i和v_j之间的链路。N_E表示网络中链路的数目,每条链路上有N_C个纤芯,则链路l_ij中的纤芯集合表示为l_ij={ lij1, lij2,…, lijc,…, lijNC},c是纤芯的索引值,c=1,2,…,N_C即第c个纤芯。每个纤芯上有N_F个频隙,编号为1,2,…,N_F。

图 1. 多纤芯光纤结构图

Fig. 1. Architecture of fiber with multi-cores

下载图片 查看所有图片

图 2. 网络结点示意图

Fig. 2. Architecture of network node

下载图片 查看所有图片

2.2 业务及问题描述

R={r₁,r₂,…,r_k,…,r_NR}是业务的集合,r_k是业务的集合R中第k个业务,N_R是业务数。从源结点传递到目的业务r_k,可以用一个三元组表示,即r_k={s_k,d_k,T_k},其中s_k,d_k和T_k分别是业务r_k的源结点、目的结点以及需要占用的频隙数。由于网络中的频隙资源是有限的,当业务的数目较多时,可能无法为某些业务服务,即一些业务被阻塞,因此就要为业务选择合适的路径和分配较优的纤芯以使得被阻塞的业务所需要占用的频隙数最少。

2.3 问题建模

多纤芯弹性光网络中选路及纤芯分配问题的求解思路是:网络中的频隙资源有限时设计合适的选路以及纤芯分配方案,使得被阻塞的业务所需要占用的频隙数最少。因此,目标函数可以表示为

minρ=min∑k=1NRλkTk∑k=1NRTk,(1)

式中:λ_k为布尔变量,当且仅当业务r_k被阻塞时有λ_k=1,否则λ_k=0。

在业务选路、纤芯分配以及频隙分配时需要满足一些约束条件。

1) 约束条件a:业务r_k(∀r_k∈R),仅能占用其候选路径集中的一条路径,即

∑q=1Kφkq=1,∀rk∈R,(2)

式中:业务r_k占用其候选路径集Q_k= Qk1,Qk2,…,Qkq,…,Qk(Nk)中的路径 Qkq时有 φkq=1,否则 φkq=0; Qkq为候选路径集Q_k中的第q条路径;K为业务r_k的候选路径集Q_k中路径的个数;R为业务请求的集合。

2) 约束条件b:业务r_k(∀r_k∈R)在其所占路径的每条链路上所占用的纤芯号必须小于链路上所拥有的纤芯数,则有

1≤ck(ql)≤NC,∀rk∈R,1≤q≤Nk,1≤l≤Lkq,(3)

式中: ck(ql)为业务r_k在路径 Qkq上的第l个链路上所占用的纤芯号; Lkq为路径 Qkq中链路的条数;R为业务请求的集合。

3) 约束条件c:业务r_k(∀r_k∈R)在其所占纤芯上占用频隙的编号不超过该纤芯上所拥有的频隙数,即

fkI+Tk+Gf-1≤NF,∀rk∈R,(4)

式中: fkI为业务r_k在其所占纤芯上占用的频隙的起始频隙号;G_f为保护频隙数。

4) 约束条件d:对于占用公共纤芯的两个业务r_k和r_k',且业务r_k占用频隙的起始频隙号小于业务r_k'(记为r_k<r_k'),则有

fkI+Tk+Gf-1≤fk'I,∀rk<rk'。(5)

5) 约束条件e:频隙分配时,业务所在链路上不同纤芯之间的串扰不能大于某一阈值,即有

∑lij∈Q(q)kμij≤σ,∀rk∈R,(6)

式中:μ_ij为业务r_k'在链路l_ij上的串扰值;σ为串扰的阈值(即大于该阈值时目的结点可能会错误解码)。

根据给出的目标函数和约束条件,以最小化被阻塞的业务所需要占用的频隙数为目标建立全局约束优化模型,模型如下:

minρ=min∑k=1NRλkTk∑k=1NRTks.t.∑q=1Kφkq=1,∀rk∈R1≤ck(ql)≤NC,∀rk∈R,1≤q≤Nk,1≤l≤LkqfkI+Tk+Gf-1≤NF,∀rk∈RfkI+Tk+Gf-1≤fk'I,∀rk<rk'∑lij∈Q(q)kμij≤σ,∀rk∈R。(7)

3 选路及纤芯分配算法

多纤芯弹性光网络中的选路、纤芯分配问题是典型的组合优化问题,如何高效地求解所建立的全局约束优化模型并得到最优的选路以及纤芯分配方案是关键。遗传算法能够模拟生物进化过程,通过个体朝着较优的方向进化得到问题的最优解,更适用于组合优化问题。因此,提出一种新的全局优化遗传算法来求解建立的全局组合优化模型以得到最优的选路、纤芯分配方案。

3.1 编码

多纤芯弹性光网络中为业务服务需要解决选路、纤芯分配以及频隙分配3个问题。采用首次适应策略给业务分配频隙,因此只需对选路和纤芯分配进行编码。

选路种群中的一个个体表示所有业务的一种选路方案。假设选路种群中的一个个体为x=(x₁,x₂,…,x_k,…,x_NR),则x_k=q表示业务r_k占用其候选路径集中的路径 Qkq,即有 φkq=1。

类似地,纤芯分配种群中一个个体表示所有业务的一种纤芯分配方案。由于研究对象是纤芯可变的多纤芯弹性光网络,因此可以用y= (ykl)NR×L表示一个纤芯分配个体,其中

ykl=cl,l≤Lkq,xk=q0,l>Lkq,xk=q,(8)

式中:L= max1≤k≤NR,1≤q≤NkLkq,即所有路径长度的最大值。(8)式表示业务r_k占用路径 Qkq上第l段链路上的c_l(1≤c_l≤N_C)。

3.2 交叉算子

选路个体和纤芯分配个体均采用整数编码,因此所设计的交叉算子适用于选路和纤芯分配个体。假设z⁽¹⁾=( z11, z21,…, zk1,…, zN1)和z⁽²⁾=( z12, z22,…, zk2,…, zN2)是两个用于交叉的两个亲代个体,则两个子代个体z^(c1)=( z1(c1), z2(c1),…, zk(c1),…, zN(c1))和z^(c2)=( z1(c2), z2(c2),…, zk(c2),…, zN(c2))可表示为

zk(c1)=floorθk×zk2+1,zk1≤zk2floor[θk×(Mk-zk1)]+1,zk1>zk2,(9)zk(c2)=floorθk×zk1+1,zk1≥zk2floor[zk1+θk×(Mk-zk2)]+1,zk1<zk2,(10)

式中:floor(·)表示向下取整函数;θ_k为0到1之间的随机数;M_k为第k维度上能够取到的最大值,当交叉个体为选路个体时M_k= Q,Q为候选路径集合的数目;当交叉个体为选纤芯个体时M_k=N_C。N是个体的长度,当交叉个体为选路个体时N=N_R,否则有N=L。

3.3 变异算子

变异算子是改变个体上某个或某些基因位上的值,以提高算法的搜索能力,提高搜索到最优解的可能性。假设z=(z₁,z₂,…,z_k,…,z_N)是一个用于变异的亲代个体,变异后的子代个体z^(m)=( z1m, z2m,…, zkm,…, zNm)可表示为

zkm=floor[zk-θk(1+Mk)]+1,θk≤zk/(1+Mk)floor[θk(1+Mk)-zk]+1,θk>zk/(1+Mk),(11)

式中:z_k为用于进行变异的亲代个体中第k个分量; zkm为变异后得到新个体的第k个分量的值;k为索引值,即k=1,2,…,N。

3.4 局部搜索算子

局部搜索算子能够在个体周围的某个小区域内进行搜索,得到更好的个体,以提高算法的搜索能力。设计了一个针对纤芯分配个体的局部搜索算子,具体如下:假设z=(z₁,z₂,…,z_k,…,z_NR)是一个用于局部搜索的亲代个体,首先产生两个随机数p,q(1≤p≤q≤N_R),那么z_k(p≤k≤q)可表示为

zk=zk+γkδk,(12)

式中:γ_k为-1~1之间的随机数,δ_k=min{z_k-1,M_k-z_k}。

3.5 适应度函数

适应度函数是评价种群中个体优劣的重要指标,表达式为

f=β-ρ,(13)

式中:β是一个常数,当个体为问题的可行解时β=1,否则β=0。适应度函数用于评价种群中的优劣,适应度函数越大,个体越好。

4 实验结果及分析

4.1 仿真参数设置

仿真实验中采用了两个网络拓扑:具有14个结点和21条链路的国家自然科学基金网络(NSFNET)、27个结点和44条链路的美国骨干网(US Backbone)。4种调制格式BPSK (Binary Phase Shift Keying)、QPSK(Quadrature Phase Shift Keying)、8QAM (8 Quadrature Amplitude Modulation)、16QAM(16 Quadrature Amplitude Modulation)的最大传输距离分别为9600,4800,2400,1200 km^[22]。链路中每条纤芯上拥有的频隙数为N_F=160,采用5组不同的业务量,分别为500×N_C,750×N_C,1000×N_C,1250×N_C,1500×N_C。每组业务中不同业务所需占用的频隙数在区间[5, 20]内产生且满足均匀分布。串扰阈值σ=0.5。遗传算法中的参数设置为:种群规模P_s=100,交叉概率和变异概率分别为p_c=0.8和p_m=0.1,最大迭代次数G_m=5000。

为验证所提带有局部搜索算子模型的求解算法(GALS)的高效性,与3个算法进行了对比:第1个是文献[ 15]提出的纤芯分配算法(RSCA);第2个是文献[ 18]提出的基于轮换策略的纤芯分配算法(IR);第3个是文献[ 19]提出的基于遗传算法的模型求解算法(GA)。

4.2 实验结果

图3和图4给出了5纤芯弹性光网络中NSFNET和US Backbone中业务的阻塞率R_B随业务数量的变化情况。图5和图6给出了7纤芯弹性光网络中NSFNET和US Backbone中业务的阻塞率随业务数量的变化情况。图7和图8给出了11纤芯弹性光网络中NSFNET和US Backbone中业务的阻塞率随业务数量的变化情况。6个仿真结果图中都是每组数据独立运行20次后取平均值后的结果。

图 3. NC=5时NSFNET中的结果

Fig. 3. Results in NSFNET when NC=5

下载图片 查看所有图片

图 4. NC=5时US Backbone中的结果

Fig. 4. Results in US Backbone when NC=5

下载图片 查看所有图片

图 5. NC=7时NSFNET中的结果图

Fig. 5. Results in NSFNET when NC=7

下载图片 查看所有图片

图 6. NC=7时US Backbone中的结果

Fig. 6. Results in US Backbone when NC=7

下载图片 查看所有图片

图 7. NC=11时NSFNET中的结果

Fig. 7. Results in NSFNET when NC=11

下载图片 查看所有图片

图 8. NC=11时US Backbone中的结果

Fig. 8. Results in US Backbone when NC=11

下载图片 查看所有图片

4.3 实验结果分析

从仿真实验结果图3和图4中可以看出:当纤芯数目为5时,所设计的算法能够得到比3种对比算法都小的阻塞率。算法RSCA采用的启发式策略不能有效地将业务分配到不同的纤芯上,只选择最短路径进行分配,增加了业务被阻塞的可能性。IR算法可以从一定程度上提高了业务在不同链路纤芯中实现分配的均衡性,但是该算法仅利用根据当前信息进行选路的纤芯分配,容易陷入局部最优,不能得到问题的最优解。GA算法虽然能在一定程度上降低网络的阻塞率,但是采用纤芯不可换的方式也会使得一些业务被阻塞。本文提出的GALS算法增加了局部搜索算子,可以提高算法搜索到最优解的能力,同一路径、不同的链路上占用的纤芯号可以不同,能够尽可能为业务服务,减小业务被阻塞的可能性。因此,所建立的模型和设计的算法能得到比对比算法小的阻塞率。且由仿真结果图可以看出,随着业务量的逐渐增加,业务的阻塞率也逐渐增加,所提出的算法比对比算法所减少的阻塞率也逐渐提高,因此能够得到更优的选路和纤芯分配方案。

5 结论

针对频隙资源有限的多纤芯弹性光网络中纤芯可交换的业务选路和纤芯分配问题进行了研究。为解决该问题,1) 建立了一个以最小化业务阻塞率为优化目标的全局约束优化模型。2) 为高效地求解所建立的优化模型,考虑路径的长度以及路径的频谱可用性为业务选择候选路径集,设计了具有高效的编码方法、交叉、变异及局部搜索算子的遗传算法。3) 在不同的网络拓扑中进行了仿真实验,结果表明所设计算法在相同的业务量情况下能够得到比对比算法都小的业务阻塞率,即可以得到较优的选路以及纤芯分配方案。然而所设计的算法时间复杂度相对较大,故更适合求解静态选路和纤芯分配问题。