Alocação de canais para roteamento geográfico em redes de sensores e atuadores sem fio empregando a teoria dos jogos

Abstract

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.