基于認(rèn)知的拓?fù)渖膳c信道分配算法

劉玉濤

(通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050081)

基于認(rèn)知的拓?fù)渖膳c信道分配算法

劉玉濤

(通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050081)

認(rèn)知無線電技術(shù)通過感知周圍環(huán)境，自適應(yīng)地調(diào)整拓?fù)浣Y(jié)構(gòu)和通信參數(shù)，可以有效地提高通信性能。由于環(huán)境的變化，尤其授權(quán)用戶工作狀態(tài)的變化，認(rèn)知無線電網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和信道分配結(jié)果也動態(tài)變化。主要基于圖論模型研究最大化瓶頸鏈路吞吐率目標(biāo)下的拓?fù)渖膳c信道分配問題。基于KM算法提出了干線節(jié)點(diǎn)和剩余節(jié)點(diǎn)的信道分配方法，仿真分析表明，可用信道比例較低時(shí)，EC、PCA、MDS、LTSA和DM方法可以在一定程度上提高組網(wǎng)的成功率。

認(rèn)知無線電；拓?fù)洌恍诺婪峙洌蛔畲蠡款i鏈路吞吐率

0 引言

認(rèn)知無線電具有在不影響授權(quán)用戶的前提下智能地利用大量頻譜空穴，實(shí)現(xiàn)隨時(shí)隨地、高可靠性通信的潛能[1]。文獻(xiàn)[2-4]論述了認(rèn)知無線電可以作為解決無線頻譜低利用率問題的最佳方案之一。由于電磁環(huán)境、地理環(huán)境的變化以及業(yè)務(wù)需求的多樣性，認(rèn)知無線電用戶通信時(shí)的可用信道以及相應(yīng)的發(fā)射功率、調(diào)制方式、編碼方式等通信參數(shù)都是動態(tài)變化的[5]。同時(shí)，由于通信需求的變化、認(rèn)知無線電用戶的移動以及授權(quán)用戶即“外界干擾”的動態(tài)性，認(rèn)知無線電網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)也是動態(tài)變化的[6]。

本文考慮的認(rèn)知無線電網(wǎng)絡(luò)存在3種結(jié)構(gòu)：星狀網(wǎng)、鏈狀網(wǎng)和樹狀網(wǎng)，其中，星狀網(wǎng)和鏈狀網(wǎng)均可作為特殊的樹狀網(wǎng)[7]。根據(jù)認(rèn)知無線電網(wǎng)絡(luò)的需求，拓?fù)渖珊托诺婪峙浼夹g(shù)一般基于3種不同的優(yōu)化原則：最大化網(wǎng)絡(luò)總吞吐率、最大化瓶頸鏈路吞吐率和最大化指定鏈路吞吐率[8]。本文主要研究樹狀網(wǎng)中基于最大化瓶頸鏈路吞吐率的拓?fù)渖膳c信道分配算法，并選擇合適的降維方法提高組網(wǎng)成功率。

文獻(xiàn)[9-12]論述了在信道分配過程中，通過引入圖論和運(yùn)籌學(xué)相關(guān)算法，可以將節(jié)點(diǎn)分為2類：指定鏈路上的節(jié)點(diǎn)和指定鏈路外的節(jié)點(diǎn)(即剩余節(jié)點(diǎn))。對于指定鏈路上的節(jié)點(diǎn)，可以利用KM算法進(jìn)行信道分配[13]；對于剩余節(jié)點(diǎn)，可以利用剩余節(jié)點(diǎn)最佳接入方法對其進(jìn)行信道分配[14]。

1 系統(tǒng)模型與參數(shù)定義

假設(shè)認(rèn)知無線電網(wǎng)絡(luò)中的節(jié)點(diǎn)具有A、B兩個獨(dú)立工作的通信模塊，且網(wǎng)絡(luò)中的任一節(jié)點(diǎn)可以使用A模塊與下級節(jié)點(diǎn)進(jìn)行通信，使用B模塊與上級節(jié)點(diǎn)進(jìn)行通信。由于節(jié)點(diǎn)的A、B兩個模塊使用的信道不同，節(jié)點(diǎn)間的通信互不干擾，并可以最大化利用感知到的頻譜資源，節(jié)點(diǎn)間組成樹狀網(wǎng)時(shí)的網(wǎng)絡(luò)模型如圖1所示。假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為16個(Ni,i=1,2,…,16)，可選信道數(shù)為150個(fi,i=1,2,…,150)，信道對應(yīng)的速率等級為5級(Li,i=0,1,…,4)，L4表示信道質(zhì)量最好，L0表示信道質(zhì)量最差且認(rèn)知用戶不能在該信道進(jìn)行正常通信。

圖1 樹狀網(wǎng)網(wǎng)絡(luò)模型

一個樹狀組網(wǎng)示意圖如圖2所示。

圖2 網(wǎng)絡(luò)拓?fù)鋵哟位疽?/p>

根節(jié)點(diǎn)為N4，根節(jié)點(diǎn)使用信道f98與節(jié)點(diǎn)N1、N3、N10和N12進(jìn)行通信。由于節(jié)點(diǎn)所處位置不同，其信道條件也不盡相同，節(jié)點(diǎn)N1、N3和N10使用第L2檔通信速率，而N12只能使用L1檔通信速率。N1作為中繼節(jié)點(diǎn)，還需要與N7和N17進(jìn)行通信，此時(shí)鏈路使用信道f80，且與N7、N17的通信速率分別是L4和L3。圖2所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)層次化地表示了節(jié)點(diǎn)在鏈路中的位置以及使用的頻點(diǎn)和通信速率。

2 信道分配算法

2.1 KM算法

文獻(xiàn)[15-17]論述了KM算法是一種基于二分圖的算法，可以求解帶權(quán)二分圖的最優(yōu)匹配也就是求權(quán)值最大的匹配。KM算法求解二分圖G的最優(yōu)匹配算法核心是反復(fù)修改頂點(diǎn)標(biāo)記，選第二長邊，使新的相等子圖的最大匹配逐漸擴(kuò)大，直至最終出現(xiàn)相等子圖的完備匹配，也就是二分圖G的最優(yōu)匹配[18]。

設(shè)G=(V,E)為賦權(quán)二分圖，L是其一個初始可行頂點(diǎn)標(biāo)記，取

(1)

設(shè)M是圖G的相等子集GL的一個匹配，KM算法的具體步驟如下：

① 若X的每個點(diǎn)都是M的飽和點(diǎn)，則M是最佳匹配；否則，取M的非飽和點(diǎn)u∈X，令S=u，T=?轉(zhuǎn)向步驟②。

② 記NLS=v|u∈S,uv∈EL，若NLS=T，則GL沒有完美匹配，轉(zhuǎn)向步驟③；否則，轉(zhuǎn)向步驟④。

③ 調(diào)整可行頂點(diǎn)標(biāo)記，計(jì)算

aL= min{Lx+Ly-Fxy|，x∈S,y∈YT}。

(2)

由此得新的可行頂點(diǎn)標(biāo)記為：

(3)

令L=H，GL=GH，重新給出GL的一個匹配M，轉(zhuǎn)向步驟①。

④ 取y∈NLST，若y是M的飽和點(diǎn)，轉(zhuǎn)向步驟⑤；否則，轉(zhuǎn)向步驟⑥。

⑤ 設(shè)xy∈M，則令S=S∪x，T=T∪y，轉(zhuǎn)向步驟②。

⑥ 在GL中的u,y一路是M-增廣路，記為P，并令M=M⊕P，轉(zhuǎn)向步驟①。

針對最大化瓶頸鏈路吞吐率問題，需要找到一種分配方式，使得主鏈各條鏈路吞吐率最大化。同時(shí)，盡可能使支鏈節(jié)點(diǎn)得到相對較高的傳輸吞吐率。將主鏈各條鏈路作為X集合，每條鏈路可使用的信道作為Y集合，這樣便得到了一個二分圖。為了應(yīng)用KM算法，可以添加一個0矩陣，使得X=Y，從而滿足KM算法的輸入條件。

2.2 剩余節(jié)點(diǎn)接入算法

對于瓶頸鏈路上的節(jié)點(diǎn)，利用KM算法確定信道之后，可能存在一些節(jié)點(diǎn)沒有接入到網(wǎng)絡(luò)中，需要按某種規(guī)則將剩余節(jié)點(diǎn)接入網(wǎng)絡(luò)，這里考慮使用廣度優(yōu)先組網(wǎng)算法進(jìn)行最優(yōu)化組網(wǎng)，從而實(shí)現(xiàn)剩余節(jié)點(diǎn)的接入。對瓶頸鏈路的向上延長是指將現(xiàn)有網(wǎng)絡(luò)的根節(jié)點(diǎn)作為子節(jié)點(diǎn)，在剩余節(jié)點(diǎn)中搜尋其父節(jié)點(diǎn)并加入網(wǎng)絡(luò)中；對瓶頸鏈路的向下延長是指將現(xiàn)有網(wǎng)絡(luò)的葉子節(jié)點(diǎn)作為父節(jié)點(diǎn)，在剩余節(jié)點(diǎn)中搜尋其子節(jié)點(diǎn)并加入網(wǎng)絡(luò)中。在延長瓶頸鏈路的同時(shí)，要選擇最佳的接入節(jié)點(diǎn)和頻點(diǎn)，選擇原則是每一次延長鏈路都要盡可能多地將剩余節(jié)點(diǎn)接入網(wǎng)絡(luò)。算法流程如圖3所示。

