S Beguet

J Perraud
email: jean.perraud@onera.fr

M Forte

J.-Ph Brazier

Modeling of transverse gaps effects on boundary-layer transition 1

Delaying laminar-turbulent transition is considered a crucial issue with respect to the reduction of airplanes environmental impact, allowing to reduce skin friction drag and thus, fuel consumption. As part of this thematic, boundary-layer destabilizing effects of surface imperfections -assembly gaps, steps, rivets, waviness, holes -have been investigated by ONERA scientists for many years. Experimental, numerical and theoretical works provided fruitful results partly described in this paper, which especially focuses on gaps effects. Geometrical triggering criteria were searched and found to reproduce transition at a realistic chord percentage on reduced scale models. More recently, predicting the impact of gaps on laminar flow transition was also studied so as to provide a numerical tool for defining tolerances compatible with Natural Laminar Flow (NLF) airfoils. A specific model based on a ∆N approach has been developed to quantify the transition displacement caused by transverse gaps with a rectangular section. Detailed experimental studies which recently contributed to its validation are also presented in this paper.

Considering the continuously increasing demand in air transport, a major effort is required so that pollutant emissions do not meet the same trend. Reducing harmful emissions has risen among the main goals of the International Civil Aviation Organisation (ICAO). As less drag reduces fuel consumption, numerous investigations aim at diminishing skin friction drag, which usually represents between 30 % and 80 % of the total airplane drag. Active and passive flow control devices have been developed for years to this end. They generally exploit the rather large difference in skin friction drag which exists between laminar and turbulent boundary-layers (a turbulent boundarylayer induces much more skin friction than a laminar one). Among them, optimizing airfoil shapes is considered as a natural passive way of extending the laminar boundary-layer region and falls in the Natural Laminar Flow (NLF) category. From the late 1930's, different countries conducted flight tests to observe pressure gradient effects, sweep or yaw angle effects on the laminar-turbulent transition position as part of NLF investigations. Smaller scale experiments were also carried out in wind-tunnels, but they all highlighted how difficult it was to reproduce real flight conditions:

high Reynolds numbers, pressure conditions, noise level, including instrumentation troubles and small geometric details. This last point has been interesting ONERA scientists for many years. At the beginning, surface imperfections were studied to define triggering criteria in order to artificially induce the transition at a realistic chord percentage on models at laboratory scale. Recently, their destabilizing impact was also investigated to take it into account during the airfoil design process.

In Gaps always cause flow re-circulation, most often limited to the gap extent. Various flow topologies may be encountered depending on the aspect ratio h/b (where h is the gap depth). In 1982, they were identified by Sinha [START_REF] Sinha | Laminar Separating Flow over Backsteps and Cavities. Part II: Cavities[END_REF] (see Fig. 1) who showed, among others, that a gap becomes equivalent to a succession of two opposite steps for h/b < 0.1, case (a). Very deep gaps also contain complex combinations of vortices (d), while in the range 0.1 to 1.5 the cavity flow is dominated by a main vortex (b) with possible secondary ones in the corners (c). Such configurations may present several stability behaviors. For this reason, gaps influence on transition remains poorly documented while various investigations were carried out about steps, humps, and waviness (for example, see ref. [START_REF] Perraud | Laminar-Turbulent Transition on Aerodynamic Surfaces with Imperfections[END_REF]).

h/b 1.5 0.5 0.1 (a) (b) (c) (d)
Fig. 1 Vortices categories according to Sinha's criteria [START_REF] Sinha | Laminar Separating Flow over Backsteps and Cavities. Part II: Cavities[END_REF] The present paper covers more than thirty years of ONERA researches about the influence of gaps on transition. All the results described in this paper are part of the accumulated ONERA database, until now only available in ONERA internal reports written in French. References and details are registered in Tables 1 and2. This article mainly aims at disseminating this knowledge through the community, in the light of experimental metrology, theoretical tools and computational methods for stability analysis evolutions. Its first part deals with gaps considered as a geometrical mean of artificially triggering transition at a realistic chord percentage in wind-tunnel experiments.

Several experimental campaigns are described in order to get a better understanding of the way the triggering criteria were obtained. The second part concerns configurations for which transition occurs downstream of the gap location: in such cases, the transition location may be progressively moved toward the leading edge depending on several parameter changes. An appropriate ∆N model is proposed, based on both experimental and numerical recent investigations. Attention was especially paid on momentum thickness continuity in order to follow the natural equipped with a super-elliptical leading edge. Gaps of various dimensions and shapes, parallel to the leading edge, were tested using a removable insert. Hot-wire measurements provided information on the nature of the boundary-layer at several locations, whereas boundary-layer parameters (such as the displacement thickness, the momentum thickness and the shape factor) were computed. Olive & Blanchard finally obtained a single "right tripping" curve for the two pressure gradients they tested (slightly negative or zero). Their data are compared to more recent ones in Fig. 2.

These other points were obtained by Séraudie [START_REF] Séraudie | Influence of Gaps and Holes on Boundary Layer, in 2D and 3D Flows[END_REF] and Gentili & Forte [START_REF] Gentili | Experimental Study of the Effect of Gaps on the Laminar/Turbulent Transition for Incompressible Boundary Layers[END_REF] at ambient temperature in a velocity range from 5 to 80 m/s (thus for unit Reynolds numbers between 300 000 and 5 millions), on a different model (Onera-D airfoil detailed in part III B 1) at several angles of attack (for more details, see Table 1). The h/b constant lines in Fig. 2 help relate the range of gaps tested to the topologies described in Fig. 1. Very deep gaps were not considered here while looking at efficient triggering conditions. According to Fig. 2, a "L-shaped" tendency emerges: dimensionless gap sizes respectively reach asymptotic values evaluated as b/δ 1g ≥ 18 and h/δ 1g ≥ 2, where δ 1g is the boundary-layer displacement thickness at the gap position for an equivalent smooth case. With regards to the large range of aerodynamic parameters, the unique qualitative evolution and the rather small dispersion are noticeable. Similar studies were also conducted on swept wings. In this configuration, the gap width in the streamwise direction b * (b * = b/ cos φ with φ the sweep angle) was experimentally shown more relevant than the gap physical width b to characterize gaps triggering limits. Figure 3 compares two-dimensional data previously presented in Fig. 2 to their three-dimensional counterpart (see ref.

[5] and [START_REF] Gentili | Experimental Study of the Effect of Gaps on the Laminar/Turbulent Transition for Incompressible Boundary Layers[END_REF]). While instability processes are totally different, corresponding to Tollmien-Schlichting waves in 2D, and to cross-flow instabilities in the 3D swept case, the asymptotic values appear to be quite similar for both configurations, with a number of 3D results located slightly below the 2D trend.

Triggering criteria provide an easy way of dimensioning gaps to cause a realistic transition on models as well as an easy way of estimating an upper limit for NLF compatible tolerances. Laminar Navier-Stokes or boundary-layer computations of the smooth case provide the reference value δ 1g .

Results must then be compared to the asymptots b/δ 1g = 18 and h/δ 1g = 2. For greater values, transition is known to be triggered at the gap location. It is also worth mentioning that this criterion highly contrasts with the original Nenni & Gluyas one which is based on upstream flow parameters and on the gap width, and which thus does not take into account local conditions as well as gap depth.

Even if this first part dealt with the triggering of transition at the roughness location, experiments also highlighted that gaps could affect transition location far downstream. Further investigations are described in the next part, where only 2D configurations are considered.

III. Gaps effects quantification in 2D cases

ONERA scientists developed a model in order to quantify the destabilizing effects of transverse gaps and contribute to answer the industrial demand concerning transition prediction and flow control.

After some comments about the stability tools which were used, this part focuses on the ∆N model description, from the mean flow calculation to the model definition and to its recent experimental validation. A further simplification consists in using spatial theory, by which the frequency ω is real and the wavenumber α complex. The term exp(-Im(α)), with Im(α) being the imaginary part of α, then describes the amplitude growth of a disturbance at a given angular frequency ω = 2πf . Because we often encounter exponential growth, it is convenient to consider the logarithm of the amplification rate and to introduce a so-called N-factor as

N f (x) = x x0 -Im(α)dx (1)
where x 0 is the most upstream position for which the considered frequency is amplified for the first time. Finally, because there is no a priori knowledge of the frequency causing transition, the N-factor is defined by taking the maximum over frequency :

N (x) = max f (N f (x))) (2)
In 1956, Smith and Gamberoni [START_REF] Smith | Transition, Pressure Gradient and Stability Theory[END_REF] and Van Ingen [START_REF] Van Ingen | A suggested semi-empirical method for the calculation of boundary-layer transition region[END_REF] based their well-known e N prediction method for laminar-turbulent transition, depending on the N-factor amplification and on the upstream level of perturbations. As long as N (x) remains smaller than a limit value N T , the boundarylayer is laminar. Non-linear mechanisms, rapidly leading to the birth of turbulent spots, start at the transition point. It is worth noting that the validity of this spatial approach was shown in case of rapidly evolving flows, in case of thin separation bubbles, by comparing -Im(α) values taken from local linear stability analyses with Direct Numerical Simulation results (see Gruber and Bestek [START_REF] Gruber | Interaction between a Tollmien-Schlichting Wave and a Laminar Separation Bubble[END_REF] for a separation bubble, and Edelmann and Rist [START_REF] Edelmann | Impact of Forward-facing Steps on Laminar-Turbulent Transition in Transonic Flows without Pressure Gradient[END_REF] in the case of a forward-facing step). In case of deep gaps, acoustics may play a role as well as other types of instabilities. The use of global stability analysis could be explored in such configurations.

Empirical ∆N model

An appropriate N-factor modification may properly model the destabilizing effects of the studied imperfections, and this is the ∆N approach main principle. In a first phase, steady laminar Navier-Stokes computations were undertaken using the ONERA code elsA, to compute the mean flow on a flat plate with a rectangular gap downstream of the leading edge. Care was taken to ensure a precise computation of the velocity profile by selecting a second order Roe scheme with low artificial dissipation. The test case of the flat plate boundary-layer was exploited to ensure that mesh definition and numerical options were correctly chosen, so that the incompressible shape In order to facilitate comparisons of the results, and post-treatment, the gap location (upstream edge x g ) was kept constant at x g = 0.8 m. The flat-plate leading edge was placed at a distance upstream of the gap such that the desired boundary-layer thickness, characterized by Re θg , could be obtained at the gap location.

The flow Mach number was set to 0.3 in order to accelerate convergence and avoid the use of the low speed pre-conditioning in the Navier-Stokes solver. Flow topologies in this range of parameters present one or two contra-rotating, stationary, transverse vortices trapped inside the gap (cases b, c of Fig. 1). The boundary-layer profiles were extracted from the flow field following the determination of the boundary-layer upper limit, as in ref. [START_REF] Perraud | Laminar-Turbulent Transition Prediction in the Presence of Surface Imperfections[END_REF].

Two sensors, based on shear and on vorticity, were used to define this limit. Care was taken to include the cavity region in the boundary-layer. The profiles are expressed in term of wall normal distance, hence the integral quantities show jumps at both edges of the gap, and the shape factor increases drastically within the gap width (Fig. 4).

The boundary-layer profiles were then used as input data for a local, linear stability calculation using the ONERA code CASTET, to produce the N-factor curves. Unstable frequencies ranging between 1 kHz and 3 kHz start gaining amplitude upstream of the gap location, are further amplified in the gap region, and pursue their evolution at a higher N-factor level past the gap. In parallel, higher frequencies ranging around 4 kHz arise inside the gap and are strongly damped just after.

The Re b and Re θg dependencies are consistent with complementary experimental observations which emphasized the gap position influence -taken into account in θ g -and confirmed the gap width influence [START_REF] Perraud | Étude expérimentale et numérique des effets de rugosités sur la transition d'une maquette en flèche, dans la soufflerie F2. Partie 2 : dépouillement et analyse des résultats[END_REF][START_REF] Perraud | Étude expérimentale et numérique des effets de marches et de rainures sur la transition en bidimensionnel. Essais complémentaires dans la soufflerie T2. Partie 2 : dépouillement et analyse des résultats[END_REF]. Concerning gap depth, computations showed an evolution of the results up to an aspect ration h/b = 0.2, and a slow variation of mean flow parameters in the range 0.2 < h/b < 0.7. Deeper gaps proved difficult to treat, due to convergence issues with the laminar Navier-Stokes solver. Further analysis assumes that h/b > 0.2 without considering gap depth effects.

The model proposed here assumes that a small gap on a flat plate will induce a pressure gradient perturbation resulting in a perturbation of the base N-factor curve. On a profile, the shape-induced pressure gradient will result in a modified smooth wall N-factor, to which the perturbation caused by a gap may then be added.

As all these simulations were done at Mach 0.3, the uncoupled regime observed in this domain may be questionable at larger velocities. This point would necessitate additional simulations.

Figure 7 shows values of N peak function of both gap width and location through the two parameters Re b and Re θg . These variations were expressed with a rather simple model, given by equations ( 3) and ( 4). given by eq. ( 3) reaches a value of 7. It is assumed here that the gap depth is larger than required by both criteria (h/b > 0.2). ) is well-suited for transition and laminarity studies. A twodimensional model based on an Onera-D symmetric profile was mounted in its test section as described in Fig. 9(a). This airfoil has a chord length of 0.35 m and is equipped with a metallic insert in order to change gap dimensions at exactly x g /c = 10 %.

Transition was detected by constant temperature hot-wire anemometry (CTA), but with two distinct approaches: in 2012 [START_REF] Gentili | Experimental Study of the Effect of Gaps on the Laminar/Turbulent Transition for Incompressible Boundary Layers[END_REF], measurements aimed at finding local velocity for which transition occurs (mentioned as "critical velocity" in this paper) by increasing free-stream velocity while keeping a fixed probe location, whereas in 2014 [START_REF] Beguet | Experimental and Numerical Study of the Effect of Gaps on the Laminar/Turbulent Transition for Incompressible Boundary Layers[END_REF] they aimed at finding the location where transition occurs by translating the probe at a constant height above the wall for a fixed free-stream velocity.

Both approaches are described with greater details in [START_REF] Forte | Experimental and Numerical Study of the Effect of Gaps on Laminar Turbulent Transition of Incompressible Boundary Layers[END_REF] and [START_REF] Forte | Experimental and Numerical Study of the Effect of Gaps on the Laminar-Turbulent Transition for Two-Dimensional Incompressible Boundary-Layers[END_REF]. They both contribute to the validation database presented in this part. In practice, several methods can be used to localize the beginning of the laminar-turbulent transition: in both presented studies, transition is identified by a sudden increase in velocity fluctuations in the boundary-layer (corresponding to the birth of turbulent spots). Tested gaps are listed in Table 3.

Aspect ratio, h/b 0.17 0.33 0.5 0.67 0.125 0.25 0.1 0.2

Transitional N-factor values

N T values are required to numerically predict the transition location induced by gaps (using the ∆N model) before comparing it to measurements. It actually may be calculated from the freestream turbulence level (Tu) of the working environment by using the Mack formula (expressed as N T = -8.43 -2.4 ln(Tu)), but the way of obtaining Tu always induces discussions (mainly about the frequency integration range). For this reason, a more robust procedure based on the experimental database and linear stability analyses was preferred to deduce the N T values in both presented studies. For a given smooth configuration, the experimental transition location was reported on the N-factor envelope curve provided by a local linear stability analysis. The N-factor reached at this location was then taken as N T .

3. Results supporting the ∆N model assumptions According to this plot, critical Re b becomes constant for aspect ratios higher than h/b = 0.2, and so becomes independent of h.

This asymptotic phenomenon can also be observed in Fig. 10 remark also tends to support the fact that a local approach apparently makes more sense, as already noticed in Part II.

Results concerning the ∆N f ar effect

In 2014 [START_REF] Beguet | Experimental and Numerical Study of the Effect of Gaps on the Laminar/Turbulent Transition for Incompressible Boundary Layers[END_REF], successful results were found about the ∆N f ar estimation. A visual example of numerical and experimental comparison is given in Fig. 11 Some particular results however remain to be discussed. The largest difference is obtained at β = 0 • with the gap b = 4 mm / h = 1 mm, for U ∞ = 50 m/s and U ∞ = 60 m/s. In these cases, transition directly occurs at the gap location whereas the model prediction finds it at x/c = 57 %.

According to the model definition, such a transition should have been caused by N peak : this remark tends to support a possible under-estimation of N peak (which did not exceed N T as planned) rather than a ∆N f ar failure.

The last significant difference is observed at β = 0 • with the gap b = 3 mm / h = 1 mm, for U ∞ = 60 m/s. In this case, the model shows a long region with decreasing N-factors (see Fig. 12), resulting from a small negative pressure gradient. Such configuration is very different from the monotonically increasing flat plate N-factor curve, and this difference may explain the large error. Transition cannot be predicted using linear stability within this region, while non-linear mechanisms may play a role with N-factors above 6. Another point which may be raised is the validity of the assumption concerning the ∆N independence from pressure gradient, which may not be valid in this case. Further investigations would be needed to evaluate pressure gradient effects on N peak and ∆N f ar . Even if some points remain to be improved, ∆N f ar can properly quantify the progressive effect of gaps on transition which happens downstream of its location, in case of strictly increasing Nfactor curves. As shown in this part, the first and only experimental campaign conducted in order to measure this effect provided very encouraging results.

Conclusion

This paper sums up activities conducted at different periods extending over more than thirty years of ONERA research dealing with the effect of transverse rectangular gaps on boundary-layer laminar-turbulent transition. Gaps were first investigated as a way to artificially trigger transition on wind-tunnel models during low Reynolds number tests without increasing the boundary-layer thickness. A triggering criterion was defined and confirmed after wind-tunnel tests in various conditions. On a two-dimensional wing (no sweep), the limits were expressed as b/δ 1g ≥ 18 and h/δ 1g ≥ 2.

These results do not significantly differ for a three-dimensional (swept) wing although the very different nature of boundary-layer instabilities should be kept in mind to extrapolate from 2D to 3D.

In

1 x

 1 factor peak at the gap location ∆N f ar N-factor shift downstream of the gap location N T N-factor for which transition occurs P stagnation pressure, bar Re b Reynolds number based on b and on the local external flow velocity Re θg Reynolds number based on θ g and on the local external flow velocity T stagnation temperature, K Tu free-stream turbulence level U ∞ upstream velocity, m.s -1 u g local external velocity at the gap location, m.s -streamwise attack (or AoA), degree δ 1g boundary-layer displacement thickness at the gap location, on a smooth profile (no gap), mm φ sweep angle, degree ν kinematic viscosity of the fluid, m 2 .s -1 θ g boundary-layer momentum thickness at the gap location, on a smooth profile, mm ω angular frequency, s -1

  1966, Nenni & Gluyas [1] conducted flight tests and suggested experimental criteria about steps and gaps effects on transition triggering. According to their results, a transverse gap would not significantly affect transition for Re b = U ∞ b ν < 15000, with U ∞ the upstream flow velocity, ν its kinematic viscosity and b the gap width. Even if this criterion remains a usual reference, it is worth mentioning that the community agreed to rather use the local velocity at the gap position u g instead of the upstream velocity U ∞ . As the very heart of this kind of study concerns unstable processes taking place inside the boundary-layer, this local point of view indeed should make more sense.

Fig. 2

 2 Fig. 2 Experimental data obtained at ONERA about "right tripping" limits in 2D configurations.

Fig. 3

 3 Fig. 3 Comparison of experimental data obtained at ONERA about "right tripping" limits in 2D and 3D configurations.

A. Numerical prediction 1 .

 1 Theoretical overview Amplification of small amplitude disturbances, such as Tollmien-Schlichting waves in 2D flows, may be predicted by way of linear stability theory. The subclass of local linear stability theory is presently the most often used approach for transport aircraft design, solving the Orr-Sommerfeld equation for viscous boundary layer flow. In local linear stability theory, disturbances are expressed as d ′ = d(y) exp [i(αxωt)], with an amplitude d depending only on the normal coordinate y. This ansatz allows to reduce the problem to an ordinary differential equation for the amplitude function d.

  factor H i is correct to the second decimal point. Parameters explored in this study are the gap width b (15000 < Re b < 40000), the gap location characterized by a momentum thickness Reynolds number (300 ≤ Re θg ≤ 800), and the aspect ratio (0.2 ≤ h/b ≤ 0.7). Both Re b and Re θg are local parameters based on the flow velocity and momentum thickness at the gap location, but on a smooth case without any gap.

Figure 5 (

 5 Figure 5(a) shows envelope curves of Tollmien-Schlichting N-factors obtained for several gaps such that Re θg = 300, in which case a large peak may exist at the gap location. When Re θg is increased to 800 (Fig. 5(b)), the local response is reduced while the N-factor curve jump past the gap may become more important.From the results of a parametric study, it was shown that the N-factor modification induced by a gap results in the superposition of two components represented in Fig.6(a): on one hand, N peak

Fig. 4 Fig. 5

 45 Fig. 4 Exemple of computed shape factor

Figure 6 (

 6 Figure 6(b) supports this remark by showing the emergence of high frequencies within the gap.

N

  peak = 0.0001(Re b /Re θg ) + 0.000209 Re b -0.00793 Re θg + 4.97 (3) ∆N f ar = 0.0086(Re b /Re θg ) + 0.000035 Re b -0.0025 Re θg + 2.244(4)This model is of low order to avoid rapid variations at its limits. It may be used within the range of parameters specified earlier.

Fig. 7 N

 7 Fig. 7 N peak model and data points issued from stability computations

Fig. 8

 8 Fig. 8 Link between Olive & Blanchard results and the N peak model

3 .B. Experimental validation 1 .

 31 Practical termsFocusing on practical aspects, the ∆N model is proving to be simple of use. Once computed the mean flow in the baseline case (without surface imperfection), the local parameters (velocity and momentum thickness) are enough to calculate N peak . With this first value, the studied gap is quickly known to trigger transition or not by comparing N peak with the transitional N-factor N T of the considered configuration. Such a point already makes this model an interesting tool for defining NLF tolerances. In case of a non-triggering gap, adding the corresponding ∆N f ar to the baseline N-factor envelope curve allows to estimate the laminar-turbulent transition shift caused by the gap. Experimental setup and methodologiesWhile the N peak model may quite simply be related to Olive & Blanchard criterion, experiments before 2011 did not allow to validate the ∆N f ar model because the search of a "critical velocity", with measurements done at a single location, could not detect a progressive move of the transition location. Additional experiments were required which took place in the subsonic open-return "Trin1" wind-tunnel located in Onera Toulouse premises. This wind-tunnel runs in ambient conditions at free-stream velocities from 10 to 80 m/s. Its low free-stream turbulence level (7 × 10 -4 < Tu < 2.5 × 10 -3

a)Fig. 9

 9 Fig. 9 Onera-D model

Figure 10 (

 10 Figure 10(a) represents critical Re b values versus aspect ratios h/b for both experiments [5, 6]. Even if Re b was first defined by Nenni & Gluyas as Re b = U ∞ b ν , Re b is here rather chosen as Re b = u g b ν , with u g the external velocity taken at the gap location under critical conditions.

  Fig. 10 Gap depth effects. h/b criterion verification[START_REF] Beguet | Experimental and Numerical Study of the Effect of Gaps on the Laminar/Turbulent Transition for Incompressible Boundary Layers[END_REF]

  Fig. 11 Numerical determination of transition location, U∞ = 30 m/s, β = 1 • and b = 4 mm [18]

Fig. 12 N

 12 Fig. 12 N-factor envelope curve, U∞ = 60 m/s at β = 0 • [18]

  contrast to the old Nenni & Gluyas criterion only function of Re b , the Olive & Blanchard criterion (fig 2) also introduces the local flow properties at the gap location with the boundary-layer displacement thickness δ 1g . Gaps effects on laminar-turbulent transition have been more recently investigated through both numerical and experimental studies which contributed to develop a specific ∆N model for low velocity 2D cases. Gaps were shown to contribute in two different ways: first, by amplifying the Tollmien-Schlichting waves already present upstream of the gap (∆N f ar effect), and second, by creating new instabilities only observed within the gap width (significant local effect, or N peak effect). These two effects are quantified by formulas (3) and (4) depending on the gap width and the boundary-layer momentum thickness θ g at the gap location. N peak and ∆N f ar provide a very simple way of predicting gaps effects, requiring at least a laminar Navier-Stokes computation (or a boundary-layer calculation) of the smooth case, and at worst (in case of non-triggering) a local linear stability analysis. Results of this model have been compared to the experimental database recently generated. One of the main difficulties lies in the fact that N peak and ∆N f ar empirical estimations result from numerical parametric studies on flat-plates with zero pressure gradient, whereas comparative experiments were conducted with an airfoil model. Promising results tend to confirm the ∆N model relevancy (particularly for the downstream effect modeled by ∆N f ar ), but the pressure gradient effect needs to be further investigated. Also to be further explored are the effects of compressibility and the behavior of gaps with a larger depth (h/b > 1). The link between the N peak estimation and the Olive & Blanchard criterion was established for a Blasius boundary-layer with a number of hypotheses. Both of the L-shaped curve (b/δ 1g ≥ 18 and h/δ 1g ≥ 2) and the N peak estimation (at large enough Reynolds number) provide a very easy way of predicting if a given gap may affect or trigger transition (they only require a laminar Navier-Stokes or a boundary-layer computation of the smooth case, and the gap dimensions). Together with the ∆N f ar model, they may be used as a convenient way of determining tolerances compatible with NLF. The present analysis is based on boundary-layer stability computations, assuming a dominant contribution of convective instabilities. Further analyses, taking into account global instabilities, are now under way at ONERA.

Table 1

 1 Experimental ONERA database on transverse gaps effects

	Date	Ref	Authors	Model	AoA β	Sweep φ	Metrology / Tools
	1982	[4]	M. Olive	Flat-plate	-1 • /-6 •	0 •	Hot-wire
			A. Blanchard
	2001	[14]	A. Séraudie	ONERA-D	-1 • /-6 •	0 • /60 •	Pitot probe
			J. Perraud
	2001	[15]	J. Perraud	OALT25	-0.15 • /0.5 •	0 •	Pitot probe
			A. Séraudie
	2010	[5]	A. Séraudie	ONERA-D	-8 •	0 • /60 •	Hot-wire
	2012	[6]	L. Gentili	ONERA-D	-8 •	0 • /60 •	Hot-wire
			M. Forte
	2014	[18]	S. Beguet	ONERA-D	0 • /1 •	0 •	Hot-wire
			M. Forte
			Table 2 Numerical ONERA database on transverse gaps effects
	Date	Ref	Authors	Model	AoA β	Sweep φ	Metrology / Tools
	1997	[11]	J. Perraud	Flat-plate	0 •	0 •	Laminar Navier-Stokes
							local linear stability
							PSE
	2010	[17]	J.-Ph. Brazier	ONERA-D	-8 •	1 • /60 •	RANS
							local linear stability
	2011	[16]	J. Perraud	Flat-plate	0 •	0 •	Laminar Navier-Stoke
							local linear stability
	2014	[18]	S. Beguet	ONERA-D	0 • /1 •	0 •	Laminar Navier-Stoke
			J. Perraud				local linear stability
			II. Transition triggering criteria
	Boundary-layer transition dependence on turbulence level and Reynolds number may prevent
	relevant comparisons between wind-tunnel experiments and flight tests. Adapted obstacles were
	thus sized to artificially trigger transition at the same location on models as in full scale conditions.

Table 3

 3 Gaps dimensions

	Width, b (mm)	3	3	3	3	4	4	5	5
	Depth, h

Table 4

 4 Transition locations (xT /c) -Measurements versus numerical prediction

				30 m/s		40 m/s		50 m/s		60 m/s
	AoA	b ; h	Exp	Num	Exp	Num	Exp	Num	Exp	Num
		3 ; 1	69 %	63 %	63 %	62 %	59 %	58 %	41 %	58 %
	β = 0 •
		4 ; 1	66 %	62 %	61 %	61 %	10 %	57 %	10 %	57 %
		3 ; 1	20 %	15 %	×	×	×	×	×	×
	β = 1 •
		4 ; 1	15 %	14 %	×	×	×	×	×	×

Acknowledgments Part of this work has been undertaken within the Joint Technology Initiative "JTI Clean Sky", Smart Fixed Wing Aircraft Integrated Technology Demonstrator "SFWA-ITD" project (contract N • CSJU-GAM-SFWA-2008-001) financed by the 7 th Framework Program of European Commission. The ∆N model was developed within the FLOWMAPI 2 contract supported by the French Délégation Générale à l'Armement (DGA).


Arnaud Mas
email: arnaud-a.mas@edf.fr

Idriss Ismaël
email: idriss.ismael@edf.fr

Nicolas Filliard
email: nicolas.filliard@edf.fr

Indy: a virtual reality multi-player game for navigation skills training

Keywords: Collaborative virtual reality, learning, gamification, spatial navigation

Working in complex industrial facilities requires spatial navigation skills that people build up with time and field experience. Training sessions consisting in guided tours help discover places but they are insufficient to become intimately familiar with their layout. They imply passive learning postures, are time-limited and can be experienced only once because of organization constraints and potential interferences with ongoing activities in the buildings. To overcome these limitations and improve the acquisition of navigation skills, we developed Indy, a virtual reality system consisting in a collaborative game of treasure hunting. It has several key advantages: it focuses learners' attention on navigation tasks, implies their active engagement and provides them with feedbacks on their achievements. Virtual reality makes it possible to multiply the number and duration of situations that learners can experience to better consolidate their skills. This paper discusses the main design principles and a typical usage scenario of Indy.

INTRODUCTION

Developing spatial understanding of an industrial building's structure can be quite difficult. Indeed, the facility priority use is production. In particular, learning sessions in such a building, even short ones, have to meet the production constraints such as busy schedule and safety measures.

Virtual learning environments (VLE) offer a great alternative for learning tasks difficult to undertake in the real world [START_REF] Dalgarno | What are the learning affordances of 3-D virtual environments[END_REF]. Indeed, they allow learners to visit a facility without any consideration about availability, distances or safety. They also give trainers the possibility to modify characteristics of the environment beyond what is possible in real life. They give learners the possibility to learn through active action instead of passive knowledge acquisition, as explained for instance by Pan et al. [START_REF] Pan | Virtual reality and mixed reality for virtual learning environments[END_REF]. Besides, attention, active engagement, feedback and strengthening phases are important in a learning process to ensure effective acquisition of knowledge, as already identified by Dehaene [START_REF] Dehaene | Apprendre à lire : Des sciences cognitives à la salle de classe[END_REF] in the way children learn how to read.

Indy is a new virtual reality application for professionals who will work in industrial facilities. It aims at helping them get familiarized with the facilities during their training period. It is designed to provide professional trainers a tool to build new pedagogical strategies based on virtual reality.

DESIGN PRINCIPLES

Collaboration

Literature tend to show that fostering social interactions and collaboration leads to higher learning efficiency for a virtual group [START_REF] Dehaene | Apprendre à lire : Des sciences cognitives à la salle de classe[END_REF][11] [START_REF] Slavin | Research on Cooperative Learning and Achievement: What We Know, What We Need to Know[END_REF]. Based on this hypothesis, we designed Indy to foster collaboration in a learning context, as defined by Roschelle et al. [START_REF] Roschelle | The construction of shared knowledge in collaborative problem solving[END_REF]: "the mutual engagement of participants in a coordinated effort to solve the problem together".

According to Slavin [START_REF] Slavin | Research on Cooperative Learning and Achievement: What We Know, What We Need to Know[END_REF], group goals and individual accountability can contribute to collaborative learning achievements. Kreijns et al. [START_REF] Kreijns | Identifying the pitfalls for social interaction in computer-supported collaborative learning environments: a review of the research[END_REF] also cite positive interdependence and promotive interaction as levers to enforce collaboration. The authors insist on the fact that "the key to the efficacy of collaborative learning is social interaction, and lack of it is a factor causing the negative effectiveness of collaborative learning". Nonetheless, they point out that technology allowing communication won't automatically imply social interaction, and that off-task casual communication is important for group cohesion.

Indy offers trainers a tool to create a training scenario where several teams are immersed in a virtual industrial building, relying on an asymmetric collaboration method [START_REF] Le Chénéchal | When the Giant meets the Ant An Asymmetric Approach for Collaborative and Concurrent Object Manipulation in a Multi-Scale Environment[END_REF]:

 Some learners are immersed, using a head mounted display (HMD), in a virtual mockup of the building. They will play the "hunters", who will have to find their way to the objective.  Some learners use floor maps and 360° photographs, on a desktop computer. They will play the "radios", who will have to guide the hunters. With this method, learners have access to complementary information according to their role: each one has a key capability to achieve the scenario objective. This makes the communication within the team necessary to navigate in the virtual building. Besides, each team member has a particular point of view and professional background that can be shared with the other team members either to help one to be more efficient or to explain his/her choices.

In Indy, communication between teammates relies on two components: oral communication and pointing at objects in the 3D environment. This way they can help each other, share their viewpoints to confirm the itinerary (current position and future direction) and identify the objective.

However, communication is not limited to the VLE: Indy is designed as part of a full training sequence, during which the trainer and the learners are physically in the same room. Although VLEs allow virtual teams, with physically separated members [START_REF] Johnson | Team development and group processes of virtual learning teams[END_REF], we wanted to preserve the training sequence, which fosters social interaction.

Gamification

Gamification can be defined as "the use of game design elements in non-game contexts" [START_REF] Deterding | From Game Design Elements to Gamefulness: Defining "Gamification[END_REF]. It is commonly used to increase users' motivation and engagement [8][15]. Nah et al. [START_REF] Nah | Gamification of Education: A Review of Literature[END_REF] list the following design elements commonly used in gamified applications, in the educational and learning contexts: points, levels/stages, badges, leaderboards, prizes and rewards, progress bars, storyline, and feedback. Sailer et al. [START_REF] Sailer | How gamification motivates: An experimental study of the effects of specific game design elements on psychological need satisfaction[END_REF] also list specific elements known to show positive effect on users' motivation: points, badges, leaderboards, performance graphs, meaningful stories, avatars and teammates.

Indy is a treasure hunt in an industrial facility: learners have to search in the building for a specific equipment or zone. These situations simulate the ones operators often face in real life, when planning an intervention in a building in which they can go only occasionally. This approach is similar to "investigation-scenarios" already experimented in learning sessions [START_REF] Drakos | Investigationscenarios » and digital mockup in training situation. 52ème[END_REF].

Trainers can launch a contest between teams: the time taken by the teams to find the objective is recorded and displayed at the end of the hunt. The trainer then has the opportunity to use the following elements:

 Level/stages: the trainer can create a new hunt in a few seconds, adapting the difficulty level to the class. The difficulty can vary according to the objective itself, but also to the presence of obstacles placed by the trainer, and the kind of information he/she gives orally or through the application before the hunt.  Points / leaderboard: the trainer can use the recorded time of each team to that matter.  Feedback: after the end of a hunt, an interface allows the trainer to show to the learners all their itineraries during the hunt and screenshots that he/she might have taken. He/she can use all this material for debriefing.

Spatial navigation training

3D VLE are an efficient tool for acquiring spatial navigation skills [START_REF] Dalgarno | What are the learning affordances of 3-D virtual environments[END_REF][1]. Waller et al. [START_REF] Waller | The Transfer of Spatial Knowledge in Virtual Environment Training[END_REF] suggest that using immersive VLE for spatial navigation training might be equivalent to training in a real environment. Indeed, Rodrigues et al. [START_REF] Rodrigues | Transfer of spatial-knowledge from virtual to real environment: effect of active/passive learning depending on a test-retest procedure and the type of retrieval tests[END_REF] confirmed that good spatial knowledge transfer can occur from virtual reality to the real world.

Chrastil et al. [START_REF] Chrastil | Active and Passive Spatial Learning in Human Navigation: Acquisition of Graph Knowledge[END_REF] affirmed that active navigation leads to better spatial knowledge. Particularly, active decision making plays a great role in elaborating a mental model of the place.

Carbonell-Carrera et al. [START_REF] Carbonell-Carrera | Virtual Learning Environments to Enhance Spatial Orientation[END_REF] also insisted on the importance of maps as a complement to VLE for spatial orientation.

As a result, Indy aims at maximizing the spatial knowledge acquired during training:

 The "hunters" have to move along the entire itinerary, at a standard walking pace.  The "radios" have to orally explain the itinerary to the hunters.  Finding the objective involves decision making along the way, particularly when the trainer places obstacles. Indy focuses on the development of 4 skills: navigating in the building (landmarks identification), reading a map (survey knowledge), converting information between both, and communicating route information to others.

BUILDING MOCKUP

Indy uses the virtual mockup of a reactor building. It includes a detailed 3D model reconstructed from laser scans, 360° photographs and updated floor maps [START_REF] Hullo | Multi-Sensor As-Built Models of Complex Industrial Architectures[END_REF].

Creating the learning scenario

When the trainer creates a new hunt, several configuration options are available:  Type of hunt: the objective can be to point at a specific equipment or regroup into a target zone.  Starting point: the trainer can choose any room of the building as a starting point.  Objective: depending on the type of hunt, the trainer can either point at an equipment in the 3D model or draw a circle on a floor map.  Objective as displayed to the learners: text that will be displayed, on demand, on the learners' side.  Obstacles: the trainer can place obstacles or markings anywhere in the building.

Hunt

The learners are divided into teams of 3 or 4 members. In each team, one person plays the "radio" and the others play the "hunters". Before starting the hunt, each team can gather around the radio's computer to prepare its itinerary. The learners can look for the equipment in the photos, and decide which itinerary seems to be best and even select alternative paths.

Afterwards, each hunter puts a HMD to start the hunt. All teammates can communicate orally, in order for the radio to give navigation instructions to the hunters. They also have the possibility to point at objects in the 3D environment, either with the mouse (for the radio) or with the Vive controllers (for the hunters). When doing so, a ray comes from the player's avatar and the object intersected by the ray is highlighted.

The players can't see players from other teams. The visibility between teammates is defined with the following rules:

 The radio can see the hunters' avatars (and pointing ray) in the 3D environment, and their positions on the floor maps.  The hunters can see other hunters' avatars (and pointing ray), but not the radio's avatar (nor pointing ray). This keeps the hunters from simply following the radio. During the whole hunt, the trainer can:  See all the learners on the floor maps or in the 3D environment: he/she can choose which team(s) to see, and which team(s) can see his/her own avatar in the 3D environment.  Point at objects (similarly to the radio players). The pointing ray will be seen by all players seeing his/her avatar.  See all learners' point of view.  Take screenshots: they are saved with their timestamp relative to the hunt.

End of the hunt

To complete the hunt, all the hunters of the team must either (depending on the type of hunt):  point at the target equipment at the same time: they have to keep pointing at the object for two seconds, while a validation animation is displayed ;  be present in the target zone at the same time, and stay in it for two seconds (with the same validation animation). Once the objective is found and validated, the team's total time is saved. When all teams found the objective, the hunt ends: on all screens, a score board shows the total time of each team. The trainer can then start the debriefing.

Debriefing

For a training session to produce better results, we propose feedback data to the trainer. On his/her computer, the trainer can see: the total time of each team in a single timeline, hunters' paths drawn on floor maps and screenshots he/she took during the session. The debriefing interface is completely interactive. The trainer can move a cursor along the timeline to update hunters' paths on the maps. All the screenshots the trainer took are also situated on the timeline. The column on the right, used to change floors, also indicates with markers the floors where the learners currently are, synchronized with the timeline cursor.

The debriefing interface was designed as a tool, leaving the liberty to the trainer to use it as he/she wants, and display it in the classroom to focus on the elements pedagogically relevant for the training.

DISCUSSION

Indy is a tool for professional trainers, allowing them to create and propose scenarios adapted to all kinds of learners: beginners, experienced professionals, engineers or operators. The treasure hunts can be repeated and debriefed as many times as necessary to achieve the trainers' pedagogical objectives.

The debriefing is a key functionality for trainers. It is designed to be as little restrictive as possible, so that trainers would have the entire liberty to define the pedagogical valorization of the hunts. Among its possible uses, we can anticipate the following: discussing learners' itineraries and their implications in terms of safety, suggesting alternatives taking into account additional constraints than those experienced during the hunt, ask learners to explain their own choices, comparing different sessions with the same objective, or even evaluate long-term progression during the learners' careers.

The variety of scenarios that trainers can build with Indy offers several benefits. It allows trainers, when needed, to adapt to a specific work profile. Indeed, different professionals have different needs in terms of spatial knowledge of the facilities: emergency intervention teams, logistics supervisors, operators performing non-destructive testing, safety engineers, etc.

The obstacles adding functionality, in particular, plays a central role in adapting the scenarios. It also offers a way to evaluate the learners' global understanding of the building structure, as they will adapt their strategies in real time to find the objective.

By fostering collaboration and turning the learning experience into a game, we intend to focus learners' attention and actively engage them in using their navigational abilities. Indy offers feedback and allows trainers to integrate strengthening phases in the learning sequence. Indy is a tool and the learning scenarios built upon it are an expression of the pedagogical strategy trainers will choose. The best practices are yet to be explored.

However, Indy has yet to be experimented in a real learning session. In order to confirm our hypotheses on the pedagogical benefits of the proposed approach, a comprehensive study should be undertaken. Despite several promising studies, the empirical data is still sparse to fully understand the transfer mechanisms from virtual reality to real life, especially for professionals in an industrial context.

CONCLUSION

We presented Indy, a collaborative virtual reality application using gamification to help professionals acquire navigation skills needed to work in industrial facilities.

Indy consists in a treasure hunt in a virtual building, making learners cooperate in order to find an objective. It is designed to be integrated into existing training methods, and to be used by a trainer with a group of learners.

This paper summarized the design principles of Indy and its key functionalities offering pedagogical benefits.

Figure 1 :

 1 Figure 1: Overview of the elements of the building mockup used in Indy: (a) 360° photographs, (b) detailed floor maps, (c) 3D model (from Hullo et al. [9]).

4 A LEARNING SESSION WITH INDY 4 . 1

 41 Software overview Indy was developed with Unity3D. It works as a network application, and provides three different clients depending on the users' role:  Trainer (desktop): shows the floor maps and gives extended views and controls over the scenario.  Learner (immersive): shows the 3D model in a HMD (HTC Vive).  Learner (desktop): shows the floor maps, 360° photos and the 3D model. The learner can walk in the building using the mouse and the keyboard.

Figure 2 :

 2 Figure 2: Interface allowing the trainer to place obstacles in the building.

Figure 3 :

 3 Figure 3: Trainer watching learners. He/she can either be visible or invisible.

Figure 4 :

 4 Figure 4: Trainer's interface showing different learners' point of view.

Figure 5 :

 5 Figure 5: Debriefing interface, showing leaners' itineraries during the hunt, and the timeline on the bottom.

ACKNOWLEDGMENTS

This work is funded by EDF R&D, and was developed by Florian Gavel during his 6 months internship.


Thanh-Hai To

Andrzej Duda

Simulation of LoRa in NS-3: Improving LoRa Performance with CSMA

Keywords: LoRa, LoRaWAN, collision ratio, energy consumption, network simulation

In this paper, we consider two research issues. First, we present a NS-3 module that simulates the behavior of LoRa in an accurate way. To validate the module, we compare its results with measurements on a real-world testbed and with measured values reported by other work. We also show that the module correctly represents the capture effect that lowers the packet drop rate due to collisions. Second, we want to improve the performance of LoRa devices while not impacting energy consumption, the aspect that usually is not taken into account in the literature. We use the simulator to evaluate CSMA (Carrier Sense Multiple Access), a simple enhancement to LoRaWAN that lowers the collision ratio. The simulation results show that CSMA considerably lowers the collision ratio while only slightly increasing energy consumption. We also observe that CSMA presents lower energy consumption than LoRa for a large number of devices. Another advantage of CSMA consists of increased throughput and larger network capacity because the ETSI restrictions on the duty cycle do not longer apply.

I. INTRODUCTION

LoRa has become an interesting technology for lightweight smart sensing in the Internet of Things (IoT) [START_REF] Lora | A Technical Overview of LoRa and LoRaWAN[END_REF]. It belongs to the new class of LPWAN (Low Power Wide Area) networks and defines a specific radio layer based on the Chirp Spread Spectrum (CSS) modulation and a simple channel access method called LoRaWAN [START_REF] Sornin | LoRaWAN Specification v1.0.2[END_REF]. The LoRa operation depends on a set of parameters: i) BW (Bandwidth), a range of spectrum for transmissions, ii) SF (Spreading Factor), the chirp rate that controls the bit rate and reliability (higher SF means lower bit rate and lower BER, Bit Error Rate), and CR (Coding Rate) that defines the ratio of the redundant information for Forward Error Correction (FEC). The LoRa CSS modulation results in low sensitivity enabling transmissions over long distances: a range of several kilometers outdoors and hundreds of meters indoors. Depending on the duty cycle of LoRa devices, their lifetimes may become very long, for instance 17 years for a node sending 100 B once a day [START_REF] Morin | Comparison of the Device Lifetime in Wireless Networks for the Internet of Things[END_REF].

LoRaWAN [START_REF] Sornin | LoRaWAN Specification v1.0.2[END_REF] defines an access method to the radio channel similar to ALOHA: a device wakes up and sends a packet to the base station (Gateway in the LoRa terminology) right away. The difference with pure ALOHA is the variable packet length in LoRa. This choice of the access method highly impacts the capacity of LoRa and its scalability to a large number of devices. Several authors studied these aspects [START_REF] Georgiou | Low Power Wide Area Network Analysis: Can LoRa Scale?[END_REF], [START_REF] Augustin | A Study of LoRa: Long Range & Low Power Networks for the Internet of Things[END_REF], [START_REF] Adelantado | Understanding the Limits of LoRaWAN[END_REF], [START_REF] Reynders | Range and Coexistence Analysis of Long Range Unlicensed Communication[END_REF], [START_REF] Haxhibeqiri | LoRa Scalability: A Simulation Model Based on Interference Measurements[END_REF], [START_REF] Mikhaylov | Analysis of capacity and scalability of the lora low power wide area network technology[END_REF], [START_REF] Bor | Lora for the internet of things[END_REF], [START_REF] Goursaud | Dedicated Networks for IoT: PHY/MAC State of the Art and Challenges[END_REF], [START_REF] Ochoa | Evaluating LoRa Energy Efficiency for Adaptive Networks: From Star to Mesh Topologies[END_REF]. The main conclusions to draw from the analyses are the following:

• the range of the LoRa network is limited to several kilometers, for instance: i) less than 10% of loss rate over a distance of 2 km for SF 9-12 and ii) more than 60% of loss rate over 3.4 km for SF 12. The coverage probability drops exponentially as the number of contending devices grows.

