一种认知无线电系统中混合并行标准的频谱分配方法

摘要

一种认知无线电系统中混合并行标准的频谱分配方法，本发明涉及一种认知无线电系统中混合并行标准的频谱分配方法。它是为了解决现有并行方法在分配频谱时，每次分配频谱时，没有利用到其他子图上的已分配的频谱信息，导致并行方法公平性差的问题。本方法是指先将一部分子图采用某一标准分配完毕，然后再将剩余子图采用水平并行标准算法进行分配，即先垂直，后水平的并行方式。垂直并行是指先将一部分子图采用协作式最大化总带宽标准分配完毕，然后再将剩余子图采用协作式最大化比例公平标准进行分配；水平并行是指在每一轮的分配过程中一部分子图采用协作式最大化总带宽标准，其余子图采用协作式最大化比例公平标准。本发明适用于无线网络领域。

权利要求

1.一种认知无线电系统中混合并行标准的频谱分配方法，其特征在于：该频谱分配方法包括下述步骤：步骤一、绘制认知无线电系统的拓扑图；

步骤二、把拓扑图分解为N个子图，N为总频谱数；

步骤三、对未分配频谱的Mg个子图进行频谱分配，其中，N≥Mg，Mg为第g轮分配时的子图数，1≤g≤M，其中5≤M≤20；

针对一个待分配的频谱m，对Mg个子图中的Mg*β个子图使用垂直并行标准获得频谱m所在的Mg*β个子图中的每个认知用户的标号值，并将频谱m分配给对应标号值最大的认知用户，其中，β为垂直并行系数，0≤β≤1，其中对Mg*β取整；

其中，所述的对Mg*β个子图使用垂直并行标准获得频谱m所在的Mg*β个子图中的每个认知用户的标号值的具体过程为：步骤三一、将Mg*β*β个子图根据协作式最大化总带宽标准进行频谱分配，在每个子图Gt1=(Vt1,Et1)中选择使标号值label1i,m最大的认知用户user1m，将该频谱m分配给使标号值label1i,m最大的认知用户user1m；

其中，label1i,m表示认知用户i使用频谱m的标号值；user1m表示子图Gt1=(Vt1,Et1)中标号值label1i,m最大的认知用户， Vm表示可用频谱列表中使用频谱m的认知用户的集合，Vt1表示子图Gt1中的认知用户的集合，t1=1,2,…Mg*β*β；其中对Mg*β*β取整，Et1表示子图Gt1中的相邻的一对认知用户之间存在的干扰的集合；

步骤三二、对剩余的Mg*β*（1-β）个子图根据协作式最大化比例公平标准进行频谱分配，在每个子图Gt2=(Vt2,Et2)中选择使标号值label2i,m最大的认知用户user2m，将该频谱m分配给最大的认知用户user2m；

其中，label2i,m表示认知用户i使用频谱m的标号值；user2m表示使标号值label2i,m最大的认知用户； Vt2表示子图Gt2中的认知用户的集合，t2=1,2,…Mg*β*（1-β），其中对Mg*β*（1-β）取整；Et2表示子图Gt2中的相邻的一对认知用户之间存在的干扰的集合；

步骤三一所述的协作式最大化总带宽标准为：

式中Di,m表示与认知用户i相邻且可用频谱列表中含有频谱m的认知用户数目，label1i,m表示认知用户i使用频谱m的标号值，bi,m为认知用户i使用频谱m的信道容量；

步骤三二所述的协作式最大化比例公平标准为：

其中，Di,m表示与认知用户i相邻且可用频谱列表中含有频谱m的认知用户数目；ai,k=1或ai,k=0，ai,k=1表示第k个子图中的频谱m被分配给认知用户i；ai,k=0表示第k个子图中的频谱m未分配给认知用户i；fi,k表示认知用户i使用第k个子图中的频谱m所带来的效益权重；

同时，针对所述待分配的频谱m，对其余Mg*(1-β)个子图使用水平并行标准获得频谱m所在的Mg*(1-β)个子图中的每个认知用户的标号值，并将频谱m分配给对应标号值最大的认知用户，其中对Mg*(1-β)取整；

