Florent Coriat

Anne Fladenmuller

Luciana Arantes
email: luciana.arantes]@lip6.fr

Olivier Marin

Crowdsourcing-based architecture for post-disaster Geolocation: a comparative performance evaluation

Keywords: geolocation, DTN, early post-disaster management, mobile devices

In the aftermath of a natural or industrial disaster, locating individuals is crucial. However, disasters can cause extensive damage to the network infrastructures and a generalized loss of communication among survivors. In this article, we present a network support solution that provides a post-disaster geolocation-collecting service that relies on inter mobile device connections. On top of this dynamically built network, survivors' mobile devices exchange information about geolocation of others they have encountered. Such information is routed towards predefined data collection centers using either the DTN Epidemic or Spray and Wait DTN protocol. Experiments were conducted on the ONE simulator and performance evaluation results confirm the effectiveness of our proposal.

I. INTRODUCTION

After a natural or human-made disaster, regular communication infrastructure is often damaged and/or overloaded by witnesses, survivors, or their relatives who keep repeatedly trying to get information about the current situation, in order to help or simply to reassure themselves. Yet global information assessment is a crucial issue for rescuers. Thus, establishing, as soon as possible, a dedicated communication network, until the regular network works normally, remains a top priority and a great challenge [START_REF] Reuter | Ad hoc participation in situation assessment: supporting mobile collaboration in emergencies[END_REF]. Ideally, such a communication network should also provide support for real-time mapping of the disaster area, danger zones and resources, as well as geolocation information of victims and survivors. In other words, the support must help to assess and deal with the emergency situation, mapping accident areas, locating users, warning users about the accidents, and maintaining contact between survivors, rescue teams, and emergency operation centers.

Many existing solutions deploy emergency network infrastructures (e.g. mobile cell sites, balloons, etc.). However, these solutions are often expensive, can take several hours after the disaster to be operational, depend on dedicated equipments, or are frequently restricted to rescue teams.

Hence, considering the above constraints, a feasible, relatively cheap, and easily available solution would be to build an ad-hoc network composed of people's (victims and survivors) mobile devices, i.e., to exploit existing mobile devices without counting on additional dedicated network infrastructure. Since users' mobile devices usually have wireless interfaces (Wi-Fi and/or BlueTooth), it would be possible to establish, maybe intermittently, ad-hoc communication links between mobile nodes, similarly to MANET (mobile ad-hoc network) or DTN (disrupted-tolerant network).

In this paper, we present a post-disaster network support solution that exploits such an ad-hoc dynamically built communication approach, requiring a minimum of fixed support. We consider that dedicated software for disaster situations runs on peoples' mobile devices as well as the existence of well-known places, denoted convergence points CPs (e.g., hospitals, railway stations, schools, etc.). Some of these CPs are also collecting data centers, denoted hotspots. The latter are endowed with processing and storage resources. Seeking to be in safe area when a disaster takes place, people move towards one of the CPs, establishing the ad-hoc communication links between his/her mobile device and those of the persons he/she crosses along the path to the CP. Furthermore, whenever a communication link exists between two persons' devices, they can exchange information about geolocation of other persons they have met. Therefore, users mobility contributes to both build an ad-hoc network and propagate information about users location. Through such a network, users can also be informed about accidents which might help them to find a better path to the most convenient CP.

Since a network composed of persons' mobile devices is intermittently connected, i.e. connections between them and the hotspots are built over time, similarly to DTNs, we applied (and adapted) two well-known DTN routing protocols, Epidemic [START_REF] Vahdat | Epidemic routing for partially-connected ad hoc networks[END_REF] and Spray and Wait [START_REF] Spyropoulos | Spray and wait: an efficient routing scheme for intermittently connected mobile networks[END_REF], for routing geolocation data towards the hotspots. Based on such disaster context, we also propose a mobility model, denoted Danger Movement. Extensive experiments were conducted with both protocols on Danger Movement, varying different parameters, on top of the ONE 1 simulator [START_REF] Keränen | The ONE simulator for DTN protocol evaluation[END_REF]. Performance evaluation results confirm the effectiveness and feasibility of our approach.

The paper is organized as follows: Section II gives a brief background about DTNs and the protocols Epidemic and Spray and Wait. In Section III, we summarizes some existing related work. Our solution is described in Section IV which also includes the description of the Danger Movement. Section V presents and discuss some evaluation performance results with both protocols. Finally, Section VI concludes the paper and gives some directions for future work.

II. DISRUPTION-TOLERANT NETWORKING

Base radio stations are statically placed aiming at offering network coverage to users. However, if they have been damaged by a disaster or the latter caused a power failure, their re-establishment or the deployment of mobile cell sites to complete or replace the failing infrastructure can take from hours to several days, wasting valuable time for victims and rescuers. Thus, autonomous and fast operational solutions to offer some communication support in the first moments of a disaster are crucial in such a context. To this end, disruption-tolerant networking (DTN) technology has been largely considered for post-disaster communications.

A disruption-tolerant network (DTN) is an opportunistic network where each node acts as a router for the network packets. Nodes can be pedestrians' mobile devices, on-board vehicle specialized devices, fixed relays, etc. In [START_REF] Bhattacharjee | Exploring an energy-efficient DTN framework supporting disaster management services in post disaster relief operation[END_REF], the authors present a classification of these types of nodes, their mobility patterns, and communication abilities (terminals, stationary relays, dedicated fixed or mobile routing facilities, etc.) from the perspective of post-disaster communication and coverage.

Devices like mobile cell stations, satellite relays, etc. can be components of a DTN. However, the main purpose of DTNs is to exploit non specialized, not expensive devices, usually with limited resources, but which are fast deployed and, thus, very suitable for disaster context. DTN routing: Many protocols have been developed for DTNs and evaluated on different network architectures. "Simple" protocols like First Contact, Epidemic, or Spray and Wait do not rely on any assumption or network structure measures for their routing rules. They are often used as references in comparative studies, regardless of the study context.

Epidemic [START_REF] Vahdat | Epidemic routing for partially-connected ad hoc networks[END_REF] is one of the most simple DTN routing protocols: whenever two nodes meet, they compare their respective sent and received message histories and exchange their "new" messages. The advantage of the Epidemic protocol is its high delivery probability. On the other hand, it consumes a lot of storage, power, and bandwidth resources. To circumvent such a problem, a FIFO policy is usually used to discard messages when the node's storage buffer is full. Hence, dissemination is limited by both bandwidth and storage and, in the long term, by available remaining energy.

Spray and Wait (SnW) [START_REF] Spyropoulos | Spray and wait: an efficient routing scheme for intermittently connected mobile networks[END_REF] is a simple trade-off between replication-based routing protocols, like Epidemic, and forward-based routing ones. The source of a message replicates it in L copies. The latter are firstly disseminated to L -1 other nodes. This spray phase accepts some variants. For instance, in Binary SnW, any node that has n > 1 message copies (source or relay), and encounters a second node (with no copies), gives to it n 2 and keeps n 2 for itself. Binary SnW has a lower delivery delay than the original Spray and Wait. Whenever a node has only one copy left, it switches to wait phase: it stores the message until it crosses the destination node to directly transmit the message. In other words, the Spray and Wait protocol manages the number of copies messages in the spray phase and uses Direct Delivery in the wait phase. As a result, the protocol presents fewer message transmissions than the Epidemic protocol.

Other protocols more "complex" than the previous ones, such as Spray and Focus [START_REF] Spyropoulos | Spray and focus: efficient mobility-assisted routing for heterogeneous and correlated mobility[END_REF], PRoPHET [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF], MaxProp [START_REF] Burgess | MaxProp: routing for vehicle-based disruption-tolerant networks[END_REF], rely on history of nodes' crossing or specific characteristics of a mobility model (Time To Return ) which predicts future nodes meeting probabilities. These protocols assume a somewhat redundant contact approach. In particular, a node S can efficiently route a message to a node D if and only if S knows D, i.e., if a packet (whichever it is a data or protocol packet) already followed a path from D to S, provided that this path still exists or at least part of it. However, these protocols perform at best as efficiently as the "simple" ones when this condition is not met. As we shall see later, geolocation messages of our protocols mainly follow such unknown paths.

We should also point out that DTN protocols are usually evaluated and compared under various scenarios and/or large randomly-generated data transfers. On the contrary, our scenarios rely on small geolocation messages, whose generation depends on each specific scenario.

III. RELATED WORK

In the context of disasters, we summarize in this section some existing solutions that provide support for diffusion of information and/or communication coverage as well as some mobility models proposed in some works.

A. Existing Solution for Support

Rescue workers typically use a dedicated trunked network infrastructure, based on a specific protocol like P25 or TETRA [START_REF] Stavroulakis | Terrestrial Trunked Radio -TETRA[END_REF]. These protocols provide support for encrypted voice and data transmission throughout a fixed mesh infrastructure, or using direct (point-to-point) communications. However, these networks are restricted to licensed professionals, and their design would not scale to a large use. Furthermore, P25 and TETRA do not provide multi-hop routing when using point-to-point communications, thus preventing their use for data collection without a resilient infrastructure. Some hardware solutions have also been proposed with the goal of temporarily replacing or restoring part of the damaged infrastructure, In this case, mobile cell sites (e.g.,"Cell On Wheels", "Cell On Truck", etc.), can be deployed to address emergencies and usually connected through wired connections, parabolic antennas, a satellite network, or a network of heliuminflated balloons, as proposed by the Loon project [START_REF][END_REF] for restoring access to the internet. Nevertheless, these solutions remain expensive -tens of thousands of dollars per cell -and their post-disaster deployment requires time.

In recent years, different disasters led to the emergence of many projects whose goal is to inform people about the disaster and to include them in the situation assessment process. For instance, after the earthquake in Japan in 2011, more than 150 applications were developed [START_REF] Utani | How geeks responded to a catastrophic disaster of a high-tech country: rapid development of counter-disaster systems for the great east japan earthquake of march 2011[END_REF] to face the disaster consequences. Most of these applications rely on crowdsourcing, offering information about the current situation, risks, needs, resources, people locations, etc. to victims, rescuers, and/or authorities. Ushahidi [START_REF] Ushahidi | [END_REF], Sahana Eden [START_REF] Sahanaeden | [END_REF], Google Crisis Response [START_REF]Google crisis response[END_REF], UbAlert Disaster Alert Network [START_REF]Disaster alert network -ubAlert[END_REF] or People Locator [START_REF] Pearson | The role of location for family reunification during disasters[END_REF] are examples of projects that make available collaborative maps on top of which the above information can be added. These applications consist of web sites or mobile applications. Even if some of them exploit alternative communications channels, like Ushahidi, which is able to collect information by SMS/MMS, they all rely on regular infrastructures as communication support.

Aiming at tolerating network failures and disruption, some other projects provide solutions that decentralize communication. Twimight [START_REF] Hossmann | Twitter in disaster mode: opportunistic communication and distribution of sensor data in emergencies[END_REF] ("Twitter in disaster mode"), is a Twitter client that can work without internet connection, exchanging tweets in an opportunistic way between terminals. Firechat [START_REF] Firechat | [END_REF] is a messaging application that can communicate with or without internet connection: Wi-Fi and BlueTooth interfaces are responsible for building a mesh network where each message can be stored, carried and forwarded on any available link. The Serval project [START_REF]The serval project[END_REF] developed a yet experimental messaging application that can transmit all sorts of data (messages, maps, voice, pictures, etc.) over an ad-hoc mesh network. These projects are not specially tailored to tackle with disaster situations but they are general solutions for regions or situations where network coverage is not working properly.

B. Mobility Models

The use of MANET or DTN to deal with a crisis situation has already been proposed [START_REF] Meissner | Design challenges for an integrated disaster management communication and information system[END_REF], [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF]. Several studies have compared known protocols in a crisis scenario [START_REF] Bhattacharjee | Exploring an energy-efficient DTN framework supporting disaster management services in post disaster relief operation[END_REF], [START_REF] Reina | Evaluation of ad hoc networks in disaster scenarios[END_REF]- [START_REF] Quispe | Behavior of ad hoc routing protocols, analyzed for emergency and rescue scenarios, on a real urban area[END_REF], or the in everyday life [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF], [START_REF] Johansson | Scenario-based performance analysis of routing protocols for mobile ad-hoc networks[END_REF], [START_REF] Boc | Price: hybrid geographic and co-based forwarding in delaytolerant networks[END_REF]), and have shown the impact of mobility on system performance.

Despite its lack of realism [START_REF] Yoon | Random waypoint considered harmful[END_REF], RWP is often used for simple [START_REF] Quispe | Behavior of ad hoc routing protocols, analyzed for emergency and rescue scenarios, on a real urban area[END_REF] or non-crisis-specific [START_REF] Karp | GPSR: greedy perimeter stateless routing for wireless networks[END_REF] evaluations or even as a reference or a sub-model of a more specific model. In [START_REF] Bhattacharjee | Exploring an energy-efficient DTN framework supporting disaster management services in post disaster relief operation[END_REF], the authors compare a set of DTN routing protocols in the scenario of Uttarakhand floods (India, 2013, 4 days of intense rainfall, 4200 affected villages, 5700 deaths). The impact of RWP, Map Based [START_REF] Keränen | The ONE simulator for DTN protocol evaluation[END_REF], Cluster Movement and Post Disaster Mobility (PDM) [START_REF] Uddin | A post-disaster mobility model for delay tolerant networking[END_REF] mobility models is evaluated on top of the ONE simulator. Among those, the last two ones also use RWP and Map Based as sub-models. For instance, PDM assigns different roles to nodes, with different mobility patterns: patrol, exploration, round-trip. Some of these patterns are based on RWP. PDM is also used in the experiment scenario in [START_REF] Ganguly | A location based mobility prediction scheme for post disaster communication network using DTN[END_REF], which addresses mobility prediction in a crisis situation.

The Disaster Area (DA) model is used in [START_REF] Martín-Campillo | Evaluating opportunistic networks in disaster scenarios[END_REF] and [START_REF] Reina | Multi-objective performance optimization of a probabilistic similarity/dissimilarity-based broadcasting scheme for mobile ad hoc networks in disaster response scenarios[END_REF] to evaluate DTN routing or broadcast protocols. The DA model introduces the concept of zones which are deployed by rescuers. Pedestrians follow a zone-restrained RWP mobility model with obstacles, whereas vehicles go back and forth between two zones.

There exist several other models in the literature which were conceived for disaster situations such as CORPS [START_REF] Huang | CORPS: event-driven mobility model for first responders in incident scene[END_REF], Dispatched Ambulance [START_REF] Aschenbruck | Modelling mobility in disaster area scenarios[END_REF], Reference Point Group Mobility (RPGM) [START_REF] Hong | A group mobility model for ad hoc wireless networks[END_REF], Human Behaviour for Disaster Areas (HBDA) [START_REF] Conceição | Modelling mobility based on human behaviour in disaster areas[END_REF], etc. However, all these models focus on rescue teams mobility, neglecting the movement of other people present in the disaster scenario [START_REF] Reina | A survey on multihop ad hoc networks for disaster response scenarios[END_REF]. In other words, victims and survivors are poorly represented, if not simply ignored, or follow a simplistic generic model (e.g., RWP or similar).

IV. OUR PROPOSED POST-DISASTER SYSTEM

In this section, we present our post-disaster system that aims at gathering geolocation and mapping information in collecting centers (hotspots) as well as informing users about accident locations. Moving to convergence points CPs, which can also be a hotspot, persons' mobile devices that get into contact with others, exchange information about geolocation of other persons they have met. Users mobility contributes then to both build a connected network and propagate information.

Our solution is deployed as a specific application, installed on people's mobile devices beforehand. We denote holder a person that holds a mobile device running this application and is within the disaster area. Note that a holder can be also a motionless victim, such as injured or dead victims as well as active dropped mobile devices.

Our goal is to provide a post-disaster geolocation system with the following features:

• Public availability: the network built by holders' devices must be available and usable by everyone that has a mobile device (smartphones, tablets, etc.). • Fast operational capacity / ad hoc routing: exploiting the holders' mobile devices, the network must be fully operational without considering, except hotspots, any additional fixed support. In other words, no specific devices and support should be used for routing messages, which would, then, require the assumption that holders' devices handle them. • Collection of data: data should be routed to central points (hotspots). • Freshness of information: collected data mainly consist of geolocation of persons' mobile devices in the area. However, only recent information about their respective location should be considered, which means that those messages with old information must be discarded.

• Informing users about accident locations: holders should, as much as possible, be informed about where there are accidents in order to allow them to change their path and circumvent risking zones. In the following, we firstly describe the environment and assumptions that we consider for our system. Then, since the majority of existing mobility models of the literature concern rescue teams (see Section III), we propose a new mobility model, denoted Danger Movement, that takes into account the considered environment and the movement of persons towards CPs. Finally, in this context, we propose to use (and adapt) both Epidemic and Binary Spray and Wait DTN protocols in order to route persons information to hotspots and disseminate accidents geolocation information.

A. Environment and Assumptions

We consider that there exist fixed places, denoted convergence points CPs, like hospitals, railway stations, schools, etc., which are known by all people and towards which they move when a disaster takes place. By default, every user chooses the closest CP in relation to his/her position when aware of the disaster. Nonetheless, a person can choose (with a certain probability) to reach another one, randomly chosen. Such an option improves the realism of the model, enriching it with "human" behaviors as, for example, parents fetching their children from school (a CP) instead of directly reaching the nearest rescue center.

Holders trying to reach a CP can be blocked by accidents. An accident is an event that permanently blocks an intersection of roads. Accidents are triggered on randomly chosen intersections following an exponential law with a chosen mean time between two accidents (MTBA).

Some CPs are endowed with storage, processing, and energy resources which render them collecting centers, denoted hotspots. The latter are interconnected by long-range resilient wireless links (laser, parabolic antenna, satellite, etc.). Periodically, hotspots synchronize themselves, exchanging collected data. Notice that this resilient communication infrastructure is not contradictory with our aim of providing a post-disaster solution which does not rely on a dedicated infrastructure. In our case, the latter is only used for synchronization between hotspots and not for connecting people or routing geolocation information to hotspots. If such a hotspot synchronization does not take place, the system still works with each hotspot having a partial view of people geolocations.

We also assume that both holder's devices and hotspots have Wi-Fi and/or Bluetooth wireless interfaces, which are widely available among the devices of holders nowadays. While, Wi-Fi benefits from better signal ranges than BlueTooth, Blue-Tooth consumes significantly less energy than Wi-Fi. Each of these interfaces runs a DTN router. We consider that a unique constant identifier (e.g., phone number) is assigned to each holder's device which is also equipped with a global positioning system (GPS).

B. Mobility Model: Danger Movement

Danger Movement is a map-based mobility model which takes into account the context described in the previous section. Basically, it characterizes the movements of survivors who move towards CPs, exchanging information about people and accident locations, which are routed to hotspots. A preliminary version of the model was presented in [START_REF] Coriat | Towards distributed geolocation for large scale disaster management[END_REF].

In accordance with our assumptions, hotspots are placed on the map as static nodes. Initially, Danger Movement randomly places holders over the map. The latter can then walk over the map at fixed or random (bounded) speeds. Holders running Danger Movement may be aware or not of the crisis situation. We denote alarmed a holder aware of the situation. Four cases are possible for a holder in Danger Movement: (1) he/she is alarmed from the beginning; (2) he/she spontaneously realizes the situation during simulation;

(3) the holder is warned by another alarmed holder; (4) the holder is never alarmed.

The map is known by all holders. Therefore, they are always able to find the shortest off-disaster path to any CP. However, holders have only knowledge of an accident provided they have seen it or another holder informed them of it. Upon having knowledge of a new accident, a holder may recompute his/her current path. Note that an alarmed holder may become stranded if there are no more accessible paths left towards his/her target CP.

Once arrived to the target CP, holders stop moving and, after transmitting all their data to the hotspot (if the CP is a hotspot), they disable their interfaces.

Figure 1 describes the different states of a holder, depending on its awareness and whether he/she is at home, walking outside or "stranded" by accidents. Notice that, in order to ensure that simulations based on Danger Movement finish, it is not required that all holders reach the safe state. Once a given defined percentage of holders are safe, all remaining holders become stranded ones.

The probabilities prewarnedP rob and walkP rob respectively concern the probability that a holder is alarmed from the beginning of the simulation (case 1) and that he/she starts walking without being alarmed (case 3). The self warnedP rob is the probability, every 1/10 s, for a nonalarmed holder to become spontaneously alarmed (case 2).

C. Protocols and Messages

As explained, every holder's interface runs a DTN router. However, since all geolocation data should be directed to hotspots, applying "complex" DTN protocols would be unfeasible in such a disaster context. Furthermore, the size of the messages is very small and those with old information should be dropped. Therefore, we have chosen to apply and adapt the simple and well-known DTN protocols Epidemic and Spray and Wait (see Section II).

Three message types are used by the protocols:

• geolocation: contains the GPS coordinates of a holder;

• accident: the GPS coordinates of an accident;

• warning: a special message which renders alarmed those holders who received the message.

Since every holder has a GPS receiver, it is able to build a geolocation message at any time.

Warning messages are automatically created by already alarmed holders while accident messages are generated by holders when getting knowledge about an accident. When they cross each other, holders may exchange geolocation information about the holders and accidents of which they are aware. Each of this information consists of a single message whose size does not exceed 20 B. However, MANET/DTN routing protocols are usually evaluated with larger messages: from 64 B for MANETs to 100 KiB for DTNs. Thus, aiming at preventing holders from sending numerous small messages, which would induce high network overhead, messages are grouped into frames of a predefined maximum transmission unit (MTU) size before being transmitted.

In order to satisfy the freshness of information requirement, messages about persons' geolocation must be versioned, i.e., timestamped. In this way, only the most recent ones (last version) are collected and kept by holders and hotspots. A status can also be added to each geolocation message, giving more information about the holder (not injured, injured, motionless victim, etc.). Our solution should, thus, ensure a anycast routing service for versioned messages, dropping those with old version.

As argued, we have chosen to implement both the Epidemic and Spray and Wait DTN protocols (see Section V), adapting them to the described disaster environment. In the case of Spray and Wait, we adapted the Binary SnW, where every node (holder), keeping more than one copy of a message, transmits half of them on the next node (holder) contact.

The two protocols have been modified to deal with messages versions: a message is automatically dropped as soon as a more recent version is received. In the case of Spray and Wait protocol, this message dropping may concern several copies of the same message, independently of the number of copies received for the new version of the message. Lastly, a transmission delay is applied to more recent versions of an already sent message, preventing continuous update flow transmissions.

It is worth noting that warning and accident messages have to be disseminated among all holders, i.e., in an epidemic way, so that only geolocation data are affected by the protocol choice.

Collected data are forwarded to hotspots, which periodically synchronize themselve, keeping only last versioned data.

V. PERFORMANCE EVALUATION

Experiments were conducted on the ONE simulator [START_REF] Keränen | The ONE simulator for DTN protocol evaluation[END_REF] using a map of the center of Santiago (29km 2 ). CPs are placed on real amenities, with hotspots chosen among hospitals. Both protocols, Epidemic and Spray and Wait (Binary SnW) have been evaluated. Firstly, we explain and define the metrics used to evaluate these protocols. Then we describe the parameters of the simulation testbed. Finally, some results are presented and discussed.

A. Metrics

In order to estimate the ability/efficiency of routing protocols to deliver messages, performance metrics such as packet delivery fraction (PDF), throughput or end-to-end delay [START_REF] Reina | Evaluation of ad hoc networks in disaster scenarios[END_REF] are commonly used, while protocol overhead is evaluated through metrics of normalized routing load (NRL) [START_REF] Martín-Campillo | Evaluating opportunistic networks in disaster scenarios[END_REF] or energy cost per message.

However, in a disaster scenario, it is important to deliver only up-to-date information, discarding obsolete messages before they can reach their final destination (a hotspot). Hence, usual performance metrics (e.g., throughput, PDF, NRL) become irrelevant or very difficult to evaluate. In our context, we aim at gathering as much geolocation information as possible while keeping low energy consumption. Consequently, to compare the efficiency of different routing protocols, we propose a new metric that better reflects the quantity of the accurate geolocation information gathered on hotspots. This efficiency metric is denote fraction of discovered holders, known by at least one hotspot. The overhead entails by the protocols is estimated by measuring the average number of frames sent by a holder over the time. Note that this second metric gives an overview of the global energy consumption of our protocol.

B. Simulation Testbed

For each parameters set, 10 simulation runs were executed. The curves of the figures show the average values for these runs.

Table I summarizes the parameters for our reference scenario. Note that the number of convergence points can vary between scenarios (3, 5, or 20), but the number of hotspots is always fixed to 3.

C. Evaluation Results

We have conducted our simulations on different scenarios. The first one is used as a reference to evaluate the impact of the type of interfaces, routing protocols, and number of CPs on the efficiency and energy consumption metrics.

