基于圖著色的加權優先D2D資源分配算法研究

薛建彬，陳譜滟

(1.蘭州理工大學 計算機與通信學院，甘肅 蘭州 730050；2.東南大學 移動通信國家重點實驗室，江蘇 南京 210096)

?

基于圖著色的加權優先D2D資源分配算法研究

薛建彬1，2，陳譜滟1

(1.蘭州理工大學 計算機與通信學院，甘肅 蘭州 730050；2.東南大學 移動通信國家重點實驗室，江蘇 南京 210096)

針對蜂窩用戶與D2D用戶所構成的異構網絡系統中同頻干擾問題，提出一種基于圖著色的加權優先D2D資源分配算法。該算法不僅允許多個D2D用戶復用一個蜂窩用戶資源，而且能夠實現簡單功控。首先建立異構干擾圖，對系統終端用戶及干擾類型進行分類異構。然后計算著色優先級，考慮各種影響因子以提升算法的實用性。最后再由分配結果進行組內功率控制，以滿足綠色通信的要求。仿真表明，該算法不僅可以降低系統用戶接入損失率，提高系統吞吐量，而且還減少了功率消耗。

資源分配；分類異構；圖著色；功率控制；綠色通信

D2D(Device-to-Device)通信能夠使得短距離范圍內的終端用戶不通過基站轉發而直接進行數據傳輸，從而很大程度提高了數據傳輸速率。此外，D2D用戶還可以用非正交方式復用蜂窩用戶的無線資源以提高頻譜資源利用率，因此，D2D通信在近年來受到業界的廣泛關注[1-3]。然而對無線資源的復用會在系統中產生同頻干擾[4-5]，所以如何通過為D2D用戶分配無線資源以抑制同頻干擾對提高頻譜利用率和滿足用戶的高速數據傳輸需求具有重要的現實意義和研究價值[6-8]。

在文獻[9]中LEE Changhee等人根據D2D用戶提供的干擾列表建立干擾圖，并基于圖著色進行順序資源分配，但該算法對終端設備的性能要求較高。文獻[10]建立D2D用戶和蜂窩用戶間加權二分圖，并采用最優匹配算法分配無線資源，提高了系統吞吐量，但算法復雜度較高。在文獻[11]中HAN Jiang等人允許一個D2D用戶復用一個蜂窩用戶的無線資源，并利用最優匹配實現了最小化系統中同頻干擾。TAB Li等人在文獻[12]中對基于圖著色理論給出一種認知頻譜分配方法，該方法將系統帶寬分為多個子信道，再將子信道分配給用戶，從而最小化帶寬需求，但該方法不能最大化系統吞吐量。此外，現已存在的圖著色資源分配算法均是將D2D用戶與蜂窩用戶作為對等用戶建立常規干擾圖，再進行無線資源分配。然而D2D通信的引入僅僅是作為蜂窩通信的一種輔助通信方式，這樣的無線資源分配不能有效體現出不同通信類型用戶的重要性。此外，傳統圖著色資源分配算法僅根據頂點飽和度來評判著色優先級的策略已遠遠無法滿足實際通信需求。

考慮到上述存在的問題，本文針對D2D用戶復用LTE系統中蜂窩用戶下行鏈路進行通信時，尤其在社交網絡中對通信質量和傳輸速度要求較高的場景下，提出了一種基于圖著色的加權優先D2D資源分配算法。相比于傳統圖著色資源分配算法，該算法的優勢在于：1) 在D2D異構網絡中，建立了一張異構干擾圖，以體現出網絡中兩類用戶重要程度的差異。2)著色順序不再是以往的隨機著色或者順序著色，而采用加權優先著色。3)確定了無線資源分配以后，引入簡單分組功控，不僅能夠進一步減小用戶發送功率降低干擾影響，還能夠動態調整特定無線資源上的能量消耗。最后，結合算法仿真圖，對比分析該算法相對于其他類似算法的優勢。

1　系統模型

在D2D異構網絡中，系統內存在著兩類用戶：傳統蜂窩用戶和短距離D2D用戶對。建立系統模型如圖1所示，系統中共有M個蜂窩用戶，記為C={C1,C2,…,CM}；N個D2D通信對，記為D={D1,D2,…,DN}。其中，Ci表示第i個蜂窩用戶，Txi表示第i個D2D用戶對中的發送端用戶，Rxi表示接收端用戶。同時D2D用戶以相同初始發送功率進行數據傳輸。另外，用LC表示蜂窩鏈路集合，LD表示所有D2D鏈路集合，Lk表示使用無線資源k的鏈路集合。為提高頻譜利用率，允許多個D2D用戶對復用同一蜂窩用戶的無線資源進行數據傳輸。

由于LTE系統下行采用OFDM(Orthogonal Frequency Division Multiplexing)技術，因此，蜂窩用戶之間不存在干擾，而D2D用戶以非正交方式復用蜂窩用戶下行信道資源，則系統中主要存在兩種干擾：D2D用戶對之間的干擾和D2D用戶對與蜂窩用戶之間的干擾。

具體干擾情況如圖1所示。圖中C1，Tx1，Tx2使用相同信道資源進行數據傳輸，基站會對Rx1，Rx2造成同頻干擾；同時Tx1也會對C1和Rx2造成同頻干擾；另外Tx2也會對C1和Rx1造成同頻干擾。由此可見，D2D異構網絡中的干擾情況比較復雜，為此需要對頻譜資源進行合理分配以協調同頻干擾，從而保證終端用戶通信質量并提高頻譜利用率。

圖1　系統模型

此外假設(φi,ri)是用戶i的極坐標，則用戶i與用戶j之間的距離dij在極坐標下表示為

(1)

式中：ri表示用戶i到基站距離；φi表示用戶i方位角。那么系統中的路損模型如下

基站到用戶的路徑損失為

p=148+37.6lg(d[km])

(2)

不同用戶之間的路徑損失為

p=148+40lg(d[km])

(3)

其中，d表示通信鏈路收發端之間的距離。

2　基于圖著色的加權優先資源分配

根據實際情況，在D2D異構網絡中，D2D通信為輔助通信方式，蜂窩用戶是主用戶而D2D用戶僅為從用戶，因此在進行干擾分析時應嚴格對主從用戶進行區分。另外，為滿足用戶的正常通信質量需求，預設蜂窩用戶正常通信的SINR閾值為γ1，D2D用戶正常通信的SINR閾值為γ2。在基于圖著色的加權優先分配資源時，將系統中的通信鏈路和鏈路之間的同頻干擾分別抽象為圖中的“頂點”和“邊”，從而建立一張異構干擾圖H。特別指出，在建立異構干擾圖時，應先將系統中每條通信鏈路抽象為異構圖的“頂點”，然而兩個“頂點”之間“邊”是否存在，則要結合用戶SINR閾值要求和用戶間同頻干擾程度來決定。

2.1建立異構干擾圖

異構干擾圖中的“頂點”由蜂窩鏈路和D2D鏈路構成。其中，所有蜂窩鏈路構成頂點集合V1，所有D2D通信鏈路構成頂點集合V2。V1和V2一起組成圖中所有頂點的集合V。根據頂點間干擾以及用戶的通信質量要求構成邊的集合E，從而可得到異構干擾圖H(V(V1,V2),E)。結合D2D異構網絡的特性，圖H中邊主要分為兩類：單類干擾邊和混合類干擾邊。其中，單類干擾邊則是針對蜂窩鏈路僅收到D2D鏈路的單一干擾所建立的邊；混合類干擾邊則是針對D2D鏈路遭受的干擾為來自蜂窩鏈路和其他D2D鏈路的混合干擾所建立的邊。

當多個D2D用戶對以非正交方式與同一蜂窩用戶使用相同無線資源k時。蜂窩用戶Ci的SINR為

(4)

D2D鏈路接收端Rxj的SINR為

(5)

式中：SINRCi表示Ci的SINR；Pi,k表示基站在信道k上對Ci的發送功率；GB,Ci表示基站到Ci的鏈路增益；PTxj,k表示Txj在信道k上的發送功率；GTxj,Ci表示Txj到Ci的鏈路增益；η表示高斯白噪聲功率；B表示信道帶寬。

另外定義鏈路i的發送端對鏈路j的接收端產生的干擾為Iij，具體表示為

Iij=PiGij

(6)

式中：Pi表示鏈路i發送端的發送功率；Gij表示鏈路i發送端到頂點j的接收端鏈路增益。

邊建立的詳細步驟如下：

1)單類干擾邊建立，步驟(偽代碼)如下：

Begin

1. 初始化集合φi=φ，頂點i=j=1，權值ωij=0

2.fori=1toM

3.Whilej≤Nthen

4. 用公式(5)計算 SINRij

5.φi=φi+{j}

6.endwhile

7.do

8.IfSINRij=min(SINRi)andj∈φithen

9. 頂點j與頂點i之間建立異類干擾邊j→i，并記邊加權值為 ωji=Iji

10.endif

11.While(SINRij>γ1)

12.endfor

13.End

2)混合類干擾邊建立

混合類干擾邊的建立步驟和方法與單類干擾邊的建立類似，不同之處在于第4步，SINR的計算采用式(5)，以及第11步中的判斷條件更改為SINRij>γ2。故此處不再進行贅述。

在單類與混合類干擾邊建立完成之后，最終得到一個異構干擾圖H。此時，根據圖H定義頂點的i飽和度S(i)為

(7)

2.2加權優先資源分配

假設基站端有兩個緩沖隊列，分別存放發起資源請求的蜂窩用戶和D2D用戶，每個用戶對應一個數據隊列用來緩存待發送的數據。為不失一般性，定義影響獲得資源優先級的因素包括：1)信道質量；2)用戶排隊等待時延；3)用戶待發送數據量；4)用戶能忍受的最大時延。一般地，用戶獲得資源的優先級越高，則要求信道質量好、用戶排隊時延大、待發送數據多、用戶可忍受等待時延小。假設用戶i發起資源請求的時刻記為ti,arr_time，獲得無線資源的時刻記為ti,leave_time，那么用戶i在隊列中的排隊等待時延Ti為

Ti=ti,leave_time-ti,arr_time

(8)

當等待時延超過能承受的最大時延時，用戶則會丟棄待發送的數據包。為了避免信道質量差的用戶長時間分配不到資源，降低系統公平性，因此這里將延遲作為影響用戶獲得獲取資源優先級的一個重要因素，定義用戶i的延遲權重為

(9)

式中：Ti,max用戶i允許接受的最大延遲。

假設用戶期望發送數據量的大小為Qi′，數據隊列能緩存的最大數據量為Qi,max，因此對應數據隊列中實際待發送數據大小Qi為

Qi=min{Qi′,Qi,max}

(10)

同時以信噪比衡量信道質量，信噪比越大說明信道質量越好。鏈路i接收端的信噪比具體表示為

(11)

基于上述分析，將用戶i獲得無線資源的優先級定義為

(12)

式中：D(i)表示用戶i獲得資源的優先級；對應頂點i和i′屬于同類集合的頂點。

對頂點著色時，綜合考慮用戶優先級和對應頂點飽和度確定著色順序。根據式(7)和式(12)對圖中頂點i著色等級F(i)定義為

(13)

當前層著色頂點color*需滿足條件為

(14)

同時將已著色頂點從對應頂點集合中刪除，更新未著色頂點。

考慮到D2D通信只是一種輔助通信模式。因此在基于圖著色的異構加權進行著色資源分配時，需要優先對頂點集合V1中的頂點著色，再對集合V2中頂點著色。具體著色步驟(偽代碼)描述如下：

Begin

