一种基于二叉排序树的局部议价的频谱分配方法

摘要

一种基于二叉排序树的局部议价的频谱分配方法，所述方法包括：在初始时刻，将扫描到的频谱划分为若干个信道，并将所述信道按照从小到大的升序顺序构建一个单支二叉排序树；然后利用分配算法对用户进行信道分配，获取分配矩阵，并根据所述分配矩阵更新二叉排序树上每个节点上的用户；在下一个时间周期，根据扫描频谱的变化对二叉排序树进行更新，同时根据申请信道用户的变化进行信道的重新分配；重复进行上述过程，直至收到停止扫描频谱命令。本发明的方法对整个频段扫描的结果是树的形式，只需要对二叉排序树进行插入和删除，就可以实现频谱分配；节省了分配时间；在频谱资源紧缺的情况下，提高了频谱的利用率，同时还可以提高用户的满意度。

说明书

技术领域

本发明属于认知无线电技术领域，具体的，本发明涉及一种基于二叉排序树的 局部议价的频谱分配方法。

背景技术

认知无线电技术主要包括频谱检测、频谱分配、频谱切换和功率控制这几个关 键技术。

由于分配给主用户的授权频段是在特定时间、频率和地理位置的资源。所以检 测到空闲频谱，对于不同的认知用户而言，是时间、频率和空间上动态变化的资源。 频谱检测的目的是辨识出当前次用户可用于认知无线通信的授权信道。

空闲频谱的动态变化特性决定了认知无线网络必须采取动态频谱分配方式才能 满足不断变化的认知用户对频谱的需求以及认知用户(也称次用户)与主用户的频 谱共享。认知无线网络在为次用户进行动态频谱分配时须保证次用户不能对已授权 频段内主用户正常通信造成干扰。在这样的前提下，次用户的可用频谱随着主用户 对授权频段占用情况的变化而动态变化。频谱分配算法就是用来确定哪些次用户可 以接入网络以及如何分配这些次用户才能实现系统吞吐量得到最大化的最优分配。 频谱分配算法是在频谱检测既知的前提下进行的。频谱分配算法基于三个模型，其 中一个较为典型的常用模型就是图论模型。它将用户抽象成为点，而将用户间的彼 此干扰表示为两点之间的线。基于图论模型有许多算法，其中颜色敏感图论着色 (CSGC)是较为常见的算法。CSGC算法假设在一个周期内用户不发生变化。该算 法将扫描到的频谱信息转化为可用信道矩阵，将扫描到的拓扑结构转化为干扰矩阵 和分配矩阵，用来进行频谱分配，直到可用信道被分配完毕。如若在多个周期计算 分配结果的话，需要按照单次步骤，多次调用该分配函数。

局部议价的频谱分配方法是一种改进的CSGC方法，该方法能够将由于用户的 移动性导致拓扑结构发生变化的模型，自组织成谈判小组并自适应形成最优分配模 型。与忽略既知分配信息的传统最优化拓扑模型相比，此方法的计算量显著减少。 局部议价的频谱分配方法的整个过程：每完成一个周期的频谱分配，各个次用户重 新搜索整个频段并感知主用户占用的信道，若出现主用户使用该信道，则需让已经 分配该信道的次用户及时退出信道占用。将感知到的信道转化成由二进制数组组成 的矩阵——可用信道矩阵，分别表示各个用户能否使用该信道的情况。将感知到的 主用户和次用户的位置和发射功率转化为二进制干扰约束矩阵，进而利用标签准则 进行频谱分配。分配结果用二进制分配矩阵表示，它表征着各个用户得到频谱与否 的状况。当冲突图发生变化时，这个自适应算法与传统的CSGC算法相比，不需要 重新分配频谱，只需补偿移动特性导致的局部区域的微小变化。当感知到变化的结 点是主用户时，更新已分配矩阵，使占用该主用户授权频谱的次用户分配矩阵变为0。 而当次用户加入已形成的拓扑图中时，使得原来理想的分配结构被打乱，邻接节点 和插入节点就会自适应的构成冲突图，自组成议价小组，在小组内改变分配方式， 达到最大化频谱利用率的目的。

局部议价的频谱分配方法相对于传统的CSGC方法可以大大节省频谱分配时间； 但是该方法并没有考虑用户需求这个因素，使得按照分配法则分配完所有的可用频 谱之后，倘若有新的用户申请使用该频谱时才贡献多余频谱。这些本来不是用户需 求的频谱，在分配过程中占用了一定的分配时间，该方法需要在议价申请和自组织 成为议价小组过程中又占用一部分时间，无疑会增加时间消耗，甚至会使本来用以 减少参与分配用户数来降低时间开销的优势被淹没；而且在该方法中，倘若感知到 的频谱分配信息是以图的形式出现，需要转化成为二进制可用信道矩阵，这样无疑 会耗用额外的分配时间。

发明内容

本发明的目的在于克服现有局部议价的频谱分配方法存在的分配时间过长、没 有考虑用户需求导致分配不合理的缺陷，提出了一种基于二叉排序树的局部议价的 频谱分配方法，该方法考虑到用户需求，将扫描到的频谱构建二叉排序树，用于进 行频谱的分配和共享，该方法具有节省频谱分配时间，提高频谱利用率的特点。

为了实现上述目的，本发明提供了一种基于二叉排序树的局部议价的频谱分配 方法，所述方法包括：在初始时刻，将扫描到的频谱划分为若干个信道，并将所述 信道按照从小到大的升序顺序构建一个单支二叉排序树；利用分配算法对用户进行 信道分配，获取分配矩阵，并根据所述分配矩阵更新二叉排序树每个节点上的用户； 在下一个时间周期，根据扫描频谱的变化对二叉排序树进行更新，同时根据申请信 道用户的变化进行信道的重新分配；重复进行上述过程，直至收到停止扫描频谱命 令。

上述技术方案中，所述方法具体包括：

步骤1)在初始时刻，将扫描到的频谱进行划分得到多个信道，并将所述信道按 照从小到大的升序顺序构建一个单支二叉排序树；

步骤2)根据系统吞吐量最大的目标，利用分配算法对用户进行信道分配，获取 分配矩阵，并根据所述分配矩阵更新二叉排序树每个节点上的用户；

步骤3)令k＝1；

步骤4)对频谱进行扫描；根据扫描后频谱的变化对二叉排序树进行更新，同时 根据次用户的变化重新进行信道的重新分配；

步骤5)令k＝k+1，转入步骤4)；直至收到停止扫描频谱命令。

上述技术方案中，所述步骤2)具体包括：

步骤201)将用户需求大于可用信道数目的用户需求置为0，同时将其标签值置 为0；统计所有用户需求数目小于自身可用频谱总数的用户总数；

步骤202)计算每个信道中获得最大标签值的用户；挑选出该用户，将此信道分 配给该用户；

对于每个信道m,由于用户列表和干扰约束关系随着其它信道处理不断发生变 化；因此信道的干扰也会不断变化；用户n使用信道的干扰值为：

$R_{n,m}=\underset{k=1,k\ne n}{\overset{N}{\Sigma }}{c}_{n,k,m}$

其中，当用户使用信道时，如果用户共享该信道且不产生干扰，则c_n,k,m＝0； 若产生干扰，则c_n,k,m＝1；1≤n≤N,1≤m≤M,M为信道总数；

选择协作式最大比例公平准则对用户进行标签；标签号大小由目标函数和效益 权重共同决定，标签号越大被分配的优先权越高；在标签准则中，每个标签号对应 一种颜色，表征着用户取得最大标签值时占用的信道；用户的最大标签值为：：

${\mathrm{lable}}_n=max\frac{{\gamma }_n·\frac{b_{n,m}}{R_{n,m}+1}}{\underset{n=1}{\overset{N}{\Sigma }}{1}_{n,m}·b_{n,m}}$

颜色值为：

${\mathrm{color}}_n=\mathrm{argmax}\frac{{\gamma }_n·\frac{b_{n,m}}{R_{n,m}+1}}{\underset{n=1}{\overset{N}{\Sigma }}{1}_{n,m}·b_{n,m}}$

其中，γ_n表示用户需求数目小于可用信道总数的用户，b_n,m表示效益矩阵，由 信道的通信质量和调制方式确定，该矩阵每个时间周期都会进行更新；l_n,m表示用户 的可用信道矩阵，它是由次用户的地理位置决定的；

步骤203)计算分配矩阵a_n,m，使系统的吞吐量达到最大；

$f=max\underset{n=1}{\overset{N}{\Sigma }}\underset{m=1}{\overset{M}{\Sigma }}{a}_{n,m}·{\gamma }_n·b_{n,m}$

步骤204)按照所述步骤203)的分配矩阵a_n,m更新二叉排序树上每个节点的信 息。

上述技术方案中，所述步骤4)具体包括：

步骤401)对已经划分好的频谱进行扫描，判断信道是否发生变化，如果有变化， 进入步骤402)；否则，进入步骤406)；

步骤402)判断是否有新信道产生，如果判断结果是肯定的，转入步骤403)； 否则，转入步骤405)；

步骤403)在二叉排序树上找到新信道对应节点的位置，在二叉排序树上插入新 结点；并判断是否有次用户申请信道，如果判断结果是肯定的，转入步骤404)；否 则，转入步骤5)；

步骤404)将新信道分配给申请信道的次用户，利用步骤2)的分配算法重新计 算分配矩阵a_n,m，并由此更新二叉排序树上每个节点的信息；转入步骤5)；

步骤405)在二叉排序树上找到减少的信道对应节点的位置，从二叉排序树上删 除此节点；并将所述分配矩阵a_n,m中该节点对应的元素置为0；

步骤406)判断是否有次用户申请信道，如果判断结果是肯定的，转入步骤407)； 否则，转入步骤5)；

步骤407)判断次用户能否与其获得信道上的用户共享该信道且不产生干扰；如 判断结果是肯定的，则次用户可以使用该信道，否则，转入步骤5)。

本发明的优点在于：

1、本发明的方法对整个频段扫描的结果是树的形式，只需要对二叉排序树进行 插入和删除，不需要重新构建拓扑图，就可以实现频谱的分配；节省了分配时间。

2、当冲突图发生变化，本发明的方法不用判断是主用户还是次用户，直接启用 频谱共享；提高了用户满意度；

3、每次重新对整个频谱进行扫描时，本发明的方法只需要对变化的频谱进行操 作，在频谱资源紧缺的情况下，提高了频谱利用率；

4、本发明的方法通过考虑用户需求并且结合二叉排序数的存储结构将频谱池中 的空闲信息存储起来，实现每次搜索整个频段就对二叉排序树的节点进行添加或者 删除，既节省了时间又提高了用户满意度。

附图说明

图1为本发明的基于二叉排序树的局部议价的频谱分配方法的流程图；

图2为本发明的实施例中的模拟信道示意图；

图3为局部议价的频谱分配方法与本发明的方法在条件最好情况下100次时间 消耗平均值的比较图；

图4为局部议价的频谱分配方法与本发明的方法在条件最坏情况下100次时间 消耗平均值的比较图；

图5为局部议价的频谱分配方法与本发明的方法在用户满意度上的比较图；

图6为在相同用户个数条件下局部议价的频谱分配方法与本发明的方法在时间 消耗上的比较图。

具体实施方式

在传统的局部议价的频谱分配方法中，如果感知到的频谱分配信息是以图的形 式出现，则需要转化成为二进制可用信道矩阵，这种方式无疑会耗用额外的分配时 间，如果能直接利用感知到的图进行分配会更省时。

本发明的方法是在搜索的频段以二叉排序树的形式表示的情境下进行研究的。 二叉排序树中每个结点表示一个信道。与每个节点相关联的是由能够使用该信道的 多个用户的集合。当完成一次分配，分配结果就会被反映到二叉排序树上来。当再 次搜索整个频段，获得主用户回收对该授权信道占用申请时，二叉排序树就会将相 应频段所代表的结点插入。同样，当搜索到主用户释放授权频段就在二叉排序树上 对应的节点插入。冲突图要发生变化时，只能是次用户申请加入某些频谱的使用， 可以利用频谱共享算法实现。

频谱池是一个从不同的频谱拥有者那里合并空闲频谱到一个公共池子中的租赁 系统。通过这一个公共的频谱池，用户可以在空闲的授权频段中暂时租用频谱资源。 在频谱池中，对授权用户的授权系统的空闲子带进行周期性的检测并提供二进制分 配向量是个非常重要的环节。当完成周期性检测后，多个移动终端会把结果汇聚到 接入点(AP)。接入点需要利用“或”运算，集合所有的单独检测出的二进制分配向 量，以达到对授权用户安全性最大化保护的目的。

通过AP接入点处理后，以频点方式对整个空闲频谱分割并排序，此时如果接收 到关于空闲频谱的二进制分配向量以二叉排序数的方式存在，那就不用将其转化为 关于用户节点的拓扑图，而直接利用该二叉排序树就可以进行频谱分配。

假设之前没有分配信息，根据二叉排序树所表达的空闲矩阵，利用一次基于需 求的CSGC算法(也可以是并行算法)进行频谱分配，获得频谱分配信息。

当移动终端二次扫描整个频段时，将扫描结果与上一次的扫描结果相比较，若 有新的空闲频谱产生，则将该频段所表示的节点插入到二叉排序树中，若主用户出 现时，要回收授权频段，就在二叉排序树中的对应频谱节点上进行信道删除。之前 被分配信道的用户可以和其他用户一样，参与到频谱分配中来。重新构建拓扑图从 而利用任意算法分配频谱。当网络结构发生变化时，新的次用户插入到拓扑结构中 来，不用重新构建新树。由于二叉排序树的每个结点都与所分配的用户结点相关联。 依据这些关联信息，快速找到获得该信道的结点，新节点在局部范围与已分配的结 点共享频谱，倘若共享会产生干扰则等待下一次拓扑更新。

下面结合附图和具体实例对本发明做进一步详细地说明。

如图1所示，一种基于二叉排序树的局部议价的频谱分配方法，所述方法包括：

步骤1)在初始时刻,将扫描到的频谱进行划分得到M个信道，并将所述信道按 照从小到大的升序顺序构建一个单支二叉排序树；

步骤2)根据系统吞吐量最大的目标，利用分配算法对用户进行信道分配，获取 分配矩阵，并根据所述分配矩阵更新二叉排序树上每个节点上的用户；具体包括：

步骤201)将用户需求大于可用信道数目的用户需求置为0，同时将其标签值置 为0；统计所有用户需求数目小于自身可用频谱总数的用户总数N；

此过程可以确保用户需求大于可用信道数目的用户不参与频谱分配过程；

步骤202)计算每个信道中获得最大标签值的用户；挑选出该用户，将此信道分 配给该用户；

对于每个信道m(1≤m≤M，M为信道总数)；由于用户列表和干扰约束关系 随着其它信道处理不断发生变化；因此信道的干扰也会不断变化；用户n(1≤n≤ N)使用信道的干扰值为：

$R_{n,m}=\underset{k=1,k\ne n}{\overset{N}{\Sigma }}{c}_{n,k,m}$

其中：当用户使用信道时，如果用户共享该信道且不产生干扰，则c_n,k,m＝0； 若产生干扰，则c_n,k,m＝1；

选择协作式最大比例公平准则对用户进行标签；标签号大小由目标函数和效益 权重共同决定，标签号越大被分配的优先权越高；在标签准则中，每个标签号对应 一种颜色，表征着用户取得最大标签值时占用的信道；用户的最大标签值为：

${\mathrm{lable}}_n=max\frac{{\gamma }_n·\frac{b_{n,m}}{R_{n,m}+1}}{\underset{n=1}{\overset{N}{\Sigma }}{1}_{n,m}·b_{n,m}}$

颜色值为：

${\mathrm{color}}_n=\mathrm{argmax}\frac{{\gamma }_n·\frac{b_{n,m}}{R_{n,m}+1}}{\underset{n=1}{\overset{N}{\Sigma }}{1}_{n,m}·b_{n,m}}$

其中，γ_n表示用户需求数目小于可用信道总数的用户，b_n,m表示效益矩阵，由信道 的通信质量和调制方式确定，该矩阵每个时间周期都会进行更新；l_n,m表示用户的可 用信道矩阵，它是由次用户的地理位置决定的。

步骤203)计算分配矩阵，使系统的吞吐量达到最大；

$f=max\underset{n=1}{\overset{N}{\Sigma }}\underset{m=1}{\overset{M}{\Sigma }}{a}_{n,m}·{\gamma }_n·b_{n,m}$

其中，a_n,m为分配矩阵；

步骤204)按照所述步骤203)的分配矩阵更新二叉排序树上每个节点的信息；

步骤3)令k＝1；

步骤4)对频谱进行扫描；根据扫描后频谱的变化对二叉排序树进行更新，同时 根据次用户的变化重新进行信道的分配；具体包括：

步骤401)对已经划分好的频谱进行扫描，判断信道是否发生变化，如果有变化， 进入步骤402)；否则，进入步骤406)；

步骤402)判断是否有新信道产生，如果判断结果是肯定的，转入步骤403)； 否则，转入步骤405)；

步骤403)在二叉排序树上找到新信道对应节点的位置，在二叉排序树上插入新 结点；并判断是否有次用户申请信道，如果判断结果是肯定的，转入步骤404)；否 则，转入步骤5)；

步骤404)将新信道分配给申请信道的次用户，利用步骤2)的分配算法重新计 算分配矩阵a_n,m，并由此更新排序树上每个节点的信息；转入步骤5)；

步骤405)在二叉排序树上找到减少的信道对应节点的位置，从二叉排序树上删 除此节点；并将所述分配矩阵a_n,m中该节点对应的元素置为0；

步骤406)判断是否有次用户申请信道，如果判断结果是肯定的，转入步骤407)； 否则，转入步骤5)；

步骤407)判断次用户能否与其获得信道上的用户共享该信道且不产生干扰；如 判断结果是肯定的，则次用户可以使用该信道，否则，转入步骤5)

若共享产生干扰，但又没有新频段产生，该次用户等候下次扫描，直到有新信 道产生；

步骤5)令k＝k+1，转入步骤4)；直至收到停止扫描频谱命令。

下面对本发明的方法的性能进行分析。

由于传统的局部议价的频谱分配方法是在固定用户和固定信道数的条件下进行 的，而本发明的方法采取的随机变化的信道数目和用户数目条件下进行，为了使得 两者具有可比性，将传统的局部议价的频谱分配方法的用户数目每次加1，与本发明 方法的条件接近。

传统的局部议价的频谱分配方法在频谱分配之前，每扫描一次，进行一次排序。 可近似看为本发明方法的直接插入排序。当它插入某个元素时，要与前面的n-1个已 经排好顺序的元素逐个进行比较，直到找到插入位置后才进行插入。

从时间方面来看，如果扫描到的结果按照从小到大的顺序排列，新插入的结点 只需要进行n次比较，0次交换位置；而如果最坏情况出现：当扫描到的结果按照倒 序排列，要进行的比较次数(CN)和交换次数(EN)如式(6)和式(7)：

$CN={\Sigma }_{i=2}^{n}i=\frac{(n+2)(n-1)}{2}\approx \frac{n^2}{2}---\left(6\right)$

$EN={\Sigma }_{i=2}^n(i+1)=\frac{(n+4)(n-1)}{2}\approx \frac{n^2}{2}---\left(7\right)$

传统的局部议价的频谱分配方法扫描频谱时利用的是直接插入排序方式，其时 间复杂度为O(n²)。而本方明的方法使用的排序方法实质上是一种快速排序递归方 法；它以第一个元素为基准，将整个序列划分成为左右两个枝树，只要码值小于基 准元素，都以左枝树方式插入到基准元素左侧，而码值大于基准元素的，都作为右 枝树形式插入基准元素右侧。因此本发明的方法的时间复杂度为：

$T\left(n\right)=\left(\begin{array}{cc}O\left(1\right)& n\le 1\\ \Gamma \left(n\right)& n\ge 2\end{array}\right)---\left(8\right)$

其中n表示序列中元素个数，为对N个元素进行一次快速比较所耗时间。快速 排序法排序时间取决于树的深度。最理想的情况就是基准元素的左子树与右子树有 相同的深度，此时算法耗用的时间为：

T(n)≤O(nlog₂n)    (9)

可以证明本发明方法的平均时间复杂度为O(nlog₂n)。就平均时间复杂度而言， 本发明的方法的性能更加优良。

下面对本发明的方法进行仿真验证。

对于1.5-3GHz的频段，仿真时将该频段平均分成10段，成为10个信道A-J。 随机产生信道的占用情况。首先假设信道的占用是以单支二叉排序树的形式给出的， 其随机产生的模拟信道如图2所示，该图明表了授权信道的占用状况。

当再次扫描的频谱占用情况时候，只将发生变化的信道所对应的结点代码反映 到该单支二叉排序树上。即如果有主用户出现要回收相应的空闲频谱，则对该单支 二叉排序树响应的结点进行删除；而如果有新的空闲频段加入频谱池，则对该单支 二叉排序树进行结点插入。这样避免了重新构建二叉排序树的时间，同时也避免了 传送整个信道占用信息而占据的多余存储空间。

如图3所示，在最好情况下即频谱池中的空闲频谱不发生变化时候，本发明的 频谱分配方法随着循环次数的增加时，时间消耗并没有增多；原因是本发明的方法 在原有分配模型的基础上另外寻找可供新加入节点可共享的频谱，仿真时每次增加 一个，可看作整个时间是相近的。然而传统的方法需要每次新加入一个结点就要构 建一次拓扑图，随着新加入用户的增多，而信道数目不发生变化所以时间消耗要随 着增大。

如图4所示，最坏情况是指每次扫描频谱都会有授权信道使用发生变化，而且 在每个扫描周期，都有新用户申请使用信道。这样，在表征授权信道占用情况的二 叉排序树上要添加或者删除结点。并且在局部议价时，新节点要判断能否和已分配 信道的用户共享该频谱，若不能共享，还需要重新将新的空闲频谱分配给该用户， 所以较直接分配频谱信息要消耗更长的时间。但考虑到一般情况下，频谱池的空闲 频谱在一段时间内保持不变的几率要大，所以本发明的方法在这种情况下较传统的 局部议价法更为节省时间。

由于本发明的方法是在考虑了用户需求后对传统的局部议价的频谱分配方法进 行改进，所以需要在相同存储结构条件下，可对时间消耗和频谱利用率进行比较。 如图5所示，在次用户数目为10时，本发明的方法的平均用户满意度较传统的方法 高。如图6所示，由于用户需求得到满足就会停止对该用户进行继续分配；因而当 信道数目越充足时，所耗用时间越多；而当信道数目比较少、频谱资源比较紧缺时 候，本发明的方法和传统的方法都有较少的分配时间。