移動中繼協助下終端直通中的模式選擇和資源分配方案

朱正倉,趙季紅,唐睿,曲樺,王璐瑤,曹照鑫

(西安交通大學電子與信息工程學院,710049,西安)

?

移動中繼協助下終端直通中的模式選擇和資源分配方案

朱正倉,趙季紅,唐睿,曲樺,王璐瑤,曹照鑫

(西安交通大學電子與信息工程學院,710049,西安)

針對移動中繼(MR)協助下終端直通(D2D)鏈路與傳統(tǒng)蜂窩鏈路之間的同頻干擾問題,在MR是、否可被多條D2D鏈路復用的條件下,分別提出了2種聯合模式選擇和資源分配減小系統(tǒng)干擾的方案。在MR可被多條D2D鏈路復用的方案(方案1)中,通過干擾模型構建的優(yōu)化問題等價于二分圖中的最大匹配問題,繼而可以借助匈牙利算法在多項式時間內得到最優(yōu)解;在MR不可被多條D2D鏈路復用方案(方案2)中,通過干擾模型構建的優(yōu)化問題等價于三維匹配問題,一般意義下屬于NP-hard難題,因此設計了一種具有多項式復雜度的方案。仿真結果表明,方案1可得到理論最優(yōu)解,其D2D鏈路總中斷概率比貪婪方案降低了29.94%;方案2的D2D鏈路總中斷概率比貪婪方案降低了23.67%,相比于最優(yōu)值,僅僅損失了8.16%的性能,有效地實現了性能與復雜度之間的折中。

終端直通;移動中繼;模式選擇;資源分配

終端直通(device-to-device,D2D)通信容許鄰近通信對間直接建立數據鏈路[1-2],無需基站轉發(fā)數據,減輕了基站負擔,降低了時延,已成為未來5G網絡的重大課題[3]。然而,5G采用頻譜已上升至30～300 GHz,無線信號繞過障礙物和穿透建筑物的能力變弱,致使遠距離路徑損耗嚴重,導致5G網絡下D2D通信的可靠通信距離變短[4],同時,為提升小區(qū)頻譜利用率,D2D用戶復用已有蜂窩用戶的頻帶資源,會產生嚴重的同頻干擾問題。針對D2D用戶的遠距離可靠通信問題,文獻[5]采用固定中繼,以增強D2D鏈路間的信號質量,但固定中繼需安裝中繼設備,增大了設備的投入費用;文獻[6-7]將空閑的移動設備作為中繼,即移動中繼(mobile relays,MR),相比于固定中繼,移動中繼的選擇增益和頻譜復用增益能更有效地提升D2D鏈路的通信質量?；诖?本文借助移動中繼協助D2D通信。

針對D2D鏈路用戶復用蜂窩用戶資源時會產生同頻干擾的問題[8],如何設計有效的模式選擇和無線資源分配方案以減小系統(tǒng)干擾引起了國內外學者的廣泛探討[5-7,9-14]。文獻[5-6]借助資源分配降低D2D用戶和蜂窩用戶間干擾,分別優(yōu)化系統(tǒng)吞吐量和能耗,但此系統(tǒng)只存在單一的中繼模式,忽略了D2D通信的直通模式。考慮到文獻[5-6]的不足,文獻[7]通過聯合模式選擇和中繼選擇優(yōu)化系統(tǒng)吞吐量,但未考慮信道資源分配,忽略了中繼和信道的多維無線資源的聯合優(yōu)化。為此,文獻[9-14]聯合優(yōu)化多維無線資源,但難以同時兼顧高算法性能和低算法時間復雜度的要求。首先,從算法性能上看,文獻[9-10]借助貪婪算法求解問題,算法復雜度低,但算法性能難以保證;文獻[11]通過啟發(fā)式算法求解問題,無法保證最優(yōu)解;文獻[12]將目標問題的三維變量分別固定其中二維變量后利用匈牙利算法不斷迭代求解,但易陷入局部最優(yōu),算法性能無法保證。其次,從算法時間復雜度上看,文獻[13]以提升的窮舉搜索方式求最優(yōu)解,但算法時間復雜度高;文獻[14]將四維優(yōu)化問題固定其中三維變量轉化為二維優(yōu)化問題求最優(yōu)解,但以遍歷方式固定三維變量,算法復雜度高。

綜上,針對MR是否可被多條D2D鏈路復用的不同場景,本文聯合模式選擇和資源分配分別提出2種減小系統(tǒng)干擾的方案。在中繼可被復用場景中,該方案將構建的干擾模型公式化為四維優(yōu)化問題,并將其轉化為圖論中的二維匹配問題,該二維優(yōu)化問題可借助匈牙利算法求解,從而提出性能最優(yōu)的方案1;在中繼不可被復用場景中,該方案將構建的干擾模型同樣公式化為四維優(yōu)化問題,其可轉化為三維優(yōu)化問題,以此提出解決方案2,且方案2的性能接近最優(yōu)的遍歷方案。

1 系統(tǒng)模型

本文考慮單小區(qū)場景,假定小區(qū)間同頻干擾已得到很好的抑制[1]。系統(tǒng)干擾模型如圖1所示,小區(qū)內包含一個宏基站(macro base station,MBS),N個蜂窩用戶(CN),M個D2D通信對(包括一個發(fā)送端DT和一個接收端DR)和L個空閑的移動中繼用戶(R),其中,移動中繼采用放大發(fā)送(amplify-and-forward,AF)中繼方式。本文考慮D2D通信復用蜂窩通信上行頻帶資源的情況,且蜂窩通信處于滿負荷,即信道數為N。將蜂窩用戶與MBS之間的鏈路稱為蜂窩鏈路(cellular link,CL)。將DT和DR間的鏈路(包括直通模式下的單條鏈路和移動中繼協助模式下的2跳鏈路)稱為D2D鏈路(D2D link,DL)。

圖1 系統(tǒng)干擾模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

2 問題構建和解決方案

為減小D2D用戶和MR用戶復用蜂窩用戶資源產生的干擾問題,聯合模式選擇和資源分配降低系統(tǒng)干擾,減小D2D鏈路總中斷概率,提升D2D鏈路的可靠性,其優(yōu)化過程分2個部分:首先,分析任意D2D鏈路在不同模式下的中斷概率;其次,設計模式選擇和資源分配方案。

2.1 D2D鏈路的中斷概率

本文分別考慮D2D通信的直通和中繼2種通信模式,需分析2種模式下D2D鏈路中斷概率公式,以構建問題模型,見定理1。

定理1 直通模式下,D2D鏈路的中斷概率為

(8)

中繼模式下,D2D鏈路的中斷概率為

(9)

證明 可詳見附錄A。

2.2 聯合模式選擇和資源分配

中繼模式下,根據用戶偏好,用戶可設定中繼是、否可被復用的2種場景。

2.2.1 中繼可復用 本文聯合模式選擇和資源分配優(yōu)化系統(tǒng)干擾,最小化D2D鏈路的總中斷概率,其中,資源分配包括信道分配和中繼選擇,可將其干擾模型公式化為式(10)的優(yōu)化問題(問題1)

(10)

問題1(式(10))為四維優(yōu)化問題,若直接求解則其算法復雜度高,可簡化問題1,見定理2。

定理2 中繼可復用時,問題1等價于二分圖的最大匹配問題。

證明 在問題1中,可將直通模式的D2D接收端看作特殊的中繼,即將模式選擇與中繼選擇合并,其原理如圖2所示,若D2D對在任意信道下選定中繼節(jié)點L+1,則表示D2D對用戶選擇直通模式通信,否則,選擇中繼模式通信。

圖2 中繼可復用時模式選擇與中繼選擇合并示意圖

