基于云架構的交通感知數據集成處理平臺

趙卓峰　丁維龍　韓燕波

(北方工業大學計算機學院　北京　100144)(大規模流數據集成與分析技術北京市重點實驗室(北方工業大學)　北京　100144)(edzhao@ncut.edu.cn)

?

基于云架構的交通感知數據集成處理平臺

趙卓峰丁維龍韓燕波

(北方工業大學計算機學院北京100144)(大規模流數據集成與分析技術北京市重點實驗室(北方工業大學)北京100144)(edzhao@ncut.edu.cn)

An Intergrated Processing Platform for Traffic Sensor Data Based on Cloud

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

關鍵詞云架構；交通感知數據；時空數據對象；實時MapReduce；流計算

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

近年來，研究者們從時空數據管理、大規模數據的分布式處理、數據流管理、流式計算等不同角度開展了大量與上述需求相關的研究工作，通過這些工作我們可以看到,當前在與本課題相關的研究領域表現出3個方面的發展趨勢：

1) 體系架構方面.以MapReduce[1]為代表的大數據處理工作采用了具有水平擴展優勢的無共享集群云架構，該種架構已經成為了大數據處理方向事實上典型架構之一.

2) 計算模型方面.近年來則針對數據流及大數據實時處理情景體現出了由批處理計算到流式計算的發展趨勢[2].

3) 數據查詢處理優化方面.從時空特征角度建立各類數據組織管理模型及索引機制成為優化具有時空屬性數據的研究重點.

然而，現有工作在應對交通感知數據處理需求時尚存在3個問題：

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

2) 傳統時空數據管理工作雖然從不同角度探索了時空數據的存儲、索引等方面的優化技術，但大多數工作局限于單機環境可存儲管理的數據規模，在應對需要分布式環境的大規模數據時表現出一些不足，特別是缺乏對具有良好伸縮性和可靠性保障的云架構的利用；

3) 在現有云架構下典型的數據處理模式下，一個作業內的數據往往局限于其自身使用，針對交通領域一種交通感知數據可支撐數十種交通應用的情況，現有的處理模式由于難以提供數據在應用間的可控共享與運行時支撐，從而會在分布式環境中造成大量不必要的數據復制與網絡傳遞，影響數據處理的性能.

本文針對上述問題并結合時空型交通感知數據及其處理類型特征，提出并設計了一個基于云架構的海量交通感知數據集成處理平臺.該平臺在現有基于無共享云架構的分布式計算模型基礎上引入時空數據對象作為一級實體，并通過提供分布式時空數據對象模型及索引的支持來提供對時空型交通感知數據模式的直接支持，借此實現跨應用的交通感知數據共享，為承載多樣化的交通感知數據處理應用提供集成化的支持.

1需求分析與相關工作

1.1交通感知數據集成處理需求

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

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

Table 1　Description of Types of Traffic Sensor Data Computing

1.2相關工作

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

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

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

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

Fig. 1　Traffic sensor data processing model based on temporal data objects.圖1　基于時空數據對象的交通感知數據處理模型

2基于時空數據對象的交通感知數據處理模型

2.1模型描述

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

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

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

1) 交通感知數據記錄(data record, DR).DR記錄相關交通對象在不同時間、空間屬性下的狀態，可表示為〈key，value〉對形式的數據單元，其中時間、空間及對象標識常被用作交通感知數據的key.

2) 實時感知數據流(data stream, DS).DS表示實時獲取到的感知數據記錄序列，它往往以流的形式進入系統.

3) 歷史感知數據(history data, HD).HD表示長時間積累的感知數據記錄集，它來自對實時感知數據進行持久化存儲的數據集.

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

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

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

根據同組時空數據對象的劃分情況(即根據key劃分成的時空數據對象數目)，每個計算任務在執行時會產生多個實例，每個實例處理相應的時空數據對象.

與典型的流式計算模型一樣，計算任務可以放置到不同的節點上，按照處理邏輯可以構成一個計算任務間的有向無環圖.

2.2多維時空數據對象組織模式

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

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

Fig. 2　Structure of spatio-temporal data objects divided from the time dimension in the beginning.圖2　先從時間維度進行劃分的時空數據對象組織結構

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

2.3時空數據對象核心操作

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

Table 2Core Operations Available for Spatio-temporal Data

Objects

表2　時空數據對象核心操作

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

3交通感知數據集成處理平臺及應用

3.1平臺實現

根據第2節的處理模型，我們實現了云架構下的海量交通感知數據集成處理平臺.平臺由1個控制節點和多個處理節點集群組成，其中，控制節點負責時空數據對象和計算任務的調度、監控和容錯處理，具體包括時空數據對象和計算任務元數據管理、狀態信息收集及生命周期控制以及集群節點協調控制.任務節點負責接收外部實時感知數據和歷史感知數據并創建時空數據對象、接收動態部署計算任務并執行任務、向控制節點定期報告時空數據對象和計算任務信息.

在具體實現中，針對1.1節歸納的4類交通感知數據處理類型，可以看到這些典型的計算任務在時空數據被接入后往往需要經歷多類業務計算，也即需要多個計算任務的處理.因此，如何組織時空數據對象并分配至計算任務以及如何調度各計算任務是系統實現必須考慮的重要問題.

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

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

系統通過擴展Hadoop MapReduce實現，改進的主要內容包括：調整JobTracker中任務調度模式為時空數據對象相關的調度，并增加了時空數據對象的調度功能和狀態監控功能；在TaksTracker中增加了對時空數據對象內存數據結構的支持；去除了TaksTracker中Map和Reduce任務執行過程中對HDFS文件系統的讀寫，中間結果改為以時空數據對象形式在內存中管理.關于系統實現的更多詳細細節可參考文獻[14-15].

3.2應用實例

上述平臺已被應用到基于車牌識別數據的城市車輛管控系統項目中，本節通過其中的城市道路旅行時間計算和伴隨車輛分析2個交通應用來展示海量交通感知數據集成處理平臺的應用方法和效果.

1) 旅行時間計算

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

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

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

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

2) 伴隨車輛分析

伴隨車輛分析主要是在海量車輛監控數據基礎上分析車輛移動對象軌跡間的相似關系，可以協助公安民警辦案、犯罪嫌疑車輛查詢，也可以為城市道路規劃提供參考，具有重要的實際意義.伴隨車輛分析問題可以簡單地理解為：給定點伴隨時間閾值、軌跡相似度閾值和軌跡長度閾值，利用已有車輛監控數據集，找出在給定的時間范圍內所有具有伴隨關系的車輛相似軌跡集合的查詢分析.

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

① 車輛軌跡分析與篩選

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

② 點伴隨判定

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

③ 軌跡相似性計算

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

4實驗與分析

4.1實驗設置

實驗環境采用的是在5臺服務機上搭建的集群環境，并在其上部署基于Hadoop擴展了中間結果緩存和時空數據對象處理機制后的平臺實現.其中，Master節點配置為4核CPU、4 GB內存，Master節點同時也被當作計算節點；另外4臺Slave節點配置為2核CPU、4 GB內存，作為計算節點.此外，每臺服務器的有效容量為80 GB，集群總存儲容量為400 GB.實驗中采用的數據為北京市1 000多個帶識別功能的道路攝像頭采集到的真實車牌識別數據.

為了從性能對比、關鍵參數影響和擴展性3方面對基于本文系統實現的旅行時間計算和伴隨車輛分析功能進行驗證分析，我們設計了2組實驗：

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

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

4.2實驗結果分析

1) 性能對比分析

① 旅行時間計算性能

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

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

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

② 伴隨車輛分析性能

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

Fig. 4　Comparison of accompanying cars query timeunder different time ranges.圖4　不同時間范圍的數據規模下的伴隨車輛查詢時間對比

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

2) 關鍵參數影響分析

① 旅行時間計算

Fig. 5　The impact of the number of road on travel time computing.圖5　路段數對旅行時間計算的影響

我們針對旅行時間計算中不同受測路段規模下的計算性能進行了實驗.從圖5可以看出，隨著受測路網中路段數目的增加，本文CMR計算方法的計算時間基本平滑，而LMR方法則在路段數增大時表現出計算時間線性增長的趨勢.這表明CMR計算方法的計算性能基本不受路段數目的影響，當我們增加受測路網規模(即增加路段數)時，并不影響旅行時間計算的計算性能.主要原因在于，路段數在旅行時間計算中的主要影響是會增大計算中間結果的規模，CMR方法由于采用時空數據對象結構優化了中間結果的處理，因此其受路段數變化的影響較小.

② 伴隨車輛分析

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

由圖6可以看到，增加用于點伴隨判定的時間間隔閾值會極大影響查詢性能，相應的查詢時間在同樣的軌跡相似度閾值下會接近線性增長.而軌跡相似度閾值的提高反而會降低相應的查詢時間，這主要是因為相似度要求高反而會減少查詢處理過程中中間結果數據的規模，從而降低查詢時間.

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　不同相似度閾值下伴隨車輛查詢結果集大小變化

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

3) 擴展性分析

在擴展性方面，由于系統采用了無共享集群的云架構模式并在Hadoop基礎上實現，對旅行時間計算和伴隨車輛分析2個不同應用具有相同的擴展性效果.這里我們僅給出旅行時間計算的擴展性實驗結果，如圖8所示.從圖8可以看出，隨著計算節點數的增加，計算時間會逐步降低，并且可以看出細粒度時間周期的計算時間更少.這表明本文平臺的實現并未影響原Hadoop架構的擴展性.

Fig. 8　The impact of computing nodes on travel timecalculations.圖8　計算節點數對旅行時間計算的影響

5結束語

本文以交通這一特定領域為牽引，針對該領域下海量交通感知數據的時空、對象相關及其處理需求的多樣化特征，提出一種基于可共享、易并行化的時空數據對象的感知數據處理模型，并在此基礎上設計并實現了交通感知數據集成處理平臺.該平臺可以為基于交通感知數據的集成處理應用提供從數據組織、獲取及計算方面統一的集成化支持，并通過數據的共享實現多樣化交通感知數據處理應用的整體優化.實際的應用效果和相關實驗驗證表明，該平臺相對于傳統的海量交通感知數據處理系統在性能及擴展性等方面都具有一定的優勢.下一步的工作包括處理模型的理論分析、時空數據對象的動態管理以及更加全面的實驗測試分析.

參考文獻

[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)(孫大為, 張廣艷, 鄭緯民. 大數據流式計算:關鍵技術及系統實例[J]. 軟件學報, 2014, 25(4): 839-862)

[3]Meng Xiaofeng, Ding Zhiming. Mobile Data Management: Concepts and Techniques[M]. Beijing: Tsinghua University Press, 2009 (in Chinese)(孟小峰, 丁治明. 移動數據管理：概念與技術[M]. 北京: 清華大學出版社, 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)(周傲英, 楊彬, 金澈清, 等. 基于位置的服務：架構與進展[J]. 計算機學報, 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)(丁治明, 高需. 面向物聯網海量傳感器采樣數據管理的數據庫集群系統框架[J]. 計算機學報, 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)(孟小峰, 慈祥. 大數據管理：概念、技術與挑戰[J]. 計算機研究與發展, 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)(亓開元, 趙卓峰, 房俊, 等. 針對高速數據流的大規模數據實時處理方法[J]. 計算機學報, 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)(亓開元, 韓燕波, 趙卓峰, 等. 支持高并發數據流處理的MapReduce中間結果緩存[J]. 計算機研究與發展, 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的城市道路旅行時間實測計算[J]. 計算機與數字工程, 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)(趙新勇, 安實. 伴隨車檢測技術應用研究[J]. 交通運輸系統工程與信息, 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

基金項目：國家自然科學基金重點項目(61033006)；北京市自然科學基金項目(4131001,4162021)；北京市屬高等學校創新團隊建設項目(IDHT20130502)；北方工業大學校科研基金項目

中圖法分類號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.