高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
引用本文:
Citation:

基于蚁群算法的延时感知VANET路由协议

    作者简介: 吉 祥(1991—),男,江苏人,博士生,主要研究方向为车联网。E-mail:jixiang_ecust@mail.ecust.edu.cn;
    通讯作者: 虞慧群, yhq@ecust.edu.cn
  • 中图分类号: TP393

Ant Colony-Based Delay-Aware Routing Protocol for VehicularAd Hoc Networks

    Corresponding author: Huiqun YU, yhq@ecust.edu.cn ;
  • CLC number: TP393

  • 摘要: 针对城市车载自组网场景,提出了一种基于蚁群算法的道路延时感知路由协议。将数据转发过程分为直路模式和路口模式,利用蚁群算法中信息素的更新机制建立了一种基于蚁群算法的延时感知路段权重计算方法,并结合蚁群对最优化路径的探索过程给出了一种优化的反应式路由方案。仿真实验模拟了城市交通场景,将所提出的路由协议与GPSR、GSR、VACO路由协议进行性能比较,实验结果表明,该协议在数据分组投递率及延时方面均有较好的性能。
  • 图 FIG. 219.  FIG. 219.

    Figure FIG. 219..  FIG. 219.

    图 1  桥节点选择机制

    Figure 1.  Bridge node selection at intersections

    图 2  蚂蚁探测包转发过程

    Figure 2.  Forwarding process of ant packets

    图 3  PAnt格式

    Figure 3.  Frame format of PAnt

    图 4  区域地图示例及相应的权重矩阵

    Figure 4.  Map of a city area as an example and the corresponding adjacency matrix

    图 5  不同车辆节点密度下的分组投递率

    Figure 5.  Packet delivery rates for varying number of vehicles

    图 6  不同车速下的分组投递率

    Figure 6.  Packet delivery rates for vary vehicular velocity

    图 7  不同车辆节点密度下的平均端到端延时

    Figure 7.  Average end-to-end delay for varying number of vehicles

    图 8  不同车辆速度下的平均端到端延时

    Figure 8.  Average end-to-end delay for varying vehicular velocity

    表 1  仿真参数

    Table 1.  Simulation parameters

    NotionDescription
    Simulation area5 200 m×4 800 m
    Mobility modelSUMO Trace
    MAC protocolIEEE 802.11p
    Transmission range500 m
    Packet size1 024 bytes
    Beacon interval1 s
    Maximum acceleration5 m2/s
    Maximum velocity10~30 m/s
    Number of vehicles300~1 500
    Teva1 s
    ηph0.9
    τmin0.1
    下载: 导出CSV
  • [1] SHAREF B T, ALSAQOUR R A, ISMAIL M. Vehicular communication ad hoc routing protocols: A survey[J]. Journal of Network & Computer Applications, 2014, 40(1): 363-396.
    [2] FERDOUS F, MAHMUD M S. Intelligent traffic monitoring system using VANET infrastructure and ant colony optimization[C]// International Conference on Informatics, Electronics and Vision. USA: IEEE, 2016: 356-360.
    [3] KAUR H, KUMAR R. QoS realization for routing protocol on VANETs using ant colony optimization[C]// International Conference on Parallel. USA: IEEE, 2017: 585-590.
    [4] SILVA R, LOPES H S, GODOY W. A heuristic algorithm based on ant colony optimization for multi-objective routing in vehicle ad hoc networks[C]// Computational Intelligence and, Brazilian Congress on Computational Intelligence. USA: IEEE, 2014: 435-440.
    [5] CORREIA S L O B, CELESTINO J, CHERKAOUI O. Mobility-aware ant colony optimization routing for vehicular ad hoc networks[C]// Wireless Communications and Networking Conference. USA: IEEE, 2011: 1125-1130.
    [6] RANA H, THULASIRAMAN P, THULASIRAM R K. MAZACORNET: Mobility aware zone based ant colony optimization routing for VANET[C]// Evolutionary Computation. USA: IEEE, 2012: 2948-2955.
    [7] LI G, BOUKHATEM L. Adaptive vehicular routing protocol based on ant colony optimization[C]// Proceeding of the Tenth ACM International Workshop on Vehicular Inter-Networking, Systems, and Applications. USA: ACM, 2013: 95-98.
    [8] LI G, BOUKHATEM L. A delay-sensitive vehicular routing protocol using ant colony optimization[C]//2013 12th Annual Mediterranean Ad Hoc Networking Workshop (MED-HOC-NET). USA: IEEE, 2013: 49-54.
    [9] KARP B, KUNG H T. GPSR: Greedy perimeter stateless routing for wireless networks[C]// International Conference on Mobile Computing and Networking. USA: ACM, 2000: 243-254.
    [10] LOCHERT C, HARTENSTEIN H, TIAN J, et al. A routing strategy for vehicular ad hoc networks in city environments[C]// Proceedings of 2003 IEEE Intelligent Vehicles Symposium. USA: IEEE, 2003: 156-161.
    [11] JI X, YU H, FAN G, et al. Efficient and reliable cluster-based data transmission for vehicular ad hoc networks[J]. Mobile Information Systems, 2018: 1-15.
    [12] GOUDARZI F, ASGARI H, AI-RAWESHIDY H S. Traffic-aware VANET routing for city environments: A protocol based on ant colony optimization[J]. IEEE Systems Journal, 2019, 13(1): 571-581.
  • [1] 曹雅茜黄海燕 . 基于代价敏感大间隔分布机的不平衡数据分类算法. 华东理工大学学报(自然科学版), 2019, 45(4): 606-613. doi: 10.14135/j.cnki.1006-3080.20180515001
    [2] 刘静丁艳玲刘小云谭正庄启昕 . 三亲性二嵌段共聚物共混体系的自组装行为. 华东理工大学学报(自然科学版), 2020, 46(2): 1-11. doi: 10.14135/j.cnki.1006-3080.20190220001
    [3] 赵倩倩赵均徐祖华陈曦邵之江秦海中 . 空分装置群的设备启停及变负荷调度策略. 华东理工大学学报(自然科学版), 2020, 46(1): 84-91. doi: 10.14135/j.cnki.1006-3080.20181015005
    [4] 姚琴娟林家骏 . 基于双通道CNN的单幅图像超分辨率重建. 华东理工大学学报(自然科学版), 2019, 45(5): 801-808. doi: 10.14135/j.cnki.1006-3080.20180523002
    [5] 帅洁胡佳杰涂燕尚亚卓刘洪来 . 光响应小分子/表面活性剂自组装体的宏观光响应行为. 华东理工大学学报(自然科学版), 2019, 45(): 1-12. doi: 10.14135/j.cnki.1006-3080.20190821001
    [6] 薛敏杨健谭帅侍洪波 . 基于多数据结构的集成质量监控方法. 华东理工大学学报(自然科学版), 2019, 45(6): 938-945. doi: 10.14135/j.cnki.1006-3080.20180821002
    [7] 罗安王汉奎王建文 . 基于小冲杆试验数据的力学性能的数值模拟. 华东理工大学学报(自然科学版), 2019, 45(4): 669-674. doi: 10.14135/j.cnki.1006-3080.20180609002
    [8] 宋振振陈兰岚娄晓光 . 基于时序卷积网络的情感识别算法. 华东理工大学学报(自然科学版), 2019, 45(): 1-9. doi: 10.14135/j.cnki.1006-3080.20190508001
    [9] 王德勋虞慧群范贵生 . 基于深度学习的面部动作单元识别算法. 华东理工大学学报(自然科学版), 2019, 45(): 1-8. doi: 10.14135/j.cnki.1006-3080.20190107003
    [10] 赵菡诸葛晶晶林家骏 . 飞行状态敏感的关联门调节算法. 华东理工大学学报(自然科学版), 2019, 45(5): 795-800. doi: 10.14135/j.cnki.1006-3080.20180622003
    [11] 高天阳虞慧群范贵生 . 基于模拟退火遗传算法的云资源调度方法. 华东理工大学学报(自然科学版), 2019, 45(3): 471-477. doi: 10.14135/j.cnki.1006-3080.20180416001
    [12] 陈立皇程华房一泉 . 基于注意力机制的DGA域名检测算法. 华东理工大学学报(自然科学版), 2019, 45(3): 478-485. doi: 10.14135/j.cnki.1006-3080.20180326002
    [13] 王学武闵永顾幸生 . 基于密度聚类的多目标粒子群优化算法. 华东理工大学学报(自然科学版), 2019, 45(3): 449-457. doi: 10.14135/j.cnki.1006-3080.20180321005
    [14] 常青张天宇赵冰冰 . 基于机器视觉的手机异形主板非标自动化检测算法. 华东理工大学学报(自然科学版), 2019, 45(4): 632-638. doi: 10.14135/j.cnki.1006-3080.20180416006
    [15] 颜建军刘章鹏刘国萍郭睿王忆勤付晶晶钱鹏 . 基于深度森林算法的慢性胃炎中医证候分类. 华东理工大学学报(自然科学版), 2019, 45(4): 593-599. doi: 10.14135/j.cnki.1006-3080.20180410001
    [16] 高炳舒刘士荣 . 基于BoW模型的RGB-D SLAM算法的运动轨迹估计. 华东理工大学学报(自然科学版), 2019, 45(4): 623-631. doi: 10.14135/j.cnki.1006-3080.20180419001
    [17] 赖兆林冯翔虞慧群 . 基于逆向学习行为粒子群算法的云计算大规模任务调度. 华东理工大学学报(自然科学版), 2019, 45(): 1-10. doi: 10.14135/j.cnki.1006-3080.20190218001
    [18] 孙佩袁伟娜程华 . 一种新的基于异步NOMA的串行干扰消除算法. 华东理工大学学报(自然科学版), 2019, 45(5): 783-788. doi: 10.14135/j.cnki.1006-3080.20180412008
    [19] 翁童袁伟娜 . 一种基于SPSO算法降低FBMC系统PAPR的新方法. 华东理工大学学报(自然科学版), 2019, 45(): 1-7. doi: 10.14135/j.cnki.1006-3080.20190731002
    [20] 于中宝邵方明 . 并行系统中排列图的可靠性近似算法. 华东理工大学学报(自然科学版), 2019, 45(): 1-5. doi: 10.14135/j.cnki.1006-3080.20180531001
  • 加载中
图(9)表(1)
计量
  • 文章访问数:  6313
  • HTML全文浏览量:  1413
  • PDF下载量:  20
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-11-16
  • 网络出版日期:  2019-07-23
  • 刊出日期:  2020-02-01

基于蚁群算法的延时感知VANET路由协议

    作者简介:吉 祥(1991—),男,江苏人,博士生,主要研究方向为车联网。E-mail:jixiang_ecust@mail.ecust.edu.cn
    通讯作者: 虞慧群, yhq@ecust.edu.cn
  • 1. 华东理工大学计算机科学与工程系,上海 200237
  • 2. 上海市计算机软件评测重点实验室,上海 201112

摘要: 针对城市车载自组网场景,提出了一种基于蚁群算法的道路延时感知路由协议。将数据转发过程分为直路模式和路口模式,利用蚁群算法中信息素的更新机制建立了一种基于蚁群算法的延时感知路段权重计算方法,并结合蚁群对最优化路径的探索过程给出了一种优化的反应式路由方案。仿真实验模拟了城市交通场景,将所提出的路由协议与GPSR、GSR、VACO路由协议进行性能比较,实验结果表明,该协议在数据分组投递率及延时方面均有较好的性能。

English Abstract

  • 车载自组网络(VANET)作为智能交通系统中的关键技术[1],近年来已经成为车联网领域的研究热点。VANET技术通过全球定位系统(GPS)、传感设备等实现车辆状况以及周边交通路况信息的采集;使用车载单元(On Board Unit, OBU)设备实现车辆与外界的信息交互;通过路边单元(Roadside Unit, RSU)或基站等道路基础设施实现车与外部网络的连接,从而提供车载导航、实时预警等综合服务。

    VANET具有自组织、高传输速率、易扩展性等优点,然而,车辆节点的高速移动会造成通信链路的不稳定,这给VANET路由协议的设计带来了极大的挑战。如何为高度动态的VANET系统设计高效、可靠的传输技术,成为一项紧迫而又具有挑战性的课题。

    已经有一些研究将蚁群算法运用到VANET中[2-4],试图通过蚁群在源节点与目标节点间建立完整的路由路径。Correia等[5]提出了一种基于移动感知与蚁群优化的MAR-DYMO路由协议,利用车辆位置及速度信息预测其运动轨迹,并寻找生命周期最长的路径,但MAR-DYMO性能会随着车辆数量的增加明显下降,具有可扩展性方面的问题。Rana等[6]提出了一种基于ACO的移动性感知区域路由协议,将网络划分为多个区域,跨区域路由采用主动式路由方式,而区域内采用按需路由。Li等[7-8]运用蚁群算法来评估各路段的数据包转发延迟、带宽和投递率,提出了VACO主动式路由算法。假设在每个路口处有一个RSU来寻找并保存路由信息,但RSU的代价非常昂贵,尤其是在VANET部署初期。

    由于蚁群算法具有良好的适应性、自组织性、鲁棒性以及容错能力等特点,非常适用于解决VANET中的路由问题,但同时也存在扩展性差、部署成本高等问题。

    本文提出了一种基于蚁群算法的延时感知路由算法(ACDAP),将节点间的路由问题转化为交叉路口间的路由问题,可以提高路由路径的复用,减少路由发现开销。ACDAP通过蚁群算法策略来探测各路段的网络延时和连通性情况,并在交叉路口设置桥节点解析蚂蚁探测包数据,计算区域性路由信息,即路段权重信息;桥节点通过获取的路段权重表信息可以直接或间接地构建源节点与目标节点间的路由路径。仿真实验结果表明,ACDAP的性能优于传统的GPSR[9]以及GSR[10]算法,且优于同样采用蚁群策略的VACO算法。

    • 城市场景中VANET的路由路径遵循城市道路网络拓扑,并且只会在十字路口改变方向,本文将VANET路由过程分为直路模式与路口模式。在直路模式下,数据传输采用贪婪转发的方式;而对于路口模式,通过在十字路口选择特殊节点充当桥节点的方式连接各分段道路网络,并利用桥节点进行路由决策。

    • 首先,十字路口区域内的所有车辆都是候选节点,选取那些在路口处逗留时间尽可能长的车辆作为桥节点[11]。因此当有候选车辆因红灯而在路口区域停留时,优先选择这些由于红灯而等候在路口的节点,且红灯的剩余等候时间越长优先级越高;如果剩余等候时间最长的车辆只有一辆,那么直接选择该车辆担任桥节点;如果有多辆车辆符合桥节点竞争条件时,为了简单起见,随机选择其中一辆车作为桥节点。如果没有车辆在路口区域停留,考虑到经过十字路口中心的车辆正驶离路口,应当优先选择那些行驶方向朝路口区域中心且速度较低的节点。

      图1通过具体示例展示了桥节点选择过程。图中的圈代表了路口区域的限定范围,桥节点候选车辆集合为ζ={V0,V1,V2,V3,V4,V5},其中V0因红灯而停留等候,其余车辆均处于行驶状态。显然,在这种情况下,V0将被选为桥节点。假设V0节点不存在,那么候选车辆集合为ζ={V1,V2,V3,V4,V5}。可以看出,V2V3V4正向中心靠近,而V1V5正驶离路口区域,因而{V1,V5}被排除出候选行列,此时最终的候选车辆集合为ζ={V2,V3,V4},选择其中速度最慢的车辆作为桥节点。

      图  1  桥节点选择机制

      Figure 1.  Bridge node selection at intersections

      当桥节点即将驶出路口区域时,将触发新的桥节点选择过程,并且旧的桥节点会将桥节点角色所有的相关信息交付给新的桥节点,这样可以保证车载网络在交叉路口场景中的持续连通。

    • 位于十字路口处的桥节点持续间断性产生轻量级控制包(称为蚂蚁探测包,PAnt)用于探测路段连通性情况,并将PAnt发送至相邻路段中,PAnt产生的时间间隔记作TAntPAnt在直路阶段通过单播方式向前转发,直至抵达下一个交叉路口的桥节点。

      图2 示出了蚂蚁探测包转发过程。在交叉路口I1处,V1被选中为桥节点,其产生一个新的PAnt并发送至下一个路口,例如I2;在选择中继节点时,采用贪婪转发策略,V1选择邻居范围内离I2最近的节点V3作为下一跳的转发节点;当PAnt被路口I2处的桥节点V2接收时,I2将被记录到PAnt中,然后V2从{S23,S24,S25}路段(Sij表示路口IiIj之间的路段)中选择一个路径继续转发PAnt,且信息素高的路段被选中的概率更高。对于一般情况,假设IiK个相邻交叉路口,分别记为 I1, I2,…, IK,当PAnt到达Ii处时,根据式(1)选择概率pij最高的路段作为PAnt的下一个方向路径。

      图  2  蚂蚁探测包转发过程

      Figure 2.  Forwarding process of ant packets

      其中:ψij表示路段Sij的信息素值;f表示PAnt刚经过的路口ID;pR(Sij)表示选择路段Sij的随机概率,pR∈(0,1)。

    • PAnt的设计如图3所示。可以看出,PAnt由以下几部分组成:

      图  3  PAnt格式

      Figure 3.  Frame format of PAnt

      (1)Type:说明包的类型。

      (2)Packet_ID:包的标识信息,由产生PAnt 的路口ID以及产生的序列编码组成,中间通过“_”连接,如{Intersection_ID}_{Serial_Number}形式。

      (3)Target_Intersection:PAnt将要发送至的交叉路口,包括路口的标识ID以及位置(Position)信息。

      (4)Intersection_Sequence:PAnt经过并记录的交叉路口序列,包括了路口的ID、Position以及PAnt到达该路口时的时间戳(Timestamp),根据该时间戳可以计算出PAnt经过路段的延时情况。

      (5)Intersection_Count:初始值为0,PAnt每经过一次交叉路口时值加1;超过一定阈值时,PAnt被丢弃,相当于lifetime功能。

    • 蚂蚁每经过一个路段会沉积信息素(Pheromone)[12],因此当桥节点接收到PAnt时,桥节点会计算相应路段的信息素。如果PAnt中的Intersection_Sequence显示其经过了相邻的交叉路口IiIj,则说明这两个路口间道路是连通的,则相应的信息素会被更新:

      其中:ψij(t)与ψij(t+1)分别表示更新前与更新后路段Sij的信息素;∆ψij表示蚂蚁更新信息素,表示如下:

      其中:dij表示PAntIi传输至Ij所需延时;$d_{M_{ij}} $表示桥节点所记录的该路段蚂蚁探测包的最低延时;ω表示一个常量。可以看出,当ω设置为 ω∈(0,0.5)时,∆ψij始终小于1,且dij越小,∆ψij越大。

      蚂蚁所留下的信息素会随着时间挥发,挥发过程定义如下:

      其中:Teva表示信息素挥发过程的时间间隔;ηph表示信息素挥发因子,ηph∈(0,1);τmin表示信息素的最低阈值。

      结合式(2)、式(3)、式(4)可以看出,只要初始信息素值ψij(0)∈(0,1),无论信息素如何更新,始终有ψij∈(0,1);且ψij越大,代表路段Sij上网络连通性越好。

      路段信息素更新之后,桥节点将更新相应路段的权重值。对于路段Sij,路段长度表示为Lij,则路段权重定义为如下形式:

      ωij越小代表路段传输延时越小,连通性越好。

    • 桥节点通过对PAnt包携带信息的分析以及路段权重的计算,可以获取周围一片区域内道路的连通性情况,为路由转发提供全局性的视野,避免因贪婪转发而容易陷入局部最优的问题。图4示出了一片区域的地图示例及相对应的道路权重矩阵。

      图  4  区域地图示例及相应的权重矩阵

      Figure 4.  Map of a city area as an example and the corresponding adjacency matrix

      在ACDAP路由协议中,通过将车辆间路由的问题转换为终端交叉路口间路由的问题,以减少路由的重复探索,简化路由过程。当源节点Vsrc需要发送数据包时,其首先产生一个格式为<Vsrc, Vdest, msg, Options>的数据包Data_Packet,其中,Vdest表示数据包的目标车辆,msg代表了具体的消息,Options用于保存附加的路由信息。VsrcVdest之间数据传输的问题可以转变为在与VsrcVdest分别相邻的交叉路口IsrcIdest间寻找合适的路由路径的问题。

      为了方便表述,将VsrcVdest统称为终端车辆,IsrcIdest统称为终端路口。由于终端车辆有两个相邻的交叉路口,需要对其进行选择。这里主要通过考虑终端车辆与路口之间的距离以及车辆行驶方向选择合适的相邻路口作为终端路口,具体的参数设计如下:

      其中:Si表示相邻交叉路口的选择权重,值比较高的一方被选为终端路口;dti表示终端车辆与相邻路口间的距离;Lt表示所在路段的总长度;$\textit{χ} $表示参数系数,本文设置为0.5;λdir(Vt)表示终端车辆的移动方向。

      路由算法的具体步骤如下:

      Step 1 源节点Vsrc首先将Data_Packet发送至 Isrc处的桥节点;

      Step 2 桥节点解析路由包查看Idest是否包含在其权重矩阵中,如果是,则跳到Step 3;否则,桥节点找出权重矩阵中离Idest最近的交叉路口作为临时目标终端Itd

      Step 3 桥节点通过Dijkstra算法计算IsrcIdest(或Itd)之间的最短路径,并将获得的路口序列存放至Data_Packet包头之中,然后沿着所选路径转发Data_Packet,转发过程采用贪婪转发策略。

      Step 4 如果Data_Packet到达Itd,则重复Step 2~Step 4;否则,Data_Packet到达Idest后,由Idest处的桥节点判断Vdest所在的路段,并将Data_Packet沿着该路段转发至Vdest

    • 本文采用NS2(Network Simulation-2)进行仿真实验。首先利用OpenStreetMap地图获取真实的城市道路场景,并通过SUMO生成道路网格文件和车辆节点运动轨迹作为NS2的输入文件。每组仿真实验时长600 s,其中前100 s让生成的车辆节点在地图环境中随机运动,其后的500 s再统计相关的性能指标数据。通过改变参数中的车辆密度以及最大车速来获得不同的仿真场景,以考察不同因素对路由性能的影响。每组仿真实验独立重复20次,并取其所得结果的平均值作为最终的实验结果。仿真参数的具体设置如表1所示。

      NotionDescription
      Simulation area5 200 m×4 800 m
      Mobility modelSUMO Trace
      MAC protocolIEEE 802.11p
      Transmission range500 m
      Packet size1 024 bytes
      Beacon interval1 s
      Maximum acceleration5 m2/s
      Maximum velocity10~30 m/s
      Number of vehicles300~1 500
      Teva1 s
      ηph0.9
      τmin0.1

      表 1  仿真参数

      Table 1.  Simulation parameters

    • 为了评估ACDAP算法的性能,实验中使用GPSR、GSR、VACO算法作为对比方法。其中GPSR是一种基于贪婪转发的路由策略;GSR是一种经典的基于地图的路由算法;VACO是一种基于蚁群算法的路由算法,它利用ACO算法来衡量道路的网络状态,包括延时、带宽以及分组投递率,并借助RSU保存路由信息并进行主动式路由发现。这3种方法及本文算法都采用贪婪转发策略,但构建路由路径的策略不同,因此选择上述3种算法作为对比算法具有可比性。

    • 为了评估ACDAP算法的性能,从两个方面对算法进行评估,分别为数据分组投递率(Packet Delivery Ratio, PDR)和平均端到端延时(Average End-to-End Delay, E2ED)。

    • 数据分组投递率是指被目标节点成功接收的数据分组数量与源节点所发出的数据分组数量的比值。

      图5示出了数据分组投递率与车辆节点数目的关系。可以看出,VANET网络中的节点密度直接影响了网络的性能,且车辆节点密度越高,各算法的分组投递率也越高。这是因为当节点数量过少时,网络的分离状况导致大量的数据分组不能被交付,导致数据分组投递率较低。

      图  5  不同车辆节点密度下的分组投递率

      Figure 5.  Packet delivery rates for varying number of vehicles

      图6示出了数据分组投递率与车辆移动速度的关系。实验结果显示,随着车辆移动速度的增加,数据分组投递率呈下降趋势。这是因为车载网络的拓扑结构受到节点移动性的影响,车速越快,网络拓扑变化越频繁,导致连接链路的频繁断开,造成分组数据丢包率的增加。

      图  6  不同车速下的分组投递率

      Figure 6.  Packet delivery rates for vary vehicular velocity

      在4种算法中,GPSR的分组投递率始终最低。这是因为GPSR采用贪婪策略,选择离当前节点较远的节点作为中继节点,而距离越远,信号衰弱越严重,链路质量也越差,因而丢包的情况也越严重。同样采用贪婪转发策略,GSR利用地图计算得到了源节点与目标节点间的最短路径,但GSR在计算最短路径时,只考虑了距离因素,而没有考虑网络的实际情况,因此其网络性能改进并不显著。VACO利用蚁群算法获得了网络质量的诊断信息,从而获得了更为合理的路由转发路径,相比GPSR算法有了明显的性能提升。然而,VACO采用的是主动式的路由发现过程。由于VANET中节点的快速移动以及网络拓扑的频繁变化,主动式路由方式往往具有一定的迟滞性。同样利用蚁群算法进行路段网络性能的诊断,ACDAP主要考虑网络传输延时,延时越小意味着网络的连通性越好。实验结果表明,ACDAP的数据分组投递率始终高于其他3种算法。尽管都是采用贪婪转发,但不同的路由路径选择机制决定了各算法获得了不同的性能结果。ACDAP通过蚁群探测包采集各路段的连通性信息,获得了所在区域的路段权重情况,选择了连通性高的路段构成了路由路径,避免了传统贪婪策略所面临的局部最优问题。

    • 平均端到端延时是指网络中所有分组数据从源节点发出到被目标节点接收所需的平均时间间隔。

      图7示出了平均端到端延时与车辆节点数目的关系。从实验结果可以看出,随着节点密度的增加,节点在转发数据包时有更多的邻居节点作为候选,且遇到路由空洞的概率降低,因此所有算法的端到端延时都随着节点密度的增加而呈现下降趋势。尤其当网络中的节点数目小于900时,可以看到GPSR与GSR随着节点数目增多,端到端延时大幅下降,VACO与ACDAP算法的延时也有明显下降。这是因为网络空洞对路由延时的影响很大,当路由转发遇到网络空洞时往往需要采用存储-携带-转发的方式进行转发,而车辆携带行驶的速度显然无法和无线信号的传输速率相提并论。当节点密度较稀疏时,网络空洞数量较多,造成了传输延时较大。对于VACO与ACDAP算法,由于在选择转发路径时考虑了网络中各路段的实际网络性能,在转发过程中遭遇网络空洞陷入局部最优的概率大大降低,因此即使在稀疏场景下也具备一定的稳定性。

      图  7  不同车辆节点密度下的平均端到端延时

      Figure 7.  Average end-to-end delay for varying number of vehicles

      图8示出了平均端到端延时与车辆移动速度的关系。实验结果显示,随着车辆速度的增加,所有算法的端到端延时呈上升趋势。这是因为车辆节点移动性越强,车载网络的拓扑结构变化越剧烈,网络连通性和稳定性下降,导致了传输延时的增加。

      图  8  不同车辆速度下的平均端到端延时

      Figure 8.  Average end-to-end delay for varying vehicular velocity

      可以看出,GPSR算法的端到端延时在4种算法中最高,GSR比GPSR的延时略有降低,ACDAP的延时最低。GSR算法在GPSR基础上利用地图信息获取最短路由路径,但只是考虑了静态道路长度信息而没有考虑实际的网络状况,因此性能的提升并不明显。VACO与ACDAP都利用了蚁群算法获取道路中实际的网络性能,但VACO采用主动式路由发现,而主动式路由发现过程需要消耗一定的时间,且VANET中节点移动性较高,网络环境随时会改变;而ACDAP利用桥节点保存区域路段权重信息,当有路由请求时,可以根据权重表通过最短路径算法直接选择出到目标节点或与目标节点较近的路口之间的最优化路径,因而ACDAP获得了更低的网络延时。

    • 本文提出了一种基于蚁群算法的延时感知路由策略。首先利用蚁群算法中信息素的更新机制以及蚁群对最优化路径的探索过程,提出了一种基于延时感知的分段网络权重分析方法,并建立面向局部区域的路段权重矩阵,然后根据该权重矩阵,提出了一种区域路由算法,有效解决了现有路由算法容易陷入局部最优的问题。实验结果表明ACDAP能够保障VANET数据传输的可靠性,并提高传输效率。

      本文利用蚁群算法探索路段网络的连通性情况,并构建了优化路由转发路径,保障了VANET中数据传输的可靠性和效率。然而,ACDAP在路由路径上的转发依然采用的是贪婪转发策略,该策略虽然可以通过减少转发跳数而降低传输延时,但同时也增加了数据包丢失的风险。未来将完善ACDAP算法中的转发策略,在选择中继节点时考虑链路的稳定性等因素,提高数据的分组投递率。

(9)  表(1) 参考文献 (12) 相关文章 (20)

目录

    /

    返回文章