IEEE TRANSACTIONS ON COMMUNICATIONS 2018

1

arXiv:1802.08676v1 [quant-ph] 23 Feb 2018

A Quantum-Search-Aided Dynamic Programming
Framework for Pareto Optimal Routing in Wireless
Multihop Networks
Dimitrios Alanis, Student Member, IEEE, Panagiotis Botsinis, Member, IEEE, Zunaira Babar, Hung Viet
Nguyen, Member, IEEE, Daryus Chandra, Student Member, IEEE, Soon Xin Ng, Senior Member, IEEE,
and Lajos Hanzo, Fellow, IEEE

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.
Index Terms—Quantum Computing, NDQIO, NDQO, Dynamic Programming, Pareto Optimality, Routing.

L IST OF ACRONYMS
BBHT-QSA
BF
BER
CDP
CF(E)
DHA
DN
EQPO
HP
MODQO

Boyer-Brassard-Høyer-Tapp
Quantum
Search Algorithm
Brute Force
Bit Error Ratio
Classical Dynamic Programming
Cost Function (Evaluation)
Durr-Høyer Algorithm
Destination Node
Evolutionary Quantum Pareto Optimization
Hardware Parallelism
Multi-Objective Decomposition Quantum
Optimization

The authors are with the School of Electronics and Computer Science, University of Southampton, Southampton, SO17 1BJ, UK (email:
{da1d16, pb1y14, zb2g10, hvn08r, dc2n14, sxn, lh}@ecs.soton.ac.uk).
The financial support of the EPSRC under the grant EP/L018659/1, that
of the European Research Council, Advanced Fellow Grant and that of the
Royal Society’s Wolfson Research Merit Award is gratefully acknowledged.
Additionally, the authors acknowledge the use of the IRIDIS High Performance Computing Facility, and associated support services at the University
of Southampton, in the completion of this work. The research data of this
paper can be found at http://doi.org/10.5258/SOTON/D0402.

MO-ACO
NDQO
(P-)NDQIO
NSGA-II
OF
OPF-SR
(O)PF
QoS
QP
RN
SN
UV
UF
WMHN

Multi-Objective Ant Colony Optimization
Non-Dominated Quantum Optimization
(Preinitialized) Non-Dominated Quantum Iterative Optimization
Non-dominated Sorting Genetic Algorithm II
Objective Function
Optimal Pareto Front Self-Repair
(Optimal) Pareto Front
Quality-of-Service
Quantum Parallelism
Relay Node
Source Node
Utility Vector
Utility Function
Wireless MultiHop Network
I. I NTRODUCTION

T

HE concept of Wireless Multihop Networks (WMHN)
[1] enables the communication of remote nodes by forwarding the transmitted packets through a cloud of mobile
relays. Naturally, the specific choice of the relays plays a
significant role in the performance of WMHNs [2], thus
bringing their routing optimization in the limelight. Explicitly,
optimal routing relies on a fragile balance of diverse and often
conflicting Quality-of-Service (QoS) requirements [3], such
as the route’s overall Bit-Error-Ratio (BER) or Packet Loss
Ratio (PLR), its total power consumption, its end-to-end delay,
the route’s achievable rate, the entire system’s sum-rate and
its “lifetime” [4].
For the sake of taking into account multiple QoS requirements, several studies consider single-component Objective Functions (OF) as their optimization objectives. In this
context, the metric of Network Lifetime (NL) [4], [5] has
been utilized, which involves the routes’ power consumption
in conjunction with the nodes’ battery levels. Additionally,
the so-called Network Utility (NU) [6] also constitutes a
meritorious single-component optimization OF. Apart from
the aforementioned QoS requirements, NU also takes into
account the routes’ achievable rate [7]. In conjunction with the
construction of aggregate functions, the authors of [8], [9] also
incorporate QoS as constraints, thus providing a more holistic
view of the routing problem. In this context, Banirazi et al. [9]
optimized an aggregate function of the Dirichlet routing cost as

2

well as the average network delay at specific operating points
that maximize the network throughput.
The beneficial properties of dynamic programming [10]
have been exploited for the sake of identifying the optimal
routes, while relying on single-component aggregate functions.
In this context, Dijkstra’s algorithm [11]–[13] has been employed, since it is capable of approaching the optimal routes
at the cost of imposing a complexity on the order of O(E 3 ),
where E corresponds to the number of edges in the network’s
graph. Additionally, the appropriately modified Viterbi decoding algorithm [14], [15] has also been utilized for solving
single-component routing optimization problems, where the
route exploration process can be viewed as a trellis graph
and thus the routing problem is transformed into a decoding
problem. Explicitly, this transformation is reminiscent of the
famous Bellman-Ford algorithm [16].
The aforementioned approaches fail to identify the potential discrepancies among the QoS requirements, but they
can be unified by the concept of Pareto Optimality [17].
However, the search-space of multi-component optimization is
inevitably expanded due to combining the single-component
OFs. Furthermore, the complexity is proportional to O(N 2 ),
where N corresponds to the total number of eligible routes.
Additionally, since N increases exponentially as the relay
nodes proliferate [18], the Pareto-optimal routing problem
is classified as Non-deterministic Polynomial hard (NP-hard)
[19]. This escalating complexity can be partially mitigated
by identifying a single Pareto-optimal solution. For instance,
Gurakan et al. [20] conceived an optimal iterative routing
scheme for identifying a single Pareto-optimal solution in
terms of the sum rate and the energy consumption of wireless
energy-transfer-enabled networks. However, in our application
we are primarily interested in identifying the entire set of
Pareto-optimal solution, since it provides fruitful insights into
the underlying trade-offs [17]. In this context, multi-objective
evolutionary algorithms [18], [21], [22] have been employed
for addressing the escalating complexity. In particular, Yetgin
et al. [18] used both the Non-dominated Sorting Genetic
Algorithm II (NSGA-II) and the Multi-Objective Differential
Evolution Algorithm (MODE) for optimizing the transmission
routes in terms of their end-to-end delay and power dissipation.
While considering a similar context, Camelo et al. [21] invoked the NSGA-II for optimizing the same QoS requirements
for both the ubiquitous Voice over Internet Protocol (VoIP)
and for file transfer. Additionally, the so-called Multi-Objective
Ant Colony Optimization (MO-ACO) algorithm [23] has been
employed in [19] for the sake of addressing the multi-objective
routing problem in WMHNs.
Quantum computing provides a powerful framework [24]–
[26] for the sake of rendering Pareto-optimal routing problems
tractable by exploiting the so-called Quantum Parallelism (QP)
[27]. Explicitly, in [28] Quantum Annealing [29], has been
invoked for the sake of optimizing the activation of the
wireless links in wireless networks, while maintaining the
maximum throughput and minimum interference as well as
providing a substantial complexity reduction w.r.t. its classical
counterpart, namely simulated annealing. In terms of Pareto
optimal routing using universal quantum computing [27],

IEEE TRANSACTIONS ON COMMUNICATIONS 2018

the so-called Non-Dominated Quantum Optimization (NDQO)
algorithm proposed in [19] succeeded in identifying the entire
set of Pareto-optimal routes at the
√ expense of a complexity,
which is on the order of O(N N ), relying on QP. As an
improvement, the so-called Non-Dominated Quantum Iterative Optimization (NDQIO) algorithm was proposed in [30].
Explicitly, the NDQIO algorithm is also capable of identifying
the entire set of Pareto-optimal routes, while imposing a
1
parallel complexity and a sequential √
complexity defined
√ in
2
[30], which is on the order of O(NOPF N ) and O(NOPF N ),
respectively, by relying on the beneficial synergy between QP
and Hardware Parallelism (HP). Note that NOPF corresponds
to the number of Pareto-optimal routes.
Despite the substantial complexity reduction offered both
by the NDQO and the NDQIO algorithms, the multi-objective
problem still remains intractable, when the network comprises
an excessively high number of nodes due to the escalating
complexity. Explicitly, √
Zalka [31] has demonstrated that the
complexity order of O( N ) is the minimum possible, as long
as the database values are uncorrelated. By contrast, when the
formation of the Pareto-optimal route-combinations becomes
correlated owing to socially-aware networking [32], a further
complexity reduction can be achieved. Based on this specific
observation, we will design a novel algorithm, namely the
Evolutionary Quantum Pareto Optimization (EQPO), in order
to exploit the correlations exhibited by the individual Paretooptimal routes by appropriately constructing trellis graphs that
guide the search process in the same fashion as in Viterbi
decoding. Furthermore, we will also exploit the synergies
between QP and HP for the sake of achieving an additional
complexity reduction by considering as low a fraction of the
database entries as possible, while still guaranteeing a nearfull-search-based performance.
Our contributions are summarized as follows:
1) In Section III, we develop a novel multi-objective dynamic programming framework for generating potentially Pareto-optimal routes relying on the correlations
of the specific links constituting the Pareto-optimal
routes, hence substantially reducing the total number
of routes considered. Explicitly, this framework is a
multi-objective extension of the popular single-objective
Bellman-Ford algorithm.
2) In Section IV, we propose a novel quantum-assisted
algorithm, namely the Evolutionary Quantum Pareto
Optimization algorithm, which jointly exploits our novel
dynamic programming framework as well as the synergies between the QP and the HP for the sake of solving
the multi-objective routing problem of WMHNs.
3) In Section V, we also characterize the performance
versus complexity of the EQPO algorithm and demonstrate that it achieves both a parallel and a sequential
complexity reduction of at least an order of magnitude
for a 9-node WMHN, when compared to that of the
NDQIO algorithm.
1 We define the parallel complexity as the complexity imposed while taking
into account the degree of parallelism. By contrast, the sequential complexity
does not consider any kind of parallelism. In [30], they are referred to as
normalized execution time and normalized power consumption, respectively.

D. ALANIS ET AL.: A QUANTUM-AIDED DYNAMIC PROGRAMMING FRAMEWORK FOR PARETO OPTIMAL ROUTING IN WMHNS

