Alexandre Mouradian
email: alexandre.mouradian@u-psud.fr

Extreme Value Theory for the Study of Probabilistic Worst Case Delays in Wireless Networks

Keywords: Extreme Value Theory, Worst-Case delays, Large-Scale

Wireless networks are more and more envisioned to be used as a support for critical safety applications. It is notably the case for large scale wireless networks such as vehicular networks, for which safety is one of the main motivations for their development. In this context, the system designer must be able to predict bounds on Quality of Service (QoS) parameters such as delay and delivery ratio. Nevertheless, obtaining strict bounds on such parameters is often difficult because of the unpredictability of the environment (electromagnetic interference, user mobility, etc). Even when the environment is well characterized, the derivation of the bound might be impractical because of the complexity of the models and techniques (the combinatorial explosion problem of model checking is an example) or the bound derived might not be tight (for example with Network Calculus). On the other hand, classic network performance evaluation techniques (stochastic modeling, discrete event simulation, experimentation, etc) usually focus on parameter averages and give very few insights on the extreme deviations from these averages which are of paramount importance for critical applications.

In this paper, we propose to use the Extreme Value Theory (EVT) in order to investigate worst case delays in wireless networks. EVT is a statistical tool which allows to make predictions on extreme deviations from the average. These statistical predictions can be made based on data gathered from simulation or experimentation. We first briefly introduce the technique. Then we discuss its application to the study of delays in wireless networks and we illustrate our discussion with a case study: safety applications in vehicular networks.

Wireless Networks, Real-Time

Introduction

Real time critical applications are applications which have strong timing requirements. If they miss a deadline it can have dramatic consequences on the environment or even on human lives. More and more of these critical applications are now distributed and thus rely on networks. One example, that will be considered through this paper, is safety applications for connected cars. These applications are one of the main motivation for the deployment of Vehicular Adhoc NETworks (VANETs) [START_REF] Hartenstein | VANET: vehicular applications and inter-networking technologies[END_REF] for cars. These road safety applications mainly aim at providing an assistance to the driver in order to avoid car accidents and are described in more details in section 5.1. Such critical applications have strong timing requirements. It is thus of paramount importance to design network protocols which can provide bounded worst case delays. But more importantly, the bounds have to be known and have to comply with the requirements of the target application.

Unfortunately, most of the performance evaluation techniques of the literature such as stochastic models, simulation and experimentation focus on parameter averages [START_REF] Jain | The art of computer systems performance analysis[END_REF] and give very few insights on extreme cases. To address this issue, formal methods have been developed specifically to study real-time critical systems [START_REF] Baier | Principles of Model Checking[END_REF] [START_REF] Boudec | Network calculus: a theory of deterministic queuing systems for the internet[END_REF]. These methods aim at deriving bounds on the response time of the system and prove that the system will never miss a deadline. Nonetheless, many problems may arise when using these methods. First, it is often difficult to define and predict the behavior of the system because it may depend on complex probabilistic environmental events. For example, a packet may be lost because of unexpected electromagnetic interferences or mobility. Most of the classic formal methods of the literature do not allow to model efficiently this kind of events [START_REF] Baier | Principles of Model Checking[END_REF] [START_REF] Boudec | Network calculus: a theory of deterministic queuing systems for the internet[END_REF]. Even when it is possible to handle such probabilistic events, formal methods allow to prove properties only on a model of the system. The level of details of the model is often limited because if it is too complex, the use of formal methods can become impractical or even impossible. It is the case, for example, for the model checking [START_REF] Baier | Principles of Model Checking[END_REF] technique whose combinatorial explosion is a well known limitation (this issue is evoked in Section 2).

In this paper, we propose to estimate the probabilistic worst case delay in a network using statistical tools. The probabilistic worst case delay is defined as the probability that the maximum delay is less than a given value (the delay can be a packet end-to-end delay, an inter packet delay, a one-hop delay, etc.). The main advantage of the statistical approach is that it allows to evaluate directly the real studied system (or a highly detailed simulation model) instead of working on an abstracted theoretical model. Moreover, the obtained probabilistic worst case delay has good chances to be less pessimistic than the worst case derived using classic formal methods as it is the case for worst case execution times in the literature [START_REF] Lu | A statistical response-time analysis of real-time embedded systems[END_REF].

The statistical method used in this paper is Extreme Value Theory (EVT) [START_REF] Beirlant | Statistics of extremes: theory and applications[END_REF]. It is presented in details in sections 3 and 4. The method can be summed up in the three following steps:

1. Produce/Gather data (by simulation or experimentation). 2. Extract extreme values from the data (maxima or values over a threshold). 3. Fit extracted values to a probability distribution predicted by the theory.

In this paper, in order to demonstrate the effectiveness of the method in the context of probabilistic worst case delay estimation in networks, we apply EVT to the case of VANETs safety applications. This choice is motivated by the fact that classic formal methods have difficulties to handle such networks because of the scale and the high mobility of the network and the error-prone wireless medium. We gather the data from extensive simulation of a large scale realistic urban vehicular network.

The key contributions of this paper can be summed up as follows. This work represents, up to our knowledge, the first attempt to apply EVT to the study of probabilistic worst case delays in wireless networks. Moreover, we simulate the vehicular network safety applications using a realistic large scale mobility trace [START_REF] Uppoor | Large-scale urban vehicular mobility for networking research[END_REF]. This paper is with [START_REF] Noori | A novel study on beaconing for vanet-based vehicle to vehicle communication: Probability of beacon delivery in realistic large-scale urban area using 802.11p[END_REF] one of the first evaluation of vehicular critical applications using the 802.11p [START_REF] Jiang | Towards an international standard for wireless access in vehicular environments[END_REF] standard in a realistic large scale urban environment ( [START_REF] Noori | A novel study on beaconing for vanet-based vehicle to vehicle communication: Probability of beacon delivery in realistic large-scale urban area using 802.11p[END_REF] focuses on the probability of delivery, and we focus on the probabilistic worst case delay).

We can notice that even if we consider VANETs safety applications in this paper, the method and discussions we develop are in principle applicable to any computer network.

This paper is an extension our previous work [START_REF] Mouradian | Study of probabilistic worst case inter-beacon delays under realistic vehicular mobility conditions[END_REF] and explore in more details the EVT techniques and its applicability to the study of delays wireless networks. We notably add the description and the application of a second theorem of EVT and we study the parametrization of the method, whereas [START_REF] Mouradian | Study of probabilistic worst case inter-beacon delays under realistic vehicular mobility conditions[END_REF] is more focused on the application.

The remainder of the paper is organized as follows. In section 2, the related work is presented and commented. In section 3, we introduce EVT's main theorems. Section 4 consists in a discussion on the application of EVT to the study of large delays in wireless networks. In section 5, we introduce safety applications for VANETs, we present the simulation setup and we apply EVT to study the delays of vehicular networks safety applications. Section 6 provides the conclusion remarks and lists future works.

Related work

The scientific literature concerning network performance analysis focuses mostly on parameter averages [START_REF] Jain | The art of computer systems performance analysis[END_REF]. Indeed, performance evaluation techniques such as theoretical modeling (notably stochastic models), simulation and experimentation mainly deal with throughput, loss rate (or delivery ratio) and delay averages metrics. Nevertheless, for critical applications, averages are not sufficient [START_REF] Olderog | Real-time systems: formal specification and automatic verification[END_REF]. In the case of critical real-time applications, if a packet delay deviates from the average and misses a deadline, the consequences on the environment or even on human lives can be catastrophic [START_REF] Olderog | Real-time systems: formal specification and automatic verification[END_REF]. To deal with this issue, over the last decades, the real-time systems research community has developed methods and models to formally derive worst case delays and formally prove that a system respects timing constraints.

The main formal methods used to check timing behaviors of systems and derive the worst case response time are theorem proving and model checking [START_REF] Clarke | Formal methods: State of the art and future directions[END_REF]. Theorem proving consists in expressing the system behavior as mathematical formulas and proving that the system satisfies a desired set of properties. Process algebras [START_REF] Baeten | A brief history of process algebra[END_REF], for instance, fall into this category. In the case of computer networks, Network Calculus [START_REF] Boudec | Network calculus: a theory of deterministic queuing systems for the internet[END_REF] provides a powerful formalism to derive worst case end-to-end delays. Nevertheless, it suffers from some limitations: the derived bound can be pessimistic which leads to design oversized systems. Moreover, Network Calculus is not adapted to dynamic networks: it cannot easily handle load balancing or mobility for instance [START_REF] Boudec | Network calculus: a theory of deterministic queuing systems for the internet[END_REF].

