1.一种移动边缘计算中的用户计算任务卸载方法,其特征在于:将应用程序视为可拆分计算卸载,采用执行时间的二次方差作为排序依据,区分依赖性任务的执行顺序,所述方法包括如下步骤:步骤1,定义边缘计算服务器集合,并将用户的应用程序划分子任务,得到子任务集合;
步骤2,计算子任务卸载的相关参数,即完成每个子任务所需要的时延和能耗;
步骤3,构建任务关系图,建立其与待卸载子任务之间的联系,得到初始任务关系图;
步骤4,根据步骤3构建的初始任务关系图,开始进行子任务在不同边缘服务器上的计算卸载过程,包括任务关系图的更新和边缘服务器的选择,转入步骤5;
步骤5,读取初始任务关系图中子任务节点和各有向边的权值,计算子任务的执行时间方差和子任务之间的通信时延,同时考虑子任务间的内在执行顺序,对各子任务赋予卸载优先级;
步骤6,根据步骤5计算的通信时延,求出关键路径,该关键路径定义为从入口节点到出口节点的最长路径;
步骤7,进行任务卸载与任务关系图更新策略:对当前子任务,判断其前驱节点是否关键路径上的子任务节点,并且满足任务复制卸载条件;若不满足则在能耗约束下,根据最早完成时间算法选择边缘服务器,并在此边缘服务器上计算执行;否则,首先根据最早完成时间算法选择边缘服务器,然后将当前子任务的前驱子任务节点,即关键路径上的节点的内容复制到当前子任务选择的服务器中,与当前子任务的内容一并计算执行;删除其前驱子任务节点,更新任务关系图,保留该子任务的计算结果,同时计算子任务开始执行时间,子任务完成时间以及卸载决策向量;
步骤8,同时进行应用程序本地计算和边缘计算,子任务集合中的子任务卸载完成后求出总体完成时间和相应的卸载决策。
2.根据权利要求1所述的一种移动边缘计算中的用户计算任务卸载方法,其特征在于:步骤1中,定义边缘计算服务器集合为S={s1,s2...sj...sN}∪{s0},其中N表示边缘服务器的数量,s0表示本地处理器;服务器sj的计算能力用fj表示,j∈{0,1...j...N},其中f0表示本地处理器的计算能力;用户的应用程序划分为M个子任务,子任务集合为V={v1,v2...vi...vM},其中i表示子任务的标号;每个子任务vi的计算任务属性表示为Ti={mi,ci,ai},其中mi表示该子任务的数据量大小,ci表示完成任务vi所需要的CPU周期数,ai表示卸载决策,a=(a1,a2...ai...aM)表示M个子任务的卸载决策向量。
3.根据权利要求2所述的一种移动边缘计算中的用户计算任务卸载方法,其特征在于:步骤2中,计算完成每个子任务所需要的时延和能耗,包括如下步骤:步骤2a,计算用户和边缘服务器j之间的上行数据速率如下:
其中B为信道带宽,qi为传输功率,gi,j为子任务vi与
边缘服务器sj之间的信道增益,ω为噪声功率, 为来自相同服务器的干扰;
步骤2b,本地计算:
l
本地计算执行时间为 本地能耗为 其中δ为终端每个CPU周期的能耗;
步骤2c,边缘计算:
边缘计算执行时间为ti,j=ci/fj,因此为了简化,结合本地计算执行时间,任务执行时间ti,j=ci/fj,j=0时为本地计算;传输时间为ωi,j=mi/ri,j(a);传输能耗为ei,j=qimi/ri,j(a)。
4.根据权利要求2所述的一种移动边缘计算中的用户计算任务卸载方法,其特征在于:步骤3中,根据待卸载子任务的先后顺序依赖关系,构建一个有向无环任务关系图G={V,E},描述各个子任务的依赖关系,其中E表示具有先后顺序依赖关系的子任务间的有向边集合,其权值表示两个子任务间的通信数据量,根据步骤2中的相关参数,计算图G子任务节点和各有向边的权值。
5.根据权利要求3所述的一种移动边缘计算中的用户计算任务卸载方法,其特征在于:步骤3构建任务关系图,包括如下步骤:将应用程序分割成若干个子任务,根据子任务的先后顺序依赖关系,将整个应用程序的所有子任务构建成只有一个起点和一个终点的有向无环图,其中指向表示两子任务之间的先后顺序依赖关系,同时指向上标记两子任务之间通信的数据量大小。
6.根据权利要求3所述的一种移动边缘计算中的用户计算任务卸载方法,其特征在于:步骤5子任务卸载优先级排序,包括如下步骤:
步骤5a,计算得到子任务vi的平均执行时间: 然后得到子任务vi的平均执行时间方差为 同时计算子任务vi和vi′的通信时间:
其中Bjj′表示服务器sj和sj′之间的带宽,eii′表示子任务vi和vi′间通信的数据量;
步骤 5b ,根据 步骤5 a计 算得到 的参 数求 子任务 vi的 卸载 优先 级其中succ(i)表示子任务vi的后继任务组成的集
合,Cii′表示子任务vi和vi′的通信时间;按降序顺序对所有子任务的rank(i)值进行排序,即rank(i)值大的子任务优先卸载。
7.根据权利要求6所述的一种移动边缘计算中的用户计算任务卸载方法,其特征在于:步骤6所述关键路径的寻找方法,包括如下步骤:
步骤6a,定义 以及
其中ranku(i)表示从入口节点计算子任务vi的升秩值,rankd(i)表示从出口节点计算子任务vi的降秩值,succ(i)表示子任务vi的后继任务组成的集合,pred(i)表示子任务vi的前驱任务组成的集合;
步骤6b,计算任务关系图中所有子任务的ranku(i)和rankd(i)值,根据ranku(i)+rankd(i)找到关键路径上的子任务节点。
8.根据权利要求7所述的一种移动边缘计算中的用户计算任务卸载方法,其特征在于:步骤7任务卸载与任务关系图更新策略,包括如下步骤:
步骤7a,首先选取当前任务关系图中具有最大rank(i)值的子任务,判断其前驱节点是否关键路径上的子任务节点,并且若满足任务复制卸载条件,即要满足不等式AFT(i,j)>AFT(i,j)′,其中AFT(i,j)表示子任务vi卸载到边缘服务器sj上计算执行所需的时间,AFT(i,j)′表示将前驱节点复制卸载后,计算执行子任务vi所需的时间;
步骤7b,若条件不成立,则在能耗约束下,根据最小的AFT(i,j)将当前子任务vi卸载到对应的边缘服务器sj上,并在此边缘服务器上计算执行;删除其前驱子任务节点,更新任务关系图,保留该子任务的计算结果,同时计算子任务开始执行时间AST(i,j),子任务完成时间AFT(i,j),以及卸载决策向量a;
步骤7c,若条件成立,首先在能耗约束下根据AFT(i,j)选择边缘服务器,然后将当前子任务的前驱子任务节点,关键路径上的节点的内容复制到当前子任务选择的服务器中,与当前子任务的内容一并计算执行;删除其前驱子任务节点,更新任务关系图,保留该子任务的计算结果,同时更新AST(i,j),AFT(i,j)和卸载决策向量a。
9.根据权利要求8所述的一种移动边缘计算中的用户计算任务卸载方法,其特征在于:步骤8计算最终完成时间,包括如下步骤:
步骤8a,计算得到子任务最早开始执行时间:
其中i和i′是子任务的标号,j和j′
是边缘服务器的标号,avail{i,j}是边缘服务器或本地设备sj准备好执行任务的最早时间,即边缘服务器sj空闲,并且空闲时隙足够长以插入子任务i以供执行的最早时间;
是子任务vi和vi′的在不同服务器上的数据交换时间,当j=j′时,步骤8b,计算子任务最终完成时间:AFT(i,j)=min(ti,j+AST(i,j));重复步骤7和步骤
8,直到卸载完所有任务即可求得最终完成时间,对应的最佳卸载方案保存在向量a中。