一種認(rèn)知無(wú)線電頻譜分配的精英量子狼群算法

徐夢(mèng)穎，盧 毅，周 杰

（石河子大學(xué) 信息科學(xué)與技術(shù)學(xué)院，新疆 石河子 832000）

0 引 言

認(rèn)知無(wú)線電（Cognitive Radio，CR）是無(wú)線通信的重要方式之一，隨著通信技術(shù)的不斷發(fā)展，人們對(duì)頻譜的需求也急劇增加。然而目前能夠應(yīng)用于無(wú)線信號(hào)傳輸?shù)念l譜少之又少[1]。衛(wèi)星、廣播等都需要占用頻譜資源，所以用于軍用、民用通信的頻譜更加稀缺，因此，對(duì)頻譜資源合理地分配顯得尤為重要[2]。最大限度地利用頻譜資源，不僅能夠節(jié)約大量成本，還能提高通信速率，對(duì)通信系統(tǒng)的發(fā)展有十分重要的意義[3?4]。

CR中有授權(quán)用戶和認(rèn)知用戶，授權(quán)用戶擁有信道的固定使用權(quán)，認(rèn)知用戶即次用戶，當(dāng)授權(quán)用戶使用某個(gè)信道時(shí)，次用戶不得再占用該信道，當(dāng)信道處于空閑狀態(tài)時(shí)，次用戶才能爭(zhēng)取該信道的使用權(quán)。對(duì)次用戶合理地分配信道可以讓認(rèn)知用戶合理地使用頻譜資源并進(jìn)行通信，緩解頻譜資源使用的緊張形勢(shì)[5?6]。然而目前，雖然頻譜分配算法一定程度上提高了頻譜分配的公平性，但是系統(tǒng)網(wǎng)絡(luò)效益較低。

為優(yōu)化CR的網(wǎng)絡(luò)效益，本文設(shè)計(jì)了圖論著色模型，在傳統(tǒng)狼群算法基礎(chǔ)上提出了精英量子狼群算法（Elite Quantum Wolf Pack Algorithm，EQWPA），該算法結(jié)合了量子進(jìn)化、精英選擇與狼群算法。狼群算法（Wolf Pack Algorithm，WPA）是模擬狼群圍捕獵物行為的一種仿生學(xué)智能算法，該算法已經(jīng)被廣泛應(yīng)用于人工神經(jīng)網(wǎng)絡(luò)、車間調(diào)度等領(lǐng)域[7?8]。改進(jìn)的精英量子狼群算法能夠優(yōu)化頻譜分配后的網(wǎng)絡(luò)效益，

緩解頻譜稀缺帶來(lái)的通信擁塞，在仿真中，將EQWPA和遺傳算法、蟻群算法（Ant Colony Optimization，ACO）進(jìn)行了仿真對(duì)比。仿真結(jié)果表明，較GA與ACO，EQWPA收斂速度更快，尋優(yōu)效果更好。當(dāng)次用戶數(shù)不變頻譜數(shù)增加時(shí)，網(wǎng)絡(luò)效益不斷增大，當(dāng)頻譜數(shù)不變，次用戶數(shù)增加時(shí)，系統(tǒng)吞吐量呈上升趨勢(shì)，算法有效地提升了頻譜分配的網(wǎng)絡(luò)效益與吞吐量。

1 相關(guān)工作

CR是提升頻譜資源使用效率的一種有效方式。歷年來(lái)，研究學(xué)者通過(guò)各種方式優(yōu)化頻譜使用率，包括圖論著色模型[9]、博弈論[10]、拍賣理論[11]等。這些頻譜分配方法一定程度上緩解了頻譜資源使用的緊張形勢(shì)，再通過(guò)智能優(yōu)化算法[12?14]可以有效對(duì)分配的性能進(jìn)行改進(jìn)。文獻(xiàn)[15]給出了一種改進(jìn)的遺傳算法（Genetic algorithm，GA），并借助圖論模型，通過(guò)該種方法來(lái)優(yōu)化頻譜資源分配。仿真實(shí)驗(yàn)結(jié)果表明，該方法優(yōu)化過(guò)的網(wǎng)絡(luò)吞吐量能夠被有效地提高，然而算法的收斂速度較慢。文獻(xiàn)[16]利用改進(jìn)的粒子群算法（Particle Swarm Optimization，PSO）對(duì)頻譜分配進(jìn)行優(yōu)化，實(shí)驗(yàn)結(jié)果表明，該方法使系統(tǒng)獲得了更高的網(wǎng)絡(luò)效益，但是當(dāng)信道的數(shù)量較大時(shí)，算法的執(zhí)行效率會(huì)降低。

