A Minimum-Spanning-Tree-Inspired Algorithm for Channel Assignment in 802.11 Networks

Iwona Dolińska, Mariusz Jakubowski, Antoni Masiukiewicz, Grzegorz Rządkowski, Kamil Piórczyński


Channel assignment in 2.4 GHz band of 802.11 standard is still important issue as a lot of 2.4 GHz devices are in use. This band  offers only three non-overlapping channels, so in crowded environment users can suffer from high interference level.  In this paper, a greedy algorithm inspired by the Prim’s algorithm for finding minimum spanning trees (MSTs) in undirected graphs is considered for channel assignment in this type of networks. The proposed solution tested for example network distributions achieves results close to the exhaustive approach and is, in many cases, several orders of magnitude faster.

Full Text:



G. Hiertz, R. Denteneer, D. Stibor, P. Lothar, Y. Zang, C. X. Pérea, B. Walke, “The IEEE 802.11 Universe,” IEEE Communications Magazine, January 2010, pp. 62-70.

S. Chieochan, E. Hossain, J. Diamond, “Channel Assignment Schemes for Infrastructure-Based 802.11 WLANs: A Survey”, IEEE Communications Surveys & Tutorials, vol. 12, no. 1, 1st Quarter 2010, pp. 124-136.

I. Dolińska, A. Masiukiewicz, G. Rządkowski, “The mathematical model for interference simulation and optimization in 802.11n networks”, in Workshop, Concurrency Specification and Programming 2013, Warsaw University, 2013, pp. 99-110.

J. Herzen, R. Merz, P. Thiran,, “Distributed Spectrum Assignment for Home WLANs”, in Proc. of IEEE INFOCOM , 2013, pp. 1573-1581.

P. Gajewski, S. Wszelak, „Optimisation of AC location in WLAN networks with direct finding metod”, Telecommunication Review no 8-9 2007, pp. 260-265 (in Polish).

Xirrus, (2011), “Wireless solution for High Density Wireless”, www.xirrus.com.

I. Dolińska, A. Masiukiewicz, G. Rządkowski, “Channel selection in home 802.11 standard networks”, in Proc. of IEEE Digital Technologies Żylina, 2014, pp. 58-64.

Y. Bejerano, S. Han, L. Li, “Fairness and Load Balancing in Wireless LANs Using Association Control”, in Proc. of 10th International Conference Mobile Computing and Networking (Mobicom 04), ACM Press New York 2004, pp. 315-329.

A. Akella, G. Judd, S. Seshan, P. Steenkiste, “Self-Management in Chaotic Wireless Deployments”, in Proc. of 11th International Conference Mobile Computing and Networking (Mobicom 05), ACM Press New York 2005, pp. 185-199.

B. Alawieh, C. Assi, H. Mouftah, Y. Zhang “Improving Spatial Reuse in Multihop Wireless Networks - A Survey”, IEEE Communications Surveys & Tutorials,, vol. 11, no. 3, 3rd Quartet 2009, pp. 71-91.

A. Hills, “Large-Scale Wireless LAN Design”, IEEE Communication Magagazine, vol. 39, no. 11, pp. 98–107, November 2001.

Y. Choi, Y. Lee, K. Kim, “Optimization of AP Placement and Channel Assignment in Wireless LANs”, in Proc. of 27th Annual IEEE Conf. Local Computer Networks, pp. 831–836, Nov. 2002.

P. Wertz, M. Sauter, F. Landstorfer, G. Wolfle, R. Hoppe, “Automatic Optimization Algorithms for the Planning of Wireless Local Area Networks”, in Proc. IEEE Vehicular Technology Conference, vol. 4, pp. 3010–3014, Sep. 2004.

X. Ling, K. L. Yeung, “Joint Access Point Placement and Channel Assignment for 802.11 Wireless LANs’”, in Proc. IEEE WCNC’05, 2005, vol. 3, pp. 1583-1588.

A. Mishra, V. Brik, S. Banerjee, A. Srinivasan, W. Arbaugh, “A Client-driven Approach for Channel Management in Wireless LANs”, in Proc. 25th IEEE International Conference on Computer Communications (INFOCOM’06), 2006, vol. 3, pp. 1300-1312.

M. Achanta, “Method and Apparatus for Least Congested Channel Scan for Wireless Access Points”, US Patent No. 20060072602, Apr. 2006.

R. Akl, A. Arepally, “Dynamic Channel Assignment in IEEE 802.11 networks’,” in Proc. IEEE International Conference on Portable Information Devices (PORTABLE’07), 2007, pp. 309-314.

I. Dolińska, A. Masiukiewicz, “Location Ability of 802.11 Access Points”, in Proc. of Conference Information and Digital Technologies, 2015, Żylina, Slovakia , pp. 233-237.

IEEE Std 802.11k™-2008.

IEEE Std 802.11v™-2011.

R. L. Freeman, “Radio System Design for Telecommunication”, Wiley &Sons 2007.

I. Dolińska, A. Masiukiewicz, G. Rządkowski, M. Jakubowski, “Algorithms for Channels Assignment in 802.11 Networks”, in Proc. of Conference Information and Digital Technologies 2016, Rzeszów, Poland, pp .83-89.

D. A. Marcus, “Graph Theory: A Problem Oriented Approach”, Mathematical Association of America, 2008.

K. Piórczynski, „Tests of RBA algorithm for Chanel assigment in small home Wi-Fi networks”, Diploma , Vistula University, 2016 (in Polish).

Fuxjäger P., Valerio D., Ricciato F., “The Myth of Non-Overlapping Channels: Interference Measurements in IEEE 802.11”, in Proc. of 4th Annual Conference on Wireless on Demand Network Systems and Service (WONS'07), 2007, pp. 1-9.


  • There are currently no refbacks.

International Journal of Electronics and Telecommunications
is a periodical of Electronics and Telecommunications Committee
of Polish Academy of Sciences

eISSN: 2300-1933