遲 劍，劉艷飛

（河北民族師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，承德 067000）

0 引言

近幾年，中小城市城鎮(zhèn)化擴(kuò)張速度迅猛，對(duì)公交運(yùn)輸提出了新挑戰(zhàn)。以承德市為例，在2010 年前，承德公交集團(tuán)年運(yùn)輸旅客在8000 萬人次左右，到疫情前的2019 年，年運(yùn)輸人數(shù)達(dá)到1.58 億人次左右，海量的乘客運(yùn)輸軌跡和公交運(yùn)營軌跡隨著公交車輛網(wǎng)絡(luò)升級(jí)，車載終端借助于GPS 與北斗雙系統(tǒng)復(fù)合模塊來定位實(shí)現(xiàn)了實(shí)時(shí)傳輸，公交公司能及時(shí)方便地獲取公交車輛的軌跡數(shù)據(jù)。大量的軌跡數(shù)據(jù)，促使公交系統(tǒng)管理由預(yù)定排班系統(tǒng)轉(zhuǎn)向?qū)崟r(shí)的計(jì)算分析，對(duì)運(yùn)營的公交車輛實(shí)現(xiàn)有效的監(jiān)測(cè)。

面向公交運(yùn)營監(jiān)測(cè)中，實(shí)時(shí)探測(cè)運(yùn)營異常是最迫切的應(yīng)用需求。這里的異常主要指同一線路上車輛聚集問題、車輛擁堵問題、車速異常問題、非站點(diǎn)停車問題等，需要在存儲(chǔ)的數(shù)據(jù)中針對(duì)異常數(shù)據(jù)快速定位分類，進(jìn)而提升問題解決的效率。在實(shí)際的運(yùn)營過程中，公交企業(yè)普遍采用成熟的數(shù)據(jù)庫產(chǎn)品，比如甲骨文的Oracle Spatial，或者是成熟的云存儲(chǔ)平臺(tái)，采用規(guī)定的接口和模式訪問相關(guān)的數(shù)據(jù)，既定的條件限制下，在海量數(shù)據(jù)中快速定位異常數(shù)據(jù)，是國內(nèi)外展開研究的熱點(diǎn)問題。

