Game theoretic models for resource sharing in wireless networks

In the last years, wireless communications have been characterized by an impressive growth of standards and technologies, and, as a result, the increasing demand in wireless spectrum has shown that current policies for the use of the available “resources” are inadequate. Furthermore, the rapid proliferation of wireless access networks and the evolution of the end–user terminal are increasing the opportunities for a mobile user to connect anytime and anywhere and, differently from the past when wireless connectivity was monopolized by a single operator/technology, the overprovisioning of access networks nowadays allows mobile users to choose among multiple access opportunities on the base of availability, cost and/or quality, eventually achieving a seamless, ubiquitous, and pervasive connectivity experience. At the same time, the increasing demand in wireless spectrum has shown that new, more flexible spectrum management schemes are necessary to improve the efficiency in spectrum usage. Within this field, recent advancements in the field of software–defined radios allow the development of spectrum–agile devices that can be programmed to operate on a wide spectrum range and tuned to any frequency band in that range with negligible delay. Resulting cognitive radios are able to sense a wide spectrum range, dynamically classifying spectrum blocks for data communications, and “intelligently” selecting the best spectrum opportunity. To reach the ambitious goal of providing seamless and pervasive connectivity to end users, however, many technical challenges still have to be addressed in different fields, e.g., on the network side, signaling architectures are required to effectively support user’s mobility among multiple networks and to manage the radio resource allocation process, on the user side, effective techniques are required to discover and classify the multiple connectivity opportunities based on quality parameters (actual throughput, access delay, wireless interference level) to steer eventually the dynamic selection of the best connectivity opportunity. In a nutshell, all the opportunities introduced by the technological advances have considerably increased the degrees of freedom offered to the end users, but they have also increased complexity and heterogeneity in the network design and management. In fact, end users can now seamlessly select the “best” wireless access network to connect to (problem of network selection), being even allowed to exploit the available spectrum, taking decisions that are based on the current availability of different spectrum opportunities (problem of spectrum sharing). These two scenarios are inherently characterized by some sort of competitive dynamics among the users, which may compete to get access to the best network and/or to the best spectrum portion. To this extent, a deeper understanding and prediction of such dynamics is central to quantitatively characterize the potentials of future wireless networks. This work aims at shedding light on the performance modeling of radio resource sharing/allocation situations. Since, in general, the quality of service perceived by a system (e.g., user, network) strictly depends on the behavior of the other entities, and the involved interactions are mainly competitive, this work introduces a frame- work based on non–cooperative game theoretic tools to characterize radio resource sharing/allocation. Non–cooperative game theory is suitable in distributed networks, where control and management are inherently decentralized. In detail, we propose non–cooperative game theoretic models for network selection and spectrum sharing by considering different scenarios where both users and networks take part in the game. First, we consider the case in which many users have to make decisions on which wireless access point to connect to. In this scenario, the quality perceived by the users mainly depends on the number of other users, i.e., congestion, choosing the very same accessing opportunity. We provide several congestion games both in wireless and mesh networks. We then consider the case in which also networks take part into the competition. In this context, we consider two–stage games where networks make decisions on how to use the available resources, and users react to this selecting the network that maximizes their satisfaction. Then, we refer to the problem of spectrum sharing, where users directly compete for portions of the available spectrum. Also this problem can be modeled as a congestion game. Furthermore, we also assume a time–varying availability of the spectrum, and we introduce a repeated game. Finally, we provide a more complex model where the users utility function is based on the Shannon rate. The aim of this second part is to provide a better representation of the satisfaction perceived by the users, i.e., in terms of achievable throughput. Due to the complexity of the game, we first provide a complete analytical study of the two–user case. Then, we extend the analysis to the N–user case. First, we analyze the game through simulations. Then, inspired by the obtained results, we introduce stochastic geometry in the analysis of the spectrum game. Namely, we first provide a stochastic characterization of the two–player game, assuming that nodes are placed at random over a disk. Then, we leverage the analysis to give an asymptotic expression for the coupling probability in a game where the transmitter positions form a (low density) Poisson process, which may be interpreted as the fraction of players essentially playing a two–player game. Finally, using a directed–influence–graph approach, we show how we can study the N–player game and predict the performance in large networks.

