一種5G異構(gòu)云無線接入網(wǎng)絡(luò)的D2D資源分配算法*

張永棠，趙元成

(1.廣東東軟學(xué)院 計算機學(xué)院，廣東 佛山 528225；2.南昌工程學(xué)院 江西省協(xié)同感知與先進(jìn)計算技術(shù)研究所，南昌 330003)

0 引 言

網(wǎng)絡(luò)規(guī)模的擴大和數(shù)據(jù)流量的增長對5G網(wǎng)絡(luò)的發(fā)展和演進(jìn)提出了一系列新的挑戰(zhàn)。為了解決這些問題，異構(gòu)云無線接入網(wǎng)(Heterogeneous Cloud Radio Access Network,H-CRAN)和設(shè)備到設(shè)備(Device-to-Device,D2D)通信結(jié)合是應(yīng)對5G網(wǎng)絡(luò)挑戰(zhàn)的關(guān)鍵技術(shù)。

H-CRAN是一種結(jié)合了異構(gòu)網(wǎng)絡(luò)(Heterogeneous Network,HetNet)和云無線接入網(wǎng)絡(luò)(Cloud Radio Access Network,C-RAN)優(yōu)點的5G無線接入網(wǎng)絡(luò)架構(gòu)，通過異構(gòu)大功率節(jié)點傳輸整個網(wǎng)絡(luò)控制信號，提高網(wǎng)絡(luò)的能量效率。

D2D通信是用戶在不通過基站(Base Station,BS)的情況下直接通信，這可以減少BS上的負(fù)載，有效提高系統(tǒng)吞吐量、能源效率和頻譜效率，符合5G網(wǎng)絡(luò)的發(fā)展趨勢。D2D通信需要共享宏用戶設(shè)備(Macrouser Equipment，MUE)的資源。因此，如何配置資源可以提高網(wǎng)絡(luò)中的系統(tǒng)吞吐量是近年來研究的一個重要問題。

隨著5G網(wǎng)絡(luò)的發(fā)展和演進(jìn)，D2D通信技術(shù)被引入到HetNet中，解決H-CRAN網(wǎng)絡(luò)中的基帶處理單元(Base Band Unit,BBU)與射頻拉遠(yuǎn)(Remote Radio Head,RRH)的鏈路受限問題[1-3]。文獻(xiàn)[4]提出了一個靜態(tài)博弈模型，并將其推廣到一個重復(fù)博弈模型，基于這種重復(fù)模型，提出了一種基于基站與設(shè)備交互的資源分配協(xié)議。這是該領(lǐng)域的經(jīng)典算法，現(xiàn)有的研究大多是基于該算法進(jìn)行改進(jìn)。

然而，已有的文獻(xiàn)都是基于蜂窩網(wǎng)絡(luò)架構(gòu)對蜂窩用戶和D2D用戶的相互干擾和信道共享等問題進(jìn)行研究，很少有文獻(xiàn)論述基于D2D 復(fù)用 H-CRAN 網(wǎng)絡(luò)場景下資源的分配方案，考慮整體系統(tǒng)的吞吐量。并且在已有文獻(xiàn)中，都是將D2D的模式假設(shè)為確定的。但在實際環(huán)境中，通信信道的接入和釋放都是隨機的，干擾的約束條件是動態(tài)選擇的。因此，本文將匹配理論應(yīng)用于H-CRAN下的動態(tài)資源分配。為了達(dá)到最大系統(tǒng)吞吐量的目標(biāo)，需要D2D和中繼用戶終端(Relay User Equipment,RUE)在保證所有用戶服務(wù)質(zhì)量(Quality of Service，QoS)要求的情況下找到適合頻譜共享的MUE。該問題被認(rèn)為是一個整數(shù)非線性規(guī)劃(Integer Nonlinear Programming，INLP)問題。為了解決這個問題，本文將資源分配問題轉(zhuǎn)化為一對一的匹配問題，一個D2D/RUE只允許共享一個MUE頻譜資源，而一個MUE頻譜資源只允許共享一個D2D/RUE。

