D2D中以用户为中心的联合接入控制和调度方法

王璐瑶 曲 桦, 赵季红 唐 睿 朱正仓 曹照鑫

1(西安交通大学软件学院 陕西 西安 710049) 2(西安交通大学电信学院 陕西 西安 710049) 3(西安邮电大学通信学院 陕西 西安 710061)

D2D中以用户为中心的联合接入控制和调度方法

王璐瑶1曲 桦1,2赵季红2,3唐 睿2朱正仓2曹照鑫2

1(西安交通大学软件学院 陕西 西安 710049)2(西安交通大学电信学院 陕西 西安 710049)3(西安邮电大学通信学院 陕西 西安 710061)

在终端直通D2D(Device-to-Device)链路密集分布的通信系统中，针对多条D2D链路复用相同频带资源产生的同频干扰问题，提出一种以用户为中心的联合接入控制和时域调度方法。区别于传统机制中优化系统吞吐量或能效等系统侧性能，以用户为中心，最大化在调度周期中满足服务质量需求的D2D链路数目。原问题可分解为两部分：接入控制部分为混合整数线性规划问题，属于NP-hard难题，提出一种逐级接入控制算法；基于上述结果，时域调度部分为convex-cardinality问题，同属NP-hard难题，设计一种启发式算法。仿真体现了以用户为中心资源优化的必要性并验证了所提算法的有效性。

以用户为中心 终端直通通信 服务质量 接入控制 时域调度

0 引 言

根据思科公司最新的统计结果[1]，多媒体流已成为无线网络中的主流业务，且随着人们生活方式的改变，越来越多的多媒体流产生在邻近区域，传统基站与设备间的通信模式在上述场景下的传输效率低下。终端直通通信作为一种近距离通信方式，使数据传输链路可直接在设备间建立，而不需经过基站转发。其能大幅度改善用户的服务质量QoS(Quality of Service)感受，提升系统频带利用率，有效降低基站的负载，因此受到了学术和工业方面的广泛关注[2-4]，且被视为5G中的关键技术之一[5]。

然而，当多条D2D链路(D2D Links, D-L)复用同一资源时，会产生同频干扰问题，如何解决此问题成为D2D通信的关键，资源分配能协调用户干扰，有效缓解上述问题[6-7]。在已有文献中，文献[8]在单链路复用单信道场景下，以系统吞吐量为目标，提出了最大化信干噪比的信道选择策略，观察了系统吞吐量受信道数目的影响。文献[9]为了最大化系统总传输速率，针对多链路复用单信道场景，提出了反向迭代组合拍卖机制，降低了算法复杂度。文献[10]在单链路复用单信道场景下，从功率控制角度提出了优化D2D用户功率的方法，优化了传输速率。文献[11]针对多用户复用单信道场景，通过信道分配，借助贪婪算法优化了系统的整体吞吐量。文献[12]为了优化频谱利用率，在单链路复用单信道场景下，联合功率控制和模式选择，最大化频谱利用率。文献[13]为保证D-L用户的QoS同时最小化系统总能耗，针对单链路复用单信道场景，联合模式选择、功率控制和信道分配，优化了目标。文献[14]在单链路复用单信道场景下，联合功率控制和资源分配，提出一种基于图论的资源分配机制，保证蜂窝用户和D2D用户的服务质量，在接入用户数量最大的前提下最小化系统能耗。文献[15]针对多用户复用单信道资源场景，联合接入控制、功率控制和信道分配，最大化系统吞吐量，保证了已有蜂窝链路(cellular link, C-L)用户和D-L用户的QoS。文献[16]在多链路复用单信道场景下，考虑最佳的功率分配并提出了保证D-L用户的QoS前提下最大化系统吞吐量的机制。文献[17]针对单链路复用单信道场景，联合功率控制和模式选择，以穷举搜索的方法保证了用户传输速率。

但文献[8-17]存在以下缺陷：1) 未以用户为中心保证用户的QoS，无法保证用户的通信质量，降低了用户的服务感受[8-11,13-14,16]；2) 保证了D-L用户的QoS，但场景为单个D-L用户仅能复用单个资源[12-14]，未研究单个D-L用户复用多个信道资源场景；3) 未考虑联合优化多维无线资源，无法实现系统性能的最优化[11-12]；4) 算法复杂度高，难以实现[17]。

基于此，本文提出了一种以用户为中心的资源分配方法。原问题可分解为以下两部分：接入控制AC(admission control)部分在保证D2D用户最低误码率要求的前提下，最大化单时隙内能复用相同频带资源的D-L数目。其属于混合整数线性规划问题，一般意义下属于NP-hard难题，因而提出了一种逐级AC算法，实现算法性能与复杂度的折中。基于上述结果，时域调度TS(time scheduling)部分在保证用户数据的传输速率基础上，确定用户的调度次数，从而最大化满足用户QoS需求的D-L数目。其等价于CC(convex-cardinality)问题，同样属于NP-hard难题，进而提出一种低复杂度的启发式算法。仿真结果表明，本文所提方法以用户为中心资源优化的必要性，并验证了所提算法的有效性。

1 系统模型

1.1 网络结构

本文考虑单小区蜂窝网络上行链路，且假定小区间的干扰得到了有效控制。此外，假设系统为D-L链路设定了专有的接入资源，不存在C-L对D-L产生干扰问题，但D-L间可复用相同资源，此时会产生同频干扰。小区内D-L集合为D={1,2,…,M}，其中M表示D-L的总数目，每条D-L中包括一个发射端DT(D2D Transmitter)和一个接收端DR(D2D Receiver)。本文考虑基于时分多址接入系统，时隙结构如图1(a)所示，帧是最小的调度周期，每个帧中包含若干个时隙。在每个时隙，多链路同时复用相同资源进行通信，如图1(b)所示：DT1和DR1通信，DT2和DR2通信，且接入同一资源中，则DT1对DR2产生了同频干扰，DT2对DR1产生了同频干扰；DT3、DR3、DR4与DT4亦然。

图1 时隙结构图和同频干扰图

对于任意时隙，第i条D-L的信干噪比SINR(Signal to Interference plus Noise Ratio)值为：

(1)

1.2 用户需求模型

(2)

其中：向量w=[wi]M×1表示每条D-L为满足其传输速率需在调度周期内复用资源的最少次数，ceil(a)表示不小于a的最小正整数。图2展示了一种可能的调度结果，其中，DT1和DR1与DT2和DR2链路接入时隙T1，能够保证上述两条链路的最低误码率需求(等价于最低SINR门限需求)。在整个调度周期，根据调度结果进行时域调度，从而满足用户的QoS。

图2 D-L用户在时域的接入示意图

1.3 问题构建

(3)

定义向量α=[αk]|F|×1表示在整个调度内复用图样被调度的次数，则Gα表示每条D-L在调度周期内的复用资源的总次数。若w-Gα≤0表示第i条D-L的速率需求在整个调度周期内得到满足；则w-Gα>0表示第i条D-L的速率需求未被满足。因此引入辅助变量q=[qi]M×1，并将w-Gα≤q引入限制条件。其中，qi=0表示该D-L满足速率要求，而qi>0表示该D-L不满足速率要求。因此最大化任意时隙中接入的D-L数目等价于最小化变量q内非零数目，即可通过最小化card(q)作为本文问题的优化目标值。综上所示，本文联合AC与TS方法可描述为问题1,P1(Problem 1)：

P1:minimizeαk∈{0,1,2,…},qi∈{0,1,2,…}card(q)

s.t.w-Gα≤q

(4)

11×|F|α≤Nf

(5)

式中：11×|F|表示元素全1的行向量；式(4)表示第i条D-L的速率要求在调度周期内被满足；式(5)表示总时隙个数不能超过Nf。

2 联合接入控制(AC)和时域调度(TS)

为了保证用户QoS的同时，最大化D-L链路的接入数目，从而最小化复用资源数目，提出了一种联合AC和TS方法。首先AC部分在单时隙下确定满足最低误码率条件的D-L链路集合，从而确定接入矩阵G；根据AC的结果，TS部分对不同时隙的资源进行调度，从而最小化所复用的资源数目。TS是基于AC所得的优化结果。

2.1 接入控制(AC)部分

AC部分的目的是为了生成复用矩阵G，根据1.3节复用图样的定义可知，随着D-L数目的增加，G的维度会呈现指数型增长。此外，如式(3)所示，相比于{1}、{2}、{3}，复用图样{1,2}、{1,3}能够更加充分利用每个时隙资源，我们将其作为最大复用图案，从而更加有利于最大化整个调度周期内满足QoS需求的链路数目。为了更好地阐述G中特定复用图样的性质，我们首先引入下列定义。

定义最大复用图样An，n为最大复用图案的个数，满足下列两个条件：

条件1i为D-L，i∈An；

满足条件1表示D-L链路i有机会接入系统，满足条件2表示每个时隙资源被最大数目的D-L复用，从而创造出最多的复用机会，保证最多数目的D-L链路能够接入系统。为了求解An，我们假定向量x=[xi]M×1表示某时隙下可接入的D-L。若第i条D-L在该时隙下接入，xi=1；否则，xi=0。为优化P1，则需要最大化任意时隙中接入的D-L链路数目，即最大化x的元素之和。求得x后，可将x整合成矩阵G，从而可进一步优化P1。根据单时隙下，为保证D-L用户的QoS，并最大化接入资源的D-L数目，可以描述为问题2,P2(Problem 2)：

P2:maximizepi,xi∑i∈Dxi

(6)

(7)

xi∈{0,1}xj=1 ∀i,j∈D

(8)

2.1.1 传统算法及缺陷

易知，P2为混合整数线性规划问题，属于NP-hard难题，在优化理论中，可以借助分支限界法BB(branch-and-bound)[18]得到最优解，但是上述过程需要较长的计算时间。若用β表示当找到最优解时在遍历树上途径的节点数目，则BB算法的复杂度为O(β(2M)3)。其中(2M)3表示利用单纯形法求解遍历树上任意节点处线性规划问题的平均复杂度。随着问题维度M的增大，β也会一定程度的增加，而且会出现β→∞的情况。然而在LTE-A通信系统的实际部署中，资源分配需在若干时隙内(毫秒级)完成。因此，BB算法并不适用于本文所考虑的问题。

为方便计算，将P2的优化目标变量转化为l0-norm函数形式，可以描述为问题3,P3(Problem 3)：

P3:minimizepi,xicard(y)

(9)

(10)

0≤xi≤1xj=1 ∀i,j∈D

(11)

式中：y=[yi]M×1,yi=1-xi；上述目标函数为l0-norm函数，表示向量中非零元素个数的函数。P3属于混合整数线性规划问题，可进一步将目标变量中的l0-norm函数形式转化为l1-norm函数形式，描述为问题4,P4(Problem 4)：

s.t. (5-a);(5-b);(5-c)

(12)

P4属于线性规划问题，从而可借助单纯形法求解，但求解结果与理论值相差较大。

2.1.2 逐步接入控制(AC)算法

基于传统算法的不足，本文提出一种逐步接入控制算法，在降低复杂度的同时保证系统效率，解决P2。算法分为优先接入和可行性检测两部分。优先接入目标是在满足式(7)的前提下最大化接入链路数目，引入D-L链路的测度值；可行性检测的目标则是满足P2中的式(6)，从而在低复杂度的情况下解决P2。

(13)

2) 第二部分为可行性检测。首先求第一部分中优先考虑接入资源的D-L的最优发射功率，并判断其最优发射功率是否满足式(6)；其次若满足，则判断其最低误码率是否得到满足。针对式(7)的约束条件，可表述为：

(14)

(E-ΓΖ)p≥Γn

(15)

式中：p表示D-L的发射功率向量；E表示Uj的模|Uj|维的单位矩阵；Γ表示D-L最低QoS需求对应的SINR门限的对角矩阵；Ζ表示D-L间归一化路径增益矩阵；n表示归一化噪声功率向量。具体定义如下：

(16)

(17)

(18)

(19)

由式(16)-式(19)知，Γ为正值，且不可约，式(15)可以满足最低的QoS条件为(E-ΓΖ)p≥Γn，即：

p*=(E-ΓΖ)-1Γn

(20)

每次更新Uj后，将其转化为矩阵x(过程类似F转化为G)，将x存入矩阵G中，若x⊂G，则不存入。遍历所有j∈D后，得到最终接入矩阵G。

综上所述：算法如算法1所示。

算法1过程

初始化：确定接入的第j条D-L；确定最大发射功率和最低QoS需求；确定每条D-L传输速率需求；初始化接入D-L的集合Uj和剩余D-L的集合Vj。

步骤2可行性检测。根据步骤1中得到的优先接入链路由公式P*=(E-ΓΖ)-1ΓN计算优先接入D-L的最优发射功率，并判断其是否小于最大发射功率，若符合，计算ΓΖ的最大特征值λ。若λ<1，则确定该条D-L接入链路，将其从Vj删除并加入到Uj中，得到集合Uj的矩阵表示形式x，类似F转化为G的过程；否则将其从Vj删除，返回步骤1。

2.2 时域调度部分

上述AC部分经功率控制和干扰协调，求解单时隙内D-L链路的接入矩阵G。据此，在已知G的条件下如何求解P1就成了关键。但P1是混合整数线性规划问题，可见定理1，其一般意义下为NP-hard难题。

定理1已知矩阵G的条件下，问题P1是混合整数线性规划问题。

证明：P1可改写为问题5,P5(Problem 5)：

P5:minimizeαk∈{0,1,2,…},qi∈{0,1,2,…}∑i∈Dπi

s.t.πili≤qi≤πiuii∈Dπi∈{0,1}w-Gα≤q11×|F|α≤Nf

(21)

式中：li为qi的最小值，其值可通过式(22)求解，ui为qi的最大值，其值可通过式(23)求解。当πi=0时，qi=0；当πi=1时，li≤qi≤ui，故目标变量中最小化∑i∈Dπi等于最大化q中零元素的个数，即最小化card(q)，此问题为混合整数线性规划问题。

minimizeαk∈{0,1,2,…},qi∈{0,1,2,…}qis.t.(4-a)(4-b)

(22)

maximizeαk∈{0,1,2,…},qi∈{0,1,2,…}qis.t.(4-a)(4-b)

(23)

上述算法如算法2所示，初始化部分复杂度为O(M)，假定Ig为该部分所分配的时隙数，|An|是单时隙下接入最多的D-L数，则算法复杂度为O(|An|Ig)，其中|An|≤M，由于最多有Nf个时隙，所以Ig≤Nf。时域调度部分算法总复杂度为O(|An|Ig+M)，故其最差算法总复杂度为O(M(Nf+1))。因此，联合AC和TS过程的总复杂度为O(M5(Nf+1))。

算法2过程

初始化：确定w矩阵，删除w(i)-Nf>0,i∈D中D-L链路i，置w(i)=0。初始化矩阵α=[α(j)]|F|×1=0,j∈Φ。

步骤1是否所有的时隙都分配到最大复用图样或者是否所有D-L的QoS需求都得到满足，如果是则算法结束，否则进入步骤2；

3 仿真结果

仿真考虑单个半径为300 m的圆形蜂窝小区，基站位于中心，所有蜂窝用户与DT均匀分布在小区内， DR以DT为中心，形成半径为10～50 m间的圆形区域，仿真部分使用的主要参数说明和设置详见表1。整个时间长度为1 000时隙，使用MATLAB平台进行仿真。

表1 主要仿真参数的说明和设定

3.1 逐步接入控制(AC)算法部分

此部分仿真中涉及的算法包括：

(1) l1-norm算法：算法复杂度低，但是性能不足。

(2) BB算法：能够得到理论最优解，但可能会出现指数型的复杂度，在实际情况中应用难度较大。

(3) 本文AC算法：针对P1的AC问题，利用本文所提的逐步接入控制算法，确定单时隙内在保证用户最低误码率前提下最大化接入资源的D-L数目。

仿真中所涉及算法的复杂度，如表2所示。

表2 仿真中所涉及算法复杂度分析

图3为在1 000次迭代条件下，小区内D-L数由20变化到30时，接入资源的D-L链路与总链路比值的变化。随着D-L数目的增加，比值程下降趋势。因为接入所需资源不变，D-L链路的增加使得系统间干扰增大，所能接入的D-L链路相对减小。图中可见本文AC算法明显优于l1-norm算法，性能比l1-norm算法提高了31.21%，比BB算法仅降低了4.09%。

图3 AC算法的性能对比

3.2 联合AC和时域调度(TS)算法部分

此部分仿真中涉及的算法包括：

(1) 随机算法：在本文所提AC部分的基础上通过随机方式求解，复杂度低，但性能不足；

(2) BB算法：在本文所提AC部分的基础上可得到理论最优解，但可能会出现指数型的复杂度；

(3) 本文联合AC和TS算法：在本文所提AC部分的基础上联合TS阶段所提的启发式算法解决P1。

仿真中所涉及算法复杂度如表3所示。

表3 仿真中所涉及算法复杂度分析

图4为在1 000次迭代条件下，小区内D-L数由20变化到30时，接入资源的D-L链路与总链路比值的变化。随着D-L数目的增加，比值程下降趋势。因为D-L间的干扰不断增加，可接入的D-L数不断减小，导致未接入的D-L数不断增加，系统性能降低。图中可见本文联合AC和TS算法为接近最优的启发式算法，比最优算法性能仅减少了1.72%，但比随机算法性能提升了13.03%，体现了本文算法的有效性。

图4 联合AC和TS算法的性能对比

4 结 语

本文通过分析D2D链路密集分布的场景，提出了以用户为中心的联合接入控制和时域调度方法，解决了在保证D2D链路服务质量的前提下，最大化接入链路数目问题。通过仿真表明，本文算法为近似最优算法，实现了算法性能和复杂度之间的折中。

[1] Cisco.Cisco visual networking index:global mobile data traffic forecast update,2015-2020[M].white paper at Cisco.com,Feb.,2016.

[2] Tang R,Zhao J H,Qu H.Joint Optimization of Channel Allocation,Link Assignment and Power Control for Device-to-Device Communication Underlaying Cellular Network[J].China Communications,2015,12(12):92-100.

[3] Mach P,Becvar Z,Vanek T.In-band Device-to-Device Communication in OFDMA Cellular Networks:a Survey and Challenges[J].IEEE Communication Surveys & Tutorials,2015,17(4):1885-1922.

[4] Tang R,Zhao J H,Qu H,et al.Joint mode selection and resource allocation for mobile relay-aided device-to-device communication[J].KSII Transactions on Internet and Information Systems,2016,10(3):950-975.

[5] Imran A,Zoha A.Challenges in 5G:how to empower SON with big data for enabling 5G[J].IEEE Network,2014,28(6):27-33.

[6] 董姣姣,赵季红,唐睿,等.设备直通中基于组合拍卖的联合资源分配机制[J].计算机应用与软件,2017,34(4):118-124.

[7] 朱正仓,赵季红,唐睿,等.移动中继协助下终端直通中的模式选择和资源分配方案[J].西安交通大学学报(自然版),2016,50(10):3541-3551.

[8] Han S,Kwon T,Choi J-W.Analysis of D2D system performance with a maximal SINR channel selection strategy[C]//Information and Communication Technology Convergence (ICTC).IEEE,2014:379-380.

