认知无线车载自组织网络中的联合路由调度

1 (武汉大学计算机学院武汉 430072) 2 (武汉理工大学计算机科学与技术学院武汉 430070)

摘要 通过将认知无线电(cognitive radio, CR)技术应用到车载自组织网络(vehicular ad hoc networks, VANETs)(也称车联网)中，认知无线车载自组织网络(CR-VANETs)可以缓解频谱资源稀缺问题，有效提高车对车通信的频谱资源利用率.由于车辆的高速移动性以及认知无线电频谱资源的动态特性，使得传统的认知无线电网络或车载自组织网络中的路由协议无法直接应用到CR-VANETs中.目前，针对CR-VANETs的路由研究相对较少，如何最大效率地利用有限的频谱资源，同时降低跳数过多带来的频谱资源浪费，仍然是一个有待解决的问题.为此，提出了一种CR-VANETs中联合路由调度方案，结合了有限频谱资源调度研究与最小化路由跳数的优化目标.首先，建立了CR-VANETs中的网络模型和基于车对车通信的频谱感知模型，预测车辆间有效接触时间和频谱可用概率.其次，通过这些参数定义出通信链路消耗，并由此得出权衡链路质量的权重因子.通过分析优化目标，将其转化为有限频谱资源约束下的最小化路由跳数问题，并证明该问题为NP难问题.然后，针对这个联合路由调度问题提出一种混合启发式算法，结合了粒子群优化算法的快速收敛性和遗传算法的种群多样性，对有限频谱资源进行调度，同时优化路由跳数.最后仿真实验结果表明，与现有的CR-VANETs路由研究比较，有着更优的路由跳数并使其保持在一个相对稳定的值.

关键词 认知无线电；车载自组织网络；频谱调度；路由跳数；混合启发式算法

车载自组织网络(vehicular ad hoc networks, VANETs)(也称车联网)是一种特殊的自组织网络.在这个网络中，车辆都配备了无线通信设备，使得车辆之间可以“彼此交谈”，信息共享 [1] .通过将无线通信技术和信息技术应用到交通系统中，VANETs被广泛应用于保障交通安全以及车辆信息的传输与交互式通信中 [2-3] .然而，VANETs面临着频谱资源稀缺的问题，主要原因有2个：1)不断增长的信息娱乐应用，例如高质量的视频流，需要消耗大量的频谱资源，这使得现有的专用信道带宽很难保障通信服务质量；2)在城市环境中，一些区域的车辆密度比普通区域高得多，从而导致了频谱资源稀缺问题更为严重 [4] .

认知无线电(cognitive radio, CR)技术是解决频谱资源稀缺问题的一种有效方法.次级用户(secondary users, SUs)采用动态频谱接入技术，在不对授权用户(primary users, PUs)造成干扰的前提下，机会地捕捉和利用当前时空中可用的授权CR频谱空洞，显著提高了频谱利用率 [5] .将CR技术与VANETs相结合构成了认知无线车载自组织网络(CR-VANETs)，即配备了CR频谱感知设备的车辆可以机会地接入其他系统中一些被授权的频带，如电视白频谱，可以有效提高频谱的使用效率，缓解频谱资源稀缺问题，从而提高车辆的通信效率 [6] .

虽然针对认知无线自组织网络(cognitive radio ad hoc networks, CRAHNs)以及VANETs的路由研究较多，但这些路由研究都无法直接应用到CR-VANETs中.这是因为，独特的车载环境如车辆的高速移动性和车对车(vehicle to vehicle, V2V)的通信链路质量都需要被考虑到CR-VANETs的路由设计中.此外，不同于静态CR场景，CR-VANETs中CR频谱资源的动态接入特性导致了信道的有效性不仅仅依赖于授权用户对频谱的使用情况，还依赖于车辆的移动性.频谱接入信息过时、无法找到中继节点、路由跳数过多，这些因素都给CR-VANETs路由设计带来了巨大的挑战 [7] .

目前针对CR-VANETs的路由研究相对较少，已有的少数研究旨在单一优化路由的端到端时延或者链路持续时间.然而，在CR-VANETs的路由设计中，如何最大效率地利用有限CR频谱资源，是需要研究的问题之一.而现有的路由研究并未将CR频谱资源调度作为衡量通信链路质量的参数，用于路由方案的设计中.此外，在多跳无线网络中，过多的跳数仅能在“能量有限”的约束环境中起到一定的作用.因为克服噪音是这种网络环境需要关注的首要问题.而在“带宽有限”的约束环境中，当信噪比高，由于使用了额外的时隙，过多的跳数则会降低端到端吞吐量 [8] .在CR-VANETs中，由于车载供能使得信号发射能量不再有限制.因此，对于有限的CR频谱资源，过多的路由跳数会消耗CR信道切换带宽，导致频谱资源浪费.尤其当车辆密度较大可能出现拥塞时，过多的路由跳数还会使路由开销增大，进一步加重拥塞.

在本文中，区别于现有的CR-VANETs路由研究以及我们前期的研究目标 [9] ，设计了一种联合路由调度方案，将CR频谱资源调度作为影响通信链路质量的参数，同时最大限度地减少网络中的路由跳数.本文的主要贡献有4点：

1) 我们建立了一个CR-VANETs中的网络模型，预测车辆移动并定义出车辆间有效接触时间.