2 數(shù)學(xué)模型

為了更好地描述該系統(tǒng)，圖論著色模型被用于解決頻譜分配問(wèn)題。圖論中的圖可以用于描述一個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。借助圖論模型，認(rèn)知無(wú)線電系統(tǒng)的頻譜分配可由4個(gè)矩陣描述，包括頻譜可用矩陣、效益矩陣、分配矩陣以及干擾矩陣。在一定區(qū)域內(nèi)假設(shè)有M個(gè)頻譜，N個(gè)次用戶數(shù)，當(dāng)在該系統(tǒng)中，對(duì)次用戶進(jìn)行頻譜分配可有效使用空閑信道，而使CR頻譜分配效益最大化。

頻譜可通過(guò)矩陣A來(lái)表示，其中，A={an,m|an,m={0,1}}N×M，該矩陣可以用于判定頻譜能否被次用戶使用，當(dāng)an,m=1時(shí)，頻譜m（m={1,2,…,M}）可以被分配給次用戶n（n={1,2,…,N}），而an,m=0時(shí)，則表示頻譜不可用。主用戶的坐標(biāo)及其發(fā)射功率都會(huì)對(duì)頻譜的使用產(chǎn)生影響，當(dāng)頻譜在主用戶覆蓋范圍內(nèi)，則其不能被次用戶使用；在主用戶發(fā)射功率范圍之外的次用戶享有頻譜的使用權(quán)。

效益矩陣可通過(guò)矩陣B表示，B={ bn,m}N×M，該矩陣表示頻譜m被分配給次用戶n時(shí)產(chǎn)生的效益值的大小，效益值由不同因素決定，信道、認(rèn)知用戶所處的環(huán)境、調(diào)制編碼方式、發(fā)射功率都會(huì)影響效益值的大小。

干擾矩陣通過(guò)矩陣C表示，C={cn,k,m|cn,k,m={0,1}}N×N×M，其表示兩個(gè)次用戶n和k在爭(zhēng)取一個(gè)頻譜m時(shí)，是否產(chǎn)生干擾。當(dāng)cn,k,m=1時(shí)，表示次用戶之間互相干擾，則次用戶n和k不能同時(shí)被分配到頻譜m；否則，不會(huì)產(chǎn)生干擾，頻譜m可以被同時(shí)分配給兩個(gè)次用戶。當(dāng)n=k時(shí)，cn,k,m=1-an,m。

分配矩陣通過(guò)矩陣D表示，D={dn,m|dn,m={0,1}}N×M，該矩陣表示了頻譜m與次用戶n之間的分配關(guān)系，當(dāng)dn,m=1時(shí)，頻譜m被分給次用戶n，當(dāng)dn,m=0時(shí)，頻譜m不被分配給次用戶n。

在式（1）中，當(dāng)次用戶分配到一個(gè)頻譜時(shí)，則會(huì)產(chǎn)生一個(gè)效益值，該值可以用rn表示。在式（2）中，f(r)表示所有次用戶分配頻譜后產(chǎn)生的總效益，在EQWPA算法中，其優(yōu)化目標(biāo)是在迭代過(guò)程中找到每一代種群中網(wǎng)絡(luò)效益值最高的個(gè)體。分配矩陣D要滿足在式（3）中根據(jù)干擾矩陣的約束條件，使得兩次用戶之間沒(méi)有干擾產(chǎn)生。吞吐量是評(píng)價(jià)數(shù)據(jù)傳輸速率的指標(biāo)，其計(jì)算方式如式（4）所示。

3 基于精英量子狼群算法的無(wú)線電頻譜分配

本文為提高CR中的網(wǎng)絡(luò)效益，提出精英量子狼群算法，該算法在狼群算法的基礎(chǔ)上結(jié)合量子計(jì)算、精英選擇。通過(guò)量子編碼提高種群多樣性，從而提高解的質(zhì)量，精英算子可以將每一代中，網(wǎng)絡(luò)效益值最高的狼保留至下一代。EQWPA的步驟包括種群編碼、種群初始化、計(jì)算適應(yīng)度、狼群更新等步驟，其中，狼群更新步驟包括探狼游走行為，頭狼召喚、猛狼奔襲和圍攻、優(yōu)勝劣汰。在EQWPA中，當(dāng)執(zhí)行到最大迭代次數(shù)算法停止，并輸出最優(yōu)網(wǎng)絡(luò)效益值，精英量子狼群中會(huì)淘汰頻譜分配效益值最差的若干只狼，并通過(guò)精英算子將每一代適應(yīng)度最高的狼保留至下一代，這就是狼群中以“優(yōu)勝劣汰”和“適者生存”為原則的生存機(jī)制。EQWPA算法的具體步驟如下所述。

3.1 種群編碼與初始化

在EQWPA中，種群的編碼方式通過(guò)量子編碼來(lái)完成，通過(guò)量子位編碼解決解頻譜分配問(wèn)題。量子編碼方式通常由量子位與二進(jìn)制數(shù)字組成，量子的狀態(tài)可以由式（5）表示。

式中，α和β分別表示兩個(gè)狀態(tài)位的概率幅，表示量子態(tài)坍縮到0和1的概率分別為|α|2和|β|2，兩個(gè)概率需滿足式（6）的歸一化條件：

一個(gè)解的編碼長(zhǎng)度為D，該解就同時(shí)表示了2D個(gè)狀態(tài)。編碼長(zhǎng)度為頻譜可用矩陣中值為1的總個(gè)數(shù)，可由式（7）計(jì)算得到。

具有D個(gè)量子比特位的第i個(gè)量子的編碼方式為：

式 中，| αd|2+| βd|2=1(d=1,2,…,D)，在 經(jīng) 歷 量 子 位 編碼后，種群在第t代的表示形式為qi={i=1,2,…,S}，在第t代種群中第i只狼的編碼形式為：

種群測(cè)量可以將種群中每個(gè)量子位的疊加態(tài)坍縮到與觀測(cè)結(jié)果相對(duì)應(yīng)的狀態(tài)，即二進(jìn)制解集P(t)。其中，通過(guò)式（10）可知，改變后的狀態(tài)P(t)由0和1組成，二進(jìn)制數(shù)的生成方式由隨機(jī)產(chǎn)生的小數(shù)rand與第i個(gè)個(gè)體中第d個(gè)量子位的概率| αi,d|2作比較得到。式中的rand為0到1之間的隨機(jī)小數(shù)。轉(zhuǎn)換后的狀態(tài)P(t)用于計(jì)算個(gè)體的適應(yīng)度。

在狼群初始化時(shí)，首先初始化參數(shù)，設(shè)置個(gè)體數(shù)量及維數(shù)，在獲得種群的測(cè)量值后，每個(gè)P(t)中的二進(jìn)制串代表一種頻譜分配方案，當(dāng)頻譜可用矩陣中的數(shù)值為1時(shí)，則對(duì)分配矩陣中的相應(yīng)位置上的數(shù)值進(jìn)行編碼，若頻譜可用矩陣中的數(shù)值為0時(shí)，則不改變分配矩陣中相應(yīng)位置上的數(shù)值。具體的編碼方式為：首先，生成一個(gè)個(gè)體，將個(gè)體從的疊加狀態(tài)轉(zhuǎn)換到其相應(yīng)的觀測(cè)狀態(tài)P(t)，當(dāng)頻譜可用矩陣中的數(shù)值為1時(shí)，將分配矩陣相應(yīng)位置上的數(shù)值按照個(gè)體的編碼順序逐行用一個(gè)測(cè)量值進(jìn)行替換；當(dāng)頻譜可用矩陣中數(shù)值為0時(shí)，則不改變分配矩陣相應(yīng)位置上的數(shù)值。

種群中個(gè)體的評(píng)價(jià)方式通過(guò)式（2）計(jì)算網(wǎng)絡(luò)效益，網(wǎng)絡(luò)總效益越高，個(gè)體質(zhì)量越好，頻譜分配后的網(wǎng)絡(luò)效益值越高。

3.2 量子旋轉(zhuǎn)門更新

在EQWPA中，對(duì)網(wǎng)絡(luò)效益較低的個(gè)體上的量子位qi進(jìn)行量子旋轉(zhuǎn)門更新，第i個(gè)個(gè)體中第d個(gè)量子位更新過(guò)程如式（11）所示。

其中，θ的更新方式如下：

當(dāng)個(gè)體pi,d=0且每一代種群中適應(yīng)度最高的個(gè)體best_pi,d=1時(shí)，t值設(shè)置如式（13）所示，rand為0~1之間的隨機(jī)數(shù)。

當(dāng)個(gè)體pi,d=1且每一代種群中適應(yīng)度最高的個(gè)體best_pi,d=0時(shí)，t值設(shè)置如下：

3.3 狼群尋優(yōu)過(guò)程

1）游走行為

對(duì)適應(yīng)度按照從大到小排序，網(wǎng)絡(luò)效益最高的個(gè)體被視為頭狼，除頭狼外的前若干個(gè)個(gè)體被視為探狼。每只探狼只能在其范圍內(nèi)的指定步數(shù)內(nèi)執(zhí)行游走行為，即隨機(jī)搜索操作，在每一次迭代中，按照式（11）更新當(dāng)前探狼。若更新后的探狼獲取到的網(wǎng)絡(luò)效益大于頭狼獲得的網(wǎng)絡(luò)效益，探狼代替頭狼發(fā)起召喚行為；否則，重復(fù)執(zhí)行探狼游走行為Tmax次。頭狼個(gè)體發(fā)起召喚后，狼群中除了頭狼與探狼之外的猛狼向頭狼的位置不斷靠近，通過(guò)式（15）計(jì)算猛狼與頭狼之間的距離dw來(lái)確定奔襲行為或圍攻行為。

2）奔襲行為

當(dāng)猛狼收到頭狼的召喚后，頭狼與猛狼之間的距離dw大于判定距離dn，則執(zhí)行奔襲行為。如式（16）所示，step1為奔襲步長(zhǎng)。

3）圍攻行為

在式（17）中，當(dāng)頭狼與猛狼之間的距離不大于判定距離，則執(zhí)行圍攻行為。其中，step2為圍攻步長(zhǎng)。

將更新后的猛狼轉(zhuǎn)換為坍縮后的狀態(tài)P(t)并計(jì)算網(wǎng)絡(luò)效益，更新頭狼并發(fā)起召喚行為。

4）優(yōu)勝劣汰

在EQWPA中，狼群內(nèi)的淘汰機(jī)制按照“優(yōu)勝劣汰”的原則進(jìn)行，網(wǎng)絡(luò)效益最高的個(gè)體被視為精英個(gè)體保留至下一代中，并淘汰種群內(nèi)最差的30%的個(gè)體，通過(guò)量子編碼重新產(chǎn)生新的個(gè)體。狼群更新過(guò)程執(zhí)行到最大迭代次數(shù)后算法停止，并輸出最優(yōu)網(wǎng)絡(luò)效益值。

EQWPA的算法流程圖如圖1所示。

圖1 EQWPA流程圖

4 仿真與實(shí)驗(yàn)

4.1 仿真環(huán)境

本文在仿真實(shí)驗(yàn)中，使用Windows 10的操作系統(tǒng)通過(guò)Matlab R2014a對(duì)基于EQWPA的頻譜分配優(yōu)化測(cè)試系統(tǒng)進(jìn)行仿真測(cè)試，以達(dá)到在迭代過(guò)程中提高網(wǎng)絡(luò)效益的目的。仿真區(qū)域大小設(shè)置為200 m×200 m，在該區(qū)域內(nèi)隨機(jī)布置主用戶與次用戶，且用戶的位置、發(fā)射功率固定不變，忽略噪聲等干擾因素，以保證可用矩陣、干擾矩陣、分配矩陣的值也不會(huì)改變。

在認(rèn)知無(wú)線電中，主用戶的數(shù)量設(shè)置為10。在EQWPA、GA、ACO三種算法中，個(gè)體數(shù)為20個(gè)，最大迭代次數(shù)為200次，實(shí)驗(yàn)次數(shù)為50次。

4.2 實(shí)驗(yàn)數(shù)據(jù)

在圖2中，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為網(wǎng)絡(luò)效益，當(dāng)次用戶數(shù)N為20，頻譜M的數(shù)量為15時(shí)，三條曲線分別代表EQWPA、GA、ACO在兩百次迭代時(shí)網(wǎng)絡(luò)效益的變化情況。在迭代前期時(shí)，算法尋優(yōu)速度較快；在迭代后期，三種算法逐漸收斂；迭代至200代時(shí)，EQWPA、GA、ACO在50次實(shí)驗(yàn)后的平均網(wǎng)絡(luò)效益值為49.058，44.321和39.572。

圖2網(wǎng)絡(luò)效益對(duì)比圖（M=15，N=20）

圖3 表示當(dāng)次用戶數(shù)量與頻譜的數(shù)量分別為20和30時(shí)，EQWPA、GA、ACO在50次實(shí)驗(yàn)后的平均網(wǎng)絡(luò)效益值對(duì)比圖。在200次迭代后，EQWPA、GA和ACO優(yōu)化過(guò)的網(wǎng)絡(luò)效益值分別達(dá)到96.607，92.524和86.613。由此可見，在傳統(tǒng)狼群算法的基礎(chǔ)上，精英選擇算子將每一代含有最高網(wǎng)絡(luò)效益值的個(gè)體保留至下一代，不僅避免了當(dāng)前最優(yōu)個(gè)體不被破壞，而且能夠保證在下一代中淘汰最差個(gè)體，提高算法尋優(yōu)能力，保證算法全局收斂。EQWPA通過(guò)加入量子計(jì)算以提高種群的多樣性，靠提高算法的收斂速度，有效地提高了網(wǎng)絡(luò)效益值。

圖3 網(wǎng)絡(luò)效益對(duì)比圖（M=30，N=20）

EQWPA、GA與ACO優(yōu)化過(guò)的網(wǎng)絡(luò)效益提升百分比表1所示，結(jié)果表明，EQWPA優(yōu)化過(guò)的頻譜分配網(wǎng)絡(luò)效益明顯大于遺傳算法與蟻群算法。

表1 EQWPA優(yōu)化過(guò)的網(wǎng)絡(luò)效益相較于GA與ACO提升百分比

在圖4中，次用戶數(shù)保持為20個(gè)，該圖表示EQWPA、GA、ACO在200次迭代后次用戶數(shù)保持不變的情況下，網(wǎng)絡(luò)效益值隨頻譜數(shù)升高的變化情況。如圖4所示，EQWPA優(yōu)化過(guò)的網(wǎng)絡(luò)效益值大于GA和ACO。當(dāng)頻譜數(shù)增加時(shí)，次用戶分配到的信道數(shù)量增加，從而提升了網(wǎng)絡(luò)效益。

圖4頻帶數(shù)增加時(shí)網(wǎng)絡(luò)效益對(duì)比圖

圖5 為EQWPA、GA、ACO的吞吐量變化圖，當(dāng)頻譜數(shù)為10時(shí)，EQWPA、GA、ACO優(yōu)化過(guò)的吞吐量在相同時(shí)間范圍內(nèi)隨著用戶數(shù)的增加而不斷提高。說(shuō)明與GA、ACO相比，EQWPA具有更好的優(yōu)化性能。

圖5 吞吐量變化圖

5 結(jié) 語(yǔ)

本文針對(duì)CR中的頻譜分配問(wèn)題，首先設(shè)計(jì)數(shù)學(xué)模型，并提出一種改進(jìn)的精英量子狼群算法，該算法在狼群算法的基礎(chǔ)上結(jié)合了量子計(jì)算與精英選擇，采用量子編碼并生成初始種群，通過(guò)量子旋轉(zhuǎn)門更新種群中的交叉?zhèn)€體。狼群的尋優(yōu)過(guò)程包括游走行為、圍攻行為和奔襲行為，體現(xiàn)了狼群協(xié)調(diào)合作的系統(tǒng)性、種群多樣性、分布式等特點(diǎn)，提高了算法的收斂速度。精英選擇算子保留了每一代最好的個(gè)體，避免破壞最優(yōu)個(gè)體，提高了算法尋優(yōu)能力，保證了算法全局收斂。在仿真實(shí)驗(yàn)中，將該算法與GA、ACO進(jìn)行仿真對(duì)比，仿真結(jié)果顯示，精英量子狼群算法有效提高了網(wǎng)絡(luò)效益和吞吐量，提升了頻譜資源利用率。但是隨著問(wèn)題規(guī)模的增大，運(yùn)行時(shí)間延長(zhǎng)，如何降低EQWPA的運(yùn)行時(shí)間、提高算法的尋優(yōu)能力還需要進(jìn)一步通過(guò)研究加以解決。

注：本文通訊作者為周杰。