认知车载网中基于簇和MAB模型的信道接入算法

2016-11-30彭飞章国安杨羽琦

电信科学 2016年7期

关键词：时隙吞吐量车载

彭飞，章国安，杨羽琦

（南通大学电子信息学院，江苏南通 226019）

认知车载网中基于簇和MAB模型的信道接入算法

彭飞，章国安，杨羽琦

（南通大学电子信息学院，江苏南通 226019）

针对高密度车流环境下认知车载网中车辆节点对认知信道的接入问题，提出了基于簇和MAB模型的clusters-UCB信道接入算法，通过簇内成员协作提高感知学习结果的准确性，提升算法学习速度，并且簇首通过clusters-UCB算法分布式地快速搜索出最佳信道，渐近地实现最大的时隙吞吐量。仿真实验表明，提出的算法相对于多用户的UCB算法和ε-greedy算法，遗憾值更低，并且趋近于对数形式的收敛速度更快，能够有效减少访问碰撞数，保证信道接入的公平性，提高时隙吞吐量。

认知车载网；簇；信道接入；MAB模型；UCB算法

1 引言

在高密度的交通环境下或者支持高速率互联网接入的车载网络中，IEEE 802.11p标准中规定的5.9 GHz频段的频谱资源远远不能满足车辆用户的需求，认知车载网的概念应运而生[1]。由于平面结构的车辆自组织网络在节点数量很大时，特别是在车辆节点高速移动的环境下，会有较大的控制开销，使得处理能力变弱甚至传输路径中断，所以平面结构不适用于高密度交通环境下的认知车载网络。因此，采用分级结构更加合适，考虑基于簇的车辆通信模型[2]，如图1所示，一个簇由一个簇首和多个簇成员组成。一个簇成员通信的数据最开始传输到簇首，然后转发到目的地，这个目的地可能是路边单元（roadside unit，RSU）或者一个相邻的簇首。采用参考文献[3]中高稳定性的RMAC （robust mobility adaptive clustering）算法进行分簇，根据邻居节点的相对移动度量值（速度、位置以及行驶方向）计算出节点优先性，从而推举出簇首，使得簇生存时间更长。簇首维护两跳范围内的节点列表，从而使得当簇成员离开原来簇的时候优先知道这一信息，以便快速加入新簇。

认知车载网中存在两种类型的信道，分别是认知信道和专用信道，都可用于簇内和簇间的通信。专用信道主要用于簇内的广播消息，而认知信道在主用户（primary user，PU）不占用的情况下供簇使用，主要用于紧急情况下的交通信息广播和大流量视频等娱乐信息的传播。簇需要感知授权频谱以检测主用户传输存在与否，然而由于资源和硬件的限制，簇只能够在给定的时间内感知部分频谱，因此需要在有限的时间内通过对以往信道有效性的学习来更快地找到最佳信道，以最大化时隙吞吐量进行数据传输。机器学习（machine learning，ML）理论中的 MAB（multi-armed bandit）模型与认知无线网络频谱分配之间存在相似性，经典的MAB模型使用UCB（upper confidence bound）算法进行搜索学习，因此UCB算法也被诸多参考文献用来解决认知信道的接入问题。参考文献[4]研究了单用户的信道信息服从独立同分布变化时，用户在多个信道中进行选择接入的问题，并提出了一种基于RMAB（restless multi-armed bandit）模型的决策方案。参考文献[5]通过在UCB索引的置信因子中引入收益方差值来调整对未知信道环境的探索过程，以降低探索成本。参考文献[6]以更快的速度使算法收敛于弱稳定平衡，而这降低了几乎所有游戏的纯纳什均衡，然而假设的是等效遗憾值而不是随机遗憾值，并且用户能够完全观察到其他用户的行为。参考文献[7]考虑组合赌博机，对于更加普遍的多个用户、不同信道有效性的模型提出了一个匹配算法分配信道，这个算法保证了对于传输时隙而言对数形式的遗憾值。

然而，参考文献[4,5]仅仅考虑了单用户的情况，而认知车载网中存在大量的车辆节点。参考文献[6,7]中用户之间进行了信息交换，而不是分布式的方案，这增加了系统开销并且不易于实现。大多数论文都考虑完美的感知情况，在认知车载网的场景下，由于阴影效应、多径效应等因素的影响，信道质量很差，感知结果很可能是不正确的，因此有必要考虑不完美的感知情况。另外，希望提出的算法具有更小的遗憾值，遗憾值是衡量UCB算法的重要性能指标，定义为与理想情况相比吞吐量的缺失，它可以指示学习算法的收敛速度。因此提出了适用于认知车载网的、基于簇和MAB模型的信道接入算法，通过簇内成员协作以提高感知的准确性，簇首通过改进的UCB算法分布式地搜索最佳信道，遗憾值较低并且趋近于对数形式的收敛速度更快，能够有效减少簇间访问碰撞数，并保证传输的公平性，渐近地实现更大的时隙吞吐量。

图1 认知车载网中基于簇的通信模式

2 网络模型

网络模型中信道模型、时隙结构以及遗憾值这3个部分对于提出的信道接入算法而言尤为重要。信道模型涉及每个簇中簇首与簇内成员对于认知信道以及专用信道的接入模式，时隙结构从时隙的角度对信道尝试接入的详细过程进行细分，而遗憾值对于基于MAB模型的信道接入算法而言是一项重要的性能指标。

2.1 信道模型

考虑由C个信道和U个簇组成的网络模型。每个车辆节点都配备有认知无线设备，可以感知和机会性地访问授权频谱。考虑基于时隙的通信方式，时间分为离散的时隙 n=0，1，2，…。在第 k 个时隙信道 i空闲的概率为 μi，即信道i空闲的指示变量表示平均值为μ的伯努利分布。

令Ti,j(k)表示信道i在k个时隙中被簇j感知的总时隙数。对于授权频谱覆盖范围内的簇，这是因为每个簇在每个时隙只感知一条信道。在第k个时隙的开始阶段，通过对以前接入结果的学习，每个簇首通知簇成员u感知信道i，由此获得信道Wi(k)的值，来判断信道i是否空闲。然后，簇内成员将感知结果Ii,j(u,k)通过专用信道发送到簇首，Ii,j(u,k)为1表示在第k个时隙簇j内的成员 u感知信道 i是空闲状态，Ii,j(u,k)为 0表示感知结果为信道i是占用状态。簇首会计算关于信道i的所有感知结果的和，usum为所有与簇首取得联系的簇内成员的总数（包括簇首），如果簇内感知结果超过判决阈值ψ，则认定信道状态为空闲，否则为占用状态，即：

如果两个或更多的簇尝试在同一个信道传输，那么没有簇会传输成功。在第k个时隙的末尾阶段，每个簇通过接收确认信号Zj(k)来判定它在kth时隙的传输数据是否被成功接收，簇j记录在k个时隙内信道i被簇j成功接入的次数。因此，任何在第k+1时隙应用在簇j的算法是基于所有簇成员之前的感知和反馈结果。然而，簇对ui的值并不清楚，所以必须学习这些值以最小化对主用户和其他簇的干扰。

2.2 时隙结构

将时隙分为4个阶段，如图2所示。

（1）决策阶段 td

根据之前时隙的传输结果和学习算法，簇j决定下次传输使用哪个信道，并在专用信道把这些信息传输给簇内成员。然后，每个簇内成员将把收发机无线接口调整到信道i。

（2）感知阶段 ts

每个簇内成员感知信道i以检测信道中主用户是否存在。若信道i在当前时隙k是空闲的，则Ii,j(u,k)=1，否则为0。不假设完美的感知，而是建模了感知的准确度，对于信道i，簇成员u正确检测的概率为，错误检测的概率为。簇内成员u决策出信道i空闲的概率为：

（3）通信阶段 tc

在感知阶段后，簇内成员在专用信道上广播感知结果，簇首接收到所有成员u=1,…,usum的结果，计算簇j关于信道i在k个时隙内所有感知结果的和，usum为簇内成员的总数（包括簇首），使用式（1）进行信道情况的判断。

（4）传输阶段 tx

如果簇首发现信道i是空闲的，则在信道i上进行传输，否则不传输，等待下一个时隙选择其他信道。当成功传输后，它从接收器中接收 Zj(k)信号，若 Zj(k)中包含ACK消息，簇首进行Xi,j(k)=Xi,j(k-1)+1运算；假如发生主用户干扰或者与其他簇发生碰撞，Zj(k)会包含NACK消息，则Xi,j(k)=Xi,j(k-1)。

2.3 遗憾值

学习算法的目标是在对主用户没有造成干扰的情况下最大化簇传输成功数，从而提高时隙吞吐量。

定义时隙吞吐量为：

图2 时隙结构

其中，dsum表示在k个时隙内U个簇感知的时隙总数，即U·k，dsuccess表示成功传输的总时隙数。

令S(n;μ,U,ρ)表示U个簇在使用算法ρ的情况下于n个时隙后成功传输的总数。理想场景下信道有效性可知，即信道空闲概率μ可知，簇正交地接入较好的U个信道中。在n个时隙后估计成功传输次数为：

其中，j*指的是具有μ中最大值的信道。

对于所有的算法 ρ和任意 n∈N，有 S*(n;μ,U)＞S(n;μ,U,ρ)。目标是在学习和访问中最小化遗憾值，即：使R(n)在任意给定的μ∈(0,1)下最小。其中：

其中，Vi,j(n)表示在n个时隙内簇j是唯一感知信道i的簇的时隙数。因此，式（5）为：

3 基于簇和MAB模型的信道接入算法

3.1 经典的UCB算法

在单用户、多信道的情况下，用户如何选择信道实现最大时隙吞吐量的问题转化为了一个简单的MAB模型，解决这种问题最简单的方法就是经典的单用户UCB算法[8]。索引值g由两部分构成，前一部分表示信道i的平均估计有效性，而后一部分是置信因子，使得每个信道经过足够次数的有效性学习。

其中，Ti(n)表示n个时隙内信道i被感知的总次数。

其中，Xi(k)表示在n个时隙内成功接入信道i的时隙数。

对于信道i，当时隙数n较小时，置信因子的值很大，感知次数越少的信道的置信因子值越大，下一个时隙就越可能感知该信道；当时隙数n很大时，置信因子的值很小，索引值的大小关键在于第一部分，即索引值的大小取决于信道的有效性。

算法1 单用户UCB算法ρ1(g(n))

定义 {Xi(n)}i=1,2,…,C表示在 n个时隙后信道 i的平均估计有效性，g(i;n)表示基于i(n)的索引值，σ(a;g(n))表示对于单用户a而言，具有最大g(n)的信道号，Curr_Sel表示准备接入的信道号。

初始化：每个信道感知一次，n←C,Curr_Sel←C。循环：n←n+1

Curr_Sel←σ(a;g(n))；

感知信道 Curr_Sel，TCurr_Sel(n)=TCurr_Sel(n-1)+1；

if感知信道Curr_Sel为空闲状态，then

XCurr_Sel(n)=XCurr_Sel(n-1)+1，在该信道传输；

else

XCurr_Sel(n)=XCurr_Sel(n-1)，等待下一个时隙进行数据传输；

end

更新所有信道的索引值 g(i;n)，i=1，2，…，C。由参考文献[8]可知，随着时隙数的增加，UCB算法的遗憾值渐进地趋向于对数形式，而不是线性形式，因而遗憾值增长速度较慢。

3.2 基于簇和MAB模型的clusters-UCB算法

基于第3.1节经典的单用户UCB算法，提出了clusters-UCB算法，主要在如下3方面做出改进。

（1）提出了随机化的防碰撞机制，在单用户的UCB算法的基础上引入碰撞指示变量，簇可以采用随机化信道访问，以避免簇与簇之间的碰撞，并且不同于将感知结果作为学习对象，将接入结果作为学习对象，这样可以防止每个簇都加入同一个具有最高有效性的信道。如果某一簇在上一个时隙发生碰撞，则在此时隙会重新随机选择一个信道，经过有限次的碰撞后，簇能够正交地选择没有其他簇干扰的最佳信道；如果上一个时隙没有发生碰撞，则不需重新选择信道。这种机制也适用于ε-greedy算法，从而将单用户的情况扩展到多用户的情况。

（2）由分布式的访问模式改变为簇内协作感知、簇间分布式接入的模式，簇内成员共享同一个认知信道，属于交叉位置的成员可以访问多个认知信道。这种基于簇的通信方式有效地扩展了可以参与认知信道访问的用户数，适用于高密度的车载网络，并且簇内协作有效地提高了感知结果的正确性，降低了对主用户的干扰。并且考虑协作带来的系统开销，簇首发出所需感知信道的ID给每个簇成员，并且每个簇成员在每个时隙只发出1 bit的感知结果，因此协作的开销仅仅为包含有感知信道ID号以及1 bit感知结果的数据分组，因此协作带来的系统开销很小。

（3）索引值g采用最优化的度量[9]，改进了UCB算法，将g由原来的更改为大大降低了遗憾值和碰撞数，更快地实现最大的时隙吞吐量。

定义用户数为U，信道数为C，Xi,j(n)表示在n个时隙后簇j成功接入信道i的时隙数，{i,j(n)}i=1,…,C表示在 n 个时隙后簇j对于信道i的平均估计有效性，Ti,j(n)表示簇j选择感知信道i的时隙数(i;n)表示基于i,j(n)的第 n个时隙簇j对于信道i的g索引值，σ(gj(n))表示对于簇j而言具有最大g索引值的信道号，ζj(i;n)表示簇j在信道i上第n个时隙的碰撞指示变量，Curr_channel表示簇j当前选择的信道号。

初始化：簇首感知每个信道一次，n←C,Curr_channel←1，ζj(i;n)←0。

循环：n←n+1；

Curr_channel←σ(gj(n))；

if ζj(Curr_channel;n-1)=1，then

选择一个新的 Curr_channel～Unif(C)；

end

TCurr_channel,j(n)=TCurr_channel,j(n)+1；

选择信道Curr_channel来感知，簇首广播信道号Curr_channel给簇成员；

if 通过式（1）的计算发现信道Curr_channel是空闲的，then

接入信道Curr_channel；

if传输成功，then

ζj(Curr_channel;m)←0；

end

从clusters-UCB算法中可以看出，如果时隙数够多，由于某些簇长期占用某些信道，导致这些信道的有效性下降，从而对于其他簇而言，这些原本信道有效性可能高的信道将获得较小的g索引值，因此，通过算法的学习，每个簇只会选择对于自身而言具有最高g索引值的信道。

4 性能评估

假设信道数用C表示，信道的有效性由具有等间隔参数{0.9,0.8,…,0.2,0.1}的伯努利分布表示，例如C=3，那么信道有效性为{0.9,0.8,0.7}，簇数用U表示。为方便分析，假设簇在仿真期间不会发生重组，即簇内成员数不会发生改变，假设簇内成员数u=5，假设每个车辆节点感知的准确性相同，即假设感知判决阈值ψ=U/2。每次仿真都运行100次并取100次结果的平均值，在遗憾值、碰撞数、公平性以及时隙吞吐量方面将clusters-UCB算法与UCB算法、ε-greedy算法进行比较。

（1）遗憾值

