# Efficient Resource Scheduling by Exploiting Relay Cache for Cellular Networks

Authors: Chun He; Haixia Cui; Gang Feng
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In relay-enhanced cellular systems, throughput of User Equipment (UE) is constrained by the bottleneck of the two-hop link, backhaul link (or the first hop link), and access link (the second hop link). To maximize the throughput, resource allocation should be coordinated between these two hops. A common resource scheduling algorithm, Adaptive Distributed Proportional Fair, only ensures that the throughput of the first hop is greater than or equal to that of the second hop. But it cannot guarantee a good balance of the throughput and fairness between the two hops. In this paper, we propose a Two-Hop Balanced Distributed Scheduling (TBS) algorithm by exploiting relay cache for non-real-time data traffic. The evolved Node Basestation (eNB) adaptively adjusts the number of Resource Blocks (RBs) allocated to the backhaul link and direct links based on the cache information of relays. Each relay allocates RBs for relay UEs based on the size of the relay UE’s Transport Block. We also design a relay UE’s ACK feedback mechanism to update the data at relay cache. Simulation results show that the proposed TBS can effectively improve resource utilization and achieve a good trade-off between system throughput and fairness by balancing the throughput of backhaul and access link.


---

## Body

## 1. Introduction

Driven by explosive increase in the number of users and data usage, the huge communication traffic volume introduces great challenges to mobile network operators. Substantial research efforts have been dedicated to the next-generation wireless networks, such as the third generation partnership project’s (3GPP) long term evolution-advanced (LTE-A). In LTE-A systems, relays are deployed in traditional microcells for increasing network throughput and improving the coverage of cellular radio networks [1, 2]. In relay-enhanced cellular systems, one or more fixed Relay Node(s) (RN) in the coverage area of the evolved Node Basestation (eNB) split the original macrocell to multiple relay cells. RN can forward packets received from eNB to User Equipment (UE). Each UE can choose to access to an eNB or an RN. When a UE chooses an eNB as access node, then the UE is scheduled by the eNB and it can be called macro-UE or one-hop UE. Otherwise, the UE, which accesses to an RN and is scheduled by the RN, is called relay UE or two-hop UE. As shown in Figure 1, there exist direct link (eNB-macroUE), backhaul link (eNB-RN), and access link (RN-relay UE) in two-hop relay-enhanced cellular system.Figure 1
Relay-enhance cellular network with RNs.In relay networks, various links may operate in shared spectrum [1]. Resource allocation in this kind of networks is a challenging issue to provide sufficiently high data rates for backhaul links, while maintaining fair sharing of resources with UEs. For two-hop links, we need to jointly consider the resource allocation for backhaul links and access links. Otherwise, bottleneck problem may arise, which will greatly degrade the throughput of two-hop links. For in-band relaying, eNBs and RNs are allowed to use the same frequency resources. In other words, the links connected to different nodes (eNB or RN) can reuse frequency resources, while the links connected to the same node need to share resources.Traditional resource scheduling algorithms [3, 4], such as Round Robin (RR), Max C/I, and Proportional Fair (PF), cannot achieve satisfactory performance for relay-enhanced cellular systems. This is because the eNB does not take into account the quality of access link when using these scheduling algorithms to schedule resource for RNs, resulting in unbalanced throughput between backhaul link (or the first hop link) and access link (or the second hop link). Hence, considering the resource allocation of backhaul links or access links independently is not advisable for improving the data rates of UEs. This motivates us to jointly address the resource scheduling for backhaul links and access links. However, the problem of maximizing the sum rate of multiple interfering MSs for only the access links has been proved to be NP-hard [5]. Thus joint resource scheduling for backhaul links and access links is a very challenging problem.In recent years, much work has been done to address resource allocation and scheduling in relay-enhanced cellular systems [6, 7], and most of existing related research work falls into two categories: centralized scheduling and distributed scheduling. For centralized scheduling, eNB is in charge of all links’ channel state and traffic queues and then allocates resource for RNs and UEs in a centralized way, while RN does not need to perform resource scheduling. Centralized scheduling can achieve the optimal resource allocation, but its computational complexity and feedback overhead are extremely huge [8–11]. For distributed scheduling, RNs perform scheduling independently. Distributed scheduling computational complexity and signaling overhead are significantly smaller than those of centralized scheduling. Thus distributed scheduling is more preferable for practical implementation. Thus in this paper we focus on distributed scheduling.The authors of [12] propose that eNB should allocate resource for RNs based on the two-hop UEs’ traffic queue information, which will make RN feedback the status of all two-hop UEs’ traffic queue to the eNB and incur heavy signaling overhead. The authors of [13] propose that RN only feedbacks to eNB the information of two-hop UEs whose traffic queue is empty, but the scheduling results may be not optimal due to possible too late feedback. The authors of [14] propose a modified PF algorithm which gives priority to relay transmission. The authors of [15] propose a joint scheduling between eNB and RN. The authors of [16] propose Adaptive Distributed Proportional Fair (ADPF) scheduling algorithm based on PF, which assures that backhaul link throughput of each RN is greater than or equal to the sum of access link throughput of relay UEs attached to the RN in resource allocation for each RN in order to fully meet the needs of relay UEs. Although ADPF considers rate matching, ADPF cannot guarantee a good balance between the throughput of backhaul link and the throughput of access link, which will result in a waste of resource and poor fairness.One of the distinctive characteristics of 4G/LTE and beyond mobile networks is to provide multimedia communications [17, 18]. Thus there exists real-time traffic such as voice and video and non-real-time traffic such as FTP and email in mobile communications, and the trend of rapid increasing non-real-time traffic becomes apparent. In this paper, we propose Two-Hop Balanced distributed Scheduling (TBS) algorithm by exploiting relay cache for non-real-time data traffic. TBS adaptively adjusts the number of Resource Blocks (RBs) allocated to by backhaul link and direct link based on the cache information of RN for the first hop and allocates RBs for each relay UE based on the size of the relay UE’s Transport Block (TB) in scheduling for the second hop. We design a relay UE’s ACK feedback mechanism to update the data cached at RNs. Simulation results show that the proposed TBS can significantly improve system resource utilization and achieve a good trade-off between system throughput and fairness by balancing the throughput of backhaul and access link.The rest of this paper is organized as follows. In Section2, we present the system model and an overview of relevant preliminary techniques. In Section 3, we elaborate our proposed TBS. Section 4 presents the simulation experiments, as well as numerical results and discussions. Finally, we conclude the paper in Section 5.


## 2. System Model and Preliminary Techniques

### 2.1. System Model

We consider downlink transmission in a two-hop relay-enhanced cellular system withL eNBs. The coverage area of eNB is macrocell (or cell), where each macrocell consists of three sectors, and there are some RNs deployed in each sector. As shown in Figure 1, RNs are uniformly deployed in the macrocell, and there are a number of RNs per sector where the angle between RN and sector antenna is 30 degrees and each RN is located at 2/3 of the radius of the macrocell.We use multiple access technology based on orthogonal frequency division multiplexing access (OFDMA), and transmission resource of system consists of the following three aspects: time domain, frequency domain, and spatial domain. Spatial resource is divided into different layer based on Multi Input Multi Output (MIMO). The basic time-frequency resource unit used for scheduling is called Resource Block (RB). The scheduling cycle is a Transmission Time Interval (TTI) which is one subframe time.We assume that RN operates in half-duplex manner; that is, RN cannot transmit and receive packets simultaneously. Therefore eNB-RN transmission and RN-relay UE transmission cannot be performed at the same time [19], while eNB-macro-UE transmission can be simultaneous with eNB-RN transmission or RN-relay UE transmission. The timing relationship of direct subframe, backhaul subframe, and access subframe is shown in Figure 2.Figure 2
Time relationship of the three subframes.In backhaul subframe, eNB schedules RBs to its subordinate RNs and macro-UEs. In access subframe, RN schedules RBs to its subordinate relay UEs, and eNB schedules RBs to its subordinate macro-UEs. Note that eNB can make its scheduling decisions for macro-UEs simply using Proportional Fair (PF) scheduling in access subframe, which lies outside research scope of this paper.In this paper, full buffer model is considered for eNB. Thus there are always enough downlink packets for macro-UEs and RNs. RN decodes and forwards packets received from eNB to relay UEs.


### 2.2. Preliminary Techniques

PF scheduling algorithm is the basis of our proposed TBS algorithm. As a preliminary study, we first briefly introduce PF scheduling algorithm applied to traditional cellular system only with eNBs and UEs. In PF scheduling, eNB first calculates the PF priority value of each UE on each RB of the RB set to be allocated. Then it finds the maximum priority value and its corresponding RB and UE and allocates the RB to the UE. After an RB has been allocated, it should be deleted from the RB set to be allocated, ensuring that an RB can only be allocated to only one UE.The PF priority value of UEu on RB k in TTI t is defined as follows [20]:(1)
P
u
k
t
=
r
u
k
t
t
c
-
1
R
u
t
-
1
¯
+
∑
k
′
=
1
K
x
u
k
′
t
r
u
k
′
t
,where r
u
k
(
t
) denotes the potential data rate of UE u on RB k in TTI t, indicating the current link quality which is determined by Channel Quality Indicator (CQI) of RB k fed back by UE u, and t
c is the average window size. x
u
k
′
(
t
) denotes whether RB k
′ has been allocated for UE u in TTI t, which is defined as follows:(2)
x
u
k
′
(
t
)
=
1
RB
k
′
has
been
allocated
for
UE
u
in
TTI
t
0
otherwise
.In (1), R
u
(
t
)
¯ denotes the average throughput of UE u up to TTI t whose recursive computation formula is given by(3)
R
u
(
t
)
¯
=
1
-
1
t
c
R
u
(
t
-
1
)
¯
+
1
t
c
R
u
t
,where R
u
(
t
) denotes the throughput of UE u in TTI t.The flow chart of PF algorithm for allocating RBs is shown in Figure3.Figure 3
Flow chart of PF algorithm for allocating RBs.After eNB allocates all RBs to its subordinate UEs, eNB should calculate the Modulation Coding Scheme (MCS), TB CQI and TB size of each UE. First eNB estimates the Signal to Interference plus Noise Ratio (SINR) of each UE on its allocated RBs based on CQI on its allocated RBs fed back by each UE, and then eNB calculates the effective SINRSIN
R
eff of each UE on each MCS from high order to low order, using effective SINR mapping algorithm, and estimates BLER of each UE on each MCS. For an MCS, if BLER of the UE is less than 0.1, the MCS is chosen as the UE’s transmission format.TB CQI of each UE is easy to obtain according to the relationship between MCS and TB CQI.The size of TB data eNB sends to UE is calculated by(4)
TB
_
Size
=
N
RB
·
N
symb
·
N
subcarri
·
M
·
CR
,where TB
_
Size denotes TB size of the UE, and N
RB denotes the number of RBs eNB allocates to the UE, and N
symb denotes the number of OFDM symbols of an RB in every TTI, and N
subcarri denotes the number of subcarriers of an RB, and M and CR, respectively, denote modulation order and coding rate which can be obtain from MCS.


## 2.1. System Model

We consider downlink transmission in a two-hop relay-enhanced cellular system withL eNBs. The coverage area of eNB is macrocell (or cell), where each macrocell consists of three sectors, and there are some RNs deployed in each sector. As shown in Figure 1, RNs are uniformly deployed in the macrocell, and there are a number of RNs per sector where the angle between RN and sector antenna is 30 degrees and each RN is located at 2/3 of the radius of the macrocell.We use multiple access technology based on orthogonal frequency division multiplexing access (OFDMA), and transmission resource of system consists of the following three aspects: time domain, frequency domain, and spatial domain. Spatial resource is divided into different layer based on Multi Input Multi Output (MIMO). The basic time-frequency resource unit used for scheduling is called Resource Block (RB). The scheduling cycle is a Transmission Time Interval (TTI) which is one subframe time.We assume that RN operates in half-duplex manner; that is, RN cannot transmit and receive packets simultaneously. Therefore eNB-RN transmission and RN-relay UE transmission cannot be performed at the same time [19], while eNB-macro-UE transmission can be simultaneous with eNB-RN transmission or RN-relay UE transmission. The timing relationship of direct subframe, backhaul subframe, and access subframe is shown in Figure 2.Figure 2
Time relationship of the three subframes.In backhaul subframe, eNB schedules RBs to its subordinate RNs and macro-UEs. In access subframe, RN schedules RBs to its subordinate relay UEs, and eNB schedules RBs to its subordinate macro-UEs. Note that eNB can make its scheduling decisions for macro-UEs simply using Proportional Fair (PF) scheduling in access subframe, which lies outside research scope of this paper.In this paper, full buffer model is considered for eNB. Thus there are always enough downlink packets for macro-UEs and RNs. RN decodes and forwards packets received from eNB to relay UEs.


## 2.2. Preliminary Techniques

PF scheduling algorithm is the basis of our proposed TBS algorithm. As a preliminary study, we first briefly introduce PF scheduling algorithm applied to traditional cellular system only with eNBs and UEs. In PF scheduling, eNB first calculates the PF priority value of each UE on each RB of the RB set to be allocated. Then it finds the maximum priority value and its corresponding RB and UE and allocates the RB to the UE. After an RB has been allocated, it should be deleted from the RB set to be allocated, ensuring that an RB can only be allocated to only one UE.The PF priority value of UEu on RB k in TTI t is defined as follows [20]:(1)
P
u
k
t
=
r
u
k
t
t
c
-
1
R
u
t
-
1
¯
+
∑
k
′
=
1
K
x
u
k
′
t
r
u
k
′
t
,where r
u
k
(
t
) denotes the potential data rate of UE u on RB k in TTI t, indicating the current link quality which is determined by Channel Quality Indicator (CQI) of RB k fed back by UE u, and t
c is the average window size. x
u
k
′
(
t
) denotes whether RB k
′ has been allocated for UE u in TTI t, which is defined as follows:(2)
x
u
k
′
(
t
)
=
1
RB
k
′
has
been
allocated
for
UE
u
in
TTI
t
0
otherwise
.In (1), R
u
(
t
)
¯ denotes the average throughput of UE u up to TTI t whose recursive computation formula is given by(3)
R
u
(
t
)
¯
=
1
-
1
t
c
R
u
(
t
-
1
)
¯
+
1
t
c
R
u
t
,where R
u
(
t
) denotes the throughput of UE u in TTI t.The flow chart of PF algorithm for allocating RBs is shown in Figure3.Figure 3
Flow chart of PF algorithm for allocating RBs.After eNB allocates all RBs to its subordinate UEs, eNB should calculate the Modulation Coding Scheme (MCS), TB CQI and TB size of each UE. First eNB estimates the Signal to Interference plus Noise Ratio (SINR) of each UE on its allocated RBs based on CQI on its allocated RBs fed back by each UE, and then eNB calculates the effective SINRSIN
R
eff of each UE on each MCS from high order to low order, using effective SINR mapping algorithm, and estimates BLER of each UE on each MCS. For an MCS, if BLER of the UE is less than 0.1, the MCS is chosen as the UE’s transmission format.TB CQI of each UE is easy to obtain according to the relationship between MCS and TB CQI.The size of TB data eNB sends to UE is calculated by(4)
TB
_
Size
=
N
RB
·
N
symb
·
N
subcarri
·
M
·
CR
,where TB
_
Size denotes TB size of the UE, and N
RB denotes the number of RBs eNB allocates to the UE, and N
symb denotes the number of OFDM symbols of an RB in every TTI, and N
subcarri denotes the number of subcarriers of an RB, and M and CR, respectively, denote modulation order and coding rate which can be obtain from MCS.


## 3. Two-Hop Balanced Distributed Scheduling (TBS)

In this section, we elaborate our proposed TBS. We first introduce the scheduling process for the first and second hop, respectively, and then present the design of relay UE’s ACK feedback mechanism.


### 3.1. Scheduling for the First Hop

The scheduling for the first hop is performed to improve resource utilization, fairness of RB allocation, and the throughput of backhaul link and direct link, by achieving a balance between backhaul link throughput and access link throughput. In scheduling for the first hop, eNB first allocates RBs to RNs and macro-UEs using PF and then adaptively adjusts the number of RBs allocated to each RN by exploiting the cache information of the RN. After that, the eNB reallocates some RBs to each RN and macro-UEs. The flow chart of scheduling for the first hop is shown in Figure4.Figure 4
Flow chart of scheduling for the first hop.In the following, we describe the details of eNB scheduling for RNs and macro-UEs in the first hop.Step 1.
eNB allocates all RBs to its subordinate RNs (the RN to which there are UEs attached) and macro-UEs using PF.Step 2.
Based on the number of the RBs that eNB allocates to RNr (r
=
1
,
…
,
N, N is the number of RNs deployed in each sector) in Step 1, eNB increases or decreases the number of RBs allocated to RN r appropriately on the basis of α
overflow
r, which is defined as(5)
α
overflow
r
=
1
the
amount
of
data
which
can
be
transmitted
by
RN
r
>
the
amount
of
data
in
buffer
of
RN
r
0
the
amount
of
data
which
can
be
transmitted
by
RN
r
≤
the
amount
of
data
in
buffer
of
RN
r
,where the data which can be transmitted by RN r is the TB data of all relay UEs attached to RN r, and the data in buffer of RN r mostly consists of the data received from eNB correctly by RN r. Because the amount of data which can be transmitted by RN r reflects the quality of relay UEs’ access links attached to RN r and the amount of data in buffer of RN r reflects the quality of RN r’s backhaul link, α
overflow
r indicates the relationship between the quality of RN r’s backhaul link and the quality of relay UEs’ access links attached to RN r. RN r calculates α
overflow
r in every access downlink subframe and feedbacks it to eNB in access uplink subframe.The eNB adjusts the number of RBs allocated to RNr on the basis of the latest k (k is a parameter related to the quality of RN r’s backhaul link and the quality of relay UEs’ access links attached to RN r) α
overflow
r cached in RN r, in order to adjust the throughput of RN r’s backhaul link and further balance the throughput of backhaul link and access link. The formula of eNB adjusting the number of RBs allocated to RN r is given by(6)
N
RB
i
(
r
)
=
M
RB
PF
(
r
)
+
N
RB
i
-
1
r
2
hhhhhh
the
latest
k
α
overflow
r
are
all
1
λ
*
max
⁡
M
RB
PF
(
r
)
-
N
RB
i
-
1
r
,
0
hhhhhh
the
latest
k
α
overflow
r
are
all
0
M
RB
PF
(
r
)
otherwise
,where N
RB
i
(
r
) is the actual number of RBs allocated to RN r in the i backhaul downlink subframe, and M
RB
PF
(
r
) denotes the number of RBs which eNB allocates to RN in Step 1, and λ denotes whether the actual number of RBs allocated to RN r in the i
-
1 backhaul downlink subframe is equal to 0, which is defined as (7)
λ
=
0
N
RB
i
-
1
(
r
)
=
0
1
N
RB
i
-
1
(
r
)
≠
0
.Step 3.
According to the increased or decreased number of RBs allocated to RNr calculated in Step 2, eNB reallocates some RBs to RN r and macro-UEs in order to improve resource utilization, fairness of RB allocation, and throughput of backhaul link and access link. The pseudocode of this process is shown in Algorithm 1.Algorithm 1:The pseudocode of eNB re_allocating some RBs for RN and macro UE.
eNB re-allocates some RBs to RN
r
and macro UEs
ifN
RB
i
(
r
)
>
M
RB
PF
(
r
)
set free all RBs occupied by macro UEs as the RB setS
1 to be allocated for RN r;
fork
=
1
:
N
RB
i
(
r
)
-
M
RB
PF
(
r
)
k
*
=
arg
⁡
max
⁡
∀
k
′
∈
S
1
CQ
I
r
k
′; CQ
I
r
k
′denotes CQI of RN r on RB
k
′
RB
k
*→RN r;
S
1
=
S
1
-
{
k
*
};
end
allocate the remaining RBs inS
1 for the macro UEs occupying them before;
else ifN
RB
i
(
r
)
<
M
RB
PF
(
r
)
set freeM
RB
PF
(
r
)
-
N
RB
i
(
r
) RBs with the minimum CQI of RN r as the RB set S
2 to be allocated for macro UEs;
fork
=
1
:
M
RB
PF
(
r
)
-
N
RB
i
(
r
)
(
u
*
,
k
*
)
=
arg
⁡
max
⁡
∀
k
′
∈
S
2
∀
u
∈
U
CQ
I
u
k
′; U is the set of macro UEs attaching to eNB
RB
k
*→macro UE u
*;
S
2
=
S
2
-
{
k
*
};
end
EndStep 4.
Calculate the number of RBs allocated to each RN and macro-UE after the reallocation.Step 5.
Calculate MCS, TB CQI, and TB size of each RN and macro-UE using the method elaborated in Section2.2.


### 3.2. Scheduling for the Second Hop

The scheduling for the second hop is performed to avoid a waste of RB resource and increase the UE fairness. In scheduling for the second hop, first RN allocates RBs to relay UEs using PF and calculates MCS, TB CQI, and TB size of each relay UE and then recalculates the TB size of each relay UE on the basis of the amount of data in RN buffer. Next RN recalculates the number of RBs to be allocated to relay UE based on the new TB size of relay UE and finally reallocates RBs to relay UEs. The flow chart of scheduling for the second hop is shown in Figure5.Figure 5
Flow chart of scheduling for the second hop.In the following, we describe the details of RN scheduling for relay UEs in the second hop.Step 1.
RN allocates all RBs to its subordinate relay UEs using PF and calculates MCS and TB size of every scheduled relay UE using the method elaborated in Section2.2.Step 2.
We first consider the case that the amount of data which can be transmitted by RN is larger than the amount of data in RN buffer. As RN can only forward packets received from eNB correctly to relay UEs without generating packets, RN recalculates the TB size of relay UEu (u
=
1
,
…
,
U, U is the number of scheduled relay UEs attached to the RN) based on the amount of data in RN buffer as follows:(8)
new
_
TBsize
u
=
TBsize
u
∑
u
′
=
1
U
TBsize
u
′
*
Rbfrsize
,where new
_
TBsize
(
u
) is the newly calculated TB size of relay UE u, and TBsize
(
u
) denotes TB size of relay UE u calculated in Step 1, and Rbfrsize denotes the amount of data in RN buffer.
For the case that the amount of data which can be transmitted by RN is less than or equal to the amount of data in RN buffer, indicating that the data in RN buffer is sufficient for transmissions from RN to its subordinate relay UEs, exit the scheduling process for the second hop regardless of Step3.Step 3.
RN recalculates the number of RBs to be allocated to relay UEu based on the newly calculated TB size of relay UE u. It can be seen from Step 2 that the newly calculated TB size of relay UE u is less than the original TB size of relay UE u, so less RBs need to be used for data transmission from RN to relay UE u. So RN recalculates the number of RBs to be allocated to relay UE u in order to avoid a waste of RB resource and increase UE fairness, the formula of which is given by (9)
N
RB
u
=
new
_
TBsize
u
N
symb
·
N
subcarri
·
M
·
CR
,where N
RB
(
u
) is the newly calculated number of RBs to be allocated to relay UE u, and N
symb, N
subcarri, M, and CR are all the same meaning as in  (4).Step 4.
RN reallocates all RBs to its subordinate relay UEs, the flow chart of which is shown in Figure6. RN finds the maximum CQI of all relay UEs on all RBs and the RB k and relay UE u corresponding to the maximum CQI. Then RN allocates RB k with the maximum CQI to relay UE u, which also means that the relay UE with the best access link quality is given priority to be allocated resource, which can improve the throughput of access link.Figure 6
Flow chart that an RN reallocates RBs to relay UEs using the principle of Max CQI.


### 3.3. Relay UE’s ACK Feedback Principle

The amount of data in RN bufferRbfrsize is used to be calculated α
overflow
r in the scheduling for the first hop and is used to be recalculated the TB size of relay UE u in the scheduling for the second hop; therefore we propose relay UE’s ACK feedback principle to calculate the amount of data in RN buffer in TBS. The specific steps of the mechanism are as follows: ① save the data received from eNB correctly by RN in RN buffer in backhaul downlink subframe; ② after relay UEs are scheduled in access downlink subframe, subtract the sum of the relay UEs’ TB size from RN buffer according to (10)
Rbfrsize
=
Rbfrsize
-
∑
u
=
1
U
new
_
TBsize
(
u
)
.Note that the relay UEs’ TB data is not indeed deleted now. When the ACK feedback of relay UEs is received by RN in access uplink subframe, the data transmitted correctly will be deleted, and the data that is not correctly received will be retransmitted. ③ After RN receives the ACK feedback of relay UEs in access uplink subframe, the data that is not correctly transmitted will be added to RN buffer again according to (11)
Rbfrsize
=
Rbfrsize
+
∑
u
=
1
U
1
-
ACK
u
new
_
TBsize
(
u
)
,where ACK
(
u
) denotes the ACK feedback received from relay UE u by RN, which is defined as (12)
ACK
(
u
)
=
1
transmit
correctly
0
transmit
falsely
.RN can retransmit the lost data to every relay UE using relay UE’s ACK feedback mechanism, which can further improve the throughput of access link.


## 3.1. Scheduling for the First Hop

The scheduling for the first hop is performed to improve resource utilization, fairness of RB allocation, and the throughput of backhaul link and direct link, by achieving a balance between backhaul link throughput and access link throughput. In scheduling for the first hop, eNB first allocates RBs to RNs and macro-UEs using PF and then adaptively adjusts the number of RBs allocated to each RN by exploiting the cache information of the RN. After that, the eNB reallocates some RBs to each RN and macro-UEs. The flow chart of scheduling for the first hop is shown in Figure4.Figure 4
Flow chart of scheduling for the first hop.In the following, we describe the details of eNB scheduling for RNs and macro-UEs in the first hop.Step 1.
eNB allocates all RBs to its subordinate RNs (the RN to which there are UEs attached) and macro-UEs using PF.Step 2.
Based on the number of the RBs that eNB allocates to RNr (r
=
1
,
…
,
N, N is the number of RNs deployed in each sector) in Step 1, eNB increases or decreases the number of RBs allocated to RN r appropriately on the basis of α
overflow
r, which is defined as(5)
α
overflow
r
=
1
the
amount
of
data
which
can
be
transmitted
by
RN
r
>
the
amount
of
data
in
buffer
of
RN
r
0
the
amount
of
data
which
can
be
transmitted
by
RN
r
≤
the
amount
of
data
in
buffer
of
RN
r
,where the data which can be transmitted by RN r is the TB data of all relay UEs attached to RN r, and the data in buffer of RN r mostly consists of the data received from eNB correctly by RN r. Because the amount of data which can be transmitted by RN r reflects the quality of relay UEs’ access links attached to RN r and the amount of data in buffer of RN r reflects the quality of RN r’s backhaul link, α
overflow
r indicates the relationship between the quality of RN r’s backhaul link and the quality of relay UEs’ access links attached to RN r. RN r calculates α
overflow
r in every access downlink subframe and feedbacks it to eNB in access uplink subframe.The eNB adjusts the number of RBs allocated to RNr on the basis of the latest k (k is a parameter related to the quality of RN r’s backhaul link and the quality of relay UEs’ access links attached to RN r) α
overflow
r cached in RN r, in order to adjust the throughput of RN r’s backhaul link and further balance the throughput of backhaul link and access link. The formula of eNB adjusting the number of RBs allocated to RN r is given by(6)
N
RB
i
(
r
)
=
M
RB
PF
(
r
)
+
N
RB
i
-
1
r
2
hhhhhh
the
latest
k
α
overflow
r
are
all
1
λ
*
max
⁡
M
RB
PF
(
r
)
-
N
RB
i
-
1
r
,
0
hhhhhh
the
latest
k
α
overflow
r
are
all
0
M
RB
PF
(
r
)
otherwise
,where N
RB
i
(
r
) is the actual number of RBs allocated to RN r in the i backhaul downlink subframe, and M
RB
PF
(
r
) denotes the number of RBs which eNB allocates to RN in Step 1, and λ denotes whether the actual number of RBs allocated to RN r in the i
-
1 backhaul downlink subframe is equal to 0, which is defined as (7)
λ
=
0
N
RB
i
-
1
(
r
)
=
0
1
N
RB
i
-
1
(
r
)
≠
0
.Step 3.
According to the increased or decreased number of RBs allocated to RNr calculated in Step 2, eNB reallocates some RBs to RN r and macro-UEs in order to improve resource utilization, fairness of RB allocation, and throughput of backhaul link and access link. The pseudocode of this process is shown in Algorithm 1.Algorithm 1:The pseudocode of eNB re_allocating some RBs for RN and macro UE.
eNB re-allocates some RBs to RN
r
and macro UEs
ifN
RB
i
(
r
)
>
M
RB
PF
(
r
)
set free all RBs occupied by macro UEs as the RB setS
1 to be allocated for RN r;
fork
=
1
:
N
RB
i
(
r
)
-
M
RB
PF
(
r
)
k
*
=
arg
⁡
max
⁡
∀
k
′
∈
S
1
CQ
I
r
k
′; CQ
I
r
k
′denotes CQI of RN r on RB
k
′
RB
k
*→RN r;
S
1
=
S
1
-
{
k
*
};
end
allocate the remaining RBs inS
1 for the macro UEs occupying them before;
else ifN
RB
i
(
r
)
<
M
RB
PF
(
r
)
set freeM
RB
PF
(
r
)
-
N
RB
i
(
r
) RBs with the minimum CQI of RN r as the RB set S
2 to be allocated for macro UEs;
fork
=
1
:
M
RB
PF
(
r
)
-
N
RB
i
(
r
)
(
u
*
,
k
*
)
=
arg
⁡
max
⁡
∀
k
′
∈
S
2
∀
u
∈
U
CQ
I
u
k
′; U is the set of macro UEs attaching to eNB
RB
k
*→macro UE u
*;
S
2
=
S
2
-
{
k
*
};
end
EndStep 4.
Calculate the number of RBs allocated to each RN and macro-UE after the reallocation.Step 5.
Calculate MCS, TB CQI, and TB size of each RN and macro-UE using the method elaborated in Section2.2.


## 3.2. Scheduling for the Second Hop

