AbstractsComputer Science

With the fast growing deployment of smart mobile devices and increasingly demanding multimedia applications, the future wireless networks must provide high-quality services to mobile users under resource-limited conditions. This necessitates the design of efficient and distributed algorithms with various key characteristics: high throughput, low energy consumption, fast convergence, low delay, and regular service. Earlier works extensively study the first-order metrics, such as throughput, fairness, and energy consumption, and very few of them address the second-order metrics, such as convergence speed, delay and service regularity  – critical for the growing time-sensitive and dynamic applications penetrating the wireless networks. Also, it is important to consider the distributed implementations of theoretically proven efficient algorithms. To that end, this dissertation mainly focuses on the following two aspects: (i) the performance and optimization of the second-order metrics; (ii) the distributed algorithm design. In the first part of this dissertation, we first develop a cross-layer algorithm that achieves the optimal convergence speed at which the running average of the received service rates and the network utility over a finite time horizon converges to their respective limits under the discrete transmission rate selections  – a typical feature of wireless networks. This result is important in twoaspects, in revealing a previously-unknown limit on how fast the service rates can approachan optimal point, and in providing a new algorithm that achieves the fastest possible speed.Then, we focus on the efficient algorithm design for overcoming unavoidable temporary overloads. We develop a novel ``queue reversal'' approach that relates the metrics in unstable systems to the metrics in stable systems, for which a rich set of tools and results exists. Furthermore, to support widely popular real-time applications, we develop a scheduling algorithm that simultaneously achieves maximum throughput, minimum delay in heavy-traffic regimes, and service regularity guarantees.In the second part of this dissertation, we first explore the throughput limitations of randomized schedulers that are widely used in distributed implementations. This systematic study is important in helping network designers to use or avoid certain types of probabilistic scheduling strategies depending on the network topology. Then, we turn to the distributed design of an optimal scheduling algorithm forserving both elastic and inelastic traffic over wireless fading channels. The corresponding result provides one of the first promising means of effectively handling changing conditions in distributed resource allocation algorithm design. Noting the high energy cost and operational difficulty for all users to continuously estimate the channel quality before each transmission, we further design efficient and distributed joint channel probing and scheduling strategies under energy constraints.Overall, this thesis develops methodologies to study the…