| Texto completo | |
| Autor(es): |
Andrade, Carlos E.
[1]
;
Resende, Mauricio G. C.
[2, 3]
;
Zhang, Weiyi
[2]
;
Sinha, Rakesh K.
[2]
;
Reichmann, Kenneth C.
[2]
;
Doverspike, Robert D.
[2]
;
Miyazawa, Flavio K.
[1]
Número total de Autores: 7
|
| Afiliação do(s) autor(es): | [1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP - Brazil
[2] AT&T Labs Res, Network Evolut Res Dept, Middletown, NJ 07748 - USA
[3] Amazon Com Inc, Math Optimizat & Planning Grp, Seattle, WA 98109 - USA
Número total de Afiliações: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | APPLIED SOFT COMPUTING; v. 33, p. 150-169, AUG 2015. |
| Citações Web of Science: | 6 |
| Resumo | |
This paper describes a biased random-key genetic algorithm for a real-world wireless backhaul network design problem. This is a novel problem, closely related to variants of the Steiner tree problem and the facility location problem. Given a parameter h, we want to build a forest where each tree has at most h hops from the demand nodes, where traffic originates, to the root nodes where each tree is rooted. Candidate Steiner nodes do not have any demand but represent locations where we can install cellsites to cover the traffic and equipment to backhaul the traffic to the cellular core network. Each Steiner node can cover demand nodes within a given distance, subject to a capacity constraint. The aggregate set of constraints may make it impossible to cover or backhaul all demands. A revenue function computes the revenue associated with the total amount of traffic covered and backhauled to the root nodes. The objective of the problem is to build a forest that maximizes the difference between the total revenue and the cost associated with the installed equipment. Although we will have a forest when we consider only the backhaul links and root nodes, the addition of demand vertices can induce undirected cycles, resulting in a directed acyclic graph. We consider instances of this problem with several additional constraints that are motivated by the requirements of real-world telecommunication networks. (C) 2015 Elsevier B.V. All rights reserved. (AU) | |
| Processo FAPESP: | 12/08222-0 - Algoritmos para determinação de vencedores e precificação em leilões combinatóriais |
| Beneficiário: | Carlos Eduardo de Andrade |
| Modalidade de apoio: | Bolsas no Exterior - Estágio de Pesquisa - Doutorado |
| Processo FAPESP: | 10/05233-5 - Algoritmos evolutivos para alguns problemas em telecomunicações |
| Beneficiário: | Carlos Eduardo de Andrade |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |