First and foremost, I would like to express my deep

Abstract

In recent years, Inter Vehicle Communication (IVC) has become an intensive research area, as part of Intelligent Transportation Systems. It supposes that all, or a subset of the vehicles is equipped with radio devices, enabling communication between them. IEEE 802.11p (standardized for vehicular communication) shows a great deal of promise. By using ad hoc mode, this radio technology allows vehicles to extend their scopes of communication and thus forming a Multi-hop wireless Ad-hoc NETwork, also called Vehicular Ad-hoc NETwork (VANET). This thesis addresses a fundamental problem of VANET: the network capacity. Two simple theoretical models to estimate this capacity have been proposed: a packing model and a Markovian point process model. They offer simple and closed formulae on the maximum number of simultaneous transmitters, and on the distribution of the distance between them. An accurate upper bound on the maximum capacity has been derived. An analytical formula on distribution of the transmitters has been presented. This distribution allows us to optimize Clear Channel Assessment (CCA) parameters that lead to an optimization of the network capacity. In order to validate the approach of this thesis, results from the analytical models are compared to simulations performed with the network simulator NS-3. Simulation parameters were estimated from real experimentation. Impact of different traffic distributions (traffic of vehicles) on the network capacity is also studied. This thesis also focuses on extended perception map applications that use information from local and distant sensors to offer driving assistance (autonomous driving, collision warning, etc). Extended perception requires a high bandwidth that might not be available in practice in classical IEEE 802.11p ad hoc networks. Therefore, this thesis proposes an adaptive power control algorithm optimized for this particular application. It shows through an analytical model and a large set of simulations that the network capacity is then significantly increased.

List of Figures

Introduction

With the creation of steam engine automobiles for the first time in 1769 [START_REF] Eckermann | World history of the automobile[END_REF], the automobile industry has become one of the most important industry and have significant influence to our daily life. Following an annual statistical report of OICA 1 , 84, 100, 167 vehicles had been produced in 2012 all over the world. In United States, a recent study by the Motor & Equiment Manufactures Association found that automobile industry is the biggest manufacturing employer offering more than 734, 000 jobs, accounting for $355 billion, about 2.3 percent of the U.S. gross domestic product.

Although, vehicles production has played a great role in economy growth, however, we also have to face with the other disadvantages, such as environment pollution, traffic jams, accidents, etc. Studies by World Bank, WHO 2 , and the Chinese Academy for Environmental Planning on the effect of air pollution on health concluded that between 350, 000 and 500, 000 people die prematurely each year as a result of outdoor air pollution in China. In Jakarta, the capital of Indonesia where you might need 2 hours to drive through a 1-kilometer-length road, there exists a special word "macet" to define the horrible traffic jam situation. In Vietnam, 10, 000 people die every year because of traffic accidents according to an annual report of Ministry of Transportation of Vietnam.

Improving traffic safety has become a crucial task in automobile industry research and development. Indeed, one might claim safety is the motivation of automobile invention systems, from vehicle lighting systems, seat-belt to other recent novel vehicle technologies such as airbag, ABS (Anti-lock Braking Systems), Infrared night vision are all served for safety purpose. 1 The Organisation Internationale des Constructeurs d'Automobiles, commonly abbreviated OICA (English:

International Organization of Motor Vehicle Manufacturers 2 World Health Organization

INTRODUCTION

Recently, driver assistance technologies have become an active research trend that allows the vehicle to warn the driver about an anomaly. As a consequence, people realize that communication between vehicles might help to improve the road safety. Thus, Vehicular Ad-hoc NETwork (VANET) has become an interesting topic. A VANET is a network where vehicles equipped with wireless interfaces communicate with each other to create a wide range network. Indeed, a

VANET can be used to extend the scope of the "safety information" (warning/alert messages, information on anomaly, etc). For a decade, there are plenty of research applications using VANET to disseminate early-warning data message that can assist drivers to make proper decisions. Urban Multi-Hop Broadcast (UMB) [2], Multi-Hop Vehicular Broadcast (MHVB) [START_REF] Osafune | Multi-hop vehicular broadcast (mhvb)[END_REF] just to name a few. These applications have different constraints. Certain may require a lot of bandwidth. However, before these applications become practical, one must answer a fundamental question: can VANET support them? This thesis is motivated by this question and the VANET capacity which is the amount of information that a VANET could carry. The contributions of this thesis are summarized as follows:

• Firstly, this thesis offers an accurate and reliable upper bound on the reachable capacity.

This estimation technique could be used as real dimensioning tools for VANET applications. The proposed models (Packing and Markovian point process models) do not give a theoretical bound on the asymptotic capacity, but instead, offer a very realistic estimation of this capacity which can be reached in practice and in real conditions.

• Secondly, this thesis also presents a closed-form distribution of VANET transmitters derived from the Markovian point process model. This distribution allows us to have a better acquaintance on other wireless link properties, i.e., Frame Error Rate (FER), Interference distribution, etc. Moreover, the information about transmitter locations also gives us a tool to optimize the capacity throughout the CCA (Clear Channel Assessment) working mechanism.

• Finally, we shall see that the capacity is not enough for certain applications as the Perception map application -a VANET application (presented later in this thesis). Therefore, an adaptive power control algorithm dedicated to this application is introduced. It is worth noting that without power control, the Perception map application is likely unusable by lack of capacity. Besides, an analytical model based on the Packing model allowing us to evaluate the performance of this algorithm in term of capacity is also proposed.

The remainder of this thesis is structured as follows. Chapter 2 presents the fundamental definition of Wireless Ad-hoc NETwork, Vehicular Ad-hoc NETwork, the principal channel access mechanism and an overview of some typical point processes which have been used recently to model wireless network transmitters. The VANET capacity problems are explicitly stated in Chapter 3, following by a section on the related works. Chapter 4 presents the Packing model which give us an upper bound on the capacity. In Chapter 5, a Markovian point process modeling the location of the transmitters is proposed allow us not only to estimate the capacity but also to optimize it. Chapter 6 presents an adaptive transmission algorithm that aims to improve the capacity and meet the Perception map requirements. Finally, Chapter 7 concludes the thesis and provides some future research perspectives.

INTRODUCTION

Chapter 2

Background study

An overview of Wireless Ad-hoc Network

This chapter provides a top-down overview on the Vehicular Ad-hoc NETwork capacity topic.

It begins with the concept of the Wireless Ad-hoc Network, its definition, characteristics and listing wireless technologies that enable ad-hoc operation mode. Then, the Vehicular Ad-hoc NETwork, a branch of Wireless Ad-hoc Network, is briefly reviewed. IEEE 802.11p Standard defined for Vehicular Ad-hoc NETwork is also presented. Then, the IEEE 802.11p channel access mechanism which is the main factor that limits the Vehicular Ad-hoc NETwork capacity is meticulously described. Finally, the background is fulfilled with an overview on point processes, a mathematical tool intensively used to model nodes or transmitter locations of the wireless networks.

Wireless Ad-hoc Network

In Latin language, the term "ad hoc" means "for this purpose". Normally, it is used to illustrate the on-the-fly solutions which are quickly, specifically developed for a particular purpose.

According to Oxford advanced learner's dictionary, "ad hoc" has the meaning of arranged or happening when necessary and not planned in advance. Historically, the earliest concept of wireless ad-hoc network can be considered to be appeared in 1968. A computer network named ALOHA [4] was initiated under the leadership of professor Norman which consists of nodes using wireless interfaces to communicate formed without any central administration entity. Indeed, a wireless ad-hoc network is a decentralized type of wireless network. The network is ad-hoc because of its independence on any pre-existing infrastructure.

The ability to easily extend radio coverage is the most salient feature of the wireless ad-hoc network when comparing to other type of wireless network. Unlike managed wireless network

where a new participator needs to be in range of a base station, in wireless ad-hoc network one only needs to be in range of other network members. In addition, wireless ad-hoc network is suitable for emergency situations (natural disasters, military conflicts, just to name a few) because of its quick deployment and minimal configuration.

Wireless technologies for ad-hoc network

By definition, a wireless ad-hoc network consists of nodes communicating in ad-hoc mode by wireless interfaces. Up to now, there are many wireless technologies that allow forming a wireless ad-hoc network. Their characteristics are different (transfer rate, communication range, frequency, etc). Therefore, this section presents a brief introduction on popular wireless technologies that enable ad-hoc working mode.

Bluetooth is a wireless technology managed by Bluetooth Special Interest Group (SIG) which has over 19, 000 member companies [START_REF]Bluetooth special interest group[END_REF]. Bluetooth is dedicated to exchange data over short In monitoring applications and surveillance activities, a Wireless Sensor Network (WSN) [13,14] usually use to monitor physical or environment conditions. It is another type of wireless adhoc network. In such a network, there are hundreds or thousands small autonomous sensors that communicate with each other. These sensors are often used to collect quantitative information on their objects such as temperature, pressure, humidity, and to cooperatively transmit their data to the primary entities. In original wireless sensor networks, primary entities have no control on sensor activity. But now, in recent networks, sensor activity can be controlled as the communications are bi-directional. However, most of the sensors run on batteries due to their automation. As a result, energy efficiency turns out to be the key for designing this kind of network.

Another popular type of wireless ad-hoc network is Mobile Ad-hoc Network (MANET) [START_REF] Hartenstein | vANET: vehicular applications and inter-networking technologies[END_REF] where nodes are able to move freely and independently in any direction. Therefore, network topology of this network type will change frequently; establishing links and terminating connections are likely to happen from time to time. Continuously maintaining the information required for traffic routing is considered as the primary challenge in a Mobile Ad-hoc Network.

Hence, most of research efforts focus on link connectivity, routing. Throughput and capacity are good metrics to evaluate the performance of this type of network.

A variant of Mobile Ad-hoc Network is Vehicular Ad-hoc Network (VANET) [START_REF] Hartenstein | vANET: vehicular applications and inter-networking technologies[END_REF] in which the participators are transportation vehicles. The substantial difference between Mobile Ad-hoc Network and Vehicular Ad-hoc Network is the predictability of movement. Unlike the random movement in Mobile Ad-hoc Network, vehicles in Vehicular Ad-hoc Network must follow the routes and traffic rules. Thus, there exist traffic patterns for trajectory of vehicles. But, even so, the high speed of vehicles makes fast mobility characteristic to become the most challenging difficulty in VANET research. Besides, improving transportation safety is the main goal for researcher working in Vehicular Ad-hoc Network domain. A deeper presentation on Vehicular Ad-hoc Network standards and channel access mechanisms will be discussed in the next part of this chapter.

Vehicular Ad-hoc Network

