On the time complexity of achieving optimal throughput in time division multiple access communication networks

Samer Nofal; Samer Nofal

doi:10.3934/math.2024659

AIMS Mathematics

2024, Volume 9, Issue 5: 13522-13536. doi: 10.3934/math.2024659

Previous Article Next Article

Research article

On the time complexity of achieving optimal throughput in time division multiple access communication networks

Samer Nofal ^,

Department of Computer Science, German Jordanian University, Amman, Jordan

Received: 22 February 2024 Revised: 26 March 2024 Accepted: 03 April 2024 Published: 12 April 2024
MSC : 05C20, 05C85

The fundamental problem of finding transmission schedules for achieving optimal throughput in time division multiple access (TDMA) communication networks is known to be NP-hard. Let $ \mathcal{N} $ be a scheduled $ k $-time slot TDMA network with $ n $ stations and $ m $ links. We showed that an optimal link schedule for $ \mathcal{N} $ can be computed recursively with a recursion tree of logarithmic depth $ \mathcal{O}(\ln m) $ in expectation. Additionally, we showed that optimal link schedules for those TDMA networks, with recursion trees of depth meeting the expectation, can be found in time $ \mathcal{O}(m^{2+\ln k}) $. Likewise, we discuss analogous results for computing optimal station schedules of TDMA networks.
- time complexity,
- expected depth of recursion tree,
- exact scheduling,
- optimal throughput,
- time division multiple access,
- communication networks
Citation: Samer Nofal. On the time complexity of achieving optimal throughput in time division multiple access communication networks[J]. AIMS Mathematics, 2024, 9(5): 13522-13536. doi: 10.3934/math.2024659

Related Papers:

Abstract

The fundamental problem of finding transmission schedules for achieving optimal throughput in time division multiple access (TDMA) communication networks is known to be NP-hard. Let $ \mathcal{N} $ be a scheduled $ k $-time slot TDMA network with $ n $ stations and $ m $ links. We showed that an optimal link schedule for $ \mathcal{N} $ can be computed recursively with a recursion tree of logarithmic depth $ \mathcal{O}(\ln m) $ in expectation. Additionally, we showed that optimal link schedules for those TDMA networks, with recursion trees of depth meeting the expectation, can be found in time $ \mathcal{O}(m^{2+\ln k}) $. Likewise, we discuss analogous results for computing optimal station schedules of TDMA networks.

References

