基于访问均衡性核度中心的分布式密集无线网络边缘缓存决策策略

王 蒙 蒙

(滨州学院信息工程学院 山东 滨州 256603) (南京航空航天大学计算机科学技术学院 江苏 南京 210000)

0 引 言

随着5G应用的普及，移动设备和数据流量将呈现指数增长。为了应对海量接入以及大容量传输，最直接高效的方法是密集地部署基站(包括宏基站、微基站、中继站等)，形成密集无线网络[1-4]。在密集无线网络中，有限的回程带宽一定程度上限制了网络性能。文献[5]指出，在极端密集的无线网络中，回程的功耗可以占到总功耗的30%。移动边缘网络缓存技术通过利用数据和用户的空间、时间特性将存储资源推送到移动网络边缘，可以有效减轻回程负载、降低网络延迟和提高用户体验[6]。

在数据资源缓存决策研究中，主要包含非协作策略和协作策略，文献[7]提出一种基于用户移动感知的数据缓存策略，通过感知用户移动将数据缓存到靠近用户目的位置的区域。Psaras等[8]提出一种基于概率的数据资源缓存策略，通过与服务器的距离概率进行缓存决策。Wang等[9]提出一种确定性缓存策略，通过构建启发式算法解决缓存决策问题。Gu等[10]在启发式策略构建过程中进一步考虑了迭代过程与初始分配方案，优化了算法性能。Gharaibeh等[11]提出一种在线缓存算法，通过多基站合作减少内容提供总成本。非协作的数据缓存策略没有考虑其他缓存主体的影响，在协作缓存策略中考虑了更多影响因素。Zhao等[12]提出了一种集中式和分布式相结合的缓存方式，以此提高缓存效率。文献[13]提出一种区域协作缓存策略，以提高缓存收益。文献[14]提出一种分层协作缓存策略，通过优化算法减少用户访问代价。Sun等[15]提出一种辅助缓存布局方案，联合优化异构网络中的数据缓存和带宽分配策略，降低用户访问中断概率。

现有算法主要针对单个基站或是综合考虑带宽、实验等因素判断是否缓存，缺乏对边缘缓存网络协作问题的研究。另外这些讨论都是针对固定网络拓扑进行的，在边缘缓存网络中接入时刻、访问时间、访问内容等都是随机的，并且由于基站节点接入限制，一个用户只能接入一个基站，那么缓存在该基站的内容将无法为其他基站用户服务。

为解决流行内容缓存位置的决策问题，本文提出基于访问均衡性核度中心的边缘缓存决策方法(Cncv)，以一个分布式无线边缘缓存网络簇为研究对象，利用核度中心评估方法结合访问信息熵共同决策内容的缓存位置，该方法既考虑了基站节点自身的连接特点，同时也考虑了访问均衡性对节点缓存价值的影响，能够针对不同访问内容确定最快满足用户响应的缓存节点，计算简便。

1 边缘缓存网络模型

边缘缓存网络主要由基站、基站服务器、RAN控制器组成，如图1所示。基站间通过无线连接，所有基站通过特定基站(簇首)经过核心网与云中心连接，服务器具备缓存功能为用户提供服务；RAN控制器与簇内所有边缘服务器相连，收集所有服务器信息。

图1 边缘缓存网络模型

用户可以随机接入任何一个基站节点请求任何内容，假设簇内任意节点间的传输时间都小于簇首节点到核心云的传输时间，则用户获得响应的方式如下：

1) 如果接入基站服务器缓存了用户请求的内容，则服务器直接响应用户请求。否则执行2)。

2) 如果接入基站服务器的一跳邻居服务器缓存了用户请求内容，则一跳邻居服务器将内容发送给接入服务器并响应用户请求，否则执行3)。

3) 如果其他节点缓存用户请求的内容，则该服务器负责传给接入基站服务器并响应用户请求，否则，继续查找其他基站服务器是否缓存该内容，直到簇内所有基站节点查找完毕。如果簇内所有节点都未缓存该内容，则执行4)。

4) 假设在核心云中用户请求得到响应，核心云将请求内容发送给簇首服务器，然后再由簇首服务器发送给接入服务器，最后发送给用户。在核心云中获得响应将不得不付出更大的代价。

