,,,

(1.解放軍理工大學 通信工程學院,南京 210007; 2.南京電訊技術(shù)研究所,南京 210007)

0 概述

隨著移動互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、智能終端的飛速發(fā)展,不斷增長的無線業(yè)務(wù)需求對帶寬和速率提出了極高要求。設(shè)備到設(shè)備(Device-to-Device,D2D)通信技術(shù)被視作一種提高資源利用率、增強用戶體驗的關(guān)鍵技術(shù)[1-2]。通過運用D2D技術(shù),兩個距離較近的通信設(shè)備之間可以不通過基站直接通信,這不僅降低了通信時延,而且提高了系統(tǒng)吞吐量[3-4]。但是,D2D技術(shù)帶來便利的同時,也帶來一些挑戰(zhàn)。因為D2D復(fù)用頻譜資源時會對系統(tǒng)中的授權(quán)用戶造成干擾,降低系統(tǒng)性能,所以如何合理地對頻譜資源進行分配顯得尤為重要[5]。目前,大量文獻對D2D網(wǎng)絡(luò)的干擾管理作了研究。例如,文獻[6]提出了一種基于比例公平的啟發(fā)式資源分配方案。在提高系統(tǒng)吞吐量的同時,兼顧了公平性。文獻[7]對多小區(qū)CDMA系統(tǒng)D2D通信上行性能進行了研究。文獻[8]提出了一種D2D通信中基于信噪比均衡的資源分配算法。文獻[9]將信道分配問題建模成混合非線性整數(shù)規(guī)劃問題,利用貪婪啟發(fā)式算法對模型進行求解。但是每個信道至多被一個D2D用戶對復(fù)用,無法獲得較高的頻譜利用率。文獻[10]用拍賣博弈的方法對蜂窩網(wǎng)絡(luò)中的信道分配進行了分析。在文獻[11-12]中,為了保證蜂窩用戶的服務(wù)質(zhì)量,將問題建模成具有靜態(tài)配額的多對一匹配模型。

受此啟發(fā),本文提出一種在保證各蜂窩授權(quán)用戶服務(wù)質(zhì)量的情況下,各資源塊可動態(tài)地被多個D2D用戶同時復(fù)用的資源分配算法。利用雙邊匹配理論,將問題建模成多對一匹配問題。D2D用戶和資源塊(Resource Block,RB)根據(jù)各自設(shè)計好的效用函數(shù)分別建立偏好序,最后通過改進遞延算法形成穩(wěn)定的資源分配方案。

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

圖1 系統(tǒng)模型

(1)

C3:xdi,j={0,1},?di∈D,j∈R

在P1中,限制條件C1規(guī)定所有DUE在RBj上對CUEcj造成的干擾低于CUEcj的干擾門限,從而保證了cj的服務(wù)質(zhì)量。限制條件C2規(guī)定各DUE至多復(fù)用一個RB。顯然P1是一個混合0-1規(guī)劃問題,其復(fù)雜度是指數(shù)冪。復(fù)雜度會隨著網(wǎng)絡(luò)規(guī)模的增大而急劇增加。

2 基于穩(wěn)定匹配的資源分配

2.1 匹配理論

匹配理論是一種能夠有效解決資源分配問題的方法,可以減小組合優(yōu)化問題的復(fù)雜度,使問題更好求解[13]。匹配理論通常用于建模2個獨立集合間的分配問題,且在這2個集合中,一方集合中個體對另一方集合中個體存在。這種偏好關(guān)系反映了一方集合中個體在選擇對方集合中個體時的選擇順序[13]。

2.2 穩(wěn)定靜態(tài)匹配算法

(2)

C3:xdi,j={0,1}

定義1匹配μ定義為一個多值映射,即D∪R→D∪R,?di∈D,?j∈R,當且僅當滿足下列條件時:

1)(di,j)∈μ;

2)|μ(di)|≤1,?di∈D;

3)當且僅當di∈μ(j)時,μ(di)=j。

(3)

定義2對于多對一匹配,如果滿足下列情況,稱主體對(di,j)為阻礙穩(wěn)定對:

定義3當一個匹配中不存在阻礙穩(wěn)定對時,稱該匹配為穩(wěn)定匹配。

為了求出穩(wěn)定匹配,可利用遞延匹配算法[14]對其求解,算法略。

2.3 具有動態(tài)配額的穩(wěn)定匹配

定義4匹配μ定義為一個多值映射:D∪R→D∪R,?di∈D,?j∈R,當且僅當滿足下列條件時:

1)(di,j)∈μ;

2)|μ(di)|≤1,?di∈D;

3)|μ(j)|≤qj,?j∈R,且|μ(j)|∈D∪?,其中qj是RBj的配額;

4)當且僅當di∈μ(j)時,μ(di)=j。

對于DUE來說,DUE更加傾向于復(fù)用使得自身擁有更大速率的RB。而對于RB來說,由于每個RB提前已經(jīng)分配給各個CUE,RB更傾向于分配給對CUE造成干擾更小的DUE。所以,DUE的偏好序和RB的偏好序根據(jù)如下偏好度函數(shù)建立:

(4)

(5)

定義5對于多對一匹配,如果滿足下列情況,稱主體對(di,j)為阻礙穩(wěn)定對:

對于所建立的多對一匹配模型,目標是尋找一個穩(wěn)定匹配,而不是一個最優(yōu)解,即以較低的計算復(fù)雜度來找到盡量使得個體滿意的資源分配方式。

改進型Gale-Shapley匹配算法具體步驟如下:

步驟1根據(jù)式(4)、式(5)計算Udi(j)、Uj(di),?di,j,建立偏好矩陣P。

步驟3whiledum≠?,且其偏好列表非空。

步驟4fordi∈dum

j是在di偏好列表中偏好序較高的RB,將j從di偏好列表中刪除;

else

找出目前匹配RBj的所有di',且di?jdi',記作集合dle;

end while

else

end if

end if

end for

end while

2.4 算法穩(wěn)定性、復(fù)雜度分析

對于所提改進遞延匹配算法,從穩(wěn)定性、優(yōu)化性能和復(fù)雜度對算法進行分析。

定理1改進遞延匹配算法的解是穩(wěn)定的。

定理2改進遞延匹配算法的復(fù)雜度是ο(M×R)。

證明:由于每個DUE最多向R個RB提出用頻申請,M個DUE最多提出M×R次用頻申請,因此時間復(fù)雜度為ο(M×R)。證畢。

3 仿真分析

仿真考慮一個D2D網(wǎng)絡(luò)部署在250 m×250 m的正方形區(qū)域內(nèi),RB、CUE數(shù)量都取3,DUE數(shù)量M在區(qū)間[1,10]內(nèi)動態(tài)變化。eNB的位置為正方形區(qū)域中心,CUE、DUE位置隨機生成。DUE收發(fā)機之間距離固定為20 m。eNB發(fā)射功率為46 dBm,DUE發(fā)射機發(fā)射功率為23 dBm,噪聲功率為-90 dBm,各RB帶寬為180 kHz。信道增益gT,R=10(-L(dT,R)/10),L(dT,R)為發(fā)射端與接收端的路徑損耗,假設(shè)L(dT,R)=15.3+37.6 lg(dT,R),dT,R為發(fā)射端與接收端的距離。gT,R可代表eNB到CUE之間或DUE收發(fā)機之間的信道增益。

為了對比算法性能,在不同干擾門限條件下將所提改進型Gale-Shapley匹配算法的求解結(jié)果和隨機匹配算法、靜態(tài)匹配算法做比較,仿真結(jié)果如圖2所示。從仿真曲線可以看出,本文所提動態(tài)配額匹配算法的分配結(jié)果的效用曲線和通過窮收得到的最優(yōu)結(jié)果效用曲線基本重合,接近最優(yōu)解。本文所提算法相對于靜態(tài)匹配算法能夠得到更好的性能。隨著干擾門限的增大,系統(tǒng)對CUE的保護性越弱,這時干擾門限限制不再影響分配結(jié)果,3種算法在高干擾門限時,分配效用具有相同的趨勢。

圖2 算法優(yōu)化性能分析

圖3為本文所提算法在RB總數(shù)為6,網(wǎng)絡(luò)DUE總數(shù)分別為5、10、15、20、25、30的情況下,干擾門限和改進型Gale-Shapley匹配算法中的平均申請總數(shù)的關(guān)系。

圖3 算法收斂性能分析

從圖3可以看出,在DEU總數(shù)固定的情況下,隨著干擾門限的增加,算法平均申請總數(shù)呈遞減趨勢,在干擾門限為-85 dBm～-60 dBm時下降最明顯。因為在干擾門限很低的情況下,每次DUE提出申請時都被拒絕,這時理論上申請次數(shù)應(yīng)該為M×R,其中每個DUE共申請R次。隨著干擾門限增加,DUE逐漸被接受,這時每個DUE申請次數(shù)少于R次,總申請次數(shù)逐漸減少,當干擾門限大到對每個DUE直接接入其認為最好的RB,申請次數(shù)為M,即圖中最后平均申請次數(shù)趨于不變。綜上,算法時間復(fù)雜度為ο(M×R)。

