基于混沌進化的引力搜索頻譜調度算法

王亞利 于繼明

1(濟源職業技術學院 河南 濟源 454650)2(金陵科技學院 江蘇 南京 211169)

0 引 言

隨著無線通線技術的快速發展，涌現出越來越多針對不同應用場景的無線通信設備，例如應用于移動健康監測的可穿戴設備[1]、應用于共享經濟的共享單車，以及應用于智慧交通的車載網絡[2]等。但無線設備數量增長給不可再生的頻譜資源帶來了巨大的壓力，從而不可避免地會加劇數據丟包、時延、信道擁塞等狀況。另一方面，這些無線設備通常使用的是政府授權的商業頻譜，例如無線通信運營商的頻譜；或特別準許工業界、科學界和醫療界所使用的公共頻譜，例如Wi-Fi、藍牙等所使用的頻譜[3]。文獻[4]顯示，除上述兩類頻譜，其他授權頻譜的使用率非常之低，最低僅有15%。綜上，面對頻譜資源使用率冰火兩重天的狀況，認知無線電[5](Cognitive Radio，CR)技術應運而生。

CR技術的主要特點是可以幫助無線設備在不影響其他用戶的前提下使用授權頻譜進行通信，以提升無線通信質量，同時提升頻譜利用率[6]。配備CR技術的無線設備所組成的網絡稱為認知無線電網絡[7](Cognitive Radio Networks，CRNs)，其中包括若干個授權用戶(Authorized User, AU)，以及若干個非授權用戶，可以稱之為認知用戶(Cognitive User, CU)。在CRNs中，最關鍵的問題是如何將有限的授權頻譜資源以一種合適的方式分配給認知用戶CU，在不影響授權用戶AU正常使用的前提下，保證認知用戶CU之間使用頻譜的公平性，即在一個成熟的系統模型中設計一套完善的調度算法對授權頻譜資源進行管理。

目前已有許多學者提出了不同的頻譜調度系統模型。干擾溫度頻譜調度模型[8]的出發點是通過設定一個溫度門限值對認知用戶CU的傳輸功率進行控制，以確保其不會對授權用戶AU造成干擾，但該模型忽略了授權頻道復用的可能性。博弈論頻譜調度模型[9]不同于干擾溫度模型，其出發點是實現系統的最大效用，降低系統的使用成本，讓認知用戶CU之間進行博弈，確定最優的頻譜調度策略，但該模型卻忽略了用戶之間的公平性。圖論頻譜調度模型[10]的思想是將一個實際的問題轉化為一個數學模型，具備較強適用性，能夠根據問題的特點在數學模型中有效地體現，避免干擾溫度模型和博弈論模型中出現的問題。

基于圖論模型所設計的頻譜調度問題是一個NP-Hard問題，所以研究學者利用智能尋優算法進行求解。文獻[11]利用遺傳算法求解頻譜調度問題的最優方案，最然具有一定的全局搜索能力和較高的適應性，但是算法的性能卻依賴初值的選擇，且算法后期易陷入局部最優。文獻[12]利用蟻群算法優化頻譜調度方案，其具備較高的算法收斂精度和全局搜索能力，但收斂速度較慢。引力搜索算法[13](Gravitational Search Algorithm, GSA)相比于遺傳算法和蟻群算法是一種新興的群體智能尋優算法，其能夠解決較高維度的空間優化問題，且對初始值不敏感，種群能夠維持較高的多樣性。但引力搜索算法依然面臨一些問題，其收斂速度和收斂精度仍有提升的空間。

通過以上對頻譜調度系統模型和智能尋優算法兩方面的分析，本文在圖論模型的基礎上，以系統效用最大化為優化目標，提出一種基于混沌進化的引力搜索算法(Chaotic and Evolutional Gravitational Search Algorithm, CEGSA)以求解認知無線電網絡中的頻譜調度問題。在CEGSA中，基于所構建的系統模型，本文在算法的迭代階段引入差分進化[14]過程，以加快算法的搜索速度，提升CEGSA的收斂速度，并引入混沌擾動機制[15]，避免算法在后期陷入局部最優解，以提高CEGSA的算法精度。

1 系統模型及優化問題

1.1 CRN模型

相比于干擾溫度模型和博弈論模型，圖論模型可以表征用戶之間的關系，以及更直觀地展現網絡中的拓撲結構。具體地，本文基于圖論理論所構建的CRN模型可以展示出不同節點(即用戶)之間的干擾關系，并通過對節點之間的連接線進行著色，用以表示用戶之間的沖突。同時，節點的干擾半徑由用戶的干擾范圍所決定。而對于目標函數，CRN模型有較好的泛化能力，可以根據不同的優化需求設計目標參數。

綜上，基于圖論理論，首先構建了一個圖論模型G=(V,E)，其中:V代表圖的節點，在CRN模型中表示授權用戶AU和認知用戶CU；E代表圖的邊，在CRN模型中表示用戶之間的干擾關系，包括AU和CU之間，以及CU和CU之間的干擾關系。圖1所示為一個CRN模型圖，包含3個AU、4個CU，以及3個可用授權頻譜K∈{α,β,δ}，其中：r1表示AU的干擾半徑，r2表示CU的干擾半徑，如果干擾區域相互重疊，則表示它們在使用同一頻譜時會發生干擾。

圖1 CRN系統模型

1.2 矩陣模型

頻譜調度算法有三個設計原則，分別是：較高的算法執行效率，體現網絡中的約束，明確的優化目標。而1.1節所構建CRN模型并不能直接用數學方法進行求解，所以，本節將其拓撲結構以及用戶之間的干擾關系轉換為矩陣模型。

首先，本文設計拓撲矩陣T和效用矩陣E用以表示CRN網絡的拓撲結構和節點的權重，其可以將圖形化語言轉化為數學語言，方便使用計算機設計算法求解。然后，本文設計干擾矩陣I表示網絡的約束條件，用于確保所設計的算法在執行過程中滿足網絡中用戶的干擾關系。最后，本文設計位置矩陣P和共享矩陣S作為算法的輸入和輸出，其中輸出矩陣S則是本文的優化目標。具體地，定義認知用戶CU的個數為N，無線頻譜的個數為K，且 1≤n,m≤N，1≤k≤K，具體見表1。

表1 矩陣模型

(1)拓撲矩陣T：定義了網絡空間中用戶的拓撲結構tn,k=1。具體地，可以從拓撲矩陣T中確定認知用戶n是否可以使用信道K，即表示可用，否則反之。例如:從圖1中可得，用戶CU2與AU3的干擾范圍沒有交集，則t2,3=1。

(2)效用矩陣E：定義了用戶n使用頻譜K時的效用。該效用由當時的網絡環境參數所決定，例如信噪比、傳輸功率，具有較強的動態性。

(3)干擾矩陣I：定義了AU與CU以及CU與CU之間干擾關系的三維矩陣。當n≠m時，in,m,k=1表示CUn和CUm同時使用頻譜k時有干擾，否則反之；當n=m時，in,m,k=1表示CUn使用頻譜k會對授權用戶產生干擾，否則反之。例如：從圖1中可得，i1,3,α=0，i2,4,δ=1。

(4)共享矩陣S：定義了最終的頻譜調度方案，sn,k=1表示將頻譜k分配給CUn使用，否則反之。此外，矩陣S需要滿足干擾矩陣I的要求，即當in,m,k=1且n≠m時，必須滿足sn,k+sm,k≤1。

(5)位置矩陣P：為方便計算機處理，本文設計了一個編碼解碼過程，將拓撲矩陣T編碼為物體的位置向量P，通過GSA一系列的運算，并將最后得到的最優解P解碼為共享矩陣S。編碼解碼的核心是將拓撲矩陣中1元素的位置按照先行后列的順序按次取出，并組成一個行向量，最后再按照該規則還原至共享矩陣S，如圖2所示。定義位置矩陣P表示空間中所有物體的位置向量集合，其中：μ表示空間中物體的個數；ε表示物體位置的維度，其值等于拓撲矩陣T中1元素的個數。

圖2 位置矩陣P編碼解碼

1.3 優化問題

定義物體位置的適應度函數，用于評價物體位置的優劣：

(1)

本文的優化問題是最大化CRN的系統效用，即在滿足干擾矩陣I的約束條件下，將最終的頻譜分配方案矩陣S乘以系統的效用矩陣E。

s.t. ?1≤n,m≤N,1≤k≤K

(2)

2 算法設計

2.1 算法優化思想

引力搜索算法GSA[13]模擬了宇宙中任意兩個物體之間都存在相互作用力的特性，利用萬有引力公式，將優化問題轉化為宇宙中物體的位置，并由物體的質量和物體間的距離計算引力的值，最后根據引力值推演物體下一次運動的方向和距離。通過不斷的移動，物體會聚集到質量最大的物體附近，而物體的質量由評價函數確定，即質量最大的物體占據著最優的空間位置。這樣，GSA通過萬有引力定律將優化問題的評價函數以及解映射到了空間中物體的位置和質量。GSA相比于遺傳算法和蟻群算法具有天然的優勢，例如對初始值不敏感、具有較高的個體多樣性等，但GSA由于萬有引力定律的性質仍然面臨一些問題，例如后期容易陷入局部最優，且收斂速度仍有提高的空間。基于此，本文分別設計了差分進化優化(Differential Evolution Optimization,DEO)機制和混沌擾動優化(Chaos Disturbance Optimization,CDO)機制來解決上述兩個問題，并同時提高了GSA的收斂速度和收斂精度。

2.2 差分進化優化機制

2.1節介紹了GSA的核心思想，即物體基于萬有引力定律向所有質量比自己大的物體的合力方向運動。在這樣的機制下，受影響最大的是空間中質量最小的物體，反而質量最大的物體可能會紋絲不動，不進行任何搜索。所以算法的收斂速度取決于質量偏小的物體，因其運動更敏捷，搜索范圍更自由。

基于此，本文設計了差分進化(DEO)機制對GSA的搜索過程進行優化，主要從三方面做了算法適配和優化工作：(1)該機制在GSA每次迭代完進行，且僅針對質量最小的部分物體；(2)DEO機制中的變異操作，僅針對質量最大的部分物體；(3)設計了隨機變異位，以確保每次操作至少在一維會有改變。綜上，本文設計的差分進化公式為：

(3)

式中：t表示位置的迭代次數，且1≤t≤T；φ為區間(0,1)之間的隨機數；ρ為選擇概率；λ為縮放因子；εrd為位置p的任意一個維度，每次迭代隨機產生，且1≤εrd≤ε；μ1、μ2、μ3為三個隨機選擇物體，且滿足μ≠μ1≠μ2≠μ3。

假設物體μ經過GSA優化后的位置向量為P=(A，B,C, …)，εrd設為3，則DEO機制的交叉過程如圖3所示。

圖3 差分進化過程

基于式(3)，假設ε=1時，φ≤ρ，則將A2替換為A；假設ε=2時，φ>ρ，則將B1替換為B；由于εrd=3，所以強制將C2替換為C；之后的交叉位選擇也依據式(3)進行操作。

綜上，基于DEO機制優化后的GSA，可以增強大質量物體對小質量物體搜索路徑的引導，即通過調節選擇概率ρ，GSA就可以調整小質量物體的進化速度，在保留一部分原有物體的位置因素的情況下，基于大質量物體的引力方向，對其下一個時隙的運動位置進行調整。對部分大質量物體的變異操作則增強了物體種群的多樣性，避免空間中的物體迅速聚攏在部分大質量物體周圍，陷入局部最優。變異位εrd則可以在小質量物體向大質量物體聚攏的過程中，對其運行軌跡觸發小范圍的波動，使其在不影響小質量物體的整體運動趨勢下，增加發現其他最優區域的可能性，提升算法的尋優速度。

2.3 混沌擾動優化機制

GSA的另一個特性是，在算法迭代的后期，所有的物體都會向質量最大的物體靠近，這會導致算法易陷入局部最優。為了避免這種問題，幫助算法找到全局最優解，提升算法精度，本文設計了混沌擾動優化(CDO)機制。該機制利用了混沌映射產生的隨機點可以遍歷整個空間且不重復的特性，在GSA經過多次迭代，但最大物體質量不變的情況下，對空間中的所有物體進行擾動，打亂其所在的位置。本文所使用的混沌映射為Tent映射：

(4)

其混沌擾動的步驟如下：

1)將物體μ的位置Pμ映射到混沌擾動空間[0,1]：

(5)

(6)

2.4 算法流程

本文所提出的CEGSA流程如下：

1)初始化位置矩陣P。根據式(1)計算每個物體的適應度，記最大適應度為Rb，其位置向量記為Pb。

2)計算物體質量。根據上文建立的物體質量與適應度函數之間的聯系，定義物體μ在第t代的質量為Mμ(t)：

(7)

(8)

式中：Rb(t)和Rw(t)分別表示第t代所有物體中最大和最小的適應度；μ和υ表示不同的物體。

3)計算物體所受引力之和。首先計算物體υ對物體μ的引力，Dμ,υ為物體μ和υ之間的歐氏距離；G(t)為動態引力常數，隨迭代次數而減少；此外，G0是G(t)的初值，σ是無窮小量，ζ是引力系數。

(9)

Dμ,υ(t)=‖Pυ(t),Pμ(t)‖2

(10)

(11)

則物體μ所受的合力為：

(12)

4)計算物體加速度。由式(8)和式(12)，便可以得到物體μ在t代的加速度：

(13)

5)更新物體速度和位置。分別計算物體在t+1代的速度和位置，所有物體初始化速度為0。

Vμ(t+1)=Vμ(t)+aμ(t)

(14)

Pμ(t+1)=Pμ(t)+Vμ(t+1)

(15)

6)差分進化優化物體位置。由EDO機制對空間中的物體進行優化，優化的數量定為μEDO。

7)更新物體的最大適應度。由式(1)計算所有物體的適應度，并將第t代最大適應度Rb(t)與Rb進行比較，保留最大值，更新至Rb、Pb。

8)判斷是否進行混沌擾動。定義進行混沌擾動的閾值為TCDO，即當空間中最大的物體質量連續TCDO代都沒有改變，則由CDO機制對空間中的物質進行擾動。

9)判斷是否到達最大迭代次數，否則轉步驟2)。

3 實 驗

本文基于MATLAB平臺構建了CRN網絡模型，并在該平臺中設計基于混沌進化的引力搜索算法以求解認知無線電網絡中的頻譜調度問題。模型所產生的網絡的拓撲結構由文獻[17]得，仿真環境為20×20的方形區域，包括K個AU、μ個CU、K個授權頻譜。另外，授權用戶AU和認知用戶CU的干擾半徑分別定為r1=5，r2=3。

本文分別從收斂速度和收斂精度兩方面對CEGSA、GA[11]、GSA[13]進行了對比實驗。為了確保仿真結果具有可比性，三個算法的種群個數均設為20，迭代次數設為T=200。其他參數設置如下：GA的變異概率設置為0.2，交叉概率為0.7，GSA和CEGSA的G(t)初始值G0=100，引力系數ζ=20，CEGSA的其他參數μEDO=6，TCDO=3。

此外，收斂速度實驗為300次實驗的均值，收斂精度實驗為30次實驗的均值，且每次實驗都會生成新的網絡拓撲結構。

3.1 收斂速度實驗

如圖4所示，本文在K=5、μ=15的網絡環境下對CEGSA、GSA和GA進行實驗，比較其收斂速度。

圖4 收斂速度實驗

可以看出，CEGSA的收斂速度最快，在62代附近收斂；GSA次之，在85代附近收斂；GA最慢，在110代附近收斂。這是因為GSA在多維空間具備較高的搜索性能，且CEGSA利用差分進化機制對空間中質量較小的物體進行了優化，驗證了DEO機制的有效性。此外，表2總結了三個算法收斂時的系統效益，以及相對于GA的效用提升比例。可以看到CEGSA的系統效用要高于其他兩種算法，驗證了混沌擾動機制對系統效用的提升起到一定作用。

表2 算法收斂性能

3.2 收斂精度實驗

本文對三種算法的收斂精度進行對比實驗。圖5為頻譜個數K=7固定，認知用戶CU個數μ從3遞增至21時系統效用的變化。圖6為μ=15固定，頻譜個數K從3遞增至19時系統效用的變化。

圖5 收斂精度實驗1

圖6 收斂精度實驗2

從圖5可以看出，三種算法的系統效用隨CU數量的增加而增加，在認知用戶數μ>15后趨于緩和。這是由于頻譜個數固定，即使CU不斷增加，也無法滿足所有的CU都有頻譜資源可以用，所以系統效用趨于峰值。此外，也可以看到CEGSA的系統效用一直高于其他兩種算法，在此證明本文所提出的CDO機制對GSA的收斂精度具有一定提升。

從圖6可以看出，三種算法的系統效用隨頻譜個數的增加而增加，且CEGSA仍然高于其他兩種算法。此外，可以看到K>7之后，三種算法的差距越來越大，這是由于K≤7時，頻譜資源緊張，無法體現出各個算法的性能。同時，可以看到三個算法在K>15后系統效用R(t)上升放緩，這是由于CU個數是固定的，頻譜資源增加并不會提升系統的效益。

4 結 語

本文針對傳統頻譜調度算法所面臨的問題，從算法的收斂速度和收斂精度兩方面進行考慮，以最大化系統效用為目標，提出了基于混沌進化的引力搜索頻譜調度算法。設計了差分進化優化機制，對傳統引力搜索算法中物體移動軌跡進行指導，加快算法的尋優過程，并利用變異過程提升了種群的多樣性；設計了混沌擾動優化機制，當算法陷入局部最優時，利用混沌算法特性對空間中的物體進行擾動，以提高算法的精度。實驗結果表明，本文算法相比于傳統引力搜索算法和遺傳算法有更高的收斂速度和系統效用。