CN111818130A - 基于强化学习缓存与计算的联合优化 - Google Patents

Abstract

本发明实施例公开了基于强化学习NOMA‑MEC系统中缓存与计算的联合优化，其中主要涉及多用户、多MEC服务器的NOMA‑MEC系统的联合缓存和卸载问题。通过将单个服务器的本地缓存扩展到多个服务器的协作缓存，服务器之间可以共享计算结果。为了使整个系统的时延最小，找到每个用户最优的缓存和卸载策略。

Description

基于强化学习缓存与计算的联合优化

技术领域

本发明涉及通信领域，尤其涉及一种基于强化学习缓存与计算的联合优化。

背景技术

随着科技的发展，用户对移动通信业务的处理速度需求越来越高，为了加快移动通信业务的处理速度，减少数据传输的延时，提高用户的体验，移动通信行业正在讨论在无线接入网的边缘设置移动边缘计算服务器，通过移动边缘计算服务器可以为接入该无线网络的用户提供计算能力和/或存储能力。

非正交多址接入(Non-orthogonal Multiple Access，NOMA)和移动边缘计算(Mobile Edge Computing，MEC)都被认为是下一代无线网络中极具发展前景的技术。随着智能通信的快速发展，移动边缘计算越来越多地应用于未来通信领域，它可以提高用户在应用中的计算能力，可以在如虚拟现实、增强现实、无人驾驶等领域发挥重要作用。与使用传统的云计算系统不同，移动边缘计算可以在云无线接入网中提供计算能力。移动边缘计算的基本思想是利用无线电网络中具有强大计算能力的设施，通过利用如集成于基站中的移动边缘计算服务器，用户可以将计算任务卸载到位于网络边缘的移动边缘计算服务器中，再由移动边缘计算服务器进行任务计算。由于移动边缘计算服务器可以部署在用户附近，因此使用移动边缘计算的网络可以为用户提供低延迟和低能耗的任务计算服务。

在移动边缘计算(MEC)和非正交多址接入(NOMA)结合的系统中，主要利用卸载计算去降低时延和能耗。由于MEC服务器的计算容量有限，并且在 MEC系统中，不同用户卸载的任务经常是相同的。为了避免相同任务的重复传输和计算，缓存是降低时延的有效解决方法。在NOMA-MEC系统中的缓存，现有技术中只考虑一个MEC服务器和本地缓存。单个MEC服务器的缓存容量有限，因此很难缓存更多的任务计算结果。如果多个用户请求任务的类型是多样的，则会导致较低的命中率。在这种情况下，未完成的任务只能被计算，因此不能有效地减少时延。

发明内容

为解决上述技术问题，本发明实施例提供了基于强化学习NOMA-MEC 系统中缓存与计算的联合优化，也可以说是一种基于强化学习的方法，目的是去最小化时延。其中主要涉及多用户、多MEC服务器的NOMA-MEC系统的联合缓存和卸载问题。通过将单个服务器的本地缓存扩展到多个服务器的协作缓存，服务器之间可以共享计算结果。为了使整个系统的时延最小，需要找到每个用户最优的缓存和卸载策略。

本发明实施例提供了如下技术方案：

一种基于强化学习缓存与计算的联合优化，应用于NOMA-MEC系统中, 联合优化缓存和计算，通过将单个服务器的本地缓存扩展到多个服务器的协作缓存，多个服务器之间可以共享计算结果，为了使整个系统的时延最小，找到每个用户最优的缓存和卸载策略，所述方法包括：

针对用户不同的决策方式，生成本地缓存，协作缓存，本地计算和卸载计算模式下的时延函数；

考虑到任务流行度是动态的和未知的，提出门控递归单元算法来预测任务流行度，将流行度高的计算结果放置在相应的移动边缘计算服务器上进行缓存。

基于服务器上缓存的计算结果，利用多代理深度Q网络算法寻找最优的缓存和卸载决策；

其中，所述针对用户不同的决策方式，生成本地缓存，协作缓存，本地计算和卸载计算模式下的时延函数，具体包括：

1)对于选择本地缓存的用户来说，与协作缓存和卸载计算相比，它的时延是忽略不计的。

2)在协作缓存模式下，处理任务的时延主要是服务器间传输产生的时延 T_m,n：

其中r_m,n表示本地服务器m和协作服务器n的下载速率，M_j代表任务j计算结果的大小。

3)如果用户选择卸载计算，为了提高频谱利用率，进一步降低传输时延，采用NOMA技术将信息传输到本地基站。处理任务的时延由卸载时延

在 MEC服务器上的处理时延

和回传时延

三部分组成。由于回传时延较小，一般可以忽略。

针对选择本地计算的用户，本地执行时延为

其中W_j表示处理任务j总的CPU周期数，

是用户i在本地计算阶段的计算容量。

其中，所述考虑到任务流行度是动态的和未知的，提出门控递归单元算法来预测任务流行度，将流行度高的计算结果放置在相应的移动边缘计算服务器上进行缓存，具体包括：

1)收集用户在历史时刻请求的任务和不同任务的计算结果，执行下面的操作。

2)输入历史时期的流行度{S_j(1),S_j(2),···S_j(T_M)}，其中,S_j(t)表示任务j在时间t上的流行度。经过GRU单元，得到长度为T_N的预测的流行度 {S_j(T_M+1)，S_j(T_M+2),···S_j(T_M+T_N)}。

3)计算预测流行度q(j)和在预测时刻到来时真实流行度p(j)之间的损失函数

通过不断调整参数，使损失函数变小。

4)直到损失函数不再发生变化，停止训练，否则，返回1)。

由于服务器的缓存空间有限，很难存储所有任务的结果，考虑到服务器的缓存容量和计算结果的大小，将任务的计算结果按流行度由大到小的顺序缓存在服务器上，以便尽可能多地缓存任务的计算结果。在这种方式下，其他服务器也使用GRU算法来缓存相应的计算结果。在所有用户请求任务之前，这些服务器已经放置了流行任务的计算结果，这有利于命中本地缓存和协作缓存。

其中，所述基于服务器上缓存的计算结果，利用多代理深度Q网络算法寻找最优的缓存和卸载决策，具体包括：

在多代理系统中，将相同基站中的每个用户视为代理。每个代理在做决策前，不知道其他代理的行为。根据环境的状态信息，代理选择自己的动作。在选择动作前，需要判断命中的情况。根据状态信息和用户请求的任务，用户可以知道是否命中了本地缓存还是协作缓存。只有当缓存被命中时，用户才能选择缓存决策。在代理获得状态信息和做出动作选择后，环境会反馈给代理奖励信息用于判断动作的好坏。考虑到奖励值，代理不断地调整自己的行为来让奖励最大化。MADQN算法的具体过程如下:

1)初始化状态s_i，动作a_i，奖励r_i，当前Q网络Q(s,a；θ)和目标Q网络

等变量。

2)对于每个代理，观察初始状态

其中μ(t)是在时间t上，存储在所有服务器上任务的序号。

表示用户i在本地服务器m上的时延。

是MEC服务器剩余的计算容量。ξ(t)代表在同一基站中N个用户可利用的能耗。

3)根据贪心算法选择动作

代理以高概率1-ε选择最优的决策。否则，它将以ε的概率随机的选择缓存和卸载决策。其中

是任务卸载决策，

表示本地计算决策，

分别表示本地缓存和协作缓存决策，ε为影响因子。

4)更新奖励r_i(t)＝T_i(t-1)-T_i(t)，其中T_i(t)和T_i(t-1)分别表示用户i在时间t和t-1上的时延。

5)存储代理i在时间t上的经验e_i(t)到经验回放单元D(t)中，训练时从中抽取小批量的转移序列。

6)使用随机梯度下降法更新损失函数L(t)。

7)更新下一个状态s(t+1)←s(t)。

8)直到参数θ收敛停止训练。

按照上述方法，缓存和卸载决策的选择可以被执行在其他基站的用户中，由于整个系统的时延是由多个基站的时延组成，所以最小化整个系统的时延可以通过减少不同基站的时延来实现。

与现有技术相比，上述技术方案具有以下优点：

本发明实施例提供了基于强化学习NOMA-MEC系统中缓存与计算的联合优化，也可以说是一种基于强化学习的方法，联合优化NOMA-MEC系统中的缓存和计算。首先，考虑到多服务器间的计算结果缓存和任务卸载的问题，利用多服务间协作缓存的方式来提高缓存命中率。其次，考虑到任务流行度是动态的和未知的这种更为合理的情况，提出门控递归单元这种新颖的任务流行度的预测方法，该算法是第一次被用于任务流行度的预测。利用这种算法去预测任务流行度，对于随时间动态变化的流行度，通过适当的增加学习率，它预测的更加准确。最后，基于预测的流行度，多代理深度Q网络算法被用来自主的选择缓存和卸载决策，通过不断地训练，它可以达到最小化时延的目的。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明一个实施例所提供的基于强化学习缓存与计算的联合优化示意图。

具体实施方式

正如背景技术部分所述，在NOMA-MEC系统中的缓存，现有技术中只考虑一个MEC服务器和本地缓存。单个MEC服务器的缓存容量有限，因此很难缓存更多的任务计算结果。如果多个用户请求任务的类型是多样的，则会导致较低的命中率。在这种情况下，未完成的任务只能被计算，因此不能有效地减少时延。

针对现有技术的不足，本申请提出一种基于强化学习缓存与计算的联合优化，应用在NOMA-MEC系统中，其中主要涉及多用户、多MEC服务器的 NOMA-MEC系统的联合缓存和卸载问题。通过将单个服务器的本地缓存扩展到多个服务器的协作缓存，服务器之间可以共享计算结果。为了使整个系统的时延最小，需要找到每个用户最优的缓存和卸载策略。

如图1所示，本申请提出了基于强化学习缓存与计算的联合优化，应用在NOMA-MEC系统中，通过将单个服务器的本地缓存扩展到多个服务器的协作缓存，多个服务器之间可以共享计算结果，为了使整个系统的时延最小，找到每个用户最优的缓存和卸载策略，包括：

第一步，针对用户不同的决策方式，生成本地缓存，协作缓存，本地计算和卸载计算模式下的时延函数。

1)对于选择本地缓存的用户来说，与协作缓存和卸载计算相比，它的时延是忽略不计的。

2)在协作缓存模式下，处理任务的时延主要是服务器间传输产生的时延 T_m,n：

其中r_m,n表示本地服务器m和协作服务器n的下载速率，M_j代表任务j计算结果的大小。

3)如果用户选择卸载计算，为了提高频谱利用率，进一步降低传输时延，采用NOMA技术将信息传输到本地基站。处理任务的时延由卸载时延

在 MEC服务器上的处理时延

和回传时延

三部分组成。由于回传时延较小，一般可以忽略。

针对选择本地计算的用户，本地执行时延为

其中W_j表示处理任务j总的CPU周期数，f_i ^l是用户i在本地计算阶段的计算容量。

第二步，决定在MEC服务器上缓存的内容。考虑到任务流行度是动态的和未知的，提出门控递归单元(Gated Recurrent Unit，GRU)算法来预测任务流行度，将流行度高的计算结果放置在相应的服务器上。具体过程如下：

1)收集用户在历史时刻请求的任务和不同任务的计算结果，执行下面的操作。

2)输入历史时期的流行度{S_j(1),S_j(2),···S_j(T_M)}，其中,S_j(t)表示任务j在时间t上的流行度。经过GRU单元，得到长度为T_N的预测的流行度 {S_j(T_M+1)，S_j(T_M+2),···S_j(T_M+T_N)}。

3)计算预测流行度q(j)和在预测时刻到来时真实流行度p(j)之间的损失函数

通过不断调整参数，使损失函数变小。

4)直到损失函数不再发生变化，停止训练，否则，返回1)。

由于服务器的缓存空间有限，很难存储所有任务的结果，考虑到服务器的缓存容量和计算结果的大小，将任务的计算结果按流行度由大到小的顺序缓存在服务器上，以便尽可能多地缓存任务的计算结果。在这种方式下，其他服务器也使用GRU算法来缓存相应的计算结果。在所有用户请求任务之前，这些服务器已经放置了流行任务的计算结果，这有利于命中本地缓存和协作缓存。

第三步，基于服务器上缓存的计算结果，利用多代理深度Q网络 (Multi-agentDeep-Q-network，MADQN)算法寻找最优的缓存和卸载决策。

在多代理系统中，将相同基站中的每个用户视为代理。每个代理在做决策前，不知道其他代理的行为。根据环境的状态信息，代理选择自己的动作。在选择动作前，需要判断命中的情况。根据状态信息和用户请求的任务，用户可以知道是否命中了本地缓存还是协作缓存。只有当缓存被命中时，用户才能选择缓存决策。在代理获得状态信息和做出动作选择后，环境会反馈给代理奖励信息用于判断动作的好坏。考虑到奖励值，代理不断地调整自己的行为来让奖励最大化。MADQN算法的具体过程如下:

1)初始化状态s_i，动作a_i，奖励r_i，当前Q网络Q(s,a；θ)和目标Q网络

等变量。

2)对于每个代理，观察初始状态

其中μ(t)是在时间t上，存储在所有服务器上任务的序号。

表示用户i在本地服务器m上的时延。

是MEC服务器剩余的计算容量。ξ(t)代表在同一基站中N个用户可利用的能耗。

3)根据贪心算法选择动作

代理以高概率1-ε选择最优的决策。否则，它将以ε的概率随机的选择缓存和卸载决策。其中

是任务卸载决策，

表示本地计算决策，

分别表示本地缓存和协作缓存决策，ε为影响因子。

4)更新奖励r_i(t)＝T_i(t-1)-T_i(t)，其中T_i(t)和T_i(t-1)分别表示用户i在时间t和t-1上的时延。

5)存储代理i在时间t上的经验e_i(t)到经验回放单元D(t)中，训练时从中抽取小批量的转移序列。

6)使用随机梯度下降法更新损失函数L(t)。

7)更新下一个状态s(t+1)←s(t)。

8)直到参数θ收敛停止训练。

按照上述方法，缓存和卸载决策的选择可以被执行在其他基站的用户中，由于整个系统的时延是由多个基站的时延组成，所以最小化整个系统的时延可以通过减少不同基站的时延来实现。

可见，本发明实施例提供了基于强化学习NOMA-MEC系统中缓存与计算的联合优化，也可以说是一种基于强化学习的方法，联合优化NOMA-MEC 系统中的缓存和计算。首先，考虑到多服务器间的计算结果缓存和任务卸载的问题，利用多服务间协作缓存的方式来提高缓存命中率。其次，考虑到任务流行度是动态的和未知的这种更为合理的情况，提出门控递归单元这种新颖的任务流行度的预测方法，该算法是第一次被用于任务流行度的预测。利用这种算法去预测任务流行度，对于随时间动态变化的流行度，通过适当的增加学习率，它预测的更加准确。最后，基于预测的流行度，多代理深度Q 网络算法被用来自主的选择缓存和卸载决策，通过不断地训练，它可以达到最小化时延的目的。

综上可知，本申请具有以下优点：

(1)通过将单个服务器的本地缓存扩展到多个服务器的协作缓存，计算结果可以在多服务器间共享，比较单个服务器的本地缓存，多服务器间的协作缓存能够提高缓存命中率。也就是说，本申请考虑到多服务器间的计算结果缓存和任务卸载的问题，利用多服务间协作缓存的方式来提高缓存命中率。

(2)提出将NOMA和MEC结合的计算结果缓存方法去解决有限计算资源和频谱资源的问题。

(3)考虑到任务流行度是动态的和未知的这种更为合理的情况。针对这种更合理的情况，本申请提出GRU这种新颖的任务流行度的预测方法，利用 GRU算法去预测任务流行度，对于随时间动态变化的流行度，通过适当的增加学习率，它预测的更加准确。而该算法是第一次被用于任务流行度的预测。

(4)基于预测的流行度，提出MADQN算法去优化缓存和卸载决策，它可以在状态动作空间大的情况下，找到最优的缓存和卸载策略，从而使系统的时延最小。该MADQN算法被用来自主的选择缓存和卸载决策，通过不断地训练，它可以达到最小化时延的目的。

本说明书中各个部分采用递进的方式描述，每个部分重点说明的都是与其他部分的不同之处，各个部分之间相同相似部分互相参见即可。

对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。

Claims (1)

1.基于强化学习缓存与计算的联合优化，其特征在于，应用在NOMA-MEC系统中，通过将单个服务器的本地缓存扩展到多个服务器的协作缓存，多个服务器之间可以共享计算结果，为了使整个系统的时延最小，找到每个用户最优的缓存和卸载策略，所述方法包括：

第一步，针对用户不同的决策方式，生成本地缓存，协作缓存，本地计算和卸载计算模式下的时延函数。

第二步，考虑到任务流行度是动态的和未知的，提出门控递归单元算法来预测任务流行度，将流行度高的计算结果放置在相应的移动边缘计算服务器上进行缓存。

第三步，基于服务器上缓存的计算结果，利用多代理深度Q网络算法寻找最优的缓存和卸载决策。

其中，所述针对用户不同的决策方式，生成本地缓存，协作缓存，本地计算和卸载计算模式下的时延函数，具体包括：

1)对于选择本地缓存的用户来说，与协作缓存和卸载计算相比，它的时延是忽略不计的。

2)在协作缓存模式下，处理任务的时延主要是服务器间传输产生的时延T_m,n：

其中r_m,n表示本地服务器m和协作服务器n的下载速率，M_j代表任务j计算结果的大小。

3)如果用户选择卸载计算，为了提高频谱利用率，进一步降低传输时延，采用NOMA技术将信息传输到本地基站。处理任务的时延由卸载时延

在MEC服务器上的处理时延

和回传时延

三部分组成。由于回传时延较小，一般可以忽略。

针对选择本地计算的用户，本地执行时延为

其中W_j表示处理任务j总的CPU周期数，f_i ^l是用户i在本地计算阶段的计算容量。

其中，所述考虑到任务流行度是动态的和未知的，提出门控递归单元算法来预测任务流行度，将流行度高的计算结果放置在相应的移动边缘计算服务器上进行缓存，具体包括：

1)收集用户在历史时刻请求的任务和不同任务的计算结果，执行下面的操作。

2)输入历史时期的流行度{S_j(1),S_j(2),…S_j(T_M)}，其中,S_j(t)表示任务j在时间t上的流行度。经过GRU单元，得到长度为T_N的预测的流行度{S_j(T_M+1)，S_j(T_M+2),…S_j(T_M+T_N)}。

3)计算预测流行度q(j)和在预测时刻到来时真实流行度p(j)之间的损失函数

通过不断调整参数，使损失函数变小。

4)直到损失函数不再发生变化，停止训练，否则，返回1)。

由于服务器的缓存空间有限，很难存储所有任务的结果，考虑到服务器的缓存容量和计算结果的大小，将任务的计算结果按流行度由大到小的顺序缓存在服务器上，以便尽可能多地缓存任务的计算结果。在这种方式下，其他服务器也使用GRU算法来缓存相应的计算结果。在所有用户请求任务之前，这些服务器已经放置了流行任务的计算结果，这有利于命中本地缓存和协作缓存。

其中，所述基于服务器上缓存的计算结果，利用多代理深度Q网络算法寻找最优的缓存和卸载决策，具体包括：

在多代理系统中，将相同基站中的每个用户视为代理。每个代理在做决策前，不知道其他代理的行为。根据环境的状态信息，代理选择自己的动作。在选择动作前，需要判断命中的情况。根据状态信息和用户请求的任务，用户可以知道是否命中了本地缓存还是协作缓存。只有当缓存被命中时，用户才能选择缓存决策。在代理获得状态信息和做出动作选择后，环境会反馈给代理奖励信息用于判断动作的好坏。考虑到奖励值，代理不断地调整自己的行为来让奖励最大化。MADQN算法的具体过程如下:

1)初始化状态s_i，动作a_i，奖励r_i，当前Q网络Q(s,a；θ)和目标Q网络

等变量。

2)对于每个代理，观察初始状态

其中μ(t)是在时间t上，存储在所有服务器上任务的序号。

表示用户i在本地服务器m上的时延。

是MEC服务器剩余的计算容量。ξ(t)代表在同一基站中N个用户可利用的能耗。

3)根据贪心算法选择动作

代理以高概率1-ε选择最优的决策。否则，它将以ε的概率随机的选择缓存和卸载决策。其中

是任务卸载决策，

表示本地计算决策，

和

分别表示本地缓存和协作缓存决策，ε为影响因子。

4)更新奖励r_i(t)＝T_i(t-1)-T_i(t)，其中T_i(t)和T_i(t-1)分别表示用户i在时间t和t-1上的时延。

5)存储代理i在时间t上的经验e_i(t)到经验回放单元D(t)中，训练时从中抽取小批量的转移序列。

6)使用随机梯度下降法更新损失函数L(t)。

7)更新下一个状态s(t+1)←s(t)。

8)直到参数θ收敛停止训练。

按照上述方法，缓存和卸载决策的选择可以被执行在其他基站的用户中，由于整个系统的时延是由多个基站的时延组成，所以最小化整个系统的时延可以通过减少不同基站的时延来实现。

Images