显然，请求的内容离访问接入基站越近，付出的代价越小；边缘缓存网络簇内缓存的内容越多，用户请求响应平均代价越小。然而边缘服务器缓存空间有限，用户访问请求分布不均匀，高效的缓存策略有利于服务质量的提高。

2 边缘缓存网络缓存决策策略

2.1 访问核度中心率

核度中心率既考虑了网络的拓扑结构，也考虑了邻居节点的连接情况，通过考察节点的连接度就可以获得节点的核度中心率。但是在边缘缓存网络中用户的接入位置是不确定的，因此哪个节点处在网络的中心位置需要考虑当前的访问情况，因此本文通过引入节点自身访问频率构成访问核度中心率Cvc(v)，以此作为缓存决策标准，确定网内缓存策略，综合考虑节点位置和接入确定放置位置。

节点的访问核度中心率是所有邻居节点的访问核度与本节点的访问数之和，Cvc(v)节点v的访问核度中心率由式(1)给出：

(1)

式中：N(v)为节点v的邻居集合；kvj是节点j的访问核度；λv为节点v的访问数，节点访问数是在统计时间内用户接入该节点发起访问请求的次数。

访问核度的确定是通过按连接度从小到大的顺序依次删除节点和其连接的边，确定其所在核层，并记录节点自身访问数，节点的访问核度就是节点的访问数与其所在核层的和。

如图2所示，其中节点旁边的数字代表访问数。按照公式1计算，节点a的访问核度中心率为18，节点b的访问核度中心率为21，同理可以计算其他节点的访问核度中心率，从计算结果可以看出节点b具有最大的访问核度中心率，因此将内容缓存在b节点上具有更高的响应效率。下面按传输能耗(假设每一跳能耗均为1)比较内容缓存在节点a和b上时的不同：

P(a)=6×2×1+3×2×1+7×3×1+

(7+1+1)×2=57

P(b)=6×3×1+3×2×2+7×2+

(7+1+1)×1=53

显然节点b作为缓存节点更有利于响应访问请求。

图2 访问核度中心率示意图1

2.2 访问均衡率

在图2中因为a、b邻居节点的总访问数不一样，影响了a、b节点的重要性，进而影响了两者的缓存价值，我们通过访问核度中心率可以很好地解决这个问题。如果a、b邻居节点的访问数一样，那a、b节点的缓存价值如何确定呢？

图3 访问核度中心率示意图2

如图3所示，此时a、b邻居节点的总的访问数是一样的，经过计算可以发现Cvc(a)=Cvc(b)=18，仅通过访问核度中心率显然无法判断a、b谁更具缓存价值。由于两者访问核度中心率相同，节点a和b会被认为具有相同的缓存价值。然而观察可以发现，虽然节点a和节点b的邻居节点的总访问数都是6，但分布不一样，因此如果节点b和节点h之间路径崩溃则直接影响4个访问，而对于节点a，若与相邻的节点e、f、g之间的1条路径的崩溃，则只影响2个访问，即在同等通信环境下，节点a比节点b对网络的影响更大，因此该节点a具有更大的缓存价值。为了衡量邻居节点访问数对节点自身缓存价值的影响，本文基于香农熵定义节点的访问均衡熵ei为：

(2)

式中：j为i邻居节点中的任一节点(j∈N(i))；kvj为节点j的访问核度；ei值越大表明节点i的访问越均衡，越容易满足用户的访问请求，其缓存价值也越大。

对访问均衡熵进行标准化处理，本文中标准化访问均衡熵我们称为访问均衡率，其公式为：

(3)

式中：mi=N(i)集合中节点的个数，并且mi≥2。因为小于2时均衡性讨论没有意义，所以本文中当某一节点的邻居节点数小于2时，其均衡性为1。均衡性实际指的是节点各分支节点的访问分布是否均匀，与节点其他因素没有关系。

2.3 访问均衡核度中心评估方法

通过以上分析，在边缘缓存网络中节点的缓存价值是与其访问均衡率以及访问核度中心率有关，结合邻居节点访问核度中心率，提出一种访问均衡核度中心评估方法Cncv(v)，其公式为：