• the number of devices in a cell can be relatively large, but they are limited to sending a few bytes of data per day.

• the ETSI regulations of the 868 MHz ISM band set limits on the maximum duty cycle to 0.1% or 1% in the 863 -870 MHz ISM band (depending on the selected sub-band), which also limits the throughput of devices and the overall network capacity.

• the LoRaWAN operation similar to ALOHA results in a high level of packet losses due to collisions as the number of devices increases. • the impact of collisions is significantly mitigated by the capture effect in which some transmissions that benefit from a stronger signal are successful despite of collisions. Surprisingly, almost all the previous papers only consider performance aspects and do not take into account energy consumption of devices, a critical aspect in many applications.

Our research goal is to find a means for improving the LoRa performance in terms of packet delivery rate, collision ratio, throughput, and energy consumption. To design enhanced access methods, we need a tool for quickly evaluating potential schemes for a large number of devices and explore a large design space. Contrary to many papers that used ad hoc LoRa simulators in their analyses, we have decided to build upon NS-3 [START_REF]NS-3 is a discrete-event network simulator[END_REF], a well established tool in the networking community. We have developed a module that simulates the LoRa behavior with a sufficient level of details to obtain meaningful results. We validate the module by comparing its results with measurements on a testbed and by comparing them with the measured values from other work.

