Efficient Global Algorithms for Transmit Beamforming Design in ISAC Systems

Jiageng Wu, Zhiguo Wang, Ya-Feng Liu, Fan Liu

TL;DR

This paper introduces a framework for finding the globally optimal transmit beamforming design in Integrated Sensing and Communication (ISAC) systems. By combining a novel Branch and Bound (B&B) algorithm with a Graph Neural Network (GNN)-based pruning policy, the authors achieve a 3-7x speedup over traditional global optimization methods while maintaining near-perfect optimality.

What Problem Does This Paper Address?

In the push toward 6G, Integrated Sensing and Communication (ISAC) has emerged as a key technology, allowing a single hardware platform to perform both radar sensing and multi-user communication. However, designing the "beamformers"—the spatial filters that shape the signal—is a nightmare for optimizers.

The goal is to maximize the sum-rate (communication speed) while minimizing the Cramér-Rao Bound (CRB) (a measure of radar sensing error). This is a non-convex, NP-hard problem. Most existing solutions use "local" optimization, which finds a "good enough" solution but can't guarantee it's the absolute best (the global optimum). Without a global benchmark, researchers can't know how much performance they are leaving on the table.

Methods

The authors tackle this by developing a global optimization strategy:

  1. Mathematical Relaxation: They use McCormick envelope relaxation to transform the non-convex problem into a series of convex sub-problems. This provides a "lower bound" on the objective function, which is essential for a search.
  2. Vanilla Branch and Bound (B&B): They implement a B&B algorithm that systematically partitions the search space into smaller "rectangles." It uses the lower bounds to prune branches that definitely don't contain the optimal solution.
  3. GNN-Based Acceleration: To solve the "curse of dimensionality" (where B&B becomes too slow as the number of users increases), they design a Graph Neural Network (GNN).
  4. Imitation Learning: The GNN is trained to "imitate" the expert B&B algorithm.
  5. Pruning Policy: During a live run, the GNN acts as a binary classifier, predicting which nodes in the search tree are "irrelevant" and can be skipped immediately.
  6. Closed-Form Solutions: For simpler cases (single-user or orthogonal channels), they derived exact mathematical formulas, removing the need for iterative searching entirely.

Datasets

The paper uses synthetic datasets generated through two specific channel models to evaluate the algorithms:

  • Scenario 1: i.i.d. complex Gaussian distribution (standard theoretical model).
  • Scenario 2: Rayleigh fading with path loss (a more realistic model where users are placed at varying distances from the base station). The GNN was trained using data generated from 20 random test instances per configuration.

Key Insights and Ideas

  • Breaking Monotonicity: Standard sum-rate maximization often relies on the objective function being "monotonically increasing" with signal quality. The authors point out that adding a radar sensing metric (CRB) breaks this property, making traditional "Polyblock" algorithms useless and necessitating a B&B approach.
  • Why GNNs? Wireless networks are dynamic; the number of users and antennas changes constantly. The authors chose a GNN because it is size-agnostic and permutation-invariant. Once trained, the same model can work even if the network configuration changes.
  • Global vs. Local: The results show that local algorithms (like WMMSE-SDR) struggle when the power budget is high or when the sensing requirements are strict. The global algorithm reveals a significant performance gap that local methods simply cannot bridge.

Key Results

  • Optimality: The vanilla B&B algorithm is mathematically guaranteed to find the global optimum.
  • Speedup: The GNN-accelerated version achieved a 3x to 7x speedup compared to the vanilla version.
  • Accuracy: Despite the aggressive pruning by the GNN, the "Optimality Gap" (how far the result was from the true best) was less than 0.05%.
  • Benchmarking: The study provides the first true "Pareto front" (the optimal trade-off curve) between communication sum-rate and radar sensing accuracy for this specific ISAC model.

Limitations and Future Work

  • Computational Complexity: While the GNN provides a massive speedup, the underlying B&B algorithm still scales exponentially in the worst-case scenario. It remains most suitable for small-to-medium-sized networks or as an offline benchmarking tool.
  • Single Base Station: The current model assumes a single ISAC base station. The authors suggest that future work should extend these global algorithms to multi-BS systems, where interference management becomes significantly more complex.
  • Hardware Constraints: The paper focuses on theoretical beamforming; future iterations could incorporate practical hardware limitations like "constant modulus" constraints for radar waveforms.

Summary updated

Abstract

In this paper, we propose a multi-input multi-output transmit beamforming optimization model for joint radar sensing and multi-user communications, where the design of the beamformers is formulated as an optimization problem whose objective is a weighted combination of the sum rate and the Cramér-Rao bound, subject to the transmit power budget. Obtaining the global solution for the formulated nonconvex problem is a challenging task, since the sum-rate maximization problem itself (even without considering the sensing metric) is known to be NP-hard. The main contributions of this paper are threefold. Firstly, we derive an optimal closed-form solution to the formulated problem in the single-user case and the multi-user case where the channel vectors of different users are orthogonal. Secondly, for the general multi-user case, we propose a novel branch and bound (B\&B) algorithm based on the McCormick envelope relaxation. The proposed algorithm is guaranteed to find the globally optimal solution to the formulated problem. Thirdly, we design a graph neural network (GNN) based pruning policy to determine irrelevant nodes that can be directly pruned in the proposed B\&B algorithm, thereby significantly reducing the number of unnecessary enumerations therein and improving its computational efficiency. Simulation results show the efficiency of the proposed vanilla and GNN-based accelerated B\&B algorithms.
BibTeX
@article{wu2024efficient,
  author = {Jiageng Wu and Zhiguo Wang and Ya-Feng Liu and Fan Liu},
  title = {{Efficient Global Algorithms for Transmit Beamforming Design in ISAC Systems}},
  journal = {IEEE Trans. Signal Process.},
  year = {2024},
  doi = {10.1109/tsp.2024.3457817},
}

Loading related content...

Figure