Nicolas Haderer

Romain Rouvoy

Lionel Seinturier

Dynamic Deployment of Sensing Experiments in the Wild Using Smartphones

While scientific communities extensively exploit simulations to validate their theories, the relevance of their results strongly depends on the realism of the dataset they use as an input. This statement is particularly true when considering human activity traces, which tend to be highly unpredictable. In this paper, we therefore introduce APISENSE, a distributed crowdsensing platform for collecting realistic activity traces. In particular, APISENSE provides to scientists a participative platform to help them to easily deploy their sensing experiments in the wild. Beyond the scientific contributions of this platform, the technical originality of APISENSE lies in its Cloud orientation and the dynamic deployment of scripts within the mobile devices of the participants.We validate this platform by reporting on various crowdsensing experiments we deployed using Android smartphones and comparing our solution to existing crowdsensing platforms.

Introduction

For years, the analysis of activity traces has contributed to better understand crowd behaviors and habits [START_REF] Liu | Uncovering Taxi Driver's Mobility Intelligence through His Trace[END_REF]. For example, the Urban Mobs initiative 1 visualizes SMS or call activities in a city upon the occurrence of major public events. These activity traces are typically generated from GSM traces collected by the cellphone providers [START_REF] Sohn | Mobility Detection Using Everyday GSM Traces[END_REF]. However, access to these GSM traces is often subject to constraining agreements with the mobile network operators, which restrict their publication, and have a scope limited to telecom data.

In addition to that, activity traces are also used as a critical input to assess the quality of scientific models and algorithms. As an example, the Reality Mining activity traces 2collected by the MIT Media Lab or the Stanford University Mobile Activity TRAces (SUMATRA) 3 have become a reference testbed to validate mobile algorithms in ad hoc settings [START_REF] Roy | Brief Announcement: A Platform for Experimenting with Mobile Algorithms in a Laboratory[END_REF]. The Community Resource for Archiving Wireless Data At Dartmouth (CRAWDAD) 4 is another initiative from the Dartmouth College aiming at building a repository of wireless network traces. Nonetheless, the diversity of the activity traces available in these repositories remains limited and thus often constrains scientists to tune inadequate traces by mapping some of the parameters to their requirements. More recently, some approaches have mined the data exposed by location-based social network like Gowalla or Foursquare, but the content of these activity traces remains limited to coarse-grained locations collected from users check-ins.

In this context, we believe that cellphones represent a great opportunity to collect a wide range of crowd activity traces. Largely adopted by populations, with more than 472 millions sold in 2011 (against 297 millions in 2010) according to Gartner institute 5 , smartphones have become a key companion in people's dailylife. Not only focusing on computing or communication capabilities, modern mobile devices are now equipped of a wide range of sensors enabling scientist to build a new class of datasets. Furthermore, the generalization of app stores or markets on many mobile phone platforms leverages the enrollment of participants to a larger scale than it was possible previously.

Using cellphones to collect user activity traces is reported in the literature either as participatory sensing [START_REF] Burke | Participatory Sensing[END_REF], which requires explicit user actions to share sensors data, or as opportunistic sensing where the mobile sensing application collect and share data without user involvement. These approaches have been largely used in the multiples research studies including traffic and road monitoring [START_REF] Biagioni | EasyTracker: automatic transit tracking, mapping, and arrival time prediction using smartphones[END_REF], social networking [START_REF] Miluzzo | Research in the App Store Era: Experiences from the CenceMe App Deployment on the iPhone[END_REF] or environmental monitoring [START_REF] Mun | The Personal Environmental Impact Report, as a Platform for Participatory Sensing Systems Research[END_REF]. However, developing a sensing application to collect a specific dataset over a given population in not trivial. Indeed, a participatory and opportunistic sensing application needs to cope with a set of key challenges [START_REF] Cuff | Urban Sensing: Out of the Woods[END_REF][START_REF] Lane | A Survey of Mobile Phone Sensing[END_REF], including energy limitation, privacy concern and needs to provide incentive mechanisms in order to attract participants.

These constraints are making difficult, for scientists non expert in this field, to easily collect realistic datasets for their studies. But more importantly, the developed ad hoc applications may neglect privacy and security concerns, resulting in the disclosure of sensible user information. With regards to the state-of-the-art in this field, we therefore observe that current solutions lack of reusable approaches for collecting and exploiting crowd activity traces, which are usually difficult to setup and tied to specific data representations and device configurations. We therefore believe that crowdsensing platforms require to evolve in order to become more open and widely accessible to scientific communities. In this context, we introduce APISENSE, an open platform targeting multiple research communities, and providing a lightweight way to build and deploy opportunistic sensing applications in order to collect dedicated datasets.

This paper does not focus on user incentive challenges, which we already addressed in [START_REF] Haderer | A preliminary investigation of user incentives to leverage crowdsensing activities[END_REF] to provide an overview of appropriate levers to encourage scientists and participants to contribute to such sensing experiments.

The remainder of this paper is organized as follows. We provide an overview of the APISENSE platform by detailling the server-side infrastructure as well as the clientside application (cf. Section 2). Then, we report on the case studies we deployed in the wild using APISENSE (cf. Section 3) before comparing our solution to the state-of-theart approaches (cf. Section 4). Finally, we discuss the related work in this domain (cf. Section 5) before concluding (cf. Section 6).

Distributed Crowdsensing Platform

The APISENSE platform distinguishes between two roles. The former, called scientist, can be a researcher who wants to define and deploy an experiment over a large population of mobile users. The platform therefore provides a set of services allowing her to describe experimental requirements in a scripting language, deploying experiment scripts over a subset of participants and connect other services to the platform in order to extract and reuse dataset collected in other contexts (e.g., visualization, analysis, replay). Technically, the server-side infrastructure of APISENSE is built on the principles of Cloud computing in order to offer a modular service-oriented architecture, which can be customized upon scientist requirements. The latter is the mobile phone user, identified as a participant. The APISENSE platform provides a mobile application allowing to download experiments, execute them in a dedicated sandbox and automatically upload the collected datasets on the APISENSE server.

Server-side Infrastructure

The main objective of APISENSE is to provide to scientist a platform, which is open, easily extensible and configurable in order to be reused in various contexts. To achieve this goal, we designed the server-side infrastructure of APISENSE as an SCA distributed system (cf. Figure 1). The Service Component Architecture (SCA) 6 standard is a set of specifications for building distributed application based on Service-Oriented Architectures (SOA) and Component-Based Software Engineering (CBSE) principles. All the components building the server-side infrastructure of APISENSE are hosted by a Cloud computing infrastructure [START_REF] Paraiso | A Federated Multi-Cloud PaaS Infrastructure[END_REF]. The Scientist Frontend and Participant Frontend components are the endpoints for the two categories of users involved in the platform. Both components define all the services that can be remotely invoked by the scientists or the participants. For example, once authenticated, the scientist can create new experiments, follow their progression, and exploit the collected dataset directly from this web interface.

Crowdsensing Library. To reduce the learning curve, we decided to adopt standard scripting languages in order to ease the description of experiments by the scientists. We therefore propose the APISENSE crowdsensing library as an extension of the JavaScript, CoffeeScript, and Python languages, which provides an efficient mean to describe an experiment without any specific knowledge of mobile device programming technologies (e.g., Android SDK). The choice of these host languages was mainly motivated by their native support for JSON (JavaScript Object Notation), which is a lightweight data-interchange format reducing the communication overhead.

The APISENSE crowdsensing library adopts a reactive programming model based on the enlistment of handlers, which are triggered upon the occurence of specific events (cf. Section 3). In addition to that, the API of APISENSE defines a set of sensing functions, which can be used to retrieve specific contextual data form sensors. The library supports a wide range of features to build dataset from built-in sensors proposed by smartphones technologies, such as GPS, compass, accelerometers, bluetooth, phone call, application status (installed, running) in the context of opportunistic crowdsensing, but also to specify participatory sensing experiments (e.g., surveys).

Privacy Filters. In addition to this script, the scientist can configure some privacy filters to limit the volume of collected data and enforce the privacy of the participants. In particular, APISENSE currently supports two types of filters. Area filter allows the scientist to specify a geographic area where the data requires to be collected. For example, this area can be the place where the scientist is interested in collecting a GSM signal (e.g., campus area). This filter guarantees the participants that no data is collected and sent to the APISENSE server outside of this area. Period filter allows the scientist to define a time period during which the experiment should be active and collect data. For example, this period can be specified as the working hours in order to automatically discard data collected during the night, while the participant is expected to be at home. By combining these filters, the scientist preserves the privacy of participants, reduces the volume of collected data, and improves the energy efficiency of the mobile application (cf. Section 4).

Deployment Model. Once an experiment is defined with the crowdsensing library, the scientist can publish it into the Experiment Store component in order to make it available to participants. Once published, two deployment strategies can be considered for deploying experiments. The former, called pull-based approach, is a proactive deployment strategy where participants download the list of experiments from the remote server. The latter, known as push-based approach, propagates the experiments list updates to the mobiles devices of participants. In the case of APISENSE, the push-based strategy would induce a communication and energy overhead and, in order to leave the choice to participants to select the experiments they are interested in, we adopted the pull-based approach as a deployment strategy. Therefore, when the mobile device of a participant connects to the Experiment Store, it sends its characteristics (including hardware, current location, sensor available and sensors that participants want to share) and receives the list of experiments that are compatible with the profile of the participant. The scientists can therefore configure the Experiment Store to limit the visibility of their experiments according the characteristics of participants. In order to reduce the privacy risk, the device characteristics sent by the participants are not stored by the infrastructure and scientist cannot access to this information.

Additionally, the Experiment Store component is also used to update the behavior of the experiment once deployed in the wild. When an opportunistic connection is established between the mobile device and the APISENSE server, the version of the experiment deployed in the mobile device is compared to the latest version published in the server. The installed crowdsensing experiment is automatically updated with the latest version of the experiment without imposing participants to re-download manually the experiment. In order to avoid any versioning problem, each dataset uploaded automatically includes the version of the experiment used to build the dataset. Thus, scientists can configure the Experiment Store component in order to keep or discard datasets collected by older versions of the experiment.

Client-side Library

Although our solution could be extended to other Operating Systems, the APISENSE mobile application is currently based on the Android operating system for the following reasons. First, the Android operating system is popular and largely adopted by the population, unit sales for Android OS smartphones were ranked first among all smartphone OS handsets sold worldwide during 2011 with a market share of 50.9% according to Gartner. Secondly, Android is an open platform supporting all the requirements for continuous sensing applications (e.g., multitasking, background processing and ability to develop an application with continuous access to all the sensors), while for example, iOS 6 does no permit a continuous accelerometer sampling.

A participant willing to be involved in one or more crowdsensing experiments proposed by a scientist can download the APISENSE mobile application by flashing the QR code published on APISENSE website, install it, and quickly create an account on the remote server infrastructure. Once registered, the HTTP communications between the mobile device of the participant and the remote server infrastructure are authenticated and encrypted in order to reduce potential privacy leaks when transferring the collected datasets to the APISENSE server. From there, the participant can connect to the Experiment Store, download and execute one or several crowdsensing experiments proposed by scientists.

Figure 2 depicts the APISENSE software architecture. Building on the top of Android SDK, this architecture is mainly composed of four main parts allowing i) to interpret experiment scripts (Facades, Scripting engine) ii) to establish connection with the remote server infrastructure (Network Manager), iii) to control the privacy parameters of the user (Privacy Manager), and iv) to control power saving strategies (Battery Manager).

Scripting Engine. Sensor Facades bridge the Android SDK with the Scripting Engine, which integrates scripting engines based on the JSR 223 specification. We build a middleware layer Bee.sense Scripting, which exposes the sensors that can be accessed from the experiment scripts. This layer covers three roles: a security role to prevent malicious calls of critical code for the mobile device, a efficiency role by including a cache mechanism to limit system calls and preserve the battery, and an accessibility role to leverage the development of crowdsensing experiments, as illustrated in Section 3. Battery Manager. Although the latest generations of smartphones provides very powerful computing capabilities, the major obstacle to enable continuous sensing application refers to their energy restrictions. Therefore, in order to reduce the communication overhead with the remote server, which tends to be energy consuming, datasets are uploaded only when the mobile phone is charging. In particular, the battery manager component monitors the battery state and triggers the network manager component when the battery starts charging in order to send all the collected datasets to the remote server. Additionally, this component monitors the current battery level and suspends the scripting engine component when the battery level goes below a specific threshold (20% by default) in order to stop all running experiments. This threshold can be configured by the participant to decide the critical level of battery she wants to preserve to keep using her smartphone.

Privacy Manager. In order to cope with the ethical issues related to crowdsensing activities, the APISENSE mobile application allows participants to adjust their privacy preferences in order to constrain the conditions under which the experiments can collect data. As depicted in Figure 3, three categories of privacy rules are currently defined. Rules related to location and time specify geographical zone and time intervals conditions under which experiments are authorized to collect data, respectively. All the privacy rules defined by the participant are interpreted by the Privacy Manager component, which suspends the scripting engine component when one these rules is triggered. The last category of privacy rules refers to authorization rules, which prevent sensors activation or access to raw sensor data if the participant does not want to share this information. Additionally, a built-in component uses cryptography hashing to prevent experiments from collecting sensitive raw data, such as phone numbers, SMS text, or address book.

Crowdsensing Experiments

This section reports on four experiments that have been deployed in the wild using our platform. These examples demonstrate the variety of crowdsensing experimentations that are covered by the APISENSE infrastructre.

Revealing Users' Identity from Mobility Traces

This first experiment aimed at identifying the potential privacy leaks related to the sporadic disclosure of user's locations. To support this experiment, we developed a APISENSE script, which reports every hour the location of a participant, known as Alice. Listing 1.1 describes the Python script we used to realize this experiment. This script subscribes to the periodic scheduler provided by the time facade in order to trigger the associated lambda function every hour. This function dumps a timestamped longitude/latitude position of Alice, which is automatically forwarded to the server. While this periodic report can be considered as anonymous since no identifier is included in the dataset, this study has shown that the identity of Alice can be semiautomatically be inferred from her mobility traces. To do so, we built a mobility model from the dataset we collected in order to identify clusters of Alice's locations as her points of interest (POI). By analyzing the size of the clusters and their relative timestamps, we can guess that the largest POI in the night relates to the house of Alice. Invoking a geocoding service with the center of this POI provides us a postal address, which can be used as an input to the yellow pages in order to retrieve a list of candidate names. In parallel, we can identify the places associated to the other POIs by using the Foursquare API, which provides a list of potential places where Alice is used to go. From there, we evaluate the results of search queries made on Google by combining candidate names and places and we rank the names based on the number of pertinent results obtained for each name. This heuristic has demonstrated that the identity of a large population of participants can be easily revealed by sporadically monitoring her location [START_REF] Killijian | Beyond San Fancisco Cabs : Building a *-lity Mining Dataset[END_REF].

Building WiFi/GSM Signal Open Data Maps

This second experiment illustrates the benefits of using APISENSE to automatically build two open data maps from datasets collected in the wild. Listing 1.2 is a JavaScript script, which is triggered whenever the location of a participant changes by a distance of 10 meters in a period of 5 minutes. When these conditions are met, the script builds a trace which contains the location of the participant and attaches WiFi and GSM networks characteristics. From the dataset, collected by three participants over one week, we build an QuadTree geospatial index to identify the minimum bounding rectangles that contain at least a given number of signal measures. These rectangles are then automatically colored based on the median signal value observed in this rectangle (cf. Figure 4). This map has been assessed by comparing it with a ground truth map locating the GSM antennas and WiFi routers7 .

Detecting Exceptions Raised by User Applications

The third experiment highlights that APISENSE does not impose to collect geolocated dataset and can also be used to build realistic dataset focusing on the exceptions that are raised by the participants' applications. To build such a dataset, Listing 1.3 describes a CoffeeScript script that uses the Android logging system (logCat) and subscribes to error logs (' * :E'). Whenever, the reported log refers to an exception, the script builds a new trace that contains the details of the log and retrieves the name of the application reporting this exception. Once deployed in the wild, the exceptions reported by the participants can be used to build a taxonomy of exceptions raised by mobile applications. The Figure 5, depicts the results of this experiment based on a dataset collected from three participants over one month. In particular, one can observe that a large majority of errors reported by the participant's applications are related to permission or database accesses, which can usually be fixed by checking that the application is granted an access prior to any invocation of a sensor or the database. This experiment is a preliminary step in order to better identify bugs raised by applications once they are deployed in the wild as we believe that the diversity of mobile devices and operating conditions makes difficult the application of traditional in vitro testing techniques.

Experimenting Machine Learning Models

The fourth experiment does not only collect user-contributed datasets, but also deals with the empirical validation of models on a population of participants. In this scenario, the scientist wanted to assess the machine learning model she defined for detecting the activity of the users: walking, sitting, standing, running, or climbing and down stairs. To assess this model, she deployed a script that integrates two phases: an exploration phase and an exploitation one. To set up this experiment, we extended the scripting library by integrating a popular machine learning [START_REF] Liu | Mobile weka as data mining tool on android[END_REF] and adding a new facade to use its features from script. The script (cf. Listing 1.4) therefore starts with an exploration phase in order to learn a specific user model. During this phase, APISENSE generates some dialogs to interact with the participant and ask her to repeat some specific movements. The script automatically switches to the next movement when the model has recorded enough raw data from the accelerometer to provide an accurate estimation. Once the model is considered as complete, the script dynamically replace the timer handler to switch into the exploration phase. The dataset collected by the server-side infrastructure of APISENSE contain the model statisitcs observed for each participant contributing to the experiment.

1 var classes = ["walk","jog","stand", "sit", "up", "down"]; 2 var current = 0; var buffer = new Array(); 3 var model = weka.newModel(["avrX","avrY",...], classes); 4 var filter = "|(dx>"+delta+")(dy>"+delta+")(dz>"+delta+")";

Empirical Validations

Evaluating the Programming Models. In this section, we compare the APISENSE crowdsensing library to two state-of-the-art approaches: ANONYSENSE [START_REF] Shin | AnonySense: A System for Anonymous Opportunistic Sensing[END_REF] and POGO [START_REF] Brouwers | a Middleware for Mobile Phone Sensing[END_REF].

We use the RogueFinder case study, which has been introduced by AnonySense and recently evaluated by POGO. Listings 1.5 and 1.6 therefore reports on the implementation of this case study in ANONYSENSE and POGO, as decribed in the literature, while Listing 1.7 describes the implementation of this case study in APISENSE. One can observe that APISENSE provides a more concise notation to describe crowdsensing experiments than the state-of-the-art approaches. This concisition is partly due to the fact that APISENSE encourages the separation of concerns by externalizing the management of time and space filters in the configuration of the experiment. A direct impact of this property is that the execution of APISENSE scripts better preserves the battery of the mobile device compared to POGO, as it does not keep triggering the script when the user leaves the assigned polygon. Nonetheless, this statement is only based on an observation of POGO as the library is not made freely available to confirm this empirically.

Evaluating the Energy Consumption. In this section, we compare the energy consumption of APISENSE to a native Android application and another state-of-the-art crowdsensing solution: FUNF [START_REF] Aharony | Social fmri: Investigating and shaping social mechanisms in the real world[END_REF]. FUNF provides an Android toolkit to build custom crowdsensing applications à la carte. For each technology, we developed a sensing application, which collects the battery level every 10 minutes. We observed the energy consumption of these applications and we report their consumption in Figure 7.

Compared to the baseline, which corresponds to the native Android application, one can observe that the overhead induced by our solution is lower than the one imposed by the FUNF toolkit. This efficiency can be explained by the various optimizations included in our crowdsensing library. Although more energyvorous than a native application, our solution does not require advanced skills of the Android development framework and covers the deployment and reporting phases on behalf of the developer.

As the energy consumption strongly depends on i) the nature of the experiment, ii) the types of sensors accessed, and iii) the volume of produced data, we conducted a experiment in order to quantify the impact of sensors (cf. Figure 8). For this experiment, we developed three scripts, which we deployed separately. The first script, labelled Bee.sense + Bluetooth, triggers a Bluetooth scan every minute and collects both the battery level as well as the resulting Bluetooth scan. The second script, Bee.sense + GPS, records every minute the current location collected from the GPS sensor, while the third script, Bee.sense + WiFi, collects a WiFi scan every minute. These experiments demonstrate that, even when stressing sensors, it is still possible to collect data during a working day without charging the mobile phone (40% of battery left after 10 hours of pulling the GPS sensor).

Related Work

A limited number of data collection tools are freely available on the market. SYSTEM-SENS [START_REF] Falaki | SystemSens: a tool for monitoring usage in smartphone research deployments[END_REF], a system based on Android, focuses on collecting usage context (e.g., CPU, memory, network info, battery) of smartphones in order to better understand the battery consumption of installed applications. Similarly, LIVELABS [START_REF] Shepard | LiveLab: measuring wireless networks and smartphone users in the field[END_REF] is a tool to measure wireless networks in the field with the principal objective to generate a complete network coverage map in order to help client to select network interface or network operators to identify blind spots in the network. However, all these tools are closed solutions, designed for collecting specific datasets and cannot be reused in unforeseen contexts in contrast to APISENSE. Furthermore, these projects are typical experiments deployed on mobile devices, without providing any privacy guarantee. FUNF [START_REF] Aharony | Social fmri: Investigating and shaping social mechanisms in the real world[END_REF] is an Android toolkit focusing on the development of sensing applications. FUNF in a box is a service provided by FUNF to easily build a dedicated sensing application from a web interface, while data is periodically published via the Dropbox service. As demonstrated in Section 4, the current version of FUNF does not provide any support for saving energy nor preserving user privacy. Furthermore, the current solution does not support the dynamic re-deployment of experiments once deployed in the wild.

More interestingly, MYEXPERIENCE [START_REF] Froehlich | Myexperience: a system for in situ tracing and capturing of user feedback on mobile phones[END_REF] is a system proposed for Windows mobile smartphones, tackling the learning curve issue by providing a lightweight configuration language based on XML in order to control the features of the application without writing C# code. MYEXPERIENCE collects data using a participatory approach-i.e., by interacting with users when a specific event occurs (e.g., asking to report on the quality of the conversation after a phone call ends). However, MYEXPERIENCE does not consider severals critical issues, such as maintaining the privacy of participants or the strategic deployment of experiments. Even if an experiment can be modified in the wild, each experiment still requires a physical access to the mobile device in order to be installed, thus making it difficult to be applied on a large population of participants.

In the literature, severals deployment of crowdsensing applications strategies have been studied. For example, ANONYSENSE [START_REF] Shin | AnonySense: A System for Anonymous Opportunistic Sensing[END_REF] uses-as APISENSE-a pull-based approach where mobile nodes periodically download all sensing experiments available on the server. A crowdsensing experiment is written in a domain-specific language and defines when a mobile node should sense and under which conditions the report should be submitted to the server. However, ANONYSENSE does not provide any mechanism to filter the mobile nodes able to download sensing experiments, thus introducing a communication overhead if the node does not match the experiment requirements.

On the contrary, PRISM [START_REF] Das | Prism: Platform for Remote Sensing Using Smartphones[END_REF] and POGO [START_REF] Brouwers | a Middleware for Mobile Phone Sensing[END_REF] adopts a push-based approach to deploy sensing experiments over mobile nodes. PRISM is a mobile platform, running on Microsoft Windows Mobile 5.0, and supporting the execution of generic binary code in a secure way to develop real-time participatory sensing applications. To support real-time sensing, PRISM server needs to keep track of each mobile node and the report they periodically send (e.g., current location, battery left) before selecting the appropriate mobile phones to push application binaries. POGO proposes a middleware for building crowdsensing applications and using the XMPP protocol to disseminate the datasets. Nonetheless, POGO does not implement any client-side optimizations to save the mobile device battery (e.g., area and period filters) as it systematically forwards the collected data to the server.

SensorSafe [START_REF] Choi | Sensorsafe: Managing health-related sensory information with fine-grained privacy controls[END_REF] is another participatory platform, which allows users to share data with privacy guaranties. As our platform, SensorSafe provides fine-grained temporal and location access control mechanisms to keep the control of data collected by sensors on mobile phone. However, participants have to define their privacy rules from a web interface while in APISENSE these rules are defined directly from the mobile phone.

Conclusion

While it has been generally acknowledged as a keystone for the mobile computing community, the development of crowdsensing platforms remains a sensitive and critical task, which requires to take into account a variety of requirements covering both technical and ethical issues.

To address these challenges, we report in this paper on the design and the implementation of the APISENSE distributed platform. This platform distinguishes between two roles: scientists requiring a sustainable environment to deploy sensing experiments and participants using their own mobile device to contribute to scientific experiments. On the server-side, APISENSE is built on the principles of Cloud computing and offers to scientists a modular service-oriented architecture, which can be customized upon their requirements. On the client-side, the APISENSE platform provides a mobile application allowing to download experiments, executing them in a dedicated sandbox and uploading datasets to the APISENSE server. Based on the principle of only collect what you need, the APISENSE platform delivers an efficient yet flexible solution to ease the retrieval of realistic datasets.

Fig. 1 .

 1 Fig. 1. Architecture of the APISENSE Web Infrastructure.

Fig. 2 .

 2 Fig. 2. Architecture of the APISENSE Mobile Application.

Fig. 3 .

 3 Fig. 3. Participant Privacy Preferences.

Fig. 4 .

 4 Fig. 4. GSM Open Data Map.

Fig. 5 .

 5 Fig. 5. Exceptions Taxonomy

Figure 6 Fig. 6 .

 66 Figure 6 reports on the collected statistics of this experiment and shows that the prediction model developed by the scientist matches quite accurately the targeted classes.

Fig. 7 .

 7 Fig. 7. Energy Consumptions of Android, APISENSE, and FUNF.

Fig. 8 .

 8 Fig. 8. Impact of APISENSE on the Battery Lifespan.

http://www.urbanmobs.fr

http://reality.media.mit.edu

http://infolab.stanford.edu/pleiades/SUMATRA.html

http://crawdad.cs.dartmouth.edu

http://www.gartner.com/it/page.jsp?id=1924314

http://www.osoa.org

http://www.cartoradio.fr


Alexandre Janon

Multifidelity variance reduction for pick-freeze Sobol index estimation

Many mathematical models involve input parameters, which are not precisely known. Global sensitivity analysis aims to identify the parameters whose uncertainty has the largest impact on the variability of a quantity of interest (output of the model). One of the statistical tools used to quantify the influence of each input variable on the output is the Sobol sensitivity index, which can be estimated using a large sample of evaluations of the output. We propose a variance reduction technique, based on the availability of a fast approximation of the output, which can enable significant computational savings when the output is costly to evaluate.

Introduction

Many mathematical models encountered in applied sciences involve a large number of poorly-known parameters as inputs. It is important for the practitioner to assess the impact of this uncertainty on the model output. An aspect of this assessment is sensitivity analysis, which aims to identify the most sensitive parameters, that is, parameters having the largest influence of the output. In global stochastic sensitivity analysis (see for example [START_REF] Saltelli | Wiley Series in Probability and Statistics[END_REF] and references therein) the input variables are assumed to be independent random variables. Their probability distributions account for the practitioner's belief about the input uncertainty. This turns the model output into a random variable, whose total variance can be split down into different partial variances (this is the so-called Hoeffding decomposition, see [START_REF] Van Der | Asymptotic statistics, volume 3 of Cambridge Series in Statistical and Probabilistic Mathematics[END_REF]). Each of these partial variances measures the uncertainty on the output induced by each input variable uncertainty. By considering the ratio of each partial variance to the total variance, we obtain a measure of importance for each input variable that is called the Sobol index or sensitivity index of the variable [START_REF] Sobol | Sensitivity estimates for nonlinear mathematical models[END_REF]; the most sensitive parameters can then be identified and ranked as the parameters with the largest Sobol indices. Once the Sobol indices have been defined, the question of their effective computation or estimation remains open. In practice, one has to estimate (in a statistical sense) those indices using a finite sample (of size typically in the order of hundreds of thousands) of evaluations of model outputs [START_REF] Helton | Survey of sampling-based methods for uncertainty and sensitivity analysis[END_REF]. Indeed, many Monte Carlo or quasi Monte Carlo approaches have been developed by the experimental sciences and engineering communities. Such an approach is the Sobol pick-freeze (SPF) scheme (see [START_REF] Sobol | Sensitivity estimates for nonlinear mathematical models[END_REF][START_REF] Sobol | Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates[END_REF]). In SPF a Sobol index is viewed as the regression coefficient between the output of the model and its pick-freezed replication. This replication is obtained by holding the value of the variable of interest (frozen variable) and by sampling the other variables (picked variables). The sampled replications are then combined to produce an estimator of the Sobol index. The SPF method requires many (typically, around one thousand times the number of input variables) evaluations of the model output. In many interesting cases, an evaluation of the model output is made by a complex computer code (for instance, a numerical partial differential equation solving algorithm) whose running time is not negligible (typically in the order of a second or a minute) for one single evaluation. When thousands of such evaluations have to be made, one generally replaces the original exact model by a faster-to-run metamodel (also known in the literature as surrogate model or response surface [START_REF] Box | Empirical model-building and response surfaces[END_REF]) which is an approximation of the true model. Wellknown metamodels include Kriging [START_REF] Santner | The Design and Analysis of Computer Experiments[END_REF], polynomial chaos expansion [START_REF] Sudret | Global sensitivity analysis using polynomial chaos expansions[END_REF] and reduced bases [START_REF] Nguyen | Certified real-time solution of parametrized partial differential equations[END_REF][START_REF] Janon | Certified reduced-basis solutions of viscous Burgers equations parametrized by initial and boundary values[END_REF], to name a few. From a multifidelity point of view, the metamodel can also be viewed as a "coarse" (low-fidelity) version of the code; the metamodel, seen as a coarse version, may also be a "degraded" version of the code: for instance, it may be a solver for a simplified model (either mathematically simplified, or discretized on a coarser grid), an integrator for a function of lesser precision, or an optimizer stopped before its full convergence. In this paper, we designate by "coarse approximation" any of the above approximations (metamodels and degraded versions). When using a coarse approximation for sensitivity analysis, the original model is generally used only to define the metamodel, and not to perform the Sobol index estimation. This leads to a necessity of measuring the difference between the model and its approximation in order to certify the sensitivity index estimation [START_REF] Janon | Certified reduced-basis solutions of viscous Burgers equations parametrized by initial and boundary values[END_REF][START_REF] Janon | Asymptotic normality and efficiency of two Sobol index estimators[END_REF]. To our best knowledge, no approach for using both metamodel and model evaluations to estimate Sobol indices have been proposed yet. In this work, we propose an approach, based on the asymptotic properties of the SPF scheme studied in [START_REF] Janon | Asymptotic normality and efficiency of two Sobol index estimators[END_REF] to optimally combine evaluations of the original model and evaluations of its approximation, in order to produce an asymptotically-justified confidence interval for the Sobol index of the original model. Our approach is inspired by the quasi-control variate method [START_REF] Emsermann | Improving simulation efficiency with quasi control variates[END_REF] which has been developed for Monte-Carlo estimation of means. This paper is organized as follows: in the first section, we begin by setting up the notations and the context of the paper. Then we define the Sobol index estimator we wish to study. The main result is Theorem 1.1, which provides an asymptotic method to estimate a confidence interval for a Sobol index. The second section is a numerical illustration on a particular (but representative) kind of model output.

Motivation and definition of the estimator 1.Notation and context

We begin by setting up the usual notations in the sensitivity analysis contexts. The output of interest is a random variable Y , which is a deterministic function η : R p → R of the random inputs X ∈ R p 1 and Z ∈ R p 2 :

Y = η(X, Z),
where p 1 and p 2 are integers, and p = p 1 + p 2 . We assume that X and Z are independent random variables and that Y has a finite and nonzero variance. We are interested in the (closed) Sobol index [START_REF] Saltelli | Sensitivity analysis in practice: a guide to assessing scientific models[END_REF] with respect to X, defined by:

S = Var(E(Y |X)) VarY .
This index, which is between 0 and 1, quantifies the influence of the X input on the output Y : a value of S that is close to 1 indicates that X is highly influential on Y . The pick-freeze method [START_REF] Janon | Asymptotic normality and efficiency of two Sobol index estimators[END_REF] expresses S using a covariance:

S = Cov(Y, Y ′ ) VarY for Y ′ = f (X, Z ′ ),
where Z ′ is an independent copy of Z.

This expression leads to different Monte-Carlo estimators of S. For instance, the following estimator is studied in [START_REF] Janon | Asymptotic normality and efficiency of two Sobol index estimators[END_REF]:

T η N = 1 N Y i Y ′ i -1 N Y i +Y ′ i 2 2 1 N Y 2 i +(Y ′ i ) 2 2 -1 N Y i +Y ′ i 2 2 ,
where, (Y i ) i=1,...,N and (Y ′ i ) i=1,...,N are independent samples of Y (resp. Y ′ ), and, as in the rest of the paper, all sums are for i from 1 to N . It is shown [op.cit., Proposition 2.2] that (T N ) N is asymptotically normal, with variance σ 2 T,η /N , where:

σ 2 T,η = Var (Y -E(Y ))(Y ′ -E(Y )) -S/2 (Y -E(Y )) 2 + (Y ′ -E(Y )) 2 (Var(Y )) 2 ,
(1) and [op.cit., Proposition 2.5] that this asymptotic variance is minimal among regular estimators that are functions of realizations of exchangeable (Y, Y ′ ) pairs. Note that a realization of the T η N estimator, for a finite sample size N , can be computed by making 2N evaluations of the η function. In this paper, we suppose that we can evaluate, in addition to the η function, an approximation η c : R p → R of the η function (the c index is for coarse).

The usage of such an approximation has been motivated in the Introduction. A concrete and ubiquitous example of η and η c will be presented in the next section. In the following section, we motivate and study our variancereduced estimator of S.

Variance-reduced estimator

Let:

Y c = η c (X, Z), Y ′ c = η c (X, Z ′ ), and (Y ci ) i=1,...,N , (Y ′ ci ) i=1,...,N be N -samples of Y c (resp. Y ′ c
). The estimator:

T N = 1 N Y ci Y ′ ci -1 N Y ci +Y ′ ci 2 2 1 N Y 2 ci +(Y ′ ci ) 2 2 -1 N Y ci +Y ′ ci 2 2
consistently estimates the Sobol index of the coarse model:

S c = Var(E(Y c |X)) VarY c .
by using 2N evaluations of η c .

As mentioned in the introduction, our objective is to combine evaluations of η and η c to estimate S at a smaller cost than an estimation that would be performed from evaluations of η only.

We take a function ψ : N → N.

It is clear that the estimator E N defined by:

E N = T η ψ(N ) -T ψ(N )
consistently estimates E = S -S c , and that a realization of E N can be obtained using 2ψ(N ) evaluations of η c and 2ψ(N ) evaluations of η. We propose a natural estimator of S based on T N and E N , inspired by the quasi-control variate method [START_REF] Emsermann | Improving simulation efficiency with quasi control variates[END_REF], is thus:

V N = T N + E N .
This estimator can be computed by making 2(N + ψ(N )) evaluations of η c and 2ψ(N ) evaluations of η. As an evaluation of η is more costly than one of η c , one can expect a computational gain if ψ(N ) ≤ N , and if the asymptotic variance of (V N ) is less than the asymptotic variance of (T η ψ(N ) ), so that asymptotic confidence intervals built upon V N are more precise than those built on T η ψ(N ) alone. The following theorem gives a method for estimating (conservative) asymptotic confidence intervals using V N . We denote by Φ the cumulative distribution function of the Gaussian with zero mean and unit variance, and by Φ -1 its inverse.

