基于遗传特征的车载网络分簇路由算法研究

路 婷，王 伟

(西安工程大学 计算机科学学院，陕西 西安 710048)

0 引 言

车载自组织网络(vehicular ad hoc network，VANET)又称车载网络，是移动自组织网络(mobile ad hoc network，MANET)在汽车行业的实际应用，也是智能交通系统中尤为重要的组成部分。车载网络以安装有无线通信设备的高移动性车辆和路边单元等作为网络节点，构建车辆与车辆(vehicle to vehicle，V2V)、车辆与网络(vehicle to network，V2N)、车辆与基础设施(vehicle to infrastructure，V2I)、车辆与行人(vehicle to pedestrian，V2P)等V2X网络互联，实现车载网络信息共享。典型的车载网络应用包括娱乐服务和安全预警。娱乐服务类应用主要包括音乐或视频文件请求、语音交互等功能，具有一定的时延容忍特性；而安全性应用是智能交通的重要应用，是网络性能要求较高的一类应用，具体应用场景包括车辆变道或变速预警、车辆碰撞预警等，要求保证信息实时、可靠、安全传输。

传统的车载网络路由算法主要分为基于拓扑的路由算法[1-2]和基于位置的路由算法[3-7]，但由于车载网络拓扑不断变化，且位置获取方式易受环境影响，所以这两种方法都存在弊端。因此，有学者提出将群智算法引入车载路由算法的研究思路，从而对传统算法进行改进，提高网络链路稳定性和数据转发效率。但现有的路由算法大多缺乏对车辆节点密度、网络无线链路变化及节点剩余能量等因素的考虑，在复杂环境下数据包转发不具稳健性，难以适用于车辆安全预警应用。

因此，基于车载网络安全预警应用对于网络无线链路稳定性、网络实时性和数据包高效转发等需求，文中提出了一种自适应的基于遗传特征的分簇路由算法。

1 相关工作

常见的车载网络路由算法主要包括传统车载网络路由算法和基于群智算法的车载网络路由算法。

1.1 传统车载网络路由算法

传统的车载路由算法是在移动自组织网络路由算法的基础上发展而来的。移动自组织网络中，常用的经典路由协议包括主动式路由协议[8]和反应式路由协议[9-11]，但其路由开销较大，无法适用于节点数量很大的车载网络环境。基于此，很多学者提出适用于车载网络的改进算法。如表1所示，车载网络路由算法可分为基于拓扑(topology based)的路由算法和基于位置(position based)的路由算法。

表1 传统车载网络路由算法对比

针对以上路由算法的缺陷，Soni. V等人[2]通过建立模糊规则库减少网络拓扑变化对路由发现的影响，一定程度上增加了网络链路的稳定性，但规则库数据存储也将带来更多的网络带宽消耗，增加了传输延迟。Luo等人[6]提出了一种基于位置和集群的CBR路由算法，将区域划分为一系列逻辑网格，并在每个网格内选择簇标头，通过选择最优邻居簇标头进行数据转发直至到达目标节点，无需路由发现和保存路由表，一定程度上减少了内存开销，提高了数据包投递率，但提高了算法复杂度，增加了网络时延，算法所使用的车载GPS设备数据易受周围环境的影响，信号不稳定、定位静态漂移等现象导致GPS信息不准确。

1.2 基于群智算法的车载网络路由算法

此外，文献[12-16]分别将蜂窝算法、狼群算法和社交属性等群智算法引入传统车载网络路由算法，通过节点集优化策略进行自适应全局随机寻优，一定程度上优化了转发节点，提高了网络性能和转发率。Tian等人[12]提出了基于生物启发的车载网络机会路由算法。该算法利用蜂窝吸引子选择下一跳，并采用多属性策略优化候选节点，减少冗余。

Yu等人[13]提出了一种基于狼群算法的聚类路由算法。算法通过求解近似最优解进行节点整体规划；引入边缘度概念优化异构节点部署，有效提高了网络稳定性，延长了网络寿命。

余玲飞[14]提出了一种基于社会贡献的路由算法。该算法引入社会贡献率的概念进行下一跳节点的决策，采用激励机制增强节点转发意愿，提高了消息递交率。

综上所述，虽然基于群智算法的车载网络路由算法得到了改进，但其收敛时间较长，缺乏节点局部信息的有效利用，存在节点评价不全面、网络开销较大、数据传输缺乏稳定性等缺陷，这也是车载网络路由协议研究中一项具有挑战性的工作。基于此，文中利用遗传算法自适应、择优等特性，对分簇路由算法进行优化。

2 网络模型

本节将对文中提出的路由算法网络模型做出如下假设：(1)车载网络物理层和MAC层的通信标准采用IEEE802.11p协议，支持无线多信道接入。上层采用IEEE 1609.4协议标准，以利于上层实体调用802.11p功能；(2)车载网络环境下的车辆包括小轿车、货车、公交车等，文中在此不作任何区分，默认其转发半径、数据发送速率相同；(3)车载网络场景下的车辆均安装有GPS定位系统和城市电子地图，通过车辆智能系统获取车辆位置等重要车辆信息。类似的假设也出现在文献[13]中。

假设车辆行驶环境为经典的曼哈顿式街区，车辆节点具有高速移动性，其行驶方向沿着道路的延伸方向。因此，车载网络下车辆节点的运动具有一定的规律性，道路上车辆节点分布和车辆连通性也具有一定的可预测性。

3 基于遗传特征的分簇路由算法

基于以上网络模型假设，本节提出了一种基于遗传特征的分簇路由(genetic-characteristics-based clustering routing，GCCR)算法。该算法框架如图1所示。

图1 GCCR算法框架

(1)下一跳路段的选择。该过程主要解决交通路口面临左转、直行和右转多个数据传输方向时，如何通过可量化指标来评估各个路段，选择合适的下一跳路段。因此，就涉及到下一跳路段的选择问题。

(2)下一跳节点的选择。该过程首先通过分簇算法对车辆节点进行分簇并随机选取簇头节点；再利用遗传算法对服务节点集进行优化，建立选定路段上的最优前向转发路径。

3.1 下一跳路段的选择

街道交通路口通常出现四个道路延伸方向，即车辆在交通路口将面临左转、直行和右转三个行驶方向的选择。因此，车辆在道路行驶过程中就涉及到了下一路段的选择问题。下一跳路段选择策略主要取决于以下四个参数：路段车辆分布密度、路段出口与目标节点的归一化距离、路段的无线连通率和路段无线连通稳定性。假设选定范围内车辆节点集合表示为{X1,X2,…,Xi,…,XM}(1

(1)路段车辆分布密度。

路段车辆分布密度与网络传输效率有关。假设该路段Oi的长度为LOi，包含的车辆节点数为SXi，利用路边基础设施采集车辆节点数量数据并以fXi的频率定时更新，则路段Oi车辆分布密度ρi可表示为：

(1)

为避免路段车辆密度太小导致车距大于网络传输半径，从而影响数据转发效率；或者车辆密度太大造成网络时延，车辆分布密度应保持在一个稳定区间ρOi。

(2)

(2)路段出口与目标节点的归一化距离。

数据包总是向更靠近目标节点的方向进行传递，路段出口与目标节点的归一化距离越近，表示数据包越靠近目标节点。假设源节点Xi坐标为(x1,y1)，目标节点XM坐标为(x2,y2)，该路段出口点XOi坐标为(xi,yi)，则路段出口与目标节点的归一化距离βOi可表示为：

(3)

(3)路段的无线连通率。

路段的无线连通率反映了该路段网络通信质量。连通率的高低一般取决于以下两个因素：一是道路车辆分布密度ρOi；二是无线通信的传输半径ξ。当且仅当每两个相邻车辆可实现无线链路连通，整个路段才可连通。双车道无线连通分为两种情况：一是单向车道上相邻车辆之间的距离小于无线传输半径；二是对向车道存在有效的车辆节点可进行单向车道无线连通条件的补充，文中将其称为链路修复现象。设LCi表示路段无线连通长度，ξ为无线传输半径，则其无线连通概率POi可表示为：

(4)

假设Lk,k+1、Lk,i分别表示节点k到k+1和k到i的距离，ρk表示单向车道的车辆密度，Pk为单向车道中断概率，PRi为双向车道的无线链路修复概率，则：

Pk=P{Lk,k+1>ξ}=e-ρkξ

(5)

PRi=P(Lk,i<ξ)+P(Li,k+1<ξ)=1-e-2(ρOi-ρk)ξ

(6)

(4)路段无线连通稳定性。

路段无线连通稳定性是路段通信性能评估中非常重要的一项指标，体现了无线链路稳定传输情况。文中所提出的路段无线连通稳定性SOi可表示为：

(7)

综上，将路段车辆分布密度ρOi、路段出口与目标节点的归一化距离βOi、路段的无线连通率POi及路段无线连通稳定性SOi这四个参数引入下一跳路段评估函数EOi中：

EOi=ω1ρOi+ω2(1-βOi)+ω3POi+ω4(1-SOi)

(8)

3.2 下一跳节点的选择

下一跳节点选择采用基于遗传特征的分簇路由算法，包括以下两个步骤：一是对路段所有车辆节点分簇，随机选择簇头节点；二是建立适应度函数，通过遗传算法的选择、交叉和变异操作，选择一条高效的数据转发路径。

3.2.1 选择簇头节点

文中采用随机选取簇头的方法。首先，每个节点生成随机数τ，满足τ∈(0,1)。定义阈值T(i)，如式(9)所示，若τ

(9)

其中，R表示簇头节点数与节点总数的比值，R=w/SXi；c表示簇头选择次数；G表示当前还没有被选为簇头节点的集合，这一参数有助于簇头节点的能量负载均衡。

考虑到簇的大小对数据转发效率的影响，文中设定双向路段一跳范围内的所有车辆为一簇，以此类推，将路段内所有车辆划分至不同的簇。假设该路段的车辆节点共划分为w个簇，每一个簇Qi所对应的簇头节点分别为{X11,X21,…,Xi1,…,Xw1}(0

3.2.2 选择最佳数据转发路径

基于遗传特征优化服务节点，选择最佳数据转发路径。遗传算法的主要优点是可以通过全局可行解随机迭代更新达到高度收敛，防止陷入局部最优。

(1)编码和产生初始群体。

文中将每个节点看作一个基因，多个基因排列组成一个染色体，代表着路段Oi的一条数据转发路由，可表示为：G={g1,…,gi,…,gm}(1

SDi=Loc(Xi)-Loc(X0)

(10)

根据式(10)选择跳距SDi≤ξ的簇头节点作为服务节点。若节点Xi被选为服务节点时，将其所在基因设为1，否则为0，即：

(11)

(2)建立适应度函数。

适应度函数的建立主要考虑以下两个参数：无线链路信道质量和节点剩余能量。

(a)无线链路信道质量。

下一跳节点的优劣并不能完全取决于跳距的大小，跳距大的节点可能具有较低的无线链路信道质量。因此，文中引入无线链路质量。信噪比是度量网络链路信道质量的一个主要技术指标。设网络无线带宽为B，信道增益为G，PRi和PTi分别为接收和发送无线信号的有效功率，PSi为高斯噪声的功率频谱密度，则路段无线链路质量LQi的计算公式为：

(12)

(b)节点剩余能量。

节点剩余能量是评估节点的另一个参数。为了延长车载网络生存期，应选择剩余能量高的节点传输数据。假设每个节点具有相同的初始能量，表示为E0，当剩余能量小于阈值时，就不再将其选为服务节点。若节点能量消耗为ECi，则节点剩余能量DEi可表示为：

DEi=E0-ECi

(13)

为便于研究，文中将忽略簇内短距离无线信道微观的多经衰落现象。设Numi表示节点i所在簇的总节点数，ld表示数据包长度，EBit表示每比特数据传输所消耗的能量，εmfp表示多经衰落信道模式下的功率放大常数，εfsp表示自由空间信道模式下的功率放大常数，Ecol表示融合一比特数据所消耗的能量，则簇头服务节点能量消耗ECch和簇内其他节点能量消耗ECco分别为：

ECch=2(Numi-1)ldEBit+ldEcol+

ldεmfpLength2(Xi,XM)

(14)

ECco=ldEBit+ldεfspLength4(Xi,Xij)

(15)

因此，节点的能量消耗ECi可表示为：

(16)

根据节点评估参数建立适应度函数Fi，其计算公式如下：

(17)

其中，γ1+γ2=1。

(3)选择、交叉、变异操作。

选择操作是将适应度函数值较大的服务节点保留下来，将其随机组合成为一种可能的数据转发链路，并作为遗传过程中的父类个体样本；交叉操作是对选择操作的结果按照一定的交叉概率进行变换，形成不同的路由选取方案，使算法具有全局搜索能力；变异操作是在数据转发链路中，以一定的变异概率进行服务节点的更改，这在很大程度上防止算法陷入局部最优。算法伪码如图2所示。

图2 GCCR算法伪码

4 算法分析

4.1 计算复杂度

文中主要考虑算法的时间复杂度。设n表示节点数，则选择下一跳路段和下一跳节点计算复杂度分别为O(1)和O(n)，因此GCCR算法的计算复杂度为O(n)。GCCR算法的计算复杂度主要与服务节点个数、车辆密度、网络传输半径等有关。在网络传输半径一定的情况下，文中将道路车辆密度引入下一跳路段的评价指标中，并通过下一跳节点的跳距作为收敛条件，减少服务节点的冗余，有效降低了其算法复杂度。

4.2 网络开销

GCCR算法网络负载开销即数据转发过程中收发数据包的多少。GCCR算法的网络负载开销主要集中于下一跳路段和下一跳节点的选择过程。假设节点通过查询-响应机制获取其他节点的信息，区域内共N条路段，某路段Oi车辆密度为ρ，节点传输半径为ξ，则选择下一跳路段和下一跳节点的网络负载开销分別为⎣N/2」×「N/2⎤和ρπξ2。因此，执行一次完整的GCCR算法所需的网络负载开销ONoh如下：

ONoh=⎣N/2」×「N/2⎤+ρπξ2

(18)

5 仿真结果及其分析

5.1 实验设置

文中实验使用VMware虚拟机及Ubuntu16.04操作系统，模拟软件为NS2.35(https://www.isi.edu/nsnam/ns/ns-build.html)。依据车载网络安全预警应用对网络传输时延和无线链路稳定性的要求，选取ω1=0.2，ω2=0.3，ω3=0.2，ω4=0.3，γ1=0.2，γ2=0.5，γ3=0.3。遗传算法中交叉概率范围一般选择在0.6～1.0之间；变异概率通常选择不大于0.1，本实验中交叉和变异概率分别设为0.8和0.1，此时算法表现最佳。实验中其他参数设置如表2所示。

表2 参数设置

5.2 实验结果与分析

为了验证GCCR算法的有效性，将其与经典AODV贪婪路由算法和LEACH分簇路由算法进行实验对比，其数据包投递率、网络传输时延和网络开销等对比如图3～图5所示。

图3 数据包投递率对比

图4 网络传输时延对比

图5 网络开销对比

数据包投递率指仿真时间内目的节点接收到来自于源节点数据包总数与源节点发送数据包总数的比值。图3显示，节点数量一定时，数据包转发投递率与节点速率成反比。当节点速率大于60 km/h时，以上算法投递率下降加快，主要原因是节点速率较大时，能够建立通信链路窗口期较短，节点间连通性变差。但GCCR算法相较于传统路由算法具有更高投递率，这主要与节点密度和网络传输半径等有关。当网络传输半径一定时，文中将节点密度引入下一跳路段的评价指标中，保证节点速率过快链路断裂也仍能发现可替代中继节点，加快路由修复，通信链路更加稳定，投递率也更高。网络传输时延指数据包从源节点到目的节点所消耗的时间。图4显示，网络传输时延随节点速率增加呈上升趋势，原因是当节点速率增大时，链路稳定性降低。由图4可知，在任意速度下，GCCR算法传输时延均为最小，而以上三种路由算法计算复杂度均为O(n)，所以其主要原因是GCCR算法具有较少的冗余节点。文中所提出的节点密度阈值概念以下一跳节点跳距为收敛条件，减少了服务节点的冗余，收敛性表现良好，有效降低了网络传输时延。

随着节点速率增加，数据传输所需带宽增加，如图5所示，网络开销也逐渐增加。由式(18)可知，在节点传输半径和数据包大小一定时，GCCR算法网络开销与路段车辆节点密度有关。算法设定车辆密度阈值选择最佳路段，综合考虑路段无线连通率和无线连通稳定性，保证数据传输路段的网络通信质量，减少传输链路中转发信息冗余，从而减少网络开销。综上所述，GCCR算法在保证较高投递率的情况下有效降低了网络数据包传输时延和网络开销，满足车载网络安全预警应用链路稳定性、网络实时性和数据包高效转发等需求。

6 结束语

文中对传统车载网络路由算法进行比较分析，在分簇路由算法的基础上引入遗传算法的思想，对数据包传输链路进行优化，最终提出一种基于遗传特征的分簇路由算法。文中的创新点在于将车辆密度、节点剩余能量等参数引入下一跳路段或节点的选择过程中，针对车辆高速行驶导致的网络链路频繁中断和抖动、震荡现象采取了平滑处理，更大程度上满足安全预警应用对网络时延和稳定性的较高要求。实验数据表明，该路由算法在数据包投递率、网络传输时延、网络开销方面均优于传统算法。

但文中算法在遗传算法的实现过程中缺乏对车辆行驶速度、方向等参数的考虑，因此对于车辆高速行驶场景中的车辆数据不够全面，缺乏鲁棒性；当车辆密度较小如交叉路口的行驶场景中，未考虑服务节点数据转发受限的问题，而携带转发又会导致传输时延增加，这一问题也是课题组未来进一步研究的重点。