Managing resources and quality of service in heterogeneous wireless systems exploiting opportunism

ABSTRACT

We propose a novel class of opportunistic scheduling disciplines to handle mixes of real-time and best-effort traffic at a wireless access point. The objective is to support probabilistic service rate guarantees to real-time sessions while still achieving opportunistic throughput gains across users and traffic types. We are able to show a "tight" stochastic lower bound on the service a real-time session would receive assuming that the users possibly heterogenous capacity variations are known or estimated, and are fast fading across slots. Such bounds are critical to enabling predictable quality of service and thus the development of complementary resource management and admission control strategies. Idealized simulation results show that the scheme can achieve 80%-90% of the maximum system throughput capacity while satisfying the quality of service (QoS) requirements for real-time traffic, and that the degradation in system throughput is slow in the number of real-time users, i.e., inter- and intra-class opportunism are being properly exploited. We note however, that there is a tradeoff between strictness of QoS requirements and the overall system throughput one can achieve. Thus if QoS requirements on real-time traffic are very tight, one would need to simply give priority to real-time traffic, and in the process lose the throughput gains of opportunism.

REFERENCES

• 1: [1] R. Knopp and P. Humblet, "Information capacity and power control in single cell multi-user communications," in Proc. IEEE Int. Computer Conf., Jun. 1995, vol. 1, pp. 331-335.
• 2: [2] A. Jalali, R. Padovani, and R. Pankaj, "Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system," in Proc. Vehicular Technology Conf. 2000 (VTC 2000-Spring), Tokyo, Japan, May 2000, vol. 3, pp. 1854-1858.
• 3: [3] P. Viswanath, D. Tse, and R. Laroia, "Opportunistic beamforming using dumb antennas," IEEE Trans. Inf. Theory, vol. 48, pp. 1277-1294, Jun. 2002.
• 4: [4] E. W. Knightly and N. B. Shroff, "Admission control for statistical QoS: Theory and practice," IEEE Network, vol. 13, pp. 20-29, Mar. 1999.
• 5: [5] M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijaykumar, and P. Whiting, "CDMA data QoS scheduling on the forward link with variable channel conditions," Bell Labs. Tech. Rep., Apr. 2000.
• 6: [6] S. Shakkottai and A. Stolyar, "Scheduling for multiple flows sharing a time-varying channel: The exponential rule," American Mathematical Society Translations, Series 2, A Volume in Memory of F. Karpelevich, vol. 207, 2002, Y. M. Suhov, Ed.
• 7: [7] S. Shakkottai and A. Stolyar, "Scheduling algorithms for a mixture of real-time and non-real-time data in HDR," in Proc. 17th Int Teletraffic Congr (ITC-17), Salvador da Bahia, Brazil, Sep. 2001.
• 8: [8] D. Wu and R. Negi, "Downlink scheduling in a cellular network for quality-of-service assurance," IEEE Trans. Veh. Technol., vol. 53, pp. 1547-1557, Sep. 2004.
• 9: [9] S. Patil and G. de Veciana, "Measurement-based opportunistic scheduling for heterogeneous wireless systems," Dept. ECE, Univ. Texas, Austin, to be submitted for journal publication. [Online]. Available: http://www.ece.utexas.edu/gustavo/papers/PaD06a.pdf
• 10: Zhengrong Ji , Yi Yang , Junlan Zhou , Mineo Takai , Rajive Bagrodia, Exploiting medium access diversity in rate adaptive wireless LANs, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023754]
• 11: [11] P. Bender, P. Black, M. Grob, R. Padovani, N. Sindhushayana, and A. Viterbi, "CDMA/HDR: a bandwidth efficient high speed wireless data service for nomadic users," IEEE Commun. Mag., vol. 38, no. 7, pp. 70-77, Jul. 2000.
• 12: [12] T. Bonald, "A score-based opportunistic scheduler for fading radio channels," in Proc. European Wireless 2004, Barcelona, Feb. 2004.
• 13: [13] S. Patil, "Opportunistic scheduling and resource allocation among heterogeneous users in wireless networks" Ph.D. dissertation, Univ. Texas, Austin, May 2006 [Online]. Available: http://www.ece.utexas. edu/~gustavo/papers/phd/Shailesh.Patil2006.pdf
• 14: [14] D. Park, H. Seo, H. Kwon, and B. G. Lee, "A new wireless packet scheduling algorithm based on the CDF of user transmission rates," in Proc. IEEE Globecom, Nov. 2003, pp. 528-532.
• 15: [15] X. Qin and R. Berry, "Opportunistic splitting algorithms for wireless networks with heterogeneous users," in Proc. Conf. Information Sciences and Systems (CISS), Mar. 2004.
• 16: [16] G. C. Fox, R. D. Williams, and P. C. Messina, Parallel Computing Works. San Mateo, CA: Morgan Kaufmann, 1994.
• 17: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 18: [18] D. Wu, "Providing quality-of-service guarantees in wireless networks," Ph.D. dissertation, Carnegie Mellon Univ., Pittsburgh, PA, Aug. 2003.
• 19: [19] M. Andrews, L. Qian, and A. L. Stolyar, "Optimal utility based multi-user throughput allocation subject to throughput constraints," in Proc. IEEE INFOCOM 2005, Mar. 2005, pp. 2415-2424.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management
          Subjects: Quality assurance

General Terms:
Design, Management, Performance

Keywords:
multi-user diversity, quality of service, scheduling