The objective of the energy efficient operation of LoRa devices along with the goal of improved performance makes the design of a new access method particularly difficult. Many known random access approaches such as CSMA/CA used in 802.11 networks require increased wake-on periods of operation, which leads to increased energy consumption. As the first step in improving LoRaWAN, we propose to consider a simple enhancement that does not impact energy consumption-the CSMA principle consisting of testing the channel if it is used by another transmission before attempting to send a packet [START_REF] Kleinrock | Packet Switching in Radio Channels: Part I-Carrier Sense Multiple-Access Modes and Their Throughput-Delay Characteristics[END_REF]. The principle, also referred to as "Listen Before Talk (LBT)", appears in the ETSI regulations: without LBT, devices need to limit their duty cycles to 0.1% or 1% depending on the sub-band. Thus, if devices apply the CSMA principle, the limitation is released so devices can use higher duty cycles, which contributes to possibly increased throughput and larger network capacity. To further lower the collision ratio, we extend CSMA with CSMA-x in which a LoRa device tests the channel during interval x before transmitting a packet. If during the interval, there is no channel activity, the device can attempt a transmission. Listening to the channel during the interval increases the consumed energy, but it may avoid some collisions, thus reducing the overall energy consumption.

We use the NS-3 simulator of LoRa to evaluate CSMA and CSMA-x compared to pure LoRaWAN. The enhanced methods result in a much better collision ratio while only slightly increasing energy consumption. For higher loads, CSMA-x even shows an improvement with respect to LoRaWAN. They enable higher transmission rates by getting rid of the 868 MHz ISM band restrictions.

