基于統計特性的蝙蝠算法在認知無線電頻譜分配中的應用

朱冰蓮, 朱文勇, 朱志青, 陳 玲, 劉紫娟

(1. 重慶大學通信工程學院, 重慶 400044; 2. 重慶大學通信與測控中心, 重慶 400044)

0 引 言

認知無線電技術是解決頻譜供需矛盾的有效方法,被視為未來無線通信技術的核心技術之一[1]。頻譜分配是認知無線電中的重要技術,其目標是將主用戶未使用的空閑頻譜分配給次用戶,以提高頻譜資源利用率,實現最大化頻譜效益。

頻譜分配影響著頻譜資源的利用率,因此各類頻譜分配模型相繼被提出,包括圖論模型[2-3]、拍賣模型[4]和博弈論模型[5]等。圖論模型通過選擇不同的目標效用函數能夠滿足不同應用場景的需求,很快成為研究熱點。圖論模型由文獻[3]提出,被證明是一個典型的NP-Hard帶約束條件的組合優化問題。文獻[3]采用圖著色算法進行尋優,分析了該模型下的網絡總效益和用戶公平性。圖著色算法求解速度快但檢測結果差[6]。文獻[7]對該模型的解編碼進行了壓縮編碼[7],隨后,遺傳算法(genetic algorithm, GA)、二進制粒子群算法(binary particle swarm optimization, BPSO)[8]、離散人工蜂群算法(discrete artificial bee colony, DABC)[9-10]等智能算法被引入到該問題的求解,取得了較好的效果。但當問題規模加大時,這些算法的收斂性能受到嚴重挑戰。尋找高效的新型啟發式優化算法解決該問題成為必然趨勢。

蝙蝠算法[11]是Yang于2010年提出一種全局最優搜索算法,該算法結構簡單、收斂性能好,已被成功應用于各類工程實際問題[12-13]。但蝙蝠算法在連續域提出,不能直接應用于離散問題的優化。為了進一步拓展蝙蝠算法在實際工程中的應用,本文將蝙蝠算法應用到頻譜分配優化中,對蝙蝠算法進行離散化處理,并針對優化問題進行改進,取得了更好的效果。

1 蝙蝠算法

1.1 標準蝙蝠算法

蝙蝠是一種非常有趣的動物,有著先進的回聲定位能力。其在空中飛行或搜尋獵物時,會使用一種叫做回音定位的聲波定位器來捕捉獵物和躲避障礙物。蝙蝠一旦發現獵物,就會逐漸減小脈沖音量,增大脈沖發生率,以便于跟蹤獵物,直到將其捕獲。蝙蝠算法是一種模擬蝙蝠捕獲獵物的行為來優化工程項目中目標函數的智能算法[12]。

標準蝙蝠算法[11]中,用蝙蝠的位置表示待優化問題的解,每個蝙蝠對獵物進行搜索時有著以下動作:

(1) 所有蝙蝠利用回聲定位的方法感知距離,并可判斷獵物和障礙之間的不同。

(2) 第i只蝙蝠的飛行速度為vi,發出超聲波的頻率為fi(或波長λ),其音量(振幅)為Ai來搜尋獵物。同時,蝙蝠根據自身與目標的距離自動調整發出脈沖的頻率(或波長)和脈沖發生率ri。

(1)

(2)

(3)

xnew=x*+εAt

(4)

式中,ε為[-1,1]的隨機數向量;At為種群中所有蝙蝠在同一時刻音量的平均值。隨著Ai的減小,開發能力增強,蝙蝠位置(解)精度提高。

蝙蝠的速度和位置更新步驟有些類似于標準粒子群算法,如fi本質上控制了聚焦粒子運動的節奏和范圍。在某種程度上,蝙蝠算法可看做標準粒子群優化以及強化局部搜索算法的結合,音量和脈沖發生率控制著其探索能力和開發能力。當蝙蝠尋找到獵物時,它的音量就會降低,同時脈沖發生率增加。兩者更新為

(5)

(6)

1.2 二進制蝙蝠算法

