認(rèn)知車載網(wǎng)中基于簇和MAB模型的信道接入算法

彭飛，章國(guó)安，楊羽琦

（南通大學(xué)電子信息學(xué)院，江蘇 南通 226019）

認(rèn)知車載網(wǎng)中基于簇和MAB模型的信道接入算法

彭飛，章國(guó)安，楊羽琦

（南通大學(xué)電子信息學(xué)院，江蘇 南通 226019）

針對(duì)高密度車流環(huán)境下認(rèn)知車載網(wǎng)中車輛節(jié)點(diǎn)對(duì)認(rèn)知信道的接入問題，提出了基于簇和MAB模型的clusters-UCB信道接入算法，通過簇內(nèi)成員協(xié)作提高感知學(xué)習(xí)結(jié)果的準(zhǔn)確性，提升算法學(xué)習(xí)速度，并且簇首通過clusters-UCB算法分布式地快速搜索出最佳信道，漸近地實(shí)現(xiàn)最大的時(shí)隙吞吐量。仿真實(shí)驗(yàn)表明，提出的算法相對(duì)于多用戶的UCB算法和ε-greedy算法，遺憾值更低，并且趨近于對(duì)數(shù)形式的收斂速度更快，能夠有效減少訪問碰撞數(shù)，保證信道接入的公平性，提高時(shí)隙吞吐量。

認(rèn)知車載網(wǎng)；簇；信道接入；MAB模型；UCB算法

1 引言

在高密度的交通環(huán)境下或者支持高速率互聯(lián)網(wǎng)接入的車載網(wǎng)絡(luò)中，IEEE 802.11p標(biāo)準(zhǔn)中規(guī)定的5.9 GHz頻段的頻譜資源遠(yuǎn)遠(yuǎn)不能滿足車輛用戶的需求，認(rèn)知車載網(wǎng)的概念應(yīng)運(yùn)而生[1]。由于平面結(jié)構(gòu)的車輛自組織網(wǎng)絡(luò)在節(jié)點(diǎn)數(shù)量很大時(shí)，特別是在車輛節(jié)點(diǎn)高速移動(dòng)的環(huán)境下，會(huì)有較大的控制開銷，使得處理能力變?nèi)跎踔羵鬏斅窂街袛?，所以平面結(jié)構(gòu)不適用于高密度交通環(huán)境下的認(rèn)知車載網(wǎng)絡(luò)。因此，采用分級(jí)結(jié)構(gòu)更加合適，考慮基于簇的車輛通信模型[2]，如圖1所示，一個(gè)簇由一個(gè)簇首和多個(gè)簇成員組成。一個(gè)簇成員通信的數(shù)據(jù)最開始傳輸?shù)酱厥?，然后轉(zhuǎn)發(fā)到目的地，這個(gè)目的地可能是路邊單元 （roadside unit，RSU）或者一個(gè)相鄰的簇首。采用參考文獻(xiàn)[3]中高穩(wěn)定性的RMAC （robust mobility adaptive clustering）算法進(jìn)行分簇，根據(jù)鄰居節(jié)點(diǎn)的相對(duì)移動(dòng)度量值（速度、位置以及行駛方向）計(jì)算出節(jié)點(diǎn)優(yōu)先性，從而推舉出簇首，使得簇生存時(shí)間更長(zhǎng)。簇首維護(hù)兩跳范圍內(nèi)的節(jié)點(diǎn)列表，從而使得當(dāng)簇成員離開原來簇的時(shí)候優(yōu)先知道這一信息，以便快速加入新簇。

認(rèn)知車載網(wǎng)中存在兩種類型的信道，分別是認(rèn)知信道和專用信道，都可用于簇內(nèi)和簇間的通信。專用信道主要用于簇內(nèi)的廣播消息，而認(rèn)知信道在主用戶（primary user，PU）不占用的情況下供簇使用，主要用于緊急情況下的交通信息廣播和大流量視頻等娛樂信息的傳播。簇需要感知授權(quán)頻譜以檢測(cè)主用戶傳輸存在與否，然而由于資源和硬件的限制，簇只能夠在給定的時(shí)間內(nèi)感知部分頻譜，因此需要在有限的時(shí)間內(nèi)通過對(duì)以往信道有效性的學(xué)習(xí)來更快地找到最佳信道，以最大化時(shí)隙吞吐量進(jìn)行數(shù)據(jù)傳輸。機(jī)器學(xué)習(xí)（machine learning，ML）理論中的 MAB（multi-armed bandit）模型與認(rèn)知無線網(wǎng)絡(luò)頻譜分配之間存在相似性，經(jīng)典的MAB模型使用UCB（upper confidence bound）算法進(jìn)行搜索學(xué)習(xí)，因此UCB算法也被諸多參考文獻(xiàn)用來解決認(rèn)知信道的接入問題。參考文獻(xiàn)[4]研究了單用戶的信道信息服從獨(dú)立同分布變化時(shí)，用戶在多個(gè)信道中進(jìn)行選擇接入的問題，并提出了一種基于RMAB（restless multi-armed bandit）模型的決策方案。參考文獻(xiàn)[5]通過在UCB索引的置信因子中引入收益方差值來調(diào)整對(duì)未知信道環(huán)境的探索過程，以降低探索成本。參考文獻(xiàn)[6]以更快的速度使算法收斂于弱穩(wěn)定平衡，而這降低了幾乎所有游戲的純納什均衡，然而假設(shè)的是等效遺憾值而不是隨機(jī)遺憾值，并且用戶能夠完全觀察到其他用戶的行為。參考文獻(xiàn)[7]考慮組合賭博機(jī)，對(duì)于更加普遍的多個(gè)用戶、不同信道有效性的模型提出了一個(gè)匹配算法分配信道，這個(gè)算法保證了對(duì)于傳輸時(shí)隙而言對(duì)數(shù)形式的遺憾值。

然而，參考文獻(xiàn)[4,5]僅僅考慮了單用戶的情況，而認(rèn)知車載網(wǎng)中存在大量的車輛節(jié)點(diǎn)。參考文獻(xiàn)[6,7]中用戶之間進(jìn)行了信息交換，而不是分布式的方案，這增加了系統(tǒng)開銷并且不易于實(shí)現(xiàn)。大多數(shù)論文都考慮完美的感知情況，在認(rèn)知車載網(wǎng)的場(chǎng)景下，由于陰影效應(yīng)、多徑效應(yīng)等因素的影響，信道質(zhì)量很差，感知結(jié)果很可能是不正確的，因此有必要考慮不完美的感知情況。另外，希望提出的算法具有更小的遺憾值，遺憾值是衡量UCB算法的重要性能指標(biāo)，定義為與理想情況相比吞吐量的缺失，它可以指示學(xué)習(xí)算法的收斂速度。因此提出了適用于認(rèn)知車載網(wǎng)的、基于簇和MAB模型的信道接入算法，通過簇內(nèi)成員協(xié)作以提高感知的準(zhǔn)確性，簇首通過改進(jìn)的UCB算法分布式地搜索最佳信道，遺憾值較低并且趨近于對(duì)數(shù)形式的收斂速度更快，能夠有效減少簇間訪問碰撞數(shù)，并保證傳輸?shù)墓叫?，漸近地實(shí)現(xiàn)更大的時(shí)隙吞吐量。

圖1 認(rèn)知車載網(wǎng)中基于簇的通信模式

2 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)模型中信道模型、時(shí)隙結(jié)構(gòu)以及遺憾值這3個(gè)部分對(duì)于提出的信道接入算法而言尤為重要。信道模型涉及每個(gè)簇中簇首與簇內(nèi)成員對(duì)于認(rèn)知信道以及專用信道的接入模式，時(shí)隙結(jié)構(gòu)從時(shí)隙的角度對(duì)信道嘗試接入的詳細(xì)過程進(jìn)行細(xì)分，而遺憾值對(duì)于基于MAB模型的信道接入算法而言是一項(xiàng)重要的性能指標(biāo)。

2.1 信道模型

考慮由C個(gè)信道和U個(gè)簇組成的網(wǎng)絡(luò)模型。每個(gè)車輛節(jié)點(diǎn)都配備有認(rèn)知無線設(shè)備，可以感知和機(jī)會(huì)性地訪問授權(quán)頻譜?？紤]基于時(shí)隙的通信方式，時(shí)間分為離散的時(shí)隙 n=0，1，2，…。在第 k 個(gè)時(shí)隙信道 i空閑的概率為 μi，即信道i空閑的指示變量表示平均值為μ的伯努利分布。

令Ti,j(k)表示信道i在k個(gè)時(shí)隙中被簇j感知的總時(shí)隙數(shù)。對(duì)于授權(quán)頻譜覆蓋范圍內(nèi)的簇，這是因?yàn)槊總€(gè)簇在每個(gè)時(shí)隙只感知一條信道。在第k個(gè)時(shí)隙的開始階段，通過對(duì)以前接入結(jié)果的學(xué)習(xí)，每個(gè)簇首通知簇成員u感知信道i，由此獲得信道Wi(k)的值，來判斷信道i是否空閑。然后，簇內(nèi)成員將感知結(jié)果Ii,j(u,k)通過專用信道發(fā)送到簇首，Ii,j(u,k)為1表示在第k個(gè)時(shí)隙簇j內(nèi)的成員 u感知信道 i是空閑狀態(tài)，Ii,j(u,k)為 0表示感知結(jié)果為信道i是占用狀態(tài)。簇首會(huì)計(jì)算關(guān)于信道i的所有感知結(jié)果的和，usum為所有與簇首取得聯(lián)系的簇內(nèi)成員的總數(shù)（包括簇首），如果簇內(nèi)感知結(jié)果超過判決閾值ψ，則認(rèn)定信道狀態(tài)為空閑，否則為占用狀態(tài)，即：

如果兩個(gè)或更多的簇嘗試在同一個(gè)信道傳輸，那么沒有簇會(huì)傳輸成功。在第k個(gè)時(shí)隙的末尾階段，每個(gè)簇通過接收確認(rèn)信號(hào)Zj(k)來判定它在kth時(shí)隙的傳輸數(shù)據(jù)是否被成功接收，簇j記錄在k個(gè)時(shí)隙內(nèi)信道i被簇j成功接入的次數(shù)。因此，任何在第k+1時(shí)隙應(yīng)用在簇j的算法是基于所有簇成員之前的感知和反饋結(jié)果。然而，簇對(duì)ui的值并不清楚，所以必須學(xué)習(xí)這些值以最小化對(duì)主用戶和其他簇的干擾。

2.2 時(shí)隙結(jié)構(gòu)

將時(shí)隙分為4個(gè)階段，如圖2所示。

（1）決策階段 td

根據(jù)之前時(shí)隙的傳輸結(jié)果和學(xué)習(xí)算法，簇j決定下次傳輸使用哪個(gè)信道，并在專用信道把這些信息傳輸給簇內(nèi)成員。然后，每個(gè)簇內(nèi)成員將把收發(fā)機(jī)無線接口調(diào)整到信道i。

（2）感知階段 ts

每個(gè)簇內(nèi)成員感知信道i以檢測(cè)信道中主用戶是否存在。若信道i在當(dāng)前時(shí)隙k是空閑的，則Ii,j(u,k)=1，否則為0。不假設(shè)完美的感知，而是建模了感知的準(zhǔn)確度，對(duì)于信道i，簇成員u正確檢測(cè)的概率為，錯(cuò)誤檢測(cè)的概率為。簇內(nèi)成員u決策出信道i空閑的概率為：

（3）通信階段 tc

在感知階段后，簇內(nèi)成員在專用信道上廣播感知結(jié)果，簇首接收到所有成員u=1,…,usum的結(jié)果，計(jì)算簇j關(guān)于信道i在k個(gè)時(shí)隙內(nèi)所有感知結(jié)果的和，usum為簇內(nèi)成員的總數(shù)（包括簇首），使用式（1）進(jìn)行信道情況的判斷。

（4）傳輸階段 tx

如果簇首發(fā)現(xiàn)信道i是空閑的，則在信道i上進(jìn)行傳輸，否則不傳輸，等待下一個(gè)時(shí)隙選擇其他信道。當(dāng)成功傳輸后，它從接收器中接收 Zj(k)信號(hào)，若 Zj(k)中包含ACK消息，簇首進(jìn)行Xi,j(k)=Xi,j(k-1)+1運(yùn)算；假如發(fā)生主用戶干擾或者與其他簇發(fā)生碰撞，Zj(k)會(huì)包含NACK消息，則Xi,j(k)=Xi,j(k-1)。

2.3 遺憾值

學(xué)習(xí)算法的目標(biāo)是在對(duì)主用戶沒有造成干擾的情況下最大化簇傳輸成功數(shù)，從而提高時(shí)隙吞吐量。

定義時(shí)隙吞吐量為：

圖2 時(shí)隙結(jié)構(gòu)

其中，dsum表示在k個(gè)時(shí)隙內(nèi)U個(gè)簇感知的時(shí)隙總數(shù)，即U·k，dsuccess表示成功傳輸?shù)目倳r(shí)隙數(shù)。

令S(n;μ,U,ρ)表示U個(gè)簇在使用算法ρ的情況下于n個(gè)時(shí)隙后成功傳輸?shù)目倲?shù)。理想場(chǎng)景下信道有效性可知，即信道空閑概率μ可知，簇正交地接入較好的U個(gè)信道中。在n個(gè)時(shí)隙后估計(jì)成功傳輸次數(shù)為：

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

對(duì)于所有的算法 ρ和任意 n∈N，有 S*(n;μ,U)＞S(n;μ,U,ρ)。目標(biāo)是在學(xué)習(xí)和訪問中最小化遺憾值，即：使R(n)在任意給定的μ∈(0,1)下最小。其中：

其中，Vi,j(n)表示在n個(gè)時(shí)隙內(nèi)簇j是唯一感知信道i的簇的時(shí)隙數(shù)。因此，式（5）為：

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

3.1 經(jīng)典的UCB算法

在單用戶、多信道的情況下，用戶如何選擇信道實(shí)現(xiàn)最大時(shí)隙吞吐量的問題轉(zhuǎn)化為了一個(gè)簡(jiǎn)單的MAB模型，解決這種問題最簡(jiǎn)單的方法就是經(jīng)典的單用戶UCB算法[8]。索引值g由兩部分構(gòu)成，前一部分表示信道i的平均估計(jì)有效性，而后一部分是置信因子，使得每個(gè)信道經(jīng)過足夠次數(shù)的有效性學(xué)習(xí)。

其中，Ti(n)表示n個(gè)時(shí)隙內(nèi)信道i被感知的總次數(shù)。

其中，Xi(k)表示在n個(gè)時(shí)隙內(nèi)成功接入信道i的時(shí)隙數(shù)。

對(duì)于信道i，當(dāng)時(shí)隙數(shù)n較小時(shí)，置信因子的值很大，感知次數(shù)越少的信道的置信因子值越大，下一個(gè)時(shí)隙就越可能感知該信道；當(dāng)時(shí)隙數(shù)n很大時(shí)，置信因子的值很小，索引值的大小關(guān)鍵在于第一部分，即索引值的大小取決于信道的有效性。

算法1 單用戶UCB算法ρ1(g(n))

定義 {Xi(n)}i=1,2,…,C表示在 n個(gè)時(shí)隙后信道 i的平均估計(jì)有效性，g(i;n)表示基于i(n)的索引值，σ(a;g(n))表示對(duì)于單用戶a而言，具有最大g(n)的信道號(hào)，Curr_Sel表示準(zhǔn)備接入的信道號(hào)。

初始化：每個(gè)信道感知一次，n←C,Curr_Sel←C。循環(huán)：n←n+1

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

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

if感知信道Curr_Sel為空閑狀態(tài)，then

XCurr_Sel(n)=XCurr_Sel(n-1)+1，在該信道傳輸；

else

XCurr_Sel(n)=XCurr_Sel(n-1)，等待下一個(gè)時(shí)隙進(jìn)行數(shù)據(jù)傳輸；

end

更新所有信道的索引值 g(i;n)，i=1，2，…，C。由參考文獻(xiàn)[8]可知，隨著時(shí)隙數(shù)的增加，UCB算法的遺憾值漸進(jìn)地趨向于對(duì)數(shù)形式，而不是線性形式，因而遺憾值增長(zhǎng)速度較慢。

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

基于第3.1節(jié)經(jīng)典的單用戶UCB算法，提出了clusters-UCB算法，主要在如下3方面做出改進(jìn)。

（1）提出了隨機(jī)化的防碰撞機(jī)制，在單用戶的UCB算法的基礎(chǔ)上引入碰撞指示變量，簇可以采用隨機(jī)化信道訪問，以避免簇與簇之間的碰撞，并且不同于將感知結(jié)果作為學(xué)習(xí)對(duì)象，將接入結(jié)果作為學(xué)習(xí)對(duì)象，這樣可以防止每個(gè)簇都加入同一個(gè)具有最高有效性的信道。如果某一簇在上一個(gè)時(shí)隙發(fā)生碰撞，則在此時(shí)隙會(huì)重新隨機(jī)選擇一個(gè)信道，經(jīng)過有限次的碰撞后，簇能夠正交地選擇沒有其他簇干擾的最佳信道；如果上一個(gè)時(shí)隙沒有發(fā)生碰撞，則不需重新選擇信道。這種機(jī)制也適用于ε-greedy算法，從而將單用戶的情況擴(kuò)展到多用戶的情況。

（2）由分布式的訪問模式改變?yōu)榇貎?nèi)協(xié)作感知、簇間分布式接入的模式，簇內(nèi)成員共享同一個(gè)認(rèn)知信道，屬于交叉位置的成員可以訪問多個(gè)認(rèn)知信道。這種基于簇的通信方式有效地?cái)U(kuò)展了可以參與認(rèn)知信道訪問的用戶數(shù)，適用于高密度的車載網(wǎng)絡(luò)，并且簇內(nèi)協(xié)作有效地提高了感知結(jié)果的正確性，降低了對(duì)主用戶的干擾。并且考慮協(xié)作帶來的系統(tǒng)開銷，簇首發(fā)出所需感知信道的ID給每個(gè)簇成員，并且每個(gè)簇成員在每個(gè)時(shí)隙只發(fā)出1 bit的感知結(jié)果，因此協(xié)作的開銷僅僅為包含有感知信道ID號(hào)以及1 bit感知結(jié)果的數(shù)據(jù)分組，因此協(xié)作帶來的系統(tǒng)開銷很小。

（3）索引值g采用最優(yōu)化的度量[9]，改進(jìn)了UCB算法，將g由原來的更改為大大降低了遺憾值和碰撞數(shù)，更快地實(shí)現(xiàn)最大的時(shí)隙吞吐量。

定義 用戶數(shù)為U，信道數(shù)為C，Xi,j(n)表示在n個(gè)時(shí)隙后簇j成功接入信道i的時(shí)隙數(shù)，{i,j(n)}i=1,…,C表示在 n 個(gè)時(shí)隙后簇j對(duì)于信道i的平均估計(jì)有效性，Ti,j(n)表示簇j選擇感知信道i的時(shí)隙數(shù)(i;n)表示基于i,j(n)的第 n個(gè)時(shí)隙簇j對(duì)于信道i的g索引值，σ(gj(n))表示對(duì)于簇j而言具有最大g索引值的信道號(hào)，ζj(i;n)表示簇j在信道i上第n個(gè)時(shí)隙的碰撞指示變量，Curr_channel表示簇j當(dāng)前選擇的信道號(hào)。

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

循環(huán)：n←n+1；

Curr_channel←σ(gj(n))；

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

選擇一個(gè)新的 Curr_channel～Unif(C)；

end

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

選擇信道Curr_channel來感知，簇首廣播信道號(hào)Curr_channel給簇成員；

if 通過式（1）的計(jì)算發(fā)現(xiàn)信道Curr_channel是空閑的，then

接入信道Curr_channel；

if傳輸成功，then

ζj(Curr_channel;m)←0；

end

從clusters-UCB算法中可以看出，如果時(shí)隙數(shù)夠多，由于某些簇長(zhǎng)期占用某些信道，導(dǎo)致這些信道的有效性下降，從而對(duì)于其他簇而言，這些原本信道有效性可能高的信道將獲得較小的g索引值，因此，通過算法的學(xué)習(xí)，每個(gè)簇只會(huì)選擇對(duì)于自身而言具有最高g索引值的信道。

4 性能評(píng)估

假設(shè)信道數(shù)用C表示，信道的有效性由具有等間隔參數(shù){0.9,0.8,…,0.2,0.1}的伯努利分布表示，例如C=3，那么信道有效性為{0.9,0.8,0.7}，簇?cái)?shù)用U表示。為方便分析，假設(shè)簇在仿真期間不會(huì)發(fā)生重組，即簇內(nèi)成員數(shù)不會(huì)發(fā)生改變，假設(shè)簇內(nèi)成員數(shù)u=5，假設(shè)每個(gè)車輛節(jié)點(diǎn)感知的準(zhǔn)確性相同，即假設(shè)感知判決閾值ψ=U/2。每次仿真都運(yùn)行100次并取100次結(jié)果的平均值，在遺憾值、碰撞數(shù)、公平性以及時(shí)隙吞吐量方面將clusters-UCB算法與UCB算法、ε-greedy算法進(jìn)行比較。

（1）遺憾值

圖3和圖4都顯示了3種算法關(guān)于遺憾值的性能比較，圖3顯示固定信道數(shù)C=9不變，U=3、4、5個(gè)簇的情況，圖4顯示固定簇?cái)?shù)U=4不變，信道數(shù)C=5、7、9的情況。3種算法的遺憾值對(duì)于時(shí)隙都漸近地呈對(duì)數(shù)形式而非線性形式。此外，還可以觀察到當(dāng)信道數(shù)不變，簇?cái)?shù)越多，遺憾值越大，收斂時(shí)間越長(zhǎng)，這是由于多個(gè)簇的競(jìng)爭(zhēng)導(dǎo)致接入較差信道的概率越大，越不容易接入彼此正交的信道；固定簇?cái)?shù)不變，信道數(shù)越多，遺憾值越大，這是因?yàn)榇乜蛇x擇的信道更多，發(fā)生碰撞時(shí)均勻隨機(jī)地選擇信道，使得簇也容易接入較差的信道，這樣也會(huì)增加遺憾值。比較而言，在遺憾值方面，clusters-UCB算法要明顯優(yōu)于多用戶UCB算法、ε-greedy算法，由于簇內(nèi)用戶的協(xié)作以及UCB改進(jìn)搜索算法的優(yōu)勢(shì)，clusters-UCB算法的遺憾值要比其他兩種算法的值小，并且學(xué)習(xí)更快，即曲線的斜率越大。還可以觀察到ε-greedy算法比UCB算法更優(yōu)，但這是在參數(shù)進(jìn)行合理調(diào)整的情況下，并且高方差的信道有效性也會(huì)對(duì)此算法產(chǎn)生巨大的影響[14]，因此，相對(duì)于ε-greedy算法，UCB算法更容易實(shí)現(xiàn)穩(wěn)定的性能。

圖 3 3 種算法關(guān)于遺憾值的比較（C=9，U=3、4、5）

圖 4 3 種算法關(guān)于遺憾值的比較（U=4，C=5、7、9）

（2）碰撞數(shù)

圖5為3種算法碰撞數(shù)(M(n))性能的比較，可以觀察到3種算法隨著時(shí)隙數(shù)n的增加，M(n)/ln(n)趨近于定值，說明碰撞數(shù)也呈對(duì)數(shù)形式，從而碰撞數(shù)增長(zhǎng)速度緩慢，UCB算法與ε-greedy算法在碰撞性能方面相差不多，而clusters-UCB算法的碰撞數(shù)大幅減小，并且收斂速度更快，這得益于改進(jìn)的g索引值和簇內(nèi)協(xié)作。因此，驗(yàn)證了clusters-UCB算法在碰撞數(shù)性能方面的優(yōu)勢(shì)。由于UCB算法碰撞數(shù)曲線的形式是由g值決定的，而ε-greedy算法碰撞數(shù)曲線形式是由探索概率ε決定的。因此，兩者關(guān)于碰撞數(shù)趨于對(duì)數(shù)形式曲線的斜率并不相同，ε-greedy算法的曲線斜率略高于UCB算法。

（3）公平性

公平性的定義為使用信道接入算法后每個(gè)簇接入最佳信道的概率相同。圖6顯示了U=5，C=9，n=8 000，運(yùn)行1 000次情況下的公平性，clusters-UCB算法的一個(gè)重要特性是不傾向于任意一個(gè)簇，每個(gè)簇具有同等的機(jī)會(huì)來訪問具有最高有效性的U個(gè)信道，5個(gè)簇中的任意1個(gè)簇在1 000次運(yùn)行過程中大約都有200次漸進(jìn)地選擇接入最佳信道。圖6中每個(gè)簇選擇最佳信道的概率大概相同，證明提出的防碰撞機(jī)制對(duì)于每個(gè)簇而言都是公平的。

圖5 U=4情況下碰撞數(shù)性能的比較

圖 6 公平性（U=5,C=9,n=8 000,運(yùn)行 1 000次）

（4）時(shí)隙吞吐量

圖7為3種算法關(guān)于時(shí)隙吞吐量性能的比較，從中可以觀察到，3種算法都能漸近地實(shí)現(xiàn)最大時(shí)隙吞吐量，而提出的clusters-UCB算法由于改進(jìn)了經(jīng)典的UCB算法，隨著時(shí)間的增加，變化幅度要快得多；由于簇內(nèi)成員的協(xié)作使得時(shí)隙吞吐量大大增加，漸近地趨近于0.75，即4個(gè)最佳信道的有效性的平均值，由于感知誤差的存在，結(jié)果比理想值小。

圖7 3種算法關(guān)于時(shí)隙吞吐量性能的比較（U=4,C=9）

5 結(jié)束語(yǔ)

針對(duì)高密度車流環(huán)境下的認(rèn)知車載網(wǎng)采用基于簇的通信模式能夠擴(kuò)大可使用認(rèn)知信道的用戶數(shù)，并且授權(quán)頻譜的使用擴(kuò)展了傳輸帶寬；針對(duì)簇間多用戶分布式信道感知和接入問題，提出了基于簇和MAB模型的UCB算法，提出了能適用于單用戶UCB和ε-greedy算法的防碰撞機(jī)制；通過簇內(nèi)成員協(xié)作提高感知結(jié)果的準(zhǔn)確性并加快了學(xué)習(xí)速度；通過具有優(yōu)化g索引值的改進(jìn)UCB算法進(jìn)一步降低了遺憾值并且學(xué)習(xí)速度進(jìn)一步加快。搭建了認(rèn)知車載網(wǎng)絡(luò)中信道感知和接入的仿真模型并進(jìn)行了仿真實(shí)驗(yàn)，提出的clusters-UCB算法相對(duì)于UCB算法以及ε-greedy算法能夠大幅降低遺憾值，加快收斂到對(duì)數(shù)形式遺憾值的速度，降低碰撞數(shù)并保證接入信道的公平性，漸近地實(shí)現(xiàn)最大的系統(tǒng)吞吐量。

[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ī)模型的信道選擇[J].電訊技術(shù),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

A

10.11959/j.issn.1000-0801.2016184

2016-03-03；

2016-07-05

國(guó)家自然科學(xué)基金資助項(xiàng)目(No.61371113,No.61401241)；交通運(yùn)輸部應(yīng)用基礎(chǔ)研究基金資助項(xiàng)目(No.2013-319-825-110)

彭飛（1991-），男，南通大學(xué)電子信息學(xué)院碩士生，主要研究方向?yàn)檎J(rèn)知車載網(wǎng)。

章國(guó)安（1965-），男，博士，南通大學(xué)電子信息學(xué)院教授、博士生導(dǎo)師，主要研究方向?yàn)闊o線通信網(wǎng)絡(luò)理論與技術(shù)。

楊羽琦（1993-），女，南通大學(xué)電子信息學(xué)院碩士生，主要研究方向?yàn)檐囕d自組織網(wǎng)絡(luò)。