无人机辅助的服务缓存边缘计算最优计算卸载决策与资源分配

田贤忠,闵 旭,周 璐

(浙江工业大学 计算机科学与技术学院,杭州 310000)

1 引 言

移动边缘计算(MEC)是5G技术的核心技术之一,它通过在接入网(如AP、基站等)的边缘部署服务器,使其更靠近物联网设备[1,2].因此,可以有效减少任务的传输时延,以及降低了设备的能耗.在MEC系统中,边缘服务器的部署会对系统性能带来很大影响.目前,大量研究采用的是静态边缘服务器进行部署.静态边缘服务器的部署,一方面,由于服务器部署的静态性,进而服务的覆盖范围是有限的,导致在服务范围以外的区域不支持任务的卸载;另一方面,如果增加边缘服务器的部署,即密集地部署边缘服务器,则会增加成本,不切实际.因此,以无人机辅助的动态MEC服务器部署方案被纳入考虑[3,4].

无人机辅助的MEC服务器部署方案通过把边缘服务器搭载在无人机上,可以根据物联网设备以及各设备上计算任务的分布情况实现边缘服务器的动态部署.目前,大多数研究都是针对固定高度的无人机位置,换句话说,边缘服务器的部署只考虑水平位置,而忽略了高度的影响.这会产生其他问题,一方面,无人机的高度会影响边缘服务器与物联网设备的距离,进而影响边缘计算系统的传输延迟和能耗[5];另一方面,考虑到回传时无人机的波束宽度影响[6],无人机的高度还会影响到其覆盖范围.在高度较小时,其覆盖半径主要受波束宽度约束,与高度成正比;在高度较大时,在波束宽度内的节点也可能超出最大传输距离,此时的覆盖半径主要由传输功率决定.针对这一问题,本文考虑无人机的三维空间位置的部署,将其与覆盖范围和传输能耗相关联,探索使系统能耗最低的部署方案.

在边缘计算系统中,服务缓存的概念早已被提出.服务部署是在边缘服务器中配置相关应用的数据库,使其需要这些服务的计算任务,能够在边缘节点上进行卸载.针对无人机上的服务缓存问题,物联网节点上的任务并不是可以任意地卸载到无人机上进行计算.也就是说,只有缓存了相应的服务框架,对应的节点任务才可以进行卸载.无人机的位置部署与服务缓存方案形成两个相互耦合的问题.针对某一无人机而言,其位置决定了可卸载的节点空间,而不同的服务缓存又影响着无人机的最佳部署.由于无人机上边缘服务器的存储资源有限,如何结合无人机的部署位置,合理地在边缘服务器上缓存服务也是一个值得研究的问题.

针对以上问题,本文研究了无人机的3D部署、服务缓存、计算卸载以及资源分配等因素对边缘计算系统性能的影响,提出一种利用无人机辅助的服务缓存边缘计算最优计算卸载决策和资源分配策略.此策略利用优化无人机的3D位置以及边缘服务器中服务合理部署,在满足任务时延约束的情况下通过最优计算卸载决策和资源分配达到最小化能量消耗的目的.本文的主要贡献如下:1)提出了一种无人机辅助和服务缓存场景下,以最小化能量消耗的目标的无人机3D部署、服务缓存、计算卸载以及资源分配方案;2)建立无人机辅助服务缓存的最小化能量消耗的优化模型,并采用遗传算法双层优化方法求解,上层将无人机3D位置和服务缓存方案放入基因编码,下层先利用贪心的思想确定资源分配,再将问题转化为整数线性规划问题进行求解.3)通过仿真实验评估了本文提出的方法对所求解问题的有效性和优越性.仿真结果表明,本文提出的算法可以实现时延、服务缓存、计算资源限制下能耗最低的优化部署.

本文的其余部分组织如下:第2部分为相关工作;第3部分介绍系统模型;第4部分对问题建模;第5部分描述解决方案;第6部分显示仿真实验结果;第7部分是结论.

2 相关工作

对无人机辅助的边缘计算的研究可分为两类:单无人机和多无人机.单无人机方面,ZHAN C等人根据物联网设备的任务和能源预算约束,研究了计算卸载和资源分配以及无人机轨迹的联合设计,以最大程度地降低无人机的能耗和完成时间[7].ZHANG T等人提出了一种新的优化问题公式,旨在通过优化位分配,时隙调度,功率分配以及无人机轨迹设计来最大程度地减少总能耗[8].WAN S等人提出了一种基于李雅普诺夫优化的在线边缘处理调度算法[9].在低数据速率的情况下,它倾向于降低边缘处理器的频率以节省能源.在高数据速率的情况下,它将智能地分配带宽以进行边缘数据卸载.YU Z等人通过共同优化无人机位置,通信和计算资源分配以及任务拆分决策来最小化所有物联网设备的服务延迟和无人机能耗的加权总和[10].而LI M等人则通过共同优化无人机轨迹,用户发射功率和计算负载分配来最大化无人机能源效率[11].这些工作都是从单个无人机进行考虑,并且轨迹设计时默认为固定高度,只进行水平位置的变化.在多无人机方面.YANG L等人为了平衡无人机的负载,提出了基于差分进化的多无人机部署机制,将问题建模为广义分配问题,然后通过近似最优解解决[12].ZHANG J等人在多无人机辅助的MEC系统中提出了计算效率最大化的问题,其中考虑了计算位和能耗.基于部分计算卸载模式,联合优化了用户关联,中央处理器周期频率,功率和频谱资源的分配以及无人机的轨迹调度[13].多无人机方向的工作较少,在部署方案中仍未考虑高度的影响,并且,隐含假设均为无人机可处理各种类型的任务.

边缘节点缓存服务是减轻背景网络和中心云负担的有效途径.BORST S等人提出了基于流行度的内容分发网络分布式缓存算法[14].ZHANG S等人提出了一种以用户为中心的边缘缓存机制,其中每个用户由多个边缘服务器协同服务,以优化服务延迟[15].YANG P等人设计了位置感知边缘缓存方案,通过预测内容的流行程度来最大化局部命中率[16].和以往工作不同的是,本文将服务缓存应用于无人机辅助的MEC场景中,这使服务缓存策略更为复杂,是一个具有挑战性的问题.

前面的工作很少考虑无人机辅助的服务缓存边缘计算系统的场景.本文将结合5G网络中的服务部署,考虑波束宽度带来的高度和覆盖范围影响,联合优化无人机3D部署、服务器服务缓存、卸载策略和资源分配策略,实现系统能耗最低的目标.

3 系统模型

图1 多无人机辅助的MEC系统Fig.1 Multi-UAV-enabled MEC system

用αk,n表示节点dk是否连接到无人机un,即ak,n∈{0,1},设定每个物联网节点只能连接到一个无人机,则有:

(1)

用βm,n表示第m种服务是否部署在无人机un,即βk,n∈{0,1},A={a1,a2,…,aM}表示每种服务所需容量大小.由于无人机上服务部署有容量限制,则有:

(2)

其中C为无人机上服务器服务缓存的容量限制.

每一个物联网节点dk都有一个要执行的计算密集型任务,这些任务被建模为四元组Wk=(Ck,Fk,tk,λk),4个参数依次为任务大小、处理一位任务数据所需CPU周期数、处理该任务的最大可容忍时延、任务的服务类型.该任务有两种操作方式:1)本地计算;2)卸载到缓存了服务λk的无人机上计算.

A.本地计算模型

当任务Wk采用本地计算时,计算时延可表示为:

(3)

其中,fk,0表示节点dk的本地计算资源.

相应的,用于任务Wk的计算能耗可表示为[17]:

Ek,0=η1(fk,0)v-1CkFk,∀k=1,2,…,K

(4)

其中,η1为有效电容开关,v为正常数.

B.MEC计算模型

当任务Wk采用计算卸载方式时,任务首先传输到无人机上,并在其服务器上进行计算,计算结束后,结果再返回给物联网节点.假设每个无人机配备一个定向天线,用θ表示天线的半功率波束宽度.下行链路时,相对于主瓣增益,主瓣外可忽略不计.无人机的覆盖半径Rn与无人机高度hn、天线半功率波束宽度相关[6],有:

(5)

对于节点dk,与无人机un的水平距离可表示为:

∀k=1,2,…,K,n=1,2,…,N

(6)

显然,如果节点dk要将任务卸载至无人机un,节点dk必须在无人机un的覆盖范围内,该约束可表示为:

C3:αk,nLk,n≤Rn,∀k=1,2,…,K,n=1,2,…,N

(7)

任务卸载还受服务缓存的影响,有以下约束:

C4:αk,n≤βλk,n,∀k=1,2,…,K,n=1,2,…,N

(8)

只有当βλk,n=1,即无人机un缓存了服务λk,节点dk才能将任务卸载,即αk,n才能取1.

节点dk与无人机un之间上行链路传输速率由下式给出[18]:

∀k=1,2,…,K,n=1,2,…,N

(9)

其中B为信道带宽,P为每个节点的发射功率,β0为参考距离处的信道功率增益,G0为正常数,N0为噪声功率谱密度.

在此卸载场景中,由于下行结果数据相对较少,本文忽略回传时间.节点dk卸载到无人机un所需总时延可表示为:

(10)

其中,fk,n表示无人机un分配给节点dk的计算资源.考虑节点的传输能耗和服务器的计算能耗.节点的传输能耗等于节点的发射功率乘以传输时间,故有:

(11)

对应的服务器计算能耗,根据文献[19]为:

(12)

4 问题建模

如图1所示的场景,本文需要解决如下几个问题:

在满足任务时延要求得前提下,物联网设备中的任务是在本地计算还是上传给无人机上的边缘服务器计算?

在计算总资源确定的条件下,如何给各物联网设备分配合适的计算资源?

如何部署无人机的3D位置,使得整个边缘计算系统性能最佳?

在服务器存储资源有限的约束下,如何合理部署服务缓存?

本文以系统的能耗为优化目标,包括本地计算能耗和MEC计算模型下相关能耗.通过需要联合优化无人机的3D部署、服务缓存、任务分配、计算资源分配,以最小化系统能耗.该问题可表述为:

(13)

C3:αk,nLk,n≤Rn,∀k=1,2,…,K,n=1,2,…,N

C4:αk,n≤βλk,n,∀k=1,2,…,K,n=1,2,…,N

C5:αk,0Tk,0≤tk,∀k=1,2,…,K

C6:αk,nTk,n≤tk,∀k=1,2,…,K,n=1,2,…,N

其中,参数μ用于调整服务器计算能耗所占比重,由于服务器的能量补充相对容易,可考虑降低服务器能耗的重要程度.约束C5、C6为每个任务的时延限制.C7是指服务器的最大计算资源约束,卸载到同一架无人机服务器上的节点所分配的计算资源之和不能超过fmax.

5 解决方案

显然,在第4节中提出的问题是NP-hard的,并且该问题是非凸非线性的.传统的优化方法不好解决,基于种群的启发式搜索算法具有很好解决这一问题的潜力.将目标变量编码到种群的基因序列中是一种自然的想法,然而,本文需要优化无人机和服务的部署、卸载决策、资源分配,决策变量的数量随着无人机个数和节点个数的增加而增加.在本文中考虑了大量的物联网节点,这对遗传算法而言是一个大规模最佳化问题[20].

为此,本文提出了一种基于遗传算法框架的双层优化算法(Optimization algorithm of placement of UAV and service based on genetic algorithm,OAP)来解决这个问题.首先,仅将无人机3D位置、服务部署方案编码于染色体中;其次,根据每一确定的染色体,即确定的无人机3D位置和服务部署方案,在内层利用线性规划方法确定物联网节点的卸载策略和无人机的资源分配;然后在外层进行染色体的选择、交叉和变异等种群操作,确定无人机3D位置、服务部署方案.

5.1 染色体编码

本文采用二进制编码对变量lun和βm,n进行编码,每一个基因片段对应无人机的3D位置部署和无人机服务器上的服务部署.如图2所示,共有N个基因片段,与无人机数量相对应.在每一个片段中,前3个变量为无人机的3D坐标,转换为二进制编码所占位数与精度相关,后续M位为服务部署,分别代表对应服务是否部署在无人机服务器上.假定位置部署每个参数占用length个位,而βm,n∈{0,1},因此,每一条染色体长度为N×(M+3length).

图2 染色体编码Fig.2 Chromosome coding

5.2 卸载策略与资源分配求解

由于目标函数是最小化问题,本文将优化目标能耗的倒数作为适应度函数.在目标函数中,无人机的3D位置部署和服务器的服务部署已由染色体确定,因此,可将优化问题转化为:

(14)

通过观察目标函数(14),可以发现,无论是本地计算还是卸载到无人机,所需的计算能耗与分配的计算资源成正比.因此,在卸载策略确定的情况下,可以在满足时延约束的条件下,尽可能少地分配计算资源.若节点dk进行本地计算(即αk,0=1),由公式(3)和约束C5可以得到:

(15)

若节点dk将任务卸载到无人机un进行计算(即αk,n=1),由公式(10)和约束C6可以得到:

(16)

为了使目标能耗最小,可以在不等式(14)、(15)中取等号,从而可求得最优的资源分配策略.

在此基础上,可以将优化问题转化为:

s.t.C1,C3,C4,C7

(17)

易知该问题为线性规划问题,本文采用分支定界法进行求解.为了应对出现少数节点没有可行计算方案的情况,本文将其设置为按照本地最大计算资源进行计算,最终计算能耗以其十倍作为惩罚并计入目标值.

5.3 无人机位置与服务部署求解

5.2中求得的是针对某一确定的染色体的最优计算卸载与资源分配策略,即在无人机位置与服务部署确定的情况下的最优计算卸载与资源分配策略.进一步,通过染色体的选择、交叉和变异等操作,实现最优无人机位置以及缓存服务部署.在执行选择操作时,采用适应度比例算法计算选择概率.在该方法中,各个个体被选择的概率和其适应度值成比例.选择方法采用基本的轮盘赌选择策略.在此方法中先按个体的选择概率产生一个轮盘,轮盘每个区的角度与个体的选择概率成比例,然后产生一个随机数,它落入轮盘的哪个区域就选择相应的个体交叉.染色体的交叉仅发生的等位基因上.例如:片段1只能和片段1进行交换.交叉概率由参数pc控制.突变是指染色体某位发生0和1的翻转,突变概率由参数pm控制.算法流程如表1所示.

表1 算法流程Table 1 Algorithm steps

通过交叉和变异产生的新个体可能不满足服务器服务缓存容量的要求,因此,在选择操作时,根据公式(2)确定其是否满足约束并去除不符合约束的个体.然后再进行选择操作.

6 性能分析

在这一部分,本文使用MATLAB r2020a进行仿真实验,以验证所提出算法的有效性.

6.1 实验设置

在表2中给出了无人机辅助MEC系统的参数设置[21].

表2 参数设置Table 2 Parameter settings

假定系统在一定宽度的正方形区域运行工作.为了比较不同算法的性能,本文从不同角度对3种算法进行了对比:

1)其他条件一定时,对比节点数不同时各算法的性能.

2)其他条件一定时,对比无人机数不同时各算法的性能.

3)改变无人机的最大计算资源,对比系统性能.

4)无人机平均缓存服务数对性能的影响.

为了从能耗的角度评价所提出算法OAP的性能,设计了两种对比方案.

OAP-H:考虑到无人机高度的影响,在算法OAP-H中,本文固定无人机高度为100m[12].相对于OAP的3D部署来说,OAP-H只用考虑无人机的平面坐标.

OAP-C:考虑到3D空间自由探索的复杂性,在算法OAP-C中,先用K均值聚类算法对场景中节点进行聚类,确定无人机的平面坐标.在高度这一因素上,与原算法保持一致,在[50,200]的范围内自由可变.

6.2 结果分析

首先考虑节点数对性能的影响.设定场景宽度为500m,N=5,平均服务缓存数为4,fmax在不同K值下均充足,μ=1,K从100到500.从图3可以看到,3种算法的能耗都随着K值的增加不断升高,而算法OAP始终优于另外两种算法.随着K的增大,系统本身的能耗是增加的趋势;由于覆盖半径和服务缓存的限制,会有更多的节点不能被无人机所服务,也就有更多的任务进行本地计算,而OAP算法能更优地对节点进行覆盖提供服务,使目标值最低.

图3 节点数的影响Fig.3 Impact of the number of nodes

无人机数量对性能的影响.设定场景宽度为500m,K=300,平均服务缓存数为4,fmax在不同N值下均充足,μ=1,N从1到10.从图4可以看到,3种算法的能耗都随着N值的增加不断降低,而算法OAP始终优于另外两种算法.可以看到,在无人机数1-4时,OAP和OAP-C能耗下降较快,在5-10时两者能量消耗已趋于平稳,这是因为随着无人机数量的增加到5及以上时,无人机对场景中节点的覆盖比较全面,再增加无人机不能再提升其覆盖程度.而算法OAP-H在无人机数到10及以上才实现对区域内节点的基本覆盖.在无人机数较小时,算法OAP展现除了明显的优势.

图4 无人机数的影响Fig.4 Impact of the number of UAV

服务器计算资源的影响.设定场景宽度为500m,K=300,N=5,平均服务缓存数为4,μ=1,fmax从0到18GHz.从图5可以看到,随着计算资源的增加,系统能耗不断减少.在0-10GHz,无人机受计算资源限制,不能为覆盖区域内的节点提供充足的服务,更多的节点选择本地计算,导致能耗较大.当计算资源超出10GHz,资源较为充足,继续增加资源却没有服务更多的节点可服务,能耗逐渐平稳.值得注意的是,服务器计算资源为0时,即所有任务都在本地计算,总体能耗远高于有足够资源时的3种算法,也说明了算法的有效性.

图5 计算资源的影响Fig.5 Impact of computation resource

平均服务缓存数的影响.无人机的服务缓存与其能否为某一节点提供服务相关.设定区域宽度为500m,K=100,N=5,,fmax在不同情况下均充足,μ=1,平均服务缓存数从1到5,如图6所示.服务缓存数的增加,意味着在无人机覆盖区域内有更多类型的节点可以选择卸载,达到能耗降低的效果.特别是平均服务数为5时,这和服务种类数M相同,表明区域内的各服务类型节点均可选择卸载,能耗达到最低.此外,图6中仍然显示了算法OAP较其余两者更为优越.

图6 服务数的影响Fig.6 Impact of the number of service

7 总 结

边缘计算为计算密集型、时延敏感型任务提供了新的解决思路,而无人机技术解决了固定基站在复杂环境面临的困境.本文针对多无人机辅助的服务缓存MEC系统,以最小化能耗为目标,用遗传算法框架求解无人机的3D部署和服务器上的服务部署,用贪心的思想确定资源分配,用整数线性规划求解卸载策略.此外,在仿真实验中,设计了复杂程度更低、性能较优的OAP-C算法.最后,仿真结果验证了算法的有效性和优越性.在未来的研究中,我们将关注无人机辅助MEC场景中的时延优化、动态调整部署、无人机轨迹优化等相关内容.