当前位置:首页 >> 信息与通信 >>

认知无线电中的并行频谱分配算法


第 29 卷第 7 期 2007 年 7 月















Vol.29No.7 Jul.. .2007

Journal of Electronics & Inf

ormation Technology

认知无线电中的并行频谱分配算法
廖楚林






唐友喜

李少谦
成都 610054)

(电子科技大学通信抗干扰技术国家级重点试验室

要:该文通过对基于图论着色原理的开放式频谱分配算法的分析,提出了一种并行分配算法。在最大化系统

效益的准则下,并行算法可以得到与 CSGC (Color Sensitive Graph Coloring)算法相同的分配矩阵,但是却可以 缩短分配周期,从而适应了认知无线电对环境的快速感知的要求。仿真结果分析验证了结论的正确性。 关键词:认知无线电;开放式频谱分配;图论着色;并行算法 中图分类号:TN915.65 文献标识码:A 文章编号:1009-5896(2007)07-1608-04

Parallel Algorithm of Spectrum Allocation in Cognitive Radio
Liao Chu-lin Chen Jie Tang You-xi Li Shao-qian
(National Key Laboratory of Communication, University of Electronic Science and Technology of China, Chengdu 610054, China) Abstract: A parallel allocation algorithm is proposed, which is a modification of CSGC (Color Sensitive Graph Coloring)algorithm. Under constraint of maximizing system utilization, the parallel algorithm obtains the same allocation matrix as CSGC, while reducing the allocation period, so that it can be adapted to the agile sense requirement of cognitive radio. Results of simulation and analysis prove this conclusion. Key words: Cognitive radio; Open spectrum allocation; Graph-coloring; Parallel algorithm

1

引言
随着无线应用的不断拓展, 频谱资源的缺乏成为无线应

测 PU 当时未使用的频谱资源放入频谱池中共享。 空闲频谱检测是认知无线电中的一项关键技术,目前已 经有一些成果[5, 6],本文讨论的是在SU检测完成后,空闲频 谱资源在SU之间的分配。为了平衡SU之间的干扰和整个系 统的效益,文献[7]提出一种基于图论着色理论的择机频谱接 入算法——CSGC (Color Sensitive Graph Coloring)算法, 在避免SU间干扰的前提下最大化系统效益。 但是该算法分配 完成的时间随着空闲频谱数的增多而增加,不适应认知无线 电中空闲频谱快速时变的要求。本文提出一种并行分配算 法, 避免了空闲频谱数对算法分配时间的影响, 在获得CSGC 算法相同分配效益的同时,减少了频谱分配的时间,满足了 空闲频谱实时变化的要求。 本文的其余部分是这样安排的,第2节分析了频谱分配 的图论着色的数学模型;第3节阐述了并行算法的基本原理, 并从理论上证明了并行算法分配时间开销与空闲频谱数的 无关性;第4节给出了数值和仿真结果;最后是本文的结论。

用研究过程中不得不面临的问题, 但是从一些研究结果可以 看到, 频谱资源的缺乏更多是由于无线接入技术的利用不合 理引起的。 现有不同无线通信系统分配频谱的方法主要是基 于固定分配方式, 即某一无线频谱块分配给某一特定的无线 接入网络,然后再把这个无线频谱块分为若干个频谱子块, 这些频谱块大小固定, 相互之间间隔一个固定大小的保护频 段,分配给具有 license 资格的不同运营商,只有这些运营 商的 license 期满之后才可以分配给其他用户。这种固定分 配的方式虽然对于频谱管理非常简单容易, 但是存在频谱利 用率低的缺点, 例如大多数通信网络在设计之初都是基于该 网络可能最大的传输流量进行考虑,但是实际情况却是,通 信网络并非全天满负荷运行,根据文献[1]可以知道,频谱资 源在不同位置不同时间段的利用有所不同, 这种静态的频谱 分配方式造成了频谱资源的浪费。为了解决这个问题,基于 对认知无线电的研究[2, 3],人们提出一种开放式频谱接入机 制 ——在授权用户(主用户,Primary User, PU)未使用该频 谱资源时,允许未授权用户(次用户,Secondary User, SU)在 不对 PU 造成干扰的情况下,使用原来分配给 PU 的频谱资 源。SU 通过使用认知无线电技术实时感知周围的环境,检
2005-12-09 收到,2006-07-10 改回 国家 863 高技术研究发展计划(2005AA123910)和国家自然科学基 金(60496313)资助课题
[4]

2

频谱分配模型
空闲频谱是指在某个时间某个空间 PU 未使用的频谱,

2.1 假设与定义 本文把空闲频谱分成一系列正交的子频带,频带间无干扰, 频谱对于 SU 是否空闲用空闲矩阵表示。 若同时使用频带 m 时两个 SU 之间存在干扰,则它们不可以同时使用频带 m, SU 间的干扰用干扰矩阵表示。用户获得的效益用效益矩阵 表示。假设分配时间相对于环境变化时间来说是很短的,各

第7期

廖楚林等: 认知无线电中的并行频谱分配算法

1609

矩阵在分配周期内维持不变。各矩阵具体定义如下。 N (1)空闲频谱矩阵 L = {ln,m | ln,m ∈ {0,1}}N ×M , 为用户 数(下标从 0 到 N?1),M 为总频带数(下标从 0 到 M?1), ln ,m = 1 表示频带 m 对于用户 n 是可用的, ln ,m = 0 表示不 可用。 (2)效益矩阵 B = {bn ,m }N ×M ,bn,m 表征用户 n 使用频带 m 所带来的效益权重, 如频谱利用率等。 将矩阵 L 与矩阵 B 相结合,可得出有效频谱的效益 LB = {ln,m ? bn,m }N ×M 。 (3) 干 扰 矩 阵 集 合 C = {cn ,k ,m | cn ,k ,m ∈ {0,1}}N ×N ×M , cn ,k ,m = 1 表示用户 n 和用户 k 在同时使用频带 m 时会产生 仅由空闲频谱矩阵 L 决 干扰, n=k 时,cn ,n,m = 1 ? ln,m , 当 定。 (4)无干扰的频谱分配矩阵 A= {an,m| an,m∈ {0,1}}N ×M ,

图 G 的拓扑是由点集和边集确定的,在给定顶点数的 边集是由干扰矩阵集合 C 情况下, 边集决定了图 G 的拓扑。 决定的,集合中一共有 M 个干扰矩阵:C m = {cn ,k ,m | cn,k ,m

∈ {0,1}}N ×N

(0 ≤ m ≤ M ? 1) ,每个矩阵对应用户复用一

个频带 m 时的干扰。由第 2 节干扰矩阵的定义可知,干扰 矩阵中对角线元素只由空闲矩阵决定, C m 中对角线元素

ci,i,m = 1 表示频带 m 对用户 i 来说不可用, 在描述 SU 在频
当 带 m 的干扰时该用户可以不考虑。 ci,i,m = 1 时把 C m 的第

i 行第 i 列删除,可以得到一个对角线元素为 0 的 lm 1 阶 0, 1 二元对称矩阵 C m 。其中 lm 为空闲矩阵 L 的列向量, L = (l 0 l1
[8]

lm

lM ?2 lM ?1 ) , lm

1

为 lm 的向量范数。

由图论 的知识可以知道, C m 满足简单标号图的邻接矩阵 的条件,每个 C m 唯一对应一个简单标号图,可以由 C m 得 到以 C m 为邻接矩阵的 M 个简单标号图 G 0 的干扰关系。 定义 r (n, m ) 表示在某个目标准则下某个循环阶段用户

an,m = 1 表示频带 m 被分配给用户 n。 必须满足无干扰条 A
件:

GM ?1 , 它们

是图 G 的导出子图,每个子图分别表征一种颜色下各用户

an,m ? ak ,m = 0,

cn ,k ,m = 1, ?n, k < N , m < M

(1)

满足式(1)条件的 A 很多, ΛN ,M 表示所有满足条件的无干 用 扰频谱分配矩阵 A 的集合。 我们的分配目标是无干扰的前提下最大化频谱利用率:
N ?1 M ?1 A∈ΛN , M

n 使用频带 m 带来的目标效益。 r (n, m ) 与本文初始定义的
效益矩阵 B 有所不同,在本文假设中,效益矩阵 B 在整个 分配周期内是不变的,而 r (n, m ) 除了受效益矩阵 B 的影响 外,还与分配的目标准则有关,并且可能受到拓扑的影响。 在 N M S B 准 则 下 r (n, m ) = bn,m , 在 C M S B 准 则 下

max

n =0 m =0

∑ ∑ an,m ? bn,m

(2)

这里效益矩阵代表用户在各个频带上所能获得的传输 速率。 2.2 图论着色模型 把上述频谱分配抽象为一个图 G = (U , EC , LB ) 的着色。
U 是图 G 的顶点集,表示共享频谱的次用户, LB 表示顶点

r (n, m ) = bn ,m /(Dn,m + 1) ,其中 Dn ,m 表示在频带 m 与用户 n 有干扰的用户个数,在图 G 中表现为与顶点 n 以 m 色边
相连的邻接顶点数。另外定义 Nbr(n, m ) = {k | ck ,n,m = 1,
0 ≤ k ≤ N ? 1, k ≠ n } , 表示在频带 m 与用户 n 有干扰的用

可选颜色集合(list)和权重,EC 是边集,由干扰约束集合 C 决定, 当且仅当 cn ,k ,m = 1 时, 两个不同的顶点(用户) u, v ∈ U 之间有一条颜色为 m(频带 m)的边。于是满足式(1)条件的 无干扰频谱分配对应的着色条件可以描述为: 当两个不同顶 点间存在 m 色边的时候这两个顶点不能同时着 m 色。 为了达到式(2)的分配目标, 文献[7]中给出了两种分配准 则 : 协 作 的 最 大 化 总 带 宽 (Collaborative- Max-Sum-

户的集合,在图 G 中表现为与顶点 n 以 m 色边相连的邻接 以子图 Gm 着 顶点集, 集合 Nbr(n, m ) 元素的个数就是 Dn ,m 。 色为例, r (n, m ) 描述的并行分配算法流程图如图 1 所示: 由 并行算法的基本原理就是同时对 M 个子图着色,由于 各个子图都是简单图,对图 G 的 list 着色可以简化为对 M

Bandwidth, CMSB) 准则和 非协作的最大化总带宽 (Noncollaborative-Max-Sum-Bandwidth, NMSB)准则。CSGC算
法根据分配准则对顶点进行标号(Labeling),标号大小表征 了某个分配循环阶段的顶点的价值。然后根据标号大小对图
G 进行list着色,每次循环选择标号最大的顶点分配对应的

颜色。

3

并行分配算法
CSGC 算法中图 G 是一个复合图,存在重边,着色算

3.1 基本原理 法也是较为复杂的带权重的 list 着色算法。本文通过对有关 矩阵的处理,把图 G 分解为多个简单图,把 list 着色简化为 对多个简单图的点着色。
图 1 并行分配算法流程示意图

1610

电 子 与 信 息 学 报
表 1 仿真参数 用户数(节点数)N 频带数(颜色数)M 空闲矩阵 L 效益矩阵 B 分别取 6,12

第 29 卷

个子图的点着色。基于频带正交假设,对某个频带的使用不 会对其他频带造成干扰, 即对某个子图的颜色分配不会影响 到其他子图的颜色分配, 并且从图 1 的流程图可以看出子图 的拓扑更新不影响其他子图的拓扑, 因此在整个着色算法过 程中,各个子图着色是相互独立的,并行算法可以得到与

从[1,30]依次取值 全部元素等于 1 元素取值为[1,N]中随机选取 的自然数 各矩阵为随机生成的 0,1 二元对称矩阵 1 微秒

CSGC 相同的最优分配矩阵 A 。
3.2 并行算法开销 为了简化比较,假设每次分配循环的执行时间均为 T , 完全 这样算法总的分配时间开销等于算法循环次数乘以 T ,

干扰矩阵集合 C 每个分配循环执行时间 T

CSGC 算法每一次循环得到一个点 由算法的循环次数决定。
对(i , j),i 为该循环阶段图 G 中最大标号的顶点,j 为分配给

配矩阵),限于篇幅,所得分配矩阵未在这里列出。图 2 是

N 取两种取值时, 两种算法在相应准则下的分配时间开销随
频带数 M 的增加而变化的曲线。从图中可以看到,CSGC 算法的时间开销随着 M 的增加近似呈线性的增加,而并行 算法的时间开销不受 M 的影响,随着 M 的增加,并行算法 的时间开销近似呈一条水平线,与 3.2 节的结论相符。另外 这是因 可以看到并行算法的时间开销存在上界—— T × N 。 为分配矩阵 A 是 0,1 二元矩阵,并行算法的最大循环次数
N ?1

i 的颜色。对应最优分配矩阵 A 中的元素 ai, j = 1 , 于是 CSGC 算法的循环次数为矩阵 A 的矩阵范数 A m 1 :
LOOP = A m 1 =
N ?1 M ?1 i =0 j =0

∑ ∑ ai , j

(3)

下面分析空闲频带数对循环次数的影响。 把最优分配矩 阵 A 写成如下向量的形式:

? a 0,0 … a1,M ?1 ? ? ? ? ? ? ? ?= a a ? ? A=? 0 1 ? ? ? ? ?a ? ? N ?1, 1 aN ?1,M ?1 ? ? ? ?

(

aM ?2 aM ?1

)

为 Max
0≤ j ≤M ?1

aj

1

= Max

0≤ j ≤M ?1 i = 0

∑ ai, j ≤ ∑ 1 = N 。当 M 增加到
i =0

N ?1

比较大的数目时,并行算法的时间开销明显低于 CSGC 算 法的时间开销。

则 LOOP = A m 1 =

M ?1 j =0

∑ aj 1
1 1

a j 为矩阵 A 的列向量, a j 为 a j 的向量范数, a j 表
征了复用第 j 个频带的用户数,根据空闲频谱的定义,至少 有一个用户可以使用空闲频谱资源, 所以 a j 数 M 的增多而增加。 并行算法同时对 M 个子图进行着色,每个子图得到的 子图 Gm 分配结果分别为最优分配矩阵 A 中的一个列向量, 的循环次数为 am 1 。由于每个子图的分配是同时进行的, 所有子图均分配完成的时间开销为 T × Max
a j ,小于
1

1

>0。 由以上

CSGC 算法的循环次数将随着空闲频谱 分析可以得出结论,

图 2 CSGC 与并行算法的开销比较

CSGC 算法的开销 T × ∑ a j
j =0

M ?1

0≤ j ≤M ?1 1

5

结束语
认知无线电系统通过快速感知周围的频谱使用情况, 使

,当所有 am 1 都相等时,开

销可以降低为原来的 1/M, 大大缩短了分配周期, 有利于实 现快速频谱分配。 另外可以看到并行算法的开销与频带数 M 无关,有利于实现大量频谱的分配。

用授权用户未使用的空闲频谱,从而提高频谱利用率。为了 保证不对授权用户造成干扰, 要求对频谱的检测信息必须可 靠。但是授权用户是否使用频谱是一个随机过程,随时都可 能有新的授权用户占用新的频谱资源, 检测信息的可靠性随 信息更新周期的增加而减弱, 因此在进行频谱分配算法设计 时,应尽量考虑缩短分配的周期,分配的周期越短,在相同 的检测技术下的检测信息就越可靠。 本文提出了开放式频谱 接入的并行分配算法,与 CGSC 算法相比,简化了拓扑结 构, 在得到相同的最优分配的同时降低了分配算法的时间开 销,缩短了分配时间,更适应认知无线电中快变的环境,而 且并行算法的分配时间与待分配的频谱数目无关, 更适用于 含有大量频谱的频谱池[9]的频谱分配。数值和仿真结果分析

4

数值与仿真结果分析
下面对 CMSB 和 NMSB 准则下的 CSGC 和并行算法进

行 仿 真 , 结 果 分 别 用 CSGC-CMSB , CSGC-NMSB ,

Parallel-CMSB 和 Parallel-NMSB 表示。为了简化分析,假
设空闲频谱对所有 SU 均可用,图 G 的拓扑随机生成,每次 分配循环的执行时间 T 均为 1 μs。具体仿真参数见表 1。 仿真得到的两种算法在相同准则下的最优分配矩阵相 同,由于分配矩阵较多(每一个(N, M)的组合均对应一个分

第7期 验证了本文的结论。

廖楚林等: 认知无线电中的并行频谱分配算法

1611

detection and false alarm probability in spectrum pooling

参 考 文 献
[1] Federal Communications Commission. Spectrum policy task force report. ET Docket 02-135, November 2002. Available at: http://www.fcc.gov/sptf/ [2] Mitola J. Cognitive radio for flexible mobile multimedia communications J] Mobile Networks and Applications, 2001, [ . 6(5): 435–441. [3] Federal Communications Commission. Facilitating opportunities for flexible, efficient and reliable spectrum use employing cognitive radio technologies. FCC-03-322, ET Docket No. 03-108, 2003. [4] DARPA XG working group RFC. rfc vision.pdf. [5] Cabric, D, Mishra, S M, and Brodersen, R W. Implementation issues in spectrum sensing for cognitive radios. Thirty-Eighth Asilomar Conference on Signals, Systems and Computers, California USA, 2004, 1: 772–776. [6] Hillenbrand J, Weiss T A, and Jondral F K. Calculation of The XG Vision.

systems. IEEE Communications Letters, 2005, 9(4): 349–351. [7] Zheng H and Peng C. Collaboration and fairness in opportunistic spectrum access. In Proc. 40th annual IEEE International Conference on Communications (ICC), Seoul, Korea, May 2005, 5: 3132–3136. [8] [9] 张先迪,李正良. 图论及其应用. 北京:高等教育出版社, 2003, 第一章. Weiss T, Hillenbrand J, and Jondral F. Spectrum pooling: an innovative strategy for the enhancement of spectrum efficiency. IEEE, Communications Magazine, 2004, 42(3): S8 –S14.

廖楚林: 陈 劼:

男,1982年生,硕士生,研究领域为宽带无线接入新技 术. 女,1973年生,博士生,副教授,主要研究领域为移动 通信新技术、协议标准与移动性管理. 男,1964年生,教授,博士生导师,主要研究领域为 MIMO、OFDM、UWB等. 男,1956年生,教授,博士生导师,主要研究领域为移 动通信与无线通信、宽带无线接入、抗干扰通信技术.

Available from http://www.darpa.mil/ato/programs/ XG/

唐友喜: 李少谦:


相关文章:
认知无线电系统中频谱分配综述
认知无线电系统中频谱分配综述》总结 2009 年第 3 期 电信 1101 臧瑞真 (一) 、摘要:问题:现有频谱利用率效率很低需要改善。分析:通过分析频谱分配的特点...
认知无线电频谱分配的研究
选择和其在非合作频谱分配中的应用做了详尽的探讨; 而在基于图论着色原理的开放式频谱分配算 法中,该节证明了这种并行分配算法更能适应认知无线电快速频谱分配的...
认知无线电频谱分配的博弈论方法
解决问题方法: 建立合适的认知无线电频谱分配问题的博 弈论框架,从而促进无线...2.3.2 分析:在频谱分配算法设计过程中,设计了大量的策略选择问题,因此需要提出...
在遮蔽衰弱环境下认知无线电网络的高效频谱分配算法
在遮蔽衰弱环境下认知无线电网络的高效频谱分配算法_互联网_IT/计算机_专业资料。...三、在遮蔽衰弱环境下节点的连通性 这篇文章中,使用了一个简单模型来描绘连通...
数据通信认知无线电系统的频谱分配方法
14 1 一种认知无线电系统的频谱分配方法 摘 要: 认知无线电网络为移动用户...认知无线电中的并行频谱分配算法. 电子与信息 学报, 2007, 29(7): 1608-...
认知无线电频谱分配技术及其应用分析
认知无线电频谱分配技术及其应用分析_电力/水利_工程科技_专业资料。华中科技大学 毕业论文认知无线电频谱分配技术 及其应用分析题 目: 认知无线电频谱分配技术及其应用...
认知无线电网络中的频谱分配技术研究
配技术的两种分配类型, 在接下来的第三和第四章节中详细 论述了本论文完成的工作, 主要 就认知无线电的频谱分配算法和需 要进行频谱分配用户的分簇机制进行了深入...
基于多目标禁忌搜索算法的认知无线电频谱分配
22 期 【摘要】 针对认知无线电动态频谱分配问题,建立图着色频谱分配模型,将模型中的分 配矩阵和禁忌搜索算法中的可行解相对应,提出基于禁忌搜索的智能求解算法。同...
认知无线电网络系统的频谱分配研究
中稳定婚姻问题的认知无线电频谱配对算法:通过建模给出了认知用户对频谱、 以及 频谱对认知用户的偏好优先级准则,再通过配对算法达到运算的收敛,最后实现频谱的分配。...
一种结合信道性能的频谱分配算法
网 http://www.qikan.com.cn 一种结合信道性能的频谱分配算法 作者:张伟卫 赵知劲 王海泉 来源:《现代电子技术》2010 年第 23 期 摘要:在认知无线电网络中,...
更多相关标签:
认知无线电频谱感知 | 并行算法导论 | 算法与并行计算 | 并行算法 | 并行算法的设计与分析 | 并行算法实践 | 并行算法实践 pdf | 并行遗传算法 |