D2D網(wǎng)絡(luò)中具有動(dòng)態(tài)配額的資源分配算法

,,,

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

0 概述

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

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

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

圖1 系統(tǒng)模型

(1)

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

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

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

2.1 匹配理論

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

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

(2)

C3:xdi,j={0,1}

定義1匹配μ定義為一個(gè)多值映射,即D∪R→D∪R,?di∈D,?j∈R,當(dāng)且僅當(dāng)滿(mǎn)足下列條件時(shí):

1)(di,j)∈μ;

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

3)當(dāng)且僅當(dāng)di∈μ(j)時(shí),μ(di)=j。

(3)

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

定義3當(dāng)一個(gè)匹配中不存在阻礙穩(wěn)定對(duì)時(shí),稱(chēng)該匹配為穩(wěn)定匹配。

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

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

定義4匹配μ定義為一個(gè)多值映射:D∪R→D∪R,?di∈D,?j∈R,當(dāng)且僅當(dāng)滿(mǎn)足下列條件時(shí):

1)(di,j)∈μ;

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

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

4)當(dāng)且僅當(dāng)di∈μ(j)時(shí),μ(di)=j。

對(duì)于DUE來(lái)說(shuō),DUE更加傾向于復(fù)用使得自身?yè)碛懈笏俾实腞B。而對(duì)于RB來(lái)說(shuō),由于每個(gè)RB提前已經(jīng)分配給各個(gè)CUE,RB更傾向于分配給對(duì)CUE造成干擾更小的DUE。所以,DUE的偏好序和RB的偏好序根據(jù)如下偏好度函數(shù)建立:

(4)

(5)

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

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

改進(jìn)型Gale-Shapley匹配算法具體步驟如下:

步驟1根據(jù)式(4)、式(5)計(jì)算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ù)雜度分析

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

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

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

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

3 仿真分析

仿真考慮一個(gè)D2D網(wǎng)絡(luò)部署在250 m×250 m的正方形區(qū)域內(nèi),RB、CUE數(shù)量都取3,DUE數(shù)量M在區(qū)間[1,10]內(nèi)動(dòng)態(tài)變化。eNB的位置為正方形區(qū)域中心,CUE、DUE位置隨機(jī)生成。DUE收發(fā)機(jī)之間距離固定為20 m。eNB發(fā)射功率為46 dBm,DUE發(fā)射機(jī)發(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ā)機(jī)之間的信道增益。

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

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

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

圖3 算法收斂性能分析

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

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

圖4 各DNE的申請(qǐng)次數(shù)對(duì)比

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

4 結(jié)束語(yǔ)

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

[1] 焦 巖,高月紅,楊鴻文,等.D2D技術(shù)研究現(xiàn)狀及發(fā)展前景[J].電信工程技術(shù)與標(biāo)準(zhǔn)化,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].桂林電子科技大學(xué)學(xué)報(bào),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].計(jì)算機(jī)工程,2017,43(12):78-82.

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

[8] 郜偉偉,易輝躍,胡艷軍,等.D2D通信中基于信噪比均衡的資源分配算法[J].計(jì)算機(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.