認知車載網中基于簇和MAB模型的信道接入算法

彭飛，章國安，楊羽琦

（南通大學電子信息學院，江蘇 南通 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

A

10.11959/j.issn.1000-0801.2016184

2016-03-03；

2016-07-05

國家自然科學基金資助項目(No.61371113,No.61401241)；交通運輸部應用基礎研究基金資助項目(No.2013-319-825-110)

彭飛（1991-），男，南通大學電子信息學院碩士生，主要研究方向為認知車載網。

章國安（1965-），男，博士，南通大學電子信息學院教授、博士生導師，主要研究方向為無線通信網絡理論與技術。

楊羽琦（1993-），女，南通大學電子信息學院碩士生，主要研究方向為車載自組織網絡。