本发明涉及基于半马尔可夫决策过程车载雾辅助的车队任务卸载方法。本发明同时考虑任务卸载中的发送时延和计算时延等因素，建立基于半马尔可夫决策过程的任务卸载模型。然后分别定义了系统状态集、动作集并推导了系统状态转移概率公式以及系统奖励函数，其次基于贝尔曼方程利用值迭代算法求解SMDP模型获得最优的任务卸载策略。该方案计算复杂度适中，系统模型合理，充分考虑了任务如何分配以及任务卸载过程中涉及到的各种时延。仿真结果表明，该方案在保证任务卸载时延的前提下，能获得更大的系统长期收益。
基于半马尔可夫决策过程车载雾辅助的车队任务卸载方法
技术领域
[0001] 本发明涉及车载任务卸载技术领域，尤其是指基于半马尔可夫决策过程车载雾辅助的车队任务卸载方法。
背景技术
[0002] 随着科技发展，无人驾驶车队得到越来越多的普及，从而来提高道路安全性。其中，每个车队都由一辆头车和几辆成员车组成。具体来说，头车控制整个车队的速度、加速度和行驶方向，成员车以相同速度一辆接一辆跟随头车在同一车道上行驶。无人驾驶车辆上一般会配备有摄像头和雷达等，这些设备会产生大量冗余数据。这时候就需要车辆对数据进行计算和分析以便提取有用信息。根据Intel公司的数据，一辆车需要进行计算、分析和融合大量的传感器数据(大约1GB/s)以便能做出安全决策。但是一辆车自身的计算能力是有限的，并且当新任务到达时该车辆本身也可能正在处理其他任务，使得该车辆的计算资源被占用，这时就需要将任务卸载给车队内其他车辆进行协作处理，然后将计算的结果返回给该车辆。但是由于车队内部的车辆数目有限，会出现车队资源紧张的情况，这时任务无法及时处理，导致处理结果无法及时接收，车辆无法进一步做出安全决策。
[0003] 车载雾计算(VFC)系统能够提供强大的计算资源来解决以上问题。VFC系统由道路中的一些车辆组成，每个车辆能够提供计算资源来协助处理任务。当车队资源紧张时，车队中的车辆会选择将任务传送给头车，再由头车将任务卸载到行驶在车队旁的VFC系统中的车辆来协作处理，然后VFC系统中的车辆将计算结果返回给头车，再由头车将计算结果转发到相应的车辆。VFC系统可以在车队资源紧张时为车队中的车辆提供各种低延迟和实时应用程序，从而大大提高了网络容量。在以上任务卸载过程中，车辆的通信方式均采用IEEE 802.11p分布式协调功能。对于自动驾驶车辆来说，任务卸载的时延至关重要，时延过大意味着车辆在卸载任务以后要经过较长时间才能接收到计算结果，这会造成车辆无法及时根据计算结果做出相应的反应，导致发生安全事故的概率大大增加。卸载时延包括发送时延、计算时延和回传时延。发送时延是发送任务占用的时间，计算时延是计算资源处理任务占用的时间，回传时延是反馈计算结果占用的时间。
[0004] 在车队中，车辆一般计算资源充足，所以一辆车足够处理一个计算任务。但是车队中的每辆车所拥有的计算资源不同，所以由不同车辆处理任务时产生的计算时延也会不同。
[0005] 在车载雾中，车辆一般由私家车组成。每辆车的计算资源有限并且大小近似相同。所以将任务卸载到VFC处理时本发明选择一辆或多辆车进行处理。具体来说，头车将任务分成几个大小相同的子任务，采用802.11pDCF协议分别将子任务传输给VFC中对应的几辆车。
由于处理卸载任务的车辆数目增加，头车分别将几个子任务卸载给VFC中对应的几辆车而产生的发送时延也增加，但同时由于处理该任务的计算资源增多，相应的计算时延降低。并且VFC中的车辆是随机到达和离开的，这使得VFC中资源动态变化。
[0006] 在资源有限的车队和VFC中，如何考虑车队中处理任务的车辆的选择、VFC中处理任务的车辆数目以及VFC中车辆的随机到达和离开，使得系统中的长期回报最大是个重要问题。其中，回报与发送时延、计算时延和回传时延有关。
[0007] 目前还尚未有研究802.11p DCF协议下对车队任务卸载进行优化的车载雾计算系统。
发明内容
[0008] 为此，本发明所要解决的技术问题在于克服现有技术中车队内部资源有限、车载雾内部资源动态变化、任务的多样性和任务卸载时延等问题。
[0009] 为解决上述技术问题，本发明提供了一种基于半马尔可夫决策过程车载雾辅助的车队任务卸载方法，基于半马尔可夫决策过程车载雾辅助的车队任务卸载方法，包括如下步骤：
[0010] 步骤S1：基于半马尔可夫决策过程定义车载雾辅助的车队任务卸载系统的状态集和动作集；
[0011] 步骤S2：根据系统的状态集和动作集得到系统当前的状态s和动作a(s)，并根据系统当前的状态s和动作a(s)计算系统状态转移概率；
[0012] 步骤S3：根据系统奖励和系统状态转移概率建立贝尔曼方程并求解系统中的最优卸载策略；
[0013] 所述系统奖励为系统在状态s采取动作a(s)的系统奖励，表示为系统的立即增益与系统状态转移期间所消耗成本之间的差值，计算如下：
[0014] R(s,a)＝U(s,a)‑G(s,a)
[0015] 其中U(s,a)表示系统在状态s下采取动作a(s)后，系统的立即增益；G(s,a)表示从当前状态转移到下一状态期间，系统的消耗。
[0016] 在本发明的一种实施方式中，步骤S2中，所述转移概率的计算方法为：分别计算车队发出任务请求时的转移概率、车辆处理的任务离开系统时的转移概率、车载雾中计算单元共同处理的任务离开系统时的转移概率、车辆到达系统时的转移概率、车辆离开系统时的转移概率，并进行归一化。
[0017] 在本发明的一种实施方式中，步骤S3中，所述立即增益的表达式为：
[0018]
[0019] 其中，η表示时间的单位价格，El表示由任务请求者自身处理时所需的时间，Tp表示车队内传输任务的传输时间，每个任务所需的计算资源为d，车队车辆Vi(i＝1,...,N)的计算资源为fi， 表示由头车将任务传输给车载雾中j个计算单元共同处理的传输时间，惩罚参数为ζ。
[0020] 在本发明的一种实施方式中，所述Tp和 具有相同的计算公式，用Ttr表示：
[0021] Ttr＝θ·Etr·Tslot
[0022] 其中θ表示车辆需要传输的任务数，在车队内，其值恒定为1，在头车与车载雾组成的网络中，其值取决于系统的决策，当 头车将任务划分为相同大小的j个子任务并分别传输给车载雾中的j辆车，θ的值为j；Etr表示传输任务所需要的平均时隙数；Tslot表示每个时隙的平均时长。
[0023] 在本发明的一种实施方式中，每个时隙的平均时长Tslot表达式为：
[0024] Tslot＝qidle·Tidle+qs·Ts+qc·Tc
[0025] 其中 表示时隙处于空闲的概率， 表示该时隙处于成功传输数据的概率，qc＝1‑qidle‑qs表示该时隙处于数据碰撞的概率，Tidle表示每个空闲时隙的时长，Ts＝Header+E[P]/θ+SIFS+δ+ACK+DIFS+δ表示时隙处于成功传输数据状态的时长，Tc＝Header+E[P]/θ+SIFS+δ+ACKtimeout表示时隙处于数据碰撞状态的时长；其中Header＝PHYh+MACh表示数据包头部长度，其值等于数据包物理层以及媒介接入层头部长度之和；E[P]表示任务的长度；δ表示传播时延；SIFS、ACK以及DIFS分别表示SIFS、ACK以及DIFS的长度。且 表示车辆传输数据
产生碰撞的概率。
[0026] 在本发明的一种实施方式中，任务传输所需要的平均时隙数Etr的表达式为：
[0027]
[0028] 其中m为重传次数，q为碰撞概率，Wmin为最小竞争窗口。
[0029] 在本发明的一种实施方式中，步骤S3中，所述系统的消耗为：
[0030]
[0031] 其中α表示连续时间折扣因子，C(s,a)是当前状态下采取动作后，系统中正在处理任务的车辆数，其表达式为：
[0032]
[0033] β(x,a)表示系统下一时刻所有事件到达率总和，β(x,a)的计算表达式为：
[0034]
[0035] 在本发明的一种实施方式中，所述贝尔曼最优方程表示为：
[0036]
[0037] 其中 表示归一化后的系统奖励， 表示归一化后的折扣因子， 表示归一化后的转移概率，引入常数，
N为车队中车辆数目，下一时刻事件A的到达率为Nλp，事件F+1和F‑1的到达率分别为λv和μv，fi为车队中的车辆Vi的计算资源大小，M表示车载雾中计算单元的个数，NR表示单个任务在车载雾中最多能分配到的计算单元数目，fv为车载雾中每个车辆的计算资源，d为每个计算任务所需的计算资源。
[0038] 在本发明的一种实施方式中，所述求解车载雾辅助的车队任务卸载系统中的最优卸载策略，包括：设定正数ε，对系统中的每一个状态都基于贝尔曼最优方程进行迭代，直到相邻两次迭代，每个系统状态价值函数绝对值的差值都小于设定值时停止迭代。
[0039] 在本发明的一种实施方式中，所述最优卸载策略计算表达式为：
[0040]
[0041] 本发明的上述技术方案相比现有技术具有以下优点：
[0042] 本发明所述的基于半马尔可夫决策过程车载雾辅助的车队任务卸载方法，针对车队内部资源有限、车载雾内部资源动态变化、任务的多样性和任务卸载时延等问题，提出了一种基于半马尔可夫决策过程的由车载雾辅助的车队任务卸载方案。首先使用IEEE 802.11p协议传输任务，同时考虑任务卸载中的发送时延和计算时延等因素，建立基于半马尔可夫决策过程的任务卸载模型。然后分别定义了系统状态集、动作集并推导了系统状态转移概率公式以及系统奖励函数，其次基于贝尔曼方程利用值迭代算法求解SMDP模型获得最优的任务卸载策略。该方法计算复杂度适中，系统模型合理，充分考虑了任务如何分配以及任务卸载过程中涉及到的各种时延。仿真结果表明，该方案在保证任务卸载时延的前提下，能获得更大的系统长期收益。
附图说明
[0043] 为了使本发明的内容更容易被清楚的理解，下面根据本发明的具体实施例并结合附图，对本发明作进一步详细的说明，其中
[0044] 图1为系统框架图。
[0045] 图2为本发明方案与其他方案获得的长期收益对比图(λp＝20)。
[0046] 图3为本发明方案与其他方案获得的长期收益对比图(λp＝13)。
具体实施方式
[0047] 下面结合附图和具体实施例对本发明作进一步说明，以使本领域的技术人员可以更好地理解本发明并能予以实施，但所举实施例不作为对本发明的限定。
[0048] 本发明的基于半马尔可夫决策过程车载雾辅助的车队任务卸载方法，步骤如下：
[0049] 步骤S1：首先定义系统的状态集。在半马尔可夫决策模型中，系统状态包含车队中车辆处理任务状态、车载雾计算系统中由不同数目的车辆共同处理任务的个数、车载雾中车辆总数以及当前发生的事件。图1给出了系统框架图。系统的状态集表示如下：
[0050]
[0051] 其中ni表示车辆Vi(i＝1,...,N)处理的任务的个数，ni＝0表示车辆Vi为空闲车辆，ni＝1表示车辆Vi正在处理任务；Bj表示由车载雾中j个计算单元共同处理的任务的个数，NR表示单个任务在车载雾中最多能分配到的计算单元数目；M表示车载雾中计算单元的个数，且满足 e表示当前发生的事件。
[0052] 步骤S2：定义系统的动作集。从集合 中选取动作，事件和动作之间的关系表示如下：
[0053]
[0054] 其中‑1表示当前事件为由车辆Vi处理的任务离开系统，由车载雾中j个计算单元共同处理的任务离开系统，车辆Vi到达以及车辆Vi离开时，系统不采取任务动作；b表示事件为车队产生计算任务，并且系统计算资源十分匮乏，系统拒绝处理该任务； 表示车队产生计算任务，系统将任务分配到车队车辆Vi中处理； 表示系统将任务传输到车载雾中的j个计算单元处理。 表示事件集合，N为车队中车辆数目，A表示车队中车辆发出计算任务，Di表示由车队中车辆Vi(i＝1,...,N)处理的任务被处理完成，Lj(j＝1,...,NR)表示由车载雾中j个计算单元共同处理的任务离开系统，F+1和F‑1分别表示车辆到达和离开车载雾。
[0055] 步骤S3：定义系统状态转移概率。在半马尔可夫决策过程中，根据当前的状态s和动作a(s)，分五种情况计算转移概率P(x|s,a)。其中动作a(s)的值从集合选取。其具体表达式为：
[0056] (1) 即车队发出任务请求。
[0057] 第一种情况是当车队发出任务请求并且系统将任务分配给车队车辆Vi，此时车队中车辆总数不变，车载雾中由j(j＝1,...,NR)个计算单元共同处理的任务个数不变，则下一时刻事件A即事件车队中车辆发出计算任务的到达率为Nλp，其中N为车队中车辆数目，λp为任务到达率。事件Lj的到达率为Bj·jfv/d。其中Bj为由车载雾中j个计算单元共同处理的任务的数目，fv为车载雾中每个车辆的计算资源，d为每个计算任务所需的计算资源。事件F+1和F‑1的到达率分别为λv和μv。事件车队车辆处理的任务离开系统的到达率需要分以下两种情况讨论。其中E表示下一时刻发生的事情。
[0058] 1)
[0059] 当前事件为车队产生任务，并由车队第i辆车处理，则车辆Vi处理的任务个数加一，所以在下一时刻事件车辆Vi处理任务离开系统的到达率为(ni+1)·fi/d。其中fi为车队中的车辆Vi的计算资源大小。
[0060] 2)
[0061] 当前事件为车队产生任务，并由车队第i辆车处理，则车辆Vi处理的任务个数加一，下一时刻发生的事件为由车队第k辆车处理的任务离开，由于车辆Vk处理的任务个数不变，则事件Dk的到达率为nk·fk/d。
[0062] 第二种情况是当车队发出任务请求并且系统将任务分配给车载雾中的j辆车共同处理，此时车队中车辆总数不变并且处理的任务个数不变，则下一时刻事件A的到达率为Nλp，事件Di(i＝1,...,N)的到达率为ni·fi/d。事件F+1和F‑1的到达率分别为λv和μv。事件由车载雾中j(j＝1,...,NR)个计算单元共同处理的任务离开的到达率需要分以下两种情况讨论。
[0063] 1)
[0064] 这种情况表明系统将任务分配给车载雾中的j辆车共同处理，则车载雾中j辆车共同处理的任务个数加一，因此在下一时刻事件Lj的到达率为(Bj+1)·jfv/d。
[0065] 2)
[0066] 这种情况表示下一时刻发生的事件为由车载雾中的m辆车共同处理的任务离开，由于m辆车共同处理的任务个数不变，因此在下一时刻事件Lm的到达率为Bm·mfv/d。
[0067] 综上所述，给定系统状态 以及动作a(s)，此时系统状态转移概率的表达式为：
[0068]
[0069] (2) 即车辆Vi处理的任务离开系统，此时系统状态转移概率的表达式为：
[0070]
[0071] (3) 即车载雾中j个计算单元共同处理的任务离开系统，此时系统状态转移概率的表达式为：
[0072]
[0073] (4) 即车辆Vi到达系统，此时系统状态转移概率的表达式为：
[0074]
[0075] (5) 即车辆Vi离开系统，此时系统状态转移概率的表达式为：
[0076]
[0077] 其中，β(x,a)表示系统下一时刻所有事件到达率总和。某一事件的转移概率为下一时刻该事件的到达率与下一时刻所有事件到达率的比值。综上所述，在不同系统状态s以及动作a(s)下，β(x,a)的计算表达式为：
[0078]
[0079] 步骤S4：定义系统的奖励模型。在状态s采取动作a(s)的系统奖励可以表示为系统立即增益与系统状态转移期间所消耗成本之间的差值。表示如下：
[0080] R(s,a)＝U(s,a)‑G(s,a)
[0081] 其中U(s,a)表示在当前状态下采取动作a(s)后，系统的立即增益；G(s,a)表示从当前状态转移到下一状态期间，系统的消耗。
[0082] 立即增益的计算方式可划分为以下几种：
[0083] (1)当e＝A, i＝1,...,N时：
[0084] 当请求车辆发出计算任务并且系统决定将其卸载到车队中的车辆Vi进行处理时，请求车辆通过802.11p协议DCF功能进行队内通信，将计算任务传输给指定车辆，则系统立即增益为η(El‑Tp‑d/fi)。其中η表示时间的单位价格，El表示由任务请求者自身处理时所需的时间，Tp表示车队内传输任务的传输时间，请求车辆发出的每个计算任务所需的计算资源为d，车队车辆Vi(i＝1,...,N)的计算资源为fi。
[0085] (2)当e＝A, j＝1,...,NR时：
[0086] 当系统决定由车载雾中j个计算单元处理该任务时，首先请求车辆通过车队内通信将任务传输给头车，头车将任务划分为j个相同大小的子任务，再将子任务分别传递给车载雾中的j个计算单元，则系统的立即增益为 其中 表示由头车将任务传输给车载雾中j个计算单元共同处理的传输时间。
[0087] (3)当e＝A,a＝b时：
[0088] 当车队发出计算任务并且系统内计算资源十分匮乏时，系统拒绝处理该任务，并受到惩罚，惩罚参数为ζ。
[0089] (4)当 时：
[0090] 当车队车辆处理的任务离开车辆、车载雾中车辆处理的任务离开、车辆到达时，系统不采取任务动作，立即收益为零。
[0091] (5)当e＝F‑1, 时：
[0092] 当车载雾中空闲车辆离开时，系统不采取任务动作，立即收益为零。
[0093] (6)当e＝F‑1, 时：
[0094] 当车载雾中正在处理任务的车辆离开时，会导致任务处理失败，系统受到惩罚且参数为ζ。
[0095] 综上所述，系统立即增益的表达式为：
[0096]
[0097] 传输时延Tp和 还需要进一步确定。由于车队内车辆采取802.11p协议的DCF功能以单播方式传输任务，而车队头车与移动车载雾组成的网络也是采取802.11p DCF功能以单播方式传输任务，只是两个网络中的车辆数不同，所以传输时延Tp和 具有相同的计算公式。用Ntr表示网络中的车辆数，对于车队网络，Ntr等于车队数的车辆总数N；而对于头车与车载雾组成的网络，其值为M+1。接下来，将推导出网络传输时延的表达式，为了方便，用Ttr表示传输时延，但其公式适用于传输时延Tp和
[0098] 网络传输时延Ttr的表达式为：
[0099] Ttr＝θ·Etr·Tslot
[0100] 其中θ表示车辆需要传输的任务数，在车队内，其值恒定为1；在头车与车载雾组成的网络中，其值取决于系统的决策，当 头车将任务划分为相同大小的j个子任务并分别传输给车载雾中的j辆车，所以θ的值为j；Etr表示传输任务所需要的平均时隙数；Tslot表示每个时隙的平均时长。
[0101] 每个时隙的平均时长Tslot表达式为：
[0102] Tslot＝qidle·Tidle+qs·Ts+qc·Tc
[0103] 其中 表示时隙处于空闲的概率， 表示该时隙处于成功传输数据的概率，qc＝1‑qidle‑qs表示该时隙处于数据碰撞的概率，Tidle表示每个空闲时隙的时长，Ts＝Header+E[P]/θ+SIFS+δ+ACK+DIFS+δ表示时隙处于成功传输数据状态的时长，Tc＝Header+E[P]/θ+SIFS+δ+ACKtimeout表示时隙处于数据碰撞状态的时长。其中Header＝PHYh+MACh表示数据包头部长度，其值等于数据包物理层以及媒介接入层头部长度之和；E[P]表示任务的长度；δ表示传播时延；SIFS、ACK以及DIFS分别表示SIFS、ACK以及DIFS的长度。且 表示车辆传输数据
产生碰撞的概率。
[0104] 任务传输所需要的平均时隙数Etr的表达式为：
[0105]
[0106] 其中m为重传次数，q为碰撞概率，Wmin为最小竞争窗口。
[0107] 系统消耗G(s,a)为：
[0108]
[0109] 其中α表示连续时间折扣因子，C(s,a)是当前状态下采取动作后，系统中正在处理任务的车辆数，其计算表达式为：
[0110]
[0111] 步骤S5：求解车载雾辅助的车队任务卸载系统中的最优卸载策略。根据贝尔曼方程采取值迭代算法求解最优卸载方案。
[0112] 贝尔曼最优方程可表示为：
[0113]
[0114] 其中 表示归一化后的系统奖励， 表示归一化后的折扣因子， 表示归一化后的转移概率，引入常
数。
[0115] 设定非常小的正数ε，对系统中的每一个状态都基于上面贝尔曼最优方程公式进行迭代，直到相邻两次迭代，每个系统的状态价值函数绝对值的差值都小于ε(1‑γ)/2γ，*停止迭代。此时，每个系统状态都根据以下公式，求得最优策略π(s)。
[0116]
[0117] 值迭代算法得伪代码如下所示：
[0118] 算法1值迭代算法
[0119] Step 1：对于每个系统状态s∈S，初始化状态值函数 设定非常小的正数ε，设定迭代次数k＝0；
[0120] Step 2：对于每个系统状态，利用贝尔曼方程计算状态价值函数 即
[0121]
[0122] Step 3：如果对于每个系统状态s∈S都满足
[0123] 则进入Step 4；否则，迭代次数加1，即k＝k+1并进入Step2；
[0124] Step 4：对于每个系统状态s∈S，计算最优卸载策略π*(s)通过公式
[0125]
[0126] 值迭代算法中的收敛误差为：
[0127]
[0128] 图2和图3验证了不同的任务到达率下，本发明卸载方案性能优于基于贪婪算法的卸载方案，即本发明方案获得更多的系统长期收益。
[0129] 本发明通过上述方法，首先使用IEEE 802.11p协议传输任务，同时考虑任务卸载中的发送时延和计算时延等因素，建立基于半马尔可夫决策过程的任务卸载模型。然后分别定义了系统状态集、动作集并推导了系统状态转移概率公式以及系统奖励函数，其次基于贝尔曼方程利用值迭代算法求解SMDP模型获得最优的任务卸载策略。该方法计算复杂度适中，系统模型合理，充分考虑了任务如何分配以及任务卸载过程中涉及到的各种时延。仿真结果表明，该方案在保证任务卸载时延的前提下，能获得更大的系统长期收益。
[0130] 本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD‑ROM、光学存储器等)上实施的计算机程序产品的形式。
[0131] 本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0132] 这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0133] 这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0134] 显然，上述实施例仅仅是为清楚地说明所作的举例，并非对实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式变化或变动。这里无需也无法对所有的实施方式予以穷举。而由此所引申出的显而易见的变化或变动仍处于本发明创造的保护范围之中。
