Anh Tuan Giang

Anthony Busson

Marco Di Renzo

Anh Tuan Giang •

Modeling and optimization of CSMA/CA in VANET

Keywords: Markov model, Packing problems, Wireless communications, Capacity, Vehicular ad hoc network, CSMA/CA

come

Introduction

In recent years, Inter-Vehicle Communication (IVC) has become an intense research area, as part of Intelligent Transportation Systems. It assumes that all or a subset of the vehicles is equipped with wireless interfaces, enabling communication between them. Although classical 802.11 can be used for IVC, specific technologies such as IEEE 802.11p [START_REF]IEEE Standard for Information technology-Local and metropolitan area networks-Specific requirements-Part 11[END_REF] (also referred to as Wireless Access in Vehicular Environments, WAVE) have been standardized to support these communications. This standard includes data exchanges between vehicles (ad hoc mode) and between infrastructure and vehicles. When the ad hoc mode is used, the network formed by the vehicles is called a Vehicular Ad hoc NETwork (VANET). VANET can be used by two families of applications. The first family is user oriented. In this case the VANET may be used to advertise restaurants, gas stations, traffic conditions, etc. But the most important applications are related to road safety. Information on road conditions, speed, traffic or alert messages (signaling an accident) may be exchanged in the VANET allowing drivers to anticipate dangerous situations [START_REF] Hartenstein | VANET Vehicular Applications and Inter-Networking Technologies[END_REF]. Data from embedded sensors may also be exchanged in order to increase the perception of the environment. This helps drivers to make appropriate decisions, as it increases the information available on road conditions and traffic situations. The amount of data which can be exchanged between vehicles is thus crucial. Design of these applications has to take into account the limited capacity of the VANET to control the quantity of information which can be sent to other vehicles. But, in such networks, capacity is mainly limited by the 802.11p spatial reuse. Indeed, as channels are shared by all the nodes, only a subset of nodes, sufficiently far from each others, can emit simultaneously.

Each node uses the 802.11p MAC layer mechanisms to determine if it can transmit or not. One of its sub-mechanisms is the Clear Channel Assessment (CCA) that sets if the medium is busy or idle. If the medium is idle for a given period the node transmits its frame, otherwise it postpones its transmission. This period depends on different timers and back-off that are not presented here. Fortunately, when nodes are sufficiently far from each others, they can transmit without interfering. Frame transmissions can thus be performed at different locations at the same time. The spatial reuse is related to this phenomenon, i.e. it measures the power of reusing the medium at different locations.

The model developed in this paper aims to evaluate the maximum spatial reuse of the 802.11p technology. Our approach can be presented through a simple example. Let us consider the vehicles depicted in Figure 1. We suppose that we are in a saturated case where all these vehicles wish to send a frame. The 802.11p MAC layer will allow each node to know if it can transmit or not. It is a distributed algorithm that tries to select nodes/vehicles in such a way that distances between concurrent transmitters are sufficiently great to avoid harmful interference between the transmissions. A snapshot of the simultaneous transmitters at a given time could correspond to the one in orange in Figure 1 (the scale of this figure is not realistic, as in practice, transmitters may be distant of several kilometers with the 802.11p technology). If we assume that these transmissions succeed, the network capacity is directly proportional to the number of simultaneous transmitters. The capacity is defined here as the maximum number of frames per second that the network is able to carry. We do not consider end-to-end throughput, but rather how many bits are transmitted/received at one hop in one second in the network. This definition of the capacity is thus strongly related to the spatial reuse. Obviously, it will depend on the considered region where nodes are distributed. Therefore, the capacity is normalized according to the considered geographical area. In this work, only roads or highways are modeled, and seen as a straight line. The capacity is thus normalized by the road length, and is expressed in Megabit per second and kilometer (M bit/s • km).

We argue that the main mechanism that sets the spatial reuse is the CCA mechanism. Therefore, our model considers only the CCA, and neglects the other 802.11 mechanism. We propose a Markovian model where locations of transmitting nodes are built recursively according to the rules used by the CCA. The equilibrium distribution of this Markov chain allows us to deduce the mean intensity of the concurrent transmitters, i.e. the mean number of transmitting nodes per kilometer, and an estimate of the capacity. The analytical model is compared to simulations performed with the network simulator NS-3 [START_REF]Network simulator 3 -ns3[END_REF]. In order to consider realistic conditions, we combine NS-3 with a traffic simulator (traffic of vehicles) that emulates drivers' behavior on a highway. Results show that our model is pertinent to estimate the VANET capacity, and to assess distribution of the distance between transmitters as well. Also, simulations allows us to highlight the impact of the other 802.11 mechanisms (that have not been modeled) on the capacity.

This work can be used in two different ways. The mean capacity can help to dimension the transmission rate of the applications in order to fit to the capacity constraints. Furthermore, we can deduce from the analytical formulas the parameters of the CSMA/CA that optimize the capacity. Such an optimization is proposed at the end of this paper.

The paper is organized as follows. In Section 2 we present the technological context of this study, in particular the CCA mechanism. Section 3 overviews related works dealing with capacity of ad hoc networks and VANET. Our contributions with regard to the existing approaches are highlighted in the same section. The model is presented in Section 4. Theoretical estimations of the capacity and simulation results are compared in Section 5. An example of CSMA/CA optimization is discussed in Section 6. We conclude in Section 7.

CSMA/CA in 802.11p

The IEEE 802.11p spectrum is composed of six service channels and one control channel. The control channel will be used for broadcast communications dedicated to high priority data and management frames, especially for safety communications. It should be the privileged channel used to disseminate messages from safety applications. The service channels can be used for safety and service applications, broadcast and unicast communications. The MAC layer in 802.11p is similar to the IEEE 802.11e Quality of Service extension. Application messages are categorized into one of four different queues depending on their level of priority. Each queue uses the classical CSMA/CA (Carrier Sense Multiple Access/Congestion Avoidance) mechanism to access the medium, but CSMA/CA parameters (backoff, etc.) are different from one queue to another in order to favor frames with high priority. In CSMA/CA, a candidate transmitter senses the channel before effectively transmitting. Depending on the channel state, idle or busy, the transmission is started or postponed. Clear Channel Assessment (CCA) is the mechanism used in CSMA/CA to determine if the medium is busy or idle. For the CSMA/CA protocols used in IEEE 802.11, CCA is performed according to one of these three methods.

1. CCA Mode 1: Energy above threshold. CCA shall report a busy medium upon detecting any energy above the Energy Detection (ED) threshold. In this case, the channel occupancy is related to the total interference level. 2. CCA Mode 2: Carrier sense only. CCA shall report a busy medium only upon the detection of a signal compliant with its own standard, i.e. same physical layer (PHY) char-acteristics, such as modulation or spreading. Note that depending on threshold values, this signal may be above or below the ED threshold. 3. CCA Mode 3: Carrier sense with energy above threshold. CCA shall report a busy medium using a logical combination (e.g. AND or OR) of Detection of a compliant signal AND/OR Energy above the ED threshold.

The CCA mechanism ensures that there is a minimal distance between simultaneous transmitters (except when a collision occurs). If the receiver is in the transmitter radio range, it guarantees a low interference level at the receiver location. Also, it limits the number of simultaneous transmitters in a given area, and thus the number of frames that can be sent per second. Therefore, there is a direct relationship between the spatial reuse imposed by the CCA mechanism and the network capacity. In the following we consider only the CCA mode 1, because it is the mode used in practice by the 802.11 interfaces.

Related works

A theoretical bound on the capacity of ad hoc networks was initially investigated in [START_REF] Gupta | Capacity of wireless networks[END_REF] where the authors prove that, in a network of n nodes, a capacity of Ω 1 √ n•log n is feasible. In [START_REF] Franceschetti | Closing the gap in the capacity of wireless networks via percolation theory[END_REF], the authors improved this bound and proved that an asymptotic capacity of

Ω 1
√ n is feasible. In these two articles, the capacity is reached by means of a particular transmission scheduling and routing scheme. In [START_REF] Dousse | Connectivity vs Capacity in Dense Ad Hoc Networks[END_REF] and [START_REF] Mhatre | On The Capacity of Ad-hoc Networks under Random Packet Losses[END_REF], more realistic link models have been used, both leading to a maximum asymptotic capacity of O 1 n . In particular, the authors of [START_REF] Mhatre | On The Capacity of Ad-hoc Networks under Random Packet Losses[END_REF] have shown that when there is a non-zero probability of erroneous frame reception, the cumulative impact of packet losses over intermediate links results in a lower capacity. Finally, it is shown in [START_REF] Franceschetti | Closing the gap in the capacity of wireless networks via percolation theory[END_REF], that when the path-loss function is bounded, the capacity is also O 1 n . However these last two results also suppose particular transmission scheduling and routing schemes. Moreover, all these studies deal with the asymptotic behavior of the capacity with regard to the number of nodes and do not propose precise estimates of this capacity.

On the other hand, in CSMA/CA based wireless networks, the transmission scheduling is distributed and asynchronous. It is not planned in advance and depends on the link conditions, interference, etc. at the time a node wants to emit its frame. The number of simultaneous transmitters is thus closely related to the CSMA/CA mechanism which limits the spatial reuse of the channel. The total number of frames sent in the whole network is thus bounded by a constant C whatever the number of nodes and the type of routing schemes. This constant has been evaluated in [START_REF] Busson | Point Processes for Interference Modeling in CSMA/CA Ad-Hoc Networks[END_REF]. Therefore, CSMA/CA multi hop wireless networks would offer a capacity of O 1 n . However all these studies focus on networks where nodes are distributed on the plane or in a 2-dimensional observation window. VANETs have very different topologies as the vehicles/nodes are distributed along roads and highways. Radio range of the nodes (about 700 meters with 802.11p in rural environment) being much greater than the road width, we can consider that the topology is distributed on a line rather than in a 2 dimensional space. Lines, grids or topologies composed of a set of lines (to model streets in a city) are thus more appropriate to model VANET topologies.

In [START_REF] Pishro-Nik | The Capacity of Vehicular Ad Hoc Networks[END_REF][START_REF] Nekaoui | Scaling Laws for Distance Limited Communications in Vehicular Ad Hoc Networks[END_REF], the authors propose a bound on VANET capacity. They show that when nodes are at constant intervals or exponentially distributed along a line, the capacity is Ω 1 n and Ω 1 n•ln(n) in downtown (city) grids. But it is also an asymptotic bound. Moreover, physical and MAC layers are unrealistic, radio ranges are constant and the same for all the nodes, interference is not taken into account and they assume a perfect transmission scheduling between the nodes. Thus, this bound cannot be applied to 802.11p networks.

In [START_REF] Du | Optimization models to characterize the broadcast capacity of vehicular ad hoc networks[END_REF][START_REF] Giang | A packing model to estimate VANET capacity[END_REF], an estimation of the number of simultaneous transmitters are proposed. The idea is thus similar to this paper. But this evaluation is based on numerical evaluation only, using integer programming [START_REF] Du | Optimization models to characterize the broadcast capacity of vehicular ad hoc networks[END_REF]. In [START_REF] Giang | A packing model to estimate VANET capacity[END_REF], only the mean intensity is derived and the distance between transmitters is not studied.

The contributions of this paper are as follows. We propose a simple model to evaluate the maximum capacity and the distribution between transmitters in a VANET. We propose a Markovian approach presented in Section 4. For this Markov chain, we deduce the transmitter intensity and the mean capacity. Also, we are able to compute the exact distribution of the distance between transmitters. To validate our approach, the theoretical results are compared to realistic simulations performed with NS-3. Simulations show that our approach is suitable for evaluating the maximum capacity of VANET precisely. It gives precise estimates of CSMA/CA performances, rather than just the asymptotic behaviors, and can consequently be used as a dimensioning or parameterizing tool.

A Markovian approach for CCA mode 1

We propose a model based on a discrete Markov chain taken its value with a continuous state space to model transmitters' location. First, we present assumptions on the radio model and interference. Then, we present the model and the main analytical results.

Radio models

For CCA mode 1, where the sum of signals from all the current transmitters (i.e. interference) is taken into account, assumptions about radio environment are required to model the signal strengths received from the current transmitters. With this CCA mode, the medium is detected idle for a node at X ∈ IR + if:

I(X) < θ (1)
where I(X) is the interference at X and θ is the ED threshold. Interference is generally considered as the sum of all interfering signals, but instead we define I(X) as:

I(X) = l(X -L) + l(R -X) (2)
where L and R are the locations of the two closest transmitters from X, the closest ones on the left and on the right. Function l(.) is the path-loss function. In our model, interference is thus computed from the signal strength of the two closest interferers. For the parameters of the 802.11p technology, this model is very similar to a model where interference from all the transmitters is taken into account. Indeed, as there is a significant distance between two successive transmitting nodes (due to the CCA mechanism), interference generated by distant interferers is negligible with regard to the closest ones (in 802.11p and in a rural environment, the second interferer in a given direction will be at least 1 km away from the first one).

We assume that the path-loss function satisfies the following conditions:

l(.) is continuous,

X 0 =0 X 1 S(X 1 -X 0 ) d max X 2 is distributed in this interval X 0 =0 X 1 S(X 1 -X 0 ) X 2 S(X 2 -X 1 ) d max X 3 is distributed in this interval X 0 =0 X 1 S(X 1 -X 0 ) X 2 S(X 2 -X 1 ) X 3  1  2  3
Fig. 2 Notations used in the model. The figure shows how the points X 2 and X 3 are distributed.

l(.) is a decreasing function, l(0) > θ, where θ is a positive constant (the ED threshold), lim u→+∞ l(u) = 0, there exists u ∈ IR + such that l(u) > θ and l(v) is strictly decreasing and differentiable for all v ∈ [u, +∞).

These conditions hold for path-loss functions with the form: l(u) = P T min(1, c/u α ) where P T is the transmitting power (with P T > θ), c and d are two positive constants (c > 0 and α > 2.0).

We define the packing constraints for the CCA mode 1. It corresponds to the constraints on the locations of the simultaneous transmitters that make the medium busy at every locations while respecting the CCA rule. When these constraints are satisfied, the medium is saturated and no new transmissions can take place. Let (Xn) n≥0 be the locations of the simultaneous transmitters. The CCA mode 1 packing constraints for (Xn) n≥0 are as follows:

-All the points have detected the medium busy (necessary condition to be a transmitter).

Therefore, I(Xn) < θ for all n. Of course, transmission from Xn is not taken into account in I(Xn). -The medium must be spatially busy (saturated case). Therefore, for all x ∈ IR + that does not belong to (Xn) n≥0 , I(x) ≥ θ.

The Markovian packing model

We propose the use of a simple Markov chain as a generic method to build tractable packing models on the line, i.e. models that satisfy the constraints given in the previous paragraph. Rather than putting the points randomly in the observed interval, we add the points one by one in an increasing order (from the left to the right of the interval) in such a way that they satisfy the packing constraints. Given {X 0 , X 1 , X 2 , ..., X n-1 }, the packing constraints define the interval where the next point Xn can be distributed. According to the first packing constraint, interference at X n-1 cannot be greater than θ, thus:

I(Xn) = l(X n-1 -X n-2 ) + l(Xn -X n-1 ) < θ (3)
It gives a lower bound on the distance Xn -X n-1 function of X n-1 -X n-2 . Let denote this bound as S(X n-1 -X n-2 ). S(u) is defined as the solution of

l(u) + l(S(u)) = θ (4)
The second constraint gives a upper bound on Xn -Xn -1: I(x) ≥ θ for all x in (X n-1 , Xn). Let dmax be this bound, it is solution of

2 • l dmax 2 = θ (5)
Thus, each point Xn (n > 1) belongs to the interval

[X n-1 +S(X n-1 -X n-2 ), X n-1 + dmax].
By convenience, we consider the sequence of random variables (ξ i ) i>0 defined as

ξ i = X i -X i-1
These random variables form a Markov chain, and takes their values in the interval [S(dmax), dmax] for all i > 0. But given ξ i-1 , the interval where ξ i is defined is limited to [S(ξ i-1 ), dmax]. It is possible to consider different distributions on this interval leading to different transmitter densities. They will always lead to model satisfying the packing constraints. The proposed model is thus quite general. As we do not know a priori the distribution of the distance between the transmitters, we have considered different distributions. The selected distribution has been set according to realistic simulations, and corresponds to a good approximation of what we observed while being mathematically tractable. This distribution is the linear distribution in [S(ξ n-1 ), dmax]. By linear distribution we mean an affine function, positive in [S(ξ n-1 ), dmax], null at dmax, and such that its integral on [S(ξ n-1 ), dmax] is 1. The pdf f ξn|ξn-1 (.) of ξn given ξ n-1 = s is then:

f ξn|ξn-1=s (u) = -2 (dmax -S(s)) 2 u + 2dmax (dmax -S(s)) 2 1 u∈[S(s),dmax] (6)
where 1 u∈[S(s),dmax] is the indicator function, equals to 1 if u ∈ [S(s), dmax] and 0 otherwise. In Figure 2, we present an example of this point process and the different notations. The stationary distribution of this Markov chain is given in the following theorem:

Theorem 1 The process (ξn) n≥0 defined in this section is a Markov chain. The stationary distribution of ξn is π(s) with:

π(s) = a • (dmax -s)(dmax -S(s)) 2 1 s∈[S(dmax),dmax] (7)
where a is a normalizing factor. The chain (ξn) n>0 converges in total variation to the distribution π(s) for all initial distribution of ξ 1 in [S(dmax), dmax]. If ξ 1 follows the stationary distribution π(.) then ξn follows the distribution π(.) for all n with n > 0.

Proof First, we prove that if the initial distribution of the Markov chain (the distribution of ξ 1 ) is π, ξn follows the distribution π for all n > 0. It suffices to show that π is the stationary distribution for this chain. We need to prove that

π(s) = dmax S(dmax)
f ξn|ξn-1=y (s)π(y)dy [START_REF] Busson | Point Processes for Interference Modeling in CSMA/CA Ad-Hoc Networks[END_REF] with π(s) = a (dmax -S(s)) 2 (dmax -s) and f ξn|ξn-1=y (s) given by equation [START_REF] Dousse | Connectivity vs Capacity in Dense Ad Hoc Networks[END_REF].

We get, dmax S(dmax)

f ξn|ξ n-1 =y (s)π(y)dy = dmax S(dmax) -2 (dmax -S(y)) 2 s + 2dmax (dmax -S(y)) 2 (9)
× 1 s∈[S(y),dmax] a(dmax -y)(dmax -S(y)) 2 dy (10) = 2a(dmax -s) dmax S -1 (s) (dmax -y)dy (11) = a (dmax -s) (dmax -S -1 (s)) 2 (12)
where S -1 (.) is the inverse function of S(.). This function exists since due to the properties of the function l(.), S(u) is bijective, differentiable and strictly decreasing in [S(dmax), dmax]. To conclude, note that S -1 (x) = S(x). We get, a (dmax -s) (dmax -S -1 (s)) 2 = a (dmax -s) (dmax -S(s)) 2 = π(s) [START_REF] Druitt | An introduction to microsimulation[END_REF] Also, we prove that ξn converges in total variation (it implies convergence in distribution) to π for any initial distribution of ξ 1 in (S(dmax), dmax]. We apply the Theorem 1 in [START_REF] Diaconis | On Markov Chains with Continuous State Space[END_REF] to prove this convergence. Since we have proved that π was the stationary distribution, it suffices to prove that the kernel P of this Markov chain is strongly π-irreducible, i.e. ∀x ∈ (S(dmax), dmax] and A ⊂ [S(dmax), dmax] with π(A) > 0, there is a positive integer n xA such that P n (x, A) > 0 ∀n ≥ n xA . In our case, π(A) > 0 with A ⊂ [S(dmax), dmax] is equivalent to ν(A) > 0 where ν(.) is the Lebesgue measure in IR + . The kernel P describes the transition probabilities, in our case it is formally defined as: [START_REF] Kazi | Modeling Drivers' Acceleration and Lane Changing Behavior[END_REF] with A ⊂ [S(dmax), dmax]. P n (., .) is the distribution of ξn (n > 1) given ξ 1 . It may be defined recursively:

P (x, A) = A f ξ2|ξ1=x (y)dy
P n (x, A) = dmax S(dmax) P (x, dy)P n-1 (y, A) (15)
First, note that if P m (x, A) > 0 with m > 0, P n (x, A) > 0 ∀n ≥ m. It can be easily proved by recurrence: Since P m (x, A) > 0 ∀y ∈ [S(dmax), dmax] and P (x, dy) = f ξ2|ξ1=x (y)dy with f ξ2|ξ1=x (y) > 0 ∀y ∈ [S(x), dmax], P m+1 (x, A) expressed as

P m+1 (x, A) = dmax S(dmax)
P (x, dy)P m (y, A) [START_REF] Diaconis | On Markov Chains with Continuous State Space[END_REF] will be positive if ν([S(x), dmax]) > 0, in other words if x > S(dmax). We prove now that P 2 (x, A) for all x ∈ [S(x), dmax] and A ⊂ [S(x), dmax] with ν(A) > 0. n xA can thus be chosen equal to 2. Let a = min{u, u ∈ A},

P 2 (x, A) = dmax S(dmax) P (y, A)f ξ 2 |ξ 1 =x (y)dy (17)
≥ dmax S(min(x,a))

P (y, A)f ξ 2 |ξ 1 =x (y)dy (18)
> 0

Indeed, P (y, A) > 0 and f ξ2|ξ1=x (y) > 0 for all y in [S(min(x, a)), dmax]. Equation (18) is thus positive when ν([S(min(x, a)), dmax]) > 0, i.e. when x > S(dmax). This proves that the Markov chain is strongly π-irreducible, and thus µP n converges in total variation to π when n → +∞ for any initial distribution µ in (S(dmax), dmax].

Approximation of the network capacity

In the following, we assume that ξ 1 follows the distribution π(.). The intensity λ of the point process (Xn) n∈I N , i.e. the mean number of points per unit length, is then given by:

λ = 1 E[ξ 1 ] = dmax S(dmax) sπ(s)ds -1 (19)
The inverse of this intensity λ is the mean distance between two consecutive transmitters. Hence, the number of simultaneous transmitters over a road with length L will be λ × L. Consequently, the capacity which is defined as the mean number of frames sent per second in the network can be estimated as:

Capacity(L) = λ × L T ( 20
)
where λ is the intensity given by equation ( 19), L is the length of the road and T is the mean time to transmit a frame. We could wonder if it is pertinent to consider the number of transmitted frames rather than the number of received frames for the capacity. In practice, the ED threshold is significantly less than the signal strength required for correct receptions. Therefore, when the transmitters respect the CCA rules, interference does not disturb reception and the number of transmitted frames corresponds approximately to the number of received ones. This will be validated by simulations in the next Section. Our simulations have shown that the main cause of transmission failures is collision, i.e. when a transmitter have not detected concurrent transmissions from close neighbors. It may happen when two nodes start their transmission at the same time, and were thus not able to detect each others. In this Section, we compare the theoretical evaluation of the capacity to simulations performed with the network simulator NS-3 [START_REF]Network simulator 3 -ns3[END_REF]. In the theoretical model, we consider the path-loss function used in NS-3. We compute for this path-loss the corresponding functions S(.), π(.), and the constants (dmax, λ, T , etc.). For the curves obtained from simulations, we compute a confidence interval at 95%. All of the nodes broadcast frames with a constant bit rate at 5M bit/s. It has been chosen equal to 80% of the interface transmission rate (6M bit/s) in order to saturate the network. All parameters are given in Table 1 and are set according to the IEEE 802.11p standard.

For the distribution of the vehicles location along the highway, we considered two scenarios: a scenario where the distances between vehicles are constant, and a scenario where vehicle locations are obtained from a realistic traffic simulator. This traffic simulator allows us to faithfully emulate driver behavior. On a highway, driver behavior is limited to accelerating, braking and changing lanes. We assume that there is no off-ramp on the section of highway. A desired speed is associated with each vehicle. It corresponds to the speed that the driver would reach if he was alone in his lane. If the driver is alone (the downstream vehicle is sufficiently far), he adapts his acceleration to reach his desired speed (free flow regime). If he is not alone, he adapts his acceleration to the vehicles around (car following regime). He can also change lanes if the conditions of another lane seem better. All these decisions are functions of traffic conditions (speed and distance) and random variables used to introduce a different behavior for each vehicle. This kind of simulation is called micro simulation [START_REF] Druitt | An introduction to microsimulation[END_REF], and the model we used which has been tuned and validated with regard to real data collected on a highway is presented in detail in [START_REF] Kazi | Modeling Drivers' Acceleration and Lane Changing Behavior[END_REF]. With the traffic simulator, we simulated a road/highway of 50 km with 2 lanes. The desired speed of the vehicles follows a Normal distribution with mean 120 km/h and standard deviation σ = 10. The distance shown on the x-axis in the figures corresponds to the mean distance between two successive vehicles.

a) Intensity and capacity results. In Figures 3 and4, we plotted the mean number of transmitters and the capacity. To compute the simultaneous number of transmitters, we counted the number of transmitters at a given time (at t = 2s). The capacity was computed as the number of sent and received bits. These quantities are easy to obtain from the NS-3 traces, as it logs time where a frame is received or sent. The different figures correspond to the two kind of traffic: constant inter-distance and trajectories generated by the traffic simulator. It is worth noting that the two traffic distributions (constant and traffic simulator) do not impact the results. This counter intuitive result is explained by the fact that the radio range and detection distance of the 802.11p technology are really greater than the mean distance between nodes. Moreover, we count the number of receptions for a close neighbors of the sender that limits the effect of interference, and favor receptions. Comments are thus the same for these two traffic scenarios.

For the number of transmitters evaluated from simulations, we distinguished transmitters provoking collisions from the other ones. In our context, we define a collision as a transmission for which the energy level from the other transmissions (that can be seen here as interference) is greater than the CCA threshold. A collision happens mainly when two nodes begin their transmission at the same time, and are thus not able to detect the transmission of each others. Also, it may be caused by a new transmission: a new transmission may increase interference level of the other transmissions in progress above the CCA threshold (even if the energy level is and stays less than the CCA threshold at the new transmitter). The number of simultaneous transmitters "without collisions" is thus the number of transmissions where the CCA threshold is respected during the transmission (that is not always the case in practice). Our model is based on this assumption, and thus estimates this quantity rather than the total number of transmitters. Nevertheless, we can observe a small gap between our model and simulations (in Figure 3(a) and 4(a)) because we do not count all transmitters above the CCA threshold whereas our model keeps a part of them. Indeed, it could suffice to remove one transmitter to allow several interfering nodes to satisfy the CCA threshold, but it is difficult to perform with NS-3. The number of transmitters "with collisions" exceeds our theoretical bound even for great vehicles inter-distance (small density), and increases considerably when inter-distances are less than 100 meters. Obviously, it is caused by the increasing number of concurrent nodes that wish to access the medium, and provoke collisions. The number of sent frames increases considerably with the vehicles density. But, the number of received frames fits perfectly to our theoretical bound, with only 4% of error for 50 veh/km (distance between vehicles=20 meters). Also, the theoretical bound is approached even for very low density traffic (from inter-distances = 500 meters in Figure 3(b) and 200 meters in Figure 4(b)). It empirically proves that our model does not offer good estimates of the number of transmitters as it neglects the other CSMA/CA mechanisms (backoff, etc.), but instead approximates very precisely the achievable capacity as, in practice, most of the transmissions that succeed are the ones that have suffered interference with an energy level less than the CCA threshold. b) Distribution of the distance between transmitters. In Figure 5, we plotted the distributions of the distance between transmitters obtained with NS-3, and the distribution π. The abscissa is [S(dmax), dmax]. The simulated highway is 50 km with 2 lanes and 10 vehicles per kilometer in average. We collected distances between transmitters from 100 samples. For each sample we collected the distances between the transmitters and we plotted the corresponding empirical probability density function. The shape of the distribution for the transmitters without collisions fits very well with the stationary distribution π(.). Nevertheless, we can observe a small difference when the function is decreasing. This difference is caused by samples greater than dmax. Indeed, it is very difficult to reach the absolute saturation of the network, where the medium is busy at every location, all the time. Therefore, sometimes there are regions where the medium is idle. Even if we simulated an important CBR for each source, nodes do not try to access the medium all the time because they only transmit when the backoff countdown reaches 0. However if we consider only samples less than dmax, we obtain the curve in Figure 5(b). This allows us to estimate the distribution in the saturated case since we neglect the network parts where the medium is idle. It appears that it fits with the theoretical distribution π(.) closely. If we compute the mean value of these samples, we obtain a mean inter-distance equal to 2.7 km corresponding to the mean inter-distance proposed in our model (2.64 km). It empirically proves that the theoretical model corresponds to a case where the CCA threshold is respected by all the nodes (no collisions), and where the medium is spatially busy. Even if these conditions are not feasible in practice, the proposed Markovian approach still offers accurate model and bound on the distribution and number of transmitters.

Optimization of the capacity

Our model can be used to tune the value of the CCA threshold in such way that it optimizes the capacity of the VANET. Indeed, as it is shown in Equation 20, we can achieve a higher capacity by increasing the spatial reuse, thus decreasing the value of the CCA threshold. A decrease of the CCA threshold allows more nodes to transmit at the same time but generates more interference. This threshold is thus a trade-off between spatial reuse and interference. It is possible to decrease the threshold as much as possible and have a maximum of simultaneous transmitters but it will lead to very short wireless links, where receivers have to be very close to their transmitters to receive properly the frames.

Therefore, to optimize the CCA threshold, we need to set a radio range where communications must be possible with a reasonable probability. For this distance, it is possible to optimize the capacity of the link as the best compromise between spatial reuse and link

ξ 1 ξ 2 d
Interfering nodes Transmitter Receiver Fig. 6 Our scenario: a transmission takes place between a receiver and a transmitter at a distance d of each others. We compute the FER for this link. Two interfering nodes apply the CSMA/CA rules, detect the medium idle and transmit, thus interfere.

quality/interference. In the rest of this Section, we propose a simple model using the analytical expression of the distance between transmitters to set the optimal value of the CCA threshold.

FER model

There are different models to compute the Frame Error Rate. For instance, we can consider that a frame is not received properly if the SINR (Signal on interference plus Noise Ratio) is less than a given threshold β [START_REF] Srikrishna Bhashyam | Feedback gain in multiple antenna systems[END_REF]:

F ER = P(SIN R ≤ β) (21)
In order to compute the SINR, we use the stationary distribution of the Markov chain developed in this paper. We consider a wireless link between a transmitter and a receiver at a distance d. The transmitter is supposed to be one of the nodes of the Markov chain. The other nodes interfere with this link. Under these assumptions, interference is mainly generated by the two nodes located on the left and right hand sides of our transmitter. This scenario is shown in Figure 6. Hence, SIN R can be expressed as: where N is a random variable modeling the noise, and ξ 1 and ξ 2 are the distances from the transmitter to the two interferers.

