Arnaud Grivet Sébert
email: arnaud.grivet.sebert@cea.fr

Jean-Philippe Poli
email: jean-philippe.poli@cea.fr

Fuzzy rule learning for material classification from imprecise data

Keywords: Fuzzy partitioning, clustering, fuzzy decision tree, fuzzy rules, imprecise data, explainable material classification

A complete method for classification of materials from imprecise chemical data is proposed. The method consists in a clustering method to find the suitable terms of the various linguistic variables and in a decision tree induction to learn rules for an explainable classification. Both methods are adaptations from classic methods to the case of imprecise data. Finally, results on simulated data are presented in the expectation of real data.

Introduction

Customs and ports security is a major issue in Europe. Indeed, many illegal or dangerous substances such as drugs, weapons, explosives pass through customs. Unfortunately, systematic container inspections are impossible in practice because of the cost and time that would be required. The volumes passing daily through the major European ports such as Rotterdam, Antwerp or Hamburg are indeed enormous: for example, 461.2 million tons of goods passed through the port of Rotterdam in 2016.

In this paper, we use tagged neutrons to obtain the chemical composition of a volume of the container. From this chemical composition, we want to determine the materials present in the container. In order to bring more credibility to the final software used by the customs officers, we will also provide a justification for this classification. Fuzzy rules allow to avoid the "black box" effect since customs officers have access to a real explanation of the classification made by the software, and close to natural language : "the container may contain drug (confidence degree : x) because the quantity of carbon is high, the quantity of nitrogen is low and the quantity of oxygen is medium" for instance.

The proportions are obtained by different treatments that are beyond our control. Thus, the input data are imprecise and are accompanied by a measure of this inaccuracy. Fuzzy logic thus seems appropriate for the exploitation of such data.

Given the time required and the authorizations needed to use a neutron generator, we will have a small learning dataset, even if all classes of relevant materials will obviously be represented. The idea is therefore to use fuzzy decision trees [START_REF] Chang | Fuzzy decision tree algorithms[END_REF], which have been applied successfully on various classification problems [START_REF] Akiyama | Application of fuzzy decision tree to analyze the attitude of citizens for wellness city development[END_REF][START_REF] Olaru | A complete fuzzy decision tree technique[END_REF]. The scarcity of training data and the intrinsic inaccuracy due to the preprocessing preclude conventional statistical learning approaches such as neural networks, SVM, etc. which also do not provide an explanation to users.

In this article, we adapt to imprecise data the classic two steps workflow consisting in using clustering methods to create relevant terms from data and then in building a decision tree to get fuzzy classification rules.

The paper is structured as follows: section 2 describes the context of the application that motivates this work. Then, section 3 describes the method to induce rules from imprecise data. Section 4 presents the results of the different experiments we conducted. Finally, section 5 draws the conclusions of this paper.

Application context

Neutron inspection for container digging

The H2020 project C-BORD (effective Container inspection at BORDer control points) aims at facilitating the digging of containers at borders by exploiting different technologies: e-noses, X-rays, photo-fission and tagged neutrons. The goal is to detect dangerous (explosives, nuclear materials, ...) or illicit (drugs, contraband, ...) substances.

In this paper, we focus on the classification of materials with tagged neutron inspection. As shown in figure 1a, a device produces a neutron beam to focus on a certain volume (called voxel) of the container. The neutrons interact with the nuclei of the atoms contained in the voxel, producing new particles that can be detected by the matrix sensors which are positioned on the side of the container. These particles are thus characteristic of the atoms encountered in the examined voxel.

The processing of the raw data is not the topic of this article but we quickly describe the principle in figure 1b. After different pretreatments, a global spectrum is obtained. In comparison with the characteristic spectra of each of the studied atoms, this spectrum is decomposed into individual spectra by a Bayesian process which makes it possible to deduce the chemical composition of the voxel, expressed in percentages. This process is based on simulation and we can easily get the mean and the standard deviation for each proportion in order to characterize the inaccuracy of the reconstruction. Figure 2 shows the result of these treatments for an exposure to ceramics, and in which the inaccuracy is represented by "box plots".

Our work consists in exploiting this information in order to recognize the materials contained in the voxel.

Previous work

The difficulty of recognizing materials from the chemical composition lies in several points : For these reasons, previous works proposed visual analytics methods to represent the content of the voxels. In [START_REF] Aupetit | Visual analytics to check marine containers in the eritr@c project[END_REF], the authors proposed a Voronoi diagram Fig. 3: Screenshots of the different visualizations introduced in [START_REF] Aupetit | Visual analytics to check marine containers in the eritr@c project[END_REF] to highlight the proximity, in terms of chemical composition, of the current voxel with voxels previously inspected and whose content is known (see figure 3). Thus, it is not a question of recognizing the materials present in the container but of displaying visually close and known containers in order to deduce the contents.

This approach has the advantage of not requiring learning or parameterization since it relies on the manual selection of a neighborhood. In figure 3, we can also see two classical representations that have been used in conjunction with this method. These are projections of the current voxel on two triangles: a triangle called "materials triangle" indicates the proximity of the voxel with metals, ceramics and organic materials, while a so-called "alert triangle" presents the ratios between carbon, nitrogen and oxygen. This last triangle makes it possible to distinguish between drugs and explosives. The main drawback of the visual analytics approach is that the operator must be able to interpret the different representations himself.

In practice, the mastering of these representations, particularly the Voronoi graph, can be difficult for operators who are not familiar with these visualization techniques. As part of the C-BORD project, we want to go further and propose a list of materials, and an explanation of the decision. It is to overcome these different difficulties that we want to use a fuzzy expert system.

Rule induction for classification

In order to effectively classify the materials while generating rules which are understandable by a human, we chose to use a fuzzy decision tree inspired by the one defined by C. Z. Janikow in [START_REF] Janikow | Fuzzy decision trees : issues and methods[END_REF]. Each node is split, by a feature which was not used yet, into N child-nodes corresponding to the associated fuzzy terms. The maximum depth of the tree is thus the number of available features if no pruning is performed. In our case, the features are the different chemical elements the system can detect.

The rule induction follows a classic 2 steps workflow but the different algorithms have been adapted to take into account data imprecision: firstly, the method extracts from data the various terms that will be involved in the decision tree with clustering methods. Then, the tree is inducted. Finally, rules are created and used in a fuzzy expert system to perform the classification of new materials.

Fuzzy partition learning

To create rules which will provide the end-user with an explanation of the material classification, we have to define terms which will enable the building of the tree and will then appear in the premises of the rules. Nevertheless, crisp terms would not represent the physical reality for which strict boundaries between different compounds are irrelevant. That is why fuzzy terms are used. Except for the extreme terms which are trapezoidal, we opted for classical triangular overlapping terms that form a strong partition of the definition domains of the stoichiometric percentage of each element, namely [0, 100]. Triangular-shaped terms are used because more complex shapes, like trapezoidal or pentagonal shapes, reduce the performance and even the accuracy in some cases.

The best methods to learn linguistic variables terms turned out to be clustering approaches. For example, using entropy-minimization-based methods gave poorer results, due to the difficulty to minimize the fuzzy entropy (see 4) which is not a convex function of the fuzzy sets parameters.

The basic idea is to cluster the data, feature by feature (chemical element), as if they were one-dimensional data, and build fuzzy terms over the resulting clusters. Once the clusters are built, the mode of a fuzzy triangle is simply set to the mean of its corresponding cluster ; the spread is then induced by the other terms' modes through the constraint of the strong partition.

