停车边缘计算：车载自组织网络中基于路边停车的任务卸载

杜 恬，朱金奇，刘念伯，曹 轲，郭杨隆

1(天津师范大学 计算机与信息工程学院，天津 300387) 2(电子科技大学 计算机科学与工程学院，成都 610054)

1 引 言

随着无线通信技术和电子技术的进步及各种物联网设备的涌现，车载自组织网络(Vehicle Ad Hoc Neteorks，VANETs)中的智能车辆节点除了装备无线通信和计算设备外，还装备了定位系统、电子地图和大量传感器，使得有关多媒体娱乐服务、车辆安全、智能驾驶、交通和信息等应用[1-3]不断涌现.车载自组织网络将成为未来智能交通系统的关键组成部分.

然而，许多车辆应用需要大量计算资源并具有延迟限制[4-6]，例如车辆通过内置摄像头感知周围环境，并通过深度学习方法识别潜在的危险车辆，如满载油的油罐车等，以协助车辆安全驾驶.再比如车辆根据从感知图像中收集的数据推断停车场的状态，然后与周围的车辆共享此信息，以帮助周围车辆快速找到停车位.而车辆的计算和存储资源通常有限，这使得车辆本身无法完成这些计算任务.由于远程云具有丰富的计算和存储资源，一些研究[7，8]提出将车辆产生的计算密集型任务上传到远程云执行.然而，远程云服务器通常距离车辆较远，导致较长的任务传输延迟，并可能产生链路拥塞问题，这严重影响任务的服务质量，尤其对于延迟敏感型应用.

近几年，移动边缘计算(Mobile Edge Computing，MEC)技术兴起.通过将云服务器部署到设备附近的网络边缘，MEC能够为用户提供低延迟和高可靠性的服务[9，10].目前已有若干研究[11-13]将MEC技术与VANET相结合.这些研究中，MEC服务器通常置于路侧单元RSUs(Roadside Uints，RSUs)附近，为此任务卸载的性能受RSU数量和性能的极大影响.然而，这些研究大都具有以下缺陷：1)VANETs中基础设施建设的费用较高，造成RSUs和MEC服务器无法覆盖所有城市区域;2)RSUs的通信范围有限，无法完全覆盖城市道路上行驶的车辆；3)RSUs和MEC服务器在自然灾害发生时可能失效.因此，有必要研究如何利用道路上车辆的计算资源，为车辆用户提供可靠的计算服务.

受城市范围内具有数量庞大、广泛分布且长时间停放的地面停放车辆的启发，且目前许多资源和时间消耗的算法都支持分布式计算，本文提出停车边缘计算(Parking Edge Computing，PEC)的思想，在无RSUs或MEC服务器覆盖的区域，把城市道路两边的车辆组织成停车簇，令停车簇充当天然的边缘计算服务器，为道路上的移动车辆提供计算服务，及时处理周围车辆的任务请求.停车边缘计算不仅扩展了MEC的服务范围，拥有丰富且稳定计算资源的停放车辆还能缓解MEC服务器的资源限制，辅助MEC执行部分卸载任务.

本文基本思想分为两部分：首先把一条道路两边的停放车辆组织成停车簇，其次基于停车簇进行任务卸载的设计，以最大化任务的完成数量.实验分析表明，与其他几种策略相比，本文所提策略具有较高的任务完成率和卸载率.

2 相关工作

已有将MEC应用于VANETs的研究主要分为两类.第1类研究仅通过边缘服务器解决任务卸载问题，如文献[14]中，作者将MEC与软件定义网络(Software Defined Networking，SDN)相结合，并通过MEC加强5G技术下车载网络的控制.Liu等[15]提出令边缘服务器处理支持SDN的车载网络中的数据，以实现快速服务和降低数据传输延迟的目的.Zachary等[16]提出分层的车辆边缘计算框架，解决MEC服务器资源受限的问题，并引入备份服务器弥补MEC服务器计算资源的不足.此外，文献[17]等提出将MEC和社交网络相结合来提高驾驶者的驾驶体验.

在第2类研究通过将MEC与移动车辆或远程云结合，解决用户的任务请求.文献[18]中作者提出利用远程云处理服务请求，以克服移动设备的电池容量限制.文献[19]认为MEC服务器和远程云协作能带来更好的服务质量.当且仅当MEC服务器过载时，延迟容忍的任务被卸载到远程云，而实时任务依然由MEC服务器执行.此外有研究利用移动车辆辅助MEC服务器执行计算任务.如文献[20]令MEC服务器共享部分任务给移动车辆.Sun等[19]建立高速公路环境下移动车辆组成的边缘服务系统，移动车辆产生的任务可以在本地执行或卸载到拥有强大计算能力的MEC车辆上执行.然而，受交通状况和车辆高速移动的影响，MEC服务器与移动车辆间的接触时间高度动态变化，使得任务难以完全共享.

文献[21]证实城市中的停放车辆拥有大量计算资源，可以为用户提供各种服务.Adiv等[22]表明车辆每天超过95%的时间处于停放状态.为此，本文把地面停放车辆组织成停车簇，为道路上的移动车辆提供边缘计算.停车边缘计算克服了固定基础设施的缺陷，在基础设施缺少或失效时，仍能够及时处理周围车辆的任务计算请求.

3 系统架构

3.1 基本架构

本文停车边缘计算的基本架构见图1，由以下几部分组成：

图1 停车边缘计算架构Fig.1 Parking edge computing architecture

1)停车簇：我们把位于一条的道路上的停放车辆组织成停车簇.当道路较短时，该道路上的停放车辆被组织成一个停车簇，当道路较长时，该道路上的停放车辆构成多个停车簇，令每个停车簇的长度不超过L米.

2)停放车辆：路边停放车辆是任务的执行者，为移动车辆的卸载任务提供计算服务和存储服务.

3)移动车辆：道路上行驶的智能车辆装备有电子地图、GPS、无线通信模块和各种感知设备等，以一定的概率产生计算任务，简单的任务可以在本地执行，计算密集型任务需要卸载到停车簇，由停车簇为其提供计算服务，移动车辆和停放车辆以及移动车辆之间以V2V(Vehicle to Vehicle，V2V)通信方式，通过DSRC技术进行通信.

此外，距离道路最近的RSU负责维护计算模型的参数，如模型的结构，网络的权重等，并周期性发送模型的参数给停车簇的簇头.

3.2 任务模型

4 停车簇的建立和维护

本节首先通过停车调查说明室外停车的特点，然后对停车簇的建立和维护进行描述，并对停车簇的稳定性进行分析.

4.1 停车调查

本文提出的策略建立在地面停车的基础上，因此地面停放车辆的数量和分布对所提策略的性能有很大影响.报告(1)https://www.docin.com/p-1901768493.html.显示西安市建成区路侧停放车辆密度为29.164m2/停放车辆，停放车辆的密度高，路侧停车位占用率大于70%.报告(2)http://wenku.baidu.com/view/36bbf31255270722192ef7c1.html.对武汉市停车状况进行分析，显示室外停车位的高使用情况.文献[23]对天津市区的地面停车调查也证明天津市区停车密度较高.文献[24]的停车报告显示，多米尼克国家的地面停车场平均占用率约69%，在一天中的某些时段和某些地区，平均占有率甚至超过了85%.上述调查结果均表明地面停放车辆的稳定性和高密度性.由于室外停放车辆具有分布广泛，数量庞大，停车时间长的特点，我们认为把地面停放车辆组织成天然的边缘计算服务器，为移动车辆提供计算服务是可行的.

4.2 停车簇的构建

停车簇的建立过程如下：若一条道路长度较长，则把该道路分成多个停车簇，令每个停车簇长度不超过L米.对于每个停车簇，位于中间的停放车辆成为簇头，其他车辆为成员车辆.各簇成员周期性地报告自己的信息如ID号，是否有任务被执行等给簇头，簇头根据收到的信息可了解各个成员车辆的状态.簇头负责管理成员车辆，维护整个簇结构.此外，簇头还要接收本簇所在道路上移动车辆的任务请求，负责停放车辆和资源的分配.考虑到簇头随时都有可能离开，选择簇头的一个邻节点成为备用簇头，令备用簇头始终保持簇头收集信息的复本，以增强簇的可靠性.另外，为降低通信开销，停车簇内停放车辆与簇头之间的数据传输按照文献[25]所述方法进行，即各簇成员首选确定到簇头的最佳路径.每次和簇头通信时均首先尝试按照最佳路径发送消息，当且仅当最佳路径无效时才选择其他路径进行数据传输.

4.3 停车簇稳定性分析

本节从理论上分析一段时间内停车簇内成员的变化，以证明停车簇的稳定程度.

假设停车簇内停放车辆数目为N(t).A、Q分别为单位时间内新到达的停放车辆及离开的停放车辆.则下一时间段Δt后停放车辆数目为：

N(t+Δt)=min{N(t)+AΔt-QΔt，C}

(1)

其中，C为停车簇容量.从公式(1)可以看出，该排队过程是一个马尔科夫过程，因此N(t+1)=j的概率为：

(2)

假设单位时间到达和离开停车簇的停放车辆数量服从泊松分布[26]，如果A≥Q，则下一时间段内，停车簇内新增的停放车辆N(Δt)=A(Δt)-Q(Δt)=n的概率为：

(3)

(4)

图2描述了在时间间隔Δt，停放车辆变化的概率.图2(a)和图2(b)显示在时间间隔Δt=15秒时，对于不同的到达

图2 停放车辆变化的概率Fig.2 Probability of change of parking vehicles

率和离开率，停放车辆变化不超过2的概率大于98%.由此得出：停车簇是相对稳定的，能够支持任务的分配.

5 任务卸载的设计

本节首先介绍停车边缘计算的基本思想，接着分析任务的完成时间，最后介绍任务调度的实现.

5.1 基本思想

移动车辆i产生的任务Ti可以通过两种方式执行：在本地执行或将任务卸载到停车簇.当本地计算资源满足任务延迟需求时，任务在车辆本地执行；否则Ti被卸载到所在路段的停车簇.当车辆i需要进行任务卸载时，首先产生任务请求消息，并通过车辆间的传输把任务请求消息发送给簇头节点.任务请求消息包含产生消息时车辆i的位置、车辆ID号以及Ti的信息.簇头节点对同时收到的任务卸载请求执行相应的任务调度算法，为任务分配簇内停放车辆节点和计算资源，并在其上部署计算模型以实现任务并行计算.之后，簇头把调度算法的执行结果回传给源车辆(车辆i).源车辆收到执行结果后，通过V2V方式卸载自己的任务给分配到的停放车辆节点.停放车辆执行完任务后，通过车辆间存储转发的传输方式把任务输出结果传输给源车辆.若源车辆离开停车簇所在道路，认为找不到源车辆，此时输出结果回传失败.图3具体描述了任务卸载的过程.

图3 任务卸载的基本流程Fig.3 Basic process of task offloading

5.2 任务卸载的分析

设车辆的计算资源为Lv，移动车辆i产生任务Ti.任务Ti本地完成时间为Ci/Li.如果Ci/Li满足：

(5)

任务在本地执行，否则任务需要卸载到停车簇执行.

若任务需要被卸载到源车辆所在路段的停车簇j，则任务的完成时间由3部分组成，分别为任务数据传输到执行任务的停放车辆的传输时间、任务执行时间和输出结果的传输时间：

(6)

其中Ti为任务完成时间，tij为任务数据的传输时延，Ri是该任务分配到的资源量，Ot为结果数据的传输时延.传输时延tij表示为：

(7)

其中h是任务数据通过车与车的中继被传输的跳数，Cvel是车辆之间数据传输的吞吐量，v是车辆在该道路上的平均移动速度，R为车辆的通信半径，l为源车辆到距离它最远的执行任务的停放车辆的距离.h计算如下：

(8)

其中ρ为道路上当前的车辆的密度，通过车辆装备的电子地图获得.

对于Ot，簇头判断任务执行完后源车辆所在位置，源车辆所在位置估计为vi(tij+Ci/Ri)+Li，其中Li是簇头获取的源车辆发送任务请求时所在位置，vi是车辆i的移动速度.若执行完任务后源车辆依然位于在停车簇所在的路段，我们忽略输出结果的传输时延，否则认为源车辆距离执行任务的停放车辆距离较远，Ot不能忽略.若Ot不能忽略，其值采取公式(7)所述方法计算为：

(9)

其中lcur为源车辆当前所在位置距离最远的执行其任务的停放车辆的距离，h′是输出结果通过车与车的中继被传输的跳数，Outp是输出结果的大小.

5.3 任务调度分析

道路上的不同移动车辆可能同时产生计算任务，这些任务相互竞争停车簇拥有的资源.不合理的资源分配可能导致资源的不合理利用、任务完成时间增长以及任务完成率低下，因此要优化任务调度.本文为任务分配停车簇内的停放车辆和计算资源时，目标是最大化成功完成的任务总数量.该任务调度表示为如下优化问题：

(10)

s.t.

(11)

