Matching Theory for Wireless Networks

The prevalence of high-performance mobile devices such as smartphones and tablets has brought fundamental changes to existing wireless networks. The growth of bandwidth-intensive multimedia and location-based mobile services has exponentially increased the network congestion and the demand for the wireless spectrum. The high computational complexity and communication overhead associated with conventional centralized resource management methods will no longer be suitable to capture the scale of tomorrow’s wireless networks. As a result, resource management in next-generation networks is shifting from conventional solutions that rely on centralized optimization to self-organizing solutions in which intelligence is distributed across the network devices and nodes. The goal of this book is to demonstrate the effectiveness of matching theory, a Nobel-prize winning operational research framework, for solving the wireless resource allocation problems in a distributed manner. Matching theory has already been widely used to solve challenging economic problems. More recently, matching theory has been shown to have a promising potential for modeling and analyzing wireless resource allocation problems due to three reasons: (1) it offers suitable models that can inherently capture various wireless communication features; (2) the ability to use notions, such as preference relations, that can interpret complex system requirements; (3) it provides low-complexity and near-optimal matching algorithms while guaranteeing the system stability. In order to understand the potential of matching theory for wireless resource management, in this chapter, we start by providing an overview on the recent changes in the wireless landscape which, in turn, motivate the need for distributed, matching-based resource management solutions.

Matching theory, in economics, is a mathematical framework that allows analyzing the formation of mutually beneficial relationships over time. Prior to the seminal work of Gale and Shapley on the stable marriage and college admission problems in 1962, many matching problems were solved by the “free for all market”. The “free for all market” term refers to the period before matching theory was conceived as a discipline, as well as the way in which matching problems were dealt with during the period. Economists have identified several issues such as unraveling, congestion, and exploding offers in the “free for all market”. Since then, with decades of efforts devoted to developing matching algorithms (i.e., there arises a trusted third party, which collects information, runs a matching algorithm, and broadcasts the matching results), these challenges were overcome. As a result, there has been a surge in the development of matching frameworks that have become widely used in many areas, such as the national resident matching program in the United States, the college admission in Hungary, the incompatible kidney exchange market, and the partnership formation in peer-to-peer (P2P) network, among others.

In device-to-device (D2D) communication networks, wireless users communicate directly without using a BS. D2D commutations can naturally improve spectrum efficiency. However, the interference introduced by the resource sharing in D2D is a key challenge that must be overcome to reap the benefits of D2D networks. In this chapter, we optimize the system throughput of a D2D-enabled cellular network while simultaneously meeting the QoS requirements for both D2D users and cellular users (CUs). We implement the SM model to solve the resource allocation between D2D users and CUs. We introduce two stable matching algorithms to optimize the social welfare while ensuring the network stability. Moreover, we introduce the idea of cheating in matching to further improve D2D users’ throughput. The cheating mechanism is proven to be able to benefit a subset of all the D2D users without reducing the rest of D2D users’ performances. Through the simulation results, we demonstrate the effectiveness of our algorithms in terms of improving the throughout of both D2D users and the entire cellular systems.

The study item: “Feasibility Study on LTE-based V2X Services”, approved at 3GPP TSG RAN #68, has drawn much attention in the study of the LTE assisted V2V and V2I communications in the vehicular networks. By deploying the D2D technology adopted in the traditional cellular networks into the V2X communications (including both the V2V and V2I communications), performance improvements can be expected, such as better reliability, lower latency, and more efficient content sharing. This chapter investigates the content sharing problem in the D2D-based V2X communications. With both vehicles and eNBs carrying different types of data, this chapter studies how to optimize the information exchanged within the network. By jointly considering the data diversity and the communication link quality, the interactions between the vehicles/eNBs are modeled as the SF matching game. Different from the traditional D2D communications, we allow vehicles.eNBs to set up multiple link connections for to further optimize the content sharing in the Vehicular ad hoc networks (VANETs). The SF game is solved by the Irving’s stable fixture (ISF) algorithm.

A Content caching techniques have emerged as a promising approach to support the backend storage of online social networks (e.g., Facebook) by reducing the service latency and improving the user satisfaction. However, the limited caching capacity and increasing user traffic have posed new challenges for content cache allocation. In this chapter, we investigate a three-layer caching model and investigate how to efficiently allocation the contents to different cache centers to minimize the overall service latency. We tackle this issue by utilizing both the centralized MILP optimization approach and the distributed CA matching-based approach. In the CA model, we leverage the Resident-oriented Gale-Shapley (RGS) algorithm to yield a stable matching between the contents and the cache centers. We compare the performances of the centralized and distributed algorithms regarding both the system welfare and the computation complexity.

The integration of millimeter-wave base stations (mmW-BSs) with conventional microwave base stations (\(\mu \)W-BSs) is seen as an integral component of tomorrow’s 5G wireless cellular systems. However, there exist significant differences in the signal propagation characteristics over the mmW and \(\mu \)W frequency bands that motivate the development of new cell association schemes cognizant of both mmW and \(\mu \)W systems. As seen thus far, matching theory provides a suitable framework for studying such problems in cellular systems. To this end, in this chapter, we introduce a matching-based cell association framework that jointly considers the blockage probability and the achievable rate to assign user equipments (UEs) to mmW-BSs or \(\mu \)W-BSs. Here, we use a one-to-many matching solution which requires minimum quota constraints for each BS in the system. The investigated matching solution is then shown to be a key enabler for load balancing over the mmW and \(\mu \)W frequency bands. We then show that, for the matching game with minimum quota, one can develop a distributed algorithm that is guaranteed to yield a two-sided stable and Pareto optimal solution for the cell association problem. Simulation results then show the effectiveness (in terms of sum-rate and load balancing) of using a matching-based approach as opposed to conventional cell association schemes, such as max-RSSI or max-SINR.

The use of LTE-Unlicensed is a promising approach to aggregate both licensed and unlicensed spectrum bands, in an effort to meet the QoS of emerging wireless services. In this chapter, we investigate the problem of carrier aggregation between licensed and unlicensed spectrum by deploying LTE-Unlicensed enabled micro-cell base stations, which have access to the unlicensed spectrum, to provide cellular users a more reliable and efficient transmission. We address the unlicensed resource allocation problem by modeling it as a student-project allocation matching game. In addition, a post-matching procedure of resource re-allocation is introduced to guarantee unlicensed users’ QoS, as well as the system-wide stability. The simulation evaluation shows the effectiveness and efficiency of our investigated matching-based approach.

This book has provided an overview on fundamental research problems at the intersection of wireless communications and the Matching Theory. We have mainly developed the book from the following four aspects: (1) We have provided an overview of the basic concepts, classifications, and models of matching theory.