认知无线电网络资源分配的公平方法

吕臻 代磊

摘  要：随着无线通信需求的增加，有限的频谱成为一项关键挑战。传统上，某些频段是为特定目的而分配的，并且只能由被许可的用户访问，该策略导致频谱利用率低下。虽然认知无线电网络可以缓解频谱稀缺问题，但节点仍然需要争夺资源，因此频谱的公平分配是一个重要的考虑因素。我们希望找到一种认知无线电网络资源分配的公平方法，并达到吞吐量和公平性的均衡性能。

关键词：认知无线电网络;资源分配;公平方法

中图分类号：TN925      文献标识码：A 文章编号：2096-4706（2019）10-0056-04

Abstract：With the increasing demand of wireless communication，limited spectrum becomes a critical challenge. Traditionally，certain bands are allocated for specific purpose，and can only be accessed by licensed users. This policy leads to the inefficiency utilization of spectrum. Although cognitive radio network can alleviate spectrum scarcity problem，nodes still need to contend for resources，hence fair allocation of spectrums is an important consideration. We hope to find a method for cognitive radio network fair resource allocation and to reach a balanced performance of throughput and fairness.

Keywords：cognitive radio network;resource allocation;fair approach

1  相关工作

许多研究人员研究了认知无线电网络中的公平资源分配。我们的工作基于一种称为多通道竞争图（MCCG）的新模型[1]。通过使用多信道竞争图，节点之间的干扰和竞争可以用无向图表示。文献[2]提出了集中式认知无线电网络的通用调度模型，并研究了几种实现公平资源分配的機制，包括最大最小公平、加权最大最小公平和比例公平。文献[3]研究了图论中的最大独立集问题，并提出了一种贪心算法。文献[4]评估了最小度贪婪算法（Minimum-degree Greedy Algorithm）的性能，并提出了一种分布式算法。我们发现贪心算法在公平资源分配中的缺点，并提出了一种提高公平性的新算法。文献[5]分析了与无线网络公平性相关的广泛问题，并总结了各种现有的模型和方法。文献[6]提出了一个广泛使用的指标，称为Jain指数。文献[7]提出了衡量公平度的五个公理，并基于这些公理评估了各种广泛使用的公平度量的表现。

2  问题定义

2.1  什么是公平

公平是一个抽象的概念，具有广泛的含义。从网络的角度来看，公平意味着无线电频谱是平等分配的;时隙是公平分配的;所有节点都有机会访问网络资源。同时，公平也是一个模糊的术语，缺乏明确的评估标准。考虑三种情况：在第一种情况下，有五个节点，A，B，C，D和E争用100 Mbps带宽，每个节点分配20Mbps带宽。我们可以说这种分配是公平的。在第二种情况下，一个节点分配30Mbps带宽，三个节点分配20Mbps带宽，一个节点分配10Mbps带宽。在第三种情况下，三个节点各分配25Mbps带宽，一个节点分配20Mbps带宽，一个节点分配5Mbps带宽。显然，这两种情况不公平，但如何比较这两种情况？哪一个相对更为公平？为了比较和评估网络的性能，我们需要一个度量来量化公平性。

2.2  指标的要求

文献[7]提出了一个好的指标应该满足的要求：

（1）度量标准应该满足连续性，换句话说，分配方案的轻微变化导致公平指数轻微变化。

（2）度量标准应与测量值和量级无关，这意味着测量单位的选择不会对公平指数产生影响。

（3）度量标准应与规模无关。该指数可用于任意数量的节点，并且不受节点数量的干扰。

2.3  测量选择

基于上述三个要求，我们使用Jain指数来衡量公平性。Jain指数由文献[6]提出，这是一个评估公平性的知名指数。Jain指数被定义为：

我们采用的另一个指标是同样被广泛应用的熵（entro-py）。熵首先由Shannon提出。它定义为：

3  假设

我们考虑这样一个场景，其中给定数量的节点随机分布在一个区域中。在认知无线电网络中，每个节点可以访问多个信道。但是，一个节点一次只能访问一个通道。另外，节点不能同时发送和接收信号。一个节点仅向一个特定用户传输信息。如果两个节点将信号发送到同一节点，则会发生干扰。

我们假设所有节点的传输功率都是固定的，因此所有节点都覆盖相同的范围。我们进一步假设所有通道具有相同的增益，并且所有接收器具有相同的性能，因此每个节点的干扰范围是相同的。在我们的测试中，我们假设干扰范围是传输范围的两倍。如果两个节点彼此靠近，虽然它们在两个不同的信道上发送信号，但它们仍然会相互干扰，这是不允许的。

我们还假设存在中央服务器，其负责感测频谱利用和分配信道资源。每个节点都可以向中央服务器发送请求，告知服务器他们的流量需求和最低需求。服务器根据干扰、信道利用率、节点需求做出决策。一旦服务器获得方案，它将向所有节点广播控制消息，并且节点将立即对控制消息做出反应且没有延迟。

4  互不干扰用户对搜索算法

最重要的问题之一是找到不互相干扰的用户对，以便它们可以同时传输数据。我们采用文献[1]提出的多通道竞争图来解决这个问题。

基于多通道竞争图，干扰可以表示为无向图。如果用户对彼此干涉，则相应的顶点通过边连接。换句话说，如果没有连接两个顶点，则相应的用户对可以同时通信。因此，识别不出相互干扰的用户对可以等价转换为在竞争图中搜索独立集。

4.1  独立集的选择

另一个问题是如何找到独立的集合。图中存在大量独立集（Independent Set）。随着顶点数的增加，独立集的数量呈指数增长。找到所有独立集是不必要的，我们只需要找到能够提高吞吐量和公平性的独立集。我们假设，如果可以同时激活更多用户对，吞吐量将更高，分配将更公平。为了实现这一目标，我们需要一种能够找到包含尽可能多的用户的独立集的算法。文献[1]提出了一种启发式算法来寻找最大独立集。最大独立集是满足这样性质的一个集合——加入图中任何额外的定点得到的新集合都不再是独立集。

4.2  基本贪心算法

4.2.1  算法描述

我们的第一个贡献是使用极大独立集（Maximal Independent Set）而非最大独立集（Maximum Independent Set）来识别不相互干扰的用户。最大独立集是一个独立集，具有最大可能的大小。最大独立集同时也是一个极大独立集，但极大独立集未必为最大独立集。找到最大独立集NP完全问题。没有算法可以在多项式时间内获得精确解。因此，找到严格的解决方案并不适用于实践，相反，我们使用贪婪算法来获得近似解。

设M表示给定图G的邻接矩阵，MIS表示最大独立集。基本贪心算法表示如表1所示。

算法1的每次迭代都可以找到一个最大独立集，j指示算法迭代的次数。算法迭代的次数越多，找到的最大独立集就越多。

4.2.2  算法1的缺点

我们的第二个贡献是发现基本贪心算法的缺点，这可能会对公平性产生负面影响。我们分析了算法1的结果。有时在获得几个最大独立集之后，我们发现一些用户不包括在任何一个最大独立集中。就是说，这些用户始终处于非活动状态，因此没有任何传输数据的机会。

算法1可以找到三个不同的最大独立集，即A=（1，2，3），B=（1，3，4）和C=（1，2，4）。用户对5不包括在三组中的任何一组中。因此，中央服务器不会将信道资源分配给用户对5，它将无法传输任何数据。显然这是不公平的分配方案。

我们进一步检查这些非活动点，发现这些点具有相对较大的度或者它们与具有最小度的点相邻。因此，它们在算法1的第一步就会被被移除。例如：在上面的情况中，对应于用户对5的顶点的度为7并且它与对应于用户对1的顶点相邻，且代表用户对1的点度为3，是所有点中最小的，用户对5将首先被移除。

我们得出结论，找到包含这些非活动点的最大独立集是不可能的。为了覆盖每个用户，我们提出算法2。

4.3  优化的贪婪算法

我们的第三个贡献是提出一种可以覆盖所有顶点的新算法。虽然找到包含那些非活动点的最大独立集是不可能的，但我们可以找到极大独立集。