SIN R = l(d) N + l(ξ 1 + d) + l(ξ 2 -d) (22)
For the sake of simplicity, we consider N = 0 (but any value or distribution can be taken into account). Hence, (24)

Under the stationary regime, the distribution of ξ 1 is π(.) and the distribution of ξ 2 with ξ 1 = s is given by the transition density function. Therefore, If we take into account the Frame Error Rate, the capacity is given by:

C = λ T F ER ( 26
)
where λ is the intensity of the simultaneous transmitters (given by equation 19), T is the time to transmit a frame, and F ER is the Frame Error Rate for a given distance.

In Figure 7, we plotted the capacity with regard to the different values of the CCA detection threshold θ. We assumed that d = 700m that is the expected radio range of the IEEE 802.11p technology, and θ varies from -140dBm to -80dBm. For the simulations, still performed with NS-3, there was thus a distance of 700 meters between the sender and the receiver at which we count the number of received frames/bits. The other parameters are identical to the ones presented in Table 1. The threshold β on the SINR used in the FER computations has been inferred from simulations, and equal to 7.3. This FER model is significantly simpler than the one used in the simulations, which takes into account the Bit Error Rate as function of the SINR, modulation, and coding to determine if a frame is properly received. In the figure, it clearly appears that there is a theoretical optimal value for θ at -101 dBm. For the simulations, the optimal is also reached for -101 dBm, but the capacity does not decrease so clearly. The capacity stays more or less constant when the CCA threshold is in the interval [-102, -97] dBm, and drops to 0 for greater values. It proves that this optimal value of θ can be easily estimated with our method. We used a simple FER computation, but this optimization can be extended to more elaborated FER model.

Conclusion

In this paper, we have proposed a generic model, based on a Markov chain with a continuous state space to model locations of the simultaneous transmitters in a VANET. We derived closed-form formulas on the distribution of the distance between transmitters. Comparisons to realistic simulations showed that the model is accurate and that it is quite independent of the traffic distribution (traffic of vehicles) as soon as the traffic is sufficiently dense. The theoretical intensity of the number of transmitters offers a very good upper bound on capacity, i.e. on the maximum number of frames that can be transmitted per second and per unit length. Also, we have shown that our model can be used to tune the CSMA/CA parameters in order to optimize the capacity. Through a simple FER model, we estimated the parameters of the CSMA mechanism that offers the best trade-off between spatial reuse and interference. Even if this model offers good estimate of this optimal, the FER model needs to be improved, according to the 802.11 physical layer, to obtain better estimates of the CCA optimal and the associated capacity. Moreover, the considered path-loss function does not take into account multi-path or fading properties of the wireless links. We are currently working on an extension of this model to take into account more elaborate wireless models.

Fig. 1

 1 Fig. 1 Example of concurrent transmissions: the 802.11p MAC layer (CSMA/CA) set the rules to access the medium. Only orange vehicles are allowed to transmit frames at the same time.

Fig. 3 Fig. 4

 34 Fig.3Mean number of simultaneous transmitters and capacity for constant inter-distances.

  Mean distance with collision Mean distance in saturation case Mean distance without collision (a) Constant inter-distance.

  Mean distance with collision Mean distance in saturation case Mean distance without collision (b) Traffic simulator.

Fig. 5

 5 Fig. 5 Distribution of the distances between concurrent transmitters.

  These results are similar to what we observe in terms of capacity in Figures 3(b) and 4(b).

3 :Fig. 7

 37 Fig. 7 Capacity as function of the CCA threshold.

F

  ER = P l(d) l(ξ 1 + d) + l(|ξ 2 -d|) ≤ β (23) = P l(ξ 1 + d) + l(|ξ 2 -d|) ≥ l(d) β

  π(s)f ξ2|ξ1=s (t)1 l l(s+d)+l(|t-d|)≥ l(d)

Table 1

 1 Simulation parameters.

	Theoretical and NS-3 Parameters Numerical Values
	IEEE 802.11std	802.11p -CCH channel
	Path-loss function	l(d) = Pt • min 1, 10 -4.5677 d 3
	CCA mode	CCA mode 1
	ED Threshold (θ)	-82 dBm
	Emission power Pt	43 dBm
	Number of samples per point	100
	Length of the packet	1024 bytes
	Duration of the simulation	4 sec
	S(u)	2.29 × 10 -10 -u -3	-1 3
	dmax	4120 m
	λ	0.379 × 10 -3
	Road length (d)	50 km
	DIFS	34 µs
	SIFS	16 µs