認知無線電網絡資源分配的公平方法

呂臻 代磊

摘? 要：隨著無線通信需求的增加，有限的頻譜成為一項關鍵挑戰。傳統上，某些頻段是為特定目的而分配的，并且只能由被許可的用戶訪問，該策略導致頻譜利用率低下。雖然認知無線電網絡可以緩解頻譜稀缺問題，但節點仍然需要爭奪資源，因此頻譜的公平分配是一個重要的考慮因素。我們希望找到一種認知無線電網絡資源分配的公平方法，并達到吞吐量和公平性的均衡性能。

關鍵詞：認知無線電網絡;資源分配;公平方法

中圖分類號：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的每次迭代都可以找到一個最大獨立集，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之間的正態分布?？偼掏铝亢凸叫噪S著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-），男，漢族，河南漯河人，碩士，研究方向：計算機網絡信息安全。