This non-provisional application claims the benefit of U.S. Provisional Application Ser. No. 60/744,627, filed on Apr. 11, 2006 entitled “Real Time Scheduler Design for Enhanced 3G Cellular Uplink Packet Access” the contents of which hereby incorporated by reference herein.
The present invention relates generally to cellular communications, and more particularly, to real time uplink scheduling for real time packet services in third generation (3G) and beyond cellular systems.
The third-generation (3G) cellular systems, e.g., CDMA2000 1xEV-DO.A, described in the 3gpp Technical Specification 25.309 version 6.3.0, “FDD enhanced uplink, overall description, Stage 2”, June 2005 and the writing by M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, P. Whiting, and R. Vijayakumar, “Providing quality of service over a shared wireless link”, IEEE Commun. Mag., pages 150-154, February 2001”, and WCDMA Release 6 High Speed Uplink Packet Access (HSUPA) or Enhanced Dedicated Channel (E-DCH) described in ITU-T Recommendation H.263, “Video Coding for Low Bitrate Communication, 1996”, were recently standardized to meet an increasing demand for high-speed packet uplink services from mobile cellular users. Both systems adopt base station-based Hybrid ARQ (HARQ) retransmission and scheduler over dedicated, time-slotted CDMA code channels for mobile users (MSs). Multiple mobile users MSs access the base station (BS) through a media access control (MAC)-layer scheduling approach.
The 3G cellular system 1xEV-DO.A allows a hybrid of centralized and distributed control of MAC, while HSUPA has a corresponding approach, namely relative grant (RG), and also a centralized approached, named absolute grant (AG), to schedule mobile users MSs uploading slot by slot. In contrast to the scheduler adopted in 1xEV-DO.A, where BS considers MSs' requests and system's loads to control deterministically and the current rates of all MSs in a differential manner (UP/DOWN/KEEP), the centralized AG scheduler at the serving BS grants explicit rate to each MS on basis of their report of traffic volume measurement (TVM), power headroom, and quality of service (QoS) states. The AG scheduler may thus have more control flexibility and responsiveness to bursty and real-time packet services, such as MPEG4 or H.263 encoded video uploading. See the references, E. Esteves, “On the reverse link capacity of CDMA2000 high rate packet data systems”, in Proc. IEEE Int. Conf. Commun. (ICC), pages 1823-1828, April-May 2002 and F. Fitzek and M. Reisslein, “MPEG-4 and H.263 video traces for network performance evaluation”, IEEE Networks Mag., 15(6), November/December 2001. A focus of the invention is a scheduler for real-time (RT) AG services at the serving cell.
There have been intense research activities in the field of uplink scheduling over synchronous or asynchronous CDMA systems. As mentioned above, the 3G cellular system, 1xEV-DO.A, see P. Tinnakornsrisuphap and C. Lott, “On the fairness of the reverse-link MAC layer in CDMA2000 1xEV-DO”, In Proc. IEEE Int'l Commun. Conf. (ICC), Paris, France, June 2004, adopted a pure CDMA approach with equal SINR among active users. Explanation of the invention further below will show that the equal-rate CDMA (ER-CDMA), a centralized version of 1xEV-DO.A's approach that also presents optimal performance bounds, fails to exploit multiuser diversity gain and therefore delivers low performance and especially low efficiency (in bits/s/watt).
Very recently P. T. Kabamba, S. M. Meerkov, and C. Y. Tang, in their work entitled, “Ranking and adaptive ranking cdma”, IEEE/ACM Trans. on Networking, 13(3):622-635, June 2005, (hereinafter Kabamba et al), proposed ranking and adaptive ranking CDMA (R-CDMA or AR-CDMA) approaches to minimize the summed mean power consumption among all mobile users MSs, where at each time slot an optimal group of n out of N mobile users MSs is selected based on a sorted list of (normalized) per-user channel quality. All active users transmit with an equivalent (and feasible) received signal-to-interference-and noise-ratio SINR. In contrast to the legacy purely CDMA scheme, referred to as constant SINR CDMA (C-SINR-CDMA) in the paper by Kabamba et al., AR-CDMA and R-CDMA are actually hybrid TDMA/CDMA approaches with and without location-aware fairness, respectively. It remains to be seen how they may perform if given delay-sensitive applications, per-user constraints of transmission power, and the RoT upper bound. In addition, the imposed requirement of equal signal-to-interference plus noise ratios (SINRs) among active MSs at each time slot need further justification, especially when the uplink traffic pattern is bursty, e.g., variable-bit-rate videos.
As referred in Kabamba et al., SINR-threshold based uplink scheduling approaches, see S. W. Kim and A. J. Goldsmith entitled, “Truncated power control in code-division multiple-access communications”, IEEE Trans. Veh. Technol., 49(3):965-972, May 2000, and by S. W. Kim and Y. Lee, entitled “Combined rate and power adaptation in DS/CDMA communications over nakagami fading channels”, IEEE Trans. Commun., 48(1):162-168, January 2000, which turn off poor-channel users and enable strong-channel users to transmit with equal received SINRs or fixed transmission power, suffer from location-dependent service unfairness. In addition, it is very difficult to decide a reasonable channel threshold in practice. Both approaches are TDMA/CDMA hybrid.
Other important work in hybrid TDMA/CDMA scheduling includes that by K. Kumaran and L. Qian, entitled “Uplink scheduling in CDMA packet-data systems”, In Proc. IEEE INFOCOM, pages 292-300, April 2003, (hereinafter Kumaran et al.), and by S.-J. Oh, T. L. Olsen, and K. Wasserman, entitled “Distributed power control and spreading gain allocation in cdma data networks”, In Proc. IEEE INFOCOM, pages 379-385, Tel Aviv, Israel, April 2000, (Oh et al.). Both these works were trying to maximize the summation of weighted throughput of all MSs at each time slot. Per-user received power at the BS is constrained. Following Oh et al. and Kumaran et al. shows that the problem is to maximize a convex function at each time slot under linear constraints, where the optimal solution is the full-power transmission by an optimal subset of active MSs. Analysis in Kumaran et al. shows that the optimal solution is actually purely CDMA when the per-user power limitations are severe, or TDMA when the limitations are removed. However, as an NP-hard problem, it can only be approximately solved in polynomial time by heuristic approaches, such as the greedy QPR process, see Kumaran et al., that chooses a single “strong” user (with small power), or a group of “weak” users (with large power and high traffic backlog or “weight”). Based on the same heuristics, Kumaran et al. also proposed an uplink proportional fair (UPF) scheme, a simple modification of proportional fair (PF), see A. Jalali, R. Padovani, and R. Pankaj, “Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system”, In Proc. IEEE Veh. Tech. Conf. (VTC), pages 1854-1858, May 2000 (hereinafter Padovani et al.) and P. Viswanath, D. N. C. Tse, and R. Laroia, entitled, “Opportunistic beamforming using dumb antennas”, IEEE Trans. Inform. Theory, 48(6):1277-1294, June 2002 (hereinafter Viswanath et al.), disclosed an process for downlink scheduling, to maximize (weightless) summation of users' throughput by encouraging simultaneous transmission of “weak” users.
There has been extensive work on downlink scheduling. However, uplink scheduling over multi-access channels differs significantly from its downlink counterpart over a shared broadcast channel. It is well known that for non-real-time (NRT) data services, resource fairness and aggregate system throughput are the most important concerns. Existing NRT downlink scheduling processes, such as max-C/I, see R. Knopp and P. A. Humblet, entitled “Information capacity and power control in single cell multiuser communications”, In Proc. IEEE Int. Conf. Commun. (ICC), pages 331-335, June 1995 (hereinafter Humblet et al.), proportional fair PF, see Padovani et al., and Viswanath et al, as well previous work, the Weighted Alpha-Rule (wAlpha-Rule), see A. Sang, X. Wang, M. Madihian, and R. D. Gitlin, “Downlink scheduling schemes in cellular packet data systems of multiple-input multiple-output antennas”, In Proc. IEEE GLOBECOM, Dallas, Tex., November 2004, an extended version in IEEE Trans. Wireless Commun., Vol. 5, No. 1, January 2006, (hereinafter Sang et al.—Downlink Sheduling . . . ), are all TDM based. Namely they schedule one user per time slot. All schemes focus on channel state exploitation under the assumption of infinite data backlog. Note that the (resource) fairness becomes a secondary issue in RT services.
On the other hand, existing RT downlink scheduling processes for 3G and Beyond cellular systems, such as the modified largest-weighted delay first (M-LWDF), see 3gpp2 C.S20024-A V1.0.CDMA2000, “High Rate Packet Data Air Interface Specification”, March 2004 (hereinafter 3gpp2-March 2004), the exponential rule (Exp-Rule), see S. Shakkottai and A. Stolyar, “Scheduling processes for a mixture of real-time and non-real-time data in HDR”, In Proc. 17th Int. Teletraffic Congress (ITC-17), September 2001, and Applicants proposed approaches rt-MCD and nrt-MCD, see A. Sang, X. Wang, and M. Madihian, entitled “QoS-Aware Channel-Dependent Scheduling over A Third-Generation (3G) Cellular Shared Downlink Channels”, April 2005, Technical Report 2005-L049, NEC Labs America (hereinafter Sang et al.—QoS-Aware Channel Dependent Scheduling . . . ), consider both RT packet delay and multiuser diversity gain. However, they are again TDM-based.
The relative grant RG scheduler in WCDMA or the scheduler in 1xEV-DO.A, see P. Tinnakornsrisuphap and C. Lott, “On the fairness of the reverse-link MAC layer in CDMA2000 1xEV-DO”, In Proc. IEEE Int'l Commun. Conf. (ICC), Paris, France, June 2004, assumes perfect power control with pilot channel for fixed target signal-to-interference plus noise ratio SINR of each mobile user MS, see M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, P. Whiting, and R. Vijayakumar, “Providing quality of service over a shared wireless link”, IEEE Commun. Mag., pages 150-154, February 2001. They impose simultaneous transmission of all backlogged mobile users MSs over their orthogonal CDMA code channels. However, such a scheme, though optimized for low-rate voice services, typically causes serious interference among users.
Accordingly, there is a need for an uplink scheduler that improves on prior work to provide improved access by cellular users in 3G cellular and beyond.