On the Design of Incentive Mechanisms in Wireless Networks: a Game Theoretic Approach

In wireless communication networks, many protocols (e.g., IEEE 802.11 a/b/g Medium Access Control (MAC) protocols) have been designed assuming that users are compliant with the protocol rules. Unfortunately, a self-interested and strategic user might manipulate the protocol to obtain a personal advantage at the expense of the other users. This would lead to socially inefficient outcomes. In this thesis we address the problem of designing protocols that are able to avoid or limit the inefficiencies occurring when the users act selfishly and strategically. To do so, we exploit the tools offered by Game Theory (GT), the branch of mathematics that models and analyzes the interaction between strategic decision makers. The dissertation covers aspects related to wireless communications at different levels. We start analyzing the downlink radio resource allocation issue of a cellular network based on Orthogonal Frequency Division Multiple Access (OFDMA). We propose a suboptimal game theoretic algorithm able to preserve the modularity of the system and to trade–off between sum–rate throughput and fairness among the users of the network. Successively, we address the problem of promoting cooperation in wireless relay networks. To give the incentive for the users of a network to relay the packets sent by other users, we consider a dynamic scheduling in which cooperative users are rewarded with more channel access opportunities. Infrastructure sharing is another form of cooperation that might be exploit to meet the increasing rate demands and quality of service requirements in wireless networks. We analyze a scenario where two wireless multi–hop networks are willing to share some of their nodes – acting as relays – in order to gain benefits in terms of lower packet delivery delay and reduced loss probability. Bayesian Network analysis is exploited to compute the correlation between local parameters and overall performance, whereas the selection of the nodes to share is made by means of a game theoretic approach. Afterwards, our analysis focuses on channel access policies in wireless ad–hoc networks. We design schemes based on pricing and intervention to give incentives for the users to access the channel efficiently. Finally, we consider another important issue that arises when the users are strategic and selfish: when asked to report relevant information, the users might lie, if it is in their individual interest to do so. For a class of environments that includes many resource allocation problems in communication networks, we provide tools to design an efficient system, in which the users have the incentive to report truthfully and to follow the instructions, despite the fact that they are self–interested. We then apply our framework and results to design a flow control management system.

Nelle reti di comunicazione wireless, molti protocolli (ad esempio, i protocolli di accesso al mezzo IEEE 802.11 a/b/g) sono stati progettati assumendo che gli utenti rispettino le regole. Purtroppo un utente, guidato da interessi personali, potrebbe manipolare il protocollo per ottenere un beneficio a discapito degli altri utenti. Di conseguenza, la rete wireless sarebbe sfruttata in maniera inefficiente da un punto di vista sociale. Questa tesi si occupa della progettazione di protocolli in grado di prevenire le inefficienze dovute al comportamento egoistico e strategico degli utenti. Per raggiungere questo scopo, vengono sfruttati gli strumenti offerti dalla teoria dei giochi, la scienza matematica che modella e analizza l’interazione tra soggetti che possono prendere delle decisioni in maniera autonoma. La tesi copre aspetti legati alla gestione delle comunicazioni wireless a differenti livelli. Si inizia analizzando l’allocazione delle risorse radio, in fase di downlink, di una rete cellulare basata sulla tecnologia di accesso al mezzo di multiplazione a divisione di frequenza ortogonale (OFDMA). Viene proposto un algoritmo sub–ottimo basato sulla teoria dei giochi che permette di preservare la modularità del sistema ed é in grado di trovare un compromesso tra la massimizzazione del throughput totale e un livello equo delle prestazioni degli utenti. Successivamente, si analizza il problema di incentivare la cooperazione nelle reti wireless in cui gli utenti agiscono opportunisticamente da relay. Per incentivare gli utenti della rete a inoltrare i pacchetti spediti da altri utenti viene adottato uno scheduling dinamico, in cui gli utenti cooperativi sono premiati aumentando le loro opportunità di accesso al mezzo. La condivisione dell’infrastruttura é un’altra forma di cooperazione che potrebbe essere sfruttata per soddisfare la crescente esigenza di rate e qualità di servizio nelle reti wireless. A tal fine, si considera uno scenario in cui due reti wireless multi–hop sono disposte a condividere alcuni nodi, che agiscono da relay per entrambe le reti. Un’analisi basata sulle reti Bayesiane permette di stimare le prestazioni globali da alcuni parametri locali, mentre un’analisi basata sulla teoria dei giochi permette di selezionare in modo opportuno i nodi da condividere. In seguito, la nostra analisi si concentra sulle politiche di accesso al mezzo in reti wireless ad–hoc. Viene progettato un protocollo basato sugli schemi di pricing e intervention per incentivare gli utenti ad utilizzare il canale wireless efficientemente. Infine, si considera un altro importante problema che sorge nel momento in cui gli utenti sono egoisti e strategici: quando viene richiesto di riportare delle informazioni rilevanti, gli utenti potrebbero mentire, se ciò fosse nel loro interesse. Partendo da uno scenario generico, comprendente molte problematiche associate all’allocazione di risorse nelle reti di comunicazione, vengono forniti degli strumenti per progettare un sistema efficiente, in cui gli utenti sono incentivati a comunicare le informazioni veritiere e seguire le istruzioni del protocollo. Tali strumenti e risultati vengono applicati per progettare un sistema di controllo della congestione in una rete di comunicazione.