Wireless packet scheduling for two-state link models

Packet scheduling is key to the provision of Quality of Service (QoS) differentiation and guarantees in a wireless network. Unlike its wireline counterpart, wireless communication poses special problems such as time-varying link capacity and location-dependent errors. These special problems make designing efficient and effective scheduling algorithms for wireless networks very challenging. Although many wireless scheduling algorithms have been proposed in recent years, some issues remain unresolved. This paper introduces a new wireless scheduling algorithm called BGFS-EBA (bandwidth-guaranteed fair scheduling with effective excess bandwidth allocation), which addresses these issues. It is shown that BGFS-EBA distributes excess bandwidth effectively, strikes a balance between effort-fair and outcome-fair, and provides delay bound for error-free flows and transmission effort guarantees for error-prone flows. The new algorithm is compared with some recent wireless scheduling algorithms.