Weighted coloring based channel assignment for WLANs

Association for Computing Machinery (ACM) - Tập 9 Số 3 - Trang 19-31 - 2005
Arunesh Mishra1, Suman Banerjee2, William A. Arbaugh1
1University of Maryland, College Park, MD
2University of Wisconsin - Madison WI#TAB#

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

Jim Geier. Assigning 802.11b access point channels. Wi-Fi Planet. Jim Geier. Assigning 802.11b access point channels. Wi-Fi Planet.

P. Karn . Maca---a new channel access method for packet radio . In Proceedings of ARRL/CRRL Amateur Radio Computer Networking Conference , 1990 . P. Karn. Maca---a new channel access method for packet radio. In Proceedings of ARRL/CRRL Amateur Radio Computer Networking Conference, 1990.

10.1145/190314.190334

AustWireless. 350 series ap w/captured diversity antennas and 128-bit wep. AustWireless.com. AustWireless. 350 series ap w/captured diversity antennas and 128-bit wep. AustWireless.com.

Vijay Vazirani . Approximation Algorithms . Springer Verlag , 2001 . Vijay Vazirani. Approximation Algorithms. Springer Verlag, 2001.

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 . 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.

10.1109/INFCOM.2005.1497933

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 . 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.

Soekris Engineering. http://www.soekris.com. Soekris Engineering. http://www.soekris.com.

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 . 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.

T Rappaport . Wireless Communications: Principle and Practice . Prentice Hall , 1996 . T Rappaport. Wireless Communications: Principle and Practice. Prentice Hall, 1996.

Bhaskar Krishnamachari , Stephen Wicker , Ramon Bejar , and Cesar Fernandez . On the complexity of distributed self-configuration in wireless networks . Journal of Telecommunication Systems , 2003 . Bhaskar Krishnamachari, Stephen Wicker, Ramon Bejar, and Cesar Fernandez. On the complexity of distributed self-configuration in wireless networks. Journal of Telecommunication Systems, 2003.

10.1023/A:1025964603779

10.1145/989459.989487

10.1145/1023720.1023742

Andrew Muir and J. J. Garcia-Luna-Aceves . A channel access protocol for multihop wireless networks with multiple channels . 1998 . Andrew Muir and J. J. Garcia-Luna-Aceves. A channel access protocol for multihop wireless networks with multiple channels. 1998.

10.1145/997122.997130

Asis Nasipuri , Jun Zhuang , and Samir Das . A multichannel csma mac protocol for mobile multihop networks . In IEEE Wireless Communications and Networking Conference , 1999 . Asis Nasipuri, Jun Zhuang, and Samir Das. A multichannel csma mac protocol for mobile multihop networks. In IEEE Wireless Communications and Networking Conference, 1999.

Jiandong Li , Zygmunt J. Haas , and Min Sheng . Capacity evaluation of multi-channel multi-hop ad hoc networks . 2002 . Jiandong Li, Zygmunt J. Haas, and Min Sheng. Capacity evaluation of multi-channel multi-hop ad hoc networks. 2002.

Rodrigo Garces and J. J. Garcia-Luna-Aceves . Collision avoidance and resolution multiple access for multichannel wireless networks . 2000 . Rodrigo Garces and J. J. Garcia-Luna-Aceves. Collision avoidance and resolution multiple access for multichannel wireless networks. 2000.

Commercial products. http://www.meshdynamics.com/ http://www.engim.com/ http://www.belairnetworks.com/ Commercial products. http://www.meshdynamics.com/ http://www.engim.com/ http://www.belairnetworks.com/

Bojan Mohar . Circular colorings of edgeweighted graphs . 2002 . Bojan Mohar. Circular colorings of edgeweighted graphs. 2002.

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. 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.

10.5555/645413.652123

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 . 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.

Thông tin
Thông tin xuất bản

Association for Computing Machinery (ACM)

Tập 9 Số 3

19-31

Thông tin tác giả