基于改進二進制灰狼算法的頻譜分配

徐 航，張達敏，王依柔，宋婷婷，樊 英

(貴州大學 大數據與信息工程學院，貴州 貴陽 550025)

0 引 言

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

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

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

1 連續灰狼算法

1.1 等級機制

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

1.2 數學模型

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

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

(1)

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

(2)

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

A=2ar1-a

(3)

C=2r2

(4)

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

a=2-2t/Tmax

(5)

其中，Tmax為最大迭代次數。

當狼群發現獵物后，最靠近獵物的頭狼α指揮等級較低的狼群執行捕殺任務，通過模擬狼群的捕食過程，不斷迭代使狼群向最優解靠近，算法首先確認當前狼群中解的前3名，然后按照下式不斷引導其它成員向最優解移動，更新狼群的位置

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 二進制灰狼算法

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

(13)

(14)

2 改進二進制灰狼算法

2.1 非線性收斂因子

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

(15)

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

圖1 收斂因子a的對比

2.2 柯西擾動策略

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

(16)

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

2.3 自適應權重

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

(17)

其中，t為當前迭代次數，Tmax為最大迭代次數，ωmax=0.9，ωmin=0.4，k為控制ω曲線跳躍幅度的縮放因子，本文k=0.05，nTent表示由Tent混沌映射[14]產生的均勻隨機數。上式中的前兩項是為了實現權重非線性遞減，且服從ω∈[0.4,0.9]，此時的權重能使算法發揮最優的尋優效果[15]；第三項的取值是為了實現了權重的動態變化，使算法在迭代前期權值較大時也能產生較小的權值，到迭代后期權重變化較小且平穩時也有機會獲得較大的權值，進而提高算法收斂精度。綜合以上改進策略后式(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 二進制灰狼算法

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

(22)

(23)

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

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

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

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

圖2 認知無線網絡拓撲結構

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

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

(24)

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

(25)

定義2 最大系統效益Umax。認知無線網絡頻譜分配的目標即為最大化系統總效益U(R)，則頻譜分配優化問題可表示如下

(26)

則最大平均系統效益表示為

(27)

定義3 認知用戶接入公平性Ufair。其目標是確保頻譜分配過程中認知用戶的接入公平性。其公式定義為

(28)

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

3.2 改進二進制灰狼算法的頻譜分配

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

(29)

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

圖3 位置編碼與矩陣A的映射關系

3.3 頻譜分配算法流程

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

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

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

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

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

步驟5 對產生的位置進行干擾約束處理，根據目標函數得到相應的適應度，并將最佳適應度值對應的位置保存為最優位置；

步驟6 若當前迭代次數t未超出最大迭代次數，則令t=t+1，并轉到步驟4，否則算法終止，輸出全局最優解和適應度值。

4 仿真實驗和結果分析

為了評估本文所提算法在頻譜分配應用中的有效性，同時驗證每一種改進策略的效果，利用MATLAB搭建仿真模型，在相同的拓撲結構下以Umax和Ufair等指標作為優化目的，將本文所提算法(IBGWO)與二進制灰狼算法(BGWO)、蝙蝠算法(BA)、粒子群算法(PSO)、加入權重的灰狼算法(WGWO)、加入非線性收斂因子的灰狼算法(AGWO)和基于柯西擾動策略的灰狼算法(CGWO)進行30次頻譜分配仿真實驗。本文實驗環境為Window10系統，16 G內存和2.9 GHzCPU。

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

4.1 不同環境下的仿真實驗

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

圖4 系統效益和迭代次數的關系

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

圖5 不同信道的系統效益

圖6 不同信道的公平性

4.2 認知用戶數對系統效益的影響

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

圖7 平均效益與用戶數的關系

4.3 可用頻譜數對系統效益的影響

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

圖8 平均效益與可用信道的關系

5 結束語

針對當前無線通信系統中頻譜資源緊缺的難題，本文從收斂速度和收斂精度等方向對灰狼算法進行改進，最后將其用于優化認知無線電頻譜分配問題，仿真結果表明：改進后的算法一定程度上優化了原始灰狼算法的缺陷，在解決認知無線電頻譜分配問題時，可獲得更高的系統效益和更高的認知用戶接入公平性，達到頻譜分配的最終目的。