Vehicular Ad-hoc Network is a promising application of Wireless Ad-hoc Network. This network is formed by moving vehicles that are equipped with IEEE 802.11p radio interfaces. With the target of improving road safety, this radio interface (also referred as the On Board Unit (OBU)) is used to broadcast or disseminate safety-warning messages. [START_REF]Ieee trial-use standard for wireless access in vehicular environments (wave)-resource manager[END_REF], [START_REF]Ieee trial-use standard for wireless access in vehicular environments (wave)-security services for applications and management messages[END_REF], [START_REF]Ieee trial-use standard for wireless access in vehicular environments (wave)networking services[END_REF], [START_REF]Ieee trial-use standard for wireless access in vehicular environments (wave)-multi-channel operation[END_REF] (summarized in Table 2.

Dedicated Short-Range Communication characteristics

The first effort to standardize communication for Vehicular Ad-hoc Network was started in 1991 [START_REF] Guo | Vehicular ad hoc networks and dedicated short-range communication[END_REF] 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. Therefore, CCA mechanism is the key to evaluate the spatial reuse in wireless network.

An overview of point processes

The point process theory is a narrow branch of statistics and probability theory. It is a type of random process for which one realization consists of a set of isolated points either in time or geographical space. A point process can model both one-dimension or multi-dimension events.

A one-dimension point process (Figure 2.7), typically modeling in time IR + , is a useful model for representing sequence of random times, each time corresponding to a particular event. For instance, the random times may model the arrivals of phone calls, since the beginning of each phone call happens at an instant (point of time). A point process can also be considered in a higher dimension space. A spatial point process (Figure 2.8), for an example, is useful to model random pattern of points in k-dimension space,

where k ≥ 2.

One may find applications of point processes in various research domains. They can be used directly, to model and analyze data which take the form of a point pattern, such as maps of the locations of trees or bird nests (statistical ecology [START_REF] Peter | Statistical analysis of spatial point patterns[END_REF], [START_REF] John | Statistical ecology: a primer in methods and computing[END_REF]); the positions of stars and galaxies (astrostatistics [25]); the locations of point-like defects in a silicon crystal wafer (materials science [START_REF] Ohser | Statistical analysis of microstructures in materials science[END_REF]); the locations of neurons in brain tissue; or the home addresses of individuals diagnosed with a rare disease (spatial epidemiology [START_REF] Elliot | Spatial epidemiology: methods and applications[END_REF]). Spatial point processes also serve as a basic model in random set theory [START_REF] Stoyan | Stochastic geometry and its applications[END_REF] and image analysis [START_REF] Robert M Haralick | Image analysis using mathematical morphology[END_REF].

Recently, point process is considered as a valuable tool in wireless network modeling. Since the geographical aspects have a great impact on wireless network performance, the location of the nodes plays an important role. For instance, the radio scope of the nodes could be increased in circumstances where transmitter density is low as the interference should be small because there are only a few emitters. However, a longer distance between the nodes in such cases should limit the connectivity. Moreover, even for a low density transmitter case, if a set of emitting nodes are gathered in a same region, interference may be still high. As all these phenomena strongly depend on the spatial distribution of nodes, they turn out to be difficult to understand. Therefore, static topologies (such as grids), and simulations performed with a finite set of topologies are inaccurate. They consider only specific patterns; as a consequence they cannot guarantee that the results obtained hold for other patterns. Stochastic point processes are thus particularly suited to the performance evaluation of ad hoc networks. In this case, a point process models the geographical location of the wireless nodes. They allow us to obtain averages and distributions for different quantities related to the performance of the networks.

These statistical quantities are based on an infinite number of topologies (the samples). The ability to describe statistical geographical properties with a few parameters (only one parameter for the Poisson point process for an example) leads to simpler interpretations of the obtaining results and is one of the stochastic point process advantages. In the next part, some typical point processes which have been recently used to model locations of nodes in wireless networks are presented.

Poisson point processes

The most commonly used point process is Poisson point process. In the literature, it has been used broadly to study the capacity or the connectivity of ad-hoc networks [START_REF] Gupta | The capacity of wireless networks. Information Theory[END_REF], [START_REF] Dousse | The costly path from percolation to full connectivity[END_REF], [START_REF] Dousse | On the throughput scaling of wireless relay networks[END_REF] , as well as in the modeling of interference and radio properties [START_REF] Baccelli | An aloha protocol for multihop mobile wireless networks[END_REF], [START_REF] Baccelli | Spatial averages of coverage characteristics in large cdma networks[END_REF], [START_REF] Elyes | Neighbor discovery in multi-hop wireless networks: evaluation and dimensioning with interferences considerations[END_REF], [START_REF] Ilow | Analytic alpha-stable noise modeling in a poisson field of interferers or scatterers[END_REF], [START_REF] Stoyan | Stochastic geometry and its applications[END_REF].

Definition 1 A homogeneous Poisson point process with constant intensity λ is characterized by two properties:

• The number of points of Φ in a bounded Borel set B has a Poisson distribution of mean λ|B|, where |B| is the Lebesgue measure of B in IR 2 .

• The numbers of points of Φ in k disjoint Borel sets form k independent random variables.

A sample of a homogeneous

Matèrn point processes

The Poisson point process can precisely model the location of nodes in an ad hoc network.

Consequently, it can be used to evaluate the connectivity, capacity and performances of routing protocols. However, it should not be used systematically to study other quantities related to radio properties such as interference, Signal to Intergerence-plus-Noise Ratio (SINR), Bit Error Rate (BER), Frame Error Rate (FER), etc. Indeed, all these quantities depend on interference which at a given time does not depend on all the nodes but only on the emitter locations.

The Poisson point process is not always suitable for modeling these emitters, as it supposes, in some way, that they are independently distributed. However, in practice, most of the radio technologies (802.11, 802.15.4, etc.) use CSMA/CA medium access protocol which requires a potential emitter to listen to the channel before emitting. If the interference level is lower than a given threshold, the emitter transmits its frame. Otherwise the channel is presumed busy and the transmission is delayed. Hence, the distribution of emitters formed by this mechanism is more correlated than Poisson point processes.

The Matèrn point process is an example of a point process that captures this phenomenon.

Originally, it was presented in [START_REF] Matérn | Spatial variation, meddelanden fran statens skogsforskningsinstitut[END_REF]. A more accessible presentation of this point process can also be found in [START_REF] Stoyan | Stochastic geometry and its applications[END_REF]. It belongs to the family of hard core point processes, where the points are forbidden to lie closer together than a certain minimum distance r. In CSMA/CA wireless network context, the inhibition distance r can be interpreted as the distance at which a potential emitter detects the emission from a neighbor.

Definition 2 Let Φ be a homogeneous Poisson point process of intensity λ. We associate to each point z of Φ, a mark m z uniformly distributed in [0,[START_REF] Eckermann | World history of the automobile[END_REF]. The points of the Matèrn point process are the points z of Φ such that the ball B(z, r) centered at z and with radius r does not contain other points of Φ with marks smaller than m z . Formally,

Φ M = {z ∈ Φs.t.m(z) < m(y)∀y ∈ Φ ∩ B(z, r)\z} (2.2)
One may consider Matèrn point process as a thinning process of an original Poisson point process. Indeed, Matèrn point process selects a subset of nodes from a Poisson point process.

According to the definition, this selection process consists in letting each proposed point z occupy a ball B(z, r) of radius r centered at z. Two points, which have overlapping balls, or equivalently, their Euclidean distance smaller than 2r, contend with each other. Once the contention between points is determined, a retention mechanism is used to prohibit the simultaneous presence of any two contending points. An independent uniform random mark m z in [0, 1] is assigned to each proposed point z, and a point is remained if its mark is the smallest among its contenders.

Thanks to its particular selection process, the Matèrn point process seems well-suited to model a network operating in CCA mode 2. Indeed, a transmitter postpones its emission upon detection of a compliant signal, i.e. the presence of a transmitter within its detection distance.

However, spatial considerations reveal some fundamental limitations.

The primary drawback of Matèrn point process is the underestimation of the simultaneous transmitters. The example in Figure 2.10 clearly shows us this problem. In this figure, Nodes 1 and 4 are legitimately selected as transmitters. Node 2 is not selected because it lies within the exclusion ball of Node 1. Node 3 is not selected as its mark is less than the one of Node 2 despite the fact that Node 2 is not selected. In the CSMA/CA perspective, this is inexact as only effective transmitters inhibit potential ones. Practically, Nodes 1, 3 and 4 should be kept after the selection process.

Simple Sequential Inhibition point processes

In order to alleviate the underestimation of Matèrn point process, a more appropriate type distribution of solids in k-dimensional spaces [START_REF] Hall | Introduction To the Theory of Coverage Processes[END_REF], [START_REF] Solomon | A review of the packing problem[END_REF]. The Simple Sequential Inhibition point process is also known as the Poisson disk distribution and is used in computer graphics to efficiently sample images [START_REF] Yellot | Spectral consequences of photoreceptor sampling in the rhesus retina[END_REF], [START_REF] Cook | Stochastic sampling in computer graphics[END_REF].

Definition 3 Consider a finite area B in a IR 2 plane. Let X 1 , ..., X n be a sequence of random variables independently and uniformly distributed in B. X 1 is systematically added to Φ S (1). X i is added to Φ S (i) if and only if X i ∈ ∪ Xj ∈Φ S (i-1) B Xj where B Xj is the cover ball of X j . The process stops whenever the n points have been considered or when B is entirely covered by the union of the inhibition balls. Φ S (n) is now, a SSI point process.

We shall say that a sample of the SSI has reached saturation when the union of the inhibition balls associated to the selected points covers entirely B.

Summary

In this chapter, an overview of Wireless Ad-hoc Network, its salient features and primary characteristics have been introduced. Inheriting all the advantages, Vehicular Ad-hoc Network which is considered as the most promising application is also presented. Besides, a brief summary of wireless technologies enable ad hoc network is presented.

This chapter provides a top-down approach on how IEEE 802.11p works and the characteristics of radio channels. Moreover, details on channel access mechanism are also described.

Indeed the MAC and Physical Layer of IEEE 802.11p play important roles as this thesis focus on capacity problems. These physical working mechanisms are the primary causes that limits the capacity of Vehicular Ad-hoc NETwork.

The recent mathematics tool with the capability to model wireless network: point processes, is also reviewed. This chapter ends with a brief introduction on some typical point processes:

the Poisson point processes, the Matèrn point processes and Simple Sequential Inhibition point processes. Discussions on their advantages as well as the disadvantages have been also presented.

Based on this background knowledge, in the next chapter, the fundamental capacity problems and some other challenges in VANET will be explicitly stated.

Chapter 3

Problems and related works

In this chapter we describe the two problems that are addressed in this thesis: the capacity estimation and optimization, and power control in VANET (that increases the network capacity). Section 3.1 presents the capacity estimation problem and the state of the art. Section 3.2 deals with power control in VANET and summarizes the related works.

VANET capacity estimation and optimization

Motivations and problem statement

With the emergence of embedded sensors, a vehicle may collect information about its environment. The vehicle system can inform the driver about a local anomaly, a too short inter-distance with the leading vehicle, help to adhere to road codes such as pavement marking, etc. Data from these sensors may also be exchanged between vehicles in order to increase the perception of this environment. This extended vision may help the driver to take appropriate decisions [START_REF] Hartenstein | vANET: vehicular applications and inter-networking technologies[END_REF].

For instance, inter-vehicle communications can be used to alert drivers about a dangerous situation, presence of an icy patch, an accident, etc. As a result, a timely warning may help the driver to avoid an emergency stop or sometimes, a collision. Other applications, not directly linked to safety, as the dissemination of information about traffic conditions or even advertising (for restaurant, gas station, etc.) are also promising and should appear quickly in our vehicles.

But, all these applications have different bandwidth requirements. Dissemination of warning messages consumes a limited capacity as these applications generate a few sporadic messages.

On the other hand, autonomous driving systems require a periodical exchanged of information from the embedded sensors. Estimation of VANET spatial capacity is thus fundamental, as it

Vehicles competing for access to the medium Vehicles that have gained access to the medium may limit the deployment or the feasibility of such applications. Therefore, this capacity must be estimated a priori in order to design applications with the capacity constraint in mind. The spatial capacity is defined here, as the amount of data that the whole network is able to carry per second per unit length. It can be expressed in M bps/km. In the following, the network capacity discussed in this thesis is refereed as this spatial network capacity.

The spatial capacity of VANET (using IEEE 802.11p standard) is mainly limited by the spatial reuse. Indeed, in classical 802.11 based ad hoc networks, each node is equipped with only one network interface card, and all the nodes use the same channel. Therefore, this channel must be shared by all the nodes. Fortunately, when two vehicles/nodes are sufficiently far from each other, they can transmit at the same time without interfering. The possibility to reuse the medium at different geographical locations is the so-called spatial reused. In practice, this quantity is directly linked to the spatial capacity offered by the network. It can be illustrated through a simple example. Clear Channel Assessments (CCA) is the key to evaluate the performance of a wireless ad-hoc network. This sensing mechanism is the primary factor that limits the number of simultaneous transmitters in a given area. As a result, it also limits the capacity of a wireless ad-hoc network. Hence, there is a direct relationship between CCA working mechanism and the wireless ad-hoc network capacity.

Let us consider the vehicles depicted in Figure 3.1. We suppose that we are in a saturated case where all the vehicles wish to send a frame. The MAC layer of the 802.11p standard will select a subset of vehicles which will be allowed to transmit their frames (they are colored in red in the figure). It selects vehicles in such a way that distances between concurrent transmitters is sufficiently large to avoid harmful interference between the transmissions. The number of simultaneous transmitters (the number of red vehicles) sets the number of frames that can be transmitted at the same time, and thus indirectly the number of frames that the network can sent per second: the network capacity.

VANET spatial capacity optimizing -optimal Clear Channel Assessment (CCA) thresholds

The Clear Channel Assessment (CCA) is linked to the capacity so it can be tuned to achieve the maximal capacity. Indeed, CCA declares the state of the medium based on the signal strength.

In the case this signal strength is greater than a predefined threshold, the medium is considered busy. Obviously, the value of this predefined threshold can affect the number of transmitters and consequently the network capacity. where Rx is the reception power, T x is the transmission power, C = -46.6777dBm is the loss reference, d is the distance and α = 3.0 is the path-loss exponent.

By default, the predefined threshold is set to -99dBm (IEEE 802.11p). Now, what happens if we increase this value? Assume that our radio environment is modeled by a simple Log Normal

Propagation model [START_REF] John | Introduction to RF propagation[END_REF]. Figure 3.2 shows us the different detection distances at which a node realizes that the medium is idle (378m, 599m, 1624m respectively). Naturally, a greater CCA threshold leads to a smaller detection distance. Since the detection distance becomes smaller, there are more simultaneous transmitters. Consequently, the number of frames being sent per second is increased and thus, the network capacity.

However, this CCA threshold cannot be increased arbitrarily. Otherwise, our network capacity may tend to infinity. In practice, there is also a constraint on the Frames Error Rate (FER). The network capacity is the number of properly transmitted frames per second. It can be defined as:

Capacity = T ransmittedF rames × (1 -F ER) (3.1)
If we increase the CCA threshold, we also increase the FER which results in limiting the network capacity. One may define the FER as an outage probability:

F ER = P(SIN R ≤ β) (3.2)
where SINR is the Signal to Interference plus Noise Ratio, and it is given by:

SIN R = ReceivedP ower Interf erence + N oise (3.3)
Due to the smaller detection distances between transmitters, the interference, generated by these transmitters, is also greater. As a result, a higher probability of frames error rate will be introduced.

On the other hand, when we decrease the CCA predefined threshold, the interference may tend to zero. But, at the same time, the detection distance becomes very large. It results in only a few simultaneous transmitters, and a low network capacity. Therefore, optimizing the capacity consists in finding the optimal trade-off between the number of transmitted frames and the frame error rate.

This optimization depends on the transmitter distributions, FER model and CCA. Such models will be presented in Chapter 5.

Vehicular Ad-hoc NETwork capacity 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 Ω

VANET capacity estimation and optimization

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, the problem with all these works is that they 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. In other words the capacity is O 1 n (≤ C) where C mainly depends on the spatial reuse. This constant has been evaluated in [START_REF] Busson | Point processes for interference modeling in csma/ca ad-hoc networks[END_REF]. These studies give pertinent bound on the capacity but they 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], the broadcast capacity of a VANET is estimated. The idea is similar to this thesis problem; an estimation of the number of simultaneous transmitters is proposed. But this evaluation is based on numerical evaluation only, using integer programming.

Point process approach in VANET modeling

Recently, point processes theory has become a popular intensity research to model the topology of MANET, VANET. A deep presentation of this can be found in [START_REF] Daley | An Introduction to the theory of point processes[END_REF], [START_REF] Stoyan | Stochastic geometry and its applications[END_REF]. An overview of results on ad hoc network performances using spatial models has been briefly presented in [START_REF] Busson | An overview of results on ad hoc network performances using spatial model[END_REF].

In [START_REF] Baccelli | An aloha protocol for multihop mobile wireless networks[END_REF], [START_REF] Yang | Co-channel interference modeling and analysis in a poisson field of interferers in wireless communications[END_REF], [55], [START_REF] Dousse | Connectivity in ad-hoc and hybrid networks[END_REF], [START_REF] Gupta | Capacity of wireless networks[END_REF], [START_REF] Ben Hamida | Neighbor discover in multi-hop wireless networks: evaluation and dimensioning with interference considerations[END_REF], Poisson point processes presented in the previous chapter (Section 2.3.1) has been extensively used to model spatial distributions of active transmitters in ad-hoc networks. One reason for this popularity is certainly the tractability of the interference distribution which is not affordable for many other point processes. For instance, the Laplace transform of the interference distribution can be assessed, and the frame error rate can be deduced for some special cases [START_REF] Baccelli | An aloha protocol for multihop mobile wireless networks[END_REF]. However, the Poisson point process is only suitable to model sparse networks where transmitters can be assumed uncorrelated. On the other hand, for dense network usings a CSMA/CA protocol, the MAC protocol introduces a correlation between the actived transmitters location. Consequently, Matèrn point process described in the previous chapter 2. [START_REF] Osafune | Multi-hop vehicular broadcast (mhvb)[END_REF].2 has been used as an alternative to the Poisson point process. This point process is based on a simple rejection rule that allowing to take MAC into account ( [START_REF] Nguyen | A stochastic geometry analysis of dense ieee 802.11 networks[END_REF], [START_REF] Haenggi | Mean interference in hard-core wireless networks[END_REF], [START_REF] Giacomelli | Outage probability of general ad hoc networks in the high-reliability regime[END_REF], [START_REF] Hunter | Transmission capacity of multi-antenna ad hoc networks with csma[END_REF], [START_REF] Hong | Demystifying white spaces[END_REF]). However, this point process suffers several weaknesses. First, the distribution of interference can be assessed but there is no closed form. Later, it was noticed in [START_REF] Busson | Point processes for interference modeling in csma/ca ad-hoc networks[END_REF] that this model underestimates the density of transmitters in the network, and consequently underestimates the aggregated interference. In this work, Simple Sequential Inhibition (SSI) model illustrated in the previous chapter (Section 2.3.3) has been proposed to alleviate underestimation problem but the closed form is still unknown. In [START_REF] Viet Nguyen | On the spatial modeling of wireless networks by random packing models[END_REF], the authors presented an outstanding mathematic result based on Random Sequential Adsorbtion (RSA) model which is proposed by Rényi [START_REF] Renyi | On a one-dimensional problem concerning random space-filling[END_REF] and Palásti [START_REF] Palasti | On some random space filling problem[END_REF]. However, this study focused on networks where nodes are distributed on the plane or in a 2-dimensional observation window.

VANET spatial capacity enhancement -Transmission

Power Control

Motivations and problem statement

Transmission Power Control is a well-known technique that allows nodes to transmit their data with different power level. It is broadly studied in both wireless and cellular networks. However, having safety as the main goal brings to VANET new constrains that were not considered before.

VANET spatial capacity enhancement -Transmission Power Control

Useful Distance

Maximal Transmission Power

Adaptive Transmission Power Spatial Reuse gainned The most promising applications of Vehicular Ad-hoc Network are safety and early warning applications. These applications used to collect information about safety conditions and spread their knowledge to the neighbors around. By doing so, other neighbors can benefit on their extended perception. Perception map [START_REF] Demmel | Simulation architecture for cooperative its applications and augmented perception[END_REF], an object of this thesis, is one example of such applications. It consists for a vehicle in collecting data through a set of embedded sensors measuring the surrounding environment. With the VANET, perception maps may be broadcasted to the adjacent vehicles allowing a node to extend its local vision. The so-called "extended perception" may improve the safety applications as it offers a better risk assessment, a better anticipation of dangerous situation, and may provide information for autonomous driving applications. Unfortunately, this information is often useful within a distance. The other neighbors who are outside of this range, gain nothing except a high interference signal. Moreover, as we will see in a next chapter, this application may require a high bandwidth that is not available with the classical IEEE 802.11p. In such a circumstance, a feasible solution is to reduce the transmission power. But, decreasing transmission power may also limit the number of reception neighbors who stay in the useful distance.

Nevertheless, the random distribution of vehicle locations in VANET, gives us an opportunity to enhance the network capacity without reducing the number of reception neighbors. Let us consider the example in Figure 3.3. The transmitting vehicle (in red) can adapt its transmission power level to fulfill all of the neighbors in the useful distance. Comparing to the maximal transmission power case, we can keep the same number of reception neighbors (in yellow) and benefit on a better spatial reuse. Therefore, in this thesis, we propose a power control algorithm for extended perception map application where the transmission power is tuned in order to reach all neighbors within the useful distance with the minimum possible power.

Summary

mobility to estimate traffic density, and then adapt its transmission power accordingly. However, the difference between the number of total vehicles and the number of vehicles equipped with radio interface and participating in a VANET may lead to an inaccuracy of calculated transmission power.

Recently, a certain number of power control algorithms designed for VANET have been proposed [START_REF] Chigan | A delay-bounded dynamic interactive power control algorithm for vanets[END_REF][START_REF] Yang | Channel adaptive one hop broadcasting for vanets[END_REF][START_REF] Torrent-Moreno | Vehicle-to-vehicle communication: Fair transmit power control for safety-critical information[END_REF][START_REF] Cheng | Vanet adaptive power control from realistic propagation and traffic modeling[END_REF][START_REF] Tian | Connectivity based transmit power control in vanet[END_REF]. But, they cannot be applied to extend perception for local vehicle due to its specific constraints.

Summary

This chapter explicitly stated the fundamental capacity problems of VANET and explained how CSMA/CA working mechanisms impact this capacity. A solution to increase or optimize the VANET capacity is to set the CCA threshold as the best trade-off between spatial reuse and Frame Error Rate. Also, this chapter described the second problem addressed in this thesis: power control. Certain applications, in particular extended perception map, require a high bandwidth that may not be available. A power control algorithm may solve this problem, as this application relies on local broadcasting where frames need to be received only at a small distance (significantly less than the IEEE 802.11p radio range). This problem presentation was followed by a brief state of the art of power control in VANET.

In the next chapter, the first contribution dealing with the capacity estimation is presented:

A packing model based on the classical packing problem of the famous Hungarian mathematician Alfréd Rényi gives us an answer on the feasible capacity.

Chapter 4

Packing model approach During his life, Rényi contributed many important results to probabilistic, random graph and information theory. Especially in probability theory, he is well-known for his packing constant (so-called parking constant). Although one may find this packing constant appeared in various scientific domains from biology to physic, the initial question was surprisingly simple and practical: for a given street with a given length, assuming that all the cars which can park at random positions along this street have the same length, what is the density of cars when there are no more free position?

The packing problem can be formally described as follow: considering a street with length L as an interval [0, L] and L > 1. For convenience and without loss of generality, we consider that car is 1 unit of length. Let N (L) be the mean number of cars which can fulfill the street without overlapping. L ) tends to a well-known constant value 0.747579. This means that for a given street with a given length, only 74.7579% of this street is used. Though the origin of this packing constant was dedicated for car parking, nevertheless, we explain in the next section how this result on the convergence may be used to estimate the number of mean simultaneous transmitters in wireless network.

Classical packing model