On the other hand, timed model checking proposes a method to automatically and exhaustively explore all the behaviors (executions) of the modeled system in order to assess that its timing behavior is correct (that it respects a set of properties) [START_REF] Baier | Principles of Model Checking[END_REF]. As this method explores all the possible behaviors of the system, the exact worst case delay can be found. Nevertheless, the main drawback of this method is what is called the combinatorial explosion problem: the number of possible behaviors of the system increases exponentially with the number of variables and clocks [START_REF] Baier | Principles of Model Checking[END_REF]. This problem is the main limitation of the technique, in the literature [START_REF] Fehnker | Modelling and verification of the lmac protocol for wireless sensor networks[END_REF] [15] the model checking technique allows to verify timing properties on wireless networks composed of at most a dozen of nodes which is not sufficient for most of modern networks.

In the literature, most of the formal verifications of real-time systems rely on predictability of the behavior of the system. Nevertheless, in reality, unexpected errors such as packet losses can occur. In order to handle this issue, probabilistic formal methods have been proposed. Probabilistic model checking [START_REF] Kwiatkowska | Automatic verification of real-time systems with discrete probability distributions[END_REF] allows to assess that a system model respect some probabilistic properties (for example, "with probability higher than 0.9995 the end-to-end delay is lower than 1 second"). This method have been applied to network protocol verification [START_REF] Kwiatkowska | Probabilistic model checking of the IEEE 802.11 wireless local area network protocol[END_REF], but suffers from the same scalability problem as classic timed model checking. Network Calculus also possesses its probabilistic or stochastic counterpart [START_REF] Vojnovic | Stochastic analysis of some expedited forwarding networks[END_REF] [START_REF] Jiang | A basic stochastic network calculus[END_REF]. It allows to express stochastic delay bounds instead of deterministic ones. Nevertheless, it sufferers from the same drawbacks as the classic formalism (bounds might not be tight and it lacks a representation of the network dynamic).

To sum up, the presented methods to derive worst case delays in networks either do not scale up or do not provide tight bounds. In the past few years, the real-time computing community have made the same observation concerning the study of worst-case execution times of programs, and develop an alternative statistical approach [START_REF] Edgar | Statistical analysis of wcet for scheduling[END_REF] [5] based on EVT [START_REF] Beirlant | Statistics of extremes: theory and applications[END_REF].

In the literature, EVT has been extensively used in very different contexts: extreme rainfalls [START_REF] Shukla | On the proficient use of gev distribution: a case study of subtropical monsoon region in india[END_REF], forest fires [START_REF] Alvarado | Modeling large forest fires as extreme events[END_REF], wind speed [START_REF] Beirlant | Statistics of extremes: theory and applications[END_REF], financial crashes [START_REF] Embrechts | Extreme value theory as a risk management tool[END_REF] studies. EVT has also been used in the context of computer networks for the estimation of traffic peaks or bursts [START_REF] Liu | Application of extreme value theory to the analysis of wireless network traffic[END_REF] [24] [START_REF] Dahab | Application of extreme value theory to bursts prediction[END_REF]. In [START_REF] Uchida | Traffic data analysis based on extreme value theory and its applications[END_REF], the author proposes to study the traffic on an Ethernet network in order to predict traffic peaks. The author shows that the gathered extreme deviations fit very well to a Generalized Pareto distribution as predicted by the theory. In another study [START_REF] Liu | Application of extreme value theory to the analysis of wireless network traffic[END_REF], the authors apply EVT to the study of traffic throughput in wireless networks and show that the generalized EVT distribution is a better match for large deviation prediction than exponential, gamma or lognormal distributions. In [START_REF] Dahab | Application of extreme value theory to bursts prediction[END_REF] the authors fit Ethernet traffic throughput data to a Weibull distribution (also predicted by EVT). Nevertheless, in these applications of EVT to network traffic throughput, the authors arbitrary use only one of the two theorems of EVT and this choice is not clearly motivated. Moreover, the authors of these works do not focus on the study of large delays, but only on throughput.

Another interesting reference on the use of EVT in a networking context is [START_REF] Liu | Delay-sensitive packet scheduling in wireless networks[END_REF]. The authors focus on opportunistic packet scheduling in wireless networks in which the scheduler chooses the node with the best current channel condition to transmit a packet in order to maximize the throughput. A delay analysis of this scheduling technique is proposed using EVT. The authors notably derive the packet delay distribution. Nevertheless, this distribution is not focused on large delays and it is then used to compute a metric based on the average delay. This metric is included in an alternative scheduling algorithm proposed by the authors which reduces the average packet delay, but no insight on large delays is provided.

As we stated previously, in order to find applications of EVT to the study of large delays in computer science, we have to look to the field of worst case execution times. Works such as [START_REF] Edgar | Statistical analysis of wcet for scheduling[END_REF] [5] make use of EVT to derive probabilistic worst case execution times. In this field, the Block Maxima (BM) is usually used and the data is fitted to the Gumbel distributions family.

The novelty of our work comes from the fact that we specifically discuss the application of EVT to delays in wireless networks. In particular, we discuss the validity of the hypothesis of EVT in this context. On the contrary of several papers of the literature, we explore the two available EVT techniques and discuss their pertinence to characterize large delays in networks. Up to our knowledge, this work represents the first attempt to apply EVT to the analysis of worst case delays in wireless networks.

A brief introduction to EVT

Extreme Value Theory have been developed during the 20th century and is now a well established tool to study extreme deviations from the average of a measured phenomenon [START_REF] Beirlant | Statistics of extremes: theory and applications[END_REF]. EVT is built around two main theorems: the Fisher-Tippett-Gnedenko theorem and the Pickands-Balkema-de Haan theorem. As we detail below, the former is interested in the maximum value of a sequence of variables, whereas the latter focuses on the values of a sequence which are above a given threshold.

The Fisher-Tippett-Gnedenko theorem states that given {X 1 , ..., X n } a sequence of independent and identically distributed (i.i.d.) variables, the distribution of M n = max{X 1 , ..., X n } the variable representing the maximum value of the sequence converges (for large n) toward the extreme value distribution characterized by its CDF (Cumulative Distribution Function) denoted G: G(x) = e (-1+γx)

1 γ , with -1 + γx > 0 (1)
with γ a shape parameter of the distribution. Depending on γ, G belongs to one of these three distribution families:

• Frechet: G(x) = e -( x-m s ) -α , for x > m (2)
if the distribution has a heavy tail;

• Gumbel:

G(x) = e -e -x-m s (3)
if the distribution has an exponential tail;

• Weibull G(x) = e -(-( x-m s )) α , for x < m (4)
if the distribution has a finite maximum; with m, s and α the distribution parameters and α > 0 in all cases.

The second theorem of EVT is the Pickands-Balkema-de Haan theorem. It states that given {X 1 , ..., X n } a sequence of i.i.d. variables, the conditional distribution F u (y) = P (X iu < y|X i > u) of each random variable X i of the sequence converges toward a generalized Pareto distribution for large u:

� G(y) = 1 -(1 + (y-m)γ s ) -1 γ , if γ � = 0 G(y) = 1 -e -y-m s , if γ = 0 (5)
with γ the shape parameter of the generalized Pareto distribution. Proofs for both of these theorems are provided in [START_REF] Beirlant | Statistics of extremes: theory and applications[END_REF]. In this paper, we are interested in how to apply them to the study of large delays in wireless networks. To each theorem corresponds a method which can be applied to characterize the distribution of extreme variations of a phenomenon. For the first theorem the method is the Block Maxima (BM) method in which the sequence of measured data is divided into blocks and the maximum of each block is computed. The maxima data is then fitted to one of the three previously mentioned distributions. The second theorem of EVT corresponds to the Peak Over Threshold (POT) method. In this method, a threshold value is chosen (the choice of the value is a difficult question that will be discussed in section 5.4.3) and the data points which are above the threshold are collected and fitted to a generalized Pareto distribution. We can note that this description of EVT only considers univariate analysis, the interested reader might refer to [START_REF] Beirlant | Statistics of extremes: theory and applications[END_REF] for a description of the multivariate case.

In the next section, we discuss how these methods can be applied to the study of delays in wireless networks.

Applying EVT to the study of delays in networks

In this section, we discuss the application of EVT for the study of worst case delays in wireless networks. By delays, we mean the measure of time between two events in the network. The delays studied in networks are of different kinds: end-to-end delays, one-hop delays, round-trip times, interpacket delays, etc. In this section we discuss the applicability of EVT to these measures. In section 5, in order to give an example of the application of EVT, we will focus on the case of inter-packet delays in VANETs.

Gathering data

The first element needed in order to apply EVT is a set of data which is a realization of the sequence of random variables {X 1 , ..., X n } mentioned in the previous section. In our case it will be measures of time. Essentially, the data set is going to be similar as the one represented in Figure 1(a): a sequence of delays (y axis) measured at different points in time (x axis). We can notice that unlike many data sets found in the literature [START_REF] Beirlant | Statistics of extremes: theory and applications[END_REF] [20], delay measures are not regularly spaced in time because events in a network may not occur on a regular basis (notably because of the sporadic nature of data traffic).

We can also notice that, in this paper, we do not make special assumption on the data gathering technique. Nevertheless, in the case study section (section 5), we specifically use discrete-event simulation.

As stated in section 3, in order to apply the EVT theorems the data variables have to be i.i.d.. We have to remark that this hypothesis may influence the data gathering strategy. This issue is discussed in the next subsection and illustrated in section 5.

The i.i.d. hypothesis

According to Fisher-Tippett-Gnedenko and the Pickands-Balkema-de Haan theorems, to apply EVT, the sequence of variable must be independent and identically distributed. The question then is: can it be the case for delays in wireless networks?

Let's first consider two packet flows A and B, following different paths. Can we assume that their packet end-to-end delays, measured at the destinations, are identically distributed? We would tend to answer yes if the network environment and measure conditions are the same for both A and B (same channel conditions, same protocols, fair access to the medium, same class of traffic, same number of hops, etc). This leads us to believe that to apply EVT on network delays we have to be careful not to have great disparities in the studied network like very dense and very sparse areas in the same network.

Concerning the independence hypothesis, we can argue that the hypothesis will hold if we consider networks in a globally stable state. For example if congestion in the network changes too much over time we will observe successive delay measures as correlated in subsets of the sequence. On the contrary if the parameters which influence the network are stable, even if we have local correlations, the sequence of measured delays in the whole network should appear as uncorrelated.

These qualitative statements will be experimentally verified in the case study in Section 5. In the next subsections, we discuss the applications of the two EVT techniques: BM and POT to delays in networks.

Block Maxima

As explain in section 3, the Block Maxima method corresponds to the Fisher-Tippett-Gnedenko theorem. It focuses on the distribution of the maxima of sequences of measures. In this section we discuss the practical details of the application of BM to the study of the maximum delay in wireless networks.

The principle of the BM technique is to divide the data sequence into blocks and to take the maximum of each block. In the literature, a block is often defined as a time interval [START_REF] Beirlant | Statistics of extremes: theory and applications[END_REF]. Figure 1(b) shows an example of application of BM: it is the same data set as Figure 1(a) divided into blocks of size 20 seconds. In each block the maximum is boxed. Then, according to the Fisher-Tippett-Gnedenko theorem the sequence of block maxima must converge to an extreme value distribution. The block maxima sequence can thus be fitted to one of the Gumbel, Weibull or Frechet distributions. The type of distribution the data will converge to is difficult to predict [START_REF] Shukla | On the proficient use of gev distribution: a case study of subtropical monsoon region in india[END_REF]. In the case study section, we thus try the three distributions and conclude thanks to the statistical tests described in Section 4.5.

We can note that the width of the block is an important parameter: it must be large enough to contain sufficient data in order to apply the Fisher-Tippett-Gnedenko theorem (which concerns asymptotic behavior) and not so large to provide a sufficient number of maximum values to be fitted to a distribution. Nevertheless, "sufficient amount of data" is not clearly defined in the literature [START_REF] Lu | A statistical response-time analysis of real-time embedded systems[END_REF]. In practice, in the case of discrete event simulation, a scenario can easily be replayed a large number of times with different random generator seeds in order to produce an important amount of data. This question will be further discussed in section 5.3 while applying the BM method to the VANET safety application case study. In particular, we investigate how the size of the block influences the parameters of the fitted distribution and the goodness of fit.

Peak Over Threshold

The Peak Over Threshold method is an application of the Pickands-Balkema-de Haan theorem. It focuses on the distribution of a variable knowing that this variable takes values greater than a threshold. In order to apply this method, we have to define a threshold and keep only the values of the data sequence which are above the threshold as depicted in Figure 1(c).

First, we have to notice that usually the POT method makes a much more efficient use of the data set [START_REF] Lu | A statistical response-time analysis of real-time embedded systems[END_REF]. Indeed, in the example of Figure 1(a) where we had only 6 values to fit with a distribution in the case of BM (see Figure 1(b)) we now have 22 values for the fitting with the Generalized Pareto distribution, as can be seen in Figure 1(c). Nevertheless, the choice of the threshold is not trivial and has not received much attention in the literature [START_REF] Beirlant | Statistics of extremes: theory and applications[END_REF]. Similarly to the size of the block for the BM method, the value of the threshold must be chosen sufficiently high so that the Pickands-Balkema-de Haan theorem can be applied, but not so high so there is sufficient data points to be fitted to the Generalized Pareto distribution. This issue is investigated in Section 5.4 where the influence of the threshold on the parameters of the fitted distribution and the goodness of fit is investigated.

Moreover, in the POT case, the interpretation of the result is not as straightforward as the BM case. In the latter case, we directly obtain the probability distribution of the maximum delay value so it directly provides us with the probabilistic worst case delay. In the POT case, we obtain the probability distribution of the delay knowing that the delay already exceeds a given threshold. These issues will be investigated and discussed further in section 5.4.

Fitting technique and statistical test

In the two previous subsections, we have described how to retrieve extreme value data from the original data set. We then have to fit this extreme value data to one of the extreme value distributions predicted by the extreme value theorems and assess that the fitted distribution is an acceptable representation of the data thanks to a goodness-of-fit statistical test. In this paper we use the Maximum Likelihood Estimation (MLE) technique to estimate the parameters of the distributions, and the Pearson's chi-squared test and quantile-quantile plots to assess the goodness-of-fit [START_REF] Jain | The art of computer systems performance analysis[END_REF].

The MLE method consists in finding the vector of parameters for the fitted distribution (in our case Frechet, Weibull, Gumbel or generalized Pareto) such that the likelihood function is maximized. In this paper, in order to solve this optimization problem we use the Nelder-Mead method [START_REF] Nelder | A simplex method for function minimization[END_REF] (more precisely, the implementation from the scipy.optimize Python package [28]).

Once the optimal distribution parameters are obtained, we have to verify that the fitted distribution is actually a convincing representation for the data. For that purpose, we use two tools: the Pearson chi-squared test and quantile-quantile plots [START_REF] Jain | The art of computer systems performance analysis[END_REF]. The former is a statistical test which assesses if there is a statistical difference between an observed data frequency distribution and a theoretical distribution. In this paper, we use the implementation from [29]. We can note that this test's statistic offers a quality indicator for the fit which can be used in the case several distributions pass the chi-squared test as in [START_REF] Shukla | On the proficient use of gev distribution: a case study of subtropical monsoon region in india[END_REF].

The quantile-quantile plot [START_REF] Jain | The art of computer systems performance analysis[END_REF] (or Q-Q plot) is a tool which allows to graphically compare two distributions. In our case, it consists in plotting the quantiles of the collected data against the quantiles of the fitted distribution. If the two distributions match, we should obtain the relation x = y. As described in [START_REF] Beirlant | Statistics of extremes: theory and applications[END_REF] and [START_REF] Jain | The art of computer systems performance analysis[END_REF], the plot consists in a set of points (x, y) where x ∈ {x 1 , ..., x n } with {x 1 , ..., x n } the ordered set of data points (in increasing order) and y = F -1 ( i n+1 ) with n the number of data points, i = 1, ..., n and F -1 the inverse CDF of the fitted distribution. If the Q-Q plot points do not fall on the x = y line, several interpretations are possible [START_REF] Jain | The art of computer systems performance analysis[END_REF]. In our case, if the points deviate above the x = y for a x given range (the slope of the curve formed by the point increases), it can be interpreted as an excess of data points compared to the theoretical distribution in this range. On the contrary, if the slope decreases, it indicates a lack of data points compared to theoretical predictions.

Case study : inter-beacon delays of VANET safety applications

In this section, we apply the presented method to a concrete case: the study of the inter-beacon delays of VANET safety applications. We first introduce the context of safety applications for VANET, we then present the simulation setup and apply BM and POT methods to the simulation results. For each method, we discuss the cases in which it could or could not be applied.

Safety applications for VANET

The safety applications are seen as an essential motivation for the deployment of VANETs [START_REF] Hartenstein | VANET: vehicular applications and inter-networking technologies[END_REF]. The main goal of these applications is to avoid car crashes. We can cite few examples of safety applications [START_REF] Consortium | Vehicle safety communications project: task 3 final report: identify intelligent vehicle safety applications enabled by dsrc[END_REF]:

• traffic signal violation which alerts neighbor cars when a user does not stop at a red traffic light;

• electronic brake which alerts neighbor vehicles when a car performs an emergency braking;

• on-coming traffic warning which notifies the driver of on-coming traffic during overtaking maneuvers.

For more examples, the interested reader may refer to a report of the U.S. National Highway Traffic Safety Administration [START_REF] Consortium | Vehicle safety communications project: task 3 final report: identify intelligent vehicle safety applications enabled by dsrc[END_REF], which provides a wide overview and requirements of safety applications, or to Chapter 2 of [START_REF] Hartenstein | VANET: vehicular applications and inter-networking technologies[END_REF] for a more concise description.

The main building block for safety applications is the exchange of periodical one-hop broadcast messages among neighbor vehicles. These messages are called beacons or heartbeat messages in the literature and contain at least information on the cars position, direction and speed [START_REF] Stanica | Broadcast communication in vehicular ad-hoc network safety applications[END_REF] [START_REF] Noori | A novel study on beaconing for vanet-based vehicle to vehicle communication: Probability of beacon delivery in realistic large-scale urban area using 802.11p[END_REF]. In the architecture defined by the ETSI ITS standard [START_REF][END_REF], these messages are called Cooperative Awareness Messages (CAM). In the case of the IEEE WAVE standard [START_REF]Standard for Information Technology -Telecommunications and Information Exchange between Systems -Local and Metropolitan Area Networks -Specific Requirements -Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications -Amendment 6: Wireless Access in Vehicular Environments[END_REF], they are named Basic Safety Messages (BSM). When receiving these messages, each car can build a representation of its environment, analyze the current situation and predict dangerous situations. The period, latency and scope (or range) of the beacons depend on the requirements of the application. For example, according to [START_REF] Hartenstein | VANET: vehicular applications and inter-networking technologies[END_REF] the electronic brake application needs a beacon frequency of 10Hz, a maximum latency of 100ms and a range of 200m to be effective.

In VANETs, these beacon messages are exchanged among cars using Direct Short Range Communications [START_REF] Hartenstein | VANET: vehicular applications and inter-networking technologies[END_REF]. Both U.S. and European standards use variants of IEEE 802.11p [START_REF] Jiang | Towards an international standard for wireless access in vehicular environments[END_REF] which is an amendment of the widely used IEEE 802.11 standard. Since 802.11p is regarded as the standard of choice for the future deployment of vehicular network, we focus on beaconing using this standard. The standards (IEEE WAVE and ETSI ITS) define several communication channels and a unique control channel CCH. The CCH is envisioned to support the beaconing traffic [START_REF] Hartenstein | VANET: vehicular applications and inter-networking technologies[END_REF].

In this context, the vehicles broadcast their safety beacons on a common channel. The main differences between 802.11 and 802.11p are pointed out in [START_REF] Jiang | Towards an international standard for wireless access in vehicular environments[END_REF]. The broadcast procedure remains unchanged and is described as follows. The time is divided into slots. First the sender senses the medium. If it is free, it transmits the beacon. If it is occupied: it picks a random number N uniformly in [0, CW ] (with CW the initial contention window value), then senses the medium and decrements N for each free slot. When N = 0, it transmits the beacon. We can note that unlike the unicast case, there are no retransmissions and thus the CW value is not updated [START_REF] Stanica | Broadcast communication in vehicular ad-hoc network safety applications[END_REF].

With this procedure, messages can collide and thus the neighbors of a sender may not receive some of the beacons. Moreover, other messages can be lost because of the unreliability of the radio links. These message collisions and losses increase the time period between consecutive beacons at the receiver side. In this case, vehicles may not be able to construct an up-todate representation of their environment and prevent efficiently car crashes. Since, the quality of the environment's representation depends on the freshness of the information about the neighbors, the inter-beacon delay is thus a crucial parameter for critical safety applications. In this paper, we therefore choose to study the inter-beacon delays in VANETs in a realistic simulation environment which is described in the next subsection.

Production of the data : the simulation setup

There exist many studies [START_REF] Hartenstein | VANET: vehicular applications and inter-networking technologies[END_REF] which focus on beacon messages for critical applications. The aim of the one we develop in this paper is twofold: it allows to show the applicability and usefulness of the EVT approach for the study of delays in wireless networks, and it allows to reproduce results of the literature [START_REF] Hartenstein | VANET: vehicular applications and inter-networking technologies[END_REF] [31] [START_REF] Kloiber | Update delay: A new information-centric metric for a combined communication and application level reliability evaluation of cam based safety applications[END_REF] [8] [START_REF] Autolitano | An insight into Decentralized Congestion Control techniques for VANETs from ETSI TS 102 687 V1. 1[END_REF] (notably the fact that 802.11 is not adapted for reliable beaconing) about beaconing in VANETs with 802.11 with a realistic mobility scenario [START_REF] Uppoor | Large-scale urban vehicular mobility for networking research[END_REF].

We use the discrete-event simulator ns2 [START_REF]The Network Simulator -ns-2[END_REF] to perform the simulations, the main simulation parameters are described in Table 1. The simulation setup is actually quite classic, we thus focus on the description of the realistic mobility trace and how we use it in the simulator.

The mobility trace we use in the simulations is a realistic micro-mobility trace of the city of Cologne generated by Uppoor and Fiore [START_REF] Uppoor | Large-scale urban vehicular mobility for networking research[END_REF]. The trace covers a 400 km 2 area and a period of 24 hours and contains about 700000 vehicle travels. In this paper, we use the part of the trace available online which covers the 6am-8am period. In Figure 2, we plot the instantaneous positions of the nodes at 8am. Each point corresponds to a vehicle position in the coordinate system provided by the trace (the coordinates are expressed in meters). The trace from 6am to 8am contains more than 300000 different vehicles, it is thus not possible to simulate the whole scenario in ns2. As we are interested in local communications (one-hop broadcasts), we decide to divide the network and restrict the simulations to 1000x1000m squares. The considered squares are highlighted in Figure 2. They contain different types of road traffic (fluid traffic, traffic jams, etc) and different vehicle densities. Even with this space division of the trace, the number of cars in one square can reach several hundreds and, in some cases, the simulations are either very long (dozens of hours) or not possible (the memory of the machine used for the simulation is not sufficient). We thus divide again the trace, but this time into time intervals. Instead of having 2 hours of simulated time we produce subset traces of 200 seconds. Each of the time blocks also contains different traffic conditions, since the traffic changes over time in the trace.

In each simulation, we monitor the inter-beacon delay as well as the emitter-receiver distance. The beacons are emitted at 10Hz corresponding to a 0.1s beacon emission period. The inter-beacon delays we are interested in are measured at the receiver, because it corresponds to the time a node spends without awareness of its neighbors. Each node computes these delays for every of its neighbors. A simulation typically provides around 2.5 millions measurements of inter-beacon delays (it varies depending on the number of cars present during the simulation). In the following sections we detail how the simulations are run and the data processed in order to extract the inputs needed by the BM and POT techniques. We apply both techniques and discuss their pros and cons.

Parameter

Block Maxima

In this subsection, we apply the BM method to study the maximum interbeacon delay distribution in VANETs.

Data set

For the BM technique, we need to divide the data into blocks and retrieve the maximum of each block. We choose to use three different ways of producing the data which is then fitted to EVT distributions:

1. The first one consists in taking the maximum of each block of 200 seconds (corresponding to one run of the simulator) for the whole trace duration and all the highlighted squares in Figure 2. 2. In the second one we take only one square and one portion of time and re-run the simulation for that particular square and time block several times. 3. The third case is the same as the second but we change the order of the beacon start of the nodes at each run (in the second case, the order of beacon start dates is generated randomly once and the same order is repeated in every simulation). These different setups allow us to understand how disparities in the simulation data affects the applicability of the BM method. Indeed, in the first case, the data collected comes from various situations in terms of car traffic amount, network density, etc. Whereas in the two last cases the blocks are more similar to one another (in the second data set there are more correlations between the runs than in the third data set because the beacon start dates are the same).

For setup 1, we run simulations for 13 successive blocks of 200 seconds for each of the 12 considered squares. We take the maximum inter-beacon delay (over around 2.5 million values) for each run and thus obtain 156 values. For setup 2 and 3 we run 300 simulation of the considered block, so we obtain 300 maximum values. In the results presented in the following sections, we only consider the receivers in a 500 meters range from the sender. Even though longer communication ranges are observed given the simulation parameters (see Table 1), we choose to focus on the delay of beacons received from neighbors less than 500 meters away which are the more relevant for safety applications [START_REF] Hartenstein | VANET: vehicular applications and inter-networking technologies[END_REF]. We thus filter out inter-beacon delays for ranges greater than 500 meters from the simulation results. We also investigate the maximum inter-beacon delay distributions for shorter than 500 meters ranges.

Maximum inter-beacon delay distribution

