VANET & Routing

Outline Part I VANET 简介 VANET网络架构 单播 广播 Abiding geocast 2

Outline Part I VANET 简介 VANET网络架构 单播 广播 Abiding geocast 3

VANET 简介 车载网络（Vehicular Ad Hoc Network，VANET） 车载网络是一种通过网络提供车辆之间的通讯，由无 线通讯与数据传输技术，交通工具以及路边交通设施， 所形成的特殊的专用网络，属于高度定制化的移动式通 讯网络。 主要功能在于让所有的驾车者可以实时获得本地服务、 娱乐和交通相关的信息，以便提高行车效率，增进道路 安全与舒适性。 4

VANET具有其他移动自组织网络所不具备的特性和传输 问题 VANET具有其他移动自组织网络所不具备的特性和传输 问题.首先,VANET是移动自组织网络在道路上的应用,它具 有移动自组织网络的各种特点,比如自治性和无固定结 构、多跳路由、网络拓扑的动态变化、网络容量有限、 良好的可扩展性等.但特殊的应用环境,如狭窄的道路、高 密度节点分布、节点高速移动等,直接影响VANET网络的 信息传输能力,使得丢包增加、延迟增大.实验表明,在 VANET中使用传统的传输层协议(如TCP,UDP)和路由协议 (如AODV,DSR,OLSR等),数据包的成功传输率不会超过50%, 延迟大且延迟抖动剧烈.

通过分析移动自组织网络传输控制协议设计的要点和思 路,可以发现一些具有实用价值的思想和方案对VANET传 输控制协议设计极具借鉴意义 通过分析移动自组织网络传输控制协议设计的要点和思 路,可以发现一些具有实用价值的思想和方案对VANET传 输控制协议设计极具借鉴意义.虽然这些研究广泛而深入, 但目前缺乏对VANET这一特殊移动自组织网专门的研究. 由于VANET特殊的网络环境、特殊的运动规律及特殊的 应用背景,它的信息传输方法将有别于当前大多数的研究 成果.VANET传输控制协议设计更具有挑战性和独创性.

在VANET中,地理信息、信道质量、路径状态等都可以通 过一定的方法和途径获得,它们对设计高效、可靠的传输 控制协议具有重大意义;但同时,通信信道狭隘、节点高速 移动、节点密度过高等特有的不利因素又给VANET传输 控制协议设计带来了巨大的困难和挑战.

应用分类 车载自组织网络(VANET)的应用可以分为两大类: 1. 主要解决行车安全，称之为安全应用； 2. 主要提供增值业务，如满足乘客在行车环境中的娱乐 等功能，称之为用户应用。

安全应用 安全应用能够显著地降低交通事故的数量。研究表 明,如果司机在碰撞发生前的0.5秒被予以示警,就可以 避免60%的交通事故。安全应用主要在以下三类场景 中发挥作用： （1）事故现场预警：汽车在公路上高速行驶时,司机 只有很短的时间对前方车辆的动作做出反应，如果 前方发生了交通事故,正在朝事故发生点行驶的车辆 常常在司机开始刹车或者完全停下之前就已经撞上 了，而安全应用能够用于提醒司机某条道路的前方 发生了交通事故,从而避免连续相撞的发生，同时,安 全应用也能够用于及时提醒司机们与旁边的车辆距 离过近,从而避免事故的发生。

（2）交叉路口：在路口附近驾驶或者穿过十字路口是司机所 面临的最复杂的挑战之一，因为这时会有很多车辆交叉行驶, 使得车辆间发生碰撞的概率大大增加。根据美国交通部门的 调查,2003年在十字路口发生的车辆相撞事件数量占所有登记 的车辆相撞事件的45%,占所有交通事故的21%。如果有安全应 用能够在撞击发生之前提醒司机及时采取措施预防相撞,那么 事故的发生将会大大减少。 （3）拥挤的道路：安全应用还能够用于帮助司机选择到达目 的地的最佳行车路线，这样就有助于降低道路的拥堵,保持交 通的顺畅,从而提高道路的容量,避免交通堵塞，同时,司机在通 畅的道路上能够不那么容易烦躁,并且更倾向于遵守交通规则, 这对减少交通事故的发生也有直接影响。

用户应用 用户应用可以在旅程中给乘客提供广告、娱乐等信 息。基木的几种用户应用有: （1）Intemet连接：对Intemet的持续访问日益成为 大多数人的需求,再加上许多用户应用本身就需要对 Intemet的连接,因此,向车辆使用者以及其他的VANET 网络应用程序提供Internet连接服务是必要的，这也 意味着通常的Internet业务能够在车辆中被无缝地实 现(如连续下载大文件),而不需要重建。 （2）点对点(Peer to Peer，P2P)应用：在VANET 中,P2P应用也是打发无聊时间的一个有趣的方法，车 里的乘客们(非司机)能够分享音乐、电影等,并且能 够彼此聊天、玩游戏，在长途旅行时,他们还能够从 专门的服务器中上传或者下载音乐和电影。

（3）商业广告发布:一些商业机构可以通过VANET向 附近的车辆发布商业广告，例如产品或服务的内容、 价格、营业时间和位置等，这些商业机构可能包括 餐厅、酒店、加油站、旅游景点等，乘客可以根据 自己的需要对这些广告进行人工或自动地筛选，例 如当车上油箱的油位较低时,车辆就会自动将己收到 的附近加油站的广告显示给车主，这些广告在为乘 客提供便利的同时,也有利于提高广告的效率，这是 因为这些广告的接收者都是位于附近并且有需要的 人，例如超市和连锁店可以通过该系统向客户提供 订单,帮助客户快速找到停车场等服务，相对于电视、 电台和Intenet的广告,这种商业广告的发布更有针对 性。

VANET与MANET的比较 VANET可说是MANET（Mobile Ad hoc Network）的一种延 伸应用，基本的架构是相同的，具有无基础设施（自组 织）、多点式跳越连接（多跳）、动态拓朴的特性（移 动性）等特点。但两者之间仍多许多不同之处，下面列 出VANET与MANET的特性之比较。 13

VANET路由相关的特点 无线信道质量不稳定。车载网无线信道质量不稳定，并 且受到多种因素影响，其中包括路边建筑、道路情况、 车辆类型和车辆相对速度等。 高速变化的拓扑。由于节点之间相对高速的移动，VANET 的拓扑一直在改变。假设车辆的无线通信半径为250m， 车辆之间的相对速度为25m/s，链路的持续时间仅有10秒 钟。 频繁的网络分割。由于与上面类似的原因，VANET网络的 连通性也频繁的变化。尤其是在车辆密度较低的时候， 网络有很大的概率是不连通的。路由的设计必须要考虑 到网络分割的存在。

VANET路由相关的特点 充足的能量和储存能力。VANET中的无线通信节点为车辆 而不是普通的手持设备，所以可以很轻松的提供足够的 能量用于支持无线通信和计算，在路由过程中，能量和 储存可以认为是无限的。 无线通信的地理性。与传统网络中单纯依靠ID号或者IP 地址不同，由于车辆的移动性是依赖于已有道路，无线 通信的地理特征较大。甚至有些网络应用对于报文的目 的区域就是特定的地理空间。

VANET路由相关的特点 移动模型和可预测性。由于无线节点的高速移动和拓扑 的动态性，移动模型和预测是网络路由协议设计的重要 考虑依据。车辆节点的运动本质上受限于高速公路、道 路或者是街道，所以给予速度和地图，节点的移动在短 期内可以被预测。 不同的通信场景。VANET网络常常会呈现两种不同的无线 通信环境。在高速公路的通信场景中，环境是简单而且 是一维的。而在城市环境中就变得更加复杂，城市中的 道路常常被有很多十字路口和多叉路口。

网络容量有限。车载自组织网络中节点分布受到道路的 限制,呈现“管状”形态，根据随机平面的网络容量计算 方法可以推算出，其网络容量比一般无线移动网络更加 有限。在长度为L的道路上,最多可以同时传输(2L/(2+△r)) 个数据包，r是1跳的平均距离。 地理位置信息易获得。随着GPS(Global Positioning System,GPS)和GIS(Geographic Information System,GIS)的普 及，车载自组织网络(VANET)中的节点可以有比较丰富的 外部辅助信息，不仅可以获得自身的位置信息，还可以 得到所在区域的地理信息，比如路口分布、道路方向等。

VANET与MANET的比较 VANET MANET 节点移动速度 快 车辆速度 慢 一般为人的移动速度 拓扑变化性 高 低 路由方向 快 车辆速度 慢 一般为人的移动速度 拓扑变化性 高 低 路由方向 道路方向 随机方向 资源限制 覆盖范围 大 小 连接维持 难 易 11/30/2018 1

Outline Part I VANET 简介 VANET网络架构 单播 广播 Abiding geocast 21

VANET网络架构 在VANET 网络架构的分类里，主要可以分为以下三大种类： 22 VANET 示意图

VANET网络架构 Roadside-to-Vehicle Communications（RVC）： 所有车辆都会透过路旁的AP（access point）或是base station来与server沟通，可取得所需的信息。 23 Roadside-to-Vehicle Communications （RVC）

Roadside-to-Vehicle Communications 在此架构下主要的研究议题有： a. Mobility management： 由于在VANET的环境中每个vehicle具有高移动性的特质， 所以时常会离开目前使用中AP的服务范围而进入另一AP 的服务范围，这就是所谓的切换(HANDOVER)问题。目标 为如何维持原本的信息传输而不造成封包遗失，让使用者 觉得连线是一直存在的，不需要有重新连线的动作。 b. Choosing Internet gateway: 一台车时常会在不只一个AP的服务范围内，这类的问题主 要在如何选择一台AP以达到最高传输效益。考虑的因素 包括路径上可使用之频宽大小或是需要经过的hop数目等 等。 24

VANET网络架构 Inter-Vehicle Communications (IVC)： 在此架构下车辆可以通过其他车辆主动要求所需的信息，或是 当前方有紧急事件发生时，车辆彼此间也可以迅速交换讯息。由于 此方式并无路旁的AP或是基地台可供使用，故当车辆间距离太远， 超出彼此能够通讯的范围时将会发生断线的情况。 25 Inter-Vehicle Communications （IVC）

IVC Routing Unicast Routing Cluster-Based Routing Geocast Routing Broadcast Routing 26

Outline Part I VANET 简介 VANET网络架构 单播 广播 Abiding geocast 27

Unicast Routing 近年来提出的车对车routing protocol 如以 下树形图所示，主要的分类有： 28 IVC routing protocol

Unicast routing Topology-based routing protocols 29

Unicast routing Proactive Reactive Topology-based routing protocols 使用目前网络中所有连线的信息找出一条最佳路径来决定怎么传封 包，又可分为两大类： Proactive 每台车都会维护并且储存一个table（通过beacon packet 来维 护），纪录与其他车辆间的连线状况。所以每隔一段时间每台车 都要广播自己table的信息给其他车辆，彼此交换讯息然后各自更 新自己的table。（OLSR） Reactive 只有在需要的时候才开启和某台车之间的连接，并且只维护正 在使用中的连接。(AODV/dsr) 30

Unicast routing Geographic routing 每台车拥有的信息只有目前附近车辆的状况。主要根据下面两 个条件来决定数据包如何传送。 数据包的目的地位置，这个位置会储存在每个封包的 header中， 而且在这边会假设传送端都会知道接收端的位置在哪里(如通过 GPS取得)。 根据目前one-hop neighbors的位置，one-hop neighbors就是那些 可以直接传送到的车辆，也就是在一台车的传送范围内的车辆 都是one-hop neighbors。

节点2的one-hop neighbors information 邻居号 方向 距离 1 -1 100 3 4 200 节点2的one-hop neighbors information

Geographic routing Geographic routing又可分为以下三类： None-DTN (Non-Delay tolerant network) DTN (delay tolerant network) Hybrid 33

None-DTN 此类protocol不考虑连线有可能会断断续续的状况，故主 要用于车辆密度较高的VANET环境中。主要的观念是 Greedy forwarding，但Greedy forwarding会造成local maximum。所以这一类的routing protocol就是用各种方式 来应付这种到达local maximum的状况。常见的方法有 GPSR, CAR, A-STAR, STBR等。 34

Greedy forwarding An intermediate nodes forward a packet to the direct neighbor which is closest to the geographic position of destination 35

Local maximum Problem 36

Local maximum

Greedy Perimeter Stateless Routing (GPSR) Perimeter Forwarding 38

Example A packet with destination D reaches a local maximum at node S. 39 S要传送data到D 但发生local maximum(S的邻居没有一个比S接近D) 这时就采用 greedy routing 中的右手定则 找出next hop直到她遇到第一个协调员再经由他帮忙forwarding A packet with destination D reaches a local maximum at node S. The forwarding of the packet is then switched to the repair strategy and it is routed along the street until it hits the first coordinator node.

DTN

DTN 相反地，由于车辆通常有很高的移动性，所以DTN是考 虑连线时常会中断的环境。当传送端准备要送出封包时 若附近没有其他车辆或是连线相当不稳定，就会先把封 包存着，直到移动到附近有别的车辆再传送出去(carry- and-forward)。常见的方法有VADD, GeOpps等。 41

Hybrid 综合none-DTN和DTN两种模式，有none-DTN的greedy mode和DTN的 carry-and-forward。主要会使用none-DTN模式，但会根据下面几种网 络连线情况由none-DTN模式切换到DTN模式：目前封包已经经过了 多少hop,附近车辆的传送质量, 还有附近车辆相对于目的地的位置等 等。 42

Outline Part I VANET 简介 VANET网络架构 单播 广播 Abiding geocast 43

Broadcast Routing Broadcast是VANET常用的一种路由，像共享交通讯息、 天气、紧急讯息。 一种简单的广播服务是flooding，每个节点重新广播收到 的讯息。Flooding可以保证每个节点都收到讯息。 Flooding在节点是数量少的时侯性能很好，当每个节点收 到讯息并且要广播讯息时，会造成封包的碰撞，会消耗 大的带宽资源。 44

车辆密度会随着不同时间、不同地区而变化。极端情况 下有两种情况： 1. 密集网络 2. 稀疏网络 通过周期性的发送beacon包获得周围邻居节点的信息， 根据邻居节点的数目判断是否是密集网络。

广播风暴问题： 广播在网段内大量复制，传播数据帧，导致网络性能下 降，甚至网络瘫痪，这就是广播风暴。 如何解决广播风暴问题？ 直观上讲，减少广播报文的发送。但是要保证让尽可能 多的节点收到广播信息。 下面，来看一下几个针对广播风暴问题提出的路由协议。

AutoCast 假设：为了避免广播风暴，平均情况下只需要收到数据 节点中的两个转发数据；而且当一个节点转发数据时， 平均情况下只有40%的邻居节点是第一次收到这个数 据。 覆盖方式：概率转发 p= 2/(n*0.4) 举例： 10个邻居的节点转发数据包的概率为 2/(10*0.4)=0.5。 概率转发缺陷修正：重复广播，最优广播间隔n/Pref—— 经验值 主题：数据传输刚开始时，新产生的数据是以flooding的方式发送的，但是只有部分节点参与了转发。转发概率文章没有使用定值60%-80%，而是动态的，基于节点的邻居数目。为了避免广播风暴，平均情况下只需要收到数据节点中的两个转发数据；而且当一个节点转发数据时，平均情况下只有40%的邻居节点是第一次收到这个数据。因此一个有10个邻居的节点转发数据包的概率为2/(10*0.4)=0.5。

OAPB 基本思想：减少转发和重发节点集的数目。 主题内容：每个车辆节点根据其两跳内的局部信息决定 它的重发概率。 主要参数：Pro, Prosh, Prosh2，转发概率∅是这三个数据的 平均值。 1. Pro是通过一跳节点能到达的两跳节点的数目和与一跳 节点的比值（如果小于等于1）， 2. Prosh是一跳节点与一跳两跳节点数目和的比值 3. Prosh2是两跳节点与一跳两跳节点数目和的比值。 等待转发时间∆(t)：根据∅求得， ∅越大，等待时间越少。 局部信息的获得：通过周期性的hello包。文章中根据节点两跳内的信息计算出Pro, Prosh, Prosh2，转发概率∅是这三个数据的平均值。其中， Pro是通过一跳节点能到达的两跳节点的数目和与一跳节点的比值（如果小于等于1），Prosh是一跳节点与一跳两跳节点数目和的比值， Prosh2是两跳节点与一跳两跳节点数目和的比值。 等待时间根据∅求得， ∅越大，等待时间越少。

p-Persistence 主题：当车辆装有GPS的时候，是基于距离的，对节点j， 分为三种方式： 1. 2. 3. 当汽车没有GPS的时候，上述的广播策略可以改用收到信 号强度（RSS），原理和基于距离的是一样的。 策略1. 收到节点i的数据包后，节点j检查数据包的id并以概率Pij转发出去，如果是第一次收到这个数据包；如果不是，则丢弃。 策略2. 收到节点i的数据包后，如果是第一次收到这个数据包并且没有在分配的时槽前再次收到这个数据包，节点j检查数据包的id并以概率1在分配的时槽Tsij转发出去；如果不是，则丢弃。 策略3. 收到节点i的数据包后，如果是第一次收到这个数据包并且没有在分配的时槽前再次收到这个数据包，节点j检查数据包的id并以预先定义的概率P在分配的时槽Tsij转发出去；如果不是，则丢弃。 当汽车没有GPS的时候，上述的广播策略可以改用收到信号强度（RSS）原理和距离是一样的。

LDMB 主题：LDMB--基于链路的分布式多跳广播 步骤1. 节点j收到节点s的广播报文，计算接收概率Psj， 若Psj>=Pth，其中Pth是概率的阈值, 节点j成为候选节点。 步骤2. 节点j再根据Psj算出等待时间Tw，开始等待。 步骤3. 如果在等待过程中，j第二次收到这个广播包，则 跳到步骤5。 步骤4. j等到时间Tw转发数据包。 步骤5. j停止等待，过程结束。 如果s发出数据包，等待一个最大等待时间后都没有他的 邻居节点转发数据包，那么s重发这个数据包。 如果s发出节点后等待一个最大等待时间后都没有他的邻居节点转发数据包，那么s重发这个数据包。 收到源节点s发出的数据包后，在广播传播方向上的节点j会算出数据包接收概率Psj，对任何Psj>=Pth，其中Pth是概率的阈值，节点j是转发数据包的候选者。

协议 优点 缺点 AutoCast 简单 不具有动态性； Flooding可能会不正常停止 OAPB 具有动态性 需要获得节点一跳、两跳邻居的信息 LDMB 考虑了链路状态； 时延问题

Outline Part I VANET 简介 VANET网络架构 单播 广播 Abiding geocast 53

持续性地理多播（Abiding geocast）： 车载自组织网络（VANET）中信息在一个特定的区域中 持续地存在的问题。 地理多播是多播的一种特殊形式。

应用场景 1. 当公路上出现事故时，处理事故需要一定的时间，警 告信息不能只广播一遍，而应该在附近的区域持续存在 一定时间； 2. 停车场向附近的车辆发布还有空闲停车位的信息； 3. 一个餐馆向潜在顾客可能存在的附近区域发布广告； ……

主要问题 1. 持续广播节点（集合）的选择； 2. 持续广播策略（时机、间隔）； 3. 多跳区域覆盖问题； 4. 链路质量问题； 5. 区域的界定。

已有策略 1. LINGER 2. homeZones 2. GVI

LINGER LINGER会把数据从数据源传送到感兴趣的区域并在这个区域内保持信息的 存在。 区域：一个半径为R的圆。 关键：信息载体的选择。 内容：计算出一个基于距离、角度、速度的值i (d, θ, v)，值越大越适合做信 息载体。当信息载体进行位置更新时，重新计算i (d, θ, v)，若为负则寻找一 个更适合的信息载体。 缺点：携带信息的节点始终只有一个，当区域很大时，不能覆盖整个区域； 而且，如果这个节点在离开区域时没有成功的转发信息，就可能造成信息 的丢失。

GVI 主题：车辆作为虚拟的基础设施。 图中，A、B、D、F被选为候选节点

根据每个候选节点到达十字路口中心的时间作为参数算出每个候选 节点的权重，权重最大的成为广播的发送者。每隔一个周期重新进 行一次选择，一个周期的时间由车辆能够停留在区域中的时间决定。 缺点：需要较高的交通密度，不然会失败。广播发送中的每次切换 需要很大的开销。应用场景很局限。

参考文献 [1]Hui Zhang, Xinming Zhang. An Adaptive Control Structure based Fast Broadcast Protocol for Vehicular Ad hoc Networks, IEEE Communications Letters, 21(8), 2017. [2]Xinming Zhang, Long Yan, Wen Li. Efficient and Reliable Abiding Geocast Based on Carrier Sets for Vehicular Ad hoc Networks, IEEE Wireless Communications Letters, 5(6), 2016. [3]Qing Ding, Bo Sun, Xinming Zhang. A Traffic-light-aware Routing Protocol based on Street Connectivity for Urban Vehicular Ad hoc Networks, IEEE Communications Letters, 20(8), 2016. [4]Xinming Zhang, Xulei Cao, Long Yan, Dan Keun Sung. A Street-centric Opportunistic Routing Protocol Based on Link Correlation for Urban VANETs, IEEE Transactions on Mobile Computing, 15(7),2016. [5]Xinming Zhang, Kaiheng Chen, Xulei Cao and Dan Keun Sung. A Street- centric Routing Protocol Based on Micro Topology in Vehicular Ad hoc Networks, IEEE Transactions on Vehicular Technology, 65(7),2016.