A game theoretical model for collaborative protocols in selfish, tariff-free, multi-hop wireless networks

Abstract

Traditional networks are built on the assumption that network entities cooperate based on a mandatory network communication semantic to achieve desirable qualities such as efficiency and scalability. With technological maturity and widespread technical know-how, a different set of network problems has emerged - clever users that alter network behavior in a way to benefit themselves at the expense of others. The problem would be more pronounced in mobile ad hoc networks (MANET) where network ownership can be shared among different entities.Node misbehavior can occur in various degrees. At the extreme end, a malicious node may eavesdrop on sensitive data or deliberately inject fabricated, replayed or tampered packets into the network to disrupt network operations. The solution is, generally, to enable network encryption and authentication. This thesis, on the other hand, focuses on misbehaviors caused by selfish but rational users while keeping in mind the dangers posed by malicious ones. In contrast to a malicious node, a rational node acts only to obtain the outcome that he most prefers. In such a case, cooperation can still be achievable if the outcome of cooperation is to the best interest of the node. MANETs, which are typically made up of wireless, battery-powered devices, will find cooperation hard to maintain because it requires the consumption of scarce resources such as bandwidth, computational power and battery power. The objective of this thesis is to apply game theory to achieve collusive networking behavior in the MANET operational environment. The scenarios for such behaviour to occur lies in the emerging 4th generation networks where communications over multihop wireless links, across nodes that may subscribe to different providers, are envisaged to occur.Research in this area is still in its infancy and existing solutions lack technical feasibility and theoretical consistency. These solutions fall into the category of pricing or punishment. The pricing solution either requires a tamper-proof counter as a reliable storage of a node's wealth, or an occasional connection to a central authority where payments can be coordinated. Punishment methods are often designed based on the well-established Repeated Game model and promiscuous listening may be relied on for the monitoring of other players' actions. Promiscuous listening is, nevertheless, unreliable and computationally demanding. In addition, the Repeated Game model (perfect and public) fails to account for imperfection in the wireless monitoring device (whether it is public or private) and proposed solutions also overlooked the need for coordinated punishment. Most unforgivably, mass punishment of nodes creates a vulnerability for Denial-of-Service (DoS) attacks, threatening even the feasibility of the punishment mechanism as a solution for sustaining cooperation in MANETs. The complexity of modeling MANETs and the suitability of available game models poses a significant challenge to the realization of a theoretical model for collusive MANETs protocols.In this work, pricing, promiscuous listening and mass punishments are avoided altogether. Our model relies on a recent work in the field of Economics on the theory of imperfect private monitoring for the dynamic Bertrand oligopoly, and adapts it to the wireless multi-hop network. The model derives conditions for collusive packet forwarding, truthful routing broadcasts and packet acknowledgments under a lossy, wireless, multi-hop environment, thus capturing many important characteristics of the network layer and link layer in one integrated analysis that has not been achieved in previous works. Finally, we provide a proof of the viability of the model under a theoretical wireless environment.