图3和图4都显示了3种算法关于遗憾值的性能比较，图3显示固定信道数C=9不变，U=3、4、5个簇的情况，图4显示固定簇数U=4不变，信道数C=5、7、9的情况。3种算法的遗憾值对于时隙都渐近地呈对数形式而非线性形式。此外，还可以观察到当信道数不变，簇数越多，遗憾值越大，收敛时间越长，这是由于多个簇的竞争导致接入较差信道的概率越大，越不容易接入彼此正交的信道；固定簇数不变，信道数越多，遗憾值越大，这是因为簇可选择的信道更多，发生碰撞时均匀随机地选择信道，使得簇也容易接入较差的信道，这样也会增加遗憾值。比较而言，在遗憾值方面，clusters-UCB算法要明显优于多用户UCB算法、ε-greedy算法，由于簇内用户的协作以及UCB改进搜索算法的优势，clusters-UCB算法的遗憾值要比其他两种算法的值小，并且学习更快，即曲线的斜率越大。还可以观察到ε-greedy算法比UCB算法更优，但这是在参数进行合理调整的情况下，并且高方差的信道有效性也会对此算法产生巨大的影响[14]，因此，相对于ε-greedy算法，UCB算法更容易实现稳定的性能。

图 3 3 种算法关于遗憾值的比较（C=9，U=3、4、5）

图 4 3 种算法关于遗憾值的比较（U=4，C=5、7、9）

（2）碰撞数

图5为3种算法碰撞数(M(n))性能的比较，可以观察到3种算法随着时隙数n的增加，M(n)/ln(n)趋近于定值，说明碰撞数也呈对数形式，从而碰撞数增长速度缓慢，UCB算法与ε-greedy算法在碰撞性能方面相差不多，而clusters-UCB算法的碰撞数大幅减小，并且收敛速度更快，这得益于改进的g索引值和簇内协作。因此，验证了clusters-UCB算法在碰撞数性能方面的优势。由于UCB算法碰撞数曲线的形式是由g值决定的，而ε-greedy算法碰撞数曲线形式是由探索概率ε决定的。因此，两者关于碰撞数趋于对数形式曲线的斜率并不相同，ε-greedy算法的曲线斜率略高于UCB算法。

（3）公平性

公平性的定义为使用信道接入算法后每个簇接入最佳信道的概率相同。图6显示了U=5，C=9，n=8 000，运行1 000次情况下的公平性，clusters-UCB算法的一个重要特性是不倾向于任意一个簇，每个簇具有同等的机会来访问具有最高有效性的U个信道，5个簇中的任意1个簇在1 000次运行过程中大约都有200次渐进地选择接入最佳信道。图6中每个簇选择最佳信道的概率大概相同，证明提出的防碰撞机制对于每个簇而言都是公平的。

图5 U=4情况下碰撞数性能的比较

图 6 公平性（U=5,C=9,n=8 000,运行 1 000次）

（4）时隙吞吐量

图7为3种算法关于时隙吞吐量性能的比较，从中可以观察到，3种算法都能渐近地实现最大时隙吞吐量，而提出的clusters-UCB算法由于改进了经典的UCB算法，随着时间的增加，变化幅度要快得多；由于簇内成员的协作使得时隙吞吐量大大增加，渐近地趋近于0.75，即4个最佳信道的有效性的平均值，由于感知误差的存在，结果比理想值小。

图7 3种算法关于时隙吞吐量性能的比较（U=4,C=9）

5 结束语

针对高密度车流环境下的认知车载网采用基于簇的通信模式能够扩大可使用认知信道的用户数，并且授权频谱的使用扩展了传输带宽；针对簇间多用户分布式信道感知和接入问题，提出了基于簇和MAB模型的UCB算法，提出了能适用于单用户UCB和ε-greedy算法的防碰撞机制；通过簇内成员协作提高感知结果的准确性并加快了学习速度；通过具有优化g索引值的改进UCB算法进一步降低了遗憾值并且学习速度进一步加快。搭建了认知车载网络中信道感知和接入的仿真模型并进行了仿真实验，提出的clusters-UCB算法相对于UCB算法以及ε-greedy算法能够大幅降低遗憾值，加快收敛到对数形式遗憾值的速度，降低碰撞数并保证接入信道的公平性，渐近地实现最大的系统吞吐量。

[1]HUANG X L,WU J,LI W,et al.Historical spectrum sensing data mining for cognitive radio enabled vehicular Ad Hoc networks[J].IEEE Transactions on Dependable& Secure Computing,2015,13(1):59-70.

[2]POONIAR C,BHARGAVAD,KUMAR BS.CDRA:cluster-based dynamic routing approach as a development of the AODV in vehicular Ad Hoc networks[C]//2015 International Conference on Signal Processing and Communication Engineering Systems (SPACES),Jan 2-3,2015,Guntur,India.New Jersey:IEEE Press,2015:397-401.

[3]GOONEWARDENE R T,ALI F H,STIPIDIS E.Robust mobility adaptive clustering scheme with support for geographic routing for vehicular Ad Hoc networks[J].IET Intelligent Transport Systems,2009,3(2):148-158.

[4]DONG S,LEE J.Greedy confidence bound techniques for restless multi-armed bandit based cognitive radio[C]//The 47th Annual Conference on Information Sciences and Systems(CISS),March 20-22,2013,Baltimore,MD,USA.New Jersey:IEEE Press,2013:1-4.

[5]朱江,陈红翠,熊加毫.基于多臂赌博机模型的信道选择[J].电讯技术,2015,55(10):1094-1100.ZHU J,CHEN H C,XIONG J H.Channel selection based on multi-armed bandit[J].Telecommunication Engineering,2015,55(10):1094-1100.

[6]KLEINBERG R,PILIOURAS G,TARDOS E.Multiplicative updates outperform generic no-regret learning in congestion games[J].Proc Stoc,2009:533-542.

[7]GAI Y,KRISHNAMACHARI B,JAIN R.Learning multiuser channel allocations in cognitive radio networks:a combinatorial multi-armed bandit formulation[C]//2010 IEEE Symposium on New Frontiers in Dynamic Spectrum Access Networks,April 6-9,2010,Singapore.New Jersey:IEEE Press,2010:1-9.

[8]AUER P,CESA-BIANCHI N,FISCHER P.Finite-time analysis of the multi-armed bandit problem[J].Machine Learning,2002,47(2-3):235-256.

[9]AGRAWAL R.Sample mean based index policies with O log n regret for the multiarmed bandit problem [J].Advances in Applied Probability,1995,27(4):1054-1078.

A novel channel access algorithm based on clusters and MAB model in cognitive vehicular network

PENG Fei,ZHANG Guoan,YANG Yuqi
School of Electronics and Information,Nantong University,Nantong 226019,China

Considering the cognitive channel access problem of vehicle nodes in cognitive vehicular networks with heavy traffic environment,a channel access algorithm called clusters-UCB which based on clusters and MAB model was proposed.The cooperation of cluster members could improve perception accuracy and enhance the learning speed.And using improved multi-user UCB algorithm,cluster heads could quickly search out the optimal channel in a distributed way,which could make the network asymptotically achieve the optimal slot throughput.Simulation results show that with respect to UCB algorithm and ε-greedy algorithm,the regret of the proposed algorithm is lower and the speed of approaching logarithmic form is faster.What’s more,clusters-UCB can effectively reduce the number of collisions when clusters access the cognitive channels,ensuring the fairness of the channel access and achieving better slot throughput.

cognitive vehicular network,cluster,channel access,MAB model,UCB algorithm

s:The National Natural Science Foundation of China (No.61371113,No.61401241),Project of Ministry of Transport of the People’s Republic of China(No.2013-319-825-110)

TN929.5

10.11959/j.issn.1000-0801.2016184

2016-03-03；

2016-07-05

国家自然科学基金资助项目(No.61371113,No.61401241)；交通运输部应用基础研究基金资助项目(No.2013-319-825-110)