一种多接口多信道VANET动态频谱分配算法研究*

孙智乐，李德敏，陶 冰，刘 潇

（1.东华大学 信息科学与技术学院，上海201620；2.数字化纺织服装技术教育部工程研究中心，上海201620)

一种多接口多信道VANET动态频谱分配算法研究*

孙智乐1，2，李德敏1，2，陶 冰1，2，刘 潇1，2

（1.东华大学 信息科学与技术学院，上海201620；2.数字化纺织服装技术教育部工程研究中心，上海201620)

为了实现多接口车载自组织网络(VANET)车辆节点之间通信频谱的动态分配，提出了一种基于信道反馈的动态频谱分配算法。在图论着色模型的基础上，分析信道的质量情况，定义了信道反馈矩阵，车辆节点可以根据信道反馈矩阵中元素的值来自主选择可用信道，从而实现了信道的最大化利用。通过软件仿真比较，可以看出该算法实现了频谱的动态分配，在兼顾最大化系统总收益的前提下大幅度减少了算法的时间开销，显著提高了多接口多信道VANET的网络性能。

多接口；车载自组网；图论着色；信道反馈；频谱分配

0 引言

车载自组网(VANET)作为智能交通系统(ITS)的重要组成部分引起了学术界和工业界的广泛关注[1]。且随着无线射频收发器硬件成本的降低，采用多射频多信道的车载自组织网络在未来具有很大的发展潜力。多接口VANET中一个关键问题就是频谱的动态分配。对于车载网络，美国联邦通信委员会(FCC)将 5.850～5.925 GHz之间75 MHz的频段用于车载通信，其被分成 7个子信道[2]。通过对车载自组网中有限的频谱资源进行动态分配，从而降低了车辆节点由于竞争信道资源而产生的冲突，提高了车载网络的吞吐性能，因此，研究多接口多信道VANET动态频谱分配算法具有重要意义。

1 相关工作

车载自组织网络拓扑频繁变化，导致固定频谱分配技术不能用于车载网络。于是人们开始考虑对频谱进行动态分配。

文献[3]是一种集中式频谱分配方案，认为频谱分配问题就是寻求在射频数目受限的前提条件下最小化网络干扰函数的问题，频谱分配集中控制设备可能成为计算瓶颈，且算法复杂度高，在车载自组网中难以实现。文献[4]是一种集中式频谱分配方案，提出了 CSGC算法。它是一种以最大化系统总带宽为目标的颜色敏感图论着色算法。但是实现时迭代次数多，且随着主用户和次用户数目的增多导致系统规模增大，其分配效率也会降低。文献[5]是一种分布式频谱分配方案，提出了RAND算法。它是一种分布式随机化算法。各用户对其可用的信道产生一个随机数，通过与其他用户比较随机数大小而决定信道的分配，但是在系统总带宽性能上，较其他算法差距较大。

本文针对有限的频谱资源中车辆用户抓住机会使用空闲信道问题，在图论着色算法模型的基础上，提出了一种基于信道反馈的动态频谱分配算法（Channel Feedback Spectrum Allocation，CFSA)，其是一种分布式实现的算法，有效解决了上述三种方案运用在车载自组网中的不足之处，经过仿真分析，性能明显优于上述方案。

2 模型描述

动态频谱分配问题的基本出发点是：在不影响授权频段的正常通信下，具有认知功能的无线通信设备可以按照某种“机会方式”接入授权的频段范围，并动态地利用频谱。整个频谱池又可划分为若干个子信道。图1描述了一个瞬时的频谱池，它反应了车载自组网中车辆用户在某一时段可利用频谱的特征。

图1 频谱池模型

多接口车载自组网络拓扑结构是动态变化的，为方便算法描述，作如下假设：

(1)上述频谱池中可用频谱被划分成 K个可用频谱带，即K个信道。每个信道的带宽和传输范围相同，且相互正交。

(2)系统中随机分布着M个车辆节点，对∀m，m∈M配备有不同的射频数目，令Mi表示节点i的射频数目，系统中车辆节点在满足信道分配规则的前提下，可以同时使用多个信道K，且满足Mi≤K。

