Leila Reddy

Radoslaw Martin Cichy

Rufin Vanrullen

Representational content of oscillatory brain activity during object recognition

Numerous theories propose a key role for brain oscillations in visual perception. Most of these theories postulate that sensory information is encoded in specific oscillatory components (e.g., power or phase) of specific frequency bands. These theories are often tested with whole-brain recording methods of low spatial resolution (EEG or MEG), or depth recordings that provide a local, incomplete view of the brain. Opportunities to bridge the gap between local neural populations and whole-brain signals are rare. Here, using representational similarity analysis we ask which MEG oscillatory components (power and phase, across various frequency bands) correspond to low or high-level visual object representations, using brain representations from fMRI, or layer-wise representations in Deep Neural Networks (DNNs) as a template for low/high-level object representations. The results showed that around stimulus onset and offset, most transient oscillatory signals correlated with low-level brain patterns (V1). During stimulus presentation, sustained beta (~20Hz) and gamma (>60Hz) power best correlated with V1, while oscillatory phase components correlated with IT representations. Surprisingly, this pattern of results did not always correspond to low-or high-level DNN layer activity. In particular, sustained beta-band oscillatory power reflected high-level DNN layers, suggestive of a feed-back component. These results begin to bridge the gap between whole-brain oscillatory signals and object representations supported by local neuronal activations.

Introduction:

Oscillatory neuronal activity is thought to underlie a variety of perceptual functions. Different frequency bands can carry information about different stimulus properties (e.g., whether the stimulus consists of coarse or fine object features) [START_REF] Smith | Perceptual moments of conscious visual experience inferred from oscillatory brain activity[END_REF][START_REF] Romei | Rhythmic TMS over parietal cortex links distinct brain frequencies to global versus local visual processing[END_REF], feedforward or feedback signals [START_REF] Van Kerkoerle | Alpha and gamma oscillations characterize feedback and feedforward processing in monkey visual cortex[END_REF][START_REF] Bastos | Visual areas exert feedforward and feedback influences through distinct frequency channels[END_REF], or may reflect neuronal communication between different neuronal populations (Fries 2005, Jensen and[START_REF] Jensen | Shaping functional architecture by oscillatory alpha activity: gating by inhibition[END_REF]. Other studies have shown that different components of an oscillation (e.g., its power or phase) encode different types of sensory information [START_REF] Smith | Perceptual moments of conscious visual experience inferred from oscillatory brain activity[END_REF].

Although neuronal oscillations are observed in different brain regions, and key theories hold that they reflect processing within, and communication between, brain regions (Fries 2005, Jensen and[START_REF] Jensen | Shaping functional architecture by oscillatory alpha activity: gating by inhibition[END_REF], it has been difficult to pin down how large-scale brain oscillations are related to local patterns of neural activity, and how this relationship unfolds over time. This is because oscillatory activity is often studied with methods such as EEG or MEG, which have low spatial resolution. Although oscillatory signals with high spatial specificity can be recorded via local field potential recordings in humans or animals, these methods usually only target specific brain regions, and thus can only provide a partial view of oscillatory activity and its role in large-scale brain function. A direct link between large-scale oscillations and local neural activity is missing.

Here, we combine large-scale oscillatory signals recorded by MEG with local patterns of neural activity recorded with fMRI to bridge the gap between oscillatory components and the different levels of object representation in the brain. Using representational similarity analysis (RSA, [START_REF] Kriegeskorte | Representational similarity analysis -connecting the branches of systems neuroscience[END_REF])), we investigate the information carried by whole-brain oscillations obtained from MEG, and examine how this information evolves over time during an object recognition task.

We define three distinct dimensions of interest along which neural representations may unfold, and which are often conflated in the literature. First, we use the terms "early" and "late" to denote the temporal evolution of representations. Second, we differentiate between "low-level" and "high-level" stages of a processing hierarchy. Third, we consider the complexity of representations by distinguishing between "basic" and more "refined" information. In many information processing systems and in many typical experimental situations, these three dimensions are directly related to one another, as input information propagates over time through a succession of hierarchical stages, becoming more and more refined along the way. In such situations, the three dimensions of interest are in fact redundant and need not be further distinguished. But in systems with recurrence and feedback loops (like the brain), time, space and information complexity are not always linearly related. For example, a lower hierarchical level (e.g. V1) can carry more refined representations, later in time, as a result of feedback loops or lateral connections [START_REF] Lamme | The distinct modes of vision offered by feedforward and recurrent processing[END_REF]. In our terminology, such a representation would be classified as late in time, low-level in the hierarchy, yet refined in terms of complexity.

In this work, we consider two main hierarchical systems. We are interested in understanding information processing in the human brain, so we use V1 and IT fMRI brain representations, as done in a number of recent studies (Cichy, Pantazis et al. 2014, Khaligh-Razavi and[START_REF] Khaligh-Razavi | Deep supervised, but not unsupervised, models may explain IT cortical representation[END_REF]. Representational similarity between MEG oscillations and this fMRI-based hierarchy can be interpreted in terms of early and late representations (based on the timing of the MEG oscillations), and in terms of low-level (V1) vs. high-level (IT) hierarchical stages. To assess the complexity of representations independent of temporal evolution and hierarchy of processing, we related our data to a second class of hierarchical systems: artificial feed-forward Deep Neural Networks (DNNs). In these artificial networks, the hierarchical level (low-level vs. high-level) is directly related to feature complexity (basic vs. refined representations), due to the absence of feed-back or recurrent loops. For any MEG oscillatory signal, representational similarity with DNN activation patterns can thus inform us about representational complexity. In turn, any difference between DNN-based and brain-based RSA may be suggestive of feed-back or recurrent influences in the MEG oscillatory signals.

With this dual approach, we find a complex picture of transient and sustained oscillatory signals that can be related to V1 and IT representations. Transient oscillatory components around stimulus onset and offset, as well as sustained beta (~20Hz) and gamma (>60Hz) power components resemble V1 representations, while phase-dependent sustained activity correlates best with IT representations. However, when compared to DNNs, some early V1-like components actually correlate more with higher DNN layers, suggesting that stimulus representations early in time may already include refined information, presumably as a result of feedback or top-down influences [START_REF] Kar | Evidence that recurrent circuits are critical to the ventral stream's execution of core object recognition behavior[END_REF][START_REF] Kietzmann | Recurrence is required to capture the representational dynamics of the human visual system[END_REF].

In effect our results narrow the gap between the description of neural dynamics in terms of whole-brain oscillatory signals and local neural activation patterns. Disentangling temporal evolution, hierarchical stage of processing and complexity of representations from each other, our approach allows for a more nuanced view on cortical information flow in human object processing.

Methods:

Experimental paradigm and data acquisition: The data analyzed in this study was obtained from [START_REF] Cichy | Resolving human object recognition in space and time[END_REF], and detailed methods can be obtained from that paper.

Fifteen subjects performed separate MEG and fMRI sessions while they viewed a set of 92 images. The image set consisted of human and non-human faces and bodies, and artificial and natural everyday objects. The 92-image stimulus set was taken from the Kiani image set [START_REF] Kiani | Object category structure in response patterns of neuronal population in monkey inferior temporal cortex[END_REF], which consists of cutout objects on a gray background.

In the MEG sessions, each image was presented for 0.5s followed by an inter-stimulus interval (ISI) of 1.2 or 1.5s. Every 3-5 trials, a target paperclip object was presented, and subjects' task was to press a button and blink whenever they detected this target image. Subjects performed 2 MEG sessions, of 2 hours each. In each session they performed between 10 to 15 runs. Each image was presented twice in each run, in random order.

In each of two fMRI sessions, each image was presented for 0.5s followed by an ISI of 2.5 or 5.5s. Subjects' task in the fMRI sessions was to press a button when they detected a color change in the fixation cross on 30 null trials, when no image was presented. Each image was presented once in each fMRI run, and subjects performed 10-14 runs in each session.

The MEG data was acquired from 306 channels (204 planar gradiometers, 102 magnetometers, Elekta Neuromag TRIUX, Elekta, Stockholm) at the Massachusetts Institute of Technology. The MRI experiment was conducted on a 3T Trio scanner (Siemens, Erlangen, Germany), with a 32-channel head coil. The structural images were acquired using a T1-weighted sequence (192 sagittal slices, FOV = 256mm 2 , TR=1,900ms, TE=2.52ms, flip angle=9 degrees). For the fMRI runs, 192 images were acquired for each participant (gradient-echo EPI sequence: TR = 2,000ms, TE=32 ms, flip angle = 80 degrees, FOV read = 192 mm, FOV phase = 100%, ascending acquisition gap = 10%, resolution = 2mm, slices=25). From the MEG signals, the complex time frequency (TF) transform was computed for each of the 306 MEG sensors. The amplitude and phase (separated into cosine and sine) values were extracted from the complex number at each TF coordinate, and a MEG RDM was constructed, reflecting the distance between oscillatory activation patterns for every pair of images (i,j) (see methods for details). As a result, we obtained a power and phase MEG RDM at each TF coordinate for each participant. (b) fMRI RDMs were obtained from [START_REF] Cichy | Resolving human object recognition in space and time[END_REF]. Two regions of interest (ROI) were defined: V1 and IT and one fMRI RDM was obtained for each ROI, and each participant, reflecting the distance between BOLD activation patterns for every pair of images (i,j). (c) The MEG power or phase RDMs were compared to the fMRI RDMs (V1 or IT) by computing the partial Pearson's R. This step was performed at each TF coordinate, resulting in an RSA map of R values at each TF coordinate, for each subject and ROI.

MEG analysis -preprocessing: MEG trials were extracted with a 600 ms baseline before stimulus onset until 1200 ms post-stimulus onset. A total of 20-30 trials were obtained for each condition, session, and participant. Each image was considered as a different condition.

Data were analyzed using custom scripts in Matlab (Mathworks) and FieldTrip [START_REF] Oostenveld | FieldTrip: Open source software for advanced analysis of MEG, EEG, and invasive electrophysiological data[END_REF]. Data were downsampled offline to 500 Hz. For each trial and sensor, we computed the complex time frequency decomposition using multitapers. Parameters used were: 50 distinct frequencies increasing logarithmically from 3 to 100 Hz, over a time interval of -600ms to 700ms with respect to stimulus onset, in steps of 20 ms. The length of the sliding time window was chosen such that there were two full cycles per time-window. The amount of smoothing increased with frequency (0.4 * frequency).

From the complex number at each time-frequency (TF) coordinate, we extracted two measures for each sensor and each condition: the power and the phase of the oscillation. For each channel and condition, on each trial, the power was first expressed in decibels, and then averaged across trials to obtain one power value per condition. The phase of the oscillation was obtained by first normalizing each trial to make each trial's vector in the complex domain of unit length, and then averaging across trials for each condition. The resultant average vector was then normalized to unit length, and the sine (real) and cosine (imaginary) components were extracted for each condition and each sensor. 1a): At each TF coordinate and for each condition, we next arranged the 306 power values from the 306 MEG sensors into a 306-dimensional vector representing the power pattern vector for that condition. Similarly, at each TF coordinate and for each condition we concatenated the 306 sine and 306 cosine values into a 612-dimensional phase pattern vector for that condition.

MEG analysis -multivariate analysis (Figure

We next computed two representational dissimilarity matrices (RDMs): one for power and one for phase, at each TF point. For each pair of conditions, the power (phase) pattern vectors were correlated using the Pearson correlation measure, and the resulting 1-correlation value was assigned to a 92 by 92 power (phase) RDM, in which the rows and columns corresponded to the images being compared. This matrix is symmetric across the diagonal. This procedure results in one power (phase) RDM at each TF point. fMRI analysis (Figure 1b): The preprocessing steps for the fMRI data are described in detail in [START_REF] Cichy | Resolving human object recognition in space and time[END_REF]. For the multivariate analysis, two regions of interest (ROIs) were defined: V1 and IT. In each subject, for each ROI, voxel activation values were extracted for each condition, and the resulting values were arranged in a pattern vector for each condition. Then, in each ROI, for each pair of conditions, the corresponding pattern vectors were correlated using the Pearson correlation measure, and the resulting 1-correlation value was assigned to the 92x92 fMRI RDM. For further analysis the fMRI RDMs were averaged across the 15 subjects, resulting in one RDM per ROI. The fMRI RDMs were provided by R. Cichy, D. Pantazis and A. Oliva [START_REF] Cichy | Resolving human object recognition in space and time[END_REF]. 1c): RSA between the MEG and fMRI RDMs was performed by computing the partial Pearson's correlation between each MEG (phase or power) RDM with each fMRI RDM (V1 or IT), while partialling out any contribution from the other fMRI RDM (IT or V1). We chose to perform a partial correlation because the V1 and IT RDMs were positively correlated with each other (r~0.3); compared to a standard correlation, the partial correlation allowed us to isolate the unique correlation of each fMRI RDM with the MEG RDM, while discarding their joint contribution.

MEG-fMRI Representational Similarity Analysis (RSA) (Figure

This procedure resulted in four RSA maps (power/phase MEG RDMs x V1/IT fMRI RDMs). Each RSA map shows the R-value between the MEG signals and the V1/IT activation patterns at each TF point. Significance of the RSA result was evaluated with a paired t-test against 0, FDR corrected, alpha = 0.05.

Clustering analysis:

The MEG time-frequency RDMs are heavily correlated with each other. To facilitate the interpretation of the information content of oscillatory signals, and to determine which features co-vary and which are independent, K-means clustering was performed on the MEG power and phase RDMs. Clustering was performed on the 4186-dimensional ((92*92-92)/2) RDMs across all (66) time points and (46) frequency points, combining the power and phase signals (resulting in 46*66*2 = 6072 data points to cluster in a 4186-dimensional space). K-means was implemented with the Matlab function kmeans, with the correlational distance measure, five replicates, and the number of clusters going from 1 to 20. The optimal number of clusters was then determined with the elbow criterion defined as the point just before the local maximum of the second derivative of the residual sum of squares (corresponding to the point at which adding another cluster would only provide a marginal gain in variance explained). With this method, the first elbow, occurred at k=7 clusters.

The chosen clusters could be visualized by plotting the correlation distance (in the 4186-dimensional RDM space) between the cluster's centroid and every time-frequency point, for both power and phase signals.

RSA (using partial Pearson's correlation) was performed between each cluster's centroid and each of the fMRI RDMs (see below). For RSA with fMRI, this procedure resulted in two RSA values (one each for V1 and IT). Since each cluster centroid could correspond to both V1 and IT to different degrees, the information content of the cluster was positioned somewhere between V1/low-level and IT/high-level using the following equation:

𝐼𝐼 = 𝜎𝜎 � (𝑅𝑅 𝐼𝐼𝐼𝐼 -𝑅𝑅 𝑉𝑉1 ) (𝑅𝑅 𝐼𝐼𝐼𝐼 + 𝑅𝑅 𝑉𝑉1 ) � � (eq. 1)
where σ denotes the sigmoid function. The measure I could vary between 0 (when the cluster's representational content was perfectly similar to V1) and 1 (when it was perfectly similar to IT).

Significance of RSA between the cluster centroids and the fMRI RDMs was computed with a surrogate test. On each iteration, the cluster centroid RDM was randomly shuffled and the partial correlation was computed between this shuffled RDM and the true RDM. This procedure was repeated for 10 5 iterations, and the number of iterations on which the shuffled RSA values were higher than the true RSA values was counted.

Deep Neural Network (DNN) RDMs:

The MEG phase/power representations were also compared to representations in four DNNs (so as to ensure that conclusions were not dependent on one specific network architecture): AlexNet [START_REF] Krizhevksy | Imagenet classification with deep convolutional neural networks[END_REF]), VGG16 (Simonyan and Zisserman 2014), GoogleNet [START_REF] Szegedy | Going deeper with convolutions[END_REF], and InceptionV3 [START_REF] Szegedy | Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning[END_REF] processing the same 92 images as in our MEG and fMRI data. However, in contrast to our 92-image stimulus set, which consisted of cutout objects on a gray background, the DNNs had been trained on images from ImageNet (millions of photographs with one or more objects in natural backgrounds). The networks had thus learned optimal representations for their training set, but in this representation space our 92 images tended to cluster into a remote "corner" (Figure 2), with low dissimilarity (1-Pearson's R) values between images, and a resulting RDM of poor quality. To retrieve meaningful distances between the representations of the 92 images, we first performed a centering procedure: we centered the activation of each layer of each DNN by subtracting the mean activation of an independent set of 368 images from the Kiani image set. This independent image set consisted of four images from each of the categories in our 92-image set. Importantly, because the image set used for centering did not include any of the 92 images from our study, there was no circularity in the centering operation, nor any leakage of information between the representations of our 92 images.

RDMs were constructed for each convolutional layer of each network based on the layer activation values. There were 5 layers for AlexNet, 13 for VGG16, 12 for GoogleNet and 16 for InceptionV3. RSA was then performed (with the Spearman correlation) between these RDMs and the centroid of each cluster (see above for details of the clustering analysis). The layer with maximum RSA, normalized by the number of layers in the DNN, was taken to reflect the information content of this cluster between 0 (in the terminology defined in the Introduction, "low-level" and basic, corresponding to the DNN's first layer) and 1 ("high-level" and refined, corresponding to the DNN's last layer), and finally averaged across the four DNNs. However, as the t-SNE visualizations show, our 92 images are all projected into a remote corner of this space, meaning that the RDM distances between the 92 images are confounded by the mean vector (the pairwise Pearson distance depends more on the alignment with the mean vector, and less on the true physical distance between points). To circumvent this problem, we used a re-centering approach as described in the methods section.

Results:

Fifteen participants viewed the same set of 92 images while fMRI and MEG data was recorded (in separate sessions). The image set consisted of human and non-human bodies and faces, and artificial and natural stimuli. Each stimulus was presented for 0.5s, followed by a 1.2 or 1.5s baseline period.

To assess oscillatory components, we extracted stimulus-related activity from -600ms to 1200ms relative to stimulus onset from the MEG data. For each trial, and each sensor a time-frequency (TF) decomposition was performed, and a power and phase value extracted at each time and frequency point. These values were used to compute representational dissimilarity matrices (RDMs) at each TF point, separately for power and phase (Methods and Figure 1a). Each element in the MEG RDMs indicates how distinct the corresponding images are in the MEG power or phase spaces, and the entire MEG RDM is a summary of how the 92-image stimulus set is represented in the MEG oscillatory power or phase at each TF point.

To assess local patterns of neural activity we generated fMRI RDMs by performing comparisons between the local BOLD activation patterns of pairs of images in V1 and IT [START_REF] Cichy | Resolving human object recognition in space and time[END_REF]. Two fMRI RDMs were obtained (Figure 1b), one for V1 and one for IT. The fMRI RDMs are a measure of the representation of the image set in the voxel space of V1 and IT local neural activity.

Bridging the space, time and frequency gap in object recognition:

How similar is the oscillatory representation of the images to their representation in each brain region?

The MEG RDMs (power and/or phase) at each TF point represent the stimulus set in a large-scale brain oscillatory activity space, while the fMRI RDMs represent the same image set via BOLD activity in a local population of neurons in two brain regions (V1 or IT). We evaluated the similarity of representations in the time-frequency domain with those in the fMRI activation patterns by computing the partial Pearson's correlation between the MEG RDMs (phase or power) with the fMRI RDMs (V1/IT), at each TF point (Figure 1c). This analysis resulted in four time frequency maps of R-values (or RSA maps), which provide the unique correspondence between whole-brain oscillations and local patterns of neural activity in V1 and IT, at each TF point (Figure 3). With these maps we can ask if and when stimulus information contained in oscillatory phase or power at each TF point resembles BOLD activations in a given brain region (V1/IT), and potentially, which region it resembles more. The advantage of measuring partial correlation (instead of a standard correlation) is to discard the (potentially large) portion of the variance in oscillatory representations that is explained equally well by V1 or IT BOLD representationsowing to the fact that V1 and IT signals already share similarities. This way, we concentrate on the part of oscillatory representations that uniquely explained by each brain region-of-interest.

Figure 3: Results of the 2x2 RSA comparisons (MEG power/phase x fMRI V1/IT), averaged over all subjects. The purple contours mark those regions in the maps that are significantly different from zero (paired ttest against 0 across N=15 subjects, FDR correction, alpha = 0.05). Note that the absolute latencies are not directly comparable across frequencies, because of different smoothing windows applied at the different frequencies when performing the TF transform (hence, the x-axis is labeled as uncorrected time).

Our results show that different oscillatory components map to different brain regions at different moments in time. Overall, the absolute maximum of representational similarity with brain area V1 occurred in the alpha band around 120ms post-stimulus for oscillatory power, whereas the absolute maximum related to area IT occurred for theta-and alpha-phase around 200-300ms. More generally, a strong increase in representational similarity was observed shortly after stimulus onset in all four maps. The frequency, latency and duration of these similarity effects depended however on the exact oscillatory signal (power, phase) and brain region (V1, IT). In terms of MEG power (Figure 3a, b), the latencies (see also Figure 4) respected the hierarchical order of visual processing [START_REF] Nowak | The timing of information transfer in the visual system[END_REF] with an increase in representational similarity in the lower (<20 Hz) frequency bands occurring around the evoked response first for V1, and about 20-30ms later for IT (paired t-test against 0, FDR corrected, alpha=0.05). This latency difference is similar to that reported in [START_REF] Cichy | Resolving human object recognition in space and time[END_REF], where the peak correspondence between the average MEG signal and V1 activity occurs about 30 ms prior to the peak with IT activity. The onset response in V1 also consisted of high gamma frequencies (>70Hz), whereas this high-gamma activity was not observed in IT. A sustained low-beta (20Hz, 200-500ms) and an offset high-beta (30Hz, ~600ms) response also corresponded to V1 representations, although neither of these effects were observed in IT (see also Figure 4). In terms of stimulus representations in the MEG oscillatory phase (Figure 3c,d), after an initial broadband (3-100Hz) transient peak at stimulus onset corresponding to V1 representations, stimulus information carried by sustained oscillatory phase resembled IT representations in the low (<20Hz) and high frequency (60Hz) bands, and this resemblance persisted until the end of the trial. Phase representations corresponding to V1 patterns were observed again around stimulus offset, at alpha (~10Hz) and beta (20-30Hz) frequencies (see also Figure 4).

These results thus suggest that different oscillatory components correspond to different brain regions at different time-frequency points. However, since the RDMs in the time-frequency space are heavily correlated with each other, it is difficult to ascertain from this analysis which power/phase features covary, and which effects occur independently. To better interpret the results shown in Figure 3 we turned to a clustering analysis. The clustering analysis allowed us to reduce the dimensionality of the dataspace and to determine which oscillatory signals occurred jointly, and which are independent. We performed k-means clustering jointly on the power and phase RDMs. The results of the clustering analysis for k=7 clusters (the "optimal" number of clusters for our dataset) are shown in Figure 5 (see also Figure 6). The first cluster (ranked by smallest distance from cluster centroid) corresponded to early broadband (0-100 Hz) phase and power RDMs, followed by sustained gamma power (>60Hz), and beta power (20-30Hz) at stimulus offset. The second cluster corresponded to broadband (0-100Hz) and sustained (0.1-0.4s) phase effects after stimulus onset, without any noticeable power effects. The third cluster consisted primarily of sustained (0.1-0.6s) beta (10-30Hz) and low-gamma (<60Hz) power, without any noticeable phase effects. The fourth cluster reflected broadband phase effects (0-100Hz) at stimulus offset (without associated power effects). The last 3 clusters (5-7) all displayed pre-stimulus effects in alpha-beta power, or alpha or gamma phase, characteristic of spontaneous, stimulus-unrelated activity that we did not investigate further (Figure 6). The clustering analysis performed on the MEG RDMs thus identified four main clusters of power and phase oscillatory components that occurred at different time points and in different frequency bands after stimulus onset.

Figure 4. Profile of the results of the RSA with V1 (green lines) and IT (black lines) in oscillatory power (top row) and oscillatory phase (bottom row) in different frequency bands. To examine the RSA maps in more detail, we extracted their time courses in different traditional frequency bands: alpha (8-13 Hz), low-beta (13-20 Hz), and highbeta (20-32 Hz). In each of these frequency bands we computed the average R-values. Since the TF decomposition induces temporal smearing, and the amount of smearing differs for different frequencies, in order to interpret the latencies of the representational similarities, we corrected for this smearing effect. Specifically, to avoid underestimating the onset latencies, we corrected time by adding half the wavelet window duration at each frequency. Note that the same correction was applied to the two curves compared in each plot. Solid lines are the means across subjects, and the shaded areas correspond to the SEM across subjects.

How do the oscillatory representations in each cluster, and their different time and frequency profiles relate to local processing in V1 and IT as measured by fMRI representations? To address this question, we performed RSA between the cluster centroids and the V1 and IT RDMs. The cluster centroids correlated to different degrees with both V1 and IT (all partial R-values between 0.12 and 0.49; all significant at p < 1e-5 with a surrogate test; see methods). To evaluate the relative importance of each area's representational similarity with the cluster centroid, we combined the two RSA partial R-values into a single scale (see Methods, equation 1). According to this scaling (see insets in Figure 5), the transient broadband phase and power effect with sustained gamma power in cluster 1 corresponded best with V1 representations (i.e., "low-level"). Conversely, the broadband sustained phase effects of cluster 2 corresponded best to IT representations ("high-level"). The other two clusters (sustained betagamma power in cluster 3, broadband offset-transient phase in cluster 4) had more balanced similarity to both V1 and IT, with a slight inclination towards V1. Thus, transient oscillatory components occurring around stimulus onset correspond more closely to V1 representations, whereas the more sustained components could be either more IT-like, or less localized depending on the frequency of the oscillations. These results thus suggest a complex link between oscillatory representations and local processing in V1 or IT. To try to clarify these relationships we next turned to using deep neural networks as a template for object representations.

Figure 5: Clustering analysis. K-means clustering was performed on the MEG power and phase RDMs. Each timefrequency plot shows the distance of each RDM from the centroid of the cluster. The purple lines correspond to the cluster boundaries as returned by the k-means algorithm, indicating that all points within the purple lines are assigned to this specific cluster based on their distance to the different cluster centroids. The insets show the relative degree of RSA between the cluster centroid and V1/IT (top), or the cluster centroid and the DNN layer hierarchy (bottom). For the DNNs, the layer with maximum RSA, normalized by the number of layers in the DNN hierarchy, and averaged across the four DNN types (colored ticks), was taken as the layer that corresponded to each cluster centroid (black arrowhead).

Assessing representational complexity with deep neural networks:

The fMRI RDMs are a representation of the image set in the multi-voxel space of V1 and IT. However, these fMRI representations are static because the fMRI BOLD signal used to construct the RDMs was measured over a period of several seconds. Neuronal activity in these regions, on the other hand, is known to evolve over fairly rapid timescales, on the order of hundreds of milliseconds as a result of feedback and top-down signals [START_REF] Roelfsema | Object-based attention in the primary visual cortex of the macaque monkey[END_REF][START_REF] Lamme | The distinct modes of vision offered by feedforward and recurrent processing[END_REF]. The fMRI RDMs are thus limited representations of the image set, potentially mixing basic and refined brain activity from different moments in each trial. Therefore, while it is tempting to interpret the oscillatory signals composing cluster 1 as basic in complexity, because they are more V1-like, and those forming cluster 2 as refined (more IT-like), such a conclusion would be premature as it ignores the dynamics of neural responses within and across brain regions, and how these neural responses evolve over different timescales. To obtain a complementary picture of low and high-level object representations, we considered the representations of our image set in different layers of feed-forward deep neural networks (DNNs) pretrained on a large dataset of natural images. To ensure the generality of our results we assessed four different DNNs: (AlexNet [START_REF] Krizhevksy | Imagenet classification with deep convolutional neural networks[END_REF], VGG16 [START_REF] Simonyan | Very Deep Convolutional Networks for Large-Scale Visual Recognition[END_REF], GoogleNet [START_REF] Szegedy | Going deeper with convolutions[END_REF], and InceptionV3 [START_REF] Szegedy | Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning[END_REF]). Activity in each layer of these DNNs is not influenced by top-down or recurrent connections, and consequently represents a truly hierarchical evolution in the complexity of image representations, from basic to refined. Indeed, several studies have suggested that DNN representations approximate the feed-forward cascade of the visual processing hierarchy in the brain (Khaligh-Razavi and Kriegeskorte 2014, [START_REF] Cichy | Comparison of deep neural networks to spatio-temporal cortical dynamics of human visual object recognition reveals hierarchical correspondence[END_REF]. Performing RSA between MEG oscillatory RDMs and DNN layer RDMs should thus reveal which features of the MEG oscillatory representations correspond to basic vs. refined object representations.

An RDM was obtained for each convolutional layer of the four DNNs. RSA was then performed between the cluster centroids of the MEG RDMs and the DNN RDMs. For each cluster and DNN, the layer with maximum RSA was determined, and scaled between 0 (lowest layer, basic information) and 1 (highest layer, refined information) based on the number of layers in the DNN hierarchy. Despite slight differences between the four DNNs, the analysis revealed that clusters 2 and 3 mapped best to higher DNN layers, cluster 1 to intermediate layers, and only cluster 4 had similarity to lower layers. This is in stark contrast with the results of fMRI RSA, which had ranked clusters 2, 4, 3 and 1 in order of decreasing complexity. The most striking difference is obtained for cluster 3 (sustained beta-gamma power): a highlevel refined representation according to DNNs, but closer to V1 than to IT according to fMRI. Based on the logic above, this cluster is likely to reflect feed-back signals that carry refined object information (visible in high DNN layers) down to lower brain regions (visible in V1 BOLD signals).

Figure 6: Clustering results for clusters 5-7. We identify these clusters as noise components because (i) their distance to the cluster centroid is typically higher than for other clusters, and (ii) they mainly map onto pre-stimulus oscillatory activity. Pre-stimulus oscillations, while accounting for a sizeable portion of the (notoriously noisy) MEG signal variance, cannot possibly encode the identity of a stimulus that has not been presented yet. Pre-stimulus alpha is a well-studied oscillatory component reflecting the attention state of the observer, and whose phase is known to modulate the subsequent ERP amplitudes and latencies; as such, it is not surprising that the phase of this oscillatory component would induce a separate cluster of RDM patterns (cluster 5). Similarly, pre-stimulus alpha-beta power (cluster 6) and gamma phase (cluster 7) could reflect preparatory attention or motor signals (including muscular artifacts) not related to stimulus identity. Notations as in Figure 5.

Discussion:

Our results show that MEG oscillatory components at different frequencies carry stimulus-related information at specific times, which can be linked, via RSA, to stimulus representations in different brain regions (V1, IT), and with different representational complexity (as measured by deep neural networks). Importantly, the representational dynamics of brain oscillations can be very differently expressed by power vs. phase signals. At stimulus onset and offset, broadband phase transients (possibly related to fluctuations in evoked potential latencies) carry mainly basic or intermediate-complexity information (clusters 1, 4 in Figure 5). However, during stimulus presentation, sustained phase information is visible across all frequencies, and consistently maps to high-level refined representations (IT and high DNN layers, cluster 2). Oscillatory power components (clusters 1 and 3) tend to correlate with both V1 and IT fMRI representations (with an inclination towards V1); however, onset-transient low-frequency (<20Hz) power together with sustained high-frequency (>60Hz) power (i.e., cluster 1) correspond best to intermediate DNN layers, whereas sustained beta-gamma power (20-60Hz) clearly maps to the highest DNN layers (cluster 3).

In Our results highlight the importance of complementing MEG-fMRI RSA with another measure of representational content such as feed-forward DNNs [START_REF] Hebart | The representational dynamics of task and object processing in humans[END_REF][START_REF] Khaligh-Razavi | Tracking the Spatiotemporal Neural Dynamics of Real-world Object Size and Animacy in the Human Brain[END_REF]. fMRI BOLD signals are often analyzed such that they reflect a single static representation. Thus, they cannot distinguish dynamics in local patterns as for example early feedforward and later feedback activity. By design, feedforward DNN layers cannot be dynamically influenced by feedback signals, and could be considered to provide a template for basic vs. refined representations during the different stages of image processing. Perhaps the best illustration of this notion stems from the discrepancy between fMRI and DNN RSA for MEG cluster 3, which suggests that sustained beta-gamma power during stimulus presentation could reflect feedback signals: best corresponding to V1 fMRI activity (low-level), but higher DNN layers (refined). Without this additional information (e.g., looking at Figure 3a alone), one might have interpreted sustained beta-power as a strictly low-level signal. The observed distinction between sustained power effects at lower frequencies (beta and low-gamma, cluster 3) vs. higher frequencies (high-gamma, cluster 1) is consistent with a large number of recent studies that reported a functional distinction between gamma-band and betaband signals, respectively supporting feed-forward and feedback communication [START_REF] Fontolan | The contribution of frequency-specific activity to hierarchical information processing in the human auditory cortex[END_REF][START_REF] Van Kerkoerle | Alpha and gamma oscillations characterize feedback and feedforward processing in monkey visual cortex[END_REF][START_REF] Bastos | Visual areas exert feedforward and feedback influences through distinct frequency channels[END_REF][START_REF] Michalareas | Alpha-Beta and Gamma Rhythms Subserve Feedback and Feedforward Influences among Human Visual Cortical Areas[END_REF]. Future work could attempt to separate feedforward from feedback signals (e.g. with backward masking), to confirm the differential contribution of gamma and beta-band oscillatory frequencies to feedforward vs. feedback object representations, as determined with RSA.

In addition to their involvement in the transmission of feedforward and feedback signals, several studies have shown that different oscillations can carry distinct information about stimulus properties [START_REF] Hebart | The representational dynamics of task and object processing in humans[END_REF][START_REF] Khaligh-Razavi | Tracking the Spatiotemporal Neural Dynamics of Real-world Object Size and Animacy in the Human Brain[END_REF]). Here we considered whether oscillatory components in different frequencies correspond to basic or more refined stimulus processing stages.

Our results suggest that most oscillatory brain activity, at least at the broad spatial scale that is measured with MEG, reflects already advanced stimulus processing in object detection tasks. This result can be seen in Figure 5 where most oscillatory components are more related to higher-level DNN layer representations, with the exception of the offset-transient (cluster 4). Indeed, one might have expected that stimulus representations at both stimulus onset and offset are more reflective of transient lowlevel/basic processing. However, while both onset and offset signals (cluster 1 and cluster 4) are better matched to V1 than IT ("low-level", see also Figure 3c,d), in terms of DNN activations the offset-transient (cluster 4) appears to be much more basic in complexity and the onset-transient more refined (cluster 1). A tentative explanation could be that the continued presence of the stimulus after the onset-transient supports a rapid refinement of object representations, which would not be the case for the offsettransient (because the stimulus is absent from the retina). Indeed, it is remarkable that, aside from this offset-transient broadband phase activity (cluster 4), no other oscillatory signal was found to reflect lowlevel DNN layers (i.e., basic information).

In conclusion, our results help characterize the representational content of oscillatory signals during visual object perception. By separately considering hierarchical level (V1/IT) and representational complexity (based on DNNs), we narrow the gap between whole-brain oscillations and visual object representations supported by local neural activation patterns.

Figure 1 :

 1 Figure 1: MEG-fMRI RSA analysis. (a) MEG analysis and MEG representational dissimilarity matrices (RDMs).From the MEG signals, the complex time frequency (TF) transform was computed for each of the 306 MEG sensors. The amplitude and phase (separated into cosine and sine) values were extracted from the complex number at each TF coordinate, and a MEG RDM was constructed, reflecting the distance between oscillatory activation patterns for every pair of images (i,j) (see methods for details). As a result, we obtained a power and phase MEG RDM at each TF coordinate for each participant. (b) fMRI RDMs were obtained from[START_REF] Cichy | Resolving human object recognition in space and time[END_REF]. Two regions of interest (ROI) were defined: V1 and IT and one fMRI RDM was obtained for each ROI, and each participant, reflecting the distance between BOLD activation patterns for every pair of images (i,j). (c) The MEG power or phase RDMs were compared to the fMRI RDMs (V1 or IT) by computing the partial Pearson's R. This step was performed at each TF coordinate, resulting in an RSA map of R values at each TF coordinate, for each subject and ROI.

Figure 2 :

 2 Figure 2: t-SNE visualizations of 500 ImageNet samples and the 92-image stimulus-set used in this study across two representative layers of the VGG network.The DNNs used in this study had been trained on images from ImageNet, which consists of millions of photographs of one or more objects in natural backgrounds. In contrast, our 92-image stimulus set consists of cut-out images on a gray background. The DNNs learn optimal representations for the training images from ImageNet, i.e., different images from different categories are mapped to different regions of the representation space, and the whole space tends to be equally occupied by the training samples. However, as the t-SNE visualizations show, our 92 images are all projected into a remote corner of this space, meaning that the RDM distances between the 92 images are confounded by the mean vector (the pairwise Pearson distance depends more on the alignment with the mean vector, and less on the true physical distance between points). To circumvent this problem, we used a re-centering approach as described in the methods section.

  our study we found no simple mapping between low/high-level (or basic/refined) representations and oscillatory components (power/phase) or frequency. Both low-frequency (theta, alpha) and highfrequency (beta, gamma) oscillatory signals can carry either low/basic or high-level/refined representations at different times (e.g. clusters 2 vs. 4). Similarly, both phase and power signals can carry either low or high-level representations (e.g. clusters 1 vs. 3). The picture that emerges is a rather complex one, in which successive interactions between different oscillatory components in different brain regions and at different frequencies reflect the different stages of neural processing involved in object recognition.


Ioanna-Vasiliki Stypsanelli

Samir Medjiah

Balakrishna J Prabhu

Reducing Service Migrations in Fog Infrastructures by Optimizing Node Location

Keywords: fog computing, service migration, integer linear programming, weighted set cover, greedy heuristic

In order to ensure service continuity of connected cars moving inside a Fog Computing infrastructure under a Service Level Agreement, a service needs to migrate from a fog node to another. An approach is to always keep migrating the service towards the fog node that is the closest to the current position. However, frequent service migrations have a migration and network cost. Intuitively, the more migrations are triggered, the bigger this cost is. In this work we look into ways to reduce this cost by studying how to minimize the number of VM migrations triggered.

We introduce a general case in which we minimize a linear combination of the infrastructure cost and the number of service migrations given statistics on the routes taken by the vehicles. This problem can be represented as a bipartite graph where the minimization problem is an instance of the Weighted Set Cover problem.

For a special case of pair-wise mobility model in which the origin and destination of vehicles are in the coverage range of adjacent base stations, we first present a static offline ILP formulation of the migration minimization problem. For this simple case, we then propose two heuristics inspired by the greedy algorithm for the weighted set cover problem as polynomial approximations.

Introduction

Fog Computing is a new promising paradigm where computational resources are distributed closer to user premises and near the points of presence. Fog nodes are sometimes referred to as cloudlets, micro data centers, microclouds or they can as well reside in eNodeB base stations nodes in architectures we call by FogRAN or Fog enabled cellular networks.

This new distributed paradigm brings a number of advantages: low application latency, network traffic distribution, since processing takes place at the network edge in different locations by the Fog nodes, network traffic distribution increasing availability, reduced bandwidth cost etc. [START_REF] Taleb | Follow me cloud: interworking federated clouds and distributed mobile networks[END_REF] However, there are challenges that Fog computing needs to deal with. One challenge is service continuity for a user who moves in a Fog computing infrastructure. This user can be a connected car, drones, flying taxis etc.

In order to deal with service continuity, a service needs to migrate among these Fog nodes so that the user can stay closer to the Fog node from which it can be served better. However there is cost implied by the migrations.

First, we have a migration cost which is incurred when the service is moved from the previously serving node to the one serving the new user location [START_REF] Li | Service migration in fog computing enabled cellular networks to support real-time vehicular communications[END_REF][START_REF] Rejiba | A survey on mobility-induced service migration in the fog, edge, and related computing paradigms[END_REF][START_REF] Taleb | Follow me cloud: interworking federated clouds and distributed mobile networks[END_REF]. Factors that affect the migration cost are the service size, the cost to initiate and release a service and the bandwidth consumed to migrate the service. 1 Second, the transmission cost which increases, when the user is moving far away from the original server which hosts the service, no service migration is triggered, and so the service is accessed from the original service node via the backhaul network, instead of one-hop link.

In our paper, we are focusing on the migration cost. Intuitively, the more migrations are triggered, the bigger the migration cost is. In this work we look into ways to reduce this cost by studying how to minimize the number of VM migrations triggered. We take a user-centric approach where we focus on data objects (user sessions and related service data) that need to be migrated between Fog nodes. We do not concern ourselves with the technical details implementing the data objects, or whether the service is implemented using VMs, containers or similar.

Contributions

It is not our concern whether the VM or container must be entirely migrated, or whether a VM or container is running for one or many users.

Base stations are connected to a number of Fog nodes which process the service requests. We do not consider base stations being Fog processing nodes, even though they may also provide services relevant to maintain the Fog running, such as working with handover events to trigger service migrations. Base stations also use their networking data to decide which Fog node to route their traffic to (or, more appropriately, decide where a data object should be spawned or migrated depending on its SLA). On the other hand, Fog nodes can be heterogeneous and have a different OS, computing capacity, number of servers. VMs, hardware etc.

In our model a car is connected using the cellular network to a number of base stations. Base stations maintain a list of candidates Fog nodes with allowed thresholds for SLA. Whenever a car moves to another base station, the data object may be migrated to another Fog node satisfying the SLA and minimizing the overall cost of service (Fog migrations, bandwidth, etc). Instead of deciding of the appropriate Fog node to migrate to when a handover happens, the Fog controller computes the optimal set in advance when the itinerary is shared.

Given a set of candidate locations for fog clouds, we study the problem of obtaining the optimal set of the fog nodes. The optimality criterion is a linear combination of the cost of infrastructure and the number of migrations. The cost of infrastructure increases with the number fog nodes. On the other hand, one would expect the number of migrations to decrease with more fog nodes. Therefore, there is trade-off between these two quantities which need to be balanced to get the optimal solution.

We shall assume that the statistics on the number of cars going from the coverage range of one base station to another is given. These statistics will be used to compute the total number of migrations.

While we present the problem for a scenario in which cars can travel along any path in the network, we shall present results for special case in which cars travel only one hop between coverage range of one base station to another. The traffic statistics can be represented by a traffic matrix whose (i, j)th entry is the traffic going from the coverage range of base station i to that of base station j.

Organization

This rest of the paper is organized as follows. In Section 2, we describe the general model, give some details on the well-known weighted set cover problem, and present an interger linear program (ILP) formulation of the problem. In Section 3, we present a heuristic to compute a feasible solution to this ILP. This heuristic is based on the greedy algorithm for the weighted set cover problem. In Section 4, we evaluate the performance of the heuristic and compare it with the standard greedy algorithms for the set cover and weighted set cover problems. Finally, we end the paper with conclusions and future work in Section 6

System Model

We are given as input a set F of potential fog nodes as well as a set B of base stations. Base station i ∈ B can route the traffic from a user to a subset of candidates fog nodes F i ⊂ F which can host the service with respect to a allowed SLA. A fog node j ∈ F i is said to cover base station i when fog node j respects the SLA requirements of the user. In this, we say there is a link between fog node j and base station i. Here, we are assuming that all the users have the same SLA requirement.

The base stations and fog nodes can be represented by a bipartite graph G = (B ∪ D, E), where an edge between base station i and fog node j is in E if and only if j can guarantee the SLA requirement of users in the coverage range of i.

When the user changes position and moves out of the coverage range of base station i and in to the coverage range of base station k where the F k and F i do not have any fog nodes in common, a service migration is triggered. That means the user session is migrated from a fog node in F i to a node in F k with F i ∩ F k = ∅. In another words, if {i, k} / ∈ F i a service migration is triggered. Let us define a path in the road network by a set of ordered base stations. We shall assume we are given as input the traffic statistics of how many users move along each path.

As an example, consider the a network with four base stations {A, B, C, D} and three fog nodes 1, 2, 3.

Here F A = {1}, F B = {1, 2}, F C = {2, 3} and F D = {3}.
There are only two subsets of F that can cover B: {1, 3} and {1, 2, 3}. Suppose there is only one path {A, B, C, D} in the network with 100 users taking this path. Then, the number of migrations for {1, 3} is 100 (one for each user migrating from fog node 1 to 3 when the user moves from base station B to base station C) whereas for {1, 2, 3} this number is again 100 (assuming 2 is not used) or 200 (if we assume that A is connected to 1, B and C are connected to 2 and D is connected to 3). Assuming the infrastructure cost is linear in the number of fog nodes, then it is optimal in this case to operate fog nodes 1 and 3 only. Now, suppose that in addition to the previous users there are 500 users that take the path {B, C} only. Now, the number of migrations for {1, 3} is 600 whereas for {1, 2, 3} it is 100 × 1 + 500 × 0 = 100 (this is because the users on the path {B, C} will be connected to fog node 2 and hence will not require any migrations). It might be more profitable in this case to operate the set {1, 2, 3}. This will depend upon the cost of infrastructure.

The decision that we want to make is to find a set F ∈ F which minimizes a linear combinations of the number of migrations and the cost of infrastructure with the constraint that all the base stations in B are covered. This decision problem can be seen an instance of the Weighted Set Cover Problem [START_REF] Vazirani | Approximation Algorithms[END_REF], which we describe next.

Weighted Set Cover Problem

The Weighted Set Cover Problem is a known problem in the area of combinatorial optimisation which is NPcomplete. It is a generalization of the Set Cover problem which is specified by a set of elements {1, 2, ..., n} called the universe and a collection S of m sets whose union equals the universe. The Set Cover problem is to identify the smallest sub-collection of S whose union equals the universe. This problem has many practical applications, e.g airline scheduling, vehicle routing, facility location. No polynomial time exact algorithm exists, so a greedy approach can be used as an approximation algorithm. In the greedy strategy, we will iteratively pick the biggest subset that contains the most number of uncovered elements.

In the weighted version of the Set Cover problem a cost function is associated to each subset. The objective is to find the subset that has the least total cost. Problem 2.1 (Weighted Set Cover) Given a universe U of n elements, a collection of subsets of U , S = S 1 , . . . , S k , and a cost function c : S → R + , find a minimum cost sub-collection of S that covers all elements of U . [START_REF] Vazirani | Approximation Algorithms[END_REF] In the greedy strategy for the weighted version, instead of picking the subset that adds the subset that has the most number of new elements, we iteratively pick the subset with the smallest c(S)

|S\C| . The greedy weighted set covering heuristic does the following [START_REF] Vazirani | Approximation Algorithms[END_REF]:

Pair-wise vehicle mobility

In this section, we formulate the minimum number of VM migration problem for a pair-wise mobility model into an ILP problem. By pair-wise mobility model, we mean that the origin and the destination base stations are neighbors and the paths are direct routes from the origin to the destination. In the example in Figure 2, the pair-wise mobility model will have traffic going between only pairs of base stations, that is routes will be {A, B}, {A, C}, {A, D}, {B, A}, {B, C}, {B, D} and so on. As mentioned in the Introduction, in this paper we will only focus on the pair-wise mobility model and will not be investigating the general mobility model.

Assume we are a given a traffic mobility pattern between various base stations. This pattern is summarized in a matrix, W , whose (i, j)th element, W i,j represents the number of vehicles that move from base station i to base station j per unit time. We shall call W the mobility matrix.

We are also given a connectivity matrix C whose (i, j)th element, c i,j , is 1 if data center j meets the SLA for traffic from base station i, and 0 otherwise.

We wish to determine the set of fog nodes to which each base station should send its data traffic to. Implicitly, this determines which fog node sites within the set F should be operational. The choice of operating or not a fog node is influenced by two conflicting costs. First, there is a cost of operating a fog node which includes the infrastructure as well as the maintenance costs. Thus, larger the number of fog nodes selected by one of more base stations, larger is this cost. The other cost is for service migration. When a vehicles moves out of the range of base station i and into the range of base station j, in order to maintain the continuity of its services, its data has to be migrated from a data center selected by one selected by j. This migration cost can be avoided if both i and j have a data center in common. There is a clear conflict between the migration and the operating costs: to reduce migrations it is better to open more data centers which increases the operating costs.

Let x k ∈ {0, 1} be a binary variable that indicates if fog node k is operational or not. It can be shown that the number of service migrations per unit time due to vehicles moving between i and j is given by

m i,j (x) = w i,j z i,j (1)
where

y i,k = c i,k x k , (2)
z i,j = 1 if y i • y j > 0, 0 otherwise (3)
Here z i,j indicates whether i and j have a node in common in the set of operational fog nodes indicated by x. Note that m i,j does not depend upon how many fog nodes are in common between i and j as long as there is at least 1.

The optimization problem is formulated as the following Integer Program:

minimize x g(x) + β i,j m i,j (x) (4)
s.t. x ∈ {0, 1} |D| , y i,k = c i,k x k , ∀k ∈ D, (5)
k y i,k ≥ 1, ∀i. (6)
The function g is the operational cost and could potentially depend upon which fog nodes are open. In the simplest non-trivial case, g(x) = k x k , i.e. a linear cost of operating a fog node.

Heuristic Algorithm

In our problem, the subsets in the weighted set cover problem are the individual fog nodes. It is not easy to assign a weight or a cost function to each node since this will depend upon the other nodes in the solution. We modify the weighted set cover by using two heuristics cost functions: (i) an inverse cost function, and (ii) a cost function that depends only on the additional migrations.

Weights / Cost function

We have calculated the weights through a weight function that counts that sum of incoming traffic to each of base stations in a subset. Given W the mobility matrix, for a subset S, j∈S i→j W i . Our model wants to favor higher weights. Since the weighted set cover algorithm minimizes the weight we are taking the inverse of the weights.

Modified weighted set cover

For j ∈ F, denote B d , the set of base stations covered by j. With slight abuse of notation we will replace j by a subset of F in which case B A will be the set of base stations covered by the subset A. Also, for A ⊂ F , A c will be denote the complement inside F, that is, the set F \ A.

For a A ⊂ D define:

γ A (k) = (i,j) / ∈B k \B A m i,j |B k \ B A | , ∀k / ∈ A. ( 7
)
The ratio γ A (k) can be interpreted as additional migrations per base station that will be covered if k is added to A. A higher value of γ, indicates that this fog node eliminates the need for a larger number of migrations and that it has a lower marginal cost.

Algorithm 2: Modified weighted set cover

1 Output: A 2 C ← ∅ 3 A ← ∅ 4 while C = B do 5 k = arg min k∈A c γ A c (k) 6 C ← C ∪ B k 7 A ∪ k

Performance Evaluation

In this section we describe the results obtained from three different heuristics: a plain set cover implementation, a weighted set cover implementation where weights represent the inverse of inbound traffic on each fog node and a modified version weighted set cover which does not start with explicit weights but computes them greedily. We also show the solution to ILP which was computed using Gurobi [START_REF]Gurobi optimizer reference manual[END_REF] which is a solver for optimization problems.

In the first example, we show how the solution of the different heuristics varies with β which is the weight if the migrations. For Figure 3 we took B = 10 and F = 5. Thus C is a 10 × 5 matrix and W is a 10 × 10 matrix. The number of cars was between 0 and 100 in the mobility matrix W .

When β is close to 0, the ILP is like a set cover problem as the cost of migrations is not taken into account in the optimization. For larger values of β, the migrations become important and the greedy algorithm for set cover becomes worse.

In the second set of experiments we increase the number of base stations and fog nodes. We take different pairs of (B, F) with maximum B = 50 and maximum F = 15. The traffic matrix has random entries between 0 and 20, and 100 different random matrices were generated. For β = 0.01, the average total cost is shown in Fig. 4 and the average execution time is shown in Fig. 5. The results show while ILP finds solution with lower cost, it is also the slowest to execute.

For β = 0.001, the results are shown in Fig. 6 and7. Again for smaller values of β, the heuristics are close to ILP but with a smaller execution time than ILP.

Finally, in Fig. 8 and 9 we plot the results for maximum B = 60 and maximum F = 20. The traffic matrix has random entries between 0 and 20, and 100 different random matrices were generated, and β = 0.001

State-of-the art

A great amount of state-of-the art literature on mobility induced service migrations is covered by the recent study [START_REF] Rejiba | A survey on mobility-induced service migration in the fog, edge, and related computing paradigms[END_REF]. The authors present recent advances where service migration has been studied on divers paradigms as cloudlets, Fog computing, cloud-based vehicular networks and multi-access edge computing.

There are different types of service migration discussed in the literature, including the migration of virtual machines (VMs), containers or processes, or of programs using an operating system and hardware architecture agnostic binary format such as WebAssembly [START_REF]Web Assembly[END_REF].

We can also mention that [START_REF] Agarwal | Volley: Automated data placement for geo-distributed cloud services[END_REF] discuss Volley, an automatic service placement for geographically distributed DCs based on iterative optimization algorithms. Volley migrates services to new DCs if the capacity of a Service migrations in Fog Computing infrastructure borrows ideas and combines techniques used in handovers in cellular networks and live migration in Cloud computing. A reader can refer to survey [START_REF] Wang | A survey on service migration in mobile edge computing[END_REF] where the authors compare these two concepts with service migration in MEC as well their different scopes and similarities.

Many publications on service migration refer to the works on "Follow me" approaches [START_REF] Taleb | Follow me cloud: interworking federated clouds and distributed mobile networks[END_REF][12][9][3] [START_REF] Taleb | An analytical model for follow me cloud[END_REF].

In [START_REF] Li | Service migration in fog computing enabled cellular networks to support real-time vehicular communications[END_REF] authors propose a quality-of-service aware scheme based on the existing handover procedures to support the real-time vehicular services. A case study based on a realistic vehicle mobility pattern for Luxembourg scenario is carried out, where the proposed scheme, as well as the benchmarks, are compared by analyzing latency and reliability as well as migration cost.

More theoretical results are given in [START_REF] Taleb | An analytical model for follow me cloud[END_REF], [START_REF] Urgaonkar | Dynamic service migration and workload scheduling in edge-clouds[END_REF]. In the first study, the authors use Markov Decision Processes to capture the tradeoff between migration cost and user experience. In the second study, the authors focus on the similar problem. They model this tradeoff due to service migration's network overhead and latency for the use. Since service migration affect workload scheduling they tackle this decision jointly. Instead of using dynamic programming to solve MDPs, they decouple the MDPs and apply the technique of Lyapunov optimization of control theory. Another theoretical work is [START_REF] Gonçalves | Proactive virtual machine migration in fog environments[END_REF], where authors as well propose a VM migration approach based on mobility prediction. The authors provide an ILP model for VM placement in Fog computing. The problem they are dealing with is different from ours. Their algorithm defines the set of candidate cloudlets to receive the users VM according to the users future position. In their model they want to maximize the accepted requests while minimizing the user's latency. They execute these two objective functions sequentially.

We finally mention tools such as described in [START_REF] Márcio | Myifogsim: A simulator for virtual machine migration in fog computing[END_REF], which is an extension of the iFogSim simulator [START_REF] Gupta | ifogsim: A toolkit for modeling and simulation of resource management techniques in internet of things, edge and fog computing environments[END_REF] adding virtual machine migration policies for mobile users. Their VM migration policy takes into account user's position, speed and direction. As well they define, the point where the migration can be potentially triggered by specifying the geographical zone based on user's coordinates. FogNetSim has been proposed in [START_REF] Qayyum | Fognetsim++: A toolkit for modeling and simulation of distributed fog environment[END_REF]. FogNetSim is an extension of OMNET++ that is used to simulate a network. The tool simulates among others geographically distributed data centers while providing support for handovers among Fog nodes. The implementation includes a number of mobility models. It is a release of 2018 and as future work authors

Conclusions and Future Work

We presented an Integer Linear Program for obtaining the optimal location of fog nodes that minimizes a linear combination of the number of migrations and the cost of infrastructure. This was done for a pairwise mobility model in which the origin and destination base stations are neighbors. We gave two heuristics based on the Weighted Set Cover problem and evaluated the performance of these heuristics with that of the optimal solution.

The research community will benefit from an optimization framework for service migrations taking mobility patterns in consideration.

As future work, we will investigate the general mobility model. For this, other heuristics will have to be proposed and we will study the approximation ratio of these.

Figure 1 :

 1 Figure 1: Service Migration based on statistics gathered on base stations

Figure 2 :

 2 Figure 2: Example bipartite graph

Algorithm 1 : 4 C ← C ∪ S 5

 145 Greedy Weighted Set Cover algorithm 1 C ← ∅ 2 while C = U do 3 Pick S with the smallest c(S) |S\C| Output the picked sets.

Figure 3 :

 3 Figure 3: Cost as a function of β for Set Cover (SC), Weighted Set Cover (WSC), Modified Weighted Set Cover (MWSC) and the ILP formulation.

Figure 4 :Figure 5 :

 45 Figure 4: Comparison of the Set Cover (SC), Weighted Set Cover (WSC), Modified Weighted Set Cover (MWSC) and the ILP formulation. Each algorithm was executed 100 times on each configuration

Figure 6 :Figure 7 :

 67 Figure 6: Comparison of the Set Cover (SC), Weighted Set Cover (WSC), Modified Weighted Set Cover (MWSC) and the ILP formulation. Each algorithm was executed 100 times on each configuration

Figure 8 :Figure 9 :

 89 Figure 8: Comparison of the Set Cover (SC), Weighted Set Cover (WSC), Modified Weighted Set Cover (MWSC) and the ILP formulation. Each algorithm was executed 100 times on each configuration

Table 1 :

 1 Variables used in the ILP formulation Notation Description

	W	mobility matrix
	C	connectivity matrix
	x k	A binary variable indicating whether tfog node k is opera-
		tional or not
	z ij	A binary variable indicating whether i and j have a fog
		node in common
	w ij	variable in the mobility matrix, represents number of
		vehicles moving from base station i to base station j per
		unit time
	m ij	Number of service migration per unit time
	c ij	binary variable in the connectivity matrix, if 1 it means the
		j fog node meets the SLA for service coming from i
	g(x)	operational cost which depends upon which fog nodes are
		open.

Acknowledgment

We gratefully acknowledge the funding received from Continental Digital Services France.


Convergent Synthesis of 2-Oxazolone-4-carboxylates Esters by Reaction of Aldehydes with Ambivalent N-Cbz-α-Tosylglycinate Ester

Masahiro Abe, a Baptiste Picard, a Michaël De Paolis a, * a Normandie Univ, UNIROUEN, COBRA, INSA Rouen, CNRS, COBRA, 76000 Rouen, France. michael.depaolis@univ-rouen.fr, Supporting Information Placeholder ABSTRACT: N-Cbz-α-tosylglycinate ester was combined with aldehydes in a redox-neutral sequence leading to 2-oxazolone-4carboxylates with high functional groups tolerance. While the scope of the method was delineated to primary and secondary aliphatic aldehydes as well as aromatics, no racemization occurred with chiral aldehydes such as Garner's. Hitherto unknown, this process relies on the ambivalent role of N-Cbz-α-tosylglycinate ester acting as pronucleophile.

Combining nitrogen and oxygen in a 5-membered aromatic ring, 2-(3H)oxazolones (2-oxo-2,3-dihydrooxazoles) are pertinent molecules in the fields of medicinal chemistry and agrochemistry, 1 as illustrated with I and II (Scheme 1A) with respectively antibacterial 1a and herbicidal activities. 1b,2 As planar and aromatic derivatives of amino acids such as serine and threonine, electron-poor 2-(3H)oxazolone-4-carboxylates esters have much promise in the aforementioned fields (Scheme 1B). However, the known strategy toward 5substituted-2-(3H)oxazolone-4-carboxylates requires two limiting steps. Scheme 1.

First, α-ketoesters are oxidized into α-nosyloxy or α-bromoβ-ketoesters, then the nitrogen nucleus is introduced with methyl carbamate by nucleophilic addition in harsh conditions, upon activation with p-toluenesulfonic acid or silver triflate, in refluxing toluene. 3 Within this strategy, alternative routes were described by combining either α-amino-β-ketoesters with triphosgene 1b or α-diazo-β-ketoesters with methyl carbamate. 1c Beside the limited functional group tolerance displayed by these methods, the assemblage and/or oxidation of the acyclic compounds remain impediments to broader molecular diversity. At the inception of this study was an attempt to promote the Mannich coupling between dihydrocinamaldehyde 1a and N-Cbz-α-tosylglycinate ester 2 which inadvertently led to 2-(3H)oxazolone 3a in 25% yield (Eq. 1).

Simply promoted by nBu 4 NF, the redox-neutral and convergent domino sequence gave 5-alkyl and 5-aryl-2-(3H)oxazolone-4-carboxylates from 2 and functionalized, aliphatic and aromatic, aldehydes (Scheme 1C). The role of 2 in this sequence was puzzling, reacting usually as a proelectrophile. 4,[START_REF]Review on α-amido sulfones: Petrini[END_REF] Interestingly, this study illustrates the ambivalent reactivity of 2 as a pronucleophile.

Scheme 2. Scope of the method

From the initial experiment (Eq.1), we set out to diminish the amount of 4 6 and, to that end, the temperature of reaction was decreased (SI contains the detailed optimization). Pleasingly, operating at -60°C gave 3a in 65% yield by reacting 1a (1.5 equiv.) with 2 (1 equiv.) in the presence of nBu 4 NF (2.5 equiv.). This result was improved by conducting the experiment with molecular sieves (4Å) and nBu 4 NF (3 equiv.), yielding 3a in 74% (Scheme 2). Switch to a less polar solvent (toluene) or modulating the ratio 1a/2 negatively or only marginally affected the efficiency of the sequence. As for the promotor, instead of nBu 4 NF, a stronger base such as LiHMDS caused the decomposition of the reagents, whereas tetrabutylammonium difluorotriphenylsilicate (TBAT) left the starting materials unchanged. [START_REF] Khmds | The conversion of 2 was total and compound 4 was the major product of the reaction. 9 Cinnamaldehyde, trans-2-bromo-3-(2-nitrophenyl)acryl aldehyde and 2-nitrobenzaldehyde were found unreactive, as well as PhCOCF 3[END_REF] With a protocol in hand, we examined the scope of the method starting with primary aldehydes such as nonaldehyde and phenylacetaldehyde which were converted into 3b (64%) and 3c (54%). For the latter, it is noteworthy that the acidity of the aldehyde only moderately impacted the efficiency of the cou-pling compared to dihydrocinnamaldehyde (74% vs 54% yield). Further, oxazolone 3d featuring an acid-sensitive acetal functional group was prepared in 61% yield from the monoprotected glutaraldehyde derivative. Since no oxidant is required to form the heterocycle, electron-rich functional groups are compatible as demonstrated with the preparation of 3e (46%) from (S)-citronellal, containing a prenyl appendage. While 4-pentynal was found less compatible, the corresponding oxazolone 3f was isolated in 21% yield, 8 electron-rich alkynylaryls such as 5-(p-tolyl)pent-4-ynal and the alkynylindole were efficiently combined with 2 into 3g (82%) and 3h (81%). In spite of the higher steric hindrance of secondary aldehydes, they still reacted with 2 as demonstrated with isopropyl and cyclopropyl substituted 2-(3H)oxazolones 3i (47%) and 3j (30%). The more functionalized N-Boc-4piperidinecarboxaldehyde was converted into 3h in 44% yield, an alkaloid of pharmaceutical pertinence. 1c A limit was reached with tertiary aldehyde, as pivalaldehyde was found unreactive and, instead of the heterocycle, the sole production of 4 was noted. On the other hand, aromatic aldehydes reacted well with 2 as observed with benzaldehyde and 4cyanobenzaldehyde giving 3i (42%) and 3j (58%). 9 Interestingly, since the motif is easily hydrolyzed in acidic conditions, α-carboxaldehyde-α'-methoxy-γ-pyrone 10 was efficiently combined with 2 into 3n (62%), a heterocycle sharing structure similarity with phenoxan, a natural product with anti-HIV and fungicide properties. 11 Moreover, a basic aromatic ring such as pyridine was smoothly combined with 2 into 3o (65%). However, hindered and electronically-rich pyridines were less reactive and 3p was assembled in 13% yield from 2 and the corresponding aldehyde. 8 Eventually, α-chiral aldehydes were examined to assess the risk of racemization induced by the conditions of reaction. To that end, Garner's aldehyde was selected due to its tendency to racemize in presence of base. Pleasingly, 2-(3H)oxazolone 3q was isolated without racemization (er = 99:1) in 22% yield after exposure of Garner's aldehyde to 2 in the standard conditions. 8 Although low, the unoptimized yield remains synthetically useful and reflects the challenge of forming C-C bonds from sterically hindered reagents. A less hindered chiral aldehyde, deriving from the Roche's ester, was more easily combined with 2 since 2-(3H)oxazolone 3r was isolated in 37% yield. Incidentally, the bulky tButyldiphenylsilyl protecting group (TBDPS) was not removed in these conditions thus proving its compatibility with the method.

To gain an insight into the mechanism, 1a was exposed to nBu 4 NF in the absence of 2 (Scheme 3, Eq. 2), which led to enal 5 resulting from the self-aldolization/crotonisation process. Since the α-hydroxyketone 6 was not observed, an umpolung mechanism in which 1a would act as nucleophile was thus ruled out. Moreover, exposure of 2 to these conditions (Eq. 3) led to 4 (44% yield, 55% conversion) demonstrating the ambivalent reactivity of 2. To examine the possibility of a radical mechanism, we performed the coupling of 1a with 2 (Eq. 4) in the presence of nBu 4 NF (3 equiv.) and of 2,2,6,6tetramethyl-1-piperidinyloxy (TEMPO, 3 equiv.), a scavenger of radical species. Since the outcome was not significantly impacted (65% vs 56% yield in 3a), we surmised that an anionic mechanism was likely.

Scheme 3. Mechanistic perspective

Accordingly, 2 would act a nucleophile after carbon deprotonation into 2', a process in competition with the usual nitrogen deprotonation of 2 leading to imine 7 (Scheme 4). As observed in the presence of tertiary aldehyde, the coupling between and 7 becomes the major pathway (path A) leading to 4 via the Mannich adduct III. In the cases of primary and secondary aldehydes (path B), an aldolization occurs with 2' forming the alcoholate IV, which after p-tolylsulfinate elimination and intramolecular addition of the alcoholate to the carbonyl of the Cbz group would give 2-(5H)oxazolone V. Subsequent isomerization of V would follow, ultimately affording 2-(3H)oxazolone 3. The success of the whole sequence probably relies on the addition of the alcoholate to the carbamate shifting the series of equilibrium to V, this step being facilitated by the non-coordinating nature of the quaternary ammonium. [START_REF]best results in the series of bases was not investigated, but combined effects may explain the superiority of the promotor. Hence, while mild basicity of the reagent is important, the reactivity of anionic species such as 2' and alcoholate IV is also enhanced by non-coordinating organic cations such as nBu 4 N + . 13 Other pronucleophiles with modulations of the substituents were tested without success[END_REF] The fact that the process failed when the Cbz group of 2 was replaced by the more hindered Boc group gives credit to this assumption. 13 As an illustration of the competition between the paths A and B, a small amount of 4 was observed when primary aldehydes were reacted while the production of 4 was significant with secondary aldehydes and predominate when a tertiary aldehyde was engaged.

Scheme 4. Postulated mechanism

Simpler and advanced synthetic processes are urgently and continuously sought for and, in this context, a convergent synthesis of various 5-alkyl and 5-aryl-2-(3H)oxazolone-4carboxylates was developed. Within the competition between C-or N-deprotonation of 2 with nBu 4 NF, the unprecedented sequence begins with the aldolization reaction of 2' which, despite being sterically hindered, reacted with a good variety of aldehydes, the main limitation of the method being the steric hindrance of the electrophile. Since no oxidation step or acidic conditions are needed, aldehydes with electron-rich, acid-sensitive or pyridinyl appendages were successfully converted into 2-(3H)oxazolones from 2, which can be prepared in large scale and in one step. Furthermore, because 2-(3H)oxazolones are known intermediates en route to oxazoles [START_REF] Vintonyak | [END_REF] or oxazolidinones, 3a this method may have a bearing on the synthesis of these motifs.

ASSOCIATED CONTENT Supporting Information

The Supporting Information is available free of charge on the ACS Publications website. General procedure and characterizations of each compounds, as well as optimization of the procedure, variations of the reagents and copies of 1 H, 13 C NMR spectra and HPLC, GC traces. FAIR Data is available as Supporting Information for Publication and includes the primary NMR FID files for compounds 3a-r and 4b.

ACKNOWLEDGMENT

We are very grateful to Drs. Julien Legros and Jacques Maddaluno (Normandie University) for helpful discussions and to the Fondation des Substances Naturelles for a fellowship to M.A. We acknowledge the financial support from ISCE-CHEM (Interreg IV, European Program), Interreg FCE LabFact (European Program and co-funded by ERDF) and Labex SynOrg (ANR-11-LABX-0029).

AUTHOR INFORMATION

Corresponding Author * Michael.depaolis@univ-rouen.fr Authors Masahiro Abecurrent address, School of Pharmacy and Pharmaceutical Sciences, Mukogawa Women's University, 11-68, 9-Bancho, Koshien, Nishinomiya, Hyogo 663-8179, Japan Baptiste Picard -Normandie Univ, UNIROUEN, COBRA, INSA Rouen, CNRS, COBRA, 76000 Rouen, France