一種改進的認知無線電頻譜接入策略

徐德艷，李 勇，程 偉

（西北工業大學 電子信息學院，陜西 西安 710100）

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

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

針對上述問題，本文提出一種新的信道接入策略，該算法對利用貪婪算法檢測出的多個信道具有相同最大獎勵值的情形進行改進。改進的方法是：當檢測出多個具有相同最大獎勵值的信道時，給該信道當前時隙的獎勵值再加入下個時隙的獎勵后重新選擇獎勵值最大的信道，可多次重復直至次用戶選擇出獎勵值最大的一條信道。該算法相比于貪婪算法增加了一些計算復雜度，但有效的提高了系統的吞吐量。

1 基于POMDP的最優頻譜接入算法

1.1 系統模型

本文的系統模型引用文獻[4]中的模型，假設整個認知網絡中有 N 條信道，每條信道的帶寬為 Bi（i=1，2，……，N），這N條信道都是授權給主用戶使用的信道。文中以時隙為單位討論網絡中信道的狀態，在時隙結構中，首先檢測信道是否可用，然后是在檢測到的可用信道上傳輸數據，最后是回復確認信息。在一個時隙內N個信道的占用情況可以看成一個共有（M=2N）種狀態的離散馬爾科夫過程，若N=2，則狀態轉移圖如圖1所示。

圖1 N=2時信道狀態轉移圖Fig.1 Channel state transition diagram When N=2

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

依照馬爾科夫鏈的空閑和占用狀態，次用戶觀測當前信道是否可用，在避免對主用戶造成干擾的情況下，實現主用戶與次用戶之間的頻譜共享。頻譜的占用或空閑示例如圖3所示，傳輸時長為相同時間長度的T個時隙。

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

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

受限于硬件條件和認知用戶的傳輸功率等因素，次用戶無法檢測到網絡中所有的信道。故假設每個時隙內，次用戶選擇 M1（M1≤N）條信道檢測，最多接入 M2（M2≤M1）條信道。次用戶在每個時隙開始時選擇M1條信道進行檢測，用Rj，M2∈{0（可用），1（不可用）}來表示檢測到的信道的可用性，時隙內操作流程如圖4所示。

圖4 一個時隙內的操作流程Fig.4 The operation process in one time slot

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

1.2 最優頻譜接入算法

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

其中 Si（t）∈{0，1}是信道 i在第 t個時隙的狀態。

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

從該式可以看出，自第t個時隙開始之后系統所能獲得的最大獎勵值包括兩個部分：1）第t個時隙的瞬時獎勵值θBa；2）第 t+1 個時隙之后系統的未來獎勵值 Vt+1（Γ（Λ（t）|a，θ））。最優策略就是在獲得瞬時獎勵和未來獎勵的信息這兩者間尋求一種平衡。 其中 Λ（t+1）=Γ（Λ（t）|a，Rj，a是綜合了第 t個時隙檢測與接入的歷史經驗后更新的關于未來第t+1個時隙的信道狀態知識。式中的置信矢量的更新使用貝葉斯準則，即

2 基于貪婪算法的次優接入策略及改進算法

由于POMDP的計算復雜度較高，在信道數少時，信道狀態數M（M=2N）比較小，最優算法比較適用，但是當信道數較多且頻譜占用的統計特性頻繁變化時，基于POMDP的最優算法不再適用。因此，需要尋求一種計算復雜度相對較低的次優解決算法——貪婪算法。

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

在t時隙結束時，置信矢量可以根據以下公式更新。

此時，如果主用戶信道未被次用戶檢測到，那么其可用概率根據馬爾科夫過程更新，如果檢測到，其可用概率將以次用戶檢測的結果為準。文獻[7]中給出了貪婪算法的計算復雜度，并且具體闡述了如何在系統性能和計算復雜度之間互換權衡。

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

在t時隙結束時，置信矢量的更新同樣依據下面的公式：

該算法實際上是一個迭代累加的過程，如果在M條信道中依據公式 （6）計算出的信道的最大瞬時獎勵依然有大部分相同，則再累加信道下一個時隙的獎勵值，直到選出最優的信道。

3 計算機仿真

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

圖5 單次用戶時貪婪算法和改進算法出現最大獎勵值相同的信道數的統計對比圖Fig.5 The number of channel which has the maximum reward of the greedy algorithm and improved algorithm

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

從仿真結果中可以看出，貪婪算法始終優于隨機算法，而改進的算法在單次用戶時吞吐量有較大的提升，并且始終優于隨機算法和貪婪算法。在兩次用戶時提升幅度又有所下降，當信息到達率約為0.13時次用戶吞吐量與貪婪算法的相同，但之后又開始上升。在三次用戶時吞吐量的提升幅度變的更小，有多處與貪婪算法相同，甚至在信息到達率低于0.06時其性能不及貪婪算法。這是因為：假設信道數目不變時，隨著次用戶數的增加，多個次用戶競爭接入信道，這將導致一定的沖突，從而造成系統性能的下降。

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

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

4 結 論

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

[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.