车载自组网信息服务与动态交通诱导算法研究

彭康华，杨军，黄裕锋

（广东工程职业技术学院 信息工程学院，广东广州510520）

据统计，我国的交通意外发生率排在世界前列，车载自组网是未来有效解决安全出行的关键途径。Dedicated Short Range Communication（DSRC），即车载专用短程无线通信，在减少交通事故、降低交通拥堵和提高交通效率方面有较好作用[1，2]。基于车载专用短程无线通信网络可用于车联网[3]，能够对车辆的运行状态实现实时监测及综合分析，进而为驾驶员提供更高效的服务，同时缓解目前积重难返的城市交通拥堵及减少交通事故的发生。车辆接入DSRC，就可将车辆操作信息传送至周围的车辆，使得收发信息、执行速度和反应得以提高，各类信息都能得到即时的共享或预警[4，5]。为达到上述条件，提出了一个研究方案，其主要特征是研究IEEE802.11p的车载自组网（VANET，Vehicular adhoc network），提供交通信息服务与基于并行蚁群算法的动态交通诱导服务，确保行车安全及通行效率。

1 基础硬体配置

在目前条件下，联网的汽车均安装有IEEE802.11p全双工无线模块的无线网卡，用于联网汽车间的通信，由车载系统进行控制。在IEEE802.11p发布前，不少研究学者已做了模拟实验，结论是IEEE802.11p在高速运行情况下，能为汽车提供正常的移动信息收发[6，7]。在我国的标准中，DSRC支持的是5.8 GHz，在5.725 GHz到5.875 GHz的共用频段内。更有学者研究表明，使用IEEE 802.11a驱动为基础，基于 DCMA86 P2、Atheros5414B等芯片的无线网卡，通过实验实现了IEEE 802.11p的驱动。车联网的车载系统可以智能的识别和收发语音，通过10英寸的液晶显示屏来对车辆相关信息及道路相关信息的输出输入，传送交通服务信息及预警信息。

2 组网设计技术

研究方案的网络拓扑结构使用基于IBSS，即独立基本服务集（Independent BSS）网络，也被称作ad-hoc网络、无线自组网、对等网等[8-10]，该网络的主要特征是有较强的抗毁坏性，无论是需组网还是需解除，均较为方便，并且费用相对低廉。数据帧主要构成如表1所示。

表1 IEEE802.11p数据帧构成

上述的数据帧构成，附带车辆身份认证信息、帧头和帧尾、校验位等，每帧总共设定为300bit。在实际应用中，与每辆车发送帧相关的汽车，通常为附近的接收车辆，设定附近车辆为30辆，根据该车辆密度控制发射功率，以IEEE802.11p为基础，假设每车发送10帧/秒，可以通过统计和计算，计算出数据帧所使用的总数据量。每秒为:

300Byte×8bit/Byte×Byte×30辆车×10帧=720kbit。

通常，IEEE802.11p在120公里每小时下，一般可以执行18 Mbps左右的接入速率，以此来计算，已经有足够的冗余，能充分满足车联网需求。

3 车联网交通信息服务

3.1 车辆定位交通信息传输的实现

现阶段常用的是GPS绝对定位技术，配合使用DSRC，每辆车辆都可以发送本身的定位信息，同时能接收附近的车辆定位等信息，建立车联网的位置关系图。为得到更精确的定位，同时配合使用了相对定位。相对定位使用超声定位，当车辆在十米以内，或无卫星信号，比如隧道，车库内，该场合可以使用相对定位来构建以本车为中心的位置关系图。在应用超声定位时，每一辆车上安装一个广角超声发射装置，三个超声接收装置。车辆在IEEE802.11p无线网卡发送完一数据帧后，随之发送超声波信号，按照接收的无线电信号与超声信号所到达的时间差，可以计算发送信号车与接收信号车的间距。而车辆的方向确认通过不同方向设置的三个超声波接收器来确定。车载系统根据接收的数据帧内容及相对定位计算数据，通过分析和计算，可以在人机界面获得附近车辆的ID、车辆状况、位置关系等相关数据。

3.2 改进蚁群算法动态交通诱导实时服务

通过将上述的交通信息服务采集或通过DSRC接收的路面实况，实时发送到车联网中，车辆收到诱导信息后，能够根据路面情况来选择或避开堵塞路段，从而提高出行效率及道路的使用率，降低交通事故发生率，使得路面资源得到有效的优化和配置。

3.2.1 基本蚁群算法模型