(4)

边缘缓存网络簇中的基站节点可以独立地计算自身的访问均衡核度中心值Cncv(v)，然后通过RAN进行排序并确定最佳缓存节点。

3 节点缓存价值理论分析

3.1 节点缓存价值比较

下面以图3的小规模样本网络为例，分别利用各种核心节点确认方法(CD、CB、Ckc、Cnc、Cncd及Cncv)对节点价值进行评估及排序。表1显示了不同核心节点确认方法的排序结果(φ=0.8)，结果显示有些方法无法区分节点排序，因此采用更为精确的方法就显得非常重要；如节点a和b在Cncv中进行了更细粒度的排序。表2显示了核心节点在不同方法下的计算值。

表1 不同方法下核心节点的排序

表2 不同方法下核心节点的计算值

3.2 访问均衡熵对节点满足访问请求能力的意义

鉴于实际情况中节点接入及无线通信并不都是稳定可靠的，假设接入的稳定性(每个访问结束前链路保持连通的概率)为β，节点间无线通信的成功率为α，当接入节点i的访问请求数为di时，该节点成功接受的有效访问请求数为Ii=di·βdi。

假设图3中a、b节点为t=0时刻的信源节点，则在t=1时刻，具有较大访问均衡熵的节点a可以满足的平均访问数是6β2α，而具有较小访问均衡熵的b节点可以满足的平均访问数是4β4α+2βα。由此可见相对于其他方法，基于访问均衡熵的方法能够更细致地对节点满足访问请求能力进行有效区分和排序。

3.3 节点满足访问请求的能力

对于每个节点发起的访问，无非有两种状态：满足和未满足。当请求的内容缓存或传输到该节点时，该节点的所有访问请求将被满足，否则就是未满足。

表3 不同核心节点访问能耗比较

通过比较计算可以看出访问能耗的排序与Cncv方法中节点缓存价值排序是一致的，也就是说访问能耗更小的节点具有更大的缓存价值，能更有效地满足请求。

4 实 验

4.1 实验网络拓扑数据

为了更准确地验证本文方法的有效性，实验过程中使用了真实的Jazz网络，拓扑特性如表4所示，其中每个节点的访问频率设置为[0,10]随机数，并且实验参数β=0.8，φ=0.8。

表4 Jazz网络拓扑数据

4.2 实验结果分析

使用独立级联模型IC比较不同方法选取差异节点的满足访问效果；实验平台为Intel(R)Core(TM) i7- 6200CPU，8 GB内存，使用的操作系统软件为ubuntu-14.04.4-desktop-i386.

为了分析本文提出的访问均衡性核度中心方法与其他评估方法在节点满足访问能力方面的差异，实验分别将Cncv与CD、CB、Cnc及Cncd四种方法两两比较，选取排名前15且与比较方法不完全一致的节点作为源节点(当节点排序无法区分时，实验节点随机选择，实验中Cncv与CB和CD各有5个不同节点、Cncv与Cnc和Cncd各有3个不同节点)，因为相同节点在同一轮次内满足的访问请求数是一样的。

(a)

(b)

(c)

(d)图4 前15名节点满足访问请求效率差异图

从图4(a)-图4(d)中可以观察到，与其他四种方法相比，Cncv方法在满足访问请求效率方面优于其他方法，在同样的传播轮次下可以满足更多的访问请求。分析可知，Cncv方法引入了访问核度的概念，对于节点的连接度、访问频率、访问多样性进行了全面考虑，因此可以更好地满足访问请求。

5 结 语

为了解决边缘缓存网络中缓存基站节点的选择问题，结合访问频率和网络结构对于缓存效率的影响，提出一种基于访问均衡性的基站节点缓存决策方法，即基于访问均衡性核度中心(Cncv)方法，该方法创新性地将满足用户请求作为直接研究对象，因此相对其他缓存决策方法可以更高效地满足用户请求。与当前其他研究工作类似，本文主要研究如何缓存内容可以更好地满足访问请求，没有深入细致地讨论信道及缓存资源分配，而在边缘网络中，这些问题是无法忽略的。未来将进一步考虑这些因素，从而实现更高的访问效率。