1.一种基于蚁群算法的面向低轨道卫星边缘计算任务调度方法,其特征在于,包括如下步骤:
1)建立通信模型:根据设备个数k(k∈{1,2,...K})、信道带宽B、传输功率Pk、高斯白噪声信号的功率σ0、信道增益gk,s和其他设备对设备k产生的干扰 建立上行传输速率Rk模型,表达式为
2)建立计算模型:包括所需的CPU周期数目ck,上行数据大小dk,计算模型分为本地计算和卫星计算模型,包括如下步骤:
2‑1)建立本地计算模型,包括如下步骤:
2‑1‑1)利用所需的CPU周期数目ck和时钟频率fk,l建立本地计算时延模型Tk,l,其表达式为
2‑1‑2)利用所需的CPU周期数目ck、时钟频率fk,l和有效的开关电容κ建立本计算能耗模2
型Ek,l,其表达式为Ek,l=κck(fk,l) ;
2‑1‑3)利用本地计算时延模型和本地计算能耗模型,建立本地计算时延和能耗函数ψk,l,其表达式为ψk,l=(1‑β)Tk,l+βEk,l,其中β∈[0,1]是业务的时延和能耗的权重;
2‑2)建立卫星计算模型,包括卸载任务和卫星执行任务,具体步骤如下:
2‑2‑1)根据排在次序q的第k位的任务数据大小dq(k)和排在次序q的第k位的任务上行传输速率Rq(k),建立卫星计算的传输时延模型 其表达式为
2‑2‑2)根据排在次序q的第k位的所需的CPU周期数目cq(k)和卫星时钟频率fs,建立卫星计算的计算时延模型 其表达式为
2‑2‑3)根据任务q(k)在卫星计算开始的时刻Hq(k)和任务q(k‑1)在卫星计算完成时刻Hq(k‑1),建立卫星计算等待时延模型 其表达式为
2‑2‑4)根据步骤2‑2‑1)建立的传输时延模型 和排在次序q的第k位的设备传输功率Pq(k),建立传输能耗模型
2‑2‑5)根据有效开关电容κ、排在次序q的第k位的所需的CPU周期数目cq(k)和卫星的时2
钟频率fs,建立卫星所消耗的能耗模型κcq(k)(fs) ;
2‑2‑6)根据步骤2‑2‑1)建立的传输时延模型 步骤2‑2‑2)建立的计算时延模型步骤2‑2‑3)建立的等待时延模型 步骤2‑2‑4)建立的传输能耗模型和步骤2‑2‑
5)建立的卫星所消耗的能耗Eq(k),s,建立卫星计算时总的时延和能耗函数模型ψq(k),s,其表达式为 其中β∈[0,1]是能耗和时延的权重因子;
3)建立问题模型:在设备的任务在本地计算不能超过最大的容忍时间 能量消耗不能超过设备的可用能量 本地设备的时钟频率 和卸载任务不能超过截止期限 的约束下,以及用二进制表示卸载决策ok∈{0,1},通过所述的约束确保设备的计算资源、电池能量和多用户具有不同QoS需求,根据步骤2‑1‑3)建立的本地计算时延和能耗函数ψk,l和步骤2‑2‑6)建立的卫星计算时总的时延和能耗函数模型ψq(k),s,建立时延和能耗系统最小花费模型
4)设计基于蚁群算法的任务调度方法,采用蚁群算法优化多设备的任务执行次序问题和通过调度时钟频率优化本地计算的花费,使时延和能耗系统的总花费最小。
2.根据权利要求1所述的一种基于蚁群算法的面向低轨道卫星边缘计算任务调度方法,其特征在于,步骤4)中,所述的基于蚁群算法的任务调度方法,具体步骤如下:
4‑1)调度时钟频率优化本地计算,包括如下步骤:
4‑1‑1)根据时延和能耗系统最小花费模块,调度时钟频率优化本地计算的模型如下:
4‑1‑2)令 则Qk,l(fk,l)的值只取决于fk,l,因此,将Qk,l(fk,l)对fk,l求导并等于0,得到
4‑1‑3)根据步骤4‑1‑1)中的约束条件C1和C2,简化得到 和
4‑1‑4)根据步骤4‑1‑3)的结果和步骤4‑1‑1)中的约束条件C3,联合得到和
4‑1‑5)确保fk,l的可行域是非空,则满足f′u≤f′h,因此步骤4‑1‑1)问题的最佳结果为:
4‑2)优化任务执行次序,用蚁群算法优化多设备的任务执行次序,则步骤3)中的时延和能耗系统最小花费模型化简为如下所示:C2:ok∈{0,1}
基于蚁群算法的任务调度方法步骤如下:
4‑2‑1)初始化变量:在计算前对CPU周期数目、有效开关电容、设备的传输功率、数据大小、能耗和时延的权重因子、卫星的时钟频率、蚂蚁数目、信息素挥发系数、最大迭代次数、信息素强度相关参数进行初始化;
4‑2‑2)输入各个任务在云端执行时间、传输时间、计算卸载最大容忍时间、计算卸载的系统花费、本地计算的系统花费;
4‑2‑3)构建解空间,如下所示:
4‑2‑3‑1)将K个任务进行随机排列,每只蚂蚁随机地放置于不同的初始任务上,并维护一个路径记忆向量,用于存放该蚂蚁依次经过的任务;
4‑2‑3‑2)蚂蚁在构建任务排队序列的每一步中,用轮盘赌法选择下一个要选择的任务;
4‑2‑3‑3)蚂蚁在构建任务排队序列的每一步中,用轮盘赌选择下一个要选择的任务;
4‑2‑3‑4)判断是否有待选的任务,如果有,则重复步骤4‑2‑3‑1),如果没有待选的任务,则记录本次迭代的任务最佳执行次序;
4‑2‑4)记录本次迭代的系统最小花费,如下所示:
4‑2‑4‑1)初始化每只蚂蚁所走路径的花费为零,依次把每只蚂蚁的路径取出来,判断每个任务是否存在等待时间;
4‑2‑4‑2)根据用户QoS需求,判断用户的任务是否计算卸载;
4‑2‑4‑3)如果不满足用户QoS需求,则该用户执行本地计算,通过调度时钟频率优化本地计算来降低本地计算的时延和能耗,降低系统的总花费;
4‑2‑4‑4)如果满足用户QoS需求,则该用户执行卫星计算并计算该任务卫星计算的总时延和能耗;
4‑2‑4‑5)记录本次迭代所有任务总系统花费;
4‑2‑5)记录当前迭代次数中的系统花费最小的任务执行次序,同时,对各个任务执行次序上的信息素浓度进行更新;
4‑2‑6)若迭代次数小于最大迭代次数则迭代次数加一,清空蚂蚁经过任务执行次序的记录表,并返回步骤4‑2‑3‑1),否则终止计算,输出最优解。