车载自组织网中基于蚁群算法的延迟感知路由协议*

吴　敏，章国安，蔡　蓉

(南通大学 电子信息学院，江苏 南通 226019)



车载自组织网中基于蚁群算法的延迟感知路由协议*

吴敏，章国安**，蔡蓉

(南通大学 电子信息学院，江苏 南通 226019)

针对城市道路环境下车载自组织网(VANETs)中通信性能下降以及数据传输失败的问题，提出了一种基于蚁群算法的延迟感知路由(ACDR)协议。首先，建立双向车道的数学延迟模型；然后，根据提出的端点十字路口(EI)的概念，ACDR利用蚁群优化(ACO)寻找最佳路线，其中前向蚂蚁根据本地路段延迟以及当前十字路口与目的节点的端点十字路口之间的全局时延来选择路径，后向蚂蚁则负责在返回路径时更新信息素，同时，相邻十字路口之间利用贪婪转发算法进行数据包的传递。最后仿真比较了ACDR协议与连通性感知路由(CAR)协议的性能，结果表明提出的ACDR协议的数据包的传输延迟小，丢包率低，通信性能好。

车载自组织网络；路由协议；延迟感知；蚁群优化算法

1　引　言

车载自组织网(Vehicular Ad Hoc Network，VANET)是一种特殊的移动自组织网络(Mobile Ad Hoc Network,MANET)，是智能交通系统(Intelligent Transportation Systems,ITS)的重要部分，可以帮助驾驶员预测危险事故和避免交通堵塞，网络中车辆可以作为路由节点进行数据交换[1]。VANET路由协议根据数据包的目的节点数目不同分为单播、广播和多播路由，本文主要研究单播路由协议，内容主要分为两类，即基于网络拓扑的路由协议和基于地理位置信息的路由协议[2]。当确定路由路径时，基于网络拓扑的路由协议需要整个网络的拓扑信息来作出决策；而基于地理位置信息的路由协议只需要通过GPS获得车载的位置来做出数据递交的决策，因此这类协议对于频繁变化的网络结构更具有灵活性[3]，但此类协议仍然面临许多挑战，比如：不具备实时性与准确性、开销大、应用成本增加等。其中，地理源路由(Geographic Source Routing，GSR)是一种基于静态地图的路由，利用Dijkstra最短路径算法进行路由决策，寻找源点与目的节点的最短路径，但忽略节点的动态分布[4]；CAR(Connectivity Aware Routing)是一种基于连通性感知路由，源点利用广播信息探索路径，最终获得一条固定的路由路径，因此无法应对VANETs快速变化的拓扑结构[5]；GyTAR(Greedy Traffic Aware Routing)是一种利用局部街道动态信息的路由协议，利用车辆密度和前进方向进行路由决策，但是并未考虑全局信息，因此在数据转发过程中可能会导致网络分区[6]。

一般情况下，城市环境下的交通复杂多变，因此会造成重复开销和路由探索时间长等问题，为此，我们提出一种基于蚁群算法的延迟感知路由(Ant Colony Based Delay Routing,ACDR)协议。与上述协议不同的是，通信车辆首先寻找端点十字路口(Endpoint Intersection，EI)，将车辆之间的通信路由探索转化成对应十字路口之间的通信路由探索，这样有效地避免重复开销，并且相应地减少探索时间。但是，随着城市道路的不断变化，VANETs的拓扑结构也在快速变化，可能导致路由协议获取不准确的信息，无法获得可用路径。

蚁群优化(Ant Colony Optimization，ACO)算法可以解决组合优化问题，包括二次分配问题、车间任务调度问题、车辆路线问题和学习模糊规则问题。本文则利用ACO算法根据全局信息灵活地探索路径，并且寻找最优路径。

2　基于蚁群算法的延迟感知路由协议

2.1延迟模型

城市环境下的道路模型可以简化为m×n的十字道路模型。图1为3×3十字路口道路模型，共有9个十字路口I1～I9，12个路段，每条路段的路况皆随机分布。

图1　3×3十字路口道路模型

路段模型主要是根据城市环境下双向车道的多链路转发延迟而建立，假设两个十字路口Ii、Ij之间的直线车道方向相反且Ii、Ij之间的路段长度为L，数据包传输方向是向东；同时路段上车辆的无线通信传输范围为R，车辆的数目服从泊松分布[7]，向东的道路和向西的道路上车辆空间密度分别为λ1和λ2，车辆平均速度分别为v1和v2。

