多车队队间通信端到端时延最小化研究*

聂淑珍 李正权，2

（1.江南大学江苏省模式识别与计算智能工程实验室 无锡 214122）

（2.东南大学移动通信国家重点实验室 南京 210096）

1 引言

车队应用是目前智能交通系统中最有前景的应 用 之 一［1～2］，车 队 内 的 车 辆 通 过V2V（Vehi⁃cle-to-Vehicle）通信周期性地传输包含车辆速度和加速度等与车辆运动相关的数据包，使车队中的各车辆保持恒定的速度和比较小的恒定车间距［3～5］。每个车队包含一个头部车辆，一个尾部车辆和多个成员车辆。头部车辆是车队中的第一辆车，控制着车队的速度和行驶方向；尾部车辆是车队中的最后一辆车；成员车辆处于车队的中间位置。头部车辆和尾部车辆被统称为骨干车辆［3］。相关研究表明，形成车队可以促进对车辆的管理，有效减少交通拥堵，节约能源并增强交通安全［4～6］。

当车辆的数目较多时，为了方便管理，需将车辆划分为一个包含多个子车队的大车队，称之为多车队［7］。多车队场景如图1 所示。在多车队中，各骨干车辆均配备了两个收发器。一个用于队内通信，即骨干车辆与其所属子车队的成员车辆间的通信；另一个用于队间通信，即骨干车辆与其他骨干车辆的通信。对于队间通信，各骨干车辆采用的是IEEE 802.11 分布式协调功能（Distributed Coordina⁃tion Function，DCF）协议来接入控制信道，并通过多跳的方式与其他骨干车辆通信。因此，在这种情况下，队间通信端到端时延会受各骨干车辆一跳时延的影响，而影响各骨干车辆的一跳时延的主要因素如下。

1）最小竞争窗口。802.11 DCF 协议采用的是载波监听多点接入/冲突避免（Carrier Sensing Medi⁃um Access/Collision Avoidance，CSMA/CA）机制访问信道，该机制采用了二进制指数退避规则来减少碰撞，该标准下的最小竞争窗口是64，造成各骨干车辆在退避过程中耗费了大量时间。

2）直接相邻的骨干车辆数目。多车队队间通信中各骨干车辆只能与其直接相邻的骨干车辆通信，各骨干车辆的通信范围内竞争信道资源的骨干车辆数目不同，造成各骨干车辆花费在退避冻结上和重传分组上的时间差别大［8～9］，各骨干车辆的一跳时延不均衡。

3）隐藏终端的数目。多车队中各骨干车辆的隐藏终端数目受该骨干车辆所处位置的影响，隐藏终端数目不同，其发送分组时冲突的概率就不同，花费在重传分组上的时间也就不同［9～10］。各骨干车辆的一跳时延不均衡。

车辆间的安全相关信息需要被迅速交付，以便在遇到紧急事件时车辆能够及时接收到信息并采取相应措施，增强道路安全［11］。而多车队的所有骨干车辆均使用IEEE 802.11 DCF标准下的最小竞争窗口，且各骨干车辆直接相邻骨干车辆和隐藏终端数目不等，造成各骨干车辆的一跳时延偏大且不均衡，重要信息可能在某一个骨干车辆上耽搁较多时间而无法迅速交付给其他骨干车辆，故整个车队的端到端时延偏大。因此，本文提出一种降低多车队通信的端到端时延的信道接入方式，该方式结合智能算法寻找适合各骨干车辆节点的最小竞争窗口，降低并平衡各骨干车辆的一跳时延，实现多车队队间通信的端到端时延最小化。仿真结果表明，与使用标准竞争窗口下的端到端时延相比，本文提出的信道接入方式下在骨干车辆数为8 时，端到端时延降低约11%，端到端吞吐量增加约5%。且随着多车队中骨干车辆数目的增加，端到端时延和端到端吞吐量能得到显著改善。

2 系统模型