其中，所述的针对所述待分配的频谱m，对其余Mg*(1-β)个子图使用水平并行标准获得频谱m所在的Mg*(1-β)个子图中的每个认知用户的标号值的具体过程为：对Mg*(1-β)*α个子图根据协作式最大化总带宽标准进行频谱分配，在每个子图Gt1=(Vt1,Et1)中选择使标号值label1i,m最大的认知用户user1m，将该频谱m分配给最大的认知用户user1m；

其中，label1i,m表示认知用户i使用频谱m的标号值；user1m表示子图Gt1=(Vt1,Et1)中标号值label1i,m最大的认知用户， Vt1表示子图Gt1中的认知用户的集合，t1=1,2,…Mg*(1-β)*α，其中对Mg*(1-β)*α取整；Et1表示子图Gt1中的相邻的一对认知用户之间存在的干扰的集合；

同时对剩余的Mg*(1-β)(1-α)个子图根据协作式最大化比例公平标准进行频谱分配，在每个子图Gt2=(Vt2,Et2)中选择使标号值label2i,m最大的认知用户user2m，将该频谱m分配给最大的认知用户user2m；

其中，label2i,m表示认知用户i使用频谱m的标号值；user2m表示使标号值label2i,m最大的认知用户； Vt2表示子图Gt2中的认知用户的集合，t2=1,2,…Mg*(1-β)(1-α)，其中对Mg*(1-β)(1-α)取整；Et2表示子图Gt2中的相邻的一对认知用户之间存在的干扰的集合；α为水平并行系数，0≤α≤1；

步骤四、去掉拓扑图中已分配完成的频谱，更新已分配矩阵；

步骤五、判断频谱分配是否完毕，判断为是，则执行步骤六；判断为否，则执行步骤三；

步骤六、结束频谱分配。

说明书

一种认知无线电系统中混合并行标准的频谱分配方法

技术领域

[0001] 本发明涉及频谱分配方法，具体涉及一种认知无线电系统中混合并行标准的频谱分配方法。

背景技术

[0002] 基于图论着色理论的频谱分配模型在移动蜂窝通信中已经用于分析小区的频率规划和指配，是一种相对成熟的模型。在认知无线电系统中，由于是择机使用授权用户的频谱，认知无线电用户的可用频谱受到授权用户工作状态、位置和覆盖范围的影响，具有空时变化的特性。因此，在认知无线电系统中采用图论着色模型进行频谱分配分析，需要对频谱分配的约束条件，分配目标等进行必要的修订。由于并行方法是把原有的拓扑结构图分解为多个子图，然后在这些子图上进行独立的频谱分配，各子图之间不进行信息的交换，所以每个子图在分配的时候无法考虑到其他子图的分配情况，无法利用到已分配频谱的信息，这是并行方法公平性差的根本原因。

发明内容

[0003] 本发明的目的是为了解决现有并行方法在分配频谱时，每次分配频谱时，没有利用到其他子图上的已分配的频谱信息，导致并行方法公平性差的问题。

[0004] 一种认知无线电系统中混合并行标准的频谱分配方法包括下述步骤：

[0005] 步骤一、绘制认知无线电系统的拓扑图；

[0006] 步骤二、把拓扑图分解为N个子图，N为总频谱数；

[0007] 步骤三、对未分配频谱的Mg个子图进行频谱分配，其中，N≥Mg，Mg为第g轮分配时的子图数，1≤g≤M；

[0008] 针对一个待分配的频谱m，对Mg个子图中的Mg*β个子图使用垂直并行标准获得频谱m所在的Mg*β个子图中的每个认知用户的标号值，并将频谱m分配给对应标号值最大的认知用户，其中，β为垂直并行系数，0≤β≤1，其中对Mg*β取整；

[0009] 同时，针对所述待分配的频谱m，对其余Mg*(1-β)个子图使用水平并行标准获得频谱m所在的Mg*(1-β)个子图中的每个认知用户的标号值，并将频谱m分配给对应标号值最大的认知用户，其中对Mg*(1-β)取整；

[0010] 步骤四、去掉拓扑图中已分配完成的频谱，更新已分配矩阵；

[0011] 步骤五、判断频谱分配是否完毕，判断为是，则执行步骤六；判断为否，则执行步骤三；

[0012] 步骤六、结束频谱分配。

[0013] 本发明为一种认知无线电系统中混合并行标准的频谱分配方法，通过利用其他子图上的已分配的频谱信息，达到了在计算标号时各频谱不全部采用相同的标准，减小单轮分配聚集现象的影响，提高系统公平性的目的。从而提出了一种认知无线系统中并行标准的频谱分配方法。传统的并行算法中，在每一轮计算标号时如果使用同一标准，极有可能产生将大量信道分给同一用户的情况，本文称这种现象为单轮分配聚集现象。

附图说明

[0014] 图1为认知无线电系统的图论模型图，图2为混合并行标准方法流程图，图3为系统公平性随着α和β的变化情况图，图4为系统公平性随着α的变化情况图，其中曲线A表示认知用户数为20和频谱数为10时，系统公平性随着水平并行系数α的变化曲线；曲线B表示认知用户数为10和频谱数为10时，系统公平性随着水平并行系数α的变化曲线；曲线C表示认知用户数为20和频谱数为20时，系统公平性随着水平并行系数α的变化曲线；曲线D表示认知用户数为10和频谱数为20时，系统公平性随着水平并行系数α的变化曲线，图5为最佳α对频谱数和认知用户数的变化规律图，图6为最佳β对频谱数和认知用户数的变化规律图。

具体实施方式

[0015] 具体实施方式一、本发明所述的一种认知无线电系统中混合并行标准的频谱分配方法，它包括下述步骤：

[0016] 步骤一、绘制认知无线电系统的拓扑图；

[0017] 步骤二、把拓扑图分解为N个子图，N为总频谱数；

[0018] 步骤三、对未分配频谱的Mg个子图进行频谱分配，其中，N≥Mg，Mg为第g轮分配时的子图数，1≤g≤M；

[0019] 针对一个待分配的频谱m，对Mg个子图中的Mg*β个子图使用垂直并行标准获得频谱m所在的Mg*β个子图中的每个认知用户的标号值，并将频谱m分配给对应标号值最大的认知用户，其中，对Mg*β取整，β为垂直并行系数，0≤β≤1；

[0020] 同时，针对所述待分配的频谱m，对其余Mg*(1-β)个子图使用水平并行标准获得频谱m所在的Mg*(1-β)个子图中的每个认知用户的标号值，并将频谱m分配给对应标号值最大的认知用户，对Mg*(1-β)取整；

[0021] 步骤四、去掉拓扑图中已分配完成的频谱，更新已分配矩阵；

[0022] 步骤五、判断频谱分配是否完毕，判断为是，则执行步骤六；判断为否，则执行步骤三；

[0023] 步骤六、结束频谱分配。

[0024] 其中步骤四所述的去掉拓扑图中已分配完成的子图，即删除已分配的认知用户对应的频谱，及相邻的一对认知用户之间存在的干扰，更新已分配矩阵，即更新得到频谱分配给认知用户的矩阵。

[0025] 将可用的频谱组成一个频谱池，并将其划分为无交叠的正交频段。假设在一个区域中有I个用户，他们竞争M个频段。每个用户根据自己的几何位置和环境都拥有一个自己的频谱池。认知用户通过频谱感知技术获得他们的环境信息，包括几何位置、发射功率、可用频谱池及相互干扰信息等。每个用户选择合适的通信频谱，调整传送频率，进而避免干扰到授权用户。这就是一个频谱分配问题，即为每一个用户提供可用的频谱来满足他们的数据传输的要求。

[0026] 频谱分配数学模型是建立在相应的干扰和约束条件之上的。在认知无线电系统的图论着色模型研究中，将认知用户组成的网络拓扑结构抽象成图论模型图。在图中，每一个顶点代表一个认知用户，每一条边表示一对顶点间存在的冲突或者干扰，而用颜色表示频谱资源。频谱分配问题就等价于使系统利用效率最大化的顶点着色问题。如果图中的某两个顶点有一条边连接，则代表两个顶点间存在冲突或者干扰，即假定这两个节点不能同时使用相同的频谱资源。另外，将每一个顶点与一个集合相关联，这个集合代表该顶点所在区域位置可以使用的频谱资源。由于每个顶点地理位置的不同，因而不同顶点所关联的资源集合是不同的。