[9] Xu C,Song L Y,Han Z,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/Supplement,2013,31(9):348-358.

[10] Zhang G P,Yang K,Liu P,et all.Power Allocation for Full-Duplex Relaying-Based D2D Communication Underlaying Cellular Networks[J].IEEE Transactions on Vehicular Technology,2015,64(10):4911-4916.

[11] Zulhasnine M,Huang C,Srinivasan A.Efficient resource allocation for device-to-device communication underlaying LTE network[C]//IEEE,International Conference on Wireless and Mobile Computing,NETWORKING and Communications.IEEE,2010:368-375.

[12] Yu C H,Doppler K,Ribeiro C B,et al.Resource Sharing Optimization for Device-to-Device Communication Underlaying Cellular Networks[J].IEEE Transactions on Wireless Communications,2011,10(8):2752-2763.

[13] Gao C F,Sheng X,Tang J,et al.Joint mode selection,channel allocation and power assignment for green device-to-device communication[C]//International Conference on Communications (ICC).IEEE,2014:178-183.

[14] 王元,赵季红,唐睿,等.D2D多播场景下面向节能的资源分配机制[J].西安电子科技大学学报,2016,43(2):162-167.

[15] Feng D Q,Lu L,Yi Y W,et al.Optimal Mobile Association in Device-to-Device Communications Underlaying Cellular Networks[J].IEEE Transactions on Communications,2013,61(8):3541-3551.

[16] Cheng W C,Zhang X,Zhang H L.Optimal Power Allocation With Statistical QoS Provisioning for D2D and Cellular Communications Over Underlaying Wireless Networks[J].IEEE Journal on Selected Areas in Communications,2016,34(1):151-162.

[17] Minchae J,Kyuho H,Sooyong C.Joint mode selection and power allocation scheme for power-efficient device-to-device (D2D) Communication[C]//75th Vehicular Technology Conference Spring (VTC-S).IEEE,2012:1-5.

[18] Boyd S,Mattingley J.Branch and Bound Methods[R].Stanford:U.S.Stanford University,2007.

USER-CENTRICJOINTADMISSIONCONTROLANDTIMESCHEDULINGFORDEVICE-TO-DEVICECOMMUNICATION

Wang Luyao1Qu Hua1,2Zhao Jihong2,3Tang Rui2Zhu Zhengcang2Cao Zhaoxin2

1(SchoolofSoftwareEngineering,Xi’anJiaotongUniversity,Xi’an710049,Shaanxi,China)2(SchoolofElectronicsandInformationEngineering,Xi’anJiaotongUniversity,Xi’an710049,Shaanxi,China)3(SchoolofTelecommunicationEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’an710061,Shaanxi,China)

In the D2D (Device-to-Device) link intensive communication system, multiple D2D links are multiplexed with the same frequency bandwidth, leading to the co-channel interference problem. Therefore, we propose a user-centric joint admission control (AC) and time scheduling (TS) scheme. In contrast to the conventional schemes of optimizing system throughput or energy efficiency, our user-centric scheme maximizes the number of admitted links with satisfied quality-of-service (QoS) requirements in each scheduling period. The original problem was divided into two parts: the AC subproblem and the TS subproblem. Particularly, the former part turned out to be mixed-integer linear programmings, which belong to NP-hard, so we propose a gradual AC scheme; based on the above results, time scheduling was part of the convex-cardinality problem and belong to the NP-hard problem, Thus, we design a heuristic algorithm. Simulations verify the necessity to perform user-centric optimization and illustrate the advantages of our proposed scheme.

User-centric D2D communication QoS Admission control Time scheduling

2017-01-27。国家自然科学基金项目(61372092，61531013)；教育部中国移动科研基金项目(MCM20150102)。王璐瑶，硕士，主研领域：D2D通信。曲桦，教授。赵季红，教授。唐睿，博士。朱正仓，硕士。曹照鑫，博士。

TP393

A

10.3969/j.issn.1000-386x.2017.12.031