Ezio Bartocci

Yliès Falcone

Giles Reger

International Competition on Runtime Verification (CRV)

We review the first five years of the international Competition on Runtime Verification (CRV), which began in 2014. Runtime verification focuses on verifying system executions directly and is a useful lightweight technique to complement static verification techniques. The competition has gone through a number of changes since its introduction, which we highlight in this paper.

Introduction

Runtime verification (RV) is a class of lightweight scalable techniques for the analysis of system executions [START_REF] Falcone | You should better enforce than verify[END_REF][START_REF] Falcone | A tutorial on runtime verification[END_REF][START_REF] Bartocci | Introduction to runtime verification[END_REF][START_REF] Bartocci | Lectures on Runtime Verification -Introductory and Advanced Topics[END_REF]. The field of RV is broad and encompasses many techniques. The competition has considered a significant subset of techniques concerned with the analysis of user-provided specifications, where executions are checked against a property expressed in a formal specification language. The core idea of RV is to instrument a software/hardware system so that it can emit events during its execution. The sequence of such events (the so-called trace) is then processed by a monitor that is automatically generated from the specification. One usually distinguishes online from offline monitoring depending on whether the monitor runs with the system or post-mortem (and thus collects events from a trace).

In 2014, we observed that, in spite of the growing number of RV tools developed over the previous decade, there was a lack of standard benchmark suites as well as scientific evaluation methods to validate and test new techniques. This observation motivated the promotion of a venue 4 dedicated to comparing and evaluating RV tools in the form of a competition. The Competition on Runtime Verification (CRV) was established as a yearly event in 2014 and has been organized as a satellite event of the RV conference since then [START_REF] Bartocci | First international competition on software for runtime verification[END_REF][START_REF] Bartocci | First International Competition on Runtime Verification: rules, benchmarks, tools, and final results of CRV 2014[END_REF][START_REF] Falcone | Second international competition on runtime verification CRV[END_REF][START_REF] Reger | Third international competition on runtime verification -CRV 2016[END_REF][START_REF] Reger | RV-CuBES[END_REF].

Over the last five years, the competition has helped to shape the development of new tools and evaluation methods but the broad objective of the competitions remain the same. CRV aims to:

stimulate the development of new efficient and practical runtime verification tools and the maintenance of the already developed ones; produce benchmark suites for runtime verification tools, by sharing case studies and programs that researchers and developers can use in the future to test and to validate their prototypes; discuss the metrics employed for comparing the tools; compare different aspects of the tools running with different benchmarks and evaluating them using different criteria; enhance the visibility of presented tools among different communities (verification, software engineering, distributed computing and cyber-security) involved in monitoring.

Related Work. Over the last two decades, we have witnessed the establishment of several software tool competitions [START_REF] Sutcliffe | The 5th IJCAR automated theorem proving system competition -CASC-J5[END_REF][START_REF] Barrett | 6 Years of SMT-COMP[END_REF][START_REF] Howar | Rigorous examination of reactive systems -the RERS challenges 2012 and 2013[END_REF][START_REF] Järvisalo | The international SAT solver competitions[END_REF][START_REF] Huisman | Verifythis 2012 -A program verification competition[END_REF][START_REF] Beyer | Software verification and verifiable witnesses -(report on SV-COMP 2015)[END_REF] with the goal of advancing the state-of-the-art in the computer-aided verification technology.

In particular, in the area of software verification, there are three related competitions: SV-COMP [START_REF] Beyer | Software verification and verifiable witnesses -(report on SV-COMP 2015)[END_REF], VerifyThis [START_REF] Huisman | Verifythis 2012 -A program verification competition[END_REF] and the RERS Challenge [START_REF] Howar | Rigorous examination of reactive systems -the RERS challenges 2012 and 2013[END_REF].

SV-COMP targets tools for software model checking, while CRV is dedicated to monitoring tools analyzing only a single program's execution using runtime and offline verification techniques. While in software model checking the verification process is separated from the program execution, runtime verification tools introduce instead an overhead for the monitored program and they consume memory resources affecting the execution of the program itself. As a consequence CRV assigns a score to both the overhead and the memory utilization. Another related series of competitions are VerifyThis [START_REF] Huisman | Verifythis 2012 -A program verification competition[END_REF] and the Rigorous Examination of Reactive Systems (RERS) challenge [START_REF] Howar | Rigorous examination of reactive systems -the RERS challenges 2012 and 2013[END_REF] that provide to the participants verification problems to be solved. On the contrary of CRV format, these competitions are problem centred and focus on the problem solving skills of the participants rather than on the tool characteristics and performance.

In the remainder of this paper, we discuss the early years of the competition during 2014-2016 (Section 2), the activities held in 2017 and 2018 that have shifted the focus of the competition (Section 3), and what the future holds for the competition in 2019 and beyond (Section 4).

The Early Years: 2014-2016

The early competition was organized into three different tracks: (1) offline monitoring, (2) online monitoring of C programs, and (3) online monitoring of Java programs. The competition spanned over several months before the announcement of results during the conference. The competition consisted of the following steps:

1. Registration collected information about participants. 2. Benchmark Phase. In this phase, participants submitted benchmarks to be considered for inclusion in the competition.

Table 1. Participants in CRV between 2014 and 2016.

Offline Track Online C Track Online Java Track

AgMon [START_REF] Kane | Monitor based oracles for cyberphysical system testing: Practical experience report[END_REF] E-ACSL [START_REF] Delahaye | Common Specification Language for Static and Dynamic Analysis of C Programs[END_REF] JavaMOP [START_REF] Jin | JavaMOP: Efficient Parametric Runtime Monitoring Framework[END_REF] BeepBeep3 [START_REF] Hallé | When RV meets CEP[END_REF] MarQ [START_REF] Barringer | Quantified Event Automata: Towards Expressive and Efficient Runtime Monitors[END_REF] JUnitRV [12] Breach RiTHM-1 [START_REF] Navabpour | RiTHM: a tool for enabling time-triggered runtime verification for c programs[END_REF] Larva [9] CRL [START_REF] Piel | Reconnaissance de comportements complexes par traitement en ligne de flux d'événements. (Online event flow processing for complex behaviour recognition)[END_REF] RTC [START_REF] Milewicz | Runtime checking c programs[END_REF] MarQ [START_REF] Barringer | Quantified Event Automata: Towards Expressive and Efficient Runtime Monitors[END_REF] LogFire [START_REF] Havelund | Rule-based Runtime Verification Revisited[END_REF] RV-Monitor [START_REF] Luo | Rvmonitor: Efficient parametric runtime verification with simultaneous properties[END_REF] Mufin [START_REF] Decker | Runtime monitoring with union-find structures[END_REF] MonPoly [START_REF] Basin | MONPOLY: Monitoring usage-control policies[END_REF] TimeSquare [START_REF] Deantoni | TimeSquare: Treat your Models with Logical Time[END_REF] RV-Monitor [26] MarQ [START_REF] Barringer | Quantified Event Automata: Towards Expressive and Efficient Runtime Monitors[END_REF] OCLR-Check [START_REF] Dou | A model-driven approach to offline trace checking of temporal properties with ocl[END_REF] OptySim [START_REF] Díaz | Obtaining models for realistic mobile network simulations using real traces[END_REF] RiTHM-2 [START_REF] Navabpour | RiTHM: a tool for enabling time-triggered runtime verification for c programs[END_REF] RV-Monitor [START_REF] Luo | Rvmonitor: Efficient parametric runtime verification with simultaneous properties[END_REF] 3. Clarification Phase. The benchmarks resulting from the previous phase were made available to participants. This phase gave participants an opportunity to seek clarifications from the authors of each benchmark. Only benchmarks that had all clarifications dealt with by the end of this phase were eligible for the next phase. 4. Monitor Phase. In this phase, participants were asked to produce monitors for the eligible benchmarks. Monitors had to be runnable via a script on a Linux system. Monitor code should be generated from the participant's tool (therefore the tool had to be installable on a Linux system). 5. Evaluation Phase. Submissions from the previous phase were collected and executed, with relevant data collected to compute scores as described later. Participants were given an opportunity to test their submissions on the evaluation system. The outputs produced during the evaluation phase were made available after the competition.

Input Formats. The competition organizers fixed input formats for traces in the offline track. These were based on XML, JSON, and CSV and evolved between the first and second years of the competition based on feedback from participants. The CSV format proved the most popular for its simplicity and is now used by many RV tools. See the competition report from 2015 [START_REF] Falcone | Second international competition on runtime verification CRV[END_REF] for details.

Participants. Over the first three years of the competition 14 different RV tools competed in the competition in the different tracks. These are summarized in Table 1. One of these tools, Mufin, was written specifically in response to the competition and all tools were extended or modified to handle the challenges introduced by the competition.

Benchmarks. Benchmarks, as submitted by the participants, should adhere to requirements that ensured compliance with the later phases of the competition. This also ensured uniformity between benchmarks and was also the first step in building a benchmark repository dedicated to Runtime Verification. A benchmark contains two packages: a program/source package and a specification package. The program/source package includes the traces or the source of the program as well as scripts to compile and run it. In these early years of the competition, we chose to focus on closed, terminating and deterministic programs.

The specification package includes an informal and a formal description (in some logical formalism), the instrumentation information (i.e., what in the program influences the truth-value of the specification), and the verdict (i.e., how the specification evaluates w.r.t. the program or trace).

In these three competitions, over 100 benchmarks were submitted and evaluated. All benchmarks are available from the competition website5 organized in a repository for each year.

Evaluation criteria/scores. Submissions from the participants were evaluated on correctness and performance. For this purpose, we designed an algorithm that uses as inputs (i) the verdicts produced by each tool over each benchmark (ii) the execution time and memory consumption in doing so, and produces as output a score reflecting the evaluation of the tool regarding correctness and performance (the higher, the better). Correctness criteria included (i) finding the expected verdict, absence of crash, and the possibility of expressing the benchmark specification in the tool formalism. Performance criteria were based on the classical time and memory overheads (lower is better) with the addition that the score of a participant accounts for the performance of the other participants (e.g., given the execution time of a participant, more points would be given if the other participants performed poorly) using the harmonic mean. Tools were evaluated against performance, only when they produced a correct result (negative points were given to incorrect results). A benchmark score was assigned for each tool against each submitted benchmark, and the tool final score was the sum of all its benchmark scores. A participant could decide not to compete on a benchmark and would get a zero score for this benchmark.

