On path selection and rate allocation for video in wireless mesh networks

ABSTRACT

Multi-path transport is an important mechanism for supporting video communications in multihop wireless networks. In this paper, we investigate the joint problem of optimal path se-lection and rate allocation for multiple video sessions in a wire-less mesh network. We present a mathematical formulation to op-timize the application level performance (i.e., video distortion) in the context of path selection and rate allocation. For this complex optimization problem, we propose a branch-and-bound based so-lution procedure, embedded with the Reformulation-Linearization Technique (RLT) that can produce (1 - Ε)-optimal solutions for any small Ε. This result is significant as it not only provides the-oretical understanding of this problem, but also offers a perfor-mance benchmark for any future proposed distributed algorithm and protocol for this problem. Simulation results are also provided to demonstrate the efficacy of the solution procedure.

REFERENCES

• 1: J. G. Apostolopoulos, T. Wong, W. Tan, and S. Wee, "On multiple de-scription streaming in content delivery networks," in Proc. IEEE IN-FOCOM, New York, Jun. 2002, pp. 1736-1745.
• 2: Handbook of Evolutionary Computation, T. Back, D. Fogel, and Z. Michalewicz, Eds. New York: Oxford Univ. Press, 1997.
• 3: A. C. Begen , Y. Altunbasak , O. Ergun, Fast heuristics for multi-path selection for multiple description encoded video streaming, Proceedings of the 2003 International Conference on Multimedia and Expo, p.517-520, July 06-09, 2003
• 4: A. C. Begen, Y. Altunbasak, and O. Ergun, "Multi-path selection for multiple description encoded video streaming," EURASIP Signal Process.: Image Commun., vol. 20, no. 1, pp. 39-60, Jan. 2005.
• 5: H. Chernoff, "A measure of asymptotic efficiency for tests of a hypoth-esis based on the sum of observations," Ann. Math. Statist., vol. 23, pp. 493-507, 1952.
• 6: Zhenhai Duan , Zhi-Li Zhang , Yiwei Thomas Hou , Lixin Gao, A Core Stateless Bandwidth Broker Architecture for Scalable Support of Guaranteed Services, IEEE Transactions on Parallel and Distributed Systems, v.15 n.2, p.167-182, February 2004 [doi>10.1109/TPDS.2004.1264799]
• 7: A. Elwalid, D. Heyman, T. V. Lakshman, D. Mitra, and A. Weiss, "Fun-damental bounds and approximations for ATM multiplexers with appli-cations to video teleconferencing," IEEE J. Sel. Areas Commun., vol. 13, no. 6, pp. 953-962, Aug. 1995.
• 8: David Eppstein, Finding the k Shortest Paths, SIAM Journal on Computing, v.28 n.2, p.652-673, April 1999 [doi>10.1137/S0097539795290477]
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: T. Kuang and C. Williamson, "A measurement study of Real Media audio/video streaming traffic," in Proc. SPIE ITCOM 2002, Boston, MA, Jul. 2002, pp. 68-79.
• 11: S. Mao, Y. T. Hou, X. Cheng, H. D. Sherali, and S. F. Midkiff, "Multi-path routing for multiple description video over wireless ad hoc networks," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 740-750.
• 12: S. Mao, S. Kompella, Y. T. Hou, H. D. Sherali, and S. F. Midkiff, "Routing for multiple concurrent video sessions in wireless ad hoc net-works," in Proc. IEEE ICC, Seoul, Korea, May 2005, pp. 1229-1235.
• 13: S. Murthy and J. J. Garcia-Luna-Aceves, "Congestion-oriented shortest multi-path routing," in Proc. IEEE INFOCOM, San Francisco, CA, May 1996, pp. 1038-1036.
• 14: I. Norros, "On the use of fractional Brownian motion in the theory of connectionless networks," IEEE J. Sel. Areas Commun., vol. 13, no. 6, pp. 953-962, Aug. 1995.
• 15: Panagiotis Papadimitratos , Zygmunt J. Haas , Emin Gün Sirer, Path set selection in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513802]
• 16: E. Setton, X. Zhu, and B. Girod, "Congestion-optimized multi-path streaming of video over ad hoc wireless networks," in Proc. IEEE ICME, Taipei, Taiwan, Jun. 2004, pp. 1619-1622.
• 17: H. D. Sherali and C. H. Tuncbilek, "A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique," J. Global Optim., vol. 2, no. 1, pp. 101-112, 1992.
• 18: H. D. Sherali and W. P. Adams, A Reformulation-Linearization Tech-nique for Solving Discrete and Continuous Nonconvex Problems. Boston, MA: Kluwer Academic, 1999.
• 19: K. Stuhlmuller, N. Farberand, M. Link, and B. Girod, "Analysis of video transmission over lossy channels," IEEE J. Sel. Areas Commun., vol. 18, no. 6, pp. 1012-1032, Jun. 2000.
• 20: W. Wei and A. Zakhor, "Path selection for multi-path streaming in wireless ad hoc networks," in Proc. IEEE ICIP, Atlanta, GA, Oct. 2006, pp. 3045-3048.
• 21: Z.-L. Zhang, Z. Duan, and Y. T. Hou, "On scalable design of bandwidth brokers," IEICE Trans. Commun., vol. E84-B, no. 8, pp. 2011-2025, Aug. 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

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

  E. Data
  E.4 CODING AND INFORMATION THEORY

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
cross-layer design, optimization, path selection, rate allocation, video communications, wireless mesh network