蚁群在觅食时能分泌信息素，所走的路程越短，信息素越浓，趋于选择该路径的蚂蚁越多，这就是蚁群算法的正反馈机制。建模时，第t次迭代网点上的信息素描述为τij（t），信息素初始化为零，即τij（0）=const，蚂蚁k历遍的途径点描述为禁忌表tabuk（k=1…r），历经途径 i、j的启发信息描述为ηij（t）。在求解时，以信息素为依据，系统选取随机概率来历遍节点，由此可知，系统在第t次循环时，蚂蚁k选择节点i到节点j的转移概率如公式（1）所示。

公式（1）的allowedk=neighborsi-tabuk，代表蚂蚁k接下来爬行的下一路径，是邻居节点排除禁忌表爬过的节点，neighborsi指的是邻居路径节点集。α、β描述为各启发因子。ηij（t）表达的是启发函数值。

3.2.2 修正的蚁群算法

修正的蚁群算法中，对转移概率、信息素浓度更新方法和启发函数等关键影响指标进行改进。

①改进的转移概率方法

随着路网成倍增长，节点数量急剧增大，求解时收敛所耗费时间更长。通过改进传统算法，提出模仿最大最小蚁群系统方法，改良为伪随机转移概率，以求解决收敛效率低的问题。具体实现方法见公式（2）。

公式（2）的R值是0到1间的随机值，R0表达为概率选择因子，如果R≤R0，蚂蚁即可以依据相邻节点转移概率最大的搜寻；如果R＞R0，依据轮盘决定随机节点。伪随机概率既可以满足传统算法的多变性，同时实现了可靠的收敛性，改进了算法的收敛效率，使得算法更加的智能化。

②改进的信息素浓度更新方法

每个蚂蚁以出发点至终点为一次爬行，使用局部更新方法。当r个蚂蚁完成一次迭代，路径实行全局更新方法。为使得下一个蚂蚁搜寻到上一个蚂蚁爬行的路经以增加多样性而采取了局部更新，以此对之前爬行过路经上的信息素浓度实施弱化处理，具体操作方法见公示（3）所示。

而全局的更新方法见公式（4）所示。

公式（5）中，Lz表达的是已搜寻的全局最佳路经。

这种全局更新方法更便于全局最短路径的搜索。

③改进的启发函数

改进的动态交通诱导启发函数中，设置了路网的加权值，为时间的函数。按照实时接收的交通服务信息来计算路面状况并预测，同时参考过去数据，计算路面在不同时间的行程时间t对应的函数f（t），如公式（6）所示。

时间函数f（t）、启发函数ηij与转移概率（t）的关系为f（t）↓⇒ηij（t′）↑⇒（t）↑，体现了动态交通变化特征，适用于实际出行交通信息服务。同时Lk代表蚂蚁k搜寻路径上行程花费总时间。

根据以上分析，归纳总结经过改进的蚂蚁算法步骤如图1所示。

图1 改进的蚂蚁算法步骤

通过改进的转移概率、信息素浓度更新方法和启发函数等关键影响指标，得到修正后的蚁群算法模型，并按上述步骤进行后节的算法实验。

3.2.3 动态交通诱导服务的并行计算法

随着人口及车辆的快速增加，交通压力日益增大，串行计算的最优路径诱导现已跟不上大规模的繁忙交通诱导的步伐。为了解决该瓶颈，并行动态交通诱导应运而生，保证了大规模交通诱导的实时性，并行计算的车联网动态交通诱导对用户快速出行需求作用巨大。

①并行计算模型

对于蚁群算法的特征而言，比较方便和适用的是信息传递模型 Message Passing Interface（MPI），该软件平台无关于编程语言，进行并行计算只需调用MPI的可移植性编程接口即可实现，也可进行异步通信，能应用于目前流行的各大操作系统，易于操作和实现。设定有r只蚂蚁，划分q为个子蚁群，在各处理器中各子任务分别执行串行蚁群算法。

②改进并行蚁群算法模型设计

在实际运用过程中，子任务求得解后需与其他处理器交换数据，但这种屡屡的数据交换可能是无用的或低效的。因此，需改进和设置固定交换周期，达到减少无用交换频率的目的。处理器通信采用主从式消息传递机制，主伺候器将汇总从伺候器在固定周期内达到的局部解，实施杂交算法来运算并反馈结果。在改进算法实施时，对求得最优解的收敛速度起关键作用的是杂交算子，杂交算子的作用在于预防局部收敛，提升求得全局最优解的概率。使用主从式通信机制时，当蚂蚁迭代次数等于所建立的固定交互周期值，主节点得到其它次节点在交互周期传递的最优解，并使用杂交算子机制来分析与处理。

③改进并行蚁群算法模型实现

设定有m个处理器，主处理器已接收来自从处理器的最优解，S={S1，S2，…，Sm}，其中 Sm代表第m个处理器求得的最优解，接下来是使用杂交算子方法来分析和处理该最优解。上述的算法中，结合路网的实际，使用了启发式杂交算子，通过实验案例来表达如下所示。