Ri≤Cmax，∀i∈M

(12)

(13)

公式(10)中的函数s为单位阶跃函数，当且仅当x≥0时，s(x)=1，否则s(x)=0.约束条件(11)保证每个任务的完成时间不超过任务的最大延迟容忍值限制，约束条件(12)确保每个任务获得的计算资源不超过任务可获得的最大计算资源，约束条件(13)保证所有任务获得的资源总和不超过停车簇拥有的资源.

该任务调度涉及到计算资源的分配和停车节点的选择，任务获得的计算资源可以是低于Cmax的任意值，且任务可以被分配给任意一个停放车辆执行，因此该问题是一个NP难问题.我们改进文献[27]所提的SAC(Sampling-and- Classification，SAC)算法解决该问题，在解决优化问题时，原算法没有考虑如何满足优化问题的约束条件限制.为此，改进原算法的主要目的是在解决无约束的优化问题的基础上满足约束条件(11)-约束条件(13)，从而达到解决本文优化问题的目的.改进的算法伪代码如算法1所示.与原算法类似，改进的算法首先初始化可行解集S0={x1，…，xs，…，xm}，初始化过程中通过独立同分布的方法随机从可行解中进行采样，并在采样时最大化停车簇内停放车辆成员的使用率，令每个停放车辆至少执行一个任务并满足公式(12)的资源限制.对于任务延迟不满足约束条件的任务，放弃该任务.之后进入循环，在每次迭代中，算法查询目标函数以评估生成的解，并形成一个二进制分类数据集.其中sign[v]函数中，如果v≥ 0返回+1，否则返回-1，αt是阈值.在分类阶段，在Bt上训练二进制分类器，以近似区域.在采样步骤中，以概率λ从H中采样，以1-λ的概率从其他可行解中进行采样，其中H是正解的集合，满足H{h：X→{-1，1}}，h是将可行解空间映射到{-1，1}的函数.在整个过程中，记录最优的解决方案，最优的解决方案将作为输出返回.

算法1.Improved Classification Algorithm

步骤：

1.fors=1 toS0do

2. Sample the sth solutionxsfrom the feasible solutionspaceUx∀n∈N，assign at least one task to each par--ked vehicle member randomly and let the resources assigned to each task less thanCmax;

3. For∀Ti(i∈M)，updateTs，iasTs，i=tij+Ci/Ri+Ot

5. updatexs，i=0

6.endfor

8.fort=1 to size(S0)do

10.fori=1 to size(S0) do

11.ht=C(Bt)，whereht∈H

12.xi=Sampling(ht，λ)and letSt=St∪{xi}

13.endfor

15.endfor

16.returnx*

6 性能模拟

6.1 实验设置

本文采用JAVA实现实验仿真，假设每个停车簇的长度是1000m，道路为双向车道，整个道路的宽度为8m，默认情况下设置每个停车簇所在路段有60辆移动车辆，车辆传输半径为250m，车速为40-80km/h，MAC层的车辆与车辆之间的通信使用2MHz的802.11信道.在仿真中，设置停放车辆在停车簇内随机停放，停放车辆密度为100辆/千米，遵守文献[25]中对城市道路停车情况的调查，设置为道路停车密度适中的情况.假设停车簇在仿真之前便已建立，以一分钟为周期进行维护.

此外，车辆拥有的计算资源为0.4GHz，每辆车辆以60%的概率产生任务.算法1中的参数取值为λ=0.95，根据每个停车簇所在路段有60辆移动车辆的情况，令m=60.其他默认参数设置如表1所示.

表1 任务卸载的模拟参数Table1 Simulation parameters of task offloading

为了验证所提协议的性能，我们与下述其他3种策略进行试验对比：

本地执行(Local computing，LC)：所有车辆的计算任务都由车载单元在本地执行.

按任务紧急程度分配计算资源(Urgency-driven allocation，UDA)：当本地计算时间大于任务延迟容忍值时，车辆将任务数据发送给停车簇.停车簇根据任务的紧急程度进行资源分配，任务越紧急(容忍延迟越小)，为它分配的资源就越多.为了进一步优化性能，在为任务分配停放车辆时，先随机分配若干停放车辆节点，判断任务在延迟容忍值内能否到达这些停放车辆节点，如果能到达就发送任务，如果不能到达，再重新随机为它分配停放车辆.如果所有分配的停放车辆都不可达，则本轮不分配该任务.

随机分配计算资源(Random-driven allocation，RDA)：当本地计算时间大于任务延迟容忍值时，车辆将任务发送给停车簇，由停车簇执行.停车簇随机为任务分派停放车辆成员和计算资源，以执行卸载的任务.

性能评估指标为任务完成率和任务上传率.任务完成率即成功完成的任务数量与产生的总任务的数量之比，任务上传率是由停车簇成功完成的任务数量与产生任务的总数量的比值.

6.2 实验分析

6.2.1 车辆速度的影响

本组实验研究移动车辆速度对各种策略性能的影响.我们把经过停车簇的移动车辆的速度从10km/h逐渐增加到100km/h，各协议的性能变化如图4所示.

图4 移动车辆速度的影响Fig.4 Influence of moving vehicle speed

图4(a)显示，随着移动车辆速度的增加，RDA，UDA和本文所提3种任务调度策略的完成率均有一定增长，而LC策略的完成率保持不变.这是因为车辆速度的增加使车辆之间的连通性增强，任务数据能够更快的传递到执行车辆，由于传输时间缩短，任务总的完成时间减小，所以能在最大容忍延迟时间内完成的任务数量增多.由于LC中任务只能在本地被执行，本地资源十分有限，无法完成复杂任务处理，因此LC的完成率最低.如图4(b)所示，随着移动车辆速度的增加，RDA，UDA和本文所提3种任务调度算法的上传率均增长.本文所提算法始终保持最高的任务完成率和上传率，这是因为所提策略不仅利用具有丰富计算资源的停放车辆执行卸载任务，且所提策略对资源和执行节点的分配进行了优化，因此能够最大程度利用停车簇的资源完成卸载任务.

6.2.2 车辆数量的影响

本组实验研究移动车辆数量对任务调度策略性能的影响.我们把移动车辆数量从20增加到140，各种策略的性能变化如图5所示.

图5 移动车辆数量的影响Fig.5 Influence of the number of mobile vehicles

图5(a)显示，随着移动车辆数量的增加，UDA和所提策略的完成率在移动车辆数量为20～40间几乎不变，这是因为移动车辆较少时产生的总任务数少，UDA和所提协议中每个卸载任务能够分配到足够的计算资源，因此任务执行时间较短.随着移动车辆数量继续增加，除LC之外的3种策略任务完成率均呈现下降趋势，这是因为此时产生的任务总数量增多了，而停车簇拥有的计算资源不变，因此每个任务分配到的资源大大减少.本文所提策略始终具有最大的完成率.图5(b)表明，随着移动车辆数量的增加，RDA，UDA和本文所提3种任务调度策略的上传率均下降.本文所提策略上传率最高，说明本文所提策略能够尽可能的利用停车资源，尽量完成各任务的计算请求.

6.2.3 计算资源需求的影响

本组实验研究计算资源的需求对策略性能的影响.我们把计算资源需求从600cycles/bit变化到2000cycles/bit，各种策略的性能变化如图6所示.

图6 计算资源需求的影响Fig.6 Influence of the requirements of computing resources

图6(a)显示，随着所需计算资源需求的增加，4种任务调度策略的完成率均呈下降趋势，且本地执行策略的下降趋势最明显.这是因为任务对资源需求的增大导致完成任务需要的计算资源增多，而移动车辆本身计算资源极其有限，当任务所需计算资源较大时，任务无法由本地执行.而其他3种策略随着任务所需资源增大，任务可以卸载到停车簇执行.相比本地执行，任务卸载到停车簇可以获得比本地执行更加丰富的计算资源，从而相比LC大大降低了任务完成时间.如图6(b)所示，在任务所需计算资源增大情况下，本文所提策略，UDA和RDA的上传率均先增大后降低.原因是执行任务需要的计算资源增加，导致需要卸载到停车单元执行的任务增多，因此上传率上升.当任务所需计算资源继续增加时，在每个任务分配到的资源一定的情况下，任务执行时间不断延长，导致任务无法在容忍值内完成，因此上传率降低.

7 结束语

针对城市范围内停放车辆分布广，数量庞大且长时间停放的特点，本文提出停车边缘计算的思想，把道路两边的停放车辆组织成停车簇，停车簇充当天然的边缘计算服务器，执行周围移动车辆卸载的任务.本文分析了任务的完成时间，并采用改进的SAC算法进行任务调度，以最大化完成任务的数量.将来的工作中，将引入深度学习方法，进一步优化任务调度的性能.