在多车队场景中，每个子车队的骨干车辆（头部车辆和尾部车辆）通过队间通信周期性地发送与车辆运动相关的信息，子车队中的骨干车辆再通过队内通信将这些信息发送给它车队内的成员车辆，以保持车队在道路上的队形。本文主要研究队间通信。在队间通信中，用n 标记多车队中子车队的个数，那么，多车队里共有2n 个骨干车辆，用1，2，…，2n-1，2n 标记这些骨干车辆，骨干车辆使用队间通信专用的收发器通过多跳通信技术与其他骨干车辆通信。此外，为了保持两个连续车队的联系和保证两个连续车队车辆的安全，骨干车辆只能与其直接相邻的前后两个骨干车辆通信［7］。记a为骨干车辆向前一个骨干车辆发送分组的概率，1-a 为该骨干车辆向后一个骨干车辆发送分组的概率。

图1 多车队队间通信场景

骨干车辆均采用IEEE 802.11 DCF协议来访问控制信道，该协议采用CSMA/CA 机制［12～13］。当骨干车辆有分组要发送时，它会在等待分布式帧间间隔（Distributed Inter-Frame Spacing，DIFS）的时间后，随机从［0，Wk-1］里选择一个整数作为退避计数器的初始值，这里k 表示该分组重传的次数，Wk是数据包被第k 次重传时的最小竞争窗口大小。若信道被检测为空闲，则退避计数器的值减1；否则，退避计数器的值被冻结，直到信道再次被检测为空闲且在DIFS 时间段内连续空闲。若退避计数器的值递减到0，骨干车辆将占用信道传输该分组。若骨干车辆在传输分组完成后的短帧间间隔（Short Inter-Frame Spacing，SIFS）周期后没有收到确认信息，它将从［0，WK+1-1］中随机选取一个整数值作为退避计数器的初始值并开始新的退避过程，这里，WK+1=2 Wk。若重传次数达到最大重传限制次数，骨干车辆将丢弃该分组［14～15］。

3 算法介绍

本节主要介绍最小化队间通信端到端时延的智能算法。算法分为初始化过程，迭代寻优过程，最优解判定过程三部分。

3.1 初始化过程

首先确定m 个初始化的2n 维随机解，即m 个最小竞争窗口组合，每一个组合里的各值对应多车队中骨干车辆1，2，…，2n-1，2n 的最小竞争窗口值，这些整数值均从［1，64］里随机选取。

3.2 迭代寻优过程

在迭代寻优过程中，m 个最小竞争窗口组合的值被迭代更新，在每次迭代中，都有一个使得目标函数值最大的最小竞争窗口组合。记第t 次迭代中，使目标函数最大的最小竞争窗口组合为gbest（t）。

第一次迭代时，输入为初始化的m个最小竞争窗口组合，仿真实验根据式（1）计算出使用组合对应的最小竞争窗口时各自的一跳时延。

其中，Tij(t)表示第t 次迭代下使用第j 个竞争窗口组合时，第i个车辆发送分组所消耗的总时间；xij(t)为此时第i个骨干车辆成功发送的总分组数；Dij(t)为第i个车辆成功发送一个分组的平均一跳时延。

找出其中使得目标函数值最大的组合gbest（t）。目标函数由式（2）给出，该目标函数衡量各骨干车辆的一跳时延与Davg的接近程度，Davg为各骨干车辆实际可取得的平均最小一跳时延。目标函数值越大，各骨干车辆总体的一跳时延越接近Davg，队间通信的端到端时延就越小。其中，CWj(t)为第t次迭代时第j个最小竞争窗口组合，f(CWj(t))为第t 次迭代使用第j 个最小竞争窗口组合时的目标函数值。

第t次迭代的最小竞争窗口组合按上一次迭代（第t次迭代）中的最小竞争窗口组合按以下步骤更新。

1）使用轮盘选择法根据本次迭代的最小竞争窗口组合更新下一次迭代的最小竞争窗口组合，在该方法中，各个最小竞争窗口组合被选择的概率与其对应的目标函数值成正比，即目标函数值越大，该竞争窗口组合被选择的概率越大。选择概率和相应的累积概率如式（3）和式（4）所示。

其中，P(CWj(t))为第t 次迭代第j 个最小竞争窗口组合被选择的概率，qj(t)为第t 次迭代前j 个最小竞争窗口组合被选择的累加概率。

2）将第一步得到的组合根据式（5）计算，产生新的组合。

其中CWij(t)、CWi(j+1)(t)分别为第t 次迭代时第j 个组合和第j+1 个组合中的第i 个骨干车辆的最小竞争窗口值，CWij(t+1)、CWi(j+1)(t+1)分别为经过此步骤得到的最小竞争窗口值，a1、a2 为［-0.25，1.25］之间的可变随机数。

3）在经过上述步骤之后，以一定的概率随机改变各最小竞争窗口组合中某一个骨干车辆的最小竞争窗口值。

3.3 最优解判定子过程

第t次迭代时，通过仿真实验和式（2）计算出m个目标函数值和gbest（t），若f（gbest（t））大于指定的精度值或迭代次数达到上限，则迭代结束，gbest（t）即为使得多车队队间通信端到端时延最小化的最小竞争窗口组合；否则，按迭代寻优过程的三个子步骤继续更新第t+1次迭代的m个最小竞争窗口组合。寻找最小化队间通信端到端时延最优竞争窗口组合的智能算法伪代码见算法1。

4 仿真结果及其分析

本节主要比较多车队各骨干车辆使用IEEE 802.11 DCF 机制定义的标准竞争窗口大小下与本文算法寻找的最小竞争窗口下的发送概率，一跳时延，端到端时延和端到端吞吐量。仿真场景如第三节描述，表1 给出了实验中使用的参数。其中CWmin为IEEE 802.11 DCF 机制中定义的标准最小竞争窗口大小［11～12］，E［L］为每个分组的大小，s 为每个时隙占用时间，M为DCF机制中定义的最大重传次数，R 为信道比特率，pe为由信道引起的传输错误概率，m为迭代时最小竞争窗口组合总个数，Im为最大迭代次数。

算法1.最小化队间通信端到端时延智能算法

按照q从本次迭代的组合里选择

图2 给出了当多车队中骨干车辆总数为8（2n=8）时，各骨干车辆使用本文算法得到的最小竞争窗口下和使用标准竞争窗口下的发送概率，一跳时延，端到端时延和端到端吞吐量。从图中可以看出，各骨干车辆均使用标准最小竞争窗口时，其发送概率不均衡且普遍偏低，而使用本文算法得到的最小竞争窗口后，各骨干车辆的发送概率约提高了40%。使用标准最小竞争窗口时，各骨干车辆直接相邻的骨干车辆个数不等，隐藏终端个数不等，造成各骨干车辆一跳时延波动较大。第1 个骨干车辆和第7 个骨干车辆的单跳时延约为2.4ms，而第3、4个骨干车辆和第5、6个骨干车辆的单跳时延在4.5ms左右。当使用本文算法得到的最小竞争窗口后，各骨干车辆由于采用的竞争窗口比标准竞争窗口小，且能根据车辆位置动态调整，故其一跳时延均可维持在3.3ms 低时延水平，骨干车辆1 到骨干车辆8 的端到端时延降低至24ms，比标准下的端到端时延减少约11%。此外，从图中还可观察到，使用本文算法后，骨干车辆1 到骨干车辆8 的端到端吞吐量约为4.2Mbp/s，比标准情况下的端到端吞吐量提高约5%。

表1 仿真参数列表

图3 比较了当多车队中骨干车辆数目为20（2n=20）时，使用本文算法得到的最小竞争窗口下和使用标准最小竞争窗口时队间通信的各骨干车辆的发送概率，一跳时延，端到端时延，端到端吞吐量。从图中可以看出，使用算法优化后的最小竞争窗口下的发送概率普遍比标准情况下的发送概率高，各骨干车辆的一跳时延能维持在3.5ms 左右，第1 个骨干车辆到其它各骨干车辆的端到端时延，端到端吞吐量随着骨干车辆索引数的增加而线性增加。与使用标准最小竞争窗口下端到端时延相比，本文算法端到端时延减少了约13%，端到端吞吐量增加了约10%。

图2 骨干车辆数目为20时队间通信性能

图3 骨干车辆数目为20时队间通信性能

5 结语

为解决多车队队间通信端到端时延较大的问题，本文结合智能算法根据多车队内骨干车辆数目动态调整各骨干车辆的最小竞争窗口，使各骨干车辆的一跳时延维持在较低的水平线上，实现队间通信端到端时延的最小化。仿真结果表明，通过使用本文算法得到的最小竞争窗口，各骨干车辆的一跳时延能维持在低水平线上，且与使用标准最小竞争窗口的各指标相比，本文算法的发送概率提高了约40%，端到端时延降低了11%，且随着多车队中骨干车辆数目的增加，端到端时延和端到端吞吐量得到显著改善。