移动边缘计算架构下面向公共交通车载监控服务的虚拟功能链部署理论与算法研究

The informatization and intelligentize of real-time surveillance on public transportation is one of the emergent requirements by the development of public transportation. Deploying the real-time surveillance on public transportation with virtual function chain in mobile edge computing, could meet the demands of the latency-sensitive and computation-intensive surveillance data processing service. This project focuses on the low latency requirement of the real-time surveillance on public transportation, and studies the deploying strategies for multi-module surveillance services by exploring virtual function chain placement and expansion algorithms to complete the deployment of low latency real-time surveillance on public transportation. Firstly, aiming at the minimization of the total service delay, this project will build a virtual function chain mapping model based on public transportation mobility traces with temporal-spatial features. Then, following the divide-and-mapping strategy, this project will investigate the graph partition theories and hypergraph optimization methods, and propose a spectral-clustering based region partition algorithm and a library-reuse-support virtual function chain mapping algorithm. Finally, towards burst of workload under the congestion scenarios, e.g., traffic jam, rush hour, this project will design a min-cost network flow based fast function chain expanding algorithm, to guarantee the low latency of surveillance service on public transportation. The prospective theories and algorithms of this project would promote the practical applications of mobile edge computing architecture in surveillance on public transportation.

公共交通车载实时监控的信息化、智能化是公共交通发展的迫切需求，在新兴的移动边缘计算架构下，以虚拟功能链的形式部署公共交通车载实时监控服务，可满足时延敏感、计算密集的监控数据分析计算的要求。本项目针对公共交通车载实时监控服务的低延时需求，对移动边缘计算架构下监控服务的部署方法进行理论分析和研究，通过探索虚拟功能链的放置和扩展算法实现低延时的公共交通车载实时监控服务的部署。首先，以最小化服务总时延为目标，基于公共交通车辆移动轨迹的时空规律性，建立虚拟功能链映射理论模型；其次，采用先划分再映射的思路，研究图分割理论及超图优化方法，提出基于谱聚类的区域划分算法及支持库重用的虚拟功能链映射算法；最后，针对交通拥塞、客流高峰等突发场景下的计算负载激增，设计基于最小代价网络流的虚拟功能链快速扩展算法，为车载监控服务提供低时延保障。本项目预期研究成果将推进移动边缘计算架构下公共交通车载实时监控的实际应用。

公共交通车载实时监控可确保公共交通车辆内部的实时安全，及时发现公共交通车辆运行中潜在的危险并进行预警，其信息化、智能化是公共交通发展的迫切需求。以移动边缘计算架构为支撑、采用多模块虚拟功能链形式部署公共交通车载实时监控服务，可满足其时延敏感、计算密集的监控数据分析计算的要求。本项目对移动边缘计算架构下的多模块、低延时、具有时空规律动态变化的服务部署进行了理论分析和研究。主要研究分为三个部分：1）根据车载实时监控服务的需求和特性，抽象出以最小服务总时延为目标、支持库重用的虚拟功能链映射问题，并分解为两个优化子问题；2）针对两个子问题分别提出过分解再聚合算法以及最优区域划分下的虚拟功能链部署算法，并证明了在树型拓扑的物理网络中虚拟功能链部署存在多项式时间下的最优算法；3）考虑实际应用中的交通拥塞、客流高峰等突发场景，设计了基于延迟感知的目标选择策略、协作式负载均衡策略、以及基于网络流的虚拟功能链快速扩展算法，为实际应用中解决公共交通车载实时监控服务的部署给出完整的解决方案。本项目完成了预定研究目标，在国内外高水平学术期刊和会议上发表了相关研究成果，并申请国家发明专利三项。项目建立起一套完整的公共交通场景下的车载实时监控服务部署算法研究，涵盖模型抽象、理论研究及算法设计，为移动边缘计算在公共交通场景下的应用提供理论支撑。