In CSMA/CA wireless networks where CCA mode 2 is used, Rényi's packing problem can be used to model the mean number of simultaneous transmitters. According to CCA mode 2, the 4.1 Classical packing problem wireless medium is assumed to be busy when a 802.11p frame is detected. This corresponds to cases where the node sensing the medium is at a distance where the signal from the transmitter is detected and compliant to the 802.11 standard. In this case, this approach is rather sensitive to the highest interfering signal rather than the overall interference level. A simple model consists of considering that the maximum distance at which a 802.11 frame is detected is constant.

Let R be this distance. The medium is then busy if there is a transmitting node located at a distance less than R. With this model, the problem about the mean number of simultaneous transmitters boils down to the following question: how many segment with the size 2R can we put in a certain interval [a, b] under the constraint that the centers of these segment cannot be covered by another segment?

The answer is simple. If we consider that the first point is located at a, we just have to set Therefore, the mean number of simultaneous transmitters of a CSMA/CA wireless network working in CCA mode 2 can then be estimated as:

0.747579 2R (b -a) (4.2)
when (b -a) is large enough.

An extension model of Rényi's packing problem

In practice, the CCA mode 1 is the primary operational mode for a node in CSMA/CA wireless networks. We propose in this chapter, a new model which is an extension of Rényi's packing problem that allows us to model the simultaneous transmitters using CCA mode 1. Unlike the CCA mode 2, a node working in CCA mode 1 senses the wireless medium, and if the signal intensity is greater or above a predefined threshold, then the medium is determined as busy. The signal intensity is estimated as the sum of signals from all current transmitters.

It is then equivalent to Interference. This interference is the main factor that makes classical packing model become unsuitable for modeling the simultaneous transmitters in a CSMA/CA wireless network. Indeed, every time a new transmitter is inserted, the interference of all nodes attempting to access the wireless medium will be increased. As a result, the detection distance is no more a constant R as we have seen in the CCA mode 2 with classical packing model.

In order to keep the model tractable, we assume that the interference is generated only by the two closest transmitters, one on the left and the other one on the right. In fact, neglecting other transmitters does not significantly impact the interference because of two reasons. First, in IEEE 802.11p the communication range can be up to 700m, hence, the detection distance could be up to 1750m (usually, as twice and a half communication range). It means that other transmitters that could generate interference, if they exist, must be at least 3500m away from considering node. This distance is huge and thus, the impact of this interference, if it exists, is low. Second, in practice, the transmitted radio signals are quickly attenuated, especially in VANET context where the communication is conducted while nodes are moving.

We also assume that the received signal is modeled by a path-loss function, denoted l(.).

This path-loss function is defined in IR + , positive, continuous, decreasing with l(0) > θ (θ is the CCA threshold) and lim d→+∞ l(d) = 0. We define the interference of a node at x as I(x)

and it can be calculated as:

I(x) = l(x -Le) + l(x + Ri) (4.3)
where Le, Ri are the two closest transmitting nodes around x, the closest one on the left (located at Le) and on the right (located at Ri).

We introduce now a function v(.) that is used in our model. Let suppose that there are two transmitters, one at 0 and one at L. Between these two transmitters there is a sub-interval where new transmitters can access to the medium. It is represented in Indeed, if the distance between two successive transmitters are lower than 2D, the function 4.5 make sure that the interference between them is always greater than θ (CCA threshold).

Extension packing model

In this section, we proposed a process modeling locations of the simultaneous transmitters (using CCA mode 1) on a highway with length L. The considered interval is thus [0, L]. The model aims to represent the maximum number of transmitters in [0, L] such that the CCA rule given by equation 4.3 is respected.

L

Step 0

Step 1

Step 2

v(L) v(L) 0 L v(s) L-v(L-s) s s-v(s) L-v(L) v(L) v(s) v(s) v(L-s) v(L-s) s+v(L-s) 0 L v(s) L-v(L-s) s v(L-s) v(L-s) s+v(L-s) t < D < D Step 3 0 L s v(u-s) t < D < D u v(t) v(t) < D v(u-s) s+v(u-s) u-v(u-s)
m(L) = 1 + 1 L -2v(L) L-v(L) v(L) (m(t) + m(L -t))dt (4.6)
By a variable substitution, we get:

m(L) = 1 + 2 L -2v(L) L-v(L) v(L) m(t)dt (4.7)
The equation 4.7 represents the mean number of simultaneous transmitters. Unfortunately, its computation, to our knowledge, is intractable. Nevertheless, we can propose some results about its intensity (mean number of transmitters per unit length).

Intensity convergence

The process above is used to simulate the locations of transmitters. In Figure 4.4(a), we plotted the mean number of transmitters as a function of road length with different values for power transmission level. As it is shown, the stronger the power level is, the smaller the mean number of simultaneous transmitters is. This observation is reasonable since lowering the transmission power results in a smaller detection distance. Consequently, there are more free space where interference is low allowing more nodes to access the medium.

We can observe in Figure 4.4(b) that the mean number of transmitters m(L) L converges to constants as L increases. But, these constants depend on the transmission power. We have been able to prove this convergence that is formally presented in the proposition below:

Proposition 1 Let m(L) be the mean number of points in the interval [0, L] for the process defined above, then:

lim L→+∞ m(L) L = λ (4.8)
where λ is positive constant.

if s ∈ [0, v(L)] (respectively ∈ [L -v(L), L]), m(s) (resp. m(L -s)) is nil and the remaining interval [s + v(L -s), L -v(L -s)] (resp. [v(s), s -v(s)]) is a subset of [v(L), L -v(L)].
m(L) being super-additive and according to the Fekete Lemma, m(L) L converges to a finite or an infinite limit when L → +∞. To prove that the limit is finite, we need to show that

∃A = constant ≥ 0 such that m(L) ≤ AL.
By definition, the minimal distance between two successive points is D 2 . The mean number of points in [0, L] is thus less than

L D 2 . m(L) L is thus
bound by a positive constant. Therefore, the limit is finite.

Theoretical capacity formula

We define the capacity of a VANET as the number of frames that the network can send per second and per kilometer, denote T as the mean time needed to transmit a frame. This time takes into account the AIFS, the time to transmit the frame, the SIFS and the mean back-off.

The formula of the capacity can be written as:

Capacity(L) = m(L) T (4.9)
where L is the length of the road and m(L) is the mean number of simultaneous transmitters over the road with length L.

Thanks to Proposition 1 and for L sufficiently large, we can write:

Capacity(L) = λL T (4.10)
According to Equation 4.10, estimation of the capacity boils down to the computation of the limit λ. We propose an estimation of λ which does not require any simulation and can be deduced directly from the path-loss function.

l(u) = P t • min(B, B u α ) (4.11)
where P t is the transmission power, B is the loss reference parameters (equals to -46.6dBm)

and α is the path-loss exponent. In this figure, we took into account two transmitting powers P t = 17.02dBm and P t = 43dBm corresponding to transmission powers used in 802.11a and 802.11p technologies, and different path-loss exponent α modeling different radio environment.

We observe that all curves converge to the same constant, approximately equal to 1.49. This result is not surprising as it holds for other packing problems in one or two-dimensional spaces (see [START_REF] Hall | Introduction To the Theory of Coverage Processes[END_REF] or [START_REF] Busson | Point processes for interference modeling in csma/ca ad-hoc networks[END_REF] for instance). We also performed the same simulations for other path-loss function (with exponential decay for example), and observe a convergence to the same constant.

These results are not shown here because of redundancy. This convergence to a universal constant allows us to estimate the limit λ of Proposition 1 as follow: The final capacity is then evaluated as:

lim L→+∞ m(L) L = λ ≈ δ D (4.12)
Capacity(L) = δL D × T (4.13)

Experimentation

Our theoretical model aims to provide precise tools to estimate VANET capacity. In order to validate this model we tried to perform experimentation. Unfortunately, estimation of the real spatial capacity was impossible as it requires a lot of vehicles scattered on roads of several kilometers. Consequently, we use a realistic simulator (presented in the next section) instead, fed with a radio model whose parameters are obtained from experimentation. Therefore, this experimentation aims to obtain a realistic radio model for VANET.

We made experimentation on a track where vehicles were in the line-of-sight of each other.

Therefore, we considered a radio model that mainly depends on a path-loss function. Experimentation was thus used to estimate a realistic path-loss function, including distribution and parameters of a random variable modeling fading.

Scenarios

Experimentation took place on the Satory speed track dedicated for testing vehicles, isolated from regular traffic. The speed track includes a 1 kilometer way of direct line of sight (see Figure 4.6). Two Renault Clio III vehicles (TIC : "Transport Intelligent Coopératif" and TAC : "Télécommunication pour l'Assistance à la Conduite") had been used for these experimentations [START_REF] Demmel | Collision warning dissemination in vehicles strings: an empirical measurement[END_REF], [START_REF] Demmel | An ieee 802.11 p empirical performance model for cooperative systems applications[END_REF]. Figure 8 presents the block diagram of the different modules installed in the two vehicles. There is a central computer named Processor that collects and processes all data from the sensors (gyro, accelerometer, odometer, etc.). IEEE 802.11p wireless interfaces which use Atheros 5413 Wi-Fi chipset were installed in an embedded PC (see the white box with the antenna on Figure 4.7(b)). This computer operates under the Linux Ubuntu operating system.

We installed the open-source ath5k Wi-Fi driver [START_REF]The mad wi-fi project[END_REF], which was patched in 2010 for the Grand Cooperative Driving Challenge [START_REF] Malone | Accelerating cooperative systems development through the grand cooperative driving challenge[END_REF] in order to enable 802.11p channels. Some modifications on the transmission power and frequencies have been made to adapt the compatibility of European Telecommunications Standards Institute [START_REF]European telecommunications standards institute[END_REF]. Indeed, these devices were manufactured for United States market under Federal Communications Commission [START_REF][END_REF] Standards. An antenna with the gain of 3 dBi was connected to the embedded PC. An Ethernet interface was used to connect this embedded PC to the central computer Processor (see Figure 4.8). The TAC vehicle was set up as a server and received packets from TIC. For each received packet, it measured the reception power.

The primary difficulty in this experimentation was to associate the packets with the distances. In other words, the TAC vehicle must know the exact distance from itself to the TIC vehicle at the receiving time of a packet. The location of a vehicle was computed thanks to a data fusion process (an Extended Kalman Filter using the embedded sensors including the RTK GPS [START_REF] Ndjeng Ndjeng | Experimental comparison of kalman filters for vehicle localization[END_REF]) allowing the central computer Processor to achieve a centimeter precision on the distance. The location of the client (TIC) was time stamped and inserted in the packets sent to the server (TAC). The clocks of the OBU and the embedded PC were synchronized via the Network Transfer Protocol, according to the time of the GPS receiving module (see Figure 4.8). Consequently, we could associate the positioning information and the reception powers.

Results

Transmission power Exponent Loss reference We varied the distance between vehicles from 2 to 300 meters with a step of 10 meters.

We collected at least 30 samples for each distance. We performed our experimentation with 3 where R x is the reception power, T x is the transmission power, LossRef is the loss reference, α is the path-loss exponent, d is the distance between transmitter and receiver, and X g is a random variable which models fading.

The elements that we need to estimate are LossRef , the path-loss exponent α and the distribution of X g . First, we assumed that X g = 0. It allowed us to estimate LossRef and α with a Minimum Mean Square Error (MMSE) method. Results are presented in Figure 4.9.

It shows the mean reception power from the experimentation (with a 95% confidence interval) and the estimated path-loss function. The extrapolated parameters are summarized in Table 4.1. Then, fading X g was interpreted as the difference between the estimated path-loss function and the measured reception power (for each sample). The empirical distribution of X g is shown in Figure 4.10 for a transmission power of 30 dBm. The best fit corresponds to a Normal distribution where parameters are given in Table 4.2.

Simulations

To validate the accuracy of our Packing model, we present a comparison between simulations performed by the Network Simulator NS-3 [START_REF]Network simulator 3 -ns3[END_REF] and the theoretical models. First, a detail on the traffic simulator used to generate precise traffic pattern modeling a VANET highway is highlighted. Then, we show the simulation scenarios and the parameters. It is followed by a discussion on these results.

Traffic simulator