The rest of this paper is organized as follows. In Section II,
we will briefly discuss the specifics of the network model
considered in our case study. In Section III, we will present a
dynamic programming framework, which is optimal in terms
of its heuristic accuracy. In Section IV, we will relax the
optimal framework of Section II for the sake of striking a
better accuracy versus complexity trade-off with the aid of
our EQPO algorithm. Subsequently, in Section V-A we will
analytically characterize the EQPO algorithm’s complexity and
in Section V-B we will evaluate its performance.
II. N ETWORK S PECIFICATIONS
In the context of this treatise, the model of the networks
considered both in [19] and in [30] has been adopted. To
elaborate further, the WMHN considered is a fully connected
network and it consists of a single Source Node (SN), a single
Destination Node (DN) and a cloud of Relay Nodes (RN).
The SN and the DN are located in the opposite corners of
a (100×100) m2 square-block area, which is the WMHN
coverage area considered. By contrast, the RNs are considered
to be roaming within the coverage area having random locations, which obey the uniform distribution within the WMHN
coverage area. A WMHN topology is exemplified in Fig. 1
for a WMNH consisting of 5 nodes in total. Additionally,
a cluster-head equipped with a quantum computer, which is
responsible for collecting all the required WMHN information,
such as the nodes’ geolocations and their interference levels, is
considered to be present at the DN side. Therefore, we should
point out that this treatise is focused on a centralized protocol.

3

overall Bit Error Ratio (BER). Before delving into the UFs,
let us define a legitimate route of our WMHN consisting of
Nnodes nodes, as xr = [SN, . . . , DN], which contains each
RN only once for the sake of limiting the total number N
of legitimate routes, while at the same time avoiding routes
associated with excessive power consumption and delay. Note
that we have associated the SN and the DN with the node
indices 1 and Nnodes , respectively, in the context of this treatise.
Additionally, these legitimate routes are mapped to a specific
index x under lexicographic ordering using Lehmer Encoding2
[33]. The route’s overall delay D(x) is considered as one
of our UFs, which is quantified in terms of the number of
hops established by the route. This is formally formulated as
follows:
D(x) = |xr | − 1,
(1)
where the operator |·| corresponds to the number of nodes
along the route xr including the SN and DN. Moving on to the
x-th route’s overall power consumption P (x), it is proportional
to the sum of path-losses incurred by each of the individual
links constituting the route. Explicitly, the path-loss LdB (i, j)
quantified in dB for a single link between the i-th and the j-th
nodes is equal to [30]:


4πdi,j
LdB (i, j) = PT x,ij − PRx,ij = 10α log10
, (2)
λc
where α corresponds to the path-loss exponent, di,j is the
distance between the two nodes and λc denotes the carrier’s
wavelength. In our case-study we have set α = 3 and
λc ≃ 0.125 m corresponding to a frequency of fc = 2.4 GHz.
Consequently, the second UF is formulated as follows:
|xr |−1

L(x) =

X

(i)

10LdB(xr

,xr(i+1) )/10

.

(3)

i=1

Figure 1: Exemplified WMHN topology associated with 5
nodes. The presence of a cluster-head in possession of a
quantum computer is considered at the DN side as in [19]
and in [30]. The interference levels experienced by each node
are presented in the legend.
Based on the network information gathered, the WMHN
cluster-head has to identify the optimal routes emerging from
the SN to the DN based on certain Utility Functions (UF).
Similar to [19] and [30], we have jointly taken into account
the route’s overall delay, its overall power consumption and its

Moving on to the final UF, namely the BER, let us first
elaborate on the interference levels experienced by the nodes.
In our specific scenario, there is only a single pair of source
and destination nodes, resulting in a single route being active. Additionally, we have assumed that the WMHN has
a sufficient number of orthogonal spreading codes and subcarriers for the sake of efficiently separating the routes as
in [32]. In this context, there is no interference stemming
from the WMHN itself; however, we have assumed that a
sufficiently high number of users access the channel, hence
the resultant interference can be treated as Additive White
Gaussian Noise (AWGN), owing to the Central Limit Theorem
(CLT) [34]. Therefore, the interference is modeled by a
random Gaussian process, with its mean set to -90 dBm and its
standard deviation set to 10 dB, while the transmission power
is set to PT x = 20 dBm. Additionally, the nodes transmit
their messages using the uncoded QPSK scheme [35] over
uncorrelated Rayleigh fading channels and utilize Decode-andForward relaying [36] for forwarding the respective messages.
Based on these assumptions, we can readily use the closedform BER performance of the adopted scheme versus the
2 Lehmer Encoding maps a specific permutation to an index in the factoradic
basis [33].

4

IEEE TRANSACTIONS ON COMMUNICATIONS 2018

received Signal-to-Noise Ratio (SNR), while the overall route’s
BER Pe (x) can be calculated using the following recursive
formula [19]:
Pe,tot = Pe,1 + Pe,2 − 2Pe,1 Pe,2 ,

(4)

which corresponds to the output BER Pe,tot of a two-stage
Binary Symmetric Channel (BSC) [19], where Pe,1 and Pe,2
represent the BER associated with the first and the second
stage, respectively.
Having described the UFs considered, let us now proceed by
defining our optimization problem. Explicitly, we will jointly
consider the UFs in the form of a Utility Vector (UV) f (x),
which is defined as follows:
f (x) = [Pe (x), L(x), D(x)] ,

(5)

where D(x) and L(x) correspond to the x-th route’s delay
and power consumption defined in Eqs. (1) and (3), while
Pe (x) denotes the x-th route’s end-to-end BER, which is
recursively evaluated using Eq. (4). Explicitly, we opt for
jointly minimizing the entire set of UFs considered by the
UV of Eq. (5). Therefore, for the evaluation of the fitness of
the UVs we will utilize the concept of Pareto Optimality3 [17],
which is encapsulated by Definitions 1 and 2.
Definition 1. Pareto Dominance [17]: A particular route xi
associated with the UV f (xi ) = [f1 (xi ), . . . , fK (xi )], where
K is the number of the UFs considered, is said to strongly
dominate another route xj associated with the UV f (xj ) =
[f1 (xj ), . . . , fK (xj )], denoted by f (xi ) ≻ f (xj ), iff we have
fk (xi ) < fk (xj ), ∀k ∈ {1, . . . , K}. Equivalently, the route
xi is said to weakly dominate another route xj , denoted by
f (xi )  f (xj ), iff we have fk (xi ) ≤ fk (xj ), ∀k ∈ {1, . . . , K}
and ∃k ′ ∈ {1, . . . , K}, so that we have fk′ (xi ) < fk′ (xj ).
Definition 2. Pareto Optimality [17]: A particular route xi
associated with the UV f (x1 ) is Pareto-optimal, iff there is
no route that dominates xi , i.e. we have ∄xj so that f (xj ) ≻
f (xi ) is satisfied. Equivalently, the route xi is strongly Paretooptimal iff there is no route that weakly dominates xi , i.e. we
have ∄xj , so that f (xi )  f (xj ) is satisfied.
Explicitly, Definition 1 provides us with the criterion for
evaluating the fitness of a specific route with respect to another
reference route, while Definition 2 outlines the condition
of the specific route’s optimality. Based on the number of
routes dominating a specific route, it is possible to group the
routes into the so-called Pareto Fronts (PF). Explicitly, the
PF comprises the Pareto-optimal routes, which are dominated
by no other routes according to Definition 2, which is often
referred to as the Optimal Pareto Front (OPF).
In our application, our aim is to identify the entire set
of weakly Pareto-optimal routes for the sake of gaining
insight into the routing trade-offs associated with the UFs
considered. Naturally, for the sake of identifying a specific
route as Pareto-optimal we have to perform precisely (N − 1)
Pareto-dominance comparisons, where N corresponds to the
total number of legitimate routes. Therefore, the complexity
3 The readers should refer to [32] for a more detailed tutorial on Pareto
optimality.

imposed by the exhaustive search aiming for identifying the
entire set of routes belonging to the OPF is on the order of
O(N 2 ). Explicitly, the total number N of legitimate routes increases exponentially as the number Nnodes of nodes increases
[19], hence rendering the multi-objective routing problem as
NP-hard. Thus sophisticated methods are required for finding
all of the solutions.
Let us now proceed by elaborating on our novel dynamic
framework designed for efficiently exploring the search space.
III. M UTLI -O BJECTIVE ROUTING DYNAMIC
P ROGRAMMING F RAMEWORK
Before delving into the analysis of our multi-objective dynamic programming framework, which is specifically tailored
for our routing problem, we will express each of the UFs
considered in the UV of Eq. (5) as a weighted sum of the
specific UFs associated with the individual links comprised
by a particular route. Explicitly, the power consumption has
already been expressed in this form based on Eq. (3). As for
the delay, which we have defined as the number of hops, it
may be redefined as follows:
D(x) =

|xr |−1 

X
i=1


1 − δx(i) ,x(i+1) ,
r

(6)

r

where δi,j corresponds to the Kronecker delta function [37],
while xr and x represent the route and its associated index,
respectively. As for the route’s overall BER, the recursive
formula of Eq. (4) may be approximated as follows:
|xr |−1

|xr |−1

Pe (x) =

X
i=1

Pe,x(i) ,x(i+1) −ǫ(x) ≈
r

r

X

Pe,x(i) ,x(i+1) , (7)
r

r

i=1

where Pe,k,l represents the BER of the specific link established between the k-th and the l-th nodes, while ǫ(x) is the
approximation error, which is on the order of:


r |−1 |xr |−1

|xX
X


Pe,x(j) ,x(i+1) Pe,x(j) ,x(j+1)  .
ǫ(x) = O 
r
r
r
r

 i=1

(8)

j=1
j 6= i

Since the sum of the products of all the links’ BER will
be several orders of magnitude lower than their sum, the
approximation error of Eq. (7) may be deemed to be negligible.
Having expressed the UFs considered as a weighted sum
of the UFs associated with their links, we may now proceed
by exploiting this specific property for the sake of achieving a
further complexity reduction. In fact, it is possible to transform
our composite multi-objective routing problem into a series of
smaller subproblems, thus arriving at a dynamic programming
structure. This transformation is performed with the aid of
Definition 3 in conjunction with Proposition 1.
Definition 3. A specific route x = {SN →R̄i →DN } is said
(j)
to generate another route xg by inserting the single RN Rj
node between the previous RN and the DN. Explicitly, the
(j)
(j)
resultant route xg is xg = {SN →R̄i →Rj →DN }, ∀j ∈
{1, . . . , Nnodes − 2}.

D. ALANIS ET AL.: A QUANTUM-AIDED DYNAMIC PROGRAMMING FRAMEWORK FOR PARETO OPTIMAL ROUTING IN WMHNS

Proposition 1. Let us consider a specific route
x
=
{SN →R̄i →DN } associated with the UV
f (x) = [f1 (x), . . . , fK (x)] and its sub-route x′ = {SN →R̄i }
associated with the UV f (x′ ) = [f1 (x′ ), . . . , fK (x′ )]. Let us
assume furthermore that each component fk (x) of the UV
associated with the route x has a positive value and that
it can be expressed as a sum of the respective UFs of its
individual links xi,i+1 , i.e. we have:
|x|−1

fk (x) =

X

fk (xi,i+1 ),

(9)

i=1

with fk (xi,i+1 ) > 0, ∀ k, i, x : k ∈ {1, ..., K}, i ∈
{1, ..., |x| − 1}, x ∈ S, where K and S are the number
of optimization objectives and the set of legitimate routes,
respectively. The route x cannot generate any Pareto-optimal
routes using the rule of Definition 3 if there is a route
xd = {SN →R̄j →DN } from the SN to the DN associated
with R̄j 6= R̄i that weakly dominates the sub-route x′ , i.e. if
we have ∃xd ∈ S : f (xd )  f (x′ ). The respective proof is
presented in Appendix A.
Explicitly, Proposition 1 guarantees that a specific route
x = {SN →R̄i →DN } comprised by the sub-route x′ =
{SN →R̄i } cannot generate Pareto-optimal routes by adding
an intermediate RN to x between its last RN and the DN, if
the sub-route x′ is weakly dominated by any of the legitimate
routes. Explicitly, should its sub-route x′ be sub-optimal, the
respective route x will be sub-optimal as well, since we have
∃xd ∈ S : f (xd )  f (x′ ) ≻ f (x), based on Proposition 1.
Note that the opposite of this statement does not apply, since
there exist sub-optimal routes, whose sub-routes are indeed
Pareto-optimal.
This specific property can be exploited for the sake of reducing the search-space size required for identifying the entire
OPF. To elaborate further, we can devise an irregular trellis
graph [38] for the sake of guiding the search space exploration,
as portrayed in Fig. 2 for the 5-node WMHN of Fig. 1. Note
however that this specific trellis graph is different from those
used for channel coding in [38], since in the latter we only
have as many legitimate paths as many legitimate symbols. By
contrast, here all transitions represent legitimate routes in our
scenario. Additionally, we rely on Definition 3 for the sake of
determining the possible trellis-node transitions. For instance,
observe in Fig. 2 that a trellis-path emerging from the trellisnode associated with the generator route {1 → 2 → 5} is
only capable of visiting the nodes associated with the routes
{1 → 2 → 3 → 5} and {1 → 2 → 4 → 5}, since a single
RN is inserted before the DN into the generator route based
on Definition 3. Moving on to the next trellis stages, during
the i-th trellis stage the following three steps are carried out:
gen
1) Surviving Routes: The set S(i)
of generated routes are
surv
constructed based on the set S(i−1) of surviving routes of the
previous stage and relying on Definition 3.
OPF
2) Pareto-Optimal Routes: The set S(i)
of Pareto-optimal
routes is identified based on the following optimization prob-

5

lem:
OPF
S(i)
=

argmin

{f (x)},

gen
OPF
∪S(i−1)
x∈S(i)
gen
s.t. ∄j ∈ S(i)

OPF
∪ S(i−1)
: f (j) ≻ f (x).

(10)

Note that the optimization problem of Eq. (10) considers the
gen
joint search space constituted by the all the routes S(i)
of
the i-th trellis stage as well as by the Pareto-optimal routes
OPF
S(i−1)
of the previous stage. Using recursion, we can readily
OPF
observe that the Pareto-optimal routes S(i−1)
of the previous
stage contain the Pareto-optimal routes across all stages up to
the (i−1)-st stage. This property is beneficial for our dynamic
programming framework, since it eliminates the need for
backwards propagation, thus only requiring the employment
of a feed-forward method for the identification of the entire
OPF.
surv
3) Surviving Routes: The set S(i)
of surviving routes is
identified based on the following optimization problem:
surv
S(i)
=

argmin{f (x)},
gen
x∈S(i)

gen
OPF
s.t. ∄j ∈ S(i)
∪ S(i−1)
: f (j)  f (x′ ).

(11)

where x′ corresponds to the particular sub-route of x, having
all the links of x, except for the last hop, as detailed in
Proposition 1.
The optimization process proceeds to the next trellis stage
as long as either there exist surviving routes, i.e. we have
surv
S(i)
6= ∅, or if the maximum affordable number of trellis
stages - which is equal to the maximum number of hops of
the legitimate routes - has not been exhausted. Otherwise,
the optimization process terminates by exporting the hitherto
identified OPF.
Let us now proceed by elaborating on the route exploration
process using the 5-node WMHN example of Fig 1. Its
respective trellis is portrayed in Fig 2, while the routes’ and
their respective sub-route’s UVs are shown in Table I. Initially,
gen
the optimization process considers the set S(1) of routes, which
is constituted by all the legitimate routes having a single and
two hops, namely the routes {1 → 5}, {1 → 2 → 5},
{1 → 3 → 5} and {1 → 4 → 5}, as portrayed in the
1st trellis stage of Fig. 2. Based on Table I, all the routes
considered are Pareto-optimal and thus the respective set is
gen
OPF
equal to S(1)
= S(1)
. Subsequently, the set of surviving nodes
is constructed. Explicitly, the direct route is not considered
in this case, since its inclusion leads to the generation of
routes, which have already been processed. Observe in Table I
that all the routes constituted by 2 hops have Pareto optimal
sub-routes and hence the set of surviving routes becomes
surv
S(1)
= [{1 → 2 → 5}, {1 → 3 → 5}, {1 → 4 → 5}].
surv
After the identification of the set of surviving routes S(1)
,
gen
nd
the set S(2) of routes generated in the 2 trellis stage is
created by including an appropriate RN right before the
DN, as annotated with the aid of black arrows in Fig 2.
Naturally, since all the routes constituted by two hops
have been identified as being Pareto-optimal, the entire set
of routes having three hops is visited by the trellis-paths
OPF
in the 2nd trellis stage, as seen in Fig. 2. The set S(1)
st
of Pareto-optimal routes of the 1 trellis stage is then

6

IEEE TRANSACTIONS ON COMMUNICATIONS 2018

Figure 2: Irregular trellis graph designed for guided search-space exploration for the 5-node WMHN of Fig. 1 using the
optimal dynamic programming framework, encapsulated by Definition 3 and Proposition 1. Note that the UVs of each route
are presented in Table I.
gen
concatenated to the set S(2)
of the routes generated in the
nd
OPF
2 trellis stage and the set S(2)
of Pareto-optimal routes
OPF
is identified. After this operation, the latter is set to S(2)
=
[{1 → 5}, {1 → 2 → 5}, {1 → 3 → 5}, {1 → 4 → 5} ,
{1 → 3 → 2 → 5}],
hence
including
the
route
{1 → 3 → 2 → 5} to the OPF, as denoted with the
aid of the bold rectangle in Fig. 2. The surviving routes of
the 2nd trellis stage are then identified using the optimization
problem of Eq. (11). Explicitly, they constitute the set
surv
S(2)
= {1 → 3 → 2 → 5}, {1 → 3 → 4 → 5}, {1 → 4 →
2 → 5}, {1 → 4 → 3 → 5}, as it may be verified by Table I
and denoted with the aid of the gray-filled nodes of Fig. 2.

In the presence of surviving nodes, the optimization process
proceeds with the final trellis stage; however, in this case the
routes {1 → 2 → 3 → 4 → 5} and {1 → 2 → 4 → 3 → 5}
are not considered, since their generators do not have Paretooptimal sub-routes. This is portrayed in Fig. 2 with the aid
both of the gray dashed arrows and of the gray dashed nodes.
gen
Hence, the set S(3)
= {1 → 3 → 2 → 4 → 5}, {1 → 3 →
4 → 2 → 5}, {1 → 4 → 2 → 4 → 5}, {1 → 4 → 3 →
OPF
2 → 5} is generated. The set S(2)
is then concatenated to
that of the routes generated in the final trellis stage and the
OPF
final set S(3)
of Pareto-optimal routes is identified. Explicitly,
the latter is identical to the respective set of the 2nd trellis
stage, since none of the routes generated in the final stage
is Pareto-optimal, as verified by Table I. Additionally, since

we have reached the final stage, the set of surviving routes is
not identified and the process exits by exporting the hitherto
observed OPF.
In a nutshell, this route exploration process succeeds in
transforming the multi-objective routing problem into a series
of significantly less complex sub-problems, each corresponding to a single trellis stage, hence inheriting the structure of
dynamic programming problems [10]. Note that the metricaccumulation, which is typical in dynamic programming problems, is constituted by the update of the Pareto-optimal routes.
Note that this dynamic programming framework is optimal in
terms of its efficacy in identifying the entire OPF, just like
the exhaustive search method. Primarily, this is a benefit of
Proposition 1, which excludes the routes that are incapable of
generating Pareto-optimal routes during the next trellis stages.
IV. E VOLUTIONARY Q UANTUM PARETO O PTIMIZATION
In Section III, we introduced a novel dynamic programming
framework for the sake of guiding the search process in
identifying the Pareto-optimal routes, thus effectively reducing
the complexity. In this section, we exploit this framework
and further improve it with the aid of our EQPO algorithm.
More specifically, we have relaxed the dynamic programming
framework of Section III for the sake of striking a better
accuracy versus complexity trade-off. Additionally, we have
improved the quantum-assisted process of [30] for identifying

D. ALANIS ET AL.: A QUANTUM-AIDED DYNAMIC PROGRAMMING FRAMEWORK FOR PARETO OPTIMAL ROUTING IN WMHNS

7

Table I: Utility Vectors of the legitimate routes and of their respective sub-routes for the 5-node WMHN topology of Fig. 1.
Route x
{1 5}
{1 2 5}
{1 3 5}
{1 4 5}
{1 2 3 5}
{1 2 4 5}
{1 3 2 5}
{1 3 4 5}
{1 4 2 5}
{1 4 3 5}
{1 2 3 4 5}
{1 2 4 3 5}
{1 3 2 4 5}
{1 3 4 2 5}
{1 4 2 3 5}
{1 4 3 2 5}

