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

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

?

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

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

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

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

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

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

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

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

1.1 基本模型

本文采用基于圖論的頻譜分配模型,并假設(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是一個正實數(shù),代表次用戶n使用頻譜m所能帶來的網(wǎng)絡(luò)收益。

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

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

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

(1)

1.2 解的編碼

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

(2)

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

圖1 解的映射編碼實例圖

2 基于MDABC的頻譜分配算法

2.1 DABC算法

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

(3)

ABC算法主要分為以下3個階段。

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

(4)

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

(5)

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

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

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

(6)

2.2 基于MDABC的頻譜分配算法

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

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

(7)

(8)

階段的劃分是平衡算法探索性能與開發(fā)性能[15]的關(guān)鍵。前期的全維更新具有更強的探索能力,但全維更新搜索精度不夠,極易陷入局優(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)驗值,取0.08;[·]表示用舍去法取整。

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

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

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

(10)

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

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

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

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

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

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

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

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

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

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

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

3 仿真實驗與分析

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

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

3.1 策略更換閾值T的測試

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

圖2 不同閾值T時的算法性能

3.2 不同算法下的平均收益

為比較不同策略對收益的影響,分別將引入和未引入更新維度選擇策略的情況稱為MDABC-SA算法和MDABC0-SA算法。以平均收益為目標函數(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特性是有效的先驗知識,融入到更新維度的選擇策略能夠使搜索更具有向性和有效性。

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

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

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

3.3 算法的耗時分析

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

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

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

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

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

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

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

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

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

4 結(jié) 論

頻譜的合理、高效分配是實現(xiàn)認知無線電技術(shù)的關(guān)鍵?；趫D論的頻譜分配模型是一個典型的NP-Hard優(yōu)化問題,適合用智能算法解決。本文提出的多策略離散人工蜂群頻譜分配算法從兩方面進行了改進:①引入多策略種群更新機制,在前期采用全維更新策略快速粗搜索以優(yōu)化初始種群,后期采用單維更新策略進行精細搜索以保證搜索精度;②利用頻譜分配問題中存在的親1特性,提出考慮親1特性的更新維度選擇策略,加強了搜索的有向性與有效性。仿真實驗表明,采用多策略離散人工蜂群的頻譜分配算法,能夠取得更高的網(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)星認知無線電檢測門限與功率分配聯(lián)合優(yōu)化算法 [J]. 西安交通大學(xué)學(xué)報, 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] 李曉艷, 張海林, 郭超平, 等. 一種異步的認知無線電網(wǎng)絡(luò)跳頻算法 [J]. 西安交通大學(xué)學(xué)報, 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] 王兵, 白智全, 董培浩, 等. 采用空時分組編碼的動態(tài)分組加權(quán)合作頻譜感知方案 [J]. 西安交通大學(xué)學(xué)報, 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]李鑫濱, 劉磊, 馬鍇. 基于離散人工蜂群算法的認知無線電頻譜分配 [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—),女,教授。 基金項目:國家自然科學(xué)基金資助項目(61201177)。

時間: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