Energy Efﬁcient Resource Allocation in SCFDMAUplink with Synchronous HARQ Constraints
Dan J. Dechene,
Student Member, IEEE
and Abdallah Shami,
Member, IEEE
Abstract
—In this paper we propose framework for energyefﬁcient (margin adaptive, MA) resource allocation in multiuserSCFDMA with synchronous HARQ constraints. Resource allocation is formulated as a twostage problem where resourcesare allocated in both time and frequency. To limit the impactof retransmissions on the timefrequency problem segmentation,we propose use of a block scheduling interval that ensuresuplink users do not experience ARQ blocking. We formulate theoptimal MA allocation problem under this framework and basedon its structure, we propose a variable complexity suboptimalapproach to minimize the energy in resource allocation. Resultsare presented for the energy performance relative to complexityand datarate.
Index Terms
—SCFDMA, Energy Efﬁciency, Margin Adaptive,Resource Allocation
I. I
NTRODUCTION
Energy efﬁciency is an ongoing issue in modern wirelesscommunication systems as radio resources account for a largeportion of mobile device energy consumption. As the proliferation of smaller and faster devices increases, efﬁcient use of limited battery resources becomes ever more paramount. Theradio resource allocation problem formulation of minimizingtransmission energy is known as the margin adaptive (MA)problem [1]. MA problems are wellstudied for a generalOFDM transmission systems [1], [2] however systems such asuplink in 3GPPLTE, employ localized SCFDMA at the physical layer. Implementation of localized SCFDMA suffers fromrestrictions such as contiguous frequency block allocation andlimited ﬂexibility in modulation and coding scheme (MCS)assignment ultimately limiting the applicability of traditionalMA resource allocation framework to the SCFDMA problem.In this work, we propose an uplink resource allocationscheme for localized SCFDMA with a focus on energyefﬁciency. The resource allocation problem is complicated byrestrictions imposed by synchronous hybrid automatic repeatrequest (HARQ) such as transmission at the same rate forretransmissions and by the fact that each UE can only transmita single transport block (TB) during a given scheduling frame.Our proposed resource allocation method exploits periodicityof the HARQ process in selection of a scheduling epoch toefﬁciently schedule uplink trafﬁc.The remainder of this paper is divided as follows. InSection II we overview the details of the employed uplink system model. In Section III and IV we formulate the energyoptimal and suboptimal uplink resource allocation problemwith HARQ constraints respectively. In Section V simulationresults are provided. Finally in Section VI, conclusions aredrawn on this work.
D. J. Dechene and A. Shami are with the Department of Electrical andComputer Engineering, The University of Western Ontario, London, ON,Canada (email: ddechene@ieee.org, ashami2@uwo.ca).
II. S
YSTEM
M
ODEL
In this paper we focus on multiuser SCFDMA used foruplink in LTE, [3]. There are
K
users (UEs) within a singlecell, communicating with a single base station (eNB). Sincewe focus on resource allocation within a single cell, for thepurpose of this paper, it is assumed that intercell interference isnegligible. The cell spectrum is divided into subcarriers whichare grouped into
M
resource blocks (RBs) consisting of
12
subcarriers. Without loss of generality we assume there is anInteger number (
M
) of RBs.The minimum duration of time that can be allocated to asingle UE is a scheduling block (SB). The
n
thSB falls inthe time duration
[
nT
f
,
(
n
+ 1)
T
f
)
where
T
f
is the subframeduration (equal to
1
ms) and is one RB in frequency. Resourceallocation decisions are made at each scheduling epoch. Wedeﬁne the
m
thscheduling epoch as the time duration in
[
mT
e
,
(
m
+1)
T
e
]
and each epoch consists of
T
e
/T
f
subframesin time. In this paper,
T
e
is chosen to be equal to
4
T
f
. The justiﬁcation of this selection
T
e
is discussed later. Figure 1shows an example of the uplink frame layout with relevanttime durations shown. Successful transmission are shown ingray, while failures are red. As shown retransmissions occurexactly
8
subframes following the initial transmission usingthe same number of resource blocks.Localized SCFDMA transmissions are limited to contiguityin frequency and each UE can transmit one TB using a common MCS mode per subframe
1
. Retransmissions employingHARQ must be transmitted over the same number of resourceblocks using the same MCS after exactly 8 subframes havepassed from srcinal transmission (nonadaptive HARQ).In each subcarrier, there are
N
sym
symbols in per subframe.We assume a constant amount of symbols
N
ctrl
are reservedfor control while the rest are for data transmission. We assumefor simplicity that valid TB sizes are those deﬁned by CQIvalues given in Table 7.2.31 of [4]. Consequently, the overallnumber of data bits that can be transmitted per subframe overa set
N
of RBs in frequency is given as
η
(
k,
N
) =
12(
N
sym
−
N
ctrl
)
k
·N
(1)where
k
is the spectral efﬁciency from [4],
N
is a set of RBs
1
For single layer (nonMIMO) transmissions. [4]
ARQ subframe
= ARQw = 8T
F
ARQ slot (
m)=T
e
=4T
F
F r e q u e n c y ( R B s )
LTEsubframe
(n)=T
F
Time(subframes, n)
8 subframes
Fig. 1: Frame Layout
9781612842318/11/$26.00 ©2011 IEEE
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2011 proceedings
in frequency and
 · 
