基于图着色和三维匹配的车联网资源分配算法

许耀华, 王慧平, 王贵竹, 朱成龙, 丁梦琴, 蒋 芳, 王 翊

(安徽大学集成电路学院, 安徽 合肥 230601)

0 引 言

近年来,互联网和蜂窝通信技术在智能交通系统中的应用越来越广泛,多数车辆都配备了传感器,可以根据服务类型的不同将数据传输到其他车辆或基础设施。在车辆密集地区,为了能在短时间内建立稳定可靠的连接,车辆对频谱资源的需求越来越大[1],但频谱资源是有限的,故需要对车联网中的频谱资源进行合理分配。在频谱资源分配的底层模式下,车辆对一切(vehicle to everything, V2X)用户可以通过资源分配[2]复用蜂窝用户(cellular user,CU)的频谱。但由于同时接入,V2X用户不可避免地会对CU造成同频干扰,故需要对频谱资源进行合理管理,使V2X用户在保证CU服务质量的前提下接入授权频谱[3]。因此,如何利用资源分配来降低干扰是车联网中一个亟需解决的问题。

在现有的车联网资源分配研究中,文献[4-5]的解决方案是对基站进行无线资源管理,无线资源管理在基站的介质访问控制层执行,并在时域中为CU和V2X用户分配频谱资源,以此来最小化 CU和V2X用户之间发生冲突的概率,并提高频谱效率和网络吞吐量;文献[6]提出一种基于地理的频谱资源调度方案,车辆根据其位置和在道路上的排序来自主选择频谱资源,其目标是通过协调车辆之间的子信道选择来降低数据包的冲突,所提方案显著改善了由于数据包冲突而导致的数据丢失问题;文献[7]研究了CU和V2X 用户在未授权频谱上的共存问题;文献[8-10]考虑了CU和V2X用户的一对一复用,在此复用模式下,V2X用户对CU造成的干扰较低,但是频谱利用率不高;在文献[11-12]中,单个CU的频谱资源可以同时被多个V2X用户复用,此时的频谱利用率较高,但仅仅考虑了CU和V2X用户之间的信道匹配,并未考虑到CU、V2X用户以及资源块(resource block, RB)这三者之间的信道分配;文献[13]考虑到了车辆对基础设施(vehicle to infrastructure, V2I)链路、车辆对车辆(vehicle to vehicle, V2V)链路以及RB这三者之间的信道分配,该文献将互干扰严重的V2V链路划分成簇并通过三维匹配算法进行了无线资源匹配,从而获得了网络吞吐量最大的资源分配方案。但该方案在V2V簇划分过程中,对簇内首条V2V链路的选择是随机的,这导致V2V簇划分不稳定,严重影响分配方案的最终结果。将图着色法用于分簇问题在文献[14]中已经被证明是可用的,使用图着色法进行V2V链路分簇可以解决上述问题。

本文在文献[13]的研究基础上提出一种基于图着色和三维匹配的车联网资源分配算法,建立以最大化V2I链路总和速率、保障V2I服务质量要求为目标的分配优化问题。所提算法利用图着色法对V2V链路进行分簇,并使用三维匹配算法进行信道分配,在保证V2I链路服务质量和V2V链路接入率相对平衡的前提下提升了V2I链路总和速率,并使系统在迭代次数相对较少的情况下收敛到最优。

1 系统模型

考虑一个支持设备到设备(device to device, D2D)的车联网通信场景,其中存在M辆进行V2I通信的车辆和N对以D2D通信形式进行本地数据交换的V2V通信链路,如图1所示。为了简化系统,假设所有的车辆在同一时间只能进行V2I通信或V2V通信。将V2I链路集表示为M={1,2,…,M},V2V链路集表示为N={1,2,…,N},其中M≪N。假设频谱资源被分成F个RB,表示为F={1,2,…,F},且M=F。为了提高频谱利用率,分配给V2I链路的上行资源被V2V链路正交复用,且多个V2V链路可以同时复用同一V2I链路的频谱资源。为了控制干扰,每个V2I链路只能正交占用一个RB。

图1 系统模型Fig.1 System model

车辆的快速移动使得系统模型中的小尺度衰落参数发生变化,如果将小尺度衰落参数传送给基站,会造成信息开销增大和时延增加,故在高速移动场景中捕捉瞬时的信道状态信息是不切实际的。本文假定基站能够获得变化缓慢的大尺度衰落参数和小尺度衰落参数的统计特性。

(1)

表1 信道增益符号表

(2)

(3)

(4)

(5)

2 问题建模

给定一组可用RB,以V2I链路的总和速率最大化为目标,同时保证V2I链路的最低通信服务质量和V2V链路的可靠性,将车辆通信问题建模为一个优化问题:

(6)

(6a)

(6b)

(6c)

(6d)

(6e)

(6f)

(6g)

(6h)

3 基于图着色和三维匹配的资源分配算法

基于图着色和三维匹配的资源分配算法由3个步骤实现。第1步,V2V链路分簇;第2步,功率控制;第3步,三维匹配算法。具体流程如图2所示。

通过构建干扰图来表示通信链路之间的干扰。首先,通过干扰图得到链路之间的干扰情况,利用图着色法对V2V链路进行分簇,得到V2V链路簇集;其次,对V2I链路和V2V链路进行功率控制,得到相对较佳的发射功率;最后,利用三维匹配算法解决V2I链路、V2V链路簇集、RB三者之间的信道分配问题。

图2 算法流程图Fig.2 Algorithm flowchart

3.1 V2V链路分簇

本文算法通过V2V链路之间的干扰构建干扰图G=(V,E),顶点集V包括每个V2V链路(每个V2V链路代表一个顶点,顶点位置位于V2V链路连接发射端和接收端的中点),v={vj,j=1,2,…,N}。E(G)表示使用相同频谱资源时图G中顶点之间的干扰边矩阵,表示为N×N的矩阵,E(G)={ei, j,i=1,2,…,N;j=1,2,…,N},ei, j∈{0,1},其中ei, j=1表示第i条V2V链路vi和第j条V2V链路vj之间存在不可忽略的干扰且两顶点之间存在相连的边。在这种情况下,vj是vi的邻居,并将vi、vj分别加入vj和vi的邻居集interfi、interfj中。由于强干扰,同一RB不能分配给两个相邻的通信链路。这类似于顶点着色问题,其中由同一条边连接的两顶点不能着相同颜色。因此,当一组顶点被涂上相同颜色时,表示允许使用相同的RB。

3.1.1 干扰图的建立

步骤 1初始化干扰图,随机放置N条V2V链路;

3.1.2 V2V对的分簇

按照上述方法,可以将V2V链路间的干扰关系映射为干扰图,基于此,可以将V2V链路分为若干个不相交的簇。本文采用图着色法对V2V链路进行分簇。具体算法如算法1所示。

算法1 基于图着色的分簇算法1:初始化:根据第3.1.1节构建干扰图,并计算每个顶点的饱和度;2:顶点着色While 存在未被染色的顶点 for count=1:f if 顶点vi的饱和度∑Nj=1ei,j的值最大 vi=count if vj∉interfi vj=count else count=count+1 end if end if end for end while

由以上两步得到V2V链路分簇结果,将划分到同一簇的V2V链路看作一个整体,不同簇间复用不同的频谱资源,故不在同一簇的V2V链路之间将不会产生干扰。

3.2 功率控制

为了实现更高的V2I链路总和速率以及保证V2V链路的服务质量,需要合理控制V2I链路及V2V链路的发射功率。

假设分配给第m条V2I链路的频谱资源f被第k个V2V链路簇集Ck复用,故目标函数式(6)变为由式(7)组成的方程组:

(7)

(7a)

(7b)

(7c)

式(7a)化简得到

(8)

假设所有V2V链路都满足信道要求,将式(8)取等号得到

(9)

(10)

(11)

3.3 信道分配

图3 三维匹配图Fig.3 Three-dimensional matching map

在上述 V2I-RB-V2V链路簇集的加权三维匹配算法求解过程中,构建三维均匀超图的时间复杂度为O(M3),加权三维匹配算法的时间复杂度为O(M5logM)。此外,基于着色的V2V链路分簇的时间复杂度为O(N2)。因此,本文所提算法的总的时间复杂度为O(c(NM3+M4N+M6NlogM)),其中c为迭代次数。此外,基于迭代的频谱分配算法的时间复杂度为O(c(M2N2+M3N+M4N)),文献[13]所提算法的时间复杂度为O(c(M2N2+M4N+M6NlogM))。

4 仿真结果及分析

4.1 实验条件和仿真设置

本文利用Matlab仿真平台对上述提出的基于图着色和三维匹配的资源分配算法进行仿真。仿真环境根据第三代合作伙伴计划(3rd generation partnership project, 3GPP)组织的TR36.885设置。具体参数见表2。

仿真针对图1所示的公路场景,假设车辆的到达服从泊松分布,车辆之间的平均距离为2.5倍车速。信道模型为基于WINNER Ⅱ信道模型建立的V2V和V2I信道模型,基站位于蜂窝区域的中心,来进行消息的接收和发送。

表2 仿真参数

4.2 仿真结果及分析

基于表2的参数设置进行仿真,本文将基于图着色和三维匹配的资源分配算法与基于迭代的频谱分配算法、文献[13]中基于三维匹配的随机频谱分配算法进行对比,关注V2I链路总和速率、V2V链路接入率等性能指标,对比不同发射功率、车辆速度、V2V链路数量和迭代次数下的V2I链路总和速率。

图4展示了活跃V2V链路数量对V2I链路总和速率的影响。从图4中可以看到,随着V2V链路数量的增加,3种算法的V2I链路总和速率都会降低。这是因为,随着V2V链路的增加,复用相同链路资源的V2V链路数量增加,这将对V2I链路产生更多干扰,进一步降低了V2I链路的接收信干噪比。此外,从容量曲线的陡峭斜率可以看出,对比算法对V2V链路的增加非常敏感,而基于图着色和三维匹配的资源分配算法的容量曲线斜率相对平缓。分析原因可知,在这些情况下,V2V链路对V2I链路产生的干扰非常严重,并且V2I链路总和速率受到很大影响,从而性能降低。而在V2V链路数量较多时,本文所提算法通过牺牲V2V链路的接入率换取信干噪比允许范围内V2V链路的可靠性,对V2I链路总和速率的影响相对较低。

图5展示了不同迭代次数下基于图着色和三维匹配的资源分配算法和对比算法的V2I链路总和速率性能,其中迭代次数不断增加,以更新V2V聚类。从图5可以看出,本文所提算法迅速收敛到次优解,并且不会随着迭代次数的增加而改善,而对比算法则在本文所提算法达到次优解时还保持增长,最终收敛到稳定的解决方案。这表明所提出的算法能在较少的迭代次数下提升性能并最终收敛到次优解。这是因为文献[13]算法在对V2V链路进行簇划分的过程中,簇内的第一条V2V链路是随机选择的,而基于迭代的频谱分配算法的RB是随机分配的,需要经过较多次迭代才能达到稳定。

图4 V2I链路总和速率与V2V链路数量的关系Fig.4 Relationship between the sum rate of V2I links and the number of V2V links

图5 V2I链路总和速率与迭代次数的关系Fig.5 Relationship between the sum rate of V2I links and the number of iterations

图6表示不同发射功率下的V2I链路总和速率与汽车速度之间的关系。如图6所示,随着车速的加快,3种算法的V2I链路总和速率都在下降,这是由于车速的增大使得车辆之间的安全距离增大,为了保证V2V链路的可靠性,负责V2V通信的车载终端只能增加发射功率来提高V2V链路的可靠性,V2V链路功率增加导致V2V链路对V2I链路的干扰增加,使得V2I链路的速率减小,最终造成V2I链路总和速率下降。本文所提算法的性能优于其他两种算法,这是由于使用三维匹配算法带来了更优的匹配灵活性。

图7为3种算法的V2V链路成功接入率。文献[13]算法和基于迭代的频谱分配算法的V2V链路接入率始终为100%,而本文所提算法的V2V链路接入率随着V2V链路的增加而降低。这是因为两种对比算法只简单地考虑了所有V2V链路都能复用V2I链路频谱资源的情况,并未考虑到当一些信道条件较差的V2V链路复用V2I链路频谱资源时,会降低V2I链路的服务质量。而本文所提算法更好地平衡了V2I链路服务质量和V2V链路接入率。

图6 V2I链路总和速率与车辆速度的关系Fig.6 Relationship between V2I link sum rate and vehicle speed

图7 V2V链路成功接入率与V2V链路数量的关系Fig.7 Relationship between the successful access rate of V2V links and the number of V2V links

图4～图6对比了各资源分配算法的V2I链路总和速率。由对比结果可以发现,所提算法的V2I链路总和速率明显优于基于迭代的频谱分配算法和文献[13]所提出的算法,但在网络中V2V链路数量较多时,本文所提算法的V2V链路接入率略差。

5 结 论

本文考虑到车联网通信场景中上行通信链路的资源分配问题,为了优化V2I链路的总和速率,解决V2V链路复用V2I链路产生的干扰,提出一种基于图着色和三维匹配的车联网资源分配算法。该算法通过图着色法对V2V链路进行分簇,通过求解V2I链路和V2V链路的发射功率,将优化问题转化为V2I链路、V2V簇和RB之间的三维匹配问题,并利用三维匹配算法进行求解。理论分析及仿真结果表明,该算法在很大程度上提高了V2I链路总和速率,并加速了算法收敛性。后续研究重点在于如何在提高V2I链路总和速率的同时,保持V2V链路的百分百接入率。