A coordinate-based approach for exploiting temporal-spatial diversity in wireless mesh networks

ABSTRACT

In this paper, we consider the problem of mitigating interference and improving network capacity in wireless mesh networks from the angle of temporal-spatial diversity. In a nutshell, while the achievable throughput on a multihop wireless path is limited by intra-flow interference, the overall capacity of a multihop wireless network can be increased by exploiting temporal-spatial diversity of concurrent transmissions that exist among a number of wireless links. Connections that are routed along multihop wireless paths can be scheduled to take place simultaneously if their transmissions do not interfere with each other (significantly).To make a case of exploiting the temporal-spatial diversity to improve network capacity, we focus on transporting downstream traffic at gateway nodes with Internet access. We propose to construct, based on measurements of received signal strengths, a virtual coordinate system that is used to determine the sets of paths along which transmissions can take place with the least inter-flow interference. Based on the sets of non-interfering paths, the gateway node then determines the order with which a gateway node schedules frames of different connections to be transmitted. Through extensive simulation (with real-life measurement traces on an operational, city-wide wireless community network), we show that the downstream throughput of a gateway node in a wireless mesh network can be improved by 10-35% under a variety of network topologies and traffic distributions. This, coupled with the fact that the proposed approach requires only minor code change in the gateway nodes and does not require any additional hardware, makes it a viable option to improving network capacity in existing wireless mesh networks.

REFERENCES

• 1: Bay area wireless user group. http://www.bawug.org/.
• 2: Champaign-Urbana community wireless network. http://www.cuwireless.net/.
• 3: MIT roofnet. http://pdos.csail.mit.edu/roofnet/doku.php.
• 4: Seattle wireless. http://www.seattlewireless.net/.
• 5: SFLan. http://www.sflan.org/.
• 6: Southampton open wireless network. http://www.sown.org.uk/.
• 7: 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]
• 8: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 9: D. Allen. Hidden terminal problems in wireless LAN's. 802.11 Working Group paper 802.11/93-xx.
• 10: D. Berger, Z. Ye, P. Sinha, S. Krishnamurthy, M. Faloutsos, and S. K. Tripathi. TCP-friendly medium access control for ad-hoc wireless networks: alleviating self-contention. In Proc. of IEEE MASS, October 2004.
• 11: 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]
• 12: 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]
• 13: Richard Draves , Jitendra Padhye , Brian Zill, Comparison of routing metrics for static multi-hop wireless networks, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 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: Zhenghua Fu , Haiyun Luo , Petros Zerfos , Songwu Lu , Lixia Zhang , Mario Gerla, The Impact of Multihop Wireless Channel on TCP Performance, IEEE Transactions on Mobile Computing, v.4 n.2, p.209-221, March 2005 [doi>10.1109/TMC.2005.30]
• 16: IEEE. Wireless LAN Media Access Control (MAC) and Physical Layer (PHY) Specification. IEEE Standard 802.11, 1999.
• 17: IEEE Computer Society. Part 11: Wireless LAN Medium Access (MAC) and Physical Layer (PHY) Specifications, Amendment 8: Medium Access Cntorl (MAC) Quality of Service Enhancement. IEEE Standard 802.11e, 2005.
• 18: Tae-Suk Kim , Jennifer C. Hou , Hyuk Lim, Improving spatial reuse through tuning transmit power, carrier sense threshold, and data rate in multihop wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161131]
• 19: Koen Langendoen , Niels Reijers, Distributed localization in wireless sensor networks: a quantitative comparison, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.4, p.499-518, 15 November 2003 [doi>10.1016/S1389-1286(03)00356-6]
• 20: Hyuk Lim , Jennifer C. Hou , Chong-Ho Choi, Constructing internet coordinate system based on delay measurement, IEEE/ACM Transactions on Networking (TON), v.13 n.3, p.513-525, June 2005 [doi>10.1109/TNET.2005.850197]
• 21: Richard T. B. Ma , Sam C. M. Lee , John C. S. Lui , David K. Y. Yau, A game theoretic approach to provide incentive and service differentiation in P2P networks, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 22: Microsoft Networking Research Group. Self-organizing neighborhood wireless mesh networks. http://research.microsoft.com/mesh/.
• 23: J. Monks, V. Bharghavan, and W. -M. Hwu. A power controlled multiple access protocol for wireless packet networks. In Proc. of IEEE INFOCOM, 2001.
• 24: A. Muqattash and M. Krunz. Power controlled dual channel (PCDC) medium access protocol for wireless ad hoc networks. In Proc. of IEEE INFOCOM, 2003.
• 25: Alaa Muqattash , Marwan Krunz, A single-channel solution for transmission power control in wireless ad hoc networks, 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.989486]
• 26: T. Nadeem, L. Ji, A. Agrawala, and J. Agre. Location enhancement to IEEE 802.11 DCF. In Proc. of IEEE INFOCOM, March 2005.
• 27: B. Noble and J. W. Daniel. Applied Linear Algebra. Prentice Hall, 1988.
• 28: Nortel Networks. The business case for wireless mesh networks. http://www.nortelnetworks.com/corporate/events/2003d/wmn eseminar/collateral/wmn eseminar.pdf, December 2003.
• 29: J. Padhye, S. Agarwal, V. N. Padmanabhan, L. Qiu, A. Rao, and B. Zill. Estimation of link interference in static multi-hop wireless networks. In Proc. of Internet Measurement Conference, 2005.
• 30: 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]
• 31: A. Raniwala and T. Chiueh. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In Proc. of IEEE INFOCOM, 2005.
• 32: Kimaya Sanzgiri , Ian D. Chakeres , Elizabeth M. Belding-Royer, Determining Intra-Flow Contention along Multihop Paths in Wireless Networks, Proceedings of the First International Conference on Broadband Networks (BROADNETS'04), p.611-620, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.32]
• 33: S. Xu and T. Saadawi. Does the IEEE 802.11 MAC protocol work well in multihop wireless adhoc networks? IEEE Communications Magazine, 39(6):130--137, 2001.
• 34: X. Yang and N. Vaidya. On the physical carrier sense in wireless ad-hoc networks. In Proc. of IEEE INFOCOM, 2005.
• 35: J. Zhu, X. Guo, L. Yang, and W. S. Conner. Leveraging spatial reuse in 802.11 mesh networks with enhanced physical carrier sensing. In Proc. of IEEE ICC, 2004.
• 36: J. Zhu, S. Roy, X. Guo, and W. S. Conner. Maximizing aggregate throughput in 802.11 mesh networks with physical carrier sensring and two-radio multichannel clustering. In Proc. of NFS-RPI Workshop on Pervasive Computing and Networking, 2004.

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
intra-/inter-flow interference, temporal-spatial, wireless mesh network