ارائه یک الگوریتم جدید برای زمان‌بندی پیوند شبکه‌های توری بی‌سیم چند ورودی-چند خروجی با تداخل متفاوت بر مبنای کلونی مورچگان

محورهای موضوعی : شبکه های مخابرات

صادق زرمهی ¹ , سید محمود دانشور فرزانگان ² , آوید آوخ ³

1 - دانشکده مهندسی برق- واحد نجف‌آباد، دانشگاه آزاد اسلامی، نجف‌آباد، ایران
2 - مرکز تحقیقات ریز شبکه‌های هوشمند- واحد نجف‌آباد، دانشگاه آزاد اسلامی، نجف‌آباد، ایران
3 - مرکز تحقیقات پردازش دیجیتال و بینایی ماشین- واحد نجف آباد، دانشگاه آزاد اسلامی، نجف آباد، ایران

تاریخ دریافت : 1401/05/18 تاریخ پذیرش : 1401/07/24 تاریخ انتشار : 1403/06/01

کلید واژه: الگوریتم کلونی مورچگان, تداخل ضعیف و قوی, زمان‌بندی پیوند, شبکه‌ توری بی‌سیم, آنتن چندورودی-چندخروجی,

چکیده مقاله :

اگر چه شبکه‌های بی‌سیم نسل جدید از نظر هزینه‌ی نصب و توسعه، فن‌آوری مناسبی برای زیرساخت اینترنت محسوب می‌شوند، ولی به ‌دلیل محدودیت در ظرفیت و مقیاس ‌پذیری، چالش‌های زیادی را مانند زمان‌بندی پیوند و مسیر‌یابی به دنبال دارند. در این مقاله، با تمرکز بر روش دسترسی چندگانه تقسیم زمانی الگوریتم جدیدی با عنوان کلونی مورچه ها برای زمانبندی پیوند در شبکه های مش (ALSM) بر مبنای رنگ آمیزی گراف و الگوریتم کلونی مورچگان ارائه شده که با زمان‌بندی پیوندها امکان تصادم را به صفر می‌رساند. در این الگوریتم سعی خواهد شد اندازه ابرقاب‌ها و اختصاص هر پیوند به یک شکاف‌ زمانی به گونه‌ای باشد که با توجه به محدودیت‌ تداخل پیوندها و نیز درجه آزادی آنتن‌های مورد استفاده برای ارسال یا دریافت، تأخیر انتها به انتها کاهش و ظرفیت شبکه افزایش یابد. در شبکه‌های توری بی‌سیم چند ورودی-چند خروجی دو نوع تداخل (تداخل ضعیف و قوی) وجود دارد. در ALSM، الگوریتم کلونی مورچگان به گونه‌ای اصلاح شده که بتوان با در نظر گرفتن این دو نوع تداخل، زمان‌بندی بهینه پیوندها را به دست آورد. نتایج این تحقیق نشان می‌دهد که الگوریتم ALSM در مقایسه با الگوریتم‌های دیگری که در سال‌های اخیر ارائه شده است با طول ابرفریم کوتاه‌تری می‌تواند زمان‌بندی پیوندها را انجام دهد.

چکیده انگلیسی:

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.

منابع و مأخذ:

[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)‏.