0 引言

　　车联网VANET(Vehicular Ad Hoc Network)是自组织网(Ad Hoc Network)的特例。VANET中的车辆可与邻近的车辆或路边设施(Road Side Units，RSU)通信。为此，VANET的通信可分为车间通信(Vehicle-to-Vehicle，V2V)和车与基础设施通信(Vehicle-to-Infrastructure，V2I)。在V2V通信中，车辆采用短距离无线技术实现车辆间信息的交换，如Wi-Fi 和WAVE[1]。车辆通过特殊的电子设备使其能接收、发送消息。在V2I通信中，道路上的车辆能与邻近的RSU进行连接并交互信息。本文，主要针对V2V通信展开分析。

　　在V2V中，车辆通过车载单元向其他车辆传递消息。车辆的快速移动和其分布的不均匀，为VANET的路由提出了挑战。首先，链路的使用寿命受车辆移动的影响；其次由于网络拓扑动态变化，每个车辆的路由表需不断的更新，这将会增加额外通信负担，甚至会引起堵塞[2-3]，使得数据包的传输变得更为艰难。为此，本文，提出多路径路由算法。

　　依据路由策略，路由可分为5类[4]：(1)基于拓扑路由(Topology-Based Routing)；(2)基于位置路由(Position-based Routing)；(3)分簇路由(Cluster-based Routing)；(4)广播路由(Broadcast Routing)；(5)组播路由(Geocast Routing)。在拓扑路由中，用表存储拓扑信息并通过请求更新，如AODV[5]。在位置路由中，车辆通过系统获取车辆的位置信息决策路由，如GPSR[6]。分簇路由[7]是将节点分簇，构成虚拟网络结构。地理区域被划分为网格，并在网格内选取节点作为簇首(Cluster Head)。簇首负责簇间以及簇内的协调工作。广播路由就是通过广播分发数据包，如BROADCOMM[8]。组播路由在地理区域内传递数据，并限制区域内泛洪，如IVG[9]。每类路由具有各自的独立的特点。本文提出的算法引用拓扑和基于位置路由两种策略理念。

　　VANET的路由可描述成单路径、存储转发路径和多路径路由。现存有大量的多路径路由，如按需多路径距离矢量路由[10](Ad hoc On-Demand Multi-path Distance Vector，AOMDV)，S-AOMDV[11]，AODVM[12]。这些路由是基于AODV的改进版，属于反应式路由，不具有可扩展性。例如，S-AOMDV通过额外的数据提高路由发现效率以及修复路由失败，这会引起通信拥塞，降低带宽利用率。

　　移动自组织网的研究工作[13-14]表明，受昆虫激励的自然启发算法被成功地引入路由机制，如基于蚁群优化(Ant Colony based Optimization，ACO)。与其他算法[15-16]相比，此类算法表现良好的性能。如：通过共享局部信息，减少路由负担；提供多路径路由，以防路由失败。

　　目前，面向VANET的移动感知的蚁群优化算法[17](Mobility-Aware Aant Colony Optimization，MARDYMO)是唯一受自然启发的路由算法。该算法属于反应式路由，采用广播机制向网络内车辆传递消息，这将占用大量的带宽，且不具有可扩展性。

　　本文提出了混合式的ACO算法。该算法将充分有效利用带宽，并具有可扩展性，对链路断裂具有强健性。将车辆归入区域，每个车辆属于一个或两个重叠区域。在区域内通过先应式算法寻找路由。在区域间通过存储于每个区域内的局部信息，并采用反应式算法寻找路由。通过这种方式，减少广播和拥塞。充分利用车辆的移动模型、车辆密度和车辆速度去构建多路径算法，即(Mobility Aware Zone based Ant Colony Optimization Routing for VANET，MAZACORNET)。

　　车辆的移动使得车辆在短时间内远离彼此的通信范围。为此，在设计路由时，必须对车辆的位置以及车辆间连接进行管理。在MAZACORNET中，通过全球定位系统(Global Positioning System，GPS)获取位置和速度信息。通过车辆间连接管理提高路由的稳定性，通过车辆的位置、速度信息可计算链路的稳定性。

1 蚁群优化算法

　　从自然界得到解决问题的方法被称为群体智慧(Swarm intelligence，SI)。作为群体智慧之一的蚁群优化算法就是被广泛应用于解决静态和动态问题[18]。

　　Goss[19]研究了蚂蚁的行为，研究结果表明，蚂蚁能够从食物源到自己巢穴之间找到最短路径，而且能够轻巧避开障碍物。蚂蚁在通往食物路径上存储化学物质，将这种物质称为信息素。后续的蚂蚁依据信息素沿着路径移动。蚂蚁通常向信息素多的地方靠拢。沿着信息素多的地方移动，就能以最短路径找到食物。这个过程就是间接通信的示例。