Reference scenario: Figure 2 and the first columns of Table II show results of the simulations, considering the parameter set of Table I.

Firstly, we observe that all simulations stabilize within 90 minutes or less and none of them ends with a complete knowledge of the position of all individuals: the best simulation results yield a knowledge of ∼99.5 % of the holders' positions, leaving only a dozen of holders unreachable.

Efficiency performance: Since only 3 CPs are hotspots which collect geolocation information, in scenarios with more CPs, device holders are statistically less likely to reach a hotspot. Consequently, performance in terms of number of discovered holders clearly drops as the number of CPs increases.

As expected, Wi-Fi interfaces produce better results than BlueTooth ones. The BlueTooth's best performance (Blue-Tooth / Epidemic) results stand out ∼5 % below Wi-Fi worst case (Wi-Fi / SnW). Since Wi-Fi propagation range is broader, Wi-Fi devices have a higher chance to forward their positions to a holder moving towards a hotspot. Hence, for similar scenarios (same number of CPs), Wi-Fi outperforms Bluetooth, with the difference on the number of detected holders growing with the number of CPs. The gap is of 5% when considering 3 CPs and up to 15% with 20 CPs.

Epidemic and SnW perform similarly on BlueTooth, but Epidemic gives slightly better results on Wi-Fi. The reason is that Epidemic seems to be more resilient to the dispersion of holders when the number of CPs increases: whereas both of them acquire ∼99.5 % knowledge about holder positions with 3 CPs, SnW misses ∼5 % more holders position information than Epidemic with 5 CPs, and ∼10 % with 20 CPs. Such degradation is easily explained by the bound in the number of copies of SnW: some relevant holder relays are missed by the protocol since there is no more copy left upon the encounter moment.

We also observe that Epidemic discovery convergence time takes place 10∼15 min earlier than SnW one, regardless of the number of CPs, probably because SnW messages are stuck in the wait phase of the protocol until their respective holders reach a hotspot.

Energy consumption:

Table II shows that BlueTooth clearly stands out with less than 30 frames sent per holder on average, regardless of the protocol: forwarding is limited by interfaces propagation range more than by the choice of the protocol.

However, with Wi-Fi broader propagation range, energy consumption becomes more significant: around 20 times more frames than BlueTooth (note the difference in scales between the 2 figures). It also impacts the choice of the protocol since SnW outperforms Epidemic by a factor of about three to five. Thus, SnW significantly reduces energy consumption when deploying Wi-Fi interfaces while keeping relatively acceptable decrease in performance (especially with few non-hotspots CPs). We could, therefore, consider SnW as a the best option when deploying with Wi-Fi interfaces.

Given the low consumption of Epidemic, choosing SnW seems rather useless With BlueTooth: both protocols can be used interchangeably, with slightly better results for Epidemic.

From the above discussions of the results, we can say that Wi-Fi / SnW and BlueTooth / Epidemic are interesting tradeoffs, which will, therefore, be taken as reference in the rest of this performance evaluation study.

Intermittent interfaces: In a crisis context, where energy networks may be inoperative, holders who cooperate to define a cartography of the crisis zone must take care about the consumption of their battery-powered devices. In this context, energy aware transmissions which rely on disabling the radio interface for a certain duration of time, seems quite suitable. Hence, it is important to study the impact of intermittent radio interfaces on the propagation of our geolocation information. To this end, we have defined an environment with intermittent interfaces: each interface is powered up and shut down periodically. On the other hand, as hotspots are not concerned by energy issues, they always keep their radio interface active.

Since synchronization to get all wireless interfaces active simultaneously is not realistic, we consider that holder devices operate independently from one another. Thus, for the current simulations, we have chosen an intermittency functioning which is based on one of the discovery protocols of Wi-Fi Direct2 .

To circumvent the risk of having devices which are never active at the same time, the intermittency has been implemented as a pseudo-periodic process: interfaces are up for active = 30 s, then down for a random amount of time between minInactive = 30 s and maxInactive = 90 s, and so on. In this way, two holder's devices whose active time are originally mutually exclusive will eventually be able to communicate with each other.

Figure 3 and the second section of Table II present the intermittency results. With a Wi-Fi interface running SnW, intermittency has nearly no impact on the performance (number of discovered devices), whereas the average number of messages is reduced by ∼25 %. Conversely, Bluetooth performance degrades due to these interruptions. The number of messages is virtually unchanged but performance efficiency drops. For example, with 3 hotspots, the number of missed holders doubles from 5 % to 10 %.

Overall, we can conclude from the results that performance of both protocols are similar, though slightly reduced, and that intermittency might be useful with Wi-Fi. Mobility -variable speeds, CP selection: Based on the reference scenario, we change, for the current simulation, the value of some parameters in order to evaluate their influence on the overall system performances. The first experiments concern the walking speed of holders. In our reference scenario, all mobile holders walk with a constant speed of 1.3 m s -1 . Only victims or individuals unaware of the crisis remain static. On the other hand, speed variations may have an influence on contact occurrences and durations.

Thus, for the simulations, we considered the parameter values of Table I except for the walk speed, that randomly varies from 0.7 m s -1 to 2.0 m s -1 . Figure 4 shows the results. Except for a hardly significant improvement of convergence time with BlueTooth / Epidemic, performances remain comparable: the average speed being still the same, the sets of encountered contacts remain very similar. However, speed variations have an impact on contact patterns since irregularity in the mobility speed of holders increases both disconnections and new contacts leading to more data exchanges. Such an impact is reflected by the increase in the number of exchanged frames, observed in the third section of Table II.

Finally, simulations are run considering a constant speed but mobility is modified by allowing holders to head towards a random CP, which may not be the closest one in relation to their current positions.

Results are presented in Figure 4 and the last section of Table II. Performance efficiency remains quite similar with 3 CPs. However, with more CPs added, this mobility variation yields to spectacular improvements (more than 60% better with 20 CPs and Wi-Fi / SnW). The reason for such great performance improvement is that divergent holders disseminate information among holders with different target CPs, and, thus, mitigate holders' dispersion. In this paper, we have proposed a new post-disaster ad hoc communication architecture for collecting geolocation information about victims and survivors. Our study focused on efficiency and speed of information gathering as well as energy cost in terms of number of exchanged messages. By defining a reference scenario, we conducted several experiments on top of the ONE simulator to assess the effect of different parameters on the overall performance. Mobility patterns and interface choices were revealed to have a significant impact on both efficiency and energy consumption, whereas protocol choices and interface intermittence have a limited (and interface-range specific) one. Furthermore, walk speed has shown to have little interest in the considered scenario.

Aiming at optimizing protocols routing choices, future directions involve the study of the characteristics of dynamic graphs built over time induced by holders encounters. In a close future, we intend to enrich our disaster scenario considering, for instance, larger disaster or adding other participants such as vehicles, rescue teams with specific mobility patterns, etc.

Fig. 1 .

 1 Fig. 1. Danger Movement : state (sub-models) diagram of a holder

Fig. 2 .

 2 Fig. 2. Reference scenario: Epidemic vs. Spray and Wait -proportion of discovered devices

Fig. 3 .

 3 Fig. 3. Intermittent interfaces

Fig. 4 .

 4 Fig. 4. Mobility variations -walk speed & CP choice

a Wi-Fi standard enabling devices to connect with each other without requiring an infrastructure.


Dorin Maxim

Robert I Davis

Liliana Cucu-Grosjean

Arvind Easwaran

Probabilistic Analysis for Mixed Criticality Scheduling with SMC and AMC

This paper introduces probabilistic analysis for fixed priority preemptive scheduling of mixed criticality systems on a uniprocessor using the Adaptive Mixed Criticality (AMC) and Static Mixed Criticality (SMC) schemes. We compare this analysis to the equivalent deterministic methods, highlighting the performance gains that can be obtained by utilising more detailed information about worst-case execution time estimates described in terms of probability distributions.

I. INTRODUCTION

In 2007, Vestal [START_REF] Vestal | Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance[END_REF] introduced a mixed criticality task model, where each task is represented by multiple worst-case execution time (WCET) estimates that are determined at different levels of assurance. For example, the WCET estimates C(LO) and C(HI) are the estimates for low-assurance and high-assurance respectively in a dual-criticality system. By contrast, in this paper we use a richer model based on probabilistic worst-case execution time (pWCET) distributions, provided by probabilistic analysis of worst-case execution times of tasks [START_REF] Cucu-Grosjean | Measurement-based probabilistic timing analysis for multipath programs[END_REF], [START_REF] Altmeyer | Static probabilistic timing analysis for real-time systems using random replacement caches[END_REF]. Figure 1 illustrates this richer model, where the line on the graph denotes the 1-CDF (Complementary Cumulative Distribution Function or exceedance function) of the pWCET for a task. The 1-CDF describes the probability that the WCET of the task exceeds any particular value given on the x-axis. The high-assurance estimate C(HI) may be obtained using an exceedance probability (on the y-axis) of p(HI) = 10 -9 , where 10 -9 denotes an acceptable threshold on the failure probability for each job of the task at the high-assurance level 1 . Thus in a mixed criticality system with a probabilistic description, the scheduler can safely ignore any execution demand beyond C(HI) because its probability of occurrence is below the threshold required. Further, at a lower level of assurance (say with acceptable threshold p(LO) = 10 -5 ), the scheduler can ignore any execution demand beyond C(LO) because its probability of occurrence is below the threshold for that level of assurance.

In this paper, we focus on the development of a probabilistic mixed criticality framework under the Fixed-Priority Preemptive Scheduling (FPPS) policy. Our choice of FPPS is motivated by the fact that it is a standard scheduling policy employed in many applications. There are two well-known FPPS schemes and corresponding deterministic schedulability analyses in the literature on mixed critiality scheduling; Static Mixed Criticality (SMC) [START_REF] Baruah | Schedulability Analysis of Sporadic Tasks with Multiple Criticality Specifications[END_REF] and Adaptive Mixed Criticality (AMC) [START_REF] Baruah | Response-Time Analysis for Mixed Criticality Systems[END_REF]. We Fig. 1: Exceedance function or 1-CDF for the pWCET distribution of a task, and also pET distributions for different jobs of the same task. develop probabilistic analyses for both of these schemes. (A brief description of these schemes is given in Section II).

A. Related work

A growing number of studies have been introduced for mixed criticality real-time scheduling, an overview of these approaches can be found in the review on mixed criticality systems [START_REF] Burns | Mixed criticality systems -a review[END_REF]. Previous work on probabilistic analysis and mixed criticality systems was done for the Earliest Deadline First (EDF) scheduling policy. Santinelli and George [START_REF] Santinelli | Probabilities and mixed-criticalities: the probabilistic c-space[END_REF] presented preliminary work that investigates the probabilistic C-space, showing how schedulability varies with task execution times under EDF. Guo et al. [START_REF] Guo | Edf schedulability analysis on mixed-criticality systems with permitted failure probability[END_REF] extended the mixed criticality task model with a single exceedance probability value for the low assurance budget of each HI-criticality task, and used probabilistic analysis to improve schedulability. In contrast, we focus on the FPPS policy, and consider a richer task model with pWCET distributions.

II. SYSTEM MODEL

In this paper, we are interested in the Fixed Priority Preemptive Scheduling of a Mixed Criticality System (MCS) comprising a static set of n sporadic tasks which execute on a single processor. We assume without loss of generality that each task τ i has a unique priority. We further assume a discrete time model in which all task parameters are given using integers.

Each task τ i is defined by its period (or minimum arrival interval), relative deadline, worst-case execution time, and level of criticality (defined by the system engineer responsible for the entire system): (T i , D i , C i , L i ). We restrict our attention to constrained-deadline systems in which D i ≤ T i for all tasks.

In a mixed criticality system, further information is needed in order to perform schedulability analysis. Thus a task τ i may be defined by: (T i , D i , C i , L i ), where C i is a vector of values -one per criticality level, with the constraint L1 > L2 ⇒ C i (L1) ≥ C i (L2) for any two criticality levels L1 and L2. In this paper we are concerned with dual criticality systems, with criticality levels LO and HI (where LO < HI).

Using a deterministic representation each LO-criticality task τ i has a single worst-case execution time estimate C i (LO), while each HI-criticality task τ i has two worst-case execution time estimates C i (LO) and C i (HI) with C i (HI) ≥ C i (LO). We use p(LO) (and p(HI)) to denote the worst-case probability that C i (LO) (resp. C i (HI)) is exceeded during the execution of any single job of the task. Thus p(LO) and p(HI) reflect the confidence that we have in the two WCET estimates. Note, in this paper, we assume that these probabilities are the same for all tasks and so drop the index. We use exemplar values for p(LO) and p(HI) of 10 -5 and 10 -9 respectively. (Note for ease of presentation, we also drop the index for C(LO) and C(HI) when using these terms in a generic way; nevertheless, these values are specific to each task).

By contrast, using a probabilistic representation, each task τ k (of LO-or HI-criticality) has a probabilistic worst-case execution time distribution (pWCET) C k . Further, there is a correspondence between the probabilistic and deterministic representations. Considering the 1-CDF (exceedance function), f (C k ) for task τ k , C k (LO) (resp. C k (HI)) in the deterministic representation corresponds to the value of f (C k ) at a probability of exceedance of p(LO) (resp. p(HI)). Note beyond this correspondence, we make no assumptions in our analysis about the form of the distribution. We assume that the WCET values of two tasks C i and C j are independent and so too are their pWCET distributions C i and C j [START_REF] Cucu-Grosjean | Independence -a misunderstood property of and for probabilistic real-time systems[END_REF].

For simplicity of presentation, we assume that C(HI) is not exceeded and that p(HI) therefore represents the probability that the WCET of a HI-criticality task is C(HI) (rather than exceeds C(HI)).

The SMC and AMC scheduling schemes investigated in this paper both use budget enforcement by the Real-Time Operating System (RTOS) to ensure that LO-criticality tasks cannot execute for more than their LO-criticality execution time budget C(LO). With the AMC scheme, the RTOS also uses the C(LO) budget for each HI-criticality task to determine if a mode change should take place. The system moves from LO-to HI-criticality mode if this budget is reached without the job completing. Once HI-criticality mode is entered, then with AMC, any jobs of LO-criticality tasks that have already started can continue to execute; however, no further jobs of LO-criticality tasks can be released. (This simple extension to the original AMC scheme, which called for jobs of LO-criticality tasks to be aborted on entering HI-criticality mode, is permitted by the analysis [START_REF] Baruah | Response-Time Analysis for Mixed Criticality Systems[END_REF] and was proposed in [START_REF] Bate | A bailout protocol for mixedcriticality systems[END_REF] as a means of avoiding difficulties in dealing with aborted jobs). With SMC, jobs of LO-criticality tasks continue to be released in HI-criticality mode. Full details of both schemes can be found in [START_REF] Baruah | Response-Time Analysis for Mixed Criticality Systems[END_REF] and [START_REF] Bate | A bailout protocol for mixedcriticality systems[END_REF].

In any processor busy period, where all jobs of HI-criticality tasks complete without exceeding their LO-criticality budgets, the system is said to be in LO-criticality mode; otherwise it is said to be in HI-criticality mode. (We assume that at an idle instant when there are no jobs with outstanding execution, the system may revert back to LO-criticality mode). There are different requirements on schedulability that apply in the different modes of the system.

We use R i to refer to the deterministic worst-case response time (WCRT) of task τ i , and R i to refer to the probabilistic worst-case response time (pWCRT) distribution which may be computed using pWCET values.

In LO-criticality mode, jobs of LO-criticality tasks must have a worst-case Deadline Miss Probability (DMP) that is no greater than a specified threshold H(LO) (for example 10 -5 ). We assume these thresholds are the same value for all LO-criticality tasks and so drop the index. Using deterministic analysis, this requirement may be satisfied by showing that the tasks are schedulable i.e. have a worst-case response time R i (LO) ≤ D i , computed using execution times of C(LO). Using the probabilistic analysis developed in this paper, the requirement may be satisfied directly by determining the worst-case deadline miss probability. This is achieved by computing a probabilistic worst-case response time distribution (pWCRT) and determining the value of the 1-CDF (Cumulative Distribution Function) at a response time corresponding to the task's deadline D i , thus computing the probability of missing the deadline.

Jobs of HI-criticality tasks must have a worst-case deadline miss probability that is no greater than a specified threshold H(HI) (for example 10 -9 ). This requirement applies to all modes, and may be met via deterministic methods or via calculating the appropriate probabilistic worst-case response time distribution and comparing it with the task's deadline. In both cases, due account needs to be taken of interference from LO-criticality tasks. In addition, we note that jobs of LO-criticality tasks may fail to meet their timing requirements by not completing by their execution time budget C(LO). The probability of this happening depends upon the budget set and may be read from the pWCET distribution for the task. It is the same irrespective of whether we use deterministic or probabilistic analysis. (The high assurance RTOS is assumed to enforce this budget at runtime).

Finally we note a subtle but important point about using pWCET distributions and probabilistic analysis, which does not occur with deterministic analysis. This point rests on the fact that when we analyse LO-criticality behaviour, we can use low assurance information e.g. C(LO) WCET estimates, pWCET distributions for LO-criticality tasks etc. However, when we analyse HI-criticality behaviour, we must be sure to use only high assurance information e.g. pWCET distributions for HI-criticality tasks, and rely on the high assurance RTOS to enforce C(LO) budgets for LO-criticality tasks. We return to this point in Section IV-A.

III. RECAP OF EXISTING PROBABILISTIC

SCHEDULABILITY ANALYSIS In this section, we recapitulate the probabilistic response time analysis for FPPS originally derived in [START_REF] Maxim | Response time analysis for fixedpriority tasks with multiple probabilistic parameters[END_REF] for tasks with both worst-case execution times and minimum inter-arrival times described by random variables. Since in this paper the minimum inter-arrival time for each task is a constant, we present only a simplified version of this analysis. First we recap the basic terminology and operators used.

We distinguish between full distributions and partial distributions. A full distribution Z has probabilities which sum to 1. Such a distribution may be split into two (or more) partial distributions X and Y such that ∀v

P (Z = v) = P (X = v) + P (Y = v).
We say that Z = X ⊕ Y where ⊕ is the coalescence of the two distributions via the addition of the probabilities for each value. In contrast, the sum Z of two independent distributions X and Y is given by their convolution X ⊗ Y where P {Z = z} = k=+∞ k=-∞ P {X = k}P {Y = z -k}. In [START_REF] Maxim | Response time analysis for fixedpriority tasks with multiple probabilistic parameters[END_REF], Maxim and Cucu-Grosjean showed that considering all valid patterns of job releases, the worst-case response time distribution of a job of task τ i occurs for the first job of τ i released simultaneously with jobs of all higher priority tasks, which are then re-released as soon as possible. We can therefore compute an upper bound on the pWCRT distribution R i of task τ i as follows.

The worst-case response time distribution for task τ i is first initialized to:

R 0 i = B i ⊗ C i (1)
where the backlog B i at the release of τ i is given by:

B i = j∈hp(i) C j (2)
The worst-case response time is then updated iteratively for each preemption as follows:

R m i = (R m-1,head i ⊕ (R m-1,tail i ⊗ C pr k )) (3)
Here, m is the index of the iteration. R m-1,head i is the part of the distribution R m-1 i that is not affected by the preemption under consideration (i.e. it only contains values ≤ t m where t m is the time of the preemption). R m-1,tail i is the remaining part of the distribution R m-1 i that may be affected by the preemption. Finally, C pr k is the pWCET distribution of the preempting task τ k .

Iteration ends when there are no releases left from jobs of higher priority tasks at time instants smaller than the largest value in the response time distribution currently obtained. Iteration may also be terminated once any new preemptions are beyond the deadline of the task. Once iteration is complete, the worst-case Deadline Miss Probability valid for any job of task τ i is given by:

DM P i = P (R i > D i ). (4)
IV. PROBABILISTIC MIXED CRITICALITY SCHEDULABILITY ANALYSIS In this section, we introduce probabilistic response time analysis for the SMC and AMC scheduling schemes, referred to as pSMC and pAMC analysis respectively.

A. pWCET Distributions Used

In our analysis, we make use of different types of pWCET distribution which we now describe. We use the term partLO to denote a partial distribution X formed from the full pWCET distribution Z of a task by taking only those values that represent completion of the task in no more than its budgeted LO-criticality execution time C(LO). Thus X is such that ∀v ≤ C(LO) P (X = v) = P (Z = v) and ∀v > C(LO) P (X = v) = 0.

As discussed in Section II, we assume that the value C(HI) is the final and therefore largest value in the pWCET distribution for a HI-criticality task. Figure 2a illustrates both f ull and partLO distributions for a HI-criticality task. (Note the shape of these distributions is for illustration purposes only. No specific distribution is assumed by the analysis).

In the case of a LO-criticality task, we are also interested in the partLO distribution, since this describes the behaviour expected of it by the system designer. In addition, with both the SMC and AMC schemes, if a job of such a task executes for its execution time budget C(LO) without signaling completion, then the job will be aborted as a result of budget enforcement by the RTOS. We need to also take this behaviour into account when computing the interference on other tasks of lower priority. Thus we form a further partial distribution for each LO-criticality task denoted by partBE (meaning budget exceeded). This distribution Y has a single value of C(LO) with a probability which equates to the sum of the probabilities for all larger values from the full distribution, i.e. P (Y = C(LO)) = P (Z > C(LO)). Note that X ⊕ Y forms the full distribution that we use for a LO-criticality task. This is illustrated in Figure 2b. We refer to this distribution as fullBE (the full distribution accounting for budget exceedance).

When we analyse the HI-criticality mode (e.g. computing the pWCRT distribution for a HI-criticality task), then we cannot trust the full pWCET distributions obtained for LO-criticality tasks. The reason for this is that LO-criticality tasks are not developed to the same rigourous standards as HI-criticality tasks. Thus, in the analysis we provide for the HI-criticality mode, we must not make any assumptions about their correct behaviour. Instead, we assume the worst; that such tasks may enter an infinite loop, and be aborted at their C(LO) budget by the RTOS, which is itself a trusted component developed to the standards required for HI-criticality operation. When we are analysing HI-criticality mode, we therefore assume that LO-criticality tasks have a degen (meaning full degenerate) distribution which has a single value C(LO) with probability 1 (see Figure 2c).

pWCRT distributions are composed from pWCET distributions using the analysis described in Section III. When partial pWCET distributions are used (for example representing LO-criticality mode only), then the resultant pWCRT distribution is also a partial distribution, giving probabilities that are conditional on being in that mode.

When analysing the Deadline Miss Probability for LO-criticality tasks, we use the partLO distributions, since we are only interested in the probability that tasks exceed their deadlines and the system remains in LO-criticality mode, i.e. no C(LO) budgets are exceed. The component of a full pWCRT distribution that is lost represents only those scenarios where the system enters HI-criticality mode, and hence where there is no requirement for LO-criticality tasks to meet their deadlines.

We note that a partial distribution Y describing the behaviour in HI-criticality mode can be obtained from a full distribution Z describing the behaviour in all modes, by subtracting the partial distribution X describing the behaviour in LO-criticality mode. By subtraction we mean the subtraction of probabilities for the corresponding values, ∀v P (Y = v) = P (Z = v) -P (X = v), i.e. the counterpart of coalescence. We write this as Y = Z X . Here, Y is well defined provided that X is a partial distribution of Z. This is the case in all uses of the operator in this paper, since Z is composed from full distributions and X from corresponding partial distributions for the same tasks.

As a building block for the analysis in the following sections, we use a function pRTA(τ k , δ, δLO, δHI, t) defined as follows.

Definition 1: pRTA(τ k , δ, δLO, δHI, t) is a function which returns a (full or partial) pWCRT distribution for task τ k computed using the analysis described in Section III. This analysis starts from an initial distribution of type δ for task τ k , and uses pWCET distributions of types δLO and δHI for preempting (i.e. higher priority) LO-criticality and HI-criticality tasks respectively. Further, jobs of higher priority LO-criticality tasks are only included in the computation of the pWCRT distribution if their release times are no later than time t. The parameters δ, δLO, and δHI may take values partLo, fullBE, degen, and full when the function is used.

B. pSMC Analysis

Recall that with the SMC scheme, LO-criticality tasks may execute in HI-criticality mode. The only constraint on their execution being budget enforcement. We note that for a LOcriticality task, there are three possibilities:

(i) The task overruns its budget, the probability for this case is given by the partBE distribution for the task; (ii) The task does not overrun its budget and the system operates in LO-criticality mode; (iii) The task does not overrun its budget and the system operates in HI-criticality mode. The partial pWCRT distributions for cases (ii) and (iii) are derived below. For a HI-criticality task, we assume that there can be no overrun of the C(HI) budget, and thus C(HI) is effectively the maximum value in the pWCET distribution. Thus there are just two cases to consider, equivalent to (ii) and (iii) above. The partial pWCRT distributions for those cases are also derived below.

