基于群智感知技术的车联网路径优化问题研究∗

万 辛 高圣翔

基于群智感知技术的车联网路径优化问题研究∗

万 辛 高圣翔

（国家计算机网络应急技术处理协调中心 北京 100012）

无线网络、云计算以及智能终端等研究推进了车联网（Internet Of Vehicle，IOV）应用的发展，如在车辆防盗、定位、紧急救援等方面，而群智感知技术为车联网的应用提供了精确、实时的兴趣数据，为解决路径选择提供了数据基础。论文首先分析介绍了IOV的关键技术，并且回顾了传统的用于解决路径选择的两类流量模型—车辆到基站（V2I，Vehicle To Infrastructure）以及车辆到车辆（Vehicle To Vehicle，V2V），论文引入了新的感知节点—人，利用基于人自身的群智感知数据，动态地创建路由选择过程，并通过试验对策略进行验证，结论证明本策略在实验环境下降低实际交通过程中的拥塞问题，最后提出了可靠性较高的交通预测。

车联网；群智感知；动态路由；拥塞

AbstractThe research of wireless network，cloud computing and intelligent terminal to promote the development of the appli⁃cation of Internet of Vehicle（IOV），such as in vehicle anti-theft，positioning，emergency rescue，however the application of the crowd sensing technology have provided accurate，interesting data in real time for IOV，which provides the basic data for the solu⁃tion the key technology of IOV is analyzed firstly and the traditional traffic models for two vehicles to solve the flow model of the Ve⁃hicle To Infrastructure（V2I）and vehicle to vehicle（V2V）are reviewed.a new perception node-person is also introduced，using crowd sourcing data based on their own，a dynamic routing process is created，and through the test the conclusion that the strategies to reduce the actual traffic congestion problem in the process of the experimental environment is validated，and finally the reliability high traffic forecast is put forward.

Key Wordsinternet of vehicle，crowd sensing，dynamic routing，traffic congestion

Class NumberTP393

1 引言

随着无线网络、云计算以及智能设备等关键技术的快速发展，物联网的产业化使得车联网（Inter⁃net Of Vehicle，IOV）进入了一个新的研究阶段，关于车联网的研究涉及多个学科的交叉，包含汽车业、交通运输、信息通信技术。根据业界对车联网的实际应用分类包含动态车辆的移动通信系统（车内通信系统：如车辆—传感器（Vehicle To Sensor，V2S）衍生出车辆到基础设施（Vehicle To Infrastruc⁃ture，V2I）以及车辆到人个体（Vehicle To Human，V2H）等方式。而云计算技术已成为信息技术发展的关键基础设施，在文献［1］中作者提出了一种基于三层次的“Client Connection Cloud”云系统，系统中包含了客户端、连接以及云服务；云计算技术助推IOV在物理系统组件方面得到了业界认可，如带有传感器的车辆通过云与其他设备实现互访（例如：监测、致动和导航），通过虚拟界面实现云上各类设备的虚拟管理［2～3］，基于云计算的车联网应用可用来解决车辆运输更清洁、安全、高效，推进清洁交通的快速发展。

移动群智感知技术是基于群智感知技术的移动性发展起来的，它是基于各类移动设备，如利用智能手机信息来解决车辆联网过程中关键数据的采集过程，利用车辆通信，通过基站服务可以实时地确定在道路的状态，并且，随着车辆状态一起将这些交通数据传递到云端，这又可以估算得出车辆的平均速度等信息。然而，当前该类应用并未为交通做出实际的意义。

在本文中，作者提出以提高运输效率为目的，基于移动群智感知技术（Mobile Crowd Sensing，MCS），利用云技术的高计算性能设计实现了用于估计和预测形成时间的优化算法，实现了一种基于云的车联网结构（Cloud-Assisted to IOV，CAIV），并利用动态路由选择策略结合预测结果为驾驶员躲避交通堵塞的情况。该策略摈弃了传统的数据采集手段，利用驾驶员或者同行人员的智能手机或者传感设备构建大规模传感网络应用环境。

2 国内外研究现状

利用科技手段提升交通运输能力是车联网应用的初衷，当前国内外学者对于车联网的研究主要集中于车联数据的收集、预测模型的设计等关键研究热点，本章节主要从以上几点对相关国内外研究现状进行分析。

1）数据采集技术

关于车联网数据的收集，国内外学者通常采用现有的基础设置作为数据源的主要端点，如通过传感设备的循环采集（如街道的一些摄像采集设备），系统可采用多周期内通过车辆的密集度来判断当前路况信息，该种采集手段已经得到多方面的应用。随着各类传感设备的出现，多数据源已经成为当前车联网应用的主要采集手段，例如通过OBE（On-Broad Equipment）、GPS、速度计等车载设备完成对车辆运动信息的采集。Zhang D等［4］设计实现了一种基于智能手机的车联自组织网应用，该应用通过感知参与人员的智能手机间与路面基站建立相互的桥联关系，实现数据的互联采集并提交给相应的应用系统，该应用在设计过程中引入了路面基站（Roadside Equipment，RSE），由于基站感知能力的局限性，在车辆高峰期并不能确保所有车辆信息的采集（由于接入点数量有限）。而本文提出的基于群智感知技术的车联网数据采集完全采用智能终端与服务端的互联，通过优化算法完成对车辆运行情况的采集。

2）预测模型的设计

业界学者对于车联网预测模型的研究包含通过V2I以及V2V模式进行模型设计。Lochert等［5］提出一种在特定情况下通过源与目的地之间的建立多条虚拟链路，模型数据基于道路之间的基础设施进行数据采集，通过各个基站与基站之间的车辆通行时间的统计-平均，得出最终的预测结果。文献［6］中通过层次聚合的方式，通过对模型中的各个地理层次分配不同的级别，对于路径的规划，系统模型在地图上进行源-目的地间进行路径的标注，并且随着车辆运行的状态动态地更新相关的路线信息。

在模型设计过程中，如何确保时空统一是模型设计的重点之一。由于在模型设计中，信息采集设备通常采用RSE作为车辆传感设备的连接点，然而如何确保各个RSE设备之间的时空统一问题是该问题研究的重点。Min等［7］提出一种时空关联的实时交通预测策略，该策略利用道路的空间特性来反映相对车辆距离的同时计算相关车辆的平均速度；文献［8］中提出一种实时和可靠的通信体系架构，基于网络化的路由算法，通过组合时间和空间的交通流数据（体积、密度、速度等关键因素），并且通过简化的流量进行了预测实验。

3）基于MCS的车联网研究

基于移动群智感知的交通应用已经被多数学者证明对交通拥堵水平、交通延误、道路通行条件等问题进行了实验验证。Hull等［9］利用车载远程信息处理设备来收集所关注车辆的位置以及速度信息，并且利用历史数据和实时的信息来估计车辆运行的时间，并且根据道路情况动态的进行实时的路由规划；Herrera等［10］通过利用智能手机的GPS设备对交通进行实时的预测，为车辆提供优化的虚拟路线；Ali等［11］开发了一个机遇群智感知的车联网应用系统，系统采用车辆间的GPS的工作日志和语音指令实时收集道路的拥塞情况，并为用户实时提供无阻赛的路由数据。以上这些基于移动群知感知技术的车联网预测研究都是以GPS作为数据源，学者们对GPS相关的环境干扰等因素均做了相应的研究，然而仅仅对车辆的路径选择做了应用研究，并未对数据处理端等作详细的研究。

3 云计算—车联网融合研究

3.1 基于云服务的车联网介绍

云计算技术为车联网的应用提供了高效、快速的计算服务，本章节主要介绍基于云计算服务的车联网应用（Vehicle with Clouds），移动云为车联网智能处理提供了更为丰富的服务可能。

如图1所示为车辆通过无线网络构建的车联网络图，根据实际云计算环境的实际分类，应用于车联网服务的云服务可分为静态云和动态云两类，其中静态云是通过云计算中心为车联网提供中心计算服务，而动态云是通过车辆间的智能设备（主要通过智能手机、智能PDA等可互联设备）自组形成相应的网络簇，实现个性化云服务（为网络簇之间的单元提供个性服务），如图1中的各个点之间的连线代表单元之间形成簇结构。

图1 基于云的车联网结构图

通过车辆间的智能设备构建的动态云，单元间可通过互联网了解相互间所面临的路况信息。

3.2 基于群智感知的路况预测模型设计

群智感知技术作为新型的互联网应用，充分利用了智能设备自身的计算以及存储特性，如何利用群智感知技术颠覆传统车联网通过RSE进行数据传输以及服务中心计算的现状，设计流程如下。

1）自动感知与上传过程：根据相关研究结论证明，2%～3%的驾驶员参与感知过程即可完成对路况信息的全区域获取。在模型设计过程中，采用志愿服务的方式征求公共交通司机（由于该类人群在路上的周期最长）参与感知过程，通过在智能终端上安装相应的服务完成数据向云平台传输的过程。

2）云服务过程：基于云服务的群智感知应用流程描述如下。

（1）用户登录云系统并输入目的地信息，待云系统进行用户权限的审核；

（2）若用户具备感知参与权限，云服务系统启动向指定用户提供云计算请求功能，并分配云计算请求给用户；若用户不具备感知参与权限则拒绝分配云计算可用请求；

（3）通过算法（算法在后期介绍）根据感知用户的参与数据完成交通流量预测工作；

（4）云服务根据预测模型的计算为服务请求用户分配最为合理的路径规划。

感知参与者通过自有的智能设备完成云服务分配的各类采集、计算工作，为云服务提供最基层的数据服务集合。为了提升感知参与者的积极性，本文设计了如下算法并引入了激励机制。

输入：

采样周期：T；位置信息：Sd；

他以为这样的盛世，会是一千年，一万年，他读书学武，游荡在街巷里，母亲在百花谷迎来送往，打情骂俏，达官贵人、三教九流在他们俩的小世界之外活色生香地活。三个月后，回望过去，我们不在其中，那也不过是一场做得有些长、又太过热烈的绮梦罢了，他们真的由梦里醒来了吗？胡子大叔、秀才哥哥，还有胖婶，你们掉在这个流言里，不愿醒来，是想搬去万花谷里继续做梦吧！

开始：

设置权值参数α，β和γ

根据距离参数生成相应的距离结构dij和qij；

Tc为当前时间，T1←Tc表示采集周期；

当用户满足感知条件时：

如果T1-Tc≥T，执行如下工作：

根据云服务生成vij和rij；

通过式1生成权值w；

获取下个位置信息Snext；

根据Dijkstra算法生成源Sd到Snext的最短距离；

时间归零；

结束

对于算法的解析，通过一个实例进行说明。

假设所研究的道路网络中存在N个站点，分别记为 S1，S2，S3，…，Sn，如图 2 所示，包含 3 个站点，d1，2表示站点1和站点2之间的距离，定义qij表示站点之间发生冲突的概率，Rij表示站点之间道路的质量情况（根据实际情况分为一级公路、二级公路和三级公路，默认一级公路发生交通概率为0，以此类推），定义Rij和qij之间的关系如下：

图2 基于云计算服务的道路预测图

定义vij为车辆在站点i和站点 j之间的平均速度，本文中认为车辆在站点间不发生任何可能的事件（如临时停车、临时转向等不确定性问题）。

通过有向图定义的方式建立预测模型，定义G=(V，E，ф)为无向图结构，其中V为站点集合V（S1，S2，S3，…，Sn），E 为路径集合 E={(Si，Sj)，若 i和 j之间存在道路｝，ф为各因素间的一个权值组合关系表达式。

其中α，β和γ相应的权值参数，根据式（1）中当vij为0时，ф将趋于无群大，并且定义W=ф(Si，Sj)为关键的权值，根据算法描述可得出下一个位置信息。在实际的预测过程中，在每一个采样周期T内进行路径的重新规划。

3.3 基于预测模型的实验设计

根据3.2节中证明道路网络结构可通过无向图来表示，本文通过C++设计实现一个基于多代理的仿真环境，在设计过程中将车辆视为一个物理代理（具备感知效应），将其各个关键属性（速度、油量等）视为一个代理维护，将各个车辆的感知运算过程视为一个代理（实现云服务功能）等，构建如图3所示的网络结果图，设α =0.4，β =0.8，γ =0，根据图3中所示各链路的权值（用数字表示该路段的平均速度）。假设源点为Ss，目的地为 Sd，那么Ss→Sd表示源到目的的路径表示，其中路径点共包含共计 S1，S2等11个路径点，那么根据式（1）计算基于移动群智感知的，对于不同路径的预测（假设道路均为一级公路）计算的权值来决定车辆所行驶路线［12］。

图3 Ss到Sd的路径图

根据传统的车联网应用路径选择以及基于群智感知的车联网路径选择进行效能优劣分析，对如图3所示中的各个路径按照式（1）进行计算，对不同的路径选择按照两种不同的方法进行计算，通过统计、分析对各个方案的行驶距离、行驶时间进行统计分析。

根据图3中的描述，Ss的出度为3，那么默认为Ss到Sd的路径方案有三套，分别用传统车联网路径计算和基于群智感知的车联网路径计算等两种方式来完成行驶距离和行驶时间进行仿真分析。

根据实际的路径选择验证两类车联网设计的优劣，图4显示出基于群智感知的车联网路径选择在路径距离的选择上相比传统的车联网距离选择提升了近20%的优化；图5显示基于群智感知的车联网路径选择在路径时间的花费上相比传统的车联网时间花费提升了近33%的优化（基于图3中的速度结构图）。

图4 两类车联网对相同案例的距离对比图

图5 两类车联网对相同案例的时间对比图

根据实验理论的证明，基于群智感知的车联网路径规划应用云服务计算各个感知参与者所提供的感知数据为用户分配最佳的道路规划（并非距离最短，但确保花费时间最少）。利用百度地图所提供的地理信息数据，设计同一起始点、同一终点作为实际路径规划的Ss和Sd，按照传统的车联网路径规划计算如图6所示的最短路径，但实际情况为该路段的车流量较大，实际用时约为40min；而基于群智感知的路径规划利用云服务计算感知参与车辆提供的路况信息数据按照算法进行分析计算，给出如图7所示的用时最少的路径规划（虽然路径距离大于图6所示的路径距离）。

图6 按照传统车联网的规划路径图

图7 按照群智感知的车联网规划路径图

4 结语

本文基于群智感知技术信息收集过程的广泛性，利用该特点为车联网的路径预测提供实时的路况信息，采用云计算的高性能特性进行预测模型的分析。提出了基于MCS的路径预测算法，并且通过代理的方式对算法进行了性能仿真，结论表明利用群智感知的路径预测为客户提供更佳的路径选择方案，而并非将路径最短作为最佳的评价指标。

［1］Liu，N.Internet of Vehicles：Your Next Connection［EB/OL］.Available online：http：//www.huawei.com/es/static/HW-110848.pdf（accessed on 20 December 2015）.

［2］Wan J，Zhang D，Sun Y，Lin K，Zou C，Cai H.VCMIA：A Novel Architecture for Integrating Vehicular Cy⁃ber-Physical Systems and Mobile Cloud Computing.Mob.Netw.Appl.2014，19：153-160.

［3］Liu J，Wan J，Wang Q，Deng P，Zhou K，Qiao Y.A Sur⁃vey on Position-based Routing for Vehicular Ad hoc Net⁃works［J］.Telecommun.Syst.2015：15-30.

［4］Zhang D，Zhang D，Xiong H，Yang T，Vasilakos A.BA⁃SA：Building Mobile Ad-hoc Social Network on top of An⁃droid［J］.IEEENetw.，2014，28：4-9.

［5］Lochert C，Scheuermann B，Wewetzer C，Luebke A，Mauve M.Data aggregation and roadside unit placement for a VANET traffic information system［C］//In Proceed⁃ings of the 5th ACM International Workshop on Vehicular Internet Working，San Francisco，CA，USA，14-19 Sep⁃tember，2008：58-65.

［6］Hartenstein H，Laberteaux K.P.VANET：Vehicular Appli⁃cations and Inter-Networking Technologies［M］.John Wiley and Sons，Ltd：New York，NY，USA，2010.

［7］Min W，Wynter L.Real-time road traffic prediction with spatio temporal correlations［J］.Transp.Res.Part C 2011，19：606-616.

［8］Wan J，Zhang D，Zhao S，Yang L.T，Lloret，J.Con⁃text-aware Vehicular Cyber-Physical Systems with Cloud Support：Architecture，Challenges and Solutions［J］.IEEE Commun.Mag.2014，52：106-113.

［9］Hull B，Bychkovsky V，Zhang Y，Chen K，Goraczko M，Miu A，Shih E，Balakrishnan H，Madden S.Cartel：A distributed mobile sensor computing system［C］//In Pro⁃ceedings of the SenSys 2006，Boulder，CO，USA，31 Octo⁃ber-3 November 2006：125-138.

［10］Herrera J，Work D，Ban X，Herring R，Jacobson Q，Bayen A.Evaluation of Traffic Data Obtained via GPS-enabled Mobile Phones：the Mobile Century Field Experiment［J］.Transp.Res.C，2010，18：568-583.

［11］Ali K，Al-Yaseen D，Ejaz A，Javed T，Hassanein H.CrowdITS：Crowdsourcing in intelligent transportation systems［C］//In Proceedings of the IEEE WCNC 2012，Paris，France，1-4 April 2012：3307-3311.

［12］Gao Wei，Cao Guohong，La P T，et al.On exploiting transient social contact patterns for data forwarding in de⁃lay-tolerant networks［J］.Mobile Computing，IEEE Transactions on，2013，12（1）：151-165.

［13］An Jian，Gui Xiaolin，Zhang Wendong，et al.Research on social relations cognitive model of mobile nodes in In⁃ternet of Things［J］.Journal of Network and Computer Application，2013，36（2）：799-810.

Research on Path Optim ization of Internet of Vehicle Based on Crowd Sensing Technology

WAN Xin GAO Shengxiang
（National Computer Network Emergency Response Technical Team/Coordination Center of China，Beijing 100012）

TP393

10.3969/j.issn.1672-9722.2017.09.016

2017年3月4日，

2017年4月15日

万辛，男，博士研究生，工程师，研究方向：通信网络、网络安全。高圣翔，男，硕士，工程师，研究方向：宽带网络。