基于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－），男，河南商丘人，研究生碩士。