朱冰蓮,朱方方,段青言,張良,肖欣庭

(重慶大學(xué)通信工程學(xué)院, 400044, 重慶)

?

采用多策略離散人工蜂群的改進(jìn)頻譜分配算法

朱冰蓮,朱方方,段青言,張良,肖欣庭

(重慶大學(xué)通信工程學(xué)院, 400044, 重慶)

針對圖論頻譜分配模型下最優(yōu)頻譜分配策略搜索解困難、耗時(shí)長的問題,提出一種采用多策略離散人工蜂群的頻譜分配算法。首先,根據(jù)感知技術(shù)得到的通信環(huán)境狀況,建立頻譜分配的圖論模型;然后,引入多策略離散人工蜂群算法進(jìn)行最優(yōu)頻譜分配策略的搜索,在搜索初期,引入全局探索能力強(qiáng)的粗搜索策略,以快速優(yōu)化初始種群,后期以高精度的單維更新進(jìn)行精細(xì)搜索;考慮到僅當(dāng)解參數(shù)值取1才能帶來網(wǎng)絡(luò)收益的增加,提出僅對取值為零的維度進(jìn)行更新的策略,增強(qiáng)了搜索的有向性與有效性。仿真實(shí)驗(yàn)表明:該算法與當(dāng)前基于離散人工蜂群和二進(jìn)制粒子算法的頻譜分配算法相比,無論是收斂速度還是網(wǎng)絡(luò)收益都得到提高;當(dāng)可用頻譜數(shù)在5～20之間、次用戶數(shù)量在5～22之間變化時(shí),獲得相同最大收益的耗時(shí)僅為對比算法的47.75%～36.18%,且隨著問題規(guī)模增加耗時(shí)呈下降趨勢。

頻譜分配;圖論模型;人工蜂群

頻譜資源緊張是制約無線通信業(yè)務(wù)進(jìn)一步發(fā)展的關(guān)鍵性問題之一。然而,大量調(diào)查卻顯示當(dāng)前頻譜利用率極低,如Chiang等對新西蘭奧克蘭市806～2 750 MHz之間的頻段使用情況進(jìn)行統(tǒng)計(jì)分析,結(jié)果表明,頻譜的有效利用率僅為6.2%[1]。面對這一現(xiàn)象,大量學(xué)者指出:并非頻譜資源本身短缺,而是當(dāng)前的頻譜管理機(jī)制存在嚴(yán)重缺陷[2]。認(rèn)知無線電技術(shù)正是解決這一問題的有效方法[3]。在認(rèn)知無線電系統(tǒng)下,認(rèn)知用戶可發(fā)現(xiàn)未被使用的空閑頻譜并智能地接入,這種頻譜管理方式極大地提高了頻譜利用率[4-5]。實(shí)現(xiàn)頻譜智能接入的關(guān)鍵技術(shù)之一就是實(shí)現(xiàn)頻譜的合理、高效分配。

在已有的頻譜分配模型如圖論模型,定價(jià)拍賣模型和博弈論模型[6]等中,圖論模型通過改變目標(biāo)效用函數(shù)能夠滿足不同應(yīng)用場景的需求,且在集中式和分布式等多種頻譜管理機(jī)制下具有普適性[7],很快成為研究熱點(diǎn)。圖論模型最初采用圖著色算法進(jìn)行求解,該算法求解速度快,但檢測結(jié)果差[8]。其后,Zhao等人對模型進(jìn)行了優(yōu)化,引入一種映射編碼方法,將遺傳算法、二進(jìn)制粒子群算法等新型智能算法引入其中,取得了較好的效果[6]。遺傳算法、二進(jìn)制粒子群算法雖然具有較快的收斂速度,但極易陷入局優(yōu)。Li等人將離散人工蜂群(discrete artificial bee colony, DABC)用于解決頻譜分配問題,提出基于離散人工蜂群的頻譜分配(discrete artificial bee colony based spectrum allocation, DABC-SA)算法[9-10],取得了更高的網(wǎng)絡(luò)收益,但離散人工蜂群算法收斂速度較慢。實(shí)時(shí)性是認(rèn)知無線電網(wǎng)絡(luò)中頻譜分配問題不同于其他資源分配問題的顯著特點(diǎn)[11],如何在提高網(wǎng)絡(luò)收益的同時(shí)保證收斂速度是關(guān)鍵。受遺傳算法、二進(jìn)制粒子群算法等快速收斂算法的啟發(fā),本文提出一種采用多策略引導(dǎo)的多策略離散人工蜂群頻譜分配算法(multi-strategy discrete artificial bee colony based spectrum allocation, MDABC-SA)算法,前期引入全局搜索能力強(qiáng)的鄰域搜索算子進(jìn)行粗搜索,以優(yōu)化初始種群、定位最優(yōu)解范圍,后期改用局部搜索能力強(qiáng)的鄰域搜索算子進(jìn)行細(xì)搜索,以保證算法的優(yōu)化性能,同時(shí)有效的先驗(yàn)知識能提高算法搜索效率、促進(jìn)算法快速收斂。就頻譜分配問題而言,增加頻譜的分配會導(dǎo)致目標(biāo)效益函數(shù)值的增加,因此,解參數(shù)值由0向1的更新才是有效更新,即問題本身存在親1特性。將親1特性與優(yōu)化算法進(jìn)行融合,保證優(yōu)化算法搜索的有向性和有效性,進(jìn)一步加快了收斂速度。

1 基于圖論的頻譜分配模型

1.1 基本模型

本文采用基于圖論的頻譜分配模型,并假設(shè)信道參數(shù)變化相對頻譜分配耗時(shí)可以忽略。設(shè)通信環(huán)境中可用頻譜數(shù)為M,次用戶數(shù)量為N,信道環(huán)境的主要參數(shù)如下[7]。

(1)頻譜可用性矩陣L={ln,m|ln,m∈{0,1}}N×M,其中l(wèi)n,m=1表示頻譜m對次用戶n可用,ln,m=0表示不可用。

(2)效益矩陣B={bn,m|bn,m∈[0,+∞]}N×M,其中bn,m是一個(gè)正實(shí)數(shù),代表次用戶n使用頻譜m所能帶來的網(wǎng)絡(luò)收益。

(3)約束矩陣C={cn,k,m|cn,k,m∈{0,1}}N×N×M,可看作M個(gè)N×N的二維矩陣,各二維矩陣表示用戶在各頻譜上的沖突情況,其中cn,k,m=1表示次用戶n和次用戶k同時(shí)使用頻譜m會產(chǎn)生干擾,cn,k,m=0時(shí)用戶n、k可同時(shí)在頻譜m上通信。顯然,當(dāng)n=k時(shí),cn,k,m的取值由ln,m決定,即cn,k,m=1-ln,m。

(4)分配矩陣A={an,m|an,m∈{0,1}}N×M,它記錄了在某一分配周期內(nèi),M個(gè)頻譜對N個(gè)認(rèn)知用戶的最終分配策略。an,m=1表示認(rèn)知用戶n可以在該分配周期內(nèi)使用頻譜m,顯然,分配矩陣A受約束矩陣C的約束,即當(dāng)cn,k,m=1時(shí),an,m+ak,m≤1,?n,k∈[0,N],m∈[0,M]。

根據(jù)通信環(huán)境需求的不同,網(wǎng)絡(luò)收益函數(shù)有多種不同的形式,在此以平均最大化網(wǎng)絡(luò)收益總和為目標(biāo)函數(shù),目標(biāo)函數(shù)的表達(dá)式為

(1)

1.2 解的編碼

分配矩陣A即為頻譜分配的求解對象,直接對A進(jìn)行編碼,則解的維數(shù)為N×M,此時(shí)解編碼的冗余度較高。原因在于:A為受L約束的同維矩陣,L中值為0的元素位置所對應(yīng)的A中元素值必定為0(不可用頻譜必定不能被分配),即當(dāng)ln,m=0時(shí),an,m=0。因此,文獻(xiàn)[6]提出僅對A中對應(yīng)于L中l(wèi)n,m=1的an,m進(jìn)行編碼,編碼長度D由L中1元素的個(gè)數(shù)決定,如式(2)表示

(2)

對于一個(gè)N=4、M=5的信道環(huán)境,直接以A進(jìn)行編碼,長度為20,在二進(jìn)制空間將有220種不同的A值。用實(shí)例來說明解的映射編碼原理,如圖1所示。圖1中,L中有7個(gè)1元素,按照文獻(xiàn)[6]提供的方法,根據(jù)L抽取A中的部分元素進(jìn)行編碼,則解編碼X是長度為7的行向量,在二進(jìn)制空間僅有27不同的值,最優(yōu)解的搜索范圍大大減少。得到最優(yōu)解X后再按L的抽取關(guān)系將X還原成A即可。

圖1 解的映射編碼實(shí)例圖

2 基于MDABC的頻譜分配算法

2.1 DABC算法

2.1.1 標(biāo)準(zhǔn)ABC算法 人工蜂群算法(artificial bee colony, ABC)是Karaboga模仿自然界蜜蜂覓食行為提出的一種智能優(yōu)化算法[12]。在ABC算法中,雇傭蜂、守望蜂、食物源在數(shù)量上相等,一個(gè)食物源位置對應(yīng)于優(yōu)化問題的一個(gè)解,目標(biāo)函數(shù)的適應(yīng)度值對應(yīng)蜂群中食物源的蜜源質(zhì)量。對于一個(gè)D維優(yōu)化問題,設(shè)種群大小為S,則在第t次搜索時(shí),第i個(gè)食物源的位置為

(3)

ABC算法主要分為以下3個(gè)階段。

(1)雇傭蜂階段。雇傭蜂在當(dāng)前食物源位置附近尋找蜜源質(zhì)量更高的食物源位置,并將蜜源質(zhì)量信息傳遞給守望蜂,雇傭蜂的鄰域搜索公式為

(4)

(2)守望蜂階段。守望蜂根據(jù)雇傭蜂傳遞的信息,挑選蜜源質(zhì)量高的食物源進(jìn)一步開發(fā),以輪盤賭法為各守望蜂選擇待采蜜源,并進(jìn)行鄰域開發(fā),守望蜂的鄰域搜索公式同式(4)。各食物源被選中的概率與其適應(yīng)度的大小相關(guān)。設(shè)pi為第i個(gè)食物源被守望蜂選中的概率,則

(5)

式中:fi為第i個(gè)食物源的適應(yīng)度值;fmax、fmin分別為所有食物源中適應(yīng)度的最大值和最小值。

(3)偵察蜂階段。當(dāng)雇傭蜂、守望蜂經(jīng)過最多U次鄰域搜索后,適應(yīng)度值仍得不到提升的食物源處出現(xiàn)偵察蜂,偵察蜂隨機(jī)尋找新的食物源替換原食物源位置。U的取值與編碼長度D和種群大小S有關(guān),一般取S>D[12]。

2.1.2 DABC算法 ABC算法的解是連續(xù)的,不能直接用于離散問題優(yōu)化。為實(shí)現(xiàn)ABC算法向離散域的拓展,Marinakis基于Sigmoid函數(shù)離散法提出DABC算法[13],即引入連續(xù)域向二進(jìn)制離散域的映射公式

(6)

2.2 基于MDABC的頻譜分配算法

頻譜分配問題可描述為:在通信環(huán)境參數(shù)L、B、C已知的情況下,尋找使目標(biāo)函數(shù)f(A)最大的分配矩陣A。為滿足通信實(shí)時(shí)性要求,本文提出多策略引導(dǎo)的MDABC-SA算法:①根據(jù)搜索過程中對算法開發(fā)能力和探索能力的平衡要求,引入不同的種群更新策略;②結(jié)合頻譜分配本身特性,提出在特定維度上進(jìn)行更新的維度確定策略。

2.2.1 種群更新策略 初始種群的優(yōu)劣是影響智能算法收斂速度的重要因素[14]。受遺傳算法、粒子群算法等全維更新算法啟發(fā),在最優(yōu)解搜索初期,雇傭蜂和守望蜂均采用全維同時(shí)更新的搜索策略,以快速優(yōu)化初始種群,后期保持單維更新的高精度策略,以提高尋優(yōu)精度。具體方法如下:設(shè)置閾值T,當(dāng)?shù)螖?shù)t≤T時(shí),進(jìn)行粗搜索(式(7));當(dāng)t>T時(shí),進(jìn)行精細(xì)搜索(式(8))

(7)

(8)

階段的劃分是平衡算法探索性能與開發(fā)性能[15]的關(guān)鍵。前期的全維更新具有更強(qiáng)的探索能力,但全維更新搜索精度不夠,極易陷入局優(yōu),該階段搜索周期過長將阻礙算法的快速收斂,而前期搜索周期過短,又起不到初始解優(yōu)化的目的。問題規(guī)模的大小決定了優(yōu)化問題的難度,問題規(guī)模越大,優(yōu)化初始解需要的迭代次數(shù)越多,故MDABC-SA算法采用與問題規(guī)模相關(guān)的階段劃分策略。閾值T的確定方法如下式

T=[ξD]

(9)

式中:ξ為初始解優(yōu)化系數(shù),該參數(shù)一般為經(jīng)驗(yàn)值,取0.08;[·]表示用舍去法取整。

2.2.2 更新維度的選擇策略 在基于圖論的頻譜分配模型中,解的某一維參數(shù)由0變?yōu)?時(shí)意味著系統(tǒng)嘗試將某一頻帶分配給某一認(rèn)知用戶,若分配滿足約束矩陣,則目標(biāo)函數(shù)f(A)將會增加由該用戶在該頻帶通信帶來的效益值;如分配不滿足約束矩陣,則系統(tǒng)根據(jù)約束矩陣C隨機(jī)取消當(dāng)前某一用戶的通信(將存在干擾的2個(gè)參數(shù)中的1個(gè)隨機(jī)置0)[6]。相反,解的某一維參數(shù)由1變?yōu)?,雖不會導(dǎo)致干擾沖突,但卻意味著讓某一用戶退出在某一頻帶上的通信,此時(shí)目標(biāo)函數(shù)f(A)必定減小,雖嘗試了新的解,但卻不是朝著目標(biāo)函數(shù)值增大的方向,此次嘗試是無益嘗試。尤其是對于單維更新的DABC-SA和MDABC-SA算法中的后期策略,一次只更新一維參數(shù)的值,若該維參數(shù)的值由1變?yōu)?,則必將導(dǎo)致f(A)的值減小,此時(shí)嘗試的新解必將被淘汰。因此,基于圖論的頻譜分配模型具有親1特性,應(yīng)讓新解嘗試由0變1。

據(jù)此,本文在種群更新策略中加入該先驗(yàn)信息,指引算法更高效地搜索。MDABC-SA算法前期采用全維更新進(jìn)行粗搜索,引入親1特性會限制算法的探索能力,導(dǎo)致算法以更大概率地陷入局優(yōu),故在算法前期不考慮親1特性,而在算法后期更注重提高算法的開發(fā)能力。后期更新策略和DABC-SA算法一樣,采用高精度的單維更新,此時(shí)引入親1特性,選擇在當(dāng)前參數(shù)值為0的維度進(jìn)行更新,更新維度P的確定如下

P=select(j|xi,xij=0)

(10)

式中:操作符select表示隨機(jī)從向量xi中抽取一取值為0的維度,并將它的維度下標(biāo)值j返回。

2.2.3 MDABC-SA算法流程 根據(jù)上述分析,MDABC-SA算法的一般流程可描述如下。