We tested existing algorithms and adapted them to the fuzzy case by the use of dissimilarities between distributions able to take into account the whole distribution of the data and not only an aggregated value. Distances or dissimilarities have already been defined and used with imprecise or uncertain data. A distance consisting in the sum of the center Euclidian distance and the spread Euclidian distance of the imprecise data was used in [START_REF] Coppi | Fuzzy time arrays and dissimilarity measures for fuzzy time trajectories[END_REF] and [START_REF] Urso | Robust clustering of unprecise data[END_REF] but this implies a loss of the information provided by the whole distribution. Moreover, even though it might have been replaced by the deviation distance, the spread distance does not make a lot of sense in the case of normal distributions whose spreads are theoretically infinite, and in our case imposed by the domain boundaries. Gullo et al. [START_REF] Gullo | Clustering uncertain data via k-medoids[END_REF] proposed an uncertain dissimilarity which corresponds, in the univariate case, to compute the double integral of the Euclidian distance of each pair ((x, f 1 (x)), (x, f 2 (x))) of points of the two distributions. We defined a simpler dissimilarity, in order to improve the performance.

The , where a and b, elements of R ∪ {-∞, +∞}, are the bounds of the definition domain of the data, 0 and 100 in our case. Since each distribution is built in such a way that its integral on [0, 100] is equal to 1, we have :

b a max(f x (t), f y (t)) + b a min(f x (t), f y (t)) = b a f x (t) + b a f x (t) = 2 Thus, d(x, y) = 1 - b a min(fx(t),fy(t)) 2-b
a min(fx(t),fy(t)) . This formula is quite close and gives similar results to the simpler one :

d(x, y) = 1 - b a min(f x (t), f y (t)) (1)
Hence, we chose to use this second formula to define the dissimilarity between two imprecise data1 . Figure 4 shows the similarity between two distributions, drawn in red.

Fig. 4: Similarity between two imprecise data

We also tried to use the T-norm product instead of the min in the definition of the dissimilarity and it gave very similar results.

We then ran the k-medoids algorithm [START_REF] Kaufman | Clustering by means of medoids[END_REF] using this dissimilarity instead of the traditional Euclidian distance which would have only used the information given by the aggregated value of each distribution -generally the mean.

Fuzzy decision tree induction

To build the tree while taking into account the imprecision of the data, we represent these data by Gaussian probability distributions. Since the definition domain of the data (proportion in each chemical element) is bounded ([0, 100]), the Gaussian distributions are transformed so that their integral on this bounded domain equals 1 and that the distribution thus keeps its probabilistic sense on the interval [0, 100] beyond which the values, which are percentages, do not have any sense. To do so, each distribution is divided by its integral on [0, 100] :

f (t) = norm(t) * +∞ -∞ norm 100 0 norm = norm(t) 100 0
norm where norm is the probability density of the normal law.

We also tried a possibilistic approach, representing the imprecise data by triangular possibilistic distributions but the accuracy was lower, that is why we chose to focus on the probabilistic approach in this paper.

Once the fuzzy terms are learnt, we have to define how to compute the membership degrees of the imprecise examples, modeled by distributions, to each of these terms, which represent the nodes of the tree. We adapted integration techniques for uncertain data and crisp terms ( [START_REF] Duch | Uncertainty of data, fuzzy membership functions, and multilayer perceptrons[END_REF], [START_REF] Tsang | Decision trees for uncertain data[END_REF]) to our imprecise data and fuzzy terms -the membership degree is defined as the integral of the product of the density of the imprecise distribution with the membership function of the fuzzy term. If f is the density of the distribution representing the imprecision associated with the proportion of an element e in an example x, and µ v (t) the membership degree of the value t to the fuzzy term v, the membership degree of the imprecise example x to the fuzzy term v is :

μv (x) = 100 0 f (t)µ v (t)dt
For the sake of reading, we will write µ v (without tilde) in the following to refer to the membership degree of an imprecise example.

This integral, illustrated in figure 5 where the imprecision distribution is dilated by a factor 10 for a better visibility, takes into account the whole continuous spectrum of probable values for the proportion of e in x, and is basically the weighted average of the membership degrees of these probable values to the fuzzy term n.

Fig. 5: Integral of the product imprecision-fuzzy term

Given the membership degree of an imprecise example x to the fuzzy terms corresponding to each chemical element, we can define the membership degree of x to each node of the tree. To do so, we chose the product as a T-norm, because it gave better results than other T-norms, like the minimum. Hence, the membership degree of an example x to a node n is the product of the membership degrees of x to the fuzzy terms associated to n and to the ascendants of n. Thus, we have the recursive definition :

d n0 (x) = 1 d n (x) = d N (x) × µ v (x) (2)
where n 0 is the root of the tree, N is n's father node, v is the fuzzy term associated to the node n and µ v (x) is the membership degree of x to the fuzzy term v.

To select the next feature to use, we use the fuzzy entropy introduced by Peng et al. in [START_REF] Peng | Soft discretization to enhance the continuous decision tree induction[END_REF].

We consider the "fuzzy frequency" of a class c in a node n :

f r c/n = xi∈c d n (x i ) xi d n (x i ) (3)
where dn j (xi) where {n j , j ∈ [|1, F |]} is the set of the "siblings" nodes of n, including n.

{x i , i ∈ [|1, T |]}
The fuzzy entropy, according to an element e, used at a node N having the children {n j , j ∈ [|1, F |]}, these nodes corresponding to each fuzzy term relative to e, is then defined as :

E = - nj f r nj c k f r c k /nj log(f r c k /nj ) (4)
where {c k , k ∈ [|1, K|]} is the set of the classes of the problem.

When the tree is built, we create a rule for each of its leaves : the premise is the conjunction of the fuzzy terms associated with the nodes leading from the root to the leaf, and the consequence is the most representated class in the leaf.

Recognition of new samples

Once the tree has been constructed using the training data, the classification of the testing data is quite simple. Given an imprecise example x, we compute the membership degree of x to each leaf l of the tree, using the very same definition we used for the training data (equations 2). For each class c, this membership degree is multiplied by the fuzzy frequency f r c/l of c conditionally to l (see definition 3), using the same formula as in [START_REF] Bounhas | A possibilistic rule-based classifier[END_REF], f r c/l being in fact the certainty factor defined in [START_REF] Bounhas | A possibilistic rule-based classifier[END_REF]. Using the weighted voting method [START_REF] Ishibuchi | Voting in fuzzy rule-based systems for pattern classication problems[END_REF], these results are then summed up for each class, over all the leaves, to obtain the confidence degree conf (x ∈ c) of x ∈ c. The algorithm finally classifies x in the class c maximizing conf (x ∈ c).

Experiments

Data simulation

Since the physical experiments supposed to provide us with real data could not be realized at the moment of the writing of this paper, we generated simulated data. To do so, we used the theoretical stoichiometric percentages of each element in each material (class) which provided us with reference values for each pair (class, element). To create an example x of a class c, a value m is randomly generated for each element e in an interval around the reference value of the pair (c, e), whose span is proportional to the reference value, the proportionality coefficient being called degree of imprecision in the following. The mean value of the Gaussian representing the imprecise proportion of e in x is set to m. A standard deviation is then randomly generated in an interval whose span is proportional to the one of the interval used to generate the mean.

To generate the data, we used the chemical formulae of seventeen explosives and nine drugs, with a degree of imprecision of 15%. Since the real data will be few due to the financial and temporal costs of the physical experiments, we chose to generate only ten examples per class to create a data set. Then, a five-fold cross-validation is performed on the set. The following results are averaged on the tests of ten different data sets.