在RB總數(shù)為6、干擾門限為-75 dBm、DUE總數(shù)為20的情況下,每個DUE申請次數(shù)如圖4所示。

圖4 各DNE的申請次數(shù)對比

從圖4可以看出,d7申請次數(shù)為1,d2、d3、d4、d6、d11、d18申請次數(shù)為2,d16申請次數(shù)為3,d17申請次數(shù)為4,其余申請次數(shù)的用戶最大申請數(shù)為6。從改進遞延匹配算法可以看出,DUE申請次數(shù)和自身對CUE造成的干擾有關(guān),對CUE造成的干擾大,被RB拒絕的次數(shù)越多。d7申請次數(shù)最小,是因為d7對其接入RB的干擾小,使得d7優(yōu)先被接受,而申請次數(shù)為6的DUE對其所申請RB的干擾大被優(yōu)先拒絕,最大拒絕次數(shù)為6。對于RB來說,CUE希望將自己的RB分配給對其干擾較小的DUE復(fù)用,從而保證了自身的服務(wù)質(zhì)量。

4 結(jié)束語

本文針對分層D2D網(wǎng)絡(luò),分析研究了在保護CUE服務(wù)質(zhì)量情況下的RB分配問題。將問題建模為具有動態(tài)配額的多對一雙邊匹配,提出了一種改進遞延匹配算法,分別根據(jù)接入RB的可達速率和DUE接入RB對CUE造成的干擾來建立偏好列表,DUE和RB通過不斷申請和拒絕最終找到資源分配方案。仿真結(jié)果表明,所提算法接近于最優(yōu)分配方案,比靜態(tài)匹配算法性能更優(yōu),同時降低了計算復(fù)雜度,有利于實際系統(tǒng)的部署。

[1] 焦 巖,高月紅,楊鴻文,等.D2D技術(shù)研究現(xiàn)狀及發(fā)展前景[J].電信工程技術(shù)與標準化,2014(6):83-87.

[2] BOCCARDI F,HEATH R W,LOZANO A,et al.Five disruptive technology directions for 5G[J].IEEE Communications Magazine,2014,52(2):74-80.

[3] 王俊義,鞏志帥,符杰林,等.D2D通信技術(shù)綜述[J].桂林電子科技大學學報,2014,34(2):114-119.

[4] ASADI A,WANG Qing,MANCUSO V.A survey on device-to-device communication in cellular networks[J].IEEE Communications Surveys & Tutorials,2014,16(4):1801-1819.

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

[6] 王俊濤,李 慧,卜智勇.一種基于比例公平的啟發(fā)式D2D資源分配方案[J].計算機工程,2017,43(12):78-82.

[7] 程永生,董宇涵,張學聃,等.多小區(qū)CDMA系統(tǒng)D2D通信上行性能研究[J].計算機工程,2013,39(7):11-15.

[8] 郜偉偉,易輝躍,胡艷軍,等.D2D通信中基于信噪比均衡的資源分配算法[J].計算機工程,2012,38(10):5-8.

[9] LEI Lei,ZHONG Zhangdui,LIN Chuang,et al.Operator controlled device-to-device communications in LTE-advanced networks[J].IEEE Wireless Communications,2012,19(3):96-104.

[10] XU Chen,SONG Lingyang,HAN Zhu,et al.Efficiency resource allocation for device-to-device underlay communication systems:a reverse iterative combinatorial auction based approach[J].IEEE Journal on Selected Areas in Communications,2013,31(9):348-358.

[11] HASAN M,HOSSAIN E.Distributed resource allocation for relay-aided device-to-device communication under channel uncertainties:a stable matching approach[J].IEEE Transactions on Communications,2015,63(10):3882-3897.

[12] MANLOVED F.Algorithmics of matching under preferences[M].[S.l.]:World Scientific Pub.Co.,2013.

[13] 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.

[14] GALE D,SHAPLEY L S.College admissions and stability of marriage[J].American Mathematical Monthly,2013,69(5):9-15.

[15] GUSFIELD D,IRVINGR W.The stable marriage problem:structure and algorithms[M].Cambridge,USA:MIT Press,1989.