认知无线电网络信道分配联合策略算法

孙彦景，郝之楹

(中国矿业大学 信息与控制工程学院，江苏 徐州 221000)

0 引 言

随着车联网、虚拟现实等新型通信业务的不断涌现使得通信业务量飞速增长。据统计，截至2015年底，移动数据流量在过去的15年中增长了近4亿倍，并预计在2020年时持续增长近8倍[1]。随着无线通信的普及，固定频谱分配方案导致了有限的频谱资源的不充分利用，愈发无法满足人们对无线通信的需求。根据美国联邦通讯委员会(federal communications commission，FCC)最近一项研究表明，3 GHz以下频段的频谱利用率仅为15%～85%，因此，新型频谱分配方案被广泛研究[2-3]。认知无线电技术(cognitive radio, CR)被认为是解决无线频谱资源短缺问题的一种有效技术，采用CR技术的网络称为认知无线电网络(cognitive radio networks, CRNs)。CRNs能够感知和发现通信环境中的频谱空洞，并根据感知结果改变自身传输参数进行动态频谱接入，充分利用空间中可用的频谱资源有效解决频谱资源稀缺的问题[4-5]。

在CRNs中，未被授权频谱的次级用户(secondary user, SU)能够复用主用户(primary user, PU)授权的频谱资源来伺机寻求可靠的通信机会。因此，次级用户需要具有认知能力，通过感知周围通信环境，了解环境变化以及主用户的活动，并相应调整其参数以接入频谱[6]。次级用户在underlay机制下复用主用户信道时，需保证信道中的次级用户对主用户产生的干扰不影响主用户的通信质量[7-8]；在完成信道分配后，复用同一信道的次级用户需要进行信道内的功率管理或信干噪比管理，以最优化网络性能。

J.Huang等[9]首先将拍卖算法等经济学理论应用于认知无线电网络的频谱分配问题，但文中的系统仅考虑了主用户与次级用户、次级用户间的干扰，未考虑次级用户与终端间的干扰。文献[10]通过限制一个信道上仅能存在一个次级用户避免了次级用户间的干扰冲突，但也限制了网络性能。文献[11-12]提出的启发式信道分配算法的目标是在不考虑干扰限制的情况下找到无冲突的频谱分配，因此，算法无法充分利用网络的可用容量。文献[13-14]中未考虑信号传输过程中中继节点的干扰，不符合实际网络情况应用需求。

本文提出了underlay机制下CRNs全干扰系统模型，在不限制信道中次级用户数量的条件下考虑次级用户与终端间的干扰。基于提出的CRNs系统全干扰模型，本文提出一种联合策略资源分配算法(joint strategy algorithm, JSA)，将系统中有限的资源合理分配给次级用户，以满足次级用户的通信需求并有效提高系统合速率。在遗传算法中加入定向变异因子(directional mutation factor, DMF)保证种群的进化方向，利用改良后的遗传算法对系统中所有的次级用户进行信道分配，求得最优的信道分配方案。针对遗传算法算法复杂度高、收敛速度慢等问题，无法满足实时应用需求，本文进一步采用拍卖算法对功率、信干噪比(signal to interference plus noise ratio, SINR)等进行管理，有效提高系统的合速率与算法收敛速度。

1 系统模型

本文研究了如图1的认知无线电网络，网络中存在S个基站，假设每个基站下有D个下行信道，则共有M(M=D·S)个无重叠正交信道，同时，系统中有N个网络接入点(access points, APs)。其中，基站代表主用户，AP代表次级用户。

图1a的全干扰系统模型中，N个次级用户(SU1,SU2,…,SUn)竞争使用M个信道(Ch1,Ch2,…,Chm)，当用户终端距离主基站较远，无法满足通信需求时，用户终端转而向次级用户请求服务，SUn在某一时段内只服务于一个用户终端n。终端n在接收信号时，同时受到来自基站s与复用信道m的其他AP的干扰。完成信道竞争后，复用同一信道内的次级用户及其服务终端的模型如图1b。终端n在信道m上的接收信号为

(1)