设定路径 S1={5，4，10，6，9，16，26，20，19}，路径 S2={5，7，8，10，12，14，16，23，20，19}，为被选中父体实施杂交，S1，S2括号里的数字为路径的节点。如去除首末节点后，相同节点有2个以上时，则将头2个相同节点来杂交，杂交点间的节点交换，生成杂交段。从S1，S2路径可以看出，除起始节点和结束节点相同外，相同节点为10、16和20，再选择起始于终点实施杂交，最终得到交换后的路径表达如下所示。

路径 S1′={5，4，10，12，14，16，26，20，19}，路径S2′={5，7，8，10，6，9，16，23，20，19}。

以上使用的杂交规则不但与复杂路面逻辑连接性相一致，更是应用了杂交运算，因此，具有很好的操作性和现实意义。在杂交后，将前后的路径长度做对比，可以发现，S1′，S2′代表杂交后路径，若有S1′≤ Min（S1，S2），或 S2′≤ Min（S1，S2），即可对 S1′或S2′依据公式（5）来更新信息素浓度，将更新后的结果来替代对应子节点的最优解S1，S2，同时更新S集，在S集的全部项均完成杂交运算后，返回结果到各自处理器，并完成更新路径的信息素浓度操作。

根据上述研究，归纳并行蚁群算法步骤如图2所示。

以上就是基于改进蚁群算法基础上的平行蚁群算法步骤，不同于串行蚁群算法的是将更新后的结果来替代对应子节点的最优解S1，S2，同时更新S集，在S集的全部项均完成杂交运算后，返回结果到各自处理器，并完成更新路径的信息素浓度操作。

图2 平行蚂蚁算法步骤

3.2.4 数据试验

①改进蚁群算法试验

基于人工智能的蚁群算法在动态交通诱导中应用广泛，根据修正的蚁群算法，采用改进的转移概率、信息素浓度更新方法和启发函数等关键影响指标，使用较有代表性的广佛交界的地图路网实行规划和进行仿真动态交通诱导试验并实证。该路网有20478个路径节点，21795条路段，具有较强的代表性。仿真规划路段为节点编号949的萝岗开泰大道到节点编号5943的广佛公路，最优路径求解的编程语言使用C语言，基于super map软件平台下进行仿真实验。算法模型中，蚂蚁数r=60，迭代次数 Nmax=50，启发因子 α =1，β =3，信息素总浓度Q=30。经改进蚁群算法计算，大量试验表明最小路径收敛曲线见图3，最佳路径见图4。通过分析和结果对比，改进后的蚁群算法对全局最优解的搜寻效率更高，可靠性得到很大的提升。

图3 求得最小路径的收敛曲线

图4 最优路径的求解

②蚁群并行算法应用实例分析

本文建立了多个处理器的试验环境，对并行算法的效果进行实证。试验中，路径初始化参数、路网出发点、目标点的设置采用上述串行蚁群算法的设定，基于多处理器环境下执行并行运算。设置不同数量的处理器，多次试验和记录，分析不同数量处理器下的算法收敛值、计算所花费的时间。将不同数量处理器下的算法收敛值、计算所花费的时间作图分析，直观显示如图5和图6所示。

图5 不同数量处理器下的算法收敛值

图6 不同数量处理器下的算法所花费时间

通过不同数量处理器的反复试验数据分析，得到的结论是处理器的数目从少到多的递增，对应的收敛值越小，但计算时间是先减少，后增加。在试验中，当处理器的数量为4时，收敛值时间花费是最少的。处理器的数量再递增到6，所花费的时间并非减少，反而是增加，原因是处理器数量增加，并行蚁群算法的处理器间进程信息传递及通讯时间花费增大，因而使得总的计算花费时间增加。对于收敛值随着处理器的增加而减少的结果，原因是处理器数量增加，算法的搜寻区域更大，尽管花费在搜寻的时间更多，但最优解却容易得到，可靠性更好。

4 结束语

并行蚁群算法的动态交通诱导技术通过实验表明，处理器数量的递增，实验结果的收敛值越小，计算时间先减少后增加。收敛值减少证实并行算法更易于对解空间进一步搜索，发现全局更佳的最优解。计算时间先减后增表明，在并行蚁群算法中，处理器增多，处理器间进程通信消耗时间极速增大。在实际应用中，面对的可能都是跨城市跨省的规模大和复杂的路网及状况，因此，并行蚁群算法的并行处理最优值和计算时间都有不同程度的提升，但处理器数量太大就会以花费更多计算时间为代价，故需设定达到平衡值的处理器，以提高并行蚁群算法的效率。使得在车辆间更好实现组网和传递交通诱导信息、安全预警等，让驾驶员更早得到预见并及时做好安排，使得安全出行更有保障。