面向蜂窩—D2D混合場景的雙層博弈匹配算法

姚天，張暉

?

面向蜂窩—D2D混合場景的雙層博弈匹配算法

姚天，張暉

（南京郵電大學，江蘇 南京 210003）

隨著無線技術(shù)的迅猛發(fā)展，無線接入網(wǎng)絡(luò)進入新的階段，即第五代（5G）移動通信系統(tǒng)階段。多種技術(shù)場景并存的5G環(huán)境具有異構(gòu)性和動態(tài)性的特點，對無線資源管理提出了嚴峻的挑戰(zhàn)。如何實現(xiàn)網(wǎng)絡(luò)資源與用戶需求之間的最佳匹配變得尤為重要。因此，5G環(huán)境下無線資源匹配算法已成為當前研究熱點。提出一種面向蜂窩—D2D混合場景的雙層博弈匹配算法，建立基于用戶體驗質(zhì)量的公平性匹配模型，采用雙層的匹配博弈理論加以求解，通過仿真驗證所提算法的有效性，結(jié)果證明了所提算法的可行性。

5G環(huán)境；蜂窩場景；D2D場景；資源匹配；匹配博弈

1 引言

在過去的數(shù)十年里，移動通信已經(jīng)徹底地改變了人們的生活方式，但人們對于更高性能的移動通信系統(tǒng)的追求卻從未止步。為了適應(yīng)未來5G系統(tǒng)連續(xù)廣域覆蓋、熱點高容量、低功耗大連接和低時延高可靠的技術(shù)場景，在移動物聯(lián)網(wǎng)和互聯(lián)網(wǎng)發(fā)展的驅(qū)動下，移動通信系統(tǒng)進入新的發(fā)展階段，即第五代（5G）移動通信系統(tǒng)階段[1-4]。

在移動通信系統(tǒng)應(yīng)對多樣化的業(yè)務(wù)需求和不斷提升的速率要求時，頻譜資源、能耗和部署成本等成為移動通信系統(tǒng)發(fā)展的主要制約條件。與此同時，5G移動通信系統(tǒng)具有動態(tài)性和異構(gòu)性等特點，均對無線資源管理提出了嚴峻的挑戰(zhàn)。因此，5G環(huán)境下無線資源管理問題成為當前無線通信領(lǐng)域中的研究熱點。

無線資源管理問題本質(zhì)上是指無線資源和用戶的業(yè)務(wù)需求之間的匹配問題。無線資源的匹配算法可以分為3個層次：第一層業(yè)務(wù)側(cè)優(yōu)化算法，即通過降低用戶體驗質(zhì)量，自適應(yīng)地優(yōu)化業(yè)務(wù)傳輸?shù)闹笜艘?，實現(xiàn)業(yè)務(wù)需求與給定網(wǎng)絡(luò)資源的匹配，例如，參考文獻[5]中提出了一種在帶寬有限的情況下，根據(jù)不同用戶的最低需求來調(diào)節(jié)用戶的速率，尋求系統(tǒng)總體效用最大化的速率分配方案；第二層網(wǎng)絡(luò)側(cè)優(yōu)化算法，是指通過對網(wǎng)絡(luò)資源的最優(yōu)匹配實現(xiàn)某種網(wǎng)絡(luò)性能目標（吞吐量，系統(tǒng)傳輸時延），從而保障用戶的業(yè)務(wù)需求，目前這一類匹配是研究的重點，以參考文獻[6]中給出的算法為例，將系統(tǒng)吞吐量作為優(yōu)化指標，采用聯(lián)盟博弈算法來解決多個D2D用戶和蜂窩用戶的上行資源分配問題；第三層網(wǎng)絡(luò)和業(yè)務(wù)匹配算法，通過從網(wǎng)絡(luò)側(cè)與業(yè)務(wù)側(cè)的聯(lián)合優(yōu)化，以最小的資源量和最優(yōu)的分配方式來保障用戶的業(yè)務(wù)體驗質(zhì)量，參考文獻[7]給出了根據(jù)網(wǎng)絡(luò)狀態(tài)適時調(diào)整傳輸負載，然后在滿足傳輸時延要求的情況下，通過優(yōu)化資源調(diào)度方案使系統(tǒng)總體效用最優(yōu)化的算法。