1) LO-criticality mode: We determine schedulability in LO-criticality mode using the partLO distribution for the task of interest τ k , and the f ullBE distribution for higher priority, LO-criticality tasks, since they may overrun their budgets, but there is no behaviour of these tasks that can cause HI-criticality mode to be entered. Finally, we need only consider the partLO distribution for HI-criticality tasks, as the remaining part of the full distribution for these tasks implies that the system enters HI-criticality mode, hence:

R k (LO) = pRTA(τ k , partLO, f ullBE, partLO, ∞) (5)
Equation ( 5) applies to both LO-and HI-criticality tasks. In each case it provides the partial pWCRT distribution for task τ k conditional on the system operating in LO-criticality mode and the task not exceeding its own budget.

2) HI-criticality mode: When analysing a HI-criticality task τ k executing in HI-criticality mode, we can no longer trust the behaviour of LO-criticality tasks. Thus we must use degenerate distributions equating to the execution time budget C(LO) for higher priority, LO-criticality tasks.

First, we compute the pWCRT distribution for both modes. Here, we begin with the full distribution for HI-criticality task τ k and similarly include the full distribution for preempting higher priority, HI-criticality tasks.

Z k = pRTA(τ k , f ull, degen, f ull, ∞) (6)
Then we determine the partial pWCRT distribution for LOcriticality mode:

X k = pRTA(τ k , partLO, degen, partLO, ∞) (7)
Finally, we obtain the partial pWCRT distribution for HI-criticality mode as a simple subtraction:

R k (HI) = Z k X k (8)
Equation ( 8) upper bounds the pWCRT distribution for a HIcriticality task τ k conditional on the system operating in HIcriticality mode.

C. pAMC Analysis

The AMC and SMC schemes have identical behaviour in LO-criticality mode, hence the analysis given in Section IV-B also provides pAMC analysis for both LO-and HI-criticality tasks in LO-criticality mode. That leaves pAMC analysis of HI-criticality tasks in HI-criticality mode.

Again, we first compute the pWCRT distribution for both HI-and LO-criticality modes. Here, we begin with the full distribution for task τ k and similarly include the full distribution for preempting higher priority, HI-criticality tasks. As this analysis is for HI-criticality mode, we assume that the behaviour of LO-criticality tasks cannot be trusted and therefore make use of the degen distributions for those tasks.

Z k = pRTA(τ k , f ull, degen, f ull, R(LO)) (9)
Then we determine the partial pWCRT distribution for LOcriticality mode:

X k = pRTA(τ k , partLO, degen, partLO, R(LO)) (10)
Note, in [START_REF] Guo | Edf schedulability analysis on mixed-criticality systems with permitted failure probability[END_REF] for symmetry and obvious compatibility with (9) we limit the jobs of higher priority LO-criticality tasks to those released by time R(LO) given by the deterministic analysis for AMC [START_REF] Baruah | Response-Time Analysis for Mixed Criticality Systems[END_REF]; however, since R(LO) is effectively computed using the maximum values in the degen distributions for LO-criticality tasks and partLO distributions for HI-criticality tasks, then in practice this does not restrict the distribution X k in any way. Note that if R(LO) cannot be obtained by deterministic analysis i.e. the task is unschedulable and R(LO) > T then R(LO) may be assumed to be infinite and the pAMC analysis reduces to the pSMC analysis. Finally, we obtain the partial pWCRT distribution for HI-criticality mode as a simple subtraction:

R k (HI) = Z k X k (11)
Equation ( 11) upper bounds the pWCRT distribution for a HIcriticality task τ k conditional on the system operating in HIcriticality mode. Together with [START_REF] Bini | Measuring the performance of schedulability tests[END_REF], this completes the analysis for pAM C.

Comparing ( 9) and ( 10) with ( 6) and [START_REF] Cucu-Grosjean | Independence -a misunderstood property of and for probabilistic real-time systems[END_REF], it is easy to see that the pAMC analysis dominates pSMC. The only difference is the discounting of LO-criticality preemptions after time R(LO) in the case of pAMC. Thus all task sets that are deemed schedulable2 by pSMC analysis are also schedulable according to the pAMC analysis. Further, we note that the pAMC analysis dominates deterministic analysis for AMC, and similarly, pSMC analysis dominates deterministic analysis for SMC. This can be seen by considering the distributions used in the probabilistic analyses. These distributions and the resulting pWCRT distributions satisfy the limit condition [START_REF] Maxim | Response time analysis for fixedpriority tasks with multiple probabilistic parameters[END_REF]. The maximum values in each input distribution are the same as the values used in the corresponding deterministic analysis, thus the maximum value in the output pWCRT distributions are the same as the deterministic WCRTs.

D. Probabilistic schedulability

For a LO-criticality task to meet its schedulability requirements, then its execution time must not exceed its C(LO) budget with more than a specified probability. This is guaranteed, as with deterministic analysis, by setting its execution time budget no lower than C(LO). Secondly, its pWCRT distribution conditional on not exceeding its budget and that the system remains in LO-criticality mode must give a worst-case Deadline Miss Probability that does not exceed the specified threshold, i.e. P (R k (LO) > D k ) ≤ H(LO). This can be determined for both pSMC and pAMC using [START_REF] Bini | Measuring the performance of schedulability tests[END_REF].

For a HI-criticality task to meet its schedulability requirements, then execution of no more than C(HI) is assumed to be assured. Further, its pWCRT distribution (valid for both modes combined) must give a worst-case Deadline Miss Probability that does not exceed the specified threshold i.e. P (R k > D k ) ≤ H(HI), where R k = R k (LO) ⊕ R k (HI). This can be determined for pSMC using ( 5) and ( 8), and for pAMC using ( 5) and [START_REF] Maxim | Response time analysis for fixedpriority tasks with multiple probabilistic parameters[END_REF].

V. EVALUATION

In this section, we present an empirical investigation, examining the effectiveness of the probabilistic analysis techniques (pSMC and pAMC) introduced in this paper, in particular examining the performance improvements that can be obtained with respect to the corresponding deterministic analyses.

A. Task set parameter generation

The task set parameters used in our experiment were randomly generated as follows:

• Task utilisations (U i = C i /T i ) (for LO-criticality mode) were generated using the UUnifast algorithm [START_REF] Bini | Measuring the performance of schedulability tests[END_REF], giving an unbiased distribution of values. • Task periods were generated according to a log-uniform distribution from 10ms to 1000ms. • Task priorities were set in deadline monotonic order. We generated the pWCET distribution for each task via extrapolation from the C(LO) and C(HI) parameter values. We assumed that the probability of exceeding C(LO) is p(LO) = 10 -5 , and that the probability of executing for, but not exceeding C(HI) is p(HI) = 10 -9 . To determine intermediate points, we assumed that the pWCET distributions have an exponential tail (as is the case with a Gumbel distribution). Thus we assumed that the 1-CDF of the pWCET was a straight line on an exceedance graph with probabilities given on a log scale, as depicted in Figure 3.

The Thresholds H(LO) and H(HI) on the maximum acceptable deadline miss probabilities for LO-and HI-criticality tasks were set to 10 -5 and 10 -9 respectively.

B. Schedulability tests

We investigated the performance of the following techniques and associated schedulability tests.

• pSMC: Probabilistic SMC analysis (Section IV-B).

• pAMC: Probabilistic AMC analysis (Section IV-C).

• dSMC: Deterministic SMC analysis [START_REF] Baruah | Response-Time Analysis for Mixed Criticality Systems[END_REF].

• dAMC: Deterministic AMC analysis [START_REF] Baruah | Response-Time Analysis for Mixed Criticality Systems[END_REF].

• dUB: Task sets pass this 'test' if they are schedulable according to deterministic analysis of FPPS in each of the individual LO-criticality and HI-criticality modes with priorities in deadline monotonic order. This is a necessary test for any fixed priority preemptive mixed criticality scheduling algorithm [START_REF] Baruah | Response-Time Analysis for Mixed Criticality Systems[END_REF]. • pUB: Task sets pass this 'test' if they are schedulable according to probabilistic analysis of FPPS in each of the individual LO-criticality and HI-criticality modes with priorities in deadline monotonic order. The dominance relationships between the algorithms and tests implies a strict ordering to the lines on the graph: pUB dominates pAMC which dominates pSMC. Similarly dUB dominates dAMC which dominates dSMC. Further pUB dominates dUB, pAMC dominates dAMC, and pSMC dominates dSMC. The purpose of the experiment is to examine the relative performance of the different schemes.

