面向边缘计算中加权信息年龄最小化的防策略在线机制

摘要

实时信息处理对于众多领域中各类应用的成功至关重要。信息年龄（AoI）作为一种新指标，已受到广泛关注，用于评估实时信息处理系统的性能。近年来，边缘计算正成为降低AoI并提供实时服务的有效范式。考虑到边缘计算中高昂的部署成本及其带来的资源限制，设计合理的定价机制对于充分利用边缘资源、进而最小化整个系统的总体AoI显得尤为必要。然而，设计此类机制面临两个挑战：1）实时计算任务的优先级（或价值）通常是用户的私有信息，自私用户可能为了自身利益而篡改这些信息，而这些信息对高效资源分配至关重要；2）由于AoI具有时变特性，任务的价值随时间发生折扣，导致传统定价机制不可行。本文将经典迈尔森定理扩展至具有时间折扣任务价值的在线环境，并据此提出一种名为PreDisc的在线拍卖机制，该机制包含分配规则和支付规则。我们采用动态规划方法在每个时隙内贪心地分配资源，并对获胜用户收取一种新的临界价格，该价格扩展自经典的迈尔森支付规则。进一步引入抢占因子以在新到达的任务与正在进行的任务之间进行权衡。我们证明了PreDisc保证了防策略性属性，并实现了恒定竞争比。我们进行了大量仿真，结果表明，PreDisc在加权AoI和边缘服务提供商收入方面均优于传统机制。与离线VCG机制中的最优解相比，PreDisc具有低得多的计算复杂度，仅带来轻微的性能损失。

I. 引言

在近年来，实时信息处理在自动驾驶、[1],在线游戏 [2], 、虚拟现实（VR）[3]以及多机器人系统[4]等多个领域中日益普及。为了评估实时信息处理系统的性能，文献[5],提出了一种称为信息年龄（AoI）的新度量指标，并且该指标近期受到了广泛关注[6]–[10]。与延迟和吞吐量等传统性能指标不同，AoI指标考虑了决策信息的新鲜度。例如，如果用户以非常低的频率发送任务，系统在延迟方面表现良好，但在AoI方面表现较差，因为缺乏及时的决策更新会导致接收到的决策过时。因此，AoI被广泛采纳为实时计算应用中更为合理的性能指标。

传统的集中式云计算模式无法满足实时信息处理系统对信息年龄的严格要求，因为终端设备必须将数据发送到远程云端进行处理，导致较高的网络延迟。边缘计算 [11],作为一种新的计算范式，备受关注，可进一步降低实时应用中的信息年龄。在边缘计算中，边缘服务器（也称为云微粒）被部署在终端设备附近，这种物理上的邻近性可以显著减少传输延迟以及信息年龄。例如，在采用云计算模式的自动驾驶车辆系统中，车辆与远程云服务器之间的传输时间约为150毫秒，而借助边缘服务器，则可实现超低延迟（小于1毫秒）[12],[13]。许多实时应用，如在线游戏和虚拟现实，通过使用边缘计算模式也改善了信息年龄，从而提升了系统性能和用户体验[2]。

尽管边缘计算实现了显著的性能提升，但它也带来了分布式部署和维护的额外成本[11],[14]。由于这一成本限制，边缘服务器的计算资源通常有限，可能导致整体服务性能下降[15]。因此，一方面，考虑边云协同的范式是一种有前景的思路，结合边缘的低延迟和远程云端充足的资源[12],[16]；另一方面，需要合理的定价机制以充分利用有限的边缘资源，并补偿边缘服务提供商的成本[17]。

在实时信息处理系统中设计边缘服务的定价机制面临若干挑战。服务提供商希望通过为紧急任务分配较大的权重（或优先级），有效管理有限的边缘资源。我们使用任务价值这一指标来衡量任务紧急性（具体定义请参见第二节），该价值与用户的私有信息相关，例如自动驾驶系统中的行驶速度和周围环境。由于任务的价值对用户而言是私有信息，用户可能会操纵此类信息，以期提高其任务的优先级，从而导致市场混乱并降低资源利用率。因此，需要精心设计定价机制以抵御用户的策略行为。

除了保证策略证明性1的困难之外，任务的动态特性和时间折扣值也为高效定价机制的设计带来了障碍。一方面，由于任务以在线方式到达边缘，边缘服务器需要在不了解未来任务的情况下在线调度它们。经典维克里‐克拉克‐格罗夫斯（VCG）机制[18]–[20]无法直接应用于这种在线环境，因为它需要计算最优离线分配。另一方面，由于实时决策的信息年龄随时间增加，若任务执行被延迟，其价值将发生折减。这种随时间变化的值使用户有更大的空间进一步操纵机制，i.e.，用户可以通过虚报其价值在不同的时隙赢得资源。现有的在线机制[21],[22],对每个获胜任务收取预定义支付，而不考虑时间折现值，因此不再具有策略证明性，从而不适用于策略性环境下的信息年龄最小化。

为应对这些挑战，本文采用云‐边协同框架来优化实时决策任务的加权信息年龄。边缘服务器用于执行紧急任务，而远程云服务器则作为备用模式，在边缘服务不可用时为用户做出决策。我们进一步提出了一种用于加权信息年龄最小化的在线拍卖机制，其中用户动态到达拍卖过程，向边缘服务器提交任务及相应的任务价值，并在特定截止时间前等待及时的决策结果。基于报告的价值，边缘服务提供商计算每个时隙任务的加权信息年龄减少量，并调度任务执行，以最小化所有任务的总体加权信息年龄。边缘服务提供商还确定用户价格以保证防策略性属性，随后用户按所需价格支付边缘服务费用。

本文的主要贡献总结如下。
- 我们深入研究了边缘计算中信息年龄优化的两个关键方面：用户可能的策略性行为以及时变特性
在策略证明机制中，用户会如实披露其私有信息，i.e.，在我们的情境下即任务的价值。有关详细定义，请参见第二节。
信息年龄。基于这两个方面的适当模型，我们将加权信息年龄最小化问题建模为具有时间折扣值的在线机制设计问题。同时也充分讨论了由于时间折扣值这一新特性给在线机制设计带来的挑战。
- 我们将著名的迈尔森定理推广到具有时间折扣值的在线环境中。我们的算法结果与理论分析为在策略性环境中优化信息年龄提供了基础性工具。该结果在机制设计文献中也具有独立的研究价值，本文还讨论了该结果的潜在应用。
- 我们提出了一种基于抢占因子和时间折扣值的定价机制（PreDisc），用于在边缘服务器上分配计算资源。
PreDisc为正在进行的任务分配较高的虚拟价值，以避免对新到达的任务进行不必要的抢占，从而在抢占与非抢占之间实现理想的权衡。我们的理论分析表明，PreDisc同时保证了防策略性和恒定竞争比。
- 我们通过大量实验评估了所提出机制的性能。评估结果表明，PreDisc优于现有的先来先服务（FCFS）和后到先服务（LCFS）机制，并接近离线VCG机制的最优解。

本文的组织结构如下。第二节介绍了模型和基本背景知识。第三节描述了防策略性属性。第四节和第五节重点阐述PreDisc的详细设计。在第四节中，我们介绍了PreDisc中针对具有单位边缘执行时间任务的分配与支付规则，并分析了与离线最优解相比的竞争比上界。第五节将我们的机制扩展到一般情况。第六节给出了关于加权AoI和边缘服务提供商收入的仿真结果。第七节回顾了相关工作。最后，第八节对本文进行了总结。

II. 预备知识

在本节中，我们介绍了边缘计算背景下具有任务价值时间折扣的在线拍卖机制模型，并简要回顾了本文所使用的博弈论中的相关解决方案概念。

A. 系统模型

我们考虑一种包含两个组件的云‐边协同计算框架：一个云服务器和一个边缘服务器，以帮助用户进行实时决策。拥有充足计算资源的云服务器通常距离用户较远，因此仅依赖云服务器进行决策时无法保证响应时间。相比之下，附近的边缘服务器能够为用户提供及时响应，但由于有限的边缘资源，只能同时支持一定数量的任务。我们考虑必须在云端或边缘服务器上完成的任务，而不是

边缘设备的计算能力有限。某些任务可能超出本地边缘设备的计算能力限制（例如，基于CNN的图像识别任务 [24]），或在自动驾驶系统中需要来自其他车辆的信息（例如，联网车辆分析 [25]）。我们假设任务的生成遵循某种用户无法操控的模式。每个用户的目标是最小化其信息年龄（AoI），定义如下。

定义1（信息年龄） ：特定时刻用户的信息年龄是当前时隙与该用户最新接收到的决策结果生成时隙之差。

1) 用户-云通信

用户在正常模式下定期与云服务器进行通信。每个用户 j在每个时间间隔 Δt定期向云服务器发送一个任务 i（如实时诊断），并在经过一段处理时间T c i，j（包括传输延迟和执行时间）后接收决策反馈。由于云服务器配备了无处不在且强大的计算资源，我们假设任务无需等待即可执行。然而，由于用户与云端之间的传输距离较长，通信时间相当长，因此在没有边缘服务器参与的情况下，信息年龄波动处于相对较高的水平。

2) 用户-边缘通信

当用户遇到紧急任务（例如，对于自动驾驶系统，某些紧急情况需要及时决策）时，用户会将任务发送到云端和边缘服务器，并从边缘服务器接收快速反馈（同时也从云服务器获得备份）。我们假设边缘执行时间为 T e i,j，且该任务需要 mi,j单位的资源，而这些资源可能无法立即获得。由于边缘服务器具有超低通信延迟的特性，我们省略了通信时间以使表述更清晰，这一点将在后续章节中讨论。我们有T e i,j始终小于 T c i,j，这是由于云端距离较远 [24],[25],，因此借助边缘服务器可以减少信息年龄。此外，由于只有紧急任务被上传至边缘服务器，我们假设同一用户的紧急任务彼此之间不重叠。

我们在图1中通过一个示例说明系统模型。为了便于表述，本示例中假设所有任务的 T e和 T c为固定值。用户在每个时间间隔 Δt定期向云服务器发送任务，并在 T c个时隙后收到反馈。在时间 t3，可以计算出用户1的信息年龄为 T c，因为新接收到的决策生成于时隙t 1，比当前时隙早了 T c个时隙。在时隙t 3之后，信息年龄随时间增加，在时间 t 4达到最高AoI T c+ Δt，然后由于接收到下一个决策而下降至 T c。在时间 t 2，用户2向云端和边缘服务器同时发送任务，并在 T e个时隙后从边缘服务器收到响应。根据信息年龄的定义，我们可以将新的信息年龄曲线绘制成红色实线。因此可以看出，在边缘服务器的帮助下，信息年龄得以降低（从蓝色实线变为红色实线）。在时间 t 5 ，用户1向边缘服务器发送一个任务；不久之后，在时间 t 6 ，用户2也向同一边缘服务器发送一个任务。然而，该边缘服务器无法

没有足够的计算资源来满足两位用户的需求，因此用户2 的任务必须等到用户1的任务完成后才能进行。

由于决策的及时性对于实时信息处理应用的成功至关重要，例如，它可能影响自动驾驶汽车的安全性或交互式游戏中的用户体验，每个用户 j的目标是使加权平均 AoI最小化，记为 Aj。权重反映了使用边缘服务执行任务的紧急程度或价值，同时也表示用户愿意支付以换取单位信息年龄减少的最低支付金额。对于每个紧急任务i，其价值（即，权重）vi，j由用户 j报告，且可能依赖于多种因素。例如，在自动驾驶车辆系统中，任务的价值取决于行驶速度、车辆性能、周围环境、安全意识以及用户的其他偏好。由于这些因素大多是用户的私有信息，她可能会为了自身利益而虚报该价值vi，j，例如，声明一个较高的价值以提高其任务的优先级，从而降低加权AoI。这种自私行为会降低边缘服务的系统性能，因为更紧急的任务可能会被虚报为高价值的非紧急任务所抢占。鉴于此，我们采用拍卖机制来激励用户如实披露其私有信息，并高效分配有限的边缘资源，以优化所有用户的加权平均AoI。

B. 问题建模

我们考虑在有限时间范围内具有 W单位可重复使用的同质资源的边缘服务器，该时间范围可进一步划分为 T个等长的时隙： T={1, 2,···, T}。假设由用户 j产生的任务集合 2为U j ，任务 i ∈ U j 在时隙a i, j 到达，并且应在截止时间d i, j = a i, j + T c i , j 之前完成。这是因为边缘服务器做出的决策会失效

2由于我们关注边缘上的紧急任务，在后续章节中不再区分“任务”和“紧急 任务”。

当云服务器的决策在T ic,j个时隙后被接收时。我们将任务 i（用户 j）在[ai,j, di,j]期间的所有时隙记为Ti,j，并将其他时间˜的时隙集合t∈/ ∪i∈Uj Ti,j记为 Tj。为了计算用户 j的加权平均AoI Aj，我们记时刻 t的信息年龄为 Aj(t)，由云服务器生成的信息年龄（即图1中的蓝色实线）为 Cj(t)，由边缘服务器生成的信息年龄（即图1中的红色实线）为Ej(t)。如果在时隙t的信息年龄不是由边缘服务器产生的，则设 Ej(t)=+∞。基于这些定义，我们可以得到

$$
A_j(t)= \min{E_j(t), C_j(t)}.
$$

然后我们将时隙分为由云端产生信息年龄的时隙和由边缘产生信息年龄的时隙，并计算加权平均信息年龄，

$$
A_j= \frac{1}{T} \left(\sum_{t\in T_j} 1 \times A_j(t)+\sum_{i\in U_j} \sum_{t\in T_{i,j}} v_{i,j} \times A_j(t) \right)
= \frac{1}{T} \left(\sum_{t\in T_j} C_j(t)+\sum_{i\in U_j} \sum_{t\in T_{i,j}} v_{i,j} \times C_j(t)
-\sum_{i\in U_j} \sum_{E_j(t)<C_j(t)} v_{i,j} \times(C_j(t)− E_j(t)) \right).
$$

由于括号中的前两项为常数，且任务之间不重叠，因此我们只需独立地针对每个任务最大化第三项$\sum_{E_j(t)<C_j(t)} v_{i,j} \times(C_j(t)− E_j(t))$，该项表示当前时隙内加权AoI的减少量，即图1中各阴影区域。为了便于表述，我们将每个用户（也称为代理）为其每个任务复制一份，从而省略所有符号中的下标 j。（例如，我们直接使用 vi表示vi,j）。

假设边缘服务器在时间 ti开始执行任务 i，并在接下来的 T e i个时隙中无中断，则可得到如下加权AoI的减少量，

$$
\sum_{E_i(t) t_i +T_e^i}^{t’<a_i +T_c^i} (C_i(t’)− E_i(t’))
$$

这是一个关于起始时间t i的函数。因此，我们将任务价值定义为

$$
v_i(t)= v_i \times f_i(t)
= v_i \times \sum_{t’>t+T_e^i}^{t’<a_i +T_c^i} (C_i(t’)− E_i(t’)), \quad (1)
$$

如果任务在时隙 t开始执行，且满足$a_i \leq t \leq a_i + T_c^i - T_e^i$。需要注意的是，我们不对 $C_i(t’)$和 $E_i(t’)$的格式做任何限制。由于在所考虑的时间区间内有$E_i(t) < C_i(t)$，因此可以得出 $f_i(t)$是非负且非递增的，这意味着任务价值随时间推移而递减。一些可能的函数$f_i(t)$可以是 $f_i(t) = \eta(t - a_i)$或 $f_i(t) = 1 - \beta (t - a_i)$，其中参数可能因不同任务而异。不失一般性，我们对 $f_i(a_i) = 1$进行归一化处理。

利用任务价值这一指标，我们可以进一步将加权信息年龄最小化问题表述如下：有 N 个代理 N={1, 2,···, N}以随机顺序到达系统。每个代理 i ∈ N 在时间 ai到达，并要求在离开时间 di 之前获得 mi 单位的资源以执行其任务。为方便符号表示，我们还将$d’_i= a_i+ T_c^i - T_e^i$ 记作任务 i 能够及时完成的最晚开始时间。每个代理 i 具有一个内在的任务价值 vi ，以及在从时间 t 起被分配 mi 单位资源并持续 T e i 个时隙后的时间变化任务价值 vi(t)。我们将 vi= vi(ai)记作vi(ai)= vi × fi(ai)和 fi(ai)= 1。如上所述，代理 i 的时间变化价值函数可表示为

$$
v_i(t)=\begin{cases}v_i \times f_i(t), & t \in[a_i, d’_i], \ 0, & \text{otherwise}, \end{cases} \quad (2)
$$

其中 fi(t)是定义在(1)中的时间折扣价值函数。我们注意到，到达时间ai对于边缘做出正确决策至关重要。例如，如果一辆自动驾驶汽车上传任务时带有错误的时间戳，则可能接收到错误的驾驶指令，从而危及安全。因此，当一个代理 i ∈ N进入系统时，其到达时间ai和资源需求 mi将被如实披露。该代理向可信拍卖者（边缘服务器）提交一个声明的内在价值（出价）ˆvi，该值可能不等于其真实内在价值 vi。我们将代理 i的真实价值 vi称为其在机制设计中的类型，并使用向量ˆv=(ˆv1, ˆv2,···, ˆvN)表示所有代理的声明类型（即，出价组合）。

边缘资源分配的在线拍卖机制的过程描述如下。我们用 Na表示活跃代理集合，即如果从当前时隙 t开始执行任务，则能够完成其任务的代理，也就是说，当ai ≤ t ≤ d’_i成立时，我们有 i ∈ Na。在每个时隙 t ∈ T，拍卖者首先通过将每个活跃代理 i ∈ Na的声明类型ˆvi替换为（2）式中的真实内在价值vi，计算其出价ˆvi(t)。给定时间 t时活跃代理的出价向量 Na：ˆv(t)=(ˆv1(t), ˆv2(t) ···, ˆv|Na |(t))，拍卖者随后将总共 W单位的资源（包括空闲资源以及现有任务正在使用的资源）分配给活跃代理。需要注意的是，为了进一步提高资源利用率，新到达的高报价代理可以中断一些正在进行的低报价任务。若代理 i 被分配了 mi单位资源，并在截止时间di前连续执行T e i 个时隙而不被中断，则称其为获胜代理；否则称为失败代理。我们用 x i(ˆ v)= 1表示当声明类型向量为ˆv时，代理 i是获胜者；否则记为x i(ˆ v)= 0。对于获胜代理，t i(ˆ v)表示当声明类型向量为ˆv时，获胜者 i ∈ W开始执行其任务的起始时间。最后，根据代理的声明价值向量ˆv，拍卖者在每个代理 i的离开时间d i 确定其支付金额 pi( ˆv)。失败代理的支付设为零。我们使用向量 x(ˆv)=(x1( ˆv) x 2( ˆv) ···, x N(ˆv))和 p(ˆv)=(p1( ˆv) p2( ˆv) ···,pN(ˆv))分别表示在线拍卖中的分配规则和支付规则。

每个代理效用 ui i ∈ N被定义为她对所分配资源的价值 与支付之间的差额：

$$
u_i(\hat{v})=\begin{cases}v_i \times f_i(t_i(\hat{v}))−p_i(\hat{v}), & i \in W, \ 0, & \text{otherwise}, \end{cases} \quad (3)
$$

其中 W是获胜代理集合W。

正如我们在本节开头所示，最小化加权平均AoI等价于最大化时变任务价值的总和，这在拍卖机制背景下被定义为社会福利，如下所示。

定义2（社会福利） ：在具有时间折扣值的在线拍卖机制中，社会福利是获胜者在其对应的获胜时间槽中的价值之和，i.e.,

$$
SW=\sum_{i\in W} v_i \times f_i(t_i(\hat{v})). \quad (4)
$$

除了社会福利外，revenue（定义为从代理收集的总支付）也是机制设计中广泛使用的目标。由于收益仅反映边缘服务提供商的利益而非整个系统的利益，因此在本研究中我们采用社会福利作为优化目标，这有利于实时边缘服务系统的长期发展。我们还在评估结果中对所提机制的收益进行了评估。

与边缘服务提供商的优化目标相反，代理是理性且自私的，有动机通过策略性地报告其私有内在价值来最大化自身效用。为了说明任务价值时间折扣场景下的这种策略性行为，我们提供一个简单示例：假设代理1携带 v1= 10 、代理2携带v2= 8在同一时刻向边缘服务器发送任务。边缘只能服务一个代理，且两个任务的执行时间均为 T e i= 1。我们采用简单的资源分配规则：优先处理更紧急的任务（即具有更高价值的任务），并采用支付规则：对获胜者收取统一价格1。根据这些规则，解决方案是在第一个时隙执行任务1，然后在后续时间槽执行任务2。如果任务价值不随时间折现，则代理2没有动机虚报其价值，因为支付与她的出价无关，且她的效用始终为 8 − 1= 7。然而，如果任务价值每轮减半，则可能发生策略性行为。假设代理2真实报告其价值，她的效用为 4 − 1= 3，社会福利为14；但如果代理2虚报价值11，她将在代理1之前获得服务，并获得更高的效用 8−1= 7，而社会福利下降至13。从该示例中我们还观察到，源自经典迈尔森定理 [23],i.e.的用于保证策略免疫性的传统支付规则，即支付与资源分配时间无关，在任务价值时间折扣的设定下不再成立。这是因为用户通过虚报其价值可以改变资源分配时间，从而在任务价值随时间变化的场景下获得不同的效用。因此，此场景下需要一种新的合适拍卖机制，以抵御此类策略性行为并仍能实现最优社会福利。

C. 解决方案概念

机制设计中的一个强解概念是主导策略，其中策略定义为用户报告的类型。

定义3（占优策略[26]） ：若对任意策略ˆvi和任意其他代理的策略组合ˆvi′ ≠ ˆvi以及任何其他代理的策略配置ˆv−i，代理 i的策略满足以下条件，则该策略为其占优策略

$$
u_i(\hat{v} i, \hat{v} {-i}) \geq u_i(\hat{v}’ i, \hat{v} {-i}).
$$

直观上，一个代理的主导策略是指无论其他代理选择何种策略组合，该策略都能使其效用最大化。

占优策略的概念是incentive-compatible机制的基础，其中如实披露私有信息对每个代理而言都是一种占优策略。一个相关联的概念是individual-rationality，这意味着参与拍卖的每个代理所期望获得的效用不少于不参与时的效用。

现在我们可以引入strategy-proof mechanism的定义。

定义4（防策略性[27]） ：当一个机制满足激励相容性和个体理性时，该机制是策略证明的。

本工作的目标是设计一种在任务价值时间折扣背景下具有策略证明性的在线拍卖机制。

III. 防策略性的特征描述

在本节中，我们提出了针对具有时间折扣值的策略证明在线拍卖机制的特征定理。这可以视为著名迈尔森定理[23]的推广。具体而言，我们指出，在时间折扣值设定下，支付规则真实实施分配规则的必要且充分条件是函数 $F(\hat{v}) = f(t(\hat{v})) \times x(\hat{v})$ 必须满足单调性准则。我们首先给出该单调性准则的定义。

定义5（单调性） ：函数$F_i(\hat{v})=f_i(t_i(\hat{v}))\times x_i(\hat{v})$是单调的，如果对于任意两个类型ˆvi和ˆv′ i，满足 ˆvi> ˆv′ i，以及其余代理的报告类型ˆv−i，均有 $F_i(\hat{v} i,\hat{v} {-i}) \geq F_i(\hat{v}’ i,\hat{v} {-i})$。

我们进一步分析这一单调条件$F_i(\hat{v} i,\hat{v} {-i}) \geq F_i(\hat{v}’ i,\hat{v} {-i})$，该条件可分为两种具体情况。一种情况是分配结果 xi(·) 从 xi(ˆv′i ,ˆv−i)= 0变为 xi(ˆvi,ˆv−i)= 1。另一种情况是分配结果 xi(·) 保持不变，即 xi(ˆvi,ˆv−i)=xi(ˆv′i ,ˆv−i)= 13且 fi(ti(ˆvi,ˆv−i)) ≥ fi(ti(ˆv′i ,ˆv−i))，在函数 fi(t) 为非增函数的假设下，这进一步意味着 ti(ˆvi,ˆv−i) ≤ ti(ˆv′i ,ˆv−i)。第一种情况与经典Myerson定理中分配规则的单调性一致，意味着出价更高的竞标者更有可能赢得拍卖。第二种情况源于在线机制的新特性，它进一步要求具有更高价值的代理被分配到更早的时隙。在在线环境下，这一单调条件背后的直观含义是：若获胜用户提高其声明类型，则她可能被分配到更早的时隙。

3另一种情况 x i (vˆi ,vˆ − i )= x i (vˆ′i,vˆ − i )= 0的分析是平凡的，此处省略。

我们现在提出主要结果：具有时间折扣值的策略证明在线拍卖机制存在的必要且充分条件。

定理1 ：存在一个支付规则 p(ˆv) 使得在时间折扣值设定下的在线拍卖机制 (x(ˆv) p(ˆv)) 是策略证明的，当且仅当对于每个代理 i ∈ N，函数$F_i(\hat{v})= f_i(t_i(\hat{v})) \times x_i(\hat{v})$是单调的。该定理表明，在为时间折扣值场景设计新机制时，我们可以将满足防策略性的条件转化为对函数 Fi(ˆv)单调性的证明。我们将该定理分为“如果”和“仅当” 两部分，并通过分析以下两个引理来完成证明。

引理1 ：如果对于每个代理，函数 Fi(ˆv)= fi(ti(ˆv)) × xi(ˆv)是单调的，则与精心设计的支付规则 p(v)相关联的在线拍卖机制是策略证明的。

证明 ：我们将支付规则设置为

$$
p_i(\hat{v})= \sum_{k=1}^{K} v_i^k \times \Delta F_i(v_i^k), \quad (5)
$$

其中序列vi1, vi2,···, viK是一组 K值，这些值是函数 Fi(ˆv)在值从0增加到真实值vi时的断点。通常，我们假设vk1 i ≤ vk2 i对 k1 ≤ k2、 vi0= 0和 viK ≤ vi成立。函数 ΔFi(vik)表示 Fi(ˆv)在断点(vik,ˆv−i)处的跳跃， 4即

$$
\Delta F_i(v_i^k)= F_i(v_i^k, \hat{v} {-i})− F_i(v_i^{k−1}, \hat{v} {-i}).
$$

支付规则(5)背后的直觉是，随着 vi的增加，代理被分配到一个“更优”（即更早）的时隙，因此拍卖者将对代理收取这一增量部分的费用。式(5)中的断点值vik表示被分配到更优时隙的临界价格，而ΔFi(vik)衡量了“新时隙有多优”，即代理 i在两次分配之间的（归一化）价值差异。

根据(5)中的支付规则，我们可以表示代理 i ∈ N的效用ui(ˆv)为：

$$
u_i(\hat{v})= v_i \times f_i(t_i(\hat{v}))\times x(\hat{v})− \sum_{k=1}^{K} v_i^k \times\Delta F_i(v_i^k)
= v_i \times F_i(\hat{v})− \sum_{k=1}^{K} v_i^k \times \Delta F_i(v_i^k)
=(v_i^K + v_i − v_i^K) F_i(v_i^K , \hat{v} {-i})
− \sum {k=1}^{K} v_i^k \times(F_i(v_i^k , \hat{v} {-i}) − F_i( v_i^{k−1} , \hat{v} {-i}))
=(v_i − v_i^K) F_i( v_i^K , \hat{v} {-i}) + \sum {k=1}^{K} (v_i^k − v_i^{k−1}) F_i( v_i^{k−1} , \hat{v}_{-i}) , \quad (6)
$$

其中第三个等式成立是因为Fi(vi, ˆv−i) = Fi(viK, ˆv−i) ，因为vKi 是资源分配的最高断点

4为简化符号表示，我们省略了存在并列情况的情形，即，我们考虑Fi(vki, vˆ − i )= Fi(vki + ε,vˆ − i )，其中 ε是一个小的正常数。

代理 i。根据值序列的定义，我们有viK ≤ vi和vk−1 i ≤ vik ，对于所有 1 ≤ k ≤ K成立。因此，代理 i的效用 ui(ˆv)不可能为负，满足个人理性的性质。

我们现在证明，单调函数Fi(ˆv) 结合 (5) 中的支付规则 pi(ˆv) 能够保证激励相容的性质。我们采用反证法进行证明。如果该拍卖机制不是激励相容的，则存在一个代理 i、其真实类型 vi 以及一个不诚实的申报类型 ˆvi，且满足 ˆvi ≠ vi，使得 ˆui(ˆvi, ˆv−i) > ui(vi,ˆv−i)。也就是说，代理 i 申报 ˆ{v10}所获得的效用严格大于她如实申报时所能获得的效用 ui(vi,ˆv−i)。由 (6) 可得

$$
(v_i − v_i^{K’}) F_i(v_i^{K’}, \hat{v} {-i})+ \sum {k=1}^{K’} (v_i^k −v_i^{k−1}) F_i(v_i^{k−1}, \hat{v} {-i}) >(v_i−v_i^K) F_i(v_i^K, \hat{v} {-i})+ \sum_{k=1}^{K} (v_i^k −v_i^{k−1}) F_i(v_i^{k−1}, \hat{v}_{-i}), \quad (7)
$$

̂，其中 K是虚报类型ˆvi对应的断点的最大索引。值得注意的是，与真实类型 vi相比，虚报类型ˆvi仅影响断点的数量，而不影响断点的值，因为断点的值独立于代理 i的声明类型。

由于以下情况 ̂ K= K对于证明是平凡的，我们可以通过区分以下两种情况来完成分析：

如果 ˆvi< vi，则我们有 K̂< K，因此 vK′i ≤ viK。由于函数 Fi(ˆv) 是单调的，我们可以得到

$$
\text{RHS of}(7) \geq(v_i − v_i^K) F_i(v_i^{K’}, \hat{v} {-i}) + \sum {k=K’+1}^{K} (v_i^k − v_i^{k−1}) F_i(v_i^{k−1}, \hat{v} {-i}) + \sum {k=1}^{K’} (v_i^k − v_i^{k−1}) F_i(v_i^{k−1}, \hat{v} {-i}) \geq(v_i − v_i^{K’}) F_i(v_i^{K’}, \hat{v} {-i}) + \sum_{k=1}^{K’} (v_i^k − v_i^{k−1}) F_i(v_i^{k−1}, \hat{v}_{-i}) = \text{LHS of}(7),
$$

其中，在第二项中，我们将 Fi(vik−1,ˆv−i) 对 K̂+ 2 ≤ k ≤ K 简化为 Fi(vK′i , ˆv−i) 。因此，我们在这种情况下得到了矛盾。

如果ˆvi > vi ，那么我们有 K̂> K，因此 vK′i ≥ vKi 。然后我们可以将(7)式的左边第二项中的求和展开为 k= 1到 K， k= K+ 1，以及 ̂ k= K+ 2到 K。于是我们得到

$$
\text{LHS of}(7) = \left(v_i − v_i^{K+1} + \sum_{k=K+2}^{K’} (v_i^{k−1} − v_i^k) \right) F_i( v_i^{K’}, \hat{v} {-i}) + \sum {k=1}^{K} (v_i^k − v_i^{k−1}) F_i(v_i^{k−1}, \hat{v} {-i}) +(v_i − v_i^K+ v_i^{K+1} − v_i) F_i(v_i^K, \hat{v} {-i}) + \sum_{k=K+2}^{K’} (v_i^k − v_i^{k−1}) F_i(v_i^{k−1}, \hat{v}_{-i}). \quad (8)
$$

此外，由于我们有 vi ≤ vK+1 i vik ≥ vk−1 i vK′i ≥ viK Fi(vK′i, v−i) ≥ Fi(viK v−i) ，且 ，因此可以得到 ˆ,ˆ，从而可以在方程中消除某些项并得到

$$
(8) \leq(v_i − v_i^K) F_i(v_i^K, \hat{v} {-i}) + \sum {k=1}^{K} (v_i^k − v_i^{k−1}) F_i(v_i^{k−1}, \hat{v}_{-i}) = \text{RHS of}(7). \quad (9)
$$