In our simulations, we considered two kind of traffic of vehicles. First, we assumed that the distance between the vehicles is constant. Then, we used a traffic simulator to inject realistic vehicle locations into NS-3. An illustration of this process is depicted in traffic simulator was completely done as it belongs to another part of the project supporting this thesis. Therefore, we describe this simulator in a few words. This is a micro-simulator emulating behavior of drivers on a highway. On a highway, drivers are limited to accelerating, braking and changing lanes. 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 condition (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 is presented in detail in [START_REF] Kazi | Modeling Drivers' Acceleration and Lane Changing Behavior[END_REF]. The model has been tuned and validated with regard to real data collected on a highway. For these simulations, we simulated a road/highway 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 (traffic cases) corresponds to the mean distance between two successive vehicles.

Results and discussions

We performed a set of simulations with regard to two scenarios:

• Default parameter case: we simulated a 20 km highway. This scenario corresponds to NS-3 default models and parameters of the IEEE 802.11p technology. We neglected fading effect in this case. This radio model is equivalent to the one considered in our models.

The other parameters are given in Table 4.3.

• Experimentation parameter case: we simulated a 20 km highway. This scenario uses the radio model set from the experimentation (presented in Section 4.3). Fading is thus taken into account. It leads to a smaller radio range compare to the default parameter scenario (approximately 500 meters). Other parameters are given in Table 4.4.

All nodes are equipped with IEEE 802.11p interfaces. Each node is a CBR (Constant Bit Rate) source where the destination is the closest vehicle on the left/right of its radio range. This CBR rate is close to the 802.11p rate (6M bps) in order to saturate the network. In such a good communication condition, frame will be likely received. In fact, we try to show that our theoretical bound is reachable. These nodes are located along a line modeling a highway. The capacity is computed as the total number of frames properly received by the nodes. To avoid edge effects, we did not take into account data from the first and the last 2.5 km of the highway for both two scenarios. Each point in the different figures are computed as the mean of 100 simulations and are presented with a confidence interval at 95%.

Default parameters case results:

Simulation results are plotted in Figure 4.12 and 4.13. The different sub figures correspond to the two kind of traffic: constant inter-distance and trajectories generated by the traffic simulator. It is worth noting that for this scenario 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. Comments are thus the same for these two traffic scenarios.

When we processed the results from the NS-3 simulator, we distinguished transmitters provoking a collision and the ones respecting the CCA rules. When we do not take into account collisions, the theoretical model gives an accurate bound on both intensity and capacity.

For the capacity, the difference is only 1% for 10 veh/km (distance between vehicles=100 meters) in Figure 4.13. The theoretical bound which is 1.648 Mbps is thus approached even for very low density traffic as 10 veh/km corresponds to very sparse traffic. The denser the density of vehicles is, the more the collisions are happened. As it is shown in Figure 4.12 and 4.13, for small inner-distances (from 50 -10 m), the difference between sent frames capacity and properly received frames capacity becomes significant. Indeed, the vehicle density increases when the inner-distance decreases, leading to more vehicles accessing the medium and provoking collisions. It is normal as the smaller inner-distance is, the more nodes/vehicles we have which results in a higher probability of collisions. We also observe that there is one point (innerdistance equals 50 m) where the simulation result (1.72 Mbps/km ) exceeds the theoretical capacity (1.648 Mbps/km). However, the difference in this case is only 0.072 Mbps/km. It is due to the fact that the neighbor for which we count the reception is close to the sender.

Therefore, sometimes, it happens that a frame is properly received even if there is an interferer in the CCA range. For lower inner distance, i.e. greater density of vehicles, contention appears that decreases the measured capacity. Mbps/km when the mean distance between two consecutive vehicles is 10 m. However, the theoretical bound is approached at a denser density traffic (50 veh/km) due to the fact that the communication range in the experimentation is smaller than the one in the previous scenarios.

Moreover, the exponent α value of the path-loss model in this case (1.9596) is significantly lower than the default (3.0) leading to a low attenuation of the interference. Nevertheless, simulation results show that the fading phenomenon does not introduce any error on our theoretical bound.

It is still explained by the short communication range between transmitters and receivers as in our simulation scenarios a node communicates with its closest neighbor on the left/right.

Consequently, in such a circumstance fading does not significantly impact communication.

Summary

Capacity of VANET is mainly limited by the spatial reuse of the CSMA/CA mechanism. In this Chapter, after briefly reviewing the famous work on packing problem of the Hungarian mathematician Alfréd Rényi, we proposed a simple model which is an extension of this classical packing problem to model the CCA mode 1. The model is then used to offer an upper bound on the capacity.

In order to have realistic radio models, a set of experimentation was performed to assess the real radio environment. From this assessment, precise parameters for modeling radio propagation were deduced. Consequently, we evaluated the VANET capacity for radio models with the NS-3 default parameters and the experimentation condition case.

Realistic simulations that combine the network simulator NS-3, the realistic radio model and a vehicles traffic generator have proved that our model offers a tight bound on the capacity. It had been shown reachable. The only idea condition that we considered is the distance between the transmitters and the receivers, all the other parameters were as realistic as possible. From this model, a simple formula allowing estimate this capacity can then be used as dimensioning or parameterizing tools to design VANET application. Markovian model approach

Motivations

In the previous chapter, the packing model gave us a tight bound on the capacity of VANET.

However, this model can only provide us the information on the number of concurrent transmitters. Therefore, it does not help us to have a better acquaintance on the wireless link properties. Indeed, other factors like Frame Error Rate (FER) or the connectivity between nodes plays an important role to evaluate network performance of wireless communication in general and VANET in particular.

These quantities not only require the number of concurrent transmitters but also distribution of their location. In fact, spatial distribution of nodes has a great impact on wireless network performance. Obviously, in case of high density of concurrent transmitters, this wireless environment has a very high FER which results in a low probability to correctly receive the frames. Whereas, in the low density scenarios, the connectivity between nodes becomes a problem. Under these circumstances, increasing transmission power is needed to guarantee the connectivity. Hence, spatial distribution of concurrent transmitters is the key to study wireless link properties.

Besides, lacking of information on link properties also limits our chance to optimize or improve this network capacity. Indeed, with the packing model, the only way to increase network capacity is reducing the power or increasing the CCA threshold. Because in this model, we estimate the network capacity as the number of sent frames, assuming implicitly that respect of the CCA rules leads to proper reception. However, this model suffers a drawback that is: It cannot answer the following question. "Is there a limitation for doing so?" Can we decrease transmission power to the lowest or increasing CCA threshold forever? Such a question heavily depends on the spatial distribution which is not handled by the packing model.

Markovian point process model

In this section, we present a Markovian point process which aims to represent the location of concurrent transmitters in a CSMA/CA wireless network using CCA mode 1 working mechanism. Indeed, the signal detection depends only on the closest interference so it is possible to be modeled through a Markov chain. Unlike other typical point processes presented in Chapter 2, we show in this chapter that this Markovian point process is tractable. The assumptions on radio environment and interference are the same as in the packing model (discussed in previous chapter). Therefore, only a brief review of them is described in the following part.

Assumption

According to CCA mode 1, we assume that the medium is detected idle for a node at X ∈ IR + if:

I(X) < θ (5.1)
where I(X) is the interference measured at X and θ is the Energy Detection (ED) threshold (CCA threshold). Here, the interference is defined exactly as the same as the packing model.

It takes into account only the 2 closest transmitting nodes, one in the left and the other in the right and is described formally by:

I(X) = l(X -le) + l(X + ri) (5.2)
where le and ri are 2 closest nodes from the left and the right. l(.) is the path-loss function which verifies the following properties:

• l(.) is continuous.

• l(.) is a decreasing function.

• l(0) > θ.

• lim u→+∞ l(u) = 0.

• there exists u ∈ IR + such that l(u) > θ and l(v) is strictly decreasing and differential for all v ∈ [u, +∞).

These conditions hold for path-loss functions with the form:

l(u) = P T min(1, c u α ) (5.3)
where P T is the transmission power and P T > θ, c and α are two positive constants.

Building the process

The model consists in a general Markovian point process composed of an ordered sequence of points (X n ) n≥0 with X n ∈ IR + which verifies two packing constraints. The first constraint is the packing criterion that sets the repulsion rule between the points, i.e. the CCA constraint.

The second criterion ensures that the space is completely filled, and that it is impossible to add new points/transmitters. It allows us to consider saturation, i.e. the maximum number of transmitters.

• Criterion 1: the interference level at each point X n of the point process (given by Equation (5.2)) is less than the Energy Detection threshold θ. Here, the interference computation does not take into account the signal from X n . Indeed, X n has detected the medium idle before transmitting.

• Criterion 2: the interference level at any point of IR + \{X n } n≥0 (everywhere except at the transmitter locations) is larger than θ.

In the following, we define the interval where the random variables of the Markov chain take their values. It is set according to these two criteria.

State space of the Markov chain

The chain is denoted (X n ) n∈I N with X n-1 < X n . According to Criterion 1, interference at each point X n must be less than the CCA threshold θ:

I(X n ) < θ ∀n ≥ 0
But, the building of this point process does not mimic the Rényi model where a point is added according to the distance from the points on the left and on the right. Indeed, the points are added in an increasing way (X n before X n+1 with X n < X n+1 ). X n is thus set without the knowledge of the next transmitter location X n+1 , and the interference level at X n is computed once the point X n+1 is set. Therefore, when we add a new point X n+1 , we need to take into account the interference level at the previous one (X n ), i.e. X n+1 must not increase interference at X n above θ:

l(|X n -X n-1 |) + l(|X n+1 -X n |) < θ (5.4)
Therefore, there is a minimal distance between X n and X n+1 that is denoted S(|X n -X n-1 |).

The function S(.) defines the minimal distance to the next transmitter. It is formally defined as the solution of

l(u) + l(S(u)) = θ (5.5)
where u corresponds to the distance between the two previous points/transmitters. A point

X n is thus distributed in [X n-1 + S(X n-2 -X n-1 ), +∞].
The second criterion allows us to bound this interval. According to Criterion 2, we shall distribute the points in such a way that it is not possible to add more points which could detect the medium idle. Consequently, the distance between transmitters must be bound by a maximal distance in order to prevent the presence of intermediate transmitters. Let D be this distance, it is solution of

2 • l D 2 = θ (5.6)
D is the same quantity as the one defined in the packing model. Thus, each point

X n (n > 1) belongs to the interval [X n-1 + S(X n-1 -X n-2 ), X n-1 + D]. Distances between the successive transmitters are denoted ξ i = X i -X i-1 . ξ n (n > 1) is thus distributed in [S(ξ n-1 ), D].

Building the point process

The point process is built as follows. The first two transmitters are located at X 0 = 0 and at X 1 with X 1 ≤ D almost surely. Assumptions about the distribution of X 1 are given in Theorem 1.

The other points are built recursively. The location of a transmitter

X n (n > 1) is distributed in [X n-1 + S(X n-1 -X n-2 ), X n-1 + D].
For convenience, we consider the sequence ξ n =

X n -X n-1 rather than X n . The sequence (ξ n ) n≥0 is thus a homogeneous Markov chain which takes its values in the continuous state space [S(D), D]. It is possible to consider any distribution on this interval, each one leading to different density of transmitters. The model can thus be adapted with regard to the system. For example, if we choose ξ n as deterministic with ξ n = S(D) (respectively ξ n = D), we obtain the maximum (respectively minimum) density of points verifying the two packing criteria. In Figure 5.1, we present an example of this point process and the different notations. As we do not know a priori the distribution of the distance between the transmitters, we have considered different distributions: uniform distribution and linear distribution. By uniform distribution (depicted in Figure 5.2(a)), it means that a new ξ n will be uniformly distributed The pdf g ξn|ξn-1 (.) of

X 0 =0 X 1 S(X 1 -X 0 ) X 2 is distributed in this interval X 0 =0 X 1 S(X 1 -X 0 ) X 2 S(X 2 -X 1 ) 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 D D
in [S(ξ n-1 ), D]. The pdf f ξn|ξn-1 (.) of ξ n = X n -X n-1 given ξ n-1 = X n-1 -X n-2 is then: f ξn|ξn-1=s (u) = 1 D -S(s)
ξ n = X n -X n-1 given ξ n-1 = X n-1 -X n-2 is then: g ξn|ξn-1=s (u) = -2 (D -S(s)) 2 u + 2D (D -S(s)) 2 1 u∈[S(s),D]
(5.8)

The sequence (ξ n ) n≥0 is thus a Markov chain which takes its values in the continuous state space [S(D), D].

Stationarity

The main result of this Markov chain is the derivation of its stationary distribution. It is given by the theorem below:

Theorem 1 The process (ξ n ) n≥0 defined in the above Section is a Markov chain. The stationary distributions of ξ n is π 1 (s) when the transition function is the uniform distribution (f ()), and π 2 (s) for the linear distributions (g()). The closed formulas of π 1 (s) and π 2 (s) are given by:

π 1 (s) = a 1 • (D -S(s))1 s∈[S(D),D]
(5.9)

π 2 (s) = a 2 • (D -s)(D -S(s)) 2 1 s∈[S(D),D] (5.10)
where a 1 , a 2 are the normalizing factors. The chain (ξ n ) n>0 converges in total variation to the distribution π 1 (s) (or π 2 (s) in the case of g()) for all initial distribution of ξ 1 in [S(D), D]. If ξ 1 follows the stationary distribution π 1 (.) (respectively π 2 (.)) then ξ n follows the distribution π 1 (.) (respectively π 2 (.)) for all n with n > 0.

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

π 1 (s) = D S(D)
f ξn|ξn-1=y (s)π 1 (y)dy (5.11) and

π 2 (s) = D S(D)
g ξn|ξn-1=y (s)π 2 (y)dy (5.12)

where π 1 (), π 2 () are given by Equations (5.9), (5.10) and f ξn|ξn-1=y (s), g ξn|ξn-1=y (s) are given by Equations (5.7), (5.8).

We get, in case of π 1 ()

D S(D)
(D -y)dy (5.17) = a 2 (D -s) (D -S -1 (s)) 2 (5.18)
where S -1 (.) is the inverse function of S(.). This function exists due to the properties of the function l(.): S(u) is bijective, differentiable and strictly decreasing in [S(D), D]. To conclude, note that S -1 (x) = S(x). It can be easily shown through the definition of S(x) given in the Equation 5.5. We get,

a 1 D -S -1 (s) = a 1 (D -S(s)) = π 1 (s)
and

a 2 (D -s) (D -S -1 (s)) 2 = a 2 (D -s) (D -S(s)) 2 = π 2 (s) (5.19)

Capacity formula

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

λ 1 = 1 E[ξ 1 ] = D S(D) sπ 1 (s)ds -1
(5.25)

λ 2 = 1 E[ξ 1 ] = D S(D) sπ 2 (s)ds -1 (5.26)
The inverse of these intensities λ 1 (resp. λ 2 ) is the mean distance between two consecutive transmitters. Hence, the number of simultaneous transmitters over a road with length L will be

λ 1 × L or λ 2 × 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) = λ 1 × L T (5.27)
Capacity(L) = λ 2 × L T (5.28)
where λ 1 , λ 2 are the intensities given by Equation (5.25), L is the length of the road and T is the mean time to transmit a frame. This time takes into account the AIFS, the time to transmit the frame, the SIFS and the mean of the back-off time.

Simulation results and discussion

In order to validate our Markovian model, we performed again the simulations described in Chapter 4 with NS-3 [START_REF]Network simulator 3 -ns3[END_REF]. Two scenarios were considered:

• Default parameters case: simulated highway is 20 km. This scenario corresponds to NS-3 default models and parameters of the IEEE 802.11p technology. Fading effect is neglected.

Other parameters are given in Table 5.1.

• Experimentation parameters case: simulated highway is 20 km. This scenario uses the radio model set from the experimentation (presented in Section 4.3). Fading is taken into account. Other parameters are given in Table 5.2.

For each scenario, we also took into account two kind of traffic: the constant inner-distance and the traffic generator (details are explained in Chapter 4). To avoid edge effects, we did not take into account data from the first and the last 2.5 km of the highway for both two scenarios. Each point in the different figures are computed as the mean of 100 simulations and are presented with a confidence interval at 95%. A software program has been coded in C language for capturing the position of transmitting nodes during the simulation time. These locations are used to evaluate and extrapolated the distribution of concurrent transmitters (so-called later the distance distribution).

Capacity and intensity results

In As it is shown in these figures, the packing model gives us the most accurate theoretical bounds on capacity as well as the intensity (mean number of simultaneous transmitters) when considering both the two simulation scenarios. Indeed, the packing model mimics exactly the CCA; whereas the Markovian models use a transition function that is arbitrarily set. We choose the ones that offer the best trade-off between tractability and accuracy. The difference between the two Markovian models (π 1 (s) and π 2 (s)) is small (only 0.78%).

Although these figures show us a small gap between Markovian theoretical bounds and simulation results. The Markovian models still offer a good upper bound on both capacity and intensity because the worst case error is only 5.25% in experimentation parameter case (Figure 5.5, 5.6). Hence, these bounds are acceptable.

Distribution of transmitters results

In Figures 5.7 and 5.8, we plotted the distributions of distance for the two scenarios: default parameter case and experimentation parameter case, respectively. Then, we compared the empirical distribution of distance obtained by NS-3 and the two theoretical distribution π 1 (s) and π 2 (s) given in Theorem 1. The abscissa is [S(D), D]. We collected distances between transmitters from 100 simulations. For each simulation, we collected the distances between the transmitters and we plotted the corresponding empirical probability density function. We also filtered the samples from the simulation results through 3 different criteria: without collisions, with collisions and saturation. In case of with collisions, we keep all the results. Whereas, we neglected the distances which are lower than S(D) in the "without collisions" case. Obviously, such a case corresponds to a collision, where the nodes competing for the medium realize that it is free at the same time. For the saturation case, we did not take into account distances greater than D. Because in reality CCA rules are not always respected (collisions for an example) and the medium is not always busy everywhere (as in our model). Therefore, we tried to highlight three set of samples corresponding to the real case (no filtering), the case without collisions (distances that cause collisions are filtered) and the saturation case (no collisions and medium is busy everywhere).

As it shown, the shapes of all distributions closely fit with the Markovian model distribution π 2 (s), especially, in case of saturation. We observe only a small difference when the function is decreasing in default parameter case. Indeed, it is very difficult to reach the absolute saturation condition where the medium is busy at every location, all the time. Sometimes, a vehicle satisfied CCA condition but it was on back-off stage, and does not transmit data. Therefore, there are regions where the medium is idle. Moreover, we observed that in case of realistic traffic, when the density becomes extremely dense (100 veh/km), there exists a lot of local traffic jams.

That explained why our model did not work well for the experimentation parameter case in realistic traffic (Figure 5.8). However, in the case of constant distance where there is no traffic jam, the theoretical curve π 2 (s) has only small difference compare with saturation case. It empirically proves that the Markovian model π 2 (s) corresponds to a case where the CCA rule is respected by all nodes (no collisions), and where the medium is spatially busy. Even if these conditions are not feasible in practice, our Markovian model π 2 (s) still offers accurate approximation for the distance distribution.

Optimizing VANET capacity

The transmitter distribution derived from this Markovian point process model allows us to optimize the capacity. In this section, we present the optimizing capacity problem and how we exploit the knowledge on this transmitter distribution to optimize it. Since the simulation results show that linear distribution is the more appropriate model to evaluate the capacity, from now, we only consider this model. π(s) is now referred as π 2 (s) and λ is now referred as λ 2 which correspond to the linear distribution case

Optimizing capacity

In practice, the real capacity should be measured as the number of successfully received frames.

As Frame Error Rate (FER) is an important factor which directly impacts to the properly receiving process, our capacity model must take into account this quantity. A simple formula that gives the capacity according to the FER is:

Capacity(L) = λL T (1 -F ER) (5.29)
where L is the road length, λ is the transmitter intensity, T is the needed time to transmit a data frame that taken into account the AFIS, SIFS, mean back-off, and F ER is the Frame Error

Rate. Obviously, we can achieve higher capacity by increasing the value of λ. In other words, we can reduce the distance between two consecutive transmitting nodes to improve the capacity.

A feasible way to do so is raising the CCA threshold θ. Indeed, increasing the CCA threshold allows more nodes to transmit at the same time but generate more interference. Therefore, this threshold must be a trade-off between spatial reuse and interference. It is possible to raise this 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.

Hence, 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 quality/interference.

Thanks to the information of concurrent transmitter distribution derived from our Markovian model and a model on FER, we can finally optimize the capacity.

Frame Error Rate models

There are different models to compute the Frame Error Rate. We consider here a simple and general model where 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 ≤ β) (5.30)
In order to compute the SINR, we use the stationary distribution of the Markov chain developed in this chapter. 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 this assumption, main interference are generated by the two nodes located on the left and right hand sides of our transmitter. This scenario is shown in Figure 5.9. Hence, SIN R can be expressed as: where l() is the path-loss function, 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) (5.31)
For sack of simplicity, we can consider N = 0 (but any value or distribution can be taken into account). Hence,

F ER = P l(d) l(ξ 1 + d) + l(|ξ 2 -d|) ≤ β (5.32) = P l(ξ 1 + d) + l(|ξ 2 -d|) ≥ l(d) β (5.33)
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,

F

Results and discussion

To validate our theoretical optimizing model, we performed a set of simulations with NS-3 [START_REF]Network simulator 3 -ns3[END_REF].

We simulated a highway where inner-distances between vehicles are constant and equal 700 m. All vehicles (nodes) are equipped with IEEE 802.11p interfaces, transmit frames to their neighbor with a constant bit rate that close to IEEE 802.11p 6 Mbps to saturate the medium.

Other detail parameters are given in Table 5.3 As it clearly shown in this figure, there is an optimal value for θ around -101 dBm. The optimal value is happened in both theoretical model and simulation results. It proves that this optimal value of θ can be easily find with our method. We used a simple FER computation, but this optimization can be easily applied to more elaborated FER model.

Conclusions

This Chapter provides a Markovian model which has the advantage to provide the distribution of the distances between simultaneous transmitters. This quantity is crucial to study wireless link properties. We validated our model through simulations performed with NS-3. In term of mean capacity, this model is less accurate than the packing model. Nevertheless, it offers an acceptable bound (with less than 5.25% of errors). The distributions of transmitting nodes have been compared with empirical simulation results. It showed that the Markovian with a transition function that is linearly distributed is the most appropriate model. From the knowledge of this distribution of transmitting nodes, a FER (Frame Error Rate) model has been proposed. It allows, for instance, optimizing the CCA threshold. Results from simulation indicated that theoretical capacity which takes into account the FER can be optimized by our model.

Chapter 6

Adaptive TPC algorithm -Random packing model

