A Quantum-Search-Aided Dynamic Programming Framework for Pareto Optimal Routing in Wireless Multihop Networks

摘要

Wireless multihop networks (WMHNs) have to strike a trade-off among diverse and often conflicting quality-of-service requirements. The resultant solutions may be included by the Pareto front under the concept of Pareto optimality. However, the problem of finding all the Pareto-optimal routes in WMHNs is classified as non-deterministic polynomial-hard, since the number of legitimate routes increases exponentially, as the nodes proliferate. Quantum computing offers an attractive framework of rendering the Pareto-optimal routing problem tractable. In this context, a pair of quantum-assisted algorithms has been proposed, namely the non-dominated quantum optimization and the non-dominated quantum iterative optimization. However, their complexity is proportional to √N, where N corresponds to the total number of legitimate routes, thus still failing to find the solutions in “polynomial time.” As a remedy, we devise a dynamic programming framework and propose the so-called evolutionary quantum pareto optimization (EQPO) algorithm. We analytically characterize the complexity imposed by the EQPO algorithm and demonstrate that it succeeds in solving the Pareto-optimal routing problem in polynomial time. Finally, we demonstrate by simulations that the EQPO algorithm achieves a complexity reduction, which is at least an order of magnitude when compared to its predecessors, albeit at the cost of a modest heuristic accuracy reduction.