离散二进制粒子群优化的频谱分配算法研究

孔令荣，王 昊，殷慧婷，李 冰

(1.南京理工大学泰州科技学院，江苏 泰州 225300；2.东南大学集成电路学院，江苏 南京 210096)

0 引言

美国学者Joseph Mitola博士在软件无线电的基础上，经过提炼和升华，于1999年首次提出认知无线电(cognitive radio，CR)这一术语[1]。认知无线电技术通过感知周围的电磁环境的变化，实时调整自身通信参数，以适应不断更新的环境。

频谱是一种不可再生的宝贵资源，无线通信技术的快速发展受到频谱短缺的制约[2]。为了更好地对频谱分配问题开展研究，许多文献提出了各种频谱分配模型，包括图论着色模型、博弈论模型与定价拍卖模型等[3-4]。频谱分配问题实际上可以归结为一个NP-hard约束优化问题[5]，频谱分配的最优策略依靠传统的算法很难实现。离散二进制粒子群优化算法作为一种智能算法，在稳定性与寻优性能方面具备一定的优势。本文在充分研究了该算法的基础上，将其应用到频谱感知与分配中，采用线性减少惯性权重系数，并通过仿真分析验证了算法的可行性，证明其可以有效地解决频谱分配问题[6-8]。

1 频谱分配模型

本文研究的感知用户与主用户共存于同一区域中，以宏基站或者家庭基站作为主用户。就通信范围而言，宏基站要大于家庭基站。感知用户以无线接入站点的方式接入，它的发射功率可以随时调整。本文采用动态频谱分配策略，Overlay接入模式，即若授权用户接入某频段，则感知用户一律不可接入。

1.1 频谱分配的图论模型

基于图论模型的频谱分配示意图如图1所示。

图1 频谱分配示意图Fig.1 Spectrum allocation diagram

主用户个数为P，感知用户个数为N，随机分布在X×Y的平面内；可用频谱个数为M，它们之间是完全正交的，也随机分布于无线传感网络系统中。感知用户能够在同一时刻使用多个频谱，但其前提是不对其他主用户和感知用户造成干扰。假设主用户为p，p=1，2，…，P；感知用户为n，n=1，2，…，N，它们在频谱m(m=1,2,…,M)覆盖范围分别是以自身为圆心作圆形区域，其半径分别是dpm和dnm。假设用户和用户间的距离是决定它们之间干扰的唯一因素，如果某一个感知用户n和某一个感知用户k在某个频谱上覆盖范围发生交集，则可以认为感知用户n和k之间有干扰存在，那么这个频谱不能被感知用户n和k使用。如图1所示，在主用户p没有进行通信的情况下，频谱m可以同时允许感知用户1、2、3接入，但是假如感知用户1和2同时接入频谱m，则会产生干扰[9-11]。

以上的图论模型也可以转换为图的着色问题，可以认为是对无向加权图G=(V，EC，LB)进行着色。其中，G的顶点是V，代表着认知无线网络中感知用户的集合；图的边的集合是EC，代表感知用户在使用某一频谱时和它的相邻用户间的干扰约束关系；每个顶点的颜色列表和权重用LB表示，代表感知用户对频谱的可用性以及收益权重。

1.2 认知无线传感网络频谱分配矩阵

通过可用频谱矩阵、网络效益矩阵、频谱干扰矩阵和分配矩阵这4个矩阵，可实现频谱状态的标识和分配，从而实现频谱分配。假定在某一个无限传感网络中，感知用户的个数为N，通过认知无线电频谱感知获得了M个频带。根据1.1节所介绍的图论模型，对相关矩阵可作如下定义。

①可用频谱矩阵。

该矩阵定义为：L={ln,m|ln,m∈{0,1}}N×M,l≤n≤N,l≤m≤M。其为N×M矩阵。0或1表示每一个元素，可用频谱矩阵描述感知用户是否可以使用该频带，即指频谱与感知用户之间的可用关系。假如ds(n,m)

②网络效益矩阵。

网络效益矩阵定义为：B={bn,m}N×M。它也是N×M矩阵。它所描述的含义是频带m被感知用户n使用时，无线传感网络所能得到的网络效益。网络吞吐量、网络最大流量以及频谱利用率等物理量都可以用来表示网络效益。相同的频谱资源被不同的感知用户所使用时获得的网络效益往往不一样，这是因为每个感知用户采用的通信调制方式和发送功率均不相同。假如感知用户无法接入频带m，此时ln,m=0，则一定有bn,m=0。

③频谱干扰矩阵。

