Abstract
In this paper, we consider the problem of channel assignment in multi-radio, multi-channel wireless mesh networks. We assume a binary interference model and represent the set of interfering links in a network topology as a conflict graph. We then develop a new centralised stochastic local search algorithm to find a channel assignment that minimises the network interference. Our algorithm assigns channels to communication links rather than radio interfaces. By doing so, our algorithm not only does preserve the network topology, but is also independent of the network routing layer. We compare the performance of our algorithm with that of a well-known Tabu-based approach (by Subramanian et al.) on randomly generated sparse and dense network topologies. Using graph-theoretic evaluation and ns2 simulations (a widely used discrete event network simulator), we show that our algorithm consistently outperforms the Tabu-based approach in terms of both the network interference and the throughput obtained under various offered loads. In particular, for a practical setting of 3 radio interfaces per mesh node in a dense network topology with 12 channels available, our approach achieves 70% lower network interference and thus 15 times higher average throughput than those achieved by the Tabu-based approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
The network simulator ns-2, http://www.isi.edu/nsnam/ns/
Aardal, K.I., van Hoesel, S.P.M., Koster, A.M., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Annals of Operations Research 153(1), 79–129 (2007)
Brar, G., Blough, D.M., Santi, P.: Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks. In: Proc. ACM MobiCom (2006)
Calvo, R., Campo, J.: Adding multiple interface support in ns-2. Tech. rep (2007), http://personales.unican.es/aguerocr/files/ucmultiifacessupport.pdf
Crichigno, J., Wu, M., Shu, W.: Protocols and architectures for channel assignment in wireless mesh networks. Ad Hoc Networks 6(7), 1051–1077 (2008)
Hertz, A., Werra, D.: Using tabu search techniques for graph coloring. Computing 39(4), 345–351 (1987)
Kawadia, V., Kumar, P.R.: Principles and protocols for power control in wireless ad hoc networks. IEEE Journal on Selected Areas in Communications 23(1), 76–88 (2005)
Ko, B., Misra, V., Padhye, J., Rubenstein, D.: Distributed channel assignment in multi-radio 802.11 mesh networks. In: Proc. IEEE WCNC (2007)
Liu, T., Liao, W.: Interference-aware QoS routing for multi-rate multi-radio multi-channel ieee 802. 11 wireless mesh networks. Trans. Wireless. Comm. 8(1), 166–175 (2009)
Maheshwari, R., Jain, S., Das, S.R.: A measurement study of interference modeling and scheduling in low-power wireless networks. In: Proc. ACM SenSys (2008)
Marina, M., Das, S., Subramanian, A.: A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks. Computer networks 54(2), 241–256 (2010)
McAllester, D.A., Selman, B., Kautz, H.A.: Evidence for invariants in local search. In: AAAI/IAAI, pp. 321–326 (1997)
Newton, M.A.H., Pham, D.N., Sattar, A., Maher, M.: Kangaroo: An efficient constraint-based local search system using lazy propagation. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 645–659. Springer, Heidelberg (2011)
Pham, D.N., Thornton, J., Gretton, C., Sattar, A.: Combining adaptive and dynamic local search for satisfiability. JSAT 4(2-4), 149–172 (2008)
Ramachandran, K., Belding, E., Almeroth, K., Buddhikot, M.: Interference-aware channel assignment in multi-radio wireless mesh networks. In: Proc. IEEE INFOCOM (2006)
Raniwala, A., Chiueh, T.: Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In: Proc. IEEE INFOCOM (2005)
Shin, M., Lee, S., Kim, Y.: Distributed channel assignment for multi-radio wireless networks. In: Proc. IEEE MASS (2006)
Si, W., Selvakennedy, S., Zomaya, A.: An overview of channel assignment methods for multi-radio multi-channel wireless mesh networks. Journal of Parallel and Distributed Computing 70(5), 505–524 (2010)
Subramanian, A., Gupta, H., Das, S.R., Cao, J.: Minimum interference channel assignment in multiradio wireless mesh networks. IEEE Transactions on Mobile Computing 7(11) (2008)
Tan, W., Hu, P., Portmann, M.: Experimental evaluation of measurement-based SINR interference models. In: Proc. IEEE WoWMoM (2012)
Zilberstein, S.: Using anytime algorithms in intelligent systems. AI Magazine 17(3), 73–83 (1996), http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Newton, M.A.H., Pham, D.N., Tan, W.L., Portmann, M., Sattar, A. (2013). Stochastic Local Search Based Channel Assignment in Wireless Mesh Networks. In: Schulte, C. (eds) Principles and Practice of Constraint Programming. CP 2013. Lecture Notes in Computer Science, vol 8124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40627-0_61
Download citation
DOI: https://doi.org/10.1007/978-3-642-40627-0_61
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40626-3
Online ISBN: 978-3-642-40627-0
eBook Packages: Computer ScienceComputer Science (R0)