基于匹配理論的NOMA 異構網絡資源分配算法

龍 懇，李 偉，魯江麗，蔣明均，隆 泉

（1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.中國移動通信集團設計院有限公司浙江分公司，杭州 310012）

0 概述

隨著各種無線終端產品的大規模接入，以正交頻分多址接入（Orthogonal Frequency Division Multiple Access，OFDMA）為代表的4G 無線通信技術將無法應對5G 無線通信系統中面臨的海量連接和高吞吐量兩個主要挑戰［1-2］，因為在OFDMA 系統中，子載波間是正交的且頻譜資源沒有得到充分利用。作為5G 多址接入技術備選方案之一的非正交多址接入（Non-Orthogonal Multiple Access，NOMA），由于其在同一頻率資源塊上具有復用多個不同功率電平用戶的能力，因此可以使整個通信系統的頻譜效率和吞吐量得到進一步提升［3-4］。

當網絡中存在多個具有不同信道狀態的無線終端時，如何對復用在特定時間和頻率資源上的用戶進行資源分配，從而使整個系統的總吞吐量達到最大化，仍然是一個開放性的問題。在整個資源分配過程中，用戶和子信道的合理分組可以在提升系統吞吐量的同時有效協調用戶間的公平性。文獻［5］將用戶-子信道匹配問題建模為非合作博弈過程，通過用戶和子信道之間的雙向選擇，提出基于超模博弈的用戶分組算法（Super-Modular Game Algorithm，S-MGA），使系統性能和用戶間的公平性得到了有效提升。文獻［6］根據不同的信道條件對用戶進行配對，提出一種基于信道增益的用戶分組算法，證明了NOMA 系統在吞吐量方面比OMA 系統能夠得到更大的性能提升。文獻［7］利用已知的信道狀態信息對用戶的信道增益進行排序，提出一種基于二進制交錯原理的用戶分組算法，在改善用戶間公平性的同時提高了系統吞吐量。文獻［8］根據同一子信道上疊加用戶的限制條件和信道增益的差異，提出一種以最大化幾何平均用戶吞吐量的多用戶分組算法，使系統吞吐量和幾何平均用戶吞吐量得到了有效提升。文獻［9］根據用戶等效信道增益的調度優先級，提出一種基于自適應比例公平（Adaptive Proportional Fair，APF）的用戶分組算法。該算法不僅可以達到理想的匹配效果，而且能夠提高用戶之間的公平性。文獻［10］研究NOMA 異構網絡下的資源分配問題，考慮到小區內和小區間的干擾，通過固定發射功率，提出一種基于拉格朗日對偶分析的分布式算法來解決用戶分組問題。該算法性能優于傳統的遺傳算法（Genetic Algorithm，GA）。除上述文獻外，關于用戶分組的理論研究在文獻［11-13］中也有所涉及。目前關于NOMA 用戶分組方面的研究主要集中在單小區，而關于NOMA 異構網絡用戶分組的研究較少。此外，現有研究較少對每個子信道的疊加用戶數、系統吞吐量、用戶最小傳輸速率和算法復雜度進行綜合考慮。

本文將子信道分配和功率分配建模為非凸優化問題，以使系統吞吐量達到最大，對兩者進行解耦，并表明子信道分配是一個多元匹配過程，其中用戶和子信道是兩組需要匹配的元素。利用匹配理論［14］構建一個自適應且低復雜度的框架，解決具有組合性質的資源分配問題［15-16］。在此基礎上，將子信道分配問題表述為具有外部性的多對多雙邊匹配問題，同時考慮小區內和小區間的同信道干擾以及匹配玩家之間偏好的相互依賴性，提出用戶-子信道雙邊匹配算法（User-Subchannel Two-Sided Matching Algorithm，USTSMA），通過少量迭代形成穩定匹配。

1 網絡模型與優化問題描述

1.1 網絡模型

本文考慮下行鏈路兩層NOMA 異構網絡，如圖1 所示。整個異構網絡由一個宏基站（MBS）和若干個微基站（PBS）構成。其中，MBS 和PBS 分別位于宏小區和微小區的中心，對于異構網絡中基站（BS）的索引可以用參數t表示（t∈{1，2，…，T}）。t=1時表示MBS，其余情況則表示PBS。假設BS 與終端用戶的天線數為1 且每個用戶在同一時間和頻段內只接入到一個BS，每個BS 將信號發送到由={1，2，…，N}表示的一組移動用戶，每組內對于用戶的索引用j表示。整個系統將可用帶寬劃分為一組由={1，2，…，K}表示的子信道集合，對于異構網絡中基站t上第k個子信道的索引，用表示。

圖1 異構網絡模型Fig.1 Model of HetNets

本文假設BS 對于信道狀態信息（Channel State Information，CSI）是已知的，基于每個子信道的CSI，BS 將非正交子信道的子集分配給用戶并為他們分配不同的功率。根據NOMA 協議［17］，一個子信道可以分配給多個用戶且一個用戶可以通過多個子信道從BS 接收。在基站t的子信道k上分配給用戶的功率由表示，滿足P(t)/K，其中，P(t)是基站t的總發射功率。本文考慮的是塊衰落信道，信道在一個時隙內保持不變，但是每個子信道之間是獨立變化的。用戶Nj在基站t上子信道的信道系數表示為其中，表示瑞利信道增益與D(·)分別表示用戶Nj與基站t的距離和路徑損耗函數表示子信道上的用戶集合表示基站t在子信道上向用戶Nj發送的信號。因此，用戶Nj通過接收的信號為：

為解調目標信號，每個用戶Nj采用串行干擾消除（Successive Interference Cancellation，SIC）技術［18］。用戶Nj的接收端可以消除來自子信道上其他用戶Ni的干擾，滿足用戶Nj將信道增益大于其自身信道增益的用戶信號視為噪聲，然后從接收信號中解碼因此，用戶Nj的速率可以表示為：

由于用戶在接收端執行SIC 技術的過程較為復雜，并且隨著同一子信道上用戶數量的增加，SIC 實現的復雜度也會增加，因此考慮到解碼的復雜性，本文假設最多有μ個用戶可以共享同一個子信道，即當給定適當的μ值時，可以將接收端的解碼復雜度降低到適當的水平。此外，由于頻譜資源的稀缺，本文還假設每個子信道至少分配l個用戶以保證調度用戶的數量。

1.2 問題描述

為更好地描述用戶集與子信道集的匹配過程，本文引入二進制元素γk，j表示子信道是否被分配給用戶Nj。整個系統的性能可以由所有用戶的總和速率來評估，因此優化目標是通過設置變量和改變調度用戶的數量來最大化系統的總和數據速率，則優化問題表述為：

在上式中：約束條件C1 和C2 確保每個子信道只能分配給最多μ個用戶和最少l個用戶；由于BS的發射功率有限，功率變量必須滿足約束條件C3 和C4；約束條件C5 則保證用戶的最低數據速率。

由于C1 中二進制變量的約束以及目標函數中存在干擾項，優化問題為非凸優化問題且在異構網絡中通過傳統的集中式方法來解決復雜度過高，因此本文將該問題分解為子信道分配和功率分配問題。為便于將子信道分配給用戶以建立彼此之間的匹配關系，利用匹配理論將用戶集和子信道集視為兩個不相交且自私的理性玩家集合，并期望用戶與子信道之間彼此匹配以使其自身的利益（相應的總和數據率）達到最大化。

2 優化問題求解

考慮到優化目標的計算復雜度，本文首先將功率分配和子信道分配分離，然后得到次優解。假設BS 的發射功率被平均分配給共享相同子信道的用戶，則可以利用匹配理論將該優化問題表示為多對多雙邊匹配問題。在此基礎上，利用注水算法［19］將BS 的發射功率分配給每個子信道上的調度用戶。

2.1 基礎知識

其中，L(Nj)和分別是用戶Nj和子信道的偏好列表。每個子信道至少被分配給l個用戶且其對該組用戶不同子集的偏好可以表示為：

式（9）表示相對于用戶子集ψ'，子信道更偏好于子集ψ中的用戶，因為子集ψ可以提供比子集ψ'更高的速率。此外，每個用戶可以占用一個或多個子信道，這些子信道的優先關系可以表示為：

匹配算法和穩定性取決于偏好列表的不同特征及其相應的屬性。在本文場景中，用戶和子信道的偏好具有傳遞性和可替換性。傳遞性是指：如果可替代性是指：假設給定一個用戶，其偏好子信道集合屬于用戶Nj與成員k和k'的相反集合，如果那么因此，用戶和子信道集合的偏好具有可替代性。

根據上述偏好列表的概念，可以將用戶-子信道的優化問題表示為多對多雙邊匹配問題。

通過上述分析可以發現，本文定義的匹配問題相對于傳統的雙邊匹配問題更復雜，這主要是因為用戶集與子信道集的子集可以在彼此之間進行任意匹配且每個子集中包含的元素可能較多，所以會導致匹配組合的數量較大。此外，疊加在相同子信道上的用戶彼此之間存在依賴關系以及同一子信道上用戶之間的功率分配，也會增加匹配問題的復雜度。為解決用戶-子信道雙邊匹配和功率分配問題，下文將提出相應的匹配算法和功率分配算法。

2.2 算法設計

2.2.1 用戶-子信道雙邊匹配算法

本文通過改進傳統雙邊匹配算法，提出一種低復雜度匹配算法USTSMA，主要設計思想為：如果用戶想要與某個子信道進行匹配，則其向該子信道提出接入請求且每個子信道有權接受或拒絕這些請求，當所有用戶都提出一次接入請求后，即一輪接入請求執行完畢。

在描述USTSMA 算法之前，本文通過引入封閉對的概念以解釋子信道如何選擇不同用戶的接入請求。

通過定義2 可以描述每個子信道在面對不同用戶的接入請求時做決策的行為。由于子信道的決策過程是消除潛在封閉對的過程，并且每個子信道選擇用戶的目的是最大化自身的傳輸速率，因此當子信道每次與Nj形成封閉對時，其將保持Nj的接入請求并拒絕其他用戶。

本文針對式（6）優化問題提出的USTSMA 算法主要包括兩個階段，即初始化階段和匹配階段。在初始化過程中，每個子信道和用戶根據已知的信道狀態信息設置偏好列表。在匹配過程中，每個用戶向自己偏好列表中沒有拒絕過他的最優子信道發出接入請求，并且該子信道可以提供比Rmin更高的數據速率。如果該子信道的當前容量小于l，則子信道保留這些接入請求；如果該子信道的當前容量大于l，則子信道只選擇少于（μ+1）個用戶提出的接入請求且拒絕其他用戶的接入請求；如果沒有用戶提出新的接入請求時，則匹配終止。USTSMA 具體描述如下：

6）如果沒有用戶對子信道提出新的接入請求，則算法終止；如果有新的接入請求，則跳轉第2）步。

2.2.2 注水功率分配算法

如果給定子信道分配，則可以利用注水功率分配算法實現用戶間的功率分配。為降低由SIC 技術引起的功率分配的復雜度，本文設置適當的注水解決方案公式表示如下：

2.3 穩定性、收斂性與復雜度分析

本節主要對USTSMA 的穩定性、收斂性和復雜度進行分析，并通過定義穩定性的概念證明該算法可以實現收斂的穩定匹配。

定義3如果匹配M中不存在不封閉的匹配對，則匹配M定義為成對穩定匹配。

引理1如果USTSMA 收斂于一個匹配M，則M為成對穩定匹配。

定理1USTSMA 可以經過有限次數的迭代收斂實現成對穩定的匹配。

證明因為在每輪匹配過程中，每個用戶向其偏好列表中的最優子信道提出接入請求且該子信道在之前配對過程中并未拒絕，所以隨著迭代次數的增加，每個用戶Nj的選擇集將會變小。由于網絡中有K個子信道，因此每個用戶Nj向子信道提出的請求次數和迭代總數均不超過K。綜上，USTSMA 收斂到最終匹配M，該匹配也為成對穩定的匹配。

定理2最優窮舉搜索復雜度為O(TK2N)，USTSMA復雜度為O(TNK2)。

證明為進行最優窮舉搜索，BS 在每個子信道上搜索所有可能的候選用戶集，選擇最偏好的用戶集并在每個子信道執行功率分配。由于候選用戶集的數量為2N-1 并且整個異構網絡中有T個BS 和K個子信道，因此最優窮舉搜索的復雜度為O(TK2N)。對于USTSMA，其復雜度主要取決于排序過程和匹配過程。在排序過程中，每個用戶都獲得其K個子信道的偏好列表，則復雜度為O(NK)，而在匹配過程中，每個用戶將提議最多K次，因此，最終算法復雜度為O(TNK2)。

3 仿真分析

本節通過仿真評估USTSMA 的性能并將其與文獻［5，10］方案、OFDMA 方案和最優上界進行對比。在文獻［5，10］方案中，主要選取S-MGA 和GA兩種用戶分組算法且每個子信道的疊加用戶數設為2。在OFDMA 方案中，為滿足正交頻分復用準則并使系統吞吐量達到最大，本文將每個子信道只分配給一個用戶且用戶分得該子信道的總功率。對于最優上界，本文將μ設為N以保證子信道可以被所有用戶共享。在此基礎上，利用最優窮舉搜索算法將所有用戶的子集與子信道進行匹配，并結合注水功率分配算法對其進行功率分配，以達到系統總吞吐量的最大化。具體的仿真參數設置如表1 所示。

表1 系統仿真參數Table 1 System simulation parameters

