基于多態(tài)蟻群優(yōu)化算法的認(rèn)知無(wú)線電頻譜分配

孫漢卿 劉 征 王桂芝 連衛(wèi)民

(河南牧業(yè)經(jīng)濟(jì)學(xué)院信息工程學(xué)院 河南 鄭州 450044)

0 引 言

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

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

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

1 認(rèn)知無(wú)線電頻譜分配模型

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

1)可用頻譜矩陣LN×M。假如主用戶已經(jīng)占用頻譜m，此時(shí)如果要使用該頻譜將會(huì)對(duì)主用戶的正常接入造成不必要的干擾。可用頻譜矩陣僅用于主用戶之間，不考慮認(rèn)知用戶之間的相互干擾。

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

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

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

2 基于蟻群算法的轉(zhuǎn)移概率計(jì)算

2.1 相關(guān)參量設(shè)置和規(guī)則

基于蟻群算法的頻譜分配方案轉(zhuǎn)移概率計(jì)算相關(guān)參量設(shè)置和規(guī)則如下：

(1)節(jié)點(diǎn)：螞蟻可能訪問的每一個(gè)認(rèn)知用戶。

(2)移動(dòng)路徑：為認(rèn)知用戶分配的一個(gè)信道。

(3)螞蟻個(gè)數(shù)：采用序號(hào)χ表示螞蟻的個(gè)數(shù)。

(4)迭代次數(shù)：采用編號(hào)ξ表示迭代的次數(shù)。

(5)認(rèn)知用戶個(gè)數(shù)：螞蟻訪問的節(jié)點(diǎn)數(shù)量，總數(shù)量用N表示，編號(hào)用n表示。

(6)信道數(shù)量：信道總數(shù)量用M表示，編號(hào)用m表示。

(7)可用信道矩陣L：屬于動(dòng)態(tài)調(diào)節(jié)矩陣，根據(jù)每個(gè)螞蟻位置變化自動(dòng)調(diào)節(jié)數(shù)值。

(8)干擾約束矩陣C：屬于動(dòng)態(tài)調(diào)節(jié)矩陣，根據(jù)每個(gè)螞蟻位置變化自動(dòng)調(diào)節(jié)數(shù)值。

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

(10)規(guī)則1：每個(gè)認(rèn)知用戶均擁有相同數(shù)量的螞蟻，即每個(gè)認(rèn)知用戶成為源節(jié)點(diǎn)的概率是相同的。

(11)規(guī)則2：螞蟻?zhàn)哌^的每個(gè)節(jié)點(diǎn)都進(jìn)行記憶，且每只螞蟻只能走過相同的節(jié)點(diǎn)一次，即每個(gè)節(jié)點(diǎn)不會(huì)被相同的螞蟻重復(fù)經(jīng)過。

上述(7)、(8)兩條主要用于決定：① 螞蟻經(jīng)過節(jié)點(diǎn)時(shí)釋放的信息素多少；② 當(dāng)螞蟻到達(dá)該節(jié)點(diǎn)時(shí)能獲得的信道效益大小；③ 螞蟻所經(jīng)歷路線的長(zhǎng)短；④ 螞蟻能否到達(dá)終點(diǎn)。

2.2 轉(zhuǎn)移概率計(jì)算步驟

(1)

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

步驟2判斷螞蟻行為。螞蟻行動(dòng)函數(shù)Aχ,ξ決定螞蟻的下一步行動(dòng)，判斷準(zhǔn)則如下：

(2)

式中：χ表示螞蟻個(gè)數(shù)；ξ表示迭代次數(shù)。當(dāng)Aχ,ξ=0時(shí)，表示認(rèn)知用戶n使用信道m(xù)時(shí)對(duì)其他認(rèn)知用戶不造成干擾，此時(shí)螞蟻會(huì)繼續(xù)移動(dòng)直到終點(diǎn)，否則螞蟻χ繼續(xù)留在該節(jié)點(diǎn)，不再前進(jìn)；當(dāng)Aχ,ξ=1時(shí)，螞蟻前進(jìn)尋找新的節(jié)點(diǎn)。

每當(dāng)螞蟻完成一次行動(dòng)，開始下次行動(dòng)之前，需要?jiǎng)h除上一個(gè)節(jié)點(diǎn)分配的信道以及與其產(chǎn)生干擾的信道，同時(shí)重新設(shè)置節(jié)點(diǎn)與信道之間的干擾約束關(guān)系。隨著螞蟻行為的不斷變化，認(rèn)知用戶的可用信道和干擾約束關(guān)系也會(huì)隨之改變，可通過改變L和C的值來反映這種變化。

步驟3螞蟻轉(zhuǎn)移概率。螞蟻行動(dòng)未終止時(shí)需要根據(jù)轉(zhuǎn)移概率選擇下一節(jié)點(diǎn)，所以為了保證路徑的多樣性，螞蟻的行動(dòng)既要考慮信息素的大小，也要考慮觀測(cè)值的大小。其中，觀測(cè)值是與消耗及干擾相關(guān)的函數(shù)：

(3)

式中：Yn,m表示認(rèn)知用戶n在信道m(xù)上的消耗函數(shù)；DLn,m表示認(rèn)知用戶n使用信道m(xù)時(shí)的信道切換時(shí)延Dswitching,ln,m和排隊(duì)等候時(shí)延Dqueueing,ln,m之和。

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

(4)

切換時(shí)延是指節(jié)點(diǎn)n從前一信道h接入到信道m(xù)所產(chǎn)生的切換時(shí)延：

(5)

式中：f表示取值為0～1之間的調(diào)節(jié)因子，用于避免時(shí)延在觀測(cè)值函數(shù)中所占比重過大；Timem表示節(jié)點(diǎn)n接入信道m(xù)的時(shí)間；Timeh,m表示從h信道開始向m信道轉(zhuǎn)換的時(shí)間。

但如果次用戶j可能正在使用信道m(xù)，則需要等待次用戶j不再使用信道m(xù)后再接入，由此產(chǎn)生排隊(duì)時(shí)延：

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

(6)

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

由此可得螞蟻轉(zhuǎn)移概率為：

(7)

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

步驟4選擇后繼節(jié)點(diǎn)。螞蟻的每一步移動(dòng)表示一個(gè)可行路徑，螞蟻選擇下一步的移動(dòng)節(jié)點(diǎn)由行動(dòng)判決依據(jù)n′決定：

(8)

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

3 方案設(shè)計(jì)

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

(9)

(10)

式中：τi表示螞蟻到達(dá)第i節(jié)點(diǎn)所經(jīng)歷時(shí)間(本文中，螞蟻每到一個(gè)節(jié)點(diǎn)就會(huì)重置時(shí)間，同時(shí)記錄螞蟻從上一個(gè)節(jié)點(diǎn)出發(fā)到到達(dá)當(dāng)前節(jié)點(diǎn)所需的時(shí)間)；τ表示循環(huán)過程所經(jīng)歷的總時(shí)間。

(11)

則可得最終的信息素更新時(shí)間系數(shù)ηi為：

(12)

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

(13)

當(dāng)一只螞蟻停留在某個(gè)節(jié)點(diǎn)不再繼續(xù)移動(dòng)時(shí)，算法的循環(huán)結(jié)束。螞蟻在移動(dòng)過程中，記錄到達(dá)每一個(gè)節(jié)點(diǎn)的時(shí)間τ，然后根據(jù)螞蟻移動(dòng)的路徑和到達(dá)各節(jié)點(diǎn)的時(shí)間對(duì)信息素矩陣中的各元素進(jìn)行更新：

(14)

傳統(tǒng)的蟻群算法是將信息素按螞蟻所經(jīng)歷的節(jié)點(diǎn)數(shù)平均將信息素分配給每一個(gè)節(jié)點(diǎn)，而通過式(14)可以將信息素按照螞蟻通過信道m(xù)到達(dá)每一個(gè)節(jié)點(diǎn)的時(shí)間來分配信息素，螞蟻達(dá)到節(jié)點(diǎn)的時(shí)間越少，則分配的信息素越多；反之，螞蟻達(dá)到節(jié)點(diǎn)的時(shí)間越多，則分配的信息素越少。

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

(15)

(16)

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

(17)

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

4 實(shí)驗(yàn)仿真及分析

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

圖1為不同可用頻譜數(shù)量下，本文算法與AOC算法、QGA算法的網(wǎng)絡(luò)收益和比較?？梢钥闯觯S著可用頻譜數(shù)量m的不斷增加，本文算法的網(wǎng)絡(luò)收益總和始終高于AOC算法和QGA算法。這是由于引入的時(shí)間參數(shù)對(duì)信道的效益起到了較好的調(diào)節(jié)作用，大大減少了認(rèn)知用戶的搜索時(shí)間，從而使系統(tǒng)的網(wǎng)絡(luò)收益得到顯著提高。

圖1 三種算法在可用頻譜數(shù)不同時(shí)的網(wǎng)絡(luò)收益和

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

圖2 三種算法在認(rèn)知用戶數(shù)不同時(shí)的網(wǎng)絡(luò)收益和

圖3為不同認(rèn)知用戶數(shù)量下，本文算法與AOC算法、QGA算法的系統(tǒng)公平性比較?？梢钥闯?，本文算法的系統(tǒng)公平性始終優(yōu)于AOC算法和QGA算法。這是由于隨著認(rèn)知用戶數(shù)量不斷增加，認(rèn)知用戶之間的競(jìng)爭(zhēng)也隨之增大，本文算法通過比較認(rèn)知用戶的信道使用情況來權(quán)衡頻譜分配公平性，使系統(tǒng)公平性得到顯著提高。

圖3 三種算法在認(rèn)知用戶數(shù)不同時(shí)的公平性

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

圖4 三種算法在認(rèn)知用戶數(shù)不同時(shí)的收斂速度

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

圖5 三種算法在可用頻譜數(shù)不同時(shí)的系統(tǒng)吞吐量

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

5 結(jié) 語(yǔ)

本文通過引入時(shí)間因子對(duì)信息素的計(jì)算方法進(jìn)行改進(jìn)，給出一種基于多態(tài)蟻群優(yōu)化算法的認(rèn)知無(wú)線電頻譜分配方案。通過動(dòng)態(tài)考慮認(rèn)知用戶的頻譜接入時(shí)間，有效加快頻譜分配速度，降低認(rèn)知用戶間的競(jìng)爭(zhēng)，大幅提高信道利用率，同時(shí)也有效提升了系統(tǒng)的公平性。仿真實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)認(rèn)知無(wú)線電頻譜分配算法相比，本文算法可以顯著提升系統(tǒng)的網(wǎng)絡(luò)收益、公平性、收斂速度和吞吐量等性能。