[4.52
[2.52
[2.35
[1.43
[9.49
[1.91
[1.36
[1.29
[1.42
[1.46
[1.36
[1.94
[1.90
[1.28
[1.49
[1.45

Route UV
10−4 , 74.15, 1]
10−4 , 73.10, 2]
10−4 , 70.89, 2]
10−2 , 71.76, 2]
10−4 , 76.09, 3]
10−2 , 75.72, 3]
10−4 , 69.55, 3]
10−2 , 71.74, 3]
10−2 , 71.19, 3]
10−2 , 73.50, 3]
10−2 , 76.36, 4]
10−2 , 76.50, 4]
10−2 , 74.13, 4]
10−2 , 71.18, 4]
10−2 , 75.23, 4]
10−2 , 72.82, 4]

Sub-route UV
[∞, ∞, ∞]
[2.52 10−4 , 73.10, 1]
[3.13 10−5 , 57.30, 1]
[1.41 10−2 , 67.50, 1]
[7.45 10−4 , 74.61, 2]
[1.89 10−2 , 74.46, 2]
[1.36 10−4 , 69.54, 2]
[1.28 10−2 , 67.46, 2]
[1.42 10−2 , 71.19, 2]
[1.44 10−2 , 70.27, 2]
[1.34 10−2 , 75.30, 3]
[1.92 10−2 , 75.18, 3]
[1.88 10−2 , 72.18, 3]
[1.28 10−2 , 71.17, 3]
[1.47 10−2 , 73.35, 3]
[1.45 10−2 , 72.81, 3]

the Pareto-optimal routes, so that it becomes capable of “remembering” the OPF identified in the previous trellis stages.
We will refer to this improved quantum-assisted process as the
Preinitialized-NDQIO (P-NDQIO) algorithm. In this context,
the P-NDQIO and the EQPO algorithms are presented in
Sections IV-A and IV-B, respectively. Let us now proceed by
presenting the P-NDQIO algorithm.

Optimal Sub-route
X
X
X
X

X

X
X
X
X

Algorithm 1 Preinitialized Non-Dominated Quantum Iterative
Optimization Algorithm (P-NDQIO)
1:
2:
3:
4:

A. Preinitialized NDQIO algorithm

5:

The P-NDQIO algorithm, which is formally stated in Alg. 1,
is the main technique of memorization [10], thus providing a
significant complexity reduction by remembering and propagating the OPF identified across the previous trellis stages
to the next ones. Its memorization is performed in Step 1 of
Alg. 1, where the OPF of the current trellis stage is initialized
to that of the previous stage. Subsequently, the P-NDQIO
algorithm performs its iterations, looking for Pareto-optimal
routes in Steps 2-14 of Alg. 1.
During each iteration, which results in identifying a single
Pareto-optimal route, the P-NDQIO algorithm first invokes
the so-called Boyer-Brassard-Hoyer-Tapp Quantum Search
Algorithm (BBHT-QSA) [25] for the sake of identifying routes
that are not dominated by any of the routes belonging to
the hitherto identified OPF. We refer to this process as the
Backward BBHT-QSA (BW-BBHT-QSA) process [30]. If an
invalid route-solution - i.e. a route that is indeed dominated
by the OPF identified so far - is output by the BBHT-QSA,
the P-NDQIO algorithm concludes that the entire OPF has
been identified. However, since the BBHT-QSA exhibits a low
probability of failing to identify a valid solution4, the BWBBHT-QSA step is repeated for an additional iteration in order
to ensure the detection of the entire OPF, as seen in Steps 12
and 14 of Alg. 1. Otherwise, should a valid route-solution be
identified by the BW-BBHT-QSA step, this specific route is

6:

4 We define a valid route-solution as the specific route that satisfies the
condition in Step 5 of Alg. 1

Optimal Route
X
X
X
X

7:
8:

9:
10:
11:
12:
13:
14:
15:

OPF
OPF
Initialize the OPF to S(i)
← S(i−1)
.
repeat
T ← 0.
Invoke the BBHT-QSA of [30, Alg. 1] searching for
gen
routes in S(i)
that are not dominated by any of the
OPF
routes of S(i) and output xs .
OPF
if f (j) ⊁ f (xs ), ∀j ∈ S(i)
then
repeat
Set j ← xs .
Invoke the BBHT-QSA of [30, Alg. 1] searching
gen
for routes in S(i)
that dominate the route j and
output xs .
until f (xs ) ⊁ f (j).
OPF
Discard the routes from S(i)
that are dominated by
the route j and append it to the OPF.
else
Set T ← T + 1.
end if
until T = 2
OPF
Export the S(i)
and exit.

classified as “potentially” being Pareto-optimal. Consequently,
the P-NDQIO algorithm invokes the so-called BBHT-QSA
chain process [19], [30] in Steps 6-9 of Alg. 1. Explicitly, the
output of the BW-BBHT-QSA is set as the initial reference
solution in Step 7 of Alg. 1 and a BBHT-QSA process is
activated in Step 8 of Alg. 1, which searches for routes
that dominate the reference one. If a route that dominates
the reference one is found, the reference route is updated
to the BBHT-QSA output and a new BBHT-QSA process is
activated. Naturally, the activation of the BBHT-QSA process
is repeated until a particular route is output by the BBHT-QSA
that does not dominate the reference route, thus indicating that

8

IEEE TRANSACTIONS ON COMMUNICATIONS 2018

the reference route is Pareto-optimal. Subsequently, the ParetoOPF
optimal routes of the set S(i)
are checked as to whether they
are dominated by the reference route, so that they are removed
OPF
and the reference route is then included in S(i)
, as seen in
Step 10 of Alg. 1. Explicitly, this check, which is referred to as
the OPF Self-Repair (OPF-SR) process in [30], provides the
EQPO algorithm with resilience against including sub-optimal
routes in the early trellis stages due to the limited number of
generated routes, hence preventing their propagation to the
later stages.
Both the BW-BBHT-QSA process and the BBHT-QSA
chains are parts of the original NDQIO algorithm; thus, the PNDQIO algorithm employs quantum circuits that are identical
to those of the NDQIO algorithm. Therefore, the motivated
readers may refer to [30] for extended discussions.
B. EQPO algorithm
The dynamic framework introduced in Section III, albeit
optimal in terms of its capability of identifying the entire OPF,
it may impose an excessive complexity quantified in terms of
the number of dominance comparisons required for solving the
optimization problem of Eq. (11). To elaborate further, as the
number of UFs considered increases, the number of surviving
routes is increased due to the differences among the UFs.
This in turn leads to the proliferation of the number of routes
generated per trellis stage. However, only a relatively small
fraction of the surviving route-population leads eventually to
generating Pareto-optimal routes in the next trellis stages.
Therefore, the employment of the optimal dynamic framework
presented in Section III imposes a significant complexity
overhead for the sake of ensuring the detection of the entire set
of Pareto-optimal routes. Consequently, a performance versus
complexity trade-off has to be struck for the sake of mitigating
this complexity overhead. In fact, this specific balance is struck
in the context of the EQPO algorithm by jointly relying on
Relaxations 1 and 2.
Relaxation 1. A route can only generate optimal routes
based on Definition 3, if it is Pareto-optimal. This is formally
formulated as follows:
OPF
OPF
surv
.
− S(i−1)
, S(i)
S(i)

(12)

surv
of the surviving routes
Relaxation 1 restricts the set S(i)
at the end of the i-th trellis stage to the set of the newlydiscovered Pareto-optimal routes at this specific trellis stage.
This relaxation provides beneficial complexity reduction, since
surv
it makes the identification both of the set S(i)
of surviving
OPF
routes and of the set S(i) of Pareto-optimal routes possible
by simply solving the optimization problem of Eq. (10).
Explicitly, Proposition 1 does not conflict with Relaxation 1,
since the Pareto-optimal routes are guaranteed to have Paretooptimal sub-routes. This is justified by the fact that the subroutes dominate their routes due to the absence of the final hop,
which results in increasing all the UFs considered. Thus, since
there exist no route from the SN to the DN dominating the
route identified, there exist no routes dominating the respective
sub-route either. However, the complexity reduction offered
by Relaxation 1 comes at the price of reduced accuracy,

since sub-optimal routes having Parero-optimal sub-routes do
exist, which might potentially lead to the generation of Paretooptimal routes in the next trellis stages. This specific limitation
is mitigated with the aid of Relaxation 2.
Relaxation 2. For the sake of facilitating the identification of
all Pareto-optimal routes, Definition 3 is relaxed as follows:
(j,k)
a specific route x is said to generate another route xg
by
inserting the single RN Rj between the k-th and the (k + 1)-st
nodes.
gen
of generated routes, which
Relaxation 2 extends the set S(i)
surv
are created by the set S(i−1) of surviving routes of the previous
trellis stage. This is realized by replacing a single direct link
established either by two RNs or by an RN and the DN with
an indirect link involving an appropriate RN as an intermediate relay. Naturally, this specific modification enhances the
heuristic accuracy of the EQPO algorithm, since it allows the
generation of additional routes, thus acting similarly to the
mutation operation of genetic algorithms [39].

Algorithm 2 Evolutionary Quantum Pareto Optimization
(EQPO) Algorithm.
1:
2:
3:
4:

5:
6:
7:
8:
9:

gen

gen

gen

OPF
surv
Set S(0) ← {SN → DN }, S(0)
← S(0) , S(0)
← S(0) ,
i ← 0.
repeat
Set i ← i + 1.
gen
surv
Generate the set of routes S(i)
from the set S(i−1)
based
on Relaxation 2 by appropriately inserting a single RN
between two intermediate nodes.
gen
gen
OPF
← S(i)
∪ S(n−1)
.
Set S(i)
gen
Invoke the P-NDQIO algorithm of Alg. 1 in the set S(i)
OPF
OPF
and initialize the identified OPF to S(n)
← S(n−1)
.
surv
OPF
OPF
Set S(i) ← S(n) − S(n−1) .
surv
= 0 or i = Nnodes − 1
until S(i)
OPF
Export the OPF S(n)
and terminate.

Let us now proceed by elaborating on the specifics of the
EQPO algorithm, which is formally presented in Alg. 2. To
elaborate further, in Step 1 of Alg. 2 the EQPO algorithm
initializes the set of routes generated, the Pareto-optimal routes
as well as the surviving routes to the direct route, i.e. to the
route {SN → DN }. It then proceeds with the trellis stages
using Steps 2-8 of Alg. 2. During each trellis stage, the set
gen
S(i)
of generated routes is constructed in Step 4 of Alg. 2
relying on Relaxation 2. Upon applying Relaxations 1 and 2
in the trellis of Fig. 2 results in the trellis of Fig. 3.
OPF
This set is then concatenated with the set S(i−1)
of Paretooptimal routes identified in the previous stage. Subsequently,
the P-NDQIO algorithm is invoked in Step 6 of Alg. 2 for
OPF
the sake of identifying the set S(i)
of Pareto-optimal routes
gen
surv
from the set S(i) . Then, the set S(i) of surviving routes is
determined in Step 7 of Alg. 2, relying on Relaxation 1.
More specifically, the steps carried out as part of the EQPO
algorithm’s dynamic programming framework during a single
trellis stage are listed as follows:

D. ALANIS ET AL.: A QUANTUM-AIDED DYNAMIC PROGRAMMING FRAMEWORK FOR PARETO OPTIMAL ROUTING IN WMHNS

9

Figure 3: Irregular trellis graph designed for guided search-space exploration for the 5-node WMHN of Fig. 1 using the EQPO
algorithm’s dynamic programming framework, encapsulated by Relaxations 1 and 2. Note that the UVs of each route are
presented in Table I
gen

1) Route Generation: EQPO creates the set S(i) of routes
surv
based on the set S(i−1)
of surviving routes from the previous trellis stage using Relaxation 2, as seen in Step 4
of Alg. 2. For instance, observe in Fig. 3 that the route
{1 → 2 → 5} is capable of generating 4 routes, namely
the routes {1 → 2 → 3 → 5}, {1 → 2 → 4 → 5},
{1 → 3 → 2 → 5}, {1 → 4 → 2 → 5}. By contrast,
Definition 3 allows the generation of only the first two routes,
as portrayed in Fig. 2. Additionally, in contrast to the optimal
dynamic programming framework of Section III, each route of
the current trellis stage in Fig. 3 can be generated by multiple
surviving routes of the previous stage. This specific feature of
Relaxation 2 enhances the heuristic accuracy, since it enables
the generation of potentially Pareto-optimal routes, which have
suboptimal constructors and hence would be disregarded based
on Relaxation 1.
2) Pareto-Optimal and Surviving Routes: Following the
gen
construction of the set S(i)
of the routes generated, the EQPO
algorithm invokes the P-NDQIO algorithm of Section IV-A
in Step 6 of Alg. 2 in order to search for new Paretogen
optimal routes belonging to the set S(i)
. However, based on
Definition 2, the optimality of the route depends on the set
OPF
of eligible routes considered. Consequently, the OPF S(i−1)
hitherto identified across all the previous trellis stages has to
gen
be concatenated with S(i)
in Step 5 of Alg. 2, thus ensuring
that the routes identified as optimal by the P-NDQIO algorithm
are indeed Pareto-optimal with respect to the entire set of
OPF
legitimate routes. Note that the set S(i)
contains the Paretooptimal routes across all trellis stages all the way up to the

i-th one, as in the optimal dynamic programming framework
of Section III. Consequently, using Relaxation 1 the Paretooptimal routes identified at the current trellis stage are considered as surviving routes. Note that the Pareto-optimal routes
identified throughout the previous stages are not taken into
account, since they would generate routes already processed
during the previous trellis stages.
The EQPO algorithm continues processing the trellis stages
either until it reaches a trellis stage having no surviving paths
or when the maximum affordable number of trellis stages
is exhausted, in a similar fashion to the optimal dynamic
programming framework of Section III.
Let us now highlight the differences between the trellises of
Figs. 2 and 3 considering the 5-node example of Fig. 1. Note
that the same annotation is used in Fig. 3 as that of Fig. 2
Explicitly, based on Eq. (12), the EQPO algorithm classified
the specific routes, which are Pareto-optimal as being “ParetoOptimal” and those that have been generated in the current
stage as “Visited & Surviving”. Hence in contrast to Fig. 2,
they are equivalent in Fig. 3. Similar to the optimal dynamic
programming framework of Section III, the EQPO algorithm
gen
of generated routes to the set of the
initializes the set S(1)
legitimate routes having either single or two hops, as portrayed
in the 1st trellis stage of Fig. 3. Based on Table I, all the
routes having two hops are Pareto-optimal and thus the EQPO
algorithm classifies them as the surviving routes of the 1st
trellis stage, as seen in Fig. 3. Similar to Fig. 2, the EQPO
algorithm’s trellis paths visit the entire set of routes having
three hops and then the algorithm identifies the route {1 →

10

IEEE TRANSACTIONS ON COMMUNICATIONS 2018

3 → 2 → 5} as Pareto-optimal with the aid of the P-NDQIO
algorithm. Consequently, this specific route is deemed to be
the sole surviving route in Fig 3. This is in contrast to Fig. 2,
where three more routes have been identified as surviving ones.
Recall from Fig. 2 that these routes do not lead to Paretooptimal routes in the last trellis stage. This in turn results in
the EQPO algorithm visiting one less route in the 3rd trellis
stage, i.e. not considering the sub-optimal route {1 → 4 →
2 → 3 → 5} as potentially Pareto-optimal.
V. C OMPLEXITY VERSUS ACCURACY D ISCUSSIONS
In this section, we will characterize the complexity imposed
by the EQPO Alg. presented in Alg. 2 and evaluate its heuristic
accuracy versus the complexity invested. Additionally, note
that since we had no quantum computer at our disposal, the
simulations of the QSAs were carried out using a classical
cluster. Explicitly, since the quantum oracle gate O [27]
calculates in parallel the UF vectors of all the legitimate routes
in the QD, they were pre-calculated. We note that this results
in an actual complexity higher than that of the full-search
method. Therefore, the employment of the quantum algorithms
in a quantum computer is essential for observing a complexity
reduction as a benefit of the QP. Hence, in our simulations, we
have made the assumption of employing a quantum computer
and we count the total number of O activations for quantifying
the EQPO’s complexity. This number would be the same for
both classical and quantum implementations. Note that in the
x
x
,
following analysis we will use the notation N(i)
≡ S(i)
x
x
where N(i) corresponds to the cardinality of the set S(i) .
Furthermore, our simulation results have been averaged over
108 runs. During each run we have randomly generated the
node’s locations as well as the interference levels experienced
by them with the aid of the respective distributions mentioned
in Section II. We have ensured that each run is uncorrelated
with the rest of the runs.
Let us now proceed by analytically characterizing the complexity imposed by our proposed algorithm.

A. Complexity
We will first characterize the complexity imposed by the
EQPO algorithm’s dynamic progamming framework, when
the exhaustive search is employed instead of the P-NDQIO
algorithm in Step 6 of Alg. 2. We will refer to this method
as the Classical Dynamic Programming (CDP) method and
we will use it as a benchmarker for assessing the complexity
reduction offered by the QP.
Prior to characterizing the EQPO algorithm and the CDP
surv
method we will analyze the the orders of the number N(i)
of
OPF
the surviving routes and of the number N(i) of the Paretooptimal routes identified across the first i trellis stages. As far
OPF
as the number N(i)
of the Pareto-optimal routes identified
across the first i trellis stages is concerned, the trellis graph
guiding the search for Pareto-optimal routes identifies more
Pareto-optimal routes, as it proceeds through more trellis

stages. Explicitly, its order can be formally expressed as
follows:
OPF
O(N(i)
) = O(ai NOPF ) = O(NOPF ), ∀i ∈ {1, . . . , Nnodes −1},
(13)
where ai corresponds to the fraction of the OPF identified by
the first i trellis stages. Naturally, this fraction ai approaches
unity as the number i of trellis stages moves closer to the
maximum number of hops.
surv
Moving on to the number N(i)
of the surviving routes
at the i-stage, it is equal to the number of Pareto-optimal
routes identified at the i-th trellis stage, based on Relaxation 1.
surv
OPF
is a fraction of the total number N(i)
of
Explicitly, N(i)
the Pareto-optimal routes identified across the first i trellis
surv
OPF
with bi ≤ 1
= bi N(i)
stages. Hence, we have N(i)
surv
∀i ∈ {1, . . . , Nnodes − 1}, since the set S(i) of Pareto-optimal
OPF
routes at the i-th trellis stage is included in the set S(i)
of Pareto-optimal routes identified at the first i trellis stages.
surv
) as follows:
Therefore we can evaluate the order O(N(i)
(13)

surv
OPF
O(N(i)
) = O(bi N(i)
) = O(bi ai NOPF ) = O(NOPF ). (14)

Consequently, in Eqs. (13) and (14), we have upper bounded
surv
the order O(N(i)
) of the number of surviving routes at the
OPF
i-th stage as well as the order O(N(i)
) of the number of
Pareto-optimal routes identified at the first i stages by the order
O(NOPF ) of the total number of Pareto-optimal routes, i.e. we
surv
OPF
have O(N(i)
) = O(N(i)
) = O(NOPF ). Naturally, Eq. (13)
and (14) will facilitate the complexity analysis, since they
render the aforementioned orders independent of the index i
of the trellis stages. Let us now proceed by characterizing the
complexity imposded by the CDP method.

1) CDP method’s complexity: Let us assume that there is a
gen
total of N(i)
generated routes arriving at the i-th trellis stage.
These particular routes are generated by the specific Paretooptimal routes identified at the previous trellis stage, which are
surv
N(i−1)
in total. Based on the aforementioned assumptions, the
number of generated routes arriving at the i-th trellis stage is
formulated as follows:
i
h
gen
surv
surv
Nnodes i ,
(Nnodes − 1 − i)i = O N(i−1)
N(i)
= N(i−1)
(14)

= O [NOPF Nnodes i] .

(15)

Since the set of Pareto-optimal routes of the previous trellis
stage are concatenated to the set of generated routes in Step 5
of Alg. 2, the total number of routes considered at the i-th
trellis stage is given by:
gen
OPF
routes
= N(i)
+ N(i−1)
N(i)

(13),(15)

=

O [NOPF Nnodes i] .

(16)

