{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T22:15:28Z","timestamp":1774304128213,"version":"3.50.1"},"reference-count":57,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2025,8,8]],"date-time":"2025-08-08T00:00:00Z","timestamp":1754611200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Future Internet"],"abstract":"<jats:p>This paper proposes a technique to estimate the minimal quantity of orthogonal channel resources required for ad hoc and sensor network connectivity. Simultaneously, the resource allocation to each specific line is conducted by grouping lines into concurrent transmission sets. Our proposed technique uses the physical-based interference model assumption, where each node interferes with every other node, turning ad hoc and sensor network performance optimization problems into the NP-hard ones. In contrast to most of the other works with the physical-based interference model assumption, we mitigate the combinatorial explosion of concurrently transmitting line sets considering the global interference instead of localizing the interference with line or space partitioning. We have performed the mitigation, firstly, using pairwise mutually acceptable line sets for each line. Then, based on the limitations of pairwise sets, we construct the tree of mutually acceptable interfering line sets. Then, from the created tree, we find the minimal set cover of concurrently transmitting line sets. The tree construction has the exponential worst-case time and space complexity if all lines in the network can transmit together. By randomly pruning the tree and using the genetic algorithm to find the pruned tree which gives the same minimal set cover as the full tree, we have reduced the worst space and time complexities to the polynomial ones. We have devised our technique with parallelism in mind to speed up the resource allocation optimization even more. Based on an extensive simulation study with random network topologies of sizes up to 250 nodes and the average number of lines up to 2000, we estimated the time and space complexity for different tree pruning and optimization techniques and found the effective ones.<\/jats:p>","DOI":"10.3390\/fi17080362","type":"journal-article","created":{"date-parts":[[2025,8,8]],"date-time":"2025-08-08T11:41:53Z","timestamp":1754653313000},"page":"362","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Parallel Algorithm for NP-Hard Problem of Channel Resource Allocation Optimization in Ad Hoc and Sensor Networks"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-3297-4793","authenticated-orcid":false,"given":"Valeriy","family":"Ivanov","sequence":"first","affiliation":[{"name":"Science and Research Department, Moscow Technical University of Communications and Informatics, 111024 Moscow, Russia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1330-281X","authenticated-orcid":false,"given":"Maxim","family":"Tereshonok","sequence":"additional","affiliation":[{"name":"Science and Research Department, Moscow Technical University of Communications and Informatics, 111024 Moscow, Russia"}]}],"member":"1968","published-online":{"date-parts":[[2025,8,8]]},"reference":[{"key":"ref_1","unstructured":"Hekmat, R. (2006). Ad-Hoc Networks: Fundamental Properties and Network Topologies, Springer Science & Business Media."},{"key":"ref_2","unstructured":"Karl, H., and Willig, A. (2007). Protocols and Architectures for Wireless Sensor Networks, John Wiley & Sons."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Sarangapani, J. (2017). Wireless Ad Hoc and Sensor Networks: Protocols, Performance, and Control, CRC Press.","DOI":"10.1201\/9781420015317"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Li, J., Blake, C., De Couto, D.S., Lee, H.I., and Morris, R. (2001, January 16). Capacity of ad hoc wireless networks. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, Rome, Italy.","DOI":"10.1145\/381677.381684"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1109\/TWC.2003.814342","article-title":"Capacity regions for wireless ad hoc networks","volume":"2","author":"Toumpis","year":"2003","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_6","unstructured":"Toumpis, S., and Goldsmith, A. (November, January 29). Ad hoc network capacity. Proceedings of the Conference Record of the Thirty-Fourth Asilomar Conference on Signals, Systems and Computers (Cat. No. 00CH37154), Pacific Grove, CA, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Li, X.Y., Tang, S.J., and Frieder, O. (2007, January 9\u201314). Multicast Capacity for Large Scale Wireless ad Hoc Networks. Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, Montreal, QC, Canada.","DOI":"10.1145\/1287853.1287886"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1109\/TNET.2002.801403","article-title":"Mobility increases the capacity of ad hoc wireless networks","volume":"10","author":"Grossglauser","year":"2002","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_9","unstructured":"Spyropoulos, A., and Raghavendra, C.S. (2003, January 11\u201315). Capacity bounds for ad-hoc networks using directional antennas. Proceedings of the IEEE International Conference on Communications (ICC\u201903), Anchorage, AK, USA."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1374","DOI":"10.1109\/TMC.2010.243","article-title":"The capacity of wireless ad hoc networks using directional antennas","volume":"10","author":"Li","year":"2010","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"5058","DOI":"10.1109\/T-WC.2008.071047","article-title":"Transmission capacity of ad hoc networks with spatial diversity","volume":"7","author":"Hunter","year":"2008","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1032","DOI":"10.1109\/TWC.2011.020111.100528","article-title":"On the asymptotic capacity of multi-hop MIMO ad hoc networks","volume":"10","author":"Jiang","year":"2011","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Liu, B., Thiran, P., and Towsley, D. (2007, January 9\u201314). Capacity of a wireless ad hoc network with infrastructure. Proceedings of the 8th ACM International Symposium on MOBILE ad Hoc Networking and Computing, Montreal, QC, Canada.","DOI":"10.1145\/1288107.1288140"},{"key":"ref_14","unstructured":"Lin, X., and Shroff, N.B. (2004, January 27\u201330). The fundamental capacity-delay tradeoff in large mobile ad hoc networks. Proceedings of the Third Annual Mediterranean Ad Hoc Networking Workshop, Bodrum, Turkey."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2061","DOI":"10.1109\/TWC.2006.1687721","article-title":"On the capacity of mobile ad hoc networks with delay constraints","volume":"5","author":"Comaniciu","year":"2006","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1917","DOI":"10.1109\/TIT.2005.847717","article-title":"Capacity and delay tradeoffs for ad hoc mobile networks","volume":"51","author":"Neely","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1137","DOI":"10.1109\/TNET.2010.2103367","article-title":"Network capacity region and minimum energy function for a delay-tolerant mobile ad hoc network","volume":"19","author":"Urgaonkar","year":"2011","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Garcia-Luna-Aceves, J., Sadjadpour, H.R., and Wang, Z. (2007, January 9\u201311). Challenges: Towards truly scalable ad hoc networks. Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, Montreal, QC, Canada.","DOI":"10.1145\/1287853.1287878"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Garcia-Luna-Aceves, J., Sadjadpour, H.R., and Wang, Z. (2007, January 21\u201325). Extending the capacity of ad hoc networks beyond network coding. Proceedings of the 2007 International Conference on Wireless Communications and Mobile Computing, Shanghai, China.","DOI":"10.1145\/1280940.1280960"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"4193","DOI":"10.1109\/TWC.2007.05499","article-title":"Maximum flow and network capacity of network coding for ad-hoc networks","volume":"6","author":"Wang","year":"2007","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Isaac, R.A., Sundaravadivel, P., Marx, V.N., and Priyanga, G. (2025). Enhanced novelty approaches for resource allocation model for multi-cloud environment in vehicular Ad-Hoc networks. Sci. Rep., 15.","DOI":"10.1038\/s41598-025-93365-y"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"36527","DOI":"10.1109\/ACCESS.2019.2904673","article-title":"Robust cross-layer routing and radio resource allocation in massive multiple antenna and OFDMA-based wireless ad-hoc networks","volume":"7","author":"Kordbacheh","year":"2019","journal-title":"IEEE Access"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2187","DOI":"10.1109\/TVT.2023.3315735","article-title":"Resource allocation for joint communication and positioning in mmWave ad hoc networks","volume":"73","author":"Luo","year":"2023","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1109\/TGCN.2023.3234165","article-title":"Starling flocks-inspired resource allocation for ISAC-aided green ad hoc networks","volume":"7","author":"Wang","year":"2023","journal-title":"IEEE Trans. Green Commun. Netw."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"6632","DOI":"10.1109\/JLT.2024.3411886","article-title":"SRS-proactive-aware resource allocation based on all-optical wavelength converters in C+ L band optical networks","volume":"42","author":"Teng","year":"2024","journal-title":"J. Light. Technol."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Wang, J., and Jiang, C. (2022). Flying ad Hoc Networks: Cooperative Networking and Resource Allocation, Springer Nature.","DOI":"10.1007\/978-981-16-8850-8"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"73790","DOI":"10.1109\/ACCESS.2019.2921075","article-title":"Resource allocation for performance enhancement in mobile ad hoc networks","volume":"7","author":"Liu","year":"2019","journal-title":"IEEE Access"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"109807","DOI":"10.1016\/j.comnet.2023.109807","article-title":"Machine learning empowered computer networks","volume":"230","author":"Cerquitelli","year":"2023","journal-title":"Comput. Netw."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2145","DOI":"10.1109\/TNET.2022.3164869","article-title":"Multi-associated parameters aggregation-based routing and resources allocation in multi-core elastic optical networks","volume":"30","author":"Yang","year":"2022","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Sun, Z., Yang, H., Li, C., Yao, Q., Teng, Y., Zhang, J., Liu, S., Li, Y., and Vasilakos, A.V. (2024). A resource allocation scheme for edge computing network in smart city based on attention mechanism. ACM Trans. Sens. Netw., 3.","DOI":"10.1145\/3650031"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"3457","DOI":"10.1109\/TCOMM.2019.2894711","article-title":"Resource assignment based on dynamic fuzzy clustering in elastic optical networks with multi-core fibers","volume":"67","author":"Yang","year":"2019","journal-title":"IEEE Trans. Commun."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"4308","DOI":"10.1109\/JIOT.2018.2853661","article-title":"A machine learning-based algorithm for joint scheduling and power control in wireless networks","volume":"5","author":"Cao","year":"2018","journal-title":"IEEE Internet Things J."},{"key":"ref_33","unstructured":"Shelim, R., and Ibrahim, A.S. (2021). A fast graph kernel based classification method for wireless link scheduling on Riemannian manifold. arXiv."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Lamm, S., Schulz, C., Strash, D., Williger, R., and Zhang, H. (2019). Exactly solving the maximum weight independent set problem on large real-world graphs. 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (Alenex), SIAM.","DOI":"10.1137\/1.9781611975499.12"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"6832","DOI":"10.1109\/OJCOMS.2024.3484948","article-title":"Dynamic link scheduling in wireless networks through fuzzy-enhanced deep learning","volume":"5","author":"Abbasalizadeh","year":"2024","journal-title":"IEEE Open J. Commun. Soc."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"3997","DOI":"10.1109\/TWC.2022.3222781","article-title":"Link scheduling using graph neural networks","volume":"22","author":"Zhao","year":"2022","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Zhao, Z., Verma, G., Swami, A., and Segarra, S. (2022, January 22\u201327). Delay-oriented distributed scheduling using graph neural networks. Proceedings of the ICASSP 2022\u20142022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Singapore.","DOI":"10.1109\/ICASSP43922.2022.9746926"},{"key":"ref_38","unstructured":"Zou, C. (2005, January 11\u201314). Optimal resource allocation for UWB wireless ad hoc networks. Proceedings of the 2005 IEEE 16th International Symposium on Personal, Indoor and Mobile Radio Communications, Berlin, Germany."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"2538","DOI":"10.1007\/s11432-010-4120-8","article-title":"Throughput maximization in UWB-based ad-hoc networks","volume":"53","author":"Zou","year":"2010","journal-title":"Sci. China Inf. Sci."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., and Wattenhofer, R. (2006, January 23\u201329). The complexity of connectivity in wireless networks. Proceedings of the INFOCOM 2006: 25th Annual Joint Conference of the IEEE Computer and Communications Societies, Barcelona, Spain.","DOI":"10.1109\/INFOCOM.2006.23"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"2643","DOI":"10.1109\/TVT.2016.2580379","article-title":"Shortest link scheduling algorithms in wireless networks under the SINR model","volume":"66","author":"Yu","year":"2016","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Wan, P.J., Frieder, O., Jia, X., Yao, F., Xu, X., and Tang, S. (2011). Wireless Link Scheduling Under Physical Interference Model, IEEE.","DOI":"10.1109\/INFCOM.2011.5935307"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1701","DOI":"10.1109\/TNET.2010.2047511","article-title":"Approximation algorithms for wireless link scheduling with SINR-based interference","volume":"18","author":"Blough","year":"2010","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Xu, X., Tang, S., and Wan, P.J. (2010). Maximum weighted independent set of links under physical interference model. Proceedings of the International Conference on Wireless Algorithms, Systems, and Applications, Springer.","DOI":"10.1007\/978-3-642-14654-1_8"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1052","DOI":"10.1007\/s10878-015-9908-4","article-title":"An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models","volume":"32","author":"Wang","year":"2016","journal-title":"J. Comb. Optim."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.jnca.2016.10.012","article-title":"SINR based shortest link scheduling with oblivious power control in wireless networks","volume":"77","author":"Huang","year":"2017","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"397962","DOI":"10.1155\/WCN.2005.554","article-title":"Throughput analysis of fading sensor networks with regular and random topologies","volume":"2005","author":"Liu","year":"2005","journal-title":"EURASIP J. Wirel. Commun. Netw."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"2134","DOI":"10.1109\/COMST.2018.2867268","article-title":"Resource allocation for ultra-dense networks: A survey, some research issues and challenges","volume":"21","author":"Teng","year":"2018","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"102978","DOI":"10.1016\/j.adhoc.2022.102978","article-title":"Survey on the state-of-the-art in device-to-device communication: A resource allocation perspective","volume":"136","author":"Islam","year":"2022","journal-title":"Ad Hoc Netw."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Jaramillo, J.J., and Srikant, R. (2010, January 14\u201319). Optimal scheduling for fair resource allocation in ad hoc networks with elastic and inelastic traffic. Proceedings of the 2010 Proceedings IEEE INFOCOM, San Diego, CA, USA.","DOI":"10.1109\/INFCOM.2010.5462048"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1109\/13.168713","article-title":"Baseband equivalents in digital communication system simulation","volume":"35","author":"Zhang","year":"1992","journal-title":"IEEE Trans. Educ."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","article-title":"On the computational complexity of combinatorial problems","volume":"5","author":"Karp","year":"1975","journal-title":"Networks"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1287\/opre.47.5.730","article-title":"A heuristic method for the set covering problem","volume":"47","author":"Caprara","year":"1999","journal-title":"Oper. Res."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Peng, R., and Tangwongsan, K. (2011, January 4\u20136). Linear-work greedy parallel approximate set cover and variants. Proceedings of the Twenty-Third Annual ACM Symposium on PARALLELISM in Algorithms and Architectures, San Jose, CA, USA.","DOI":"10.1145\/1989493.1989497"},{"key":"ref_55","unstructured":"Sekar, S., and Reggia, J. (1988, January 14\u201318). Parallel set covering algorithms. Proceedings of the Fourth Conference on Artificial Intelligence Applications, San Diego, CA, USA."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1109\/TEVC.2015.2511142","article-title":"Kuhn\u2013Munkres parallel genetic algorithm for the set cover problem and its application to large-scale wireless sensor networks","volume":"20","author":"Zhang","year":"2015","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"Koufogiannakis, C., and Young, N.E. (2009, January 10). Distributed and parallel algorithms for weighted vertex cover and other covering problems. Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, Calgary, AB, Canada.","DOI":"10.1145\/1582716.1582746"}],"container-title":["Future Internet"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-5903\/17\/8\/362\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:26:22Z","timestamp":1760034382000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-5903\/17\/8\/362"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,8]]},"references-count":57,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2025,8]]}},"alternative-id":["fi17080362"],"URL":"https:\/\/doi.org\/10.3390\/fi17080362","relation":{},"ISSN":["1999-5903"],"issn-type":[{"value":"1999-5903","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,8]]}}}