Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks

ABSTRACT

Wireless mesh networks are expected to be widely used to provide Internet access in the near future. In order to fulfill the expectations, these networks should provide high throughput simultaneously to many users. Recent research has indicated that, due to its conservative CSMA/CA channel access scheme and RTS/CTS mechanism, 802.11 is not suitable to achieve this goal.In this paper, we investigate throughput improvements achievable by replacing CSMA/CA with an STDMA scheme where transmissions are scheduled according to the physical interference model. To this end, we present a computationally efficient heuristic for computing a feasible schedule under the physical interference model and we prove, under uniform random node distribution, an approximation factor for the length of this schedule relative to the shortest schedule possible with physical interference. This represents the first known polynomial-time algorithm for this problem with a proven approximation factor.We also evaluate the throughput and execution time of this algorithm on representative wireless mesh network scenarios through packet-level simulations. The results show that throughput with STDMA and physical-interference-based scheduling can be up to three times higher than 802.11 for the parameter values simulated. The results also show that our scheduling algorithm can schedule networks with 2000 nodes in about 2.5 minutes.

REFERENCES

• 1: 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]
• 2: Azulstar Website: http://www.azulstar.com/coverage-map.html.
• 3: N. Ben Salem, J. P. Hubaux, "A Fair Scheduling for Wireless Mesh Networks", Proc. IEEE Workshop on Wireless Mesh Networks (WiMesh), 2005.
• 4: John Bicket , Daniel Aguayo , Sanjit Biswas , Robert Morris, Architecture and evaluation of an unplanned 802.11b mesh network, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080833]
• 5: Jimmi Grönkvist , Anders Hansson, Comparison between graph-based and interference-based STDMA scheduling, 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.501453]
• 6: J. Gronkvist, J. Nilsson, and D. Yuan, "Throughput of Optimal Spatial Reuse TDMA for Wireless Ad-Hoc Networks," Proc. IEEE Vehicular Technology Conference, pp. 2156--2160, 2004.
• 7: J. Gronkvist, "Traffic Controlled Spatial Reuse TDMA in Multi-hop Radio Networks," Proc. Int'l. Symp. on Personal, Indoor, and Mobile Radio Communications, pp. 1203--1207, 1998.
• 8: P. Gupta and P.R. Kumar, "The Capacity of Wireless Networks," IEEE Trans. Info. Theory, Vol. 46, No. 2, pp. 388--404, 2000.
• 9: P. Gupta, P. R. Kumar, "Critical Power for Asymptotic Connectivity in Wireless Networks", Stochastic Analysis, Control, Optimization and Applications, Birkhauser, Boston, pp. 547--566, 1998.
• 10: Ivaylo Haratcherev , Jacco Taal , Koen Langendoen , Reginald Lagendijk , Henk Sips, Automatic IEEE 802.11 rate control for streaming applications: Research Articles, Wireless Communications & Mobile Computing, v.5 n.4, p.421-437, June 2005 [doi>10.1002/wcm.v5:4]
• 11: Houston Wireless Website: http://www.houstonwireless.org/.
• 12: 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]
• 13: 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]
• 14: V. F. Kolchin, B. A. Sevast'yanov, V. P. Chistyakov, Random Allocations, V. H. Winston and Sons, Washington D.C., 1978.
• 15: 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]
• 16: P. Kyasanur, X. Yang, N. Vaidya, "Mesh Networking Protocols to Exploit Physical Layer Capabilities", Proc. IEEE Workshop on Wireless Mesh Networks (WiMesh), 2005.
• 17: P. Kyasanur, N. Vaidya, "Routing and Interface Assignment in Multi-Channel Multi-Interface Wireless Networks", Proc. IEEE WCNC, 2005.
• 18: T. Moscibroda, R. Wattenhofer, "The Complexity of Connectivity in Wireless Networks", Proc. IEEE Infocom 2006, to appear.
• 19: R. Nelson and L. Kleinrock, "Spatial-TDMA: A Collison-free Multihop Channel Access Protocol," IEEE Trans. on Communication, Vol. 33, pp. 934--944, Sept. 1985.
• 20: D. Qiao, S. Choi, "Goodput enhancement of IEEE 802.11a wireless LAN via link adaptation", Proc. IEEE ICC, pp. 1995--2000, 2001.
• 21: B. Raman, "Channel Allocation in 802.11-based Mesh Networks," Proc. IEEE Infocom 2006, to appear.
• 22: Bhaskaran Raman , Kameswari Chebrolu, Design and evaluation of a new MAC protocol for long-distance 802.11 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.1080847]
• 23: A. Raniwala, T. Chiueh, "Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Networks", Proc. IEEE Infocom, pp. 2223--2234, 2005.
• 24: George F. Riley, The Georgia Tech Network Simulator, Proceedings of the ACM SIGCOMM workshop on Models, methods and tools for reproducible network research, August 25-27, 2003, Karlsruhe, Germany [doi>10.1145/944773.944775]
• 25: Paolo Santi , Douglas M. Blough, The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.1, p.25-39, January 2003 [doi>10.1109/TMC.2003.1195149]
• 26: P. Santi, Topology Control in Wireless Ad Hoc and Sensor Networks, John Wiley & Sons, Chichester, UK, 2005.
• 27: Seattle Wireless Website: http://www.seattlewireless.net/.
• 28: O. Somarriba, Multihop Packet Radio Systems in Rough Terrain, Tech.lic. Thesis, Radio Communication Systems, Royal Institute of Technology, Stockholm, Sweden, Oct. 1995.
• 29: Jian Tang , Guoliang Xue , Weiyi Zhang, Interference-aware topology control and QoS routing in multi-channel wireless mesh networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062700]
• 30: Wireless Communities Website: http://wiki.personaltelco.net/index.cgi/WirelessCommunities.
• 31: Z. Wu and D. Raychaudhuri, "D-LSMA: Distributed Link Scheduling Multiple Access Protocol for QoS in Ad-hoc Networks," Proc. Globecom 2004, pp. 1670--1675.
• 32: Y. Yuan, H. Yang, S. Wong, S. Lu, W. Arbaugh, "ROMER: Resilient Opportunistic Mesh Routing for Wireless Mesh Networks", Proc. IEEE Workshop on Wireless Mesh Networks (WiMesh), 2005.

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
STDMA scheduling, network capacity, physical interference model, wireless mesh networks