基于改進(jìn)二進(jìn)制灰狼算法的頻譜分配

徐 航，張達(dá)敏，王依柔，宋婷婷，樊 英

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽 550025)

0 引 言

隨著當(dāng)今通信技術(shù)的快速發(fā)展，超高速、超高容量的5G技術(shù)也將在幾年內(nèi)商業(yè)化，而無線通信業(yè)務(wù)的增加導(dǎo)致無線頻譜資源稀缺的問題日益嚴(yán)重，而且當(dāng)前頻譜資源的使用率低，存在較多的頻譜空洞[1]，為了解決這一問題，許多專家提出了認(rèn)知無線電(cognitive radio，CR)[2]，而動態(tài)頻譜分配則是認(rèn)知無線技術(shù)中的焦點(diǎn)問題，其主要通過動態(tài)感知授權(quán)頻譜當(dāng)前的使用狀態(tài)，從而達(dá)到最大化頻譜利用率的目的。

在CR系統(tǒng)中，一般用來實現(xiàn)動態(tài)頻譜分配的模型有博弈論模型[3]、干擾溫度模型[4]、拍賣競價模型[5]和圖論著色模型[6]等，由于這些模型在優(yōu)化系統(tǒng)效益和用戶間公平性等方面有比較明顯的缺陷，所以許多研究將智能優(yōu)化算法用于優(yōu)化該問題。文獻(xiàn)[7]提出了一種基于改進(jìn)二進(jìn)制粒子群算法的頻譜分配策略，對粒子速度公式進(jìn)行離散化改進(jìn)，但算法難以得到最優(yōu)解。文獻(xiàn)[8]提出了基于改進(jìn)遺傳算法的頻譜分配策略，但改進(jìn)遺傳算法仍然容易早熟，而且收斂速度較慢。針對傳統(tǒng)的優(yōu)化算法存在的缺陷，而相關(guān)研究結(jié)果表明許多群體智能優(yōu)化算法[9,10]在工程領(lǐng)域也有不錯的實用效果，本文采用群體智能優(yōu)化算法來解決上述問題。

本文在圖論著色模型的基礎(chǔ)上，提出一個改進(jìn)二進(jìn)制灰狼優(yōu)化算法(improved binary grey wolf optimizer，BGWO)來優(yōu)化認(rèn)知無線電頻譜分配問題，實驗結(jié)果表明，本文的二進(jìn)制灰狼優(yōu)化算法能有效提高系統(tǒng)效益和認(rèn)知用戶接入公平性，這對優(yōu)化認(rèn)知無線電系統(tǒng)的性能具有重要的意義。

1 連續(xù)灰狼算法

1.1 等級機(jī)制

自然界中的灰狼群具有嚴(yán)格的等級制度，受這種等級制度的啟發(fā)，有人對灰狼算法(grey wolf optimizer，GWO)[11]進(jìn)行了研究。在捕食過程中，整個灰狼群等級像金字塔形狀一樣排列，頂層的α狼決定狼群的所有行動，其它狼不斷向頭狼靠近；位于第二層稱為β狼，負(fù)責(zé)協(xié)助α做出管理決策；第三層的δ狼和底層的ω狼，負(fù)責(zé)聽從α及β的指令，主要作用是平衡種群內(nèi)部關(guān)系，這種分層的等級制度使狼群能有序地從各個方位完成各種捕食任務(wù)。

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

在灰狼算法中，首先對狼群的捕獵過程進(jìn)行建模，對空間中隨機(jī)生成的灰狼個體進(jìn)行適應(yīng)度評估，把適應(yīng)度值最好的前3頭灰狼分別記為α、β、δ，隨著算法的進(jìn)行更新狼群位置，最終到達(dá)最優(yōu)解附近。在這個過程中，首先實現(xiàn)對獵物進(jìn)的包圍，更新公式如下所示

X(t+1)=X*(t)-A·D

(1)

D=|C×X*(t)-X(t)|

(2)

其中，X(t)為當(dāng)前灰狼位置，X*(t)為當(dāng)前獵物位置，t為當(dāng)前迭代次數(shù)，A,C表示系數(shù)向量，定義如下

A=2ar1-a

(3)

C=2r2

(4)

其中，r1和r2為[0,1]的隨機(jī)數(shù)，a表示一個隨迭代次數(shù)增加由2線性遞減到0的收斂因子，定義為

a=2-2t/Tmax

(5)

其中，Tmax為最大迭代次數(shù)。

當(dāng)狼群發(fā)現(xiàn)獵物后，最靠近獵物的頭狼α指揮等級較低的狼群執(zhí)行捕殺任務(wù)，通過模擬狼群的捕食過程，不斷迭代使狼群向最優(yōu)解靠近，算法首先確認(rèn)當(dāng)前狼群中解的前3名，然后按照下式不斷引導(dǎo)其它成員向最優(yōu)解移動，更新狼群的位置

Dα=|C1×Xα-X|

(6)

Dβ=|C2×Xβ-X|

(7)

Dδ=|C3×Xδ-X|

(8)

X1=Xα-A1·Dα

(9)

X2=Xβ-A2·Dβ

(10)

X3=Xδ-A3·Dδ

(11)

(12)

1.3 二進(jìn)制灰狼算法

GWO在提出之時是用于解決優(yōu)化函數(shù)問題，而在本文頻譜分配問題中要解決的是常見的0、1問題，因此需要通過特定的轉(zhuǎn)換函數(shù)實現(xiàn)連續(xù)解空間到二元空間的轉(zhuǎn)換，大多研究中常使用Sigmoid函數(shù)[12]來實現(xiàn)連續(xù)到離散域的轉(zhuǎn)換，轉(zhuǎn)換函數(shù)表達(dá)式如下

(13)

(14)

2 改進(jìn)二進(jìn)制灰狼算法

2.1 非線性收斂因子

在灰狼算法中，設(shè)置算法參數(shù)A來調(diào)節(jié)算法的勘探能力，當(dāng)|A|≥1時，灰狼群將擴(kuò)大搜索范圍，即著重全局搜索階段；當(dāng)|A|<1時，灰狼群將收縮包圍圈，對獵物發(fā)動攻擊，即著重局部搜索階段。根據(jù)式(3)可知，算法參數(shù)A是由參數(shù)a決定的，所以a可以較大程度影響算法的優(yōu)化結(jié)果，但算法中a隨著迭代次數(shù)的增加呈線性遞減，為了合理平衡算法的全局和局部搜索能力，有必要對灰狼優(yōu)化算法的參數(shù)a進(jìn)行優(yōu)化，本文提出了一個非線性收斂因子，公式如下

(15)

其中，t為迭代次數(shù)，ainitial表示a的初始值2，Tmax為最大迭代次數(shù)，由圖1可知，在算法前期，隨著迭代次數(shù)的增加，a從2非線性先緩后急遞減，此時a減小速度緩慢，即a>1所占迭代次數(shù)比例更大，從而加強(qiáng)了算法的全局搜索能力；到迭代后期，a>1所占迭代次數(shù)比例減小，而且到后期減小速率明顯加快，此時算法快速進(jìn)行局部開發(fā)階段，因此本文通過非線性收斂因子來加強(qiáng)算法的全局搜索能力。

圖1 收斂因子a的對比

2.2 柯西擾動策略

GWO容易出現(xiàn)早熟等問題，為降低這些缺陷對算法的影響，在原始位置更新公式的基礎(chǔ)上，提出一種帶有柯西擾動算子的位置更新方案，主要思想是利用柯西變異的優(yōu)勢，擴(kuò)大狼群的分布區(qū)域，從而減小算法局部早熟的概率。一維標(biāo)準(zhǔn)的Cauchy分布的概率密度函數(shù)[13]如下所示

