Marco Luise, Giacomo Bacci
The ever-increasing demand for reliable and ubiquitous high-speed data services calls for new challenges in the design of wireless communication networks. In the near future, wireless networks are expected to support a variety of applications with different quality of service (QoS) constraints. In the last two decades, considerable effort has been made to providing efficient schemes to address resource allocation issues, possibly involving cross-layer optimization. Such design and optimization methods are benefiting from the adoption of sophisticated signal processing techniques at large.
Recently, game theory has emerged as an effective framework for the design of a wireless network. Game theory is a broad field of applied mathematics aimed at describing and analyzing interactive decision processes. In particular, it provides analytical tools to predict the outcome of interactions among rational entities, where rationality calls for strict adherence to a strategy based on perceived or measured results. Traditionally, the main areas of application of game theory have been economics, political science, biology and sociology, but recently, it has also been widely used in telecommunications and wireless communications. The interaction of the users in a wireless network can be modeled as a game in which the user terminals are the players in the game competing for network resources (i.e., bandwidth and energy), which are typically scarce. Any action taken by a user affects the performance of other users as well, and game theory turns out to be a natural tool for investigating this interplay.
This tutorial provides an overview of the relevant applications of game theory in wireless communications, focusing on noncooperative techniques. An important feature of the noncooperative approach is the inherent de-centralization of the algorithms, which allows each user to individually choose its own strategy (e.g., power transmit level at the physical layer, bandwidth allocation at the medium access layer, packet forwarding at the network layer) through a simple noncooperative scheme. Distributed (noncooperative) solutions are in general suboptimal with respect to those obtained via a centralized (cooperative) approach, but they are well suited to a many-node network due to their intrinsic scalability and the simplicity of the relative solutions. The centralized approach, although optimal, is often characterized by NP-hard problems, whose solutions cannot be reasonably computed (or even approximated) in real-time. The complete de-centralization of the resource allocation scheme allows for the total absence of an infrastructure, which is highly desirable to extend game-theoretic techniques to the design of wireless ad-hoc networks.
In the first part of the tutorial, the basic concepts will be introduced by means of many toy examples taken from concrete problems faced every day in the context of wireless communications. The purpose of such examples is to help understanding the motivations that led many engineers to model networks as economic systems.
In the second part of the tutorial, the relevant applications of noncooperative game theory to wireless networks design are reported, emphasizing the discussion on how to translate a real-world problem to an analytical game model. The main focus will be on the first two layers of the OSI stack, including cross-layer optimizations. Due to the wide literature available on the topic, it is impossible to give an in-depth course on game theory in a three-hour tutorial. Hence, we will not intend to provide an extensive review of all ongoing approaches of game theory, but rather to focus on significant examples of its application.
Marco Luise is a Full Professor of Telecommunications at the University of Pisa, Italy. He was born in Livorno, Italy, in 1960 and received his MSc (cum Laude) and PhD degrees in Electronic Engineering from the University of Pisa, Italy. In the past, he was a Research Fellow of the European Space Agency (ESA) at the European Space Research and Technology Centre (ESTEC), Noordwijk, The Netherlands, a Researcher of CNR (the Italian National Research Council), at the Centro Studio Metodi Dispositivi Radiotrasmissioni (CSMDR), Pisa, and an Associate Professor at the Dipartimento di Ingegneria dell'Informazione (Dept. of Information Engineering) of the University of Pisa. He chaired the V, VI, VII, and IX editions of the Tyrrhenian International Workshop on Digital Communications, respectively, and he was the General Chairman of the URSI Symposium ISSSE'98. He served as the Technical Co-Chairman of the 7th International Workshop on Digital Signal Processing Techniques for Space Communications and of the Conference European Wireless 2002. Recently, Prof. Luise was the General Chairman of EUSIPCO 2006 held in Florence, Italy, in September 2006. He regularly teaches at the University of Pisa and at the Lucca Institute for Advanced Studies IMT. M. Luise is a senior member of the IEEE, was an Editor of the IEEE Transactions on Communications and has served as the co-editor of the ‘98 Special Issue on Signal Processing in Telecommunications of the European Transactions on Telecommunications. He was a co-editor of the IEEE Journal of Selected Areas in Communication special issue on Signal Synchronization in Digital Transmission Systems and Editor for Communication Theory of the European Transactions on Telecommunications, and has co-edited a Special Issue of the Proceedings of the IEEE on Turbo techniques: algorithms and applications. He is the co-Editor-in-Chief of the recently founded International Journal of Navigation and Observation, and acts as General Secretary of the Italian Association GTTI, Gruppo Telecomunicazioni Teoria dell'Informazione. He is also member of the Italian Committee of URSI and of the International Committee on Global Navigation Satellite Systems (ICG) of the UNO. His main research interests lie in the broad area of communication theory, with particular emphasis on wireless communications, and mobile and satellite communication and positioning systems. A full list of Prof. Luise’s scientific publications is available at http://www2.ing.unipi.it/~d7384/HTML/PubFrm.html
Giacomo Bacci was born in Cecina, Italy, in 1980. He received the B.E. and the M.E. degrees in telecommunications engineering and the PhD degree in information engineering from the University of Pisa, Pisa, Italy, in 2002, 2004, and 2008, respectively. Since 2005, he has been with the Department of Information Engineering at the University of Pisa. In 2006/07, he was a visiting student research collaborator at the Department of Electrical Engineering at Princeton University, Princeton, NJ, under the supervision of Prof. H. V. Poor. His research interests are in the areas of digital communications, signal processing and estimation theory. His current research topics focus on power control and resource allocation for multiple-access wireless networks and time delay estimation for satellite positioning systems and wireless communications.
Dr. Bacci is currently a post-doc research fellow and a teaching assistant at the University of Pisa for the M.E. degrees in telecommunications engineering and computer science engineering, and serves as a reviewer for IEEE Transactions on Wireless Communications, IEEE Journal on Selected Topics in Signal processing, IEEE Communications Letters and many international conferences. He received the best student paper award from the International Waveform Diversity and Design Conf., Pisa, Italy, in 2007, and the best session paper at the ESA Workshop on EGNOS Performance and Applications, Gdynia, Poland, 2005. He was also recipient of a scholarship issued by the Italian Ministry of Education for his PhD program.