步驟1 初始化。設(shè)置最大迭代次數(shù)H、種群大小S、鄰域搜索次數(shù)最大值U、初始解優(yōu)化系數(shù)ξ,根據(jù)式(2)計(jì)算編碼長度D,由式(9)計(jì)算T。隨機(jī)生成S組形如式(3)的初始蜜源位置x,且x∈{0,1}D,每個(gè)蜜源位置x代表一種可能的頻譜分配方案。將L中值為1的元素對應(yīng)的下標(biāo)(n,m),按先n遞增,后m遞增的順序記錄在R中,即R={(n,m)|ln,m=1}。

步驟2 干擾約束處理。將所有x按R記錄的映射關(guān)系映射為A,按C的約束關(guān)系進(jìn)行約束處理[6]:對任意m,查找所有滿足cn,k,m=1的(n,k),當(dāng)an,m和ak,m同時(shí)為1時(shí),隨機(jī)將其中之一置0。將約束處理后的A按R記錄的映射關(guān)系還原成x。

步驟3 評價(jià)各食物源蜜源質(zhì)量。根據(jù)式(1)進(jìn)行蜜源質(zhì)量計(jì)算,并記錄。

步驟4 雇傭蜂階段。雇傭蜂依次對食物源進(jìn)行鄰域開發(fā):當(dāng)t≤T時(shí),按式(7)進(jìn)行更新;當(dāng)t>T時(shí),由式(10)確定更新維度,再按式(8)進(jìn)行更新,按式(6)離散化。再按步驟2和步驟3進(jìn)行約束處理和蜜源質(zhì)量計(jì)算,保留蜜源質(zhì)量高的食物源。若該蜜源更新,則該蜜源的未更新次數(shù)r置0;否則r加1。

步驟5 守望蜂階段。按式(5)計(jì)算各食物源被選中概率,以輪盤賭法為各守望蜂選擇待開發(fā)蜜源,按步驟4的方法進(jìn)行鄰域開發(fā)。

步驟6 偵察蜂階段。當(dāng)某蜜源處的r大于U時(shí),該蜜源處出現(xiàn)一只偵察蜂,即隨機(jī)產(chǎn)生一個(gè)形如式(3)的蜜源位置x,且x∈{0,1}D,用x替代舊蜜源位置。

步驟7 停止條件判斷。如果迭代次數(shù)t小于H,記錄S組蜜源中蜜源質(zhì)量最大的蜜源位置,作為當(dāng)前最優(yōu)解,同時(shí),轉(zhuǎn)至步驟4;否則,停止搜索,并將當(dāng)前最優(yōu)解按R映射為A,作為得到的最佳頻譜分配策略。

2.3 MDABC-SA算法的收斂性分析

文獻(xiàn)[16]分析了ABC算法的收斂性,證明了人工蜂群算法是一種全局收斂算法。本文MDABC-SA算法與ABC算法一樣,解的更新是一個(gè)有記憶的隨機(jī)游動,當(dāng)前解僅與上一次迭代解相關(guān),滿足有限齊次Markov鏈的判定條件。MDABC-SA算法與ABC算法的不同在于:MDABC-SA算法引入多策略機(jī)制,在搜索初期以全維更新算子進(jìn)行搜索,以優(yōu)化初始解,但是全維更新算子僅執(zhí)行有限次,且MDABC-SA算法的任一策略均保留了貪婪選擇策略,在經(jīng)歷足夠迭代次數(shù)后,這一過程與ABC算法的過程保持一致。因此,MDABC-SA算法也是一種全局收斂的算法。

3 仿真實(shí)驗(yàn)與分析

通信環(huán)境參數(shù)L、B、C,頻譜數(shù)M以及用戶數(shù)N設(shè)置如下[10]:L為隨機(jī)生成的0、1矩陣;B中元素取值從1到10中隨機(jī)選取;C中各二維矩陣為隨機(jī)生成的0、1對稱陣;M=22;N=20。

為分析MDABC-SA算法的性能,將MDABC-SA算法與基于粒子群的頻譜分配(BPSO-SA)算法[6]和DABC-SA算法[10]進(jìn)行比較。參數(shù)設(shè)置如下:S=20;T=[0.08D];U=SD,H取為500。為了排除偶然性,下面給出的實(shí)驗(yàn)結(jié)果均為30次仿真的平均結(jié)果。