算法2可以找到包含任何给定顶点的极大独立集。MIS1表示最大独立集，MIS2表示极大独立集，T是存储每次迭代结果的矩阵，优化的贪婪算法如表2所示。

算法2返回包含多個独立集的集合并将结果存储在矩阵中。矩阵的每一行代表一个独立的集合。每个用户对至少被算法2覆盖一次。

5  用户动态最低需求

另一个贡献是提出每个用户的动态最低需求（Dynamic Minimum Demand Of Each User）以提高公平性。DMD算法基于线性规划。文献[1]提出了以下算法：

其中，目标函数式（9）确保总吞吐量最大，约束式（10）、（11）、（12）与Tang的算法相同。注意约束的差异式（13），在Tang的算法中（我们称之为下一个原算法），它并不关心每个用户的最小吞吐量，这可能导致一些用户的吞吐量非常低，甚至等于零，但其他用户的吞吐量相当高。显然，这种情况对于吞吐量较低的一些用户来说是不公平的。因此，为了提高公平性，我们需要确保所有用户的吞吐量大于或等于最小需求dmi。

dmi是一个动态值。它可以根据每个用户的最大流量需求而变化。dmi=di×Co，其中Co是di的系数，Co∈[0，0.3]。当Co=0时，我们可以得到dmi=0，在这种情况下我们的算法与文献[1]相同;当Co>0.3时，dmi的值更接近于di。通过仿真我们可以得出结论：与原始算法相比总吞吐量会显着降低，尽管它具有更高的公平性，却由于极低的吞吐量而没有意义。因此，我们最终设定了Co∈[0，0.3]。

优化贪心算法可以消除不活动的用户。但是，如果未应用优化的贪婪算法，则可能存在一个或多个非活动用户且其吞吐量为零，并且我们无法限制这些用户的最低需求。换句话说，非活动用户的吞吐量必须为零，这意味着它的最小需求也必须为零。因此，为了保证非活动用户的最小需求等于零，我们的算法将在计算dmi的值之前检查每个用户并判断它是活动的还是非活动的。如果我们找到一个不活跃的用户，无论Co和di的值是什么，其最小需求都会被直接设置为0。

例如：我们假设用户数是3，di服从12到24之间的正态分布。另外，我们把Co设为0.3。如果每个用户的最大需求是：d1=16，d2=18，d3=20。我们可以获得每个用户的最低要求：dm1=4.8（活动用户），dm2=5.4（活动用户），dm3=0（非活动用户）。我们可以看到，第一个和第二个用户是活动的，因此它的最小需求分别等于其最大需求时间系数。但第三个用户处于非活动状态，因此其最低需求等于零。

6  模拟

6.1  方法描述

我们使用MATLAB仿真并评估了以上算法的性能。我们在不同的实验参数下观察了三个指标的差异，即总吞吐量、Jain指数和熵值。实验参数包含基本算法、优化贪心算法和DMD算法之间的用户数和通道数。实际上，我们提出的两种算法（优化贪婪算法和DMD算法）都可以提高无线通信系统中用户的公平性。但是功能各有侧重，优化的贪心算法可以消除非活动用户，DMD算法可以确保每个用户的吞吐量最小化。为了反映各算法对公平性的影响，我们不仅将这两种算法结合起来，还分别比较了各自与其基本算法的性能。

为了考察一个参数如何影响不同算法的总吞吐量和公平性，我们使用控制变量法，改变一个参数，固定其他参数。此外，每一次运行仿真程序，MCCG图是随机创建的，di不是固定的，但是服从正态分布。每一种设定下，我们执行10次仿真程序，取吞吐量和公平度的平均数，这样可以确保最终结果具有代表性。

例如：模拟用户数量不断增加时吞吐量和公平性的变化。首先，我们需要固定其他参数，如Co=0.2，信道数=3，等等。然后，设置用户数的范围。最后，在MATLAB中以不同的算法执行程序并收集数据。

6.2  结果

6.2.1  不同用户数下的性能

