Net Centric Optimization    (OPLINK::UMA)       TIN2005-08818-C04-01 - Ministerio de Educación y Ciencia (Spain)
> Problems > RND

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)