Stochastic models for resource sharing in wireless networks

Next-generation wireless networks will likely evolve from cellular and small-scale home networks to large, inter-connected networks that form the backbone for low-cost internet access. A de??ning characteristic of wireless networks is that all nodes share the same medium for their transmissions, and consequently, simultaneous transmissions from nearby nodes will interfere with each other. The resulting performance issues can be mitigated by regulating node activity. Various mechanisms exist for regulating node access to the wireless medium, which can be categorized into scheduled-access and random-access algorithms. The former involve a centralized entity that controls the behavior of all nodes, while random-access constitutes a class of randomized, distributed algorithms. Random-access algorithms are popular for their simplicity, and their distributed nature makes them well-suited for large, dynamic wireless networks. Scheduled-access networks generally have better performance since the presence of an omniscient controller allows for coordination between nodes, but entail higher implementation complexity. One well-known algorithm for centralized access is MaxWeight scheduling, which is popular for its ability to achieve maximum stability and throughput optimality in a wide variety of scenarios. The distinguishing characteristic of MaxWeight policies is that these require solving the maximum weighted independent set problem of the underlying interference graph. The maximum-stability guarantees however rely on the premise that the system consists of a fixed set of flows, while in reality the collection of active flows dynamically varies. In Chapters 2 and 3 we demonstrate that in the presence of ow-level dynamics the algorithm may no longer be throughput-optimal, and we identify two causes for the instability: (i) failure to fully exploit rate variations; and (ii)spatial ineffciency. In Chapter 2 we consider the MaxWeight scheduling algorithm in a single downlink scenario with varying transmission rates. We identify a simple necessary and sufficient condition for stability, and show that MaxWeight policies may fail to provide maximum stability. The intuitive explanation is that these policies tend to favor flows with large backlogs, so that the rate variations of flows with smaller backlogs are not fully exploited.

• View at Publisher
• View at Worldcat