一种基于用户移动性的小小区缓存设备分配算法

摘要

本发明公开了一种基于用户移动性的小小区缓存设备分配算法，属于无线通信领域。首先在初始化阶段进行用户群长期移动轨迹的数据集合分析，将用户移动轨迹数据集的系统时间按照一定的时间间隔分为离散的时间槽。用户在每一个时间槽内请求一次文件，计算总体缓存命中率；然后将缓存分配问题转化为一个整数规划问题；使用遗传退火算法，在解空间内搜索缓存设备容量初始分配问题的最优解。其中包括专门优化设计的适应度函数、选择操作、交叉操作等操作；若解已收敛，则输出此时设备文件在小小区基站间的分布，并据此在小小区基站间分配缓存设备，得到最优缓存设备分配方案，提高用户的缓存命中率性能并有效地节约了设备铺设成本。

说明书

技术领域

本发明属于无线通信领域，具体是一种基于用户移动性的小小区缓存设备分配算法。

背景技术

近年来，随着移动网络的快速发展，越来越多的移动用户使用多种设备通过无线网络接入互联网，因此，移动网络中的数据流量大幅增长，增加了骨干网数据传输的压力。小小区边缘缓存技术具有降低蜂窝流量和回程链路流量的优点，可以应对大量移动数据流量带来的挑战，提升网络性能，优化用户体验。

由于下一代移动通信系统中，小小区基站部署较密集，在所有的小小区基站上都布置足够容量的缓存设备将造成巨大的开销，因此，在总的缓存设备成本有限的情况下，系统无法保证每个小小区基站处都安装有足够的缓存设备。怎样优化缓存设备在小小区基站中的分布，即缓存设备在小小区基站间的选址，是一个关键问题。

目前的研究在涉及到小小区基站的缓存容量问题时，都是假设每个小小区基站都拥有相同容量的缓存设备的前提下进行的，并没有考虑缓存设备不均匀分配的情况；采用缓存设备平均分配明显的缺点就是不能灵活地在小小区基站间分配缓存设备，而在大部分现实场景中，由于移动用户的特性，在不常有用户到访的小小区基站安装与常有大量用户到访的小小区基站相同容量的缓存设备明显是不合理的，将会导致缓存设备资源的浪费。

基于M.C.Gonzalez,C.A.Hidalgo,and A.-L.Barabasi等人在2008年发表的Understanding Individual Human Mobility Patterns一文中的相关研究，人类的移动轨迹以24小时为周期，而以此周期为单位呈现回归趋势。另外，在小小区密集部署的环境中，同一用户一般可以接入数个基站，复杂的拓扑结构使得缓存设备的分配问题变得更加复杂，需要结合文件的流行度联合分析。

发明内容

本发明为了在缓存设备总量有限的情况下最大化用户的缓存命中率性能，同时优化缓存设备在小小区基站中的分配，提出了一种基于用户移动性的小小区缓存设备分配算法。

具体是：针对包含大量移动用户的密集小小区网络中基站的边缘缓存容量分配场景，通过分析用户长期移动轨迹的数据集合，综合热门文件的流行度分布，将小小区基站间缓存设备的初始分配问题以及热点文件的放置问题相结合，将其转化为一个整数规划问题，使用遗传模拟退火算法思想的邻域搜索算法在解空间内搜索缓存设备容量初始分配问题的最优解。

具体步骤为：

步骤一、针对移动网络中的某个用户群体，分析该群体中每个用户历史的长期移动轨迹，并将所有移动轨迹占有的时间按固定间隔离散化成时间槽；

移动轨迹记录的是每个用户在不同时间槽内所在的位置。

步骤二、针对每个时间槽内，每个用户都向网络请求一个单位大小的文件服务；

请求不同文件的概率符合文件流行度分布；

步骤三、根据每个时间槽内用户所处的位置、文件流行度、缓存设备及设备文件在小小区基站间的分布，计算总体缓存命中率。

全体用户的缓存命中率的数学期望值E_total(χ)如下：

T是连续时间线划分的离散的时间槽集合；为服务用户的集合；为用户请求的流行文件的集合；Z(f)为用户的文件流行度大小；I为指示函数，当其表达式为真时，I＝1；否I＝0。为小小区集合；表示用户u在时间槽τ时所处的位置；为所有用户的位置集合，二元变量γ_p,c表示用户在p位置是否处于基站c的覆盖范围内，如果在，γ_p,c＝1；否则，γ_p,c＝0；二元变量因子χ_c,f表示基站c内是否储存了文件f，如果是χ_c,f＝1；否则，χ_c,f＝0；

同时，数学期望值E_total(χ)要满足以下约束条件：

其中，C1表示基站c上存储的所有文件要小于等于该基站所能安装的缓存设备最大容量CS_max；所有基站的缓存设备最大容量CS_max值均相同。

C2表示系统为所有的基站分配的存储容量总和要小于等于系统可分配的总的缓存设备容量CS_total；系统为基站c分配的存储容量为CS(c)。

步骤四、基于遗传算法和模拟退火算法，优化总体缓存命中率的数学期望值E_total(χ)，得到缓存设备在小小区基站上的最优分配，以及热点文件在缓存设备上的最优放置。

具体步骤如下：

步骤401、将数学期望值E_total(χ)中属于同一个分配状态的二元变量因子χ_c,f排列为一个行列的矩阵χ作为遗传染色体，根据设定的种群数量，随机生成数个染色体，作为初始种群。

矩阵χ中第i行第j列的元素表示基站i上是否存储了文件j；当元素χ(i,j)为1时，说明基站i上存储了文件j；否则，基站i上未存储文件。

步骤402、将当前种群设为父代种群，计算父代种群中每个染色体的适应度；

当前种群大小为N，种群中的染色体表示为：χ₁,χ₂,…χ_n,...,χ_N；

S(χ_n)是染色体χ_n的适应度值，计算如下：

χ^best为遗传算法历次迭代中产生的最优良个体的染色体；随着迭代次数的增加而变化。

步骤403、根据每个染色体的适应度，使用轮盘赌式随机选择染色体，分别计算每个染色体被选择遗传给子代的概率。

针对染色体χ_n被选择遗传给子代的概率P_n计算如下：

步骤405、当染色体被选择遗传给子代的概率满足约束条件时，选择该染色体进行后续操作；

约束条件为：

r为利用随机数种子生成的实数，0＜r＜1；

针对染色体χ_n，当概率P_n时满足上述约束条件时，染色体χ_n被选中；

步骤406、选择两个满足条件的染色体，进行交叉和变异操作，得到两个新染色体；

具体步骤如下：

步骤4061、系统生成两个随机数

步骤4062、利用选中的两个染色体χ_a,χ_b，判断的值是否为1，如果是，则交换χ_a(u,v)与χ_b(u,v)的值，进入步骤4063；否则，返回步骤4061；

步骤4063、验证交换后的染色体χ_a与χ_b是否满足约束条件，如果是，进入步骤4064进行变异操作；否则，返回步骤4061；

约束条件如下：

C3表示矩阵χ中第i个基站上存储的所有文件要小于等于该基站所能安装的缓存设备最大容量CS_max；也就是染色体χ_a与χ_b对应的矩阵中每个基站上存储的所有文件满足小于等于CS_max；

C4表示系统为矩阵χ中所有基站分配的存储容量总和要小于等于系统可分配的总的缓存设备容量CS_total；也就是系统为矩阵χ_a与χ_b中所有基站分配的存储容量总和满足小于等于CS_total。

步骤4064、系统产生四个随机数

步骤4065、针对交换后的染色体χ_a判断是否如果是，则交换χ_a(u,v)与χ_a(u′,v′)的值作为染色体χ_a的变异结果χ_a'，否则，返回步骤4064。

针对交换后的染色体χ_b进行同样操作，得到染色体χ_b'的最终变异结果。