因此，我们在这种情况下也得到了矛盾，“如果”部分的证明到此完成。 反之，我们考虑“仅当”部分。

引理2 ：如果在线

IV. 边缘执行时间为单位时间情况下的PreDisc

我们现在提出所提议机制PreDisc的详细设计，并分析其经济属性和竞争比。我们首先介绍单位边缘执行时间的情况，即所有任务的 $T_e^i= 1$（因此我们省略下标 i），在这种情况下，在线环境中抢占问题不存在。在此情形下，任务的云处理时间 $T_c^i$和资源需求 $m_i$可能不同。我们注意到，该问题的“在线”特性仍然是一个挑战，即我们必须在任务持续时间内决定何时执行任务以优化总体AoI。当前任务分配的时隙可能会阻碍未来任务的执行。我们将在下一节中将该机制扩展到边缘不同执行时隙的一般情况。

A. 分配规则

我们在算法1中给出了PreDisc的资源分配规则的过程。在每个时隙，将活跃任务收集到集合 $N_a$中，并将其当前值和资源需求收集到集合 $\Gamma$中（第3‐7行）。每个时隙的分配问题可以表述为一个0‐1背包问题，其中背包的容量是资源容量 $W$，每个物品的收益和权重分别对应任务的当前值和资源需求。我们每个时隙的目标是在资源容量约束下选择最具成本效益的活跃任务。因此，我们采用动态规划技术来求解每个时隙 $t$的资源分配问题，以获得获胜者集合 $W_t$，并更新最终获胜者集合 $W$（第8‐10行）。

接下来我们证明，这种在不了解未来任务的情况下、仅基于每个时隙的简单分配规则，可以获得恒定竞争比2。该结果意味着PreDisc至少能达到离线最优社会福利的一半。

定理2 ：在具有单位边缘执行时间的情况下，PreDisc中资源分配规则的竞争比为2。

证明 ：设离线最优解（OPT）中的获胜者集合为 OPT，在时隙t内OPT中的获胜代理为 OPTt。类似地，我们将PreDisc得到的相应获胜代理集合分别记为 $W$和$W_t$。对于一个获胜代理 $i$，我们用$t_i^*$表示其在OPT中被选中的时间，用 $t_i$表示其在PreDisc中被选中的时间。我们区分以下两种情况。

对于代理$i \in \text{OPT}_t$，如果代理 $i \in W_t’$满足 $t’ \leq t$，即，代理 $i$也在时隙 $t$或之前被PreDisc选为获胜者，我们将这些代理记为集合$W$。由于任务的价值是非递增的，我们可以很容易地得到

$$
\sum_t \sum_{i\in\text{OPT} {1t}} v_i(t^*_i) \leq\sum {i\in W} v_i(t_i).
$$

对于 $\text{OPT} t$ 中的其他代理，我们知道这些代理在任何 $t’ \leq t$ 下都不在 $W {t’}$ 中，并将它们记为 $\text{OPT}_{2t}$。在 PreDisc 中，这些代理可能落选或之后被选为获胜者。我们可知，这些代理在时隙 $t$ 的总价值应小于PreDisc所选代理的总价值；否则，动态规划算法会将其输出为结果。因此，我们可以得到

$$
\sum_{i\in\text{OPT} {2t}} v_i(t^*_i) \leq\sum {i\in W_t} v_i(t_i).
$$

总体而言，我们有

$$
\sum_{i\in\text{OPT}} v_i(t^ i)=\sum_t \left( \sum {i\in\text{OPT}_{1t}} v_i(t^ i)+ \sum {i\in\text{OPT} {2t}} v_i(t^*_i) \right) \leq\sum {i\in W} v_i(t_i)+\sum_t \sum_{i\in W_t} v_i(t_i) = 2\sum_{i\in W} v_i(t_i), \quad (12)
$$

这完成了我们的证明。

B. 支付规则

在经典在线拍卖机制 [21],[22], 中，为了保证防策略性，支付规则是为每个时隙设置一个预定义价格。然而，我们在上一节中构建了一个简单示例，以证明当价值随时间折损时，采用此类支付规则将不再满足防策略性属性。为克服这一障碍，我们计算每个单一时隙的临界价格，并基于第三节中的扩展的迈尔森定理推导出我们的支付规则。

我们通过以下步骤计算分配规则中每个获胜者 $i$的支付。首先，我们再次运行资源分配算法（i.e.，算法1），以计算一个不包含代理 $i$的新解。在此新的分配过程中，在每个时隙，我们可以利用动态规划的最优子结构性质，并获得最小出价$\hat{v}^{\min}_i (t)$，其为总资源量分别为 $W$单位和$W - m_i$ 单位时的解之间的差值。该值$\hat{v}^{\min}_i (t)$表示代理 $i$在时隙 $t$能够赢得该时隙资源所需的最低出价。然后，

根据时变价值函数(2)的定义，我们可以得到相应的关键内在价值

$$
v^{\min}_i,t= \frac{\hat{v}^{\min}_i (t)}{f_i(t)},
$$

代理 $i$ 为了在时隙 $t$获胜需要声明的关键值。根据每个时隙中代理 $i$ 的该临界值，我们可以贪婪地选择一个随时间变化的非递增临界值子序列，即定理1中所述的断点值。直观上，假设一个断点为 $v^{\min} {i,t}$，这意味着当代理 $i$ 在到达时间 $a_i$ 报告的内在价值不低于 $v^{\min} {i,t}$ 时，她将在不晚于时隙 $t$ 被选为获胜者。我们在算法2中给出了一个过程，用于从临界内在价值确定断点以及获胜代理 $i$ 的相应支付。

从到达时间 $a_i$ 到最晚开始时间 $d’_i$ 遍历各个时隙，我们将第一个小于代理出价的临界内在价格设为第一个断点。之后，仅当某个临界内在价格小于之前选定的断点时才将其选为新的断点（第2‐3行）。例如，假设声明类型为5，临界内在价格序列为 {6, 4, 2, 3}，我们选择4，然后选择 2作为断点。可以验证，这样选出的一组内在价值满足断点的定义。然后，我们将选出的断点按非递减顺序排序，并使用定理1中的(5)式计算支付（第8‐11行）。

考虑图2中的一个简单示例，其中资源总量 $W$为5，所有任务的云处理时间 $T_c^i = 3$ ，以及每个用户的价值 $i \in N$通过一个时间折扣函数 $f_i(t)= 1 - \frac{1}{3}(t - a_i)$随时间线性减少。在图2中，我们使用实线表示每个代理的当前时间区间。每个代理的资源需求和价值也显示在其旁边。在分配确定阶段，第一个时隙选择代理A和C作为获胜者，因为它们的总价值9大于B的总价值。在第二个时隙，B的价值变为 $\frac{10}{3}$ ，并且由于更高的值6而选择了D。在第三个时隙，具有更新后值$\frac{5}{3}$的代理B和具有更新后的值2的代理E处于活跃状态，并且选择了E作为获胜者。我们在图2中用红色表示每个时隙的获胜者。在支付计算阶段，对于代理A，我们将其移除并重新运行资源分配过程，得到每个时隙的关键内在价值$v^{\min} {A,1}= 4,v^{\min} {A,2}= 8,v^{\min} {A,3}= 5$。我们可以贪婪地获得仅有一个断点 $v^1_A= 4$的递减子序列。利用(5)，可以计算出代理A的支付为$p_A= 4$。类似地，代理C的断点序列为$v^1_C= 0$，代理D的断点序列为$v^{\min} {D,2}= \frac{10}{3}, v^{\min} {D,3}= 3, v^{\min} {D,4}= 0$，代理E的断点序列为 $v^3_E= \frac{5}{2}, v^4_E= 0$。最后，我们可以计算出各代理的支付：$p_C= 0,p_D= \frac{19}{9}, p_E= \frac{5}{6}$。我们现在基于定理1证明PreDisc的防策略性。

定理3 ：对于具有单位边缘执行时间的情况，在上述分配与支付规则下的在线拍卖机制PreDisc是策略证明的。

证明 ：根据定理1，我们只需证明资源分配规则的单调性，即当获胜代理提高其出价时，该代理将在更早或相同的时隙被执行。由于动态规划算法在每个时隙输出最优解，若一个获胜代理报告更高的价值，则她要么在当前时隙被选中，要么在更早的时隙被选中。因此，定义5中定义的分配规则的单调性得以满足，证毕。

五、一般情况下的PreDisc

在本节中，我们首先将PreDisc扩展到 $T_e^i$ 可以大于1但对所有任务仍然相同的情况（因此我们可互换使用 $T_e$ 和 $T_e^i$）。在这种情况下，任务在执行过程中可能被其他任务抢占，因此在这些在线设置中任务之间的交互变得更加复杂。在第V‐D节中，我们将PreDisc进一步扩展到最一般情况，其中任务在边缘的执行时间 $T_e^i$ 可以不同，并且还考虑了到边缘的通信时间。

A. 虚拟出价生成

当新到达的代理的任务价值高于某些正在进行的代理时，拍卖者可以选择抢占正在进行的任务以弥补任务价值差异，或拒绝新代理以保证边缘的连续性服务。一旦任务被抢占，它将一直等待直到下次被选中，然后从头开始执行任务，因此如果新到达的代理没有提供显著更高的出价，抢占可能会降低资源利用率。考虑到这一点，拍卖者会提高正在进行的代理的出价，记为 $N_o$，以赋予它们更高的优先级，从而持续获得资源分配。在时隙 $t$，每个正在进行的代理$i \in N_o$自时隙 $t_i(\hat{v})$以来已连续分配到 $m_i$单位资源。我们将代理 $i$在时隙 $t$的虚拟出价记为$b_i(t)$，其可按如下方式计算

$$
b_i(t)= \hat{v}_i(t_i(\hat{v}))\times \alpha^{\phi_i}, \quad \text{where } \phi_i=(t - t_i(\hat{v}))/T_e
$$

表示任务 $i$在时间$t$的完成度百分比， $\alpha \geq 1$是拍卖者可调节以控制抢占频率的参数： $\alpha= 1$的设置代表抢占模型，即一旦有出价更高的新任务到达，就会中断正在进行的任务。通过增加 $\alpha$，拍卖者可以为正在进行的任务提供更多保护。当 $\alpha \to \infty$时，拍卖者不允许抢占，任务一旦分配到资源便可连续执行$T_e^i$个时隙。对于尚未分配到资源的活跃代理，i.e.，集合$N_a\backslash N_o$中的代理，拍卖者会更新它们的出价，i.e.， $b_i(t)= \hat{v}_i(t)$。拍卖者可通过区分以下两种情况，在时隙 $t \in T$生成代理$i \in N$的虚拟出价 $b_i(t)$：

$$
b_i(t)=\begin{cases}\hat{v}_i(t_i(\hat{v}))\times \alpha^{\phi_i}, & i \in N_o, \ \hat{v}_i(t), & i \in N_a\backslash N_o. \end{cases} \quad (13)
$$

B. 分配规则

一般情况下的资源分配算法如算法3所示。为简便起见，我们仅展示一个时隙的算法。与简单情况下的分配规则类似，其核心思想是在每个时隙使用代理的虚拟出价，并采用动态规划技术。我们首先将任务的当前值更新为虚拟出价，以赋予正在进行的任务更高的分配优先级（第1‐7行）。之后，我们将资源分配问题视为背包问题，并采用动态规划技术求解（第8‐9行）。我们更新两类代理的分配状态：对于新获胜的代理，将其获胜时间 $t_i(\hat{v})$更新为$t$（第 10‐11行）；对于被抢占的代理，将其获胜时间重置为 Null back（第12‐13行），以便其等待下一次分配过程。我们将那些在截止时间前已连续执行 $T_e^i$ 个时隙的代理加入最终获胜者集合（第15‐16行）。我们剔除那些任务无法在剩余时间内完成的代理（第17‐18行）。

定理4 ：在具有相同边缘计算时隙的一般情况下，我们的资源分配规则在PreDisc中的竞争比为 $1+ \frac{\alpha}{1 - \alpha^{-1/T_e}}$，相较于离线最优解。

证明 ：证明过程与定理2类似，我们重用定理2中的符号。我们注意到在具有相同 $T_e$的一般情况下，一个代理将在 $T_e$个连续时隙中成为获胜者。因此，我们用 $i \in \text{OPT}_t$表示任务 $i$从时隙 $t$开始连续执行 $T_e$个时隙（i.e.， $t_i^*= t$）；对于PreDisc中的 $i \in W$，任务 $i$从时隙$t_i$开始连续执行 $T_e$个时隙。但对于临时获胜代理集合 $i \in W_t$中的任务 $i$，它仅表示任务 $i$在时隙 $t$被选中，之后可能会被抢占。我们区分以下两种情况。

对于代理 $i \in \text{OPT} t$，如果 $i \in W$且 $t_i \leq t$，i.e.，该代理$i$在起始时间或早于时隙 $t$的PreDisc中也被选为获胜者，我们将它们记为集合 $\text{OPT} {1t}$ ，并将所有时隙中这些集合的全体记为$\text{OPT} 1= \cup {t \in T} \text{OPT}_{1t}$。由于任务的价值是非递增的，我们可以很容易得到

$$
\sum_{i \in\text{OPT} 1} v_i(t^*_i) \leq\sum {i \in W} v_i(t_i) .
$$

对于 $\text{OPT} t$ 中的其他代理，即满足 $t_i > t$的 $i\notin W$ 或 $i \in W$，我们将它们在所有时隙的集合记为$\text{OPT} {2t}$。这些代理可能在PreDisc中失败，或之后被选为获胜者。类似地，我们将它们全部记为 $\text{OPT} 2= \cup {t \in T} \text{OPT} {2t}$。我们有，在时隙$t$，$\text{OPT} {2t}$ 中代理的总价值不应超过PreDisc在同一时隙选择的代理的虚拟出价总和；否则，动态规划算法会将它们作为输出结果。因此，我们可以得到

$$
\sum_{i\in\text{OPT} {2t}} v_i(t^*_i)= \sum {i\in\text{OPT} {2t}} v_i(t) \leq\sum {i\in W_t} b_i(t),
$$

其中左边的等式是因为如上所述的$t_i^*= t$。

接下来，在时隙 $t$，我们将未完成的正在进行的代理的虚拟出价之和记为 $S_{un}(t)$。可以观察到，在时隙 $t+1$ 的虚拟出价之和至少为 $S_{un}(t)\times\alpha^{1/T_e}$，这是根据虚拟出价规则得出的。这意味着，PreDisc 中每个被选中的代理 $i$要么最终会被完成，要么会被其总价值大于被抢占代理的虚拟出价之和的新代理所抢占。我们注意到，即使抢占以链式发生，该观察结果仍然成立。因此，设在我们的算法中于时隙 $t’$完成的代理集合为 $N_{c,t’}$，并回顾 $T$中的最后一个时隙是 $T$，则我们可以得到

$$
\sum_{i\in W_t} b_i(t) \leq \sum_{t’=t}^{T} \sum_{i’\in N_{c,t’}} b_{i’}(t’)\times \alpha^{(t-t’)/T_e}.
$$

该方程的关键思想是，一旦在时隙 $t$选出了获胜者，它可能会被抢占，但最终该获胜者或其（链式）抢占者将在后续的某个时隙完成。因此，我们将后续完成的任务映射到时隙 $t$，并对它们全部求和，作为左侧的一个上界。因此我们得到

$$
\sum_{i\in\text{OPT} 2} v_i(t^*_i)=\sum_t \sum {i\in\text{OPT} {2t}} v_i(t) \leq\sum_t \sum {i\in W_t} b_i(t) \leq\sum_t \sum_{t’=t}^{T} \sum_{i’\in N_{c,t’}} b_{i’}(t’)\times \alpha^{(t-t’)/T_e} \leq\sum_{i\in W}(v_i(t_i) \sum_{\Delta=-\infty}^{0} \alpha^{\Delta/T_e}) =\sum_{i\in W} v_i(t_i)\times \frac{\alpha}{1 - \alpha^{-1/T_e}}.
$$

总体而言，我们得到

