1

Latency Minimization for Intelligent Reflecting

Surface Aided Mobile Edge Computing
Tong Bai, Member, IEEE, Cunhua Pan, Member, IEEE,
Yansha Deng, Member, IEEE, Maged Elkashlan, Member, IEEE,
Arumugam Nallanathan, Fellow, IEEE and Lajos Hanzo, Fellow, IEEE
arXiv:1910.07990v2 [eess.SP] 21 Nov 2019

Abstract

Computation off-loading in mobile edge computing (MEC) systems constitutes an efficient paradigm
of supporting resource-intensive applications on mobile devices. However, the benefit of MEC cannot
be fully exploited, when the communications link used for off-loading computational tasks is hostile.
Fortunately, the propagation-induced impairment may be mitigated by intelligent reflecting surfaces
(IRS), which are capable of enhancing both the spectral- and energy-efficiency. Specifically, an IRS
comprises an IRS controller and a large number of passive reflecting elements, each of which may
impose a phase shift on the incident signal, thus collaboratively improving the propagation environment.
In this paper, we investigate the beneficial role of IRSs in MEC systems, where single-antenna devices
may opt for off-loading a fraction of their computational tasks to the edge computing node via a multi-
antenna access point with the aid of an IRS. We formulate pertinent latency-minimization problems
for both single-device and multi-device scenarios, subject to practical constraints imposed on both the
edge computing capability and the IRS phase shift design. To solve this problem, we invoke the block
coordinate descent (BCD) technique to decouple the original problem into two subproblems and then
alternatively optimize the computing and communications settings. Optimal solutions are provided for
the associated computing design subproblem, while the communications design subproblem is solved
using a low-complexity iterative algorithm, which is guaranteed to converge to its Karush-Kuhn-Tucker
(KKT) point. It is demonstrated that our IRS-aided MEC system is capable of significantly outperforming
the conventional MEC system operating without IRSs. Quantitatively, about 20 % computational latency
reduction is achieved over the conventional MEC system in a single cell associated of a 300 m radius,
relying on a 5-antenna access point and 5 active devices.

T. Bai, C. Pan, M. Elkashlan and A. Nallanathan are with the School of Electronic Engineering and Computer Science, Queen
Mary University of London, London E1 4NS, U.K. (e-mail: t.bai@qmul.ac.uk, c.pan@qmul.ac.uk, maged.elkashlan@qmul.ac.uk,
a.nallanathan@qmul.ac.uk). Y. Deng is with the Department of Engineering, King’s College London, London, WC2R 2LS, U.K.
(e-mail: yansha.deng@kcl.ac.uk). L. Hanzo is with the School of Electronics and Computer Science, University of Southampton,
Southampton, SO17 1BJ, U.K. (e-mail: lh@ecs.soton.ac.uk).
 2

I. I NTRODUCTION

A. Motivation and Scope

In the Internet-of-Things (IoT) era, myriads of machines and sensors are envisioned to be con-
nected [1]. However, since these devices typically have limited computing capabilities, resource-
intensive applications cannot be readily supported by these devices due to their resultant excessive
computational latency. Aimed at tackling this issue, powerful computing nodes can be deployed
at the edge of the network (typically co-located with the access points (APs)) [2]. As a benefit,
the computational latency of these resource-intensive applications can be reduced, by employing
both local computing on the devices and edge computing for processing these computational
tasks, provided that these tasks can be successfully off-loaded. This paradigm is referred to
as mobile edge computing (MEC) [3]–[14]. At the time of writing, the potential of this MEC
paradigm has not been fully exploited, predominantly because the computation off-loading link
is far from perfect. For example, the devices located at the cell edge typically suffer from a low
off-loading success rate, and/or their computation off-loading may impose higher latency than
computing their tasks locally. Hence these devices have to rely on their own computing resources,
which is however often incapable of supporting resource-intensive applications. Therefore, it is
imperative to improve the performance of MEC systems from a communications perspective.
The recent advances in the programmable meta-materials [15] facilitate the construction of
intelligent reflecting surfaces (IRS) [16] for enhancing both the spectral- and energy-efficiency
of wireless communications. Specifically, an IRS is comprised of an IRS controller and a large
number of passive reflecting elements. Under the instructions of the IRS controller, each IRS
reflecting element is capable of adjusting both the amplitude and the phase of the signals reflected,
thus collaboratively modifying the signal propagation environment. The gain attained by IRSs
is based on the combination of both the virtual array gain and the reflection-aided beamforming
gain. To elaborate, the virtual array gain can be achieved by combining both the direct and
IRS-reflected signals, while the reflection-aided beamforming gain is realized by proactively
controlling the phase shift induced by the IRS elements. By beneficially combining these two
types of gains, the IRS becomes capable of boosting the devices’ off-loading success rate, hence
improving the potential of MEC systems. In this treatise, we focus our attention on investigating
the role of the IRS in MEC systems.
 3

B. Related Works

1) Design of Mobile Edge Computing Systems: At the current state-of-the-art, MEC systems
can be categorized into [5]: single-user [6]–[9] and multi-user systems [10]–[14]. Among the
design metrics of single-user MEC systems, the computation off-loading strategy plays a crucial
role. More explicitly, the binary off-loading strategy of [6] was proposed to decide whether the
task is executed locally at the mobile device or remotely at the edge-cloud node. By contrast,
Wang et al. [7] conceived a partial off-loading scheme for data-partitioning oriented applications,
where a fraction of the data can be processed at the mobile device, while the rest at the edge.
However, in realistic multi-user systems, inter-user interference is imposed both on the radio
communications link and on the computing node at the edge, which may erode the overall
performance of the MEC system. In order to cope with this hindrance, Sardellitti et al. [10]
jointly optimized the transmit precoding matrices and the computational resources allocated to
each user in a multi-cell multi-user scenario. For the system where the devices have to make
their off-loading decisions locally, Chen et al. [11] provided a distributed joint computation off-
loading and channel selection policy relying on classic game theory. Recently, a specific user
association scheme was also developed for multi-user systems served by multiple edge computing
nodes [13], while a mobility-aware dynamic service scheduling algorithm was proposed for MEC
systems [14]. At the time of writing, the computation offloading issue of the devices in the face
of hostile communications environments has not been well addressed. Against this background,
in this paper we improve the performance by invoking IRSs. Let us now continue by reviewing
the relevant research contributions on IRSs as follows.
2) Intelligent Reflecting Surface Aided Wireless Networks: In order to explore the benefits of
IRSs in wireless communications, extensive research efforts have been invested into their ergodic
capacity analysis [17], channel estimation [18] and practical reflection phase shift modeling [19]
as well as into the associated phase shift design [20]–[27]. Specifically, a joint design of the IRS
phase shift and of the precoding at the AP was proposed for minimizing the transmit power,
while maintaining the target receive signal-to-interference-plus-noise ratio (SINR) [20], relying
on the sophisticated techniques of the semidefinite relaxation and of alternating optimization.
These investigations were then extended to the more practical discrete phase shift setting [21].
However, the excessive computational complexity of the algorithm developed in [20] prohibits its
application in large-scale IRSs. In order to reduce the complexity, Guo et al. [22] proposed three
 4

low-complexity algorithms, while Pan et al. [24] provided a pair of majorization-minimization

(MM) algorithms and complex circle manifold methods for multi-cell scenarios. Furthermore,
in order to reduce the overhead during the IRS channel estimation, Yang et al. [27] grouped
the IRS elements, where each group shares the same phase shift coefficient, and optimized
the power allocation and phase shift in orthogonal frequency division multiplexing (OFDM)-
based wireless systems. Apart from the conventional communications scenarios, the role of
IRSs was also investigated both in terms of improving physical-layer security [28]–[31] and
simultaneous wireless information and power transfer (SWIPT) [32], [33], where substantial
gains were achieved. These impressive research contributions inspired us to exploit the beneficial
role of IRSs in MEC systems.

C. Contributions and Organizations

Our main contribution is the employment of IRSs in MEC systems and the design of a joint
computing and communications scheme for minimizing the computational latency of IRS-aided
MEC systems, detailed as follows.
• New IRS-aided MEC system design and latency minimization problem formulation: In order
to further exploit the potential of MEC systems, we first propose IRS-aided MEC systems,
for assisting the computational task off-loading of mobile devices. A latency-minimization
problem is formulated for multi-device scenarios, which optimizes the computation off-
loading volume, the edge computing resource allocation, the multi-user detection (MUD)
matrix, and the IRS phase shift, subject to both the total edge computing capability and to the
IRS phase shift constraints. Owing to the coupling effect of multiple optimization variables,
the latency-minimization problem cannot be solved directly. Hence we decouple the original
problem into two subproblems for alternatively optimizing computing and communications
settings, relying on the block coordinate descent (BCD) technique.
• Computing design: Given a fixed communications setting, we decouple the computation off-
loading volume and the edge computing resource allocation, again using the BCD technique.
Our analysis reveals that given a fixed edge computing resource allocation, the optimal
computation off-loading volume can be determined by assuming the equivalence of the
latency induced by local computing and by edge computing. Given a fixed computation
off-loading volume, the subproblem is proved to be a convex problem and the optimal edge
 5

