车联网WAVE的多三角形网络组播通信模型

汤春明，闫 博，鄢 婷，于 翔

（1.天津工业大学 电子与信息工程学院，天津 300387；2.天津工业大学 工程教学实习训练中心，天津 300387）

车联网WAVE的多三角形网络组播通信模型

汤春明1，闫 博1，鄢 婷1，于 翔2

（1.天津工业大学 电子与信息工程学院，天津 300387；2.天津工业大学 工程教学实习训练中心，天津 300387）

以高速公路车与车之间的通信模式为研究对象，研究基于车联网WAVE的多三角形组播通信模型.针对高速公路上行驶的车辆具有高移动性、不确定性以及分布密度较大等特点，易使通信链路频繁地断开和重链等问题，采用Delaunay三角网对其进行动态分组后，实现了多三角形组播通信，以保证车辆快速而稳定的通信.在Repast J仿真环境中进行了测试，结果表明：该模型节约了建网时间，其建网时间小于1 ms，切换网络时间在50 ms左右，传输时延在10 ms以内，总共在60 ms左右，符合美国车联网通信技术需求标准.保证了动态节点的实时链接，避免了网络的频繁断开与重链，确保了数据传输的实时性，能够用于高速公路上车对车的稳定快速通信.

车联网；组播通信模型；Delaunay三角网；动态分组；动态节点实时链接

dynamic node link

智能交通系统（intelligent transport system，ITS），是将先进的信息技术、数据通信传输技术、电子传感技术、控制技术及计算机技术等有效集成运用于整个地面交通管理而建立的一种在大范围内、全方位发挥作用的，实时、准确、高效的综合交通运输管理系统[1]. ITS可以有效地利用现有交通设施，减少交通负荷和环境污染，保证交通安全，提高运输效率，它的研究和应用日益受到各国重视.车联网是物联网在智能交通领域的运用，是智能交通系统的重要组成部分.车联网中车辆间的通信属于私有云之间通信的一部分，具有巨大的发展潜力.WAVE（wireless access in vehicular environments）作为车载自组网（vehicular ad hoc networks，VANET）的一种短程通信技术协议栈（dedicated short range communications，DSRC），专门应用于智能交通系统无线通信[2].智能交通系统中的车辆通信类型包括车与车之间（vehicle to vehicle，V2V）、车辆与路边单元之间（vehicle to roadside，V2R）、车辆与便携设备之间（vehicle to pedestrian，V2P）的通信[2].本文是基于VANET的组播路由协议，主要研究车与车之间的通信模式.

在WAVE车联网通信中，一个比较核心的问题是路由协议算法的选择.V2V的VANET路由协议算法一般分为3种：单播路由、广播路由和组播路由.其中组播路由出现的时间最晚，但其同时具有单播和广播的优点，最具发展前景.目前，VANET的单播和广播路由算法在国内外研究较多，而组播路由算法的研究相对来说较少.关于组播路由算法，Faezipour等[3]参考了VANET的应用特点以及考虑通信成本等因素，提出了在节点间距离较近且通信区域内节点密度较高时，优先选择WAVE作为数据传输网络，但是并没有指出具体采用了哪种路由协议.Lucani等[4]提出了基于网络编码的可靠建模方法，以及网络编码时采用双工信道的思想，数据丢包率低，但效率不高.Nzouonta等[5]提出基于实时交通信息的城市自组车联网路由协议，它适用于十字路口等路径上有交叉点的公路，可以在不影响信息的实时性同时消除大量的冗余信息，但是此协议不适用于高速公路上行驶的车辆.Perdana等[6]提出了一种应用于IEEE 1609.4标准下，Dijkstra算法与组播协议结合的移动模型，该算法可在短时间找到最短的通信路径，但是其吞吐量较高.Jemaa等[7]提出了一种基于VANET组播的扩展移动性管理和路由协议，该算法通过采用低控制开销和有效地利用带宽来提供组播移动性管理，其优势在于扩大服务范围和有效的抑制了广播风暴，但是可能会造成一部分信息的延时.和国外的研究相比，近年来国内对于VANET的研究还不是很多.主要有蔡莉等[8]提出的一种在Ad-hoc网络中基于地理位置的改良组播路由算法，该算法动态地选择一些发送节点，可以节约节点的能量，以此来优化组播树，它的缺点是若组播树中的子节点不属于转发区域，则不能寻找该节点的转发节点.罗娟等[9]提出一种基于网络编码的多播车载网路由算法研究，该算法有效地减少了节点的通信次数，降低了通信干扰，实现了网络负载均衡，但是编码和解码会带来通信冗余的增加，会造成时延.宋超等[10]提出了一种基于分布式实时信息的车载自组织网络路由协议，实时性好确保数据的有效传递，但是只适用于城市交通.