Negli ultimi anni, le comunicazioni wireless sono state caratterizzate da un imponente aumento di nuovi standard e tecnologie. Inoltre, la crescente richiesta di spettro ha dimostrato che le attuali politiche di assegnamento dello stesso sono fortemente inadeguate. Allo stesso tempo, la diffusione e l’evoluzione dei terminali stanno crescendo le opportunità per gli utenti di essere connessi sempre e ovunque e, a differenza del passato, la connettività wireless non è più monopolizzata da un singolo operatore o basata su una singola tecnologia. Di conseguenza, nuove e più flessibili politiche di accesso allo spettro sono necessarie per un migliore utilizzo dello stesso. In questo contesto, diversi problemi possono essere presi in considerazione. In particolare, dal punto di vista degli utenti, uno dei problemi fondamentali è la selezione della migliore opportunità d’accesso, cioè la migliore rete, la migliore tecnologia o più nello specifico la migliore porzione di spettro disponibile. Dal punto di vista della rete invece, il problema fondamentale è come utilizzare le risorse (lo spettro) disponibili. Una delle metodologie più utilizzate in quest’ambito è la teoria dei giochi. Infatti, le diverse entità (utenti, reti) competono e si influenzano reciprocamente, ognuna cercando di massimizzare i propri obiettivi. In questo lavoro, sono stati proposti modelli di gioco per analizzare l’interazione tra utenti e reti che competono per utilizzare e condividere lo spettro disponibile. Il primo modello di gioco considera il problema di selezione della rete in scenari in cui ogni utente ha a disposizione diverse reti a cui connettersi, e sceglie la rete che massimizza la propria utilità. Il problema può essere modellato con un gioco, poiché l’utilità/costo di ogni giocatore dipende anche dalle scelte degli altri. Sono state studiate quattro diverse funzioni costo, in cui si tiene conto non solo della banda nominale offerta dalla rete, ma anche dell’interferenza, che in reti basate sulla tecnologia WiFi è un elemento necessario per la valutazione dell’effettivo throughput raggiungibile dall’utente. L’analisi del problema della selezione della rete è stata condotta anche in scenari di rete mesh. Il secondo modello di gioco unisce il problema di selezione della rete a quello di allocazione delle risorse, in cui le reti competono nell’allocazione delle porzioni di spettro disponibili. In questo caso il gioco è bi-livello, perché l’utilità di ogni rete dipende, non solo dalle scelte prese da altre reti, ma anche dal gioco degli utenti. L’utilità massimizzata da ogni rete è funzione del numero di utenti che decidono di connettersi alla rete stessa. Il terzo modello di gioco considera il problema di condivisione dello spettro in reti cognitive, in cui le porzioni di banda non utilizzate dagli utenti primari possono essere sfruttate dai secondari. In particolare, la gestione dello spettro comprende diverse funzionalità, quali la classificazione delle bande disponibili, spectrum decision, la gestione dell’interferenza tra utenti, spectrum sharing, la caratterizzazione del costo legato allo spostamento (switching) tra diverse porzioni di spettro, spectrum handover. Si è proposto un framework per la valutazione di queste funzionalità basato sulla teoria dei giochi non cooperativi. L’analisi statica del gioco comprende la valutazione e il confronto di molteplici funzioni costo. L’analisi dinamica considera invece uno scenario tempo-variante, in cui le decisioni degli utenti sono ripetute ogni qual volta la disponibilità dello spettro cambia. Il problema dinamico è modellato con un gioco ripetuto, in cui si tiene conto del costo di switching. La condivisione dello spettro è stata analizzata anche in scenari ah-hoc, dove gli utenti condividono porzioni di spettro con l’obiettivo di massimizzare l’effettivo throughput percepito dagli utenti (espressione del rate di Shannon). L’analisi del gioco è stata inizialmente condotta considerando uno scenario composto da due coppie di utenti. In questo caso, gli equilibri di Nash sono stati caratterizzati in forma chiusa. I risultati hanno dimostrato che la qualità e il numero degli equilibri dipendono dalle posizioni degli utenti. Di conseguenza, è stata introdotta la geometria stocastica per caratterizzare il gioco quando gli utenti sono disposti casualmente in un’area circolare. La caratterizzazione stocastica del gioco è l’elemento fondamentale per analizzare il caso composto da molti giocatori. In questo scenario, si è innanzitutto derivata la probabilità dei giocatori di essere accoppiati, cioè di giocare un gioco a due. Infine, utilizzando un approccio basato sui grafi, si mostra com’è possibile studiare il gioco in reti di grandi dimensioni.