基于改進麻雀搜索算法的認知無線電頻譜分配

張金飛，岳文靜，陳 志

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003；2.南京郵電大學 計算機學院，江蘇 南京 210023)

0 引 言

近年來，隨著第五代移動通信技術(5G)的應用越來越廣泛，無線電通信技術也被應用到各種新型無線設備中，隨之也帶來了一系列的問題，如無線通信業務量急劇增加、無線電頻譜資源嚴重缺乏等。頻譜資源作為國家具有戰略地位的資源，深入影響著國民經濟的發展，同時又不可再生。所以合理利用頻譜資源，提高頻譜利用率成為眾多學者和研究人員關注的話題。由于認知無線電(Cognitive Radio，CR)技術可動態探測無線環境，能夠實現頻譜資源的共享，因此，該技術受到了廣泛的關注。認知無線電可以通過動態管理頻譜資源從而提高頻譜利用率，無線通信的質量也得到一定程度的提高，是目前解決頻譜資源短缺問題的有效方法之一。

隨著技術不斷進步，研究學者對認知無線電頻譜分配的方案取得了一系列嶄新的成果。通常將群智能搜索算法與認知無線電中的頻譜分配問題相結合以解決問題。例如經典遺傳算法、蟻群算法、二進制粒子群算法以及人工蜂群算法等。文獻[1]通過在蟻群算法中信息素分配時加入一個時間因子，并對信息素排序，進而將信道分配給認知用戶。文獻[2]提出了一種改進的粒子群算法來優化頻譜資源分配，該算法一定程度上提高了網絡效益，但當信道數較大時，算法的效率較低。文獻[3]給出了一種多策略更新信息素的蟻群算法，使用混沌初始化和混沌擾動對信息素進行依次更新，再對干擾約束條件進行了調整，進而求得最優解。該算法在一定程度上提高了平均網絡效益，并未將頻譜分配的公平問題考慮在內。文獻[4]通過引入一個自適應概率閾值和自適應權重，提出了一種改進鯨魚算法的方案來優化頻譜分配，雖然提高了算法的收斂速度，但是當認知用戶之間頻譜使用的競爭增大時，網絡的公平性也會進一步降低。文獻[5]在基本狼群算法的基礎上結合了量子進化算法與精英選擇算子，精英選擇算子的引入在一定程度上提高了算法的求解精度，但是該算法易陷入局部最優，很容易丟掉全局最優解。文獻[6]提出了一種新型的智能搜索算法——麻雀搜索算法，模擬自然界麻雀捕食時的團隊協作關系，即捕食與反捕食行為。采用該群智能優化算法來獲得全局優化問題中的最優解。文獻[7]則將克隆操作引入到海鷗算法中，擴充海鷗個體的多樣性，進而通過人工免疫算子計算出適應度最佳個體。文獻[8]介紹了頻譜分配的三種模型，主要對圖論著色模型展開論證，重在理論研究。文獻[9-11]對麻雀搜索算法步長等參數做了一定的改進，但仍可優化。文獻[12]則對頻譜實現動態化分配管理，結果缺乏對比。文獻[13-17]主要對網絡的主要參數進行修改，缺乏具體的現實意義。因此，該文就認知無線電網絡中常見的頻譜分配優化問題，提出了一種改進的麻雀搜索算法。首先，種群初始化時采用透鏡成像反向學習策略，在最優麻雀位置基礎上繼續尋優，便于最佳位置的搜索；然后，采用變步長設計，使用衰減因子來提高SSA算法的收斂速度；最后，對偵查預警的麻雀位置引入Levy策略進行更新，提高算法總體尋優的能力，在極大程度上節約了頻譜分配所需時間，提高了信道使用效率。

1 頻譜分配模型

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

在認知無線電網絡中，可將用戶分為主用戶和認知用戶。當認知用戶只有在滿足干擾約束條件時才可以使用不被占用的信道資源，同時不能影響主用戶與外界正常的數據傳輸，這樣認知用戶和主用戶共同使用固有的頻譜資源，就可以通過頻譜資源共享技術提高頻譜資源利用率。通常頻譜共享的方式有以下兩種：一是利用控制信道得到所需要的信號資源;二是通過認知無線網絡中的基站取得頻率資源占用狀況。該文將認知無線電網絡頻譜分配問題建模為圖論著色問題。圖論著色中頻譜分配問題可用信道矩陣L、頻譜效益矩陣B、干擾約束矩陣C以及無干擾頻譜分配矩陣A等參數來描述。對其相關參數的說明如下：

(1)可用信道矩陣L：

L={ln,m|ln,m∈{0,1}}N×M，表示在該段時間中信道不被占用，系統中可以分配給認知用戶使用的信道。當ln,m=1時，代表信道m有資源分配給認知用戶n;當ln,m=0時，代表信道m中沒有空閑資源供認知用戶n使用。

(2)頻譜效益矩陣B：

B={bn,m}N×M，是指信道m分配給用戶n使用獲得的效益。B為一個N×M的實數矩陣，bn,m表示認知用戶n使用信道m時所能獲得的最大效益。顯然當ln,m=0時，則有bn,m=0。

(3)干擾約束矩陣C：

C={cn,k,m|cn,k,m∈{0,1}}N×K×M，表示當認知用戶n和k在該時刻可以共同使用信道m通信，干擾矩陣C用來判斷認知用戶之間是否造成了干擾。當cn,m,k=1時，表示次用戶n和次用戶m會造成相互干擾。反之，當cn,m,k=0，則表示不會造成相互干擾。此時，用戶n和用戶k可共享信道m。

(4)無干擾頻譜分配矩陣A：

A={an,m|an,m∈{0,1}}N×M，表示主用戶不被影響且次用戶之間互不干擾時的信道分配。an,m=1表示將信道m分配給次用戶n，反之，信道m不能分配給用戶n使用。該矩陣要滿足L和C所規定的約束條件。

(5)用戶效益R：

R={βn}N×1，其中βn表示在無干擾分配矩陣A下，次用戶n在所有信道上獲得的收益。公式為：

(1)

則系統總收益UR表示為：

(2)

(6)認知用戶接入公平度Ufair：

為認知用戶的比例公平度的最大值，主要是確保頻譜分配過程每個認知用戶獲取近似相等概率的效益。公式為：

(3)

1.2 認知無線電網絡分配頻譜模型

認知無線電網絡中，主用戶的出現是不確定的，且其對信道的使用是隨機的，認知用戶檢測到的信號是不斷發生變化的。當認知用戶的信道分配發生沖突時，信道分配問題在約束條件下可轉為圖論著色問題。頻譜分配中的圖論著色模型是根據主用戶與認知用戶之間，以及認知用戶之間對某個信道的使用，并將這種關系抽象成網絡拓撲圖G(V,E,L)。V是圖中所有頂點的集合，代表頻譜分配模型中的所有認知用戶；E是圖中所有頂點之間邊的集合，代表頻譜分配模型中認知用戶之間存在干擾；L為信道可用狀態矩陣，表示每個頂點可以選擇的顏色集合。

圖1為主用戶和認知用戶組成的網絡拓撲，信道A-D分別代表四個主用戶授權的信道，S1-S5為五個認知用戶，圖中主用戶所覆蓋的通信范圍可由圖中的虛線圓表示，直線則代表認知用戶之間存在一定程度的干擾。當認知用戶處在主用戶的通信覆蓋范圍之內，就會對該主用戶的通信造成干擾，所以認知用戶便不能利用該頻段進行通信。圖中每個認知用戶括號內的頻譜則是該用戶的可用頻譜集。例如S1可以使用的信道為B、C、D。

圖1 認知無線限電網絡拓撲

2 麻雀搜索算法

麻雀是雜食性群居鳥類，相比于其他鳥類，更具有團體協作意識。麻雀搜索算法是受自然界中麻雀的覓食行為的啟發，將麻雀覓食過程構造成算法最優值的求解過程來進行搜索。SSA將麻雀分為三種類型：分別是發現者、加入者和偵察者，每種類型承擔不同的功能。發現者擔負著為種群尋找生存食物的職責，擁有最大的適應度值，加入者和偵察者會緊跟著發現者的位置變化來獲取食物；加入者為種群主體，它們一直跟隨發現者以得到充足的食物，同時不斷與其他同類搶奪食物以維持生存；偵察者負責種群的安全，捕食過程中當意識到有危險靠近時會立即發出逃離信號，整體麻雀迅速向安全區域移動更新位置，做出反捕食行為。

(1)麻雀發現者的位置移動公式如下：

(4)

式中，t代表SSA搜索時每次進行迭代的次數，T代表最大迭代次數，α為[0,1]的隨機數。xi,j(t)表示第i只麻雀在第j維的位置，Q是一個隨機常數且取值服從正態分布，L表示一個1×d且元素值都為1的矩陣，R2∈[0,1]表示預警值，ST∈[0.5,1]為設定的安全值。當R2

(2)麻雀加入者的位置移動公式如下：

xi,j(t+1)=

(5)

式中，xworst(t)表示第t次迭代中麻雀種群的全局最差位置，xbest(t)表示第t次迭代中的全局最優位置即最容易獲取到食物的麻雀位置。A表示一個1×d且元素隨機賦值為1或者-1的矩陣，且A+=AT(AAT)-1。當i>n/2時，表示適應度值較差的第i只麻雀加入者無法捕獲到食物，此時需要飛往其他的地方來繼續搜索食物。