Theorem 1.1. Suppose that lim N →+∞ ψ(N ) = +∞. Then, for any α e and α c in ]0, 1[: lim

N →+∞ P |S -V N | ≤ q(α e ) σ e ψ(N ) + q(α c ) σ c √ N ≥ 1 -(α e + α c ),
for:

q(a) = Φ -1 (1 -a/2), σ 2 c = Var (A c -B c /2) (VarY c ) 2 , σ 2 e = σ 2 c + Var (A -B/2) (VarY ) 2 - 2Cov(A, A c ) -(Cov(A, B c ) + Cov(B, A c )) + Cov(B, B c )/2 VarY VarY c ,
where A, B, A c , B c are the following random variables:

A = (Y -E(Y ))(Y ′ -E(Y )), B = S (Y -E(Y )) 2 + (Y ′ -E(Y )) 2 , A c = (Y c -E(Y c ))(Y ′ c -E(Y c )), B c = S c (Y c -E(Y c )) 2 + (Y ′ c -E(Y c )) 2 .
The same holds when σ c and σ e are replaced by any consistent estimators. Sketch of proof. Follow the proof of [START_REF] Janon | Asymptotic normality and efficiency of two Sobol index estimators[END_REF], Proposition 2.2, and apply the δmethod to (T N , T η ψ(N ) ) to get the asymptotic variance of (E N ). Then use that for any ǫ 1 , ǫ 2 ,

{|V N -S| ≥ ǫ 1 + ǫ 2 } ⊆ {|T N -S c | ≥ ǫ 1 } ∪ {|E N -E| ≥ ǫ 2 } .

Choice of ψ, α e and α c

To convert the theorem above into a practical procedure, it remains to choose the parameters ψ, α e and α c , so as to minimize the overall computational time.

We will assume that one evaluation of η as a unit cost, and that an evaluation of η c has cost 0 < ρ < 1. We also set ψ(N ) = ⌈µN ⌉, where µ ∈]0, 1[ is to be found, and ⌈•⌉ is the "ceiling" function. We choose a target risk level α ∈]0, 1[ and a target length L for the confidence interval of Theorem 1.1. It is clear these constraints force α c in function of α e and α:

α c = α * (α e ) = 1 -(α + α e ),
and that N has to satisfy:

N ≥ N * (α e , µ) := 4 L 2 q(α e )σ e √ µ + q(α * (α e ))σ c 2
We approximate ψ(N * ) by µN * . The cost of the required evaluations of η and η c is thus, in the general case:

Cost(α e , µ) = 2N * (α e , µ) (2µ + ρ) ,
corresponding to the ψ(N ) evaluations of η and the ψ(N ) + N evaluations of η c . However, in some settings, the computations made to compute η c can be reused to compute η, allowing to evaluate η c and η for a unit cost, leading to: Cost Hier (α e , µ) = 2N * (α e , µ) (µ + ρ) .

Such a "hierarchical" property is beneficial to our estimation scheme and occurs naturally for some η, as we will see in the numerical illustration section. Now, one would obviously choose α e and µ so as to minimize the cost Cost(α e , µ) (or, depending on the case at hand, Cost Hier (α e , µ)). In practice, this is not possible, as σ e and σ c are unknown. Hence, approximately optimal parameters are found by empirically estimating these quantities, based on a small sample of realizations of Y , Y ′ , Y c and Y ′ c . This gives rise to α * e and µ * , and an estimated optimal costs:

Cost( α * e , µ * ) and Cost Hier ( α * e , µ * ).

2 Numerical illustration

Model set-up

In financial mathematics, the Heston model [START_REF] Steven L Heston | A closed-form solution for options with stochastic volatility with applications to bond and currency options[END_REF] is the following stochastic differential model for the price of a risky asset (S t ) t≥0 as function of the We are interested in the price of an European call option of maturity T and strike K, which is given by e -RT E Q (S T -K) + . Although a semi-analytical formula is available for the fast computation of this expectation (such a formula may not exist for more complex dynamics of the underlying asset, or for exotic options), we will use a numerical approximation so as to illustrate our methodology on a realistic model example. The expectation is approached by the following Monte-Carlo procedure: η(ν 0 , κ, θ, r, ξ, R, S 0 , T, K) = e -RT M M j=1 (S T,j -K) + with an Euler-Maruyama approximation of (S t , ν t ) t∈[0,T ] with timestep h > 0: for j = 1, . . . , M and t = 1, ..., T /h:

           S 0,j = S 0 ν 0,j = ν 0 S th,j = S (t-1)h,j 1 + Rh + √ ν (t-1)h,j √ h∆W 1 t,j ν th,j = ν (t-1)h,j 1 + κ(θ -ν (t-1)h,j )h + ξ √ ν (t-1)h,j √ h(r∆W 1 t,j + √ 1 -r 2 ∆W 2 t,j )
where h > 0 is the time discretization parameter, and (∆W 1 t,j , ∆W 2 t,j ) are indepedent realizations of a standard Gaussian random variable. We fix S 0 = 60 (the initial price of the asset), T = 0.25, K = 30, as well as the discretization parameters h = .001 and M = 10000. The uncertain parameters are X = (ν 0 ) and Z = (κ, θ, r, ξ, R), which are given the uniform distribution probabilities summarized in Table 1. The coarse approximation uses a reduced number m of simulated trajectories to compute the empirical mean:

η c (ν 0 , κ, θ, R, ξ, R, S 0 , T, K) = e -RT m m j=1 (S T,j -K) +
Note that for computing η c , the same time discretization parameter h, as well as the same simulated Brownian increments ∆W 1,2 are kept, hence our approximation is "hierarchical" in the sense of Subsection 1.3.

We chose m = 5000, so that ρ = m/M = 1/2.

Results and discussion

We estimated σ c and σ e based on a sample of n = 100 realizations of each variable Y, Y ′ , Y c and Y ′ c . The estimates are:

σ c = .
9017 σ e = .4909.

For comparison purposes, we also estimated σ T,η :

σ T,η = .8491.

We are interested in the (estimated) relative efficiency of the confidence intervals based on our variance-reduced estimator, as compared with those based on T η , that is:

Eff = 1 - Cost Hier ( α * e , µ * ) ClassicalCost ,
where ClassicalCost is the cost of the η evaluations necessary to produce an asymptotic confidence interval of fixed length L using only the T η estimator: ClassicalCost = 2 4 L 2 (q(α) σ T,η ) 2 .

As the denominator and the numerator of Eff are proportional to L 2 , the relative efficiency is independent of the target length of the confidence interval L.

In Figure 1, we plot the estimated relative efficiency of our variance-reduced estimator, as function of the target risk level α.

We see that, based on empirical estimations, our variance reduction enables an interesting reduction of the computational cost by more than 50% for α = 0.05, and this reduction is even more significative for small risk levels (up to 90% for α = 0.0001).

  0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045 0.05 relative efficiency estimate alpha (risk level)

Figure 1 :

 1 Figure 1: Estimates of relative efficiencies, for various values of α ∈ [0.0001, 0.05].

Table 1 :

 1 Distributions and interpretations of the input parameters. ) t≥0 are standard Brownian motions (under the risk-neutral probability measure Q) whose correlation is r ∈ [0, 1].

	Name Interpretation	Min. Max.
	ν 0	Initial volatility	.2		.25
	κ	Volatility convergence rate	0		3
	θ	Volatility limit	.2		.22
	r	Correlation between Brownians -1		1
	ξ	Volatility of the volatility	0		.4
	R	Risk-free rate	.08	1.1
	time t > 0: where (W 1 t ) t≥0 and (W 2 dS t = µS t dt + dν t = κ(θ -ν t ) dt + ξ √ ν t S t dW 1 t √ ν t dW 2 t t	,

* Laboratoire de Sciences Actuarielle et Financière, ISFA, Université Lyon 1, 50 avenue Tony Garnier, 69007 Lyon, France. Homepage: http://isfaserveur.univ-lyon1.fr/ ~janona/

Acknowledgements.

This work has been partially supported by the French National Research Agency (ANR) through COSINUS program (project COSTA-BRAVA nr. ANR-09-COSI-015).


Romain Peretti

Thierry Deschamps

Guillaume Gomard

Xianqin Meng

Loïc Lalouat

Fabien Mandorlo

Alain Fave

Emmanuel Drouard

Christian Seassal
email: christian.seassal@ec-lyon.fr

Nanophotonics in photovoltaic cells for solar or indoor light trapping

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

In this communication, we will first introduce the design [2], fabrication, and optical characterization of photonic crystal hydrogenated amorphous silicon (a-Si:H) solar cells structures using 1D [3] or 2D Ph.C. [4,[START_REF] Meng | Solar Energy Materials and Solar Cells 95[END_REF] as shown in fig 1. Such a corrugation of the cell allow to a broader spectral absorption but also a better angular response allowing being good candidate in both solar and indoor photovoltaic.

Then, we introduce designs and experimental results obtained for solar cell structures based on crystalline silicon layers with thicknesses in the micrometer range [6] demonstrating spectral and angular absorption enhancement.

In parallel, and to go further in the complexity of the cells, a better understanding of the phenomenon playing a role in light absorption in PV cell was studied [7,[START_REF] Peretti | Proceeding SPIE[END_REF]. We used the "time domain coupled mode theory" to model light absorption in our device especially focusing in 2 modes interaction.

Lastly, as an outlook, we discuss on the possibility to assist UV light absorption and IR light emission, using a down conversion layer [START_REF] Deschamps | In Photonic West[END_REF], especially useful in the case of indoor photovoltaic cells. For instance, rare earth doped thin layers can absorb UV light and convert down to IR light with an efficiency upper than 1 (1.3 in our case), which is more efficiently converted into an electrical current by a c-Si solar cell. The efficiency of this process can be greatly increased if, e.g., UV light absorption can be strongly enhanced by photonic crystals.

To conclude, using the possibility to take control of the properties of optical modes, including their photon lifetime and their radiation pattern, is a great opportunity to generate novel generations of photovoltaic cells exhibiting specifically designed characteristics that can handle absorption enhancement in both solar and indoor light harvesting.

Figures 1 .

 1 Figures 1. SEM views of the photonic crystal structure (a), and absorption spectra under normal incidence measured for the reference and patterned structures (b).

During the past decades, research in the field of photovoltaic (PV) solar cells was mainly driven by material development, technological upgrading and cost reduction. New challenges have emerged with third generation PV devices, with a view to achieving very high efficiency and low cost systems by using a wider spectral range. In this scope, the recent development of Nanophotonics has triggered the emergence of novel concepts for light management in photovoltaic cells. This includes incident light trapping and strategies to control light absorption in thin film photovoltaic cells especially with Photonic Crystal (Ph.C.)[1]: it enables to reach higher absorption increase with a high angular tolerance, over the whole solar spectrum that enables to reach a very high absorption increase, over the whole solar spectrum. These approaches allow facing specification of light absorption for both solar and indoor light. In the first case, the major issue is to enable a broadband absorption enhancement mostly under a normal incidence while in the second case, the Ph.C parameters are adjusted to achieve a robust optical response over a broad range of solid angles as well as to match the particular emission spectra of the indoor light sources.

Acknowledgements, This work was supported by Orange Labs Networks contract 0050012310-A09221, by the European Union (EU) PhotoNVoltaics project (Grant Agreement No. 309127), by the ANR "Sparcs" and "Nathisol" project and by the "Repcop" IMUST project.


Grace Hechme-Doukopoulos

Sandrine Brignol-Charousset

Jérôme Malick

Claude Lemaréchal

The short-term electricity production management problem at EDF 1I n t r o d u c t i o n

Production management aims at meeting the demand of customers at minimum cost. Since electricity cannot be stored, an electricity producer mainly faces the permanent challenge of matching generation and demand to avoid physical failures of the production system. This article presents how EDF (French Electricity Board) solves this optimization problem: we sketch some issues and the resolution scheme, and we highlight parts of the numerical optimizationp r ocess of the short term management.

From long-to short-term management EDF manages a mix of generation units, composed of nearly 60 nuclear plants, 100 classical thermal plants (coal, fuel, gas,c o m b i n e d cycles), and 500 hydraulic plants dispatched in 50 valleys (ah y d r ovalley is a set of rivers, grouped in such a way that two different valleys are geographically independent). The electricity generation management at EDF consists in determining a strategy (illustrated by Figure 1) which manages the chain of decisions.

The overall decision-making problem is highly complex and way too difficult to be solved globally. Starting from long-term decisions to the short-term ones, a time horizon decomposition amenable to dynamic programming is thus used. Each horizon computes Bellman values for stocks (reservoirs, nuclear plants, . . . ) to be used by the shorter horizon.

On the longer-term horizons, we take into account uncertainties by using statistical forecast models within a stochastic optimization framework; technical constraints are drastically simplified. By contrast, a very fine vision of the generation mix is necessary fort h e short term. Real technical constraints make the use of stochastics prohibitive; rather, deterministic counterparts are solved.

The main decisions at each time-horizon are the following ones: • On the long term (five to twenty years): to design the generation mix: planning investments, choosing the right kind of plants, forecasting polluting emissions, . . . • On the mid term (one to five years): to define the planning for nuclear outages (refueling and overhaul), to calculate management strategies for the main reservoirs (hydraulic reservoirs, demand side management, polluting emission, fuel stocks, . . . ), to buy fossil fuel and to evaluate the failure risks and associated hedging decisions. • On the short term (a few days to a few hours): to compute production schedules that satisfy the technical constraints and the demand/production equilibrium, and provide marginal costsofthe system.

!"#$%&'$"&()$*+%+,"% -./0$&( !"#$%"!&'(

Aspects of short-term management

We focus here on the shor t-term management problem, commonly called unit-commitment. The decision-making problem is expressed as an optimization problem whose main characteristics are the following:

• large size (10 6 variables, 10 6 constraints): all production plants are modeled with a large number of technical constraints and on a 48 hours horizon discretized in half-hourly time steps; • nonconvex and noncontinuous nature: some production costs have discontinuities and the production variables are discrete; • strict computational limits, due to a very tense operational process: the latest data collection phase ends at 12:30 and the feasible schedules have to be sent to the transport system operator at 16:30. Moreover post-optimization treatments involvinghuman expertise are required; altogether, about 15 minutes are left for solving the optimization problem. This article is mainly devoted to modeling aspects of the problem: we describe the technical characteristics of the productionu n i t si n some details, and we outline the general solution methodology. For more details on the latter, as well as numerical results, the reader is referred to [START_REF] Dubost | A primal-proximal heuristic applied to the french unit-commitment problem[END_REF].

The structure of this paper is then as follows. Section 2 presents technical aspects of the production units (thermal and hydraulic), and their mathematical modeling. Section 3 sketches the methods that are used in practice to tackle the production optimization problem. Current issues and research directions are discussed inS e ction 4.

2D e s c r i p t i o n o f t h e s h o r t -t e r m m a n a g e m e n t p r o b l e m 2.1 Overall optimization problem

The goal of generation management is to compute technically feasible production schedules with a good supply-demand balance at a minimal operating cost.

At a high level, this optimization problem is written as follows. Let T be the discretized time horizon and D ∈ R T the total predicted demand. A production unit v has a production

P v ∈ R T ,a n operating cost c v ,andatechnicalfunctioningdomainP v ⊂ R T .The unit-commitment problem is min v c v (P v ), s.t. P v ∈P v , v P v = D.
(1)

The production units are thus subject to two types of constraints: the global linking demand constraint, and local structural constraints. These local constraints are detailed in the next two sections. Then section 3 explains how to deal with all of these constraints when solving problem (1).

Constraints and cost for thermal units Te c h n i ca l a s p e ct s

Thermal units consist of both classical (coal, oil, gas) and nuclear units since their operating domains are similar. We give a simplified description in the following.

When a thermal unit is turned on, the production level must remain between a minimum and a maximum value, which can vary in time. For instance, the maximum level is equal to zero during refueling periods. All levels between the maximum and minimum cannot be used, and the production levels are discrete. Moreover, production variations must follow several rules, namely: a minimalduration between consecutive level changes, upper and lower bound values, and variation prohibition for the rest of the time period after a level decrease.

Switching on or off a thermal unit is not instantaneous. Specific start-up and shut-down curves must be followed, as well as minimum durations of shut-down. There are also some daily constraints: the number of start-ups, shut-downs, and production level variations are limited in a day.

The production cost of a thermal plant is composed by two parts: af u e lc o s td e p e n d i n go nt h eg e n e r a t i o nl e v e l ,p l u ss o m es t a r t-up costs depending on the duration of the previous shut-down.

Mathematical formulation

Denote by P t v the production level of unit v at time step t ∈ T .Let

T on v [T off v ]b

et h es e to ft i m es t e p sw h e nt h eu n i ti so n l i n e( t h a ti s with

P t v > 0)[ offline(withP t v = 0)].
The constraints on the production levels can be expressed as follows:

• Static constraints: N v being the number of discrete generation levels for v,a n d0

<P t v = P v,
where P v,1 < ••• <P v,n < ••• <P v,Nv .
• Dynamic constraints: the three constraints on the production variations are: the minimal duration between level variations,

if P t+1 v = P t v then ∀τ ∈ [t + 2; t + d min v ], P τ v = P t+1 v ,
the variation prohibition after a decrease

if P t+1 v -P t v < 0 then ∀τ ∈ [t + 2; T], P τ v = P t+1 v ,
and the bound constraints:

∆ v ≤ P t+1 v -P t v d t ≤ ∆ v ,
∆ v and ∆ v being the minimum and maximum values, and d t the duration of time step t. • Start-up or shut-down curves constraints: A start-up [shut-down] curve is a set of different generation levels at each time-step of the start-up [shut-down] period:

{0 ≤ P start,i v ≤ P v ,i ∈ [1,d start v ]},
and

{0 ≤ P stop,i v ≤ P v ,i ∈ [1,d stop v ]},
where

d start v [d stop v
]isthedurationofstart-up[shut-down].Note that the particular curve to follow depends on the duration ofthe previous offline/online period. The constraints are then described as follows:

• Aplanthastofollowaminimumdurationforanyofflineperiod: if P t v = 0 and P t+1 v = 0 then: ∀τ ∈ [t + 1; t + d stop v ], P τ v = 0.
• Ap lan th astof ollo wth eadeq u ates tartin g-u pcu rv ewh eng oing online: if P t v = 0 and P t+1 v = 0 then:

∀τ ∈ [t + 1; t + d start v ], P τ v = P start,τ-t v .
• Aplanthastofollowtheadequateshut-downcurvewhengoing offline: if

P t v = 0 and P t+1 v = 0 then: ∀τ ∈ [t + 1; t + d stop v ], P τ v = P stop,τ-t v .
• The aforementioned daily constraints turn out to make the problem intractable. They are therefore incorporated as penalties p daily in the objective function.

In view of the previous discussions, the total generation cost has the form:

c v (P v ) = t∈T on v {c fixed v,t + c prop v,t P t v + p daily (P t v ,P t-1 v )}+ c start v , (2)
where c start v is a start-up cost depending on the previous offline period.

Constraints and cost for hydraulic units Te c h n i ca l a s p e ct s

Ahydro-plantconsistsofasetofturbinesthatdischargewater from its upstream reservoir into its downstream one. The reverse is also possible for some plants equipped with pumping units: pumping up water at low demand hours allows one to re-use the water at higher demand ones. Unlike thermal or nuclear units, the productiono fa hydro-plant is not computed individually. It is rather optimized in a more global entity, a hydro-valley, that depicts the interaction between a set of hydro-plants and the reservoirs connecting them.

The power delivered by a hydro-plant can take only a finite number of values (designated in what follows as discrete production points). These values correspond to the power produced by its turbines that are switched on successively. Since the time period is short, the considered turbines' rates are fixed, just because the water level in the upstream reservoir is considered as constant.

The production of a hydro-valley is subject to a set of constraints that deal with technical functioning aspects, aimed at preventing a fast degradation of the units or simply at following some external regulations. Of course, in addition to the flows induced by pumping or turbining, a reservoir is subject to outer water inputs duetorain, snow or spillage. Hence, through the time period, the volume of a reservoir is governed by an equilibrium flow constraint that rules these factors.

As for the power plants, their production variations are subject to upper and lower bound constraints. A minimal delay of one hour is also imposed between two production variations of opposite nature. Furthermore, when two reservoirs are connected with both turbining and pumping plants, simultaneous pumping and turbining is forbidden, and a minimal halt of thirty minutes before switching from pumping into turbining (and vice versa) is imposed.

Mathematical formulation

Given a hydro-valley v,w edenotebyU its set of production plants and by R its reservoirs. Each plant u ∈ U is described by a set of turbining/pumping units G(u).E a c hu n i ti sc h a r a c t e r i z e db yi t sfl o w capacity F u,g and its power rate ρ u,g ;unitsar erankedaccordingto decreasing ρ's. At time step t,t hestateofunitg is given by a binary variable e t u,g ∈{0, 1} so that we have

F t u = g∈G(u)
e t u,g F u,g , (the flow capacity of u)

P t u = g∈G(u)
e t u,g ρ u,g F u,g (the power of u).

For all u,t hebinaryvariablesmustfollowasequenceconstraint: The production variation constraints are expressed as:

∀t ∈ [2,T -1], ∀g ∈ G(u), -1 ≤ e t u,g -e t-1 u,g -e t+1 u,g ≤ 0,
for the minimal delay between production variations, and

∀t ∈ [1,T -1], δ u ≤ g∈G(u) (e t+1 u,g -e t u,g )F u,g ≤ δ u
for the bound constraints, δ u and δ u being the lower and upper bounds respectively. Denote by V t r the volume of reservoir r ∈ R at time step t.T h e flow constraint has the following form:

V t r = V t-1 r + u∈N↑(r ) F t-d(u,r ) u - u∈N↓(r ) F t+d(r ,u) u + I t r ,
where N ↑ (r ) [N ↓ (r )]i st h es e to fh y d r o -p l a n t su p[ d o w n ]r e s e rvoir r , I t r is the outer water input, and d(u, r ) is the travel time of water between reservoir r and plant u and vice versa. Note finally that the volume is also subject to bound constraints (resulting from the hydraulicity, environment, or regulations due to the recreational use of the reservoir).

The production cost of a hydro-valley is the global water loss through the time horizon:

c v (P v ) = r ∈R ω r (V 0 r -V T r ).
The value ω r of water of reservoir r is estimated with marginal indicators resulting from mid-term models, giving the future gain if the water is not discharged (remember Figure 1).

3O p t i m i z a t i o n m e t h o d s 3.1 Solving the overall problem via decomposition

In our overall optimization problem (1), v indices the thermal plants of Section 2.1 and the hydro-valleys of Section 2.2. Then we see that each P v depends on no other P v ,a n dt h a tt h eb a l a n c ec o n s t r a i n t v P v = D is the only link between the "local agents" P v .T h e problem is thus clearly decomposable and, as already seen in [START_REF] Bertsekas | Optimal shortterm scheduling of large-scale power systems[END_REF], Lagrangian relaxation is an attractive approach. Thus, for given dual variable λ ∈ R T ,(1)isr eplacedbythedecomposed problem

θ(λ) := min Pv ∈Pv v c v (P v ) + λ • D - v P v = λ • D + v min Pv ∈Pv c v (P v ) -λ • P v (3)
and the issue becomes that of finding an adequate λ,s oa st or eproduce a solution of (1). To this end, duality theory (see, e.g., [START_REF] Grinold | Lagrangian subgradients[END_REF][START_REF] Lasdon | Optimization Theory for Large Systems[END_REF][START_REF] Geoffrion | Duality in nonlinear programming: a simplified applications-oriented development[END_REF][START_REF]Lagrangian relaxation[END_REF]) tells us that: (i) If an optimal solution P(λ) of ( 3) is feasible in [START_REF] Bertsekas | Optimal shortterm scheduling of large-scale power systems[END_REF], then it is also optimal in (1). (ii) To achieve this, λ must maximize the dual function θ of ( 3).

(iii) This function is concave, D -v P v (λ) ∈ R T being a subgradi- ent (of -θ at λ).
(iv) However, the converse in (ii) is false: finding a λ maximizing θ does not necessarily yield a primal optimal P( λ).U s u a l l y , v P v (λ) ≠ D for any λ ∈ R T ,evenforλ = λ. (v) Nevertheless, the dual problem (ii) does provide a certain primal point P ={ Pv } v which solves a certain convexified form of (1); the Pv 's need not lie in P v but v Pv = D. (vi) Besides, a dual optimum λ gives the marginal cost of the linking constraints v P v = D,a ssociatedwiththecon v exification alluded to in (v). Accordingly, a two-phase strategy is adopted.

• Phase I -maximizing θ(λ) θ(λ) θ(λ).P r o p e r t y( i i i )m a k e s( i i )p o s s i b l ea n d common approaches use the popular subgradient algorithm. Instead, the present operational software uses the bundle algorithm of [START_REF] Lemaréchal | Variable metric bundle methods: from conceptual to implementable forms[END_REF], which in turn uses a quadratic solver written by K. C. Kiwiel. A first advantage is robustness:ar e l i a b l ed u a lo p t imum λ is computed which, according to (vi), provides useful information on the marginal prices of the demand D in (1). Besides, ap r i m a lp o i n t P as described in (v) is also obtained. We will see in the forthcoming sections that hydraulic valleys cannot always be optimized exactly; this results in a noisy θ,whichishandledb y the technique of [START_REF] Kiwiel | A proximal bundle method with approximate subgradient linearizations[END_REF]. • Phase II -producing schedules. Because of (iv), solving the dual problem as above can only be viewed as a first step toward solving (1). It is therefore followed by a second phase, aimed at computing schedules that do lie in P v ,whilerealizingagoodcompromise between minimizing the cost and satisfying the balance equation.

The method currently used is based on augmented Lagrangian [START_REF] Cohen | Decomposition coordination methods in large scale optimization problems. the nondifferentiable case and the use of augmented Lagrangians[END_REF] where a quadratic stabilization term is added to the dual function.

Since the quadratic term destroys the decomposability property, a" p a r t i a ll i n e a r i z a t i o n "a si n[ 2]i sa p p l i e d .A l t o g e t h e rt h el o c a l problems of (3) are replaced by

min Pv ∈Pv c v (P v ) -λ • P v + r |P v -Q v | 2 (4)
where the "stability center" Q v is just the previous iterate P k -1 v (thus an initialization P 0 is required). In order to assess schedules satisfying all technical constraints of Section 2, while not matching the linking constraints, a "total cost"

C(P) := v c v (P v ) + π D - v P v (5)
is introduced, where π penalizes the balance mismatch. Convergence of the model is measured as the gap between the value θ( λ) of the dual function computed in Phase I and the total cost of the primal solution obtained in Phase II (from weak duality, thisgapgives aboundfortheoptimalcostC).

Solving the sub-problems Thermal units

As t a n d a r dM I Pf o r m u l a t i o nw o u l db eq u i t ec o m p l e xa n dr e q u i r e considerably high computational time to obtain a satisfactory solution. A specific dynamic programming approach has been developed to solve the thermal sub-problems, which can be outlined as follows.

Af ou r -dimen s ion als tate{S 1 ,S 2 ,S 3 ,S 4 } is defined: S 1 represents the online/offline state (S 1 = 1 if the plant is online, S 1 = 0 if not), S 2 = P v is the discrete production level, S 3 represents the sign of the last production variation (S 3 = 1 for an increase, 0 otherwise), S 2 = d v represents the duration of the current online/offline period. At each time step t,t h es etofau t h or i zeds t at esi scal cu l at edt aki n g into account all the production constraints (limits on the production levels, halts . . . ). Authorized transitions between states at different timesteps are then computed taking into account the timing constraints (minimum durations, start-up curves . . . ).

Costs associated to each transition are then calculated: a transition to an offline state costs 0;at r a n s i t i o nt oag e n e r a t i o ns t a t ei s associated to the cost

v i = min tr∈Tri [C(tr) + Vb v tr -1 (i) ]
is the Bellman value of node i,w her etr -1 (i) is the node connected to node i by transition tr, C(tr) is the cost associated to transition tr.

Hydro-valleys

The hydraulic sub-problems, modeled as MIP's described in Section 2.2, cannot be solved to optimality in a reasonable computing time. This is the reason why three versions of the model are at stake: (a) the actual implementation currently in operation uses a continuous relaxation; combinatorial constraints are taken into account only in Phase II with the help of various heuristics; (b) a forthcoming version will keep the continuous relaxation in Phase I only, while Phase II will solve inaccurately the actual model 2.2; (c) a third version is planned, where inaccurate solutions oftheactual model will be computed in both phases. Effort is currently focused on version (b); Section 4 will explain why version (c) has been postponed so far.

Numerical illustration

Let us illustrate the behaviour of the forthcoming version b)ab o v e. The code is distributed and runs on a cluster of 32 processors.I t performs around 500 total iterations for each phase. An iteration takes about 0.1 seconds for Phase I, and 1.5 seconds for Phase II (remember that Phase I solves "easy" hydraulic subproblems). The total computational time of one run is therefore around 900 seconds.

On average over one year, Phase I optimizes θ within 0.1 % and produces a convexified P satisfying the balance constraint within 0.1 % as well. Phase II produces a schedule P ,whosetotalcostC( P) is optimal within 1.3 %.

Tw o fi g u r e s b e l o w g i v e a n i d e a o f t h e p r o g r e s s i o n o f t h e a l g o r i thm, for both phases. The evolution of the dual function (3) through Phase I is depicted in Figure 2. As for Phase II, Figure 3 displays two curves: the balance mismatch | P v -D| (averaged over the time period [0,T]), and the total cost of (5). Both figures use a logarithmic scale; for industrial privacy, all values have beennormalized as follows:

for n = 1,...,N, a n → ân = a n -a a 1 -a , with a = min(a n ).
Good convergence behavior is sometimes difficult to achieve (especially in Phase II). For instance, we can remark in Figure 3 that the best solution was found at iteration 414 (â 414 = 0), and the method carried on for almost 100 additional iterations without being able to improve it.

! "! #!! #"! $!! $"! %!! %"! &!! &"! "!! '()*+(',-. /0+1230-4(',-

4P e r s p e c t i v e s

Including all possible real-life constraints of an electricity production management problem is pure dream (remember the human postprocessing mentioned in Section 1). The model is therefore regularly improved, in order to better reflect reality and to achieve better numerical performances.

For instance, Phase I of the actual implementation (a) "sees"a less constrained hydraulic model; implementing version (c)s h o u l d be desirable. However, it turns out that inserting the true model in Phase I results in chaotic λ.T h i su n d e s i r e db e h a v i o u rm i g h tb ed u e to stiff hydraulic constraints (which impacts the balance constraints), or to inaccurate computations of the dual function [START_REF] Cohen | Decomposition coordination methods in large scale optimization problems. the nondifferentiable case and the use of augmented Lagrangians[END_REF]. Further analysis is needed to fix this question; an important question because Phase I not only initializes Phase II but also provides marginal indicators about costs of the demand ( λ mentioned in (vi) of Section 3.1).

Another point concerns Phase II, which uses a local search method strongly dependent on the initial point. Moreover thea lgorithm does not have guaranteed convergence properties on this nonconvex problem. Alternative methods are worth investigating to improve this phase.

Grace Hechme-Doukopoulos, EDR R&D, 1 avenue du Général de Gaulle, 92141 Clamart, France. grace.doukopoulos@edf.fr Sandrine Brignol-Charousset, EDR R&D, 1 avenue du Général deG a u l l e , 92141 Clamart, France. sandrine.charousset@edf.fr Jérôme Malick, CNRS, Lab. J. Kunztmann, INRIA, 655 avenue de l'Europe, Montbonnot, 38334 Saint Ismier, France. jerome.malick@inria.fr Claude Lemaréchal, INRIA, 655 avenue de l'Europe, Montbonnot, 38334 Saint Ismier, France. claude.lemarechal@edf.fr

Figure 2 .

 2 Figure 2. Evolution of the (normalized) dual function along the iterations

Figure 3 .

 3 Figure 3. Evolution of the (normalized) balance mismatch and total production cost

  Denote by u T and u P the turbining and pumping plants respectively. The constraints

	∀t, e t uT ,1 + e t uP ,1 ≤ 1
	prohibit simultaneous pumping and turbining, while the minimal halt
	delay before a flow mode switch can be imposed by:
	∀t ∈ [1,T -1], e t uP ,1 + e t+1 uT ,1 ≤ 1,e t+1 uP ,1 + e t uT ,1 ≤ 1.
	∀t, ∀g ∈ G(u),	e t u,g+1 ≤ e t u,g ,

to have P t u equal to a discrete production point at each time step t. Note that it is then sufficient to apply the pumping/turbiningt e c h n ical constraints for g = 1 only.

  ; a transition to a start-up curve is associated to the sum of the generation cost and the start-up cost.Dynamic programming is then applied, calculating backward the Bellman value of each state. The graph is a set of nodes and a set of transitions between nodes. Call Tr i the set of transitions going to node i;t hen

	c fixed v,t + c	prop v,t P t v + p daily (P t v ,P t-1 v ) -λ t P t v
	in the Lagrangian (2) (3)Vb

Discussion Column

Antonio Frangioni

Unit Commitment problems: A tale in Lagrangian optimization

The paper provides an account of the current status of a multi-luster collaboration between academia and industry about the application of Lagrangian techniques for the solution of Unit Commitment(UC) problems in electrical power production.

UC problems have played an important role, perhaps as significant as that of multicommodity flows, to popularize solution techniques based on Lagrangian relaxation both in the mathematical programming community and within practitioners (in particular, in this case in the electrical engineering community). This is due to a number of factors:

• UC is indeed a large-scale problem with both nonlinear and discrete components. As such, it has been until recently firmly out of reach of solution techniques based on general-purpose mixedinteger solvers, and specialized approaches have been a necessity. However, single-unit scheduling problems, both for thermal and hydro units, are relatively easy to solve with appropriate approaches (typically dynamic programming and flow/linear programming techniques). • As a consequence, UC, at least in some of its "easiest" versions, is incredibly well-suited for the technique. Lower bounds obtained by Lagrangian relaxation can have a ludicrously small inherent gap, as low as a small fraction of a percentage point, especially for the largest hydro-thermal instances that used to be the norm in several relevant application environments (and still are inthatdescribed in the Scientific Contribution). Each Lagrangian iteration is quite fast, which coupled with a good method to update the multipliers produces these terrific bounds quickly enough. • UC has really tight operational constraints, making the development of methods capable of quickly and reliably producing goodquality solution of utmost importance. • UC is, or at least used to be, the almost perfect example of an "easy sell" for advanced applied research. The problem is huge in terms of costs involved and has to be solved daily, thus small savings rapidly add up to incredibly vast sums. Optimizing the schedules of production units has no noticeable negative effect, and therefore no meaningful opposition by any of the parties involved.

The problem used to be of concern of a single monopolistic producer -often state-owned -with almost unlimited financial resources. This is not to say that UC is an easy problem. Indeed, successful application of Lagrangian techniques to UC (as well as to other difficult combinatorial problems) requires several nontrivial stepswhichhave motivated relevant theoretical contributions, to which thea u t h o r s of the Scientific Contribution are by no means unconnected: • algorithmic recovery [START_REF] Kiwiel | A proximal bundle method with approximate subgradient linearizations[END_REF]o ft h ec o n t i n u o u ss o l u t i o n so ft h e" p r imal counterpart" of the Lagrangian Dual [START_REF] Lasdon | Optimization Theory for Large Systems[END_REF]; • fast converging bundle methods using techniques like disaggregation in the master problem and preconditioning [START_REF] Cohen | Auxiliary problem principle and decompositionofoptimization problems[END_REF];

• general yet efficient approaches for recovering primal feasible solutions out of a Lagrangian dual [START_REF] Cohen | Decomposition coordination methods in large scale optimization problems. the nondifferentiable case and the use of augmented Lagrangians[END_REF], comprised an entire new class of Lagrangian-based heuristics [START_REF] Grinold | Lagrangian subgradients[END_REF]. All this illustrates a very nice instance of a central credence (hope? wishful thinking?) in the mathematical programming community, and in applied mathematics in general: important practical problems motivate relevant theoretical developments, sophisticated mathematical theory is necessary to solve crucial practical applications.

Research on UC problems is by no means over, due to several factors: • Most countries in the world have been transitioning from electrical systems based on monopolistic producers to those based on free market, where competition between producers and consumers (regulated by a central authority, typically taking care of the electrical network) is supposed to increase the overall efficiency. In this setting, the UC problem takes different forms for different actors, sometimes complicating matters considerably (most of the system is in the hand of other decision makers, whose behavior is unknown), sometimes simplifying them somewhat (each decision maker needs to model only his units, which are a subset of the whole system, and the effects of the constraints on the transmission network is somewhat less pronounced). • It is possible (perhaps desirable) that the future will bringveryrelevant changes in the characteristics of the generating units. Other than several hundreds of large and relatively reliable plants, many thousands of smaller and less reliable units based on renewables -ore v enm u chmor ewi t hfu elcel l scar si nt h een vi s agedh yd r ogen economy -may have to be taken into account. Distribution grids may also undergo substantial updates to the so-called "smart grids". All this may clearly have very profound impacts on theUC models to be solved.