本文工作的主要創(chuàng)新點：將婚姻匹配算法應(yīng)用于資源分配問題，提出了一種資源分配算法來執(zhí)行MUE與D2D/RUE之間的初始匹配;在初始匹配的基礎(chǔ)上，提出了一種符合卡爾多-?？怂?Kaldor-Hicks)原則的資源交換策略，實現(xiàn)系統(tǒng)總體吞吐量的最大化，并通過仿真實驗驗證了該算法的有效性。

1 系統(tǒng)模型與問題表述

1.1 系統(tǒng)模型

H-CRAN系統(tǒng)的下行鏈路傳輸模型如圖1所示。假設(shè)存在1個BS、N個 RRH、C個MUE、L對D2D、H個RUE，使用R={Rr|1≤r≤N},M={Mi|1≤i≤C},D={Dd|1≤d≤L},K={Kj|1≤j≤H}分別表示RRH、MUE、D2D和RUE的集合。此外，假設(shè)Hr是每個RRH中RUE的數(shù)目，且H=∑r∈NHr，Kr,j表示RRH中的第j個RUE。在本文中，假設(shè)L+H=C。

圖1 系統(tǒng)模型

假設(shè)BS將頻譜資源分配給MUE。為了解決頻譜資源不足的問題，D2D和RUE需要共享MUE的資源。為了便于討論，D2D對和RUE被視為同一類型的用戶，它們被統(tǒng)一地表示為V，且V={Vn|1≤n≤L+H}。假設(shè)一個MUE的頻譜資源可以由一個D2D/RUE共享，而一個D2D/RUE只能共享一個MUE頻譜資源。也就是說，這個問題可以看作是一對一的資源分配問題，為D2D對和RUES進(jìn)行合理的資源分配，以達(dá)到最大系統(tǒng)吞吐量的目標(biāo)。所有資源由BS統(tǒng)一分配。

為了更好地描述資源分配問題，使用二進(jìn)制數(shù)xr,i,j表示Mi的頻譜資源是否分配給Kr,j，二進(jìn)制數(shù)yd,i表示Mi的頻譜資源是否分配給Dd。在該模型中，假設(shè)功率為常數(shù)。當(dāng)被DR共享時，信干噪比(Signal-to-Interference plus Noise Ratio,SINR)和可達(dá)數(shù)據(jù)率分別為

(1)

ζi=Wilb(1+Φi)。

(2)

當(dāng)RUE共享的頻譜資源為Mi時，Kr,j的信噪比和可達(dá)數(shù)據(jù)率分別為

(3)

ζr,j,i=Wilb(1+Φr,j,i)。

(4)

當(dāng)D2D對共享的頻譜資源為Mi時，Dd的信噪比和可達(dá)數(shù)據(jù)率分別為

(5)

ζd,i=Wilb(1+Φd,i)。

(6)

式中：Wi為Mi的帶寬，σ2為加性高斯白噪聲的功率。

1.2 問題描述

資源分配的目的是將資源合理地分配給D2D和RUE，以實現(xiàn)資源共享，提高系統(tǒng)吞吐量。因此，在進(jìn)行資源分配時，需要滿足基本的QoS要求，控制用戶集V對MUE的干擾程度。

最大吞吐量問題可以表述為[5]

(7)

s.t.

(8)

(9)

(10)

(11)

(12)

(13)

式(7)～(13)約束條件構(gòu)造的問題是一個INLP問題。當(dāng)H-CRAN中涉及的RRH、RUE、MUE、D2D等用戶數(shù)變大時，問題將變得難以求解，這是NP復(fù)雜問題?；诒疚奶岢龅哪繕?biāo)，下一節(jié)將提出一種資源交換策略來有效地解決這個問題。

2 資源分配問題求解

本節(jié)解釋如何使用資源交換策略來解決資源分配問題，以最大化系統(tǒng)吞吐量。該方法遵循卡爾多-?？怂乖韀6]。

2.1 初始資源分配算法

這里把資源分配問題看作是一對一的匹配博弈，一個用戶Mi對應(yīng)一個用戶Vn。首先，進(jìn)行初步的資源分配，得到Mi與Vn之間的初始匹配；然后，在初始匹配的基礎(chǔ)上，通過資源交換策略使系統(tǒng)吞吐量最大化。初始匹配可以在一定程度上減少資源交換操作的數(shù)量。

定義1(匹配u) 假設(shè)有兩個集合M和V，元素分別由Mi(1≤i≤C)和Vn(1≤n≤L+H)表示。如果Vn向Mi提出一個匹配請求，并且Mi接受這個提議，則Vn和Mi是一個匹配對，其數(shù)學(xué)方式表示為Mi=u(Vn)和Vn=u(Mi)。

目標(biāo)是完成雙方一對一的匹配。首先，根據(jù)偏好值建立雙向偏好列表，首選項值取決于用戶吞吐量。根據(jù)偏好列表，集合V中的用戶依次向集合M中的用戶提出匹配請求。當(dāng)用戶Vn共享Mi資源時，由用戶Vn和Mi生成的偏好值分別由等式(14)和(15)計算:

Pn,i=Wilb(1+Φn,i)，

(14)

Pi,n=Wilb(1+Φi)。

(15)

所有偏好值的計算、偏好列表的建立和信息的傳播都是由BS來統(tǒng)一分配的。

定義2(偏好算子?) 如果在用戶Vn的偏好列表中，Mp的偏好值高于Mq，即相比于Mq，Vn更愿意匹配Mp，數(shù)學(xué)方式表示為

Mp?vnMqPn,p>Pn,q。

(16)

同理，如果在用戶Mi的偏好列表中，Vm的偏好值高于Vn，即相比于Vn，Mi更愿意匹配Vm，數(shù)學(xué)方式表示為

Vm?miVnPm,i>Pn,i。

(17)

根據(jù)蓋爾-沙普利(Gale-shapely，GS)[7]婚姻穩(wěn)定匹配算法，本文提出了一種基于偏好列表的婚姻匹配算法。在模型中，根據(jù)方程(14)和(15)建立偏好列表，并利用婚姻匹配算法(算法1)的思想對M和V的集合進(jìn)行初始匹配。算法1的偽代碼如下：

輸入:所有用戶V的偏好列表ξ和所有用戶M的偏好列表?

輸出:初始匹配u

1 設(shè)置不匹配用戶Vn∈V列表ΩV和不匹配用戶Mi∈M列表ΩM；

2 whileΩV≠? do

3 ifu(Mi)=? then

4Mi=u(Vn),Vn=u(Mi);

5ΩM=ΩMMi,Ωv=ΩvVn;

6 else

7 ifVn?miu(Mi) then

8Ωv=Ωv∪u(Mi),Mi=u(Vn);

9Vn=u(Mi),Ωv=ΩvVn;

10 else

11Mi拒絕Vn，并保持u(Mi);

12Vn在偏好列表中的尋找下一個匹配項;

13 end if

14 end if

15 end while

16 輸出匹配項u

該算法主要思想是：用戶Vn向用戶Mi發(fā)送請求，并且Mi在Vn偏好列表中具有最高的偏好值，如果Mi沒有伴侶，Mi接受Vn；如果Mi有伴侶，Mi判斷用戶Vn偏好值是否高于其現(xiàn)有伴侶，如果它更高，那么Mi接受Vn，否則Mi拒絕Vn；只要Vn被拒絕，Vn就可以向其首選項列表中的下一個用戶發(fā)出請求，直到用戶集V中的所有用戶都得到一個伴侶，算法結(jié)束。

2.2 配對博弈的交換策略

算法1的執(zhí)行可以對M和V的集合進(jìn)行初始匹配。在此基礎(chǔ)上，提出一種遵循卡爾多-?？怂乖韀8]的資源交換方法，實現(xiàn)系統(tǒng)吞吐量的最大化。

定義3(Kaldor-Hicks原理) Kaldor-Hicks意味著第三方的總成本不超過交易的總收益。也就是說，從結(jié)果中獲得的收益可以完全補償所遭受的損失。

本文中，在資源交換策略不影響其他匹配對的前提下，參與資源交換的部分用戶(如D2D/RUE/MUE)降低了整體吞吐量，部分用戶增加了交換后的吞吐量。只要增加的吞吐量足以補償減少的吞吐量，并且系統(tǒng)的總吞吐量增加，則認(rèn)為它就達(dá)到了Kaldor-Hicks。Kaldor Hicks實際上是總體吞吐量的最大化標(biāo)準(zhǔn)[9]。

資源交換必須滿足以下條件：交換后仍保證MUE的QoS要求;除了參與交換的對之外，其他匹配對的吞吐量不應(yīng)受到影響;交換后必須增加系統(tǒng)吞吐量。

交換資源方法要求首先找到一組可以交換資源的用戶。集合中的每個用戶都需要滿足這樣的條件，即它們必須更喜歡另一個用戶的伴侶(至少有一個用戶在同一個集合中)才能比原來的伴侶更好。例如，u(Vm)?vnu(Vn)表示Vn更喜歡Vm的伴侶，而不是其原始伴侶。為了更方便表達(dá)，Vm被稱為Vn的合作對象。如果V1是V2的合作對象，V2是V3的合作對象，…，Vn-1是Vn的合作對象，V1,V2,V3,…,Vn-1,Vn構(gòu)成一個可以交換資源的集合。然后，V1的資源可以移交給V2，V2的資源可以移交給V3，…，Vn-1的資源可以移交給Vn。從上面可以看出，當(dāng)用戶交換資源的方向可以形成循環(huán)時，則可以進(jìn)行交換操作。

本文提出一種求圖中最大環(huán)的啟發(fā)式算法[8]，通過構(gòu)造圖和查找循環(huán)[10]兩個步驟來求解用戶資源交換問題。考慮到吞吐量最大化的目的不是在圖中找到最大環(huán)路，而是在資源交換之后依次找到能夠最大化系統(tǒng)吞吐量的環(huán)路。因此，需要根據(jù)一定的規(guī)則建立構(gòu)造圖。首先，以集合V中的所有用戶作為圖的頂點，為用戶找到合作對象，并建立從用戶到他們的合作對象的有向邊，從而創(chuàng)建了一個有向圖；然后，在有向圖中找到所有現(xiàn)有的循環(huán)，并形成一個集合E；最后，根據(jù)上述資源交換方法進(jìn)行資源交換，在資源交換后選擇符合Kaldor-Hicks原理的循環(huán)，并根據(jù)系統(tǒng)吞吐量的改進(jìn)程度對這些選定的循環(huán)進(jìn)行排序。根據(jù)貪心策略，找到吞吐量改善最大的循環(huán)作為交換資源的第一個循環(huán)。在此之后，依次選擇的循環(huán)需要滿足兩個條件(一是它與以前選擇的循環(huán)沒有公共頂點；二是在剩余的環(huán)路中，存在能夠最大限度地提高系統(tǒng)吞吐量的環(huán)路)，直到?jīng)]有循環(huán)可供選擇。

在循環(huán)中用戶的資源交換完成后，參與交換的每個用戶將獲得一個新的可共享資源。也就是說，形成了新的匹配。根據(jù)原始偏好列表和新的匹配，重構(gòu)有向圖，直到在形成的圖中找不到循環(huán)，停止資源交換，形成最終的匹配。資源交換算法(算法2)偽代碼如下：

輸入:基于算法1的初始匹配u

輸出:最終匹配u′

1 根據(jù)上述規(guī)則，建立基于匹配u的圖G;

2 ifG??

3u′=u;

4 else

5 { for 所有頂點的Γi∈G

6 { whileΓi未被訪問 do

7 訪問Γi;

9 { while 合作對象 do

10 { if(Γnext沒有被訪問)

11 訪問next(Γnext);

12 else if(Γnext被訪問&&Γnext=Γi)

13 找到一個循環(huán)e;

14E=E∪{e};

15 else

16 continue;}}}}

17 forei∈E

18 {選擇交換資源后吞吐量提升最大的環(huán)作為交換的第一循環(huán);

19 按吞吐量改進(jìn)順序選擇另一個循環(huán)，該循環(huán)與已選擇的循環(huán)沒有相同的頂點;

20 建立一個新的匹配u′

21u=u′;}

