0

Multihop Relay-Enhanced WiMAX Networks

Yongchul Kim and Mihail L. Sichitiu
Department of Electrical and Computer Engineering
North Carolina State University
Raleigh, NC 27695
USA

1. Introduction
The demand for high speed data service has been increasing dramatically since the Internet
has become a part of people’s lives. Most broadband wireless service providers have boosted
data service rates by adopting recently developed technologies such as OFDM, MIMO, and
smart antennas. However, in practice there are still problems such as coverage holes due to
shadowing, and poor signal to interference and noise ratio (SINR) for the subscriber stations
(SSs) that are far away from the base station (BS). A simple solution for this problem is to add
more BSs, but it is a very inefficient solution especially when there are few SSs to be served
(e.g., in rural areas.) As an alternative to adding BSs, deploying low-cost relay stations (RSs)
provides a cost-effective way to overcome the above problem (RSs are a simplified version of a
full BS resulting in with lower upfront cost than BS; additionally, RSs do not require backhaul
connections, thus reducing operating costs). The WiMAX specification was amended (802.16j,
2009) to include multihop relays, an extension which has gained much attention and proved to
be an attractive technology for the next-generation of wireless communications. Furthermore,
the currently evolving Long Term-Evolution Advanced (LTE-A) standard considers multihop
relaying as an essential feature (3GPP, 2009). In this chapter, we study the effect of using RSs
on both capacity and coverage enhancements.
The IEEE 802.16j amendment focuses on the deployment of RSs in such a way that the
network capacity can be enhanced or coverage of the network can be extended. Accordingly,
two different types of RSs are specified in the amendment: transparent RS (T-RS) mode
and non-transparent RS (NT-RS) mode. In T-RS mode, the framing information is always
transmitted by the BS to the SSs directly, while data traffic can be relayed via RSs. Therefore,
in cells with T-RSs, the SSs associated with an RS have to be located within the coverage of the
BS. Conversely, in NT-RS mode, the framing information is transmitted along the same path as
data traffic to the SSs, and thus the RS operates effectively as a BS for connected SSs. Therefore,
T-RSs allow throughput enhancement only, whereas NT-RSs can extend the coverage as well
as increase the throughput. Both types of relays can serve unmodified SSs (i.e., the SSs do not
distinguish between genuine BSs and RSs). In this chapter, we analyze the benefits of using
RSs for the capacity enhancement scenario with T-RSs and the coverage extension scenario
with NT-RSs respectively.
In the first part of this chapter, we focus on improving cell capacity by deploying T-RSs inside a
cell, and consider the placement of RSs that maximizes cell capacity. According to the location
of RSs, the network capacity will vary significantly, i.e., when the RS is either very close to
2 Will-be-set-by-IN-TECH

the BS or far away from the BS, only a few SSs will benefit from the RS. In order to maximize
the number of SSs that can achieve greater throughput through the T-RSs, we need to find
the optimal placement of T-RSs such that the cell throughput is maximized. We also show
how various network parameters such as reuse factor, terrain types, RS antenna gain, and the
number of RSs affect the optimal placement of RSs and the capacity gain compared to the
conventional scenario (i.e., without using RSs).
In the second part, we focus on deploying NT-RSs for the purpose of coverage extension.
We explore three different issues in this part. First, we study several scheduling schemes
such as orthogonal, overlapped, and optimal schemes in order to maximize cell throughput
while serving the SSs in a fair manner. Second, we analyze cell coverage extension by varying
both the location and number of RSs from a cost efficiency perspective. Finally, we explore
an extension of the optimal scheme to a general multihop relaying scenario, and analyze
the network throughput degradation due to the increase of relay hops under the optimal
scheduling scheme.
The rest of this chapter is organized as follows. In the next section, we discuss the system
model including system description, SINR analysis, fading channel, and relay strategy. In
Section III, we present the capacity enhancement scenario with T-RSs. In Section IV, we
analyze cost effective coverage extension scenarios with NT-RSs. The optimal scheduling
scheme is also presented and compared with the orthogonal and overlapped schemes. Section
V concludes the chapter.

2. System model
2.1 System description
In this chapter, we consider a single WiMAX cell consisting of a central BS and several RSs
for the purpose of capacity enhancement, coverage extension, or both. The SSs are uniformly
distributed throughout the cell and only N SSs are randomly chosen to be active at a time for
each scenario. The BS is responsible for allocating resources for the SSs to be served and is
connected to the backhaul network, while the RSs have no backhaul links but are wirelessly
connected to the BS. The main responsibility of the RS is to relay data between the BS and
SSs. All RSs and the BS are referred to as service nodes in the rest of this chapter. The RS to
RS connection is also allowed for the coverage extension scenario. However, in the capacity
enhancement scenario, we assume only two-hop relaying since more than two-hop relaying
without extending coverage reduces the efficiency of using RSs. The one-hop links BS to RS
and RS to RS are referred to as relay links, and the links BS to SS and RS to SS as access links.
We assume that every node in a cell has a single omni-directional antenna and operates in
half-duplex mode, hence, no terminal can receive and transmit data simultaneously. The
frequency reuse scheme is not considered in the scenario for the optimal placement of T-RSs,
i.e., only one node can be active at a time. In contrast, for the coverage extension scenario,
the proposed optimal scheduling scheme allows for frequency reuse in order to maximize
the bandwidth efficiency, hence, the throughput degradation due to coverage extension can
be minimized. The standard allows for two types of duplex methods to separate the uplink
(UL) and downlink (DL) channels: time division duplex (TDD) and frequency division duplex
(FDD); we assume TDD in this chapter since TDD makes more efficient use of the spectrum
by dynamically allocating the amount of time slots to each direction. The system parameters
used for the analysis are listed in Table 1.
Multihop Relay-Enhanced WiMAX Networks 3

System Parameters OFDMA Parameters

Operating Frequency 3.5 GHz FFT Size 1024
Duplex TDD Sub-carrier Frequency Spacing 10.94 kHz
Channel Bandwidth 10 MHz Useful Symbol Time 91.4 μs
BS/RS Height 50 m Guard Time 11.4 μs
SS Height 1.5 m OFDM Symbol Duration 102.9 μs
BS/RS Antenna Gain 17 dBi Data Sub-carriers(DL / UL) 720 / 560
SS Antenna Gain 0 dBi Pilot Sub-carriers(DL / UL) 120 / 280
BS/RS Power 20 W Null Sub-carriers(DL / UL) 184 / 184
SS Power 200 mW Sub-channels(DL / UL) 30 / 35
BS/RS Noise Figure 3 dB
SS Noise Figure 7 dB
Table 1. Simulation Parameters

2.2 SINR analysis

The adaptive modulation and coding scheme (AMC) is the primary method of maintaining
the quality of wireless transmission. WiMAX supports AMC by defining seven combinations
of modulation and coding rate that can be used to achieve various data rates specified
by the standard (Andrews et al., 2007). Table 2 shows the modulation and coding rates
and the corresponding achievable data rate; the last column represents the minimum
required threshold values of SINR computed by a bit error rate expression for M-QAM
(Foschini & Salz, 1983) when bit error rate is 10−6 . For example, when the received SINR
is between 9.1 and 11.73dB, the achievable data rate will be 5.25Mbps. In general, a higher
order modulation tends to be used close to the base station, whereas lower order modulations
tend to be used at longer ranges.
The IEEE 802.16 working group has recommended the Erceg-Greenstein path loss model for
fixed wireless application systems. Since we did not consider the mobility of the SSs in this
analysis, we used this model to calculate path loss. The Erceg-Greenstein models are divided
into three types of terrains, namely A, B and C. Terrain type A has the highest path loss,
and is applicable to hilly terrains with moderate to heavy foliage densities. Type C has the
lowest path loss and applies to flat terrains with light tree densities. Type B is suitable for
intermediate terrains. The basic path loss equation with correction factors is presented in
(Erceg & Hari, 2001):
       
