認(rèn)知無(wú)線電網(wǎng)絡(luò)資源分配的公平方法

呂臻 代磊

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

關(guān)鍵詞：認(rèn)知無(wú)線電網(wǎng)絡(luò);資源分配;公平方法

中圖分類號(hào)：TN925? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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? 相關(guān)工作

許多研究人員研究了認(rèn)知無(wú)線電網(wǎng)絡(luò)中的公平資源分配。我們的工作基于一種稱為多通道競(jìng)爭(zhēng)圖（MCCG）的新模型[1]。通過(guò)使用多信道競(jìng)爭(zhēng)圖，節(jié)點(diǎn)之間的干擾和競(jìng)爭(zhēng)可以用無(wú)向圖表示。文獻(xiàn)[2]提出了集中式認(rèn)知無(wú)線電網(wǎng)絡(luò)的通用調(diào)度模型，并研究了幾種實(shí)現(xiàn)公平資源分配的機(jī)制，包括最大最小公平、加權(quán)最大最小公平和比例公平。文獻(xiàn)[3]研究了圖論中的最大獨(dú)立集問(wèn)題，并提出了一種貪心算法。文獻(xiàn)[4]評(píng)估了最小度貪婪算法（Minimum-degree Greedy Algorithm）的性能，并提出了一種分布式算法。我們發(fā)現(xiàn)貪心算法在公平資源分配中的缺點(diǎn)，并提出了一種提高公平性的新算法。文獻(xiàn)[5]分析了與無(wú)線網(wǎng)絡(luò)公平性相關(guān)的廣泛?jiǎn)栴}，并總結(jié)了各種現(xiàn)有的模型和方法。文獻(xiàn)[6]提出了一個(gè)廣泛使用的指標(biāo)，稱為Jain指數(shù)。文獻(xiàn)[7]提出了衡量公平度的五個(gè)公理，并基于這些公理評(píng)估了各種廣泛使用的公平度量的表現(xiàn)。

2? 問(wèn)題定義

2.1? 什么是公平

公平是一個(gè)抽象的概念，具有廣泛的含義。從網(wǎng)絡(luò)的角度來(lái)看，公平意味著無(wú)線電頻譜是平等分配的;時(shí)隙是公平分配的;所有節(jié)點(diǎn)都有機(jī)會(huì)訪問(wèn)網(wǎng)絡(luò)資源。同時(shí)，公平也是一個(gè)模糊的術(shù)語(yǔ)，缺乏明確的評(píng)估標(biāo)準(zhǔn)。考慮三種情況：在第一種情況下，有五個(gè)節(jié)點(diǎn)，A，B，C，D和E爭(zhēng)用100 Mbps帶寬，每個(gè)節(jié)點(diǎn)分配20Mbps帶寬。我們可以說(shuō)這種分配是公平的。在第二種情況下，一個(gè)節(jié)點(diǎn)分配30Mbps帶寬，三個(gè)節(jié)點(diǎn)分配20Mbps帶寬，一個(gè)節(jié)點(diǎn)分配10Mbps帶寬。在第三種情況下，三個(gè)節(jié)點(diǎn)各分配25Mbps帶寬，一個(gè)節(jié)點(diǎn)分配20Mbps帶寬，一個(gè)節(jié)點(diǎn)分配5Mbps帶寬。顯然，這兩種情況不公平，但如何比較這兩種情況？哪一個(gè)相對(duì)更為公平？為了比較和評(píng)估網(wǎng)絡(luò)的性能，我們需要一個(gè)度量來(lái)量化公平性。

2.2? 指標(biāo)的要求

文獻(xiàn)[7]提出了一個(gè)好的指標(biāo)應(yīng)該滿足的要求：

（1）度量標(biāo)準(zhǔn)應(yīng)該滿足連續(xù)性，換句話說(shuō)，分配方案的輕微變化導(dǎo)致公平指數(shù)輕微變化。

（2）度量標(biāo)準(zhǔn)應(yīng)與測(cè)量值和量級(jí)無(wú)關(guān)，這意味著測(cè)量單位的選擇不會(huì)對(duì)公平指數(shù)產(chǎn)生影響。

（3）度量標(biāo)準(zhǔn)應(yīng)與規(guī)模無(wú)關(guān)。該指數(shù)可用于任意數(shù)量的節(jié)點(diǎn)，并且不受節(jié)點(diǎn)數(shù)量的干擾。

2.3? 測(cè)量選擇

基于上述三個(gè)要求，我們使用Jain指數(shù)來(lái)衡量公平性。Jain指數(shù)由文獻(xiàn)[6]提出，這是一個(gè)評(píng)估公平性的知名指數(shù)。Jain指數(shù)被定義為：

我們采用的另一個(gè)指標(biāo)是同樣被廣泛應(yīng)用的熵（entro-py）。熵首先由Shannon提出。它定義為：

3? 假設(shè)

我們考慮這樣一個(gè)場(chǎng)景，其中給定數(shù)量的節(jié)點(diǎn)隨機(jī)分布在一個(gè)區(qū)域中。在認(rèn)知無(wú)線電網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)可以訪問(wèn)多個(gè)信道。但是，一個(gè)節(jié)點(diǎn)一次只能訪問(wèn)一個(gè)通道。另外，節(jié)點(diǎn)不能同時(shí)發(fā)送和接收信號(hào)。一個(gè)節(jié)點(diǎn)僅向一個(gè)特定用戶傳輸信息。如果兩個(gè)節(jié)點(diǎn)將信號(hào)發(fā)送到同一節(jié)點(diǎn)，則會(huì)發(fā)生干擾。

我們假設(shè)所有節(jié)點(diǎn)的傳輸功率都是固定的，因此所有節(jié)點(diǎn)都覆蓋相同的范圍。我們進(jìn)一步假設(shè)所有通道具有相同的增益，并且所有接收器具有相同的性能，因此每個(gè)節(jié)點(diǎn)的干擾范圍是相同的。在我們的測(cè)試中，我們假設(shè)干擾范圍是傳輸范圍的兩倍。如果兩個(gè)節(jié)點(diǎn)彼此靠近，雖然它們?cè)趦蓚€(gè)不同的信道上發(fā)送信號(hào)，但它們?nèi)匀粫?huì)相互干擾，這是不允許的。

我們還假設(shè)存在中央服務(wù)器，其負(fù)責(zé)感測(cè)頻譜利用和分配信道資源。每個(gè)節(jié)點(diǎn)都可以向中央服務(wù)器發(fā)送請(qǐng)求，告知服務(wù)器他們的流量需求和最低需求。服務(wù)器根據(jù)干擾、信道利用率、節(jié)點(diǎn)需求做出決策。一旦服務(wù)器獲得方案，它將向所有節(jié)點(diǎn)廣播控制消息，并且節(jié)點(diǎn)將立即對(duì)控制消息做出反應(yīng)且沒(méi)有延遲。

4? 互不干擾用戶對(duì)搜索算法

最重要的問(wèn)題之一是找到不互相干擾的用戶對(duì)，以便它們可以同時(shí)傳輸數(shù)據(jù)。我們采用文獻(xiàn)[1]提出的多通道競(jìng)爭(zhēng)圖來(lái)解決這個(gè)問(wèn)題。

基于多通道競(jìng)爭(zhēng)圖，干擾可以表示為無(wú)向圖。如果用戶對(duì)彼此干涉，則相應(yīng)的頂點(diǎn)通過(guò)邊連接。換句話說(shuō)，如果沒(méi)有連接兩個(gè)頂點(diǎn)，則相應(yīng)的用戶對(duì)可以同時(shí)通信。因此，識(shí)別不出相互干擾的用戶對(duì)可以等價(jià)轉(zhuǎn)換為在競(jìng)爭(zhēng)圖中搜索獨(dú)立集。

4.1? 獨(dú)立集的選擇

另一個(gè)問(wèn)題是如何找到獨(dú)立的集合。圖中存在大量獨(dú)立集（Independent Set）。隨著頂點(diǎn)數(shù)的增加，獨(dú)立集的數(shù)量呈指數(shù)增長(zhǎng)。找到所有獨(dú)立集是不必要的，我們只需要找到能夠提高吞吐量和公平性的獨(dú)立集。我們假設(shè)，如果可以同時(shí)激活更多用戶對(duì)，吞吐量將更高，分配將更公平。為了實(shí)現(xiàn)這一目標(biāo)，我們需要一種能夠找到包含盡可能多的用戶的獨(dú)立集的算法。文獻(xiàn)[1]提出了一種啟發(fā)式算法來(lái)尋找最大獨(dú)立集。最大獨(dú)立集是滿足這樣性質(zhì)的一個(gè)集合——加入圖中任何額外的定點(diǎn)得到的新集合都不再是獨(dú)立集。

4.2? 基本貪心算法

4.2.1? 算法描述

我們的第一個(gè)貢獻(xiàn)是使用極大獨(dú)立集（Maximal Independent Set）而非最大獨(dú)立集（Maximum Independent Set）來(lái)識(shí)別不相互干擾的用戶。最大獨(dú)立集是一個(gè)獨(dú)立集，具有最大可能的大小。最大獨(dú)立集同時(shí)也是一個(gè)極大獨(dú)立集，但極大獨(dú)立集未必為最大獨(dú)立集。找到最大獨(dú)立集NP完全問(wèn)題。沒(méi)有算法可以在多項(xiàng)式時(shí)間內(nèi)獲得精確解。因此，找到嚴(yán)格的解決方案并不適用于實(shí)踐，相反，我們使用貪婪算法來(lái)獲得近似解。

設(shè)M表示給定圖G的鄰接矩陣，MIS表示最大獨(dú)立集?；矩澬乃惴ū硎救绫?所示。

算法1的每次迭代都可以找到一個(gè)最大獨(dú)立集，j指示算法迭代的次數(shù)。算法迭代的次數(shù)越多，找到的最大獨(dú)立集就越多。

4.2.2? 算法1的缺點(diǎn)

我們的第二個(gè)貢獻(xiàn)是發(fā)現(xiàn)基本貪心算法的缺點(diǎn)，這可能會(huì)對(duì)公平性產(chǎn)生負(fù)面影響。我們分析了算法1的結(jié)果。有時(shí)在獲得幾個(gè)最大獨(dú)立集之后，我們發(fā)現(xiàn)一些用戶不包括在任何一個(gè)最大獨(dú)立集中。就是說(shuō)，這些用戶始終處于非活動(dòng)狀態(tài)，因此沒(méi)有任何傳輸數(shù)據(jù)的機(jī)會(huì)。

算法1可以找到三個(gè)不同的最大獨(dú)立集，即A=（1，2，3），B=（1，3，4）和C=（1，2，4）。用戶對(duì)5不包括在三組中的任何一組中。因此，中央服務(wù)器不會(huì)將信道資源分配給用戶對(duì)5，它將無(wú)法傳輸任何數(shù)據(jù)。顯然這是不公平的分配方案。

我們進(jìn)一步檢查這些非活動(dòng)點(diǎn)，發(fā)現(xiàn)這些點(diǎn)具有相對(duì)較大的度或者它們與具有最小度的點(diǎn)相鄰。因此，它們?cè)谒惴?的第一步就會(huì)被被移除。例如：在上面的情況中，對(duì)應(yīng)于用戶對(duì)5的頂點(diǎn)的度為7并且它與對(duì)應(yīng)于用戶對(duì)1的頂點(diǎn)相鄰，且代表用戶對(duì)1的點(diǎn)度為3，是所有點(diǎn)中最小的，用戶對(duì)5將首先被移除。

我們得出結(jié)論，找到包含這些非活動(dòng)點(diǎn)的最大獨(dú)立集是不可能的。為了覆蓋每個(gè)用戶，我們提出算法2。

4.3? 優(yōu)化的貪婪算法

我們的第三個(gè)貢獻(xiàn)是提出一種可以覆蓋所有頂點(diǎn)的新算法。雖然找到包含那些非活動(dòng)點(diǎn)的最大獨(dú)立集是不可能的，但我們可以找到極大獨(dú)立集。

算法2可以找到包含任何給定頂點(diǎn)的極大獨(dú)立集。MIS1表示最大獨(dú)立集，MIS2表示極大獨(dú)立集，T是存儲(chǔ)每次迭代結(jié)果的矩陣，優(yōu)化的貪婪算法如表2所示。

算法2返回包含多個(gè)獨(dú)立集的集合并將結(jié)果存儲(chǔ)在矩陣中。矩陣的每一行代表一個(gè)獨(dú)立的集合。每個(gè)用戶對(duì)至少被算法2覆蓋一次。

5? 用戶動(dòng)態(tài)最低需求

另一個(gè)貢獻(xiàn)是提出每個(gè)用戶的動(dòng)態(tài)最低需求（Dynamic Minimum Demand Of Each User）以提高公平性。DMD算法基于線性規(guī)劃。文獻(xiàn)[1]提出了以下算法：

其中，目標(biāo)函數(shù)式（9）確?？偼掏铝孔畲?，約束式（10）、（11）、（12）與Tang的算法相同。注意約束的差異式（13），在Tang的算法中（我們稱之為下一個(gè)原算法），它并不關(guān)心每個(gè)用戶的最小吞吐量，這可能導(dǎo)致一些用戶的吞吐量非常低，甚至等于零，但其他用戶的吞吐量相當(dāng)高。顯然，這種情況對(duì)于吞吐量較低的一些用戶來(lái)說(shuō)是不公平的。因此，為了提高公平性，我們需要確保所有用戶的吞吐量大于或等于最小需求dmi。

dmi是一個(gè)動(dòng)態(tài)值。它可以根據(jù)每個(gè)用戶的最大流量需求而變化。dmi=di×Co，其中Co是di的系數(shù)，Co∈[0，0.3]。當(dāng)Co=0時(shí)，我們可以得到dmi=0，在這種情況下我們的算法與文獻(xiàn)[1]相同;當(dāng)Co>0.3時(shí)，dmi的值更接近于di。通過(guò)仿真我們可以得出結(jié)論：與原始算法相比總吞吐量會(huì)顯著降低，盡管它具有更高的公平性，卻由于極低的吞吐量而沒(méi)有意義。因此，我們最終設(shè)定了Co∈[0，0.3]。

優(yōu)化貪心算法可以消除不活動(dòng)的用戶。但是，如果未應(yīng)用優(yōu)化的貪婪算法，則可能存在一個(gè)或多個(gè)非活動(dòng)用戶且其吞吐量為零，并且我們無(wú)法限制這些用戶的最低需求。換句話說(shuō)，非活動(dòng)用戶的吞吐量必須為零，這意味著它的最小需求也必須為零。因此，為了保證非活動(dòng)用戶的最小需求等于零，我們的算法將在計(jì)算dmi的值之前檢查每個(gè)用戶并判斷它是活動(dòng)的還是非活動(dòng)的。如果我們找到一個(gè)不活躍的用戶，無(wú)論Co和di的值是什么，其最小需求都會(huì)被直接設(shè)置為0。

例如：我們假設(shè)用戶數(shù)是3，di服從12到24之間的正態(tài)分布。另外，我們把Co設(shè)為0.3。如果每個(gè)用戶的最大需求是：d1=16，d2=18，d3=20。我們可以獲得每個(gè)用戶的最低要求：dm1=4.8（活動(dòng)用戶），dm2=5.4（活動(dòng)用戶），dm3=0（非活動(dòng)用戶）。我們可以看到，第一個(gè)和第二個(gè)用戶是活動(dòng)的，因此它的最小需求分別等于其最大需求時(shí)間系數(shù)。但第三個(gè)用戶處于非活動(dòng)狀態(tài)，因此其最低需求等于零。

6? 模擬

6.1? 方法描述

我們使用MATLAB仿真并評(píng)估了以上算法的性能。我們?cè)诓煌膶?shí)驗(yàn)參數(shù)下觀察了三個(gè)指標(biāo)的差異，即總吞吐量、Jain指數(shù)和熵值。實(shí)驗(yàn)參數(shù)包含基本算法、優(yōu)化貪心算法和DMD算法之間的用戶數(shù)和通道數(shù)。實(shí)際上，我們提出的兩種算法（優(yōu)化貪婪算法和DMD算法）都可以提高無(wú)線通信系統(tǒng)中用戶的公平性。但是功能各有側(cè)重，優(yōu)化的貪心算法可以消除非活動(dòng)用戶，DMD算法可以確保每個(gè)用戶的吞吐量最小化。為了反映各算法對(duì)公平性的影響，我們不僅將這兩種算法結(jié)合起來(lái)，還分別比較了各自與其基本算法的性能。

為了考察一個(gè)參數(shù)如何影響不同算法的總吞吐量和公平性，我們使用控制變量法，改變一個(gè)參數(shù)，固定其他參數(shù)。此外，每一次運(yùn)行仿真程序，MCCG圖是隨機(jī)創(chuàng)建的，di不是固定的，但是服從正態(tài)分布。每一種設(shè)定下，我們執(zhí)行10次仿真程序，取吞吐量和公平度的平均數(shù)，這樣可以確保最終結(jié)果具有代表性。

例如：模擬用戶數(shù)量不斷增加時(shí)吞吐量和公平性的變化。首先，我們需要固定其他參數(shù)，如Co=0.2，信道數(shù)=3，等等。然后，設(shè)置用戶數(shù)的范圍。最后，在MATLAB中以不同的算法執(zhí)行程序并收集數(shù)據(jù)。

6.2? 結(jié)果

6.2.1? 不同用戶數(shù)下的性能

我們將用戶數(shù)的范圍設(shè)置為3到100，并且Co=0.15，通道數(shù)=3，di服從12到24之間的正態(tài)分布。我們之前已經(jīng)提到，Jain指數(shù)的值接近1，公平性更好，更高的熵值同樣代表更好的公平性。當(dāng)用戶數(shù)量不大時(shí)，DMD算法的吞吐量和公平性與基本算法接近，隨著用戶數(shù)量的增加，DMD算法的吞吐量低于基本算法，但它具有更好的公平性。因此，我們得出結(jié)論，DMD算法可以提高公平性，特別是與優(yōu)化貪心算法相結(jié)合時(shí)。在相同數(shù)量的用戶條件下，雖然優(yōu)化貪婪算法的吞吐量低于基本算法，但是Jain指數(shù)和熵的值更高，這意味著它具有更好的公平性。我們得出結(jié)論，優(yōu)化的貪心算法可以顯著提高公平性。

6.2.2? 信道數(shù)對(duì)性能的影響

通道數(shù)的范圍設(shè)置為2到20，并且Co=0.15，用戶數(shù)=40，di服從12到24之間的正態(tài)分布。我們還可以得出結(jié)論，優(yōu)化的貪心算法和DMD算法都可以提高公平性。然而，與先前模擬的結(jié)果不同，即隨著用戶數(shù)量的增加，公平度會(huì)增加。在這一實(shí)驗(yàn)中，信道的數(shù)量不會(huì)影響公平性和吞吐量。這兩個(gè)指標(biāo)只會(huì)受到算法的影響。此外，我們可以看到優(yōu)化的貪心算法中的公平性比基本算法更穩(wěn)定，因?yàn)榛舅惴ǖ墓叫圆环€(wěn)定由非活動(dòng)用戶導(dǎo)致，而優(yōu)化的貪心算法消除了不活躍用戶。

6.2.3? Co對(duì)性能的影響

我們將Co的值的范圍從0設(shè)置為0.3（間隔為0.02）。用戶數(shù)=40，信道數(shù)=3，di服從12到24之間的正態(tài)分布?？偼掏铝亢凸叫噪S著Co的增加而增加。Co的值與公平性之間的關(guān)系不夠明確。因此，我們觀察總吞吐量和公平性與Co值的關(guān)系時(shí)，發(fā)現(xiàn)當(dāng)Co=0時(shí)，兩個(gè)算法的性能彼此相同;隨著Co值的增加，吞吐量的差異越來(lái)越大，DMD算法的公平性越來(lái)越好;當(dāng)Co=0.3時(shí)，吞吐量的差異非常大，DMD算法的Jain指數(shù)甚至非常接近1。因此，我們可以得出結(jié)論，Co的值對(duì)吞吐量和公平性具有顯著影響。

7? 結(jié)  論

（1）優(yōu)化的貪心算法可以消除不活躍的用戶，從而提高吞吐量和公平性。

（2）DMD算法也可以顯著提高公平性。如果與優(yōu)化的貪心算法結(jié)合使用，這一優(yōu)勢(shì)會(huì)更加明顯。

（3）隨著用戶數(shù)量的增加，公平性也在增加。

（4）信道數(shù)與公平無(wú)關(guān)。

（5）隨著Co的增加，公平性也在增加。

總吞吐量與公平性之間存在沖突。根據(jù)不同無(wú)線通信系統(tǒng)的要求，我們可以設(shè)置不同的參數(shù)，如Co的值，以達(dá)到吞吐量和公平性之間的平衡。

參考文獻(xiàn)：

[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(xiàn).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.

作者簡(jiǎn)介：呂臻（1987-），男，漢族，河南漯河人，碩士，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)信息安全。