# Minimum-Cost QoS-Constrained Deployment and Routing Policies for Wireless Relay Networks

Authors: Frank Yeong-Sung Lin; Chiu-Han Hsiao; Kuo-Chung Chu; Yi-Heng Liu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

With the continued evolution of wireless communication technology, relaying is one of the features proposed for the 4G LTE Advanced (LTE-A) system. The aim of relaying is to enhance both coverage and capacity. The idea of relays is not new, but relaying is being considered to ensure that the optimum performance is achieved to enable the expectations or good quality of service (QoS) of the users to be met while still keeping capital expenditure (CAPEX) within the budgeted bounds of operators. In this paper, we try to stand for an operator to propose a solution that determines where and how many relays should be deployed in the planning stages to minimize the development cost. In the planning stages, we not only derive a multicast tree routing algorithm to both determine and fulfill the QoS requirements to enhance throughput, but we also utilize the Lagrangian relaxation (LR) method in conjunction with optimization-based heuristics and conduct computational experiments to evaluate the performance. Our contribution is utilizing the LR method to propose an optimal solution to minimize the CAPEX of operators to build up a relay network with more efficiency and effectiveness and the QoS can be guaranteed by service level agreement.


---

## Body

## 1. Introduction

Providing a guaranteed service and good performance with budgets constraint is always an optimization problem of operators and vendors. During the last decade, this problem has however become much more difficult, because the traffic has grown significantly and demand for broadband data services is expected to increase tremendously [1]. The business challenges of operators would be that increasing revenues will have to come from nonvoice services which means they have to increase total communication market shares with extending service coverage and offering good service by capacity expansion as well as increased bandwidth and improved quality of services (QoSs) [2]. But building out of the macronetworks significantly will require huge investments, especially where access would otherwise be limited or unavailable without the need for expensive cellular towers. So, the operators may plan to compensate with new revenues and cost reduction at the same time. The aim of this paper is related to the relays should be deployed strategies to investigate how the relays are suitable for providing good services by minimize operator capital expenditure (CAPEX) significantly [3].In the ongoing standardization technology development by third-Generation Partnership Project (3GPP), relaying is one of the features proposed for the LTE Advanced (LTE-A) system [4–8]. The aim of LTE-A relaying is to enhance both coverage and capacity. However, this idea of relays is not new, but the LTE-A relaying is being considered to ensure that the optimum performance is achieved to enable the expectations of the users to be met while still keeping CAPEX within the budgeted bounds. As cell edge performance is becoming more critical, with some of the technologies being pushed towards their limits, it is necessary to look at solutions that will enhance performance at the cell edge for a comparatively low cost. One solution that is being investigated and proposed is that of the use of relays [9–11].In order for the cellular telecommunications technology to be able to keep pace with technologies that may compete, it is necessary to ensure that new cellular technologies are being formulated and developed. But there are many realistic conditions influencing operators including the tough economic environment, declining budgets, limited resources, time pressures, and high user expectations.This paper proposes a solution approach for relay network planning of where to build relays, and how to configure each relay, how the routing algorithm of relays and mobile stations is worked properly. This research can be divided into two parts. First, we constructed the relay network architecture with multicast tree routing concepts. Secondly, we proposed a precise mathematical expression to model this network and developed algorithms based on Lagrangian Relaxation Method to solve this problem. These model approaches might nevertheless be regarded as useful engineering guidelines for operators to build up a good network to extend services and reduce CAPEX efficiently and effectively.This paper is organized as follows. Section2 is Literature Survey, and then we introduce a mathematical formulation for the wireless relay networks design problem in Section 3. In Section 4, we present the solution approach by using Lagrangian Relaxation, in which heuristics for calculating a good primal feasible solution are developed, and conduct computational experiments. In Section 5, we conclude and discuss the direction of future research.


## 2. Literature Survey

Multihop Wireless Networking has been widely studied and implemented throughout ad hoc networks and mesh networks to exploit the user diversity concept and improve overall performance. The original concept of general relaying problems was defined in [12, 13] and was inspired by the development of the ALOHA system at the University of Hawaii. Based on this concept, a relay network can be designed as a tree-based topology with one end of the path being the base station (BS) relaying multiple connections to provide services and improve the coverage.Relay stations (RSs) have some characteristics or cost efficiency for the following reasons.(1)
The transmission range is much less than a BS, meaning that the transmit power is also less than that of a BS. Relays are generally cheaper than BS, meaning reduced costs without site survey and easy to construct relays in the place which is not suitable to build a base station tower.(2)
Relays do not have a wired connection to the backhaul. Instead, they receive signals from the BS and retransmit to destination users wirelessly and vice versa. The leases of wired broadband backhauls can be saved.(3)
Relaying techniques have the dual advantages of performance improvement and coverage extension at the cell edge. These could feasibly be a deployment solution for the high-frequency band in which propagation is significantly more vulnerable to nonline-of-sight (NLOS) conditions to overcome shadowing [14].Coordinated multipoint (CoMP) is a relatively new class of spatial diversity techniques that are enabled by relaying [15, 16] and cooperative communications which is shown in Figure 1 [17, 18]. This concept has been the focus of many studies by 3GPP for LTE-A as well as the IEEE for the WiMAX, 802.16 standards. But still no conclusion about CoMP has been reached regarding the full implementation, because CoMP has not been included in Rel.10 of the 3GPP standards. As the work is ongoing, CoMP is likely to reach a greater level of consensus; when this occurs, it will be included in future releases of the standards.Figure 1
Coordinated multipoint.CoMP is a complex set of techniques which are distributed radios that jointly transmit information in wireless environments. The main purpose may be improved for the reliability of communications in terms of coverage extension, reduced outage probability, symbol-error, or bit-error probability for a given transmission rate [19–21]. It brings many advantages to the user as well as the network operator as follows. (1)
It makes better utilization of network: by providing connections to several BSs or RSs at once, using CoMP, data can be passed through least loaded BS or RS for better resource utilization.(2)
It provides enhanced reception performance: using several sources cooperative BSs or RSs for each connection means that overall reception will be improved and the number of dropped calls should be reduced.(3)
Multiple site reception increases received power: the joint reception from multiple BSs or RSs using CoMP techniques enables the overall received power at the handset to be increased.When building a relay wireless network in a metropolis, various factors influence the design such as QoS requirements, throughput requirements, and total cost. The objective of our research is “to minimize the total building costs subject to QoS and throughput requirements.” Nonetheless, this objective is obviously a tradeoff because total building costs will increase if the QoS and throughput requirements increase. Based on this conventional tradeoff, we take multipath routing algorithms into consideration to solve the critical problem [22, 23].The purpose of this research is different from that of conventional network design problems. The assumptions are that multiple source nodes jointly transmit one single source of information if the signal strength is not robust enough in the link between one source node to the destination. The routing policy is no longer a single path but a more complex and interesting multipath algorithms.


## 3. Problem Formulation

### 3.1. Problem Description

A sequence of the wireless relay network design may be described as fellows. First, the location of each BS could be determined by site survey and how many BSs can cover the service area. Second, the set of BSs roughly divide the entire network into several subnetworks, each of which is rooted by one BS connected to the core network which is shown in Figure2. Meanwhile, there are many candidate locations suitable for the deployment of relays. The decision of deploying a relay at a specific location depends on the users surrounding the location; once a location is selected, the relay must associate with one of the BSs mentioned previously. So that total costs will depend on where relays are developed and how many relays should be developed of the network. But there is another important factor that should be considered by how to provide a good QoS of users at the stage of the network design. This problem may be solved by designing a mechanism or routing algorithm through which users can reach the suitable relays or BSs which can serve users well. In our work, we introduce the multicast tree-based routing algorithm (MTBR) to apply the multipath concept, as represented later.Figure 2
Network separations with several BSs.Figure2 illustrates the entire network design: the triangles represent the BSs; the cell phones represent the mobile stations (MSs); the circles with solid line represent the relay stations being built on the selected locations; and the circles with dotted line represent the locations not selected to build RSs. The whole area is divided into several subnetworks and rooted at associated BSs. If a subnetwork is concerned that each OD pair, like the BS-to-MS, can be expressed in Figure 3, transmits through the routing multicast tree to the associated BS. In DL transmission, data is multicasted from BS to the RSs selected by the MS, and cooperatively relayed to the destination MS to achieve the spatial diversity gains through CoMP techniques. The same routing multicast tree in UL is represented in Figure 4, in which the aggregation of traffic from the MS can overcome the weak signal strength when the MS is far from the BS or RSs. Because the channels, bandwidth, and even transmission power are different between DL and UL, the DL tree and UL tree of an MS may be different. In this paper, we derive a near optimal RSs development policy to minimize total development costs; we also maintain both DL and UL spanning trees and use the MTBR to ensure that BER and data rate requirements of each MS are satisfied.Figure 3
One OD pair routing multicast tree in DL transmission.Figure 4
One OD pair routing multicast tree in UL transmission.


### 3.2. Mathematical Modeling

Assumption
(i)
The relaying protocol in this model isDecode-and-Forward.
(ii)
Once a location is selected to build an RS, it must home to one BS.
(iii)
Each MS must home to either a BS or RS(s).
(iv)
The RSs selected by an MS must associate with the same BS.
(v)
The routing path of each OD pair in DL (UL) is a multicast tree.
(vi)
The capacity of a linkuv is decided by adaptive modulation with respect to the signal-to-noise ratio (SNR) received at node v.
(vii)
The spatial diversity gains are represented by the aggregate SNR with CoMP techniques.
(viii)
The bit error rate (BER) of a transmission is measured by the receiving SNR value
(ix)
The aggregate BER of the destination is the summation of BER of each node on the routing multicast tree.
(x)
The numbers of links of each path adopted by each MS are assumed to be equal to ensure that the CoMP can be achieved within limited delay.
(xi)
Error corrections and retransmissions are not considered in this problem.Given
(i)
The set of BSs, candidate locations and configurations of RSs, MSs,
(ii)
required data rate of an MS in DL and UL,
(iii)
fixed and configured cost of an RS,
(iv)
the set of all spanning trees, paths,
(v)
distance of each link,
(vi)
attenuation factor,
(vii)
thermal noise function,
(viii)
transmit power of BS, RS, and MS,
(ix)
sNR function,
(x)
the minimum SNR requirement for an MS in DL and UL to home to a BS or an RS,
(xi)
the maximum BER threshold of a OD pair transmission in DL and UL,
(xii)
nodal and link capacity functions,
(xiii)
the maximum spatial diversity of an MS in DL and UL.Objective. To minimize the total cost of wireless relay network deployment.Subject to
(i)
RS selection constraints,
(ii)
nodal capacity constraints,
(iii)
cooperative relaying constraints in DL and UL,
(iv)
routing constraints in DL and UL,
(v)
link capacity constraints in DL and UL.To Determine
(i)
Whether or not a location should be selected to build an RS,
(ii)
the cooperative RSs of each MS,
(iii)
the routing paths of an OD pair (a BS to an MS or contrary), which form a multicast tree from the BS to the cooperative RSs selected by each MS.Objective Function
(
IP
1
)
min
∑
r
∈
R
∑
k
∈
K
(
ψ
r
+
Φ
r
(
k
)
)
η
r
kSubject toRelay Selection Constraints
(1)
∑
k
∈
K
η
r
k
≤
1
∀
r
∈
R
,
(2)
∑
b
∈
B
h
r
b
dir
≤
1
∀
r
∈
R
,
dir
∈
DIR,
(3)
∑
b
∈
B
h
r
b
dir
≤
∑
k
∈
K
η
r
k
∀
r
∈
R
,
dir
∈
DIR
.Nodal Capacity Constraints
(4)
∑
u
∈
{
R
∪
B
}
∑
n
∈
N
y
n
u
r
1
θ
n
1
+
∑
w
∪
{
R
∪
B
}
∑
n
∈
N
y
n
r
w
2
θ
n
2
≤
∑
k
∈
K
η
r
k
C
r
(
k
)
¯
∀
r
∈
R
,
(5)
∑
r
∈
R
∑
n
∈
N
y
n
b
r
1
θ
n
1
+
∑
i
∈
R
∑
n
∈
N
y
n
i
b
2
θ
n
2
+
∑
n
∈
N
∑
dir
∈
DIR
κ
n
b
dir
θ
n
dir
≤
C
b
¯
∀
b
∈
B
.Cooperative Relay Constraints
(6)
κ
n
r
dir
≤
∑
k
∈
K
η
r
k
∀
n
∈
N
,
r
∈
R
,
dir
∈
DIR
,
(7)
∑
b
∈
B
κ
n
b
dir
+
κ
n
r
dir
≤
1
∀
n
∈
N
,
r
∈
R
,
dir
∈
DIR
,
(8)
1
≤
∑
s
∈
{
R
∪
B
}
κ
n
s
dir
∀
n
∈
N
,
dir
∈
DIR,
(9)
∑
r
∈
R
κ
n
r
dir
≤
S
D
dir
∀
n
∈
N
,
dir
∈
DIR,
(10)
κ
n
s
1
P
min
N
≤
κ
n
s
1
π
s
n
1
∀
n
∈
N
,
s
∈
{
R
∪
B
}
,
(11)
κ
n
s
2
P
min
R
≤
κ
n
s
2
π
n
s
2
∀
n
∈
N
,
s
∈
{
R
∪
B
}
,
(12)
ω
n
≤
∑
s
∈
{
R
∪
B
}
κ
n
s
1
π
s
n
1
∀
n
∈
N
,
(13)
0
≤
π
s
n
dir
≤
π
n
¯
∀
s
∈
{
R
∪
B
}
,
n
∈
N
,
dir
∈
DIR,
(14)
κ
n
s
1
π
s
n
1
≤
∑
k
∈
K
η
s
k
[
P
(
ρ
s
1
(
k
)
,
D
s
n
,
τ
)
-
P
N
(
n
)
]
∀
s
∈
{
R
∪
B
}
,
n
∈
N
,
(15)
κ
n
s
2
π
n
s
2
≤
∑
k
∈
K
η
s
k
[
P
(
ρ
n
N
,
D
n
s
,
τ
)
-
P
N
(
s
)
]
∀
s
∈
{
R
∪
B
}
,
n
∈
N
,
(16)
y
n
u
v
dir
P
min
R
≤
y
n
u
v
dir
ϕ
u
v
dir
∀
n
∈
N
,
u
,
v
∈
{
R
∪
B
}
,
dir
∈
DIR,
(17)
ε
n
v
≤
∑
u
∈
{
R
∪
B
}
y
n
u
v
2
ϕ
u
v
2
∀
n
∈
N
,
v
∈
{
R
∪
B
}
,
(18)
0
≤
ϕ
u
v
dir
≤
ϕ
v
¯
∀
u
,
v
∈
{
R
∪
B
}
,
dir
∈
DIR
,
(19)
y
n
u
v
dir
ϕ
u
v
dir
≤
∑
k
∈
K
η
u
k
[
P
(
ρ
u
dir
(
k
)
,
D
u
v
,
τ
)
-
P
N
(
v
)
]
∀
n
∈
N
,
u
,
v
∈
{
R
∪
B
}
, dir
∈
DIR,
(20)
∑
u
∈
{
R
∪
B
}
∑
v
∈
{
R
∪
B
}
y
n
u
v
1
BER
(
ϕ
u
v
1
)
+
BER
(
ω
n
)
≤
BE
R
1
∀
n
∈
N
,
(21)
∑
v
∈
{
R
∪
B
}
BER
(
ε
n
v
)
+
∑
s
∈
{
R
∪
B
}
BER
(
κ
n
s
2
π
n
s
2
)
≤
BE
R
2
∀
n
∈
N
.Routing Constraints
(22)
κ
n
r
dir
≤
h
r
b
dir
∀
n
∈
N
,
r
∈
R
,
b
∈
B
,
dir
∈
DIR,
(23)
h
r
b
dir
≤
∑
p
∈
P
b
r
x
n
r
p
dir
∀
n
∈
N
,
b
∈
B
,
dir
∈
DIR,
(24)
∑
b
∈
B
∑
p
∈
P
b
r
x
n
r
p
dir
≤
1
∀
n
∈
N
,
r
∈
R
,
dir
∈
DIR,
(25)
∑
p
∈
P
b
i
∑
u
∈
{
R
∪
B
}
∑
v
∈
{
R
∪
B
}
x
n
i
p
dir
δ
p
u
v
≤
∑
p
∈
P
b
j
∑
u
∈
{
R
∪
B
}
∑
v
∈
{
R
∪
B
}
x
n
j
p
dir
δ
p
u
v
+
(
1
-
κ
n
j
dir
)
M
¯
∀
n
∈
N
,
i
,
j
∈
R
,
b
∈
B
,
dir
∈
DIR,
(26)
y
n
u
v
1
≤
∑
k
∈
K
η
v
k
∀
n
∈
N
,
u
∈
{
R
∪
B
}
,
v
∈
R
,
(27)
y
n
u
v
2
≤
∑
k
∈
K
η
u
k
∀
n
∈
N
,
u
∈
R
,
v
∈
{
R
∪
B
}
,
(28)
∑
b
∈
B
∑
p
∈
P
b
r
x
n
r
p
dir
δ
p
u
v
≤
y
n
u
v
dir
∀
n
∈
N
,
r
∈
R
,
u
,
v
∈
{
R
∪
B
}
,
dir
∈
DIR
.Link Capacity Constraints
(29)
∑
n
∈
N
y
n
u
v
dir
θ
n
dir
≤
C
u
v
(
ϕ
u
v
dir
)
,
∀
u
,
v
∈
{
R
∪
B
}
,
dir
∈
DIRInteger Constraints
(30)
η
r
k
=
0
or
1
∀
r
∈
R
,
k
∈
K
,
h
r
b
dir
=
0
or
1
∀
r
∈
R
,
b
∈
B
,
dir
∈
DIR,
κ
n
s
dir
=
0
or
1
∀
n
∈
N
,
s
∈
{
R
∪
B
}
,
dir
∈
DIR
,
x
n
r
p
dir
=
0
or
1
∀
n
∈
N
,
r
∈
R
,
p
∈
P
b
r
,
b
∈
B
,
dir
∈
DIR,
y
n
u
v
dir
=
0
or
1
∀
n
∈
N
,
u
,
v
∈
{
R
∪
B
}
,
dir
∈
DIR.Explanation of Objective Function. The objective function (IP) is to minimize the total cost of RSs deployment: (1) Fix costs of RS such as land acquisition and hardware purchases; (2) The configured costs of each RS. The detail parameters in the formulation are noted and shown in Tables 1 and 2.Table 1
Notations of given parameters.
Given parameters
Notation
Description
General
DIR
The set of transmission direction, wheredir∈DIR, DIR = {1 (downlink), 2 (uplink)}
B
The set of BSs, whereb∈B
R
The set of RS candidate locations, wherer∈R
K
The set of RS configurations, wherek∈K
N
The set of MCs, wheren∈N
θ
n
dir
The data rate required to be transmitted of MCn in direction dir in (packets/sec)
ψ
r
The fix cost of building an RS on locationr
Φ
r
(
k
)
The configured cost of building RSr, which is a function of configuration k
M
¯
An arbitrarily large number
Routing
P
b
r
The set of paths from BSb to RS r, where p∈Pbr
δ
p
u
v
The indicator function which is 1 if linkuv is on path p and 0 otherwise
SNR and attenuation
D
u
v
The distance of linkuv
τ
Attenuation factor
ρ
r
dir
(
k
)
Transmit power of RSr in direction dir, which is a function of configuration k
P
N
(
s
)
Thermal noise strength function in dBm/Hz, wheres∈{N,R,B} represents receiving node type.
ρ
b
B
Transmit power of BSb
ρ
n
N
Transmit power of MCn
P
(
ρ
u
dir
(
k
)
,
D
u
v
,
τ
)
Signal strength received by nodev in dBm, which is a function of ρrdir(k), Duv and τ
P
min
N
The minimum SNR requirement for a MC to receive from a RS in DL
P
min
R
The minimum SNR requirement for a RS to receive from a MC in UL
ϕ
¯
v
The maximum SNR can be received by nodev in link uv, where u,v∈{R∪B}
π
¯
v
The maximum SNR can be received by nodev in link uv, where u∈{R∪B},v∈N in DL; and u∈N,v∈{R∪B} in UL
BER
BER
dir
The BER requirement for the transmission received by a  destination in directiondir where the destination in DL is MC and in UL is BS
BER
(
SNR
s
)
The BER value of each nodes, which is a function of the receiving SNR, where s∈{R∪B∪N}
Capacity
C
b
¯
The nodal capacity of BSb in (packets/sec)
C
r
(
k
)
¯
The nodal capacity of RSr in (packets/sec), which is a function of configuration k
C
u
v
(
SNR
)
The capacity of linkuv in (packets/sec), which is a function of the receiving SNR of node v, where u,v∈{R∪B}
Relaying
SD
dir
The maximum spatial diversity of a MC in directiondirTable 2
Notations of decision variables.
Notation
Description
Decision variables
η
r
k
1 if candidate locationr is selected to build a RS with configuration k and 0 otherwise
h
r
b
dir
1 if RSr associates with BS b in direction dir and 0 otherwise
κ
n
s
dir
1 if nodes is selected to cooperatively relay the transmission of MC n in direction dir and 0 otherwise, where s∈{R∪B}
y
n
u
v
dir
1 if linkuv is on the multicast tree adopted by MC n in direction dir and 0 otherwise
x
n
r
p
dir
1 if pathp is selected for MC n to cooperative RS r in direction dir and 0 otherwise, where p∈Pbr
Auxiliary variables
ϕ
u
v
dir
The SNR received by nodev in link uv, where u,v∈{R∪B}
π
u
v
dir
The SNR received by nodev in link uv, where u∈{R∪B},v∈N in DL; and u∈N,v∈{R∪B} in UL
ω
n
The summation of SNR received by MCn in DL
ε
n
s
The summation of SNR received by nodes in UL oriented by MC n, where s∈{R∪B}Explanation of Constraint(1) Relay Assignment Constraints. Constraint (1) requires that each location is selected to install an RS with exactly only one configuration or none.Constraint (2) requires that each RS can associate with one BS or none in direction dir.Constraint (3) indicates that once an RS r associates with a BS, r must be built.(2) Nodal Capacity Constraints. Constraint (4) requires that each RS’s total amount of traffic in DL and UL cannot be greater than its nodal capacity.Constraint (5) requires that each BS’s total amount of traffic in DL and UL cannot be greater than its nodal capacity.(3) Cooperative Relay Constraints. Each MC will select an RS r in direction dir  only if r is installed in (6).An MC must select either one BS or RS(s) in directiondir in (7).Constraints (8) and (9) represent the boundaries of the number of cooperative RSs an MC can select.The minimum SNR constraints for an MC to receive from a BS or an RS in DL, and for an MC to transmit to a BS or an RS in UL, are expressed in (10) and (11), respectively.Constraint (12) requires that the SNR value received by an MC n in DL cannot exceed the summation of the SNR values n receives from the cooperative RSs selected by n.Constraint (13) represents the boundaries of decision variable πuvdir.Once MCn selects RS (or BS) s to be its cooperative RS, the SNR value on link ns cannot exceed the SNR transmitted from source node to destination node in DL and UL in constraints (14) and (15).The minimum SNR constraint for a linkuv selected by MC n is expressed in (16), while u,v∈{R∪B}.Constraint (17) requires that the SNR value received by an RS (or BS) v in UL cannot exceed the summation of the SNR values on the link uv selected by MC n.Constraint (18) represents the boundaries of decision variable ϕuvdir.Once MCn selects a link uv in direction dir, the SNR value on uv cannot exceed the SNR transmitted from u to v in (19).The aggregative BERs constraints for DL in MC and UL in BS are expressed in (20) and (21), respectively.(4) Routing Constraints. Constraint (22) requires that once RS r is selected by MC n, r must associate with one BS in direction dir.Constraint (23) requires that once RS r associates with BS b in direction dir, the paths from b to r must be selected by one or more than one MC.Constraint (24) requires that there is exactly one path to be selected by an MC from the associated BS to RS r only if the MC selects RS r in direction dir.There are two constructions in (24): first, every two RSs selected by an MC must associate with the same BS; second, the numbers of links of every two paths selected by an MC must be the same.For each MC, every receiving RSv on a link uv in DL is installed in (26) and every transmitting RS u on a link uv in UL is installed in (27).Constraint (28) requires that, if link uv is on the path p adopted by the MC n to reach RS r in direction dir, then ynuvdir must be 1.(5) Link Capacity Constraints. The aggregate flow of link uv in direction dir is restricted in (29).(6) Integer Constraint. Constraints (30) are integer properties of the decision variables.


## 3.1. Problem Description

A sequence of the wireless relay network design may be described as fellows. First, the location of each BS could be determined by site survey and how many BSs can cover the service area. Second, the set of BSs roughly divide the entire network into several subnetworks, each of which is rooted by one BS connected to the core network which is shown in Figure2. Meanwhile, there are many candidate locations suitable for the deployment of relays. The decision of deploying a relay at a specific location depends on the users surrounding the location; once a location is selected, the relay must associate with one of the BSs mentioned previously. So that total costs will depend on where relays are developed and how many relays should be developed of the network. But there is another important factor that should be considered by how to provide a good QoS of users at the stage of the network design. This problem may be solved by designing a mechanism or routing algorithm through which users can reach the suitable relays or BSs which can serve users well. In our work, we introduce the multicast tree-based routing algorithm (MTBR) to apply the multipath concept, as represented later.Figure 2
Network separations with several BSs.Figure2 illustrates the entire network design: the triangles represent the BSs; the cell phones represent the mobile stations (MSs); the circles with solid line represent the relay stations being built on the selected locations; and the circles with dotted line represent the locations not selected to build RSs. The whole area is divided into several subnetworks and rooted at associated BSs. If a subnetwork is concerned that each OD pair, like the BS-to-MS, can be expressed in Figure 3, transmits through the routing multicast tree to the associated BS. In DL transmission, data is multicasted from BS to the RSs selected by the MS, and cooperatively relayed to the destination MS to achieve the spatial diversity gains through CoMP techniques. The same routing multicast tree in UL is represented in Figure 4, in which the aggregation of traffic from the MS can overcome the weak signal strength when the MS is far from the BS or RSs. Because the channels, bandwidth, and even transmission power are different between DL and UL, the DL tree and UL tree of an MS may be different. In this paper, we derive a near optimal RSs development policy to minimize total development costs; we also maintain both DL and UL spanning trees and use the MTBR to ensure that BER and data rate requirements of each MS are satisfied.Figure 3
One OD pair routing multicast tree in DL transmission.Figure 4
One OD pair routing multicast tree in UL transmission.


## 3.2. Mathematical Modeling

Assumption
(i)
The relaying protocol in this model isDecode-and-Forward.
(ii)
Once a location is selected to build an RS, it must home to one BS.
(iii)
Each MS must home to either a BS or RS(s).
(iv)
The RSs selected by an MS must associate with the same BS.
(v)
The routing path of each OD pair in DL (UL) is a multicast tree.
(vi)
The capacity of a linkuv is decided by adaptive modulation with respect to the signal-to-noise ratio (SNR) received at node v.
(vii)
The spatial diversity gains are represented by the aggregate SNR with CoMP techniques.
(viii)
The bit error rate (BER) of a transmission is measured by the receiving SNR value
(ix)
The aggregate BER of the destination is the summation of BER of each node on the routing multicast tree.
(x)
The numbers of links of each path adopted by each MS are assumed to be equal to ensure that the CoMP can be achieved within limited delay.
(xi)
Error corrections and retransmissions are not considered in this problem.Given
(i)
The set of BSs, candidate locations and configurations of RSs, MSs,
(ii)
required data rate of an MS in DL and UL,
(iii)
fixed and configured cost of an RS,
(iv)
the set of all spanning trees, paths,
(v)
distance of each link,
(vi)
attenuation factor,
(vii)
thermal noise function,
(viii)
transmit power of BS, RS, and MS,
(ix)
sNR function,
(x)
the minimum SNR requirement for an MS in DL and UL to home to a BS or an RS,
(xi)
the maximum BER threshold of a OD pair transmission in DL and UL,
(xii)
nodal and link capacity functions,
(xiii)
the maximum spatial diversity of an MS in DL and UL.Objective. To minimize the total cost of wireless relay network deployment.Subject to
(i)
RS selection constraints,
(ii)
nodal capacity constraints,
(iii)
cooperative relaying constraints in DL and UL,
(iv)
routing constraints in DL and UL,
(v)
link capacity constraints in DL and UL.To Determine
(i)
Whether or not a location should be selected to build an RS,
(ii)
the cooperative RSs of each MS,
(iii)
the routing paths of an OD pair (a BS to an MS or contrary), which form a multicast tree from the BS to the cooperative RSs selected by each MS.Objective Function
(
IP
1
)
min
∑
r
∈
R
∑
k
∈
K
(
ψ
r
+
Φ
r
(
k
)
)
η
r
kSubject toRelay Selection Constraints
(1)
∑
k
∈
K
η
r
k
≤
1
∀
r
∈
R
,
(2)
∑
b
∈
B
h
r
b
dir
≤
1
∀
r
∈
R
,
dir
∈
DIR,
(3)
∑
b
∈
B
h
r
b
dir
≤
∑
k
∈
K
η
r
k
∀
r
∈
R
,
dir
∈
DIR
.Nodal Capacity Constraints
(4)
∑
u
∈
{
R
∪
B
}
∑
n
∈
N
y
n
u
r
1
θ
n
1
+
∑
w
∪
{
R
∪
B
}
∑
n
∈
N
y
n
r
w
2
θ
n
2
≤
∑
k
∈
K
η
r
k
C
r
(
k
)
¯
∀
r
∈
R
,
(5)
∑
r
∈
R
∑
n
∈
N
y
n
b
r
1
θ
n
1
+
∑
i
∈
R
∑
n
∈
N
y
n
i
b
2
θ
n
2
+
∑
n
∈
N
∑
dir
∈
DIR
κ
n
b
dir
θ
n
dir
≤
C
b
¯
∀
b
∈
B
.Cooperative Relay Constraints
(6)
κ
n
r
dir
≤
∑
k
∈
K
η
r
k
∀
n
∈
N
,
r
∈
R
,
dir
∈
DIR
,
(7)
∑
b
∈
B
κ
n
b
dir
+
κ
n
r
dir
≤
1
∀
n
∈
N
,
r
∈
R
,
dir
∈
DIR
,
(8)
1
≤
∑
s
∈
{
R
∪
B
}
κ
n
s
dir
∀
n
∈
N
,
dir
∈
DIR,
(9)
∑
r
∈
R
κ
n
r
dir
≤
S
D
dir
∀
n
∈
N
,
dir
∈
DIR,
(10)
κ
n
s
1
P
min
N
≤
κ
n
s
1
π
s
n
1
∀
n
∈
N
,
s
∈
{
R
∪
B
}
,
(11)
κ
n
s
2
P
min
R
≤
κ
n
s
2
π
n
s
2
∀
n
∈
N
,
s
∈
{
R
∪
B
}
,
(12)
ω
n
≤
∑
s
∈
{
R
∪
B
}
κ
n
s
1
π
s
n
1
∀
n
∈
N
,
(13)
0
≤
π
s
n
dir
≤
π
n
¯
∀
s
∈
{
R
∪
B
}
,
n
∈
N
,
dir
∈
DIR,
(14)
κ
n
s
1
π
s
n
1
≤
∑
k
∈
K
η
s
k
[
P
(
ρ
s
1
(
k
)
,
D
s
n
,
τ
)
-
P
N
(
n
)
]
∀
s
∈
{
R
∪
B
}
,
n
∈
N
,
(15)
κ
n
s
2
π
n
s
2
≤
∑
k
∈
K
η
s
k
[
P
(
ρ
n
N
,
D
n
s
,
τ
)
-
P
N
(
s
)
]
∀
s
∈
{
R
∪
B
}
,
n
∈
N
,
(16)
y
n
u
v
dir
P
min
R
≤
y
n
u
v
dir
ϕ
u
v
dir
∀
n
∈
N
,
u
,
v
∈
{
R
∪
B
}
,
dir
∈
DIR,
(17)
ε
n
v
≤
∑
u
∈
{
R
∪
B
}
y
n
u
v
2
ϕ
u
v
2
∀
n
∈
N
,
v
∈
{
R
∪
B
}
,
(18)
0
≤
ϕ
u
v
dir
≤
ϕ
v
¯
∀
u
,
v
∈
{
R
∪
B
}
,
dir
∈
DIR
,
(19)
y
n
u
v
dir
ϕ
u
v
dir
≤
∑
k
∈
K
η
u
k
[
P
(
ρ
u
dir
(
k
)
,
D
u
v
,
τ
)
-
P
N
(
v
)
]
∀
n
∈
N
,
u
,
v
∈
{
R
∪
B
}
, dir
∈
DIR,
(20)
∑
u
∈
{
R
∪
B
}
∑
v
∈
{
R
∪
B
}
y
n
u
v
1
BER
(
ϕ
u
v
1
)
+
BER
(
ω
n
)
≤
BE
R
1
∀
n
∈
N
,
(21)
∑
v
∈
{
R
∪
B
}
BER
(
ε
n
v
)
+
∑
s
∈
{
R
∪
B
}
BER
(
κ
n
s
2
π
n
s
2
)
≤
BE
R
2
∀
n
∈
N
.Routing Constraints
(22)
κ
n
r
dir
≤
h
r
b
dir
∀
n
∈
N
,
r
∈
R
,
b
∈
B
,
dir
∈
DIR,
(23)
h
r
b
dir
≤
∑
p
∈
P
b
r
x
n
r
p
dir
∀
n
∈
N
,
b
∈
B
,
dir
∈
DIR,
(24)
∑
b
∈
B
∑
p
∈
P
b
r
x
n
r
p
dir
≤
1
∀
n
∈
N
,
r
∈
R
,
dir
∈
DIR,
(25)
∑
p
∈
P
b
i
∑
u
∈
{
R
∪
B
}
∑
v
∈
{
R
∪
B
}
x
n
i
p
dir
δ
p
u
v
≤
∑
p
∈
P
b
j
∑
u
∈
{
R
∪
B
}
∑
v
∈
{
R
∪
B
}
x
n
j
p
dir
δ
p
u
v
+
(
1
-
κ
n
j
dir
)
M
¯
∀
n
∈
N
,
i
,
j
∈
R
,
b
∈
B
,
dir
∈
DIR,
(26)
y
n
u
v
1
≤
∑
k
∈
K
η
v
k
∀
n
∈
N
,
u
∈
{
R
∪
B
}
,
v
∈
R
,
(27)
y
n
u
v
2
≤
∑
k
∈
K
η
u
k
∀
n
∈
N
,
u
∈
R
,
v
∈
{
R
∪
B
}
,
(28)
∑
b
∈
B
∑
p
∈
P
b
r
x
n
r
p
dir
δ
p
u
v
≤
y
n
u
v
dir
∀
n
∈
N
,
r
∈
R
,
u
,
v
∈
{
R
∪
B
}
,
dir
∈
DIR
.Link Capacity Constraints
(29)
∑
n
∈
N
y
n
u
v
dir
θ
n
dir
≤
C
u
v
(
ϕ
u
v
dir
)
,
∀
u
,
v
∈
{
R
∪
B
}
,
dir
∈
DIRInteger Constraints
(30)
η
r
k
=
0
or
1
∀
r
∈
R
,
k
∈
K
,
h
r
b
dir
=
0
or
1
∀
r
∈
R
,
b
∈
B
,
dir
∈
DIR,
κ
n
s
dir
=
0
or
1
∀
n
∈
N
,
s
∈
{
R
∪
B
}
,
dir
∈
DIR
,
x
n
r
p
dir
=
0
or
1
∀
n
∈
N
,
r
∈
R
,
p
∈
P
b
r
,
b
∈
B
,
dir
∈
DIR,
y
n
u
v
dir
=
0
or
1
∀
n
∈
N
,
u
,
v
∈
{
R
∪
B
}
,
dir
∈
DIR.Explanation of Objective Function. The objective function (IP) is to minimize the total cost of RSs deployment: (1) Fix costs of RS such as land acquisition and hardware purchases; (2) The configured costs of each RS. The detail parameters in the formulation are noted and shown in Tables 1 and 2.Table 1
Notations of given parameters.
Given parameters
Notation
Description
General
DIR
The set of transmission direction, wheredir∈DIR, DIR = {1 (downlink), 2 (uplink)}
B
The set of BSs, whereb∈B
R
The set of RS candidate locations, wherer∈R
K
The set of RS configurations, wherek∈K
N
The set of MCs, wheren∈N
θ
n
dir
The data rate required to be transmitted of MCn in direction dir in (packets/sec)
ψ
r
The fix cost of building an RS on locationr
Φ
r
(
k
)
The configured cost of building RSr, which is a function of configuration k
M
¯
An arbitrarily large number
Routing
P
b
r
The set of paths from BSb to RS r, where p∈Pbr
δ
p
u
v
The indicator function which is 1 if linkuv is on path p and 0 otherwise
SNR and attenuation
D
u
v
The distance of linkuv
τ
Attenuation factor
ρ
r
dir
(
k
)
Transmit power of RSr in direction dir, which is a function of configuration k
P
N
(
s
)
Thermal noise strength function in dBm/Hz, wheres∈{N,R,B} represents receiving node type.
ρ
b
B
Transmit power of BSb
ρ
n
N
Transmit power of MCn
P
(
ρ
u
dir
(
k
)
,
D
u
v
,
τ
)
Signal strength received by nodev in dBm, which is a function of ρrdir(k), Duv and τ
P
min
N
The minimum SNR requirement for a MC to receive from a RS in DL
P
min
R
The minimum SNR requirement for a RS to receive from a MC in UL
ϕ
¯
v
The maximum SNR can be received by nodev in link uv, where u,v∈{R∪B}
π
¯
v
The maximum SNR can be received by nodev in link uv, where u∈{R∪B},v∈N in DL; and u∈N,v∈{R∪B} in UL
BER
BER
dir
The BER requirement for the transmission received by a  destination in directiondir where the destination in DL is MC and in UL is BS
BER
(
SNR
s
)
The BER value of each nodes, which is a function of the receiving SNR, where s∈{R∪B∪N}
Capacity
C
b
¯
The nodal capacity of BSb in (packets/sec)
C
r
(
k
)
¯
The nodal capacity of RSr in (packets/sec), which is a function of configuration k
C
u
v
(
SNR
)
The capacity of linkuv in (packets/sec), which is a function of the receiving SNR of node v, where u,v∈{R∪B}
Relaying
SD
dir
The maximum spatial diversity of a MC in directiondirTable 2
Notations of decision variables.
Notation
Description
Decision variables
η
r
k
1 if candidate locationr is selected to build a RS with configuration k and 0 otherwise
h
r
b
dir
1 if RSr associates with BS b in direction dir and 0 otherwise
κ
n
s
dir
1 if nodes is selected to cooperatively relay the transmission of MC n in direction dir and 0 otherwise, where s∈{R∪B}
y
n
u
v
dir
1 if linkuv is on the multicast tree adopted by MC n in direction dir and 0 otherwise
x
n
r
p
dir
1 if pathp is selected for MC n to cooperative RS r in direction dir and 0 otherwise, where p∈Pbr
Auxiliary variables
ϕ
u
v
dir
The SNR received by nodev in link uv, where u,v∈{R∪B}
π
u
v
dir
The SNR received by nodev in link uv, where u∈{R∪B},v∈N in DL; and u∈N,v∈{R∪B} in UL
ω
n
The summation of SNR received by MCn in DL
ε
n
s
The summation of SNR received by nodes in UL oriented by MC n, where s∈{R∪B}Explanation of Constraint(1) Relay Assignment Constraints. Constraint (1) requires that each location is selected to install an RS with exactly only one configuration or none.Constraint (2) requires that each RS can associate with one BS or none in direction dir.Constraint (3) indicates that once an RS r associates with a BS, r must be built.(2) Nodal Capacity Constraints. Constraint (4) requires that each RS’s total amount of traffic in DL and UL cannot be greater than its nodal capacity.Constraint (5) requires that each BS’s total amount of traffic in DL and UL cannot be greater than its nodal capacity.(3) Cooperative Relay Constraints. Each MC will select an RS r in direction dir  only if r is installed in (6).An MC must select either one BS or RS(s) in directiondir in (7).Constraints (8) and (9) represent the boundaries of the number of cooperative RSs an MC can select.The minimum SNR constraints for an MC to receive from a BS or an RS in DL, and for an MC to transmit to a BS or an RS in UL, are expressed in (10) and (11), respectively.Constraint (12) requires that the SNR value received by an MC n in DL cannot exceed the summation of the SNR values n receives from the cooperative RSs selected by n.Constraint (13) represents the boundaries of decision variable πuvdir.Once MCn selects RS (or BS) s to be its cooperative RS, the SNR value on link ns cannot exceed the SNR transmitted from source node to destination node in DL and UL in constraints (14) and (15).The minimum SNR constraint for a linkuv selected by MC n is expressed in (16), while u,v∈{R∪B}.Constraint (17) requires that the SNR value received by an RS (or BS) v in UL cannot exceed the summation of the SNR values on the link uv selected by MC n.Constraint (18) represents the boundaries of decision variable ϕuvdir.Once MCn selects a link uv in direction dir, the SNR value on uv cannot exceed the SNR transmitted from u to v in (19).The aggregative BERs constraints for DL in MC and UL in BS are expressed in (20) and (21), respectively.(4) Routing Constraints. Constraint (22) requires that once RS r is selected by MC n, r must associate with one BS in direction dir.Constraint (23) requires that once RS r associates with BS b in direction dir, the paths from b to r must be selected by one or more than one MC.Constraint (24) requires that there is exactly one path to be selected by an MC from the associated BS to RS r only if the MC selects RS r in direction dir.There are two constructions in (24): first, every two RSs selected by an MC must associate with the same BS; second, the numbers of links of every two paths selected by an MC must be the same.For each MC, every receiving RSv on a link uv in DL is installed in (26) and every transmitting RS u on a link uv in UL is installed in (27).Constraint (28) requires that, if link uv is on the path p adopted by the MC n to reach RS r in direction dir, then ynuvdir must be 1.(5) Link Capacity Constraints. The aggregate flow of link uv in direction dir is restricted in (29).(6) Integer Constraint. Constraints (30) are integer properties of the decision variables.


## 4. Solution Approach and Computational Experiments

### 4.1. Lagrangian Relaxation Techniques

By applying the Lagrangian Relaxation (LR) Method and the Subgradient Method to solve the complex problem, based on the problem formulation mentioned previously, the first step would be that the constraints of the primal problem are relaxed by using the LR Method [26]. In this step, we can not only determine a theoretical lower bound of the primal problem, but, can also glean some hints of feasible solutions captured by the primal problems. After iterations, the end result of the Lagrangian Relaxation Problem is guaranteed to a feasible solution by a feasible step which is satisfied with all constraints of the primal problem, if not, we have to make some modifications.


### 4.2. Getting Primal Feasible Heuristics

To obtain the primal feasible solutions for(IP1), the first step is considered the solutions to the Lagrangian Relaxation. Two major decision variables, κnsdir and ynuvdir are taken into consideration. According to κnsdir, the RS(s) (or BS) can be obtained to serve MS n selected in dir direction, and ynuvdir represents the link uv which n selected on the routing multicast tree in dir direction. In addition to κnsdir and ynuvdir, for the complexity of this problem including five 0-1 integer decision variables, we still need other clues to help solving this problem in good quality. Thus, the coefficient μns14+∑b∈Bμnsb115+PminNμns5+M¯∑i∈R∑b∈Bμnisb116-πsn1(μns5+μn7-μns8) of κns1 in DL, namely, Cκ1; μnr24+∑b∈Bμnrb215+PminRμnr6+M¯∑i∈R∑b∈Bμnirb216-πnr2(μnr6-μnr9)+μn14BEP(πnr2) of κns2 in UL, namely, Cκ2 is introduced in our solution to sort κnsdir for further calculations.The main purpose of determining the primal feasible heuristic is, in both DL and UL directions, and for each MS sorted by the distance to BS, to fully utilize the RSs built already to meet the BER requirement, and if not, to at least minimize the number of RSs necessary to reach the previous goal. The detailed procedure that decomposites the Lagrangian Relaxation Problem into several subproblems is described in the appendix.


### 4.3. Experiments Environment

In this session, we conduct several computational experiments to justify the proposed algorithms. Due to limitation of available experiment scenarios and parameters, we focus on IEEE 802.16j instead of LTE-A; it is easier to build the network based on realistic and operable environment parameters. In order to effectively analyze the physical operations of an 802.16j network, Table3 lists all system parameters utilized in this research with reference to “Mobile WiMAX” published by WiMAX forum. Adaptive Modulation and Coding (AMS) applied in 802.16j is illustrated specifically in Table 4 with the same reference to “Mobile WiMAX.”Table 3
System parameters [24, 25].
Parameters
Value
Operation frequency
2500 MHz
Channel bandwidth
10 MHz
BS antenna gain
15 dBi
RS basic antenna gain
5 dBi
MS antenna gain
−1 dBi
BS noise figure
4 dB
RS noise figure
5 dB
MS noise figure
7 dB
BS transmit power
43 dBm
RS basic transmit power
33 dBm
MS transmit power
23 dBm
RS config, set
3
Attenuation factor
3.2
Thermal noise figure
−174 dB
Min. RS to RS SNR
7.9515 dB
Min. SNR received by MS
2.6505 dB
BER threshold
0.0001
Max. spatial diversity
3
Traffic required by MS (DL)
1 Mbps
Traffic required by MS (UL)
0.5 Mbps
BS capacity
100 Mbps
RS basic capacity
15 Mbps
RS fix cost
1 M dollars
RS config. cost
0.2 M dollarsTable 4
Modulation and code rate [24, 25].
Modulation
Code rate
SNR
DL rate (Mbps)
UL rate (Mbps)
QPSK
1/2 CTC
SNR≤
9.4
6.34
4.70
QPSK
3/4 CTC
9.4 < SNR≤ 11.2
9.50
7.06
16 QAM
1/2 CTC
11.2 < SNR≤ 16.4
12.67
9.41
16 QAM
3/4 CTC
16.4 < SNR≤ 18.2
19.01
14.11
64 QAM
2/3 CTC
18.2 < SNR≤ 22.7
25.34
18.82
64 QAM
3/4 CTC
22.7 < SNR
28.51
21.17In the meantime, and for the purpose of evaluating our solution of quality, two simple algorithms, minimum BER algorithm (MBA) and density-based algorithm (DBA), are implemented for comparison. The purpose of each MBA is, for each MSn, always to find the best paths that can generate the smallest BER value n receives in DL and BS b receives in UL. This algorithm will provide every transmission the minimum BER. The other one is DBA, the main concept would be the building of an RS with the first priority of the highest density area which is not served at the edges of coverage.Path Loss Function [27]
(31)
P
L
(
d
)
¯
(
dB
)
=
32.45
+
10
×
n
log
f
c
(
MHz
)
+
10
×
n
log
d
(
km
)
,
where n is attenuation factor, fc is operation frequency, d is distance.Thermal Noise Function
(32)
N
=
K
T
0
B
F
,
transfer  into
(
dB
)
:
N
=
-
174
(
dBm
)
+
10
lo
g
10
B
+
F
(
dB
)
,
where  B is channel bandwidth,  F is noise figure.In this research, the SNR function we apply is listed as follows:(33)SNR(dBm)=Pt+Gt+Gr-PL(d)¯-N,
where Pt is transmit power, Gt is transmit gain, Gr is receive gain, PL(d)¯ is path loss function, N is thermal noise function.The BER evaluation functions we apply have been moderated with various modulation schemes [28, 29] are demonstrated the theoretical and simulated results of BER value in four different modulation schemes.


### 4.4. Experiment Scenarios

For the unique characteristics of this network deployment problem, the given circumstances are BS and MS locations, but RSs would be candidate locations. There is no RS built at the beginning. The word “topology” introduced in the following refers to the geographic distribution (the position) of locations where an RS could be built. Two types of topologies, grid and random, are proposed with different numbers of RS and MS in one BS environment to analyze the impact on deployment cost. We then apply different numbers of RS and MS with two BSs in a random topology to analyze the deployment in multiple BSs environment. Table5 lists the experiment scenarios; Figures 5 and 6 show the graphic examples of grid and random networks. For each scenario, all MSs are guaranteed to have transmission paths and each scenario can be solved in our experiments. In these scenarios, BSs are at the center of the network, RSs are in Grid/Random topology, and MSs are in random topology.Table 5
Experiment scenarios.
Topology
Network scale
No. of BS
No. of RS
No. of MS
Grid
3.2 km
1
8, 24, 48
20, 30, 40, 50
Grid
6.4 km
1
24, 48
20, 30, 40, 50
Grid
9.6 km
1
80
20
Random
3.2 km
1
8, 24, 48
20, 30, 40, 50
Random
6.4 km
2
16, 48
40, 60, 80Figure 5
Grid topology example.Figure 6
Random topology example.


### 4.5. Experiment Results

In Lagrangian relaxation approach, an upper bound (UB) of the problem, is the best primal feasible solution, while the solution to the Lagrangian dual problem guarantees the lower bound (LB) of the problem. By solving the Lagrangian dual problem iteratively and getting a primal feasible solution, we derive the LB and the UB, respectively. Thus, the gap between the UB and LB, computed by (UB − LB)/LB × 100%, illustrates the quality (optimality) of the problem solution.Figure7 and Table 6 show the total deployment cost calculated by different algorithms within 1 BS and grid RS topology configuration with different numbers of RS and MS are deployed, respectively. It is obvious that LR-based algorithm results in superior solution in comparison with MBA and DBA, especially when the RS number is large. Additionally, DBA has lower costs than MBA. This illustrates that the LR algorithm has a trend of choosing RS with large MS density instead of RS, which results in minimum BER.Table 6
Algorithm comparison (1 BS, grid, 3.2 km).
No. of RS
No. of MC
LB
UB
GAP (%)
MBA
Imp. ratio of MBA (%)
DBA
Imp. ratio of DBA (%)
8
20
901.7678
920
1.98176
960
4.347826
960
4.347826
8
30
1020.242
1060
3.750792
1280
20.75472
1120
5.660377
8
40
1258.947
1280
1.644797
1280
0
1280
0
8
50
1260.484
1280
1.524727
1280
0
1280
0
24
20
1156.286
1280
9.665148
1600
25
1440
12.5
24
30
1164.774
1280
9.002031
1920
50
1600
25
24
40
1208.743
1320
8.428545
2080
57.57576
1920
45.45455
24
50
1269.846
1440
11.81623
2400
66.66667
2080
44.44444
48
20
860.6118
880
2.203205
1760
100
1120
27.27273
48
30
921.4716
960
4.013375
2240
133.3333
1220
27.08333
48
40
1082.548
1220
11.2666
2240
83.60656
1480
21.31148
48
50
1098.812
1260
12.79272
2560
103.1746
1640
30.15873Figure 7
Deployment cost with different number of RS and MS (1 BS, grid, 3.2 km).In RS grid topology, for a given network scale, the distance of RS is the farthest locations from BS to receive signals under BER threshold should be included mandatorily. This phenomenon can be observed in Figures8 and 9. The RS locations in grid topologies of RS = 24 exclude the RS locations in the same topologies of RS = 8 where the about farthest locations BS can reach an RS. The costs in the scenarios of RS = 24 are all higher than in the scenarios of RS = 8 except MBA. We infer that this is because some MSs in RS = 24 need more hops than RS = 8 to reach the BS, thus inducing costs.Figure 8
Deployment cost with different number of RS (1 BS, grid, 3.2 km).Figure 9
Deployment cost with different number of MS (1 BS, grid, 3.2 km).From Figures10 and 11, we can come to the conclusion that with a fixed number of MSs, total deployment costs are reduced with an increasing number of RSs. Meanwhile, with a fixed number of RSs, total deployment costs are reduced with an increase in the number of MSs.Figure 10
Deployment cost with different number of RS and MS (1 BS, random, 3.2 km).Figure 11
Deployment cost with different number of RS (1 BS, random, 3.2 km).Figure10 and Table 7 show total deployment costs as calculated by different algorithms through 1 BS with different numbers of RS and MS in a random topology. Again, it is obvious that the Lagrangian Relaxation-based algorithm receives better solution of quality in comparison with MBA and DBA (bold font), particularly so with a large number of RSs.Table 7
Algorithm comparison (1 BS, random, 3.2 km).
No. of RS
No. of MC
LB
UB
GAP (%)
MBA
Imp. ratio of MBA (%)
DBA
Imp. ratio of DBA (%)
8
20
867.3459
900
3.628233
960
6.666667
960
6.666667
8
30
850.3321
900
5.518652
960
6.666667
960
6.666667
8
40
846.2536
900
5.971822
1120
24.44444
960
6.666667
8
50
909.7847
980
7.164823
1280
30.61224
1020
4.081633
24
20
811.1707
860
5.67783
1600
86.04651
960
11.62791
24
30
798.1251
860
7.19476
1920
123.2558
1020
18.60465
24
40
805.3412
900
10.51765
2080
131.1111
1020
13.33333
24
50
860.9539
980
12.14756
2400
144.898
1340
36.73469
48
20
734.8455
820
10.3847
1760
114.6341
1020
24.39024
48
30
766.4685
860
10.87563
1820
111.6279
1080
25.58142
48
40
744.6947
880
15.3756
2260
156.8182
1140
29.54545
48
50
768.6480
920
16.4513
2420
163.0435
1260
36.95652Figures11 and 12 indicate the same conclusion in grid topology. With a fixed number of MSs, total deployment costs are reduced with an increase in the number of RSs. At the same time, with a fixed number of RSs, total deployment costs are reduced with an increase in the number of MSs.Figure 12
Deployment cost with different number of MS (1 BS, random, 3.2 km).In random topology, it is difficult to generate a network capable of satisfying every MS’s transmission when a few RSs (ex. RS = 8) are deployed. In general, RSs are not distributed uniformly enough to fully cover all MSs. Figure13 and Table 8 show total deployment costs calculated by different algorithms under 2 BS and random topology, with different number of RS and MS. We come to the same conclusion: the Lagrangian Relaxation-based algorithm still gets better solution of quality in comparison with MBA and DBA, more so with a large number of RSs.Table 8
Algorithm comparison (2 BSs, random, 6.4 km).
No. of RS
No. of MC
LB
UB
GAP (%)
MBA
Imp. ratio of MBA (%)
DBA
Imp. ratio of DBA (%)
16
40
1542.505
1620
4.78362
1760
8.641975
1680
3.703704
16
60
1726.22
1840
6.18371
2240
21.73913
1840
0
16
80
1737.373
1920
9.5118
2400
25
2020
5.208333
48
40
1409.38
1540
8.48179
3040
97.4026
1760
14.28571
48
60
1533.7687
1720
10.8274
3360
95.34884
1940
12.7907
48
80
1550.1775
1820
14.82541
3840
110.989
2280
25.27473Figure 13
Deployment cost with different number of BS in random topology.If these scenarios experimented previously are double the size of those in which BS = 1, how the result is. With random topology in BS = 1, it is also difficult to get a feasible network when RS number is small (ex. RS = 16 here). Figure13 illustrates total deployment costs in random topologies with BS = 1 and BS = 2. Since the RS locations are different in both conditions, it would be fruitless to compare their costs. However, it is still obvious that the gaps are all larger in every scenarios in BS = 2 than in BS = 1 for network complexity.Figure14 and Table 9 show the scenario of 1 BS, with different number of RS and MS in a grid topology with a 6.4 km network scale. Since the network (6.4 km) is larger than that of previous experiments (3.2 km), 8 RSs is no longer sufficient to fulfill all transmissions. Therefore, 24 RSs (two layers from the BS) becomes the smallest size of this network scale.Table 9
Experiment results (1 BS, grid, 6.4 km).
No. of RS
No. of MC
LB
UB
GAP (%)
MBA
Imp. ratio of MBA (%)
DBA
Imp. ratio of DBA (%)
8
20
N/A
N/A
N/A
N/A
N/A
N/A
N/A
8
30
N/A
N/A
N/A
N/A
N/A
N/A
N/A
8
40
N/A
N/A
N/A
N/A
N/A
N/A
N/A
8
50
N/A
N/A
N/A
N/A
N/A
N/A
N/A
24
20
2155.106
2340
7.901457
2720
16.23932
2420
3.418803
24
30
2212.838
2480
10.77267
3520
41.93548
2840
14.51613
24
40
2469.994
2820
12.41156
4800
70.21277
3360
19.14894
24
50
2699.765
3440
21.51847
5440
58.13953
4480
30.23256
48
20
1537.11
1700
9.581763
2880
69.41176
1960
15.29412
48
30
2059.57
2320
11.22543
4480
93.10345
2640
13.7931
48
40
2309.617
2720
15.08761
5600
105.8824
3480
27.94118
48
50
2445.661
3280
25.43715
6240
90.2439
4880
48.78049Figure 14
Deployment cost with different number of RS and MS (1 BS, gird, 6.4 km).Figure15 demonstrates the deployment costs of 20 MSs with various numbers of RS among three kinds of network scale, 3.2 km with 8 RSs (1 layer from the BS), 6.4 km with 24 RSs, and 9.6 km with 80 RSs (4 layers from the BS). As explained previously, in the 6.4 km network scale the smallest grid size is 24 RSs (2 layers from the BS). One can see the same situation in 9.6 km, with the smallest grid size being 80 RSs (3 layers from the BS).Figure 15
Deployment cost and lower bound (LB) values in different network scales (1 BS, grid, 20 MSs).


