Detail

Criação de Triangulações de Delaunay num único passo de comunicação

As redes ad hoc sem fios apresentam algumas restrições importantes relativamente a uma rede com fios convencional. Estas restrições dizem respeito não só à largura de banda disponível, mas também à própria capacidade dos nós, que possuem pouca bateria e pouca capacidade de processamento. Aliados à mobilidade, estes factores fazem com que não seja exequível propagar todas as alterações que ocorrem na topologia da rede. Neste contexto, os esquemas de encaminhamento geográfico apresentam vantagens significativas relativamente aos esquemas de encaminhamento mais clássicos, baseados em trocas de tabelas de encaminhamento.

Um esquema de encaminhamento geográfico baseia-se na hipótese de que os nós conseguem determinar a sua posição geográfica e que a posição do destino é conhecida (ou passível de ser determinada). Dentro deste paradigma, uma das soluções mais simples consiste em encaminhar em grafos planos ( i.e., sem intersecções de arestas) de forma a garantir a entrega de mensagens no destino. No entanto, os grafos planos utilizados costumam ser extremamente esparsos, não permitindo, assim, a obtenção de caminhos curtos. Uma forma de aumentar a densidade, mantendo a planaridade, consiste em utilizar uma triangulação de Delaunay localizada. Por ser localizada, este tipo de triangulação requer pouca informação de controlo e permite garantir a entrega de mensagens com desempenho muito superior ao de grafos mais esparsos. Ainda assim, estes algoritmos requerem o envio de diversas mensagens por nó, o que em muitas circunstâncias poderá não ser viável.

Para resolver este problema, apresentamos dois algoritmos que criam um grafo plano chamado “triangulação plana e localizada de Delaunay”, PLDel, que é um bom grafo de cobertura do grafo de disco unitário, UDG. Enquanto que algoritmos anteriores construíam o grafo PLDel em quatro passos de comunicação, os nossos algoritmos necessitam de apenas um passo, mantendo um custo óptimo de O(n log n), o que está a uma constante do óptimo. A simplicidade dos nossos algoritmos torna possível a utilização do grafo PLDel em alternativa a outros grafos de cobertura, que, embora piores, eram mais fáceis de construir por não necessitarem de mais informação para além do conhecimento dos vizinhos. Finalmente, mostramos que um dos nossos algoritmos pode resistir a modelos de comunicação que vão para além do disco de raio unitário (UDG).