is the size of a set. For
N
sym
= 14
(regular cyclic preﬁx, [4]) and assuming
N
ctrl
= 3
, the abovereduces to
η
(
k,
N
) =
132
k
·N
.The SNR of the channel between each UE and the eNBand from RB to RB is independent. A block fading model isassumed, where the channel is static for the duration of thedecision epoch and independent from epoch to epoch. Channelestimation is assumed to be errorfree and available at the eNB.The block error rate (BLER) is the average failure rate of TBs. In general this will depend on
γ
i,eff
(the effective SNRof a transmission),
T
i
(the TB size), and
k
i
(the MCS employed). There exists no analytical solution to obtain the errorrate of a coded transmission. Practically, estimates of BLERare based on receiver training/calibration. For the remainderof this paper, the measure of Information Outage probability(IOP) derived in [5] is used as a measure for BLER. TheIOP was shown to closely model BLER for moderate block lengths. Extensions are trivial when system BLER can be moreaccurately estimated and stored for a particular implementation(via proper training). From [5], we obtain
BLER
(
γ,
N
i
,T
i
)
≈
Q
⎛⎝
log(1 +
γ
−
log(2)
T
i
132
N
i

2132
N
i

γ
1+
γ
⎞⎠
(2)where
N
i
is set of RBs in use,
Q
(
·
)
is the wellknown
Q
function and
γ
i,eff
is the effective SNR.
132
N
i

and
T
i
132
N
i

corresponds to the number of modulated symbols and effectivespectral efﬁciency per allocation respectively.The measured effective SNR of a transmission is relatedto the SNR of the subchannels allocated for that particulartransmission. As in [6], the effective SNR of an SCFDMAsymbol cannot be approximated using EESM or MIESM (asin OFDM), but rather it can be computed as the average SNRover the set of subchannels or as
γ
(0)
i,eff
(
m,
N
i
) =1
N
i

k
∈N
i
γ
i,k
(
m
)
N
i

(3)where
γ
i,k
(
m
)
is the instantaneous SNR in resource block
k
seen from UE
i
relative to a reference power level
γ
0
and
N
i
is the set of RBs in the computation. The superscript
(
x
)
is used to denote the
x
thretransmission number where
0
is the initial transmission. The additional
N
i

in the aboveequation describes that power is equally allocated across theall assigned resource blocks. Further, we can model the effectof retransmissions as an increase in the measured SNR [7]. Weemploy this model with coefﬁcients for SNR gains given in Table 2 of [7]. We note however that for a given implementation,these gain factors can be obtained through receiver calibrationmeasurements. The effective SNR of retransmission
z
is thengiven as (in dB)
γ
(
z
)
i,eff,
(
dB
)
(
m,
N
i
,k
i
) =
γ
(0)
i,eff,
(
dB
)
(
m,
N
i
)+
μ
(
z,k
i
)
·
R
code
+
(
z,k
i
)
(4)where
R
code
is the code rate
×
1024
which is given in [4](
i.e.,
78
,
120
,
...
),
μ
(
z,k
i
)
and
(
z,k
i
)
are given from [7]for each retransmission and modulation scheme and where
γ
(0)
i,eff
(
m,
N
i
)
is the effective SNR for UE
i
given in (3).The required power to obtain
BLER
tgt
is then simply
P
i
=
γ
i,eff
(
N
i
,T
i
)
γ
(
z
)
i,eff
(
m,
N
i
)
(5)where
γ
i,eff
(
N
i
,T
i
)
is the
γ
argument in (2) when (2) is setequal to
BLER
tgt
for given arguments
N
i
and
T
i
.III. O
PTIMAL
A
LLOCATION
F
RAMEWORK
It is wellknown [2] that OFDM MA problems are NPhard due to Integer constraints on the subcarrier allocationvariables. The problem is further complicated in localized SCFDMA due to restrictions on contiguity of allocated resources.Nevertheless, for the interest of the reader we formulate theMA resource allocation optimization problem. Based on thecharacteristics of this problem formulation, we propose anonline suboptimal scheme that tries to minimize the averagetransmission power of each new transmission in Section IV.
A. Time Domain, TimeFrequency Domain Packet Scheduler
Recent research, particularly for LTE systems, proposessegmenting the packet scheduling problem into a timedomain packet scheduling (TDPS) and frequencydomainpacket scheduling (FDPS) problem. Such methods [8] choosea set of users at each scheduling interval to schedule (TDPS)and allocate them in frequency (FDPS) to maximize cellthroughput (rate adaptive, RA).In the energy limited regime, the goal is to minimizetransmission energy while meeting throughput requirements.In this regime, the optimal allocation for MA differs fromthat of an RA problem. As a result, RA methods are notdirectly applicable in solving the MA problem. Further, dueto limitations imposed by synchronous HARQ, the abovedescribed approaches may experience ARQ blocking since theTDPS is limited in knowledge to a single subframe in time.A simple method to eliminate ARQ blocking is to limitthe number of new transmissions a station can initiate ineach ARQ window. In synchronous HARQ, retransmissionsare limited to exactly
ARQ
w
subframes following the initialtransmission (where
ARQ
w
= 8
in LTE uplink) and themaximum number of times a packet can be transmitted is
4
. Based on these observations, the maximum number of new transmissions that any station should initiate during any
ARQ
w
subframes is
ARQ
w
/
4 = 2
to eliminate any ARQblocking.Based on this, we deﬁne an ARQ slot as the duration of time such that each UE can be allotted at most one new TB fortransmission. Consequently, each ARQ slot
m
has a durationof
4
subframes or
1
/
2
of an
ARQ
w
(
i.e.,
T
e
= 4
T
f
).We formulate the resource allocation problem by segmenting it into a TDPS and TimeFrequency Domain packetscheduler (TFDPS). At the beginning of scheduling epoch(ARQ slot)
m
, the TDPS chooses which UEs can access thechannel (and with how much data,
T
i
(
m
)
) based on the buffersand priority of each UE over ARQ slot
m
. The TFDPS thenallocates the UEs within the TimeFrequency grid of a ARQslot based on channel conditions and ongoing retransmission.
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2011 proceedings
B. TDPS Formulation
During ARQ slot
m
, the TDPS analyzes the number of resources available for transmission. Based on this informationcombined with buffer and quality of service information,the TDPS chooses the set of UEs to transmit with TB size
T
i
(
m
)
. For the remainder of this paper, we assume all UEstransmit
T
i
(
m
) =¯
T
i
bits per frame. The detailed design of an energy efﬁcient TDPS will be presented elsewhere.
C. TFDPS Formulation
The TFDPS is formulated as follows. Given a set of UEs
{
1
,
2
,...,K
}
and a set of TB sizes for each UE
{
T
1
(
m
)
,T
2
(
m
)
,...,T
K
(
m
)
}
for all
m
, the TFDPS energy minimization problem can be formulated to solve forresource assignment (
S
i,j,n
(
m
)
and
S
i,j,n
(
m
)
,
∀
i,j,n,m
),power assignment (
P
i,n
(
m
)
,
∀
i,n,m
), and rate assignment(
k
i,n
(
m
)
,
∀
i,n,m
). Here
S
i,j,n
(
m
)
and
S
i,j,n
(
m
)
are binaryindicators that denote whether a given RB
j
is allocated toa given UE
i
for both new transmissions and retransmissionsrespectively,
P
i,n
(
m
)
denotes the power allocated to UE
i
and
k
i,n
(
m
)
denotes the spectral efﬁciency of the MCS chosen forUE
i
all during subframe
n
of ARQ slot
m
.The energyoptimal objective function can be given as
min
⎛⎝
lim
t
→∞
1
t
t
m
=0
K
i
=1
M
j
=13
n
=0
α
i
(
S
i,j,n
(
m
) +
S
i,j,n
(
m
))
P
i,n
(
m
)
(6)where
α
i
is the relative importance parameter of power minimization for UE
i
and subframe
n
∈ {
0
,
1
,
2
,
3
}
within ARQslot
m
.
1) Rate Constraints:
The amount of new information thatmust be transmitted during a frame is constrained as
M
j
=13
n
=0
S
i,j,n
(
m
)
k
i,n
(
m
)
≥
T
i
(
m
)
,
∀
i,m
(7)
2) HARQ Constraints:
The ARQ constraints ensure thatresource allocation cannot occur in a subframe where a retransmission exists. This means
S
i,j,n
(
m
) = 0
,n
∈ S
i
(
m
−
2)
,
∀
i,m
, where
S
i
(
m
−
2)
is the set of subframes during ARQslot
m
−
2
whose transmissions were unsuccessful and havenot reached the maximum number of retransmissions. Further,the number of RBs allocated to a user during a retransmissionmust equal the srcinal amount of RBs assigned,
i.e.,
M
j
=1
S
i,j,n
(
m
) =
M
j
=1
(
S
i,j,n
(
m
−
2) +
S
i,j,n
(
m
−
2))
,n
∈ S
i
(
m
−
2)
,
∀
i,m
(8)
3) New Transmission Limitation:
In order to ensure ARQblocking does not occur, each station is limited to a newtransmission in a ARQ slot. This constraint is given as
n
∈S
Ci
(
m
−
2)
I
⎛⎝
M
j
=1
S
i,j,n
(
m
)
⎞⎠
≤
1
,
∀
i,m
(9)where
I
(
x
) = 0
when
x
= 0
and
1
otherwise and
S
C i
(
m
−
2)
is the complementary set of
S
i
(
m
−
2)
.
4) Allocation and Contiguity Constraints:
Additionally, localized SCFDMA is limited to RB allocations in contiguity,this constraint can be given jointly as
K
i
=1
(
S
i,j,n
(
m
) +
S
i,j,n
(
m
))
≤
1
,S
i,j,n
(
m
)
,
S
i,j,n
(
m
)
∈ {
0
,
1
}
,
∀
j,n,m
(10)ensuring only a single user can occupy an RB during an instantof time and from [9] as
S
i,j,n
(
m
)
−
S
i,j
+1
,n
(
m
) +
S
i,x,n
(
m
)
≤
1
,x
=
j
+ 2
,...,M,
∀
i,j,n
∈ S
C i
(
m
−
2)
,m
(11)
S
i,j,n
(
m
)
−
S
i,j
+1
,n
(
m
) +
S
i,x,n
(
m
)
≤
1
,x
=
j
+ 2
,...,M,
∀
i,j,n
∈ S
i
(
m
−
2)
,m
(12)
5) Power Level Constraints:
The applied power level constraints are expressed as
P
i,n
(
m
) =
γ
i,eff
(
N
i,n
,T
i
(
m
))
γ
(0)
i,eff
(
m,
N
i,n
)
,
∀
i,n
∈ S
C i
(
m
−
2)
,m
(13)
P
i,n
(
m
) =
γ
i,eff
(¯
N
i,n
,T
i
(
m
))
γ
(
z
i,n
)
i,eff
(
m,
¯
N
i,n
)
,
∀
i,n
∈ S
i
(
m
−
2)
,m
(14)where
z
i,n
(
m
)
is the retransmission number in subframe
n
forUE
i
during ARQ slot
m
and
N
i,n
=
{
j

S
i,j,n
(
m
) = 1
}
and
¯
N
i,n
=
{
j

S
i,j,n
(
m
) = 1
}
Combining (6)(14), forms the optimal TFDPS allocationfor inputs
T
i
(
m
)
,
∀
m
. In general, it is not computationallyfeasible to solve this problem for all time
m
. This is due tothe time dependance on
m
(
i.e.,
scheduling for slot
m
dependson the outcome of all previous slots
m
).IV. S
UB
O
PTIMAL
R
ESOURCE
A
LLOCATION
S
CHEME
As previously noted, it is not feasible to allocate resourcesdescribed in Section III for all time
m
in advance. Traditionalapproaches in the literature [10] have done so by exhaustively breaking the system into channel states and solving theoptimization problem as a function of these states. Howeverunlike the above methods, the SCFDMA channel has a largenumber of subchannels (RBs) resulting in a state space thatgrows exponentially with the number of RBs. This combinedwith the Integer allocation constraints above, makes solvingthe problem in this fashion infeasible.A greedy, less complex approach is to solve the problemonline at each ARQ slot
m
. The resulting problem is stillrather complex, particularly when considering the contiguityconstraints. Recent work by Wong et al. [11] exploited thesecontiguity constraints as a method of reducing the overallproblem search space to solve the SCFDMA RA allocationproblem. This was accomplished by exploiting the propertythat the number of exhaustive frequency contiguous allocations
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2011 proceedings
is signiﬁcantly less than the exhaustive allocations for a general OFDMA RA allocation problem. From the reduced searchspace, allocations were solved for each UE to maximize thecell uplink sumrate. While the exhaustive set of allocationsreduces the search space, it is still quite large, particularly fora moderate number of RBs in frequency and UEs.In the case of an MA problem (where we look to minimizeenergy used for transmission while meeting a target raterather than maximizing cell throughput), it is not necessaryto allocate all RBs as in RA problems (as with the approachin [11]), but to simply allocate those necessary to minimizetransmission power while meeting rate constraints. Further,Wong’s method suffers from needing to exhaustively considerall possible allocations while in practice, only a small numberof allocations need to be considered in the problem.In our proposed method, we adapt the approach in [11] forthe MA problem and solve the problem for each ARQ slot
m
.The proposed suboptimal algorithm provides for a varyingdegree of complexity. By including a limited number of themost energy efﬁcient allocations for a UE determined basedon channel measurements, the optimization framework canconsider a reduced search space. We denote this as the Best
N
method. The search space increases as
N
increases, andin the limiting case when
N
is large, this method obtainsthe optimal allocation at each ARQ slot
m
. The algorithmoperates as follows. At the beginning of each ARQ slot
m
determine the subset of RBs available for transmissionas described in Section IVA. For each UE, ﬁnd the
N
most energy efﬁcient allocations (power, rate and subcarriers)subject to the restrictions and details described in Section IVBand formulate the reduced searchspace optimization problem.Finally, allocate the chosen subcarriers to each UE at a givenpower level and using a given MCS.
A. Residual Resource Allocation
Due to the synchronous HARQ mechanism, any transmission that was erroneous, and has not exceeded the maximumnumber of transmissions is rescheduled exactly
8
subframesfollowing its srcinal transmission. These transmissions arescheduled using the same set of RBs
2
and using the sameMCS. To accommodate these restrictions, we denote theresource restriction for each UE the vector given as
S
i
(
m
)
T
=[
S
T i,
1
,
S
T i,
2
,
S
T i,
3
,
S
T i,
4
]
where
S
i,n
has elements given as
S
i,n
:
j
=
⎧⎨⎩
1
,
if block
{
n,j
}
is reserved for ReTx
1
,
if UE
i
ReTx during
n
0
,
otherwise
j
= 1
,...,M
(15)The resource restriction vector ensures that UEs are not ableto initiate a new transmission during subframes where theyhave a retransmission, and cannot be allocated any resourcesthat are reserved for retransmission by any UE.
B. Best
N
Allocation Computation
The Best
N
allocations represent the
N
allocations (setof RBs, MCS mode, and power allocated) that are the mostenergy efﬁcient for the UE use for transmission. We denote
2
Retransmissions are restricted to the same RBs in frequency.
the tuple
B
i,n
≡ {
k
i
,P
i
,
N
i
}
as the
n
thmost energy efﬁcientallocation for a UE
i
. These allocations minimize the requiredapplied power to satisfy a target error rate
BLER
tgt
. To obtainthese allocation, for each UE
i
, we perform the following1) For known
T
i
(
m
)
, obtain the number of RBs
M
(
k
i
)
needed for each MCS mode
k
i
given from [4] andusing (1)2) For each unique quantity of resource blocks
M
(
k
i
)
,choose the minimum effective coding rate that cantransmit
T
i
(
m
)
bits of data during that block 3) For each such MCS scheme, determine the power levelneeded to maintain
BLER
tgt
for all possible allocationsof
M
(
k
i
)
contiguous resource blocks using (2). As the
Q
function is monotonic in its arguments, this can easybe found through efﬁcient search techniques.4) Store the Best
N
allocations, including MCS, powerlevel required and resource block set in
B
i,n
ranked byrequired power allocation level.Once efﬁcient allocations have been computed, the optimization problem is a general setpacking problem and can beformulated using binary programming as
min
x
c
T
x
(16)s.t.
Ax
≤
1
M
,
A
eq
x
=
1
K
, x
j
∈ {
0
,
1
}
,
∀
j
∈
x
where
c
is a realvalued vector,
x
is the vector of allocationselections,
A
eq
is the equality constraint matrix of
K
rowsand
A
is the inequality constraint matrix. Each nonzeroentry of the solution vector
x
corresponds to selecting thecorresponding column allocation in
A
. Consequently, thematrices
A
and
A
eq
are given as
A
= [
A
1
,
···
,
A
K
](17)
A
eq
=
⎡⎢⎣
1
T C
1
···
0
T C
K
.........
0
T C
1
···
1
T C
K
⎤⎥⎦
(18)
where the columns of matrices
A
1
,...,
A
K
each contain a setof potential RB allocations for each UE based on the efﬁcientallocations found previously and
C
i
is the number of columnsin
A
i
. The inequality ensures that at most
1
UE occupies anyRB in frequency during any subframe while the equality isused to ensure exactly
1
allocation is chosen for each UE.The submatrix
A
i
is obtained as follows. Let
N
(
i,n
)
bethe set of RB allocations for the
n
thallocation of
i
(stored in
B
i,n
).
A
i
is then comprised of small submatrices for each of the
n
allocations and for each subframe of the ARQ slot or as
A
i
=
⎡⎢⎣
A
i,
1
···
0
M
······
A
i,n
···
0
M
.........
······
.........
0
M
···
A
i,
1
······
0
M
···
A
i,n
⎤⎥⎦
(19)where
0
M
is an
M
length column vector and
A
i,n
is a
M
length column vector given as
a
i,n
:
j
=
1
, j
∈ N
(
i,n
)0
,
otherwise
, j
= 1
,
2
,...,M
(20)Finally,
A
i
is obtained by removing any columns from
A
i
that share any nonzero row elements with the column vector
S
i
(
m
)
(to account for preallocated retransmissions).
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2011 proceedings