(16)

Cauchy分布的概率密度曲線類似于一個鐘形，峰值較小但在兩端的分布長且平緩，無限接近于x軸而不與坐標(biāo)軸相交，這種特征意味著通過柯西變異，可以產(chǎn)生與原點(diǎn)相距較遠(yuǎn)的隨機(jī)數(shù)，也意味著經(jīng)過Cauchy變異后的灰狼個體在一定程度上具備了可以迅速跳出局部最優(yōu)區(qū)域的能力，同時，利用Cauchy分布峰值較低的特點(diǎn)可以減小變異后的個體在鄰域周圍搜索的時間。

2.3 自適應(yīng)權(quán)重

在GWO中，如果α狼在某一代捕獲到局部最優(yōu)解時，將導(dǎo)致整個狼群向局部最優(yōu)區(qū)域收斂，而且GWO在全局搜索和局部開發(fā)階段時權(quán)重是固定的，受粒子群算法慣性權(quán)重的啟發(fā)，同時為了提高局部搜索的能力，引入一個自適應(yīng)的權(quán)重因子，不斷地通過非線性權(quán)重的調(diào)整，從而強(qiáng)化算法跳出局部最優(yōu)區(qū)域的能力。公式如下

(17)

其中，t為當(dāng)前迭代次數(shù)，Tmax為最大迭代次數(shù)，ωmax=0.9，ωmin=0.4，k為控制ω曲線跳躍幅度的縮放因子，本文k=0.05，nTent表示由Tent混沌映射[14]產(chǎn)生的均勻隨機(jī)數(shù)。上式中的前兩項是為了實現(xiàn)權(quán)重非線性遞減，且服從ω∈[0.4,0.9]，此時的權(quán)重能使算法發(fā)揮最優(yōu)的尋優(yōu)效果[15]；第三項的取值是為了實現(xiàn)了權(quán)重的動態(tài)變化，使算法在迭代前期權(quán)值較大時也能產(chǎn)生較小的權(quán)值，到迭代后期權(quán)重變化較小且平穩(wěn)時也有機(jī)會獲得較大的權(quán)值，進(jìn)而提高算法收斂精度。綜合以上改進(jìn)策略后式(9)～式(12)的位置更新公式如下

X1=(Xα-A1·Dα)·(1+i·cauchy(0,1))

(18)

X2=(Xβ-A2·Dβ)·(1+i·cauchy(0,1))

(19)

X3=(Xδ-A3·Dδ)·(1+i·cauchy(0,1))

(20)

(21)

2.4 二進(jìn)制灰狼算法

為了更好處理實際中的離散問題，連續(xù)域到離散域的研究也是必要的，有研究顯示Sigmoid函數(shù)離散化后的算法會出現(xiàn)位置不變等缺點(diǎn)，因此本文引進(jìn)一個新的離散轉(zhuǎn)換函數(shù)[16]來實現(xiàn)頻譜分配時的0、1轉(zhuǎn)換操作

(22)

(23)

式中：rand為[0,1]分布的隨機(jī)數(shù)，通過上述轉(zhuǎn)換，將連續(xù)變量更好地轉(zhuǎn)換為離散變量，進(jìn)而提高整個頻譜分配的效果。

3 基于灰狼算法的頻譜分配

3.1 基于圖論著色的頻譜分配模型

本文利用灰狼算法實現(xiàn)頻譜分配的目的是將頻譜資源智能且有效地分配給認(rèn)知用戶，同時要滿足主用戶對于頻譜資源正常使用的需求。假設(shè)在一個X×Y的區(qū)域中分布M個完全正交的可用頻譜，存在I個主用戶和N個認(rèn)知用戶，認(rèn)知用戶在不對其他用戶(主用戶和認(rèn)知用戶)產(chǎn)生干擾的前提下可以使用多個頻譜，當(dāng)主用戶i(i=1,2,…,I)分配的頻譜為m(m=1,2,…,M)，認(rèn)知用戶n(n=1,2,…,N)機(jī)會接入m時，則主用戶在頻譜m的覆蓋范圍是以i為中心rii,m為半徑的圓形區(qū)域，認(rèn)知用戶n在頻譜m的覆蓋范圍是以n為中心rnn,m為半徑的圓形區(qū)域，假設(shè)用戶間干擾只由用戶的干擾距離決定，如圖2所示，認(rèn)知用戶1會對主用戶1產(chǎn)生干擾，所以認(rèn)知用戶1不能使用主用戶1的授權(quán)信道，同理，認(rèn)知用戶2不能使用主用戶2的授權(quán)信道，同時，認(rèn)知用戶間存在干擾，所以認(rèn)知用戶1、2不能同時接入同一授權(quán)頻譜。

圖2 認(rèn)知無線網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

本文將認(rèn)知無線網(wǎng)絡(luò)的頻譜分配建模為圖論著色問題，用無向圖的形式來表示用戶間的關(guān)系，其中頻譜分配涉及的空閑矩陣L、效益矩陣B、干擾約束矩陣C和無干擾分配矩陣A的定義同文獻(xiàn)[17]。

定義1 用戶效益R。R={βn}N×1，其中βn表示認(rèn)知用戶n在無干擾分配矩陣A的前提下，在M個信道上所取得的全部收益，表示為

(24)

則系統(tǒng)總效益U(R)表示為

(25)

定義2 最大系統(tǒng)效益Umax。認(rèn)知無線網(wǎng)絡(luò)頻譜分配的目標(biāo)即為最大化系統(tǒng)總效益U(R)，則頻譜分配優(yōu)化問題可表示如下

(26)

則最大平均系統(tǒng)效益表示為

(27)

定義3 認(rèn)知用戶接入公平性Ufair。其目標(biāo)是確保頻譜分配過程中認(rèn)知用戶的接入公平性。其公式定義為

(28)

在頻譜分配問題的仿真階段，為了更明顯地驗證頻譜分配是否有效，將Umax、Umean和Ufair作為判斷本文頻譜分配系統(tǒng)是否有效的指標(biāo)。

3.2 改進(jìn)二進(jìn)制灰狼算法的頻譜分配

在本文提出的關(guān)于頻譜分配優(yōu)化的IBGWO算法中，每個領(lǐng)頭狼α的位置使用一串二進(jìn)制編碼來表示，用于代表一個有效的頻譜分配方案。求解最大系統(tǒng)總效益情況下的無干擾分配矩陣A是頻譜分配的最終目標(biāo)，通過上述空閑矩陣中認(rèn)知用戶使用信道的具體情況，可以確定矩陣A中的所有數(shù)字，若ln,m=0，表示認(rèn)知用戶n沒有獲得使用信道m(xù)的權(quán)限，這時對應(yīng)A中相應(yīng)位置的an,m一定為0；若ln,m=1，那么an,m可能為0或1，此時只需對矩陣中元素為1的位置進(jìn)行編碼，記錄矩陣L中元素1的個數(shù)，即解的編碼長度D，計算公式如下

(29)

在頻譜分配模型中，狼群的初始位置編碼是隨機(jī)生成的，對于認(rèn)知用戶間的干擾也應(yīng)該考慮其中，所以，需要對個體的位置進(jìn)行約束處理。對任何信道m(xù)，首先確定C中滿足cn,k,m=1的條件下所有n和k的情況，同時判斷A中的an,m和ak,m的值是否滿足同時為1的情況，假如均為1，則隨機(jī)將其中一個1設(shè)置為0，按照上述流程完成后，才能將領(lǐng)頭狼的位置編碼達(dá)到無干擾約束的要求。如圖3所示，假設(shè)在一個網(wǎng)絡(luò)環(huán)境中，認(rèn)知用戶數(shù)N=5，信道數(shù)M=4，根據(jù)上述編碼規(guī)則，可以得到解得編碼長度為8(8維)，同時得到無干擾分配矩陣A。

圖3 位置編碼與矩陣A的映射關(guān)系

3.3 頻譜分配算法流程

綜上所述，本文頻譜分配具體流程如下：

步驟1 初始化空閑矩陣L、效益矩陣B和干擾約束矩陣C，統(tǒng)計L中值為1的數(shù)量，并且記錄值為1的位置上對應(yīng)的n和m，即為L={(n,m)|ln,m=1}，L中的元素按n和m值遞增的規(guī)則排序，確定算法編碼長度；

步驟2 隨機(jī)生成二進(jìn)制編碼(初始化個體位置)，設(shè)置種群規(guī)模、最大迭代次數(shù)等，并記錄初始適應(yīng)度值；

步驟3 對相關(guān)的矩陣完成干擾約束處理過程，分配矩陣A為α狼的位置的映射，隨后判斷C中滿足cn,k,m=1的條件下的所有n和k，接下來確認(rèn)A中an,m和ak,m的值是否一樣，若均為1時，將an,m和ak,m的值隨機(jī)一個設(shè)置為0，經(jīng)過干擾約束處理后再對相應(yīng)的解進(jìn)行二進(jìn)制編碼；

步驟4 根據(jù)式(15)～式(17)更新算法參數(shù)，根據(jù)式(18)～式(20)來更新算法位置，尋找并更新全局最優(yōu)解，并使用式(22)、式(23)進(jìn)行離散操作；

步驟5 對產(chǎn)生的位置進(jìn)行干擾約束處理，根據(jù)目標(biāo)函數(shù)得到相應(yīng)的適應(yīng)度，并將最佳適應(yīng)度值對應(yīng)的位置保存為最優(yōu)位置；

步驟6 若當(dāng)前迭代次數(shù)t未超出最大迭代次數(shù)，則令t=t+1，并轉(zhuǎn)到步驟4，否則算法終止，輸出全局最優(yōu)解和適應(yīng)度值。

4 仿真實驗和結(jié)果分析

為了評估本文所提算法在頻譜分配應(yīng)用中的有效性，同時驗證每一種改進(jìn)策略的效果，利用MATLAB搭建仿真模型，在相同的拓?fù)浣Y(jié)構(gòu)下以Umax和Ufair等指標(biāo)作為優(yōu)化目的，將本文所提算法(IBGWO)與二進(jìn)制灰狼算法(BGWO)、蝙蝠算法(BA)、粒子群算法(PSO)、加入權(quán)重的灰狼算法(WGWO)、加入非線性收斂因子的灰狼算法(AGWO)和基于柯西擾動策略的灰狼算法(CGWO)進(jìn)行30次頻譜分配仿真實驗。本文實驗環(huán)境為Window10系統(tǒng)，16 G內(nèi)存和2.9 GHzCPU。

假定在一個區(qū)域中，認(rèn)知用戶N=20，可用信道數(shù)M=10，各個算法參數(shù)設(shè)置為：種群大小為40，最大迭代次數(shù)Tmax=500，ωmax=0.9，ωmin=0.4，ainitial=2，k=0.5，i=0.6，蝙蝠算法中響度A=0.9，脈沖發(fā)射率r=0.7。

4.1 不同環(huán)境下的仿真實驗

由于收斂速度和精度都是評價算法優(yōu)劣的指標(biāo)，圖4為N=20,M=10時隨機(jī)一次實驗中各個算法的收斂曲線，可以看出系統(tǒng)效益隨著迭代次數(shù)增加而增加，而IBGWO的最終系統(tǒng)效益遠(yuǎn)遠(yuǎn)高于其它算法，而且最終網(wǎng)絡(luò)效益比最差的BA高出約40%；從收斂速度來看，由于IBGWO融合了其它算法的改進(jìn)思想，所以收斂速度最快，且迭代到200次左右就趨于收斂，說明改進(jìn)后的算法具有一定有效性，進(jìn)而驗證其可以在頻譜分配時表現(xiàn)出較好的效果。

圖4 系統(tǒng)效益和迭代次數(shù)的關(guān)系

為了驗證算法在不同網(wǎng)絡(luò)環(huán)境下的頻譜分配效果，因此在N=20，M=10的條件下模擬環(huán)境中30種不同的分散情況，最終獲得多種條件下的Umax和Ufair的目標(biāo)曲線圖。由圖5和圖6可以看出，在不同網(wǎng)絡(luò)環(huán)境下，IBGWO獲得的系統(tǒng)總效益和用戶接入公平性的效果都比其它算法要好，說明加入的改進(jìn)策略提高了灰狼算法的性能，可以準(zhǔn)確快速地到達(dá)最優(yōu)解附近，所以使IBGWO在不同網(wǎng)絡(luò)環(huán)境下都能獲得較高的網(wǎng)絡(luò)效益和認(rèn)知用戶接入公平性，而且相對穩(wěn)定，同時可以看出每一個加入改進(jìn)點(diǎn)的算法都比原始算法的效果更好，說明文中所提及的改進(jìn)點(diǎn)對算法的性能具有一定的促進(jìn)作用。

圖5 不同信道的系統(tǒng)效益

圖6 不同信道的公平性

4.2 認(rèn)知用戶數(shù)對系統(tǒng)效益的影響

系統(tǒng)平均效益受很多因素影響，為了驗證不同用戶數(shù)量對系統(tǒng)平均效益的影響，設(shè)置環(huán)境中可用信道數(shù)M=10保持不變，認(rèn)知用戶數(shù)N從10遞增到30，可以總結(jié)出使用頻譜的用戶數(shù)量和系統(tǒng)平均效益之間的關(guān)系，分析圖7可知，保持環(huán)境中可用信道數(shù)量不變，如果不斷增加系統(tǒng)中認(rèn)知用戶的數(shù)目，那么認(rèn)知無線電系統(tǒng)的平均系統(tǒng)效益就會逐步減小，這是由于信道資源緊缺，才會導(dǎo)致系統(tǒng)平均效益呈下降趨勢，但是IBGWO得到的平均系統(tǒng)效益仍然比其它算法要高，進(jìn)而驗證了本文所提二進(jìn)制灰狼算法在頻譜分配中的優(yōu)越性。

圖7 平均效益與用戶數(shù)的關(guān)系

4.3 可用頻譜數(shù)對系統(tǒng)效益的影響

由于環(huán)境中頻譜數(shù)也會影響整個系統(tǒng)的效益，為了研究算法在不同信道數(shù)下的性能，設(shè)置認(rèn)知用戶數(shù)N=20保持不變，可用頻譜數(shù)M從10遞增到30，從圖8可知，當(dāng)某一區(qū)域中存在的空閑頻譜數(shù)量增加時，認(rèn)知用戶可以接入頻譜的機(jī)會也會相應(yīng)增加，所以系統(tǒng)平均效益也逐漸增大，同時IBGWO的平均效益也高于其它算法，進(jìn)而說明本文所提算法在頻譜分配當(dāng)中的有效性。

圖8 平均效益與可用信道的關(guān)系

5 結(jié)束語

針對當(dāng)前無線通信系統(tǒng)中頻譜資源緊缺的難題，本文從收斂速度和收斂精度等方向?qū)依撬惴ㄟM(jìn)行改進(jìn)，最后將其用于優(yōu)化認(rèn)知無線電頻譜分配問題，仿真結(jié)果表明：改進(jìn)后的算法一定程度上優(yōu)化了原始灰狼算法的缺陷，在解決認(rèn)知無線電頻譜分配問題時，可獲得更高的系統(tǒng)效益和更高的認(rèn)知用戶接入公平性，達(dá)到頻譜分配的最終目的。