Keywords: WLAN, WiFi, WiMAX, IEEE 802.11, spectral efficiency, radio channel Réseau radio local, WiFi, WiMAX, IEEE 802.11, efficacité spectrale

In the context of radio distributed networks, we present a generalized approach for the Medium Access Control (MAC) with fixed congestion window. Our protocol is quite simple to analyze and can be used in a lot of different situations. We give mathematical evidence showing that our performance is tight, in the sense that no protocol with fixed congestion window can do better. We also place ourselves in the WiFi/WiMAX framework, and show experimental results enlightening collision reduction of 14% to 21% compared to the best known other methods. We show channel capacity improvement, and fairness considerations.

Introduction

Radio networks have received in the past years a growing interest for their ability to offer relatively wide band radio networking. Applications cover a large area of domains including computer network wireless infrastructures, and high speed Internet access for rural areas.

In particular, in WiFi and partly WiMAX norms, the underlying mechanism [START_REF]Higher-speed physical layer extension in the 2.4 GHz band[END_REF][START_REF]IEEE standard for local and metropolitean network. Part 16: Air Interface for Broadband Wireless Access System (IEEE802.16 REVd D[END_REF] (see also [START_REF] Seo | Performance of IEEE 802.16 random access protocol -steady state queuing analysis[END_REF]) is a 2-layer protocol whose first part relies on a derivative of the Binary Exponential Back-off protocol (BEB). The principle is that when a failure occurs, the transmission protocol delays the following retransmission by some penalty factor. The protocol uses a contention window (CW) mechanism to realize this back-off mechanism. Roughly speaking, the probability of trying an access to the channel is 1/CW. When a transmission fails, the station increases CW in order to be less demanding for futures accesses.

Already much research work has been done to model the CW increase /decrease process. Strong simplifying assumptions are at the basis of some models [START_REF] Cali | Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit[END_REF], while some others focus on an individual station while considering that the effect of the others on the channel can be represented by an occupancy probability p occ (see [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF][START_REF] Wu | Performance of reliable transport protocol over IEEE 802.11 wireless LAN: analysis and enhancement[END_REF][START_REF] Xiao | Saturation performance metrics of the IEEE 802.11 MAC[END_REF]), following an earlier popular approach on CSMA [START_REF] Kleinrock | Packet switching in radio channels: Part I -carrier sense multiple access modes and their throughput-delay characteristics[END_REF][START_REF] Beuerman | The delay characteristics of CSMA/CD networks[END_REF].

In fact, those studies show that on average, the contention window mechanism draw the stations to access the channel with some probability that converges to a value noted p acc (n) which depends on the number n of stations simultaneously willing to access the channel. Therefore several studies have shown that the optimal behavior is when p acc (n) = O(1/n), and proposed some alternative mechanisms to increase and decrease the contention window in order to reach this value. In [START_REF] Bononi | Optimization of IEEE 802.11 wireless LANs performance[END_REF], the authors aim at guessing the total number of stations trying to emit in order to directly set the value CW . In [START_REF] Galtier | Optimizing the IEEE 802.11b performance using slow congestion window decrease[END_REF], an optimization of the increase /decrease parameters is done to converge to the optimal channel efficiency in terms of capacity. In [START_REF] Heuse | Idle sense: An optimal access method for high throughput and fairness in rate diverse wireless LANs[END_REF] the authors use the observation of idle slots to deduce the probable number of competing stations.

A different branch of CSMA protocols has been initiated by the Hiperlan protocol [START_REF]HIgh PErformance Radio Local Area Network (HIPERLAN) Type 1; Functional Specification[END_REF], a twin standard of 802.11a developed in the same period. In this protocol, the contention phase is bounded. The contention phase begins for each terminal by the emission of a burst whose length follows a truncated geometric distribution, and the terminal having the longest burst wins the right to transmit. If several terminals have the same longest burst, this results in a collision. A very similar protocol developed in the context of sensor networks has been called Sift [START_REF] Jamieson | Sift: A MAC protocol for event-driven wireless sensor networks[END_REF].

Another related protocol is the Contention Tree Algorithm [START_REF] Capetanakis | Tree algorithms for packet broadcast channels[END_REF][START_REF] Capetanakis | Generalized TDMA: the multi-accessing tree protocol[END_REF][START_REF] Janssen | Analysis of contention tree algorithms[END_REF], or CTA for short, also called Stack Algorithm [START_REF] Fayolle | Analysis of a stack algorithm for random multiple-access communication[END_REF][START_REF] Tsybakov | Free synchronous packet access in a broadcast channel with feedback[END_REF], which uses a tree to solve contention problems. Although we also use a tree, our protocol is completely different. This algorithm is basically based on feedback, that is evidence that a collision occurred. In the radio context, a feedback is expensive since it requires an acknowledgment packet. On the contrary, we rely on evidence of occupation, which is the fact that a silent terminal can detect that one or more terminals are signaling their presence.

In figure 1 we show how our protocol works. As in the standard 802.11 approach, the transmission begins with a period of sensing after the last emission (either an acknowledgment packet or a failed one, for instance due to collision). After observing a sufficiently long period with no emission (the DIFS period), the system operates a contention resolution protocol (CRP) that is supposed to select one station and only one. Then the packet is transmitted. If it is correctly received, the receiving station emits an ACK after a SIFS period. This is the end of a transmission period and a new transmission period can begin. If no ACK is listened to, the new transmission period begins immediately after the failed packet, and the stations start the CRP mechanism just after the DIFS period (recall that SIFS<DIFS). How does the CRP work? In our protocol the time is subdivided into timeslots that correspond to rounds of selection. At the beginning, each terminal emits a signal on the first time-slot with a certain probability. When the station does not emit, it listens to other signals, and, when it hears at least one other signal, it withdraws itself from the selection. This process -called round -is repeated k times, where k is a fixed integer, in order to leave only one remaining station at the end with the highest probability. This method is used in [START_REF] Abichar | CONTI: constant-time contention resolution for WLAN access[END_REF].

The present article generalizes this method, and present a mathematical framework to analyze its strengths and weaknesses. As a result, the improved method present a reduction of collision between 13.9% and 21.1%, resulting in a systematic gain of throughput. Improving CONTI by a few percents, the gain to the original 802.11b norm is as high as 31.4%, achieving the best known throughput for this family of protocols. Moreover, the new protocol keeps excellent fairness characteristics, as indicates the Jain index.

Our experiments advocate that six mini-slots of selections (as in [START_REF] Abichar | CONTI: constant-time contention resolution for WLAN access[END_REF]) is indeed the correct number when the amount of contending that this is indeed the correct number when the amount of contending stations is often between 10 and 100. Anyway, our analysis can be very easily extended to a different number than six mini-slots of selection, so that by adding a sufficient (and provably optimal) number of mini-slots, we can reduce the number of collisions to an arbitrarily low level. However, this does not necessarily increase the throughput since adding a mini-slot can be statistically more penalizing from the throughput point of view than retransmitting a packet in case of collision.

The key to obtain those results is in the choice of the probabilities with which a station will decide to keep silent or emit a signal in the CRP phase. Each station takes into account the fact that signals were emitted or not in the previous rounds to adapt its probability of emission.

In the following, we call try-bit and denote by r(t) the fact that at least one station has emitted a signal on the t th round.

In figure 2, we show how the choice of p -the probability that a station emits at a given round of selection -evolves in the course of the rounds of selection and in function of the previous try-bits chosen by the terminal. The first value (in the figure, p = 0.06) is unique for all the terminals. During the second round, if the terminal has emitted a signal at the first round (which we denote r(1) = 1), the protocol chooses the left part of the tree, and uses p 1 = 0.31 for the second round. If on the contrary the terminal did not emit, and did not hear any signal of other terminals (r(1) = 0), then the protocol chooses the right part of the tree and uses p 0 = 0.17 for the second round. If the terminal did not emit and actually listens to a signal from another station, it withdraws and leaves to other stations the right to send the following packet. As a result, the probability used in the second round is necessarily p r [START_REF]Higher-speed physical layer extension in the 2.4 GHz band[END_REF] . The realization of the second round will determine the value of r(2), and the third round will be governed by the probability p r(1)r(2) in the tree of figure 2. We plot the whole process in figure 3. Note that each station has a local try-bit R(t) at round t which equals r(t) as long as the station is not eliminated. We manage to find a tight approximation of the behavior of this protocol when the number of rounds k increases. More precisely, if we denote by q n the probability that n stations try to emit in the system, and if we introduce the function

INRIA r(2) r(3) 1 0 1 1 0 1 1 1 0 0 0 0 r (
f (x) = n≥1 q n x n , (1)
then we can show that tuning the p coefficients to this probability space, the lowest possible rate of collision 1 -ρ observed will be fairly approximated by

1 -ρ ≈ 1 0 f ′′ (t)dt 2 2 k+1 .
The article is organized as follows. A mathematical analysis in the next section investigates analytically the optimization issues raised by the problem of the choice of the p's, and gives some tight bounds for this question. The reader that desires to know the protocol without the mathematics can skip this section. A practical implementation of the mathematical ideas is given in section 3, allowing the computation of the values of the p's, which turns to give a new protocol for the WiFi/WiMax networks. Here again, this implementation is not necessary to implement our protocol, which is described in terms of parameters in table 2. Finally, our protocol is compared with other ones in section 4 where some numerical results are presented.

Mathematical analysis

In the following we denote m the number 2 k .

We denote by q n the probability that n stations try to emit in the system. We have necessarily q n ≥ 0 and n≥1 q n = 1. We introduce f , that we will call in the following the generating function of the distribution of stations, defined by:

f (x) = n≥1 q n x n .
We try now to characterize the distribution after the transmission on the first mini-slot. Let f 1 , respectively f 0 , be generating functions for the number of stations still in contention depending, respectively, on whether or not there was a transmission in the previous slot. If every station emits a signal with probability p, then the probability that n stations emit is given by:

P [n stations emit a signal] = i≥n ( i n )q i p n (1 -p) i-n .
Therefore, the distribution of the number of stations that emit is characterized by a function f 1 analog of f , defined by:

f 1 (x) = i≥1 P [i stations emit a signal]x i .

INRIA

and we deduce logically that:

f 1 (x) = n≥1 1≤i≤n ( n i )q n p i (1 -p) n-i x i = n≥1 q n [(px + 1 -p) n -(1 -p) n ] = f (px + 1 -p) -f (1 -p) .
Similarly, in the event where no signal has been emitted at the first round, we can deduce some information on the distribution of the number of stations. Indeed, the probability that n stations remain silent is (1 -p) i . Therefore if we write:

f 0 (x) = i≥0
P [i stations are present and remain silent]x i then we obtain:

f 0 (x) = i≥0 q i x i (1 -p) i = f ((1 -p)x).
And we see that at the end of the first round of selection, the distribution of the whole set of surviving station can be known by the mathematical function

f 0 + f 1 .
We can also note that the distribution in the case where the event r(0) occurs (either 0 or 1) is given by f r(0) /f r(0) [START_REF]Higher-speed physical layer extension in the 2.4 GHz band[END_REF]. By extension, if we note w a word in the alphabet {0, 1} and w0 (resp. w1) the same word to which the letter "0" (resp. "1") is added, and if we note p w and f w , respectively, the probability and generating function corresponding to step w, then (setting f ∅ = f ) the following inductive formulas hold:

f w1 (x) = f w (p w x + 1 -p w ) -f w (1 -p w ) f w0 (x) = f w ((1 -p w )x)
We observe that the probability of the event of the choice w = r(1) . . . r(t) is f w [START_REF]Higher-speed physical layer extension in the 2.4 GHz band[END_REF]. Given that the event w occurs, the distribution of the number of stations is characterized by f r(1)...r(k) /f r(1)...r(k) [START_REF]Higher-speed physical layer extension in the 2.4 GHz band[END_REF]. If we denote by l(w) the length of the word w, then the global distribution for all the event space after k rounds of selection is given by the sum of all the f w 's that correspond to an event after k rounds, (which is true if and only if l(w) = k), and therefore:

g(x) = w:l(w)=k f w (x).
The probability of success ρ of the rounds of selection is the probability that only one station remains. It is given by the first term of the integral series of g, that is g ′ (0). Therefore:

ρ = w:l(w)=k f ′ w (0).
In the following we evaluate the value of f ′ w (0). We therefore denote, for any word w in the alphabet {0, 1}, the quantity defined inductively by δ ∅ = 1 and

δ w0 = (1 -p w )δ w δ w1 = p w δ w (2)

Galtier

Then we note w a < w b if their corresponding binary values verify this inequality, and, using the convention y ∅ = 0, we set:

y w = v : l(v) = l(w) v < w δ v . (3)
Lemma 1 y w0 = y w .

Proof. It is easy to see that δ w1 + δ w0 = δ w . Therefore

y w0 = v : l(v) = l(w0) v < w0 δ v = u : l(u) = l(w) u < w δ u0 + δ u1 = u : l(u) = l(w) u < w δ u = y w Lemma 2 f ′ w (x) = δ w f ′ (y w + δ w x) for all x ∈ [0, 1]. Proof. Obviously δ ∅ f ′ (y ∅ + δ ∅ x) = f ′ (x) = f ′ ∅ .
Then we apply another induction on w. We suppose that the statement is established for w and show that it is true for w0 and w1. Indeed:

f ′ w0 (x) = (1 -p w )f ′ w ((1 -p w )x) = (1 -p w )δ w f ′ (y w + δ w (1 -p w )x) = δ w0 f ′ (y w0 + δ w0 x),
moreover, noticing from equation (3) that y w1 = y w0 + δ w0 , we have,

f ′ w1 (x) = p w f ′ w (p w x + 1 -p w ), = p w δ w f ′ (y w + δ w (p w x + 1 -p w )), = δ w1 f ′ (y w0 + δ w0 + δ w1 x), = δ w1 f ′ (y w1 + δ w1 x).
And therefore ρ = w:l(w)=k

δ w f ′ (y w ).
This formula exactly says that we aim at approximating the integral of f ′ by a Riemann integral. In other words, if we are given m -1 = 2 k -1 real numbers

z 1 , . . . , z m-1 in ]0, 1[, with 0 = z 0 < z 1 < . . . < z m-1 < z m = 1, then the quantity ρ = i∈{1,...,m} (z i -z i-1 )f ′ (z i-1 )
is the approximation of the integral of f ′ by a piece-wise constant function having m steps. This fact is illustrated by figure 4. In this figure we draw the f ′ function, which integral between 0 and 1 exactly equals 1 (since f (1)-f (0) = 1).

Points have been chosen to approximate this integral by a lower-bound piecewise constant function. The rate of collision of our protocol will be exactly equal to the area in gray on the figure, which is also the approximation default.

Therefore, if we have the best values of z 0 , . . . , z m for this integral, it is sufficient to set y w = z #(w) , where #(w) is the numerical binary value that is represented by w. The reader can verify that this is obtained by setting:

p w = z #(w)2 k-l(w) +2 k-l(w) -z #(w)2 k-l(w) +2 k-l(w)-1 z #(w)2 k-l(w) +2 k-l(w) -z #(w)2 k-l(w) .
Proposition 1 For all protocol of selection governed by a series of selective rounds as indicated in figure 2, we can associate a series of m + 1 real numbers z 0 , . . . , z m in [0, 1], with 0 = z 0 < z 1 < . . . < z m-1 < z m = 1, such as the probability of success (non-collision) of the protocol is given by: ρ = i∈{1,...,m}

(z i -z i-1 )f ′ (z i-1 ). ( 4
)
In this case, the probabilities chosen to operate the different rounds of selection are given by:

p w = z #(w)2 k-l(w) +2 k-l(w) -z #(w)2 k-l(w) +2 k-l(w)-1 z #(w)2 k-l(w) +2 k-l(w) -z #(w)2 k-l(w) . (5)
Inversely, to all family of real numbers z 0 , . . . , z m verifying

0 = z 0 < z 1 < . . . < z m-1 < z m = 1,
RR n 6396

Galtier

we can associate a protocol of selection whose probability of success and probabilities are given by equations ( 4) and ( 5).

So we are now left with the problem of finding optimal values for z. Analyzing a little further the value of ρ, we obtain the formula:

1 -ρ = 1 0 f ′ (t)dt - i∈{1,...,m} (z i -z i-1 )f ′ (z i-1 ) = i∈{1,...,m} f (z i ) -f (z i-1 ) -(z i -z i-1 )f ′ (z i-1 ).
Three lemmas will allow us to analyze it. Lemma 3 Let be the piece-wise constant function defined by

: x → 1 m(z i -z i-1 ) for x ∈ [z i-1 ; z i [. ( 6
)
We have 0 1 (t)dt = 1 and

1 2m 1 0 f ′′ (t) (t) dt = i∈{1,...,m} zi zi-1 z i -z i-1 2 f ′′ (t)dt = i∈{1,...,m} (z i -z i-1 )(f ′ (z i ) -f ′ (z i-1 )) 2 .
Moreover,

1 -ρ - 1 2m 1 0 f ′′ (t) (t) dt ≥ - 1 12
i∈{1,...,m}

(z i -z i-1 ) 3 f ′′′ (z i )
and

1 -ρ - 1 2m 1 0 f ′′ (t) (t) dt ≤ - 1 12
i∈{1,...,m}

(z i -z i-1 ) 3 f ′′′ (z i-1 ).
Proof.

1 -ρ - 1 2m 1 0 f ′′ (t) (t) dt = i∈{1,...,m} f (z i ) -f (z i-1 ) -(z i -z i-1 )f ′ (z i-1 ) -(zi-zi-1)(f ′ (zi)-f ′ (zi-1)) 2 = i∈{1,...,m} f (z i ) -f (z i-1 ) -(z i -z i-1 ) f ′ (zi)+f ′ (zi-1) 2 .
But f is an harmonic function with positive coefficients, and radius of convergence from 0 at least 1, therefore:

f (z i ) = j≥0 (z i -z i-1 ) j j! f (j) (z i-1 ) f ′ (z i ) = j≥1 (z i -z i-1 ) j-1 (j -1)! f (j) (z i-1 )
INRIA and we have

f (z i ) -f (z i-1 ) -zi-zi-1 2 (f ′ (z i ) + f ′ (z i-1 )) = (z i -z i-1 ) 3 j≥3 (z i -z i-1 ) j-3 1 j! -1 2(j-1)! × f (j) (z i-1 ), = -(z i -z i-1 ) 3 j≥3 (z i -z i-1 ) j-3 1 (j-1)! 1 2 -1 j × f (j) (z i-1 ).
We note that all the derivatives of f are positive, and therefore all the term of this series are non-positive. Hence the second inequality. Moreover,

j≥3 (z i -z i-1 ) j-3 1 2(j -1)! - 1 j! f (j) (z i-1 ) = j≥3 (z i -z i-1 ) j-3 j -2 2(j!) f (j) (z i-1 ) ≤ j≥3 (z i -z i-1 ) j-3 1 12(j -3)! f (j) (z i-1 ) ≤ 1 12 f ′′′ (z i )
Lemma 4 Suppose f ′′ (0) > 0. Let the real numbers z 0 , . . . , z m in [0, 1], with 0 = z 0 < z 1 < . . . < z m-1 < z m = 1, that achieve the maximum value of ρ = i∈{1,...,m} (z i -z i-1 )f ′ (z i-1 ). Then we have: i∈{1,...,m}

(z i -z i-1 ) 2 ≤ 2 mf ′′ (0)
,

and ∀i ∈ {1, . . . , m} z i -z i-1 ≤ 2 f ′′ (0) 1 √ m .
Proof. We have:

1 -ρ = i∈{1,...,m} f (z i ) -f (z i-1 ) -(z i -z i-1 )f ′ (z i-1 ),
and by Taylor expansion, there

exists b i-1 in the interval ]z i-1 ; z i [ such that f (z i ) -f (z i-1 ) = (z i -z i-1 )f ′ (z i-1 ) + (z i -z i-1 ) 2 2 f ′′ (b i-1 ). Therefore 1 -ρ = i∈{1,...,m} (z i -z i-1 ) 2 2 f ′′ (b i-1 ).
Since ρ is a maximum value for all the choices of z i , necessarily 1 -ρ ≤ 1/m (indeed, if we take z i = i/m, we obtain a solution verifying 1 -ρ ≤ 1/m). Therefore z i -z i-1 tends to 0 when m tends to infinity. The previous inequality taken term by term gives

z i -z i-1 ≤ 2 f ′′ (0) 1 √ m ,
and since all the f ′′ (b i ) are bounded below by f ′′ (0), we obtain i∈{1,...,m}

(z i -z i-1 ) 2 ≤ 2 mf ′′ (0)
.

Lemma 5 If f ′′ is piece-wise continuous, the minimum of the value

1 0 f ′′ (t)
h(t) dt on the functions h piece-wise continuous and verifying

1 0 h(t)dt = 1 is obtained by h * : x → √ f ′′ (x) 1 0 √ f ′′ (t)dt
and therefore equals

1 0 f ′′ (t)dt 2 .
The proof of lemma 5 is easily obtained if f ′′ is a piecewise constant-function, and we use uniform convergence of piecewise constant-functions to piece-wise continuous functions.

Proposition 2 If f ′′ (0) > 0, whatever the series of m values of z . used, we have:

1 -ρ ≥ 1 0 f ′′ (t)dt 2 2m - f ′′ (1) 3 √ 2f ′′ (0) 3/2 1 m 3/2 .
Proof. By lemma (3) we have:

1 -ρ ≥ 1 2m 1 0 f ′′ (t) (t) dt - 1 12
i∈{1,...,m}

(z i -z i-1 ) 3 f ′′′ (z i ).
Then applying lemma (5) for = h gives

1 -ρ ≥ 1 2m 1 0 f ′′ (t) (t) dt - 1 12
i∈{1,...,m}

(z i -z i-1 ) 3 f ′′′ (z i ).
Then the second inequality of lemma (4) gives:

1 -ρ ≥ 1 2m 1 0 f ′′ (t) (t) dt - 1 12 √ m 2 f ′′ (0) i∈{1,...,m} (z i -z i-1 ) 2 f ′′′ (z i ). Since f ′′′ (z i ) ≤ f ′′′ (0), it gives: 1 -ρ ≥ 1 2m 1 0 f ′′ (t) (t) dt - f ′′′ (0) 12 √ m 2 f ′′ (0) i∈{1,...,m} (z i -z i-1 ) 2 .

INRIA

Finally the first inequality of lemma (4) gives:

1 -ρ ≥ 1 2m 1 0 f ′′ (t) (t) dt - f ′′′ (0) 12 √ m 2 f ′′ (0) 2 mf ′′ (0)
.

Hence the result.

This result clearly shows what is the maximum efficiency of the protocol whatever the chosen values of probabilities, and therefore the maximum we can asymptotically expect, that is

1 -ρ ≈ 1 0 f ′′ (t)dt 2 2m
.

The strategy of approaching h by a piecewise constant-function therefore gives a result asymptotically optimal. We note also that as the number of round increases, the collision rates systematically decreases, and this factor of division converges to 2 as the number of rounds increases. It means that we can reduce the collision rate by an arbitrary low level by using a reasonably small number of additional rounds. For applications that suffer from retransmissions (and jitter) this property can have a considerable impact.

However, further experiments showed, that in the 802.11b framework where the jitter was not important and the throughput was to be optimized, the good number of mini-slots to use was 6.

Some more results on the approximation of a function by Riemann integrals are worth to be noted. We are interested in the following problem:

Problem 1 Let ϕ a non-decreasing function from [0; 1] to [0; 1], with ϕ(0) = 0 and ϕ(1) = 1. We are looking for a piecewise constant function ψ, with m + 1 pieces, such that

   ∀z ∈ [0; 1] ψ(z) ≤ ϕ(z), 1 0 (ϕ(z) -ψ(z)) dz is minimum.
Clearly, this problem is the optimization formulation of the preceding issue when, for z ∈

[0; 1], ϕ(z) = f ′ (z)/f ′ (1). Proposition 3 If z → zϕ(z) is convex, m = 1,
and ϕ continuously derivable, then the minimum for g is reached with a step z verifying

(1 -z)ϕ ′ (z) = ϕ(z). Proof. If the step is z ∈ [0, 1], then 1 0 (ϕ(t) -ψ(t))dt = 1 0 ϕ(t)dt -(1 -z)ϕ(z).
Note that necessarily there is some z * ∈]0; 1[ such that ϕ(z * ) > 0 and this particular z * does better than z = 0 or z = 1. The best z necessarily then verifies d dz (1 -z)ϕ(z) = 0.

Galtier

Proposition 4 For a fixed m, for any ϕ function, there is a ψ function that reaches the minimum. This minimum will be noted c m .

Proof. L Set c m = inf ψ piece wise constant with m + 1 pieces, and ψ ≤ ϕ

(ϕ(t) -ψ(t))dt.
Let ψ p be a series of piece-wise constant functions, with m + 1 pieces, such that

lim p→∞ 1 O (ϕ(t) -ψ p (t))dt = c m . Let z (1) p ≤ . . . ≤ z (m) p
be the points where g p is not continuous. Since [0; 1] is compact, let us extract a converging series z ). Let ε > 0 be a real number. There is a η > 0 such that for all i ∈ {1, . . . , m}, |z -z

σ(p) , p ∈ IN is converging. Let us then note z (i) * = lim p→∞ z (i) σ(p) , for i ∈ {1, . . . , m}, z (0) * = 0, z m}, z (i)
(i) * | < η implies |ϕ(z) -ϕ(z (i) * )| < ε. If η > ε, set η = ε. Then there is a P ∈ IN such that p ≥ P implies |z (i) * -z (i) σ(p) | ≤ η.
We see that for each i ∈ {1, . . . , m}, ψ * (z

(i) * ) = ϕ(z (i) * ) ≥ ϕ(z (i) p ) -ε = ψ p (z (i) p ) -ε
for p ≥ P , and therefore

1 0 (ψ * (t) -ψ p (t)) dt ≥ -ε -mη ≥ -(m + 1)ε.
This is true for all ε > 0, and so

1 0 ψ * (t)dt ≥ c m .
Proposition 5 Let A the function from IR m to IR given by

A(z 1 , . . . , z m ) = i=m i=2 (z i -z i-1 )ϕ(z i-1 ) + (1 -z m )ϕ(z m ). Then max (z1,...,zm)∈[0;1] m A(z 1 , . . . , z m ) = c m .

INRIA

Fixing a scenario

Approximating the integral Choice of the values of p

≤ . . . ≤ z m . Note that if α < β, then (β -α)ϕ(α) + (1 -β)ϕ(β) > (α -β)ϕ(β) + (1 -α)ϕ(α).

It follows that

A(z 1 , . . . , z i-1 , α, β, z i+1 , . . . , z m ) ≥ A(z 1 , . . . , z i-1 , β, α, z i+1 , . . . , z m ).

Therefore, ordering the arguments of A maximizes its results (use for instance bubble sort).

Those results open tools for promising optimization.

Practical implementation

In figure 5, we show the basic principles of an optimization based on our mathematical analysis. A preliminary step consists in fixing a scenario, that is the probabilities that a given number of stations appears. For instance we set as previously P [Number of emitting stations = n] = q n .

And we consider

f (x) = n≥1 q n x n .
Then we have an ĥ function defined by ĥ(x) = f ′′ (x) ( ĥ is the equivalent of h * in the previous section, but without the normalization we take a number M largely greater than m = 2 k and we compute H as follows

     H(0) = 0 H(i + 1) = H(i) + ĥ i+1/2 M for i ∈ {0, . . . , M -1}
and we define z j for j ∈ {0, . . . , m} by

         z 0 = 0, z j = 1 M min i : H(i) H(M) ≥ j m for j ∈ {1, . . . , m -1}, z m = 1.

Finally we set

p w = z #(w)2 k-l(w) +2 k-l(w)-1 -z #(w)2 k-l(w) +2 k-l(w) z #(w)2 k-l(w) -z #(w)2 k-l(w) +2 k-l(w)
where w is a word in the {0, 1} alphabet, #(w) represents the numerical binary value denoted by w and l(w) the length of the word w.

Numerical results

In the first part of this section, we compare the collision rate of our method to that of CONTI [START_REF] Abichar | CONTI: constant-time contention resolution for WLAN access[END_REF]. We show that for some parameter our collision rate is always favorable, and therefore systematically results in a better performance to CONTI. Along with the native 802.11b protocol [START_REF]Higher-speed physical layer extension in the 2.4 GHz band[END_REF], we compare to two high performing protocols, the Idle Sense one [START_REF] Heuse | Idle sense: An optimal access method for high throughput and fairness in rate diverse wireless LANs[END_REF] and the additive congestion window increase /decrease protocol [START_REF] Galtier | Optimizing the IEEE 802.11b performance using slow congestion window decrease[END_REF]. Finally we concentrate on fairness issues for these different schemes, based on the Jain index [START_REF] Jain | A quantitative measure of fairness and discrimination for ressource allocation in shared computer system[END_REF].

A tuning of the probabilities

An essential step is to set the values of q n . One idea is to set a favorite interval of operation, say {2, . . . , N }, and fix, for n ∈ {2, . . . , N }, and some α ∈ [0, 1],

q n = n -α i=N i=2 i -α . ( 7
)
This distribution allows to take into account in a balanced way loaded or non loaded networks. In figure 6, we show different probability curves obtained for N = 100, and various values of α.

In order to see the advantage of our optimization techniques, we compare our results to that performed by CONTI [START_REF] Abichar | CONTI: constant-time contention resolution for WLAN access[END_REF]. In our context, one can simply view CONTI as a special assignment of the values of p w that only depends on the length w. For completeness, we recall the values taken in table 1.

Globally, we can see that these functions perform remarkably well compared to CONTI. Whereas the latter has a collision rate between 4.5 and 6.5%, with a maximum for the 4.5% rate, our algorithms fall often under 4%. The value α = 0 allows to give equal weights to all the events. In practice, we see that this global optimization tends to pay more attention to the cases where more stations are present (50 to 100) at the expense of more collisions when two to five stations are present in the system. On the contrary α = 1 performs well when a small number of stations are present at the expense of lesser performance over 60 stations. A good compromise seems to be α = 0.7 which varies between 3.9% and 6.3% with an average improvement to CONTI of 13.9% in collision rate. For the cases α = 0 and α = 0.5, the improvement -although in some cases negative -is on average even better, respectively 21.1% and 17.8%. In the following we will set α = 0.7. For sake of completeness, we give in figure 2 our probability values so that the reader can replicate our experiments without further considerations on choosing α.

Comparative bandwidth

We set the general parameters as follows, according to the IEEE 802.11b norm. The SIFS and DIFS times are set to 10µs and 50µs respectively. The time-slot interval for CRP is set to 20µs. The size of the payload of a packet is set to 1500 bytes. A packet (either regular or ACK) contains a physical header of 96µs. On top of that, the MAC head and tail represent in all 19 bytes in a regular packet, and 14 bytes in an ACK one, that are transmitted at the maximum speed, that is 11Mbit/s. We now further describe the specificity of each protocol.

The 802.11b norm [START_REF]Higher-speed physical layer extension in the 2.4 GHz band[END_REF]. Each station has a CW parameter. At the beginning, a station chooses a κ -called back-off counter -randomly in the interval {0, . . . , CW -1}. If κ = 0, the transmission begins immediately. Otherwise, if an empty time-slot is observed, κ is decreased by one. At the end of a transmission, the value of CW itself is updated to CW M in if the transmission was successful, and to min(CW M ax, 2 * CW ) if a collision occurred. We have set as in the norm CW M in = 32 and CW M ax = 1024.

The Idle Sense method [START_REF] Heuse | Idle sense: An optimal access method for high throughput and fairness in rate diverse wireless LANs[END_REF]. At the end of a transmission, successful or not, the terminal stores the number of idle time-slots before its transmission. After 5 transmissions, the terminal computes the average waited time-slots. If this number is inferior to 5.68, the congestion window is updated by CW = min(CW M ax, CW * 1.2).

Otherwise, the new CW is given by:

CW = max(CW M in, 2 * CW/(2 + 1e -3 * CW )).
The additive congestion window increase/decrease [START_REF] Galtier | Optimizing the IEEE 802.11b performance using slow congestion window decrease[END_REF]. At the end of an unsuccessful transmission, CW is set to min(CW max, CW +32).

If the transmission is successful, the station flips a biased coin, and with probability 0.1809 updates CW by CW := max(CW min, CW -32) The CONTI method [START_REF] Abichar | CONTI: constant-time contention resolution for WLAN access[END_REF]. At each step a CRP of six time-slots is applied with the probabilities given by table 1. The surviving stations transmit.

Our method -MAC in fixed congestion window. We apply a CRP of six time-slots. We have used the probabilities of table 2.

Our results are presented in figure 7. In this figure, we plot for various numbers of stations the total throughput observed in the system. We clearly see that all the proposed methods improve significantly the original IEEE 802.11b mechanism. The methods based on adaptive tuning of the congestion window, namely [START_REF] Heuse | Idle sense: An optimal access method for high throughput and fairness in rate diverse wireless LANs[END_REF][START_REF] Galtier | Optimizing the IEEE 802.11b performance using slow congestion window decrease[END_REF], achieve quite close performances. The CONTI method performs very well. Our method gives the best performance in all cases, and has a total improvement as far as 31.4% for 100 stations to the original norm.

Fairness considerations

In this part we take into consideration the fairness issues. For each of the experiments, we have observed a series of 10000 successful transmission, and assigned to each station i the number x i of packets it managed to transmit. In order to evaluate the fairness, we use the Jain index [START_REF] Jain | A quantitative measure of fairness and discrimination for ressource allocation in shared computer system[END_REF], defined by:

Index = ( x i ) 2 n x 2 i .
This index is always between 0 and 1, and closer to 1 if the system is more fair. Our results are given in figure 8. Note that our method is equivalent to INRIA the CONTI method from the fairness point of view. The results plotted are averages obtained after a series of 10 tests. The results show different behaviors. We observe as in [START_REF] Heuse | Idle sense: An optimal access method for high throughput and fairness in rate diverse wireless LANs[END_REF] that slow congestion window methods tend to generate some unfairness. We also notice that new method hardly improve the quality of the original IEEE 802.11b norm. Note, anyway, that our method achieves the best fairness performance.

Conclusion

In this paper we have demonstrated the efficiency of MAC protocols with constant congestion window size in the wireless context. We have determined their limits in terms of avoidance of collision, and shown that they perform very well in terms of fairness. The tuning that we propose achieves the best throughput performance in the 802.11b framework to our knowledge. This advocate for a more extensive use of these methods, and the building of devices including this new access control mode. This is not necessarily a simple task, since the proposed scheme is not compatible with the previous ones excepted CONTI, but is a promising way to achieve better wireless networks.

Figure 1 :

 1 Figure 1: A view of the general frame structure.

Figure 2 :

 2 Figure 2: Choice of the values of p in the course of the rounds of selection

  R(t)=0]=p(R(1),...,R(t-1)) Drawing of the value R(t) in {0,1} Listening to other signals t:=t+1 R(t)=0 t=k ?

Figure 3 :

 3 Figure 3: Global diagram for the rounds of selection in a terminal.

Figure 4 :

 4 Figure 4: Interpretation of the collision rate in terms of Riemann integral.

( 1 )

 1 σ1(p) (that is, σ 1 is an increasing function from IN to IN such that the series z

( 1 )

 1 σ1(p) , p ∈ IN is converging), and σ 2 such that z

( 2 )

 2 σ2(σ1(p)) is converging, and so on to σ m such that z (m) σmo...oσ1(p) is converging. Setting σ = σ m o . . . oσ 1 we have that σ is increasing from IN to IN and for each i ∈ {1, . . . ,

* = 1 ,

 1 and ψ * such that for i ∈ {1, . . . , m + 1}, and z ∈ [z (i-1) * , z (i) * [, ψ * (z) = ϕ(z (i-1) *

Figure 5 :

 5 Figure 5: Strategies of optimization of the values of p

1 0

 1 h * (t)dt = 1). And

Figure 6 :

 6 Figure 6: Various collision rates obtained with our algorithm compared to CONTI.

Figure 7 :

 7 Figure 7: Comparative total throughput for different protocols.

Figure 8 :

 8 Figure 8: Comparative Jain index for different protocols.

Table 1 :

 1 Values taken by CONTI.

Table 2 :

 2 00111 0.475313 p 000 0.388521 p 01000 0.476041 p 001 0.398651 p 01001 0.476681 p 010 0.407585 p 01010 0.477124 p 011 0.416295 p 01011 0.477647 p 100 0.429211 p 01100 0.477976 p 101 0.444548 p 01101 0.478795 p 110 0.457931 p 01110 0.478203 p 111 0.465291 p 01111 0.48056 p 0000 0.442201 p 10000 0.479927 p 0001 0.444984 p 10001 0.480932 p 0010 0.447669 p 10010 0.481663 p 0011 0.450083 p 10011 0.48324 p 0100 0.452293 p 10100 0.484177 p 0101 0.454545 p 10101 0.485714 p 0110 0.456444 p 10110 0.486056 p 0111 0.459286 p 10111 0.486726 p 1000 0.462745 p 11000 0.490291 p 1001 0.466754 p 11001 0.491979 p 1010 0.469799 p 11010 0.491329 p 1011 0.473795 p 11011 0.490566 p 1100 0.475827 p 11100 0.489796 p 1101 0.478916 p 11101 0.492754 p 1110 0.484211 p 11110 0.492188 p 1111 0.483871 p 11111 0.491667 Values obtained for the p • 's for α = 0.7 and N = 100.

	Galtier

RR n 6396

Probability that a non-eliminated station emits a signal at the round l(w) + 1, given that the preceding try-bits where r(1), . . . , r(l(w)) = w. f

Generating function of q . , see equation ( Parameter to set the values of q • , see equation [START_REF] Cali | Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit[END_REF].

In the experiments, amount of packets that an individual station has emitted.


Young Adult (20-30 yrs) Older Adult (> 30 yrs) Frequency of Canines with Linear Enamel Hypoplasia

Linear Enamel Hypoplasia vs Age at Death in Natufian Prehistoric

Hunter-Gatherers

BACKGROUND: NATUFIAN BIOARCHAEOLOGY

The rapid increase in burial of the dead, from the earlier Epipaleolithic (ca. 19-16 kya), makes the Natufian archaeological sample the largest known Pleistocene-age skeletal series from a single regional archaeological culture. Linked to the rise of sedentism and foraging intensification, southern Levantine Natufian populations faced diverse biocultural changes.

Much previous work has focused on comparisons between Natufian hunter-gatherer skeletal samples and later Prepottery Neolithic agricultural ones. Populations from both periods were generally healthy (Eshed et al. 2004b(Eshed et al. , 2010;;cf. Bocquentin 2003). Eshed et al. (2004a) suggest that adult mortality declined from the Natufian to Prepottery Neolithic periods. Alternatively, with the shift toward agriculture and village-based co-residence patterns, Prepottery Neolithic funerary recruitment may have become more biased toward interring male elders. In any case, the apparent decline in adult mortality is at odds with the data summarized by Bocquet-Appel (2008) and Guerrero et al. (2008). Relative juvenile mortality (5-19 years at death) may have risen in the Prepottery Neolithic period, possibly indicating higher population growth. We emphasize that Early and Late Natufian mobility, settlement, burial practices, and-very likely-health and demography varied substantially between sites and over the millennia. It is necessary to proceed cautiously in teasing apart signals of population biological change from those of cultural change in funerary recruitment.

AIM, MATERIALS, AND METHODS

In this study we carry out new analyses of data from the comprehensive database compiled by Bocquentin

SEDENTISM AND MORTUARY RITUAL IN THE FINAL PLEISTOCENE

BACKGROUND: INTENSIFIED FORAGING

Early Natufian hamlet settlement involved economic intensification. Human hunting depressed big game populations, as fastescaping small game were increasingly targeted (Munro 2004). Grain-processing intensification followed in the Late Natufian period (Dubreuil 2004).

INTRODUCTION

In the Fertile Crescent of Near East, Pleistocene mobile hunting and gathering gradually gave way to early Holocene agro-pastoral food-management systems. This study presents a new analysis of linear enamel hypoplasias (LEH) in the region's largest Final Pleistocene hunter-gatherer skeletal series, from the Natufian archaeological culture of the southern Levant (ca. 15,000-12,000 BP). We investigate whether adults experiencing osteologically recognizable early-life stress faced greater mortality risk in the context of economic intensification and reducing residential mobility.

RESULTS

A conservative multiple-indicator approach to age and sex estimation (Bocquentin 2003) confirms the importance of analyzing taphonomically comparable categories. Thus, the decline in proportion of juveniles (5-19 yrs) from the Early to Late Natufian periods might be a taphonomic artifact of shifting mortuary practices, toward more common secondary burial in the Late/Final Natufian period. Studying LEH occurrence on the estimated-age individuals-interred in similar ways in the Early and Late Natufian periods-we can test whether early-life stress associated with higher adult mortality risk.

The LEH-age-assocation results consistently suggest that early-life stress significantly shaped mortality risk under Early Natufian foraging intensification and sedentary settlement. Developmental-stress effects on adult mortality appear to have ameliorated during the Late / Final Natufian period. The canine MNI sample from all Natufian individuals (n = 87; Fisher's Exact Test p-value = 0.02) confirms this association. A general indicator of early-life stress, LEH is more prevalent in adults dying by 30 years. LEH is relatively rare in adults surviving past 30. Considered by period-Early versus Late/Final-it is only the Early Natufian sample for which the LEH-mortality association is significant.

Natufian canines exhibit disproportionately high susceptibility to LEH, relative to incisors (Bocquentin 2003;cf. Goodman & Armelagos 1985). The total canine NISP sample (n = 315; Chi-Square p-value = 0.00001) shows a highly significant association between age at death and LEH formation.

1

  (2003), based on observations of 458 individuals from Early and Late Natufian burial features. Taking a conservative taphonomic approach, we address a new question in the bioarchaeology of populations under biocultural transition in Near Eastern prehistory:Ø Did early-life stress shape heterogeneity in adult mortality in the Natufian transition to sedentism and foraging intensification?We analyze LEH occurrences scored in 315 canines from 138 individuals interred in primary and secondary burial features across seven sites. The sample spans the Early (ca. 15,000-13,000 cal BP) and Late/Final Natufian (ca. 13,000-11,700 cal BP). Associated dental and skeletal data supported age-at-death estimates into juvenile, young adult (ca. < 30 yrs), and old adult (ca. > 30 years) categories (Bocquentin 2003Division of History & Social Science, Oxford College of Emory University, astutz@emory.edu 2 Department of Anthropology, Emory University 3 UMR 7041 du CNRS, ArScAn, Equipe Ethnologie Préhistorique, fanny.bocquentin@cnrs.fr

  Natufian sites with burials included in this study. Base map courtesy Google Earth (map data from SIO, NOAA, US Navy, NGA, GEBCO from Landsat Imagery)

health improve in the overall Late/Final Natufian population? Or… Ø Were improved health and longevity restricted to higher status lineages/alliances? Early Natufian Lower Canines n = 84; Fisher's Exact Test p- value = 0.02 Late Natufian Lower Canines Late Natufian Upper Canines Early Natufian Upper Canines n = 77; Fisher's Exact Test p- value = 0.01 0 0.1 0.2 0.3 0.4

  Young adult mortality is disproportionately associated with linear enamel hypoplasias, especially on the lower canines. The LEH-age-assocation results clarify some of the possible biocultural impacts and factors shaping the long-term emergence of agriculture:

	Frequency of Canines with Linear Enamel Hypoplasia	0.5 0.6 0.7 0.8 0.9
		Juvenile (5-19 yrs)	Young Adult (20-30 yrs)	Older Adult (> 30 yrs)

Patterns in the figures above are belied by a significant increase in deposition of fragmentary skeletons-in secondary burials-during the Late/Final Natufian period. Later Natufian samples have more uncertain-aged and sexed adults (thus, not in the figures). For determinate versus indeterminate sex estimation, chi-square pvalue = 0.01; for age estimation, p-value = 0.05. Sex and age estimation analysis described in

Bocquentin (2003)

.

ACKNOWLEDGMENTS CONCLUSION

Ø Did

Linear Enamel Hypoplasia vs Age at Death in Natufian Prehistoric Hunter-Gatherers Total Natufian Lower Canines Total Natufian Upper Canines

	TOTAL NISP	Juvenile (5-19 yrs)	Young Adult (20-30 yrs)	Older Adult (> 30 yrs)
	LEH Present	37	51	36
	LEH Absent	55	36	100


Manuel Yguel

Olivier Aycard

Christian Laugier Ε-

Update Policy of Dense Maps: efficient algorithms and sparse representation

Introduction and Previous Work

Providing a robot with a fully detailed map is one appealing key for the Simultaneous Localisation and Mapping (SLAM) problem. It gives the robot a lot of hints to solve either the data association or the localisation problem itself. The more details are in the map, the more chances are that different places may appear differently, solving ambiguities. The more landmarks are used, the more accurate are the algorithms that solve the localisation problem since in a least square sense an approximation of the solution is more precise. Last, it helps a lot in the presence of a few dynamic objects because these moving parts of the environment remain marginal in the amount of data used to model the map and can thus be filtered out. For instance, the moving objects can be detected or cancelled in the localisation procedure by robust techniques using Monte-Carlo algorithms [START_REF] Khan | Mcmc data association and sparse factorization updating for real time multitarget tracking with merged and multiple measurements[END_REF] or RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF]. The environment models that provide such possibilities are named dense maps. To build such a representation from range-finders there exist in the literature a lot of propositions: using the point clouds generated by the sensors [START_REF] Cole | Using laser range data for 3d slam in outdoor environments[END_REF], using grid-based representation [START_REF] Elfes | Occupancy grids: a probabilistic framework for robot perception and navigation[END_REF], [START_REF] Grisetti | Improving grid-based slam with rao-blackwellized particle filters by adaptive proposals and selective resampling[END_REF] or using more geometrical modelling involving feature fitting such as lines or planes [START_REF] Vandorpe | Exact dynamic map building for a mobile robot using geometrical primitives produced by a 2d range finder[END_REF], [START_REF] Triebel | Multi-level surface maps for outdoor terrain mapping and loop closing[END_REF]. From our point of view the second kind of representation using occupancy grid (OG) is of particular interest since it offers a strong mathematical framework for updates or merges of maps even if the measurements or the map disagree. For example this property is useful if a part of the map, that was not observed, had changed a lot like the streets of a city where the cars park and go. However as their name suggests it dense maps comes with a memory burden. For instance raw scan records of 361 points of a laser range-finder operating at 50Hz produce in 3 hours almost 195 millions of points which make 780Mb of data and a grid-based representation that use cubic cells with a side of 5cm needs 3.6 billions of cells to cover an area of 3km 2 which make 28.8Gb for an (OG). Naturally this is a hard limitation for such maps and that is why the design of sparse representations is very important. In this paper we present a review of update methods for grid-based maps like OGs under the requirement of a sparse representation emphasizing the pros and the cons then we propose a new update policy that is particularly appropriate to the sparse condition. In a first part grid based representations and update are presented. In a second part update policies are studied. Then in the third section is discussed how the new update policy modified the hierarchical algorithms for sparse OGs presented in our previous works. Finally results are presented in the last section.

Grid-based maps

In this section the process of information fusion in grid-based map is described.

Occupancy grids

Grid-based representations were first introduced by Elfes and Moravec with the occupancy grids (OGs): in each cell of the grid a probabilistic estimation is maintained for the presence of an obstacle. This representation is closely related to range sensors for which sensor models exists that take into account measurement uncertainty to update the map.

Sensor model

• Z a random variable 1 for the sensor range measurements in the set Z .

• O x,y ∈ O ≡ {occ, emp}. O x,y is the state of the cell (x, y), where (x, y) ∈ Z 2 . Z 2 is the set of indexes of all the cells in the monitored area. • the OGs needs three probability distribution to be defined: the a priori map occupancy P 0 (O x,y ) and the two sensor models: P(Z|[O x,y = occ]) and P(Z|[O x,y = emp]). The two last modelling how uncertain a measurement is with respect to the obstacle location (fig. 1(a)). (a) Update of a 2D OG after a sensor reading, initially each cell occupancy was unknown, i.e. 0.5 probability. The sensor beam has an aperture of 7 degrees. The sensor is positioned in (0,0). It thus is the just adding in each cell the value of the log-ratio of the two sensor models. (b) A range-finder beam. The range finder is located at Ω and its field of view is surrounded by red boundaries. It defines the three kind of cell types, unknown cells (U set) in white, empty cells (E set) in light blue and occupied cells: the one close to an obstacle marked with a "D" (B set).

Log-ratio form of occupancy update

As the occupancy is a binary variable, a quotient between the likelihoods of the two states of the variable is sufficient to describe the binary distribution. The new representation used is:

odd(O x,y ) = log p([O x,y = occ]) p([O x,y = emp]) (1.1)
In the Bayesian update of the occupancy, the quotient makes the marginalization term disappear and thanks to a logarithm transformation, sums are sufficient for the inference:

log p(occ|z) p(emp|z) = log p(occ) p(emp) + log p(z|occ) p(z|emp) = odd 0 + odd(z) (1.2)
where odd 0 named the initial estimation of the cell occupancy is log-ratio.

Reflection probability maps

Reflection probability maps were described by Burgard and instead of the occupancy probability the map measures the probability of a reflection per grid cell and have the advantage of not requiring an explicit sensor model. For each cell two numbers are stored: the number of times a beam has traversed the cell (♯misses) and number of times a beam has ended in the cell (♯hits). Then the probability of reflection is estimated as:

p(O x,y ) = ♯hits ♯hits + ♯misses (1.3)

Normal transforms

The normal transforms store in addition of one of the previous kind of occupancy information the mean and the standard deviation of all the end-points of the beams that fall into the cell2 . This representation was proposed by Biber in [START_REF] Biber | The normal distributions transform: A new approach to laser scan matching[END_REF] and as a nice feature it reduces the problem of space discretization induced by the grid which greatly improved the localisation accuracy for instance.

Update Policies

In this section is studied the effect of long term sensor fusion on grid-based maps. In the first subsection the effect of the simple sensor fusion updates of the previous section are described highlighting the drawbacks. Then the usual max and clamping policies used to counter these drawbacks are reviewed. Last we present the policy we used along with the occupancy a priory that gives the best memory saving.

No policy

When updates are performed using just the equation of the previous section, the map obtained suffers from two drawbacks: it is overconfident and it is highly irregular (fig. 2(a), fig. 3(a)). If carried in log-ratio space these two problems are evident through the unbounded sums along fusion updates. The number of observations required to change the state of a static cell is equal to the number of observations in the past that have defined this state. And if the robot have stayed a long time observing a part of the map, it will make a long time to change its state which is annoying since obstacles like car can be parked a long time before going quickly. This issue is called the map overconfidence problem. It can be understood as a memory problem since the map remember all agreeing observations. In particular as the vantage points of the sensor observations changes, all the minor changes in the pose of the sensor let a print in the map leading to very irregular representation. The term irregular means, here, that the function representing the map is far from a continuous function. And as there is no way to predict the patterns that appear in the map there is no way neither to compress the map efficiently. However this update as a clear advantage: all the information are used to estimate the static parts of the map which made the location of the wall for instance very accurate (fig. 3(a)). It is worth notice that all these drawbacks and advantages are valid for all the grid-based representations.

Max policy

A solution, usually use because it is conservative ( [START_REF] Payeur | Probabilistic octree modeling of a 3-d dynamic environment[END_REF] or [START_REF] Thrun | Probabilistic Robotics (Intelligent Robotics and Autonomous Agents), chapter 9[END_REF]) is to update using the maximum rule:

odd t = max(odd t-1 , odd(z)). (1.4)
In this case, there is not any overconfidence problem for empty regions but an occupied area can never be empty anymore, the model cannot represent accurately the obstacles in case of false measurement or moving objects for instance. Furthermore the estimation of the obstacle position is very poor (thick wall in fig. 3(b)) which tends to give bad localisation. However the compression capabilities of such representation are interesting since most parts of the map stay at the original value when the space is empty (fig. 2(b)). For reflection probability maps the same effect can be obtained by just updating ♯hits.

Clamping policy

A quantification policy discretized the range of occupancy values into a small set of possible values, like in [START_REF] Kraetzschmar | Probabilistic quadtrees for variable-resolution mapping of large environments[END_REF]. This process is often done a posteriori since it is not obvious how to consistently update quantified values. For instance the minimum and maximum probabilities are not anymore respectively equivalent to 0 and 1 probabilities. The same policy is difficult to obtain with reflection probability maps since bounding ♯hits and ♯misses independently leads to wrong estimations. For log-ratio occupancy maps the update equation becomes: odd t = max(min(odd t-1 + odd(z), odd max ), odd min ).

(1.5)

where odd max and odd min are the predefined maximum and minimum log-ratio occupancy probabilities. This policy is illustrated in fig. 2(c) and fig. 3(c). It is obvious that this policy suffers for the same problem of precision than the max policy. However, the state of the grid is reversible which make it more suitable for map updates. The regularity of the maps is good because most areas tend to converge towards the two extreme values.

Exponential forgetting policy

We present here a new policy that solve the precision, the overconfident and the regularity problem altogether. The update equations are the following:

odd t = (1 -γ)odd t-1 + γodd(z).
(1.6) The map is naturally bounded, since the odd(z) is bounded and if odd t-1 = odd(z) then odd t = odd t-1 . Therefore the map is easy to compress since there are large coherent areas (fig. 2(d)) and is not overconfident. The map keeps precision since the peaks of occupancy do not disappear because neighboring cells do not all reach the occupancy bounds but always keep their relative differences by forgetting (fig. 3(d)). These policy is called exponential forgetting since a past observation is exponentially less important in the current occupancy estimation. It is worth to notice that ♯hits, ♯misses, mean and standard deviation can be updated the same way. The choice of γ determines the rate of forgetting and by trials we find that a low value is interesting in the case of the mapping with a laser-range finder at 10Hz (γ = 0.3 is taken in the experiments).

One drawback of this policy is that using naively in the unobserved area, it makes the cell occupancies converge toward a unknown state rapidly since in log-ratio the value of odd(z) for this kind of area is zero. This problem can be avoided by only updating areas that are in the field of view of the sensor, in the occupied and empty zones only (see fig. 1(b))

Policy mixing and initial conditions

All these different policies can be combined together to build new policies that solve some of the problems. For instance, since the empty space is often the most important part of a map, an interesting combination is to clamp the lower occupancy values while not bounding the upper ones. The compression abilities of such a map are good, and it was the policy we use in previous experiments [START_REF] Yguel | Dense mapping for range sensors: Efficient algorithms and sparse representations[END_REF]. In this case, an obstacle can easily appear but it disappears very slowly if it was observed a long time. It is conservative from an obstacle avoidance point of view while it could be really annoying when searching a free place in a car park. An other important choice is the initialization of the occupancy value of the map. From a compression point of view the most interesting choice is to initialize the map with the empty bound3 since it is the most probable value in an environment where a robot is supposed to evolve (see fig. 4(a

Sparse representation through hierarchical map organization

This section describe how the update policies change the hierarchical update algorithm developed in [START_REF] Yguel | Dense mapping for range sensors: Efficient algorithms and sparse representations[END_REF] for sparse representations.

Problem statement

One popular method to compress a grid-based representation in the robotic community rely on building a tree based hierarchical representation of the map ( [START_REF] Kraetzschmar | Probabilistic quadtrees for variable-resolution mapping of large environments[END_REF], [START_REF] Payeur | Merging uncertainty into probabilistic octree models of 3-d perturbed workspaces[END_REF], [START_REF] Payeur | Range data merging for probabilistic octree modeling of 3-d workspaces[END_REF], [START_REF] Payeur | Probabilistic octree modeling of a 3-d dynamic environment[END_REF], [START_REF] Yguel | Dense mapping for range sensors: Efficient algorithms and sparse representations[END_REF]). The idea is to represent large area with the same occupancy with a single node at an appropriate coarse scale. To be efficient these strategies suppose that the map have indeed large uniform occupancy area, therefore a policy that bound the map is always required at least for the main part of the map (which is the empty one). As stated in [START_REF] Yguel | Wavelet occupancy grids: a method for compact map building[END_REF], it is often interesting to store differences between the scales instead of the plain values because small differences are the clue to notice uniform areas or a variant of this scheme like the Haar wavelet transform.

The problem in such representations is how to efficiently update the hierarchical representation taking into account sensor model uncertainties. In a previous work [START_REF] Yguel | Dense mapping for range sensors: Efficient algorithms and sparse representations[END_REF] we derive a hierarchical algorithm that allow to make efficient hierarchical updates with a clamping policy.and in particular updates that are hierarchical in the sens that large part of the map can be updated at large scale when a large part is discover as empty. That is very important in the car park situation when a car can occupied many cells at fine resolution for instance. The drawback of clamping-based policy is that they are either lacking in precision, the drawback when not bounding the occupancy is that the map is overconfident. In the following is exposed the modifications to bring to the hierarchical algorithm in order to use exponential forgetting policies.

hierarchical algorithm

The key idea in the hierarchical exploration of the grid space is to define a predicate: existIntersection that is true if a given set of grid cells intersect the volume defined by the field of view of the sensor beams (blue plus red cells in fig. 1(b)). The absence of intersection indicates that the given set of cells are outside the sensor field of view and don't need updating. For the case of existIntersection evaluating to true, a special sub case would be when the set of cells are totally included in the sensor field of view, then all the cells of the set belong to E (blue cells in fig. 1(b)) and their occupancy are decreased by the same amount of odd emp , eq. 1.2. As the algorithm is able to detect uniform regions recursively, the grid representation should allow the update of regions, and wavelets provide a natural mechanism for doing so. For each grid area, the existIntersection predicate guides the search. If there is intersection the traversal searches deeper into the grid hierarchy, i.e. exploring finer scales. Otherwise it stops at the current node. An update is almost always required for cells that are in the obstacle neighborhood (cells marked with 'D' in fig. 1(b) ) so iteration is always performed in area that contains such a cell. But for boundaries that separate cells that belongs to U set and to E set (white and blue cells in fig. 1(b)) iteration is required only if the E set corrects the knowledge in the grid (fig. 5(c)) otherwise the iterations can stop early in the hierarchy (fig. 5(b)). Further details and pseudo code can be found in [START_REF] Yguel | Dense mapping for range sensors: Efficient algorithms and sparse representations[END_REF].

Modification of the update algorithm under exponential forgetting update policy

The main contribution of the update algorithm with the wavelet representation is that for uniform area the update is hierarchical, however with the exponential forgetting policy all finer scales must forget too. This an important drawback of this policy for a hierarchical representation. To solve this issue there is the possibility to always proceed to a complete traversing of the tree except for regions outside the sensor field-of-view (U set) or regions with occupancy that has reached one of the boundaries occupancy values. The solution proposed here improves this by noticing that a hierarchical update is worth when a big part of the environment being previously occupied becomes empty (like with parked car that leaves its place), in that case successive updates will lead to a complete empty area. Therefore updating the grid at fine scale is totally useless and time consuming, since big parts will be empty. We propose to keep track of the empty updates performed at a coarse scale by recording the corresponding coarse nodes of the grid in a second tree T e . In that tree is stored the corresponding nodes from which empty updates are required along with the number of time an empty update was performed. When updating the grid tree, T e is traversed too and if an update is required for child of a node in T e the empty updates are performed in a lazy fashion. The equations are the following: The number of cells vary from 9 Millions to 36000 from scale 0 to scale 4 and the ratio is one for 256 if the scale 4 is compared to the scale 0. It is obvious that the precision of the map decreases when the scale increases however the shape of the environment is sufficient enough for path planning since scale 3 in the big open area which is very interesting and promising for multiscale path planning algorithm for instance.

odd t = (1 -γ) n odd t-1 + γodd emp ( n-1 ∑ i=0 (1 -γ) i ), = (1 -γ) n (odd t-1 -odd emp ) + odd emp . (1.7)
when n is the number of cached empty update stored in the coarse node of T e . T e is then updated by zeroing the cached updates at the coarse node. It the empty update is required for a fine scale the whole tree is traversed. The only parameter to set is the threshold between fine scale and coarse scale which we fix to match half the size of a car in our application.

Experiments

Computing time and required memory

We performed experiments4 on 2D real data with the modified hierarchical algorithm for exponential forgetting policy with moving obstacles.

In the 2D experiment a big truck equipped with four SICK LMS-291 at each corner carries a big hot metal container behind it during a 1.5 hours experiment, the data are noisy and the evolution property of the map is required by the presence of a lot of moving obstacles (in particular the hot metal container). The algorithm processes the 4 laser rangefinder at real-time (40Hz each). The processing time of the modified algorithm matches the processing time of the update algorithm with clamping policy but provides in addition a non overconfident map.

Conclusions and future works 1.6.1 Conclusions

The objective of this work is to present a review of the update policies in grid-based representation that makes this kind of environment modelling more suitable for compression and to present a new one based on exponential forgetting. This new update policy offers many advantages compare to the others because it present neither overconfidence nor loss of accuracy in the long term. However it remained to see how this new update pattern fit with our hierarchical update algorithm of a sparse grid representation. We have then presented a scheme that allows lazzy updates in case of gross disapearance of objects like cars that leave a car park. In that case the algorithm delayed update as long as possible and in most of the case never needs to do them which makes it as efficient than the update algorithm with Haar wavelets and clamping update policy.

Future Works

In the future we will explore parallelising the computing of the hierarchical update algorithm since the tree structure and distributed memory organisation of the data structure seems be well designed for such a purpose.

  Fig. 1.1.(a) Update of a 2D OG after a sensor reading, initially each cell occupancy was unknown, i.e. 0.5 probability. The sensor beam has an aperture of 7 degrees. The sensor is positioned in (0,0). It thus is the just adding in each cell the value of the log-ratio of the two sensor models. (b) A range-finder beam. The range finder is located at Ω and its field of view is surrounded by red boundaries. It defines the three kind of cell types, unknown cells (U set) in white, empty cells (E set) in light blue and occupied cells: the one close to an obstacle marked with a "D" (B set).

Fig. 1 . 2 .

 12 Fig. 1.2. Log-ratio occupancy maps from the Freiburg data set generated with various policies. For all the figure the color code is the following: the more bright is the color the more occupied is the cell. All color scales are defined from the min occupancy to the max occupancy of the maps. (a) No policy. (b) Max policy. (c) Clamping policy. (d) Exponential forgetting policy.

Fig. 1 . 3 .

 13 Fig. 1.3. Zoom on the map from the Freiburg data set generated with various policies. (a) No policy. (b) Max policy. (c) Clamping policy. (d) Exponential forgetting policy.

  ) and fig.4(b)).

Fig. 1 . 4 .

 14 Fig. 1.4. Map from the Freiburg data set generated with the exponential forgetting policy and a initialization to an empty map. (a) Entire map (b) Zoom on the map.

Fig. 1 . 5 .

 15 Fig. 1.5. (a)The hierarchical process of updating the grid: from the coarsest scale to the finest. To save computing time, area that are outside the polygon of view or totally included inside the area classified as empty are detected and processed early in the hierarchy. (b) and (c): two different cases for the iteration along a boundary of the field of view that separates E set and U set. Fig.5(b) artificial separation, S (with waves) was totally empty and the observation of a part of its interior (on the right of the red boundary) does not bring any information gain. Fig.5(c) the separation brings information about the state of the yellow area that is inside the field of view (on the right of the red boundary). Just in this last case the algorithm 2 performs a search at a finer scale.

Fig. 1 . 6 .

 16 Fig. 1.6. Results of algorithm 2 for 2D data: scaled views of the OG provided by different scales of WavOG representation (a) scale 0, cell size: 10cm × 10cm. (b) scale 2, cell size: 40cm × 40cm. (c) scale 3, cell size: 80cm × 80cm. (d) scale 4, cell size: 1.60m × 1.60m. The data where provided by CSIRO on a long-run experiment. The size of the map is approximately 450m × 200m.The number of cells vary from 9 Millions to 36000 from scale 0 to scale 4 and the ratio is one for 256 if the scale 4 is compared to the scale 0. It is obvious that the precision of the map decreases when the scale increases however the shape of the environment is sufficient enough for path planning since scale 3 in the big open area which is very interesting and promising for multiscale path planning algorithm for instance.

For a certain variable V we will note in upper case the variable, in lower case v its realization, and we will note p(v) for P([V = v]) the probability of a realization of the variable.

Note that it supposed to store the number of time the cell was a beam end-point

It is rarely done without any policy that bound the map since there is no really empty value, and the maps are often initialized with a uniform prior in those cases

Every experiment was done with an Intel(R) Pentium(R) 4 CPU 3.00GHz.

Acknownledgments

The authors would like to thank Christopher Tay Meng Keat, Christophe Braillon and Cedric Pradalier for their contributions and fruitful discussions. We express also our gratitude to CSIRO for providing a consistent huge data set that allowed us to validate our method. We also thank Cyrill Stachniss for making corrected data sets available through his web page [11].


A Djerdir

K Elkadri

A Miraoui

Electrical vehicle feeding by association of utltracapacitors and photovoltaic generators

Keywords: electrical vehicle, ultracapacitors, DC-DC power converters, photovoltaic generator. 1

the aim of this work is to study the association of the ultracapacitors and photovoltaic generators to feed an electrical vehicle. In order to size these components, two electrical models have been proposed starting from their physical behaviours. Two DC-DC converters for the energy management between the photovoltaic generator, the ultracapacitors and the dc bus of the electrical vehicle, have been proposed. The simulation of their functionalities gives good results and shows the possibility to achieve this new application.

INTRODUCTION

The power fluctuations are prejudicial to the battery. So, its useful life decreases considerably in such operation (significant and repetitive of power peaks). The ultracapacitors, by their strong power density and their great ability to be charged and discharged, are more able than the batteries to provide these necessary peaks of power at the convenient periods [START_REF] Bezian | Systèmes de piles à combustibles pour la cogénération -état de l'art[END_REF]. In the reference [START_REF] Djerdir | Utilisation des supercondensateurs dans la chaîne de motorisation des véhicules à pile à combustible[END_REF], the authors describe an electrical train for which the electrical feeding is completely ensured by ultracapacitors. The later are charged from the electrical network during the train stations. This process allows solving the problem of the limited autonomy of ultracapacitors regarding to the batteries one. Furthermore, the railway electric lines are suppressed as well as the related costs.

In this paper we present a study of an association of a photovoltaic generator to ultracapacitors in order to ensure the electric train feeding. Two packs of ultracapacitors are used : the first one is located at the train station where it is charged with a low current (slow charging). The second pack is aboard of the train and it is charged from the first pack under a high current (fast charging), see figure 1. This study shows the used methodologies to choose the converters conv1 and conv2, their sizing and their control strategies. The ultracapacitor packs and photovoltaic generators sizing are also treated. Finally, some simulation results of different functionalities of this new system are included. The voltage level of the DC bus of the electric vehicles is generally about 400V. So, to be able to use the ultracapacitors as principal source of energy in these vehicles, we must consider a conditioning of their voltage with that of the vehicle. The voltage and current levels acceptable by the currently available ultracapacitors are respectively 2.3V and 400A. Thus, their use in a higher voltage and current environments requires their assembly in series or series/parallel. In order to insert the ultracapacitors pack thus gathered, within an electric vehicle, two solutions may be considered: a pack directly connected on the DC bus or through a lifting stage of voltage. At the end of a comparative study between possible conditioner structures, we retained a DC/DC converter based on the boost/back topology. The ratio between the voltage levels of the ultracapacitors pack and the DC bus is a very constraining parameter in the choice of the converter structures. Indeed, the current to cross by the conditioner converter is significant as well as the value of this ratio is high.

PHOTOVOLTAIC GENRATOR MODELLING

In order to size the photovoltaic generator and to study its real time operation, it is necessary to model it in dynamic operating mode. So, the current-voltage characteristics of this generator which are strongly non linear (figure 2) are used to achieve the dynamic modelling. Several studies in different domains of engineering lead to the electrical model of photovoltaic generator which is presented in figure 3 [START_REF] Protin | Convertisseurs photovoltaïques, Techniques de l'Ingénieur[END_REF]. We strike the fact that this generator has a voltage and current behaviours similar to that of a DC current source with a limited voltage. We note also that the photovoltaic generator is about 15% for silicon cells. Thus for a needed power P the solar panel (figure 3) must have a surface 1000 15 , 0 P S  

. Afterwards, one must verifying if the current value of 3.2 A is effectively sufficient for the application. In the case of this value is very small one must grouping several panels in parallel.

CHOCE OF THE CONVERTERS CONV1 AND CONV2

In order to adapt the ultracapacitors voltage to the DC bus one, it's necessary to use a conditioning converter (conv2). This converter must fulfil the following conditions: 1. The ultracapacitors voltage lifting to that of the DC bus.

2. The regulation of the voltage ratio between the chopper input and output.

3. Ensuring the current reversibility.

So, the searched converter is a DC-DC one with an inductive stage of energy storage. Thus, we chose the boost/back converter shown in figure 4. This structure is simple both for its command and its establishment. With the same way we lead to choose the same structure for conv2.

Ultracapacitors

MINATURE TEST MODEL

This study concerns a miniature test model "1/24 th scale" for that the main components are presented on figure5. In this time, the train is Ac-Dc powered. Our target is to replace this feeding system by a solar-power one. To achieve this goal we must build the two converters conv1 and conv2 (figure 1). At this stage of the study, the ultracapacitors packs (pack1 and pack2) and the converters (conv1 and conv2) are sized and the different functionalities of the system have been simulated. The simulations have been achieved by using the Matlab/Simulink software. In this section we present the main simulation results showing the feasibility of this new application.

A.

Low charge : photvoltaic generator -pack1 :

In order to see the magnitudes variations, we consider a small value of capacitance of the pack1 (6.76 F for example). We obtain the current and voltage variation in the low charge case, see figure 6. The pack1 is initially charged at 10 V, the pack2 at 12V. The pack1 is discharged in pack2 thought the converter conv1. The figures 7 and 8 show respectively the currents and the voltages of both the packs of ultracapacitors.

C. Pack2-Dc bus

This simulation highlight that the proposed system ensures well the voltage conditioning between the pack2 and the DC bus voltages of the electrical vehicle. The simulation results are presented on figures 9 and 10. It is clearly seen that the Dc bus of 24 V is fulfilled during the load cycle. We notice that the current in the pack2 increase when the corresponding voltage decreases. At this stage of the study, we are finalizing the test model building. So, several studies in the area of the electrical energy management may be experimented.

In the full paper, we will develop the study of the structure presented above. We will analyze the converters and their command. We will present some simulations and experiment results highlighting the operation of a "photovoltaic generator -conv1-pack1-conv1-pack2-conv2-dc bus and load" system. More details about the experiment aspects of this study will be also given.

8.

RÉFÉRENCES

Figure 1 :

 1 Figure 1 : Energetic scheme of the studied system

Figure 2 :

 2 Figure 2 : Example of photovoltaic characteristics [7]

Figure 3 :

 3 Figure3: Equivalent electrical scheme of a photovoltaic generator[START_REF] Protin | Convertisseurs photovoltaïques, Techniques de l'Ingénieur[END_REF]

Figure 4 :

 4 Figure 4 : boost/back converter

Figure 5 :

 5 Figure 5 : Photos of the miniature test bunch 6. SIMULATION

Figure 6 :

 6 Figure 6 : voltages and currents of pack1 and photovoltaic generator during the low charging B. Fast charging : pack1 -pack2 :

Figure 7 :

 7 Figure 7 : current variations of pack1 and pack2

Figure 9 :

 9 Figure 9 : Voltage and current of the pack2 during a load cycle

Figure 10 :

 10 Figure 10 : Voltage and current of the Dc bus during a load cycle 7. CONCLUSIONThis work assures us an obvious contribution of the ultracapacitors insertion into the motorization chain of electric vehicles. The combination of ultracapacitors and solar panels may be used to completely feed an electrical vehicle. The obtained simulation results are encouraging to start novel prospects in the renewable energy applications.At this stage of the study, we are finalizing the test model building. So, several studies in the area of the electrical energy management may be experimented.In the full paper, we will develop the study of the structure presented above. We will analyze the converters and their command. We will present some simulations and experiment results highlighting the operation of a "photovoltaic generator -conv1-pack1-conv1-pack2-conv2-dc bus and load" system. More details about the experiment aspects of this study will be also given.


Romain David
email: romain.david@imbe.fr

Laurence Mabile
email: laurence.mabile@univ-tlse3.fr

Mohamed Yahia

Anne-Sophie Cambon-Thomsen
email: anne.cambon-thomsen@univ-tlse3.fr

Anne-Sophie Archambeau

Louise Bezuidenhout

Sofie Bekaert

Gabrielle Bertier

Elena Bravo

Jane Carpenter

Anne Yahia

Louise Archambeau

Sofie Bezuidenhout

Gabrielle Bekaert

Elena Bertier

Jane Bravo

Anna Aurélie Carpenter

Michele Delavaud

Laurent De Rosa

Florencia Dollé

Fiona Grattarola

Sophie Murphy

Alison Pamerlon

Anne-Marie Specht

Mogens Tassé

Martina Thomsen

Rda-Sharc Zilioli

Group Interest

Anne Cambon

Fiona Murphy

Murphy Mitchell

Alison Specht

Mogens Thomsen

How to operationalize and to evaluate the FAIRness in the crediting and rewarding processes in data sharing: a first step towards a simplified assessment grid

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.

/or recognition for researchers practicing Open Science. 2017 * E.U. European Commission Directorate-General for Research and Innovation report: H2020 Programme Guidelines on FAIR Data Management in Horizon 2020, Version 3.0, 26 July 2016

each data/dataset identified by an indexed and independant identifier ?

Persistent metadata / data link ?

Metadata updated standards for data describing ? If so, are the data standards and particularly versioning data standards recommended by community-approved or appropriate authorities specified

Data format/type description?

Metadata description and searchability

Are the types and formats of data generated / collected well described?

Data traceability

Are the provenance and type of all data properly specified (origin of raw, primary, transformed, secondary..)?

Data access restriction justification?

Access restriction

In case of a non legal restricted access, is the restriction properly justified by the researcher ?

Data repositories?

Reusability tools

Does the researcher provide information on methods and tools that permit the understandability, integrity, value and readability of data intended to be kept on the long-term ? (e.g. versioning, archival and long term reuse issue for protocols, softwares, required methods and contexts to create, read and understand data)

Never/NA If Mandatory Sometimes Always Never/NA If Mandatory Sometimes Always

Legal reuse restriction properly justified?

Reusability right

In case of a legal reuse restriction (such as personal data, state and public security, national defense secret, confidentiality of external relations, information systems security, secrets in industrial and commercial matters) , is the restriction properly justified? The aim of the simplified assessment grid is to focus on essential criteria only and to be completed by scientists who produce data. It is the summary of a more extensive grid designed for assessing optimal sharing of data (not yet possible at the moment for most scientists worldwide). The assessment is based on FAIR criteria compliance.

Data sharing arrangements meet data ethics and protection?

This grid can be used to get a first appreciation of the researcher's practice but cannot be used alone for a comprehensive assessment of the FAIRness of data sharing. Motivations related-criteria help to interpret further the results highlighted as good practices.

In order to foster data sharing, the RDA-SHARC (SHAring Rewards & Credit) interest group has been set up to unpack and improve crediting and rewarding mechanisms in the data/resources sharing process. As part of the objectives, two assessment grids are being developed using criteria to establish if data are compliant to the F.A.I.R principles (findable /accessible / interoperable / reusable). The criteria used are based on the work from FORCE 11*, and on the basis of the Open Science Career Assessment Matrix designed by the EC Working group on Rewards under Open science.

Par SangyaPundir -Travail personnel, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=53414062

DATA SHARING EVALUATION TO TRIGGER CREDITING/REWARDING PROCESSES BUILDING FAIR-BASED ASSESSMENT GRIDS

To be generic and trans-disciplinary, assessment grids should be understandable by all scientist including the ones who are not expert in data science.

The two grids displayed as a tree-graph structure are based on previous works on FAIR data management (Reymonet et al., 2018;Wilkinson et al., 2016;Wilkinson et al., 2018; and E.U.Guidelines about FAIRness DMPs*): 1/ the self-assessment grid is conceived as a checklist for scientists to identify if her/his own activities are compliant to FAIR principles and to pinpoint the hurdles that hinder efficient sharing and reuse of data 2/ the two-level grid (simplified / extensive) is conceived as a chart for the evaluator to assess the quality of the researcher/scientist sharing practice, over a given period, taking into account the means & support available over that period. Assessment criteria are classified according to their level of stringency for FAIRness (essential / recommended / desirable).

First draft of the simplified FAIR criteria assessment grid

INPUT NEEDED FROM RESEARCH COMMUNITIES

To implement a highly fair appraisal of the sharing process, appropriate criteria must be selected in order to design optimal generic assessment grids. This process requires participation, time and input from volunteer data producers/users scientists in various fields. The aim is to get feedback from a larger community as to the validity of the criteria over different fields. The assessment grids will circulate in the RDA community as an online questionnaire as soon as possible.

Are you producing or using data? Please participate in the development of the FAIRness assessment grids by completing the questionnaire when available.

It will help you get credit back for your efforts!