(1)式中：hn,n(m)为SUn至终端n在信道m上的增益；hj,n(m)表示SUj至终端n在信道m的增益；hs,n(m)表示基站s至终端n在信道m的增益；Ps为基站的发射功率；Pn,m为SUn在信道m上的传输功率。

每个次级用户SUn都有自己接入信道m的效用函数，即速率um,n。系统的效用矩阵表示为U={um,n}M×N，其计算方式表示为

(2)

|hn,n|2=gSDn,n·gFn,n·gPLn,n

(3)

(4)

(2)—(4)式中：B为信道带宽；gSDn,n，gFn,n，gPLn,n分别表示阴影、衰落和路径损耗，阴影因子gSDn,n服从对数正态分布，衰落因子gFn,n服从瑞利分布，路径损耗因子gPLn,n服从Okumura-Hata路径损耗模型；|hj,n|2，|hs,n|2的计算与|hn,n|2计算方法相同[10]；N0为噪声功率谱密度；Pt为传输功率；Γm表示信道m上所有的次级用户的集合。本文假设所有的次级用户具有相同的传输功率。

将次级用户使用信道的情况记为信道可用矩阵L={lm,n|lm,n∈{0,1}}M×N，当且仅当SUn可以复用信道m时，lm,n=1，反之，则为0。为了保证通信的可靠性，SUn在信道m上的信干噪比必须要大于一个最小的信干比γ0。由于SUn在申请接入信道m时，SUn不知道信道m内是否存在其他次级用户，因此，在最初生成矩阵L时，本文只考虑信干比γn,m，即

γn,m≥γ0

(5)

得到矩阵L后，当SUn可以使用信道m时，再根据限制条件(5)判断信道m是否分配给SUn。基于矩阵L，可知同时复用信道m的所有次级用户，因此，区别于(5)式，下文将γn,m记为信干噪比。记信道分配矩阵A={am,n|am,n∈{0,1},am,n≤lm,n}M×N，当且仅当SUn复用信道m时，am,n=1，反之，则为0。

2 认知无线电网络信道分配联合策略算法

基于提出的干扰模型，针对如何将系统中有限的信道资源合理分配给次级用户，本文提出一种JSA算法。JSA采用改良遗传算法完成信道分配后，使用拍卖算法对信道内的次级用户进行功率控制，有效提高了系统的合速率。算法在遗传算法寻求最优解的基础上，联合拍卖算法提升整体的收敛速度，减小复杂度。

算法的优化目标可以描述为

(6)

γn,m≥γ0

(7)

(6)式保证了信道m上所有的次级用户对基站s产生的干扰小于可承受干扰阈值(interference temperature level, ITL)，(7)式保证了信道m上任意SUn的信干噪比大于γ0。

2.1 基于遗传算法的信道分配

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的随机化方法。一个给定问题的解决方案称为“染色体”，染色体由“基因”组成，其中，包含了一组优化变量的值。本文将信道分配矩阵中lm,n=1的元素记为一个基因，一个基因中包含了次级用户信息和信道信息，对所有的基因进行0/1编码后记为一个染色体，即一个染色体代表一种可能的信道分配方案，并将一组“染色体”记为一个种群。与传统遗传算法不同的是，改良后的遗传算法中加入了DMF以保证种群朝着好的方向进化。

具体算法如下所述。

步骤1 通过(5)式得到矩阵L，若对矩阵L中的每一个元素都进行编码，染色体中会产生很多冗余，为了减少计算量，仅对矩阵L中值为1的元素进行0/1编码，因此，染色体的长度Lch等于矩阵L中值为1的元素的个数。

步骤2 根据(6)式，(7)式检查染色体是否符合限制条件，若不符合，则略作修改。种群中染色体遗传的方向取决于每代中个体的适应度，即对每个染色体的客观评价机制，根据(2)式计算种群中每个染色体的适应度。

步骤3 得到每个染色体的适应度后，计算染色体的选择概率以及累计概率，通过轮盘赌选择的方法对染色体进行优胜劣汰。保留下的染色体首先按照交叉概率Pc对染色体进行2点交叉变异，之后按照随机变异概率Pm对染色体进行变异，最后本文加入了DMF，分别记次级用户数最多和最少的信道为Cmax与Cmin，淘汰Cmax中适应度最低的次级用户，并在Cmin上随机增加一个次级用户。

