基于BSP計(jì)算模型的信號(hào)交叉口延誤方法

山東科技大學(xué)測(cè)繪科學(xué)與工程學(xué)院 朱海川

基于BSP計(jì)算模型的信號(hào)交叉口延誤方法

山東科技大學(xué)測(cè)繪科學(xué)與工程學(xué)院 朱海川

針對(duì)基于MapReduce計(jì)算模型的信號(hào)交叉口延誤的獲取實(shí)時(shí)性差的問題，給出了以BSP（Bulk Synchronous Parallel，整體同步并行）計(jì)算模型實(shí)時(shí)計(jì)算信號(hào)交叉口延誤的同步并行方法。信號(hào)交叉口中心坐標(biāo)和浮動(dòng)車數(shù)據(jù)以鄰接表的形式存儲(chǔ)，信號(hào)交叉口中心坐標(biāo)為頂點(diǎn)，與之關(guān)聯(lián)的浮動(dòng)車數(shù)據(jù)為目的頂點(diǎn)，圍繞信號(hào)交叉口中心坐標(biāo)進(jìn)行迭代計(jì)算。結(jié)果表明：部署在Hama集群上的基于BSP計(jì)算模型的信號(hào)交叉口延誤方法，具有更高的執(zhí)行效率，提高了實(shí)時(shí)性。

BSP計(jì)算模型；信號(hào)交叉口延誤；圖結(jié)構(gòu)；浮動(dòng)車數(shù)據(jù)；實(shí)時(shí)性

1.引言

信號(hào)交叉口的運(yùn)行狀態(tài)評(píng)價(jià)主要取決于車輛經(jīng)過交叉口的延誤。信號(hào)交叉口延誤是評(píng)價(jià)信號(hào)交叉口的運(yùn)行效率和服務(wù)水平的重要度量[1]，是智能交通系統(tǒng)用于動(dòng)態(tài)路徑誘導(dǎo)、智能導(dǎo)航、路網(wǎng)交通狀況實(shí)時(shí)監(jiān)測(cè)等的重要判斷指標(biāo)[2]，實(shí)時(shí)的動(dòng)態(tài)交通信息主要來源于浮動(dòng)車數(shù)據(jù)，因此在保證精確度和可靠性的前提下利用浮動(dòng)車數(shù)據(jù)實(shí)時(shí)計(jì)算信號(hào)交叉口延誤，是急需解決的重要問題。

對(duì)于信號(hào)交叉口延誤的計(jì)算，采用傳統(tǒng)的公式計(jì)算方法和現(xiàn)場(chǎng)試驗(yàn)方法[3]，這兩種方法不僅結(jié)果誤差較大而且難以大范圍實(shí)現(xiàn)。對(duì)于大量浮動(dòng)車數(shù)據(jù)計(jì)算信號(hào)交叉口延誤情況，多采用高吞吐量、擴(kuò)展性良好等優(yōu)點(diǎn)的MapReduce模型處理[4]，但是在處理過程中，每次任務(wù)迭代處理都是在本地磁盤進(jìn)行處理的，再以數(shù)據(jù)復(fù)制的方式進(jìn)行遷移，造成大量時(shí)間和網(wǎng)絡(luò)資源損失，MapReduce計(jì)算模型不適用的信號(hào)交叉口延誤的實(shí)時(shí)計(jì)算[5]。

對(duì)于利用大規(guī)模浮動(dòng)車數(shù)據(jù)進(jìn)行信號(hào)交叉口延誤的實(shí)時(shí)計(jì)算，BSP計(jì)算模型是一個(gè)良好的選擇。以浮動(dòng)車數(shù)據(jù)為數(shù)據(jù)源，研究基于BSP計(jì)算模型的信號(hào)交叉口延誤的實(shí)現(xiàn)方法[6]，并部署在以BSP計(jì)算模型為執(zhí)行引擎的Hama集群上進(jìn)行驗(yàn)證。結(jié)果表明，基于BSP計(jì)算模型的信號(hào)交叉口延誤方法，減少時(shí)間消耗，提高了執(zhí)行效率，適用于低延遲計(jì)算。

2.BSP計(jì)算模型的優(yōu)勢(shì)

BSP計(jì)算模型多適用于由一個(gè)master（管理者）和多個(gè)相互獨(dú)立的slave（工作者）實(shí)現(xiàn)的并行分布式集群來處理大規(guī)模的圖論計(jì)算、矩陣計(jì)算和網(wǎng)絡(luò)計(jì)算任務(wù)，BSP計(jì)算模型相對(duì)于MapReduce計(jì)算模型具有以下優(yōu)勢(shì)[7]：

（1）執(zhí)行機(jī)制：基于MapReduce的數(shù)據(jù)處理，通過復(fù)制本地磁盤中的數(shù)據(jù)進(jìn)行數(shù)據(jù)傳輸，而對(duì)于BSP模型，數(shù)據(jù)的處理是通過消息通信的方式交流中間結(jié)果，不需要數(shù)據(jù)復(fù)制。

（2）迭代處理：MapReduce計(jì)算模型需要多次連續(xù)啟動(dòng)才能完成迭代任務(wù)，鄰接迭代以數(shù)據(jù)復(fù)制的方式處理。BSP計(jì)算模型只需一次啟動(dòng)，鄰接迭代通過superstep的全局通信完成，有效減少啟動(dòng)次數(shù)，減少時(shí)間損失，提高迭代效率。

（3）數(shù)據(jù)分割：基于MapReduce的數(shù)據(jù)處理雖然不需要專門的數(shù)據(jù)分割，但是在數(shù)據(jù)處理的過程造成數(shù)據(jù)遷移，需要消耗大量時(shí)間和網(wǎng)絡(luò)資源，而BSP的處理僅需一次數(shù)據(jù)分割，只需要數(shù)據(jù)的路由地址通信。

3.信號(hào)交叉口延誤模型

信號(hào)交叉口延誤是相當(dāng)復(fù)雜的問題，它與信號(hào)周期、配時(shí)、交通量及隨機(jī)因素有關(guān)。根據(jù)最新《城市道路交通管理評(píng)價(jià)指標(biāo)體系》對(duì)信號(hào)交叉口延誤定義：車輛駛過信號(hào)交叉口延誤的實(shí)際時(shí)間與理想速度駛過的時(shí)間之間的差值，對(duì)于利用浮動(dòng)車數(shù)據(jù)計(jì)算信號(hào)交叉口延誤，獲取信號(hào)交叉口的影響范圍和車輛的暢行速度是非常必要的。

3.1 信號(hào)交叉口影響范圍確定

車輛在信號(hào)交叉口影響區(qū)域會(huì)受到排隊(duì)延誤、加減速延誤和信號(hào)控制延誤等影響[8]，在進(jìn)行信號(hào)交叉口延誤計(jì)算之前要確定信號(hào)交叉口的影響范圍。根據(jù)我國城市道路規(guī)劃規(guī)范，文獻(xiàn)中對(duì)交叉口檢測(cè)器的預(yù)埋距離，以及信號(hào)交叉口延誤現(xiàn)場(chǎng)試驗(yàn)中對(duì)信號(hào)交叉口的影響范圍l設(shè)定為140-180m[9]。

圖1 信號(hào)交叉口影響范圍

信號(hào)交叉口影響范圍如圖1所示。本文設(shè)定信號(hào)交叉口影響范圍l為180m，即以信號(hào)交叉口轉(zhuǎn)角緣石曲線端點(diǎn)為計(jì)算起點(diǎn)，道路進(jìn)口道向上游和道路出口道向下游計(jì)算，180m為信號(hào)交叉口影響范圍的距離。

3.2 理想速度確定

利用浮動(dòng)車數(shù)據(jù)計(jì)算信號(hào)交叉口延誤需要獲取車輛通過信號(hào)交叉口時(shí)的理想速度，目前各個(gè)道路類型的理想速度還沒有沒有標(biāo)準(zhǔn)值。暢通是車輛在經(jīng)過信號(hào)范圍內(nèi)行駛的狀態(tài)，車輛通過信號(hào)交叉口的暢行速度與在信號(hào)交叉口范圍內(nèi)的運(yùn)行狀態(tài)有關(guān)，信號(hào)交叉口范圍內(nèi)的暢行速度v理依據(jù)《城市道路規(guī)劃規(guī)范》規(guī)定的速度設(shè)定，如表1所示。