我们将用户数的范围设置为3到100，并且Co=0.15，通道数=3，di服从12到24之间的正态分布。我们之前已经提到，Jain指数的值接近1，公平性更好，更高的熵值同样代表更好的公平性。当用户数量不大時，DMD算法的吞吐量和公平性与基本算法接近，随着用户数量的增加，DMD算法的吞吐量低于基本算法，但它具有更好的公平性。因此，我们得出结论，DMD算法可以提高公平性，特别是与优化贪心算法相结合时。在相同数量的用户条件下，虽然优化贪婪算法的吞吐量低于基本算法，但是Jain指数和熵的值更高，这意味着它具有更好的公平性。我们得出结论，优化的贪心算法可以显著提高公平性。

6.2.2  信道数对性能的影响

通道数的范围设置为2到20，并且Co=0.15，用户数=40，di服从12到24之间的正态分布。我们还可以得出结论，优化的贪心算法和DMD算法都可以提高公平性。然而，与先前模拟的结果不同，即随着用户数量的增加，公平度会增加。在这一实验中，信道的数量不会影响公平性和吞吐量。这两个指标只会受到算法的影响。此外，我们可以看到优化的贪心算法中的公平性比基本算法更稳定，因为基本算法的公平性不稳定由非活动用户导致，而优化的贪心算法消除了不活跃用户。

6.2.3  Co对性能的影响

我们将Co的值的范围从0设置为0.3（间隔为0.02）。用户数=40，信道数=3，di服从12到24之间的正态分布。总吞吐量和公平性随着Co的增加而增加。Co的值与公平性之间的关系不够明确。因此，我们观察总吞吐量和公平性与Co值的关系时，发现当Co=0时，两个算法的性能彼此相同;随着Co值的增加，吞吐量的差异越来越大，DMD算法的公平性越来越好;当Co=0.3时，吞吐量的差异非常大，DMD算法的Jain指数甚至非常接近1。因此，我们可以得出结论，Co的值对吞吐量和公平性具有显著影响。

7  结  论

（1）优化的贪心算法可以消除不活跃的用户，从而提高吞吐量和公平性。

（2）DMD算法也可以显著提高公平性。如果与优化的贪心算法结合使用，这一优势会更加明显。

（3）随着用户数量的增加，公平性也在增加。

（4）信道数与公平无关。

（5）随着Co的增加，公平性也在增加。

总吞吐量与公平性之间存在冲突。根据不同无线通信系统的要求，我们可以设置不同的参数，如Co的值，以达到吞吐量和公平性之间的平衡。

参考文献：

[1] TANG J，Misra，Satyajayant，et al. Joint spectrum allocation and scheduling for fair spectrum sharing in cognitive radio wireless networks [J]. Computer Networks，2008，52（11）：2148-2158.

[2] D. Gözüpek，F.Alagöz. A fair scheduling model for centralized cognitive radio networks [J/OL]. http：//arxiv.org/pdf/1309.2233v1.pdf，2018.

[3] Liu Y，Lu J，Yang H，et al. Towards maximum independent sets on massive graphs [J]. Proceedings of the VLDB Endowment，2015，8（13）：2122-2133.

[4] HALLD＼’ORSSON MM，RADHAKRISHNAN J. Greed is good：Approximating independent sets in sparse and bounded-degree graphs [J]. Algorithmica，1997，18（1）：145-163.

[5] Huaizhou Shi. Fairness in Wireless Networks：Issues，Measures and Challenges [J]. Communications Surveys & Tutorials，IEEE，2014，16（1）：5-24.

[6] R. Jain，D.-M. Chiu and W. Hawe. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems [J].Maynard：Eastern Research Laboratory，Digital Equipment Corporation，1998.

[7] Lan T，Kao D，Chiang M，et al. An Axiomatic Theory of Fairness in Network Resource Allocation [J]. Proceedings-IEEE INFOCOM，2009，1（9）：1-9.

作者简介：吕臻（1987-），男，汉族，河南漯河人，硕士，研究方向：计算机网络信息安全。