雾计算中基于古诺博弈的协作缓存优化算法

涂 亮，徐 雷

(南京理工大学 计算机科学与工程学院，江苏 南京 210094)

0 引 言

在移动互联网快速发展的时代，大批智能移动设备访问互联网资源。显然，传统的云计算在处理如此海量的资源请求时必然会出现诸多问题，例如：高时延、移动支持性差等。雾计算可看作云计算的延伸，在云端内容中心和用户之间建立的新架构。雾计算同样可以为用户终端提供相关的计算、内容存储、请求转发等服务。由于雾计算通过将服务器节点部署距离用户终端相对较近的地理位置，因此时延更低、对移动性支持更好[1]。

移动互联网作为人们日常生活必不可少的部分，对音乐、视频、图片等流媒体内容的获取和发布已经成为当今互联网的主流模式。据Cisco流量统计数据预测：在2014至2017年间，全球的IP流量增长超过4倍。预计2019年，视频内容流量将达到网络流量80%[2]。面对流媒体内容指数式增长，移动智能设备受限于其存储容量、电池容量、无线网络信号等因素，移动终端用户从云端内容中心获取的内容十分有限。那么利用雾服务器节点对经过其的请求内容进行计算并存储，可以大大降低用户终端获取该流行内容的时延、减少网络带宽资源的浪费。

目前，在已有对雾计算在移动互联网中的应用[3-5]更多的是关注于数据在网络边缘的放置。例如，文献[6]提出一种在网络边缘节点进行计算、存储的方法；文献[7]提出对于请求相同内容的用户终端划分于同一个边缘节点，即对于单个边缘节点只存储同一种请求内容。显然，该方法不适合内容种类繁多的情况；文献[8]介绍了一种通过边缘节点自愿提供存储空间的高度集中式控制缓存方式，集中式控制方式对于地理位置分散、请求内容种类过多的情况就显得不合适。

此外，传统的缓存算法很少会对链路代价、传输时延等网络实际因素进行考虑。由于不同的请求内容情况所产生的链路开销是不一样的，所以文中提出一种基于古诺博弈的链路最小代价的协作缓存算法(link minimal cost，LMC)。该算法利用雾服务器节点对请求内容的链路代价进行实时计算，评估该请求内容对整个缓存系统的影响，以便决定是否对其进行缓存。最后对比仿真效果，该算法在命中率、链路消耗参数上表现更好。

1 雾计算中的缓存分析

本节将主要介绍雾计算中的协作缓存过程，并且对用户终端进行内容请求时产生的链路代价进行分析，同时引入节点之间协作存储的方法来提高存储效率。

1.1 缓存系统模型

雾计算中的缓存架构主要分为三部分：云端内容中心、雾计算节点集群、用户终端。现假设在仅有一个云端内容中心的情况下，雾计算服务节点集群由F={F1,F2,…,FN}组成，其中Fi(i∈1,2,…,N)表示第i个雾服务器节点。U={U1,U2,…,UM}表示用户终端集合，其中Uj(j=1,2,…,M)表示第j个用户终端。

假定在给定的地理范围，根据范围内的用户终端数M和雾服务器节点数N划分各用户终端所属雾服务节点，即用户的请求将首先经过其所属雾服务器节点。考虑到用户终端间的移动性和社交传播影响，文中采用基于社交关系的划分方式[9]为用户终端划分雾服务器节点，用户终端Ui和用户终端Uj的社交关系实体Ei,j的计算方式如下：

(1)

其中，μ为比例因子；λi,j∈[0,1]，表示用户终端Ui和Uj的影响因子；a和b分别表示内容信息和地理位置的影响因子；Di,j∈{0,1}表示用户终端Ui和Uj是否在影响范围内。

文中将雾服务器的缓存大小C划分为协作和非协作两部分(如图1所示)。其中非协作部分C(1-R)用于存放该雾服务器节点自治域内访问频率较高的内容，而协作部分CR通过控制协作比例R来缓存整个缓存系统中访问频率较高的内容。协作比例R的取值过小将导致整个缓存系统中的存储冗余，取值过大将导致用户终端通过其他雾服务器获取内容开销增大。文中将围绕选择一个合适的协作比例R来达到减少链路开销的效果。

图1 雾服务器的缓存空间组成

1.2 链路开销分析

从上一节模型结构可知，用户终端获取内容来源主要有3种情况：云端内容中心、其归属的雾服务器节点、其他的协作部分。文中用户终端通过不同内容源访问到内容的单位链路传输开销有所不同。单位链路传输开销为网络链路中1比特(Byte)数据传输需要的额外消耗。假定Pi,j为雾服务器节点Fi和Fj的单位开销；Pi为其自治域内的单位开销；雾服务器节的点与云端内容中心之间的单位开销为Pc，其中满足Pc>Pi,j>Pi[10]。

下面分别讨论从上述3种情况获取内容的开销：

(1)雾服务器节点没有存储内容v。用户终端将只能通过云端内容中心获取内容，则在一个缓存周期内请求该内容的总开销为：

(2)

(2)部分雾服务器节点缓存了内容v。用户可以直接从其归属雾服务器节点访问到内容v。若其归属雾服务器节点未存储内容v，则从距离其最近的雾服务器节点获取。那么获取该内容的总开销为：

Pi)

(3)

其中，N{Nv}表示没有存储内容v的雾服务器节点的集合；save(Nv)为存储了内容v的雾服务器节点个数；Ps为雾服务器节点的单位数据的存储开销；min(Pi,j)为雾服务器节点之间的最小链路开销。

(3)各雾服务器节点均存储了内容v。用户可以直接在其归属雾服务器节点访问到内容v，那么获取该内容总开销为：

Ptotal=save(N)PsCv

(4)

其中，save(N)为整个缓存系统雾服务器节点个数。

1.3 缓存价值计算

(5)

min(Pi,j)+Pi]-PsCv

(6)

2 链路最小代价缓存算法

前一节详细介绍了雾计算中协作缓存的组成部分及缓存价值的计算。本节将主要介绍基于古诺博弈的链路最小代价缓存算法的实现，该算法由两部分组成：缓存决策部分和缓存替换部分[11-12]。

2.1 缓存决策算法

决策流程如图2所示。各个雾服务器节点通过协作部分存储系统中较为流行的内容，云端为整个雾计算提供请求内容、计算、协作调度，其中关于古诺博弈的协作调度实现将在下一节介绍。

图2 缓存决策流程

2.2 缓存替换算法

在用户终端Ui所需的内容v在其所属的雾服务器节点Fi中没有存储时，雾服务器节点Fi依据内容v缓存价值决定存储内容、如何更换其缓存空间中已存储的内容，其中文中假定缓存块大小和内容块大小相同(下同)。

假设用户终端Ui请求的内容v返回至雾服务器节点Fi，若雾服务器节点Fi非协作部分有空余缓存空间，则直接存储内容v。若非协作部分已经没有缓存空间，则继续查找协作部分是否还有缓存空间。若协作部分还有空间，则将非协作部分缓存价值最大的内容移置协作部分，同时更新云端中关于协作部分的内容信息，之后将非协作部分中缓存价值最大的内容更换为内容v。

否则对比内容v和非协作部分缓存价值最小的内容，若缓存价值大于最小内容，则执行替换操作，否则不执行替换。

2.3 古诺博弈的协作调度

在1.1节中描述了各雾服务器节点的协作部分组成缓存空间，可以为该协作缓存空间建立一个市场垄断模型。即当不同雾服务器节点均未存储所需的同一个内容时，那么可以将该请求内容看作商品。为了保证整个缓存系统中该内容不重复存储，各雾服务器节点均希望能就近存储其缓存空间中，那么节点之间便通过竞争以获得最大的收益。最后由云端内容中心将该内容下发到雾服务器节点，这样可以使得整个缓存系统的链路开销达到最小，这就是典型的古诺博弈。

运用古诺博弈，设定每个雾服务器节点均为出价者。每个出价者给出其对该请求内容的出价pi，云端内容中心作为唯一的内容源提供者，对各雾服务器的出价进行权衡。因此，得到相应的定价函数[13]如下：

(7)

其中，a,b和τ均表示正常数；P={p1,p2,…,pN}表示不同雾服务器节点的出价集合。令τ≥1，即表明该定价函数为凸函数，从而确保了云端内容中心将相同的请求内容下发到使整个缓存系统链路开销最小的雾服务器节点上。

从1.2节链路开销分析可得各个雾服务器节点节省的链路开销为：

Lsave=Lnocache-Lcache=

(8)

(9)

其中，ωK表示请求内容的概率总和。

3 仿真分析

为了验证提出的基于古诺博弈的链路最小代价算法(LMC)的有效性，选择了传统缓存算法：最近最小使用(least recency user，LRU)、先来先服务(first in first out，FIFO)、随机(random)算法作为对比算法。假定所有用户终端所有请求均满足Zipf分布[13]。同时，为了评价算法的性能，定义了三个参数作为参照：命中率、缓存时延、缓存链路开销。其中仿真参数如表1所示。

表1 仿真参数具体设置

从图3可知，各算法平均缓存命中率在σ增加时均有所增加。这是因为当内容流行度增大，用户终端对流行内容的请求概率增大，雾服务器节点对请求内容的替换频率降低，命中率增加。文中提出的LMC算法相比传统算法，通过雾服务器之间的协作缓存，使得热点内容停留在缓存中的时间更长，缓存命中率也随之增加。

图3 缓存命中率对比

从图4、5可知，各算法的平均缓存时延和链路开销随着Zipf参数σ的增加均减少。因为参数σ的增加，用户终端请求同一内容的概率增大，相应的内容可以直接从本地雾服务器节点获取，减少了从云端内容中心获取内容而产生的传输时延和链路开销。文中提出的LMC算法相比传统算法，通过协作缓存，丰富了整个缓存系统的内容种类，从而比传统算法拥有更低的时延和更小的链路开销。

图4 缓存时延对比

图5 缓存链路开销对比

同理，该算法对于协作比例R、雾服务器节点个数F的参数影响均优于传统算法的仿真结果，由于篇幅有限，不作论述。

4 结束语

文中首先对雾计算中的缓存系统架构进行介绍，同时提出协作缓存对缓存优化的必要性。提出的基于古诺博弈的链路最小代价算法充分考虑了不同内容的流行度、地理位置、各自治域的链路代价等因素，各协作部分通过古诺博弈，充分利用协作缓存空间，从而减少缓存系统中缓存相同的内容，增加了内容丰富度。仿真效果表明，LMC算法在缓存命中率、链路时延、链路开销的表现更好。