車載自組織網(wǎng)絡(luò)中車輛路徑預(yù)測序列模式數(shù)據(jù)挖掘方法＊

張宏

（1.內(nèi)蒙古大學(xué)，呼和浩特 010070；2.內(nèi)蒙古自治區(qū)城市交通數(shù)據(jù)科學(xué)及應(yīng)用工程技術(shù)研究中心，呼和浩特 010070）

主題詞：車輛路徑預(yù)測 車輛行駛路徑序列 序列模式 車載自組織網(wǎng)絡(luò) 數(shù)據(jù)挖掘

1 前言

車輛行駛期間獲得車輛的預(yù)計(jì)行駛路徑和目的地是避免事故發(fā)生的有效手段之一[1]，為此，國內(nèi)外學(xué)者開展了車輛路徑預(yù)測研究。路徑預(yù)測主要方法有線性函數(shù)、貝葉斯網(wǎng)絡(luò)模型、馬爾科夫鏈模型、高斯混合模型等。Pan 等人[2]借助多變元正態(tài)分布提出線性預(yù)測方法，但該模型預(yù)測有時(shí)間延遲，無法實(shí)時(shí)監(jiān)控交通流環(huán)境；Li等人[3]提出了改進(jìn)貝葉斯推理方法，將歷史軌跡分解，構(gòu)建更精確的馬爾科夫模型，提高了預(yù)測精度和算法效率；Jing Yuan 等人[4]利用馬爾科夫概率模型構(gòu)建了車輛路徑預(yù)測算法模型，短距離預(yù)測準(zhǔn)確率較高，但不適用于遠(yuǎn)距離車載自組織網(wǎng)絡(luò)交通信息服務(wù)；Qiao 等人[5]提出了基于馬爾科夫模型的自適應(yīng)動態(tài)軌跡預(yù)測算法，該模型通過不同類型軌跡預(yù)測最優(yōu)路線，但未考慮大數(shù)據(jù)環(huán)境下算法的運(yùn)行效率；Dai 等人[6]基于高斯混合模型和最短路徑算法，考慮軌跡大數(shù)據(jù)中個(gè)性化行駛偏好概率問題，提出了帶權(quán)重的軌跡圖，使用該算法對多模式運(yùn)動路徑進(jìn)行預(yù)測，但不適用于復(fù)雜場景。由上述分析可知，大多數(shù)算法對單一車輛運(yùn)動模式預(yù)測準(zhǔn)確性較好，針對大量復(fù)雜歷史軌跡數(shù)據(jù)挖掘頻繁模式，需多次掃描數(shù)據(jù)庫，效率和準(zhǔn)確性不能兼顧，所以需構(gòu)建新型數(shù)據(jù)頻繁模式挖掘算法，提高數(shù)據(jù)挖掘的準(zhǔn)確性和效率。

車載自組織網(wǎng)絡(luò)（Vehicular Ad-hoc Networks，VANET）涉及移動車輛信息交換，是車聯(lián)網(wǎng)技術(shù)的基礎(chǔ)，在VANET 中，利用序列模式進(jìn)行車輛路徑預(yù)測，需要收集車輛歷史移動軌跡數(shù)據(jù)。序列模式數(shù)據(jù)挖掘方法主要收集事件集的時(shí)間序列[7-8]，事件集為車輛駛過的路段。本文通過建立車輛歷史序列模式數(shù)據(jù)庫，利用數(shù)據(jù)挖掘技術(shù)，實(shí)時(shí)跟蹤車輛，建立行駛檔案，以預(yù)測車輛未來行駛軌跡。

2 車載自組織網(wǎng)絡(luò)體系結(jié)構(gòu)

車載自組織網(wǎng)絡(luò)由安裝了車載單元（On Board Unit，OBU）的一組車輛和路側(cè)單元（Road Side Unit，RSU）組成，如圖1 所示。部分RSU 還可連接其他網(wǎng)絡(luò)（例如Internet），OBU 利用無線網(wǎng)絡(luò)在有效連通范圍內(nèi)直接連接到其他車輛和RSU。車載自組織網(wǎng)絡(luò)可支持道路安全、信息娛樂、道路交通優(yōu)化等各種應(yīng)用[9]。

