Volume 58, Number 1, January-February 2024
|185 - 205
|26 January 2024
Exact and heuristic approaches for maximizing flows in UAV-enabled wireless cellular networks with multi-hop backhauls
Department of Mechanical and Industrial Engineering, College of Engineering, Qatar University, Doha, Qatar
2 Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, Trondheim, Norway
3 Electrical Engineering Department, College of Engineering, Qatar University, Doha, Qatar
Accepted: 11 October 2023
This paper investigates the problem of data routing in backhaul networks using Unmanned Aerial Vehicles (UAVs) to relay data from Small Cells (SCs) to the core network. The objective is to maximize the total fulfilled demand of data to be routed, while ensuring technical requirements such as hop constraints and edge capacity. The problem is formulated using a compact mixed-integer programming model, which can solve small- and medium-sized topologies. In addition, a fast constructive heuristic based on a maximal tree is developed to solve large-scale topologies, resulting in a significant reduction in CPU time. The quality of the heuristic is evaluated by using column generation for solving the linear programming relaxation of an exponential formulation. The computational study shows the effectiveness and value of the proposed compact model and constructive heuristic for various topology sizes. Furthermore, experiments demonstrate that by keeping the network setup constant and updating the demand vector only, the computational time of the compact model can be drastically reduced for all topology sizes.
Mathematics Subject Classification: 90B18 / 90C27
Key words: Bakchaul network / unmanned Aerial Vehicles (UAVs) / data routing / mixed-integer programming / heuristic / column generation
© The authors. Published by EDP Sciences, ROADEF, SMAI 2024
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.