基于BSP计算模型的信号交叉口延误方法

山东科技大学测绘科学与工程学院 朱海川

基于BSP计算模型的信号交叉口延误方法

山东科技大学测绘科学与工程学院 朱海川

针对基于MapReduce计算模型的信号交叉口延误的获取实时性差的问题，给出了以BSP（Bulk Synchronous Parallel，整体同步并行）计算模型实时计算信号交叉口延误的同步并行方法。信号交叉口中心坐标和浮动车数据以邻接表的形式存储，信号交叉口中心坐标为顶点，与之关联的浮动车数据为目的顶点，围绕信号交叉口中心坐标进行迭代计算。结果表明：部署在Hama集群上的基于BSP计算模型的信号交叉口延误方法，具有更高的执行效率，提高了实时性。

BSP计算模型；信号交叉口延误；图结构；浮动车数据；实时性

1.引言

信号交叉口的运行状态评价主要取决于车辆经过交叉口的延误。信号交叉口延误是评价信号交叉口的运行效率和服务水平的重要度量[1]，是智能交通系统用于动态路径诱导、智能导航、路网交通状况实时监测等的重要判断指标[2]，实时的动态交通信息主要来源于浮动车数据，因此在保证精确度和可靠性的前提下利用浮动车数据实时计算信号交叉口延误，是急需解决的重要问题。

对于信号交叉口延误的计算，采用传统的公式计算方法和现场试验方法[3]，这两种方法不仅结果误差较大而且难以大范围实现。对于大量浮动车数据计算信号交叉口延误情况，多采用高吞吐量、扩展性良好等优点的MapReduce模型处理[4]，但是在处理过程中，每次任务迭代处理都是在本地磁盘进行处理的，再以数据复制的方式进行迁移，造成大量时间和网络资源损失，MapReduce计算模型不适用的信号交叉口延误的实时计算[5]。

对于利用大规模浮动车数据进行信号交叉口延误的实时计算，BSP计算模型是一个良好的选择。以浮动车数据为数据源，研究基于BSP计算模型的信号交叉口延误的实现方法[6]，并部署在以BSP计算模型为执行引擎的Hama集群上进行验证。结果表明，基于BSP计算模型的信号交叉口延误方法，减少时间消耗，提高了执行效率，适用于低延迟计算。

2.BSP计算模型的优势

BSP计算模型多适用于由一个master（管理者）和多个相互独立的slave（工作者）实现的并行分布式集群来处理大规模的图论计算、矩阵计算和网络计算任务，BSP计算模型相对于MapReduce计算模型具有以下优势[7]：

（1）执行机制：基于MapReduce的数据处理，通过复制本地磁盘中的数据进行数据传输，而对于BSP模型，数据的处理是通过消息通信的方式交流中间结果，不需要数据复制。

（2）迭代处理：MapReduce计算模型需要多次连续启动才能完成迭代任务，邻接迭代以数据复制的方式处理。BSP计算模型只需一次启动，邻接迭代通过superstep的全局通信完成，有效减少启动次数，减少时间损失，提高迭代效率。

（3）数据分割：基于MapReduce的数据处理虽然不需要专门的数据分割，但是在数据处理的过程造成数据迁移，需要消耗大量时间和网络资源，而BSP的处理仅需一次数据分割，只需要数据的路由地址通信。

3.信号交叉口延误模型

信号交叉口延误是相当复杂的问题，它与信号周期、配时、交通量及随机因素有关。根据最新《城市道路交通管理评价指标体系》对信号交叉口延误定义：车辆驶过信号交叉口延误的实际时间与理想速度驶过的时间之间的差值，对于利用浮动车数据计算信号交叉口延误，获取信号交叉口的影响范围和车辆的畅行速度是非常必要的。

3.1 信号交叉口影响范围确定

车辆在信号交叉口影响区域会受到排队延误、加减速延误和信号控制延误等影响[8]，在进行信号交叉口延误计算之前要确定信号交叉口的影响范围。根据我国城市道路规划规范，文献中对交叉口检测器的预埋距离，以及信号交叉口延误现场试验中对信号交叉口的影响范围l设定为140-180m[9]。

图1 信号交叉口影响范围

信号交叉口影响范围如图1所示。本文设定信号交叉口影响范围l为180m，即以信号交叉口转角缘石曲线端点为计算起点，道路进口道向上游和道路出口道向下游计算，180m为信号交叉口影响范围的距离。

3.2 理想速度确定

利用浮动车数据计算信号交叉口延误需要获取车辆通过信号交叉口时的理想速度，目前各个道路类型的理想速度还没有没有标准值。畅通是车辆在经过信号范围内行驶的状态，车辆通过信号交叉口的畅行速度与在信号交叉口范围内的运行状态有关，信号交叉口范围内的畅行速度v理依据《城市道路规划规范》规定的速度设定，如表1所示。

表1 城市道路设计车速（km/h）

3.3 利用浮动车数据计算信号交叉口延误