蝙蝠算法初期提出主要用來解決連續空間函數優化問題，為了解決實際工程中許多的組合優化問題,需要對原始蝙蝠算法進行離散化處理。一般采用Sigmoid函數法進行離散化。在二進制蝙蝠算法(binary bat algorithm, BBA)[14]中,蝙蝠的每一維位置都限定為二進制0或1,但其速度大小沒有被限制,從而利用速度的大小來確定其在對應位置上是0或1,即位置更新意味著從0和1之間的相互轉換。這里采用S型函數進行離散化,蝙蝠位置更新為

(7)

(8)

綜上所述,BBA算法流程如下:

步驟1初始化蝙蝠種群,隨機產生蝙蝠的位置xi和速度vi。

步驟3根據式(1)調整頻率,根據式(2)更新蝙蝠的速度。

步驟4產生一個隨機數rand,如果rand>ri,則根據式(4)生成新解。否則,根據式(3)生成新解。按式(7)和式(8)對新解進行離散化。

步驟5產生一個隨機數rand,如果randF(x*),則接受新解,并增加ri,減小音量Ai,否則保持不變,其中F為待優化問題的函數。

步驟6根據蝙蝠位置,計算所有蝙蝠的適應度值,更新當前最優解x*。

步驟7如果達到所設置的最大迭代次數,停止執行算法;否則,轉至步驟3。

1.3 基于統計特性的蝙蝠算法

經過離散化處理后的BBA可以應用到頻譜分配優化問題中,但取得的效果并不好。因此,針對頻譜分配的特點對蝙蝠算法進行改進,以得到更好的效果。根據BBA流程的步驟5,可以看出蝙蝠算法是非貪婪選擇,這對于連續域優化問題,可以減少陷入局部最優的概率。由于頻譜分配優化問題是一個NP-Hard問題,其解空間為有限可列,若采用貪婪選擇,則可以增加算法在當前位置的開發能力。因此,本文采用貪婪選擇策略,即只要新解比當前位置好,就接受該解。

除此之外,蝙蝠算法的局部開發能力有待于改進[15],在局部搜索時,應當考慮種群中其他蝙蝠的位置。受量子粒子群算法[16]啟發,將平均最好位置作為蝙蝠算法位置更新的一種策略,提出基于統計特性的蝙蝠算法(bat algorithm based on statistical characteristics, SCBA)。在SCBA中,記錄種群中各蝙蝠所經歷的最好位置,利用統計分析方法,統計所有蝙蝠經歷最好位置的分布情況,利用平均最好位置指導蝙蝠尋優。平均最好位置的定義為

(9)

對于一個種群大小NP=4,待優化問題維數D=5的二進制優化問題中,xt表示第t次迭代后各蝙蝠所經歷的最好位置,由式(9)得到平均最好位置如圖1所示。

圖1 平均最好位置的定義Fig.1 Definition of mean best position

(10)

2 基于蝙蝠算法的頻譜分配

由于圖論模型參數簡單,并且每個參數有著實際的物理意義,易于仿真實現。通過選擇不同的目標效用函數能夠滿足不同應用場景的需求,很快成為頻譜分配的研究熱點,因此,本文選擇圖論模型。

2.1 圖論頻譜分配模型

假設通信環境改變的時長與頻譜分配所需時間相比(主用戶的位置變化、可用頻譜數變化所需時間與頻譜分配計算時間相比),可忽略不計。將用戶之間的頻譜使用情況用圖表示,則可以利用無向圖優化得到較優頻譜分配方案。對于次用戶數為N，可用頻譜數為M的頻譜環境,圖論模型下的頻譜分配的定義如下[3]:

定義1頻譜可用性矩陣L。L={ln,m|ln,m∈{0,1}}N×M,其中,ln,m=1表示在該時刻用戶n可利用頻譜m進行通信,ln,m=0則表示在該時刻用戶n不能用頻譜m進行通信。

通過頻譜感知技術可以檢測到次用戶在當前環境中可利用的頻譜,將所有次用戶和可用頻譜的關系用矩陣L描述。

定義2頻譜效益矩陣B。B={bn,m}N×M,其中,bn,m表示用戶n使用頻譜m能獲得的最大帶寬或吞吐量,具體到本文選擇的是一個度量值。

由于次用戶與認知基站的距離不同,可能采用不同的發射功率和調制技術,從而不同次用戶使用相同的頻譜,所獲得帶寬或傳輸速率也不同,用矩陣B描述各次用戶在不同頻段通信時的系統效益。