1. 初始化系統中可用無線資源數為K，可選顏色集合φ={φj|j∈V2,φj=K}，未著色頂點集合?=V2，頂點i=j=1

2.fori=1toM

3. 根據式(13)計算F(i)，確定著色順序并為頂點著色

4.endfor

5.forj=1toN

6. 根據式(13)計算F(j)，更新φj=K-定點j的度

7.endfor

8.Do

9. 根據式(14)找到集合?中頂點著色優先級最高的頂點i

10.Ifφi=1then

11.elseifφi>1then

12. 從φi集合的可用顏色中，選擇已經被其他頂點著色次數最多的顏色，并將其為頂點i著色

13.endif

14.更新未著色頂點集合?=?-i；找到與i相鄰的頂點，并從這些頂點的可用顏色列表中去掉頂點i使用過的顏色

15.while(?=空集)

16.End

為了評判系統中D2D用戶間的公平性，采用jains公平性評估標準如

(15)

式中：Fair表示系統公平性；n表示請求資源的D2D用戶數量；xi表示D2D用戶i的傳輸速率。

將D2D系統用戶損失率定義為因超過最大時延而放棄排隊等待資源分配的用戶數與請求用戶總量比值，具體定義為

(16)

式中：n表示等待時延超過最大時延的D2D用戶數；N表示請求資源的D2D用戶數。

2.3分組功率控制

為了減小用戶終端功率消耗，以保證用戶最低SINR要求為前提，采用簡單功率調控最小化對應用戶的發送功率。根據圖著色無線資源分配結果，將占用相同無線資源的所有用戶作為一個分組，對每組中所有用戶進行功率調控，從而優化用戶的發送功率。

根據資源分配結果，計算蜂窩用戶和D2D用戶實際SINR。結合Cm的SINR閾值γ1和同組Gm的D2D用戶的發送功率，可以得到其最低發送功率為

(17)

式中：Pm′表示經過功率調控后；基站對Cm的發送功率。

按式(17)更新基站對Cm的發送功率，同時結合式(5)計算所有D2D用戶的SINR，并按此時的SINR從大到小逐個更新D2D用戶發送功率。根據閾值要求γ2，更新Gm當前SINR最大的Rxn相應Txn的發送功率表示為

(18)

式中：PTn′表示經功率控制后Tn的發送功率；若Ti發送功率已更新，則PTi為更新后的發送功率，否則為原始功率。

對未更新功率的D2D用戶按照SINR從大到小的順序，繼續采用式(18)更新發送功率，從而減小系統功率消耗。

3　仿真與性能分析

為了評估本文提出的D2D無線資源分配算法對系統性能的影響，采用計算機仿真來進行驗證和分析。用戶在小區內服從均勻分布，蜂窩用戶分布在基站中心200m內，D2D用戶復用蜂窩用戶下行鏈路資源。每個用戶排隊等待時延在仿真時隨機生成，其余仿真參數設置如表1所示。由于所有用戶在小區中的位置具有一定隨機性，仿真次數為500次并取平均值以便得到的數據更具有參考價值。同時，將以隨機著色資源分配算法(RCA)、僅考慮時延的著色資源分配算法(DCA)和傳統圖著色資源分配算法(TGCA)作為參考，對比本文的分配算法(DGCA)，重點考察D2D系統公平、系統吞吐量和系統功率消耗等方面的性能。

表1仿真參數設置

參數名參數取值小區半徑/m750D2D通信對距離/m10～25子信道數5系統帶寬/MHz5蜂窩請求用戶數5基站發送功率/dBm43D2D用戶發送功率/dBm24高斯白噪聲密度/(dBm·Hz-1)-174γ1,γ2/dB12,16蜂窩、D2D鏈路陰影衰落標準差/dB10,12α,β0.7,0.3