[0027] 图1是一个认知无线电系统的网络拓扑结构的图论模型图。图中的六个顶点su1～su6代表六个不同的认知用户，四个顶点puA～puD代表四个不同的授权用户，且假设各个授权用户使用的授权频段分别是频谱A、频谱B、频谱C和频谱D。虚线圆表示，授权用户工作范围，在此范围内认知用户不能使用授权用户的频段，也就是说认知无线电用户使用授权频段的前提是：如果当前频谱被授权用户使用，则为了避免对授权用户的干扰，这个频谱不能被附近的认知用户使用。

[0028] 统一的图论模型由空闲矩阵，效益矩阵，干扰矩阵和分配矩阵描述。

[0029] 空闲频谱是指在某个时间某个空间授权用户未使用的频谱，通常把空闲频谱分成一系列正交的子频谱，频谱间无干扰。由于空间位置以及传输功率等参数的不同，对于不同的认知无线电用户，同一个频谱空闲与否可能不同。比如在某个授权用户使用某个频谱m时，m对于离授权用户比较近的认知无线电用户可能是无效的，但是对于距离该授权用户足够远的认知无线电用户而言，m是可以视作空闲的。频谱对于认知用户是否空闲用空闲矩阵表示。

[0030] 若同时使用频谱m时两个认知用户之间存在干扰，则它们不可以同时使用频谱m，认知无线电用户间的干扰用干扰矩阵表示。由于用户所处的环境以及采用的调制编码技术可能不同，不同用户在同一个有效空闲频谱上获得的效益不一样，用户获得的效益用效益矩阵表示。

[0031] 假设分配时间相对于环境变化时间来说是很短的，各矩阵在分配周期内维持不变。各矩阵具体定义如下：

[0032] 效益矩阵B＝{bi，m}I×N，bi，m表征认知用户i使用频谱m所带来的效益权重(频谱容量)，I为总用户数，N为总频谱数。将矩阵L与矩阵B相结合，可得出有效频谱的效益LB＝{li，m·bi，m}I×N。

[0033] 干扰矩阵集合C＝{ci，k|ci，k∈{0，1}}I×I，ci，k＝1表示认知用户i和认知用户k在同时使用相同频谱时会产生干扰，当i＝k时，ci，k＝0。

[0034] 无干扰的频谱分配矩阵A＝{ai，m|ai，m∈{0，1}}I×N，ai，m＝1表示频谱m被分配给认知用户i。A必须满足无干扰条件：

[0035]

[0036] 引入了每个频段的效益，可以得到以最大化频谱效益为目标的最优分配标准(Max-Sum-Bandwidth，MSB)的表达式，相应地系统达到最大频谱效益的数学表达式变为：

[0037]

[0038] 式中ΛI×N——所有满足条件的无干扰频谱分配矩阵A的集合。

[0039] 表达式的物理含义是频谱分配为系统带来的最大频谱效益，效益矩阵通常代表用户在各个频谱上所能获得的传输速率。

[0040] 为了比较不同方法的公平性，方法还引入了有关频谱分配公平性的度量标准，即最大比例公平性度量(Max-Proportional-Fair，MPF)：

[0041]

[0042] 子图定义：设G＝(V1，E1)和H＝(V2，E2)是两个图，若满足 且 则称H是G的子图。特别地，当V2＝V1时，称H是G的生成子图；当 或 时，称H是G的真子图。

[0043] 具体实施方式二、本实施方式与具体实施方式一所述的一种认知无线电系统中混合并行标准的频谱分配方法的区别在于：步骤三所述的对Mg*β个子图使用垂直并行标准获得频谱m所在的Mg*β个子图中的每个认知用户的标号值的过程为：

[0044] 步骤三一、将Mg*β*β个子图根据协作式最大化总带宽标准

[0045] (Collaborative-Max-Sum-Bandwidth，CMSB)进行频谱分配，在每个子图Gt1＝(Vt1，Et1)中选择使标号值label1i，m最大的认知用户user1m，将该频谱m分配给使标号值label1i，m最大的认知用户user1m；

