{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:44:56Z","timestamp":1774417496890,"version":"3.50.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T00:00:00Z","timestamp":1120176000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOBILE Mob. Comput. Commun. Rev."],"published-print":{"date-parts":[[2005,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1094549.1094554","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"19-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":253,"title":["Weighted coloring based channel assignment for WLANs"],"prefix":"10.1145","volume":"9","author":[{"given":"Arunesh","family":"Mishra","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suman","family":"Banerjee","sequence":"additional","affiliation":[{"name":"University of Wisconsin, Madison, WI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William","family":"Arbaugh","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Jim Geier. Assigning 802.11b access point channels. Wi-Fi Planet.  Jim Geier. Assigning 802.11b access point channels. Wi-Fi Planet."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of ARRL\/CRRL Amateur Radio Computer Networking Conference","author":"Karn P.","year":"1990","unstructured":"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."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/190314.190334"},{"key":"e_1_2_1_4_1","unstructured":"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."},{"key":"e_1_2_1_5_1","volume-title":"Approximation Algorithms","author":"Vazirani Vijay","year":"2001","unstructured":"Vijay Vazirani . Approximation Algorithms . Springer Verlag , 2001 . Vijay Vazirani. Approximation Algorithms. Springer Verlag, 2001."},{"key":"e_1_2_1_6_1","volume-title":"If","author":"Recommended IEEE.","year":"2003","unstructured":"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."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2005.1497933"},{"key":"e_1_2_1_8_1","volume-title":"wireless lan medium access control (mac) and physical layer(phy) specifications: Specification for radio resource measurement","author":"IEEE.","year":"2003","unstructured":"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."},{"key":"e_1_2_1_9_1","unstructured":"Soekris Engineering. http:\/\/www.soekris.com.  Soekris Engineering. http:\/\/www.soekris.com."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of 27th Annual IEEE Conference on Local Computer Networks (LCN)","author":"Lee Youngseok","year":"2002","unstructured":"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."},{"key":"e_1_2_1_11_1","volume-title":"Wireless Communications: Principle and Practice","author":"Rappaport T","year":"1996","unstructured":"T Rappaport . Wireless Communications: Principle and Practice . Prentice Hall , 1996 . T Rappaport. Wireless Communications: Principle and Practice. Prentice Hall, 1996."},{"key":"e_1_2_1_12_1","volume-title":"Journal of Telecommunication Systems","author":"Krishnamachari Bhaskar","year":"2003","unstructured":"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."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025964603779"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/989459.989487"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1023720.1023742"},{"key":"e_1_2_1_16_1","volume-title":"A channel access protocol for multihop wireless networks with multiple channels","author":"Muir Andrew","year":"1998","unstructured":"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."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/997122.997130"},{"key":"e_1_2_1_18_1","volume-title":"IEEE Wireless Communications and Networking Conference","author":"Nasipuri Asis","year":"1999","unstructured":"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."},{"key":"e_1_2_1_19_1","volume-title":"Capacity evaluation of multi-channel multi-hop ad hoc networks","author":"Li Jiandong","year":"2002","unstructured":"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."},{"key":"e_1_2_1_20_1","volume-title":"Collision avoidance and resolution multiple access for multichannel wireless networks","author":"Garces Rodrigo","year":"2000","unstructured":"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."},{"key":"e_1_2_1_21_1","unstructured":"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\/"},{"key":"e_1_2_1_22_1","volume-title":"Circular colorings of edgeweighted graphs","author":"Mohar Bojan","year":"2002","unstructured":"Bojan Mohar . Circular colorings of edgeweighted graphs . 2002 . Bojan Mohar. Circular colorings of edgeweighted graphs. 2002."},{"key":"e_1_2_1_23_1","volume-title":"On conflict-free coloring of points and simple regions in the plane","author":"Har-Peled Sariel","year":"2003","unstructured":"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."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652123"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the IEEE IPDPS-2002 Workshop on Advances in Parallel and Distributed Computational Models","author":"Stephen","year":"2002","unstructured":"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."}],"container-title":["ACM SIGMOBILE Mobile Computing and Communications Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1094549.1094554","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1094549.1094554","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:13Z","timestamp":1750278133000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1094549.1094554"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["10.1145\/1094549.1094554"],"URL":"https:\/\/doi.org\/10.1145\/1094549.1094554","relation":{},"ISSN":["1559-1662","1931-1222"],"issn-type":[{"value":"1559-1662","type":"print"},{"value":"1931-1222","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,7]]},"assertion":[{"value":"2005-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}