Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Solving the natural wireless localization problem to optimality efficiently

Texto completo
Autor(es):
Crepaldi, Bruno E. [1] ; de Rezende, Pedro J. [1] ; de Souza, Cid C. [1]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS; v. 48, n. 5, SI, p. 370-379, JUL 2015.
Citações Web of Science: 0
Resumo

Considered a variation of the art gallery problem, the wireless localization problem deals with the placement of the smallest number of broadcasting antennas required to satisfy some property within a given polygon. The case dealt with here consists of antennas that propagate a unique key within a certain antenna-specific angle of broadcast, so that the set of keys received at any given point is sufficient to determine whether that point is inside or outside the polygon. To ascertain this localization property, a Boolean formula must be produced along with the placement of the antennas. In this paper, we present an exact algorithm based on integer linear programming for solving the NIP-hard natural wireless localization problem. The efficiency of our algorithm is certified by experimental results comprising the solutions of 720 instances, including polygon with holes, of up to 1000 vertices, in less than fifteen minutes on a standard desktop computer. (C) 2015 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 12/17608-9 - O Problema do Posicionamento de Antenas: um estudo geométrico e Algortmico
Beneficiário:Bruno Espinosa Crepaldi
Linha de fomento: Bolsas no Brasil - Mestrado
Processo FAPESP: 07/52015-0 - Métodos de aproximação para computação visual
Beneficiário:Jorge Stolfi
Linha de fomento: Auxílio à Pesquisa - Temático