面向5G-ICN切片的分层缓存策略*

戈丽平，周金和

(北京信息科技大学 信息与通信工程学院，北京 100101)

0 引 言

5G网络具有控制平面和用户平面彻底分离，灵活转发等功能，并且能够实现网络服务协调和控制功能的灵活部署[1]，为部署网络切片提供了保障。网络切片可以支持不同服务需求的业务场景[2]，能够显著降低移动虚拟网络运营商(Mobile Virtual Network Operator,MVNO)运营过程中的资本支出和运营成本[3]。文献[4]结合5G网络和网络切片技术，制定了缓存策略和资源分配策略，最大化了5GC-RAN的系统收益。文献[5]提出了5G核心网切片，为增加网络运营商的收入，综合虑了延时约束，确定了联合缓存分配和延时控制的资源分配方案(Joint Cache Allocation and Delay Control,JCADC)。虽然上述研究考虑了不同网络需求条件下的缓存资源分配方案，降低了延时，但缺少对缓存成本的研究。为降低缓存的成本，文献[6]在5G网络中部署端到端网络切片，考虑了核心网和无线接入网的不同成本需求，依据请求数量定义了缓存成本函数，并利用排序算法解决分层缓存资源共享问题。文献[7]为降低端到端延时，结合缓存资源和带宽资源需求，探讨了基站间的协作缓存问题。虽然上述研究考虑了在网络节点中加入缓存功能，但缺乏对传输能耗的考虑。

多接入边缘计算(Multiple-Access Edge Computing,MEC)具有网络缓存功能，能够实现和核心云之间的灵活调度，促进了信息中心网络(Information-Centric Network,ICN)服务与5G网络切片的结合。文献[8]为降低用户和远程云之间的传输能耗，提出了协作式的MEC缓存分配和计算分载方案。文献[9]提出了一种基于ICN的分层主动缓存方法，根据用户未来需求和移动性确定缓存的位置。ICN不再以主机为中心，而是以内容为中心，并提供网络内置缓存功能[10]。文献[11]基于名称在域内部署ICN切片，使用户可以在最近的地方获得缓存内容，降低了传输能耗。文献[12]从ICN组网和服务提供的角度提出了一个ICN切片框架，优化了虚拟内容放置的问题，节省了传输能耗。上述研究提高了运营商收益，但缺少对缓存成本和传输能耗的综合考虑。

博弈论与其他方法相比，能够考虑一个或多个实体在特定约束条件下对局中利益相关方的优化策略，能够综合考虑多个制约因素，如文献[13]利用博弈论研究了内容提供商和不同ICN实体间缓存和定价的相互作用。文献[14]为激励内容提供商主动缓存，提出了一种基于博弈的激励性主动缓存机制。文献[15]通过使用纳什讨价还价博弈来关注延迟和能耗的联合优化，保证了良好的公平性。因此，博弈论可以用来研究切片中内容提供者和网络运营商之间的资源分配问题。

然而，博弈中的缓存分配问题需要进一步优化。为实现资源的有效分配，文献[16]利用基于灰狼算法的群体智能算法实现功率的优化分配，为解决资源分配提供了方向。为提高问题的准确性，文献[17]利用遗传放置算法(Genetic Placement,GP) 解决了缓存资源的分层放置问题,有效降低了用户请求的时延，提高了缓存放置的准确性，但需要耗费较长的计算时间。

目前对于缓存问题有以下难点：首先，运营商收益问题不容忽视；其次，忽略了MVNO的部署成本和传输成本的联合问题；最后，缓存分配的位置问题有待解决。因此，本文提出了一种基于改进遗传算法的联合缓存成本和传输能耗的缓存策略。

1 网络架构和系统模型

1.1 网络架构

ICN网络切片系统架构如图1所示，其中，MVNO为ICN切片提供者，内容提供商(Content Provider,CP)为网络切片资源消耗者。网络切片中ICN用户设备(ICN User Equipment,ICN-UE)通过gNB接入网络，由MEC或ICN网关(ICN Gateway,ICN-GW) 提供缓存资源。ICN-GW离用户较远，MEC更靠近用户。由核心控制器执行本文算法，选择最优缓存位置和缓存数量。用户平面功能(User Plane Function,UPF)提供分流功能[18]，如果MEC缓存了内容，则直接由MEC提供，否则由原路径返回。