computing resource can be found by relying on the KKT conditions and the classic bisection
search method.
• Communications design: Given a computing setting, the objective function (OF) becomes
available in a non-convex sum-of-ratios form, which cannot be solved using the algorithms
developed in [20], [22], [24], [33]. To tackle this challenge, we transform this problem to
an equivalent parameterized form by introducing auxiliary variables. Our analysis reveals
that this equivalent form can be decomposed into a series of tractable subproblems. Then,
we develop an iterative algorithm to find the solution. In each iteration, the auxiliary
variables are updated using the modified Newton method, while upon reformulating this
series of tractable subproblems by exploiting the equivalence between the weighted sum-rate
maximization problem and the weighted mean square error (MSE) minimization problem,
we provide a closed-form expression for the MUD matrix and the IRS phase shift, using
the weighted minimum MSE method and MM algorithm, respectively. Our analysis reveals
that the proposed algorithm exhibits a low complexity.
• Study of the single-device scenario: In order to complete the investigations, we also study the
single-device scenario, where neither the edge computing resource allocation nor the multi-
user interference has to be considered. A low-complexity iterative algorithm is proposed by
simplifying the algorithm developed in the aforementioned multi-device scenario.
• Numerical validations and evaluations: The numerical results verify the convergence of the
proposed algorithms, and quantify the performance of our IRS-aided MEC system in terms
of its latency in diverse simulation environments.
The rest of the paper is organized as follows. In Section II, we establish the system model and
formulate the latency minimization problem. The solution of this latency minimization problem
is provided in Section III. In Section IV, we investigate the solution of the special case, where
a single device is served by the MEC system. Our numerical results are discussed in Section V.
Finally, our conclusion are offered in Section VI.

II. S YSTEM M ODEL

In this section, we elaborate on our system model, both from a communications and computing
perspective. Following this, we formulate the latency-minimization problem of our IRS-aided
MEC system, detailed as follows.
 6

A. Communications Model

As shown in Fig. 1, we consider an MEC system operating in a single-cell scenario, where K

single-antenna devices may opt for off-loading a certain fraction of or all of their computational
tasks to an edge computing node via an M -antenna AP through the wireless transmission link.
The edge computing node and the AP are assumed to be co-located and connected using high-
throughput low-latency optical fiber. Then, the latency imposed by the data communication
between the AP and the edge computing node is deemed to be negligible. An IRS comprised
of N reflecting elements is placed in the cell for assisting the devices’ computation off-loading.
We assume that both the antenna spacing at the AP and the element spacing of the IRS are high
enough so that the small-scale fading associated both with two different antennas and with two
different reflecting elements is independent, respectively.

Figure 1: Illustration of the system model, where a N -element IRS assists the computation off-loading of K single-antenna
devices to the edge computing node via the M -antenna access point (AP).

The equivalent baseband channels spanning from the k-th device to the AP, and from the k-th
device to the IRS, as well as from the IRS to the AP are denoted by h d,k ∈ CM ×1 , h r,k ∈ CN ×1
and G ∈ CM ×N , respectively. These channels are assumed to be perfectly estimated 1
and
quasi-static, hence remaining near-constant when devices are scheduled for off-loading their
computational tasks. As for the IRS, we simply set the amplitude reflection coefficient to 1 for
all reflection elements and denote the phase shift coefficient vector by θ = [θ1 , θ2 , . . . , θN ]T ,
where θn ∈ [0, 2π) for all n ∈ {1, 2, . . . , N }. Then, we have the reflection-coefficient matrix

of the IRS Θ = diag ejθ1 , ejθ2 , . . . , ejθN , where j represents the imaginary unit. We assume
that the IRS phase shift setting is calculated at the AP in accordance with both the channel and
computing dynamics, which is then sent to the IRS controller along the dedicated channel. The

1
Naturally, this assumption is idealistic. Hence the algorithm developed in this paper can be deemed to represent the best-case
bound for the latency performance of realistic scenarios.
 7

composite device-IRS-AP channel is modeled as a concatenation of the device-IRS link, the IRS
reflection characterized by its phase shift and the IRS-AP link.
Here, we assume that the computation off-loading of the K devices takes place over a given
frequency band B within the same time resource. Upon denoting the off-loading power and
off-loading signal of the K devices as well as the noise vector by pt , s = [s1 , s2 , . . . , sK ]T and
n = [n1 , n2 , . . . , nK ]T , respectively, we may readily formulate the signal y ∈ CM ×1 received at
the AP as
K
√ √ X

y= ptH s + n = pt h d,k + GΘh r,k sk + n , (1)
k=1

where we have nk ∼ N (0, σ 2 ) for k = 1, 2, . . . , K. Furthermore, we define h k , h d,k + GΘh r,k

 
and H , h 1 , h 2 , . . . , h K . As a computational complexity compromise at the AP, we invoke
a linear MUD technique. Upon denoting the MUD matrix by W ∈ CM ×K , we may obtain the
signal recovered at the AP as

√
ŝs = W H y = W H ( ptH s + n). (2)

As for the k-th device, its recovered signal is formulated as

" K
#
√ X
ŝk = w H


k pt h d,j + GΘh r,j sj + n , (3)
j=1

where w k is the k-th column of the matrix W . Then, the SINR of the k-th device’s signal
recovered is given by

