无滤波器光网络中多层边不相交树的规划

《Optical Fiber Technology》：Planning of multilevel edge-disjoint trees in filterless optical networks

针对多级无过滤光网络中多播树规划与频谱分配问题，提出EDHM启发式算法和EDGA遗传算法，通过仿真验证EDGA在降低峰值频谱使用方面优于传统方法，多级设计可提升效率，简单需求分配规则表现稳健。

　　

Kuan-Yi Wu|Der-Rong Din

国立彰化教育大学计算机科学与信息工程系，台湾彰化市金德路1号，500

摘要

无滤波光网络（FONs）因其成本和能效优势而备受关注；然而，在边缘不相交的情况下进行多播服务会加剧频谱竞争。本研究探讨了在物理拓扑和流量需求矩阵的约束下，联合设计多层边缘不相交的多播树和频谱分配方案，以最小化最大频谱占用数量。我们开发了单层和多层算法，包括基于最小生成树和最短路径树的启发式方法，以及遗传算法（GA）的变体，这些算法共同优化了树的结构和需求到树的分配。仿真结果表明，与启发式方法相比，遗传算法能够持续降低峰值频谱使用量。同时，多层设计进一步降低了峰值频谱使用量。我们还观察到，一种简单的分配规则——优先分配给最小边缘树——在各种网络中都能表现出良好的性能。研究结果表明，基于遗传算法的多层设计为FONs中的多播服务提供了一种实用且可扩展的解决方案。

引言

光纤通信技术的快速发展重新激发了人们对在严格成本和能源限制下提供高容量传输架构的兴趣。其中，无滤波光网络（FONs） [1]去除了波长选择性组件，通过广播选择（B&S）方案被动转发信号，大幅降低了节点复杂性、控制平面开销和部署成本。但这些优势也伴随着挑战：功率分割损耗和波长干扰 [2]、[3]、频谱/资源竞争 [4]，以及生存能力和虚拟网络嵌入问题 [5]、[6]。对于对成本敏感和边缘应用场景而言，FONs仍然具有吸引力，因此需要制定能够保持信号完整性和效率的规划和分配方法。

在B&S架构下，每个节点将所有传入的光信号广播到所有输出链路；下游节点根据拓扑和功率预算进行被动选择。其主要特点包括 [1]、[2]、[3]、[4]：(1) 无滤波操作：波长在传输过程中无需主动过滤。(2) 功率分割：传入功率在输出端口之间分配，分割次数越多，衰减越大。(3) 被动选择：下游节点根据接收能力和信道利用率选择所需信号。这些特性简化了硬件设计，但限制了路由和频谱分配，尤其是在密集或高负载环境下。

为了提高可扩展性和效率，多层 FON架构在每一层组织多个光纤树，同一层内的树需要相互边缘不相交；不同层之间的树不必相互不相交 [7]。这种设计支持同一层内的独立子载波分配，实现多路径和备份传输，减少频谱竞争，并增强鲁棒性和容错能力。由于B&S机制可能导致同一树上的多对信号同时传输而引发竞争，因此需要精心规划树结构和频谱分配。此外，实际网络中的流量往往不均匀；假设流量均匀 [1]通常是错误的。图1展示了一个两层的示例。

采用具有多路径传输能力的多层结构时，特定流量需求可以通过不同层内的光纤树来传输。如何高效地在这些光纤树之间分配所需的频谱资源，以及配置适当的收发器和频谱分配以实现平衡的频谱利用和成本优化，成为一个复杂问题。

然而，[7]并未提供此类架构的规划方法。根据作者的文献综述，目前尚无研究提出用于设计多层FON架构的算法或实证分析。

我们研究了在异构流量和物理（例如距离）约束下，多层FONs的边缘不相交树规划问题。目标是逐层构建满足所有需求的边缘不相交树集合，同时最大化频谱效率。我们解决了以下问题：(1) 在多层结构中构建距离上可行的边缘不相交树。(2) 在资源有限的情况下，进行考虑流量的频谱分配以最大化效率。(3> 多层设计对性能、可扩展性和鲁棒性的影响。

为此，我们提出了：(i) 一种边缘不相交启发式多播（EDHM）算法，用于快速构建可行的树结构；以及(ii) 一种边缘不相交遗传算法（EDGA），用于联合优化拓扑和频谱分配。这两种方法都适用于多层场景。该方法在必要时能够分离高流量需求，平衡不同树之间的频谱使用，并减少最大占用频谱数量。

第2节回顾了相关工作。第3节阐述了模型和假设。第4节介绍了算法。第5节报告了性能评估结果。第6节进行了总结。

部分摘录

无滤波光网络

在FONs中，节点不具备波长选择能力，而是采用基于广播的传输方式，所有传入的光信号被无差别地转发到所有输出链路。这种设计显著降低了节点复杂性和网络部署成本，同时简化了控制平面。FON架构的主要优势在于硬件简单性和成本效益，使其特别适合静态或半静态光网络，尤其是在这些网络中频繁

问题定义

在多层FONs中，多播树和频谱分配策略对整体性能和频谱效率有直接影响。然而，在多层架构下，高效构建边缘不相交的多播树并同时进行频谱分配仍然是一个缺乏系统研究和规划方法的领域。本文致力于设计有效的多层树规划和频谱分配策略

针对多层FONs提出的算法

本节介绍了几种用于规划多层FONs中边缘不相交树、需求路由和频谱分配的算法。主要目标是在最大传输距离限制下构建高效的非重叠多播树集合，同时优化频谱资源利用。

仿真结果

这些算法在配备Intel Core i7-8700处理器（3.20 GHz）、16 GB RAM并运行64位Windows 10的工作站上进行了仿真测试。实现代码采用Python 3.8.0编写，并在Jupyter Notebook中执行。

测试拓扑包括具有7个节点和11条边的德国网络（G7）、具有10个节点和15条边的意大利网络（I10），以及具有17个节点和26条边的德国网络（G17），如图4所示。对于每种拓扑，需求集

结论

本研究在树结构、直径和覆盖范围的现实约束下，探讨了FONs中的边缘不相交树规划问题。我们提出了单层和双层架构，以及将树构建与频谱分配相结合的分配策略，并评估了三种进化搜索方法：(i) 仅考虑可行性的方法；(ii) 半可行性方法（强制树/无环性；惩罚直径/覆盖范围）；(iii> 允许所有违规但进行惩罚的方法。

CRediT作者贡献声明

Kuan-Yi Wu： 负责撰写初稿、软件开发及形式化分析。Der-Rong Din： 负责审稿与编辑、项目管理、方法论研究及概念构思。

利益冲突声明

作者声明以下可能构成潜在利益冲突的财务利益和个人关系：Der-Rong Din表示获得了台湾地区国家科学技术委员会的财政支持。如果还有其他作者，他们也声明没有已知的财务利益冲突或个人关系。