圖3 剩余節(jié)點(diǎn)接入流程

3 仿真分析

3.1 參數(shù)設(shè)置

在仿真中將可用鏈路比例(可用鏈路數(shù)量/鏈路總數(shù))與可用信道比例(可用信道數(shù)量/信道總數(shù))分別作為輸入?yún)?shù)，對每種組合進(jìn)行100次獨(dú)立仿真實(shí)驗(yàn)。為達(dá)到最佳仿真效果，每次仿真都對信道列表進(jìn)行初始化，盡量降低仿真之間的相關(guān)性。仿真的目的是選擇合適的降維算法，考慮的降維算法包含以下幾種：EC算法、EC-Advanced算法、PCA算法、LDA算法、MDS算法、Isomap算法、Kernel PCA算法、GDA算法、Diffusion maps算法、LTSA算法、LLTSA算法和FDA算法。

3.2 仿真結(jié)果分析

可用鏈路比例為0.8時(shí)，組網(wǎng)成功率在信道可用比例變化時(shí)的1 000次仿真的統(tǒng)計(jì)結(jié)果如圖4所示。由圖4可知，隨著可用信道數(shù)量的增加，部分算法表現(xiàn)不夠穩(wěn)定，比如K-PCA，當(dāng)信道可用比例達(dá)到0.25后，其組網(wǎng)成功率明顯下降。與K-PCA類似的是LTSA算法，在信道可用比例達(dá)到0.25后，其組網(wǎng)成功率下降，不適合于高信道可用比例下的組網(wǎng)。

圖4 組網(wǎng)成功率隨信道可用比例變化仿真結(jié)果

下面在低信道比例(0.1)條件下，繼續(xù)對算法進(jìn)行統(tǒng)計(jì)分析。組網(wǎng)成功率在鏈路可用比例變化時(shí)的1 000次仿真的統(tǒng)計(jì)結(jié)果如圖5所示。由于K-PCA算法效果較差，這里只針對其余13種映射算法進(jìn)行了仿真。由圖5可知，效果較好的5種映射算法分別為EC、PCA、MDS、LTSA和DM。

圖5 組網(wǎng)成功率隨鏈路可用比例變化仿真結(jié)果

4 結(jié)束語

本文主要研究基于認(rèn)知的拓?fù)渖膳c信道分配問題。由于KM算法是一種逐漸接近最優(yōu)匹配的二分圖方法，可以有效地解決認(rèn)知用戶間的信道分配問題，因此本文以KM算法為基礎(chǔ)，提出了最大化瓶頸鏈路吞吐率目標(biāo)下的干線節(jié)點(diǎn)和剩余節(jié)點(diǎn)的信道分配算法。由于認(rèn)知無線電用戶是次要用戶，需要伺機(jī)接入授權(quán)用戶空閑的頻譜，因此信道可用比例較低。仿真分析表明，在低信道可用比例條件下，EC、PCA、MDS、LTSA和DM等降維算法能夠獲得較高的組網(wǎng)成功率。

[1] 宋志群.認(rèn)知無線電技術(shù)及應(yīng)用[J].無線電通信技術(shù),2012,38(5):1-6.

[2] 張瑩,滕偉,韓維佳,等.認(rèn)知無線電頻譜感知技術(shù)綜述[J].無線電通信技術(shù),2015,41(3):12-16.

[3] 張平,李建武,馮志勇,等.認(rèn)知無線網(wǎng)絡(luò)架構(gòu)與關(guān)鍵技術(shù)研究[J].無線電通信技術(shù),2014,40(3):1-5.

[4] 馬恒.認(rèn)知無線電中頻譜檢測技術(shù)研究[J].無線電工程,2014,44(3):77-80.

[5] SIP,SUN E,ZHANG Y.Optimal Spectrum Allocation of Primary Users in Light-handed Cognitive Radio Networks[J].Journal of Harbin Institute of Technology,2012,12(3):21-27.

[6] 李云,張智慧,黃巍,等.基于信道分配的多跳認(rèn)知無線電網(wǎng)絡(luò)路由算法[J].系統(tǒng)工程與電子技術(shù),2013,35(4):852-858.

[7] 翟臨博,劉元安.自組網(wǎng)中樹型拓?fù)涞恼J(rèn)知無線電路由協(xié)議[J].北京郵電大學(xué)學(xué)報(bào),2012,35(1):85-89.

[8] LI Jianwu,FENG Zebing,FENG Zhiyong,et al.A Survey of Security Issues in Cognitive Radio Networks[J].China Communications,2015(3):132-150.

[9] 謝玉鵬,譚學(xué)治,馬琳,等.一種認(rèn)知無線電系統(tǒng)中聯(lián)合的頻譜分配新算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2013,45(7):35-41.

[10] ZHAIL,JI H,LI X,et al.Optimal Resource Allocation Scheme for Cognitive Radio Networks with Relay Selection Based on Game Theory[J].The Journal of China Universities of Posts and Telecommunications,2012,19(6):25-28.

[11] EZIRIMK,SENGUPTA S.Self-coexistence among Cognitive Radio Networks using Risk-motivated Channel Selection Based Deference Structure[J].Tsinghua Science and Technology,2013,18(3):242-249.

[12] 王垚,張中兆,馬琳,等.基于授權(quán)用戶活動性的認(rèn)知無線電頻譜分配算法[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,40(8):26-31.

[13] 黎潔,劉羽西,李奇越.基于拓展迭代條件模式的認(rèn)知無線頻譜分配研究[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,38(12):1628-1634.

[14] 倪秋芬.基于博弈論的認(rèn)知無線電網(wǎng)絡(luò)頻譜分配研究[J].計(jì)算機(jī)與數(shù)字工程,2016,44(1):95-99.

[15] FUS,LI Y,YE F,et al.Optimized Parallel Cooperative Spectrum Sensing Strategy Based on Iterative Kuhn Munkres Algorithm[J].Journal of Donghua University (English Edition),2014,31(1):33-38.

[16] 葉培青,李莉,周小平,等.基于Kuhn-Munkres算法保證認(rèn)知用戶QoS的動態(tài)頻譜分配[J].上海師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,42(2):137-142.

[17] 馮冠元.面向認(rèn)知網(wǎng)絡(luò)的信道分配策略研究[D].哈爾濱：哈爾濱工業(yè)大學(xué),2013.

[18] 紀(jì)曉東,謝信乾.基于二分圖最大賦權(quán)匹配的網(wǎng)絡(luò)編碼中繼選擇[J].北京郵電大學(xué)學(xué)報(bào),2011,34(5):33-37.

TopologyGenerationandChannelAllocationAlgorithmBasedonCognitiveRadio

LIU Yutao

(ScienceandTechnologyonInformationTransmissionandDisseminationinCommunicationNetworksLaboratory,Shijiazhuang050081,China)

By sensing the wireless environment,cognitive radio technology can adjust topology and communication parameters adaptively,thereby enhancing system performance.For the changes of wireless environment,especially in authorized user status,the topology and channel allocation results are changed dynamically.This paper mainly focuses on topology generation and channel allocation.After the channel allocation algorithm is proposed for the main and the remaining nodes based on the KM algorithm,the appropriate descending dimension algorithms such as EC,PCA,MDS,LTSA and DM are

through simulation analysis when the useful channel proportion is low.

cognitive radio；topology；spectrum allocation；maximizing the bottleneck link throughput

2017-09-20

國家科技重大專項(xiàng)(2015ZX03004002-004)；國家自然科學(xué)基金面上項(xiàng)目(61671179)

10.3969/j.issn.1003-3106.2018.01.02

劉玉濤.基于認(rèn)知的拓?fù)渖膳c信道分配算法[J].無線電工程,2018,48(1):6-9.[LIU Yutao.Topology Generation and Channel Allocation Algorithm Based on Cognitive Radio[J].Radio Engineering,2018,48(1):6-9.]

TN929.5

A

1003-3106(2018)01-0006-04

劉玉濤男，(1981—)，畢業(yè)于哈爾濱工業(yè)大學(xué)通信與信息系統(tǒng)專業(yè)，博士，高級工程師。主要研究方向：移動自組織網(wǎng)絡(luò)、認(rèn)知無線電。