University of Surrey

Test tubes in the lab Research in the ATI Dance Research

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

Alanis, Dimitrios, Botsinis, Panagiotis, Babar, Zunaira, Nguyen, Hung Viet, Chandra, Daryus, Ng, Soon Xin and Hanzo, Lajos (2018) A Quantum-Search-Aided Dynamic Programming Framework for Pareto Optimal Routing in Wireless Multihop Networks IEEE Transactions on Communications, 66 (8). pp. 3485-3500.

[img]
Preview
Text
A Quantum-Search-Aided Dynamic Programming Framework for Pareto Optimal Routing in Wireless Multihop Networks.pdf - Accepted version Manuscript

Download (2MB) | Preview

Abstract

Wireless Multihop Networks (WMHNs) have to strike a trade-off among diverse and often conflicting Qualityof-Service (QoS) 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 NP-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 have been proposed, namely the Non-Dominated Quantum Optimization (NDQO) and the Non-Dominated Quantum Iterative Optimization (NDQIO). 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.

Item Type: Article
Divisions : Faculty of Engineering and Physical Sciences > Electronic Engineering
Authors :
NameEmailORCID
Alanis, Dimitrios
Botsinis, Panagiotis
Babar, Zunaira
Nguyen, Hung Viethung.nguyen@surrey.ac.uk
Chandra, Daryus
Ng, Soon Xin
Hanzo, Lajos
Date : 6 February 2018
DOI : 10.1109/TCOMM.2018.2803068
Copyright Disclaimer : This work is licensed under a Creative Commons Attribution 3.0 License. For more information, see http://creativecommons.org/licenses/by/3.0/
Uncontrolled Keywords : Quantum Computing; NDQIO; NDQO; Dynamic Programming; Pareto Optimality; Routing
Depositing User : Clive Harris
Date Deposited : 19 Mar 2018 22:39
Last Modified : 26 Oct 2018 10:19
URI: http://epubs.surrey.ac.uk/id/eprint/846046

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year


Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800