Adam Quotb

Evelio E Ramírez-Miquet

Clément Tronche

Julien Perchoux

Optical Feedback Interferometry sensor for flow characterization inside ex-vivo vessel

Pressure myograph systems allow the study of pharmacological effects of drugs and other vasoactive compounds on small isolated vessels by image processing. In this work, we present a new pressure myograph system based on Optical Feedback Interferometry (OFI) sensor that gives information about local velocity in fluids and enables reconstruction of a velocity profile inside a vessel.

OFI is a self-aligned interferometric technique that uses the laser as both the light source and the receiver thus offering high sensitivity, fast response, and a simple and compact optical design. The local Doppler flow velocity is directly measured inside ex-vivo rat vessel with a step of 100 µm thus avoiding the need to use complex image processing and models based profile calculation for extracting flow velocity. This technique will be useful to investigate hemodynamics in microcirculation by measuring unsteady irregular blood.

I. INTRODUCTION

The need to accurately measure physiological functions and properties of small arteries, veins and other vessels is well established [START_REF] Kamishima | Small Vessel Myography[END_REF]. Vascular smooth muscle cells, located inside vessel wall play a key role in contraction and relaxation of arteries [START_REF] Lu | Assessment of endothelial function of large, medium, and small vessels: a unified myograph[END_REF].

These vasoconstriction and conversely vasodilatation effects are driven, in normal conditions by the central nervous system or, in case of disease, by vasodilative or vasocontrictive drugs. In the perspective of vessel characterization, two kind of measure systems exist:

• The isometric method, which measures changes in force from dissected resistance arteries while the length (diameter) remains constant.

• The isobaric method, which measures changes in diameter while transmural pressure across the artery wall is kept constant. This paper will be focused on isobaric or pressure myograph systems. On these sensors, a single vessel is isolated on two glass cannulas, pressurized and flushed by a liquid to simulate blood flow [START_REF] Clifford | IemphSpatial Distribution and Mechanical Function of Elastin in Resistance Arteries: A Role in Bearing Longitudinal Stress[END_REF]. Then, the artery is imaged on a video monitor and diameter is assessed by contrast detection of the arterial wall in the dimension analyzer. Investigation on myogenic response, vasodilatative effect and endothelium behavior can be done with this kind of system [START_REF] Mccarron | Myogenic contraction by modulation of voltage-dependent calcium currents in isolated rat cerebral arteries[END_REF].

In our sensor, the vessel cannulation set up is inspired from myograph systems but instead of using high resolution camera and microscope sensors, OFI is employed.

In the OFI process, the light emitted from a laser source is backscattered from a moving target and re-enters in the laser cavity. This optical feedback produces a modulation of the optical output power. At the micro scale, the maximum Doppler frequency of the interferometric signal and the relative flow velocity are correlated [START_REF] Campagnolo | Flow profile measurement in microchannel using the optical feedback interferometry sensing technique[END_REF].

For biomedical sensing, OFI sensors are ideally suited for measurements of blood flow: local flow in rat brain [START_REF] Figueiras | Selfmixing microprobe for monitoring microvascular perfusion in rat brain[END_REF] or extra corporal circulation ( [START_REF] Donati | Norgia Self-Mixing Interferometry for Biomedical Signals Sensing, Selected Topics in Quantum Electronics[END_REF], [START_REF] Pesatori | Self-Mixing Laser Doppler Spectra of Extracorporeal Blood Flow: A Theoretical and Experimental Study[END_REF]). By moving the sensor across a microfluidic channel, Campagnolo et al. ( [START_REF] Campagnolo | Flow profile measurement in microchannel using the optical feedback interferometry sensing technique[END_REF]) provide a system able to measure parabolic profile of velocity inside a capillarity tube.

This study proposes a new sensor for myograph systems able to measure local flow velocity with a 100 µm step and, by scanning a whole vessel section, a flow profile is extracted. Internal vessel diameter is estimated from the profile base width and a 2D vessel velocity image is computed.

II. MATERIALS AND METHODS

A. OFI theory

The more generalized sensing method used in laser diodes is the measurement of the optical power changes in the photodiode (PD) due to optical feedback induced by scattering targets. The relation of the emission power with target velocity is given by the formula: where P 0 is the optical power of the laser without feedback, L is the distance between the target and the laser, c is the speed of light, t is time and V T is the target velocity.

P T = P 0 [1 + cos(2π 2(L + V T t) c )] (1)
OFI sensors are well suited as alternative optofluidic systems as long as there is a minimal concentration of particles embedded in the fluid acting as scatters centers. OFI signals from fluid flow contain information on particles velocity in the fluid in a wide range. The power spectral density analysis of the Fast Fourier Transformation (FFT) of temporal signals allows the direct calculation of flow velocity, which is related to the fundamental Doppler frequency F Dopplermax in the spectrum as follows:

V T = λ * F Dopplermax 2 * η * cos(θ) . ( 2
)
where η is the refractive index of the liquid flushed, θ the angle between the laser and the flow direction and λ the laser wavelength.

B. Aorta preparation

From frozen Wistar rat, carotid aorta is extracted and cannulated on two glass cannulas. At both extremities, the aorta is held in place with two sutures (5-0 USP).

It is then pressurized and flushed by a liquid composed by a ratio of 10:1 of Phosphate Buffered Solution and milk. The speed flow and pressure are considered as constant during all the experiment because of the use of a high precision pressure pump (Fluigent MFCS-EZ-4C). The laser sensor is focalized on the center of the vessel where the Doppler frequency reaches its maximum (figure 1). • One plano-convex optical len (LA1951-B).

C. OFI Sensor signal recording

• A compact electronic system that realizes both laser driving and signal amplification functions. The prototype fits on a 5x5 cm PCB.

The amplified photodiode signal is digitized by a National Instruments card (NI USB 6251) connected by USB to a computer. For each measurement point 4096 samples are recorded at a frequency of 1MHz.

The optical setup consists on a laser diode (HITACHI HL7851G) emitting at 785 nm and driven by an injection current of 50 mA. The laser is coupled to a single lens of 25.4 mm focal length and the collimated radiation is pointed to the vessel with angle of 86°.

The 2D automatic scanning protocol is presented in figure 2.B. The scan mechanical system and laser's photodetector signal recording are synchronized using Labview VI. For one position, 10 succesively temporal signals are recorded and processed off-line using a Matlab script/code. The fundamental Doppler frequency provides the information necessary to calculate the local velocity according to equation 2, thus kinematic properties of the flow can be easily determinated.

Because of the size of a rat aorta is bewteen 500 µm and 1 mm, we have selected a scan step of 100 µm which is also analog to the resolution of the camera. For each position, the Fig. 3. Overview of the computational process, from OFI signal to 2D velocity mapping

D. OFI Sensor signal processing

In [START_REF] Campagnolo | Flow profile measurement in microchannel using the optical feedback interferometry sensing technique[END_REF], the signal processing consisted in the fitting of the OFI signal spectrum by a complex exponential function. This method, despite the excellent results obtained for the estimation of the fluid velocity, was requiring a rough calibration of several coefficients in the fitting function before running the fitting algorithm itself. Thus it was not possible to run the signal processing for the full scan in an automated way.

The signal processing approach have been changed and, by setting a threshold level in the electrical spectrum of the OFI signal, the maximum Doppler frequency is evaluated.

The signal processing block for one position is presented in figure 3. For each position, 10 FFTs of the photodiode signal are computed, averaged and smoothed. The maximum Doppler (F Dopplermax ) is extracted by spectrum thresholding and, according to equation 2, maximum velocity (V T ) is measured. Figure 4 shows an example of a 2D velocity mapping on a plastic tube (500 µm internal diameter), with a 10 µm scanning step on an area of 2 cm 2 .

III. RESULTS

A. Image processing diameter assessment

From the literature, internal Wistar rat carotid have been evaluating around 850 µm [START_REF] Lu | Assessment of endothelial function of large, medium, and small vessels: a unified myograph[END_REF]. Figure 5 shows a 220 x 182 pixels picture of the cannulated and prezurissed carotid aorta. One pixel correspond to 100 µm and internal diameter is evaluated by taking suture thread as reference. In that context, after an image processing, the internal diameter have been computed in between 800 µm and 900 µm.

B. OFI diameter assessment

1) Sensor calibration: For the first use, a calibration procedure has to be done prior to aorta extraction. Indeed, because of the optical setup, the laser beam position is unknown and has to be focus in the middle of the channel. In that perspective, a calibration scan is done on a well known diameter tube and fluid. The sensor is calibrated with a solution of milk (1%) and distilled water (99%) flushed inside a plastic tube at a constant velocity. Then, the beam is manually adjusted along the three axis and θ angle where the OFI signal reaches its highest frequency.

