基于电力业务时延敏感度和服务可靠性的虚拟网络映射方法

郑伟军，徐 宏，王 征，唐锦江，胡景博，朱重希，姚继明

1.国网浙江省电力有限公司嘉兴供电公司，浙江 嘉兴 314000

2.国网浙江省电力有限公司桐乡市供电公司，浙江 桐乡 314506

3.全球能源互联网研究院有限公司，北京 102200

随着智能电网的快速发展与能源互联网的兴起，电网规模不断扩大，电力业务种类不断增多，电力业务类别可分为控制类、采集类和移动应用类，其中控制类业务涉及到核心生产控制的业务流程，对通信网络的要求十分严格。如配网差动保护业务，时延要求在15 ms范围内，时延抖动在±50 μs，可靠性要求99.999%，对于精准负荷控制业务，时延要求在50 ms范围内，可靠性要求99.999%［1］。

聚焦到智能配用电环节，5G技术为配电通信网“最后一公里”无线接入通信覆盖提供了一种更优的解决方案，配网差动保护、精准负荷控制、高级计量、分布式能源接入等业务可借力5G技术实现更优的业务承载。在使用同一5G网络承载多种电力业务的应用场景下，如何保障电力控制类等重要业务的时延和可靠性要求，是实现5G在电力系统中的规模化应用的重要条件。

虚拟化节点和链路资源的分配问题被称为虚拟网络嵌入（Virtual Network Embedded，VNE）［2］，目前，许多研究都着眼于提高物理基础设施的收入和减少虚拟网络映射时间的问题［3］，而带有约束条件的映射［3］被证明是 NP⁃hard 问题［4］。

现有的大多数映射算法［5］将给定的虚拟网络（Virtual Network，VN）映射分为两个独立有序的阶段：虚拟节点映射阶段和虚拟链路映射阶段。这种映射策略不能保证每个虚拟网络的最优或次优嵌入分配。文献［6］中作者采用节点度、节点强度和Markov Random Walk模型迭代计算所有节点优先级。文献［7］中作者考虑了不同拓扑属性的7个特征：“度”、“强度”、“距离中心性”、“接近中心性”、“介数中心性”、“特征向量中心性”和“卡茨中心性”，通过拓扑感知启发式算法，求解计算节点的相对重要性。文献［8］针对虚拟网络功能链对性能与可用性需求，以最大化资源利用率为目标，形式化定义了高可用虚拟网络功能链部署问题，证明了该问题是NP难问题，提出了基于路径扩展的虚拟网络功能部署算法，并采用备份共享的思路，提出基于概率空间划分的虚拟网络功能备份策略。文献［9］采用一致的优化模型综合分析网络资源分配的现有技术方法，包括成本优化、收益优化、剩余资源优化和网络能耗优化。进一步针对电信级运营，分析了业务等级违约最小化、跨网络分域部署策略和博弈机制设计方案，论述了动态拓扑适应、接纳和可靠性控制的方法，以及采用比例计算节能的优化问题建模。文献［10］提出的节点排序算法考虑了4种节点链路约束因素：节点位置、节点容量、链路带宽和链路传播延迟，以保证时延敏感业务的时延需求。但是，以上启发式映射算法都将节点映射阶段与链路映射阶段完全分离，均未考虑全局属性，忽略了链路映射结果对物理节点排名的影响，这可能会导致更高的映射成本和虚拟节点在底层网络上的分布式分布带来的负载不均衡问题。

由于VNE是为未来动态网络场景而设计的，因此最大限度地减少映射分配计算时间和保证嵌入质量非常重要。对于5G智能电网的端到端NS部署，需要考虑电力业务的具体QoS需求。文献［11］提出了一种基于遗传算法的容错虚拟链路映射（GFVLM）算法，在映射过程中考虑了负载均衡，避免了“瓶颈节点”的出现，保证网络的容错和可靠性。文献［12］提出了一种基于优先级和故障概率的主链路映射模型，考虑了智能电网的服务可靠性，为高可靠性链路提供高优先级的服务。但是以上智能电网场景下的虚拟网络映射算法未考虑电力业务在业务请求层的时延需求，由于虚拟网络请求的优先级不仅受业务类型不同的影响，还由资源消耗、映射成本、等待时间和持续时间等综合因素共同确定。然而以上虚拟网络映射算法都忽略了虚拟网络请求自身业务的差异性和业务属性参数对请求映射顺序的影响，造成虚拟网络请求等待时间过长从而可能导致请求接收率降低。而恰当地处理并调整虚拟网络映射的顺序，会有效提升虚拟网络映射算法的性能，缩短虚拟网络请求的等待时间并提高虚拟网络请求接收率，支撑更优质的网络承载服务。

综上所述，本文针对电力业务时延敏感度、节点的全局资源和业务可靠性需求，提出一种基于电力业务时延敏感度和服务可靠性的虚拟网络映射方案。首先对请求业务排序，缩短虚拟网络请求的等待时间并提高虚拟网络请求接收率；然后，在节点映射层，提出一种基于节点拓扑属性和相邻节点重要性的节点排序方法；最后，在链路映射层，构建基于链路时延和链路负载比方差的可靠性惩罚函数，提出基于遗传算法的链路映射算法。

1 系统模型

系统模型如图1所示，虚拟网络映射模型包括3层，分别是基础设施层、虚拟网络提供层和业务层。定义E表示虚拟网络映射模型中业务请求层提出资源请求的集合，e表示这个集合中的一个请求。将虚拟网络（VN）提供层的网络建模为一个加权图GV＝（NV，LV），其中，NV代表节点ni的集合，LV代表链路lx的集合。虚拟节点的计算能力需求为 cpu（ni），链路的带宽容量需求为BV（lx）。 物理网络可以抽象为加权无向图GS＝（NS，LS），NS和LS分别为物理网络的节点集合和链路集合。每条基础设施链路都有一个总带宽容量和剩余带宽BS（lx）。

图1 虚拟网络映射模型

服务接收率O（t）定义为时间段T内成功映射的虚拟网络请求数量与收到的虚拟网络请求数量的比值，表示式为

式中，Re（t）表示在时刻t成功映射的虚拟网络服务请求数，Ge（t）表示在时刻t收到的虚拟网络服务请求数。

2 虚拟网络映射算法

本文从电力业务的QoS要求出发，实现5G虚拟化技术与电力业务的动态需求高度匹配。考虑到电力业务时延敏感度、节点的全局资源、业务可靠性需求等因素，以有效提高虚拟网络请求接收率和资源利用率，保障业务的时延和可靠性需求。

在业务请求层根据业务时延敏感度对业务请求进行优先级排序，高优先级的请求优先选择虚拟节点；在虚拟网络提供层根据拓扑属性和相邻节点重要性对虚拟节点进行优先级排序，实现映射后链路的负载均衡，高优先级节点会优先映射最优链路；在基础设施层通过遗传算法求得最优链路映射方案，以保障业务的时延，提高业务的可靠性和网络资源的利用率。

2.1 业务请求优先级排序

由于不同业务请求的资源需求量和生存周期不同，因此对时延敏感度高且资源需求量大的业务请求设置高优先级可以提高后续请求的映射成功率，提高物理资源利用率。

定义业务请求所需资源为

式中，cpu（ni）为请求业务所需的cpu计算能力，为剩余链路带宽资源。

定义业务请求等待时间和最长等待时限的比值为

式中，tw为业务请求等待时间，TW为最长等待时限，该时限取决于电力业务的时延敏感度，时延敏感度越高，最长等待时限越短。

定义业务请求优先级属性P（GV）为

式中，Tc为业务请求持续时间，P（GV）值越大，优先级越高。当请求等待时间超过最大等待时限时，将优先级设为最高等级。

η是一个二分值，定义为

当η为0时，业务请求等待时间超过最大等待时限，将其优先级调至最高，即0，以保证业务请求的公平性，当时延不敏感的业务请求时间过长时，可暂时提高其优先级，优先发出请求。因此，业务请求的优先级p的最高级为0，其次为P（GV）的最大值，最后为P（GV）的最小值，始终优先执行优先级为0的业务请求。

2.2 虚拟节点优先级排序

在节点映射阶段通过启发式算法对虚拟节点进行排序，然后进行排序映射。本文将拓扑属性和相邻节点重要性作为排序参数，对节点进行排序，以确保映射后链路负载均衡。定义单个节点的拓扑属性值为

式中，Strength（ni）表示节点的强度属性，对于某个节点ni，其强度属性表示其相邻链路的强度的权重之和。在本文中，链路带宽表示链路的权值。也就是说，如果节点强度越高，节点就有越多的相邻资源来映射虚拟网络。表示邻居节点nbr（ni） 的链路带宽资源B（lij）的总和。 Ratio（ni）为节点负载率，定义为

式中，cpumax（ni）为节点最大计算资源；cpuremain（ni）为节点剩余计算资源，定义为

式中，cpu′（ni）为映射请求业务之前的cpu计算能力，cpu（ni）为请求业务需要的cpu计算能力。

为了考虑相邻节点对节点属性值的影响，定义了节点全局属性值。节点全局属性值SV（ni）表示为

式中，ρ定义为相邻节点重要性，表示带宽资源占总带宽资源的比例，用来衡量邻居节点的相对重要性，定义为

综上所述，将单个节点拓扑属性Rv（ni）和相邻节点重要性ρ作为输入，计算节点全局拓扑属性值SV，对节点进行排序。将满足业务请求计算能力cpu（ni）的节点放入集合S中，其中高优先级的业务优先选择属性值SV高的节点。算法执行流程图如图2所示。具体流程如算法1所示。

图2 虚拟节点排序算法流程图

算法1基于属性值的虚拟节点映射算法

2.3 基于多条件约束的链路映射方法

在虚拟网络提供层，根据拓扑属性和相邻节点重要性对虚拟节点进行优先级排序，实现映射后链路的负载均衡。本节考虑了基础设施层的可靠性、负载均衡和链路时延因素，构建了基于链路时延和链路负载比方差的可靠性惩罚函数，构建目标函数为

式中，α为权重值；DelayS为链路时延，其中，定义固定时延为Dfixed，排队时延为Dq，不对称时延为Dcd，即有

式中，固定时延Dfixed一般取区间均值1.57 ms；排队时延为平均流量到达速率，μr为队列的分组传输速率；不对称时延当双向通道延时不相等时，存在一定的时延差，因此设终端向主站发送方向通道时延为Td1，主站向终端发送方向通道时延为Td2，由于发送时延与接收时延不等造成的同步调整时间误差为：ΔTd＝且必须满足为制动系数），才能保证保护类业务不发生误动，即有

基础架构层链接的变化Var＿ratio（LS）表示为链路负载比方差

式中，δ（lx）是一个二分值，表示映射指标变量，定义为

链路负载率定义为

与节点负载率的定义类似，Bmax（lx）为每条链路的总带宽容量，B（lx）为剩余带宽资源。

链路带宽限制表示为

式中，φni（x）为业务映射指标变量，表示为

因此，最小化相应的惩罚函数，建立链路映射模型为

该数学模型是一个NP⁃hard问题，可以通过遗传优化算法求解。本文提出的GLMA算法流程如算法2所示。

算法2基于遗传算法的链路映射算法流程

其中，个体表示一个可行的VN划分方案，种群表示一组个体形成的集合，基因表示一个虚拟节点。用长度为I（虚拟节点个数）的串表示问题的解，即染色体。基于遗传算法的链路映射方案执行过程如下：首先，输入虚拟网络GV＝（NV，LV），物理网络GS＝（NS，LS）。 采用自然数编码，自然数在0到z之间排序，不同的排序方式表示不同的路径选择，每条染色体都是一种映射方案。其中，为了使初始种群在整个解空间中均匀分布，采用部分随机方法生成初始种群。在适应度函数方面，染色体的适应度越大，其性能越好。因此，将目标函数转化为适应度函数

式中，fc为染色体c的适应度。选择操作采用的是轮盘赌选择法［13］，适应度值越好的个体被选择概率越大。在利用轮盘赌选择策略时，首先需要解决的是如何将适应度值转化为选择概率。具体步骤如下：

（1）累加种群的适应度值，并将累加值作为分母。

（2）将每个个体的适应度值作为分子，得到每个个体被选择的概率。

（3）制作轮盘，将每个个体所得到的被选择概率设定为在圆盘上所占份额。

（4） 随机产生一个［0，1］区间内的随机数，若该随机数小于或等于个体的被选择的概率，则该个体被选择。

选择单个个体的概率为

交叉操作采用的是单点交叉算法［14］，在个体染色体中随机设置一个交叉点，然后在该点相互交换两个父母染色体的部分染色体。例如式（22）中两个相同长度的二进制串。

单点交叉包括选择一个均匀分布的随机整数k∈［1，length（A1）－1］， 在A1和A2间交换k＋1到length（A1）之间的各变量，如果k＝3，则A1和A2变为

变异操作采用的是反转变异算子［15］，在父代中随机选择两个点，然后反转之间的部分，则交叉后的A1和A2变为

变异后转向个体适应度评价，若迭代次数未达到最大值，则开始新的循环，最终得到惩罚函数的近似最优解。

3 仿真与分析

本文使用Matlab对所提的基于遗传算法的链路映 射 算 法 （Genetic⁃algorithm based Mapping Algorithm，GLMA）进行仿真，并在服务接收率、可靠性、时延等方面与负载均衡随机映射算法（Load⁃balancing Random Mapping Algorithm，LRMA）［16］和贪婪资源映射算法（Greedy⁃based Resource Mapping Algorithm，GRMA）［17］进行比较。 其中，LRMA 算法通过最优化网络负载均衡，选择最短路径进行链路映射，GRMA算法是一种经典的虚拟网络映射算法，通过贪婪算法选择最高可靠性链路进行虚拟网络映射。

仿真场景是模拟我国江苏省智能电网通信网络。根据智能电网差异化的业务需求，本文将电力业务根据时延敏感度分为5类（见表1）：电网控制和保护类业务、配电自动化、分布式能源、交互式音频和视频、用电信息采集。利用 GT⁃ITM（Georgia Tech Internetwork Topology Models）工具生成参数如表2和表3所示，其中，虚拟网络有8个节点和15条链路，虚拟网路的到达时间为Poisson分布，生存周期为指数分布，最长等待时限在0.1～1之间均匀分布。本文分别对5类业务进行了模拟，业务请求数量分别设为 5，10，15，20，25，30，35。 为保证实验的准确性，进行10次实验，取结果的平均值。

表1 电力业务指标

表2 节点资源参数表

表3 链路资源参数表

图3为3种算法服务接收率的比较，其中基于GLMA的服务接收率最高。其次是LRMA。GRMA由于没有考虑基础设施网络的负载均衡，导致服务接收率较低，LRMA算法没有对流量进行优先级排序，不能保证服务获得高可靠性链路，业务接收失败率较高。而本文的GLMA结合了LRMA和GRMA的优点，针对业务的不同优先级提供不同的链路，根据业务不同属性参数分配不同可靠性的链路，在业务接收率方面具有优异的性能。

图3 服务接收率的比较

图4为3种算法的惩罚函数比较，其中基于GLMA的惩罚函数最小，其次是LRMA，GRMA的惩罚函数值最大。这是因为GRMA没有考虑到负载均衡问题，导致惩罚函数中的负载率过大；而LRMA由于没有进行优先级排序，导致惩罚函数中的时延过大。本文的GLMA充分考虑到了业务的时延敏感特性，在业务请求层和链路映射层都加入了时延属性，同时也将负载率纳入主要影响因素之中。已知惩罚函数越小，服务可靠性越高，因此，GLMA具有最高的服务可靠性。

图4 惩罚函数比较

图5为3种算法平均时延对比，其中基于GLMA的平均时延最小，且随着请求的不断增加，平均时延的增长幅度也较小，而其他两种算法的平均时延增加较为明显。这是因为GLMA算法考虑了窗口中待映射请求的等待时间属性参数和时延敏感度，对等待时间较长的请求优先映射，同时，考虑了链路映射过程中的时延问题，而其他两种算法则未考虑时延因素。因此，GLMA算法在平均时延方面明显优于其他两种算法。

图5 平均时延对比

4 结束语

本文提出了基于电力业务时延敏感度和服务可靠性的虚拟网络映射方案，从电力业务的时延需求出发，提出了基于时延敏感度的业务请求排序，缩短虚拟网络请求的等待时间并提高虚拟网络请求接收率；然后，将拓扑属性和相邻节点重要性作为排序参数，对节点进行排序；最后，在链路映射层，构建了基于链路时延和链路负载比方差的可靠性惩罚函数，提出了基于遗传算法的链路映射算法，得到最优映射链路。仿真结果表明，所提方法保障了电力业务的时延和可靠性需求，同时有效提高了虚拟映射请求接收率。