畢曉君，李安寧

哈爾濱工程大學(xué)信息與通信工程學(xué)院，哈爾濱 150000

基于差分進(jìn)化算法的認(rèn)知無(wú)線電頻譜分配

畢曉君，李安寧

哈爾濱工程大學(xué)信息與通信工程學(xué)院，哈爾濱 150000

針對(duì)認(rèn)知無(wú)線電系統(tǒng)中認(rèn)知用戶分配可用頻譜問題，提出基于差分進(jìn)化算法的認(rèn)知無(wú)線電頻譜分配算法。利用差分算法設(shè)置參數(shù)少、尋優(yōu)能力強(qiáng)、不易于陷入局部最優(yōu)等特點(diǎn)，得到可以使認(rèn)知用戶平均系統(tǒng)效益最大化的頻譜分配方案。仿真結(jié)果表明，提出的算法不僅提高了用戶平均系統(tǒng)效益，而且縮短了運(yùn)行時(shí)間，提高了頻譜分配效率。

認(rèn)知無(wú)線電；認(rèn)知用戶；差分進(jìn)化算法；頻譜分配；系統(tǒng)效益

1 引言

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

2 認(rèn)知無(wú)線電頻譜分配模型

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

（1）可用頻譜矩陣L

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

（2）效益矩陣B

B={bn，m}N×M，bn，m表示認(rèn)識(shí)用戶n使用頻譜m為系統(tǒng)所帶來(lái)的效益。由于不同的認(rèn)知用戶采用的發(fā)射功率、調(diào)制技術(shù)等不同，因此在不同的頻譜上具有不同的系統(tǒng)效益，如頻譜利用率、最大流量。由于只有可用的頻譜才會(huì)為系統(tǒng)帶來(lái)效益，因此，當(dāng)ln，m=0時(shí)，必有bn，m=0。

（3）干擾矩陣C

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

（4）無(wú)干擾分配矩陣A

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

文獻(xiàn)[6]選擇最大化系統(tǒng)效益總和（MSR）工作目標(biāo)，其目的是使整個(gè)小區(qū)內(nèi)所有認(rèn)知用戶取得的效益總和最大化，然而當(dāng)認(rèn)知用戶逐漸增多時(shí)并不能很好地反映系統(tǒng)中平均每個(gè)認(rèn)知用戶所取得的系統(tǒng)效益，為了體現(xiàn)出系統(tǒng)中認(rèn)知用戶平均系統(tǒng)效益U，本文選取認(rèn)知用戶平均系統(tǒng)效益作為工作目標(biāo)[11]，具體公式如式（2）所示。

其中，N為認(rèn)知用戶的數(shù)目，M為可用頻譜的數(shù)目。

3 差分進(jìn)化算法

3.1 標(biāo)準(zhǔn)差分進(jìn)化算法

差分進(jìn)化算法（Differential Evolution，DE）是1995年由Storn等人提出的一種群體智能優(yōu)化算法[12]，2005年被引入國(guó)內(nèi)。DE算法具有記憶個(gè)體最優(yōu)解和種群內(nèi)信息共享的特點(diǎn)，通過(guò)種群內(nèi)個(gè)體的合作與競(jìng)爭(zhēng)來(lái)實(shí)現(xiàn)對(duì)優(yōu)化問題的求解[13]，其本質(zhì)是一種基于實(shí)數(shù)編碼的具有保優(yōu)思想的貪婪遺傳算法。

其中f為目標(biāo)函數(shù)。

3.2 二進(jìn)制差分進(jìn)化算法

最初的DE算法主要針對(duì)解決連續(xù)空間函數(shù)優(yōu)化問題，為解決離散優(yōu)化問題，文獻(xiàn)[14]提出一種二進(jìn)制差分算法（Binary Differential Evolution，BDE），可以有效解決離散函數(shù)優(yōu)化問題。

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

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

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

除了以上不同之外，二進(jìn)制差分算法與標(biāo)準(zhǔn)差分算法完全相同。

4 基于BDE算法的認(rèn)知無(wú)線電頻譜分配算法

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

圖1 差分進(jìn)化個(gè)體編碼結(jié)構(gòu)示例

算法的實(shí)現(xiàn)流程如下：

（1）為了模擬實(shí)際應(yīng)用中各個(gè)認(rèn)知用戶使用頻譜所帶來(lái)的效益和不同用戶之間可能存在的干擾，隨機(jī)生成可用頻譜矩陣L、效益矩陣B（本文在創(chuàng)建B時(shí)給B乘以了一個(gè)系數(shù)M/N，用來(lái)模擬小區(qū)無(wú)線網(wǎng)絡(luò)的實(shí)際情況）、干擾約束矩陣C。

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

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

（4）計(jì)算目標(biāo)函數(shù)值：按照?qǐng)D2求解得到矩陣A1；并對(duì)A1利用公式（1）進(jìn)行約束處理，使其滿足無(wú)干擾約束條件；再根據(jù)公式（2）計(jì)算得到每個(gè)個(gè)體的目標(biāo)函數(shù)值。

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

