Cell Planning with Capacity Expansion in Mobile Communications - A Tabu Search Approach(2).pdf

(118 KB) Pobierz
Cell Planning with Capacity Expansion in Mobile
Communications: A Tabu Search Approach
Chae Y. Lee and Hyon G. Kang
Department of Industrial Engineering, KAIST
373-1, Kusung Dong, Taejon 305-701, Korea
cylee@heuristic.kaist.ac.kr
Abstract
Cell planning problem with capacity expansion is examined in wireless
communications. The problem decides the location and capacity of each new base
station to cover expanded and increased traffic demand. The objective is to minimize
the cost of new base stations. The coverage by the new and existing base stations is
constrained to satisfy a proper portion of traffic demands. The received signal power at
the base station also has to meet the receiver sensitivity. The cell planning is formulated
as an integer linear programming problem and solved by a Tabu Search algorithm.
In the tabu search intensification by add and drop move is implemented by short-
term memory embodied by two tabu lists. Diversification is designed to investigate
proper capacities of new base stations and to restart the tabu search from new base
station locations.
Computational results show that the proposed tabu search is highly effective. 10%
cost reduction is obtained by the diversification strategies. The gap from the optimal
solutions is approximately 1∼5 % in problems that can be handled in appropriate time
limits. The proposed tabu search also outperforms the parallel genetic algorithm. The
cost reduction by the tabu search approaches 10~20 % in problems with 2,500 traffic
demand areas in CDMA.
1
1. Introduction
In cell planning for mobile communication systems we need to consider the traffic
demand to cover a specific region, availability of base station sites, available channel
capacity at each base station, and the service quality at various potential traffic demand
areas (TDAs). Selection of good base station sites and channels will result in acceptable
coverage performance at base stations both in coverage area and in signal quality. The
problem discussed in this paper is to determine the number of base stations and location
and capacity of each base station to cover increased traffic demand. The coverage has to
satisfy a certain level of total traffic demand and the received signal strength.
Optimal location of transmitters for micro-cellular system is studied by Sherali et al.
[5]. The path loss at each subarea is represented as a function of the base station
location. A nonlinear programming problem is presented which minimizes a measure of
weighted path-losses. Several nonlinear optimization algorithms are investigated to
solve the problem. In [6] the radio coverage optimization problem is converted to a
maximum independent set problem. The objective is to achieve a large coverage of
traffic demand areas with a small number of base stations. A simulation method is
employed to examine the relationship between the number of base stations and the
relative coverage of traffic demand areas.
Tutschku [12] proposed an automatic cellular network design algorithm without
considering the capacity of transmitters. The network design problem is converted to a
maximal covering location problem by using demand node concept. The location of
transmitter is optimized by minimizing co-channel interference. He [9] also proposed a
greedy heuristic to solve the maximal coverage location problem of transmitters. The
heuristic takes into account all the RF design objectives as well as the capacity and the
network deployment constraints.
Ye et al. [10] solve the cell planning in a CDMA network. They maximize the cell
coverage for given traffic and find optimal location configuration by considering nodes
covered via soft handoff by two or three base stations.
A genetic algorithm approach is presented by Calegari et al. [7, 8]. The selection of
base stations is represented in a bit string. Selection based on fitness value, one-point
crossover and mutation operators are employed. The fitness value combines two goals
of maximizing the cover rate and minimizing the number of transmitters. To speed up
the procedure a parallel genetic algorithm is implemented by using island model. Their
computational results show that the solution quality is significantly influenced by the
2
number of islands.
Most of the research in the optimization of the radio coverage in cellular system is
restricted to the selection of base station locations. Base stations are considered to start
service at the same time. In this paper we consider two types of base stations. Some
existing base stations are currently in service for a specified region. The increased
traffic demand in the region requires capacity expansion with additional base stations.
We thus need to determine the location and the capacity of each new base stations.
The remainder of this paper is organized as follows. In Section 2, we discuss the
capacity of a base station in various multiple access technologies and the potential
service area of a base station. We also provide a mathematical model for the cell
planning problem. Section 3 presents a tabu search procedure to solve the problem.
Construction of initial solutions, intensification, and diversification strategies are
examined. The performance of various tabu operators and the efficiency of the proposed
tabu search procedure are presented and compared with a genetic algorithm and an
excellent integer programming algorithm CPLEX [16] in Section 4. Finally, we
conclude the paper in Section 5.
2. Cell Planning with Capacity Expansion
The cell planning we are interested in is to decide the location and capacity of each
new base station to cover increased traffic demand. It causes cell splitting in urban area
and requires new cell sites in suburban area. Thus, some of the existing TDAs are
served by the new base stations due to the cell splitting. Here, we consider the increased
traffic demand, the capacity of each new base station to locate and the coverage of the
base station.
2.1 Capacity of a Base Station
The capacity of a base station has experienced a great improvement due to the digital
modulation, multiple access schemes and other technological development. Advanced
Mobile Phone Service (AMPS) employs the frequency division multiple access
(FDMA). It utilizes 50 MHz of spectrum in the 800 MHz band. Each channel band of
AMPS is 30 kHz. Assuming two competing carriers in the market, a carrier has 416
channels [1]. Twenty one channels are used for control and the rest for traffic channels.
3
When we assume 7-cell reuse pattern, the number of traffic channels available in a cell
becomes 56. It corresponds to a base station capacity of 46 Erlangs (Erlang B) when the
blocking probability is 2%.
Global System for Mobile (GSM) is a typical standard of the time division multiple
access (TDMA). GSM utilizes two bands of 25 MHz for forward and reverse links. The
frequency band is divided into 200 kHz wide channels called ARFCNs (Absolute Radio
Frequency Channel Numbers). Each channel is time shared between as many as eight
subscribers using TDMA. Since each radio channel consists of 8 time slots, there are
thus a total of 1000 traffic channels within GSM. In practical implementations, a guard
band of 100 kHz is provided at the upper and lower ends of GSM spectrum, and only
124 channels are implemented [1]. By assuming two companies as in AMPS, each
carrier has 62 channels. Assuming the 4-cell reuse pattern, a BS can use 120 time slots.
This corresponds to 107.4 Erlangs when the blocking probability is 2 %.
Interrim Standard 95 (IS-95) [14] is the standard of the code division multiple access
(CDMA) and offers some advantages over TDMA and FDMA. Each CDMA channel
which is called the frequency assign (FA) occupies 1.25 MHz of spectrum. Assuming
25 MHz for both links, the number of available channels becomes 10 FAs. Since the
reuse pattern in IS-95 is one, one cell use up to 10 FAs. However, normally 3-4 FAs are
used practically in a cell. Assuming 4 FAs and 36 traffic channels [15] per 1 FA, 144
traffic channels are available in a cell. If the system uses 120-degree directional antenna,
then the capacity is increased approximately 2.5 times, which corresponds to 360 traffic
channels. Assuming 2% blocking probability, the capacity becomes 345.7 Erlangs at
each base station.
2.2 Potential Service Area of a Base Station
Potential service area of a base station represents the TDAs that can be served with
sufficient quality by the base station. In this study, we are interested in a general
propagation path-loss formula in a general mobile radio environment. By using the path
loss model the received signal power can be estimated as a function of transmitted
power, distance between the transmitter and receiver, processing gains, and antenna
heights. If we ignore fading, the following propagation model [2] may well be used in
computing potential service areas. In the model the path loss exponent is assumed to be
four.
P
r
=
P
t
+
G
r
+
G
t
+ 20 log
h
r
+ 20 log
h
t
+
L
- 40 log
r
4
P
r
: received power
P
t
: transmitted power
G
r
,
G
t
: processing gains of receiver and transmitter
h
r
,
h
t
: antenna heights of receiver and transmitter
L:
buffer for fading
r:
distance between transmitter and receiver
From the above model, the radius of a cell site can be computed for a given receiver
sensitivity. In other words, the TDAs that can be covered by a base station are
determined by comparing the received power and the receiver sensitivity. Since we are
interested in the location and the capacity of each new base station, we consider the
received power at a base station from TDAs. We also assume that co-channel and
adjacent channel interferences are negligible in the uplink analysis.
2.3 Problem Formulation
Suppose that mobile users are distributed over a designated region composed of
N
TDAs. Each traffic demand area TDA
i
has a traffic demand
d
i
,
i=1, ..., N.
Assume that the region has
K
1
existing base stations each of which is denoted by BS
k
,
k=1,
…
, K
1
. To satisfy increased traffic demands
K
2
candidate cell sites are considered.
It is assumed that the potential location of each candidate base station BS
k
,
k=K
1
+1, …,
K
1
+ K
2
is known. Let
c
k
and
M
k
be respectively the cost and capacity of each new base
station
k.
Note that the cost and capacity are mainly dependent on the way of multiple
access, number of user channels, and sectorization. We assume that the base station cost
c
k
is linear to the capacity
M
k
.
To formulate the problem, we introduce two types of variables. Let
y
ik
be the wireless
connection between TDA
i
and BS
k
such that
y
ik
= 1, if TDA
i
is covered by BS
k
0, otherwise
Also, let
z
k
be the selection variable of BS
k
,
k=1, ... , K
1
+K
2
, such that
z
k
= 1, if BS
k
is selected
0, otherwise
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin