认知无线电网络中基于拓扑控制的频谱资源分配方法

摘要

本发明提供一种认知无线电网络中基于拓扑控制的频谱资源分配方法，包括：一个执行周期较长的静态分配方法，所述静态分配方法包括：寻找最大节点度最小的生成树的近似算法，根据生成树向网络中的链路分配频带；向与节点相关的最小割集分配附加频带的分配算法；一个执行周期较短的动态分配算法，所述动态分配算法包括：获取当前网络流分布情况；根据分布情况改变频带分配结构，使之满足当前的通信需求。本发明提供的方法能够提高次级用户网络的鲁棒性和容量，具有较低的运算复杂度，优化了认知无线电次级用户网络的性能。

说明书

技术领域

本发明属于通信技术领域，具体地涉及一种认知网络中针对拓扑控制的频谱资源的分配方法。 

背景技术

由于无线设备的大量应用和无线产业的蓬勃发展，作为信息载体的频谱资源被过度使用的情况越来越严重。这一问题在未授权频段上尤为显著，但授权频段却常常未被充分利用。认知无线电被认为是一种具备解决这一问题能力的先进技术。在认知无线电技术中，次级用户（SU,secondary user）可以在主用户（PU,primary user）不使用授权频带的时候动态地接入频带。而次级用户通信的主要前提是次级通信不应该对主用户通信带来过度干扰，于是，在次级用户正在进行通信的同时，主用户尝试接入频谱，可能对主用户施加干扰的次级用户需要立即放弃频谱的使用权。在大多数情况下，我们可以用一个自组织网络来刻画次级用户间的通信。当一部分次级用户放弃接入频谱时，次级用户之间的通信将会受到严重影响。首先，由于主用户通常具有较强的通信功率，其发射天线的通信覆盖范围较大，使得他们可以影响许多次级用户的数据链路。其次，这种影响可能造成一些特定的数据链路停止工作，引起网络分离，即网络的连通性遭到破坏。在这种情况下，次级用户间通信的服务质量（QoS）将会严重下降。所以，我们需要合理地设计次级用户网络中的频带分配策略。 

由于主用户对于次级网络干扰的最主要体现在与次级用户间的数据链路的断开，拓扑控制成为许多之前的工作用以解决这一问题的主要工具。拓扑控制的主要目的在于设计一种将频带分配给数据链路的策略，使得网络容量得到优化的同时，减小乃至消除网络分离的风险。关于拓扑控制的相关工作可以参看文章“Interference-aware topology control and QoS routing in multi-channel wireless mesh networks”（针对无线自组织网络的涉及干扰的拓扑控制以及面向服务质量的路由，ACM Mobihoc2005）以及“Robust Topology Control in Multi-hop Cognitive Radio Networks”（针对多跳认知无线电网络的鲁棒拓扑控制，IEEE INFOCOM2012）。 在目前的工作中，利用K-连通图作为支持网络拓扑的基础结构，可以兼顾网络的鲁棒性和降低次级用户数据链路之间的相互干扰。然而，K-连通图无法保证次级用户能完全防止网络分离。在完全保证连通性的基于鲁棒性检测的拓扑控制机制中，过多的频带被分配了不同的数据链路，网络中的同道干扰现象十分严重，影响网络容量。 

因此，对于认知网络中频谱资源的分配及网络拓扑控制而言，目前亟待解决的一大问题是如何在完全避免网络分离问题的同时，优化网络性能，提高效率。 

发明内容

本发明解决的问题是提供一种运算复杂度低、兼顾认知无线电中次级网络的鲁棒性和网络容量的频谱分配和拓扑控制算法。 

为解决上述技术问题，本发明提供了一种认知无线电网络中基于拓扑控制的频谱资源分配方法，包括步骤：执行一个静态分配步骤A和一个动态分配步骤B，其中，所述静态分配步骤的执行周期长于所述动态分配步骤的执行周期； 

所述静态分配步骤包括如下步骤： 

步骤A1：利用近似算法寻找最大节点度最小的生成树，根据生成树向网络中的链路分配频带，从而使两棵生成树工作在不同频带上； 

步骤A2：向与节点相关的最小割集分配附加频带； 

所述动态分配步骤包括如下步骤： 

步骤B1：获取当前网络流分布情况； 

步骤B2：根据分布情况改变频带分配结构，使频带分配结构满足当前的通信需求。 

优选地，用于寻找最大节点度最小的生成树的近似算法是避免引入圈的贪婪算法。 

优选地，步骤A1包括如下步骤： 

对于每个边给于权值，该权值能够在步骤A1执行过程中变化，具体而言： 

w_i＝c_i+1   （式一） 

其中，w_i为边i的权值，c_i为与边i相邻的边中已经被选入生成树的边的个数。 

在每一步向网络中的链路分配频带中，在不引入圈的前提下选择w_i最小的边加入生成树。 

优选地，所述步骤A2包括如下步骤： 

在分配附加频段时，人为设定某一条边的权值为负无穷大，使得Stoer-Wagner算法 运行的结果必定包含该边，将与某个节点相连的所有边分别设为负无穷，分别运行Stoer-Wagner算法，使得Stoer-Wagner算法运行的结果必定包含该边，从而得到与某个节点有关的最小割集，并对这一最小割集分配额外的频带。 

优选地，所述网络流分布情况包括网络中的源汇节点以及每个数据链路上已被占用的带宽。 

优选地，所述步骤B2包括如下步骤： 

步骤B20：利用Dinic算法确定当前网络中的最小源-汇割集，将空闲的频带分配给最小源-汇割集中的数据链路。 

优选地，所述步骤B20包括如下步骤： 

根据已有的频带分配情况预测新分配的频带可带来的容量增量，具体而言： 

$\mathrm{\Delta C}=\frac{\mathrm{BW}}{\max (d_i\left(u\right),d_i\left(v\right))}$   （式三） 

式中，ΔC为容量增量，d_i(u)为与节点u相邻的使用频带i的边的个数，d_i(v)为与节点v相邻的使用频带i的边的个数，BW为单个频带能支持的数据带宽； 

按以下原则将频带c_i分配给e_m： 

   （式四） 

式中，mS_k为当前最小源-汇割集，C为频带集合，e_m为将要被分配额外频带的边（数据链路）。 

与现有技术相比，本发明的技术方案具有以下优点： 

（1）通过两个工作在不同频带上的生成树作为支撑次级网络通信的骨干，能够保证当授权用户收回一个频道的使用权时，次级用户网络的连通性不被破坏。 

（2）通过最小化生成树中的最大节点度，降低了同道干扰的可能性，增加了网络容量。 

（3）利用Stoer-Wagner和Dinic算法确定网络中通信容量的瓶颈可能的位置，通常是网络中的最小割集，并对其分配额外的频带提高网络的通信性能。 

（4）提高次级用户网络的鲁棒性和容量，具有较低的运算复杂度，优化了认知无线电次级用户网络的性能。 

附图说明

通过阅读参照以下附图对非限制性实施例所作的详细描述，本发明的其它特征、目的和优点将会变得更明显： 

图1是次级用户网络拓扑及频谱分配示意图，左图中的虚线代表次级用户中的数据链路，右图中的实线及对应的数字标明分配给该链路的频带； 

图2是本发明实施方式的认知网络中频谱资源分配及拓扑控制方法的流程示意图； 

图3是本发明实施方式中用来解释近似算法性能的一个例子； 

图4是本发明一实施例在频带总数C＝5，每个节点具备的接口数Q＝3，数据流个数F＝5时，各个算法下次级用户平均数据速率随次级用户数目的变化示意图； 

图5是本发明一实施例在次级用户数N＝20，每个节点具备的接口数Q＝3，数据流个数F＝5时，各个算法下次级用户平均数据速率随频带总数的变化示意图； 

图6是本发明一实施例在次级用户数N＝20，每个节点具备的接口数Q＝3，频带总数C＝5时，各个算法下次级用户平均数据速率随数据流个数的变化示意图； 

图7是本发明一实施例在次级用户数N＝20，每个节点具备的接口数Q＝3，频带总数C＝5，数据流个数F＝5，本发明算法下次级用户平均数据速率随动态分配已进行轮数的变化示意图。 

具体实施方式

下面结合具体实施例对本发明进行详细说明。以下实施例将有助于本领域的技术人员进一步理解本发明，但不以任何形式限制本发明。应当指出的是，对本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进。这些都属于本发明的保护范围。 

正如背景技术所述，授权用户活动给次级用户通信带来的干扰的最显著表现就是次级用户网络中的网络分离现象，而这一现象本质上反映为网络的拓扑结构的变化。因此，针对网络拓扑控制的频谱分配策略能够有效地解决这一问题，降低授权用户活动给次级用户网络带来的干扰。并且，由于网络流容量受网络中最小割集制约，这类频谱分配策略也可以提高网络容量及性能。 

在本发明中，将频谱分配算法分成两个部分。其一是静态分配，主要用来维持网络在受到授权用户干扰时的鲁棒性，主要是利用了两棵工作在不同频带上的生成树，并且为了减小同道干扰提高性能，使用了一个近似算法寻找最大节点度最小的生成树；其二是动态分配，主要是寻找网络中的最小割集并对其分配额外的频带，从而提高网络的流容量。 

为了更好地说明本发明的技术方案，本实施方式中以单个授权用户工作在多个 授权信道上，在任意时刻至多收回一个信道的使用权，并且N个次级用户利用授权信道组成一个自组织网络，而每个次级用户具有M个无线接口的情形为例进行说明。 

图1所示为次级用户网络的数据链路以及频谱分配对于网络拓扑结构影响的示意图。左图中虚线所示为次级用户间的数据链路，而只有当一条数据链路分配到了不少于一条的频带时，数据链路才可以进行通信。一种可能的频带的分配情况由右图所示。图中实线所示为分配给数据链路的频带，实线上的数字标明该频带的编号。注意到，分配给与同一节点相邻的所有边的频带数量受该节点所具有的无线接口数量Q（假设对于所有节点Q都是相同的）限制，而图1所示的分配在Q≥3时是可行的。 

图2是本发明实施方式的认知网络中针对拓扑控制的频谱资源的分配方法的流程示意图，如图2所示，所述认知网络中频谱资源的分配方法包括： 

步骤S11：利用近似算法寻找最大节点度最小的生成树，并分配频带使网络拓扑中有两棵生成树工作在不同频带上； 

步骤S12：向与节点相关的最小割集分配附加频带； 

步骤S13：获取当前网络流分布情况，包括：当前网络流的源汇节点及每条数据链路上已被占用的数据带宽； 

步骤S14：根据步骤S13中获得的网络流分布情况，改变频带分配结构，使之满足当前通信需求，主要通过寻找最小源-汇割集并对其分配额外频带实现。 

以下对上述步骤进行一一说明。 

本实施方式中，PU工作在多个授权频带上。我们假设在任一时刻PU使用的频带数量不超过1，而在PU空闲的时刻，SU可以在任意授权频带上进行通信，并且，所有的频带能支持的数据速率是同样的。当与同一节点相连的多个链路使用同一频道时，这些链路按照时分复用的方式工作。因此我们认为，当一条数据链路被分配了复数个频道时，其能支持的最大数据速率为它被分配的所有频道能支持的数据速率之和。而所谓的网络分离现象是指，当PU收回某一频道时，代表工作在这一频道上的数据链路的边将被移出网络拓扑。网络分离发生当且仅当此时网络的连通分量数大于1。 

参考图1和图2，拓扑控制的主要目的就是通过向数据链路分配特定的频带，控制网络拓扑图的一些性质。首先，我们执行步骤S11。分配频带使得网络中有两 条生成树工作在不同的两个频带上，即对于这两棵生成树中的任意一棵来说，它包含的所有的边均工作在同一频带上，且这两棵树工作的频带不同。在这种情况下，当PU收回任意一个频带时，总有一棵生成树能够维持工作，从而保证了整个网络拓扑的连通性，防止了网络分离现象的发生。并且，考虑到同一棵生成树中同一节点的邻边需要通过时分复用的方式工作，造成这些边的有效数据带宽降低，我们应该最小化该生成树中最大节点度。 

寻找具有最小的最大节点度的生成树已经被证明是NP-hard问题，因此我们提出了一种贪婪的近似算法来解决。算法的执行过程类似用于求最小权值生成树的Kruskal算法，包括以下步骤： 

将每条边的初始权值设为1； 

每一步都将当前权值最小，且不会引入圈的边加入生成树，每加入一条边所有与这条边相邻的边的权值加1； 

当已经加入了N-1条边时算法终止。 

通过运行这个算法，我们可以得到一棵最大节点度较小的生成树。考虑到单个节点损坏可能带来的影响，我们希望第二棵生成树应该在最小化节点度的同时与第一棵生成树具有尽可能大的差异。为此，我们可以将属于第一棵树的初始权值设为2，然后再次执行算法，即可得到另一棵生成树。 

通过对这个算法的分析我们可以证明该算法最终得到的生成树中任意节点的节点度不超过该节点邻点构成的导出子图的连通分量数的3倍，请见图3。 

图3中节点A的邻点导出子图包括节点A₁,A₂,A₃,A₄，以及边A₁A₂。因此其连通分量数为3。这一性质当图趋近稠密（即边的数量接近N²）时尤为有利，因为此时几乎所有的节点邻点导出子图的连通分量都为1。 

执行步骤S12，由于网络流容量主要受限于网络拓扑中的最小割集，对于仍有空闲接口的节点，我们需要找到与其相关的最小割集，然后在可行的位置对这个割集中的边分配新的频带。割集与一个节点相关是指这个割集中的某一条边以该节点为端点。具体而言，我们通过将一个节点的某一条邻边的权值（容量）设为负无穷，然后运行Stoer-Wagner算法保证该边包含在求得的最小割集中。如此，我们遍历一个节点的所有邻边，得到的所有与其相关的割集中权值最小的割集对应的边，并且该边的两端点均有空闲接口的，就是我们要分配附加频带的边。为了减弱同道干扰的影响，用来附加的频带是当前被分配到的数据链路数量最小的频带。 