（6）選擇操作：使變異和交叉前后的個(gè)體進(jìn)行適應(yīng)度比較，目標(biāo)函數(shù)值大的個(gè)體保留下來(lái)進(jìn)入下一代。

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

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

5 實(shí)驗(yàn)仿真與結(jié)果分析

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

系統(tǒng)仿真實(shí)驗(yàn)所用到的相關(guān)參數(shù)如下：種群規(guī)模popsize=10，迭代次數(shù)max_g=500，改進(jìn)遺傳遺傳算法中pc1=0.6，pc2=0.9，在BDE算法中CR=0.8，F(xiàn)=0.05。

本文分別從用戶平均系統(tǒng)效益隨迭代次數(shù)變化曲線、隨認(rèn)知用戶數(shù)目變化曲線和隨頻譜數(shù)目變化曲線三方面將本文BDE算法與改進(jìn)遺傳算法進(jìn)行對(duì)比。

圖2給出了M=10、N=10時(shí)，兩種算法系統(tǒng)效益隨迭代次數(shù)的變化曲線。

圖2 用戶平均系統(tǒng)效益變化曲線

從圖中可以看出本文提出頻譜分配算法迭代最后能夠獲得的系統(tǒng)效益遠(yuǎn)遠(yuǎn)高于改進(jìn)遺傳算法獲得的系統(tǒng)效益。

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

在實(shí)際無(wú)線環(huán)境中，頻譜數(shù)目和認(rèn)知用戶數(shù)目實(shí)時(shí)改變，并且數(shù)目可能較大，需要分別驗(yàn)證用戶平均系統(tǒng)效益隨頻譜數(shù)目和認(rèn)知用戶數(shù)目變化時(shí)的工作性能。

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

圖3 用戶平均系統(tǒng)效益變化曲線

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

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

圖4 用戶平均系統(tǒng)效益變化曲線

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

6 結(jié)論

針對(duì)認(rèn)知無(wú)線電頻譜分配算法存在算法收斂速度慢，易陷入局部最優(yōu)等缺陷，本文提出了一種基于差分進(jìn)化算法的頻譜分配算法，充分利用差分進(jìn)化算法具有設(shè)置參數(shù)少、尋優(yōu)能力強(qiáng)、不易于陷入局部最優(yōu)等優(yōu)點(diǎn)，得到可以使認(rèn)知用戶平均系統(tǒng)效益最大化的頻譜分配方案。實(shí)驗(yàn)仿真結(jié)果表明，本文提出的算法收斂速度快，可使用戶獲得更高的系統(tǒng)效益，并且在大規(guī)模頻譜數(shù)量分配問題和大規(guī)模認(rèn)知用戶頻譜分配問題中可取得更好的分配結(jié)果，在認(rèn)知無(wú)線電系統(tǒng)中具有一定的實(shí)用價(jià)值。

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

[2]王欽輝，葉保留，田宇，等.認(rèn)知無(wú)線電網(wǎng)絡(luò)中頻譜分配算法[J].電子學(xué)報(bào)，2012，40（1）：147-154.

[3]滑楠，曹志剛.認(rèn)知無(wú)線電網(wǎng)絡(luò)路由研究綜述[J].電子學(xué)報(bào)，2010，38（4）：910-918.

[4]Wen K，F(xiàn)u 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]朱冰蓮，裴光術(shù)，張磊，等.認(rèn)知無(wú)線電網(wǎng)絡(luò)中系統(tǒng)效益最大化的頻譜分配[J].計(jì)算機(jī)工程，2012，38（3）：107-109.

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

[8]劉若辰，焦李成，雷七峰，等.一種新的差分進(jìn)化約束優(yōu)化算法[J].西安電子科技大學(xué)學(xué)報(bào)，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]張北偉，朱云龍，胡琨元.基于粒子群算法的認(rèn)知無(wú)線電頻譜分配算法[J].計(jì)算機(jī)應(yīng)用，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]畢曉君，王義新.多模態(tài)函數(shù)優(yōu)化的擁擠差分進(jìn)化算法[J].哈爾濱工程大學(xué)學(xué)報(bào)，2011，32（2）：223-227.

[13]王培崇，錢旭，王月，等.差分進(jìn)化算法研究綜述[J].計(jì)算機(jī)工程與應(yīng)用，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]彭振，趙知?jiǎng)?，鄭仕?基于混合蛙跳算法的認(rèn)知無(wú)線電頻譜分配[J].計(jì)算機(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.

國(guó)家自然科學(xué)基金（No.61175126）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金（No.HEUCFZ1209）；教育部博士點(diǎn)基金（No.20112304110009）。

畢曉君（1964—），女，博士，教授，主要研究領(lǐng)域?yàn)橹悄苄畔⑻幚?；李安寧?987—），男，碩士研究生，主要研究方向?yàn)橹悄苄畔⑻幚?，認(rèn)知無(wú)線電。E-mail：bixiaojun@hrbeu.edu.cn

2012-09-25

2012-11-16

1002-8331（2014）16-0100-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-03-26,http://www.cnki.net/kcms/detail/11.2127.TP.20130326.1042.013.htm l