Experimental environment, availability, reproducibility, quality. Git-based repositories and wiki pages were provided to the participants to share their benchmarks and submissions. This facilitated the communication and ensured transparency. To run the experiments, we used DataMill [START_REF] Petkovich | Datamill: a distributed heterogeneous infrastructure for robust experimentation[END_REF], to ensure robust and reproducible experiments. We selected the most powerful and general-purpose machine and evaluated all submissions on this machine. DataMill ensured flexibility and fairness in the experiments. Benchmarks could be setup and submitted via a Web interface and then be scheduled for execution. DataMill ensured that only one monitor was running on the machine at a time, in addition to a minimalist operating system, cleaned between each experiments. Execution times and memory consumption measures were obtained by averaging 10 executions. Results were available through the Web interface. Winners. Table 2 indicates the winners in each track in each year. The detailed results are available from the competition website and associated reports [START_REF] Bartocci | First international competition on software for runtime verification[END_REF][START_REF] Bartocci | First International Competition on Runtime Verification: rules, benchmarks, tools, and final results of CRV 2014[END_REF][START_REF] Falcone | Second international competition on runtime verification CRV[END_REF]. In 2014, the scores in the Online Java track were so close that a joint winner was announced. In 2016, only one participant entered the C track and the track was not run. (We note that, more tools have been developed for monitoring Java programs thanks to the AspectJ support for instrumentation.)

Issues. The early years of the competition were successful in encouraging RV tool developers to agree on common formats but the number of participants dropped in each year with two main issues identified:

1. The amount of work required to enter was high. This was mainly due to the need to translate each benchmark into the specification language of the entered tool. Common specification languages would address there was no agreement on such languages at the time. 2. It was not clear how good the benchmarks were at differentiating tools.

More work was required to understand which benchmarks were useful for evaluating RV tools.

The next two years of activities addressed these issues as described below.

3 Shifting Focus: 2017-2018

In 2017, the competition was replaced by a workshop (called RV-CuBES) [START_REF] Reger | RV-CuBES[END_REF] aimed at reflecting on the experiences of the last three years and discussing future directions. A workshop was chosen over a competition as there was strong feedback from participants in 2016 that the format of the competition should be revised (mainly to reduce the amount of work required by participants). It was decided that this was a good opportunity to reassess the format of the competition in an open setting. The workshop attracted 12 tool description papers and 5 position papers and led to useful discussion at the 2017 RV conference. A full account can be found in the associated report. A suggestion of the workshop was to hold a benchmark challenge focusing on collecting relevant new benchmarks. Therefore, in 2018 a benchmark challenge was held with a track for Metric Temporal Logic (MTL) properties and an Open track. The purpose of the MTL track was to see what happened when participants were restricted to a single input language whilst the Open track gave full freedom on the choice of the specification language.

There were two submissions in the MTL track and seven in the Open track. The submissions in the Open track were generally in much more expressive languages than MTL and no two submissions used the same specification language. All submissions were evaluated by a panel of experts and awarded on qualities in three categories: (1) correctness and reliability, (2) realism and challenge, and (3) utility in evaluation. As a result of the evaluation two benchmark sets were identified for use in future competitions (see below).

Back to the Future

The 2019 competition is now in its initial stages and will return to a competition comparing tools, using the benchmarks from the 2018 challenge. The competition will use two specification languages: MTL and a future-time first-order temporal logic. We have chosen to fix two specification languages (with differing levels of expressiveness) to reduce the overall work for participants. Standardising the specification language of the competition has been a goal of the competition from the start and the benchmark challenge has allowed us to pick two good candidates. MTL was chosen as it can be considered a 'smallest shared' specification language in terms of expressiveness and usage. Similarly, the future-time first-order temporal logic was chosen as it can be considered a 'largest shared' specification language in terms of expressiveness and usage.

Beyond 2019, there are many opportunities to take the competition in different directions. For example, a key issue in RV is that of specifications. Thus, when organizing a competition, one may wonder whether a competition could also focus on evaluating aspects related to specifications (e.g., expressiveness, succinctness and elegance of specifications). Moreover, in so far, the competition has neglected the area of hardware monitoring, and the comparison of tools in such domains remains an open question. We note that there have been less research efforts on monitoring hardware where instrumentation aspects are more challenging. The main reasons for common specification languages not being used in the early years stemmed from two facts: (i) a main research activity in RV consists in developing new languages to have alternative representation of problems (ii) the monitoring algorithm of an RV tool is often closely coupled to the input language. Hence, a challenge is to rely on a shared specification language whilst encouraging research that explores the relationship between input language and performance or usability.

Table 2 .

 2 Winners of CRV between 2014 and 2016.

	Year Offline Track Online C Track	Online Java Track
	2014	MarQ	RiTHM-1	MarQ & JavaMOP (joint)
	2015	LogFire	E-ACSL	Mufin
	2016	MarQ	-	Mufin

https://www.rv-competition.org/benchmarks/

Acknowledgements

The authors would like to thank the anonymous reviewers for their helpful comments and all the colleagues involved in CRV over the last years (B. Bonakdarpour, D. Thoma, D. Nickovic, S. Halle, K. Y. Rozier, and V. Stolz).

This work was partially supported by the Austrian FWF-funded National Research Network RiSE/SHiNE S11405-N23 and ADynNet project (P28182). 4 https://www.rv-competition.org/


Pascale Minet
email: pascale.minet@inria.fr

Yasuyuki Tanaka
email: 2yasuyuki.tanaka@inria.fr

Optimal Number of Message Transmissions for Probabilistic Guarantee in the IoT

Keywords: IoT, industrial IoT, reliability, TSCH, latency, scheduling, network lifetime, IEEE802.15.4e, PDR, ETX, retransmission, probabilistic guarantee

The Internet of Things (IoT) is now experiencing its first phase of industrialization. Industrial companies are completing proofs of concept and many of them plan to invest in automation, flexibility and quality of production in their plants. Their use of a wireless network is conditioned upon its ability to meet three Key Performance Indicators (KPIs), namely a maximum acceptable end-to-end latency L, a targeted end-to-end reliability R and a minimum network lifetime T . The IoT network has to guarantee that at least R% of messages generated by sensor nodes are delivered to the sink with a latency ≤ L, whereas the network lifetime is at least equal to T . In this paper, we show how to provide the targeted end-to-end reliability R by means of retransmissions to cope with the unreliability of wireless links. We present two methods to compute the maximum number of transmissions per message required to achieve R. M F air is very easy to compute, whereas M Opt minimizes the total number of transmissions necessary for a message to reach the sink. M F air and M Opt are then integrated into a TSCH network with a load-based scheduler to evaluate the three KPIs on a generic data-gathering application. We first consider a toy example with eight nodes where the maximum number of transmissions M axT rans is tuned per link and per flow. Finally, a network of 50 nodes, representative of real network deployments, is evaluated assuming M axT rans is fixed. For both TSCH networks, we show that M Opt provides a better reliability and a longer lifetime than M F air, which provides a shorter average end-to-end latency. M Opt provides more predictable end-to-end performances than Kausa, a KPI-aware, state-of-the-art scheduler.

I. INTRODUCTION

The Internet of Things (IoT) is transforming our daily life at home [START_REF] Delaney | A framework to implement IoT network performance modelling techniques for network solution selection[END_REF], at work, in our cities [START_REF] Tao | Locating compromised data sources in IoT-enabled smart cities: A great-alternative-region-based approach[END_REF], in transportation [START_REF] Tao | Location-based trustworthy services recommendation in cooperative-communication-enabled internet of vehicles[END_REF], in sport training and healthcare, in process control and automation, in smart farming and beyond.

A. Context

At home or in the office, the IoT allows us to save time and energy by controlling lights and appliances and knowing our resource consumption habits. In business and industry, it increases productivity and efficiency by streamlining processes. In transportation, it helps people to enjoy services of better quality. IoT devices are electronic devices able to communicate with a network and perform a task. We can draw a distinction between consumer devices, smart home devices, enterprise and industrial IoT devices. In this paper, we do not focus on IoT devices themselves, but rather on applications using these devices. More precisely, we will consider IoT applications that are responsible for data gathering and are the most demanding in terms of quality of service provided by the networks supporting them [START_REF] Kumar | A survey on IoT performances in big data[END_REF], [START_REF] Srinidhi | Network optimizations in the Internet of Things: A review[END_REF]. We will consider three types of requirements:

• end-to-end reliability, denoted R: the data generated by any sensor node must be delivered to the sink with a probability greater than or equal to R. A value of 0.99 is frequent. In industry, a value of 0.99999 is targeted. • end-to-end latency, denoted L: since, on the one hand, the role of the network is to collect data generated by wireless sensor nodes that are deployed in the area covered by this network and, on the other hand, only up-to-date information can be used to take accurate decisions, the time elapsed between data generation and data delivery to the sink is defined as the end-to-end latency. A value less than one second is usual. • network lifetime, denoted T : since most IoT devices are battery operated, the goal of the network is to maximize its lifetime defined as the time when the first device has exhausted its battery. The importance of this requirement increases with the difficulty or the cost of replacing a battery in the environment concerned. A lifetime of several years (e.g., 3 years) is usual. Since most wireless sensor networks deployed up to now are based on the IEEE 802.15.4 technology [START_REF]IEEE Standard for Local and Metropolitan Area Networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs); IEEE Std[END_REF] and, given that the TSCH (Time Slotted Channel Hopping) technology [START_REF]IEEE Standard for Local and Metropolitan Area Networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs)-Amendment 1: MAC Sublayer; IEEE Std[END_REF] has been designed to enhance the IEEE 802.15.4 technology to better meet the three types of requirements previously defined, we focus our study on TSCH networks. Is a TSCH network able to meet the usual requirements of IoT applications? The goal of this paper is to answer this question, which can be refined into: is a TSCH network capable of ensuring that at least R percent of messages will be delivered to the sink with a delay less than or equal to L, and a network lifetime greater than or equal to T , while taking into account the unreliability of wireless links.

B. Contributions

Before going further, we define the concept of flow. A f low is defined as a set of messages having the same attributes such as the source address, the destination address and the QoS (Quality of Service) parameters (e.g., end-to-end reliability, end-to-end latency).

In contrast to many network performance evaluations, we take into account the unreliability of wireless links. The first contribution of this paper is to show how to reach the targeted end-to-end reliability R with two methods M F air and M Opt able to estimate the maximum number of transmissions per message and per flow over each link visited, taking into account both the heterogeneity of link quality and the dynamicity of link quality observed on real traces. Whereas M F air is very simple, M Opt minimizes the total number of transmissions per message, for each flow considered. The second contribution consists of providing a fully-integrated approach for a TSCH network by integrating these methods and a Load-based scheduler in the 6TiSCH stack. As a third contribution, we evaluate the performances (i.e., the end-to-end reliability and the end-to-end latency) obtained by this approach on two TSCH networks, one of eight nodes and the other of 50 nodes. Finally, we show that, on a generic data-gathering application, this approach provides more predictable end-to-end performances than Kausa [START_REF] Gaillard | KPI-aware scheduling algorithm for multi-flow in multi-hop IoT networks[END_REF], a KPI-aware state-of-the-art scheduler.

This paper is organized as follows. In Section II, we present the advantages and drawbacks of well-known link quality estimators and show how they are used to enhance network performances. Since the approach proposed in this paper shares the same goals as Kausa [START_REF] Gaillard | KPI-aware scheduling algorithm for multi-flow in multi-hop IoT networks[END_REF], Kausa is briefly described. A more detailed description is given in Section VII. Section III describes the two methods we propose to estimate the maximum number of transmissions per message and per flow over each link visited. Section IV shows how to integrate these methods in a TSCH network with a centralized scheduling function. Section V gives performance results with regard to end-to-end reliability and end-to-end latency for a targeted end-to-end reliability ranging from 0.9 to 0.99999 for a toy example. In Section VI, a TSCH network of 50 nodes is considered with a generic data-gathering application. End-to-end latency and reliability are evaluated. The solution proposed is compared to Kausa in Section VII. Finally, we conclude in Section VIII.

II. RELATED WORK

Different ways to estimate the quality of a wireless link exist. They all rely on link measurements obtained by an active, passive or hybrid link monitoring. A usual classification distinguishes between hardware and software-based link quality estimators [START_REF] Kirubasri | A study on hardware and software link quality metrics for wireless multimedia sensor networks[END_REF], [START_REF] Baccour | Radio link quality estimation in wireless sensor networks: A survey[END_REF]. Hardware estimators have the advantage of being directly provided by hardware without the need for any additional processing overhead. However, their accuracy is not very good for two reasons. First, they are measured only on successfully received packets, and they do not take into account the number of packet losses. Second, they are not evaluated on the whole packet received but only on eight symbols of this packet. The main hardware-based quality estimators are RSSI (Received Signal Strength Indicator), LQI (Link Quality Indicator), and SNR (Signal-to-Noise Ratio). In addition, LQI depends on the manufacturer of the radio transceiver used. For the software-based quality estimators, we distinguish those based on PRR (Packet Reception Rate), from those based on RNP (Required Number of Packet retransmissions) and finally those using a score. For instance, ETX (Expected Transmission Count) [START_REF] De Couto | A high-throughput path metric for multi-hop wireless routing[END_REF] is classified as an RNP-based estimator, whereas F-LQE (Fuzzy Link Quality Estimator) [START_REF] Baccour | A fuzzy link quality estimator for wireless sensor networks[END_REF] is a score-based one assessing link quality in terms of four properties: Smoothed Packet reception Ratio, Stability factor, ASymmetry Level and channel Average Signal-to-Noise Ratio. In [START_REF] Pöttner | Constructing schedules for time-critical data delivery in wireless sensor networks[END_REF], the authors introduce Bmax, the maximum count of consecutive transmissions needed for a frame to be transmitted on a link. This metric evaluates the link burstiness, where a burst is defined as a period of continuous packet loss. It is obtained empirically for each link based on previous transmissions and can be seen as an observed worst case. Then, they build a schedule that allocates Bmax cells for every frame that a link is supposed to carry. The problem with such a method is that it may require a long delay (more than 140 hours according to the authors) before a representative Bmax is known for all the links.

Whatever the link quality estimator used, authors usually agree on the following conclusions:

• The quality of any wireless link can be classified as good, intermediate or bad. The challenge lies in an accurate estimation of the intermediate link quality. • An ideal link quality estimator should be [START_REF] Baccour | Radio link quality estimation in wireless sensor networks: A survey[END_REF] energy efficient (i.e., requiring low processing, communication and memory overhead), accurate (i.e., reflecting the real link behavior), reactive (i.e., able to promptly react to persistent link state changes) and stable (i.e., able to tolerate transient link state changes). • To better reflect the real behavior of a link, several link properties should be taken into account. That is why link quality estimators tend to combine several simple estimators [START_REF] Vlavianos | Assessing link quality in IEEE 802.11 wireless networks: Which is the right metric[END_REF] and use sophisticated techniques (e.g., simple average, filtering, machine learning [START_REF] Cerar | Link Quality Estimation using Machine Learning[END_REF], [START_REF] Sun | WNN-LQE: Wavelet-neural-network-based link quality wstimation for smart grid WSNs[END_REF], regression, and fuzzy logic [START_REF] Rekik | Low-Power link quality estimation in smart grid environments[END_REF], [START_REF] Guo | Fuzzy logic based multidimensional link quality estimation for multi-hop wireless sensor networks[END_REF]) to produce a metric from link measurements. Link quality estimators have been used to improve the quality of service provided to end-users [START_REF] Nguyen | Quality of service routing in a MANET with OLSR[END_REF]. By using links of better quality, the network throughput is maximized, the delivery times are minimized, routes are more stable [START_REF] Guo | Fuzzy logic based multidimensional link quality estimation for multi-hop wireless sensor networks[END_REF], etc. These improvements can be increased by link quality prediction using online machine learning techniques as in [START_REF] Marinca | On-line learning and prediction of link quality in wireless sensor networks[END_REF]. In such a case, packets are then able to avoid links before their quality degrades below an acceptable threshold, and routing reactivity is improved. Furthermore, if both the link quality estimator and the routing protocol take energy into account, network lifetime is maximized, as in [START_REF] Mahfoudh | Energy efficient routing and node activity scheduling in the OCARI wireless sensor network[END_REF].

Closer to our work, Gaillard et al. propose a greedy algorithm that optimizes the distribution of links used by flows networkwide [START_REF] Gaillard | Enabling Flow-Level Reliability on FTDMA Schedules with Efficient Hop-by-Hop Over-Provisioning[END_REF]. These authors extend TASA [START_REF] Palattella | Traffic Aware Scheduling Algorithm for reliable low-power multi-hop[END_REF], a well-known centralized scheduling algorithm for FTDMA networks, to take into account retransmissions and fragmented packets. They build a schedule that complies with reliability expectation by adding extra cells that are used in the case of consecutive retransmissions. They take into account link quality and packet fragmentation. The same authors further extend their research in [START_REF] Gaillard | KPI-aware scheduling algorithm for multi-flow in multi-hop IoT networks[END_REF] by proposing Kausa, a centralized scheduling algorithm that builds resource paths that guarantee QoS per flow, when multiple applications are using the same network, and each application has its own requirements and traffic flows.

In this paper, we propose to use a simple link quality estimator: PDR (Packet Delivery Rate) that is easily computed by the sender as the ratio of the number of acknowledged frames to the number of sent frames. Even if this estimator is not ideal, as previously defined, it provides an accurate estimation of link behavior because, unlike hardware-based link estimators, it takes into account packet losses. We use the PDR link quality estimator to compute the maximum number of transmissions per message and per flow over any link visited by the flow considered.

We share the same goal as Kausa [START_REF] Gaillard | KPI-aware scheduling algorithm for multi-flow in multi-hop IoT networks[END_REF]: namely, to build a centralized schedule ensuring that flows meet their required endto-end latency and delivery rate, by means of message retransmissions. Like [START_REF] Gaillard | KPI-aware scheduling algorithm for multi-flow in multi-hop IoT networks[END_REF], we adopt a per flow approach, allowing us to differentiate QoS per flow. However, unlike [START_REF] Gaillard | KPI-aware scheduling algorithm for multi-flow in multi-hop IoT networks[END_REF], we consider the optimal solution for any flow to be the one that minimizes the total number of transmissions per message of this flow, while achieving the desired end-to-end reliability. Furthermore, traces obtained from real IoT networks like [START_REF] Audéoud | Quick and efficient link quality estimation in wireless sensors networks[END_REF], [START_REF] Brun-Laguna | Moving beyond testbeds? Lessons (we) learned about connectivity[END_REF] allow us to better understand the challenges of wireless networking and make realistic assumptions. That is why, in this paper, the performance evaluation is based on PDR values computed from a realistic model, as explained in Section VI-A.

III. OPTIMAL RETRANSMISSION ESTIMATION

To cope with the unreliability of network links, unacknowledged messages are retransmitted up to a maximum number of retransmissions. We have to determine this maximum number that of course depends on the unreliability of the link considered as well as the targeted end-to-end reliability R.

Since each flow may request its own QoS, we adopt a per-flow approach. Without loss of generality, we assume that each message is labeled with its flow tag, which includes the origin node of the flow.

A. Assumptions and Basic Properties

Let us consider the flow f originating from any sensor node N h with h ∈ [1, n]. Let h denote the path length (i.e., the number of hops) from N h to the sink N 0 . To simplify the notation, we assume that the path is defined by

N h → N h-1 → N h-2 • • • → N 0 .
For any link j ∈ [1, h] of f 's path, we denote by M j the maximum number of transmissions of any message of f transmitted by node N j to its parent in the routing tree, and P j the probability of successful acknowledgment receipt after a single transmission, whereas R j is the probability of successful acknowledgment receipt on link j after a maximum number M j ≥ 1 of transmissions. Table I gives the notations used in this paper.

TABLE I: Main notations.

Name Meaning R the targeted end-to-end reliability L the targeted end-to-end latency T the targeted network lifetime j the link from node N j to its parent in the routing tree M j the maximum number of transmissions of any message transmitted on link j P j the probability of successful acknowledgment receipt after a single message transmission on link j R j the probability of successful acknowledgment receipt on link j after a maximum number M j of transmissions

For the sake of simplicity, we adopt the following assumptions:

Assumption 1. Network links fail independently.

Assumption 2. The transmissions of any message fail independently.

Assumption 3. Each node has enough Transmission opportunities to prevent message drops due to Transmission queue overflow.

In a TSCH network, this assumption means that the scheduling algorithm has assigned enough transmission cells to each node. As a consequence, the unreliability of a transmission is only due to the unreliability of the wireless link considered. If this assumption were not true, then the computation of the transmission reliability should include not only the message loss due to the unreliability of the wireless link considered but also the message loss due to Transmission queue overflow.

We first recall some basic properties: Property 1. The end-to-end reliability on a path is equal to the product of the reliability of each link composing that path.

Property 2. The probability of successful acknowledgment receipt over any link j increases with the maximum number of message transmissions M j according to the following equation:

R j = 1 -(1 -P j ) Mj .
(1)

Proof. After M j transmissions, the acknowledgment of a message is not received successfully with a probability equal to (1-P j ) Mj . Hence, the probability of successful acknowledgment receipt after M j transmissions is equal to 1-(1-P j ) Mj .

B. A Fair Method

The question is: knowing the end-to-end reliability that must be met on a given path, how to distribute this targeted end-toend reliability into the targeted reliability of each link on that path? The maximum number of transmissions on each link is then deduced from the targeted reliability on the link and the probability of successful transmission on that link. In this paper, we propose two methods that can be applied to any network meeting Assumptions 1-3.

Since we adopt a per-flow approach, we consider any flow f , originating from a node h hops away from the sink. In other words, the path of f consists of h links, h ≥ 1. Since the end-to-end reliability on the path is equal to the product of the reliability of each of its links, which should be ≥ R, a simple solution consists of fairly and uniformly sharing the end-to-end reliability over each link of the path. Hence, each link j has to meet a reliability equal to R j = R 1/h . The maximum number of transmissions on any link j is then equal to

