Arunesh Mishra
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.
- Jim Geier. Assigning 802.11b access point channels. Wi-Fi Planet.Google Scholar
- P. Karn. Maca---a new channel access method for packet radio. In Proceedings of ARRL/CRRL Amateur Radio Computer Networking Conference, 1990.Google Scholar
- V. Bhargavan, A. Demers, S. Shenker, and L. Zhang. Macaw: A media access protocol for wirelesss lans. In Proceedings of ACM Sigcomm, 1994. Google ScholarDigital Library
- AustWireless. 350 series ap w/captured diversity antennas and 128-bit wep. AustWireless.com.Google Scholar
- Vijay Vazirani. Approximation Algorithms. Springer Verlag, 2001. Google ScholarDigital Library
- 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.Google Scholar
- Ishwar Ramani and Stefan Savage. Syncscan:practical fast handoff for 802.11 infrastructure networks. In Proceedings of IEEE Infocom, 2005.Google ScholarCross Ref
- 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.Google Scholar
- Soekris Engineering. http://www.soekris.com.Google Scholar
- Youngseok Lee, Kyoungae Kim, and Yanghee Choi. Optimization of ap placement and channel assignment in wireless lans. In Proceedings of 27th Annual IEEE Conference on Local Computer Networks (LCN), 2002. Google ScholarDigital Library
- T Rappaport. Wireless Communications: Principle and Practice. Prentice Hall, 1996. Google ScholarDigital Library
- Bhaskar Krishnamachari, Stephen Wicker, Ramon Bejar, and Cesar Fernandez. On the complexity of distributed self-configuration in wireless networks. Journal of Telecommunication Systems, 2003.Google Scholar
- Filipe Mazzini, Geraldo Mateus, and James Macgregor Smith. Lagrangean based methods for solving large-scale cellular network design problems. Journal of Wireless Networks, 2003. Google ScholarDigital Library
- Jungmin So and Nitin Vaidya. Multi-channel mac for ad hoc networks: Handling multichannel hidden terminals using a single transceiver. In Proceedings of ACM MobiHoc, 2004. Google ScholarDigital Library
- Paramvir Bahl, Ranveer Chandra, and John Dunagan. Ssch: Slotted seeded channel hopping for capacity improvement in ieee 802.11 ad-hoc wireless networks. In Proceedings of ACM Mobicom, 2004. Google ScholarDigital Library
- Andrew Muir and J. J. Garcia-Luna-Aceves. A channel access protocol for multihop wireless networks with multiple channels. 1998.Google Scholar
- Ashish Raniwala, Kartik Gopalan, and Tzi cker Chiueh. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks. ACM SIGMOBILE Mobile Computing and Communications Review, 2004. Google ScholarDigital Library
- Asis Nasipuri, Jun Zhuang, and Samir Das. A multichannel csma mac protocol for mobile multihop networks. In IEEE Wireless Communications and Networking Conference, 1999.Google Scholar
- Jiandong Li, Zygmunt J. Haas, and Min Sheng. Capacity evaluation of multi-channel multi-hop ad hoc networks. 2002.Google Scholar
- Rodrigo Garces and J. J. Garcia-Luna-Aceves. Collision avoidance and resolution multiple access for multichannel wireless networks. 2000.Google Scholar
- Commercial products. http://www.meshdynamics.com/ http://www.engim.com/ http://www.belairnetworks.com/Google Scholar
- Bojan Mohar. Circular colorings of edgeweighted graphs. 2002.Google Scholar
- 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.Google Scholar
- Guy Even, Zvi Lotker, Dana Ron, and Shakhar Smorodinsky. Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. In Proceedings of FOCS-2002, 2002. Google ScholarDigital Library
- Stephen T. Hedetniemi and David P. Jacobs. Fault tolerant distributed coloring algorithms that stabilize in linear time. In Proceedings of the IEEE IPDPS-2002 Workshop on Advances in Parallel and Distributed Computational Models, 2002. Google ScholarDigital Library
Index Terms
- Weighted coloring based channel assignment for WLANs
Recommendations
Distributed channel assignment algorithms for 802.11n WLANs with heterogeneous clients
As the latest IEEE 802.11 standard, 802.11n applies several new technologies, such as multiple input multiple output (MIMO), channel bonding, and frame aggregation to greatly improve the rate, range and reliability of wireless local area networks (WLANs)...
A distributed channel assignment algorithm for uncoordinated WLANs
CCNC'10: Proceedings of the 7th IEEE conference on Consumer communications and networking conferenceIEEE 802.11 WLANs are becoming more and more popular in homes and urban areas. As opposed to traditional WLANs, the access points (APs) in these networks are often deployed by network non-specialists in an uncoordinated manner, leading to unplanned ...
Channel assignment schemes for infrastructure-based 802.11 WLANs: A survey
Efficient channel assignment is crucial for successful deployment and operation of IEEE 802.11-based WLANs. In this article we present a survey on the state of the art channel assignment schemes in IEEE 802.11-based WLANs. After detailing out all the ...
Comments