車聯(lián)網(wǎng)數(shù)據(jù)聚集研究綜述

馮強(qiáng) 馮誠 李治軍 姜守旭

摘 要：當(dāng)今，車聯(lián)網(wǎng)是實現(xiàn)智能交通應(yīng)用的平臺。車聯(lián)網(wǎng)有著特殊的網(wǎng)絡(luò)特征，使得其上的數(shù)據(jù)聚集算法不同現(xiàn)有的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)聚集。數(shù)據(jù)聚集可以有效地降低傳輸過程中的數(shù)據(jù)量，但同時亦會引起數(shù)據(jù)時延的增加和數(shù)據(jù)精度的降低。因此聚集算法往往考慮聚集數(shù)據(jù)的時延和精度。本文對現(xiàn)有的車聯(lián)網(wǎng)聚集算法進(jìn)行綜述分析。

關(guān)鍵詞：車聯(lián)網(wǎng)；數(shù)據(jù)聚集；數(shù)據(jù)質(zhì)量；無線移動感知網(wǎng)絡(luò)

中圖分類號：TP391 文獻(xiàn)標(biāo)識號：A

Abstract： Today， VANET is the platform of achieving intelligent transportation system. VANETs has its own characters. Data aggregation algorithms in VANETs are different from in wireless sensor networks. Data aggregation can decrease the amount of data transmission， also can increase the delay of aggregated data and decrease the accuracy of aggregated data. Therefore， aggregation algorithm always consider the delay and accuracy of aggregated data. The paper surveys and analyzes current data aggregation algorithms in VANETs

Keywords： VANETs； Data Aggregation； Quality of Data； Wireless Mobile Sensor Networks

0 引 言

目前物聯(lián)網(wǎng)的研究已經(jīng)覆蓋到市政、交通、物流運輸、醫(yī)療、教育、工農(nóng)業(yè)生產(chǎn)等諸多領(lǐng)域。物聯(lián)網(wǎng)在交通領(lǐng)域的重要分支即為車聯(lián)網(wǎng)（Internet of Vehicles）[1， 2]。車聯(lián)網(wǎng)為物聯(lián)網(wǎng)時代下的智能交通系統(tǒng)（Intelligent Transportation System） [3] 提供了實現(xiàn)的平臺。車聯(lián)網(wǎng)是智能車之間以及智能車與路邊設(shè)備之間通過無線通信形成的移動通信網(wǎng)絡(luò)。車聯(lián)網(wǎng)可用于協(xié)助駕駛者及時躲避交通事故，提高交通運輸?shù)男?，監(jiān)控實時交通狀況等。車聯(lián)網(wǎng)改變了現(xiàn)有交通管理監(jiān)控的技術(shù)框架，利用交通參與的主體（如車輛、乘客、行人、路邊設(shè)備等）自主感知交通狀況，實現(xiàn)了人與物理世界的緊密交互和融合。

1 車聯(lián)網(wǎng)

車聯(lián)網(wǎng)，又被稱為車用自組織網(wǎng)絡(luò)（Vehicular Ad-hoc Networks， VANETs） [4]或車載感知網(wǎng)絡(luò)（Vehicular Sensor Networks， VSNs）[5]， 由車輛節(jié)點自組織形成車與車之間（Vehicle to Vehicle， V2V） [6] 以及車與基礎(chǔ)設(shè)施之間（Vehicle to Infrastructure， V2I）[6] 的異構(gòu)通信網(wǎng)絡(luò)。車聯(lián)網(wǎng)的結(jié)構(gòu)如圖1所示。這是一種無線移動感知通信網(wǎng)絡(luò)。通常每個車輛節(jié)點裝配無線通信設(shè)備，GPS定位設(shè)備以及各種傳感器設(shè)備（如加速度傳感器、速度傳感器等）。邏輯上智能車有兩種單元：操控單元（on-board unit， OBU） 和應(yīng)用單元（Application Unit， AU）。操控單元通常有獲取感知數(shù)據(jù)，定位，以及無線和/或有線通信功能。應(yīng)用單元通常由便攜式設(shè)備構(gòu)成，如筆記本電腦、個人數(shù)據(jù)處理機(jī)（Personal Digital Assistant， PDA）等，是智能車的附屬部分。具體功能是利用操控單元獲取信息開發(fā)和實現(xiàn)具體應(yīng)用。操控單元和應(yīng)用單元可以通過有線互連，也可以采用無線方式，如藍(lán)牙（Bluetooth）、無線USB（Wireless USB， WUSB）等。智能車的結(jié)構(gòu)如圖2所示。

1.1 車聯(lián)網(wǎng)的歷史

VANET的概念最早是在2003 年由國際電信聯(lián)盟的汽車通信標(biāo)準(zhǔn)化會議上被正式提出。但關(guān)于VANET的研究卻是由來已久。1986 年在歐洲PROMETHEUS（Programme for European Traffic with Highest Efficiency and Un-precedented Safety）即已獲得提出。該框架一經(jīng)提出就被19個歐洲國家以及歐盟委員會接受并實現(xiàn)支持。進(jìn)入90 年代，人們集中在協(xié)同駕駛應(yīng)用研究上。1996年到2000年期間日本Tsukuba市部署ASV（Advanced Safety Vehicle）項目[7]。1997年San Diego部署了PATH（California Partners for Advanced Transit and Highways）[8]。1999 年美國聯(lián)邦通信委員會在5.9GHz頻帶上分配了75MHz帶寬的信道給車與路邊設(shè)備之間的短距離無線通信（Dedicated Short-Range Communication，DSRC）[9]。這使得VANET的概念再次得到了工業(yè)界的廣泛關(guān)注。同時多個標(biāo)準(zhǔn)化組織也開始積極為DSRC制定通信協(xié)議標(biāo)準(zhǔn)。2004年IEEE 提出基于802.11p協(xié)議的WAVE（Wireless Access in Vehicular Environment）標(biāo)準(zhǔn)[10]。2000年到2005年期間美國的IVI（Intelligent Vehicle Initiative），歐洲的CarTalk和FleetNet以及日本的ASV三期項目均把研究熱點從協(xié)作式自動駕駛轉(zhuǎn)向協(xié)作式駕駛操作。ISO（International Standard Organization） 提出了CALM（Continuous Air interface for Long and Medium distance）標(biāo)準(zhǔn)。基于該標(biāo)準(zhǔn)歐洲在2006年到2010年之間開展了幾個主要項目：COOPERS、PReVENT、SeVeCom、NoW和PRE-DRIVE。

1.2 車聯(lián)網(wǎng)的特點

車聯(lián)網(wǎng)與其他的移動網(wǎng)絡(luò)和通信網(wǎng)絡(luò)相比，具有一些優(yōu)勢和挑戰(zhàn)。在此，分析總結(jié)為如下幾點。

（1）無限制的節(jié)點能量。與傳統(tǒng)的感知網(wǎng)絡(luò)相比，車聯(lián)網(wǎng)移動設(shè)備的能量問題通常不是一個重要的限制條件，車輛本身能夠給計算和通信設(shè)備提供持續(xù)的能量。

（2）更強(qiáng)的計算能力。相對于傳感器節(jié)點等小型設(shè)備，車輛節(jié)點可以提供更強(qiáng)的計算、通信和感知能力。

（3）可預(yù)測的移動性。不同于傳統(tǒng)移動自組織網(wǎng)絡(luò)，車輛節(jié)點的移動受限于道路網(wǎng)絡(luò)，因此車輛節(jié)點的運動具有很好的可預(yù)測性。道路網(wǎng)絡(luò)信息通常是可得的，且車輛的位置信息可以通過GPS獲得。因此根據(jù)車輛的平均速度，當(dāng)前瞬時速度和歷史軌跡可以預(yù)測車輛在未來時間出現(xiàn)的位置。

（4）大規(guī)模的節(jié)點分布。車聯(lián)網(wǎng)原則上可以擴(kuò)展到整個道路網(wǎng)絡(luò)上，并且有眾多參與者，包括路面上的車輛，路邊?？康能囕v，路邊設(shè)備等，而之前研究的自組織網(wǎng)絡(luò)通常假設(shè)存在于局部有限的空間范圍。