Comparison of fuzzy partitioning algorithms

One of the most influential parameters of the fuzzy partition in terms of accuracy of the whole classification process is the number of fuzzy terms constituting the partitions of each chemical ratio domain. Thus, we ran tests with k-medoids algorithm using the previously defined dissimilarity (see 1) over the grid of all the combinations of numbers of terms between 2 and 14, for elements C, N and O only, imposing five fuzzy terms for the other elements. Indeed, C, N and O ratios are the most discriminative features in our problem so we focused on them to run quicker tests. The graphic 6 shows the dependence of the correct classification rate of the tree on the numbers of fuzzy terms partitioning C, N and O chemical ratio domains. We can easily see that the accuracy increases when the number of fuzzy terms increases, until a certain threshold. For N and O, this threshold is about 12, whereas it is surprisingly low for C -around 6. The best results are actually obtained for number of terms between 5 and 7 for C, and between 11 and 14 for N and O -several of these combinations give the best classification rates, between 84.5% and 85%.

We then tested the clustering algorithm called affinity propagation [START_REF] Frey | Clustering by passing messages between data points[END_REF], using the similarity associated with the previously defined dissimilarity : s(x, y) = b a min(f x (t), f y (t)). Affinity propagation does not take the number of clusters (thus fuzzy terms) in parameter but a parameter called preference that increases the number of clusters when it is high. Giving the same preference to the clustering for the partitions of C, N and O ratios give worse results than the best obtained with k-medoids. But in the light of k-medoids tests, we tried to give Fig. 6: Correct classification rate against number of fuzzy terms smaller preference to C partition and greater for N and O partitions, and results similar to the best ones of k-medoids were obtained (between 84% and 85%).

We can conclude that k-medoids algorithm is preferable for this problem since it gives results as good as affinity propagation but the parameter to be optimized -the list of the numbers of fuzzy terms -is discrete whereas affinity propagation preference is continuous.

In order to improve the robustness of our method, it would have been interesting to split the training set in two parts in order to learn the fuzzy terms from different data from the ones used to build the tree. But since our data are very few, we decided to learn the fuzzy terms and tree from the whole training set.

Results analysis

From the grid-based test over the combinations of numbers of fuzzy sets for C, N and O, we determined the best combination in terms of accuracy : respectively 5, 14 and 12 terms for C, N and O. Figure 8 is a confusion matrix that summarizes the results of the classification using k-medoids with this optimal combination of numbers of fuzzy sets regarding C, N and O, and 5 fuzzy terms for the other elements. We note that the algorithm classes quite correctly both the explosives (seventeen first classes from the top in ordinate) and the drugs (six last classes). This method does represent an improvement compared to the classic algorithms which do not take the imprecision of the data into account. As we can see on figure 7, the correct classification increases up to 14%, this difference being higher for more imprecise simulated data.

We ran the method with the same numbers of fuzzy terms on a more complex data set composed of 38 classes of drugs, explosives and benigns. The accuracy obtained is 75% (see the confusion matrix on figure 9).

Conclusion

In this article, we introduced a workflow for explainable material recognition from their chemical composition and based on both a decision tree induction and linguistic variables learning. The method takes into account the imprecision of data during the learning phase and the exploitation of the decision tree. It performs better for high imprecision: the classification rate is up to 84% for a classification into 26 classes.

We have several opportunities to enhance our method's accuracy in further work. We may improve our clustering technique taking the samples' labels into account. Using pruning techniques but also random forests could make the method more accurate. We will also study more sophisticated techniques than the sum we are using for aggregating the results of each leaf of the tree. As far as the rules are concerned, we might generate simpler rules corresponding to intern nodes of the tree. We shall also test the possibilistic approach with other measures and methods more adapted to it.

At this stage of our work, the method has been evaluated on simulated data while we are performing real data acquisition on pure elements, chemical products, drug and explosive simulants. This will be a first step since in real life container voxels, several materials will be present. We will then have to deal with recognition of mixtures and not only mono-material samples.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Neutron inspection workflow

  dissimilarity used is inspired by the Jaccard distance : d(A, B) = 1 -|A∩B| |A∪B| , where A and B are two sets. The sets are here replaced by the probability distributions representing two imprecise data, the cardinality by the integral of the distribution, the intersection and union respectively by the min and max. Thus, for two imprecise data x and y represented by the densities of probability f x and f y respectively, the dissimilarity becomes : d(x, y) = 1-b a min(fx(t),fy(t)) b a max(fx(t),fy(t))

  is the training set and the "membership frequency" of the examples to the node n : f r n =

Fig. 7 :Fig. 8 :Fig. 9 :

 789 Fig. 7: Gain obtained when taking the imprecision of the data into account

This dissimilarity is actually a distance for continuous distributions but we will not show it in this paper for reasons of space.

Acknowledgment

This research has been funded by the project H2020 C-BORD. We warmly thank S. Moretto, C. Fontana, F. Pino, A. Sardet, C. Carasco, B. Prot and V. Picaud for their contributions before our work, for their availability and their expertise.


Keywords: MANET, réseaux à connexion intermittente, théorie de l'information, propagation de l

information, vitesse, performances.

Vitesse de Propagation de l'Information dans les Réseaux Mobiles Tolérants aux Délais

Résumé : Des travaux récents ont montré la nécessité de développer des protocoles de routage pour les réseaux mobiles ad hoc où un chemin multi-sauts entre toute paire de sommet n'est pas guarantie, et où donc les communications ne peuvent se faire qu'en combinant le temps et la mobilité. Suivant le contexte, ces réseaux sont appelés "réseaux mobiles à connexion intermittente (ICNs)" ou "Réseaux Mobiles Tolérants aux Délais et aux Dérangements (DTNs)". En contre partie, il y a peu de connaissance sur les propriétés intrinsèques de ces réseaux, et du coup, les évaluations de performance sont limitées à des comparaisons de simulations (utilisant des modèles de mobilité spécifiques et des traces réelles).

Le but de ce rapport de recherche est d'accroitre notre connaissance des performances possibles dans ces réseaux DTNs. Après avoir défini notre modèle d'étude, nous utilisons des outils analytiques pour obtenir des bornes supérieures théoriques de la vitesse de propagation de l'information dans les réseaux mobiles ad hoc. Nous présentons également des simulations numériques pour illustrer l'exactitude de nos bornes dans de nombreuses configurations.

Introduction

Our objective is to evaluate the maximum speed at which a piece of information can propagate in a mobile wireless network. If the network is connected (i.e., an end-to-end multi-hop path exists) this speed is rather high and can be considered infinite compared to the mobility of the nodes: a piece of information is a packet (of small size) which can be transmitted almost instantaneously between two nodes in range.

A major difficulty occurs when the mobile network is temporary disconnected. In this case the information propagation is stalled as long as the node mobility does not allow the information to jump to different connected components of the network. The packet is either transmitted or carried by a node (requiring a store-carry-and-forward routing model). Thus, a "path" is an alternation of packet transmission and packet carriage that connects a source to a destination, and is better referred (from now on) as a journey.

Depending on the context, these networks are commonly referred as Intermittently Connected Mobile Networks (ICNs) or Mobile and Delay/Disruption Tolerant Networks (DTNs). Numerous efforts have been dedicated to the design of efficient routing protocols (see [START_REF] Zhang | Intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges[END_REF] for a survey of most results).

Unfortunately, performance evaluations are often limited to comparative simulations, using concrete traces (e.g., [START_REF] Sarafijanovic-Djukic | Island Hopping: Efficient Mobility-Assisted Forwarding in Partitioned Networks[END_REF][START_REF] Zhang | Study of a Bus-Based Disruption Tolerant Network: Mobility Modeling and Impact on Routing[END_REF]) or specific mobility models [START_REF] Camp | A Survey of Mobility Models for Ad Hoc Network Research[END_REF], as a complete understanding of what one can expect for optimal performance (e.g., through theoretical bounds) is still missing.

Informally, our aim is to find the shortest journey (in time) that connects a source to a destination. (Note that formally, we should denote this as the "earliest" or "foremost" journey as the smallest time required between a particular source and a particular destination will vary with the time of the request. However, as we are in fact interested in the overall propagation speed, between any source and any destination, we will denote it as the shortest journey without lack of generality.) It is worth noting that the shortest journey in time from a source to its destination can be calculated in polynomial time when the changes in the network topology can be predicted in advance (e.g., [START_REF] Bui Xuan | Computing Shortest, Fastest, and Foremost Journeys in Dynamic Networks[END_REF][START_REF] Ford | Flows in Networks[END_REF][START_REF] Halpern | Shortest Path with time constraints on movement and parking[END_REF]).

Without predictive knowledge, we can still achieve the fastest possible information propagation, by using an algorithm that contains all possible "shortest" journeys: the full broadcast. We call the information, the beacon. Every time a new node is in range of a node which carries a copy of the beacon, the latter node transmits another copy of the beacon to the new node. Transmission is done indifferently by broadcast or unicast, this does not change the details of our model.

We do not consider here the fact that the high rate of transmission will affect the range of transmission (e.g., Gupta and Kumar [START_REF] Gupta | The capacity of wireless networks[END_REF]) and that packet loss will occur: our model is intended to unfold all journeys from a source to a destination for which a window of opportunity for transmission may be possible.

Mobile network model

We consider an infinite two-dimensional network with uniform node distribution and with constant density ν. We assume that each node follows an independent walk of speed v. The node keeps a uniform speed but changes direction at Poisson rate τ .

When τ → ∞ we are on the Brownian limit, when τ → 0 we are on a random way point-like model. The motion direction angles are uniform distributed between 0 and 2π.

Initially, we also adopt the unit-disk model: two nodes at distance smaller than one can exchange the beacon. The average number of neighbors per node is therefore πν.

In [START_REF] Xue | The number of neighbors needed for connectivity of wireless networks[END_REF], Xue and Kumar have shown that if the average number of neighbors is smaller than 0.074 log N , N being the total number of nodes in the network then the network is surely disconnected.

The network in our model being infinite it is surely disconnected. However the accumulated size of neighbors increasing with time, there exists almost surely a journey between a source and a destination if one waits long enough (i.e., the accumulated topology becomes connected over time [START_REF] Pellegrini | A Graphbased Model for Disconnted Ad Hoc Networks[END_REF]).

Main results

Our main result is the evaluation of an upperbound of the information propagation speed. In fact the concept of propagation speed is probabilistic. Let consider a mobile at coordinate z = (x, y) at time t = 0, let q(z, t) denotes the probability that the mobile receives the beacon before time t. A scalar σ 0 > 0 is an upper bound of the propagation speed, if for all σ > σ 0 lim q(z, |z| σ ) = 0 when |z| → ∞. For example if q(z, t) < exp(-a|z| + bt + c) then quantity b a is a propagation speed upperbound.

Theorem 1 An upper bound of the information propagation speed in a network (where node radio range is R, node density is ν, node speed is v, node direction change rate is τ ) is the smallest ratio θ ρ attained by the elements (ρ, θ) of the set K made of the non negative tuples (ρ, θ) that are root of

(τ + θ) 2 -ρ 2 v 2 -τ - 8vR π νI 0 (ρR) 1 -πR 2 νΨ(ρR)
where functions I 0 () and Ψ() can be expressed in terms of modified Bessel functions (see [START_REF] Abramowitz | Chapter 9, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables[END_REF]) and are defined respectively by

I 0 (x) = k≥0 ( x 2 ) 2k 1 (k!) 2 and Ψ(x) = 2 x I 1 (x) = k≥0 ( x 2 ) 2k 1 (k + 1)!k! .
Remark Quantity ρ is expressed as inverse of distance and quantity θ is expressed as an inverse of time, therefore the ratio θ ρ is the dimension of a speed. In the remaining of the paper, and w.l.o.g., we will assume that R = 1.

Since quantities I 0 (x) and Ψ(x) are both greater than 1, the previous expression has meaning when ν < 1 π . When ν ≥ 1 π , our model indicates an infinite propagation speed. Therefore our model is interesting when ν is small. Similarly, when v = 0 and ν < 1 π , the propagation speed is zero.

INRIA

Corollary 1 Let v > 0 and τ > 0, when ν → 0, the propagation speed is asymptotically equivalent to 4v νvR τ π .

It is important to notice that the speed diminishes with the square root of the density ν.

However this estimate does not hold in the case τ = 0 that we will fully depict as the random waypoint model limit later in the paper.

Corollary 2 In the random waypoint limit, that is τ = 0, the propagation speed upper bound is

(1 + O(ν 2 ))v.
Remark It turns out that the propagation speed upperbound at the limit is v. It is rather surprising because we would expect that the propagation speed tends to zero when ν → 0. In fact the corollary is not only correct but also accurate as we will confirm by simulations. The explanation is that we first set ν and then look at the propagation speed when the mobile nodes are located at location infinitely far from the beaconing source. This is different than considering first a node at a remote location z from the source and then let ν → 0. In fact we have q(z, t) < exp(-a|z| + bt + c) and c → ∞ when ν → 0 confirming that propagation speed tends to zero when ν → 0 when z is fixed, but tends to

(1 + O(ν 2 ))v when ν is fixed and |z| → ∞.
A rule of thumb for having v lower-bounding the propagation speed is that as soon as the set of attained nodes is large enough there is likely to be one heading toward z.

Plan of the paper

We adopt a didactic approach. In Section 2, we will initially study a simpler problem where nodes are only allowed to transmit when they change direction or when they receive the beacon. This is not an upper-bound since we do not allow nodes to transmit when they move (although it is worth noting that it will converge to the real problem when we consider the Brownian limit). We will develop and comment our analytical tools in this simpler approach. In Section 3, we will complicate the approach to make it general (and realistic), by allowing nodes to transmit only when they have a new neighbor or when they receive a new copy of the beacon (i.e., when a local event occurs). In Section 4, we present some numerical simulations to illustrate the accuracy of the bounds in numerous scenarios.

Simplified approach

In this section we suppose that nodes can only transmit when they change direction or when they receive the beacon.

Journey analysis

Our analysis is based on journey segmentation between the source and the destination. Formally, a journey is a space-time trajectory of the beacon between the source and a destination. We assume that time zero is when the source transmits, and we will check at what time t, the beacon is emitted at distance smaller than one to the destination at coordinate z = (x, y). The beacon can take many journeys in parallel, due to the broadcast nature of radio transmission, and the fact that the beacon stays in the memory of the emitter (and therefore can be emitted several times in the trajectory of a mobile node). In a first approach and in order to simplify we will assume that the destination is fixed (the node does not move). We will later modify the model in order to support the destination motion.

We will consider only simple journeys, i.e., journeys which never return twice through the same node. If a journey arrives to the destination at time t then we can extract a simple journey from this journey which arrives at time t too.

To simplify the presentation we now consider journeys as if they were enumerable objects and therefore can be affected to a probability weight. In the following we will in fact consider a journey as a discrete event in a continuous set and therefore the probability weight should be converted into a probability density.

