周 敏，王少尉

(南京大學 電子科學與工程學院， 江蘇 南京 210023)

大部分可用的頻譜資源被授權給了特定的應用，如廣播電視、移動通信等。在過去的幾十年里，移動數(shù)據(jù)流量快速增長，引發(fā)了頻譜資源短缺問題。此外，調查表明，授權給特定應用的頻譜未被充分利用，部分授權頻譜在時間和空間尺度上是空閑的，這導致了頻譜的利用效率低下。在不干擾授權用戶(主用戶)的前提下，認知無線電允許次級用戶動態(tài)地接入空閑的授權頻譜進行數(shù)據(jù)傳輸[1-2]。動態(tài)頻譜接入是解決頻譜資源短缺和利用效率低問題的潛在方案[3]，引起了廣泛關注。

頻譜感知是實現(xiàn)動態(tài)頻譜接入的前提。然而，由于硬件的限制[4]，次級用戶無法在很寬的頻譜范圍內進行感知。因此，頻譜感知次序在認知無線電系統(tǒng)中是一個重要的問題，次級用戶需要在給定的時間內確定優(yōu)先感知哪個頻段，盡快找到空閑信道進行數(shù)據(jù)傳輸，從而縮短頻譜感知時間，充分利用頻譜資源。理想情況下，為了獲得更多的頻譜接入機會，次級用戶應該優(yōu)先感知頻譜空閑概率最高的頻段。在信道空閑概率已知的前提下，文獻[5]提出了一種按照概率下降次序感知信道的方法。在信道空閑概率未知的情況下，文獻[6]采用Q學習方法來提高系統(tǒng)性能。文獻[7]提出了一種兩階段學習算法，該算法利用強化學習進行信道選擇，減少感知信道的時間。

然而，上述方法無法同時處理以下兩種情況：給定頻段的頻譜空閑概率通常是不可知的；即使可以通過長時間的觀察來預測頻譜空閑概率，這一概率也隨時會發(fā)生變化。在這種情況下，可能會使用過時的信息進行決策，導致系統(tǒng)性能的下降。因此，需要建立合理的頻譜感知模型并利用有效的算法來跟蹤頻譜空閑概率的變化。

本文研究了多個頻段間的頻譜感知次序問題，每個頻段的頻譜空閑概率不同且其統(tǒng)計規(guī)律在時間尺度上是變化的。提出了基于在線學習[8]的頻譜感知次序最優(yōu)選擇：利用在線學習的框架，邊探索邊利用，在利用歷史信息進行決策的同時，考慮利用探索獲取的新信息對未來決策的影響，待解決的問題可以看作經(jīng)典多搖臂賭博機問題，并引入滿意折現(xiàn)湯普森抽樣(Satisficing Discounted Thompson Sampling, SDTS)算法[9-10]處理優(yōu)化問題。

1 問題描述

本文研究了頻譜感知次序問題，也可以說是多頻段間的信道選擇問題。因為在同一時間、同一地區(qū)接入每個頻段的用戶數(shù)不同，所以每個頻段的頻譜空閑概率不同。此外，由于用戶的移動性，空閑概率在一段時間后會發(fā)生變化。假設次級用戶有多個可能接入的頻段，但是由于硬件限制，次級用戶無法感知很寬的頻譜。同時，假設在給定的時隙內，次級用戶只能感知同一頻段內的信道。因此，目標是動態(tài)選擇一個頻段進行感知，從而得到更多無主用戶活動的信道，以便次級用戶傳輸數(shù)據(jù)。

1.1 頻譜感知次序問題

考慮有N個頻段且每個頻段劃分為C個互不重疊的信道。研究了T時隙內次級用戶利用空閑信道得到的總數(shù)據(jù)吞吐量。頻段i在時隙t的頻譜空閑概率記作μi，其中i∈{1,2,…,N}。在實際場景中，同一頻段內各個信道的空閑概率可能各不相同。假設在時隙t，頻段i的第c個信道的回報記作Hi,c，服從期望為μi的伯努利分布，其中c∈{1,2,…,C}。也就是說，如果信道c空閑，則Hi,c=1，否則Hi,c=0。系統(tǒng)模型如圖1所示。μi不能提前得知且會隨著時間的推移發(fā)生變化，因此考慮利用在線學習框架完成頻譜感知任務。

圖1 系統(tǒng)模型示例Fig.1 An example of the system model

在時隙t，次級用戶選擇頻段i進行頻譜感知，其中t∈{1,2,…,T}，i∈{1,2,…,N}。根據(jù)上文Hi,c的定義，獲得的空閑信道數(shù)服從二項分布。因此，在時隙t，頻段i的期望空閑信道數(shù)為Cμi。次級用戶需要在多個頻段間動態(tài)選擇，從而最大化T時隙內總期望空閑信道數(shù)目，因此，優(yōu)化問題可表示為

(1)

其中，下標i(t)表示在時隙t，次級用戶所選頻段的索引。在該優(yōu)化問題中，要求次級用戶提前選擇一系列頻段使累積空閑信道最多。每個時隙得到的空閑信道數(shù)和未知的頻譜空閑概率有關，這一概率可以通過在線學習的方式獲得。根據(jù)上述描述，頻譜感知次序問題可以歸約為經(jīng)典多搖臂賭博機問題。

1.2 經(jīng)典多搖臂賭博機模型

考慮一個有N個搖臂(決策項)的賭博機(決策問題)。決策者共需進行T次決策。在每個階段，當選擇搖臂i后，產(chǎn)生的回報服從期望為μi的伯努利分布，且該回報立即被決策者觀察到。每個階段選擇的搖臂產(chǎn)生的回報是獨立同分布的。經(jīng)典多搖臂賭博機[11]算法根據(jù)前t-1次決策的回報決定第t次決策選擇哪一個搖臂。這個問題的目標是最大化T時隙內的總期望回報。頻譜感知次序問題中供選擇的頻段可以看作是經(jīng)典多搖臂賭博機模型中的一個搖臂。為了在T時隙內獲得更多的數(shù)據(jù)傳輸機會，次級用戶需要動態(tài)選擇最優(yōu)的頻段并進行頻譜感知，從而最大化總期望空閑信道數(shù)目，這等價于經(jīng)典多搖臂賭博機問題中最大化總期望回報。不同之處在于：經(jīng)典多搖臂賭博機問題中，每個搖臂產(chǎn)生的回報是0或1；而優(yōu)化問題中的回報，即空閑信道數(shù)，是隨機分布在[0,C]的整數(shù)。考慮先將優(yōu)化問題中的回報縮放至[0,1]，再進行一次成功概率為縮放后回報的伯努利實驗[12]，二值變量ri為伯努利實驗的觀測結果。伯努利實驗的期望回報為μi。經(jīng)過縮放處理后，可以使用經(jīng)典多搖臂賭博機的相關算法處理優(yōu)化問題。

2 滿意折現(xiàn)湯普森抽樣算法

湯普森抽樣算法[13]是處理經(jīng)典多搖臂賭博機問題的有效算法。它根據(jù)過去時隙選擇的搖臂及相應回報在當前時隙做出決策。文獻[14]給出了湯普森抽樣算法的后悔上界和性能保證的理論分析?，F(xiàn)有的大多數(shù)關于多搖臂賭博機問題的文獻的目標是快速收斂到最優(yōu)決策以減小探索成本。但由于優(yōu)化問題中每個搖臂產(chǎn)生的回報服從分布的參數(shù)是動態(tài)變化的，存在達到收斂之前最優(yōu)決策已經(jīng)發(fā)生變化的情況，也就是說，相對于次優(yōu)決策，找到最優(yōu)決策的代價過大，因此，在文獻[9]提出的適用于非平穩(wěn)搖臂的折現(xiàn)湯普森抽樣算法的基礎上，引入了滿意湯普森抽樣算法[10]。它的目標是確定一個足夠滿意或者足夠接近最優(yōu)的決策。

由于μi未知，滿意折現(xiàn)湯普森抽樣算法使用B(1,1)，即均勻分布作為其先驗分布。在時隙t，頻段i先前已接入成功Si次(即ri=1)，接入失敗Fi次(即ri=0)。頻段i回報的后驗分布更新為B(Si+1,Fi+1)，并作為下一時隙決策的先驗分布。滿意折現(xiàn)湯普森抽樣算法的時間復雜度為O(NT)。在每個時隙，次級用戶決定選擇哪一個頻段的具體步驟如算法1所示，其中超參數(shù)γ控制對頻段的Si(或Fi)的置信度，防止由于某個頻段的Si過大而出現(xiàn)總是選擇這個頻段的現(xiàn)象，即使該頻段不是頻譜空閑概率最大的。超參數(shù)ξ是一個容限參數(shù)，表示可以接受的滿意決策與最優(yōu)決策的差距。如果ξ=0，滿意折現(xiàn)湯普森抽樣與湯普森抽樣相同，否則，滿意折現(xiàn)湯普森抽樣傾向于選擇過去時隙已經(jīng)選擇過的頻段。特別是當最優(yōu)決策需要很長時間才能學到而滿意決策可以很快學到的時候，滿意折現(xiàn)湯普森抽樣算法可以快速達到接近最優(yōu)的性能，而湯普森抽樣算法需要繼續(xù)探索來確定最優(yōu)決策，會產(chǎn)生較大的性能損失。下面將通過推導展示使用滿意折現(xiàn)湯普森抽樣方法解決優(yōu)化問題的合理性。

算法1 滿意折現(xiàn)湯普森抽樣

假設觀測向量Ri包含頻段i被選后到當前時隙的所有觀測結果ri，觀測結果的產(chǎn)生方式1.2節(jié)已經(jīng)給出。因此，Ri的似然概率為

(2)

滿意折現(xiàn)湯普森抽樣算法使用貝塔分布作為參數(shù)μi的先驗分布，而貝塔分布是式(2)中似然函數(shù)的共軛分布，根據(jù)貝葉斯準則，μi的后驗分布為

(3)

其中

(4)

參數(shù)αi和βi決定了貝塔分布的均值和方差。將式(2)和式(4)代入式(3)，有

(5)

令H=Γ(αi+βi)/[Γ(αi)Γ(βi)pi(Ri)]，有

(6)

(7)

這符合參數(shù)為Si+αi和Fi+βi的貝塔分布。所以μi的后驗概率可以根據(jù)下式更新，即

pi(μi|Ri)=B(Si+αi,Fi+βi)

(8)

3 仿真結果及分析

假設有5個待選的頻段，每個頻段劃分為C=20個互不重疊的信道。頻段i的頻譜空閑概率μi服從標準均勻分布，即μi是從以(0,1)為界的均勻分布中采樣得到的。頻段i的每個信道根據(jù)成功概率為μi的伯努利分布產(chǎn)生回報。通過和其他具有代表性的算法，即折現(xiàn)ε-貪心算法(Discountedε-greedy)，折現(xiàn)湯普森抽樣[8](Discounted Thompson Sampling, DTS)和折現(xiàn)信心上界算法[15](Discounted Upper Confidence Bound, Discounted-UCB)進行比較，可以看出滿意折現(xiàn)湯普森抽樣算法的性能有一定的提升。在折現(xiàn)ε-貪心算法[16]中，每次決策次級用戶以1-ε的概率選擇當前時隙平均回報最大的頻段；以概率ε隨機選擇一個頻段。仿真過程中，設置ε=0.1。在折現(xiàn)信心上界算法中，引入了“信心上界指標”，該指標是回報的經(jīng)驗分布簡單函數(shù)。次級用戶先依次選擇每個頻段，在t>5的任意時隙，選擇信心上界指標最大的頻段進行頻譜感知。為了處理非平穩(wěn)多搖臂賭博機問題，在標準信心上界算法的基礎上，折現(xiàn)信心上界算法利用歷史回報計算當前時隙的期望回報時引入了折現(xiàn)因子，使得距離當前時隙較近時隙的回報權重更高。折現(xiàn)ε-貪心算法采用和折現(xiàn)信心上界算法相同的折現(xiàn)方法計算即時期望回報。

考慮了滿意折現(xiàn)湯普森抽樣算法中不同大小的容限參數(shù)ξ對平均每個時隙后悔值的影響。μi在200個時隙內保持不變，超參數(shù)γ等于1。考慮到每個頻段的回報在0到1之間，ξ分別取0.01, 0.05, 0.10和0.15。對于每個頻段i，μi分別是{0.23, 0.10, 0.28, 0.32}。進行了100次蒙特卡洛模擬取平均得到仿真結果。平均每個時隙的后悔值定義為后驗最優(yōu)決策和所提算法決策的累積期望回報差值與所經(jīng)歷時隙的比值。如果次級用戶可以提前得知μi的先驗信息，那么總是選擇頻段5，即μi最大的頻段進行頻譜感知是后驗最優(yōu)決策。圖2展示了不同ξ對平均每個時隙后悔值的影響。從圖2可以看出，對于不同的ξ值，平均每個時隙的后悔值都能達到一個較小的值，且隨著ξ的增大，后悔值會先減小再增大，ξ設為0.05時，后悔值最小。這是因為，當ξ較小時，隨著ξ的增大，算法可以較快地從歷史決策中找出和最優(yōu)決策回報差距較小的滿意決策，避免為了尋找回報更大的決策繼續(xù)探索導致當前后悔的增加，減小了探索成本，后悔值減??；但是超過一定閾值后，ξ繼續(xù)增大，符合容限范圍的滿意決策會更快找到，因而過早停止探索，不斷執(zhí)行和最優(yōu)決策差距較大的決策而錯過回報更大的決策，導致后悔值增大。因此，在后續(xù)的仿真過程中，將超參數(shù)ξ設為0.05。

圖2 ξ對平均每個時隙后悔值的影響Fig.2 Effect of ξ on the average per time slot regret

圖3 μi不變時歸一化吞吐量關于時隙的函數(shù)Fig.3 Normalized throughput as a function of the number of time slots with fixed μi

圖3展示了當μi在200個時隙內保持不變時歸一化吞吐量關于時隙的函數(shù)，其中歸一化吞吐量定義為所用算法得到的總空閑信道數(shù)與后驗最優(yōu)決策得到的總空閑信道數(shù)的比值。各頻段的μi分別是{0.20, 0.04, 0.37, 0.35, 0.06}。如果該信息能夠提前得知，那么可以推斷200個時隙內總是選擇頻段3是后驗最優(yōu)決策。顯然，后驗最優(yōu)決策的歸一化吞吐量始終為1。從圖3可以看出，經(jīng)過一定的時間，根據(jù)滿意折現(xiàn)湯普森抽樣算法進行決策得到的累積空閑信道數(shù)只比后驗最優(yōu)決策得到的少5%，而這一方法不需要知道頻譜空閑概率的先驗信息，這在實際應用中有很大的優(yōu)勢。此外，和折現(xiàn)湯普森抽樣算法、折現(xiàn)信心上界算法、折現(xiàn)ε-貪心算法相比，所提算法的吞吐量更大，這是因為它傾向于更快地選擇頻譜空閑概率最大的頻段，從而給次級用戶提供更多接入空閑信道的機會，進行數(shù)據(jù)傳輸。

研究了非穩(wěn)態(tài)場景下累積空閑信道關于時隙的函數(shù)。假設μi每200個時隙變化一次，在2000個時隙內共變化10次。μi的先驗信息如表1所示，其中k代表μi第k次發(fā)生變化。一系列仿真結果顯示，超參數(shù)γ等于0.99時得到的空閑信道更多，因此為了應對0.99動態(tài)變化的場景，超參數(shù)γ設為0.99。圖4給出了μi變化時累積空閑信道關于時隙的函數(shù)。從圖4可以看出，根據(jù)后驗最優(yōu)決策選擇頻段，也就是總是選擇μi最大的頻段進行頻譜感知，獲得的累積空閑信道最多。但是，在μi動態(tài)變化且對次級用戶不可知的情況下，滿意折現(xiàn)湯普森抽樣算法得到的空閑信道數(shù)只比后驗最優(yōu)決策得到的少9%，且比其他經(jīng)典算法至少多4%，這說明每次μi發(fā)生變化時，滿意折現(xiàn)湯普森抽樣算法都能適應μi的變化，較快地找到滿意決策。

表1 μi的先驗信息

圖5展示了非穩(wěn)態(tài)場景下平均每個時隙的后悔值關于時隙的函數(shù)。這個后悔值反映了后驗最優(yōu)決策和所提算法決策之間的性能差距，可以看作是算法的跟蹤誤差。如圖5所示，雖然μi每隔一定時隙會發(fā)生變化，但是經(jīng)過一定的時隙，每個算法的平均后悔值都會達到一個比較小且相對穩(wěn)定的值。而且，所提滿意折現(xiàn)湯普森抽樣算法的平均后悔值比其他算法更小、更穩(wěn)定。這是因為每次頻譜空閑概率發(fā)生變化時，滿意折現(xiàn)湯普森抽樣算法都能夠比其他算法更快地找到概率最大的頻段，跟蹤性能更優(yōu)。

圖4 μi變化時累積空閑信道關于時隙的函數(shù)Fig.4 Cumulative number of idle channels as a function of the number of time slots with time-varying μi

圖5 μi變化時平均每個時隙的后悔值關于時隙的函數(shù)Fig.5 Average per time slot regret as a function of the number of time slots with time-varying μi

4 結論

本文研究了在頻譜空閑概率的先驗信息不可知且動態(tài)變化的情況下，認知無線電中次級用戶在多頻段間的頻譜感知次序選擇問題。這個問題被歸納成一個動態(tài)的在線學習模型，即多搖臂賭博機問題。在湯普森抽樣算法的基礎上，提出了一種滿意折現(xiàn)湯普森抽樣算法處理該問題。仿真結果顯示，該算法得到的空閑信道數(shù)和后驗最優(yōu)決策得到的相近。與經(jīng)典的信息上界算法和折現(xiàn)ε-貪心算法相比，本文所提算法獲得的空閑信道更多。此外，所提算法還能夠跟蹤頻譜空閑概率的動態(tài)變化。