表1 城市道路設(shè)計(jì)車速（km/h）

3.3 利用浮動(dòng)車數(shù)據(jù)計(jì)算信號(hào)交叉口延誤

浮動(dòng)車左轉(zhuǎn)或直行通過信號(hào)交叉口時(shí)，除了行駛信號(hào)交叉口影響范圍距離l外，還有停車線包圍的導(dǎo)流線距離 ，因此在整個(gè)信號(hào)交叉口范圍內(nèi)浮動(dòng)車行駛的距離。當(dāng)浮動(dòng)車左轉(zhuǎn)或直行時(shí)其導(dǎo)流線距離的長(zhǎng)度是不同的，如圖2所示。

圖2 信號(hào)交叉口延誤示意圖

式中：

3.4 基于BSP模型的信號(hào)交叉口延誤實(shí)現(xiàn)

Hama主要是以HDFS（Hadoop Distributed File System，分布式文件系統(tǒng)）為文件存儲(chǔ)系統(tǒng)以BSP計(jì)算模型為引擎的同步并行分布式集群[10]。數(shù)據(jù)的加載需要VertexInputReader類，該類定義了以鄰接表的形式進(jìn)行數(shù)據(jù)加載，解析輸入的每一行數(shù)據(jù)，得到頂點(diǎn)、目的頂點(diǎn)、邊的相關(guān)信息，所以需要把浮動(dòng)車、信號(hào)交叉口數(shù)據(jù)以圖結(jié)構(gòu)的形式進(jìn)行組織。令為圖數(shù)據(jù)的頂點(diǎn)ID，為圖數(shù)據(jù)的頂點(diǎn)屬性，為目的頂點(diǎn)ID，為目的頂點(diǎn)屬性，的組合（自定義）為邊權(quán)重。數(shù)據(jù)加載時(shí)，每次從HDFS中讀取一行數(shù)據(jù)，master按照頂點(diǎn)的不同執(zhí)行具體的分配，不同的頂點(diǎn)被master分配到不同的slave上，與之關(guān)聯(lián)的目的頂點(diǎn)和邊信息分配與頂點(diǎn)有關(guān)。

數(shù)據(jù)加載完成后，在compute()方法中實(shí)現(xiàn)信號(hào)交叉口延誤的迭代計(jì)算。每個(gè)迭代都是圍繞頂點(diǎn)的運(yùn)行狀態(tài)來進(jìn)行調(diào)度、通信和同步的。在compute()方法自定義迭代任務(wù)，再結(jié)合ZooKeeper提供的障柵同步機(jī)制，利用這些信息改變自身的運(yùn)行狀態(tài)，達(dá)到同步計(jì)算的目的，計(jì)算流程如圖3所示。

圖3 計(jì)算流程

4.實(shí)驗(yàn)驗(yàn)證與分析

在利用浮動(dòng)車數(shù)據(jù)計(jì)算信號(hào)交叉口延誤方面，驗(yàn)證基于BSP計(jì)算模型的信號(hào)交叉口延誤計(jì)算的表現(xiàn)，是否比基于MapReduce計(jì)算模型性能更優(yōu)，實(shí)現(xiàn)環(huán)境主要是Hama集群和Hadoop集群。兩種集群全部部署在VMware Workstation-11.0虛擬機(jī)上，具有統(tǒng)一的網(wǎng)絡(luò)配置，部署10臺(tái)機(jī)器組成的小集群，一臺(tái)作為master，其余都為slave，則兩種集群的所有機(jī)器環(huán)境如下：

（1）操作系統(tǒng)：CentOS-6.5；

（2）java運(yùn)行環(huán)境：JDK-7u79；

（3）hadoop運(yùn)行版本：hadoop-2.6.0；

（4）hama運(yùn)行版本：apache-hama-0.7.0。

