基于公平性的D2D時隙調度算法

詹金珍，郭達偉，滑維鑫

(1.西北工業大學明德學院，西安 710124； 2.西北工業大學 自動化學院，西安 710129； 3.中國移動通信集團 陜西有限公司，西安 710074) (*通信作者電子郵箱guodaw@nwpu.edu.cn)

基于公平性的D2D時隙調度算法

詹金珍1，郭達偉2*，滑維鑫2,3

(1.西北工業大學明德學院，西安 710124； 2.西北工業大學 自動化學院，西安 710129； 3.中國移動通信集團 陜西有限公司，西安 710074) (*通信作者電子郵箱guodaw@nwpu.edu.cn)

針對設備到設備(D2D)通信資源分配中的時隙調度時延以及信道增益變化導致吞吐率下降的問題，提出了一種公平性時隙調度(FTDS)算法。首先,基于頻譜復用模式建立系統模型，并歸納為一組合優化問題;然后，在模型的次優求解中，FTDS算法將調度周期劃分為多個等長的時隙，根據優先級策略將D2D用戶分配至不同時隙調度，從而適應D2D用戶多于蜂窩用戶的應用場景;同時,為了權衡服務質量(QoS)與系統吞吐率的關系，構造一滿足性權值與傳輸速率相互制約，共同決定用戶調度優先級。仿真實驗中，FTDS算法相比TDS、RANDOM算法，吞吐率平均增幅分別達到11.09%和40.64%，且FTDS算法下D2D用戶被調度頻次累積分布更為集中；同時，相比TDS算法調度時延最大降低31.22%。仿真實驗表明，FTDS算法擁有更優的吞吐率性能、更公平的調度機制、更小的調度時延。

設備到設備；資源復用；時隙分配；滿足性權值；公平性調度

0 引言

設備到設備(Device to Device, D2D)直接通信被廣泛認為是蜂窩網絡前景技術之一[1-2]。在D2D通信中，鄰近移動終端間的通信數據不需要基站轉發，而是在基站的控制下，允許使用蜂窩網絡頻譜資源直接建立本地鏈路通信，由此減輕了基站中繼轉發的負載瓶頸，使得移動終端具有更小的傳輸延遲，更小的能量消耗[3]。在LTE(Long Term Evolution) Release 12版本中，3GPP已經啟動了鄰近服務(Proximity Service)的D2D通信標準化研究[4]，當前將應用場景分為公共安全和商業應用兩大類。公共安全指蜂窩網絡不能正常工作時，允許終端間脫網通信，而商業應用則關注廣播、社交網絡、媒體共享等內容業務，與其他Wifi、Bluetooth等本地通信技術不同的是，D2D使用授權網絡頻譜資源，擁有更高的系統吞吐率，更好的服務質量保障[5];同時,文獻[6]面向下一代5G通信網絡，對D2D設備發現、會話建立、資源分配等關鍵技術進行了綜述討論。

為了進一步節約蜂窩網絡資源，提高網絡頻譜效率，D2D通信允許使用資源復用的方式建立傳輸，使得蜂窩網絡在資源匱乏的情況下保證系統吞吐率。然而D2D用戶(D2D User, DU)與傳統蜂窩用戶(Cellular User, CU)在資源復用模式下會引入新的干擾問題[7]，因此如何復用分配資源以減輕D2D用戶對原蜂窩用戶的干擾影響是核心問題之一。

Ye等[8]依據位置信息及信道增益，動態確定每個蜂窩用戶可復用資源比例；Wen等[9]適應性選擇用戶傳輸模式，基于用戶服務需求以及干擾級別動態分配RB資源；而Xu等[10]以最大化D2D通信鏈路數為目標建立資源分配模型，同時加入信干噪比約束，均較好地抑制了D2D對原蜂窩用戶的強干擾影響。Kuruvatti等[11]依據用戶密度將蜂窩網絡覆蓋面劃分為多個虛擬扇區，并依據用戶信號到達角對用戶進行分組聚類，處于相互垂直的扇形區域用戶可復用相同RB(Resource Block)資源，由此減輕干擾效應，但定位的魯棒性將使實際性能產生偏差。Zhang等[12]面對分配模型高復雜度求解的問題，提出一種基于干擾感知圖的次優算法，權衡算法效率與性能之間的關系，然而干擾和最大并不意味系統吞吐率最大，頻譜效率可進一步優化。文獻[13]基于上行鏈路資源建立分配模型，提出了一個基于Barrier方法的算法來求解對偶問題，然而其計算與約束條件的個數、容忍誤差以及初始值等因素有關，具有多項式復雜度。D2D用戶間以競爭或合作的方式復用頻譜資源，因此可將資源分配描述為博弈過程，Huang等在文獻[14]中了討論不同博弈論模型的適用性，結論認為非合作博弈及拍賣框架更適用D2D資源分配。在此基礎上，Song等[15]將D2D與蜂窩用戶間的資源復用過程抽象為斯坦博格模型，蜂窩用戶通過出售所屬RB資源而獲得虛擬利益，D2D用戶依據最優響應策略，在給定價格下，迭代地選擇發射功率及RB資源，最終達到均衡收益狀態，然而各D2D用戶的博弈均衡將會犧牲系統吞吐率，造成頻譜效率降低。

現實環境中，往往存在D2D用戶多于蜂窩用戶的場景，如商場、體育場等，蜂窩用戶較少使得D2D用戶可復用資源匱乏，而資源分配的公平性將直接影響D2D用戶服務質量。常見的公平性分配策略是最大最小公平模型[16]，最早用于網絡流量控制，使資源的最小分配量盡可能最大化，防止任何網絡流被“餓死”，同時在一定程度上盡可能增加每個流的速率，以實現公平分配資源，但公平性會制約系統吞吐率的收益。為了權衡公平性和系統效率的關系，文獻[17]提出一種聯合資源分配算法，保證了用戶比例公平性下系統最大化吞吐率收益。在D2D通信模型中，Cai等[18]不僅允許一個D2D用戶可復用多個RB資源，而且任一RB資源均可被多個D2D用戶復用，同時提出一種次優的著色圖算法，較好地解決了資源匱乏問題。此外Chen等[19]運用了時隙調度思路，將基站調度周期劃分為等長時隙，然后將D2D用戶公平性分組調度在不同時隙，同樣解決了與RB需求與供給不平衡關系,但是文獻忽略了信道增益動態變化問題，影響系統吞吐率性能，同時算法中D2D用戶僅能被固定分配在單個時隙內，導致延遲問題。

在本文的研究中，考慮D2D用戶多于蜂窩用戶的應用場景，為了解決資源匱乏的公平性問題，同樣將一個調度周期劃分為多個等長的時隙。首先根據蜂窩與D2D用戶的資源復用關系，以最大化系統吞吐率為目標建立分配模型，并在模型中加入信干噪比、速率需求約束，將資源分配歸納為一個組合優化問題。在模型求解過程中，提出一種公平性時隙調度(Fairness Time Division Scheduling, FTDS)算法，算法中的D2D用戶在每個時隙均有被調度的機會;同時,為了權衡D2D用戶速率服務需求與系統吞吐率的公平性關系，構造滿足性權值因子與吞吐率增益因子互相制約，共同確定D2D用戶調度優先級。仿真實驗表明，FTDS算法在滿足D2D用戶服務質量需求下擁有更優的吞吐率性能，更小的調度時延。

1 系統模型

圖1中描述了覆蓋半徑為s的單蜂窩小區 的D2D通信系統。

定義1 蜂窩小區Z中存在M個蜂窩用戶CUi(i=1,2,…,M)。

CU與DU均勻分布在蜂窩小區內，包含兩種傳輸模式：基站eNodeB與CU的中繼通信(如圖1中CU1)，以及D2D之間的直接鏈路通信(如圖1中DU1)。整個系統采用基于正交頻分復用(Orthogonal Frequency Division Multiplexing, OFDM)的LTE通信方案，其最小資源調度單位為一RB(Resource Block),時域上包含7個OFDM符號，頻域上包含12個子載波。系統中DU通過復用CU下行鏈路RB資源的方式實現接入。資源復用模式將引入新的干擾問題。圖1中可見，在下行鏈路復用中，基站eNodeB將會對DU接收用戶DR產生干擾影響，而CU將會暴露在復用相同RB資源的DU發送用戶DT干擾下。本文考慮這樣一種應用場景，網絡中DU數N大于CU數M，且每個CU擁有單個RB資源，每個RB資源僅能被單個DU復用，從而抑制DU對CU過量干擾影響，同時一個DU可以復用多個CU的RB資源以滿足速率需求。為了有效減輕D2D用戶對原蜂窩用戶的干擾，在保證蜂窩用戶信干噪比前提下，進一步提升網絡的頻譜效率，選擇恰當的CU與DU資源復用組合尤為重要，為此首先建立以統吞吐率為最大化目標的資源分配模型。

圖1 D2D通信系統

(1)

(2)

(3)

(4)

定義3 定義一個M×N的資源復用分配矩陣β=[βi, j]M×N，表示CU與DU的資源復用關系。其中矩陣元素βi, j∈{0,1}為二進制變量，當βi, j=1時表示CUi與DUj復用相同RB資源，反之當βi, j=0時表示兩者未復用相同RB資源，由此可以推導出M個CU以及N個DU的吞吐率加Rc、Rd分別為：

(5)

(6)

同時整個系統吞吐率可以表示為Rc與Rd的加和：

(7)

因此資源復用的目標是求解這樣一個資源分配矩陣β=[βi, j]M×N，在約束條件下使得系統吞吐率性能達到最大：

(8)

(9)

(10)

(11)

(12)

上述約束條件式(9)表示任一RB資源上至多僅能被一個DU復用，約束條件式(10)表示DU必須滿足傳輸速率的服務質量(Quality of Service, QoS)需求，同時約束條件式(11)、(12)表示CU、DU需滿足的信干噪比閾值，減輕因資源復用而互相產生的干擾影響。

進一步分析上述模型可知，其為求解分配矩陣β=[βi, j]M×N的組合優化問題，在采用基站集中式計算中，復雜度呈現指數增長。為此提出一種公平性時隙調度(FTDS)算法，在滿足服務質量的前提下，尋找問題的近似解。

2 時隙調度算法

當DU數N多于CU數M時(N>M)，由于CU僅擁有單個RB資源，導致單次調度中DU可復用RB資源數無法滿足需求，為了適應上述應用場景，文獻[19]提出一種時隙調度(Time Division Scheduling, TDS)算法，如圖2所示。

圖2 時隙調度過程

TDS算法將一個調度周期劃分為s個等長的時隙，基站通過鏈路信息CSI檢測潛在的D2D通信，并將DU均衡分配至各時隙上調度，在每個時隙中，僅有被調度DU才能復用CU所屬RB資源建立通信鏈路。TDS算法的核心思路主要包括以下兩方面：

1)DU分組策略。將DU均衡地分配至每一個時隙上，每時隙上的DU數為N/s，同時采用離散準則，選擇距離和最大的DU進行組合。負載均衡下使得每時隙調度的DU數最小，因此保證更多的DU可以滿足其傳輸速率的服務質量需求，而離散準則避免DU對CU的干擾效應影響，提升系統吞吐率。

2)RB分配策略。在每時隙上的RB分配中，首先計算DU滿足速率所需最小RB數Nmin,然后選取其吞吐率增益最大的前Nmin個RB資源分配，進而最大化每時隙上的吞吐率性能。

上述分析可見，基于時隙調度的TDS算法較好地解決了當M小于N時的資源匱乏問題，但是文獻忽略了兩個問題的影響：

1)傳輸增益動態變化。傳輸增益的動態變化將導致DU在每時隙上的吞吐率收益不同。文獻中將DU固定分配，僅考慮單時隙上的速率最大化，而某DU在其他時隙上的速率收益因傳輸增益的影響可能會更優，因此系統吞吐率依舊存在提升空間。

2)調度時延。DU固定分組方案使得每個DU僅能在當前調度周期的某個時隙上調度，極端情況下當調度在第k-1個周期的T1時隙與第k個周期的Ts時隙時，最大相差達到兩個調度周期的長度，因此對實時性要求較高的業務存在服務質量劣勢。

針對文獻[19]存在的問題，在時隙調度算法TDS框架的基礎上，下文中提出改進型算法，將每時隙調度的候選集擴展為全DU集合，并引入滿足性加權因子，期望在進一步提升系統吞吐率的同時，保障各DU的服務質量。

3 公平性時隙調度算法

FTDS算法同樣將一個調度周期劃分為s個等長的時隙單元T1,T2,…,Ts,如圖2所示。

(13)

則在時隙Tt的RB分配過程表示如下：

(14)

進一步分析可知，式(14)的分配雖保證了系統吞吐率的最大化，但忽略了DU的服務質量，為此提出一種滿足性權值的約束，定義DUj在時隙Tt的滿足性權值ωi, j(t)如下：

(15)

(16)

(17)

4 仿真實驗與分析

仿真實驗使用Matlab平臺，采取蒙特卡羅方法，每次隨機生成3 000個不同分布樣本場景，在不同場景下分別進行資源調度分配，最后使用統計方法對性能結果取平均值。其仿真參數見表1。

表1 仿真參數設置

為了更好地體現本文中公平性時隙調度(FTDS)算法的性能優勢，將該算法與文獻[19]中時分調度(TDS)以及隨機調度(RANDOM)算法相比較，RANDOM算法同樣運用時分調度機制，而在每個時隙中隨機選取DU復用RB資源。在仿真實驗中對比中，選取了系統吞吐量、DU調度頻次、DU平均調度間隔，DU滿足率四個性能指標。其中系統吞吐量定義為：單位調度周期內CU與DU的總速率和；調度頻次定義為：單位調度周期內，DU被調度的次數；DU滿足率則定義為：已滿足速率需求的DU數與總DU數的比值。

圖3顯示了FTDS、TDS、RANDOM算法在不同CU數量下的系統吞吐率變化。伴隨著CU增多，每時隙內DU可復用的RB資源數增多，因此三個算法吞吐率均呈現遞增趨勢,同時得益于FTDS算法考慮到每個時隙傳輸增益的動態變化，將DU分配至吞吐率更優的時隙上調度,可以看到其吞吐率的性能優勢伴隨CU增多而逐漸凸顯，吞吐率平均增幅相比TDS及RANDOM算法，分別達到11.09%和40.64%。

圖3 吞吐率伴隨CU數量變化

用戶在資源分配中被調度的次數，能夠反映算法對各用戶資源請求的公平性滿足情況，為此在仿真實驗中，對每周期內DU調度頻次的累計分布進行統計分析。如圖4中所示，TDS相比FTDS、RANDOM算法擁有更廣泛的分布，用戶調度頻次分布在10～40次的范圍內，而FTDS與RANDOM算法中，多數分布于15～35次的區域內，調度頻次的分布比TDS較為集中。RANDOM算法因隨機選取DU調度，因此在實驗中體現出其公平性的本質，而FTDS算法中，加入公平性權值約束，調度頻次在實驗中表現出與RANDOM相似的集中分布，優于TDS算法。

圖4 DU調度頻次累積分布

圖5中以時隙為單位進一步分析了DU的平均調度間隔，顯然DU被調度的時隙間隔越小，用戶業務實時性保障越好。圖中FTDS、TDS、RANDOM三算法的DU調度間隔均伴隨著CU數的增多而減小，同時當CU密度較大時(M>50)，三算法的差異逐漸消失，這是由于CU增多導致RB增多，在每時隙內可調度更多的DU復用RB資源，DU在每時隙中被調度幾率更大。其中FTDS算法中滿足性權值發揮了重要作用，圖5中可見，平均調度間隔同樣優于TDS、RANDOM算法，在M=5處延遲降低最大31.2%，調度實時性較好。

圖5 DU調度間隔伴隨CU數量變化

圖6顯示了FTDS、TDS、RANDOM三算法的DU滿足率伴隨CU數量變化情況。

圖6 DU滿足率伴隨CU數量變化

當CU數處于15以上的密度時，此時每時隙內存在冗余RB資源，因此三算法調度下的DU滿足率均達到了100%，而在15以下的密度區域，TDS算法相比FTDS、RANDOM資源滿足率較好，是因為TDS將DU均勻分組，并固定分配在各時隙內，保證了各DU在每個周期內均有被調度的權利，但可以看到FTDS算法下的資源滿足率，相比TDS差異僅為2.1%，且伴隨CU的增多滿足率迅速提升至100%，同樣具有較好的滿足率性能。

5 結語

本文針對D2D資源分配提出了一種公平性時隙調度算法FTDS，該算法將DU分布在不同時隙調度，從而適應D2D用戶多于蜂窩用戶的應用場景;同時引入一滿足性權值，在資源分配中，依據用戶速率需求差異獎懲吞吐率收益，權衡服務質量與系統速率增益的關系。實驗結果表明，FTDS算法在滿足各用戶速率需求的基礎上擁有更優的吞吐率性能、更小的調度時延、更公平的調度機制;同時在FTDS算法中，時隙個數s取值將會對系統性能產生影響：s較大時，在一個調度周期內能夠容納更多的DU，但未被調度的DU將等待較長時間，尤其對于實時性較高的業務容易產生時延問題；反之當s較小時，每個時隙將涌入大量DU，導致服務質量下降;因此下一步的研究方向將詳細討論s的取值。

References)

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

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

[3] LIN X, ANDREWS J, GHOSH A, et al. An overview of 3GPP device-to-device proximity services [J]. IEEE Communications Magazine, 2014, 52(4): 40-48.

[4] ASTELY D, DAHLMAN E, FODOR G, et al. LTE release 12 and beyond [J]. IEEE Communications Magazine, 2013, 51(7): 154-160.

[5] CONDOLUCI M, MILITANO L, ORSINO A, et al. LTE-direct vs. WiFi-direct for machine-type communications over LTE-A systems [C]// Proceedings of the 2015 IEEE 26th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications. Piscataway, NJ: IEEE, 2015: 2298-2302.

[6] 錢志鴻,王雪.面向5G通信網的D2D技術綜述[J].通信學報,2016,37(7):1-14.(QIAN Z H, WANG X. Reviews of D2D technology for 5G communication networks [J]. Journal on Communications, 2016, 37(7): 1-14.)

[7] WEI L, HU R, QIAN Y, et al. Enable device-to-device communications underlaying cellular networks: challenges and research aspects [J]. IEEE Communications Magazine, 2014, 52(6): 90-96.

[8] YE Q, AL-SHALASH M, CARAMANIS C, et al. Resource optimization in device-to-device cellular systems using time-frequency hopping [J]. IEEE Transactions on Wireless Communications, 2014, 13(10): 5467-5480.

[9] WEN S, ZHU X, ZHANG X, et al. QoS-aware mode selection and resource allocation scheme for Device-to-Device (D2D) communication in cellular networks [C]// Proceedings of the 2013 IEEE International Conference on Communications Workshops. Piscataway, NJ: IEEE, 2013: 101-105.

[10] XU Y, YIN R, HAN T, et al. Dynamic resource allocation for device-to-device communication underlaying cellular networks [J]. International Journal of Communication Systems, 2014, 27(10): 2408-2425.

[11] KURUVATTI N P, KLEIN A, JI L, et al. Robustness of location based D2D resource allocation against positioning errors [C]// Proceedings of the 2015 IEEE 81st Vehicular Technology Conference. Piscataway, NJ: IEEE, 2015: 1-6.

[12] ZHANG R, CHENG X, YANG L, et al. Interference-aware graph based resource sharing for device-to-device communications underlaying cellular networks [C]// Proceedings of the 2013 IEEE Wireless Communications and Networking Conference. Piscataway, NJ: IEEE, 2013: 140-145.

[13] 程永生,朱江,林孝康.引入D2D通信的蜂窩網上行資源分配算法[J].電子與信息學報,2014,36(12):2822-2827.(CHENG Y S, ZHU J, LIN X K. Uplink resource allocation in device to device enabled cellular network [J]. Journal of Electronics and Information Technology, 2014, 36(12): 2822-2827.)

[14] HUANG B Y, SU S T, WANG C Y, et al. Resource allocation in D2D communication—a game theoretic approach [C]// Proceedings of the 2014 IEEE International Conference on Communications Workshops. Piscataway, NJ: IEEE, 2014: 483-488.

[15] SONG L, NIYATO D, HAN Z, et al. Game-theoretic resource allocation methods for device-to-device communication [J]. IEEE Wireless Communications, 2014, 21(3): 136-144.

[16] 張瀟璐,劉曦,李偉東,等.基于共享資源量的動態多資源公平分配策略[J].通信學報,2016,37(7):151-160.(ZHANG X L, LIU X, LI W D, et al. Dynamic fair allocation of multi-resources based on shared resource quantity [J]. Journal on Communications, 2016, 37(7): 151-160.)

[17] 潘甦,曹跑跑,劉勝美.一種多無線電系統中基于公平性和精細化帶寬分配的資源分配算法[J].電子與信息學報,2015,37(2):399-404.(PAN S, CAO P P, LIU S M. A resource allocation algorithm based on proportional fairness and refined bandwidth allocation for multi-radio systems [J]. Journal of Electronics and Information Technology, 2015, 37(2):399-404.)

[18] CAI X, ZHENG J, ZHANG Y. A graph-coloring based resource allocation algorithm for D2D communication in cellular networks [C]// Proceedings of the 2015 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2015: 5429-5434.

[19] CHEN B, ZHENG J, ZHANG Y. A time division scheduling resource allocation algorithm for D2D communication in cellular networks [C]// Proceedings of the 2015 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2015: 5422-5428.

[20] LI X, LI B, LAN B, et al. Adaptive PF scheduling algorithm in LTE cellular system [C]// Proceedings of the 2010 International Conference on Information and Communication Technology Convergence. Piscataway, NJ: IEEE, 2010: 501-504.

ZHAN Jinzhen, born in 1963, M. S., associate professor. His research interests include wireless network, image processing.

GUO Dawei, born in 1968, Ph.D., associate professor. His research interests include MANET, networked control.

HUA Weixin, born in 1989, Ph.D. candidate. His research interests include D2D communication, target detection and tracking.

Device to device time division scheduling algorithm based on fairness

ZHAN Jinzhen1, GUO Dawei2*, HUA Weixin2,3

(1.NorthwesternPolytechnicalUniversityMingDeCollege,Xi’anShaanxi710124,China; 2.SchoolofAutomation,NorthwesternPolytechnicalUniversity,Xi’anShaanxi710129,China; 3.ShaanxiCompanyLimited,ChinaMobileCommunicationsCorporation,Xi’anShaanxi710074,China)

To solve the problem of throughput degradation caused by slot scheduling delay and channel gain variation in Device to Device (D2D) communication resource allocation, a Fairness Time Division Scheduling (FTDS) algorithm was proposed. Firstly, the system model was established based on the spectrum reuse mode, and was transformed to a combinatorial optimization problem. Then, in the sub-optimal solution of the model, the scheduling period was divided into several equal-length slots by the FTDS algorithm, and the D2D users were assigned to different time divisions according to the priority policy, for the application scenario that D2D users are more than cellular users. Meanwhile, to balance Quality of Service (QoS) and system throughput, a satisfaction weight was constructed to restrict transmission rate, jointly determined the user scheduling priority. In the simulation, compared with TDS and RANDOM algorithm, the average throughput increase of FTDS algorithm was 11.09% and 40.64% respectively, and cumulative distribution of D2D scheduling frequency was more centralized by FTDS algorithm; meanwhile, the time delay of FTDS algorithm decreased as much as 31.22% compared with TDS.The simulation results show that FTDS algorithm has better throughput performance, more fair scheduling mechanism and smaller scheduling time delay.

Device to Device (D2D); resource sharing; time division allocation; satisfaction weight; fair scheduling

2016- 08- 24;

2016- 09- 17。

詹金珍(1965—),男,陜西西安人,副教授,碩士,主要研究方向:無線網絡、圖像處理; 郭達偉(1968—),男,陜西西安人,副教授,博士,主要研究方向:無線自組織網絡、網絡化控制; 滑維鑫(1989—),男,陜西西安人,博士研究生,主要研究方向:D2D通信、目標檢測與跟蹤。

1001- 9081(2017)03- 0711- 06

10.11772/j.issn.1001- 9081.2017.03.711

TN929.5

A