基于车辆运行管理的多目标化V2V数据传递优化研究

尹 乾

（西安外事学院工学院，陕西 西安 710077）

引言

1 基于轨迹的多目标优化数据传递方法建模

1.1 传输延迟与网络开销的关系

传输延迟是指信息传输过程中，由于传输经过的距离远或者一些故障，或者网络繁忙，导致传输并没有准时达到目的地情况。而要提高传输效率，就要求数据在局域网和广域网之间传输时不进行协议转换，避免传输延迟和抖动，因此会增加网络开销。传输延迟和网络开销对车辆自组织网络数据传递都非常重要，但两个指标之间相互冲突，即一个指标减少时会诱发引起另一个指标增加。如果要兼顾两个指标，不能简单地最小化传输延时或者网络开销，也不能按比例分割处理，要通过方案优化来处理二者之间的关系，提高传输效率[3]。

1.2 交叉路口转发决策

通过与交叉路口相连的各方向采取优先级排列的方法进行优化决策，当携带数据包的车辆到达交叉路口处，数据包携带者根据数据平台测算的优先级别进行优先级别的选择，并实现自身状态信息与数据平台及周边车辆终端之间的数据传递。预先计算好的最优决策进行下一步转发方向选择，它首先检查自己传输范围内是否有向优先级为1的方向（这个方向由道路段或交叉路口指明）行驶的车辆，如果有就转发，若没有，再检查它自己是否向这个方向行驶，如果是，就不转发数据包[4]。否则就认为数据包无法向优先级为1的方向转发，那么携带数据包的车辆再检查其通信范围内是否有向优先级为2的方向行驶的车辆，其优先级的决策，如图1所示。依次类推，数据包最终会根据当前交通状况，以最优的选择向数据平台或周边的数据包携带者车辆终端转发信息。

图1 交叉路口处具有优先级的决策Figure.1 Decision with priority at intersection

车辆自组织网络中数据传递问题可以很好地映射为马尔可夫决策过程。其中数据包的位置为马尔可夫决策过程中的状态集，转移概率可以通过对车辆轨迹的分析或通过道路交通统计得来[5]，如图2所示。

1.3 马尔可夫决策过程模型映射

图2 交叉路口i处马尔可夫决策过程模型Figure.2 Markov decision process model at interaction i

此外，选择数据包将哪个方向传递即为马尔可夫决策过程的动作集，传递延迟和网络开销都可以看作马尔可夫决策过程中需要最小化的值。解马尔可夫决策过程的目标便是求出最优决策，在本问题中即是求出数据包传递过程中道路网的每个交叉路口的决策。

根据相应的马尔可夫决策过程模型，计算公式如下：

它的通用表示形式为：

一百多年前人们在规划西克尔高地时就设定了一系列明文规定：“包括你能做什么和不能做什么”。他们相信“规则是秩序之母，是营造和谐的关键，因此一切都应该得到管理”，就连起床时间、窗帘颜色、男人头发长度等等，都需要得到管理。此外“还有一些潜规则”，比如每家房子的颜色都要遵从规划者的意图。这座被誉为“克利夫兰山巅的彩虹”的城市，从一开始就被规划和建设成“山巅之城”。由此形成西克尔人“只有规划才是最好”的价值观、“一丝不苟”的追求目标。里查德森太太家第一代移居者就非常赞赏这些规则，终生践行、维护着它们，并且将之一代代传承下来。

其中j为交叉路口i的某相邻交叉路口，Ii为i的相邻交叉路口集合。

1.4 转移概率的推导

首先考虑这样的情景：携带数据包的车辆到达交叉路口i，在采取策略的情况下数据包通过道路段eij被传递到交叉路口j，便表示当前情境下数据包被向交叉路口j的方向转发的概率[6]。很显然，如果携带数据包的车辆遇到向 j方向行驶的车辆或者它自己向这个方向行驶，这个数据传递过程便能完成，但是前提是携带数据包的车辆没有遇到驶向策略中比eij优先级更高的道路段的车辆，并且它自己也不向优先级更高的道路段上行驶。由此，定义三个概率事件：

A事件表示某一车辆在交叉路口i处没有遇到驶向比道路段eij优先级更高的道路段的车辆；

B事件表示某一车辆在交叉路口i处遇到驶向道路段eij上的车辆，并且车辆自己不驶向比道路段eij优先级更高的道路段；

C事件表示某一车辆驶向道路段eij上的概率。

通过三个实践的组合推导可以得到转移概率公式如下：

2 多目标数据传递求解策略

2.1 凸组合

凸组合的方法就是将两个优化目标的值函数通过加权进行合并，设定这个新的数据传递目标为M，在决策π的情况下，交叉路口i处的这个目标函数表示为：

2.2 帕累托最优

解多目标马尔可夫决策过程还有另一种方法就是求出它的帕累托最优决策集。对于车辆自组织网络数据传递问题，可以先利用求解多目标马尔可夫决策过程得到它的帕累托最优决策集合，再根据一定的策略选取集合中的决策进行数据包的转发[8]。利用马尔可夫决策过程优化传输延迟和网络开销这两个指标，使之最小化。

帕累托最优是指资源分配的一种理想状态。假定固有的一群人和可分配的资源，如果从一种分配状态到另一种状态的变化中，在没有使任何人境况变坏的前提下，使得至少一个人变得更好，这就是帕累托改善。帕累托最优的状态就是不可能再有更多的帕累托改善的状态;换句话说，不可能再改善某些人的境况，而不使任何其他人受损。在车辆自组织管理中，假设具有传输延迟和网络开销两个目标要通过马尔可夫决策过程最大化这两个目标的值。假设两个目标的值都大于0，两个坐标轴与凸曲线之间的每个点都对应一个决策（连续情况，离散的情况相似），每个点都对应两个目标的值，这两个目标值便是由相应的决策计算得来。那么凸曲线上的所有点对应的决策即为此多目标马尔可夫决策过程的帕累托最优决策集合。这个曲线上所有点的特点即不会被集合中其他任何一个点所 dominate[9]。这里，dominate定义这样描述：两个l维值向量，满足以下条件：

图3 多目标马尔可夫决策过程的值曲线（两个目标）Figure.3 Value curve in multi-target Markov decision process (two targets)

2.3 数据传递以及错误恢复

当数据包到达目的交付路口时，目的车辆可能不在此位置，无法直接交付，主要考虑两种情况。第一种是目地车辆比数据包先到达目的交叉路口 id。当携带数据包的车辆到达id在其通信范围内没有找到目的车辆，于是检查时间戳，这时会发现目的车辆已经驶过此处，这时数据包会被沿着目的车辆的轨迹的方向继续转发（不再使用之前计算出的策略），直至追上目的车辆交付成功或者到达TTL而被丢弃。第二种情况即数据包比目地车辆提前到达目的交叉路口 id。此情况下，数据包会被朝着目的车辆轨迹相反的方向继续转发直至与目的车辆相遇并交付或者达到网络生存时间被丢弃。

3 测试与评估

3.1 实验设定

为了使实验结果更为真实，使用真实的车辆轨迹数据集进行实验。目前，有三个一线城市公开了的车辆轨迹数据集：SUVnet数据集、Geolife数据集、车辆GPS轨迹数据集等，其中规模最大的公开数据集是SUVnet数据集，其中包括近5 000辆不同类型的车辆，包括出租车、公交车、社会车辆，其运行轨迹数据连续一个多月。

原始数据逐条记录了某时刻对应车辆的位置、运行状态等信息。记录中每一列分别表示为：记录 ID标识、车辆当前位置所在经度、车辆当前位置所在纬度、车辆速度、角度，记录时间的六列为年、月、日、时、分、秒，最后两列分别为扩展状态和保留字段。此外，如果单独以车辆为单位来看，数据大约以每 30 s记录一次。选取了某市中心区域的 12.6 km×12.9 km的区域作为我们的实验区域，如图4所示。我们选取了此区域中的主次干道和比邻的比较宽的道路，制作了区域的路网图，标注出各交叉路口的信息，将路网与交叉路口信息以数据格式存储在电子地图中，作为实验研究区域，如图4所示。

图4 实验区域Figure.4 Text area

结合算法将道路环境建模称为有向图即路网图，并将数据集中的数据映射到路网图上。将无线通信的范围假设为半径相等的圆，其半径设定为200m。选取了某区域中的3996辆不同类型的车辆进行实验，区域中最大的车辆密度处为93.9辆/千米。此外，不考虑周围建筑物、绿化带等环境对无线传输的影响。

3.2 实验结果和分析

3.2.1 凸组合评估

凸组合是一类特殊的线性组合，是若干个点的某种特定意义下的非负线性组合。基于车辆自组织网络中车辆轨迹的多目标化数据传递特性与凸组合非付线性的类似性，现决定选用凸组合法去评价数据传递中多个目标传递的不稳定性。凸组合法求解多目标的马尔可夫决策过程，一般是先分析各目标的关系，指定凸组合参数，或者利用不同的凸组合参数值分别求解，通过比较获得最佳效果。设定不同的凸组合参数α的值，选择不同类型、一定数量的车辆进行实验，其实验结果如图5所示，图5中的（a）、（b）、（c）分别为V2V数据传递中α的值变化对交付率、网络开销、数据传输效率的影响。由图5可以看出，当α的值取0.9时，对应交付率高、网络开销较低、传输效率大，综合评价效果最优。

图5 V2V数据传递中α值的变化对交付率、网络开销及数据传输效率的影响Figure.5 Impact of αchange on delivery rate, network overhead and data transmission efficiency in data transmission

由于V2V的数据传递方法具有通用性，很方便地可以把V2V的数据传递方法转化为V2I和I2V的方法，OVDF法对于优化传输延迟的V2I较佳。为了进一步论证α值对交付率、网络开销、数据传输效率的影响确定性，现将TMOD F法与OVDF法进行比较试验。

实验中，设定目的节点即AP的数目为3个，按照OVDF的方案，数据包被传递到3个AP中的任何一个便视为交付成功。将TMODF法也作此设定，且不使用任何额外的基础设施来辅助数据传递，只要求数据包携带者车辆终端之间进行数据传递。两种方法均将α的值设定为0.9，观测α的值对交付率、网络开销、数据传递效率等要素的影响。

通过实验看出，目的节点的移动性会给数据传输带来更大的不确定性，在相同的车辆密度下，TMODF法获取的交付率比OVDF法获取的交付率高，TMODF法对于V2I的交付率比对V2V的交付率高。TMODF法随着车辆密度的不断提高，有更多的车辆节点能够作为中继节点协助数据传递，交付率也是不断提高，这是由于当网络中的车辆数目增加时，有更多车辆节点可以作为中继节点对数据进行转发。OVDF法只对传输延迟进行了优化，对网络开销考虑前充分。若同时考虑传输延迟和网络开销，OVDF法在传输延迟方面的优化效果要高于本研究中的多目标方案，但是，数据传递的效率也要考虑其对交付率、网络开销等指标的影响。

3.2.2 帕累托最优评估

理论上讲，不管是用凸组合法，还是帕累托最优法，其研究对象及其试验区域是一样的。在凸组合法中α的值可以有无穷多个，从无穷多个方案中选出最优的，而帕累托最优法却无法实现这样条件的选择。此外，利用帕累托最优法求解多目标马尔可夫决策方案，其需求空间较大。在利用帕累托最优法求解过程中，每次迭代选取帕累托最优决策集合，距离均值最近的点以及对应的决策予以保留，并参与下次迭代计算。每轮迭代时帕累托最优策略的数量均呈指数型增长。此外在每轮迭代还保留帕累托最优决策集合中传输延迟最小的点和网络开销最小的点。

在传递时选择使用折衷的策略进行V2V数据传递分析，并与凸组合中α值为0.9时进行比较。将多目标马尔可夫决策过程利用帕累托最优法与凸组合法在交付率、延迟时间、网络开销、数据传输效率等要素进行比较。同时，针对研究的车辆，对帕累托最优方案中保留的三个策略在各数据传递指标上进行比较，见表1。

表1 车辆数目固定的情况下三种策略的各指标比较Table.1 Comparison of indicators of three strategies when vehicle number is fixed

由表1可以看出：折衷策略相比其他两个方案在交付率和数据传递效率上都取得了较好的效果。另外，侧重于优化传输延迟所取得的效果明显优于侧重于优化网络开销效果。

4 结论

本文通过在设定试验区域内，将车辆自组织网络数据传递问题建模，选定不同类型的试验车辆并采集分析车辆历史轨迹、统计道路交通运行状况等手段，挖掘多目标马尔可夫决策过程参数，求得数据传递的最优解，利用最优解来指导真实的数据传递过程。此外，还设定了错误恢复过程对预测目的交叉路口的错误进行恢复，提高了数据交付率。最后，利用数据集验证了多目标优化数据传递方法TMODF的有效性。本文作为项目研究课题的一部分，在试验条件的界定、选取研究对象的代表性等方面难免以偏概全。另外，随着Alios操作系统、阿里云Link、5G网络、北斗导航系统(BeiDou Navigation Satellite System，BDS)、GPS、电子地图、实时道路数据、车辆运行轨迹等技术平台被广泛应用于车辆自组织网络中，以及无人驾驶汽车的推广应用，优化传输延迟、网络开销、交付率等车辆自组织网络参数，已成为数据传递中不可或缺的重要指标，这些指标的优化情况，将直接影响未来智能交通技术的应用与推广。