车载自组网中一种自适应粒子群算法的研究

周杰英，彭石，刘映淋，许杨鹏

（中山大学电子与信息工程学院，广州 510006）

车载自组网中一种自适应粒子群算法的研究

周杰英，彭石，刘映淋，许杨鹏

（中山大学电子与信息工程学院，广州 510006）

车载自组网又称VANET，具有车辆节点高速移动、拓扑变化快、通信链路不稳定等特点。传统路由协议不能很好适应动态多变的车载环境，所提出的自适应路由协议方法在相邻网络节点间建立马尔科夫链路信息表RLM，然后利用改进的粒子群路由算法选择数据包传递经过的下一跳节点；实验仿真表明，采用RLM监控机制有效解决VANET网络中传输链路不稳定的问题，减少数据包丢包的发生概率，而使用粒子群路由算法有效降低数据包传输时出错的概率，降低时延，从而提高分组投递率。

VANET；粒子群算法；时延；连通性

0 引言

车载自组织网络VANET（Vehicular Ad Hoc Network）是一种由若干个移动的具有接收和发送功能的无线节点构成的自适应网络，其便捷、灵活、自组织的特性弥补了固定网络的不足，因此VANET通信网络在军事和民用领域具有广泛的用途。由于VANET之中的节点需要在没有任何预设的基础设施的情况下完成通信，不仅需要充当信源和信宿节点，还需要充当路由器对其他节点发送的分组进行转发，因此需要有合适的路由协议实现这些功能[1-2]。

现有的路由协议如AODV[3]，GPSR[4]，DSR[5]通过特定的策略动态选择一条从源节点到目的节点的路径，具有简单、可靠性高、易于实现等特点。但由于VANET之中的节点随着车辆高速移动，网络拓扑结构变化频繁，通信链路割裂严重，此外复杂多变的城市环境等特点使传统的Ad Hoc路由协议直接运用在VANET上的效果很不理想[6]，所以，目前提出了很多改进的路由算法。文献[7]针对车载自组网之中现有的GPSR协议存在网络拥塞的问题，提出了一个改进的GPSR协议，利用节点的缓冲区来控制网络拥塞；文献[8]针对AODV路由算法存在控制开销大、路由发现和修复时间长等不足，为此，对AODV算法进行局部优化，提出一种改进的路由算法，利用节点位置、运动速度等信息预测链路失效时间；此外，针对路由网络之中的难题，提出了许多基于仿生学和群体智能的路由协议。例如，文献[9]提出了一种利用不同蚂蚁群搜索最短路径而启发得出的蚁群优化算法。文献[10]针对在高移动性的的Ad Hoc网络之中，存在高时延，能量消耗，丢包的问题，提出一个结合粒子群的路由优化算法。文献[11]在定义了包含邻居节点信息的粒子适应度函数的基础上，提出了一种基于离散粒子群（DPSO）的单跳路由分簇协议（DPSOCA）。

本文根据城市交通下VANET的路由特点，提出的APSO路由协议方法通过马尔科夫链模型（Route Link Model，RLM）在相邻网络节点间建立网络状态概率转移矩阵，然后利用改进的粒子群优化算法选择数据包传递经过的最佳节点；理论和实验表明采用该监控机制不仅有效解决了VANET网络中通信链路不稳定的问题，减少了数据包冲突的发生概率，还为数据流量模型预测提供了一个很好的途径，而使用粒子群路由算法有效降低了数据包传输时出错的概率，降低了时延，从而提高了分组投递率。

1 相关数学模型研究

1.1 VANET的QoS模型

为方便数学分析，本文将VANET网络表示为一个无向带权图。假设，G=（V，E）代表一个VANET网络，其中V代表网络中节点集合，E代表联系两个节点路径的集合。对于每条路径e∈E，传输时延表示为delay（e），对于每一个节点n∈V，处理时延表示为delay（n）；给定一个i∈V和一个j∈V，可以假设path（i，j）代表从i到j的路径，则路径上QoS参数可以通过式（1）～式（2）计算。路径时延delay（path（i，j））等于每个节点的处理时延和每条链路的传播时延总和。参数d（i，j）等于路径中节点i和j的距离，数据包从源节点传到目的节点需要经过多跳，通常希望找到一个距离最短的路径，时延少，路径节点更加稳定。

1.2 VANET路由链路模型RLM

为了在网络之中维护链路信息表，需要当前节点和网络的若干外围节点之间保持链路联系。在本文，采用贝叶斯网络的方法来确定链路表的大小。首先，将VANET网络的拓扑结构表示为一个有向无环图（DAG），有向无环图中的节点用随机变量{x1，x2，…，xn}表示；为了选择符合要求的路由路径，需要满足按照特定顺序排列的节点子集{，，…，x}（在本文中n≤5），并要求当n〈m，距离d（x，x）〈d（x，x），这样一来，REQ包每向外传输一次，下一跳节点就离初始节点越远，初始节点就能够掌握更多的外围节点信息。

令G=（I，V）表示实际VANET网络，其中I代表图形中所有的节点的集合，而V代表有数据包传递的边集合；设E、H∈I为其有向无环图中的某两个随机节点，将链路中节点之间的发包概率看做一个状态空间，将状态空间之中任意相邻的节点E发送数据包到达节点H的联合概率看作是一个贝叶斯过程：

其中NHE表示E向H节点的发包数量，NH表示经过节点H的发包数量，p（H|E）表示节点E向节点H发送数据包占经过H的数据包总数的概率；为了连接一定范围之内的节点，因此需要计算若干相连节点的传输概率。本文将此表示为一个马尔科夫过程，利用此模型，就会产生一个路由序列{xi1，xi2，…，xik}。

其中，xik表示当前节点连接的最外层节点xi1表示当前节点，p（xi1，xi2，…，xik）表示节点xi1至xik组成一条链路的概率，其由式（4）推导出来。当某个链路的概率p（xi1，xi2，…，xik）大于一定的阈值，就会认为该链路是稳定可靠的，否则认为该链路容易发生断裂。通过以上方式，VANET网络中的各个节点动态维护自身的多条链路信息，从而实现对外围节点的监控。

1.3 路径选择模型

本文中，VANET网络采用粒子群算法（PSO）来计算各个节点的相对适应值，并且根据计算结果选择最佳的下一跳节点。其中各个邻居节点的相对适应值的计算方式如下：

其中，k表示当前节点的第k个邻居节点，ΔFk表示第k个邻居节点和当前节点的相对适应值；惯性权重μ0为常数，μ1和μ2为学习系数；μk定义为vk=1/Nk，Nk是邻居节点k维护的有效链路数目；源节点F初始适应值为0，pbestk代表局部最优值，gbestk全局最优值，定义如下：

其中i代表当前节点，Dt（i，k）代表邻居节点k和当前节点之间的传输时延，Lt（i，k）代表节点k和目的节点之间的空间距离，从式（5）可以看出，vk，pbestk，gbestk越小，ΔFk就越小，代表该节点作为下一跳节点的可能性越大。反之，ΔFk越大，意味着该节点属于孤立节点，高时延，远距离。

2 APSO协议实现

在本节给出了自适应粒子群算法APSO的具体设计方案，在该路由协议之中，运动的节点通过维护一条条链路信息表来获知周围节点的位置速度方向等信息。当源节点需要传输数据的时候，如果链路信息表中不存在到达目的节点的路由，源节点就会利用APSO算法来查找到达目的节点的最优路径。所述APSO协议方法包含如下步骤：

（1）监控步骤

A1：网络中的节点周期性发送包括当前节点信息的路由请求包REQ，邻居节点收到请求包后利用上文提到的路由链路模型RLM计算当前节点和上一跳节点之间的发包概率，建立网络状态概率转移矩阵。该路由请求包的格式如下所示：

其中，Nk为经过的节点数组，Dk为经过的节点位置数组，Vk为经过的节点速度数组，Fk为经过的节点方向数组，Tk为经过的节点时间戳数组，Pk为经过的节点跳数数组，Hk是经过的节点的概率数组；REQ请求包每经过一个节点，都会更新本次传输的相关参数到对应数组之中。当最后一次计算的Hk小于某个阈值的时候，当前节点就会将数据包反向发送到起始节点，起始节点就会更新自己的RLM链路信息表。本文中REQ包跳数值设置为不大于5，所以默认源节点发送和接收REQ包的传输是在瞬时完成的，传输时延和处理时延可以忽略不计。

