多无人机辅助MEC环境中基于Wardrop路由博弈的计算卸载  

Computation Offloading with Wardrop Routing Game in Multi-UAV-aided MEC Environment

作　　者：汪昕隆 林兵 陈星[3,4] WANG Xinlong;LIN Bing;CHEN Xing(College of Physics and Energy,Fujian Normal University,Fuzhou 350117,China;School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China;Fujian Key Laboratory of Network Computing and Intelligent Information Processing(Fuzhou University),Fuzhou 350116,China;College of Computer and Data Science/College of Software,Fuzhou University,Fuzhou 350108,China)

机构地区：[1]福建师范大学物理与能源学院,福州350117 [2]北京大学信息科学技术学院,北京100871 [3]福建省网络计算与智能信息处理重点实验室(福州大学),福州350116 [4]福州大学计算机与大数据学院/软件学院,福州350108

出　　处：《计算机科学》2024年第3期309-316,共8页Computer Science

基　　金：国家自然科学基金(62072108);福建省高校产学合作项目(2022H6024);福建省社科规划项目(FJ2020C046)。

摘　　要：无人机(Unmanned Aerial Vehicles,UAVs)与多接入边缘计算(Multi-access Edge Computing,MEC)技术的结合突破了传统地面通信的局限性,已成为解决MEC中任务卸载问题的重要手段。由于单无人机可提供的计算资源和能量有限,为了应对日益扩大的网络规模,考虑了多无人机辅助MEC环境中的任务卸载问题。基于问题定义,任务卸载过程可以视为一个在平行链路上进行的、具有玩家特定延迟函数的Wardrop路由博弈,目的是得到均衡状态和最优状态下的卸载策略,并量化分析两者间的差距。由于均衡解难以计算,因此构造了一个新的势函数,将均衡问题转换成最小化势函数问题。同时使用Frank-Wolfe算法最终获得均衡和最优卸载策略。算法在每次迭代中将目标函数线性化,通过求解线性规划得到可行方向,进而沿此方向在可行域内作一维搜索。仿真实验表明,相比其他基准测试方法,基于平行链路Wardrop路由博弈的均衡卸载策略能够有效降低模型总成本,且与最优卸载策略下总成本的比值约为1。The combination of Unmanned aerial vehicles(UAVs)and multi-access edge computing(MEC)technology breaks the limitations of traditional terrestrial communications,which has become a significant approach to solve the tasks offloading pro-blem in MEC.Due to the limited computing resources and energy that a single UAV can provide,the tasks offloading problem in a multi-UAV-assisted MEC environment is considered to cope with the growing network scale.Based on the problem definition,to obtain the offloading strategies in the equilibrium and optimal states and analyze the gap between them quantitatively,the tasks offloading process can be viewed as a Wardrop routing game on parallel links with player-specific latency functions.Since the equilibrium solution is difficult to compute,a new potential function is introduced to convert the equilibrium problem into a minimization problem of potential function.Simultaneously,the Frank-Wolfe algorithm is used to obtain the equilibrium and the optimal offloading strategies finally.At each iteration of this algorithm,the objective function is linearized,and the feasible direction is thus obtained by solving the linear programming,along which a one-dimensional search is performed in the feasible domain.Simulation experiments verify that the equilibrium offloading strategy based on the Wardrop routing game on parallel links can effectively reduce the model’s total cost compared with other benchmark methods,and the ratio between the total costs caused by the equilibrium and optimal offloading strategies is about 1.

关 键 词：多接入边缘计算 任务卸载 无人机 Wardrop路由博弈 Frank-Wolfe算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]