[0046] 其中，label1i，m表示认知用户i使用频谱m的标号值；user1m表示子图Ct1＝(Vt1，Et1)中标号值label1i，m最大的认知用户， Vt1表示子图Gt1中的认知用户的集合，t1＝1，2，…Mg*β*β；Et1表示子图Gt1中的相邻的一对认知用户之间存在的干扰的集合；

[0047] 步骤三二、对剩余的Mg*β*(1-β)个子图根据协作式最大化比例公平标准(Collaborative-Max-Proportional-Fair，CMPF)进行频谱分配，在每个子图Gt2＝(Vt2，Et2)中选择使标号值label2i，m最大的认知用户user2m，将该频谱m分配给最大的认知用户user2m；

[0048] 其中，label2i，m表示认知用户i使用频谱m的标号值；user2m表示使标号值label2i，m最大的认知用户； Vt2表示子图Gt2中的认知用户的集合，t2＝1，2，…Mg*β*(1-β)；Et2表示子图Gt2中的相邻的一对认知用户之间存在的干扰的集合。

[0049] 具体实施方式三、本实施方式与具体实施方式一所述的一种认知无线电系统中混合并行标准的频谱分配方法的区别在于：步骤三所述的对Mg*(1-β)个子图使用水平并行标准进行频谱分配的方法为：

[0050] 步骤三六、对Mg*(1-β)*α个子图根据协作式最大化总带宽标准进行频谱分配，在每个子图Gt1＝(Vt1，Et1)中选择使标号值label1i，m最大的认知用户user1m，将该频谱m分配给最大的认知用户user1m；

[0051] 其中，label1i，m表示认知用户i使用频谱m的标号值；user1m表示子图Gt1＝(Vt1，Et1)中标号值label1i，m最大的认知用户， Vt1表示子图Gt1中的认知用户的集合，t1＝1，2，…Mg*β*β；Et1表示子图Gt1中的相邻的一对认知用户之间存在的干扰的集合；

[0052] 同时对剩余的Mg*(1-β)(1-α)个子图根据协作式最大化比例公平标准进行频谱分配，在每个子图Gt2＝(Vt2，Et2)中选择使标号值label2i，m最大的认知用户user2m，将该频谱m分配给最大的认知用户user2m；

[0053] 其中，label2i，m表示认知用户i使用频谱m的标号值；user2m表示使标号值label2i，m最大的认知用户； Vt2表示子图Gt2中的认知用户的集合，t2＝1，2，…Mg*β*(1-β)；Et2表示子图Gt2中的相邻的一对认知用户之间存在的干扰的集合；α为水平并行系数，0≤α≤1。

[0054] 具体实施方式四、本实施方式与具体实施方式二或具体实施方式三的区别在于：协作式最大化总带宽标准为：

[0055]

[0056] 式中Di，m表示与认知用户i相邻且可用频谱列表中含有频谱m的认知用户数目，label1i，m表示认知用户i使用频谱m的标号值，bi，m为认知用户i使用频谱m的信道容量。

[0057] 具体实施方式五、本实施方式与具体实施方式四的区别在于：协作式最大化比例公平标准为：

[0058]

[0059] 其中，Di，m表示与认知用户i相邻且可用频谱列表中含有频谱m的认知用户数目；ai，k＝1或ai，k＝0，ai，k＝1表示第k个子图中的频谱m被分配给认知用户i；ai，k＝0表示第k个子图中的频谱m未分配给认知用户i；bi，k表示认知用户i使用第k个子图中的频谱m所带来的效益权重。

[0060] 在混合并行标准方法中，垂直并行并行系数β定义为每一轮计算标号的时候使用CMSB标准的子图数与该轮分配时的总子图数之比。当β＝0时，所有子图均采用CMPF标准，此时垂直并行标准方法等价于改进方法的CMPF标准；当β＝1时，所有子图均采用协作式最大化总带宽标准，此时垂直并行标准方法等价于改进方法的协作式最大化总带宽标准。水平并行系数α定义为每一轮计算标号的时候使用协作式最大化总带宽标准的子图数与该轮分配时的总子图数之比。当α＝0时，所有子图均采用协作式最大化比例公平标准；当α＝1时，所有子图均采用协作式最大化总带宽标准。

