基于粒子群算法的车载自组网GPSR协议优化

龚 凯，陈 志，岳文静

(1.南京邮电大学 计算机学院，江苏 南京 210023； 2.南京邮电大学 通信与信息工程学院，江苏 南京 210003)

0 引 言

随着智能城市和物联网应用技术的快速发展，车载自组网(VANET)等技术变得越来越重要[1]。VANET提供数据收集和传送的功能，如何最大限度地提高其通信质量，尽可能地减少数据收发时延，同时降低其能量消耗，一直是广泛关注的研究热点。

基于地理位置的VANET路由协议相比其他路由协议具有较高的数据包传送比率和低时延，更适应动态的车辆通信环境[2]，但下一跳节点选择策略仍存在不足。有些策略为了降低时延却忽略了节点的能量利用率，导致局部节点过早死亡，有些策略考虑到了节约能量却严重牺牲了数据传输时延。文献[3]提出利用粒子群算法生成一个能量利用率高的分簇路由协议，该协议通过平衡能量消耗，以提高节点的生命周期。文献[4]提出基于车辆密度、行驶方向和速度的路由优化策略，该策略在包传输率和路由开销上均优于已存在的GPSR协议。文献[5]利用缓存转发机制在贪婪转发模式中引入缓冲区域消除不可靠节点，解决节点在高密度环境下易受干扰的问题。这些已有的优化方法在解决路径问题上单调考虑一面判决因素，忽略网络内包含的多面可利用信息，在解决贪婪转发模式所存在的问题上还有继续优化的可能。

粒子群优化算法是一种群智能优化技术[6]，在每次迭代过程中，利用粒子通过当前所找的个体极值和全局极值来不断更新自己的位置和速度，慢慢地向目标位置靠近，最终找到最优解[7]。为尽量考虑到节点下一跳选择时的多方面因素，文中优化了GPSR协议，利用粒子群算法来均衡处理，通过迭代寻优找出最优下一跳节点，以有效提高VANET路由质量。

1 车载自组网模型

1.1 网络模型

为了将问题模型切合实际，对所研究的车载自组网(VANET)作如下假设：

(1)VANET所有节点随机部署在M×M矩形区域内，每个节点在该区域内随机运动。

(2)VANET所有节点的初始能量相同、能量有限、地位平等，是一个同构型网络。

(3)VANET每个节点都有一个唯一的标识ID，且都能感知自己的位置和剩余能量，相邻节点之间的距离采用欧氏距离计算公式:

(1)

其中，xi,yi,xj,yj分别为GPSR节点i与j的横坐标与纵坐标；d(i,j)为两节点之间的欧氏距离。

(4)VANET每个节点的数据传输率相同，且所有节点的传输半径都为R。

1.2 能耗模型

在VANET传输数据时，除了数据包的发送与接收需要消耗能量外，其他能量消耗都忽略不计，并且发射器发送数据包的能耗随着传输距离的增大而呈指数级增长。因此，传输kbit数据所消耗的总能量可表示为[8]：

Econ(k,d)=ETx(k,d)+ERx(k)

(2)

ETx(k,d)=ETx-elec(k)+ETx-amp(k,d)=

(3)

ERx(k)=ERx-elec(k)=k×Eelec

(4)

1.3 粒子与GPSR节点位置映射模型

由于GPSR协议中节点的位置分布是随机并且离散的，而粒子群算法是对离散空间求解最优解。根据粒子群算法的位置和速度公式进行更新后，粒子的位置与监测区域内当前节点的所有邻居节点位置不一定一一映射。

定义粒子与当前节点的所有邻居节点之间的位置映射函数为[9]：

f(Xi)={Xn|min[d(Xi,Xn)],1≤i≤M,

0≤n≤Nneighbor}

(5)

其中，Xi为粒子的位置；Xn为GPSR节点的位置；M为粒子的数量；Nneighbor为当前节点的邻居节点总数。由于VANET节点部署在平面区域，则解空间的维数为2，d(Xi,Xn)为粒子Xi与GPSR节点Xn之间的欧氏距离。

根据上面的位置映射函数对每个粒子的位置进行调整，使得调整后的粒子对应到具体的VANET节点，满足Xix∈{X1x,X2x,…,XNneighborx}，Xiy∈{X1y,X2y,…,XNneighbory}。其中，XNneighborx为当前节点的第N个邻居节点位置坐标的x分量，XNneighbory为当前节点的第N个邻居节点位置坐标的y分量。假设f(Xi)=Xk，即d(Xi,Xk)最小，表示第i个粒子与当前节点的第k个邻居节点之间的距离最近，计算后的位置为：Xix≈Xkx,Xiy≈Xky，即粒子i映射到当前节点的第k个邻居节点。

2 GPSR协议优化

传统GPSR协议使用地理位置信息和贪婪算法实现VANET路由。在GPSR协议中，当源节点向目的节点转发数据分组时，首先在自己的所有邻居节点中选择一个距离目的节点最近的节点作为数据分组的下一跳，然后将数据分组传送给它；上述过程一直重复，直到数据分组到达目的节点或者某个最佳主机[10]。在发生最佳主机问题时，数据分组采用边界转发策略来实现路由。目前的贪婪选择下一跳节点策略所选择的节点并不一定满足数据传输的QoS要求，同时能量的消耗也不平衡，文中在贪婪转发的基础上利用粒子群算法对贪婪转发下一跳节点选择策略进行优化，通过适应值函数来评估粒子的质量，为下一跳节点的最优选择提供可靠的依据，建立GPSR优化协议P-GPSR。

2.1 适应值函数

适应值函数用来评估粒子的优劣，通常取决于具体优化的问题，是系统算法与实际优化问题的接口[11]。为了在提高GPSR协议的能量利用率的同时，满足数据传输的QoS要求[12]，P-GPSR所采用的适应值函数主要考虑以下四个因素：

(1)下一跳节点的能耗与剩余能量。当前节点在选择下一跳节点时，需考虑下一跳节点的能耗和剩余能量，优先选择下一跳节点能耗占剩余能量比例小的节点，防止下一跳节点因能量不足导致路由中断，保证数据的有效路由传输。

(2)当前节点距下一跳节点的距离与其距所有邻居节点的平均距离。由于节点的能耗与包传输距离有关，因此需考虑当前节点距下一跳节点与其距所有邻居节点的平均距离的比值，比值越小，节点传输数据包的能耗越少，节点剩余能量也就越多。

(3)当前节点距下一跳节点的距离与当前节点距目的节点的距离。若下一跳节点处于当前节点的传输边界，其因边界信号强度弱和网络拓扑变化频繁而造成其能量消耗大、转发忙碌和丢包问题。因此，优先选择当前节点距下一跳节点距离与当前节点距目的节点距离的比值较小的节点作为下一跳节点。

(4)下一跳节点和目的节点分别与当前节点所构成的偏转角。为确保数据包的正向传输，使下一跳节点与当前节点的连线和目的节点与当前节点的连线所构成的偏转角尽可能最小，以达到减少路由跳数的目的。

综上所述，P-GPSR的适应值函数定义为：

F=a·f1+b·f2+c·f3+d·f4

(6)

f1=Econ(Ni)/Eresidual(Ni)

(7)

(8)

f3=d(Ni,last,Ni)/d(Ni,last,D)

(9)

f4=θ(Ni,last,Ni,D)/2Π

(10)

根据以上适应值函数的定义，每轮迭代的全局最优解取全部个体最优解中的最小值，较小的f1、f2、f3、f4均能保证最优下一跳节点的选取。粒子的适应值越小，说明相应节点的能耗越少，剩余能量越多，数据包传输的距离越小，下一跳节点受边界干扰程度越小，而且保证了数据包的正向传输。较小的适应值改善了节点的负载均衡程度，提高了整个VANET网络的使用寿命和数据传输效率。因此粒子群算法的优化目标是利用适应值函数来评估每个粒子的质量，搜索适应值最小的粒子作为本轮最优下一跳节点。

2.2 改进的下一跳节点选择过程

P-GPSR采用以下步骤对GPSR协议下一跳节点选择过程进行改进。

Step1：判断当前节点的邻居节点集中是否有距目的节点的距离比当前节点距目的节点距离小的节点，如果有则转到Step2，否则进入周边转发模式。

Step2：初始化粒子群。首先，从当前节点的邻居节点集中随机选择M个节点作为初始粒子群X{X1,X2,…,XM}。然后，初始化每个粒子的速度Vi和位置Xi。将每个粒子的初始位置作为个体最优解(pBest)，根据适应值函数计算每个粒子的适应值，选择适应值最小的粒子作为整个粒子群的全局最优解(gBest)。

Step3：速度和位置的更新。由于优化空间为二维，所以将每个粒子的速度和位置坐标分解成Vix，Viy，Xix，Xiy的形式。然后根据以下的粒子群速度和位置更新公式对每个粒子的速度和位置进行更新。同时，将更新后的粒子根据粒子与节点间的位置映射公式映射到具体的GPSR节点上。

Xix(t+1)=Xix(t)+Vix(t+1)

(11)

Xiy(t+1)=Xiy(t)+Viy(t+1)

(12)

Vix(t+1)=Vix(t)+c1·rand·(pBest-Xix(t))+c2·rand·(gBest-Xix(t))

(13)

Viy(t+1)=Viy(t)+c1·rand·(pBest-Xiy(t))+c2·rand·(gBest-Xiy(t))

(14)

其中，c1、c2为学习因子，通常取值为c1=c2=2；rand为[0,1]之间的随机数；t为迭代次数。

Step4：个体最优解(pBest)和全局最优解(gBest)的更新。比较每个粒子的适应值f(Xi)与上一次迭代的个体最优解f(pBesti)的大小，若f(Xi)

Step5：如果没有找到gBest或者没有达到设定的最大迭代次数，则转到Step3；否则，算法终止，将其中具有最小适应值的粒子作为最优下一跳节点。

3 仿真实验与结果分析

下面采用网络仿真模拟器NS2[13]进行仿真实验，模拟GPSR协议的通信过程，其主要的仿真场景参数配置如下：实验是运行在1 200 m×1 200 m的区域内，VANET节点数目50个，节点的通信范围为250 m，节点的侦听范围为550 m，节点的运动速度为10～100 m/s，信道带宽为5 Mbps，建立3条CBR数据流，每个数据包的大小为512 Byte，仿真时间为250 s。节点的运动模型是利用NS2自带的setdest程序生成，在不同的运动速度下，分别运行GPSR协议、O-GPSR协议和P-GPSR协议，其中GPSR协议是原始协议，O-GPSR协议是基于机会转发的优化协议，P-GPSR协议是提出的基于粒子群算法的优化协议。通过端到端时延、丢包率、能耗来分析比较各个协议的优劣。

(1)端到端时延。

数据包的端到端时延表示数据包从源节点开始，到目的节点接收数据包时的累积时间，其包含了数据包在传输过程中的全部时延，如发送缓冲器的发送时延、接口队列发生阻塞时的排队时延、数据包在传输过程中的传输时延、MAC层重传时延[14]等。

图1显示了在不同时间段内，原GPSR协议与两种改进的GPSR协议的端到端时延的数据对比。

从图1可以看出，在0～150 s之间，总体上P-GPSR的端到端时延要比另两种GPSR协议小，但是150 s之后三种协议的时延都为零，是因为实验设置在0～150 s之内传输cbr数据流，150 s后没有进行数据流传输。在数据包传输阶段内，由于节点位置变化，导致网络拓扑结构跟着变化，形成不同程度的时延。O-GPSR协议虽然在端到端时延相对于原协议较小，但与P-GPSR协议相比，仍有不足，这是由于其在选择下一跳节点时虽然考虑到边界转发易受干扰导致数据包拥塞，但在贪婪转发选取下一跳节点时，缺乏考虑节点因剩余能量不足导致传输质量不高的问题。而P-GPSR协议利用粒子群算法不但考虑了边界转发干扰，而且还能根据节点剩余能量多少来选择下一跳，减少了数据包的传输时间和排队时间，进而减少了数据包的端到端时延。

(2)网络能耗。

网络能耗的多少直接影响着VANET整个网络的运行周期和节点的使用寿命[15]。P-GPSR协议在选择下一跳节点时依据下一跳节点与目的节点分别和当前节点连线所构成的偏转角和下一跳的距离与一跳平均距离的比值等影响因子，保证数据包的正向传输，减短路径长度，减少能耗。

图2为网络发送相同数量cbr数据流(500个)时，P-GPSR协议与另外两种GPSR协议在节点速度不同时的能量消耗比较。

图2 网络能量消耗

由图2可知，三种协议的能耗随着节点速度的增加都在上升，是因为网络节点的速度越大，节点自身运动消耗的能量越多，同时也加快了网络拓扑结构的变化。P-GPSR协议的上升幅度较另两种协议缓慢，是因为P-GPSR协议利用粒子群算法对节点的各方面因素迭代判断，下一跳节点有较低概率因网络拓扑变化加快而变化，减少额外的路由消耗。还可以看出，在节点速度相同的情况下，P-GPSR算法消耗更少的能量。所以，相比于另外两种GPSR协议，P-GPSR协议能量消耗少，能耗上升幅度缓，保证了整个VANET网络的使用寿命。

(3)网络丢包率。

网络丢包率是目的节点没有收到的数据包个数与源节点发出的数据包个数之比，大小反映了VANET网络传输的可靠性，比值越小表明协议性能越好。

图3为在不同节点运动速度下，三种协议的丢包率的对比。

图3 丢包率

从图中可以看出，三种协议的丢包率随着速度的增加而增加，是由于VANET节点速度的变快导致网络拓扑结构的变化频率增加，路由断裂的概率增大，导致数据包丢失的概率变大。另外还可以看出，在相同节点速度的情况下，P-GPSR协议的丢包率比另外两种GPSR协议要小，是因为P-GPSR协议在贪婪转发下一跳节点选择时，没有一味地选择离目的节点最近的节点，而是综合考虑了节点剩余能量大小、边界节点易受干扰和数据包的正向传输等问题，防止因节点剩余能量不足而导致路由断裂出现路由空洞，以及数据包因一直偏离目的节点方向使传输时延增加，导致数据包没有在规定时间内送达而被丢弃。综上，改进的P-GPSR协议在丢包率上优于另外两种协议。

4 结束语

GPSR协议在贪婪转发选择下一跳节点时，选择距离目的节点最近的节点作为下一跳节点，忽略了VANET有时出现的边界节点易受干扰、损耗大、节点剩余能量不足、网络整体能耗高和数据包偏向传输等问题。对此，提出了基于粒子群算法的VANET协议P-GPSR。该协议利用粒子群算法来解决上述问题，选择具有最小的全局适应度值的节点作为下一跳节点。仿真实验与结果分析说明，相比于GPSR协议及其他优化协议，该协议能够有效降低端到端时延和丢包率，对VANET路由空洞问题也产生了一定作用，同时降低了VANET网络数据包传输的能量消耗，延长了VANET使用寿命。