（5）高移動性。車聯(lián)網(wǎng)中的大部分車輛節(jié)點都在高速移動，而且車輛之間的相對速度范圍很大。在高速公路上，相對速度可以達(dá)到300km/h，這時節(jié)點的密度可能很低；在城市交通中，相對速度可以到60km/h，這時節(jié)點的密度會很高。

（6）通信網(wǎng)絡(luò)的不可連通性。車聯(lián)網(wǎng)通常瞬時是不連通的，交通的動態(tài)性導(dǎo)致在稀疏交通場景下車輛之間存在大的間隙，從而形成多個孤立的節(jié)點簇。節(jié)點連通程度高度依賴于兩個因素：無線鏈路的通信半徑和加入車聯(lián)網(wǎng)的車輛比例。

（7）網(wǎng)絡(luò)拓?fù)涞膭討B(tài)性。與傳統(tǒng)的自組織網(wǎng)絡(luò)相比，車聯(lián)網(wǎng)的車輛節(jié)點一直在移動，因此車聯(lián)網(wǎng)場景具有很強(qiáng)的動態(tài)性。具體表現(xiàn)在節(jié)點之間的無線鏈路時斷時續(xù)，網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化頻繁。

1.3 車聯(lián)網(wǎng)的應(yīng)用

車聯(lián)網(wǎng)上的應(yīng)用主要分為三大類，一是與行駛安全相關(guān)的應(yīng)用，二是交通管理和協(xié)調(diào)的應(yīng)用，三是與娛樂相關(guān)的應(yīng)用。其中，與行駛安全相關(guān)的應(yīng)用主要用于降低交通事故發(fā)生的概率，減少交通事故中的人員傷亡。這類應(yīng)用通過及時向用戶提供周圍交通情況信息，從而協(xié)助用戶避免交通事故，例如變車道警示、追尾警示。而交通管理和協(xié)調(diào)應(yīng)用則集中在提高交通流量，協(xié)調(diào)交通流有序流暢運行，以及為車輛提供實時交通狀況信息用于實時導(dǎo)航。這類應(yīng)用有合作式導(dǎo)航、速度管理等。另外，娛樂相關(guān)的應(yīng)用主要是為乘客提供Internet連接服務(wù)進(jìn)行線上游戲或資訊下載，例如廣告推送、在線游戲等。

2 車聯(lián)網(wǎng)上的數(shù)據(jù)聚集

車聯(lián)網(wǎng)上的數(shù)據(jù)聚集是近年來車聯(lián)網(wǎng)上的研究熱點。數(shù)據(jù)聚集是車聯(lián)網(wǎng)上數(shù)據(jù)收集和分發(fā)過程中的一個核心技術(shù)。常見的聚集操作有以下幾種，MAX（求最大值）、MIN（求最小值）、SUM（求和）、COUNT（計數(shù)）、AVERAGE（求平均值）、MEDIAN（求中位數(shù)） 等[11]。網(wǎng)內(nèi)聚集是在網(wǎng)絡(luò)內(nèi)部傳輸數(shù)據(jù)的過程中同時進(jìn)行聚集操作，不斷傳輸中間聚集結(jié)果，并將最終聚集結(jié)果傳輸?shù)綌?shù)據(jù)中心或網(wǎng)絡(luò)內(nèi)的其他移動節(jié)點。網(wǎng)內(nèi)數(shù)據(jù)聚集技術(shù)可以有效減少傳輸過程中的數(shù)據(jù)量，并充分利用動態(tài)帶寬資源，減輕網(wǎng)絡(luò)的數(shù)據(jù)傳輸負(fù)擔(dān)。同時聚集技術(shù)也會影響數(shù)據(jù)的精度和時延。因此，現(xiàn)有的車聯(lián)網(wǎng)數(shù)據(jù)聚集研究主要分為以下兩類，一是權(quán)衡聚集數(shù)據(jù)的延遲和聚集收益的優(yōu)化，二是權(quán)衡聚集數(shù)據(jù)的精度和聚集收益的優(yōu)化。

2.1 基于車聯(lián)網(wǎng)上考慮聚集數(shù)據(jù)時延的聚集算法研究

