基于認知的拓撲生成與信道分配算法

劉玉濤

(通信網信息傳輸與分發技術重點實驗室，河北 石家莊 050081)

基于認知的拓撲生成與信道分配算法

劉玉濤

(通信網信息傳輸與分發技術重點實驗室，河北 石家莊 050081)

認知無線電技術通過感知周圍環境，自適應地調整拓撲結構和通信參數，可以有效地提高通信性能。由于環境的變化，尤其授權用戶工作狀態的變化，認知無線電網絡的拓撲結構和信道分配結果也動態變化。主要基于圖論模型研究最大化瓶頸鏈路吞吐率目標下的拓撲生成與信道分配問題。基于KM算法提出了干線節點和剩余節點的信道分配方法，仿真分析表明，可用信道比例較低時，EC、PCA、MDS、LTSA和DM方法可以在一定程度上提高組網的成功率。

認知無線電；拓撲；信道分配；最大化瓶頸鏈路吞吐率

0 引言

認知無線電具有在不影響授權用戶的前提下智能地利用大量頻譜空穴，實現隨時隨地、高可靠性通信的潛能[1]。文獻[2-4]論述了認知無線電可以作為解決無線頻譜低利用率問題的最佳方案之一。由于電磁環境、地理環境的變化以及業務需求的多樣性，認知無線電用戶通信時的可用信道以及相應的發射功率、調制方式、編碼方式等通信參數都是動態變化的[5]。同時，由于通信需求的變化、認知無線電用戶的移動以及授權用戶即“外界干擾”的動態性，認知無線電網絡的拓撲結構也是動態變化的[6]。

本文考慮的認知無線電網絡存在3種結構：星狀網、鏈狀網和樹狀網，其中，星狀網和鏈狀網均可作為特殊的樹狀網[7]。根據認知無線電網絡的需求，拓撲生成和信道分配技術一般基于3種不同的優化原則：最大化網絡總吞吐率、最大化瓶頸鏈路吞吐率和最大化指定鏈路吞吐率[8]。本文主要研究樹狀網中基于最大化瓶頸鏈路吞吐率的拓撲生成與信道分配算法，并選擇合適的降維方法提高組網成功率。

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

1 系統模型與參數定義

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

圖1 樹狀網網絡模型

一個樹狀組網示意圖如圖2所示。

圖2 網絡拓撲層次化示意

根節點為N4，根節點使用信道f98與節點N1、N3、N10和N12進行通信。由于節點所處位置不同，其信道條件也不盡相同，節點N1、N3和N10使用第L2檔通信速率，而N12只能使用L1檔通信速率。N1作為中繼節點，還需要與N7和N17進行通信，此時鏈路使用信道f80，且與N7、N17的通信速率分別是L4和L3。圖2所示的網絡拓撲結構層次化地表示了節點在鏈路中的位置以及使用的頻點和通信速率。

2 信道分配算法

2.1 KM算法

文獻[15-17]論述了KM算法是一種基于二分圖的算法，可以求解帶權二分圖的最優匹配也就是求權值最大的匹配。KM算法求解二分圖G的最優匹配算法核心是反復修改頂點標記，選第二長邊，使新的相等子圖的最大匹配逐漸擴大，直至最終出現相等子圖的完備匹配，也就是二分圖G的最優匹配[18]。

設G=(V,E)為賦權二分圖，L是其一個初始可行頂點標記，取

(1)

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

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

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

③ 調整可行頂點標記，計算

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

(2)

由此得新的可行頂點標記為：

(3)

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

④ 取y∈NLST，若y是M的飽和點，轉向步驟⑤；否則，轉向步驟⑥。

⑤ 設xy∈M，則令S=S∪x，T=T∪y，轉向步驟②。

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

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

2.2 剩余節點接入算法

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

圖3 剩余節點接入流程

3 仿真分析

3.1 參數設置

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

3.2 仿真結果分析

可用鏈路比例為0.8時，組網成功率在信道可用比例變化時的1 000次仿真的統計結果如圖4所示。由圖4可知，隨著可用信道數量的增加，部分算法表現不夠穩定，比如K-PCA，當信道可用比例達到0.25后，其組網成功率明顯下降。與K-PCA類似的是LTSA算法，在信道可用比例達到0.25后，其組網成功率下降，不適合于高信道可用比例下的組網。

圖4 組網成功率隨信道可用比例變化仿真結果

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

圖5 組網成功率隨鏈路可用比例變化仿真結果

4 結束語

本文主要研究基于認知的拓撲生成與信道分配問題。由于KM算法是一種逐漸接近最優匹配的二分圖方法，可以有效地解決認知用戶間的信道分配問題，因此本文以KM算法為基礎，提出了最大化瓶頸鏈路吞吐率目標下的干線節點和剩余節點的信道分配算法。由于認知無線電用戶是次要用戶，需要伺機接入授權用戶空閑的頻譜，因此信道可用比例較低。仿真分析表明，在低信道可用比例條件下，EC、PCA、MDS、LTSA和DM等降維算法能夠獲得較高的組網成功率。

[1] 宋志群.認知無線電技術及應用[J].無線電通信技術,2012,38(5):1-6.

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

[3] 張平,李建武,馮志勇,等.認知無線網絡架構與關鍵技術研究[J].無線電通信技術,2014,40(3):1-5.

[4] 馬恒.認知無線電中頻譜檢測技術研究[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] 李云,張智慧,黃巍,等.基于信道分配的多跳認知無線電網絡路由算法[J].系統工程與電子技術,2013,35(4):852-858.

[7] 翟臨博,劉元安.自組網中樹型拓撲的認知無線電路由協議[J].北京郵電大學學報,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] 謝玉鵬,譚學治,馬琳,等.一種認知無線電系統中聯合的頻譜分配新算法[J].哈爾濱工業大學學報,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] 王垚,張中兆,馬琳,等.基于授權用戶活動性的認知無線電頻譜分配算法[J].華南理工大學學報(自然科學版),2012,40(8):26-31.

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

[14] 倪秋芬.基于博弈論的認知無線電網絡頻譜分配研究[J].計算機與數字工程,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算法保證認知用戶QoS的動態頻譜分配[J].上海師范大學學報(自然科學版),2013,42(2):137-142.

[17] 馮冠元.面向認知網絡的信道分配策略研究[D].哈爾濱：哈爾濱工業大學,2013.

[18] 紀曉東,謝信乾.基于二分圖最大賦權匹配的網絡編碼中繼選擇[J].北京郵電大學學報,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

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

10.3969/j.issn.1003-3106.2018.01.02

劉玉濤.基于認知的拓撲生成與信道分配算法[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—)，畢業于哈爾濱工業大學通信與信息系統專業，博士，高級工程師。主要研究方向：移動自組織網絡、認知無線電。