之后，返回步骤2，直至达到迭代次数，记录并输出适应度最高的分配矩阵A。

算法的具体流程如下。

算法1 基于遗传算法的信道分配。

步骤1 根据(5)式计算得到信道可用矩阵L={lm,n|lm,n∈{0,1}}M×N；

步骤3 根据0/1编码机制随机生成初代种群；

尽管我也为孩子配备了安全座椅，可是安装起来很麻烦，宝宝也不大喜欢坐。只要坐上安全座椅宝宝不是哭闹，就是各种乱动，让我很是头疼。就在准备放弃安全座椅时发现了宝贝第一铠甲舰队PLUS的试用活动。

步骤4 对于所有染色体，将染色体的第j位映射到lm,n，其中，(m,n)是L1中的第j个元素且1≤j≤Lch；

步骤5 根据(2)式计算当前种群中每个个体的适应度；

步骤6 进行轮盘赌选择，交叉，随机变异以及定向变异得到新的种群；

步骤7 返回步骤5直至达到迭代次数，记录适应度最高的分配矩阵A。

2.2 基于拍卖算法的功率控制

通过遗传算法完成了次级用户间的信道分配后，假设共有U(U≥0)个次级用户分配至信道m，U个次级用户如何合理协作最优使用信道却是未知的，因此，本文使用拍卖算法对信道内的所有次级用户进行功率控制或信干噪比控制[14-15]。拍卖过程中，次级用户进行竞拍以表示自己的支付意愿，管理者(主用户)提出一个非负的预留定价β以保证拍卖可以得到一个最优解，并根据次级用户的投标按比例进行功率控制或(SINR控制)，次级用户根据自己投标得到的功率(或SINR)进行支付。拍卖过程中，采取的是完全信息博弈，参与拍卖的次级用户互相公开自己的效用值。

本文采取2种拍卖机制：①根据次级用户的功率进行收费，这一机制可以最大化合速率；②根据次级用户的SINR进行收费，可以实现加权的SINR分配的最小公平最大化。由于2种拍卖机制的流程相似，因此，下面仅以拍卖功率为例，详述算法流程如下。

1)主用户提出预留定价β和定价πI，SUn根据β和πI给出投标bn(bn≥0)；

2)主用户预留功率ps，根据SUn的投标分配功率pn。为简便表达将ITL记为I，根据(6)式可得

(8)

(9)

根据(8)式和(9)式可以得到信道内信干噪比为

(10)

3)分配功率后，SUn需支付Cn=πIpn|hn,n|2。将所有次级用户的投标记为向量b=(b1,b2,…,bU)，记b-n=(b1,…,bn-1,bn+1,…,bU)，因此，可以将b表达为b=(bn;b-n)。在之后的拍卖过程中，次级用户修改投标以达到剩余函数的最大化

S(bn;b-n)=U(λn(bn;b-n))-Cn

(11)

S(bn;b-n)=U(λn(bn;b-n))-πIpn|hs,n|2=

-πIρn

(12)

4)将(11)式求得最大值的b记为

(13)

为求Sn(bn;b-n)的最大值，对(11)式求关于bn的偏导数并令其值为0,

(14)

(15)

因此，存在唯一一个满足下列条件的最佳出价

Bn(b-n)=,若

(16)

Bn(b-n)=0,若U′n(0)≤πI

记矩阵K和k分别为

(17)

则(13)式可表示为

(18)

每一轮拍卖后，主用户和次级用户根据第上一次的拍卖修改β，πI和b并进行下一次拍卖

(19)

根据(19)式可得

(20)

b*=(I-K)-1kβ

(21)

(21)式是矩阵求逆的解析解，所以复杂度为矩阵维度的3次方，即为U3。

观察(21)式可以发现，最终实现NE的拍卖投标b*与初始投标b0没有关系，仅与K和k相关。因此，拍卖过程中管理者可以通过调整πI来实现NE，这减轻了NE的典型低效率。在得到b*后，可以反推出pn，根据(1)式可计算得到信道内功率分配后的合速率sumU。整体算法流程如下。

算法2 基于拍卖算法的功率控制。

步骤1 输入算法1得到的矩阵A，管理者提出β，πI，用户提出bn；

步骤2 管理者预留功率ps，根据SUn的投标分配功率pn；

步骤3SUn根据pn支付Cn=πIpn|hn,n|2；

步骤4 计算Sn(bn;b-n)=Un(λn(bn;b-n))-Cn，并判断是否达到NE；

步骤5 若在步骤4时达到NE，则输出使Sn最大的b，反之则管理者通过修改πI来实现NE；

步骤6 达到NE后，通过b可得到pn并计算出sumU。

JSA算法即由算法1与算法2构成，通过算法1完成信道分配并输出矩阵A后，算法2根据矩阵A进行信道内资源分配并输出优化后的系统合速率sumU。

算法的整体流程如图2。

3 仿真结果

为验证算法结果的有效性，通过Matalb仿真工具分别对穷尽算法(exhaustive testing)，JSA算法，没有加入定向因子的JSA-D算法，传统遗传算法(conventional GA)以及随机算法(randomized algorithm)进行性能分析，其中，JSA算法包括对SINR进行拍卖的JSA算法以及对功率进行拍卖的JSA算法，JSA-D同理。设交叉概率Pc=0.8，变异概率Pm=0.001，迭代次数T=200，基站数S=3，基站下行信道数量D=2，系统中信道总数M=D·S=6，系统半径d=0.3 km，传输功率Ps=Pt=0.6 W，带宽B=200 kHz，n0=-110 dBm，干扰阈值ITL=-110 dBm，最小信干噪比γ0=12 dB，对数正态分布的标准差为10 dB，终端在系统中的位置服从标准分布。

图3为相同迭代次数、不同用户数下的7种算法的合速率比较。从图3中可以看出，对功率进行拍卖的JSA算法始终优于对SINR拍卖的JSA算法与遗传算法，并非常接近穷尽算法得到的效果。当次级用户数不断增加时，在相同的迭代次数下，JSA算法的收敛速度优于遗传算法，加入DMF的JSA算法的收敛速度优于未加入DMF的JSA-D算法，因此，JSA算法的合速率始终高于遗传算法与JSA-D算法。由此可以得出，JSA算法可以有效提高系统的合速率。

图4仿真为当次级用户数为10时，5种算法的系统合速率随迭代次数变化的结果。由图4可得，遗传算法无法得到收敛，但JSA算法以较快的速度收敛至稳定，其中，对功率进行拍卖的JSA算法随着迭代次数的增加始终高出对SINR进行拍卖的JSA算法约50 bit/s/Hz。当迭代次数提升至100次时，遗传算法的合速率将高于对SINR进行拍卖的JSA算法；当迭代次数继续增长至200次时，遗传算法的合速率将逼近对功率进行拍卖的JSA算法。

图5为相同迭代次数、不同用户数时，5种算法的公平性比较。纵坐标表示Jain’s公平性指数[16]，指数越大说明公平性越好。由于对SINR拍卖的JSA算法可以实现最小公平最大化，因此，从图5中可以看出，其公平性始终优于对功率进行拍卖的JSA算法，并且随着用户数的增加，优势愈发明显。当用户数为10时，对功率进行拍卖的JSA算法公平性略低于遗传算法0.01，但当用户增加至18时，公平性开始明显优于遗传算法。由此可以得出，JSA算法具有良好的公平性。

4 结 论

本文在考虑了CRN系统内主用户、次级用户与终端间多种干扰的基础上，建立了一种认知无线电网络全干扰系统模型，并基于模型提出了一种基于改良遗传算法与拍卖算法的联合策略信道分配算法。算法通过加入DMF改良遗传算法，保证种群的进化方向，通过改良遗传算法完成信道分配后，采用拍卖竞价方法对复用同一信道的所有次级用户进行功率或SINR管理。仿真结果表明，本文所提出的联合策略信道分配算法可以明显提升系统合速率，达到充分利用频谱资源的目的，此外，JSA的收敛速度优于传统遗传算法，更符合实际应需求。