Capacity of wireless systems under distributed scheduling of time-dependent users

Consider the problem of a multiple access channel with a large number of users K. While several multiuser coding techniques exist, in practical scenarios, not all users can be scheduled simultaneously and choosing the most suitable user to transmit can boost network performance dramatically. This is the essence of multi-user diversity. Although the problem has been studied in various time-independent scenarios, capacity scaling laws and algorithms for time-dependent channels (e.g., Markov channels) remains relatively unexplored. In this work, we consider the Gilber-Elliott Channel as a model for a simple time-dependent channel, and derive the expected capacity under centralized scheduling. We show that the capacity scaling law is O (σ_g √2 log K + μ_g), where σ_g and μ_g are channel parameters during the good channel state. In addition, a distributed algorithm for this scenario is suggested along with it´s capacity analysis. The expected capacity under distributed scheduling scales (in K) the same as under centralized scheduling, hence, there is no loss in optimality due to the distributed algorithm. The analysis uses tools from Extreme Value Theory and Point Process Approximation.