Figure 3(a) is a histogram representation of the maximum delays for the first data set. First, we have to note that the measured maximum interbeacon delays are very large compared to the inter-beacon emission period (0.1 seconds), but we have to keep in mind that these are maximum delays and each value accounts only for the maximum of 2.5 million delay measurements as explained in the previous section. The study of the simulation traces shows that these large values are due to two main reasons: the mobility and the broadcast scheme used. When a node broadcasts its beacon using 802.11p, it cannot detect collisions. Indeed, collisions happen at the level of the receivers and the sender does not know which of its neighbors will actually receive the packet and does not wait for acknowledgments in the case of broadcasting. Moreover, broadcast messages are subject to the hidden terminal problem since the RTS/CTS messages are not used for broadcast. These problems have been highlighted several times in the literature [START_REF] Hartenstein | VANET: vehicular applications and inter-networking technologies[END_REF] [START_REF] Stanica | Broadcast communication in vehicular ad-hoc network safety applications[END_REF]. In order to better comprehend the observed long maximum delays, let's consider the following scenario: first, a node 1 periodically receives a beacon from one of its neighbors 2, then another node, node 3 moves in the neighborhood of 1 and the beacons from 3 collides with those of 2 (in the case of the hidden terminal problem the beacons may constantly collide), then node 3 moves out of range of node 1 again. In this scenario, when node 3 at last get out of the range of node 1, it puts an end to the collisions with beacons from node 2. When node 1 receives the first beacons from node 2 after node 3 went out, the inter-beacon delay is approximately equal to the duration of the presence of node 3 in the range of node 1. In the Cologne trace case, this delay can be of the order of tens of seconds as we observe in the simulations results. Even if these scenarios are very rare, they have to be taken into account in the scope of critical applications such as road safety applications.

Let's now focus on the fitting of the data of the first data set to the different extreme value distribution families. Figures 3(b), 3(c) and 3(d) respectively represent the Q-Q plots of the fitted Frechet, Gumbel and Weibull distributions (fitting has been realized using the MLE method described in section 4). First we observe that none of the distribution fits well to the data. Indeed, none of the graphs show a x = y curve. Nevertheless, we remark that in the Frechet case the curve is piecewise linear which seems to indicate that there are linear relations between the data quantiles and the fitted Frechet distribution quantiles. In the case of the fitted Weibull distribution, we observe that for x and y lesser than 60, the points are approximately on the x = y curve.

The fact that the Q-Q plots are piecewise, seems to indicate that actual maximum inter-delay distribution is multimodal. In fact, from the simulation data, we observe that the different modes correspond to different areas (squares) of the network and different time periods. We conclude that the EVT hypothesis which states that the set of inter-beacon delays are identically distributed does not hold for this data set and thus it is not possible to apply EVT. As a matter of fact, the results of the chi squared tests for all three EVT distributions for this data set are negative as shown in Table 2 (the tests are performed with a 0.05 significance level). We can add that these observations holds for shorter ranges as well. For instance, we also observe multimodal histograms when considering only beacons with a range shorter than 300 meters.

