面向停车合作基于深度强化学习的车辆任务卸载_王振川.pdf

小 型 微 型 计 算 机 系 统 ：年 月 第 期 收稿日期：收修改稿日期：基金项目：天津市自然科学基金项目（，）资助；国家自然科学基金项目（，）资助；天津市企业科技特派员项目（）资助 作者简介：王振川，男，年生，硕士研究生，研究方向为车联网和深度学习；花季伟（通讯作者），男，年生，博士，讲师，研究方向为物联网；朱金奇，女，年生，博士，教授，研究方向为移动计算、车载网络和网络安全；孙麒惠，女，年生，硕士研究生，研究方向为车联网和边缘计算；郑 敏，女，年生，硕士研究生，讲师，研究方向为电子信息技术、通信技术；李云龙，男，年生，硕士研究生，副教授，研究方向为自动化控制技术面向停车合作基于深度强化学习的车辆任务卸载王振川，花季伟，朱金奇，孙麒惠，郑 敏，李云龙（天津师范大学 计算机与信息工程学院，天津）（天津中德应用技术大学 智能制造学院，天津）：摘 要：针对路边基础设施受损或失效情况下卸载任务无法被执行的状况，提出令拥有丰富计算资源的路边停放车辆彼此合作，执行车联网中移动车辆产生的计算密集型任务 在把一条道路的路边停放车辆组织成停车簇后，首先分析各卸载任务所需最佳资源量，接着提出基于深度强化学习（，）的计算任务分块卸载算法，将任务划分为多个子任务后由多个停放车辆并行执行，以最小化任务执行延迟和执行任务能耗开销构成的总成本 大量仿真结果表明，本文所提算法的任务执行完成率大大高于其他对比算法，且具有最低的任务执行成本开销关 键 词：边缘计算；停放车辆；任务卸载；深度强化学习中图分类号：文献标识码：文 章 编 号：（），（，）（，）：，（），（），：；引 言近年来，随着无线通信和车辆智能化的迅速发展，车联网（，）技术不断取得重大突破，出现了许多智能车辆，这些车辆大都装备了为用户提供各种各样服务的车载单元 尽管车载单元的计算能力大大增强，但是在变幻莫测的交通环境中，仍然存在着一些车载单元无法及时处理的应用任务，例如基于语音的人车动态交互、实时路况分析识别、增强现实、周围危险车辆识别，等 这些应用任务通常涉及到复杂的计算，被称为计算密集型任务 此外，产生的应用任务往往具有时延限制，需要实时获得处理结果 车载单元计算能力不足，存储容量有限的特点严重影响了车辆的服务能力，从而影响驾驶者的驾驶体验和车辆的安全性 云计算通常可以为用户提供快速且安全的数据服务和存储，车辆通过访问云计算平台来使用网络上的庞大计算资源与数据中心，突破了车辆原本有限的计算和存储限制 然而，将数据传输到数据中心再返回执行结果会产生较大的传输时延，因此云计算虽然拥有足够的计算资源但是仍无法解决时延限制的问题车辆边缘计算（，）将边缘计算技术（，）引入车联网，成为解决上述问题的可行途径 通过将具有强大计算能力和存储功能的服务器放置在道路边缘，车辆产生的计算密集型任务可以卸载到附近的边缘服务器执行，既避免了本地资源容量不足的缺陷，又减小了任务的执行时延 研究表明，大大增强了车辆的服务能力，目前，大部分已有 相关研究认为边缘服务器仅部署于车联网专用基础设施路侧单元（，）附近，且任务卸载的实现均建立在这样的架构之上 然而，这种边缘服务器部署方式存在以下不足：）建设费用较高，且布局需要契合实际交通场景；）的通信范围有限，难以做到交通道路的全面覆盖；）可能受到意外损坏，所以需要定期检查和维修，以保持正常运行城市范围内，停放车辆众多，这些停放车辆具有计算和存储单元，可以取代实际中部署的边缘服务器，在车联网中执行卸载的计算任务 基于上述事实，本文提出利用停放车辆彼此合作，执行移动车辆产生的计算密集型任务，即把路边停放车辆组织成静态服务节点，多个车辆并行处理任务请求 未被充分利用的停放车辆在路侧单元受损或失效情况下，仍能如实际部署的边缘服务器一样，处理车辆的任务，为车辆用户的应用需求提供计算支持 为此，本文首先把道路上一定范围内的停放车辆组织成停车簇，其次分析停放车辆执行任务的时延和执行能耗，并建立优化模型分析停车簇分配给各卸载任务的最佳资源量 在此基础上，结合深度强化学习（，），提出基于 的任务卸载策略，在尽量降低停放车辆的能耗和任务执行时延的前提下最大化成功执行的任务数量 实验分析表明，相比于其它卸载策略，本文所提策略具有更高的卸载性能 相关工作国内外学者针对 已经进行了大量的研究，并取得了显著成就 目前关于车联网计算任务卸载的研究主要分为两类第 类研究仅使用边缘服务器解决任务卸载问题 如基于单个 服务器不能满足大量的任务卸载需求的情况，张建军等设计了一种多 服务器的联合任务上传方案，当服务器超负荷时通过将任务转发到周围服务器的方式提高任务完成率 文献中作者利用 技术和社会网络同时提升车辆用户的服务质量和服务体验 针对车辆高速移动和车辆拥有的计算资源受限的问题，文献考虑任务卸载成本，利用深度强化学习解决任务卸载问题，最大程度的减小任务执行时延和能耗的综合成本 等提出 中，基础设施 的状态可能在工作和睡眠两种模式间动态切换 作者证明最小化任务的执行时延问题是 难问题，并提出贪婪算法解决该问题 但是边缘服务器的计算资源量并不充足，这类研究的缺点在于当大量车辆应用任务产生时，一些任务在规定的时间内可能无法得到及时处理第 类研究通过资源扩充解决来自车辆用户的任务请求 例如吴振铨等为解决网络边缘服务超负荷的问题，提出了一个基于停放车辆协同的边缘计算任务卸载框架 等提出 云架构来为用户提供强大的存储能力 实验证明基于该体系结构可以获得有效的数据上传、下载以及数据管理服务 在文献 中，作者展示了所设计的雾计算系统，其中移动巴士可以执行路侧单元共享的任务，用于缓解边缘服务器的计算资源瓶颈带来的问题 等人在 中引入一个卸载服务提供商，通过部署的 服务器按需调度停放车辆来处理卸载任务，并研究了有效的工作负载和以用户为中心的效用最大化，以优化任务调度 部分研究提出通过移动车辆辅助执行卸载到边缘服务器上的任务 但是由于受交通状况的影响和车辆的高速移动性，服务器与移动车辆以及移动车辆之间的接触时长动态变化，这使得任务难以被完全共享并影响任务卸载的性能目前也有利用深度神经网络解决 中任务卸载问题的研究，但是假设场景普遍过于简单，且状况空间很小，或者没有考虑到边缘服务器的计算能力有限的问题 本文把未被充分利用的路边停放车辆加入到，并考虑道路上多个车辆同时产生任务的实际情况，建立基于 的任务卸载模型，目的是在尽量降低停放车辆的能耗和任务时延的前提下得到最佳的任务分配方案，并提高任务卸载的性能 系统架构 基本架构本文网络场景如图 所示，包含一条道路上的移动车辆和路边停放车辆，车辆之间通过（，）方式进行数据传输 停放车辆作为天然的边缘计算设备，执行卸载的计算任务 为了让停放车辆彼此协同，并对停放车辆进行有效管理，一条街道上的停放车辆形成停车簇 为降低任务数据传输时延，限制一个停车簇最大长度为 米 对于每个停车簇，选择一辆车作为簇头，簇头位于簇的中间或者两端，确定簇头后，其它剩余车辆作为簇成员 设路边停放车辆的集合为 ，集合中的每个元素标志一辆停放车辆，总数量为 停放车辆成员定期向簇头发送成员信息和状态，比如车辆编号，剩余电量，是否正在执行任务等 簇头根据收到的信息管理成员车辆，维护整个簇结构 簇头同时负责收集本簇所在道路上移动车辆的任务请求，掌管成员车辆和资源的分配 因为簇头随时都有可能开走，令簇头的一个邻居充当备用簇头，用来维持簇头存储的信息副本，以增强簇的鲁棒性移动车辆产生的任务集为 ，每个任务都和一个四元组关联，例如任务表示为（，），个参数分别表示任务大小，任务执行所需资源量（的周期数），任务返回结果大小以及任务的最大容忍时延 另外，根据文献，这 个参数之间的关系可以表示为：（）（）其中，表示任务的计算复杂度，是任务完成结果大小与任务大小的比例，为了简化模型，在本文中假设对所有的计算任务，和 具有相同的值图 系统模型 在图 中，行驶在道路上的智能车辆随机产生计算任务，任务车辆本地终端具有一定的计算和存储能力，但是对于某些本地不能及时完成的任务，需要上传到停车簇执行以满足任务的最大容忍时延需求 此时，任务车辆会将行驶速度、当前所在位置以及自身携带的任务信息发送给其所在范围停车 期 王振川 等：面向停车合作基于深度强化学习的车辆任务卸载 簇的簇头 簇头根据收集到的请求，分析任务需要的最佳资源量，并根据下文描述的基于 的任务卸载策略决定每个任务卸载的最佳位置 当停车簇的空闲车辆不足以执行一个计算任务时，剩余的未执行任务在本地执行，如果得到任务结果所需要的时间超过任务的最大容忍时延，认为任务执行失败 簇的稳定性分析道路上车辆的停放情况是动态变化的，车辆加入和从簇中开走具有随机性 停车簇若为卸载服务提供可靠计算支持，需要保证簇的相对稳定 在本节中，通过建立停车簇中车辆的数量变化的分布函数模型，为本文所提任务卸载方案提供理论支持文献 证明加入和从停车簇中开走的成员数量各自遵循 辆每秒和 辆每秒的泊松过程，设经过时长，加入和开走的车数为（）和（），概率分布为：（）（）！，（）（）（）！，（）则簇中多了 辆成员，即（）（）的概率是：（）（）（）（）（）（）（）！（）（）与公式（）类似，该时长内簇中少了 个成员的概率为：（）（）（）（）（）！（）（）图 停车簇中车辆变化数量的分布函数 图（）描述了经过时间，停放车辆增加数量的分布函数 根据文献，规定 ，即平均每小时有 辆车驶入停车簇，辆车从中开走 图（）描述了经过不同时间，停放车辆减少数量的分布函数，其中 ，根据图 所示，当经过 秒时，簇中增加或者减少 辆车的概率小于，经过 秒时，簇中增加或者减少 辆车的概率小于 因此，停车簇因为成员的变动影响到卸载任务的计算的概率较小，这证明了停车簇成员相对稳定 任务执行成本 任务执行时延对于计算任务，若选择在本地车辆终端执行，则执行时延为：（）为移动车辆的计算能力若不超过任务的最大容忍时延，则此任务可以在本地成功执行，否则应该上传任务数据到停车簇，由停车簇内的多个停放车辆并行执行此任务，以加快任务的执行速度若任务需要卸载，首先应根据此任务获得的资源情况将任务划分为若干子任务，每个子任务的执行时延由 部分组成，分别为数据上传时延，在停放车辆 上的计算时延和结果返回时延，当全部任务子块计算完并且执行结果返回到移动车辆时，任务才算完成，所以任务执行时延取各个任务子块执行时延的最大值 因此，该任务完成时延表示为：（）（）每个任务子块的各部分时延计算如下：（）（）（）其中表示停放车辆 的计算能力，卸载到该车上的任务子块大小为，任务子块所需计算资源总量是，这两个参数可根据 节获得 为产生任务的移动车辆到执行任务的停放车辆 的距离，为任务结果返回时停放车辆 到移动车辆的距离，可通过移动车辆的行驶速度以及初始位置预测得到数据通过车辆之间的存储转发方式递交，子任务在车辆间经过跳后到达停放车辆，计算完成之后经过跳返回任务结果 代表车辆间转发数据的吞吐量，是车辆的传输半径，是移动车辆在停车簇所在道路上的平均运动速率 对于跳数有：（）（）上式中 是停车簇所在街道的车辆密度，通过车辆装备的电子地图可以得到，计算方法类似公式（）停放车辆能耗分析若选择将任务卸载到停放车辆上执行，停放车辆接收任务数据，执行任务和输出返回结果的过程中，均会产生相应的能耗开销，而停放车辆的能耗为所有这 部分能耗之和 对于停放车辆的拥有者，希望在执行任务时尽量降低自己的能耗 并且若停放车辆因为执行任务造成电池能量耗尽，会导致车辆无法启动，造成严重的后果 为此，停放车辆要考虑节能问题给定车辆传输功率，车辆接收功率，任务被停放车辆执行时的的总能耗为：（）（）其中，表示任务的计算能耗系数 任务执行成本任务卸载方案不仅要追求尽可能小的任务完成时延，考虑到停放车辆的电池容量，还要尽量降低执行任务的停放车辆的能耗，因此，将每个任务的执行成本定义为两者的加权之 小 型 微 型 计 算 机 系 统 年和，任务对应的执行成本计算公式为如下：（）（）所以，任务总执行成本为：（）其中 为权重因子，代表此公式