图1 ICN切片系统架构

1.2 系统模型

对于任一CP，排名为k的内容出现的概率服从Zipf分布，表示为p(k)=z/kβ，z为常数，β为Zipf指数。若CP放置kn个流行内容表示为

(1)

ICN-MVNO的支出综合考虑了内容传输所花费的能耗和内容缓存花费的成本：

cost=λ1a+λ2w。

(2)

式中:cost为ICN-MVNO的总支出；w为传输能耗花费；a为缓存成本花费；λ1为缓存成本所占的权重；λ2为传输能耗所占的权重。

1.3 一主多从的Stackelberg博弈

博弈主要分为博弈方、策略、利润函数三个要素。Stackelberg博弈能够实现不同参与者利润的最大化，主导者是ICN-MVNO，策略是为每单位缓存资源制定价格p。博弈跟随者是CP，策略是请求缓存资源的数量kn。

当ICN-MVNO缓存一定的资源后，由于CP购买缓存资源需要一定的成本，CPn的收入会随着缓存能力的增加而放缓，αn为每个CPn的成本系数，CPn的收入可以表示为

(3)

ICN-MVNO的收入为CP所花费的成本，支出是缓存kn数量的资源时的缓存成本以及传输成本：

(4)

(5)

式(5)中：an为缓存到MEC所需花费的成本；xn,j∈{0,1}；xn,CN∈{0,1}代表的是CPn是否会选择mj节点和CN节点。

在这个过程中，综合考虑了内容缓存和能量消耗，目的是选择一个能够满足CP需求并且综合费用低的节点。

1.4 纳什均衡解存在性及唯一性

Stackelberg博弈可以通过找出其完美的纳什均衡来获得。本文在给定ICN-MVNO的定价后，CP间属于非合作博弈，每一个理性的参与者都不会有单独改变策略的冲动[19]时，即存在纳什均衡解。

证明：给定缓存资源的价格下，博弈参与者数量有限，式(3)中函数的一阶偏导数为

(6)

根据公式(12)和公式(13)的一阶导数定理，公式(6)得到的极大值点为

(7)

公式(3)的二阶偏导数可计算为

(8)

(9)

公式(4)得到最优缓存数量下关于p的一阶偏导函数见公式(10)，二阶偏导函数见公式(11)。αn>0,λ1,λ2≥0,an,aCN>0,kn>0,0<β<1,p>0时每个参与者的策略空间的集合都是欧氏空间有界闭集合，且利润函数在其策略空间上连续且公式(3)和公式(4)关于kn和p的函数是准凹的，所以博弈存在纳什均衡解。

xn,CNkn(λ1aCN+λ2wb))=

(10)

(11)

(12)

(13)

2 资源分配算法

2.1 分层缓存位置求解

遗传算法(Genetic Algorithm,GA)可以用来解决博弈问题以及0-1背包问题[20]，直接对结构对象操作，具有更好的全局寻优能力，相较于其他的启发式算法得到的解集更加趋近于全局最优。图2展示了GA算法的流程图。为了防止丢失个体，本文使用“精英选择”策略将在进化过程中最好的个体直接复制到下一代和“相似性交叉方法”使相似性较低的染色体交叉作用。

图2 遗传算法基本步骤

CP内容缓存的位置无法确定，是NP问题，其中costs和costt分别为成本和能耗的联合成本函数：

cost(kn)=xn,jcosts+xn,CNcostt。

(14)

遗传算法选择最优的个体，或者达到最大迭代次数，称之为一代[21]。本文将公式(4)作为适应度函数。xn,j表示为染色体的基因，表示的是第n个CP是否将内容缓存在第j个节点，最大迭代次数为It，种群数目为I。染色体表示为Xi=(xn,1,xn,2,…,xn,M+1)，种群X=(X1,X2,…,XI)。如果对应个体没有节点响应CP的请求，则应该重新初始化个体，直到满足条件。如果一个CP与多个存储点配对，则应选择利润最大且满足约束条件的节点缓存；否则，应重新初始化该个体。算法对于Xi被选择用于繁育后代的概率为

