徐德艷，李 勇，程 偉

（西北工業(yè)大學(xué) 電子信息學(xué)院，陜西 西安 710100）

隨著無(wú)線通信服務(wù)需求的快速增長(zhǎng)，頻譜已變的越來(lái)越擁擠?，F(xiàn)有的頻譜分配政策表明，幾乎所有的可用頻譜都已被占用。但是，被授權(quán)的頻譜不會(huì)在任何時(shí)候都被主用戶占用，在被占用的授權(quán)頻譜中尋求可供次用戶使用的頻譜機(jī)會(huì)（即所謂的“頻譜空洞”），是一種有效的解決頻譜資源稀缺的辦法。1999年，Joseph Mitola博士提出了認(rèn)知無(wú)線電[1]（Cognitive Radio）的概念，其核心就是：CR用戶（次用戶）具有學(xué)習(xí)能力，能與周圍環(huán)境交互信息，以感知和利用在該空間的可用頻譜，并限制和降低沖突的發(fā)生。當(dāng)認(rèn)知用戶檢測(cè)到可用頻譜時(shí)，需要即時(shí)進(jìn)行接入。然而，如何接入、以怎樣的方式接入，這是一個(gè)極具挑戰(zhàn)性的問(wèn)題。為解決這個(gè)問(wèn)題，DAPRA XG研究小組提出了機(jī)會(huì)頻譜接入（Opportunity Spectrum Access，OSA）的概念。

目前，已有不少學(xué)者研究了認(rèn)知無(wú)線電頻譜接入問(wèn)題，文獻(xiàn)[2]中作者提出了一種基于硬件約束的信道接入算法，該算法采用停時(shí)過(guò)程對(duì)感知信道數(shù)進(jìn)行優(yōu)化，從優(yōu)化后的信道數(shù)中選擇可用的信道。文獻(xiàn)[3]中作者提出一種經(jīng)典的頻譜接入算法——VAC接入算法，認(rèn)知用戶隨機(jī)感知信道，發(fā)現(xiàn)信道空閑時(shí)則進(jìn)行數(shù)據(jù)發(fā)送并在發(fā)送完后等待，若檢測(cè)到繁忙則直接等待一段時(shí)間后再感知。但上述算法中都未涉及利用主用戶歷史使用概率及信道統(tǒng)計(jì)特性來(lái)對(duì)主用戶的行為進(jìn)行預(yù)測(cè)。為此，文獻(xiàn)[4]中提出一種基于部分可觀測(cè)馬爾科夫過(guò)程 （Partially Observable Markov Decision Process ，POMDP）的機(jī)會(huì)頻譜接入算法，該算法的設(shè)計(jì)思想是：充分利用頻譜檢測(cè)的先驗(yàn)知識(shí)和信道統(tǒng)計(jì)特性，使得每個(gè)次用戶動(dòng)態(tài)的搜尋頻譜機(jī)會(huì)，最大化自身獎(jiǎng)勵(lì)，提高系統(tǒng)的吞吐量和頻譜利用率。然而，文獻(xiàn)[4]中作者又指出，POMDP算法在信道數(shù)較多且頻譜環(huán)境變化復(fù)雜的情況下其計(jì)算的復(fù)雜度將超出次用戶可以承受的范圍。因此，該文又提出一種基于貪婪算法的次優(yōu)接入策略，該算法為了降低計(jì)算復(fù)雜度，不從整體最優(yōu)上加以考慮，而只考慮信道當(dāng)前時(shí)隙的最大獎(jiǎng)勵(lì)值，無(wú)法得到問(wèn)題的最優(yōu)解，但在解的優(yōu)化程度和算法復(fù)雜度上是一個(gè)很好的折中。然而，貪婪算法的自私性是其最大的不足，由于其只關(guān)注當(dāng)前時(shí)隙的瞬時(shí)獎(jiǎng)勵(lì)，最大獎(jiǎng)勵(lì)值相同的信道會(huì)出現(xiàn)多個(gè)，在該情形下次用戶只能隨機(jī)選擇信道接入。此時(shí)，貪婪算法相對(duì)于直接使用隨機(jī)接入策略的優(yōu)越性就無(wú)法體現(xiàn)。

針對(duì)上述問(wèn)題，本文提出一種新的信道接入策略，該算法對(duì)利用貪婪算法檢測(cè)出的多個(gè)信道具有相同最大獎(jiǎng)勵(lì)值的情形進(jìn)行改進(jìn)。改進(jìn)的方法是：當(dāng)檢測(cè)出多個(gè)具有相同最大獎(jiǎng)勵(lì)值的信道時(shí)，給該信道當(dāng)前時(shí)隙的獎(jiǎng)勵(lì)值再加入下個(gè)時(shí)隙的獎(jiǎng)勵(lì)后重新選擇獎(jiǎng)勵(lì)值最大的信道，可多次重復(fù)直至次用戶選擇出獎(jiǎng)勵(lì)值最大的一條信道。該算法相比于貪婪算法增加了一些計(jì)算復(fù)雜度，但有效的提高了系統(tǒng)的吞吐量。

1 基于POMDP的最優(yōu)頻譜接入算法

1.1 系統(tǒng)模型

本文的系統(tǒng)模型引用文獻(xiàn)[4]中的模型，假設(shè)整個(gè)認(rèn)知網(wǎng)絡(luò)中有 N 條信道，每條信道的帶寬為 Bi（i=1，2，……，N），這N條信道都是授權(quán)給主用戶使用的信道。文中以時(shí)隙為單位討論網(wǎng)絡(luò)中信道的狀態(tài)，在時(shí)隙結(jié)構(gòu)中，首先檢測(cè)信道是否可用，然后是在檢測(cè)到的可用信道上傳輸數(shù)據(jù)，最后是回復(fù)確認(rèn)信息。在一個(gè)時(shí)隙內(nèi)N個(gè)信道的占用情況可以看成一個(gè)共有（M=2N）種狀態(tài)的離散馬爾科夫過(guò)程，若N=2，則狀態(tài)轉(zhuǎn)移圖如圖1所示。

圖1 N=2時(shí)信道狀態(tài)轉(zhuǎn)移圖Fig.1 Channel state transition diagram When N=2

整個(gè)認(rèn)知網(wǎng)絡(luò)中每條信道都有兩個(gè)工作狀態(tài){0（占用），1（空閑）}，每個(gè)時(shí)隙 t的信道狀態(tài)由向量[s1（t），s2（t），s3（t），…，sN（t）]表示，其中 si（t）∈{0，1}。 假設(shè) T 個(gè)時(shí)隙內(nèi)，信道的統(tǒng)計(jì)特性α，β不變，信道的狀態(tài)轉(zhuǎn)移概率{pi，j}已知。如圖2所示，信道概率以α從0轉(zhuǎn)移到狀態(tài)1，以概率β保持在狀態(tài)1。

依照馬爾科夫鏈的空閑和占用狀態(tài)，次用戶觀測(cè)當(dāng)前信道是否可用，在避免對(duì)主用戶造成干擾的情況下，實(shí)現(xiàn)主用戶與次用戶之間的頻譜共享。頻譜的占用或空閑示例如圖3所示，傳輸時(shí)長(zhǎng)為相同時(shí)間長(zhǎng)度的T個(gè)時(shí)隙。

圖2 馬爾科夫信道模型Fig.2 Markov channel model

圖3 頻譜占用情況Fig.3 Spectrum occupancy

受限于硬件條件和認(rèn)知用戶的傳輸功率等因素，次用戶無(wú)法檢測(cè)到網(wǎng)絡(luò)中所有的信道。故假設(shè)每個(gè)時(shí)隙內(nèi)，次用戶選擇 M1（M1≤N）條信道檢測(cè)，最多接入 M2（M2≤M1）條信道。次用戶在每個(gè)時(shí)隙開(kāi)始時(shí)選擇M1條信道進(jìn)行檢測(cè)，用Rj，M2∈{0（可用），1（不可用）}來(lái)表示檢測(cè)到的信道的可用性，時(shí)隙內(nèi)操作流程如圖4所示。

圖4 一個(gè)時(shí)隙內(nèi)的操作流程Fig.4 The operation process in one time slot

綜上所述，問(wèn)題簡(jiǎn)化為每個(gè)時(shí)隙內(nèi)的檢測(cè)和接入策略為{M1，M2}，為便于研究，將檢測(cè)信道和接入信道的數(shù)目均設(shè)為1，即M1=M2=1，則每個(gè)時(shí)隙內(nèi)便只檢測(cè)N條信道中的一條信道 a∈{1，…，N}，a若可用就接入。 定義接入策略 ΘM∈{0（接入），1（不接入）}，在時(shí)隙結(jié)束時(shí)將收到 ACK信號(hào) KM2，這里KM2∈{0（成功），1（失敗）}。 我們定義，當(dāng)信道狀態(tài) Si（t）=1，檢測(cè)結(jié)果Rj，M1=1，接入策略ΘM=1的3個(gè)前提條件都成立時(shí)。MM2=1 此時(shí)，獎(jiǎng)勵(lì)值由 rj，M1，M2來(lái)決定。POMDP 最優(yōu)策略的目的就是在每一個(gè)次用戶獨(dú)立尋找頻譜接入的情況下最大化自身的獎(jiǎng)勵(lì)值（即系統(tǒng)的最大吞吐量），同時(shí)充分利用歷史累積的頻譜檢測(cè)先驗(yàn)知識(shí)以及信道統(tǒng)計(jì)特性，來(lái)限制或減少次用戶自身對(duì)主用戶的干擾。

1.2 最優(yōu)頻譜接入算法

對(duì)部分可觀測(cè)馬爾科夫而言，其內(nèi)部狀態(tài)是完全未知的，在第t個(gè)時(shí)隙，基于歷史的決策信息和觀測(cè)先驗(yàn)知識(shí)，信道內(nèi)部的狀態(tài)可用一個(gè)置信矢量 Λ（t）=[λ1（t），…，λM（t）]來(lái)表示，這里的λj（t）是條件概率，它表示了歷史決策和觀測(cè)先驗(yàn)知識(shí)以及信道狀態(tài)轉(zhuǎn)移概率下，第t個(gè)時(shí)隙的信道狀態(tài)為j的概率。根據(jù)文獻(xiàn)[5]：對(duì)于任意的t，在第t個(gè)時(shí)隙的置信矢量Λ （t）都是最佳接入策略 {M1，M2}的充分統(tǒng)計(jì)量。因此，在POMDP 模型下給出一種策略 Ω=[μ1，μ2，…，μT]，其中 μT:Λ（t）∈[0，]M→{M1（t），M2（t）}，該式將頻譜檢測(cè)與接入策略轉(zhuǎn)變?yōu)橛邢迺r(shí)域上的一種POMDP算法。由于POMDP算法的設(shè)計(jì)是MAC層和物理層的混合，所以用帶寬來(lái)表示其獎(jiǎng)勵(lì)值，獎(jiǎng)勵(lì)值與帶寬成正比，計(jì)算式為：

其中 Si（t）∈{0，1}是信道 i在第 t個(gè)時(shí)隙的狀態(tài)。

考慮次用戶網(wǎng)絡(luò)的實(shí)際情況，由于硬件條件及次用戶自身功率等因素的限制，頻譜檢測(cè)錯(cuò)誤是可能存在的，但本文僅討論一種理想情況，即次用戶頻譜檢測(cè)無(wú)差錯(cuò)，檢測(cè)結(jié)果真實(shí)的反應(yīng)了信道的狀態(tài)。我們只需要關(guān)注次用戶如何選擇每個(gè)時(shí)隙內(nèi)檢測(cè)到的信道，使得在所有時(shí)隙內(nèi)的獎(jiǎng)勵(lì)值總和最大。因此，定義 Vt（Λ（t））為在當(dāng)前置信矢量為 Λ（t）時(shí)，自第 t個(gè)時(shí)隙開(kāi)始之后系統(tǒng)所獲得的最大獎(jiǎng)勵(lì)值。計(jì)算公式如下：

從該式可以看出，自第t個(gè)時(shí)隙開(kāi)始之后系統(tǒng)所能獲得的最大獎(jiǎng)勵(lì)值包括兩個(gè)部分：1）第t個(gè)時(shí)隙的瞬時(shí)獎(jiǎng)勵(lì)值θBa；2）第 t+1 個(gè)時(shí)隙之后系統(tǒng)的未來(lái)獎(jiǎng)勵(lì)值 Vt+1（Γ（Λ（t）|a，θ））。最優(yōu)策略就是在獲得瞬時(shí)獎(jiǎng)勵(lì)和未來(lái)獎(jiǎng)勵(lì)的信息這兩者間尋求一種平衡。 其中 Λ（t+1）=Γ（Λ（t）|a，Rj，a是綜合了第 t個(gè)時(shí)隙檢測(cè)與接入的歷史經(jīng)驗(yàn)后更新的關(guān)于未來(lái)第t+1個(gè)時(shí)隙的信道狀態(tài)知識(shí)。式中的置信矢量的更新使用貝葉斯準(zhǔn)則，即

2 基于貪婪算法的次優(yōu)接入策略及改進(jìn)算法

由于POMDP的計(jì)算復(fù)雜度較高，在信道數(shù)少時(shí)，信道狀態(tài)數(shù)M（M=2N）比較小，最優(yōu)算法比較適用，但是當(dāng)信道數(shù)較多且頻譜占用的統(tǒng)計(jì)特性頻繁變化時(shí)，基于POMDP的最優(yōu)算法不再適用。因此，需要尋求一種計(jì)算復(fù)雜度相對(duì)較低的次優(yōu)解決算法——貪婪算法。

基于貪婪算法的接入策略將不考慮獎(jiǎng)勵(lì)值中的未來(lái)獎(jiǎng)勵(lì)部分，而只關(guān)注當(dāng)前時(shí)隙t的最大瞬時(shí)獎(jiǎng)勵(lì)值。貪婪算法將信道狀態(tài)數(shù)由M（M=2N）減少為N，以每個(gè)信道的置信矢量來(lái)代替整個(gè)網(wǎng)絡(luò)狀態(tài)算法的置信矢量，故以r=[ω1，…，ωN]來(lái)表示，式中ωi為當(dāng)前時(shí)隙t信道i是否被占用的概率。已經(jīng)證明當(dāng)N條信道相互獨(dú)立時(shí)，γ（t）是最優(yōu)接入策略的充分統(tǒng)計(jì)量[6]。利用可以得到基于貪婪算法的次優(yōu)策略以最大化每個(gè)時(shí)隙的吞吐量，由于信道相互獨(dú)立，根據(jù)圖1的馬爾科夫信道模型，在給定信道狀態(tài)先驗(yàn)知識(shí)為γ（t）的條件下，第t個(gè)時(shí)隙選擇信道 a 所獲得的獎(jiǎng)勵(lì)值為（ωa（t）βa+（1+ωa（t））αa）Ba，它表示的是第t個(gè)時(shí)隙選擇的信道a可用的概率。故貪婪算法的信道選擇策略可依據(jù)以下公式計(jì)算：

在t時(shí)隙結(jié)束時(shí)，置信矢量可以根據(jù)以下公式更新。

此時(shí)，如果主用戶信道未被次用戶檢測(cè)到，那么其可用概率根據(jù)馬爾科夫過(guò)程更新，如果檢測(cè)到，其可用概率將以次用戶檢測(cè)的結(jié)果為準(zhǔn)。文獻(xiàn)[7]中給出了貪婪算法的計(jì)算復(fù)雜度，并且具體闡述了如何在系統(tǒng)性能和計(jì)算復(fù)雜度之間互換權(quán)衡。

由于貪婪算法只關(guān)注每個(gè)時(shí)隙當(dāng)前的獎(jiǎng)勵(lì)值，并不關(guān)心未來(lái)時(shí)隙信道的獎(jiǎng)勵(lì)值，這是其不足之處，即具有自私性。在每個(gè)時(shí)隙開(kāi)始時(shí)，各個(gè)信道具有相同的初始置信矢量，若只關(guān)注瞬時(shí)獎(jiǎng)勵(lì)值，被檢測(cè)的信道出現(xiàn)相同獎(jiǎng)勵(lì)值的可能性就會(huì)很大。假設(shè)網(wǎng)絡(luò)中有N條信道，若出現(xiàn)了N-2個(gè)相同最大獎(jiǎng)勵(lì)值的信道，在文獻(xiàn)[5]中作者指出，該情形下次用戶會(huì)在N-2個(gè)信道中隨機(jī)選擇，此時(shí)在N-2個(gè)信道中的隨機(jī)選擇與直接使用隨機(jī)算法結(jié)果很相似。另外，在多個(gè)次用戶同時(shí)存在時(shí)，可能出現(xiàn)多個(gè)次用戶同時(shí)選擇了相同的信道接入，那么碰撞將不可避免的發(fā)生。針對(duì)上述情形，我們提出一種改進(jìn)的算法，算法的中心思想是：假設(shè)出現(xiàn)了條具有相同最大獎(jiǎng)勵(lì)值的信道，則在瞬時(shí)獎(jiǎng)勵(lì)值的基礎(chǔ)上加上這M條信道下個(gè)時(shí)隙的獎(jiǎng)勵(lì)值并依據(jù)最大獎(jiǎng)勵(lì)值公式重新計(jì)算最大獎(jiǎng)勵(lì)值。重新選擇信道 b 所獲得的獎(jiǎng)勵(lì)值為（ωb（t）βb+（1-ωb（t））αb）Bb，這里b∈{1，2，…，M}，此時(shí)最佳接入策略將依據(jù)下式進(jìn)行選擇，

在t時(shí)隙結(jié)束時(shí)，置信矢量的更新同樣依據(jù)下面的公式：

該算法實(shí)際上是一個(gè)迭代累加的過(guò)程，如果在M條信道中依據(jù)公式 （6）計(jì)算出的信道的最大瞬時(shí)獎(jiǎng)勵(lì)依然有大部分相同，則再累加信道下一個(gè)時(shí)隙的獎(jiǎng)勵(lì)值，直到選出最優(yōu)的信道。

3 計(jì)算機(jī)仿真

設(shè)置信道數(shù)N=10，帶寬B=1，信道狀態(tài)轉(zhuǎn)移概率{α=0.2，β=0.8}，信息到達(dá)率 λ：λ 從 0.02到 0.2，每隔 0.02取一個(gè)點(diǎn)，仿真總次數(shù)為200次，時(shí)隙總數(shù)T=100。首先，在單次用戶時(shí)對(duì)貪婪算法和改進(jìn)算法中最大獎(jiǎng)勵(lì)值相同的信道出現(xiàn)的個(gè)數(shù)進(jìn)行統(tǒng)計(jì)對(duì)比，如圖5所示，從圖5中可以看出，改進(jìn)后的算法明顯降低了最大獎(jiǎng)勵(lì)值相同的信道出現(xiàn)的個(gè)數(shù)。最后，為不失一般性，仿真將分別設(shè)置為單次用戶、兩次用戶、三次用戶的情景，并對(duì)隨機(jī)算法、貪婪算法、改進(jìn)算法進(jìn)行仿真，仿真結(jié)果如圖6~圖8所示。

圖5 單次用戶時(shí)貪婪算法和改進(jìn)算法出現(xiàn)最大獎(jiǎng)勵(lì)值相同的信道數(shù)的統(tǒng)計(jì)對(duì)比圖Fig.5 The number of channel which has the maximum reward of the greedy algorithm and improved algorithm

圖6 單次用戶時(shí)3種算法的次用戶吞吐量Fig.6 The throughput of three algorithms when single user

從仿真結(jié)果中可以看出，貪婪算法始終優(yōu)于隨機(jī)算法，而改進(jìn)的算法在單次用戶時(shí)吞吐量有較大的提升，并且始終優(yōu)于隨機(jī)算法和貪婪算法。在兩次用戶時(shí)提升幅度又有所下降，當(dāng)信息到達(dá)率約為0.13時(shí)次用戶吞吐量與貪婪算法的相同，但之后又開(kāi)始上升。在三次用戶時(shí)吞吐量的提升幅度變的更小，有多處與貪婪算法相同，甚至在信息到達(dá)率低于0.06時(shí)其性能不及貪婪算法。這是因?yàn)椋杭僭O(shè)信道數(shù)目不變時(shí)，隨著次用戶數(shù)的增加，多個(gè)次用戶競(jìng)爭(zhēng)接入信道，這將導(dǎo)致一定的沖突，從而造成系統(tǒng)性能的下降。

圖7 兩次用戶時(shí)3種算法的次用戶吞吐量Fig.7 The throughput of three algorithms when two users

圖8 3次用戶時(shí)3種算法的次用戶吞吐量Fig.8 The throughput of three algorithms when three users

4 結(jié) 論

文中首先分析了基于POMDP的最優(yōu)頻譜接入策略，POMDP算法利用歷史累積的頻譜檢測(cè)信息和信道統(tǒng)計(jì)狀態(tài)作為先驗(yàn)知識(shí)來(lái)選擇信道，明顯提升了系統(tǒng)的吞吐量，但POMDP算法對(duì)硬件的要求較高，在信道數(shù)較多或頻譜環(huán)境較復(fù)雜時(shí)算法的復(fù)雜程度不可估量。故在POMDP算法的基礎(chǔ)上考慮了貪婪算法，但貪婪算法又具有自私性，因此文章針對(duì)其自私性做了改進(jìn)，使得接入策略更優(yōu)化。改進(jìn)的算法相比于貪婪算法增加了一些計(jì)算復(fù)雜度，卻有效提升了系統(tǒng)的吞吐量，具有一定的適用性。然而，從仿真結(jié)果圖中可以看到，當(dāng)次用戶數(shù)增多時(shí)，由于多個(gè)次用戶將競(jìng)爭(zhēng)接入信道而造成一定的沖突，這使得算法的性能有所下降，后續(xù)的工作需要深入研究該問(wèn)題以找到解決的方法。衛(wèi)星群組網(wǎng)中，每顆衛(wèi)星都配備認(rèn)知無(wú)線電終端，不同的衛(wèi)星根據(jù)處理的業(yè)務(wù)的主次不同、重要程度不同被定義為主用戶和次用戶。因此，本文提出的算法也可考慮用于衛(wèi)星組網(wǎng)MAC協(xié)議設(shè)計(jì)中的信道接入算法。

[1]Mitola Joseph，Maguire，G Q.， Jr.， Cognitive radio:making software radios more personal[J].Personal Communications，IEEE，1999，6（4）:13，18.

[2]Cormio C.A survey on MAC protocols for cognitive radio networks[J].Ad Hoc Netw，2009，7（7）:1315-1329.

[3]HUANGSen-hua，LIUXin，DINGZhi.Opportunistic spectrum access in cognitive radio networks[J].IEEE INFOCOM 2008 Proceedings，2008:2101-2109.

[4]ZHAO Qing，LANG TONG，Swami A，et al.Decentralized cognitive MAC for opportunistic spectrum access in ad hoc networks:A POMDP framework [J].Selected Areas in Communications， IEEE Journal on，2007，25（3）:589-600.

[5]Richard D，Smallwood，Edward J.Sondik.The optimal control of partially observable Markov processes over a finite horizon[J].Operations Research，1971:1071-1088.

[6]Zhao Q，wami A，Chen Y.Decentralized Medium Access Control Protocols for Dynamic Spectrum Access:Decision Theoretic Framework[J].2006:284-286.

[7]CHEN Yunxia，ZHAO Qing，Swami A.Distributed cognitive MACfor energy-constrained opportunistic spectrum access[J].Military Communications Conference，2006.MILCOM 2006.IEEE，2006（7）:23-25.