本文研究的匹配算法屬于第二層網(wǎng)絡(luò)側(cè)優(yōu)化算法，對于5G環(huán)境下的信道分配問題，現(xiàn)有的研究主要采用凸優(yōu)化算法[8]、貪心算法[9]和基于博弈論的算法[10-12]。其中基于博弈論的算法應(yīng)用較為廣泛，例如非合作博弈理論常被用于分布式地解決在D2D通信中的資源分配問題[13-15]，但從這個模型中得到納什均衡是單邊不穩(wěn)定的。相比較而言，以匹配博弈理論為基礎(chǔ)的資源分配提供了一種分布式自組織的雙邊穩(wěn)定的匹配。匹配博弈理論最初用于經(jīng)濟學領(lǐng)域，用以解決如婚姻匹配、大學錄取等雙邊的匹配問題[16]。隨著匹配博弈理論的發(fā)展，越來越多的學者將其用于無線通信領(lǐng)域中，用以解決無線資源匹配問題[17]，突破了博弈論的很多局限性。

參考文獻[18]提出了基于匹配博弈理論，為基站中蜂窩用戶分配信道的算法。ZHOU Z Y等人[19]提出了基于博弈理論的D2D通信環(huán)境下以系統(tǒng)能耗作為優(yōu)化指標，采用迭代的方法對頻譜和功率進行聯(lián)合分配的算法。而在參考文獻[20]中，提出了一種以系統(tǒng)的吞吐量為優(yōu)化指標，基于多對多匹配博弈理論的D2D用戶信道分配算法。這些算法均提供了易于實現(xiàn)的架構(gòu)，以解決NP難無線資源分配問題。

但是，上述參考文獻提出的算法中，沒有考慮5G蜂窩—D2D混合場景下同時為蜂窩用戶和D2D用戶分配信道的問題，同時它們大多都是以系統(tǒng)的吞吐量為優(yōu)化指標，且沒有考慮到用戶的公平性問題。而5G環(huán)境下，作為關(guān)鍵技術(shù)之一的D2D通信技術(shù)在提高系統(tǒng)容量和頻率利用率的同時，也為蜂窩用戶引進了干擾，極大地提高了不同用戶信道分配的復(fù)雜度。同時，5G通信系統(tǒng)以用戶體驗為導(dǎo)向，一味追求系統(tǒng)的吞吐量已不再適用，因此本文提出了一種面向蜂窩—D2D混合場景的雙層博弈匹配算法，建立了基于體驗質(zhì)量（QoE）的公平性匹配模型。

2 網(wǎng)絡(luò)場景

圖1 蜂窩—D2D混合場景系統(tǒng)模型

3 模型構(gòu)建

由于5G系統(tǒng)是以用戶體驗為導(dǎo)向的，在該模型中采用QoE作為優(yōu)化指標，用滿意度效用函數(shù)來描述具有不同的速率需求的用戶的QoE，即定義如下：

其中，表示單個用戶的吞吐量，req表示用戶基本速率需求；r表示用戶飽和速率需求，r表示使用戶滿意度下降所對應(yīng)的速率初始值，為斜率參數(shù)。對于每個用戶來講，req、r、r和均可能不同。顯然，QoE指標由兩部分組成：第一部分表明（以用戶基本速率需求為基準）當吞吐量越大，用戶需求越能得到滿足，相應(yīng)的QoE越大；第二部分表明隨著吞吐量增大，用戶需求已經(jīng)完全滿足（達到飽和），以用戶飽和速率需求為基準，再行增加吞吐量，已無法提升用戶體驗，反而會造成成本提高，故相應(yīng)的QoE將會變小?？梢钥闯?，上述定義能夠準確地描述吞吐量與QoE的關(guān)系。

限制條件C1和C2限制CU和DU必須滿足其SINR的要求，C3表明x,j的值只能是0或者1，C4表明每個CU的信道最多能被max個DU復(fù)用，這個條件可以限制每個CU的信道上的干擾，同時減少執(zhí)行的復(fù)雜度，C5限制條件是考慮到用戶的公平性，保證每個DU和CU所獲得的體驗質(zhì)量都能達到它們的最低限度，以防出現(xiàn)信道分配嚴重不均的情況。

4 雙層博弈匹配算法求解

在5G環(huán)境下的蜂窩—D2D混合場景中，存在兩種干擾，即DU復(fù)用CU的資源塊對CU造成的干擾和復(fù)用同一個CU資源塊的DU之間產(chǎn)生的干擾，使DU和CU的匹配結(jié)果相互影響，極大地增加了信道分配問題的復(fù)雜度。因此，本文提出了一種易操作的雙層博弈匹配算法，將這個復(fù)雜的信道分配問題簡化為兩層問題來解決，即第一層：CU分配信道，基于多對一匹配博弈理論，采用蜂窩用戶的信道分配算法求解；第二層：DU復(fù)用CU的資源塊，基于多對多匹配博弈理論，采用D2D用戶的信道分配算法求解。最后再采用迭代的方法分別解決第一層和第二層，即用雙層博弈匹配算法求解該復(fù)雜的信道分配問題。

對于上述涉及多個對象相互作用的問題，匹配博弈理論是一種有效的工具。因此，分別建立基于考慮已存匹配的多對一匹配博弈理論，其中玩家是CU和信道代理商，和考慮已存匹配的多對多匹配博弈理論，其中玩家是DU和信道協(xié)調(diào)器。整個雙層博弈匹配算法的架構(gòu)如圖2所示。接下來，將分析上述兩層問題的求解過程。

圖2 算法整體匹配架構(gòu)

4.1 蜂窩用戶的信道分配算法

定義4 （穩(wěn)定）匹配中不存在阻塞個體和阻塞對。

CU的信道分配方案步驟如下。

步驟1 初始化：建立初始的匹配狀態(tài)。

4.2 D2D用戶的信道分配算法

接下來，考慮建立D2D用戶對（DU）和資源塊RB之間的多對多匹配模型。在網(wǎng)絡(luò)中，CU和DU通過共享頻譜資源來提高頻譜和能量的利用效率，但D2D通信會為蜂窩引進新的干擾。多個DU可以復(fù)用同一個信道，一個DU也可以同時復(fù)用多個信道。因此，利用同一個信道的DU和CU之間存在干擾，利用同一個信道的DU之間也會存在干擾，基于已存匹配的多對多匹配博弈理論來解決DU的信道分配的問題。

這一類型的匹配叫做考慮已存匹配的匹配博弈算法，即每個個體有一個建立在對方個體上的動態(tài)偏好列表，這與傳統(tǒng)上個體擁有固定的偏好列表的匹配算法不同[23]。在這個匹配模型中，偏好列表是在某一匹配狀態(tài)時，根據(jù)DU和RB的效用值建立的。

受到住房分配問題的啟發(fā)，提出一種將其拓展為多對多的匹配博弈算法。和傳統(tǒng)的延遲接受算法不同，本算法允許兩個D2D用戶對直接交換各自的資源塊。為了更好地描述雙方偏好的相互作用關(guān)系，定義交換匹配的概念如下：

基于交換匹配的概念，交換阻塞對定義如下。

定義6 （交換阻塞對）（D,D′）是一個交換阻塞對，當且僅當：

交換操作是在交換阻塞對之間進行的，條件（1）表明交換阻塞對（D,D）進行交換操作之后，參與交換的個體包括資源塊和D2D用戶對的效用不能降低；條件（2）表明至少一個個體的效用在交換之后效用會提高。值得注意的是，空穴的效用和與空穴相匹配的個體無需考慮這兩個條件。

DU的信道分配方案具體步驟如下。

步驟1 建立初始的匹配狀態(tài)，每個DU為其匹配的RB分配能量。

步驟4 每個資源塊RB根據(jù)自己的偏好列表，同意最偏好的用戶的建立交換對的請求，拒絕其他的用戶。

步驟5 更新匹配狀態(tài)，同時更新與每個資源塊匹配的DU個數(shù)。

步驟6 返回步驟1，直到系統(tǒng)中沒有交換阻塞對，即得到穩(wěn)定的匹配。

4.3 算法流程

結(jié)合以上CU和DU的信道分配方案，完整的蜂窩—D2D混合環(huán)境下雙層博弈匹配的算法流程如下。

步驟2 如果迭代次數(shù)不大于最大匹配次數(shù)，即≤max時，執(zhí)行步驟3，否則執(zhí)行步驟4。

步驟4 根據(jù)步驟1匹配結(jié)果，利用DU信道匹配方案，更新分配向量；返回步驟2。

步驟5 得到穩(wěn)定的匹配結(jié)果。

綜上所述，本文提出的雙層博弈匹配算法的匹配流程如圖3所示。

圖3 算法的匹配流程

5 仿真驗證

為了驗證本文提出的雙層博弈匹配算法的有效性，用MATLAB語言編寫了本文算法的驗證程序。在本仿真模型中，以50 m為半徑的圓形區(qū)域內(nèi)隨機分布CU和DU，DU的接收端和發(fā)送端之間的最大距離為20 m。其他系統(tǒng)仿真參數(shù)如下：算法最大迭代次數(shù)max=20；路徑衰減指數(shù)=4；路徑衰減常數(shù)=10?2；DU發(fā)送端最大發(fā)送功率P=23 dBm；CU最大發(fā)送功率Q=23 dBm；信道帶寬=180 kHz；信道噪聲功率0=?114 dBm；每個DU用戶最大復(fù)用用戶信道數(shù)為2。

圖4（a）表示信道數(shù)為6、DU個數(shù)為2時系統(tǒng)總體效用QoE隨CU個數(shù)（cu）的變化曲線。從中看出，隨著蜂窩用戶數(shù)的增加，系統(tǒng)總體效用也增加。圖4（b）表示CU個數(shù)為4、DU個數(shù)為3時系統(tǒng)總體效用QoE隨信道個數(shù)（channel）的變化。從中看出，隨著信道個數(shù)的增加，系統(tǒng)總體效用也不斷增加。而且，由圖4可以看出，本文算法隨著迭代次數(shù)的增加最后趨于穩(wěn)定。

圖4 本文算法性能隨參數(shù)的變化曲線

接下來，將從有效性、穩(wěn)定性、收斂性和復(fù)雜性幾個方面分別將本文提出的雙層博弈匹配的匹配算法（下文簡稱雙層博弈匹配算法）與隨機匹配算法和最優(yōu)化匹配算法進行比較，分析本文提出的雙層博弈算法的性能。

隨機匹配算法以式（2）為優(yōu)化模型，不考慮用戶公平性，采用兩兩隨機匹配的方法求解相應(yīng)模型。最優(yōu)化匹配算法以吞吐量為優(yōu)化目標構(gòu)建最優(yōu)化模型，不考慮用戶公平性，采用多對多匹配博弈理論求解相應(yīng)模型[20]。3種算法的比較指標均采用本文定義的用戶QoE指標。

圖5 3種算法的性能比較

（1）有效性

本文的算法是以QoE為指標進行匹配優(yōu)化的，將該算法與隨機匹配和最優(yōu)化匹配算法兩種方法相比較。在圖5（a）中，在DU個數(shù)為2、信道數(shù)為10時，比較CU個數(shù)變化后，每種算法的對應(yīng)的QoE效用值。在圖5（b）中，當CU個數(shù)為4、信道數(shù)為8時，比較DU個數(shù)變化后，每種算法對應(yīng)的QoE效用值。由于最優(yōu)化匹配算法不考慮用戶公平性，能夠?qū)崿F(xiàn)總體吞吐量的最大化。在某些情況下（QoE指標與總吞吐量呈遞增關(guān)系時），最優(yōu)化匹配算法性能更優(yōu)（如圖5（a）第二個點）；但在大多數(shù)情況下（QoE指標與總吞吐量并不是簡單的遞增關(guān)系），而且雙層博弈匹配算法是直接優(yōu)化QoE指標，故雙層博弈匹配算法性能將更優(yōu)。由圖5（a）和圖5（b）可以看出，雙層博弈匹配算法性能整體優(yōu)于隨機匹配算法和最優(yōu)化匹配算法。

（2）收斂性和穩(wěn)定性

6 結(jié)束語

本文基于匹配博弈理論，結(jié)合5G環(huán)境的特點，提出了蜂窩—D2D混合場景下面向QoE的雙層博弈匹配算法，將復(fù)雜的信道分配問題分層進行解決。首先，建立了第一層蜂窩用戶信道分配算法，然后建立了第二層D2D用戶信道分配算法，從而形成整個算法解決所有用戶信道分配的問題。這個過程中充分考慮了用戶的公平性和用戶之間復(fù)雜的干擾問題，同時改進了系統(tǒng)最優(yōu)化目標函數(shù)，即效用函數(shù)，不再是一味追求高吞吐量，而是考慮用戶的體驗質(zhì)量。本文算法是基于匹配博弈理論，因此匹配的結(jié)果是雙邊穩(wěn)定的，而且該算法不是集中式算法，而是分布式的，不依賴于參與匹配的終端和系統(tǒng)的拓撲結(jié)構(gòu)，具有很好的有效性、收斂性和可行性。

[1] GE X, TU S, MAO G, et al. 5G ultra-dense cellular networks[J]. IEEE Wireless Communications, 2016, 23(1): 72-79.

[2] 陳曉貝, 魏克軍. 全球5G研究動態(tài)和標準進展[J]. 電信科學, 2015, 31(5): 16-19.

CHEN X B, WEI K J. Global research and standardization progress of 5G [J]. Telecommunications Science, 2015, 31(5): 16-19.

[3] 楊峰義, 張建敏, 謝偉良, 等. 5G蜂窩網(wǎng)絡(luò)架構(gòu)分析[J]. 電信科學, 2015, 31(5): 52-62.

YANG F Y, ZHANG J M, XIE W L, et al. Analysis of 5G cellular network architecture [J]. Telecommunications Science, 2015, 31(5): 52-62.

[4] 王胡成, 徐暉, 程志密, 等. 5G網(wǎng)絡(luò)技術(shù)研究現(xiàn)狀和發(fā)展趨勢[J]. 電信科學, 2015, 31(9): 156-162.

WANG H C, XU H, CHENG Z M, et al. Current research and development trend of 5G network technologies [J]. Telecommunications Science, 2015, 31(9): 156-162.

[5] TAN L, ZHU Z, GE F, et al. Utility maximization resource allocation in wireless networks: methods and algorithms[J]. IEEE Transactions on Systems Man & Cybernetics Systems, 2015, 45(7): 1018-1034.

[6] LI Y，JIN D. Coalitional games for resource allocation in the device-to-device uplink underlaying cellular networks[J]. IEEE Transactions on Communications, 2014, 13(7): 3965-3977.

[7] ZUO S, HOU I H, LIU T, et al. Joint rate control and scheduling for real-time wireless networks[J]. IEEE Transactions on Wireless Communications, 2017, 12(1):1-10.

[8] LIANG Y S, CHUNG W H, NI G K, et al. Resource allocation with interference avoidance in OFDMA femtocell networks[J]. IEEE Transactions on Vehicular Technology, 2012, 61(5): 2243-2255.

[9] NGO D T, KHAKUREL S, LE-NGOC T. Joint subchannel assignment and power allocation for OFDMA femtocell networks[J]. IEEE Transactions on Wireless Communication, 2014, 13(1): 342-355.

[10] WANG C, LIU Y, TAO M, et al. Stackelberg game for spectrum reuse in the two-tier LTE femtocell network[C]//Wireless Communications and Networking Conference, April 07-10, 2013, Shanghai, China. Piscataway: IEEE Press, 2013: 1888-1892.

[11] SUN Y, WANG J, SUN F, et al. Energy-aware joint user scheduling and power control for two-tier femtocell networks: a hierarchical game approach[J]. IEEE Systems Journal, 2016.

[12] SUN Y, WANG J, SUN F, et al. Local altruistic coalition formation game for spectrum sharing and interference management in hyper-dense cloud-RANs[J]. IET Communications, 2016, 10(15): 1914-1921.

[13] SONG L, HAN Z, XU C. Resource management for device-to- device underlay communication[M]. New York: Springer, 2014.

[14] LIU J, KATO N, MA J, et al. Device-to-device communication in LTE-Advanced networks: a survey[J]. IEEE Communications Surveys & Tutorials, 2017, 17(4):1923-1940.