例如圖2中,D2D對1選擇信道2和中繼L+1以直通模式通信,D2D對3選擇信道1和中繼2以中繼模式通信,因此,問題1可轉化為如下的三維優(yōu)化問題(問題2)

(11)

式(11)的目標函數中:二元變量yi,j,r∈{0,1},yi,j,r=1表示D2D對j通過中繼r以信道i通信,否則yi,j,r=0;當1≤r≤L時,Wi,j,r=Ui,j,r,1,當r=L+1時,Wi,j,r=Ui,j,r,2;目標函數的2個限制條件類似問題1中的限制條件,同樣表示單個信道只能被單個D2D對和MR復用及單個D2D對只能使用單個信道和中繼。

問題2(式(11))將問題1降為三維優(yōu)化問題,根據中繼可被復用條件與問題2的2個限制條件可進一步將問題2轉化為二維優(yōu)化問題,其過程如下式所示

(12)

式中:Mi,j=min{Wi,j,1,Wi,j,2,…,Wi,j,L+1},?i,j;二元變量zi,j∈{0,1},其中zi,j=1表示D2D鏈路j通過中繼r*在信道i通信,否則zi,j=0;步驟(a)的物理意義在于:在任意確定的信道i和D2D對j的情況下,選擇D2D對j復用信道i時,使D2D鏈路中斷概率最小的中繼r*。根據式(12)可將問題2進一步轉化為如下的問題(問題3)

(13)

綜上,問題1可轉化為問題3(式(13)),問題3易證明其等價于二分圖的最大匹配問題[14],此處從略。因此,為求解問題3,可構建圖論問題模型,借助匈牙利算法求解問題3中(i,j)間的最優(yōu)匹配值zi,j,并可將二維優(yōu)化變量zi,j還原為問題1的4維優(yōu)化變量xi,j,r,q,證明結束。

本文根據定理2設計性能最優(yōu)的方案1,其算法復雜度為O(J3+MN(L+1)),J=max(M,N)。方案1的詳細步驟如下:

步驟1 設定M,N,L值,初始化矩陣W=[Wi,j,r]N×M×(L+1);

步驟2 構建二分圖G=(V∪S,E),其中,集合V={j|1≤j≤M}表示D2D對的集合,集合S={i|1≤i≤N}表示可復用信道的集合,E為集合V與S中元素j和i的連接邊,邊的權值為Mi,j;

步驟3 借助匈牙利算法求解矩陣M=[Mi,j]N×M的二維最優(yōu)匹配矩陣Z=[zi,j]N×M;

步驟4 ?i,j,當zi,j=1時,搜索Mi,j=Wi,j,r的任一r*,若1≤r*≤L,則q=1且xi,j,r,q=1,若r*=L+1,則q=2且xi,j,r,q=1,否則xi,j,r,q=0,確定問題1的最優(yōu)解xi,j,r,q。

2.2.2 中繼不可復用 中繼不可復用時,類似于構建式(10)的問題1,根據干擾模型,將其公式化為式(14)的優(yōu)化問題(問題4)

(14)

問題4(式(14))類似于問題1,因為中繼不可復用,問題4比問題1增加了一個限制條件(問題4的第3個限制條件),表示單個中繼只能復用單個信道并協助單個D2D鏈路通信。

問題4為四維優(yōu)化問題,可轉化為三維優(yōu)化問題,具體見定理3。

定理3 中繼不可復用時,四維優(yōu)化問題4等價于式(15)表示的三維優(yōu)化問題5。

證明 在問題4中,合并模式選擇與中繼選擇時,因中繼不可復用,中繼的維度需增加至L+M,以確保所有D2D對的直通模式可被選擇,其示例過程如圖3所示,L+1到L+M代表D2D用戶以直通模式通信,圖中D2D對2選擇信道3以直通模式通信,因此問題4等價于式(15)的優(yōu)化問題(問題5)

(15)

式中:1≤r≤L時,Ki,j,r=Ui,j,r,1;L+1≤r≤L+M時,Ki,j,r=Ui,j,r,2。證明結束。

圖3 中繼不可復用時模式選擇與中繼選擇合并示意圖

中繼不可復用時,優(yōu)化問題5(式(15))不滿足式(8)中步驟(a)的轉化條件,而且問題5為NP-難問題[14],算法設計的挑戰(zhàn)在于找到一個逼近最優(yōu)值的低復雜度算法。因此基于方案1,本文提出方案2,其復雜度為O(tJ3+MN(L+M))(t為被復用的中繼個數,1≤t≤J)。

方案2的思路如下:首先設定包含(i,j,r)這3類元素的集合F,F表示所有未匹配的信道i,D2D對j和中繼r;其次,先忽略問題5中的第3個限制條件,此時問題5等價于問題3,可借助方案1求出問題5的最優(yōu)解,根據最優(yōu)解重新考慮問題5中的第3個限制條件,其中,先篩選出最優(yōu)解中被復用的中繼集合,搜索中繼集合中對應最小中斷概率的D2D對和信道,將此D2D對,中繼和對應信道記錄并從集合F中除去;最后,根據更新后的集合F,重新循環(huán)使用方案1,直至無中繼被復用時終止。

根據方案2的思路,其詳細步驟如下:

步驟1 初始化矩陣K=[Ki,j,r]N×M×(L+M),構建集合F={(i,j,r)|1≤i≤N,1≤j≤M,1≤r≤L+M},k=0,F表示未匹配的D2D對,中繼和信道的集合;

步驟2 構建二分圖G=(V∪S,E),其中,集合V={j|1≤j≤M-k,j∈F}表示未匹配的D2D對集合,集合S={i|1≤i≤N-k,i∈F}表示未復用的信道集合,E為集合V與S中j和i的邊,其權值Oi,j=min{Ki,j,1,Ki,j,2,…,Ki,j,L+M},?i,j;

步驟3 借助匈牙利算法求矩陣O=[Oi,j]N×M的二維最優(yōu)匹配矩陣Z=[zi,j]N×M;

步驟4 對?i,j∈F,當zi,j=1時,搜索Oi,j=Ki,j,r中Ki,j,r的全部r(r∈F),令ti,j,r=1,否則ti,j,r=0,繼而確定三維矩陣T=[ti,j,r]N×M×(L+M)值;

3 仿真結果與分析

假定仿真的蜂窩小區(qū)是半徑為500 m的圓形小區(qū),設定N=10,M=4,L=8,用戶的最大發(fā)射功率Pmax=126 mW,基站和用戶接收端的噪聲分別為5 dB和9 dB,信道帶寬為180 kHz,用戶接收端的高斯噪聲功率譜密度10-17.4mW/Hz,信道衰落服從瑞利衰落,且信道間相互獨立同分布,信道的路徑衰落常數β=102,路徑損失系數α=4。

仿真設定的參考算法:①無中繼方案[1],即D2D對間以直通模式通信,不考慮中繼模式;②貪婪方案[9-10],即以貪婪原則進行聯合模式選擇和資源分配減小系統(tǒng)干擾的方案;③最優(yōu)方案1[14],即中繼可復用時,聯合模式選擇和資源分配減小系統(tǒng)干擾的最優(yōu)方案;④最優(yōu)方案2[12],即中繼不可復用時,聯合模式選擇和資源分配減小系統(tǒng)干擾的最優(yōu)方案。

針對中繼是否可被復用,仿真分為以下2部分。

(1)在中繼可被復用、中繼數為6～20時,比較了本文方案1與3種參考方案的D2D鏈路總中斷概率,結果如圖4所示。由圖4可見,本文方案1為聯合優(yōu)化的最優(yōu)方案,性能優(yōu)于文獻[1]的直通模式方案和貪婪方案。其中,文獻[1]方案中,中繼不參與通信過程,故隨著中繼數目的增加其曲線不變,且本文方案1比其性能提升了72.23%。文獻[14]方案與本文方案1同為最優(yōu)方案,故2種方案曲線重合,但本文方案1的算法復雜度遠低于文獻[14]方案的算法復雜度(O(J3+MN(L+1))

圖4 中繼可復用時總中斷概率與中繼數的關系

圖5 中繼不可復用時總中斷概率與中繼數的關系

(2)在中繼不可被復用、中繼數為6～20時,比較本文方案2與3種參考方案的D2D鏈路總中斷概率,結果如圖5所示。由圖5可見,本文方案2的性能優(yōu)于文獻[1]的直通模式方案和貪婪方案,而單純考慮直通模式的文獻[1]方案與中繼無關,其曲線同樣不會隨著中繼數變化,但考慮中繼的本文方案2比文獻[1]方案的性能提升了78.34%。本文方案2的性能接近文獻[12]的最優(yōu)方案,僅損失了8.16%,但本文方案2的時間復雜度O(t(J3+MN(L+M)))卻遠小于文獻[12]的方案的時間復雜度O(J3HM,N),其中HM,N=max(M,N)!/[(max(M,N)-min(M,N))!]。

4 結 論

本文聯合模式選擇、資源分配以減小系統(tǒng)干擾,提升D2D鏈路性能,針對中繼是否可被復用的場景分別提出本文方案1和本文方案2。本文方案1和文獻[14]方案同為性能最優(yōu)的方案,但本文方案1具有更低的時間復雜度(O(J3+MN(L+1))

[1] 楊陽, 廖學文, 高貞貞, 等. 多小區(qū)終端直通異構網絡中利用圖論的資源分配方案 [J]. 西安交通大學學報, 2014, 48(10): 22-28. YANG Yang, LIAO Xuewen, GAO Zhenzhen, et al. A resource allocation scheme using graph theory for D2D communication in multi-cell heterogeneous cellular network [J]. Journal of Xi’an Jiaotong University, 2014, 48(10): 22-28.

[2] 王元, 趙季紅, 唐睿, 等. D2D多播場景下面向節(jié)能的資源分配機制 [J]. 西安電子科技大學學報, 2016, 43(2): 173-178. WANG Yuan, ZHAO Jihong, TANG Rui, et al. Energy aware resource allocation for underlaid D2D multicast [J]. Journal of Xidian University, 2016, 43(2): 173-178.

[3] YILMAZ O N C, LI Zexian, VALKEALAHTI K, et al. Smart mobility management for D2D communications in 5G networks [C]∥Proceedings of 2014 IEEE Wireless Communications and Networking Conference Workshops. Piscataway, NJ, USA: IEEE, 2014: 219-223.

[4] QIAO Jian, SHEN Xuemin, MARK J, et al. Enabling device-to-device communications in millimeter-wave 5G cellular networks [J]. IEEE Communications Magazine, 2015, 53(1): 209-215.

[5] HASAN M, HOSSAIN E, KIM D I. Resource allocation under channel uncertainties for relay-aided Device-to-Device communication underlaying LTE-A cellular networks [J]. IEEE Transactions on Wireless Communication, 2014, 13(4): 2322-2338.

[6] MA Xiran, YIN Rui, YU Guanding, et al. A distributed relay selection method for relay assisted device-to-device communication system [C]∥Proceedings of IEEE International Symposium on Personal Indoor and Mobile Radio Communication. Piscataway, NJ, USA: IEEE, 2012: 1020-1024.

[7] CHITHRA R, ROBERT B, SARAT K P. Hungarian method based joint transmission mode and relay selection in device-to-device communication [C]∥Proceedings of 2015 8th IFIP Wireless and Mobile Networking Conference. Piscataway, NJ, USA: IEEE, 2015: 261-268.

[8] 孫黎, 徐洪斌. 協作式終端直通系統(tǒng)中星座旋轉輔助的干擾避免策略 [J]. 西安交通大學學報, 2015, 49(12): 6-11. SUN Li, XU Hongbin. A scheme to avoid interference via constellation rotation for cooperative device to device systems [J]. Journal of Xi’an Jiaotong University, 2015, 49(12): 6-11.

[9] ZHAO W, WANG S. Resource sharing scheme for Device-to-Device communication underlaying cellular networks [J]. IEEE Transactions on Communication, 2015, 63(12): 4838-4848.

[10]LI G Q, LIU H. Resource allocation for OFDMA relay networks with fairness constraints [J]. IEEE Journal on Selected Areas in Communications, 2006, 24(11): 2061-2069.

[11]JIA Juncheng, ZHANG Jin, ZHANG Qian. Cooperative relay for cognitive radio networks [C]∥Proceedings of IEEE INFOCOM. Piscataway, NJ, USA: IEEE, 2009: 2304-2312.

[12]KIM T, DONG Miaomiao. An iterative Hungarian method to joint relay selection and resource allocation for D2D communications [J]. IEEE Wireless Communications Letters, 2014, 3(6): 2162-2337.

[13]LU Zaixin, SHI Yan, WU Weili, et al. Efficient data retrieval scheduling for multi-channel wireless data broadcast [C]∥Proceedings of IEEE INFOCOM. Piscataway, NJ, USA: IEEE, 2012: 891-899.

[14]CHEN Hao, REN Pinyi, SUN Li, et al. A joint optimization of transmission mode selection and allocation for cognitive relay networks [C]∥Proceedings of IEEE International Conference on Communication. Piscataway, NJ, USA: IEEE, 2013: 2852-2856.

附錄A

直通模式和中繼模式D2D鏈路中斷概率分析如下。

(1)直通模式:直通模式的D2D鏈路信干噪比為

(A1)

(A2)

Y的概率密度函數為

(A3)

令Z=X/Y,此時Z的概率密度函數為

(A4)

直通模式的D2D鏈路中斷概率表達式為

(A5)

根據式(A4)、(A5)分析直通模式的D2D鏈路中斷概率,可見正文式(8)。

(2)中繼模式:根據式(7)推導中繼模式D2D鏈路中斷概率

(A8)

將式(A7)、(A8)代入式(A6),分析中繼模式的D2D鏈路中斷概率,見式(9)。

(編輯 劉楊)

Two Mode Selection and Resource Allocation Schedules for Device-to-Device Communication with Mobile Relay Assistance

ZHU Zhengcang,ZHAO Jihong,TANG Rui,QU Hua,WANG Luyao,CAO Zhaoxin

(School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

The joint allocation of transmission mode and resource is considered, and two mechanisms are proposed to address the problem of the severe mutual interference between mobile relay (MR) assisted device-to-device (D2D) communication and the existing cellular communication whether each MR can be reused by multiple D2D links. The problem model of interference is reduced into a bipartite matching problem in mechanism 1 when each MR can be reused by multiple D2D links, and the optimal solution of the problem is obtained in polynomial-time by using Hungary algorithm. The problem model of interference turns out to be a three-dimensional matching problem in mechanism 2 when each MR cannot be reused by multiple D2D links. The problem generally is NP-hard, and a heuristic algorithm is proposed to get its approximate optimum in polynomial-time. The results show that the proposed mechanism 1 maintains the optimal performance and outweighs the greedy scheme by 29.94%, and mechanism 2 achieves a 23.67% gain compared with the greedy scheme, and that a comparison with the optimal algorithm shows the proposed schemes attain polynomial-time complexity with only 8.16% performance loss.

device-to-device communication; mobile relay; mode selection; resource allocation

2016-03-07。

朱正倉(1987—),男,碩士生;趙季紅(通信作者),女,教授,博士生導師。

國家自然科學基金資助項目(61372092);國家高技術研究發(fā)展計劃資助項目(2014AA01A706)。

時間:2016-07-21

http:∥www.cnki.net/kcms/detail/61.1069.T.20160721.2212.008.html

10.7652/xjtuxb201610017

TN914.3

A

0253-987X(2016)10-0111-07