步骤407、对变异所得的两个新染色体χ_a'与χ_b'，分别执行扰动操作，并判断扰动结果是否满足Metropolis准则，如果是，则进入步骤408，否则，对扰动结果重新进行扰动操作。

扰动操作具体如下：

步骤4071、系统产生四个随机数

步骤4072、针对变异染色体χ_a'判断是否如果是，则交换χ_a'(u₁,v₁)与χ_a(u₂,v₂)的值作为待变异染色体χ_a'的扰动结果，否则，返回步骤4064。

针对变异后的染色体χ_b'进行同样操作，得到染色体χ_b'的最终扰动结果。

步骤408、判断当前扰动次数是否达到迭代步长，如果是，将染色体χ_a'与χ_b'的扰动结果放入子代种群，进入步骤409；否则，返回步骤407；

步骤409、判断子代种群是否等于自适应种群大小，如果是，进入步骤410；否则，执行步骤406，继续选择染色体进行操作。

步骤410、判断当前子代种群内具有最大E_total(χ)的染色体是否已收敛，如果是，则结束并输出最优结果，否则，返回步骤402进行新一轮迭代：

最优结果为小小区基站上如何布置缓存设备以及在缓存设备上如何放置热点文件。

步骤五、按照最优的结果在小小区基站上布置缓存设备，以及在缓存设备上放置热点文件。

本发明的优点在于：

1)、一种基于用户移动性的小小区缓存设备分配算法，可以实现对用户缓存命中率的提升。根据仿真结果可以看出，本发明对小小区基站缓存设备的分配，有效的提升了用户的缓存命中率性能。

2)、一种基于用户移动性的小小区缓存设备分配算法，可以节约缓存设备成本，通过分析用户的移动位置偏好，减少不常有用户到访的小小区基站的缓存设备，从而节省了运营商铺设缓存设备的成本。

附图说明

图1是本发明移动网络中用户群体历史的长期移动轨迹示意图；

图2是本发明一种基于用户移动性的小小区缓存设备分配算法流程图；

图3是本发明基于遗传模拟退火算法优化总体缓存命中率的数学期望值的流程图；

图4是本发明与平均分配算法下缓存命中率随文件的流行度分布的变化比较图；

图5是本发明与平均分配算法下缓存命中率随缓存容量饱和度的关系对比示意图。

具体实施方式

下面将结合附图和实施例对本发明作进一步的详细说明。

本发明一种基于用户移动性的小小区缓存设备分配算法，在具有边缘缓存技术的小小区网络中，首先，在初始化阶段进行用户群长期移动轨迹的数据集合分析，将用户移动轨迹数据集的系统时间按照一定的时间间隔分为离散的时间槽。用户在每一个时间槽内请求一次文件，并根据每个时间槽内用户所处位置、综合热门文件的流行度分布，将小小区基站间缓存设备的初始分配问题以及热点文件在缓存设备的放置问题相结合，计算总体缓存命中率；然后，将缓存分配问题转化为一个整数规划问题；使用遗传退火算法，以设备文件在小小区基站间的分布变量为染色体，在解空间内搜索缓存设备容量初始分配问题的最优解，以优化总体缓存命中率。其中包括专门优化设计的适应度函数、选择操作、交叉操作、变异操作、自适应交叉变异概率机制、扰动操作、降温函数、自适应种群数量机制；若解已收敛，则视为达到最优分配，输出此时设备文件在小小区基站间的分布，并据此在小小区基站间分配缓存设备，得到最优缓存设备分配方案，提高用户的缓存命中率性能并有效地节约了设备铺设成本。

如图2所示，具体步骤为：

步骤一、针对移动网络中的某个用户群体，分析该群体中每个用户历史的长期移动轨迹，并将所有移动轨迹占有的时间按固定间隔离散化成时间槽；

移动轨迹记录的是每个用户在不同时间槽内所在的位置，如图1所示。

步骤二、针对每个时间槽内，每个用户都向网络请求一个单位大小的文件服务；

请求不同文件的概率符合文件流行度分布；

步骤三、根据每个时间槽内用户所处的位置、文件流行度、缓存设备及设备文件在小小区基站间的分布，计算总体缓存命中率。

全体用户的缓存命中率的数学期望值E_total(χ)如下：

T是连续时间线划分的离散的时间槽集合；为服务用户的集合，数量为为用户请求的流行文件的集合；数量为大小相等；Z(f)为用户的文件流行度大小；I为指示函数，当其表达式为真时，I＝1；否I＝0。为小小区集合，数量为表示用户u在时间槽τ时所处的位置；为所有用户的位置集合，二元变量γ_p，c表示用户在p位置是否处于基站c的覆盖范围内，如果在，γ_p,c＝1；否则，γ_p,c＝0；二元变量因子χ_c,f表示基站c内是否储存了文件f，如果是χ_c,f＝1；否则，χ_c,f＝0；

同时，数学期望值E_total(χ)要满足以下约束条件：

其中，C1表示基站c上存储的所有文件要小于等于该基站所能安装的缓存设备最大容量CS_max；所有基站的缓存设备最大容量CS_max值均相同。

C2表示系统为所有的基站分配的存储容量总和要小于等于系统可分配的总的缓存设备容量CS_total；系统为基站c分配的存储容量为CS(c)；单位为一个流行文件的大小。

步骤四、基于遗传算法和模拟退火算法，优化总体缓存命中率的数学期望值E_total(χ)，得到缓存设备在小小区基站上的最优分配，以及热点文件在缓存设备上的最优放置。

如图3所示，具体步骤如下：

步骤401、将数学期望值E_total(χ)中属于同一个分配状态的二元变量因子χ_c,f排列为一个行列的矩阵χ作为遗传染色体，根据设定的种群数量，随机生成数个染色体，作为初始种群。

针对缓存命中率的数学期望值E_total(χ)，χ为自变量；通过调整来优化E_total(χ)；χ_c,f是二元变量，符合遗传算法中的染色体位点特性，无需引入额外的编码方式。考虑到式(2)与式(3)的约束条件，本发明使用矩阵形式的遗传染色体，将属于同一个分配状态的χ变量排列为一个行列的矩阵，用χ表示。矩阵χ中第i行第j列的元素χ(i,j)表示基站i上是否存储了文件j；当元素χ(i,j)为1时，说明基站i上存储了文件j；否则，基站i上未存储文件。

将式(2)与式(3)的约束条件转化为：

C3表示矩阵χ中第i个基站上存储的所有文件要小于等于该基站所能安装的缓存设备最大容量CS_max；也就是染色体χ_a与χ_b对应的矩阵中每个基站上存储的所有文件满足小于等于CS_max；

C4表示系统为矩阵χ中所有基站分配的存储容量总和要小于等于系统可分配的总的缓存设备容量CS_total；也就是系统为矩阵χ_a与χ_b中所有基站分配的存储容量总和满足小于等于CS_total。

步骤402、将当前种群设为父代种群，计算父代种群中每个染色体的适应度；

当前种群大小为N，种群中的各染色体表示为：χ₁,χ₂,…χ_n,...,χ_N；

S(χ_n)是染色体χ_n的个体适应度值，计算如下：

χ^best为遗传算法历次迭代中产生的最优良个体的染色体；是一个动态值，随着迭代次数的增加而变化。

步骤403、根据每个染色体的适应度，使用轮盘赌式随机选择染色体，分别计算每个染色体被选择遗传给子代的概率。

在每代进化时，首先向子代中添加当前最优基因χ^best；则针对染色体χ_n被选择遗传给子代的概率P_n计算如下：

步骤405、当染色体被选择遗传给子代的概率满足约束条件时，选择该染色体进行后续操作；

约束条件为：

r为利用随机数种子生成的实数，0＜r＜1；

针对染色体χ_n，当概率P_n时满足上述约束条件时，染色体χ_n被选中；

