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.

[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
Identification Number : 10.1109/TCOMM.2018.2803068
Copyright Disclaimer : © 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works
Uncontrolled Keywords : Quantum Computing; NDQIO; NDQO; Dynamic Programming; Pareto Optimality; Routing
Depositing User : Clive Harris
Date Deposited : 19 Mar 2018 22:39
Last Modified : 22 Mar 2018 10:10
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