A New Algorithm for Link Scheduling in MIMO Wireless Mesh Networks with Various Interference Condition by Ant Colony Algorithm

Subject Areas : Telecommunication networks

Sadegh Zarmehi ¹ , Mahmoud Daneshvar Farzanegan ² , Avid Avokh ³

1 - Department of Electrical Engineering- Najafabad Branch, Islamic Azad University, Najafabad, Iran
2 - Smart Micro Grids Research Center, Najafabad Branch, Islamic Azad University, Najafabad, Iran
3 - Digital Processing and Machine Vision Research Center- Najafabad Branch, Islamic Azad University, Najafabad, Iran

Received: 2022-08-09 Accepted : 2022-10-16 Published : 2024-08-22

Keywords: Ant Colony Algorithm, Wireless Mesh Network, link scheduling, multi-input multi-output antenna, strong and weak interference,

Abstract :

Wireless mesh networks are appropriate and cost-effective infrastructure for Internet but due to the limited scalability and capacity, a lot of research has been doing on new ways to improve these limitations such as optimization of scheduling, routing, etc. In this paper focusing on time division multiple access (TDMA) method, a new algorithm called ant colony for link scheduling in mesh networks (ALSM) based on Ant Colony algorithm is proposed which reduces the possibility of collision to zero by scheduling links. In this algorithm, we will try to size super frames and assign each link to a time slot in such a way that limitations are satisfied and finally, the end-to-end latency is minimized. In multi-input multi-output (MIMO) networks, we face two types of interference (weak and strong). In ALSM, the ant colony has been modified in such a way that the optimal timing of the links can be obtained by considering these two types of interferences. Our results show that ALSM algorithm can schedule links with shorter super frames compared to other recent algorithms.

References:

[1] F. Aghaei, A. Avokh, “MRCSC: A cross-layer algorithm for joint multicast routing, channel selection, scheduling, and call admission control in multi-cell multi-channel multi-radio cognitive radio wireless networks”, Pervasive and Mobile Computing, vol. 64, Article Number: 101150, April 2020 (doi: 10.101­6/j.pm­cj.2020.101150).‏

[2] A. Avokh, G. Mirjalily, “Performance analysis of broadcasting in small-scale multi-radio multi-channel wireless mesh networks”, Proceeding of the IEEE/ICACT, pp. 537-542, PyeongChang, Korea (South), Feb 2012.

[3] Y. Chai, X.J. Zeng, “A multi-objective dyna-Q based routing in wireless mesh network”, Applied Soft Computing, vol. 108, Article Number: 107486, Sept. 2021 (doi: 10.1016/j.asoc.2021.107486).

[4] R. Vijayanand, D. Devaraj, “A novel feature selection method using whale optimization algorithm and genetic operators for intrusion detection system in wireless mesh network”, IEEE Access, vol. 8, pp. 56847-56854, March 2020 (doi: 10.1109/ACCESS.2020.2978035).

[5] X. Jiang, H. Zhang, E.A.B. Yi, N. Raghunathan, C. Mousoulis, S. Chaterji, S. Bagchi, “Hybrid low-power wide-area mesh network for iot applications”, IEEE Internet of Things Journal, vol. 8, no. 2, pp. 901-915, Jan. 2021 (doi: 10.1109/JIOT.2020.3009228).

[6] X. Feng, J. Qian, “Architecture of wireless multimedia mesh network nodes for longwall coal mine automation”, Proceeding of the IEEE/ICIC, pp. 42-45, Wuxi, China, June 2010 (doi: 10.1109/ICIC.2010.104).

[7] A. Avokh, G. Mirjalily, J. Abouei, S. Valaee, “On the relationship between multicast/broadcast throughput and resource utilizations in wireless mesh networks”, The Scientific World Journal, vol. 2013, Article Number: 794549, Nov. 2013 (doi: 10.1155/2013/794549 ).‏

[8] B. Mumey, J. Tang, T. Hahn, “Joint stream control and scheduling in multihop wireless networks with MIMO links”, Proceeding of the IEEE /ICC, pp. 2921-2925, Xiamen, China , May 2008 (doi: 10.1109/ICC.2008.550).

[9] B. Mumey, J. Tang, T. Hahn, “Algorithmic aspects of communications in multihop wireless networks with MIMO links”, Proceeding of the IEEE /ICC, pp. 1-6, Cape Town, South Africa, May 2010 (doi: 10.1109/ICC.201­0.55­02358).

[10]  L. Wabg, “Link scheduling in multi-transmit-receive wireless mesh networks”, PhD Thesis, University of Wollongong, July 2015.

[11]  M.lee, G.Yu, G. Ye Li, “Graph embedding-based wireless link scheduling with few training samples”, IEEE Trans. on Wireless Communications, vol. 20, no. 4, pp. 2282-2294, April 2020 (doi: 10.1109/TWC.20­20.30­40­983).

[12]  V. Gabale, B. Raman, P .Dutta, S. Kalyanraman, “A classification framework for scheduling algorithms in wireless mesh networks”, IEEE Communications Surveys and Tutorials, vol. 15, no. 1, pp. 199-222, 2013 (doi: 10.1109/SURV.2012.022412.00068).‏‏

[13] D. M Blough, G. Resta, P. Santi, R. Srinivasan, L. M. Cortes-Pena, “Optimal one-shot scheduling for MIMO networks”, Proceeding of the IEEE/SECON, pp. 404-412, Salt Lake City, UT, USA, June 2011 (doi: 10.1109/SAHCN.2011.5984924).

[14] M. Dorigo, M. Birattari, T.Stutzle, “Ant colony optimization”, IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28-39, Nov. 2006 (doi: 10.1109/MCI.2006.329691).‏

[15] R. Ramamoorthy, M. Thangavelu, “An enhanced hybrid ant colony optimization routing protocol for vehicular ad-hoc networks”, Journal of Ambient Intelligence and Humanized Computing, vol. 13, no.8, pp.3837-3868, April 2021 (doi: 10.1007/s12652-021-03176-y).‏

[16] Y. Wang, J. Chen, W. Ning, H. Yu, S. Lin, Z. Wang, C. Chen, “A time-sensitive network scheduling algorithm based on improved ant colony optimization”, Alexandria Engineering Journal, vol. 60, no. 1, pp. 107-114, Feb. 2021 (doi: 10.1016/j.aej.2020.06.013).‏

[17] T. WANG, Z. Mi, “Design of intelligent building scheduling system for internet of things and cloud computing”, Scalable Computing: Practice and Experience, vol. 22, no. 2, pp. 183–192, Oct 2021 (doi: 10.12694/scpe.v22i2.1883). ‏

[18] P. Cappanera, L. Lenzini, A. Lori, G. Stea, G. Vaglini, “ Link scheduling with end-to-end delay constraints in wireless mesh networks”, Proceeding of the WoWMoM, pp. 1-9, Kos Island, Greece, June 2009 (doi: 10.1109/WOWMOM.2009.5282472).

[19] C. Shepard, H. Yu, L. Zhong, “ArgosV2: A flexible many-antenna research platform”, Proceedings of the MOBICOM, pp. 163-166, Miami, USA, Sept. 2013 (doi: 10.1145/2500423.2505302).

[20] X. Zhanyuan; C. Wei, “A joint channel and queue aware scheduling method for multi-user massive MIMO systems”, Proceeding of the IEEE/ICC, pp. 1-6, Shanghai, China, May 2019 (doi: 10.1109/ICC.201­9.8­76­1587).‏

[21] K. Sundaresan, M. A. Ingram, “Medium access control in ad hoc networks with MIMO links: Optimization considerations and algorithms”, IEEE Trans. on Mobile Computing, vol. 3, no. 4, pp. 350-365, Oct 2004 (doi: 10.1109/TMC.2004.42).

[22] L.Badia, A.Botta, L.Lenzini, “A genetic approach to joint routing and link scheduling for wireless mesh networks”, Ad Hoc Networks, vol. 7, no. 4, pp. 654-664, June 2009 (doi:10.1016/j.adhoc.2008.04.005).‏

[23] X. Deng, J. Luo, L. He, Q. Liu, X. Li, L. Cai, “Cooperative channel allocation and scheduling in multi-interface wireless mesh networks”, Peer-to-peer Networking and Applications, vol. 12, no. 1, pp. 1-12, Nov 2017 (doi:10.1007/s12083-017-0619-8)

[24] B. Gurashish, D. Blough, P. Santi, “Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks”, Proceedings of the AICMCN, pp. 2-13, Los Angeles CA USA, Sep 2006 (doi: 10.1145/1161089.1161092).

[25] R. Shu, H. Yi, L. Liu, D. Liu, “A queue-length and collision-risk-prediction based scheduling for wireless mesh networks”, Proceeding of the IEEE/ICTC, pp. 70-74, Nanjing, China, May 2020 (doi: 10.1109/ICTC49­638­.2­020.9123263).‏

[26] X. Li, X. Yu, T. Sun, J. Guo, J. Zhang, “Joint Scheduling and Deep Learning-Based Beamforming for FD-MIMO Systems Over Correlated Rician Fading”, IEEE Access, vol. 7, pp. 118297– 118309, Aug 2019 (doi: 10.1­109/ACCESS.2019.2936880).

[27] Y. Ren, K.W. Chin, S. Soh, “A novel degree of freedom (DoF) link scheduler for full-duplex wireless local area networks”, IEEE Networking Letters, vol. 2, no. 2, pp. 58-61, March 2020 (doi: 10.1109/LNET.2020.29­83754).‏

[28] G.I. Ricardo, J.D. Rezende, V.C. Barbosa, “Scheduling wireless links in the physical interference model by fractional edge coloring”, IEEE Wireless Communications Letters, vol. 9, pp. 528-532, Dec 2019 (doi: 10.1109/LWC.2019.2961361).‏

[29] W. Cui, K. Shen, W. Yu, “Spatial deep learning for wireless scheduling”, IEEE Journal on Selected Areas in Communications, vol. 37, no. 6, pp. 1248-1261, March 2019 (doi: 10.1109/JSAC.2019.2904352 )‏

[30] H. Fawaz, M.E. Helou, S. Lahoud, K. Khawam, “A reinforcement learning approach to queue-aware scheduling in full-duplex wireless networks”, Computer Networks, vol. 189, Article Number: 107893, April 2021 (doi: 10.1016/j.comnet.2021.107893).‏ ‏

[31] Y. Shi, J. Liu, C. Jiang, C. Gao, Y. T. Hou, “An optimal link layer model for multi-hop MIMO networks”, In: 2011 Proceedings IEEE INFOCOM. IEEE, pp. 1916-1924, Shanghai, China, April 2011 (doi: 10.1109/L­WC­.2019.2­961361).‏

[32] K.A. Downsland, J.M. Thompson, “An improved ant colony optimization heuristic for graph colouring”, Discrete Applied Mathematics, vol. 156, no. 3, pp. 313-324, Feb 2008 (doi: 10.1016/j.dam.2007.03.025).‏

[33] J. Wu, D. Lin, G. Li, Y. Liu, Y. Yin, “Distributed link scheduling algorithm based on successive interference cancellation in MIMO wireless networks”, Wireless Communications and Mobile Computing, vol. 2019, Article Number: 9083282, June 2019 (doi: 10.1155/2019/9083282).‏

[34] L.M. Cortés-Pena, D.M. Blough, “MIMO link scheduling for interference suppression in dense wireless networks”, Proceeding of the IEEE/WCNC, pp. 1225-1230, New Orleans, LA, USA, March 2015 (doi: 10.1109/WCNC.2015.7127644)‏.