Cooperative Game Theory and Non-convex Optimization Analysis of Spectrum Sharing

Abstract

Opportunistic spectrum access has become a high priority research area in the past few years. The motivation behind this actively researched area is the fact that the limited spectrum available is currently being utilized in an inefficient way. The complete wireless spectrum is assigned and reserved, but not necessarily being used. At the same time, the demand for innovation in wireless technology is growing. Since there is no room in the wireless spectrum to allocate significant frequency bands for future wireless technologies, the only recourse is to increase utilization of the spectrum. To achieve this, we must find a way to share the spectrum.

Spectrum sharing techniques will require coordination between all the layers of the protocol stack. The network and the wireless medium are inextricably linked and, thus, both must be considered when optimizing wireless network performance. Unfortunately, interactions in the wireless medium can lead to non-convex problems which have been shown to be NP-hard. Techniques must be developed to tackle the optimization problems that arise from wireless network analysis.

In this document we focus on analyzing the spectrum sharing problem from two perspectives: cooperative game theory and non-convex optimization. We develop a cooperative game theory model to analyze a scenario where nodes in a multi-hop wireless network need to agree on a fair allocation of spectrum. We show that in high interference environments, the utility space of the game is non-convex, which may make some optimal allocations unachievable with pure strategies. However, we show that as the number of channels available increases, the utility space becomes close to convex and thus optimal allocations become achievable with pure strategies. We propose the use of the NBS and show that it achieves a good compromise between fairness and efficiency, using a small number of channels. We also propose a distributed algorithm for spectrum sharing and show that it achieves allocations reasonably close to the NBS.

In our game theory analysis, we studied the possible outcomes of the spectrum sharing problem and propose the NBS as a desirable outcome and propose an algorithm to achieve the NBS spectrum allocation. However, the expression used to compute the NBS is a non-convex optimization problem. We propose an optimization model to solve a class of problems that incorporate the non-convex dynamics of the wireless medium that occur when the objective is a function of SINR. We present two case studies to show the application of the model to discrete and continuous optimization problems. We propose a branch and bound heuristic, based on the RLT, for approximating the solution of continuous optimization problems. Finally, we present results for the continuous case study. We show simulation results for the heuristic compared to a time constrained mixed integer linear program (MILP) as well as a nonlinear optimization using random starting points. We show that for small networks the MILP achieves the optimal in reasonable time and the heuristic achieves a value close to the optimal. We also show that for large networks the heuristic outperforms the MILP as well as the nonlinear search.