M j = Log(1-R 1/h )
Log(1-Pj ) . This principle is applied by the M F air Algorithm given hereafter (see Algorithm 1).

Algorithm 1 M F air: compute the number of transmissions on each link j to reach a reliability R 1/h over this link per message of flow f visiting h links.

Require: R the targeted end-to-end reliability, P j =the success probability of receiving the acknowledgment after a single message transmission over link j with 1 ≤ j ≤ h Ensure: M j is the minimum number of transmissions on link j to achieve R 1/h for each link j do if

P j = 1 then M j ← 1 else M j ← Log(1-R 1/h ) Log(1-Pj ) end if
end for Property 3. The processing complexity of the M F air Algorithm is in O(1).

Proof. The complexity of the Fair Algorithm is equal to the complexity of computing

Log(1-R 1/h ) Log(1-Pj )
for each link, times h the number of links, hence the property.

Figure 1 depicts the maximum number of transmissions over a link whose probability of successful acknowledgment receipt ranges from 0.5 to 0.9 for a 4-hop flow when the targeted end-to-end reliability ranges from 0.9 to 0.9999.

C. An Optimal Method

For any sensor node N i , let us denote f the flow originating from N i . The problem consists of minimizing the total number of transmissions needed to deliver any message of f to the sink, under the constraint that the end-to-end latency is greater than or equal to R.

The optimization problem can be defined as follows: Goal: Find the values of M j for each link j visited by f , j = 1 • • • h that minimize h j=1 M j under the constraints:

h j=1 (1 -(1 -P j ) Mj ) ≥ R, (2)
M j integer ≥ 1. (3)
If several solutions exist for the same total number of transmissions, choose the solution maximizing

h j=1 (1 -(1 -P j ) Mj ). Lemma 1. Each link j = 1 • • • h should provide a reliability R j at least equal to the requested end-to-end reliability R, R j ≥ R. Hence, M j ≥ Log(1-R)
Log(1-Pj ) . Proof. If there is a link j that provides a reliability R j < R, then the product of the reliability of all other links should be greater than 1 to obtain an end-to-end reliability of R, which is impossible. Therefore, each link has to provide a reliability at least equal to R by means of retransmissions. Since the reliability of a link j increases with the maximum number of transmissions according to Equation (1), to obtain an end-to-end reliability of R, the number of transmissions M j should be greater than or equal to that needed to obtain a link reliability of R, leading to

M j ≥ Log(1-R) Log(1-Pj ) .
Lemma 2. There is no solution ensuring an end-to-end reliability ≥ R, with a total number of transmissions <

h j=1 Log(1-R) Log(1-Pj ) . Proof. It is deduced from Lemma 1. Lemma 3.
If there is no solution ensuring an end-to-end reliability greater than or equal to R, with a total number of transmissions

≤ M = h j=1 Log(1-R)
Log(1-Pj ) and, if increasing M j to M j + 1 for the link j maximizing the value of P j (1/R j -1) does not achieve R, then there is no solution ensuring an end-to-end reliability R in M + 1 transmissions.

Proof. Assuming that there is no solution ensuring an end-to-end reliability ≥ R, with a total number of transmissions

≤ M = h j=1 Log(1-R)
Log(1-Pj ) , we compute, for any link k, the benefit on the end-to-end reliability brought by increasing M k to M k +1. The new end-to-end reliability can be written newR = (

h j=1,j =k R j )(1-(1-P k ) M k +1 ). Since 1-(1-P k ) M k +1 = 1 -(1 -P k )(1 -P k ) M k = R k + P k (1 -R k ), we get newR = ( h j=1,j =k R j )(R k + P k (1 -R k )). Denoting h j=1 R j as oldR,
we get newR = oldR(1 -P k + P k /R k ). Hence, maximizing newR means selecting the link k that maximizes P k (1/R k -1). Hence, if with that link k, the end-to-end reliability newR is not greater than or equal to R, then no other link can meet the end-to-end reliability R with a total number of transmissions equal to M + 1.

Property 4. The M Opt algorithm given in Algorithm 2 finds the optimal solution.

Proof. The algorithm starts with the smallest possible number of transmissions M , according to Lemma 2. If the requested end-to-end reliability is met, then the solution is found. Otherwise, the algorithm increases the total number of transmissions by one and checks again whether the requested end-to-end reliability is met by increasing the number of transmissions of one on the link providing the highest reliability gain. If yes, the solution is found, otherwise there is no solution for M + 1 transmissions.

Algorithm 2 M Opt: Compute the number of transmissions M j on link j to achieve an end-to end reliability ≥ R and minimize the total number of transmissions per message of flow f visiting h links Require: R the targeted end-to-end reliability 0 < R < 1, P j =the probability of successful acknowledgment receipt after a single transmission over link j with 1 ≤ j ≤ h Ensure: M j is the minimum number of transmissions to achieve R for each link j do if

P j = 1 then M j ← 1 else M j ← Log(1-R) Log(1-Pj ) R j ← 1 -(1 -P j ) Mj Gain j ← P j (1/R j -1) end if end for while h j=1 R j < R do Select the link j maximizing Gain j
If several links provide the same Gain, take the farthest link j from the sink

M j ← M j + 1 R j ← 1 -(1 -P j ) Mj Gain j ← P j (1/R j -1) end while
We now evaluate the complexity of this algorithm and more particularly we upper bound the number of iterations needed to find the maximum number of transmissions over each link such that the total number of transmissions per message of the flow considered is minimized. Property 5. The M Opt Algorithm, given in Algorithm 2, finds the optimal solution in a number of iterations less than or equal to

h j=1 Log(h) Log(1-Pj ) .
Proof. Let us consider any link j visited by the flow considered. Since R → 1, we have

R 1/h < 1 -1-R h . Hence, Log(1 -R 1/h ) > Log(1 -R) -Log(h), leading to: Log(1-R 1/h ) Log(1-Pj ) < Log(1-R)-Log(h) Log(1-Pj ) . We then obtain Log(1-R 1/h ) Log(1-Pj ) ≤ Log(1-R)-Log(h) Log(1-Pj ) . Since a -b ≤ a -b , we get: M j,f air -M j,init ≤ Log(h)
Log(1-Pj ) , where M j,f air denotes the maximum number of transmissions over link j, whereas M j,init denotes the first value tried by the optimal algorithm. Since h j=1 M j,f air is the maximum number of transmissions of a message to reach the sink provided by the Fair algorithm and this number is never exceeded by the Optimal algorithm, the maximum number of iterations of the Optimal algorithm is upper bounded by

h j=1 M j,f air - h j=1 M j,init ≤ Log(h)
Log(1-Pj ) , hence the property.

D. Expected vs. Maximum Number of Transmissions

For any flow considered and whatever the method adopted to compute the maximum number of transmissions over each link visited by the flow considered, the real number of transmissions used is much smaller than the maximum one, which occurs with a very low probability. In this section, we want to evaluate the energy saving obtained with a variable number of transmissions instead of always considering the worst case that has a very low occurrence probability. With the Assumptions 1, 2 and 3, we can evaluate E(M j ) the expected number of transmissions on any link j, knowing that M j , the maximum number of transmissions, is computed either by M F air or by M Opt. We then have:

E(M j ) = Mj -1 k=1 kP j (1 -P j ) k-1 + M j (1 -P j ) Mj -1 . Property 6.
The expected number of transmissions on any link j is equal to

E(M j ) = 1 -(1 -P j ) Mj P j ,
where M j denotes the maximum number of transmissions used for link j.

Proof. Let us consider S n (x) = n k=1 (1 + x) k and let S n (x) be its derivative. We have

S n (x) = n k=1 k(1 + x) k-1 . Since S n (x)
is the sum of a geometric progression, we have:

S n (x) = -1+x-(1+x) n+1 x = (1+x)((1+x) n -1)
x . Hence, the derivative is:

S n (x) = (1+x) n (nx-1)+1 x 2
. By replacing x by -P j and n by M j -1, we get

E(M j ) = Mj -1 k=1 kP j (1-P j ) k-1 +M j (1-P j ) Mj -1 = 1-(1-Pj ) M j -1 (-1-(Mj -1)Pj )+1 Pj = 1-(1-Pj ) M j Pj
, hence the property.

Figure 2 depicts the maximum and the expected numbers of transmissions per message of a 4-hop flow, for a targeted endto-end reliability of 0.9999, over a link whose success probability per transmission ranges from 0.5 to 0.9. We observed that, in all the cases studied, although the value of E(M j ) decreases when P j , the success probability per transmission increases, E(M j ) remains constant and equal to 2. By stopping its retransmissions as soon it receives an acknowledgment, the sender saves its energy. For instance, let us consider that for any link j for which P j = 0.5 is visited by a 4-hop flow, the sender saves M j -E(M j ) transmissions for this link that is 16 -2 = 14 transmissions for M F air. Since the flow visits four hops and assuming that its four links have the same success probability, each of the four transmitting nodes saves 14 transmissions. Assuming that the schedule is periodic with a period of 101 time slots (the default value in the TSCH network), and this flow generates a message per schedule period, these four nodes save 140 ms each schedule period of 101 × 7.25 = 732.25 ms, for a slot duration of 7.25 ms. This corresponds to an increase of 19% in sleeping time per schedule period for each node. It is useful to compare this value with the value of ETX on link j, denoted by ET X j . Let D j be the delivery rate from node j to its parent, whereas D r(j) is the delivery rate in the reverse direction. Since P j is defined as the probability for j to receive the acknowledgment of its message, we have to take into account the delivery rates of both directions, which gives:

P j = D j * D r(j) (4)
ET X j is defined as:

ET X j = 1 D j * D r(j) . (5)
As a consequence, ET X j does not depend on the targeted end-to-end reliability R but only on the reliability of both directions of the link considered. This explains the main difference between ET X j and M j .

In addition, ET X j is not equal to E(j). Indeed, E(j) assumes a maximum number of transmissions equal to M j , whereas ET X j assumes a number of transmissions that may be infinite.

IV. FRAMEWORK FOR A TSCH NETWORK

The M Opt and M F air methods are now applied to compute the maximum number of transmissions per link and per flow. Flows are generated by a low-power network based on the TSCH technology [START_REF]IEEE Standard for Local and Metropolitan Area Networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs)-Amendment 1: MAC Sublayer; IEEE Std[END_REF].

We focus on data gathering applications with end-to-end requirements in terms of reliability and latency, as well as requirements with regard to network lifetime. The network supporting these applications is a TSCH network [START_REF]IEEE Standard for Local and Metropolitan Area Networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs)-Amendment 1: MAC Sublayer; IEEE Std[END_REF].

A. TSCH Network

In a TSCH network, the medium access is time-slotted and several transmissions are done on different channels in the same time slot. More precisely, transmissions are scheduled in cells, where a cell is defined by its channel offset and its time slot offset. There are two types of cells: shared cells where any node having a message to transmit is allowed to do so, and dedicated cells, where only the transmitter defined in the schedule is allowed to. The choice of a wireless TSCH network helps to meet Assumptions 1-3 because the mapping between logical channels and physical ones changes at each time slot. Thus, even if a message is retransmitted in the next slot and on the same logical channel as previously, it will be transmitted on a different physical channel.

The schedule of transmissions is periodic and conflicts in dedicated cells are avoided. In addition, nodes know from the schedule in which slots they are allowed to transmit or to receive. They sleep in any other slot in order to save energy.

B. Scheduling Function

The scheduling algorithm, which is assumed to be centralized in this paper, works per flow: it allocates the cells needed to transmit a message from the flow origin to the sink. More precisely, it proceeds hop by hop, starting from the flow origin and allocating to each visited node the number of cells needed to receive the message from its child and then the number of cells needed to transmit this message to its parent. Since the scheduler does not know a priori which message transmission will be successful, it has to take into account the worst case where a message is received by the next hop after the maximum number of transmissions for this link and this flow. Hence, for each message, the scheduler allocates to each visited link a number of cells corresponding to the maximum number of transmissions on that link for the flow in question.

However, this does not mean that each message is transmitted a maximum number of times. In fact, as soon as the sender has received the acknowledgment of any message msg, it stops retransmitting msg and may use the slot foreseen for a retransmission of msg for the transmission of another message, if it has one in its T ransmit queue.

Any sensor node first transmits the message in its T ransmit queue that has the highest flow priority, as the primary criterion and the smallest timestamp within a same flow, as the secondary criterion. This assumes that messages are timestamped when they are generated by their origin node.

The Load-based scheduler is selected because of its simplicity combined with its very good performances [START_REF] Brun-Laguna | Optimized scheduling algorithm for time-critical industrial IoT[END_REF]. This scheduler schedules first the flow originating from the most loaded node. The load of a node is computed as the number of cells needed to transmit its own flows, plus the number of cells needed to receive and transmit the flows originating from its descendants.

C. Computation of Key Performance Indicators

In this paper, we consider three Key Performance Indicators (KPIs) that matter for Industry 4.0 and the IoT. We now show how to compute them for a TSCH network and a scheduling function defined in Sections IV-A and IV-B, respectively. These three KPIs are:

• The maximum end-to-end latency L is the maximum time elapsed between data generation by a sensor node and its delivery to the sink. To compute this value within the framework defined in Section IV-B, we make an additional assumption: Assumption 4. The maximum number of message transmissions on a link, denoted as M axT rans, a parameter of the MAC TSCH protocol, is dynamically tuned according to the value computed by M F air or M Opt.

With Assumption 4, the maximum end-to-end latency [START_REF] Khoufi | Scheduling transmissions with latency constraints in an IEEE 802.15.4e TSCH network[END_REF] is obtained when the last slot assigned to the node considered has just elapsed and then only the last transmission of the message is successful. This gives:

(Slotf rameSize -1 + U sedSlots) × SlotDuration, (6)
where U sedSlots is the number of slots used by the schedule for data gathering. Hence, the smallest maximum end-to-end latency that can be achieved is obtained by an optimal schedule, which uses M inSize the minimum number of slots for data gathering and for a slotframe duration equal to this number of slots. This smallest maximum latency is equal to

(2 * M inSize -1) × SlotDuration. (7)
• The end-to-end reliability R provided by the network. It is evaluated by the ratio of the total number of user-data messages sent by the sensor nodes over the total number of user-data messages delivered to the sink. • Network lifetime T is defined as the time the first node runs out of battery. Network lifetime can be expressed as:

M in N ∈N odes Initial Energy(N ) × SF Duration Average Energy Consumption(N ) , (8)
where Initial Energy(N ) denotes the initial energy of node N , Average Energy Consumption(N ) is the average energy consumption of N per slotframe, and SF Duration is the slotframe duration. To evaluate the network lifetime, defined as the time up to first battery depletion of the busiest node, we use the parameters whose values are given in Table II. To summarize, the IoT network has to guarantee that at least R percent of the messages generated by sensor nodes are delivered to the sink with a latency ≤ L, whereas the network lifetime is at least equal to T .

D. Generalization of the Theoretical Bound on the Maximum Latency

We now compute a theoretical bound on the maximum latency when T XCell f (N i ) < M axT rans, where T XCell f (N i ) denotes the number of TX cells assigned to flow f on node N i .

Let f be the flow whose message m has the maximum end-to-end latency. Let N k be the source node of f which is k hops away from the sink. Flow f visits successively N k , N k-1 , • • • N 1 and then the sink. We adopt an additional assumption: on any visited node, m is never delayed by another flow. The worst case occurs when on N k message m is generated just after the last slot assigned to N k . Hence, N k has to wait for the next slotframe to transmit m. In addition, on any node, only the last transmission (i.e., the M axT rans th transmission) is received in the worst case; the previous ones are lost. According to the framework defined in Section IV-B, when any node N i receives a message of flow f in a slotframe, it has T XCell f (N i ) cells to transmit it to its parent in the current slotframe. In each slotframe, any node N i has g T XCell g (N i ) opportunities to transmit a message to its parent, where g is a flow visiting N i . Hence, we get the following formula:

M axLatency(f ) ≤ M axT rans T XCell f (N k ) + k-1 h=1 M axT rans -T XCell f (N h ) g T XCellg(N h ) * Slotf rameSize + SlotU sed * SlotDuration. ( 9
)
If only Depth, the routing tree depth, and M inT XCell, the minimum number of TX cells per pair (sensor node, flow), are known, the bound becomes, taking into account that each sensor node generates its own flow:

M axLatency ≤ M axT rans M inT XCell + k-1 h=1 M axT rans -M inT XCell M inT XCell * (Depth -h + 1) * Slotf rameSize + SlotU sed * SlotDuration. ( 10
)
Notice that Equations ( 9) and ( 10) generalize Equation ( 6), which is valid only when M inT XCell ≥ M axT rans.

V. PERFORMANCE RESULTS FOR A TOY EXAMPLE

We first consider a toy example of a wireless TSCH network comprising a sink and seven sensor nodes. Each sensor node generates an application message of 27 bytes every 10 seconds. The slot duration is assumed to be 7.25 ms. The routing tree is depicted in Figure 3, where node A denotes the sink. The value associated with each link j gives P j the probability of successful receipt of a single transmission over that link. We notice that links have heterogeneous qualities, ranging from 0.5 to 0.9. For each of the seven flows generated by a sensor node, we compute the maximum number of transmissions per link for any message of this flow. All the flows, except that generated by B, are multi-hop, which is six flows. In this example, we assume that Assumption 4 is met: M axT rans is dynamically tuned according to the value computed by M F air or M opt. Tables III to VII compare the values obtained with M F air and M Opt, when the targeted end-to-end reliability ranges from 0.9 to 0.99999. These tables show that, whatever the targeted reliability, and as expected:

• The maximum number of transmissions per message over a link increases, when the link quality decreases.

• Both methods provide the same maximum number of transmissions for all single-hop flows.

• The total number of transmissions per message of any given multi-hop flow obtained by M Opt is always less than or equal to that obtained by M F air. For instance, for R = 0.9 (see Table III), we observe a gain on the total number of transmissions per message and per flow, which is equal to 1 for the 2-hop flows (i.e., flows originating from C and E), and for the 3-hop flow originating from D. This gain becomes 2 for the 4-hop flow originating from G and 3 for the 4-hop flow originating from H. To summarize the results obtained for the six multi-hop flows considered, we observe five improvements for R = 0.9, four improvements for R = 0.99, two improvements for R = 0.999, four improvements for R = 0.9999 and five improvements for R = 0.99999, leading to a total of 20 improvements over the 30 cases tested. • Even if the total number of transmissions is the same for both methods, the distribution over the links may differ as exemplified in Table VII by the flow originating from D, where M Opt gets an end-to-end reliability of 0.99922, whereas M F air gets a slightly less value 0.99921. Hence, M Opt provides the smallest total number of transmissions per flow and, if equal with M F air, M Opt provides the highest end-to-end reliability.

• With M F air, two links having the same link quality always have the same maximum number of transmissions for the same flow, as exemplified in all tables by the flow originating from H, where the links HD and CB have the same quality. However, this is not always the case with M Opt; see, for instance, this flow in Table IV, where the maximum transmission number for link HD is 9, whereas it is 8 for link CB. Since the nodes close to the sink usually have a larger load, decreasing their load improves the network performances. Notice, however, that the maximum number of transmissions on a given link depends on the flow. For instance, the maximum number of transmissions on Link B → A is equal to 11 for all flows, except the flow originating at B, where it is 10, for a targeted R = 0.99999. • The number of iterations of M Opt never exceeds h + 1 in all the cases evaluated.

B. Load-Based Scheduling

Let us see how these transmissions are scheduled, assuming a per-flow approach and more precisely the selection of the Load-based scheduler, which schedules first the flow originating from the most loaded node. We recall that the load of a node is computed as the number of cells needed to transmit its own flows, plus the number of cells needed to receive and transmit the flows originating from its descendants. Figures 5 and6 depict the Load-based schedule of the seven flows generated by sensor nodes with M F air and M Opt, respectively, assuming a targeted end-to-end reliability of 0.9. In both cases, the Load-based scheduler schedules the flows in the same order, starting with the most loaded node B, the scheduling order is B, C, D, E, H, F, G, although Load(B) = 52 cells with M F air and only 46 with M Opt. The two resulting schedules are optimal in terms of slots needed because node B, the most loaded node, is kept busy in all slots of both schedules. However, M F air requires exactly 52 slots to schedule the 72 transmissions, (see Figure 5), whereas M Opt requires only 46 slots to schedule the 64 transmissions, (see Figure 6). In this simple configuration with seven flows, M Opt allows for saving eight transmissions, which represents an improvement of 11% in the number of transmissions to schedule. In addition, M Opt allows for saving six slots, which reduces by 11.5% the number of slots used. In the Load-based schedule obtained with M F air and depicted in Figure 5, we have M inSize = 52 slots. Hence, for a slot duration of 7.25 ms, the smallest maximum latency that can be achieved with M F air is equal to (52 + 51) * 7.25 = 0.7465 s. The average energy consumption per slotframe of node B, the greatest loaded node, is equal to: (22 × T XCharge + 30 × RXCharge)/SF Duration, where SF Duration denotes the slotframe duration. With an initial energy of 2821.5 mAh, the default slotframe size of 101 slots and a slot duration of 7.25 ms, this node will have a lifetime of 39 days and a maximum latency of (101 -1 + 52) * 7.25 * 10 -3 = 1.102 s. To meet a lifetime of one year, the slotframe size should be greater than or equal to 933 slots, with a maximum latency of (933 -1 + 52) * 7.25 * 10 -3 = 7.0905 s.

With the Load-based schedule obtained with M Opt and depicted in Figure 6, we have M inSize = 46 slots. Hence, for a slot duration of 7.25 ms, the smallest maximum latency that can be achieved with M Opt is equal to (46+45) * 7.25 = 0.65975 s, which represents an improvement of 13.67%. It becomes 1.0585 s for the default slotframe size of 101 slots. The average energy consumption of B per slotframe becomes (20 × T XCharge + 26 × RXCharge)/SF Duration, leading to a network lifetime of 44 days for the default slotframe size of 101 slots and a maximum end-to-end latency of (101 -1 + 46) * 7.25 = 1.0585 s. To meet a lifetime of one year, the slotframe size should be greater than or equal to 830 slots, with a maximum latency of (830 -1 + 46) * 7.25 * 10 -3 = 6.34375 s, which represents an improvement of 12.38% with regard to M F air. For a slotframe size of 933 slots, M Opt would provide a maximum latency of 7.0905 s, a decrease of 11.77% with regard to M F air and a network lifetime of 410 days instead of 365 for M F air, an increase of 12.40%.

Table VIII points out the trade-off between the maximum end-to-end latency and network lifetime by listing the results obtained by M F air and M Opt for different slotframe sizes: 52, 101 and 933 slots. To increase the network lifetime by increasing the slotframe size, provided that the application still generates the same number of messages per slotframe, leads to an increase in maximum latency. M Opt provides a shorter maximum end-to-end latency because of a smaller schedule size (i.e., smaller number of slots used).

VI. PERFORMANCE RESULTS OF A TSCH NETWORK WITH 50 NODES

For the performance evaluation of a TSCH network with 50 nodes, we use the 6TiSCH simulator [START_REF] Municio | Simulating 6TiSCH networks[END_REF], which has been designed for a fast prototyping. In [START_REF] Gaillard | KPI-aware scheduling algorithm for multi-flow in multi-hop IoT networks[END_REF], network performances are evaluated on two specific applications running on a same network. In this particular configuration, randomly deployed sensors are only in charge of generating messages that they forward to a close relay, whereas relays are deployed according to a triangular grid. Since a more generic configuration is representative of much more applications, we focus on a generic data gathering application running on random network topologies.

A. Simulation Parameters

The network topology is a random topology such that any mote has at least three neighbors (i.e., three motes with which P DR ≥ 0.5). For each wireless link, the PDR value is computed according to the Pister-Hack model [START_REF] Le | Energy-Aware Routing in Wireless Sensor Networks with Adaptive Energy-Slope Control[END_REF]. The 6TiSCH protocol stack is used with RPL as the routing protocol with the ET X metric and the Load-based scheduler as the scheduling function. RPL, M F air and M Opt use the PDR values computed for the wireless links considered. For each wireless link i, RPL deduces ET X(i) from P DR(i). The simulation parameters used to evaluate the KPIs are those given in Table IX. The deepest routing tree observed in the simulations is 7-hop deep, the shallowest is 4-hop deep, with a median of 5-hop. Notice that, in the simulations done with the 6TiSCH stack, M axT rans, the maximum number of transmissions of any message on any link is fixed, as in the standardized MAC TSCH protocol. In the 6TiSCH simulations, its value is set to 6. If after six transmissions the acknowledgment is not received, the message is discarded. This behavior has a strong impact on the latency. Since Assumption 4 is not met, the theoretical bound for the maximum latency given in Equation ( 6) is no longer valid, we use the new theoretical bound given in Section IV-D.

A legitimate question is why a schedule provides a number of Transmission cells (TX) for any given flow greater than M axT rans, since a message that has not been acknowledged after M axT rans transmissions is discarded. The justification is provided by the decrease in the average end-to-end latency and the maximum end-to-end latency as we will see in Section VI-C. This decrease is due to a greater number of opportunities to transmit.

B. End-to-End Delivery Rate

Simulation results about the average end-to-end delivery rate are depicted in Figure 7. As expected, the end-to-end reliability is better with M Opt than with M F air because M Opt maximizes the end-to-end reliability provided for a minimum total number of transmissions per message.

C. End-to-End Latency

Simulation results about the average end-to-end latency are depicted in Figure 8. As M F air tends to compute a greater number of transmissions than M Opt, the schedule for M F air includes a greater number of cells in a slotframe whose size is kept identical for M Opt and M F air. The more cells, the more chance to send or forward. Since an application packet is generated at a random time point in the slotframe, the more transmission (TX) cells the node has, and the more chance to send the packet immediately. This is why the average end-to-end latency is shorter with M F air.

Figure 9 shows the percentage of messages delivered in a single slotframe. It is smaller with M Opt than with M F air due to the greater number of TX cells granted by M F air. Table X compares the theoretical bound for the maximum end-to-end latency obtained by Equation ( 10) with the simulation results, for different values of the targeted end-to-end reliability and a given random topology. The maximum end-to-end latency obtained by simulation decreases when the targeted end-to-end reliability increases: a greater number of TX cells assigned to nodes give them more opportunities to transmit in a slotframe. With the theoretical bound, the decrease is obtained when the number of TX Cells assigned to a node increases to reach the targeted end-to-end reliability. Whatever the targeted reliability, the bound given by Equation ( 10) and the simulation results are not close. The theoretical bound could be refined to take more information into account. TABLE X: Comparison of the theoretical maximum end-to-end latency and the simulation results for M F air and M Opt, taken from particular simulations having the same routing topology. Table X also provides the end-to-end reliability. As expected, M Opt provides an end-to-end reliability better than M F air. However, for a targeted end-to-end reliability ≥0.999, M F air fails to achieve the requested reliability, when M axT rans is left fixed to 6 instead of being dynamically tuned according to the values computed by M F air or M Opt.

D. Duty Cycle

With regard to network lifetime and energy consumption, we consider the busiest node excluding the root (sink) node, since it is supposed to be mains-powered. This busiest node determines the network lifetime. The duty cycle on this busiest node is computed as:

Duty Cycle = number of slots used on the busiest node schedule size in slots .

Note that Equation ( 11) is meant for the following comparison, which does not represent actual radio duty cycle. In TSCH, a device does not turn on its radio all the time even during an active slot. As a consequence, for high targeted reliabilities (i.e., ≥0.999), M F air and M opt give close end-to-end latencies at a greater energy cost for M F air.

E. Impact of M axT rans, a TSCH Parameter

We now study the impact of M axT rans the maximum number of transmissions of a message in TSCH, whose default value is 6. We set M axT rans to the value of 20, which is greater than the maximum number of transmissions on each link computed by M F air or M Opt. We run the same simulations as previously and evaluate the impact on the end-to-end reliability and the end-to-end latency.

As expected, the end-to-end reliability depicted in Figure 14 is increased both with M Opt and M F air, when the maximum number of transmissions per message in TSCH is set to 20. It is very close to 100%, for all the values of the targeted reliability tested. Notice, however, that increasing M axT rans may lead to a network overload resulting in violations of the maximum acceptable latency L. To avoid that, messages whose lifetime is greater than or equal to L should not be transmitted and should be discarded. The consequence of increasing M axT rans to 20 is an increase in the average latency for both M F air and M Opt, as shown in Figure 15. The shortest average latency is still provided by M F air. However, the gap decreases for high targeted end-to-end reliabilities (i.e., ≥0.999). Using a value of M axT rans greater than the value required by M F air or M Opt on a given link may result in an increase in end-to-end latency and energy consumption for a very strongly limited gain in end-to-end reliability.

VII. COMPARISON WITH Kausa

Since Kausa [START_REF] Gaillard | KPI-aware scheduling algorithm for multi-flow in multi-hop IoT networks[END_REF] is a well-known centralized scheduler that takes into account the unreliability of wireless links and adopts a per-flow approach to meet KPIs, we now compare M Opt to Kausa when run in a 6TiSCH network.

A. Our Kausa Implementation in the 6TiSCH Simulator

In the 6TiSCH simulator, as in any 6TiSCH implementation compliant with the standard, routing is done by the RPL protocol with the ETX metric. We simulated Kausa on the 6TiSCH simulator and ran it with the generic configuration defined in Section VI-A. We recall that the value of M axT rans is fixed to 6. In these conditions, the main differences between Kausa and our approach are:

• Kausa selects first the flow requesting the highest end-to-end reliability, then the shortest end-to-end latency and finally the flow originating from the farthest node of the sink. Our approach selects the flow originating from the most loaded sensor node (i.e., the sensor node needing the largest number of Tx+Rx cells). • For any flow f , Kausa starts by assigning cells to the most loaded node visited by f . Then, Kausa goes backward to the source of f . Finally, Kausa goes upward from the most loaded node to the sink. In our approach, cells are assigned to nodes visited by f in a cascading way from the source of f up to the sink. It follows that our approach is easier to implement. • For any flow f , Kausa minimizes the number of retransmissions on the most loaded node, whereas we minimize the total number of retransmissions on the path of f . Notice that we implement an optimization of Kausa for 6TiSCH, enabling any node to use its next Tx cell to transmit any message to its parent, as done in our approach. This is not true in the published version of Kausa, where any node N is not allowed to use cells assigned to a flow f for another flow f visiting N .

B. End-to-End Latency

Figure 16 depicts the average end-to-end latency obtained by M Opt and Kausa. They both provide close values. However, M Opt provides a much smaller variance of the average end-to-end latency than Kausa, making it more predictable, even for high targeted reliabilities.

The same conclusion applies to the maximum end-to-end latency depicted in Figure 17. The predictability of performance is a property sought by industrial applications.

C. End-to-End Reliability

With regard to the end-to-end PDR, we observe in Figure 18 that both M Opt and Kausa ensure a PDR greater than the targeted one when it belongs to the interval [0.9, 0.999]. For greater values, the PDR is not met because the value of M axT rans = 6 is too small to reach the targeted end-to-end reliability. In addition, M Opt tends to provide a greater median value than Kausa.

D. Duty Cycle

Since the energy consumption can be deduced from the duty cycle of the busiest node, we compare the number of cells scheduled at the busiest node by Kausa and M Opt, as depicted in Figure 19. Both provide close values for a targeted end-to-end reliability less than or equal to 0.999. For a higher reliability, Kausa provides a smaller number of cells due to a number of transmissions scheduled per message less than or equal to M axT rans, whereas M Opt may schedule a larger number, explaining this result.

E. Schedule Size

The schedule size, illustrated in Figure 20, is a little greater with M Opt than with Kausa. As a consequence, a node has fewer opportunities to transmit with Kausa than with M Opt, leading to a higher and less predictable end-to-end latency.

VIII. CONCLUSION

