Packet scheduling in wireless networks

Recent years have witnessed rapid development in wireless networking technology, which aims to provide wireless users with quality of service (QoS) through wireless media. This dissertation examines how to design and analyze scheduling algorithms over wireless networks to guarantee QoS for heterogeneous traffic. More specifically, it addresses QoS issues rising from the inherent characteristics of wireless media including the high and bursty channel errors and scarce bandwidth of wireless link.; The channel errors in wireless networks are location-dependent, which impairs the fairness in bandwidth allocation. Correspondingly, various compensation mechanisms have been proposed to deal with the problem of unfairness resulting from location dependent channel errors. To evaluate and improve the performance of systems carrying on fair scheduling with compensation mechanisms, we develop a Two-stage Quasi Tandem Queue (TSTQ) model for such systems accordingly. This model has been used to quantify the relationship between system parameters like lagging bound and performance metrics.; The channel errors are also shown to be time-varying, which leads to a time-varying bandwidth over the wireless networks. To adapt to the variable wireless channel bandwidth, we propose a new scheduling algorithm, called Variable-Weight GPS (VWGPS), for channels with variable capacities. The major feature of the VWGPS algorithm is its capability to accommodate flows with dissimilar tolerances to service quality degradation. Like the GPS (Generalized Processor Sharing) model, VWGPS allocates channel capacity to flows according to corresponding weight values.; The other characteristic is the scarce bandwidth of wireless link. Because of this unique characteristic, it is critically important to utilize the limited bandwidth efficiently. At the end of this dissertation, we study the way to efficiently integrate a fair scheduling algorithm to a widely used multiple access scheme, the multi-code CDMA (MC-CDMA), which results in a novel MAC protocol. The key difficulty of typical MAC for MC-CDMA is the nature of the distributed queues for the uplink, which results in significant workload caused by the message overhead to inform the centralized scheduler of the queue states. In our protocol, frame structure is employed for packet transmission, which eliminates frequently reporting states. In addition, packets with similar SNR requirements are located to the same time slots in each frame, which maximizes the throughput of the system. Analysis and simulations show that our MAC protocol together with scheduling algorithms achieves fair bandwidth allocation and efficient utilization of wireless resource. (Abstract shortened by UMI.)...