基于多態蟻群優化算法的認知無線電頻譜分配

孫漢卿 劉 征 王桂芝 連衛民

(河南牧業經濟學院信息工程學院 河南 鄭州 450044)

0 引 言

近年來，無線通信領域持續繁榮，導致頻譜資源嚴重緊缺。認知無線電(Cognitive Radio,CR)技術是解決此類問題的有效方式之一，它可以自動找尋并且充分利用可用的頻譜資源[1]。在認知無線電網絡中，認知用戶可以接入頻譜資源的前提條件是不能對主用戶產生干擾，認知用戶是以一種機會的方式占用可用頻譜資源[2]。頻譜分配的核心思想是對感知到的未被占用的頻譜進行公平且高效的分配，從而提高頻譜的使用效率[3]。頻譜分配問題本質上是一種優化問題且具有非確定性特點，所以采用智能算法對頻譜分配問題進行求解非常有效。蟻群算法的思想在解決全局優化求解問題中得到了廣泛使用，無論是解決簡單的單目標優化問題，還是復雜的多目標優化問題都非常有效。

目前，國內外研究人員針對認知無線電頻譜分配的智能算法求解取得了一定研究成果。文獻[4]提出了一種基于蟻群優化算法的認知無線電頻譜分配方案，通過引入學習因子改良了信息素的積累方式，進一步縮短計算最優解的時間，有效節約了時間開銷。但由于分配模型的效益函數不完善，使得該算法無法兼顧增益矩陣，導致網絡總效益有所下降。文獻[5]提出了一種基于遺傳算法和蟻群算法相結合的頻譜分配算法，通過遺傳算法求出初始解，再利用銜接策略將初始解轉化為蟻群算法所需的信息素，最終求得最優解。該算法雖然在一定程度上提高了網絡平均效益，但未針對頻譜分配的公平性問題進行討論。文獻[6]提出了一種基于感知時間和門限聯合的頻譜分配優化模型，通過采用“先聽后傳”的次用戶幀結構，從頻譜感知時間和子信道感知門限出發求得最優解，能確保系統擁有較高的吞吐量，但是其會導致認知用戶之間的競爭增大，無法保證系統的公平性。文獻[7]提出了一種改進蟻群算法的無線電頻譜智能分配策略，該算法在傳統蟻群算法的基礎上，引入了自助查詢搜索窗口，通過限定螞蟻的前進路徑來縮短搜索時間，從而達到提高網絡系統整體效益的目的，但是該算法在整體尋優方面存在不足，不能很好地求得全局最優解。

綜上可知，現有認知無線電頻譜分配模型大都采用平均分配模式進行分配，并未從認知用戶需求角度出發，僅根據差別用戶對頻譜的需求程度分配將導致公平性較低，頻譜資源得不到較好利用[8-9]。為解決認知無線電頻譜分配中認知用戶間競爭大、網絡效益低，以及認知用戶接入可用頻譜所用時間長等問題，本文給出一種基于多態蟻群優化算法的認知無線電頻譜分配方案(cognitive radio spectrum allocation based on improved polymorphic ant colony algorithm,IPAC)。IPAC算法思想是：基于傳統蟻群算法計算螞蟻的轉移概率，為螞蟻的行動提供依據；針對傳統蟻群算法未考慮螞蟻到達節點的時間因素，引入一個時間因子生成新的信息素分配方法，并按照“螞蟻達到節點的時間越少，所分配信息素越多”原則進行信息素分配，更加公平地分配信息素；對所有認知用戶的信息素進行排序，將信道分配給信息素最大的認知用戶。該算法可以較好地確保認知用戶之間的公平性，大幅節省頻譜分配所需時間，提高信道利用率，有效減少了認知用戶的搜索時間，從而提高系統收斂速度、網絡效益和吞吐量。

1 認知無線電頻譜分配模型

認知無線電頻譜分配基本模型[10]如下：在分布式認知無線電頻譜共享系統模式下，認知用戶(次用戶)通過感知主用戶(授權用戶)信號的情況，在不干擾主用戶接入頻譜的前提下，根據其自身的性質、性能、方位等情況獲得所需的可用頻譜。每個認知用戶通過這種方式獲取各自的可用頻譜，并了解有關受到的干擾約束條件，實現了認知用戶之間的信息交互[12]。頻譜共享的方式有以下兩種：一是通過控制信道獲取所需的信息；二是通過認知無線網絡的基站獲得頻譜資源占用情況。認知無線電頻譜分配主要采用可用頻譜矩陣LN×M、干擾約束矩陣CN×K×M、信道效益矩陣BN×M和無沖突分配矩陣SN×M進行描述。其中：N表示認知用戶的總數量，n表示N中的某個認知用戶；M表示信道的總數量，m表示某個頻譜；K表示另一認知用戶的總數量，k表示K中的某個認知用戶。下面對上述四種矩陣分別進行說明：

1)可用頻譜矩陣LN×M。假如主用戶已經占用頻譜m，此時如果要使用該頻譜將會對主用戶的正常接入造成不必要的干擾?？捎妙l譜矩陣僅用于主用戶之間，不考慮認知用戶之間的相互干擾。

2)干擾約束矩陣CN×K×M。該矩陣主要是用于說明不同認知用戶之間的干擾約束問題。假如存在cn,k,m=1，則說明如果認知用戶n和認知用戶k同時占用同一信道m，將會使它們彼此之間的干擾增大。干擾約束條件主要取決于用戶所在區域、用戶間的距離和信號的強度三個因素。

3)信道效益矩陣BN×M。該矩陣主要是用于說明一個認知用戶接入某個信道時所得到的信道吞吐量，即該用戶是否順利接入該頻帶。bn,m表示在沒有鄰道干擾的情況下，認知用戶n接入頻帶m后，可獲得的最大帶寬吞吐量比。如果在可用頻譜矩陣中ln,m=0，則有bn,m=0。

4)無沖突分配矩陣SN×M。若sn,m=1，則認知用戶n此時正在使用頻帶m。若sn,m=0，則此時無法將頻帶m分配給認知用戶n使用。同時，該矩陣需要滿足LN×M和CN×K×M所規定的干擾約束條件。

2 基于蟻群算法的轉移概率計算

2.1 相關參量設置和規則

基于蟻群算法的頻譜分配方案轉移概率計算相關參量設置和規則如下：

(1)節點：螞蟻可能訪問的每一個認知用戶。

(2)移動路徑：為認知用戶分配的一個信道。

(3)螞蟻個數：采用序號χ表示螞蟻的個數。

(4)迭代次數：采用編號ξ表示迭代的次數。

(5)認知用戶個數：螞蟻訪問的節點數量，總數量用N表示，編號用n表示。

(6)信道數量：信道總數量用M表示，編號用m表示。

(7)可用信道矩陣L：屬于動態調節矩陣，根據每個螞蟻位置變化自動調節數值。

(8)干擾約束矩陣C：屬于動態調節矩陣，根據每個螞蟻位置變化自動調節數值。

(9)信息素矩陣TN×M×ξ：矩陣中的元素表示螞蟻在第ξ次迭代時第n個認知用戶在第m個信道處釋放的信息素多少，N表示認知用戶的總個數，M表示信道的總數，ξ表示迭代的次數。

(10)規則1：每個認知用戶均擁有相同數量的螞蟻，即每個認知用戶成為源節點的概率是相同的。

(11)規則2：螞蟻走過的每個節點都進行記憶，且每只螞蟻只能走過相同的節點一次，即每個節點不會被相同的螞蟻重復經過。

上述(7)、(8)兩條主要用于決定：① 螞蟻經過節點時釋放的信息素多少；② 當螞蟻到達該節點時能獲得的信道效益大?。虎?螞蟻所經歷路線的長短；④ 螞蟻能否到達終點。

2.2 轉移概率計算步驟

(1)

式中：Yn,m表示認知用戶n在信道m上的消耗函數；K表示另一認知用戶的總個數；cn,k,m為干擾約束矩陣CN×K×M中的元素，當cn,k,m=1時，認知用戶n和認知用戶k之間存在干擾，反之則不存在干擾；lk,m為可用頻譜矩陣LN×M中的元素，當lk,m=1時則說明認知用戶k也可以使用該信道，反之則說明該信道已被占用。

步驟2判斷螞蟻行為。螞蟻行動函數Aχ,ξ決定螞蟻的下一步行動，判斷準則如下：

(2)

式中：χ表示螞蟻個數；ξ表示迭代次數。當Aχ,ξ=0時，表示認知用戶n使用信道m時對其他認知用戶不造成干擾，此時螞蟻會繼續移動直到終點，否則螞蟻χ繼續留在該節點，不再前進；當Aχ,ξ=1時，螞蟻前進尋找新的節點。

每當螞蟻完成一次行動，開始下次行動之前，需要刪除上一個節點分配的信道以及與其產生干擾的信道，同時重新設置節點與信道之間的干擾約束關系。隨著螞蟻行為的不斷變化，認知用戶的可用信道和干擾約束關系也會隨之改變，可通過改變L和C的值來反映這種變化。

步驟3螞蟻轉移概率。螞蟻行動未終止時需要根據轉移概率選擇下一節點，所以為了保證路徑的多樣性，螞蟻的行動既要考慮信息素的大小，也要考慮觀測值的大小。其中，觀測值是與消耗及干擾相關的函數：

(3)

式中：Yn,m表示認知用戶n在信道m上的消耗函數；DLn,m表示認知用戶n使用信道m時的信道切換時延Dswitching,ln,m和排隊等候時延Dqueueing,ln,m之和。

DLn,m=Dswitching,ln,m+Dqueueing,ln,m

(4)

切換時延是指節點n從前一信道h接入到信道m所產生的切換時延：

(5)

式中：f表示取值為0～1之間的調節因子，用于避免時延在觀測值函數中所占比重過大；Timem表示節點n接入信道m的時間；Timeh,m表示從h信道開始向m信道轉換的時間。

但如果次用戶j可能正在使用信道m，則需要等待次用戶j不再使用信道m后再接入，由此產生排隊時延：

Dqueueing,ln,m=Timen,m-Timej,end

(6)

式中：Timen,m表示次用戶n開始向信道m接入的時間；Timej,end表示次用戶j不再使用信道m的時間。

由此可得螞蟻轉移概率為：

(7)

式中：N為螞蟻接下來需經過的所有節點數，但禁忌表中的元素不包含在N中；α和β表示權重因子，分別表示信息素和信道效益的相對重要程度；tn,m,ξ表示信息素矩陣TN×M×ξ中的元素，表示螞蟻在第ξ次迭代時，認知用戶n在信道m處釋放的信息素多少。

步驟4選擇后繼節點。螞蟻的每一步移動表示一個可行路徑，螞蟻選擇下一步的移動節點由行動判決依據n′決定：

(8)

式中:g表示0～1間的隨機數；G取0.9;RW表示輪盤賭法。如果g

3 方案設計

在傳統蟻群算法中，信息素矩陣各元素中信息素更新方式為：

(9)

(10)

式中：τi表示螞蟻到達第i節點所經歷時間(本文中，螞蟻每到一個節點就會重置時間，同時記錄螞蟻從上一個節點出發到到達當前節點所需的時間)；τ表示循環過程所經歷的總時間。

(11)

則可得最終的信息素更新時間系數ηi為：

(12)

則信息素矩陣TN×M×ξ中各元素的信息素更新如下：

(13)

當一只螞蟻停留在某個節點不再繼續移動時，算法的循環結束。螞蟻在移動過程中，記錄到達每一個節點的時間τ，然后根據螞蟻移動的路徑和到達各節點的時間對信息素矩陣中的各元素進行更新：

(14)

傳統的蟻群算法是將信息素按螞蟻所經歷的節點數平均將信息素分配給每一個節點，而通過式(14)可以將信息素按照螞蟻通過信道m到達每一個節點的時間來分配信息素，螞蟻達到節點的時間越少，則分配的信息素越多；反之，螞蟻達到節點的時間越多，則分配的信息素越少。

首先更新局部信息素，然后進一步更新全局信息素，在每次迭代完成后，重新計算每條路徑上的信息素：

(15)

(16)

完成全局信息素更新后，首先將所有節點的信息素進行比較，然后按照信息素的大小順序來分配信道。其中，信道的最終判決依據ωn為：

(17)

式中：εmax表示最大迭代次數。經εmax次迭代后，將信道分配給信息素最大的認知用戶。分配完成之后需將信息素矩陣初始化，然后進行下一輪分配。

4 實驗仿真及分析

假設仿真實驗區域為一個30×30的網格，該網格區域中認知用戶總個數為20個，可提供給認知用戶使用的信道總數量為30個，每個認知用戶的干擾范圍d設為[3,6]。各個認知用戶先不進行任何行動，當主用戶未對其授權頻段進行使用時，認知用戶則根據分配的頻譜乘機接入到該頻譜。根據上述參數則可計算出可用頻譜矩陣L、干擾約束矩陣C和信道效益矩陣B。假定搜索螞蟻數量X=25，最大迭代次數εmax=100，信息素強度Q=2，信息素揮發因子ρ=0.11，信息素指數為1，啟發式信息指數為3，初始信息量c=5，MAXPC=20。仿真共進行50次獨立實驗并記錄結果，且每次實驗時的矩陣L、B和C均隨機生成。將本文IPAC算法與傳統AOC算法[7]、QGA算法[14]、CSGC算法[15]在網絡收益和、系統公平性、收斂速度和系統吞吐量四個方面的性能進行比較。

圖1為不同可用頻譜數量下，本文算法與AOC算法、QGA算法的網絡收益和比較?？梢钥闯觯S著可用頻譜數量m的不斷增加，本文算法的網絡收益總和始終高于AOC算法和QGA算法。這是由于引入的時間參數對信道的效益起到了較好的調節作用，大大減少了認知用戶的搜索時間，從而使系統的網絡收益得到顯著提高。

圖1 三種算法在可用頻譜數不同時的網絡收益和

圖2為不同認知用戶數量下，本文算法與AOC算法、QGA算法的網絡收益和比較?？梢钥闯觯斦J知用戶數量不斷增加時，三種算法的網絡收益和都在減小。這是由于隨著認知用戶數量不斷增多，作用于可用頻譜上的干擾也隨之增多，從而導致分配可用頻譜的時間也相應變長。但由于本文算法與AOC算法、QGA算法相比收斂速度較高，所以當頻譜數量不變時，認知用戶可以做出有利選擇，獲得更好的網絡收益。

圖2 三種算法在認知用戶數不同時的網絡收益和

圖3為不同認知用戶數量下，本文算法與AOC算法、QGA算法的系統公平性比較?？梢钥闯?，本文算法的系統公平性始終優于AOC算法和QGA算法。這是由于隨著認知用戶數量不斷增加，認知用戶之間的競爭也隨之增大，本文算法通過比較認知用戶的信道使用情況來權衡頻譜分配公平性，使系統公平性得到顯著提高。

圖3 三種算法在認知用戶數不同時的公平性

圖4為不同認知用戶數量下，本文算法與AOC算法、CSGC算法的收斂速度比較?？梢钥闯觯疚乃惴ǖ氖諗克俣纫冀K快于AOC算法和CSGC算法。這是由于本文算法引入了時間效率這一量化因子，使系統減少了認知用戶的搜索時間，大幅節約了時間開銷。

圖4 三種算法在認知用戶數不同時的收斂速度

圖5為不同可用頻譜數量下，本文算法與AOC算法、CSGC算法的收斂速度比較。可以看出，當可用頻譜數量增加時，三種算法的系統的吞吐量都在增加。但是由于本文算法的收斂速度明顯比AOC算法和CSGC算法快，所以系統的吞吐量顯著高于兩種算法，可以有效改善系統的整體性能。

圖5 三種算法在可用頻譜數不同時的系統吞吐量

綜上所述，本文算法由于引入了時間效率這一量化因子，大大減少了認知用戶的搜索時間，使認知用戶能更快速地接入到可用頻譜，具有更快的收斂速度，進而獲得了更好的網絡收益和以及系統吞吐量。同時，其通過比較認知用戶的信道使用情況來權衡頻譜分配公平性，顯著提高了系統頻譜分配的公平性。因此，本文算法在網絡收益和、系統公平性、收斂速度和系統吞吐量四個方面的性能均優于AOC算法、QGA算法和CSGC算法。

5 結 語

本文通過引入時間因子對信息素的計算方法進行改進，給出一種基于多態蟻群優化算法的認知無線電頻譜分配方案。通過動態考慮認知用戶的頻譜接入時間，有效加快頻譜分配速度，降低認知用戶間的競爭，大幅提高信道利用率，同時也有效提升了系統的公平性。仿真實驗結果表明，與傳統認知無線電頻譜分配算法相比，本文算法可以顯著提升系統的網絡收益、公平性、收斂速度和吞吐量等性能。