[15] ZHOU Z, DONG M, OTA K, et al. Game-theoretic approach to energy-efficient resource allocation in device-to-device underlay communications[J]. Communications IET, 2014, 9(3): 375-385.

[16] GALE D, SHAPLEY L S. College admissions and the stability of marriage[J]. American Mathematical Monthly, 2013, 120(5): 386-391.

[17] GU Y, SAAD W, BENNIS M, et al. Matching theory for future wireless networks: fundamentals and applications[J]. IEEE Communications Magazine, 2015, 53(5): 52-59.

[18] ELHAJJ A M, DAWY Z, SAAD W. A stable matching game for joint uplink/downlink resource allocation in OFDMA wireless networks[C]//2012 IEEE Internation al Conference on Communications, Jun 10-15, 2012, Otlawa, ON, Canada. Piscataway: IEEE Press, 2012: 5354-5359.

[19] ZHOU Z Y, MA G, DONG M, et al. Iterative energy-efficient stable matching approach for context-aware resource allocation in D2D communications[J]. IEEE Access, 2016(4): 6181-6196.

[20] ZHAO J, LIU Y, CHAI K K, et al. Many-to-many matching with externalities for device-to-device communications[J]. IEEE Wireless Communications Letters, 2016, 6(1): 3452-3458.

[21] LONG C, ZHAO H, BAO L, et al. Resource allocation algorithm based on stable matching in hierarchical cognitive radio networks[J]. Journal of Electronics & Information Technology, 2016, 38(11): 123-128.

[22] HOLFELD B, JORSWIECK E. On stable many-to-many matching for distributed medium access with reuse of spectral resources[C]//The 20th International ITG Worksnop on Smakt Antennad (WSA 2016), March 09-11, 2016, Munich, Germany. Berlin: VDE Uerlag, 2016: 536-543.

[23] GU Y, ZHANG Y, PAN M, et al. Matching and cheating in device to device communications underlying cellular networks[J]. IEEE Journal on Selected Areas in Communications, 2015, 33(10): 2156-2166.

A bilevel game matching algorithm in cellular-D2D hybrid scenario

YAO Tian, ZHANG Hui

Nanjing University of Posts and Telecommunications, Nanjing 210003, China

With the rapid development of wireless technologies, wireless access networks enter the 5G system phase. 5G environment with various technical scenarios is heterogeneous and dynamic, causing great challenges for wireless resource management. Hence, it is significant to achieve the optimal matching between network resources and user demands. Therefore, wireless resource matching algorithms in 5G environment have become one of the hottest research directions. A bilevel game matching algorithm in cellular-D2D hybrid scenario was proposed: a QoE based matching model considering user fairness was constructed, the bilevel matching game theory was used to solve this optimization problem, and the effectiveness of proposed algorithm was verified through simulations.

5G environment, cellular scenario, D2D scenario, resource matching, matching game

TN915

A

10.11959/j.issn.1000?0801.2018027

2017?06?13；

2017?11?17

張暉, zhhjoice@126.com

國家自然科學基金資助項目 (No.61471203)；江蘇省“六大人才高峰”項目（No.RJFW-024）；江蘇省“青藍工程”項目(No.2016); 南京郵電大學“1311”人才計劃基金資助項目(No.2015)；通信與網(wǎng)絡(luò)技術(shù)國家工程研究中心開放課題(No.TXKY17002)；江蘇省計算機信息處理技術(shù)重點實驗室開放課題(No.KJS1518)；國家科技重大專項基金資助項目(No.2012ZX03001008-003)

The National Natural Science Foundation of China (No.61471203), Six Talent Peaks Project of Jiangsu Province (No.RJFW-024), “Qing Lan Project” of Jiangsu Province(No.2016), “1311 Talent Program” of NJUPT(No.2015), Open Project of National Engineering Research Center of Communications and Networking(No.TXKY17002), Open Project of Jiangsu Provincial Key Laboratory for Computer Information Processing Technology(No.KJS1518), National Science & Technology Major Project (No.2012ZX03001008-003)

姚天(1995?)，女，南京郵電大學碩士生，主要研究方向為5G資源配置。

張暉(1982?)，男，博士，南京郵電大學副教授、碩士生導(dǎo)師，主要研究方向為下一代網(wǎng)絡(luò)。