执行步骤S13，网络的中心节点收集当前网络中网络流的分布情况，包括源汇节点集合、每个数据链路上已经被占用的数据带宽以及每个数据链路上的总数据带宽。相关的数据收集传递机制为现有技术，此处不再展开叙述。需要注意的是，由于我们设计的拓扑控制算法能够保证网络始终连通，因此这个数据收集过程是可靠的。 

执行步骤S14，我们利用Dinic算法求得当前网络流中的最小源-汇割集，记为mS_k，我们将选出mS_k中可能带来最大的流容量增量的链路-频带组合进行分配。具体而言， 

$\mathrm{\Delta C}=\frac{\mathrm{BW}}{\max (d_i\left(u\right),d_i\left(v\right))}$   （式五） 

式中，ΔC为容量增量，d_i(u)为与节点u相邻的使用频带i的边的个数，d_i(v)为与节点v相邻的使用频带i的边的个数，BW为单个频带能支持的数据带宽。我们按以下原则将频带c_i分配给e_m： 

   （式六） 

式中，mS_k为当前最小源-汇割集，C为频带集合，e_m为将要被分配额外频带的边（数据链路）。 

步骤S14执行的周期应该明显小于前三个步骤，从而动态地调整网络拓扑适应当前的通信需求。 

图4是本发明一实施例在频带总数C＝5，每个节点具备的接口数Q＝3，数据流个数F＝5时，各个算法下次级用户平均数据速率随次级用户数目的变化示意图。网络中数据链路的位置按如下步骤给出：次级用户节点均匀随机的分布在一个900×900的方形区域内，次级用户节点的通信距离设为400，相邻的数据链路认为存在相互干扰的可能。用以对照的CRTCA算法与INSTC算法分别出自“Robust Topology Control in Multi-hop Cognitive Radio Networks”（针对多跳认知无线电网络的鲁棒拓扑控制，IEEE INFOCOM2012）以及“Interference-aware topology control and QoS routing in multi-channel wireless mesh networks”（针对无线自组织网络的涉及干扰的拓扑控制以及面向服务质量的路由，ACM Mobihoc2005）。网络路由采用一个简单的最短路径算法。从图6中我们可以看出，另外两个算法的性能随着节点数量的增多而下降，而我们的算法相对稳定。这种现象的原因在于当节点更加稠密时，次级网络中的同道干扰变大，因此CRTCA和INSTC算法性能受到影响。但 是同时，我们提出的算法性能也趋近于最优，抵消了同道干扰的影响。 

图5是本发明一实施例在次级用户数N＝20，每个节点具备的接口数Q＝3，数据流个数F＝5时，各个算法下次级用户平均数据速率随频带总数的变化示意图。因为我们提出的算法可以将分配多余的频带用以提高网络容量，所以当C＞Q时网络容量也能持续增加。 

图6是本发明一实施例在次级用户数N＝20，每个节点具备的接口数Q＝3，频带总数C＝5时，各个算法下次级用户平均数据速率随数据流个数的变化示意图。 

图7是本发明一实施例在次级用户数N＝20，每个节点具备的接口数Q＝3，频带总数C＝5，数据流个数F＝5，本发明算法下次级用户平均数据速率随动态分配已进行轮数的变化示意图。动态分配的确可以提高网络流容量，并且收敛的速度比较快。另外，在所有的实验中，我们的算法性能始终优于另外两个算法。 

综上所述，本发明的技术方案至少具有以下有益效果： 

（1）本发明将网络拓扑控制及频谱分配划分为两个阶段：静态分配和动态分配，可以在保障网络连通性的情况下优化网络性能。 

（2）在静态分配过程中，我们通过构建两棵工作在不同频带上的生成树，能够保障在授权用户只收回某一频带的时候，网络分离现象不会发生。并且，我们通过一个近似算法减小生成树中的最大节点度，尽可能减小同道干扰，增加网络容量。而后，通过分配剩余的频带和接口，进一步提高网络容量。 

（3）在动态分配过程中，我们通过收集当前网络流的分布信息，分配额外的频带从而增加源-汇割集的容量，提高网络性能。 

以上对本发明的具体实施例进行了描述。需要理解的是，本发明并不局限于上述特定实施方式，本领域技术人员可以在权利要求的范围内做出各种变形或修改，这并不影响本发明的实质内容。