2) 我们建立了一个基于V2V通信的CR频谱模型，得出CR频谱可用概率.通过建模得出的参数，定义出V2V通信链路的链路消耗，将其作为权衡链路质量的权重因子，并通过这个权重因子来进行CR频谱资源调度.同时分析了优化目标，将其转化为有限CR频谱资源约束下的最小化路由跳数问题，并证明该问题为NP难问题.

3) 针对这个联合路由调度问题，我们提出了一种混合启发式算法，结合了粒子群优化算法的快速收敛性和遗传算法的种群多样性，在对有限CR频谱资源调度的同时进行路由跳数优化.

4) 仿真实验结果表明，与现有的CR-VANETs路由研究比较，我们的优化方案有着更优的路由跳数并使其保持在一个相对稳定的值.

1 CR - VANETs背景知识

1999年美国联邦通信委员会(the US Federal Communications Commission, FCC)分配了75 MHz无线频谱(5.850～5.925 GHz)带宽给专用短程通信(dedicated short range communications, DSRC)，用于智能交通系统(intelligent transportation systems, ITS)服务 [10] .根据FCC的规定，这样的频段分为7个信道，包括1个控制信道和6个服务信道，控制信道被分配用于传输信标或基本安全消息 [11] .每个车辆周期性地在控制信道上广播交通信息，包括车速、坐标和车辆的下一个坐标.此信息有助于车辆实时地发现所有相邻车辆 [12] .然而，在城市环境中，车辆的增多伴随着车辆间通信需求的增加，引发了通信频带的拥挤，导致了车辆间通信效率的下降 [13] .此外，车内信息娱乐应用也越来越多，包括对带宽要求高的多媒体应用将会导致网络的拥塞 [14] .

随着认知无线电技术和动态频谱接入技术的出现，为了提高频谱使用效率，FCC放开了授权频谱的使用权，使得空闲的授权频谱(也被称为“频谱空洞”)可以机会地被未授权用户使用.为了解决频谱稀缺问题，VANETs与CR技术联合在一起，形成了CR-VANETs.即装载了CR通信装置的车辆可以方便地接入DSRC信道以及其他检测到的空闲信道.当DSRC信道的传输负载较重，CR将检测和使用其他的空闲信道.在这种情况下，配备了CR通信设备的车辆是未授权用户，也称为SUs.

不同于传统CR网络，车辆的高速移动性使得CR-VANETs网络拓扑是一个动态结构.而不同于传统VANETs，在CR-VANETs中频谱的动态特性使得频谱空洞可能在时间和空间上均发生变化.这些特性使得CR-VANETs中的频谱感知和频谱接入问题极具挑战性.为了解决这些问题，近年来，一些学者对CR-VANETs中的频谱感知、接入、管理等问题进行了深入研究 [15-18] .一方面，这些文献指出高速运动的车辆具有较好的时空分集特性.在CR-VANETs中，采用协作感知的方法能够获得更好的频谱感知参数，充分利用车辆的时空分集特性能够获得更好的频谱检测性能.另一方面，这些文献基于车辆位置预测和频谱地理数据库查询的方法，让车辆快速和准确地获得当前位置以及将来位置的可用频谱信息.这些工作通过理论和仿真实验论证了在CR-VANETs中，所提方法能够保证高速运动环境下CR信道检测的准确性和及时性.

2 相关工作

CRAHNs和VANETs是与CR-VANETs有相似点但又完全不同的2种网络.目前针对CRAHNs和VANETs中路由协议的研究较多.文献[19]提出了一种CRAHNs中基于频谱聚合的协同路由方案，这个路由方案由2种不同类别的路由协议组成，一种用于提高能源效率和吞吐量，另一种则用于减少端到端的延时.文献[20]的作者针对大规模CRAHNs的无线网络衰落信道，提出了一种基于频谱授权图的机会路由协议，并采用协同网络调度来实现多径传输方案.在文献[21-22]中，CRAHNs中的路由路径被分割为数个机会转发段，数据包通过这些转发段来实现一步接一步的转发.文献[23]提出了一种VANETs中基于协同传输方案的跨层路由协议.通过衡量路由决策的链路成本，更好地实现传输功耗和端到端可靠性之间的权衡关系.文献[24]基于变化的拓扑结构设计了一个VANETs中链路持续时间的度量值，并通过捕捉链路剩余时间来判断该链路是否可以用于有效通信，以达到优化路由结构的目的.在文献[25]中，一种称为骨干辅助的方案被用于提供交叉路口的连接状态.基于这种连接状态，作者提出了一种基于贪心策略的路由调度方案，使得在城市VANETs环境中，路由的中间节点数目最小.

然而，上述这些路由协议无法直接用于CR-VANETs环境中.一方面是由于车辆的高速移动，使得车对车通信处在一个高速动态特性的网络拓扑中；另一方面，CR频谱的可用性不仅会根据PUs的活动发生变化，还会根据SUs的活动呈现持续变化的特性.本文在设计CR-VANETs路由方案时，将车辆间的有效接触时间以及CR频谱的可用性均列入了路由设计的考虑因素.

目前已有若干针对CR-VANETs的路由方案研究.有的考虑到了CR频谱的干扰性及车辆的移动性，还有一些考虑到了PUs的活动特性、地理位置及信道切换时延等.

文献[26]提出了一种任意路径的路由协议，利用地理位置信息和感知到的信道进行多速率路由调度.这个任意路径路由的特性是，选择在地理位置上更接近目的地的节点为转发节点，路由路径随着转发节点的改变而改变，从而达到优化路由传输时延的目的.文献[27]的作者通过可用频谱状态，选择了一条安全路径使得PUs和SUs能同时保持通信，并使用移动参数和频谱感知信息来避免路由开销过大.在这个路由方案中，节点仅仅需要知道自己的频谱信息就可以选路，而不需要将自己的频谱信息告诉邻居节点.在文献[28]中，作者通过将PUs的活动特性考虑到频谱变化参数中，提出了一种路径持续时间最大化的路由算法，实现从源节点到目的节点之间的路由有最大路径持续时间.在前期的研究中 [9] ，我们针对时延要求不高的应用场景，采用存储转发策略，提出了一种时延容忍的路由策略来最大化路由投包率.

然而，上述文献的路由方案均未从CR频谱资源调度方面进行考虑，也未针对路由跳数进行研究和优化.基于目前还没有针对CR-VANETs中频谱调度和路由跳数优化的研究，本文提出了一种联合路由调度方案，通过混合启发式算法，将CR频谱资源调度作为影响通信链路质量的参数，同时最大限度地减少网络中的路由跳数.

3 系统模型及问题描述

我们假设有V={V 1 ,V 2 ,…,V n }辆车，每一辆车都配备了 CR 频谱感知设备和 GPS 设备.我们可以通过 GPS 来获取车辆的位置信息和速度信息，然后计算出车辆与车辆间的相对速度.考虑到一般性，我们定义车辆V i ,V j ∈V，分别以速度v i 和v j 在极坐标(v i ,θ i )和(v j ,θ j )中行驶，定义车辆V i 和车辆V j 之间的相对速度为 v i j ，则相对速度 v i j 可以计算为

其中，g(v i ,v j ,θ i ,θ j )依赖于随机变量v i ,v j ,θ i 和θ j ，并且这些变量之间相互独立.此外，我们认为 v i j = v j i .

我们假设每个 CR 节点的通信范围为Ω∈r 2 .如图1所示，如果在时间间隔 Δ t内，车辆V i 和V j 没有改变它们的行驶速度，相对于车辆V j 来说，车辆V i 可视为相对静止在一个固定的位置，此时车辆V j 以相对速度 v i j 移动.设车辆V i 的有效通信覆盖区半径为r TX ，当车辆V j 在这个有效通信的覆盖区域内，车辆V i 和V j 之间能够进行有效通信.当车辆V j 移出图1中的这个阴影区域，则车辆V i 和V j 之间无法进行有效通信.

Fig. 1 V2V communication region
图1 车对车通信范围

在实际应用中，我们还需要考虑不同车辆之间的接触时间.因此我们定义车辆V i 和车辆V j 之间的有效接触时间如下：

定义1 . 有效接触时间.假设在时间t q 时，车辆V j 在车辆V i 的通信范围内，即

其中

定义为t q 之前的时间.有效接触时间定义为：当车辆V j 与车辆V i 开始接触，直到车辆V j 移出车辆V i 的通信范围的这个时间段.即：

这个网络模型可以被抽象为一个二维平面内的有向图G(V,E).其中，节点集V为之前描述的所有车辆节点的集合V={V 1 ,V 2 ,…,V n }，E表示网络中车辆节点之间的无线链接.如果车辆V j 在车辆V i 的通信范围之内，则边(V i ,V j )∈E.

在下垫式CR频谱系统中，一个基于V2V通信的CR频谱模型如图2所示.我们假设每个车辆根据GPS地图将道路分割成S={S 1 ,S 2 ,…,S m }个路段.与车辆的高速移动性相比，PUs在道路上处于一个相对固定的位置，并工作在一个授权信道上.车辆行驶在相同的道路上，会经历相同的CR信道可用性统计数据图.通过这些历史感知统计数据，可以由马尔可夫模型计算出相同信道的状态转移矩阵，推导出反映信道可用性的潜在规律 [29] .

Fig. 2 CR spectrum model based on V2V
图2 基于V2V通信的CR频谱模型

IEEE 802.22标准中规定，协作频谱的感知操作会消耗几个毫秒(通常小于200 ms)，CR在空闲信道上传输的时间需要几秒(通常为2 s).因此，我们假设2 s为CR传输检测周期，即在下一个2 s中的信道可用性与当前频谱决策结果不同.如果路段的长度分割合理，我们假设同一路段内的信道状态相同，每条路段都属于多种CR信道状态之一.该做法的目的是预测在下一个路段的信道可用性，即CR信道状态将在下一个周期(如2 s)转变.因此只要CR信道状态在该路段内保持不变，路段的长度就不影响CR信道可用概率的预测.

通过对历史频谱感知图的统计数据进行数据挖掘，以及对具有相同信道状态转移矩阵的信道进行先验预测，车辆V i 在路段S l 里， CR 信道可用概率可计算为 [29]

其中，变量Threshold是用于决定一个信道是否空闲的阈值;k={1,2,…,K+1}为K+1个不同的 CR 信道状态集

代表车辆V i 在路段S l 中的信道状态

为信道状态转移矩阵.在下一个路段S l+1 中，车辆V i 的信道可用概率可通过信道状态转移矩阵

获得.隐藏超参数(

)是通过对历史频谱感知图的统计数据进行数据挖掘得到的.该算法是在历史数据挖掘结果的基础上，预测到达下一路段的信道可用性概率.

在 CR - VANETs 中，由于 CR 频谱带宽资源有限，我们需要计算不同车辆之间通信链路对频谱资源的消耗，以权衡中继节点的频谱效用.如果车辆V i 和V j 出现在通信链路中，我们定义车辆V i 与车辆V j 之间的通信链路消耗如下：

定义2 . 通信链路消耗.假设在路段S l 中，车辆V i 与车辆V j 之间存在着通信链路

为车辆V i 与车辆V j 之间的有效接触时间，车辆V j 在路段S l 上的 CR 信道可用概率为

我们将车辆V i 与车辆V j 之间的通信链路消耗定义为：从车辆V i 到车辆V j 的链路权重，与有效接触时间及链路中接收端车辆的 CR 信道可用概率成反比.即：

将通信链路消耗作为链路权重因子，能够有效地衡量车辆V i 与车辆V j 通信的频谱资源效用以及车辆间通信链路质量.在这个系统中，我们假设信道分配状态消息是通过公共控制信道来交换的.这在 CR - VANETs 中，可以通过使用专用授权频带来实现.

在CR-VANETs系统中，有 V 辆车、 S 个路段以及 k 个不同的CR信道状态.我们优化的目标为有限CR频谱资源调度，同时最小化路由跳数.

我们可以将有限CR频谱资源调度问题，视为提高CR频谱资源效用的问题.在3.2节中，我们定义了通信链路消耗参数 W ( V i , V j )，并将其作为链路权重因子.由于 W 与车辆的CR可用信道概率成反比，同时与车辆的有效接触时间成反比.当权重因子最小，即通信链路消耗参数 W 取最小值时，CR可用信道概率与车辆的有效接触时间同时有最大值，此时CR频谱资源效用最大，通信链路质量最好，即频谱资源调度最优.在3.1节中，我们将CR-VANETs网络模型抽象为一个二维平面内的有向图 G ( V , E )，这个问题则转化为：如何将有向图中链路总消耗 W ( V i , V j )的总和降到最低，这可以等同于一个最小生成树问题.

此外，我们可以将最小化路由跳数问题视为一个路由选路的问题，即在此系统中，消息尽其可能通过最少的中继节点来实现从源节点到目的节点的转发.因此，我们的联合路由调度问题可以转化为：在有限CR频谱资源约束下，最小化路由跳数的路由问题.

我们定义节点V i 的可达邻居子图为G i (V i ,E i )，并在其中构建最小生成树.然后，我们用E i ={ε 1,2 ,ε 1,3 ,…,ε i,j ,…,ε n-1,n }记录G i 中的边，如果边(V i ,V j )∈E i ，则ε i,j =1，否则ε i,j =0.我们用D i ={δ 1,2 ,δ 1,3 ,…,δ i,j ,…,δ n-1,n }表示图G i 的一棵生成树.如果ε i,j =1，且边(V i ,V j )被选为生成树的边，则δ i,j =1，否则δ i,j =0.对于任何一棵生成树D，其权值用所有边权重的和来表示.我们定义F(x V )为路由跳数，则我们的优化目标可被描述为

其中，R * 为联合路由调度问题转化的路由问题，这个路由有最小化路由跳数F(x V )的目标，并结合了有限 CR 频谱资源约束条件

).在这个约束条件中，W(V i ,V j )为链路V i ,V j 之间的权重因子，用于衡量V i ,V j 之间的通信链路消耗，δ i,j 为二进制常数，当链路被选中时δ i,j =1，当链路未被选中时δ i,j =0.

当最小生成树问题被赋予了新的约束条件，即转化为节点约束最小生成树问题，则该问题是一个典型的NP难问题 [30] .因此，CR-VANETs中，基于有限CR频谱资源约束下的最小化路由跳数问题也是一个NP难问题.

4 混合启发式算法

由于节点约束最小生成树问题属于多维优化问题，因此本文提出了一种混合启发式(hybrid two heuristic, HTH)算法来解决这个联合路由调度问题.这个混合启发式算法结合了具有快速收敛特性的粒子群优化算法和具有良好全局收敛特性的遗传算法，增加了种群多样性，提高了搜索效率.通过这个混合启发式算法，我们首先找出CR频谱资源效用大的路由路径，然后基于这个给定备选路径选出跳数最少的路由方案.

首先，我们引入带有惯性权重的粒子群优化算法，其数学表达式为

v i d (t+1)=wv i d (t)+c 1 α(P i d (t)-x i d (t))+
c 2 β(P g d (t)-x i d (t)),

其中，v i d (t)为第i个粒子第t次迭代中飞行速度的第d维分量;x i d (t)为第i个粒子第t次迭代中位置的第d维分量;P i d 为粒子i最好位置P i 的第d维分量;P g d 为群体最好位置P g 的第d维分量.α和β为随机数;c 1 和c 2 为加速因子;w为惯性权重.

粒子群优化算法中每个粒子可以用于表示问题的一个候选解，不同的问题通常采用不同的粒子编码方式.本文在算法设计时，采用 Prufer 数的染色体编码机制 [31] 来表示生成树的解空间. Prufer 数给出了n个节点的生成树与长度为n-2的数字串之间的一一对应关系，能够保证解空间的完备性. Prufer 编码和解码算法的伪代码描述如下：

例如有一棵生成树如图3( a )所示，与之相对应的 Prufer 数则为图3( b )所示的编码.

Fig. 3 Spanning tree and Prufer number
图3 生成树与对应的Prufer数编码

我们根据 Prufer 数的解码方案计算出生成树D={δ 1,2 ,δ 2,3 ,…,δ i,j ,…,δ n-1,n }，解码方案为编码方案的逆过程.则粒子X的适应度可定义为

命题1 . 在同一个路段，对于种群中的任意2个粒子，拥有较小适应度的粒子有更好的解.

证明. 假设在同一路段S l ，fit(X i )和fit(X j )分别代表了V i 和V j 的适应度.如果fit(X i )lt;fit(X j ),则有

).为了简化这个证明，我们假设在这个路段中δ i =δ j .因此，基于这个假设前提可以得到W i lt;W j .而较小的链路消耗意味着较大的 CR 信道可用概率或较长的有效接触时间.因此，拥有较小适应度的粒子X j 有更好的解.

通过命题1可知，使用式(6)的适应度方程，我们可以选择出更优的 CR 频谱资源效用方案，然后基于这个方案下的备选路径，选择跳数最少的路由.

粒子群优化算法在复杂的多峰搜索问题中可能会导致过早收敛，为解决此问题，我们采用了遗传算法中的变异算子M来代替粒子群优化算法中的惯性部分，其中

表示第i个粒子在第t-1代的解：

变异算子M的具体操作如下:首先随机选取粒子X中的一个位置点ξ，令X(ξ)等于{1,2,…,n}中随机选取的一个值.对于某个节点车辆V i 而言，n为节点V i 的可达邻居节点数.

此外，我们采用遗传算法中的交叉算子C p 和C g 来表示粒子群优化算法中的局部最优位置和全局最优位置：

其中，r 2 和r 3 都是[0,1]之间的一个随机值

为

经过惯性操作之后的粒子值

算子表示将

与第i个粒子的自身最优解进行交叉运算

算子表示将

与种群目前为止搜索到的最优解进行交叉运算.

杂交算子C p ，C g 均采用的是双点杂交算子，具体操作如图4所示：令粒子X的当前位置为A i ，X的自身最优位置为P i ，种群的全局最优位置为G，随机选取2个位置点h 1 和h 2 ，则新粒子位置点h 1 和h 2 之间的部分由粒子P i 的这部分序列直接复制而来.

Fig. 4 Two point hybridization of particles
图4 粒子的双点杂交示意图

粒子与种群的全局最优位置的交叉操作也采取相同的方式.综上所述，粒子X的位置更新公式为

在搜索过程中，为了提高算法的搜索效率，将参数调整如下：

其中，w max 和w min 分别为初始化时w的最大值和最小值；gen为种群最大的进化代数；mgen为种群当前的进化代数.

CR - VANETs 中的任意节点V i 根据局部信息，运行 HTH 算法伪代码如下：

输入：原始的局部网络拓扑结构图G i (V i ,E i )、节点的最大通信范围;

① 初始化种群X以及相应的参数，如种群规模popsize，进化代数gen，w，c 1 和c 2 等；

通过这个混合启发式算法，我们采用了最小生成树的拓扑调节思路，通过对粒子的适应度进行评价，对加速因子和惯性权重进行调整，得出问题的全局最优解，即选出跳数最少的路由方案.

5 实验与结果

我们使用了NS2平台来评估混合启发式算法的性能，并同4种路由方案作参数比较：无线自组网按需平面距离向量路由协议(ad hoc on-demand distance vector routing, AODV)、CR-VANETs中的延时优化路由研究(CoRoute) [26] 、转发性能优化路由研究(SSR) [27] 以及路由持续时间优化的研究(EPDM-R) [28] .

在仿真环境中，我们采用干扰温度模型来确定接收信号的实际信道状态 [32] .授权用户PUs通过瑞丽信道传输信号，并按照自由空间传播模型衰减.CR频谱包含10个信道，每一个信道有2 MHz带宽，每个PU被分配到10个CR信道中的一个信道.此外，我们采用了文献[33]中对信道概率的设置规则，即每个PU接入授权信道的规则为： p (0/0)=0.95， p (1/0)=0.05， p (0/1)=0.10， p (1/1)=0.90，其中 p (1/0)是PU从闲置状态“0”变化为忙状态“1”的概率.

依据IEEE 802.22标准中规定的参数，我们假设2 s为一个信道传输检测周期.考虑到车辆移动的最大速度为60 km/h(即16.7m/s)，我们在仿真实验中设置的路段长度为50 m.

在无线网络配置方面，我们采用IEEE 802.11p标准作为媒体接入控制(media access control, MAC)层协议.我们设置通信范围为400 m，数据包大小为512 B.为便于评估性能参数，我们不考虑城市场景中的障碍物遮挡情况.我们假设车辆(即次级用户SUs)在道路上呈泊松分布，并沿着道路直线行驶.仿真实验在不同的车辆密度下进行，从50～300辆车，表示相对稀疏和密集的网络.仿真时间12 h，所有参数均取平均值.实验参数如表1所示:

Table 1 Simulation Parameters

表1 实验参数

实验结果分别从平均路由跳数、投包率以及端到端延时这3个参数来对比了5种路由方案的性能参数，同时比较了不同路由方案在不同车辆密度下的参数值.此外，我们还基于本文提出的路由方案，比较了不同信道带宽参数对平均路由跳数的影响.

图5显示了在不同车辆密度下，上述5种路由方案的平均跳数值.当车辆密度增大时，这5种路由方案的平均跳数值都有所增加.这是因为，随着车辆的增多，可以作为中继节点的候选车辆节点数量也随之增多，每个包的传输机会随着车与车的接触增多也相应增大.为了各自的优化目标，这5种路由方案都会为了完成优化目标而改变包的传输路径，从而导致了路由跳数的增加.

Fig. 5 Average hop count of different routing algorithms
图5 不同路由方案的平均跳数

HTH算法在每个密度点的跳数均值都优于其他路由方案，并且其平均跳数值保持在一个相对较小的波动范围内.在相对密集的网络环境中，SSR路由方案的平均跳数略有减少，这是由于在其优化转发过程中，为了避免开销过大会对路由开销进行约束，从而导致了路由跳数减小.在相对稀疏的网络中，EPDM-R路由方案的平均跳数值也相对较小.但随着车辆密度的增大，中继节点增多，基于从源节点到目的节点的路由持续时间最大化优化目标导致了该方案路由跳数的增加.CoRoute路由方案的平均跳数值随车辆节点的增加而增幅最大.这是因为在CoRoute路由方案中，最小化端到端延时是其优化目标，当出现了路径更短的中继节点时，此节点便立即成为下一跳目标.这就导致当车辆节点增多时，候选节点的增多带来了路由跳数的增加.

Fig. 6 Packet delivery ratio of different routing algorithms
图6 不同路由方案的投包率

图6显示了在不同车辆密度下，上述5种路由方案的数据投包率.其他路由方案的投包率均随着车辆密度的增大而增加，而AODV路由方案的投包率则明显下降.导致这种现象的原因之一是：在AODV协议中，当一个节点需要给网络中的其他节点传送信息时，如果没有到达目标节点的路由，则必须先以多播的形式发出路由请求报文.而包开销的增加会导致网络负载显著增加，从而导致更多的数据包被丢弃.

在大多数密度节点下，HTH路由方案取得了比其他路由方案更高的投包率.这是由于在HTH路由方案中，将CR频谱资源调度作为衡量通信链路质量的参数，将通信链路消耗作为有限频谱CR频谱资源约束条件，从而提高了CR频谱资源效用，获得了较高的投包率.在车辆密度增长到250节点后，HTH路由方案的投包率呈现增长平缓的趋势.这是因为HTH路由方案联合了最小化路由跳数的优化目标，使其在节点密度大的环境中，权衡了优化目标和约束条件这两者之间的关系.在车辆到达300的最大密度节点时，由于EPDM-R路由方案的优化目标为路由持续时间最大化，因此表现的更佳.

Fig. 7 End-to-End delay of different routing algorithms
图7 不同路由方案的端到端时延

图7显示了在不同车辆密度下，上述5种路由方案的端到端延时.当车辆密度增大时，其他路由方案的端到端延时有所下降，而AODV路由方案的端到端延时则明显上升.这是因为在AODV路由方案中，一旦发现某一个链路断开，路由中的节点就发送ERROR报文通知那些因链路断开而不可达的节点删除相应的记录，或者对已存在的路由进行修复，从而增加了传输时延.基于延时优化目标的CoRoute路由方案表现最优.HTH路由方案在端到端延时这个性能上，表现略逊于CoRoute路由方案，但是仍然优于SSR路由方案以及EPDM-R路由方案.在HTH路由方案中，包是按照最佳跳数路由来传播的，这导致了它会因为路由跳数的优化目标而错过一些延时较小的中继节点，或者不会为了选择更短的几何距离到达目的节点从而选择跳数较多的路由.SSR路由方案和EPDM-R路由方案均有相对较高的端到端延时，且在低密度节点SSR路由方案优于EPDM-R路由方案，而在高密度节点则正好相反.这是因为不同的优化目标使得它们在不同的节点密度下表现出不同的优化特性.

图8显示了在不同车辆密度下HTH路由方案的平均跳数值.当CR信道带宽较小时，平均路由跳数相对较大.当CR信道带宽增加到一定值时，平均路由跳数则不再受到CR信道带宽的显著影响.这是因为，通过使用额外的CR信道带宽，一定程度上降低了DSRC信道拥塞，从而减少了路由跳数.此外，CR信道空闲带宽越大，其信道可用概率就越高，包传输的可靠性则越高.当CR信道带宽超过一定的阈值时，路由平均跳数受信道带宽的影响则相对较小.

Fig. 8 Average hop count with different channel bandwidth
图8 不同信道带宽情况的平均路由跳数

6 结束语

本文研究了一个CR-VANETs中联合CR频谱资源调度和最小化路由跳数的问题.为解决这个问题，我们建立了CR-VANETs中的网络模型以及基于V2V通信的CR频谱模型，用于预测车辆间有效接触时间，并得出CR频谱可用概率.通过这些参数，我们定义了网络拓扑中的通信链路消耗，并将这个链路消耗作为CR频谱资源调度的权重因子.我们将这个联合路由调度问题转化为有限CR频谱资源约束下的路由跳数优化问题，并证明该问题为节点约束最小生成树的NP难问题.我们通过粒子群优化算法和遗传算法相结合的混合启发式算法，找出CR频谱资源效用大的路由路径，然后基于这个给定备选路径，我们选出跳数最少的路由方案.仿真实验结果表明，与现有的CR-VANETs路由研究比较，我们的方案有着更优的路由跳数并使其保持在一个相对稳定的值.

[1]Drabkin V, Friedman R, Kliot G, et al. On reliable dissemination in wireless ad hoc networks[J]. IEEE Trans on Dependable amp; Secure Computing, 2011, 8(6): 866-882

[2]Xie Yong, Wu Libing, Zhang Yubo, et al. Anonymous mutual authentication and key agreement protocol in multi-server architecture for VANETs[J]. Journal of Computer Research and Development, 2016, 53(10): 2323-2333 (in Chinese)(谢永, 吴黎兵, 张宇波, 等. 面向车联网的多服务器架构的匿名双向认证与密钥协商协议[J]. 计算机研究与发展, 2016, 53(10): 2323-2333)

[3]Liu Bingyi, Wu Libing, Jia Dongyao, et al. Data uplink strategy in mobile cloud service based vehicular ad hoc network[J]. Journal of Computer Research and Development, 2016, 53(4): 811-823 (in Chinese)(刘冰艺, 吴黎兵, 贾东耀, 等. 基于移动云服务的车联网数据上传策略[J]. 计算机研究与发展, 2016, 53(4): 811-823)

[4]Lu Ning, Luan T, Wang Miao, et al. Capacity and delay analysis for social-proximity urban vehicular networks[C]

Proc of IEEE INFOCOM’2012. Piscataway, NJ: IEEE, 2012: 1476-1484

[5]Tsukamoto K, Koba S, Tsuru M, et al. Cognitive radio-aware transport protocol for mobile ad hoc networks[J]. IEEE Trans on Mobile Computing, 2013, 14(2): 288-301

[6]Han You, Ekici E, Kremo H, et al. Throughput-efficient channel allocation algorithms in multi-channel cognitive vehicular networks[J]. IEEE Trans on Wireless Communications, 2017, 16(2): 757-770

[7]Singh K D, Rawat P, Bonnin J M. Cognitive radio for vehicular ad hoc networks (CR-VANETs): Approaches and challenges[J]. EURASIP Journal on Wireless Communications and Networking, 2014, 2014(1): 49

[8]Andrews J G, Weber S, Kountouris M, et al. Random access transport capacity[J]. IEEE Trans on Wireless Communications, 2010, 9(6): 2101-2111

[9]Wang Jing, Zhang Huyin, Tang Xing. Delay tolerant routing for cognitive radio vehicular ad hoc networks[C]

Proc of the 22nd IEEE Int Conf on Parallel and Distributed Systems. Piscataway, NJ: IEEE, 2017: 24-31

[10]Regan M A, Oxley J A, Godley S T, et al. Intelligent transport systems: Safety and human factors issues[J]. Report, 2001, No.01

[11]Kenney J B. Dedicated short-range communications (DSRC) standards in the United States[J]. Proceedings of the IEEE, 2011, 99(7): 1162-1182

[12]Ma Xiaomin, Zhang Jinsong, Wu Tong. Reliability analysis of one-hop safety-critical broadcast services in VANETs[J]. IEEE Trans on Vehicular Technology, 2011, 60(8): 3933-3946

[13]Cheng S T, Horng G J, Chou C L. Adaptive vehicle to vehicle heterogeneous transmission in cooperative cognitive network VANETs[J]. International Journal of Innovative Computing Information amp; Control, 2012, 8(2): 1263-1274

[14]Ghandour A J, Fawaz K, Artail H. Data delivery guarantees in congested vehicular ad hoc networks using cognitive networks[C]

Proc of the 7th Int Wireless Communications and Mobile Computing Conf. Piscataway, NJ: IEEE, 2011: 871-876

[15]Niyato D, Hossain E, Wang Ping. Optimal channel access management with QoS support for cognitive vehicular networks[J]. IEEE Trans on Mobile Computing, 2011, 10(4): 573-591

