Weighted coloring based channel assignment for WLANs

ABSTRACT

We propose techniques to improve the usage of wireless spectrum in the context of wireless local area networks (WLANs) using new channel assignment methods among interfering Access Points (APs). We identify new ways of channel re-use that are based on realistic interference scenarios in WLAN environments. We formulate a weighted variant of the graph coloring problem that takes into account realistic channel interference observed in wireless environments, as well as the impact of such interference on wireless users. We prove that the weighted graph coloring problem is NP-hard and propose scalable distributed algorithms that achieve significantly better performance than existing techniques for channel assignment. We evaluate our algorithms through extensive simulations and experiments over an in-building wireless testbed.

REFERENCES

• 1: Jim Geier. Assigning 802.11b access point channels. Wi-Fi Planet.
• 2: P. Karn. Maca---a new channel access method for packet radio. In Proceedings of ARRL/CRRL Amateur Radio Computer Networking Conference, 1990.
• 3: Vaduvur Bharghavan , Alan Demers , Scott Shenker , Lixia Zhang, MACAW: a media access protocol for wireless LAN's, Proceedings of the conference on Communications architectures, protocols and applications, p.212-225, August 31-September 02, 1994, London, United Kingdom
• 4: AustWireless. 350 series ap w/captured diversity antennas and 128-bit wep. AustWireless.com.
• 5: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 6: IEEE. Recommended Practice for Multi-Vendor Access Point Interoperability via an Inter-Access Point Protocol Across Distribution Systems Supporting IEEE 802.11 Operation. IEEE Standard 802. If, July 2003.
• 7: Ishwar Ramani and Stefan Savage. Syncscan:practical fast handoff for 802.11 infrastructure networks. In Proceedings of IEEE Infocom, 2005.
• 8: IEEE. Lan man standards of the ieee computer society. wireless lan medium access control (mac) and physical layer(phy) specifications: Specification for radio resource measurement. IEEE Draft 802.11K, 2003.
• 9: Soekris Engineering. http://www.soekris.com.
• 10: Youngseok Lee , Kyoungae Kim , Yanghee Choi, Optimization of AP Placement and Channel Assignment in Wireless LANs, Proceedings of the 27th Annual IEEE Conference on Local Computer Networks, p.831-836, November 06-08, 2002
• 11: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 12: Bhaskar Krishnamachari, Stephen Wicker, Ramon Bejar, and Cesar Fernandez. On the complexity of distributed self-configuration in wireless networks. Journal of Telecommunication Systems, 2003.
• 13: Filipe F. Mazzini , Geraldo R. Mateus , James Macgregor Smith, Lagrangean based methods for solving large-scale cellular network design problems, Wireless Networks, v.9 n.6, p.659-672, November 2003 [doi>10.1023/A:1025964603779]
• 14: Jungmin So , Nitin H. Vaidya, Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver, 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.989487]
• 15: 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]
• 16: Andrew Muir and J. J. Garcia-Luna-Aceves. A channel access protocol for multihop wireless networks with multiple channels. 1998.
• 17: 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]
• 18: Asis Nasipuri, Jun Zhuang, and Samir Das. A multichannel csma mac protocol for mobile multihop networks. In IEEE Wireless Communications and Networking Conference, 1999.
• 19: Jiandong Li, Zygmunt J. Haas, and Min Sheng. Capacity evaluation of multi-channel multi-hop ad hoc networks. 2002.
• 20: Rodrigo Garces and J. J. Garcia-Luna-Aceves. Collision avoidance and resolution multiple access for multichannel wireless networks. 2000.
• 21: Commercial products. http://www.meshdynamics.com/ http://www.engim.com/ http://www.belairnetworks.com/
• 22: Bojan Mohar. Circular colorings of edgeweighted graphs. 2002.
• 23: Sariel Har-Peled and Shakhar Smorodinsky. On conflict-free coloring of points and simple regions in the plane. 2003. http://www.uiuc.edu/sariel/research/papers/02/coloring.
• 24: Guy Even , Zvi Lotker , Dana Ron , Shakhar Smorodinsky, Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.691-700, November 16-19, 2002
• 25: Stephen T. Hedetniemi , David Pokrass Jacobs , Pradip K. Srimani, Fault Tolerant Distributed Coloring Algorithms that Stabilize in Linear Time, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.153, April 15-19, 2002

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory