一種采用并行免疫優(yōu)化的頻譜分配算法

吳慧欣， 王 秉， 柴爭(zhēng)義

(1. 華北水利水電大學(xué) 信息工程學(xué)院，河南 鄭州 450011； 2. 河南交通職業(yè)技術(shù)學(xué)院 航運(yùn)海事系，河南 鄭州 450005; 3. 天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387; 4. 東南大學(xué) 移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210096)

無線頻譜是不可再生的稀缺資源．隨著無線通信業(yè)務(wù)的迅速發(fā)展，無線頻譜資源愈發(fā)緊缺．已有的研究表明，固定頻譜管理體制造成了頻譜資源的巨大浪費(fèi)[1]．在認(rèn)知無線網(wǎng)絡(luò)中，認(rèn)知用戶(次用戶)通過對(duì)授權(quán)用戶(主用戶)授權(quán)頻譜的“二次利用”，有效地提高了頻譜使用效率，被認(rèn)為是目前解決頻譜資源供需矛盾的最有效途徑之一[2-3]．

頻譜分配是提高頻譜利用率的關(guān)鍵問題之一．頻譜分配的主要目的是在認(rèn)知用戶、網(wǎng)絡(luò)QOS等需求下，有效分配可用頻譜資源，達(dá)到最優(yōu)狀態(tài)．針對(duì)不同的應(yīng)用場(chǎng)景，現(xiàn)有的頻譜分配方法主要包括博弈論、拍賣理論以及圖著色理論等[4]．筆者主要研究基于合作的分布式完全受限頻譜分配算法，是基于圖著色理論實(shí)現(xiàn)的．在基于圖論的已有研究中，顏色敏感圖著色(Color Sensitive Graph Coloring，CSGC)算法[5]是最具代表性的成果之一，詳細(xì)地給出了基于圖論的頻譜分配模型，并對(duì)效益和公平性進(jìn)行了較詳盡的分析．基于圖論的頻譜分配是一個(gè)優(yōu)化問題，其最優(yōu)著色算法是一個(gè)NP難問題[6]，智能優(yōu)化是求解此類問題的有效途徑．為了降低算法的復(fù)雜度，文獻(xiàn)[6]將遺傳算法引入頻譜分配，實(shí)現(xiàn)了較好的分配結(jié)果并降低了求解復(fù)雜度．此后，免疫算法[7]、粒子群算法[8]、蟻群算法[9]等智能算法相繼用來提高求解效果．

然而，已有的算法更多地關(guān)注網(wǎng)絡(luò)的總體收益，對(duì)如何減少算法運(yùn)行時(shí)間的研究并不多．實(shí)際上，由于可用頻譜信息的動(dòng)態(tài)變化，實(shí)時(shí)性要求是認(rèn)知無線網(wǎng)絡(luò)頻譜分配區(qū)別于其他無線通信頻譜分配的最重要特點(diǎn)之一，因此，頻譜分配時(shí)間應(yīng)該盡可能短．基于此，筆者提出一種基于并行免疫的頻譜分配算法，減少算法的計(jì)算時(shí)間．

1 認(rèn)知無線網(wǎng)絡(luò)的頻譜分配模型

認(rèn)知無線網(wǎng)絡(luò)頻譜分配模型可用以下矩陣表示[4-9]: 可用頻譜矩陣L、效益矩陣B、干擾矩陣C和分配矩陣A．

假設(shè)有N個(gè)認(rèn)知用戶，可用頻譜數(shù)為M，頻譜間相互正交．對(duì)各個(gè)矩陣說明如下:

(1) 可用頻譜矩陣L．可用頻譜矩陣L={ln，m|ln，m∈{0，1}}N×M．當(dāng)ln，m=1 時(shí)，表示認(rèn)知用戶n(1≤n≤N) 可以使用頻譜m(1≤m≤M) ；當(dāng)ln，m=0 時(shí)，表示認(rèn)知用戶n不能使用頻譜m．

(2) 效益矩陣B．在同一個(gè)可用頻譜上，不同的認(rèn)知用戶獲得的效益用效益矩陣B={bn，m}N×M表示，即用戶n(1≤n≤N) 使用頻譜m(1≤m≤M) 后得到的收益．很顯然，當(dāng)ln，m=0 時(shí)，必有bn，m=0，即只有可用頻譜才有效益矩陣．

(3) 干擾矩陣C．不同的認(rèn)知用戶使用同一可用頻譜可能產(chǎn)生干擾，用干擾矩陣C表示，C= {cn，k，m|cn，k，m∈{0，1}}N×N×M．當(dāng)cn，k，m=1 時(shí)，表示認(rèn)知用戶n和k(1≤n，k≤N) 同時(shí)使用頻譜m(1≤m≤M) 會(huì)產(chǎn)生干擾；反之，當(dāng)cn，k，m=0 時(shí)，干擾矩陣C由可用頻譜矩陣L決定．當(dāng)n=k時(shí)，cn，n，m= 1-ln，m，并且滿足cn，k，m≤ln，mlk，m，即只有頻譜m同時(shí)對(duì)認(rèn)知用戶n和k可用時(shí)，才可能產(chǎn)生干擾．

(4) 無干擾分配矩陣A．將可用、無干擾的頻譜分配給認(rèn)知用戶，得到無干擾分配矩陣A= {an，m|an，m∈{0，1}}N×M．當(dāng)an，m=1 時(shí)，表示將頻譜m分配給認(rèn)知用戶n；反之，an，m=0．分配矩陣必須滿足C定義的如下約束條件:an，m×ak，m=0， 如果cn，k，m=1，?n，k

從上面的描述可知，滿足條件的分配矩陣A不止一個(gè)，用∧NM表示所有A的集合．給定某一無干擾頻譜分配矩陣A，次用戶n獲得的總收益用效益向量R表示為

頻譜分配的目標(biāo)是最大化網(wǎng)絡(luò)效益U(R)，則可表示為如下所示的優(yōu)化問題:

其中，arg(·)表示求解網(wǎng)絡(luò)效益最大時(shí)所對(duì)應(yīng)的頻譜分配矩陣A．因此，A*即為所求的最優(yōu)無干擾頻譜分配矩陣．

U(R)有不同的表示形式[4-9]，考慮到流量和公平性需求，這里U(R)定義為平均最大化網(wǎng)絡(luò)收益總和：

2 并行免疫優(yōu)化算法的主要思想

在智能優(yōu)化中，為了加快算法的收斂速度，同時(shí)又不希望犧牲種群的多樣性，算法的并行實(shí)現(xiàn)是一個(gè)有效途徑．人工免疫優(yōu)化的并行化模型主要借鑒進(jìn)化算法實(shí)現(xiàn)，有主從式并行模型、粗粒度并行模型及細(xì)粒度并行模型[10-12]．筆者采用簡(jiǎn)單易實(shí)現(xiàn)的主從式并行模型．主從式是一種單種群進(jìn)化模型，分為主進(jìn)程和從進(jìn)程，主進(jìn)程執(zhí)行進(jìn)化操作算子，從進(jìn)程分別計(jì)算每個(gè)抗體的親和度值，主進(jìn)程和從進(jìn)程交替工作．

在人工免疫優(yōu)化中，抗體映射為問題的候選解，免疫優(yōu)化算法通過初始化、親和度評(píng)價(jià)、克隆擴(kuò)增、克隆變異、克隆選擇等過程對(duì)抗體進(jìn)行優(yōu)化，最終得到所需的解[13-14]．對(duì)免疫優(yōu)化算法而言，傳統(tǒng)的串行算法在克隆個(gè)體后，循環(huán)計(jì)算每個(gè)個(gè)體的親和度．在并行計(jì)算中，可以把循環(huán)進(jìn)行分解，也就是把要計(jì)算適應(yīng)度的個(gè)體通過消息發(fā)送到集群中的多個(gè)節(jié)點(diǎn)中，然后并行計(jì)算親和度，最后各個(gè)節(jié)點(diǎn)把計(jì)算好的親和度傳送回來．

并行算法流程簡(jiǎn)單描述如下:

(1) 主節(jié)點(diǎn)獲得處理器(CPU)個(gè)數(shù)X和種群規(guī)模Y．

(2) 計(jì)算每個(gè)節(jié)點(diǎn)要計(jì)算的個(gè)體數(shù)目Z．每個(gè)處理器要計(jì)算的個(gè)體(向下取整)，剩余的個(gè)體發(fā)送給編號(hào)較大的處理器．因此，每個(gè)處理器接收到的個(gè)體數(shù)目最多只相差一個(gè)．

(3) 主節(jié)點(diǎn)發(fā)送個(gè)體編碼到從節(jié)點(diǎn)，各個(gè)從節(jié)點(diǎn)并行計(jì)算親和度并發(fā)送回主節(jié)點(diǎn)，主節(jié)點(diǎn)接收從節(jié)點(diǎn)返回的親和度值．

3 基于并行免疫優(yōu)化的頻譜分配實(shí)現(xiàn)技術(shù)

從上面的描述可知，頻譜分配問題具體描述為: 在可用頻譜矩陣L、效益矩陣B、干擾矩陣C已知的情況，如何找到最優(yōu)的頻譜分配矩陣A，使得網(wǎng)絡(luò)效益U(R)最大．

3.1 關(guān)鍵技術(shù)

針對(duì)頻譜分配問題，筆者設(shè)計(jì)的免疫優(yōu)化算法關(guān)鍵技術(shù)說明如下:

(2) 抗體編碼表示到分配矩陣A的映射．分別記錄矩陣L中值為1的元素對(duì)應(yīng)的n與m，并將其按照先n遞增、后m遞增的方式保存在L1中，即L1= {(n，m)|ln，m=1}．顯然，L1中元素個(gè)數(shù)為l．將種群中每個(gè)抗體的每一位j(1≤j≤l) 映射為矩陣A的元素an，m，其中(n，m)的值為L(zhǎng)1中相應(yīng)的第j個(gè)元素j(1≤j≤l)．

(3) 親和度函數(shù)的表示．由于頻譜分配的目標(biāo)是實(shí)現(xiàn)最大化網(wǎng)絡(luò)效益U(R)，故直接將U(R)作為親和度函數(shù)．

3.2 算法實(shí)現(xiàn)步驟

算法的基本步驟如下(其中，P表示抗體種群，p表示一個(gè)抗體)．

步驟1 初始化．設(shè)進(jìn)化代數(shù)g為零，種群規(guī)模為s，按照前面所述的編碼方式，隨機(jī)初始化種群P(g)= {p1(g)，p2(g)，…，ps(g)}．

步驟2 抗體表示到頻譜分配方案的映射．通過抗體映射方式，將每一個(gè)抗體映射為相應(yīng)的分配矩陣A，即為一種可能的頻譜分配方案．

步驟3 干擾約束的處理．隨機(jī)產(chǎn)生的抗體所對(duì)應(yīng)的分配矩陣A不一定滿足干擾矩陣C，所以，必須進(jìn)行修正．具體實(shí)現(xiàn)如下: 對(duì)任意m，如果cn，k，m=1，則查看矩陣A中第m列的第n行和第k行元素值是否同時(shí)為1．若是，則隨機(jī)將其中一位置零，另一位保持不變．此時(shí)得到的分配矩陣A則為經(jīng)過約束處理的可行解；同時(shí)，對(duì)相應(yīng)的抗體表示進(jìn)行映射，更新P(g)．

步驟4 按照上面所示的并行化過程對(duì)P(g)進(jìn)行親合度函數(shù)評(píng)價(jià)．對(duì)P(g)中的s個(gè)抗體進(jìn)行親和度計(jì)算，結(jié)果按從大到小降序排序，親和度最大的抗體所對(duì)應(yīng)的分配矩陣A即為所求的最優(yōu)頻譜分配方案．

步驟5 終止條件判斷．如果達(dá)到設(shè)置的最大進(jìn)化次數(shù)gmax，則算法終止，將抗體種群中親和度最高的抗體映射為A的形式，即得到了最佳的頻譜分配；否則，轉(zhuǎn)步驟6．

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

4.1 算法仿真環(huán)境和參數(shù)設(shè)置

在并行計(jì)算實(shí)驗(yàn)室HPC集群機(jī)上進(jìn)行了仿真．集群有1個(gè)管理節(jié)點(diǎn)，1個(gè)I/O節(jié)點(diǎn)， 32個(gè)常規(guī)計(jì)算節(jié)點(diǎn)，操作系統(tǒng)為RedHat Enterprise Linux AS，使用C+MPI進(jìn)行編程實(shí)現(xiàn)．MPI是消息傳遞模型的國(guó)際標(biāo)準(zhǔn)[10]．在實(shí)驗(yàn)過程中，L、B、C矩陣的生成采用文獻(xiàn)[5]附錄1提供的偽代碼產(chǎn)生，并且保證其滿足相應(yīng)的約束．免疫算法中參數(shù)的取值如下: 最大進(jìn)化代數(shù)gmax=200，種群規(guī)模s=20，變異概率pm=0.1，克隆規(guī)模控制參數(shù)nc=5，使用的處理器個(gè)數(shù)為1～8個(gè)．

