Quantum-Assisted Joint Virtual Network Function Deployment and Maximum Flow Routing for Space Information Networks

Abstract

Network function virtualization (NFV)-enabled space information network (SIN) has emerged as a promising method to facilitate global coverage and seamless service. This paper proposes a novel NFV-enabled SIN to provide end-to-end communication and computation services for ground users. Based on the multi-functional time expanded graph (MF-TEG), we jointly optimize the user association, virtual network function (VNF) deployment, and flow routing strategy (U-VNF-R) to maximize the total processed data received by users. The original problem is a mixed-integer linear program (MILP) that is intractable for classical computers. Inspired by quantum computing techniques, we propose a hybrid quantum-classical Benders' decomposition (HQCBD) algorithm. Specifically, we convert the master problem of the Benders' decomposition into the quadratic unconstrained binary optimization (QUBO) model and solve it with quantum computers. To further accelerate the optimization, we also design a multi-cut strategy based on the quantum advantages in parallel computing. Numerical results demonstrate the effectiveness and efficiency of the proposed algorithm and U-VNF-R scheme.

References in corpus (10)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Network Function Virtualization: State-of-the-art and Research Challenges
• Noisy intermediate-scale quantum (NISQ) algorithms
• The Road Towards 6G: A Comprehensive Survey
• A Survey on Non-Geostationary Satellite Systems: The Communication Perspective
• Undecidability of the Spectral Gap (short version)
• 5G Embraces Satellites for 6G Ubiquitous IoT: Basic Models for Integrated Satellite Terrestrial Networks
• Consistency of the Adiabatic Theorem
• Quantum-Assisted Joint Caching and Power Allocation for Integrated Satellite-Terrestrial Networks