An upper bound on multi-hop multi-channel wireless network performance

ABSTRACT

Given a placement of wireless multi-radio nodes in space and a traffic demand between pairs of nodes, can these traffic demands be supported by the resulting network? The key issue in this setting is the wireless interference between neighbouring nodes using the same channel, including self-interference along multi-hop paths. We extend previous work addressing this problem taking into consideration the availability of multiple channels. As such, this paper presents a generic model for sustainable network load in a multi-hop multichannel setting and recasts this model in a multicommodity flow problem with interference constraints. A theorem is stated which gives a necessary and sufficient condition for the feasibility of this multicommodity flow problem. From this theorem an upper bound is derived for the throughput that can be achieved by the network, which is illustrated by examples. We indicate how the results can be used as a basis for a channel allocating algorithm.

REFERENCES

• 1: Coenen, T. J. M, de Graaf, M. and Boucherie, R. J., An upper bound on multi-hop wireless network performance, Lecture Notes on Computer Science, vol. 4516/2007, p 335--347, 2007.
• 2: Ford, L. R. and Fulkerson, D. R., Maximal flow through a network, Canadian Journal of Mathematics, vol. 8, p 399--404, 1956.
• 3: Ford, L. R. and Fulkerson, D. R., Flows in Networks, Princeton University Press, Princeton, NJ, 1962.
• 4: Gupta, K. and Kumar, P. R., The capacity of wireless networks, IEEE Transactions on Information Theory, 46(2), p 388--404, 2000.
• 5: Gupta, R., Musacchio, J. and Walrand, J., Sufficient rate constraints for QoS flows in ad-hoc networks, UCB/ERL Technical Memorandum M04/42, 2004.
• 6: Haan, R. de, Boucherie, R. J. and Ommeren, J. C. W. van, The impact of interference on optimal multi-path routing in ad hoc networks, Lecture Notes on Computer Science, vol. 4516/2007, p 803--815, 2007.
• 7: 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]
• 8: 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]
• 9: Murali Kodialam , Thyaga Nandagopal, Characterizing the capacity region in multi-radio multi-channel 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.1080837]
• 10: Kyasanur, P. N. and Vaidya, N. H., Multi-channel wireless networks: Capacity and protocols, Technical Report, University of Illinois at Urbana-Champaign, 2005.
• 11: 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]
• 12: Schrijver, A., Combinatorial Optimization: Polyhedra and efficiency, Springer, Berlin, 2003.
• 13: Stemerdink, J., A Simulation Approach to a Robust Multi-radio Multi-channel Wireless Ad Hoc Network, Proceedings of the IST Mobile Summit 2007, Budapest, Hungary, June 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking

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

General Terms:
Design