When the middle of the channel is found, a scan is performed and base velocity profile width is evaluated. Then the result is compared to the tube diameter in order to determine the threshold level. In this study, the threshold is set to 14 dB.

2) Aorta 2D imaging: Before scanning, the laser beam is focused on the centre of the aorta in the same way for the calibration procedure. Then it is moved towards the x axis through the scan start point. As soon as the fluid velocity is stabilized the complete 2D laser scan is performed on a surface of 3.75 mm 2 . In figure 5, the red rectangle represents the scan zone with a width of 2.5 mm (x axis) and a height of 1.5 mm (y axis). For each scan line (along x axis), an aorta OFI fluid velocity profile is computed from the maximum Doppler frequency extracted from spectra. Figure 6 presents results from one line scan where three points of interest have been highlighted (outside aorta (black), 300 µm (red) and 500 µm (purple) inside the aorta). FFT spectra of these points are shown in figure 6.A and fluid velocity profile in figure 6.B. On a first hand we can notice a difference between spectrum outside the aorta (black curve) and inside (red and purple curves). In a second hand, despite the fact that there are 200 µm between the two positions, maximum Doppler frequencies are well distinguish.

The fluid velocity profile (figure 6.B) is composed by 25 measurements points and from the base profile width, an aorta diameter of 850 µm is measured. Moreover, Poiseuille'law describes the fluid velocity profile inside a tube as parabolic [START_REF] Campagnolo | Flow profile measurement in microchannel using the optical feedback interferometry sensing technique[END_REF]. Even without any fitting, from the experimentally measured flow velocity profile plotted in figure 6.B, a parabolic shape is observed. The complete aorta scan and the comparison with the raw image is presented in figure 7. From the OFI sensor image, the aorta is clearly visible and the fluid velocity distribution can be analyzed. High speed flow (between 0.7 and 1 normalized speed) is observed on 300 µm in the middle of the aorta. Near The feasibility to use an OFI sensor for flow characterization inside ex-vivo rat aorta has been demonstrated. Two main informations are provided: internal vessel diameter is estimated from the profile base width and local velocity information is extracted from the correlation between OFI signal and position. Because OFI sensor is based on basic signal processing methods, electronics and optics, it differs from the well establish technology. In addition, with this sensor coupled to myograph systems, the investigation on hemodynamics in microcirculation by measuring unsteady irregular blood is now a reality for biomedical field and medicine.

In this study, a 100 µm scan step has been used. By accepting a compromise between precision and recording time, we will reduce this scan step to 10 µm in order to provide a high definition fluid velocity image. In that perspective, future works on OFI sensors will be focused on the mechanical displacement system. Indeed, the scanning protocol is time consuming: on 600 seconds dedicated to the scanning, only 2 % of the time is used for OFI signal acquisition and recording. The time remaining is consumed by the mechanical system. Due to this main drawback, new displacement systems based on mirrors or continuous scanning will be further developed in our future OFI sensors.

Fig. 1 .Fig. 2 .

 12 Fig. 1. OFI Sensor setup for internal rat aorta diameter assesment

Figure 2 .

 2 Figure 2.A shows an overview of OFI sensor used for this study. It is composed by three main parts: • XYZ displacement system. Three miniature motorized linear stages (Zaber-LSM 50A) move the laser with a resolution of 0.1905 µm and are controlled by computer.

Fig. 4 .

 4 Fig. 4. 2D velocity mapping on a fluidic device

Fig. 5 .

 5 Fig. 5. Cannulated rat aorta: Red rectangle corresponds to OFI scanned area

Fig. 6 .

 6 Fig. 6. One line scan on rat aorta by OFI: A) Three FFT spectra: outside the aorta (black), 300 µm (red) and 500 µm (purple) inside the aorta, B) Fluid velocity profile composed by 25 scan points

Fig. 7 .

 7 Fig. 7. Rat aorta imaging: A) 2D rat aorta fluid velocity imaging captured by OFI and B) Raw image of the scanning zone captured by camera

ACKNOWLEDGMENT This work has been supported by the National Polytechnic Institute of Toulouse (INPT) through the grant Bourse Nouveaux Entrants 2013 and the french embassy in Havana.


Donia El Kateb

Johann Bourcier

Yves Le Traon
email: yves.letraon@uni.lujohann.bourcier@inria.fr

Optimizing Multi-Objective Evolutionary Algorithms to enable Quality-Aware Software Provisioning

Keywords: MOEAs, Hyper-heuristics, Optimization, Cloud, Software Deployment

. Still though, their runtime efficiency limits the widespread adoption of such algorithms in cloud engines, and thus the consideration of quality criteria in clouds. Indeed MOEAs produce many dead-born solutions because of the Darwinian inspired natural selection, which results in a resources wastage. To tackle MOEAs efficiency issues, we apply a process similar to modern biology. We choose specific artificial mutations by anticipating the optimization effect on the solutions instead of relying on the randomness of natural selection. This paper introduces the Sputnik algorithm, which leverages the past history of actions to enhance optimization processes such as cloud elasticity engines. We integrate Sputnik in a cloud elasticity engine, dealing with performance and quality criteria, and demonstrate significant performance improvement, meeting the runtime requirements of cloud optimization.

I. INTRODUCTION

a) Software Deployment in the Cloud is a Multi-Objective Optimization Problem: Cloud Computing paradigm leverages hardware and software resources to offer hosting capabilities that enable customers to get rid of the burden of maintaining their own applications by paying fees that vary on the CPU power consumption per hour or storage usage instead of paying for software license. When hosting a software in the cloud, cloud providers aim at both achieving the quality of service requirements that are stated in the Service Level Agreements (SLA) [START_REF] Patel | Service level agreement in cloud computing[END_REF] and at reducing energy consumption. In several cases, these objectives are conflicting: An illustrating example is the one related to Virtual Machines (VMs) allocation: Cloud customers tend to isolate their workloads in separate VMs for security purposes while cloud providers aim at reducing the number of alive VMs to reduce energy consumption in the data-center. The resolution of these objectives has to be performed within acceptable time frame to cope with elasticity features such as resources dynamic autoscaling to meet users needs.

b) MOEAs for Cloud Multi-Objective Optimization Problems Resolution: In [START_REF] Harman | Cloud engineering is search based software engineering too[END_REF], the authors have motivated the use of Search Based approaches for the resolution of cloud engineering problems. Multi-Objective Evolutionary Algorithms (MOEAs) [START_REF] Deb | Multi-objective optimization using evolutionary algorithms[END_REF], [START_REF] Van Veldhuizen | Multiobjective evolutionary algorithms: Analyzing the state-of-the-art[END_REF] is a class of search based approaches that addresses problems in which a decision maker aims at finding a solution that optimizes several conflicting objectives. MOEAs simulate population evolution to produce solutions exhibiting trade-offs between conflicting objectives such as grid jobs scheduler [START_REF] Frey | Search-based genetic optimization for deployment and reconfiguration of software in the cloud[END_REF] as they are able to automate a set of configurations exploration [START_REF] Coello | Applications of multi-objective evolutionary algorithms[END_REF]. A cloud infrastructure, characterized by its dynamic entities, is a typical example of self-adaptive system. MOEAs offer generic and reusable domain exploration capabilities which make them suitable candidate for self-adaptive systems. Self-Adaptive systems require run-time corrective actions [START_REF] Kephart | The vision of autonomic computing[END_REF], that will be made after the identification/selection of the best fitted configuration. A cloud infrastructure can be abstracted by a set of software resources that run on top of Virtual Machines (VMs) dynamically starting/stopping in physical machines. MOEAs are thus used nowadays in several design case studies [START_REF] Frey | Search-based genetic optimization for deployment and reconfiguration of software in the cloud[END_REF], [START_REF] Kateb | Generic cloud platform multi-objective optimization leveraging models@ run[END_REF], such as self-adaptive cloud scheduling problems, to maintain conflicting quality characteristics [START_REF] Deb | Multi-objective optimization using evolutionary algorithms[END_REF], [START_REF] Van Veldhuizen | Multiobjective evolutionary algorithms: Analyzing the state-of-the-art[END_REF] such as system performance, cost and safety. Beyond their applicability for cloud optimizers, MOEAs offer the following advantages to set-up autonomous self-adaptive engines working "at runtime": (i) no need for predefined solutions, (ii) the incremental optimization process can be stopped on-demand, (iii) operating multi-objective optimization and finding trade-offs.