(3)对于需要通信的车辆节点，通信双方必须各自选择一个射频接口，并且使双方的射频接口切换到相同的信道上。

(4)本文不考虑功率控制因素，假设所有的车辆用户都使用相同的功率，且每个车辆节点在各个信道上的干扰半径相同。

由于图的着色算法已经被广泛地应用于频谱的动态分配上，它是一种成熟的模型。因此图论着色模型的数学定义可以由距离矩阵、空闲矩阵、干扰矩阵、有效分配矩阵表示。

矩阵D为距离矩阵，用于描述车载自组网中车辆节点之间的距离，其是一个 M×M矩阵，其定义如式(1)所示：

其中，dij为车辆节点i与 j之间的距离。

矩阵L为空闲矩阵，其是一个M×K矩阵，表征信道有效性。代表车辆节点是否可用该信道，如果车辆节点m可以用k信道，则 lm，k=1，否则lm，k=0。如式(2)所示：

矩阵B为干扰矩阵，其是一个M×M×K矩阵，代表车辆节点i和车辆节点j在信道k上存在干扰。如式(3)所示：

这些干扰是特定的，两个车辆节点在一个信道上是否相互干扰取决于它们之间的距离，不代表在另一个信道上仍受干扰。

矩阵S为有效分配矩阵，它是一个M×K矩阵，如果信道k分配给了车辆节点 m，则Sm，k=1，否则Sm，k=0。如式(4)所示：

其中 S满足所有干扰矩阵 Λ定义的限制条件，Si，k＋Sj，k≤1，如果 λi，j，k=1，当且仅当∀i，j＜M，k＜K。可以知道，满足上述条件的S矩阵很多，故令QM×K代表有效频谱分配矩阵集。

3 动态频谱分配算法设计

车载自组网中车辆与车辆之间的拓扑变化很快，使得通信链路不能及时建立。而车辆节点在选择可用频段时，必须有一个衡量标准作为选择的依据。本文提出的CFSA算法，根据信道反馈的实时性从而实现频谱合理有效的分配。

3.1 车辆射频接口状态

所有车辆节点的射频数目是不确定的，为了充分利用频谱资源，本文首先为射频接口定义了三种状态。

(1)忙状态。如果该射频正在发送业务，称该射频在忙状态。

(2)空闲状态。如果该射频没有发送业务，称该射频处在空闲状态。

(3)假空闲状态。如果一个射频接口正在发送业务，但车辆节点通过空闲时的监测得知该射频当前工作的信道反馈值小于设置的信道反馈阈值 CFT(Channel Feedback Threshold)，而此时节点又没有其他空闲的射频，为了保证通信业务的质量，假设该射频目前处于空闲状态。

3.2 信道反馈

确定了车辆节点的射频接口状态，为方便算法描述，建立如下结构。

(1)将上述图论模型的数学描述抽象成一个无向图G=(V，E，L1)，如图2所示。其中，V={vm|m=1，…，M}表示顶点的集合，每个顶点代表参与信道分配的车辆用户，包括车辆节点当前可用信道的集合；E={eij|i，j=1，…，M}表示边的集合，代表相邻两个车辆节点在某一个信道k上存在干扰。因已假设了各车辆用户在各个信道上的干扰半径相同，若车辆 i，j的干扰范围不出现重叠，则 eij= 0，否则 eij=1；而 L1表示车辆顶点可选信道颜色的集合，每个可用信道被看作不同的颜色，可选颜色由信道有效矩阵 L决定，当且仅当 lm，k=1时，车辆节点可以使用当前被着色的信道。

图2 VANET中频谱分配模型

(2)由于信道k在某一时段可能被不同的车辆用户占用，即一个信道上的车辆邻居数目是不定的，如果按照文献[3]中CSGC算法进行频谱分配，就会增加无线控制信道的流量。因此本文考虑信道反馈因素，定义了信道反馈矩阵，将可用信道分配给吞吐量利用率最大的车辆用户。

矩阵R为信道反馈矩阵，它是一个M×K阶矩阵，用来描述各车辆节点在给定的频谱分配条件下，车辆用户在可用信道上所获得的最大通信容量，可以是最大带宽或者最大吞吐量。其公式如式(5)所示：

信道反馈矩阵R中各元素的取值采用文献[6]中的方法进行计算，其目标就是最大化信道吞吐量，其公式如式(6)所示：

其中bm，k表示车辆用户m在信道k上能够产生的最大带宽，Cm，k为车辆用户m在信道k上的邻居数目。根据信道反馈矩阵的值，当信道吞吐量最大时，其信道k即为当前车辆用户选择的最优信道。

(3)针对车载自组网的时变特性，网络拓扑和信道的可用性均随着时间不停地变化着，为了使每个可用信道的吞吐量达到最大，在频谱分配时定义了最大化带宽准则，如式(7)所示：

其中 sm，k为有效分配矩阵，bm，k为车辆用户 m在信道 k上产生的带宽。

上述算法的主要思想是在满足干扰条件的前提下，利用现有的图论着色模型，提出信道反馈的概念，让车辆用户根据信道反馈的值来进行信道选择。其目标就是使车辆用户最大公平地接入信道，获得最大的带宽。

3.3 算法实现流程

算法的初次分配流程与文献[3]中 CSGC算法类似，算法每次迭代将选出拥有最大信道反馈值的车辆用户，其算法流程图如图3所示。

CFSA频谱分配算法流程图如图3所示，核心思想就是优先选出最有价值的信道分配给车辆节点，即让吞吐量利用率最大的车辆用户接入该信道。

图3 算法流程图

4 仿真与分析

为了验证算法的有效性，本文利用MATLAB对算法进行仿真，并针对VANET网络中频谱分配算法的时间开销、系统最大收益和其他常用算法进行比较。

4.1 仿真场景

本文的模拟场景是在800 m×800 m的矩形区域中随机分布5～40个车辆节点，车辆节点均配备8个射频接口，信道数为 20，车辆通信半径为 100 m，干扰半径为300 m，具体仿真参数如表1所示。

表1 仿真参数表

4.2 性能比较与结果分析

图 4可以看出，当频谱数量固定时，取k=20，可以看出CSGC的时间开销最大，并且随着车辆节点数量的增多，本文提出的CFSA算法在时间开销上明显小于CSGC算法和RAND算法。由于本文提出的算法是在CSGC算法初次分配的基础之上继续分配，以兼顾系统最大吞吐量换取了时间开销的减少，图5表示CFSA算法在系统总收益上明显高于CSGC算法和RAND算法。

5 结束语

本文提出的一种基于信道反馈的动态频谱分配算法CFSA，让车辆用户根据反馈矩阵的值来最优选择信道，解决了CSGC分配算法只是针对静态网络的问题，最后对CFSA算法进行了仿真和分析。仿真结果表明，CFSA算法在兼顾系统总收益的基础上减少了时间开销，降低了算法运行的迭代次数，显著提高了网络的性能。

Research of dynamic spectrum allocation algorithm for multi-radio multi-channel VANET

Sun Zhile1，2，Li Demin1，2，Tao Bing1，2，Liu Xiao1，2
（1.School of Information Science&Technology,Donghua University，Shanghai 201620，China；2.Engineering Research Center of Digitized Textile&Fashion Technology，Ministry of Education Donghua University，Shanghai 201620，China）

In order to achieve dynamic allocation of communication spectrums between the vehicle nodes in multi-radio VANET,a dynamic spectrum allocation algorithm based on channel feedback is proposed.This paper analyzed the quality of channel，defined channel feedback matrix.The vehicle nodes could select available channel according to the values in channel feedback matrix.So as to realize the maximization of channel utilization.Through software simulation,it can be seen that this algorithm reduces time overhead significantly under the precondition of the maximize system total revenue and significantly improves the network performance of multi-radio multi channel VANET.

multi-radio；VANET；graph coloring；channel feedback；dynamic spectrum allocation

TN929

：A

：0258-7998(2015)03-0090-03

10.16157/j.issn.0258-7998.2015.03.023

国家自然科学基金 (71171045),上海市科委保密专项项目（11JG0500300）