Figures 4(a

× � � Gumbel × × � Weibull × × � Table 2: Chi-Squared test
beacon delays with the expected frequencies from the fitted Frechet distribution and the Q-Q plot of the data against the fitted distribution for the second data set. As stated in section 5.3.1, this set consists of one square and one portion of 200 seconds run 300 times. The chosen square is defined as x ∈ [11000, 12000] and y ∈ [11000, 12000] (cf. Figure 2) and the considered time block is from 1200 to 1400 seconds of the original trace. In this case, as summed up in Table 2, only the fitted Frechet distribution successfully passes the Pearson chi squared test. The Q-Q plot (Figure 4(b)) shows that the fit is good for the lowest values and of a lower quality for the highest values. We can also still discern at least two modes in the frequency distribution in Figure 4(a) (also visible in Figure 4(b), because the points lie over the x = y curve for x < 15 and then under until approximately x = 18). Figures 5(a) and 5(b) present the results for the third simulation setup (the third data set): it is the same as the previous (one square for one 200 second interval run multiple times) but the nodes are starting their beacon emission at different dates in each simulation. The starting dates are in fact uniformly distributed in the first second of the simulation. The results presented in Table 2 indicate that for this data set, all three fitted EVT distributions pass the chi squared test. Figure 5(a) depicts the frequency plot of the inter-beacon delays with the expected frequencies from the three EVT distribution. In Figure 5(b), we present only the Q-Q plot for the fitted Frechet distribution because even if all the distributions pass the chi squared test, the Frechet distribution is the best fit (the one with the lowest test statistic). In this Q-Q plot, we observe, as in the last, that the fit is good for the lower values and less good for higher values. Nevertheless, for this data set, we do not observe multimodal tendency which seems to indicate that the identically distributed hypothesis holds. All the results we have presented so far are for a 500 meters range: we the inter-beacon delays for receivers within 500 meters of the sender. Nevertheless, for most of critical safety applications, the range of beacon emission can be much lower [START_REF] Consortium | Vehicle safety communications project: task 3 final report: identify intelligent vehicle safety applications enabled by dsrc[END_REF]. In Figure 6, we plot the CDFs of fitted Frechet distribution for different ranges. The CDF of the maximum delay express the probability that the maximum delay is under a given value. It corresponds to the probabilistic worst case delay. Thanks to this probabilistic worst case delay, the system designer can state that, for example, "the probability that the maximum inter-bacon delay in a 100 meters range around the sender is less than 5 seconds is 0.9995". Whether this probabilistic delay bound is sufficient or not depends on the considered application. In Figure 6, we can notice that the CDF for higher ranges is lower. This means that the probability that the maximum delay is over a given value is higher for higher ranges. This can be explained by two phenomena: the higher probability of packet loss at longer distances and the hidden terminal problem as explained above in this section.

Impact of the block width

As stated in section 4.3, the width of the block from which the maximum value is extracted can have an impact on the quality of the probabilistic bound obtained when applying EVT. If it is too narrow, the Fisher-Tippett-Gnedenko theorem might not be applicable. If it is too wide, not enough data is available for the fitting with the EVT distributions. Indeed, the MLE technique requires a sufficient amount of data in order to obtain robust models. In [START_REF] Long | Regression models for categorical and limited dependent variables, Advanced quantitative techniques in the social sciences[END_REF], the author recommend to use at least 100 values for MLE. In our case, the number of values depends on the block width: for the same simulation duration, a larger block width involves a smaller set of maximum values.

Figures 7(a) and 7(b) depict the Q-Q plot of the data against fitted Frechet distributions respectively for 100 seconds blocks and 400 seconds blocks. In order to produce the data sets corresponding to these block sizes, we used data set 3. We divided the 200 seconds block in two for the 100 seconds block and united two 200 seconds blocks for the 400 seconds blocks. For the 200 seconds blocks, the number of data points (measured delays) is about 2.5 millions. It is thus half that number for 100 blocks and twice that number for 400 blocks. The number of extracted maxima is greater when the block is smaller : in our case, it is 300 values for the 200 blocks, 600 for the 100 blocks and 150 for the 400 blocks. Following the recommendations of [START_REF] Long | Regression models for categorical and limited dependent variables, Advanced quantitative techniques in the social sciences[END_REF], we did not experiment with larger block width. Figures 7(a) and 7(b) can be compared with the 200 seconds block case for the third data set in Figure 5(b). First we have to notice that the 100 seconds and 200 seconds cases (respectively Figures 7(a) and 5(b)) are very similar: the fit is good for the first quantiles and less for higher quantiles (we can note that in every case, the fitted distribution passes the chi squared test). Interestingly, in Figure 7(b), we observe that the fit is better for 400 seconds blocks. It can be explained by the fact that the Fisher-Tippett-Gnedenko theorem applies for large blocks of data (blocks with high number of values). Because the theorem establishes a convergence to an extreme value distribution when n goes to infinity, n being the size of the sequence of random variables from which the maximum is taken.

Figure 7(c) shows the CDF of the fitted Frechet distributions for different block sizes. We observe that a greater block size produces a higher probabilistic worst case delay: by higher we mean that for a given probability threshold, the delay is greater. For example, if we consider a 0.8 probability to obtain a worst case delay under a given value, for the 100 seconds block case, this value is around 19s and for the 400 seconds block case, it is around 30s. This means that if the chosen block is too narrow, the obtained probabilistic worst case delay might be optimistic.

In the following sections, we move to the application of the POT method to our VANETs simulation results. We then discuss the possible interpretations and uses for the EVT results for both methods.

Peak Over threshold

In this section, we apply the POT method to the study of high interbeacon delays in VANETs. This method is the application of the Pickands-Balkema-de Haan theorem.

Data set

To avoid the applicability problems encountered when applying BM to the three considered data sets, in the POT case, we use only the third data set depicted in section 5.3.1 (one square, one time block, simulation ran 300 times). From this data set, we keep only the values which are over a chosen threshold to fit it to a generalized Pareto distribution.

We first choose the threshold to be 10 seconds. It seems a reasonable choice since we actually observe values above 10 seconds and that 10 seconds is very high compared to the theoretical inter-beacon delay which is 0.1 second. Then, in section 5.4.3, we change the value of the threshold in order to observe its effect on the quality of the fit with a generalized Pareto distribution.

Inter-beacon delay distribution for delays over a threshold

First we have to notice that even if the data fitting process and statistical test is the same as the BM method, the result given by the fitted distribution does not have the same interpretation. Indeed, the distribution obtained from the BM method is the distribution of the maximum delay, whereas the distribution obtained from the POT method is the distribution of the delay knowing that this delay is already over a given threshold. This distinction has already been noticed in section 4.4 and will also be commented in section 5.6. In this section, we investigate the impact of the threshold value on the quality of the fit. In this case, the threshold must be high enough for the Pickands-Balkema-de Haan theorem to be applicable but not too high in order to have a sufficient amount of data to feed to MLE (at least 100 values, as mentioned in Section 5.3.3). Figures 9(a) and 9(b) represent respectively the Q-Q plots of data against the fitted generalized Pareto distribution for 15s and 20s thresholds. First, we have to notice that the higher the threshold is, the lower the number of data points is. In our case, the number of delays over 10, 15 and 20 seconds is 2380, 619 and 208 respectively. We do not use higher thresholds in order to keep the number of values sufficiently high. Figures 9(a) and 9(b) can be compared to Figure 8(b) which is the Q-Q plot for a 10s threshold. We observe that the match between the data and the theoretical generalized Pareto distribution is better when the threshold increases, especially for high quantiles values (points are closer to the x = y line).

Figure 9(c) is the plot of the CDFs of fitted generalized Pareto distributions for different thresholds. We cannot directly compare the distributions for values under 20 seconds, because it is the value of the highest threshold. Nevertheless, we observe that the models for higher threshold are more conservative because the curves do not cross each others and the CDF for higher thresholds converge more slowly to one. Since the distributions for higher thresholds are a better match for the data, we conclude that taking a too low threshold value can lead to underestimate the probability to observe a given high delay.

Comparison of the model with new measurements

Until this point, we have only been interested in the capacity of the EVT model to represent some gathered data. The natural question then is: how good the model is to predict new data? In [START_REF] Uchida | Traffic data analysis based on extreme value theory and its applications[END_REF], the author fits generalized Pareto Distribution to a subset of the available data and shows that the fitted distribution is a good model for the rest of the data set. In this section, we perform the same experiment but for the BM technique and instead of dividing the data set, we produce more data to compare to the model.

As we observed in Section 4.3, we can only produce a good quality EVT model for homogeneous parts of the network. Therefore, in this section, we compare the theoretical model obtained with the 400 seconds block in Section 5.3.3 with the data from simulation of the same square as data set 3, but at different times. In order to produce this data, we ran simulation on this square at different time intervals of the trace with the same setup as the previous simulations (cf. Section 5.2). As in Section 5.3.3, we unite two 200 seconds trace intervals in order to get the 400 seconds block. . In this later interval, the number of vehicles is 20% higher than the previous two intervals. We observe in Fig. 11(a) that the match with the model is not good. Nevertheless, the curve formed by the points is almost linear, which indicates that the distribution is still Frechet. Fig. 11(b) confirms these conclusions. We also remark, as expected, that the model is optimistic compared to the data, because the data is obtained in a denser and thus more loaded network.

In this section, we observe that the model can accurately represent new data for the same network conditions. We also confirm a limitation of the EVT models: they are relevant only for a particular network situation. We can thus ask how we can deal with inhomogeneous networks? As we focus on extreme delay deviations, a good practice would be to be interested in the more conservative model (in our case the one obtained from the densest parts of the network).

Discussions on the use and interpretation of EVT results

EVT provides powerful tools to study large delays in a realistic situation. It allows the system designer to check if the actual system (or a very realistic simulation model) complies with the application requirements. EVT can also be seen as a complementary approach to formal methods: in the case a worst case delay has been derived using formal methods, it can be checked that the EVT probabilistic worst case is compatible with the one provided by formal methods. Moreover, during the system design process, several design options (different protocols, different protocol tunings, etc.) can be tested and their probabilistic worst case delays compared (by comparing the CDF of the obtained distributions) in order to choose the most suited for the considered application.

As mentioned previously, both BM and POT methods can be applied to the study of large delays in wireless networks, but they do not have the same signification. BM provides the probabilistic worst case delay, whereas POT provides a probability distribution of the delay knowing that it is already above a threshold. In the latter case, the probability of the delay to be above the threshold has to be known in order to provide the probabilistic bound on the delays in the network. As stated in section 3, POT provides P (X -u < y|X > u), thus knowing P (X > u), and thanks to the conditional probability formula we can compute P (u < X < u + y). Nevertheless, P (u < X < u + y) is not exactly equivalent to the result provided by the BM method: BM is about the maximum delay (the worst case), whereas POT is about all delays (including the maximum).

In sections 5.3 and 5.4 we investigate the impact of the size of the block and the value of the threshold on the EVT results. We show that if these values are not chosen high enough, the obtained delay distribution can be overly optimistic. A too optimistic bound can lead to a system not sufficiently safe. The size of the block and value of the threshold have thus to be chosen carefully: high enough so the fit is good (as in Figures 7(b) and 9(b)), but not too high so there is sufficient data to perform the fitting and the statistical test.

We can also remark that EVT can provide a probability of extreme deviation from the mean even if those deviations are never observed in reality. Nevertheless, the probability itself depends on the measurements performed on the observed system. If those measurements are not representative of the complete behavior of the system, the obtained probabilistic bound can be too optimistic [START_REF] Abella | Heart of gold: Making the improbable happen to increase confidence in mbpta[END_REF]. The experimentation or simulation conditions have thus to be carefully chosen [START_REF] Abella | Heart of gold: Making the improbable happen to increase confidence in mbpta[END_REF].

Conclusion and future works

This paper aims at studying large delays in wireless networks using the EVT statistical method. We first discuss the application of EVT to the study of large delays in networks. We then apply the two techniques provided by EVT: BM and POT, to the study of inter-beacon delays in VANETs safety applications. We observe that in the BM case, it is the Frechet distribution family which fits best the distribution of maximum inter-beacon delays. This distribution could thus be used as a model of probabilistic worst case in this context. We also remark that EVT cannot be applied in the case the measured delays are not identically distributed (as for the first considered data set). We study the impact of the block size and the threshold value (resp. for BM and POT method) and observe that to chose too low values can lead to a too optimistic probabilistic worst case delay and thus to overestimate the safety of the system. We conclude that EVT is a powerful tool which allows to estimate large delays in networks. It can be used as a complementary tool to formal methods when they fail to provide results or as a way to double check their results with more realistic system models.

EVT allows to deduce a model of the worst case delay based on data samples retrieve from simulation or experimentation. The sampling method is thus of uttermost importance: the sampled executions of the system must be representative of the whole set of its possible behaviors. If it is not the case, the EVT results might be biased. In the future, we plan to investigate the impact of the sampling methods on EVT results.

Figure 1 :

 1 Figure 1: Illustrative example data set

Figure 2 :

 2 Figure 2: Cologne data set

Figure 3 :

 3 Figure 3: Results for all the squares and blocks and 500m range

Figure 4 :

 4 Figure 4: Results for one square during 200 seconds

Figure 5 :

 5 Figure 5: Results for one square during 200 seconds with random beacon start at each run Data set 1 Data set 2 Data set 3 Frechet× � � Gumbel × × � Weibull × × �

Figure 6 :

 6 Figure 6: CDF for different beacon ranges

  (a) Q-Q plot for 100s block size (data against Frechet distribution) (b) Q-Q plot for 400s block size (data against Frechet distribution) (c) Comparison of the maximum delay Frechet distributions for different block sizes

Figure 7 :

 7 Figure 7: Results for different block sizes

Figure 8 :

 8 Figure 8: Results for The POT method with a threshold of 10 seconds

Figures 8 (Figure 9 :

 89 Figures 8(a) and 8(b) depict respectively, the frequency plot of the data with the expected frequencies computed from fitted generalized Pareto distribution and the Q-Q plot of the data quantiles against the fitted distribution data quantiles. In Figure8(b), we observe that the quantiles of the fitted generalized Pareto distribution are a very good match for the ones of the data for values under x = 35, then the fit is of a lesser quality. Nevertheless, the fitted distribution passes the Pearson chi squared test. The fitted general Pareto distribution can thus be considered as a good model for the tail of the inter-beacon delays for this data set.5.4.3. Impact of the threshold value

Figure 10 :Figure 11 :

 1011 Figure 10: Comparison with the following time interval

Table 1 :

 1 Simulation parameters.

		Value
	Bitrate	6 Mbps
	Transmission power 10 dBm
	Preamble Capture	ON
	Simulation area	1000x1000 m
	Beacon size	400 bytes
	MAC and Phy	802.11p
	Propagation model Nakagami m=1
	Beacon frequency	10Hz


Arief Wicaksana

Alban Bourge

Olivier Muller

Frédéric Rousseau

Demonstration of a context-switch method for heterogeneous reconfigurable systems

Nowadays, FPGAs are integrated in high-performance computing systems, servers, or even used as accelerators in Systemon-Chip (SoC) platforms. Since the execution is performed in hardware, FPGA gives much higher performance and lower energy consumption compared to most microprocessor-based systems. However, the room to improve FPGA performance still exists, e.g. when it is used by multiple users. In multi-user approaches, FPGA resources are shared between several users. Therefore, one must be able to interrupt a running circuit at any given time and continue the task at will. An image of the state of the running circuit (context) is saved during interruption and restored when the execution is continued. The ability to extract and restore the context is known as context-switch.

In the previous work [START_REF] Bourge | Automatic High-Level Hardware Checkpoint Selection for Reconfigurable Systems[END_REF], an automatic checkpoint selection method is proposed for circuit generation targeting reconfigurable systems. The method relies on static analysis of the finite state machine of a circuit to select the checkpoint states. States with minimum overhead will be selected as checkpoints, which allow optimal context save and restore. The maximum time to reach a checkpoint will be defined by the user and considered as the context-switch latency. The method is implemented in C code and integrated as plugin in a free and open-source High-Level Synthesis tool AUGH [START_REF] Prost-Boucle | Fast and standalone Design Space Exploration for High-Level Synthesis under resource constraints[END_REF].

I I . D E M O N S T R AT I O N

In this demonstration, we present the context-switch method [START_REF] Bourge | Automatic High-Level Hardware Checkpoint Selection for Reconfigurable Systems[END_REF] implemented in heterogeneous reconfigurable systems using a network-connected framework. SoC-FPGA platforms with a CPU tightly-coupled with an FPGA are being used in the framework. The demonstration framework consists of two FPGA-SoC platforms, a server with tool-chain installed and a network storage disk. We use two different platforms in the framework, a ZC706 Evaluation Board from Xilinx and an Arria V SoC Development Kit from Altera, to show the genericity of our method even for FPGAs from different vendors. The server provides a tool-chain suite of corresponding platforms for configuration purpose and the network storage is implemented with NFS protocol.

A graphical and a non-graphical applications will be used to perform context-switch on the boards. These applications will consume test vectors as input and perform the computations. For the graphical application, an output video will be prepared for each board so attendees can follow from the screen. For the non-graphical application, the flow of the execution will be observed from user's PC connected to the server.

Figure 1 shows general overview of our demonstration framework and the execution flow. A typical execution flow is given below. Other variations of boards and steps are possible.

1) A user connects to Server either via local connection or framework's network, put its application and launch the execution.

2) The configuration of the circuit is generated in Server and saved in Network Storage with its respective input test vectors.

