Mohammed Dahhani
email: mohammed.dahhani@enseeiht.fr

André-Luc Beylot
email: beylot@enseeiht.fr

Gentian Jakllari
email: jakllari@enseeiht.fr

An Analytical Model for Assessing the Performance of IEEE 802.11ad Beamforming Training

In the race for Gigabit wireless links, IEEE introduced 802.11ad, an amendment aimed at delivering Gbps capacities in a WLAN setting by leveraging the 60 GHz band. The key innovation of the standard is its beamforming training protocol. Executed periodically at the beginning of every beacon interval, it enables the formation of directional links. To address contention during the uplink part of beamforming training, 802.11ad introduced A-BFT (Access-BeamForming Training), an Aloha-inspired, two-level backoff race. While central to the functionality of 802.11ad networks, the performance of A-BFT, however, remains poorly understood.

In this paper, we propose an analytical finite-population model for evaluating the performance of 802.11ad A-BFT under the assumption of ideal channel conditions. After using an opensource simulator to demonstrate its accuracy, we use our model to assess the performance of A-BFT. We find that a counterintuitive, quit-easily/be-lazy approach by the stations leads to the best overall beamforming training performance.

For the remainder of the article we will use interchangeably the terms SSW slot and slot, and the terms A-BFT period, A-BFT and period.

I. I

IEEE has emerged as a leader in mmWave technology with the introduction of 802.11ad [START_REF]Enhancements for Very High Throughput in the 60 GHz Band[END_REF], an amendment aimed at offering Gigabit capacities in a WLAN setting. 802.11ad products operating in the 60 GHz band can be now found on high-end laptops, routers [2] and, most recently, on smartphones [START_REF] Aggarwal | A first look at 802.11ad performance on a smartphone[END_REF]. However, if mmWave currently offers several GHz of mostly idle spectrum, it is because it suffers from poor propagation characteristics, making directional antennas essential [START_REF] Jog | Many-to-many beam alignment in millimeter wave networks[END_REF]. As a result, neighbor discovery, the most basic networking primitive, becomes particularly challenging [START_REF] Zhou | Fastnd: Accelerating directional neighbor discovery for 60-ghz millimeter-wave wireless networks[END_REF]. While with traditional, omni-directional antennas, simply broadcasting a beacon suffices to discover a station in range, with directional communications a catch-22 situation emerges. Discovering neighbors requires communication but communication requires knowing the location of potential neighbors so as to steer the signal beam in the right direction.

802.11ad addresses the directional neighbor discovery challenge by introducing a beamforming training protocol, executed at the beginning of every beacon interval. In short, it breaks the catch-22 using a two-phase process. First, the access point (AP) transmits a series of control packets in all possible directions (sectors in the standard's language) while stations receive in quasi-omnidirectional mode. A station receiving at least one of the control packets is able to identify the best sector the AP needs to use to reach it. It feeds this information back to the AP in the second phase, during which the roles are reversed. Stations transmit control packets in all sectors while the AP receives in quasi-omnidirectional mode. If the AP successfully receives a station's control packets, it can determine: a) the best sector to use to transmit to the particular station and b) the best sector the station needs to transmit to the AP. The process finishes with the AP feeding this information back to the station.

The downlink part of the 802.11ad beamforming training, with only the AP transmitting, is simple protocol-wise. In the uplink part, however, multiple stations may attempt to transmit their control packets to the same access point, leading to contention. To complicate matters further, stations transmit in directional mode, significantly limiting the efficiency of carrier sensing at resolving contention. 802.11ad's answer to this challenge is Access-Beamforming Training (A-BFT), a novel, Aloha-like protocol using a two-level backoff race. A-BFT is divided into a fixed number of time slots, with stations allowed to transmit at the beginning of a slot without checking if the channel is busy. Should a collision occur, stations execute a backoff using a fixed contention window equal to the number of slots in A-BFT. If a station fails to transmit its control packets after attempting a maximum number of times, it transitions into idle mode. An idle station is not allowed to transmit and has to enter the idle-state backoff. It selects at random a number between zero and a maximum contention window, set by the standard, and decrements it once per beacon interval. At the end of the backoff, the station can transition back to active.

Fundamental to 802.11ad, the performance of the beamforming training protocol remains poorly understood. To the best of our knowledge, the basic question of how long it will take for a link to be established between a station and an access point -equivalent to computing the time it takes for a station to successfully transmit its control packets during A-BFTremains open. As the first IEEE mmWave technology, recently making its way into consumer products, the primary focus has been on evaluating the overall performance of 802.11ad networks using off-the-shelf hardware and/or simulations [START_REF] Nitsche | Boon and bane of 60 ghz networks: Practical insights into beamforming, interference, and frame level operation[END_REF]- [START_REF] Saha | A detailed look into power consumption of commodity 60 ghz devices[END_REF]. A few works have considered A-BFT but it has been mostly using simulations [START_REF] Akhtar | Efficient network level beamforming training for ieee 802.11ad wlans[END_REF], [START_REF] Zhou | Enhanced random access and beam training for millimeter wave wireless local networks with high user density[END_REF]. The analytical models introduced in [START_REF] Wu | Enhance the edge with beamforming: Performance analysis of beamformingenabled wlan[END_REF], [START_REF]Channel access in a-bft over multiple channels[END_REF] cannot address A-BFT's basic question.

In this work, we aim at introducing an analytical model allowing to assess the performance of A-BFT as a function of its three parameters: 1) the number of slots in A-BFT, N s ; 2) the maximum number of failed attempts in active state, M axA; 3) the idle-state contention window, M axI. While A-BFT is inspired by Aloha, analyzing it presents new and distinct challenges due to its innovative two-level backoff race and the fact that it is interrupted regularly by the data transmission phase of 802.11ad. In short, we address this challenge by introducing the concept of a virtual slot and a discrete-time Markov chain that accurately models A-BFT.

Our main contributions may be summarized as follows: • We introduce the first analytical finite-population model that can compute the time it takes for a station to successfully transmit its control packets during A-BFT as a function of its three parameters, under the assumption of ideal channel conditions (Section III). The model is simple but nevertheless accurate, modeling exactly what occurs over an A-BFT period and aggregating over k periods. • We develop a simulator that implements the details of A-BFT as defined in the standard, available to the community as open-source [START_REF] Dahhani | IEEE 802.11ad a-bft beamforming training simulator in python[END_REF], and use it to demonstrate the accuracy of our analytical model (Section IV-A).

• We use our model to assess the performance of A-BFT and find that a counter-intuitive quit-easily/be-lazy approach by the stations leads to the best beamforming training performance (Section IV-B). This finding demonstrates the value of an analytical model at optimizing an 802.11ad network deployment using the parameters provided by the standard.

II. C

Channel access in 802.11ad is coordinated using a schedule communicated by the access point (AP). Channel time is divided into Beacon Intervals which in turn are subdivided into access periods. As shown in Fig. 1, the first two access periods are dedicated to beamforming training. First the access point, during Beacon Transmission Interval (BTI), transmits control packets in all possible directions while stations receive in quasi-omnidirectional mode. The roles are reserved during Access-Beamforming Training (A-BFT). The Announcement Transmission Interval (ATI) is then used to exchange management frames and schedule data communication for the DTI period. Finally, the Data Transmission Interval (DTI) is used for data and control frame exchange (Table I summerizes the different acronyms).

Among the mechanisms introduced by 802.11ad, beamforming training is the most novel and, as a result, the least understood. We focus on it in the following.

A. 802.11ad beamforming training

The 802.11ad physical layer defines a set of directional or quasi-omnidirectional antenna radiation pattern called transmit sectors or receive sectors. Beamforming training is the challenge of identifying, from the pre-defined set, the best transmit and receive sectors for establishing a link between two devices.

To address this challenge, 802.11ad introduces the Sector Level Sweep (SLS) [START_REF]Enhancements for Very High Throughput in the 60 GHz Band[END_REF]. It comprises 3 phases: 1) Initiator Sector Sweep (ISS) occurs during BTI. The AP sends a beacon using each of its transmit sectors, including in the beacon the sector id, while stations receive in quasiomnidirectional mode. A station receiving one or more In the next section, we focus on A-BFT, the non-trivial part, protocol-wise, of the beamforming training.

B. Access-Beamforming Training (A-BFT)

As shown in Fig. 1, the A-BFT period is divided into a fixed number of Sector-Level Sweep (SSW) slots . Stations compete for the available SSW slots to perform their Responder Sector Sweeps (RSS). If more than one station execute their RSS during the same SSW slot, collisions will occur at the AP, which is receiving in quasi-omnidirectional mode. When an RSS attempt fails, the station will have to retry. Two questions emerge regarding the execution of RSS's during A-BFT: 1) How does a station gain access to a SSW slot? 2) What happens when collisions occur? IEEE 802.11ad addresses these questions using a two-level medium access method. As depicted in Fig. 2, during A-BFT, a station can be in one of the two states: Active, attempting , decremented at the end of each A-BFT period, starting with the following beacon interval. Rule 8 : A station exits idle state and can attempt an RSS in an A-BFT period only if its idle state backoff count is zero at the start of that period. Rule 9 : A station that succeeds its RSS attempt in an A-BFT period can perform a new RSS in the following period.

f ail & exceed succeed f ail & exceed backof f idle == 0 backof f idle > 0
A1 A2 A3 AMaxA-1 AMaxA A 1 I1 I2 IMaxI-2 IMaxI-1 . . . . . . . . . pfail 1 psucc pexceed 1 pfail 2 psucc pexceed 2 . . . psucc pexceed 3 pfail (M axA-1) psucc pexceed (M axA-1) pexceed (M axA) psucc (1 -r0) × pexceed 1 r0 × pexceed 1 psucc pfail 1 r1 1 -r1 . . . 1 -r2 r (M axI-2) 1 -r (M axI-2) 1 ×(1 -r0) ×r0

C. Problem statement

Given the two-level channel access in A-BFT, the fundamental question becomes:

How long does it take for a station to succeed its RSS and, therefore, complete its beamforming training?

Next, we address this question using an analytical model.

III. A A-BFT

In this section, we consider an 802.11ad network with N stations and N s slots per A-BFT period and introduce an analytical model for computing the time it takes for a station to succeed its RSS ( § II-C). To this end, we introduce a discretetime Markov chain that models the A-BFT channel access rules introduced in § II-B.

A. A Markov chain for A-BFT

Let M axA be the maximum number of failed attempts before a station enters idle state and, M axI, the maximum number of periods a station stays in idle state.

We define X(t) to be the random variable representing the state (A 1 , ..., A M axA , A 1 , I 1 , ..., I M axI-1 ) of a station in A-BFT period t. A discrete time scale is adopted: t and t + 1 correspond to the beginning of two consecutive A-BFT periods. A state I k refers to a period where the station is idle and, states A k and A 1 , a period where the station is active. Assuming the probability of a successful RSS, p succ , is constant, we can model the process {X(t), t ∈ N} with the discrete-time Markov chain depicted in Fig. 3. We describe each of its states as follows:

• A station is in state A 1 when it performs a new RSS or after succeeding a previous one. A station is in state A k if it did not succeed its ongoing RSS for k -1 periods since the last time it became active. As long as the station has not reached the maximum number of consecutive failed attempts, M axA, it transitions to state A k+1 with a probability of p f ail k .

• If an active station exceeds M axA consecutive failed attempts k -1 periods after the last time it became active, the station becomes idle with probability p exceed k .

• A station that becomes idle uniformly picks a random number between 0 and M axI-1. It chooses 0 with probability 1-r 0 , becoming active in the next period (state A 1 ). Otherwise, it stays idle for at least one period (state I 1 ), with probability r 0 .

• If a station is idle for k > 0 consecutive periods (state I k ), it stays idle in the next period with probability r k (state I k+1 ), where

r k = 1 - 1 M axI-k , k ∈ [0, M axI -1].
A station that stayed idle for M axI consecutive periods becomes active in the following period with probability 1 (state A 1 ).

• A station transitions to state A 1 after exiting an idle state I k or in one of the following situations: i) after becoming idle in the same period or multiple periods since the RSS started ii) after becoming active then failing M axA attempts in the same period. In these two cases, if the station picks 0 in the idle backoff window it ends up in state A 1 , resuming the same RSS -as opposed to state A 1 in which the station starts a new one.

B. Computing RSS success time and stationary distribution

The Markov chain in Fig 3 has a finite state space and is ergodic. Therefore the steady-state distribution π exists and is unique. Assuming M is the transition matrix, we find π by numerically solving π = πM .

Let

T 1 = inf {t ≥ 1, X(t + u) = A 1 | X(u) = A 1 }
be the random discrete variable representing the first return time to state A 1 . The average number of periods before a station succeeds its RSS corresponds to E(T 1 ). State A 1 is by definition recurrent. Therefore, the expected first return time to state A 1 -the RSS success time -can be simply derived using the steady-state distribution π.

In the following, we compute the one-step transition probabilities of our Markov chain.

C. Computing the transition matrix

Model Parameters: Computing the stationary distribution requires the knowledge of the transition matrix. In this section we will compute the one-step transition probabilities p succ , p f ail k and p exceed k .

Success in a period: Let N a be the number of active stations in a period and S(N a ) the discrete random variable representing the number of successful RSS in a period with N a active stations. The dependence in t is omitted. We define the success rate in a period as

T succ (N a ) = E(S(N a )) N a (1)
Let T idle be the probability a station is in idle state. As per rule Rule 6 ( § II-B), not all N stations contend in an A-BFT period. Some stations can be in idle state. Thus, the number of successful RSSs in a period depends on N -N a , the number of stations in idle state. If we know the probability of a station being in idle state, T idle , and the success rate in a period with N a active stations, T succ (N a ), it is possible to compute the success probability of an RSS as:

p succ = N i=1 N -1 i -1 (1 -T idle ) i-1 T succ (i) T N -i idle (2)
Failure and entering idle state: The probability of an active station becoming idle in a given period depends on the number of periods spent in active state (Rule 5) and the number of its consecutive failed attempts (Rule 6). However, taking into account these dependencies makes the problem of computing the probability of a station becoming idle highly complicated. Thus, we introduce an approximation:

Approximation : Our model assumes that the success of a station's RSS in an A-BFT period is independent of the number of periods for which the station has been active. We assume that it only depends on the number of active stations at the beginning of the period and ignore the probability that a station becomes idle before the end of a period. The impact of this approximation on the precision of the end results ( § IV) is small.

Let L be the random variable representing the number of periods since the last time a station was active until it becomes idle. L takes its values in [1, M axA], {L = 1} beeing the event according to which the station fails M axA attempts in the same period it became active (or the RSS started). Using the above approximation, the conditional probability of a station becoming idle (k -1) periods since the last time it became active can be computed as follows:

p exceed k = P {"fail" ∩ "M axA attempts k periods later"}

= (1 -p succ ) × P {L = k} (3)
The probability of a station in state A k failing its RSS but staying active in the following period is given by: p f ail k = P {"fail" ∩"M axA attempts k periods later"}

= (1 -p succ ) × (1 -P {L = k}) (4)
Therefore, constructing the transition matrix requires: 1) T succ , a station's success rate in a period. 2) the PDF of L, the number of periods before entering idle.

1) Success rate in an A-BFT period:

In this section, we focus on what happens within one A-BFT period and propose a theoretical model based on enumerative combinatorics to find the law of S(N a ), the number of successes in a period with N a active stations.

Finding the success rate τ succ is about identifying how many stations successfully performed RSS by the end of a period. To do so, we introduce the virtual slot, a concept we use to model how stations retry an RSS in a period.

The virtual slot φ: According to rule Rule 4, if a station fails an RSS attempt, it can attempt again in the same period. However, if there are not enough slots, the RSS operation is postponed to the next period -Rule 5. As depicted in Fig. 4, in this case, we can imagine that, if by the end of A-BFT the station's transmission backoff counter does not reach 0, the RSS attempt will happen in a virtual slot φ outside A-BFT. Slot φ is useful to keep count of how many stations were not able to attempt again in the same period.

At the beginning of a period, N a stations contend over N s slots by uniformly selecting a number in [0, N s -1]. We define the initial state of a period as being the way stations are distributed among slots as a result of this uniform random backoff. The space of all initial possible states is {n = (n 1 , ..., n Ns )/ Ns i=1 n i = N a }, where n i represents the number of stations that chose slot i. This is the set of weak compositions of N a into N s parts, therefore, Na+Ns-1 Na possible initial states exist [START_REF] Stanley | Enumerative Combinatorics[END_REF].

Let n = (n 1 , ..., n Ns , 0) be a possible initial state. As shown in Figure 4, if multiple stations choose the same slot, i, a collision occurs and they are distributed uniformly among the remaining slots, including the virtual one. The resulting intermediate state, n , can be found using an iterative method on the number of stations, n i , in slot i. If n i ∈ {0, 1}, we simply get n = n. If n i > 1, let v j for j > i be the number of colliding stations that pick slot j. We get:

               n j = n j 1 ≤ j < i n i = 0 j = i n j = n j + v j i < j ≤ N s n φ = v φ Ns j=i+1 v j + v φ = n i
This operation is carried out iteratively until the end of the period. Note that the conflict is not resolved for slot N s since colliding stations in this slot have no chance of succeeding in the ongoing period.

Let Ω be the space of all final states and, Π n , the probability of final state n. To compute the number of successes in a period, we need to construct all possible final states and count how many slots have exactly one RSS attempt. Therefore, the probability distribution of S(N a ) is given by:

           P {S(N a ) = k} = 0, k > min(N s , N a ) P {S(N a ) = k} = n∈Ω Ns i=1 1 {n i =1} =k Π n , k ≤ min(N s , N a )
Π n = P {n = (n 1 , ..., n Ns , n φ )}, n ∈ Ω (5) From ( 1) and ( 5) it is possible to derive T succ (N a ), the success rate in a period . However, this requires the knowledge of the final state space probabilities. To this end, we introduce Algorithm 1:

Algorithm 1 Probability of final states

Ω ← {n = (n 1 , ..., n Ns , 0)/ Ns i=1 n i = N a } for each slot i ∈ [1, N s -1] do for each state n in Ω do Π n ← Probability of state n if slot i has n i > 1 stations then v ← distribute n i over N s + 1 -i remaining slots n ← v + n Π v ← Probability of state v Π n ← Π n + Π n × Π v Remove n from Ω and add n Π n ← 0 end if end for end for return Π n , n ∈ Ω (i)
It checks slot by slot for each state whether or not multiple stations chose the same slot (n i > 1).

(ii) If a collision occurs in slot i, the algorithm considers all possible weak compositions v of n i stations into N s -i + 1 slots. (iii) It computes the probability Π v and saves the resulting intermediate state. (iv) After all collisions are resolved (slots 1 to N s -1), all states in Ω become final states. Using Algorithm 1 and Equation 5, we are able to compute Π n for all possible final states and therefore deduce the success rate in a period T succ (N a ) with N a active stations.

2) Characterization of idle states: In this section, we characterize the number of failed attempts of an RSS in a period and extend it to k ≤ M axA periods.

Let ξ be a station's count of the number of failed RSS attempts. ξ is incremented by 1 when the ongoing RSS fails and it is reset to 0 when it succeeds or when the station becomes idle [START_REF]Enhancements for Very High Throughput in the 60 GHz Band[END_REF]. When ξ reaches M axA, the station enters idle state and reschedules an attempt for ulterior periods.

Let F (k) for k ∈ [1, M axA] be the random discrete variable representing the number of failed attempts of a given RSS k -1 periods since the last time the station became active. F (k) takes values in [0, M axA] and F (1) corresponds to the number of failed attempts the station performed in the same period the station became active (or started the RSS). The conditional probability of an active station transitioning to idle (k -1) periods since the last time it became active, i.e. P {L = k} can be derived by taking into account the fact that a station attempts at least once in a period:

   P {L = k} = P {F (k) =M axA} 1-k-1 j=1 P {F (j) =M axA} P {L = 1} = P {F (1) = M axA} (6)
Clearly, by identifying the law of the number of failed RSS attempts, we can deduce the probability distribution of L, the number of periods after which an active station becomes idle.

The law of the number of RSS attempts in a period: Let R be the discrete random variable representing the number of failed attempts a station performs in a given A-BFT period. And let R (j) be the stochastic process representing the number of RSS attempts (1, ..., min(j, M axA)) a station performs between the first slot and slot j of the same period. {R (j) , j ∈ [1, N s ]} is a discrete-time finite-state Markov chain. By analysing its probability distribution at instant j = N s , we can derive the probability distribution of R as follows:

                     P {R = t} = P {R (Ns) = t}, t = min(N s , M axA) P {R = t} = 1 - Ns j=t+1 P {R (j) = t + 1} - t-1 i=1 P {R = i}, t < min(N s , M axA) P {R = 1} = 1 - Ns j=2 P {R (j) = 2} (7)
Since an active station's RSS attempt in a period is governed by a uniform random backoff, the state probabilities of R (j) are straightforward. From [START_REF] Saha | Fast and infuriating: Performance and pitfalls of 60 ghz wlans based on consumer-grade hardware[END_REF] we can fully characterize R.

The law of the number of RSS attempts after k periods:

Let u k (t) be the PDF of F (k) such that:

u k (t) = P {F (k) = t}, k ≤ t ≤ M axA (8)
Recognizing that F (1) = R, we get:

u 1 (t) = P {R = t} u k (t) = u k-1 * u 1 (t) (9)
where * is the linear convolution operator and, u 1 (t), the probability a station fails t attempts in the period it becomes active (or starts the RSS). Using equations ( 5) to (9), we can derive the probability distribution function of L.

IV. P E

The performance evaluation is organized in two parts. In the first part, we use computer simulations to validate our analytical model. In the second part, we assess the performance of 802.11ad beamforming training using the analytical model.

A. Model Validation

Methodology: We conduct Monte Carlo simulations to validate our mathematical model. To this end, we developed a discrete-event time-driven custom simulator in Python that implements the A-BFT medium access protocol [START_REF] Dahhani | IEEE 802.11ad a-bft beamforming training simulator in python[END_REF]. It closely follows the IEEE 802.11ad protocol details for each independently transmitting station. For the experiments, we use the default values recommended by the standard for the number of slots per period, the maximum number of successive attempts and the idle backoff window (see Table III). All simulation results are obtained with a 95% confidence interval lower than 0.004. We consider the transmission channel ideal so that RSS failures are due to collisions only. We model an RSS as a single frame transmission occupying one slot. We abstract the feedback mechanism ( § II) and instead keep count of the Results: The objective of our model is to evaluate the average number of A-BFT periods -equivalent to the number of beacon intervals -until a station succeeds its Responder Sector Sweep (RSS). Thus, we first focus on this metric.

Figure 5 shows the average number of periods until an RSS succeeds (E(T 1 )) , as computed by our model and via simulations. The data leads to two findings: First, which is also the main objective of this experiment, data shows that the analytical model is very accurate -analytical and simulation results practically coincide. For high loads (16 < N < 24), for example, the gap is less than 0.7 periods. However, a second finding emerges: for dense networks, using the default parameters recommended by the standard, it may take a station over a dozen beacon intervals to successfully execute an RSSa relatively high number. We elaborate more on this in § IV-B.

Next, we focus on the different components of our analytical model: the probability distribution of L, the success rate, τ succ , the success probability of an RSS, p succ , and the probability of a station being in idle state, τ idle .

Figure 6 shows that the calculations of the analytical model closely match what we observe in the simulations. In the case of the probability distribution of L, Fig. 6b, and τ idle , Fig. 6d, the results show almost a perfect match. The difference observed in Fig. 6a is due to the pessimistic approximation we use in our model. Namely, we consider that the number of active stations stays constant within the same A-BFT period. Thus, we do not take into account the stations that reach the maximum number of consecutive failed attempts and stop contending before the period ends. As a result, the success rate given by our model is lower than that of the simulation for a high number of nodes. It is interesting to point out that especially for a high number of nodes Fig. 6c shows that the model's calculation of p succ matches better the simulations. This can be explained by the fact that the model slightly overestimates τ idle , Fig. 6d. As τ succ and τ idle both contribute to the value of p succ , the model's underestimation of the former is compensated by its overestimation of the latter, leading to the observed result.

B. Assessing 802.11ad beamforming training

In this section, we use our model to analyze the performance of the IEEE 802.11ad beamforming training and more specifically the Access-Beamforming Training (A-BFT), its most challenging component.

We consider the time it takes for a station to successfully execute its Responder Sector Sweep (RSS) the key performance metric of A-BFT. Therefore, we focus our attention on assessing how the three A-BFT parameters -M axA, M axI, N s -affect this metric. Methodology: To assess the impact of the three A-BFT parameters on its performance we proceed by first fixing the values of two of the parameters to those recommended by the 802.11 standard. We then use our analytical model to compute E(T 1 ) for different values of the third parameter and different numbers of stations. Recall from our Markov Chain, Fig. 3, that T 1 is the time of the first return to A 1 , the state to which a station transitions after it succeeds its RSS.

Impact of MaxA: Figure 7 shows the number of A-BFT periods necessary for a station to succeed its RSS as a function of M axA and the total number of stations. Two interesting findings emerge. The first is counter-intuitive -for a high number of stations, using a small M axA, thus abandoning the effort to transmit the RSS more easily and transitioning to idle, leads to the quickest success. Second, we find that using the standard-recommended value of 8 for M axA increases by almost 40% the time it takes for a station to succeed its RSS in dense topologies.

Impact of MaxI: Figure 8 shows the number of A-BFT periods necessary for a station to succeed its RSS as function of M axI and the total number of stations. The conclusions the data point to follow a similar pattern with what we observed in Fig. 7. Counter-intuitively, accepting to spend a longer time in idle mode leads a station to succeed its RSS faster in denser topologies. A M axI of 16 divides by more than two the time it takes for a station to succeed its RSS when compared with using a M axI of 4. Furthermore, the standard-recommended value of 8 for M axI is clearly not the best choice.

Quit-easily/Be-lazy: To further elucidate the findings above, in Fig. 9 we depict the performance of A-BFT as function of M axA and M axI for dense networks. The data shows that indeed combining the smallest value of M axA -Quit-easilywith the highest value of M axI -Be-lazy -leads to the best A-BFT performance. This seemingly counter-intuitive result can be explained by a careful examination of the A-BFT medium access rules ( § II-B). As per Rules 1 and 4, an active station always backs off using N s as contention window, a constant value that does not adapt to congestion. When congestion does occur (for N > N s ), this mechanism does nothing to relieve it. Thus, retrying for a high number of times, a high M axA, is counterproductive. In idle mode, on the other hand, stations back off using M axI as contention window, Rule 7. A high value of M axI will relieve congestion. Therefore, a policy of quiting active mode easily (small M axA) and using a high backoff value while in idle (high M axI) leads to the best A-BFT performance.

Impact of N s : Finally, we assess the impact of the size of A-BFT on its performance. Figure 10 shows that, as expected, an A-BFT with a larger number of slots enables a station to succeed its RSS faster. Note, however, that since the duration of A-BFT period is proportional to N s , any increase to N s will reduce the size of the Data Transmissions Interval (DTI), significantly reducing the degree of liberty as to its duration. M axA and M axI, on the other hand, only impact A-BFT, making them the most useful parameters for optimizing its performance.

V. R W Evaluation of IEEE 802.11ad: As the first IEEE mmWave technology available off-the-shelf, 802.11ad has been the subject of multiple performance evaluation studies. A large body of work makes use of off-the-shelf 802.11ad hardware to carefully evaluate different aspects of the protocol and/or networks constructed around it [6]- [START_REF] Saha | A detailed look into power consumption of commodity 60 ghz devices[END_REF]. However, none of these works have looked at the performance of A-BFT (accessbeamforming training).

Certain works [START_REF] Kiran | Saturated throughput analysis of ieee 802.11ad edca for high data rate 5g-iot applications[END_REF]- [START_REF] Hemanth | Performance analysis of contentionbased access periods and service periods of 802.11ad hybrid medium access control[END_REF] have introduced analytical models to evaluate IEEE 802.11ad by extending the classic model by Bianchi [?]. However, all these studies are focused on the CSMA part of the DTI (data transmission interval). A-BFT uses no carrier sensing and, thus, cannot be evaluated by these models. Extending these works to model A-BFT is not straightforward.

Evaluation of 802.11ad A-BFT:

A few works have focused on the evaluation of the A-BFT part of 802.11ad, however, it has been mostly using simulations [START_REF] Akhtar | Efficient network level beamforming training for ieee 802.11ad wlans[END_REF], [START_REF] Zhou | Enhanced random access and beam training for millimeter wave wireless local networks with high user density[END_REF]. To the best of our knowledge, only [START_REF] Wu | Enhance the edge with beamforming: Performance analysis of beamformingenabled wlan[END_REF], [START_REF]Channel access in a-bft over multiple channels[END_REF] introduce analytical models to study A-BFT. [START_REF] Wu | Enhance the edge with beamforming: Performance analysis of beamformingenabled wlan[END_REF] analyzes the success probability of an RSS. However, it makes several simplifying approximations regarding the protocol: a) it assumes a station attempts at most one RSS per A-BFT period, when according to the standard [START_REF]Enhancements for Very High Throughput in the 60 GHz Band[END_REF] a station makes as many attempts as possible; b) it assumes the size of A-BFT adapts to the number of stations when according the standard it is fixed; c) it replaces the uniform backoff procedure a station performs when entering idle state with simply using its expected value. Our work makes no such approximations. Furthermore, unlike our work, their model cannot be used to study the average delay before a station succeeds its RSS. The authors in [START_REF]Channel access in a-bft over multiple channels[END_REF] study the probability of collision during A-BFT, however, it is limited to the case in which the number of stations is lower than the number of time slots in A-BFT. Our analytical model places no restriction on the number of stations.

Evaluation of other wireless access protocols:

There is a rich literature on the performance of wireless access protocols, some going back to the classic works on Aloha [START_REF] Abramson | The aloha system: Another alternative for computer communications[END_REF], from which 802.11ad A-BFT was inspired. However, the introduction by A-BFT of the dual active-idle race and the fact that A-BFT is interrupted regularly by the other access periods, including DTI, makes this prior research non applicable. For example, [START_REF] Kleinrock | Packet switching in a multiaccess broadcast channel: Performance evaluation[END_REF] introduced a finite population model to evaluate the delaythroughput performance under stable and unstable [START_REF] Lam | Packet switching in a multiaccess broadcast channel: Dynamic control procedures[END_REF]- [START_REF] Metcalfe | Steady-state analysis of a slotted and controlled aloha system with blocking[END_REF] slotted Aloha channel conditions. However, the constant retry probability assumption as well as the joint assumption on active population size and transmission probability are not applicable to A-BFT due to the idle states. The zero-order approximation of the infinite population model in [START_REF] Abramson | The aloha system: Another alternative for computer communications[END_REF], [START_REF] Roberts | Aloha packet system with and without slots and capture[END_REF], extended in [START_REF] Lam | Packet switching in a multi-access broadcast channel in a computer network[END_REF], describes the maximal capacity of a slotted Aloha channel based on a Poisson arrival process. These assumptions, however, are not valid for modeling medium access in the A-BFT because the number of contending stations in the A-BFT is finite and depends on the failure history.

