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

和非协作的最大化总带宽(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