選用2012年03月01日的部分北京市的浮動(dòng)車數(shù)據(jù)，187812條浮動(dòng)車軌跡，72449882個(gè)浮動(dòng)車軌跡點(diǎn)，1856個(gè)信號(hào)交叉口參與計(jì)算，獲取信號(hào)交叉口平均延誤值。表2、3為實(shí)驗(yàn)數(shù)據(jù)明細(xì)，存儲(chǔ)在HDFS中，圖4、圖5為數(shù)據(jù)的運(yùn)行結(jié)果對(duì)比圖。

從圖4、5可以看出，Hama集群和Hadoop集群處理信號(hào)交叉口延誤的時(shí)間隨著任務(wù)量的增多而增加，并且MapReduce計(jì)算模型的執(zhí)行時(shí)間大概是BSP計(jì)算模型的執(zhí)行時(shí)間的5倍，Hama集群和Hadoop集群處理信號(hào)交叉口延誤的任務(wù)時(shí)間隨著slave的增多而減少，Hama集群執(zhí)行時(shí)間的減少速度更快。

表2 不同容量的實(shí)驗(yàn)數(shù)據(jù)明細(xì)

表3 不同slave的實(shí)驗(yàn)數(shù)據(jù)

圖4 不同容量數(shù)據(jù)的運(yùn)行時(shí)間對(duì)比

圖5 不同slave的數(shù)據(jù)運(yùn)行時(shí)間對(duì)比

5.結(jié)論

通過部署在Hama集群上的基于BSP計(jì)算模型的信號(hào)交叉口延誤方法的探討，以實(shí)現(xiàn)利用大量浮動(dòng)車數(shù)據(jù)計(jì)算信號(hào)交叉口延誤。實(shí)驗(yàn)表明：基于BSP計(jì)算模型的信號(hào)交叉口延誤方法的同步并行化實(shí)現(xiàn)，不僅具有良好的可擴(kuò)展性，而且任務(wù)的執(zhí)行時(shí)間相對(duì)較少，提高了利用大量浮動(dòng)車數(shù)據(jù)計(jì)算信號(hào)交叉口延誤的效率，提高了實(shí)時(shí)性。但是對(duì)于巨大浮動(dòng)車數(shù)據(jù)源或者大規(guī)模集群實(shí)現(xiàn)的信號(hào)交叉口延誤還需要進(jìn)一步的研究。

[1]吳佩莉,劉奎恩,郝身剛,張全新,譚毓安.基于浮動(dòng)車數(shù)據(jù)的快速交通擁堵監(jiān)控[J].計(jì)算機(jī)研究與發(fā)展,2014,(01):189-198.

[2]劉廣萍,裴玉龍.信號(hào)控制下交叉口延誤計(jì)算方法研究[J].中國公路學(xué)報(bào),2005,18(1):104-108.

[3]張希瑞,方志祥,李清泉,等.基于浮動(dòng)車數(shù)據(jù)的城市信號(hào)通行能力時(shí)空特征分析[J].地球信息科學(xué)學(xué)報(bào),2015,17(3):336-343.

[4]余洋.云計(jì)算環(huán)境下的大樣本浮動(dòng)車數(shù)據(jù)處理關(guān)鍵技術(shù)研究[D].武漢:武漢大學(xué),2010.

[5]潘巍,李戰(zhàn)懷,伍賽,等.基于消息傳遞機(jī)制的MapReduce圖算法研究[J].計(jì)算機(jī)學(xué)報(bào),2011,34(10):1768-1784.

[6]孫玲,李靜.利用浮動(dòng)車回傳數(shù)據(jù)的信號(hào)交叉口延誤估計(jì)[C]//The International Conference on Power Electronics and Intelligent Transportation System.2010.

[7]徐淑,陸朝俊,陳昌生,等.基于BSP的并行事務(wù)處理模型[J].計(jì)算機(jī)研究與發(fā)展,2001,38(11):1399-1404.

[8]邵長(zhǎng)橋,榮建,任福田,楊振海.停車延誤、引道延誤和控制延誤關(guān)系研究[J].中國公路學(xué)報(bào),2002,(04):93-96.

[9]譚祥爽,王靜,宋現(xiàn)鋒,等.基于浮動(dòng)車數(shù)據(jù)的路口探測(cè)方法[J].地理與地理信息科學(xué),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－），男，河南商丘人，研究生碩士。