2
pt w H
k h d,k + GΘh r,k
w k , θ ) = PK
γk (w
2 . (4)
pt j=1,j6=k w H
k h d,j + GΘh r,j + σ w
2 |w H 2
k |

Accordingly, upon assuming a perfect capacity-achieving transmission scheme is invoked, we

arrive at the maximum achievable computation off-loading rate of the k-th device formulated as

 
w k , θ ) = B log2 1 + γk (w
Rk (w wk, θ ) . (5)

B. Computing Model

We consider the data-partitioning based application of [7], where a fraction of the data can
be processed locally, while the other part can be off-loaded to the edge node. The computing
model is detailed for the local and edge computing as follows.
 8

• Local computing: For the k-th device, we use Lk , `k and ck to represent its total number of
bits to be processed, its computation off-loading volume in terms of the number of bits and
the number of CPU cycles required to process a single bit, respectively. As for the local
computing, upon denoting the computational capability at the k-th device in terms of the
number of CPU cycles per second by fkl , we may formulate the time required for carrying
out the local computation as Dkl (`k ) = (Lk − `k )ck /fkl .
• Edge computing: we denote the maximum number of executable CPU cycles at the edge
e
and the computational capability allocated to the k-th device by ftotal and fke , respectively,
which obey K e e
P
k=1 fk ≤ ftotal . Here, we assume that the edge computing for the k-th device

only begins its operation, when all its `k bits are completely off-loaded. In this case, the
total latency of edge computing is jointly constituted by the computation off-loading and
by the edge computing as well as by the transmission delay of sending the computational
result back. Given that the computational result is typically of a negligible size [5], we may
reasonably assume that its feedback latency is also negligible. Then the total latency imposed
by the computation off-loading and the edge computing is given by Dke (w
w k , θ , `k , fke ) =
w k , θ ) + `k ck /fke .
`k /Rk (w
To this end, the latency of the k-th device can be readily calculated by selecting the maximum
value between those imposed by the local and by the edge computing, formulated as
 
e
 l e e (Lk − `k )ck `k `k ck
w k , θ , `k , fk ) = max Dk (`k ), Dk (w
Dk (w w k , θ , `k , fk ) = max , + e .
fkl wk, θ )
Rk (w fk
(6)

C. Problem Formulation

In this paper, we aim for minimizing the weighted computational latency of all the devices,
which is achieved by jointly optimizing the computation off-loading volume ` = [`1 , `2 , . . . , `K ]T ,
the edge computing resources f e = [f1e , f2e , . . . , fKe ]T allocated to each device, the MUD matrix
W and the IRS phase shift θ . Specifically, the weighted delay minimization problem is formulated
 9

as
K
X
P0 : min e w k , θ , `k , fke )
$k Dk (w
W ,θθ ,``,ff
k=1

s.t. 0 ≤ θn < 2π, n = 1, 2, . . . , N, (7a)

`k ∈ {0, 1, . . . , Lk }, k = 1, 2, . . . , K, (7b)
K
X
e
fke ≤ ftotal , (7c)
k=1

fke ≥ 0, k = 1, 2, . . . , K. (7d)

where $k represents the weight of the k-th device. Eq. (7a) specifies the range of the phase
shift of the IRS elements; Eq. (7b) indicates that the computation off-loading volume should be
an integer between 0 and Lk for the k-th device; Finally, Eq. (7c) and (7d) restrict the range of
the edge computing resources allocated to each device.

Remark 1. The difficulties of solving Problem P0 are owing to two aspects. One is the coupling
effect when optimizing the computation off-loading volume `, the edge computing resource
allocation f e , the MUD matrix W and the IRS phase shift vector θ . The other is the phase
shift design under the constraint (7a). In the following, we tackle these two issues relying on the
BCD technique and the Majorization-Minimization (MM) algorithm, respectively.

III. J OINT O PTIMIZATION OF C OMPUTING AND C OMMUNICATIONS S ETTING

In Problem P0, we have four variables in total, namely, the off-loading volume and edge
computing resource allocation, MUD matrix and IRS phase shift. The optimization of the
former two variables is related to the computing setting, while the optimization of the other
two specifies the communications design. In this section, the BCD technique is invoked for
decoupling the optimization variables. The pivotal idea of the BCD technique is to optimize one
of the variables while fixing the other variables in an alternating manner, until the convergence
of the OF is achieved. In the rest of this section, we present the joint optimization of the off-
loading volume and of the edge computing resource allocation while fixing the communications
setting, followed by the joint optimization of the MUD matrix and of the IRS phase shift while
fixing the computing setting. Our goal is the joint optimization both of the communications and
of the computing design.
 10

A. Joint Optimization of the Off-loading Volume and the Edge Computing Resource Allocation
While Fixing the Communications Settings

Given an MUD matrix W and an IRS phase shift vector θ , we may simplify Problem P0 to
K
X
P1 : min
e
$k Dk (`k , fke )
` ,ff
k=1

s.t. (7b), (7c), (7d). (8a)

The optimization of ` and f e can be decoupled, relying on the aforementioned BCD technique,
detailed as follows.
1) Optimization of ` : We may optimize the value of ` with the aid of the proposition below.

Proposition 1. Given an MUD matrix W and an IRS phase shift coefficient vector θ as well as
an edge computing resource allocation vector f e , the optimal number of off-loaded bits is given
by

`∗k = arg
 min Dk (`ˆk ), (9)
`ˆk ∈ b`ˆ∗k c,d`ˆ∗k e

where b·c and d·e represent the floor and ceiling operations, respectively, and `ˆ∗k is selected for
ensuring that the value of Dl (`ˆk ) becomes equivalent to that of De (`ˆk ), i.e.
k k

Lk ck Rk fke
`ˆ∗k =
. (10)
fke fkl + ck Rk fke + fkl

Proof. See Appendix A.

2) Optimization of f e : Here, the edge computing resource allocation f e is optimized, while

fixing the MUD matrix W , the IRS phase shift coefficient vector θ , and the off-loading volume
` . Specifically, substituting (10) into the OF of Problem P1, we may reformulate the problem
as:
K
X $k (Lk c2 Rk + Lk ck f e )
k k
P1-E : min
ef f ef l
k=1 k k
+ ck Rk (fke + fkl )

s.t. (7c), (7d). (11a)

Problem P1-E can be proved to be a convex optimization problem following the proposition
below.

Proposition 2. Problem P1-E is a convex optimization problem.

 11

Proof. See Appendix B.

Since Problem P1-E is convex and the Slater’s condition [34] is satisfied 2 , we may impose
the Karush–Kuhn–Tucker (KKT) conditions on the problem for finding its optimal solution.
Specifically, the Lagrangian function associated with Problem P1-E is given by
K K
$k (Lk c2k Rk + Lk ck fke )
X X 
e e e
L(ff , µ, ν ) = +µ fk − ftotal , (12)
c R f l + (fkl + ck Rk )fke
k=1 k k k k=1

where the variable µ is the non-negative Lagrange multiplier, while the optimal edge computing
resource allocation vector f e ∗ and the optimal Lagrange multiplier µ∗ should satisfy the following
KKT conditions, for k = 1, 2, . . . , K:

∂L −$k Lk c3k Rk2 ∗

=  + µ = 0,
e∗ 2
(13)
∂fke
 l l
ck Rk fk + (fk + ck Rk )fk
K
X 
∗ e∗ e
µ fk − ftotal = 0, (14)
k=1

fke ∗ ≥ 0. (15)

The value of fke can be directly derived from (13) for a given µ, which is written as
q
$k Lk c3k Rk2
µ
− ck Rk fkl
e
fk = , k = 1, . . . , K. (16)
fkl + ck Rk
q
e $k Lk c3k Rk2
In order to ensure fk ≥ 0 in (16), we have µ
− ck Rk fkl ≥ 0, which is reformulated as
µ ≤ $k Ll 2k ck . Given that µ 6= 0 in (16), we may find the optimal µ∗ in the range of (µl , µu ] =
 fk

i
0, min $k Ll 2k ck to ensure (14), using the well-known bisection search method associated with
k fk
the termination coefficient of , because K e
P
k=1 fk can be proved to be monotonically decreasing

with respect to µ. The procedure of solving Problem P1 is summarized in Algorithm 1. The

complexity of Algorithm 1 is dominated by calculating f e (t1 +1) using (16) and by calculating
µ using the bisection search method. Its complexity is on the order of O log2 ( µu −µ



l
)K . Thus
log2 ( µu −µ


the total complexity of Algorithm 1 is O tmax
1 
l
)K .

2
In words, the Slater’s condition for convex programming states that strong duality holds if all constraints are satisfied and
the nonlinear constraints are satisfied with strict inequalities.
 12

Algorithm 1 Joint optimization of ` and f e , given W and θ

e
Input: h r,k , h d,k , G , B, pt , σ 2 , K, $k , Lk , ck , fkl , ftotal
e
, tmax f satisfying (7c) and (7d)
1 , , W , θ and f̂
∗ e∗
Output: Optimal ` and f , given W and θ
1. Initialization e
(0)
initialize t1 = 0, 1 = 1, f e (0) ← f̂f
calculate R using (5)
2. Joint optimization of ` and f e
(t )
while 1 1 >  && t1 < tmax 1 do
• calculate ` (t1 +1) using (10)
• calculate f e (t1 +1) and µ by
using (16) and
the bisection search method, respectively
(t +1) obj `(t1 +1) ,f
f e (t1 +1) −obj `(t1 ) ,f
f e (t1 )
• 1 1 =

f e (t1 +1)
obj ` (t1 +1) ,f
• t1 ← t1 + 1
end while
3. Output optimal ` ∗ and f e ∗
` ∗ ← ` (t1 ) and f e ∗ ← f e (t1 )

B. Joint Optimization of the MUD Matrix and the IRS Phase Shift Coefficient While Fixing the
Computing Settings

Given an off-loading volume vector ` and an edge computing resource allocation vector f e ,
Problem P0 is reformulated as
K
X
P2 : min wk, θ )
$k Dk (w
W ,θθ
k=1

s.t. 0 ≤ θn < 2π, n = 1, 2, . . . , N. (17a)

Remark 2. The challenge of solving Problem P2 is due to from two aspects. The first one is
w k , θ ) that is caused by the operation max as detailed in Eq. (6),
the segmented form of Dk (w
while the second issue is that the OF is the summation of fractional functions, with respect to
W and θ as shown in the OF of Problem P2-E1 below, which makes the problem a non-convex
sum-of-ratios optimization. In order to tackle these two issues, we transform the problem as
follows.

1) Problem Transformation: As detailed in Proposition 1, the optimal solution of Problem

P0 results in Dk = Dkl = Dke . Hence upon replacing Dk by Dke and removing the constant
terms, we may reformulate Problem P2 as:
K
X $k `k
P2-E1 : min
W ,θθ wk, θ )
Rk (w
k=1

s.t. 0 ≤ θn < 2π, n = 1, 2, . . . , N. (18a)

 13

We then rewrite it in the following equivalent form:

K
X
P2-E2 : min βk
W ,θθ ,β
β
k=1
$k `k
s.t. ≤ βk , k = 1, 2, . . . , K, (19a)
wk, θ )
Rk (w
0 ≤ θn < 2π, n = 1, 2, . . . , N. (19b)

The following proposition may assist us in solving Problem P2-E2.

W ∗ , θ ∗ , β ∗ ) is the solution of Problem P2-E2, a λ ∗ = [λ1 , λ2 , . . . , λK ] exists

Proposition 3. If (W
W ∗ , θ ∗ ) satisfies the KKT conditions of the following problem, when we set β = β ∗ and
that (W
λ = λ∗
K
X  
P2-E3 : min wk, θ )
λk $k `k − βk Rk (w
W ,θθ
k=1

s.t. 0 ≤ θn < 2π, n = 1, 2, . . . , N. (20a)

W ∗ , θ ∗ ) also satisfies the following equations, when we set β = β ∗ and λ = λ ∗

Furthermore, (W

λ k = 1
w ∗k ,θθ ∗ ) , k = 1, 2, . . . , K,

Rk (w
(21)
βk = $k∗`k ∗ , k = 1, 2, . . . , K.

Rk (ww ,θθ ) k

W ∗ , θ ∗ ) is a solution to Problem P2-E3 and satisfies Equation (21) when

Correspondingly, if (W
we set β = β ∗ and λ = λ ∗ , (W
W ∗ , θ ∗ , β ∗ ) is the solution of Problem P2-E2 associated with the
Lagrange multiplier λ = λ ∗ .

Proof. See Appendix C.

To this end, the sum-of-ratios form in Problem P2-E1 has been transformed to a parameterized
subtractable form in Problem P2-E3, which can be solved in two steps [35], [36]: the first step
is to obtain W ∗ and θ ∗ by solving Problem P2-E3, given β and λ ; the second step is to update
β and λ using the modified Newton method until the convergence is achieved. The procedure
is summarized in Algorithm 9, where we have

w ∗k , θ ∗ ) − 1,
χk (λk ) = λk Rk (w k = 1, 2, . . . , K, (22)

w ∗k , θ ∗ ) − $k `k ,
κk (βk ) = βk Rk (w k = 1, 2, . . . , K. (23)
 14

The complexity of Algorithm 9 is analyzed at the end of Section III-B.

Algorithm 2 Joint optimization of W and θ , given ` and f e

Input: h r,k , h d,k , G , B, pt , σ 2 , $k , ` and f e
Output: Optimal W ∗ and θ ∗ , given ` and f e
1. Initialization
initialize t2 = 0, ζ ∈ (0, 1),  ∈ (0, 1) and θ (0) satisfying (7a)
calculate W (0) and R (0) using (29) and (32), respectively
calculate λ (0) and β (0) using (21)
2. Joint optimization of W , θ , λ and β
repeat
• update W (t2 +1) and θ (t2 +1) using Algorithm 3
• update λ (t2 +1) and β (t2 +1) as follows
(t2 +1) (t )
(t2 +1) (t )

(t2 +1) (t2 ) ζi χk λk 2 (t2 +1) (t2 ) ζi κk βk 2
λk = λk − (t +1)
, and β =β − (t +1)
, (24)
Rk w k 2 , θ (t2 +1) Rk w k 2 , θ (t2 +1)

where i(t2 +1) is the smallest integer among i ∈ {1, 2, 3, . . .} satisfying

K (t ) 2 X K 2
ζ i χk (λk 2 ) ζ i κk (β (t2 ) )
  
(t )
X
(t2 )
χk λk 2 − + κk β −
k=1 Rk (ww (t
k
2 +1)
, θ (t2 +1) ) k=1 w k(t2 +1) , θ (t2 +1) )
Rk (w
K h
X (t )
2
2i
≤ (1 − 3 ζ i )2 χk λk 2 + κk β (t2 ) (25)
k=1

• t2 ← t2 + 1
until the following conditions are achieved
(t ) (t ) (t )
w k 2 , θ (t2 ) ) − 1 = 0,
λk 2 Rk (w w k 2 , θ (t2 ) ) − $k `k = 0
βk Rk (w (26)

3. Output optimal W ∗ and θ ∗

W ∗ ← W (t2 ) and θ ∗ ← θ (t2 )

Let us now focus our attention on the first step of solving Problem P2-E3, i.e. optimizing W ∗
and θ ∗ , given a set of β and λ as well as an off-loading volume vector ` . In this case, the OF
of Problem P2-E3 is equivalent to max K
P
w k , θ ). By introducing a set of auxiliary
k=1 λk βk Rk (w
W ,θθ
variables {Υk }, we transform Problem P2-E3 as follows [37]:
K
X
W , θ ) − λk βk log2 (λ−1 −1
 
P2-E4 : min Υk ek (W k βk Υk ) − λk βk
W ,θθ
k=1

s.t. 0 ≤ θn < 2π, ∀n ∈ {1, 2, . . . , N }, (27a)

where the mathematical expression of {Υk } is given later and ek represents the MSE of the k-th
 15

user, which is written as

√ √ H
W , θ) =
ek (W ptw H
k h
(h d,k + GΘh r,k ) − 1 p tw H
k h
(h d,k + GΘh r,k ) − 1
K
X
+pt wH
k (h hd,j + GΘhr,j )H w k + σ 2w H
hd,j + GΘhr,j )(h k wk. (28)
j6=k

Compared to Problem P2-E3, Problem P2-E4 becomes more tractable, because given an IRS
phase shift coefficient vector, the OF of Problem P2-E4 is a convex function for an optimization
variable, while fixing the other one. Again, the BCD technique is invoked for solving this problem
as follows.
2) MUD Matrix Design: In Problem P2-E4, fixing the phase shift coefficient vector θ and
the auxiliary variable Υk , we may obtain the MUD vector by forcing the first-order derivative
of the OF with respect to w k as 0. After several steps of mathematical manipulations, we may
readily observe that the above minimization is equivalent to minimizing the weighted MSE.
Then, the MUD vector is given by [38, Sec. 6.2.3]

√
wk = ptJ −1 (h
hd,k + GΘh r,k ), (29)

PK
where J = pt hd,j
j=1 (h hd,j + GΘh r,j )H + σ 2I M .
+ GΘh r,j )(h
3) Auxiliary Variable Design: Fixing θ and w k , we may obtain the optimal auxiliary variable
by minimizing the OF of Problem P2-E4 with respect to Υk , given by

Υk = λk βk (ek )−1 . (30)

Furthermore, substituting (29) into (28), the MSE becomes

eMMSE
k hd,k + GΘh r,k )H J −1 (h
= 1 − pt (h hd,k + GΘh r,k ). (31)

Bearing in mind that the relationship between the SINR and the MSE of the system equipped
with the minimum mean square error (MMSE) MUD is given by γk = (eMMSE
k )−1 − 1 [38,
Sec. 6.2.3], we may reformulate (5) as

Rk = −B log2 eMMSE


k . (32)

4) IRS Phase Shift Coefficient Design: In this subsection, we focus our attention on optimizing
the reflection phase shift coefficients θ , while fixing the auxiliary variable Υk and the MUD
 16

matrix W . Specifically, by substituting (28) into the OF of Problem P2-E4 and removing the
terms that are independent of the phase shift coefficient vector θ , we may reformulate Problem
P2-E4 as follows:
K X
K K K
X X √ X √
P2-E5 : min Υk ptw H H
k hjhj w k − Υk pth H
k wk − Υk ptw H
k hk
θ
k=1 j=1 k=1 k=1

s.t. 0 ≤ θn ≤ 2π, ∀n ∈ {1, 2, . . . , N }, (33)

where the first and the second terms in the OF can be respectively formulated in expansion
forms as
K X
X K K X
X K
Υk ptw H H
k hjhj w k = Υk ptw H H H H H H H H
k GΘh r,j h r,j Θ G w k + Υk ptw k h d,j h r,j Θ G w k
k=1 j=1 k=1 j=1

+Υk ptw H H H H


k GΘh r,j h d,j w k + Υ k p tw k h d,j h d,j w k , (34)

and
K K
X √ X √ √ H H H

Υk pthH
k wk = Υk pthH
d,k w k + Υk pth r,k Θ G w k . (35)
k=1 k=1

Upon defining A , K
P H H
PK H
PK PK H H
k=1 Υk ptG w kw k G , B , j=1 h r,j h r,j , C , k=1 j=1 Υk pth r,j h d,j w kw k G
√
and D , K H
P
k=1 Υk pth r,kw k G , we may rewrite Problem P2-E5 as:

ΘH AΘB ) + tr Θ H (C
C − D )H + tr Θ (C
   
P2-E6 : min tr(Θ C − D)
θ

s.t. 0 ≤ θn ≤ 2π, ∀n ∈ {1, 2, . . . , N }. (36)

 T
Defining φ , [φ1 , . . . , φN ]T where φn = ejθn , and v = [C
C − D ]1,1 , . . . , [C
C − D ]N,N , we have

ΘH AΘB ) = φ H (A
tr(Θ A φ,
B )φ (37)

where represents the Hadamard product, and

C − D )H = v H φ ∗ ,
tr Θ H (C C − D ) = φT v .
   
tr Θ (C (38)

Further defining Ψ , A B , we may equivalently rewrite Problem P2-E6 as:

φ) = φ H Ψφ + 2Re φ H v ∗

P2-E7 : min f (φ
φ

s.t. |φn | = 1, ∀n ∈ {1, 2, . . . , N }. (39)

 17

Problem P2-E7 is a non-convex one because of the unit modulus constraint on φn . In the
following, the MM algorithm [39] is invoked for solving this problem, which has two steps. In
φt ), which represents
φ|φ
the majorization step, we construct a continuous surrogate function g(φ
φ). Then in the minimization step, we update φ by φ t+1 ∈ arg min g(φ
the upperbound of f (φ φt ).
φ|φ
φ
As such, we may initialize φ 0 that satisfies the constraint (39), and then use the MM algorithm
φt }, where t refers to the iteration index. Now we
to generate a sequence of feasible vectors {φ
construct the surrogate function with the aid of the proposition below.

Proposition 4. Denoting the maximum eigenvalue of Ψ by λ̂max and given a solution φ t at the
t-th iteration, we have the inequality below

φ) ≤ φ H λ̂maxI N φ − 2Re φ H (λ̂maxI N − Ψ )φ

φt + (φ φt + 2Re φ H v ∗ .
φt )H (λ̂maxI N − Ψ )φ
 
f (φ

(40)

Proof. See [24], [40].

φt ). Then,
φ|φ
Here we define the terms on the right side of (40) by our surrogate function g(φ
we may reformulate Problem P2-E7 at the t-th iteration as

φt )
φ|φ
P2-E8 : min g(φ
φ

s.t. |φn | = 1, ∀n ∈ {1, 2, . . . , N }. (41)

φt )H (λ̂maxI N − Ψ )φ
Since (φ φt is a constant for a given φ t and we have φ H λ̂maxI N φ = M λ̂max ,
Problem P2-E8 can be equivalently written as
n  o
φt − v ∗
P2-E9 : max Re φ H (λ̂maxI N − Ψ )φ
φ

s.t. |φn | = 1, ∀n ∈ {1, 2, . . . , N }. (42)

Then, the optimal solution of Problem P2-E9 is readily given by

t ∗
φ t+1 = ej arg[(λ̂maxI N −Ψ φ −vv ]
Ψ)φ
. (43)

Accordingly, the optimal solution to Problem P2-E6 can be obtained as

φt − v ∗ ].
θ t+1 = arg[(λ̂maxI N − Ψ )φ (44)
 18

φt+1 ) − f (φ
The termination condition of the MM algorithm is given by f (φ φt ) /f (φ
φt+1 ) ≤  or
t ≥ tmax
MM . The procedure of solving Problem P2-E3 is summarized in Algorithm 3.

Algorithm 3 Joint optimization of W and θ , given λ and β

Input: h r,k , h d,k , G , B, pt , σ 2 , $k , tmax2 , , λ and β
Output: Optimal W ∗ and θ ∗ , given λ and β
1. Initialization
(0)
initialize t3 = 0, 3 = 1, θ (0) satisfying (7a)
2. Joint optimization of W and θ
(t )
while 3 2 >  && t3 < tmax 3 do
• calculate W (t3 +1) using (29)
• calculate Υ (t3 +1) using (30)
• calculate θ (t3 +1) by solving
Problem P2-E6
with the aid of the MM algorithm
(t +1) obj W (t3 +1) ,θ
θ (t3 +1) −obj W (t3 ) ,θ
θ (t3 )
• 3 3 =

θ (t3 +1)
obj W (t3 +1) ,θ
• t3 ← t3 + 1
end while
3. Output optimal W ∗ and θ ∗ , given λ and β
W ∗ ← W (t3 ) and θ ∗ ← θ (t3 )

The complexity of Algorithm 3 is dominated by its Step 2. Specifically, the complexity of

calculating W (t3 +1) by (29) is on the order of O max{KM 3 , KM N 2 } ; the complexity of
calculating Υ (t3 +1) by (30) is on the order of O(K). With regard to the calculation of θ (t3 +1)
using the MM algorithm, the complexity of calculating the eigenvalue λmax of Ψ is on the
order of O(N 3 ), while for each iteration of the MM algorithm, the main complexity lies in the
calculation of φt+1 in (43), whose complexity is on the order of O(N 2 ). Hence the complexity of
the MM algorithm is O(N 3 + tmax 2
MM N ). Summing these three terms together, we obtain the total


complexity of Algorithm 3 as O max{N 3 + tmax 2 3 2
MM N , KM , KM N } . Finally, the complexity

of Algorithm 9 is mainly dependent on updating W (t2 +1) and θ (t2 +1) using Algorithm 3, because
all other steps are given by explicit mathematical expressions.

C. Overall Algorithm to Solve Problem P0

Based on the above discussions, we provide the detailed description of the BCD algorithm
used for solving Problem P0 in Algorithm 4. Note that a decreasing OF value of Problem P0
is guaranteed in Step 2 and Step 3. Furthermore, the OF value has a lower bound due to the
constraint on the total edge computing resources. Hence Algorithm 4 is guaranteed to converge.
The computational complexity of Algorithm 4 is mainly dependent on its Step 2 and Step 3,
whose complexities have been analyzed in the above subsections. Furthermore, the simulation
 19

results in Section V show that Algorithm 4 converges rapidly, which demonstrates the low
complexity of our algorithms.

Algorithm 4 Joint Optimization of ` , f e , W and θ

Input: h r,k , h d,k , G , B, pt , σ 2 , $k , Lk , ck , ftotal e
and 
e
Output: Optimal ` , f , W and θ
1. Initialization
(0)
initialize t4 = 0, 4 = 1
initialize θ satisfying (7a) and f e (0) satisfying (7c) and (7d)
(0)

calculate W (0) using (29)

2. Joint optimization of ` and f e , given W (t4 ) and θ (t4 )
calculate ` (t4 +1) and f e (t4 +1) using Algorithm 1
3. Joint optimization of W and θ , given ` (t4 +1) and f e (t4 +1)
calculate W (t4 +1) and θ (t4 +1) using Algorithm 9
4. Convergence checking


(t ) obj ` (t4 +1) ,f
f e(t4 +1) ,W
W (t4 +1) ,θ
θ (t4 +1) −obj ` (t4 ) ,f
f e(t4 ) ,W
W (t4 ) ,θ
θ (t4 )
4 4 =

f e (t4 +1) ,W
obj ` (t4 +1) ,f θ (t4 +1)
W (t4 +1) ,θ
(t )
if 4 4
>  && t4 < tmax
4 holds then
t4 = t4 + 1
Go to Step 2
else
integerize `(t4 +1) by (9)
Output the optimal ` ∗ , f e ∗ , W ∗ and θ ∗
end if

IV. S PECIFIC C ASE S TUDY: T HE S INGLE -D EVICE S CENARIO

In order to fully characterize the IRS-aided MEC system, in this section we investigate a special
case, where a single device is served by the MEC system. The optimization problem of the single-
device scenario becomes much simpler for the following reasons. Firstly, the edge computing
resource allocation no longer has to be considered, because all the edge computing resources can
be assigned to this single device. Secondly, the sum-of-ratios form in Problem P2-E1 becomes
a single-ratio form, which implies that the optimization problem is more tractable. Thirdly, the
multi-user interference does not have to be considered, when we optimize the detection vector
and the IRS phase shift coefficient vector. The joint optimization is detailed as follows.
Problem P0 can be simplified for the single-device scenario as

w , θ , `)
P3 : min D(w
w ,θθ ,`

s.t. 0 ≤ θn < 2π, n = 1, 2, . . . , N, (45a)

` ∈ {0, 1, . . . , L}, (45b)

 20

w , θ , `) becomes
where the OF D(w
 
(L − `)c ` `c
w , θ , `) = max
D(w , + e . (46)
fl w , θ ) ftotal
R(w

w , θ , `) achieves its minimum

As illustrated in Proposition 1, for a given set of w and θ , D(w
(L−`)c ` `c
value when ` is selected to ensure fl
= w ,θθ )
R(w
+ e .
ftotal
Therefore, the optimal value of the
relaxation of ` is given by
e
LcRftotal
`ˆ∗ = e e

. (47)
ftotal f l + cR ftotal + fl

Then Problem P3 is reformulated as

` `c
P3-E1 : min + e
w ,θθ w , θ ) ftotal
R(w
s.t. 0 ≤ θn < 2π, n = 1, 2, . . . , N, (48a)

which is equivalent to

w, θ)
P3-E2 : max R(w
w ,θθ

s.t. 0 ≤ θn < 2π, n = 1, 2, . . . , N. (49a)

Substituting (4) and (5) into the OF of Problem P3-E2 and taking several steps of mathematical
manipulation, we may equivalently transform Problem P3-E2 as

2
pt w H h d + GΘh r
P3-E3 : max
w ,θθ w H |2
σ 2 |w
s.t. 0 ≤ θn < 2π, n = 1, 2, . . . , N. (50a)

Again, the BCD technique is invoked for optimizing w and θ in Problem P3-E3. Specifically,
given a θ , w can be optimized following the well-known maximum ratio combining (MRC)
criterion [41], which is given by

√
w= hd + GΘh r )/σ,
pt (h (51)

while for a given w , we have the following inequality for the OF of Problem P3-E3,

2 2 2
pt w H h d + GΘh r pt w H h d pt w H GΘh r
≤ 2 H2 + . (52)
w H |2
σ 2 |w w |
σ |w w H |2
σ 2 |w
 21

w H hd ) =
The equality in (52) holds only when the IRS phase shift coefficient obeys arg(w
w H GΘh r ). Accordingly, we may readily obtain the reflection phase shift vector θ as
arg(w

w H h d ) − arg(diag{w
θ = arg(w w H G }h
hr ). (53)

In Algorithm 5, we provide the overall algorithm that is used for solving our optimization
problem for the single-device scenario.
The complexity of Algorithm 5 is dominated by calculating θ (t5 +1) and w (t5 +1) using (53) and


(51), whose complexities are on the order of O max{M N, N 2 } and of O(M N 2 ), respectively.
Hence the complexity of Algorithm 5 is on the order of O(M N 2 ).

Algorithm 5 Joint Optimization of `, w and θ proposed for the single-user scenario

Input: h r , h d , G , B, pt , σ 2 , L, c, ftotal
e
and 
Output: Optimal `, w and θ
1. Initialization
(0)
initialize t5 = 0, 5 = 1
(0)
initialize θ satisfying (7a)
calculate w (0) using (51)
2. Joint optimization of w and θ
repeat
• calculate θ (t5 +1) and w (t5
+1) using (53)
and (51), respectively
(t ) obj w (t5 +1) ,θ
θ (t5 +1) −obj w (t5 ) ,θ
θ (t5 )
• 5 5 = (t +1) (t +1)

, where the obj refers to the OF of Problem P3-E3
obj w 5 θ
,θ 5

• t5 = t5 + 1
(t )
until 5 5 ≤  || t5 > tmax
5
3. Optimization of `
calculate `ˆ(t5 +1) using (47)
integerize `(t5 +1) by (9)

V. N UMERICAL R ESULTS

In this section, we evaluate the benefits of deploying the IRS in a MEC system relying on our
algorithms developed in Section III and IV. We consider a single-cell MEC system for both the
single-device and two-device as well as multi-device scenarios. As shown in Fig. 2, the AP’s
coverage radius is R = 300 m and the IRS is deployed at the cell edge. The location of the
device is specified both by d and by d in the single-device scenario, while in the two-device
scenario, the devices’ locations are specified by (d1 , d1 ) and (d2 , d2 ), respectively. Furthermore,
in the multiple-device scenario, we assume that the devices are uniformly distributed within a
circle, whose size and location are prescribed by its radius r as well as d and d, respectively.
 22

The default value of these parameters are set in the “Location model” block of Table I. As for
the communications channel, we consider both the small scale fading and the large scale path
loss. Specifically, the small scale fading is i.i.d. and obeys the complex Gaussian distribution
associated with zero mean and unit variance, while the path loss in dB is given by
d
PL = PL0 − 10α log10 , (54)
d0

where PL0 is the path loss at the reference distance d0 ; d and α represent the distance of the
communications link and its path loss exponent, respectively. Here we use αua , αui and αia to
denote the path loss exponent of the link between the device and the AP, that of the link between
the device and the IRS as well as that of the link between the IRS and the AP, respectively. The
zero-mean additive white Gaussian noise associated with the variable of σ 2 is imposed on the
off-loaded signal. The default settings of these parameters are specified in the “Communications
model” block of Table I. The variables Lk , ck and fkl obey the uniform distribution, whose ranges
are given in the “Computing model” block of Table I.

(a) (b) (c)

Figure 2: Top-view setting of the single-device scenario (a), the two-device scenario (b) and multiple-device scenario (c).

The following subsections detail our simulation results, in terms of the convergence behavior of
our proposed algorithm and the latency performance in both the single-device and two-device as
well as multi-device scenarios in various simulation environments. The following three schemes
are considered:
• With IRS: The off-loading volume and edge computing resource allocation, MUD matrix and
IRS phase shift are optimized relying on Algorithm 5 and Algorithm 4 in the single-device
and multi-device scenarios, respectively.
• RandPhase: The off-loading volume and edge computing resource allocation as well as
MUD matrix are optimized using Algorithm 5 and Algorithm 4 in single-device and multi-
device scenarios, respectively, while skipping the step of designing the IRS phase shift,
which is randomly set obeying the uniform distribution in the range of [0, 2π).
 23

• Without IRS: The composite channel GΘhr,k taking into account the IRS is set to 0. The
off-loading volume, edge computing resource allocation and the MUD matrix are designed
following Algorithm 5 and Algorithm 4 in the single-device and multi-device scenarios,
respectively.

Table I: Default simulation parameter setting

Description Parameter and Value

Location model R = 300 m, d = d1 = d2 = 10 m
Bandwidth = 1 MHz
PL0 = 30 dB, d0 = 1 m
Communication model
αua = 3.5, αui = 2.2, αia = 2.2
M = 5, pt = 1 mW, σ 2 = 3.98 × 10−12 mW
Lk = [250, 350] Kb
Computing model ck = [700, 800] cycle/bit
fkl = [4, 6] × 108 cycle/s
Convergence criterion  = 0.001

A. Convergence of the Algorithms

Fig. 3 shows the device-average latency versus the number of iterations under various settings
of the IRS phase shift number, i.e. N = 10, 20, and 40, for both the single-device and multi-
device scenarios. We have the following two observations. Firstly, a larger number of phase
shifts leads to a slightly slower convergence, especially for the multi-device scenario. This is
because more optimizing variables are involved. Secondly, the proposed algorithms are capable
of achieving a convergence within 5 iterations, which validates its practical implementation.

500 500
N = 10 450 N = 10
Latency (ms)

Latency (ms)

400 N = 20 N = 20
400
N = 40 N = 40
300 350
200 300
250
100
200
0 150
0 2 4 6 8 10 12 14 16 18 20 0 2 4 6 8 10 12 14 16 18 20
Number of iterations Number of iterations
(a) (b)

Figure 3: Convergence of the algorithms for the single-device scenario (a) and the two-device scenario (b). The parameters are
e
set as follows: ftotal = 50 × 109 cycle/s; ck = 750 cycle, Lk = 300 Kb and fkl = 0.5 × 109 cycle/s for all devices. (a):
d = 280 m; (b): d1 = d2 = 280 m.
 24

B. Single-Device Scenario

Fig. 4 presents the latency versus various parameter settings in the single-device scenario, dis-
cussed as follows. Note that the following results are obtained by averaging over 500 independent
simulation episodes.

120 140 140

With IRS With IRS
130 RandPhase 120 RandPhase
110 Without IRS Without IRS
120 100

Latency (ms)

Latency (ms)
100
Latency (ms)

110 80
90
60
80 100
With IRS 40
70 RandPhase 90
Without IRS 20
60 80
10 20 30 40 50 60 70 80 90 100 5 10 15 20 25 30 35 40 45 50 55 60 0 50 100 150 200 250 300
e
ftotal (109 cycle/s) d (m)
N
(a) (b) (c)

Figure 4: Simulation results of the latency versus the number of the IRS elements (a), the edge computing capability (b) and
e
the device location (c) in the single-device scenario. For each subfigure, we have (a): d = 280 m and ftotal = 50 × 109 cycle/s;
e 9
(b): d = 280 m and N = 40; (c): N = 40 and ftotal = 50 × 10 cycle/s.

1) Impact of the Number of Reflecting Elements: Fig. 4a presents the latency versus the
number of the reflecting elements, for the various phase shift design schemes. We have the
following observations. Firstly, the performance gap between the schemes “Without IRS” and
“RandPhase” becomes higher upon increasing the number of reflecting elements, which implies
that the IRS is capable of assisting the computation off-loading even without carefully designing
the phase shift. This is because the received SINR can be improved by deploying an IRS for
computation off-loading. The gain was termed as the virtual array gain in Section I. Secondly, the
performance gain of the scheme “With IRS” over the scheme “RandPhase” is around 11 ms when
we set N = 10, while it becomes 46 ms when we have N = 100. This implies that a sophisticated
design of the IRS phase shift response provides a beamforming gain, and that increasing the
number of IRS elements leads to a higher reflection-based beamforming gain. Combining these
two types of gains together, IRSs are capable of efficiently reducing the latency in MEC systems.
2) Impact of the Edge Computing Capability: Fig. 4b shows the latency versus the edge
computing capability of various IRS phase shift schemes. Our observations are as follows. For
e e
all these three schemes, the increase of ftotal drastically reduces the latency when ftotal is of
e
a small value, while the reduction of the latency becomes smaller when ftotal reaches a certain
threshold value, say 30×109 cycle/s. This is because the latency imposed by the edge computing
 25

e
dominates when ftotal is of a small value, whereas the latency imposed by computation off-loading
e
plays a dominant role when ftotal reaches a high value. Therefore, it is not necessary to equip the
edge computing node with an extremely powerful computing capability for latency minimization.
3) Impact of the Device Location: Fig. 4c depicts the latency versus the device location,
equipped with various IRS phase shift schemes. We have the following observations. In the
case where no IRS is employed, the latency increases upon increasing the distance between
the AP and the device. In the case where the IRS’s phase shift is randomly set, the advantage
of using the IRS becomes visible when the distance between the device and the IRS is less
than 20 m. By contrast, the benefit of the IRS becomes notable for a much larger coverage
of 100 m for the “With IRS” scheme. This observation implies that a sophisticated design of
the IRS phase shift response is capable of extending the coverage of the IRS. Furthermore, the
latency reaches its maximum value at d = 260 m and thereafter becomes smaller for the “With
IRS” scheme. This is because the direct device-AP link dominates the computation off-loading
when the device’s location obeys d ≤ 260 m, while the composite device-IRS-AP link plays a
dominant role, when we have d ≥ 260 m. This observation further consolidates that a higher
gain can be achieved in the near-IRS area, where the composite device-IRS-AP link dominates
the computation off-loading.

C. Multi-Device Scenario

Fig. 5 presents the latency in the two-device scenario. Again, the following results are obtained
by averaging over 500 independent simulation episodes.

140 170 180

Average With IRS Average With IRS
160 Device 1 RandPhase 160 Device 1 RandPhase
130
150 Device 2 Without IRS Device 2 Without IRS
140
120
140
Latency (ms)

120
Latency (ms)
Latency (ms)

110
130 100
100 120 80
90 110 60
140
130
80 100 40
Average With IRS 120
70 Device 1 RandPhase 90 20 110
Device 2 Without IRS 260 270 280 290 300
60 80 0
10 20 30 40 50 60 70 80 90 100 5 10 15 20 25 30 35 40 45 50 55 60 0 50 100 150 200 250 300
e
ftotal (109 cycle/s)
N d1 (m)

(a) (b) (c)

Figure 5: Simulation results of the latency versus the user location (a), the number of the IRS elements (b) and the edge computing
resource (c) in the two-device scenario. d2 = 280 m are set for all figures. For each subfigure, we have (a): d1 = 260 m and
e
ftotal = 50 × 109 cycle/s; (b): d1 = 260 m and N = 40; (c): N = 40 and ftotal e
= 50 × 109 cycle/s.
 26

