Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We seek distributed protocols that attain the global optimum allocation of link transmitter powers and source rates in a cross-layer design of a mobile ad hoc network. Although the underlying network utility maximization is nonconvex, convexity plays a major role in our development. We provide new convexity results surrounding the Shannon capacity formula, allowing us to abandon suboptimal high-SIR approximations that have almost become entrenched in the literature. More broadly, these new results can be back-substituted into many existing problems for similar benefit.

Three protocols are developed. The first is based on a convexification of the underlying problem, relying heavily on our new convexity results. We provide conditions under which it produces a globally optimum resource allocation. We show how it may be distributed through message passing for both rate- and power-allocation. Our second protocol relaxes this requirement and involves a novel sequence of convex approximations, each exploiting existing TCP protocols for source rate allocation. Message passing is only used for power control. Our convexity results again provide sufficient conditions for global optimality. Our last protocol, motivated by a desire of power control devoid of message passing, is a near optimal scheme that makes use of noise measurements and enjoys a convergence rate that is orders of magnitude faster than existing methods.

REFERENCES

• 1: M. Avriel and A. C. Williams, "Complementary geometric programming," SIAM J. Appl. Math., vol. 19, no. 1, pp. 125-141, Jul. 1970.
• 2: M. Avriel, W. E. Diewert, S. Schaible, and I. Zang, Generalized Concavity . New York, London: Plenum Press, 1988.
• 3: A. Ben-Tal, "On generalized means and generalized convex functions," J. Opt. Theory Appl., vol. 21, no. 1, pp. 1-13, Jan 1977.
• 4: D. P. Bertsekas, Nonlinear Programming. Belmont, MA: Athena Scientific, 1995.
• 5: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 6: Thomas Bonald , Laurent Massoulié, Impact of fairness on Internet performance, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.82-91, June 2001, Cambridge, Massachusetts, United States
• 7: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 8: S. Chen, M. A. Beach, and J. P. McGeehan, "Division-free duplex for wireless applications," Electron. Lett., vol. 34, no. 2, pp. 147-148, Jan 1998.
• 9: M. Chiang and J. Bell, "Balancing supply and demand of bandwidth in wireless cellular networks: Utility maximization over powers and rates," in Proc. IEEE INFOCOM, 2004, vol. 4, pp. 2800-2811.
• 10: M. Chiang, "Balancing transport and physical layers in wireless multihop networks: Jointly optimal congestion control and power control," IEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 104-116, 2005.
• 11: Andrea Goldsmith, Wireless Communications, Cambridge University Press, New York, NY, 2005
• 12: R. Horst and H. Tuy, Global Optimization: Deterministic Approaches, 2nd ed. New York: Springer-Verlag, 1993.
• 13: M. Johansson, L. Xiao, and S. Boyd, "Simultaneous routing and power allocation in CDMA wireless data networks," in IEEE Int. Conf. Communications , May 2003.
• 14: D. Julian, M. Chiang, D. O'Neill, and S. Boyd, "QoS and fairness constrained convex optimization of resource allocation for wireless cellular and ad hoc networks," in Proc. IEEE INFOCOM, June 2002, vol. 2, pp. 477-486.
• 15: S. Kandukuri and S. Boyd, "Optimal power control in interference-limited fading wireless channels with outage-probability specifications," IEEE Trans. Wireless Commun., vol. 1, no. 1, pp. 46-55, 2002.
• 16: F. P. Kelly, "Charging and rate control for elastic traffic," Euro. Trans. Telecom., vol. 8, pp. 33-37, Jan 1997.
• 17: U. C. Kozat, I. Koutsopoulos, and L. Tassiulas, "A framework for cross-layer design of energy-efficient communication with QoS provisioning in multi-hop wireless networks," in Proc. IEEE INFOCOM, Mar. 2004, vol. 2, pp. 1446-1456.
• 18: Steven H. Low, A duality model of TCP and queue management algorithms, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.525-536, August 2003 [doi>10.1109/TNET.2003.815297]
• 19: Steven H. Low , David E. Lapsley, Optimization flow control—I: basic algorithm and convergence, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.861-874, Dec. 1999 [doi>10.1109/90.811451]
• 20: Steven H. Low , Larry L. Peterson , Limin Wang, Understanding TCP Vegas: a duality model, Journal of the ACM (JACM), v.49 n.2, p.207-235, March 2002 [doi>10.1145/506147.506152]
• 21: R. Madan, S. Cui, S. Lall, and A. Goldsmith, "Cross-layer design for lifetime maximization in interference-limited wireless sensor networks," in Proc. IEEE INFOCOM, Mar. 2005.
• 22: B. R. Marks and G. P. Wright, "A general inner approximation method for nonconvex mathematical programs," Oper. Res., vol. 26, no. 4, pp. 681-683, 1978.
• 23: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]
• 24: K.-H. Pan, H.-K. Wu, R.-J. Shang, F. Lai, and Y.-W. Lin, "Communications over two-way waveform channels in wireless networks," in Proc. 1999 IEEE Canadian Conf. Electrical and Computer Engineering , Edmonton, Canada, May 1999, pp. 45-50.
• 25: J. Papandriopoulos, J. S. Evans, and S. Dey, "Optimal power control for Rayleigh-faded multiuser systems with outage constraints," IEEE Trans. Wireless Commun., vol. 4, pp. 2705-2715, Nov. 2005.
• 26: J. Papandriopoulos, "Resource optimization in multiuser communication networks," Ph.D. dissertation, University of Melbourne, Melbourne, Australia, 2006.
• 27: X. Qiu and K. Chawla, "On the performance of adaptive modulation in cellular systems," IEEE Trans. Commun., vol. 47, no. 6, pp. 884-895, Jun. 1999.
• 28: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 29: J. B. Rosen, "Iterative solution of nonlinear optimal control problems," SIAM J. Control, vol. 4, pp. 223-244, 1966.
• 30: K. Tsubouchi, H. Nakase, A. Namba, and K. Masu, "Full duplex transmission operation of a 2.45-GHz asynchronous spread spectrum using a SAN convolver," IEEE Trans. Ultrason, Ferroelectr. Freq. Contr., vol. 40, no. 5, pp. 478-482, Sep. 1993.
• 31: Jiantao Wang , Lun Li , Steven H. Low , John C. Doyle, Cross-layer optimization in TCP/IP networks, IEEE/ACM Transactions on Networking (TON), v.13 n.3, p.582-595, June 2005 [doi>10.1109/TNET.2005.850219]
• 32: R. D. Yates, "A framework for uplink power control in cellular radio systems," IEEE J. Sel. Areas Commun., vol. 13, no. 7, pp. 1341-1347, 1995.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  E. Data
  E.4 CODING AND INFORMATION THEORY

General Terms:
Algorithms, Design, Management, Performance, Theory

Keywords:
Rayleigh fading, congestion control, cross-layer optimization, mobile ad hoc network, network utility maximization, outage probability, power control