孙麒惠，朱金奇，花季伟，王振川，郑 敏，魏艳敏
(天津师范大学 计算机信息工程学院，天津 300387)
将移动边缘计算(mobile edge computing，MEC)技术引入车联网，利用边缘服务器为车辆提供边缘计算服务，称为车辆边缘计算(vehicular edge computing，VEC)[3]，但边缘服务器的资源有限[4]，当大量车辆任务产生时，边缘服务器无法为车辆提供足够的计算资源，特别是在交通流量密度很高的情况下。
受城市中停放车辆高密集分布且具有大量闲置计算资源的启发，我们提出让停放车辆辅助边缘服务器，执行移动车辆产生的计算任务。为此，首先把路边停放车辆组织成停车簇，停车簇作为虚拟边缘服务器参与任务的卸载执行，从而极大缓解边缘服务器资源受限的问题。其次，提出自上而下的任务优化分配方案，把任务合理的分配到各停车簇和边缘服务器，以最小化卸载任务总的完成时间。对于分配到各停车簇的任务，在考虑停放车辆的能耗、收益以及任务完成延迟的基础上，我们进一步提出簇内任务分配算法，为各卸载任务选择最佳的停放车辆。通过上述双重任务分配策略，既保证了卸载任务的服务质量，又使停放车辆的收益最大化，同时降低停放车辆的能耗开销。仿真实验结果表明，与其它几种分配策略相比，本文所提任务分配方法具有较高的性能。
已有VEC任务卸载相关研究主要分成两类，其中大部分是通过集中式方式实现任务的分配，即存在一个控制器(或服务器)用来做全局任务分配决策。例如文献[5]提出了一种异构感知的任务分配方案，该方案可以将相互依赖的任务映射到具有异构硬件和运行环境的设备上，从而共同降低任务延迟和能耗。文献[6]中，作者基于半马尔可夫决策过程(SDMP)提出了车辆云中的集中式任务卸载和资源分配问题，目的是使车辆的总报酬最大化。文献[7]中，作者提出一种新任务调度模型为每个请求的任务分配服务器，从而使总响应时间最小化。文献[8]提出在软件定义网络中，设计性能增强型路由协议管理车辆网络资源，控制器根据车辆的拓扑结构在基站间分配信息。文献[9]分析了边缘计算环境下的车辆通信模式选择,作者根据K-means聚类算法和非支配排序遗传算法得出最优任务卸载决策。文献[10]中，道路上的所有停放车辆中选择一个中心车辆执行的任务调度算法，为各个任务分配计算资源以便任务及时执行并保证车辆的使用率最大化。然而集中式方案通常没有考虑各个边缘设备在执行边缘计算中各自利益的问题。
考虑到依赖于中央决策者进行任务分配方式的不足，部分研究采用分布式进行任务分配。比如文献[11]中提出了一种知识驱动(KD)的服务卸载框架，作者着眼于边缘节点类型，采用A3C算法在边缘节点上训练每种服务的卸载决策模型，然后将其分发给车辆。车辆在运行服务时，执行异步在线学习使时延最小。文献[12]中车辆能够在卸载计算任务时了解其相邻车辆的卸载延迟性能，在此基础上设计了一种自适应学习任务卸载算法，以最小化平均卸载延迟。文献[13]中作者提出了一种利用先验分布和统计信息引入贝叶斯推理的深度Q网络算法，其中车辆动态选择候选服务器来执行任务，最大程度地减少了延迟和能耗的总成本。文献[14]提出了一个基于边缘服务器和车载服务器合作工作的任务卸载策略，在安全切换交互协议的前提下使任务卸载算法降低能耗同时减少卸载时间。针对非车联网的边缘计算问题，文献[15]中，作者将资源分配问题描述为双重拍卖游戏，采用博弈方法进行建模获得最优资源价格和设备资源需求。文献[16]中作者开发了一种任务分配方案，允许非合作的边缘设备使用动态激励来挑选各个设备收益最大的任务,然而该方案没有做出全局最优的任务调度。
综上所述，集中式方式主要以满足卸载任务的需求为目标求解最优解，而分布式方式则是以满足终端设备的需求如收益等为设计目标。目前来看，综合考虑卸载任务和移动终端设备需求的研究很少，为此，我们从同时协调上述两个优化目标出发，寻求满足条件的最优解。
2.1 系统框架
本工作中任务卸载的基本架构如图1所示，主要包括一个基站、边缘服务器、基站范围内的停车簇以及移动车辆4部分。
图1 系统架构
(1)移动车辆(mobile vehicle)：是道路上行驶的智能车辆，这些车辆产生各种应用服务，如网络游戏、智能驾驶应用、增强现实等。
(2)基站(base station)：移动车辆产生的任务卸载请求均需要发送给基站，基站为所有卸载任务分配具体执行任务的边缘服务器、停车簇和计算资源。
(3)边缘服务器(edge server)：边缘服务器位于基站附近，通过有线网络可以直接快速的与基站进行数据交换。
(4)停车簇(parking cluster)：一个基站通信范围内有多辆停放车辆，位于同一条街道上的停放车辆被组织成停车簇。停车簇充当虚拟边缘服务器，辅助边缘服务器，为移动车辆提供任务计算和数据存储服务。
2.2 任务模型
2.3 停车簇的构建
典型的停车簇如图2所示，构建过程描述如下：首先，各道路上的车辆确定各自的地理位置，然后根据各自的地理位置确定其在停车簇中的角色。令道路中间的停放车辆作为簇头，如图中的H，道路上的其它停放车辆(M1～M11)充当簇成员。
图2 停车簇
簇头管理维护整个停车簇，包括簇内资源的管理，为具体的任务卸载分配车辆成员，以及处理车辆离开和加入簇的事件等。簇内车辆成员周期性向簇头发送信息，包括其ID号、位置以及剩余电量、剩余资源等。考虑到簇头车辆在车主的控制下随时可能离开，我们将距离簇头最近的停放车辆作为备用簇头，如图中的SH，当簇头离开，需要簇头将信息传输到备用簇头并令新的簇头重新管理停车簇。
2.4 停车簇调查
我们提出的策略基于路边停放车辆状况，因此路边停放车辆的分布以及稳定性是本策略实现的关键，本小节通过调研分析车辆的停放状况。文献[17]对美国普吉特海湾地区现有的停车位使用情况进行调查发现，车位具有长时间连续占用的特点，地面停车场的平均利用率约占78%，其中一半以上的停车场占用率接近100%。文献[18]对加拿大蒙特利尔市5500平方公里的停放车辆状况进行统计分析，每天停放车辆的数量约为3万，平均停车事件6.1万次起，平均停车时间将近6.95 h。报告文献[19]中对深圳道路的状况进行调查显示，全市停车泊位密度为0.21万个/平方公里。文献[20]中调查了哈尔滨市商圈停车场现状，发现白天停车位利用率维持在80%以上且相对稳定。尽管上述提供的停车报告仅针对几个城市或区域，但大范围停车、长时间停车、高密度路边停车在每个城市都很常见，由此我们得出停车簇的结构具有一定的稳定性。现有的城市交通车辆变化很大，街道上的车辆甚至每秒钟都会快速变换位置，尤其在交通高峰期。但停放车辆会静止数小时，且每辆车的静止时间远长于行驶时间。基于上述特征我们得出：与移动车辆相比，城市中停放车辆辅助任务卸载，具有很强的实用性。
2.5 基本思想
对于道路上移动车辆生成的任务，可以通过本地或服务器两种方式执行。服务器分为两种类型：基站旁的边缘服务器和由停车簇构成的虚拟边缘服务器。如果任务的本地完成时间小于其最大容忍响应时间，则将在本地执行，否则应将任务卸载到服务器。在卸载时，首先，生成任务的车辆向基站发送请求消息，请求消息包含其ID和具体任务信息。基于收集到的任务信息，根据下面提出的自上而下任务调度算法为所有请求的任务分配服务器和计算资源，之后基站将资源分配要求发送给服务器节点。对于分配给停车簇的任务，簇头根据簇内任务分配算法确定执行子任务的具体停放车辆，同时将结果告知基站。基站再将具体卸载任务的最终结果通知给产生任务的移动车辆，最后实现并行计算。
3.1 任务卸载分析
当任务Ti需要被卸载到服务器j(j∈L) 上时，完成时间分为两部分：产生任务Ti的移动车辆到服务器j的传输数据时间和执行任务所花费的时间，由于任务输出结果的传输时间很小所以这里忽略不记。任务Ti的完成时间表示为
(1)
其中，ti,j是完成时间，ttran,ij是任务数据传输时间，ri,j是服务器j分配给任务Ti的资源量。对于传输时间ttran,ij， 若任务Ti被卸载到基站附近的边缘服务器，其值为
(2)
其中，c(Vi,S)表示从移动车辆到该基站的吞吐量，根据香农定理，其值为
(3)
其中，B代表信道带宽，Pv是车辆传输功率，g0为路径损耗常数，ξ(Vi,S)和d分别是产生任务的车辆到边缘服务器的信道功率增益和距离，β表示路径损耗指数，I是干扰的最大接收功率，σ2是高斯噪声。
若j为停车簇，任务将被分割成多个子任务，由若干停放车辆成员并行执行。此时为了计算ttran,ij， 我们首先检查产生任务Ti的车辆是否可以直接与停车簇j通信。如果可以
(4)
其中，cvel是车对车通信的吞吐量，Lcj是停车簇j的长度，R是车辆的通信范围，si/2cvel表示由一跳数据传输引起的平均任务传输延迟，Lcj/2R表示向具体停放车辆传输数据的平均通信跳数。
否则任务数据必须在基站的帮助下传输到停车簇j，此时ttran,ij为
(5)
(6)
其中，PB是基站传输功率，ξ(S,Vp)和d′分别是基站到停放车辆p的信道功率增益和距离。
3.2 自上而下的任务调度分析
道路上行驶的智能车辆可能会同时生成任务，产生计算资源的竞争，为此需要合理分配计算节点和资源。任务的分配由基站执行，此外，基站还同时负责维护深度学习模型的参数等。
本文将移动车辆产生的任务调度问题描述为一个优化问题，优化的目的是最小化任务总的完成时间，该优化问题表示为
(7)
s.t.
zi,j∈{0,1}, ∀i∈T,j∈L
(8)
(9)
(10)
(11)
ri,j≤rmax, ∀i∈T,j∈L
(12)
约束式(8)中，当任务Ti被分派给服务器j时，zi,j的值为1，否则为0。约束(9)确保每个任务只能卸载到一个服务器上执行。约束(10)保证每个任务都在最大容忍响应时间内完成。ri,j是服务器j分配给任务Ti的资源量，最大资源量约束为rmax。式(11)保证服务器分配给任务的计算资源总量不超过其拥有的资源Rj。条件(12)是对每个任务计算资源量的约束。
该问题涉及两个问题：资源分配和执行任务具体位置的选择。分配给每个任务的计算资源是不高于rmax的任何值，此外和基站直接连接的边缘服务器以及周围的停车簇均能执行卸载任务，该调度问题是NP难问题[21]。为了解决该优化问题，我们把此问题转化为两个子问题，通过分别解决两个子问题解决问题P。首先假设执行任务的服务器已经确定，此时P转化为
(13)
s.t.
(14)
(15)
(16)
在确定资源分配后，下一步需要选择任务卸载的最佳服务器节点。此时根据式(1)可得ti,j， 问题P简化为子问题P2，只需求解zi,j。
该子问题P2是0-1整数规划问题，我们采用分支定界算法[23]解决。
通过求解资源分配和服务器节点选择两个子问题，最终解决了自上而下任务调度的优化问题。
3.3 簇内任务分配分析
根据前一节优化得到的占用资源大小，将分配给停车簇的任务分为不同的子任务，由多个停放车辆并行执行，以加快任务的执行速度。我们令簇头负责为子任务分派具体的停放车辆，从而尽可能满足停放车辆的能耗和收益需求。以停车簇j为例，由于上一小节已经为卸载到j上的每个任务确定了最佳资源，因此执行任务Ti的停放车辆数量为
(17)
为了簇头合理的分配子任务，定义Ti的每个子任务卸载到停放车辆p的惩罚函数为
(18)
(19)
其中，ttran,i′p是停放车辆p接收子任务数据花费的时间，根据式(4)或式(5)获得，ci/nilv是执行子任务的时间。
在具体分配停放车辆时，要考虑车辆的电池能量状态，尽量降低停放车辆的能量消耗。停放车辆p执行子任务消耗的能量表示为
(20)
其中，Pv是车辆传输功率，ttran,i′p是传输时间，ei′,p是在停放车辆p上运行子任务Ti′所消耗的能量，γ是文献[24]中与任务执行能量消耗相关的系数。
基于执行子任务固有奖励，时间惩罚函数以及车辆能量消耗，定义停放车辆p执行子任务的效用函数为
(21)
其中，ri是完成任务Ti所获得奖励，则停放车辆完成子任务获得的奖励为ri/ni，Emin是保证车辆能够正常驾驶的最小能量值。停放车辆p执行完Ti′子任务后剩余能量值Ep,remain为
Ep,remain=Ep-Ei′,p
(22)
其中，Ep是停放车辆p的当前能量值。
簇头分配任务时，需要尽可能地使停放车辆的效用最大化，算法1显示了停车簇中具体分配子任务的伪代码：
算法1：Allocation of parked vehicles
(1)arrange all subtasks in queueZ；
(2)record all parking vehicles asP;
(3)for each subtaskTi′inZ
(5) for each idle vehiclepinPdo
(6) calculateui′,pusing Equation(21);
(7) ifumax (8)umax=ui′,p; (9) record vehiclepask； (10) else (11) continue; (12) end if (13) end for (14) assign subtaskTi′to parking vehiclekfor execution; (15) remove elementkfrom setP; (16)end for 我们利用c++进行实验模拟，假设一个基站覆盖区域内有5条纵横交错的街道，平均每条街道长900 m，该区域有100～500辆车随机移动。车辆传输半径R为250 m，车辆的总能量为3 W，Emin设置为车辆总能量的30%。对于停放车辆的当前能量值在总能量值的60%～100%之间随机选择。每辆车拥有的资源设置为0.4 GHz，基站拥有的资源设置为8 GHz。此外，设置无干扰情况[25]，同一条街道上的停放车辆被组织成一个停车簇，根据文献[11]中城市道路停车调查，默认设置停车簇中的停车分布符合文献所述中等密度分布。令移动车辆以60%的概率产生任务，任务参数设置如下：计算资源量ci为1000 cycles/bit，数据大小si为 [2,4] Mb， 任务的最大容忍响应时间为[4,8] s。 其它默认参数见表1。 表1 默认参数 我们将本文所提策略与以下3种策略进行比较： (1)本地执行(local computing，LC)：移动车辆产生的计算任务总是全部由产生任务的车辆本地执行。 (2)自上而下任务分配(top-down task assignment，TDTA)：根据3.2节所提出的自上而下的任务调度，把任务分配到各停车簇和边缘服务器，对于在停车簇执行计算的任务，停车簇根据任务分配到的计算资源随机给各任务分配停放车辆。 (3)停车簇内任务分配(parking cluster task allocation，PCTA)：车辆产生的所有任务随机分配资源及服务器节点，对于分配到停车簇的任务，使用本文提出的簇内子任务分配算法进行分配。 性能评估指标为任务完成率、任务完成时间和停放车辆效用，任务完成率即成功完成任务的数量与产生的总任务数量之比，任务完成时间指的是平均完成一个任务所花费的时间，其中执行失败的任务完成时间统一记为9 s； 4.2.1 任务数量的影响 为了分析任务数量对各种策略性能的影响，假设基站覆盖区域内有4个停车簇，我们设置不同的移动车辆数量，即将任务数量从100逐渐增加到350个，此时各调度策略的性能变化如图3、图4和图5所示。 图3 完成率随任务数量的变化 图4 任务完成时间随任务数量的变化 图5 车辆效用值随任务数量的变化 图3显示，TDTA和所提任务分配策略在任务数量为100时能够全部完成，这是因为基站附近服务器的可用资源充足，且在任务数量较少时停车簇具有的资源足够卸载任务使用，为此每个卸载的任务可以分配到足够的计算资源来执行任务。随着任务数的增加，除LC外，其它3种分配策略的完成率均呈下降趋势，这是因为任务总数增加，而边缘服务器和停车簇拥有的计算资源却保持不变，因此每个任务所分配的资源量降低造成任务完成率下降。其中，本文提出的策略总是具有最大的完成率。这是因为我们不但为每个任务选择合理的停车簇，且为每个卸载到停车簇的任务选择最佳的执行车辆，保证了任务的服务质量。图4表明，随着任务数量的增加，TDTA、PCTA和本文所提策略的任务平均完成时间都在增加，但均低于LC策略。本文所提策略性能最好，其次是TDTA，说明自上而下的任务调度可以最大限度地减少任务的总完成时间，同时尽可能地完成每个任务的计算请求。图5显示，随着任务数量的增加，TDTA、PCTA和本文所提策略的停放车辆效用值均减小，而本文所提策略的车辆效用值始终保持最大。由于LC中的任务只能在本地执行，本地资源非常有限，一些复杂任务无法处理，因此LC的完成率最低、任务的平均完成时间最高。综上所述，随着任务数量增加，本文所提策略不仅性能最高，且能保证停放车辆的效用值最大化。 4.2.2 计算资源需求的影响 本组实验研究在任务数量为200、停车簇数量为4的情况下，计算资源需求变化对策略性能的影响。将计算资源从600 cycles/bit变化到1600 cycles/bit，各种策略的性能变化如图6、图7、图8所示。 图6 完成率随计算资源需求的变化 图7 任务完成时间随计算资源需求的变化 图8 车辆效用值随计算资源需求的变化 如图6和图7所示，随着计算资源需求越来越大，4种分配策略的完成率呈下降趋势，完成时间呈上升趋势。计算资源需求的增加导致完成任务所需资源极大增加，而移动车辆的计算资源非常有限，因此LC完成率的下降趋势以及任务平均完成时间的上升趋势尤为明显。对于另外3种策略，可以将任务卸载到边缘服务器上，减少了任务的完成时间，提高了完成率，而由图可看出我们所提的策略具有最大完成率以及最小任务完成时间。如图8所示，本文所提策略、TDTA和PCTA的车辆效用值随着计算资源需求的增加而降低。原因是执行任务所需的计算资源增加，导致时间和能耗都增加。当任务所需计算资源继续增加时，任务执行时间和能量消耗不断增大，导致任务无法卸载到停放车辆完成。本文所提策略保证了停放车辆执行卸载任务的完成时间和能量消耗最小，以及停放车辆收益最大，从而拥有停放车辆的最大效用值。 4.2.3 停车簇数量的影响 本组实验主要研究停车簇数量对4种任务分配方案完成率以及车辆效用值的影响，实验中默认任务数量仍保持200不变。 当只有一个停车簇时，图9中的完成率较低，这是由于停放车辆较少，不足以支撑足够多的任务卸载，但此时本文所提策略、TDTA和PCTA几种卸载性能仍旧比LC的完成率要高。如图9和图10所示，随着停车簇数量的逐渐增多，路边停放车辆的可利用资源量增加，除LC外的其它几种策略完成率和车辆效用值均呈上升趋势，充分验证了利用路边停放车辆协助完成任务卸载可提高任务分配性能。LC本地执行策略和停放车辆的数量无关，因此不随停车簇数量变化而变化。通过对比4种方案性能随停车簇数量的变化，可见本文所提卸载策略的完成率和车辆效用值始终保持最大。 图9 完成率随停车簇数量的变化 图10 车辆效用值随停车簇数量的变化 本文所提分配策略始终保持性能最优，这是因为所提策略不仅利用具有丰富资源的停放车辆执行卸载任务。在任务分配方面，首先对资源和服务器节点的选择进行了合理调度，又从停放车辆自私性的角度保证了停放车辆的效用值最大化。 本文把路边停放车辆组织成停车簇，拥有充分且未被充分利用资源的停车簇可以协助基站附近的服务器，参与任务的卸载执行，从而极大缓解边缘服务器的资源限制。在此基础上，提出了自上而下的任务调度和停车簇内部分配策略来解决车辆边缘计算中任务低完成延迟以及停放车辆低能耗且高收益的任务分配需求。仿真实验结果表明了本文所提策略的有效性。下一步工作将考虑引入深度学习的方法对调度性能进行优化，并考虑车辆移动速度等其它因素对车联网环境的影响。4.1 实验设置
停放车辆效用是从车辆执行任务所获利出发的一个关于时间、能耗和固有奖励的函数值，其中奖励和任务数据大小成正比。4.2 实验分析
