Combinatorial optimization of connected UAV communication bridges for emergency response

AI summary

Overview

Research area: Quantum computing for combinatorial optimization, applied to wireless network planning (UAV/drone-based emergency communications, FANETs).

Technical level: Advanced — the paper assumes familiarity with integer programming, QUBO/Ising formulations, and adiabatic quantum computation.

Scope: A single paper that defines a new UAV placement optimization problem (c-BUP), solves it with a classical solver (CPLEX), and reformulates it as a QUBO for the quantum adiabatic algorithm (QAA), tested on small instances via statevector emulation.

What This Paper Is About

After a natural disaster, ground communication infrastructure is often destroyed, so rescue teams need a quickly deployable network. The authors study how to place a limited number of 5G-equipped UAVs at pre-selected candidate sites so that ground coverage is maximized, interference between overlapping signals is minimized (by assigning multiple frequencies), and every drone has a multi-hop path back to a gateway. They call this the Connected-Backbone UAV Placement (c-BUP) problem.

Key Contributions

1. A new problem formulation (c-BUP). The paper introduces a combinatorial optimization problem that couples two graphs sharing the same candidate sites: an air-to-air connectivity graph (G_B) and a ground-interference graph (G_V). This goes beyond prior work that modeled only the backbone via minimum connected dominating set, by explicitly coupling the backbone problem with the coverage/frequency problem.

2. An integer quadratic program (IQP) with a cubic coupling term. Interference is encoded in a quadratic binary cost function (rather than the circle-packing schemes cited in prior work), and the model extends an earlier placement model to include both backbone nodes and multi-frequency selection. A cubic (H_{VB}^{(2)}) term is added to penalize a leaf connecting to two backbone nodes at once, and its effect on connectivity is measured.

3. A direct QUBO mapping. Because the formulation has no inequalities, conversion to QUBO requires no extra variables; with an algorithm such as QAA that can handle cubic Ising terms, the variable count drops to (N(B+F+1)). Only the cubic-term decoupling slack variables are needed on a quantum annealer, which supports quadratic models only.

4. Classical scaling analysis plus a small-scale QAA demonstration. CPLEX time-to-solution (TTS) is characterized on realistic configurations, a time-limited heuristic mode is proposed, and QAA on a statevector emulator is shown to solve small instances accurately.

Main Findings

• Exponential TTS growth with site count: The abstract reports a "significant exponential increase in Time-to-Solution (TTS) as the number of sites grows," which the authors describe as a critical challenge for urgent, time-sensitive scenarios.
• TTS grows faster than exponentially with backbone size: In the figures of merit for instances with (N=16) and (V=12), the paper states that TTS "grows faster than exponentially with (B)."
• Time-limited solutions are a practical trade-off: By enforcing a time limit on the solver, approximate suboptimal solutions can be produced that are not optimal but "preserve connectivity in most cases," keeping computation within feasible limits for real-time UAV redeployment.
• The cubic term improves connectivity but costs time: Across all instances considered, adding the (H_{VB}^{(2)}) term effectively enforced enhanced connectivity. Because CPLEX needs slack variables to handle the cubic term, this produced much larger TTS than the model without it; the authors suggest the cheaper model plus a heuristic re-attachment of disconnected leaves as a possible alternative.
• Frequency count controls interference: With (F=2) frequencies, the ((16,12,3,2)) solution still shows two interference conflicts; with (F=3), the ((16,12,3,3)) solution avoids all interference. The reason given is that any triangle can be made interference-free only by assigning a different frequency to each vertex, and denser graphs need more frequencies.
• Frequency assignment feeds back on connectivity: The backbone configuration changes when the frequency assignment changes, which the authors highlight as a coupling effect.
• Backbone size controls connectivity: For the illustrated case, (B=2) is not enough — node (v=5) is assigned but disconnected — so the minimum (B^{*}) ensuring full connectivity is 3. The number of connected antennas increases monotonically with (B) and converges to the total number of antennas (V) at (B=3).
• Coverage cost (H_V(y^*)) is much higher for (F=1), signaling a large number of interference events; for (F=2), selected overlaps are so small that for (B \le 3) the difference from (F=3) is smaller than the marker size.
• QAA solves small instances accurately: Through high-performance computing emulation, the paper shows the quantum adiabatic algorithm can accurately solve small-scale instances.

Methodology in Plain English

The authors pick (N) fixed candidate sites, from which (V \le N) sites get a drone ((V \le N)) and (B \le V) of the placed drones form a connected "backbone" that relays traffic to an entry point; drones attached to the backbone are called leaves, in analogy with trees.

The problem is split into three pieces that are then combined with Lagrange multipliers:

• Backbone: binary variables (x_{v,i}) say whether site (v) is the (i)-th backbone node. A cost term rewards consecutive backbone nodes that are joined by an edge in the air-to-air graph, which is how connectivity is encouraged without a hard linear constraint.
• Coverage and interference: binary variables (y_{v,p}) use a one-hot encoding, where (p=0) means the site is empty and (p>0) means it operates at frequency (\nu_p) — essentially a weighted graph-coloring scheme. One term rewards covered area, another penalizes overlap area between sites on the interference graph, with overlap counted only when two antennas share the same frequency.
• Coupling: a term forces any backbone site to also be an occupied site, a term rewards leaves being attached to backbone nodes, and a cubic term removes the double counting that lets one leaf attach to two backbone nodes.

Instances are generated on a (1\ \mathrm{km} \times 1\ \mathrm{km}) area using pseudo-random Sobol' sequences with Lloyd's optimization, producing an irregular grid with no symmetry so trivial schemes cannot solve it. Realistic parameters assume UAVs at approximately 150 m altitude with directional ground antennas giving a 45-degree coverage cone, an interference radius (r^{\mathrm{int}} \approx 150) m (so interference within 300 m), a connectivity radius (r^{\mathrm{back}} = 150 \sim 400) m, and a fixed ratio (r^{\mathrm{back}}/r^{\mathrm{int}} = 2.2) in the simulations. IQP instances were solved with the free version of IBM CPLEX via docplex, with graphs built using networkx.

Why This Matters

Research impact: The paper connects disaster-response network planning to quantum optimization in a way that is unusually concrete — the same model, with the same realistic radio parameters, is solved both classically and as a QUBO. It also gives a complexity argument: when (V=N) and (B^*) is chosen minimally, the problem reduces to minimum connected dominating set (known NP-hard), and the multi-frequency placement part combines graph coloring with an Ising problem on a non-planar graph, which the authors argue makes general c-BUP instances NP-hard as well.

Real-world applications:

• Re-establishing communication for rescue coordination after earthquakes, hurricanes, and floods that destroy conventional infrastructure.
• Search-and-rescue operations needing low-latency, high-bandwidth links in hazardous or unknown terrain.
• Rapidly redeployable localized coverage where satellite-based options are unsuitable because of extra hardware, weight, and battery constraints.
• Complementary capacity for partially functioning networks, improving quality-of-service where infrastructure survives.

Industry relevance: The work comes from Leonardo S.p.A.'s Quantum Computing Solutions group and its Hypercomputing Continuum, tying the problem to operational emergency-response and defense-adjacent communications, and to HPC resources at a command-and-control center.

Future Directions

• Scaling beyond small instances: QAA was validated only on small-scale instances with a statevector emulator; the path to large-scale, time-critical instances is presented as future work.
• Decomposition to cut computational burden: The authors suggest the SPLIT framework, used previously for a similar frequency-allocation problem, as a way to reduce the cost of solving c-BUP.
• Heuristics on top of the cheaper model: Dropping the cubic term and attaching disconnected leaves to the backbone in a second, heuristic step is proposed as a route to faster solutions.
• Choosing (B) systematically: The paper outlines two options — direct optimization by replacing the fixed-(B) constraint with (N_B(x) \le V) (which needs a larger variable set), or iterating over (B) with a stopping criterion — but does not resolve which is preferable.
• Dynamic reallocation: The stated scope covers optimal placement and only "partially" addresses reallocating UAVs in response to real-time changes.

Target Audience

Researchers and practitioners working at the intersection of quantum optimization and wireless networking — particularly those formulating QUBO/Ising models from real engineering problems — as well as network planners and emergency-communications engineers interested in what classical and quantum solvers can currently handle. Readers without background in integer programming or adiabatic quantum computing will find the formalism dense. Note that the supplied text is truncated during the discussion of Figure 9's scaling results, so the numerical TTS values for the ((12,10,k+2,1)) and ((12,10,3,k)) sweeps are not reported in the available content.

Authors’ abstract

We present a combinatorial optimization problem for the strategic deployment of UAVs equipped with 5G antennas to assist rescue operations in regions hit by natural disasters. Our goal is to optimize the placement of UAVs to provide coverage in flying ad-hoc networks among given candidate sites. Our formulation aims to maximize signal coverage and minimize interference while ensuring network connectivity. To mitigate interference effects, we incorporate the use of multiple frequencies. We formulate this problem as an integer quadratic program (IQP). We present numerical solutions obtained via the CPLEX solver and conduct a preliminary analysis of the problem's scalability in realistic network configurations. Our findings reveal a significant exponential increase in Time-to-Solution (TTS) as the number of sites grows, which poses a critical challenge in urgent, time-sensitive scenarios. To address this issue, approximate suboptimal solutions can be produced by enforcing a time limit on the solver. Although these solutions are not optimal, they preserve connectivity in most cases, providing a practical trade-off between solution quality and computational times that remain within feasible limits for real-time UAV redeployment. Recognizing the limitations of classical solvers in these contexts, we explore quantum computing as a promising alternative. Specifically, we reformulate the problem as a quadratic unconstrained binary optimization (QUBO) problem, suitable for most quantum algorithms. Through high-performance computing emulation, we show that the quantum adiabatic algorithm (QAA) can accurately solve small-scale instances, paving the way for future application of quantum computing to large-scale, time-critical optimization problems in disaster response.