V2V通信中基于超图理论的资源分配算法

张家波，吴昌玉，袁 凯

(重庆邮电大学 通信与信息工程学院，重庆 400065)

0 引 言

车与车(vehicle to vehicle，V2V)通信在改善交通安全性，交通效率和道路服务质量等方面发挥了重要作用[1]。在动态且密集的交通环境下，车辆周期性地向邻近车辆广播合作意识消息(cooperative awareness message，CAM)，例如车辆的转向、位置、速度等，提高了车辆之间相互感知的能力，并在很大程度上减少了因驾驶人员的视线盲区所造成的安全隐患，从而避免交通事故的发生[2]。

干扰是无线通信系统中的固有现象[3]。由于无线信道的广播特性，每当多个发射机在同一频带中同时广播时，就会对其它接收机产生干扰。目前基于长期演进车对车(long term evolution-vehicle to vehicle，LTE-V2V)下的资源分配研究还存在不足[4]。在文献[5]中，作者通过车辆聚类将资源分配问题转换为二分图的最大权重匹配问题以最大化系统总容量。文献[6]为限制累积干扰，提出了基于矩阵谱半径估计理论的资源分配方案，该方案将可靠性要求转换为矩阵谱半径的约束，最大化同时传输的链路数量。文献[7]提出了基于车辆地理位置的资源分配方案，该方案将小区的覆盖区域划分若干区域，并为每个区域分配一组专用资源，从而实现资源的重用。在文献[8]中，作者首先根据车辆行驶方向划分资源池，然后基于能量感知在给定的资源池里选择传输资源，减少了资源冲突和带内发射对车辆间的潜在干扰。文献[9]提出了基于动态地理的资源选择算法，通过资源池的划分提高资源的利用率，然而该方案需要许多参数设置，其影响尚未在文献中得到很好的研究。

针对现有文献中V2V广播通信中集中式资源调度算法较少考虑半双工约束和累积干扰的问题，提出了一种低复杂度的超图着色资源分配算法。仿真结果表明，该算法能进一步减少更新时延，并提高数据包接收率。

1 系统模型及问题描述

1.1 系统模型

在城市道路场景下，车辆周期性(100 ms)生成CAM消息，并发送给邻居车辆,如图1所示。

图1 V2V广播通信场景

为确保安全信息传输的可靠性，V2V通信使用专用资源池进行资源分配[10]。专用资源池在时域上分为100个子帧(每个子帧1 ms)，频域上分为50个资源块(resource block，RB)，每个数据包所占用的RB数量由传输的调制与编码策略(modulation and coding scheme，MCS)决定[2]。如图2所示，资源池中资源主要被用于传输CAM数据包以及调度分配(scheduling assignment，SA)信息，CAM数据包传输所用资源主要通过SA进行传输。如果车辆在一个子帧中充当接收车辆(RX)，则不能在该子帧中充当发送车辆(TX)[3]。

图2 资源池

在密集的网络拓扑中，主要存在两个问题：①频率复用带来的干扰，当多个TX在发送数据包时选择相同资源时，会对共有的一跳邻居车辆产生严重干扰，例如图1的TX1和TX2对RX1/RX2的干扰。②半双工约束[11]，彼此处于一跳范围内的车辆预定在相同的子帧里进行广播，如图1中TXj和TXk在同一子帧下广播消息，则彼此间接收不到对方的消息。

1.2 问题描述

RXm在第 (t,f) 个时频资源中从TXj处接收到的信干噪比(signal to interference plus noise ratio，SINR)表示为

(1)

本数据包的数量，一个传输周期内成功解码数据包的数量表示为

(2)

(3)

(4)

(5)

(6)

式中：dj,j′表示TXj与TXj′的距离，式(4)表示由于半双工的性质，彼此通信范围的内的任何车辆不能同时在一个子帧内作为TX，式(5)表示车辆只能占用一个时频资源。

2 资源分配算法

式(3)中给出的优化问题是NP难组合优化问题，穷举法是解决优化问题的直接方法，但是该算法具有很高的计算复杂度，为了在计算复杂度与数据包接收率之间实现适当的平衡，本文基于超图着色算法对其进行求解，以实现次优解。

2.1 干扰超图的建立

在传统的动态调度中，资源分配可能导致显著的延迟，因为用户需要针对每个数据包向基站发送资源请求消息。为了减少UL等待时间以及减轻基站负载，基站进行集中式的半静态调度(semi-persistent scheduling，SPS)。基站在一个或多个传输周期组成的每个SPS周期的开始处将预定义的资源分配给用户，资源分配方案在SPS周期的每个传输周期内保持不变[13]。为了充分利用基站获得的全局位置信息，基站在每个SPS周期的开始处构建干扰超图，并确定TX-RX在资源池的分配。

为了减轻频率复用带来的干扰，必须要让复用相同资源且传输不同数据包的发送车辆相距一定的距离。当不同的TX之间选择相同资源发送数据包时，主要干扰是TX对其余V2V链路的RX的干扰，如图3所示。

图3 V2V广播群距离

为降低计算复杂度，本文进行简化分析，仅考虑距离损耗对信号传输的影响[3]，考虑最差的情况，即在传输范围内发送车辆前方与之具有最小信道增益的接收车辆，以及在发送车辆后方与之具有最小信道增益的接收车辆，将其与发送车辆视为两个V2V通信组。

传统图的构建中，连接两个顶点的边缘不足以模拟无线网络中的干扰，因为一些弱干扰源可能构成强烈的累积干扰源以影响链路质量。因此，本文通过超图原理进行干扰建模，关于超图的相关概念可以参见文献[14]。

干扰超图的建立主要分为以下3个步骤：

(1)相邻车辆列表。因为两跳传输范围内的车辆如果复用同一资源会对共有的一跳邻居车辆产生严重干扰，所以车辆i两跳传输范围内的车辆都会进入其相邻车辆列表，在两跳传输范围以外，车辆j会进入车辆i的相邻车辆列表,如果满足式(7)或者式(8)

(7)

(8)

式中：η1是车辆i选择相邻车辆的门限值，这一步主要是为了排除对车辆i的干扰完全可以忽略的车辆，具体如图4(a)所示。其中Hi,k1和Hi,k2分别表示第i个广播群中TX在发送范围内与两个接收车辆k1和k2之间的信道增益，Hj,k1和Hj,k2分别表示第j个广播群TX到第i个广播群的第k1个和第k2个接收车辆的信道增益。

(2)独立干扰者。在邻近车辆列表中寻找独立干扰者，车辆i两跳传输范围以内的车辆都作为其独立干扰者构建普通边，车辆i两跳传输范围以外的相邻车辆会作为车辆i的独立干扰者，如果满足式(9)或者式(10)

(9)

(10)

式中：η2是超图构建普通边的门限值，这一步的主要作用是为了构建对车辆i有过大干扰的车辆。一跳邻居用实线连接，一跳邻居外用虚线连接，如图4(b)所示。并把与i构建普通边的车辆在i的相邻车辆列表中去除。

(3)累加干扰者。在剩余的相邻列表中寻找累加干扰者并构建超边，剩余的相邻车辆会作为车辆i的累加干扰者，如果满足式(11)或者式(12)

(11)

(12)

式中：η3表示累加干扰的门限值，为了简化，Nm值取2，也就是只考虑3个顶点的超边,如图4(c)所示。最后形成的干扰超图如图4(d)所示，具体算法见表1。

图4 干扰超图构建

表1 超图构建算法

2.2 超图着色

2.2.1 二重着色

在上述构建的干扰超图中，考虑以下两种通信干扰：

(1)直接冲突：一跳邻居范围内的TX分配了相同的子帧。(半双工约束)

(2)间接冲突：在彼此干扰范围内TX分配了相同的子帧和子信道。

为TX分配信道和子帧的问题可以转换成图顶点着色问题，将为顶点分配时频资源看作为分配两种颜色，从而将资源分配问题转化为顶点二重着色问题，对应关系见表2[15]。

为定量描述着色冲突，V={v1,v2,…,vN} 表示N个顶点，ti表示vi选择的主色，fi表示vi选择的副色，si=(ti,fi) 是顶点vi的着色方案，S={si|i=1,2,…,N} 表示整个顶点干扰图的着色方案。如图5所示，单跳邻居范围内的车辆由实线相连，相互干扰范围内车辆由虚线相连。将每个顶点分成两半，左边表示主色，代表为发送车辆分配的子帧，右边表示副色，代表为发送车辆分配的子信道。为干扰超图分配颜色时，由实线连接的两顶点必须主色不同，虚线连接的两顶点则必须主色或副色不同[3]。

表2 子帧和信道的分配与顶点二重着色问题的对应关系

图5 信道子帧分配示例

2.2.2 基于超图的二重着色算法

超图构建后，为超图H着色，处于同一超边的顶点至少有两个顶点被分配不同的颜色，以这种方式减轻累积干扰，算法中相关名词定义请参见文献[14]。算法的基本思路：首先根据图中顶点的mono-degree将超图H分解，然后从分解的H中得到顶点的排序，最后基于点排序的相反顺序为对应顶点着色。区别于贪心算法的求最小颜色数，根据调度方式以及信标消息的周期性，时频资源的数量是固定的，因此为了使每个资源能得到合理的使用，从可用的颜色集合里随机选择一个颜色进行着色，在最差的情况下，如果没有可用的颜色，则选择这样的一个颜色，在这个颜色上，待分配节点离正在使用这个颜色的最近节点的距离最大，如式(13)所示

C(i)=argmaxk(minj∈NkDij)

(13)

式中：C(i) 表示节点i的资源选择，Dij表示车辆i与车辆j之间的距离，这个资源给出了它和其它共享该资源的对等体之间最好的距离，具体算法见表3，基站半静态资源调度见表4。

3 仿 真

使用文献[16]设计的LTEV2Vsim模拟器进行仿真，并考虑文献[17]中定义的道路模型，如图6所示。现有的资源管理方案将可靠性要求直接转换成SINR约束，即SINR应该大于给定的目标值。在LTE中的不同的MCS下，保证可靠性要求的SINR阈值也是不同的。本文分别就MCS=4，8时进行仿真分析，仿真参数见表5和表6，RB-C表示传输一个CAM消息需要的RB数量，NR表示一个周期内的资源数量。

表3 基于超图的二重着色资源分配算法

表4 基站半静态资源调度

图6 道路撒点模型

通过将本文提出的基于超图理论的二重着色算法(hypergraph based)与基于矩阵谱半径算法(matrix spectral radius)和基于地理位置算法(geographic based)对比。为了评估CAM传输时的通信质量，主要考虑以下两个参数：

表5 系统仿真配置

表6 LTE-V调制和编码方案及相应的值

(1)数据包接收率：场景中所有接收节点从数据源节点正确接收数据包的数量，与所有发送节点发送数据包的比值。具体表示为

(14)

式中：PRR表示数据包接收率，Nneighbors表示场景中所有车辆的邻居数量之和。Nsuccess表示场景中车辆节点成功接收数据包的数量。

(2)数据包更新时延：车辆节点正确接收信标的时间差，具体表示为

tu=tn+1-tn

(15)

式中：tu表示更新时延，tn+1表示车辆节点第n+1次正确接收数据包的时刻，tn表示车辆节点第n次正确接收数据包的时刻。通过更新时延的累积分布函数(cumulative distribution function，CDF)评估通信等待时间。

图7和图8分别就MCS=4，MCS=8时，比较了3种算法中发送车辆传输距离之间的关系与数据包接收率的关系。从图7和图8中可以看出，MCS=8时的PRR相比MCS=4时的PRR更高，因为在不同的MCS下，可分配的资源数以及保证可靠性要求的SINR阈值也是不同的。当MCS的值固定时，随着TX传输距离的逐渐增加，收发车辆传输范围内会有越来越多的其它TX对RX产生干扰，从而导致数据包接收率也逐渐降低，因此可以推出在MCS值固定时，距离对数据包接收率带来负向的影响。分析以上仿真结果，在所有情况下，Geographic算法基于车辆的地理位置复用，未充分考虑用户间的干扰影响，数据包接收率最低。Matrix spectral radius算法可以改善系统PRR性能，但是Hypergraph算法的数据包接收率大于Matrix spectral radius算法，因为Hypergraph算法相较于Matrix spectral radius算法在考虑累积干扰的同时，还考虑了半双工约束带来的数据包丢失。

图7 当MCS=4时，数据包接收率对比

图8 当MCS=8时，数据包接收率对比

图9和图10比较了MCS=4，MCS=8时，r=100 m时3种算法的数据包更新时延的CDF，从图中可以看出，MCS=4时，Hypergraph算法的更新时延在0.2 s以内已经达到99%，保证了较低的通信延迟。Matrix spectral radius算法在0.7 s达到了99%，Geographic在0.8 s内达到了99%。MCS=8时，Hypergraph算法依旧保证了较低的通信延迟，更新时延在0.2 s以内已经达到99%，Matrix spectral radius算法在0.5 s达到了99%，Geographic在 0.7 s 内达到了99%。这些结果表明了Hypergraph算法保证了较低的连续错误发生的概率。

图9 更新时延的CDF(MCS=4，r=100 m)

图10 更新时延的CDF(MCS=8，r=100 m)

4 结束语

本文主要针对高密度的交通环境下资源分配问题，提出了一种基于超图理论的资源分配算法。该算法中将超图理论和二重着色结合，降低了累积干扰带来的影响，并减少了半双工约束导致的数据包丢失。仿真结果表明，基于超图理论的算法可以在通信范围内提高数据包的接收率，并保证了较低的连续错误发生的概率。

本文研究是基于单小区场景下的资源分配，在多小区场景下，为了避免基站覆盖范围边缘车辆受到干扰，邻近基站需要知道彼此的资源分配结果，通过基站之间的协调从而更加合理的利用资源。