In our experiment, the LO-criticality utilisation was varied from 0.05 to 1. For each utilisation value, 1000 task sets were generated and the schedulability of those task sets determined for the different schemes.

Figure 4 plots the percentage of task sets generated that were deemed schedulable for a system of 10 tasks, with on average 50% of those tasks having HI-criticality (CP = 0.5) and each task having a HI-criticality execution time that is 1.5 times its LO-criticality execution time (CF = 1.5). The utilisation values (x-axis) are computed using the C(LO) values and periods for each task. Figure 4 shows that the probabilistic analysis (pAMC and pSMC) provides substantially improved performance compared to deterministic analysis (dAMC and dSMC), with many more task sets deemed schedulable. This is because the probabilistic analysis is able to account for the full extent of the pWCET distributions, and thus the very small probability that multiple jobs take long execution times leading to a very long response time. We note that pAMC and pSMC may deem some tasks sets with LO-criticality utilisation greater than 1 schedulable. This is correct, and is a reflection of the shape of the pWCET distributions (see Figure 3). Recall that C(LO) has a probability of exceedance of 10 -5 thus once the distributions for a number of tasks are convolved, the probability that all of them execute for C(LO) or more becomes very small. Further, we note that the results for pSMC and pAMC converge at a very high values of LO-criticality utilisation. This is because finite values for R(LO) can no longer be computed via deterministic analysis. We note that using the deterministic R(LO) value in pAMC leads to only a small improvement over pSMC. In future, we will investigate whether an improved pAMC analysis can be obtained by making use of the probabilistic R(LO) distribution.

VI. CONCLUSIONS

In this paper we introduced probabilistic analysis for fixed priority preemptive scheduling of mixed criticality systems under the SMC [START_REF] Baruah | Schedulability Analysis of Sporadic Tasks with Multiple Criticality Specifications[END_REF] and AMC schemes [START_REF] Baruah | Response-Time Analysis for Mixed Criticality Systems[END_REF]. This analysis makes use of probabilistic worst-case execution time (pWCET) distributions to compute probabilistic worst-case response time distributions (pWCRT) and thus the worst-case deadline miss probability (DMP) for each task under SMC and AMC. Provided that the DMP is below the appropriate threshold 3 for that task, then it is declared schedulable.

The main contributions of this paper are as follows:

• Introducing probabilistic analysis of mixed criticality systems based on a richer mixed criticality model using pWCET distributions. • Deriving probabilistic worst-case response time analysis for both LO-and HI-criticality tasks under the SMC and 3 Derived from acceptable failure rates for tasks of that criticality.

AMC schemes. • Showing via an experimental evaluation that the probabilistic analyses, pSMC and pAMC, substantially out-perform their deterministic counterparts. This is due to the fact that low-probability unfavorable events such as all HI-criticality jobs simultaneously requiring additional execution time can be soundly ignored. In future, we intend to explore whether the probabilistic analysis framework can provide improved support for LO-criticality tasks based on the observation that the LO-criticality WCET estimates used in the deterministic representation are in reality tunable execution time budgets at different levels of assurance. We expect that the more effective probabilistic analysis will enable these budgets to be increased for both LO-and HI-criticality tasks, thus reducing the chance that HI-criticality mode is entered and lowering the likelihood that LO-criticality jobs have to be dropped or aborted.

  (a) partLO and full probability distribution for a HI-criticality task. (b) fullBE distribution for a LO-criticality task. (c) degen distribution for a LO-criticality task.

Fig. 2 :

 2 Fig. 2: Illustrations of the full and partial distributions used in probabilistic analysis.

•

  The LO-criticality execution time of each task was set based on the utilisation and period: C i (LO) = U i T i . • The HI-criticality execution time of each task was a fixed multiplier of the LO-criticality execution time, C i (HI) = CF • C i (LO) (default CF = 1.5), where CF is called the Criticality Factor. • The probability that a generated task was a HI-criticality task was given by the parameter CP (default CP = 0.5). • Task deadlines were constrained, chosen from a uniform distribution in the range [CF.C(LO), T ].

Fig. 3 :

 3 Fig. 3: Example of possible pWCET distributions.

Fig. 4 :

 4 Fig. 4: Percentage of task sets deemed schedulable according to the four tests: dSMC, dAMC, pSMC and pAMC.

We note that the relationship between failure rates and acceptable thresholds on failure probabilities is not direct, but rather depends on various factors considered in fault tree analysis[START_REF] Griffin | Evaluating mixed criticality scheduling algorithms with realistic workloads[END_REF]. In this paper, we assume that suitable values for the thresholds are given, and make a somewhat arbitrary choice of values for illustration purposes

Recall that by schedulable we mean that LO-criticality tasks must not exceed their DMP threshold in LO-criticality mode, and HI-criticality tasks must not exceed their DMP threshold in either mode.

Acknowledgements

The research described in this paper was partially funded by EU FP7 Integrated Project PROXIMA, the FR BGLE funded Departs project, the FR LEOC Capacites project, the FR FUI Waruna project, the ESPRC grant, MCC (EP/K011626/1), the Inria International Chair program, and the Ministry of Education Tier-2 grant, ARCS9/14. EPSRC Research Data Management: No new primary data was created during this study.


Farhood Negin
email: farhood.negin@inria.fr

Jérémy Bourgeois

Emmanuelle Chapoulie

Philippe Robert

Francois Bremond

Praxis and Gesture Recognition

Keywords: Gesture Recognition, Static and Dynamic Gestures, Alzheimer Disease, Reflection Time, Motion Descriptors

Introduction: Most of the developed societies are experiencing an aging trend of their population. Aging is correlated with cognitive impairment such as dementia and its most common type: Alzheimer's disease. So, there is an urgent need to develop technological tools to help doctors to do early and precise diagnoses of cognitive decline. Inability to correctly perform purposeful skilled movements with hands and other forelimbs most commonly is associated with Alzheimer's disease [START_REF] Mozaz | Posture recognition in alzheimers disease[END_REF]. These patients have difficulty to correctly imitate hand gestures and mime tool use, e.g. pretend to brush one's hair. These patients make spatial and temporal errors. Goal: We propose a gesture recognition and evaluation framework as a complementary tool to help doctors to spot symptoms of cognitive impairment at its early stages. It is also useful to assess one's cognitive status. First, the algorithm classifies the defined gestures in the gestures set and then it evaluates gestures of the same category to see how well they perform compared to correct gesture templates. Methods Shape and motion descriptors such as HOG (histogram of oriented gradient) [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] and HOF (histogram of optical flow) [START_REF] Dalal | Human detection using oriented histograms of flow and appearance[END_REF] are an efficient clue to characterize different gestures (Figure 1a). Extracted descriptors are utilized as input to train the classifiers. We use bag-ofvisual-words approach to characterize gestures with descriptors. The classification happens in two steps: first we train a classifier to distinguish different gestures and after, we train another classifier with correct and incorrect samples of the same class. This way, we could recognize which gesture is performed and whether it is performed accurately or not.

Experiments and Results

: the framework is fed by input data which comes from a depth sensor (Kinect®, Microsoft©). At first phase, the correct samples of gestures which are performed by clinicians, are recorded. We train the framework using correct instances of each gesture class. In the second phase, participants were asked to perform the gestures. We use virtual reality as modality to interact with subjects to make the experiments more immersive and realistic experience. First an avatar performs a specific gesture and then she asks the subject to repeat the same gesture (Figure 1b).

In this work, we analyze two categories of gestures. First category is dynamic gestures where the whole motion of the hands is considered as a complete gesture. Second category of gestures is static gestures where only a static pose of hands is the desired gesture. For static gestures, we also need to detect this key frame. Moreover, reaction time which starts after avatar asked the subject to do the gesture, until subject really starts to perform the gesture, could be an important diagnostic factor. Our algorithm uses motion descriptors to detect key frames and reaction time. In the preliminary tests, our framework successfully recognized more than 80% of the dynamic gestures. It also detects key frames and reaction time with a high precision. Conclusion: the proposed gesture recognition framework to help doctors by providing a complete assessment of gestures performed by subject.

Future Work: we will do extensive evaluation on large dataset collected from cognitively impaired patients with different levels of impairment. We will investigate more feature, like deep features on static gestures to achieve better classification accuracy. Detecting head and its relative position to hands could be a helpful clue to characterize different gestures.

Figure 1 .

 1 Figure 1. a) Extracted motion descriptors while performing a gesture b) virtual avatar guides patients in a virtual reality environment a b