移动边缘计算中成本‐延迟权衡的双侧优化

摘要

移动代码卸载（MCO）是一种将计算任务从移动设备卸载到由代码卸载服务提供商（CSP）管理的远程服务器的技术。如今，建议将远程服务器部署在网络边缘，以支持增强现实等对延迟极为敏感或需要高带宽的现代应用。迄今为止，先前的研究独立地处理了移动设备端的代码卸载策略以及CSP端的定价和服务器配置策略；此外，用户侧和CSP侧的系统模型尚未充分反映其实际特性。本文为双方设计了更贴近实际的模型，并在一个集成的MCO框架中同时考虑这两方面。通过利用李雅普诺夫漂移‐惩罚技术，我们在竞争场景和合作场景下分别提出了针对移动用户的代码卸载、本地CPU时钟频率和网络接口选择策略，以及针对CSP的MCO服务定价和服务器配置策略。在竞争场景中，我们提出了用于移动用户的Com‐UC算法和用于CSP的Com‐PC算法，目标是在每个队列稳定性约束下最小化各自的成本。在合作场景中，我们提出了Coo‐JC算法，旨在最小化移动用户与CSP的总成本。通过基于真实轨迹的仿真表明，与现有算法相比，Com‐UC最多可节省71%的成本，Com‐PC在相同延迟下可获得82%的利润增益；此外，移动用户与CSP之间的合作还能进一步降低成本和延迟。

索引术语

成本最小化，竞争场景和合作场景，代码卸载服务提供商（CSP），边缘计算，移动代码卸载，移动用户。

I. 引言

MOBILE 移动代码卸载服务（MCO）正作为一种突出的技术兴起，使移动设备能够卸载处理任务繁重任务（如语音/图像/视频处理）卸载到远程服务器。这些远程服务器通常位于数据中心，其计算能力远高于移动设备，但与移动设备在地理上相距较远。在这些数据中心进行的任务计算被称为云计算。尽管云计算能够方便地提供MCO服务，但往往难以满足对延迟敏感或与移动性相关的应用的需求[2],[3]。此外，由于普遍存在的移动设备和物联网（IoT）设备产生了越来越多的分布式数据，当前网络基础设施（尤其是蜂窝网络）的核心网络高度拥塞，导致难以将所有数据传输到云数据中心[4],[5]。为了克服这些限制，边缘计算[2],[3]最近成为下一代网络中有前景的技术之一。边缘计算的主要思想是将用于MCO的远程服务器部署在网络边缘，使其更靠近终端用户[6]，这与云计算不同。因此，边缘计算可为终端用户提供低延迟和具备移动性感知的MCO服务。

国际数据公司（IDC）报告称，到 2019[7]，超过40 %的数据将在靠近网络边缘或在网络边缘进行存储、处理、分析和响应。此外，许多联盟最近提出了新的边缘计算架构，例如OFC[8],MEC[9]和Cloudlets[10]。根据欧洲电信标准协会（ETSI）[11]，边缘服务器将位于LTE宏基站、无线网络控制器（RNC）或多技术基站汇聚点（例如公司、校园和体育场），以用于未来的5G蜂窝网络。

移动设备在使用本地CPU处理大量计算任务时会消耗大量能量，因为本地CPU功耗随时钟频率的增加呈指数级增长[12]。移动用户可以通过使用MCO服务将繁重任务卸载到边缘服务器，从而节省处理能耗并提升计算性能。然而，移动设备在将计算任务传输到边缘服务器时，不仅会消耗网络能耗（而非处理能耗），还需要为MCO服务以及蜂窝网络的使用支付费用。这种权衡导致了移动设备中的代码卸载决策问题，即选择在本地处理计算任务或将它们传输到边缘服务器，以及时钟频率调整和网络接口选择（蜂窝与Wi‐Fi之间）的问题。这三个问题的控制参数应结合计算任务的数量和处理密度1,移动设备的处理能力、网络速度和能量消耗，以及MCO和蜂窝网络的服务价格。

代码卸载服务提供商（CSP）在向订阅者提供MCO服务时可以获得利润，但同时需要向电力供应商支付用于运行边缘服务器的电费；因此，在收入（来自订阅者）和支出（支付给电力供应商）之间存在权衡。这种权衡导致CSP面临MCO服务定价和服务器配置问题，即边缘服务器的激活与分配问题。这些问题的控制参数应结合移动用户的支付意愿、计算任务的处理密度以及电费来确定。由于移动用户（例如网络速度[13]）和CSP（例如电费[14]）的一些因素在移动环境中是时变的，因此移动用户和CSP应根据变化的条件谨慎设计各自的策略。此外，移动用户与CSP之间的联合问题更具挑战性，因为两者相互关联、相互影响。

云服务提供商可以是商业公司之一，例如网络运营商（如AT&T）或第三方OTT（Over‐the‐top）服务供应商（如微软Azure[15]），也可以是公共机构之一，例如大学和医院[16]2。需要注意的是，公共机构可能会向其成员提供免费的代码卸载服务3。因此，我们可以将现实的边缘计算场景分为云服务提供商与移动用户之间的竞争场景和合作场景。在竞争场景中，云服务提供商（如网络运营商）的目标是最大化利润，而移动用户则希望通过向云服务提供商支付费用来使用MCO服务以最小化其成本（如能耗和货币成本）。另一方面，在合作场景中，云服务提供商（如大学）和移动用户（如学生）的统一目标是最大化他们的共同利益。

本文中，我们在两种不同场景下的移动边缘计算系统中构建了双侧控制4问题，具体如下：(i)竞争场景：用户与云服务提供商相互竞争，即各自旨在最小化满足队列稳定性约束的自身成本。(ii)合作场景：用户与云服务提供商进行合作，旨在最小化满足队列稳定性约束的社会成本。我们采用“李雅普诺夫漂移加惩罚”技术[17]来设计双侧控制算法，该算法无需预知未来任务到达、网络状态和计费信息。为了更真实地刻画移动代码卸载服务系统，我们考虑了移动用户与云服务提供商之间的交互、边缘服务器的有限计算能力、处理密度的异质性以及活跃边缘服务器的时变电价。我们基于真实世界测量参数（如 LTE/Wi‐Fi数据）进行了基于轨迹的仿真流行智能手机型号中的处理/网络能耗和速率。

本文的贡献总结如下。

1) 我们在一个统一的边缘计算框架中，为移动用户和代码卸载服务提供商（CSP）的策略与环境设计了一个实际的模型。
2) 我们引入了移动用户与云服务提供商之间的竞争场景和合作场景。在竞争场景中，移动用户和云服务提供商是自私的实体，例如，云服务提供商是商业公司。在合作场景中，云服务提供商可以被视为学校等公共机构；因此，移动用户和云服务提供商相互合作以最小化其总成本。
3) 我们提出了用户侧（Com‐UC）和CSP侧（Com‐PC）算法，分别旨在竞争场景下最小化移动用户和云服务提供商的成本，同时确保有限处理时间。具体而言，Com‐UC联合控制代码卸载策略、CPU时钟速度和无线接口，而Com‐PC联合控制MCO服务价格和活跃边缘服务器数量。此外，我们提出了一种双侧算法，即Coo‐JP，旨在合作场景下最小化社会成本，同时确保有限处理时间。
4) 我们使用在真实网络环境中由我们测量的实际参数以及来自多种高影响力参考文献的收集参数，对我们的算法进行了严格评估。然后我们证明，与现有方案相比，Com‐UC通过交换6 MB的平均队列积压（60秒延迟）节省了71%的成本，而Com‐PC在相同延迟下获得了82%的利润增益；此外，用户与云服务提供商的合作使他们实现了额外28%的社会成本降低和额外30%的延迟减少。

在本文的其余部分，我们在第二节总结了移动代码卸载的相关工作。在第三节描述了系统模型。在第四节，我们分别提出了竞争和合作场景下的控制算法。接着，在第五节，我们通过基于轨迹的仿真评估了所提出的算法。最后，我们在第六节对本文进行了总结。

II. 相关工作

用户侧移动代码卸载

自从Cuervo等[18],提出开创性工作以来，已有大量关于用户侧MCO[19],[20]的研究，旨在最小化能耗和处理延迟。Kosta等[19]提出了一种考虑卸载成本、能耗和执行时间优先级的代码卸载算法。然而，该算法是一种启发式算法，远未达到最优。Wen等[20]提出了一种最优代码卸载方案，旨在在给定处理延迟约束下最小化移动设备的能耗。但他们忽略了计算任务规模的变化、网络选择或移动设备的多宿主传输。例外的是，Kwak等[13]在一个移动代码卸载框架中考虑了这些因素异构类型的任务。然而，假设边缘服务器的处理能力是无限的，因此未考虑CSP侧的处理延迟。此外，他们仅关注设备能耗的最小化，而忽略了蜂窝数据费用和MCO服务费用等货币成本。Chen et al.[21]基于博弈论方法研究了共享无线接入的多个移动用户之间的代码卸载决策。

CSP侧移动代码卸载

诸如Windows Azure之类的商业云服务提供商已在MCO服务中对单位计算资源采用固定定价[15]。已有研究针对CSP侧的MCO[22]–[28],，旨在最小化CSP成本（例如运行远程服务器的电费），或最大化CSP从订阅者获得的收入。Lin等[22]提出了一种动态服务器规模调整算法，通过在预定义时间段内停用服务器来降低数据中心的能耗。Liu等[23]通过控制任务的接入和服务器分配，考虑了CSP的利润最大化问题。作为[23],的扩展，Chen等[24]引入了额外的控制维度——服务器CPU的频率调节，以实现进一步的节能。Ren等[25]研究了在地理上分布的数据中心之间进行计算任务的负载均衡，旨在最小化数据中心的能耗并保证不同用户组之间的吞吐量公平性。然而，这些研究[22]–[24]忽略了MCO服务的定价控制与终端用户的卸载决策之间的相互关联关系。换句话说，这些研究假设来自终端用户的卸载请求数量对CSP而言是已知的，而未考虑CSP策略和用户策略的影响。

为了捕捉终端用户根据MCO服务定价而产生的异构卸载决策，Wang et al.[26]提出了一种基于拍卖的定价算法，旨在增加云服务提供商的收入，并允许用户公平竞争以获取计算资源。Ren etal.[27]和Zhao et al.[28]开发了一种联合计算任务调度与定价技术，通过利用李雅普诺夫优化[17]来最大化云服务提供商的利润。尽管在[26]–[28],中考虑了控制卸载请求数量的动态定价，但其系统模型未涵盖影响用户卸载决策的各种用户侧因素，例如网络状态、本地设备的处理能力以及剩余计算任务的数量。

协作式移动代码卸载

Menache等[29]提出了一种定价与计算资源分配算法，以调控订阅者的接入，其目标是通过利用移动代码卸载系统来最大化移动用户和云服务提供商的社会效益。然而，他们忽略了移动设备的本地处理调整及其能量消耗。Song等[30]提出了一种在移动用户之间的协作式代码卸载方案，通过在WLAN环境下共享彼此的本地计算资源来实现。Chen等[31]研究了部署在小基站（SBS）上的单个边缘服务器之间的协作式代码卸载，以降低MCO服务的延迟。然而，这些工作[30],[31]忽视了移动设备与云服务提供商之间的协作。

III. 系统模型

我们在图1所示的边缘计算系统中展示了移动代码卸载（MCO）机制。我们考虑一个代码卸载服务提供商（CSP），其管理多个靠近终端用户的边缘服务器（例如，多技术基站汇聚点[16]），并支持代码卸载服务。我们将 i ∈I表示为在CSP注册使用MCO服务的移动用户。该用户 i向CSP上报其设备配置文件（例如，智能手机型号或规格）以及正在使用的应用程序。我们考虑一个时隙系统，以 t ∈ T={0, 1,…T−1}作为索引。接下来，我们将描述图1中边缘计算系统的各个部分的详细模型。

A. 计算任务与到达模型

在每个时隙 t，用户 i 请求 Ai(t)（比特）的计算任务。我们假设 Ai(t) 是一个独立同分布{i.i.d.}5过程，并且在每个时隙都是有界的，即 Ai(t) ≤ Ai max，对于所有 i ∈I成立。每个用户运行一种不同类型的应用，该应用具有处理密度 γi（周期/比特），定义为处理用户 i 的单位比特计算任务所需的CPU时钟周期。用户 i 的应用被认为已在用户 i 的设备和边缘服务器上预安装。本系统中的目标计算任务可以被分割为独立的子任务，并具有延迟容忍特性6（这类应用的示例可在许多代码卸载研究中找到，例如 [18]，相关参考文献也在其中）。到达任务被缓存到用户侧队列 Qi u( t) 中，该队列定义于第三节‐D，可通过两种类型的处理资源进行处理：(i)每个移动设备中的本地CPU资源，以及(ii)远程边缘服务器中的CPU资源。

B. 移动用户资源模型

通常，现代智能手机具有DVFS（动态电压频率调整）功能[32]7,，因此用户 i可以在每个时隙调整CPU时钟速度，即 si(t) ∈ S（周期/时隙），其中 S={0, s1, s2,…, smax}定义为移动设备可调CPU时钟速度的集合，而 si(t)= 0表示用户 i停止处理计算任务并使中央处理器进入空闲状态。我们考虑两种类型的无线接口，即蜂窝和Wi‐Fi，用于将数据从智能手机传输到边缘服务器。由于移动性和流量负载波动，蜂窝网络和Wi‐Fi网络的网络可用性及可达速率随时间变化。我们用 μi l(t) ∈[0, μi l,max]和 μi w(t) ∈[0, μi w,max]（比特/时隙）分别表示在时隙 t用户i通过蜂窝和Wi‐Fi网络接口可传输的计算任务量，例如，如果Wi‐Fi不可用，则μi w(t) = 0。由于边缘服务器位于终端用户附近， μi l(t)和 μi w(t)可通过使用接收信号强度指示（RSSI）和历史数据速率[33]的在线和离线估计方法进行预测。

在每个时隙，用户 i首先决定是将计算任务在本地处理，还是将计算任务传输到边缘服务器，即表示为 oi(t)的卸载策略。
oi(t)=
⎧ ⎪⎪⎨ ⎪⎪⎩
1
,如果移动设备中的计算任务被转移到边缘服务器，0,如果
移动设备中的计算任务在本地CPU中处理。
如果决定进行本地计算，用户 i 将选择本地CPU时钟频率 si(t)。否则，用户 i 将在蜂窝和Wi‐Fi之间选择活动网络接口，以将计算任务传输至边缘服务器，如下所示8。
θi l(t)={1, if cellular interface is activated, 0, otherwise.
θi w(t)={1, if Wi-Fi interface is activated, 0, otherwise.
此外，我们考虑了移动设备的最新多宿主技术，该技术能够同时使用蜂窝和Wi‐Fi网络，θi(t)=(θi l( t) θi w(t))=(1,1)。它通过MPTCP[34],[35]或HTTP聚合[36]来提升网络速度。

C. CSP资源模型

每个时隙，云服务提供商（CSP）决定每单位CPU周期的计算价格 pc( t) ≥ 0（美元/周期），以提供MCO服务。在我们的系统模型中，CSP采用时变定价方案，即计算价格可根据CSP的策略[28] 随时间变化。CSP拥有 nmax(t)个可用边缘服务器，其中 nmax(t) ∈{0, 1,…, N} 可在每个时隙[27]进行动态调整。每个边缘服务器具有有限处理能力服务器的处理能力用 sc（周期/时隙）表示。然后，云服务提供商决定用于处理用户 i请求的计算任务的活跃边缘服务器数量 ni(t)，即服务器配置。由于活跃边缘服务器的总数不能超过可用服务器的数量，我们考虑如下约束条件。
∑
i∈I
ni(t) ≤ nmax(t).

D. 队列模型

对于移动用户 i ∈I，我们用Qi u(t)表示用户侧计算任务队列（以比特为单位），对于云服务提供商，我们用 Qi c(t)表示在时隙 t的CSP侧队列（以比特为单位）。这些队列表示由用户 i请求但尚未完成的任务量。对于MCO服务， Qi u(t)和 Qi c(t)通常由用户 i和云服务提供商9共享。我们分别对用户侧和CSP侧的排队动态建模如下。
Qi u(t+ 1)=
[Qi u(t)−(1 − oi(t))
si(t) γi − oi(t)Ri(θi(t))+ Ai(t)]
+
, (1)
Qi c(t+ 1)=
[Q i sc
γi+ oi(t)Ri(θi(t))]
+
, ∀i ∈I, (2)
其中[x]+= max(x, 0)，且 Ri(θi(t))=. θi l(t)μ i w(t)
μi w(t)表示当用户 i决定 θi(t)时，转移至边缘服务器的计算任务量。用户侧队列的离开量取决于控制参数(oi(t) θi l(t)
θi w(t) si(t))。CSP侧队列的到达量和离开量分别取决于控制参数(oi(t) θi l(t) θi w(t))和 ni(t)。由于移动设备本地CP U中的si(t)（以及边缘服务器远程CPU中的 sc）的单位为周期/时隙，而 Q i u(t)（以及Q i c(t)）的单位为比特，因此为统一单位，队列中已处理的工作负载量（以比特为单位） 为 si(t)（以及 sc）除以 γi。

E. 成本模型

在移动设备中使用本地CPU资源处理计算任务会消耗中央处理器能量 Es(si (t))（单位：焦耳/时隙），该能量是CPU时钟速度的函数。我们假设 Es(·) 是时钟频率 si (t)[12] 11的凸的、可微的且递增的函数。另一方面，如果计算任务由边缘服务器的计算资源处理，则移动用户需要承担多种成本，如下：(i) 将计算任务传输到边缘服务器所产生的网络能耗成本（蜂窝网络为 El ，Wi‐Fi为 Ew ，单位：焦耳/时隙）；(ii)MCO服务成本（蜂窝网络为 pc(t)γ i μ i l( t)）
pc(t)γiμiw(t)（用于Wi‐Fi），用户需向云服务提供商支付，(iii)仅在蜂窝网络上应用的数据使用成本 plμi l(t)，其中 pl（单位为美元/比特）是每比特的蜂窝数据价格。我们假设 Wi‐Fi网络的使用是免费的。另一方面，云服务提供商通过在边缘服务器而非移动设备上处理任务，从移动用户处获得相同数量的金钱。然而，云服务提供商需要向电网支付电费以运行边缘服务器。我们将e(t)表示为在时隙 t激活一个边缘服务器所需的电价（单位为美元）。综上所述，用户hi u(t)和云服务提供商 hc(t)在时隙 t的成本（单位为美元）如下所示。
User i: hi u(t)=(1 − oi(t))αiEs(si(t))
+ oi(t)(θi l(t)D i w(t)Di w(t)),
CSP: hc(t)=∑
i∈I
ni(t)e(t)−∑
i∈I
oi(t)Ri(θi(t))γipc(t),
其中，Di l(t) =. αiEl+ pc(t)γ iμi l(t) + plμ i w(t) =. αiEw+ pc(t)γ iμi w(t) 分别表示用户 i通过蜂窝网络和 Wi‐Fi 网络卸载计算任务时产生的成本。对于用户 i， αi（单位为美元/焦耳）是一个将设备能耗转换为金钱的权重参数，该参数由人为因素决定，取决于对金钱和能源的敏感度，我们假设每个用户提前确定 αi。12

F. 系统模型的结构

我们基于移动用户与云服务提供商之间的竞争场景来描述系统流程。在此场景中，移动用户和云服务提供商是独立的实体，例如，云服务提供商是一家商业公司，如网络运营商或第三方OTT服务供应商。

在每个时隙的开始，云服务提供商（CSP）获知队列积压和网络（E, B）的状态，并做出定价和服务器供应（C）的决策。随后，每个移动用户根据云服务提供商（CSP）给出的服务价格（B），决定其卸载策略、本地CPU时钟频率以及网络接口激活。根据移动用户和云服务提供商的决策，计算任务被卸载至边缘服务器或在各设备内直接处理，其中排队模型（D）描述了被卸载或被处理的计算任务的动态到达与离开过程。此外，能耗以及成本模型（E）所定义的货币成本支付（或交换）也受到控制参数（即移动用户和云服务提供商的决策）的影响。最后，移动用户请求新的计算任务（A），并通过排队模型（D）将其缓存至用户侧队列。

另一方面，在合作场景中，云服务提供商（CSP）是学校或医院等公共机构；因此，CSP向移动用户提供免费的MCO服务。在此场景中，系统流程与竞争情况基本相同，只是省去了CSP的定价决策，即图1中的充电路径消失。表I总结了本节中使用的符号，以便于理解。

在仿真部分，我们根据韩国智能手机电池快充的价格设置了 α i。
| 符号 | 含义 |
| — | — |
| I | 移动用户集合 |
| Ai(t) | 用户 i在 t到达的计算任务 |
| γi | 用户 i的计算任务处理密度 |
| μi l(t) | 用户 i可处理的计算任务量 通过蜂窝接口在 t处传输 |
| μi w(t) | 用户 i可处理的计算任务量 通过Wi‐Fi接口在 t传输 |
| oi(t) | 用户 i在 t的卸载策略 |
| θi l(t) | 用户 i在 t的蜂窝接口激活 |
| θi w(t) | i在 t的Wi‐Fi接口激活 |
| si(t) | i在 t的本地CPU时钟频率 |
| sc | 边缘服务器的CPU时钟速度。|
| ni(t) | 在 t为用户 i的任务分配的边缘服务器数量 |
| nmax(t) | t处可用的边缘服务器数量 |
| pc(t) | t处每单位周期的MCO服务价格 |
| pl | 单位蜂窝数据价格 |
| e(t) | t处单位电价 |
| Qi u(t) | 用户 i在 t的用户侧队列积压 |
| Qi c(t) | 用户 i在 t时刻的CSP侧队列积压 |
| Es(si(t)) | 中央处理器在CPU时钟速度 si(t)下的能耗 |
| El | 激活蜂窝接口的能耗 |
| Ew | 激活Wi‐Fi接口的能耗 |
| αi | 用户 i的能量和金钱之间的权重参数 |

IV. 双侧控制算法

在本节中，我们提出了两个优化问题，其目标是在以下两种情况下，在满足队列稳定的条件下最小化成本：(i)竞争场景（即用户和云服务提供商的目标分别是各自最小化自身成本）；(ii)合作场景（即用户与云服务提供商进行合作，旨在最小化二者成本之和，即社会成本）。以竞争场景为例，我们考虑由负责CSP的网络运营商与负责移动用户的订阅者之间的竞争关系，其中各方（即网络运营商和订阅者）具有相互冲突的目标。以合作场景为例，我们考虑校园内的免费MCO服务，其中大学负责CSP，学生负责移动用户，如[16]中所述。针对竞争场景，我们设计了用户侧控制算法Com‐UC和CSP侧控制算法Com‐PC。针对合作场景，我们设计了联合控制算法Coo‐JC。最后，本节对所提出的Coo‐JC进行了理论分析。

A. 问题描述

竞争场景（Com‐U 和 Com‐P）以及合作场景（Coo‐UP）下的目标与约束总结于表II中，其中控制参数（o, θ, s, pc n ,）定义如下。
⎧ ⎪ ⎨
⎪ ⎩
o=(o i (t), ∀i ∈I, t ∈ T), θ=(θ i l (t), θ i w (t), ∀i ∈I, t ∈ T), s=(s i (t), ∀i ∈I, t ∈ T), p c =(pc(t), ∀t ∈ T), n=(n i (t), ∀i ∈I, t ∈ T).

（通信‐用户）的目标是通过在给定CSP的策略下控制（o i , θ i , s i）来最小化用户 i的平均成本。该目标受到用户侧和CSP侧队列稳定性的约束。

问题	目标	约束
（通信‐用户）	min (oi,θi, si) [lim T→∞ 1 T T −1 ∑ t=0 期望值{hi u(t) }], ∀i	上极限 T→∞ 1 T T −1 ∑ t=0 期望值[Qi u(t) + Qi c(t)]< ∞, oi(t) θi l(t) θi w(t) ∈{0, 1}, ∀i ∈I, t ∈ T, si(t) ∈ S, ∀i ∈I, t ∈ T,
（Com‐P）	最小化(pc,n)[lim T→∞ 1 T T −1 ∑ t=0 期望值{hc(t)}],	上极限 T→∞ 1 T T −1 ∑ t=0 期望值[∑ i∈I Qi c(t)]< ∞, pc(t) ≥ 0, ∀t ∈ T, ∑ i∈I ni(t) ≤ nmax(t) ∀t ∈ T,
（Coo‐UP）	最小化 (o,θ, s,n)[ lim T→∞ 1 T T −1 ∑ t=0 期望值 {∑ i∈I hi u(t)+ hc(t)}],	上极限 T→∞ 1 T T −1 ∑ t=0 期望值[∑ i∈I (Qi u(t) + Qi c(t) )]< ∞, oi(t) θi l(t) θi w(t) ∈{0, 1}, ∀i ∈I, t ∈ T, si(t) ∈ S, ∀i ∈I, t ∈ T, ∑ i∈I ni(t) ≤ nmax(t) ∀t ∈ T,

为了在有限时间内处理所有请求的计算任务。（Com‐P）的目标是通过控制（pc,n）以最小化云服务提供商的平均成本，前提是用户策略给定。该问题受到CSP侧队列稳定性的约束，因为云服务提供商必须在有限时间内处理来自用户的任务。（Coo‐UP）的目标是通过控制（o, θ, s,n）来最小化平均社会成本，并满足用户侧和CSP侧的队列稳定性约束。在时刻 t 的社会成本定义为∑i∈I hi u(t) + hc(t)，其包含由用户和云服务提供商产生的所有成本。由于MCO价格pc不影响社会成本（即云服务提供商从用户获得的收益等于用户向云服务提供商的支付），因此在合作场景中我们不考虑 pc。

B. 算法设计

我们利用“李雅普诺夫漂移‐惩罚”框架[17] 为问题（Com‐U）、独立优化问题（Com‐P）和协作优化问题（Coo‐UP）设计控制算法，其理论意义在于通过权衡延迟来最小化成本（或最大化利润），同时不损失容量（满足队列稳定性）。该技术的优势在于无需未来任务到达、网络状态和电价的信息，而仅需这些状态的当前信息。

制定逐时隙目标

首先，我们定义李雅普诺夫函数及其李雅普诺夫漂移函数如下。
(Com-U): L(t)=
1 2[(Q i u(t))
2 +(Q i c( t)) 2], (3)
ΔL(t)= E[L(t+ 1)− L(t) ∣ ∣ Q
i (t)], (4)
(Com-P): L(t)=
1 2[∑ i ∈ I
(Q i c( t)) 2], (5)
ΔL(t)= E[L(t+ 1)− L(t)∣ ∣Qc(t)], (6) （Coo‐UP）： L(t) =
1 2[∑ i∈I {(Q i u(t)) 2+(Q i c(t)) 2+(Q i u(t)+ Q i c(t)) 2}(7],) ΔL(t)= E[L(t+ 1)− L(t)∣ ∣Q(t)], (8)
其中
⎧ ⎪⎨ ⎪⎩ Qu(t)=(Q 1 u(t), Q 2 u(t),…, Q I u(t)), Qc(t)=(Q 1 c(t) , Q 2 c(t) ,…, Q I c(t)), Q i(t)=(Q i u(t), Q i c( t)), Q(t)=(Qu(t), Qc(t)).
在李雅普诺夫函数（3）中，(Q i u( t))2用于稳定用户侧队列，而(Q i c( t))2用于避免CSP侧拥塞。式（5）和（7）中的李雅普诺夫函数旨在公平地稳定各用户之间的队列。函数（5）旨在稳定CSP侧队列。在函数（7）中，(Q i u(t))2和(Q i c( t)) 2分别用于稳定用户侧和CSP侧队列，而(Q i u(t) + Q i c( t)) 2用于稳定用户 i的系统级队列。然后，针对每个目标函数的李雅普诺夫漂移最小化问题（4）、（6）和（8）分别与表II中的约束具有相同的含义。

接下来，我们定义“李雅普诺夫漂移加惩罚”函数，其中惩罚函数为时隙 t 期间的期望成本，如下所示。
(Com-U):ΔL(t)+ V E[hi u(t) ∣ ∣ Q
i (t)], (9)
(Com-P):ΔL(t)+ V E[hc( t) ∣ ∣ Qc( t)], (10)

(Coo-UP):ΔL(t)+ V E[∑ i∈I hi u(t)+ hc(t)∣∣Q(t)], (11)

其中 V是一个非负参数，用于调整成本与延迟之间的权衡，即与处理延迟减少相比，我们在多大程度上关注成本降低13。我们注意到，根据利特尔定律[39],，平均延迟可以转换为平均队列积压除以平均到达率。因此，在给定平均到达率的情况下，我们将交替使用平均延迟和平均队列积压这两个术语。于是，表II中针对（Com‐U）、（Com‐P）和（Coo‐UP）的原始长期最小化目标被转化为在每个时隙 t分别最小化短期函数(9)∼(11)。关键推导步骤是获得李雅普诺夫漂移加惩罚的上界。推导上界。我们利用排队动态(1)、(2)以及第三节中假设的计算任务到达、中央处理器和网络速度的界限，来推导(9)∼(11)的上界。

引理1

在任何可能的控制变量 (o(t) θ(t),s(t), pc(t)) 下，我们有：
(Com-U):ΔL(t)+ V E[hi u(t)∣ ∣Q i(t)]
≤ B1+ V E[hi u(t)∣ ∣Q i(t)] −E[[(1−oi(t)) si(t) γi+oi(t)Ri(θi(t))−Ai(t)]Q i u(t)∣ ∣Q i(t)]
−E[[ni(t) sc γi − oi(t)Ri(θi(t))] Q i c(t) ∣ ∣Q i(t)],
(Com-P):: ΔL(t)+ V E[hc(t) ∣
≤ B2+ V E[hc(t) ∣
−E[∑ i∈I[ni (t) sc γi − oi (t)R i(θi (t))] Q i c(t) ∣
(Com-UP):ΔL(t)+ V E[∑ i ∈I hi u(t)+ hc(t) ∣
≤ B3+ V E[∑ i ∈ I h i u(t)+ hc(t) ∣
−E[∑ i ∈ I[n i (t) sc γi − o i (t)R i(θ i (t))] Q i c( t)∣ ∣Q(t)]
−E[∑ i ∈I[(1−o i (t)) s i (t) γ i +o i (t)R i(θ i (t))−A i (t)]Q i u(t) ∣ ∣ Q(t)]
−E[∑ i ∈ I (1−o i (t)) s i (t) γ i +n i (t) sc γ i −A i (t) ∣ ∣ Q(t)],
(12)
我们建议读者参考 [ 33 ] , [ 38 ] 以了解实际的 V控制。这些工作的作者根据瞬时延迟动态控制 V。
where
⎧ ⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎩
B1= 1 2[(Amiax)2+(smax) 2 (γ i)2+ 2(μi l,max+ μiw,max)2+(sc)2 (γ i)2],
B2= 1 2∑i∈I[(sc)2 (γ i)2+(μi l,max+ μiw,max)2], B3=∑i∈I[(Amiax)2+(smax) 2 (γ i)2+(μi l,max+μi w,max)2+(sc)2 (γ i)2+ smaxsc (γ i)2].
证明： 证明见附录A。

C. 竞争场景中成本最小化的控制算法

针对用户与云服务提供商（CSP）之间的竞争场景，我们通过求解（Com‐U）：(oi(t) θi l(t) θi w(t) si(t)) 以得到用户 i 的卸载决策，以及求解（Com‐P）：(n(t) pc(t)) 以得到CSP的独立优化问题（Com‐P），分别在每个时隙最小化(9)和(10)的上界，从而提出了Com‐UC和Com‐PC算法。

用户侧控制算法(Com-UC)

每个用户在时隙 t考虑用户侧和云服务提供商侧的队列积压、网络状态以及MCO价格。在做出卸载策略oi(t)的决策之前，用户会考虑两种情况：用户选择(i)本地处理和(ii)代码卸载。
1) 如果选择本地处理（oi(t) = 0），则本地CPU时钟选择问题可表述如下。
min si(t)∈S[V αiEs(si(t))− si(t) γi Q i s,t.(13)
由于 Es(·)是CPU时钟速度上的凸可微函数，因此可以通过求导轻松地从连续的时钟频率集合中找到最优的CPU时钟速度 si u(t) #。
si u(t) #=(E ˙s) −1(Q i u(t) V γiαi) . (14)
由于可调节的CPU时钟速度集合 Su是离散化的，我们必须检查距离 si u( t)#最近的左右两个可调时钟速度点，并选择使(13)最小化(13)的时钟速度 si u( t)。在 (13)中，随着 si(t)变快，移动设备可以通过消耗更多能量来处理更多的计算任务。从(14)可以看出，当用户侧剩余较多计算任务(Q i u( t))且电池能量的价值变低时(α i )，最优时钟速度会增加。
2) 否则，如果选择代码卸载（o i (t) = 1），则网络接口选择问题可分解为蜂窝和Wi‐Fi的开关问题，如下所示。
min θ i l ( t )∈{ 0 , 1 } θ i l( t)[VD i l( t)−μ i l( t)(Q i u(t)−Q i c(t))]=Ω i l,t( pc(t)),
min θ i w ( t )∈{ 0 , 1 } θ i w(t)[VD i w(t)−μ i w(t)(Q i u(t)−Q i c(t))]=Ω i w,t( pc(t)).
我们可以直接推导出网络接口选择算法(θi l(t) θwi(t))如下。
θi l(t)={1, if V Di l(t)<μi l(t)(Qi u(t)−Qi c(t)), 0, otherwise, (15)
θi w(t)={1, if V Di w(t)<μi w(t)(Qi u(t)−Qi c(t)), 0, otherwise.
(16)
在(15)中，当大量计算任务滞留在用户侧(Qi u(t))、CSP侧的处理队列积压(Qi s(t))降低以及计算价格(pc(t))变得更便宜时，网络接口更有可能被激活。此外，当计算价格和蜂窝数据价格相对于用户侧与CSP侧之间的队列差异足够低时，较高的网络速度(μi l(t)和μi w(t))会使网络接口被激活。我们注意到，由于额外的数据成本 plμ i l(t)，蜂窝网络被激活的倾向比 Wi‐Fi网络更为保守。
基于上述结果，用户决定卸载策略oi(t)如下。
oi(t)={1, if Ωi s,t ≥ Ωi l,t(pc(t))+ Ωi w,t(pc(t)), 0, otherwise.
(17)
为了确定卸载策略（17），用户需在成本降低和队列稳定方面权衡本地处理与代码卸载哪种决策更有利。我们观察到，当用户侧队列积压远大于CSP侧队列积压（Q i u(t) Q i c(t)）、网络信道状态良好且计算价格较低时，用户更倾向于进行代码卸载（oi(t)= 1）。这意味着用户会根据机会将计算任务分配给用户侧和CSP侧。我们注意到，用户侧控制算法的复杂度较低，因为每个控制变量只需通过比较两个选项的值即可确定。

CSP侧控制算法（Com-PC）

在CSP侧，最小化问题可分解为以下两个子问题：(a) 服务器配置和(b) MCO服务定价。
1) 服务器配置问题可以表述如下。
min n(t)[∑ i ∈ I n i (t){V e(t)− sc γi Q i c( t)}],
subject to∑ i ∈ I n i (t) ≤ nmax(t). (18)
为了解决问题 (18)，云服务提供商将用户集 J 定义如下。
J={i ∈I|V e(t)< s c γ i Q i c( t)}. (19)
对于所有用户 i ∈ J，云服务提供商倾向于分配边缘服务器来处理用户 i 的计算任务，以减少延迟，因为大量任务仍停留在云服务提供商侧的队列 Q i c (t) 中。然而，由于可用服务器的总数受限于 n max( t)，云服务提供商分配最小化 Qic(t γ i sc ), nmax(t))服务器分配给集合 Qic(t)γ i中值最高的用户。该过程以贪心方式迭代，直到没有可用服务器或 |J| 次迭代完成。我们可以观察到，CSP侧在用户之间的排队延迟方面公平地服务CSP侧队列。需要注意的是，CSP侧服务器配置算法的复杂度为 O(|I|2)，因为CSP需要根据 Qi c(t) γ i对用户排序。
2) MCO服务定价问题可以表述如下。
min p c(t)≥0[∑ i∈I oi(t)Ri(θi(t))[Qi c(t)− V pc(t)γ i]]
= min p c(t)≥0[∑ i∈I Υi(pc(t))], (20)
其中oi(t)、 θi l(t)和 θi w(t)依赖于 pc(t)。在(20)中，云服务提供商面临着一个权衡：既要从用户处获取更多金钱，又要同时减少云服务提供商侧队列的增长。遗憾的是，无法将问题(20)分解为针对每个用户的子问题，而必须检查所有 pc(t) ≥ 0以找到最优的MCO服务价格，这需要很高的复杂度。然而，我们引入了一种方法，利用引理2，在不损失最优性的情况下轻松找到该价格。

引理2

我们可以通过检查一组转换价格 Ptrans来找到最优的 MCO服务价格 pc(t)，其中 |Ptrans| ≤ 2|I|。
证明： 为了证明引理2，我们表明对于每个移动用户而言，最多存在两个转换价格，使得该用户改变其策略（例如，与 oi(t)相关的卸载策略，或与(20)中的 Ri(θi(t))相关的激活网络接口数量）。然后我们可以说明，(20)中用户 i的函数 Υi(pc(t))在 pc(t)上是一个被截断的、部分递减的线性函数，其中截断点即为转换价格。同理，对于移动用户集合 I，∑i ∈I Υi(pc(t))的性质与 Υi(pc(t))相同，云服务提供商可以通过检查最多 2|I|个转换价格来找到∑i ∈ I Υ i(pc(t))的最大值。详细证明见附录B。
然后，我们针对竞争场景的Com‐UC和Com‐PC算法可以描述如下。

算法1： 竞争场景的算法描述

在每个时隙 t，
CSP侧控制 (Com-PC): 1: 通过 J找到用户集合(19).
2：初始化所有 i ∈I 和 nuse= 0 的 ni(t) = 0。
3: 当 J= φ 且 nuse= nmax(t) 时，
4: j= arg mini∈J Qi c(t)γ i和 nj(t)=最小化( Qj c(t)γ j sc nmax(t) − nuse)。
5: nuse= nuse+ nj(t) 且 J= J −{j}。
6:结束循环
7: 根据引理2，找到转换价格集合 Ptrans。
8: pc(t)= arg min p c(t)∈Ptrans∪{∞}[∑i∈I Υ i(pc(t))].
User-s e contro om‐U C) f h
1: if Ωi s,t< Ωi l,t(pc(t))+ Ωi w,t(pc(t)), 2: Select oi(t)= 0, θi l(t)= 0 and θi w(t)= 0.
Select si(t) based on(14).
3:否则
4: Select oi(t)= 1, si(t)= 0.
Select θi l(t) and θi w(t) based on(15) and(16), respectively.
5:结束如果
根据排队动态(1)和(2)更新所有 i ∈I的队列 Qi u(t) Qi c(t)。

D. 合作场景中成本最小化的控制算法

对于用户与云服务提供商之间的合作场景，我们通过为用户和云服务提供商寻找(o(t) θ(t) s(t) n(t))，提出了一种 Coo‐JC算法，以在每个时隙最小化(11)的上界。幸运的是，我们可以将Coo‐JC算法独立地分解为用户侧和CSP侧，但每个控制变量的操作均基于社会成本和延迟，相较于竞争场景。

算法2： 合作场景的算法描述

场景（Coo‐JC）。
在每个时隙 t , CSP侧控制:
1: 查找用户集合 J˜由(21)得出。
2: 初始化所有 i ∈I和 nuse= 0的 ni(t) = 0。
3:当 J˜=且 nuse= nmax t， φ ()
4: j= arg min i∈J ˜ Qi u(t)+ 2Qi c(t) γi and nj(t)= min(Qjc(t)γj sc , nmax(t)− nuse).
5: nuse= nuse+ n(t) 且 J= J −{j}。 ˜ ˜
6:结束循环
用户侧控制：对于每个用户 i，
1: if Ω˜i s,t< Ω˜i l,t(pc(t)) + Ω˜i w,t(pc(t))，
选择 oi(t) = 0， θi l(t) = 0和 θi w(t) = 0。
根据 (22) 选择 si(t)。
3:否则
4:选择 oi(t) = 1, si(t) = 0。
根据(23)和(24)选择 θi l(t)和 θi w(t) 分别。
5:结束如果
根据所有 i ∈I 更新队列 Qi u(t) Qi c(t) 排队动态 (1) 和 (2)。

期望值. Coo-J C的性能分析

我们表明，当采用Coo‐JC算法时，用户侧和CSP侧的时间平均社会成本以及时间平均队列积压之和可由以下定理2进行上界约束。在证明这一点之前，我们在定理1中给出了最优策略的存在性，该策略与队列积压无关，并在满足队列稳定性的条件下优化社会成本。

定理1

对于容量区域14Λ内任意的计算任务到达率向量 λ，其中 λ i=期望值[A i (t){v8, ∀i ∈I，存在一个稳态随机控制策略 (o(t){v14, θ(t){v19,s(t){v24,n(t) ∗ )，该策略在每个时隙 t均独立于当前的队列积压，并满足以下条件：对于所有 i ∈I，
E[(1 − o i (t) ∗ ) s i (t) ∗ γ i + o i (t) ∗ R i (θ i (t) ∗ )] ≥ λ i ,(25)
请注意，容量区域指的是系统能够在有限时间内处理的所有任务到达的集合。

定理2

假设 t ∈{0, 1,…, T −1}且计算任务的到达率向量位于容量区域 λ ∈ Λ内部。那么，在Coo‐JC算法下，我们有：
lim sup T→∞ 1 T T −1 ∑ t=0 E[∑ i ∈I h i u(t)+ h c(t)] ≤ Ψ(λ+ ε)+ B3 V ,
lim sup T→∞ 1 T T − 1 ∑ t=0 E[∑ i ∈ I {Q i u(t)+ Q i c(t)}] ≤ B 3+ V Ψ(λ+ ε) ε ,
其中 ε> 0使得 λ+ ε=(λ 1+ ε, λ 2+ ε,…, λ I+ ε) ∈ Λ。定理2意味着，对于给定的成本‐延迟权衡参数V，Coo‐JC算法在保持平均队列积压为 O(V)的同时，实现了与最优平均社会成本之间 O( 1/V)的差距。注意，如果我们令 V和 ε趋近于无穷大，则零，Coo‐JC算法实现最优社会成本。
证明： 我们从定理1中的稳态随机控制策略推导出引理1中短期目标函数的界限。然后，利用随机化策略的队列无关特性和迭代期望定律，可以证明定理2。详细证明见附录C。

V. 基于轨迹的仿真

A. 测量与轨迹

能量测量

我们使用Monsoon电源监控器[42]测量了配备LTE芯片组的Galaxy Note[41]智能手机的能耗。我们测量了中央处理器在多个时钟频率（0.1∼1.4 GHz）下的能耗。然后，我们将参数(κ, ϕ, ρ)拟合到[12]中的典型CPU能耗模型，其中Δt表示一个时隙的时间持续时间（单位为秒），如下所示。
Es(s i(t))=(κ(si(t))ϕ+ ρ)Δt.
LTE和Wi‐Fi网络的测量能耗分别为2605毫焦/秒和1225毫焦/秒，中央处理器能量参数为(κ, ϕ, ρ) =(0.33,3.00, 0.10)。

真实轨迹

我们收集了八个包含LTE和Wi‐Fi网络可用性及上行吞吐量的轨迹。这些数据针对三个网络运营商以及多种移动场景进行测量，包括固定位置、在韩国市中心步行以及在高速公路上驾驶。上行吞吐量轨迹通过每分钟向我们的私有服务器上传一个5 MB的虚拟文件并记录传输时间来测量。测得的LTE和Wi‐Fi平均上行吞吐量分别为5.9 Mbps和6.4 Mbps，Wi‐Fi接入点的时间覆盖率为63%。为了运行仿真，我们为每位用户选用一条LTE和Wi‐Fi的上行吞吐量及可用性轨迹。为了生成用户的计算任务到达，我们使用了一个YouTube视频大小分布的数据集[43]并对其进行重新缩放，使得平均视频大小为12.6 MB。我们采用美国加利福尼亚州的真实电费数据[44]，其时间粒度为5分钟。对于LTE数据价格，我们采用韩国某网络运营商的统一资费计划（pl= 1.16 × 10−9美元/比特），其中1 GB LTE数据使用的费用为$10[45]。

B. 仿真设置

我们考虑一种场景：携带Galaxy Note的移动用户在 LTE覆盖范围内以及间歇性的Wi‐Fi覆盖范围内移动。这些用户运行的应用程序会产生可卸载的计算任务，任务以伯努利过程到达。移动用户的处理密度设置为200至6000周期/比特16。我们主要针对3000周期/比特的处理密度进行仿真，该处理密度通常适用于棋类游戏、视频转码和人脸识别应用[13]。为了便于分析，我们将所有用户的能量‐ 金钱权重参数设置为相同的αi= 2.44 × 10−4美元/焦耳。该值通过韩国便利店智能手机快速充电价格的5倍除以 Galaxy Note的电池容量计算得出。对于CSP侧，我们假设云服务提供商拥有边缘服务器，每个时隙可用的服务器数量在范围[1, |I|]内均匀分布。电费也是时变的[44]，其平均值为每激活一台服务器1秒需要$5.5×10−5[44]。详细的仿真参数汇总于表III。

用户数量	80
实验时间[小时]	6
平均到达速率[兆比特/秒]	0.96
处理密度[周期/比特]	200∼6000[13]
能耗（LTE，Wi‐Fi）[毫焦/秒]	(2605, 1225)[13]
中央处理器能耗参数 (κ, ϕ, ρ)	(0.33, 3.00, 0.10)[12]
平均上行吞吐量（LTE，Wi‐Fi）[兆比特/秒]	(5.9, 6.4)[1]
LTE数据价格 [$/bit]	1.16 × 10−9[45]
能量‐金钱权重参数 [$/J]	2.44 × 10−4
每台服务器单位平均电价 [$/秒]	5.5 × 10−5[44]
CSP可用服务器数量	uniform[1, 80]
移动设备的处理能力为[GHz]	1.4[41]
单个边缘服务器的处理能力 [GHz]	3.0[15]

作为性能指标，我们观察用户和云服务提供商的平均成本以及平均队列积压。在竞争场景中，我们将用户侧的 Com‐UC与现有的代码卸载算法[18]–[20]进行比较。同时，我们将CSP侧的Com‐PC与当前商业云服务提供商部署的基线算法进行比较。对于用户侧所有对比的算法，CPU速度由DVFS方案[32]选定。对于MA UI[18],，仅当当前任务可在指定延迟内完成传输时才选择代码卸载。对于 ThinkAir[19],，仅当网络的延迟和能量消耗均低于本地处理时才选择代码卸载。对于OAEP17 [20],，当网络的能量效率（速度/能量）高于本地处理时才选择代码卸载。Local-only和Edge-only策略分别始终采用本地处理以及使用所有可用网络进行代码卸载。在CSP侧，基线算法采用固定定价策略，并不会故意推迟任务处理（即尽可能激活边缘服务器来处理计算任务）。我们将Coo‐JC算法与 （Com‐UC+Com‐PC）进行比较，以验证用户与云服务提供商之间协作的优势。

C. 仿真结果1—竞争场景 rio

成本-延迟权衡

图2(a)描绘了当CSP采用Com‐PC时，Com‐UC和现有算法在用户侧以及CSP侧的用户平均成本与平均稳定队列积压总和。首先，我们观察到Com-UC通过仅牺牲6MB队列积压（50秒）实现了71%的成本节省我们用OAEP表示[ 20 ] 中的最优应用执行策略。

延迟），这意味着在付出少量延迟的情况下，存在大幅成本节约的有效空间（见圆点虚线）。成本节约来源于：(i) 根据当前队列积压调整本地CPU时钟频率，从而节省中央处理器能量；(ii) 通过考虑时变的MCO环境， opportunistically 将计算任务转移至CSP。应注意，高效的 成本‐延迟权衡区域对应于平均队列积压从4 MB到10 MB的范围（参见图2(a)的斜率）。此外，移动用户可根据目标应用的延迟容忍度调节成本‐延迟权衡参数 V。在用户侧控制算法的极端情况下，仅本地和仅边缘 （具有不同的DVFS阈值）分别表现出低成本高延迟和高成本低延迟。这些结果表明，需要一种智能的用户侧控制算法，以根据用户需求调节成本‐延迟权衡。其他对比算法的缺点如下：MAUI未考虑智能手机的成本（能耗、货币成本），即使网络速度高于本地CPU速度，只要延迟变大，就始终选择本地处理；ThinkAir无法根据当前计算任务积压情况在成本与延迟之间动态权衡，原因是它仅在网络的能耗和延迟均优于本地处理时才选择代码卸载，缺乏灵活性；OAEP只要代码卸载比本地处理更节能就会选择卸载，即使MCO价格较高也是如此。我们观察到，Com-UC优于现有算法，在队列积压为43 MB时相比MAUI成本降低60 %，在6.7 MB时相比ThinkAir成本降低35%，在30 MB时相比OAEP成本降低73%。Com‐UC优于现有算法的原因在于，它通过利用时变网络状态、MCO和LTE数据价格以及剩余队列积压的机会，联合优化了卸载策略、CPU时钟选择和网络选择。

多宿主技术的影响

我们量化了在MCO环境中多宿主技术对移动用户产生的连锁效应。为此，我们模拟了一个不支持多宿主的Com‐UC，该场景下无法选择蜂窝和Wi‐Fi接口进行传输，

与原始的Com‐UC算法进行比较。图2(b)展示了当多宿主可用时，移动用户的成本降低百分比相对于多宿主不可用时的情况。随着平均队列积压的增大，成本降低迅速下降，即当平均队列积压达到17 MB时，成本降低百分比低于5%。原因是当用户可以容忍较长的处理延迟时，无需同时激活蜂窝和Wi‐Fi接口以提高传输速度（这会带来较高的能量和金钱成本）。然而，当用户要求较短的处理延迟时，多宿主技术显著降低了用户成本，例如在平均队列积压为6 MB时成本降低达39%。这表明多宿主技术对延迟敏感型应用的性能具有显著影响。

动态定价与服务器配置的影响

为了评估我们的 Com‐PC算法，我们在移动用户采用Com‐UC的情况下，将Com‐PC与基线算法进行比较。基线算法对MCO服务采用固定定价，并尽可能激活边缘服务器来处理计算任务，而不考虑电费的变化。图3展示了CSP的平均队列积压以及利润（来自用户的收入减去电费）。对于基线算法，随着固定MCO价格降低，由于用户对计算任务的请求增加，CSP侧队列积压逐渐增大。然而，CSP的利润随MCO价格呈现出抛物线趋势，其鞍点（可实现最高利润的价格）为2.3 × 10−14美元/周期，这是我们在仿真中得出的结果。与固定MCO价格为2.3 × 10−14美元/周期的基线算法相比，Com-PC实现了82%的利润增益，同时保持了相近的平均队列积压（1.2 MB）。原因是Com‐PC通过时变定价充分利用了用户支付意愿的差异，同时还利用了时变电价的机会，在满足队列稳定性的前提下降低了边缘服务器的运行成本。

用户相关参数的影响

为了观察微观层面的情况，我们分析了具有不同用户参数的每个用户的已处理计算任务。图4显示了每个移动用户的计算任务中由本地CPU处理、通过蜂窝网络卸载以及通过Wi‐Fi网络卸载的比例，即卸载比率。在图4(a)中，我们模拟了所有移动用户的 Wi‐Fi网络时间覆盖率和平均数据速率相同（分别为63% 和6.4 Mbps）的情况，并绘制了按蜂窝平均数据速率降序排列用户索引后的卸载比率。（最大值：8.5 Mbps，最小值：4.9 Mbps）。随着平均蜂窝数据速率的提高，卸载到边缘服务器的计算任务比率 （绿色+蓝色）增加，原因是蜂窝接口的能量效率变得更高。与此同时，所有移动用户的Wi‐Fi卸载比率（绿色）相近，这意味着即使在平均蜂窝数据速率足够高的情况下， Wi‐Fi网络通常也比蜂窝网络更受青睐，因为在我们的仿真设置中，Wi‐Fi卸载所需的能量和货币成本低于蜂窝卸载。

在图4(b)中，我们模拟了所有移动用户的蜂窝网络的平均数据速率相同（5.9 兆比特/秒）的情况，并绘制了用户索引按平均Wi‐Fi数据速率降序排列（最大值：10 兆比特/秒，最小值：3 兆比特/秒）时的卸载比率。我们观察到，由于与图4(a)类似的原因，当移动用户的平均Wi‐Fi数据速率越高时，蜂窝和Wi‐Fi卸载比率之和也越高。然而，蜂窝卸载比率（蓝色）却更低，因为在数据速率、能量效率和货币成本方面，良好的Wi‐Fi连接总是优于蜂窝网络。尽管如此，由于Wi‐Fi网络存在间歇性连接，即使在最佳 Wi‐Fi条件下，移动用户的蜂窝卸载比率仍保持在30%。

在图4(c)中，我们模拟了所有移动用户的蜂窝网络和 Wi‐Fi网络的平均数据速率相同的情况（分别为5.9 Mbps、6.4 Mbps），并绘制了卸载比率，其中用户索引按计算任务的处理密度降序排列（最小值：200 周期/比特，最大值：6000 周期/比特）。对于具有低处理密度任务的移动用户，几乎所有的计算任务都在本地处理（黄色），因为在处理负载较轻的任务场景下，使用低时钟速度的本地CPU是最具成本效益的方法。另一方面，当计算任务的处理密度较高时，由于需要更高的CPU时钟速度，本地处理的负担增加，而将计算任务传输到边缘服务器的每周期 （能量和数据）成本变得更低。因此，卸载到边缘服务器的计算任务比例更高。我们观察到，处理密度最高的用户 （6000 周期/比特18）将其90%的计算任务进行了卸载。

D. 模拟结果2—合作增益

成本-延迟权衡

我们比较了在用户与云服务提供商合作（Coo‐JC）或不合作（Com‐UC+ Com‐PC）时提出的两种双侧控制算法。图5(a)和(b)分别展示了在相同平均队列积压和社会成本下，Coo‐JC相对于（Com‐UC+Com‐PC）的社会成本降低和队列积压减少情况。当平均队列积压为10 MB时，合作可实现28%的成本降低；当社会成本为20美元时，合作可实现30%的队列积压减少，相较于竞争场景。这些合作收益主要来自于移动用户在无需承担MCO服务价格负担的情况下将计算任务转移给云服务提供商。此外，云服务提供商主动处理这些

不同蜂窝网络平均数据速率下的移动用户卸载比率。(b) 不同 Wi‐Fi网络平均数据速率下的移动用户卸载比率。(c) 不同计算任务处理密度下的移动用户卸载比率。)

在相同平均队列积压下的社会成本降低百分比。(b) 在相同社会成本下的队列积压减少百分比。)

通过考虑用户侧和CSP侧的剩余任务来管理CSP侧队列。当队列积压（即社会成本）变大时，由于控制算法在成本‐ 延迟权衡参数 V极大或极小时表现相似，社会成本降低 （即队列积压减少）会变小。当 V变得极大时，移动用户会尝试以最低的CPU时钟速度仅通过本地处理来最小化计算任务的处理；另一方面，当 V变得极小时，移动用户会尝试通过利用所有可用的网络接口仅进行代码卸载来最大化处理计算任务。

VI. 结论

在本文中，我们研究了移动边缘计算系统中移动用户和代码卸载服务提供商（CSP）的成本‐延迟权衡。我们提出了一种在保证有限处理延迟的前提下实现能耗/货币成本最小化的算法。在竞争场景下，我们提出了一种用户侧控制算法，即Com‐UC，用于控制卸载策略、本地CPU时钟频率以及网络接口激活。同时，我们还提出了一种CSP侧控制算法，即Com‐PC，用于控制服务器配置和移动代码卸载（MCO）服务价格。此外，在合作场景下，我们提出了联合用户‐CSP控制算法，即Coo‐JC。基于实际测量的轨迹驱动仿真结果表明，我们的控制算法与现有算法相比，可为用户和云服务提供商带来显著的成本节约。本文将为云服务提供商提供管理MCO服务的指导原则，并为移动用户在竞争场景和合作场景下高效利用本地和边缘计算资源提供相应的指导原则。我们的工作可以扩展到多CSP环境，其中每个CSP位于不同地点（导致电价不同），并具有不同的计算能力。随后，我们可以设想多个CSP相互竞争的场景，移动用户需要进行额外的决策，例如选择能够提供高质量卸载服务且价格较低的CSP。这将作为未来工作加以研究。