王井龙

中国电信股份有限公司

0 引言

随着5G网络的快速建设和应用，各种基于5G网络的业务和应用快速增加。为提高基础网络的资源利用率，节约网络建设的成本，网络切片技术已成为网络运营商普遍采用的关键技术。在网络切片环境下，传统的基础网络被划分为底层网络和虚拟网络两个部分。其中，底层网络包括底层节点和底层链路。虚拟网络服务提供商通过租用底层网络的资源，构建虚拟网络，为用户提供特定的业务和服务。在网络切片环境下，如何提高底层网络资源的利用率是一个重要的研究内容。

通过对已有研究分析可知，已有研究已经采取了较多的策略，用于提高底层网络的资源利用率。但是，已有研究主要采用贪婪或随机的策略，基于网络特性进行资源分配，这种资源分配策略容易导致算法获得的解不是全局最优解。另外，部分智能化算法已被应用到资源分配，但是这些算法没有利用网络特征进行资源分配，给算法的运行带来较大的开销，也较难获得全局最优解。为解决此问题，本文首先分析网络特征，其次基于网络特征采取遗传算法进行资源分配。本文首先为需求资源较多的虚拟网络分配资源，这样可以降低因底层网络资源缺少导致资源分配失败的概率。其次，采用遗传算法，为每个虚拟网请求智能化求解最优的资源分配算法。

1 问题描述

网络切片环境下，为了提高底层网络的资源利用率，需要根据底层网络拓扑的特点和虚拟网请求的资源特征，实现资源的高效率分配。本文使用GS=(NS,ES)表示底层网络拓扑。GS=(NS,ES)包括底层节点集合NS和底层链路集合ES。底层节点集合NS由底层节点构成，每个底层节点包括计算资源属性和位置属性，分别用和表示。底层链路集合ES由底层链路构成，每条底层链路的属性是带宽资源，使用表示。在虚拟网拓扑方面，使用GV=(NV,EV)表示虚拟网络拓扑。GV=(NV,EV)由虚拟节点集合NV和虚拟链路集合EV构成。每个虚拟节点包括计算资源属性和位置属性，分别使用表示。在底层节点为虚拟节点分配资源时，需要同时满足计算资源属性和位置属性的限制。在计算资源属性限制方面，底层节点为虚拟节点分配的计算资源容量需要满足虚拟节点的计算资源需求量。在位置属性的限制方面，底层节点的位置需要在虚拟节点位置属性的半径范围内。

通过对已有虚拟网资源分配算法分析可知，对于虚拟节点的资源分配，虚拟网资源分配失败的原因主要是底层网络的节点资源不能满足虚拟节点资源需求。为解决此问题，本文将优先为资源需求较大的虚拟网络分配资源，从而降低因底层节点资源缺少导致的资源分配失败问题。

2 基于遗传算法的虚拟网最优资源分配算法

根据遗传算法的基本原理，如果将遗传算法应用于虚拟网资源分配问题，需要解决染色体编码、种群初始化、适应度函数定义、选择操作定义、交叉操作定义、变异操作定义6个关键问题。

2.1 遗传算法参数分析

在染色体编码方面，将每个虚拟网的映射方案建模为一个染色体。对于虚拟网，染色体编码表示为表示虚拟网的D个虚拟节点所映射的底层网络节点的编号。

在种群初始化方面，根据网络规模，采用种群初始化方法生成初始种群，作为算法的起始解。初始化种群的规模与虚拟网的规模相关，取值为虚拟网包含的虚拟节点数量的n倍。本文初始化种群的规模取10倍。例如，当虚拟网络包括10个虚拟节点，初始化种群的数量为100个。

在适应度函数定义方面，当算法完成一个虚拟网资源分配后，底层网络开销与算法的优劣相关。当算法比较优化时，可以减少底层网络资源的开销。所以，本文将底层网络开销与适应度函数进行关联。由于优化的目标是选择适应度值尽可能大的染色体，为便于计算，当映射成功虚拟网后，本文将映射成功虚拟网的适应度函数定义为底层网络开销的倒数，如公式（4）所示。根据公式（4）的定义可知，适应度取值越大，说明底层网络的开销越小。

在选择操作定义方面，为了优化和更新种群，需要从已有种群中选择部分较优化的个体加入到新种群。在选择个体时，本文按照个体的适应度值进行降序排列，选择适应度值较大的个体加入新的种群中。在交叉操作定义方面，从较优化的个体中选择两个个体作为交叉操作中的父代，之后将两个父代进行部分替换，替换后根据同一虚拟网不能有两个虚拟节点映射到相同底层节点的约束，对两个新个体进行调整，得到新的两个个体。在变异操作定义方面，从较优化的个体中选择一个个体作为变异操作的父代，之后将父代中的底层节点编号进行互换，从而生成新的个体。

2.2 资源分配算法