Let C be a simple journey. Let Z(C) be the terminal point. Let T (C) be the time at which the journey terminates. Let p(C) be the probability of journey C.

We call p(z, t) the average number of journeys that arrive at z before time

t: p(z, t) = lim r→∞ 1 πr 2 |z-Z(C)|<r,T (C)<t p(C) .

Journey segmentation

In the following we split the journey into segments C = (s 1 , s 2 , . . . , s k ) such that

p(C) = p(s 1 )p(s 2 ) • • • p(s k ).
Therefore a journey is made by two kinds of segments:

• Carry segment s c : the beacon is hold until the next change of direction;

• Emission segment s e : the beacon is transmitted to a neighbor.

A carry segment s c is a space-time vector (tv cos φ, tv sin φ, t) where φ is the direction angle of the motion vector which belongs to [0, 2π[, and t is the time duration of segment. At this level of the analysis the segments are no longer enumerable and we refer to probability density of segment which is

p(s c ) = 1 2π τ e -τ t
since all angles have same probability. An emission segment s e is a space time vector (r cos φ, r sin φ, ) with r ∈ [0, 1[. The quantity is the time needed for a transmission assumed being small compared to typical node mobility, practically = 0. W.l.o.g, we take later = 0 in order to insist on the fact that transmission times are infinitely smaller than moving times. With respect to variable φ and r, we have the density p(s e ) = νr .

Notice that a journey of k segments is made of k space vectors and p(C) is therefore a density in vector of dimension 3k. By virtue of Laplace transform we have

p(z, t) = ( 1 2iπ ) 3 w(ζ, θ)e ζ.z+tθ dζ dθ θ (1)
where the integration domains are plans parallel to the imaginary plan in the definition domain. And in this case the quantity p(z, t) is the average density of journeys that arrive at z before time t.

A journey being an arbitrary combination of carry segments and emission segments, we have the simple expression inspired from combinatorial analysis:

w(ζ, θ) = 1 1 -sc p(s c )e -sc,(ζ,θ) -se p(s e )e -se,(ζ,θ) (2)
where the quantity s c , (ζ, θ) is the dot product between two space-time vectors.

We have the expression where

Ψ(x) = 2 x I 1 (x) = k≥0 ( x 2 ) 2k 1 (k + 1)!k! .

Saddle point analysis

Equation (1) for p(z, t) can be rewritten as

( 1 2iπ ) 3 w(ζ0 + iθ, θ0 + iθ)e (ζ 0 ,θ 0 ),(z,t) +i (ζ,θ),(z,t) dζ dθ θ0 + iθ (3)
where the integration domain are real plans.

The key of the analysis is the set K of pairs (ρ, θ) such that D(ρ, θ) = 1, called the Kernel.

Theorem 2 When |z| and t tend both to infinity we have

p(z, t) = (1 + O( 1 √ t )) exp(-ρ 0 |z| + θ 0 t) 2πθ 0 D θ Dρ ρ0 ∇ 2 D(t, |z|)
where (ρ 0 , θ 0 ) is the element of K that minimizes -ρ|z| + θt.

Quantity D ρ = ∂ ∂ρ D, D θ = ∂ ∂θ D and ∇ 2 D(x, y) = x 2 ∂ 2 D ∂ρ 2 + y 2 ∂ 2 D ∂θ 2 + 2xy ∂ 2 D ∂ρ∂θ RR n°6390
Proof The function 1 -D(ρ, θ) has a definition domain {(ρ, θ), ((θ + τ ) 2ρ 2 v 2 ) > 0} and, when θ varies, it has a simple root at

θ(ρ) = ( τ 1 -πνΨ(ρ) ) 2 + ρ 2 v 2 -τ.
Notice that (ρ, θ(ρ)) describes the set K. In order to have ρ > 0 for some elements in K and to apply a consistent analysis we need the condition πν < 1.

Therefore the residues analysis gives:

p(|z|, t) = I(z, t) + R(z, t)
where

I(z, t) = 1 (2iπ) 2 exp (ζ, θ(|ζ|)), (z, t) θ(ρ)D θ (ρ, θ(ρ)) dζ
with D θ = ∂ ∂ρ D, and R(z, t) is the integral of exp( (ζ,θ),(z,t)

(1-D(|ζ|,θ)θ when ρv -τ < (θ) < θ(ρ).

We will show at the end that R(z, t) = O(e -Bt I(z, t)) for some B > 0.

We first focus on I(z, t) by using saddle point techniques. Let ζ 0 be the value that minimizes (ζ, z + θ(|ζ|)t). Obviously ζ 0 = -ρ0 |z| z with ρ 0 that minimizes -ρ|z| + θ(ρ)t.

Let θ and θ be the first and second derivatives of θ(ρ) respectively. We already know that θ = |z| t . Since D(ρ, θ(ρ)) = 1, by derivation with respect to ρ we have D ρ + D θ θ = 0 and, by second derivation, ∇ 2 D(1, θ ) + D θ θ = 0 at ρ = ρ 0 . Without loss of generality we assume that z = (-|z|, 0) and ζ = (-ρ 0 , 0) + (x, y), thus

|ζ| = ρ 0 -x + 1 2ρ 0 y 2 + O(x 3 + y 3 )
and in turn

ζ.z + θ(|ζ|)t = -ρ 0 |z| + θ 0 t + t 2 (θ x 2 + θ ρ 0 y 2 ) + O((x 3 + y 3 )t) By change of variable ζ = (-ρ 0 , 0) + i √ t (x, y) we get ζ.z + θ(|ζ|)t = -ρ 0 |z| + θ 0 t -1 2 (θ x 2 + θ ρ0 y 2 ) + O((x 3 + y 3 )t -1/2 ) (4) I(z, t) = exp(-ρ0|z|+θ0t) (2π) 2 exp( 1 2 (θ x 2 + θ ρ 0 y 2 )) θD θ dxdy × (1 + O(t -1/2 )) = exp(-ρ0|z|+θ0t) 2πθ0D θ θ θ ρ 0 (1 + O(t -1/2 )) . (5)
To terminate with integral R(z, t) we identify

B = θ 0 -ρ 0 v + τ. INRIA 2.

Information propagation speed

Let q(z, t) be the probability that there exists a journey that arrives at distance less than 1 to z before time t.

Theorem 3

We have the upper-bound:

q(z, t) ≤ |z-z |<1
p(z , t)dz .

Therefore q(z, t) = Θ(p(z, t)) and clearly q(z, t) vanishes very quickly when t is smaller than the value such that -ρ 0 |z| + θ 0 t = 0, i.e. when θ0 ρ0 = z t = θ (ρ 0 ). This ratio gives the upper-bound of the propagation speed. In other word point (ρ 0 , θ 0 ) which achieves the lowest ratio θ ρ in the kernel set K.

The moving destination

In the previous evaluation we assume that the destination does not move during the propagation of the information. Now we consider that the destination can move as the other nodes, starting at position z at time t = 0.

Theorem 4 When the destination moves as the other nodes in the network then the asymptotic propagation speed upper bound does not change when (z, t) tend to infinity.

For this end it suffices to multiply the journey Laplace transform w(ζ, θ) with the Laplace transform of the node excursion from its original position. The excursion Laplace transform is obtained from carry segment Laplace transform and has expression

1 f (|ζ|,ρ)-τ with f (ρ, θ) = (θ + τ ) 2 -ρ 2 v 2 .
The new Laplace transform has two sets of poles, the set K and the set K 2 corresponding to the set {(ρ, θ), θ = ρv -τ }. The last set is dominated on the right by CK, for all (ρ, θ 2 ) ∈ K 2 , there is a (ρ, θ) in K with θ > θ 2 + B. Therefore the contributions from K 2 will be exponentially negligible (of order exp(-Bt)) with regard to the main contribution from K.

The main contribution from K gives

p(z, t) ∼ exp(-ρ 0 |z| + θ 0 t) (f (ρ 0 , θ 0 ) -τ )2πθ 0 D θ Dρ ρ0 ∇ 2 D(t, |z|)
and the propagation speed upper-bound does not change from the value computed in the last subsection.

3 Realistic Approach (Proof of Theorem 1)

In this approach we assume that the nodes can transmit only when they meet new neighbors or when they receive the beacon. According to [START_REF] Jacquet | Control of Mobile Ad Hoc Networks[END_REF] when nodes move at speed v with isotropic direction, then the frequency f at which new neighbors appear satisfies f = 8v π ν.

Lemma 1

The journey Laplace transform with realistic approach has the expression

w(ζ, θ) = R(|ζ|, θ) 1 -D(|ζ|, θ) with D(ρ, θ) = 1 (θ + τ ) 2 -ρ 2 v 2 τ + f I 0 (ρ) 1 -πνΨ(ρ)
where

I 0 (x) = k≥0 ( x 2 ) 2k 1 (k!) 2 and R(ρ, θ) = 1 (θ + τ ) 2 -ρ 2 v 2 .
Proof A typical journey is an arbitrary mixture of carry segments s c and carry-and-transmit segments s ce . A carry-and-transmit segment is made of a carry-to-neighbor segment s cn and transmit-to-neighbor segment s tn followed by an arbitrary number of emission segments s e . The generating function of the arbitrary number of emission segment is

1 1-πνΨ(ρ)
. The carry-to-neighbor segment is a space-time vector (v cos φ, v sin φ, t) where φ is a number in [0, 2π[ and t is a non negative number. We have the density p(s cn ) = e -τ t f 2π .

The generating function:

E(e (ζ,θ),scn ) = f (ρ + τ ) 2 -ρ 2 v 2
For the transmit-to-neighbor segment we assume that the beacon is transmitted to the new neighbor only, at distance 1, the other neighbors having already received the beacon. Therefore a transmit-to-neighbor segment is a space-time vector (cos φ, sin φ, 0), and p(s tn ) = 1 2π . Computing the generating function yields.

E(e (ζ,θ),stn ) = 2π 0 e |ζ| cos φ dφ 2π = I 0 (|ζ|)
Finally the generating function of the carry-and-transmit segment is

f I 0 (ρ) (θ + τ ) 2 -ρ 2 v 2 (1 -πνΨ(ρ))
.

Therefore the function w(ζ, θ) is in denominator 1-E(e (ζ,θ),sc -E(e (ζ,θ),sce and in numerator, the function 1

√

(ρ+τ ) 2 -ρ 2 v 2 , the excursion Laplace transform, to indicate that the last straight line before the destination. This terminates the proof.

Using the methodology developed in the simplified approach section, we now prove Theorem 1 as follows.

INRIA

Theorem 1 An upper bound of the information propagation speed in a network (where node radio range is R, node density is ν, node speed is v, node direction change rate is τ ) is the smallest ratio θ ρ attained by the elements (ρ, θ) of the set K made of the non negative tuples (ρ, θ) that are root of

(τ + θ) 2 -ρ 2 v 2 -τ - 8vR π νI 0 (ρR) 1 -πR 2 νΨ(ρR)
.

Proof The Kernel of w(ζ, θ) is the root of the denominator (τ + θ) 2 -ρ 2 v 2 - τ - 8vR π νI0(ρR)
1-πR 2 νΨ(ρR) . Therefore, following the asymptotic analysis of the average number of journeys, the propagation speed upperbound is given by the minimum ratio θ ρ of (ρ, θ) ∈ K.

Corollary 1 Let v > 0 and τ > 0, when ν → 0, the propagation speed is asymptotically equivalent to 4v νvR τ π .

Proof Let (ρ, θ) be an element of the set K. W.l.o.g. for R = 1, we have

θ = (τ + νH(ρ)) 2 + ρ 2 v 2 -τ , with H(ρ) = 8 π I0(ρ)
1-πνΨ(ρ) . We have

H(ρ) = 8v (1 -πν)π + O(ρ 2 ).
Therefore

θ = τ 2 + ρ 2 v 2 -τ + τ τ 2 + ρ 2 v 2 H(ρ)ν + O(ν 2 ).
The ratio

θ ρ = H(ρ)ν ρ τ τ 2 +ρ 2 v 2 + √ τ 2 +ρ 2 v 2 -τ ρ + O( ν 2 ρ ) = H(0)ν ρ + ρv 2 2τ + O( ν 2 ρ + νρ 2 ) Quantity H(0)ν ρ + ρv 2 2τ is minimized with value v 2νH(0) τ attained at ρ = √ 2ντ H(0) v . Therefore θ ρ is minimized at value v 2νH(0) τ + O(ν 3/2 ).

The random way-point limit

The random way-point model is equivalent to set τ = 0. It is not really the random way-point model, since the true random way-point model assumes a finite convex map and our model is developed on infinite maps. Indeed the node density in the finite random way-point is not uniform and there is no independence between speed angle and node position. Anyhow if we consider a disk map that grows to infinity, then we will get our infinite random way-point model.

There is nothing particular about our random way-point model, excepted that the Kernel set K is made of points (ρ, θ(ρ)) where θ(ρ

) = v ρ 2 + G(ρ) 2 with G(ρ) = 8ν π I0(ρ)
1-πνΨ(ρ) . In this case the upper-bound speed is proportional to v with factor of proportionality equal to ρ 2 0 + G(ρ 0 ) 2 where ρ 0 minimizes G(ρ) ρ . Since G(ρ0) ρ0 = 8ν π min I0(ρ) ρ + O(ν 2 ) we get the estimate (1 + O(ν 2 ))v, proving Corollary 2.

The Brownian limit

The Brownian limit is more interesting. It happens when τ → ∞. But in this case if the speed remains constant, then at the limit the nodes does not move anymore. Therefore we have to accelerate the speed v suitably to get significant results. This is done by increasing the speed v such that v 2 τ tends to a limit σ called the Brownian variance spread factor.

In this case we get

(τ + θ) 2 -ρ 2 v 2 -τ = θ - v 2 τ ρ 2 + O( 1 τ 2 ).
This leads to θ(ρ) = vG(ρ)

+ σρ 2 + O( 1 τ 2 ).
If σρ 2 is negligible in front of vG(ρ) then we get the same estimate than with the random way point model. This estimate is clearly too large, because at fixed speed v, the nodes do not really move when τ → ∞. The reason for this discrepancy is that when a node enters a disk unit of another node then by virtue of the random walk it comes out and in again frequently, and this artificially adds to the neighbor creation rate f (this is the same neighbor that shows up and shows down). This particular model needs to be refined.

Bound values and Simulations

In this section, we first present some calculations to illustrate the behavior of our upper bound on the information propagation speed, then assess the accuracy of our theoretical upper bound by comparing it with simulation results.

Slowness of Information Propagation.

To illustrate the behavior of the upper bound on the information propagation speed when the mobile density ν varies, we define the slowness, i.e., the inverse of the information propagation speed, for which our theroretical study now provides lower bounds.

For the calculations, we use a Unit-Disk Graph model, where mobiles speed is 1s -1 . Two commonly used mobility models are simulated: Random Way-Point model (which corresponds to our setting τ = 0 as described in subsection 3.1) and Random Walk model (which corresponds to our setting τ = 0.1). Plotting results (obtained by numerical resolution) of our theoretical lower bound are presented in Figure 1 and in Figure 2 respectively. We remark that the slowness drops to 0 at ν = 1/π which corresponds to the limit of our model. Recall, that this is a lower bound of slowness (equivalent to the upper bound on the propagation speed). Actual slowness should continue to be non-zero beyond ν = 1/π.

For the Random Way Point (i.e., τ = 0), we notice that the slowness is in 1 -O(ν 2 ) confirming the Corollary 2. For the Random Walk, we notice that the slowness is unbounded when ν → 0 confirming the O( 1 √ ν ) theoretical behavior proved in Corollary 1. We now evaluate the accuracy of our theoretical upper bound in different scenarios by comparing it to the average information propagation time obtained by simulating a full broadcast (as described in Section 1). In all cases (see Figure 3 to Figure 10), we provide the simulated average information propagation time versus the distance (plots), and display the theoretical bound slope (in color). For the theoretical bound slope, the starting point is placed manually to best-fit the constant values which are not calculated in our model. Therefore the analysis of position of the slope as an upper or lower bound is irrelevant. Again, what is important is the comparison of the two slopes at infinity.

Again, we study the same two popular mobility models: Random Way-Point (i.e., τ = 0) and Random Walk (i.e., τ = 0.1) for different density and area values (ν = 0.025 on a 80 × 80 square, ν = 0.05 on a 60 × 60 square, ν = 0.1 on a 40 × 40 square, ν = 0.2 on a 30 × 30 square, respectively). For all the simulations, we use a Unit-Disk Graph model, where mobiles speed is 1s -1 .

For both mobility models, the simulations show that the theoretical bound provides an accurate slope until the network is too dense (ν = 0.2 on a 30 × 30 square), but the slope is still a lower bound as proved in the Theorems.

Conclusion

In this paper we have initiated a partial characterisation of the information propagation speed of Delay/Disruption Tolerant mobile Networks (DTNs) and Intermittently Connected mobile Networks (ICNs) by providing a theoretical upper bound. The model used in our analytical study is sufficiently general to encapsulate many popular mobility models (such as Random Way-Point and Random Walk). Simulations and calculations for several scenarios show the accuracy of our upper bound, specifically when the networks are sparse and may never be fully connected. Future investigations should consider extending the analysis to larger dimensions and neighboring models different from Unit-Disk Graphs (e.g., quasi-disk graphs, probabilistic models), as well as designing an accurate lower bound for the information propagation speed.

INRIA 2 . 1 . 2

 212 Journey Laplace transform Let ζ be a space vector and θ a scalar. We denote w(ζ, θ) the journey Laplace transform defined by w(ζ, θ) = E(exp(-ζ.Z(C) -θT (C))) = C p(C) exp(-ζ.Z(C) -θT (C)) defined for a domain definition for (ζ, θ). Notice that ζ.Z(C) is the dot product of two space vectors.

dφ 1 0

 1 sc p(s c )e -sc,(ζ,θ) |ζ|vt cos φ e -θt e -τ t dt = τ √ (τ +θ) 2 -|ζ| 2 v 2 Similarly se p(s e )e -se,(ζ,θ) = 2π 0 νrdre r|ζ| cos φ = πνΨ(|ζ|)

INRIA 4 . 2

 42 Accuracy: Theoretical Bounds vs. Simulations.

Figure 1 :

 1 Figure 1: Theoretical lower bound of slowness versus mobile density ν when τ = 0

Figure 2 :Figure 3 :Figure 4 :Figure 5 :Figure 6 :Figure 7 :Figure 8 :Figure 9 :Figure 10 :

 2345678910 Figure 2: Theoretical lower bound of slowness versus mobile density ν when τ = 0.1

RR n°6390


Anthony A Valero
email: anthony.valero@cea.fr

Dorian G Gaboriau

Pascal Gentile

Saïd Sadki

On ship integration of High-performance Micropseudocapacitors based on Silicon nanotrees coated by transition metal oxides and high-k dielectrics

Keywords: Micropseudocapacitors, Silicon nanotrees, Transition metal oxides, High-k dielectrics

In recent years, significant attention has been paid to the development of microdevices as innovative energy storage solutions. For instance micro-sensor networks such as sensors actuators or implantable medical devices require power densities and cyclability that are several orders of magnitude higher than those of conventional Lithium-Ion batteries. For such applications, Microsupercapacitors (MSCs), a developing novel class of micro/nanoscale power source are rising alternatives, and their integration "on-chip" could allow significant innovations to emerge. 1 Therefore, a great deal of attention has been focused on MSCs, for which large series of nanostructured active materials have been developed. Following this trend, our work focuses on MSCs made of silicon nanotrees 2,3 functionalized by high-k dielectrics and transition metal oxides as new nanostructured materials to improve their performances. Here we deposit NiCo2O4 4 oxides particles synthetized by various facile and scale up inorganic processes such as oxalate route and electrodeposition. Oxides based on Ni and Co have been chosen for their promising performances, as NiCoO4 nanowires electrodes were shown to exhibit a specific capacitance of 743 F.g -1 at 1 A.g -1 with excellent rate cycling stability (6.2% loss after 3000 cycles) 5 . We have also investigated the impact of the addition of a high-k dielectric layer, such as Al2O3 and HfO2 as protective films on silicon nanotrees exhibiting outstanding cycling performances with more than 4 billion cycle stability within a potential window of 4V.


Anthony Valero

Dorian Gaboriau

P Gentile

Saïd Sadki

Atomic Layer Deposition of Alumina on Silicon Nanotrees, towards the development of 3D ultrastable Aqueous Si Microsupercapacitor

Keywords: Microsupercapacitors, Silicon nanotrees, High-k dielectrics, aqueous electrolytes, PEDOT-PSS

In recent years, significant attention has been paid to the development of micro-devices as innovative energy storage solutions. For instance micro-sensor networks such as sensors actuators or implantable medical devices require power densities and cyclability that are several orders of magnitude higher than those of conventional Lithium-Ion batteries. For such applications, Microsupercapacitors (MSCs), a developing novel class of micro/nanoscale power source are rising alternatives, and their integration "on-chip" could allow significant innovations to emerge. 1 Therefore, a great deal of attention has been focused on MSCs, for which large series of nanostructured active materials have been developed.

Following this trend, we have demonstrated through comprehensive investigations the interest of silicon nanostructures grown by Chemical Vapor Deposition (CVD) as electrodes materials for MSCs using ionic liquid electrolytes 2,3 . The fine morphological tuning of the nanostructure allowed by the bottom-up approach enables specific designs of electrode architectures, with a considerable leeway compared to other techniques. Such latitude allows optimizing porosity and ionic and electronic pathways while keeping robust mechanical and thermal performances, depending on the target application. Nanostructures such as SiNWs and SiNTrs have displayed excellent electrochemical performances being stable over more than 1 million cycles of galvanostatic charge/discharge under a 4 V wide electrochemical windows in EMI-TFSI ionic liquid, with large power densities of 10 mW.cm - 2 and good capacitance values of 0.5 mF.cm -2 at high current density of 0.5 mA.cm -2 . 4 However a major silicon weakness which was still hindering its use with acqueous electrolytes is the native uncontrolled growth of silica when subjected to ambient atmosphere. Here we have developed a highly conformal passivation coating of a nanometric high-k dielectric layer of Al2O3based on the rising Atomic Layer Deposition (ALD) technique. ALD has proven to allow a nanometric thickness control of the deposited layer while being highly conformal and covering. Electrochemical stability performances in ionic liquid, were enhanced allowing symmetric 2 electrode devices to reach an unprecedented cell voltage of 5.5 V 5 , improving energy and maximum power densities compared to pristine nanostructured silicon. The cyclability was also largely enhanced, with only 3% capacitance fade after 10 6 galvanostatic charge/discharge cycles at 4 V, and no degradation even after several 10 5 resilience cycles over a 5 V window 5 . Moreover, the protective alumina layer enables the use of aqueous electrolytes for nanostructured Si based MSCs, which significantly increases the specific power of the devices up to 200 mW.cm -2 at 0.5 mA.cm -2 while keeping the capacitance performances at 0.5 mF.cm -2 . Furthermore the system is remarkably able to retain 99% of its initial capacitance after 2 billion galvanostatic charge-discharge cycles at high current density of 0.5 mA.cm -2 in an aqueous electrolyte of Na2SO4.

Eventually we have investigated the pseudocapacitive response of such MSCs in aqueous eletrolytes by a simple drop-cast method of a PEDOT-PSS film. The device exhibited promising performances with a specific energy of 2 Wh.kg -1 and a power density of 300 W.kg -1 at a current density of 1 A.g -1 .

The MSCs was able to retain 80% its initial capacitance after 50,000 galvanostatic charge-discharge cycles at 0.5 A.g -1 .

Acknowledgements

The authors would like to thank the DGA, Direction General de l'Armement, and the CEA for their financial and technical support throughout the PhD thesis of A. Valero.


P Gentile

Anthony Valero

Dorian Gaboriau

Maxime Boniface

Dmitry Aldakov

Saïd Sadki

Alu Ald

ALD Alumina Passivated Silicon Nanotrees electrodes for Ultrastable Microsupercapacitors

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

Abstract Title : ALD Alumina Passivated Silicon Nanotrees electrodes for Ultrastable Microsupercapacitors Submitted to symposium Q : Synchrotron Radiation and Atomic Layer Deposition for Advanced Materials of the E-MRS 2017 Fall Meeting, which will be held at the Central Campus of Warsaw University of Technology (Poland) from September 18 to 21, 2017. by Authors : P. Gentile, A. Valero, D. Gaboriau, M. Boniface, D. Aldakov, S. Sadki Affiliations : Univ. Grenoble Alpes, CEA, CNRS, INAC, SYMMES, F-38000 Grenoble - -------------------------------------------------------------Abstract : The current trend towards miniaturized and autonomous electronic devices requires innovative energy storage solutions. For instance, autonomous micro-sensor networks or implantable medical devices would need a robust power source with high cyclability and a large power density, which might be out of the scope of conventional battery technologies. For such applications, microsupercapacitors (µSCs) are promising alternatives, and their integration ?on-chip? could allow significant innovations. However, finding a suitable ?onchip? µSCs technology implies addressing key challenges, such as temperature resistance, silicon industry compatibility and good electrochemical performances on a small footprint. Nanostructures such as SiNWs and SiNTrs demonstrated excellent cyclability with more than 1 million cycles of galvanostatic charge/discharge under a 4 V wide electrochemical windows in EMI-TFSI ionic liquid, with large power densities and good capacitance values. Moreover, the use of silicon for electrode material allows extremely interesting developments towards ?on-chip? integration and potential scale-up production using standard silicon industry processes for small micro-sized energy storage devices. Furthermore, we have also investigated the impact of the addition of a high-k dielectric layer, such as Al2O3 as protective films on silicon nanotrees. The electrochemical performances was enhanced, allowing symmetric 2 electrodes device to reach an unprecedented cell voltage of 5.5 V, improving energy and maximum power densities compared to unmodified nanostructured silicon. The cyclability was also largely enhanced, with only 3% capacitance fade after 1 million galvanostatic charge/discharge cycles at 4 V, and no degradation even after several 100000 cycles over 5 V.

--------------------------------------------------------------Abstract Type : Invited


Sébastien Deck. Pierre-Elie Weiss

Sébastien Deck

Advanced Numerical Strategy for the Prediction of Unsteady Flow Aerodynamics around Complex Geometries

published or not. The documents may come

Advanced Numerical Strategy for the Prediction of Unsteady Flow Aerodynamics around Complex Geometries

Pierre-Élie Weiss and Sébastien Deck

DAAA, ONERA, Université Paris Saclay, F-92190 Meudon -France

One of the future challenges in Computational Fluid Dynamics deals with the ability to simulate quantitatively the physical phenomena driving the multi-scale physics of turbulent flows around complex geometries.

Considering this frame, the present work focuses on an advanced numerical methodology named ZIBC standing for Zonal Immersed Boundary Conditions [START_REF] Mochel | Zonal Immersed Boundary Conditions: Application to a high Reynolds number afterbody flow[END_REF][START_REF] Weiss | On the coupling of a zonal body-fitted/immersed boundary method with ZDES: application to the interactions on a realistic space launcher afterbody flow[END_REF][START_REF] Deck | A rapid and low noise switch from RANS to WMLES on curvilinear grids with compressible flow solvers[END_REF] enabling to account for realistic configurations [START_REF] Hannemann | Launch Vehicle Base Buffeting: Recent Experimental and Numerical Investigations[END_REF][START_REF] Schwane | Numerical Prediction and Experimental Validation of Unsteady Loads on ARIANE 5 and VEGA[END_REF][START_REF] Pain | Zonal Detached Eddy Simulation of the flow around a simplified launcher afterbody[END_REF][START_REF] Weiss | ZDES of the flow dynamics on an Ariane 5-type afterbody with and without struts[END_REF] at high Reynolds numbers. The numerical strategy allowing the coupling between a modelling method (e.g. RANS, URANS, ZDES, LES or DNS) and IBC (Immersed Boundary Conditions) is detailed. In this paper, the modelling method retained is the Zonal Detached Eddy Simulation (ZDES) which has reached a high level of maturity on turbulent separated flows [START_REF] Deck | Unsteadiness of an axisymmetric separatingreattaching flow[END_REF][START_REF] Weiss | On the dynamics of axisymmetric turbulent separating/reattaching flows[END_REF][START_REF] Weiss | Control of the antisymmetric mode (m = 1) for high Reynolds axisymmetric turbulent separating/reattaching flows[END_REF]. Then, the numerical strategy can be applied to complex configurations dealing with internal or external Aerodynamics such as a full space launcher configuration. As an example, Fig. 1(a) illustrates the feasibility to simulate the interactions between the technological details, treated with IBC, and the simplified afterbody, modelled with a body-fitted (BF) approach consisting in classical adiabatic no-slip boundary conditions, in the turbulent flow field surrounding the main stage of the space launcher afterbody. In particular, the ZIBC simulation allows to return the salient unsteady features of the flow field such as the wall pressure fluctuations (see Fig. 1(b)).

Fig. 1

 1 Fig. 1 (a) Thick slices of the instantaneous streamwise velocity field of the ZDES simulation around a full space launcher modelled with ZIBC : grey parts ('clean' configuration) are modelled with a body-fitted (BF) approach, yellow parts (technological details) are taken into account using an immersed boundary (IB) method. (b) Contours of the fluctuating pressure coefficient Cp rms at the wall and in the flow field.

Seventh HRLM Symposium, 19-21 September 2018, Berlin, Germany Session: