Algoritmos para a determinação da região coberta por um k-transmissor

Abstract

Os problemas de visibilidade/cobertura têm diversas aplicações a situa ções reais. Os mais recentes são inspirados nas novas tecnologias, envolvendo dispositivos de rede sem os. Neste trabalho será abordado o problema de determinar a região coberta pelo sinal emitido por um destes dispositivos, colocado em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, a geometria de edifícios e são de fácil manipulação computacional, podendo o sinal estudado atravessar um dado número de obstáculos (parades/arestas do polígono), razão pela qual os dispositivos são chamados de k-transmissores, de acordo com o número de obstáculos que o sinal emitido é capaz de atravessar. A resolução deste problema torna-se importante, não só pela sua aplicação directa, mas principalmente porque permitirá prosseguir estudos relacionados, como o problema da determinação do número mínimo de posições para a colocação destes dispositivos num dado polígono, de modo a que os sinais por eles emitidos consigam cobrir a totalidade do polígono. Nesta dissertação são referidos os algoritmos existentes para a resolu- ção do problema da determinação da região coberta pelo sinal emitido por um dispositivo de redes sem os, colocado num polígono simples, e são apresentados dois novos algoritmos para a resolução desse mesmo problema. Com o objectivo de testar e avaliar experimentalmente os algoritmos apresentados e de facilitar o prosseguimento de estudos relacionados, foi desenvolvida uma aplicação que inclui uma interface grá ca para facilitar a introdução de dados de entrada (vértices do polígono e dados relativos aos dispositivos) e a visualização dos resultados (região coberta pelo sinal) por parte do utilizador. Esta aplicação é descrita de forma detalhada nesta dissertação.

Visibility/coverage problems have several applications to real-life situations. The most recent coverage problems are inspired by new technologies and envolve wireless devices. This work deals with the problem of nding the covered region by the signal of these devices, located on geometrical structures known as polygons, since polygons are appropriate representations of objects geometry and are easily handled by computers. Notice that the signal of those devices can cross a certain number k of walls (edges of the polygon) and that is the reason why the devices are called k-transmitters. The determination of solutions to this problem is important not only because of its direct application but also (and mainly) because it will make possible to proceed related studies, like the problem of nd a minimum number of device positions on a given polygon such that these devices collectively cover the whole polygon. In this dissertation, we refer the existing algorithms to solve the problem of nding the covered region by the signal transmitted by a wireless device, located on a simple polygon, and two new algorithms to also solve this problem are presented. To experimentally test and evaluate the analyzed algorithms and to become easier to proceed related studies, an application that includes a graphic interface has been developed to make it possible for the user to easily insert data (the vertices of the polygon and the information related to devices) and visualize the nal results (the covered region). There is a detailed description of that application in this thesis.