(3)麻雀偵察者的位置移動位置公式如下：

(6)

式中，xbest(t)表示第t次迭代中麻雀的全局最佳位置，β為服從均值為0、方差為1的正態分布的隨機數，K∈[-1,1]代表麻雀的前進方向，可以控制步長參數，fi表示個體適應度值，fg為最大適應度值，fw為最小適應度值，e是為了防止分母為零的情況出現而設定的一個最小常數。當fi>fg時，表示麻雀處于種群的最外側,易失去食物或受到捕食者攻擊，當fi=fg時，表示處于種群內部的麻雀察覺到周邊有危險存在，因此需要提醒種群逃離以免被捕食。

3 改進的麻雀搜索算法

基本麻雀算法在尋優過程中較易陷入局部最優解，為增強算法全局搜索能力，通過對影響算法搜索的主要參數進行調整，可改善尋優效果。

3.1 透鏡成像反向學習策略

反向學習是一種為解決群智能算法在搜索過程中因陷入局部最優的情況而提出的優化機制，通過對當前搜索范圍中最佳位置的反向點進行探索，擴大了搜索范圍，更易找出最優解。將群智能搜索算法與反向學習策略在一定情況下進行結合可以有效提高方法的尋優性能。為解決SSA算法在求解過程中易陷入局部最優問題，該文引入凸透鏡成像原理來幫助SSA算法跳出局部最優問題，即在當前最優麻雀位置上通過透鏡成像找到最優點的反向點，然后在反向點的基礎上繼續向其他區域進行尋優求解。原理示意圖如圖2所示。

圖2 透鏡成像反向學習示意圖

在一維有限空間ab中，存在個體p的高度為H，該點映射在坐標軸上為最佳位置x。凸透鏡的中心點為o，f是凸透鏡的焦距。通過凸透鏡成像原理可以得到p的對應個體p*，高度為h，即為映射在坐標軸上的最優位置x*。根據凸透鏡成像原理可以得出：

(7)

設H/h=n,可計算得到x*的表達式為：

(8)

通過調整n取不同的值，可以得到不同位置的反向點，即產生新麻雀個體的最佳位置。當n=1時，即為一般的反向學習策略。可以看出，通常所指的反向學習是透鏡成像反向學習的一個特例，一般反向學習的反向點是固定的，而透鏡成像反向學習通過調整n的值，得到的是一個動態變化的反向點，從一定程度上提高了求解精度。該文設置n=10 000。因為最優個體較一般個體擁有更佳的搜索位置，所以通過雙透鏡成像反向學習機制，可以避免SSA算法陷入局部極值問題，進而使算法的求解更加精確。

3.2 步長調整

在標準SSA算法中，加入者為麻雀種群中數量最多的個體，通過對加入者中麻雀個體的步長進行調整，可以改善整體的尋優性能。式(2)中的步長參數Q對平衡局部搜索和全局尋優能力具有重要作用，但Q每次為隨機取值，在每次對最優解空間進行探索時，很容易陷入局部最優的狀況。為了平衡局部精度和全局最優之間的關系，該文采用在進行初始查找時使用較大的步長，后面隨著迭代次數的不斷增加，步長比例性減小的方式。改進后的公式如下：

Q(t)=k·Q(t-1)

(9)

式中，t為當前迭代次數，k為步長衰減系數，通常k∈[0.7,1]。

3.3 Levy飛行策略

生物種群在自然界中進行覓食時，其捕食方式大多可看作是一種Levy飛行策略。Levy飛行是一種非高斯隨機步態，它的特點是在小步長更替過程中會隨機出現大步長。由于步長具有不確定性的特點，Levy飛行策略的步長比布朗運動的步長增長的更加快速且更具有隨機性。當覓食者在未知環境中較大范圍地搜索食物時，Levy飛行策略具有比布朗運動更加良好的搜索效果。傳統SSA在最優值求解過程中，容易陷入到局部極值的困境。由于Levy飛行進行的是高頻短距離的探索和低頻長距離的交替探索，在尋找最優解過程中，引入Levy飛行可以在局部搜索和全局搜索時，分別采用不同長度的步長展開搜索。這樣當搜索接近最優值時，選用合理的步長進行搜索，可以有效提高算法的收斂精度，解決標準SSA陷入局部最優的問題。該文在麻雀偵察者更新公式中加入Levy飛行策略，提高全局搜索能力。改進后的公式如下：

xi,j(t+1)=

(10)

其中，d為向量維度，Levy計算公式為：

(11)

(12)