3) The CPU on Xilinx Board which detects the configuration file in Network Storage and the test vectors will program the FPGA and launch the execution. When there is an interruption, it will retrieve the context from FPGA and save it in Network Storage. 4) The CPU on Altera Board which detects the bitstream and the context in Network Storage will program the FPGA and continue the execution. When there is no other interruption, it will finish the execution and put the results in Network Storage.

R E F E R E N C E S

  Demonstration of a Context-Switch Method for Heterogeneous Reconfigurable Systems Arief Wicaksana, Alban Bourge, Olivier Muller, Frédéric Rousseau TIMA Laboratory -Grenoble-INP/UGA/CNRS 46 avenue Félix Viallet, 38000 Grenoble, FRANCE {arief.wicaksana,alban.bourge,olivier.muller,frederic.rousseau}@imag.fr I . I N T R O D U C T I O N

Figure 1 .

 1 Figure 1. Demonstration Framework and its Typical Execution Flow


Romain Dupin
email: romain.dupin@mines-paristech.fr

Andrea Michiorri
email: andrea.michiorri@mines-paristech.fr

Georges Kariniotakis
email: georges.kariniotakis@mines-paristech.fr

DYNAMIC LINE RATING DAY-AHEAD FORECASTS -COST BENEFIT BASED SELECTION OF THE OPTIMAL QUANTILE

Dynamic Line Rating (DLR) is a promising field of research aiming to help network operators face challenges, such as increased penetration of renewable energies and peak electricity demand. Research on realtime overhead line ampacity estimation is currently advanced and, in the last few years, research has started to address medium-term DLR forecasting. The focus is on probabilistic forecasts, in order to select ratings associated with very low probability of occurrence. For this reason, 1%-quantiles are usually selected. In this paper, the authors propose a methodology for selecting the most appropriate quantiles based on a cost-benefit analysis, considering both the economic benefits of an increased line ampacity and the costs associated with a DLR forecast that is higher than its observed value. The proposed methodology is evaluated using realistic weather data on a virtual line connecting Belgium and France.

INTRODUCTION

Nowadays, static seasonal ratings are applied to overhead lines in order to control statutory clearance. The corresponding current limit is traditionally calculated using methods defined in standards such those of IEEE [START_REF]Standard for Calculating the Current-Temperature Relationship of Bare Overhead Conductors[END_REF] or CIGRE [START_REF] Cigre | Thermal Behaviour of Overhead Conductors[END_REF], and considering weather parameters defined as constant for a fixed period of time. This kind of rating is called Static Line Rating (SLR).

Due to its static nature, SLR is bound to be below the instantaneous rating most of the time, and thus restrictive weather characteristics are considered (i.e. low wind speed and high ambient temperature). This restrictive aspect may lead to congestion situations. To overcome this issue, an alternative way of defining the rating has emerged based on a dynamically modified ampacity that depends on real weather characteristics. This kind of rating is called Dynamic Line Rating (DLR). The development of real-time DLR tools is already advanced. A detailed state of the art on DLR technology is presented in [START_REF] Michiorri | Forecasting for dynamic line rating[END_REF]. Adopting DLR is expected to bring several benefits for network operators [START_REF] Khaki | Electric power system cost/loss optimization using dynamic thermal rating and linear programming[END_REF][START_REF] Wallnerstrom | Impact From Dynamic Line Rating on Wind Power Integration[END_REF][START_REF] Greenwood | Investigating the impact of real-time thermal ratings on power network reliability[END_REF]. However, fully exploiting these benefits requires inputting information on DLR not only into real-time processes but also the various decision-making processes related to grid management for the forthcoming hours and days. This requires forecasting DLR for a future time period. DLR forecasting has been addressed in the literature only recently. For medium-range forecasts (6-48 hours), models providing low-quantile forecasts were developed in [START_REF] Ringelband | Probabilistic ampacity forecasting for overhead lines using weather forecast ensembles[END_REF][START_REF] Sun | Probabilistic forecasting of dynamic line rating for over-head transmission lines[END_REF][START_REF] Nguyen | Dynamic line rating and ampacity forecasting as the keys to optimise power line assets with the integration of res. The European project Twenties Demonstration inside Central Western Europe[END_REF][START_REF]Final report on NETFLEX Demo[END_REF]. Indeed in practical implementations, low quantile forecasts are preferred in order to avoid situations where the DLR forecasts are greater than the measurements. Infringing the thermal limit of an overhead line causes the line to sag more, which reduces the statutory clearance to the ground. However, note that in all the above works, the authors arbitrarily selected a quantile for their forecast, usually equal to 1%. In this paper, a methodology is proposed for a dynamic selection of the quantile used for DLR day-ahead forecasts. This is compared with the choice of an arbitrarily chosen but fixed quantile. The proposed methodology is illustrated in the test case of a virtual line connecting Belgium and France, considering the local weather and the day-ahead and balancing markets in the two countries.

METHODOLOGY Optimal quantile selection

A model providing probabilistic forecasts is a model that can calculate at time t, considering the information available , for a horizon h, a distribution function ̂ for the possible values assumed by the parameter ̂

. To use the model in standard decision-making, it is often necessary to translate the probability density function calculated to a single value, for example by selecting the value ̂ corresponding to a specific quantile τ.

The quantile τ can be arbitrarily selected, but it can also be the result of an optimisation, taking into account safety or financial aspects, as shown below. Such a selection is made considering that the forecast error ̂ , has a cost per unit equal to or when its value is respectively positive or negative, as shown in Equation (1).

