基于认知的拓扑生成与信道分配算法

刘玉涛

(通信网信息传输与分发技术重点实验室，河北 石家庄 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—)，毕业于哈尔滨工业大学通信与信息系统专业，博士，高级工程师。主要研究方向：移动自组织网络、认知无线电。