其中，Γ(x)=(x-1)!，Q為服從正態分布的隨機數，r3,r4∈[0,1]，ξ是一個可以調節的常數，通常可取值為1.5。

3.4 算法步驟

ISSA運行偽代碼如下：

步驟1：初始化相關參數，如麻雀數量popsize、最大迭代次數iterMax、麻雀中發現者數量PD、偵察者數量SD、安全值ST、預警值R2等。

步驟2：分別計算種群中各個麻雀的適應度值并排序，找出當前最優值和最差值，及最優值和最差值對應的麻雀位置。

步驟3：參照式(4)和式(8)，使用透鏡成像反向學習策略對PD中的最優和最差位置進行更新。

步驟4：參照式(5)和式(9)，動態調整步長因子，對加入者中麻雀位置進行更新。

步驟5：參照式(6)、式(10)和式(11)，在每次迭代中使用Levy飛行策略對偵察者SD中麻雀位置進行更新。

步驟6：判斷是否達到最大迭代次數Max_iter，是則跳出循環；否則依次重復步驟3～步驟5。

步驟7：輸出最優麻雀位置和最佳適應度值。

4 仿真與分析

為驗證提出的ISSA算法在認知無線電頻譜分配中的性能，考慮從系統總效益、認知用戶接入公平性、收斂速度等方面出發，通過與傳統遺傳算法(GA)、粒子群算法(PSO)、海鷗算法(SOA)及初始麻雀搜索算法(SSA)進行對比，分析其性能優劣。

4.1 參數設置

實驗采用Matlab2019b編寫算法和仿真實現，條件假設無線網絡環境中只存在用戶間的干擾，不考慮環境中其他因素的影響。實驗仿真設定認知無線電頻譜分配網絡區域為1 000×1 000，將算法的各項參數分別設置為：認知用戶數N=20，可用信道數M=10，默認主用戶數K=10，種群規模為20，迭代次數最大取為300次。

4.2 結果分析

實驗主要選擇三個性能指標進行分析，其中網絡總效益指的是所有認知用戶在指定信道下獲得的網絡效益(帶寬)；認知用戶接入公平性是確保頻譜分配過程每個認知用戶獲取效益的機會均等；收斂速度可體現算法對系統變化的敏感度。

圖3為選取網絡總效益為目標函數和迭代次數進行比較，繪制了五種算法進行30次尋優操作的平均曲線，且以下圖均為30次取平均的結果。此時信道數M和認知用戶數N為固定值。由圖3可知，隨著迭代次數的增大，網絡總效益不斷增加，并逐漸穩定于一個常數。且改進后的麻雀搜索算法具有最大的網絡總效益，收斂速度也較其他算法更快。

圖3 迭代次數與網絡總效益關系曲線

圖4為網絡效益與可用信道數的關系曲線，此時認知用戶數固定，N=20。可以看到，網絡效益隨著可用信道數的增加而提高，這是因為在相同條件下，認知用戶能夠使用的信道數越多，該用戶獲得的收益也越大，可以看出ISSA算法的網絡效益也超過了其他算法。

圖4 可用信道數與網絡效益關系曲線

圖5 認知用戶數與網絡效益關系曲線

圖5是在認知用戶數從10增長到30的情況下，保持可用信道數和主用戶數不變，運行30次算法取均值網絡效益的仿真結果。由圖5可知，隨著認知用戶數的不斷增加，網絡效益逐漸減小，主要原因就是當可用信道數為一個不變的值時，認知用戶數逐漸增加，信道資源開始處于緊張狀態，進而分配不足導致獲取的效益減小。

圖6為在可用信道數和認知用戶數固定的情況下，其他參數都按照條件默認值設置，獨立運行20次的試驗次數與認知用戶接入公平性的曲線。由圖可知，ISSA具有最大的網絡公平性，優于其他算法，也反映了ISSA算法的有效性。

圖6 試驗次數認知用戶數接入公平性關系曲線

5 結束語

為解決認知無線電中頻譜分配過程存在的優化問題，文中提出了一種改進的ISSA算法，并將其應用到認知無線電頻譜分配中。通過使用透鏡成像反向學習策略來增加麻雀種群的多樣性，同時引入飛行策略控制麻雀轉移步長，來提高算法在求解尋優問題過程中的收斂速度與精度。通過與原始麻雀搜索算法(SSA)、遺傳算法(GA)、粒子群算法(PSO)、海鷗算法(SOA)進行對比測試，表明改進算法后的網絡系統性能得到了明顯的改善，表現出更快的收斂速度，一定程度上提高了認知用戶的接入公平性。下一步將對認知無線電在干擾條件下的頻譜分配和頻譜的動態分配進行研究。