## 4.1. Lagrangian Relaxation Techniques

By applying the Lagrangian Relaxation (LR) Method and the Subgradient Method to solve the complex problem, based on the problem formulation mentioned previously, the first step would be that the constraints of the primal problem are relaxed by using the LR Method [26]. In this step, we can not only determine a theoretical lower bound of the primal problem, but, can also glean some hints of feasible solutions captured by the primal problems. After iterations, the end result of the Lagrangian Relaxation Problem is guaranteed to a feasible solution by a feasible step which is satisfied with all constraints of the primal problem, if not, we have to make some modifications.


## 4.2. Getting Primal Feasible Heuristics

To obtain the primal feasible solutions for(IP1), the first step is considered the solutions to the Lagrangian Relaxation. Two major decision variables, κnsdir and ynuvdir are taken into consideration. According to κnsdir, the RS(s) (or BS) can be obtained to serve MS n selected in dir direction, and ynuvdir represents the link uv which n selected on the routing multicast tree in dir direction. In addition to κnsdir and ynuvdir, for the complexity of this problem including five 0-1 integer decision variables, we still need other clues to help solving this problem in good quality. Thus, the coefficient μns14+∑b∈Bμnsb115+PminNμns5+M¯∑i∈R∑b∈Bμnisb116-πsn1(μns5+μn7-μns8) of κns1 in DL, namely, Cκ1; μnr24+∑b∈Bμnrb215+PminRμnr6+M¯∑i∈R∑b∈Bμnirb216-πnr2(μnr6-μnr9)+μn14BEP(πnr2) of κns2 in UL, namely, Cκ2 is introduced in our solution to sort κnsdir for further calculations.The main purpose of determining the primal feasible heuristic is, in both DL and UL directions, and for each MS sorted by the distance to BS, to fully utilize the RSs built already to meet the BER requirement, and if not, to at least minimize the number of RSs necessary to reach the previous goal. The detailed procedure that decomposites the Lagrangian Relaxation Problem into several subproblems is described in the appendix.


## 4.3. Experiments Environment

In this session, we conduct several computational experiments to justify the proposed algorithms. Due to limitation of available experiment scenarios and parameters, we focus on IEEE 802.16j instead of LTE-A; it is easier to build the network based on realistic and operable environment parameters. In order to effectively analyze the physical operations of an 802.16j network, Table3 lists all system parameters utilized in this research with reference to “Mobile WiMAX” published by WiMAX forum. Adaptive Modulation and Coding (AMS) applied in 802.16j is illustrated specifically in Table 4 with the same reference to “Mobile WiMAX.”Table 3
System parameters [24, 25].
Parameters
Value
Operation frequency
2500 MHz
Channel bandwidth
10 MHz
BS antenna gain
15 dBi
RS basic antenna gain
5 dBi
MS antenna gain
−1 dBi
BS noise figure
4 dB
RS noise figure
5 dB
MS noise figure
7 dB
BS transmit power
43 dBm
RS basic transmit power
33 dBm
MS transmit power
23 dBm
RS config, set
3
Attenuation factor
3.2
Thermal noise figure
−174 dB
Min. RS to RS SNR
7.9515 dB
Min. SNR received by MS
2.6505 dB
BER threshold
0.0001
Max. spatial diversity
3
Traffic required by MS (DL)
1 Mbps
Traffic required by MS (UL)
0.5 Mbps
BS capacity
100 Mbps
RS basic capacity
15 Mbps
RS fix cost
1 M dollars
RS config. cost
0.2 M dollarsTable 4
Modulation and code rate [24, 25].
Modulation
Code rate
SNR
DL rate (Mbps)
UL rate (Mbps)
QPSK
1/2 CTC
SNR≤
9.4
6.34
4.70
QPSK
3/4 CTC
9.4 < SNR≤ 11.2
9.50
7.06
16 QAM
1/2 CTC
11.2 < SNR≤ 16.4
12.67
9.41
16 QAM
3/4 CTC
16.4 < SNR≤ 18.2
19.01
14.11
64 QAM
2/3 CTC
18.2 < SNR≤ 22.7
25.34
18.82
64 QAM
3/4 CTC
22.7 < SNR
28.51
21.17In the meantime, and for the purpose of evaluating our solution of quality, two simple algorithms, minimum BER algorithm (MBA) and density-based algorithm (DBA), are implemented for comparison. The purpose of each MBA is, for each MSn, always to find the best paths that can generate the smallest BER value n receives in DL and BS b receives in UL. This algorithm will provide every transmission the minimum BER. The other one is DBA, the main concept would be the building of an RS with the first priority of the highest density area which is not served at the edges of coverage.Path Loss Function [27]
(31)
P
L
(
d
)
¯
(
dB
)
=
32.45
+
10
×
n
log
f
c
(
MHz
)
+
10
×
n
log
d
(
km
)
,
where n is attenuation factor, fc is operation frequency, d is distance.Thermal Noise Function
(32)
N
=
K
T
0
B
F
,
transfer  into
(
dB
)
:
N
=
-
174
(
dBm
)
+
10
lo
g
10
B
+
F
(
dB
)
,
where  B is channel bandwidth,  F is noise figure.In this research, the SNR function we apply is listed as follows:(33)SNR(dBm)=Pt+Gt+Gr-PL(d)¯-N,
where Pt is transmit power, Gt is transmit gain, Gr is receive gain, PL(d)¯ is path loss function, N is thermal noise function.The BER evaluation functions we apply have been moderated with various modulation schemes [28, 29] are demonstrated the theoretical and simulated results of BER value in four different modulation schemes.


## 4.4. Experiment Scenarios

For the unique characteristics of this network deployment problem, the given circumstances are BS and MS locations, but RSs would be candidate locations. There is no RS built at the beginning. The word “topology” introduced in the following refers to the geographic distribution (the position) of locations where an RS could be built. Two types of topologies, grid and random, are proposed with different numbers of RS and MS in one BS environment to analyze the impact on deployment cost. We then apply different numbers of RS and MS with two BSs in a random topology to analyze the deployment in multiple BSs environment. Table5 lists the experiment scenarios; Figures 5 and 6 show the graphic examples of grid and random networks. For each scenario, all MSs are guaranteed to have transmission paths and each scenario can be solved in our experiments. In these scenarios, BSs are at the center of the network, RSs are in Grid/Random topology, and MSs are in random topology.Table 5
Experiment scenarios.
Topology
Network scale
No. of BS
No. of RS
No. of MS
Grid
3.2 km
1
8, 24, 48
20, 30, 40, 50
Grid
6.4 km
1
24, 48
20, 30, 40, 50
Grid
9.6 km
1
80
20
Random
3.2 km
1
8, 24, 48
20, 30, 40, 50
Random
6.4 km
2
16, 48
40, 60, 80Figure 5
Grid topology example.Figure 6
Random topology example.


## 4.5. Experiment Results

