Stochastic learning solution for distributed discrete power control game in wireless data networks

ABSTRACT

Distributed power control is an important issue in wireless networks. Recently, noncooperative game theory has been applied to investigate interesting solutions to this problem. The majority of these studies assumes that the transmitter power level can take values in a continuous domain. However, recent trends such as the GSM standard and Qualcomm's proposal to the IS-95 standard use a finite number of discretized power levels. This motivates the need to investigate solutions for distributed discrete power control which is the primary objective of this paper. We first note that, by simply discretizing, the previously proposed continuous power adaptation techniques will not suffice. This is because a simple discretization does not guarantee convergence and uniqueness. We propose two probabilistic power adaptation algorithms and analyze their theoretical properties along with the numerical behavior. The distributed discrete power control problem is formulated as an N-person, nonzero sum game. In this game, each user evaluates a power strategy by computing a utility value. This evaluation is performed using a stochastic iterative procedures. We approximate the discrete power control iterations by an equivalent ordinary differential equation to prove that the proposed stochastic learning power control algorithm converges to a stable Nash equilibrium. Conditions when more than one stable Nash equilibrium or even only mixed equilibrium may exist are also studied. Experimental results are presented for several cases and compared with the continuous power level adaptation solutions.

REFERENCES

• 1: J. M. Aein, "Power balancing in system employing frequency reuse," COMSAT Technical Review, vol. 3, no. 2, pp. 277-300, 1973.
• 2: R. W. Nettleton and H. Alavi, "Power control for a spread spectrum radio system," in Proc. IEEE Vehicular Technology Conf., Toronto, ON, Canada, 1983, pp. 242-246.
• 3: S. A. Grandhi, R. Vijayan, D. J. Goodman, and J. Zander, "Centralized power control in cellular radio systems," IEEE Trans. Veh. Technol., vol. 42, no. 5, pp. 466-468, Nov. 1993.
• 4: J. Zander, "Performance of optimum transmitter power control in cellular radio systems," IEEE Trans. Veh. Technol., vol. 41, no. 1, pp. 57-62, Feb. 1992.
• 5: J. Zander, "Distributed cochannel control in celluar radio systems," IEEE Trans. Veh. Technol., vol. 41, no. 4, pp. 305-311, Aug. 1992.
• 6: S. A. Grandhi, R. Vijayan, and D. J. Goodman, "Distributed power control in cellular radio systems," IEEE Trans. Commun., vol. 42, no. 2, pp. 226-228, Feb. 1994.
• 7: A. Sampath, P. S. Kumar, and J. M. Holtzman, "Power control resource management for a multimedia CDMA wireless system," in Proc. IEEE PIMRC, 1995, pp. 21-25.
• 8: K. Seong-Lyun, Z. Rosberg, and J. Zander, "Combined power control and transmission rate selection in cellular networks," in Proc. IEEE Vehicular Technology Conf., Sep. 1999, pp. 19-22.
• 9: S. Ulukus and R. Yates, "Stochastic power control for cellular radio systems," IEEE Trans. Commun., vol. 46, no. 6, pp. 784-798, Jun. 1998.
• 10: M. K. Varanasi and D. Das, "Fast stochastic power control algorithms for nonlinear multiuser receivers," IEEE Trans. Commun., vol. 50, no. 11, pp. 1817-1827, Nov. 2002.
• 11: A. Yener, R. D. Yates, and S. Ulukus, "Joint power control, multiuser detection and beamforming for CDMA systems," in Proc. IEEE Vehicular Technology Conf., Houston, TX, May 1999, pp. 1032-1036.
• 12: J. Zhang, E. K. P. Chong, and I. Kontoyiannis, "Unified spatial diversity combining and power allocation schemes for CDMA systems in multiple time-scale fading channels," IEEE J. Sel. Areas Commun., vol. 19, no. 7, pp. 1276-1288, Jul. 2001.
• 13: Hongbin Ji , Ching-Yao Huang, Non-cooperative uplink power control in cellular radio systems, Wireless Networks, v.4 n.3, p.233-240, March 1998 [doi>10.1023/A:1019108223561]
• 14: T. Alpcan, T. Basar, R. Srikant, and E. Altman, "CDMA uplink power control as a noncooperative game," in Proc. IEEE Conf. Decision and Control, Dec. 2001, vol. 1, pp. 197-202.
• 15: C. W. Sung and W. S. Wong, "A noncooperative power control game for multirate CDMA data networks," IEEE Trans. Wireless Commun., vol. 2, no. 1, pp. 186-194, Jan. 2003.
• 16: Mingbo Xiao , Ness B. Shroff , Edwin K. P. Chong, A utility-based power-control scheme in wireless cellular systems, IEEE/ACM Transactions on Networking (TON), v.11 n.2, p.210-221, April 2003 [doi>10.1109/TNET.2003.810314]
• 17: D. Famolari, N. B. Mandayam, D. J. Goodman, and V. Shah, "A new framework for power control in wireless data networks: Games, utitlity and pricing," in Proc. 36th Annu. Allerton Conf. Communications, Control, and Computing, Monticello, IL, 1998, pp. 289-310.
• 18: C. U. Saraydar, N. B. Mandayam, and D. J. Goodman, "Efficient power control via pricing in wireless data networks," IEEE Trans. Commun., vol. 50, no. 2, pp. 291-303, Feb. 2002.
• 19: "An overview of the application of code division multiple access (CDMA) to digital cellular systems and personal cellular networks," Qualcomm Inc., Doc. EX60-10010, 1992.
• 20: C. W. Sung, K. K. Leung, and W. S. wong, "A quality-based fixed-step power control algorithm with adaptive target threshold," IEEE Trans. Veh. Technol., vol. 49, no. 7, pp. 1430-1439, Jul. 2000.
• 21: M. Andersin , Z. Rosberg , J. Zander, Distributed Discrete Power Control in Cellular PCS, Wireless Personal Communications: An International Journal, v.6 n.3, p.211-231, March 1998 [doi>10.1023/A:1008888824271]
• 22: Kumpati S. Narendra , Mandayam A. L. Thathachar, Learning automata: an introduction, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 23: R. Chandramouli, "A stochastic technique for on-line prediction and tracking of wireless packet networks," in Proc. 35th Asilomar Conf. Signals, Systems, and Computing, 2001, vol. 1, pp. 672-676.
• 24: S. Kiran and R. Chandramouli, "An adaptive energy efficient link layer protocol using stochastic learning control," in Proc. IEEE Int. Conf. Communications, 2003, pp. 1114-1118.
• 25: D. Fudenberg and J. Tirole, Game Theory. Cambridge, MA: MIT Press, 1992.
• 26: P. S. Sastry, V. V. Phansalkar, and M. A. L. Thathachar, "Decentralized learning of Nash equilibria in multi-person stochastic games with incomplete information," IEEE Trans. Syst., Man, Cybernet., vol. 24, no. 5, pp. 769-777, May 1994.
• 27: Junling Hu , Michael P. Wellman, Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm, Proceedings of the Fifteenth International Conference on Machine Learning, p.242-250, July 24-27, 1998
• 28: K. S. Narendra , A. M. Annaswamy, Stable adaptive systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 29: R. N. Kent and B. S. Edward, Fundamentals of Differential Equations and Boundary Value Problem. Reading, MA: Addison-Wesley, 1996.
• 30: S. Lakshmivarahan and K. S. Narendra, "Learning algorithms for two-person zero-sum stochastic games with incomplete information: A unified approach," SIAM J. Control Optim., vol. 20, no. 4, pp. 541-552, Jul. 1982.
• 31: A. Blaquiere, Non-Linear System Analysis. New York: Academic, 1966.
• 32: K. S. Narendra , A. M. Annaswamy, Stable adaptive systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 33: M. F. Norman, Markov Processes and Learning Models. New York: Academic, 1973.
• 34: M. Haleem and R. Chandramouli, "Adaptive downlink scheduling and rate selection: A cross layer design special issue on mobile computing and networking," IEEE J. Sel. Areas Commun., vol. 23, no. 6, pp. 1287-1297, Jun. 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design, Management, Performance

Keywords:
game theory, power control, stochastic learning, wireless networking