刘伯阳，杨宁乐，马 杰,万奕尧，周继军

(1.西安邮电大学 通信与信息工程学院，陕西 西安 710121； 2.北京邮电大学 信息安全中心，北京 100876)

移动边缘计算(Mobile Edge Computing,MEC)是一项非常有前景的技术，能够在网络边缘为用户提供类似云计算的服务，从而将用户从繁重的计算工作中解放出来[1-2]。一般来说，MEC服务器的部署位置固定，服务器与用户之间通信链路通常以非视距为主[3-4]，其覆盖范围较小。无人机具有机动性高和部署灵活的特点，搭载在无人机上的MEC服务器与用户之间通常具备视距链路，因此，将MEC服务器部署在无人机上能够为地面用户提供灵活的广覆盖服务[5]。

近年来，无人机辅助的MEC系统受到了越来越多的关注。文献[6-7]考虑了无人机同时作为MEC服务器和中继节点为用户提供服务的场景，并研究了该场景下无人机与所有用户总能耗最小问题。文献[8]通过联合优化物联网设备的分组以及无人机的服务顺序使无人机的能耗最小化。在文献[6-8]的基础上，文献[9]进一步研究了多无人机协同场景，并对无人机的空间位置进行优化，使用户与无人机能耗最小。为了提高无人机辅助MEC系统的性能，文献[10]联合优化了用户分组、无人机运行轨迹以及用户传输功率以实现总卸载比特数最大化。在此基础上，文献[11]重点考虑了用户对时延敏感的场景，通过对无人机的飞行轨迹以及用户的相关运行参数联合优化，最小化用户任务完成时延。为了更有效地评估无人机辅助MEC系统的性能，文献[12]提出了计算能效的概念并将其定义为用户计算比特数与总体能耗的比值。

现有针对无人机辅助的MEC网络的研究主要集中在系统如何在计算资源、能耗以及时延约束条件下完成所有用户的计算任务等方面。然而，当用户数量很大或者用户任务计算数据量巨大时，考虑无人机能搭载的MEC服务器重量与体积限制，仅依靠无人机完成所有用户的计算任务是不现实的。特别是在物联网(Internet of Things,IoT) 场景中，MEC服务器服务区域内往往存在大量的接入设备，并且用户的位置较为分散，利用无人机为所有用户提供服务较为困难。因此，应该研究如何合理地优化无人机部署位置使其可以服务尽可能多的地面用户，即最大化无人机服务覆盖范围，尽可能扩大无人机辅助的MEC网络的服务范围。

针对以上问题，提出了一种无人机辅助的移动边缘计算无人机空间部署位置与资源分配优化算法，在满足网络计算资源约束与用户卸载功率约束下，最大化无人机服务的用户数并建立优化问题。首先将原始的非凸混合整型优化问题松弛为一个连续非凸优化问题，通过固定一些优化变量优化另外一些优化变量进行交替迭代求解。对于过程中建立的非凸子问题，利用连续凸近似[13]将其转化为凸问题进行求解。最后利用二分法将松弛后的二元整型优化变量进行恢复。

1 系统模型

如图1所示，考虑一个无人机辅助的MEC网络。该网络中，无人机搭载MEC服务器为K个位置固定的地面用户提供计算服务。令κ={1,2,…,K}表示用户的集合，其中每个用户都有任务等待计算。用户k(k∈κ)的计算任务可用数组(Ik,Ck,tk)表示，其中Ik表示用户k待计算任务数据量的大小，Ck表示用户k处理1 bit数据需要的中央处理器(Central Processing Unit,CPU)周期数，tk表示用户k任务完成期限。与文献[6]中采取相同的近似，假设所有用户任务的完成期限均等于无人机的悬停时间tk=T。

图1 系统模型

1.1 坐标与信道模型

采用三维笛卡尔坐标系，令wk=(xk,yk)表示用户k的水平坐标，所有的用户都固定在地面上，即其高度均为0。无人机以固定高度H飞行，其中H为保证无人机能够避开服务区域内所有障碍物的最低高度。适当的H可使无人机无需频繁调整高度以保证飞行安全，同时也能保证无人机与用户之间能以较低的传输功率通信。无人机的水平坐标为q=(xq,yq)。假设在无人机与用户之间具备视距链路(根据文献[14]中的实地测量，在服务区边长小于等于100 m的空旷环境中，无人机与用户之间具有视距链路的概率接近于1)。无人机与用户k之间的信道功率增益[15]可表示为

(1)

其中，β0表示在参考距离为1 m时的信道增益。

1.2 计算和任务卸载模型

采用部分卸载模型[3]，即假设用户的计算任务可以被分割为两部分，一部分由用户自身进行计算，另一部分通过无线链路卸载到无人机，由无人机上搭载的MEC服务器进行计算，计算完成后将计算结果返回用户。假设用户k的CPU时钟频率为fl,k，则用户在本地计算的比特数可以表示为

(2)

无人机为用户k提供服务是指无人机协助用户k在期限内完成其计算任务。令二元变量μk∈{0,1}表示无人机是否为用户k提供服务，μk=1表示无人机为用户k提供服务，否则μk=0。因此，无人机的覆盖范围可以由服务用户的数量衡量。为了避免干扰，用户与无人机之间采用频分多址(Frequency Division Multiple Access，FDMA)进行通信。令αk∈[0,1]表示分配给用户k的频带宽度占整个带宽的比例，用户k卸载到无人机上的任务比特数可以表示为

(3)

其中：B为总体可用带宽；pk表示用户k向无人机卸载任务数据时的传输功率。无人机接收到用户卸载的任务后对任务数据进行计算处理得到输出结果，将输出结果回传给相应的用户。考虑到计算结果所占比特数往往较小(如人脸识别，只需返回判断结果是或者否)，因此，忽略计算结果回传带来的传输时延。

2 覆盖范围最大化资源分配方案

通过联合优化用户CPU工作频率与传输功率、用户带宽分配、用户分组、无人机的CPU时钟频率及部署位置最大化MEC服务器覆盖范围。令α=[αk,k∈κ]，f=[fe,k,k∈κ]，p=[pk,k∈κ]和μ=[μk,k∈κ]分别表示用户带宽分配、无人机CPU时钟频率分配、传输功率及用户分组向量。无人机覆盖范围最大化问题如下表示。

s.t.C1ll,k+lo,k≥μkIk

C4μk∈{0,1}

C60≤fu,k,fl,k≤fl,max,0≤pk≤pmax

其中，fl,max、pmax和fu,max分别表示用户最大CPU时钟频率、用户最大传输功率以及无人机搭载的MEC服务器的最大CPU时钟频率。约束条件C1保证所有用户的计算任务都能在规定时间内完成，C2保证用户卸载到无人机的数据量能在规定时间T内被无人机计算完毕，C3表示分配给每个用户的频谱资源之和不能超过该系统中可用的频谱资源总量，C4表示无人机是否为用户k提供服务，C5-C6约束了无人机的CPU计算频率与用户的传输功率与CPU时钟频率。

优化问题P1中存在二元优化变量所组成的向量μ，导致问题P1是一个难以求解的非凸混合整型优化问题。为了能有效地改善这个问题，首先将二元整型变量μk松弛为一个连续优化变量，且有0≤μk≤1。再对问题P1进行求解，最后恢复原始二元优化变量。然而，约束条件中存在较多的变量耦合，即使将二元优化变量松弛为一个连续优化变量，上述问题仍为一个非凸问题。为了改善这个问题，提出了一个两阶段交替迭代优化算法。具体而言，首先，固定无人机的部署坐标q，优化用户与无人机的CPU时钟频率向量f、用户分组向量μ、用户传输功率向量p以及系统带宽分配向量α；其次，基于第一步优化得到的优化结果，对无人机位置进行优化。

固定无人机的部署位置后，相应的优化问题表示为

(4)

s.t.C1—C3,C5—C6，0≤μk≤1

为了处理非凸约束条件C1和C2，首先引入辅助变量zk=αkpk,k∈κ，可得

(5)

需要注意的是，此时无人机的部署位置是固定的，因此根据式(1)可得，无人机与各用户之间的信道功率增益也是一个确定的值，则是一个凹函数。等式右边是左侧的透视函数，为凹函数。故约束条件C1和C2不等号左边均为凹函数，可以分别表示为

(6)

(7)

(8)

(9)

其中，αk[n]和zk[n]表示连续凸近似算法中第n次迭代时的任意可行点。通过将式(7)的凸近似式(8)代入问题P1.1可得

其中：z=[zk]；ε是一个很小的正的常数，其作用是为了防止在优化过程中αk为0。ε很小，其对最优解的影响可以忽略不计。P1.1.1是一个凸问题，可利用凸优化工具箱对其求解。令Θ[n]=[αk[n],zk[n]]，表示带宽分配与辅助变量所组成的向量，第n次迭代得到的解为(f*,μ*,Θ*(Θ[n]))。连续凸近似算法原理如算法1所示。

算法1连续凸近似算法

步骤1初始化。选择原始问题的一个可行解，初始化步长因子r∈(0,1]，令k=0。

步骤4设置k+1→k，返回步骤2。

求解P1.1的具体步骤如算法2所示，步骤2的终止条件为(f*,μ*,Θ[n])收敛到问题P1.1的一个驻点。

算法2求解P1.1的连续凸近似算法

步骤1初始化。选择合适步长r[n]∈(0,1]，输入初始可行向量Θ[0]，令n=0。

步骤2若(f*,μ*,Θ[n])满足终止条件，则停止，输出最优解(f*,μ*,Θ*)=(f*,μ*,Θ[n])，否则转入下一步。

步骤3从P1.1.1中计算(f*,μ*,Θ*(Θ[n]))。

步骤4Θ[n+1]=Θ[n]+r[n][Θ*(Θ[n])-Θ[n]]。

步骤5令n+1→n，返回步骤2。

对于第二个子问题，需要基于第一步中得到的最优解(f*,μ*,Θ*)实现对无人机部署位置的优化，相应的子优化问题可以表示为

(10)

则P1.2第二个约束的一个凸近似可以表示为

(11)

等号右边是关于q的凸函数，同理，其在任意可行点处的一阶泰勒展开式均是其全局下界，可表示为

Ψ2,k[n]=2(q[n]-wk)T(q-q[n])+
‖q[n]-wk‖2

(12)

因此，基于式(10)和式(12)，得到了优化问题P1.2的一个凸近似，可以表示为

问题P1.2.1是一个凸问题，可以利用凸优化工具有效求解。步骤2中，求解子优化问题P1.2的具体步骤如算法3所示，步骤2中的终止条件为q[n]收敛到问题P1.2的一个驻点。

算法3求解P1.2的连续凸近似算法

步骤1初始化。选择合适步长r[n]∈(0,1]，输入初始可行点q[0]，令n=0。

步骤2若q[n]满足终止条件，则停止，输出最优解q*=q[n]，否则转入下一步。

步骤3从P1.2.1中计算q*(q[n])。

步骤4更新可行点q[n+1]。

q[n+1]=q[n]+r[n][q*(q[n])-q[n]]。

步骤5令n+1→n，返回步骤2。

综上，将原始非凸优化问题P1分解为两个子优化问题P1.1和P1.2进行交替迭代求解，对于每一个子优化问题，利用凸优化方法获得各自的最优解，求解原始优化问题P1的步骤总结在算法4中。

算法4求解P1的两阶段交替迭代优化算法

步骤1初始化。给定q[0]。

步骤2若P1目标函数值收敛，则结束。

步骤3利用算法1求解子问题P1.1，获得最优解(f*,μ*,Θ*)，否则转入步骤4。

步骤4基于步骤3中得到的最优解(f*,μ*,Θ*)，利用算法2获得问题P1.2最优解q*，返回步骤2。

算法5恢复出二元优化变量μ*的二分法

步骤3若P1有解且kup-klow≤1，则μ*[Idex(1:kmid)]=1，μ*[Idex(kmid+1:end)]=0，结束；否则进入步骤4。

步骤4令

步骤5基于步骤4中得到的μ,利用算法3求解P1，若P1有解，则klow=kmid；若P1无解，则kup=kmid。返回步骤3。

3 性能仿真及分析

针对提出的无人机辅助MEC覆盖范围最大化算法进行仿真和性能分析。详细仿真参数如表1所示。

表1 仿真参数

图2和图3描述了无人机辅助的MEC网络覆盖性能与用户输入数据量Ik,k∈(1,2,…,K)的关系。所有的用户均匀分布在一个半径为r0=15 m,圆心为(0,0)的圆上。在假设条件下，无人机与用户之间的信道功率增益与其之间的距离有关。从图2和图3中可以看出，在这种用户分布的场景下，无人机的最优部署位置为圆心(0,0)，符合预期设想。并且由图3可以看出，随着任务输入数据量的增加，服务的用户数降低(由9个降低到5个)，无人机机载边缘服务器的计算资源有限，在任务数据量增大时，无法为原有的所有用户设备提供服务，因此，只能降低服务用户数以保证服务用户的服务质量。

图2 Ik=2×104 bits情况下用户均匀分布时的覆盖性能

图3 Ik=2×104 bits情况下用户均匀分布时的覆盖性能

比较图4和图5可以看出，首先，当用户分为两个数目相同用户组，分布在两个不同的地理位置时，无人机的最优部署位置接近于两个用户组的中点。而当两个分组用户数目不同时，为了服务尽可能多的用户，无人机的最优部署位置将更靠近用户数多的那一边，并且随着用户分布的更密集，无人机服务的用户数将增加。

图4 用户均匀分布时的覆盖性能

图5 用户非均匀分布时的覆盖性能

图6对所提二分法恢复整型变量的正确性进行验证，其中横坐标表示用户的任务数据量，纵坐标为提供服务的用户数。由图6可以看出，所提算法可正确恢复,整数变量，算法有效。同时也可看出随着用户待计算任务量的增加，无人机MEC覆盖范围越来越小。

图6 用户非均匀分布时的覆盖性能

4 结语

针对目前无人机辅助边缘计算研究较少的服务覆盖范围问题，提出一种无人机辅助的移动边缘计算无人机部署位置与资源分配优化算法。利用连续凸近似的二阶段迭代算法与二分法优化无人机部署位置、计算资源以及用户发送与计算参数，无人机服务用户数。仿真结果表明，当用户分布均匀时，无人机的最优部署位于几何中心；当用户分布不均匀时，无人机的最优部署倾向于高密度区域。