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.
Collections
- Doctoral Dissertations [14973]