面向协同移动边缘计算网络的分式任务卸载:带非线性约束的凸优化与分布式求解

摘要：移动边缘计算（MEC）可有效处理边缘服务器上计算密集、时延敏感的移动任务。但服务器间资源不均及高通信、计算成本，使高效任务卸载决策极具挑战。本文研究合作式MEC网络约束卸载问题，多边缘服务器与云中心协作处理移动设备任务。我们将其建模为一般凸约束优化问题，区别于现有仅关注单一性能指标的模型，本文模型可涵盖服务时延、能耗及二者组合，且除标准线性约束外，还引入资源和时延相关的非线性不等式约束。我们提出基于梯度投影与虚拟队列的分布式算法，使边缘服务器仅通过本地通信确定卸载决策，无需有瓶颈的中心处理器。证明其以次线性速率收敛至最优分配，仿真验证其效率且计算复杂度低于基线算法。

在大数据与万物互联的时代，自动驾驶、交互式游戏、在线目标识别等移动应用迅速普及，这类应用往往需高算力支撑与极低服务时延[1][2]。然而，移动终端受限于电池容量与处理能力，难以独立满足需求。移动云计算（MCC）曾通过将任务卸载至远程云中心缓解此矛盾[3][4]，但地理距离导致传输时延依旧显著。

移动边缘计算（MEC）通过在无线接入网边缘部署存储与计算资源来解决上述困境[5]，使终端可将过载任务交给邻近边缘服务器处理，从而缩短传输时延。现有研究[6–11]多假设各边缘服务器独立处理接收任务或与云中心单向协作，存在两大痛点：

• 资源异构与孤岛效应：边缘服务器算力有限且分布不均，独立处理易造成负载失衡与资源浪费；
• 云边回传开销大：大量卸载任务回传云中心会引发长时延与高能耗。

合作式MEC[12–19]通过边边协作（边缘服务器之间）与云边协作（边缘与云中心之间）实现跨节点负载均衡，成为近年热点。如图1所示，合作机制能动态分配任务至最优节点，提升整体资源利用率。Fig. 1. Cooperative MEC network consisting of a cloud center, multiple edge servers and multiple mobile devices.

然而，现有工作在建模与算法层面仍有局限：多数忽略云资源成本[12–17]；常将资源或能量约束简化为线性形式，难以刻画实际系统中的非线性特性（如带宽、能耗、时延硬约束）[11][14][23][30–32]；分布式算法要么依赖中心节点收集全局信息（隐私与瓶颈风险）[13][18][19]，要么计算复杂度高[14][23]。

针对这一难题，上海科技大学信息科学与技术学院的王丹丹、朱鸿斌、邱晨阳、周勇与陆疌在《IEEE Transactions on Vehicular Technology》2024年发表本文，提出一种更通用的带非线性约束的凸优化建模框架，并设计不依赖中心节点的分布式算法，兼具低复杂度与次线性收敛保证。

1. 核心思路：将合作式MEC任务卸载建模为带非线性约束的凸优化问题并用分布式梯度投影求解

作者将多边缘服务器与云中心的协作卸载过程抽象为一个带等式、不等式及边界约束的凸优化问题。令边缘服务器集合为，云中心编号，邻居集合。定义：

• ：服务器本地处理的任务量
• （）：从卸载至邻居的任务量
• ：从卸载至云中心的任务量
• ：所有发往的任务向量（）
• ：云中心接收的总任务向量

设、分别为边缘服务器与云中心的处理成本，为传输成本，可涵盖时延、能耗或其加权和。约束包括：

• 资源/时延/能耗不等式约束：（可非线性）
• 服务请求等式约束：
• 变量范围：

优化问题统一写为：

此模型兼容已有工作特例（仅时延、仅能耗、加权目标等），且允许非线性约束，覆盖更广的实际场景（如带宽硬上限、能耗预算、端到端时延要求）。

2. 核心创新：引入梯度投影与虚拟队列的分布式算法，支持非线性约束且免中心节点

传统分布式解法（对偶分解、ADMM）需中心节点收集全局信息或直接求解复杂子问题，难以应对非线性约束。作者创新点如下：

1. 增广拉格朗日构造：引入随时间更新的辅助函数，融合目标函数、约束违反惩罚及二次正则项，使得梯度更新可局部计算。
2. 梯度投影替代集中优化：将全局最小化替换为，其中。利用投影的可分解性，各服务器仅需邻居与云的局部梯度信息即可更新自身决策（式18-19）。
3. 双变量虚拟队列更新：对偶变量（不等式约束）采用虚拟队列法（式20），（等式约束）采用经典对偶次梯度更新（式21），均可在本地完成。
4. 免中心节点：整个迭代过程中无需求解全局优化或集中收集全部，通信仅在邻居与云间进行，避免单点瓶颈与隐私泄露。
5. 收敛性保证：在目标函数 -光滑、约束凸且 -Lipschitz 连续、Slater条件成立等假设下，证明运行平均解以速率满足约束并使目标值逼近最优（定理1、2）。

3. 实验验证：合作卸载显著降低时延，算法收敛快且计算复杂度优于分布式ADMM

作者在两种场景下验证：

线性计算能力约束

网络拓扑：6个互连边缘服务器+云中心（图2），任务到达率，服务能力，单位工作量比特。Fig. 2. Connected graph of a cooperative edge computing network with cloud-edge cooperation and edge-edge cooperation.
负载均衡效果：图3显示，合作策略有效均衡各服务器负载；图4展示时延在各服务器间趋于一致。Fig. 3. Workload of each edge server with and without cooperation.Fig. 4. Latency of each edge server with cooperation.
抗负载冲击：图5表明，随任务到达率提升，平均时延增长更缓慢，且服务器数量越多减缓效果越明显。Fig. 5. Average latency with different workload arrival rates.
算法对比：图6显示在6~10个服务器规模下，所提算法与分布式ADMM均优于FCA，且在时延降低方面相当或更优。Fig. 6. Comparison between different algorithms on average latency.
收敛性：图7显示数百次迭代后目标误差趋于稳定，服务器数量少时收敛更快；图8-9验证约束满足情况。Fig. 7. Convergence performance of Algorithm 1 with different number of edge servers.Fig. 8. Value of each computing capacity constrained function .Fig. 9. Sum of proportions of workload offloaded from each edge server.

非线性能耗约束

加入形如的非线性约束，比较所提算法、分布式ADMM与集中式对偶次梯度法：

图10显示，三种方法均降低平均时延，集中法立即收敛，所提算法与ADMM在 <50 次迭代内接近最优，且所提算法更接近最优值。Fig. 10. Average latency of different algorithms under nonlinear energy constraints.
计算时间对比（表III）：达到相同收敛阈值，所提算法耗时显著低于分布式ADMM，例如在时分别为 49.6s 与 279.0s，验证了其低复杂度优势。

TABLE III COMPARISON OF RUNNING TIME WITH DIFFERENT CONVERGENCE THRESHOLDS

Convergence threshold ε	Running time of our proposed algorithm (s)	Running time of distributed ADMM (s)
ε = 0.1	3.0106	6.7473
ε = 0.05	3.3847	23.4564
ε = 0.01	7.8211	28.4415
ε = 0.005	15.6954	118.1665
ε = 0.001	23.6734	221.4950
ε = 0.0005	32.4260	244.6814
ε = 0.0001	49.6004	278.9744

4. 总结与展望

本文贡献可概括为：

• 建模通用化：统一描述云边、边边协作及多种性能指标与非线性约束；
• 算法分布式与低复杂度：基于梯度投影与虚拟队列，无需中心节点，计算与通信开销显著低于ADMM类方法；
• 理论保证：次线性收敛到可行最优解；
• 实验充分：线性与非线性约束场景均验证性能优势。

局限性：

• 参数选取依赖 Lipschitz 常数与对偶变量的界，实际中需估计或自适应调整；
• 当前模型假设任务可分割且传输/计算成本函数已知，未考虑动态信道或任务随机到达的在线情形。

未来方向：

• 结合强化学习实现参数自适应；
• 拓展至在线分布式优化应对任务流不确定性；
• 探索跨域合作（移动设备–边缘–云）统一建模；
• 硬件原型验证与真实网络部署评估。