无线城域网中基于两阶段决策的多边缘协同负载均衡方法

1.本发明涉及移动边缘计算技术领域，具体涉及一种无线城域网中基于两阶段决策的多边缘协同负载均衡方法。


背景技术：

2.随着移动通信技术和物联网的快速发展，移动设备(如智能手机、车辆、无人机)表现出更大的资源需求，以确保其在无线城域网(wmans)环境处理计算密集型任务方面的高性能。然而，移动设备受自身尺寸大小的约束，其计算能力和存储容量存在明显的局限性。通过将移动设备上的计算密集型任务卸载到的远程云服务器上，可以在一定程度上缓解移动设备的资源限制问题。
3.然而，由于移动设备与远程云服务器之间的地理位置距离较远，会导致较长的响应时延。这个问题可以通过引入移动边缘计算得到很好的缓解，它将计算资源从核心网络下沉到网络边缘。因此，将计算密集型任务从移动设备卸载到附近的边缘来执行，可以减少无线城域网环境中的响应时延。
4.在边缘环境中，部署在无线基站的边缘服务器可以为附近的移动设备提供低延迟的访问以及强大的计算能力，从而提高移动设备的性能。基于此，边缘可以被视为在无线城域网环境中提升用户服务质量(qos)的一个重要补充手段。通常，来自移动设备的任务倾向于被卸载到其最近的边缘来执行，但是这可能不是最佳选择，因为在wmans中的不同边缘存在波动负载。例如，当许多移动设备(如智能手机、车辆、无人机)同时在边缘的覆盖范围内工作，会导致边缘的负载率急剧上升，以及响应延时的增加。为了解决这个问题并提升用户的qos，多边缘协同机制是一种可行的解决方案。
5.目前，解决负载均衡问题的方法主要使用集中决策或分散决策的模式。一部分基于集中决策的方式采用了启发式或机器学习(ml)算法。然而，在具有大量广泛分布边缘的wmans中收集所有边缘的实时信息，这可能造成过多的决策时间和通信开销。启发式算法可能会消耗大量的搜索时间来寻找目标负载均衡方案，从而使得很难满足移动应用的实时服务需求。ml算法无法在数据支持不足的情况下建立准确的负载均衡决策模型。另一部分基于分散决策的方式，与集中决策方式相比，可以实现更好的可扩展性。然而，它们可能仅仅获得局部最优而不是全局最优，因为它们在负载均衡的决策过程中仅仅使用局部信息。因此，需要寻找高效的多边缘协同负载均衡方法，以在动态变化的wmans环境中实现多边缘间的负载均衡。


技术实现要素：

6.考虑在无线城域网环境中，由于各个边缘的负载情况处于动态变化，因此需要通过任务调度来实现边缘间的负载平衡。本发明使用的无线城域网中基于两阶段决策的多边缘协同负载均衡方法能够在秒级完成负载均衡任务调度方案的求解过程，生成高效的负载均衡方案，满足多边缘间的负载均衡的实时性需求。
ec的模型置信度总是超过95％，并且选择调整操作的平均准确率达到92.5％。
附图说明
17.下面结合附图和具体实施方式对本发明进一步详细的说明：
18.图1是本发明实施例建立的无线城域网中的多边缘协同负载均衡模型示意图；
19.图2是本发明实施例方法概览图；
20.图3是本发明实施例包含5个边缘的拓扑图示例图；
21.图4是本发明实施例dqn架构图；
22.图5是本发明实施例实验场景示意图；
23.图6是本发明实施例在不同场景下，tdb-ec与理想方案的最大平均响应时间对比图；
24.图7是本发明实施例不同场景中负载均衡方案评估模型的置信度示意图；
25.图8是本发明实施例距离理想方案不同调整次数时操作决策的正确率示意图；
26.图9是本发明实施例从最大平均响应时间的角度，tdb-ec与三种基准方法的比较示意图；
27.图10是本发明实施例tdb-ec与三种基准方法的所有任务平均响应时间的比较示意图。
具体实施方式
28.为让本专利的特征和优点能更明显易懂，下文特举实施例，作详细说明如下：
29.应该指出，以下详细说明都是例示性的，旨在对本技术提供进一步的说明。除非另有指明，本说明书使用的所有技术和科学术语具有与本技术所属技术领域的普通技术人员通常理解的相同含义。
30.需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本技术的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。
31.以下对本发明实施例方案做具体的说明：
32.1、问题定义
33.如图1所示，在本实施例所构建的模型当中，一组边缘放置于wmans环境中的无线接入点上，并且边缘间可以通过无线网络进行交互。本实施例假设移动设备上的应用程序可以被动态地划分为独立的、且能在任意一个边缘上处理的可卸载任务。由于用户的移动性，移动设备的分布是高度可变的，这导致了边缘处的负载不均衡。高负载导致执行任务的响应延迟增大，而低负载导致严重的资源浪费。为此，需要对wman中的多边缘进行协同负载均衡，以减少任务的响应延迟并提高边缘的资源利用率。
34.本实施例假设一个wman中部署了n个边缘，用e＝{e1,e2,
…
,en}表示。其中，ei表示第i个边缘，且每个边缘ei仅和邻近的c个边缘相连(后续将通过无线网络互连的两个边缘称为相邻边缘)。边缘的服务速率定义为集合v＝{v1,v2,
…
,vn}，其中vi代表边缘ei的服务速率，即边缘ei在单位时间内能够完成的任务量。
35.然后，在wman中每对相邻边缘间的单位任务传输时延d定义如下：
[0036][0037]
其中，d
i,j
代表两个边缘(即ei和ej)之间单位任务传输时延。特别地，如果i＝j，则d
i,j
＝0。当边缘ei没有和边缘ej相互连接，则d
i,j
＝∞。
[0038]
接着，边缘的任务到达率定义为集合λ＝{λ1,λ2,
…
,λn}，λi代表边缘ei的任务到达率，即单位时间内卸载到边缘ei的任务量。特别地，这些卸载任务被称为到达任务。一个边缘的到达任务可以在本地或者调度到其相邻边缘上处理，以保证边缘间的负载均衡。
[0039]
同时，边缘集合e的全局负载均衡方案f
mat
定义如下：
[0040][0041]
其中，只有一个边缘的到达任务可以被调度，而不能调度接收于相邻边缘的任务。当i＝j时，f
i,j
代表单位时间边缘ei内在本节点上执行的到达任务中的任务量。当i≠j时，f
i,j
代表单位时间内边缘ei的到达任务中调度到相邻边缘ej上处理的任务量。此外，如果边缘ei和边缘ej不存在网络连接，则有f
i,j
＝0。
[0042]
此外，边缘的负载定义为集合w＝{w1,w2,
…
,wn}。wi》0代表边缘ei单位时间内执行的任务总量，包括边缘ei的到达任务中在自身上处理的任务量和来自于相邻边缘的任务量两部分。在初始状态，wi等于边缘ei的到达任务λi。然后，到达任务可以在本地或者调到相邻边缘上处理。因此，边缘ei上到达任务的平均响应时间应定义如下：
[0043][0044]
其中，t
i,j
代表单位时间内从边缘ei调度任务到边缘ej时的任务的平均响应时间，它包含了执行和传输时间。于是，t
i,j
定义如下：
[0045]
t
i,j
＝ta(lj)+d
i,j
[0046]
其中，ta(lj)代表在边缘ej负载率为时，其上的任务对应的平均执行时间。ta(lj)与具体的边缘节点配置相关。
[0047]
进一步，使用所有边缘上到达任务最大的平均响应时间作为评价指标，以更好地评估负载均衡效果，其定义如下：
[0048][0049]
最后，定义本方案的目标函数为：
[0050]
min(t
max
)
[0051]
当采用不同的全局负载均衡方案f
mat
时，最大平均响应时间t
max
可能改变。为了在wmans中实现更好的多边缘协同负载均衡效果，本实施例设计的目标是尽可能的降低最大平均响应时间t
max
。
[0052]
2、基于两阶段决策的多边缘协同负载均衡方法
[0053]
接下来，基于以上构造的模型和目标函数，介绍所提出的无线城域网中基于两阶段决策的多边缘协同负载均衡方法(tdb-ec)，其将集中决策和分散决策的方式相结合，如图2所示。
[0054]
首先，基于全局信息，使用基于dnn的负载均衡方案评估模型(p_predmodel)进行集中式决策，评估每对相邻边缘间的任务调度区间(详见2.1节)。算法1描述了全局集中决策的过程，具体步骤如下：首先，更新当前的全局信息，包括边缘集合的全局负载均衡方案f
cur
和各边缘任务响应时间tr(第5行)；其次，基于全局信息，使用基于dnn的负载均衡方案评估模型来计算当前系统状态下每对相邻边缘间的任务调度方案评估值集合f'(第6～7行)；然后，计算每对相邻边缘间的任务调度区间集合sr(第9行)；最后，循环执行上述过程，不断更新sr。
[0055][0056][0057]
接着，边缘节点基于自身的局部信息，使用基于dqn的负载均衡调整操作q值预测模型(q_predmodel)进行分散式决策，每个边缘在上述任务调度区间约束下独立执行本节点和相邻节点间的负载均衡任务调度(详见2.2节)。算法2描述了边缘ei分散决策的过程，具体步骤如下：首先，更新当前的局部信息，包括局部负载均衡方案自身和相邻边缘的负载率li和局部任务调度区间集合sri(第6行)，由于全局的决策和其他边缘的决策也在
同时进行，li和sri是不断变化的，因此，ei每次决策前要重新获取li和sri，其中，sri由全局集中决策的结果中获得；其次，将λi、li和sri作为输入，调用运行时决策算法(算法4)计算边缘ei的下一个负载均衡调整操作a(第7行)。如果算法4得到的a为空，说明边缘ei已经找到局部系统状态下的目标局部负载均衡方案(用表示)，此时不再进行调整(第8～9行)，否则执行算法4得到的调整操作a(第11行)；最后，循环执行上述过程以不断进行相邻节点间的负载均衡调度操作。
[0058][0059][0060]
在基于两阶段决策的多边缘协同负载均衡方法中，并行独立地进行全局的集中式决策和单节点的分散式决策，并使用反馈控制机制来逐步获取合适的全局负载均衡方案。
[0061]
2.1、基于dnn的全局负载均衡方案评估模型
[0062]
基于全局信息，本实施例使用基于dnn的负载均衡方案评估模型进行集中式决策，评估每对相邻边缘间的任务调度区间。其中，基于dnn的负载均衡方案评估模型输入为边缘集合的任务到达率λ、当前全局负载均衡方案f
cur
和当前任务响应时间tr，输出为每对相邻边缘的任务调度方案。
[0063]
本实施例使用无向拓扑图g＝(e,ψ)表示无线城域网中n个边缘的连接关系。其
中，边缘集合e＝{e1,e2,
…
,en}为拓扑图的顶点集，集合ψ＝{ψ1,ψ2,
…
ψm}表示拓扑图的边集(包含m条边)。拓扑图中的第k条边ψk表示边缘ei与边缘ej之间的网络连接。同时，规定在每对相邻边缘ei和ej(i《j)中，边缘ei的任务调度方向为正方向，即任务从边缘ei调度到边缘ej(i《j)的方向为正方向；反之，任务从边缘ej调度到边缘ei(i《j)的方向为负方向。于是，全局负载方案f
mat
可以转换为f＝{f1,f2,
…
,fm}，负载均衡方案全局评估模型如表2.1所示。
[0064]
表2.1负载均衡方案全局评估模型的输入和输出
[0065][0066]
基于历史运行数据，采用dnn训练全局负载均衡方案评估模型。由于各个边缘的服务速率vi不同，且有λi《vi和f
i,j
《min(vi,vj)。因此，不同边缘的到达任务量λ、任务调度量f差异较大。于是，对到达任务量λ、任务调度量f进行归一化，如下所示：
[0067]
λ
′i＝λi/vi[0068]f′k＝fk/min(vi,vj)
[0069]
其中，λ'i表示归一化后的边缘ei的到达任务。fk表示边缘ei和边缘ej之间的任务调度量，f'k表示归一化后的任务调度量。
[0070]
图3是一个包含5个边缘节点的拓扑图实例，在该场景下，边缘集合的任务到达率λ＝(6.8,14.5,4.6,13.2,9.1)，当前负载均衡方案f
cur
＝(1.62,0,1.12,-3.18,-2.7)，目标负载均衡方案f＝(0.81,1.62,0,-3.18,-3.3)。通过归一化公式，分别对实例中的λ和f进行归一化，得到的结果如表2.2所示，其中，λ'i的值在(0,1)区间内，f'k的值在(-1,1)区间内。
[0071]
表2.2用于说明归一化的简单例子
[0072][0073]
训练得到的负载均衡方案评估模型，能够基于边缘任务到达率λ'、当前负载均衡方案f'
cur
和当前任务响应时间tr，对目标负载均衡方案f'进行预测。但由于边缘负载情况复杂多变，负载均衡方案评估模型无法非常准确的预测每对边缘间的任务调度方案。于是，本实施例采用置信度模型，进一步对任务调度方案的取值区间进行描述，如下所示：
[0074][0075]
其中，c表示置信度，ε表示模型的误差，f'k表示任务调度方案预测值，表示任务调度方案实际值，于是有，有c％的概率落在区间[f'
k-ε,f'k+ε]内。
[0076]
基于上述置信度模型和归一化过程，每对相邻边缘间的任务调度的合理取值区间表示为集合sr＝{sr1,sr2,
…
,srm}，即算法1的输出。具体来说，边缘ei和边缘ej的任务调度区间计算如下所示：
[0077]
srk＝[(f
′
k-ε)
·
min(vi,vj),(f
′k+e)
·
min(vi,vj)]
[0078]
2.2基于dqn的负载均衡调整操作q值预测模型
[0087]
其中，γ是折扣系数，ω是dnn的权重，q(s,a；ω)是当前q值，maxq(s',a'；ω')则是在下一状态s'选择动作a'的最大q值。
[0088]
通常，drl问题可以被表述为马尔科夫决策过程(mdp)，其目的是使长期回报最大化。具体来说，mdp可以描述为四元组《s,a,p,r》，其中s，a，p和r分别代表状态空间、动作空间、状态转移函数和奖励函数。根据wman中的多边缘协同负载均衡的问题定义，将它们定义如下：
[0089]
状态空间：边缘ei的状态空间表示为si，其中代表一个潜在状态。具体来说，定义为一个三元组如果使用方案使得一个边缘的负载超过了它的可调整范围(即边缘的负载率小于0或大于1)，那么被视为无效状态。因此，为非法方案。
[0090]
动作空间：边缘ei的动作空间定义为。一个动作是增加或减少从边缘ei的到达任务中调度到相邻边缘的任务量的调整操作。其中，每次调度的任务量是一个固定值δ。例如，是增加边缘ei调度到边缘的任务量。
[0091]
状态转移函数:状态转移函数被定义为p(s,a)，其返回的是执行a后的下一个状态。例如，当在状态执行可以观察到下一个状态可以观察到下一个状态其中，边缘ei处的负载减少δ，边缘处的负载增加δ.
[0092]
奖励函数：为了引导dqn代理找到目标局部负载均衡方案奖励函数被定义为：
[0093][0094]
如果在状态处执行动作a找到dqn代理可以获得10的奖励。如果在状态处执行动作a得到一个非法方案，奖励将被设置为-1作为惩罚。至于其他情况，奖励仍为0。
[0095]
dqn根据dnn估计的q值和奖励的反向传播确定新的q值，并将q值带入损失函数以更新dnn的参数。然而，由于以下问题，通过上述过程直接训练一个负载均衡调整操作q值预测模型是很困难的。
[0096]
(1)当停留在目标状态时，所有负载均衡调整操作的理论q值为0。然而，当接近目标状态时，这些q值过高，无法实现负载均衡调整操作的准确q值预测。表2.4是一个用于解释说明上述问题的例子，边缘ei与边缘和边缘相连，状态s7为目标状态。在状态s7时，操作的q值预测值为2.9670(理论值应为0)，这会对运行时决策过程中停止条件的设定造成影响。如表2.4所示，当处于目标状态时，操作q值均小于3。因此，本实施例将停止条件设为当所有操作q值小于3时认为达到目标状态。但是，当在状态s2、s3和s4时，所有调整操作对应的q值同样小于3，此时，将无法到达目标状态。
[0097]
(2)当在执行某个调整操作后使得局部负载均衡方案成为一个非法方案时，对应的q值突变成负数(理论值应为-1)，这会影响同一相邻边缘相反操作的q值预测。例如，在状态s1时，由于执行操作将导致边缘的负载率超出可调度范围，此时的q值预测值为负数(理论值应为-1)，这同时影响了操作的q值预测值。相比状态s1和状态s2时操作q值预测值的差值，本实施例发现的差值更大些，说明操作的q值预测值在s1时被拉低了，这进一步影响了调整操作的运行时决策。如表2.4所示，在状态s1时，理论上选择的操作为但该状态下的q值预测值受的影响低于正常值(q值预测值为0.4162)，实际上却选择了(q值预测值为0.4675)，此时，将无法达到目标状态。
[0098]
表2.4未预处理的负载均衡调整操作q值表例子
[0099][0100][0101]
为了解决这些问题，在dqn训练期间，目标q值(用q_target表示)处理如下：
[0102][0103]
如果这个负载均衡调整操作将被视为非法操作，相应的q_target被置为i，并且不会被存储到dqn的经验池中。当时，被找到，q_target＝0。在其它情况下，因此，当接近时，q_target会逐渐减小，如下表所示。
[0104]
表2.5表2.4中的q值处理结果
[0105][0106][0107]
如上表所示，对dqn算法训练过程中q值计算进行处理后，运行时决策能够到达目标状态。一方面，处于目标状态时的调整操作q值与其他状态有着较大差距，此时，停止条件设为q值小于0.15，当在状态s1时，通过运行时决策能够逐步到达目标状态s7。另一方面，在状态s1时操作的q值预测值不再受到操作的影响。特别的，在s1时，调整操作和
的q值预测值分别为0.7581和0.8012，能够选择正确调整操作
[0108]
算法3展示了基于dqn的负载均衡调整操作q值预测模型的训练算法。首先，随机初始化dqn的参数(第6～8行)，然后训练过程开始(第9行)。在每个回合中，根据数据集初始化当前状态s
cur
和目标状态s
obj
(第10～11行)。当s
cur
≠s
obj
(第12行)，以∈的概率随机选择一个动作a，否则以argminq(s,a)选择动作a(第13行)。然后，执行动作a后，根据奖励函数计算奖励r，并得到下一个状态s'(第14～16行)。如果在执行动作a后，则跳过这一回合的训练(第17～18行)。否则，(s,a,r,s')将被存储到经验池(第20行)。然后，以一个批次的方式从经验池中抽取m个样本并计算q_tar getj(第21行)。然后，通过损失函数更新网络权重ω(第22行)。在每k次迭代中，使用ω更新ω'(第23行)，之后，状态s
cur
和状态s'之间发生状态转换(第24行)。最终，该算法将不断训练，直到收敛。
[0109]
[0110]
[0111][0112]
2.3负载均衡调整操作的运行时决策
[0113]
在这个部分，本实施例提出一个新的运行时决策算法，用于获取每个边缘和其相邻边缘间的目标负载均衡方案。算法4展示了运行时决策的主要过程。首先，调用q_predmodel计算所有动作的q值(即负载均衡调整操作)并将它们存储到集合q_values(第9行)。如果选择动作后的局部负载均衡方案是非法的或者任务量不在任务调度区间内，那么该动作被视为非法动作，并且对应的q值被标记为i(第10～15行)。然后，使用一个预先定义的阈值t来判断是否找到目标负载均衡方案。这是因为在负载均衡调整操作q值预测中存在一定的误差。如果所有有效动作的q值均小于等于阈值t(用i标记的除外)，则认为到达了目标方案，因此不需要再进一步执行调整操作(第16～17行)，否则将选取具有最小q值的调整操作(第18～20行)。最后，返回得到的调整操作a(第22行)。
[0114]
[0115][0116]
值得注意的是，每个边缘独立地进行相邻边缘间的负载均衡任务调度，直至对应的决策算法终止。
[0117]
3实验仿真与结果
[0118]
在本节中，本实施例首先介绍实验设置。接下来，围绕以下研究问题(research question，rq)对提出的方法进行分析和评估：
[0119]
rq1：tdb-ec能否在不同环境中实现自适应负载均衡？
[0120]
rq2：p_predmodel和q_predmodel性能如何？
[0121]
rq3：与经典方法相比，tdb-ec的性能提高了多少？
[0122]
3.1实验设置
[0123]
首先，基于某地的基站分布数据集和经纬度信息设计了5个不同的场景以进行仿真实验，如图5所示。其中，每个边缘ei用一个二元组(λi,vi)表示。每个场景的边缘数量n被设定为15，与一个边缘相连的相邻边缘的数量满足0《c≤3。边缘ei的任务到达率λi以及服务速率vi分别服从正态分布n(10,4)和n(15,6)。根据基站之间的距离，单位任务传输延时d被映射到区间[0.1,0.2]内。在边缘ei处，调整操作增加或减少的固定任务量δi设置为3％
×
vi。
[0124]
此外，基于排队理论，本实施例模拟了不同边缘上的任务平均执行时间，其定义如下：
[0125][0126]
接着，通过模拟不同的场景，收集历史数据集。其中，对于全局负载均衡，数据集包含了λ、f
cur
、tr和f
obj
；对于局部负载均衡，数据集包含了λi、li、和上述数据集被随
机划分成为训练集(75％)和测试集(25％)。在p_predmodel中，采用四层全连接层。其中，隐藏层节点数的比例为128:64。对于q_predmodel，它的dnn结构与p_predmodel一样，隐藏层节点数的比例为512:256。dqn算法使用tensorflow 2.0.0框架实现。其中，学习率、折扣系数γ、探索概率∈、回合数和经验池的容量分别设置为0.001、0.8、0.1、500和2000。此外，运行时决策算法的阈值t设定为0.15。因此，一旦所有有效的负载均衡调整操作的q值都小于或等于阈值t，就不再进行任何操作。
[0127]
3.2 rq1：tdb-ec的有效性评估
[0128]
表3.1不同场景中用tdb-ec所得方案和理想方案进行负载均衡前后各边缘负载率的对比
[0129][0130][0131]
首先，本实施例评估tdb-ec在5种不同场景中的有效性。更具体地说，本实施例比较分别使用tdb-ec得到的方案和理想负载均衡方案进行负载均衡任务调度后的各边缘负载率。其中，本实施例通过边缘节点的仿真模型评估不同状态下边缘ei上的任务平均执行时间ta(li)，并基于启发式算法在解空间中搜索不同场景下的理想负载均衡方案。但由于它极大的复杂度，实际中难以找到理想方案。
[0132]
如表3.1所示，在不同场景中tdb-ec能获得与理想方案较为相似的负载均衡方案，其中不同边缘的负载率差距较小。以第一个场景为例，分别利用tdb-ec所得的方案和理想方案进行负载均衡后，边缘e6和边缘e
15
的负载率均相等。而其它边缘负载率，其差距也小于6％。如图6所示，本实施例从任务的最大平均响应时间的角度分析比较了两种方案的负载均衡效果，tdb-ec能够得到接近理想方案的性能，其差距在5％～6％左右。结果表明，所提
出的方法获得了接近最优的多边缘负载均衡性能(以t
max
为评价指标)，能够很好地满足不同网络拓扑配置、各种工作负载的wman中的多边缘负载均衡的要求。
[0133]
本实施例以场景一中的边缘e5(分别与边缘e4和边缘e6相连)为例，来说明tdb-ec的负载均衡任务调度过程。每个调整操作增加或减少的固定任务量δ5＝0.35(v5×
3％)。上界和上界分别表示边缘e5的到达任务中调度到相邻边缘e4和e6上处理的任务量的最大值。如表3.2所示，初始状态s1表示λ5均在边缘e5上处理，和分别为97％、69％和77％。此时，根据任务调度区间计算公式可以计算得到和的取值范围分别为[0,1.16]和[0,1.79]。由于在初始状态s1执行和操作会使得相邻边缘的负载率超出可调度范围，所以调整操作和均为非法操作i。于是，在状态s1执行操作(具有最小预测q值且不为i的调整操作)并获取每个边缘的新负载率，从而进入下一状态s2。对于每一步操作，均采取合法的且具有最小的预测q值的负载均衡调整操作。另外，在状态s9，通过计算得到的取值范围为[0,2.14]。这时如果在状态s9继续执行调整操作则任务量变为2.45，将超出对应的取值范围的上界，所以调整操作被标记为i。因此，在状态s9选择采取调整操作在状态s
12
时，所有合法的负载均衡调整操作的预测q值都小于设定的阈值0.15，则表明已经到达目标状态，并且不需要继续采取调整操作。值得一提的是，边缘e4和边缘e6也在独立地做出决策，这影响了边缘e5的负载均衡任务调度过程。例如，在状态s1时，边缘e5选择执行操作(即任务量从边缘e5调度到边缘e4)，而在下一个状态s2中，边缘e6的负载率同时也发生了改变。
[0134]
表3.2本实施例方案的负载均衡过程(场景一的边缘e5，)
[0135][0136][0137]
3.3 rq2：p_predmodel和q_predmodel的性能
[0138]
3.3.1基于dnn的负载均衡方案评估模型
[0139]
首先，本实施例根据模型的容许误差ε和置信度c评估基于dnn的负载均衡方案评估模型的准确率，误差ε表示任务调度方案预测值f'k和任务调度方案实际值之差的绝对值，置信度c表示误差在ε范围内的预测值f'k数量的比例。
[0140]
如图7所示，当负载均衡方案评估模型的容许误差设置为0.15时，模型的置信度均可以达到95％以上。具体来说，负载均衡方案评估模型在5种不同的边缘场景中的置信度分别为96.6％、96.2％、96％、95.3％和95.7％。因此，集中决策得到的任务调度区间srk＝
[(f'
k-0.15)
·
min(vi,vj),(f'k+0.15)
·
min(vi,vj)]，能够有效指导各个边缘节点进行分散决策。
[0141]
3.3.2基于dqn的负载均衡调整操作q值预测模型
[0142]
动作准确率(aar)被定义为衡量决策过程中管理操作的正确性，如下所示
[0143][0144]
其中，表示采取的总调整操作数，代表采取的正确调整操作数。如果采取调整操作可以使当前负载均衡方案接近目标负载均衡方案，则它们被视为正确的调整操作。
[0145]
接着，根据距离理想负载均衡方案不同步数来研究tdb-ec在决策过程中的动作准确率。如图8所示，随着当前负载均衡方案接近理想方案，aar不断降低。例如，当当前负载均衡方案与理想方案差距超过10步时，aar超过95％。当当前负载均衡方案与理想方案相距较近(即5步)时，aar仍然保持在90％左右。平均来说，tdb-ec选择调整操作的准确性为92.5％。因此，tdb-ec总能在q_predmodel的支持下，以很高的正确率做出调整操作的决策。只有当前负载均衡方案与理想方案相距小于5步时，aar下降明显，但它仍然超过85％，此时当前负载均衡方案已经较为接近理想方案。因此，tdb-ec通常获得的负载均衡方案可以满足系统的正确性需求。
[0146]
3.4 rq3：tdb-ec相对于经典方法的性能改进
[0147]
在本节中，本实施例将tdb-ec与rf-clb、ml-based和rule-based三种基线方法进行对比分析。对于rf-clb方法，它采用分散决策的模式，并结合了强化学习(q-learning)和机器学习以进行相邻节点间的负载均衡任务调度。该方法的状态空间、动作空间和奖励函数的设置与tdb-ec一致。与rf-clb相比，tdb-ec是集中决策和分散决策相结合，集中决策的结果为边缘的独立调度决策提供指导；ml-based方法基于对边缘处于不同负载率下的任务平均执行时间的预测，利用粒子群优化和遗传算法(pso-ga)来搜索全局负载均衡方案；对于rule-based方法，其同样采用分散决策的模式。该方法根据每个边缘ei当前的负载率li选取相应的负载均衡调整操作，从而执行相邻节点间的负载均衡任务调度。对于边缘ei，其调度操作选取规则如下所示：
[0148]
如果li≥70％，增加从边缘ei调度到具有最低负载率的相邻边缘的任务量；
[0149]
如果30％≤li《70％，不采取任何调整操作；
[0150]
如果li《30％，减少从边缘ei调度到具有最高负载率的相邻边缘的任务量。
[0151]
首先，本实施例分别使用tdb-ec、rf-clb、ml-based和rule-based四种方法在所设置的5种不同的边缘场景中获取负载均衡方案。实验结果如图9所示，tdb-ec在5种场景中均取得了最好的效果。具体来说，tdb-ec得到的负载均衡方案的最大平均响应时间比rf-clb方法的降低了3.69％～4.61％。这是因为集中决策的方式考虑了全局的信息，从全局的角度评估每对相邻边缘间的任务调度区间，用于指导边缘的独立调度决策。相比单纯的分散决策方式，所以在一定程度上提升了负载均衡的效果。tdb-ec得到的负载均衡方案的最大平均响应时间比ml-based方法的降低了4.01％～6.34％。其中，本实施例在允许误差为15％的前提下，对ml-based方法使用的任务平均执行时间预测模型的准确率进行评估，得到模型的准确率只有88.2％。这是由于预测模型的训练需要大量的数据，来预测边缘在不同负载率下的任务平均执行时间。但是，如果没有足够的训练数据支持，可能会因为模型预
测不准确而导致负载均衡效率低下。tdb-ec得到的负载均衡方案的最大平均响应时间比rule-based方法的降低了14.46％～16.72％。这是由于rule-based方法包含了由专家定制的边缘负载调整规则。而在不同的负载均衡场景下，不能都使用同一调整规则。
[0152]
接着，本实施例根据负载均衡前后得到的各边缘上所有到达任务的平均响应时间，对使用的不同方法进行比较分析，其计算方式如下所示：
[0153][0154]
实验结果如图10所示，与负载均衡前的各边缘上所有到达任务的平均响应时间相比，使用tdb-ec方法进行负载均衡后，各边缘上所有到达任务的平均响应时间平均降低43.0％，实现了最显著的效果。具体地说，tdb-ec在五种不同的场景中进行负载均衡任务调度后的得到t
ave
，分别比rf-clb、ml-based和rule-based方法进行负载均衡任务调度后得到的t
ave
平均降低了2.2％、4.8％和12.9％。
[0155]
综上，tdb-ec方法在高效地实现多边缘协同负载均衡(以t
max
作为评价指标)的同时，也能够很好地减少所有到达任务的平均响应时间t
ave
。
[0156]
最后，本实施例分别对tdb-ec、rf-clb、ml-based和rule-based四种方法寻找负载均衡方案的平均时间开销进行分析评估。表3.3显示了这四种方法在五种不同场景中寻找目标负载均衡方案的时间成本。结果表明，rule-based、rf-clb，tdb-ec方法分别为0.104秒、1.42秒和3.71秒。因此，从系统管理的角度来看，这三种方法都能很好地满足要求。相比之下，ml-based方法的平均时间成本为239s，因此很难适应随着动态负载变化的多边缘无线城域网环境。
[0157]
表3.3不同方法找到负载均衡方案的平均时间(s)
[0158] tdb-ecrf-clbml-basedrule-based场景一3.881.572380.103场景二3.731.422410.107场景三3.811.262420.102场景四3.531.462400.106场景五3.611.382330.101
[0159]
以上所述，仅是本发明的较佳实施例而已，并非是对本发明作其它形式的限制，任何熟悉本专业的技术人员可能利用上述揭示的技术内容加以变更或改型为等同变化的等效实施例。但是凡是未脱离本发明技术方案内容，依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化与改型，仍属于本发明技术方案的保护范围。
[0160]
本专利不局限于上述最佳实施方式，任何人在本专利的启示下都可以得出其它各种形式的无线城域网中基于两阶段决策的多边缘协同负载均衡方法，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本专利的涵盖范围。

技术特征：
1.一种无线城域网中基于两阶段决策的多边缘协同负载均衡方法，其特征在于：基于全局信息执行负载均衡的集中决策，通过基于深度神经网络的预测模型评估相邻边缘之间的任务调度范围；并基于局部信息执行负载均衡的分散决策，通过一个基于深度q网络的调整操作q值预测模型评估边缘之间的负载均衡方案；最后，通过反馈控制获得目标负载均衡方案。2.根据权利要求1所述的无线城域网中基于两阶段决策的多边缘协同负载均衡方法，其特征在于：使用所有边缘上到达任务最大的平均响应时间作为评价指标，目标是尽可能的降低最大平均响应时间t
max
。3.根据权利要求1所述的无线城域网中基于两阶段决策的多边缘协同负载均衡方法，其特征在于：基于全局信息，使用基于dnn的负载均衡方案评估模型进行集中式决策，以评估每对相邻边缘间的任务调度区间，具体步骤如下：首先，更新当前的全局信息，包括边缘集合的全局负载均衡方案f
cur
和各边缘任务响应时间；其次，基于全局信息，使用基于dnn的负载均衡方案评估模型计算当前系统状态下每对相邻边缘间的任务调度方案评估值集合f
′
；然后，计算每对相邻边缘间的任务调度区间集合sr；循环执行上述过程，以不断更新sr；边缘节点基于自身的局部信息，使用基于dqn的负载均衡调整操作q值预测模型进行分散式决策，每个边缘在任务调度区间约束下独立执行本节点和相邻节点间的负载均衡任务调度，具体步骤如下：首先，更新当前的局部信息，包括局部负载均衡方案自身和相邻边缘的负载率l
i
和局部任务调度区间集合sr
i
，由于全局的决策和其他边缘的决策也在同时进行，l
i
和sr
i
是不断变化的，因此，e
i
每次决策前要重新获取l
i
和sr
i
，其中，sr
i
由全局集中决策的结果中获得；其次，将λ
i
、l
i
和sr
i
作为输入，调用运行时决策算法计算边缘e
i
的下一个负载均衡调整操作a，如果决策算法得到的a为空，说明边缘e
i
已经找到局部系统状态下的目标局部负载均衡方案，用表示，此时不再进行调整，否则执行决策算法得到的调整操作a，循环执行上述过程以不断进行相邻节点间的负载均衡调度操作；在基于两阶段决策的多边缘协同负载均衡方法中，并行独立地进行全局的集中式决策和单节点的分散式决策，使用反馈控制机制以逐步获取合适的全局负载均衡方案。4.根据权利要求3所述的无线城域网中基于两阶段决策的多边缘协同负载均衡方法，其特征在于：所述决策算法的具体执行步骤包括：调用q_predmodel计算所有动作的q值并将它们存储到集合q_values，如果选择动作后的局部负载均衡方案是非法的或者任务量不在任务调度区间内，那么该动作被视为非法动作，并且对应的q值被标记为i，然后，使用一个预先定义的阈值t来判断是否找到目标负载均衡方案；如果除用i标记的外，所有有效动作的q值均小于等于阈值t，则认为到达了目标方案，因此不需要再进一步执行调整操作，否则将选取具有最小q值的调整操作；最后，返回得到的调整操作a。5.根据权利要求3所述的无线城域网中基于两阶段决策的多边缘协同负载均衡方法，其特征在于：所述基于dnn的全局负载均衡方案评估模型的输入为边缘集合的任务到达率λ、当前全局负载均衡方案f
cur
和当前任务响应时间t
r
，输出为每对相邻边缘的任务调度方案；使用无向拓扑图g＝(e，ψ)表示无线城域网中n个边缘的连接关系；其中，边缘集合e＝
{e1，e2，...，e
n
}为拓扑图的顶点集，集合ψ＝{ψ1，ψ2，...ψ
m
}表示拓扑图的边集，包含m条边；拓扑图中的第k条边ψ
k
表示边缘e
i
与边缘e
j
之间的网络连接，规定在每对相邻边缘e
i
和e
j
，i＜j中，边缘e
i
的任务调度方向为正方向，即任务从边缘e
i
调度到边缘e
j
，i＜j的方向为正方向；反之，任务从边缘e
j
调度到边缘e
i
，i＜j的方向为负方向，由此将全局负载方案f
mat
转换为f＝{f1，f2，...，f
m
}；基于历史运行数据，采用dnn训练全局负载均衡方案评估模型：首先，对到达任务量λ、任务调度量f进行归一化，如下所示：其中，λ
′
i
表示归一化后的边缘e
i
的到达任务；f
k
表示边缘e
i
和边缘e
j
之间的任务调度量，f
′
k
表示归一化后的任务调度量；训练得到的负载均衡方案评估模型，基于边缘任务到达率λ
′
、当前负载均衡方案f
′
cur
和当前任务响应时间t
r
，对目标负载均衡方案f
′
进行预测，并采用置信度模型，进一步对任务调度方案的取值区间进行描述，如下所示：其中，c表示置信度，ε表示模型的误差，f
′
k
表示任务调度方案预测值，表示任务调度方案实际值，有c％的概率落在区间[f
′
k-ε，f
′
k
+ε]内；基于上述置信度模型和归一化过程，每对相邻边缘间的任务调度的合理取值区间表示为集合sr＝{sr1，sr2，...，sr
m
}，边缘e
i
和边缘e
j
的任务调度区间计算如下所示：sr
k
＝[(f
′
k-ε)
·
min(v
i
，v
j
)，(f
′
k
+ε)
·
min(v
i
，v
j
)]。6.根据权利要求3所述的无线城域网中基于两阶段决策的多边缘协同负载均衡方法，其特征在于：所述基于dqn的负载均衡调整操作q值预测模型中：一个边缘e
i
收集的局部信息包含边缘e
i
的任务到达率用λ
i
表示，边缘e
i
以及相邻边缘的任务负载率用l
i
表示，边缘e
i
的当前局部负载均衡方案用表示以及对应的到达任务的平均响应时间用表示和边缘e
i
的可选局部负载均衡方案用表示以及对应的到达任务的平均响应时间用表示，根据收集的局部信息，每个边缘独立地执行相邻边缘之间的负载均衡调度操作；边缘e
i
与c个相邻边缘连接，定义为集合其中，1≤j≤c表示与边缘e
i
相连接的第j个边缘，一个边缘的到达任务只能在本地或者调度到相邻边缘上进行处理；其中和1≤j≤c分别代表边缘e
i
和边缘的负载率；其中和1≤j≤c分别代表在边缘e
i
和边缘执行的到达任务中的任务量；在根据进行任务调度后，计算对应的在运行环境的所有可选方案中，边缘e
i
的目标局部负载均衡方案是具有最小的方案，用表示；此外，用集合表示；此外，用集合表示边缘e
i
和相邻边缘间的任务调度区间集合，其中1≤j≤c表示边缘
e
i
与相邻边缘的任务调度区间；边缘e
i
在不同系统状态下的运行数据构成了其历史数据集，其中包含λ
i
、l
i
和dqn算法根据边缘的历史数据集评估其在不同系统状态下所有调整操作的q值；具体来说，边缘的系统状态为调整操作为增加/减少从边缘e
i
的到达任务中调度到相邻边缘的任务量；当找到目标方案则生成对应的奖励；dqn代理首先收到运行时边缘环境的状态s，并通过贪婪策略选择动作a；接下来，dqn代理获得了相应的奖励r，并到达下一个状态s
′
；在每一步中，(s，a，r，s
′
)被存储在具有固定容量的经验池；如果达到阈值容量，dnn的参数ω将被更新，损失函数定义如下：loss＝(r+γmaxq(s
′
，a
′
；ω
′
)-q(s，a；ω))2其中，γ是折扣系数，ω是dnn的权重，q(s，a；ω)是当前q值，maxq(s
′
，a
′
；ω
′
)则是在下一状态s
′
选择动作a
′
的最大q值；根据wman中的多边缘协同负载均衡的问题定义，描述如下：状态空间：边缘e
i
的状态空间表示为s
i
，其中代表一个潜在状态；定义为一个三元组如果使用方案使得一个边缘的负载超过了它的可调整范围，那么被视为无效状态；因此，为非法方案；动作空间：边缘e
i
的动作空间定义为一个动作是增加或减少从边缘e
i
的到达任务中调度到相邻边缘的任务量的调整操作；其中，每次调度的任务量是一个固定值δ；是增加边缘e
i
调度到边缘的任务量；状态转移函数：状态转移函数被定义为p(s，a)，其返回的是执行a后的下一个状态；奖励函数：为了引导dqn代理找到目标局部负载均衡方案奖励函数被定义为：如果在状态处执行动作a找到dqn代理可以获得10的奖励；如果在状态处执行动作a得到一个非法方案，奖励将被设置为-1作为惩罚；至于其他情况，奖励仍为0；dqn根据dnn估计的q值和奖励的反向传播确定新的q值，并将q值带入损失函数以更新dnn的参数；在dqn训练期间，目标q值处理如下：如果这个负载均衡调整操作将被视为非法操作，相应的q_target被置为i，并且不会被存储到dqn的经验池中；当时，被找到，q-target＝0；在其它情况下，7.根据权利要求6所述的无线城域网中基于两阶段决策的多边缘协同负载均衡方法，其特征在于：基于dqn的负载均衡调整操作q值预测模型的训练过程具体为：首先，随机初始化dqn的参数，然后训练过程开始；在每个回合中，根据数据集初始化当前状态s
cur
和目标状态s
obj
；当s
cur
≠s
obj
，以∈的概率随机选择一个动作a，否则以argminq(s，a)选择动作a；然后，执行动作a后，根据奖励函数计算奖励r，并得到下一个状态s
′
；如果在执行动作a后，则跳过这一回合的训练；否则，(s，a，r，s
′
)将被存储到经验池；然后，以一个批次的方式从经
验池中抽取m个样本并计算q_target
j
；然后，通过损失函数更新网络权重ω；在每k次迭代中，使用ω更新ω
′
，之后，状态s
cur
和状态s
′
之间发生状态转换；经过不断训练，直至收敛。

技术总结
本发明的目的在于提供一种无线城域网中基于两阶段决策的多边缘协同负载均衡方法，首先，基于全局信息执行负载均衡的集中决策，其中设计了一个基于深度神经网络（DNN）的预测模型来评估相邻边缘之间的任务调度范围。接下来，基于局部信息执行负载均衡的分散决策，其中设计了一个基于深度Q网络（DQN）的调整操作Q值预测模型来评估边缘之间的负载均衡方案。最后，通过反馈控制获得目标负载均衡方案。通过仿真实验证明了TDB-EC能够很好地适应新环境，并在秒级实现多边缘负载均衡。此外，TDB-EC优于三种经典方法，并达到近似最优的性能。并达到近似最优的性能。并达到近似最优的性能。


技术研发人员：陈星 姚泽玮 胡晟熙 沈启航
受保护的技术使用者：福州大学
技术研发日：2023.04.03
技术公布日：2023/8/14