c) MOEAs Tuning is needed to make them appropriate for self-adaptive systems such as a cloud infrastructure: MOEAs are not the standard solution for designing a run-time adaptation engine. A major factor which threatens their adoption for self-adaptive systems such as a cloud infrastructure is the run-time resources consumption, which often requires ad-hoc empirical tuning of such algorithms to meet performance needs. Indeed, as in the Darwinian theory [START_REF] Darwin | On the origins of species by means of natural selection[END_REF], [START_REF] Reeves | Genetic algorithms: principles and perspectives: a guide to GA theory[END_REF], the evolution process of MOEAs relies on random mutations to ensure proper domain exploration. This randomness leads to suboptimal performance due to the creation of many dead-born evolution branches. Reed [START_REF] Coello | Applications of multi-objective evolutionary algorithms[END_REF] et al report that even if MOEAs usage simplifies the design of automatic configuration engines, empirical fine-tuning of evolutionary search parameters is still needed and can save 70% of computational costs. These results motivate the need for software engineering techniques to avoid MOEAs ad-hoc tuning and to provide reusable techniques and frameworks for run-time usage. d) Besides, modern genetics is evolving: Nowadays, modern genetics does not only rely on natural evolution process. Instead, based on the founding work of Muller et al [START_REF] Plaskett | Artificial transmutationof the gene[END_REF], artificial mutation is now widely used to save time and generation cycles for instance to produce genetically modified organisms. Instead of relying only on crossover and natural selection, Muller et al [START_REF] Plaskett | Artificial transmutationof the gene[END_REF] studied artificial mutation using X-Ray to modify a fruit with an anticipated intent. These principles have led the genetic field to build instruments for such selective artificial mutations: the evolution process is accelerated by selecting some specific mutations that contribute to enhance a certain objective. e) Our proposal to accelerate MOEAs: Going along the same line, we study how such principles could be adapted to MOEAs to accelerate the convergence by guiding the evolutionary algorithms through dynamically selected mutation operators. Our intuition is that operators applied in a smart and artificial way would provide better results than operators applied randomly, and in particular would reduce the number of useless solutions. Thus, the new algorithm we propose is no longer inspired by Darwinian evolution, but by "artificial mutation", based on a smart and dynamic selection of the best mutation operator to apply at a given step. By applying such operators in priority, we aim at orienting the evolution process of a given population in the right direction for the problem to solve.

In this paper, we present an hyper-heuristic [START_REF] Burke | A classification of hyper-heuristic approaches[END_REF], called Sputnik, inspired by artificial mutation. Our algorithm takes its name from a virus family which evolves and mutates together with their host in order to perfectly fit their environment and to replicate more quickly. In the same manner, Sputnik algorithm leverages a continuous ranking of operators according to their impact on fitness functions to smartly select dynamically the most relevant mutation operator as the search evolves.

We focus on performance as a key factor for run-time usage to reach faster acceptable trade-offs while saving computation time and generation cycles. For instance, the acceleration Sputnik provides is useful for adaptive systems when a solution/reaction has to be found in a short time. We evaluate our approach on a cloud reasoning engine that is able to continuously provision customers software while handling several conflicting objectives (i.e, isolation, cost). We have integrated Sputnik in the Polymer 1 framework and evaluated it using 1 http://kevoree.org/polymer/ Kevoree2 as a models@run.time platform. We have conducted experiments to compare natural selection performance versus Sputnik performance. Our experiments highlight that Sputnik results in a faster convergence by reducing the number of generations while conserving the ability to achieve acceptable trade-offs in our use case. This paper is organized as follows. Section 2 describes the key concepts related to this paper. Section 3 presents Sputnik hyper-heuristic. Section 4 presents validation elements of our approach. Finally, Sections 5 and 6 discuss the related work, our conclusion and future work.

II. CLOUD OPTIMIZATION, MOEAS RUN-TIME

CONSTRAINTS AND HYPER-HEURISTICS This section introduces existing approaches that have tackled the cloud multi-objective optimization problem. We also briefly outline MOEAs concepts used in Sputnik and their relevance to drive run-time optimization. In a second step, we give an overview about MOEAs performance issues with a particular focus on run-time usage. Finally, we highlight the role of hyper-heuristics to improve MOEAs algorithms efficiency.

A. Multi-Objective Optimization of Software Deployment in the Cloud

When moving their applications to the cloud, cloud customers take advantage of an elastic environment in which resources are previsioned/deprovisioned automatically to adapt to variable workload. Cloud elasticity leverages a set of actions that are responsible to move cloud configurations from one state to another. This leads to a very wide set of potential candidate solutions, and consequently to a wide domain to explore in order to find at a given time the best cloud configuration. Different cloud optimization axes have been recently explored over the literature. For instance some of the approaches are cost effective, other approaches are oriented towards performance improvement or security hardening while others are oriented towards achieving an eco-friendly green cloud. In [START_REF] Chaisiri | Optimization of resource provisioning cost in cloud computing[END_REF], the authors have defined an algorithm called optimal cloud resource provisioning (OCRP) in which they provide an optimal cloud resources provisioning by formulating and solving a stochastic integer programming. The results show that the approach is able to reduce resources costs. In [START_REF] Jung | Mistral: Dynamically managing power, performance, and adaptation cost in cloud infrastructures[END_REF], the authors have proposed Mistral, a controller framework that optimizes power consumption, performance, and costs. Mistral is based on a search algorithm that takes into consideration the costs induced by the search algorithm itself. In [START_REF] Chen | Profiling energy consumption of vms for green cloud computing[END_REF], the authors have built energy profiles to reduce energy consumption in the perspective of designing a green cloud. These energy profiles can be integrated into a monitoring system to reduce energy consumption. In [START_REF] Kateb | Generic cloud platform multi-objective optimization leveraging models@ run[END_REF], we study how security, isolation requirements and performance objectives can be considered simultaneously in the same optimization process.

B. MOEAs Concepts

As depicted by [START_REF] Zhou | Multiobjective evolutionary algorithms: A survey of the state of the art[END_REF], genetic based approaches are suitable candidate for scheduling and planning problems. Genetic Algorithms (GA) are driven by elitism rules that favor the survival of strongest species (best candidate solutions) in analogy to natural selection [START_REF] Van Veldhuizen | Multiobjective evolutionary algorithms: Analyzing the state-of-the-art[END_REF]. They are based on an iterative search process, which involves a set of individuals which are randomly selected and mutated (or mixed using crossover operator) in each iteration to constitute the next generation population. Fitness functions [START_REF] Beasley | An overview of genetic algorithms: Part 1. fundamentals[END_REF] are used to evaluate solutions with regards to a specific optimization problem, in analogy to natural selection where species qualities are evaluated according to their surrounding context. Genetic algorithms introduce changes in the population to create new individuals called offspring through the following operators [START_REF] Van Veldhuizen | Multiobjective evolutionary algorithms: classifications, analyses, and new innovations[END_REF]:

• The crossover operator generates offspring by a genetic recombination of the two selected parents. The resulting offspring maintains some features from each parent, thus maintaining population diversity. • The mutation operator introduces small changes on an individual with a probability to improve the population diversity [START_REF] Mahfoud | Niching methods for genetic algorithms[END_REF]. • The selection operator selects a fixed number of fittest offspring for the next generation to maintain a fixed population size and puts good offspring into the next generation with a high probability. More formally, a multi-objective optimization aims at minimizing a vector function F(x) = ( f 1 (x), f 2 (x), ...., f n (x)) where x ∈ ℜ n and F is a vector of n objective functions. Multi-Objective optimization introduces two important concepts: The Pareto Dominance and the Pareto Optimality [START_REF] Deb | Multi-objective optimization using evolutionary algorithms[END_REF]: given two solution

X 1 and X 2 , X 1 is said to dominate X 2 , (X 1 X 2 ), if f i (X 1 ) f i (X 2 ), for all i = 1, .., n and f i (X 1 ) ≺ f i (X 2 )
for at least one objective function f i (X). A Pareto-optimal front is a curve that groups all solutions belonging to the Pareto-optimal set.

Multi-Objective Evolutionary Algorithms (MOEAs) have been successfully applied in many domains such as finance, logistics and recently in cloud engineering problems. In [START_REF] Coello | Applications of multi-objective evolutionary algorithms[END_REF], the authors have provided a taxonomy of the different application domains of MOEAs. Some of these applications have to be used in a run-time context where dynamic parameters adjustment is required such as running vehicles guidance. Runtime optimization has thus to be performed with constrained resources to cope with run-time constraints, the next section highlights these constraints.

C. Performance of MOEAs at run-time