4πd0 d h f
L = 20 log10 + 10α log10 − 10.8 log10 + s + 6 log10 , (1)
λ d0 2 2000

where d0 =100m, α is the path loss exponent dependent on terrain type, d is the distance
between the transmitter and receiver, h is the receiver antenna height, f and λ are the
frequency and wavelength of the carrier signal, and s is a zero mean shadow fading
component. When the path loss value between the transmitter and receiver is computed by
using (1), the received signal power Pr can be calculated by:

Gt Gr Pt
Pr = , (2)
L
where Gt , Gr , and Pt represent the transmitting antenna gain, receiving antenna gain, and
the transmission power. Once the received signal power is computed, the SINR value at the
4 Will-be-set-by-IN-TECH

Downlink Spectral
Modulation & Threshold
Data Rate Efficiency
Coding rate [dB]
[Mbps] [bps/Hz]
QPSK 1/2 5.25 1.0 9.1
QPSK 3/4 7.87 1.5 11.73
16 QAM 1/2 10.49 2.0 13.87
16 QAM 3/4 15.74 3.0 17.55
64 QAM 2/3 20.99 4.0 20.86
64QAM 3/4 23.61 4.5 22.45
64 QAM 5/6 26.23 5.0 24.02
Table 2. SINR Threshold Set for a BER of 10−6

receiver can be easily determined by:

Pr
SI NR = , (3)
PN + βPI
where β is the number of co-channel cells of the first tier, PN is the noise power, and PI is
the interference signal power from a neighboring cell on the same frequency as the current
cell. In a similar way to the received signal power, the interference signal power can be
computed by using (1) and (2)√ with the information of co-channel distance. We assume that
the co-channel distance is R 3τ (Rappaport, 2001), where τ is the reuse factor and R is the
cell size. For the capacity enhancement scenario with T-RSs, only inter-cell interference is
considered since no concurrent transmissions are allowed inside a cell, while for the coverage
extension scenario with NT-RSs, intra-cell interferences is also considered as multiple nodes
can transmit simultaneously.

2.3 Fading channel

In a wireless communication system, a signal can travel from transmitter to receiver over
multiple paths, and hence the received signal can fade. This phenomenon is referred to
as multipath fading. In a fading environment the received signal power varies randomly
over time due to multipath fading. We assume well known fading channels such as the
Rayleigh fading and Rician fading channel for the access link and the relay link respectively.
The Rayleigh fading channel is most applicable when there is no propagation along the
line of sight between the transmitter and receiver, while the Rician fading channel is more
appropriate when there is a dominant line of sight component at the receiver. For an access
link, the amplitude distribution of the received signal is accurately modeled by a Rayleigh
distribution:  
ρ ρ2
p(ρ) = 2 exp − 2 , ρ ≥ 0, (4)
σ 2σ
where ρ is the amplitude of the received signal and σ2 is the local mean power. From the
probability density function (pdf) of the received signal amplitude (4), the pdf of received
signal power, γ, can be derived and has the exponential pdf (Zhang & Kassam, 1999):
 
1 γ
p(γ ) = ∗ exp − ∗ , γ ≥ 0, (5)
γ γ
where γ ∗ is the mean power of the received signal. In a similar way, for a relay link,
the amplitude distribution of the received signal is more accurately modeled by a Rician
Multihop Relay-Enhanced WiMAX Networks 5

distribution:  2   
ρ ρ + ν2 ρν
p(ρ) = 2 exp − I0 , ρ ≥ 0, ν ≥ 0, (6)
σ 2σ2 σ2
where In (·) is the n th -order modified Bessel function of the first kind, and 12 ν2 and σ2 are the
power of the LOS component and the power of all other scattered components respectively.
Thus, the total mean power of the received signal, γ ∗ , can be expressed as γ ∗ = 12 ν2 + σ2 .
The ratio between the signal power in the dominant component and the local mean scattered
ν2
power is defined as Rician K-factor (Erceg & Hari, 2001), where K = 2σ 2 . When the K-factor is
equal to zero, the Rician distribution becomes a Rayleigh distribution; from the pdf of received
signal envelope (6), the pdf of received signal power, γ, can be derived by transforming
random variable ρ into γ by considering the relationship between amplitude and power of
the signal, γ = 12 ρ2 . The pdf of received signal power can be expressed as:
   
(1 + K ) e − K (1 + K ) γ 4K (1 + K )γ
p(γ ) = exp − I0 , K ≥ 0, γ ≥ 0, (7)
γ∗ γ∗ γ∗

where γ ∗ is the mean power of the received signal.

2.4 Relay strategy

The SSs that are outside of the transmission range of the BS have to be served via RSs, while
the SSs located inside the transmission range of the BS can be served either directly from the
BS or via RSs. In general, the SSs transmit/receive data to/from the BS via RSs only if the
achievable relay data rate (BS-RS-SS) is greater than direct data rate (BS-SS). Since we assume
that every node has a single antenna and operates in half duplex mode, the relay data rate
is influenced by the link capacities and time durations of both hops involved. It is unlikely
that the SSs having a good direct link capacity from the BS will use an RS to achieve a higher
data rate. To compute the relay data rate in this chapter, we assume that the incoming data
and outgoing data at the RSs should be equal. Let CBS− RS and CRS−SS be the capacities of
BS to RS and RS to SS links respectively when each link is given the whole bandwidth, and
also let t BS− RS and t RS−SS be the time durations of BS to RS and RS to SS links respectively.
Focusing on the DL transmission, t BS− RS + t RS−SS should be equal to the total duration of DL
subframe. The amount of data transferred from the BS to an RS is equal to the amount of data
transferred from the RS to an SS:

CBS− RS · t BS− RS = CRS−SS · t RS−SS . (8)

Thus, the average data rate of an SS using an RS is equal to the amount of data received
divided by the time required to receive it:

CBS− RS · t BS− RS
CBS−SS = , (9)
t BS− RS + t RS−SS

as the RS cannot receive from the BS while transmitting to the SS. Consequently, using (8), the
relay data rate of an SS can be rewritten as:

1 1 1
= + . (10)
CBS−SS CBS− RS CRS−SS
6 Will-be-set-by-IN-TECH

1500
Base Station
Relay Station
Relay SSs
1000

500
Y [m]

0
z

−500

−1000

−1500
−1500 −1000 −500 0 500 1000 1500
X [m]

Fig. 1. A scenario with a single RS optimally placed at distance z from the BS showing the
nodes that benefit from the RS.

3. Capacity enhancement
In this section, we focus on improving cell capacity by deploying T-RSs (transparent relays)
inside a cell, and consider the placement of RSs that maximizes cell capacity. There has been
a great deal of research directed toward improving the capacity of wireless networks at the
physical layer. However, the achievable bit rate is still limited by the received signal strength
due to the fact that wireless signal attenuates severely as it propagates between transmitter
and receiver. Especially, the SSs located at the edge area of a cell achieve very limited data
rates. To mitigate this problem, deploying RSs inside a cell can increase the achievable bit rate
between a transmitter and a receiver leading to capacity enhancement.

3.1 Optimal placement of transparent relay

