1.一种公平感知任务调度和资源分配方法,其特征在于,本方法包括以下步骤:步骤一:无人机轨迹优化;步骤二:任务决策和位调度;步骤三:资源分配;本发明方法具体为:首先考虑了一个基于频分多址的无人机启用MEC网络,其中多个地面终端结点分别表示为:并且它们随机分布在地面上,记作:Wk=(xk,yk)T;定义整个导航时间为T,Q0和QF分别表示3D笛卡尔坐标系中的原点和终点;无人机在固定高度H的水平面飞行,在导航过程中为资源有限的GN(地面结点)提供数据计算和缓存服务,GN保持静止;其中T被划分为N个槽,每个槽的长度为τ=T/N(以秒为单位),记为q[n]=(x[n],y[n])T为无人机在第n个时隙的位置,Vmax为无人机的最大速度;由于τ很小,q[n+1]和q[n]之间的平均速度可以近似为瞬时速度||v[n]||,由下式给出无人机作为移动边缘计算服务器为物联网设备提供计算资源和数据缓存服务;其中||·||表示欧氏距离,v[n]不能超过其最大速度Vmax,||q[n+1]‑q[n]||≤τvmax;此外,无人机与第n个时隙内的第k个GN之间的距离可以写为第一要设定传输模型;假设无人机和第k个GN之间的无线信道由视线(LoS)链路主导;
将第k个GN到第n个时隙处的无人机的信道增益表示为hk[n],由下式给出:其中β0表示参考距离d0=1m处的信道增益;总带宽B在GN之间共享,分配给第k个GN的几率为bk[n],并且必须满足:因此,以每秒比特(bps)为单位的第k个GN的可实现速率可以写为:其中pk是第k个GN的发射功率,N0是无人机的噪声功率谱密度;
第二要设定任务执行模型,在飞行过程中,每个GN运行一个主循环应用程序,生成多个位,可以根据具体需要针对不同的操作(例如本地计算、计算或缓存的任务卸载)进行处理,其中假设GN没有将数据存储在其本地缓冲区中;由于GN的计算能力和能源供应有限,可以把这些比特卸载到无人机进行进一步处理,而不是在本地计算,以将GN从计算密集型或耗能工作负载中解放出来;分别将Sk和Sk[n]表示为第k个GN的总比特数及其在第n个时隙调度的比特数,满足 考虑到网络的公平性和稳定性,每个GN的每个时隙内的调度比特都有一个下限和一个上限,其中 表示要处理的最小生成比特,以确保GNS它们之间的公平性; 表示根据GNS之间共享的无人机的计算能力和缓存容量调度的最大合理工作负载,使支持无人机的MEC网络更加稳定;此外,为了保证成功卸载,无人机和第k个GN之间的信道容量的下限由下式给出为:
定义一个三元变量 决定第k个GN处调度比特,其中表示本地计算, 代表计算卸载, 表示缓存卸载;由于一次只能执行一个操作,因此必须满足以下约束此外,计算每个GN的总大小应满足:这样才能保证不同类型卸载服务之间的公平性;由于计算的能量消耗大于缓存的能量消耗,因此添加这个约束是用来避免无人机缓存所有的卸载位,其中 表示在UAV或第k个GN处执行计算的总位数;同时,如果执行缓存,则会分配缓冲区空间,总缓存位不能超过无人机的缓存容量,由下式给出其中C代表无人机的最大缓存容量,如果内容或任务被存储,它可以被另一个TD使用,而无需在之后额外传输,并为用户提供内容传输服务,以满足其频繁的请求;此外,缓存的使用还可以用来缓冲大量的数据或任务,直到无人机有足够的计算资源;由于无人机可以处理缓存的数据,因此在GN由于信道增益较差而低速率传输的情况下,不会浪费无人机的计算能力;因此,无人机可以部署缓存来保存其存储区域中的任务或内容,以降低响应延迟,并同时提高通信资源和计算能力的使用效率;
如果调度位在本地执行,则GN处对延迟的处理可以写为:其中θk表示第k个GN处的CPU计算强度;如果卸载给无人机,则应考虑卸载延迟,包括传输延迟和处理延迟;由于写入缓存的时间可以忽略不计,所以处理延迟仅针对计算任务,因此,卸载延迟为:
其中 表示计算延迟, 表示上行传输时延,θ表示在UAV上计算1位所需的CPU周期;此外,总分配的CPU频率不能超过无人机的总计算能力其中 代表无人机分配给第k个GN的计算频率;为保证网络的瞬时性能,每个时隙调度比特的处理延迟应该受到以下的约束:此外,由于应用程序的延迟要求,第k个GN处的应用程序应该在给定的时间内完全执行:
第三要设定能耗模型
1)GNs的能耗:给定处理器的计算能力,fk,处理器的功耗建模为 (焦耳每秒),其中Kk表示与第k个GN处配备的处理器芯片相关的计算能效系数;考虑到处理延迟(11),本地计算的能量消耗由下式给出
如果卸载到无人机,则在第k个GN处传输的能量消耗为:而且,第k个GN的总能量消耗不能超过其能量预算:
2)无人机能耗:在卸载过程中,无人机为这些卸载的比特分配计算资源或缓存空间;以类似的方式,对于计算卸载,执行来自第k个GN的比特的能量消耗为:其中η是无人机的CPU能耗系数;此外,无人机还可以临时缓存卸载的比特,以节省能源或避免飞行过程中CPU过载;根据能量比例模型,从第k个G缓存比特的能耗为:其中ω为无人机存储硬盘相关的缓存能量系数;此外,对于无人机推进能量消耗采用旋翼能量模型,由下式给出:
其中P0和Pi表示悬停状态下的恒定叶片轮廓功率和感应功率;Qtip是转子叶片的叶尖速度,v0表示悬停时的平均转子感应速度,PC是与环境相关的常数值;因此,无人机的总能耗可以写为:
为了让符号变简单,定义Q={q[n]}, 其中第四就是问题的制定;在本文中,旨在通过联合优化无人机的轨迹Q、任务决策A和比特调度S、带宽B和计算资源分配F来最小化无人机的能耗;因此,优化问题可以写为:满足
q[0]=Q0,q[N]=QF,#(23c)其中(23i)确保可以根据信道条件成功卸载,(23k)保证不同操作之间的公平性,(23o)和(23p)是延迟要求,而(23l),(23m)和(23q)用于任务调度和资源分配;请注意,上述公式化问题是一个MINLP问题,但由于约束(23j)中的三元变量以及目标函数和约束中的强耦合变量,导致问题变得非常棘手,此外,还有一些非线性约束(23o)、(23q)加上整数变量进一步使P更难;
由于问题P是一个MINLP问题,并且{Q,A,S,B,F}在目标函数和约束条件上仍然是耦合的,因此很难直接获得当前形式的P的解;受迭代设计的启发,采用BCD方法来解耦P中的这些变量,因为它具有处理多个耦合变量的好处;因此,将原始问题分为三个更易于管理的子问题:1)PT:无人机轨迹优化Q,2)PS:任务决策和位调度,A和S,3)PR:UAV的通信和计算资源分配B和F,并根据BCD方法以替代方式优化这些子问题;下面详细介绍BCD方法的应用;
首先,根据给定的任务决策和比特调度A和S,通信和计算资源分配B和F,可以在其内部* *
循环2的第i次迭代中获得最佳轨迹Q ;其次,利用新获得的轨迹Q ,可以根据线性规划求解器和B&B算法在其内循环中迭代优化任务决策和位调度,A和S;第三,使用求解器CVX,可以* * * * *
借助辅助变量推导出最优的(B ,F),这使得PR与新实现的(Q ,A ,S)相凸;最后,将在外循环中迭代更新导出的{Q,A,S,B,F},该过程称为BCD方法;将按照基BCD的迭代方法提出无人机轨迹、任务决策和比特调度、通信带宽和计算资源分配的联合优化,如下所示;
A:无人机的轨迹优化
给定{A,S,B,F},无人机Q的轨迹可以从以下问题导出:满足:(23c)‑(23e)(23i)(23o)‑(23q),由于目标函数中的非线性以及关于Q的约束(23i)、(23o)和(23q),它仍然是非凸的;为了使PT更易于处理,利用SCA技术在辅助变量的帮助下处理非凸性从而使目标函数相对于v[n]是凸的;在第i次迭代时使用一阶泰勒展开式,o[n]可以进一步转化为以下给定点(oi[n],vi[n])的不等式,此外,引入松弛变量 来处理约束中与rk[n]相关的非凸部分,并由下式给出:
其中 和 是常数速率和第i次迭代的一阶
2 2
导数,其中di=||q[n]‑wk||+H;最终,PT可以转化为如下凸优化问题:满足
(23c)‑(23e)
其中 PT1可以通过求解器求解,例如CVX,其细节可以参见算法一;
算法一:无人机轨迹优化
输入:给定初始点{Qi,Bi,Ai,Fi,Si},其中i=0;
*
输入:Q;
1.初始化:vi[n]=||qi[n+1]‑qi[n]||/τ,,其中
2.循环
3.给定局部点 通过求解PT1可以进一步得到最优解
4.更新局部点
5.直到收敛到容错精度;
B:任务决策和位调度
*
使用优化的轨迹Q并给定{B,F},可以通过求解以下优化问题来导出任务决策和比特调度(A,S),使无人机的能耗最小化:满足(23a)(23b)(23j)‑(23q);
由于目标函数和约束中的二元变量A和高度耦合的变量(A,S),这也是非凸的;为了解这些变量,提出了一种基于BCD的算法将PS划分为两个子问题,如下所示:·关于位调度S的线性规划(LP)问题,可以通过线性规划求解器解决;
·关于任务决策A的整数线性规划(ILP)问题,可以通过B&B解决;通过构建搜索树和计算边界值,B&B可以通过递归遍历来获得精确解;
C:资源分配
* * *
基于新推导出的{Q ,A ,S},可以通过求解PR获得通信带宽和计算资源分配,进一步降低本小节无人机的能耗
满足(23f)‑(23i)(23m)(23o)‑(23q);
由于与延迟要求(23o)、(23p)和能源供应(23q)相关的约束是非凸和非线性的,因此引入辅助变量 来处理这些强耦合约束其中 并且(31)的LHS相对于bk[n]是凹的;因此,PR可以是转化为以下问题:满足
(23f)(23g)(23h)(23m)(31),它们可以通过CVX求解;
D:整体算法
原始问题的次优解可以通过以迭代方式交替优化子问题PS、PT和PR得到,直到在外循环中达到容错精度;算法二总结了整个算法的细节,算法复杂度分析如下;I1和I2分别表示外
3 3
循环和内循环的迭代次数;PT的计算复杂度,即算法一,可以粗略给出为O(I1KN),其中K,N是算法一每次迭代中优化变量的数量;由于PS由一个ILP问题和一个LP问题组成,可以在多
3KN
项式时间内用内点法求解,而B&B算法的内环计算复杂度为O(2 );此外,由于对数形式
3.5 3 3
[46],PR的复杂度为O((2KN) );因此,所提出的整体算法的总计算复杂度为O(I1(K N +
3KN 3.5
I22 +(2KN) ));
算法二:整体算法
输入:给定初始点{Qi,Bi,Ai,Fi,Si},其中i=0;
* * * * *
输出:{Q ,A ,S ,F ,B};
1.循环
2.给定{Bi,Ai,Fi,Si},通过基于算法一求解PT1来优化无人机的轨迹Qi+1;
3.给定{Bi,Fi}和新推导出的Qi+1,(从步骤4到步骤8)可以得到任务决策和位调度{Ai+1,Si+1},其中在PS的内循环中初始化j=0;
4.循环
j,* j,*
5.在第j次迭代中求解具有给定A 的LP问题以获得S ;
j,* j,*
6.在第j次迭代时用新获得的S 解决ILP问题并推导出A ;
j j,*
7.更新A=A ,j=j+1;
8.直到收敛到容错精度;
9.利用新导出的{Ai+1,Si+1,Qi+1},通过求解PT1来优化通信带宽和计算资源分配{Bi+1,Fi+1};
10.更新变量Qi=Qi+1,Ai=Ai+1,Si=Si+1,Bi=Bi+1,Fi=Fi+1;
11.直到收敛到容错精度;
算法三:基于罚函数法降低计算复杂度的算法虽然B&B算法可以通过遍历整个变量空间找到全局最优解,随着K和N的增加进一步使得算法的复杂度不利于实际应用,所以提出了另一种基于罚函数法来降低计算复杂度的算法来处理PS;
首先,PS中的整数约束(23n)可以等价转化为由于强耦合变体,这仍然不会改变PS的非凸性;因此,引入辅助变量 其中 以重新表述PS和约束的目标函数中的耦合项,即(10)、(14)、(15)和(18)如
为了进一步解决PS问题,定义了如下惩罚函数,将等式约束(33b)惩罚到目标函数中来其中μ是惩罚参数, 是PS的目标函数,p1(A)表示由约束(33b)构成的惩罚项,由下式给出
其中
据观察,由于惩罚等式项 是凹的, 仍然是非凸的;因此,通过在第j次迭代中利用给定点 处的一阶泰勒展开来近似该项,那么目标函数 可以在第j次迭代时近似为子问题PS可以重新写为:
满足
(23a)(23b)(23j)(23m)(24),这是关于 的LP,可以通过完善的工具箱解决;请注意,这种基于罚函数法的算法通过替换算法二中的步骤4到步骤8来降低整个算法的计算复杂度;此外,基于罚函数法的算法的计算复杂度为 其中I3表示一阶泰勒展开的迭代次数;因此,新提出的整体算法的复杂度可以写为 从而降低了复杂度。