Distributed channel management in uncoordinated wireless environments

ABSTRACT

Wireless 802.11 hotspots have grown in an uncoordinated fashion with highly variable deployment densities. Such uncoordinated deployments, coupled with the difficulty of implementing coordination protocols, has often led to conflicting configurations (e.g., in choice of transmission power and channel of operation) among the corresponding Access Points (APs). Overall, such conflicts cause both unpredictable network performance and unfairness among clients of neighboring hotspots. In this paper, we focus on the fairness problem for uncoordinated deployments. We study this problem from the channel assignment perspective. Our solution is based on the notion of channel-hopping, and meets all the important design considerations for control methods in uncoordinated deployments - distributed in nature, minimal to zero coordination among APs belonging to different hotspots, simple to implement, and interoperable with existing standards. In particular, we propose a specific algorithm called MAXchop, which works efficiently when using only non-overlapping wireless channels, but is particularly effective in exploiting partially-overlapped channels that have been proposed in recent literature. We also evaluate how our channel assignment approach complements previously proposed carrier sensing techniques in providing further performance improvements. Through extensive simulations on real hotspot topologies and evaluation of a full implementation of this technique, we demonstrate the efficacy of these techniques for not only fairness, but also the aggregate throughput, metrics.We believe that this is the first work that brings into focus the fairness properties of channel hopping techniques and we hope that the insights from this research will be applied to other domains where a fair division of a system's resources is an important consideration.

REFERENCES

• 1: Aditya Akella , Glenn Judd , Srinivasan Seshan , Peter Steenkiste, Self-management in chaotic wireless deployments, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080849]
• 2: Anand Balachandran , Geoffrey M. Voelker , Paramvir Bahl, Wireless hotspots: current challenges and future directions, Proceedings of the 1st ACM international workshop on Wireless mobile applications and services on WLAN hotspots, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941326.941328]
• 3: Yigal Bejerano , Seung-Jae Han , Li (Erran) Li, Fairness and load balancing in wireless LANs using association control, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023751]
• 4: A. Mishra, V. Brik, S. Banerjee, A. Srinivasan, and W. Arbaugh, "A client-driven approach for channel management in wireless lans," in IEEE Infocom, 2006.
• 5: A. Vasan, R. Ramjee, and T. Woo, "Echos: Enhanced capacity 802.11 hotspots," in IEEE Infocom, 2005.
• 6: Paramvir Bahl , Ranveer Chandra , John Dunagan, SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless 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.1023742]
• 7: "Intel pro/wireless network connection for mobile," http://www.intel.com/network/connectivity/products.
• 8: Arunesh Mishra , Vivek Shrivastava , Suman Banerjee , William Arbaugh, Partially overlapped channels not considered harmful, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 9: J. Geier, "Assigning 802.11b access point channels," Wi-Fi Planet, 2004.
• 10: C. McDiarmid and B. Reed, "Channel assignment and weighted coloring," Wiley Networks, 2000.
• 11: G. B.Sabbatel, A. Duda, M. Heusse, and F. Rousseau, "Short-term fairness of 802.11 networks with several hosts," in IEEE MWCN, 2004.
• 12: Avrim Blum, New approximation algorithms for graph coloring, Journal of the ACM (JACM), v.41 n.3, p.470-516, May 1994 [doi>10.1145/176584.176586]
• 13: "Wigle: Wireless geographic logging engine," http://www.wigle.net/.
• 14: Arunesh Mishra , Suman Banerjee , William Arbaugh, Weighted coloring based channel assignment for WLANs, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.3, July 2005 [doi>10.1145/1094549.1094554]
• 15: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 16: B. Krishnamachari, S. Wicker, R. Bejar, and C. Fernandez, "On the complexity of distributed self-configuration in wireless networks," Telecommunication Systems, 2003.
• 17: 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]
• 18: 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]
• 19: Ashish Raniwala , Kartik Gopalan , Tzi-cker Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.2, April 2004 [doi>10.1145/997122.997130]
• 20: Jungmin So , Nitin H. Vaidya, Load Balancing Routing in Multi-Channel HybridWireless Networks with Single Network Interface, Proceedings of the Second International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks, p.14, August 22-24, 2005 [doi>10.1109/QSHINE.2005.30]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

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

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
IEEE 802.11, channel assignment, channel hopping, partially overlapped channels