一种基于强化学习的多边缘协同负载均衡任务调度方法与流程

1.本发明涉及边缘计算中的负载均衡调度策略领域，特别是一种基于强化学习的多边缘协同负载均衡任务调度方法。
背景技术：
：：2.近年来，移动计算技术的进步使得用户能够体验到各种各样的应用程序。然而，随着新开发的应用程序的资源需求不断增长，移动设备的计算能力仍然有限。克服移动设备资源匮乏的传统方法是利用远程云中丰富的计算资源。移动设备通过将计算密集型任务卸载到远程云上执行，可以减轻其工作负载并延长电池寿命。然而，云和用户之间的长距离会导致用户交互频繁的应用程序出现延迟，影响用户体验。为了尽量减少任务卸载到远程云的延迟，研究人员建议使用更靠近用户的边缘来进行任务卸载。3.边缘是一个资源丰富的计算机集群，通过无线网路连接到附近的移动用户。通过提供对其丰富计算资源的低延迟访问，边缘可以显著提高移动应用程序的性能。尽管边缘通常被定义为孤立的“盒子中的数据中心”，但将多个边缘连接在一起形成网络有明显的好处。城市通常人口密度较高，这意味着边缘将可供大量用户使用。这提高了边的成本效益，因为它们不太可能空闲。此外，由于网络的规模，无线城域网服务提供商在通过无线城域网提供边缘服务时可以利用规模经济，使边缘服务更能为公众所接受。4.无线城域网服务提供商面临的一个主要问题是如何将用户的任务请求分配到不同的边缘，从而使无线城域网中边缘之间的工作负载得到很好的平衡，从而缩短任务的响应时延，增强用户使用服务的体验。具体来说，网络中的大量用户意味着每个边缘的工作负载都将是高度不稳定的。如果边缘突然被用户请求淹没，边缘的任务响应时间将急剧增加，从而导致用户应用程序的延迟和用户体验的降低。为了防止某些边缘过载，将用户请求分配给不同的边缘非常重要，这样边缘之间的工作负载就可以很好地平衡，从而减少最大响应时间。技术实现要素：5.有鉴于此，本发明的目的是提供种基于强化学习的多边缘协同负载均衡任务调度方法，用于解决无线城域网中的多边缘协同负载均衡问题，每个边缘节点基于局部信息，独立进行本节点和相邻节点间的负载均衡调度，通过强化学习和机器学习结合的方法进行单次调度决策，经过反馈控制和多边缘协同，逐步寻找合适的负载均衡方案，可以有效地减少任务的响应时间。6.本发明采用以下方案实现：一种基于强化学习的多边缘协同负载均衡任务调度方法，包括以下步骤：7.步骤s1：根据历史数据集，使用强化学习算法来评估不同多边缘协同系统状态下各调整操作的q值；8.步骤s2：对步骤s1中构建q值表中调整操作的q值进行预处理，然后用机器学习算法训练一个q值预测模型；9.步骤s3：每个边缘根据q值预测模型独立并行地进行决策。10.进一步地，步骤s1中所述强化学习算法为：11.状态空间：边缘ei的每一个状态用一个三元组＜λi,li＞表示，分别为边缘ei的任务到达率λi，边缘ei的当前局部负载均衡方案和边缘ei及其相邻边缘的负载率li；12.动作空间：边缘ei的动作空间用表示，其中，表示增加边缘ei的到达任务中调度到相邻边缘上执行的任务量；表示减少边缘ei的到达任务中调度到相邻边缘上执行的任务量；13.奖励函数：奖励函数定义如下：[0014][0015]所述强化学习算法采用的是q‑learning算法，q值更新公式如下：[0016]q(s,a)＝q(s,a) α[r γ·max(q(s',a'))‑q(s,a)][0017]其中，max(q(s',a'))表示在状态s'时选择动作a'所获得的最大q值，参数α表示学习效率，参数γ表示奖励折扣。[0018]进一步地，所述步骤s1具体包括以下步骤：[0019]步骤s11：初始化q值表；[0020]步骤s12：使用q‑learning算法评估每一条历史数据中调整操作的q值，训练过程一直持续到q值收敛；[0021]步骤s13：得到一个q值表，记录不同时刻的边缘ei的任务到达率，边缘ei的当前局部负载均衡方案和边缘ei及其相邻边缘的负载率li，以及每个调整操作对应的q值。[0022]进一步地，所述步骤s12具体包括以下步骤：[0023]步骤s121：在每一回合中，首先随机初始化当前局部负载均衡方案并且生成当前系统状态；[0024]初始化当前局部负载均衡方案[0025][0026]边缘ei的每一个状态用一个三元组＜λi,li＞表示，分别为边缘ei的任务到达率λi，边缘ei的当前局部负载均衡方案和边缘ei及其相邻边缘的负载率li；[0027]步骤s122：如果当前局部负载均衡方案不是目标局部负载均衡方案循环执行步骤s123至步骤s125；[0028]步骤s123：根据ε‑greedy策略从动作空间中选取一个动作a；用ε‑greedy策略选择一个动作a：[0029]a＝select_action(s,q_table)；[0030]步骤s124：在状态转移函数的作用下到达状态s'并且获得奖励r；[0031]当前状态在状态转移函数作用下转变为s'：[0032]s'＝t(s,a)[0033]代理获得奖励值：[0034][0035]步骤s125：再根据下述公式更新q值，最后用状态s'代替当前状态s；[0036]更新q值：[0037]q(s,a)＝q(s,a) α[r γ·max(q(s',a'))‑q(s,a)][0038]更新当前状态：[0039]s＝s'。[0040]进一步地，步骤s2中所述[0041]对q值进行了预处理，处理规则如下：[0042][0043]如果q_value＝＝0and对应的调整操作被认为是不合法的，这些q值将被标记为i；如果即找到了目标局部负载均衡方案，则q值仍设为0；对于其余情况，将q值设为其倒数；预处理后，除了被标记为i的q值，当前局部负载均衡方案越接近目标局部负载均衡方案调整操作的q值越小，找到目标局部负载均衡方案时，q值为最小值0；基于预处理后的q值表，使用svr算法来训练q值预测模型，其回归方程表示为：[0044][0045]其中，m是训练样本的数量，κ(x,xi)是核函数，其余参数是模型参数；将高斯核作为核函数,即[0046][0047]其中χ＞0是高斯核的带宽。[0048]进一步地，所述步骤s3的具体内容为：[0049]采用调整操作决策算法，利用q值预测模型，在决策时预测不同多边缘协同系统状态下各个操作的q值，并选择q值最小的动作；设定一个阈值t，当每个调整操作对应的q值均小于阈值t时，则认为当前局部负载均衡方案已经足够接近目标局部负载均衡方案，此时，将当前局部负载均衡方案近似地作为目标局部负载均衡方案；调整操作决策算法的输入包括边缘ei的任务到达率λi、边缘ei的当前局部负载均衡方案以及边缘ei和相邻边缘的负载率li，输出是边缘ei的下一个负载均衡调整操作a；其具体过程如下：[0050]首先，评估各个动作即调整操作的q值；如果一个动作被认为是不合法的，则将对应的q值标记为i；其他情况下，根据q值预测模型预测每个动作对应的q值；[0051][0052]其中，prediction_model()‑调用q值预测模型[0053]q_value(a)‑动作a的q值[0054]然后，判断所有合法调整操作的q值是否均小于阈值t，其中，除了被标记为i的q值；如果所有动作的q值均小于阈值t，则认为已经找到了目标局部负载均衡方案，无需再进行调整，调整操作为null；否则选择q值最小的调整操作，如果存在多个调整操作的q值一样且为最小q值，则从中随机选取一个调整操作；[0055]if(foreachq_value(a)≤t||q_value(a)＝＝i):[0056]a＝null[0057]else:[0058]记录q值最小且不为i的动作：[0059]a_list＝ai.getaction_minqvalue()[0060]从a_list里面随机选取一个动作：[0061]a＝a_list.get_action_random()[0062]最后，返回所选取的边缘ei的下一个负载均衡调整操作a。[0063]与现有技术相比，本发明具有以下有益效果：[0064]本发明将强化学习和机器学习相结合，设计无线城域网中的多边缘协同负载均衡方法。每个边缘节点仅利用局部信息，便可独立进行本节点和相邻节点间的负载均衡调度，经过反馈控制和多边缘协同逐步寻找合适的负载均衡方案。所寻找的方案可以有效地减少任务的响应时间。附图说明[0065]图1为本发明实施例的总框架图。[0066]图2为本发明实施例的与传统方法的性能对比图。具体实施方式[0067]下面结合附图及实施例对本发明做进一步说明。[0068]应该指出，以下详细说明都是例示性的，旨在对本技术提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本技术所属
技术领域：
：的普通技术人员通常理解的相同含义。[0069]需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本技术的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。[0070]图1、2所示，本实施例提供一种基于强化学习的多边缘协同负载均衡任务调度方法，包括以下步骤：[0071]步骤s1：根据历史数据集，使用强化学习算法来评估不同多边缘协同系统状态下各调整操作的q值；其中，多边缘协同系统是指无线城域网中的多边缘协同系统，由多个通过无线城域网互相连接的边缘组成。[0072]步骤s2：对步骤s1中构建q值表中调整操作的q值进行预处理，然后用机器学习算法训练一个q值预测模型；[0073]步骤s3：每个边缘根据q值预测模型独立并行地进行决策。[0074]在本实施例中，步骤s1中所述强化学习算法为：[0075]状态空间：边缘ei的每一个状态用一个三元组＜λi,li＞表示，分别为边缘ei的任务到达率λi，边缘ei的当前局部负载均衡方案和边缘ei及其相邻边缘的负载率li；[0076]动作空间：边缘ei的动作空间用表示，其中，表示增加边缘ei的到达任务中调度到相邻边缘上执行的任务量；表示减少边缘ei的到达任务中调度到相邻边缘上执行的任务量；[0077]奖励函数：奖励函数定义如下：[0078][0079]所述强化学习算法采用的是q‑learning算法，q值更新公式如下：[0080]q(s,a)＝q(s,a) α[r γ·max(q(s',a'))‑q(s,a)][0081]其中，max(q(s',a'))表示在状态s'时选择动作a'所获得的最大q值，参数α表示学习效率，参数γ表示奖励折扣。[0082]在本实施例中，所述步骤s1具体包括以下步骤：[0083]步骤s11：初始化q值表；[0084]步骤s12：使用q‑learning算法评估每一条历史数据中调整操作的q值，训练过程一直持续到q值收敛；[0085]步骤s13：得到一个q值表，记录不同时刻的边缘ei的任务到达率，边缘ei的当前局部负载均衡方案和边缘ei及其相邻边缘的负载率li，以及每个调整操作对应的q值。[0086]在本实施例中，所述步骤s12具体包括以下步骤：[0087]步骤s121：在每一回合中，首先随机初始化当前局部负载均衡方案并且生成当前系统状态；[0088]初始化当前局部负载均衡方案[0089][0090]边缘ei的每一个状态用一个三元组＜λi,li＞表示，分别为边缘ei的任务到达率λi，边缘ei的当前局部负载均衡方案和边缘ei及其相邻边缘的负载率li；[0091]步骤s122：如果当前局部负载均衡方案不是目标局部负载均衡方案循环执行步骤s123至步骤s125；[0092]步骤s123：根据ε‑greedy策略从动作空间中选取一个动作a；用ε‑greedy策略选择一个动作a：[0093]a＝select_action(s,q_table)；[0094]步骤s124：在状态转移函数的作用下到达状态s'并且获得奖励r；[0095]当前状态在状态转移函数作用下转变为s'：[0096]s'＝t(s,a)[0097]代理获得奖励值：[0098][0099]步骤s125：再根据下述公式更新q值，最后用状态s'代替当前状态s；[0100]更新q值：[0101]q(s,a)＝q(s,a) α[r γ·max(q(s',a'))‑q(s,a)][0102]更新当前状态：[0103]s＝s'。[0104]在本实施例中，步骤s2中所述[0105]对q值进行了预处理，处理规则如下：[0106][0107]如果q_value＝＝0and对应的调整操作被认为是不合法的，这些q值将被标记为i；如果即找到了目标局部负载均衡方案，则q值仍设为0；对于其余情况，将q值设为其倒数；预处理后，除了被标记为i的q值，当前局部负载均衡方案越接近目标局部负载均衡方案调整操作的q值越小，找到目标局部负载均衡方案时，q值为最小值0；基于预处理后的q值表，使用svr算法来训练q值预测模型，(训练q值预测模型，即为训练回归方程中的参数)其回归方程表示为：[0108][0109]其中，m是训练样本的数量，κ(x,xi)是核函数，其余参数是模型参数；将高斯核作为核函数,即[0110][0111]其中χ＞0是高斯核的带宽。[0112]在本实施例中，所述步骤s3的具体内容为：[0113]采用调整操作决策算法，利用q值预测模型，在决策时预测不同多边缘协同系统状态下各个操作的q值，并选择q值最小的动作；设定一个阈值t，当每个调整操作对应的q值均小于阈值t时，则认为当前局部负载均衡方案已经足够接近目标局部负载均衡方案，此时，将当前局部负载均衡方案近似地作为目标局部负载均衡方案；调整操作决策算法的输入包括边缘ei的任务到达率λi、边缘ei的当前局部负载均衡方案以及边缘ei和相邻边缘的负载率li，输出是边缘ei的下一个负载均衡调整操作a；其具体过程如下：[0114]首先，评估各个动作即调整操作的q值；如果一个动作被认为是不合法的，则将对应的q值标记为i；其他情况下，根据q值预测模型预测每个动作对应的q值；[0115][0116]其中，prediction_model()‑调用q值预测模型[0117]q_value(a)‑动作a的q值[0118]然后，判断所有合法调整操作的q值是否均小于阈值t，其中，除了被标记为i的q值；如果所有动作的q值均小于阈值t，则认为已经找到了目标局部负载均衡方案，无需再进行调整，调整操作为null；否则选择q值最小的调整操作，如果存在多个调整操作的q值一样且为最小q值，则从中随机选取一个调整操作；[0119]if(foreachq_value(a)≤t||q_value(a)＝＝i):[0120]a＝null[0121]else:[0122]记录q值最小且不为i的动作：[0123]a_list＝ai.getaction_minqvalue()[0124]从a_list里面随机选取一个动作：[0125]a＝a_list.get_action_random()[0126]最后，返回所选取的边缘ei的下一个负载均衡调整操作a。[0127]较佳的，在本实施例中，符号定义如下：[0128]定义1：无线城域网中部署部署的边缘集合表示为e＝{e1,e2,...,en}，其中ei表示第i个边缘，n是边缘总数。[0129]定义2：n个边缘的服务速率用v＝{v1,v2,...,vn}表示，其中，vi表示边缘ei的服务速率。[0130]定义3：n个边缘之间的单位任务传输时间表示为：[0131][0132]其中，di,j表示边缘ei和边缘ej之间的任务传输时间。[0133]定义4：n个边缘的任务到达率用λ＝{λ1,λ2,...,λn}表示，其中λi＞0表示边缘ei的任务到达率。为了方便描述，以下将用户卸载到边缘的初始任务称为边缘的到达任务。定义5：全局负载均衡方案表示为：[0134][0135]其中，fi表示边缘ei的局部负载均衡方案。[0136]定义6：n个边缘的实际任务负载表示为w＝{w1,w2,...,wn}，其中wi＞0表示单位时间内边缘ei的实际任务量。[0137]定义7：单位时间内边缘ej的实际任务负载率表示为：[0138][0139]较佳的，在本实施例中问题定义如下：[0140]定义8：基于排队论，任务在不同边缘上的平均执行时间为：[0141][0142]定义9：任务响应时间由执行时间和传输时间组成，于是，单位时间内边缘ei的到达任务中调度到相邻边缘ej上执行的任务的平均响应时间为：[0143]ti,j＝ta(lj) di,j[0144]定义10：边缘ei上的到达任务的平均响应时间tri为：[0145][0146]定义11:n个边缘上的到达任务的最大平均响应时间为：[0147][0148]定义12：:目标函数为：[0149]min(tmax)[0150]即最小化n个边缘上的到达任务的最大平均响应时间。[0151]强化学习：[0152]状态空间：边缘ei的每一个状态用一个三元组＜λi,li＞表示，分别为边缘ei的任务到达率λi，边缘ei的当前局部负载均衡方案和边缘ei及其相邻边缘的负载率li。[0153]动作空间：边缘ei的动作空间用表示，其中，表示增加边缘ei的到达任务中调度到相邻边缘上执行的任务量；表示减少边缘ei的到达任务中调度到相邻边缘上执行的任务量。[0154]奖励函数：本文的奖励函数定义如下：[0155][0156]本实施例的强化学习算法采用的是q‑learning算法，q值更新公式如下：[0157]q(s,a)＝q(s,a) α[r γ·max(q(s',a'))‑q(s,a)][0158]其中，max(q(s',a'))表示在状态s'时选择动作a'所获得的最大q值，参数α表示学习效率，参数γ表示奖励折扣。[0159]基于上述定义，根据表3的数据集，q‑learning算法被用于评估不同调整操作的q值，如算法1所示。首先，初始化q值表(第1行)。然后，使用q‑learning算法评估每一条历史数据中调整操作的q值，训练过程一直持续到q值收敛(2‑12行)。在每一回合中，首先随机初始化当前局部负载均衡方案并且生成当前系统状态(第3行)。然后如果当前局部负载均衡方案不是目标局部负载均衡方案循环执行以下过程(第5‑11行)：首先根据ε‑greedy策略从动作空间中选取一个动作a(第6行)，然后在状态转移函数的作用下到达状态s'并且获得奖励r(第7‑8行)。接下来，再根据公式(9)更新q值(第9行)。最后用状态s'代替当前状态s(第10行)。[0160]于是，可以得到一个q值表，记录不同时刻的边缘ei的任务到达率，边缘ei的当前局部负载均衡方案和边缘ei及其相邻边缘的负载率li，以及每个调整操作对应的q值。[0161][0162][0163]q值预测模型：[0164]对q值进行了预处理，处理规则如下：[0165][0166]如果q_value＝＝0and对应的调整操作被认为是不合法的，这些q值将被标记为i。如果(即找到了目标局部负载均衡方案)，则q值仍设为0。对于其余情况，将q值设为其倒数。预处理后，除了被标记为i的q值，当前局部负载均衡方案越接近目标局部负载均衡方案调整操作的q值越小，找到目标局部负载均衡方案时，q值为最小值0。基于预处理后的q值表，使用svr算法来训练q值预测模型，其回归方程可表示为：[0167][0168]其中，m是训练样本的数量，κ(x,xi)是核函数，其余参数是模型参数。我们选择高斯核作为核函数,即[0169][0170]其中χ＞0是高斯核的带宽。[0171]局部负载均衡调度算法：[0172]首先，初始化边缘ei的当前负载均衡方案(第1行)，即边缘ei的到达任务均在本节点上执行。[0173]然后，边缘ei重复执行以下过程(第2～11行)：[0174]第一步：边缘ei获取自身和相邻边缘的负载率li(第3行)。[0175]第二步：使用边缘ei的任务到达率λi，边缘ei的当前局部负载均衡方案和边缘ei及其相邻边缘的负载率li作为输入，根据算法3得到边缘ei的下一个负载均衡调整操作(第4行)。[0176]第三步：如果算法3返回的调整操作为空，则说明边缘ei已经找到了目标局部负载均衡方案，无需再进行调整(第5～6行)；否则，边缘ei执行得到的调整操作并更新当前局部负载均衡方案(第7～9行)。[0177][0178]算法3是利用q值预测模型，在决策时预测不同系统状态下各个操作的q值，并选择q值最小的动作。我们设定一个阈值t，当每个调整操作对应的q值均小于阈值t时，我们就认为当前局部负载均衡方案已经足够接近目标局部负载均衡方案，此时，可以将当前局部负载均衡方案近似地作为目标局部负载均衡方案。[0179]算法3的输入包括边缘ei的任务到达率λi、边缘ei的当前局部负载均衡方案以及边缘ei和相邻边缘的负载率li，输出是边缘ei的下一个负载均衡调整操作a。其具体过程如下：[0180]首先，评估各个动作(调整操作)的q值。如果一个动作被认为是不合法的，则将对应的q值标记为i；其他情况下，根据q值预测模型预测每个动作对应的q值(1～7行)。[0181]然后，判断所有合法调整操作的q值是否均小于阈值t(除了被标记为i的q值)。如果所有动作的q值均小于阈值t，则认为已经找到了目标局部负载均衡方案，无需再进行调整，调整操作为null。否则选择q值最小的调整操作，如果存在多个调整操作的q值一样且为最小q值，则从中随机选取一个调整操作(8～13行)。[0182]最后，返回所选取的边缘ei的下一个负载均衡调整操作a(第14行)。[0183][0184][0185]较佳的，本实施例在上海市的无线基站分布图上随机选取五个区域，设计了五个不同的仿真场景。在每个场景中，边缘总数n＝15，在每个区域中随机选取15个无线基站的经纬坐标作为边缘的坐标，每个边缘的任务到达率λi满足正态分布n(10,4)，服务速率vi满足正态分布n(15,6)；每个边缘连接其他边缘的数量0＜k≤3，边缘间的单位任务传输时间d，根据它们间的距离映射到区间[0.1,0.2]，两个边缘间的距离越近，单位任务的传输时间越小。强化学习的迭代回合数(episode)、学习效率α、奖励折扣γ分别设置为100、0.1、0.9。ε‑greedy策略中设置ε＝0.1。阈值t设为0.15。[0186]将本实施例所提出的方法(rf‑clb)和经典ml‑based方法和rule‑based方法进行比较，实验结果如图所示。实验结果表明，rf‑clb得到的负载均衡方案的响应时间分别比经典ml‑based方法和rule‑based方法的小6～9％和10～12％。[0187]以上所述仅为本发明的较佳实施例，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本发明的涵盖范围。当前第1页12当前第1页12