The organization of the paper is as follows. We start with discussing the related work in Section II. Section III gives an overview of LoRa, LoRaWAN, and the LoRa network architecture. In Section IV, we describe the NS-3 simulation framework for LoRa. Section V defines the operation of CSMA and CSMA-x. In Section VI, we present the results of the evaluation. Finally, Section VII concludes the paper.

II. RELATED WORK

Several authors studied the issue of limits to the capacity of LoRa and its scalability to a large number of devices. Georgiou and Raza [START_REF] Georgiou | Low Power Wide Area Network Analysis: Can LoRa Scale?[END_REF] provided a stochastic geometry framework for modeling the performance of a single gateway LoRa network. They showed that the coverage probability drops exponentially as the number of contending devices grows. They concluded that LoRa networks will become interference-limited rather than noise-limited in dense deployment scenarios because of the LoRaWAN access method.

Augustin et al. [START_REF] Augustin | A Study of LoRa: Long Range & Low Power Networks for the Internet of Things[END_REF] presented throughput measurements on a testbed showing: i) less than 10% of loss rate over a distance of 2 km for SF 9-12 and ii) more than 60% of loss rate over 3.4 km for SF 12. They also simulated the LoRa behavior for a larger number of devices and showed that it behaves closely to ALOHA with the maximum channel capacity of 18% and an increasing collision ratio: for a link load of 0.48, the ratio is around 60%.

Adelantado et al. [START_REF] Adelantado | Understanding the Limits of LoRaWAN[END_REF] explored LoRa from the point of view of the capacity and the network size. They observed that for low duty cycles, throughput is limited by collisions, whereas for higher duty cycle values, the maximum duty cycle set by the ETSI regulations prevents devices from increasing their packet transmission rates and limits throughput. For instance, for 1000 devices, the maximum packet rate per node is 38 pkt/hour (packets of 50 B) with the probability of successful reception of only 13%.

Reynders et al. [START_REF] Reynders | Range and Coexistence Analysis of Long Range Unlicensed Communication[END_REF] compared the performance of LoRa and Ultra Narrowband (UNB, SIGFOX-like) networks with regard to the range and coexistence. They showed that UNB MAC is slightly better than LoRaWAN: the latter discards both colliding packets at reception, while the UNB network enables reception of the strongest packet thanks to the capture effect. The maximal throughput of the network occurs for 10 5 devices in the network, but results in a packet loss of 63%.

Haxhibeqiri et al. [START_REF] Haxhibeqiri | LoRa Scalability: A Simulation Model Based on Interference Measurements[END_REF] investigated the scalability of LoRa in terms of the number of devices per gateway. They used a simulation model based on the measurements of the interference behavior between two nodes to show that when the number of nodes with the duty cycle of 1% increases to 1000 per gateway, losses increase to 32%. However, this level of the loss rate should be considered as low compared to 90% in pure ALOHA for the same load and it results from taking into account the capture effect, which apparently plays an important role in the LoRa behavior. We compare their measured packet loss rate and collision ratio with the simulation results.

Mikhaylov et al. [START_REF] Mikhaylov | Analysis of capacity and scalability of the lora low power wide area network technology[END_REF] showed that a LoRa cell can potentially serve a large number of devices, but devices are limited to sending only a few bytes of data per day. The majority of devices need to be located in the vicinity of the gateway: only less than 10% can reside at distances longer than 5 km. Another factor that limits scalability is the use of acknowledgements-as the gateway is subject to the same ETSI restrictions on the duty cycle, it cannot acknowledge each packet in a dense network.

Bor et al. [START_REF] Bor | Lora for the internet of things[END_REF] developed a LoRa simulation to study its scalability. They showed that a typical Smart City deployment can support 120 nodes per 3.8 ha, which is not sufficient for future IoT deployments. Other studies in the literature analyzed the performance of the LoRa modulation-Goursaud and Gorce [START_REF] Goursaud | Dedicated Networks for IoT: PHY/MAC State of the Art and Challenges[END_REF] considered other technologies (SigFox, Weightless, and RPMA by Ingenu) in addition to LoRa to highlight their pros and cons.

Ochoa et al. [START_REF] Ochoa | Evaluating LoRa Energy Efficiency for Adaptive Networks: From Star to Mesh Topologies[END_REF] proposed various strategies to adapt LoRa radio parameters to different deployment scenarios. Their simulation results showed that in a star topology, we can achieve the optimal scaling-up/down strategy of LoRa radio parameters to obtain either a high data rate or a long range while respecting low energy consumption.

All the analyses show a large space for possible improvement of the LoRa performance. Nevertheless, the proposals for enhanced access methods need to take into account energy consumption along with performance, which is our goal in the next sections.

III. LORA OVERVIEW

This section gives a short introduction to the LoRa physical layer, the LoRaWAN channel access method, and the network architecture.

A. LoRa Physical Layer

The LoRa physical layer is based on the Chirp Spread Spectrum modulation that provides low sensitivity needed for long communication ranges [START_REF] Berni | On the Utility of Chirp Modulation for Digital Signaling[END_REF]. Communication between end devices and gateways can take place simultaneously on multiple frequency channels. Each end device can transmit its packet with a specific SF (Spreading Factor). For a given SF, there are 2 SF chirps per symbol. Higher values of SF result in longer communication ranges. Typical values of bandwidth (BW) are 125, 250, and 500 kHz in the ISM 868 and 915 MHz bands [START_REF] Goursaud | Dedicated Networks for IoT: PHY/MAC State of the Art and Challenges[END_REF]. Sensitivity ranges from -136 dBm for SF 12 and BW of 125 kHz to -111 dBm for SF 6 and BW of 500 kHz. Coding Rate (CR) can be 4 5 , 4 6 , 4 7 , or 4 8 . For instance, for BW of 125 kHz and CR of 4 5 , the bit rate is 5468 b/s with SF 6 and 293 b/s with SF 12.

B. LoRaWAN

LoRaWAN defines three types of devices, namely Class A, B, and C. Class A devices use pure ALOHA protocol for the uplink. After sending a packet, a device listens to a response from the gateway during two downlink receive windows. Class A results in the lowest energy consumption, so we only consider this class in the paper. Class B devices aim at applications requiring more downlink traffic. The devices open extra receive windows at scheduled times by receiving a time-synchronized beacon from the gateway. Class C devices are always on and listen to the channel all the time, so their energy consumption is the highest. Only Class A must be implemented in all end devices.

Although the parameters of the LoRa physical layer and the operation of LoRaWAN mostly impact the performance of LoRa networks, the ETSI restrictions on the sub-band duty cycle appear as the key factor for limiting the network size [START_REF] Adelantado | Understanding the Limits of LoRaWAN[END_REF]. When a device transmits a packet in a given sub-band, it records the instant of the transmission and the time on the air [START_REF] Sornin | LoRaWAN Specification v1.0.2[END_REF]. It cannot use the same sub-band during interval T off SubBand :

T off SubBand = T imeOnAir DutyCycle SubBand -T imeOnAir (1)

C. LoRa Network Architecture

A typical LoRa network can be viewed as a "star-of-stars" architecture with three entities: end devices, gateways, and a network server. Gateways relay packets between end devices and the network server. End devices send packets to gateways over a single wireless hop and gateways connect to the network server over a high throughput backhaul network.

IV. LORA SIMULATION MODULE IN NS-3

We have developed a LoRa module for NS-3 based on some open source code shared by the Semtech company and other contributions.

A. LoRa Physical Layer