1) Impact of the Number of IRS Elements: Fig. 5a depicts the latency versus the number of
the IRS elements in the two-device scenario, equipped with various phase shift schemes. Apart
from the insights obtained in the single-device scenario, we also have the following observations.
Firstly, Device 2 outperforms Device 1 for the “With IRS” scheme, whilst Device 1 has a lower
latency both for the “Without IRS” and “RandPhase” schemes compared to Device 2. This is in
accordance with the comparative relationship between the devices located at d = 260 m and at
d = 280 m in terms of the latency using those three phase shift schemes, as shown in Fig. 4c.
This also implies that IRSs may change the latency ranking of the devices in MEC systems.
Secondly, upon increasing the number of IRS elements, Device 2 obtains a higher gain than
Device 1. This is because Device 2 is located closer to the IRS, where the composite device-
IRS-AP channel dominates the computation off-loading. Again, this implies that given a specific
path loss exponent, a higher array and passive beamforming gain may be achieved if the device
is located closer to the IRS.
2) Impact of the Edge Computing Capability: Fig. 5b presents the latency versus the edge
computing capability in the multi-device scenario, equipped with various phase shift schemes.
This scenario follows similar trends to the single-device case illustrated in Fig. 4b.
3) Impact of the Device Location: Fig. 5c plots the latency versus the location of Device 1,
while fixing the location of the AP, the IRS and Device 2. As for the “With IRS” scheme, the
curve of Device 1’s latency intercepts that of Device 2 at d1 = 220 m and d1 = 280 m, which
implies that the devices at these two locations have the same channel gain. In other words, the
IRS is capable of assisting the device at d = 280 m to achieve the same latency as the device at
d = 220 m. Note that the specific values of these two equivalent-latency locations are dependent
on the specific values of the path loss exponents of the device-IRS, IRS-AP and device-AP
channels, as presented below.
4) Impact of the Path Loss Exponent: Fig. 6 illustrates the latency versus the path loss
exponent value associated with the IRS. It can be observed that the intercept point disappears,
when αIRS is changed for the “With IRS” scheme. Furthermore, the latency of devices increases
upon increasing αIRS . This is because higher αIRS leads to a lower array and beamforming gain
by the IRS. This provides important insights for engineering design: the location of the IRS
should be carefully selected to avoid obstacles, for achieving a lower αui and αia .
5) Impact of the Number of Devices: Fig. 7 shows the latency versus the number of devices
in the cycle in multi-device scenario. It can be readily observed that the device-average latency
 27

140 180

130
160
120
Latency (ms)

Latency (ms)
110 140

100 120
90
Average With IRS 100 With IRS
80 Device 1 RandPhase RandPhase
Device 2 Without IRS Without IRS
70 80
2.0 2.2 2.4 2.6 2.8 3.0 1 2 3 4 5
αIRS K

Figure 6: Simulation results of the latency versus the path Figure 7: Simulation results of the device-average latency
loss exponent, where we set αui = αia = αIRS . The versus the number of devices K The parameters are set as
parameters are set as follows: d1 = 220 m, d2 = 280 m, follows: d = 280 m, d = 10 m, r = 10 m, N = 40 and
e
N = 40 and ftotal = 50 × 109 cycle/s. e
ftotal = 50 × 109 cycle/s.

increases upon increasing the number of devices in the IRS-aided MEC system. This is partially
because of the reduced edge computational resources allocated to each device and partially due
to the reduced beamforming gain achieved at each device. The former issue may be overcome by
equipping the edge node with more powerful computing capability, while the latter problem can
be solved by deploying more IRSs in the MEC system for forming stronger beams. Nonetheless,
compared to the “Without IRS” scheme, our “With IRS” scheme is capable of reducing the
device-average latency from 177 ms to 139 ms, when we have 5 devices in the MEC system.
This again validates the benefits of our proposed system.

VI. C ONCLUSIONS

In order to reduce the computational latency, we employed IRSs in our MEC systems, and
formulated a latency-minimization problem, subject to the constraints on the total edge computing
capability and IRS phase shift. Sophisticated algorithms were developed for optimizing both the
computing and communications settings. The benefits of using IRSs in the MEC system were
evaluated under various simulation environments. Quantitatively, the device-average computa-
tional latency was reduced from 177 ms to 139 ms, compared to the MEC system operating
without IRSs in a single cell associated with the cell radius of 300 m, a 5-antenna access
point and 5 active devices. Furthermore, the rapid convergence of our proposed algorithm was
confirmed numerically, which validates the benefits of our algorithms. These results inspire us
to conceive an energy-minimization design for IRS-aided MEC systems in our future work.
 28

A PPENDIX A
T HE PROOF OF P ROPOSITION 1

We use `ˆk ∈ [0, Lk ] to represent the relaxation [42] of the integer value `k ∈ {0, 1, . . . , Lk }.
Furthermore, given the values of W , θ and f e , we define the delay associated with `ˆk to be
D̂k (`ˆk ) , max Dkl (`ˆk ), Dke (`ˆk ) , which can be reformulated from (6) as a segmented form


