CRN中基于遺傳算法的信道分配方案研究

衛小偉

CRN中基于遺傳算法的信道分配方案研究

衛小偉

在感知無線電網絡中，為了緩解終止頻譜使用和切換造成的影響，最低干擾穩健型拓撲結構的構建問題（MIRTC）研究具有重要意義。將該問題表述為整數規劃問題，并提出一種基于遺傳算法的信道分配方案（GACA）來構建可將干擾降至最低的穩健型CR網絡拓撲結構。其方法中，任意一個信道受到干擾，每一對數據源—目的地間仍可保持連接。此外，還提出了一種高效的Bisearch算法以進一步降低干擾。仿真結果表明，該算法可降低網絡干擾，并有效地提升了網絡吞吐量。

感知無線電網絡；最低干擾穩健型拓撲；整數規劃；遺傳算法；信道分配；吞吐量

0 引言

無線應用的發展大大增加了對無線電頻譜的需求。然而多種研究及美國聯邦通信委員會指出[1]，當前的頻譜應用效率很低。感知無線電技術[2]被認為是增加頻譜利用率的潛在方法。在感知無線電網絡（Cognitive Radio Networks, CRN）中，如果頻譜未被PU用戶使用，每個未被授權用戶可感知并訪問頻譜。當PU請求訪問頻譜時，以機會方式使用相同頻譜的SU用戶需要切換到其他未被占用的頻譜上，以保護PU用戶的數據傳輸，并繼續傳輸自己的數據。然而，在頻譜交接時，SU網絡的吞吐量嚴重降低。

文獻[3]提出一種主動頻譜訪問方法，根據信道的使用歷史來預測頻譜的可用性。為了實現頻譜的快速切換，IEEE 802.22標準引入了備份信道概念[4]。Kim等人[5]提出一種備份信道列表管理方法使備份信道的機會最大。Feng等人[6]提出集中式和分布式貪婪策略使多跳CR網絡的頻譜切換延時最小。這些研究均假設PU的行為是可預測的，因此SU可對頻譜切換進行協調。然而在實踐中，PU的活動具有隨機性且不可預測；此外，由于CR網絡的動態性，備份信道的開銷較大。

文獻[7]首次提出了多跳CRN中的穩健型拓撲結構概念，穩健型拓撲結構構建方法并不假設PU用戶的活動可預測，而是為網絡中的每條鏈路分配多個信道，于是即使某條信道被 PU突然占用，每對數據源-目的地仍可保持連接，也就是說，網絡不會因PU請求某個信道而被分割。因此，數據報文在頻譜切換期間仍可沿著另一條路徑進行傳輸，緩解了潛在的報文丟棄或報文延時問題。該文獻分別研究了集中式和分布式信道分配方法，以提高網絡的穩健性，實現網絡干擾最小化。然而，這些算法不足以使網絡干擾最小化；于是，即使實現了網絡穩健性，網絡吞吐量可能較低。此外，文獻[9-11]中傳統的信道分配方法也沒有考慮網絡穩健性，因此不適用于多跳CRN的穩健型拓撲構建。

為此，本文定義了最低干擾穩健型拓撲構建問題（MIRTC），并將其表述為一種整數線性規劃問題，即使所有PU用戶出現，也可實現最大干擾最小化。鑒于MIRTC問題中二元決策變量的特點，我們提出一種基于通用算法的信道分配策略（GACA），通過將每個染色體定義為一串二元基因來表示可能解，進而求解MIRTC問題。此外，我們還提出一種高效的Bisearch算法以進一步降低干擾。仿真結果表明，本文的GACA算法和Bisearch算法在構建多跳CRN的穩健型拓撲結構時，可有效降低網絡干擾，當網絡中的可用信道數量較少時效果更為明顯。

1 系統模型和問題定義

假設多跳CRN包括多個SU用戶。當授權頻譜未被PU用戶占用時，SU可按一定機會訪問授權頻譜。我們用無向圖G=（N, L）表示機會型CRN，其中N表示SU用戶集合，L表示無向無線鏈路集合。對任意兩個SU用戶來說，如果互相位于對方傳輸范圍內，則它們之間存在一條無向無線鏈路。頻譜資源分為多個信道。每個SU用戶在轉發數據時可以切換信道和訪問可用信道。

在實際的CRN中，PU的干擾請求無法事先知曉。PU請求的到達時間變化多端，隨機占用信道，在網絡中的逗留時間不定。我們用一組狀態S來描述PU用戶的行為，其中狀態S表示信道S被PU用戶占用，也就是說，所有SU用戶均不得訪問信道S。狀態O表示沒有PU用戶發出請求的狀態。通過將各條信道的占用情況看成是不同的狀態，PU請求的動態情景被成功轉化為一種離線問題。

本文的目的是實現信道的離線分配，以便滿足穩健性約束，使各種狀態下的干擾最小。以802.11干擾模型[12]為基礎，我們將MIRTC問題看成是一種線性規劃問題。為了便于描述，下文中用到的相關符號的含義如表1所示：

表1 相關符號及其涵義

問題（MIRTC）如公式（1）：

條件如公式（2）～（7）：

MIRTC問題的目的函數是使網絡中干擾鏈路的最大數量最小化。約束公式（2）為每個狀態s下每個會話w構建一條路由路徑（即：滿足穩健性約束），其中wsrc和wdest分別表示會話w的數據源和目的地。約束公式（3）通過變量來尋找每條鏈路上開啟了哪些信道；如果，則。約束公式（4）表示802.11干擾模型，在該模型中，如果信道h由鏈路（i, j）使用，則在節點i和j的干擾范圍內最多有Ω個鏈路可使用相同的信道h。約束公式（5）要求狀態為s時網絡中的信道s應該關閉，以保護PU的出現。約束公式（6-7）要求變量和為二元變量。

2 本文算法

遺傳算法(GA)是求解復雜整數線性規劃算法的著名搜索方法之一[13]。本文基于遺傳算法的信道分配算法（GACA）包含5個階段：染色體，適應，交叉，變異和幸存者選擇。開始時，由一組個體（或染色休）生成一個群體，每一個個體表示目標問題的一個候選解。個體的獨特特征構成一個染色體，且染色體包含一組基因。生成染色體后，適應度函數確定其優越性。對最小化問題，適應度較小的個體被認為是優秀個體。然后，通過交叉、變異和幸存者選擇操作來進化種群。迭代過程一直持續，直到滿足終止準則。一般來說，終止準則是達到最大迭代次數，或連續代的適應度函數值之差達到閾值。GACA算法的偽代碼如圖1所示：

圖1 GACA算法的偽代碼

下面具體闡述信道分配算法中的遺傳操作。

（a）染色體：對MIRTC問題，設計染色體來表示網絡中所有鏈路的所有可用信道。一個基因對應于一條鏈路的一個信道，基因值是個二進制符號。如果基因值為1，則鏈路的信道處于活躍狀態，否則基因值為0，如公式（8）：

圖2 染色體示例

（b）適應度函數：適應度函數的目的是區分優質染色體和劣質染色體，以便種群向預期目標進化。GACA算法的目的是確定每條鏈路每個信道是開啟還是關閉，以便滿足連接性約束和目標函數值約束。因此，本文將染色體的適應度函數定義為所有狀態下未連接對的數量和懲罰因子之和。懲罰因子定義為公式（9）：

其中Ω表示染色體干擾鏈路的最大數量，Ωtar表示干擾鏈路的目標最大數量（即：被允許的干擾鏈路最大數量）。由 Bisearch算法來更新Ωtar。我們將在稍后討論 Bisearch算法。染色體x的適應度函數定義為公式（10）：

（c）交叉：從種群中隨機選擇兩個染色體作為母體，并利用這兩個染色體通過交叉操作來生成子體。對這兩個染色體中每條染色體的每個基因，本文隨機生成區間[0,1]中的一個數值，且定義交叉概率為pc=0.9。如果生成的基因數值小于pc，則該基因在選擇的兩個染色體間進行交換；否則，不進行基因交換。這一操作的示意圖如圖3所示：

圖3 示意圖

其中第2、4和5個基因（灰色框體）被選擇進行交叉操作。

（d）變異：變異操作可用于增加進化的多樣性。對每個子體，我們設置變異概率為pm=0.1以確定基因是否需要改變其二進制符號。類似地，為每個基因隨機生成一個數值。如果生成的基因數值小于pm，則通過XOR操作來更改該基因的二進制符。否則，我們維持其二進制符不變，如圖 4所示：

圖4 Bisearch算法的偽代碼

（e）幸存者選擇：重復第（c-d）步，直到子體數量等于種群規模。然后，我們不斷地從母體和子體中取出最優染色體，將其放入新的種群，直到新的種群規模等于預先定義的種群規模。

第（a）-（e）步列于圖1中，其中Xk表示種群，xk表示第k代的染色體。使用Fitness（x）來計算染色體x的適應度。第6行生成初始種群，第10-16行生成新的種群。第12和第 13行分別進行交叉和變異操作。當種群數k到達MaxGeneration時，GACA啟發式算法終止。當算法終止時，返回最優染色體x*。

通過GACA算法可以獲得最優信道分配器（即染色體x*）。我們進一步提出Bisearch算法以獲得MIRTC問題的解。如果x*的適應度為 0（表示采取信道分配方案x*時，每一個數據源-目的地對在各種狀態下均保持連接，且可實現目標最大干擾Ωtar），則我們將目標最大干擾減半，即。新的Ωtar值輸入到GACA算法中，以搜索新的最優染色體x*。如果x*的適應度不為0，則通過計算Ωtar和Ω*之和的一半來更新Ωtar。該Bisearch算法見圖2。如果Φ次之后Ωtar無法提升，則該算法終止。通過Bisearch算法可獲得MIRTC問題的解。下節將運行本文Bisearch算法，并針對一種小型網絡求解MIRTC問題，以評估它們的性能。

3 示例分析

本文運行LINGO優化軟件[14]來獲得MIRTC問題的最優解，并在小型網絡條件下比較最優解與Bisearch算法解的性能。

小型網絡包括5個CR節點，如圖5所示：

圖5 MIRTC問題的最優解和Bisearch算法解比較

如圖 5（a）所示，其中實線表示傳輸鏈路。干擾范圍設為傳輸范圍的2倍（即兩跳范圍）。每個節點有4個可用信道。MIRTC問題的最優解和Bisearch算法的解見圖5(b-c)，其中每條鏈路標識為活躍信道。

從圖5（b）的最優解可以看出，無論哪條信道被PU用戶占用，各個數據源-目的地對均能保持連接（即：滿足穩健性約束），且干擾鏈路最大數量為3。圖5(b-1)和5(b-2)分別給出了PU占用信道4和3時的情形（即：信道4和3從拓撲結構中刪除）。圖5（c）)給出了Bisearch算法的運行結果，其中 Bisearch 算法的輸入包括且。在信道被占用的各種狀態下，每個數據源-目的地對仍能保持連接（即：滿足穩健性約束）。干擾鏈路最大數量為3，與MIRTC問題的最優解相同。

4 性能評估

4.1 仿真配置

30個靜態CR節點隨機部署于500×500m2CRN上。每個CR用戶的傳輸和干擾范圍分別設置為150m和300m。每個CR節點可訪問H個未被占用的授權信道。每個CR節點安裝了4個無線電裝置以訪問這些未被占用的授權信道。我們在仿真時使用兩種性能評估指標：網絡干擾度和網絡吞吐量。評估3種方法的性能，即：RR（帶有穩健性約束的隨機信道分配）、CRTCA（集中式穩健型拓撲控制算法）[7]、Bisearch（Φ=1）， Bisearch（Φ=3）， Bisearch（Φ=5），?其中Φ表示Bisearch算法的終止準則。GACA算法中（即種群大小）和Max Generaion分別設置為100, 1000和10。所有仿真結果取10次仿真中的最優值。

4.2 網絡干擾度

網絡干擾度定義為干擾鏈路的最大數量（即：目標值Ω）。不同方案的網絡干擾度比較結果如圖6所示：

圖6 網絡干擾度與H間的關系

從圖中可以看到，當H增加時，所有算法的網絡干擾度均會下降。當每個節點的可用信道數量（即H）增加時，每條鏈路有更多機會分配給不同的信道，以避免干擾。當Φ增加時，本文Bisearch算法的網絡干擾度將會下降。RR算法的網絡干擾度最大。與CRTCA相比，Bisearch算法可將網絡干擾度有效降低14%-40%。具體來說，因為CRTCA算法的目標是構建一種穩健型拓撲但不考慮干擾程度最小化，所以當H大于6后，網絡干擾度無法進一步下降。

4.3 網絡吞吐量

生成的每個SU用戶對的數據速率要求設置為2Mb/s。每個SU用戶對的數據源-目的地對隨機選擇。每個SU對的流量采取最短路徑路由。采用香農信道容量計算信道數據率如公式（11）～（12）：

圖7 網絡吞吐量的比較情況

可以看到，當可用信道數量（H）、帶寬（B）或對數增加時，每種算法的吞吐量均會上升。RR算法的網絡吞吐量最低。本文Bisearch算法采用遺傳搜索最小干擾度信道分配方案。因此，Bisearch算法的網絡吞吐量最高。與CRTCA相比，當增加H,B和對數時，Bisearch算法的網絡吞吐量分別上升25%、30%和40%左右。

5 總結

本文將最小干擾度穩健型感知無線電網絡的構建問題看成一種整數線性規劃問題，并提出基于遺傳算法的信道分配策略(GACA)和Bisearch算法來獲得該問題的最優解。在小規模網絡條件下，本文Bisearch算法獲得了最優解。仿真研究表明，本文算法可有效地將網絡干擾度下降14%-40%，將網絡吞吐量提升 25%-40%。我們下一步工作的重點是基于壓縮感知理論，研究CRN中的動態頻譜檢測方案。

[1] 許瑞琛, 蔣挺. 基于 POMDP 的認知無線電自適應頻譜感知算法[J]. 通信學報, 2013, 34(6): 49-56.

[2] 劉會衡, 鄧小鴻, 陳偉. 一種基于特征值的多天線認知無線電盲感知算法[J]. 計算機應用研究, 2015, 32(1): 191-193.

[3] Yang L, Cao L, Zheng H. Proactive channel access in dynamic spectrum networks [J]. Physical Communication, 2012, 1(2): 103-111.

[4] Ko G, Franklin A A, You S J, et al. Channel management in IEEE 802.22 WRAN systems [J]. Communications Magazine, IEEE, 2010, 48(9): 88-94.

[5] Kim H, Shin K G. Fast discovery of spectrum opportunities in cognitive radio networks[C]. New Frontiers in Dynamic Spectrum Access Networks, 2008: 1-12.

[6] Feng W, Cao J, Zhang C, et al. Joint optimization of spectrum handoff scheduling and routing in multi-hop multi-radio cognitive networks[C]. Distributed Computing Systems, 2009. ICDCS'09. 29th IEEE International Conference on. IEEE, 2009: 85-92.

[7] Zhao J, Cao G. Robust topology control in multi-hop cognitive radio networks[C].INFOCOM, 2012 Proceedings IEEE. 2012: 2032-2040.

[8] Liu Y, Cai L X, Shen X. Spectrum-aware opportunistic routing in multi-hop cognitive radio networks [J]. IEEE Journal on Selected Areas in Communications, 2012, 30(10): 1958-1968.

[9] Huang X, Lu D, Li P, et al. Coolest path: spectrum mobility aware routing metrics in cognitive ad hoc networks[C]. Distributed Computing Systems (ICDCS), 2011 31st International Conference, 2011: 182-191.

[10] Cacciapuoti A S, Caleffi M, Paura L. Reactive routing for mobile cognitive radio ad hoc networks [J]. Ad Hoc Networks, 2014, 10(5): 803-815.

[11] Kamruzzaman S M, Kim E, Jeong D G. Spectrum and energy aware routing protocol for cognitive radio ad hoc networks[C]. Communications (ICC), 2011 IEEE International Conference, 2011: 1-5.

[12] Perahia E, Stacey R. Next Generation Wireless LANs: 802.11 n and 802.11 ac [M]. Cambridge University Press, 2013.

[13] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. (Evolutionary Computation), IEEE Transactions on, 2012, 6(2): 182-197.

[14] Farahani R Z, Elahipanah M. A genetic algorithm to optimize the total cost and service level for just-in-time distribution in a supply chain [J]. International Journal of Production Economics, 2008, 111(2): 229-243.

Research on Channel Assignment Scheme Based on Genetic Algorithm in Cognitive Radio Networks

Wei Xiaowei
(Department of Information Engineering, ShanXi College of Communication Technology, Xi’an 710018, China)

In cognitive radio networks, for mitigating the impact of spectrum usage termination and switching, the study of the Minimum interference robust topology construction (MIRTC) has important significance. In this paper, it formulates the problem as an integer programming problem and proposes a genetic-algorithm-based channel assignment (GACA) scheme to construct a robust CR topology in minimizing interference. The proposed formulation maintains the connectivity of each source-destination pair under the interruption of any single channel. In addition, an efficient Bisearch algorithm is proposed to further reduce the interference. Simulation results demonstrate that the proposed scheme can reduce network interference and enhance network throughput efficiently.

Cognitive Radio Networks; Minimum Interference Robust Topology; Integer Programming; Genetic Algorithm; Chan nel Assignment; Throughput Amount

TP393

A

1007-757X(2016)09-0046-05

2015.06.30）

衛小偉（1975-），男，西安人，西安交通職業技術學院，信息工程系，博士，副教授。研究方向：無線傳感網、移動計算，西安 710018