1.一种车联网中基于任务关联性的卸载方法,其特征在于,具体包括:以车联网中最小任务完成总时延为目标,以路侧单元和服务车辆作为服务节点的差异、V2X通信模式选择、任务时延和通信距离为约束条件,构建基于任务关联性的卸载模型;
采用基于任务车辆优先级的KM匹配算法求解该卸载模型,为任务车辆匹配卸载的服务节点;
在V2V通信模式下,采用基于子任务权重和子任务优先级的调度算法求解该卸载模型,对子任务按照匹配后的服务节点生成调度决策,根据调度决策完成V2V下子任务卸载;
在V2I通信模式下,采用基于任务车辆优先级和子任务优先级的调度算法求解该卸载模型,对子任务按照匹配后的服务节点生成调度决策,根据调度决策完成V2I下子任务卸载。
2.根据权利要求1所述的一种车联网中基于任务关联性的卸载方法,其特征在于,在构建基于任务关联性的卸载模型之前还包括在单路侧单元下多车辆直行通信场景下,根据车辆信息将车辆划分为任务车辆和服务车辆;每个任务车辆具有一个待计算的任务,每个任务分为多个关联性的子任务,服务车辆和路侧单元均作为服务节点辅助任务车辆进行任务计算;并计算出卸载到服务车辆的传输速率。
3.根据权利要求1所述的一种车联网中基于任务关联性的卸载方法,其特征在于,所述基于任务关联性的卸载模型的公式为:s.t.C1:ai,m∈{0,1},
其中, 表示每个任务车辆i带有由多个子任务关联形成的任务, 表示任务车辆i的卸载对象选择集合, 表示时间点t时刻子任务qi,m是否在本地计算的时间因子,当时表示子任务qi,m在t时刻在本地计算,当 时表示子任务qi,m在t时刻未在本地计算; 表示时间点t时刻子任务qi,m是否在服务节点j上进行计算的时间因子,当时表示子任务qi,m在t时刻在服务节点j上进行计算;当 时表示子任务qi,mT在t时刻未在服务节点j上进行计算;N 表示任务车辆的总数;令 ti表示任务车辆i中所有子任务计算完成的时间, 表示子任务qi,m的完成时间,Qi表示任务车辆i中所有子任务集合;ai,m表示对子任务qi,m执行卸载决策的二元变量,bi,j表示任务车辆iS选择服务节点j作为卸载对象的二元变量;N表示服务节点的总数;约束条件C1和C2表示一个任务车辆中的子任务可以选择本地计算或可以卸载计算,且每个任务车辆都进行卸载但只能选择一个服务节点作为卸载对象;ti,m表示子任务qi,m卸载需要的时间, 表示子任务qi,m的最大容忍时延;C3表示处理子任务需要的时间不能超过该子任务的最大容忍时延;Mi表示每个 中包含子任务的个数,C4、C5和C6表示在本地,卸载给服务车辆和卸载至路侧单元的非抢占CPU计算方式约束,即在每个节点上,一个时间点下只有一个任务进行计算;C7表示在处理子任务的时间内,任务车辆在不能离开服务节点的通信距离。
4.根据权利要求1所述的一种车联网中基于任务关联性的卸载方法,其特征在于,任务车辆优先级的计算方式包括计算出所有任务车辆的所有子任务的平均优先级,按照计数函数计算出每个任务车辆中的子任务优先级高于平均优先级的个数;根据任务车辆与服务节点的平均距离、任务车辆的最大计算时间、任务车辆的子任务优先级高于平均优先级的个数,计算出每个任务车辆优先级。
5.根据权利要求4所述的一种车联网中基于任务关联性的卸载方法,其特征在于,任务车辆优先级的计算公式表示为:v
其中,pri 表示任务车辆i的优先级,ui表示任务车辆i的子任务优先级高于平均优先级的个数,max{uv}、min{uv}分别表示任务车辆集合中子任务优先级高于平均优先级个数的最小值,Ti表示任务车辆i的最大计算时间,max{Tv}、min{Tv}分别表示任务车辆集合中计算时间的最大值和最小值, 表示任务车辆i与服务节点的平均距离, 分别表示任务车辆集合与服务节点的平均距离的最大值和最小值。
6.根据权利要求1或4所述的一种车联网中基于任务关联性的卸载方法,其特征在于,子任务优先级的计算方式包括根据子任务的出度和权重定义子任务的重要度,根据子任务的权重、重要度以及完成时间计算出每个子任务优先级。
7.根据权利要求6所述的一种车联网中基于任务关联性的卸载方法,其特征在于,子任务优先级的计算公式表示为:其中, 表示时间点t时刻子任务qi,m的优先级,impi,m表示子任务qi,m的重要度,max{impi,n}、min{impi,n}分别表示子任务集合中重要度的最大值和最小值, 表示子任务qi,m的最大计算时间, 分别表示子任务集合中计算时间的最大值和最小值,wi,m表示子任务qi,m的权重,max{wi,n}、min{wi,n}分别表示子任务集合中权重的最大值和最小值。
8.根据权利要求1所述的一种车联网中基于任务关联性的卸载方法,其特征在于,所述采用基于任务车辆优先级的KM匹配算法求解该卸载模型,为任务车辆匹配卸载的服务节点包括:将车联网中服务车辆与相应数量的任务车辆建模为一个待匹配的二分图 二分图中每个节点即为系统车辆,所述系统车辆包括服务车辆和任务车辆;
根据服务车辆的数量,按照任务车辆优先级划分出待匹配的任务车辆;
其中,系统中的车辆集合表示为 任务车辆和服务车辆的集合分别表示S
为 待匹配的任务车辆为优先级前N 个任务车辆,N表
T S
示系统车辆集合的总数,N表示任务车辆的总数,N表示服务车辆的总数;
T S
将任务车辆集合N中的任务车辆按任务车辆优先级正序排序,将服务车辆集合N中的服务车辆按服务车辆计算能力正序排列;
将待匹配的任务车辆添加到V2V车辆集合 中,其他任务车辆直接添加到V2I车辆集合 中;
设置V2V车辆集合 中节点的顶标lt(vi)=max{ri,j},其中,设置服务车辆集合 中V2V的节点顶标ls(vj)=0,vi表示任务车辆节点,ri,j表示V2V车辆集合V 中vi和服务车辆集合sN中节点vj链接时边的权值,vj表示服务车辆节点;
从V2V车辆集合 中优先级最高的任务车辆节点开始增广寻找完备匹配;
如果没有找到完备匹配,修改V2V车辆集合 和服务车辆集合 中节点的顶标值,再次从未匹配节点开始增广直至完全匹配。
9.根据权利要求1所述的一种车联网中基于任务关联性的卸载方法,其特征在于,采用基于子任务权重和子任务优先级的调度算法,进行V2V下子任务卸载的过程包括:S1:将子任务按照其权重进行升序排序,若权重相同,将权重相同的子任务再按照子任务优先级降序排序,得到子任务决策顺序;
S2:按照子任务决策顺序,将排序后的子任务添加至待分配卸载决策集合 中;
S3:计算出子任务qi,m在本地的完成时间 和卸载的完成时间 当 且子任务qi,m卸载至服务节点j计算;当 或 时,子任务qi,m进行本地计算; 表示任务车辆i选择卸载任务至服务节点j时离开通信范围的时间;
S4:任务车辆和服务节点按照子任务的决策顺序进行计算,更新时间因子表示子任务的执行情况;待子任务完成卸载及调度分配后,将子任务移除待分配卸载决策集合 直至为空。
10.根据权利要求1所述的一种车联网中基于任务关联性的卸载方法,其特征在于,用基于任务车辆优先级和子任务优先级的调度算法求解该卸载模型,完成V2I下子任务卸载的过程包括:S1:将所有子任务按照子任务优先级划分到高优先级子任务集合 和中优先级子任务集合 中,也即将没有前置任务或前置任务均完成的子任务添加至 中,将直接前置任务正在传输或计算的子任务添加至 中;
S2:对于在集合 中的子任务,按照子任务优先级排序,依次判断子任务是否卸载;
S3:计算出子任务qi,m在本地的完成时间 和卸载的完成时间 当 且子任务qi,m卸载至服务节点j计算;当 或 时,子任务qi,m进行本地计算;
S4:将卸载至路侧单元也即服务节点j=0的子任务按子任务优先级顺序放入初始调度策略集合S5:路侧单元对收到的子任务的调度顺序进行动态调整,并更新时间因子表示子任务的执行情况;
S6:在通过对集合 中的子任务进行初步卸载与调度后,得到本地和路侧单元上集合中所有子任务完成的预计时间,对于集合 中的子任务,结合预计完成时间和直接前置任务的计算情况,进行卸载及调度;
S7:路侧单元根据车辆优先级,降序轮询各任务车辆在集合 中的子任务是否卸载;
S8 :当卸载同 时满足以 下条 件, 和
执行卸载,将子任务qx,m添加至集合 并按照上述S5更新方式法则更新集合
其中 为子任务qx,m的优先级, 为子任务qz,n的优先级, 为子任务qz,n的完成时间, 子任务qx,m卸载过程中的传输时间, 为子任务qx,m卸载后的计算时间,为子任务qx,y的完成时间, 为子任务qx,m的本地计算时间, 为卸载至路侧单元也即服务节点j=0时的时间限制因子;
S9:在集合 中所有子任务均计算完成后,更新集合 和集合 直至所有子任务完成计算。