车联网数据聚集研究综述

冯强 冯诚 李治军 姜守旭

摘 要：当今，车联网是实现智能交通应用的平台。车联网有着特殊的网络特征，使得其上的数据聚集算法不同现有的无线传感器网络数据聚集。数据聚集可以有效地降低传输过程中的数据量，但同时亦会引起数据时延的增加和数据精度的降低。因此聚集算法往往考虑聚集数据的时延和精度。本文对现有的车联网聚集算法进行综述分析。

关键词：车联网；数据聚集；数据质量；无线移动感知网络

中图分类号：TP391 文献标识号：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 引 言

目前物联网的研究已经覆盖到市政、交通、物流运输、医疗、教育、工农业生产等诸多领域。物联网在交通领域的重要分支即为车联网（Internet of Vehicles）[1， 2]。车联网为物联网时代下的智能交通系统（Intelligent Transportation System） [3] 提供了实现的平台。车联网是智能车之间以及智能车与路边设备之间通过无线通信形成的移动通信网络。车联网可用于协助驾驶者及时躲避交通事故，提高交通运输的效率，监控实时交通状况等。车联网改变了现有交通管理监控的技术框架，利用交通参与的主体（如车辆、乘客、行人、路边设备等）自主感知交通状况，实现了人与物理世界的紧密交互和融合。

1 车联网

车联网，又被称为车用自组织网络（Vehicular Ad-hoc Networks， VANETs） [4]或车载感知网络（Vehicular Sensor Networks， VSNs）[5]， 由车辆节点自组织形成车与车之间（Vehicle to Vehicle， V2V） [6] 以及车与基础设施之间（Vehicle to Infrastructure， V2I）[6] 的异构通信网络。车联网的结构如图1所示。这是一种无线移动感知通信网络。通常每个车辆节点装配无线通信设备，GPS定位设备以及各种传感器设备（如加速度传感器、速度传感器等）。逻辑上智能车有两种单元：操控单元（on-board unit， OBU） 和应用单元（Application Unit， AU）。操控单元通常有获取感知数据，定位，以及无线和/或有线通信功能。应用单元通常由便携式设备构成，如笔记本电脑、个人数据处理机（Personal Digital Assistant， PDA）等，是智能车的附属部分。具体功能是利用操控单元获取信息开发和实现具体应用。操控单元和应用单元可以通过有线互连，也可以采用无线方式，如蓝牙（Bluetooth）、无线USB（Wireless USB， WUSB）等。智能车的结构如图2所示。

1.1 车联网的历史

VANET的概念最早是在2003 年由国际电信联盟的汽车通信标准化会议上被正式提出。但关于VANET的研究却是由来已久。1986 年在欧洲PROMETHEUS（Programme for European Traffic with Highest Efficiency and Un-precedented Safety）即已获得提出。该框架一经提出就被19个欧洲国家以及欧盟委员会接受并实现支持。进入90 年代，人们集中在协同驾驶应用研究上。1996年到2000年期间日本Tsukuba市部署ASV（Advanced Safety Vehicle）项目[7]。1997年San Diego部署了PATH（California Partners for Advanced Transit and Highways）[8]。1999 年美国联邦通信委员会在5.9GHz频带上分配了75MHz带宽的信道给车与路边设备之间的短距离无线通信（Dedicated Short-Range Communication，DSRC）[9]。这使得VANET的概念再次得到了工业界的广泛关注。同时多个标准化组织也开始积极为DSRC制定通信协议标准。2004年IEEE 提出基于802.11p协议的WAVE（Wireless Access in Vehicular Environment）标准[10]。2000年到2005年期间美国的IVI（Intelligent Vehicle Initiative），欧洲的CarTalk和FleetNet以及日本的ASV三期项目均把研究热点从协作式自动驾驶转向协作式驾驶操作。ISO（International Standard Organization） 提出了CALM（Continuous Air interface for Long and Medium distance）标准。基于该标准欧洲在2006年到2010年之间开展了几个主要项目：COOPERS、PReVENT、SeVeCom、NoW和PRE-DRIVE。

1.2 车联网的特点

车联网与其他的移动网络和通信网络相比，具有一些优势和挑战。在此，分析总结为如下几点。

（1）无限制的节点能量。与传统的感知网络相比，车联网移动设备的能量问题通常不是一个重要的限制条件，车辆本身能够给计算和通信设备提供持续的能量。

（2）更强的计算能力。相对于传感器节点等小型设备，车辆节点可以提供更强的计算、通信和感知能力。

（3）可预测的移动性。不同于传统移动自组织网络，车辆节点的移动受限于道路网络，因此车辆节点的运动具有很好的可预测性。道路网络信息通常是可得的，且车辆的位置信息可以通过GPS获得。因此根据车辆的平均速度，当前瞬时速度和历史轨迹可以预测车辆在未来时间出现的位置。

（4）大规模的节点分布。车联网原则上可以扩展到整个道路网络上，并且有众多参与者，包括路面上的车辆，路边停靠的车辆，路边设备等，而之前研究的自组织网络通常假设存在于局部有限的空间范围。

（5）高移动性。车联网中的大部分车辆节点都在高速移动，而且车辆之间的相对速度范围很大。在高速公路上，相对速度可以达到300km/h，这时节点的密度可能很低；在城市交通中，相对速度可以到60km/h，这时节点的密度会很高。

（6）通信网络的不可连通性。车联网通常瞬时是不连通的，交通的动态性导致在稀疏交通场景下车辆之间存在大的间隙，从而形成多个孤立的节点簇。节点连通程度高度依赖于两个因素：无线链路的通信半径和加入车联网的车辆比例。

（7）网络拓扑的动态性。与传统的自组织网络相比，车联网的车辆节点一直在移动，因此车联网场景具有很强的动态性。具体表现在节点之间的无线链路时断时续，网络拓扑动态变化频繁。

1.3 车联网的应用

车联网上的应用主要分为三大类，一是与行驶安全相关的应用，二是交通管理和协调的应用，三是与娱乐相关的应用。其中，与行驶安全相关的应用主要用于降低交通事故发生的概率，减少交通事故中的人员伤亡。这类应用通过及时向用户提供周围交通情况信息，从而协助用户避免交通事故，例如变车道警示、追尾警示。而交通管理和协调应用则集中在提高交通流量，协调交通流有序流畅运行，以及为车辆提供实时交通状况信息用于实时导航。这类应用有合作式导航、速度管理等。另外，娱乐相关的应用主要是为乘客提供Internet连接服务进行线上游戏或资讯下载，例如广告推送、在线游戏等。

2 车联网上的数据聚集

车联网上的数据聚集是近年来车联网上的研究热点。数据聚集是车联网上数据收集和分发过程中的一个核心技术。常见的聚集操作有以下几种，MAX（求最大值）、MIN（求最小值）、SUM（求和）、COUNT（计数）、AVERAGE（求平均值）、MEDIAN（求中位数） 等[11]。网内聚集是在网络内部传输数据的过程中同时进行聚集操作，不断传输中间聚集结果，并将最终聚集结果传输到数据中心或网络内的其他移动节点。网内数据聚集技术可以有效减少传输过程中的数据量，并充分利用动态带宽资源，减轻网络的数据传输负担。同时聚集技术也会影响数据的精度和时延。因此，现有的车联网数据聚集研究主要分为以下两类，一是权衡聚集数据的延迟和聚集收益的优化，二是权衡聚集数据的精度和聚集收益的优化。

2.1 基于车联网上考虑聚集数据时延的聚集算法研究

车联网考虑时延的聚集算法主要针对聚集传输的时刻进行研究。文献[11-12] 考虑的就是如何设定数据在节点的转发延迟，使得可聚合的数据在同一节点相遇的概率最大。该文提出的CatchUp算法中的每个节点根据自己的局部试图利用分布式的马尔可夫决策过程模型判断每个时间周期对数据是否需要转发，使得数据在节点等待与自己可以聚合的数据的到来。文献[13]研究的是限定截止时间内的优化收集聚集信息量问题，为此提出DB-VDG协议，该协议通过调整数据传输过程中的转发和携带策略使得在截止时间内AP节点收集的数据量最多。又提出了一个查询响应协议DB-VDG，该协议的主要设计思想是数据如果能在限定的延迟内被携带到目的地，就尽量少进行转发，这样可以最大限度地节省带宽。现有的车联网上考虑时延的数据聚集算法没有分析利用车联网的动态通信拓扑信息，也没有深入地规划和利用无线信道资源，因此现有算法并未从根本上解决基于时延界的聚集问题。

2.3 基于车联网上考虑聚集数据精度的聚集算法研究

下面，将专题分析和总结考虑聚集数据精度的聚集技术的研究。根据具体的应用区别，聚集数据的类型分为离散型数据（如空闲停车位数） 和连续型数据（如平均速度等）。离散型数据的聚集需要解决的核心问题是如何避免对同一数据进行重复聚集操作，而连续型数据的聚集需要考虑如何减小聚集操作引起的数值上的偏差。

文献[14–16] 研究的是空闲停车位信息的聚集问题。文献[14] 利用quad树结构对空闲停车位数进行层次型聚集。该文利用quad树对二维空间实施了层次性划分，然后将各区域的空闲停车位信息实现了累加聚集。文献[15]利用一个特殊的数据结构FM模式采用概率的方法对空闲停车位信息进行聚合。它不聚合实际的停车位个数，而是将停车位位置散列到特定的数据结构中，然后利用修订的FM框架得到空闲停车位个数的概率近似值。该方法可以一定程度上解决原始数据在多次聚合时的重复出现问题，使得多个聚合数据可以进一步聚合得到更好的聚合数据。文献[17–24]研究的是车速等连续型数据的聚集问题。最早是由Nadeem等 [17] 提出车联网上考虑聚集数据精度的数据聚集问题。文献[17] 研究节点上哪些数据进行聚集，从而在保证聚集精度的前提下最小化聚集数据量。该文采用无结构广播方式进行单节点上的数据聚集和分发。这样的优点是没有额外的维护路由结构的开销，缺点是同一数据的聚集数据会出现多个版本并且很难从这些不同版本数据进行取舍。文献[18–20] 采用无损数据压缩的方式进行聚集。文献[21] 提出了CASCADE算法。该算法是将前方交通场景的精确试图传递给后面的车辆，使得后面的车辆能预先获知前方的交通状况。该算法中对于车速的聚合数据不仅包括平均车速，还包括每个原始车速值与平均车速的方差。文献[22]是文献[21] 的后续研究。研究中对CASCADE中簇的大小的选择进行了优化，聚合操作沿用了CASCADE的方法。文献[23] 利用车联网收集行驶时间、时间平均速度、空间平均速度等动态交通状况参数。该文的方法利用车辆节点和路边接入点之间的通信进行无损数据聚集。文献[25] 研究的是在高速公路上对车速信息进行聚合的问题。利用模糊推理根据实际的速度数据值考虑是否聚合，最后得出的聚合数据能比较准确地反映数据的实际分布情况。文献[24]研究基于聚集的数据分发算法。该文主要思想是利用用户通常需要周围的信息更详细，远程的信息更粗略的现象，使得数据分发时利用数据聚集产生不同粒度的信息进行更高效的分发。现有的车联网上考虑聚集数据精度的聚集算法对于离散型数据解决得较好，对于连续型数据还有很多问题。连续型数据的聚集操作往往对数据精度影响较大，而现有的研究没有推出基于聚集数据的精度界设计聚集算法，同时在聚集传输的过程中也还没有提出可行的避免重复计算的方法。

3 结束语

数据聚集是车联网上一个重要研究方向。聚集数据的时延和精度直接影响应用的结果。因此，车联网的数据聚集需要基于网络动态性考虑聚集数据的质量优化聚集性能。经过对现有算法的分析，本文总结出现有聚集问题中仍未臻至圆满解决的部分，进而设计更好的聚集算法提高车联网上数据聚集性能。

参考文献：

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

[2] 杨放春， 王尚广， 李静林，等. 车联网综述（英文）[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] 李建中，高宏。无线传感器网络的研究进展[J]. 计算机研究与发展，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.