A network operator always desires the most cost effective solution with a minimal
deployment expenditure for the provision of satisfactory service. Therefore, in order to
provide efficient multi-hop relay networks, we need to know the optimal location of RSs for
maximizing network capacity. In this subsection, we show how to find the optimal location
of a T-RS that maximizes the cell capacity; the results can be easily extended to scenarios
with multiple RSs. We assume that multiple RSs are deployed in a circular pattern inside a
cell. Thus, the optimal distances from the BS to the RSs are consistent, however the optimal
distance could vary as the number of RSs changes.
As shown in Fig. 1, the BS is located at the center of the cell and the SSs are distributed
uniformly in the coverage area of the BS with constant grid size 10m. The location of an
SS can be uniquely identified by its coordinates. We define the set of coordinates of the SSs
inside a cell, Q = {( x1 , y1 ), ( x2 , y2 ), ..., ( x N , y N )} where N is the total number of SSs inside
a cell. When a T-RS is located at ( x, y) and an SS i is located at ( xi , yi ), i ∈ {1, 2, ..., N }, the
Multihop Relay-Enhanced WiMAX Networks 7

distances of the links BS to RS, RS to SS, and BS to SS can be expressed as:

d BS−SS = x2i + y2i ,

d BS− RS = x2 + y2 , (11)

d RS−SS = ( xi − x )2 + (yi − y)2 .

Let us denote with Css ( xi , yi ) the achievable data rate of an SS that is located at ( xi , yi ). We
Direct( x , y ) and C Relay
also denote with Css i i ss ( xi , yi ) the achievable direct data rate (BS-SS) and
relay data rate (BS-RS-SS) of an SS located at ( xi , yi ) respectively when the whole channel
bandwidth is used for that SS; with the distances computed by equation (11), the path losses
and average received signal powers are calculated by using equations (1), (2). After that, the
random values of the received signal powers can be generated by distributions (5), (7), and
then the instantaneous SINR values can be computed by equation (3). Consequently, using
the threshold SINR values in Table 2 and the equation (10) for the relay case, the achievable
direct and relay data rates of an SS can be determined. To maximize the cell capacity, every SS
will choose the best achievable data rate between direct and relay data rates:
 
Relay
Css ( xi , yi ) = max CssDirect
( xi , yi ), Css ( xi , yi ) . (12)

Due to the fading channel effect (i.e., received signal power is a random variable), an SS that
is close to the BS does not always achieve a higher data rate than an SS that are further away
from the BS. Likewise, as shown in Fig. 1 a few SSs located on the left side of the cell can
benefit from the RS placed on the right side of the cell. We denote with relay SSs and direct
SSs the SSs whose relay data rate is higher than direct data rate and the SSs whose direct data
rate is higher than relay data rate respectively. We also define the mean cell capacity, Ccell , as
the summation of every SS’s achievable data rate divided by the total number of SSs in a cell.
Therefore, the optimal placement of an RS can be determined in such a way that the mean cell
capacity is maximized:
1
arg max ∑ Css (xi , yi ; x, y).
( x,y ) N( x ,y )∈Q
(13)
i i

3.2 Impact of network parameters

In this subsection, we show how various network parameters such as reuse factor, terrain
types, RS antenna gain, and the number of RSs affect the optimal placement of RSs and the
cell capacity. To evaluate the performance of using RSs in comparison to the conventional
Relay Direct be
scenario (without using RSs), we define the capacity gain parameter. Let Ccell and Ccell
the cell capacity with RS and without RS respectively, the relative capacity gain can be defined
as:
Relay
C − C Direct
Capacity Gain = cell Directcell . (14)
Ccell
We assume that our basic system has a reuse factor of seven, one sector per cell, terrain type A,
17dBi RS antenna gain, and four RSs deployed to enhance cell capacity. The system is analyzed
by varying one specific parameter without changing the rest of basic system parameters. For
each scenario, the cell size (cell radius) will vary since the received SINR value at the SS is
8 Will-be-set-by-IN-TECH

25
Terrain A Downlink
Terrain A Uplink
Terrain B Downlink
Terrain B Uplink
20

15
SINR [dB]

9.1dB

10

0
0 500 1000 1500 2000 2500 3000
Distance between BS and SS [m]

Fig. 2. Downlink and uplink edge SINR as a function of cell size for two different terrain
types.

affected by the different network parameters. Fig. 2 shows how cell size can be determined
for a specific scenario. The SINR value of an SS located at the edge of the cell decreases as
the distance between BS and SS increases on both DL and UL regardless of the terrain types.
The decrease in SINR is more significant for terrain type A. However, when the edge SS is
close to the BS, the SINR values under terrain type A are even higher than that of terrain type
B because the co-channel interference values are significant when the received signal powers
are similar in both terrain types. Once either the DL or UL SINR value reaches the minimum
threshold value 9.1dB, that distance from the BS is considered as a cell size.
The first scenario is to evaluate the capacity gain and the optimal placements of RSs by varying
the reuse factor. The reuse factor represents the number of cells grouped in a cluster. When the
number of cells in a cluster increases, the co-channel distance also increases. The co-channel
interference is a function of co-channel distance, hence, the larger the reuse factor the smaller
the interference power from neighboring cells. Moreover, the cell size is affected by the
reuse factor. When the reuse factor decreases, the cell size also decreases as the co-channel
interference increases. When the cell size is small, most of the SSs do not benefit from the RSs
since they are close enough to the BS leading to the smaller capacity gain. In other words, it
is not very useful to deploy RSs in scenarios with a smaller reuse factor. Fig. 3(a) shows the
cell capacity gain as a function of the location of RS in each reuse factor scenarios four, seven,
nine, and twelve. The maximum cell capacity gain of 31.54% is achieved for a reuse factor of
twelve, while only a capacity gain of 13.22% is obtained in the scenario with a reuse factor of
four. Although RSs are optimally placed in a cell, only small number of SSs can benefit from
RSs in the scenario with the reuse factor four. It is interesting to note that RSs are increasing
the capacity of the cell even if placed near the base station due to Rayleigh fading that may
result in SSs preferring the link to the RSs to the link to the BS. The exact cell capacities and
relay locations are listed in Table 3.
In the second scenario we study the impact of terrain types mentioned in section 2.2 on the
capacity gain and the optimal placements of RSs. When terrain type changes from A to C, the
path loss decreases between transmitter and receiver. Thus, the received signal mean power
Multihop Relay-Enhanced WiMAX Networks 9

Reuse factor 12 Terrain A

30 Reuse factor 9 Terrain B
Reuse factor 7 30 Terrain C
Reuse factor 4 Optimal Point
Optimal Point
25
25
Capacity Gain [%]

Capacity Gain [%]

20

20
15

10 15

5
10
0 200 400 600 800 1000 1200 1400 0 300 600 900 1200 1500 1800 2100
Position of RS [m] Position of RS [m]

(a) Reuse factor (b) Terrain type

30 35
RS Gain 17dB
RS Gain 10dB
RS Gain 5dB 30
25 Optimal Point

25
20
Capacity Gain [%]

Capacity Gain [%]

20
15
15

10
10

5
5 RS Gain 17dB
RS Gain 10dB
RS Gain 5dB
0 0
0 200 400 600 800 1000 1200 1400 0 2 4 6 8 10 12 14
Position of RS [m] Number of RS

(c) RS antenna gain (d) Multiple RSs

Fig. 3. Cell capacity gains for different network parameters when using four T-RSs.

increases leading to a bigger cell size as terrain types changes from A to C. The cell sizes for
terrain type A, B, and C are 1390m, 1810m, and 2120m respectively. Fig. 3(b) shows achievable
capacity gains with respect to the location of RS for different terrain type scenarios. The
maximum capacity gains for each scenario are very similar to each other, 29.7% is achieved
for terrain type B and 28.87% is achieved for terrain type C. However, the ratio of optimal
location of RS to each cell radius decreases as terrain type changes from A to C. When terrain
type is A, the optimal location of RS is 67.63% of the cell radius, while optimal location of RS
for terrain type C is 58.96%.
In the third scenario we analyze the capacity gain and the optimal placements of RSs by
varying the RS antenna gain. The cost of an RS is assumed to be much less than a BS since
an RS does not have a backhaul link, but the antenna gain of an RS could be as good as the
BS antenna gain. We use 17dBi RS antenna gain for our basic system, and change that to
10dBi and 5dBi to analyze the impact of RS antenna gain on the system. Fig. 3(c) shows the
cell capacity gain results for different RS antenna gains. The maximum capacity gain 29.03%
is achieved when RS antenna gain is 17dBi and the lowest capacity gain 14.13% is achieved
when RS antenna gain is 5dBi. It is clear that the cell capacity gain is significantly impacted
by the antenna gain of RS. That is, the lower the RS antenna gain the lower the capacity gain
10 Will-be-set-by-IN-TECH

Direct Relay
Radius Ccell Optimal Ccell Capacity
Scenario
[m] [Mbps] Location [Mbps] Gain[%]
Reuse factor 4 930 16.6132 530 18.8094 13.22
Reuse factor 7 1390 12.9280 940 16.6804 29.03
Reuse factor 9 1420 12.6865 980 16.5553 30.50
Reuse factor 12 1440 12.5138 1020 16.4602 31.54
Terrain B 1810 12.4314 1110 16.1237 29.70
Terrain C 2120 12.2409 1250 15.7743 28.87
RS Gain 10dB 1390 12.9272 940 15.7502 21.84
RS Gain 5dB 1390 12.9266 890 14.7527 14.13
Table 3. Capacity and optimal relay position for the basic scenario and variations of the reuse
factor, terrain type, and RS antenna gain.

achieved. It is also shown that the different antenna gains of RS had no significant impact on
the optimal placement of RS.
In the last scenario of this subsection we explore the impact of the number of RSs on cell
capacity. In general, the more RSs, the higher the cell capacity. However, the network cost
will also increase as the number of RS increases. Fig. 3(d) shows how much capacity gain
can be achieved with respect to the number of RS for different RS antenna gain scenarios.
The increase rate of capacity gain for each scenario is clearly decreasing as the number of
RS increases. When the RS antenna gains are 17dBi, 10dBi, and 5dBi, the capacity gains
are limited to approximately 33%, 31%, and 25% respectively. Therefore, it is clear that the
addition of RSs after a certain number of RSs does not further improve the cell capacity, e.g.,
deploying more than six RSs in 17dBi antenna gain scenario is not useful. The capacity gain
with 14 RSs of antenna gain 5dBi is lower than that of a system with five RSs of antenna gain
10dBi or three RSs of antenna gain 17dBi. That is, the RS antenna gain has more significant
impact on the capacity gain than the number of RSs.

4. Coverage extension
In this section, we focus on deploying NT-RSs for coverage extension. In order to analyze
the benefits of using RSs from a coverage extension perspective, we need to examine how
deploying RSs affects cost and throughput as well as coverage increase. To analyze the
variation of throughput under the influence of RSs, the scheduling scheme has to be taken into
account since the achievable throughput could differ significantly according to the scheduling
schemes used. We first present three scheduling schemes: orthogonal, overlapped, and
optimal that can be used in two-hop relaying networks. We then analyze the cost effective
coverage extension problem by varying both the location and number of RSs (Kim & Sichitiu,
2010a). Finally, we explore an extension of the optimal scheduling scheme to a general
multihop relaying scenario, and examine the impact of an increased number of relay hops
on the network performance (Kim & Sichitiu, 2011a). Fig. 4 shows an example coverage
extension scenario where three NT-RSs are deployed at the edge of the BS transmission range.
Using this scenario, we evaluate the performance of the scheduling schemes presented in the
following subsection. The cell radius for the coverage extension scenario is assumed to be
1200m (determined by the condition that the cell coverage probability under the Rayleigh
fading channel is greater than 90% (Erceg & Hari, 2001)), and the rest of network parameters
are the same as the basic system in Section 3.
Multihop Relay-Enhanced WiMAX Networks 11

2000

5
1500

7
1
1000 RS 5
2 10
RS2
500

Radius [m]
23 6
2 RS1
0 BS

BS RS1 7

20
ï500
15
15

10
ï1000 RS 10 7
3
1
RS3 ï1500

5
ï2000
15

ï2000 ï1000 0 1000 2000

Radius [m]

(a) Coverage extension scenario (b) Contour graph

Fig. 4. (a) Coverage extension scenario and (b) Contour graph of achievable average data rate
when three RSs are deployed at the edge of the cell.

4.1 Scheduling schemes

According to the standard (802.16j, 2009), it is possible for the NT-RSs and BS to transmit
and receive simultaneously to/from the associated SSs during the access zone period.
Therefore it is challenging to schedule transmission opportunities to each link in the network,
especially for serving SSs in a fair manner. We first present two existing scheduling schemes,
namely the orthogonal and overlapped schemes (Park et al., 2009), and then introduce an
optimal scheme (Kim & Sichitiu, 2011b). The orthogonal scheme minimizes interference by
disallowing frequency reuse; however it can lead to lower throughput performance, whereas
the overlapped scheme can achieve higher throughput by maximizing frequency reuse, but
the outage rate is also increased due to significant intra-cell interference. In (Park et al.,
2009), the boundary between access and relay zones was not dynamically selected according
to the traffic load but statically determined for each scenario. To overcome this problem,
we formulate the optimization problem for both orthogonal and overlapped schemes such
that the cell throughput is maximized by optimally determining the boundary between the
access and relay zones. Furthermore, we introduce an optimal scheduling scheme to combine
the advantages of orthogonal and overlapped schemes. The optimal scheme maximizes the
frequency reuse efficiency while avoiding outage events due to interference. The formulated
optimization problems can be solved by using linear programming.
OFDMA based WiMAX networks allow scheduling to be done in the tiling frame structure
(two-dimensional time×frequency) to attain frequency selectivity and multiuser diversity.
However, due to the fact that the original tile scheduling problem is NP-hard (Deb et al.,
2008), we will not consider multiuser scheduling over the frequency domain. Thus the entire
spectrum is allocated to each node whenever they are allowed to transmit, i.e., scheduling is
done by assigning time slots to nodes. For scheduling, fairness is an important issue. The well
known fairness schemes such as max-min and proportional fairness for the relay enhanced
WiMAX system are evaluated in our previous paper (Kim & Sichitiu, 2010b). The goal of
max-min fairness is to allocate network resources in such a way that none of the active SSs
can achieve more throughput than other active SSs without decreasing the throughput of other
SSs. We formulate the optimization problem for each scheduling scheme under the max-min
12 Will-be-set-by-IN-TECH

Notation Description
R Set of RSs
R+ Set of service nodes (BS and RSs)
U Set of possible transmission subsets of service nodes
V Set of possible transmission subsets of relay links
L Set of possible relay links (lij ∈ L)
lij Relay link between service node i and j (i ∈ R+ , j ∈ R)
S Set of SSs
Sb Set of SSs associated with BS
SR Set of SSs associated with RSs
Sru Set of SSs associated with RS r ∈ R in the subset u
Sru+ Set of SSs associated with r + ∈ R+ in the subset u
Csu Achievable data rate of SS s ∈ S in the subset u
Cr Achievable data rate of RS r ∈ R from the BS
Cijv Achievable data rate for a relay link l ij in the subset v
λus Time fraction allocated to SS s ∈ S in the subset u
λr Time fraction allocated to RS r ∈ R in relay zone
λu Time fraction of subset u ∈ U in access zone
λv Time fraction of subset v ∈ V in relay zone
λvij Time fraction allocated for a relay link l ij in the subset v
Ts Throughput of SS s ∈ S
Table 4. Notations used

fairness constraints (Tassiulas & Sarkar, 2002). The notations used for the formulations are
listed in Table 4.

4.1.1 Orthogonal scheduling scheme

The orthogonal scheme is an extreme solution for schedule resources since it does not allow
frequency reuse in order to minimize intra-cell interference during the access zone period.
In this scheme, only one service node can be active at a time to transmit to the associated
SSs. Hence, there is no outage problem due to interference, but the achievable network
throughput will be degraded due to inefficient radio resource utilization. To determine the
time duration of each transmission for the orthogonal scheme, we formulate the optimization
problem such that the cell throughput is maximized under max-min fairness constraints. Since
it is impossible to increase the throughput of an SS without decreasing that of other SSs in the
orthogonal scheme, the max-min fairness is equivalent to absolute fairness, i.e., every active
SS achieves an equal throughput.
We denote with R and S the sets of RSs
and SSs respectively,
 and the set of service nodes
(the BS and RSs) is denoted as R+ i.e., |R+ | = |R| + 1 . Let U be the set of possible
simultaneously active service nodes during the access zone period. Each element u ∈ U
represents one subset of R+ with all the service nodes in that subset able to transmit
concurrently to their associated SSs. In the orthogonal scheme, only single element subsets
are possible in U since simultaneous transmission
among service nodes
 is not allowed, hence,
the two sets U and R+ have the same cardinality i.e., |U | = |R+ | in the orthogonal scheme.
Let Cs be the achievable data rate of an SS from the service node that the SS is associated
with. In other words, Cs represents the instantaneous link capacity between an SS and its
Multihop Relay-Enhanced WiMAX Networks 13

service node. Similarly, the achievable data rate of an RS from the BS is denoted by Cr . Also,
let λs and λr be the time fraction allocated to an SS and the time fraction allocated to an RS
respectively. When the transmission subset u ∈ U changes, an SS can be associated with
a different service node. Thus, the achievable data rate and time fraction of an SS in each
transmission subset u are denoted by Csu and λus respectively. The ultimate throughput of an
SS, Ts , during the current DL subframe can be expressed as the summation of throughputs
received in each transmission subset u when the SS was allocated the time fraction λus :

Ts = ∑ Csu λus , ∀s ∈ S . (15)

u∈U

Our goal of maximizing cell throughput corresponds to maximizing the throughput, Ts , of

any subscriber s ∈ S in the orthogonal scheme. Finding the maximum achievable throughput
of an SS can be formulated as a linear programming problem as follows:

max Ts . (16)
s ∈S

Subject to:

Ts1 = Ts2 , ∀ s1 , s2 ∈ S ( s1  = s2 ). (17)

Cr λr = ∑ Cs λ s , ∀r ∈ R . (18)
s ∈S r
λu = ∑ λus , ∀r + ∈ u, ∀u ∈ U , |Sru+ | > 0. (19)
s ∈S ru+

∑ λu + ∑ λr ≤ 1. (20)
u∈U r ∈R
0 ≤ λus , λr ≤ 1, ∀ u ∈ U , ∀ s ∈ S , ∀r ∈ R . (21)

Here, Sr and Sr + denote the set of SSs associated with RS r ∈ R and service node r + ∈ R+
respectively. In each transmission subset u, the sets Sr and Sr + are denoted by Sru and Sru+ . The
first constraint ensures that every active SS in a cell achieves an equal throughput. The second
constraint states that there is no data loss at the RSs, the data transferred from BS to RS r ∈ R is
equal to the data transferred from RS r to the associated SSs. The third constraint ensures that
resources within the duration of each transmission subset u are fully utilized by the associated
SSs. Thus, the time fraction of each transmission subset u, λu , is equal to the summation of
time fractions allocated to SSs associated with r + when r + is the element of subset u. The forth
constraint captures the fact that the DL subframe consists of an access zone and a relay zone.
The summation of time fractions of every transmission subset will be equivalent to the access
zone time fraction, and the summation of time fractions allocated to RSs is the same as the
relay zone time fraction. The sum of access and relay zone time fractions should be less than
or equal to one. The final constraint restricts the amount of each time fraction allocated to SSs
and RSs to be positive and smaller than one. By using these scheduling constraints (17)-(21),
the objective function (16) can be maximized. Once the throughput of an SS (16) is maximized,
the cell throughput can be computed by:

Cell Throughput = ∑ Ts . (22)

s ∈S
14 Will-be-set-by-IN-TECH

17 50

45
16
40

15 35
Cell throughput [Mbps]

Outage rate [%]

30
14
25
13
20

12 15
Max throughput Max throughput
Max service nodes 10 Max service nodes
11 Max served nodes Max served nodes
5

10 0
1 5 10 15 20 25 1 5 10 15 20 25
Number of active SSs Number of active SSs

(a) Cell throughput (b) Outage probability

Fig. 5. (a) Cell throughput and (b) outage probability as a function of the number of active
SSs within a cell for different subset selection objectives for the overlapped scheme.

4.1.2 Overlapped scheduling scheme

The main goal of the overlapped scheme is to fully reuse radio resources during the access
zone period. Multiple service nodes can transmit data to the associated SSs simultaneously,
thereby enhancing network throughput, but at the same time outage events increase due to
significant intra-cell interference. All the service nodes in a cell can be active simultaneously
to maximize the chance of frequency reuse, however according to the number of active SSs
and distributions of the SSs, some of the service nodes may not have to be active since it is
possible that none of the active SSs are associated to that service node. Therefore, the decision
regarding which service node should be active over a frame needs to be made at the beginning
of a frame before scheduling. In other words, the overlapped scheme will consider only one
transmission subset of the active service nodes over one frame duration. That is, once the
subset of active service nodes is determined at the beginning of a frame, it will last for the
duration of the entire current frame. For determining the set of active service nodes, we should
also consider an additional subset selection objective (Kim & Sichitiu, 2011b):
• maximizing cell throughput,
• maximizing the number of active service nodes, or
• maximizing the number of served SSs.
According to which of these objectives are selected, a different subset of active service nodes
is determined for the overlapped scheme. Now, we can formulate the optimization problem
as in Section 4.1.1 to maximize cell throughput for the overlapped scheme by considering only
one subset u ∈ U instead of the entire set U . When the service nodes of the selected subset are
active simultaneously, each active SS can be associated only to the service node that has the
strongest link capacity to that SS over the entire duration of that frame. However, not every
active SS can fully use resources during the access zone period because we assume max-min
fairness and also the relay links (BS to RSs) have to share the resources orthogonally to transfer
data from the BS to the RSs. Therefore, for the SSs that are served via RSs, the SSs with
low link capacity are allocated large fractions of time while the SSs with high link capacity
may have smaller time fractions, hence, the absolute fairness still holds for the SSs associated
with RSs, but the SSs associated with the BS directly may achieve a higher throughput under
Multihop Relay-Enhanced WiMAX Networks 15

max-min fairness since these larger throughputs do not affect the throughput of the rest of
SSs associated with the RSs. Consequently, the objective of maximizing the throughput of an
SS does not correspond to maximizing the cell throughput for the overlapped scheme since
the equivalence of the absolute and max-min fairness constraint does not hold. Therefore, the
objective of the optimization problem for the overlapped scheduling scheme is expressed as:

max ∑ Ts . (23)
s ∈S

Let Sb and S R be the set of SSs associated with the BS and RSs respectively over a frame period.
The max-min fairness ensures that every SS achieves an equal throughput in each subset Sb
and S R . However, the throughput of an SS in Sb could be higher than the throughput of
an SS in S R . Therefore, the first constraint (17) in the orthogonal scheme is modified for the
overlapped scheme as follows:

Ts1 = Ts2 , ∀ s1 , s2 ∈ S b ( s1  = s2 )
Ts3 = Ts4 , ∀ s3 , s4 ∈ S R ( s3  = s4 ) (24)
Ts5 ≥ Ts6 , ∀ s5 ∈ S b , ∀ s6 ∈ S R .

The second and fifth constraints (18), (21) do not change for the overlapped scheme as there
is no data loss at the RSs, but the third and forth constraints (19), (20) are modified because
there may be wasted resources in the access zone due to fairness and only one subset of R+ is
considered in the overlapped scheme:

λu ≥ ∑ λus , ∀r + ∈ u, ∀u ∈ U , |Sru+ | > 0 (25)

s ∈S ru+

λu + ∑ λr ≤ 1. (26)
r ∈R

Consequently, the cell throughput for the overlapped scheme can be maximized by solving
linear programming with the objective (23) under constraints (18), (21), (24), (25), (26). Any
subset could be chosen at the beginning of a frame based on the subset selection objectives,
and the selected service nodes in that subset will be optimally scheduled to maximize
cell throughput by using the optimization problem formulated above. However, the cell
throughput and outage rate can vary according to the subset of active nodes chosen. Fig.
5 shows the cell throughput and outage rate as a function of the number of active SSs for
different subset selection objectives for the overlapped scheme. The max throughput objective
achieves the highest cell throughput, while the max served nodes objective attains the lowest
cell throughput. In contrast, the outage rate performance of the max served nodes objective
case is the best among three objective cases, while the outage rate of the max throughput
objective case is the worst.

4.1.3 Optimal scheduling scheme

The key drawback of the orthogonal scheme is the bandwidth inefficiency because it prevents
frequency reuse during the access zone period. For the overlapped scheme, the high outage
probability is a serious problem. To eliminate these problems, an optimal scheduling scheme
is proposed. The main task of an optimal scheme is to maximize bandwidth efficiency by
allowing frequency reuse while avoiding outage events due to intra-cell interference. In
order to accomplish the main task of the optimal scheme, we need to consider all possible
16 Will-be-set-by-IN-TECH

transmission subsets of service nodes during the access zone period, i.e., the set U is the power
+
set of R+ excluding the empty set in the optimal scheme scenario (|U | = 2|R | − 1). In each
subset of service nodes, an active SS can be either outage due to interference or associated
with the active service node that has the highest link capacity to that SS. The achievable data
rate of an SS, Csu , varies for each subset of active service nodes because intra cell interference
changes according to the number of active service nodes in each subset.
Similar to the orthogonal scheme, the objective of the optimization problem for the optimal
scheme is to maximize the throughput of any active SS in a cell since the equivalence of
the absolute and max-min fairness holds for the optimal scheme. In this scheme, the whole
bandwidth should be fully utilized without wasting resources, thus none of the active SSs can
achieve more throughput without decreasing the throughput of the other SSs. The first, forth
and fifth constraints (17), (20), (21) in the orthogonal scheme do not change for the optimal
scheme, but the second and third constraints (18), (19) are modified to take into account every
possible subset of service nodes for the optimal scheme. In the orthogonal and overlapped
schemes, the set of SSs associated with RS r, Sr , does not change over one DL subframe
interval because an RS r can be active only one time to transfer data to the SSs associated
to that RS, i.e., an RS r can not be included in more than two subsets. However, in the optimal
scheme, an RS r can be active more than once as part of different subsets, i.e., an RS r can be
an element of multiple subsets. Thus, the second constraint can be rewritten as:

Cr λr = ∑ ∑ Csu λus , ∀r ∈ R . (27)

u∈U s ∈S ru

To ensure that resources within the duration of each transmission subset u are fully utilized
by the associated SSs in the optimal scheme, there should not be any wasted resources.
For example, when r1+ and r2+ are active service nodes in the subset u, the summation of
time fractions allocated to SSs associated with r1+ should be equal to the summation of time
fractions allocated to SSs associated with r2+ :

λu = ∑ λus = ∑ λus ,
s ∈S u+ s ∈S u+
r
1
r2 (28)
∀r1+ , r2+ ∈ u, ∀u ∈ U , |Sru+ | > 0, |Sru+ | > 0.
1 1

Therefore, the cell throughput for the optimal scheme can be maximized by solving the linear
programming problem with the objective (16) under constraints (17), (20), (21), (27), (28).
To evaluate the performance of the optimal scheduling scheme, we compare its performance
with the orthogonal and overlapped schemes. Fig. 6 shows the cell throughput and outage
rates as a function of the number of active SSs in a cell. To obtain the average cell throughput
value, the simulation is repeated 10,000 times for each scenario with N active SSs randomly
placed in the cell with a uniform distribution. For the overlapped scheme, the max served
nodes subset selection objective is assumed. When there is only one active SS in a cell, there is
no difference between the three scheduling schemes on both the cell throughput and outage
rate since there is no frequency reuse and intra-cell interference. However, the differences
becomes significant as the number of active SSs increases. The cell throughput achieved by
the orthogonal scheme decreases because it is more likely to have SSs with low link capacities
consuming large fractions of the time in order to preserve fairness, while the cell throughput
for the optimal scheme grows as the number of active SSs increases since the optimal scheme
maximizes frequency reuse without increasing outage rates. As shown in Fig. 6(b), the outage
Multihop Relay-Enhanced WiMAX Networks 17

12 35
Overlapped(OvTH) Overlapped(OvTH)
Optimal(OpTH) Optimal(OpTH)
11.5 Orthogonal(OrTH) 30 Orthogonal(OrTH)

11 25
Cell throughput [Mbps]

Outage rate [%]

10.5 20

10 15

9.5 10

9 5

8.5 0
1 5 10 15 20 25 1 5 10 15 20 25
Number of active SSs Number of active SSs

(a) Cell throughput (b) Outage probability

Fig. 6. (a) Cell throughput and (b) outage probability as a function of the number of active
SSs within a cell for different two-hop scheduling schemes.

rate from the optimal scheme is identical to the result from the orthogonal scheme, while the
outage rate for the overlapped scheme continues to rise significantly as more SSs join the cell.
Although there is no interference between service nodes in the orthogonal scheme, about 6%
of active SSs still encounter outage due to the Rayleigh fading channels. Overall, the cell
throughput and outage rate performance can be dramatically enhanced by using the optimal
scheduling scheme.

4.2 Cost effective coverage extension

In this subsection we analyze a cost effective coverage extension scenario by varying both
the location and number of RSs. We use the optimal scheduling scheme presented in the
previous subsection to compute the cell throughput for each coverage extension scenario and
analyze the impact of varying the location and number of RSs on network throughput as well
as network cost. We assume that each cell has between one and six RSs arranged in a circular
pattern at the same distance from the BS to extend the cell coverage, and the cost of an RS
is assumed to be 40% of the cost of a BS (Upase & Hunukumbure, 2008). To compare the
network cost enhanced with RSs with the network cost without RSs, we define the relative
cost parameter:

Cost of network with RS

Relative Cost[%] = × 100. (29)
Cost of network without RS
For example, assume that the total network service area is covered by 100 BSs without RSs
(i.e., 100 cells); when two RSs are deployed in each cell to extend the cell coverage, the total
number of cells needed to cover the service area will be decreased. Assume that the new
number of cells is 50 (i.e., 50 BSs and 100 RSs); then the relative cost of this relay enhanced
network is 90% (50 + 100 × 0.4). We consider this relative cost as the network cost.
Figure 7(a) shows relative costs as a function of the RS location for a different number of RSs
per each cell. The distance between the BS and RSs varies from 1200m to 2400m, which is
twice the cell size. Since the RSs have higher antenna gains and transmission power than
those of the SSs, the location of RS could be outside of the BS coverage. As the location of
RSs from the BS increases, the relative costs decrease because the cell coverage extends when
18 Will-be-set-by-IN-TECH

95 16
1 RS
90 2 RS
3 RS 14
85 4 RS
5 RS
80 12
6 RS

Cell throughput [Mbps]

Relative Cost [%]

75
10
70

65 8

w/o RS
60
6 3RS at 1200m
55 4RS at 1500m
5RS at 1900m
4
50 6RS at 2300m

45 2
1200 1400 1600 1800 2000 2200 2400 0 5 10 15 20 25
RS location from the BS [m] Number of active SSs

(a) Relative cost vs RS location (b) Cell throughput vs number of active SSs
14
w/o RS
RS6
13 RSs at 1200m RS5
RSs at 1500m RS4
12 RSs at 1900m
RS3 RS
2 RS1
Cell throughput [Mbps]

11
RS1
RS2
10 RS3
RS5 RS6
RS4
9

8 RS1

RS2
7 RS
RS4 3

6 RS5 RS6

5
50 55 60 65 70 75 80 85 90 95 100
Relative Cost [%]

(c) Cell throughput vs relative cost

Fig. 7. Cost effective coverage extension scenario results

the RSs are further away from the BS leading to fewer required cells to cover the network
area, hence, lower cost. When the number of RSs increases from one to three, the relative
cost decreases regardless of the location of RSs, however, when the number of RSs is greater
than four, the relative cost of the higher number of RSs is not necessarily lower than that of
a smaller number of RSs. For example, the minimum relative cost is achieved by the three
RSs case, i.e., deploying more than four RSs at 1200m is not desirable as they are more costly.
From 1400m to 1700m deploying four RSs is the optimal case, and from 1800m to 2200m five
RSs is better, and six RSs is better for distances from 2300m to 2400m.
To evaluate the effect of varying locations and numbers of RSs on the cell throughput, the
optimal scheduling scheme is used such that every active SS can achieve the same throughput
and a reduced outage rate. Fig. 7(b) shows cell throughput as a function of the number
of active SSs for different locations and numbers of RSs. In the case without-RSs, the cell
coverage area is the minimum, while the cases with-RSs increase the cell coverage as the
placement of the RS is further away from the BS. Thereby, the cell throughput decreases as
the cell coverage increases. However, the cell throughput of the case without-RSs decreases as
the number of active SSs increases, while some of the cases with RSs show that cell throughput
tends to increase with the number of active SSs. This change in cell throughput is due to the
Multihop Relay-Enhanced WiMAX Networks 19

fact that it is more likely to have SSs with small link capacities consuming a large fraction of
the time in order to preserve fairness as the number of active SSs increase, but in the cases
with RSs the frequency reuse efficiency can overcome this tendency, hence, it is clear that the
frequency reuse scheme has a positive impact on the cell throughput. Especially, when the
location of RSs is less than 1500m, the achievable cell throughput continues to grow with the
number of active SSs.
To be able to determine the cost effective coverage extension scenario, we need to
simultaneously examine the effects of using RSs on both cost and throughput. Fig. 7(c)
shows the cell throughput as a function of relative cost when the number of active SS is 25.
Cell throughputs for three different RS locations and one to six RSs are plotted in this graph.
Overall, the relative cost decreases as the location of RSs is further away from the BS and the
number of RSs increases, but at the same time cell throughput also decreases. In other words,
lower network cost can be achieved at the expense of the cell throughput. However, when
the location of RSs is 1200m, the cell throughput continues to increase as the number of RSs
increases due to the increase in frequency reuse. Especially, when the number of RSs changes
from one to three, the relative cost decreases significantly. That is, deploying up to three RSs
at 1200m is beneficial from both throughput and cost points of view, but deploying more than
four RSs at 1200m is enhancing throughput at more cost. Therefore, cost effective coverage
extension without significant throughput degradation is always feasible by carefully choosing
both the location and number of RSs.

4.3 Generalization for multihop scenario

We explore an extension of the optimal scheduling scheme to a general multihop relaying
scenario by allowing more than three-hop relaying in a cell. Although the two-hop scenario
is technically a multihop scenario, we will use the term "multihop" to refer to scenarios with
more than one relay tier. Many researchers have focused on two-hop relaying networks since
this scenario has the largest throughput gain and more hops per connection cause a greater
delay. On the other hand, it is clear that the cell coverage will be significantly extended by
increasing the number of relay hops. Therefore, it is of interest to explore how increasing
the number of relay hops can affect the network performance under an optimal scheduling
scheme. The optimal scheme presented in the previous subsection is aimed at two-hop
relaying networks where the relay zone is orthogonally shared by relay links (BS to RSs). In
a multihop relaying scenario, the RSs should be able to relay data to/from other RSs, hence,
frequency reuse between relay links is also possible during the relay zone period. Therefore,
the extension of the optimal scheduling scheme should take into account frequency reuse in
both the access and relay zone periods. We present an extended optimal scheduling scheme in
this subsection, and evaluate its performance using two example three-hop relaying scenarios.

4.3.1 Optimal scheme for multihop

In the two-hop relaying scenario, the SSs are receiving data from the BS either directly or
via only one RS, while in the multihop scenario, the SSs can receive data through multiple
RSs. Also, multiple paths from the BS to each SS exist in a cell. If we assume that there is no
frequency reuse in the relay zone, as it is in two-hop scenario, the optimal path to each SS will
be the path that has the highest achievable relay data rate of the SS. However, to minimize
throughput degradation due to the increase of number of hops, frequency reuse must be
considered. Thereby, it is possible that a lower capacity relay link can also be scheduled for
RSs to relay data, since multiple relay links can be active simultaneously during the relay
20 Will-be-set-by-IN-TECH

zone period. To formulate the optimization problem for the multihop optimal scheduling
scheme, we need to consider every possible link between service nodes as relay links, and
then consider every possible set of relay links that can be active simultaneously.
Let lij be a relay link from the service node i ∈ R+ to j ∈ R, and let L be the set of all possible
relay links (i.e., lij ∈ L). To consider every possible simultaneous transmissions between
relay links, we denote with V the power set of L excluding the empty set and any sets of links
that cannot be active at the same time. Thus, each element v ∈ V is a subset of relay links
that can be active at the same time. Also, we denote with Cij and λij the achievable data rate
and time fraction allocated for a relay link l ij respectively. For the simultaneous transmission
subset v, the achievable data rate and time fraction allocated for a relay link could vary due
to intra-cell interference, hence, the Cij and λij when the relay links in the subset v are active
are denoted by Cijv and λvij respectively. To simplify the notation, let Tr be the total amount of
data transferred from an RS r to the associated SSs during the DL subframe interval as shown
in (27):
Tr = ∑ ∑ Csu λus , ∀r ∈ R. (30)
u∈U s ∈S ru
The objective of the multihop optimal scheme is to maximize the throughput of any active SS
in a cell since the equivalence of the absolute and max-min fairness holds for the multihop
optimal scheme. Finding the maximum achievable throughput of an SS can be formulated as
a linear program as follows:
max Ts . (31)
s ∈S
Subject to:
Ts1 = Ts2 , ∀ s1 , s2 ∈ S ( s1  = s2 ). (32)
+
∑ ∑ Cijv λvij =∑ ∑ v v
Cjk λ jk + Tj , ∀i ∈ R , ∀ j, k ∈ R. (33)
v ∈V l ij ∈v v ∈V l jk ∈v