The scheduling for the second hop is performed to avoid a waste of RB resource and increase the UE fairness. In scheduling for the second hop, first RN allocates RBs to relay UEs using PF and calculates MCS, TB CQI, and TB size of each relay UE and then recalculates the TB size of each relay UE on the basis of the amount of data in RN buffer. Next RN recalculates the number of RBs to be allocated to relay UE based on the new TB size of relay UE and finally reallocates RBs to relay UEs. The flow chart of scheduling for the second hop is shown in Figure5.Figure 5
Flow chart of scheduling for the second hop.In the following, we describe the details of RN scheduling for relay UEs in the second hop.Step 1.
RN allocates all RBs to its subordinate relay UEs using PF and calculates MCS and TB size of every scheduled relay UE using the method elaborated in Section2.2.Step 2.
We first consider the case that the amount of data which can be transmitted by RN is larger than the amount of data in RN buffer. As RN can only forward packets received from eNB correctly to relay UEs without generating packets, RN recalculates the TB size of relay UEu (u
=
1
,
…
,
U, U is the number of scheduled relay UEs attached to the RN) based on the amount of data in RN buffer as follows:(8)
new
_
TBsize
u
=
TBsize
u
∑
u
′
=
1
U
TBsize
u
′
*
Rbfrsize
,where new
_
TBsize
(
u
) is the newly calculated TB size of relay UE u, and TBsize
(
u
) denotes TB size of relay UE u calculated in Step 1, and Rbfrsize denotes the amount of data in RN buffer.
For the case that the amount of data which can be transmitted by RN is less than or equal to the amount of data in RN buffer, indicating that the data in RN buffer is sufficient for transmissions from RN to its subordinate relay UEs, exit the scheduling process for the second hop regardless of Step3.Step 3.
RN recalculates the number of RBs to be allocated to relay UEu based on the newly calculated TB size of relay UE u. It can be seen from Step 2 that the newly calculated TB size of relay UE u is less than the original TB size of relay UE u, so less RBs need to be used for data transmission from RN to relay UE u. So RN recalculates the number of RBs to be allocated to relay UE u in order to avoid a waste of RB resource and increase UE fairness, the formula of which is given by (9)
N
RB
u
=
new
_
TBsize
u
N
symb
·
N
subcarri
·
M
·
CR
,where N
RB
(
u
) is the newly calculated number of RBs to be allocated to relay UE u, and N
symb, N
subcarri, M, and CR are all the same meaning as in  (4).Step 4.
RN reallocates all RBs to its subordinate relay UEs, the flow chart of which is shown in Figure6. RN finds the maximum CQI of all relay UEs on all RBs and the RB k and relay UE u corresponding to the maximum CQI. Then RN allocates RB k with the maximum CQI to relay UE u, which also means that the relay UE with the best access link quality is given priority to be allocated resource, which can improve the throughput of access link.Figure 6
Flow chart that an RN reallocates RBs to relay UEs using the principle of Max CQI.


## 3.3. Relay UE’s ACK Feedback Principle

The amount of data in RN bufferRbfrsize is used to be calculated α
overflow
r in the scheduling for the first hop and is used to be recalculated the TB size of relay UE u in the scheduling for the second hop; therefore we propose relay UE’s ACK feedback principle to calculate the amount of data in RN buffer in TBS. The specific steps of the mechanism are as follows: ① save the data received from eNB correctly by RN in RN buffer in backhaul downlink subframe; ② after relay UEs are scheduled in access downlink subframe, subtract the sum of the relay UEs’ TB size from RN buffer according to (10)
Rbfrsize
=
Rbfrsize
-
∑
u
=
1
U
new
_
TBsize
(
u
)
.Note that the relay UEs’ TB data is not indeed deleted now. When the ACK feedback of relay UEs is received by RN in access uplink subframe, the data transmitted correctly will be deleted, and the data that is not correctly received will be retransmitted. ③ After RN receives the ACK feedback of relay UEs in access uplink subframe, the data that is not correctly transmitted will be added to RN buffer again according to (11)
Rbfrsize
=
Rbfrsize
+
∑
u
=
1
U
1
-
ACK
u
new
_
TBsize
(
u
)
,where ACK
(
u
) denotes the ACK feedback received from relay UE u by RN, which is defined as (12)
ACK
(
u
)
=
1
transmit
correctly
0
transmit
falsely
.RN can retransmit the lost data to every relay UE using relay UE’s ACK feedback mechanism, which can further improve the throughput of access link.


## 4. Simulation and Evaluation

In this section, we use simulation experiments to demonstrate the effectiveness of proposed scheduling algorithms. We set up LTE-A TDD downlink relay system simulation platform based on Vienna LTE simulation platform. To comprehensively evaluate the performance of our proposed scheduling algorithm, we implement TBS, ADPF, and PF in LTE-A TDD downlink relay system simulation platform, and we compare and evaluate the performance of TBS, ADPF, and PF in terms of a number of metrics.


### 4.1. Performance Metrics

(1) Average Sector Throughput (
T
s
).
T
s is defined as the average sum of direct and access link throughput in a sector.(2) UE Throughput Fairness Index (
F
T
). Similar to Jain fairness index [21], F
T is defined as (13)
F
T
=
∑
u
=
1
U
x
u
2
U
∑
u
=
1
U
x
u
2
,where U denotes the number of UEs, and x
u denotes the throughput of UE u. F
T is between 0 and 1, and the larger the F
T is, the fairer the throughput of UE is.(3) UE RB Fairness Index (
F
R
B
). Similar to Jain fairness index [21], F
RB is defined as (14)
F
RB
=
∑
u
=
1
U
k
u
2
U
∑
u
=
1
U
k
u
2
,where k
u denotes the number of RBs allocated by UE u in one TTI. F
RB is between 0 and 1, and the larger the F
RB is, the fairer the number of RB occupied by UE is.(4) Data Forwarding Ratio of RN (
η
). In relay-enhanced cellular system, RN does not generate data. Instead, it just forwards the packets received from eNB correctly to relay UEs. Thus access link throughput is less than or equal to backhaul link throughput in each sector. When access link throughput is equal to backhaul link throughput, indicating that all packets received from eNB correctly by RN have been forwarded to relay UEs correctly, η reaches the maximum 1. The larger the η is, the better the balance of backhaul link throughput and access link throughput is. η is defined by(15)
η
=
T
a
T
b
,where T
a denotes access link throughput in average every sector, and T
b denotes backhaul link throughput in average every sector.


### 4.2. Simulation Parameter Settings

In this paper, distance-dependent path loss, shadowing fading and small-scale fading of direct, backhaul and access link models defined in 3GPP TR 36.814 [22]. TDD frame structure [23] is shown in Figure 7.Figure 7
TDD frame structure.In Figure7, Db denotes downlink backhaul subframe; Da denotes downlink access subframe; Ub denotes uplink backhaul subframe; Ua denotes uplink access subframe; S denotes special subframe; downlink backhaul subframe and downlink access subframe can both be used as downlink direct subrame; uplink backhaul subframe and uplink access subframe can both be used as uplink direct subrame.Other simulation parameters are listed in Table1.Table 1
Simulation parameters.
Parameters
Values
Cellular layout
Hexagonal grid, 7 eNB
RN layout
1, 2 and 4 RN per sector
Intersite distance
500 m
Carrier frequency
2 GHz
System bandwidth
10 MHz
Transport model
2 * 2 * 2OLSM
UEs per sector
20
UE speed
3 km/h
UE access selection algorithm
Algorithm based on spectral efficiency [24]
Tx power
eNB: 46 dBm; RN: 30 dBm
Noise figure
RN: 5 dB; UE: 9 dB
Thermal noise density
−174 dBm/Hz
Simulation time
20 drops, 500 TTIs per drop


### 4.3. Numerical Results and Discussions

In our simulations, we consider a cell with 3 sectors and there are a number of relays (from 1 to 4 relays) deployed in each sector, as shown in Figure1. Other system parameters are listed in Table 1. In the first experiment, we compare the throughput of our proposed TBS with that of PF and ADPF, when there are different numbers of relays in each sector. Figure 8 compares the average sector throughput of PF, ADPF, and TBS for different number of RNs in a sector.Figure 8
Average sector throughput.From Figure8, we can observe that the average sector throughput T
s of each scheduling algorithm increases with the number of RNs in a sector. When 1 RN is deployed in a sector, T
s of TBS is the maximum, and T
s of PF is the minimum. When 2 or 4 RNs are deployed in a sector, T
s of ADPF is the highest, and T
s of PF is still the lowest. The difference of throughput increases with the number of RNs. Specifically, when 1 RN is deployed in a sector, T
s of TBS is higher than that of ADPF and PF by 1.16% and 4.09%, respectively. When 2 or 4 RNs are deployed in a sector, T
s of TBS is slightly lower than that of ADPF. This is because ADPF gives priority to relay UEs. The access link throughput increases significantly with the number of RNs, resulting in a poor fairness of ADPF. When there exists RNs, T
s of TBS is always higher than that of PF, and the more the number of RNs, the larger the difference of throughput. This is because TBS can achieve the balance of throughput in backhaul link and access link and thus improve resource utilization. T
s of TBS is higher than that of PF by 9.80% in 4 RNs per sector. From this experiment, we can conclude that our proposed TBS can effectively improve system throughput by means of adjusting the number of RBs occupied by RN in the first hop scheduling adaptively.In the second experiment, we examine the advantages of TBS in data forwarding ratio of RN. Figure9 compares the data forwarding ratio η of RN of PF, ADPF, and TBS for different number of RNs in a sector.Figure 9
Data forwarding ratio of RN.From Figure9, we can observe that η of RN of TBS is significantly higher than that of PF and ADPF and is close to 1. This indicates that TBS can achieve a good balance between backhaul and access link throughput.In the third and fourth experiment, we, respectively, examine the advantages of TBS in UE throughput fairness index and UE RB fairness index. Figures10 and 11, respectively, compare UE throughput fairness index and UE RB fairness index of PF, ADPF, and TBS for different number of RNs in a sector.Figure 10
UE throughput fairness index.Figure 11
UE RB fairness index.In Figures10 and 11, we can observe that UE throughput fairness index F
T and UE RB fairness index F
RB of TBS are always greater than that of ADPF and PF, respectively. F
T of TBS is greater by up to 100.49% than that of ADPF for different number of RNs in a sector, and F
RB of TBS is greater by up to 168.84% than that of ADPF for different number of RNs in a sector. This is because ADPF gives priority to allocating RB for RN in order to increase throughput of relay UE regardless of fairness between relay UE and macro-UE, while TBS avoids the waste of RB and further increases fairness of RB between relay UE and macro-UE by means of recalculating the number of RBs allocated to each relay UE based on relay UE’s TB size in the scheduling for the second hop, and at the same time TBS can balance the number of RBs occupied by backhaul link and direct link in the first hop scheduling. Moreover, F
T of TBS is greater by up to 7.46% than that of PF for different number of RNs in a sector, and UE RB fairness index of TBS is increased up by 123.07% compared with PF at most for different number of RNs in a sector. F
RB of TBS fluctuate slightly with the number of RNs, while F
RB of TBS decreases with the number of RNs, mainly due to the increasing number of RBs allocated to relay UEs.


## 4.1. Performance Metrics

(1) Average Sector Throughput (
T
s
).
T
s is defined as the average sum of direct and access link throughput in a sector.(2) UE Throughput Fairness Index (
F
T
). Similar to Jain fairness index [21], F
T is defined as (13)
F
T
=
∑
u
=
1
U
x
u
2
U
∑
u
=
1
U
x
u
2
,where U denotes the number of UEs, and x
u denotes the throughput of UE u. F
T is between 0 and 1, and the larger the F
T is, the fairer the throughput of UE is.(3) UE RB Fairness Index (
F
R
B
). Similar to Jain fairness index [21], F
RB is defined as (14)
F
RB
=
∑
u
=
1
U
k
u
2
U
∑
u
=
1
U
k
u
2
,where k
u denotes the number of RBs allocated by UE u in one TTI. F
RB is between 0 and 1, and the larger the F
RB is, the fairer the number of RB occupied by UE is.(4) Data Forwarding Ratio of RN (
η
). In relay-enhanced cellular system, RN does not generate data. Instead, it just forwards the packets received from eNB correctly to relay UEs. Thus access link throughput is less than or equal to backhaul link throughput in each sector. When access link throughput is equal to backhaul link throughput, indicating that all packets received from eNB correctly by RN have been forwarded to relay UEs correctly, η reaches the maximum 1. The larger the η is, the better the balance of backhaul link throughput and access link throughput is. η is defined by(15)
η
=
T
a
T
b
,where T
a denotes access link throughput in average every sector, and T
b denotes backhaul link throughput in average every sector.


## 4.2. Simulation Parameter Settings

In this paper, distance-dependent path loss, shadowing fading and small-scale fading of direct, backhaul and access link models defined in 3GPP TR 36.814 [22]. TDD frame structure [23] is shown in Figure 7.Figure 7
TDD frame structure.In Figure7, Db denotes downlink backhaul subframe; Da denotes downlink access subframe; Ub denotes uplink backhaul subframe; Ua denotes uplink access subframe; S denotes special subframe; downlink backhaul subframe and downlink access subframe can both be used as downlink direct subrame; uplink backhaul subframe and uplink access subframe can both be used as uplink direct subrame.Other simulation parameters are listed in Table1.Table 1
Simulation parameters.
Parameters
Values
Cellular layout
Hexagonal grid, 7 eNB
RN layout
1, 2 and 4 RN per sector
Intersite distance
500 m
Carrier frequency
2 GHz
System bandwidth
10 MHz
Transport model
2 * 2 * 2OLSM
UEs per sector
20
UE speed
3 km/h
UE access selection algorithm
Algorithm based on spectral efficiency [24]
Tx power
eNB: 46 dBm; RN: 30 dBm
Noise figure
RN: 5 dB; UE: 9 dB
Thermal noise density
−174 dBm/Hz
Simulation time
20 drops, 500 TTIs per drop


## 4.3. Numerical Results and Discussions

In our simulations, we consider a cell with 3 sectors and there are a number of relays (from 1 to 4 relays) deployed in each sector, as shown in Figure1. Other system parameters are listed in Table 1. In the first experiment, we compare the throughput of our proposed TBS with that of PF and ADPF, when there are different numbers of relays in each sector. Figure 8 compares the average sector throughput of PF, ADPF, and TBS for different number of RNs in a sector.Figure 8
Average sector throughput.From Figure8, we can observe that the average sector throughput T
s of each scheduling algorithm increases with the number of RNs in a sector. When 1 RN is deployed in a sector, T
s of TBS is the maximum, and T
s of PF is the minimum. When 2 or 4 RNs are deployed in a sector, T
s of ADPF is the highest, and T
s of PF is still the lowest. The difference of throughput increases with the number of RNs. Specifically, when 1 RN is deployed in a sector, T
s of TBS is higher than that of ADPF and PF by 1.16% and 4.09%, respectively. When 2 or 4 RNs are deployed in a sector, T
s of TBS is slightly lower than that of ADPF. This is because ADPF gives priority to relay UEs. The access link throughput increases significantly with the number of RNs, resulting in a poor fairness of ADPF. When there exists RNs, T
s of TBS is always higher than that of PF, and the more the number of RNs, the larger the difference of throughput. This is because TBS can achieve the balance of throughput in backhaul link and access link and thus improve resource utilization. T
s of TBS is higher than that of PF by 9.80% in 4 RNs per sector. From this experiment, we can conclude that our proposed TBS can effectively improve system throughput by means of adjusting the number of RBs occupied by RN in the first hop scheduling adaptively.In the second experiment, we examine the advantages of TBS in data forwarding ratio of RN. Figure9 compares the data forwarding ratio η of RN of PF, ADPF, and TBS for different number of RNs in a sector.Figure 9
Data forwarding ratio of RN.From Figure9, we can observe that η of RN of TBS is significantly higher than that of PF and ADPF and is close to 1. This indicates that TBS can achieve a good balance between backhaul and access link throughput.In the third and fourth experiment, we, respectively, examine the advantages of TBS in UE throughput fairness index and UE RB fairness index. Figures10 and 11, respectively, compare UE throughput fairness index and UE RB fairness index of PF, ADPF, and TBS for different number of RNs in a sector.Figure 10
UE throughput fairness index.Figure 11
UE RB fairness index.In Figures10 and 11, we can observe that UE throughput fairness index F
T and UE RB fairness index F
RB of TBS are always greater than that of ADPF and PF, respectively. F
T of TBS is greater by up to 100.49% than that of ADPF for different number of RNs in a sector, and F
RB of TBS is greater by up to 168.84% than that of ADPF for different number of RNs in a sector. This is because ADPF gives priority to allocating RB for RN in order to increase throughput of relay UE regardless of fairness between relay UE and macro-UE, while TBS avoids the waste of RB and further increases fairness of RB between relay UE and macro-UE by means of recalculating the number of RBs allocated to each relay UE based on relay UE’s TB size in the scheduling for the second hop, and at the same time TBS can balance the number of RBs occupied by backhaul link and direct link in the first hop scheduling. Moreover, F
T of TBS is greater by up to 7.46% than that of PF for different number of RNs in a sector, and UE RB fairness index of TBS is increased up by 123.07% compared with PF at most for different number of RNs in a sector. F
RB of TBS fluctuate slightly with the number of RNs, while F
RB of TBS decreases with the number of RNs, mainly due to the increasing number of RBs allocated to relay UEs.


## 5.Conclusion

In this paper, we have proposed a Two-Hop Balanced distributed Scheduling (TBS) algorithm based on PF for non-real-time data traffic in relay-enhanced cellular system. In the first hop scheduling, eNB adaptively adjusts the number of RBs occupied by backhaul and direct link based on the information of RN, and in the second hop scheduling, RN allocates RBs to all relay UEs based on the size of all relay UEs’ TB. To further improve system throughput, we have designed a relay UE’s ACK feedback principle to update the data amount of RN buffer. Simulation results have shown that UE throughput fairness, UE RB fairness, and data forwarding ratio of RN of TBS are significantly larger than that of PF and ADPF. In addition, the average sector throughput of TBS is significantly larger than that of PF. Thus our proposed TBS can improve resource utilization and achieve a good trade-off between system throughput and the fairness among all UEs by means of balancing throughput of first hop and second hop.



---

*Source: 140727-2015-03-03.xml*