3.1 策略更換閾值T的測試

T的大小關(guān)系著算法探索性能和開發(fā)性能的平衡,以迭代次數(shù)為橫軸,平均最大化網(wǎng)絡(luò)收益總和(以下簡稱平均收益率)為縱軸,對不同T值進(jìn)行仿真對比實(shí)驗(yàn),結(jié)果如圖2所示。圖2中,曲線1的T=0,即為DABC-SA算法,收斂速度較慢;當(dāng)T值過大時(shí),如圖中曲線3,算法雖也能收斂,但由于第一階段過長,停留于局部最優(yōu)時(shí)間過長,從而導(dǎo)致算法收斂速度變慢;而當(dāng)T取無窮大,即整個(gè)搜索過程采用全維更新時(shí),算法無法跳出局優(yōu)。實(shí)驗(yàn)中發(fā)現(xiàn)當(dāng)T取[0.05D]～[0.1D]時(shí),收斂較快,圖2中2號線是T取[0.08D]的結(jié)果。

圖2 不同閾值T時(shí)的算法性能

3.2 不同算法下的平均收益

為比較不同策略對收益的影響,分別將引入和未引入更新維度選擇策略的情況稱為MDABC-SA算法和MDABC0-SA算法。以平均收益為目標(biāo)函數(shù),MDABC0-SA、MDABC-SA、DABC-SA和BPSO-SA算法的收斂曲線如圖3所示。由圖3可以看出,DABC-SA算法能夠獲得較高收益,但收斂性能不如BPSO-SA算法,而MDABC0-SA、MDABC-SA算法的收斂速度都明顯快于DABC-SA、BPSO-SA算法,說明初期的種群優(yōu)化策略是有效的,且MDABC-SA算法無論收斂速度還是優(yōu)化性能,都優(yōu)于MDABC0-SA算法,說明親1特性是有效的先驗(yàn)知識,融入到更新維度的選擇策略能夠使搜索更具有向性和有效性。

圖3 不同算法下網(wǎng)絡(luò)平均收益率與迭代次數(shù)的關(guān)系

以計(jì)算時(shí)間為橫軸,得到與圖3相對應(yīng)的收斂曲線如圖4所示。由圖4可以看出,無論在前期還是后期,達(dá)到相同的收益時(shí)MDABC-SA算法所需要的計(jì)算時(shí)間更短。

圖4 不同算法下網(wǎng)絡(luò)平均收益率與計(jì)算時(shí)間的關(guān)系

3.3 算法的耗時(shí)分析

幾種算法達(dá)到DABC-SA算法的最大收益值的耗時(shí)情況如表1所示。雖然BPSO-SA算法前期具有較快的尋優(yōu)能力,但易陷入局優(yōu),達(dá)不到DABC-SA算法的最大收益值,故未在表1中列出。從表1中可以看出:MDABC-SA算法相對于DABC-SA算法耗時(shí)大幅減小;當(dāng)可用頻譜數(shù)在5～20之間變化、次用戶數(shù)量在5～22之間變化時(shí),獲得DABC-SA算法所能得到的最大收益的耗時(shí)僅為其47.75%～36.18%,且隨著問題規(guī)模增大,耗時(shí)比呈現(xiàn)下降的趨勢。

表1 不同算法下的耗時(shí)隨問題規(guī)模變化

注:耗時(shí)比為DABC-SA算法的耗時(shí)與MDABC-SA算法的耗時(shí)之比。

3.4 認(rèn)知用戶數(shù)變化下的平均收益

保持可用頻譜數(shù)M=30不變,改變認(rèn)知用戶數(shù),得到平均收益率隨認(rèn)知用戶數(shù)N的變化曲線如圖5所示,可以看出,隨著認(rèn)知用戶數(shù)的不斷增加,平均收益呈遞減變化,MDABC-SA算法始終能獲得高于DABC-SA和BPSO-SA算法的平均收益率。

圖5 平均收益率隨認(rèn)知用戶數(shù)的變化關(guān)系

