面向6G承载网的路由优化算法研究

张冬月，韩赛，王光全，王泽林，刘畅

（中国联合网络通信有限公司研究院，北京 100048）

0 引言

随着5G 商用落地，5G 技术成功地渗透到各行各业，实现了峰值速率、时延、网络能效等方面的显著提升[1]。6G 作为未来移动通信技术演进的方向，将呈现大量沉浸化、智慧化、全域化的新型业务，如无人驾驶、扩展现实（XR,Extended Reality）、感官互联等[2-3]。因此，对6G 网络的数据传输速率、网络时延以及连接密度提出了更高的要求与挑战[4]。6G 相对于5G，其性能指标将提升10～100 倍，尤其在时延性能方面，6G 对端到端时延的要求是小于0.1 ms[5]，在6G 时代将会面临实时海量数据的传输，数据的暴增将带来大量的拥塞和数据分组时延。承载网作为支撑6G 新型业务的重要基础，超低时延特性将会对承载网提出新的需求。考虑到空口、核心网等处理时延，6G 业务对承载网络传输时延的要求将更加严苛。

为满足6G 网络对承载网超低时延的要求，需要对现有的IP 路由转发策略进行优化，在现网中IP 链路的metric 值用于指示网络设备之间传输数据的代价，是路由算法用以确定到达目的地的最佳路径的计量标准，作为路由转发的关键参数，其设置结果至关重要[6]，直接影响了IP 路由转发的效率以及网络时延。传统的metric 设置方式主要是网络专家根据专家经验进行人工设定，尝试方案少，无法确定其为最优方案，存在局限性大、部分IP 链路时延过高、无法满足6G 超低时延场景等问题，因此亟需智能化手段来解决上述问题。

伴随着AI 的蓬勃发展，AI 技术与6G 的深度融合作为实现内生智能新型网络的重要基础，将驱动智慧网络不断升级[5]。目前路由优化领域的研究主要有：基于有监督学习的路由优化方法[7-10]，利用监督学习模型提取流量特征，预测未来流量，获取最佳路由策略，或者利用监督学习模型直接学习路径的研究；基于强化学习的路由优化算法[11-14]；基于启发式算法的路由优化算法[15-17]等，但尚未有针对metric 设计方法的研究。

针对以上问题，本文提出了一种面向6G 承载网的基于k-means[18]和粒子群优化算法（PSO,Particle Swarm Optimization）[19]的路由优化算法，可实现在有效范围内大规模搜索最优方案，克服人工方案的局限性。该算法采用k-means 算法对IP 链路进行聚类分析，可有效缩小PSO 粒子搜索范围，提高粒子搜索效率；使用PSO 算法找出最优的metric 方案。本算法通过在网络仿真平台[20]上进行测试，验证了算法的有效性。

1 基于k-means和PSO的路由优化算法

1.1 数据

本文采用的数据为国际IP 链路，每个IP 链路的特征包括：发送端城市的经度、发送端城市的纬度、发送端路由的角色、接收端城市的经度、接收端城市的纬度、接收端路由的角色、链路的时延、链路当前的metric 值、链路带宽、是否跨国。其中，路由的角色包括AR、CR 等，不同的角色代表不同的作用。

1.2 路由优化算法

本文提出的路由优化算法是基于k-means 算法和PSO 算法。k-means 算法是一种经典的聚类算法。该算法主要是将样本按照样本距离聚集到k个簇中，最终实现簇内距离小、簇间距离大；PSO 算法是模拟鸟群觅食行为的启发式算法，通过鸟群之间的集体协作使群体获得最优解。具体流程如图1 所示，主要包括以下两个步骤：

图1 PSO路由优化算法流程图

（1）为缩小PSO 粒子搜索范围，提高粒子搜索效率，本文采用k-means 算法对IP 链路进行聚类分析。

（2）使用PSO 算法找出最优的metric 方案。

具体流程如下：

（1）采用k-means 算法对IP 链路进行聚类分析，过程如下：

1）输入数据和参数，设置k-means 算法的簇数K=10。如果（源设备）国内-＞（目的设备）国外跨国/（源设备）国外-＞（目的设备）国内跨国：是否跨国设置为20 000，否则设置为0。

2）对输入数据做归一化处理，采用最大最小归一化（MinMaxScaler）方法，利用数据列中的最大值和最小值进行标准化处理，标准化后的数值范围为[0,1]，计算方式为数据与该列的最小值作差，再除以极差。

3）随机选择K个点作为点的聚类中心，这表示要将数据分为K类。

4）遍历所有的点P，算出P到每个聚类中心的距离，此距离采用欧氏距离，将P放到最近的聚类中心的点集中，遍历结束后将得到K个点集。

5）遍历每一个点集，算出每一个点集的中心位置，将其作为新的聚类中心。

6）重复4）和5），直到聚类中心位置不再移动。

聚类结果将IP 链路分为10 组，根据组内IP 链路的原始metric 值的范围，为每一组的IP 链路设置相同的metric范围，此取值范围用于PSO 算法中粒子更新范围上限和下限的设置。10 组链路的metric 范围具体如表1 所示：

表1 IP链路的metric范围

（2）根据聚类结果对PSO 进行参数设置，使用PSO 找出最优的metric 方案，算法中的每一个粒子代表一种metric 方案，过程如下：

1）输入参数：维数dim设置为82；粒子的数量pop设置为40；粒子搜索的下限lb、粒子搜索的上限ub（设置方法根据聚类结果）；惯性权重w设置为0.8；学习因子c1和c2均设置为0.5。

2）初始化粒子群体（群体规模为pop），包括随机位置和速度。

3）根据损失函数计算每个粒子的损失，该算法的损失函数为当前粒子在网络仿真平台上的全网平均时延。

4）对于每个粒子，将其当前损失与个体历史最佳位置对应的损失做比较，如果当前的损失更小，则将用当前位置更新历史最佳位置pbest。

5）对于每个粒子，将其当前损失与全局最佳位置对应的损失做比较，如果当前的损失更小，则将用当前粒子的位置更新全局最佳位置gbest。

6）更新每个粒子的速度与位置，粒子i的第d维速度更新公式为：

其中：

r1、r2：两个随机函数，取值范围为[0,1]，以增加随机性；

w：惯性权重，非负数，调节对解空间的搜索范围；

c1、c2：加速度常数，调节学习最大步长（超参数）。

粒子i的第d维位置更新公式为：

7）如果没有满足结束条件，则返回3），结束条件为损失在多次迭代后没有发生变化。

1.3 实验结果

根据以上方法，获得的最优metric 方案如表2 所示。由于链路较多，本文只展示部分实验结果。

表2 部分IP链路的metric结果

本文使用IP 网络仿真平台对metric 方案进行验证，此平台针对IP 数据网进行路由仿真，涉及IGP/BGP/MPLS 等IP 层面的规划设计，包括对路由协议、路径以及流量的仿真。

本方案在网络仿真平台运行结果显示：本方案全网平均时延为174.841 ms，原始的metric 方案的平均时延为180.975 ms，相对于原始的方案平均时延降低了3.39%。

2 结束语

本文研究如何在6G 网络超低时延的要求下有效提升IP 承载网路由转发效率，结合人工智能技术，提出了一种基于k-means 和PSO 的IP 路由优化算法。通过k-means算法对现有的IP 链路的metric 值进行聚类，根据聚类结果使用PSO 算法寻找最优的metric 组合方案，可进一步提升路由转发效率，最终实现降低全网业务传输时延。通过仿真实验表明，该算法可以有效降低IP 承载网业务传输时延，提高IP 承载网业务传输效率。