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

ABSTRACT

Next 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 ability to simultaneously communicate with many neighbors using multiple radios (interfaces) over orthogonal channels. Networks based on the IEEE 802.11a/b/g and 802.16 standards are examples of these systems. However, due to the limited number of available orthogonal channels, interference is still a factor in such networks. In this paper, we propose a network model that captures the key practical aspects of such systems and characterize the constraints binding their behavior. We provide necessary conditions to verify the feasibility of rate vectors in these networks, and use them to derive upper bounds on the capacity in terms of achievable throughput, using a fast primal-dual algorithm. We then develop two link channel assignment schemes, one static and the other dynamic, in order to derive lower bounds on the achievable throughput. We demonstrate through simulations that the dynamic link channel assignment scheme performs close to optimal on the average, while the static link channel assignment algorithm also performs very well. The methods proposed in this paper can be a valuable tool for network designers in planning network deployment and for optimizing different performance objectives.

REFERENCES

• 1: IEEE Std. 802.11-1999, "Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications", 1999.
• 2: IEEE Std. 802.16-2004, "Part 16: Air Interface for Fixed Broadband Wireless Access Systems", July 2004.
• 3: Microsoft Research, "Mesh Networking", http://research.microsoft.com/mesh/.
• 4: Mesh Dynamics Inc., http://www.meshdynamics.com.
• 5: Gupta, P., and Kumar, P.R., "The Capacity of Wireless Networks", IEEE Transactions on Information Theory, 46(2), pp. 388--404, 2000.
• 6: Qiu, L., Chandra, R., Jain, K., and Mahdian, M., "Optimizing the Placement of Integration Points in Multi-hop Wireless Networks", IEEE ICNP, 2004.
• 7: A. Raniwala and T. Chiueh, "Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network", IEEE Infocom, March 2005.
• 8: Ashish Raniwala , Kartik Gopalan , Tzi-cker Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.2, April 2004 [doi>10.1145/997122.997130]
• 9: P. Kyasanur and N. Vaidya, "Routing and Interface Assignment in Multi-Channel Multi-Interface Wireless Networks", IEEE WCNC, 2005.
• 10: P. Kyasanur and N. Vaidya, "Routing in Multi-Channel Multi-Interface Ad Hoc Wireless Networks", Technical Report, December 2004.
• 11: Jungmin So , Nitin H. Vaidya, Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989487]
• 12: Tzamaloukas, A., and Garcia-Luna-Aceves, J.J., "A receiver initiated collision-avoidance protocol for multi-channel networks", In IEEE Infocom, 2001.
• 13: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 14: Richard Draves , Jitendra Padhye , Brian Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023732]
• 15: Paramvir Bahl , Ranveer Chandra , John Dunagan, SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023742]
• 16: Atul Adya , Paramvir Bahl , Jitendra Padhye , Alec Wolman , Lidong Zhou, A Multi-Radio Unification Protocol for IEEE 802.11 Wireless Networks, Proceedings of the First International Conference on Broadband Networks (BROADNETS'04), p.344-354, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.8]
• 17: 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]
• 18: Kodialam, M., and Nandagopal, T., "The Effect of Interference on the Capacity of Multi-hop Wireless Networks", IEEE Symposium on Information Theory, June 2004.
• 19: Murali Kodialam , Thyaga Nandagopal, Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938991]
• 20: Murali Kodialam , Thyaga Nandagopal, Characterizing achievable rates in multi-hop wireless mesh networks with orthogonal channels, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.868-880, August 2005 [doi>10.1109/TNET.2005.852873]
• 21: Sven O. Krumke , Madhav V. Marathe , S. S. Ravi, Models and approximation algorithms for channel assignment in radio networks, Wireless Networks, v.7 n.6, p.575-584, November 2001 [doi>10.1023/A:1012311216333]
• 22: V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, End-to-end packet-scheduling in wireless ad-hoc networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 23: Gastpar, M., and Vetterli, M., "On the Capacity of Wireless Networks: The Relay Case", IEEE Infocom, pp. 1577--1586, 2002.
• 24: Frederico Calì , Marco Conti , Enrico Gregori, Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit, IEEE/ACM Transactions on Networking (TON), v.8 n.6, p.785-799, Dec. 2000 [doi>10.1109/90.893874]
• 25: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 26: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 27: Eszter Kail , Gábor Németh , Zoltán Richárd Turányi, Throughput of ideally routed wireless ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501449.501457]
• 28: Chandra, R., Bahl, V., and Bahl, P., "MultiNet: Connecting to multiple IEEE 802.11 networks using a single wireless card", IEEE Infocom, 2004.
• 29: Choudhury, R., and Vaidya, N., "Impact of Directional Antennas on Ad Hoc Routing", In IEEE Personal Wireless Communication Conference, Sept. 2003.
• 30: Hung-Yun Hsieh , Kyu-Han Kim , Yujie Zhu , Raghupathy Sivakumar, A receiver-centric transport protocol for mobile hosts with heterogeneous wireless interfaces, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938987]
• 31: 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
• 32: S. Borbash and A. Ephremides, "Wireless Link Scheduling with Power Control", IEEE WiOpt '04, March 2004.
• 33: Mansoor Alicherry , Randeep Bhatia , Li (Erran) Li, Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080836]
• 34: Pradeep Kyasanur , Nitin H. Vaidya, Capacity of multi-channel wireless networks: impact of number of channels and interfaces, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080835]

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Design, Theory

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