3.5 頻譜數(shù)變化下的平均收益

設(shè)認(rèn)知用戶數(shù)N=20不變,當(dāng)可用頻譜數(shù)M改變時(shí),平均收益率變化曲線如圖6所示。由圖6可見,隨著可用頻譜數(shù)的增加,平均收益率不斷增加,且MDABC-SA算法始終能獲得高于DABC-SA和BPSO-SA算法的平均收益率。

圖6 平均收益率隨可用頻譜數(shù)的變化關(guān)系

4 結(jié) 論

頻譜的合理、高效分配是實(shí)現(xiàn)認(rèn)知無線電技術(shù)的關(guān)鍵?；趫D論的頻譜分配模型是一個(gè)典型的NP-Hard優(yōu)化問題,適合用智能算法解決。本文提出的多策略離散人工蜂群頻譜分配算法從兩方面進(jìn)行了改進(jìn):①引入多策略種群更新機(jī)制,在前期采用全維更新策略快速粗搜索以優(yōu)化初始種群,后期采用單維更新策略進(jìn)行精細(xì)搜索以保證搜索精度;②利用頻譜分配問題中存在的親1特性,提出考慮親1特性的更新維度選擇策略,加強(qiáng)了搜索的有向性與有效性。仿真實(shí)驗(yàn)表明,采用多策略離散人工蜂群的頻譜分配算法,能夠取得更高的網(wǎng)絡(luò)收益和更快的收斂速度。

[1] CHIANG R I, ROWE G B, SOWERBY K W. A quantitative analysis of spectral occupancy measurements for cognitive radio [C]∥ Proceedings of the IEEE 65th Vehicular Technology Conference. Piscataway, NJ, USA: IEEE, 2007: 3016-3020.

[2] 陳鵬, 邱樂德, 王宇. 衛(wèi)星認(rèn)知無線電檢測門限與功率分配聯(lián)合優(yōu)化算法 [J]. 西安交通大學(xué)學(xué)報(bào), 2013, 47(6): 31-36, 43. CHEN Peng, QIU Lede, WANG Yu. Joint optimization algorithm of detection threshold and power allocation for satellite underlay cognitive radio [J]. Journal of Xi’an Jiaotong University, 2013, 47(6): 31-36, 43.

[3] 李曉艷, 張海林, 郭超平, 等. 一種異步的認(rèn)知無線電網(wǎng)絡(luò)跳頻算法 [J]. 西安交通大學(xué)學(xué)報(bào), 2012, 46(12): 30-35. LI Xiaoyan, ZHANG Hailin, GUO Chaoping, et al. Asynchronous channel hopping algorithm for cognitive radio networks [J]. Journal of Xi’an Jiaotong University, 2012, 46(12): 30-35.

[4] 王兵, 白智全, 董培浩, 等. 采用空時(shí)分組編碼的動態(tài)分組加權(quán)合作頻譜感知方案 [J]. 西安交通大學(xué)學(xué)報(bào), 2014, 48(8): 23-28. WANG Bing, BAI Zhiquan, DONG Peihao, et al. A spectrum sensing scheme with weighted collaboration of dynamical clustering using space-time block code [J]. Journal of Xi’an Jiaotong University, 2014, 48(8): 23-28.

[5] TRAGOS E Z, ZEADALLY S, FRAGKIADAKIS A G, et al. Spectrum assignment in cognitive radio networks: a comprehensive survey [J]. IEEE Communications Surveys & Tutorials, 2013, 15(3): 1108-1135.

[6] ZHAO Z, PENG Z, ZHENG S, et al. Cognitive radio spectrum allocation using evolutionary algorithms [J]. IEEE Transactions on Wireless Communications, 2009, 8(9): 4421-4425.

[7] PENG C, ZHENG H, ZHAO B Y. Utilization and fairness in spectrum assignment for opportunistic spectrum access [J]. Mobile Networks and Applications, 2006, 11(4): 555-576.

[8] FRAGKIADAKIS A G, TRAGOS E Z, ASKOXYLAKIS I G. A survey on security threats and detection techniques in cognitive radio networks [J]. IEEE Communications Surveys & Tutorials, 2013, 15(3): 428-445.

[9] GHASEMI A, MASNADI-SHIRAZI M A, BIGUESH M, et al. Spectrum allocation based on artificial bee colony in cognitive radio networks [C]∥ Proceedings of 2012 Sixth International Symposium on Telecommunications. Piscataway, NJ, USA: IEEE, 2012: 182-187.

[10]李鑫濱, 劉磊, 馬鍇. 基于離散人工蜂群算法的認(rèn)知無線電頻譜分配 [J]. 系統(tǒng)工程與電子技術(shù), 2012, 34(10): 2136-2141. LI Xinbin, LIU Lei, MA Kai. Cognitive radio spectrum allocation based on discrete artificial bee colony algorithm [J]. Systems Engineering and Electronics, 2012, 34(10): 2136-2141.

[11]NAEEM M, ANPALAGAN A, JASEEEMUDDIN M, et al. Resource allocation techniques in cooperative cognitive radio networks [J]. IEEE Communications Surveys & Tutorials, 2014, 16(3): 729-744.

[12]KARABOGA D, BASTURK B. On the performance of artificial bee colony (ABC) algorithm [J]. Applied Soft Computing, 2008, 8(1): 687-697.

[13]MARINAKIS Y, MARINAKI M, MATSATSINIS N. A hybrid discrete artificial bee colony-GRASP algorithm for clustering [C]∥ Proceedings of International Conference on Computers & Industrial Engineering. Piscataway, NJ, USA: IEEE, 2009: 548-553.

[14]GAO W, LIU S, HUANG L. A global best artificial bee colony algorithm for global optimization [J]. Journal of Computational and Applied Mathematics, 2012, 236(11): 2741-2753.

[15]CREPINSEK M, LIU S, MERNIK M. Exploration and exploitation in evolutionary algorithms: a survey [J]. ACM Computing Surveys, 2013, 45(3): 35-38.

[16]寧愛平, 張雪英. 人工蜂群算法的收斂性分析 [J]. 控制與決策, 2013(10): 1554-1558. NING Aiping, ZHANG Xueying. Convergence analysis of artificial bee colony algorithm [J]. Control and Decision, 2013(10): 1554-1558.

(編輯 劉楊)

An Improved Spectrum Allocation Algorithm Using Multi-Strategy Discrete Artificial Bee Colony Technology

ZHU Binglian,ZHU Fangfang,DUAN Qingyan,ZHANG Liang,XIAO Xinting

(College of Communication Engineering, Chongqing University, Chongqing 400044, China)

An improved spectrum allocation (MDABC-SA) algorithm using the multi-strategy discrete artificial bee colony technology is proposed to reduce computational time of spectrum allocation based on graph model. First, a spectrum allocation model is established based on parameters obtained by sensing technology. Then, the multi-strategy discrete artificial bee colony technology is employed to find the optimal spectrum allocation scheme, and a global searching operator is used in initial searches to rapidly find a better initial population, An one-dimensional search is then used in later searches to perform fine line search. The strategy to update only the elements with value of 0 is proposed to inhance the direction and effectiveness of searches by considering the fact that the more ‘1’ have in the solution, the higher network utilization can be achieved. Simulation results and comparisons with the spectrum allocation algorithms using DABC and BPSO algorithms show that the proposed algorithm obviously improves both the convergence speed and network utilization. The algorithm achieves the same maximum benefit with only 47.75%-36.18% of consumed time of the former two algorithms when the number of available spectrum is between 5 and 20 and the number of secondary users varies from 5 to 22 and a downward trend in consumed time is observed when the problem scale increases.

artificial bee colony; spectrum allocation; graph model

2015-04-13。

朱冰蓮(1959—),女,教授。 基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(61201177)。

時(shí)間:2016-01-03

10.7652/xjtuxb201602004

TP18;TN925

A

0253-987X(2016)02-0020-06

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160103.2006.002.html