22 根據(jù)新的匹配重復(fù)步驟1～16。

該方法提高了參與交換的用戶Vn的吞吐量，但對用戶Mi吞吐量的影響是不確定的。不同用戶共享MUE的資源，會對其造成不同程度的干擾，MUE的吞吐量可能下降，也可能上升，需要應(yīng)用Kaldor-Hicks來確保系統(tǒng)吞吐量的提高。因此，本文提出的交換策略，只要增加的吞吐量足以補償減少的吞吐量和總體吞吐量的增加就允許交換，符合Kaldor-Hicks原則。

2.3 復(fù)雜度分析

不失一般性，認(rèn)為H≈N>C。假設(shè)a1、a2分別表示算法1和算法2在收斂前的迭代次數(shù)。根據(jù)2.2節(jié)的交換策略，每一次用戶資源交換后，算法2都會被重新執(zhí)行一次，直至集合V中的所有用戶為節(jié)點的圖G中找不到循環(huán)，即找不到被移出的MUE。可以看出，在最壞的情況下，集合V需要被簡化H次，則算法2需要被執(zhí)行a1·a2·H次，每次執(zhí)行算法2的運算復(fù)雜度為O(H(NC)3)。因此，采用本文提出的資源匹配方案，獲得系統(tǒng)吞吐量的最大化的整體復(fù)雜度近似表示為O(a1·a2·H2(NC)3)。

3 仿真驗證及結(jié)果分析

3.1 仿真設(shè)計

根據(jù)圖1的系統(tǒng)模型，部署了H-CRAN下行傳輸場景。其中，BS放置在半徑為500 m的仿真場景中心，坐標(biāo)是(0,0)；場景中隨機分布D2D、RUE和MUE，每個用戶的位置不重疊。為了便于討論，假設(shè)D2D與RUE之和等于MUE的數(shù)目。所有實驗結(jié)果取100次試驗的平均值，并將本文算法與文獻(xiàn)[3]、文獻(xiàn)[4]、隨機接入算法的仿真結(jié)果進(jìn)行比較。實驗參數(shù)如表1所列。

表1 部分仿真參數(shù)設(shè)置

3.2 仿真結(jié)果分析

圖2展示了三種算法在不同用戶數(shù)的情況下生成的用戶集V的吞吐量，可以看出，隨機接入的性能最差且曲線平坦。由于在隨機接入中，沒有采用有效的主動策略來提高系統(tǒng)的吞吐量，并且系統(tǒng)的帶寬限制了系統(tǒng)的吞吐量，因此，只要系統(tǒng)帶寬保持不變，用戶集V產(chǎn)生的吞吐量之和本質(zhì)上是相同的，而受用戶數(shù)的數(shù)量影響非常小，幾乎可以忽略。

圖2 用戶集V的總吞吐量

本文所提算法的性能明顯優(yōu)于文獻(xiàn)[4]算法，因為本文算法在資源交換操作中考慮了用戶Vn∈V的吞吐量，只有在Vn吞吐量增加時才允許資源交換操作，該策略保證了用戶集V的吞吐量增加。除隨機算法生成的曲線外，其余兩條曲線均呈上升趨勢。由于帶寬的限制，隨著用戶數(shù)量的增加，最終區(qū)域變平。與文獻(xiàn)中的算法相比，本文算法總吞吐量均得到了提高，較文獻(xiàn)[4]提高了約15%，隨著用戶數(shù)量的增加，較文獻(xiàn)[11]的優(yōu)勢更加明顯。因此，該算法在提高用戶集V的吞吐量方面具有較好的性能。

圖3展示了三種算法在不同用戶數(shù)情況下產(chǎn)生的系統(tǒng)吞吐量，可見由于缺乏主動策略和系統(tǒng)帶寬的限制，隨機算法的性能仍然是最差的。與文獻(xiàn)[4]算法相比，本文算法在提高系統(tǒng)吞吐量方面有更好的性能，系統(tǒng)吞吐量提高了約8%。由于本文算法中使用了Kaldor-Hicks，保證了每次交換資源時系統(tǒng)吞吐量的提高。與文獻(xiàn)[11]對比，在D2D用戶對數(shù)量比較少的時候，該算法略有不足，但是隨著用戶對數(shù)量的增加，該算法的優(yōu)勢開始顯現(xiàn)。因此，本文算法在系統(tǒng)吞吐量方面有較好的實驗結(jié)果。

