Research On Packet Scheduling In Wireless Networks

With the rapid growth of mobile communications and Internet, the demands of wideband wireless access are becoming urgent. People expect that future mobile communication systems can provide higher transmission rates and satisfy more users with heterogeneous quality of service (QoS) requirements. Effective packet scheduling policies are critical to achieve this goal. In many circumstances, packet scheduling policies designed for wired networks and wireless static channels are inadequate for wireless networks because of the limited and time-varying wireless channel capacity. As a result, it is a hot topic in the area of wireless communications to design the packet scheduling algorithms by considering the characteristics of wireless time-varying channels with the objectives of providing QoS guarantees to users as well as increasing the capacities of the wireless networks.Opportunistic scheduling which exploits the independent and time-varying channel conditions of different users can obviously increase the spectral efficiency of wireless channels. Though always serving the users who have the best channel conditions (represented by the received SNRs) can maximize the system throughput, some fairness rules must be adopted in scheduling decisions in order to provide each user in the system with better QoS considering different wireless users can have distinct channel conditions. Since spectral efficiency and fairness are usually two conflicting design objectives, an effective opportunistic scheduling scheme should make an optimum trade-off between these two objectives based on the QoS requirements of users. In this dissertation, we investigate the packet scheduling mechanisms in a wireless time-varying and Time Division Multiplexing (TDM) system.First, the scheduling mechanisms for non-real-time services in wireless networks are investigated. Based on the improvement to the traditional maximum relative SNR (Max-rSNR) scheme, a modified Max-rSNR scheduling algorithm (M-Max-rSNR) is proposed which can provide short-term temporal guarantee. While possessing excellent long-term temporal fairness inherited from the Max-rSNR scheme, M-Max-rSNR can also insure each user get service over any short time interval in order to satisfy some non-real-time users' requirmets. Based on thses characteristics, M-Max-rSNR achieves better performance in terms of system/user throughput when compared with the proportional fair (PF) scheme. Meanwhile, noticing the lack of providing weighted temporal fairness of present opportunistic scheduling schemes, a wireless non-real-time service scheduling algorithm with short-term weighted temporal fairness is proposed (SFOS). This algorithm exploits both the virtual time mechanism and the Max-rSNR rule to make opportunistic scheduling while providing each user with weighted temporal service over any short interval. Secondly, the scheduling policies for wireless real-time services are studied. Since real-time services have stringent delay requirements, an effective scheduler should reduce the waiting time of the real-time service packets in each user's queue by exploiting opportunistic scheduling. Therefore, an opportunistic scheduler for wireless real-time services (ORS) is presented. In the ORS scheme, the priority function of each user includes both his relative SNR and an increasing concave function of the waiting time of the Head-Of-Line (HOL) packet in the user's queue. In this context, when each user has smaller waiting time, the user with the maximum relative SNR will be scheduled. Otherwise, if the waiting time of a user is approaching his deadline, the rapidly increased waiting-time function value makes the user get scheduled. Compared with the EXP and M-LWDF schemes which have been adopted in the HDR and HSDPA systems, ORS can obviously reduce both the average waiting time and the packet violation probabilities of all users in the system.Thirdly, the wireless scheduling strategies for a mixture of real-time and non-real-time services are designed. Since real-time and non-real-time users have quite different QoS requirements, the design for the scheduling policy that can offer higher QoS provisions to heterogeneous users is a critical issue for future wireless networks. Therefore, a packet fair queueing based hierarchical scheduling scheme (PFQ-HS) is proposed, which adopts an independent and hierarchical scheduling process. The first-stage scheduler of PFQ-HS can use any two scheduling schemes to make independent decisions for real-time and non-real-time services. Then, the second-stage scheduler uses a PFQ based opportunistic scheduling scheme (PFQ-OS) to guarantee service fairness. Compared with two scheduling schemes for a mixture of real-time and non-real-time services, i.e., MPF and VTQ, PFQ-HS can provide better QoS to heterogeneous users while maintaining temporal fairness.Fourthly, the power-saving scheduling algorithms for wireless real-time services are investigated. Since a majority of users in wireless networks are mobile terminals (MTs) powered by battery, the methods on reducing the power consumptions of these MTs are very critical for future wireless networks. An effective power-saving method is to put the wireless network interface (WNI) of the MT into sleep when it is idle. Based on this method, a joint buffering and scheduling power-saving scheme (JBS) is proposed, whose goal is to reduce the power consumptions of the MTs when they are used to receive the streaming services. In order to achieve this goal, JBS first employs a shaping buffer on the base station (BS) which buffers the input packets. Then JBS uses the ORS scheme to make scheduling decisions of the streaming packets. By this means, JBS can simultaneously buffer multiple packets in each user's queue and make each MT accumulate enough sleeping time over shorter time interval. Compared with the other two power-saving schemes, i.e., BKS and RBS, JBS can effectively reduce the power consumptions of the WNIs while ensuring the QoS provisions of the streaming users.