Frédéric Voisin
email: fred@fredvoisin.com

Designing Virtual Soundscapes for Alzheimer's Disease Care

Keywords: Sound design, Soundscapes, Sonic Interaction, Cognitive Rehabilitation, Alzheimer's Desease, Dementia, Caring, Quality of Life, Virtual Reality

Sound environment is a prime source of conscious and unconscious information which allows listeners to place themselves, to communicate, to feel, to remember. The author describes the process of designing a new audio interactive apparatus for Alzheimer's care, in the context of an active multidisciplinary research project led by the author in collaboration with a longterm care centre (EHPAD) in Burgundy (France), a geriatrician, a gerontologist, psychologists and caregivers. The apparatus, named Madeleines Sonores in reference to Proust's madeleine, have provided virtual soundscapes sounding for a year for 14 elderly people hosted in the dedicated Alzheimer's unit of the care centre, 24/7. Empiric aspects of sonic interactivity are discussed in relation to dementia and to the activity of caring. Scientific studies are initiated to evaluate the benefits of such a disposal in Alzheimer's disease therapy and in caring dementia.

Introduction

Nowadays, Alzheimer's disease (AD) is the main cause of dementia. AD usually starts slowly and gradually worsens over time with brain damages and main effects on memory, cognition and behiavior : short-term and procedural memories are progressively affected until severely damaged, with severe spatio-temporal disorientation, when long-term memory becomes impaired later [START_REF] Eustache | Langage, vieillissement et démences[END_REF] [START_REF] Dubois | Revising the definition of Alzheimer's disease : a new lexicon[END_REF]. When different hypothesis may explain the causes of AD, there is no known validated pharmacologic therapy. Nevertheless, the research effort present promising results. Non-drug therapies are adapted to flatten or compensate the AD effects by stimulating cognitive and sensorimotor activities such as music practice and dance, which convene neural plasticity processes [START_REF] Chancellor | Art Therapy for Alzheimer's Disease and Other Dementias[END_REF]. Playing and listening to music all together stimulate social forms of cognition, emotion and participate to re-entrainments of implicit and procedural memories affected by AD [START_REF] Guétin | Effect of Music Therapy on Anxiety and Depression in Patients with Alzheimer's Type Dementia: Randomised, Controlled Study[END_REF][5] [START_REF] Mofredj | Music therapy, a review of the potential therapeutic benefits for the critically ill[END_REF].

In the context of longterm care centres (EHPAD), these recent results encourage group musical activities led by music therapists in a variety of non-drug therapies for AD. Nevertheless in such a longterm care context, musical activity may be too rare and the benefits for each victim of AD are difficult to evaluate, particularly when the latter may present different forms of dementia.

Author's preprint version, accepted in july 2019 for the 14th Intern. Symposium Computer Music Multidisciplinary

Research.

As a geriatrician may observe in his own practice in such a context, too little attention is generally given to all sonic interactions which include not only music but various oral communications, noises, audio productions... and silences, all that actually defines the standard soundscapes of a living and social place in a hospital environment.

Moreover, such sonic interactions are able to recall facts from subjects' trivial (long term) memory, and reach the subcortical circuits spared by the disease, in particular those that are related to emotion as well as hearing.

In 2016, an experimentation by Dr Jeannin with AD victims showed that some peculiar sounds can help recall long-term memories and emotions, when the listener's performance shows no relation with standard cognitive tests such as MMSE and NPI. Dr Jeannin also demonstrates how long such an experience of auditory memory with simple sounds implies a knowledge of the biography of the listener : this biographical knowledge may facilitate the activity of caring by, for instance, sparking some conversation [START_REF] Jeannin | Projet Hippocampe : Les madeleines sonores[END_REF].

Therefore, some hospital's inner sound environment may not be well adapted to AD victims : during the day, loud radio or TV-shows play for a long time in individual or collective rooms and can make a continuous flow of informations that has mostly become incomprehensible in the studied cases of dementia. At night, wanderings are not rare in deep silence with no landmarks, no surprise, nowhere to go when the way back may be already lost in anonymous and closed halls, etc.

When sonic interactions may focus on the caring activity in a clinical perspective, a question may be: how would sound directly take part in AD caring ?

It is with this prospect that the Grégoire Direz Residence (EHPAD) in Mailly-le-Château has welcomed, since July 2017, a sound design research action in their unit specially equipped for AD victims. The hospital, its geriatric physician (Dr Pierre Jeannin), and its care team work together with a gerontologist (Prof. France Mourey1 ) on scientific aspects while I work on conceiving and carrying out the sound device on location: the « Madeleines sonores ».

To be pragmatic, we presume that from a functional and systematic point of view, not only music but every sound may involve various cognitive and emotional circuits [START_REF] Westerkamp | Linking Soundscape Composition and Acoustic Ecology[END_REF] [START_REF] Andringa | How Pleasant Sounds Promote and Annoying Sounds Impede Health: A Cognitive Approach[END_REF]. An hypothesis would be that as soon as emotions and long-term memory still strong in later stages of AD (alexithymia appears late), not only music but any sound, if well chosen sounds, may help the caring activity [START_REF] Jeannin | Projet Hippocampe : Les madeleines sonores[END_REF] for AD : being in situ (i.e. on location), attention, social processes as well as emotion -itself able to move us -can be called upon as much through the music as from a variety of familiar or merely recognized sounds. Where, when and how sounds occur seem to be relevant questions to AD and dementia in a longterm health care centre.

Finally, one may consider that a continuity exists between "music" and "nonmusic" or "noise", which vary according to the human society and its history. According to Luigi Russolo, Edgar Varèse, John Cage, Pierre Henri, Muray Schafer and others, a silent rest, a siren and other urban or natural soundscapes may be considered as "music" in certain conditions. Anthropologists and musicologists have shown a very large variety of music productions in relation to humans, animals, nature or surnatural beings.

Designing Soundscapes for AD victims

Pragmatically, we suggest designing virtual soundscapes adapted not only to different stages of dementia due to AD, i.e. to different mind states and beliefs, but also to some of the physiological effects of aging, such as a reduced visual field, hearing loss (or blocked ears), altered movement control, relative perceptions of time, etc. Starting from my own experience, from philosophical and ecological aspects of soudscapes from philosophical and theoretical frameworks devoted to soundscapes and mental health [START_REF] Schafer | The Tuning of the World[END_REF][9] [START_REF] Andringa | How Pleasant Sounds Promote and Annoying Sounds Impede Health: A Cognitive Approach[END_REF], and from rare references to some experiments on sound and soundscapes for AD victimes [START_REF] Nagahata | A soundscape study : What kinds of sounds can elderly people affected by dementia recollect?[END_REF] [START_REF] Burgio | Environmental «white noise»: an intervention for verbally agitated nursing home residents[END_REF], I decided at first to chart the time and space of this very particular place and, then, to focus on anxiety phenomena that a sound environment may generate in certain conditions, particularly with elderly people.

After my first observations done for nights and days in the Alzheimer's Unit at the EHPAD under the supervision of Dr Jeannin and of the caring team, I decided at first to design the common areas of the Unit, where people spend place most of their time standing, moving, doing some activity or resting, with the care team.

The first sounds I had to produce had to obviously be congruent with the physical environment: big rooms, corridors, impersonal furniture, windows overlooking beautiful gardens and, in the distance, a village ... They also had to be congruent with the immediate perception and beliefs the residents may have, residents who are affected by (various forms of) dementia but who also bravely bear the various marks of now ancient times! To answer these multiple deteriorations of perception (vision, audition, proprioception), I deemed necessary to start with reinforcing what already existed to increase perception, thus "reality" in some ergonomical perspective. This is the context in which, afterwards, sounds were supposed -tactfully -to encourage each one's imagination of former memories, collectively as well as individually, ordinary as well as extraordinary : not only with sound samples played out of their context, but sound effects.

A great variety of sound effects may partake in the staging of different sound realities and their modelling. With that prospect, I suggest understanding the notion of sound effect with an emphasis on a "logic of meaning", between the cause and the event itself, "in a dimension that is altogether that of event and of situation", through the "demonstration of a phenomenon that supports the [assumed] existence of the object" [START_REF] Augoyard | Sonic experience: a guide to everyday sounds[END_REF]. Therefore, the staging of this particular hospital space, that has become the canvas of a "film for the ear", must be as much part of the scripting as of the content of the generated sound flows. By the way, the digital audioprocessing used in the actual disposal are not numerous: some peculiar synthesisers and peculier sound players with volume controls, fading, filters and a reverb. On the contrary, the logical and stochastic effects are much richer and are the subject of the original computer coding (see below Section 4).

Author's preprint version, accepted in july 2019 for the 14th Intern. Symposium Computer Music Multidisciplinary Research.

In the map above (see Figure 1), sounds produced from realistic sources from outside are supposed to be welcome in such a hospital's closed space : at its extreme borders, synthesized sounds of (virtual) bells give night and day to the listeners the (real) hours... or a landmark, as well as a short but regular game for cognitive stimulation (counting the strokes). In the patio, a granular audio synthesizer produces a continuous but varying waterfall sound, congruent with the beautiful but silent view, when the windows cannot be opened for security reasons.

This very first signals appear to be strong enough as landmarks to allow some algorithmic variations, depending on a mix between the actual and virtual place, on both the weather and the rhythm of the caring activity : when the sound quality of the waterfall or of the bells can change according to the outside temperature, or to the amount of humidity in air, their loudness intensity varies according to the care activity as well as to the cosmological events. Periods of days and seasons are also marked by a variety of geophonic sounds such as rain and wind which vary according to the actual weather... On the biophonic side, animal populations and their audio activity also change according the actual season, weather and ethological data. In the same way, the biophonic production is in relation with the precise location of the broadcasting of sound: birds that might come -whether in reality or virtually -to the waterfall in the patio are not the same ones as those that can be heard in the little living room on the North side, neither are they the same as those that can be heard in the big living on the South side.

The time-length of the animal sound sequences is approximately twenty minutes long, depending on weather conditions. Their intensity and density, therefore the duration of silences, depend on season and weather. Thus different tones continuously blend while they « naturally » diversify, as the algorithm gives the sound of birds in the rain, that would be more often crows in winter and tits in spring. When the sonorous broadcasting through loudspeakers is allowed for by the layout, audio spatialization effects may be produced, with moderation, to render movements coming from the wind, trees, birds, mammals... Sounds that are distinctive to human activity, more variable are arbitrary, are broadcast in other (more infrequent) places of the common space. For example, in the area of the dining room sounds may suggest meal preparation. In this case, aiming at realism, and especially at respecting a multimodal congruence (here audition vs. taste), the choice of sound samles can, eventually, be made consistent with the menu, and the sound of a pressure cooker made become more frequent in winter than in spring: this implies, therefore, collaborating with cooks ! Author's preprint version, accepted in july 2019 for the 14th Intern. Symposium Computer Music Multidisciplinary Research. Extreme attention is given to the sound pressure intensity. I adapted the sound production with a rather unusual but conscious concern for the continuously exposed audience. Calibrated measures of acoustic pressure are underway.

