与汽车工业如火如荼的蓬勃发展形成鲜明对比的是城市道路停车难问题，笔者通过组建车载自组网(VANET, vehicular ad-hoc network)，利用途经车辆的车载摄像头获取路边车位占用图像，借助图像分析手段得到车位占用信息，为附近寻找车位的驾驶员提供及时有效的可用车位推荐服务是解决车位问题的出发点.但由于车载处理器计算和通信能力有限，当车辆采集的图像信息处理任务量过大时，无法在有效的时间内提供分析结果，而采用任务卸载技术将过载的计算任务卸载到网内其他车辆节点、路边Cloudlet或路边基站等具备更强计算或通信能力的设备上，能减少任务处理的时间，加快任务执行的效率^[1].近年来，研究者提出了一些车联网中任务卸载的算法. Wu等^[2]提出了一种用于移动自组网环境下的任务卸载模型，解决了网络可用性低时任务卸载的问题. Kosta等^[3]和Cuervo等^[4]提出了节能框架，通过配置硬件组件采用卸载来优化移动设备的使用率. Zhao等^[5]提出了在小型云中进行关键路径卸载的方案，通过细粒度卸载的处理方式，解决关键路径时间复杂度优化问题. Kao等^[6]和Zhang等^[7]采用整数规划方式联合优化计算卸载、调度和云卸载策略，从而用最少的资源达到最佳处理结果.侯蓉晖等^[8]利用分组的等待时延建立李雅普诺夫方程，通过传输和丢包决策算法保证了用户时延需求. Deng等^[9]和Lü等^[10]采用多目标的动态规划算法，在最小化预估开销的同时，保证用户时延需求.

笔者提出了一种任务卸载决策的方案.该方案通过多个车载移动终端组成VANET，当某一终端数据处理能力有限，无法及时提供计算结果时，可以把任务卸载到具有更高性能的相邻移动终端上，以此来提高数据处理的效率.

1 系统模型

以下给出一个实际的应用场景，如图 1所示.用户A要获取目的地B附近空闲车位信息，通过车载网络进行请求车位查询服务.目的地B处提供有Cloudlet服务，其右侧道路边有规划的路边停车位，左侧有一个小型的基站D.在任意时间段，路段上部署有任务卸载服务功能的车辆、路边基站以及Cloudlet服务终端组建的一个自组织网络，当有车辆进入或离开该网络覆盖范围时，系统定期进行重新自组网.数据经过路边基站传输到云服务中心，经过处理后再经过多层转发发送到与查询车辆最近的路边基站，最后传送到需求车载电脑上.

1.1 任务卸载模型

根据图 1所示的应用场景，构造抽象的网络模型如图 2所示.其中，V_i(i=1, 2, …, 7)为7个移动终端节点，B_δ(δ=1, 2, …, 5)为5个路边基站，CA和CB为2个Cloudlet服务终端，C为云服务中心. V₁所在的目的地B范围内的节点组建一个临时的自组网，其中(V₂, V₃, V₄, V₅, V₆, V₇)是V₁的下一跳邻居节点，CA节点在V₃节点通信范围内，CB节点在V₄节点通信范围内.

假定本模型满足以下前提条件：数据在传输的过程中不会丢包，目标区域内的移动终端都能进行正常工作，网络是可用的且能进行有效的无线数据传输，所有节点具备持续供电能力无需考虑能耗问题.

车辆V₁经过该路段时使用车载摄像头对车位使用情况进行拍照，对拍摄的图像信息的处理有2种情况：①车辆V₁的数据处理和通信能力均较强，且能在可用的时间范围内计算得出车位使用信息以及位置信息；②车辆V₁的数据处理和通信能力有限，无法满足时间要求时，则需要执行任务卸载.

下面重点考虑第2种情况.由于车联网中节点能力差异大，不排除一跳节点较弱但第2跳节点很强的情况.基于此，提出以下二次卸载模型.假设V₁为任务发起节点，以V₁为核心对其所有一跳邻居节点按照性能递减依次排序，当需要执行任务卸载时，选择排在最上方的节点为最佳节点，若最佳节点脱离自组网，则在下一阶梯的2个节点中选择性能强的作为下一个卸载节点.接受任务的终端节点为新的起始节点，再次将任务卸载到最佳处理任务的节点.二次卸载模型如图 3所示.

1.2 任务卸载原理

为衡量节点的能力，以下给出3个定义.非特殊说明，以下节点可以是移动终端、Cloudlet服务端或者路边基站.

定义1 直接能力E_h：源节点h根据其自身设备的性能所能提供的计算、存储和通信能力的总称.

定义2 间接能力P_h：在自组网内，源节点h周围的所有一跳邻居节点中性能最强的邻居节点所能提供的计算、存储和通信能力的总称，即等价于该邻居节点的直接能力.

定义3 能力指数A_h：源节点h的能力由直接能力和间接能力两部分来衡量，是对每个节点综合能力的预估值.

直接能力和间接能力均转换为对任务处理所需的时间开销来表示，而执行某一任务所需耗费的时间开销由任务的处理时间与计算数据的传输时间构成.假定节点h的CPU处理速率为v_h、数据传输速率为d_h，可卸载计算的任务数据量为S₀，任务指令集为L₀，则源节点h的直接能力E_h可计算为

$ {E_h} = \frac{{{L_0}}}{{{v_h}}} + \frac{{{S_0}}}{{{d_h}}} $

(1)

同理，自组网内任意节点的直接能力均可依据式(1)计算得到.而源节点h的间接能力则来源于其所有一跳邻居节点中直接能力最强的节点，计算如下：

$ \begin{array}{*{20}{c}} {{P_h} = \min \left\{ {{E_{{h^ * }}}\left| {{E_{{h^ * }}}} \right. = \frac{{{L_0}}}{{{v_{{h^ * }}}}} + \frac{{{S_0}}}{{{d_{{h^ * }}}}},} \right.}\\ {\left. {{h^ * }\;表示源节点\;h\;的所有一跳邻居节点} \right\}} \end{array} $

(2)

P_h值越小，代表此节点的邻居节点所能提供的计算、存储和通信能力越强；反之亦然.

1.2.1 节点预选取

任务卸载之前需要对自组网区域内的节点进行预处理，预先对节点性能强弱做出判断，选出能力指数最高的节点作为备选节点.但由于节点的性能动态变化，其直接和间接能力不是定值，也需动态调整.

定义4 能力权重W_h：直接或间接能力在节点h整个能力指数中所占的比重.其取值由节点当前的能力值E′_h(0≤E′_h≤E_h)及无负载状态下的最大能力值E_h决定.下面采用文献[11-12]的方法来评估和计算节点的剩余计算能力和数据传输能力，并依据式(1)得到节点的当前能力值.初始状态下，W_h=0.5.计算式如下：

$ {W_h} = \frac{{1 - \frac{{{{E'}_h}}}{{{E_h}}}}}{2} $

(3)

假设W_eh和W_ph分别是终端节点h的E_h和P_h相对应的权值，且满足条件W_eh+W_ph=1.负载越小，节点当前的处理能力就越强，权值也越小.当起始节点接收到任务时，根据自身所获取的所有下一跳节点及下一跳节点邻居节点的性能参数信息，即可计算得每个邻居节点的综合能力值：

$ {A_h} = {E_h}{W_{eh}} + {P_h}{W_{ph}} $

(4)

A_h值最小的节点即可选定为起始节点的下一跳任务卸载的备选节点.

1.2.2 任务卸载决策

假定起始节点为h′，经过卸载计算后得到的计算结果数据量为S₁.根据任务量L₀、通信数据量S₀、节点CPU处理速率以及节点的通信速率，可得到任务在起始节点h′本地所需的处理时间T_h′^local为

$ T_{h'}^{{\rm{local}}} = \frac{{{L_0}}}{{{v_{h'}}}} $

(5)

若需要卸载计算，且接受卸载任务的节点为n₁，则从节点h′传输任务到n₁所需的时间T_{h′, n1}^network为

$ T_{h',n1}^{{\rm{network}}} = \frac{{{S_0}}}{{{d_{h'}}}} $

(6)

节点n₁所需的计算时间T_n1^compute和计算结果回传时间T_{n1, h′}^network分别为

$ T_{n1}^{{\rm{compute}}} = \frac{{{L_0}}}{{{v_{n1}}}} $

(7)

$ T_{n1,h'}^{{\rm{network}}} = \frac{{{S_1}}}{{{d_{n1}}}} $

(8)

若任务还需经历二次卸载，且接受卸载任务的节点为n₂，则从节点n₁传输任务到n₂所需的时间T_{n1, n2}^network为

$ T_{n1,n2}^{{\rm{network}}} = \frac{{{S_0}}}{{{d_{n1}}}} $

(9)

节点n₂所需的计算时间T_n2^compute和计算结果回传时间T_{n2, h′}^network为

$ T_{n2}^{{\rm{compute}}} = \frac{{{L_0}}}{{{v_{n2}}}} $

(10)

$ T_{n2,h'}^{{\rm{network}}} = \frac{{{S_1}}}{{{d_{n2}}}} + \frac{{{S_1}}}{{{d_{n1}}}} $

(11)

根据以上计算方法，可知任务量在自组网络中经历一次卸载全过程的总时间为

$ {T_1} = T_{h',n1}^{{\rm{network}}} + T_{n1}^{{\rm{compute}}} + T_{n1,h'}^{{\rm{network}}} $

(12)

任务量在自组网络中经历二次卸载全过程的总时间为

$ {T_2} = T_{h',n1}^{{\rm{network}}} + T_{n1,n2}^{{\rm{network}}} + T_{n2}^{{\rm{compute}}} + T_{n2,h'}^{{\rm{network}}} $

(13)

根据任务在本地的计算时间T_h′^local、经历一次卸载所需的时间T₁以及经历二次卸载所需的时间T₂的大小关系，可以进行如下决策：

$ \begin{array}{*{20}{c}} {决策 = }\\ {\left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 本地执行,\\ 执行一次卸载,\\ 执行两次卸载, \end{array}&\begin{array}{l} \left( {T_{h'}^{{\rm{local}}} \le {T_1} \le {T_2}} \right) \cup \left( {T_{h'}^{{\rm{local}}} \le {T_2} \le {T_1}} \right)\\ \left( {{T_1} \le T_{h'}^{{\rm{local}}} \le {T_2}} \right) \cup \left( {{T_1} \le {T_2} \le T_{h'}^{{\rm{local}}}} \right)\\ \left( {{T_2} \le T_{h'}^{{\rm{local}}} \le {T_1}} \right) \cup \left( {{T_2} \le {T_1} \le T_{h'}^{{\rm{local}}}} \right) \end{array} \end{array}} \right.} \end{array} $

2 任务卸载算法

本任务卸载决策算法由系统初始化、节点预选取、任务卸载决策3部分构成.

2.1 系统初始化

首先，目的地B所在区域所有节点进行自组网，构造自组网结构.当自组网结构确定后，每个节点均获知其下一跳邻居节点及所有一跳邻居节点的计算能力、通信能力以及根据节点当前的状态更新的权值参数W_eh和W_ph，且自组网结构在一个相对的时间段内处于稳定状态.每个节点配置一个参数信息表，所获取参数信息均存储在各自的参数列表中.当有节点离开或加入网络时，自组网结构进行重构，此参数列表随之进行更新.

2.2 节点预选取

依据1.2.1节节点能力指数A_h的计算方法可知，A_h越小说明其执行所需的时间越短.由此，在起始节点的所有下一跳邻居节点中，根据A_h的取值便可挑选出最佳节点.详细步骤如下：

步骤1 将任务触发节点设为起始节点.当任务到达起始节点时，根据任务量以及其参数信息表中记录的所有一跳邻居节点的参数信息，计算每个节点的E_h值，并根据每个节点当前的权值W_eh和W_ph，依据式(4)计算得到每个节点的A_h值.

步骤2 初始化集合：

$ {Q_1} = \left\{ {{V_i}\left| {一次卸载中可用传输节点} \right.} \right\} $

$ {Q_2} = \left\{ {{V_i}\left| {二次卸载中可用传输节点} \right.} \right\} $

$ {U_1} = \left\{ {{V_i}\left| {一次卸载中可用计算节点} \right.} \right\} $

$ {U_2} = \left\{ {{V_i}\left| {二次卸载中可用计算节点} \right.} \right\} $

步骤3 首先将起始节点加入集合Q₁与集合Q₂中，将其设定为预判节点.

步骤4 由预判节点进行卸载选择预判.根据每个节点A_h的大小来优选出任务卸载的下一跳节点，若出现能力指数A_h相等的节点，则取其中E_h值最小的节点为起始节点的下一跳节点.将预判节点所有一跳邻居节点中A_h值最小的节点预选定为该节点的下一跳任务卸载的备选节点.

步骤5 以备选节点为预卸载节点.由于该节点除了计算，还需将计算结果回传至起始节点，所以其既是计算节点也是传输节点.将该节点加入集合Q₁和集合U₁.

步骤6 判断预卸载节点的所有下一跳邻居节点，若存在计算能力比当前节点更强的节点，则将预卸载节点加入集合Q₂，将其最强的下一跳邻居节点录入集合Q₂和集合U₂，且作为最新的预判节点，重复执行步骤4；否则，节点预选取过程结束.

步骤7 将集合U₁、U₂、Q₁、Q₂中记录的节点输出，即可得到经过一次卸载和经过二次卸载的最佳任务卸载节点以及传输数据的节点.

2.3 任务卸载决策

根据1.2.2节任务卸载决策判断依据，对节点自身以及集合U₁、U₂、Q₁、Q₂中的节点能力进行比较，即可确定任务卸载选择哪种方式.

步骤1 用户A进行空车位需求广播，采集到车位图像信息的起始节点准备进行任务卸载预判.

步骤2 根据U₁集合内的节点与Q₁集合内的节点可以计算出任务在自组网络中经历一次卸载全过程的总时间T₁.根据U₂集合内的节点与Q₂集合内的节点可以计算出任务在自组网络中经历二次卸载全过程的总时间T₂.

步骤3 通过计算得到的T_h′^local、T₁和T₂的数值大小，依据1.2.2节的决策策略，即可确定任务最优的执行方案.

3 仿真实验与分析 3.1 实验环境

仿真实验使用机器配置为AMDRyzen31200四核处理器、4 GB内存，使用Windows10操作系统，采用Matlab R2016a进行仿真实验.仿真实验中，遵循专用短程通信技术以及IEEE 802.11p(WAVE)协议，设定车联网设备传输速率为20 Mbit/s.由于车联网节点移动速度较快，为了模拟车联网中实际情况，分别选取6个和12个邻居终端节点与源节点来组建自组织网络，且每个终端节点的CPU处理速率和数据传输速率在合理的范围内随机赋值，其中源节点的处理速率设定为1.2 GHz，采集的图像信息大小分别定义为3 MB和6 MB.

3.2 实验结果与分析

为了验证所提的任务卸载决策算法，根据实际可能出现的情况假设了2种场景.

场景1：V_j(j=2, 3, …, 13)的邻居节点不存在Cloudlet或基站等具备更强计算能力的节点.将V_j节点和其邻居节点的CPU处理速率的范围均设置为[0.8, 2.4]GHz，且V_j邻居节点的CPU处理速率在较大概率上会比V_j节点的CPU处理速率高.

场景2：V_k(k=2, 3, …, 13)节点的CPU处理速率都比V₁节点的CPU速率低，但V_k节点的邻居节点存在Cloudlet或基站等具备更强计算能力的节点.将V_k节点CPU处理速率的范围设置为[0.6, 1.2]GHz，V_k邻居节点的CPU处理速率的范围设置为[1.6, 10.0]GHz.

首先，考虑场景1.假设图片为标清图且大小为3 MB，任务量设定为[1.0×10⁶, 2.0×10⁶]条指令，以每10万条指令集进行递增.当自组网规模为7个节点时，如图 4(a)所示，T₁在部分区间呈增长趋势，部分区间呈下降趋势，T₂主要呈下降趋势.由于V_j节点自身的处理能力较弱，但它的邻居节点可以提供更高性能的计算服务，所以V₁会选择该节点作为卸载节点.当自组网规模扩大为13个节点时，如图 4(b)所示，T₁在某一区域呈明显上升趋势，T₂在多数指令集区间段大于T_h′^local.由于V_j的CPU处理速率和通信速率与V₁节点相差无几，但任务经历2次的传输会额外消耗一定的时间，此时选择在V₁节点上进行卸载计算最为节省时间.

假设图片为高清图且大小为6 MB，任务量设定为[2.0×10⁶, 4.0×10⁶]条指令，以每20万条指令集进行递增.当自组网规模为7个节点时，如图 5(a)所示，在部分区域T₁呈明显上升趋势，T₂呈缓慢上升趋势且任务经历二次卸载所花费的时间逐渐比直接在V₁节点上计算大(由于在传输过程中节点选取的不合理).当自组网规模扩大为13个节点时，如图 5(b)所示，在大部分任务区间，T₂比T₁以及T_h′^local要小，表明随着节点的增加任务二次卸载的优势越明显.

通过对比4种计算过程所需花费的时间可知，在少数情况下任务经过二次卸载的计算时间要比任务经过一次卸载以及直接在本地进行卸载的时间要长，但是多数情况下经历二次卸载任务所花费的时间是最短的.

其次，考虑场景2.图片为标清图且大小为3 MB，相应的指令集范围为[1.0×10⁶, 2.0×10⁶]条，以每10万条指令集进行递增.当自组网规模为7个节点时，如图 6(a)所示.当指令集为[1.5×10⁶, 1.8×10⁶]条时，T₁和T₂波动较大；而在指令集为[1.1×10⁶, 1.3×10⁶]条时，T₁和T₂波动较小.当自组网规模扩大为13个节点时，如图 6(b)所示.当指令集为[1.8×10⁶, 2.0×10⁶]条时，T₁出现较大波动而T₂逐渐趋于稳定状态.这是因为随着自组网节点数的增加，V_k的邻居节点为高性能服务节点的概率也随之增加.

假设图片为高清图且大小为6 MB，相应任务指令集范围是[2.0×10⁶, 4.0×10⁶]条，以每20万条指令集进行递增.当自组网规模为7个节点时，如图 7(a)所示.当指令集为[3.4×10⁶, 3.8×10⁶]条时，T₁波动较大；当指令集为[2.2×10⁶, 2.8×10⁶]条时，T₂波动较小.当自组网规模扩大为13个节点时，如图 7(b)所示.当指令集为[2.0×10⁶, 3.0×10⁶]条时，T₂波动较小基本保持平缓趋势；当指令集为[2.4×10⁶, 4.0×10⁶]条时，T₁波动较大.由示意图可以看出，卸载计算的时间消耗与任务的大小关系较小，与节点个数的多少关系较大.这是因为V_k的邻居节点有基站，当节点较少时，任务经历一次卸载的时耗较不稳定且消耗的时间比在V₁节点上计算要多，而经历二次卸载的时耗波动虽较不稳定，但消耗时间较少；当节点增多时，任务经历一次卸载的时耗波动较大，而经历二次卸载的时耗较稳定且时耗相比在V₁节点上计算要少. 表 1和表 2分别给出了上述不同情况下的计算数据.

4 结束语

为了提高移动自组网络情景下任务计算卸载的效率，提出了面向车联网实时应用场景的任务卸载决策算法.该算法通过节点对数据传输时间和任务计算时间的预判，采用二次卸载策略选择不同的节点进行任务的卸载计算，有效地避免了在任务量大的情况下，任务计算效率低的缺点.通过实验仿真及分析验证了所提方案的有效性，为车联网场景下的实时应用提供了一定的参考.