边缘计算中客户端竞争建模

t8u9v0

830人浏览 · 2025-10-13 15:26:46

t8u9v0 · 2025-10-13 15:26:46 发布

边缘计算环境中多个客户端行为分析

摘要

边缘计算是一种新兴的计算范式，在5G时代发挥着至关重要的作用。边缘计算中的一个基本应用场景是，终端用户能够选择边缘服务器节点，期望这些节点参与处理其分配的任务；同时，边缘服务器节点也可自由决定为哪些终端用户的服务任务提供服务。终端用户必须通过向边缘节点支付费用来相互竞争以获取边缘节点的服务。本文采用博弈论将终端用户与边缘服务器节点之间的交互建模为一种非合作博弈。其中，终端用户作为参与者竞争服务，而边缘服务器节点则提供服务。我们证明了该博弈中纳什均衡的存在性，表明在边缘计算环境中存在稳定的系统状态。此外，我们还展示了在最佳响应动态博弈过程中的纳什均衡稳定性，进一步说明在实际中，当终端用户在竞争由服务器节点提供的边缘计算资源过程中动态调整其策略时，系统能够达到这一稳定状态。

索引术语

边缘计算，博弈论，非合作博弈

一、引言

边缘计算（EC）[1][2]被提出用于将丰富而强大的计算资源放置在互联网边缘并靠近终端用户，以显著降低终端用户计算任务的延迟[3][4]，并提供更好的隐私保护（通过减少或完全消除通过互联网[5][6]的数据传输）。由于其在未来广泛应用场景中蕴含的巨大潜力，边缘计算吸引了越来越多的研究关注。例如，边缘计算可结合深度学习技术应用于交通控制场景，这可能为智慧城市的交通控制系统提供更优且更智能的解决方案。

在边缘计算环境中，资源分配是边缘计算中最基本的问题之一，已有大量相关研究。例如，一些研究人员[7][8]关注在人口密集区域的边缘云计算环境中，通过虚拟机迁移和传输功率控制来最小化服务延迟的问题。此外，一些研究人员[9][10][11]利用博弈论研究终端用户之间的竞争，以描述终端用户的行为，并假设任务可以通过边缘基站上传至云服务器，他们分析了如何确定应传输的本地任务的合适数量。

本文聚焦于边缘计算环境中包含多用户的场景[12][13]。一个关键问题是用户之间为吸引边缘节点参与其分布式任务而产生的竞争。鉴于大多数情况下边缘计算环境中存在多用户，一个关键挑战[16][17][18]是如何建模用户向边缘节点提供的价格之间的竞争过程。我们提出一种非合作博弈论模型，用于分析用户的行为动态，该模型使得边缘节点能够从终端用户处获得满意奖励，以激励其参与终端用户的任务。边缘节点可以切换所服务的用户以获取更优的奖励，这反过来将促使用户调整策略。

本文的主要贡献如下。

（1） 动态非合作博弈模型 ：我们关注边缘计算系统中多个客户端之间为吸引边缘节点参与而产生的价格竞争现象。具体而言，本文详细考虑由两个客户端和多个边缘节点组成的边缘计算场景，关于多于两个客户端的情况将在我们的未来工作中进行讨论。我们从客户端和边缘节点的行为两方面研究竞争的动态处理过程的发展。

（2） 纳什均衡 ：接着，我们研究双客户端竞争边缘计算环境中纳什均衡的存在性，并证明该博弈是一个具有势函数的合理模型。根据博弈的性质，我们证明双客户端竞争博弈始终存在纳什均衡。

（3） 纳什均衡的稳定性 ：接下来，我们关注上述系统的稳定性，以研究其是否为稳定状态。通过理论分析，我们发现即使某个客户端出于自私目的为了获取更高利润而改变其策略，系统仍会收敛至纳什均衡。

本文的其余部分组织如下。在第二节中，我们重点描述系统模型，以建立一个简要的概念。第三节详细介绍了边缘节点和客户端的问题建模。然后，在第四节中讨论了纳什均衡的稳定性。最后，我们进入结论部分并总结整篇文章。

II. 系统模型

A. 边缘计算客户端环境

我们讨论一种包含多个客户端和大量边缘节点的边缘计算场景。客户端集合可表示为 N，代表客户端的数量。
示意图0
图1展示了客户端之间竞争的情况。客户端必须调整策略，以吸引边缘节点为其任务提供服务。一旦客户端 i 宣布其价格为每单位时间 ri，边缘节点将评估客户端提供的奖励，并决定如何分配其计算资源来完成客户端提供的任务，即决定分配给客户端的时间单位数量 i。每个边缘节点做出时间分配决策的目的是最大化自身利润，即收到的总奖励。作为对边缘节点决策的响应，客户端可能会调整我们所提供的奖励，以提高各自的利润。

B. 游戏描述

博弈论提供了一种解决方案，通过一个标准框架来分析理性客户端的行为。它描述了多个客户端的行为模型。在本文中，我们使用标准的伯特兰德博弈将价格竞争建模为一种动态非合作博弈。该博弈的解是纳什均衡。

在客户端之间的竞争博弈中，players（来自经典博弈论）指的是客户端。利润函数 Pi 是提出用于表示客户端收益的 payoff，可表示为边缘任务收益减去向边缘节点分发任务所产生的成本。边缘节点将不会在客户端公布其安排之前决定它们将贡献多少单位时间（参数 bi）。每单位时间的价格 ri 是客户端的 strategy。

我们关注以下问题：客户端如何设置 ri 以最大化其利润？价格调整过程是否会达到稳定状态？为了回答第一个问题，客户端需要知道边缘节点提供单位时间服务的情况为其他客户端提供服务。第二个问题与纳什均衡的概念相关。纳什均衡是指一种策略组合，在该状态下，没有任何参与者能够通过改变自身策略而获益，因此每个参与者都不会改变其当前策略。最佳响应是另一个与纳什均衡相关的概念。在给定其他参与者策略的情况下，最佳响应是指能为某参与者带来最有利结果的策略。当每个参与者同时选择了针对其他参与者策略的最佳响应时，整个博弈就处于纳什均衡状态。

III. 问题表述

A. 边缘节点的响应

边缘节点的效用函数 U(b) 可以表示如下。通常，边缘节点的效用函数是每个客户端获得的总奖励减去所有客户端在分布式任务中消耗的总成本的结果。客户端 i 的奖励可定义为 biri。相比之下，客户端 i 参与分布式任务的成本为 biki。边缘计算环境的整体概念源于寡头垄断的线性模型[19][20][21]。

边缘节点的效用函数是：
$$
U(b) = \sum_{i=1}^{N} b_i r_i - \frac{1}{2} \left( \sum_{i=1}^{N} b_i^2 + s \sum_{i \neq j} b_i b_j \right) - \sum_{i=1}^{N} b_i k_i \quad (1)
$$
其中 $ b_i $ 是从代表性的边缘节点提供给客户端 i 的时间单位数量，$ b = {b_1, …, b_i, …, b_N} $ 是服务集合。在一个迭代中，一个边缘节点可以为多个客户端提供服务，但在每个单位时间内只能服务一个客户端。$ r_i $ 是客户端 i 每单位时间提供的价格。$ c_i $ 是边缘节点完成来自客户端 i 任务的成本。此外，边缘节点的切换意愿会影响边缘节点的利润函数。我们使用参数 $ s \in [0.0, 1.0] $ 来描述切换行为的可能性。如果 $ s = 0.0 $，表示边缘节点对其所服务的客户端极为忠诚；相反，如果 $ s = 1.0 $，则意味着边缘节点可能频繁更换其所服务的客户端。

$$
\frac{\partial U(b)}{\partial b_i} = r_i - b_i - \frac{s \sum_{i \neq j} b_j}{2} - k_i \quad (2)
$$
我们可以通过对 $ U(b) $ 关于 $ b_i $ 求导并令其等于0来计算任务计划。这就是在最大化 $ U(b) $ 的目标下确定 $ b_i $ 值的方法。

B. 客户端的利润函数

假设 $ r = {r_1, …, r_i, …, r_N} $ 表示所有参与者的策略集。令 $ r_{-i} $ 表示不包含 $ r_i $ 的策略集。我们使用 $ r = (r_i, r_{-i}) $ 进行简化。$ B_i(r_{-i}) $ 用于表示客户端 i 的最佳响应。则客户端 i 的利润函数为：
$$
P_i(r) = c b_i - r_i b_i \quad (3)
$$
其中 $ c > 1 $ 是系统参数，$ 0 < r_i < c $。$ c $ 是用于衡量客户端 i 参与边缘节点所获得收益的参数。

通过求解公式(2)，我们得到 $ b = {b_1, …, b_i, …, b_N} $ 作为关于所有边缘节点的任务计划的详细信息。之后，我们将 $ b_i $ 替换为 $ W_i(r) $。
$$
W_i(r) = \frac{(r_i - k_i)[1 + s(N - 2)] - \frac{s \sum_{i \neq j} (r_j - k_j)}{2}}{(1 - s)[1 + s(N - 1)]} \quad (4)
$$
公式(4) 可以写成另一种形式 $ W_i(r) = D_2 r_i - D_1(r_{-i}) $，其中 $ D_1(r_{-i}) $ 和 $ D_2 r_i $ 是如下所示的常数：
$$
D_2 = \frac{[1 + s(N - 2)]}{(1 - s)[1 + s(N - 1)]} \quad (5)
$$
$$
D_1(r_{-i}) = \frac{k_i[1 + s(N - 2)] + \frac{s \sum_{i \neq j} (r_j - k_j)}{2}}{(1 - s)[1 + s(N - 1)]} \quad (6)
$$
在完成公式(4)、公式(5)和公式(6)的准备工作后，我们可以将公式(3)重写如下：
$$
P_i(r) = (c - r_i) W_i(r) \quad (7)
$$
为了研究客户端 i 的最佳响应，我们计算 $ P_i $ 关于 $ r_i $ 的导数如下：
$$
\frac{\partial P_i(r)}{\partial r_i} = -2D_2 r_i + D_1(r_{-i}) + cD_2 \quad (8)
$$
$$
\frac{\partial^2 P_i(r)}{\partial r_i^2} = -2D_2 \quad (9)
$$
由于 $ P_i $ 的二阶导数始终为负，$ P_i $ 在 $ r_i $ 上是严格凹的，这意味着对于另一客户端的任意给定策略剖面 $ r_{-i} $，客户端 i 的最佳响应策略 $ B_i(r_{-i}) $ 是唯一的。

通过将公式(8) 设为 0，我们得到
$$
-2D_2 r_i + D_1(r_{-i}) + cD_2 = 0 \quad (10)
$$
$$
r_i = \frac{D_1(r_{-i}) + cD_2}{2D_2} \quad (11)
$$
结合公式(5)、公式(6)和公式(11)，我们得到
$$
r_i = \frac{1}{2} \left[ \frac{\sum_{i \neq j} (r_j - k_j)}{2[s(N - 2) + 1]} s + k_i + c \right] \quad (12)
$$
公式(12) 给出了纳什均衡下的价格分布。

C. 客户端的迭代行为

边缘计算环境中的竞争存在纳什均衡，这意味着单边行为无法增加客户端的利润。根据信息完整性，客户端逐步达到纳什均衡的算法分为两类。

首先，如果一个环境在完全信息下进行评估，则客户端可以获得其他客户端在上一次迭代中的策略信息。考虑到其他竞争者所采用的策略，客户端 i 在迭代 t+1 时会根据纳什均衡调整其策略。另一方面，如果客户端无法获取其他客户端的信息，则它们只能基于本地信息做出决策——它们分配的已完成任务的数量。在本文中，考虑到边缘计算的特点，我们关注不完全信息的情况。

$ r_i[t] $ 表示客户端 i 在迭代 t 时给出的价格。$ r_{-i}[t] $ 和 $ r[t] $ 可以类似地定义。然后，客户端 i 在时间 t+1 的价格为：
$$
r_i[t+1] = B_i(r_{-i}[t]), \forall i \quad (13)
$$
根据公式(13)，每个客户端将调整其价格策略。客户端只能基于本地信息和边缘节点的供应来调整策略。显然，一个客户端了解其历史服务供应情况。通过最大化其利润，该客户端将按如下方式调整其策略：
$$
r_i[t+1] = r_i[t] + \alpha_i \left( \frac{\partial P_i(r)}{\partial r_i} \right) \quad (14)
$$
其中 $ 0 < \alpha_i < 1 $ 是一个表示调整速度的参数。
$$
\frac{\partial P_i(r)}{\partial r_i} \approx \frac{P_i(r_{-i}[t] \cup {r_i[t]+\delta}) - P_i(r_{-i}[t] \cup {r_i[t]-\delta})}{2\delta} \quad (15)
$$
$$
P_i(r_{-i}[t] \cup {r_i[t] \pm \delta}) = c W_i(r_{-i}[t] \cup {r_i[t] \pm \delta}) - r_i W_i(r_{-i}[t] \cup {r_i[t] \pm \delta}) \quad (16)
$$
为了估算边际利润，一个客户端可以观察到小变化 $ \delta $ 下的边际服务供给。通过求解公式(14)、公式(15)和公式(16)，我们得到：
$$
r_i[t+1] = r_i[t] + \alpha_i (c - r_i[t]) D_2 = [1 - \alpha_i D_2] r_i[t] + \alpha_i D_2 c \quad (17)
$$
示意图1
图2描述了客户端A的利润随价格变化在不同条件下的趋势。显然，如果客户端A提供更高的价格，由于更多边缘节点的参与带来了更高的系统回报，其利润会上升。然而，在超过某个阈值后，由于支付给边缘节点的成本增加，利润从峰值开始下降。带来最高利润的价格即为最佳响应。当客户端B的价格为常数时，如图2所示，客户端A的利润先达到峰值，随后下降。X1、X2 和 X3 之间的关系为 X1 < X2 < X3。显然，如果客户端B提供了更高的价格，那么客户端A必须支付更多才能获得其最佳响应，且该最佳响应低于之前水平。这一现象可以解释为竞争变得更加激烈。因此，客户端A不得不提高其价格，以吸引边缘节点的参与。然后，图3
示意图2
展示了在不同参数s下，客户端A和客户端B如何达到纳什均衡，即图中不同参数s下的交点。X1与X2的关系为 X1 < X2。两个客户端可以自主选择其提供的价格。蓝线与绿线的交点表示在参数s = X1下，两个客户端同时达到了各自的最佳响应，此时即为纳什均衡状态。如果 X1 变得更高，例如 X2，意味着边缘节点更倾向于以更高的概率更换其所服务的客户端，从而导致两个客户端的最佳响应价格均上升。这可被视为客户端为了获得边缘节点的忠诚而不得不提供更高的价格。

IV. 纳什均衡的稳定性

我们关注价格调整过程是否会收敛到稳定价格配置。如我们所见，公式(13)和公式(14)均为自映射函数。根据定义，若由自映射函数定义的雅可比矩阵的所有特征值均位于复平面的单位圆内，则该自映射函数是稳定的 [22][23]。

在本文中，雅可比矩阵如下：
$$
J = \begin{pmatrix}
\frac{\partial r_1[t+1]}{\partial r_1[t]} & \frac{\partial r_1[t+1]}{\partial r_2[t]} & \cdots & \frac{\partial r_1[t+1]}{\partial r_N[t]} \
\frac{\partial r_2[t+1]}{\partial r_1[t]} & \frac{\partial r_2[t+1]}{\partial r_2[t]} & \cdots & \frac{\partial r_2[t+1]}{\partial r_N[t]} \
\vdots & \vdots & \ddots & \vdots \
\frac{\partial r_N[t+1]}{\partial r_1[t]} & \frac{\partial r_N[t+1]}{\partial r_2[t]} & \cdots & \frac{\partial r_N[t+1]}{\partial r_N[t]}
\end{pmatrix} \quad (18)
$$

对于公式(13)，雅可比矩阵为：
$$
J = \begin{pmatrix}
0 & \frac{s}{4[s(N-2)+1]} & \cdots & \frac{s}{4[s(N-2)+1]} \
\frac{s}{4[s(N-2)+1]} & 0 & \cdots & \frac{s}{4[s(N-2)+1]} \
\vdots & \vdots & \ddots & \vdots \
\frac{s}{4[s(N-2)+1]} & \frac{s}{4[s(N-2)+1]} & \cdots & 0
\end{pmatrix} \quad (19)
$$

通过求解公式(19)，我们得到
$$
\lambda_i = -\frac{s}{4[s(N-2)+1]}, \frac{s}{4[s(N-2)+1]}, \ldots, \frac{(N-1)s}{4[s(N-2)+1]} \quad (20)
$$

如果我们希望所有 $\lambda_i$ 都满足该条件，我们将看到：
$$
\frac{(N - 1)s}{4[s(N - 2)+ 1]} < 1 \Rightarrow (7 - 3N)s + 4 > 0 \quad (21)
$$

当 $N=2$ 时，我们有 $4 - s > 0$，由于参数 $s \in [0, 1]$，这始终成立。因此，我们得出结论 $|\lambda_i| < 1$，这意味着价格调整将处于稳态。

对于公式(14)，雅可比矩阵为：
$$
J = \begin{pmatrix}
1 - \alpha_1 D_2 & 0 & \cdots & 0 \
0 & 1 - \alpha_2 D_2 & \cdots & 0 \
\vdots & \vdots & \ddots & \vdots \
0 & 0 & \cdots & 1 - \alpha_N D_2
\end{pmatrix} \quad (22)
$$

方程(22)的特征值可以求解：
$$
\lambda_i = 1 - \alpha_i D_2 \quad (23)
$$

如果 $|\lambda_i| < 1$ 成立，则条件为 $0 < \alpha_i < 1, \frac{2}{D_2} \geq 1$ 或 $0 < \alpha_i < \frac{2}{D_2}, \frac{2}{D_2} < 1$。经过计算，$\frac{2}{D_2} \geq 1$ 并不总是成立。
示意图3