In previous chapters, we have evaluated the network capacity and it is not great, only 1.9367 Mbps per kilometer. This capacity may be enough for warning and alert messages as they do not require a lot of bandwidth. But for applications like driving assistance, that require much information exchanges it may be not enough. A simple solution to increase the capacity is to control the transmission power. In this chapter, we focus on a particular application: the perception map. This application that requires a significant capacity is presented in details in this chapter. We show how topology control may increase the capacity in this case and propose a practical TPC (Transmission Power Control) algorithm. This work has been done in collaboration with LIVIC (Laboratoire sur les Interactions Véhicules-Infrastructure-Conducteurs) laboratory. This chapter starts with the overview of the perception map and its capacity requirement. Then, we present our TPC algorithm and the modified packing model to evaluate the network capacity when using this algorithm. Then, we perform a set of simulations with NS-3 and compare these results with the analytical model. Finally, this chapter ends with our conclusions.

An overview of Perception map, a VANET application

Perception map consists for a vehicle in collecting data through a set of embedded sensors measuring the surrounding environment. It gives both a local representation and modeling of the information resources used by the vehicle applications like ACC (Adaptive Cruise Control),

Stop and Go, road departure avoidance, collision mitigation, etc. With the VANET, perception maps may be broadcasted to the adjacent vehicles allowing a node to extend its local vision.

The so-called "extended perception" may improve the safety applications as it offers a better risk assessment, a better anticipation of dangerous situation, and may provide information for autonomous driving applications.

But, information from sensors needs to be exchanged at a high rate (up to 100 packets per second) to be pertinent. Therefore, extended perception may generate an important amount of data that must be efficiently carried by the network. The fundamental and natural question that arises is thus to know if the VANET can offer such a capacity. If not, we need to propose mechanisms offering enough bandwidth to support these essential applications. surrounding the ego-vehicle (the local vehicle). In fact, the system tries to react to a current situation in order to minimize the gravity of an event (collision, road departure, etc.). In first answer in order to improve the network capacity for a better extended perception.

Transmission Power Control algorithm 6.2.1 Motivation

Our power control algorithm is dedicated to the extended map application, i.e. transmission power changes apply only to these application packets. As described earlier, the perception map application have the following properties: each vehicle/node broadcasts information at a high frequency, information contained in these packets are pertinent in the vicinity of the nodes (50-100 meters), and the application does not require a fully reliable delivery of the broadcasted packets so it tolerates a few losses. Therefore, the proposed power control algorithm aims to ensure a good reception rate of broadcast packets for receivers lying less than a certain distance (denoted d ref in the following), and with the smallest possible transmission power.

We do not assume any particular radio environment, path-loss, etc. The algorithm is adaptive, i.e. transmission power is tuned only with regard to measures made locally on each node.

Basically, the algorithm has three tasks: update a list of nodes at distance less than d ref , spy the reception qualities for these nodes, and increase/decrease the transmission power according to these information.

Algorithm details

The algorithm and the application assume that all involved nodes are equipped with GPS receiver or any devices allowing a node to know its location. The second list contains only nodes at a distance less than d ref (pertinent distance from the application point of view). To manage this list, we use the packets of the perception map application that periodically broadcasts packets at a high frequency. The power control algorithm applies to these packets. The corresponding list of nodes is denoted LocalNeighborsList.

It contains the neighbor IDs, up-link and down-link quality, and a local time out as shown in Table 6.2. The initial local timeout is set according to the constant LOCAL TIMEOUT.

This timeout aims to update/remove an entry of the local neighbor list when there are several consecutive missed packets from this neighbor. The up-link and down-link qualities may be the received signal strength, SNR, SINR or any quantity reflecting the link quality. In our simulations, we considered the received signal strength since it is available, but for a real implementation the RSSI (Radio Signal Strength Indicator) could be considered instead. The down-link quality is updated at the reception of a probe/application packet. When sending a probe packet (an application packet using this algorithm is called a probe packet), the sender piggybacks its own location and its LocalNeighborList. These information allows the receiver to update the location/distance and the up-link quality for this neighbor. It is uniformly distributed in this interval. It corresponds to the step 1 in Figure 6.3. This new point, located at u in our example, generates two busy intervals of lengths v(u, 0, P u , P 0 ) and v(u, L, P u , P L ) respectively. Also, the lengths of the busy intervals at 0 and L increase since the interferer at u is closer. The intervals become v(0, u, P 0 , P u ) and v(L, u, P L , P u ). Then, a new point is added in the idle interval (at v in step 2), and so on. We repeat this process until there is no idle interval in [0, L].

The busy intervals v(., ., ., .) are defined as follows. v(loc 1 , loc 2 , power 1 , power 2 ) represents the length of the busy interval around location loc 1 when interferers are located at distance loc 1 and loc 2 with transmitting powers power 1 and power 2 . This interval is located on the right hand side of loc 1 when loc 2 > loc 1 and on the left hand side otherwise. It is formally defined as the solution of I(loc 1 + v(loc 1 , loc 2 , power 1 , power 2 )) = θ when loc 2 > loc 1 and

I(loc 1 -v(loc 1 , loc 2 , power 1 , power 2 )) = θ otherwise.
Proposition 2 Let m(L) be the mean number of points in the interval (0, L) (we do not count the two points at 0 and L) for the process defined above, then:

lim L→∞ m(L) L = β (6.2)
where β is a positive constant.

The proof of this proposition is the same as the one in Chapter 4 since using random transmission power does not change the fact that m(.) is super-additive.

Capacity estimation

The positive constant β can be used to estimate the mean number of simultaneous transmitters over a road with length L at a given time. We denote T the mean time to transmit a 802.11p frame. It takes into account the different times used in the 802.11p protocol (AIFS, SIFS, etc.). We do not consider acknowledgment as our application generates only broadcast traffic.

The average number of frames that a network with length L can transmit per second can be expressed as:

Capacity(L) = βL T (6.3)
According to equation (6.3), estimation of the capacity boils down to the computation of the limit β. We propose an estimation that allows us to compute this constant from the path-loss function and the distribution of the transmission power. Since the adaptive TPC algorithm leads to the use of different transmission powers, we represent it as a random variable P tx . We collected more than 120, 000 samples of transmission powers from simulations (described in a next section). The best fit among the classical distributions of the empirical distribution of P tx -P max , where P max is the maximum transmission power, was the exponential law (Figure 6.4(a)).

Therefore, we express the transmission power distribution as a shifted exponential random variable truncated on the interval [0, P max ]. Its p.d.f. is given by:

f Ptx (x) = λ 1 -exp -λPmax exp -λ(Pmax-x) (6.4)
λ has been inferred from the samples. In order to estimate β, we consider the mean detection distance denoted D detect . It corresponds to the distance at which a node detects a transmission when there is no other source of interference. D detect is the solution of P tx l(D detect ) = γ. We get:

D detect = l -1 γ P tx (6.5)
In Figure 6. Therefore, the final capacity can be expressed as:

Capacity(L) = 1.70L E[D detect ]T (6.7)

Simulation results -Discussions

To validate our theoretical model and study the performance of the adaptive power control algorithm, we implemented our algorithm in NS-3 [START_REF]Network simulator 3 -ns3[END_REF]. In all simulations, vehicles were equipped with IEEE 802.11p interfaces and located along a line modeling a 15km -length highway. delivery rate, the number of packets per second generated by the perception map application was 125 packets/sec for inter-vehicle distances from 50 to 25 meters. For lower inter-distances, the application rate was 58 packets/sec.

In order to evaluate the benefit of our TPC algorithm, we performed the same simulations with and without power control. The first quantity we considered is the broadcast ratio defined as the ratio of received frames over the number of sent frames. The number of received frames is the sum of the successful receptions for vehicles at distance less than d ref from the transmitter. This quantity is thus greater than one, and increases with the vehicles density. Figure 6.5 depicts the broadcast ratio for the two mobility models. It shows that the delivery rate is almost the same with and without the power control algorithm. It means that our mechanism decreases the transmission power while keeping the targeted neighbors in its radio range. We have only a few losses with the Gaussian mobility model when the traffic becomes dense. These losses are mainly due to new neighbors entering within the pertinent area (distance < d ref ), that are not taken into account by our algorithm instantaneously.

The second quantity that we estimated is the spatial capacity. It is computed as the mean number of sent/received bits per second and per kilometer. When we consider the sent bits, we just count what is transmitted by the nodes. For the reception, we take into account bits of a broadcasted frame only once (even if there are several receptions), and only if it has been properly received by at least one node. The capacity improvement is shown in Figure 6.6. We observe a huge improvement of capacity (almost 10 times in some points). The fluctuation that appears when the inter-distance is equal to 25 meters is due to the change of our application rate explained earlier. The two horizontal lines correspond to the theoretical evaluation. We considered an exponential distribution of the transmission powers, and the empirical distribution obtained from the simulation samples. The bound from the exponential distribution is close to the empirical one, and has the benefit to be easily and analytically computable. The two bounds are accurate. For some points, the number of sent bits is greater than the theoretical bounds, but it is due to collisions, i.e. when a transmission does not respect the CCA rules (mainly due to the draw of the same back-off by two nodes). But, when we are looking at the number of received bits, our bounds are not reached and clearly offer good estimates.

Heterogeneous transmission scenarios

In practice, both broadcast and unicast transmission schemes can be appeared in VANET.

Therefore, to evaluate our TPC algorithm in such a realistic situation, we considered a hetero- Capacity of VANET is limited by the spatial reuse of the CSMA/CA mechanism. We aimed to develop analytical models that allow us to estimate the maximum amount of information that a VANET could carry.

Firstly, we proposed a simple model which is an extension of the famous classical Rényi packing model that models the CSMA/CA CCA mode 1. The model was then used to offer a good upper bound on the capacity of VANET. We also performed a set of experimentation to assess the real radio environment. From this assessment, precise parameters for modeling radio propagation were deduced. Consequently, we can evaluate the VANET capacity for both radio models regard to IEEE 802.11p Standard case and the experimentation condition case. From this model, a simple formula allowing estimate this capacity can then be used as dimensioning or parameterizing tools to design VANET application.

