Murali Kodialam
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.
- 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.Google Scholar
- Hajek, B., and Sasaki, G., "Link Scheduling in Polynomial Time", IEEE Transactions on Information Theory, 34(5), pp. 910--917, 1988.Google ScholarDigital Library
- Gupta, P., and Kumar, P. R., "The Capacity of Wireless Networks", IEEE Transactions on Information Theory, 46(2), pp. 388--404, 2000. Google ScholarDigital Library
- Ahuja, R.K., Magnanti, T. L., Orlin, J.B., "Network Flows: Theory, Algorithms, and Applications", Prentice Hall, 1993. Google ScholarDigital Library
- Grotschel, M., Lovasz, L., and Schrijver, A., "The Ellipsoid Method and its Consequences in Combinatorial Optimization", Combinatorica, 1(2), pp. 169--197, 1981.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Jain, K., Padhye, J., Padmanabhan, V., and Qiu, L., "Impact on Interference on Multi-hop Wireless Network Performance", ACM Mobicom'03, September 2003. Google ScholarDigital Library
- Shahrokhi, F., and Matula, D., "The Maximum Concurrent Flow Problem", Journal of the ACM, 37, pp. 318--334, 1990. Google ScholarDigital Library
- Garg, N., and Könemann, J., "Faster and Simpler Algorithms for Multi-commodity Flow and other Fractional Packing Problems", Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp.300--309, 1998. Google ScholarDigital Library
- Karakostas, G., "Faster Approximation Schemes for Fractional Multi-commodity Flow Problems", 13th ACM/SIAM Symposium on Discrete Algorithms, pp. 166--173, 2002. Google ScholarDigital Library
- Shannon, C. E., "A Theorem on Coloring the Lines of a Network", J. of Math. Physics, 28, pp. 148--151, 1949.Google ScholarCross Ref
- Nishizeki, T., and Kashiwagi, K., "On the 1.1 Edge-Coloring of Multi-graphs", SIAM Journal of Discrete Math., 3(3), pp. 391--410, 1990. Google ScholarDigital Library
- 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.8Google Scholar
- 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.Google Scholar
- Barrett, C., Istrate, G., Anil Kumar, V.S., Marathe, M., and Thite, S., "Approximation Algorithms for Distance-2 Edge Coloring", Unpublished Document, 2002.Google Scholar
- Suurballe, J. W., and Tarjan, R. E., "A Quick Method for Finding Shortest Pairs of Disjoint Paths", Networks, 14, pp. 325--336, 1984.Google ScholarCross Ref
Index Terms
- Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem
Recommendations
Routing in multi-radio, multi-hop wireless mesh networks
MobiCom '04: Proceedings of the 10th annual international conference on Mobile computing and networkingWe present a new metric for routing in multi-radio, multi-hop wireless networks. We focus on wireless networks with stationary nodes, such as community wireless networks.The goal of the metric is to choose a high-throughput path between a source and a ...
Characterizing the capacity region in multi-radio multi-channel wireless mesh networks
MobiCom '05: Proceedings of the 11th annual international conference on Mobile computing and networkingNext generation fixed wireless broadband networks are being increasingly deployed as mesh networks in order to provide and extend access to the internet. These networks are characterized by the use of multiple orthogonal channels and nodes with the ...
Opportunistic routing in multi-radio multi-channel multi-hop wireless networks
Two major factors that limit the throughput in multi-hop wireless networks are the co-channel interference and unreliability of wireless transmissions. Multi-radio multichannel technology and opportunistic routing (OR) have shown their promise to ...
Comments