4.2 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本算法的性能，與目前求解頻譜分配問題經(jīng)典的CSGC算法[5]及本課題前期的免疫克隆選擇算法進(jìn)行了比較[7]．這兩個(gè)算法是串行算法，在I/O節(jié)點(diǎn)上運(yùn)行．實(shí)驗(yàn)結(jié)果使用網(wǎng)絡(luò)收益總和來衡量．為了公平起見，在算法比較試驗(yàn)中，使用代碼產(chǎn)生相同的L、B、C，使用同樣的參數(shù)設(shè)置，并將算法運(yùn)行50次，取平均結(jié)果．表1是50次實(shí)驗(yàn)所得到的平均收益，其中分別選M=N=5 和M=N=20 (M表示可用頻譜，N表示認(rèn)知用戶)．從表1中可以看出，筆者提出的算法在網(wǎng)絡(luò)收益上高于對(duì)比算法．同時(shí)，也可以看出，隨著迭代次數(shù)的增加(CSCG是確定性算法，不隨迭代次數(shù)變化)，筆者提出的算法收斂速度快于串行免疫算法的收斂速度，說明了筆者提出的算法有較快的求解速度．

表1 網(wǎng)絡(luò)收益比較

為了進(jìn)一步對(duì)比算法的性能，實(shí)驗(yàn)驗(yàn)證了在認(rèn)知用戶N固定的情況下，隨著可用頻譜M的增加，相關(guān)算法的性能變化．這里取N=10，結(jié)果如圖1所示．

圖1 可用頻譜對(duì)相關(guān)算法網(wǎng)絡(luò)收益的影響圖2 用戶數(shù)量對(duì)相關(guān)算法網(wǎng)絡(luò)平均收益的影響

從圖1可以看出，隨著可用頻譜數(shù)M的增加，網(wǎng)絡(luò)收益一直在遞增．筆者提出的算法在收益增加方面優(yōu)于另外兩種算法，進(jìn)一步表明了筆者提出的算法的有效性．同時(shí)，實(shí)驗(yàn)也驗(yàn)證了在可用頻譜M已知的情況下，認(rèn)知用戶數(shù)變化對(duì)網(wǎng)絡(luò)收益的影響，結(jié)果如圖2所示．實(shí)驗(yàn)結(jié)果表明：隨著認(rèn)知用戶數(shù)的增加，系統(tǒng)收益降低，但筆者提出的算法得到的收益高于另外兩種算法，證明了筆者提出的算法的優(yōu)越性．

4.3 并行算法的性能分析

衡量并行算法相對(duì)收益的指標(biāo)一般使用加速比和效率分析[10-12]．加速比sp=ts/tp，其中ts是求解一個(gè)問題的串行算法的運(yùn)行時(shí)間，tp是求解同一個(gè)問題的并行算法的運(yùn)行時(shí)間．可見，加速比是算法的并行性對(duì)運(yùn)行時(shí)間改進(jìn)的程度．效率Ep=sp/p，其中p為處理器的個(gè)數(shù)，效率反映了并行系統(tǒng)中處理器的有效利用情況．這里使用筆者提出的算法和串行免疫克隆算法[7]進(jìn)行比較．

表2 算法并行效果

表2所示是在不同處理器個(gè)數(shù)下頻譜分配算法運(yùn)行時(shí)間、加速比、效率的情況．

5 總結(jié)與展望

頻譜分配是認(rèn)知無線網(wǎng)絡(luò)中的關(guān)鍵問題之一，而實(shí)時(shí)性是其顯著特點(diǎn)之一．筆者提出了一種基于并行免疫優(yōu)化的頻譜分配算法，縮短了算法分配時(shí)間，對(duì)認(rèn)知頻譜分配的實(shí)時(shí)性有促進(jìn)意義．下一步將繼續(xù)研究并行免疫優(yōu)化算法的并行模型、子種群規(guī)模和計(jì)算能力之間的關(guān)系．此外，負(fù)載均衡和程序優(yōu)化等也還需要進(jìn)一步的研究．

[1] Akyildlz I F, Lee W Y, Vuran M C, et al. Next Generation/dynamic Spectrum Access/cognitive Radio Wireless Networks: a Survey [J]. Computer Networks, 2006, 50(13): 2127-2159.

[2] 魏急波, 王杉, 趙海濤. 認(rèn)知無線網(wǎng)絡(luò): 關(guān)鍵技術(shù)與研究現(xiàn)狀[J]. 通信學(xué)報(bào), 2011, 32(11): 147-158.

Wei Jibo, Wang Shan, Zhao Haitao. Cognitive Wireless Networks: Key Techniques and Sate of the Art[J]. Journal on Communications, 2011, 32(11): 147-158.

[3] Wang Beibei, Liu K J R. Advances in Cognitive Radio Networks: a Survey[J]. IEEE Journal of Selected Topics in Signal Processing, 2011, 5(1): 5-23.

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

Wang Qinhui, Ye Baoliu, Tian Yu, et al. Survey on Spectrum Allocation Algorithms for Cognitive Radio Networks[J]. Acta Electronica Sinica, 2012, 40(1): 147-154.

[5] Peng Chunyi , Zheng Haitao, Zhao Benyi. Utilization and Fairness in Spectrum Assignment for Opportunistic Spectrum Access[J]. Mobile Networks and Applications, 2006, 11(4): 555-576.

[6] Zhao Zhijin, Peng Zhen, Zheng Shilian. Cognitive Radio Spectrum Allocation Using Evolutionary Algorithms[J]. IEEE Transactions on Wireless Communications, 2009, 8(9): 4421-4425.

[7] 柴爭(zhēng)義, 劉芳. 基于免疫克隆選擇優(yōu)化的認(rèn)知無線網(wǎng)絡(luò)頻譜分配[J]. 通信學(xué)報(bào), 2010, 31(11): 91-100.

Chai Zhengyi, Liu Fang. Spectrum Allocation of Cognitive Wireless Network Based on Immune Clone Selection Optimization[J]. Journal on Communications, 2010, 31(11): 91-100.

[8] Tang Meiqin, Long Chengnian, Guan Xinping, et al. Nonconvex Dynamic Spectrum Allocation for Cognitive Radio Networks Via Particle Swarm Optimization and Simulated Annealing[J]. Computer Networks, 2012, 56(11): 2690-2699.

[9] 楊淼, 安建平. 認(rèn)知無線網(wǎng)絡(luò)中一種基于蟻群優(yōu)化的頻譜分配算法[J]. 電子與信息學(xué)報(bào), 2011, 33(10): 2306-2311

Yang Miao, An Jianping. An Ant Colony Optimization Algorithm for Spectrum Assignment in Cognitive Radio Networks[J]. Journal of Electronics & Information Technology, 2011, 33(10): 2306-2311.

[10] 朱虎明, 焦李成. 并行免疫克隆特征選擇算法[J]. 西安電子科技大學(xué)學(xué)報(bào), 2008, 35(5): 853-857.

Zhu Huming, Jiao Licheng. Parallel Immune Clonal Selection for Feature Selection[J]. Journal of Xidian University, 2008, 35(5): 853-857.

[11] Jacobsen D A. Senocak I. Multi-level Parallelism for Incompressible Flow Computations on GPU Clusters[J]. Parallel Computing, 2013, 39(1): 1-20.

[12] 戚玉濤, 焦李成, 劉芳. 基于并行人工免疫算法的大規(guī)模TSP問題求解[J]. 電子學(xué)報(bào), 2008, 36(8): 1552-1558.

Qi Yutao, Jiao Licheng, Liu Fang. Parallel Artificial Immune Algorithm for Large-Scale TSP[J]. Acta Electronica Sinica, 2008, 36(8):1552-1558.

[13] 尚榮華, 焦李成, 胡朝旭, 等. 修正免疫克隆約束多目標(biāo)優(yōu)化算法[J]. 軟件學(xué)報(bào), 2012, 23(7): 1773-1786.

Shang Ronghua, Jiao Licheng, Hu Chaoxu, et al. Modified Immune Clonal Constrained Multi-Objective Optimization Algorithm[J]. Journal of Software, 2012, 23(7): 1773-1786.

[14] 王凌霞, 焦李成, 顏學(xué)穎, 等. 利用免疫克隆進(jìn)行小波域遙感圖像變化檢測(cè)[J]. 西安電子科技大學(xué)學(xué)報(bào), 2013, 40(4): 108-113.

Wang Lingxia, Jiao Licheng, Yan Xueying, et al. Change Detection in Multi-temporal Remote Sensing Images Based on the Wavelet-domain Immune Clonal Optimazition[J]. Journal of Xidian University, 2013, 40(4): 108-113.

[15] Gong Maoguo, Chen Xiaowei, Ma Lijia, et al. Identification of Multi-resolution Network Structures with Multi-objective Immune Algorithm[J]. Applied Soft Computing, 2013, 13(4): 1705-1717.

[16] Gong Maoguo, Zhang Lingjun, Ma Jingjing, et al. Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm[J]. Journal of Computer Science and Technology, 2012, 27(3): 455-467.