定義3干擾約束矩陣C。C={cn,k,m|cn,k,m∈{0,1}}N×N×M。其中,cn,k,m=1表示次用戶n和k同時使用頻譜m進行傳輸數據時,將會產生通信干擾。

次用戶與次用戶之間的距離和調制技術等因素,使得多個次用戶使用同一頻譜時,可能會產生通信干擾。用矩陣C描述當前環境中各次用戶使用相同頻譜時的干擾約束情況。

定義4無干擾分配矩陣A。A={an,m|an,m∈{0,1},an,m≤ln,m}N×M。其中,an,m=1表示該時段次用戶n分配到頻譜m。為了保證通信可行性與可靠性,必須保證分配矩陣A與干擾約束矩陣C不能沖突,即:當cn,k,m=1時,對任意n,k≤N,m≤M有an,m+ak,m≤1。

定義5用戶效益值R。R={βn}N×1。其中,βn表示在分配矩陣A下,次用戶n所獲得效益值,計算為

(11)

定義6系統效益函數U(R)。用來評價頻譜分配策略對系統效益影響的函數,其定義為

(12)

基于以上定義,從系統總效益的角度出發,求解無干擾頻譜分配矩陣,使得當前認知無線電系統下用戶所獲得的系統總效益最大,其表達式為

(13)

2.2 基于統計特性的蝙蝠算法的頻譜分配描述

本文提出SCBA算法的認知無線電頻譜分配方案中,每只蝙蝠的位置對應一種頻譜分配方案。因此,頻譜分配問題的最終求解目標即為最大化系統效益的無干擾分配矩陣A。直接編碼A,則其維數為N×M,當網絡中次用戶數N、可用頻譜數M增加時,問題規模隨著維數成指數級增長。由于可用性矩陣L對無干擾分配矩陣A的約束,即ln,m=0時,表示當前通信環境下用戶n不能使用頻譜m,從而頻譜m不能分配給用戶n使用,從而an,m只能為0。因此,文獻[7,17]提出只對矩陣L中元素值為1的位置進行編碼。此時,解的編碼長度D根據矩陣L中非零元素的個數確定,其計算式為

(14)

如圖2所示,在該認知無線電系統中,用戶數N=5、頻譜數M=4,通過頻譜檢測得到可用矩陣L,按照逐行的順序抽取矩陣L中對應位置為1的元素,然后對它們進行編碼,得到解向量x(xi∈{0,1}),其維數為8,優化以后,再按照之前的映射關系將解向量x映射為分配矩陣A。

圖2 解向量與分配矩陣的映射關系Fig.2 Relationship between solution vector and allocation matrix

