异构边缘网络中内容扩散策略及优化

薛寒星，尤佳莉，王劲林

(1.中国科学院声学研究所国家网络新媒体工程技术研究中心,北京 100190； 2.中国科学院大学,北京 100190)

0 引 言

边缘网络作为骨干网络的补充，如何利用其中海量终端设备的空闲资源来缓解骨干网络的压力得到了广泛关注。因为网络中大部分的流量集中在少部分热门内容上[1]，通过内容扩散系统[2]将少部分热门内容的副本部署在边缘网络中。用户直接从终端中获取低时延的内容服务的同时，骨干网络的负载压力也会得到极大的缓解。例如在智能路由器[3-5]或蜂窝网络中的用户设备(UE)[6-7]中部署内容副本。网络边缘拥有多种类型的终端设备，它们可能拥有不同的处理能力和存储空间,设备的可用带宽和设备间的链路状态(时延、丢包率等)也会存在差异[8]；同时，CNNIC的统计报告[9]表明不同地理区域、不同职业、不同年龄和不同文化程度的用户对内容的访问都存在差异；所以边缘网络是一个由能力、带宽和兴趣异构的边缘设备构建的网络。在边缘网络构建和内容扩散中如果对所有的设备一视同仁，忽略它们之间的异构性，很容易造成内容服务的瓶颈。因此，异构边缘网络中，如何合理地构建网络拓扑并根据用户兴趣实现针对性的内容扩散对边缘网络的性能有很大的影响。

本文对异构边缘网络中的内容扩散策略进行研究，主要贡献包括：

1)提出一种基于节点簇的分层网络拓扑结构和基于内容流行度的覆盖率需求。在此基础上设计一种去中心化的内容扩散策略，充分利用边缘设备的资源实现热门内容副本的快速扩散。

2)针对边缘设备的异构性，从扩散目标、缓存节点选择、传输策略这3个方面对内容扩散策略进行优化。首先提出基于指数的时间衰减的方式刻画设备兴趣，进一步提出基于簇的兴趣特征的自适应覆盖率调整策略。基于该策略扩散完成后的边缘网络可以在设备兴趣异构的场景下提供稳定的内容服务。然后，综合考虑设备能力、兴趣和服务负载，提出一种启发式的缓存节点选择策略，均衡设备服务负载差异的同时，提高设备在本地获取内容服务的概率。最后，数据传输部分，提出覆盖率感知的传输内容选择策略和传输负载感知的接收节点选择策略，减少系统完成扩散所需的时间。

1 相关工作

本文研究异构的边缘网络中内容的扩散，包括节点能力、带宽异构下的内容扩散、用户兴趣的刻画、基于用户兴趣的分发和预取等。

针对节点能力的异构，已有学者在不同场景下提出针对能力异构的网络拓扑构建的策略。Srivatsa等人[10]设计了分层的网络拓扑，将能力较高的节点部署在上层网络。Fesci-Sayit等人[11]在构建组播树的过程中将高带宽的节点放在更高的数据层来接收低时延的视频流。Fortuna等人[12]提出了节点优先与高带宽和低时延的节点建立连接。所以，网络拓扑构建中针对设备能力异构的主要思路是将高能力节点放置在网络中更重要的位置。本文在选择簇的管理节点时也会优先选取带宽较高和能力较强的节点。

很多学者在节点带宽异构的情况下对内容的快速扩散进行了研究。Langer等人[13]在带宽异构下研究数据分块策略来加速内容传输速率。Meng等人[14]在流传输模型下，通过分割节点的高带宽来减少多文件的扩散所需时间。Ku等人[15]在完全二叉树中选择拥有更高比例的未缓存内容的子节点优先接收内容。Bhat等人[16]在广播和多播中提出了优先选择最快的节点(Fast Node First, FNF)来接收数据。Silva等人[17]提出了一种带宽感知(Bandwidth Aware Scheduler, BAS)的节点选择策略，节点被选择来接收内容的概率正比于节点的带宽。Abeni等人[18]修正了ELp[19]策略，加入带宽特征来选择合适的接收节点。Wang等人[20]提出了综合节点的带宽和内容的稀有情况来选择合适的接收节点。可以发现相关研究的主要思路即以较大的概率优先选择带宽较高的节点进行内容扩散，尽早利用这部分节点的带宽资源。然而这些策略都忽略了节点传输的负载，可能会导致部分带宽略低的节点资源的浪费，所以本文提出优化的基于节点传输负载的接收节点选择策略。

针对用户兴趣异构的内容服务研究主要包括2个部分：用户兴趣的刻画和基于兴趣的内容预取和缓存管理。在兴趣刻画和挖掘方面，第一种策略是基于用户设备已缓存的内容刻画兴趣，主要为语义网络的构建。Voulgaris等人[21]根据节点间拥有内容的相似性来构建语义网络，提高检索的成功率。另一种方式是通过用户的历史访问(检索)记录刻画用户的兴趣，进而进行内容的推荐和预取。在推荐系统中，Ding等人[22]提出了指数衰减的加权模型为不同时刻的用户行为赋予不同的权重，并基于用户的兴趣来预取内容。Shen等人[23]在社交网络中提出了基于兴趣的数据块预取，降低用户观看视频的启动时延。Xu等人[24]通过分析观看记录刻画用户的兴趣，进一步通过协同过滤方法来选出预取内容。不同于已有的研究，本文的内容扩散策略的本质是热门内容的扩散，节点间的邻居关系更侧重于相似的网络状态和较近的网络距离来提供低时延的内容服务。所以本文仅基于用户的兴趣来指导内容扩散中的副本数量和放置位置。

2 兴趣刻画和异构边缘设备组网策略

2.1 用户兴趣刻画

因为边缘设备有内容感知的特性，可以获取并记录用户请求的相关信息。假设网络中存在的内容种类集合为M，RNi,j,x表示节点i对j类内容在距离当前时刻x天的请求数量。设备会记录并定时更新前k天中的每类内容在每天的请求数量，见公式(1)。矩阵中的每一行代表一天中节点i对每类内容的请求数量，不同的行代表不同天的请求情况。同时，研究表明用户的兴趣可能会随时间而改变[22]。所以基于用户对不同内容的请求数量，本文提出一种基于指数的时间衰减的方式来刻画用户的兴趣，具体计算见公式(2)。其中，Ii,j表示节点i对内容j的兴趣系数，可以看出x越大，距离当前时刻越远，相应的请求情况对兴趣系数的影响越小。通过归一化计算，节点i对j类内容的兴趣系数为NIi,j，见公式(3)。节点将定期更新每类内容的的兴趣特征，具体形式为{NIi,1,…,NIi,j,…,NIi,m}。

(1)

(2)

(3)

2.2 异构边缘设备的组网策略

相对于扁平的覆盖网络，层次化的网络具有更好的扩展性，因此本文使用层次式的覆盖网络来组织异构的边缘设备。因为在内容扩散策略中，节点的带宽对内容扩散的速率和最终的服务性能有非常大的影响，所以本文在网络构建中以节点带宽能力的异构为主。具体的网络拓扑构建流程为：

1)设备根据物理拓扑的近似性进行分簇，防止出现逻辑边缘网络与物理网络失配的问题。簇内的边缘设备之间建立全连接的无结构网络。

2)每个簇选取带宽最高的节点作为管理节点，其余为普通节点。在多个设备拥有相同带宽时，优先选择拥有更强处理能力的设备。管理节点维护簇内所有边缘设备的信息，包括设备的带宽、兴趣和已缓存副本。管理节点基于簇内节点的兴趣特征计算簇的兴趣特征，CNIC,j表示簇C对j类内容的兴趣系数，计算过程见公式(4)：

(4)

3)不同簇的管理节点之间构建无结构的簇间连接网络。图1中展示了分层网络结构的示例。

图1 分层的网络结构

3 去中心化的内容扩散及优化策略

3.1 层次式网络中的去中心化扩散

3.1.1 内容扩散目标

内容扩散策略的扩散目标是将热门内容的副本扩散在每个簇内，使得节点可以在簇内直接获取热门内容的服务。本文首先将簇C在t时刻对内容j的覆盖率CC,j(t)定义为簇内j的副本数量与簇中所有节点数量的比值，计算见公式(5)。其中，xi,j(t)表示节点i在t时刻是否缓存了j，已缓存则xi,j(t)=1，否则xi,j(t)=0。管理服务器根据全局的内容请求情况为不同的内容设定相应的覆盖率需求，计算见公式(6)。其中，Cd(j)表示内容j的需求覆盖率，NRj表示内容j的请求数量，F表示系统中所有内容的集合。可以假设当内容在簇内的覆盖率大于需求覆盖率时，簇中该内容的副本数量足以向簇内节点提供就近的内容服务。

(5)

(6)

3.1.2 层次式网络中的去中心化内容扩散

针对分层网络拓扑和扩散目标，本文提出一种去中心化的内容扩散策略，具体扩散流程如下：

1)管理服务器随机选择某个簇的管理节点作为扩散内容j的种子节点，种子节点通过簇间覆盖网络将j的消息广播至所有簇的管理节点。

2)收到关于j的消息的管理节点确定的j覆盖率需求，根据「Cd(j)×|C|⎤确定簇内需要扩散的j的副本数量。根据缓存节点选择策略，管理节点在簇内选择相应数量的节点来缓存副本，同时告知已缓存j副本的源节点地址。

3)被选择的节点向已缓存j的内容源节点请求数据。内容源节点通过选择传输的内容和接收的节点来完成数据传输。在所有簇都满足扩散内容的覆盖率需求后，去中心化的内容扩散即完成。

图2 层次式网络内容扩散的实例

图2中展示了一个层次式网络中的内容扩散实例。覆盖率需求为0.2的内容的副本从簇1的管理节点扩散到4个簇中。

3.2 内容扩散的优化策略

3.2.1 扩散目标优化策略

如前文所述，不同的用户拥有不同的喜好，局部请求情况可能会与全局请求情况存在显著差异。所以根据全局请求情况设定的内容覆盖率需求与单个簇内的需求可能并不相同。因为管理节点维护了整个簇的兴趣情况，在簇内的内容扩散过程中，可以基于簇的兴趣情况对全局的覆盖率需求进行自适应的调整。本文提出一种基于兴趣的覆盖率调整策略(Interest-based Adjustment of Coverage, IAC)，具体见公式(7)，其中，Cd(C,j)表示调整后的簇C对内容j的覆盖率需求。内容j属于类别x，CNIC,x×|M|的数值反映的是簇C内节点对x类内容的平均喜好情况。CNIC,x×|M|>1表示簇内节点对x类内容的喜好超出平均值，所以适当上调覆盖率需求。反之则降低覆盖率需求。

Cd(C,j)=Cd(j)×CNIC,x×|M|

(7)

3.2.2 缓存节点选择策略优化

因为节点的带宽存在差异，相应提供服务的能力也不同。可以适当地在能力较高的节点上部署较多内容的副本来充分利用节点的带宽资源。同时，不同用户的兴趣也存在差异，在选择缓存节点时也需要考虑节点的兴趣特征。通过综合考虑节点的带宽、服务负载和兴趣，本文提出优化的综合缓存节点选择策略。

设BWmin表示向一个节点提供稳定视频服务的最小上行带宽。节点i的带宽等级BWLi的计算见公式(8)，实质是节点带宽与最小带宽的比值的取整，反映了节点可以同时向多少个邻居节点提供服务。带宽等级越高表示节点的能力越强。本文将节点的服务负载NLi定义为节点带宽等级和节点缓存副本数量的比值，计算见公式(9)，其中，xi(t)表示节点i在t时刻已缓存副本数。NLi反映了每个副本能分到的节点带宽，数值越大代表每个副本分到的带宽越多，节点的负载越小；反之则负载较大。

(8)

(9)

设NBWLi和NNLi分别表示归一化后的带宽等级和服务负载，归一化方式见公式(10)和公式(11)。定义每个节点对于内容j的综合指标为CIi,j，计算见公式(12)，其中，wBW、wNL和wI分别为节点带宽、服务负载和兴趣的权重。管理节点在选择节点缓存副本时，计算簇内所有节点对j的综合指标，并根据CIi,j的数值对节点进行降序排序，优先选择CIi,j数值较高的节点来缓存内容的副本。

(10)

(11)

CIi,j=wBW×NBWLi+wNL×NNLi+wI×NIi,j

(12)

3.2.3 数据传输策略优化

在设计的内容扩散策略中，每个节点可能会缓存多个内容的副本。相应地，缓存多个内容副本的节点会作为多个内容的源节点，会收到来自不同节点关于不同内容的请求。因为不同的节点拥有不同的带宽，内容源节点优先处理哪个内容的请求，并选择哪个节点来接收内容对扩散的速率和完成的时间可能会有很大的影响。因此，本文对传输内容和接收节点的选择策略进行优化。

在扩散完成后，内容的副本数量与其覆盖率需求成正比。覆盖率需求越高，内容的副本数量会越多，相应的扩散次数也更多。所以本文提出一种覆盖率感知(Coverage rate Aware, CA)的传输内容选择策略，即内容被选择传输的概率正比于其覆盖率需求。设CQNi,j表示向节点i请求内容j的节点集合，CCi(t)表示节点i在时刻t已缓存的内容集合，CSi表示节点i已完成缓存，并且当前传输请求数量大于零的内容集合，见公式(13)。节点i从已缓存的内容中选择内容j传输的概率见公式(14)，节点会大概率选择覆盖率需求更高的内容优先传输。

CSi={x|x∈CCi(t),|CQNi,x|>0}

(13)

(14)

相比于上传带宽较低的节点，上传带宽较高的节点对内容扩散的速率有更大影响。但是每个节点完成内容的缓存后也需要处理传输请求继续进行扩散，把过多的副本全部优先推送到高带宽节点上可能会超出它们带宽的能力范畴，部分拥有相对较低带宽的节点的资源却在空闲。因此，本文提出传输负载感知(Transmission Load Aware, TLA)的接收节点选择策略。节点的传输负载TLi定义为节点在当前时刻待处理的传输请求数量和节点带宽等级的比值，计算见公式(15)，其中，节点i在t时刻可以处理的传输请求是所有请求中已经完成缓存的内容的请求，即集合CSi中内容的请求。TLi数值越大，表示相对于节点的带宽，节点当前时刻需要处理的传输请求会更多，因此节点的传输负载越大。相应地，数值越小表示节点的传输负载越小。因此，在选择接收节点时，优先选择TLi数值较小的节点来传输内容，可以更充分地利用节点资源。

(15)

4 实验与分析

4.1 实验设计

本文在Peersim[25]仿真平台下实现整个异构网络中的内容扩散策略。仿真实验中，边缘网络的规模固定为2000，每个簇的规模大小限制在[50，100]范围内。其中，边缘设备的存储空间为8 GB。假设网络中共有10000个内容，每个文件大小为200 MB，对应的请求数量服从Zipf分布(α=1.0)。系统将在边缘网络中扩散最热门的100个文件，每个文件的覆盖率需求可以根据公式(6)计算得出。管理服务器的上行带宽为20 Mbps，为每一个扩散文件随机选择一个簇的管理节点作为种子节点，按照顺序依次将100个待扩散文件传输至各自的种子节点。

因为设备的上行带宽对内容扩散的速率有重要的影响，实验中所有设备的上行带宽分为3档，分别为1 Mbps、2 Mbps、4 Mbps，相应的设备数量分别占设备总数的比例为70%、20%、10%。BWmin的取值为0.85 Mbps，设备会采用先到先服务的策略，拒绝超出带宽能力的服务请求。实验中所有的内容被随机分为5个不同的类别。为了模拟用户的历史请求情况，根据内容的流行度排名和Zipf分布生成多轮请求，将所有的请求行为随机分发至网络中的设备。边缘设备根据请求情况，基于公式(3)和公式(4)计算对应的用户和簇的兴趣特征。

4.2 实验评估

本文设计的内容扩散策略与已有策略的区别在于：1)扩散对象不同，不同于已有的CDN网络或P2P网络中的扩散，本文设计的策略是在用户侧的智能终端构建的边缘网络中进行扩散；2)扩散目标不同，已有扩散策略是将热门内容的副本部署在CDN的边缘服务器，或将用户请求的内容扩散至终端设备，本文设计的策略是在设备的邻域内预部署热门内容的副本；3)扩散方式不同，本文设计的策略采用主动推送的方式将内容的消息扩散至网络，进一步采用拉取的方式进行数据的传输，整个扩散过程采用的是去中心化的方式实现快速的扩散。所以本文的扩散策略与已有策略存在较大区别，很难找到较为相近的策略或方法进行定量的比较，在实验评估部分使用优化后的策略与初始策略进行比较。

4.2.1 覆盖率调整策略评估

实验在扩散完成后会模拟用户请求峰值情况，即所有用户同时发起请求。其中，不同内容的请求数量服从Zipf分布。本文定义边缘网络的服务成功率为节点从簇内成功获取内容服务的请求数量与总的请求数量的比值，数值越高表示用户有更高的概率直接从簇内获取低时延的内容服务。因为实验中随机模拟用户的兴趣，本文在同等条件下进行了5次实验。图3展示了5次扩散完成后边缘网络的服务成功率，Default表示未调整的默认覆盖率。Upper Limit表示成功率的上限，即所有请求中关于已扩散内容的请求数量占的比例。由图3可知，基于IAC的边缘网络扩散完成后可以提供稳定的服务，并且服务成功率非常接近理论上限。覆盖率不调整的网络的服务成功率则在0.43～0.5之间波动。原因在于相对于全局的请求分布，在随机分配用户请求行为的场景中，局部请求情况可能与全局请求情况存在较大差异。部分簇对最热门的内容可能会拥有很高的请求比例，而其余簇对最热门的内容的请求比例可能并不高。所以在第4次实验中，当局部请求情况都很接近全局请求情况时，扩散不调整覆盖率需求也可以获取较高的服务成功率。但是在内容请求的分布不均的场景下，不调整覆盖率扩散的服务成功率会出现不同程度的下降。

图3 不同覆盖率需求下边缘网络的服务成功率

图4展示了5次实验完成后网络中的副本总数。未调整覆盖率时，多次扩散完成后的副本总数相同。但是基于IAC扩散完成后的内容副本数会出现小范围波动，同时比未调整要略高约1.3%。这是因为IAC是基于初始覆盖率需求进行调整，除了初始覆盖率需求较高的最流行的内容，其余内容的覆盖率调整幅度都很小。而且因为最流行的内容请求相对较多，整体调整后的覆盖率需求会略微上浮。图5展示了2个簇调整后的覆盖率需求和默认的覆盖率需求。图中可以明显地看出流行度排名靠前的内容的覆盖率波动较大，流行度排名靠后的内容的覆盖率需求波动幅度较小。较为流行的内容整体的覆盖率需求会略微增加。

图4 扩散完成后的副本总数

图5 调整后的覆盖率需求

4.2.2 缓存节点选择策略评估

在自适应调整覆盖率的基础上，本节对不同的缓存节点选择策略进行了比较，包括：随机选择(Random)、基于带宽和负载的选择策略(Bandwidth and Load， BL)、本文提出的基于带宽、负载和兴趣的选择策略(Bandwidth, Load and Interest， BLI)。BLI策略基于公式(12)，BL策略为公式(12)去除兴趣特征NIi,j。在实验中，不同特征的权重取值均相同。

本节将节点间的服务差异定义为节点缓存副本数和带宽等级的比值(NLi的倒数)的标准差，相应的数值越大表示节点间的负载越不均衡。表1展示了基于不同缓存节点选择策略的扩散完成后的性能。在服务成功率部分，不同的节点选择策略影响很小，因为相应的覆盖率需求设计使得对应的副本数量足以满足簇内节点的请求。但是在服务负载差异方面，随机策略要明显大于BL和BLI，这是因为随机策略在选择节点时不会考虑节点的带宽能力，将所有的节点同构化，导致拥有较高上传带宽的节点不会缓存较多的副本来提供服务，导致这些节点间的副本分布和能力分布不匹配。相反，BL和BLI策略在选择时会综合考虑节点的带宽和缓存的副本数，扩散副本时会尽可能将副本的数量正比于节点的服务能力，节点间的服务负载会比较均衡。

表1 不同缓存节点选择策略的服务性能

指标上限RandomBLBLI服务成功率0.530.5210.5220.52服务负载差异-0.6230.1470.167

图6展示了边缘网络成功服务中，节点在本地获取内容服务(0Hip)和1跳邻居获取服务(1Hip)的各自占比。由图可知，BL策略和随机策略的分布基本相同，约15%～17.4%的服务由本地节点直接提供，82.6%～85%的服务由邻居提供。BLI策略增加了用户的兴趣特征后，将本地提供服务的比例显著提高了约25.5%。这是因为在多个候选节点拥有相同的加权带宽和负载的情况下，考虑用户的兴趣特征会优先将副本放置在更容易请求该内容的节点上，所以BLI算法的本地服务成功率会明显更高。

图6 边缘网络成功服务中不同跳数的比例

4.2.3 数据传输策略优化评估

本节使用扩散完成所需时间来评估提出的覆盖率感知的传输内容选择策略(CA)和传输负载感知的接收节点选择策略(TLA)。首先固定接收节点选择策略为TLA，与CA比较的传输内容选择策略包括：轮询策略(Polling)和随机策略(Random)。因为扩散过程中不同内容扩散的副本数不同，相应的稀缺程度不能反映副本的真实稀缺情况，所以未与文献[16]和文献[18]中的算法进行比较。表2展示了在不同传输内容选择策略下的扩散完成时间。由表中数据可知，相对于轮询策略和随机策略，CA策略能以更短的时间完成扩散，减少了约7.6%的时间。因为不同内容的覆盖率需求不同，相应的扩散副本数量不同。基于覆盖率感知的选择策略在传输过程中，可以将有限的带宽资源按照比例赋予不同的内容，所以可以在较短的时间内完成扩散。因为轮询策略和随机策略都是尽可能均衡地选择不同的传输内容，所以使得部分副本数量不是很多的内容优先被扩散，传输任务较重的内容较后被扩散，扩散完成时间会相对较长。但是因为整体的内容扩散可以实现高效的资源利用，所以不同策略的扩散完成时间差距不大。

表2 不同传输内容选择策略下的扩散完成时间

指标PollingRandomCA扩散完成时间/h5.785.895.44

固定传输内容选择策略为CA，与TLA比较的接收节点选择策略为相关工作中提到的FNF[16]和BAS[17]。表3展示了在不同接收节点选择策略下的扩散完成时间。由表中数据可知，FNF扩散完成时间最长，BAS次之，TLA最短。FNF在选择接收节点时只考虑节点带宽，将所有的内容副本都优先传送到高带宽的节点上。这使得高带宽节点上累积了大量超出传输能力的副本，而带宽相对较低的节点的带宽资源却在空闲。同时，根据缓存节点选择策略，流行度较低的内容往往最后会被放置在带宽较低的节点上，这部分内容扩散完成的时间对整个网络扩散完成的时间有重要的影响，所以FNF有最长的扩散完成时间。BAS将节点选择概率正比于节点带宽，改善了FNF中的缺陷，带宽较少的节点也会以一定的概率被选择，在一定程度上减少了扩散完成的时间。TLA进一步通过定义的传输负载来量化节点带宽和等待传输的请求情况，通过更准确地衡量接收节点当前的传输负载来寻找当前负载最小的节点优先接收，实现了较优的数据扩散，减少了约9.3%的扩散完成所需时间。

表3 不同接收节点选择策略下的扩散完成时间

指标FNFBASTLA扩散完成时间/h6.336.05.44

5 结束语

针对边缘设备能力和所属用户兴趣的异构性，本文首先提出了分层的边缘网络拓扑构建，基于内容的请求频率设计了覆盖率需求和去中心化的内容扩散策略，实现了热门内容副本的快速扩散。进一步考虑设备能力和兴趣异构性，从扩散目标、缓存节点选择和数据传输策略方面对扩散策略进行优化，提出了基于用户兴趣的覆盖率需求自适应调整策略，使得边缘网络在用户请求分布不均的情况下可以提供稳定的服务。进一步综合考虑设备的带宽、负载和兴趣优化缓存节点选择策略，提高了约25.5%的用户在本地直接获取服务的比例。最后通过提出覆盖率感知的传输内容选择策略和传输负载感知的接收节点选择策略，减少了约7.6%的完成扩散所需时间。