[16]Pan Miao, Li Pan, Fang Yuguang. Cooperative communication aware link scheduling for cognitive vehicular networks[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(4): 760-768

[17]Felice M D, Doost-Mohammady R, Chowdhury K R, et al. Smart radios for smart vehicles: Cognitive vehicular networks[J]. IEEE Vehicular Technology Magazine, 2012, 7(2): 26-33

[18]Cheng Nan, Zhang Ning, Lu Ning, et al. Opportunistic spectrum access for CR-VANETs: A game-theoretic approach[J]. IEEE Trans on Vehicular Technology, 2014, 63(1): 237-251

[19]Ping S, Aijaz A, Holland O, et al. SACRP: A spectrum aggregation-based cooperative routing protocol for cognitive radio ad-hoc networks[J]. IEEE Trans on Communications, 2015, 63(6): 2015-2030

[20]Lin S C, Chen K C. Spectrum-map-empowered opportunistic routing for cognitive radio ad hoc networks[J]. IEEE Trans on Vehicular Technology, 2014, 63(6): 2848-2861

[21]Tang Xing, Chang Yanan, Zhou Kunxiao. Geographical opportunistic routing in dynamic multi-hop cognitive radio networks[C]

Proc of 2012 Computing, Communications and Applications Conf. Piscataway, NJ: IEEE, 2012: 256-261

[22]Tang Xing, Liu Qin. Network coding based geographical opportunistic routing for ad hoc cognitive radio networks[C]

Proc of 2012 IEEE GLOBECOM Workshops. Piscataway, NJ: IEEE, 2013: 503-507

[23]Ding Zhiguo, Leung K K. Cross-layer routing using cooperative transmission in vehicular ad-hoc networks[J]. IEEE Journal on Selected Areas in Communications, 2011, 29(3): 571-581

[24]Sofra N, Gkelias A, Leung K K. Route construction for long lifetime in vanets[J]. IEEE Trans on Vehicular Technology, 2011, 60(7): 3450-3461

[25]Sahu P K, Wu E H, Sahoo J, et al. BAHG: Back-bone-assisted hop greedy routing for VANET’s city environments[J]. IEEE Trans on Intelligent Transportation Systems, 2013, 14(1): 199-213

[26]Kim W, Gerla M, Oh S Y, et al. CoRoute: A new cognitive anypath vehicular routing protocol[J]. Wireless Communications amp; Mobile Computing, 2011, 11(12): 1588-1602

[27]Abedi O, Bemaninejad S. Soft and stable routing protocol for cognitive radio VANETs considering cognitive users mobility[C]

Proc of the 11th Int Conf on Innovations in Information Technology. Piscataway, NJ: IEEE, 2015: 116-121

[28]Liu Jing, Ren Pinyi, Xue Shaoli, et al. Expected path duration maximized routing algorithm in CR-VANETs[C]

Proc of the 1st IEEE Int Conf on Communications in China. Piscataway, NJ: IEEE, 2012: 659-663

[29]Huang Xinlin, Wu Jun, Li Wenfeng, et al. Historical spectrum sensing data mining for cognitive radio enabled vehicular ad-hoc networks[J]. IEEE Trans on Dependable amp; Secure Computing, 2016, 13(1): 59-70

[30]Mitsuo G, Cheng Runwei. Genetic Algorithms and Engineering Optimization[M]. Beijing: Tsinghua University Press, 2004

[31]Gottlieb J, Julstrom B A. Prufer numbers: A poor representation of spanning trees for evolutionary search[J]. Cheminform, 2002, 36(7): 2386-2390

[32]Federal Communications Commission (FCC). Notice of inquiry and notice of proposed rulemaking[R]. Washington, DC: Technical Report ET Docket 03-237, 2003

[33]Huang Xinlin, Wang Gang, Hu Fei. Multitask spectrum sensing in cognitive radio networks via spatiotemporal data mining[J]. IEEE Trans on Vehicular Technology, 2013, 62(2): 809-823

Zhang Huyin , born in 1962. Professor and PhD supervisor. His main research interests include network QoS, next generation network architecture, and ad hoc networks.

Wang Jing , born in 1983. PhD candidate. Her main research interests include wireless networks and mobile ad hoc networks (wangjing100717@whu.edu.cn).

Joint Routing and Scheduling in Cognitive Radio Vehicular Ad Hoc Networks

1 (School of Computer Science, Wuhan University, Wuhan 430072) 2 (School of Computer Science and Technology, Wuhan University of Technology, Wuhan 430070)

Abstract Cognitive radio vehicular ad hoc networks (CR-VANETs) have been envisioned to solve the problem of spectrum scarcity and improved spectrum resource efficiency in vehicle-to-vehicle communication by exploiting cognitive radio into the vehicular ad hoc networks. Most existing routing protocols for cognitive radio networks or vehicular ad hoc networks cannot be applied to CR-VANETs directly due to the high-speed mobility of vehicles and dynamically changing availability of cognitive radio channels. At present, the routing research for CR-VANETs is relatively few. How to utilize the spectrum resources effectively and moreover reduce the spectrum band consumption caused by routing hops is still a pending problem. Aspiring to meet these demands and challenges, this paper presents a joint routing and scheduling, which combines the scheduling of spectrum resources and the goal of minimizing routing hops in CR-VANETs. To achieve this goal, we first establish a network model and a CR spectrum model to predict the contact duration between vehicles and the probability of spectrum availability. We define the communication link consumption and the weight of channel according to these parameters. Then we transform the optimization objective into a routing scheme with minimizing hop count, subject to constraint on the scheduling of spectrum resource, and moreover prove this routing scheme is NP-hard. To tackle this issue, a hybrid heuristic algorithm is composed by a particle swarm optimization with fast convergence and a genetic algorithm with population diversity. Simulation results demonstrate that our proposal provides better routing hop counts compared with other CR-VANETs protocols.

Key words cognitive radio (CR); vehicular ad hoc networks (VANETs); spectrum scheduling; routing hops; hybrid heuristic algorithm

Received his PhD degree in computer science from City University of Hong Kong in 2015. Lecturer. His main research interests include distributed systems and wireless networks (tangxing@whut.edu.cn).

基金项目： 国家自然科学基金项目(61772386)；广东省省级科技计划项目(2015B010131007)

This work was supported by the National Natural Science Foundation of China (61772386) and the Science and Technology Planning Project of Guangdong Province (2015B010131007).