頻譜感知次序的在線最優(yōu)選擇

周 敏，王少尉

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

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

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

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

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

1 問(wèn)題描述

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

1.1 頻譜感知次序問(wèn)題

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

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

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

(1)

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

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

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

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

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

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

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

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

(2)

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

(3)

其中

(4)

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

(5)

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

(6)

(7)

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

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

(8)

3 仿真結(jié)果及分析

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

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

圖2 ξ對(duì)平均每個(gè)時(shí)隙后悔值的影響Fig.2 Effect of ξ on the average per time slot regret

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

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

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

表1 μi的先驗(yàn)信息

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

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

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

4 結(jié)論

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