below 
 (Lk −`lˆk )ck , Lk ck Rk fke
0 ≤ `ˆk ≤ ,

fke fkl +ck Rk (fkl +fke )
D̂k (`ˆk ) = fk
(55)
 `ˆk + `ˆk ck Lk ck Rk fke
, < `ˆk ≤ Lk .

Rk fke fke fkl +ck Rk (fkl +fke )
 
Lk ck Rk fke
A glance at (55) reveals that D̂k (`ˆk ) decreases upon increasing `ˆk in the range of `ˆk ∈ 0, e l
,
fke +fkl
  fk fk +ck Rk
L c R f e
while D̂k (`ˆk ) increases upon increasing `ˆk in the range of `ˆk ∈ e l k k k ke l
, Lk . Therefore,
fk fk +ck Rk fk +fk
Lk ck Rk fke
it is readily inferred that D̂k (`ˆk ) achieves its minimum value when we set `ˆk =
,
fke fkl +ck Rk fke +fkl
which is denoted by `ˆ∗k . Bearing in mind that the optimal value of `k has to be an integer, we
may obtain it by carrying out the operation `∗k =  arg min Dk (`ˆk ). This completes the proof.
ˆ b`ˆ∗ c,d`ˆ∗ e
`∈ k k

A PPENDIX B
T HE PROOF OF P ROPOSITION 2

Let us denote the second derivative of the OF of Problem P1-E with respect to fke by Φ1-E ,
which is calculated as

2$k Lk c3k Rk2 (fkl + ck Rk )

Φ1-E = 
3 . (56)
fke fkl + ck Rk fke + fkl

Since the values of $k , ck , Rk , fkl are all positive and Lk ≥ 0, fke ≥ 0, we may readily
demonstrate that Φ1-E ≥ 0. Hence the OF is a convex function with respect to fke . Furthermore,
the constraint functions (7c) and (7d) are all of linear forms. Hence, we have shown Problem
P1-E to be a strictly convex problem.

A PPENDIX C
T HE PROOF OF P ROPOSITION 3

The Lagrangian of Problem P2-E2 is given by

K
X K
X  
W , θ , β , λ) =
L(W βk + wk, θ )
λk $k `k − βk Rk (w (57)
k=1 k=1
 29

W ∗ , θ ∗ , β ∗ ) is the solution of Problem

where {λk } is the non-negative Lagrange multiplier. If (W
P2-E2, there exists λ ∗ satisfying the following KKT conditions

∂L
= −λ∗k βk∗ ORk (w w ∗k , θ ∗ ) = 0, k = 1, 2, . . . , K, (58)
∂θk
∂L
= −λ∗k βk∗ ORk (w w ∗k , θ ∗ ) = 0, k = 1, 2, . . . , K, (59)
∂wwk
∂L
= 1 − λ∗k Rk (ww ∗k , θ ∗ ) = 0, k = 1, 2, . . . , K, (60)
∂βk
w ∗k , θ ∗ ) = 0, k = 1, 2, . . . , K,
λ∗k $k `k − βk∗ Rk (w
 
(61)

λ∗k ≥ 0, k = 1, 2, . . . , K, (62)

$k `k − βk∗ Rk (w
w ∗k , θ ∗ ) ≤ 0, k = 1, 2, . . . , K, (63)

0 ≤ θk∗ ≤ 2π, k = 1, 2, . . . , K. (64)

w k , θ ) > 0, (60) is equivalent to

Since we have Rk (w

1
λ∗k = , ∀k ∈ {1, 2, . . . , K}, (65)
w ∗k , θ ∗ )
Rk (w

and then (61) is equivalently written as

$k `k
βk∗ = , ∀k ∈ {1, 2, . . . , K}. (66)
w ∗k , θ ∗ )
Rk (w

Furthermore, Eq. (58), (59) and (64) are exactly the KKT conditions of Problem P2-E3, when
we set λ = λ ∗ and β = β ∗ . This proves the first conclusion of Proposition 3. Following the
same procedure, the second conclusion of Proposition 3 may also be readily shown.

R EFERENCES

[1] M. R. Palattella, M. Dohler, A. Grieco, G. Rizzo, J. Torsner, T. Engel, and L. Ladid, “Internet of things in the 5G era:
Enablers, architecture, and business models,” IEEE Journal on Selected Areas in Communications, vol. 34, no. 3, pp.
510–527, Mar. 2016.
[2] FP7 European Project (2012), “Distributed computing, storage and radio resource allocation over cooperative femtocells
(TROPIC),” http://www.ict-tropic.eu, [Online].
[3] S. Barbarossa, S. Sardellitti, and P. Di Lorenzo, “Communicating while computing: Distributed mobile cloud computing
over 5G heterogeneous networks,” IEEE Signal Processing Magazine, vol. 31, no. 6, pp. 45–55, Nov. 2014.
[4] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: Vision and challenges,” IEEE Internet of Things Journal,
vol. 3, no. 5, pp. 637–646, March 2016.
[5] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication
perspective,” IEEE Communications Surveys & Tutorials, vol. 19, no. 4, pp. 2322–2358, April 2017.
 30

[6] W. Zhang, Y. Wen, K. Guan, D. Kilper, H. Luo, and D. O. Wu, “Energy-optimal mobile cloud computing under stochastic
wireless channel,” IEEE Transactions on Wireless Communications, vol. 12, no. 9, pp. 4569–4581, Sep. 2013.
[7] Y. Wang, M. Sheng, X. Wang, L. Wang, and J. Li, “Mobile-edge computing: Partial computation offloading using dynamic
voltage scaling,” IEEE Transactions on Communications, vol. 64, no. 10, pp. 4268–4282, Oct. 2016.
[8] J. Ren, G. Yu, Y. Cai, and Y. He, “Latency optimization for resource allocation in mobile-edge computation offloading,”
IEEE Transactions on Wireless Communications, vol. 17, no. 8, pp. 5506–5519, Aug. 2018.
[9] T. Bai, J. Wang, Y. Ren, and L. Hanzo, “Energy-efficient computation offloading for secure UAV-edge-computing systems,”
IEEE Transactions on Vehicular Technology, vol. 68, no. 6, pp. 6074–6087, June 2019.
[10] S. Sardellitti, G. Scutari, and S. Barbarossa, “Joint optimization of radio and computational resources for multicell mobile-
edge computing,” IEEE Transactions on Signal and Information Processing over Networks, vol. 1, no. 2, pp. 89–103, June
2015.
[11] X. Chen, L. Jiao, W. Li, and X. Fu, “Efficient multi-user computation offloading for mobile-edge cloud computing,”
IEEE/ACM Transactions on Networking, vol. 24, no. 5, pp. 2795–2808, Oct. 2015.
[12] X. Lyu, W. Ni, H. Tian, R. P. Liu, X. Wang, G. B. Giannakis, and A. Paulraj, “Optimal schedule of mobile edge computing
for Internet of Things using partial information,” IEEE Journal on Selected Areas in Communications, vol. 35, no. 11, pp.
2606–2615, Nov. 2017.
[13] Y. Dai, D. Xu, S. Maharjan, and Y. Zhang, “Joint computation offloading and user association in multi-task mobile edge
computing,” IEEE Transactions on Vehicular Technology, vol. 67, no. 12, pp. 12 313–12 325, Dec. 2018.
[14] T. Ouyang, Z. Zhou, and X. Chen, “Follow me at the edge: Mobility-aware dynamic service placement for mobile edge
computing,” IEEE Journal on Selected Areas in Communications, vol. 36, no. 10, pp. 2333–2345, Oct 2018.
[15] T. J. Cui, M. Q. Qi, X. Wan, J. Zhao, and Q. Cheng, “Coding metamaterials, digital metamaterials and programmable
metamaterials,” Light: Science & Applications, vol. 3, no. 10, p. e218, 2014.
[16] W. Qingqing and Z. Rui, “Towards smart and reconfigurable environment: Intelligent reflecting surface aided wireless
network,” arXiv preprint arXiv:1905.00152, 2019.
[17] Y. Han, W. Tang, S. Jin, C.-K. Wen, and X. Ma, “Large intelligent surface-assisted wireless communication exploiting
statistical CSI,” IEEE Transactions on Vehicular Technology, vol. 68, no. 8, pp. 8238–8242, Aug. 2019.
[18] B. Zheng and R. Zhang, “Intelligent reflecting surface-enhanced OFDM: Channel estimation and reflection optimization,”
arXiv preprint arXiv:1909.03272, 2019.
[19] S. Abeywickrama, R. Zhang, and C. Yuen, “Intelligent reflecting surface: Practical phase shift model and beamforming
optimization,” arXiv preprint arXiv:1907.06002, 2019.
[20] Q. Wu and R. Zhang, “Intelligent reflecting surface enhanced wireless network via joint active and passive beamforming,”
IEEE Transactions on Wireless Communications, pp. 1–1, 2019.
[21] Q. Wu and R. Zhang, “Beamforming optimization for intelligent reflecting surface with discrete phase shifts,” arXiv preprint
arXiv:1810.03961, 2019.
[22] H. Guo, Y.-C. Liang, J. Chen, and E. G. Larsson, “Weighted sum-rate optimization for intelligent reflecting surface enhanced
wireless networks,” arXiv preprint arXiv:1905.07920, 2019.
[23] J. Ye, S. Guo, and M.-S. Alouini, “Joint reflecting and precoding designs for SER minimization in reconfigurable intelligent
surfaces assisted MIMO systems,” arXiv preprint arXiv:1906.11466, 2019.
[24] C. Pan, H. Ren, K. Wang, W. Xu, M. Elkashlan, A. Nallanathan, and L. Hanzo, “Intelligent reflecting surface for multicell
MIMO communications,” arXiv preprint arXiv:1907.10864, 2019.
[25] G. Zhou, C. Pan, H. Ren, K. Wang, W. Xu, and A. Nallanathan, “Intelligent reflecting surface aided multigroup multicast
MISO communication systems,” arXiv preprint arXiv:1909.04606, 2019.
 31

[26] C. Huang, G. C. Alexandropoulos, C. Yuen, and M. Debbah, “Indoor signal focusing with deep learning designed
reconfigurable intelligent surfaces,” arXiv preprint arXiv:1905.07726, 2019.
[27] Y. Yang, B. Zheng, S. Zhang, and R. Zhang, “Intelligent reflecting surface meets OFDM: Protocol design and rate
maximization,” arXiv preprint arXiv:1906.09956, 2019.
[28] M. Cui, G. Zhang, and R. Zhang, “Secure wireless communication via intelligent reflecting surface,” IEEE Wireless
Communications Letters, pp. 1–1, 2019.
[29] H. Shen, W. Xu, S. Gong, Z. He, and C. Zhao, “Secrecy rate maximization for intelligent reflecting surface assisted
multi-antenna communications,” IEEE Communications Letters, vol. 23, no. 9, pp. 1488–1492, Sep. 2019.
[30] D. Xu, X. Yu, Y. Sun, D. W. K. Ng, and R. Schober, “Resource allocation for secure IRS-assisted multiuser MISO systems,”
arXiv preprint arXiv:1907.03085, 2019.
[31] J. Chen, Y.-C. Liang, Y. Pei, and H. Guo, “Intelligent reflecting surface: A programmable wireless environment for physical
layer security,” arXiv preprint arXiv:1905.03689, 2019.
[32] Q. Wu and R. Zhang, “Weighted sum power maximization for intelligent reflecting surface aided SWIPT,” arXiv preprint
arXiv:1907.05558, 2019.
[33] C. Pan, H. Ren, K. Wang, M. Elkashlan, A. Nallanathan, J. Wang, and L. Hanzo, “Intelligent reflecting surface enhanced
MIMO broadcasting for simultaneous wireless information and power transfer,” arXiv preprint arXiv:1908.04863, 2019.
[34] S. Boyd and L. Vandenberghe, Convex optimization. Cambridge university press, 2004.
[35] S. He, Y. Huang, L. Yang, and B. Ottersten, “Coordinated multicell multiuser precoding for maximizing weighted sum
energy efficiency,” IEEE Transactions on Signal Processing, vol. 62, no. 3, pp. 741–751, March 2013.
[36] Y. Pan, C. Pan, Z. Yang, M. Chen, and J. Wang, “A caching strategy towards maximal D2D assisted offloading gain,”
IEEE Transactions on Mobile Computing, pp. 1–1, 2019.
[37] S. S. Christensen, R. Agarwal, E. De Carvalho, and J. M. Cioffi, “Weighted sum-rate maximization using weighted MMSE
for MIMO-BC beamforming design,” IEEE Transactions on Wireless Communications, vol. 7, no. 12, pp. 4792–4799, Dec.
2008.
[38] L.-L. Yang, Multicarrier communications. John Wiley & Sons, 2009.
[39] Y. Sun, P. Babu, and D. P. Palomar, “Majorization-minimization algorithms in signal processing, communications, and
machine learning,” IEEE Transactions on Signal Processing, vol. 65, no. 3, pp. 794–816, Feb. 2016.
[40] J. Song, P. Babu, and D. P. Palomar, “Sequence design to minimize the weighted integrated and peak sidelobe levels,”
IEEE Transactions on Signal Processing, vol. 64, no. 8, pp. 2051–2064, Apri 2015.
[41] A. Goldsmith, Wireless Communications. Cambridge University Press, 2005.
[42] M. L. Fisher, “The Lagrangian relaxation method for solving integer programming problems,” Management science, vol. 27,
no. 1, pp. 1–18, Jan. 1981.