Secondly, we proposed a Markovian point process model which has the advantage not only to estimate the VANET capacity, but also to provide the distribution of the distances between simultaneous transmitters. This quantity is important to study wireless link properties. The distributions of transmitting nodes have been compared with empirical simulation results. From the knowledge of the distribution of transmitting nodes, a FER (Frame Error Rate) model which allows us, for instance, to optimize the CCA threshold has been proposed. Finally, we focused on extended perception map applications that use information from local and distant sensors of the vehicle to offer driving assistance (autonomous driving, collision véhicules ont été proposés à ces fins.

X 0 =0 X 1 S(X 1 -X 0 ) X 2 is distributed in this interval X 0 =0 X 1 S(X 1 -X 0 ) X 2
S(X 2 -X 1 ) X 3 is distributed in this interval Le modèle consiste en un processus Markovien à valeurs continues (X n ) n≥0 avec X n ∈ IR + . Ce processus décrit la position des émetteurs et doivent donc respecter les règles du CCA:

X 0 =0 X 1 S(X 1 -X 0 ) X 2 S(X 2 -X 1 ) X 3
• Critère 1: les interférences au point X n (donnée par l'équation (A.1)) est inférieure au seuil θ.

• Criterion 2: les interférence à n'importe quel autre point de IR + \{X n } n≥0 est plus grand que θ.

Ces deux contraintes nous permettent de définir les intervalles dans lesquels sont distribués les variables aléatoires: Nous considérons deux distributions différentes des points dans ces intervalles. La fonction de densité f ξn|ξn-1 (.) de ξ n = X n -X n-1 sachant ξ n-1 = X n-1 -X n-2 sont données par:

X n ∈ [X n-1 + S(X n-1 -X n-

A.2.5 Simulations

Nous présentons dans ce paragraphe les résultats de simulations. Le paramétrage des modèles radios ont été éffectué à partir d'expérimentations non présentées dans ce résumé. Voici les deux scenarios: Mais ces données ne sont pertinentes qu'à de courtes distances, de l'ordre de 50-

2. 1

 1 An example of a Wireless Ad hoc Network. . . . . . . . . . . . . . . . . . . . . . 2.2 An example of a Vehicular Ad-hoc Network. . . . . . . . . . . . . . . . . . . . . . 2.3 IEEE 1609 WAVE Layer model compare to OSI Layer model. . . . . . . . . . . . 2.4 Channel allocated by DSRC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 IEEE Std 802.11p MAC Internal architecture and channel coordination. . . . . . 2.6 IEEE 802.11p nodes contending example. . . . . . . . . . . . . . . . . . . . . . . 2.7 A point process in time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 A point process in two dimensions. . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Two examples of Poisson point processes: points are distributed in a square region [0, 1000] × [0, 1000]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 The Matèrn point process selection. . . . . . . . . . . . . . . . . . . . . . . . . . 2.11 Samples of the Matèrn and SSI point process in IR 2 plane after saturation. . . . 3.1 Example of concurrent transmissions: the 802.11p MAC layer (CSMA/CA) set the rules to access the medium. Only red vehicles are allowed to transmit frames at the same time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Reception power as function of distance and with different transmission powers. The propagation radio environment is modeled by a Log Normal Propagation model Rx(d) = T x•C d α where Rx is the reception power, T x is the transmission power, C = -46.6777dBm is the loss reference, d is the distance and α = 3.0 is the path-loss exponent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 The spatial reused gained by a lower transmission power . . . . . . . . . . . . . . 4.1 The road is divided into 2 segments when a new car randomly parked at position s. 4.2 A description of low interference zone where a new node can be inserted. . . . . . vii LIST OF FIGURES 4.3 A sample of our model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 m(L) and m(L) L with various transmission powers. . . . . . . . . . . . . . . . . . . 4.5 Convergence of m(L)D L as L increases for l(u) = P t min(B, B u α ) and different value of α and P t . D is the solution of 2l( D 2 ) = θ with θ = -99dBm. . . . . . . . . . . 4.6 Satory's speed track on http://geoportail.gouv.fr. . . . . . . . . . . . . . . . . . . 4.7 Vehicles and equiments on the track. . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 Inside vehicle devices modules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Path-loss function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 X g fading histogram and fitting curve . . . . . . . . . . . . . . . . . . . . . . . . 4.11 Simulation flow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12 Scenario with NS-3 default parameters: simultaneous transmitters. . . . . . . . . 4.13 Scenario with NS-3 default parameters: capacity. . . . . . . . . . . . . . . . . . . 4.14 Scenario with experimentation parameters: simultaneous transmitters. . . . . . . 4.15 Scenario with experimentation parameters: capacity. . . . . . . . . . . . . . . . . 5.1 Notations used in the model. The figure shows how the points X 2 and X 3 are distributed. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Probability Density Function of distance between the transmitters in different distribution: uniform distribution and linear distribution. . . . . . . . . . . . . . 5.3 Scenario with NS-3 default parameters: simultaneous transmitters. . . . . . . . . 5.4 Scenario with NS-3 default parameters: capacity. . . . . . . . . . . . . . . . . . . 5.5 Scenario with experimentation parameters: simultaneous transmitters. . . . . . . 5.6 Scenario with experimentation parameters: capacity. . . . . . . . . . . . . . . . . 5.7 Scenario with NS-3 default parameters: simultaneous transmitters. . . . . . . . . 5.8 Scenario with experimentation parameters: capacity. . . . . . . . . . . . . . . . . 5.9 Our scenario: a transmission takes place between a receiver and a transmitter at a distance d of each other. We compute the FER for this link. Two interfering nodes apply the CSMA/CA rules, detect the medium idle and transmit, thus interfere. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.10 Theoretical model and simulation results on capacity with different CCA value thresholds. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Attributes of a perception local map. . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 A comparison between theoretical capacity and the required capacity. . . . . . . viii LIST OF FIGURES 6.3 Random packing model example. . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.4 The convergence and the fitting distribution. . . . . . . . . . . . . . . . . . . . . 95 6.5 Broadcast ratio for constant and mobile cases in pure broadcast scenarios. . . . . 98 6.6 Total capacity for constant and mobile cases in pure broadcast scenarios. . . . . 99 6.7 Total capacity for constant and mobile cases in heterogeneous transmission environment: broadcast and unicast scenarios. . . . . . . . . . . . . . . . . . . . . . 101 6.8 Particular broadcast and unicast capacity for constant and mobile cases in heterogeneous transmission environment. . . . . . . . . . . . . . . . . . . . . . . . . 102 6.9 Broadcast ratio for constant and mobile cases in heterogeneous transmission environment. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 A.1 Notations du modèle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 A.2 Scenario with NS-3 default parameters: simultaneous transmitters. . . . . . . . . 117 A.3 Scenario with NS-3 default parameters: capacity. . . . . . . . . . . . . . . . . . . 118 A.4 Scenario with experimentation parameters: simultaneous transmitters. . . . . . . 118 A.5 Scenario with experimentation parameters: capacity. . . . . . . . . . . . . . . . . 119 A.6 Scenario with NS-3 default parameters: simultaneous transmitters. . . . . . . . . 119 A.7 Scenario with experimentation parameters: capacity. . . . . . . . . . . . . . . . . 120 A.8 Broadcast ratio for constant and mobile case in pure broadcast scenarios. . . . . 125 A.9 Total capacity for constant and mobile case in pure broadcast scenarios. . . . . . 125 Glossary ABS Anti-lock Braking Systems AC Access Category AIFS Arbitration Inter-frame Space Chapter 1

Figure 2 . 1 :

 21 Figure 2.1: An example of a Wireless Ad hoc Network.

  (a) Vehicle-to-Vehicle communication. RSU RSU (b) Vehicle-to-Infrastructure communication.

Figure 2 . 2 :

 22 Figure 2.2: An example of a Vehicular Ad-hoc Network.

  2) is a mode of operation used by IEEE Std 802.11 TM devices in environments where the physical layer properties are rapidly changing and where very short-duration communications exchanges are required, laying in a high layer in order to provide the minimum set of specifications required to ensure interoperability between wireless devices attempting to communicate in potentially rapidly changing communications environments and in situations where transactions must be completed in time frames much shorter than the minimum possible with infrastructure or ad hoc 802.11 networks. A comparison showing the relevant layers between WAVE model and OSI reference model is given in Figure 2.3. IEEE 802.11p uses a modified version of IEEE 802.11a for its Medium Access Control (MAC) layer protocol. It uses CSMA/CA as the basic medium access scheme for link sharing. The 802.11p PHY layer based on Dedicated Short-Range Communication (DSRC) standard works in 5.850-5.925 GHz spectrum due to the fact that IEEE refers to Federal Communications Commission in United States and European Telecommunications Standards Institute in European Union for regulatory requirements.

  . The United States Congress passed the Intermodal Surface Transportation Efficiency Act of 1991 that resulted in the creation the first generation of Intelligent Transportation System (ITS) which has the main purpose of improving traffic safety. After, Federal Communications Commission (FCC) indicated Dedicated Short-Range Communication (DSRC) as the standard designed for automotive use. The first generation of the Dedicated Short-Range Communication Part Name Purposes P1609.

Figure 2 . 8 :

 28 Figure 2.8: A point process in two dimensions.

•

  Poisson point process is shown in Figure 2.9. The homogeneous Poisson point process is called homogeneous because of the constant intensity λ. If we consider a Poisson point process with a varying intensity function λ(s), this Poisson point process is named inhomogeneous Poisson point process. As the name indicates, the mean number of points in a given area depends on the location of this area. More precisely, the definition of the inhomogeneous Poisson point process is the same as Definition 1, except that the first assertion is changed to: The number of points in a Borel set B has a Poisson distribution of mean ∧(B), where ∧ is an intensity measure and ∧(B) = B λ(s)ds.A sample of inhomogeneous Poisson point process with λ(s) = 4000||s|| is drawn in Figure2.9.

  (a) Homogeneous Poisson point process. (b) Inhomogeneous Poisson point process with λ(s) = 4000||s||.

Figure 2 . 9 :

 29 Figure 2.9: Two examples of Poisson point processes: points are distributed in a square region [0, 1000] × [0, 1000].

  of point processes has been recently considered, the Simple Sequential Inhibition (SSI) point process. It was first introduced by Palásti[START_REF] Palasti | On some random space filling problem[END_REF]. This model belongs to a family of well-known models used in the context of packing problems or space filling. They are concerned with the

Figure 2 . 10 :

 210 Figure 2.10: The Matèrn point process selection.

Figure 2 .

 2 11 depicts samples of Matèrn and SSI point processes after saturation. We can clearly see that with n large enough, the SSI covers entirely B whereas the Matèrn does not. The SSI model compensates the main drawback of the Matèrn model as it considers only the inhibition balls associated to effective transmitters during the selection process. However, until now, very few theoretical results exist for SSI point processes. The moment measures for this class of point processes are not known in closed form and seems to be intractable.

  2. BACKGROUND STUDY(a) A sample of Matèrn point process.(b) A sample of SSI point process.

Figure 2 . 11 :

 211 Figure 2.11: Samples of the Matèrn and SSI point process in IR 2 plane after saturation.

Figure 3 . 1 :

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

Figure 3 . 2 :

 32 Figure 3.2: Reception power as function of distance and with different transmission powers. The propagation radio environment is modeled by a Log Normal Propagation model Rx(d) = T x•C d α

Figure 3 . 3 :

 33 Figure 3.3: The spatial reused gained by a lower transmission power

Figure 4 .

 4 Figure 4.1 illustrates this parking process. In this figure, we assume that the first car is randomly and uniformly distributed in [0, L] at position s. Rényi showed in [64] that the mean density of the cars (lim L→+∞ N (L)

Figure 4 . 1 :

 41 Figure 4.1: The road is divided into 2 segments when a new car randomly parked at position s.

a

  segment at a distance R from the previous one until reaching b. But in a VANET, potential transmitters are arbitrarily distributed on the line, and transmitters are aimlessly chosen (it depends on the applications, back-offs, etc.). Therefore, a more appropriate model consists in placing the segments randomly in [a, b]. The first segment is placed uniformly in [a, b]. Then, we place the second segment uniformly into all points x of [a, b] such that a segment at x does not cover the center of the previous segment, and so on. The process terminates when there are no gaps in [a, b] large enough to host another segment. Certainly, we can see the similarity between Rényi's packing problem and the CSMA/CA CCA mode 2 network modeling. Indeed, if we consider the detection distance 2R as the length of a car, they are exactly the same. Hence, the limit of the mean number of segments over an interval [a, b] also converges to the packing constant: lim (b-a)→∞ M (b -a) b -a = 0.747579 (4.1) where M (b -a) is the mean number of segments put in an interval [a, b].

  Figure 4.2.

Figure 4 . 2 :

 42 Figure 4.2: A description of low interference zone where a new node can be inserted.

Figure 4 . 3 :

 43 Figure 4.3: A sample of our model.

  Mean number of transmitters as function of road length for different transmission power levels. Transmission power = dBm Transmission power = dBm Transmission power = dBm (b) Mean number of transmitters over road length for different transmission power levels.

Figure 4 . 4 :

 44 Figure 4.4: m(L) and m(L) L with various transmission powers.

5

 5 Pt=43dBm α=4.0 Pt=17.02dBm α=2.2 Pt=17.02dBm α=2.5 Pt=17.02dBm α=3.0 Pt=17.02dBm α=3.5 Pt=17.02dBm α=4.0

Figure 4 . 5 :

 45 Figure 4.5: Convergence of m(L)D L as L increases for l(u) = Ptmin(B, B u α ) and different value of α and Pt. D is the solution of 2l( D 2 ) = θ with θ = -99dBm.

Figure 4 . 6 :

 46 Figure 4.6: Satory's speed track on http://geoportail.gouv.fr.

  (a) Renault Clio III TIC and TAC on the track. (b) Equipments inside the TIC.

Figure 4 . 7 :Figure 4 . 8 :

 4748 Figure 4.7: Vehicles and equiments on the track.

different transmission powers: 24 ,

 24 27 and 30 dBm. Since we considered a line-of-sight propagation model, we extrapolate the measured path-loss function with the classical Log Distance Path-loss model. The formula of this model is as follow: R x = T x + LossRef -10αlog(d) + X g (4.14)

Figure 4 . 9 :

 49 Figure 4.9: Path-loss function.

Figure 4 . 10 :

 410 Figure 4.10: Xg fading histogram and fitting curve

Figure 4

 4

Figure 4 . 11 :

 411 Figure 4.11: Simulation flow.

  vehicles (m) Number of transmitters per km NS-3: simultaneous transmitters with collision NS-3: simultaneous transmitters without collision Packing model: theoretical number of transmitters (a) Constant inter-distance. Mean distance between vehicles (m) Number of transmitters per km NS-3: simultaneous transmitters with collision NS-3: simultaneous transmitters without collision Packing model: theoretical number of transmitters (b) Traffic simulator.

Figure 4 .

 4 Figure 4.12: Scenario with NS-3 default parameters: simultaneous transmitters.

  distance between vehicles (m) Capacity (Mbps/km) Capacity -received bits Packing model: theoretical capacity (b) Traffic simulator.

Figure 4 .

 4 Figure 4.13: Scenario with NS-3 default parameters: capacity.

4. 5

 5 SummaryExperimentation parameters case results:

Figure 4 .

 4 Figure 4.14 and 4.15 describe simulation results performed with parameters estimated from experimentation. In this case, our Packing model offers a good theoretical bound on both capacity and the intensity of simultaneous transmitters.

Figure 4 .

 4 Figure 4.15 shows that the capacity results from simulations reach 1.9394 Mbps/km (constant case) and 1.9367 Mbps/km (traffic simulator case) while theoretical bound is 2.0252

  Mean distance between vehicles (m) Number of transmitters per km NS-3: simultaneous transmitters with collision NS-3: simultaneous transmitters without collision Packing model: theoretical number of transmitters (a) Constant inter-distance.

  Mean distance between vehicles (m) Number of transmitters per km NS-3: simultaneous transmitters with collision NS-3: simultaneous transmitters without collision Packing model: theoretical number of transmitters (b) Traffic simulator.

Figure 4 .

 4 Figure 4.14: Scenario with experimentation parameters: simultaneous transmitters.

  bits Packing model: theoretical capacity (a) Constant inter-distance.

  distance between vehicles (m) Capacity (Mbps/km) Capacity -received bits Packing model: theoretical capacity (b) Traffic simulator.

Figure 4 . 15 :

 415 Figure 4.15: Scenario with experimentation parameters: capacity.

  Point processes described in the Chapter 2 are recent tools for studying spatial distribution of transmitters in wireless network. However, as clearly indicated earlier, these typical point processes become unsuitable to model VANET. The idea is to propose a Markov chain, distributed in IR + , where point locations respect the CCA rule. Thanks to the Markovian mathematical framework, it is then possible to derive a closed formula for transmitter distribution. The Markovian model and capacity estimation are described in Section 5.2. Comparisons to simulation are presented in Section 5.3.

Figure 5 . 1 :

 51 Figure 5.1: Notations used in the model. The figure shows how the points X2 and X3 are distributed.

1

 1 u∈[S(s),D] is the indicator function, equals to 1 if u ∈ [S(s), D] and 0 otherwise. Also, we considered the linear distribution where ξ n will be linearly distributed in [S(ξ n-1 , D]. The linear distribution is an affine function, positive in [S(ξ n-1 ), D], null at D, and such that its integral on [S(ξ n-1 ), D] is 1. It is illustrated in Figure 5.2(b).

2 D

 2 -S(ξ n-1 ) S(ξ n-1 ) D (b) Linear distribution.

Figure 5 . 2 :

 52 Figure 5.2: Probability Density Function of distance between the transmitters in different distribution: uniform distribution and linear distribution.

f 1 D 1 DS - 1 2 × 1

 11121 ξn|ξn-1=y (s)π 1 (y)dy (5-S(y) 1 [S(y),D] (s)a 1 (D -S(y))dy (5.14) = a (s) dy = a 1 D -S -1 (s) (5.15) and, in case of π 2 () s∈[S(y),D] a 2 (D -y)(D -S(y)) 2 dy (5.16) = 2a 2 (D -s) D S -1 (s)

Figure 5 .

 5 3 and 5.5, we plotted the simulation results on the mean number of simultaneous transmitters and compared them with theoretical bounds from the packing model, Markovian model π 1 (s), and Markovian model π 2 (s). The comparisons on capacity are depicted in Figure 5.4 and 5.6.

  Mean distance between vehicles (m) Number of transmitters per km NS-3: simultaneous transmitters with collision NS-3: simultaneous transmitters without collision Packing model: theoretical number of transmitters Markovian model: π 1 (s) Markovian model: π 2 (s) (a) Constant inter-distance.

  vehicles (m) Number of transmitters per km NS-3: simultaneous transmitters with collision NS-3: simultaneous transmitters without collision Packing model: theoretical number of transmitters Markovian model: π 1 (s) Markovian model: π 2 (s) (b) Traffic simulator.

Figure 5 . 3 :

 53 Figure 5.3: Scenario with NS-3 default parameters: simultaneous transmitters.

  Constant inter-distance.

  Traffic simulator.

Figure 5 . 4 :

 54 Figure 5.4: Scenario with NS-3 default parameters: capacity.

  Mean distance between vehicles (m) Number of transmitters per km NS-3: simultaneous transmitters with collision NS-3: simultaneous transmitters without collision Packing model: theoretical number of transmitters Markovian model: π 1 (s) Markovian model: π 2 (s) (a) Constant inter-distance.

  vehicles (m) Number of transmitters per km NS-3: simultaneous transmitters with collision NS-3: simultaneous transmitters without collision Packing model: theoretical number of transmitters Markovian model: π 1 (s) Markovian model: π 2 (s) (b) Traffic simulator.

Figure 5 . 5 :

 55 Figure 5.5: Scenario with experimentation parameters: simultaneous transmitters.

  Constant inter-distance.

  Traffic simulator.

Figure 5 . 6 :

 56 Figure 5.6: Scenario with experimentation parameters: capacity.

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

Figure 5 . 7 :

 57 Figure 5.7: Scenario with NS-3 default parameters: simultaneous transmitters.

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

  Traffic simulator.

Figure 5 . 8 :

 58 Figure 5.8: Scenario with experimentation parameters: capacity.

Figure 5 . 9 :

 59 Figure 5.9: Our scenario: a transmission takes place between a receiver and a transmitter at a distance d of each other. We compute the FER for this link. Two interfering nodes apply the CSMA/CA rules, detect the medium idle and transmit, thus interfere.

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

3 :Figure 5 . 10 :

 3510 Figure 5.10: Theoretical model and simulation results on capacity with different CCA value thresholds.

  figure is calculated as the mean of 20 samples and with a confidence interval at 95%. We assumed in our theoretical model that d = 700 m which is the expected radio range of the IEEE 802.11p technology, β = 10 (threshold on the SINR in the FER computation) and θ is varied from -140 dBm to -80 dBm (the default value of CCA mode 1 is -99 dBm).

Figure 6 . 1 :

 61 Figure 6.1: Attributes of a perception local map.

  Different frequencies transmissions for a fixed vehicle density (400 veh/km). Different vehicles densities at 10Hz of transmission frequency.

Figure 6 . 2 :

 62 Figure 6.2: A comparison between theoretical capacity and the required capacity.

  exponent α = 2.5 Path-loss exponent α = 3.0 Path-loss exponent α = 3.5 Path-loss exponent α = 4.0 (b) Convergence of m(L)E[D detect ] L for different path-loss function parameters.

Figure 6 . 4 :

 64 Figure 6.4: The convergence and the fitting distribution.

  4(b), we plotted the quantity m(L)2E[D detect ] L when L increases (E[D detect ] is the expectation of D detect ). Each point is the average of 100 samples and is shown with a confidence interval at 95%. The considered path-loss function is the classical Log Distance Path-loss [96]: l(d) = min(c, c/d α ). The values of the parameters are given in Table6.4. We observe that all curves converge once again to the same constant, approximately equal to 1.70. This convergence to an universal constant allows us to estimate the limit β of Proposition 2 as follows:

  (b) Mobile broadcast ratio

Figure 6 . 5 :

 65 Figure 6.5: Broadcast ratio for constant and mobile cases in pure broadcast scenarios.

  frames Power Control sent frames No Power Control received frames No Power Control sent frames Theoretical model (empirical distribution) Theoretical model (exponential distribution) distance between vehicles (m) Capacity (Mbps/km) Power Control received frames Power Control sent frames No Power Control received frames No Power Control sent frames Theoretical model (empirical distribution) Theoretical model (exponential distribution) (b) Mobile Total Capacity

Figure 6 . 6 :

 66 Figure 6.6: Total capacity for constant and mobile cases in pure broadcast scenarios.

  frames Power Control sent frames No Power Control received frames No Power Control sent frames Theoretical model (empirical distribution) Theoretical model (exponential distribution) distance between vehicles (m) Capacity (Mbps/km) Power Control received frames Power Control sent frames No Power Control received frames No Power Control sent frames Theoretical model (empirical distribution) Theoretical model (exponential distribution) (b) Mobile Total Capacity

Figure 6 . 7 :

 67 Figure 6.7: Total capacity for constant and mobile cases in heterogeneous transmission environment: broadcast and unicast scenarios.

  Mean distance between vehicles (m) Capacity (Mbps/km) Power Control scenario: broadcast Power Control scenario: unicast No Power Control scenario: broadcast No Power Control scenario: unicast (b) Mobile Total Capacity

Figure 6 . 8 :

 68 Figure 6.8: Particular broadcast and unicast capacity for constant and mobile cases in heterogeneous transmission environment.

  (b) Mobile broadcast ratio

Figure 6 . 9 :

 69 Figure 6.9: Broadcast ratio for constant and mobile cases in heterogeneous transmission environment.

λ

  d'atténuation l(.) qui donne la puissance en réception en fonction de la distance à l'émetteur. On suppose que l(.) est continue, positive, dérivable, décroissante et que l(0) > θ et lim u→+∞ l(u) = 0. Ces hypothèses sont vérifiées pour la plupart des fonctions d'atténuations de la littérature, en particulier pour les fonctions l(u) = P t min(1, c/u α ) avec P t la puissance d'émission (P t > θ), et òu c et α sont deux constantes positives.Nous supposons que les interférences I(x) à x (x ∈ IR + ) sont générées par les deux émetteurs les plus proches:I(x) = l(x -Le) + l(Ri -x) (A.1)où Le, Ri sont les deux noeuds transmettant les plus proches de x, plus proche sur la gauche (Le) et sur la droite (Ri).Le medium sera donc libre si:I(x) = l(x -Le) + l(Ri -x) < θ (as L increases for l(u) = Pt.min(c, c u α ) and different value of α and Pt. D is the solution of 2l( D 2 ) = θ with θ = -99dBm. Nous invitons le lecteur à lire la thèse dans son intégralité pour obtenir une description du modèle originale de Rényi. Notre extension consiste à prendre en compte les interférences dans la séléction des noeuds plutôt qu'une distance fixe. Nous considérons une autoroute ou une route de taille L. Le modèle donne une borne supérieure sur le nombre de transmetteurs simultanés sur cet intervalle. Autour de chaque émetteur il y a une boule d'inhibition où les interférences sont supérieures au seuil θ. Ces intervalles correspondent aux rectangles hachurés dans la figure A.1(a). Ils sont asymmtriques. Nous définissons une fonction v(s) pour décrire ces intervalles. Pour s (s > 0) distance entre deux émetteurs succéssifs, les interférences pour un point u entre ces deux émetteurs sera l(u) + l(s -u). La distance minimale v(s) pour qu'un noeud au milieu puisse détecter le medium libre est donc: l(v(s)) + l(s -v(s)) = θ (A.3) Cette equation a un sens uniquement si s est suffisament grand (s > 2 • v(s)). Cette distance minimale est notée D avec D solution de 2 • l( D 2 ) = θ. Nous pouvons maintenant décrire le processus de construction de notre modèle (un exemple est donné figure A.1(a)): • Step 0 (initialization): deux points sont positionnés en 0 et L. • Step 1: un nouveau point est uniformément distribué dans [v(L), L -v(L)], à s dans notre exemple. Il y a deux nouveaux intervalles où des nouveaux points peuvet être placés: [0, s] et [s, L]. • Step 2: un nouveau point est uniformément distribué dans [v(s), s -v(s)], à t. Les intervalles à droite et à gauche de t étant plus petit que D aucun autre point ne peut rajouter dans ces 2 itervalles. • Step 3: un nouveau point u est uniformément distribué dans [s + v(L -s), L -v(L -s)]. • Step 4: L'intervalle à droite de u est plus petit que D. Mais un nouveau point peut rajouté sur la gauche, dans l'intervalle [s + v(u -s), u -v(u -s)]. Cela n'est pas montré sur la figure. Ce dernier point est le dernier du processus. Nous notons m(L) le nombre moyen de points dans l'intervalle [0, L]. Malheureusement son calcul exacte est, à notre connaissance, impossible. Cependant nous pouvons montrer sa convergence. est une constante positive. La constante λ peut être utilisée pour évaluer le nombre de transmetteurs simultanés et la capacité du réseau. En effet, m(L) peut être évalué comme λL. Nous obtenons donc: Capacity(L) = λL T (A.5) où T est le temps moyen d'émission d'une trame.

Figure A. 1 :

 1 Figure A.1: Notations du modèle.

9 )

 9 2 ), X n-1 + D], avec S(u) définit par:l(u) + l(S(u)) = θ (Pour des raisons pratiques nous définissons ξ i = X i -X i-1 , avec ξ n distribué dans [S(ξ n-1 ), D].

fTheorem 2

 2 ξn|ξn-1=s (u) = 1 D -S(s) 1 u∈[S(s),D] (A.10) où 1 u∈[S(s),D] est la fonction indicatrice, et g ξn|ξn-1=s (u) = -2 (D -S(s)) 2 u + 2D (D -S(s)) 2 1 u∈[S(s),D] (A.11)La distribution stationnaire est donnée dans la proposition ci-dessous. Le processus (ξ n ) n≥0 définit ci-dessus est une chaîne de Markov. Les distributions stationnaires (des deux fonctions de densités) sont π 1 (s) et π 2 (s) avec:π 1 (s) = a 1 • (D -S(s))1 s∈[S(D),D] (A.12) π 2 (s) = a 2 • (D -s)(D -S(s)) 2 1 s∈[S(D),D] (A.13)où a 1 , a 2 sont des facteurs de normalisations. La chaîne (ξ n ) n>0 converge en total variation vers la distribution π 1 (s) (où π 2 (s)) pour n'importe quelle distribution de ξ 1 dans [S(D), D].

  distance between vehicles (m) Capacity (Mbps/km) Capacity -received bits Packing model: theoretical capacity Markovian model: π 1 (s) Markovian model: π 2 (s) (a) Constant inter-distance.

  distance between vehicles (m) Capacity (Mbps/km) Capacity -received bits Packing model: theoretical capacity Markovian model: π 1 (s) Markovian model: π 2 (s) (b) Traffic simulator.

Figure A. 5 :

 5 Figure A.5: Scenario with experimentation parameters: capacity.

  Mean distance with collision Mean distance in saturation caseMean distance without collision π 1 (s) (a) Constant inter-distance.

Figure A. 6 :

 6 Figure A.6: Scenario with NS-3 default parameters: simultaneous transmitters.

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

Figure A. 7 :

 7 Figure A.7: Scenario with experimentation parameters: capacity.

Figure A. 8 :

 8 Figure A.8: Broadcast ratio for constant and mobile case in pure broadcast scenarios.

  vehicles (m) Capacity (Mbps/km) Power Control received frames Power Control sent frames No Power Control received frames No Power Control sent frames Theoretical model (empirical distribution) Theoretical model (exponential distribution) (a) Constant Total Capacity

  vehicles (m) Capacity (Mbps/km) Power Control received frames Power Control sent frames No Power Control received frames No Power Control sent frames Theoretical model (empirical distribution) Theoretical model (exponential distribution) (b) Mobile Total Capacity

Figure A. 9 :

 9 Figure A.9: Total capacity for constant and mobile case in pure broadcast scenarios.

Table 2 . 1 :

 21 Wireless Ad hoc Network enabling technologies. gateways are stationary entities. They form a backbone of the network and other mesh clients communicate with them through wireless links. Various wireless technologies can be used to implement a Wireless Mesh Network, including IEEE 802.11, IEEE 802.15, even cellular technologies or combination of more than one type.

  2.1.2.1 IEEE 802.11p -WAVE In 2010, IEEE has completed the IEEE 802.11p[16] specification which is an approved amendment to the IEEE 802.11 standard to add Wireless Access in Vehicular Environments (WAVE). It defines enhancements to IEEE 802.11 required to support Intelligent Transportation Systems (ITS) applications. According to the definition of IEEE, Wireless Access in Vehicular Environments (WAVE) IEEE 1609.x

Table 2 . 2 :

 22 IEEE 1609 WAVE Standard components.

	Application
	Presentation Session	IEEE 1609.1	Upper Layers
	Transport
		IEEE 1609.3	Networking Services
	Network
		IEEE 802.2	LLC Sublayer
	Data Link	IEEE 1609.4 IEEE 802.11	MAC Sublayer
	Physical	IEEE 802.11p	Physical
		Medium
	Figure 2.3: IEEE 1609 WAVE Layer model compare to OSI Layer model.

Table 2 . 3 :

 23 Spectrum allocation in different regions.

	It is noteworthy that one should keep in mind the difference in spectrum allocation between
	Federal Communications Commission (FCC) and European Telecommunications Standards In-
	stitute (ETSI). The summary of spectrum allocation for WAVE/DSRC applications is listed in
	Table 2.3.

Table 2 . 4 :

 24 IEEE 802.11p Access categories.

	An example of node contending for access to the medium is illustrated in Figure 2.6. As-
	suming that there are three nodes, Node 1 is transmitting, Node 2 has voice traffic and Node
	3 has best effort traffic, both want to transmit. When Node 1 finishes its transmission, both
	Node 2 and 3 have to wait for an AIFS interval. Since the voice traffic AIFS is smaller than
	the best effort traffic AIFS, Node 2 begins to count down its back-off period then starting its
	transmission. While Node 3 is decreasing its back-off timer, it senses the medium and realizes
	Node 2 is transmitting, it stops its back-off countdown until Node 2 finish. After that, Node
	3 has to wait another best effort AIFS interval, hold its transmission until its back-off timer
	reaches zero.

Table 4 . 1 :

 41 Estimated parameters.

			95% Confidence Interval
	Mean	0.06 -0.13	0.26
	Standard deviation 5.2	5.07	5.24

Table 4 . 2 :

 42 Normal fitting curve values.

Table 4 . 3 :

 43 Simulation parameters on default case.

	Theoretical and NS-3 Parameters Numerical Values
	IEEE 802.11std	802.11p -CCH channel
	Path-loss function	l(d) = P t • min 1, 10 -4.5677 d 3
	CCA mode	CCA mode 1
	ED Threshold (θ)	-99 dBm
	Emission power P t	42 dBm
	Antenna gain	1 dBi
	Number of samples per point	100
	Packet size	400 bytes
	Duration of the simulation	2 sec
	D	4093.7 m
	Road length (L)	20 km
	aTimeslot	13µs
	SIFS	32µs
	Theoretical and NS-3 Parameters Numerical Values
	IEEE 802.11std	802.11p -CCH channel
	Path-loss function	l(d) = P t • min 1, 10 -5.3976 d 1 .9596
	CCA mode	CCA mode 1
	ED Threshold (θ)	-99 dBm
	Emission power P t	30 dBm
	Antenna gain	3 dBi
	Number of samples per point	100
	Packet size	400 bytes
	Duration of the simulation	2 sec
	D	3216.7 m
	Road length (L)	20 km
	DIFS	13µs
	SIFS	32µs

Table 4 . 4 :

 44 Simulation parameters on experimentation case.

Table 5 .

 5

	Theoretical and NS-3 Parameters Numerical Values
	IEEE 802.11std	802.11p -CCH channel
	Path-loss function	l(d) = P t • min 1, 10 -4.5677 d 3
	CCA mode	CCA mode 1
	ED Threshold (θ)	-99 dBm
	Emission power P t	43 dBm
	Antenna gain	1 dBm
	Number of samples per point	100
	Length of the packet	1024 bytes
	Duration of the simulation	2 sec
	D	4093.7 m
	Road length (d)	20 km
	aTimeslot	13 µs
	SIFS	32 µs

1: Simulation parameters on default case.

Table 5 .

 5

	Theoretical and NS-3 Parameters Numerical Values
	IEEE 802.11std	802.11p -CCH channel
	Path-loss function	l(d) = P t • min 1, 10 -5.3976 d 1 .9596
	CCA mode	CCA mode 1
	ED Threshold (θ)	-99 dBm
	Emission power P t	30 dBm
	Antenna gain	3 dBm
	Number of samples per point	100
	Length of the packet	1024 bytes
	Duration of the simulation	2 sec
	D	3216.7 m
	Road length (d)	20 km
	ATimeSlot	13 µs
	SIFS	32 µs

2: Simulation parameters on experimentation case.

Table 5 . 3 :

 53 Simulation parameters.

	Theoretical and NS-3 Parameters Numerical Values
	IEEE 802.11std	802.11p -CCH channel
	Path-loss function	l(d) = P t • min 1, 10 -4.5677 d 3
	CCA mode	CCA mode 1
	ED Threshold (θ)	-140 to -80 dBm
	Emission power P t	43 dBm
	Antenna gain	1 dBm
	Number of samples per point	20
	Length of the packet	1024 bytes
	Duration of the simulation	4 sec
	Road length (d)	50 km
	aTimeslot	13 µs
	SIFS	32 µs

Table 6 . 2 :

 62 Example of a LocalNeighborsList. function of vehicle density. As we can observe, the theoretical capacity can support up to 150 veh/km for National-road and 100 veh/km for Highway.Obviously, to realize the Perception map, we have to either minimize the probe packet size or developing a smart adaptive power control algorithm to meet the criteria on this upper bound of capacity. The work presented in this Chapter is dedicated to this problem and try to give a

	192.168.0.1	-75 dBm	-54 dBm	timeout 1
	192.168.0.3	-60 dBm	-59 dBm	timeout 2
	...	...	...	...

Table 6 . 3 :

 63 Our algorithm manages two lists Default values of the power control algorithm.The first list relies on a link sensing mechanism using HELLO packets. These HELLOs are sent periodically, at a low frequency denoted HELLO INTERVAL (about 1 or 2 seconds), at the maximum transmission power, and include the sender location. It allows each node to keep a global neighbors list, with ID and locations of the neighbors. An entry/neighbor is removed from this list if no HELLO is received for a GLOBAL TIMEOUT period. This algorithm is classical; we do not present the details.

	Parameters	Values
	Application packet frequency	Varying
	HELLO INTERVAL	1 second
	LOCAL TIMEOUT	3× Packet frequency (0.3 sec)
	GLOBAL TIMEOUT	3× HELLO INTERVAL (3.0 sec)
	P max	33 dBm
	φ	-90 dBm
	d ref	50 meters
	∆	1 dBm
	of neighbors.

  Un réseau VANET (Vehicular Ad hoc NETwork) est un réseau composé de véhicules équipés de cartes réseau sans fil. Ils permettent d'étendre la portée des communications au delà de la simple portée radio. Depuis environ 10 ans, la communauté scientifique s'est interessée à ce problème et a developé des protocoles de diffusion permettant de disséminer efficacement des messages d'alertes dans le VANET. Urban Multi-Hop Broadcast (UMB) [2], et Multi-Hop Vehicular Broadcast (MHVB) [3] en sont des exemples. Mais les applications de sécurité routière ont des contraintes différentes des autres applications. Certaines requiert une bande passante importante, d'autres moins. Une des questions préliminaire aux déploiement de ces applications est donc de savoir ce que le réseau VANET est capable d'offrir en terme de débit, de capacité. En effet, avec la technologie prévue pour ces communications, le IEEE 802.11p, tous les noeuds seront sans doute equipés d'une seule carte radio utilisant le même canal. Le canal sera donc partagé dans le temps et dans l'espace. Lorsque deux véhicules sont suffisament éloignés l'un de l'autre ils peuvent émettre en même temps sans interférer. La possiblité de réutiliser le medium différents endroits est la réutilisation spatiale. Clear Channel Assessments (CCA) est le sous mécanisme du 802.11p qui fixe cette réutilisation spatiale. En effet, le CCA va indiquer à un noeud si le medium est libre ou non. Il prvoit 3

	A.2 Estimation de la capacité et optimisation
	A.2.1 Définition du problème
	A.2.1.1 Estimation de la capacité
	L'éstimation de la capacité est donc fondamentale dans la mesure où elle limite les applications
	qui pourront être déployées. En conséquences, elle doit être éstimée a priori. Elle est définit

Cette thèse tente de répondre à cette question. Ces contributions sont résumées ci-dessous:

• Nous proposons des bornes supérieures théoriques sur le volume qu'est capable de transporter le réseau en terme de kilobits par second et par kilomètre. La borne proposée est atteignable en pratique, et permet donc d'être utilisée comme un vrai outil de dimensionnement pour les applications.

• Nous calculons la distribution de la distance entre les véhicules. Cette quantité permet d'étudier un certain nombre de propriétés radio comme le taux d'erreures trames, le rapport signal à bruit, etc. Ceci nous offre également un moyen d'optimiser le mécanisme d'accès au medium de la norme IEEE 802.11p.

• Enfin, nous nous intéressons à une application particulière de sécurité routière: perception map application. Celle-ci requiert une capacité importante. La première partie de la thèse ayant montré que celle-ci n'était pas disponible, nous proposons un mécansime de contrôle de puissance permettant de l'offrir au final. comme le nombre de kilobits ou Megabits par seconde et par kilomètre que le réseau est capable de transporter. Le principal phénomène limitant la capacité est la réutilisation spatiale du medium. méthodes: 1. CCA Mode 1: Energy above threshold. Le medium est considéré occupé si le niveau d'énergie dépasse un seuil donné (seuil CCA). 2. CCA Mode 2: Carrier sense only. Le medium est considéré occupé si un signal 802.11p est détecté (signal ayant la même modulation par exemple).

3. CCA Mode 3: Carrier sense with energy above threshold. Le medium est considéré occupé si l'une des deux ou les deux méthodes précédentes ont détèctés un medium occupé. Le CCA s'assure qu'il y a une distance minimale entre les noeuds permettant des transmissions sans erreures (hormis lorsqu'il y a une collision). Il limite donc le nombre de noeuds qui peuvent utiliser le medium en même temps et donc la capacité du réseau. Dans la suite, nous proposons de modéliser le CCA afin d'offrir une borne sur la capacité.

A.2.2 Hypothèses

Notre borne modèle le mode 1 du CCA, où c'est le niveau d'énergie, c'est à dire la somme des interfèrences qui est pris en compte. Avec ce mode, le medium sera supposé libre si le niveau d'interférences est inférieures au seuil θ (seuil CCA). Nous considérons une fonction

•

  Default parameters case: autoroute de 20 km. Pour ces simulations nous prenons les paramètres par défaut du simulateur NS-3. Les autres paramètres sont donnés dans la table A.1.• Experimentation parameters case: autoroute de 20 km. Ce scenario prend en compte les résultats des expérimentations. Les autres paramètres sont donnés dans la table A.2.Pour chaque scenario, nous avons considéré deux types de trfic routier: une distance constante entre les véhicules, et des trajéctoires de véhicules issues d'un simulateur de tarfic. = P t • min 1,10 -4.5677

	Theoretical and NS-3 Parameters Numerical Values
	IEEE 802.11std	802.11p -CCH channel
	Path-loss function	l(d) d 3
	CCA mode	CCA mode 1
	ED Threshold (θ)	-99 dBm
	Emission power P t	43 dBm
	Antenna gain	1 dBm
	Number of samples per point	100
	Length of the packet	1024 bytes
	Duration of the simulation	2 sec
	D	4093.7 m
	Road length (d)	20 km
	aTimeslot	13 µs
	SIFS	32 µs

Table A . 1 :

 A1 Simulation parameters on default case. A.2.5.1 Résultats sur la capacité et l'intensité Dans les figures A.2 et A.4, nous pouvosn observer le nombre moyen de transmetteurs simultanés comparés à notre bore analytique et au modèle Markovien. La capacit est quand à elle représentée sur les figures A.3 et A.5. Comme nous pouvons l'observer sur ces figures le "packing model" nous donne une éstimée très précise de la capacité. La différence entre le modèle Markovien est un peu plus important mais reste très correcte: seulement 0.78%. A.2.5.2 Distribution de la position des émetteurs Sur les figures A.6 et A.7, nous pouvons observer la distribution des distances. Les abscisses

sont l'intervalle [S(D), D]. Pour certaines courbes nous avons filtrer certains échantillons, sans

Table A . 4 :

 A4 100m. De plus ces données doivent être échangées à de grandes fréquences. L'idée est donc de proposer un Table A.3: Example of a LocalNeighborsList. Default values of the power control algorithm.système de contrôle de puissance. Celui-ci permet de diminuer la puissance d'émission pour s'adapter aux courtes mises en jeux ici. La réutilisation spatiale peut ainsi être augment et donc la capacité. Notre algorithme vise à diminuer le plus possible la puissance d'émission tout en garantissant que les tous véhicules à moins d'une certaine distancereçoivent correctement les trames. Notre algorithme est conçu pour l'application "perception map" et s'applique donc uniquement à ses paquets. L'algorithme prévoit 3 procédures: met à jour la liste des voisins à moins de d ref mètres, surveille la qualité des réceptions pour ces noeuds, et augmente ou diminue la puissance d'émission en fonction de ces informations.A.3.2.2 Détails de l'algorithmeNous supposons que tous les noeuds sont équipés de GPS. Chaque noeud gère deux listes de noeuds, une liste globale des noeuds à portée radio (pour la puissance d'émission maximale) et

	192.168.0.1	-75 dBm	-54 dBm	timeout 1
	192.168.0.3	-60 dBm	-59 dBm	timeout 2
	...	...	...	...
	Parameters	Values
	Application packet frequency	Varying
	HELLO INTERVAL	1 second
	LOCAL TIMEOUT	3× Packet frequency (0.3 sec)
	GLOBAL TIMEOUT	3× HELLO INTERVAL (3.0 sec)
	P max		33
	θ		-90 dBm
	d ref		50 meters
	∆		1 dBm
	A.3.2 Algorithme
	A.3.2.1 Motivation

To ...

√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.

Acknowledgements

A.4 Conslusions D'autres améliorations pourraient être apportées à l'algorithme de contrôle de puissance.

Son paramétrage pourrait être adaptatif, et il serait intéressant de l'implémenter sur une plate forme rèelle afin de l'évaluer.

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

Transmission power control related works

Transmission Power Control is a well-known technique that allows nodes to transmit their data with different power levels. It is broadly studied in both cellular networks and wireless networks. However, most of the studies in the literature try to find an optimal transmission power to minimize or maximize a specific constrains (throughput, capacity or energy saving, etc). For instances, in [66], authors try to minimize the power consumption. In [START_REF] Qiao | Adaptive transmit power control in ieee 802.11a wireless lans[END_REF], [START_REF] Jung | A power control mac protocol for ad hoc networks[END_REF],

authors propose to enforce an RTS/CTS frame exchange before each data transmission, and then select the most energy-efficient combination of the PHY mode and the transmit power level for the subsequent data frame transmission to save energy. However, energy efficiency is not an issue in VANETs where we may consider that nodes have an unlimited power supply. Moreover, in [START_REF] Qiao | Adaptive transmit power control in ieee 802.11a wireless lans[END_REF], [START_REF] Jung | A power control mac protocol for ad hoc networks[END_REF], authors focus on infrastructure model where Point Coordinator Function (PCF) is applied; hence, it is not suitable for VANETs. In [START_REF] Kawadia | Power control and clustering in ad hoc networks[END_REF], authors propose CLUSTERPOW algorithm aims to increase the network capacity by increasing spatial reuse, but the context of this paper is MANET with the connectivity target. Therefore, in VANETs context, this algorithm becomes impractical.

In [START_REF] Elbatt | Power management for throughput enhancement in wireless ad-hoc networks[END_REF], [START_REF] Wattenhofer | Distributed topology control for power efficient operation in multihop wireless ad hoc networks[END_REF], authors try to resolve the trade-off between the transmission power and the throughput of the network. Besides, some studies, such as [START_REF] Narayanaswamy | Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the compow protocol[END_REF], try to adapt transmission power per packet to ensure the connectivity between nodes for unicast flows. However, this kind of approach seems to be impractical for VANETs where broadcast is the most compromising transmission method. Indeed, fast mobility characteristic of VANETs make maintaining routing information for unicast a difficult task. Some other proposed works for VANETs are considered in a pure broadcast environment [START_REF] Li | An analytic model predicting the optimal range for maximizing 1-hop broadcast coverage in dense wireless networks[END_REF][START_REF] Li | Using adaptive range control to maximize 1-hop broadcast coverage in dense wireless networks[END_REF]. In these studies, authors propose an analytically model able to find a transmission power that maximized 1-hop broadcast coverage, and an adaptive algorithm that converges to the beforehand fixed transmission power. Although, they focus on a pure broadcast environment, but, their assumptions are unrealistic for VANETs: a) all nodes are static and b) all nodes use the same transmission power.

Another approach in power control is adapting the transmission power regards to the surrounding information. For example, in [START_REF] Krunz | Transmission power control in wireless ad hoc networks: challenges, solutions and open issues[END_REF], authors try to adapt power level according to the node degree (number of neighbours), but this approach may have problem with clustered network and VANETs should be considered in 1-D rather than 2-D. In [START_REF] Artimy | Local density estimation and dynamic transmission-range assignment in vehicular ad hoc networks[END_REF], authors propose an algorithm to assign transmission power dynamically based on estimation of vehicle density. This estimation algorithm is based on traffic theory. Vehicle only uses internal information about Also, we prove that ξ n converges in total variation (it implies convergence in distribution) to π 1 (or π 2 ) for any initial distribution of ξ 1 in (S(D), D]. 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(D), D] and A ⊂ [S(D), D] 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(D), D] 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:

) is the distribution of ξ n (n > 1) given ξ 1 . It may be defined recursively:

First, note that if order to achieve this goal, we need to develop efficient ways to build dynamic and reactive perception maps. These perception maps give both a local representation and modeling of the information resources needed to ensure a high quality and reliability of embedded applications like ACC, Stop and Go, road departure avoidance, collision mitigation. In Figure 6.1, we give an example of the embedded sensors that may be equipped in a vehicle. In fact, from the front local perception, we had only a short range perception in front of the ego-vehicle. This local perception centered around the ego-vehicle positioning provides a local risk assessment from the information about near obstacles, road marking and lanes, and ego-vehicle dynamic information.

Recently, it is become important to extend the perception range in order to anticipate the hazardous situation (risk assessment) and to provide information for autonomous driving applications (copilot application with path planning and navigation functionalities) [START_REF] Vanholme | A legal safety concept for highly automated driving on highways[END_REF]. The extended map modeling is both a spatial and temporal representation of a specific extended situation (limited in the local map by sensor ranges) allowed by communication means. By using communications within a range of less than 50-100 meters, we can send information to the other vehicles moving both in front and in the rear of our position. This local information can also be used in order to inform vehicles far away from the ego-vehicle (in rear position)

to have enough information to assess a risk indication. Such an application has been already

tested in [START_REF] Demmel | Simulation architecture for cooperative its applications and augmented perception[END_REF][START_REF] Demmel | An ieee 802.11p empirical performance model for cooperative systems applications[END_REF] and prove its efficiency to reduce the global risk point of view. In these papers, the authors compare the performance of a cooperative risk assessment using an extended map against a non-cooperative approach based on local-perception only. The results of this study show a systematic improvement of forward warning time for most vehicles in a platoon scenario when using the extended-map-based risk assessment.