Knight implemented an open source physical layer of LoRa for end devices [START_REF] Knight | An Open-Source Implementation of the LoRa CSS PHY[END_REF]. As this source code is written in C and Python and provided with documentation, it is a very good reference for implementing the physical layer of LoRa module on NS-3. Blum et al. [START_REF] Blum | LoRa Modem with LimeSDRL[END_REF] also implemented the physical layer of LoRa by making use of software-defined radio hardware to receive and decode LoRa. It supports the data format used by the SX1272 LoRa chip.

We have developed the LoRa physical layer of our module based on these reference implementations.

B. LoRaWAN

There are three open source implementations of LoRaWAN by Semtech Corporation: i) an implementation of a LoRaWAN Class A and C end devices with SX1272/76 radio drivers [START_REF]LoRaMac Node[END_REF], (ii) the library corresponding to the driver/hardware abstraction layer for building a gateway using a concentrator board based on the Semtech SX1301 multi-channel modem and SX1257/SX1255 RF transceivers [START_REF]LoRa Gateway[END_REF], and iii) a LoRa packet forwarder running on the LoRa gateway for relaying packets to the network server over UDP/IP and from the network server to end devices over the LoRa link [START_REF]Packet Forwarder[END_REF].

The implementations have provided us an in-depth understanding of how to develop the NS-3 module for LoRaWAN class A end devices and gateways.

C. Existing NS-3 Components

The NS-3 framework already supports three components related to our goal: i) a pure ALOHA access method, ii) an implementation of the spectrum intended as an example for building custom models with the spectrum module, and iii) the energy framework for evaluating energy consumption of each node and the whole network.

We have first implemented the LoRa physical layer based on the existing open source implementations. Then, our module inherits the classes of the pure ALOHA access method to implement LoRaWAN class A devices. The NS-3 ALOHA access method is based on the MAC studied in the context of underwater sensor networks [START_REF] Parrish | System design considerations for undersea networks: Link and multiple access protocols[END_REF]. We have also reused the spectrum and energy modules of NS-3 with a number of modifications. We have used the ECC-33 propagation model developed by Electronic Communication Committee (ECC) [START_REF]ECC) within the European Conference of Postal and Telecommunications Administration (CEPT)[END_REF] designed for cellular and microwave communications in the frequency range from 700 MHz to 3.5 GHz. We have integrated this path loss model already implemented in NS-3 in the LoRa module. The source code is available at https://github.com/drakkar-lig/lora-ns3-module.

D. Energy Framework in NS-3

We use the energy framework implemented in NS-3 by Wu et al. [START_REF] Wu | An Energy Framework for the Network Simulator 3 (NS-3)[END_REF] to estimate energy consumption at a battery powered node or in the whole network. The framework reflects the following assumption on energy consumption.

All operations of devices are represented as states with their associated current draw values that determine power consumption. In case of the radio, we assume three states defined as transmit, receive, and sleep. The total energy consumption E is composed of the energy consumed in each state denoted as E tx , E rx , and E s , respectively: where T tx , T rx , T s , and P tx , P rx , P s are time spent and power consumption in the states for transmission, reception, and sleep, respectively. The energy consumption model reflects the operation of duty cycle MAC layers in a realistic way [START_REF] Martinez | The Power of Models: Modeling Power Consumption for IoT Devices[END_REF], [START_REF] Varga | GreenNet: an Energy Harvesting IP-enabled Wireless Sensor Network[END_REF]. The energy source is the power supply or batteries of network nodes. Connecting an energy source to a device energy model on an end device indicates that the end device draws power from the source. In NS-3, the energy sources supply power to devices on each node at a constant voltage of 3.3 V.

E = E tx + E rx + E s , (2)
E = T tx P tx + T rx P rx + T s P s , (3)

E. Validation of the LoRa Module

We have first validated the LoRa module on a testbed composed of four Semtech SX1272LM1BAP end devices and a Kerlink IoT Station used as a gateway (see Figure 1). We have run several experiments in a real world environment (see Figure 2) to measure the packet delivery rate and the collision ratio in function of the distance between end devices and the gateway using SF from 7 to 12. Figures 3 and4 show the comparison between the measured values and the results of a NS-3 simulation in the same topology. The presence of objects in the environment (e.g., buildings) is the main reason for a small difference between the measured and simulated values. We have also compared the results of the LoRa module with the measurements reported by Haxhibeqiri et al. [START_REF] Haxhibeqiri | LoRa Scalability: A Simulation Model Based on Interference Measurements[END_REF] for the same simulation parameters. The goal is to validate the capture model in the module because their measurements showed an important impact of the capture effect that lowers the packet drop rate due to collisions. We have used a threshold-based model available on NS-3 for the packet capture effect [START_REF] Lau | Capture Models for Model Packet Radio Networks[END_REF]. We have considered a scenario with the number of devices up to 1000. Figure 5 shows the packet loss rate and the collision ratio predicted by the simulation compared to the results by Haxhibeqiri et al. [START_REF] Haxhibeqiri | LoRa Scalability: A Simulation Model Based on Interference Measurements[END_REF].

V. IMPROVING LORA WITH CSMA

In this section, we present the principle of CSMA for LoRaWAN.

We assume N contending devices. When end device i ∈ N has a packet to send, it randomly chooses communication channel c i . It performs CCA (Clear Channel Assessment) to test if there is an ongoing transmission on the channel. Only when the channel is clear, the device starts its transmission, otherwise, it backs off-it goes to sleep for a random interval of time and attempts a transmission later on. The random interval is equal to k slots of 1 s, where k ∈ [0, 2 n -1] for the n th transmission attempt (the maximum value of n is set to 3). Figure 6 illustrates the principle.

Another variant of CSMA that we call CSMA-x is to listen to the channel for a small interval of time called CCG (Clear Channel Gap) before attempting a transmission. For instance, CSMA-10 corresponds to CSMA with an interval of 10 ms before a transmission. When the device detects a transmission during this interval, it backs off as in the basic CSMA. Figure 7 illustrates the principle.

To investigate the energy consumption at each node and in the whole network, we use Lithium-ion batteries as the type of energy sources and assign a device energy model to each end device. There are interactions between the energy source and the device energy model: the model consumes the energy from the source and the source notifies the model when its energy is completely drained.

The parameters of energy consumption in each state come from the datasheet of LoRa SX1272 [START_REF]Semtech SX1272[END_REF] and the Low Energy Consumption Design for SX1272/3/6/7/8 LoRa Modem [START_REF]Low Energy Consumption Design for[END_REF] (see Table I).

VI. SIMULATION RESULTS

In this section, we describe the scenario used in simulations and their results. We consider a scenario with one gateway and a number of end devices up to 10000 nodes. The simulation time is limited to 20000 seconds. The positions of end devices are randomly distributed around the gateway in the area of 10000 m x 10000 m. End devices send unconfirmed data frames. We simulate LoRaWAN, CSMA, and CSMA-10 (CSMA-x with the interval of 10 ms). Table I presents other parameters.

A. Simulation Scenario and Settings

B. Results

We have evaluated CSMA and CSMA-10 and compared their performance with LoRaWAN using NS-3 with respect to packet delivery ratio, collision ratio, and energy consumption. We have simulated a network with an increasing number of nodes from 1 up to 10000. If a packet is being received by the receiver and it is receiving the preamble of another packet, we consider this situation as the capture effect: if the value of Signal-to-Interference Ratio (SIR) of the new packet is above a specific threshold, then the current packet is dropped and the receiver locks on the new incoming packet.

Figure 8 presents the packet delivery rate for LoRaWAN, CSMA, and CSMA-10 (the ratio of the number of received packets by the gateway to the number of all packets transmitted by end devices). We can observe a much better rate for CSMA compared to LoRa. The figure also shows better scalability of CSMA-it obtains the packet delivery rate greater than 90% for more than 4000 devices. The rate for CSMA-10 is even higher than that of CSMA when the number of devices rises up to 1500 devices and more. Figure 9 presents the collision ratio for LoRaWAN and CSMA: the number of dropped packets because of collisions to the number of all transmitted packets. We can notice that the ratio rapidly increases for LoRaWAN with the number of contending devices. The increase of CSMA is much more moderate because devices send much less packets involved in collisions.

Figures 10,11, and 12 present the energy consumption of LoRaWAN, CSMA, and CSMA-10 in a network with the number of devices in ranges 0 -1000, 1500 -4000, and 5000 -10000, respectively. In range of 0 -1000 devices, the total consumed energy for CSMA is higher than that of LoRaWAN because of the interval before transmission during which a device is awake (see Figure 10). For the range of 1500 -4000, the difference is lower (see Figure 11) and the trend is inversed for the range of 5000 -10000: the energy consumption of CSMA is lower than that of LoRaWAN (see Figure 12). For the large number of contending devices, there are more ongoing transmissions so the first CCA detects a transmission and the device backs off. LoRaWAN devices spend too much time in collisions.

VII. CONCLUSION

This paper considers two research issues. First, we have presented a NS-3 module that simulates the behavior of LoRa in an accurate way. To validate the module, we have compared its results with measurements on both a real-world testbed and the measured values reported in other work [START_REF] Haxhibeqiri | LoRa Scalability: A Simulation Model Based on Interference Measurements[END_REF]. The comparisons show very good accuracy of the simulation results.

Second, we wanted to improve the performance of LoRa devices while not impacting energy consumption, the aspect that usually is not taken into account in the literature. We have used the NS-3 simulator to evaluate CSMA and CSMA-10, the proposed enhanced access methods that lower the collision ratio. The simulation results show that CSMA considerably lowers the collision ratio while only slightly increasing energy consumption. We also observe that CSMA-10 presents lower energy consumption than LoRaWAN for a large number of devices. Another advantage of CSMA consists of increased throughput and larger network capacity because the ETSI restrictions on the duty cycle do not longer apply.

Fig. 1 :

 1 Fig. 1: The LoRa testbed with 4 Semtech SX1272LM1BAP end devices and a Kerlink IoT gateway.

Fig. 2 :

 2 Fig. 2: The real environment for deployment the testbed. The distance from end devices to the gateway is increased gradually.

Fig. 3 :

 3 Fig. 3: Comparison between measured and simulated values: packet delivery ratio in function of the distance between end devices and the gateway.

Fig. 4 :Fig. 5 :

 45 Fig. 4: Comparison between measured and simulated values: collision ratio in function of the channel load.

Fig. 6 :

 6 Fig.6: Principle of CSMA: device j sends a packet after a CCA and backs off when channel is busy.

Fig. 7 :

 7 Fig. 7: Principle of CSMA-x: device j sends a packet after a CCA and a CCG interval.

Fig. 8 :Fig. 9 :

 89 Fig. 8: Packet delivery ratio in the whole network under LoRaWAN, CSMA, and CSMA-10.

Fig. 10 :Fig. 11 :

 1011 Fig. 10: Energy consumption per node under LoRaWAN, CSMA, and CSMA-10 for 0 -1000 nodes.

Fig. 12 :

 12 Fig. 12: Energy consumption per node under LoRaWAN, CSMA, and CSMA-10 for 5000 -10000 nodes.

TABLE I :

 I Power consumption in LoRa

	Ptx	419.6 mW
	Prx	44.06 mW
	Ps	4.32 µW

TABLE II :

 II Simulation parameters

	Voltage	3.3 V
	Frequency Band	868 MHz
	Code Rate	4/5
	Bandwidth	125 kHz
	Duty Cycle	1%
	Output Power	20 dBm
	Payload Length	10 bytes
	Preamble Length	12 symbols
	Number of channels 3
	Spreading Factor	SF7-SF12

VIII. ACKNOWLEDGMENTS This work has been partially supported by the French Ministry of Research projects DataTweet under contract ANR-13-INFR-0008-01, the PERSYVAL-Lab under contract ANR-11-LABX-0025-01, and the Use IoT project funded by Fonds Européens de Développement Régional (FEDER) No. N00011459 of the Auvergne-Rhône-Alpes region.


Marc Wolf
email: marc.wolf@tsoftemail.com

François Wolf
email: francois.wolf@dbmail.com

Corentin Le Coz
email: corentin0107@hotmail.fr

Wolf Marc
email: marc.wolf3@wanadoo.fr

Wolf François

Le Coz Corentin

Calculation of extended gcd by normalization

Keywords: extended gcd, normalizer, co-normalizer, minimizing one of the two coordinates, normal solution, linear diophantine equation, mixed Euclid algorithm

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

with equal to gcd of and . In number theory, this problem occurs in many situations like in the theory of corrector codes [1] or for the factorization of integers [2]. Moreover, it is the elementary component of the classical algorithm of Smith invariants computation of a matrix with integer coefficients, which allows the general resolution of the linear diophantine equations [3]. See also [4] for a recent application of the Euclid algorithm.

Notation

Let and be two integers, we denote the remainder of the Euclidean division of by , which belongs to by convention.

2 Extended GCD with and coprime integers.

The purpose of this section is to propose an algorithm to solve the extended gcd problem in the case of coprime integers. Let us take .

The normalizer

For any integer , we consider the following equation in and :

It is well-known that solutions exist if and only if , and that given a particular solution , the set of all solutions is equal to .

Definition 1. Assume . Then there exists a unique solution of verifying , which will be called the normal solution.

will be called the normalizer of .

Remark. Knowing , we can deduce , and therefore all the solutions of . Furthermore, if , , and if and , .

From the structure of solutions of , we get the following proposition:

Proposition 1. For any solution of , .

Definition 2. Under the same assumptions as definition 1, we can define the co-normalizer of to be the unique such that solves for some .

Arithmetic properties of the normalizer

Let .

Proposition 2. The normalizer is additive:

It is easily proved by summing the equations and . Corollary 1. The normalizer is multiplicative:

In particular:

From the previous propositions, we deduce that the normalizer is -linear in modulo , but for our algorithm we will only need the following corollary:

Corollary 2. We have:

Under certain assumptions, the normalizer may also be stable by division: Proposition 3. If is odd and is even, then and:

Proof. Assume odd, even, . The fact that will follow from the fact that we will write it as a linear combination of and .  If is even, is even as well, and so is . Therefore verify , which clearly implies .

 If is odd: o Either is odd, which means that is odd, so must be odd. o Or is even, in which case is even and so must be even too. In both cases, still verify , and , from which we deduce that .

Remark. Similar properties for the co-normalizer can be also shown.

We deduce from the above proposition the following algorithm, which will be part of the

Presentation of the algorithm

Solving the problem of extended gcd with and being coprime integers is equivalent to determining . The algorithm WWL1 proceeds in two steps: an initialization with the two values of given by the previous proposition, and then a descent loop using corollary 2 of proposition 2 to determine .

Once has been determined, the complete solution is obtained by calculating:

Validity of the algorithm

It can be noted that throughout the loop, we keep equal to the normalizer of . Furthermore, at each step of the loop, decreases, with and remaining positive. This proves the termination of the algorithm (the sequence of has to be finite). We deduce that at the end of the loop or . However, because , we deduce that remains constant equal to its initial value by hypothesis. Hence at the end of the loop, if was equal to , this would necessarily mean than , which is impossible: otherwise at the previous step we would already have one of the , which would mean that we should already have exited the loop.

If then , Else

, End If  we modify and so that they verify .

 we divide as many times as possible by .

If then

End If  we reassign and so as to have .

End While

 the loop is left when Return  the solution is returned

Proof. The same arguments as in the proof of WWL1 hold: decreases strictly along the loop, which ensures that it terminates, always remains the normal solution of along the loop, and stays equal to , so that when necessarily . Remark 1. Here the exit condition is somehow simpler but it actually means one more step than WWL1 when , which could be optimized away in the coprime case. Remark 2. The algorithm can be adapted to return the co-normalizer instead of the normalizer. This is left to the reader.

Conclusion

We have reduced linear Diophantine equations solutions to a single and unique integer, its normalizer. We have used this terminology to develop a solution of the extended gcd problem, which has the advantage of controlling the size of the final result as well as that of the intermediary steps, while remaining very simple to implement. Our benchmark with other algorithms (see appendix) suggested a similar complexity, but an average computational gain of 15% which makes it advantageous to use. Optimizing the algorithm was not our main concern for this article, however we discuss some further possible improvements at the end of the appendix.

• [1] R. P. Brent, H. T. Kung, Systolic VLSI arrays for polynomial GCD computations. IEEE Trans. Comput. C-33, 731-736 (1984)

Contents1

  Introduction ............................................................................................................................... 2 1.1 The problem of extended gcd ............................................................................................. 2 1.2 Notation .........................................................................................................................

1 Introduction 1.1 The problem of extended gcd

	Let	and	be two integers, the extended gcd problem consists in finding three
	integers ,	and	such that:
			......................................................... 7
	6 Appendix: gcd algorithms .......................................................................................................... 8

..... 2 2 Extended GCD with and coprime integers. .................................................................... 2 2.1 The normalizer .............................................................................................................. 2 2.2 Arithmetic properties of the normalizer ............................................................................. 3 2.3 Presentation of the algorithm ............................................................................................. 4 2.4 Validity of the algorithm ..................................................................................................... 5 3 General case ............................................................................................................................... 6 4 Conclusion .................................................................................................................................. 7 5 References .........................................................................

Acknowledgments: We would like to thank François-Xavier Villemin for his attentive comments and suggestions.

 -----------------------------

General case

It is impractical to impose for and to be coprimes, therefore we will adapt the previous algorithm to the general case where and are any numbers. Experimental tests also highlighted that it is more advantageous to calculate at the same time as the normalizer during the finite descent. Hence our algorithm will return, when it is possible, the unique triplet satisfying both conditions and . If and are both even, a first step is to factor them both by the greatest power of possible (which boils down to a cheap bit shift), so that one of them necessarily becomes odd. From now on, let us assume by symmetry that is odd.

Algorithm 3: Function Div2(u,v,c): Given integers verifying the conditions , and , returns a triplet verifying the same conditions, obtained by dividing as many times as possible by .

While do If then

Else

End If End While Return

Proof. This is an extension of the algorithm Div1, exploiting directly the result of the second corollary of proposition 2.

.

Appendix: gcd algorithms

We present here two popular gcd algorithms (not in their extended version for the sake of simplicity), namely the Euclidean algorithm [5] and its binary version [6]. We note that the steps followed by our WWL2 algorithm are exactly the same as a combination of those two, and as stated in the conclusion of our article outperforms on average those two.

Algorithm 5: (classical Euclid algorithm) EulerGCD: Given two integers, returns their gcd.

While do

End While Return

This algorithm is the most self-contained, however it performs quite badly due to the high numerical cost of the Euclidean divisions. The next one takes advantage of the inexpensivity of divisions by 2 (bit shifts):

Algorithm 6: (binary Euclid algorithm) BinaryGCD: Given two integers, returns their gcd.

While do

End While  Factorization of a power of

While do

While do

End While

End While Return

As stated before, the following mixed Euclid algorithm is a mixture of the two previous ones, which only keeps a single Euclidean division: On average, the cost of this single division is compensated by a significant decrease in the number of remaining binary algorithm steps. For large integers, it could be interesting to check whether performing more than one Euclidean division yields yet a more significant gain. Another idea would be to trigger an Euclidean division when the binary algorithm is likely to perform many substractions in a row (typically if is large and odd, and is small and even).