电子论文-认知无线电中的并行频谱分配算法

电子论文-认知无线电中的并行频谱分配算法

本文由烤鸭的幸福贡献

pdf文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。

第 29 卷第 7 期 2007 年 7 月

电

子

与

信

息

学

报

Vol.29No.7 Jul.. .2007

Journal of Electronics & Information 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

引言

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

时未使用的频谱资源放入频谱池中共享。空闲频谱检测是认知无线电中的一项关键技术，目前已经有一些成果[5, 6]，本文讨论的是在SU检测完成后，空闲频谱资源在SU之间的分配。为了平衡SU之间的干扰和整个系统的效益，文献[7]提出一种基于图论着色理论的择机频谱接入算法——CSGC (Color Sensitive Graph Coloring)算法，在避免SU间干扰的前提下最大化系统效益。但是该算法分配完成的时间随着空闲频谱数的增多而增加，

电子论文-认知无线电中的并行频谱分配算法

不适应认知无线电中空闲频谱快速时变的要求。本文提出一种并行分配算法，避免了空闲频谱数对算法分配时间的影响，在获得CSGC 算法相同分配效益的同时，减少了频谱分配的时间，满足了空闲频谱实时变化的要求。本文的其余部分是这样安排的，第2节分析了频谱分配的图论着色的数学模型；第3节阐述了并行算法的基本原理，并从理论上证明了并行算法分配时间开销与空闲频谱数的无关性；第4节给出了数值和仿真结果；最后是本文的结论。

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

2005-12-09 收到，2006-07-10 改回国家 863 高技术研究发展计划(2005AA123910)和国家自然科学基金(60496313)资助课题

2

频谱分配模型

空闲频谱是指在某个时间某个空间 PU 未使用的频谱，

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

第7期

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

1609

矩阵在分配周期内维持不变。各矩阵具体定义如下。 (1)空闲频谱矩阵 L = {ln,m | ln,m ∈ {0,1}}N ×M ，为用户 N 数(下标从 0 到 N1)，M 为总频带数(下标从 0 到 M1)， 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 时会产生干扰， n＝k 时，cn,n,m = 1 ln ,m ，当仅由空闲频谱矩阵 L 决定。 (4)无干扰的频谱分配矩阵 A= {an,m| an,m∈ {0,1}}N ×M ， an,m = 1 表示频带m 被分配给用户 n。必须满足无干扰条 A 件：

图 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个简单标号图 G0 的干扰关系。定义 r (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 准则下 r (n, m ) = bn,m /(Dn ,m + 1) ，其中 Dn ,m 表示在频带 m 与用户 n 有干扰的用户个数，在图 G 中表现为与顶点 n 以 m 色边相连的邻接顶点数。另外定义 Nbr(n, m ) = {k | ck ,n,m = 1, 表示在频带 m 与用户 n 有干扰的用 0 ≤ k ≤ N 1, k ≠ n } ，户的集合，在图 G 中表现为与顶点 n 以 m 色边相连的邻接顶点集，集合 Nbr(n, m ) 元素的个数就是 Dn ,m 。以子图 Gm 着色为例， r (n, m ) 描述的并行分配算法流程图如图 1 所示：由并行算法的基本原理就是同时对 M 个子图着色，由于各个子图都是简单图，对图 G 的 list 着色可以简化为对 M

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

max

n =0 m =0

∑∑ an,m bn,m

(2)

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

U 是图 G 的顶点集，表示共享频谱的次用户， LB 表示顶点

可选颜色集合(list)和权重，EC 是边集，由干扰约束集合 C 决定，当且仅当 cn ,k ,m = 1 时，两个不同的顶点(用户) u, v ∈ U 之间有一条颜色为 m(频带 m)的边。于是满足式(1)条件的无干扰频谱分配对应的着色条件可以描述为：当两个不同顶点间存在 m 色边的时候这两个顶点不能同时着 m 色。为了达到式(2)的分配目标，文献[7]中给出了两种分配准则：协作的最大化总带宽 (Collaborative- Max-SumBandwidth, 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 的流程图可以看出子图的拓扑更新不影响其他子图的拓扑，因此在整个着色算法过程中，各个子图着色是相互独立的，并行算法可以得到与 CSGC 相同的最优分配矩阵 A 。 3.2 并行算法开销为了简化比较，假设每次分配循环的执行时间均为 T ，完全这样算法总的分配时间开销等于算法循环次数乘以 T ，由算法的循环次数决定。 CSGC 算法每一次循环得到一个点对(i , j),i 为该循环阶段图 G 中最大标号的顶点，j 为分配给 i 的颜色。对应最优分配矩阵 A 中的元素ai, j = 1 ,于是 CSGC 算法的循环次数为矩阵 A 的矩阵范数 A m 1 ：

LOOP = A m 1 =

N 1 M 1 i =0 j =0

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

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

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

N 1

∑∑ ai , j

(3)

下面分析空闲频带数对循环次数的影响。把最优分配矩阵 A 写成如下向量的形式： a 0,0 … a1,M 1 = a a A= 0 1 a N 1, 1 aN 1,M 1

(

a M 2 a M 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

a j 为矩阵 A 的列向量， a j 为 a j 的向量范数， a j 表

1 1

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

j =0 M 1

0≤ j ≤M 1

1

由以上 >0。

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

图2

CSGC 与并行算法的开销比较

a j ，小于

1

5

结束语

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

1

，当所有 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/

唐友喜：李少谦：

1

本文来源：https://www.bwwdw.com/article/0f61.html