浮动车左转或直行通过信号交叉口时，除了行驶信号交叉口影响范围距离l外，还有停车线包围的导流线距离 ，因此在整个信号交叉口范围内浮动车行驶的距离。当浮动车左转或直行时其导流线距离的长度是不同的，如图2所示。

图2 信号交叉口延误示意图

式中：

3.4 基于BSP模型的信号交叉口延误实现

Hama主要是以HDFS（Hadoop Distributed File System，分布式文件系统）为文件存储系统以BSP计算模型为引擎的同步并行分布式集群[10]。数据的加载需要VertexInputReader类，该类定义了以邻接表的形式进行数据加载，解析输入的每一行数据，得到顶点、目的顶点、边的相关信息，所以需要把浮动车、信号交叉口数据以图结构的形式进行组织。令为图数据的顶点ID，为图数据的顶点属性，为目的顶点ID，为目的顶点属性，的组合（自定义）为边权重。数据加载时，每次从HDFS中读取一行数据，master按照顶点的不同执行具体的分配，不同的顶点被master分配到不同的slave上，与之关联的目的顶点和边信息分配与顶点有关。

数据加载完成后，在compute()方法中实现信号交叉口延误的迭代计算。每个迭代都是围绕顶点的运行状态来进行调度、通信和同步的。在compute()方法自定义迭代任务，再结合ZooKeeper提供的障栅同步机制，利用这些信息改变自身的运行状态，达到同步计算的目的，计算流程如图3所示。

图3 计算流程

4.实验验证与分析

在利用浮动车数据计算信号交叉口延误方面，验证基于BSP计算模型的信号交叉口延误计算的表现，是否比基于MapReduce计算模型性能更优，实现环境主要是Hama集群和Hadoop集群。两种集群全部部署在VMware Workstation-11.0虚拟机上，具有统一的网络配置，部署10台机器组成的小集群，一台作为master，其余都为slave，则两种集群的所有机器环境如下：

（1）操作系统：CentOS-6.5；

（2）java运行环境：JDK-7u79；

（3）hadoop运行版本：hadoop-2.6.0；

（4）hama运行版本：apache-hama-0.7.0。

选用2012年03月01日的部分北京市的浮动车数据，187812条浮动车轨迹，72449882个浮动车轨迹点，1856个信号交叉口参与计算，获取信号交叉口平均延误值。表2、3为实验数据明细，存储在HDFS中，图4、图5为数据的运行结果对比图。

从图4、5可以看出，Hama集群和Hadoop集群处理信号交叉口延误的时间随着任务量的增多而增加，并且MapReduce计算模型的执行时间大概是BSP计算模型的执行时间的5倍，Hama集群和Hadoop集群处理信号交叉口延误的任务时间随着slave的增多而减少，Hama集群执行时间的减少速度更快。

表2 不同容量的实验数据明细

表3 不同slave的实验数据

图4 不同容量数据的运行时间对比

图5 不同slave的数据运行时间对比

5.结论

通过部署在Hama集群上的基于BSP计算模型的信号交叉口延误方法的探讨，以实现利用大量浮动车数据计算信号交叉口延误。实验表明：基于BSP计算模型的信号交叉口延误方法的同步并行化实现，不仅具有良好的可扩展性，而且任务的执行时间相对较少，提高了利用大量浮动车数据计算信号交叉口延误的效率，提高了实时性。但是对于巨大浮动车数据源或者大规模集群实现的信号交叉口延误还需要进一步的研究。

[1]吴佩莉,刘奎恩,郝身刚,张全新,谭毓安.基于浮动车数据的快速交通拥堵监控[J].计算机研究与发展,2014,(01):189-198.

[2]刘广萍,裴玉龙.信号控制下交叉口延误计算方法研究[J].中国公路学报,2005,18(1):104-108.

[3]张希瑞,方志祥,李清泉,等.基于浮动车数据的城市信号通行能力时空特征分析[J].地球信息科学学报,2015,17(3):336-343.

[4]余洋.云计算环境下的大样本浮动车数据处理关键技术研究[D].武汉:武汉大学,2010.

[5]潘巍,李战怀,伍赛,等.基于消息传递机制的MapReduce图算法研究[J].计算机学报,2011,34(10):1768-1784.

[6]孙玲,李静.利用浮动车回传数据的信号交叉口延误估计[C]//The International Conference on Power Electronics and Intelligent Transportation System.2010.

[7]徐淑,陆朝俊,陈昌生,等.基于BSP的并行事务处理模型[J].计算机研究与发展,2001,38(11):1399-1404.

[8]邵长桥,荣建,任福田,杨振海.停车延误、引道延误和控制延误关系研究[J].中国公路学报,2002,(04):93-96.

[9]谭祥爽,王静,宋现锋,等.基于浮动车数据的路口探测方法[J].地理与地理信息科学,2015,31(5):34-38.

[10]Seo S,Yoon E J,Kim J,et al.HAMA: An Efficient Matrix Computation with the MapReduce Framework[C]// IEEE Second International Conference on Cloud Computing Technology and Science.IEEE, 2010:721-726.

朱海川（1989－），男，河南商丘人，研究生硕士。