VI. C

We presented an analytical model for assessing the performance of beamforming training in 802.11ad networks. Our model is simple yet models accurately the details of A-BFT, the non-trivial part, protocol-wise, of the 802.11ad beamforming. Once we demonstrated the accuracy of the model using a simulator we have made available as open-source, we evaluated the performance of A-BFT as a function of its three parameters. Our results showed that a counter-intuitive, quit-easily/be-lazy approach leads to the best beamforming training performance.

A

This work was supported in part by the Agence Nationale de la Recherche under the ANR JCJC CiTADEL grant. R

Fig. 1 :

 1 Fig. 1: IEEE 802.11ad beacon interval. A-BFT is composed of several random-access SSW slots. A station gaining access transmits multiple SSW frames, followed by a SSW-feedback by the AP.

Fig. 2 :

 2 Fig. 2: The two states of a station.

Fig. 3 :

 3 Fig. 3: Markov Chain model for the Access-Beamforming Training (A-BFT). A station can be in active state (A 1 , A 2 , ...) attempting to succeed its RSS, or in Idle state (I 1 , I 2 , ...), attempting to transition to active state.

Fig. 4 :

 4 Fig.4: Final states: n i stations collide in slot i and contend over the remaining N s -i + 1 slots. A station that chooses slot φ won't succeed its attempt in the current period.

  slots per period (Ns) 8 max. attempt (M axA) 8 idle backoff win. (M axI) 8

Fig. 5 :

 5 Fig. 5: Analysis vs. Simulation: The average number of A-BFT periods until an RSS succeeds, E(T 1 ).

  Fig. 6: Analysis vs. Simulation: Components of the model using the standard's default values.

Fig. 7 :Fig. 8 :

 78 Fig. 7: The virtue of quiting easily: While the standard recommends 8 as the default value for M axA, quitting after 4 failures leads to succeeding significantly earlier in dense networks.

Fig. 9 :

 9 Fig. 9: Performance of A-BFT as function of MaxI and MaxA for dense networks (N > N s ). The Quit-easily/Be-lazy approach offers the best performance.

Fig. 10 :

 10 Fig. 10: Increasing the period size leads to succeeding early. However, it also reduces the time reserved for data transmission (DTI) in each beacon interval.

TABLE I :

 I BEAMFORMING ACRONYMS

	Symbol Description
	BI	Beacon Interval
	BTI	Beacon Transmission Interval
	A-BFT	Access Beamforming Training
	ATI	Annoucement Transmission Interval
	DTI	Data Transmission Interval
	SSW	Sector Level Sweep
	ISS	Initiator Sector Sweep
	RSS	Responder Sector Sweep
		Active state	Idle state

TABLE II :

 II MODEL PARAMETERS Πn Probability of state (n1, .., nN s , n φ )

	Symbol Description
	N	Total number of stations
	Na	Number of active stations
	Ns	Number of slots in an period
	M axA Max. number of consecutive failed attempts
	M axI	Idle backoff window size
	S	Number of success in a period
	X(t)	State of station in period t
	T1	Time of first return to A1
	τsucc	Success rate in a period
	τ idle	Probability a station is idle
	L	Number of periods until station becomes idle
	F (k)	A station's failed attempts after k periods
	u k (t)	P {F (k) = t}
	R	A station's failed attempts in a period
	R (j)	A station's failed attempts until slot j

TABLE III :

 III A-BFT default parameters.


How to classify permanent grasslands? Conclusions from a French national network

Keywords: Typology, grassland, taxonomy, functional classification, services

Since agronomists and ecologists began to study permanent grasslands, they have set various classifications to describe the variety of grasslands or to suggest clear interpretations of their functioning. First classifications due to phytosociologists described the structures of plant communities, and their relations with environment. Recent advances in plant ecology introduced typologies based on life plant traits. It is now clearly established that ecosystemic services provided by grasslands (ie grass production or red list species protection) cannot be predicted by the same characteristics of vegetation. We aimed to compare these contrasted ways of classifying grasslands, estimating the redundancy of vegetation characteristics. Therefore, a national network of 178 grasslands was studied in 2009 with a common experimental protocol to determine the botanical composition. The main result is the low redundancy between taxonomical and functional (i.e. life traits) characteristics of vegetation, despite a dependence between these variables. Single criterion based classifications must thus be avoided for the full prediction of grassland ecosystem services.

Introduction

Permanent grasslands occupy almost 40% of the land used by the European Union. A huge variety of pedoclimatic and management conditions result in a wide variety of the types of vegetation. Agronomists and ecologists have described this diversity for a long time, with various criteria: presence, frequency, dominance or abundance of species, sward biomass or height, forage quality, etc. More recently, progress in functional ecology lead to measure plant life traits. On this basis, diverse classifications of permanent grassland have been established, depending on their initial purpose: describe, understand or predict. It is clearly stated that the agronomical and ecological services delivered by permanent grasslands greatly depends on the characteristics of the vegetation [START_REF] De Bello | Towards an assessment of multiple ecosystem processes and services via functional traits[END_REF]. For example, forage yield is closely linked to criteria like grasses proportion and type, legumes proportion influence forage quality, and the maintenance of patrimonial and ordinary biodiversity rely on botanical composition. The aim of the present work is to study the potential redundancy of some criteria involved in the classification of permanent grasslands. One key issue of this approach is to assess the need to perform a multicriteria vs monocriteria study of grassland to predict agroecosystem services.

Materials and methods

A network of 178 French permanent grasslands was set in 2009, covering a broad climatic and edaphic gradient in France. It included most pedoclimatic areas from oceanic to alpine conditions and covered most of grassland type in France, excluding Mediterranean conditions. Altitudes of grassland range from sea level to 2000 meters. This environmental gradient was crossed with a management gradient, defined by a diversity of farm systems (dairy or meat cattle and sheep) and management practices (type and number of uses, type of animals and livestock density, type and amount of fertilization). Use of grasslands was divided into three categories: 44.38% only grazed, 12.36% only cut and 43.26% grazed and cut. The botanical composition was observed once during the spring 2009: full list of present species within an homogeneous station (1000 to 5000 m 2 ), and visual estimation of species dominance in 8 quadrats (0.25m 2 ) randomly located in the station. Floristic relevés were managed with eflorasys [START_REF] Plantureux | e-FLORA-sys, a website tool to evaluate the agronomical and environmental value of grasslands[END_REF], which was used to calculate the following 6 functional criteria (mean value for the grassland, weighted by species dominance): Leaf Dry Matter Content (LDMC), Specific Leaf Area (SLA), Leaf Life Span (LLS), Date of Inflorescence (DI), Number of Oligrotrophic species (NOS) (linked to ecological value) and the Proportion of Entomophily Species (PES) (linked to the pollination service). Two classifications of grasslands were set to determined taxonomic criteria, respectively based on Presence (PRE) and Dominance (DOM) of species. This was achieved with a Multiple Component Analysis (MCA) followed by an ascendant hierarchical classification, and a tree cut with a characterization of classes. To compare the criteria we made: i) a linear regression between the 6 functional characteristics, ii) a variance analysis between the 2 taxonomic characteristics (qualitative variable) and the 6 functional characteristics (quantitative variables), and iii) a Khi2 test between DOM and PRE.

Results and discussion

Main results for the links between vegetation characteristics are presented in table 1. Most of relations show a link between criteria, except for 2 criteria poorly linked to the others: the date of inflorescence and the proportion of entomophily species. Except for NOS with taxonomic criteria, the coefficients of determination are quite low, demonstrating that none of these criteria can be used to predict another one. Among functional criteria, LDMC is linked to SLA and LLS, as previously demonstrated by [START_REF] Ansquer | Convergence in plant traits between species within grassland communities simplifies their monitoring[END_REF]. The relation between others functional criteria are either not statistically significant (i.e. LDMC and DI) or with a poor quality model explaining less than 30% of the variance. The relations between taxonomic criteria (DOM and PRE) and functional criteria are always significant (except for DOM and SLA). The same trend can be observed between DOM and PRE. Despite of the value of the khi 2 test, the similarity between classifications of grasslands based on presence and dominance was weak. All these relations mean that the criteria are not independent, but the conclusion of the redundancy of the criteria cannot be drawn. The example of LDMC will be used to demonstrate this statement. Figure 1a confirms the good link between LDMC and SLA, whereas Figure 1b indicates that the number of oligrotrophic species is not closely related to LDMC, despite a statistical significance in table 1. Figures 1c and1d show that even if some types of grassland (classified on presence or dominance) have higher or lower LDMC than other types, the variability within types can be as higher than the variability between types.

Conclusion

The criteria used to classify grassland that we have tested are not redundant (except for LDMC vs SLA and LLS), but at the same time are not fully independent. Taxonomical and functional characteristics are not redundant and each category of criteria provide specific information on sward features.. Thus, to predict from vegetation characteristics the agronomical and ecological services provided by grasslands single criterion based classifications must be avoided.

Aknowledgments: Funding for this project has been supplied by the French Ministry of Agriculture (CASDAR program). The program is managed by « Institut de l'Elevage » (Eric Pottier) in collaboration with 33 members of agricultural extension services. Plant life traits were provided by Pablo Cruz, INRA Toulouse, France

Figure 1 :

 1 Figure 1: Relation between Leaf Dry Matter Content (mean life trait calculated at community level) and 4 criteria to classify permanent grasslands

Table 1 :

 1 Relations between vegetation taxonomic and functional characteristics of the French network of 178 permanent grasslands, Values indicate the coefficients of determination and are associated to statistical significances (ns, *=P<0.05, **=P<0.01 or ***=P<0.001)

		LDMC	SLA	LLS	DI	NOS	PES	DOM
	Leaf Dry matter Content (LDMC)	.
	Specific Leaf Area (SLA)	0.33***	.
	Leaf Life Span (LLS)	0.42*** 0.05**	.
	Date of inflorescence (DI)	ns	0.16***	ns	.
	Number of oligotrophic species (NOS)	0.26*** 0.06*** 0.18***	ns	.
	Proportion of entomophily species (PES)	ns	ns	ns	0.09*** 0.02*	.
	Dominance of species (DOM)	0.41*** 0.14* 0.41*** 0.40*** 0.51*** 0.32***	.
	Presence of species (PRE)	0.29** 0.19*** 0.27*** 0.45*** 0.58*** 0.31*** Khi²=516