模型分析时，相邻十字路口之间的数据包利用贪婪携带-转发算法进行传输。另外，由于城市环境中交通灯的规则，车辆成簇移动，簇内的车辆相互连接，因此根据车辆簇群的规模大小，可以将车辆状况划分为如下3种不同的情况。

(1)全部连通状态

簇群范围超出路段边界，如图2所示，路段上的所有链路完全连通，两个十字路口之间的数据包利用跳与跳之间的贪婪算法进行转发。

(2)全部断开状态

车辆无法形成簇群，如图3所示，链路全部中断，且没有可用车辆转发数据包，因此十字路口之间的数据包只能通过车辆携带进行传输。

图3　全部断开状态的路段

(3)部分连通状态

簇群范围小于路段规模，如图4所示，路段上的车辆部分连通，因此连通路段上的数据包进行贪婪转发，而断开路段上的数据包进行贪婪携带传输。

图4　部分连通状态的路段

2.2蚁群算法

蚂蚁在寻找食物时会在所经过的路径上释放出一种特殊的分泌物(信息素)，当下一个路口时，随机挑选一条路径释放信息素，蚂蚁走的路径越长，则释放的信息素越小，当后来的蚂蚁再次碰到这个路口时，选择信息素浓度大的路径，则经过此路口的蚂蚁更多，因而形成一个正反馈机制[8]。

根据蚂蚁的多样性与正反馈以及个体之间的相互协作与信息交流，20世纪90年代Dorigo最早提出了基本蚂蚁系统，并应用于解决经典的旅行商问题等优化问题。

令G=(V，E)为n十字路口的加权有向图，其中V表示有向图顶点的集合，E表示边的集合，n=|V|，蚁群优化用于寻找图G中源节点的端点十字路口(Endpoint Intersection source,EIS)到目的节点的端点十字路口(Endpoint Intersection destination,EID)的最佳路径，每条边e(i,j)∈E表示一个路段，i、j分别表示相邻的两个十字路口，每条边上存在一个信息素变量τij和启发式信息ηij，当探索蚂蚁k访问当前十字路口i时，则选择十字路口j作为下一个访问的十字路口的概率：

(1)

随着探索蚂蚁的移动，路段上的信息素也在发生变化，因此当探索蚂蚁到达EID时，产生后向蚂蚁沿对应的路径返回EIS，进行信息素的更新，更新公式如下：

τij←(1-δ)·τij+δ·Δτij。

(2)

式中：j是i的下一个十字路口；(1-δ)·τij表示信息素的挥发；δ·Δτij表示信息素的增量；δ为挥发系数，δ∈[0,1]。

本文假设每个十字路口设置一个静态节点用于存储信息素。

2.3路由协议

ACDR路由算法通过寻找端点十字路口之间的路由代替寻找车辆之间的路由，有利于避免重复探索且节约时间，并且利用蚁群优化算法探索最佳路由路径，另外两个相邻十字路口之间利用贪婪携带-转发算法转发数据包[9-10]。主要步骤如下：首先，源节点车辆S发送路由请求数据包(RREQ)给其端点十字路口EIS，检查EIS是否有到目的节点的端点十字路口EID的可用路由信息，若有，EIS发送路由回复数据包(RREP)给S；然后，S直接将数据包转发给EIS，EIS可以为数据包动态地选择下一个优化十字路口，否则S启动探索蚂蚁进程，根据状态转移概率和信息素的更新选择下一跳十字路口，寻找EIS和EID之间的可用路径，进行路径优化，最终得到最优路径[11]。协议流程如图5所示。

图5　ACDR路由协议流程图

3　延迟分析

根据2.1节的模型可以得出3种情况的路段，接下来主要分析这3种路况的延迟、连通性以及跳数。

(1)全部连通状态

如图2所示，数据包在十字路口Ii与十字路口Ij之间进行传输，转发链路长度Lf定义为数据包在路段上进行跳与跳转发所经过的距离，此时Lf=L。

根据上述分析，Ii与Ij之间的传输延迟表示为

Dfc=Hfc·Tp。

(3)

连通性概率[12]可以表示为

Pfc=(1-e-(λ1+2λ2)·R)N-1。

(4)

式中：N表示路段上向东道路上车辆的数目，且N=L·λ1。

(2)全部断开状态

如图3所示，车辆Cv携带数据包穿过路段，此时携带链路长度Lc定义为车辆穿过路段的长度，此时Lc=L-R。

根据上述分析，传输延迟表示如下：

(5)

式中:V1表示与数据包转发方向相同的车辆的速度。

假设K是一个随机变量，表示双向道上R内车辆的数目，显然K满足泊松分布，概率质量函数(Probability Mass Function,PMF)表示为

(6)

因此，全部中断的概率Pfb表示为

Pfb=P(K=0)=e-(λ1+λ2)·R。

(7)

(3)部分连通状态

如图4所示，从车辆Cm到车辆C1的链路是完全连通的，但是路段剩下的链路部分是完全断开的，因此数据包只能从Cm到C1之间进行跳与跳的转发，然后车辆C1携带数据包传输直到进入十字路口Ij的传输范围，此时，转发链路的长度Lf等于十字路口Ii到车辆C1之间的距离，携带链路长度Lc=L-R-Lf，且部分连通性的概率Ppc=1-Pfc-Pfb。

在上述分析的基础上，传输延迟为

(8)

基于上述分析，因此相邻两个十字路口i、j之间的平均传输延迟和延迟方差分别为

Dij=Dfc·Pfc+Dfb·Pfb+Dpc·Ppc，

(9)

(10)

另外，路段上数据包转发的平均跳数为

Hij=Hfc·Pfc+Hfb·Pfb+Hpc·Ppc。

(11)

其中，由于全部中断的情况下，不存在转发跳数，因此Hfb=0。

图6～8分别是平均延迟与传输范围、车辆速度和车辆密度三者之间的关系曲线。在图6中平均延迟是关于传输范围和车辆空间密度的函数，交通信息的参数设置如下：车辆速度V1设为15 m/s；路段长度L为2 000 m；车辆空间密度λ1=λ2=λ分别为0.005 vehicle/m、0.015 vehicle/m、0.025 vehicle/m和0.035 vehicle/m。由图可知：车辆空间密度相同时，传输范围增大，数据包传输所需的延迟会减小；传输范围一定时，车辆空间密度越大，传输延迟越小。在图7中平均延迟是关于车辆速度和车辆空间密度的函数，传输范围R为250 m，路段长度L为2 000 m，车辆空间密度λ分别为0.005 vehicle/m、0.01 vehicle/m、0.015 vehicle/m和0.02 vehicle/m。由图可知：车辆空间密度一定时，车辆速度越快，延迟会逐渐减小；车辆速度相同时，车辆空间密度增加，传输延迟会减少。在图8中平均延迟是关于车辆空间密度和路段长度的函数，车辆速度V1为15 m/s，传输范围R为250 m，路段长度L分别为500 m、1 000 m、1 500 m和2 000 m。由图可知：路段长度相同时，随着车辆空间密度的增加，延迟逐渐减少；车辆空间密度一定时，路段长度越长，则延迟越高。

图6　平均延迟与传输范围的关系

图7　平均延迟与车辆速度的关系

图8　平均延迟与车辆密度的关系

图9～10分别是平均跳数与传输范围和车辆空间密度之间的关系。在图9中，平均跳数是关于传输范围和车辆空间密度的函数，交通信息的参数设置如下：车辆速度V1=15 m/s；路段长度L=2 000 m，车辆空间密度λ1=λ2=λ分别为0.005 vehicle/m、0.015 vehicle/m、0.025 vehicle/m和0.035 vehicle/m。由图可知：曲线先呈上升趋势，当到达一个临界点后呈下降趋势，因为当传输范围R小于临界值时，部分路段可能处于断开状态，则随着R的增大，路段断开的长度可能会减小，因而平均跳数会增加，当达到临界值时，随着传输范围的增加，数据包转发的次数会减少，因此平均跳数减小；同样，当传输范围一定时，车辆空间密度增加，则平均跳数增多。在图10中，平均跳数是关于车辆空间密度和路段长度的函数，车辆速度V1为15 m/s，传输范围R为250 m，路段长度L分别为500 m、1 000 m、1 500 m和2 000 m。由图可知：当车辆空间密度小于0.02 vehicle/m时，随着车辆空间密度的增加，平均跳数逐渐增加，当车辆空间密度大于0.02 vehicle/m时，平均跳数趋于稳定；对于不同的路段长度，路段长度越长，则平均跳数越多。

图9　平均跳数与传输范围的关系

图10　平均跳数与车辆空间密度的关系

4　ACDR路由分析

城市环境下车辆之间的通信频繁发生，尤其是在高峰期，为了减少重复的路由探索和路由开销，因此提出了端点十字路口的概念，并且利用蚁群优化算法根据当前十字路口存储的信息选择下一个十字路口进行数据包的转发，探索最佳路由。

4.1端点十字路口选择

利用通信终端(例如源车辆和目的车辆)所在路段的车辆空间密度和其与邻居十字路口的距离来选择端点十字路口，对于每个候选十字路口i给定一个评分，评分最高的十字路口为端点十字路口。评分公式如下：

(12)

式中：d(i)表示通信终端到候选十字路口i的距离；χ为加权因子；L对应当前路段的距离；Navg表示当前路段上车辆的平均数目；Ncon表示区域内车辆的平均数目。

4.2路由发现

当探索蚂蚁进行移动时，根据路段的延迟模型，每条边上对应的启发式信息ηij和信息素τij会发生相应的变化，ηij表示i和j之间路段的本地延迟，并且可以帮助蚂蚁探索新的路径，表达式如下：

(13)

式中：Dij、Dvij分别表示十字路口i和j之间的延迟和延迟方差；Dth表示EIS和EID之间的延迟临界值，定义如下：

(14)

式中：Distance(EIS,EID)表示EIS和EID之间的距离；v表示车辆速度。

τij反映从当前十字路口i到EID(在这条路径上，i的下一个十字路口是j)路径的全局延迟，Δτij是反向蚂蚁更新的信息素。Δτij的表示如下：

(15)

式中：Dj(i,EID)和Dvj(i,EID)分别表示从当前十字路口i到EID且经过十字路口j之间的路径上的延迟和延迟方差。

一旦所有的反向蚂蚁到达源节点时，EIS和EID之间信息素τ最大的路径为最佳路由，为了应对通信对的拓扑变化和自适应地选择最佳路由，一旦源节点或目的节点的端点十字路口EI改变，一个新的路由探索就会实现。

5　性能仿真

利用Matlab仿真软件对ACDR的性能指标进行仿真分析，并且与CAR[4]协议进行性能参数的比较。仿真环境选取4×4十字路口的城市道路进行模拟，相关仿真参数如表1所示。

表1　仿真参数设置

图11为平均延迟与累积分布函数的曲线，由图可知ACDR的累积分布函数始终高于CAR，同时当车辆速度较高时，两种协议的累积分布函数皆高于速度低时，意味着ACDR具有较低的平均延迟。CAR协议是一种基于源点位置的路由协议，不能及时自适应地处理拓扑的变化，但所提出的ACDR协议可以利用最新的路由信息动态地进行路由决策，寻找出最佳路由。

图11　平均延迟的累积分布函数

图12为车辆数目与数据包传输比值的曲线，由图可知车辆越多，数据包丢失越少，同时针对不同的车辆数目，ACDR的数据包传输能力较优，ACDR协议利用蚁群算法及时更新信息，适应网络拓扑的快速变化，最终寻找最优路径，避免网络堵塞；CAR协议根据源点位置确定一条完整的路由路径，但对于不断变化的网络结构而言，固定的路径会导致大量数据包的丢失。

图12　数据包传输比值与车辆数目的关系

6　结束语

本文提出了一种基于蚁群优化算法的车载自组织网络路由协议，首先利用ACO解决延迟的最优化问题，接着利用探索蚂蚁和反向蚂蚁探索所有可用路径，更新信息素表，最终选择最佳路由，并且在两个相邻十字路口之间，利用贪婪携带-转发算法进行数据包的转发。仿真结果显示，与CAR协议相比，所提出的ACDR协议延迟性能更优，数据包传输性能更好，可以自适应地处理网络的拓扑结构变化，更具有灵活性。但是蚁群算法复杂度比较高，搜索时间较长，仿真过程中容易出现停滞现象，因此今后可以考虑将蚁群算法与其他启发式仿生算法结合，优势互补，进一步优化系统性能。

[1]金婕,艾宝丽. 智能交通系统的无线信道建模[J].电讯技术,2015,55(3):262-269.

JIN Jie,AI Baoli.Channelmodeling for intelligent transport system[J].Telecommunication Engineering,2015,55(3):262-269.(in Chinese)

[2]AL-RABAYAH M,MALANEY R.A new scalable hybrid routing protocol for VANETs[J].IEEE Transactions on Vehicular Technology,2012,61(6):2625-2635.

[3]RAJESH K,KARTHICK V R,RAJ G S.A new scalable reactive location based ad hoc routing protocol for VANETs[C]//Proceedings of 2014 International Conference on Information Communication and Embedded Systems(ICICES).Chennai,Indian:IEEE,2014:1-5.

[4]CHO K,RYU M.A survey of greedy routing protocols for vehicular ad hoc networks[J].Smartcr,2012,2(4):125-137.

[5]ALSHARIF N,SHEN X S. iCARII:intersection-based connectivity aware routing in vehicular networks[C]//Proceedings of 2014 IEEE International Conference on Communications(ICC). Sydney:IEEE,2014:2731-2735.

[6]JERBI M,RASHEED T,SENOUCI S M,et al.Towards efficient geographic routing in urban vehicular networks[J].IEEE Transactions on Vehicular Technology,2009,58(9):5048-5058.

[7]ATHANASIOS P,PETER M,SIMONE F,et al.On temporal stochastic modeling of precipitation,nesting models across scales[J].Advances in Water Resources,2014,63(2):152-166.

[8]KADONO D,IZUMI T,OOSHIT F,et al.An ant colony optimization routing based on robustness for ad hoc network with GPSs[J].Ad Hoc Networks,2010,8(1):63-67.

[9]WANG S,LIN C,HWANG Y,et al.A practical routing protocol for vehicle-formed mobile ad hoc networks on the roads[C]//Proceedings of 2005 IEEE Intelligent Transportation Systems. Vienna,Austria:IEEE,2005:161-166.

[10]PANICHPAPIBOON S,PATTARA-ATIKOM W.Connectivity requirements for self-organizing traffic information systems[J].IEEE Transactions on Vehicular Technology,2008,57(6):3333-3340.

[11]LI G,BOUKHATEM L,MARTIN S.An intersection-based QoS routing in vehicular ad hoc networks[J].Mobile Networks & Applications,2014,20(2):268-284.

[12]SANTOS R A,EDWARDS A,EDWARDS R M,et al.Performance evaluation of routing protocols in vehicular ad hoc networks[J].International Journal of Ad Hoc and Ubiquitous Computing,2005,1(2):80-91.

吴敏(1992—)，女，江苏如皋人，硕士研究生，主要研究方向为车载自组织网络;

WU Min was born in Rugao,Jiangsu Province,in 1992. She is now a graduate student. Her research concerns vehicular ad hoc networks.

Email：125524853@qq.com

章国安(1965—)，男，江苏如皋人，2001年于东南大学获博士学位，现为教授、博士生导师，主要研究方向为无线通信网络理论与技术;

ZHANG Guoan was born in Rugao，Jiangsu Province,in 1965. He received the Ph.D.degree from Southeast University in 2001.He is now a professor and also the Ph.D. supervisor. His research concerns wireless communication network theory and technology.

Email：gzhang@ntll.edu.cn

蔡蓉(1991—)，女，江苏盐城人，硕士研究生，主要研究方向为车载自组织网络。

CAI Rong was born in Yancheng,Jiangsu Province,in 1991. She is now a graduate student. Her research concerns vehicular ad hoc networks.

The National Natural Science Foundation of China(No.61371113,61401241);Project of Ministry of Transport of the People′s Republic of China(2013-319-825-110)

A Delay Perception Routing Protocol Based on Ant Colony Algorithm in Vehicular Ad Hoc Networks

WU Min,ZHANG Guoan,CAI Rong

(School of Electronics and Information,Nantong University,Nantong 226019,China)

In order to solve the data transmission failure problem and improve the degradation of communication performance on city roads in vehicular ad hoc networks(VANETs),a delay perception routing protocol based on ant colony algorithm is proposed. Firstly,a two-way lanes model of delay is established. Then according to the concept of endpoint intersection(EI),the routing protocol uses ant colony optimization to find the best route.According to the local delay and global delay of a route between current intersection and the endpoint intersection of destination,path is selected by forward ants. Backward ants are responsible for updating pheromone in the return path.At the same time,packets are transmitted by greedy forwarding algorithm between the adjacent intersections. Finally,ant colony algorithm based delay perception routing protocol and connectivity aware routing protocol are compared by simulation. The simulation results show that the proposed routing protocol is superior in terms of packet transmission delay,packet loss rate and communication performance.

vehicular ad hoc network(VANET)；routing protocol；delay perception；ant colony optimization

10.3969/j.issn.1001-893x.2016.10.004

2016-03-02；

2016-06-03Received date:2016-03-02；Revised date：2016-06-03

国家自然科学基金资助项目(61371113,61401241);交通运输部应用基础研究基金资助项目(2013-319-825-110)

TN915.04;TP393

A

1001-893X(2016)10-1086-07

引用格式：吴敏，章国安，蔡蓉.车载自组织网中基于蚁群算法的延迟感知路由协议[J].电讯技术，2016,56(10):1086-1092.[WU Min,ZHANG Guoan,CAI Rong.A delay perception routing protocol based on ant colony algorithm in vehicular ad hoc networks[J].Telecommunication Engineering,2016,56(10):1086-1092.]

**通信作者：gzhang@ntu.edu.cnCorresponding author：gzhang@ntu.edu.cn