Scheduling for fairness and minimal response times in wireless data networks.

摘要

The rapid growth of the Internet has led to the emergence of wireless data networks that enable truly nomadic computing. These wireless networks can be categorized into two complementary types: (a) cellular networks, where a base station connects mobile devices to the Internet, and (b) ad hoc networks, where mobile devices form a distributed network among themselves. With the exponential increase in the number of wireless data users, providing quality of service (QoS) in these networks becomes critical. Scheduling at the MAC layer enables us to provide fine-grained QoS to users. In this thesis, we focus on the design of scheduling algorithms to address various QoS issues in cellular and ad hoc networks.; Ad hoc networks are decentralized and do not have the notion of a base station to control channel access. Simultaneous transmissions and location-dependent contention make it difficult to characterize the rates that hosts and flows can obtain in an ad hoc network. We develop a framework to model the nature of wireless channels and obtain a distributed algorithm that can be used to realize a desired fair rate structure in the ad hoc network. A large class of fairness models are applicable to our work.; Next generation 3G/4G cellular data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users in such networks poses the two-dimensional challenge of assigning both power (rate) and codes for every a communication-theoretic model for multirate wireless channels, and attempt to optimize the maximum response time of jobs, a QoS metric suitable for a stream of user requests. Using a novel approach called resource augmented competitive analysis, we present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, online algorithms for approximating the optimal response time.; We believe that using our analytical techniques will result in simple, efficient and practical scheduling algorithms for providing QoS in wireless data networks.