按照上述編碼方式,隨機的初始化蝙蝠位置(頻譜分配方案),并不一定能滿足定義3的無干擾約束條件。因此,需要對蝙蝠的位置進行干擾約束處理。對任意頻譜m(0≤m

綜上所述,本文提出的SCBA算法的認知無線電頻譜分配流程如下:

步驟2初始化種群xi(i=1,2,…,NP),初始化速度vi、頻率fi及脈沖發生率r。

步驟3干擾約束處理,將解向量xi還原成分配矩陣A,在干擾約束矩陣C中,對所有m(0≤m

步驟4根據式(1)調整頻率,根據式(2)更新蝙蝠的速度。

步驟5產生一個隨機數rand,如果rand>r,則利用平均最好位置指導蝙蝠尋優,按式(9)和式(10)更新蝙蝠位置,否則按式(3)更新位置,并按式(7)和式(8)進行離散化處理。

步驟6按照步驟3,對新解進行干擾約束處理。

步驟7計算蝙蝠適應度值,利用貪婪選擇策略選擇當前較好的蝙蝠進行下一次的迭代,并更新當前最優解。

步驟8若達到算法所設置的最大迭代次數,則算法結束;否則,轉至步驟4。

2.3 算法復雜度分析

SCBA算法的計算時間復雜度即為種群迭代的時間復雜度。在執行種群迭代階段,每只蝙蝠以概率r執行全局搜索,其復雜度為O(r·NP·2D),以概率(1-r)執行局部搜索,執行局部搜索操作的復雜度為O((1-r)·NP·D)),由此可得迭代一次的計算時間復雜度為O(r·NP·2D+(1-r)·NP·D),即O((1+r)NP·D),因此SCBA算法的計算時間復雜度為O((1+r)T·NP·D)。其中,T為算法迭代的最大次數。根據BBA算法流程可得其計算時間復雜度為O(2T·NP·D)。所以，SCBA算法的時間復雜度低于BBA算法的時間復雜度。

SCBA算法的空間復雜度主要包括頻譜分配模型矩陣的存儲和蝙蝠種群位置的存儲。L所需的存儲空間為O(N·M),B的存儲空間為O(N·M),C的復雜度為O(N2·M)。每個蝙蝠位置的存儲空間為O(D)。因此,在圖論模型下SCBA算法的空間復雜度為O(N·M·(N+2)+NP·D),與其他算法的空間復雜度相同。

3 仿真實驗及結果分析

根據文獻[7-8,10,17],GA、BPSO、DABC、多策略離散人工蜂群算法(multi-strategy discrete artificial bee colony, MDABC)都應用于認知無線電頻譜分配,在求解使得系統效益最大化的頻譜分配方案中,MDABC的性能最好,其次分別是DABC、BPSO、GA。為了驗證SCBA算法在認知無線電頻譜分配中的有效性,與BBA和MDABC算法在同一條件下進行仿真測試。

假設認知無線電網絡模型中次用戶的個數為20,可用頻譜數為22,即N=20,M=22。優化問題的維數D由式(14)計算。MDABC算法參數[17]為S=20,T1=[0.08D],U=SD;BBA和SCBA算法的參數:種群大小NP=20,音量A=0.6,脈沖發生率r=0.7；所有算法最大迭代次數為T=500。為了降低算法的偶然性,所有結果為各算法在同一條件下運行30次的平均值。

3.1 幾種智能算法的比較

圖3是3種算法在不同頻譜環境下的系統總效益的平均值對比。該試驗采用了30種不同的L、B、C矩陣,對于每種算法均采用相同的初始值?？梢钥闯?SCBA算法在不同的頻譜環境下都能使系統獲得更大的效益值。

圖4是在一次仿真實驗中,系統效益與迭代次數的關系。從圖中可以看出,SCBA的收斂速度快于MDABC和BBA兩種算法,且在相同迭代次數時,尋找的頻譜分配方案總使得系統獲得更大的效益值。

圖3 不同頻譜環境下的系統效益值Fig.3 Benefit value of system in different spectrum environment

圖4 不同算法下系統效益與迭代次數的關系Fig.4 Relationship between benefit value of system and iteration times under different algorithms

3.2 計算時間分析

圖論模型下的頻譜分配是基于某一短暫時間內頻譜環境參數不變,對頻譜進行分配,使系統效益最大化。以時間為橫軸,效益值為縱軸,BBA、SCBA、MDABC算法在同一頻譜環境下重復30次取平均值,得到平均計算時間與系統效益曲線如圖5所示。

圖5 系統效益與搜索時間的關系Fig.5 Relationship between benefit value and search time

從圖5中可以看出,MDABC在迭代500次所需總時間少于BBA和SCBA,但所得頻譜分配方案使得系統效益小于SCBA,且SCBA在0.8 s左右就收斂了。當使得系統效益相同時,SCBA所需時間更少。

3.3 系統效益隨用戶數和可用頻譜數變化的關系

在認知無線電系統中,由于次用戶數和可用頻譜數受到主用戶頻譜使用情況、地理位置、發射功率大小等因素的影響和限制,其在不斷地變化,從而影響整個系統的效益。圖6為用戶數固定為20,頻譜數M從15變化到40時,系統平均效益(系統總效益與用戶數之比)與可用頻譜數之間的關系,從圖中可以看出,當可用頻譜數增加時,系統平均效益也增加,但是SCBA獲得的用戶平均效益略高于MDABC。

圖6 系統平均效益與可用頻譜數變化的關系Fig.6 Relationship between the average benefit value of system and the number of available spectrum

圖7為頻譜數M固定為30,用戶數N從15到40變化時系統平均效益與用戶數的關系仿真結果。從圖中可以看出,用戶數增加后,相互干擾的概率增加,用戶獲得的平均效益逐漸減小。但是,SCBA獲得的系統平均效益高于BBA和MDABC。

圖7 系統平均效益與用戶數變化的關系Fig.7 Relationship between the average benefit value of system and the number of users

4 結 論

本文提出了改進蝙蝠算法的認知無線電頻譜分配方法。①將蝙蝠算法的選擇策略改為貪婪選擇,增強了蝙蝠算法在當前位置的開發能力,提高了解的精確性。②根據蝙蝠種群中位置的統計特性,即,平均最好位置反映了所有蝙蝠在該位置上取0或1的趨勢,根據這一趨勢,在下一次迭代中產生更好的解,加快算法收斂速度。③在局部搜索時,直接在離散域操作,減少實數到二進制的映射,從而縮短搜索時間。通過仿真比較了BBA、SCBA和MDABC在頻譜分配中的應用,仿真結果表明,SCBA獲得的頻譜分配方案與BBA和MDABC相比,系統效益更大,且所需時間更少。

[1] AKYILDIZ I F, LEE W, 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] LIU Q, NIU H, XU W, et al. A service-oriented spectrum allocation algorithm using enhanced PSO for cognitive wireless networks[J]. Computer Networks, 2014, 74:81-91.

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

[4] LI Z P, LI B C, ZHU Y F. Designing truthful spectrum auctions for multi-hop secondary networks[J]. IEEE Trans.on Mobile Computing, 2015, 14(2): 316-327.

[5] ZAYEN B, HAYAR A, NOUBIR G. Game theory-based resource management strategy for cognitive radio networks[J]. Multimedia Tools and Applications, 2014, 70(3): 2063-2083.

[6] 高洪元,曹金龍. 認知無線電中的量子蛙跳頻譜分配[J]. 應用科學學報, 2014, 32(1): 19-26.

GAO H Y, CAO J L. Quantum-inspired shuffled frog leaping algorithm for spectrum allocation in cognitive radio[J]. Journal of Applied Sciences, 2014, 32(1):19-26.

[7] 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.

[8] 趙知勁, 徐世宇, 鄭仕鏈, 等. 基于二進制粒子群算法的認知無線電決策引擎[J]. 物理學報, 2009, 58(7):5118-5125.

ZHAO Z J, XU S Y, ZHENG S L, et al. Cognitive radio decision engine based on binary particle swarm optimization[J]. Acta Physica Sinica, 2009, 58(7):5118-5125.

[9] GHASEMI A, MASNADI-SHIRAZI M A, BIGUESH M, et al. Spectrum allocation based on artificial bee colony in cognitive radio networks[C]∥Proc.of the 6th International Symposium on Telecommunications, 2012:182-187.

[10] 李鑫濱,劉磊,馬鍇. 基于離散人工蜂群算法的認知無線電頻譜分配[J]. 系統工程與電子技術. 2012, 34(10): 2136-2141.

LI X B, LIU L, MA K. Cognitive radio spectrum allocation based on discrete artificial bee colony algorithm[J]. Systems Engineering and Electronics, 2012, 34(10):2136-2141.

[11] YANG X S. A new metaheuristic bat-inspired algorithm[M]. Nature Inspired Cooperative Strategies for Optimization. Berlin Heidelberg: Springer, 2010:65-74.

[12] YE Z, WANG M, LIU W, et al. Fuzzy entropy based optimal thresholding using bat algorithm[J]. Applied Soft Computing. 2015, 31(0): 381-395.

[13] YANG X, GANDOMI A. Bat algorithm: a novel approach for global engineering optimization[J]. Engineering Computations, 2012, 29(5): 464-483.

[14] MIRJALILI S, MIRJALILI S M, YANG X S. Binary bat algorithm[J]. Neural Computing and Applications, 2014, 25(3):663-681.

[15] YILMAZ S, UGUR KUCUKSILLE E, CENGIZ Y. Modified bat algorithm[J]. Elektronika Ir Elektrotechnika, 2014, 20(2):71-78.

[16] SUN J, FANG W, PALADE V, et al. Quantum-behaved particle swarm optimization with Gaussian distributed local attractor point[J].Applied Mathematics and Computation, 2011,218(7): 3763-3775.

[17] 朱冰蓮,朱方方,段青言,等.采用多策略離散人工蜂群的改進頻譜分配算法[J].西安交通大學學報,2016,50(2):20-25.

ZHU B L, ZHU F F, DUAN Q Y, et al. An improved spectrum allocation algorithm using multi-strategy discrete artificial bee colony technology[J].Journal of Xi’an Jiaotong University, 2016,50(2):20-251.