步骤406、选择两个满足条件的染色体，进行遗传算法的交叉和变异操作，得到两个新染色体；

具体步骤如下：

步骤4061、系统生成两个随机数

步骤4062、利用从父代种群选中的两个染色体χ_a,χ_b，判断的值是否为1，如果是，则交换χ_a(u,v)与χ_b(u,v)的值，进入步骤4063；否则，返回步骤4061；

步骤4063、验证交换后的染色体χ_a与χ_b是否满足式(4)和(5)的约束条件，如果是，进入步骤4064进行变异操作；否则，返回步骤4061；

步骤4064、系统产生四个随机数

步骤4065、针对交换后的染色体χ_a判断是否如果是，则交换χ_a(u,v)与χ_a(u′,v′)的值作为染色体χ_a的变异结果χ_a'，否则，返回步骤4064。

针对交换后的染色体χ_b进行同样操作，得到染色体χ_b'的最终变异结果。

对应于染色体χ_a，交叉概率P_cross和变异概率P_mutate的设置如下：

其中，F_avg为当前种群的适应度平均值，P_c1为设定的交叉概率的上界；P_c2为设定的交叉概率的下界，P_m1为设定的变异概率的上界；P_m2为设定的变异概率的下界。本文中取P_c1＝0.9，P_c2＝0.5，P_m1＝0.2，P_m2＝0.02。并且在对两个染色体进行交叉操作时，交叉概率选为两染色体对应交叉概率的较小值。

步骤407、对变异所得的两个新染色体χ_a'与χ_b'，分别执行扰动操作，并判断扰动结果是否满足Metropolis准则，如果是，则进入步骤408，否则，对扰动结果重新进行扰动操作。

在每次执行完遗传算法的交叉操作与变异操作产生新个体后，在固定的步长L内，使用扰动操作随机改变染色体χ，当染色体χ温度为T时，计算此时的固体能量G(χ)＝1/F(χ)，随着温度T的下降，在下一次迭代时，使用扰动函数使固体处于一个新状态χ′，计算此时的固体能量G(χ′)。并根据Metropolis准则以及概率P_Metropolis选择是否接受新状态χ′作为当前固体状态。另外，本发明使用的扰动操作与之前所述的变异操作相同。

概率P_Metropolis计算如下：

其中，ΔG＝G(χ′)-G(χ)，即新固体能量与旧固体能量的差值。

在模拟退火环节中，初始温度T₀为：

其中，F_min和F_max分别为初始种群中适应度值的最小值与最大值，s为一可调整的常数。

降温函数使系统当前温度T在每次迭代的过程中改变，本发明在指数降温函数的基础上改进，若设下一代温度为T′，则有

其中，本实施例取α＝0.95，K＝1.1，M＝20。

扰动操作具体如下：

步骤4071、系统产生四个随机数

步骤4072、针对变异染色体χ_a'判断是否如果是，则交换χ_a'(u₁,v₁)与χ_a(u₂,v₂)的值作为待变异染色体χ_a'的扰动结果，否则，返回步骤4064。

针对变异后的染色体χ_b'进行同样操作，得到染色体χ_b'的最终扰动结果。

步骤408、判断当前扰动次数是否达到迭代步长，如果是，将染色体χ_a'与χ_b'的扰动结果放入子代种群，进入步骤409；否则，返回步骤407；

步骤409、判断子代种群是否等于自适应种群大小，如果是，进入步骤410；否则，执行步骤406，继续选择染色体进行操作。

步骤410、判断当前子代种群内具有最大E_total(χ)的染色体是否已收敛，如果是，则结束并输出最优结果，否则，返回步骤402进行新一轮迭代：

最优结果为小小区基站上如何布置缓存设备以及在缓存设备上如何放置热点文件。

基于遗传算法和模拟退火算法，优化总体缓存命中率的数学期望值E_total(χ)的总体算法流程概述如下：

步骤1：输入初始化种群数目S_max、自适应最小种群数目S_min、自适应参数M、初温系数s、退温系数α、加扰系数K、模拟退火步长L、交叉概率P_c1与P_c2、变异概率P_m1与P_m2。

步骤2：初始化种群并根据适应度函数计算每个个体的适应度值。并根据式(13)计算初始温度T₀。

步骤3：将当前种群设为父群，开始进化，首先把当前最优基因χ^best放入子代种群。

步骤4：按照选择操作选择两染色体，记录其适应度值，并根据交叉概率P_c1与P_c2、变异概率P_m1与P_m2计算自适应交叉变异概率P_cross和P_mutate，并根据此概率进行交叉变异操作。

步骤5：将所得的染色体做扰动操作，计算新的适应值，并根据Metropolis准则决定是否接收新状态。

步骤6：若当前迭代次数若小于模拟退火步长L，则返回步骤5，否则将新染色体放入子代种群中。

步骤7：若当前子代种群未满，则返回步骤4，否则更新当前子代种群适应度值，并更新当前最优基因χ^best。

步骤8：判断当前最优解χ^best是否已收敛，若未收敛，则返回步骤3，否则，输出当前最优解χ^best并结束算法。

在算法初期，设定初始种群数量为一较大值S_max，这样可以保证初期的基因多样性，而在遗传算法迭代过程中，若经历M次遗传迭代而χ^best未发生变化，则S_max减小1，直至减小到最小种群数量S_min为止。由此可减少算法后期在不存在最优解的解空间内进行不必要搜索所浪费的计算量，提高了算法的执行效率。

步骤五、按照最优的结果在小小区基站上布置缓存设备，以及在缓存设备上放置热点文件。

实施例：

本实施例考虑如下场景：使用韩国科学技术院内(KAIST)的92个实验用户在1个月内的移动轨迹作为移动轨迹数据来源。使用均匀分布的小小区基站部署方式，将相邻小小区基站间的距离设为40米，每个小小区基站信号的覆盖半径设为100米。每个基站最多可安装的缓存设备容量的大小为5个文件单位。在用户文件请求方面，假设文件流行度符合系数为α的Zipf分布，且流行文件集合的总数为100。另外，为分析系统缓存命中率和总缓存容量CS_total大小的关系，定义缓存容量饱和度η为总缓存容量CS_total与小小区基站数量之比，单位为文件，即

为了证明本文提出的缓存设备分配机制的性能，选用了平均分配的缓存设备分配机制进行对比。

平均分配算法：将总缓存设备平均分配给各个小小区基站，不考虑用户移动性。

如图4所示，设定缓存容量饱和度η＝1。由图可知，随着Zipf分布系数α的增加，两种算法的缓存命中率性能也随之增大，且在不同的Zipf分布系数α下，遗传退火算法的缓存命中率性能较平均分配算法都有着一定提升。

遗传退火算法和平均分配算法在不同的缓存容量饱和度下的缓存命中率性能对比，如图5所示，其中，设定Zipf分布系数α＝1。可以发现，随着缓存容量饱和度的增加，两种算法的缓存命中率性能均有提升。并且，相较于平均分配算法，遗传退火算法在低缓存容量饱和度的情况下的性能提升了120％，而在高缓存容量饱和度的情况下性能提升了80％。这是因为遗传退火算法根据用户群体长期的移动轨迹数据调整缓存设备的分配，在总的缓存设备容量一定的情况下，将更多的缓存设备分配给具有较多被接入机会的小小区基站，并同时在用户可以接入多个小小区基站的密集场景下，结合文件流行度的分布进行缓存内容的最优化。由此可见，在缓存容量饱和度较低的情况下，遗传退火算法相较于平均分配算法有着更好的缓存命中率性能提升效果。

本发明在小小区基站缓存设备的分配中，引入用户的移动性来优化分配，并采用基于遗传模拟退火的算法模型来求解，从而决策出最优的分配方案，提高用户的缓存命中率性能，节约设备铺设成本。