- 1 -
基于点着色的认知无线电频谱分配
薛钰
北京邮电大学通信网络综合技术研究所，北京（100876）
摘 要：本文主要研究认知无线电网络(CRN）中的机会频谱分配算法，基于图着色原理研
究了频谱分配的模型，假设及算法，分析了六种经典算法的基本原理和分配目标，并针对三
种基础的分布式算法，提出了三种改进和拓展算法，并在吞吐量、公平性及复杂度方面对这
三种算法进行了仿真和比较分析。
关键词：认知无线电网络，频谱分配，图着色原理，分布式算法
中图分类号: 文献标识码: A
1. 引言
随着无线通信业务需求的快速增长，目
前可分配频谱资源日益紧张。而检测表明，
无线频段的使用却是严重的“贫富不均”：有
些频段异常拥挤，而有些频段大部分时间则
处于闲置状态。为了解决这种短缺资源没有
有效利用的问题，采用认知无线电网络
CRN(Cognitive Radio Network)通过感知时
域、频域、和空间域等三维空间中的频谱环
境，自动搜寻并利用这些闲置频段，实现不
可再生频谱资源的再利用，大幅度全方位地
提高频谱的使用率[1-3]。因而频谱的有效分
配成为 CRN关注的一个重点。
为了解决两系统并存下，CRN 可用信
道的有效分配，引入基于着色原理的频谱分
配模型，并在此基础上对算法进行研究和改
进。本文在基于图着色理论的频谱分配模型
基础上，给出了分布式贪婪算法 DGA
（Distributed Greedy Algorithm）和分布式公
平算法 DFA（Distributed Fair Algorithm）随
机分布式算法 RDA（Randomized Distributed
Algorithm）[4]的改进算法，并在此基础上衡
量了各算法的性能。
2. 频谱分配算法模型
在固定拓扑中，CR用户位置的固定使
得信道分配相对简单，为简化分析假设一次
分配中用户的可用信道也是固定不变的。针
对于此，为避免冲突在给定拓扑下信道的分
配需满足两个限制条件：一是在同一时间，
每个 CR用户的可用信道需与检测结果中授
权用户未占用信道相匹配；二是 CR用户之
间同时分配相同信道需满足一定的距离、发
送功率等要求。
在此限制条件下，CR用户信道分配发
生冲突时，优化信道分配问题可转换为图着
色问题。将整个CRN网络抽象为一个冲突图
G（V，E，L），信道的分配过程可用图着色
理论建模：
（1）顶点 { , 1,2,..., }nV V n N= = ， 表示
需要分配信道的所有CR用户集合, V N= 表
示CR用户总数。
（2）边E表示信道分配相互冲突的关联
边矩阵, { }{ }| 0,1nr nr N NE e e ×= ∈ ， nre ＝1/0表示
用户 n与用户 r间有边/无边。有边表示两用
户信道分配不满足干扰限制，可能出现冲
突，需分配不同的信道，即着不同的色。
（3） L是可用信道状态矩阵，
{ }{ }| 0,1nm nm M NL l l ×= ∈ ， nml =1/0表示用户 n可以
/不可以使用信道m。依据授权用户占用信
道的情况，每个CR用户可用信道集合不同。
分配的信道是颜色的集合 { , 1,2,..., }mC C m M= = ，
C M= 表示可分配信道总数。实际分配后，
信道分配情况表示为分配矩阵
{ }{ }| 0,1nm nm N MS s s ×= ∈ ， nms ＝1/0表示信道m
本课题得到教育部博士点基金（20040013010）资助。
2
已分配/未分配给CR用户 n。具体抽象模型
过程如下图1：
图 1 冲突图模型
如上图所示， nV 代表CR用户， nV 根据
授权网络的信道使用情况（如图中区域内小
括号内所示），列出本身可用的信道列表，
然后进行下一步分配。在传统的图着色理论
中，将冲突图中的顶点进行着色, 在满足一
定条件下,是使得任意两个相邻顶点不具有
相同的颜色，而所需要的颜色数最少。本文
中采用图着色理论主要用来解决在上述限
制条件下如何最大化的分配信道。
3. 频谱分配算法的研究现状
3. 1基于吞吐量最大的算法
当不考虑信道差异，权值归一化为1时，
分布式贪婪算法DGA（Distributed Greedy
Algorithm）针对每一信道，最大化使用此信
道的用户数，达到系统总吞吐量最大。当考
虑信道差异时，合作最大化和带宽CMSB
(Collaborative Max Sum Bandwidth)算法[5]联
合考虑相邻用户间的冲突 nmD （ nmD 表示用户
n相邻用户中m信道可用的用户数之和），分
配给权值较大且冲突数较小的用户，最大化
系统的总吞吐量[5]。随机分布式算法RDA
（Randomized Distributed Algorithm）通过调
整用户的竞争窗口，在相邻用户间比较后分
配信道，最大化可用信道的分配同时减小了
通信开销，降低了复杂度。
表 1 基于吞吐量最大的分配算法比较
算法 目标规则 分配方法
DGA
1 1
max
NM
nm
Sm n
s
= =
∑ ∑
逐一将信道分配给满
足
1
max
N
nm
n
s
=
∑ 的用户，若
有相同，则
1
( )
M
nm
m
L n l
=
= ∑
越小，优先级越高
CMSB
1 1
max
N M
nm nm
S n m
s b
= =
⋅∑ ∑
逐一将信道分配给满
足 ( )max / 1
n
nm nm
m l
b D
∈
+ 的
用户，若有相同，则 nmD
越小优先级越高
3. 2基于公平性最佳的算法
分布式公平算法DFA（Distributed Fair
Algorithm）以平均分配信道为目标，优先分
配小信道冲突数用户，来保证分配的公平。
合 作 最 大 化 最 小 带 宽 算 法 CMMB
(Collaborative Max Min Bandwidth )以最大
化小流量CR用户的吞吐量，来保证系统分
配的公平性；合作最大化比例公平CMPF
(Collaborative Max Proportional Fair)算法则
根据比较各CR用户使用某一信道的回报结
果来分配信道，达到系统吞吐量上的比例公
平[5]。
表 2 基于公平性最佳的分配算法比较
算法 规则 分配方法
DFA *
1
arg min
M
nm
m
n s
=
= ∑
( )*
1
min
M
rmn r
m
e s
=
⋅∑
根据用户的可用信
道数生成有向图，从
宿结点开始逆向逐
次分配一个冲突数
较小的信道。
CMMB
1
max min
M
nm nm
n NS m
s b< =
⋅∑
逐次选出总流量最
小的用户，分配给其
可用信道中权值最
大的信道。若用户流
量相同，则 nmD 越小
优先级越高。
CMPF
10
1 1
max log
N M
nm nm
S n m
s b
= =
⎛ ⎞⋅⎜ ⎟⎝ ⎠∑ ∑
比较 ^/n nr R （即用户
n 使用此信道能得
到的吞吐量和之前
n 使用此信道得到
的 平 均吞 吐量 之
比），将信道分配给
最大 ^/n nr R 值的用
3
户。
3. 3基于复杂度最佳的算法
复杂度的衡量包括计算开销和通信维
护等开销两方面内容，如今随着CPU计算和
处理能力的快速发展，计算开销已经不需要
过多考虑，而通信和维护开销成为衡量算法
复杂度的主要因素，因此本文中用通信开销
来比较算法的复杂度。随机分布式算法RDA
（Randomized Distributed Algorithm）通过调
整用户的竞争窗口，在相邻用户间比较后分
配信道，最大化可用信道的分配同时减小了
通信开销，大幅度降低了频谱分配的复杂
度。
表 3 基于复杂度最小的分配算法
算法 规则 分配方法
RDA ( )
1 1 1
max
N N M
nr rm
Sn r m
e r
= = =
∑∑ ∑
rmr ：表示分
配中 r 用户对
m 信道产生的
随机数
CR 用户在窗口[0,w]内
对每个可用信道产生
一个随机数，将信道分
配给所有相邻用户中
随机数最大的用户。调
整竞争窗口后，产生新
的随机数，继续下一轮
信道分配，直到信道分
配完成。
4. 频谱分配算法的改进和拓展
由于以上部分算法在 CRN 中的局限
性，因此在性能的基础上进一步考虑实际情
况的运用，因而可以得到以下几种算法的改
进和拓展。
4. 1 DGA的改进
因为 DGA是以顶点（用户）链路度数
为比较对象，来分配信道的，因而结果不够
准确，即算法不够贪婪。引入冲突数 nmD 作
为衡量标准，首先改进 DGA 算法，成为
DCGA （ Distributed Collision Greedy
Algorithm）针对一个信道，以用户的冲突数
大小为衡量标准，越小优先级越高，进行信
道分配。吞吐量较 DGA 更大，仿真显示如
下所示：
5 10 15 20 25 30 35 40
50
100
150
200
CR用户数
吞
吐
量
5 10 15 20 25 30 35 40
20
40
60
80
100
CR用户数
公
平
性
DGA
DCGA
DGA
DCGA
图 2 DGA与 DCGA的仿真性能比较
由上图可以看出，DCGA在总吞吐量上
要比 DGA 性能好，且公平性也较 DGA 有
所提高，因而，冲突数的引入比顶点度数更
适合解决 CRN中的无冲突信道分配问题。
进一步，将 DCGA 算法考虑信道质量
差异和环境差异而引起的信道权值的不同，
得到 DCGBA（Distributed Collision Greedy
Bandwidth Algorithm）算法，算法的主要思
路是以冲突数为主要依据，尽量给用户分配
较多数量的信道，在此基础上保证最大的吞
吐量。一次分配的具体实现流程如下：
N MB ×
nv
nmD
nmb
( )nmmin D
nv
nmD
nmb
nv
图 3 DCGBA算法流程图
4. 2 DFA的改进
DFA 考虑信道质量差异得到改进算法
DBFA （ Distributed Bandwidth Fair
Algorithm），算法主要思路如下：根据用户
的可用信道数的大小将网络生成一个有向
图，进而从宿节点开始逆向给可用信道数最
小的用户分配其可用信道中权值最大的信
道，逐个用户逆向分配，知道一轮分配完成，
循环分配直到所有的可用信道均分配完后，
循环终止。一次分配的具体流程如下：
4
N MB ×( )max nmb
( )max nmb
nmb nmD
nmD
图 4 DBFA算法流程图
4. 3 RDA的改进
RDA考虑信道质量差异得到改进算法，
得 到 RBDA （ Bandwidth Randomized
Distributed Algorithm）算法，算法依照以下
思路得到：
1 1 1
max
1
N N M rm
nr
Sn r m nm
be
D= = =
⎛ ⎞ ×⎜ ⎟+⎝ ⎠∑∑ ∑
其主要思路如下：在相邻用户间用吞吐
量权值代替随机产生的随机数，进行比较，
在相邻用户间，将此可用信道分配给拥有较
大吞吐量权值的用户。一次分配流程如下：
初始化权值矩阵
交互信息，计算
比较相邻用户
是否最大
调整
竞争
窗口
w为
2w调整累加回报吞吐量w为
分配信道
否
是
下
一
轮
比
较
1
nm
nm
b
D +
1
nm
nm
b w
D
×+
N MB ×
/2w
图 5 RBDA算法流程图
5. 频谱分配改进算法的仿真
5. 1场景设置
仿真条件取 CR 用户数从 N＝5 变化到
N＝40，可用工作信道总数为M＝20，随机
产生的信道可用概率为 ，仿真结果取循
环 100次后的平均值。
5. 2 仿真衡量参数：
（1）平均吞吐量：取每个 CR 用户分
配信道所获得吞吐量的平均值来衡量算法
的吞吐量性能。
（2）平均分配信道数比较：取每个 CR
用户所分配的信道数的平均值来衡量算法
的服务量性能。
（3）吞吐量公平性：公平性指标用CR
用户之间吞吐量的方差来衡量，吞吐量方差
越小，公平性越好。若所有CR用户获取相
同的吞吐量，则公平性指标为零。
（4）分配信道数公平性：为了保证不
同用户的服务量，以分配信道数的公平性为
标准，取CR用户之间分配到的信道数的方
差，方差越小，用户服务量越公平。
（5）复杂度：在此首先假设各种算法
一次分配中用户的可用信道固定不变。而实
际的CRN网络中，由于授权用户业务流量的
变化会引起CR用户可用信道随时间不断变
化。一次分配时间较长和迭代次数较多的算
法不适合这种网络。由于上述各算法在信道
分配过程中，时间的消耗主要分布在交互信
息上，这里仿真算法的通信开销来比较时变
的适用性。
5. 3 仿真结果和分析：
5 10 15 20 25 30 35 40
2
3
4
5
6
7
8
CR用户数
平
均
吞
吐
量
DCGBA
DBFA
RBDA
图 6 三种改进算法的平均吞吐量比较
5 10 15 20 25 30 35 40
4
6
8
10
12
14
16
CR用户数
平
均
信
道
数
DCGBA
DBFA
RBDA
图 7 三种改进算法的平均信道数比较
由上图可知，改进算法的平均吞吐量依
次为 RBDA DBFA DCGBAT T T> > ，RBDA吞吐量
最大，DBFA 其次，DCGBA 平均吞吐量相
对最小。但是改进算法的平均信道数依次为
5
CH CH CH
DCGBA RBDA DBFAT T T> > ，DCGBA 所分配的平
均可用信道数最多，RBDA其次，DBFA相
对最少。
5 10 15 20 25 30 35 40
0
5
10
15
20
CR用户数
吞吐
量公
平性
DCGBA
DBFA
RBDA
图 8 三种改进算法的吞吐量公平性比较
5 10 15 20 25 30 35 40
0
20
40
60
80
CR用户数
分
配
信
道
数
公
平
性
DCGBA
DBFA
RBDA
图 9 三种改进算法的信道数公平性比较
由上图可知，三种改进算法的吞吐量公
平性比较后，依次为： DCGBA RBDA DBFAF F F> >
（“ > ”表示“差于”），DBFA吞吐量公平性最
好，RBDA其次，DCGBA最差。
三种算法的分配信道数公平性比较后，
依次为： CH CH CHDCGBA RBDA DBFAF F F> > ，DBFA 信道
数公平性仍然最好，RBDA 其次，DCGBA
最差。
5 10 15 20 25
0
50
100
150
200
250
300
350
400
450
CR用户数
通
信
开
销
CMSB
CMMB
CMPF
DCGBA
DBFA
RBDA
图 10 三种改进算法的通信开销比较
由上图可知，随着 CR用户数的增加，
各算法的通信开销增加。由于 DCGBA需交
互所有用户的链路度数信息，通信开销最
大，对可用信道时变适用性最差；RBDA只
需交互相邻用户信息，通信开销最小，在通
信网络中的时变性最好，复杂度最低，实用
性也就比较好。
6. 结论
本文在感知无线电这一具体环境下，以
吞吐量，公平性以及复杂度为衡量标准，对
CRN中的六种算法进行了比较，并对 DGA，
DFA以及 RDA根据实际情况进行了进一步
的改进，最后仿真分析了三种改进算法的各
方面性能。这些算法在实际网络中，有各自
使用的场景，因而在下一步的研究中可根据
实际网络的参数变化，以及分簇方式等组网
方式的不同，对算法进行适用性的变化。
参考文献：
[1]Haykin S. Cognitive radio: brain-empowered
wireless communications [J], IEEE JSAC, 2005, 23
(2):201-220.
[2] Weiss T A, Jondral F K. Spectrum pooling: an
innovative strategy for the enhancement of spectrum
efficiency [J]. Communications Magazine, 2004,
42(3):8 - 14.
[3]Caili G, Tiankui Z, Zhimin Z, et al. Investigation
on spectrum sharing technology based on cognitive
radio[C]//First International Conference on
Communications and Networking in China
(CHINACOM 2006).
[4] Wei W, Xin L, List-coloring based channel
allocation for open-spectrum wireless
networks[C]//IEEE Fall VTC 2005. 2005:690-694.
[5] H. Zheng, C. Peng, “Collaboration and fairness in
opportunistic spectrum access”, Proc. IEEE ICC 2005,
vol. 5, May2005, pp. 3132–3136.
6
Node-coloring Based Spectrum Allocation in Cognitive
Radio Network
Xue Yu
Institute of Telecommunication Network Technology，Beijing University of Posts and
Telecommunications，Beijing (100876)
Abstract
Opporunity spectrum allocation algorithm of cognitive radio network is studied in this paper. A
spectrum allocation model ，hypothesis and algorithm based on graph coloring theory is proposed. And
the basic fundamental principles and objects of six typical algorithms are analyzed. For these basic
distributed algorithms, three new algorithms are proposed for adapting the real circumstance and
optimizing fairness and overhead . Experimental results show the performance of the new algorithm.
Keywords：cognitive radio network，collaborative spectrum allocation，graph coloring theory，
distributed algorithm