A2：当中间节点收到REQ数据包时，中间节点提取数据包的信息，计算和上一跳节点的联系概率P，判断当前的马尔科夫链路概率是否小于预设的阈值，若是则停止转发数据包，并反向发送REQ数据包到达源节点；否则，中间节点继续检查当前数据包是否已经到达本节点，若是则丢弃该数据包，否则中间节点更新自身信息到REQ数据包中，接着选择符合要求的邻居节点，继续向外转发REQ包；

A3：若源节点收到自外层网络发来的REQ数据包，源节点提取数据包中的信息，将链路信息保存在自身的路由信息表中，并检查路由表之中是否包含相同的链路信息，若包含则更新该链路信息；否则将该马尔科夫链保存到路由表之中；若某条链路信息过了预定时间没有更新，则将该链路从路由表中删除。

本文提出的APSO协议通过路由节点网络和马尔科夫链路在相邻网络节点间建立网络状态概率转移矩阵，该监控机制不仅有效解决了VANET网络中通信链路不稳定的问题，减少了数据包冲突的发生概率，还为数据流量模型预测提供了一个很好的途径。

（2）数据包转发步骤

B1：需要发送数据的源节点，通过GPS等辅助定位设备得到目的节点的物理位置，然后封装自己的物理位置，节点地址，唯一性标志号以及目的节点等信息到待发送的数据包之中，并且从自身的链路信息表之中，采用自适应粒子群路由算法计算获得邻居节点的适应值，选择适应值最小的节点作为最佳的下一跳节点，并将数据包发送到该节点。

B2：中间节点收到数据包之后，提取数据包内的路由信息。判断自身是否是目的节点，若是就停止发送数据包，并且发送应答包沿着链路路由节点返回到源节点；否则，更新自身节点信息到数据包之内，然后按照上面的方法发送数据包到下一跳节点，直到到达目的节点。

APSO进行分组转发时，在链路信息表的基础之上，利用自适应粒子群算法来选择下一跳的路由节点，由于综合考虑全局和局部的特性，使得所选择的下一跳更加准确，大大提高了分组投递率，降低了链路之中的时延。

（3）路由修复步骤

C1.当监控步骤中的寻址过程发生丢包时，发生丢包的源节点发送新的REQ请求包到下一跳节点，通过计算新的链路状态概率得到可用的马尔科夫链路；当前节点将新的链路信息封装到路由请求REQ包发送到相邻的节点，相邻节点收到路由请求包并重新评估网络状态，然后重发寻址数据包。

C2.当数据传输过程发生丢包时，若中间节点收不到成功传输的应答包，其会更新自身的链路信息表，然后从自身的缓存之中提取数据包信息，按照计算得到的结果选择最佳的下一跳节点，直到数据包到达目的节点。

3 APSO协议仿真

为验证文中提出的APSO算法的有效性和性能，本节在NS2仿真环境下，通过改变VANET之中的节点数目来观察APSO，GPSR，AODV协议的延时性能和分组投递率。节点数目用来模拟VANET网络的拓扑结构，节点数目越大，表示贝叶斯网络状态空间的链路数目越多，链路断裂的可能性越小。

仿真环境：Ad Hoc节点随机放置在1500m×1500m的矩形区域中，节点可以根据IDMIM模型随机进行移动，最大移动速度为40m/s。节点的最大传输范围为250m，MAC层使用IEEE802.11DCF。数据包大小为512 bytes，数据源为CBR。每次仿真运行900s。算法中的一些参数设置如下：μ0=0.3，μ1=0.3，μ2=0.4，REQ代理发送周期0.5s，路径更新定时器为1s。仿真结果如下图所示。

图1 分组投递率随节点数目变化性能仿真结果

图1，2，是本文的仿真结果图。从图1可以看出，当节点数较小的时候，由于车辆的运动，造成路由链路经常发生断裂，因此三者的分组投递率较低，丢包率较高；但随着节点数目变大，相对于AODV和GPSR，本文提出的APSO协议的分组投递率明显优于前者，因为本文的马尔科夫链路监控机制和APSO算法在VANET大大降低了链路断裂的概率和丢包的概率。从图2可以看出，随着节点数目增多，端到端时延逐步降低；当节点数较小的时候，三个协议的端到端时延都较高，这是因为网络中各个节点的邻居节点数目很少，导致数据包无法及时传输到下一跳节点，造成时延增加；但是APSO的性能依然优于另外两个，因为APSO综合考虑了全局和局部的特性，使数据包错误发送的概率降低，大大增加了路由的有效性。

4 结语

本文在深入研究已有VANET网络路由算法的基础上，建立VANET网络的链路状态监控机制，通过马尔科夫链路在相邻的网络节点之间建立网络状态概率转移矩阵，该监控机制增强了链路的稳定性和有效性；在进行分组转发过程中，采用APSO算法进行下一跳的节点选择，综合考虑了全局和局部的特性，使选择得下一跳更加准确，大大提高了分组投递率，降低了链路之中的时延。

图2 端到端时延随节点数目变化性能仿真结果

[1]Zeadally S，Hunt R，Chen Y S，et al.Vehicular Ad Hoc Networks（VANETS）:Status，Results，and Challenges[J].Telecommunication Systems，2012，50（4）:217-241.

[2]Martin-Campillo A，Crowcroft J，Yoneki E，et al.Evaluating Opportunistic Networks in Disaster Scenarios[J].Journal of Network& Computer Applications，2012，36（2）:870-880.

[3]Verma V K，Singh S，Pathak N P.Analysis of Scalability for AODV Routing Protocol in Wireless Sensor Networks[J].Optik-International Journal for Light and Electron Optics，2014，125（2）:748-750.

[4]Karp B.Greedy Perimeter Stateless Routing for Wireless Networks[J]，2000.

[5]Johnson D B，Maltz D A.Dynamic Source Routing in Ad Hoc Wireless Networks[C].Mobile Computing.1996:153-181.

[6]Viriyasitavat W，Bai F，Tonguz O K.Dynamics of Network Connectivity in Urban Vehicular Networks[J].IEEE Journal on Selected Areas in Communications，2011，29（3）:515-533.

[7]Hu T，Liwang M，Huang L，et al.An Enhanced GPSR Routing Protocol Based on the Buffer Length of Nodes for the Congestion Problem in VANETs[C].International Conference on Computer Science&Education,2015:416-419.

[8]夏梓峻，刘春凤，赵增华，等.基于链路预测的VANET路由算法[J].计算机工程，2012，38（4）:110-111.

[9]Nishitha T，Reddy P C.Performance Evaluation of AntHocNet Routing Algorithm in Ad Hoc Networks[C].International Conference on Computing Sciences，2012:207-211.

[10]K.D.Kalambe，A.R.Deshmukh，S.S.Dorle.Particle Swarm Optimization Based Routing Protocol for Vehicular Ad Hoc Network International Journal of Engineering Research and General Science Volume 3，Issue 1，January-February，2015 ISSN 2091-2730

[11]邹学玉，曹阳，刘徐迅，等.基于离散粒子群的WSN分簇路由算法[J].武汉大学学报理学版，2008，54（1）:99-103.

周杰英，女，博士，副教授，研究方向为无线自组织网络、Mesh网络

彭石（1988-），男，湖北人，研究生，研究方向是网络协议

刘映淋（1991-），男，广东人，研究生，研究方向为Ad Hoc

许杨鹏（1993-），男，湖南人，研究生，研究方向为软件、网络

Research on an Adaptive Particle Swarm Optimization Algorithm in VANET

ZHOU Jie-ying，PENG Shi，LIU Ying-lin，XU Yang-peng

（School of Electronics and Information Technology，SYSU，Guangzhou 510006）

Characteristics such as high speed,changing network topology and unstable communication link exist in the design of VANET routing protocols.Traditional protocols cannot adapt to the dynamic environment of VANET.Proposes a routing protocol based on Markoff route link model between adjacent nodes and uses a novel particle swarm optimization algorithm to select the optimum node that the packet passes through.Simulation results show that the monitoring mechanism solves the problem of unstable communication link in VANET,reduces the probability of packet loss.And the improved particle swarm optimization algorithm can effectively reduce the probability of transmission error.The delay is reduced and packet delivery ratio of the network is improved.

VANET;APSO;Delay;Connectivity

1007-1423（2017）11-0026-05

10.3969/j.issn.1007-1423.2017.11.005

2017-01-20

2017-03-12

广东省省级科技计划项目（No.2015A010103007）