TSCH is a very promising technology for the IoT. It is now necessary to evaluate the performances it can provide to IoT applications. These performances are evaluated by means of three KPIs: maximum end-to-end latency L, end-to-end reliability R and network lifetime T . This IoT network has to guarantee that at least R% of messages generated by sensors are delivered to the sink with a latency less than or equal to L, while the network lifetime is at least T . In this paper, we have proposed two methods M F air and M Opt to achieve a targeted end-to-end reliability taking into account the unreliability of wireless links. The trade-offs between end-to-end latency, network lifetime and end-to-end reliability have been pointed out. In addition, we have shown that minimizing the total number of transmissions of a message to reach the sink with M Opt saves 12% of network lifetime in a small network of eight nodes, assuming a Load-based schedule of flows. As expected, M Opt provides a better end-to-end reliability and a longer network lifetime than M F air. However, the average end-to-end latency provided by M F air is smaller. These results scale up to a 50-node network representative of real deployments, as shown by simulation results obtained with the 6TiSCH simulator. However, using a fixed maximum number of transmissions M axT rans equal to the default value of the TSCH protocol, instead of using the value computed by M F air or M Opt for the link and the flow considered, may lead to a violation of the targeted end-to-end reliability: messages that have not been acknowledged after M axT rans transmissions are discarded. Compared to Kausa, a KPI-aware, state-of-the-art scheduler, our approach is simpler to implement and ensures more predictable end-to-end performances, which is an essential property for industrial applications.

Fig. 1 :

 1 Fig. 1: Maximum number of transmissions over a link visited by a 4-hop flow, computed by M F air.

Fig. 2 :

 2 Fig. 2: Expected number of transmissions versus M F air Maximum number of transmissions over a link.

Fig. 3 :

 3 Fig. 3: A routing tree with the PDR of each link used by flows.

Fig. 4 :

 4 Fig. 4: Total number of transmissions for a flow message.

Fig. 5 :

 5 Fig. 5: Load-based schedule with M F air.

Fig. 6 :

 6 Fig. 6: Load-based schedule with M Opt.

Fig. 7 :

 7 Fig. 7: End-to-end delivery rate obtained with M F air and M Opt.

Fig. 8 :

 8 Fig. 8: Average end-to-end latency obtained with M F air and M Opt.

Fig. 9 :

 9 Fig. 9: Percentage of packets delivered in one slotframe with M F air and M Opt.

Figure 10

 10 Figure10depicts the cumulative distribution function of the end-to-end latency for M F air and M Opt. With M F air, 98% of messages reach the sink in one slotframe that is with an end-to-end latency ≤7 s. The gap between M F air and M Opt is smaller than 1%.

Fig. 10 :

 10 Fig. 10: Cumulative distribution function of the end-to-end latency with M F air and M Opt.

Fig. 11 :

 11 Fig. 11: Maximum end-to-end latency obtained by simulation with M F air and M Opt.

Figure 12

 12 Figure12depicts the schedule size expressed as the number of slots used in the schedule of M F air and M Opt. Unsurprisingly, the schedule size increases with the targeted end-to-end reliability, due to a great number of transmissions on each link to reach the targeted end-to-end reliability. Whatever the targeted reliability, the schedule size is always shorter with M Opt than with M F air, as expected.

Fig. 12 :

 12 Fig. 12: Maximum slot used by M F air and M Opt.

Figure 13 Fig. 13 :

 1313 Figure13depicts the number of cells assigned to the busiest node in one simulation run for each targeted end-to-end reliability.

Fig. 14 :

 14 Fig. 14: End-to-end delivery rate obtained with M F air and M Opt for M axT rans = 20 transmissions.

Fig. 15 :

 15 Fig. 15: Average end-to-end latency obtained with M F air and M Opt for MaxTrans = 20 transmissions.

Fig. 16 :

 16 Fig. 16: Average end-to-end latency obtained with M Opt and Kausa.

Fig. 17

 17 Fig. 17: Maximum end-to-end latency obtained with M Opt and Kausa.

  Fig. 17: Maximum end-to-end latency obtained with M Opt and Kausa.

Fig. 18 :

 18 Fig. 18: End-to-end delivery rate obtained with M Opt and Kausa.

Fig. 19 :

 19 Fig. 19: Number of cells used at the busiest node with M Opt and Kausa.

Fig. 20 :

 20 Fig. 20: Schedule size obtained with M Opt and Kausa.

TABLE II :

 II Parameters used for network lifetime computation.

	Parameter	Value
	Initial energy of node powered by 2 Energizers L-91 AA batteries 2821.5 mAh
	Transmit a data frame & receive its acknowledgment	54.5 µC
	Receive a data frame & transmit its acknowledgment	32.6 µC
	IdleListen	6.4 µC
	Sleep	0 µC

TABLE III :

 III Comparison of M F air and M Opt for a targeted end-to-end reliability R=0.9 on 7 flows.

				Maximum number of transmissions for targeted R=0.99		Total number of	End-to-end
	Flow Hop	P=0.7		P=0.5	P=0.8		P=0.6	P=0.9		transmissions per msg	reliability
			Fair	Opt.	Fair Opt.	Fair Opt.	Fair	Opt.	Fair Opt.	Fair	Opt.	Fair	Opt.
	B	1	4	4									4	4	0.9919	0.9919
	C	2	5	5	8	8							13	13	0.993673 0.993673
	E	2	5	5					6	6			11	11	0.99348	0.99348
	D	3	5	5	9	8	4	4					18	17	0.99402	0.99208
	F	3	5	5	5				7	6			17	16	0.9935	0.99106
	G	4	5	5	9	8	4	4			3	3	21	20	0.99303	0.99109
	H	4	5	5	9	9 8	3	3					27	26	0.99208	0.99014

TABLE IV :

 IV Comparison of M F air and M Opt for a targeted end-to-end reliability R=0.99 on 7 flows.

				Maximum number of transmissions for targeted R=0.999		Total number of	End-to-end
	Flow Hop	P=0.7	P=0.5	P=0.8		P=0.6	P=0.9		transmissions per msg	reliability
			Fair	Opt.	Fair Opt.	Fair Opt.	Fair	Opt.	Fair Opt.	Fair	Opt.	Fair	Opt.
	B	1	6	6									6	6	0.99927	0.99927
	C	2	7	7	11	11							18	18	0.99929	0.99929
	E	2	7	7					9	8			16	15	0.99951	0.99912
	D	3	7	7	12	11	5	6					24	24	0.99921	0.999229
	F	3	7	7					9	9			23	23	0.99930	0.99930
	G	4	7	8	12	11	6	6			4	4	29	28	0.99937	0.99922
	H	4	7	7	12	12	6	6					37	37	0.999229 0.999229

TABLE V :

 V Comparison of M F air and M Opt for a targeted end-to-end reliability R=0.999 on 7 flows.

				Maximum number of transmissions for targeted R=0.9999		Total number of	End-to-end
	Flow Hop	P=0.7	P=0.5	P=0.8		P=0.6	P=0.9		transmissions per msg	reliability
			Fair	Opt.	Fair Opt.	Fair Opt.	Fair Opt.	Fair Opt.	Fair	Opt.	Fair	Opt.
	B	1	8	8									8	8	0.999934	0.999934
	C	2	9	9	15	15							24	24	0.9999498	0.9999498
	E	2	9	9					11	11			20	20	0.99993837 0.99993837
	D	3	9	9	15	14	7	7					31	30	0.999937	0.999918
	F	3	9	9					12	11			30	29	0.99994386	0.999906
	G	4	9	9	16	15	7	7			5	5	37	36	0.999942	0.999927
	H	4	9	9	16	15	7	7					48	46	0.999937	0.999906

TABLE VI :

 VI Comparison of M F air and M Opt for a targeted end-to-end reliability R=0.9999 on 7 flows.

				Maximum number of transmissions for targeted R=0.99999		Total number of	End-to-end
	Flow Hop	P=0.7	P=0.5	P=0.8		P=0.6	P=0.9		transmissions per msg	reliability
			Fair	Opt.	Fair Opt.	Fair Opt.	Fair Opt.	Fair Opt.	Fair	Opt.	Fair	Opt.
	B	1	10	10									10	10	0.9999941	0.9999941
	C	2	11	11	18	17							29	28	0.99999441	0.9999906
	E	2	11	11					14	13			25	24	0.99999554 0.99999152
	D	3	11	11	19	18	8	8					38	37	0.99999376 0.99999185
	F	3	11	11					14	14			36	36	0.99999377 0.99999377
	G	4	11	11	19	18	9	9			6	6	45	44	0.9999948	0.9999929
	H	4	11	11	19	18	9	9					58	56	0.9999939	0.9999909

TABLE VII

 VII

: Comparison of M F air and M Opt for a targeted end-to-end reliability R=0.99999 on 7 flows.

TABLE VIII :

 VIII The trade-off of end-to-end latency versus network lifetime for M F air and M Opt.

			M F air			M Opt		Relative Improvement
		Slotf rame(slots)	Slotf rame(slots)	Slotf rame(slots)
		52	101	933	52	101	933	52	101	933
	Max. latency (s)	0.74675 1.102	7.134	0.70325 1.0585 7.0905	5.82%	3.94%	0.61%
	Lifetime (days)	20.35	39.54 365.28	22.87	44.42	410.41 10.98% 12.35% 12.35%

TABLE IX :

 IX Simulation parameters.

		Parameter	Value
		Number of nodes	50
	Config.	Number of Channels Topology	16 random
		Link reliability	computed
		Slot duration	10 ms
		Slotframe size	700 slots
	TSCH	Secure join Keep-alive (L2)	disabled disabled
		Transmit queue size	10 packets
		Max of retransmissions	5 (i.e., max of 6 transmissions)
	Routing	RPL a stable routing topology	with ETX metric where DAO is disabled after 60 min
	Scheduling	Scheduling function	Load-based scheduler
	Application	is run & measures made packet generation interval on each sensor node	during the next 60 min in [57 s, 63 s]
	Simulation	100 runs per pair (algorithm, targeted reliability)	algorithm ∈ {M Opt, M F air} targeted reliability ∈ {0.9, 0.99, 0.999, 0.9999}

Table

  XI gives the duty cycle on the busiest node with M F air and M Opt. This gives an insight on network lifetime which is determined by the lifetime of the busiest node.

TABLE XI :

 XI Comparison of the duty cycle of the busiest node for M F air and M Opt.

			Targeted End-to-End Reliability
			0.9	0.99	0.999	0.9999
	Schedule size (slots)	M F air M Opt	96 84	154 134	199 190	249 246
	Cells assigned to busiest node	M F air M Opt	77 63	103 87	127 122	159 149
	Duty cycle of the busiest node	M F air M Opt	11% 9%	14.71% 12.42%	18.14% 17.42%	22.71% 21.28%
	Relative gain in duty cycle	18.18%	15.53%	3.93%	6.29%

ACKNOWLEDGMENTS

The authors acknowledge Keoma Brun-Laguna and Thomas Watteyne for their valuable feedback on this work.


David Chapelle
email: david.chapelle@univ-fcomte.fr

Liping Feng

Philippe Nardin
email: cphilippe.nardin@univ-fcomte.fr

Jean-Yves Rauch

Assessment of the gas permeation through thin coated polymeric membranes; improvement of the gas barrier ability for hydrogen storage

Keywords: Hydrogen barrier, gas permeation, hydrogen storage

We investigate and simulate the permeation behavior of PET membranes on which thin coatings are deposited. Depending on the parameters of deposition and on the thin coating thickness, we assume this alteration could make it possible to decrease by one order of magnitude the permeation coefficient. Some specific developments have been necessary, all the more not only a decrease of permeation is expected but also the mechanical strength of the thin coating during severe mechanical loadings. We consequently design devices dedicated to the permeation test but also to the bulge and blister tests which permit to check the mechanical properties of the film and its adhesion on the PET surface. This paper focuses on the permeation test.

Introduction

The emerging of a hydrogen energy world requires developing new materials and new technologies (but also standards) whether it be for hydrogen production, storage or utilization [1]. When hydrogen storage or utilization is accounted, one of the main challenges to overcome is to design materials which prevent structure from any leakage or for which the kinetics of the leak could be controlled. Thus, for high pressure vessel, two types of liner, it means barrier envelop, are commonly used, a metallic liner or a polymeric liner. The latter one allows the structure to fulfill the standards requirements for cycling loading while presenting a 10 times permeation increase compared to a metallic liner.

Poly (ethylene terephthalate) (PET) is a very valuable polymer because PET is lightweight, optically transparent, unbreakable and also recyclable [2,3]. PET materials can be blown into containers and bottles used as the packaging of food and water. However, the application of PET containers to some products like gas or water involves significant difficulties because of the insufficient gas barrier properties of PET. Thus, developing new films or processes to improve gas barrier properties of PET are highly demanded in the market [2,4].

Previous studies focused mainly on the improvement of barrier properties of PET applications in food and drink packaging industry. Therefore, many coatings were investigated, such as AlOx [5], SiOx [6], AlOxNy [7] and carbon films [8], because of their excellent oxygen and water vapour barrier performance. Presently, PET can be formed into pipelines used as the conveyance of high pressure gas or petroleum products. However, there are very few studies of the barrier properties of PET applications in high pressure hydrogen transportation. The microstructural and gas barrier properties of thin coatings deposited on polymer substrates are of great importance to the high pressure hydrogen transportation. Additionally, the process and surface treatment of polymers prior to coating are efficient ways of modifying the surface ability of PET to then produce a good deposit. In this study, metallic films are deposited on PET substrates by RF magnetron sputtering and evaporation. Pre-treatments of Ar plasma and Ar beam are adopted for RF magnetron sputtering and evaporation, respectively. Current work is focused on investigating the pressure hydrogen permeation behavior of metallic films prepared on PET by different processes.

Theory

Gas permeation through a membrane is a rather well known phenomenon which could be depicted in three stages. The first one refers to the gas penetration on the inlet side, the second is the matter transportation form one side to the other and for which the driving-force is the concentration gradient, the third one is the exit of gas on the outlet surface. The permeation test relates to the technics which allow quantifying the matter transportation. This can be fulfilled using easily accessible manometric method or less affordable, but more accurate, technics as mass spectroscopy. In literature, background on diffusion is well documented [9] and its field of application is large [10]. Fig. 1 introduce a schematic representation but also the characteristic curve of such an experiment. The following expression provides the gas volume crossing the plane membrane according to time while steady-state is reached, the permeability and the gas concentration at surface, respectively:

        - = D e t e DC t Q 6 ) ( 2 , ( 1
) DS P = , (2)
Sp C = .
(

) 3
Physical quantities are ( STP : Standard Pressure and Temperature) Q , the gas volume at time t (

) ( 3 STP cm ), D the diffusion coefficient ( 1 2 - s cm
), e the membrane thickness ( cm ), C the gas concentration at surface ( 3

3 ) ( - cm STP cm
), P the permeability (

1 1 1 3 ) ( - - - s cm bar STP cm
), S the gas solubility in the membrane (

3 1 3 ) ( - -cm bar STP cm
) and p the gas pressure ( bar ). The time-lag, defined as the intercept between the steady-state linear plot and the time axis, is expressed as:

D e L 6 2 = . ( 4
)

Experimental

As polymer substrates, 1 mm thick PET disc membranes with a 50 mm diameter are prepared (Fig 2 .a). Metallic thin films (Al, Ti and Cr) with thickness less than 300 nm are deposited on the PET substrates by RF magnetron sputtering and evaporation. PLASSYS MP500 system is used for RF magnetron sputtering and EVA 450 equipment is used for evaporation. The PET substrates are dipped in ethanol solution and cleaned using ultrasonic apparatus. After that, samples are dried to remove adsorption dust on the surface, and finally present mirror like surface on the metallic thin coating side (Fig 2 .b). The purity for metallic target is greater than 99.99%. The substrate-to-target distance is about 6.0 cm and 40 cm for the sputtering and evaporation deposition, respectively. Hydrogen permeation measurements were carried out using in-house developed permeation device (Fig. 3), having three permeation cells and allowing monitoring the inlet pressure from 1 to 10 bar by means of a Brooks 5866 pressure regulator. The hydrogen transport is assessed by pressure measurement using 0-250 mbar Baumer transducers.

Results and discussion

Al, Cr and Ti deposition

This section is dedicated to the comparison of the gas barrier potential of three different metallic thin coatings, i.e. Aluminum coating, Chromium coating and Titanium coating. The composition of the film is expected to significantly modify the behavior of the so-made composite membrane, regarding the gas flow. At the same time, evaporation and sputtering methods to deposit the thin films are performed for comparison and the influence of surface preparation with respectively Ar beam or Ar plasma pre-treatment is investigated. Table 1 gives the parameters used in order to carry out these pre-treatments or depositions. Table 1: Pre-treatment (PT) and deposition (D) parameters Before having permeation experiments on those samples, some observations with an optical microscope have been carried out. These reveal relevant discrepancies of the resulting thin film depending on the parameters and on the metal. Thus, results are clearly distinct according to the metal deposited: optical aspect of Ti and Cr films is far from Al film aspect. For Ti and Cr thin coatings, observations show a network of cracks. The worst results are obtained when the deposition is made using evaporation method, even worse when there's no pre-treatment. Fig. 4 illustrates these comments showing images of Ti and Cr thin coatings by evaporation method, with or without any pretreatment. At the opposite, on the Al thin coating never any failure has been observed. Visual aspect of the surface is clearly dependent on preparation process but no drastic defect has been evidenced during observations. Fig. 5 presents images of the Al thin coatings obtained on the PET substrate with evaporation method and no pretreatment, and with sputtering method and Ar plasma pretreatment. Obviously, such reports lead to predict a poor efficiency of Ti and Cr thin coatings whatever the deposition process is. Failures observed on those coatings involve easy ways for gas flow. This is confirmed by the permeation tests performed consecutively. At the opposite, regardless of the applied process to get Al thin coatings, permeation tests show homogeneous results with a fourfold reduction of the permeability in comparison with permeability of the PET membrane.

Al thickness effect

In accordance with previous results, we decided to focus on aluminum thin coating deposition using sputtering method. The following investigations aim to assess the effect of the Al thin coating thickness on the barrier efficiency. Thus, new samples have been prepared with parameters as detailed in Table 2 (pressure is 7×10 -3 mbar). The applied pretreatment is identical to the one used in the above section for sputtering, i.e. pressure is 7×10 -3 mbar, power is 150 W and process time is 120 s. For each set of samples, three permeation tests have been performed using the three available cells. The hydrogen inlet pressure is monitored and fixed at 4 bar. Fig. 6 plots the mean values of the gas quantity which passed through the composite membrane versus time. It is worth to immediately point out that the results for 150 nm thin coating should be consider with real caution. Pressure monitoring during this experiment is clearly defective and involves in our opinion an underestimate of the amount of gas which goes through the membrane. This justifies the choice made in Table 3 to give an estimation of the slope, which gives the gas flow trend, for these specimens (bold italic).

Except the check of the monitoring pressure for 150 nm thin coating, the previous option is motivated by results from the two other thin coating thickness experiments. Contrarily to our first hypothesis, the thickness increase of the thin coating leads to a decrease of the gas barrier efficiency. Thus, the assessed efficiency of a 75 nm Al thin coating is more than 3 times the efficiency of the single PET membrane, while the 100 nm Al thin coating is twice less efficient compared to the 75 nm Al film. The next investigations should help us to establish the relevance of such a conclusion by controlling the residual stresses in the thin coating, the amount of defect correlated to the previous measurements. Another controversial issue is the permeability mentioned in literature for PET membrane. In [START_REF] Massey | Permeability properties of Plastics and Elastomers[END_REF], at 25°C, permeability is equal to 39.4

1 2 1 3 ) ( - - - day m atm mm STP cm , i.e. 4.56×10 -9 1 1 1 3 ) ( - - - s cm bar STP cm
, and in [12], the given value at 50°C is 1.31 Barrer (10 -10

1 1 1 3 ) ( - - - s cm cmHg STP cm
), i.e. 9.96×10 -9

Conclusions

This paper investigates the permeation through polymeric membrane on which thin coating is deposited in order to increase the gas barrier efficiency. Ti, Cr and Al films have been tested in order to address their suitability as a gas barrier. This study reveals that only Al thin coating is acceptable with the deposition parameter range which was taken into account. In an unexpected way, the increase of the Al thin coating thickness seems to lead to a decrease of the barrier efficiency. Regarding at the initial goal, the decrease of the global composite permeability is far from one order of magnitude. Following investigations involve checking the above mentioned results but also estimating the durability of such a barrier when used on a structure subjected to severe environmental and mechanical loadings.

Figure 1 :

 1 Figure 1: Principle scheme (left) and characteristic curve (right) of the permeation phenomenon through a plane membrane.

Figure 2 :

 2 Figure 2: 1 mm thick PET disc membranes with a 50 mm diameter a), with metallic thin coating b)

Figure 3 :

 3 Figure 3: Permeation device with 3 parallel permeation cells (4 th is for swelling measurement)

Figure 4 :

 4 Figure 4: Optical observations of Ti and Cr thin coatings a) Ti evaporated without pretreatment, b) Ti evaporated with Ar beam pretreatment c) Cr evaporated without pretreatment, d) Cr evaporated with Ar beam pretreatment

Figure 5 :

 5 Figure 5: Optical observations of Al thin coatings a) Al evaporated without pretreatment, b) Al sputtered with Ar plasma pretreatment

Figure 6 :

 6 Figure 6: Permeation measurements on PET substrate with Al deposition (75, 100 and 150 nm)Mean hydrogen quantity (cm 3 (STP)) is plotted versus time (h).

Table 3 :

 3 Sample sets depending exposure time and estimated thickness Slope 10

Table 2 :

 2 Sample sets depending exposure time and measured thickness

		Set 1	Set 2	Set 3
	Intensity (A)	1.5	1	1.5
	Exposure time (s)	60	120	120
	Estimated Al thickness (nm)	< 75	100	150

Acknowledgement

This work is supported through 'Region Project' by Région Franche-Comté. A financial support has been brought for device development but also for a post-doctoral position.