一种边缘计算环境下的安全服务与功能服务联合编排方法转让专利
申请号 : CN202110649247.6
文献号 : CN113259175B
文献日 : 2021-09-24
发明人 : 郭得科 , 郑龙 , 秦煜东 , 罗来龙
申请人 : 中国人民解放军国防科技大学
摘要 :
权利要求 :
1.一种边缘计算环境下的安全服务与功能服务联合编排方法，其特征在于包括以下步骤：
A、建立一个具有 个异构边缘站点和一个远程云的边缘系统，所述边缘站点通过回程网络连接，使得用户请求被非本地边缘站点服务，从边缘站点i到j的传输延迟被表示为 ，设 ， ，每个边缘站点与无线接入点相关联；当边缘系统无法满足用户请求时，用户请求将通过互联网迁移到远程云上处理， 表示边缘站点i的资源容量，所述资源为一个包含计算、带宽和存储容量的三维向量；
B、服务提供商在边缘系统部署功能服务，用以满足用户需求；服务提供商在边缘系统部署安全服务，用以检查用户请求存在的安全风险；功能服务的集合表示为F，安全服务表示为 ；
C、用户通过接入点向边缘系统发送请求，设有U个用户请求， ， 表示需要功能服务f的用户请求集合，每个用户请求都与它需要的功能服务和它到达的边缘站点相关联，如果用户请求没有在边缘系统上调度，它将被传输到远程云处理；
D、设立高效安全部署问题，所述高效安全部署问题的目标是在安全部署模式下，获得在服务延迟上界内处理的最大用户请求数，表示为在约束条件下的整数规划模型， ，表示用户请求u是否在边缘站点被处理；
约束条件包括，
安全约束，为了提供安全保护，在边缘上处理的用户请求必须由安全服务处理，；
处理能力约束，对于安全服务和功能服务的每个VNF链实例，处理能力约束保证调度给它的用户请求不会超过它的处理能力，；
资源约束，对于每个边缘站点，放置在其上的所有VNF所需的总资源不得超过其资源容量，
；
完整性约束，对于每个VNF链实例，其中包含的所有VNF都应该放在某个边缘站点上，以确保链正常工作，
；
QoS约束，对于边缘系统处理的每个用户请求，应该由其所需的功能服务来处理，，
定义为功能服务f的VNF链实例 所引起的延迟，，
和 分别表示服务i的VNF链中的第一个与最后一个VNF， 为实例j中从到 的传输时延，
表示用户请求u到达和离开的边缘站点， 为从 到实例i的 的传输时延，为实例i的 到 的传输时延，，
延迟约束描述为，
；
决策变量约束，
；
其中， 表示服务j部署的VNF链实例的数目， 表示用户请求u是否被相应功能服务的第i个VNF链实例处理， 表示用户请求u是否被安全服务的第i个VNF链实例处理， 表示服务f的第i个VNF链实例中的v是否部署在边缘站点n； 的定义为：边缘站点集合； 的定义为：用户请求集合，需要服务 的用户请求的集合； 的定义为：功能服务集合，安全服务； 的定义为：在服务i的VNF链中，VNF的集合与链路的集合；
的定义为：边缘站点i的资源容量； 的定义为：VNF 的资源需求与处理容量； 的定义为：功能服务i的延迟上界； 的定义为：边缘站点i与j的传输时延； 的定义为：用户请求u是否在边缘站点被处理的标志符； 的定义为：用户请求u是否被安全服务的第i个VNF链实例处理，是否被相应功能服务的第i个VNF链实例处理的标志符； 的定义为：服务f的第i个VNF链实例中的VNF 是否部署在边缘站点 的标志符；的定义为：服务i部署的VNF链实例的数目；
E、使用启发式算法求解高效安全部署问题的最优解。
2.根据权利要求1所述的边缘计算环境下的安全服务与功能服务联合编排方法，其特征在于：步骤B中，
每个服务都具体实现为一个特定的VNF链，VNF为虚拟网络功能，该链由一个有序的VNF序列组成； 表示服务f的VNF链中的链路集合，对于服务i的VNF链， 表示该链的处理能力，即这条链可以同时处理的最大用户请求数， 表示包含在服务f的VNF链中的VNF集合，表示v的资源需求，部署服务是指确定相应VNF链的实例数，以及每个VNF链实例的嵌入方案。
3.根据权利要求2所述的边缘计算环境下的安全服务与功能服务联合编排方法，其特征在于：服务提供商为用户提供的不同种类的功能服务具有延迟上界；在安全部署模式中，延迟上界把安全服务所消耗的时间包含在内；设VNF处理用户请求所花费的时间是恒定的，总的延迟中不确定的部分仅与边缘站点之间的传输延迟有关。
4.根据权利要求1所述的边缘计算环境下的安全服务与功能服务联合编排方法，其特征在于：所述高效安全部署问题为NP难问题。
5.根据权利要求2所述的边缘计算环境下的安全服务与功能服务联合编排方法，其特征在于：步骤E中，使用增量资源分配策略作为启发式算法的整体框架；
所述增量资源分配策略包括，
部署方案，用于记录每一个服务是如何部署的，包含每一个VNF链实例的嵌入方案；
调度方案，用于记录每一个用户请求分别被安全服务和功能服务的哪一个VNF链实例所处理；
当边缘系统资源不足时，增量资源分配策略终止；使用VNF链嵌入算法为每个服务的VNF链生成嵌入方案 ；嵌入方案记录了一个VNF链实例的每一个VNF放置在哪一个边缘站点上；VNF链嵌入方法表示为函数 ，如果当前资源足够嵌入服务i的VNF链，将 的值置为 ，否则置为 ，如果当前资源无法放置任何服务的VNF链，那么这个过程将停止；函数 用于计算增益和调度方案，具有最大增益的VNF链被实际嵌入，嵌入新链后，相关参数将更新；函数 是以贪婪的方式实现的，对于每个尚未调度的用户请求，函数 检查每个安全服务和相应的功能服务的VNF链实例构成的实例对，如果该用户请求能够被其中任意一个实例对在延迟上界内处理，则将该用户添加到 中去，将该实例添加到 中去。
6.根据权利要求5所述的边缘计算环境下的安全服务与功能服务联合编排方法，其特征在于：资源分配次数为恒定的k，每次都会触发 函数和 函数S次，S是所有服务的数量，每次运行 函数需要 次计算，U是用户请求数， 函数每次运行需要 次计算，T是VNF链的VNF数，N是边缘站点数，总计算复杂度为。
7.根据权利要求2所述的边缘计算环境下的安全服务与功能服务联合编排方法，其特征在于：步骤E中，使用VNF链嵌入方法具体描述框架中服务部署的步骤，每个VNF的放置位置有N种，根据评估指标对这 个选择中的每一个进行评分；设 表示VNF链中的第t个VNF， 表示在边缘站点i上放置 的评分；放置 的评分是基于放置的评分计算的；根据 的每个选择计算 ，并选出其中得分最高的一个，即， 是当 放置在站点k上时， 放置在站点i上的评估指标；对于每个边缘站点 计算 ，并记录其对应的 的选择，用最高的分数做为最后的选择，然后回溯到 ；
在嵌入VNF链时，具有资源限制和传输延迟两个约束；要嵌入的VNF链有T个VNF，并将第i个VNF表示为 ，所有的VNF都有相同的N种选择进行放置，它们被描述为 ，表示VNF被放置在边缘站点i上；
计算矩阵M来记录每个边缘站点的可用资源，M的第i行表示选择 ，第j列表示在每种选择下边缘站点j的剩余资源， 表示第i行和第j列的交点，VNF链中的VNF按顺序更新矩阵M
；
定义资源指标 来评估在边缘站点i上放置 的选择，设其前一个VNF放置在边缘站点k上，其中 是放置 所需的资源，是一个小于最小资源单位的正值，用以防止或 导致的错误，
；
设 表示在 选择 的情况下 选择 的概率， 表示从边缘站点i到边缘站点j的延迟，
；
对于没有前一个VNF的第一个VNF，将延迟指标计算为 ，其中 表示从初始边缘站点到边缘站点i的延迟，并且初始边缘站点是具有最多相应请求的站点，‘
对于第一个VNF，资源指标被计算为 ，矩阵M和资源指标是动态更新的，通过回溯得分最高的最终选择，生成嵌入方案。
8.根据权利要求7所述的边缘计算环境下的安全服务与功能服务联合编排方法，其特征在于：当出现恶意用户请求时，估计恶意用户请求在所有用户请求中所占的比例 ，当恶意用户请求是非自适应的时候，使用观察到的经验平均值作为估计值；将功能服务的总处理能力提高 ，然后调度用户请求，当调度到同一VNF链的正常请求超过了处理能力，则随机挑选超量的请求迁移到云。
9.根据权利要求8所述的边缘计算环境下的安全服务与功能服务联合编排方法，其特征在于：根据延迟和资源指标对VNF的每个选择进行评分，具有以下3种模式，
1）负载均衡模式，资源指标值随着边缘站点的可用资源增加而升高；
2）集中模式，根据资源利用率设计资源指标，站点被选择放置一个新的VNF的概率随着VNF放置数量增加而升高；
3）QoS模式，根据延迟来计算评分，当边缘站点有足够的资源用于放置新的VNF时，将资源指标的值设置为1，否则该值将设置为0。
说明书 :
一种边缘计算环境下的安全服务与功能服务联合编排方法
技术领域
背景技术
们的网络服务从远程的云卸载到网络边缘，这对延迟敏感或计算密集型的服务有很大增
益。
硬件转换为基于软件的模块。这些软件模块被称为虚拟网络功能（VNFs），他们可以快速灵
活地在商用服务器上安装或卸载。使用NFV，服务提供商可以提供由VNF链实现的网络服务，
该链通常由一系列有序的VNF组成。在这种情况下，网络服务处理用户请求的过程，就是用
户请求被VNF链中的VNF按顺序处理的过程。在实际应用中，同一服务的不同vnf可以部署在
网络中的不同设备上。
提供服务，减少维护费用，提高资源利用率。由于对用户和服务提供商都有益处，在网络边
缘上部署服务（VNF链）的研究变得越来越有吸引力。无论是服务提供商向网络运营商租用
边缘资源，还是建立自己的边缘站点，现有的边缘资源都是有限的、异构的，给服务部署带
来了很大的挑战。因此，现有的大多数工作都从成本或QoS的角度关注边缘资源的有效利
用。
来部署功能服务来为用户提供服务。我们认为这种假设是不实际的。首先，网络中可能总是
有恶意用户试图窃取信息或干扰VNF的正常运行。其次，一些边缘站点是由微型服务器或过
时的边缘设备组成的，而这些设备无法保证高级别的安全性。因此，在没有考虑安全保护的
情况下部署功能服务是存在较大风险的。这就是为什么生产网络总是需要防火墙、深度包
检测、入侵检测等安全服务的原因。换句话说，安全服务和功能服务应该共存于网络边缘。
只有经过安全服务的检查，数据流才能进入功能服务。当用户请求爆炸时，这两种服务可能
会竞争有限的边缘资源。
一类型的服务，即单独部署安全服务或功能服务。然而，这些方法不适用于我们的情况。原
因是他们未能在这两种服务之间取得平衡。因此，需要一种新的编排方案来解决安全服务
与功能服务的联合部署问题。
发明内容
利用率。
为 ，设 ， ，每个边缘站点与无线接入点相关联；当边缘系统无法满足用户
请求时，用户请求将通过互联网迁移到远程云上处理， 表示边缘站点i的资源容量，所述
资源为一个包含计算、带宽和存储容量的三维向量；
务表示为 ；
点相关联，如果用户请求没有在边缘系统上调度，它将被传输到远程云处理；
， ，表示用户请求u是否在边缘站点被处理；
理能力，即这条链可以同时处理的最大用户请求数， 表示包含在服务f的VNF链中的VNF集
合， 表示v的资源需求，部署服务是指确定相应VNF链的实例数，以及每个VNF链实例的嵌
入方案。
间是恒定的，总的延迟中不确定的部分仅与边缘站点之间的传输延迟有关。
VNF链实例处理， 表示服务f的第i个VNF链实例中的v是否部署在边缘站点n；的
定义为：边缘站点集合； 的定义为：用户请求集合，需要服务 的用户请求的集合；
的定义为：功能服务集合，安全服务； 的定义为：在服务i的VNF链中，VNF的集合与链路
的集合； 的定义为：边缘站点i的资源容量； 的定义为：VNF 的资源需求与处理容量；
的定义为：功能服务i的延迟上界； 的定义为：边缘站点i与j的传输时延； 的定义
为：用户请求u是否在边缘站点被处理的标志符； 的定义为：用户请求u是否被安全
服务的第i个VNF链实例处理，是否被相应功能服务的第i个VNF链实例处理的标志符； 的
定义为：服务f的第i个VNF链实例中的VNF 是否部署在边缘站点 的标志符；的定义为：服
务i部署的VNF链实例的数目。
站点上；VNF链嵌入方法表示为函数 ，如果当前资源足够嵌入服务i的VNF链，
将 的值置为 ，否则置为 ，如果当前资源无法放置任何服务的
VNF链，那么这个过程将停止；函数 用于计算增益和调度方案，具有最大增益的
VNF链被实际嵌入，嵌入新链后，相关参数将更新；函数 是以贪婪的方式实现的，
对于每个尚未调度的用户请求，函数 检查每个安全服务和相应的功能服务的VNF
链实例构成的实例对，如果该用户请求能够被其中任意一个实例对在延迟上界内处理，则
将该用户添加到 中去，将该实例组合添加到 中去。
函数每次运行需要 次计算，T是VNF链的VNF数，N是边缘站点数，总计算复
杂度为 。
于放置 的评分计算的；根据 的每个选择计算 ，并选出其中得分最高的一个，即
， 是当 放置在站点k上时， 放置在站点i上的评估
指标；对于每个边缘站点 计算 ，并记录其对应的 的选择，用最高的分数做
为最后的选择，然后回溯到 ；
， 表示VNF被放置在边缘站点i上；
新矩阵M
防止 或 导致的错误，
服务的总处理能力提高 ，然后调度用户请求，当调度到同一VNF链的正常请求超过了处理
能力，则随机挑选超量的请求迁移到云。
要求，同时将此模式建模为一个优化问题。本发明开创性的研究安全服务和功能服务联合
部署问题，并提出了一种启发式算法来解决它，在执行时间和平均服务请求数方面能够取
得较好的效果。
附图说明
具体实施方式
为 ，设 ， ，每个边缘站点与无线接入点相关联；当边缘系统无法满足用户
请求时，用户请求将通过互联网迁移到远程云上处理， 表示边缘站点i的资源容量，所述
资源为一个包含计算、带宽和存储容量的三维向量；
务表示为 ；
点相关联，如果用户请求没有在边缘系统上调度，它将被传输到远程云处理；
， ，表示用户请求u是否在边缘站点被处理；
理能力，即这条链可以同时处理的最大用户请求数， 表示包含在服务f的VNF链中的VNF集
合， 表示v的资源需求，部署服务是指确定相应VNF链的实例数，以及每个VNF链实例的嵌
入方案。
的，总的延迟中不确定的部分仅与边缘站点之间的传输延迟有关。
VNF链实例处理， 表示服务f的第i个VNF链实例中的v是否部署在边缘站点n；的
定义为：边缘站点集合； 的定义为：用户请求集合，需要服务 的用户请求的集合；
的定义为：功能服务集合，安全服务； 的定义为：在服务i的VNF链中，VNF的集合与链路
的集合； 的定义为：边缘站点i的资源容量； 的定义为：VNF 的资源需求与处理容量；
的定义为：功能服务i的延迟上界； 的定义为：边缘站点i与j的传输时延； 的定义
为：用户请求u是否在边缘站点被处理的标志符； 的定义为：用户请求u是否被安全
服务的第i个VNF链实例处理，是否被相应功能服务的第i个VNF链实例处理的标志符； 的
定义为：服务f的第i个VNF链实例中的VNF 是否部署在边缘站点 的标志符；的定义为：服
务i部署的VNF链实例的数目。
站点上；VNF链嵌入方法表示为函数 ，如果当前资源足够嵌入服务i的VNF链，
将 的值置为 ，否则置为 ，如果当前资源无法放置任何服务的
VNF链，那么这个过程将停止；函数 用于计算增益和调度方案，具有最大增益的VNF
链被实际嵌入，嵌入新链后，相关参数将更新；函数 是以贪婪的方式实现的，对于
每个尚未调度的用户请求，函数 检查每个安全服务和相应的功能服务的VNF链实
例构成的实例对，如果该用户请求能够被其中任意一个实例对在延迟上界内处理，则将该
用户添加到 中去，将该实例组合添加到 中去。
放置 的评分计算的；根据 的每个选择计算 ，并选出其中得分最高的一个，即
， 是当 放置在站点k上时， 放置在站点i上的评估
指标；对于每个边缘站点 计算 ，并记录其对应的 的选择，用最高的分数做
为最后的选择，然后回溯到 ；
， 表示VNF被放置在边缘站点i上；
新矩阵M
防止 或 导致的错误，
理能力提高 ，然后调度用户请求，当调度到同一VNF链的正常请求超过了处理能力，则随
机挑选超量的请求迁移到云。
单元和9个单元分别表示100个边缘站点和9个功能服务。每个用户轨迹都转换为一个用户
请求。对于每个用户轨迹，边缘站点网格中的出发位置转换为用户请求到达的边缘站点，功
能服务网格中的目的地位置转换为所需的功能服务。边缘站点的资源容量是根据相应格子
内的出租车数目设置的。两个边缘站点之间的传输延迟是基于用户轨迹在其相应格子间的
平均旅行时间来设置的。功能服务的延迟边界是基于目的地为相应单元的用户轨迹的平均
旅行时间来设置的。对于每个实验，对随机抽取的用户请求进行10次实验，并对结果取平均
值。所有的算法都是用python3.6.9实现的，并在配置为ubuntu18.04、2.4GHz Xeon‑
Skylake处理器和2GB内存的云服务器上运行。
其他的解决方案生成另外3种算法。具体情况如下。
时间的影响。请求数都设置为200。我们可以看到，所有3种算法的执行都随着站点规模的增
加而增加。我们的算法比其他两个算法快一点。图2示出了不同请求数下的执行时间。站点
数目设置为50。我们可以看到，当请求数超过100时，执行时间趋于稳定。这是因为边缘站点
上的资源耗尽，算法终止。
其他两种算法，与FAS+VCE算法相比，当站点数为30时，差距可达31%。图4示出了服务请求的
平均数目随着请求数目的增加而增加。请求数的增加为提高嵌入式VNF链的利用率提供了
更多的可能性。本发明的算法与基准测试之间的差距可以达到35%（当请求数为150时，与
FAS+VCE相比）。
同规模的边缘站点下进行了实验，即5个站点、10个站点和15个站点。用户请求数目是50。
0.04和0.08。另一方面，本发明的算法更高效。它求解所花费时间远远少于1秒，而OEA的执
行时间边缘站点数量的增加而显著增长。OEA的执行时间最多达到了VCEA执行时间的7678
倍。
50。随着服务类型数的增加，平均服务的请求数减少。本发明的算法优于其他两个基准算
法，但是当服务类型增加到12和16时，其结果仍然分别下降了12.4%和16.5%。原因是服务种
类的增加导致需要每种服务的请求数减少，因为总请求数是固定的。因此，VNF链的利用率
更有可能降低。
12]。图6显示了VNF链长度的影响。显然，VNF链越长，边缘上可以服务的用户请求就越少，因
为当VNF链的长度增加时，它需要更多的资源来服务相同数量的请求。当长度范围扩大1.5
倍和2倍时，本发明的算法的结果分别下降了21.4%和50.4%，仍然优于其他两个基准算法。
VNF链的数量。图7展示了实验结果。当边缘站点上的资源减少一半时，服务的平均请求数量
将显著减少。
上界减小为0.6倍和0.8倍时，算法的结果分别降低了24.7%和17.4%。
期比例，通过在功能服务中增加虚拟容量来优化算法。将通用算法和优化算法分别表示为
GA和OA。我们比较了GA和OA所处理的包含恶意和正常用户请求的总用户请求数（标签中后
缀为total），以及正常用户请求数（标签后缀为normal）。我们将恶意用户请求的比例从5%
逐步提升为50%。结果如图9所示。可以看出，通过优化算法计算出的处理请求数随着恶意请
求所占比例的增加而增加。这是因为OA中针对恶意请求只部署安全服务，从而充分利用了
GA中浪费的资源。当然，整个请求中的恶意程度越高，在边缘上处理的正常请求就越少。OA
和GA下正常请求的处理次数均随恶意请求比例的增加而减少。OA在处理总请求数和正常请
求数方面分别比GA高出20.6%和18.1%。