$$
\sum_{i\in\text{OPT}} v_i(t^ i)= \sum {i\in\text{OPT}_1} v_i(t^ i)+ \sum {i\in\text{OPT} 2} v_i(t^*_i) \leq\sum {i\in W} v_i(t_i)+\sum_{i\in W} v_i(t_i)\times \frac{\alpha}{1 - \alpha^{-1/T_e}} =\sum_{i \in W} v_i(t_i)\times\left(1+ \frac{\alpha}{1 - \alpha^{-1/T_e}}\right), \quad (14)
$$

这完成了我们的证明。

根据该定理，我们可以通过简单的数学计算得到最优抢占因子 $\alpha=(1+ \frac{1}{T_e})^{T_e}$，其对应的竞争比为$(T_e+ 1)(1+ \frac{1}{T_e})^{T_e}$，这是一个较小的常数。这一结果表明，最优抢占因子仅与边缘执行时间相关。直观上，在相同的 $\phi_i$下，较大的 $T_e$意味着正在进行的任务占用资源的时间更长，因此不抢占该任务更具成本效益，i.e.，应设置更大的抢占因子 $\alpha$。

C. 支付规则

与简单情况下的支付规则类似，需要计算 $i$的临界内在价格在不同时间时隙中的获胜者。但区别在于，在具有$T_e \geq 1$的一般情况中，临界内在价格应保证代理 $i$能够在连续的 $T_e$个时隙中获胜。按照第四节‐B中的步骤，我们可以得到代理 $i$在单一时隙$t$获胜所需的最小虚拟出价$b^{\min}_i(t)$。相应地，我们可以计算$\hat{v}^{\min}_i (t)$，即代理 $i$从时间 $t(t \in[a_i, d’_i])$开始连续赢得 $T_e$个时隙时，在时隙 $t$所需的最低出价。

$$
\hat{v}^{\min} i (t)= \max {t’\in[t,t+T_e-1]} \frac{b^{\min}_i (t’)}{\alpha^{(t’-t)/T_e}}, \quad (15)
$$

即当前区间内单一时隙的最小虚拟出价的最高最低出价。然后，我们得到代理 $i$在时间 $t$对应的关键内在价值：

$$
v^{\min}_{i,t}= \frac{\hat{v}^{\min}_i (t)}{f_i(t)}.
$$

接下来，我们可以调用算法2来计算每个获胜代理的支付。最后，我们可以得到关于防策略性的以下理论保证。由于该证明与定理3几乎相同，我们在此省略证明。

定理5 ：我们提出的机制PreDisc在具有相同边缘执行时间的一般情况下，采用上述分配与支付规则是策略证明的。

D. 扩展

接下来，我们将PreDisc扩展到最一般和最现实的情况，其中1）考虑了到边缘的通信时间，以及2）任务的边缘执行时间 $T_e^i$可能不同，因此关于抢占的决策变得更加复杂。

我们可以首先得出，具有不可忽略的到边缘通信时间的机制设计问题，在我们的简化模型中等价于任务在通信时间之后生成的问题。此外，由于任务的通信时间无法由用户操控，因此到边缘的通信时间不会影响理论分析，且在扩展了不可忽略的到边缘通信时间后，策略证明性和常数竞争比仍然成立。

接下来我们表明，在上述分配规则和支付规则下，相应的竞争比在扩展情况下与定理4类似，只要我们将 $T_e$替换为 $T_e^{\max}$ ，即所有任务中最高的边缘执行时间。由于证明也与定理4的证明类似，此处省略。

定理6 ：采用与上述相同的分配规则和支付规则，PreDisc 在一般情况下与离线最优解相比的竞争比为 $1+ \frac{\alpha}{1 - \alpha^{-1/T_e^{\max}}}$。

防策略的经济属性在扩展情况下也成立。该证明与定理3的证明几乎相同，由于篇幅限制此处省略。

定理7 ：采用与上述相同的分配规则和支付规则，我们提出的机制PreDisc在一般情况下是策略证明的。

我们将进一步解释一般情况如何在现实世界任务卸载场景中被理解。我们可以将边缘执行时间建模为

$$
T_e^{i,\text{exe}}= \frac{c_i}{m_i},
$$

以及到边缘的通信时间作为

$$
T_e^{i,\text{comm}}= \frac{l_i}{R_e^i},
$$

其中， $c_i$是任务所需的CPU周期数， $m_i$是分配给该任务的CPU计算能力， $l_i$是任务的输入数据大小， $R_e^i$是边缘与用户之间的平均数据传输速率。因此，我们得到边缘处理时间为

$$
T_e^i= T_e^{i,\text{comm}}+ T_e^{i,\text{exe}}= \frac{l_i}{R_e^i} + \frac{c_i}{m_i}.
$$

类似地，我们可以将云处理时间建模为

$$
T_c^i= T_c^{i,\text{comm}}+ T_c^{i,\text{exe}}= \frac{l_i}{R_c^i} + \frac{c_i}{m_i},
$$

其中$T_c^{i,\text{comm}}$是到云端的通信时间，$T_c^{i,\text{exe}}$是云端执行时间，$R_c^i$是云端与用户之间的平均数据传输速率。我们注意到$T_c^{i,\text{exe}}$与边缘执行时间$T_e^{i,\text{exe}}$相同，因为CPU周期数$c_i$及其分配的CPU计算能力$m_i$相同。这样，现实世界任务卸载场景可以通过用户具有不同 $T_e^i$和 $T_c^i$的一般情况来捕捉。

VI. 评估结果

A. 实验设置

我们用C++实现了所提出的机制，并与现有机制进行了比较。在实验中，有 $N= 100$个用户和 $T= 100$个时隙，每个时隙的长度设置为10毫秒。每个任务所需的CPU资源 $m_i$设为服从均匀分布的整数，范围为[1, 5],，每单位GPU资源设为1 GHz。除非另有说明，边缘端的总CPU容量为$W= 10$ GHz。特别地，我们将任务的内在价值设为服从[1, 10]上的均匀分布。时间折扣价值函数 $f_i(t)$被定义为线性函数 $f_i(t)= 1 -\frac{(t-a_i)}{T_c^i-T_e^i}$。如果某用户在某一时刻没有正在执行的任务，则她在该时隙以概率（到达率）$\gamma$生成一个任务。在实验中，我们将到达率 $\gamma$设为0.1。为了使表述更清晰，我们首先考虑一个简化模型，其中不考虑到边缘的通信时间，边缘执行时间固定为30毫秒（即3个时隙），云处理时间为100毫秒（即10个时隙）。然后，我们也考虑实际情况，包括不可忽略的到边缘的通信时间，以及任务之间不同的边缘执行时间和云处理时间。类似于[29]–[31],中的设置，除非另有说明，我们将所有任务的输入数据大小设为 $l= 50$ Kb，到边缘的数据传输速率为 $R_e= 5$ Mbits/s，到云端的数据传输速率为 $R_c= 0.5$ Mbits/s。

我们假设执行时间在[1, 5]个时隙（i.e.，10毫秒到50毫秒）内服从均匀分布。我们在不同机制下评估加权平均 AoI和收益随参数变化的情况。我们进行了500次实验以获得平均结果。

我们将我们的机制PreDisc与以下基准机制进行比较：
- 先到先服务（FCFS） ：在FCFS中，每个时隙内，活跃任务（包括正在进行的任务）按其到达时间升序排列。若到达时间相同，则优先选择价值更高的任务。值得注意的是，FCFS本质上是非抢占式的，因为到达时间较晚的任务总是会被延后执行。
- 抢占式后到先服务（LCFS‐p） ：在LCFS‐p中，每个时隙内，活跃任务（包括正在进行的任务）按其到达时间降序排列。类似地，如果它们的到达时间相同，则价值更高的任务优先服务。注意，LCFS‐p不对正在进行的任务提供抢占保护，因此这些任务很可能会被后续任务抢占。
- 非抢占式后到先服务（LCFS‐np） ：LCFS‐np 与 LCFS‐p 类似，区别在于正在进行的任务受到保护而不会被中断，即一旦某个任务被选中执行，将不会被抢占并完成该任务。
- 离线VCG（VCG‐off） ：VCG 是一种针对具有策略性输入问题的、具有最优社会福利的著名机制。我们将边缘资源分配问题转化为其离线版本，并将 VCG 机制视为理想的最优基线。需要指出的是，该机制无法在实际应用中部署，因为它需要离线的全局信息。

我们在PreDisc上进行了三种抢占因子的实验： $\alpha= 1$ （ PreDisc‐1）、 $\alpha= 100$ （PreDisc‐100）和最优 $\alpha \approx 2.4$（ PreDisc‐opt），其中PreDisc‐opt在某些图中也被称为PreDisc，作为默认设置。

为了计算FCFS、LCFS‐p和LCFS‐np的收益，我们采用了一种在实践中广泛使用的简单支付规则，即 $p_i= \rho \cdot v_i(t_i)$，其中 $0< \rho< 1$是一个常数。在我们的仿真中，我们设置 $\rho= 0.5$ ，意味着边缘服务提供商收取已完成任务价值的一半作为费用。需要指出的是，这种支付规则易于部署，但并不诚实，因为用户容易通过谎报其价值来减少支付。

B. 数值结果

不同参数下的加权平均信息年龄评估结果如图3所示。我们在图3(a)中首先比较了不同到达率 $\gamma$下各机制的表现。总体来看，我们的机制相比其他机制在加权信息年龄上实现了显著降低，其中PreDisc‐opt取得了最小的加权信息年龄。我们的机制具有优势的原因有两点：第一，由于采用了动态规划而非简单的贪心算法，我们的机制在每个时隙都能实现最优的资源分配；第二，PreDisc‐opt在抢占与非抢占之间实现了良好的权衡。此外，FCFS和 LCFS‐p表现最差，因为FCFS倾向于选择到达时间较早但已陈旧的任务，而LCFS‐p一旦有新到达的任务就会频繁地进行抢占。在LCFS‐np中，高价值的新鲜任务被选择并完成而不被抢占，因此实现了较低的信息年龄。当 $\gamma$从 0.05增加到0.3时，大量任务被上传至边缘，导致许多高价值任务未能完成，因此所有机制的加权信息年龄均随到达率的上升而增加。

在图3(b)中，我们将上述机制与离线VCG机制（即理想最优基准）进行比较。VCG的计算复杂度极高，因为它需要枚举所有可能的调度结果。因此，我们减小了问题规模，设置为 $N= 20, T= 10,l= 25$ Kb， $W= 5$ GHz，并对100次运行的评估结果取平均。从图3(b)可以看出，加权

我们的机制的信息年龄（AoI）与离线VCG机制非常接近，这表明了PreDisc的有效性。与图3(a)的一个微小不同之处在于，在图3(b)中，某些机制的信息年龄（AoI）随着到达率的增加而下降。这是因为在资源规模减小的设置下，资源相对充足，因此增量已完成任务的影响高于增量未完成任务的影响。我们进一步评估了FCFS、LCFS‐p、LCFS‐np、我们的机制以及VCG‐off的计算复杂度（即程序执行时间），并将结果展示在表I中。这些结果表明，我们提出的机制PreDisc能够在计算复杂度远低于最优解的情况下，实现近似最优加权平均AoI。

图3(c)展示了CPU计算能力$W$的影响。当CPU计算能力较大时，边缘服务器能够高效调度任务以减少加权 AoI，从而使得所有机制下的信息年龄均下降。当 $W \geq 60$ GHz时，几乎所有机制中的任务都能及时完成，因此达到了最低的信息年龄。当$W \leq 40$ GHz时，资源受限，PreDisc具有更高的资源利用率，因而相比其他机制获得了更低的加权AoI。

抢占因子 $\alpha$对加权AoI的影响如图3(d)所示。我们可以看到，当抢占因子接近最优值 $\alpha$（在我们的默认设置下约为2.4）时，加权AoI确实表现出更好的性能。该结果验证了我们在PreDisc理论分析中关于抢占参数选择的最优性。

我们在图3(e)中报告了云处理时间 $T_c$和边缘执行时间 $T_e$对评估结果的影响。以及图3(f)所示。我们注意到， $T_c$是最大AoI，因为每个任务在 $T_c$个时隙后都可以收到来自云端的响应。较大的 $T_c$能够为发送到边缘的紧急任务提供灵活调度，从而降低这些任务的加权AoI。然而，由于 $T_c$较大，导致发送到云端的任务（占所有任务的大多数）的加权平均AoI显著增加，因此总体AoI随着 $T_c$而上升。较大的 $T_e$意味着任务需要等待更长时间才能完成，因此随着 $T_e$的增加，加权 AoI也会更高。

我们在图4中进一步研究了不同机制下边缘的平均收益。

图4(a)展示了不同机制的收益表现。我们可以观察到，由于边缘资源的高利用率，我们的机制的收益优于其他所有机制。此外，PreDisc‐1在我们的机制中实现了最高的收益，这一点将在后面进行解释。随着到达率$\gamma$的增加，我们机制的收益也随之增加，因为更多的任务导致更激烈的竞争，从而提高了获胜者的关键价格。

在问题规模缩减的设置下，在图4(b)中展示了与离线VCG的平均收益对比结果。离线VCG实现了最高的收益，但我们的机制与离线VCG之间的差距较小。考虑到离线VCG机制极高的计算复杂度以及对全局信息的需求，PreDisc在部署中更具实用性，仅带来轻微的收益损失。当$\gamma= 0.1$或0.2时，LCFS‐np的收益略高于我们的机制，这是因为在问题规模缩减的设置下资源相对充足，因此我们机制中的临界价格在一定程度上较低。我们还注意到，由于LCFS‐np的支付规则不是策略证明的，其当前表现出的收益在实际应用中可能会下降。

图4(c)展示了CPU计算能力$W$对收益的影响。显然，FCFS、LCFS‐p和LCFS‐np的收益随着 $W$的增加而增加，因为这些机制的收益与完成任务的数量成正比，而完成任务的数量显然会随着CPU的提升而增加

计算能力。与这些机制相比，当资源供应更充足时，PreDisc的收益会随着 $W$的增大先增加后减少至0，因为完成的任务数量增加，但资源的临界价格下降。因此，我们指出，可以通过增加用户之间对边缘资源的竞争来提高 PreDisc的收益。

在图4(d)中，我们展示了抢占因子$\alpha$对PreDisc收益的影响。我们观察到，随着$\alpha$的增大，收益下降。这是因为较低的 $\alpha$会导致频繁的抢占，从而使得每个时隙的临界价格较高。因此，我们可以得出结论：当抢占因子 $\alpha$低于最优值时，加权AoI和收益均随抢占因子的增加而降低，这一结果也为实际应用中在此范围内选择 $\alpha$时权衡AoI与收益提供了方向。

然后，我们在图4(e)和图4(f)中分别展示了不同 $T_c$和 $T_e$值下各机制的收益。在图4(e)中，PreDisc的收益起初随 $T_c$增大而增加，但当 $T_c$超过某一阈值后开始下降。这是因为当 $T_c$较大时，PreDisc能够更灵活地调度任务，从而完成的任务数量增加，收益也随之上升。然而，如果 $T_c$继续增长，大量完成的任务意味着临界价格较低，因此 PreDisc的收益略有下降。LCFS的收益始终很小，因为频繁抢占正在进行的任务导致仅有少量任务得以完成。在 LCFS‐np中，仅选择新到达的任务，因此随着$T_c$增大，产生的任务更少，收益反而下降。在FCFS机制中，较大的 $T_c$意味着具有最高优先级的任务更加陈旧，因此收益随 $l$显著下降。图4(f)描绘了边缘执行时间 $T_e$的影响。当 $T_e$较大时，每个任务需要占用更多时隙的资源，导致完成的任务减少，从而获得的收益更低。当$T_e= 10$ ms时，每个任务在单一时隙内完成，不发生抢占，因此LCFS‐p和LCFS‐np性能相同。随着 $T_e$升高，FCFS选择的任务变得更新鲜，因此当 $T_e \geq 50$ ms时，收益有所增加。

我们展示了PreDisc在不同用户数量 $N$下的性能，如图5所示。图5(a)表明，随着 $N$的增加，加权AoI逐渐接近上限100毫秒，因为边缘计算资源变得更加稀缺。PreDisc相对于其他机制的相对优势保持不变。收益性能如图5(b)所示，随着用户数量增加，收益显著提升，因为