一种多域物联网服务功能链放置优化方法

本发明属于物联网网络，具体涉及一种多域物联网服务功能链放置优化方法。

背景技术：

1、随着5g技术的快速应用和物联网(internet of things，iot)的蓬勃发展，越来越多的物联网用户试图访问自己的特定物联网服务。因此，近年来，为了满足各种服务需求，大量多样化的物联网服务急剧涌现。网络功能虚拟化(network functionvirtualization，nfv)被认为是物联网服务的一种很有前途的技术推动者。网络功能虚拟化以软件的形式用虚拟网络功能(virtual network function，vnf)取代了传统的硬件相关功能。在支持网络功能虚拟化的物联网网络中，每个请求服务的流量被引导按照给定的顺序流经一系列特定的虚拟化网络功能，从而形成服务功能链(service function chain，sfc)。在传统的物联网网络中，网络功能严重依赖于专用硬件，导致物联网网络功能，同时实现物联网服务的灵活弹性部署。

2、在多域物联网网络中部署服务功能链时，由于资源争用，虚拟化网络功能可能会分散放置在不同的地理节点上。在这种情况下，服务功能链请求的数据流被引导从源节点跨多个物联网域传输到目的节点。因此，这将导致端到端延迟和运营代价成本的显著增加。在这种情况下，可能会违反服务请求的qos和sla需求，从而无法保障物联网用户的服务qoe。如今，随着6g时代的到来，为物联网用户提供超低延迟、高可靠性的服务迫在眉睫。然而，传统的服务功能链在单域物联网中的部署方法很难适应大规模的物联网网络，也很难满足快速增长的物联网服务需求。因此，设计一种高效的多域物联网服务功能链放置优化方案，以满足多元化服务需求，保障用户的服务质量，是非常必要的。

技术实现思路

1、本发明的目的在于提供一种多域物联网服务功能链放置优化方法，最小化服务成本，可以满足多元化服务需求，保障用户的服务质量。

2、为实现上述目的，本发明提供了一种多域物联网服务功能链放置优化方法，包括以下步骤：

3、s1、建立感知的服务功能链放置rqsp问题的系统模型；

4、系统模型具体包括网络模型、服务功能链请求模型、服务延迟模型、服务代价成本模型；

5、s2、建立基于生成式遗传算法的启发式放置优化gap算法；

6、gap算法以多域物联网g、服务功能链请求集r、种群规模大小np、精英比例pe、最大迭代次数iter、交叉概率pc和变异概率pm为输入，最终输出最优放置解。

7、优选的，所述步骤s1中，建立网络模型具体为，

8、a、将一个多域物联网网络建模为一个无向图，

9、g＝(v，e)

10、式中，v是物联网节点的集合，e是物联网链路的集合；

11、b、假设物联网边缘节点的可用资源容量大于物联网终端节点的可用容量；

12、c、将每个物联网域建模为一个无向图，

13、gi＝(vi，ei)

14、式中，vi是该物联网域的中节点，ei是该物联网域链路的集合；

15、d、考虑物联网节点的cpu资源和物联网链路带宽资源；

16、给定一个物联网节点vi，j∈vi，用ci，j表示其可用的cpu资源容量；用bi，j，m，n表示物联网链路的可用带宽资源ei，j，m，n∈e；用和分别表示物联网节点vi，j的cpu资源和物联网链路ei，j，m，n的带宽资源的单价；定义di，j和di，j，m，n分别表示物联网节点vi，j的处理延迟和物联网链路ei，j，m，n的传输延迟。

17、优选的，所述步骤s1中，构建服务功能链请求模型具体为，

18、a、设r表示一组服务功能链要求，将第i个服务功能链请求表示为，

19、ri＝(igi，egi，sfi，di)，

20、式中，igi表示服务功能链请求的入口节点，egi表示服务功能链请求的出口节点，sfi表示服务请求对应的服务功能链，di表示服务功能链路请求所能容忍的最大端到端延迟；

21、b、给定一个服务功能链sfi，将其建模为一个有向图，

22、

23、式中，fi是虚拟网络功能节点的集合，li是逻辑虚拟链路的集合；

24、将fi，j表示为第j个虚拟网络功能，li，j，h表示虚拟化网络功能fi，j和fi，h之间的虚拟链路；

25、c、设tf表示虚拟网络功能类型的集合；设ci表示第i类虚拟网络功能所需的cpu资源tfi∈tf，bi，j，h表述虚拟链路li，j，h所需的带宽资源。

26、优选的，所述步骤s1中，构建服务延迟模型具体为，

27、将一个服务功能链的整体服务延迟认为由物联网节点的处理延迟和物联网链路的传输延迟组成；放置在物联网节点vm，n上的虚拟网络功能fi，j∈fi的处理延迟表示为，

28、

29、式中，ci，j为虚拟网络功能fi，j所需要的cpu资源需求；cm，n为物联网节点vm，n的cpu资源总量；dm，n为物联网节点vm，n的处理延迟。

30、优选的，所述步骤s1中，构建服务代价成本模型具体为，定义放置服务功能链sfi所产生的服务代价为，

31、

32、式中，φi表示服务功能链sfi放置所产生的资源消耗代价，表示服务功能链sfi放置失败所产生的惩罚代价，ψi表述服务功能链sfi的数据流跨域传输所产生的跨域运营代价。

33、优选的，所述步骤s1具体步骤为，

34、s11、定义决策变量；给定一个多域物联网g和一个服务功能链sfi，找一个从有向图到无向图g的最优映射；

35、s12、优化目标；将服务功能链放置在多域物联网中，满足资源和服务质量qos需求的约束；

36、优化目标表示为，

37、

38、

39、

40、

41、

42、式中，μ表示单位惩罚代价成本，η表示权重系数，表示服务功能链sfi所占用的物联网域的总数量；

43、s13、满足约束条件；

44、a、物联网服务功能链的每个虚拟网络功能只能放置在一个物联网节点上，不能拆分放置在多个物联网结点上，

45、

46、b、确保任何类型的虚拟网络功能fi，j都属于虚拟网络功能类型集中的一个类型，

47、

48、c、物联网节点vm，n的剩余cpu资源容量大于或等于部署的虚拟网络功能fi，j的cpu资源需求，

49、

50、d、保障放置在同一物联网节点vm，n上的所有虚拟网络功能所需的cpu资源的总和不超过该物联网节点vm，n的cpu资源总量，

51、

52、e、确保对于任何一个服务功能链请求sfi，其每个虚拟链路只能映射到一个物联网链路上，而不是被拆分映射到多条物联网链路，

53、

54、f、保障对于任意物理链路em，np，q，映射到该链路上的所有虚拟链路的带宽资源需求不能超过其链路带宽资源总量，

55、

56、g、保障网络服务质量，对于任意的服务功能链请求sfi，必须满足其端到端服务延迟约束，

57、

58、h、确保对于每个服务功能链sfi，其虚拟网络功能依赖关系约束不会被违反，

59、

60、优选的，所述步骤s13中，二元决策变量还需要满足以下约束条件，

61、

62、

63、

64、

65、

66、γi∈{0，1}

67、式中，表示服务功能链sfi中的虚拟网络功能fi，j是否被放置在物联网节点vi，j上；表示服务功能链sfi中的虚拟链路li，j，h与物理链路em，np，q的之间的映射关系；表示虚拟链路li，j，h是否通过从源节点s到目的节点t的路径表示任意两个虚拟网络功能节点fi，j和fi，h之间的依赖关系；表示虚拟网络功能fi，是否为tfk∈tf类型；γi表示服务功能链sfi的最终部署状态。

68、优选的，所述步骤s2具体步骤为，

69、s21、建立基于贪婪策略的种群初始化gpi算法；

70、a、对于每个虚拟网络功能fi，j∈fi，首先在入口节点igi所在的物联网域中搜索满足虚拟网络功能fi，j的cpu资源需求约束的候选物联网节点；

71、若最终无法找到合适的物联网节点，则由于物联网节点的资源容量有限，服务功能链请求将被拒绝；

72、b、在确定候选物联网节点后，按照资源单价的升序对其进行排序；

73、c、虚拟网络功能优先考虑资源单价最低的物联网节点，在确定虚拟网络功能放置的物联网节点后，基于dijkstra算法进行虚拟链路映射；

74、d、如果不能找到满足资源和延迟约束的路径，则该服务功能链请求将被拒绝；

75、s22、设计有效的双亲个体选择机制；采用精英保留和轮盘赌联合选择erjs策略来实现双亲个体选择；

76、a、首先选择当前一代中具有最高适应度函数值的前k个个体作为精英个体，并从当前一代的剩余其他个体中选择其他双亲个体；

77、b、将目标函数定义为适应度函数，个体xi被选择为双亲个体的概率计算如下，

78、

79、c、在确定适应度函数后，计算当前一代中所有个体的适应度函数值，并按适应度函数值的大小对其进行升序排序；

80、d、为每个个体xi生成一个随机数r；若pi+1≤r≤pi，则选择个体xi为双亲个体；

81、e、重复a-d步骤，操作选择出所有的双亲个体；

82、s23、对双亲个体进行交叉运算；

83、a、采用统一的交叉策略来执行交叉操作，生成一个随机数rc∈[0，1]来决定两个后代个体和双亲个体之间的遗传继承关系，表示为，

84、

85、式中，spi[j]表示后代个体spi的第j个基因，pri[j]表示双亲个体pri的第j个基因；

86、b、给定两个双亲个体pr1和pr2，假设一条染色体上的遗传总数为ng，交叉概率为pc，对于两个后代个体sp1和sp2的当前第j个基因；

87、若rc≤pc，则后代个体sp1可以继承双亲个体pr1的第j个基因的遗传；否则，sp1继承双亲个体pr2的第j个基因，子代个体sp2继承双亲个体pr1的j个基因；

88、c、在生成两个新子代个体之后，进一步检查新子代的可行性；如果两个新的子代个体不可行，直接用它们的父代替换它们，以保障服务功能链请求的qos需求；

89、d、重复执行步骤a-c双亲个体选择与交叉操作，直到生成新一代中的所有子代个体；

90、s24、执行变异变异运算操作；

91、对于子代个体中的每个基因，生成一个随机数rm∈[0,1]来确定遗传是否发生改变，表示如下，

92、spi[j]←v,if rm≤pm

93、s25、最优解的确定；

94、a、当算法达到最大迭代次数时，交叉和变异操作完成；

95、b、计算当前一代中所有个体的适应度函数值，并将适应度函数数值最好的个体作为最优解；

96、c、将最优染色体个体解码，构造最优虚拟化网络功能放置方案，并在优化虚拟网络功能放置的基础上，利用dijkstra算法完成链路映射操作；

97、d、基因最终的网络服务功能链放置优化方案计算其总的服务代价成本。

98、本发明的有益效果：

99、(1)本发明将rqsp问题建模为一个混合整数线性规划模型，目标是服务成本最小化，同时考虑资源分配和qos需求约束。服务代价成本由三部分组成，包括成功部署网络服务功能链所产生资源消耗代价成本、网络服务功能链部署失败的惩罚代价成本和跨域部署网络服务功能链所产生的额外运营成本；

100、(2)本发明证明了rqsp问题是一个np难问题，并求解优化模型，其中提出了一种基于贪婪策略的种群初始化机制和一种精英和轮盘赌联合选择策略，以加快算法收敛并减少运行时开销；

101、(3)本发明基于两个真实的中等规模和大规模网络场景进行了广泛的性能评估模拟实验；仿真结果表明，所提出的gap算法在服务接受率、服务成本、服务器利用率和平均服务延迟等多个性能指标上优于对比算法。

102、下面通过实施例，对本发明的技术方案做进一步的详细描述。

技术特征：

1.一种多域物联网服务功能链放置优化方法，其特征在于，包括以下步骤：

2.根据权利要求1所述的一种多域物联网服务功能链放置优化方法，其特征在于：所述步骤s1中，建立网络模型具体为，

3.根据权利要求1所述的一种多域物联网服务功能链放置优化方法，其特征在于：所述步骤s1中，构建服务功能链请求模型具体为，

4.根据权利要求1所述的一种多域物联网服务功能链放置优化方法，其特征在于：所述步骤s1中，构建服务延迟模型具体为，

5.根据权利要求1所述的一种多域物联网服务功能链放置优化方法，其特征在于：所述步骤s1中，构建服务代价成本模型具体为，定义放置服务功能链sfi所产生的服务代价为，

6.根据权利要求1所述的一种多域物联网服务功能链放置优化方法，其特征在于：所述步骤s1具体步骤为，

7.根据权利要求1所述的一种多域物联网服务功能链放置优化方法，其特征在于：所述步骤s13中，二元决策变量还需要满足以下约束条件，

8.根据权利要求1所述的一种多域物联网服务功能链放置优化方法，其特征在于：所述步骤s2具体步骤为，

技术总结
本发明公开了一种多域物联网服务功能链放置优化方法，该方法包括以下步骤：S1、建立感知的服务功能链放置RQSP问题的系统模型；S2、建立基于生成式遗传算法的启发式放置优化GAP算法。本发明采用上述一种多域物联网服务功能链放置优化方法，最小化服务成本，可以满足多元化服务需求，保障用户的服务质量。

技术研发人员：张闯闯,崔光海,李亦昊,张淑宁,刘莉,杨洪勇,何强,成汶霖
受保护的技术使用者：鲁东大学
技术研发日：
技术公布日：2024/9/23