Abstract
In wireless networks, efficiently allocating limited network resources holds significant practical importance. This work focuses on the NP-hard overlap constrained resource allocation problem (OCRAP) in wireless networks. As one of the practical decision-making problems, OCRAP aims to find a subset of candidate wireless resources, each capable of servicing multiple areas, to maximize the profit function while satisfying the given budget and overlap constraints. We have formulated the OCRAP model based on the budgeted maximum coverage problem and propose an effective hybrid evolutionary algorithm (HEA) for solving it. The proposed HEA algorithm combines a tabu search procedure for local optimization with an effective crossover operator to generate promising offspring solutions. We show computational results on 60 benchmark instances and present comparative studies with several heuristic algorithms as well as the general CPLEX solver. We also provide a convergence analysis to further demonstrate the robust performance of the proposed algorithm.
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
Notes
- 1.
Available at: https://github.com/YitingQueen/HEA_results_summary.
References
Abrardo, A., Alessio, A., Detti, P., et al.: Radio resource allocation problems for OFDMA cellular systems. Comput. Oper. Res. 36, 1572–1581 (2009)
Ahmed, I.Z., Sadjadpour, H., Yousefi, S.: Constrained resource allocation problems in communications: an information-assisted approach. In: Proceedings, MILCOM 2021–2021 IEEE Military Communications Conference (MILCOM) (2021)
Bouras, C., Kalogeropoulos, R.: User allocation in 5G networks using machine learning methods for clustering. In: Proceedings, International Conference on Advanced Information Networking and Applications (AINA) (2021)
Capone, A., Carello, G., Filippini, I., et al.: Solving a resource allocation problem in wireless mesh networks: a comparison between a CP-based and a classical column generation. Networks 55, 221–233 (2010)
Dutta, R.N., Ghosh, S.C.: Resource allocation for millimeter wave D2D communications in presence of static obstacles. In: International Conference on Advanced Information Networking and Applications (AINA) (2021)
Falsafain, H., Heidarpour, M.R., Vahidi, S.: A branch-and-price approach to a variant of the cognitive radio resource allocation problem. Ad Hoc Netw. 132, 102871 (2022)
Glover, F., Laguna, M.: Tabu Search. Springer, Heidelberg (1998)
Goldschmidt, O., Nehme, D., Yu, G.: Note: On the set-union knapsack problem. Naval Res. Logist. (NRL) 41, 833–842 (1994)
He, Y., Xie, H., Wong, T.-L., et al.: A novel binary artificial bee colony algorithm for the set-union knapsack problem. Futur. Gener. Comput. Syst. 78, 77–86 (2018)
Kar, B., Wu, E.H.-K., Lin, Y.-D.: The budgeted maximum coverage problem in partially deployed software defined networks. IEEE Trans. Netw. Serv. Manag. 13, 394–406 (2016)
Khuller, S., Moss, A., Naor, J.S.: The budgeted maximum coverage problem. Inf. Process. Lett. 70, 39–45 (1999)
Kia, S.S.: A distributed dynamical solver for an optimal resource allocation problem over networked systems. In: Proceedings, IEEE Conference on Decision and Control (CDC) (2015)
Konnov, I., Kashina, O., Laitinen, E.: Vector resource allocation problems in communication networks. In: Proceedings, Symposium and Workshops on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt) (2013)
Lai, X., Hao, J.-K., Glover, F., et al.: A two-phase tabu-evolutionary algorithm for the 0–1 multidimensional knapsack problem. Inf. Sci. 436, 282–301 (2018)
Letchford, A.N., Ni, Q., Zhong, Z.: An exact algorithm for a resource allocation problem in mobile wireless communications. Comput. Optim. Appl. 68, 193–208 (2017)
Li, L., Wang, D., Li, T., et al.: Scene: a scalable two-stage personalized news recommendation system. In: Proceedings, International ACM SIGIR Conference on Research and Development in Information Retrieval (2011)
Li, L., Wei, Z., Hao, J.-K., et al.: Probability learning based tabu search for the budgeted maximum coverage problem. Expert Syst. Appl. 183, 115310 (2021)
Stanczak, S., Wiczanowski, M., Boche, H,: Fundamentals of Resource Allocation in Wireless Networks: Theory and Algorithms. Springer, Heidelberg (2009)
Suh, K., Guo, Y., Kurose, J., et al.: Locating network monitors: complexity, heuristics, and coverage. Comput. Commun. 29, 1564–1577 (2006)
Vanderster, D.C., Dimopoulos, N.J., Parra-Hernandez, R., et al.: Resource allocation on computational grids using a utility model and the knapsack problem. Futur. Gener. Comput. Syst. 25, 35–50 (2009)
Wang, P., Peng, W., Zhang, W., et al.: Joint channel and power allocation algorithm for flying ad hoc networks based on bayesian optimization. In: Proceedings, International Conference on Advanced Information Networking and Applications (2021)
Wei, Z., Hao, J.-K.: Multistart solution-based tabu search for the Set-Union Knapsack Problem. Appl. Soft Comput. 105, 107260 (2021)
Wei, Z., Hao, J.-K.: Iterated hyperplane search for the budgeted maximum coverage problem. Expert Syst. Appl. 214, 119078 (2023)
Zhou, J., Zheng, J., He, K.: Effective variable depth local search for the budgeted maximum coverage problem. Int. J. Comput. Intell. Syst. 15, 43 (2022)
Acknowledgement
This work is partially supported by the National Natural Science Foundation Program of China (Grant No. 72301036, 62172056). Support from the Research Innovation Fund for College Students and the High-performance Computing Platform of Beijing University of Posts and Telecommunications is also acknowledged.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Wang, Y., Li, Y., Wei, Z., Li, J. (2024). Hybrid Evolutionary Algorithm for the Overlap Constrained Resource Allocation Problem in Wireless Networks. In: Barolli, L. (eds) Advanced Information Networking and Applications. AINA 2024. Lecture Notes on Data Engineering and Communications Technologies, vol 201. Springer, Cham. https://doi.org/10.1007/978-3-031-57870-0_22
Download citation
DOI: https://doi.org/10.1007/978-3-031-57870-0_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-57869-4
Online ISBN: 978-3-031-57870-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)