MRS: a simple cross-layer heuristic to improve throughput capacity in wireless mesh networks

ABSTRACT

Wireless Mesh Networks (WMNs) are an emerging architecture based on multi-hop transmission. ISPs considers WMNs as a potential future technology to offer broadband Internet access. Therefore, in WMNs, the throughput capacity of the wireless backbone becomes a key factor, limiting the scalability in terms of users able to effectively take advantage of the network. Increasing the effective throughput capacity will support WMNs become a very cost-effective solution for wireless ISPs.Based on the analysis of the theoretical capacity bound derived by Gupta et al., we propose MRS (Mesh Routing Strategy), a novel cross layer routing solution. MRS is specifically designed for Wireless Mesh Networks, where routing is challenging due to the unreliable wireless medium. Traditional routing paradigms are not able to overcome this issue, resulting in an average throughput experienced by the network far lower than the theoretical throughput capacity bound. This paper shows how a cross-layer approach will consistently improve the throughput experienced by large-scale multi-hop networks. We show through simulation that our proposal increases throughput while reducing the average transmitted power. Furthermore, MRS limits interference and gets closer to the theoretical throughput capacity bound.

REFERENCES

• 1: Ian F. Akyildiz , Xudong Wang , Weilin Wang, Wireless mesh networks: a survey, Computer Networks and ISDN Systems, v.47 n.4, p.445-487, 15 March 2005 [doi>10.1016/j.comnet.2004.12.001]
• 2: D. Beyer,"Fundamental characteristics and benefits of wireless routing (mesh) networks, "Wireless Communications Association International Technical Symposium, Jan. 2002.
• 3: D. Decouto, D. Aguayo, B. Chambers, and R. Morris, "Performance of multi-hop wireless networks: Shortest path is not enough," Proceedings of First Workshop on Hot Topics in Networks (HotNets-I), Oct. 2002.
• 4: Henrik Lundgren , Erik Nordströ , Christian Tschudin, Coping with communication gray zones in IEEE 802.11b based ad hoc networks, Proceedings of the 5th ACM international workshop on Wireless mobile multimedia, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570790.570799]
• 5: P. Gupta and P. Kumar, "The capacity of wireless networks," IEEE Transactions on Information Theory, Mar. 2000.
• 6: J. Gomez and A. Campbell, "A case for variable-range transmission power control in wireless ad hoc networks," Proceedings of IEEE INFOCOM'04, Mar. 2004.
• 7: L. Iannone, R. Khalili, K. Salamatian, and S. Fdida, "Cross-layer routing in wireless mesh networks," In Proceeding of ISWCS'04, Sept. 2004.
• 8: J. Jaffe, "Algorithms for finding paths with multiple constraints," Networks, no. 14, pp. 95--116, 1984.
• 9: The Network Simulator NS-2, "http://www.isi.edu/nsnam/ns/."
• 10: R. Punnoose, P. Nikitin, and D. Stancil, "Efficient simulation of ricean fading within a packet simulator," Proceedings of IEEE VTC2000-spring, Sept. 2000.
• 11: IEEE, "Wireless lan medium access control (mac) and physical layer (phy) specifications," IEEE Standard 802.11, June 1999.
• 12: E. Perkins, E. Belding-Royer, and S. Das, "Ad hoc on demand distance vector (aodv) routing," RFC 3561.
• 13: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 14: D. B. Johnson and D. A. Maltz, "Dynamic source routing in ad hoc wireless networks," Mobile Computing, vol. 353, 1996.
• 15: B. Awerbuch, D. Holmer, and H. Rubens, "High throughput route selection in multi-rate ad hoc networks," Technical report, Johns Hopkins University, Computer Science Department, 2003.
• 16: 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
• 17: U. Kozat, I. Koutsopoulos, and L. Tassiulas, "A framework for cross-layer design of energy-efficient communication with qos provvisioning in multi-hop wireless networks," Proceedings of IEEE INFOCOM'04, Mar. 2004.
• 18: T. Elbatt and A. Ephremides, "Joint scheduling and power control for wireless ad hoc networks," Proceedings of IEEE INFOCOM'02, June 2002.
• 19: R. Cruz and A. Santhanam, "Optimal routing, link scheduling and power control of multi-hop wireless network," Proceedings of IEEE INFOCOM'03, Mar. 2003.
• 20: M. Chiang, "To layer or not to layer: Balancing transport and physical layers in wireless multihop networks," Proceedings of IEEE INFOCOM'04, Mar. 2004.
• 21: W. Yuen, H. Lee, and T. Anderson, "Simple but effective cross-layer networking system for mobile ad hoc networks," Proceedings of 13th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC'02), Sept. 2002.
• 22: 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]
• 23: Ramin Hekmat , Piet Van Mieghem, Interference in wireless multi-hop ad-hoc networks and its effect on network capacity, Wireless Networks, v.10 n.4, p.389-399, July 2004 [doi>10.1023/B:WINE.0000028543.41559.ed]
• 24: R. Ramanathan and R. Rosales-Hain, "Topology control of multihop wireless networks using transmit power adjustment," Proceedings of IEEE INFOCOM'00, Mar. 2000.
• 25: M. Subbarao, "Dynamic power-conscious routing for manets: An initial approach," Proceedings of IEEE Vehicular Technology Conference, May 1999.
• 26: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 27: V. Kawadia and P. Kumar, "Principles and protocols for power control in wireless ad hoc networks," In Journal on Selected Areas in Communications (JSAC) Wireless Ad Hoc Networks - Part I, Jan. 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

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

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Algorithms, Design, Performance

Keywords:
cross-layer, mesh networks, multi-hop networks capacity, power control, routing