λu = ∑ λus = ∑ λus , ∀r1+ , r2+ ∈ u, ∀u ∈ U , |Sru+ | > 0, |Sru+ | > 0. (34)

1 1
s ∈S u+ s ∈S u+
r r
1 2

∑ λu + ∑ λv ≤ 1. (35)
u∈U v ∈V
λ = λvl1 = λvl2 ,
v
∀l1 , l2 ∈ v, ∀v ∈ V . (36)
0≤ λus , λr ≤ 1, ∀ u ∈ U , ∀ s ∈ S , ∀r ∈ R . (37)
The first constraint ensures that every active SS in the cell achieves an equal throughput. The
second constraint states that there is no data loss at the RSs: the data transferred from any of
service node i ∈ R+ to an RS j is equal to the sum of data transferred from the RS j to any
of service nodes k ∈ R and data transferred from the RS j to the associated SSs. The third
constraint ensures that resources within the duration of each transmission subset u are fully
utilized by the associated SSs. The forth constraint captures the fact that the sum of access
and relay zone time fractions should be less than or equal to one. The summation of every
time fraction of subset λv is equivalent to the relay zone time fraction. The fifth constraint
ensures that resources within the duration of each transmission subset v are fully utilized
by the associated relay links. The final constraint restricts the amount of each time fraction
allocated to SSs and RSs to be positive and smaller than one. By using these scheduling
constraints (32)-(37), the objective function (31) can be maximized and the cell throughput
with multihop optimal scheduling scheme can be easily computed.
Multihop Relay-Enhanced WiMAX Networks 21

12

11

Cell throughput [Mbps]



10

Two−hop relaying with 3RS

Three−hop relaying with 6RS
8
Three−hop relaying with 9RS

1 5 10 15 20 25
Number of active SSs



(a) Coverage extension scenarios (b) Cell throughput results

Fig. 8. (a) A coverage extension scenario with (i) no RS, (ii) three RSs, (iii) six RSs, (iv) nine
RSs and (b) cell throughput results for different multihop scenarios.

To evaluate the performance of the multihop optimal scheduling scheme, we show two
three-hop relaying scenarios with six and nine RSs respectively. Fig. 8(a) shows how the
RSs are deployed to extend the cell coverage for the two-hop and three-hop scenarios. We
do not assume a hexagonal cell shape in this work, but use it to demonstrate how much
cell coverage can be extended with the increase in the number of hops. For example, when
three RSs are deployed in the two-hop scenario, the extended cell coverage is three times
lager than the cell without RSs. Similarly, the coverage of three-hop scenarios with six and
nine RSs can be five and seven times larger than that of a cell with no RSs. Fig. 8(b) shows
the cell throughput results for two-hop and three-hop relaying scenarios. It is clear that the
cell throughput decreases as the number of hops increases. The throughput increase rates of
three-hop cases are slightly higher than that of the two-hop case as the number of active SSs
increases. When the number of active SSs is 25, the throughput degradations from two-hop
to three-hop with six and nine RSs are approximately 12% and 19% respectively, which is
surprisingly low considering the significant increase in cell coverage.

5. Conclusion
In this chapter we studied the impact of deploying RSs on both capacity and coverage aspects
in relay-enhanced WiMAX networks. In particular, this chapter is composed of two main
parts: Section 3 is targeted at optimizing the placement of transparent RSs that maximize the
cell capacity; Section 4 is focused on cost effective coverage extension in the non-transparent
RS mode. In Section 3, we present the optimal placement of transparent RSs in WiMAX
networks. The results show how various network parameters such as reuse factor, terrain
types, RS antenna gain, and the number of RSs affect the optimal placement of RSs. In Section
4, we explore three different issues with regard to coverage extension scenario. First, we
present three scheduling schemes called orthogonal, overlapped, and optimal to maximize
cell throughput while preserving fairness. The results show that the cell throughput and
outage rate performance can be dramatically enhanced by using the optimal scheduling
scheme. Second, we suggest some design guidelines allowing network operators to achieve
cost-effective coverage extensions without significant throughput degradation. In general, the
22 Will-be-set-by-IN-TECH

lower the relative cost the lower the cell throughput; however, a higher cell throughput can
be achieved with lower relative cost by carefully choosing both location and number of RSs.
Finally, we extend our optimal scheduling scheme to a general multihop relaying scenario in
order to show the impact of an increased number of relay hops on the network performance.

6. References
3GPP (2009). Relay advancements for E-UTRA (LTE-Advanced), TR 36.806, 3rd Generation
Partnership Project (3GPP).
802.16j (2009). IEEE standard air interface for broadband wireless access systems: Multihop
relay specification.
Andrews, J. G., Ghosh, A. & Muhamed, R. (2007). Fundamentals of WiMAX: Understanding
Broadband Wireless Networking, Prentice Hall PTR, Upper Saddle River, NJ, USA.
Deb, S., Mhatre, V. & Ramaiyan, V. (2008). WiMAX relay networks: opportunistic
scheduling to exploit multiuser diversity and frequency selectivity, MOBICOM,
ACM, pp. 163–174.
Erceg, V. & Hari, K. V. S. (2001). Channel models for fixed wireless applications, IEEE 802.16
Broadband Wireless Access Working Group, Technical Report.
Foschini, G. J. & Salz, J. (1983). Digital communications over fading radio channels, Bell System
Tech. J. pp. 429–456.
Kim, Y. & Sichitiu, M. L. (2010a). Cost effective coverage extension in 802.16j mobile multihop
relay networks, WCNC, IEEE, pp. 1–6.
Kim, Y. & Sichitiu, M. L. (2010b). Fairness schemes in 802.16j mobile multihop relay networks,
GLOBECOM 2010, 2010 IEEE Global Telecommunications Conference, pp. 1 –5.
Kim, Y. & Sichitiu, M. L. (2011a). Optimal max-min fair resource allocation in
multihop relay-enhanced WiMAX networks, IEEE Trans. Veh. Technol. accepted. URL:
http://www4.ncsu.edu/∼mlsichit/Research/Publications/wimaxOptimalSchedulingTVT.pdf
Kim, Y. & Sichitiu, M. L. (2011b). Optimal resource allocation in multihop relay-enhanced
WiMAX networks, WCNC, IEEE, pp. 1–6.
Park, K., Ryu, H. S., Kang, C. G., Chang, D., Song, S., Ahn, J. & Ihm, J. (2009). The performance
of relay-enhanced cellular OFDMA-TDD network for mobile broadband wireless
services, EURASIP J. Wirel. Commun. Netw. 2009: 1–10.
Rappaport, T. (2001). Wireless Communications: Principles and Practice, 2nd edn, Prentice Hall
PTR, Upper Saddle River, NJ, USA.
Tassiulas, L. & Sarkar, S. (2002). Max-min fair scheduling in wireless networks, INFOCOM,
Vol. 2, pp. 763–772.
Upase, B. & Hunukumbure, M. (2008). Dimensioning and cost analysis of multihop
relay-enabled WiMAX networks, Fujitsu Sci. Tech. J. 44(3): 303–317.
Zhang, Q. & Kassam, S. (1999). Finite-state Markov model for Rayleigh fading channels, IEEE
Trans. Commun. 47(11): 1688–1692.