Alocação de canais para roteamento geográfico em redes de sensores e atuadores sem fio empregando a teoria dos jogos
Date
2012-05-25Metadata
Show full item recordAbstract
Espera-se que as redes de sensores e atuadores sem fio cresçam rapidamente em tamanho devido à contínua redução de custo dos dispositivos. Para tais redes de larga escala, os algoritmos de roteamento geográfico são adequados. Estes encontram a rota
com base nas posições dos nós. Contudo, geralmente as rotas encontradas são mais longas do que as rotas possíveis, aumentando a probabilidade de perda do pacote. Ademais, os
dispositivos sem fio de baixo custo operam nas faixas livres do espectro e estão sujeitos a interferências causadas por outras redes que operam nessas mesmas faixas. Ainda, com
o aumento da densidade da rede, aumenta também a competição pelo canal. Portanto, tanto interferências internas quanto externas prejudicam a confiabilidade da comunicacão.
Para aumentá-la pode-se utilizar múltiplos canais, uma vez que os rádios que equipam os nós podem ser sintonizados em diferentes frequências. Contudo, o número de canais disponíveis é limitado, tornando imperativo um protocolo de alocação eficiente. Porém foi demonstrado que encontrar uma solução ótima é inviável. Por isso, a Teoria dos Jogos pode ser empregada para se encontrar alocações sub-ótimas de forma distribuída. A Teoria dos Jogos permite modelar o problema como um jogo, onde os nós são os jogadores; os canais, suas ações; e conforme suas escolhas, cada não recebe uma recompensa. Um projetista deve definir as funções de recompensa e um algoritmo de aprendizado, que permite ao jogador determinar a ação que maximiza sua recompensa através da observação do jogo. Se o jogo for potencial, o algoritmo pode levá-lo a um equilíbrio, conhecido por Equilíbrio de Nash (NE), após repetidas rodadas. Em um NE, todo jogador estão satisfeito e sua recompensa pode ser limitada por uma constante multiplicativa da máxima recompensa possível. Seguindo esta abordagem, um protocolo denominado GBCA foi proposto na literatura, o qual aloca canais com base na topologia da rede e nas rotas utilizadas. Contudo, o GBCA necessita conhecer as rotas antecipadamente e estas devem ser estáticas. Por outro lado, algoritmos geográficos determinam a rota sob demanda para cada pacote. Portanto, para tornar o GBCA adequado para redes com roteamento geográfico, propõe-se, nesta Tese, modificações ao GBCA. Utilizando-se o protocolo proposto, denominado GBCA-G, demonstra-se, por simulação, que é possível obter resultados melhores quanto à taxa de entrega de pacotes, ao atraso médio de entrega e ao número médio de transmissões efetuadas por transmissão bem-sucedida.