Abstract：The performance of the graph-based scheduling for device-to-device communications overlaying cellular networks is studied. The graph-based scheduling consists of two stages, the frequency assignment stage and the time slot scheduling stage. For such scheduling, a theoretical method to analyze the average spectrum efficiency of the D2D subsystem is proposed. The method consists of three steps. First, the frequency assignment stage is analyzed and the approximate formula of the average number of the D2D links which are assigned the same frequency is derived. Secondly, the time slot scheduling stage is analyzed and the approximate formula of the average probability of a D2D link being scheduled in a time slot is derived. Thirdly, the average spectrum efficiency of the D2D subsystem is analyzed and the corresponding approximate formula is derived. Analysis results show that the average spectrum efficiency of the D2D subsystem is approximately inversely linearly proportional to the second-order origin moment of the normalized broadcast radius of D2D links. Simulation results show that the proposed method can correctly predict the average spectrum efficiency of the D2D subsystem.
Key words：cellular; device-to-device (D2D) communication; graph; scheduling; spectrum efficiency
Device-to-device (D2D) communications refer to the technologies that enable devices to communicate directly[1-3]. D2D communications in cellular networks consist of two phases. The first is discovery, which is to identify that a user equipment (UE) is in proximity of another; the second is data transmission, during which the D2D UEs exchange data traffic directly over the air. This paper focuses on the data transmission phase.
A major concern with D2D data transmission is the interference caused by D2D links, including interference between D2D transmission and cellular reception, the interference between cellular transmission and D2D reception, and the interference between D2D transmission and D2D reception. To mitigate the interference, different methods can be used, including resource orthogonalisation or overlay[4-8], power control[9-11], signal processing based methods[12-13], and graph based scheduling[14-15], and so on. In this paper, we consider cellular D2D communications, in which a combination of resource orthogonalisation and graph-based scheduling is used. The underlay case will be considered in our future work.
The graph-based scheduling is one of the effective techniques for interference mitigation, in which the base station (BS) can identify parallel non-interfering D2D transmissions whenever possible so that the efficiency and capacity of D2D communications can be improved. However, most existing works in the literature evaluate the performance of the graph-based scheduling via simulation and there is lack of theoretical analysis of the performance of the graph-based scheduling. Therefore, this work will provide the theoretical formula of D2D spectrum efficiency under the graph-based scheduling to fill the gap of the literature in this aspect. Specifically, analysis results show that the D2D spectrum efficiency under the graph-based scheduling is inversely linearly proportional to the second-order origin moment of the normalized broadcast radius of D2D links. Simulation results validate the correctness of the proposed theoretical analysis formula. Additionally, this work focuses on the overlay scenario and the analysis method can be directly extended to the underlay scenario, which will be included in our future work.
Consider a frequency division duplex (FDD) cell and assume that D2D communications use the uplink spectrum. There is a number of frequency units (FUs) allocated to the uplink, among which assume that there are J FUs reserved for D2D communications. In the time domain, assume that the time axes are organized into consecutive time units (TUs). The basic resource unit for data transmissions is denoted as a resource unit (RU), which is defined by one FU in the frequency domain and one TU in the time domain, respectively. For simplicity, it is assumed that all RUs of these J FUs can be used by D2D communications.
Let Q denote the number of D2D links in a cell. For each D2D link, it is assumed that the discovery phase has been finished, the D2D link has been established, and the BS has the knowledge of its existence. There can be interference between D2D links. We call two D2D links neighbors if the receiver of one D2D link can “hear” from the transmitter of another. To avoid interference, it is specified that neighbor D2D links shall not reuse the same resource. This constraint can be modeled by the interference graph G=(V,E), where each vertex in V represents a D2D link and each edge in E between two vertices denotes that the two corresponding D2D links are neighbors. An example is provided in Fig.1 to illustrate how to relate D2D networks to graph. In this example, it is assumed that there are four D2D links, as shown in Fig.1(a). Therefore, there are four vertices in the graph, as shown in Fig.1(b). Furthermore, since R1 is in proximity of T4, the vertices 1 and 4 are connected with an edge in the graph; since R2 is in proximity of T3, the vertices 2 and 3 are connected with an edge in the graph; and so on. This paper focuses on the graph-based scheduling and how to construct the interference graph is out of the scope of this paper[15].
(a) (b)
Fig.1 An example of scenario. (a) D2D links; (b) Interference graph
This section performs the theoretical performance analysis of the graph-based scheduling for cellular D2D communications. First, a scheduling algorithm[16], which is selected as the example of the graph-based scheduling for D2D communications, is briefly described for completeness. Let ηD2D denote the average spectrum efficiency of D2D communications in a cell, bit/(s·Hz). Then, a theoretical formula to calculate the value of ηD2D is derived.
2.1 Scheduling algorithm
The scheduling algorithm consists of two stages. The first is the FU assignment stage, and the second is the TU scheduling stage. In the FU assignment stage, all Q links are divided into J groups and each group is assigned one FU. Let Gj=(Vj,Ej) denote the interference subgraph on FU j where each vertex in Vj represents a link to which FU j is assigned. Initially, Gj is empty. Consider link q. If this link is assigned FU j, then the subgraph on FU j shall be updated to be 
=(Vj∪{q},
), where is the set of edges in the subgraph after link q has joined the j-th group. Define 
, where Ej is the set of edges in the subgraph before link q joins the j-th group. Then, we find j(q) for which the value of dj,q is the smallest. If j(q) is not unique, just pick randomly to break the tie. Having determined to assign FU j(q) to link q, we update the subgraph 
(q), while keeping other subgraphs Gj (j≠j(q)) unchanged. Repeat the above steps for each D2D link. In the TU scheduling stage, the following notions are needed to describe the operations. Let Qj denote the set of D2D links to which FU j is assigned; xq(t) denotes the binary decision variable which is valued 1 if RU (j,t) is allocated and 0 otherwise; Cq(t) denotes the throughput achieved by D2D link q on RU (j,t) if allocated; and Rq(t) denotes the throughput of the D2D link q up to TU t. The value of Rq(t) is updated according to Rq(t)=(1-εt)Rq(t-1)-εtxq(t)Cq(t) where εt is equal to 1/t and the initial value Rq(0) is set to be an arbitrary small positive constant. The TU scheduling stage consists of the following steps.
1) For (j,t), calculate Rq(t) for each q∈Qj;
2) For (j,t), determine wq(t)=Cq(t)/Rq(t-1) for each q∈Qj;
3) For (j,t), solve the following maximum weight independent set problem via the greedy algorithm[16]:
s.t. xq(t)+xp(t)≤1, (p,q)∈Ej
4) Repeat steps 1) to 3) until all J FUs have been treated;
5) Update t←t+1 and repeat steps 1) to 4).
2.2 Derivation of ηD2D
First, we analyze the FU assignment stage. Let nj denote the number of D2D links which are assigned to the j-th FU. Since the philosophy behind the proposed FU assignment scheme is that the interference among D2D links shall be balanced among FUs, we make the first approximation,
(1)
Secondly, we analyze the TU scheduling stage. Pick arbitrarily a D2D link q (1≤q≤Q) and assume that the broadcast radius of correct decoding at the given SINR threshold for the transmitter of D2D link q is rq (unit:m). Define the ratio
(2)
where R is the radius of the cell, m. According to the graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex. Let Dq denote the degree of vertex q in graph G. It can be calculated as
(3)
Let D denote the average degree of the interference graph G. Therefore, we can approximately calculate that
D=Ε[Dq]≈Ε[α2]Q
(4)
where αq is assumed as a realization of random variable α and E[·] is the expectation of a random variable. According to the probability theory, we can calculate E[α2]=Var(α)+(E[α])2, where Var(·) represents the variance of a random variable. Assuming that all D2D links are uniformly distributed in the cell, we have E[α]=(αmin+αmax)/2 and Var(α)=(αmax-αmin)2/12, where αmin and αmax are the minimal and maximal values of α, respectively. Therefore, we have
(5)
Assume that the transmitter of this D2D link has μq neighbor D2D links. Then, we propose to approximate the value of μq as
μq≈D
(6)
Now, we consider the j-th FU and the associated interference subgraph is Gj. Let Dj denote the average degree of the interference subgraph Gj. Therefore, we make the approximation,
(7)
For any vertex in Gj, it cannot be scheduled simultaneously with its neighbors in one TU. Therefore, we propose to approximate the average probability of a vertex in Gj being scheduled in one TU as
(8)
Finally, we analyze the value of ηD2D. Let Cj,i,t (bit/s) denote the average transmission capacity of the i-th D2D link which is assigned to the j-th FU in the t-th TU. Let WFU (Hz) denote the bandwidth of the FU. We have
(9)
where xi,t is a binary variable to indicate whether the D2D link has been scheduled or not. When T approaches infinity, we can approximately have
(10)
where E[Cj,i] represents the average transmission capacity of the i-th D2D link which is assigned the j-th FU. Substituting Eqs.(8), (7) and (4) into Eq.(10), we have
(11)
Let CD2Dlink denote the average D2D link-level transmission capacity over one FU and it can be expressed as
(12)
Substituting Eq.(12) into Eq.(11), then we have
Let ηD2Dlink=CD2Dlink/WFU denote the average value of the D2D link-level spectrum efficiency. Then, we have the approximate formula,
(13)
Actually, the main purpose of the graph-based scheduling is to avoid interference among D2D links as much as possible. Therefore, for each TU, all scheduled D2D links will not or basically not interfere with each other (i.e., spatial reuse). According to the theoretical analysis result in Eq.(13), the average number of such D2D links on each TU is approximately 1/E[α2]. Therefore, 1/E[α2] measures the spatial reuse gain of the graph-based scheduling algorithm. This result helps us understand the key factors of the performance of cellular D2D communications.
In this section, simulation results are reported to validate the correctness of the analytical formula of ηD2D in Eq.(13).
3.1 Parameter setting
Consider a single cell in which Q D2D links are uniformly distributed. The main parameters used in this section are listed in Tab.1. Each simulation run consists of the following steps.
Tab．1 Simulation parameters
ParametersValueCellradiusR/m500BandwidthofoneFUWFU/kHz180MaximumtransmitpowerPmax/dBm23NoisepowerdensityN0/(dBm·Hz-1)-174Shadowingstandarddeviationσ/dB8PathlossPL(x)/dB30.6+40lg(x)NumberofFUallocatedtoD2DlinksJ12D2DlinknumberQ100to1000MaximumdistanceofD2Dlinkdmax/m35TargetSINRofeachD2DlinkK0/dB3
First, Q D2D links are generated. For each D2D link q, the transmitter is placed according to a uniform distribution into the cell. The distance dq between the transmitter and receiver is selected from 1 to dmax uniformly, and the direction of a D2D link is also uniformly generated. For each D2D link q, assume the target SINR K0 to be fixed. Let PT,q denote the transmit power of D2D link q. To satisfy the target SINR at the receiver, the transmitter devices employ open loop power control and set the transmit power as PT,q=min(K0+PN+PL(dq), Pmax), where PN is the noise power in dBm. Before scheduling, the interference graph shall be constructed. Then, the actual interference graph is constructed. Recall that the broadcast radius of D2D link q is denoted by rq. For simplicity and without loss of generality, we calculate the value of rq based on the model rq=wdq, where we set w=2 in the simulations[17]. We assume that the broadcast radius of both the transmitter and the receiver of D2D link q are the same and equal to rq. For any two D2D links q and j, let dqj denote the distance between the transmitter of link q and the receiver of link j. If dqj<rq, there is an edge connecting the two corresponding vertices in the actual interference graph. Additionally, after obtaining the values of rq, we can calculate the values of αq according to Eq.(2) and then the value of 1/E[α2] according to Eq.(5), which is used for the calculation of ηD2D according to Eq.(13).
After constructing the interference graph, we perform the scheduling algorithm. During the simulation, for each D2D link q, the received power PR,q is determined by PR, q=PT, q-PL(dq)-β, where β represents the shadow fading. The SINR of D2D link q is calculated according to γq=PR,q/(PI,q+PN),where PI,q is the interference power caused by D2D links which are scheduled in the same RU as D2D link q. Finally, the link level spectrum efficiency of D2D link q is calculated according to the Shannon formula log2(1+γq).
3.2 Validation of theoretical analysis
First, we validate the analysis of the FU assignment stage. For this stage, it is expected that the values of 
(i.e., the number of D2D links which are assigned the j-th FU) are approximately the same for different j, respectively, where Gj=Vj,Ej) is the interference subgraph on FU j. The simulation results are plotted in Fig.2(a). Observing the values in the figure, we can find that the values of are approximately the same for different j for different Q. Furthermore, we plot the theoretical values predicted by Eq.(1) in Fig.2(a), which match the simulation results well. This shows that the approximation we made in Eq.(1) is accurate. We then validate the analysis of the TU scheduling stage. For this stage, we have made an approximation in Eq.(8). To validate the correctness of the theoretical analysis, the simulation results and theoretical values of scheduling probability pj (i.e. the average probability of a vertex in Gj being scheduled in one TU) are plotted in Fig.2(b). Simulation results show that the prediction error increases with the increase of Q. This is due to the fact that the topology of the interference graph becomes complicated with the increase of Q so that the accuracy of the approximation made in Eq.(8) is decreased.
(a)
(b)Fig.2 Validation of theoretical analysis.(a) Performance of FU assignment;(b) Performance of TU scheduling
Secondly, we validate the analysis of spectrum efficiency ηD2D. In Fig.3(a), the distribution of ηD2Dlink (i.e. link level spectrum efficiency) is plotted, where the values are distributed around log2(1+K0)=1.585. In Fig.3(b), the simulation results of the number of D2D links which are simultaneously scheduled are plotted, where the red dotted line represents the average value. In Fig.3(c), the theoretical values predicted in Eq.(13) and simulation results of the D2D spectrum efficiency η are plotted. The performance of the random scheduling algorithm is also plotted for comparison purposes. Simulation results show that for the considered parameters, the prediction error is no more than 10%. Furthermore, the prediction error decreases with the decrease of Q.
(a)
(b)
(c)Fig.3 The performance of resource scheduling.(a) Spectrum efficiency of D2D links;(b) Number of D2D links scheduled simultaneously;(c) Spectrum efficiency of D2D subsystem
This paper focuses on the interference graph-based resource scheduling for overlay cellular D2D communications. The theoretical performance analysis of the scheduling algorithm is performed. Simulation results show that the theoretical performance analysis is accurate and the interference graph-based resource scheduling algorithm works well with the D2D link number as large as 1 000. Our future work will extend this to the underlay case.
References：
[1]Doppler K, Rinne M, Wijting C, et al. Device-to-device communication as an underlay to LTE-advanced networks [J]. IEEE Communications Magazine, 2009, 47(12): 42-49. DOI:10.1109/mcom.2009.5350367.
[2]Fodor G, Dahlman E, Mildh G, et al. Design aspects of network assisted device-to-device communications [J]. IEEE Communications Magazine, 2012, 50(3): 170-177. DOI:10.1109/mcom.2012.6163598.
[3]Lien S Y, Chien C C, Tseng F M, et al. 3GPP device-to-device communications for beyond 4G cellular networks [J]. IEEE Communications Magazine, 2016, 54(3): 29-35. DOI:10.1109/mcom.2016.7432168.
[4]Sun S, Gao Q, Chen W, et al. Recent progress of long-term evolution device-to-device in third-generation partnership project standardization [J]. IET Communications, 2015, 9(3): 412-420. DOI:10.1049/iet-com.2014.0311.
[5]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.
[6]George G, Mungara R K, Lozano A. An analytical framework for device-to-device communication in cellular networks [J]. IEEE Transactions on Wireless Communications, 2015, 14(11): 6297-6310. DOI:10.1109/twc.2015.2452264.
[7]Khoshkholgh M G, Zhang Y, Chen K C, et al. Connectivity of cognitive device-to-device communications underlying cellular networks [J]. IEEE Journal on Selected Areas in Communications, 2015, 33(1): 81-99. DOI:10.1109/jsac.2014.2369611.
[8]Lin X, Andrews J G, Ghosh A. Spectrum sharing for device-to-device communication in cellular networks [J]. IEEE Transactions on Wireless Communications, 2014, 13(12): 6727-6740. DOI:10.1109/twc.2014.2360202.
[9]Song H, Ryu J Y, Choi W, et al. Joint power and rate control for device-to-device communications in cellular systems [J]. IEEE Transactions on Wireless Communications, 2015, 14(10): 5750-5762. DOI:10.1109/twc.2015.2442975.
[10]Lee N, Lin X, Andrews J G, et al. Power control for D2D underlaid cellular networks: Modeling, algorithms, and analysis [J]. IEEE Journal on Selected Areas in Communications, 2015, 33(1): 1-13. DOI:10.1109/jsac.2014.2369612.
[11]Lin M, Ouyang J, Zhu W. Joint beamforming and power control for device-to-device communications underlaying cellular networks [J]. IEEE Journal on Selected Areas in Communications, 2016, 34(1): 138-150. DOI:10.1109/jsac.2015.2452491.
[12]Ni Y, Jin S, Xu W, et al. Beamforming and interference cancellation for D2D communication underlaying cellular networks [J]. IEEE Transactions on Communications, 2016, 64(2): 832-846. DOI:10.1109/tcomm.2015.2507574.
[13]Ma C, Liu J, Tian X, et al. Interference exploitation in D2D-enabled cellular networks: A secrecy perspective [J]. IEEE Transactions on Communications, 2015, 63(1): 229-242. DOI:10.1109/tcomm.2014.2379633.
[14]Zhang R, Cheng X, Yang L, et al. Interference graph-based resource allocation (InGRA) for D2D communications underlaying cellular networks [J]. IEEE Transactions on Vehicular Technology, 2015, 64(8): 3844-3850. DOI:10.1109/tvt.2014.2356198.
[15]Wu W, Zhang Y. Constructing conflict graph for D2D communications in cellular systems [C]//International Conference on Wireless Communication and Signal Processing (WCSP 2014). Nanjing, China, 2014: 1-5.
[16]Zhang Y, Wu W, Li X. Resource allocation method for device-to-device communications in cellular networks [J]. Journal of Southeast University (English Edition), 2013, 29: 361-365.
[17]Wu Z, Park V D, Li J. Enabling device to device broadcast for LTE cellular networks [J]. IEEE Journal on Selected Areas in Communications, 2016, 34(1): 58-70. DOI:10.1109/jsac.2015.2452585.
Citation：Du Peng, Zhang Yuan．Performance analysis of graph-based scheduling for device-to-device communications overlaying cellular networks[J]．Journal of Southeast University (English Edition),2016,32(3):272-277．DOI:10.3969/j.issn.1003-7985.2016.03.003.
DOI：10.3969/j.issn.1003-7985.2016.03.003
摘要：研究了基于图的蜂窝覆叠D2D通信调度算法的性能,该调度算法由频率分配与时隙调度2个阶段组成．针对该算法,提出了一种对D2D子系统的平均频谱效率性能进行理论分析的方法．该方法包括3个步骤．首先,对频率分配阶段进行了分析,推导了被分配使用同一频率资源的D2D链路个数的近似公式．其次,对时隙调度阶段进行了分析,推导了每条D2D链路在单个时隙内被调度的概率的近似公式．然后,对D2D子系统的平均频谱效率性能进行了分析,并推导了相应的理论公式．理论分析结果表明,在基于图的调度算法下,D2D子系统的平均频谱效率与D2D链路的归一化广播半径的二阶原点矩成线性反比关系．仿真结果表明该方法能够准确地预测D2D子系统的平均频谱效率性能．
关键词：蜂窝网络； D2D通信; 图; 调度; 频谱效率
中图分类号：TN929.5
Received：2015-12-23．
Foundation item：s：The National Natural Science Foundation of China (No. 61571111), the National High Technology Research and Development Program of China (863 Program) (No.2014AA01A703, 2015AA01A706), the Fundamental Research Funds for the Central Universities of China (No.2242016K40098).
Biographies：Du Peng (1971—), male, doctor, lecturer; Zhang Yuan (corresponding author), male, doctor, associate professor, y.zhang@seu.edu.cn.