SDM-EON中基于串扰避免的多纤芯分配算法_张盛峰.pdf

第 卷第 期重庆邮电大学学报（自然科学版）年 月 （）：中基于串扰避免的多纤芯分配算法收稿日期：修订日期：通讯作者：陈会丹 基金项目：国家自然科学基金（）：（）张盛峰，陈会丹，彭 樱（重庆邮电大学 通信与信息工程学院，重庆）摘 要：为了解决空分复用弹性光网络中的频谱碎片、路由频谱纤芯分配（）和低业务负载下芯间串扰等问题，建立针对多纤芯 问题的动态业务分割整数线性规划（）模型，提出基于串扰避免的多纤芯分配算法（）。在路由选择阶段，综合路径负载和跳数设计路径排序公式；在频谱分配阶段，将纤芯分组，组内纤芯分类和多纤芯分配相结合；通过业务分割的方式使多个子业务独立地在同组内的多条纤芯上传输，从而减小串扰和碎片的产生。仿真结果表明，与对比算法相比，所提算法在带宽阻塞率和频谱利用率方面都取得了较好的性能。关键词：空分复用弹性光网络；串扰避免；频谱碎片；多纤芯分配中图分类号：文献标志码：文章编号：（），（，）：，（），（），：；引 言传统的波分复用（，）网络采用固定粒度（或）的波长分配方式，难以实现频谱资源的高效利用，并且无法自适应选择调制格式，网络资源配置方式僵化。随着流量需求的增加，使用单芯光纤的弹性光网络已渐渐达到其本身的香农极限，无法满足未来网络流量的需求，于是人们开始广泛研究空分复用弹性光网络（，）。基于多芯光纤（，）的 虽然具有高效、灵活分配频谱资源、带宽容量成倍增加等优点，但由于引进了空间这一维度，因而业务在网络中的建立过程更加复杂，并且还会有芯间串扰问题的产生。文献对弹性光网络中涉及到的相关问题进行了详细描述，包括弹性光网络的基本原理和结构、主要的硬件组成、芯间串扰和碎片形成的原因等，并总结了以往文献提出的各种解决串扰、碎片和频谱分配问题的方法。文献提出纤芯优先级和纤芯分类的概念，它通过尽可能避免使用相邻的纤芯来达到减少串扰的目的，另外，通过为每个纤芯分配统一的带宽连接来减少频谱碎片的产生。结果表明，该方法可以通过这两种策略提高整个网络的频谱利用率，降低阻塞率。文献通过在关键节点配置频谱转换器从而放宽网络对频谱一致性的要求，采用频谱转换以降低业务串扰，改善带宽阻塞率。文献采用业务分割的方法降低了网络对频谱连续性的要求，从源节点到目的节点的光路请求经过业务分割后，在多条路径上传输，直到一个连接所需的全部频隙分配完毕。文献将光谱进行分区，每区划分成 的幂次标准频谱块，该算法通过对业务进行分割、分割后的子业务在同一个路径分组里寻找路径的方式建立的光路连接。由于有保护带宽的存在，分割的子业务越多，浪费的频隙数越多。考虑到多芯光纤的每条纤芯都可作为一个独立的通道，文献提出的纤芯频谱块多路（，）算法通过多纤芯分配的方法实现业务请求的建立，但它没有考虑保护带宽和频谱块类型的优先级，只是寻找第一个可用的频谱块进行分配，这对后续业务的建立会造成不利影响，并且，在某条纤芯上若没有大于或等于所需标准块数目的频谱块，算法会直接考虑下一纤芯，这对下一纤芯频谱块上连续频隙的数目要求更严格，使得业务的建立更困难。文献也是利用了多纤芯分配的思想，并且通过串扰感知的方式将串扰对网络的影响考虑在内，但和文献不同，这篇文献的侧重点主要是在提高网络生存性和减小能源消耗方面。采用 的 虽然能缓解大容量数据传输问题，但由于增加了纤芯这一维度，相应地增加了资源分配的复杂度。首先，业务传输必须遵循频谱分配的 个约束条件，降低了业务分配的灵活性；其次，在 中采用多芯光纤，在为业务提供更多频谱资源的同时，也带来了芯间串扰问题，影响业务的传输质量；最后，频谱碎片也是 中一个不可忽视的问题，当网络中的空闲频谱块大小不能满足到来业务需要的频隙数时，业务就会被阻塞，从而影响网络性能。基于以上分析可知，打破业务传输时的频谱连续性约束，充分利用网络中的频谱碎片，这是减少业务阻塞的一种有效策略。业务分割是打破频谱连续性要求的常用方式，它通过将一个完整的业务分割成多个子业务，每个子业务独立进行传输的方法，最终达到业务成功建立连接的目的，在这个过程中，以何种方式分割业务，分割后的子业务采用什么方式传输是一项具有研究意义和挑战性的工作，已有研究大多采用平均分割或根据路径负载分割的方式分割业务，并且分割后的子业务在多条路径上传输，较少涉及在空分复用弹性光网络中进行多纤芯分配的问题。然而，多路径传输时，由于路径长度不同，业务在传输过程中会产生不同的时延差，影响业务的传输质量，而多纤芯传输使用的是同一条路径上的频谱资源，不会产生时延差的问题。因此，本文提出了一种在空分复用弹性光网络中考虑串扰和碎片的多纤芯分配算法，通过将纤芯分组，组内纤芯分类和多纤芯分配结合起来，最大程度地避免了串扰和碎片的产生。网络模型 问题描述本文中的网络拓扑可建模为一个无向图（，），其中 为网络拓扑中节点的集合，表示节点个数；为网络拓扑中链路的集合，表示链路数目。对于 重 庆 邮 电 大 学 学 报（自然科学版）第 卷每一条链路，定义一个频隙集合为 ，包含的频隙数量为 ，每条链路上的频隙数量相同；定义业务请求集合为，网络中业务请求的总数为；第 个业务请求表示为，、分别为源端、目的端，为业务请求的传输速率。本文采用自适应的调制格式，具体的调制格式和调制等级以及对应的传输距离如表 所示。为防止相邻业务间串扰，本文设置保护带宽，取值为 个频隙。表 调制格式与传输距离的关系 调制格式调制等级传输距离 模型路由频谱纤芯分配（，）问题的最终目标是在网络中频谱资源一定的情况下，最大化网络中成功建立连接的业务数；在频谱分配的过程中，满足一定约束条件的情况下，最小化业务请求使用的频隙数。根据以上分析，本文针对空分复用弹性光网络中的 问题设计了整数线性规划（，）模型。动态业务分割多纤芯路由频谱纤芯分配问题的链路路径的 数学模型如下。：纤芯集，。：当前到达业务请求的传输速率，。（）：当前到达业务请求的可行光路集，。：二进制变量，光路（）承载业务请求 时，。（）：光路（）的跳数。（）：光路（）所占据的频隙数。（，）：（）中经过给定，的光路子集。：光路（）承载的业务速率。：预先设置的最大业务分割块数。模型中的（）是依当前到达业务的（，）信息 及 现 有 连 接 状 态，可 分 配 频 隙 范 围 为，的可行光路集。目标函数为（）（）（）（）（，），（）（）（）（）（）（）式的目标是最小化为当前业务连接光路分配的频隙数；（）式满足了频谱非重叠，确保链路中一条纤芯上的一个频隙只能分配给一条光路；（）式保证业务分割下多条光路上承载的速率大于等于该业务的请求速率；（）式使得单个业务的分割数小于预置的最大值。该 模型是一个非多项式算法问题，在网络中存在大量业务的情况下，针对每一个请求，根据 模型得到最优解是一项时间复杂度极高的工作，不能满足动态业务频谱分配的实时性要求。因此，本文设计启发式算法来求解动态业务分割多纤芯路由频谱纤芯分配问题。考虑串扰和碎片的 算法为了解决 中的、芯间串扰和频谱碎片问题，本文主要通过 个启发式的想法来设计算法。首先，本文提出了一个光路排序公式，设计此公式的目的是在选择路径时，尽量使业务请求能均匀地分配在网络中的各条链路频谱资源上，避免瓶颈链路的产生，从而降低业务阻塞的概率；其次，在处理芯间串扰方面，本文设置了纤芯分组，保证同组内纤芯互不相邻，从而避免低业务负载下有芯间串扰的产生，以此提高网络中业务的传输质量；最后，由于到来业务的速率不同，随着业务动态建立和释放，网络中会产生很多的频谱碎片，为了解决这一问题，本文设置了组内纤芯分类，通过在每条纤芯为业务分配固定大小的频隙，避免碎片的产生，降低业务阻塞的概率。路由选择采用最短路径优先或最小跳数优先的策略虽然能减少频谱资源的消耗，但对于业务的成功建立并不总是有利的，因此，本文提出了考虑路径跳数和路径上资源使用情况的光路排序公式，公式设计如下。，（）（）第 期 张盛峰，等：中基于串扰避免的多纤芯分配算法（）式中：是路径（取 到）上链路的集合；是多芯光纤纤芯的集合；、和分别表示路径 上的链路数目、光纤的纤芯数目和每条链路上的频隙数目；（）是路径上的跳数；，是个二进制变量，当链路 纤芯 槽 未占用时，值为，否则为。设计（）式是为了在选择路径时，尽量使业务请求均匀地分配在网络中的各条链路频谱资源上，避免瓶颈链路的产生，均衡网络负载，从而降低业务阻塞的概率。越大，表明路径 上所有链路纤芯上的空闲频隙数目越多，路径 的跳数越少，在此条路径上业务成功建立连接的可能性越大，因此，在进行路由选择时，将候选路径按照权重值降序排列，优先选择权重值大的路径进行传输。计算业务所需频谱槽数的公式为 （）（）式中，为业务请求的传输速率；为所选调制格式对应的调制等级；为单个频隙的宽度大小，取。（）式计算所需频隙数的方式没有考虑业务之间的保护带宽，这是因为在后续的多纤芯分配的过程中，我们无法预知需要的保护带宽总数目，不过在进行多纤芯传输时，会将保护带宽考虑在内，这在后续的工作中会进行说明。纤芯分组和纤芯分类为了尽量避免串扰的产生，减小在纤芯频谱分配过程中相邻纤芯间同位频隙的使用，本文所提路径选择多纤芯分配（，）算法用基于顶点着色的方法将纤芯进行分组，即保证分组后同组内的纤芯互不相邻。在后续进行多纤芯分配时，每次只选择一个纤芯组执行多纤芯分配过程，这样在业务成功建立连接后，多个子业务间不会有串扰的产生。由于不同组的纤芯间会产生芯间串扰，为了进一步降低串扰，我们设置纤芯组优先级，即每次请求到来后，按照组优先级的顺序依次选择纤芯组，只有前一个纤芯组没有可用的频谱资源时，才考虑后一个，这样能够保证在低业务量时，业务都建立在同一纤芯组的频谱资源上，从而达到避免串扰的目的。由于每个业务到来的速率不同，随着业务的动态建立和释放，网络中的频谱资源变得杂乱无章，难以管理。因此，在预处理阶段，本文所提算法还对同组内的纤芯进行分类，每条纤芯按照 的幂次划分标准频谱块，根据标准频谱块中的频隙数对纤芯分类（中间纤芯作为一般类使用），分类数即为每组内纤芯的数目。业务在每个纤芯上分配的频隙数必须是其标准频谱块的整数倍，即标准频谱块要么不使用，要么全使用。基于业务分割的 算法在频谱分配阶段，本文提出了一种改进的多纤芯分配（，）算法，该算法的核心是业务分割，分割后多个子业务频谱分配的过程发生在同一纤芯组中。具体的算法流程如图 所示。以 芯光纤为例介绍多纤芯分配过程，如图 所示。图 中，纤芯、为组，纤芯、为组，中间纤芯 作为一般类纤芯与组、组 配合使用。以请求在组 里的分配为例。假设到来的业务请求需要 个频隙，保护带宽为 ，纤芯、对应的标准块的频隙数分别为、，芯光纤的结构和纤芯组 以及中间纤芯中的资源使用情况见图。以下计算中，表示当前需要分配的频隙数；表示在某纤芯上需要分配的标准频谱块数目。：）纤芯 上无和所需相等或比它大的频谱块，因此将最大的标准块，即 个 的频谱块分配给业务，更新业务请求需要的剩余频谱槽数目。：）（）纤芯 上和所需相等的频谱块有 个，选择第一个频谱块，更新业务请求需要的剩余频谱槽数目。：）（）纤芯 上和所需相等的频谱块有 个，将其分配给业务请求。：此时，纤芯组 中所有纤芯已经检查完毕，但仍需要 的资源，则在中间纤芯 上分配。算法本文所提 算法分为 个阶段。在预处理阶段，进行纤芯分组和纤芯分类；在 阶段，先根据（）式选择出 条候选路径并降序排列，然后按照组优先级顺序选择纤芯组，在所选纤芯组内执行 算法。具体的算法过程见图。重 庆 邮 电 大 学 学 报（自然科学版）第 卷图 算法流程图 图 芯光纤结构及组 频谱资源 算法仿真及结果分析 仿真参数设置算法仿真使用 个节点、条链路的 网络和 个节点、条链路的 网络，图 图 分别为 和 的网络拓扑图，仿真的性能指标为带宽阻塞率（，）和频谱利用率（，），二者的计算公式为第 期 张盛峰，等：中基于串扰避免的多纤芯分配算法（）（）（）为阻塞业务的带宽总和，为业务请求的总带宽，、分别为网络链路数、纤芯数、每条纤芯上的频隙数和仿真时间。仿真时业务请求的到达时间服从参数为 的泊松分布，业务持续时