In Lagrangian relaxation approach, an upper bound (UB) of the problem, is the best primal feasible solution, while the solution to the Lagrangian dual problem guarantees the lower bound (LB) of the problem. By solving the Lagrangian dual problem iteratively and getting a primal feasible solution, we derive the LB and the UB, respectively. Thus, the gap between the UB and LB, computed by (UB − LB)/LB × 100%, illustrates the quality (optimality) of the problem solution.Figure7 and Table 6 show the total deployment cost calculated by different algorithms within 1 BS and grid RS topology configuration with different numbers of RS and MS are deployed, respectively. It is obvious that LR-based algorithm results in superior solution in comparison with MBA and DBA, especially when the RS number is large. Additionally, DBA has lower costs than MBA. This illustrates that the LR algorithm has a trend of choosing RS with large MS density instead of RS, which results in minimum BER.Table 6
Algorithm comparison (1 BS, grid, 3.2 km).
No. of RS
No. of MC
LB
UB
GAP (%)
MBA
Imp. ratio of MBA (%)
DBA
Imp. ratio of DBA (%)
8
20
901.7678
920
1.98176
960
4.347826
960
4.347826
8
30
1020.242
1060
3.750792
1280
20.75472
1120
5.660377
8
40
1258.947
1280
1.644797
1280
0
1280
0
8
50
1260.484
1280
1.524727
1280
0
1280
0
24
20
1156.286
1280
9.665148
1600
25
1440
12.5
24
30
1164.774
1280
9.002031
1920
50
1600
25
24
40
1208.743
1320
8.428545
2080
57.57576
1920
45.45455
24
50
1269.846
1440
11.81623
2400
66.66667
2080
44.44444
48
20
860.6118
880
2.203205
1760
100
1120
27.27273
48
30
921.4716
960
4.013375
2240
133.3333
1220
27.08333
48
40
1082.548
1220
11.2666
2240
83.60656
1480
21.31148
48
50
1098.812
1260
12.79272
2560
103.1746
1640
30.15873Figure 7
Deployment cost with different number of RS and MS (1 BS, grid, 3.2 km).In RS grid topology, for a given network scale, the distance of RS is the farthest locations from BS to receive signals under BER threshold should be included mandatorily. This phenomenon can be observed in Figures8 and 9. The RS locations in grid topologies of RS = 24 exclude the RS locations in the same topologies of RS = 8 where the about farthest locations BS can reach an RS. The costs in the scenarios of RS = 24 are all higher than in the scenarios of RS = 8 except MBA. We infer that this is because some MSs in RS = 24 need more hops than RS = 8 to reach the BS, thus inducing costs.Figure 8
Deployment cost with different number of RS (1 BS, grid, 3.2 km).Figure 9
Deployment cost with different number of MS (1 BS, grid, 3.2 km).From Figures10 and 11, we can come to the conclusion that with a fixed number of MSs, total deployment costs are reduced with an increasing number of RSs. Meanwhile, with a fixed number of RSs, total deployment costs are reduced with an increase in the number of MSs.Figure 10
Deployment cost with different number of RS and MS (1 BS, random, 3.2 km).Figure 11
Deployment cost with different number of RS (1 BS, random, 3.2 km).Figure10 and Table 7 show total deployment costs as calculated by different algorithms through 1 BS with different numbers of RS and MS in a random topology. Again, it is obvious that the Lagrangian Relaxation-based algorithm receives better solution of quality in comparison with MBA and DBA (bold font), particularly so with a large number of RSs.Table 7
Algorithm comparison (1 BS, random, 3.2 km).
No. of RS
No. of MC
LB
UB
GAP (%)
MBA
Imp. ratio of MBA (%)
DBA
Imp. ratio of DBA (%)
8
20
867.3459
900
3.628233
960
6.666667
960
6.666667
8
30
850.3321
900
5.518652
960
6.666667
960
6.666667
8
40
846.2536
900
5.971822
1120
24.44444
960
6.666667
8
50
909.7847
980
7.164823
1280
30.61224
1020
4.081633
24
20
811.1707
860
5.67783
1600
86.04651
960
11.62791
24
30
798.1251
860
7.19476
1920
123.2558
1020
18.60465
24
40
805.3412
900
10.51765
2080
131.1111
1020
13.33333
24
50
860.9539
980
12.14756
2400
144.898
1340
36.73469
48
20
734.8455
820
10.3847
1760
114.6341
1020
24.39024
48
30
766.4685
860
10.87563
1820
111.6279
1080
25.58142
48
40
744.6947
880
15.3756
2260
156.8182
1140
29.54545
48
50
768.6480
920
16.4513
2420
163.0435
1260
36.95652Figures11 and 12 indicate the same conclusion in grid topology. With a fixed number of MSs, total deployment costs are reduced with an increase in the number of RSs. At the same time, with a fixed number of RSs, total deployment costs are reduced with an increase in the number of MSs.Figure 12
Deployment cost with different number of MS (1 BS, random, 3.2 km).In random topology, it is difficult to generate a network capable of satisfying every MS’s transmission when a few RSs (ex. RS = 8) are deployed. In general, RSs are not distributed uniformly enough to fully cover all MSs. Figure13 and Table 8 show total deployment costs calculated by different algorithms under 2 BS and random topology, with different number of RS and MS. We come to the same conclusion: the Lagrangian Relaxation-based algorithm still gets better solution of quality in comparison with MBA and DBA, more so with a large number of RSs.Table 8
Algorithm comparison (2 BSs, random, 6.4 km).
No. of RS
No. of MC
LB
UB
GAP (%)
MBA
Imp. ratio of MBA (%)
DBA
Imp. ratio of DBA (%)
16
40
1542.505
1620
4.78362
1760
8.641975
1680
3.703704
16
60
1726.22
1840
6.18371
2240
21.73913
1840
0
16
80
1737.373
1920
9.5118
2400
25
2020
5.208333
48
40
1409.38
1540
8.48179
3040
97.4026
1760
14.28571
48
60
1533.7687
1720
10.8274
3360
95.34884
1940
12.7907
48
80
1550.1775
1820
14.82541
3840
110.989
2280
25.27473Figure 13
Deployment cost with different number of BS in random topology.If these scenarios experimented previously are double the size of those in which BS = 1, how the result is. With random topology in BS = 1, it is also difficult to get a feasible network when RS number is small (ex. RS = 16 here). Figure13 illustrates total deployment costs in random topologies with BS = 1 and BS = 2. Since the RS locations are different in both conditions, it would be fruitless to compare their costs. However, it is still obvious that the gaps are all larger in every scenarios in BS = 2 than in BS = 1 for network complexity.Figure14 and Table 9 show the scenario of 1 BS, with different number of RS and MS in a grid topology with a 6.4 km network scale. Since the network (6.4 km) is larger than that of previous experiments (3.2 km), 8 RSs is no longer sufficient to fulfill all transmissions. Therefore, 24 RSs (two layers from the BS) becomes the smallest size of this network scale.Table 9
Experiment results (1 BS, grid, 6.4 km).
No. of RS
No. of MC
LB
UB
GAP (%)
MBA
Imp. ratio of MBA (%)
DBA
Imp. ratio of DBA (%)
8
20
N/A
N/A
N/A
N/A
N/A
N/A
N/A
8
30
N/A
N/A
N/A
N/A
N/A
N/A
N/A
8
40
N/A
N/A
N/A
N/A
N/A
N/A
N/A
8
50
N/A
N/A
N/A
N/A
N/A
N/A
N/A
24
20
2155.106
2340
7.901457
2720
16.23932
2420
3.418803
24
30
2212.838
2480
10.77267
3520
41.93548
2840
14.51613
24
40
2469.994
2820
12.41156
4800
70.21277
3360
19.14894
24
50
2699.765
3440
21.51847
5440
58.13953
4480
30.23256
48
20
1537.11
1700
9.581763
2880
69.41176
1960
15.29412
48
30
2059.57
2320
11.22543
4480
93.10345
2640
13.7931
48
40
2309.617
2720
15.08761
5600
105.8824
3480
27.94118
48
50
2445.661
3280
25.43715
6240
90.2439
4880
48.78049Figure 14
Deployment cost with different number of RS and MS (1 BS, gird, 6.4 km).Figure15 demonstrates the deployment costs of 20 MSs with various numbers of RS among three kinds of network scale, 3.2 km with 8 RSs (1 layer from the BS), 6.4 km with 24 RSs, and 9.6 km with 80 RSs (4 layers from the BS). As explained previously, in the 6.4 km network scale the smallest grid size is 24 RSs (2 layers from the BS). One can see the same situation in 9.6 km, with the smallest grid size being 80 RSs (3 layers from the BS).Figure 15
Deployment cost and lower bound (LB) values in different network scales (1 BS, grid, 20 MSs).


## 5. Conclusions and Future Work

With 3G technology established, it was obvious that the traffic is increased significantly, but the average revenue per user (ARPU) is decreased very fast. The business challenges of operators would be that increasing revenues by finding other solutions more efficiency and effectiveness. But the network development of a new 4G system started to be investigated and made huge investments of macro base station deployments. In one early investigation which took relays would be able to speed up extend services and expanded market share at this stage economically. So, the operators can make new revenues and cost reduction balance.Although our experiments do not cover large network scales with large number of RSs and MSs for the restrictions of computational capabilities, these model approaches can nevertheless be regarded as useful engineering guidelines for future LTE-A relay network development.In this paper, we stand for an operator to propose a solution that determines where and how many relays should be deployed in the planning stages to minimize the development cost. In the planning stages, we not only derive a Multicast Tree routing algorithm to both determine and fulfill the QoS requirements and also enhance throughput on both down-link  and up-link  communications, but we also utilize the Lagrangian Relaxation Method in conjunction with optimization-based heuristics and conduct computational experiments to evaluate the performance of the proposed algorithms.Our contributions in this research can be divided into three parts. First, we have constructed the network architecture with multicast tree routing concepts. Secondly, we proposed a precise mathematical expression to model the network architecture problem. This is not an intuitive mathematical model for considering the solvability of this problem. We have designed the entire model not only to be solvable but also to not violate the physical meanings. Finally, we provide the lagrangian relaxation and optimization-Based algorithms to solve this problem; we prove it to have superior quality after verification with other simple algorithms and lower bound value. This optimal solution is a good strategic method to minimize the CAPEX of operators to build up a relay network with more efficiency and effectiveness and the QoS can be guaranteed.



---

*Source: 517846-2013-10-30.xml*