圖2 展示了子信道數一定時（K=10）系統總和數據速率與總用戶數之間的變化關系。整個異構網絡包括1 個MBS 和1 個PBS。通過仿真分析可以發現，隨著用戶數N的增加，系統總和數據速率也隨之增加且變化趨勢先快后慢，然后逐漸趨于平穩，這是因為當系統的子信道數一定時（K=10），BS 傾向于將子信道分配給信道增益更高的用戶。為具體分析每個子信道上最大疊加用戶數μ與系統總和數據速率的變化關系，本文分別選取μ的值為2、3、4。從圖2中可以看出，當μ=4 時，USTSMA 的性能優于μ取2 和3 的情況。隨著系統用戶數的增加，USTSMA 的性能逐漸優于GA和S-MGA。這是因為GA和S-MGA的系統總和數據速率隨著用戶數的增加而降低。一方面，GA 的效率取決于種群大小［18］；另一方面，雖然S-MGA 可以很好地解決單小區內用戶分組問題，但NOMA 異構網絡存在小區間干擾，這導致其性能隨著小區數和用戶數的增加而降低。此外還可以看出，USTSMA 性能明顯優于OFDMA 方案且逼近最優上界。

圖2 系統總和數據速率與總用戶數的關系Fig.2 Relationship between sum rate of system and total number of users

圖3 展示了子信道數一定時（K=10）系統調度用戶數與總用戶數在一個時隙內的變化關系。可以看出：當用戶數N小于子信道數K時，無論是NOMA 方案還是OFDMA 方案，系統內的子信道資源可以被所有用戶使用；當用戶數N大于子信道數K時，由于OFDMA 方案中用戶之間的正交性（每個子信道只能分配給一個用戶），導致整個系統的用戶調度數將逐漸穩定在某一個固定值，即用戶調度數逐漸逼近子信道數；對于NOMA 方案，用戶調度數將隨著系統內總用戶數量的增加而增加，并逐漸穩定到某個定值且該值小于Kμ。此外還可以看出，隨著同一子信道上疊加用戶數μ的增加，系統的用戶調度數也隨之增加，這是因為μ增大將導致同一子信道上允許接入更多用戶。

圖3 調度用戶數與總用戶數的關系Fig.3 Relationship between number of scheduling users and total number of users

圖4 展示了子信道數一定時（K=10）系統中調度用戶的平均數據速率與總用戶數的變化關系。可以看出，調度用戶平均數據速率的變化趨勢為先降低后升高，然后逐漸趨于平穩，但NOMA 方案的總體性能優于OFDMA 方案，主要原因為：當用戶數較小時，由于子信道數一定，因此調度用戶的平均數據速率將隨用戶數的增加而降低；當用戶數較大時，根據圖3 用戶調度數與總用戶數的變化關系可知，隨著用戶數量的增加，系統的用戶調度數將逐漸達到一個穩定值，但多用戶的分集增益將導致系統總和數據速率不斷增加，因此，每個調度用戶的平均數據率也隨之增加。此外，在NOMA 方案中，調度用戶的平均數據速率與每個子信道上最大疊加用戶數μ呈反比關系，即μ越大調度用戶的平均數據速率越小，這是因為具有較低信道增益的用戶可以共享同一個子信道。

圖4 調度用戶的平均數據速率與總用戶數的關系Fig.4 Relationship between average data rate of scheduling users and total number of users

圖5 展示了用戶數一定時（N=20）系統的總和數據速率與子信道數的變化關系。可以看出，本文方案的性能總體優于OFDMA 方案，同時其性能優于GA和S-MGA 并逼近最優上界，這是因為在本文方案中，系統總和數據速率隨著子信道數和同一子信道疊加用戶數的增加而增加，但對于OFDMA 方案，由于每個用戶占用一個子信道，因此當子信道數大于總用戶數時，系統總和數據速率將保持不變。

圖5 系統總和數據速率與子信道數的關系Fig.5 Relationship between sum rate of system and total number of subchannels

4 結束語

針對NOMA 異構網絡的資源分配問題，本文通過聯合子信道分配和功率分配達到用戶調度數與系統吞吐量之間的平衡。將用戶-子信道分配建模為多對多雙邊匹配問題并提出USTSMA 算法，該算法接近性能最優并且復雜度較低，能夠使用戶和子信道之間形成穩定匹配。仿真結果表明，本文方案下的NOMA 異構網絡在系統總吞吐量、用戶調度數等方面均優于OFDMA 方案，USTSMA 性能較S-MGA和GA 兩種用戶分組算法也有顯著提高。本文的前提假設是用戶-基站之間的關聯已知，下一步將通過引入用戶關聯對本文方案進行優化。