杨茂保;徐利亚;葛明珠;舒长兴
【摘 要】针对车载自组织网络中大量节点传输信息带来信道竞争,使数据包重传次数增多,引发广播风暴的问题,提出了车载网中一种低延时的广播路由(LLBR).基于减少广播数据包节点数量的策略,对当前节点的邻居节点构建连通支配集,并优化近似成最小连通支配集,以该支配集中的节点为中继节点并以一定的概率广播数据包.仿真结果表明,所提出的广播路由与传统的广播方法基于邻居覆盖的概率转发(NCPR)和基于距离的多跳广播(DMB)相比,在平均端到端延时和数据包递送率方面有较大改善. 云盘控【期刊名称】《汽车技术》
【年(卷),期】2018(000)012
【总页数】6页(P13-18)
【关键词】车载网;紧急信息;广播路由
【作 者】杨茂保;徐利亚;葛明珠;舒长兴
激光夜视仪【作者单位】九江学院,九江 332005;九江学院,九江 332005;九江学院,九江 332005;九江学院,九江 332005
【正文语种】中 文
【中图分类】TP393
1 前言
车载自组织网络（Vehicular Ad hoc Network，VANET）是一种将传感器技术、短距离移动通信及信息处理技术相结合的移动自组网（Mobile Ad hoc Network，MANET），是智能交通系统的基础信息承载平台。VANET中的节点主要由车辆组成，车辆可利用车载传感器实时采集交通信息，通过与其他车辆的交流来广播安全、道路状况等信息，在改善交通环境、减少交通事故等方面具有积极的作用[1]。此外，在VANET中，车辆还可以与路侧单元（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|表示边的数量。以(vi,vj)∈E(G)表示节点 vi和 vj有直接连接的边，即 vi与 vj相邻，节点 vi和节点vj互为邻居节点。
连通支配集（Connected Dominating Set，CDS）是圆盘图G中的节点集合D⊆V(G)，对任一节点v，v∈U或者v是D中节点的邻居节点。
若v是图G中的一节点，集合Neighbor(v)表示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，MCDS）是不确定多项式时间问题（Non-deterministic Polynomial-time hard，NP-hard）[16]，即在多项式时间内不收敛，得不出解。本文研究该问题的近似解，即构建一个近似最小的CDS算法。
3.1.1 算法描述
构建以当前节点S为中心的通信范围内初始连通图G(V,E)，用最小生成树思想[17]构造1个正弦波发生器
初始CDS。要使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为初始连通支配集。
图1 初始图G(V,E)算法流程
图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和随机图中的节点数n，得到CDS内的节点数量与传输半径R和图中节点数n的关系，如图3所示。
图3 CDS内的节点数量随图中节点数量的变化
由图3a可知，当R=30 m时，贪心算法生成CDS内的节点数量较Rule-K算法和M-CDS算法多。当节点数较少时，M-CDS算法的表现与Rule-K算法较为接近，但随着节点数的增多，Rule-K算法的性能略胜一筹。这是因为随着节点的增多，CDS内的节点数量随之增加，导致边界网关增多。Rule-K算法去除冗余节点的规则比M-CDS更为精确，能最大限度地得出MCDS，但是其相应的开销稍大些，相反，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，车辆节点数量n的变化范围是10～100，对每个n，生成100次网络拓扑图，求解图中CDS内节点的数量，取平均值，结果如图4所示。
图4 R=200 m时CDS的节点数量随图中的节点数量的变化
由图4可知，CDS中包含的节点数量随图中节点数量的增加而增加，当节点数达到100时，产生的随机图已经非常稠密，但是由M-CDS算法产生的CDS所包含的节点数却较少。
设n=20，R的变化范围为100～200 m，进行100次试验，取平均值，结果如图5所示。
图5 n=20时CDS的节点数量随节点传输半径的变化
由图5可知，当节点传输半径增加时，CDS的数量减少，但CDS中包含的节点数量增加。当R=200 m时，CDS的数量几乎为1，因为理论上此时几乎能覆盖到区域内的所有节点。
3.2 概率广播
构建M-CDS后，本文以CDS中的节点作为广播节点来广播数据包。为了进一步减少节点的广播数据包数量、减少传输冲突、提高信道利用率，本文针对CDS中的节点，提出一种动态的按概率广播的策略广播数据包，根据节点的密度和邻居覆盖集计算节点的广播概率。
3.2.1 节点平均密度的计算
本文根据局部邻居节点信息来计算网络中局部节点的密度。如果某节点的邻居节点数比网络中节点的平均邻居节点数多，则认为该节点所处的区域是节点密度大的区域，反之是节点密度稀疏的区域。
网络中节点的平均邻居数量为：
式中，N为网络中节点的总数量；Ui为节点i的邻居数量。
spta3.2.2 节点的邻居覆盖集设定
本文的目标是当传输路由请求（Route Request，RREQ）包时，减少冗余包的传输，从而不影响网络吞吐量。根据节点所在区域的节点密度和广播包已覆盖的邻居节点集来动态设
定当前节点广播该数据包的概率。节点根据接收到的RREQ包中的节点信息更新自己的邻居节点表，并确定该RREQ包已覆盖的邻居节点集。如果当前节点的一跳邻居节点已经有相当部分被该RREQ包覆盖，则当前节点广播该RREQ包的概率较低。
节点的数据包覆盖邻居集指已经接收到同一个数据包的该节点的一跳邻居节点集。如图6所示，节点S将RREQ包广播到它的邻居节点A、B、C、D、E，由于节点C和节点E是D的邻居节点且已经收到了同样的RREQ包，所以对于该RREQ包，D的邻居覆盖集就是节点C和节点E。
图6 节点的数据包覆盖邻居集示意
3.2.3 节点广播数据包的概率
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议