圖1 車載自組織網(wǎng)絡(luò)體系結(jié)構(gòu)

VANET有3種連接方式，如圖2所示。自組織模式下，車對車（Vehicle to Vehicle，V2V）連接在車輛與車輛間提供通訊，發(fā)送、接收或交換有價(jià)值的交通信息，如交通擁堵、交通事故等。車輛對基礎(chǔ)設(shè)施（Vehicle to Infrastructure，V2I）連接用于在網(wǎng)絡(luò)基礎(chǔ)設(shè)施與車輛之間廣播關(guān)鍵信息，也可用于道路條件和安全問題等重要信息的傳達(dá)，在這種通訊類型中，車輛與RSU 創(chuàng)建連接，并可連接到Internet等外部網(wǎng)絡(luò)。V2I連接不易受到攻擊，較V2V連接需更大帶寬[10]。在VANET中，車內(nèi)連接可確認(rèn)車輛性能和駕駛員行為，對公共安全至關(guān)重要。在車輛對寬帶（Vehicle to Broadband，V2B）連接中，車輛可以通過4G、5G網(wǎng)絡(luò)與無線寬帶系統(tǒng)連接。因?qū)拵г瓢嘟煌ㄐ畔?、監(jiān)控?cái)?shù)據(jù)和娛樂信息，所以V2B連接對主動駕駛輔助和車輛跟蹤作用較大。

圖2 車載自組網(wǎng)中的連接類型

3 運(yùn)動模式描述與定義

序列模式挖掘算法最早由Agrawal和Srikant提出[11]。時(shí)序模型在很多不同領(lǐng)域已有應(yīng)用，為將時(shí)序模型應(yīng)用于車載自組織網(wǎng)絡(luò)，需對VANET 中車輛移動行為進(jìn)行描述和定義?；谖墨I(xiàn)[12]，描述和定義如下：

a.M={M1,M2,…,Mi,…}為道路節(jié)點(diǎn)集合，一條路段可表示為2個(gè)連續(xù)的道路節(jié)點(diǎn)之間的單項(xiàng)邊。本文中，交叉口也被認(rèn)為是道路路段的一部分，還可表示道路的末端、出口等，交叉口可連接2個(gè)或多個(gè)路段。

b.V={V1,V2,…,Vi,…}表示給定地理區(qū)域內(nèi)行駛一定時(shí)間的一組車輛。Y=[M1Mi…Mn]表示車輛運(yùn)動序列模式，即車輛Vi在特定地理區(qū)域內(nèi)行駛期間所經(jīng)過的路段節(jié)點(diǎn)。建立車輛移動數(shù)據(jù)庫，將其行駛路段以運(yùn)動模式存儲在數(shù)據(jù)庫中。若Y′模式包含Y中路段元素，順序也相同，則Y稱為Y′的子模式。如運(yùn)動模式[M4M5M7]為[M2M4M5M7]和[M1M4M5M7M9]的子模式，但因運(yùn)動模式順序不同，所以不是[M2M4M5M6M7]的子模式。運(yùn)動模式Y(jié)的支持度用S(Y)表示，定義為移動數(shù)據(jù)庫中運(yùn)動模式Y(jié)及含有子模式Y(jié)′的運(yùn)動模式的數(shù)量。

c.運(yùn)動規(guī)則R定義為關(guān)聯(lián)規(guī)則Y1?Y2，設(shè)R的支持度為S(Y1?Y2)，Y1和Y2是Y的子模式，且二者間沒有共同的路段，則運(yùn)動規(guī)則R的置信度c(R)定義為：

規(guī)則由數(shù)據(jù)庫中的運(yùn)動模式生成，如運(yùn)動模式Y(jié)=[M2M3M4M5]的規(guī)則集可能為[M2]?[M3M4M5]、[M2M3]?[M4M5]、[M2M3M4]?[M5]。

若c([M1M2]?[M3])=2/3，則表示正在路段M1M2上的車輛有2/3的概率到達(dá)路段M2M3。