The usage of MOEAs in run-time optimization problems [START_REF] Jensen | Reducing the run-time complexity of multiobjective eas: The nsga-ii and other algorithms[END_REF], for instance load balancing problems which can be seen as a subset of scheduling problems, motivates the need to improve their performance. Several studies have explored the computational costs of MOEAs [START_REF] Khare | Performance scaling of multi-objective evolutionary algorithms[END_REF], [START_REF] Van Veldhuizen | Multiobjective evolutionary algorithms: Analyzing the state-of-the-art[END_REF] by evaluating their performance on different problems using various MOEAs categories. According to [START_REF] Jin | A comprehensive survey of fitness approximation in evolutionary computation[END_REF], MOEAs computational costs can be reduced by reducing its algorithmic complexity or the computational costs of the fitness function. Several studies have been focusing on highlighting the computational costs of fitness evaluations while proposing models to reduce its cost. In [START_REF] Buche | Accelerating evolutionary algorithms with gaussian process fitness function models[END_REF], the authors have tested complex fitness functions, and have proposed the concept of surrogate models to reduce their computational cost. Their approach is based on a gaussian optimization model that evaluates previous fitness functions to estimate future fitness functions scores instead of evaluating real fitness functions. In [START_REF] Tan | Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization[END_REF], authors highlight the impact of large populations on the computation time of the Pareto front [START_REF] Ishibuchi | Evolutionary many-objective optimization by nsga-ii and moea/d with large populations[END_REF], [START_REF] Ishibuchi | Comparison between singleobjective and multi-objective genetic algorithms: Performance comparison and performance measures[END_REF]. In [START_REF] Khare | Performance scaling of multi-objective evolutionary algorithms[END_REF], [START_REF] Deb | Scalable multiobjective optimization test problems[END_REF], authors conduct experiments and highlight the efficiency loss and overhead introduced by a number of objectives above 3.

All of these studies highlight MOEAs performance drawbacks and propose specific solutions to improve MOEAs. In this paper, we focus on the notion of hyper-heuristic (described in the next section) to propose a solution with an impact on the algorithm complexity.

D. Hyper-heuristics: Classification and Objectives

In search based engineering, hyper-heuristics [START_REF] Burke | A classification of hyper-heuristic approaches[END_REF] define methods that act on adapting search parameters over the search process. Hyper-heuristics introduce modifications on the algorithm itself, in order to improve its computational efficiency or effectiveness to handle a specific purpose [START_REF] Seah | Pareto rank learning in multi-objective evolutionary algorithms[END_REF]. Hyper-heuristics rely on machine learning mechanisms [START_REF] Burke | A classification of hyper-heuristic approaches[END_REF], to leverage knowledge assessed during each search iteration. For example, in [START_REF]Deriving operating policies for multi-objective reservoir systems: Application of self-learning genetic algorithm[END_REF] such learning methods store neighborhood information through a neural network to improve a genetic algorithm accuracy. In [START_REF] Mansilla | Molecs: Using multiobjective evolutionary algorithms for learning[END_REF], a learning method is used to prioritize some objectives along the search process.

Hyper-heuristics can be classified according to the following taxonomy [START_REF] Burke | A classification of hyper-heuristic approaches[END_REF] depending on the nature of the heuristic used (based on selection or generation methodologies). For each nature, we thus differentiate : (i) Online learning hyper-heuristics which learn while the search algorithm is running, (ii) Offline learning hyper-heuristics which learn from the system before the execution of the search process. The contribution of this paper, falls into the category of hyper-heuristics that embed online learning mechanisms which are based on both selection and generation methodologies to achieve performance improvement over a set of software engineering problems [START_REF] Güney | Hyper-heuristics for performance optimization of simultaneous multithreaded processors[END_REF], [START_REF] Özcan | A comprehensive analysis of hyper-heuristics[END_REF]. Indeed, our approach relies on mutation operator prioritization (selection nature) based on the evaluation of past execution efficiency (generation nature).

III. Sputnik: AN HYPER-HEURISTIC FOR AN EFFICIENT SELF-ADAPTIVE SYSTEMS OPTIMIZATION

The randomness introduced by natural selection of evolutionary approaches leads to suboptimal performance in terms of computational power and memory usage. Random selection of mutation operators produces useless candidate solutions that lead to computational resources wastage and therefore does not meet run-time optimization constraints. In modern biological studies, after identifying a gene impact on an individual phenotype trait, scientists like Muller et al [START_REF] Plaskett | Artificial transmutationof the gene[END_REF] leverage artificial mutation to directly produce an individual combining the foreseen modification.

Our hypothesis is that the artificial mutation concept can be introduced in evolutionary algorithms to mimic modern biological genetics, thus reducing the number of required generations to reach acceptable solutions. The a priori scientific knowledge of a gene modification impact, could be replaced by a continuous ranking and learning approach leveraging execution history. Therefore, in this paper we aim at optimizing MOEAs, by dynamically reducing the usage of mutation operators that are less effective in improving fitness functions scores. At the same time, we maintain the equity of natural selection, to ensure that the modified evolution algorithm is able to reach any solution. Thus, we replace the random mutation operator selection by an hyper-heuristic that detects for each individual the most pertinent operator to apply in order to achieve a faster trade-off.

After each application, mutation operators are classified according to the delta variance they introduce on each fitness function. Internally, Sputnik maintains an elitist group of mutation operators that are relevant to improve a fitness function score. To enhance operators selection, Sputnik, considers the current fitness scores reached by a solution, and selects the most relevant mutator in elite groups to improve next generation 3 . As illustrated in Figure 1, Sputnik takes as inputs an initial population and a generation number. As most of MOEAs variants like (NSGA-II, ε-MOEA, SPEA 2 [START_REF] Van Veldhuizen | Multiobjective evolutionary algorithms: Analyzing the state-of-the-art[END_REF]), the algorithm is based on an individual ranking step according to fitness function evaluation and a non dominating population construction. Sputnik introduces a favoritism operator approach in the mutation process described as follows:

We consider a multi-objective evolutionary optimization of f with n objectives ( f 1 , f 2 ,..., f n ). The average fitness score for a generation g l is defined by n ∑ i=1 f i /n for each individual in the generation. We define impact f g l ,op as the fitness score variation between the average of fitness function evaluation for a generation g l-1 and a generation g l that is achieved by the operator op:

3 http://www.genetics.org/content/111/1/147.short

impact f g l ,op =( n ∑ i=1 f i /n) g l ,op -( n ∑ i=1 f i /n) g l-1 ,op
Sputnik records the selection occurrence for the different mutation operators that have been involved over the search process. Once all mutation operators have been selected at least once, impact f g l ,op is evaluated for all the operators and Sputnik is configured to select the operators that have impact f g l ,op > 0 in the generation g l+1 with the Elitist or the Caste strategies. More formally, Sputnik selection function selection op is specified as follows:

selection op : operators × generation × ob jectives -→ operator × probability (op 1 , op 2 , ..., op m ), g l , ( f 1 , f 2 , ..., f n ) -→ op max( impact fg l ,op) × P selection P selection depends on Sputnik strategy and is evaluated as follows:

• Elitist Strategy: The operator that has the highest impact f g l ,op is selected in the generation g l+1 with a high P selection . This configuration accords higher chance to the "winner operator" to be selected in the next generation. All others operators are selected with a probability 1-P selection .

• Caste Strategy: A selection probability is partitioned between operators which have impact f g l ,op 0 and is defined as follows:

P selection = impact f g l ,op ∑ op∈operators impact f g l ,op
. This configuration gives more equity in terms of selection probability for all operators which have a positive impact on a fitness score.

Sputnik-based mutation operators selection is described in Algorithm 1. In both settings, we set a selection probability of 10% for pure random selection of operators to not discriminate worst ranked operators. The random selection of operators mimics the natural evolution and aims at giving equitable chances to all solutions, and to any potential mutation operator. This random operators selection ensures a proper exploration of the domain and prevents the solutions to fall into a local minimum. Sputnik keeps 10% of mutation to give chance to less selected operators to be reintroduced in the elite group of a fitness function. Through this mechanism, we keep a minimal equity of species while conserving 90% of the Pareto for most efficient mutation.

IV. VALIDATION

To evaluate Sputnik, we have considered an experimental scenario in which a cloud provider aims at placing several software components related to many customers in the different Virtual Machines running on the top of physical machines. We define a cloud configuration as an architecture model which leverages virtual machines and components (i.e, provisioned software in our context) concepts. Based on our architectural model, an Individual represents a solution vector X that corresponds to a cloud infrastructure model. The reader may refer to our open source Polymer framework which gives ample details about our architectural model 4 . A gene corresponds to a component, a virtual machine or a physical machine in our model. A population corresponds to a set of cloud infrastructure models. A genetic mutation operator corresponds to an elementary A Cloud infrastructure multi-objective optimization problem is represented by the following Triplet (I,F,CO). I denotes a cloud infrastructure model which represents an abstraction of a set of (VM). Each (VM) hosts n software components (C). CO denotes a set of possible configurations in I that satisfy F. A configuration co ∈ CO is obtained through a mapping from Components (C) to Virtual Machines (VMs), for example co = (V M 1 (c 1 , c 2 , c 3 )) denotes a configuration with a single virtual machine V M 1 hosting 3 components c 1 , c 2 , c 3 . The vector F(X) is composed of the following 4 objective functions, F(X) = ( f 1 (x), f 2 (x), f 3 (x), f 4 (x)) that have to be minimized. These objectives reflect the different axis of optimization that the provider aims at achieving when placing the software components at the level of the different Virtual Machines and are defined as follows: I presents our set of operators O including 7 mutation operators and 1 crossover (SwitchOperator) operator. Software deployment in the cloud is a multi-objective optimization problem that aims at finding a cloud configuration co ∈ CO such as min F(X) co . We have implemented an optimization prototype in the Polymer framework which leverages a model based encoding to perform MOEAs optimization. Model@run.time paradigm [START_REF] Blair | Models@ run. time[END_REF] enables our cloud models to be seamlessly deployed in a real large-scale production environment [START_REF]Dissemination of reconfiguration policies on mesh networks[END_REF], [START_REF] Fouquet | A dynamic component model for cyber physical systems[END_REF] like a cloud infrastructure. Thus this validation section aims at evaluating the performance improvement achieved by Sputnik hyper-heuristic, in terms of efficiency and effectiveness to solve the software deployment optimization problem.

• f 1 (x)= Cost(

A. Research Questions

This validation section aims at exploring Sputnik efficiency to improve MOEAs convergence speed to achieve a certain level of trade-off between several objectives. Thus, we compare the efficiency achieved with and without Sputnik hyperheuristic. We also explore the effectiveness of Sputnik once embedded in most popular MOEAs algorithms such as ε-MOEA and NSGA-II. As a metric to compare the solutions of the different algorithms under study, we choose the hypervolume [START_REF] Zitzler | The hypervolume indicator revisited: On the design of pareto-compliant indicators via weighted integration[END_REF] metric as Pareto-front quality indicator that defines the total size of space dominated by the solutions in the Pareto-front. Our validation steps are summarized in the following research questions:

• RQ 1 : Sputnik Efficiency:

B. Experimental results

To answer RQ 1 , we embed Sputnik in a cloud optimization engine that manages 100 virtual nodes and maintains a web front-end and a load-balancer software components that have to be dispatched in the different Virtual Machines (VMs). Our cloud reasoning engine is configured to leverage an ε-NSGA II [START_REF] Deb | Multi-objective optimization using evolutionary algorithms[END_REF]. We perform 30 runs of our experiments with 300 generations with the following configurations: Sputnik with Caste Strategy, Sputnik with Elitist Strategy and finally with random operators selection. The average hypervolume values of the results obtained in the 30 runs, are depicted in Figure 2 according to generation number and in Figure 4.a according to the elapsed time.

We consider that a solution achieves an acceptable trade-off if it reaches 90% of the best obtained solution. In our case study, the best obtained solution achieves an hypervolume of 0.79 (acceptable hypervolume value is 0.71 in our case), it has been reached with a 250 generations previous run. A run with Sputnik (with both strategies) reaches this value after 176 generations whereas a run with random operators selector reaches this value after 279 generations, respectively 8s for Sputnik and 16s for the random selection. Sputnik strategies are very similar in terms of hypervolume achievements, they both reach a value around 0.76. We notice that elitist strategy converges slightly faster however, the caste strategy can reach better hyper-volume scores. These results can be justified by mutators diversity introduced by the caste strategy, which favors at a certain extent operators equity. In average, Sputnik (both with caste and elitist configurations) outperforms random selection by reducing around 37% the number of necessary generations, and around 50% the time to reach acceptable solutions. This confirms our first hypothesis which states that a smart mutation selection strategy is successful to improve efficiency to reach acceptable trade-offs compared to a classical random selection strategy.

To explore the impact of the selection probability of the elitist strategy on Sputnik efficiency, we run the same previous experiment with two different probability values of P selection . The results of a selection probability of 90% and 50% are shown in Figure 4.a and Figure 4.b. Unsurprisingly, we observe that the more Sputnik uses its learning strategy, the best is the convergence speed comparing to a random selection.

We also have evaluated the values reached by the different objectives of our case study (Cost, Redundancy, Similarity, Isolation). The results are illustrated in Figure 3. The chart presents the cost per hour and SLA satisfaction percentage reached for the Redundancy, Similarity, Isolation objectives. Note that in a mono-objective optimization that aims at just reducing one objective at a time, we have best objectives values. Note that the values obtained for the mono-objective optimization correspond to distinct runs in which we aimed at optimizing one objective at once on the detriment of other objectives. For our minimization multi-objective optimization problem, Sputnik achieves 3 better objectives values in 400 generations compared to a standard NSGA-II: For the different objectives (Cost, Similarity, Redundancy, Isolation), a possible solution presents the following values (75.96, 29.41, 78.94, 35.57) compared to (76. 41, 41.26, 48.38, 57.54) for standard NSGA-II. We conclude that for the same number of generations, we obtain results that exhibit better trade-offs with Sputnik activated on top of NSGA-II.

To answer RQ 2 , we run a similar experiment with both To answer RQ 3 , we have evaluated Sputnik with different MOEAs algorithms and various number of objectives. Given that several factors (e.i., implementation aspects, existence of other processes running in the machine, etc) may influence execution time of our approach, we have compared the hypervolume reached over 400 generations. The results are shown in Figure 5 with hypervolume distribution in Figure 6. For NSGA-II algorithm, an hypervolume value of 0.7 is reached after 90 generations with Elitist strategy, 120 generations with Caste strategy, and reached after 240 generations with random strategy. A Sputnik on top of ε-NSGA-II for almost both the Caste and the Elistist version achieves an hypervolume of 0.6 in 100 generations. Similarly to NSGA-II based approaches, we observe a similar speedup for SMS-MOEA and ε-MOEA algorithms. Above 300 generations for NSGA-II and ε-NSGA-II, we also observe that the elitist strategy could lead to little decreased effectiveness. This result could be explained by the total order between operators introduced by elitist strategy, which reduces diversity. We conclude that the caste strategy is less intrusive hyper-heuristic which maintains better the algorithm effectiveness. From these runs, we notice that the Sputnik hyper-heuristic can be generalized on several MOEAs. Secondly, we have explored the generalization of Sputnik with variable objectives by analyzing the hypervolume while varying the objectives from 1 to 4. The results, generated with NSGA-II for 200 generations are presented in Figure 7 in term of optimization time. We observe that Sputnik with the caste and elitist strategies provides faster hypervolume convergence compared to random with smaller number of objectives. Indeed for 1 and 3 objectives, the Sputnik strategy selects efficient operators faster, however above 4 objectives, Sputnik effect tends to be similar to random selection. We explain such effect by the fact that Sputnik does not keep the history of previous selected operator selection, thus above 4 objectives, the selection tends to be random. In future work we plan to add operators selection history to maintain Sputnik efficiency independently of the objectives number.

C. Threats to Validity

Internal validity is related to the parameters setting of our experiments (i.e. generation number, objectives number, operators, etc...), such as values chosen for the value of ε in the ε-dominance which might impact our validation results. More specifically, Sputnik incrementally builds a mapping of each operator impact on a particular fitness function. Thus, the coupling effect between the eight used operators and a particular fitness function could introduce a bias on our results. To minimize this bias, we leverage a set of operators without direct coupling effect.

Construct validity arises from the bias introduced in the way we build our experiments. In each experiment presented in the paper, we have compared one run of Sputnik against a random mutator selector. As for any random based techniques, a set of repeated experiments should be run to draw statistially significant results. This bias is mitigated by the number of different experiments that have been run on Sputnik which all demonstrate the effectiveness of the approach.

External validity is related to the generalization of observed results outside the case study presented in the validation section. Although we applied the approach to a cloud reasoning engine and have shown the impact of Sputnik to improve the efficiency of the optimization, further experimentation is needed on different systems that have to comply to run-time constraints in their optimization process.

V. RELATED WORK Several approaches have focused on heuristics to improve classical evolutionary algorithms such as Ant Colony Optimization, Particle Swarm Optimization and Artificial Bee Colony [START_REF] Selvi | Comparative analysis of ant colony and particle swarm optimization techniques[END_REF]. This work focuses on hyper-heuristics that operate on top of MOEAs to improve their usage in a run-time context and particularly to a cloud-based deployment software. In [START_REF] Seah | Pareto rank learning in multi-objective evolutionary algorithms[END_REF], the authors embed learning techniques in classical MOEAs. They assume that objective functions are expensive to compute so they rank the Pareto front elements and they evaluate only the individuals that have higher ranks. In [START_REF] León | Hyperheuristics for a dynamicmapped multi-objective island-based model[END_REF], the authors have proposed an hyper-heuristic that relies on the hypervolume calculation to improve computational results. These approaches consider only the Pareto front set evaluation to improve MOEAs, whereas our approach evaluates operators contribution in improving fitness and thus injects mutation operators that are eligible to make MOEAs converge faster. In [START_REF] Yuan | Statistical racing techniques for improved empirical evaluation of evolutionary algorithms[END_REF], the authors have shown that racing algorithms can be used to reduce the computational resources inherent from using evolutionary algorithms in large scale experimental studies, their approach automates solutions selection and discards solutions that do not introduce results improvement. Whereas racing techniques eliminate worst solutions candidates to speed up the search, in our approach we keep considering worst ranked candidates to maintain operators diversity. In [START_REF] Drake | Controlling crossover in a selection hyper-heuristic framework[END_REF], the authors have explored the advantages of using a controlled crossover on top of single-point search based hyper-heuristics. They maintain the best solutions obtained during the search and update crossover operator accordingly. The authors rely on a process focused on crossover as a biological selective breeding. This breeding assumes that fittest genes are already present in the initial population. Unlike cited approaches, Sputnik focuses on artificial mutation selection, therefore mimicking the process used to produce genetically modified organisms. As far as we know, there is no other hyper-heuristic that proposes artificial mutation at mutation operators level.

VI. CONCLUSION

In this paper, we have introduced, an hyper-heuristic breaking the random natural selection of classical MOEAs to leverage an elitist artificial mutation inspired by biological studies [START_REF] Plaskett | Artificial transmutationof the gene[END_REF]. Sputnik relies on a mutation operator selection based on a continuous learning of past effect on fitness functions, instead of random mutation operators selection. The overall goal of Sputnik is to enhance the optimization algorithm itself, and to guide the search towards faster trade-offs achievement to finally save generation cycles and time. Experimentally, we provide evidence of the effectiveness of artificial mutation to reduce significantly the number of necessary generations to find acceptable trade-offs. In the future, we plan to explore the effectiveness of Sputnik in accelerating the optimization processes of other adaptive systems that have to comply with run-time constraints.

Fig. 1 :

 1 Fig. 1: Sputnik Workflow

  x): Denotes Virtual Machines cost which is proportional to the number of active VMs on the top of a PaaS. • f 2 (x)= Isolation(x): This function is incremented by 1 whenever two components from different cloud customers share the same Virtual Machine. To achieve isolation, a cloud provider aims at hosting software components belonging to different customers workloads in different Virtual Machines. • f 3 (x)= Similarity(x): The similarity function quantifies the similarity between the components hosted in Virtual Machines to assess software diversity. Software diversity [2] is an indicator of potential cascading failure to quantify cloud fault tolerance capabilities. • f 4 (x)= Redundancy(x): The redundancy function provides a score based on redundant software (i.e. number of replicates of the same service). All fitness values have been normalized to range in the interval [0,1]. Table

1 Fig. 2 :

 12 Fig. 2: Hypervolume: Sputnik (Elitist & Caste) versus Random Selection

Fig. 4 :Fig. 3 :

 43 Fig. 4: NSGA-II Hypervolume with different probabilities of Sputnik Selector (a) Sputnik selector with a probability of 90%

Fig. 5 :Fig. 6 :

 56 Fig. 5: Hypervolume over 400 generations (a) NSGA-II

Fig. 7 :

 7 Fig. 7: NSGA-II hypervolume over Execution Time with Variable Objectives (a) 1 objective

  Algorithm 1 Sputnik Input: Population P, Generation Number g, Operators Op set , List of operators operator-used=∅, boolean sputnik active=false Output: Population P Apply randomly a mutation operator Op current on P to get P new for all j where j ranges from 1 to g do Evaluate f i (x) on P operator-used:=operator-used ∪ Op current /* Sputnik is active only if all the mutation operators have been at least chosen once */ if operator-used ⊆ Op set then sputnik active=true Evaluate impact f g i ,op ∀ op in Op set Select P selection ∈ {P elitist , P cast } Identify Op best Select Op best with P selection , Op with 1-P selection from Op set and get P new else Select Op randomly from Op set and get P new end if Update P based on dominance ranking and crowding distance to get P new end for flip in the model that is introduced by an elementary operation.

TABLE I :

 I Operators Definition

http://kevoree.org/

http://kevoree.org/polymer/


Francisco Javier
email: francisco.acosta@inria.fr

Acosta Padilla

Frederic Weis
email: frederic.weis@irisa.fr

Johann Bourcier
email: johann.bourcier@irisa.fr

Towards a Model@runtime Middleware for Cyber Physical Systems

Cyber Physical Systems (CPS) or Internet of Things systems are typically formed by a myriad of many small interconnected devices. This underlying hardware infrastructure raises new challenges in the way we administrate the software layer of these systems. Indeed, the limited computing power and battery life of each node combined with the very distributed nature of these systems, greatly adds complexity to distributed software layer management.

In this paper we propose a new middleware dedicated to CPS to enable the management of software deployment and the dynamic reconfiguration of these systems. Our middleware is inspired from the Component Based Systems and the model@runtime paradigm which has been adapted to the context of Cyber Physical Systems. We have conducted an initial evaluation on a typical Cyber Physical Systems hardware infrastructure which demonstrates the feasibility of providing a model@runtime middleware for these systems.

INTRODUCTION

We are now surrounded by a plethora of interconnected devices (mobile phones, household appliances, wearable sensors, and so on) that continuously collect data on our living environment. This distributed computing infrastructure is becoming pervasive and users tend to naturally interact with it. This new computing environment offers a lot of opportunities for developing new applications in many different domains. Technology can now operate behind the scene by dynamically responding to people wishes. Based on this principle, Cyber Physical Systems (CPS) have emerged. CPS are pervasive and long living systems formed by a constellation of many small interconnected devices integrated into houses, building, cities, factory chain, etc.

In a building automation scenario, CPS typically rely on sensor nodes that detect and record data such as presence, temperature, ambient lighting and energy consumption. Thus, a CPS uses sensors to continuously analyse the situation in order to adapt our living environment to match user needs and preferences. User wishes may involve different objectives such as comfort, air quality, and energy savings. To go beyond energy management and comfort, building automation systems have to deal with new types of services, depending on the use of the building: fire safety and security management for hotel, indoor air quality control in schools and office buildings, etc. The opportunities of services offered by CPS and the user preferences are countless and will change over the lifetime of these systems. The set of small interconnected devices integrated into building can be seen as a computing infrastructure that can host these new services. Consequently the software deployed on these nodes needs to be dynamically reconfigured and re-deployed to meet the evolution of services and user preferences.

For this reason, the capacity of dynamically deploying and reconfiguring the software layer of CPS is a crucial feature. In this paper, we address the problem of enabling the deployment of a distributed software layer and its dynamic reconfiguration over a network of nodes featuring very limited resources: memory, processing power, bandwidth communication and energy autonomy.

To solve this problem, various techniques have been proposed, such as system image replacement [START_REF] Hui | The dynamic behavior of a data dissemination protocol for network programming at scale[END_REF] and virtual machines [START_REF] Koshy | Vm*: Synthesizing scalable runtime environments for sensor networks[END_REF]. These approaches have two main drawbacks. First they are not efficient in terms of energy. Second while they are suited to deploy static applications, these are not convenient solutions for CPS, because CPS operate in dynamic environments in which tasks performed by each node must be easily and frequently adapted.

In this paper we present our initial results towards the design of a middleware featuring deployment and reconfiguration facilities over a Cyber Physical System. Our middleware aims at implementing the paradigm of model@runtime taking into account the stringent requirements of Cyber Physical Systems. This paper is structured as follows. Section 2 presents the Kevoree component model. Section 3 details the challenges of mapping the model@runtime paradigm to microcontrollers, and explains how we implemented Kevoree on these very limited nodes. Our proposal is evaluated in section 4. Section 5 presents related work and Section 6 gives our conclusion and highlights some perspectives to be addressed in future work.

BACKGROUND

The problem of managing software layer in a distributed system is not a new topic. Component based systems and the model@runtime paradigm [START_REF] Morin | Taming dynamically adaptive systems using models and aspects[END_REF] has been proposed in the context of distributed systems to manage the software layer. In this section, we briefly present these paradigms and highlight their limitations regarding the Cyber Physical Systems environment.

Component-based software architecture

The software architecture aims at reducing complexity through abstraction and separation of concerns by providing a common understanding of component, connector and configuration [START_REF] Dashofy | An infrastructure for the rapid development of XML-based architecture description languages[END_REF][START_REF] Medvidovic | A Classification and Comparison Framework for Software Architecture Description Languages[END_REF][START_REF] Van Ommering | The Koala Component Model for Consumer Electronics Software[END_REF]. One of the benefits is that it facilitates the management of dynamic applications, which becomes a primary concern in Cyber Physical Systems [START_REF] Nitto | A journey to highly dynamic, self-adaptive service-based applications[END_REF]. Such systems are inherently dynamic and thus require techniques for self-adaptation. Many works [START_REF] Fouquet | Dissemination of reconfiguration policies on mesh networks[END_REF][START_REF]Proceedings of the 15th ACM SIGSOFT Symposium on Component Based Software Engineering, CBSE 2012, part of Comparch '12 Federated Events on Component-Based Software Engineering and Software Architecture[END_REF] have demonstrated the benefits of using component-based approaches in such open-world environments [START_REF] Baresi | Toward open-world software: Issue and challenges[END_REF].

To satisfy the needs for adaptation, several component models provide solutions to dynamically reconfigure software architectures through, for example, the deployment of new modules, the instantiation of new services, and the creation of new bindings between components. In practice, component-based (and/or service-based) platforms like Fractal [START_REF] Bruneton | The FRACTAL Component Model and its Support in Java. Software Practice and Experience, Special Issue on Experiences with Auto-adaptive and Reconfigurable Systems[END_REF], OpenCOM [START_REF] Coulson | A component model for building systems software[END_REF], OSGi [START_REF]OSGi Service Platform Core Specification[END_REF] or SCA [START_REF] Seinturier | A Component-Based Middleware Platform for Reconfigurable Service-Oriented Architectures[END_REF] provide platform mechanisms to support dynamic architectures.

Model@runtime

Built on top of dynamic component frameworks, the model@runtime paradigm refers to a model-driven approach that aims at reducing the complexity of dynamic adaptation in distributed systems. In practice, component-based platforms offer reflection APIs that allow introspection within the application (e.g., which components and bindings are currently in place in the system) and dynamic adaptation (e.g., changing the current components and bindings). While some of these platforms offer roll-back mechanisms to recover after an erroneous adaptation [START_REF] Léger | Reliable dynamic reconfigurations in a reflective component model[END_REF], the purpose of model@runtime is to prevent the system from actually enacting an erroneous adaptation. In other words, the "model at runtime" is a reflection model that can be decoupled from the application (for reasoning, validation, and simulation purposes) and then automatically resynchronized. The principle of model@runtime is illustrated on figure 1.

The Kevoree framework

Kevoree is an open-source framework which provides an implementation of the model@runtime paradigm for distributed systems. It provides the following concept to design a distributed system featuring dynamic adpatation. The Node concept is used to model the infrastructure topology and the Group concept is used to model the semantics of inter-node communication, particularly when syn-chronizing the reflection model among nodes. Kevoree includes a Channel concept to allow for different communication semantics between remote Components deployed on heterogeneous nodes. All Kevoree concepts (Component, Channel, Node, Group) obey the object type design pattern [START_REF] Johnson | The Type Object Pattern[END_REF] in order to separate deployment artifacts from running artifacts. Kevoree supports multiple execution platforms (e.g., Java, Android, MiniCloud, FreeBSD, Arduino). For each target platform it provides a specific runtime container.

As a result, Kevoree provides an environment to facilitate the implementation of dynamically reconfigurable applications in the context of distributed system. Because our goal is to design and implement a middleware dedicated to CPS to enable the deployment and dynamic adaptations, the introspection and the dynamic reconfiguration facilities offered by Kevoree seems to suit our needs.

Limitations regarding CPS

The model@runtime paradigm has been mainly investigated in the context of distributed systems. These research efforts have been focused on the provision of a comprehensive set of tools to easily deploy, dynamically reconfigure, and disseminate software on a set of distributed computing units. The current model@runtime tools have been implemented regardless of the specific characteristics and constraints of a Cyber Physical System. In particular, the network topology and the resource constraint of the nodes forming the distributed system have not been taken into consideration. As a result, state of the art model@runtime tools are not suitable to be used in the context of Cyber Physical Systems. First, most approaches are relying on the Java language, which does not meet the resource constraint of the computing nodes. Secondly, the size of the model and its distribution among the system are not taking into consideration the limited memory capacity of each node, and their energy constraints.

In [START_REF] Fouquet | A dynamic component model for cyber physical systems[END_REF], an effort has been made to port the model@runtime paradigm on the constraints of a Cyber Physical System. Despite the particular attention given to the specific constraints of a Cyber Physical System, this work heavily relies on over the air firmware flashing to support the deployment and reconfiguration of software. We consider that relying on firmware flashing to support software deployment constitutes a flaw in the approach because of its energy cost (the complete firmware has to be sent, and if any error occurs, the whole process is restarted). A second limitation of this approach lies in the fact that each resource constrained node relies on a more powerful node to perform most of his task related to the dynamic reconfiguration (firmware synthesis, reconfiguration decision and so on). This second limitation is not suitable in the context of a system mainly composed of resource constrained nodes since all the resource constrained nodes have to be managed by bigger nodes. Pushing this idea further, the management of a CPS composed of a wide number of resource constrained devices and a bigger node, the latter will have to manage all the smaller devices in a centralized management scheme.

In this paper, we investigate a dedicated model@runtime approach for CPS which offers the same set of functionalities on resource constrained nodes and bigger nodes.

MODEL@RUNTIME FOR CPS 3.1 Overview

In this paper we present our initial result towards the design of a middleware which will offer the functionalities of model@runtime over a Cyber Physical System. Porting the concept of model@runtime on Cyber Physical Systems will enable a continuous management of the deployed software. This middleware will give a development framework for the applications development on top of these systems, and will provide the runtime infrastructure to support the deployment and dynamic reconfiguration of these applications.

As illustrated in figure 2, our goal is to provide a middleware that will be present on each node of the system, and will take care of the various tasks imposed by the model@runtime paradigm. More specifically, our middleware will be in charge of:

1. receiving new models that define the new targeted state of the system, 2. defining the set of local adaptations that are needed to reach this new state, 3. enacting the various local adaptations produced by the previous step.

The set of local adaptations enables the dynamic reconfiguration and may download new pieces of codes, instantiate or remove components and channels used to bind them, or reconfigure the value of any attribute.

Figure 2: An overview of model@runtime for Cyber Physical Systems

Challenges

Designing the presented middleware in the context of Cyber Physical System raises scientific challenges. All the following challenges are related to the limited resources of these nodes and the particular topology of the network that interconnect them.

Currently the concept of model@runtime has been applied on top of object oriented languages which offers the required features at the language level to implement the model@runtime layer. The implementation of this model@runtime layer requires several features (such as dynamic code loading, network stack, etc.) from the operating system that operates on each node.

The first challenge lies in the fact that typical Operating Systems used in Cyber Physical Systems and which offer these features do not support these object oriented languages and thus the design must fit a procedural language such as C.

The second challenge lies in the very limited resources of these nodes thus forcing the middleware to meet the memory, and CPU constraints. This imposes constraints on the way the model is represented, stored and processed on each node. This challenge is particularly important and hard to meet, since many software components are needed to enable the communication in these environments (radio/MAC/IP stack and so on).

Another challenge comes with the energy constraint of each node, together with the mesh topology of the network. This implies the necessity to optimize the way the model and the software are disseminated in the network.

Current implementation

We use the ContikiOS [START_REF]Contiki: The open source os for the internet of things[END_REF] in order to provide an efficient way to distribute components, since it allows dynamic loading of binary modules. Contiki includes an implementation of the IPv6 compressed stack, 6loWPAN [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE[END_REF], which let us assign directly an IPv6 address. This enables a ready to use IoT environment. We use erbium's [START_REF] Kovatsch | A low-power coap for contiki[END_REF] CoAP implementation in order to have a REST engine which enables services discovery through the network. It is also used as a main communication channel between nodes. The dynamic code loading mechanisms are based on a dynamic linker and loader that use the standard ELF object file format [START_REF] Dunkels | Run-time dynamic linking for reprogramming wireless sensor networks[END_REF].

The current implementation1 is done using the version 4 of the Kevoree meta-model. This meta-model has been mapped into C code as a Contiki application. We are able to add nodes, components, groups and channels, and bind them through the Kevoree editor.

EVALUATION

This section describes the experiments conducted to evaluate our framework described in Section 3.3. The goal of this evaluation is to assess the feasibility of using a model@runtime implementation on CPS. In these experiments, we focus on measuring the overhead induced by our implementation, in order to evaluate the compatibility of this overhead with the resource constraints.

The platform used to run our experiments is located in a testbed called IoT-Lab [START_REF]Iot experimentation at a large scale[END_REF]. IoT-Lab provides a very large scale infrastructure suitable for testing small wireless sensor devices and heterogeneous communicating objects. The M3 open node is a platform that provides similar resources which can be found in most of CPS. This node is based on a STM32 (ARM Cortex M3) microcontroller, which embed 512KB of flash memory and 64KB of RAM. The used toolchain to compile the source code is GCC for ARM.

This evaluation focuses on answering the two following research questions:

RQ1: Does the overhead induced by our models@runtime implementation fit the resources constraints?

RQ2: Is this resulting overhead small enough to allow scalability?

To answer these questions four experiments are performed using the following metrics:

• Start-up delay: time needed to load the current model. To measure this time, we evaluate the time in milliseconds until the application is ready to work.

• Consumption overhead: amount of energy in joules drawn by the node while running our firmware. This energy is measured using IoT-Lab tools.

• Memory: amount of memory used by our model representation and our midlleware. That memory is measured by comparing both flash and RAM between various firmwares implementing our middleware, and another one without this implementation.

Overheads

Experimental setup. We compare the performances of two firmwares.

• The first firmware consists in a simple Blink/COAP application, with the network stack and a CoAP server initialized. This application consists in a LED that starts blinking until the end of the experiment.

• The second firmware includes the same functionalities but using our middleware. For this purpose we add a model@runtime platform in order to get a model reflecting the current state of the Blink/COAP application. To do so, a basic model is built from the current system, representing the Blink/COAP application as a component instance.

All the generated models are compatible with the version 4 of the Kevoree editor 2 . In this experiment the two firmwares are uploaded on an IoT-lab node and the applications are executed during one minute. To evaluate the overhead of our middleware the two firmwares are compared with respect to:

Memory used

• memory consumption both in ROM and RAM,

• the energy consumption, 2 The generated models are available at: https://github.com/kYc0o/kevoree-contiki

• and the startup delay.

The result of this experiment are shown in Table 1.

As it can be observed from the table, the usage of a model@runtime has a visible overhead on the memory both in ROM and RAM. This overhead is due to the code of our middleware for the ROM part and to the model loaded in memory for the RAM part. We consider that this memory overhead is reasonable compared to the benefit of enabling dynamic reconfigurations.

Our approach also impacts the startup time and causes a very small delay before the application is ready. This delay is measured using timestamps. It is due to the time used by the processor, in order to load a model@runtime from the current application. This delay is considered reasonable as it is very small and it only impacts the initial loading of the application and has no effect during the normal operation.

As shown on table 1, the overhead of our framework on the energy consumption is very low. This consumption has been measured using the data generated by the IoT-Lab platform, which includes voltage and power used by the node in an experiment. The energy consumption overhead, shown in Table 1, is obtained as a product of the power in watts used by the node while loading the model@runtime, and the time needed before the application is ready and the LED is blinking. The overhead on energy consumption is only due to the extra computing power needed in the startup phase to load the model in memory. This overhead evaluation highlights the feasibility of implementing a complete model@runtime middleware on CPS. The memory overhead is reasonable and fits with the resource constraints of the CPS nodes. We consider that the critical overhead for such system is the energy consumption, and our results show that it is marginally impacted by our middleware.

Scalability

In this experiment we evaluate the scalability of our approach by focusing on the memory needed to represent a large model. To do so, we first measure the memory size without any model loaded in node's memory. The command size of the ARM compiler was used to obtain that measure, since this application does not need dynamic memory allocation.

Our goal is to evaluate the biggest size that the model can reach. We progressively increase the model size by augmenting the number of nodes until running out of memory. Three variants of this experiment are run at last:

• with one component per node,

• with two components per node,

• and with three components per node.

Figure 3 shows the memory usage for each model depending on its size. These results show that our current implementation enables to scale the model up to 60 nodes with one component per node, and up to 37 nodes with three components per node. These numbers are encouraging, some tens of nodes enable pervasive systems and CPS to run in various environments like house, building, car, factory chain etc.

Summary

Our initial results show that the models@runtime implementation is feasible for CPS and there are enough resources to deploy several other functional software components. It is possible to observe that our overheads are small enough to affect the overall operation of a node, while adding an abstract representation of the running system, in addition to reconfiguration and adaptation features. Since these results are promising, we showed that our middleware is able to manipulate a running application by affecting it through a component model, without an important overhead, neither in memory nor in energy consumption.

RELATED WORK

A preceding implementation of the models@runtime approach, called µ-Kevoree [START_REF] Fouquet | A dynamic component model for cyber physical systems[END_REF], is able to manage dynamic adaptations. When a change is made to the model, a new firmware with the changes is synthesized and sent over the network to the related nodes, while disseminating the reflected model to the entire network. This particular implementation provide the required functionality, but in some wireless networks where energy consumption plays an important role, this method becomes not adapted. Our goal is to provide a flexible and reconfigurable environment by sending to the nodes only the required software components, in order to provide new services. This will reduce the size of the transmitted binary, in such a way that network overhead is consequently reduced.

Another approach called Agilla, a mobile agent middleware designed to support self-adaptive applications in wireless sensor networks, proposes the distribution of specific applications in a WSN. Agilla's model focuses its design for localized adaptations like fire tracking. Thus, data collection is not one of its main features [START_REF] Fok | Agilla: A mobile agent middleware for self-adaptive wireless sensor networks[END_REF]. CPS in communicating environments demand an important amount of data collected from other devices. Due to this system requirements, distribution of single purpose agents seems not to be the best approach.

Valentine [START_REF] Hoang | Valentine: A dynamic and adaptive operating system for wireless sensor networks[END_REF] is a component-based OS which aims to provide reconfiguration functions to WSN, using the Fractal [START_REF] Bruneton | The FRACTAL Component Model and its Support in Java. Software Practice and Experience, Special Issue on Experiences with Auto-adaptive and Reconfigurable Systems[END_REF] approach. It provides a component model that can be reconfigured using eventdriven queues. The reconfigurations can only be made at specific predetermined points in time: when all tasks are finished. Since Valentine uses the Fractal approach components' introspection is available through the controller mechanism. These controllers can be used to obtain a complete image of the system, but increasing at the same time the processor use. Therefore, the time needed to build this representation will increase in relation with the architecture's complexity, which can be for instance the ubiquity of sub-components. This mechanism requires a more powerful node on which reconfiguration schemes can be settled. This important overhead does not lead us to have independent nodes in which a distributed system could be implemented. In most case studies, such distributed systems are often implemented, in order to deploy dynamic applications distributed among CPS. Since most of the current approaches aim to get highly reconfigurable and adaptable environments, it is possible to observe that CPS resource constraints are one of the most important issues. In our implementation, we are able to manage that issue, and we have made possible the usage of a model@runtime to reflect the system state and manipulate it as needed.

CONCLUSION

In this paper, we have presented our proposed solution to ease the deployment and enable the dynamic reconfiguration of the software layer on a Cyber Physical System. Our solution is based on a middleware which proposes an adoption of the model@runtime paradigm to the specific constraints of Cyber Physical Systems. We have presented the scientific challenges to implement this paradigm on resource constrained nodes and an initial evaluation of our implementation which demonstrates the feasibility of implementing this middleware on CPS. This initial work opens many perspectives for CPS. Indeed, the possibility of reasoning on and managing the software layer presents on CPS after their initial deployment is a crucial enabler for many applications.

Our perspective includes works on the way to optimize the model storage, the software download and the propagation of changes within the system. All these aspects are impacted by the network topology and greatly influence the energy consumption of the system. Indeed, minimizing the communication will strongly impact the energy consumption of these systems.

Figure 1 :

 1 Figure 1: Model@runtime principle

Figure 3 :

 3 Figure 3: Memory overhead for 1, 2 and 3 Blink/COAP components.

Table 1 :

 1 Memory use for the Blink/COAP example

				Energy	Startup
				consumption	delay
		ROM (in bytes)	RAM (in bytes)	Joules	Msec.
	Blink + CoAP	79344	13244	9.6	0
	Kevoree +
	Blink +	112724	15822	9.606	39.1
	CoAP

The source code of our framework is available at: https://github.com/kYc0o/kevoree-contiki