基于云架構(gòu)的交通感知數(shù)據(jù)集成處理平臺(tái)

趙卓峰　丁維龍　韓燕波

(北方工業(yè)大學(xué)計(jì)算機(jī)學(xué)院　北京　100144)(大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室(北方工業(yè)大學(xué))　北京　100144)(edzhao@ncut.edu.cn)

?

基于云架構(gòu)的交通感知數(shù)據(jù)集成處理平臺(tái)

趙卓峰丁維龍韓燕波

(北方工業(yè)大學(xué)計(jì)算機(jī)學(xué)院北京100144)(大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室(北方工業(yè)大學(xué))北京100144)(edzhao@ncut.edu.cn)

An Intergrated Processing Platform for Traffic Sensor Data Based on Cloud

摘要海量、多源、不間斷的交通感知數(shù)據(jù)環(huán)境下，如何提供集成化的交通感知數(shù)據(jù)處理支持是多樣化交通應(yīng)用實(shí)施中的難點(diǎn).現(xiàn)有的通用計(jì)算框架及平臺(tái)由于缺少對(duì)具有時(shí)空相關(guān)等特征的交通感知數(shù)據(jù)和應(yīng)用間交通感知數(shù)據(jù)共享的支持，使得交通感知數(shù)據(jù)處理應(yīng)用的開發(fā)存在較高的復(fù)雜性并且易于造成大量重復(fù)的數(shù)據(jù)跨節(jié)點(diǎn)傳輸而影響應(yīng)用性能.針對(duì)此問題，通過分析交通感知數(shù)據(jù)及其處理需求特征，提出一種基于可跨應(yīng)用共享的時(shí)空數(shù)據(jù)對(duì)象的交通感知數(shù)據(jù)處理模型，通過引入時(shí)空數(shù)據(jù)對(duì)象這一新的概念抽象并提供易并行劃分的時(shí)空數(shù)據(jù)對(duì)象組織及共享支持，實(shí)現(xiàn)分布計(jì)算中對(duì)時(shí)空型交通感知數(shù)據(jù)的優(yōu)化管理.在此基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)了交通感知數(shù)據(jù)集成處理平臺(tái).通過實(shí)際應(yīng)用和基于真實(shí)交通數(shù)據(jù)的實(shí)驗(yàn)測(cè)試表明:該平臺(tái)相對(duì)于傳統(tǒng)的交通感知數(shù)據(jù)處理方法及系統(tǒng)在性能及擴(kuò)展性等方面均具有一定的優(yōu)勢(shì).

關(guān)鍵詞云架構(gòu)；交通感知數(shù)據(jù)；時(shí)空數(shù)據(jù)對(duì)象；實(shí)時(shí)MapReduce；流計(jì)算

隨著交通相關(guān)的傳感、監(jiān)測(cè)技術(shù)的發(fā)展，各類智能交通系統(tǒng)在實(shí)踐應(yīng)用中不斷產(chǎn)生并積累了大量反映實(shí)際交通狀態(tài)的交通感知數(shù)據(jù)，這些通過各種交通傳感設(shè)備(如全球定位系統(tǒng)傳感器、車牌識(shí)別傳感器、交通流量傳感器、路況傳感器、車況傳感器等)實(shí)時(shí)采集并集中匯聚的交通感知數(shù)據(jù)逐漸成為智能交通系統(tǒng)中一類新的、關(guān)鍵的數(shù)據(jù)內(nèi)容，基于此類數(shù)據(jù)提供更加精確、全面、智能的交通管理及信息服務(wù)成為當(dāng)前智能交通系統(tǒng)中的研發(fā)熱點(diǎn).然而，如何面向海量、多源、不間斷的交通感知數(shù)據(jù)提供可擴(kuò)展、實(shí)時(shí)、連續(xù)的處理支持以滿足多樣化、動(dòng)態(tài)變化的交通應(yīng)用需求成為當(dāng)前智能交通系統(tǒng)建設(shè)的一個(gè)核心問題.

近年來，研究者們從時(shí)空數(shù)據(jù)管理、大規(guī)模數(shù)據(jù)的分布式處理、數(shù)據(jù)流管理、流式計(jì)算等不同角度開展了大量與上述需求相關(guān)的研究工作，通過這些工作我們可以看到,當(dāng)前在與本課題相關(guān)的研究領(lǐng)域表現(xiàn)出3個(gè)方面的發(fā)展趨勢(shì)：

1) 體系架構(gòu)方面.以MapReduce[1]為代表的大數(shù)據(jù)處理工作采用了具有水平擴(kuò)展優(yōu)勢(shì)的無共享集群云架構(gòu)，該種架構(gòu)已經(jīng)成為了大數(shù)據(jù)處理方向事實(shí)上典型架構(gòu)之一.

2) 計(jì)算模型方面.近年來則針對(duì)數(shù)據(jù)流及大數(shù)據(jù)實(shí)時(shí)處理情景體現(xiàn)出了由批處理計(jì)算到流式計(jì)算的發(fā)展趨勢(shì)[2].

3) 數(shù)據(jù)查詢處理優(yōu)化方面.從時(shí)空特征角度建立各類數(shù)據(jù)組織管理模型及索引機(jī)制成為優(yōu)化具有時(shí)空屬性數(shù)據(jù)的研究重點(diǎn).

然而，現(xiàn)有工作在應(yīng)對(duì)交通感知數(shù)據(jù)處理需求時(shí)尚存在3個(gè)問題：

1) 當(dāng)前主流的大數(shù)據(jù)處理技術(shù)，無論是批處理計(jì)算還是流式計(jì)算，其計(jì)算模型抽象層次都過高，缺乏對(duì)特定數(shù)據(jù)模式(特別是具有時(shí)空特征的交通感知數(shù)據(jù)模式)的直接支持，使得在編寫海量交通感知數(shù)據(jù)處理應(yīng)用時(shí)對(duì)程序員有較高的能力要求；

2) 傳統(tǒng)時(shí)空數(shù)據(jù)管理工作雖然從不同角度探索了時(shí)空數(shù)據(jù)的存儲(chǔ)、索引等方面的優(yōu)化技術(shù)，但大多數(shù)工作局限于單機(jī)環(huán)境可存儲(chǔ)管理的數(shù)據(jù)規(guī)模，在應(yīng)對(duì)需要分布式環(huán)境的大規(guī)模數(shù)據(jù)時(shí)表現(xiàn)出一些不足，特別是缺乏對(duì)具有良好伸縮性和可靠性保障的云架構(gòu)的利用；

3) 在現(xiàn)有云架構(gòu)下典型的數(shù)據(jù)處理模式下，一個(gè)作業(yè)內(nèi)的數(shù)據(jù)往往局限于其自身使用，針對(duì)交通領(lǐng)域一種交通感知數(shù)據(jù)可支撐數(shù)十種交通應(yīng)用的情況，現(xiàn)有的處理模式由于難以提供數(shù)據(jù)在應(yīng)用間的可控共享與運(yùn)行時(shí)支撐，從而會(huì)在分布式環(huán)境中造成大量不必要的數(shù)據(jù)復(fù)制與網(wǎng)絡(luò)傳遞，影響數(shù)據(jù)處理的性能.

本文針對(duì)上述問題并結(jié)合時(shí)空型交通感知數(shù)據(jù)及其處理類型特征，提出并設(shè)計(jì)了一個(gè)基于云架構(gòu)的海量交通感知數(shù)據(jù)集成處理平臺(tái).該平臺(tái)在現(xiàn)有基于無共享云架構(gòu)的分布式計(jì)算模型基礎(chǔ)上引入時(shí)空數(shù)據(jù)對(duì)象作為一級(jí)實(shí)體，并通過提供分布式時(shí)空數(shù)據(jù)對(duì)象模型及索引的支持來提供對(duì)時(shí)空型交通感知數(shù)據(jù)模式的直接支持，借此實(shí)現(xiàn)跨應(yīng)用的交通感知數(shù)據(jù)共享，為承載多樣化的交通感知數(shù)據(jù)處理應(yīng)用提供集成化的支持.

1需求分析與相關(guān)工作

1.1交通感知數(shù)據(jù)集成處理需求

智能交通系統(tǒng)中涉及的交通感知數(shù)據(jù)主要包括實(shí)時(shí)感知數(shù)據(jù)流和歷史交通感知數(shù)據(jù)2類.此外，基于交通感知數(shù)據(jù)的交通業(yè)務(wù)應(yīng)用需求也是多樣化的，它們往往需要集成來自不同系統(tǒng)的多元數(shù)據(jù)(如車輛GPS數(shù)據(jù)、交通流量數(shù)據(jù)、車牌識(shí)別數(shù)據(jù)、路網(wǎng)數(shù)據(jù)、車輛備案數(shù)據(jù)、嫌疑車黃標(biāo)車公交車數(shù)據(jù)等以及基于初始交通感知數(shù)據(jù)計(jì)算得出的交通流量數(shù)據(jù)、道路旅行時(shí)間數(shù)據(jù)等2次交通感知數(shù)據(jù))來支撐不同部門、不同單位的業(yè)務(wù)需求，例如實(shí)時(shí)采集的道路車輛車牌識(shí)別數(shù)據(jù)可以支撐套假牌、區(qū)間超速、黃標(biāo)車等違章車輛自動(dòng)甄別業(yè)務(wù)，交通流參數(shù)、路段旅行時(shí)間等實(shí)時(shí)路況計(jì)算業(yè)務(wù)，黑名單車輛布控、伴隨車輛分析等刑技偵業(yè)務(wù).由此可以看到交通感知數(shù)據(jù)及處理需求具有典型的“多源性和多樣性”.為此，迫切需要提供有效的數(shù)據(jù)集成與共享方式來支持在多樣化的交通應(yīng)用中使用這些海量的交通感知數(shù)據(jù).此外，智能交通系統(tǒng)中的交通感知數(shù)據(jù)主要圍繞車輛、道路、監(jiān)測(cè)點(diǎn)及交通設(shè)施等核心交通對(duì)象產(chǎn)生，具有典型的對(duì)象相關(guān)特性，如某車輛一天的行駛軌跡數(shù)據(jù)、某路段各時(shí)段的車流量數(shù)據(jù)等.同時(shí)這些交通感知數(shù)據(jù)又都涉及時(shí)間和空間2個(gè)維度的屬性，往往可以看作是交通對(duì)象在特定道路空間(即交通路網(wǎng))的時(shí)間序列數(shù)據(jù)，具有一定的時(shí)空關(guān)聯(lián)關(guān)系和分布特征，大多交通應(yīng)用也都是圍繞著這些具有時(shí)空屬性的交通感知數(shù)據(jù)展開的.我們把交通感知數(shù)據(jù)的上述特性稱為“對(duì)象相關(guān)性和時(shí)空相關(guān)性”.因此，需要充分利用這些特性來優(yōu)化交通感知數(shù)據(jù)在分布式環(huán)境中的并行劃分和組織管理.

另一方面，根據(jù)對(duì)上述交通感知數(shù)據(jù)處理需求的分析，我們可以將交通感知數(shù)據(jù)計(jì)算任務(wù)按照4類計(jì)算特征劃分，如表1所示.這4類計(jì)算任務(wù)從流計(jì)算和批計(jì)算的不同角度對(duì)交通感知數(shù)據(jù)處理提出了集成化的支撐需求.

Table 1　Description of Types of Traffic Sensor Data Computing

1.2相關(guān)工作

近年來，與上述需求相關(guān)的研究工作涉及多個(gè)研究方向，包括時(shí)空數(shù)據(jù)管理、分布式大數(shù)據(jù)處理、流數(shù)據(jù)處理及流式計(jì)算等.其中，時(shí)空數(shù)據(jù)管理是數(shù)據(jù)庫(kù)領(lǐng)域針對(duì)位置或形狀隨時(shí)間而變化的各類時(shí)空對(duì)象進(jìn)行管理的一個(gè)研究方向，其主要內(nèi)容涉及時(shí)空對(duì)象數(shù)據(jù)的建模、索引與查詢，可以支持對(duì)交通系統(tǒng)中車輛、人員等移動(dòng)對(duì)象的管理[3-4].但傳統(tǒng)時(shí)空數(shù)據(jù)模型在空間數(shù)據(jù)模型基礎(chǔ)上引入時(shí)態(tài)信息來對(duì)時(shí)空對(duì)象建模，但這類模型只適合對(duì)小規(guī)模、低頻率時(shí)空數(shù)據(jù)進(jìn)行建模，而且其上的查詢處理主要基于SQL語言，缺少對(duì)具有海量交通數(shù)據(jù)復(fù)雜處理的支持，特別是現(xiàn)有的時(shí)空數(shù)據(jù)管理方法大多局限于單機(jī)環(huán)境，在應(yīng)對(duì)大規(guī)模、不間斷的交通數(shù)據(jù)方面也缺乏分布式環(huán)境下的有效解決方案[5-6].

以MapReduce[1]為代表的一系列分布式計(jì)算技術(shù)為大數(shù)據(jù)處理帶來了新的思路，其強(qiáng)調(diào)在大量低端通用服務(wù)器的無共享集群云架構(gòu)下建立面向海量數(shù)據(jù)處理的并行計(jì)算模型和可伸縮環(huán)境，遵循了BASE(basic availability, soft state and eventual consistency)設(shè)計(jì)原則[7]來獲得大規(guī)模數(shù)據(jù)處理系統(tǒng)的可伸縮性和可用性，并在以搜索為主的大規(guī)?；ヂ?lián)網(wǎng)數(shù)據(jù)處理等應(yīng)用中得到了良好的驗(yàn)證.然而，MapReduce及其相關(guān)擴(kuò)展工作都屬于對(duì)持久化數(shù)據(jù)的批處理方式，在每次處理時(shí)都需要初始化運(yùn)行環(huán)境，同步地在Map和Reduce階段載入、處理大規(guī)模數(shù)據(jù)，并在節(jié)點(diǎn)間傳輸大量數(shù)據(jù)以及進(jìn)行MapReduce任務(wù)的同步.按照這種方式處理不間斷到達(dá)的交通數(shù)據(jù)很難滿足其流式計(jì)算中的實(shí)時(shí)性需求[8].

在流數(shù)據(jù)處理方面，數(shù)據(jù)流管理系統(tǒng)(data str-eam management system, DSMS)被設(shè)計(jì)用來滿足持續(xù)到達(dá)的數(shù)據(jù)序列的處理需求[9].由于數(shù)據(jù)流的持續(xù)性和無限性，傳統(tǒng)的數(shù)據(jù)流系統(tǒng)受數(shù)據(jù)采集速度、傳輸帶寬、內(nèi)存容量和計(jì)算能力等因素的限制不可能處理數(shù)據(jù)流的所有記錄(即只能支持有限歷史數(shù)據(jù))，因而一般采用滑動(dòng)窗口模型(sliding window model)或界標(biāo)模型(landmark model)來劃定處理邊界，或者通過抽樣(sampling)或概要數(shù)據(jù)方式形成一個(gè)子集代表數(shù)據(jù)全集，側(cè)重于針對(duì)相對(duì)小規(guī)模的數(shù)據(jù)進(jìn)行處理[10].此外，數(shù)據(jù)流系統(tǒng)支持處理類型大多為相對(duì)簡(jiǎn)單的查詢(如查找特定數(shù)據(jù)記錄或序列模式等)，不支持復(fù)雜分析與計(jì)算，處理后的數(shù)據(jù)流也會(huì)被丟棄，難以再次利用[11].因此，在面對(duì)多樣化的海量交通感知數(shù)據(jù)處理需求時(shí)它們不得不面對(duì)處理能力和擴(kuò)展性方面的問題.

從2010年開始，流式計(jì)算逐漸成為大數(shù)據(jù)處理的一個(gè)研究熱點(diǎn)，也出現(xiàn)了Storm[12]，Spark Streaming[13]等知名的流式計(jì)算系統(tǒng)，該方向可以看作是數(shù)據(jù)流系統(tǒng)在大數(shù)據(jù)新背景下的一個(gè)新發(fā)展[2].在該計(jì)算模型中，數(shù)據(jù)以流和批等不同形式到達(dá)，多個(gè)處理單元中的計(jì)算程序?qū)?shù)據(jù)進(jìn)行不間斷的實(shí)時(shí)計(jì)算和傳遞.一個(gè)典型的流式計(jì)算模型可以看作一系列算子(點(diǎn))和數(shù)據(jù)流(邊)組成的數(shù)據(jù)流圖(表示為有向非循環(huán)圖)，然而這種高度抽象的計(jì)算模型在面向交通數(shù)據(jù)處理需求時(shí)由于不能提供對(duì)交通感知數(shù)據(jù)模式的直接支持，在交通數(shù)據(jù)處理應(yīng)用研發(fā)中需要進(jìn)行大量重復(fù)的復(fù)雜開發(fā)工作.

Fig. 1　Traffic sensor data processing model based on temporal data objects.圖1　基于時(shí)空數(shù)據(jù)對(duì)象的交通感知數(shù)據(jù)處理模型

2基于時(shí)空數(shù)據(jù)對(duì)象的交通感知數(shù)據(jù)處理模型

2.1模型描述

按照1.1節(jié)所述的處理要求，面對(duì)高速到達(dá)的實(shí)時(shí)感知數(shù)據(jù)及大規(guī)模歷史感知數(shù)據(jù)形式存在的交通感知數(shù)據(jù)，如何利用其時(shí)空相關(guān)及對(duì)象相關(guān)等特征進(jìn)行有效表示和組織以支持在多樣化的感知數(shù)據(jù)處理應(yīng)用中共享使用是海量交通感知數(shù)據(jù)集成處理的關(guān)鍵所在.

為了在已有狀態(tài)的計(jì)算任務(wù)為核心的流式計(jì)算模型上加強(qiáng)對(duì)交通感知數(shù)據(jù)模式的直接支持，我們提出一種基于時(shí)空數(shù)據(jù)對(duì)象的感知數(shù)據(jù)處理模型，其核心特點(diǎn)是引入適于并行化的時(shí)空數(shù)據(jù)對(duì)象并允許在同一數(shù)據(jù)對(duì)象上執(zhí)行不同計(jì)算任務(wù)來解決引言提到的交通感知數(shù)據(jù)集成處理所面臨的3個(gè)問題.該模型將時(shí)空數(shù)據(jù)對(duì)象作為交通感知數(shù)據(jù)集成處理中的一級(jí)實(shí)體，時(shí)空數(shù)據(jù)對(duì)象是一種易于并行劃分及動(dòng)態(tài)維護(hù)的內(nèi)存數(shù)據(jù)對(duì)象，通過對(duì)其管理待處理的數(shù)據(jù)并記錄處理的狀態(tài)，也可實(shí)現(xiàn)跨計(jì)算任務(wù)的共享.

下面我們給出如圖1所示的基于時(shí)空數(shù)據(jù)對(duì)象的交通感知數(shù)據(jù)處理模型中的核心概念.

1) 交通感知數(shù)據(jù)記錄(data record, DR).DR記錄相關(guān)交通對(duì)象在不同時(shí)間、空間屬性下的狀態(tài)，可表示為〈key，value〉對(duì)形式的數(shù)據(jù)單元，其中時(shí)間、空間及對(duì)象標(biāo)識(shí)常被用作交通感知數(shù)據(jù)的key.

2) 實(shí)時(shí)感知數(shù)據(jù)流(data stream, DS).DS表示實(shí)時(shí)獲取到的感知數(shù)據(jù)記錄序列，它往往以流的形式進(jìn)入系統(tǒng).

3) 歷史感知數(shù)據(jù)(history data, HD).HD表示長(zhǎng)時(shí)間積累的感知數(shù)據(jù)記錄集，它來自對(duì)實(shí)時(shí)感知數(shù)據(jù)進(jìn)行持久化存儲(chǔ)的數(shù)據(jù)集.

4) 時(shí)空數(shù)據(jù)對(duì)象(data object, DO).DO表示可供感知數(shù)據(jù)計(jì)算任務(wù)使用的感知數(shù)據(jù)記錄集合，該集合中感知數(shù)據(jù)記錄的key都滿足一定的約束，比如給定的時(shí)間或空間范圍.

時(shí)空數(shù)據(jù)對(duì)象可以方便地表示對(duì)參與計(jì)算的交通感知數(shù)據(jù)的并行化劃分，按照同一種劃分規(guī)則得到的時(shí)空數(shù)據(jù)對(duì)象可被歸入同一組管理.同時(shí)，不同的時(shí)空數(shù)據(jù)對(duì)象可以在不同計(jì)算任務(wù)(包括跨應(yīng)用的計(jì)算任務(wù))間共享.

5) 計(jì)算任務(wù)(computing task, CT).CT表示感知數(shù)據(jù)處理中的基本單元，每個(gè)計(jì)算任務(wù)可以指定需要計(jì)算的時(shí)空數(shù)據(jù)對(duì)象組，計(jì)算結(jié)果可以形成新的時(shí)空數(shù)據(jù)對(duì)象.

根據(jù)同組時(shí)空數(shù)據(jù)對(duì)象的劃分情況(即根據(jù)key劃分成的時(shí)空數(shù)據(jù)對(duì)象數(shù)目)，每個(gè)計(jì)算任務(wù)在執(zhí)行時(shí)會(huì)產(chǎn)生多個(gè)實(shí)例，每個(gè)實(shí)例處理相應(yīng)的時(shí)空數(shù)據(jù)對(duì)象.

與典型的流式計(jì)算模型一樣，計(jì)算任務(wù)可以放置到不同的節(jié)點(diǎn)上，按照處理邏輯可以構(gòu)成一個(gè)計(jì)算任務(wù)間的有向無環(huán)圖.

2.2多維時(shí)空數(shù)據(jù)對(duì)象組織模式

根據(jù)2.1節(jié)所述模型，適于并行化組織的時(shí)空數(shù)據(jù)對(duì)象成為交通感知數(shù)據(jù)處理模型中除計(jì)算任務(wù)外的另一核心要素.為了支持時(shí)空數(shù)據(jù)對(duì)象管理，需要提供一種適于分布式環(huán)境下并行處理的時(shí)空數(shù)據(jù)對(duì)象組織方式.

通過對(duì)交通感知數(shù)據(jù)及其處理需求特征歸納，交通感知數(shù)據(jù)主要從時(shí)間、空間、對(duì)象3個(gè)維度進(jìn)行劃分，相關(guān)交通業(yè)務(wù)基本圍繞這3個(gè)維度交叉進(jìn)行數(shù)據(jù)處理，如圍繞車輛對(duì)象的車輛監(jiān)管業(yè)務(wù)、圍繞路段路徑空間屬性的實(shí)時(shí)路況業(yè)務(wù)以及圍繞時(shí)間屬性的不同周期交通數(shù)據(jù)統(tǒng)計(jì)業(yè)務(wù).因此，我們首先從這3個(gè)維度對(duì)時(shí)空數(shù)據(jù)對(duì)象進(jìn)行劃分，具體可以根據(jù)不同類型交通感知數(shù)據(jù)處理需求并通過定義這3個(gè)維度上的Hash函數(shù)來完成不同節(jié)點(diǎn)下的數(shù)據(jù)對(duì)象劃分及分布方案.同時(shí)，為了提供細(xì)粒度的數(shù)據(jù)共享支持，還可以對(duì)每個(gè)維度下劃分得到的數(shù)據(jù)對(duì)象從其他維度進(jìn)一步分解，為此我們?cè)诠?jié)點(diǎn)內(nèi)采用B樹結(jié)構(gòu)來對(duì)其進(jìn)行組織.這樣，可以形成一種基于Hash B樹的分層次索引結(jié)構(gòu)以組織每個(gè)維度劃分得到的時(shí)空數(shù)據(jù)對(duì)象.圖2給出了首先從時(shí)間維度進(jìn)行劃分的時(shí)空數(shù)據(jù)對(duì)象組織結(jié)構(gòu).數(shù)據(jù)對(duì)象中包含的具體交通感知數(shù)據(jù)記錄可以在樹的葉節(jié)點(diǎn)按照時(shí)間順序以鏈表形式存儲(chǔ)；同時(shí)，還可以先從空間角度或者車輛對(duì)象角度進(jìn)行數(shù)據(jù)劃分，進(jìn)一步再采用B樹結(jié)構(gòu)對(duì)劃分后的數(shù)據(jù)按照其他維度進(jìn)行組織.

Fig. 2　Structure of spatio-temporal data objects divided from the time dimension in the beginning.圖2　先從時(shí)間維度進(jìn)行劃分的時(shí)空數(shù)據(jù)對(duì)象組織結(jié)構(gòu)

根據(jù)上述時(shí)空數(shù)據(jù)對(duì)象組織結(jié)構(gòu)，可以看出對(duì)Hash表的任意劃分能形成對(duì)Hash B樹的劃分，因此該結(jié)構(gòu)具有較好的可劃分性，適于分布環(huán)境下的并行劃分.同時(shí)，由于用作Hash鍵的時(shí)間、空間和交通對(duì)象值都可預(yù)測(cè)并具有唯一的Hash值，因此可以通過分配足夠的Hash表項(xiàng)使得該結(jié)構(gòu)下的插入和查找操作的復(fù)雜度僅為O(1).

2.3時(shí)空數(shù)據(jù)對(duì)象核心操作

由于時(shí)空數(shù)據(jù)對(duì)象包含參與計(jì)算的感知數(shù)據(jù)及計(jì)算過程中涉及的中間狀態(tài)數(shù)據(jù)，它們主要通過對(duì)原始感知數(shù)據(jù)(包括實(shí)時(shí)感知數(shù)據(jù)和歷史感知數(shù)據(jù))進(jìn)行劃分及執(zhí)行特定的操作得到或產(chǎn)生，而這些數(shù)據(jù)對(duì)象可以被不同的計(jì)算任務(wù)共享使用.根據(jù)1.1節(jié)對(duì)交通感知數(shù)據(jù)處理需求的歸納，針對(duì)時(shí)空數(shù)據(jù)對(duì)象的創(chuàng)建、劃分、組織維度重組、鍵值變換、數(shù)據(jù)更新等需求，我們?cè)O(shè)計(jì)了表2所列的5類時(shí)空數(shù)據(jù)對(duì)象核心操作.這些不同類別的操作可以用于支持計(jì)算過程中涉及的對(duì)共享數(shù)據(jù)對(duì)象的處理，以滿足不同計(jì)算任務(wù)對(duì)時(shí)空數(shù)據(jù)對(duì)象的處理需求.此外，用戶也可以指定計(jì)算過程中新產(chǎn)生的時(shí)空數(shù)據(jù)對(duì)象是否需要共享.

Table 2Core Operations Available for Spatio-temporal Data

Objects

表2　時(shí)空數(shù)據(jù)對(duì)象核心操作

上述操作均是以時(shí)空數(shù)據(jù)對(duì)象為中心的操作，它們針對(duì)交通感知數(shù)據(jù)的處理語義明確.這些操作的設(shè)計(jì)思路參考了1.2節(jié)所述的Storm和Spark等相關(guān)工作.其中，load操作借鑒了Storm IBlot接口中的prepare操作，在核心計(jì)算業(yè)務(wù)前準(zhǔn)備數(shù)據(jù)，專注于感知數(shù)據(jù)從持久化存儲(chǔ)中讀取并加載至內(nèi)存；transform操作和edit操作，則參考了Spark中的transform操作和action操作，前者專注于存在鍵變化的對(duì)象，后者專注于存在值變化的對(duì)象；而partition操作和regroup操作則提供對(duì)交通感知數(shù)據(jù)在時(shí)間、空間、對(duì)象3個(gè)維度不同組織方式的支持.

3交通感知數(shù)據(jù)集成處理平臺(tái)及應(yīng)用

3.1平臺(tái)實(shí)現(xiàn)

根據(jù)第2節(jié)的處理模型，我們實(shí)現(xiàn)了云架構(gòu)下的海量交通感知數(shù)據(jù)集成處理平臺(tái).平臺(tái)由1個(gè)控制節(jié)點(diǎn)和多個(gè)處理節(jié)點(diǎn)集群組成，其中，控制節(jié)點(diǎn)負(fù)責(zé)時(shí)空數(shù)據(jù)對(duì)象和計(jì)算任務(wù)的調(diào)度、監(jiān)控和容錯(cuò)處理，具體包括時(shí)空數(shù)據(jù)對(duì)象和計(jì)算任務(wù)元數(shù)據(jù)管理、狀態(tài)信息收集及生命周期控制以及集群節(jié)點(diǎn)協(xié)調(diào)控制.任務(wù)節(jié)點(diǎn)負(fù)責(zé)接收外部實(shí)時(shí)感知數(shù)據(jù)和歷史感知數(shù)據(jù)并創(chuàng)建時(shí)空數(shù)據(jù)對(duì)象、接收動(dòng)態(tài)部署計(jì)算任務(wù)并執(zhí)行任務(wù)、向控制節(jié)點(diǎn)定期報(bào)告時(shí)空數(shù)據(jù)對(duì)象和計(jì)算任務(wù)信息.

在具體實(shí)現(xiàn)中，針對(duì)1.1節(jié)歸納的4類交通感知數(shù)據(jù)處理類型，可以看到這些典型的計(jì)算任務(wù)在時(shí)空數(shù)據(jù)被接入后往往需要經(jīng)歷多類業(yè)務(wù)計(jì)算，也即需要多個(gè)計(jì)算任務(wù)的處理.因此，如何組織時(shí)空數(shù)據(jù)對(duì)象并分配至計(jì)算任務(wù)以及如何調(diào)度各計(jì)算任務(wù)是系統(tǒng)實(shí)現(xiàn)必須考慮的重要問題.

1) 在數(shù)據(jù)組織方面.我們采用基于外存的多維倒排索引來組織海量離線的時(shí)空數(shù)據(jù)，即在指定的時(shí)間閾值下(如1 d或1周)，分別構(gòu)建數(shù)據(jù)在時(shí)間、空間和對(duì)象上的倒排索引，同時(shí)根據(jù)配置的副本度，在系統(tǒng)的計(jì)算節(jié)點(diǎn)上均勻布局.針對(duì)實(shí)時(shí)在線的時(shí)空數(shù)據(jù)，則采用2.2節(jié)的Hash B樹結(jié)構(gòu)，在內(nèi)存中以輕量級(jí)有限空間的方式組織維護(hù).

2) 在數(shù)據(jù)分發(fā)和任務(wù)調(diào)度方面.我們分別針對(duì)表1所述的計(jì)算類型，將計(jì)算任務(wù)分類并按照所設(shè)定的計(jì)算閾值(計(jì)算頻率、窗口大小等)劃分任務(wù)關(guān)于獲取數(shù)據(jù)的需求，并對(duì)相同需求的計(jì)算分配相同的數(shù)據(jù)對(duì)象，對(duì)離線計(jì)算任務(wù)采用盡可能靠近數(shù)據(jù)位置的分配方式.

系統(tǒng)通過擴(kuò)展Hadoop MapReduce實(shí)現(xiàn)，改進(jìn)的主要內(nèi)容包括：調(diào)整JobTracker中任務(wù)調(diào)度模式為時(shí)空數(shù)據(jù)對(duì)象相關(guān)的調(diào)度，并增加了時(shí)空數(shù)據(jù)對(duì)象的調(diào)度功能和狀態(tài)監(jiān)控功能；在TaksTracker中增加了對(duì)時(shí)空數(shù)據(jù)對(duì)象內(nèi)存數(shù)據(jù)結(jié)構(gòu)的支持；去除了TaksTracker中Map和Reduce任務(wù)執(zhí)行過程中對(duì)HDFS文件系統(tǒng)的讀寫，中間結(jié)果改為以時(shí)空數(shù)據(jù)對(duì)象形式在內(nèi)存中管理.關(guān)于系統(tǒng)實(shí)現(xiàn)的更多詳細(xì)細(xì)節(jié)可參考文獻(xiàn)[14-15].

3.2應(yīng)用實(shí)例

上述平臺(tái)已被應(yīng)用到基于車牌識(shí)別數(shù)據(jù)的城市車輛管控系統(tǒng)項(xiàng)目中，本節(jié)通過其中的城市道路旅行時(shí)間計(jì)算和伴隨車輛分析2個(gè)交通應(yīng)用來展示海量交通感知數(shù)據(jù)集成處理平臺(tái)的應(yīng)用方法和效果.

1) 旅行時(shí)間計(jì)算

路段旅行時(shí)間作為城市交通出行信息的關(guān)鍵指標(biāo)，可以直接用來評(píng)判城市道路的運(yùn)行狀況和擁堵水平，有效的旅行時(shí)間監(jiān)測(cè)與分析也可以為城市路網(wǎng)規(guī)劃、城市道路交通管理與控制、公眾出行路線選擇提供合理依據(jù).旅行時(shí)間計(jì)算問題可以看作是：給定旅行時(shí)間計(jì)算時(shí)間周期和一定時(shí)間范圍內(nèi)的車牌識(shí)別數(shù)據(jù)集，對(duì)受測(cè)道路路網(wǎng)中的所有路段求其在給定時(shí)間范圍不同時(shí)間區(qū)間上的路段旅行時(shí)間.對(duì)于不同時(shí)間區(qū)間上的路段旅行時(shí)間，可以通過計(jì)算其在不同時(shí)間區(qū)間上的所有單車旅行時(shí)間，并進(jìn)一步取中位數(shù)方法求得最終結(jié)果.

針對(duì)旅行時(shí)間計(jì)算處理邏輯中涉及的車牌識(shí)別數(shù)據(jù)加載、單車旅行時(shí)間計(jì)算、單車旅行時(shí)間中位數(shù)查找3個(gè)子任務(wù)，可采用2次MapReduce迭代處理.

第1次MapReduce處理中的Map函數(shù)完成車牌識(shí)別數(shù)據(jù)的讀入及劃分和如2.2節(jié)所述的數(shù)據(jù)結(jié)構(gòu)組織，具體可通過load操作來進(jìn)行裝載并得到Hash B樹結(jié)構(gòu)的數(shù)據(jù)對(duì)象，進(jìn)一步利用partition操作進(jìn)行劃分.具體地，首先從時(shí)間維度，為支持時(shí)間區(qū)間劃分采用時(shí)間區(qū)間作為key，相同時(shí)間區(qū)間的車牌識(shí)別數(shù)據(jù)在Hash表的同一項(xiàng)中用B樹組織；其次，監(jiān)測(cè)點(diǎn)作為空間劃分基礎(chǔ)被用來組織最終的車牌識(shí)別數(shù)據(jù)，每個(gè)監(jiān)測(cè)點(diǎn)的車牌識(shí)別數(shù)據(jù)在B樹的葉節(jié)點(diǎn)用鏈表按照時(shí)間順序進(jìn)行組織，最終以形如〈key: 時(shí)間區(qū)間+監(jiān)測(cè)點(diǎn)，value: 車牌號(hào)+時(shí)間〉的鍵值對(duì)組織數(shù)據(jù)；Reduce函數(shù)利用transform操作形成指定時(shí)間和路段下的單車旅行時(shí)間數(shù)據(jù)對(duì)象，即將上述Hash B樹中葉節(jié)點(diǎn)的監(jiān)測(cè)點(diǎn)識(shí)別數(shù)據(jù)變換為特定車輛在不同路段的旅行時(shí)間數(shù)據(jù)，其可根據(jù)路段信息對(duì)中間結(jié)果按照車牌號(hào)進(jìn)行重組得到形為〈key: 時(shí)間區(qū)間+路段(監(jiān)測(cè)點(diǎn)1、監(jiān)測(cè)點(diǎn)2)，value: 車牌號(hào)及時(shí)間點(diǎn)1和時(shí)間點(diǎn)2〉的鍵值對(duì).

第2次MapReduce處理中的Map函數(shù)利用edit操作計(jì)算單車路段旅行時(shí)間而不做任何數(shù)據(jù)變換，Reduce函數(shù)同樣只進(jìn)行所有單車旅行時(shí)間中位數(shù)查找，最后形成最終結(jié)果數(shù)據(jù)對(duì)象，即得到形如〈key:時(shí)間區(qū)間+路段，value: 旅行時(shí)間值〉的鍵值對(duì).〈201310020830+LD0014[JCD06,JCD07]，360〉是一個(gè)路段旅行時(shí)間計(jì)算最終結(jié)果示例,該示例表示在2013-10-02T8：30—8：45的時(shí)間區(qū)間，0014號(hào)路段(即監(jiān)測(cè)點(diǎn)JCD06到監(jiān)測(cè)點(diǎn)JCD07的路段)的旅行時(shí)間為360 s.

2) 伴隨車輛分析

伴隨車輛分析主要是在海量車輛監(jiān)控?cái)?shù)據(jù)基礎(chǔ)上分析車輛移動(dòng)對(duì)象軌跡間的相似關(guān)系，可以協(xié)助公安民警辦案、犯罪嫌疑車輛查詢，也可以為城市道路規(guī)劃提供參考，具有重要的實(shí)際意義.伴隨車輛分析問題可以簡(jiǎn)單地理解為：給定點(diǎn)伴隨時(shí)間閾值、軌跡相似度閾值和軌跡長(zhǎng)度閾值，利用已有車輛監(jiān)控?cái)?shù)據(jù)集，找出在給定的時(shí)間范圍內(nèi)所有具有伴隨關(guān)系的車輛相似軌跡集合的查詢分析.

伴隨車輛分析過程可分解為軌跡分析與篩選、點(diǎn)伴隨判定、軌跡相似性計(jì)算3次MapReduce迭代處理.

① 車輛軌跡分析與篩選

該步驟讀取原始車牌識(shí)別數(shù)據(jù)，并將數(shù)據(jù)按時(shí)間屬性進(jìn)行劃分，然后按照車輛進(jìn)行數(shù)據(jù)對(duì)象組織，可以通過對(duì)旅行時(shí)間計(jì)算中時(shí)空數(shù)據(jù)對(duì)象施加regroup操作獲得.在此基礎(chǔ)上，通過一次MapReduce運(yùn)算可統(tǒng)計(jì)得出所有車輛在給定時(shí)間段內(nèi)的有效軌跡數(shù)據(jù).其中，Map函數(shù)將調(diào)用transform操作得到形如〈key:車牌號(hào)，value:時(shí)間和監(jiān)測(cè)點(diǎn)〉的數(shù)據(jù)對(duì)象；Reduce函數(shù)通過transform操作將相同key的Map函數(shù)輸出進(jìn)一步進(jìn)行合并形成單車軌跡數(shù)據(jù)對(duì)象，并對(duì)單車軌跡長(zhǎng)度小于給定軌跡長(zhǎng)度閾值的軌跡數(shù)據(jù)進(jìn)行刪除.

② 點(diǎn)伴隨判定

點(diǎn)伴隨判定主要讀取第1次MapReduce過濾后的數(shù)據(jù)對(duì)象，并通過第2次MapReduce進(jìn)行計(jì)算返回具有點(diǎn)伴隨關(guān)系的車輛對(duì)，即在同一監(jiān)測(cè)點(diǎn)鄰近時(shí)間范圍內(nèi)出現(xiàn)的2個(gè)車輛.在此次MapReduce中，首先在Map函數(shù)中直接讀取一次MapReduce得到的數(shù)據(jù)對(duì)象并通過transform操作將其轉(zhuǎn)換為形如〈key: 監(jiān)測(cè)點(diǎn)ID，value: 監(jiān)測(cè)時(shí)間和車牌號(hào)〉的數(shù)據(jù)對(duì)象，然后傳遞給Reduce函數(shù)；經(jīng)過同一個(gè)監(jiān)測(cè)點(diǎn)的識(shí)別數(shù)據(jù)會(huì)發(fā)給同一個(gè)Reduce函數(shù)處理，Reduce函數(shù)對(duì)接收的車輛識(shí)別數(shù)據(jù)，按監(jiān)測(cè)時(shí)間先后排序，隨后開始點(diǎn)伴隨計(jì)算.點(diǎn)伴隨計(jì)算從車倆軌跡鏈表頭結(jié)點(diǎn)開始，取第1個(gè)監(jiān)測(cè)數(shù)據(jù)和之后的數(shù)據(jù)比較，判斷2個(gè)時(shí)間差是否小于點(diǎn)伴隨時(shí)間閾值，如果滿足則直接將2個(gè)車牌號(hào)輸出到結(jié)果，其中key為車牌號(hào)1和車牌號(hào)2組合，value為固定值1.

③ 軌跡相似性計(jì)算

通過第3次MapReduce完成軌跡相似性計(jì)算，即對(duì)第2次MapReduce得到的點(diǎn)伴隨結(jié)果根據(jù)車輛軌跡進(jìn)行統(tǒng)計(jì)，然后按照軌跡相似度計(jì)算公式判定伴隨車輛.在此次處理中，Map函數(shù)直接讀取第2次MapReduce得到的結(jié)果并直接輸出.其中，輸出結(jié)果的key為具有點(diǎn)伴隨關(guān)系的2個(gè)車牌，value值為固定值1；Reduce函數(shù)接收Map函數(shù)輸出的鍵值對(duì)，利用edit操作計(jì)算key相同的數(shù)目，然后根據(jù)車輛軌跡計(jì)算軌跡相似度，并返回滿足軌跡相似度閾值的車牌對(duì).

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

4.1實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)環(huán)境采用的是在5臺(tái)服務(wù)機(jī)上搭建的集群環(huán)境，并在其上部署基于Hadoop擴(kuò)展了中間結(jié)果緩存和時(shí)空數(shù)據(jù)對(duì)象處理機(jī)制后的平臺(tái)實(shí)現(xiàn).其中，Master節(jié)點(diǎn)配置為4核CPU、4 GB內(nèi)存，Master節(jié)點(diǎn)同時(shí)也被當(dāng)作計(jì)算節(jié)點(diǎn)；另外4臺(tái)Slave節(jié)點(diǎn)配置為2核CPU、4 GB內(nèi)存，作為計(jì)算節(jié)點(diǎn).此外，每臺(tái)服務(wù)器的有效容量為80 GB，集群總存儲(chǔ)容量為400 GB.實(shí)驗(yàn)中采用的數(shù)據(jù)為北京市1 000多個(gè)帶識(shí)別功能的道路攝像頭采集到的真實(shí)車牌識(shí)別數(shù)據(jù).

為了從性能對(duì)比、關(guān)鍵參數(shù)影響和擴(kuò)展性3方面對(duì)基于本文系統(tǒng)實(shí)現(xiàn)的旅行時(shí)間計(jì)算和伴隨車輛分析功能進(jìn)行驗(yàn)證分析，我們?cè)O(shè)計(jì)了2組實(shí)驗(yàn)：

實(shí)驗(yàn)1. 選取北京市2012-11-01—2012-11-20期間20 d的真實(shí)車牌識(shí)別歷史數(shù)據(jù)(約1億條)作為原始計(jì)算數(shù)據(jù)集，分別測(cè)試5 min，15 min，1 h這3個(gè)時(shí)間周期下路段旅行時(shí)間計(jì)算的性能、關(guān)鍵參數(shù)影響和擴(kuò)展性情況.同時(shí)，還選取直接在Hadoop平臺(tái)上實(shí)現(xiàn)而并未對(duì)車牌識(shí)別數(shù)據(jù)進(jìn)行特別處理的旅行時(shí)間計(jì)算方法(LMR方法)[16]作為比較對(duì)象，與本文基于本文平臺(tái)實(shí)現(xiàn)的旅行時(shí)間計(jì)算方法(CMR方法)進(jìn)行性能比較.

實(shí)驗(yàn)2. 選取北京市2012-11-13全天采集到的真實(shí)車牌識(shí)別數(shù)據(jù)(這組車牌識(shí)別數(shù)據(jù)中涉及的車牌數(shù)量(即車輛數(shù))約230萬，道路監(jiān)測(cè)點(diǎn)為1 794個(gè))，數(shù)據(jù)記錄為970萬余條，大小0.94 GB，對(duì)本文平臺(tái)下實(shí)現(xiàn)的伴隨車輛查詢方法(MPST方法)進(jìn)行性能及關(guān)鍵參數(shù)影響測(cè)試.同時(shí)，還利用同組實(shí)驗(yàn)數(shù)據(jù)測(cè)試了文獻(xiàn)[17-18]中提出的單機(jī)環(huán)境下的伴隨車輛查詢方法(即TMN-Tree方法和ACR方法)以進(jìn)行對(duì)比.

4.2實(shí)驗(yàn)結(jié)果分析

1) 性能對(duì)比分析

① 旅行時(shí)間計(jì)算性能

從圖3可以看出，隨著參與計(jì)算的車牌識(shí)別數(shù)據(jù)集數(shù)據(jù)量的增加，2種計(jì)算方法的計(jì)算時(shí)間均呈線性增加；但CMR方法在計(jì)算效率上比LMR方法有較高的提升，并且CMR方法受時(shí)間周期差異的影響比LMR方法小很多，5 min，15 min，1 h這3個(gè)不同時(shí)間周期下計(jì)算時(shí)間的差異均在100 s以內(nèi).

Fig. 3　The impact of vehicle license plate recognition data on the performance of travel time computing.圖3　車牌識(shí)別數(shù)據(jù)量對(duì)旅行時(shí)間計(jì)算性能的影響

此外，從圖3還可以看到，LMR方法在計(jì)算時(shí)間周期越短(即時(shí)間段劃分粒度越細(xì))時(shí)計(jì)算時(shí)間越長(zhǎng)，5 min周期下的計(jì)算時(shí)間最長(zhǎng)；而CMR方法恰好相反，在計(jì)算時(shí)間周期變短時(shí)計(jì)算時(shí)間反而會(huì)略微減少，5 min周期下的計(jì)算時(shí)間最短.究其原因，主要因?yàn)楫?dāng)計(jì)算時(shí)間周期較小時(shí)，需要計(jì)算旅行時(shí)間的時(shí)間區(qū)間會(huì)大幅增加，使得Hadoop運(yùn)行態(tài)中的Map任務(wù)和Reduce任務(wù)大增并帶來較大的任務(wù)執(zhí)行調(diào)度代價(jià).傳統(tǒng)LMR方法由于未根據(jù)車牌識(shí)別數(shù)據(jù)特征進(jìn)行劃分優(yōu)化，執(zhí)行中需要大量的Map任務(wù)和Reduce任務(wù)間的同步等待，從而使得小時(shí)間周期下的計(jì)算時(shí)間變長(zhǎng)；而CMR方法由于通過先時(shí)間后空間的劃分模式使得旅行時(shí)間計(jì)算過程可以避免Map任務(wù)和Reduce任務(wù)間不必要的數(shù)據(jù)依賴，這樣單個(gè)Map任務(wù)和Reduce任務(wù)一次處理的數(shù)據(jù)量(受時(shí)間區(qū)間大小影響)成為影響計(jì)算時(shí)間的主要因素，因此使得短時(shí)間周期下的計(jì)算時(shí)間反而變短.

② 伴隨車輛分析性能

我們分別針對(duì)1 h，3 h，8 h，24 h不同時(shí)間范圍內(nèi)的車牌識(shí)別數(shù)據(jù)進(jìn)行了伴隨車輛查詢測(cè)試，其中采用的1 h識(shí)別數(shù)據(jù)量約為41萬條，3 h的識(shí)別數(shù)據(jù)量約為155萬條，8 h的識(shí)別數(shù)據(jù)量約為370萬條，全天24 h的識(shí)別數(shù)據(jù)量約為970萬條.在具體實(shí)驗(yàn)中，分別使用上面提到的3種不同的伴隨車輛查詢方法對(duì)相同時(shí)間范圍的數(shù)據(jù)進(jìn)行查詢，其中點(diǎn)伴隨時(shí)間閾值取值為1 min，軌跡長(zhǎng)度閾值取值為10，軌跡相似度閾值取值為75%.實(shí)驗(yàn)結(jié)果如圖4所示:

Fig. 4　Comparison of accompanying cars query timeunder different time ranges.圖4　不同時(shí)間范圍的數(shù)據(jù)規(guī)模下的伴隨車輛查詢時(shí)間對(duì)比

由圖4可見，在1 h的數(shù)據(jù)規(guī)模下本文MPST方法性能略高于TMN-Tree方法和ACR方法，這說明在數(shù)據(jù)規(guī)模較小的情況下性能提升還相對(duì)不明顯；但在3 h，8 h，24 h數(shù)據(jù)規(guī)模時(shí)，MPST方法通過利用并行化的方式可以在分布式環(huán)境下獲得較好的查詢性能提升，大幅提高查詢效率，查詢處理性能相對(duì)于傳統(tǒng)單機(jī)的查詢算法最高可提高10倍以上.

2) 關(guān)鍵參數(shù)影響分析

① 旅行時(shí)間計(jì)算

Fig. 5　The impact of the number of road on travel time computing.圖5　路段數(shù)對(duì)旅行時(shí)間計(jì)算的影響

我們針對(duì)旅行時(shí)間計(jì)算中不同受測(cè)路段規(guī)模下的計(jì)算性能進(jìn)行了實(shí)驗(yàn).從圖5可以看出，隨著受測(cè)路網(wǎng)中路段數(shù)目的增加，本文CMR計(jì)算方法的計(jì)算時(shí)間基本平滑，而LMR方法則在路段數(shù)增大時(shí)表現(xiàn)出計(jì)算時(shí)間線性增長(zhǎng)的趨勢(shì).這表明CMR計(jì)算方法的計(jì)算性能基本不受路段數(shù)目的影響，當(dāng)我們?cè)黾邮軠y(cè)路網(wǎng)規(guī)模(即增加路段數(shù))時(shí)，并不影響旅行時(shí)間計(jì)算的計(jì)算性能.主要原因在于，路段數(shù)在旅行時(shí)間計(jì)算中的主要影響是會(huì)增大計(jì)算中間結(jié)果的規(guī)模，CMR方法由于采用時(shí)空數(shù)據(jù)對(duì)象結(jié)構(gòu)優(yōu)化了中間結(jié)果的處理，因此其受路段數(shù)變化的影響較小.

② 伴隨車輛分析

我們還針對(duì)本文方法中用于點(diǎn)伴隨判定的時(shí)間間隔閾值和軌跡相似度閾值的不同對(duì)查詢性能和查詢結(jié)果集大小的影響進(jìn)行了測(cè)試，實(shí)驗(yàn)在24 h的車牌識(shí)別數(shù)據(jù)(千萬記錄量級(jí))上進(jìn)行.

由圖6可以看到，增加用于點(diǎn)伴隨判定的時(shí)間間隔閾值會(huì)極大影響查詢性能，相應(yīng)的查詢時(shí)間在同樣的軌跡相似度閾值下會(huì)接近線性增長(zhǎng).而軌跡相似度閾值的提高反而會(huì)降低相應(yīng)的查詢時(shí)間，這主要是因?yàn)橄嗨贫纫蟾叻炊鴷?huì)減少查詢處理過程中中間結(jié)果數(shù)據(jù)的規(guī)模，從而降低查詢時(shí)間.

Fig. 6　Accompanying cars query performance changes under different similarity thresholds.圖6　不同相似度閾值下的伴隨車輛查詢性能變化

Fig. 7　Results set size change of accompanying carsquery under different similarity thresholds.圖7　不同相似度閾值下伴隨車輛查詢結(jié)果集大小變化

圖7則給出了不同閾值下查詢結(jié)果集大小的實(shí)驗(yàn)結(jié)果.由圖7可以看出，降低相似度閾值和放大用于點(diǎn)伴隨判定的時(shí)間間隔閾值都帶來結(jié)果集的增大；但當(dāng)相似度閾值降低到80%及以下時(shí)，結(jié)果集數(shù)據(jù)量開始明顯增大，并且不同時(shí)間間隔閾值下結(jié)果集數(shù)據(jù)量的差距將變得愈發(fā)突出.

3) 擴(kuò)展性分析

在擴(kuò)展性方面，由于系統(tǒng)采用了無共享集群的云架構(gòu)模式并在Hadoop基礎(chǔ)上實(shí)現(xiàn)，對(duì)旅行時(shí)間計(jì)算和伴隨車輛分析2個(gè)不同應(yīng)用具有相同的擴(kuò)展性效果.這里我們僅給出旅行時(shí)間計(jì)算的擴(kuò)展性實(shí)驗(yàn)結(jié)果，如圖8所示.從圖8可以看出，隨著計(jì)算節(jié)點(diǎn)數(shù)的增加，計(jì)算時(shí)間會(huì)逐步降低，并且可以看出細(xì)粒度時(shí)間周期的計(jì)算時(shí)間更少.這表明本文平臺(tái)的實(shí)現(xiàn)并未影響原Hadoop架構(gòu)的擴(kuò)展性.

Fig. 8　The impact of computing nodes on travel timecalculations.圖8　計(jì)算節(jié)點(diǎn)數(shù)對(duì)旅行時(shí)間計(jì)算的影響

5結(jié)束語

本文以交通這一特定領(lǐng)域?yàn)闋恳?，針?duì)該領(lǐng)域下海量交通感知數(shù)據(jù)的時(shí)空、對(duì)象相關(guān)及其處理需求的多樣化特征，提出一種基于可共享、易并行化的時(shí)空數(shù)據(jù)對(duì)象的感知數(shù)據(jù)處理模型，并在此基礎(chǔ)上設(shè)計(jì)并實(shí)現(xiàn)了交通感知數(shù)據(jù)集成處理平臺(tái).該平臺(tái)可以為基于交通感知數(shù)據(jù)的集成處理應(yīng)用提供從數(shù)據(jù)組織、獲取及計(jì)算方面統(tǒng)一的集成化支持，并通過數(shù)據(jù)的共享實(shí)現(xiàn)多樣化交通感知數(shù)據(jù)處理應(yīng)用的整體優(yōu)化.實(shí)際的應(yīng)用效果和相關(guān)實(shí)驗(yàn)驗(yàn)證表明，該平臺(tái)相對(duì)于傳統(tǒng)的海量交通感知數(shù)據(jù)處理系統(tǒng)在性能及擴(kuò)展性等方面都具有一定的優(yōu)勢(shì).下一步的工作包括處理模型的理論分析、時(shí)空數(shù)據(jù)對(duì)象的動(dòng)態(tài)管理以及更加全面的實(shí)驗(yàn)測(cè)試分析.

參考文獻(xiàn)

[1]Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113

[2]Sun Dawei, Zhang Guangyan, Zheng Weimin. Big data stream computing: Technologies and instances[J]. Journal of Software, 2014, 25(4): 839-862 (in Chinese)(孫大為, 張廣艷, 鄭緯民. 大數(shù)據(jù)流式計(jì)算:關(guān)鍵技術(shù)及系統(tǒng)實(shí)例[J]. 軟件學(xué)報(bào), 2014, 25(4): 839-862)

[3]Meng Xiaofeng, Ding Zhiming. Mobile Data Management: Concepts and Techniques[M]. Beijing: Tsinghua University Press, 2009 (in Chinese)(孟小峰, 丁治明. 移動(dòng)數(shù)據(jù)管理：概念與技術(shù)[M]. 北京: 清華大學(xué)出版社, 2009)

[4]Zhou Aoying, Yang Bin, Jin Cheqing, et al. Location-based services: Architecture and progress[J]. Chinese Journal of Computers, 2011, 34(7): 1155-1171 (in Chinese)(周傲英, 楊彬, 金澈清, 等. 基于位置的服務(wù)：架構(gòu)與進(jìn)展[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(7): 1155-1171)

[5]Sergio I, Eduardo M. Location-dependent query processing: Where we are and where we are heading[J]. ACM Computing Surveys, 2010, 42(3): Article 12

[6]Ding Zhiming, Gao Xu. A database cluster system framework for managing massive sensor sampling data in the Internet of things[J]. Chinese Journal of Computers, 2012, 32(6): 1175-1191 (in Chinese)(丁治明, 高需. 面向物聯(lián)網(wǎng)海量傳感器采樣數(shù)據(jù)管理的數(shù)據(jù)庫(kù)集群系統(tǒng)框架[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 32(6): 1175-1191)

[7]Pritchett D. BASE: An acid alternative[J]. Queue, 2008, 6(3): 48-55

[8]Meng Xiaofeng, Ci Xiang. Big data management: Concepts, techniques and challenges[J]. Journal of Computer Research and Development, 2013, 50(1): 146-169 (in Chinese)(孟小峰, 慈祥. 大數(shù)據(jù)管理：概念、技術(shù)與挑戰(zhàn)[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(1): 146-169)

[9]Abadi D J, Ahmad Y, Balazinska M, et al. The design of the Borealis stream processing engine[C] //Proc of the 2nd Biennial Conf on Innovative Data Systems Research. New York: ACM, 2005: 277-289

[10]Motwani R, Widom J, Arasu A, et al. Query processing, resource management, and approximation in a data stream management system[C] //Proc of the 1st Biennial Conf on Innovative Data Systems Research. New York: ACM, 2003: 176-187

[11]Golab L, Tamer M. Issues in data stream management[J]. SIGMOD Record, 2003, 32(2): 5-14

[12]Toshniwal A, Taneja S, Shukla A, et al. Storm @Twitter[C] //Proc of the 33rd ACM Int Conf on Management of Data (SIGMOD 2014). New York: ACM, 2014: 147-156

[13]Zaharia M, Das T, Li H, et al. Discretized streams: An efficient and fault-tolerant model for stream processing on large clusters[C] //Proc of the 4th Conf on Hot Topics in Cloud Computing. Berkeley, CA: USENIX Association, 2012: 181-184

[14]Qi Kaiyuan, Zhao Zhuofeng, Fang Jun, et al. Real-time processing for high speed data stream over large scale data[J]. Chinese Journal of Computers, 2012, 35(3): 477-490 (in Chinese)(亓開元, 趙卓峰, 房俊, 等. 針對(duì)高速數(shù)據(jù)流的大規(guī)模數(shù)據(jù)實(shí)時(shí)處理方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(3): 477-490)

[15]Qi Kaiyuan, Han Yanbo, Zhao Zhuofeng, et al. MapReduce intermediate result cache for concurrent data stream processing[J]. Journal of Computer Research and Development, 2013, 50(1): 111-121 (in Chinese)(亓開元, 韓燕波, 趙卓峰, 等. 支持高并發(fā)數(shù)據(jù)流處理的MapReduce中間結(jié)果緩存[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(1): 111-121)

[16]Zhang Shuai, Zhao Zhuofeng, Ding Weilong. Urban road trip time measured calculation based on MapReduce[J]. Computer & Digital Engineering, 2014, 42(9): 1542-1546 (in Chinese)(張帥, 趙卓峰, 丁維龍. 基于MapReduce的城市道路旅行時(shí)間實(shí)測(cè)計(jì)算[J]. 計(jì)算機(jī)與數(shù)字工程, 2014, 42(9): 1542-1546)

[17]Chang J, Song M, Um J. TMN-tree: New trajectory index structure for moving objects in spatial networks[C] //Proc of the 10th Int Conf on Computer and Information Technology. Piscataway, NJ: IEEE, 2010: 1633-1638

[18]Zhao Xinyong, An Shi. Research on accompanying cars recognition in practical application[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(3): 36-40 (in Chinese)(趙新勇, 安實(shí). 伴隨車檢測(cè)技術(shù)應(yīng)用研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2012, 12(3): 36-40)

Zhao Zhuofeng, born in 1977. PhD and associate professor. Senior member of China Computer Federation. His current research interests include streaming computing, Internet of things technology and cloud computing.

Ding Weilong, born in 1983. PhD and assistant professor. Member of China Computer Federation. His main research interests include real-time data processing, distributed system and cloud computing.

Han Yanbo, born in 1962. PhD, professor and PhD supervisor. Senior member of China Computer Federation. His current research interests include cloud computing, big data science and service computing.

Architecture

Zhao Zhuofeng, Ding Weilong, and Han Yanbo

(SchoolofComputerScienceandTechnology,NorthChinaUniversityofTechnology,Beijing100144)(BeijingKeyLaboratoryonIntegrationandAnalysisofLarge-ScaleStreamData(NorthChinaUniversityofTechnology),Beijing100144)

AbstractWith the continuous expansion of the scope of traffic sensor networks, traffic sensor data becomes widely available and is continuously being produced. Traffic sensor data gathered by large amounts of sensors shows the massive, continuous, streaming and spatio-temporal characteristics compared with traditional traffic data. How to provide intergrated support for multi-source, massive and continuous traffic sensor data processing is becoming one key issue of the implementation of diversified traffic applications. However, due to the absence of support for spatio-temporal traffic sensor data, it is difficult to develop corresponding applications and optimize the data transfer among different nodes in currenent distributed computing platforms. In this paper, we propose a traffic domain-specific processing model based on spatio-temporal data object. The spatio-temporal data object is treated as the first-class object in the distributed processing model. According to the model, we implement an intergrated processing platform for traffic sensor data based on the share-nothing architecture of cloud computing, which is designed to combine spatio-temporal data partition, pipelined parallel processing and stream computing to support traffic sensor data processing in a scalable architecture with real-time guarantee. Applications of the platform in real project and experiments based on real traffice sensor data show that our platform excels in performance and extensibility compared with traditional traffic sensor data processing system.

Key wordscloud architecture; traffic sensor data; spatio-temporal data object; real-time MapReduce; stream computing

收稿日期：2015-06-09；修回日期：2015-09-11

基金項(xiàng)目：國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(61033006)；北京市自然科學(xué)基金項(xiàng)目(4131001,4162021)；北京市屬高等學(xué)校創(chuàng)新團(tuán)隊(duì)建設(shè)項(xiàng)目(IDHT20130502)；北方工業(yè)大學(xué)?？蒲谢痦?xiàng)目

中圖法分類號(hào)TP333

This work was supported by the Key Program of the National Natural Science Foundation of China (61033006), the Natural Science Foundation of Beijing (4131001,4162021), the Project of Construction of Innovative Teams and Teacher Career Development for Universities and Colleges under Beijing Municipality (IDHT20130502), and the Research Funding of North China University of Technology.