But, data quality heavily depends on both the quality of the local algorithms used to perceive the environment, and the communication capability to send an amount of data in a short time and in a dense traffic configuration. The more delay the communications have, the more uncertainties on the data (especially the position, speed, and heading) will be degraded and unusable. With the required frequency of exchanged between vehicles (up to 100 Hz), and the expected radio range of the IEEE 802.11p technology (up to 1km), such application may not be supported due to the lack of network capacity precisely indicated in the following part.

Perception map capacity requirement

Each probe packet generated by the Perception map application is composed of all actors given in the Table 6.1 [START_REF] Demmel | Simulation architecture for cooperative its applications and augmented perception[END_REF]. To estimate the preliminary requirement capacity, we considered two types of road, the National-road and the Highway. Typically, a National-road has 2 lanes while a Highway has 3 lanes. This difference leads to a variation on the number of Obstacles and Roadway actors. Each lane has a dedicated Obstacles and Roadway actors, therefore, the Obstacles and Roadway actors are duplicated according to the type of road (2 times for the National-road and 3 times for the Highway). Every actor put in frame is separated by 4 bits of start and 4 bits of stop, equivalent to 1 byte per actor. First, we estimate the size of each probe packet. Then, this result is applied for all vehicles with a specific transmission frequency.

Actor Subframe (bytes) Actor Subframe (bytes)

Ego-vehicle Position (6) Weather conditions Type (1) Speeds ( 6)

Density ( 1) Variances ( 6)

Visibility ( 1) Heading ( 2)

Distance (1) Roadway Attributes (6) Road signs Position ( 6) Type ( 2)

Type (1) Confidence ( 1)

Information (1) Obstacles

Id (1) Additional information Risk level (1) Position ( 6)

Warning (1) Speeds ( 6)

Mode (1) Variances ( 6) Heading ( 2) Confidence (1) Table 6.1: Perception map application probe packet structure and corresponding field size.

In Figure 6.2(a), we compared the maximum theoretical capacity given by the Packing model with realistic wireless propagation environment described in Chapter 4 with the requirement capacity generated by the Perception map with the worst traffic density (400 veh/km). To guarantee the quality of the Perception map, probe packets must be sent every 100 ms (equivalent to a transmission frequency of 10 Hz). Nonetheless, as it is shown, we can only support up to 3.7 Hz transmission frequency for National-road or 2.5 Hz for Highway.

In Figure 6.2(b), we fixed the transmission frequency of the Perception map at 10 Hz. We compared the maximum theoretical capacity with the one required by this application as the The algorithm includes 3 sub-procedures. The three procedures are detailed in Algorithm 1, 2 and 3. Each node has a global variable TxPower that sets the transmission power of the probe packets. When a node R receives a probe packet from a node E, it calls the Reception() procedure. R updates the LocalNeighborsList, and increases the transmission power if R is not in LocalNeighborsList of E that sent this probe (meaning that the transmission power of R is not sufficiently high to reach its neighbor E). When a node wants to transmit its probe, it calls the Transmission() procedure. Interference at location x is thus formally described as:

where le and ri are the locations of the two closest interferers on left and right hand sides of x. P le (resp. P ri ) is the transmitting power from node at le (resp. ri). P y is thus a random variable describing the transmission power for a node at location y. Transmitting powers are assumed i.i.d., and greater than θ almost surely (the transmitting power is greater than the CCA detection threshold).

Our model is built as follows. We consider an interval [0, L] with L ∈ IR + . We assume that there are two points/nodes at 0 and L. For L sufficiently great, there are two subintervals denoted [0, v(0, L, P 0 , P L )] and [0, v(L, 0, P L , P 0 )] (represented in Figure 6.3) where the interference level is greater than θ. V(0,u,P 0 ,P u ) V(L,u,P L ,P u ) V(u,0,P u ,P 0 ) V(u,L,P u ,P L ) Intervals overlap V(u,v,P u ,P v )

V(v,u,P v ,P u ) V(L,v,P L ,P v )

V(v,L,P v ,P L )

V(u,w,P u ,P w ) V(v,w,P v ,P w )

V(w,u,P w ,P u ) V(w,v,P w ,P v ) Two different simulation scenarios had been considered: the pure broadcast and the heterogeneous transmission. The pure broadcast scenarios assumed that broadcast method is the solely transmission scheme realized in VANET. The heterogeneous transmission, a more common situation, considered both broadcast and unicast transmission. The unicast application used systematically the maximum transmission power and is simulated to evaluate the behavior of our algorithm on extended map application when it co-exists with classical applications. Each point in the different figures are computed as the mean of 100 simulations and are presented with a confidence interval at 95%. All simulation scenarios considered two mobility models:

"constant mobility" where vehicles have a 104 km/h constant velocity, and "Gaussian mobility"

where the vehicle speeds follow a Gaussian distribution with mean 104 km/h and variance 43.

These values have been set according to vehicle speeds collected on Canadian highways [START_REF] Macangus | Speed characteristics on manitobas national highway system roads using weigh-in-motion data[END_REF].

The other parameters used in both scenarios are given in Table 6.4.

Pure broadcast scenarios

In this scenario, vehicles periodically broadcast probe packets using the TPC algorithm as defined in Section 6.2. These simulations aim to estimate the maximum rate reachable by our TPC algorithm. In order to estimate this maximum capacity we had to consider two different application rates. Indeed, as we increase the number of vehicles, a constant rate led to significant contention and a poor throughput when the traffic density became high. To keep a reasonable geneous transmission scenario. Besides of periodically broadcasting probe packets as in the pure broadcast scenario, vehicles were installed with unicast client server applications. During the simulation time, a Vehicle A (the client) send UDP packets to its adjacent neighbor vehicle B that is acting as a server. Oppositely, vehicle B also plays the role of the client and transmitting UDP packets to vehicle A who is serving as server. The number of periodically broadcasting probe packets generated by our perception map application and the generating rate of unicast application were constant, at 100 packet/sec.

To emphasize the gain of our algorithm, we performed the same simulations with and without the TPC algorithm. TPC applies only to the perception map application. It means that in any case, unicast packets were transmitted at the maximum constant power level P max . The metrics used to assess the performance of our TPC algorithm are the same as in the pure broadcast scenario: broadcast ratio and the spatial capacity.

Figure 6.7 depicted the improvement of capacity with and without the power control algorithm and considered the two mobility models. It can be observed that the capacity is increased up to 250%, approximately 10 Mbps/km (with power control) compare to 4 Mbps/km (without power control). The capacity plotted in this figure is the total capacity taken into account both broadcast and unicast packets. The theoretical bounds still offer good estimations. Additionally, we also plotted in Figure 6.8 the capacity corresponding to each particular transmission method. In this figure, only the real capacity, measured as the number of received packets, is illustrated for a clearer-understandable description. Figure 6.8 shows that the capacity improvement is happened for both transmission methods, approximately 8 Mbps/km (broadcast) and 1.05 Mbps/km (unicast) with the TPC, compare to 2.95 Mbps/km (broadcast) and 0.6

Mbps/km (unicast) otherwise.

The broadcast ratio is defined as the same in the pure broadcast scenario and it is shown in Figure 6.9. In this heterogeneous transmission scenario, this metric is perfectly matched for both cases: with and without using power control. It definitely indicates that our TPC power control algorithm can significantly enhance the capacity while keeping the delivery rate.

Summary

Some safety applications using VANET exchange a large amount of data, and consequently require an important network capacity. In this Chapter, we focus on extended perception map applications that use information from local and distant sensors to offer driving assistance

Summary

(autonomous driving, collision warning, etc). Extended perception requires a high bandwidth that might not be available in practice in classical IEEE 802.11p ad hoc networks.

We proposed an adaptive TPC algorithm dedicated to extended perception map building.

It is based on signal strength measurements of the packets generated by the application. It is worth noting that without power control, the perception map application is likely unusable by lack of capacity. We have shown through simulations and a theoretical model that this algorithm may improve the network capacity up to 10 times in a pure broadcast environment and 2.5 times in a heterogeneous transmission environment. It offers an extended bandwidth while keeping good transmission reliability.

Although, this algorithm can offer a higher network capacity, there still exists some works which can be done to improve it. For example, we can tune its parameters (φ for an instance) to achieve better performances. Besides, other factor that might downgrade the network capacity when using this algorithm is the delay of electronic device when we switch the transmission power. Therefore, in the future we need to take into account this fundamental problem to offer a more realistic model.

warning, etc). The first part of our work applies directly to the design of these applications.

It showed that the IEEE 802.11p technology used with its default parameters does not offer the required capacity of this application. To solve this problem, we proposed an adaptive TPC algorithm dedicated to this application to fulfill its capacity requirement. It is based on signal strength measurements of the packets generated by the application. Our algorithm offers an extended bandwidth while keeping good transmission reliability.

Future research

The research reported in this thesis suggests several interesting open problems. Other open issues are to optimize the proposed TPC algorithm and implementing this algorithm in practice. In fact, we can tune the parameters of this algorithm (φ for an instance) to achieve better performance. Besides, in practice, the delay of electronic devices when switching the transmission power cannot be neglected. Therefore, in the future we need to take into account this delay to offer a more realistic model. L'économie liée à l'automobile a joué un rôle important dans la croissance mondiale, mais l'avènement de l'automobile a aussi ses inconvénients tels que la pollution, les bouchons, et les accidents. Une étude menée par la "World Heath Organization" et la "Chinese Academy for Environmental Planning" sur l'impact de la pollution sur la santé montre qu'entre 350000 et 500000 personnes meurent prématurément chaque année du aux effets de la pollution. A Jakarta, la capitale de l'Indonésie, où il faut parfois jusqu'à deux heures pour faire un kilomètre, il existe uin mot spéciale "macet" pour dèfinir les bouchons extrêmes. Au Vietnam, 10000 personne meurent chaque année dans des accidents de la route.

Appendix A Version Française

Améliorer la sécurité routiére est devenue une priorité de la recherche automobile. Les inventions des 20-30 dernières années comme la ceinture de sécurité, l'AIR-BAG, l'ABS, etc.

A.3.3 Random packing model

Step 0

Step 1

Step 2

Step 3

(a) Random packing model example.

A.3.4 Simulations