基于布谷鳥搜索算法的認知車載網(wǎng)絡(luò)頻譜分配方法

劉彩麗，肖海林

(桂林電子科技大學 信息與通信學院，廣西 桂林　541004)

?

基于布谷鳥搜索算法的認知車載網(wǎng)絡(luò)頻譜分配方法

劉彩麗，肖海林

(桂林電子科技大學 信息與通信學院，廣西 桂林541004)

針對認知車載網(wǎng)絡(luò)頻譜分配中網(wǎng)絡(luò)吞吐量低的問題，提出一種基于布谷鳥搜索算法的頻譜分配方法。該方法考慮了認知車載網(wǎng)絡(luò)中授權(quán)頻段可用時長的差異性，將最大化網(wǎng)絡(luò)吞吐量轉(zhuǎn)化為求最大化可用時長內(nèi)認知車載用戶成功完成的總數(shù)據(jù)量，建立目標函數(shù)，并將頻譜分配變量映射為布谷鳥鳥巢位置，采用布谷鳥搜索算法求解。數(shù)值分析表明，基于布谷鳥搜索算法的頻譜分配方法所獲得的網(wǎng)絡(luò)吞吐量高于基于遺傳算法的頻譜分配。

認知車載網(wǎng)絡(luò)；布谷鳥搜索算法；頻譜分配；吞吐量

隨著車輛道路安全服務(wù)需求的不斷增長，車載自組織網(wǎng)絡(luò)的可用頻譜資源變得尤為緊缺，而認知無線電能解決這一問題[1]。認知車載網(wǎng)絡(luò)是將認知無線電(cognitive radio，簡稱CR)技術(shù)應(yīng)用到車載自組織網(wǎng)絡(luò)(vehicular ad hoc network，簡稱VANET)的新型車載網(wǎng)絡(luò)[2]。在認知車載網(wǎng)絡(luò)(CR-VANET)中，認知車載用戶可以“伺機”接入空閑授權(quán)頻譜，以緩解車載網(wǎng)絡(luò)頻譜資源的匱乏，提高頻譜利用率。

頻譜分配是認知無線電的關(guān)鍵技術(shù)之一[3]，近年來國內(nèi)外學者對其進行了大量研究。文獻[4]把頻譜分配問題抽象成圖著色問題，提出了基于圖論著色理論的頻譜分配算法，但該算法存在不公平性，且時間開銷較大。文獻[5]以實現(xiàn)最大化網(wǎng)絡(luò)效益為目標，將頻譜分配問題歸化為優(yōu)化問題，采用遺傳算法(genetic algorithm，簡稱GA)求解，減少了時間開銷。文獻[6]提出了基于遺傳算法的多目標頻譜分配方法，該方法能使認知用戶在頻譜分配過程中實現(xiàn)最大網(wǎng)絡(luò)效益的同時獲得最大比例公平，比圖論著色理論的頻譜分配更具優(yōu)越性，但遺傳算法難以克服易陷入局部最優(yōu)的缺點。

上述方法所應(yīng)用的認知無線網(wǎng)絡(luò)均考慮的是靜態(tài)的認知用戶，并不適用于具有動態(tài)認知用戶的車載網(wǎng)絡(luò)。文獻[7]將認知用戶實體化為高速行駛的車輛，根據(jù)實際的交通狀況模擬網(wǎng)絡(luò)拓撲隨時間快速變化的車載網(wǎng)絡(luò)場景，運用基于協(xié)作最大化帶寬總和算法進行頻譜分配，實現(xiàn)網(wǎng)絡(luò)吞吐量的最大化。文獻[8]研究了認知車載網(wǎng)絡(luò)中基于QoS保障的頻譜共享，將多認知小區(qū)間的頻譜分配構(gòu)建為基于廣義納什討價還價解模型。文獻[9]針對認知車載網(wǎng)絡(luò)中授權(quán)頻段的動態(tài)特性，采用基于部分可觀測馬爾科夫決策過程的機會式頻譜接入，認知車載用戶選擇空閑概率最大的授權(quán)頻段進行感知及接入，使自身吞吐量最大化。文獻[10]根據(jù)車載用戶的速度和行駛方向建立一種頻譜資源分配框架，將頻譜分配問題轉(zhuǎn)化為最大化網(wǎng)絡(luò)可用頻譜資源利用率的優(yōu)化問題，并采用分支界定算法求解，以降低復雜度，但其未考慮由認知車載的移動而導致的授權(quán)頻段在空間上存在的空閑。文獻[11]研究了城市場景下認知車載網(wǎng)絡(luò)中授權(quán)頻譜在時間和空間上的空閑持續(xù)時長分布，根據(jù)各個授權(quán)頻段不同的空閑時長，提出了一種基于博弈論的頻譜接入方法，但該方法未解決多個車載用戶接入同一授權(quán)頻段可能造成的干擾問題。

為此，以最大化網(wǎng)絡(luò)吞吐量為準則，提出一種基于布谷鳥搜索算法的頻譜分配方法，消減車載用戶間的同頻干擾。

1　系統(tǒng)模型

1.1認知車載網(wǎng)絡(luò)模型

考慮的CR-VANET模型如圖1所示[10-12]。網(wǎng)絡(luò)包括K個主用戶、M個認知車載用戶和若干個路邊單元。其中，主用戶按泊松點過程隨機分布。網(wǎng)絡(luò)共有N(N≥K)個授權(quán)頻段，每一個授權(quán)頻段對應(yīng)一個信道。認知車載用戶已知每個授權(quán)頻段上的主用戶平均密度和主用戶的頻譜使用統(tǒng)計特性，且工作在同一頻段的主用戶具有相同的系統(tǒng)特性和相同的頻譜使用統(tǒng)計特性，如頻譜占用和空閑的持續(xù)時間。假設(shè)認知車載用戶已完成頻譜感知獲得可用頻譜，并將相關(guān)信息發(fā)送給路邊單元，由路邊單元進行頻譜分配。

圖1　認知車載網(wǎng)絡(luò)模型Fig.1　CR-VANET model

在認知車載網(wǎng)絡(luò)中，由于車載的移動性，認知車載用戶的狀態(tài)可分為3種：1)處于空閑頻段的覆蓋范圍之內(nèi)；2)處于被占用頻段的覆蓋范圍之內(nèi)；3)處于被占用頻段的覆蓋范圍之外。顯然，授權(quán)頻段是否空閑不僅取決于是否被主用戶占用，還因車載進入或離開主用戶的通信覆蓋范圍而改變。因此，對于認知車載，授權(quán)頻段存在時間和空間上的空閑[11]。

1.2頻譜可用性建模

主用戶的頻譜使用統(tǒng)計特性為主用戶占用和離開授權(quán)頻段的轉(zhuǎn)換過程，主用戶占用某一頻段進行通信時，處于該主用戶覆蓋范圍之內(nèi)的認知車載用戶不能使用該頻段，以避免對主用戶造成干擾。根據(jù)認知網(wǎng)絡(luò)中廣泛使用的頻譜使用統(tǒng)計模型，主用戶占用和離開授權(quán)頻段i的持續(xù)時間服從參數(shù)為λbusy,i、λidle,i的指數(shù)分布：

Tidle,i～exp(λidle,i)，Tbusy,i～exp(λbusy,i)。

(1)

為避免對主用戶造成干擾，認知車載用戶只有當授權(quán)頻段在時間或空間上空閑時，才可以使用，否則，不可使用。因此，對于認知車載用戶，授權(quán)頻段的可用性綜合為2種狀態(tài)：可用(OFF)和不可用(ON)。2種狀態(tài)轉(zhuǎn)換如下：

1)ON→OFF。認知車載用戶駛出正占用授權(quán)頻譜的主用戶的保護區(qū)域或主用戶停止占用。

2)OFF→ON。認知車載用戶駛?cè)胝加檬跈?quán)頻譜的主用戶的保護區(qū)域或主用戶開始占用。

授權(quán)頻段“OFF”狀態(tài)和“ON”狀態(tài)之間的轉(zhuǎn)換滿足馬爾科夫過程，因此，授權(quán)頻段的可用性可建模為一個連續(xù)時間馬爾科夫鏈。授權(quán)頻段i的可用狀態(tài)持續(xù)時長服從參數(shù)為λOFF,i的指數(shù)分布[12]：

TOFF,i～exp(λOFF,i)。

(2)

其分布參數(shù)為：

(3)

假設(shè)授權(quán)頻段i的可用時長為TOFF,i，當認知車載用戶接入到頻段i時，頻段i的可用時長已經(jīng)持續(xù)了時間t，則授權(quán)頻段i的剩余可用時長不小于T(T<)的概率為：

(4)

顯然，Pi(T)越大，認知車載用戶在[t，t+T]時間段內(nèi)能夠成功完成數(shù)據(jù)傳輸?shù)母怕试酱螅瑒t越有利于車載用戶進行數(shù)據(jù)傳輸。

1.3頻譜分配優(yōu)化問題建模

認知車載用戶m在頻段i上的傳輸速率為：

(5)

其中：w為每個授權(quán)頻段的帶寬；ψ為認知車載用戶的發(fā)射功率；hm,i為認知車載用戶m在頻段i上的信道增益；σ2為噪聲方差；i∈1,2,…,N，m∈1,2,…,M。

當認知車載用戶在t時刻接入頻段i時，只有頻段i的可用時長至少達到T，其在[t，t+T]時間內(nèi)的數(shù)據(jù)傳輸才不會中斷。因此，綜合考慮授權(quán)頻段的可用時長和傳輸速率，在時長T內(nèi)，認知車載用戶每次接入頻段能夠成功完成的數(shù)據(jù)量可表示為：

(6)

其中：xm,i為0-1頻譜分配變量，其為1時表示頻段i分配給了認知車載用戶m，為0時表示頻段i未分配給用戶m；Pi(T)為授權(quán)頻段i的可用時長不小于T的概率。

(7)

其中：Rm、Rk分別為認知車載用戶m、k的傳輸半徑；dm,k為認知車載用戶m、k之間的距離。

只有當頻段i為認知車載用戶m的可用頻段時，該頻段才可被分配給認知車載用戶m，因而約束條件(8)表明，若頻段i不為認知車載用戶m的可用頻段，則xm,i=0。此外，采用認知車載用戶之間的地理距離和各自的傳輸半徑來判斷兩者同時使用頻段i是否產(chǎn)生干擾。約束條件(9)表明，當認知車載用戶m與認知車載用戶k的距離小于兩者傳輸半徑之和時，只能將頻段i分配給這2個用戶中的一個。

上述約束優(yōu)化問題為非線性0-1規(guī)劃問題，此類問題屬于NP難問題[14]，直接進行求解較為困難，因此，采用布谷鳥搜索算法對該問題進行求解。

2　基于布谷鳥算法的頻譜分配方法

2.1布谷鳥搜索算法

布谷鳥搜索(cuckoosearch，簡稱CS)是一種源于自然界中布谷鳥孵育寄生行為和Lévy飛行搜索原理開發(fā)的一種新型智能算法，其探索解空間的性能高，能靈活地跳出局部極值，并且結(jié)構(gòu)十分簡單，控制參數(shù)較少，參數(shù)的調(diào)整和設(shè)置方便，易于實施，在非線性規(guī)劃問題求解方面得到廣泛應(yīng)用[15-17]。CS算法的個體更新方式有2種：

1)通過Lévy飛行。根據(jù)Lévy飛行模式，布谷鳥尋窩路徑和位置的更新公式為：

(10)

2)通過一個固定的發(fā)現(xiàn)概率ε。用一個隨機數(shù)r與發(fā)現(xiàn)概率ε對比，以確定是否更新鳥巢位置，更新公式為：

(11)

在實際的優(yōu)化中，鳥巢位置用向量Xj=[xj,1,xj,2,…,xj,d]表示所有優(yōu)化變量的d維有效取值空間，鳥巢位置的適應(yīng)度值則代表優(yōu)化變量取不同值所對應(yīng)的目標函數(shù)[16]。

2.2種群編碼

其中：Xj為第j個鳥巢位置，其對應(yīng)一種可能的頻譜分配策略，j∈1,2,…,P；P為種群數(shù)。

由于頻譜分配變量的0-1特性，需采用二進制CS算法。在二進制CS算法中，所求解通過保留基本的CS算法中的更新公式對更新位置進行二進制編碼，即鳥巢位置矢量仍屬于實屬空間，而所求解屬于二進制空間[17]。鳥巢位置進行二進制編碼的公式為：

(12)

基于CS算法的頻譜分配步驟為：

1)根據(jù)給定的可用頻譜矩陣確定優(yōu)化維數(shù)D，并設(shè)定最大迭代次數(shù)。

3)計算每個鳥巢位置的適應(yīng)度值，選出最大的適應(yīng)度值，并記錄其對應(yīng)的鳥巢位置Xbest，Xbest即為當前最優(yōu)鳥巢位置。

5)按照式(11)更新鳥巢位置，計算每個鳥巢位置的適應(yīng)度值，再與步驟4)中的每個鳥巢位置對應(yīng)的適應(yīng)度值比較，保留較大適應(yīng)度值對應(yīng)的鳥巢位置，記錄此時最大的適應(yīng)度值對應(yīng)的鳥巢位置X″best。

6)判斷是否達到預(yù)先設(shè)定的最大迭代次數(shù)。若是，則輸出X″best，終止迭代；否則，迭代次數(shù)加1，返回至步驟4)，繼續(xù)迭代。

3　仿真實驗

仿真實驗中，可用頻譜矩陣L和車載用戶間的距離按照文獻[4]產(chǎn)生，主用戶保護半徑Ri為2 km，車載用戶平均速度為4 m/s，發(fā)射功率ψ為50 mW；頻段帶寬w為1 kHz，參數(shù)λidle,i和穩(wěn)態(tài)概率ωbusy,i均為[0,1]上隨機數(shù)，信道增益hm,i服從均值為1的瑞利分布，每個頻段上的主用戶平均密度ρp,i均為1 km-2，噪聲功率σ2為10-5W，時長T為1 s。最大迭代次數(shù)為150，ε=0.25，GA算法中交叉概率為0.8，變異概率為0.01。

圖2為N=8、M=10時本頻譜分配方法的收斂曲線。從圖2可看出，種群數(shù)為P=20時，由于種群數(shù)多樣性偏低，算法發(fā)生早熟現(xiàn)象，隨著種群數(shù)的增大，本方法收斂得更快，在P=60和P=100時，體現(xiàn)出良好的收斂性能。

圖2　N=8、M=10時本方法的收斂曲線Fig.2　The convergence curve of the proposed method when N=8 and M=10

當N=18、M=20時，本方法的收斂曲線如圖3所示。從圖3可看出，當用戶和頻譜數(shù)量增大后，方法仍具有較好的收斂性能，表明了本方法的優(yōu)越性。

圖3　N=18、M=20時本方法收斂曲線Fig.3　The convergence curve of the proposed method when N=18 and M=20

圖4為P=20、N=8、M=10時進行30次相同參數(shù)的仿真結(jié)果。從圖4可看出，基于CS算法比基于GA算法的頻譜分配方法所得到的網(wǎng)絡(luò)吞吐量高。

圖4　P=20、N=8、M=10時不同實驗次數(shù)下的吞吐量Fig.4　The throughput in different numbers of test when P=20, N=8 and M=10

圖5為P=20、N=18、M=20時進行30次相同參數(shù)的仿真結(jié)果。從圖5可看出，本方法所得的網(wǎng)絡(luò)吞吐量均高于基于GA算法的頻譜分配方法。

圖5　P=20、N=18、M=20時不同實驗次數(shù)下的吞吐量Fig.5　The throughput in different numbers of test when P=20, N=18 and M=20

4　結(jié)束語

針對認知車載網(wǎng)絡(luò)中的可用頻譜資源，提出基于布谷鳥搜素算法的頻譜分配方法。該方法以最大化網(wǎng)絡(luò)吞吐量作為頻譜分配的優(yōu)化目標函數(shù)，實現(xiàn)可用頻譜在認知車載用戶間分配時獲得最大網(wǎng)絡(luò)吞吐量。仿真結(jié)果表明，本方法使網(wǎng)絡(luò)吞吐量得到提高。

[1]MITOLA J I,MAGUIRE G Q.Cognitive radio:making software radios more personal[J].IEEE Personal Communications,1999,6(4):13-18.

[2]FELICE M D,DOOST-MOHAMMADY R,CHOWDHURY K R,et al.Smart radios for smart vehicles:cognitive vehicular networks[J].IEEE Vehicular Technology Magazine,2012,7(2):26-33.

[3]DING L,MELODIA T,BATALAMA S N,et al.Cross-layer routing and dynamic spectrum allocation in cognitive radio ad hoc networks[J].IEEE Transactions on Vehicular Technology,2010,59(4):1969-1979.

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

[5]WEN K,FU L,LI X.Genetic Algorithm Based Spectrum Allocation for Cognitive Radio Networks[M].Germany:Pringer Berlin Heidelberg,2011:693-700.

[6]姚再英，黃玉清.基于多目標遺傳算法的認知無線電頻譜分配[J].西南科技大學學報，2010,25(4):82-86.

[7]張超，郭愛煌，楊曦，等.基于車載通信網(wǎng)絡(luò)的認知無線電信道分配技術(shù)的研究[J].電子測量技術(shù)，2009,32(8):49-51.

[8]ZHANG Jianfeng.Cooperative spectrum allocation with QoS support in cognitive cooperative vehicular ad hoc networks[J].Wireless Communication Over Zigbee for Automotive Inclination Measurement China Communications,2014,11(10):49-59.

[9]張雪飛，章國安，季彥呈.CVANET中基于POMDP模型的頻譜接入算法[J].電信科學，2014(9):111-115.

[10]JIANG T,WANG Z,ZHANG L,et al.Efficient spectrum utilization on TV band for cognitive radio based high speed vehicle network[J].IEEE Transactions on Wireless Communications,2014,13(10):5319-5329.

[11]CHENG N,ZHANG N,LU N,et al.Opportunistic spectrum access for CR-VANETs:a game-theoretic approach[J].IEEE Transactions on Vehicular Technology,2014,63(1):237-251.

[12]MIN A W,KIM K H,SINGH J P,et al.Opportunistic spectrum access for mobile cognitive radios[C]//2011 Proceedings IEEE INFOCOM,2011:2993-3001.

[13]GUPTA P,KUMAR P R.The capacity of wireless networks[J].IEEE Transactions on Information Theory,2000,46(2):388-404.

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

[15]EL-FERGANY A A,ABDELAZIZ A Y.Capacitor allocations in radial distribution networks using cuckoo search algorithm[J].IET Generation Transmission and Distribution,2014,8(2):223-232.

[16]KHODIER M.Optimisation of antenna arrays using the cuckoo search algorithm[J].IET Microwaves Antennas and Propagation,2013,7(6):458-464.

[17]BHATTACHARJEE K K,SARMAH S P.A binary cuckoo search algorithm for knapsack problems[C]//2015 International Conference on IEEE Industrial Engineering and Operations Management,2015:1-5.

編輯：翁史振

Spectrum allocation based on cuckoo search algorithm in cognitive vehicular network

LIU Caili, XIAO Hailin

(School of Information and Communication Engineering, Guilin University of Electronic Technology, Guilin 541004, China)

To improve the network throughput in spectrum allocation of cognitive vehicular network, a spectrum allocation method based on cuckoo search algorithm is proposed. The method has considered the diversity of authorized spectrum available time, formulates the network throughput maximization as total data maximization problem of cognitive vehicular users successfully transmit in the time slot to establish objective function, and uses cuckoo search algorithm to solve it by mapping the spectrum allocation variables to the position of cuckoo’s nest. Numerical simulation shows that compared with the genetic algorithm, the network throughput is improved.

cognitive vehicular network; cuckoo search algorithm; spectrum allocation; throughput

2016-01-05

廣西自然科學基金重點項目(2011GXNSFD018028)；廣西自然科學基金(2013GXNSFFA019004)

肖海林(1976-)，男，湖北黃岡人，教授，博士。研究方向為智能天線、MIMO移動通信系統(tǒng)、協(xié)同通信技術(shù)。E-mail：xhl_xiaohailin@163.com

TN929.5

A

1673-808X(2016)03-0173-05

引文格式： 劉彩麗，肖海林.基于布谷鳥搜索算法的認知車載網(wǎng)絡(luò)頻譜分配方法[J].桂林電子科技大學學報，2016,36(3):173-177.