[1]	P. Adasme, F. Seguel, I. Soto, E. S. Juan, Spatial time division multiple access for visible light communication networks, 2017 First South American Colloquium on Visible Light Communications (SACVLC), Santiago, Chile, 2017, 1–6. https://doi.org/10.1109/SACVLC.2017.8267605
[2]	S. R. Akbar, M. H. H. Ichsan, A. A. Darmawan, Reference broadcast synchronization and time division multiple access implementation on WSN, Telkomnika (Telecommunication Computing Electronics and Control), 17 (2019), 291–298. http://doi.org/10.12928/telkomnika.v17i1.11615 doi: 10.12928/telkomnika.v17i1.11615
[3]	S. Andersson, B. Hagerman, M. Berg, H. Dam, U. Forssen, J. Karlsson, et al., Adaptive antennas for global system for mobile communications and time division multiple access (interim standard-136) systems, In: Handbook of antennas in wireless communications, Boca Raton: CRC Press, 2002, https://doi.org/10.1201/9781315220031
[4]	E. Arikan, Some complexity results about packet radio networks (Corresp.), IEEE T. Inform. Theory, 30 (1984), 681–685. https://doi.org/10.1109/TIT.1984.1056928 doi: 10.1109/TIT.1984.1056928
[5]	X. Chen, W. S. Hu, D. Feng, Direct-sequence spread spectrum time division multiple access with direct detection for latency optimized passive optical network, Opt. Commun., 510 (2022), 127955. https://doi.org/10.1016/j.optcom.2022.127955 doi: 10.1016/j.optcom.2022.127955
[6]	S. Even, O. Goldreich, S. Moran, P. Tong, On the np-completeness of certain network testing problems, Networks, 14 (1984), 1–24. https://doi.org/10.1002/net.3230140102 doi: 10.1002/net.3230140102
[7]	N. Fahier, W. C. Fang, An HBC-based biosensor transmitter for time division multiple access network, 2017 IEEE International Conference on Consumer Electronics-Taiwan (ICCETW), Taipei, Taiwan, 2017,161–162. https://doi.org/10.1109/ICCE-China.2017.7991045
[8]	H. Falsafain, M. R. Heidarpour, S. Vahidi, A branch-and-price approach to a variant of the cognitive radio resource allocation problem, Ad Hoc Netw., 132 (2022), 102871. https://doi.org/10.1016/j.adhoc.2022.102871 doi: 10.1016/j.adhoc.2022.102871
[9]	S. Faruque, Time division multiple access (TDMA), In: Radio frequency multiple access techniques made easy, Cham: Springer, 2019, 35–43. https://doi.org/10.1007/978-3-319-91651-4_4
[10]	X. Fernando, G. Lazaroiu, Spectrum sensing, clustering algorithms, and energyharvesting technology for cognitive-radio-based internet-of-things networks, Sensors, 23 (2023), 7792. https://doi.org/10.3390/s23187792 doi: 10.3390/s23187792
[11]	C. V. Giriraja, V. Chirag, C. Sudheendra, S. S. Bellur, T. K. Ramesh, K. N. Meera, Priority based time-division multiple access algorithm for medium range data communication in very high frequency radios, J. Comput. Theor. Nanos., 17 (2020), 290–296. https://doi.org/10.1166/jctn.2020.8664 doi: 10.1166/jctn.2020.8664
[12]	C. Goswami, P. Sharma, R. Bharati, K. C. Rajheshwari, L. P. Maguluri, M. Elangovan, Algorithms for high mobility environment in 5g radio access networks with millimeter wave communications, Opt. Quant. Electron., 56 (2024), 276. https://doi.org/10.1007/s11082-023-05858-7 doi: 10.1007/s11082-023-05858-7
[13]	S. D. Ilcev, Analyses of time division multiple access (TDMA) schemes for global mobile satellite communications (GMSC), International Journal on Marine Navigation and Safety od Sea Transportation, 14 (2020), 831–837. http://doi.org/10.12716/1001.14.04.06 doi: 10.12716/1001.14.04.06
[14]	Y. H. Kwon, J. H. Cha, D. S. Kim, Design and performance analysis of asymmetric time division multiple access method for improving response time and throughput in tactical radio communication, Journal of the Korea Institute of Military Science and Technology, 21 (2018), 361–369. https://doi.org/10.9766/KIMST.2018.21.3.361 doi: 10.9766/KIMST.2018.21.3.361
[15]	J. Lee, W. C. Jeong, B. C. Choi, Multi-channel time division multiple access time slot scheduling with link recovery for multi-hop wireless sensor networks, Int. J. Distrib. Sens. N., 13 (2017), 1550147717726311. https://doi.org/10.1177/1550147717726311 doi: 10.1177/1550147717726311
[16]	C. Li, Z. Y. Xu, J. Y. Wang, J. Y. Zhao, A. L. Qi, J. H. Li, Ultraviolet random access collaborative networking protocol based on time division multiple access, J. Opt. Commun. Netw., 15 (2023), 393–403. https://doi.org/10.1364/JOCN.479471 doi: 10.1364/JOCN.479471
[17]	Y. Liang, P. P. Wen, H. X. Wang, Z. F. Zhao, An improved time division multiple access protocol in UWSN, 2017 International Conference on Mechanical, Electronic, Control and Automation Engineering (MECAE 2017), Beijing, China, 2017,208–213. https://doi.org/10.2991/mecae-17.2017.39
[18]	J. H. Luo, L. Y. Fan, S. Wu, X. T. Yan, Research on localization algorithms based on acoustic communication for underwater sensor networks, Sensors, 18 (2017), 67. https://doi.org/10.3390/s18010067 doi: 10.3390/s18010067
[19]	K. H. Mohammadani, K. A. Memon, I. Memon, N. N. Hussaini, H. Fazal, Preamble time-division multiple access fixed slot assignment protocol for secure mobile ad hoc networks, Int. J. Distrib. Sens. N., 16 (2020), 1550147720921624. https://doi.org/10.1177/1550147720921624 doi: 10.1177/1550147720921624
[20]	H. Mokari, E. Firouzmand, I. Sharifi, A. Doustmohammadi, Deception attack detection and resilient control in platoon of smart vehicles, 2022 30th International conference on electrical engineering (ICEE), Tehran, Iran, Islamic Republic, 2022, 29–35. https://doi.org/10.1109/ICEE55646.2022.9827376
[21]	H. Mokari, E. Firouzmand, I. Sharifi, A. Doustmohammadi, Resilient control strategy and attack detection on platooning of smart vehicles under DoS attack, ISA T., 144 (2024), 51–60. https://doi.org/10.1016/j.isatra.2023.11.019 doi: 10.1016/j.isatra.2023.11.019
[22]	A. A. Monterrosas, W. D. Kight, E. Gunduzhan, D. M. Coleman, A selfsynchronizing time-division multiple-access network protocol, 2019 Wireless Telecommunications Symposium (WTS), New York, USA, 2019, 1–5. https://doi.org/10.1109/WTS.2019.8715529
[23]	S. Ramanathan, E. L. Lloyd, Scheduling algorithms for multihop radio networks, IEEE-ACM T. Network., 1 (1993), 166–177. https://doi.org/10.1109/90.222924 doi: 10.1109/90.222924
[24]	M. R. Rezaee, N. A. W. A. Hamid, M. Hussin, Z. A. Zukarnain, Fog offloading and task management in iot-fog-cloud environment: Review of algorithms, networks and SDN application, IEEE Access, 12 2024, 39058–39080. http://doi.org/10.1109/ACCESS.2024.3375368 doi: 10.1109/ACCESS.2024.3375368
[25]	L. Rocha, D. Sasaki, The backbone packet radio network coloring for time division multiple access link scheduling in wireless multihop networks, Networks, 71 (2018), 403–411. https://doi.org/10.1002/net.21767 doi: 10.1002/net.21767
[26]	B. Schieber, B. Samineni, S. Vahidi, Interweaving real-time jobs with energy harvesting to maximize throughput, In: WALCOM: Algorithms and Computation, Cham: Springer, 2023,305–316. https://doi.org/10.1007/978-3-031-27051-2_26
[27]	G. Sebestyen, J. Kopiak, Assessing the stability of time-division multiple access (TDMA) mesh networks through flooding route selection, 2023 IEEE 21st Jubilee International Symposium on Intelligent Systems and Informatics (SISY), Pula, Croatia, 2023, 000649–000652. https://doi.org/10.1109/SISY60376.2023.10417892
[28]	S. Sharma, V. Kumar, K. Dutta, Multi-objective optimization algorithms for intrusion detection in iot networks: A systematic review, Internet of Things and Cyber-Physical Systems, 4 (2024), 258–267. https://doi.org/10.1016/j.iotcps.2024.01.003 doi: 10.1016/j.iotcps.2024.01.003
[29]	E. Shayo, P. Mafole, A. Mwambela, A survey on time division multiple access scheduling algorithms for industrial networks, SN Appl. Sci., 2 (2020), 2140. https://doi.org/10.1007/s42452-020-03923-4 doi: 10.1007/s42452-020-03923-4
[30]	M. Shwetha, S. Krishnaveni, A systematic analysis, outstanding challenges, and future prospects for routing protocols and machine learning algorithms in underwater wireless acoustic sensor networks, J. Interconnect. Netw., 2024 (2024), 2330001. https://doi.org/10.1142/S0219265923300015 doi: 10.1142/S0219265923300015
[31]	H. Son, C. Jeong, Virtual mimo beamforming for opportunistic cooperative time division multiple access, IEEE T. Commun., 68 (2020), 7521–7532. https://doi.org/10.1109/TCOMM.2020.3019287 doi: 10.1109/TCOMM.2020.3019287
[32]	H. Son, B. Kwon, Ris-assisted cooperative time-division multiple access, Sensors, 24 (2023), 178. https://doi.org/10.3390/s24010178 doi: 10.3390/s24010178
[33]	Y. X. Sun, Z. H. Zhang, X. P. Li, S. Xiao, W. B. Tang, An extensible frame structure for time division multiple access medium access control in vehicular ad-hoc networks, T. Emerg. Telecommun. T., 31 (2020), e3912. https://doi.org/10.1002/ett.3912 doi: 10.1002/ett.3912
[34]	A. B. Tambawal, R. M. Noor, R. Salleh, C. Chembe, M. H. Anisi, O. Michael, et al., Time division multiple access scheduling strategies for emerging vehicular ad hoc network medium access control protocols: a survey, Telecommun. Syst., 70 (2019), 595–616. https://doi.org/10.1007/s11235-018-00542-8 doi: 10.1007/s11235-018-00542-8
[35]	P. Tirandazi, A. Rahiminasab, M. Ebadi, An efficient coverage and connectivity algorithm based on mobile robots for wireless sensor networks, J. Ambient Intell. Human. Comput., 14 (2023), 8291–8313. https://doi.org/10.1007/s12652-021-03597-9 doi: 10.1007/s12652-021-03597-9
[36]	S. Wang, Y. C. Wang, D. Y. Li, Q. C. Zhao, Distributed relative localization algorithms for multi-robot networks: a survey, Sensors, 23 (2023), 2399. https://doi.org/10.3390/s23052399 doi: 10.3390/s23052399
[37]	A. Wood, T. Upthegrove, C. Funai, B. Thapa, S. Loos, D. Javorsek, Pulsenet: A discriminative model for time division multiple access time slot prediction, MILCOM 2022-2022 IEEE Military Communications Conference (MILCOM), Rockville, MD, USA, 2022, 1–6. https://doi.org/10.1109/MILCOM55135.2022.10017899
[38]	J. Wu, L. Yu, F. F. Gou, Data transmission scheme based on node model training and time division multiple access with iot in opportunistic social networks, Peer-to-Peer Netw. Appl., 15 (2022), 2719–2743. https://doi.org/10.1007/s12083-022-01365-w doi: 10.1007/s12083-022-01365-w
[39]	A. Yaman, T. van der Lee, G. Iacca, Online distributed evolutionary optimization of time division multiple access protocols, Expert Syst. Appl., 211 (2023), 118627. https://doi.org/10.1016/j.eswa.2022.118627 doi: 10.1016/j.eswa.2022.118627
[40]	Z. J. Yan, Q. Q. Li, B. Li, M. Yang, A link distance division based time division multiple access protocol for directional aeronautical relay networks, Journal of Northwestern Polytechnical University, 38 (2020), 147–154. http://doi.org/10.1051/jnwpu/20203810147 doi: 10.1051/jnwpu/20203810147

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)