車聯(lián)網(wǎng)考慮時延的聚集算法主要針對聚集傳輸?shù)臅r刻進(jìn)行研究。文獻(xiàn)[11-12] 考慮的就是如何設(shè)定數(shù)據(jù)在節(jié)點的轉(zhuǎn)發(fā)延遲，使得可聚合的數(shù)據(jù)在同一節(jié)點相遇的概率最大。該文提出的CatchUp算法中的每個節(jié)點根據(jù)自己的局部試圖利用分布式的馬爾可夫決策過程模型判斷每個時間周期對數(shù)據(jù)是否需要轉(zhuǎn)發(fā)，使得數(shù)據(jù)在節(jié)點等待與自己可以聚合的數(shù)據(jù)的到來。文獻(xiàn)[13]研究的是限定截止時間內(nèi)的優(yōu)化收集聚集信息量問題，為此提出DB-VDG協(xié)議，該協(xié)議通過調(diào)整數(shù)據(jù)傳輸過程中的轉(zhuǎn)發(fā)和攜帶策略使得在截止時間內(nèi)AP節(jié)點收集的數(shù)據(jù)量最多。又提出了一個查詢響應(yīng)協(xié)議DB-VDG，該協(xié)議的主要設(shè)計思想是數(shù)據(jù)如果能在限定的延遲內(nèi)被攜帶到目的地，就盡量少進(jìn)行轉(zhuǎn)發(fā)，這樣可以最大限度地節(jié)省帶寬?，F(xiàn)有的車聯(lián)網(wǎng)上考慮時延的數(shù)據(jù)聚集算法沒有分析利用車聯(lián)網(wǎng)的動態(tài)通信拓?fù)湫畔?，也沒有深入地規(guī)劃和利用無線信道資源，因此現(xiàn)有算法并未從根本上解決基于時延界的聚集問題。

2.3 基于車聯(lián)網(wǎng)上考慮聚集數(shù)據(jù)精度的聚集算法研究

下面，將專題分析和總結(jié)考慮聚集數(shù)據(jù)精度的聚集技術(shù)的研究。根據(jù)具體的應(yīng)用區(qū)別，聚集數(shù)據(jù)的類型分為離散型數(shù)據(jù)（如空閑停車位數(shù)） 和連續(xù)型數(shù)據(jù)（如平均速度等）。離散型數(shù)據(jù)的聚集需要解決的核心問題是如何避免對同一數(shù)據(jù)進(jìn)行重復(fù)聚集操作，而連續(xù)型數(shù)據(jù)的聚集需要考慮如何減小聚集操作引起的數(shù)值上的偏差。

文獻(xiàn)[14–16] 研究的是空閑停車位信息的聚集問題。文獻(xiàn)[14] 利用quad樹結(jié)構(gòu)對空閑停車位數(shù)進(jìn)行層次型聚集。該文利用quad樹對二維空間實施了層次性劃分，然后將各區(qū)域的空閑停車位信息實現(xiàn)了累加聚集。文獻(xiàn)[15]利用一個特殊的數(shù)據(jù)結(jié)構(gòu)FM模式采用概率的方法對空閑停車位信息進(jìn)行聚合。它不聚合實際的停車位個數(shù)，而是將停車位位置散列到特定的數(shù)據(jù)結(jié)構(gòu)中，然后利用修訂的FM框架得到空閑停車位個數(shù)的概率近似值。該方法可以一定程度上解決原始數(shù)據(jù)在多次聚合時的重復(fù)出現(xiàn)問題，使得多個聚合數(shù)據(jù)可以進(jìn)一步聚合得到更好的聚合數(shù)據(jù)。文獻(xiàn)[17–24]研究的是車速等連續(xù)型數(shù)據(jù)的聚集問題。最早是由Nadeem等 [17] 提出車聯(lián)網(wǎng)上考慮聚集數(shù)據(jù)精度的數(shù)據(jù)聚集問題。文獻(xiàn)[17] 研究節(jié)點上哪些數(shù)據(jù)進(jìn)行聚集，從而在保證聚集精度的前提下最小化聚集數(shù)據(jù)量。該文采用無結(jié)構(gòu)廣播方式進(jìn)行單節(jié)點上的數(shù)據(jù)聚集和分發(fā)。這樣的優(yōu)點是沒有額外的維護(hù)路由結(jié)構(gòu)的開銷，缺點是同一數(shù)據(jù)的聚集數(shù)據(jù)會出現(xiàn)多個版本并且很難從這些不同版本數(shù)據(jù)進(jìn)行取舍。文獻(xiàn)[18–20] 采用無損數(shù)據(jù)壓縮的方式進(jìn)行聚集。文獻(xiàn)[21] 提出了CASCADE算法。該算法是將前方交通場景的精確試圖傳遞給后面的車輛，使得后面的車輛能預(yù)先獲知前方的交通狀況。該算法中對于車速的聚合數(shù)據(jù)不僅包括平均車速，還包括每個原始車速值與平均車速的方差。文獻(xiàn)[22]是文獻(xiàn)[21] 的后續(xù)研究。研究中對CASCADE中簇的大小的選擇進(jìn)行了優(yōu)化，聚合操作沿用了CASCADE的方法。文獻(xiàn)[23] 利用車聯(lián)網(wǎng)收集行駛時間、時間平均速度、空間平均速度等動態(tài)交通狀況參數(shù)。該文的方法利用車輛節(jié)點和路邊接入點之間的通信進(jìn)行無損數(shù)據(jù)聚集。文獻(xiàn)[25] 研究的是在高速公路上對車速信息進(jìn)行聚合的問題。利用模糊推理根據(jù)實際的速度數(shù)據(jù)值考慮是否聚合，最后得出的聚合數(shù)據(jù)能比較準(zhǔn)確地反映數(shù)據(jù)的實際分布情況。文獻(xiàn)[24]研究基于聚集的數(shù)據(jù)分發(fā)算法。該文主要思想是利用用戶通常需要周圍的信息更詳細(xì)，遠(yuǎn)程的信息更粗略的現(xiàn)象，使得數(shù)據(jù)分發(fā)時利用數(shù)據(jù)聚集產(chǎn)生不同粒度的信息進(jìn)行更高效的分發(fā)?，F(xiàn)有的車聯(lián)網(wǎng)上考慮聚集數(shù)據(jù)精度的聚集算法對于離散型數(shù)據(jù)解決得較好，對于連續(xù)型數(shù)據(jù)還有很多問題。連續(xù)型數(shù)據(jù)的聚集操作往往對數(shù)據(jù)精度影響較大，而現(xiàn)有的研究沒有推出基于聚集數(shù)據(jù)的精度界設(shè)計聚集算法，同時在聚集傳輸?shù)倪^程中也還沒有提出可行的避免重復(fù)計算的方法。

3 結(jié)束語

數(shù)據(jù)聚集是車聯(lián)網(wǎng)上一個重要研究方向。聚集數(shù)據(jù)的時延和精度直接影響應(yīng)用的結(jié)果。因此，車聯(lián)網(wǎng)的數(shù)據(jù)聚集需要基于網(wǎng)絡(luò)動態(tài)性考慮聚集數(shù)據(jù)的質(zhì)量優(yōu)化聚集性能。經(jīng)過對現(xiàn)有算法的分析，本文總結(jié)出現(xiàn)有聚集問題中仍未臻至圓滿解決的部分，進(jìn)而設(shè)計更好的聚集算法提高車聯(lián)網(wǎng)上數(shù)據(jù)聚集性能。

參考文獻(xiàn)：

[1] Moustafa H， Zhang Y. Vehicular networks： techniques， standards， and applica-tions[M]. Boca Raton： Auerbach publications， 2009.

[2] 楊放春， 王尚廣， 李靜林，等. 車聯(lián)網(wǎng)綜述（英文）[J]. 中國通信， 2014， 10：003

[3] James W. Intelligent transport system： US， Google Patents. US Patent 6，810，817[P].2004-11-02.

[4] Hartenstein H， Laberteaux K. VANET： vehicular applications and inter-networking technologies[M]. Vol. 1.Wiley Online Library， 2010

[5] LIU Y， XIONG N， ZHAO Y， et al. Multi-layer clustering routing algorithm for wireless vehicular sensor networks[J]. IET communications， 2010， 4（7）： 810–816.

[6] SANTA J， GóMEZ-SKARMETA A F， SáNCHEZ-ARTIGS M. Architecture and evaluationof a unified V2V and V2I communication system based on cellular networks[J]. Computer Communications， 2008， 31（12）： 2850–2861.

[7] TAKAHASHI A， ASANUMA N. Introduction of Honda ASV-2 （advanced safety vehicle- phase2）[C].Proceedings of the IEEE Intelligent Vehicles Symposium，Ohio， USA：IEEE， 2000： 694–701.

[8] SHLADOVER S E. Path at 20-history and major milestones[J]. IEEE Transactions on intelligent transportation systems， 2007， 8（4）： 584–592.

[9] DELGROSSI L， ZHANG T. Dedicated short-range communications[J]. Vehicle Safety Communications： Protocols， Security， and Privacy， 2009： 44–51.

[10] YU B， GONG J， XU C Z. Catch-up： a data aggregation scheme for vanets[C]// Proceedings of the fifth ACM international workshop on Vehicular Inter-NETworking， New York， USA： ACM， VANET 08，2008：49-57.

[11] 李建中，高宏。無線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J]. 計算機(jī)研究與發(fā)展，2015，45（1）：1-15.

[12] YU B， XU C Z， GUO M. Adaptive forwarding delay control for VANET data aggregation[J]. IEEE Transactions on Parallel and Distributed Systems， 2012， 23（1）：11 -18.

[13] PALAZZI C E， PEZZONI F， RUIZ P M. Delay-bounded data gathering in urban vehicular sensor networks[J]. Pervasive Mobile Computation， 2012， 8（2）： 180–193.

[14] CALISKAN M， GRAUPNER D， MAUVE M. Decentralized discovery of free parking places[C]// The 3rd International Workshop on Vehicular Ad Hoc Networks， New York， NY， USA： ACM，2006：30-39.

[15] LOCHERT C， SCHEUERMANN B， MAUVE M. Probabilistic aggregation for data dissemination in VANETs[C]// Proceedings of the Fourth ACM International Workshop on Vehicular Ad Hoc Networks， New York， NY， USA： ACM， VANET 07，2007：1-8.

[16] LOCHERT C， SCHEUERMANN B， MAUVE M. A probabilistic method for cooperative hierarchical aggregation of data in VANETs[J]. Ad Hoc Networks， 2010， 8（5）：518–530.

[17] NADEEM T， DASHTINEZHAD S， LIAO C， et al. TrafficView： traffic data dissemination using car-to-car communication[J]. ACM SIGMOBILE Mobile Computing and Communications Review， 2004， 8（3）： 6–19.

[18] IBRAHIM K， WEIGLE M C. Accurate data aggregation for VANETs[C]// Proceedings of the fourth ACM international workshop on Vehicular ad hoc networks， New York， NY， USA： ACM， VANET 07，2007：71-72.

[19] IBRAHIM K， WEIGLE M. CASCADE： Cluster-based accurate syntactic compression of aggregated data in VANETs[C]// 2008 IEEE Global Communications Conference， New Orleans，USA：IEEE， 2008： 1 -10.

[20] IBRAHIM K， WEIGLE M. Optimizing CASCADE data aggregation for VANETs[C]//5th IEEE International Conference on Mobile Ad Hoc and Sensor Systems， Atlanta， USA：IEEE， 2008： 724-729.

[21] DIETZEL S， SCHOCH E， BAKO B， et al. A structure-free aggregation framework for Vehicular Ad Hoc Networks[C]// The 6th International Workshop on Intelligent Transportation （WIT 2009）. Hamburg， Germany：[s.n.]， 2009：1-16.

[22] ARBABI M H， WEIGLE M. Using vehicular networks to collect common traffic data[C]// The sixth ACM international workshop on VehiculAr InterNETworking， New York， NY， USA： ACM， VANET 09， 2009：117-118.

[23] TSAI H W， CHEN T S， LIN S K. Dissemination of data aggregation in vehicular Ad Hoc Networks[C]. 10th International Symposium on Pervasive Systems， Algorithms， and Networks （ISPAN）， Kaoshiung， Taiwan： IEEE ， 2009： 625–630.

[24] YU X， ZHAO H， ZHANG L， et al. Cooperative Sensing and Compression in Vehicular Sensor Networks for Urban Monitoring[C]// 2010 IEEE International Conference on Communications （ICC）， Cape Toun，South Africa：IEEE， 2010： 1-5.