Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Wireless sensor and actuator networks are expected to grow quickly in size due to the
decreasing cost of nodes. For such large scale networks, the geographic routing algorithm
is a suitable approach. It finds a route for the packet based on the positions of the
nodes. However, it often finds longer routes than the shortest possible ones, increasing the
probability of packet loss. Moreover, the low cost wireless devices usually operate in the
unlicensed bands, which is a crowded portion of the spectrum where several networks may
be operating. Furthermore, the expected increase in the network density will also increase
the competition for the wireless channel. Thus, intra and inter-network interferences play
a major role in the reliability of the communication. In order to increase it, communication
over multiple channels can be used. It exploits the capability of the radios that equip the
nodes to be tuned over different frequencies. However, the number of available channels is
limited in practice. Therefore, an allocation protocol must employ the channels eficiently.
However, it was shown that to find an optimal allocation is NP-hard. Thus, one can use
game theory to design a protocol that sub-optimally assigns channels in a distributed way.
Game theory allows to model the problem as a game, where nodes are players and channels
are their actions. According to the actions played, every node receives a payoff. The task of
the protocol designer is to assign to every player a payoff function and a learning algorithm.
This algorithm allows a player to play accordingly its observations of the game in order
to maximize its payoff. If the designed game is potential, the algorithm can be used such
that repeated playing converge to a steady state, known as Nash Equilibrium (NE). In
a NE, no player can be better of by switching its current action and its received payoff
can be bounded by a constant factor of the optimal payoff. By following such approach, a
protocol called GBCA has been proposed, which allocates channels by exploiting topology
and routing information. However, GBCA was designed for networks where routes are
known in advance and static during a relatively long time. Geographic routing, by the
other hand, finds the route for every packet on-demand. Therefore, in order to apply
GBCA in networks that use geographic routing, this thesis proposes suitable modifications
to the payoff functions. Using this modified protocol, which is called GBCA-G, it is shown,
by simulations, the improvement of the network perfomance according to the metrics of
delivery ratio, average delay and average number of trials per successfull transmission. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufsm.br:1/3670 |
| Date | 25 May 2012 |
| Creators | Barriquello, Carlos Henrique |
| Contributors | Campos, Alexandre, Prado, Ricardo Nederson do, Martins, João Baptista dos Santos, Rocha Neto, José Sérgio da, Beck Filho, Antonio Carlos Schneider |
| Publisher | Universidade Federal de Santa Maria, Programa de Pós-Graduação em Engenharia Elétrica, UFSM, BR, Engenharia Elétrica |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFSM, instname:Universidade Federal de Santa Maria, instacron:UFSM |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 300400000007, 400, 300, 300, 300, 300, 300, 300, 272a7edd-3c46-4479-b573-4cd18bb0b376, 587f1258-fd66-491a-bf60-911cd6d648ab, 12860ce2-1b41-4c4f-b769-49ca2a56fc71, 0b253003-b502-4ac1-aae6-03b42b0eacd3, ae3df507-bf6a-4e38-82f0-bff9c402c673, 8fb5a54f-e9cf-49c9-86c2-db9e743e5463 |
Page generated in 0.0026 seconds