針對(duì)云存儲(chǔ)平臺(tái)，一般主要對(duì)數(shù)據(jù)索引以及存儲(chǔ)結(jié)構(gòu)兩個(gè)方面加以改進(jìn)加快定位速度。呂江波等［1］提出基于車輛軌跡誤差來源，研究統(tǒng)計(jì)分析方法，設(shè)計(jì)了基于Hadoop 的預(yù)處理模型方案，解決數(shù)據(jù)量大的時(shí)候數(shù)據(jù)分析瓶頸。喬千雄等［2］提出根據(jù)歷史數(shù)據(jù)分析，測(cè)定異常行為數(shù)據(jù)分類，根據(jù)分類狀態(tài)借助于MapReduce 算力，完成異常數(shù)據(jù)監(jiān)測(cè)。余列冰等［3］根據(jù)軌跡數(shù)據(jù)基本特征，重設(shè)Hbase中分布列的數(shù)據(jù)結(jié)構(gòu)，采用k近鄰算法，提出了融合時(shí)空劃分和軌跡分段的組織方法，提升了稀疏區(qū)域數(shù)據(jù)處理效率。魏學(xué)才等［4］根據(jù)數(shù)據(jù)的訪問頻度分為冷熱數(shù)據(jù)，提出多數(shù)據(jù)編碼機(jī)制，基于HDFS-RAID 設(shè)計(jì)了相應(yīng)的框架，部署于Hadoop集群中。李劍斌等［5］在Spark 并行計(jì)算框架中實(shí)現(xiàn)車輛軌跡數(shù)據(jù)實(shí)時(shí)分析區(qū)域車輛密度，挖掘道路擁堵狀況，在治理擁堵問題上快速定位擁堵點(diǎn)。另外，為了獲取更高的數(shù)據(jù)存儲(chǔ)和查詢性能，挖掘數(shù)據(jù)特性，構(gòu)建索引也是研究點(diǎn)之一。Meng 等［6］早在2012 年在海量數(shù)據(jù)分析中構(gòu)建分區(qū)位圖索引，和傳統(tǒng)的索引相比，非常顯著地提升了范圍查詢。Dittrich 等［7］早在數(shù)據(jù)上傳到Hadoop 前，就構(gòu)建HALL 索引，提升上傳處理速度，比單獨(dú)在Hadoop 上的數(shù)據(jù)處理速度提升較為顯著。文獻(xiàn)［6］和文獻(xiàn)［7］較早提出了兩種海量數(shù)據(jù)中數(shù)據(jù)處理方向和索引算法，這也成為近年來研究的熱點(diǎn)問題。相關(guān)研究的改進(jìn)方向主要根據(jù)軌跡信息點(diǎn)特性，軌跡相關(guān)區(qū)域劃定，軌跡相似度分析來快速定位相應(yīng)帶查詢區(qū)域。例如，針對(duì)車輛軌跡數(shù)據(jù)的連續(xù)性，黃火榮等［8］依據(jù)連續(xù)歷史數(shù)據(jù)確定分段，依據(jù)分段設(shè)計(jì)索引實(shí)現(xiàn)查詢，取得了很好的查詢性能。Shen 等［9］對(duì)原始數(shù)據(jù)預(yù)處理階段構(gòu)建位圖索引結(jié)構(gòu)，實(shí)現(xiàn)兩段查詢，分別對(duì)持續(xù)時(shí)間和間隔時(shí)間進(jìn)行優(yōu)化，這對(duì)解決公交問題的連續(xù)車輛間隔和擁堵時(shí)長(zhǎng)定位有一定的啟發(fā)。鄭浩泉等［10］也驗(yàn)證了根據(jù)時(shí)空軌跡數(shù)據(jù)特點(diǎn)設(shè)計(jì)三種存儲(chǔ)方法，數(shù)據(jù)上傳前完成分類，從而提升特定數(shù)據(jù)挖掘速度。

在實(shí)際快速定位存儲(chǔ)應(yīng)用中，由于公交企業(yè)存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)采集結(jié)構(gòu)是固定的，其更新的可能性比較低，另外在中小城市中，站點(diǎn)之間的距離較短，而車輛擁堵的時(shí)間一般小于20分鐘，要求更快定位異常點(diǎn)。毛嘉莉等［11］在軌跡異常數(shù)據(jù)綜述中指出，車輛軌跡異常數(shù)據(jù)分析基本途徑是融合軌跡異常的時(shí)間特性和因果聯(lián)系，實(shí)現(xiàn)數(shù)據(jù)過濾，繼而完成大空間內(nèi)數(shù)據(jù)異常定位。因此，本文針對(duì)海量公交運(yùn)營數(shù)據(jù)的位圖索引過濾，而后在模擬的公交存儲(chǔ)框架上完成異常數(shù)據(jù)定位，建立異常數(shù)據(jù)臨時(shí)存儲(chǔ)區(qū)作為數(shù)據(jù)分析源，旨在解決異常車輛的快速定位問題。

1 公交運(yùn)用數(shù)據(jù)存儲(chǔ)平臺(tái)及異常數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

目前公交集團(tuán)數(shù)據(jù)集遷移云平臺(tái)已成大勢(shì)所趨。本文模擬公交集團(tuán)試驗(yàn)線路采用的云存儲(chǔ)平臺(tái)構(gòu)建基本的存儲(chǔ)框架。在Hadoop 生態(tài)系統(tǒng)中，以數(shù)據(jù)存儲(chǔ)和分析為目的的分布式平臺(tái)，包括數(shù)據(jù)采集、數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)分析三個(gè)部分。數(shù)據(jù)采集層依據(jù)GPS 傳輸，采集車輛運(yùn)行數(shù)據(jù)以及路口數(shù)據(jù)和IC 卡數(shù)據(jù)；數(shù)據(jù)存儲(chǔ)層使用HDFS 作為數(shù)據(jù)存儲(chǔ)，同時(shí)依據(jù)Impala 完成數(shù)據(jù)的多維預(yù)處理；數(shù)據(jù)分析層借助HBase 查詢接口，實(shí)現(xiàn)實(shí)時(shí)查詢分析，具體如圖1所示。

圖1 存儲(chǔ)平臺(tái)架構(gòu)

數(shù)據(jù)采集層采集到的數(shù)據(jù)包括靜態(tài)數(shù)據(jù)和動(dòng)態(tài)數(shù)據(jù)。靜態(tài)數(shù)據(jù)通過批處理方式將靜態(tài)站點(diǎn)數(shù)據(jù)傳入存儲(chǔ)層；實(shí)時(shí)動(dòng)態(tài)數(shù)據(jù)經(jīng)過簡(jiǎn)單的清洗后，讀取進(jìn)入HDFS分布式存儲(chǔ)系統(tǒng)，在該存儲(chǔ)系統(tǒng)上，采用Impala 結(jié)合位圖索引探查HDFS 數(shù)據(jù)，普通數(shù)據(jù)存入歷史數(shù)據(jù)庫，異常定位數(shù)據(jù)存入異常數(shù)據(jù)實(shí)時(shí)分析數(shù)據(jù)庫。

本文構(gòu)建的平臺(tái)框架在HDFS 上部署了Impala 實(shí)現(xiàn)數(shù)據(jù)探查、構(gòu)建區(qū)間位圖索引并定位異常數(shù)據(jù)區(qū)域。其中Impala 基于Hadoop 的SQL查詢性能，實(shí)時(shí)查詢HDFS中的實(shí)時(shí)點(diǎn)數(shù)據(jù)。借助于Imapalad 守護(hù)進(jìn)程，在每個(gè)DataNode 完成查詢點(diǎn)請(qǐng)求。查詢框架如圖2所示。

用戶發(fā)布的SQL 查詢請(qǐng)求任意空閑的Impalad節(jié)點(diǎn)，返回查詢id。而后Impalad執(zhí)行查詢分析，從元數(shù)據(jù)庫獲取元數(shù)據(jù)，從HDFS中獲取數(shù)據(jù)地址，得到該查詢相關(guān)的數(shù)據(jù)節(jié)點(diǎn)。Impalad 中的協(xié)調(diào)器coordinator 將查詢子任務(wù)分布到不同Impalad 節(jié)點(diǎn)，根據(jù)相關(guān)子任務(wù)請(qǐng)求完成相應(yīng)的執(zhí)行結(jié)果。查詢結(jié)束以后，需要單獨(dú)的子任務(wù)完成結(jié)果匯總，轉(zhuǎn)換為結(jié)果信息，用戶根據(jù)相應(yīng)的接口，讀取查詢結(jié)果。

應(yīng)用過程中，Impala 應(yīng)對(duì)海量數(shù)據(jù)場(chǎng)景，導(dǎo)致查詢出錯(cuò)的可能性較大，同時(shí)用于多維查詢中出錯(cuò)率較高。本次實(shí)驗(yàn)中對(duì)于探查數(shù)據(jù)的csv 文件，首先經(jīng)過區(qū)間位圖索引分類，對(duì)可能近似數(shù)據(jù)實(shí)現(xiàn)關(guān)鍵數(shù)據(jù)屬性連接，進(jìn)入異常檢測(cè)數(shù)據(jù)集，再應(yīng)用Impala完成搜索。

本實(shí)驗(yàn)數(shù)據(jù)采用真實(shí)的承德公交數(shù)據(jù)車輛GPS 數(shù)據(jù)和主要路口數(shù)據(jù)，其中車輛GPS 數(shù)據(jù)如表1信息，路口數(shù)據(jù)如表2信息。

表1 車輛GPS數(shù)據(jù)

表2 路口信息數(shù)據(jù)

數(shù)據(jù)采集過程中清洗掉由于客觀因素比如天氣，網(wǎng)絡(luò)通信影響，存儲(chǔ)平臺(tái)借助Impala 實(shí)時(shí)查詢框架，在實(shí)時(shí)上傳的數(shù)據(jù)中定位異常運(yùn)營車輛的基本信息。

本存儲(chǔ)平臺(tái)除了在存儲(chǔ)階段探查數(shù)據(jù)異常之外，主要目的是監(jiān)測(cè)運(yùn)行異常。運(yùn)行異常大致分為兩類，車輛異常和道路異常。這種異常是衡量運(yùn)營乘客滿意度和運(yùn)營成本的主要指標(biāo)。其中車輛異常主要包含有車速在不同路段之間的速度異常，以及相同線路車輛聚集異常等，道路異常主要為道路擁堵異常，造成車輛無法準(zhǔn)點(diǎn)進(jìn)站。本實(shí)驗(yàn)驗(yàn)證兩種異常事件：

（1）單點(diǎn)速度異常事件：公交車輛在不同形式路段的運(yùn)營速度超過平均速度或者同一線路車輛在運(yùn)營中同一線路、同一方向上車輛間距到達(dá)臨界值從而引發(fā)的異常。

（2）道路擁堵異常事件：公交車輛即將通過路口車輛密度到達(dá)臨界點(diǎn)引發(fā)的異常。這里僅僅針對(duì)路口進(jìn)行異常判斷，主要由于目前僅能收集主要路段的路口行車數(shù)據(jù)。

公交運(yùn)營過程受到司機(jī)主觀影響，因此異常數(shù)據(jù)是普遍存在的，在固定的時(shí)間周期內(nèi)海量數(shù)據(jù)中順序掃描異常數(shù)據(jù)，無疑耗費(fèi)大量的時(shí)間，因此掃描前數(shù)據(jù)過濾是非常有必要的。高強(qiáng)等［12］在數(shù)據(jù)處理關(guān)鍵技術(shù)提出了位圖索引過濾多維表的方案，在提升性能的設(shè)計(jì)方面具有很強(qiáng)的代表性。本文針對(duì)異常數(shù)據(jù)，建立區(qū)域編碼以及定點(diǎn)查詢連接機(jī)制，在實(shí)驗(yàn)分析部分展示了在此存儲(chǔ)平臺(tái)上查詢結(jié)果。

2 基于改進(jìn)位圖索引，構(gòu)建Impala查詢平臺(tái)

基于海量數(shù)據(jù)批處理查詢以及實(shí)時(shí)查詢效率的衡量，采用Impala 作為HDFS 上層數(shù)據(jù)探查。Impala 直接查詢HDFS 文件，查詢操作通過Impalad 服務(wù)，在內(nèi)存中完成查詢。查詢過程中，每個(gè)Impalad 的緩存會(huì)存儲(chǔ)最近加載的全部查詢表，可以實(shí)現(xiàn)實(shí)時(shí)任務(wù)交互。Espeholt等［13］針對(duì)Impala 性能測(cè)試分析，查詢最主要的挑戰(zhàn)就是內(nèi)存的容量。Impala 查詢中，Impalad 結(jié)點(diǎn)會(huì)緩存所有元數(shù)據(jù)，這樣方便了對(duì)同一個(gè)表重復(fù)查詢使用，但當(dāng)超出內(nèi)存容量時(shí)會(huì)直接報(bào)錯(cuò)。因此在查詢前，需要針對(duì)海量采集到的數(shù)據(jù)，利用區(qū)域位圖編碼，快速實(shí)現(xiàn)相關(guān)數(shù)據(jù)區(qū)域定位和多表連接。多維結(jié)構(gòu)中應(yīng)用位圖索引完成多表連接是可行的，賀智明等［14］、張延松等［15］都分別應(yīng)用了位圖索引解決了海量數(shù)據(jù)區(qū)域查詢?cè)O(shè)計(jì)方案。據(jù)此，本次實(shí)驗(yàn)將定時(shí)收集到的海量公交軌跡數(shù)據(jù)以及路口數(shù)據(jù)集成分類存儲(chǔ)，生成軌跡運(yùn)行屬性值。按照各個(gè)站點(diǎn)處于不同的路段，設(shè)置公交運(yùn)行速度時(shí)限，按照路段和速度時(shí)限完成位圖編碼，對(duì)采集的數(shù)據(jù)清洗，篩選出超出路段速度閾值的數(shù)據(jù)，同時(shí)根據(jù)相應(yīng)路段定位路口數(shù)據(jù)，連接篩選數(shù)據(jù)和路口數(shù)據(jù)建立新表。Impala 中通過設(shè)定SQL 語句，定位異常數(shù)據(jù)值。建立區(qū)域位圖索引的聚集方案為：

（1）根據(jù)歷史數(shù)據(jù)，將不同路段車輛準(zhǔn)點(diǎn)到站平均車速以及規(guī)定的最小速度作為不同街區(qū)各站點(diǎn)之間的閾值，為一個(gè)屬性區(qū)間C={(v1,v2),(v2,v3),….(vn-1,vn) }，該屬性描述了車輛在不同街區(qū)形式的正常速度區(qū)間分布，如果相應(yīng)速度在該區(qū)間之外，則為速度異常特征值。

（2）建立路段位置和速度變化區(qū)域的位圖索引，根據(jù)不同路口所在的街道，檢查車輛的速度是否超過閾值。所以每一個(gè)索引數(shù)據(jù)分成兩個(gè)部分，其中后三位為所在街道位置，其余位數(shù)為實(shí)時(shí)掃描速度，不同的街道速度監(jiān)測(cè)閾值不同。因此給定n個(gè)基數(shù){b1,b2,…,bn}，一個(gè)數(shù)據(jù)V可以分解為{v1,v2}，因此數(shù)據(jù)V的索引為

具體設(shè)計(jì)如表3所示。

表3 基于范圍位圖索引示例

（3）采集并過濾數(shù)據(jù)。利用上述位圖索引過濾數(shù)據(jù)集，上傳異常區(qū)域數(shù)據(jù)集。其中位圖索引篩選過程：首先確定路段位置，假定車輛速度在相應(yīng)標(biāo)準(zhǔn)范圍之外，則標(biāo)記為1，該數(shù)據(jù)上傳，否則標(biāo)記為0，放入等待區(qū)，接受批量上傳。

（4）在設(shè)定的范圍內(nèi)搜索異常點(diǎn)，按照key值存入Hbase 數(shù)據(jù)庫，可以直接定位相應(yīng)數(shù)據(jù)。考慮表的Rowkey 的長(zhǎng)短，采用路口標(biāo)識(shí)和車輛編號(hào)迭加車輛速度作為行鍵，存儲(chǔ)車輛GPS 數(shù)據(jù)。

以上的存儲(chǔ)設(shè)計(jì)，在數(shù)據(jù)上傳初期，利用位圖索引初步在海量數(shù)據(jù)中篩選區(qū)間異常數(shù)據(jù)，此時(shí)從數(shù)據(jù)中把可能異常數(shù)據(jù)篩選出來，縮小了后繼Impala 查詢的掃描區(qū)間，進(jìn)一步提升了掃描效率，同時(shí)避免了在Impala 的多表中查詢。在第一步索引中，以路段為關(guān)鍵字，聚集路口數(shù)據(jù)表中相應(yīng)路段數(shù)據(jù)，以速度關(guān)鍵字聚集軌跡數(shù)據(jù)中位置、速度、車輛信息關(guān)鍵字，直接組織異常文件的存儲(chǔ)結(jié)構(gòu)，在完成多維數(shù)據(jù)的位圖聚集上，進(jìn)一步提升Impala 的查詢速度，同時(shí)縮小了數(shù)據(jù)量。加入時(shí)間戳間隔控制，避免進(jìn)入內(nèi)存數(shù)據(jù)過大，減少了查詢出錯(cuò)出現(xiàn)的次數(shù)，提升了查詢效率。

3 存儲(chǔ)平臺(tái)性能測(cè)定

為了驗(yàn)證位圖索引預(yù)處理存儲(chǔ)平臺(tái)和Impala的查詢效率，實(shí)驗(yàn)的樣本集來源于承德公交2018 年5 月份一個(gè)月的路口數(shù)據(jù)和GPS 數(shù)據(jù)，為疫情前的正常實(shí)驗(yàn)數(shù)據(jù)，同時(shí)考慮到5 月份承德進(jìn)入旅游季，所有備用的公交車輛全部正常運(yùn)營，共包含872 萬條GPS 數(shù)據(jù)，以及2032萬條路口數(shù)據(jù)，實(shí)驗(yàn)測(cè)試了一個(gè)星期數(shù)據(jù)以及一個(gè)月的數(shù)據(jù)用于異常查詢中的性能分析，二者主要的區(qū)別是位圖索引的建立花費(fèi)的時(shí)間不同，同時(shí)比較了使用位圖索引和僅使用無索引Impala 在存儲(chǔ)框架上定位的速度。實(shí)驗(yàn)硬件環(huán)境包括3 臺(tái)內(nèi)存2 G 的計(jì)算機(jī)，軟件環(huán)境使用Ubuntu 16.04、Hadoop 2.2.0、JDK 1.6、Impala1.2.0搭建定點(diǎn)查詢模型。

其中定點(diǎn)查詢車輛語句：

范圍速度范圍語句：

加入位圖范圍索引以后，減少了掃描區(qū)域，提升查詢性能，以公交一個(gè)月數(shù)據(jù)為例，實(shí)際查詢性能如圖3所示。

圖3 查詢性能結(jié)果

為了獲得更正確的結(jié)果，實(shí)驗(yàn)中的數(shù)據(jù)為同樣測(cè)試執(zhí)行10 次后查詢時(shí)間的平均值。同樣循環(huán)查詢測(cè)試了Impala 錯(cuò)誤中斷次數(shù)，改進(jìn)后Impala 在運(yùn)行1 天時(shí)間內(nèi)，錯(cuò)誤中斷次數(shù)為0，這為后續(xù)數(shù)據(jù)分析平臺(tái)穩(wěn)定運(yùn)行提供了基礎(chǔ)。

4 結(jié)語

在公交運(yùn)營透明化的趨勢(shì)下，精準(zhǔn)的運(yùn)營分析是乘客和公交企業(yè)共同的期盼，是智慧公交最終的目的。智慧公交的大腦，來源于海量歷史數(shù)據(jù)的分析和實(shí)時(shí)數(shù)據(jù)的精準(zhǔn)定位。本文通過在公交集團(tuán)云存儲(chǔ)平臺(tái)上模擬精準(zhǔn)定位實(shí)時(shí)分析，應(yīng)用Hadoop 平臺(tái)，來源于歷史數(shù)據(jù)的標(biāo)準(zhǔn)設(shè)定，改進(jìn)了基于范圍區(qū)間的位圖索引，預(yù)先構(gòu)建頻繁查詢數(shù)據(jù)集，進(jìn)入HDFS 存儲(chǔ)層，供給上部Impala 定位查詢，產(chǎn)生異常數(shù)據(jù)存儲(chǔ)Hbase數(shù)據(jù)庫，實(shí)現(xiàn)異常數(shù)據(jù)的存儲(chǔ)和實(shí)時(shí)數(shù)據(jù)發(fā)布。實(shí)驗(yàn)中可見在查找成功前提下，改進(jìn)后的平臺(tái)在查詢定位速度以及出錯(cuò)率上有了很大的改進(jìn)。為后一步的精準(zhǔn)調(diào)度奠定了數(shù)據(jù)基礎(chǔ)。