In the common spaces, that are the noisiest, the acoustic pressure produced is unevenly distributed. Periods of silence (the acoustic pressure being of roughly 30 dBA) are frequent, except in the patio that overlooks the inner garden and its waterfall whose sound is continuous, though variable during long periods depending on time and weather conditions (minimum pressure of roughly 40 dBA). From the little living room on the north side, some sounds are broadcast loud enough to be heard as we arrive from the corridors that lead to it. In this more isolated place than the others, that leads to meditation or strolling, periods of silence alternate with active periods (with an acoustic pressure of 70 dBA and peaks at 80 dBA).

Until now, as is confirmed by the written notes taken by the care team, voiced complaints have never been about sound pressure, but rather about their eventual existence and pertinence. On the contrary, it even seems as if, with time, sounds tend to not be noticed consciously, at least by the health care workers. In agreement with the care team, the general sound pressure has even been reinforced with experimentation, in particular to compensate the eventual hearing deficiencies of the residents.

As recommended by music therapists [START_REF] Guétin | Effect of Music Therapy on Anxiety and Depression in Patients with Alzheimer's Type Dementia: Randomised, Controlled Study[END_REF], the general shape of a sound sequence, aside from the sound landmarks, for example the chirping of a bird, or horses passing, Author's preprint version, accepted in july 2019 for the 14th Intern. Symposium Computer Music Multidisciplinary Research.

etc. follows as much as is possible a U-shape for about 20', most often followed by a period of silence. Insofar as we offer to encourage mnesic recalling and, in order to achieve that, to resort to attention cognitive processes, we suggest also resorting to a form of ABA' shape in which the sound shape A would tend to ressemble a call. It can be noticed, as a matter of fact, that the U-shape, that can also change into an inverted "J", conjures up a kind of returning (if only that of an increasing tempo), like the ABA' shape.

Each broadcasting point being independent, several sequences can partly overlap in various places. The number of simultaneous voices in the same location remains, however, voluntarily limited so as not to saturate the sound space, without, for that matter, preventing more or less fortuitous sounds meeting. Silences also allow, depending on what sounds are conjured up by the context, various effects that can concern sometimes a feeling of expectation (calls), at other times relief (response), mirroring the shape of a rhythm.

When the soundscapes of the common spaces take their inspiration from an as common reality, the broadcasting of soundscapes in the private spaces (bedrooms) is much more personalized. The scripting strategies there are somewhat different since the idea is to conjure up the residents' old memories while avoiding to cause confusional states that would take place in particular moments that the care team would help define. The choice of sounds and their staging here has to answer the congruence with a reality perceived in a state of dementia -which needs to be diagnosed in the best possible way -as well as the life story of the listener. We also have to admit that such diagnoses are not often enough made, with regards the evolution of the disease. Different protocols, based on the above-mentioned principles, are being considered. Some simple and repetitive sounds, that conjure up a bygone past, may have a soothing effect: an initial observation, along with the care team, showed that the warm, slow and regular sound of a grandfather clock's pendulum, slowed down to an every-two-second impulse, seems to ease the sleeping phases and allow for a better sleep. Such observations are still, at this point of experimentation, to be confirmed experimentally: the rooms are in the process of being empirically and progressively fitted with sound. We hope that, in the long run, such an experimentation may enable to elaborate a precise questionnaire, based -for example -on a guided listening of sounds which are defined beforehand, that better allows to characterize each resident's sensitivity to different sounds.

This personnalized aspect of conception, the most delicate, is in the course of being experimented and will progressively be deployed.

Soundscapes for caregivers

Obviously, some sounds may be difficult to play with. In some conditions, with dementia, when the perception of some sounds imply, as a reflex, the viewing of their origin, their separation from their real or imaginary cause may create confusional states: to avoid such a case, the help of a caregiver is useful to explain the origin of such a sound, to calm the person down and to finally have -as expected -some conversation.

Author's preprint version, accepted in july 2019 for the 14th Intern. Symposium Computer Music Multidisciplinary Research.

Conceiving a sound environment and its dynamics, necessariy involves the health care team. Sound must not interfere with care, it must help and support it. We can therefore consider that sound may help the patient in directly adressing him or her while addressing the care team as well. With their assent and their complicity, oral conversations may be engaged in and sounds adopted.

