| |
The Radio Network Design Problem
|
|
| |
 Description:
This NP-hard combinatorial problem consists
of determining a set of locations for placing
radio antennae in a geographical area in order
to offer high radio coverage using the smallest
number of antennae. This problem is originally
found in mobile telecommunications (such as
mobile telephony), and is also relevant in the
rising area of sensor networks. The part of
an area that is covered by an antenna is called
a cell. In the following we will assume that
the cells and the area considered are discretized,
that is, they can be described as a finite collection
of geographical locations (taken from a geo-referenced
grid).
The problem we consider recalls the Unicost
Set Covering Problem (USCP) that is known to
be NP-hard. An objective function to combine
the two goals has been proposed in [CAL97]:
where the parameter α can be tuned to favor
the cover rate factor with respect to the number
of antennae. Just like Calégari et al. did [CAL97],
we will use α = 2, and a 287 x 287 point
grid representing an open-air flat area. Three
different antenna types will be used in this
work: a square shaped cell antenna that covers
a 41 x 41 point cell as used in [CAL97,
ALB05, ALB06], an omnidirectional antenna
that covers a 22 point radius circular cell
(new contribution here), and a directive antenna
that covers one sixth of the omnidirectional
cell. When directive antennae are employed,
three of them are placed in the location site.
When
non square shaped cell antennae are employed,
it is impossible the get full coverage without
having overcoverage (terrain covered by more
than one antenna). This overcoverage is undesired
in our problem formulation as it produces resource
spilling. Therefore, the fitness function has
been slightly modified to use with omnidirectional
or directive cell antennae:
The
parameter α is maintained at the value
of 2, and a new parameter, k, is introduced.
This parameter, which has a value ranging between
0 and 1, controls the relative value of terrain
with overcoverage versus terrain with coverage
from a single antenna. At its extreme values:
k = 0 means that overcovered terrain has the
same value as terrain with normal coverage,
k = 1 means that overcovered terrain has no
value at all (like uncovered terrain). For our
work we selected an intermediate value: k =
0.5.
|
|
| |
Instances:
Classic
Definition
The grid representing the terrain is modelled
as a numerical array:
static
short int grid[GRID_SIZE];
A squared cell is a 41x41 terrain spots (from
the terrain grid) square with its center being
the antenna. An omnidirectional cell is a 23
terrain spot radius circle with its center being
the antenna.
The set of available location sites is defined
by a list of coordinates {{a,b},{c,d}..} that
has to be interpreted as follows: each pair
of coordinates {a,b} represents the position
"a*GRID_SIZE_X + b" inside the terrain grid.
In principle, any list of coordinates is suitable
for the RND problem.
We
have used two lists of coordinates for RND problem,
one for instances using square cell antennae,
and the other for instances using omnidirectional
or directive antennae. This has been done in
order for a theoretical optimum of the problem
(depending on the shape of the cell, thus specific
of the type of antenna) to be included as a
reference mark in all the experiments.
The
coordinates for the square cell antennae instances
are here.
The
coordinates for the omnidirectional antennae
instances are here.
The values of the constants are:
- #define GRID_SIZE_X 287 //Artificial
grid horizontal size.
- #define GRID_SIZE_Y 287 //Artificial
grid vertical size.
- #define GRID_SIZE
82369 //Total grid size (287*287)
|
New
Instance: Malaga City
A
new instance is defined upon a map of
the city of Malaga of size 4.25*6.4 km.
The city area is modeled by a 450*300
grid, where each position correspond to
an area of 15*15 square meters.
Map
of the city of Malaga
A
list of 1000 positions located on roofs
of buidings are selected as candidate
sites for the placement of antennae. The
coordinates of the candidate sites are
here.
Each
antenna has an omnidirectional coverage
with an estimated cover range of 450 meters
(30 grid points).
Two
approaches for this problem are used.
In the first one the objective is to maximize
the fitness obtained (for this instance
the first fitness function will be employed).
In the second one, two different objectives
are defined:
- Get the maximum coverage using a preset
number of antennae
- Use the minimum number of antennae
to reach a preset coverage
|
|
|
| |
Related Papers:
[CAL97] Calégari, P., Guiadec, F.,
Kuonen, P., Kobler, D.: Parallel island-based
genetic algorithm for radio network design.
Journal of Parallel and Distributed Computing
(47) (1997) 86-90
[ALB05] Alba, E., Chicano, F.: On
the behavior of parallel genetic algorithms
for optimal placement of antennae in telecommunications.
International Journal of Foundations of Computer
Science 16(2) (2005) 343-359
[ALB06] Alba, E., Molina, G.: Optimal
Placement of Antennae in Telecommunications
Using Metaheuristics. Technical Report ITI 2006-01.
Department of Computar Science and Languages,
University of Málaga (2006)
Click here
to get the bibliography in bibtex format.
|
|
| |
Last Updated: 20/09/07
For any question or suggestion, click here
to contact with us.
|
|
|
