基于差分進化算法的認知無線電頻譜分配

畢曉君，李安寧

哈爾濱工程大學信息與通信工程學院，哈爾濱 150000

基于差分進化算法的認知無線電頻譜分配

畢曉君，李安寧

哈爾濱工程大學信息與通信工程學院，哈爾濱 150000

針對認知無線電系統中認知用戶分配可用頻譜問題，提出基于差分進化算法的認知無線電頻譜分配算法。利用差分算法設置參數少、尋優能力強、不易于陷入局部最優等特點，得到可以使認知用戶平均系統效益最大化的頻譜分配方案。仿真結果表明，提出的算法不僅提高了用戶平均系統效益，而且縮短了運行時間，提高了頻譜分配效率。

認知無線電；認知用戶；差分進化算法；頻譜分配；系統效益

1 引言

近幾年隨著人們對無線通信需求的增長，無線頻段不斷被授權用戶分配，造成頻譜日益擁擠，因此出現了認知無線電技術，以期在授權頻段中尋找頻譜空穴，提高頻譜的利用率[1]。在認知無線電網絡中[2-3]，頻譜分配是一項關鍵技術，它允許未授權的無線系統通過對周圍無線通信環境的感知，來實現共享授權用戶所使用的頻段，從而達到提高頻譜利用效率的目的。因此，頻譜分配方案的好壞將直接影響整個系統的資源利用率[4-5]。對此，已有學者進行了相關研究，其中應用效果最好的是基于改進遺傳算法的頻譜分配算法[6]，雖然可以在一定程度上提高用戶平均效益，但是遺傳算法自身存在易于陷入局部最優的缺點，無法保證每次都能獲得最佳的頻譜分配方案。差分進化算法是近年興起的效果最好的優化算法，具有設置參數少、尋優能力強、不易于陷入局部最優等優點[7-8]，為此本文提出一種基于二進制差分進化算法的頻譜分配算法，可以在更短的時間內得到用戶效益更高的分配方案。

2 認知無線電頻譜分配模型

認知無線電的頻譜分配模型由可用頻譜矩陣、效益矩陣、干擾矩陣和無干擾分配矩陣來描述[9]。假設分配周期相對于頻譜環境變化時間很短，那么分配周期內各矩陣將保持不變[10]，假設在小區內某一時刻有N個認知用戶需要通信，同時有M個空閑頻帶可以使用，則相關矩陣具體定義如下：

（1）可用頻譜矩陣L

L={ln，m∈{0，1}}N×M，如果ln，m=1表示用戶n可以使用頻段m，ln，m=0表示用戶n不可以使用頻段m。具體的含義是如果頻譜m被授權用戶占用，一旦有認知用戶使用頻譜m則會對授權用戶產生干擾，違背認知無線電在不干擾授權用戶基礎上提高頻譜使用率這一初衷，因此分配方案需要根據可用矩陣L來進行分配。

（2）效益矩陣B

B={bn，m}N×M，bn，m表示認識用戶n使用頻譜m為系統所帶來的效益。由于不同的認知用戶采用的發射功率、調制技術等不同，因此在不同的頻譜上具有不同的系統效益，如頻譜利用率、最大流量。由于只有可用的頻譜才會為系統帶來效益，因此，當ln，m=0時，必有bn，m=0。

（3）干擾矩陣C

各個次用戶之間由于使用相同的可用頻譜而會對彼此產生干擾，用矩陣C表示，C={cn，k，m∈{0,1}}N×N×M。認知用戶n和k(1≤n，k≤N)同時使用頻譜m(1≤m≤M)產生干擾表示為cn，k，m，反之，cn，k，m=0。C由L決定，當n=k時，cn，n，m=1-ln，m；亦需滿足cn，k，m≤ln，m×lk，m，即頻譜m如果同時對認知用戶n和k可用時，就會可能產生干擾。

（4）無干擾分配矩陣A

將可用、無干擾的頻譜分別分配給用戶，得到A= {an，m|an，m∈{0，1}}N×M，其中an，m=1表示將頻譜m分配給認知用戶n，反之，an，m=0。同時，矩陣A必須滿足C定義的如下約束條件：

文獻[6]選擇最大化系統效益總和（MSR）工作目標，其目的是使整個小區內所有認知用戶取得的效益總和最大化，然而當認知用戶逐漸增多時并不能很好地反映系統中平均每個認知用戶所取得的系統效益，為了體現出系統中認知用戶平均系統效益U，本文選取認知用戶平均系統效益作為工作目標[11]，具體公式如式（2）所示。

其中，N為認知用戶的數目，M為可用頻譜的數目。

3 差分進化算法

3.1 標準差分進化算法

差分進化算法（Differential Evolution，DE）是1995年由Storn等人提出的一種群體智能優化算法[12]，2005年被引入國內。DE算法具有記憶個體最優解和種群內信息共享的特點，通過種群內個體的合作與競爭來實現對優化問題的求解[13]，其本質是一種基于實數編碼的具有保優思想的貪婪遺傳算法。

其中f為目標函數。

3.2 二進制差分進化算法

最初的DE算法主要針對解決連續空間函數優化問題，為解決離散優化問題，文獻[14]提出一種二進制差分算法（Binary Differential Evolution，BDE），可以有效解決離散函數優化問題。

與標準差分算法不同之處在于問題解空間都是通過0和1編碼，如果直接進行變異操作所得到的變異個體可能不符合解空間取值范圍的限制，所以進行以下操作，首先按照下式對解向量映射到[0，1]之間，如公式（6）所示。

然后針對變異操作后不在[0，1]之間的解按照sigmoid函數映射到該范圍內，如公式（7）所示。

最后在交叉操作之前再將解重新映射成由0和1組成的解，如公式（8）所示。

除了以上不同之外，二進制差分算法與標準差分算法完全相同。

4 基于BDE算法的認知無線電頻譜分配算法

本文研究的認知無線電頻譜分配問題可以描述為：在L，B，C已知的情況下，如何找到最優的無干擾分配矩陣A，使得認知用戶平均系統效益達到最大化。通過研究發現本文的頻譜分配問題可以歸結為NP問題，而差分進化算法是近年解決復雜NP問題較為理想的方法，因此本文首次將BDE算法應用到頻譜分配問題中，對公式（2）進行尋優，使U最大。在求解過程中，首先需要根據矩陣L生成初始種群，如果可用頻譜矩陣L中的ln，m為0，則對應無干擾分配矩陣A中相同位置的an，m必然為零，因此可以選擇對L中值為1位置對應A中的元素位置進行編碼，編碼長度等于L中值為1的個數l，因此種群中個體是長度為l的一維矢量[15]；在利用公式（2）計算個體目標函數值時，需要對兩個矩陣對應元素相乘，因此需要將種群中個體映射成無干擾分配矩陣A，只需先將一維矢量中元素為零對應矩陣L中相應位置元素值置為0，其他保持不變得到矩陣A1，再利用公式（1）對所得到的矩陣進行約束處理，即得到矩陣A。圖1給出了N=5、M=5時代表可行解的進化個體編碼結構示例，由圖中可以得到矩陣L中元素值為1的個數為7，種群個體pi為隨機生成長度為7的一維矢量，在計算個體目標函數值前，將pi中值為0元素對應矩陣L中相應位置元素值置0，得到矩陣A1，再利用矩陣C通過公式（1）進行約束處理，可得到無干擾分配矩陣A。

圖1 差分進化個體編碼結構示例

算法的實現流程如下：

（1）為了模擬實際應用中各個認知用戶使用頻譜所帶來的效益和不同用戶之間可能存在的干擾，隨機生成可用頻譜矩陣L、效益矩陣B（本文在創建B時給B乘以了一個系數M/N，用來模擬小區無線網絡的實際情況）、干擾約束矩陣C。

（2）設定參數：設定種群規模popsize，算法迭代次數max_g，交叉概率CR，變異因子F，并根據可用頻譜矩陣L確定初始種群中每個個體的維數codelength。

（3）生成初始種群：隨機生成一個popsize行codelength列的矩陣，其中每一行代表一個個體。

（4）計算目標函數值：按照圖2求解得到矩陣A1；并對A1利用公式（1）進行約束處理，使其滿足無干擾約束條件；再根據公式（2）計算得到每個個體的目標函數值。

（5）差分和交叉算子操作：從父代種群中隨機選取兩個不同的個體，根據公式（3）產生變異后新的子代；根據公式（4）生成交叉后的新個體。

（6）選擇操作：使變異和交叉前后的個體進行適應度比較，目標函數值大的個體保留下來進入下一代。

（7）重復步驟（4）～（6），直到滿足終止條件。其中適應度值最大的解映射成的矩陣就是使用戶平均系統效益達到最大的無干擾分配矩陣。

算法時間復雜度是影響算法效率的重要因素，通過算法的實現流程可以分析得到本文算法時間復雜度包括計算頻譜分配模型矩陣的時間復雜度和執行種群迭代的時間復雜度，頻譜分配模型矩陣的時間復雜度為O(N2M)，執行種群迭代的時間復雜度為O(popsize×N2M)，因此BDE算法迭代一次的時間復雜度為O(popsize×N2M)。

5 實驗仿真與結果分析

為驗證本文提出算法的效果，這里進行了仿真實驗，并與目前效果最好的改進遺傳算法[6]進行對比實驗。仿真結果均由算法重復運行30次并計算平均值而獲得，從而驗證本文提出算法的有效性和先進性。實驗是在Inter core i7 CPU Q720，1.6 GHz、內存4 GB的計算機上運行，程序采用MATLAB 2010b版本編寫。

系統仿真實驗所用到的相關參數如下：種群規模popsize=10，迭代次數max_g=500，改進遺傳遺傳算法中pc1=0.6，pc2=0.9，在BDE算法中CR=0.8，F=0.05。

本文分別從用戶平均系統效益隨迭代次數變化曲線、隨認知用戶數目變化曲線和隨頻譜數目變化曲線三方面將本文BDE算法與改進遺傳算法進行對比。

圖2給出了M=10、N=10時，兩種算法系統效益隨迭代次數的變化曲線。

圖2 用戶平均系統效益變化曲線

從圖中可以看出本文提出頻譜分配算法迭代最后能夠獲得的系統效益遠遠高于改進遺傳算法獲得的系統效益。

在實際應用中，頻譜分配要求算法必須在較快的時間內得到分配方案，因此要求算法的運行時間要短，在M=10、N=10時，改進遺傳算法所需運行時間為1.8 s，本文的BDE算法所需運行時間為1.4 s，可以看出本文算法的運行時間要少于改進遺傳算法，說明本文提出的算法不僅為認知用戶帶來更高的系統效益，而且花費的時間更短。兩個算法達到相同精度時，本文BDE算法所需迭代次數和時間均少于改進遺傳算法，說明BDE算法收斂速度快于改進遺傳算法。

在實際無線環境中，頻譜數目和認知用戶數目實時改變，并且數目可能較大，需要分別驗證用戶平均系統效益隨頻譜數目和認知用戶數目變化時的工作性能。

圖3給出了認知用戶數目固定，系統效益隨頻譜數目的變化曲線，具體參數為N=10，M從10逐漸變化到30。

圖3 用戶平均系統效益變化曲線

從圖中可以看出隨著頻譜數目增多，用戶平均系統收益呈總體上升趨勢，而本文BDE算法所取得的系統綜合收益始終要高于基于改進遺傳算法的系統收益，說明本文算法在大規模頻譜數量分配問題中可以獲得更好的頻譜分配方案。

圖4給出了頻譜數目固定，認知用戶平均系統效益隨認知用戶數目的變化曲線，具體參數為M=10，N從10逐漸變化到30。

圖4 用戶平均系統效益變化曲線

從圖中可以看出隨著認知用戶的數目增多，用戶平均系統收益呈總體下降趨勢，而本文BDE算法所取得的認知用戶平均系統收益始終要高于基于改進遺傳算法的系統收益，說明在為大規模認知用戶頻譜分配問題中，本文算法可以獲得更好的頻譜分配方案。

6 結論

針對認知無線電頻譜分配算法存在算法收斂速度慢，易陷入局部最優等缺陷，本文提出了一種基于差分進化算法的頻譜分配算法，充分利用差分進化算法具有設置參數少、尋優能力強、不易于陷入局部最優等優點，得到可以使認知用戶平均系統效益最大化的頻譜分配方案。實驗仿真結果表明，本文提出的算法收斂速度快，可使用戶獲得更高的系統效益，并且在大規模頻譜數量分配問題和大規模認知用戶頻譜分配問題中可取得更好的分配結果，在認知無線電系統中具有一定的實用價值。

[1]王臣昊，楊震，肖小潮.基于優化貝葉斯壓縮感知算法的頻譜檢測[J].信號處理，2012，28（5）：750-756.

[2]王欽輝，葉保留，田宇，等.認知無線電網絡中頻譜分配算法[J].電子學報，2012，40（1）：147-154.

[3]滑楠，曹志剛.認知無線電網絡路由研究綜述[J].電子學報，2010，38（4）：910-918.

[4]Wen K，Fu L S，Li X S.Genetic algorithm based spectrum allocation for cognitive radio networks[C]//2011 International Conference on Coputer，Communication，Control and Automation.Zhuhai，China，19-20 November，2011：693-700.

[5]Zhao Z J，Peng Z，Zheng S L，et al.Cognitive radio spectrum allocation using evolutionary algorithms[J].IEEE Trans on Wireless Communications，2009，8（9）：4421-4425.

[6]朱冰蓮，裴光術，張磊，等.認知無線電網絡中系統效益最大化的頻譜分配[J].計算機工程，2012，38（3）：107-109.

[7]楊啟文，蔡亮，薛云燦.差分進化算法綜述[J].模式識別與人工智能，2008，21（4）：506-513.

[8]劉若辰，焦李成，雷七峰，等.一種新的差分進化約束優化算法[J].西安電子科技大學學報，2011，38（1）：47-52.

[9]Bernaille L，Teixeira R，Akodkenou I.Traffic classification on the fly[J].Computer Communication Review，2006，36（2）：23-26.

[10]張北偉，朱云龍，胡琨元.基于粒子群算法的認知無線電頻譜分配算法[J].計算機應用，2011，32（12）：3184-3214.

[11]Peng C，Zheng H，Zhao B Y.Utilization and fairness in spectrum assignment for opportunistic spectrumacess[J]. ACM Mobile Networks and Applications，2006，11（4）：555-576.

[12]畢曉君，王義新.多模態函數優化的擁擠差分進化算法[J].哈爾濱工程大學學報，2011，32（2）：223-227.

[13]王培崇，錢旭，王月，等.差分進化算法研究綜述[J].計算機工程與應用，2009，45（28）：13-16.

[14]Deng C S，Zhao B Y，Yang Y L，et al.Novel binary differential evolution algorithm for discrete optimaization[C]//5th International Conference on Natural Computation，Tianjian，China，14-16 August 2009：346-349.

[15]彭振，趙知勁，鄭仕鏈.基于混合蛙跳算法的認知無線電頻譜分配[J].計算機工程，2010，36（6）：210-217.

BI Xiaojun,LI Anning

College of Information and Communication Engineering,Harbin Engineering University,Harbin 150000,China

According to the problem of spectrum allocation for secondary users in cognitive radio system,this paper puts forward the spectrum allocation algorithm based on the differential evolution algorithm.With less parameters,strong ability of finding global optimization solution and avoiding getting into local optimality of the differential evolution algorithm. The spectrum allocation scheme is got which can maximize the mean system utility.The simulation results show that the algorithm in this paper not only increases mean system utility of secondary users but also shortens running time and improves the efficiency of spectrum allocation.

cognitive radio;secondary user;DE algorithm;spectrum allocation;system utility

A

TN914

10.3778/j.issn.1002-8331.1209-0287

BI Xiaojun,LI Anning.Spectrum allocation based on differential evolution algorithm in cognitive rad io.Computer Engineering and Applications,2014,50（16）：100-103.

國家自然科學基金（No.61175126）；中央高校基本科研業務費專項資金（No.HEUCFZ1209）；教育部博士點基金（No.20112304110009）。

畢曉君（1964—），女，博士，教授，主要研究領域為智能信息處理；李安寧（1987—），男，碩士研究生，主要研究方向為智能信息處理，認知無線電。E-mail：bixiaojun@hrbeu.edu.cn

2012-09-25

2012-11-16

1002-8331（2014）16-0100-04

CNKI網絡優先出版：2013-03-26,http://www.cnki.net/kcms/detail/11.2127.TP.20130326.1042.013.htm l