车载网中一种低延时的广播路由*

Automobile Technology - - 汽车技术 -

杨茂保 徐利亚 葛明珠 舒长兴332005) (九江学院,九江

【摘要】针对车载自组织网络中大量节点传输信息带来信道竞争,使数据包重传次数增多,引发广播风暴的问题,提出了车载网中一种低延时的广播路由( LLBR)。基于减少广播数据包节点数量的策略,对当前节点的邻居节点构建连通支配集,并优化近似成最小连通支配集,以该支配集中的节点为中继节点并以一定的概率广播数据包。仿真结果表明,所提出的广播路由与传统的广播方法基于邻居覆盖的概率转发( NCPR)和基于距离的多跳广播( DMB)相比,在平均端到端延时和数据包递送率方面有较大改善。 主题词:车载网 紧急信息 广播路由TP393 A中图分类号: 文献标识码: DOI: 10.19620/j.cnki.1000-3703.20180093 A Low Latency Broadcast Routing in VANET Yang Maobao, Xu Liya, Ge Mingzhu, Shu Changxing Jiujiang University, Jiujiang 332005) ( Abstract Broadcast storm was caused by the increase of data packet and channel contention resulting from【 】information transmission of large amount of nodes in the Vehicular Ad hoc Network (VANET). To solve this problem, a Low Latency Broadcast Routing (LLBR) was proposed in VANET. Based on the strategy to reduce the number of broadcasting data packet node, a connected dominating set was constructed for the neighboring nodes of the current node, which was optimized to approximate the Minimum Connected Dominating Set (M- CDS). The nodes of the M- CDS was used as relay node and data packet was broadcasted at a given probability. Simulation results have shown the effectiveness of the proposed broadcast routing is improved considerably compared to two traditional broadcast protocols NCPR and DMB in end-to-end latency and packet delivery rate. Key words: VANET, Emergency information, Broadcast routing

1 前言

Vehicular Ad hoc Network,

车载 自 组 织 网 络(

VANET)

是一种将传感器技术、短距离移动通信及信息

Mobile Ad hoc Network,

处理技术相结合的移动自组网(

MANET),

是智能交通系统的基础信息承载平台。

VANET

中的节点主要由车辆组成,车辆可利用车载传感器实时采集交通信息,通过与其他车辆的交流来广播安全、道路状况等信息,在改善交通环境、减少交通事故

VANET等方面具有积极的作用[1]。此外,在 中,车辆还

Road Side Units,RSU) RSU

可以与路侧单元( 通信,通过接入主干网,为车内成员提供更丰富的服务[2-5]。车载网中的广播路由算法主要有基于地理位置的 路由[6- 9]、基于内容的路由[10- 14]。基于地理位置的广播路由算法的优点是实现较简单、执行效率高,通常基于地理位置划分候选节点,选择距离广播节点更远的节点作为下一跳中继节点来转发数据包,但该类算法没有很好

VANET

地顾及到 中车辆节点移动速度快、网络拓扑变化快的特点,当数据包传输到车辆节点稀少的路段时,会产生极大的延时。基于内容的广播路由算法中,数据包含有本地拓扑信息,能高效率地选择中继节点来传输数据包,但由于拓扑变化快,会产生冗余,当节点缓存已满时会造成数据包的丢失。

因此,信息在车载网络中的传输面临诸多挑战:节点密度大、车速快使得网络拓扑结构变化极快,节点间形成的链路持续时间较短;节点的移动受道路的强制约

VANET

束,使得网络中节点分布不均匀,造成 中严重的网络分割现象;在道路区域,特别是热点区域(如交叉路口周围),节点的密度巨大,如不加限制地使所有节点自由广播信息,会带来激烈的信道资源竞争,使得该区域

VANET

的无线传输瘫痪。这些因素导致信息在 中的传输不稳定,本文提出一种低延时的广播路由,通过建立连通支配集,概率广播数据包来减少传输冲突。

2 单位圆盘图

VANET

本文讨论的 场景采用全向传输方式。根据全向传输方式中无线覆盖区域呈圆盘状的特点,该

Unit- Disk Graph,UDG)[

区域可用单位圆盘图( 15]表示,

G=(V,E),

即 其中, V为节点集, E为边集,即两点之间可形成链路。

以发送节点的位置为圆心,以无线通信最大传输范围为半径,且假设节点的最大无线传输范围相同,如果节点在另一个节点的通信范围内,则这两个节点可以通信,即它们之间存在一条链路。

UDG ID

在 模型中,每个节点都有唯一的 以标识身

V | | | S|

份。 表示网络中节点的数量, 表示任意节点集合S⊆ V(G) | E| ( v,vj)∈E(G)

中节点的数量, 表示边的数量。以 i

表示节点vi和vj有直接连接的边,即vi与vj相邻,节点vi和节点vj互为邻居节点。

Connected Dominating Set,CDS)

连通支配集( 是圆

D⊆ V(G), v∈

盘图G中的节点集合 对任一节点v, U或者v是D中节点的邻居节点。Neighbor ( v)

若v是图G中的一节点,集合 表示v的邻

居集。

d(u1,u2)

为顶点u1、u2之间的距离, R为节点最大传输

d(u1,u2)<

距离,如果 R,则顶点u1和u2有一条连通的边。

U是节点内维护的集合,存放当前节点为中心长度为d的路段内的所有节点。

3 路由选择

VANET

本文提出的广播路由方法为:对 热点区域

CDS;

中的车辆节点构造 对每个要传输的数据包,选择

CDS

中的节点作为广播路由的中继车辆节点,并按一定的概率广播。

3.1 连通支配集的构造算法

UDG,车辆节点的传输模型是 然而在图中,计算最

Minimum Connected Dominating Set,M小连通支配集(

CDS) Non- deterministic是不确定多项式时间问题(

Polynomial-time hard,NP-hard)[

16],即在多项式时间内不收敛,得不出解。本文研究该问题的近似解,即构建一 CDS

个近似最小的 算法。

3.1.1

算法描述

构建以当前节点S为中心的通信范围内初始连通

G(V,E), 1 CDS

图 用最小生成树思想[17]构造 个初始 。要

CDS CDS

使 内的节点数更少,则要保证选入 内的节点

M-CDS G(V,E)

具有更多的邻居节点,构建 。在图 中,当

CDS

前节点的邻居节点数即为该节点的度,所以在选择内的节点时,将节点的度作为权衡参数,节点的度越大,其权值越高。

3.1.2

算法实现

VANET source) d

构建 中以源( 节点为中心,长度为

CDS, CDS

的区域内的 并将该 广播到区域内的所有节

G(V,E) M-CDS

点。构建的初始图 算法和 算法流程分别

1 2

如图 、图 所示,其中, u0为 source

顶点, CDSinitial为初始连通支配集。 图2 M-CDS算法流程 3.1.3

算法分析

初始图G(V,E)算法是依据数据结构中经典的构

O(n3) M-CDS

造图方法建立的,时间复杂度为 。 算法的时间复杂度分析过程为:

a. O(n)

赋权值给图中的各边,其时间复杂度为 。

b. Prim O(n2)

算法生成最小生成树的时间复杂度为 。

c.

选择非叶子节点。对于构建好的最小生成树

1

中的节点,易知只需依次判断节点的度是否为 即可,

O(n)

故该部分的时间复杂度为 。

d.

去除冗余的节点。需要将初始支配集中的节点两两进行邻居节点对比。对于n个节点,两两遍历需

n(n- 1)/2

要查询的次数是 。假设两节点拥有的邻居节点

数分别为m1和m2,邻居节点集中的节点以ID

按序排列,则判断两节点的邻居集是否存在包含关系需要的查询

max{ m1, m2}

次数为 。在一个网络中,当每个节点拥有的

5.177 4logn[

邻居节点数超过 18]时,该网络是全连通的,因此, m1、m2均小于5.177 4logn,

则该步的时间复杂度为

O(n2logn)

CDS

由于上述步骤是顺序执行的,所以构建 的时间

O(n2logn)

复杂度是 。

3.1.4

结果分析

Greedy Algorithm) Rule-K

选择经典的贪心算法( 和

M- CDS

算法,在静态拓扑场景下与本文提出的 算法进

VANET

行比较,然后按照 场景设置节点传输半径R和

CDS

随机图中的节点数n,得到 内的节点数量与传输半

3

径R和图中节点数n的关系,如图 所示。 b) R= 100 m ( 3 CDS图 内的节点数量随图中节点数量的变化3a R =30 m CDS

由图 可知,当 时,贪心算法生成 内

Rule- K M- CDS

的节点数量较 算法和 算法多。当节点

M- CDS Rule- K

数较少时, 算法的表现与 算法较为接

Rule- K

近,但随着节点数的增多, 算法的性能略胜一

CDS

筹。这是因为随着节点的增多, 内的节点数量随之

Rule- K

增加,导致边界网关增多。 算法去除冗余节点

M- CDS M

的规则比 更为精确,能最大限度地得出

CDS, M-CDS

但是其相应的开销稍大些,相反, 算法实现简单,开销相对较小。

3b R =100 m CDS

由图 可知,当 时,贪心算法生成 内

2 Rule- K

的节点数量依然较其他 个算法大,而 算法与

M-CDS CDS

算法生成的 较为接近。这是由于节点传输

M- CDS

半径增大使得节点邻居数大量增加, 算法生成

CDS CDS

的 中每个节点拥有更多叶子节点,生成初始的 时会删除所有的叶子节点,即删除的冗余节点也更多。

10 km 25 m

在本文场景中,选择长为 、宽为 的矩形区域,随机投放一定数量的车辆节点,每个车辆节点的

R= 200 m,

连通半径为 距离小于R的车辆节点间能够通信,反之不能通信。每次随机产生的图如果是连通的,则继续试验,否则重新产生随机图。

R= 200 m, 10~设 车辆节点数量n的变化范围是

100, 100 CDS对每个n,生成 次网络拓扑图,求解图中 内

4

节点的数量,取平均值,结果如图 所示。 4 R= 200 m CDS图 时 的节点数量随图中的节点数量的变化4 CDS

由图 可知, 中包含的节点数量随图中节点数

100

量的增加而增加,当节点数达到 时,产生的随机图

M- CDS CDS

已经非常稠密,但是由 算法产生的 所包含的节点数却较少。

n= 20, 100~200 m, 100

设 R的变化范围为 进行 次试

5

验,取平均值,结果如图 所示。 5 n= 20 CDS图 时 的节点数量随节点传输半径的变化5 CDS

由图 可知,当节点传输半径增加时, 的数量CDS R= 200 m

减少,但 中包含的节点数量增加。当 时, CDS 1,

的数量几乎为 因为理论上此时几乎能覆盖到区域内的所有节点。

概率广播

M-CDS CDS

构建 后,本文以 中的节点作为广播节点来广播数据包。为了进一步减少节点的广播数据包

CDS

数量、减少传输冲突、提高信道利用率,本文针对中的节点,提出一种动态的按概率广播的策略广播数据包,根据节点的密度和邻居覆盖集计算节点的广播概率。

3.2.1

节点平均密度的计算本文根据局部邻居节点信息来计算网络中局部节点的密度。如果某节点的邻居节点数比网络中节点的平均邻居节点数多,则认为该节点所处的区域是节点密度大的区域,反之是节点密度稀疏的区域。

Newspapers in Chinese (Simplified)

Newspapers from China

© PressReader. All rights reserved.