衛(wèi)小偉

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

衛(wèi)小偉

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

感知無線電網(wǎng)絡(luò)；最低干擾穩(wěn)健型拓撲；整數(shù)規(guī)劃；遺傳算法；信道分配；吞吐量

0 引言

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

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

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

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

1 系統(tǒng)模型和問題定義

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

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

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

表1 相關(guān)符號及其涵義

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

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

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

2 本文算法

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

圖1 GACA算法的偽代碼

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

（a）染色體：對MIRTC問題，設(shè)計染色體來表示網(wǎng)絡(luò)中所有鏈路的所有可用信道。一個基因?qū)?yīng)于一條鏈路的一個信道，基因值是個二進制符號。如果基因值為1，則鏈路的信道處于活躍狀態(tài)，否則基因值為0，如公式（8）：

圖2 染色體示例

（b）適應(yīng)度函數(shù)：適應(yīng)度函數(shù)的目的是區(qū)分優(yōu)質(zhì)染色體和劣質(zhì)染色體，以便種群向預(yù)期目標(biāo)進化。GACA算法的目的是確定每條鏈路每個信道是開啟還是關(guān)閉，以便滿足連接性約束和目標(biāo)函數(shù)值約束。因此，本文將染色體的適應(yīng)度函數(shù)定義為所有狀態(tài)下未連接對的數(shù)量和懲罰因子之和。懲罰因子定義為公式（9）：

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

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

圖3 示意圖

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

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

圖4 Bisearch算法的偽代碼

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

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

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

3 示例分析

本文運行LINGO優(yōu)化軟件[14]來獲得MIRTC問題的最優(yōu)解，并在小型網(wǎng)絡(luò)條件下比較最優(yōu)解與Bisearch算法解的性能。

小型網(wǎng)絡(luò)包括5個CR節(jié)點，如圖5所示：

圖5 MIRTC問題的最優(yōu)解和Bisearch算法解比較

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

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

4 性能評估

4.1 仿真配置

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

4.2 網(wǎng)絡(luò)干擾度

網(wǎng)絡(luò)干擾度定義為干擾鏈路的最大數(shù)量（即：目標(biāo)值Ω）。不同方案的網(wǎng)絡(luò)干擾度比較結(jié)果如圖6所示：

圖6 網(wǎng)絡(luò)干擾度與H間的關(guān)系

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

4.3 網(wǎng)絡(luò)吞吐量

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

圖7 網(wǎng)絡(luò)吞吐量的比較情況

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

5 總結(jié)

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

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

[2] 劉會衡, 鄧小鴻, 陳偉. 一種基于特征值的多天線認(rèn)知無線電盲感知算法[J]. 計算機應(yīng)用研究, 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）

衛(wèi)小偉（1975-），男，西安人，西安交通職業(yè)技術(shù)學(xué)院，信息工程系，博士，副教授。研究方向：無線傳感網(wǎng)、移動計算，西安 710018