频谱干扰矩阵定义为C={cn,k,m|cn,k,m∈[0,1]}N×M，它是N×M×M三维矩阵。通常需要依靠频谱干扰矩阵，来描述感知用户n和k同时使用频带m时是否会产生干扰。如果cn,k,m=1，表示感知用户n和k同时使用频带m时会产生干扰；反之，则表示无干扰。当cn,k,m=1时，表示感知用户n和k能够同时使用频带m，也就是说该频带必然能够分别被用户n和k所使用，即表示存在制约关系：cn,k,m≤ln,m≤lk,m。当n=k时，cn,k,m=1-ln,m，只通过可用频谱矩阵L确定。

④分配矩阵。

1.3 频谱分配性能指标

在认知无线传感网频谱分配模型中，寻找频谱分配方案的过程就是使网络效益函数达到最大值的过程。本文运用最大效益(max sum reward，MSR)和最大比例公平(max proportional fair，MPF)这两种不同的网络效益函数作为频谱分配性能指标。

①最大网络效益。

UMSR(R)定义为：

(1)

其目标是不考虑感知用户之间是否公平分配，而专注于使总网络效益达到最大。

②最大比例公平网络效益。

UMPF(R)定义为：

(2)

该网络效益函数考虑了用户之间的公平性。其实质是如果存在另一种频谱分配方案，则其相关的用户效益将弱于该网络效益。

2 基于离散二进制粒子群的频谱分配

2.1 基本粒子群算法

粒子群算法(particle swarm optimization，PSO)由Kennedy和Eberhart提出，其应用于连续空间的优化计算，是一种群智能进化算法。粒子自身的目标函数与种群整体评价函数可以对粒子自身的位置信息与速度信息作出相应的调整、断判及更新，并作出动态的调整。

假定在一个D维搜索空间之中，一粒子群由m个粒子所组成。其中：第i粒子的空间位置可以表示为xi=(xi1,xi2,…,xiD)T,i=1,2,…,m；第i个粒子所经历的最好位置称为其个体历史最好位置，记为pi=(pi1,pi2,…,piD)T，i=1,2,…,m；相应的适应值为个体最好适应值Fi。每个粒子均具有各自的飞行速度，可以表示为vi=(vi1,vi2,…,viD)T,i=1,2,…,m。用全局历史最好位置表示所有粒子经历过的最好位置，可以表示为pg=(pg1,pg2,…,ggd)，相应的适应值就是全局历史最优适应值。

在基本PSO算法中，对于第t代粒子，其第d维(1≤d≤D)元素速度、位置更新迭代式为：

(3)

(4)

式中：ω为惯性权重；c1与c2为学习因子；r1与r2为两个随机数，其变化取值范围是[0,1]。

[Xd,min,Xd,max]表示第d维粒子元素的位置变化范围，[Vd,min,Vd,max]表示第d维粒子元素的速度变化范围。在算法迭代过程中，假如某一维粒子元素的Xid或Vid超出了边界值，那么就令Xid或Vid等于边界值。

2.2 离散二进制粒子群算法

PSO算法最初用于对连续空间问题进行优化。离散二进制粒子群(binary particle swarm optimization，BPSO)算法作为基本粒子群算法的改进，其频谱分配矩阵各值为0或1，属于离散二进制数。在BPSO算法中，粒子定义为一组由0、1组成的二进制向量。速度值vid通过预先设计的S形限幅转换函数Sig(vid)转换为粒子元素xid取“1”的概率。速度值vid越大，则粒子元素位置xid取“1”的可能性越大，反之则越小。

(5)

(6)

式中：Sig(vid)为Sigmoid函数。通常，为防止速度过大，令vid∈[vidmin,vidmax]，使概率值不会过于接近0或1，保证算法能以一定的概率从一种状态跃迁到另一种状态，防止算法早熟。

惯性权重系数ω决定了粒子先前速度对当前速度的影响程度，起到了平衡算法全局搜索和局部搜索能力的作用。当ω的取值范围为[0.9，1.2]时，算法优化性能较好。本文采用惯性权重ω的自适应策略，即随着迭代的进行，线性减少权重ω。线性减少权重系数ω的公式为：

(7)

式中：ωmax和ωmin分别为最大惯性权重系数和最小惯性权重系数;t为运行的迭代数，即第t代时的权重系数值;tmax为最大运行迭代数。

惯性权重系数ω越大，表明全局探索能力越强，能探索更大的新空间；惯性权重系数ω越小，表明局部探索能力越强，能在最优解附近精细探索空间。随着迭代的进行，线性地减少惯性权重系数ω，可以使得粒子群算法在迭代的初期有较强的探索能力，从而探索新的区域；而在后期又有较好的收敛性，可以在最优解附近精细搜索。

2.3 频谱分配算法步骤

基于BPSO算法的频谱分配步骤如下。

④按照式(3)和式(4)，更新粒子速度和位置信息；利用式(5)和式(6)，将位置离散二进制化。

⑤重复执行步骤③。

⑥判断是否满足终止条件。如果满足，则终止算法；反之，重新执行步骤④。

3 试验验证

试验验证采用Matlab仿真平台。BPSO参数设置c1=c2=2，ω的取值范围为0.9～1.2，迭代次数为200。仿真40次，取仿真结果平均值。

改变主用户数、信道数、感知用户数，观察与网络效益、最大比例公平网络效益关系，如图2和图3所示。

图2 迭代次数与网络效益关系图Fig.2 Relationship between numbers of iterations and network benefit

图3 迭代次数与最大比例公平网络效益关系图Fig.3 Relationship between numbers of iterations and maximum proportion fair networks benefit

图2(a)和图2(b)信道数、感知用户数相同，主用户数不同。如果主用户数增加，那么可用信道空闲率会减少，从而减少感知用户占用信道的机率，降低整体网络效益。同理，图3(b)和图3(a)相比，主用户数增加，最大比例公平网络效益降低。

图2(a)和图2(c)主用户数、感知用户数相同，信道数不同，表明通过增加可用信道空闲数量使感知用户占用信道的机率大大增加，整体网络效益得到大幅度提高。同理，图3(c)和图3(a)相比，空闲信道数增加，最大比例公平网络效益提高。

图2(a)和图2(d)主用户数、信道数相同，感知用户数不同。虽然感知用户数量的增加使感知用户之间的竞争变得激烈，但另一方面使得可用信道的利用率也有所提高，其结果是使得整体网络效益略有提高。但是由于各感知用户之间竞争激烈，同时受到频谱资源的限制，图3(d)和图3(a)相比，空闲信道数增加，最大比例公平网络效益降低。

将本文BPSO算法与遗传算法(genetic algorithm，GA)、敏感图着色法(color sensitive graph coloring algorithm，CSGC)进行比较。

图4为使用BPSO、GA和CSGC三种算法仿真网络效益随迭代次数变化的关系曲线。取主用户数为20，信道数为10，感知用户数为20。BPSO算法的网络效益迭代后稳定在231，GA稳定在189，CSGC稳定在165。在相同迭代次数下，采用BPSO算法可获得较高的网络效益，优于GA和CSGC算法。

图4 网络效益变化曲线Fig.4 Variation curves of network benefit

图5为使用BPSO、GA和CSGC三种算法仿真最大比例公平网络效益随迭代次数变化关系曲线。取主用户数为20，信道数为10，感知用户数为20。BPSO算法的最大比例公平网络效益迭代后稳定在1.4，GA稳定在0.95，CSGC稳定在0.4。在相同迭代次数下，采用BPSO算法获得的最大比例公平网络效益优于GA和CSGC算法。

图5 最大比例公平网络效益变化曲线Fig.5 Variation curves of maximum proportional fair network benefit

4 结束语

本文借助图论模型，将频谱分配问题转换为网络效益与分配矩阵寻优问题。采用离散二进制粒子群优化算法，以网络效益、最大比例公平网络效益为目标函数，寻找最优分配矩阵。通过改变主用户数、信道数和感知用户数，经过多次Matlab仿真试验，证明了本文提出的基于离散二进制粒子群频谱分配算法相比于遗传算法和敏感着色法，可以获得更高的网络效益和最大比例公平网络效益，并有效提高网络吞吐量。该研究具有一定的实用价值和应用前景。

参考文献:

[1] MITOLA J.Cognitive radio for flexible mobile multimedia communications[C]//IEEE International Workshop on Mobile Multimedia Communications,1999:3-10.

[2] GOSCINIAK I.A new approach to particle swarm optimization algorithm[J].Expert Systems with Applications，2015，42(2)：844-854.

[3] EBERHART R C，KENNEDY J.A new optimizer using particle swarm theory[C]//Proceedings of the Sixth International Symposium on Micro-Machine and Human Science,1995：39-43.

[4] TANGY，WANG Z，FANG J.Feedback learning particle swarm optimization[J].Applied Soft Computing，2011，11(8)：4713-4725.

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

[6] EBERHART R C，SHI Y.Particle swarm optimization：developments，applications and resources[C]//Proceedings of Evolutionary Computation，2001：81-86.

[7] CLERC M,KENNEDY J.The Particle Swarm-explosion，stability，and convergence in multidimensional complex space[J].IEEE Transactions on Evolutionary Computation，2002，6(1)：58-73.

[8] HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C]//Hawaii International Conference on System Sciences，2000：8020.

[9] JUN Z,YUN B.Analytical optimization for collaborative double-threshold energy detection in cognitive radio network[J].Journal of Information and Computational Science，2012，9(13)：3875-3882.

[10]JINJ， XUH B， RENC J.Superposition-based cooperative spectrum sensing in cognitive radio networks[C]//In Proceedings of 2010 International Conference on Computer Application and System Medeling(ICCASM),2010：342-346.

[11]GUO J， SONG T， WU M， et al.An improved weighted cooperative spectrum sensing in cognitive radio networks[C]//International Conference on Consumer Electronics，2013：113-116.