Long distance wireless mesh network planning: problem formulation and solution

ABSTRACT

Several research efforts as well as deployments have chosen IEEE802.11 as a low-cost, long-distance access technology to bridge the digital divide. In this paper, we consider the important issue of planning such networks to the minimize system cost. This is a non-trivial task since it involves several sets of variables: the network topology, tower heights, antenna types to be used and the irorientations, and radio transmit powers. The task is further complicated due to the presence of network performance constraints, and the inter-dependence among the variables. Our first contribution in this paper is the formulation of this problem in terms of the variables, constraints and the optimization criterion. Our second contribution is in identifying the dependencies among the variables and breaking-down the problem into four tractable sub-parts. In this process, we extensively use domain knowledge to strike a balance between tractability and practicality.

We have evaluated the proposed algorithms using random input sets as well as real-life instances with success. We have been able to show detailed planning of network topology, required tower heights, antenna types, and transmit powers for the Ashwini project, a long distance WiFi network under deployment in Andhra Pradesh, India, In this case, we are able to achieve within 2% additional cost of a lower bound estimate.

REFERENCES

• 1: Pravin Bhagwat, Bhaskaran Raman, and Dheeraj Sanghi. Turning 802.11 Inside-Out. In HotNets-II, Nov 2003.
• 2: Eric Brewer , Michael Demmer , Bowei Du , Melissa Ho , Matthew Kam , Sergiu Nedevschi , Joyojeet Pal , Rabin Patra , Sonesh Surana , Kevin Fall, The Case for Technology in Developing Regions, Computer, v.38 n.6, p.25-38, June 2005 [doi>10.1109/MC.2005.204]
• 3: Project Ashwini. http://www.byrrajufoundation.org/ashwini_overview.htm.
• 4: New wireless networking system brings eye care to thousands in India. http://www.berkeley.edu/news/media/releases/2006/06/06_telemedicine.sht%ml, June 2006. U.C.Berkeley News.
• 5: Nepal Wireless. http://www.nepalwireless.net/.
• 6: DjurslandS.net: The story of a project to support the weak IT infrastructure in an low populated area of Denmark. http://djurslands.net/biblioteket/international/djurslands_net_english_presentation.ppt.
• 7: Bhaskaran Raman. Digital Gangetic Plains: 802.11-based Low-Cost Networking for Rural Areas, 2001-2004: A Report. http://www.cse.iitk.ac.in/users/braman/dgp.html, 2004.
• 8: Jeffrey E. Wieselthier, Gam D. Nguyen, and Anthony Ephremides. On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks. In INFOCOM, 2000.
• 9: Bhaskar Ramamurthi. Broadband Wireless Technology for Rural India. In XXVIII URSI General Assembly, Oct 2005.
• 10: Kameswari Chebrolu , Bhaskaran Raman , Sayandeep Sen, Long-distance 802.11b links: performance measurements and experience, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161099]
• 11: HyperGain 2.4 GHz Outdoor Directional 802.11b and 802.11g WiFi Antennas for Wireless LAN Systems. http://www.hyperlinktech.com/web/antennas_2400_out_directional.php.
• 12: 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]
• 13: Sayandeep Sen. Topology planning for long distance wireless mesh networks. Master's thesis, Indian Institute of Technology Kanpur, 2006.
• 14: A Ravindran, Don T. Phillips, and James J. Solberg. Operation Research Principles and Practice, chapter 11.2. John Wiley & Sons, 1986.
• 15: QSOPT Linear Programming Solver. http://www2.isye.gatech.edu/~wcook/qsopt/.
• 16: Rajesh Gandhi. Empirical path loss models for 802.11b links. Master's thesis, Indian Institute of Technology Kanpur, 2003.
• 17: Ram Ramanathan and Regina Hain. Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment. In INFOCOM, pages 404--413, 2000.
• 18: R. Wattenhofer, L. Li, P. Bahl, and Y. M. Wang. Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks. In INFOCOM, 2001.
• 19: Zhuochuan Huang, Chien-Chung Shen, C. Srisathapornphat, and C. Jaikaeo. Topology Control for Ad Hoc Networks with Directional Antennas. In ICCN, 2002.
• 20: S. A. Borbash and E. H. Jennings. Distributed Topology Control Algorithm for Multihop Wireless Networks. In IJCNN, 2002.
• 21: Nilesh Mishra , Kameswari Chebrolu , Bhaskaran Raman , Abhinav Pathak, Wake-on-WLAN, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135893]
• 22: Shridhar Mubaraq Mishra, John Hwang, Dick Filippini, Tom Du, Reza Moazzami, and Lakshminarayanan Subramanian. Economic Analysis of Networking Technologies for Rural Developing Regions. In 1st Workshop on Internet and Network Economics, Sep 2005.

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
          Subjects: Network topology

General Terms:
Algorithms

Keywords:
802.11 mesh networks, long-distance WiFi, low cost networking, rural Connectivity