routes 2
Additionally, the CDP method performs O[(N(i)
) ] dominance comparisons, which we will refer to as the Cost
Function Evaluation (CFE), since each generated route has
to be compared to all of the routes considered. Therefore, the
total complexity imposed by the CDP method across all trellis
stages may be quantified in terms of the number of dominance

D. ALANIS ET AL.: A QUANTUM-AIDED DYNAMIC PROGRAMMING FRAMEWORK FOR PARETO OPTIMAL ROUTING IN WMHNS

comparisons, which is formulated as follows:
Nnodes
2 
X−1 
2
5
routes
= O(NOPF
Nnodes
),
O N(i)
LCDP =

(17)

i=1

where we have exploited the property
of the sum of squared
Pn
numbers [37], where we have i=1 i2 = O(n3 ).
2) EQPO algorithm’s complexity: Moving on to the EQPO
algorithm’s complexity analysis, the P-NDQIO algorithm is
activated once per trellis stage, based on Alg. 2. Note that
we will classify the complexity imposed by the P-NDQIO
into two different domains, namely that of the parallel and
that of the sequential complexity. To elaborate further, the
P-NDQIO algorithm also exploits the synergies between QP
and HP, which was utilized by the NDQIO algorithm of [30].
Explicitly, the parallel complexity, which is termed as “normalized execution time” in [30], is defined as the number of
dominance comparisons, when taking into account the degree
of HP. Therefore, it may be deemed to be commensurate with
the algorithm’s actual normalized execution time. By contrast,
the sequential complexity, which is termed as “normalized
power consumption” in [30], is defined as the total number
of dominance comparisons, without considering the potential
degree of HP. Hence, this specific complexity may be deemed
to be commensurate with the algorithm’s normalized power
consumption, as elaborated in [30] as well.
Let us now proceed by characterizing the complexity of
the individual sub-processes of the P-NDQIO process. During
each trellis stage, the P-NDQIO algorithm activates its BWBBHT-QSA step. This step invokes the BBHT-QSA once;
however, since the quantum circuits of the original NDQIO
algorithm are utilized, each activation of the quantum oracle,
namely the operator UG in [30, Fig. 8], compares each of the
generated routes to all the routes comprising the OPF identified
so far. Since this set of comparisons is carried out in parallel,
OPF
a single activation imposes a single CFE and N(i)
CFEs in
the parallel and sequential domains, respectively. Note that the
surv
BW-BBHT-QSA process will be activated (N(i)
+ 2) times
during a single trellis stage, since we opted for repeating this
step for an additional iteration, when the BBHT-QSA fails
to identify a valid route. Therefore, the parallel and sequential complexity imposed by the BW-BBHT-QSA process are
quantified as follows:
routes
surv
),
+ 2)LBBHT (N(i)
= (N(i)
LBW,P
(i)
p
= O(NOPF NOPF Nnodes i),

(18)
(19)

chains, it has been demonstrated in [30] that the complexity
imposed by a single of BBHT-QSA chain - which leads to the
identification of a single Pareto-optimal route - is identical
to that of the so-called Durr-Hoyer Algorithm
(DHA) [26],
√
namely on the order of LDHA (N ) = O( N ) in terms of the
number of quantum oracle gate activations. As for the latter,
the Ug′ quantum operator of [30, Fig. 7] has been utilized,
which implements a dominance comparison. Explicitly, each
activation of this operator imposes a parallel complexity of
1/K CFEs and a sequential complexity of a single CFE,
owing to the parallel implementation of the UF comparisons.
Therefore, the parallel and sequential complexity imposed by
the BBHT-QSA chains are quantified as follows:
Lchain,P
(i)
Lchain,S
(i)

X

(20)
(21)

surv
Recall that the term N(i)
in Eqs. (18) and (20) corresponds to
the number of Pareto-optimal routes identified . Additionally,
for the calculation of the orders of complexity we have relied
on the fact that the BBHT-QSA
has a complexity on the order
√
of LBBHT (N ) = O( N ) as demonstrated both in [30] and in
[25]. Moving on to the complexity imposed by the BBHT-QSA

=

surv
routes
N(i)
LDHA (N(i)
),

(22)
(23)
(24)
(25)

N surv

LSR,P
(i)

(i)
1 X
OPF
2
(j + N(i−1)
) = O(NOPF
),
=
K j=1

(26)

surv
N(i)

LSR,S
=
(i)

X

2
OPF
) = O(NOPF
).
(j + N(i−1)

(27)

j=1

Recall from Eqs. (19), (21), (23), (25), (26) and (27) that
surv
we used Eqs. (13) and (14), where we have O(N(i)
) =
OPF
O(N(i) ) = O(NOPF ) with NOPF corresponding to the total
number of Pareto-optimal routes. Let us now proceed with
the evaluation of the total parallel and sequential complexities
of the EQPO algorithm. In the worst-case scenario the EQPO
algorithm will process (Nnodes −1) trellis stages, corresponding
to the maximum possible number of hops, whilst visiting each
node at most once. Thus, the total parallel and sequential
complexities imposed by the EQPO algorithm are quantified
as follows:
LP
EQP O =
=

j=0

surv
routes
+ N(i)
LBBHT (N(i)
),
p
2
= O(NOPF NOPF Nnodes i).

routes
LDHA (N(i)
),
K
p
= O(NOPF NOPF Nnodes i),

=

Finally, as for the OPF-SR dominance comparisons of Step 10
of Alg. 1, the parallel and sequential complexity imposed by
this process are quantified as follows:

LSEQP O =

OPF
routes
)+
(j + N(i−1)
) LBBHT (N(i)

surv
N(i)

p
= O(NOPF NOPF Nnodes i).

surv
N(i)

LBW,S
=
(i)

11

=

Nnodes
X−1

+ LSR,P
,
LBW,P
+ Lchain,P
(i)
(i)
(i)

i=1
3/2 2
),
O(NOPF Nnodes
Nnodes
−1
X
LBW,S
+
(i)
i=1
5/2 2
).
O(NOPF Nnodes

(28)
(29)

+ LSR,S
Lchain,S
(i)
(i) ,

(30)
(31)

Note that in Eqs. (29) and (31) we have exploited the
specific
of the sum of square roots, where we
√
Pnproperty
have
i
=
O(n3/2 ) [37]. Observe from Eqs. (17)
i=1
and (29) that the EQPO algorithm achieves a parallel complexity reduction against
√ the CDP method by a factor on
3
the order of O(Nnodes
NOPF ). Additionally, the respective
sequential complexity reduction is by a factor on the order

12

√
3
of O(Nnodes
/ NOPF ), based on Eqs. (17) and (31). Hence,
the EQPO imposes a lower sequential complexity √
than the
3
CDP method, as long as we have O(Nnodes
) > O( NOPF ).
As far as the EQPO algorithm’s predecessors are concerned,
it has been proven in [30] that the NDQO algorithm imposes
identical parallel and
√ sequential complexities, which are on
the order of O(N N ). By contrast, the NDQIO algorithm
imposes a parallel and √a sequential complexity,
which are
√
2
N ), respectively,
on the order of O(NOPF N ) and O(NOPF
where N corresponds to the total number of legitimate routes.
Consequently, the complexity imposed by both the√NDQO
and the NDQIO algorithms is proportional to O( N ) in
both domains, yielding an exponential increase in the order
of complexity as the number nodes increases. By contrast,
both the EQPO algorithm and the CDP method exhibit a
complexity order similar to polynomial scaling, since its has
been demonstrated in [30, Fig. 11] that the total number NOPF
of Pareto-optimal routes increases at a significantly lower rate
than that of the total number N of routes.
Let us now proceed by presenting the average parallel
and the average sequential complexity imposed both by the
EQPO algorithm and by the CDP method, which are shown
in Figs. 4a and 4b, respectively. We will compare the complexities imposed by the aforementioned algorithms to those
of the Brute-Force (BF) method as well as to those of the
EQPO algorithm’s predecessors, namely the NDQO and the
NDQIO algorithms. The aforementioned methods consider the
entire set of legitimate routes, hence they have no database
correlation exploitation capabilities. Additionally, the NDQO
algorithm and the BF method do not employ any HP scheme,
thus their respective parallel and sequential complexities are
identical. As far as the average complexity of the CDP method
is concerned, observe in Figs. 4a and 4b that it requires a
higher number of CFEs than the BF method for WMHNs
having less than 8 nodes. This parallel complexity overhead
is justified by the fact that the number NOPF of Paretooptimal routes w.r.t. the total number N of legitimate routes
is relatively high. This in turn yields an increase in the
fraction of trellis nodes that are classified as survivors, hence
leading to more dominance comparisons. However, this trend
is reversed for WMHNs having more than 7 nodes, where
the CDP method exhibits a complexity reduction compared
to the BF method. More specifically, for WMHNs constituted
by 9 nodes, this complexity reduction is close to an order of
magnitude. Still referring to 9-node WMHNs, the CDP method
imposes a slightly higher parallel complexity than that of the
NDQO algorithm, while it matches the sequential complexity
of the NDQIO algorithm for the same 9-node network, based
on Figs. 4a and 4b, respectively.
Moving on to the average parallel complexity of the EQPO
algorithm, observe in Fig. 4a that the EQPO algorithm imposes
fewer CFEs than the rest of the algorithms considered for
WHMNs having more than 5 nodes. Explicitly, this complexity
reduction becomes more substantial, as the number of nodes
increases, reaching a parallel complexity reduction of almost
an order of magnitude for 9-node WMHNs, when compared
to the NDQIO algorithm, which is capable of exploiting the
HP as well. As for its sequential complexity, observe in

IEEE TRANSACTIONS ON COMMUNICATIONS 2018

Fig. 4b that the EQPO algorithm imposes more CFEs than
the rest of the algorithms for WMHNs having less than 7
nodes. This may be justified by the relatively small number
of surviving routes, which does not allow the QP to excel
by providing beneficial complexity reduction. However, this
trend is reversed for WMHNs having more than 6 nodes,
where the number of surviving routes becomes higher. More
specifically for 9-node WMHNs, the EQPO algorithm begins to impose a sequential complexity reduction w.r.t. all
the remaining algorithms considered. Additionally, observe
in Figs. 4a and 4b that the EQPO algorithm’s complexity
increases with a much lower gradient, as the number of nodes
increases, when compared to the full-search-based algorithms,
namely to the BF method as well as to the NDQO and the
NDQIO algorithms. Explicitly, this is justified by the “almost
polynomial” order of complexity, as demonstrated in Eqs. (29)
and (31).
B. Accuracy
Having elaborated on the complexity imposed by the EQPO
let us now proceed by discussing its heuristic accuracy. Since
our design target is to identify the entire set of Pareto-optimal
routes, we will evaluate the EQPO algorithm’s accuracy versus
the complexity imposed in terms of two metrics, namely that
of the average Pareto distance E[Pd ] and that of the average
Pareto complection E[C]. The same set of metrics have been
considered in [30] for the evaluation of NDQIO algorithm’s
accuracy as well. To elaborate further, the Pareto distance of
a particular route is defined as the probability of this specific
route being dominated by the rest of the legitimate routes.
Explicitly, given a set of Pareto-optimal routes identified
by the EQPO algorithm, their average Pareto distance is a
characteristic of the OPF, since it provides insights into the
proximity of the exported OPF to the true OPF. Naturally, a
Pareto distance having a value of E[Pd ] = 0 implies that the
OPF identified by the EQPO is fully constituted by true Paretooptimal routes. By contrast, the average Pareto completion is
defined as the specific fraction of the solutions on the true OPF
identified by the EQPO. Therefore, our goal is to achieve a
Pareto completion as close to E[C] = 1 as possible.
Having defined the performance metrics, let us now present
the performance versus complexity results of the EQPO algorithm, which are shown in Fig. 5 for 7-node WMHNs.
The reason we have evaluated the aforementioned metrics
for 7-node WMHNs is for the sake of comparison to the
methods analyzed in [19] as well as in [30]. Apart from the
NDQO and NDQIO algorithms, we have used as benchmarks
two additional classical evolutionary algorithms5, namely the
NSGA-II and the MO-ACO. Using the same convention as in
[19] and [30], we have set the number of individuals equal
to the number of generations and we have matched the total
parallel complexity imposed by these classical algorithms to
that of the NDQO algorithm, since the NDQO algorithm
appears to impose the highest parallel complexity, based on
Fig. 4a. As for their total sequential complexity we have set
5 The readers should refer to [19] and to [18] for a detailed description of
the MO-ACO and the NSGA-II, respectively.

D. ALANIS ET AL.: A QUANTUM-AIDED DYNAMIC PROGRAMMING FRAMEWORK FOR PARETO OPTIMAL ROUTING IN WMHNS

107

107

NDQIO Alg.
NDQO Alg.
BF Method
CDP Method
EQPO Alg.

105

106

Total Number of CFEs

106

Total Number of CFEs

13

104
103
102
10

105
104
103

NDQIO Alg.
NDQO Alg.
BF Method
CDP Method
EQPO Alg.

102
10

1

1
4

5

6

7

8

9

Number of Nodes, Nnodes
(a) Parallel Complexity

4

5

6

7

8

9

Number of Nodes, Nnodes
(b) Sequential Complexity

Figure 4: EQPO Alg. (a) parallel and (b) sequential complexity quantified in terms of the number of CFEs. The results have
been averaged over 108 runs.
it to that of the NDQIO algorithm. Consequently, we have
considered employing 19 individuals over 19 generations for
the parallel complexity matching and 29 individuals over 29
generations for the sequential complexity matching for both
the NSGA-II and the MO-ACO algorithm.
Let us now proceed by elaborating on the average Pareto
distance exhibited by 7-node WMHNs versus the parallel
complexity invested, as portrayed in Fig. 5a. Observe in this
figure that the EQPO algorithm performs optimally – in the
sense that no suboptimal routes are included in the OPF –
for about 130 CFEs and then exhibits an error floor around
6 · 10−6 . Similar trends are observed for the classical NSGAII and for MO-ACO algorithm as well as for the quantumassisted NDQO algorithm; the classical benchmark algorithms
both exhibit an error floor around 10−3 , while the respective
NDQO algorithm’s error floor is around 7 · 10−9. By contrast,
the NDQIO algorithm initially has an error floor of about
3 · 10−5 , which then decays to infinitesimally low levels,
when more CFEs are invested owing to its OPF-SR process
[30]. This specific trend is visible in Fig. 5a, where the
NDQIO algorithm outperforms the NDQO technique in terms
of their E[Pd ] beyond 8842 CFEs in the sequential complexity
domain. Additionally, the NDQIO algorithm begins to exhibit
a lower E[Pd ] than that of the EQPO algorithm after 498 and
2932 CFEs in the parallel and sequential domains, respectively.
Let us now provide some further insights into the significance of the aforementioned error floors. Explicitly, a
particular route is considered suboptimal, if there exists even
just a single route dominating it, i.e. if it has a Pareto distance
higher than or equal to Pdth = 1/N , where N corresponds
to the total number of legitimate routes. This threshold is
visually portrayed with the aid of the dashed and dotted
horizontal lines in Figs. 5a and 5b. Hence, we can normalize
the results w.r.t. this threshold for exporting the probability of
a specific route becoming suboptimal. Consequently, EQPO
algorithm’s error floor is translated into a probability of a

specific route being suboptimal, which is equal to 0.2%, while
the respective probability of the NDQO algorithm is equal
to 2 · 10−6 . Additionally, the respective probabilities of the
classical benchmark algorithms are about 33% and 3.3%, when
parallel and sequential complexity are considered, respectively.
Consequently, the EQPO algorithm’s probability of opting for
a suboptimal route may be regarded as negligible.
The evaluation of the average Pareto completion probability
versus the parallel and the sequential complexity are shown in
Figs. 5c and 5d. Note that the subplots inside these figures
portray the portion of unidentified true Pareto-optimal routes,
as encapsulated by the expression of 1 − E[C]. Explicitly,
we will utilize this metric for assessing the error floor w.r.t.
the E[C], which may not be visible from the main plots.
Additionally, note that we examined both E[Pd ] and E[C]
versus the parallel and sequential complexity imposed up to
the maximum value observed by the EQPO algorithm. As far
as the EQPO algorithm’s average Pareto completion versus the
parallel complexity is concerned, observe in Fig. 5c that the
EQPO is capable of identifying a higher portion of the true
OPF, when compared to the rest of the algorithms examined,
while considering the same number of CFEs in the parallel
complexity domain. Explicitly, the EQPO algorithm succeeds
in identifying almost the entire set of Parero-optimal routes,
since it is only incapable of identifying as few as 0.1% of
the entire true OPF. This error floor is reached after 1301 and
14651 CFEs in the parallel and sequential complexity domains,
respectively, as it can be verified by Figs. 5c and 5d.
By contrast, this trend is not echoed in the sequential
complexity domain. To elaborate further, observe in Fig. 5b
that the EQPO algorithm remains more efficient than its
classical counterparts. On the other hand, while it is indeed
more efficient than the NDQO algorithm up to a complexity
budget of 2147 sequential CFEs, it identifies less Paretooptimal routes than the NDQO algorithm. The same trend
is observed for the NDQIO algorithm as well for a com-

14

IEEE TRANSACTIONS ON COMMUNICATIONS 2018

10−1

1/N

10−3

10−3

10−5

10−5

10−7

EQPO
NDQIO
NDQO
NSGA-II
MO-ACO

10−9
10−11
10−13

0

260

520

780

1040

E[Pd ]

E[Pd ]

10−1

1/N

10−7

EQPO
NDQIO
NDQO
NSGA-II
MO-ACO

10−9
10−11
10−13

1300

0

Parallel Complexity in CFEs

2930

5860

8790

11720

14650

Sequential Complexity in CFEs

(a)

(b)

1

1

5

5

EQPO
NDQIO
NDQO
NSGA-II
MO-ACO

5

10−2

260

10

10−1

EQPO
NDQIO
NDQO
NSGA-II
MO-ACO

5

10−4

2

0

2

520

0

325
780

650

975
1040

1300
1300

Parallel Complexity in CFEs
(c)

1 − E[C]

10−1

E[C]

2

1 − E[C]

E[C]

1
1

−1

10−2
10−3
10−4

0

3362 6724 10086 13448

2

0

2930

5860

8790

11720

14650

Sequential Complexity in CFEs
(d)

Figure 5: EQPO algorithm performance in terms of its Pareto dinstance (a,b) and its Pareto Completion (c,d) versus the parallel
complexity (a,c) and the sequential complexity (b,d) for required 7-node WHMNs. The results have been averaged over 108
runs.

plexity budget of 4794 sequential CFEs. Nevertheless, this
discrepancy between the parallel and sequential complexity is
expected to be decreased, as the number of nodes increases.
This is justified by the fact that the EQPO algorithm imposes
a lower sequential complexity as the nodes proliferate, as seen
in Fig. 4b.

Last but not least, the results portrayed on Fig. 5 rely on
the intelligent central node having perfect knowledge both of
the nodes’ geo-locations and of the interference power levels
experienced by them. This fundamental assumption, albeit
impractical, provides us with the upper bound of the achievable
performance of the routing schemes considered. Explicitly,
despite its impractical nature, it facilitates a fair comparison
of the EQPO algorithm to its predecessors in terms of their
complexity and heuristic accuracy, which is the main focus
of this treatise. Intuitively, a practical network information
update process would result in both approximated and outdated
network information, thus degrading the results of Fig. 5, while
maintaining the complexity per routing routing optimization
at a similar order. Note that we plan on characterizing these
imperfections and conceive a practical network information
update scheme in our future work.

VI. C ONCLUSIONS
In this treatise we have exploited the correlations in the
formation of the Pareto-optimal routes for the sake of achieving a routing complexity reduction. In this context, we have
first developed an optimal dynamic programming framework,
which transforms the multi-objective routing problem into
a decoding problem. However, this optimal framework imposes a high complexity. For this reason, we relaxed the
aforementioned framework and proposed the EQPO algorithm,
which is empowered by the P-NDQIO algorithm and thus
jointly exploits the synergies between the QP and the HP
along with the potential correlation in the formation of the
Pareto-optimal routes. We then analytically characterized the
complexity imposed by the EQPO algorithm showed that it
is capable of solving the multi-objective routing problem in
near-polynomial time. In fact, the EQPO achieved a parallel
complexity reduction of almost an order of magnitude and
a sequential complexity reduction by a factor of 3 for 9node WMHNs. Finally, we demonstrated with the aid of
simulations that this complexity reduction only imposes an
almost negligible error, which was found to be 0.2% and 0.1%
in terms of the average Pareto distance and the average Pareto
completion probability for 7-node WMHNs.

D. ALANIS ET AL.: A QUANTUM-AIDED DYNAMIC PROGRAMMING FRAMEWORK FOR PARETO OPTIMAL ROUTING IN WMHNS

A PPENDIX A
P ROOF OF P ROPOSITION 1
(j)

Proof. Let
us
consider
the
route
xg
=
{SN →R̄i →Rj →DN } generated by the route x. Based
on Eq. (9), the UFs associated with this specific route are
equal to:
fk (x(j)
g ) = fk (SN →R̄i ) + fk (R̄i →Rj ) + fk (Rj →DN ).
(32)
Additionally, the sub-route x′ is associated with the following
UFs
fk (x′ ) = fk (SN →R̄i ).
(33)
Since we have fk (x) > 0, ∀x from Eq. (9), the sub-route
(j)
x′ strongly dominates the route xg based on Eqs. (32) and
(j)
′
(33), i.e. we have f (x ) ≻ f (xg ). Since now there is a specific
route xd from the SN to DN that weakly dominates the subroute x′ , i.e. we have f (xd )  f (x′ ), the route xd strongly
(j)
dominates the route xg as well, yielding:
f (xd )  f (x′ ) ≻ f (x(j)
g ),
f (xd ) ≻

(34)

f (x(j)
g )

(35)
(j)

Consequently, based on Eq. (35) the route xg cannot be
Pareto-optimal, since it is strongly dominated by the route
xd .

R EFERENCES
[1] Z. Jiao, B. Zhang, C. Li, and H. T. Mouftah, “Backpressure-based
routing and scheduling protocols for wireless multihop networks: A
survey,” IEEE Wireless Communications, vol. 23, pp. 102–110, February
2016.
[2] B. Alawieh, Y. Zhang, C. Assi, and H. Mouftah, “Improving spatial
reuse in multihop wireless networks - a survey,” IEEE Communications
Surveys Tutorials, vol. 11, pp. 71–91, Aug 2009.
[3] Y. Chen, S. Zhang, S. Xu, and G. Y. Li, “Fundamental trade-offs on
green wireless networks,” IEEE Communications Magazine, vol. 49,
pp. 30–37, June 2011.
[4] H. Yetgin, K. T. K. Cheung, M. El-Hajjar, and L. Hanzo, “Networklifetime maximization of wireless sensor networks,” IEEE Access, vol. 3,
pp. 2191–2226, 2015.
[5] A. Abdulla, H. Nishiyama, J. Yang, N. Ansari, and N. Kato, “Hymn:
A novel hybrid multi-hop routing algorithm to improve the longevity of
wsns,” IEEE Transactions on Wireless Communications, vol. 11, no. 7,
pp. 2531–2541, 2012.
[6] L. Tan, Z. Zhu, F. Ge, and N. Xiong, “Utility maximization resource
allocation in wireless networks: Methods and algorithms,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 45, pp. 1018–
1034, July 2015.
[7] Y. Shi, Y. T. Hou, and H. Sherali, “Cross-layer optimization for data rate
utility problem in UWB-based ad hoc networks,” IEEE Transactions on
Mobile Computing, vol. 7, pp. 764–777, June 2008.
[8] M. Caleffi, I. F. Akyildiz, and L. Paura, “Opera: Optimal routing metric
for cognitive radio ad hoc networks,” IEEE Transactions on Wireless
Communications, vol. 11, pp. 2884–2894, August 2012.
[9] R. Banirazi, E. Jonckheere, and B. Krishnamachari, “Heat-Diffusion:
Pareto optimal dynamic routing for time-varying wireless networks,” in
IEEE INFOCOM 2014 - IEEE Conference on Computer Communications, pp. 325–333, April 2014.
[10] S. Dasgupta, C. H. Papadimitriou, and U. Vazirani, Algorithms.
McGraw-Hill, Inc., 2006.
[11] D. Ramirez and B. Aazhang, “Optimal routing and power allocation for
wireless networks with imperfect full-duplex nodes,” IEEE Transactions
on Wireless Communications, vol. 12, pp. 4692–4704, September 2013.
[12] J. Zuo, C. Dong, H. V. Nguyen, S. X. Ng, L. L. Yang, and L. Hanzo,
“Cross-layer aided energy-efficient opportunistic routing in ad hoc
networks,” IEEE Transactions on Communications, vol. 62, pp. 522–
535, February 2014.

15

[13] C. Luo, S. Guo, S. Guo, L. T. Yang, G. Min, and X. Xie, “Green
communication in energy renewable wireless mesh networks: Routing,
rate control, and power allocation,” IEEE Transactions on Parallel and
Distributed Systems, vol. 25, pp. 3211–3220, Dec 2014.
[14] Q. You, Y. Li, M. S. Rahman, and Z. Chen, “A near optimal routing
scheme for multi-hop relay networks based on Viterbi algorithm,”
in 2012 IEEE International Conference on Communications (ICC),
pp. 4531–4536, June 2012.
[15] Y. Wang, M. Z. Bocus, and J. P. Coon, “Dynamic programming for route
selection in multihop fixed gain amplify-and-forward relay networks,”
IEEE Communications Letters, vol. 17, pp. 932–935, May 2013.
[16] J. Yao, S. Feng, X. Zhou, and Y. Liu, “Secure routing in multihop
wireless ad-hoc networks with decode-and-forward relaying,” IEEE
Transactions on Communications, vol. 64, pp. 753–764, Feb 2016.
[17] K. Deb, “Multi-objective optimization,” in Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques
(E. K. Burke and G. Kendall, eds.), pp. 403–449, Boston, MA: Springer
US, 2014.
[18] H. Yetgin, K. Cheung, and L. Hanzo, “Multi-objective routing optimization using evolutionary algorithms,” in IEEE Wireless Communications
and Networking Conference (WCNC), pp. 3030–3034, 2012.
[19] D. Alanis, P. Botsinis, S. X. Ng, and L. Hanzo, “Quantum-assisted
routing optimization for self-organizing networks,” IEEE Access, vol. 2,
pp. 614–632, 2014.
[20] B. Gurakan, O. Ozel, and S. Ulukus, “Optimal energy and data routing
in networks with energy cooperation,” IEEE Transactions on Wireless
Communications, vol. 15, pp. 857–870, Feb 2016.
[21] M. Camelo, C. Omaa, and H. Castro, “QoS routing algorithm based on
multi-objective optimization for wireless mesh networks,” in 2010 IEEE
Latin-American Conference on Communications (LATINCOM), pp. 1–6,
2010.
[22] F. Martins, E. Carrano, E. Wanner, R. H. C. Takahashi, and G. Mateus,
“A hybrid multiobjective evolutionary approach for improving the performance of wireless sensor networks,” IEEE Sensors Journal, vol. 11,
no. 3, pp. 545–554, 2011.
[23] M. Lopez-Ibanez and T. Stutzle, “The automatic design of multiobjective
ant colony optimization algorithms,” IEEE Transactions on Evolutionary
Computation, vol. 16, pp. 861–875, Dec 2012.
[24] L. K. Grover, “A fast quantum mechanical algorithm for database
search,” in Proceedings of the twenty-eighth annual ACM symposium
on Theory of computing, pp. 212–219, ACM, 1996.
[25] M. Boyer, G. Brassard, P. Hyer, and A. Tapp, “Tight bounds on quantum
searching,” Fortschritte der Physik, vol. 46, no. 4-5, pp. 493–505, 1998.
[26] C. Durr and P. Høyer, “A quantum algorithm for finding the minimum,”
arXiv preprint quant-ph/9607014, 1996.
[27] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum
information. Cambridge university press, 2010.
[28] C. Wang, H. Chen, and E. Jonckheere, “Quantum versus simulated
annealing in wireless interference network optimization,” Scientific Reports, vol. 6, no. 25797, 2016.
[29] C. Wang, E. Jonckheere, and T. Brun, “Differential geometric treewidth
estimation in adiabatic quantum computation,” Quantum Information
Processing, vol. 15, pp. 3951–3966, Oct 2016.
[30] D. Alanis, P. Botsinis, Z. Babar, S. X. Ng, and L. Hanzo, “Nondominated quantum iterative routing optimization for wireless multihop
networks,” IEEE Access, vol. 3, pp. 1704–1728, 2015.
[31] C. Zalka, “Grover’s quantum searching algorithm is optimal,” Physical
Review A, vol. 60, no. 4, p. 2746, 1999.
[32] D. Alanis, J. Hu, P. Botsinis, Z. Babar, S. X. Ng, and L. Hanzo,
“Quantum-assisted joint multi-objective routing and load balancing for
socially-aware networks,” IEEE Access, vol. 4, pp. 9993–10028, 2016.
[33] D. H. Lehmer, “Teaching combinatorial tricks to a computer,” in Proc.
Sympos. Appl. Math. Combinatorial Analysis, vol. 10, pp. 179–193,
1960.
[34] R. Steele and L. Hanzo, Mobile radio communications: second and third
generation cellular and WATM systems. Wiley - IEEE, J. Wiley, 1999.
[35] L. Hanzo, S. X. Ng, W. Webb, and T. Keller, Quadrature amplitude
modulation: From basics to adaptive trellis-coded, turbo-equalised and
space-time coded OFDM, CDMA and MC-CDMA systems. IEEE PressJohn Wiley, 2004.
[36] S. Yang, X. Xu, D. Alanis, S. X. Ng, and L. Hanzo, “Is the lowcomplexity mobile relay aided FFR-DAS capable of outperforming the
high-complexity CoMP?,” IEEE Transactions on Vehicular Technology,
vol. 65, pp. 2154–2169, April 2016.
[37] M. Abramowitz and I. A. Stegun, Handbook of mathematical functions:
with formulas, graphs, and mathematical tables, vol. 55. Courier
Corporation, 1964.

16

[38] W. Zhang, M. F. Brejza, T. Wang, R. G. Maunder, and L. Hanzo, “Irregular trellis for the near-capacity unary error correction coding of symbol
values from an infinite set,” IEEE Transactions on Communications,
vol. 63, pp. 5073–5088, Dec 2015.
[39] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist
multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on
Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.

IEEE TRANSACTIONS ON COMMUNICATIONS 2018