圖2比較了不同算法下，D2D系統資源分配的公平性影響。從圖中可以看出，隨著D2D請求對數增加，D2D系統公平度開始下降。其中，TGCA以吞吐量最大為目標，而相對犧牲了較多的公平性。在系統中有80對D2D用戶的情況下使用DGCA算法，則相比于DCA算法可以提高5%的調度公平性。這是因為DCA算法僅考慮時延而沒考慮頂點飽度，而DGCA不僅考慮了頂點飽和度，而且也將時延作為著色的一個因素，能夠在一定程度上提高那些因為信道質量差而遲遲得不到資源的D2D用戶獲得資源的優先級，因此，系統的公平性得到了提高。

圖2　不同算法公平度比較

圖3比較了不同著色資源分配算法下，D2D系統平均時延的影響。由圖可看出不同算法的系統平均時延都隨著資源請求的D2D對數增加而增加。其中，相比于DCA算法，DGCA算法在D2D用戶數達到50對時系統平均時延會稍微偏高0.1 ms，但D2D通信主要用于數據傳輸而非實時業務，因此0.1 ms的延遲對用戶并不感知。另外結合圖2和圖3分析可知DCA算法優先對時延較大的頂點進行著色資源分配，使系統整體時延最小，但是嚴重犧牲了資源調度的公平性。相比于其他兩種算法，DGCA在降低系統時延上則顯示出了明顯的優勢。

圖3　不同算法系統時延比較

圖4比較了不同算法下的系統吞吐量。從圖中可以分析隨著系統中D2D用戶數的增加，系統吞吐量也逐漸增加。由于TGCA算法僅僅根據頂點飽和度進行著色資源分配，而獲得了最大的系統吞吐量。DGCA不僅考慮了頂點飽和度還提高了時延較大頂點的著色優先級，使得丟棄的數據包較少，雖然獲得的吞吐量相比于TGCA有平均1.5%的降低，但結合圖2、圖3和圖4綜合分析，TGCA獲取較高吞吐量的前提則是嚴重犧牲了用戶調度的公平性以及很大程度上增加了系統的時延。

圖4　不同算法下系統吞吐量比較

圖5比較了不同閾值對系統吞吐量的影響。圖中顯示隨著D2D對數增加，系統吞吐量增加，而閾值越大，系統吞吐量越小。這是因為未達到用戶SINR閾值時，系統接入D2D對數隨著請求D2D對數增加而增加，從而系統吞吐量也增加，而SINR閾值越大，用戶能承受的干擾越小，允許接入的D2D對數越少，系統吞吐量就越小。

圖5　SINR閾值對系統吞吐量影響

圖6比較了有功率控制和無功率控制時系統總的功率消耗。沒有功率控制時，基站和用戶均以固定功率發送，而有功率控制時，根據用戶SINR最低要求進行功率控制，從而減小了系統功率消耗。

圖6　功率控制對系統功耗影響

4　結語

在TD-LTE系統中為D2D用戶選擇合適的蜂窩用戶下行無線資源進行復用。首先根據用不同通信類型戶間干擾程度，建立異構干擾圖。進一步結合頂點飽和度、等待時延、信道質量、數據量計算加權優先著色順序。最后根據圖著色算法進行無線資源的分配。理論上，改進了現有圖著色資源分配算法的不足，并實現了系統最大吞吐量性能。實際上，又將影響無線資源分配的因素全面考慮，具有很強的實際應用價值。

仿真表明，本文算法在系統平均時延、丟包率以及系統吞吐量方面的綜合性能最好，同時還減少了系統總功率消耗。

[1]DOPPLER K，RINNE M，WIJTING C，et al. Device-to-device communication as an underlay to LTE-advanced networks[J]. IEEE communications magazine，2009，47(12)：42-49.

[2]SARTORI P，BAGHERI H，DESAI V，et al. Design of a D2D overlay for next generation LTE[C]//Vehicular Technology Conference.[S.l.]： IEEE，2014：1-5.

[3]MOUBAYED A，SHAMI A，LUTFIYYA H. Wireless resource virtualization with device-to-device communication underlaying LTE network[J]. IEEE transactions on broadcasting，2015，61(4)：734-740.