本文提出的网络切片下基于遗传算法的虚拟网最优资源分配算法（Virtual Network Resource Allocation Algorithm based on Genetic Algorithm，VNRAAoGA）如表1所示。该算法包括虚拟网的节点资源需求评估及降序排列、对于集合中的每个虚拟网请求分配资源两个过程。虚拟网的节点资源需求评估及降序排列步骤，主要用于分析虚拟网节点资源需求的数量。如果虚拟网需求的节点资源较多，需要优先分配资源，从而防止部分虚拟节点因资源需求太大不能被满足导致资源分配失败的情况发生。

表1 基于遗传算法的虚拟网资源分配算法

3 性能分析

实验环境方面，使用GT-ITM工具生成网络拓扑。生成的网络拓扑包括底层网络拓扑和虚拟网络拓扑。底层网络拓扑包括100个底层网络节点。底层网络的网络链路由任意两个节点之间以0.3的概率连接生成。每个底层网络节点的计算资源、每条链路的带宽资源服从[15，35]的均匀分布。虚拟网络拓扑包括的虚拟节点服从[3，10]的均匀分布。虚拟网络的虚拟链路由任意两个虚拟节点之间以0.2的概率连接生成。每个虚拟网络节点的计算资源服从[1，3]的均匀分布。每条虚拟链路的带宽资源服从[1，6]的均匀分布。

实验中使用固定的时间段进行网络环境更新和生成虚拟网资源分配请求。实验中生成的虚拟网资源分配请求数量为2 000个。每个虚拟网请求的到达服从2个时间单位的泊松分布。每个虚拟网的生命时长为12个时间单位。实验运行的总时长为3 000个时间单位。

在算法性能分析方面，将本文算法VNRAAoGA与基于贪婪策略的虚拟网资源分配算法（Virtual Network Resource Allocation Algorithm based on Greedy Strategy，VNRAAoGS）进行比较。VNRAAoGS算法在为每个虚拟网分配资源时，采用随机搜索策略，查找最优的资源分配策略。为验证算法的性能，实验中从底层网络开销、底层网络收益、虚拟网络映射成功率3个维度对两个算法进行比较。在底层网络开销对比分析时，考虑到分配给虚拟网的资源之和较大，不便于分析。本文采取max-min归一化方法将底层网络资源开销进行归一化处理，为了保证资源开销大的资源分配策略在归一化后的取值仍然较大，在采用max-min归一化方法时，使用底层网络开销值减去最小的开销值作为归一化方法的分子部分。

底层网络开销比较结果如图1所示。X轴表示虚拟网请求的数量从100个增加到600个。Y轴表示底层网络开销的取值。从图可知，随着虚拟网请求数量的增加，两种算法下底层网络的开销快速增加。这是因为虚拟网请求数量的增加，需要底层网络为其分配的资源数量快速增加。比较两种算法，不同的虚拟网请求数量下，本文算法的底层网络开销较小。这说明本文算法为虚拟网分配了更加优化的底层网络资源，从而减少了底层网络的开销。

图1 底层网络开销比较

底层网络收益比较的结果如图2所示。图中，X轴表示虚拟网资源分配算法的运行时长。Y轴表示底层网络的收益。从图可知，随着虚拟网资源分配算法的运行时间增加，两个算法下获得的底层网络收益都在降低并趋于稳定。这是因为随着算法运行时间增加，底层网络的剩余资源越来越少，不能满足新的虚拟网请求。同时，由于底层网络的剩余资源规模也逐渐变小，不能满足大容量的资源请求。两个算法的性能比较方面，本文算法下底层网络获得了较大的收益，说明本文算法可以提高虚拟网的资源分配成功率，从而提升底层网络的收益。

图2 底层网络收益比较

虚拟网络映射成功率比较结果如图3所示。X轴表示虚拟网资源分配算法的运行时长。Y轴表示虚拟网映射成功率。从图可知，随着虚拟网算法运行时间增加，两个算法的虚拟网映射成功率都趋于稳定。相对于传统算法，在本文算法下，虚拟网映射成功率较高，表明本文算法为虚拟网分配了比较优化的底层网络资源，从而使更多的虚拟网能够映射成功。

图3 虚拟网络映射成功率比较

4 结束语

网络切片技术是提升网络资源利用率的关键技术之一。为合理利用底层网络资源，虚拟网络的资源分配问题成为研究重点。为降低底层网络开销、提升虚拟网资源分配的成功率，本文提出了基于遗传算法的虚拟网资源分配算法。在实验部分，从底层网络的开销、底层网络的收益、虚拟网映射成功率3个方面，将本文算法与传统算法进行比较，验证了本文算法较好地提升了虚拟网资源分配算法的性能。考虑到网络切片环境下虚拟网业务的优先级越来越重要，为了保证高优先级业务的虚拟网能够优先获得底层网络资源，需要在本文研究的基础上增加虚拟网优先级因素。下一步工作将基于本文研究成果，研究基于虚拟网业务优先级的资源分配算法，从而提升高优先级虚拟网的服务质量。