[0061] 为了分析混合并行系数对系统公平性的影响，对系统公平性随水平并行系数和垂直并行系数的变化情况进行仿真。每种情况下随机生成1000个拓扑图，其结果如图3所示。

[0062] 从图3可以看到，对于认知用户数I为10，频谱数M为20的情况，水平并行系数α和β在0～1之间存在一个使得系统公平性最大的极值，对于不同的情况，使公平性最大的极值也不尽相同。

[0063] 不同认知用户数和不同频谱数时的最佳α和β不同，且没有明显的规律性，所以为了在下文的仿真中确定不同情况的最佳α和β，本文将认知用户数在5到20之间依次取值，频谱数在5到20之间依次取值的时候的最佳α和β值求出，混合并行标准方法的最佳水平并行系数见附录表1，混合并行标准方法的最佳垂直并行系数见附录表2[0064] 本方法考虑一下的三个方面。

[0065] (1)协作式认知用户总效益。

[0066]

[0067] (2)协作式系统公平性。

[0068]

[0069] (3)通信开销。在仿真中，假设每次分配循环的执行时间为一个时间单位，即相邻两次更新拓扑图的时间间隔为一个时间单位，因此方法的时间开销为方法循环次数乘以时间单位，完全由方法的循环次数决定。

[0070] 以水平并行标准方法为例，寻找并行系数的确定方法。水平并行系数α定义为每一轮计算标号的时候使用CMSB标准的子图数与该轮分配时的总子图数之比。

[0071] 为了分析水平并行系数对系统公平性的影响，对以下四种情况下系统公平性随水平并行系数的变化情况进行仿真。α取不同值时的平均系统公平性

[0072] (1)认知用户数为10，频谱数为10；

[0073] (2)认知用户数为10，频谱数为20；

[0074] (3)认知用户数为20，频谱数为10；

[0075] (4)认知用户数为20，频谱数为20。

[0076] 每种情况下随机生成1000个拓扑图，计算α取不同值时，1000个拓扑图的系统公平性的平均值，其结果如图4所示。

[0077] 从图4可以看到，对于某一固定情况，水平并行系数α在0～1之间存在一个使得系统公平性最大的极值，对于不同的情况，使公平性最大的极值也不尽相同。例如对于情况(2)，当α＝0.22时，使系统的公平性最大。事实上，如果进行多次的仿真，就可以发现，即使对于某一固定的情况，由于其拓扑结构的随机性和随机产生的拓扑数的有限性，使其公平性最大的α的极值也不是相同的。例如对于情况(2)，按照上述方法求α的极值，重复试验50次，其结果如图5所示。

[0078] 从图5中可以看到，α的极值并不是固定的，在不同的试验中其取值不同。但α的极值也不是连续变化的，而是在几个值之间取值，因此，为了确定某一情况下的α的极值，在该种情况下多次求解α的极值，然后取诸多数值中的众数作为该种情况的最佳α。例如在图5所示的试验中，α的极值取0.22的试验出现34次，取0.3的试验出现6次，取
0.19的试验出现3次，取其他值的试验出现7次，因此认为情况(2)的最佳α为0.22。

[0079] 由于不同认知用户数和不同频谱数的情况的最佳α也不同，在认知用户数为5到20的情况下，以及频谱数固定为20的情况下最佳α随着认知用户数的变化规律进行了仿真，其结果如图5所示。同理可得混合标准方法中垂直并行标准中，认知用户数为5到20的情况下，以及频谱数固定为20的情况下最佳β的情况，如图6所示。

[0080] 不同认知用户数和不同频谱数时的最佳α不同，且没有明显的规律性，所以为了在下文的仿真中确定不同情况的最佳α，本文将认知用户数在5到20之间依次取值，频谱数在5到20之间依次取值的时候的最佳α值求出，并将其列表保存，以备后文仿真时使用。混合并行标准方法的水平并行系数最佳α取值表见附录表1。

[0081] 附录表1

[0082]

[0083] 附录表1续

[0084]

[0085]

[0086] 附录表2

[0087]

[0088] 附录表2续

[0089]

[0090]