4 車輛路徑數(shù)據(jù)收集及分析

首先收集車輛行為，建立移動數(shù)據(jù)庫，生成移動模式。常用運(yùn)動模式提取依賴于一段時(shí)間內(nèi)收集的歷史移動信息。在收集全部車輛路徑并確定最小支持閾值后，可提取行駛最頻繁的車輛路徑，將其作為車輛運(yùn)動模式。通信方式有基于RSU和車輛兩種方案。基于車輛收集路徑信息方案也稱為全路徑方案，分為廣播模式和發(fā)現(xiàn)模式。在方案實(shí)施過程中，RSU分布在各地理區(qū)域內(nèi)，互相組合連通，增加網(wǎng)絡(luò)拓?fù)涞倪B通性，使信號覆蓋所有路段。每輛車可使用地圖匹配技術(shù)檢測新路段，每個(gè)RSU負(fù)責(zé)跟蹤附近車輛發(fā)送的部分路徑。

車輛作為移動節(jié)點(diǎn)，利用車載網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)傳遞，可減少RSU部署數(shù)量和網(wǎng)絡(luò)開銷，如圖3所示。

圖3 方案場景示意

在混合交通中，數(shù)據(jù)傳輸執(zhí)行效率與環(huán)境密切相關(guān)，傳遞隨機(jī)性較強(qiáng)，而有目的的數(shù)據(jù)傳輸存在時(shí)間較長和數(shù)據(jù)抖動問題，可能導(dǎo)致信息傳輸失敗，為提高數(shù)據(jù)傳輸?shù)竭_(dá)率和準(zhǔn)確性，需在熱點(diǎn)位置部署少量RSU，由RSU存儲關(guān)鍵數(shù)據(jù)并傳遞給目標(biāo)車輛。

車輛路徑選擇會受到駕駛員主觀能動性影響，駕駛員在選擇出行路徑時(shí)會綜合考慮道路條件、交通狀態(tài)、出行目的等多種因素，本文通過前期問卷調(diào)查，統(tǒng)計(jì)分析車輛軌跡信息，結(jié)果表明，私家車動態(tài)運(yùn)動軌跡遵循一定規(guī)律，可預(yù)測性為89%，并且行駛路徑與距離無關(guān)。

私家車、出租車和公交車對車流量的貢獻(xiàn)較大，對其進(jìn)行軌跡預(yù)測能較好地掌握車流量及行駛方向。本文的數(shù)據(jù)來源于“中國工況”項(xiàng)目組內(nèi)蒙古地區(qū)私家車、出租車和公交車共94輛車記錄的GPS移動信息[13-14]。

5 車輛路徑預(yù)測與方案評估

5.1 車輛路徑預(yù)測

根據(jù)車輛序列模式特點(diǎn)，相鄰兩項(xiàng)為道路節(jié)點(diǎn)，對呼和浩特市路段進(jìn)行整理和劃分，用復(fù)雜網(wǎng)絡(luò)理論將路段抽象為邊，交叉口抽象為點(diǎn)，生成城市道路網(wǎng)絡(luò)拓?fù)鋱D，如圖4所示。

圖4 呼和浩特市主干路網(wǎng)

車輛路徑序列具有典型的時(shí)間特征，根據(jù)期望的最小延遲進(jìn)行車輛路徑預(yù)測，可采用廣義序列模式（Generalized Sequential Pattern，GSP）算法對序列模式進(jìn)行挖掘。其核心思想為反復(fù)掃描直到滿足預(yù)先設(shè)置的最小支持度，為加快循環(huán)進(jìn)程和避免死循環(huán)，需對所有子序列均不滿足最小支持度的候選序列進(jìn)行修剪。

車輛路徑預(yù)測具有規(guī)律性，將數(shù)據(jù)庫中車輛歷史路徑序列作為規(guī)則前件，預(yù)測車輛行駛路徑序列作為規(guī)則后件。前件與后件的路徑關(guān)聯(lián)規(guī)則由具有方向性的路徑序列模式?jīng)Q定。

為簡化說明計(jì)算原理，建立模擬交通網(wǎng)絡(luò)圖，并進(jìn)行編號，示例如圖5 所示，構(gòu)建相應(yīng)的車輛行駛路徑數(shù)據(jù)庫如表1所示。

圖5 呼和浩特市中心城區(qū)部分主干路路網(wǎng)

以表1所示數(shù)據(jù)庫為例，首先掃描數(shù)據(jù)序列獲得序列1 的模式Y(jié)1，通過序列模式函數(shù)繼續(xù)掃描由序列k的模式Y(jié)k生成序列(k+1)的候選模式Hk+1，計(jì)算其支持度，若滿足要求，則Yk+1=Hk+1，繼續(xù)循環(huán)掃描，直至無新的序列模式產(chǎn)生。設(shè)最小支持度為3，符合最小支持度的車輛行駛路徑序列1 的模式及相應(yīng)的支持度為[A]（5）、[B]（6）、[C]（7）、[E]（3）、[F]（8）、[G]（9）、[H]（3）、[K]（3）。由序列1的模式生成序列2的候選模式時(shí)，因支持度較小、序列較多，會生成大量候選序列和冗余序列，大幅增加了掃描時(shí)間，所以考慮交通網(wǎng)絡(luò)實(shí)際意義和提高算法的性能，僅連接交叉路口的相鄰路段，如圖5 中[C]路徑模式僅與[B]、[G]、[D]連接，生成候選模式為[CB]、[CG]和[CD]。

表1 車輛行駛數(shù)據(jù)庫示例

對長度大于3的路徑模式生成關(guān)聯(lián)規(guī)則，計(jì)算置信度，建立關(guān)聯(lián)規(guī)則數(shù)據(jù)庫。

本文使用NS-2（Network Simulator 2）環(huán)境，在尺寸為800 m×800 m 的2D 網(wǎng)格地圖上進(jìn)行仿真，RSU 安裝場景如圖2所示。使用不同路徑定義車輛行駛軌跡，為符合實(shí)際場景，保證數(shù)據(jù)收集有效性，在某些場景中需手動生成移動車輛，路徑大小表示車輛駛過的路段數(shù)量。為在密集場景中確保方案精確，隨機(jī)生成的路徑執(zhí)行其余仿真。仿真參數(shù)如表2所示。

表2 模擬參數(shù)

仿真過程中對通信開銷進(jìn)行評估，在不同路徑大小和車輛數(shù)量下進(jìn)行測量。對于路徑大小，逐漸增加路段數(shù)量，將若干車輛設(shè)置為逐漸駛過這些路段。收集仿真過程中交換的信息數(shù)量，并將其視為與路徑大小相關(guān)的通信開銷。由于數(shù)據(jù)收集過程中主要收集車輛路徑，而路徑中的路段數(shù)量會發(fā)生變化，因此需要評估方案效率。針對車輛數(shù)量進(jìn)行研究的目的是測量只有車輛密度變化的情況下發(fā)生的開銷。針對路徑大小，每次增加5段路徑，直至20段，針對車輛數(shù)量，每次增加10輛車，直至60 輛，測量不同路徑大小和車輛數(shù)量下車輛與RSU之間相互發(fā)送消息的總量，結(jié)果如圖6、圖7所示。

圖6 不同路徑大小和車輛數(shù)量下的網(wǎng)絡(luò)開銷

圖7 不同車輛數(shù)量下的RSU 通信開銷和車輛通信開銷（路徑大小為10）

由圖6 可知，通信開銷隨路徑的增加而增加，由于其取決于RSU 發(fā)送的消息數(shù)量，所以開銷較大。不論附近是否有移動車輛，RSU每隔10 s均會廣播一次信標(biāo)消息，造成了大量無效通信開銷。

由圖7 可知，隨著車輛數(shù)量的增加，多個(gè)路段中通信開銷逐漸增大，RSU 開銷占比較大，車輛發(fā)送的消息明顯較RSU少，因此需對RSU增加的開銷進(jìn)行分析。

為檢驗(yàn)結(jié)果，多次試驗(yàn)取平均值，并進(jìn)行方差分析。路徑大小和車輛密度的通信開銷平均值如圖8 所示。本文對路段、車輛每個(gè)變量運(yùn)行10次后提取結(jié)果，并計(jì)算平均值，經(jīng)方差分析檢驗(yàn)，其差異顯著性＜0.05。

圖8 平均通信開銷

實(shí)際使用中，采用V2V 方式時(shí)必須保證目標(biāo)車輛與上一跳車輛恰好相遇才能傳遞數(shù)據(jù)，出租車和私家車行駛路線不固定，需要部署在交叉口的RSU幫助傳遞，否則車輛行駛路線和運(yùn)行時(shí)間的不確定性難以保證數(shù)據(jù)及時(shí)交換。

5.2 支持度和置信度評估

車輛路徑數(shù)據(jù)按時(shí)間排列事件的形式進(jìn)行收集，即順序模式，按照序列屬性進(jìn)行分類分析，支持度和置信度是其重要指標(biāo)。

為挖掘序列模式，首先需設(shè)定最小支持度。對車輛行駛過程中可能行駛的路徑定義一組最小支持度，并記錄最小支持度在所收集運(yùn)動模式中出現(xiàn)的次數(shù)。分析運(yùn)動模式數(shù)據(jù)庫，最小支持度為1、2、3、4和5運(yùn)動模式出現(xiàn)的次數(shù)分別為12513、10657、59264、35782、89。隨最小支持度的增加，運(yùn)動模式數(shù)據(jù)庫中作為子模式出現(xiàn)的運(yùn)動模式的次數(shù)降低。為在預(yù)測和檢測階段提高準(zhǔn)確性，可分別設(shè)置最小支持度，以便發(fā)現(xiàn)非常頻繁運(yùn)動模式，但會忽略一些對車輛路徑預(yù)測有利的非常頻繁模式。

挖掘序列模式時(shí)也需考慮與生成規(guī)則相關(guān)的置信度。此規(guī)則定義為基于已發(fā)生的特定事件序列而產(chǎn)生的不同序列模式事件集。在提取頻繁序列模式后，需為所有可能的子模式生成運(yùn)動模式，通過計(jì)算某一運(yùn)動規(guī)則的置信度，得到基于前序序列事件發(fā)生某一事件的概率。例如：在圖5 所示的EF路段，在F十字路口，會產(chǎn)生4條規(guī)則：

規(guī)則1：[MEMF]?[MB]（向左轉(zhuǎn)）；

規(guī)則2：[MEMF]?[MJ]（向右轉(zhuǎn)）；

規(guī)則3：[MEMF]?[MG]（直行）；

規(guī)則4：[MEMF]?[MF]（在交叉口停留）。

計(jì)算4 條規(guī)則的置信度，結(jié)果為分別13.32%、37.93%、41.14%、7.61%。規(guī)則1 的置信度為13.32%，表示在數(shù)據(jù)庫的模式中，記錄了13.32%的車輛從EF路段左轉(zhuǎn)彎的情況。

6 結(jié)束語

本文將車載自組織網(wǎng)絡(luò)拓?fù)渑c實(shí)際道路車輛運(yùn)動路徑相結(jié)合，提出一些VANET環(huán)境下序列模式定義，采用基于路側(cè)單元和基于車輛兩種方案收集車輛路徑信息，通過歷史車輛路徑數(shù)據(jù)進(jìn)行序列模式數(shù)據(jù)挖掘，對未來車輛路徑預(yù)測提供準(zhǔn)確支持。仿真過程中在不同路徑大小和車輛數(shù)量下評估了網(wǎng)絡(luò)通信開銷，隨著路徑大小和車輛數(shù)量的增加，通信開銷逐漸增大，其中RSU開銷占比較大。評估了由頻繁運(yùn)動模式生成的運(yùn)動規(guī)則置信度，并可計(jì)算出每個(gè)規(guī)則的概率。然而本文車載自組織網(wǎng)絡(luò)數(shù)據(jù)傳遞延遲較高，需進(jìn)一步挖掘?qū)煌ㄓ兄匾绊懙能囕v時(shí)空特性，找出其穩(wěn)定規(guī)律。