{ (1)

Considering the above costs, an optimal quantile can thus be selected through the minimization of the function [START_REF] Cigre | Thermal Behaviour of Overhead Conductors[END_REF], the optimization problem to be solved being described in [START_REF] Michiorri | Forecasting for dynamic line rating[END_REF].

( ̂ ) ∫ ( ̂ ) ̂ (2) ( ̂ ) (3)
An example of this approach is shown in [START_REF] Pinson | Trading wind generation from short-term probabilistic forecasts of wind power[END_REF], where the authors present a methodology according to which probabilistic wind power forecasts are used for trading wind generation in an electricity market with the goal of reducing imbalance penalties. The optimal forecast in this application is not necessarily the one that minimises the Mean Absolute Percentage Error (MAPE), but rather the one that minimises financial losses.

If the costs and are independent from and positive, the quantile minimizing this equation can be calculated analytically using formula in Equation ( 4):

(4)

DLR Forecast optimised quantile

The method described above is here adapted to DLR forecasting. We consider that a quantile forecast of the DLR, ̂ can be calculated. In this case, both ̂ and are expressed in MVA. The DLR is considered as the thermal limit of the line, although this value should be reduced by taking into account other criteria due to grid limitations, for example: i) the limited size of balancing reserves on both sizes of the line, ii) the risk of removing N-1 configurations in case a DLR forecast appears to be false, iii) the current stability limits, and iv) the thermal limits of other components, such as circuit breakers or transformers. However, for the sake of simplicity, these constraints are not considered in this study.

The following study is carried out for a line connecting two different electricity markets. The case study was designed to express simply the financial cost at both sides of the line due to errors related to DLR forecasting. As a reminder, as described in [START_REF] Madlener | Power exchange spot market trading in Europe: theoretical considerations and empirical evidence[END_REF], a producer participating in an electricity market can go through four channels:

 The electricity futures market, on which long-term contracts on electricity bids are made.  The day-ahead market, also called the spot market, on which a unique spot price is set depending on the proposed bids.  The intraday market, on which the imbalances that occurred during the day can be corrected. This usually ends from 30 minutes to 2 hours before the time of delivery.  Towards the end of the intraday market and the delivery time, possible imbalances are corrected during balancing by the transmission system operator. Positive and negative imbalances can have different costs.

The economic benefits associated with DLR forecasts are here considered to be dependent from the spot and imbalance costs. This involves assuming that the DLR forecast error has a different financial cost for positive and negative errors:

 If >0, for a line connecting two areas with different spot electricity costs, and (€/MW), the following cost is defined in Equation ( 5):

(5

)
This cost is linked to the fact that a better forecast would have increased the economic benefits relative to the use of the line. It is assumed that the increased rating of the line has no impact on and .  If , the rating of the line is reduced to , and up and down reserves are activated in the two connected areas. If , it causes a cost described in Equation ( 6). In the opposite case, the indexes need to be swapped: [START_REF] Greenwood | Investigating the impact of real-time thermal ratings on power network reliability[END_REF] where is the regulation cost for negative imbalances in the first area. is the regulation cost for positive imbalances in the second area. It is supposed that both these parameters are independent from d.

At this point, considering (4), ( 5) and ( 6), the quantile optimising the financial benefits from DLR forecast can be calculated as in Equation ( 7):

(7)

CASE STUDY

The test case considered here is a virtual line at the border of France and Belgium, connecting the two countries. It is located at the position (3.125°N, 50.375°E, only one point was considered in this study and not the whole length of the circuit), and was studied from 1st January 2014 to 31st December 2015. We considered that the line is equipped with a 175mm² Lynx conductor.

The spot prices for France were provided by EPEX and those for Belgium by BELPEX. The balancing cost data were provided by the two national transmission system operators, RTE and Elia.

The DLR was calculated every 12 hours at the studied position, using reanalysis data provided by the European Center for Medium range Weather Forecasts (ECMWF) and the CIGRE standard method for calculating DLR [START_REF] Cigre | Thermal Behaviour of Overhead Conductors[END_REF]. The parameters used were:  The 10m East/West wind component Uf (m.s -1 ).  The 10m North/South wind component Vf (m.s -1 ).  The ambient temperature Tf (°C).  The solar radiation S set equal to 0 W.m -2 . The DLR forecasts were generated using Numerical Weather Predictions (NWP) provided by ECMWF for the same parameters, at 4 positions close to the studied point. The prediction horizon h of the forecasts was equal to 24 hours. The forecasts were provided with a Quantile Regression Forest method (QRF) [START_REF] Meinshausen | Quantile Regression Forest[END_REF], which was trained with the data from 2014. Data from 2015 was used for the evaluation.

RESULTS

DLR forecasts

Day-ahead DLR forecasts were provided every 12 hours for the studied case, and the 99 percentiles associated with the forecasted DLR were calculated. As an example, the result obtained for one month is shown in Figure 1. Using the MAPE, we can compare the deterministic performances of the model with the ones of a persistence model, whereby the forecast made at t for t + h is equal to the observation at t. A MAPE of 8.1% was calculated for the QRF, and of 11.4% for the persistence model.

Optimised quantile

Two methods were proposed for the quantile selection:

 An arbitrarily selected quantile τ Arbitrary .  A dynamically modified quantile in accordance with the spot prices, selected using Equation [START_REF] Ringelband | Probabilistic ampacity forecasting for overhead lines using weather forecast ensembles[END_REF].

Depending on the values of the balancing costs used, two quantiles are calculated: τ Spot with the mean balancing cost values of the same month during the previous year and τ Spot,Balancing with observed balancing costs at time t + h.

For the first method, the economic benefits linked to the current flowing through the lines were calculated for various quantiles, from 1% to 100%. As seen on Figure 2, the benefits were optimised using the 14%-quantile. This evaluation was made with the formula in Equation ( 8).

( ̂ ) | | ( ̂ ) (8)
Figure 2. Benefits with an arbitrarily selected quantile

With the second method, the quantiles were calculated for 2015. The mean values for each month were provided in Table 1. In order to evaluate the financial benefit of the proposed approaches, 5 cases were tested and compared:

1. The 1%-quantile DLR forecasts were used.

2. The 50%-quantile DLR forecasts were used.

3. The τ Arbitrary -quantile DLR forecasts were used. τ Arbitrary is set as equal to 14%. 4. The τ Spot -quantile DLR forecasts were used. 5. The τ Spot,Balancing -quantile DLR forecasts were used.

The benefits achieved during 2016 for the five cases were compared and the results are shown in Table 2. The results were normalised with respect to the benefits achieved using an arbitrary 1% quantile.

Case

Financial benefits respect to 1% 1%-forecasts 100.0% 50%-forecasts 76.7% τArbitrary-forecasts 115.1% τSpot forecasts 115% τSpot,Balancing forecasts 120.2%

Table 2. Normalized benefits for cases 1 to 5

The analysis of these results leads to the following considerations:

 Using an arbitrary 50%-quantile of the forecasts was counter-productive.  Increasing the chosen quantile from 1% to 14% increased the financial benefits by 15.1%.

 The choice of a variable optimal quantile taking into account spot prices and historical average balancing costs increased the benefits by 15.0%. If real balancing costs at t+h were taken into account, the benefits increased by 20.2%.

CONCLUSIONS

The study presented a methodology for selecting the optimal quantile to determine a forecast DLR obtained using probabilistic methods. The methodology is based on a cost-benefit analysis and the aim is to use it, along with other criteria, to optimize day-ahead DLR forecasts.

The methodology proposed was tested on a test case describing a circuit on which DLR is applied, connecting two electricity market zones with different prices and balancing costs. This case is simple, and more complex situations should be studied further, but the observed results are promising and show potential benefits compared to the standard method using an arbitrarily selected low quantile.

It should be stressed that whilst the choice of the quantile is not influenced by the actual value of the rating, the financial benefit calculated is. This means that the results presented in Table 2 are more dependent on the data used, and in particular on the meteorological data used for rating calculations and forecasts, which are obtained from 12-hour reanalysis. The use of more precise historical weather data is expected to increase the precision of the forecasts and the results, but also to increase the variability of the rating. Moreover, this methodology based on a simple cost-benefit analysis does not take into account other DLR limitations, which should be included in further studies on adapting DLR forecasts to grid conditions. Other criteria, such as the costs associated with increased risks, could be considered when evaluating DLR forecast errors.

Figure 1 .

 1 Figure 1. Consecutive day-ahead DLR forecasts from 01/07/2015 to 31/07/2015.

Table 1 .

 1 Mean optimal quantile selected during 2015.

	Parameter	τSpot	τSpot,Balancing
	January	2.5%	2,6%
	February	2.8%	2,1%
	Mars	4.1%	3,8%
	April	10.9%	10,8%
	May	12.9%	14,7%
	June	8.7%	8,0%
	July	7.4%	8,0%
	August	10.2%	8,8%
	September	15.2%	18,2%
	October	9.3%	8,6%
	November	3.9%	4,9%
	December	2.5%	7,6%
	Mean value	7.5%	8.2%

ACKNOWLEDGMENT

The following companies are acknowledged: ECMWF for access provided to the weather forecasts and reanalysis data; EPEX and BELPEX for the historical data on spot costs; RTE and Elia for the access provided to the historical data on balancing costs.