CN116321199B 一种基于时序图和图匹配理论的任务卸载方法、设备及介质 （南京邮电大学）

一种基于时序图和图匹配理论的任务卸载本发明公开了一种基于时序图和图匹配理维度表示了用户移动过程中动态变化的基站集基于图匹配理论中的A*算法对任务卸载策略进发将任务卸载问题建模为图同态问题并基于A*算法为移动场景下的依赖任务的卸载问题提出2步骤S1：获取应用图sa中的子任务的集合va并按照每个子任务的时延容忍值对所有任务v0表示对子任务进行本地处理的用户终端；当n≠0时，BSn表示对子任务进行边缘计算的基步骤S5_1：确定时间戳ts下的卸载节点集合CandidateSet以及准备好的子任务集合步骤S5_3：根据OpenList中每个子任务的标记更新其候选的中子任务vj是子任务vj的直接前序子任务；载，则候选节点集合不进行更新而使用初始值即candidateset={BS(ts)UBS};BS(ts)为时步骤S5_4：按照OpenList中每个子任务的排名顺序Rank(vj)，依次为每个子任务计算3当子任务vj的时延容忍值大于下个时间戳即LST(vj)>ts+1时，将子任务vj判定为延迟子任务vj的直接前序子任务为vi，当子任务vi有多个直接后序子任务vj即succ(vi)>2当子任务vj不满足延迟卸载和串行处理时，则将子任务vj判定为普通卸载并将其标记所述VertexTrans(vj)计算公j)表示子任务vj的直接前序子任务集合，m,n表示卸载节点BSm和卸载节点BSn之间连边的开始时刻，am,n表示卸载节点BSm4理器执行时，实现如权利要求1_7中任一所述的一种基于时序图和图匹配理论的任务卸载5用户的移动过程中为单个应用中的每个子任务选择合适的卸载节点以减少应用的实际计[0009]步骤S1：获取应用图sa中的子任务的集合va,并按照每个子任务的时延容忍值对[0011]步骤S3：将子任务v0的卸载节点确定为用户终端即x0,n＝BS0,将子任务v0从6[0012]步骤S4：将子任务vI的卸载节点确定为用户终端即xI,n＝BS0，将子任务vI从中子任务vi是子任务vj的直接前序子任务；载，则候选节点集合不进行更新而使用初始值即candidateset={BS(ts)UBSO}eBS(ts)为子任务vj判定为延迟卸载并将其标记为st务vj即succ(vi)＞2时，将子任务vj判定为串行处理并将其标记为status(vj)＝2。succ7)表示用户等待接入的时长，(am,n_sm,n)表示用户接入后的可用时理器执行时，实现如第一方面中任一所述的一种基于时序图和图匹配理论的任务卸载方配理论出发将任务卸载问题建模为图同态问题并基于A*算法为移动场景下的依赖任务的8务vj的输入数据，因此当子任务vj的前序子任务vi还没有完成的情况下是无法开始处理子j的前序子任务可能有多个。下覆盖用户的基站节点集合以及用户的终端，即candidateset=fBS(0)u因为用户依赖关系的即两个相关的子任务之间有一定的数据量要转移。如果子任务vj1和子任务vj29不同的边缘服务器所能提供的计算资源也是不同的。当用户在移动过程中进行任务卸载，移动性所带来的不利影响在于用户可能因为切换基站而导致服务基站不能在用户离开覆盖范围之前将正在处理的子任务的计算结果及时返回给用户而造成任务卸载的中断甚至务之间存在依赖性即子任务需要有前序子任务的计算结果来作为自身在卸载节点处执行考虑是否将存在依赖关系的两个子任务卸载到相同的卸载节点以减效用即求解应用最小的完成时延被转化成了求解最短的路径。由于子任务之间存在依赖同的候选的卸载节点的集合中选择合适的卸载节点所形成的匹配对将作为最短路径上的[0068]输入数据：应用图sa=(va,Ea),基站图SS=(VS,ES,D)。[0072]步骤S1：获取应用图sa中的子任务的集合并按照每个子任务的时延容忍值对[0074]步骤S3：将子任务v0的卸载节点确定为用户终端即x0,n＝BS0,将子任务v0从[0076]步骤S4：将子任务vI的卸载节点确定为用户终端即xI,n＝BS0，将子任务vI从任务放在用户终端处进行本地处理以保证用户及时接收应迟卸载并将其标记为status(vj)＝=2；当子任务vj不满足上述两种情况时，则将子任务vj判定为普通卸载并将其标记为站所提供的计算资源以及用户接入基站后的可用时长)，这一点充分利用了用户移动性所刻覆盖用户的基站具有不良好的卸载条件(比如用户可接入的时长较短，当用户选择接入后将很快发生切换)，则用户可以选择接入下个时刻下的基站以期接入卸载条件更佳的基[0083]进行串行处理的子任务将有可能选择和其前序子任务的其他后序子任务相同的[0084]进行普通卸载的子任务是没有采取上述延迟卸载以及串行处理两种方式的子任务，这种类型的子任务将从当下时刻覆盖用户的基站集合中选择卸载条件最好的卸载节候选节点的集合以及其前序子任务的卸载节点即candidateset=(BS(ts)UBS,uxim3,其)表示用户等待接入的时长，(am,n_sm,n)表示用户接入后的可用时因此A*算法中最短路径上的节点等价于所求解的站都配备了相应的MEC服务器。用户需要将一个截止时间为D即需要在(0,D)时段内完成的计算密集型应用卸载给基站或其自身的终端设备，对此仅考虑(0,D)时段内的用户位置以该基站对于用户来说是不可用的，因此用户接入某个基站后的可用时长是具有一定限制程中可卸载节点的集合表示成有向时序图SS=(VS,ES,D),其中是卸载节点集合，(卸载用户可卸载的基站集合为BS(T1)=BS1UBS2,第二个采样时刻T2下用户可卸载的基站集合过程中可卸载节点的集合为其中BS0是用户的终端设备以表示本地处理(如图3)来表示，即sa=(VA,EX),其中va是子任务集合，边的集合用来似性指标，最后用改进后的A*算法即所提供的OASA算法来求解图编辑序列即任务