由于WAVE的网络中车辆节点高速的移动，网络拓扑结构变化快速，传统的路由机制并不能够很好地解决通信问题，因此路由机制的研究仍然是当前VANET发展研究的难点和热点.本文提出了一种基于Delaunay三角网的链路连接方式，组成通信网络，以实现组播通信，并对提出的模型在Repast J中进行了仿真，并给出了实验结果.

1 多三角形网络组播通信模型设计

多三角形组播通信模型的算法研究假定3个条件成立：①车联网中的车辆都配备WAVE设备，每辆车可以通过GPS获取各自的相关信息，比如实时速度，自身位置等；②车辆通过定期广播信标信息，可以获取其他车辆的ID号、位置、速度信息、方向信息；③若车辆处于繁忙状态，则会广播告知周围的节点.

多三角形通信网络（Multi-triangle Communication Network，MTCN）是在Delaunay三角网[11]中以1个车辆为中心，与其他相邻车辆组成多个三角形所构成的多边形.它的形状和大小取决于不规则分布的车辆密度和位置.所构建的MTCN必须满足于Delaunay三角网的2个重要准则和一些特性[11].这样建网的优点是：形成的网络结构良好，数据结构简单，数据冗余度小，存储效率高，可适应各种分布密度的数据，有利于与周围其它相邻的车辆进行通信[11].

1.1 模型定义

以图1为例，对一段高速公路上的汽车进行编号：1～10，并建立多三角形通信网，在该网络中，每个车辆相当于一个节点.共存在2种类型的节点：一种是网络中心的主节点；另一种是与主节点相连的从节点.主节点与从节点是相对的，每个节点既可成为主节点又可成为从节点.如图1中星形标注车辆1、2、7是所在各自群的主节点，其他均为从节点.

图1 多三角形网络模型Fig.1 MTCN model

主节点与其他从节点所形成的网络节点组成的集合称为群.主群是指当前所在的MTCN中主节点和若干从节点形成的群，从群是指以若干从节点为主节点所形成的群.主群与从群的概念也是相对的.在图1中，以车辆1为主节点形成的多三角形网络的群为车辆2-7，以车辆2为主节点形成的网络的群为车辆1，3以及7～10，以车辆7为主节点形成的群为车辆1、2、6、8.若1形成的群为主群，那么车辆2和7所形成的群为车辆1群的从群，反之，车辆2形成的群为主群，车辆1和7所形成的群就称为从群.

1.2 链路连接

为了保证组播通信的实时性和准确性，规定每个主节点最多与6个在其通信半径中形成MTCN的从节点进行分组.由于MTCN中的每个节点都是以与其最接近的2个点形成三角形，且各三角形的三边皆与其他三角形不相交.通过欧氏距离公式计算出每个主节点与其形成多三角形网络的其他节点的距离，通过比较得到在其通信范围内最近的6个节点作为从节点，其余的节点被舍弃.

由于车速变化频繁，节点的网络拓扑结构是动态的.为了避免网络节点频繁地断开和重连，并保证拓扑结构的稳定性，规定如果有新的车辆加入某群Gi，通过欧式距离公式和t=s/v，其中，来预测该车辆是否可以与群Gi连接时间t超过5 s，是则允许该车辆加入Gi，否则不允许加入Gi.

1.3 通信过程

1.3.1 主从节点通信

当车辆A进入高速公路时，先向其他车辆定时广播自己的信息，包括车辆A的ID、速度、位置等，然后根据周围其他车辆位置信息建立车辆A的MTCN，最后车辆A自主动态分组.先由主节点向本群的其他从节点（最多6个）发送通信请求，若从节点同意通信请求，则主节点确认通信，从而进行通信.主节点发送WSA信息，从节点在控制信道（CCH）上进行监听，当从节点收到WSA信息时，开始与主节点进行数据传输.

1.3.2 主从节点切换

当车辆进入一个稳定的群时，首先判断群中从节点个数是否小于6，若小于，则将车辆纳入群中.反之，计算主节点和该群内6个从节点之间的距离，和刚进入该群的节点与主节点之间的距离，去除距离最大的节点，重新形成稳定群.当某一车辆离开其所在群时，主节点向某一从节点发出请求是否断开连接，从节点给予答复，主节点再次确认.

1.3.3 紧急情况通信

一般情况下，群建立后都是主从节点间进行通信.但是，如果遇到紧急情况，需要点对点通信时，若目标节点在信息源节点通信半径内，则直接进行单播通信，单播通信的优先权要高于组播通信；否则，则计算出一条最优多跳的路径用来转发信息.

1.3.4 主群与从群之间通信

主群与从群之间通信的实质就是主群中的主节点与从节点的通信，主群中从节点作为某个从群的主节点，再与其所在从群中的从节点通信，从而形成群与群之间通信.

2 模型仿真及结果分析

2.1 测试平台及仿真环境

REPASE[12]（recursive porous agent simulation toolkit）是芝加哥大学社会科学计算研究中心研制的多主体建模工具，它提供了一系列用以生成、运行、显示、收集数据的类库，它是一个开源的仿真工具，专门用来仿真智能体（Agent）.Agent可以代表主动收集数据并具有复杂学习能力的决策者，还可以代表具有被动特点但没有认知能力的决策者.与NS2（Network Simulator version 2）相比，Repast更适合分析复杂适应系统模型，其功能更强大，在网络结构生成、Agent的空间关系管理方面更为出色，具有跨平台特性，可以在多个操作系统上安装和使用，而且模型的设计语言有了更多的选择.Repast J是使用Java语言设计的一个完全独立的模拟平台，避免了内存泄漏，且Java的跨平台特性使得在不同的平台上的安装和操作也很简便[13].仿真环境是32位系统、主频2.3 GHz、Repast3.1版本的Repast J，Eclipse.

2.2 实验步骤

本实验建立了一个40*8的双向车道，以Agent代表车辆，建立模型.投入若干数量的Agent进行仿真，每个Agent的初始速度不同，且每个Agent都有唯一的ID号，本实验选择40个Agent随机撒在车道，并沿着所在车道的方向移动.由于高速公路上车速为60～ 120 km/h之间，所以设每走1步的距离设定为16.7 m，每个Agent沿车道有3种移动方向：前方、左前方、右前方.为了简化模型，将Agent的速度随机设为：一步1格和一步2格，若Agent前方有车则考虑向左前方或右前方移动，否则沿直线运动.当Agent离开车道区域时，就将其消亡并且其ID号作废，重新在车道的另一端撒入新的Agent，并给其分配新的ID号和初始速度.实验步骤流程图如图2所示.

2.3 仿真结果

由于双向车道的车辆所运行的方向不同，因此只对同向运行的车辆进行建网，本实验选用图3中运行界面的右上侧图中第一车道的Agent进行建网.建成的MTCN如左上侧图所示.图4为对图3中动态的MTCN进行组播分析的结果.例如，以A为主节点的组播群为B、E、C、D、J、I；以B为主节点的组播群为A、E、I、F、G、H；以E为主节点的组播群为D、A、B、F，等等.动态分组的界面如图3中下部文字所示.从上述分析中可以看到，每个节点既可为主节点又可以从节点.当某车辆速度急剧变化或者是有新车辆并入该车道时，网络拓扑结构随之更新，重新分组通信.

图2 模型流程图Fig.2 Model flow chart

图3 多三角形组播模型运行界面Fig.3 Multi-triangular multicast model running interface

图4 组播分析图Fig.4 Multicast analysis chart

2.4 建网与通信时间估算

根据中华人民和国道路交通安全法实施条例：机动车在高速公路上行驶，车速超过100 km/h时，应当与同车道前车保持100 m以上的距离；车速低于100 km/h时，与同车道前车距离可以适当缩短，但最小距离不得少于50 m.可以得出1 km的高速公路上车辆的数量最多为80辆.本实验生成的Delaunay三角网是基于Bowyer-Watson算法[11，13].该算法的优点是基于散点的构网算法理论严密、唯一性好，网络的生成时间较快，较为理想.将实验中的Agent数量增加至100个，车道的长度增加一倍为80（约为1 km），并对同向行驶的车辆建立MTCN，如图5所示，其MTCN的生成时间为0.000 076 s.可以看出，生成网络的时间非常快.

图5 车辆模型以及其对应的MTCNFig.5 Vehicle model and its corresponding MTCN

国内外相关研究表明：高速公路上行驶的车辆，车辆速度一般呈高斯分布[14-15].根据文献[15]对高速公路上行驶车辆的车速统计数据：汽车速度服从均值为88.155 5 km/h、标准差为13.744 06 km/h的正态分布，通过公式（1）、（2）得出车速概率密度曲线和统计概率.

车速概率密度曲线和车速概率曲线如图6所示.由图6可以看出，大约85%的车辆在高速公路上行驶时速度处于74.4～101.9 km/h之间.根据IEEE802.11p标准，行驶中群内主从节点切换一次只需50 ms，当通信网络的拓扑结构频繁发生变化时，不影响数据传输的准确性和实时性[16].由于WAVE通信距离是0.3～1 km，在通信网络的拓扑结构保持不变时，车辆之间通信时间至少在39～130 s范围内.

图6 车速的概率密度曲线和概率曲线图Fig.6 Vehicle velocity probability density distribution curve and probability plot

3 结语

对于高速公路上的车与车的通信，本文在组播通信的基础上建立了针对动态节点拓扑结构实时变化的多三角形网络组播通信模型，并对网络模型的相关性能进行了仿真实验.由实验结果及分析可以看出，本文的算法在时间上有很大的优势，即节约了建网时间，在实时链接车辆的同时，又不影响数据传输的准确性和实时性，且避免了网络的频繁断开与重连，可应用于高速公路上车辆之间的通信.根据美国车联网通信技术需求标准，要求网络接入时间短传输时延低，一般要求在100 ms左右.该模型建网时间小于1 ms，切换网络时间在50 ms左右，传输时延在10 ms以内，总共在60 ms左右，符合其标准.因此研究基于车联网WAVE的多三角形网络组播通信模型对车联网的发展具有推动作用.下一步课题组需重点研究基于车联网的大数据的服务平台和车联网安全等问题.

[1]赵娜，袁家斌，徐晗.智能交通系统综述[J].计算机科学，2014，41（11）：7-11，45.

[2]吕子茹.基于WAVE的车载通信系统介绍 [J].现代电信科技，2010（8）：50-54.

[3]FAEZIPOUR M，NOURANI M，SAEED A，et al.Progress and challenges in intelligent vehicle area networks[J].Communications of the Acm，2012，55（2）：90-100.

[4]MEDARD M，LUCANI D E，STOJANOVIC M.Random linear networkcodingfortimedivisionduplexing：Whentostoptalking and start listening[J].Proceedings IEEE Infocom，2009，2350：1800-1808.

[5]NZOUONTA J，RAJGURE N，WANG G，et al.VANET routing on city roads using real-time vehicular traffic information[J]. IEEE Transactions on Vehicular Technology，2009，58（7）：3609-3626.

[6]PERDANA D，SARI R F.Multicast routing performance analysis for different mobility models on the IEEE 1609.4 standard using random Dijkstra algorithm[C]//Intelligent Green Building and Smart Grid（IGBSG）.2014：1-7.

[7]JEMAA I B，SHAGDAR O，GARRIDO P，et al.Extended mobility management and routing protocols for internet-to-VANET mu-lticasting[C]//International Workshop on Vehicular Networking&Intelligent Transportation Systems，2015：30-35.

[8]蔡莉，黄传河，张文涛，等.一种在Ad Hoc网络中基于地理位置的节约能量的组播路由算法 [J].计算机工程与应用，2004，40（2）：154-156.

[9]罗娟，肖仪，卢真，等.基于网络编码的多播车载网路由算法研究[J].计算机研究与发展，2011，48（9）：1616-1622.

[10]宋超，刘明，龚海刚，等.基于分布式实时信息的车载网络路由协议[J].软件学报，2011，22（3）：466-480.

[11]余杰，吕品，郑昌文.Delaunay三角网构建方法比较研究[J].中国图象图形学报，2010，15（8）：1158-1167.

[12]REPAST Development Group.Overview of REPAST[EB/OL]. [2014-05-18].http：//repast.Sourceforge.net.

[13]周雪梅，黎应飞.基于Bowyer-Watson三角网生成算法的研究[J].计算机工程与应用，2013，49（6）：198-200.

[14]FITZPATRICK K，ELEFTERIADOU L，HARWOOD D W，et al.Speed prediction for two lane rural highways[R].Washington：Federal Highway Administration，2000.

[15]阎莹，王晓飞，张宇辉，等.高速公路断面运行车速分布特征研究[J].中国安全科学学报，2008，18（7）：171-176.

[16]田敏华.基于IEEE1609部分协议的实现[D].北京：北京邮电大学，2013.

Multi-triangle multicast communication network model of vehicle networking WAVE

TANG Chun-ming1，YAN Bo1，YAN Ting1，YU Xiang2
（1.School of Electronics and Information Engineering，Tianjin Polytechnic University，Tianjin 300387，China；2.Center for Engineering Practice and Training，Tianjin Polytechnic University，Tianjin 300387，China）

Taking communication model of vehicles to vehicles in highway traffic as object，a multi-triangle communication network model based on vehicle networking WAVE is studied.The vehicle on the highway has the characteristics of high mobility，uncertainty and large density and this leads to the frequent disconnection and reconnection of the communication link.By applying a Delaunay triangulation to dynamic grouping，multi-triangular multicast communication is realized to ensure a fast and stable communication in vehicles.The model is simulated in Repast J and the result shows that it saves time in constructing a network.The network construction time is less than 1 ms，switching network time is about 50 ms，the transmission delay within 10 ms，total of time is about 60 ms.It complis with the US car demand networking communication technology standards，and can ensure dynamic node link quickly，avoide the frequent disconnection and reconnection of the network.This model can ensure data transmission in real time and be applied in communication of vehicles in highway traffic.

vehicle networking；multicast communication model；Delaunay triangulation；dynamic grouping；real-time

TP393

A

1671－024X（2015）05－0058－05

10.3969/j.issn.1671-024x.2015.05.012

2015-06-24

天津市第三批三年千人计划项目（62014511）；天津工业大学人才引进基金项目（030367）

汤春明（1971—），女，教授，硕士生导师，主要研究方向为网络安全检测、目标识别与追踪.E-mail：910541218@qq.com