[4]XIN Q，KANG C G. An effective interference alignment approach for device-to-device communication underlaying multi-cell interference network[C]//2012 International Conference on ICT Convergence (ICTC) .[S.l.]：IEEE，2012：219-220.

[5]ZHANG B，WANG Y，JIN Q. Energy-efficient architecture and technologies for device to device (D2D) based proximity service[J]. China communication，2015，12(12)： 32-42.

[6]PHUNCHONGHARN P，HOSSAIN E，KIM D I. Resource allocation for device-to-device communications underlaying LTE-advanced networks[J]. IEEE wireless communications，2013，20(4)：91-100.

[7]TSOLKAS D，LIOTOU E，PASSAS N，et al. A graph-coloring secondary resource allocation for D2D communications in LTE networks[C]//Proc.International Workshop on Computer Aided Modeling & Design of Communication Links & Networks. Barcelona：IEEE，2012：56-60.

[8]BIN WANG，LI CHEN，XIAOHANG CHEN，et al. Resource allocation optimization for device-to-device communication underlaying cellular networks[C]//Proc. Vehicular Technology Conference (VTC Spring).Budapest：IEEE，2011：1-6．

[9]LEE C，OH S M，PARK A S. Interference avoidance resource allocation for D2D communication based on graph-coloring[J]. Journal of Korean institute of communications & information sciences，2014，39A(12)：729-738.

[10]ZHANG H，WANG T，SONG L，et al. Radio resource allocation for physical-layer security in D2D underlay communications[C]//Proc. IEEE International Conference on Communications.Sydney：IEEE，2014：2319-2324.

[11]HAN J，CUI Q，YANG C，et al. Bipartite matching approach to optimal resource allocation in device to device underlaying cellular network[J]. Electronics letters，2014，50(3)： 212-214.

[12]TAB I，FENG Z，LI W，et al. Graph coloring based spectrum allocation for femtocell downlink interference mitigation[C]//Proc. IEEE Wireless Communications & Networking Conference. Cancun：IEEE，2011：1248-1252.

薛建彬(1973— )，教授，博士，主要研究方向為無線通信理論與技術，為本文通信作者；

陳譜滟 (1991— )，碩士，主研無線通信理論與技術。

責任編輯：許盈

Resource allocation algorithm based on graph coloring for weighted priority D2D communication

XUE Jianbin1，2, CHEN Puyan1

(1.SchoolofComputerandCommunication,LanzhouUniversityofTechnology,Lanzhou730050,China;2.NationalMobileCommunicationsResearchLaboratory,SoutheastUniversity,Nanjing210096,China)

In order to solve the co-channel interference problem in heterogeneous network system composed of cellular users and D2D users, a weighted priority D2D resource allocation algorithm based on graph coloring is proposed. This algorithm not only allows multiple D2D users to reuse the radio resource of one cellular user, but also can achieve simple power control. Firstly, the heterogeneous interference pattern is established based on the user equipment in system and the different types of interferences. And then the color priority is calculated, taking into account a variety of factors to improve the practicality of the algorithm. Finally, according to the results of the allocation of resources to control the power of user equipments of the group, to meet the requirements of green communication. Simulation results show that the proposed algorithm can not only reduce the loss rate of user equipments access the system and improve the system throughput, but also reduce the power consumption.

resource allocation; classification heterogeneous; graph coloring; power control; green communication

TN929.5

A

10.16280/j.videoe.2016.09.011

東南大學移動通信國家重點實驗室開放研究基金資助課題(2014D13)；甘肅省自然科學基金項目(1310RJZA003)

2016-03-14

文獻引用格式：薛建彬，陳譜滟. 基于圖著色的加權優先D2D資源分配算法研究[J].電視技術，2016，40(9)：56-61.

XUE J B, CHEN P Y. Resource allocation algorithm based on graph coloring for weighted priority D2D communication [J].Video engineering，2016，40(9)：56-61.