Loading...
Please wait, while we are loading the content...
Similar Documents
Um Algoritmo Eficiente para o Problema do Posicionamento Natural de Antenas
| Content Provider | Semantic Scholar |
|---|---|
| Author | Crepaldi, Bruno Eiras Souza, Cid C. De Rezende, Pedro Jussieu De |
| Copyright Year | 2020 |
| Abstract | Considerado uma variacao do problema da galeria de arte, o problema do posicionamento de antenas trata do posicionamento do menor numero de antenas requerido para determinar se uma pessoa esta dentro ou fora da galeria. Uma antena propaga uma chave unica dentro de um ângulo especifico de transmissao, de modo que o conjunto de chaves recebidas em um dado ponto do plano seja suficiente para decidir se ele pertence ou nao ao poligono que representa a galeria. Para verificar esta propriedade de localizacao, uma formula Booleana deve ser produzida junto com o posicionamento de antenas. Dizemos que as antenas estao em posicao natural se elas estao localizadas nos vertices ou nas arestas do poligono e transmitindo sinal no ângulo formado pelos lados deste ultimo no ponto onde a antena esta posicionada. O problema do posicionamento natural de antenas e NP-dificil. Nesta dissertacao, apresentamos um algoritmo exato para resolve-lo. Para tanto, propomos um modelo inicial de programacao linear inteira para o problema que, ao ser computado por um resolvedor comercial, se mostrou capaz de encontrar solucoes otimas de instâncias correspondentes a poligonos com algumas dezenas de vertices. Em seguida, atraves de estudos de propriedades geometricas, sao introduzidas varias melhorias no modelo matematico e tambem na forma de computa-lo. Como consequencia desta pesquisa, desenvolvemos um algoritmo iterativo baseado em programacao linear inteira com o qual conseguimos solucionar o problema para instâncias consideravelmente maiores. A eficiencia do nosso algoritmo e certificada por resultados experimentais que compreendem as solucoes otimas de 720 instâncias de ate 1000 vertices, incluindo poligono com buracos, as quais foram calculadas em menos de seis minutos em um computador desktop padrao. Abstract |
| File Format | PDF HTM / HTML |
| DOI | 10.5753/ctd.2015.10005 |
| Alternate Webpage(s) | https://sol.sbc.org.br/index.php/ctd/article/download/10005/9888 |
| Alternate Webpage(s) | https://doi.org/10.5753/ctd.2015.10005 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