(15)

轮盘每圈的概率随机生成的，ξw∈U(0,1)，当满足PPw-1<ξw

根据相关性矩阵区分染色体，将相似性较低的染色体进行交叉操作，防止产生不必要的染色体[24]：

(16)

突变概率Pm的典型值在0.005%～0.05%的范围内。在此之后进行修订操作，移除不符合要求的染色体，如果CP尚未向ICN-MVNO发送与新个体中一种或多种个体相对应的请求，则该个体将被上一代种群中的相应个体替换。

改进的遗传算法(Elite Correlative Genetic Algorithm,ECGA) 综合考虑了内容传输能耗和缓存成本，并将ICN-MVNO的利润函数作为该算法的适应度函数，通过对个体进行精英选择、相关性交叉、突变、修订操作，获得最佳的缓存分配位置X。ECGA算法(算法1)伪代码如下所示：

Input:初始种群X,种群数量I，缓存节点集合w+1，CP集合S,ICN-MVNO的价格p,缓存容量集合S,最大种群迭代次数It。

1 根据公式(7)和初始价格p,获得缓存数量请求列表kn；

2 for it=1,2,3,…,It do

3 通过公式(4)和公式(5)获得Xi-1的适应度确定适应函数R和可行的解决方案。

4 根据公式(15)计算个体选择概率PX

5 根据概率PX选择个体

6 ifRIM(Xi-1)>RIM(Xi) then

7X=X+Xi-1

8 根据公式(16)，计算相关性矩阵

9 根据相关性矩阵交叉操作

10 根据Pm突变

11 修订并消除重复个体

13 end if

14 it=it+1

15 end for

2.2 博弈求解过程

博弈首先评估CP的缓存情况，输入初始价格p。初始化后，CP间竞争缓存资源，ICN-MVNO寻找最优价格。算法1根据ICN-MVNO的收益寻找收益值最大的点，并将每个节点对应的收益值放入存储库中，以便下一步计算使用。当价格不随缓存数量和位置的变化而变化或达到最大迭代次数时，博弈迭代(Iteration of Game,IToG)算法(算法2)停止并输出最优的价格和缓存数量。算法2的伪代码如下：

Input:CP集合N，缓存节点集合M+1，缓存资源请球数量kn,缓存容量集合S,最大迭代次数T。

1 根据博弈跟随者CP请求的资源数量确定博弈领导者ICN-MVNO的初始价格p；

2 whilet≤Tdo

当前，人工智能正处于高速发展阶段，其发展方向、发展边界尚不清晰，导致规范什么和怎么规范并无统一认识。尽管争论不断，但人工智能在很多方面开始受到监管，相关法律法规正在孕育。这些努力不一定是制定规范人工智能发展的普遍原则，更多的是对涉及人工智能技术应用的具体领域的规范，如隐私保护、网络安全、反商业和金融欺诈行为，以及交通、健康、就业等领域的安全保障等。大多数规范并不特别适合人工智能，随着人工智能的发展还在不断引发新的问题。可以认为，人工智能应用到哪里，人工智能引发的问题出现到哪里，人工智能的立法领域就应延伸到哪里。目前讨论来看，人工智能涉及的法律问题主要有以下几个。

3 ICN-MVNO确定需要缓存CP的资源数量为kn

4 ICN-MVNO根据算法1确定缓存节点位置Xi

7 else

8 根据算法1重新定义缓存节点

9 end if

10 ICN-MVNO通过缓存位置和数据重新定义缓存价格

12p←p′

13t=t+1

14 CP评估是否更改放置缓存资源的数量

17 end while

18 end if

19 end while

2.3 复杂度分析

假设算法1收敛于itst，复杂度为O(I3)，因此，ECGA算法的复杂度为itst×O(I3)。ECGA算法考虑了交叉特性，计算复杂度略高于贪婪算法复杂度以及灰狼算法的复杂度，但在牺牲复杂度的同时提高了最优解的精度，并且ECGA算法复杂度低于GP算法的复杂度T×O(G×K3×I4)。博弈策略X和p不断更新，直到达到纳什均衡解，因此算法2的复杂度为O(t)。

3 仿真与分析

3.1 仿真设置

本文使用的计算机配置为Intel(R) Core(TM) i5-6300HQ CPU @2.30 GHz和16RAM，并对Matlab R2018b的仿真结果进行了分析。网络环境由3个CP、3个MEC和1个ICN-GW组成，sj=100，ICN-GW的容量设置为MEC的2倍。与贪婪搜索(Iteration Greedy Search,IGS)算法[25]、JCADC算法和随机的选择节点分配缓存(Random Cache Allocation,RCA)算法[26]进行了对比。最初将λ1、λ2设置为等值，再根据试错机制进行调整[27]。仿真参数设置为aCN=3,ε=0.001,β=0.8,an设置为定价p的一半,ωa=10-8J/b,ωb=2.7×10-8J/b[28]。

3.2 可行性分析

为了验证算法的可行性，将ECGA算法与GP算法进行对比，如图3所示。由于个体需要相关性交叉操作，本文算法在开始时的收敛速率低于GP算法。由图可知，本文算法遗传代数收敛于第300代，与收敛于400代的GP算法相比收敛性较好，具有较快的计算时间，复杂度较低。

图3 优化过程

3.3 收益变化情况

图4表明随着迭代次数的增大，ICN-MVNO和CP的利润函数收敛到定值。ICN-MVNO和CP的博弈是参与者策略交互的过程，经过迭代后能够使得缓存分配收敛到纳什均衡。还对比了αn=30和αn=20的收益情况，ICN-MVNO和CP的收益值都随着αn的升高而增大。

图4 不同αn下的ICN-MVNO和CP收益变化情况

图5分析了权重因子λ1和Zipf分布指数β对ICN-MVNO的收益的影响。在β相同时，可以看出λ1=0.3比λ1=0.5的收益高，表明运营商更加关注传输能耗花费。当λ1相同时，β=0.8时的收益高于β=0.3时的收益，表明内容提供商放置的内容越流行，ICN-MVNO的收益越高。

图5 λ1和β对ICN-MVNO的收益的影响

图6说明了不同算法下ICN-MVNO的收益变化情况。IGS算法考虑了传输能耗，但缺少对资源成本的研究，降低了运营商的收益，得到稳定解(60,270.349)。JCADC算法综合考虑了核心网节点缓存成本和延时需求，在一定程度上增加了内容传输的能耗，得到稳定解(60,249.842)。本文算法稳定解为(60,360.244)，与IGS、JCADC算法相比，运营商的收益分别提高了32%、44%，且收敛性最好。

图6 不同算法的ICN-MVNO收入对比

3.4 能量节省率

图7对比了本文算法和IGS、JCADC和RCA的能量节省率，可以看出IGS、JCADC、ITOG算法的节省率随着CP数量的增多而上升，在CP等于4时达到最大。由图中可以得出，本文算法与IGS、JCADC算法相比，传输能耗分别节省了5%、11%。由于算法在开始寻找最优解时需要耗费大部分能量，因此，IGS具有较高节省率。而JCADC算法考虑了延时的控制能力，能量节省率较低，并且下降速率较快。

图7 不同算法的能量节省率对比

3.5 博弈迭代解

图8说明了ITOG求得的纳什均衡解。ICN-MVNO制定一个较高缓存价格p，CP根据资源价格p调整购买缓存资源的数量，两个参与者不断更新策略，最终得到稳定解(4.7,69)，即CP和ICN-MVNO之间达到纳什均衡。

图8 纳什均衡解

4 结束语

本文考虑了具有ICN-GW和多个MEC的5G-ICN切片分层缓存架构，通过博弈方法最大化ICN-MVNO和CP的利润函数，并根据ITOG算法得到最佳缓存数量和价格。在解决分层问题时，本文利用ECGA算法确定分层缓存分配方案。该算法具有较高的有效性以及较好的缓存资源分配能力，能够降低传输能耗和缓存成本，提高运营商的收益。未来为综合考虑运营商收益和延时需求，我们将对MEC节点的部署和动态重配置作进一步研究。