圖3 系統(tǒng)的吞吐量

圖4展示了D2D傳輸功率對總吞吐量的影響，可以看出，隨著D2D用戶的功率增大，三種算法的總吞吐量都是呈上升趨勢;當(dāng)功率達(dá)到50 dBm時，文獻(xiàn)[4]和隨機接入算法的吞吐量最終趨于平緩，這是由于傳輸功率的增加會引起D2D用戶之間的干擾也增大，最終導(dǎo)致平緩。本文算法以及采用了動態(tài)窮舉的文獻(xiàn)[11]算法均獲得了較高的吞吐量，并且隨著傳輸功率的增加，本文算法的優(yōu)勢更加明顯，證明了本文算法采用的資源交換分配方案能有效解決D2D用戶之間的干擾，承受較大傳輸功率的通信，使頻譜的利用率得到提高。

圖4 傳輸功率與吞吐量的關(guān)系

圖5展示了D2D用戶鏈路間距對吞吐量的影響，可以看出，在D2D傳輸功率保持不變的情況下，吞吐量與D2D用戶鏈路間距是成反比的。隨著鏈路間距的增大，文獻(xiàn)[4]和隨機接入算法的性能下降非常明顯，而本文算法雖有下降，但是下降程度較緩。隨著D2D用戶鏈路間距的增加，本文算法的吞吐量優(yōu)于文獻(xiàn)[11]。這一結(jié)果進(jìn)一步驗證了本文算法具有較強抗信道干擾能力。

圖5 用戶鏈路間距與吞吐量的關(guān)系

為了驗證本文提出的資源分配方案具有均衡性和穩(wěn)定性，對RRH與BS分別按3∶7、7∶3兩種不同的混合接入策略，以及用戶全部接入RRH和用戶全部接入BS兩種極端情況進(jìn)行實驗，并與文獻(xiàn)[4]、文獻(xiàn)[11]進(jìn)行對比。圖6展示了D2D用戶的平均收益及迭代次數(shù)的關(guān)系，可以看出，兩種全部接入的極端情況，用戶平均收益都是非常低，并且是完全均衡的；文獻(xiàn)[4]和文獻(xiàn)[11]的用戶平均收益明顯好于兩種極端接入，但還是低于本文算法的通信效率。

圖6 用戶平均收益與迭代次數(shù)的關(guān)系

此外，本文算法用戶可以按照最合適的比例選擇混合接入，提高用戶的平均收益。在博弈達(dá)到均衡之前，用戶收益曲線會有一些振蕩，這是因偏好值計算及偏好列表更新引起的；經(jīng)過不斷迭代逐漸趨向博弈均衡，獲得最優(yōu)的收益，本文算法的兩種比例接入均達(dá)到了均衡，并且明顯優(yōu)于其他算法。此時的迭代次數(shù)約10次，并且本文算法的收斂速度優(yōu)于文獻(xiàn)[11]，進(jìn)一步驗證了本文算法的復(fù)雜度較低。

4 結(jié) 論

由于5G H-CRAN頻譜資源的不足，導(dǎo)致D2D共享出現(xiàn)信號干擾問題。為了解決此問題，本文運用婚姻匹配算法來解決5G H-CRAN下的D2D資源分配，提出了一種新的算法來執(zhí)行MUE與D2D/RUE之間的初始匹配，由BS將頻譜資源分配給MUE，然后將D2D和RUE合理共享MUE的資源，實現(xiàn)一對一的初始匹配。在初始匹配的基礎(chǔ)上，提出了一種符合卡爾多-?？怂乖瓌t的資源交換策略，實現(xiàn)系統(tǒng)總體吞吐量的最大化。仿真結(jié)果表明，該算法對系統(tǒng)的吞吐量、用戶平均增益都有明顯的提高，具有算法復(fù)雜度低、收斂速度快等優(yōu)點。