For example, in the very first days following the beginning of the setup (in July 2018), nursing auxiliaries asked me for the new bells in the commons spaces never to leave: the opportunity and ergonomics of such a multi-functional sequence of a simple sound, repeated twice an hour (at 2' interval), 24 hours a day allows to mark a territory, to recall an hour common to all, to be the opportunity for a social exchange, and to become a training of different short-term memories, indeed to become part of spontaneous cognitive assessment, almost at any time. And slight periodic variations of the sound synthesis of bells can be sought for, for who might want it if only per chance. More or less shared knowledge, whether popular, personal or specialized, may be called upon on the subject of some animal sound production. Producing some insect sounds, or mammal ones, for example, has been the subject of discussions with the care team as regards their realism, the cridibility, or the emotional states they are likely to cause.

Soundification of virtual human activities may also take part in the organisation of care: for example, the sound accompanying meals may be realised in such a way that it more or less consciously prepares the residents to eat. This anticipation may be all the more appreciated as the residents themselves are incapable, because of their dementia, of knowing that it is in fact really time to eat... Such an effect is most certainly welcome when it contributes to the support of demented people in the absence of any other clue that would be obvious and familiar to them, in a hospital context.

The developpement of a closer feedback and control interface from the care team is contemplated. Conceiving such an interface would should directly integrate existing computer interfaces already devoted to caring. With that as a goal, research in psychosociology on the links between sonic environment and care has already began under the supervision of Prof. France Mourey. A first study of the effects of "Madeleines sonores" (the virtual soundscapes, the plan of action) on the relationship between caregivers and care receivers is based on collecting information during interviews with the various professionals linked with this project. The thematic analysis [START_REF] Negura | Content analysis in the study of social representations (L'analyse de contenu dans l'étude des représentations sociales)[END_REF] of the interviews that were carried out have allowed to establish one (or more) questionnaire(s) that may characterize the representations and attitudes that the care team takes up faced with the sound plan of action2 . We are considering that the use of such a questionnaire may allow to know the attitudes that come into play while applying the sound plan of action, this being to clarify the contribution in relation with the resident. Moreover, knowing how the care team sees this sound plan of action also partakes in evaluating its effects, in terms of contribution or benefits, with the residents.

Author's preprint version, accepted in july 2019 for the 14th Intern. Symposium Computer Music Multidisciplinary Research.

database with thousands of items indexed by myself. Periods of silence between sound samples or synthesizers are more or less short and always irregular. They define the density of virtual events that occur depending on each resident's sensitivity and the general context: according to daytime periods, the year, the care provided, etc. In the individual rooms, the soundscapes are rendered using two equivalent monophonic loudspeakers placed across the room, one close to the window and the other facing the bed. The activation of the soundscapes entirely depends on the explicit approval of whom concerned: the individual, himself, herself or their family when he or she cannot agree for clinical reasons and, obviously, by the caring team (doctors, psychologists, nurses).

All hi-level instructions, play-lists, sound filenames, pressure levels, etc are systematically locally logged. The overall disposal can be remotely controled and monitored thru a standard secured connection (SSH) on internet, using any Unix-like terminal. Confidentiality is ensured in particular by the entire anonymity of the digitized data.

Discussion

The work presented here is only the beginning of a long conceiving process in an emerging activity within the field of sound design, mental health and care. Its actual state is an action-research led in the fields of sound art, human and health science, and technology.

Our first observations are encouraging: the behaviour of part of the residents suggest that not only the residents appreciate the variety of the new sound environment but they tend to place themselves close to the audio sources to recollect or to meditate, whether consciously or not (see Fig. 3 below). The questionnaire we developed should make it possible to make care givers aware of the effects of sound environment on AD victims.

After such a first research that was necessarily empirical, considering the innovative characteristic of the project, applications respecting a truly experimental protocol have to be considered.

Optimizing the algorithms that was developped for that purpose still has to be done, as the deployment of the plan of action is being ratified. Particular attention should be focused onto indexing the sound samples insofar as they should enable, not only to identify the origin, the nature and the quality of sounds, but also, beyond their psycho-accoustic properties, the emotions and reactions they are liable to cause, as well as the broadcasting methods (context). In fact, we are contemplating the fact that, ultimately, the care team may report the reactions they provoke thanks to an interface that remains to be created. Such an interface would then enable to directly partake in the experimental phase of the plan.

The whole plan of action is for the moment operating as a multimedia work of art (sound and computer) that falls within the altogether artistic, scientific and clinical perspective that federates different social and economic players in a humanistic dynamic of research and innovation.

Thanks

I am particularly thankful to Dr Pierre Jeannin for his benevolence, his logistic and voluntary support, and of course to the charity Castel-Mailletaise that welcomed this project, and the care team that is closely involved in it. My thanks also go towards France Mourey for her support. And I am grateful to Claire Webster for emending and translating parts of this article.

  Author's preprint version, accepted in july 2019 for the 14th Intern. Symposium Computer Music Multidisciplinary Research.

Figure 1 .

 1 Figure1. Layout of the loudspeakers in the common spaces of the Alzheimer's Unit: 1) the broadcasting points of the landmarks: bells and waterfalls (black circles), can also play geophonic and biophonic sequences ; 2) the broadcasting points of sounds for geophony or biophony and occasional human sonic activities from outside (grey circles) ; and 3) the broadcasting points of human audio activities, mostly from inside (dashed circles). The bedrooms have two broadcasting points each (smaller empty circles) : only six of them are shown on this map.

  Author's preprint version, accepted in july 2019 for the 14th Intern. Symposium Computer Music Multidisciplinary Research.

Figure 3 .

 3 Figure 3. A resident is meditating at the closest place to the audio source mounted at the ceiling.

Gerontologist, at Cognition, Action and Sensorimotor Plasticity Lab., UMR Inserm Unit 1093 -Université de Bourgogne, Dijon (France).

I would like to thank Arnaud Bidotti, Master in Occupational and Organizational Psychology who led this study in March and April 2019 under the scientific supervision of Prof. Edith Salès-Wuillement, Laboratoire Psy-DREPI EA-7458 (Psychologie: Dynamiques Relationnelles et Processus Identitaires), Université de Bourgogne.

Cf. cron programs in Unix-like operating systems (see: https://en.wikipedia.org/wiki/Cron ).

All computers operating systems are GNU-Linux based. The on-board ARM based computers are Raspberry Pi3-B+ with audio boards IQaudio Pi-DigiAMP+ and in-ceiling 6.5'' loudspeakers QI 65C/St by QAcoustics (70 Hz to 16 kHz ± 3 dB, up to 90 dBA max pressure level). The DSP is built using Pure Data open-source software[START_REF] Puckette | Pure Data[END_REF]. The communications are based on TCP/IP protocols: secure-shell (SSH) for asynchronous sound transferts, UDP for real-time controls.

Author's preprint version, accepted in july 2019 for the 14th Intern. Symposium Computer Music Multidisciplinary Research.

A Digital Architecture for Virtual Soundscapes

The soundscapes are systematically generated and mixed in real-time using a distributed architecture with a principal generator (see the « Soundscape Generator », in Figure 2 below) that can be described as a server hosting the sound database and a set of routines periodically executed by its operating system scheduler 3 . These routines, written in Lisp language and Unix-like shell scripts, compute different kinds of mapping, empirically developped, relevant to the environmental data as modelised, to its inner virtual population and to individual data (biographies). They finally control 24 on-board computers 4 fixed in the ceiling of the common and private spaces and hosting their own digital signal processing (DSP) and loudspeakers (the « Players », in Figure 2). All the soundscapes are generated as a remix of short sound samples (lasting from a few seconds to a few dozens of seconds), or using sound synthesizers models adapted from my own experience [START_REF]Author's website[END_REF] and from [START_REF] Farnell | Designing Sound[END_REF]


Alexis Godart

Hervé Manier

Christelle Bloch

Marie-Ange Manier

MILP for a variant of Pickup & Delivery Problem for both passengers and goods transportation*

Pickup and delivery problems have been declined in many variants. In these optimization problems, a fleet of vehicles must satisfy customers' transport demand under specific constraints. This paper studies the feasibility of using a linear model including constraints that are not only related to the goods transport, but also combined with passengers transport in a more flexible way. We explore many characteristics simultaneously like transfers capabilities (with and without storage), time windows on sites, on transfer points and on vehicle depots, heterogeneous capacities and multiple visits. We use exact methods on some instances we created, using commercial solver IBM CPLEX TM . Results obtained show potential savings on two instances but also highlight the complexity and limits in terms of scalability.

I. INTRODUCTION

Over last decades, transport demand has been quickly growing around the world. These growths are especially located in cities that keep spreading. They have many consequences, already well-known, such as increased costs and environmental impacts. In most countries, stakeholders and governments have worked together to avoid such negative externalities without preventing the economical growth and social improvements. A fundamental factor is the optimization of transport and its infrastructure in urban areas [START_REF] Flores | Urban transport infrastructure: A state of the art[END_REF]. Among the existing socio-economic studies dealing with urban transport, those conducted by Dacko [6] and Spikermann [START_REF] Spickermann | Heading towards a multimodal city of the future? Multi-stakeholder scenarios for urban mobility[END_REF] highlight the expected benefits for all stakeholders in changing the urban mobility model. This would be made by promoting intermodal travel behavior, and require transport providers working together to offer multimodal mobility services. This collaboration implies pooling of transport infrastructures and resources. The proposed approach considers both passengers mobility and goods mobility into a single urban logistics system. The next section expose the related state of the art in operational research.

II. LITERATURE REVIEW

An efficient logistics system within urban environment implies a reasonable quality of service into an environment with low available space, shared infrastructures and a limited budget, keeping in mind that urban congestion can also be a significant source of delay, noise pollution and high-level gas emissions. There have been lots of studies and research in recent years dedicated to the optimization of logistics problem, sometimes considering several characteristics independently. Problems in which a set of vehicles is used to fulfill transportation requests are called Vehicle Routing Problem (VRP), as introduced by Dantzig [START_REF] Dantzig | The Truck Dispatching Problem[END_REF] in 1959. Pickup and Delivery Problems (PDP), also known as the Vehicle Routing Problem with Pickup and Delivery (VRPPD) have been surveyed and discussed by Savelsbergh [START_REF] Savelsbergh | The general pickup and delivery problem[END_REF] and more recently by Berbeglia in both static [START_REF] Berbeglia | Static Pickup and Delivery Problems: A Classification Scheme and Survey[END_REF] and dynamic [START_REF] Berbeglia | Dynamic Pickup and Delivery Problem[END_REF] context, within a general framework. In PDP, objects or people are moved between origins and destinations. These moves are made thanks to a fleet of homogeneous or heterogeneous vehicles. According to Cordeau [START_REF] Cordeau | The dial-a-ride problem: models and algorithms[END_REF] Dial-A-Ride Problems (DARP) can be considered as Pickup and Delivery Problems (PDP) in which origins and destinations for each demand are known beforehand. Additionally, DARP are problems that better fit for people transportation because of narrow time windows and objectives aiming better quality of services rather than cost reduction. The transport request is expressed with one-to-one relation where each demand has a single origin point and a single destination point.

In the following subsections we review some papers dealing with some variants of PDP including (but not limited to) time windows and transfers with characteristics such as heterogeneous fleet of vehicles, multiple depots or also multiple echelons. Our state of the art focuses on both static and dynamic problems with deterministic environment, integrating interesting features for the urban context.

Pickup and Delivery Problems with Time Tindows (PDPTW) are specific PDP problems with temporal constraints over sites, vehicles, demands and/or interactions between those. [START_REF] Dumas | The pickup and delivery problem with time windows[END_REF] present in 1991 a general framework and they exactly solve the problem using a column generation. [START_REF] Ropke | Models and a Branch-and-Cut Algorithm for Pickup and Delivery Problems with Time Windows[END_REF] introduce a new formulation of general PDPTW. They tackle it with branch-and-cut algorithms and adding valid inequalities. They solve instances with 96 requests, 194 nodes and 8 vehicles to the optimality. One variant studied by [START_REF] Lin | A vehicle routing problem with pickup and delivery time windows, and coordination of transportable resources[END_REF] deals with coordination of heavy and light resources to save time and reduce global cost. This problem was solved with a two-staged heuristics. Initial solutions are first created. They are improved using ejection chains, and then an assignment stage with light resources is used until an optimal assignment. Multi-objective PDPTW has also been treated [START_REF] Grandinetti | The Multiobjective Multi-vehicle Pickup and Delivery Problem with Time Windows[END_REF]. These authors solve a problem with several vehicles and three objectives (total travel cost, makespan, number of vehicles used) using an approximate -constraint solution to create the efficient Pareto fronts.

Nowadays PDP and DARP most often involve several vehicles. Benefits of transfer operations are intuitively guessed over cost reduction and distance savings. PDP with transfers (PDPT) was studied by [START_REF] Cortés | The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method[END_REF] who propose general formulation for the static variant. An extra binary variable z keeps track of the exact position of requests. A branch-and-cut method using Benders decomposition is proposed. [START_REF] Bouros | Dynamic pickup and delivery with transfers[END_REF] formulate a dynamic PDPT involving additional demands arriving at arbitrary times. Given solutions use a shortest path algorithm on a dynamic graph, on instances with 200 to 2000 requests.

Regarding transfer operations arising in DARP (DARPT), [START_REF] Masson | The dial-a-ride problem with transfers[END_REF] present a general formulation and an adaptive large neighborhood search method. The results prove savings due to transfers while minimizing the total distance traveled. [START_REF] Deleplanque | Dial-a-ride problem with time windows, transshipments, and dynamic transfer points[END_REF] solve DARP with dynamic transfer points using insertion techniques and constraints propagation.

III. MATHEMATICAL FORMULATION A. Characteristics and assumptions

A fleet of vehicles V with heterogeneous capacity Q v is considered. Vehicles are either dedicated to the mobility of passengers or to the mobility of goods. Vehicles have heterogeneous speed v v equal to the mean velocity while visiting nodes through edges, and an associated depot w v , from which each vehicle begins and ends its trip. Each vehicle can only do one trip per period.

The graph G = (N, E) contains 3 sets of nodes, organized as follows. The set W of vehicle depots dedicated to host empty vehicles. The set Ω of Origin/Destination sites expresses origins and destinations for transportation requests. Each site can be origin and destination as it can be involved in more than one request. Neither vehicle depots nor sites have storage capacity. The set T of transfers points with a storage capacity sc t . This capacity is only considered for vehicles transporting goods. It can not be expressed for passengers. Indeed, in urban context, infrastructures are assumed to be large enough for welcoming as many passengers as needed at any time, on any node. Storage capacity can be fixed to zero, to imply no storage at all. Then the transfer point requires both vehicles to meet during a same time window. This induces some precedence and synchronization constraints, which are discussed later in this paper. Two sets T + and T -are created, resulting from the duplication of set T, representing respectively the incoming flow capture and outgoing flow capture at any transfer point t ∈ T.

Any node i has an opening time window, expressed by an earliest date e i and a latest date l i . Any loading/unloading operation must be realized within this time window [e i ; l i ]. The graph G is assumed to be complete, oriented and asymmetric. The set of edges E connects nodes in N = W ∪ Ω ∪ T ∪ T + ∪ T -. A subset N = N \ W contains all nodes except vehicle depots. A cost d ij is assigned to each edge. It corresponds to the shortest path between an origin node i ∈ N and a destination node j ∈ N such that i = j.

Finally, transport demands are stored in a set of known transportation requests R. For each request r ∈ R we know the origin node S + r , where request r will be picked up, and the destination node S - r where it will be dropped-off. A set B r lists vehicles that can handle r. The quantity q r is the number of entities moving from the origin to the destination. Service times for pickup δ + r and for drop-off δ - r are taken into account respectively for loading operations and unloading operations. r can be handled only within a time window [p + r ; p - r ] where p + r is the earliest date for the pickup at S + r , and p - r is the latest date for the drop-off at S - r . A vehicle can visit several times a same node within its trip.

The maximum number of visits θ i in an Origin/Destination site i ∈ Ω is equal to the number of occurrences where node i appears as origin S + r plus the number of occurrences where node i appears as destination S - r for all r ∈ R. The maximum number of visits in a transfer site t ∈ T by all vehicles v ∈ V is θ t .

B. Decision variables

x v ijab =        1 if vehicle v ∈ V is moving directly from i ∈ N on the visit number a ∈ {1, . . . , θ i } to j ∈ N on the visit number b ∈ {1, . . . , θ j }, 0 else. A v ijab : Arrival date of vehicle v ∈ V at node j ∈ N on visit number b ∈ {1, . . . , θ j } when coming from node i ∈ N on visit number a ∈ {1, . . . , θ i }. D v ijab :
Departure date of vehicle v ∈ V at node i ∈ N on visit number a ∈ {1, . . . , θ i } when going to node j ∈ N on visit number b ∈ {1, . . . , θ j }.

z rv ijab =        1 if vehicle v ∈ V is handling request r ∈ R from i ∈ N on the visit number a ∈ {1, . . . , θ i } to j ∈ N on the visit number b ∈ {1, . . . , θ j }, 0 else. τ rvv ta =            1 if request r ∈ R is transfered with storage operation from vehicle v ∈ V to vehicle v ∈ V | v = v while v is leaving transfer node t ∈ T on visit a ∈ {1, . . . , θ t }, 0 else.
Decision variables A v ijab and D v ijab are both defined in R + . Binary variable z rv ijab allows us to track requests independently of the transport modes being used. Requests are tracked on edges. We denote M a big number, used to linearize some constraints.

C. Transfer operations

Any request can be transferred from one vehicle to another if there is at least one transfer point available. These transfer operations can take place under two major conditions. First, the transfer point must be available so vehicles can operate on it within its opening time window. Second, operations must take place respecting all time constraints. Hence we define two kinds of transfer operations we consider along this paper : transfer with storage and transfer without storage. Storage isn't considered in the context of passengers transportation.

On one hand, transfers can be accomplished with storage, and time constraint applied is only a precedence constraint between two vehicles and their drop-off and pickup operations. On the other hand, transferring without storage implies a synchronization constraint. Both vehicles must be at the same transfer node within a common time window, and this time window must be at least wide enough to realize their respective operations.

In both cases (for passengers and for goods), requests are not necessarily transferred, and therefore the unload time is only the sum of service times of requests being transferred.

Transfer points are duplicated twice (fig. 1 & 2), so we can separate incoming flow from outgoing flow. Since decision variable z tracks requests on edges, pickup and drop-off operations are executed by switching the binary value z between two edges.

(x v ijab * d ij ) (1)
The problem stated is solved with mono-objective function. The criteria is to minimize the overall distance traveled by vehicles (1). z rv ijab = 1 ∀r ∈ R; j = S - r ; i = j (3)

E. Constraints

x v ijab * M ≥ r∈R z rv ijab ∀i, j ∈ N ; ∀v ∈ V ∀a ∈ {1, . . . , θ i }; ∀b ∈ {1, . . . , θ j } (4)
We choose here to deal with the non-selective variant of PDPTW, meaning that all requests must be honored. The variable z is used to track requests during transportation, and constraints ( 2) and ( 3) force the request r to be picked up from the origin node S + r and to be dropped-off at the destination node S - r , regardless of the vehicle v ∈ B r being used.

As mentioned in 3.2, we use decision variable x to track the route described by each vehicle. Constraint (4) ensures that if the request r is handled by vehicle v when going from node i on visit number a to node j on visit number b (i.e. when z rv ijab = 1) then this vehicle had to move on that edge the exact same way.

x v hj1b = i∈N θi a=1 x v iha2 ∀v ∈ V ; h = w v (7)
Constraint ( 5) allows vehicles to be used or not. We ensure with constraint (6) that each vehicle has to leave its associated vehicle depot if and only if this vehicle is being used anywhere in the graph, while constraint [START_REF] Dantzig | The Truck Dispatching Problem[END_REF] forces this same vehicle to finish his route at this same vehicle depot. A vehicle v or a request r on node i must only pass through one edge [i, j] for each visit number a to ensure one unique flow for vehicles [START_REF] Deleplanque | Dial-a-ride problem with time windows, transshipments, and dynamic transfer points[END_REF] and for requests [START_REF] Dumas | The pickup and delivery problem with time windows[END_REF] departing from any node. Any given request can only enter once at most in each transfer point [START_REF] Flores | Urban transport infrastructure: A state of the art[END_REF].

j∈N θj b=1 x v ijab ≤ 1 ∀i ∈ N ; ∀v ∈ V ; ∀a ∈ {1, . . . , θ i } (8) j∈N θj b=1 z rv ijab ≤ 1 ∀r ∈ R; ∀i ∈ N ∀v ∈ B r ; ∀a ∈ {1, . . . , θ i } (9)
j∈N |j =i θj b=1 x v ija b ≤ j∈N |j =i θj b=1 x v ijab ∀v ∈ V ∀i ∈ Ω ∪ T + ∪ T -; ∀a ∈ {1, . . . , θ i -1}; a = a + 1 (11)
v∈V j∈N θj b=1

x v t ja b ≤ v∈V j∈N θj b=1 x v t jab ∀j ∈ W ∪ Ω ∀t ∈ T ; ∀a ∈ {1, . . . , θ t -1}; t = t + 2 • |T |; a = a + 1 (12)
Constraints ( 11) and ( 12) ensure that any solution must use lowest visit index order while visiting an origin/destination site or a transfer point.

h∈N |h =i θ h a=1 x v hiab = j∈N |j =i θj c=1 x v ijbc ∀v ∈ V ∀b ∈ {1, . . . , θ i }; ∀i ∈ N (13)
h∈Ω∪T -|h =i Route continuity for vehicles is defined by constraint (13) which ensures that any vehicle arriving on any site (except vehicle depots) will leave for the next destination. Requests r ∈ R do need the same flow conservation [START_REF] Ropke | Models and a Branch-and-Cut Algorithm for Pickup and Delivery Problems with Time Windows[END_REF] but only on Ω sites. However note that origin node S + r and destination node S - r are excluded since physical flow must be interrupted to make pickup and drop-off operations happen. Any request r ∈ R entering a transfer point must leave it, no matter which vehicle is transporting it [START_REF] Savelsbergh | The general pickup and delivery problem[END_REF]. Thereby, transfer operations can be achieved for one or more requests when vehicles are visiting a transfer point. Equations ( 16) and (17) allow respectively pickup and drop-off operations only on the incoming transfer node and the outgoing transfer node (see fig. 2 18) and ( 19) associate exactly one vehicle at maximum to one visit index. Thus for any transfer point t ∈ T, the maximum number of visits θ t concern all vehicles, and not per vehicle. These two constraints are used to ensure that temporal constraints on transfer points are valid (eg. precedence, operations order between two vehicles during a transfer...).

θ h a=1 z rv hiab = j∈Ω∪T + ∪T |j =i θj c=1 z rv ijbc ∀r ∈ R; v ∈ V ; b ∈ {1, . . . , θ i }; ∀i ∈ N (14
θj b=1 D v ij1b ≥ e i * θj b=1 x v ij1b ∀v ∈ V ; i = w v ; ∀j ∈ N \ {i} (20) θ h a=1 A v hia2 ≤ l i * θ h a=1 x v hia2 ∀v ∈ V ; i = w v ; ∀h ∈ N \ {i} (21) A v ijab ≥ D v ijab + x v ijab * d ij /v v ∀i ∈ N ; ∀j ∈ N | i = j ∀a ∈ {1, . . . , θ i }; ∀b ∈ {1, . . . , θ j }; ∀v ∈ V (22)
Vehicles v ∈ V are allowed to leave their associated depot w v only after the earliest date e wv (20) and must return in it before the latest date l wv (21). Temporal continuity between 2 nodes is ensured with constraint (22) considering average speed v v and distance between i and j called d ij .

j∈N \T -|j =i θj c=1 D v ijbc ≥ h∈N \{T ∪T + }|h =i θ h a=1 A v hiab + r∈R|S + r =i (δ + r * j∈N \T -|j =i θj c=1 z rv ijbc ) + r ∈R|S - r =i (δ - r * h∈N \{T ∪T + }|h =i θ h a=1 z r v hiab ) ∀i ∈ Ω ∪ T + ; b ∈ {1, . . . , θ i }; ∀v ∈ V (23) θt c=1 D v tt bc ≥ θt a=1 A v t tab + r∈R (σ - r ( θt a=1 z rv t tab - θt c=1 z rv tt bc )) ∀t ∈ T ; ∀b ∈ {1, . . . , θ t }; v ∈ V ; t = t + |T |; t = t + 2 • |T | (24) j∈N |j =t θj c=1 D v t jbc ≥ θt a=1 A v tt ab + r∈R (σ + r ( j∈N |j =t θj c=1 z rv t jbc - θt a=1 z rv tt ab )) ∀v ∈ V ∀t ∈ T ; ∀b ∈ {1, . . . , θ t }; t = t + |T |; t = t + 2 • |T | (25)
Temporal continuity on nodes is conditioned by taking into account pickup and drop-off operations on origin/destination nodes in Ω (23) but also on incoming transfer points in T + (24) and outgoing transfer points in T -(25). If multiple loading/unloading operations begin at the same time we consider the sum of all service times, and vehicles are free to move once all operations performed.

A v ijab ≤ x v ijab * M ∀i ∈ N ; ∀j ∈ N | j = i ∀a ∈ {1, . . . , θ i }; ∀b ∈ {1, . . . , θ j }; ∀v ∈ V (26)
D v ijab ≤ x v ijab * M ∀i ∈ N ; ∀j ∈ N | j = i ∀a ∈ {1, . . . , θ i }; ∀b ∈ {1, . . . , θ j }; ∀v ∈ V (27) j∈N |j =i θj b=1 D v ijab ≤ j∈N |j =i θj b=1 D v ija b +M (1 - j∈N |j =i θj b=1 x v ija b ) ∀i ∈ N \ T ; ∀a ∈ {1, . . . , θ i -1}; a = a + 1; ∀v ∈ V (28) v∈V θj b=1 D v t tab + M (1 - v∈V θj b=1 x v t tab ) ≤ v∈V θj b=1 D v t ta b + M (1 - v∈V θj b=1 x v t ta b ) ∀t ∈ T ; ∀a ∈ {1, . . . , θ t -1}; a = a + 1 (29)
Constraints (26-27) enforce null values for arrival date A and departure date D when vehicle isn't passing on that edge. For all origin/destination sites in Ω and any vehicle v ∈ V, visit order is sorted chronologically thanks to equation (28). Same constraint is applied on transfer points in T but regardless of vehicles (one visit corresponds to one vehicle at most)

r∈R j∈N |j =i θj c=1 (z rv ijbc * q r ) ≤ Q v ∀i ∈ N ∀b ∈ {1, . . . , θ i }; ∀v ∈ V (30)
Capacity constraint (30) allows vehicles to welcome a limited amount of entities on board at any time, corresponding to the defined capacity Q v .

h∈N |h =i θ h a=1 A v hiab ≥ e i * h∈N |h =i θ h a=1 x v hiab ∀i ∈ Ω v ∈ V ; ∀b ∈ {1, . . . , θ i } (31) j∈N |j =i θj c=1 D v ijbc ≤ l i ∀i ∈ Ω ∀v ∈ V ; ∀b ∈ {1, . . . , θ i } (32) h∈N |h =t θ h a=1 A v ht ab ≥ e t * h∈N |h =t x v ht ab ∀t ∈ T ; t = t + |T |; ∀v ∈ V ; ∀b ∈ {1, . . . , θ t } (33)
j∈N |j =t θj c=1 D v t jbc ≤ l t ∀t ∈ T ; t = t + 2 • |T |; ∀v ∈ V ; ∀b ∈ {1, . . . , θ t } (34) j∈N |j =i θj b=1 D v ijab -δ + r + M (1 - j∈N |j =i θj b=1 z rv ijab ) ≥ p + r ∀r ∈ R; ∀v ∈ V ; ∀a ∈ {1, . . . , θ i }; i = S + r ( 35
) j∈N |j =i θj c=1 D v ijbc -δ - r -M (1 - h∈N |h =i θ h a=1 z rv hiab ) ≤ p - r ∀r ∈ R; ∀v ∈ V ; ∀b ∈ {1, . . . , θ i }; i = S - r (36)
Constraints (31-32) apply on all vehicles so any visit matches time windows [e i ; l i ] on any origin/destination site i ∈ Ω. Constraints (33-34) are also time window constraints arising for transfer points t ∈ T, such all vehicles can only visit them during time window [e t ; l t ]. Finally, requests r ∈ R can only be handled within a specific time window [p + r ; p - r ] on origin node S + r and destination node S - r (35-36).

Transfers operations have been discussed earlier in this paper, and two situations have been presented. In both cases, precedence constraint (37) must always be applied so vehicle v ∈ V and v ∈ V can exchange one request r ∈ R, including service time δ + r needed to exchange it. However if there is no storage, another temporal constraint has to be applied : synchronization constraint (38). Both vehicles are sharing a common time window so requests can be transshipped from on vehicle to another. In the other case where storage arises, constraint (39) ensures the respect of storage capacity at any visit (since one visit correspond to one vehicle at most, visiting the transfer point).

IV. COMPUTATIONAL RESULTS

Problem formulation implies to create new instances as no similar ones have been found in literature to our knowledge. 4 initial fictive instances were created (F00-F03). Each instance is studied in the case with no transfer operation, in the case with transfer operation without storage and in the case with transfer and storage allowed. Finally these 3 new instances are studied in both mono-visit and multi-visit cases. Given results (fig. 3) are obtained with exact methods using IBM Cplex TM solver on a Xeon E7-4850 @ 2.4 GHz with 16 cores and 32 threads.

As expected instances are solved widely faster considering mono-visit over multi-visit, and faster without transfer operations allowed. In mono-visit, saving for instance F01 obtained by allowing transfers without storage is 1.6% and raise to 3.7% with storage. Allowing several visits for each vehicle leads to 12.7% of saving which is significant for this size of instance. Saving for F02 is only 1.2% and is obtained by whether allowing transfer operations with Numeric results obtained are shown in (fig. 3) and prove that this instance can be solved in mono-visit only if transfer operations with storage are allowed (solution in fig. 5). Fig. 5. F00 solved with mono-visit and transfer with storage allowed However, better solution can be found if a vehicle can visit one site multiple times (multi-visit) and for this instance saving appeared to be almost 5% (solution in fig. 6). However, one can safely speculate about narrow relations between requests density and distribution among origin/destination sites, the number of vehicles being available (time window and load on board), and savings that can be made using multi-visit. Another speculation is about savings made by allowing transfer operations. In the case of 2 vehicles that are willing to proceed a transshipment, one first observation is towards their respective time windows. Indeed, if both vehicles are sharing a common time window (i.e. joint time windows) then transfer operation will more likely happen with synchronization and so without storage. One major interest in this particular case would be to allow storage because vehicle being transshipped could have a temporary lack of free space at the date considered. The other observation concerns the case where both vehicles aren't sharing a common time window (i.e. disjointed time windows). Vehicles will most likely transship request if there is a transfer point with storage capacity and of course free space in it, for the complete duration of storage. V. CONCLUSION In this paper, a general formulation has been developed to answer new urban mobility challenges, considering both goods and passengers viewpoints. This variant of PDP with time windows includes transfer operations with and without storage, vehicles are allowed to visit one site several times, and it ensures that vehicles must visit sites and transfer points within defined time windows. Computational results show potential savings on some instances but also show complexity and limits in terms of scalability. We can observe that using transfer points does not always improve the objective function. Indeed, the location of these points can strongly impact the quality of the solutions. The next step in our work will be to develop rules that will determine the number of transfer points and their position. Solving large examples is very difficult with this model, but is still a starting point for defining metaheuristics to solve this PDP variant.

Fig. 1 . 2 Fig. 2 .

 122 Fig. 1. Abstracted physical flow of a request being transferred from vehicle 1 to vehicle 2

  ∀r ∈ R; i = S + r ; j = i (2)

≤ 1

 1 ∀r ∈ R; ∀t ∈ T ; t = t + |T |[START_REF] Flores | Urban transport infrastructure: A state of the art[END_REF]

  ∀v ∈ V ; ∀v ∈ V ; ∀r ∈ R; ∀t ∈ T ; t = t + |T | t = t + 2 • |T |; ∀a ∈ {1, . . . , θ t }; ∀a ∈ {1, . . . , θ t } tab ) -M * τ rvv tb ∀r ∈ R; ∀v ∈ B r ; ∀v ∈ B r ; ∀t ∈ T ; t = t + |T | t = t + 2 • |T |; ∀a ∈ {1, . . . , θ t }; ∀b ∈ {1, . . . , θ t } (38)r∈R v∈Br v ∈Br (τ rvv ta * q r ) ≤ sc t ∀t ∈ T ; ∀a ∈ {1, . . . , θ t }

Fig. 3 . 6 Fig. 4 .

 364 Fig. 3. Computational results

Fig. 6 .

 6 Fig. 6. F00 solved with multi-visit and transfer without storage (same solution obtained with storage allowed)

  )

			θj
	v∈Br	z rv t taa = ∀a ∈ {1, . . . , θ (15) j∈N b=1 v∈Br z rv t jab ∀r ∈ R; ∀t ∈ T
		θt		θt
		z rv t tab -	z rv tt bc ≥ 0	∀r ∈ R; ∀t ∈ T
		a=1		c=1
	∀b ∈ {1, . . . , θ θt		θt
		z rv tt ab -		z rv t jbc ≥ 0	∀r ∈ R; ∀t ∈ T
	a=1	j∈N	c=1

t }; t = t + |T |; t = t + 2 • |T | t }; ∀v ∈ B r ; t = t + |T |; t = t + 2 • |T | (16) ∀b ∈ {1, . . . , θ t }; ∀v ∈ B r ; t = t + |T |; t = t + 2 • |T | (17)

  ).

		θt
		x v t tab ≤ 1 ∀t ∈ T ; ∀a ∈ {1, . . . , θ t }; t = t + |T |
	v∈V	b=1
		(18)
		θt
		x v tt ab ≤ 1 ∀t ∈ T ; ∀a ∈ {1, . . . , θ t }; t = t+2•|T |
	v∈V	b=1
		(19)
	Constraints (

*Mobilitech project funded by the region of Franche-Comté (CPER 2015-2020) and labeled by Pôle Véhicule du Futur


Joseph Azar
email: joseph.azar@univ-fcomte.fr

Abdallah Makhoul
email: abdallah.makhoul@univ-fcomte.fr

Mahmoud Barhamgi
email: mahmoud.barhamgi@univ-lyon1.fr

Raphael Couturier
email: raphael.couturier@univ-fcomte.fr

Raphaël Couturier

An energy efficient IoT data

Keywords: IoT, Edge computing, Data compression, Machine learning, Energy efficiency, Stress detection

Introduction

Cloud computing that is centrally deployed on a global scale has become an indispensable part of processing IoT data. However, cloud-assisted Internet of things (CoT) faces several difficulties such as transmission latency, bandwidth constraints, and high energy consumption. For instance, sending a single bit of data over the cellular network consumes a lot of energy which decreases the lifetime of the IoT system.

On the other hand, edge computing has emerged as a promising paradigm that pushes the cloud services to the edge of the network. It can be seen as a decentralized cloud that drives the computing power closer to the source of data and allows local decision making. Edge computing was shown to be a better solution than the cloud in numerous IoT applications [START_REF] Shi | Edge computing: Vision and challenges[END_REF]. For instance, applications that demand near real-time responses such as autonomous driving cars and eHealth can not work properly with the cloud due to the high latency and ineffective bandwidth caused by the large number of sensors connected to the network.

Wireless Sensor Networks (WSNs), Wireless Body Sensor Networks (WBSNs), and wearable devices make up the essential blocks of IoT architectures. Many of these smart objects, that are responsible for the collection, processing, and transmission of data, are still battery operated and resource constrained. The three major constituents of a smart object that consume energy are the microcontroller (MCU), transceiver, and sensor units. Among all tasks, it is well known that data transmission is the highest energy-consuming task in IoT nodes [START_REF] Anastasi | Energy conservation in wireless sensor networks: A survey[END_REF] [START_REF] Razzaque | Compression in wireless sensor networks: A survey and comparative evaluation[END_REF]. An important step towards energy efficiency in IoT applications is the transfer of computational tasks from the cloud to the edge. In general, the radio communication task between the IoT nodes and the edge consumes less energy than transmitting the data directly to the cloud over the cellular network [START_REF] Shi | Edge computing: Vision and challenges[END_REF] [START_REF] Miettinen | Energy efficiency of mobile clients in cloud computing[END_REF]. Equally important, reducing the amount of data to be transmitted to the edge can further increase the lifetime of the IoT nodes and save storage at the edge. In this paper, we consider the IoT network architecture shown in Figure 1, where the data are collected from smart objects such as wearables and sensor devices and sent periodically to an edge node using short range communication protocols (e.g. WiFi, Bluetooth). The edge node is responsible for the processing, analyzing, filtering, storing, and sending the data to the cloud. To start,

The energy conservation problem is tackled by proposing a fast error-bounded lossy data compression technique to be deployed on the IoT devices. The objective is to reduce the number of bits to be transmitted periodically to the edge node. Then, we study the effect of lossy compression on the performance of machine and deep learning models deployed at the edge, and trained on reconstructed data with degraded quality as compared to the original data. To do so, we consider the driving behavior monitoring use case where physiological signals are collected from drivers and sent to the edge node in order to detect their stress level. The stated problem in this work can be formulated as follow: Does the loss of information due to lossy compression and energy conservation techniques deployed on the IoT nodes affect the analysis and processing of the data at the edge?

The rest of the paper is organized as follows: Section 2 presents the work related to data analysis on the edge and data reduction in IoT applications. Section 3 explains the proposed compression scheme. Section 4 discusses the case studied in this paper and presents the prediction model deployed at the edge. Section 5 details the experimental results. Section 6 discusses and analyses the obtained results and section 7 concludes the paper.

Related Work

In this section, we first introduce the analysis of data in edge computing using machine and deep learning, and then we discuss data reduction in IoT applications.

Machine and deep learning in edge computing

The use of machine and deep learning techniques for data processing could help edge devices to be smarter, and improve privacy and bandwidth usage.

In [START_REF] Li | Learning iot in edge: Deep learning for the internet of things with edge computing[END_REF], the authors introduced deep learning for IoT into the edge computing environment and proposed an approach that optimizes network performance and increase user privacy. Machine and deep learning in edge computing can bring multiple improvements to the traditional approaches that rely on cloud computing by: • Processing data using conventional machine learning techniques and transferring the results or necessary features extracted from raw sensor data.

• Deploying part of deep learning networks layers on the edge and transferring the extracted features whose size is smaller than that of the input data.

• Deploying neural networks on the edge with minimized size that maintain accuracy.

• Training the networks on the cloud and shipping the trained models to the edge.

The aforementioned approaches reduce the pressure on the network by reducing the size of the data to be transferred to the cloud. For instance, each layer in a deep learning network processes and scales down the size of the generated features from the previous layer. The more layers are deployed on the edge, the smaller is the size of the features to be transferred to the cloud and the more they are incomprehensible, hence, increasing the privacy.

Edge nodes are devices such as mobile phones, IoT gateways, and local PCs that have a limited processing capability as compared to cloud servers.

The size of neural networks deployed on these devices should be reasonable.

In [START_REF] Varghese | Challenges and opportunities in edge computing[END_REF], the authors showed that different lightweight libraries and algorithms can be deployed on edge nodes such as smartphones and enable real-time data analytics.

Data reduction in IoT applications

Different data reduction schemes for energy saving in IoT applications have been proposed in the state of the art. In [START_REF] Laiymani | Adaptive data collection approach for periodic sensor networks[END_REF][8], the authors proposed data reduction approaches based on adaptive sampling. These approaches work by studying the level of variance between the collected data over a certain time frame, and dynamically adjusting the sampling frequency of the devices. Adaptive sampling approaches work well in applications where the collected time series are stationary. In the case of quickly varying data, these approaches perform poorly. In [START_REF] Tayeh | A distributed realtime data prediction and adaptive sensing approach for wireless sensor networks[END_REF], the authors proposed a data reduction mechanism based on dual prediction. The proposed mechanism works by building a model that describes the sensed phenomenon and deploying it on both the edge node and the IoT devices. The advantage of prediction approaches is that the model at the edge predicts the sensed measurement without requiring any radio communication unless the prediction error exceeds a predefined threshold. However, such prediction mechanisms suffer when it comes to devices like a high frequency motion sensor, where the data collection frequency is high and the data varies quickly.

Numerous aggregation and compression approaches that take advantage of the temporal correlation in the collected data have been proposed [START_REF] Harb | En-route data filtering technique for maximizing wireless sensor network lifetime[END_REF][START_REF] Alieksieiev | One approach of approximation for incoming data stream in iot based monitoring system[END_REF][START_REF] Azar | On the performance of resource-aware compression techniques for vital signs data in wireless body sensor networks[END_REF][START_REF] Azar | Using dwt lifting scheme for lossless data compression in wireless body sensor networks[END_REF][START_REF] Harb | A real-time massive data processing technique for densely distributed sensor networks[END_REF].

In [START_REF] Harb | En-route data filtering technique for maximizing wireless sensor network lifetime[END_REF], the authors proposed a data filtering technique based on the Pearson coefficient metric. This method works by recursively dividing the dataset into two equal parts and aggregating the data based on the correlation between the subsets. In [START_REF] Alieksieiev | One approach of approximation for incoming data stream in iot based monitoring system[END_REF], the author proposed a data aggregation method for incoming data stream in IoT based monitoring systems. The proposed method is an approximation with 'extremums' technique that reduces the volume of data to be stored or transmitted. The results show that this method was able to achieve a compression of up to 10 times on temperature data. In [START_REF] Azar | On the performance of resource-aware compression techniques for vital signs data in wireless body sensor networks[END_REF][START_REF] Azar | Using dwt lifting scheme for lossless data compression in wireless body sensor networks[END_REF] Compressive Sensing (CS) and transform domain compression techniques that are usually used for images have been proposed as well for multivariate time series compression in IoT applications. In [START_REF] Gaeta | Multisignal 1-d compression by ftransform for wireless sensor networks applications[END_REF], the authors proposed a multisignal compression technique based on the theory of fuzzy transform. The proposed method has been applied on multisignal environmental data collected by a wireless sensor network and reduced the data by approximately two times.

In [START_REF] Cheng | Lifting wavelet compression based data aggregation in big data wireless sensor networks[END_REF], the authors proposed the 2-D lifing wavelet transformation to compress multisignal data collected from different sensor nodes. The proposed method uses the Haar wavelet and achieves a compression ratio of 1.33 and recovery accuracy of 98.4%. Transform domain compression techniques are character-ized by the ability to recover the data accurately. However, the compressing performance of these techniques remains limited. On the other hand, CS theory has emerged as an efficient approach for energy-efficiency in IoT applications in recent years [START_REF] Deligiannakis | Compressing historical information in sensor networks[END_REF] [START_REF] Fragkiadakis | Adaptive compressive sensing for energy efficient smart objects in iot applications[END_REF]. By taking advantage of the signal sparsity, CS approaches assure an accurate signal recovery by sampling signals at a much lower rate than the traditional Shannon-Nyquist theorem. Nevertheless, CS techniques suffer when dealing with non-sparse multi-dimensional signals containing diverse features with different scales of values.

The major drawbacks of the above-mentioned propositions is that they yield low compression ratio on non-stationary multi-sensor data and they are not tested on real devices. This paper proposes a data compression technique for IoT applications and resource constrained devices that works efficiently on multivariate time series and implemented on a real wearable device. In the following sections, the proposed lossy compressor is presented and the impact of information loss on data analytics at the edge is studied.

Error-bounded lossy compression

In this paper, a lighweight version of the work presented in [START_REF] Di | Fast error-bounded lossy hpc data compression with sz[END_REF] is given. The authors in [START_REF] Di | Fast error-bounded lossy hpc data compression with sz[END_REF] proposed a fast error-bounded lossy compression scheme namely SZ for High Performance Computing (HPC) applications. This compression scheme has been proposed to deal with the huge amounts of data generated during the execution of HPC applications. The original SZ compresses input data files that are in binary format and can have different data shapes and data types (single-precision and double-precision). In this work, we propose to adapt the SZ algorithm for IoT devices by considering only the floating point data type and discarding the other types which make the code smaller in size and easier to compile on tiny devices. Moreover, the algorithm was adapted to take a 1-D array of float sensor data as input and return a byte array that is going to be transmitted to the edge node. The motivations behind choosing SZ for IoT applications are as follows:

• SZ allows the compression of multivariate time series containing diverse features with different scales

• SZ allows the control of information loss by using an error bound

• SZ leads to higher compression ratio than the multi-dimensional transform

domain compression techniques

The proposed compression scheme is defined in Algorithm 1. It is considered that the data are transmitted to the edge after each period P of time t. The collected data are in the form of M × N array, where M denotes the number of readings and N denotes the number of features. For example, consider a motion sensor that collected 128 gyroscope and accelerometer readings for the three coordinate axes after a period P . In that case, M is equal to 128, and N to 6.

To begin, the 2-D array is converted to the 1-D array (Algorithm 1, line 4).

Then, the flattened array is compressed using the lossy SZ technique. Finally, the resulted binary array is transmitted to the edge. Algorithm 2 presents the main steps employed by the adapted SZ compression scheme. Note that the adaptation has been done by extracting the necessary functionalities from the original SZ to make it fit on wearables and resource constrained devices.

Algorithm 1 Proposed compression scheme

Require: E (error bound) 1: while Energy > 0 AND Sensors status = ON do 2:

for each period do

3: data[M, N ] ← collected sensors data 4: input[M × N ] ← F latten(data) 5: bin output ← adapted SZ(input, E, M, N ) (Alg 2) 6:
transmit Data(bin output) For instance, if the value of a data point is considered to be X, an absolute error bound of 10 -1 means that the decompressed value should be in the range [X -10 -1 , X + 10 -1 ].

Case Study

The combination of IoT, cloud computing, and healthcare has taken a lot of attention during the past years. Among the major challenges that face the healthcare applications are:

• Latency due to communication between cloud and IoT devices

• Limited network bandwidth due to the high amount of generated data

• High cost of privacy and security breaches

Here is where the benefits of edge computing take place. As mentioned in previous sections, edge computing can be considered a major solution for latency and bandwidth challenges in IoT and healthcare applications. In a similar way, efficient on-node data compression can increase the lifetime of the application, and reduce the size and the number of transmitted packets which may affect the latency and network bandwidth positively. However, the integrity of the data and loss of information due to compression remain critical issues for healthcare applications. In this section, the impact of data compression and energy efficiency on the analysis of medical data at the edge is studied. Let us consider the case of driving behaviour monitoring and stress detection where the physiological signals are continuously collected from a driver and transmitted to the edge node for analysis and detection of stress level.

In the following, the dataset used in our work is described, then the processing and analysis of the data are discussed, and finally, the model used for stress level detection is presented.

Dataset

The Stress Recognition in Automobile Drivers database published on Phys-ioNet has been used in this work [20][21]. This dataset contains multiple physiological signals recorded from healthy volunteers, taken while they were driving on a specified route in and around Boston, Massachusetts. The driving task done by each driver varies from about 50 min to 1.5 h and can be divided into six sections as shown in Figure 2: • Rest [START_REF] Shi | Edge computing: Vision and challenges[END_REF][START_REF] Varghese | Challenges and opportunities in edge computing[END_REF]: The resting periods in the beginning of the driving task and at the end of it are labeled as "low stress"

• City [START_REF] Anastasi | Energy conservation in wireless sensor networks: A survey[END_REF][START_REF] Li | Learning iot in edge: Deep learning for the internet of things with edge computing[END_REF]: Driving in the city periods in sections 2 and 5 are labeled as "high stress" since the subjects drove in a busy main street and frequently handled the traffic conditions and the unexpected emergencies created by cyclists and jaywalkers

• Highway [START_REF] Razzaque | Compression in wireless sensor networks: A survey and comparative evaluation[END_REF][START_REF] Miettinen | Energy efficiency of mobile clients in cloud computing[END_REF]: Driving on the highway periods in sections 3 and 4 are labeled as "moderate stress" Note that the labeling of the data has been validated by drivers' self-reported questionnaires in [START_REF] Healey | Detecting stress during real-world driving tasks using physiological sensors[END_REF].

Data processing and analysis

For each driver data file, the noise has been removed from HR and GSR signals following [START_REF] Ollander | Wearable sensor data fusion for human stress estimation[END_REF]. In order to study the impact of data compression on the information contained in the data, a feature extraction phase is used from which time-domain and frequency-domain features are extracted from the ECG signal in addition to the two main components of the GSR signal namely: Skin Conductance Level (SCL), and Skin Conductance Response (SCR). The objective of this step is to compare the features extracted from the original data with the features extracted from the compressed data.

Table 1 describes the features extracted from the ECG signal by applying time and frequency domain analysis such as FIR-filters and fast fourier transform methods. In order to analyze the GSR signal, which can be considered The number of interval differences of successive RR intervals greater than 20 ms divided by the total number of RR intervals pNN50

The number of interval differences of successive RR intervals greater than 50 ms divided by the total number of RR intervals an important sensitive measure for emotional arousal, we extract the slow variation (SCL) and the faster alterations (SCR) following a convex optimization approach proposed in [START_REF] Greco | cvxeda: A convex optimization approach to electrodermal activity processing[END_REF]. Table 2 shows the features extracted from the GSR signal.

Stress detection using Feed-Forward Neural Network (FFNN)

This section considers the features shown in Tables 1 and2 in addition to heart rate (HR) and respiration rate (RR) as a single sequence in which a label is assigned. The prediction task is a supervised sequence classification task. A one input layer, one or more hidden layers, and one output layer.

Figure 3 shows the FFNN architecture used in the classification task. The neural network consists of 17 input neurons, corresponding to a sequence of 17 physiological features. Additionally, the neural network is provided with a correct label of that sequence. That is, whether the sequence corresponds to low stress, moderate stress, or high stress. Providing that edge analytics require lightweight algorithms to perform reasonable machine learning [START_REF] Varghese | Challenges and opportunities in edge computing[END_REF], we have used a network with a minimized size that maintains accuracy. The implemented network has four hidden layers consisting of 60 neurons, which use the ReLU activation function [START_REF] Nair | Rectified linear units improve restricted boltzmann machines[END_REF]. The number of layers The network was trained with a variant of stochastic gradient descent 'Adam' [START_REF] Kingma | A method for stochastic optimization[END_REF] and categorical cross entropy.

Furthermore, Dropout regularization technique [START_REF] Srivastava | Dropout: A simple way to prevent neural networks from overfitting[END_REF] has been used to prevent overfitting and 10-Fold Cross Validation has been used to validate and find the optimal set of hyperparameters for the model. Finally, the network has been trained for 300 epochs with a learning rate of 0.01.

Experimental Results and Analysis

In the following sections, the results of applying the aforementioned data compression technique on physiological data are presented. Two metrics are discussed in the following: data reduction, and the impact of information loss on the prediction accuracy.

Data reduction and energy conservation

The data sets and the signals were recorded from the drivers at 496 Hz.

In order to test the efficiency of the proposed compression scheme, we have deployed the data on the SD card of a Polar M600 wearable. In the same way, the compression technique written in C language using Android NDK toolset was implemented. After each period p = 1 min, an array data[M, N ] is transmitted using Android (Bluetooth Low Energy) BLE to the edge device, which is a local PC where the received data are processed and analyzed. The results are then transferred to the cloud. Note that M , the number of readings, is equal to 148800 and N , the number of features, is equal to 5.

The experimentation has been conducted for around 4 hours, equivalent to 241 periods. Figure 4 shows the difference between the amount of data transmitted with and without compression. The x-axis denotes the periods, and the y-axis denotes the number of bytes needed to represent the data in logarithmic scale.

The transmission of the original data after each periods requires around 2976000 bytes, while the number of bytes required for transmitting the compressed data varies between 28732 bytes and 41602 bytes. Thus, reducing the transmitted data by up to 103 times. • Black line: the wearable device is in the idle state

• Red line: the wearable device is continuously collecting data (motion and heart rate sensors are turned on)

• Yellow line: the wearable device is collecting data and running the compression algorithm after each period

• Green line: the wearable device is collecting data, and performing compression and transmission after each period

• Blue line: the wearable device is collecting data, and performing data transmission after each period (no compression)

The results clearly show the impact of data reduction on the communication task energy consumption. The battery level of the device continuously collecting data was decreased to around 86% after 241 periods. Note that by comparing the sensing and computation tasks with the idle state, it can be noticed that these tasks contribute a little in the energy consumption of the device. On the other hand, when applying the proposed data compression scheme prior to transmission, the battery level was decreased to 83% while sending the data without compression decreased the battery level to around 56%. As a result, the device lifetime could be increased by up to 27% after 4 hours.

Loss of information and stress detection

In this section, the impact of information loss on the prediction accuracy of the proposed FFNN for stress level detection is studied. For each of the drivers datasets, a sliding window of 30 seconds with 75% overlap on the data is applied, and the physiological features described in the previous section are extracted from each window. Note that for each window, the extracted features form a set/sequence labeled as low, moderate, or high stress that is going to be fed as an input to the neural network. though the compression has affected slightly the shape of the signal, the positions of the peaks that are used to exploit the signal and extract the most important features remain unchanged. Note that one of the advantages of the SZ algorithm is that the error bound is controllable and can be initialized according to the medical need. In other words, the trade off between compression ratio and loss of information can be easily controlled by the medical staff.

Table 3 shows the Root Mean Square Error (RMSE) between the features extracted from the compressed and original ECG and GSR signals for the 9 drivers. Notice that the average RMSE for each feature is small, and the important features such as heart rate, respiration rate, and R-R interval have a RMSE close to zero, which means that the compression had very low impact on the information loss.

In order to fully answer the stated problem in section 1, the sequences of features are randomly divided into train and test sets (75%/25%). Two models are considered, the first one was trained on the sequences of features extracted

Discussion

Most of the IoT devices nowadays are equipped with multiple sensors and are able to collect different types of data. Thus, the compression techniques must deal with multisensor readings at a single device. Furthermore, in the case of real-time or near real-time applications, the reconstruction (decompression) time of the algorithm must be small in order to pass the data to the machine learning model and return the prediction/classification results to the user in the shortest time possible. Although transform-based compression and compressed sensing (CS) can be used for dealing with multisensor readings, these methods have several disadvantages that make the choice of SZ for this type of problems is the best solution. Transform-based compression techniques transform raw data to a set of coefficients, and need to be followed by an entropy coding step to encode the coefficients in order to achieve an acceptable reduction rate.

On the other hand, CS requires that a signal is sparse in some domain and doesn't contain noise in order to achieve an "exact" reconstruction, which is not the case in real world applications. CS is also an asymmetric algorithm, which means that the decompression needs a higher computational complexity than that of the compression and longer time in order to recover the data, mak- Table 5 shows the time needed by the proposed SZ algorithm deployed on a wearable device (Polar M600) to compress and decompress different sizes of input multivariate data. It can be seen that the average compression/decompression time is small, thus making SZ suitable for near real-time applications. For the above-mentioned reasons, the proposed SZ can be a better candidate for multisensor readings compression not only for its fast compression/decompression and high compression rate, but also for its ability to adapt for different applications and scenarios.

ing

Conclusion

Since bringing intelligence closer to IoT devices reduces network latency and energy consumption due to radio communications, data reduction can be seen 20 as an additional solution to increase the lifetime of IoT devices. In this paper, an energy efficient data reduction scheme for IoT-Edge applications was proposed. The proposed scheme is based on an error-bounded lossy compressor designed for high performance computing applications that produce large amounts of data during the execution. The compression algorithm was adapted to fit on a Polar M600 wearable and its performance was tested on medical multivariate time series. The results showed that the we were able to reduce the amount of transmitted data to the edge device by up to 103 times and thus to increase the lifetime of the wearable. Furthermore, we considered the use case of drivers stress recognition and studied the impact of lossy data compression on the analysis, exploit, and classification of medical data. The results showed that the information extracted from compressed data was valid, and the classification accuracy obtained from training the model on features extracted from compressed data did not decrease.

Figure 1 :

 1 Figure 1: IoT network architecture

  scheme and the Differential Pulse Code Modulation (DPCM). The aforementioned data reduction techniques, in addition to many others proposed in the literature, perform well on stationary univariate time series. However, an important number of IoT devices nowadays include more than one sensor and are able to collect multiple features. Therefore, data reduction techniques that work efficiently on multivariate time series are required.

1 :

 1 end whileThe SZ compressor starts by compressing the 1-D array using adaptive curvefitting models. The bestfit step employs three prediction models: Preceding Neighbor Fitting (PNF), Linear-Curve Fitting (LCF), and Quadratic-Curve Fitting (QCF). The difference between the three models resides in the number of precursor data points required to fit the original value. The adopted model is the one that yields the closest approximation. Note that the fitted data are transformed into integer quantization factors and encoded using Huffman tree.In the case when none of the prediction models in the curve-fitting step satisfies the error bound, the data point is marked as unpredictable and is then encoded by analyzing the IEEE 754 binary representation. (Algorithm 2, line 2). Algorithm 2 Adapted SZ steps Require: input (1-D array), E (error bound),M (num rows),N (num columns) Ensure: output (binary array) Bestfit Curve-Fitting Compression 2: Compressing Unpredictable DataAs for the error bound, the absolute error bound has been used in which the compression/decompression errors are limited to be within an absolute error.

Figure 2 :

 2 Figure 2: Driving task

  Figure 3: FFNN

Figure 5 Figure 4 :

 54 Figure 5 describes the change of the wearable battery level over 241 periods for five different scenarios:

Figure 5 :

 5 Figure 5: Polar M600 battery level over 241 periods

Figure 6 :Figure 6

 66 Figure 6: 2500 original ECG samples vs compressed ECG samples

Table 1 :

 1 Features extracted from ECG signal

	Feature	Description
	RMSSD	Root mean square of the Inter-beat (RR) Intervals (the time
		intervals between consecutive heart beats)
	meanNN	Mean RR interval
	sdNN	Standard deviation RR interval
	cvNN	Coefficient of Variation (CV), i.e. the ratio of sdNN divided
		by meanNN
	CVSD	Coefficient of variation of successive differences, i.e. the
		RMSSD divided by meanNN
	medianNN	Median of the absolute values of the successive differences
		between the RR intervals
	madNN	Median Absolute Deviation (MAD) of the RR intervals
	mcvNN	Median-based Coefficient of Variation (MCV), i.e. the ratio
		of madNN divided by medianNN
	pNN20

Table 2 :

 2 Features extracted from GSR signal

	Feature	Description
	meanGSR Mean value of GSR signal
	meanSCL Mean value of SCL
	slopeSCL	Difference between max and min values of SCL
	meanSCR Mean value of SCR
	maxSCR	Max value of SCR
	FFNN is a network that contains a large number of neurons, arranged in layers:

Table 3 :

 3 Root mean square error between the features extracted from original data and the features extracted from reconstructed data from the original data and the second one on the sequences of features extracted from the compressed data. For hyperparameter optimization, 10-fold cross validation is performed on the training sets, and then our models are evaluated on the test sets. Table4summarizes the stress level detection performance of the aforementioned models. The results show that the average accuracy achieved by the two models is 98%. It can be noticed that not only the compression did not affect the prediction accuracy but even improved it in some cases such as for driver 7 and driver 12, which is due to the denoising capability of the compression technique.

			Accuracy
		Original Compressed
	Driver 4	1.0	0.99
	Driver 6	1.0	1.0
	Driver 7	0.97	0.98
	Driver 8	0.98	0.98
	Driver 9	0.98	0.97
	Driver 10 0.99	0.99
	Driver 11 0.92	0.94
	Driver 12 0.99	0.99
	Driver 16 0.99	0.98
	Average	0.98	0.98

Table 4 :

 4 FFNN prediction accuracy on test sets (25%) corresponding to sequences of features extracted from original and compressed data respectively

Table 5 :

 5 it inefficient for applications that require fast responses. Another issue for transform-based techniques and CS is adaptability. In other words, the compression algorithm must adapt and perform well across different applications, subjects, and activities. For instance, the multivariate time series used in this paper contains different variables having different statistical characteristics. So in order to apply CS to multivariate data, each of the variables contained in the data must meet the conditions needed by CS to work perfectly, which is not always the case. Average compression/decompression time for the SZ algorithm on different data sizes

	Data size (bytes) Compression time (seconds) Decompression time (seconds)
	11904000	0.036	0.05
	2976000	0.012	0.01
	992000	0.005	0.006
	99200	0.003	0.002

Acknowledgment

This work is partially funded by the EIPHI Graduate School (contract "ANR-17-EURE-0002")


François Courvoisier
email: francois.courvoisier@femto-st.fr

Ismail Ouadghiri Idrissi

Rémi Meyer

Jesus Del Hoyo

Chen Xie

Maxime Jacquot

Luc Froehly

Cyril Billet

Remo Giust

John Michaël Dudley

I Ouadghiri-Idrissi

J Del Hoyo

R Giustand

Filamentation of Bessel and Bessel-like beams in solids. Applications to materials processing

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The filamentation of ultrafast laser pulses inside dielectrics has recently raised tremendous interest because of a new technological application to high-speed dicing of glass. So-called "stealth dicing" is a two-step technique where the first consists in illuminating the glass workpiece with high intensity ultrafast laser pulses so as to create a plane with weakened material inside the bulk [START_REF] Meyer | Single-shot ultrafast laser processing of high-aspect-ratio nanochannels using elliptical Bessel beams[END_REF]. These allows in a second step, to cleave the material after a simple mechanical stress. This technique does not necessitate to ablate a great amount of material, which obviously is much faster than conventional laser-cutting techniques and reduces drastically the amount of unwanted debris. The typical cutting speed is around 1 m/s.

The important challenge to create the weakened plane inside glass is to control the energy deposition process along the propagation direction : this corresponds to the filamentation of the ultrafast laser pulse. In this field, Bessel beams have proven to be a very useful tool, when they can be generated in the stationary regime to homogeneously create a plasma channel. Here, we highlight several results of our recent work in this area. We demonstrate that spatial phase and amplitude shaping provides a high degree of freedom on the control of the propagation of ultrafast pulses inside dielectrics for material micro-and nano-structuring. We have investigated the regimes of generation of stationary Bessel filaments and generated other beam shapes that also create homogeneous plasma tracks with non-circular cross sections.

Control of Four wave mixing with longitudinally-shaped beams

Although femtosecond Bessel beams can sustain quasi-invariant regimes of filamentation, they can still suffer of significant modulation instability at high intensity and low cone angle. In this case, Kerr-related nonlinearities dominate the dynamics and the propagation is no longer stationary. The interference between the Bessel beam (k r0 ) and the new spectral components around k r ∼ 0 and ∼ √ 2k r0 generates oscillations of the on-axis intensity. This is obviously deleterious to control homogeneous energy deposition inside dielectrics [START_REF] Gaizauskas | Discrete damage traces from filamentation of Gauss-Bessel pulses[END_REF].

In this context, we have used the fact that Bessel beams can be shaped along the optical axis [START_REF] Ouadghiri-Idrissi | Arbitrary shaping of on-axis amplitude of femtosecond Bessel beams with a single phase-only spatial light modulator[END_REF]. Figure 1 compares the growth of new spectral components for different target on axis intensity profiles with identical peak intensity. The only difference between the profiles is the onset intensity rise. It is apparent that, in the Kerrnonlinear regime, the quadratic input profile (3) generates less FWM and therefore creates less on-axis oscillations. Detailed analysis shows that the reason of this behavior can be found in the spectral phase of the input beam. The amount of FWM can be ranked with the slope of the spectral phase, steeper slopes which correspond to a higher degree of dephasing between spectral components have lower FWM generation efficiency [START_REF] Ouadghiri-Idrissi | Controlling nonlinear instabilities in Bessel beams through longitudinal intensity shaping[END_REF]. Interestingly, these results are still valid in the filamentation regime when plasma generation is taken into account. Our results also help and clarify the smooth vs abrupt input transition observed when a Bessel-Gauss beam is launched in a nonlinear medium [START_REF] Polesana | Filamentation in Kerr media from pulsed Bessel beams[END_REF].

Novel stationary elliptical channels and multiple channel formation from spatially filtered Bessel beams

For sufficiently high cone angle (typ. above 15 • in dielectric medium), single shot illumination from high intensity Bessel beam yields the formation of a void inside glass, fused silica or sapphire. However, for a new applications to stealth dicing, nanochannels with non-circularly symmetric cross-sections would be desirable. In this context, we have investigated the propagation of new beam shapes based on the spatial filtering of Bessel beams [START_REF] Meyer | Single-shot ultrafast laser processing of high-aspect-ratio nanochannels using elliptical Bessel beams[END_REF]. An example is shown in Fig. 2 where a Bessel Gauss beam generated from an axicon is filtered in the Fourier plane of a lens. After Fourier transformation by a microscope objective, a Bessel-like beam is generated. It preserves the nondiffracting properties of the original Bessel beam while exhibiting a main lobe with an elliptical cross section. Single shot irradiation of glass with 2.8 ps pulse duration resulted in two interesting observations. First, at relatively low pulse energy, a nanochannel with elliptical cross section can be fabricated. Secondly, at higher energies, when side lobes intensity exceeds the plasma generation threshold, we observed the formation of three parallel channels separated by only ∼ 1 µm as can be seen in Fig. 2(b,c). This indicates that the propagation of the filtered Bessel beam, i.e. the elliptical Bessel beam, experienced a stationary propagation even at relatively high intensity. This technique opens new perspectives for the generation and control of multifilamentation inside transparent media.

Reconstruction of pulse propagation within solids

The comparison of experimental and numerical results is a key to adjust filamentation and plasma generation models. High intensity beam sampling is already a difficult task because of the damage usually generated on the beam sampler. But this approach is obviously impossible inside solids. To answer the need for experimental characterization of the pulse propagation, we have developed a technique to reconstruct the 3D fluence distribution inside fused silica by controlling accurately the relative position between the beam and the exit surface of the sample. This approach was successfully used to characterize the propagation of Bessel vortices [START_REF] Jukna | Filamentation with nonlinear Bessel vortices[END_REF][START_REF] Xie | Tubular filamentation for laser material processing[END_REF].

Depending on incident cone angle, several nonlinear regimes were observed : stationary, rotating and specklelike . Experimental results could be quantitatively compared to our numerical simulations. In the stationary regime, tubular plasma could be generated in single pulse inside glass, creating cylindrical damages [START_REF] Xie | Tubular filamentation for laser material processing[END_REF]. We anticipate that this approach can be further used for material compression.

At higher cone angle, the stationary regime is obtained over a wider input pulse energy window, and we noticed some discrepancies between experiments and simulations. These can be explained by the fact that much higher plasma densities are reached within the pulse duration, and simulation of paraxial pulse propagation fail to accurately capture the light plasma interaction.

Fig 1 .

 1 Fig 1. (a) target on-axis profiles launched, (b) simulation of pure Kerr nonlinear propagation of the 3 profiles, (c) corresponding evolution of the spectral intensity along the propagation distance.

Fig 2 .

 2 Fig 2. (left) Surface of the glass sample processed by single shot elliptical Bessel beam for two differente pulse energies, (right) image of the cross section of the 18 muJ case where focused ion beam milling allows a visual access along the plane marked as dashed line on the sample surface. The 3 channels processed in a single pulse are apparent, with constant diameter.