2 MAZACORNET

　　2.1 链路的稳定性

　　位置管理和连接管理对路由算法的性能起到非常关键的作用。通常，通过GPS获取车辆的位置和速度信息。连接管理用于维持路由的稳定性。

　　假定行驶道路上的两个车辆i、j，通过GPS获取的初始位置分别为(Xi0，Yi0)和(Xj0，Yj0)，初始速度分别为Vi0和Vj0。如果两个车辆在同一个通信范围内，则认为它们是邻居。用D表示两车间的距离，R表示通信范围。如果D>R，链路断裂。车辆i、j间的链路的使用寿命?驻t表示从链路建立时t0到当D=R时t1时间差，即?驻t=t1-t0。如果给定车辆的位置以及速度，链路的使用寿命?驻t可通过式(1)进行计算[20]。

　　车辆i、j间的链路的稳定性LS(Link Stability)可通过式(2)进行计算[21]：

　　其中，tmax为常数，表示路由表的有效期。在本文提出的算法中，链路稳定性将被用于决策路由。

　　2.2 面向VANET的ACO模型

　　信息素是ACO算法中最为关键的参数。在蚁群中，信息素被存储于地面上，从而吸引更多的蚂蚁沿着由信息素构成的路由移动。对于VANET，聚集在链路上的信息素的增加和减弱均表征了该链路的质量。为了获取高质量的链路，应寻找沿途沉积信息素大的路径，即优质链路。假定从源节点至目的节点链路Lij，沉积的信息素量可表示为式(3):

　　其中，LS表示链路的质量，可由式(2)进行计算，PR表示成功接受消息的概率。

　　成功接受消息的概率PR取决于在同一个通信范围内车辆间的距离，可通过Nakagami Fading Model[22]进行估计。该模型结合了VANET的高速、城市环境的特点，如式(4)所示。

　　其中，m表示衰减参数。例如，当m=3，表示快速衰减环境。

　　通过式(3)和(4)，沉积在链路Lij上的信息素可通过式(5)进行计算：

　　在ACO算法中，信息素的蒸发率通常设定为常数[23]。然而，在本文提出的算法中，针对每条不同的链路，的值不同。每条链路Lij的蒸发率可通过式(6)计算。

　　其中，k表示链路上至少沉积的信息素。为蒸发时限的倒数。

　　以上分析了面向VANET的ACO路由算法，接下来将分析基于蚁群优化的混合式移动感知路由算法。该算法具有可扩展性，并结合了反应式和先应式路由的优点。

　　2.3 基于蚁群的区域算法

　　在本文算法中，网络划分为区域。在区域内通过先应式算法传输数据包，区域与区域间采用反应式算法。通信跳数决定区域的尺寸大小。车辆可处于两个重叠区域，区域尺寸也可变动。依据车辆所处区域的位置，可将车辆分为区内车辆(Interior Vehicle)、区边车辆(Boundary Vehicle)和区外车辆(Exterior Vehicle)。如图1所示，源节点S，区域半径为2跳，车辆A、D、F处于边界上，称为区边车辆。车辆B、C、E是区内车辆，其他的车辆属区外车辆。

　　路由过程主要分为两个阶段：路由发现和路由维护。本文算法采用两类路由表：区内路由表(Intra Zone Routing)和区间路由表(Inter Zone Routing)。区内路由表实时更新区域内信息，而区间路由表按需追踪区间信息。在路由发现和路由维护阶段，使用五类蚁群，分别为区内转发蚁群(Internal Forward Ants)、区外转发蚁群(External Forward Ants)、后向蚁群(Backward Ants)、通告蚁群(Notification Ants)以及错误蚁群(Error Ants)。

　　蚂蚁用的数据表示格式如表1所示。

　　其中，Source表示源节点地址。Destination表示目的节点地址，对于区内转发的蚁群，该区域为空。Sequence number表示每个蚂蚁附身的序列号。Type用于标识不同类的蚂蚁，区内转发蚁群、区外转发蚁群、后向蚁群、通告蚁群以及错误蚁群分别用0、1、2、3、4表示。Hop表示节点与区域内所有其他节点间的跳数。该区域的值用于辨别节点是属于区内节点或非区内节点。Speed表示该节点的速度。Position表示该节点当前的位置。Path表示由一系列节点构成的源节点至目的节点的路径。

　　(1)区域内的路由发现

　　区内路由表用于区域内的路由发现阶段。该表包含了区域内所有车辆的信息。区内转发的蚁群周期地更新表中的车辆信息。表中的列表示区域内所有车辆，而行表示离其他车辆一跳距离的车辆。在路由表中，通过式(5)和式(6)增加和减弱信息素识别路由。当源节点需要向目的节点发送信息时，首先查询区内路由表的列，如果目的节点在它的区域，路由发现阶段就完成了，否则，就在区域间进行路由发现，如下文所示。

　　(2)区域间的路由发现阶段

　　当车辆在其区域内不能找到目的节点时，区域间路由表就开始发挥作用。通过区域间路由表寻找区边车辆，以构建新的路由。区外转发蚁群向区边节点靠拢，直到发现目的节点。一旦发现了目的节点，后向蚁群将向源节点遍历返回路线。然而，如果没有发现目的节点或路径的有效期已过期，则从当前区域使用区边节点重复进行路由发现，直到发现目的节点。

　　(3)路由维护

　　由于网络拓扑动态变化，路由可能断裂。如果是在区域内路由断裂，则按先应式算法原则周期地修复。若是在区域间路由断裂，则该路由的上游车辆存储数据包并选择备用路由。如果存在备用路由，则启动备用路由并更新。如果不存在，则通过错误蚁群向源节点发送路由失败消息。

3 系统仿真及分析

　　3.1 仿真场景建立

　　使用随机街道的都市场景进行仿真。初始仿真区域为500 m×500 m的区域，车辆数为25，交通灯数为10。随后，区域变为1 500 m×1 500 m，车辆数增加至100。构建NS2仿真参数如下：

　　(1)仿真时间设定为2 000 s，车辆于t=0 s时刻移动，于t=100 s开始传输；

　　(2)车辆数目被设定为25、50、75、100；

　　(3)数据包大小为512 B；

　　(4)采用PriQuenue队列；

　　(5)采用IEEE 802.11pw作为MAC协议；

　　(6)采用Nagakami传播模型；

　　(7)仿真的协议为：MAZCORNET、AODV、AMODV、GPSR。

　　3.2 仿真结果

　　本小节分析MAZCORNET的路由性能，并与其他路由协议比较。

　　3.2.1 车辆数目对端到端传输时延的影响

　　图2 显示了车辆数目对端到端传输时延的影响曲线。与AODV、AMODV和GPSR相比，MAZCORNET的端到端传输时延最低。这主要归功于MAZCORNET采用了区域架构、区内路由表和区间路由表。在区域内，通过先应式路由维护区内路由表，而在区间存有由蚁群存储的路径。通过这些预先准备的路径信息有助于提高数据包端到端的快速传输。使用式(6)调整链路上信息素的减弱率，导致断裂链路能及时被蚁群发现并丢弃。通过这些措施减轻了MAZACORNET端到端传输时延。

　　3.2.2 车辆数目对数据包传递率的影响

　　图3显示了MAZACORNET以及其他路由算法AODV、AMODV、GPSR的数据包传递率。从图3可知，当车辆数目较少时，MAZCORNET并不具有良好的数据包传递率。这主要是由于沉积在链路上的信息素很少，区边车辆不能传递数据包。在这种情况下，上游车辆缓存所有的数据包，并启动修复程序，寻找通往目的节点的其他路径。一旦发现了新的路径，将告知源节点。同时，缓存的数据包就依据这条新发现的路径传递到目的节点。从图3可知，当节点数目的增加，MAZACORNET数据包传递率优于其他路由算法。这主要是因为MAZACORNET具有多条路径选择，而AODV和GPSR的路径选择是单一的。

　　3.2.3 车辆数目对数据吞吐量的影响

　　吞吐量性能曲线如图4所示。当车辆数目增加，MAZACORNET的吞吐量性能最好。这是因为随着车辆数目的增加，区域内车辆数也随之增加，这会提高区域内车辆的连接率，增加了路径数，从而使数据传输更为流畅，降低了数据包的丢失率，提高了数据包的传输率，如图3所示。

　　3.2.4 车辆数目对路由开销的影响

　　图5显示了MAZACORNET以及其他路由算法AODV、AOMDV、GPSR的路由开销性能曲线。由于AODV和AOMDV是属于反应式路由，无区域概念。而MAZACORNET在区域内使用了先应式路由理念。通过周期地发送控制包维护区域内路由，这是MAZACORNET路由开销的主要来源。

　　本节，通过仿真结果分析了文中提出算法的性能。结果表明，MAZACORNET更适合城市场景即密集网络。当网络密集时，该算法能获取较高的数据传递率和较低的端到端传输时延，与其他路由算法相比，由于MAZACORNET能够提供多条路径，维持较高的通信连接率，因此表现出更好的性能。

4 结论

　　针对VANET的路由问题，提出MAZACORNET路由方案。该方案是基于先应式和反应式两种路由理念的混合多路径路由算法。在路由决策过程中，不广播消息，并提供多条可选路径。将网络区域划分为不同的区域。在区域内通过先应式路由方案建立路径，而在区域间采用反应式路由方案寻找路由，从而减少控制包广播的次数，降低了网络拥塞率。仿真结果表明，提出的MAZACORNET在密集车辆区域表现出了良好的性能，有效地提高了数据包传输率，降低了端到端传输时延。

参考文献

　　[1] Xiang Weidong，Shan Dan，Yuan Jiaqi，et al.A full func-tional wireless access for vehicular environments(WAVE) prototype upon the IEEE 802.11p standard for vehicular communications and networks. In Proceedings of IEEE Consumer Communications and Networking Conference[C], Las Vegas, NV, USA 2012：58-59.

　　[2] 王海凤，何之栋，黄文君.故障安全通信系统的研究与设计[J].电子技术应用，2014(1)：115-119.

　　[3] KAKARLA J，SATHYA S S，GOVINDA B，et al.A survey on routing protocols and its issues in VANET[J].InternationalJournal of Computer Applications，2011，28(4)：38-44.

　　[4] JOHNSON D B，MALTZ D A.Dynamic source routing in ad hoc wireless networks[J].Kluwer Academic Publishers，Boston，1996，5(353)：153-181.

　　[5] Pei Guangyu，GERLA Mario，Tsu-Wei Chen.Fisheye state routing：a routing scheme for ad hoc wireless networks[C].In Proceedings of IEEE International Conference on Comm-unications，New Orleans，USA，2000：70-74.

　　[6] KARP B，KUNG H T.GPSR：Greedy Perimeter Stateless Routing for wireless networks[C].In Proceedings of the 6th Annual ACM International Conference on Mobile Computingand Networking, Boston, Massachusetts, United States, Aug.2000：243-254.

　　[7] LIN C R，GERLA M.Adaptive clustering for mobile wirelessnetworks[J].IEEE Journal on Selected Areas in Communi-cations, 1997,15(7)：1265-1275.

　　[8] DURRESI M，DURRESI A，BAROLLI L.Emergency broad-cast protocol for inter-vehicle communications[C].In Pro-ceedings of 11th International Conference on Parallel and Distributed Systems,  2011，2(3)：402-406.

　　[9] BACHIR A，BENSLIMANE A.A multicast protocol in ad hoc networks inter-vehicle geocast[C].In Proceedings of 57th IEEE Semiannual Conference on Vehicular Technology, April 2013,4(4)：2456-2460.

　　[10] MARINA M K，DAS S R.On-demand multipath distance vector routing in ad hoc networks[C].In Proceedings of 9thIEEE International Conference on Network Protocols, pages14-23, California, USA, Nov. 2001.

　　[11] Chen Yufeng，Xiang Zhengtao，Wei Jian，et al.An improvedAOMDV routing protocol for V2V communication[C]. In Proceedings of the IEEE Intelligent Vehicles Symposium, 2011：1115-1120.

　　[12] Ye Zhenqiang，KRISHNAMURTHY S V，TRIPATHI S K.A framework for reliable routing in mobile ad hoc net-works[C]. In Proceedings of the 22nd IEEE International Conference on Computer Communications), pages 270-280, San Francisco, USA, Mar. 2003：270-280.

　　[13] SCHOONDERWOERD Ruud，BRUTEN J L，HOLLAND O E，et al.Ant-based load balancing in telecommunications  networks[J].Adaptive Behavior, 1996,5(2):169-207.

　　[14] PRASAD Sunita，SINGH Y P，RAI C S.Swarm based routing for MANETs[J]. International Journal of Recent Trends in Engineering,2011,1(1)：153-158.

　　[15] CLAUSEN T H，JACQUET P.Optimized link state routing  protocol(OLSR).Technical report, INRIA, Oct.2003.

　　[16] PERKINS C，ROYER E M.Ad-hoc on-demand distance vector routing[C].In Proceedings of 2nd IEEE Conference on Mobile Computing Systems and Applications, February 1999:90-100.

　　[17] LUIS Sergio，CORREIA O B，CELESTINO Joaquim，et al.Mobility-aware ant colony optimization routing for vehicularad hoc networks[C]. In Proceedings of IEEE Conference 2011:1125-1130.

　　[18] BONABEAU E，DORIGO M，THERAULAZ Guy.Swarm

　　Intelligence:From Natural to Artificial Systems[J].Oxford University Press, USA, Sep.1999:123-128.