无人机使能的边缘计算优化问题

07-17 1801阅读

Joint Deployment and Task Scheduling Optimization for Large-Scale Mobile Users in Multi-UAV-Enabled Mobile Edge Computing论文阅读笔记

Background
Contributions
System Model and Problem Formulation
- Local Execution Model
- MEC Execution Model
- UAV Hover Model
- Proposed Approach
- - Motivation
  - ToDeTas
  - Experimental Study
  - - Settings
    - Effectiveness of Two-Layer Optimization
    - Effectiveness of Upper-Layer Optimization
    - Effectiveness of Lower-Layer Optimization
    - Effectiveness of Our Multi-UAV-Enabled MEC System
    - mind
      Background
      
      在移动边缘计算中，用户常常将会产生大量对计算能力和时延要求高的任务，这些任务通过卸载到边缘服务器上，能够迅速完成计算从而满足用户QoS。对于普通的MEC服务器来说，它们的位置总是固定的，无法根据移动用户的需要进行灵活改变，这限制了MEC的能力。近年来，无人机在通信领受到了广泛的关注。将无人机作为可移动的边缘服务器，不仅能够提供更好的通信链路(LoS)，而且能够灵活进行部署，从而缩短通信的距离。所以，本文讨论了多个无人机使能的MEC系统，在这个系统中，多个无人机被部署服务大规模的移动用户。无人机作为可移动边缘服务器，提供着任务卸载的服务，那么本文将着重探讨联合无人机部署和任务调用优化问题。
      
      本文的创新点有以下几个：
      1. 考虑多个UAV使能的MEC系统，多个无人机用于服务大规模的移动用户。
      2. 联合优化无人机部署和任务调度问题。
      3. 提出两层架构算法，算法简化了决策变量空间，通过计算推导保证了计算时间复杂度和运行时间，适用于大规模的移动用户。
      Contributions
      
      本文的贡献为以下五点：
      - 在大规模移动用户场景中构建了多无人机使能的移动边缘计算系统，无人机充当MEC服务器。
      - 提出两层优化方法ToDeTaS，用于解决无人机部署和任务调度联合优化问题，最小化系统的能量消耗。优化四个方面：无人机的部署数量、无人机的部署位置、卸载决策变量、资源分配变量。
      - 在算法的上层，使用带有消除算子( elimination operator)的差分进化(differential evolution, DE)算法来优化UAV部署问题。将UAV的位置编码进一个个体(individual)中，整个UAV的部署就是种群(population)。为了最小化系统的能量消耗，首先确定UAV的最大数量，接着逐渐减小消除算子的数量如果所有的任务都可以完成。UAV的数量根据消除算子自适应调整，UAV的部署位置根据DE算法进行优化。
      - 确定了UAV的部署后，那么下层的算法主要解决任务调度的问题。通过分析该问题能够转化为一个0-1整数规划问题。为了减少大规模0-1整数规划问题的计算时间，本文提出一种贪心算法来求得近似解。
      - 扩展实验从移动用户数100增加至1000，实验结果有效证明了提出ToDeTaS的有效性和多UAV-enabled系统的有效性。
        System Model and Problem Formulation
        
        系统模型如上图所示，共有M个移动用户，N个无人机，每个无人机能够服务通信范围内的用户。假设每个用户产生一个待执行的任务U，任务U=(C,D)，其中C为计算所需CPU频率，D为用户输入的数据量。系统中移动用户的数量M、移动用户的位置(x,y,0)、任务的CPU频率C、任务的数据量D都是已知的，而无人机数量N、无人机位置(X,Y,H)是未知的。其中高度H是固定已知的。
        由于联合优化问题的目标是最小化能量消耗，所以需要考虑无人机在计算执行、悬停情况下的能耗。将系统分为三个模型：（1）本地执行（2）MEC 执行（3）悬停
        
        Local Execution Model
        
        本地执行，时间为
        
        能量消耗为
        
        
        MEC Execution Model
        
        若是卸载到无人机上，任务首先得从移动用户传输到UAV上，然后在UAV上进行计算。定义 a i , k a_{i,k} ai,k为卸载决策，即移动用户i的任务是否卸载到UAV k上（k=0表示本地执行）。若 a i , k = 1 a_{i,k}=1 ai,k=1，则移动用户i的任务卸载到UAV k上，否则不然。定义 f i , k f_{i,k} fi,k为资源分配决策，即UAV k分配给用户i的任务的CPU频率。
        首先，用户需要在UAV的通信范围之内：
        其次，两个UAV之间的距离不能过近，否则会产生冲突：
        再者，每个UAV的资源是有限的，所以这里假设UAV最多能够执行 n m a x n_{max} nmax个任务【疑问：资源的分配通过任务执行数来界定有一定偏颇，若任务种类相似可以这样定义，若任务种类不相似，任务大小的方差太大，对于资源的分配利用并非高效的】
        MEC上执行时间分为两部分：卸载传输时间和卸载计算时间
        
        上式为传输速率，下式为总的执行时间
        
        MEC上的能量消耗为
        
        
        UAV Hover Model
        
        悬停的时间为T，悬停的能耗为
        
        
        对于整个系统，优化目标为最小化能耗，那么优化问题建模为
        
        优化目标：根据决策变量a得到计算卸载的总能耗，无人机悬停也需要能耗。
        C1: 通信范围约束，移动用户i不能超出无人机j(k)的服务范围
        C2: 无人机通信干扰约束，无人机之间需要保持最小冲突距离
        C3: 资源分配约束，无人机可计算任务的数量有限
        C4: 卸载决策约束，对于移动用户i产生的任务，只能卸载到一个无人机上(二进制卸载）
        C5、C6: 联合资源分配与任务卸载约束，可卸载才分配资源，否则不分配
        C7、C8: 时间约束，任务必须在无人机悬停时间内计算完毕
        
        Proposed Approach
        
        Motivation
        
        分析可知，该问题是一个非凸的非线性优化问题，考虑使用启发式搜索算法——进化算法求解。
        通过分析可知：
        （1）需要进行优化的变量有2(N+M)+1个
        UAV的数量（1个）、UAV的位置信息（2N)个、卸载决策变量（M个）、资源分配决策变量（M个）
        而对于大规模的移动用户场景来说，这是一个相当大的优化决策变量数量。
        （2）优化变量的类型不同
        离散变量：UAV的数量、卸载决策变量
        连续变量：UAV的位置信息、资源分配决策变量
        （3）UAV部署和任务调度是耦合的优化问题，确定了UAV的部署能够通过任务调度评价部署的好坏；而确定了任务调度能够反馈UAV向能耗更少的方向部署。
        
        因此，本文提出了ToDeTaS算法，将优化问题进行解耦，分为两层，进行交替优化。上层负责优化UAV的部署，下层负责优化任务调度。在上层中，通过编码方式将优化变量转化为2N个；在下层中，通过严密计算能够求出最优资源分配决策变量，从而使得优化变量只剩下卸载决策变量。所以，在上层中，只有连续变量；在下层中，只有离散变量，不存在混合变量。
        
        ToDeTas
        
        算法的整体流程如下：
        
        在上层中，UAV的部署问题是一个可变长度的优化问题，在进化算法中引入一种新的编码机制，使得每个individual都有固定长度（2维，位置的x坐标和y坐标）
        算法2，3，4用于优化UAV的部署：
        上层优化中，通过证明分析可知，在满足所有任务执行完成与时延约束的条件下，UAV的数量越少越好。
        在下层优化中，由于前面已经计算出UAV的部署，那么下层的优化问题可以表述为：
        根据约束C7、C8可知：
        而总的优化目标要尽可能减少能耗，所以资源分配决策的最优解可以求出：
        那么优化子问题变成了：
        所以下层的优化变量只有卸载决策变量，该问题退化为一个0-1整数规划问题。常见的求解该类问题的方法有 branch-and-bound algorithm，但是当计算规模增大时是十分耗时的。因此下层采用了贪心算法求解次优解。
        任务分为三种：
        （1）只能在本地执行的；
        （2）只能卸载到UAV的；
        （3）既可以在本地又可以在UAV上执行的。
        对三类任务划分优先级：第一类优先级最高，因为本地耗能少；第二类优先级次之，因为有助于尽可能多完成任务，第三类最后。
        算法5 优化任务调度：
        
        Experimental Study
        
        Settings
        
        Effectiveness of Two-Layer Optimization
        
        对比算法：
        DE-VND 一种单层优化算法（对原文方法稍作修改，设置相同的参数）
        ToDE-VND DE-VND 的两层版本，任务调度层与ToDeTaS相同
        
        
        Effectiveness of Upper-Layer Optimization
        
        对比算法：
        ToDE-VND （下层与ToDeTaS相同）
        ToDeTaS
        
        Effectiveness of Lower-Layer Optimization
        
        对比算法：
        ToDeTaS-BB （上层与ToDeTaS相同，下层采用 branch-and-bound algorithm）
        ToDeTaS
        
        Effectiveness of Our Multi-UAV-Enabled MEC System
        
        对比算法：
        ToDeTaS-L （只能本地执行）
        ToDeTaS-M （只能UAV执行）
        ToDeTaS
        ToDeTaS-M的平均任务完成数量与ToDeTaS相近，查看所需的UAV数量
        
        图中可知ToDeTaS用的更少。
        
        mind
        
        虽然优化问题的形式为单目标优化，但是给人感觉像是多目标优化（UAV数量最少、任务完成率最高、能耗最少）
        问题建模非时隙性，作者认为，对于动态变化的环境需要重新优化，感觉不太智能
        ——————————————————————————————————————————————————————————————
        references:
        [1]Y. Wang, Z. -Y. Ru, K. Wang and P. -Q. Huang, “Joint Deployment and Task Scheduling Optimization for Large-Scale Mobile Users in Multi-UAV-Enabled Mobile Edge Computing,” in IEEE Transactions on Cybernetics, vol. 50, no. 9, pp. 3984-3997, Sept. 2020, doi: 10.1109/TCYB.2019.2935466.