Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem

ABSTRACT

This paper considers the problem of determining the achievable rates in multi-hop wireless networks. We consider the problem of jointly routing the flows and scheduling transmissions to achieve a given rate vector. We develop tight necessary and sufficient conditions for the achievability of the rate vector. We develop efficient and easy to implement Fully Polynomial Time Approximation Schemes for solving the routing problem. The scheduling problem is a solved as a graph edge-coloring problem. We show that this approach guarantees that the solution obtained is within 67% of the optimal solution in the worst case and, in practice, is typically within about 80% of the optimal solution. The approach that we use is quite flexible and is a promising method to handle more sophisticated interference conditions, multiple channels, multiple antennas, and routing with diversity requirements.

REFERENCES

• 1: Baker, D. J., Wieselthier, J. E., and Ephremides, A., "A Distributed Algorithm for Scheduling the Activation of Links in a Self-Organizing Mobile Radio Networks", IEEE Int. Conference Communications, 1982, pp. 2F6.1--2F6.5.
• 2: Hajek, B., and Sasaki, G., "Link Scheduling in Polynomial Time", IEEE Transactions on Information Theory, 34(5), pp. 910--917, 1988.
• 3: Gupta, P., and Kumar, P. R., "The Capacity of Wireless Networks", IEEE Transactions on Information Theory, 46(2), pp. 388--404, 2000.
• 4: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 5: Grotschel, M., Lovasz, L., and Schrijver, A., "The Ellipsoid Method and its Consequences in Combinatorial Optimization", Combinatorica, 1(2), pp. 169--197, 1981.
• 6: Post, M. J, Kershenbaum, A. S. and Sarachik, P. E., "Scheduling Multi-hop CDMA Networks in the Presence of Secondary Conflicts", Algorithmica, 1989, pp. 365--393.
• 7: Wieselthier, J. E., Barnhart, C. M., and Ephremides, A., "A Neural Network Approach to Routing Without Interference in Multi-hop Networks", IEEE Transactions on Communications, 1994.
• 8: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 9: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 10: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 11: George Karakostas, Faster approximation schemes for fractional multicommodity flow problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.166-173, January 06-08, 2002, San Francisco, California
• 12: Shannon, C. E., "A Theorem on Coloring the Lines of a Network", J. of Math. Physics, 28, pp. 148--151, 1949.
• 13: Takao Nishizeki , Kenichi Kashiwagi, On the 1.1 edge-coloring of multigraphs, SIAM Journal on Discrete Mathematics, v.3 n.3, p.391-410, Aug. 1990 [doi>10.1137/0403035]
• 14: Ramanathan, S., "A Unified Framework and Algorithm for (T/F/C)DMA Channel Assignment in Wireless Networks", IEEE Int. Conference on Communications, 1991, pp. 7d.2.1--7d.2.8
• 15: Kodialam, M., and Nandagopal, T., "The Effect of Interference on the Capacity of Multi-hop Wireless Networks", Bell Labs Technical Report, Lucent Technologies, July 2003.
• 16: Barrett, C., Istrate, G., Anil Kumar, V.S., Marathe, M., and Thite, S., "Approximation Algorithms for Distance-2 Edge Coloring", Unpublished Document, 2002.
• 17: Suurballe, J. W., and Tarjan, R. E., "A Quick Method for Finding Shortest Pairs of Disjoint Paths", Networks, 14, pp. 325--336, 1984.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Theory

Keywords:
graph coloring, optimization, routing, scheduling, wireless networks