Ines Khoufi

Erwan Livolant

Pascale Minet

Mohamed Hadded

Keywords: Vehicular Adhoc NETworks (VANETs), MAC, TDMA, highway environments, schedule, time slot assignment, safety-critical applications, routing, infrastructure, cluster, multi-hop communication Réseaux Véhiculaires (VANET), MAC, TDMA, ordonnancement, allocation des slots de temps, les applications de sécurité routière, routage, infrastructure, cluster, communication multi-sauts

Road crashes and the damage they entail represent a serious issue and are one of the main causes of death. Some statistics have shown that the majority of road accidents are due to human error and 60% of these accidents could have been avoided if the driver had been warned at least 0.5 sec beforehand. In this context, Vehicular Ad hoc NETworks, known as VANETs, are deployed to reduce the risk of road accidents as well as to improve passenger comfort by allowing vehicles to exchange different kinds of data between the vehicles themselves and potentially between the vehicles and the infrastructure. The data exchanged between vehicles ranges widely from road safety messages and traffic management to infotainment. Nowadays, safety applications are receiving a great deal of attention from researchers as well as from automobile manufacturers. In this thesis, we particularly focus on safety-critical applications, designed to provide driver assistance in dangerous situations and to avoid accidents in highway environments. Such applications must guarantee that the vehicles can access the wireless medium and have strict requirements regarding end-to-end delay and packet loss ratio. Therefore, our main goal is to propose new medium access control and routing protocols, which can efficiently adapt to frequently changing of VANET network topologies.

After a comprehensive overview of free-contention MAC protocols, we propose several solutions, based on Time Division Multiple Access Technique (TDMA). We have designed DTMAC, a fully distributed TDMA-based MAC protocol, which does not rely on an expensive infrastructure. DTMAC uses vehicles' locations and a slot reuse concept to ensure that vehicles in adjacent areas have collision-free schedule. Using simulations, we prove that DTMAC provides a lower rate of access and merging collisions than VeMAC, a well-known TDMA based MAC protocol in VANET. Then, in order to ensure that event-driven safety messages can be sent over a long distance, we propose TRPM, a TDMA aware Routing Protocol for Multi-hop communication. Our routing scheme is based on a cross layer approach between the MAC and the routing layers, in which the intermediate vehicles are selected using TDMA scheduling information. Simulation results show that TRPM provides better performances in terms of average end-to-end delay, average number of hops and average delivery ratio.

In the second part, we focus on coordinator-based TDMA scheduling mechanisms. First, we propose the Centralized TDMA based MAC protocol (CTMAC) which uses Road Side Units (RSU) as a central coordinator to create and maintain the TDMA schedules. CTMAC implements an Access Collision Avoidance mechanism ii iii that can prevent the access collision problem occurring more than twice between the same vehicles that are trying to access the channel at the same time. Using simulation, we show an improvement in terms of access and merging collisions as well as the overhead required to create and maintain the TDMA schedules compared to distributed scheduling mechanisms. However, in the CTMAC protocol, fast moving vehicles will need to compete for new slots after a short period of time when they leave their current RSU area, which makes a centralized scheduling approach very expensive. In order to further improve the performance of coordinator-based TDMA scheduling mechanisms, we focus on cluster-based TDMA MAC protocols in which some vehicles in the network are elected to coordinate the channel access, allowing the vehicles to remain connected with their channel coordinator for a longer period of time. To this end, first we propose an adaptive weighted clustering protocol, named AWCP, which is road map dependent and uses road IDs and vehicle directions to make the clusters' structure as stable as possible. Then, we formulate the AWCP parameter tuning as a multi-objective problem and we propose an optimization tool to find the optimal parameters of AWCP to ensure its QoS. Next, we propose ASAS, an adaptive slot assignment strategy for a cluster-based TDMA MAC protocol. This strategy is based on a cross layer approach involving TDMA and AWCP. The objective is to overcome the inter-cluster interference issue in overlapping areas by taking into account vehicles' locations and directions when the cluster head assign slots.

Acknowledgement

First of all, I would like to thank professors Mr Yacine Ghamri Doudane and Mrs Sihem Guemara for kindly accepting to review my thesis. Also, my thanks go to the members of the jury for reading my manuscript and their interest on my research: Mr Guy Fayolle, Mr Marcelo Dias De Amorim and Mr Sami Tabbane.

I would never have been able to successfully finish my dissertation without first the guidance of my advisors and second the support and help from my family and friends.

I would like to express my deepest gratitude to my advisors, Mr Paul Muhlethaler and Mr Anis Laouiti, for their excellent guidance and their continuous support of my PhD study. I have enjoyed worked with them over the last three years. Without their help and advice, I would not be able to write this dissertation. They inspired me to do my best to accomplish my goals. They helped me to grow professionally and I learned many skills from them that will be of greatest assistance in my future career. My thanks go also to my co-advisor Mrs Leila Saidane for her scientific advice and knowledge and insightful discussions and suggestions.

I also thank Mrs Christine Anocq, Mrs Valerie Mateus and Mrs Brigitte Laurent for their valuable help and support. They always made my administrative tasks so much easier.

I would like to express my special thanks to Mr Richard James for the considerable time and effort he spent correcting my papers and this dissertation.

I would also like to thank my parents Abdessalem and Jalila, my sister Marwa, my two brothers Marwen and Khalifa. They were always supporting me and encouraging me with their best wishes.

Finally, I want to address my kind regards to the many friends inside Telecom SudParis, Inria and ENSI and also outside for the excellent and truly enjoyable ambiance. My warmest thanks go to, hoping not to forget any of the names, Khalifa Toumi, Inès Khoufi, Yassine Lehiani, Nessrine ben Hassine, Hamza Chniter, Nabil Bouri, Mejdi Maaloul, Aroua Sabrine, Soumaya Argoubi, Younes Bouchaala, Nedya Boufares, Hana M'hamdi, Rim Jouini, Ridha Soua, Ahmed Soua, Dhaou Brini. I am grateful to all of you, for your support and encouragements as well as the fun times I have shared with you. General Introduction

Contents

List of Tables

Background and motivations

The continuing increase in road traffic accidents worldwide has motivated the development of Intelligent Transportation Systems (ITS) and other applications to improve road safety and driving comfort. A communication network, called a VANET 1 , in which the vehicles are equipped with wireless devices has been developed to make these applications feasible. Recently, VANETs have attracted a lot of attention in the research community and in automobile industries due to their promising applications. Nevertheless, VANETs have own specificities: high node mobility with constrained movements and the mobile nodes have ample energy and computing power (i.e. storage and processing) [START_REF] Kumar | Mobile Agent as an Approach to Improve QoS in Vehicular Ad Hoc Network[END_REF]. In a VANET, communications can either be Vehicleto-Vehicle (V2V) or Vehicle-to-Infrastructure (V2I) [START_REF] Tse | Improving message reception in vanets[END_REF]. The applications of VANET can be divided into the following three services namely, safety services, traffic management and user-oriented services [START_REF] Hartenstein | A tutorial survey on vehicular ad hoc networks[END_REF]3]. Safety services have special requirements in terms of quality of service. In fact, bounded transmission delays as well as low access delays are mandatory in order to offer the highest possible level of safety. At the same time, user-oriented services need a broad bandwidth. MAC 2 protocol will play an important role in satisfying these requirements. In VANETs, nodes share a common wireless channel by using the same radio frequencies and therefore an inappropriate use of the channel may lead to collisions and a waste of bandwidth. Hence, sharing the channel is the key issue when we seek to provide a high quality of service.

MAC schemes must be designed to share the medium between the different nodes 1 Vehicular Ad-hoc NETwork 2 Medium Access Control 1 both efficiently and fairly. However, due to the special characteristics of VANETs, traditional wireless MAC protocols are not suitable for use in VANETs which leads either to adapting these traditional MAC protocols or to designing new mechanisms.

Generally, MAC protocols fall into one of two broad categories: contention-based and contention-free. In contention-based protocols, each node can try to access the channel when it has data to transmit using the carrier sensing mechanism [4]. Several neighboring nodes can sense a free channel, and so decide to access and transmit their data at the same time, which generates collisions at the destination nodes.

Contention-free MAC protocols try to avoid this issue by assigning access to the channel to only one node in a neighborhood at any given time. Contention-based protocols do not require any predefined schedule, each node will compete for channel access when it needs to transmit, without any guarantee of success. For real-time applications, random access may cause problems such as packet loss, or large access delay. On the other hand, contention-free protocols can provide bounded-delays for real-time applications, but require the periodic exchange of control messages to maintain the schedule table and require time synchronization between all the nodes in the network.

In order to provide QoS and reduce collisions in VANET, MAC protocols must offer an efficient broadcast service with predictable bounded delays. Moreover, they must also handle frequent topology changes, different spatial densities of nodes and the hidden/exposed node problem. They have to support multi-hop communication and nodes (vehicles) moving in opposite directions. The relevance of these issues has been confirmed by the development of a specific IEEE standard to support VANETs.

The IEEE 802.11p [START_REF]IEEE standard for information technology-Telecommunications and information exchange between systems-local and metropolitan area networksspecific requirements part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) and physical layer (PHY) specifications amendment 6: Wireless access in vehicular environments[END_REF], which is the emerging standard deployed to enable vehicular communication, is a contention-based MAC protocol, using a priority-based access scheme that employs both Enhanced Distributed Channel Access (EDCA) and Carrier

Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanisms [START_REF] Uzcátegui | WAVE: A Tutoriat[END_REF]. However, the IEEE 802.11p standard does not provide a reliable broadcast mechanism with bounded communication delay [START_REF] Hadded | Tdmabased mac protocols for vehicular ad hoc networks a survey, qualitative analysis and open research issues[END_REF]. This disadvantage is particularly challenging in VANETs which are specially designed to improve road safety. Therefore, designing an efficient MAC protocol that satisfies the QoS requirements of VANET applications is a particularly crucial task.

Currently, a great deal of research work on contention-free MAC protocols for VANETs is being carried out. These protocols help avoid the disadvantages of the IEEE 802.11p standard by eliminating the need for a vehicle to listen to the channel before it starts its transmission and by reducing the time to access the channel when node density is high. Several contention-free MAC protocols have been proposed in the literature for inter-vehicle communications including Frequency Division Multiple Access (FDMA), Code Division Multiple Access (CDMA), and Time Division Multiple Access (TDMA). These protocols solve the collision problem as in the IEEE 802.11p standard by assigning respectively a unique frequency band, code sequence or time slot to each vehicle in a given channel contention area 3 . Therefore, these protocols are suitable for VANET safety applications in terms of access delay and collision rate. FDMA-based MAC protocols require that the transmitter and the receiver be synchronized to the same channel frequency. Hence, a frequency synchronization mechanism is necessary to match the communicating vehicles to each other.

The synchronization algorithm usually requires creating a dedicated control channel frequency which will be used by the vehicles to negotiate frequencies by exchanging control messages. This makes the FDMA mechanism very complex and adds a high communication overhead. Unlike FDMA, the CDMA scheme uses the same channel frequency which is shared between different vehicles by assigning unique code sequences. At the beginning of each communication, the sender and receiver must agree on the code to use in a way that reduces the risk of collision as much as possible.

A CDMA code assignment algorithm is therefore required to negotiate and allocate codes for every communication, which means that the CDMA scheme has a significant overhead and an increased transmission delay.

An emerging area of research in the field of VANETs is TDMA-based MAC protocols where the time is divided into slots and only one vehicle can access the channel at each time slot. In TDMA all the vehicles use the same frequency channel without any code sequence but at a different time. This means that the transmitter and the receiver have to be frequency synchronized. In contrast to the FDMA scheme, which can suffer from interference between vehicles using the same frequency band and start transmitting at the same time, the TDMA technique ensures that they will not experience interference from other simultaneous transmissions. Moreover, TDMA can efficiently support I2V communication, as fixed RSUs can be used to create and manage the TDMA slot reservation schedule. Another important feature of the TDMA scheme is that it allows a different number of time slots to be allocated to different vehicles. This means that the bandwidth resources can be assigned on-demand to different vehicles by concatenating or rescheduling time slots based on access priority.

Recently, MAC protocols, notably those that are based on the TDMA technique, have attracted a lot of attention and many protocols have been proposed in the literature.

Although these protocols can provide deterministic access time without collisions, they must be aware of slot allocation of neighboring vehicles. In addition, most of them make use of real-time systems that provide location and time information such as the Global Positioning System (GPS) which allow them to synchronize the communicating vehicles. However, many issues arise due to the high vehicle mobility in VANETs and, therefore, the scheduling mechanism in TDMA protocols should take this into consideration so as to avoid collisions. In our study we focus on contentionfree MAC protocols , particularly those that are based on the TDMA technique. This thesis has the following objectives:

• Introduce a set of TDMA-based MAC protocols that take into account the unique VANETs topology features without having to use expensive spectrum and complex wide-band mechanisms such FDMA or CDMA. These solutions should be able to dynamically adapt to frequent changes in VANET network topologies as well as provide a reliable one-hop broadcast service that can ensure collision-free and delay-bounded transmissions for safety applications.

• Present a TDMA-aware routing protocol for real-time and multi-hop communications that can ensure coherent decisions between the MAC and routing layers by selecting the next relay node based on the TDMA schedule. The main goal of this work is to allow vehicles to send their event-driven safety messages over long distances.

Main contributions

The main contributions of this thesis are summarized below:

1. Contribution 1: Design issues and specificities of TDMA based MAC

protocols in VANETs

We provide a survey of TDMA-based MAC protocols and we discuss how well these protocols can satisfy the stringent requirements of VANET safety applications and how well they can handle the highly dynamic topology and the various conditions of vehicular density that are often present in VANET. Moreover, we classify these protocols into three different categories based on the network topology. We identify the problems that can occur with TDMA and we list some TDMA protocols found in the literature. After having discussed the protocols recently proposed for VANETs, we highlight some open issues which may become new research areas in the future. The routing protocols which are proposed for VANETs are generally designed to find the best path for end-to-end packet delivery, which can satisfy QoS requirements by considering the number of relay nodes and link lifetime. Although these protocols can achieve good performance in terms of the metrics studied, they are not simultaneously optimized to maximize the overall network performance. In order to tackle this issue, we design a TDMA-aware routing protocol for multi-hop VANETs, called TRPM that allows a vehicle to send its event-driven messages over a long distance. This routing scheme can ensure coherent decisions between the MAC and routing layers by selecting the next relay node based on the DTMAC scheduling scheme.

Contribution 4: Design and evaluation of stable and adaptive clustering protocols in VANETs

Another solution is clusters with Cluster Heads (CHs) which would control the TDMA scheduling. However, the main challenges in cluster-based TDMA protocols are the stability of clusters and the overhead generated to elect the cluster head and maintain the cluster members in a highly dynamic topology. However, designing an efficient clustering protocol is no simple task in VANETs due to the rapid changes in network topology. Hence, in this contribution, we identify and discuss certain essential features that the clustering protocols must satisfy in order to build stable clusters in VANETs and we propose two clustering algorithms to cope with clusters instability. The first is an adaptive weighted clustering protocol, called AWCP, which is road map dependent and uses road IDs and vehicles' directions in order to make the clusters as stable as possible. The second is an Angle-based Clustering Algorithm (ACA), which exploits the angular position and the direction of the vehicles to select the most stable vehicles that can act as cluster heads for as long a time as possible.

5. Contribution 5: Multi-objective framework combining NSGA-II and ns2 for AWCP QoS optimization

Due to the high number of feasible configurations of AWCP and the conflicting nature of its performance metrics, AWCP parameters tuning is an NP-hard problem. Therefore, finding the best parameter settings to optimally configure the AWCP protocol is the key aim of this fifth contribution. For that purpose, we formulate AWCP parameters tuning as a multi-objective problem and we propose an optimization tool which combines a non-dominated sorting genetic algorithm, version 2 (NSGA-II) [START_REF] Abdou | Using an evolutionary algorithm to optimize the broadcasting methods in mobile ad hoc networks[END_REF] and a network simulator ns-2 to find the suitable parameters of AWCP that optimize its QoS. ASAS uses vehicles' locations and directions as well as a slot reuse mechanism to reduce inter-cluster interference under different traffic load conditions without having to use expensive spectrum and complex mechanisms such as CDMA or FDMA.

Manuscript organization

The present chapter has introduced the context and the motivations of our thesis and has described our contributions. The rest of this manuscript is organized as follows.

Part I: State of the art

In Chapter 2, we provide an overview of the special features of VANETs.

We then give an insight into inter-vehicle communication standardization and projects that are being developed in the field. In chapter 3, we provide an overview of TDMA-based MAC protocols that have been proposed for VANETs and we present a topology-based classification of these protocols. We then give a qualitative comparison, and we discuss some open issues that need to be tackled in future studies. we use an approximation approach to find the optimal configuration of AWCP.

Chapter 7 describes two TDMA scheduling solutions. This first solution, which corresponds to Contribution 6, called CTMAC, aims at reducing the scheduling overhead as well as the access collision rate by using RSUs to schedule and maintain time slot assignment for the vehicles in their coverage area. The second one, called ASAS, is cluster-based in which one vehicle in each group is elected to assign time slots to the vehicles within its transmission range. This corresponds to Contribution 7.

In Chapter

Introduction

Vehicular Ad-Hoc Networks (VANETs) are deployed to make communication between vehicles possible using ad hoc wireless devices. Nowadays, these networks have become an emerging technology due to the variety of their applications in Intelligent Transportation Systems (ITS). By creating a vehicular network, each vehicle can exchange information to inform drivers in other vehicles about the current status of the traffic flow or the existence of a dangerous situation. They can also be used to improve traffic management conditions such as route optimization, flow congestion control and to provide on-board infotainment such as Internet access, the location of free parking places, video streaming sharing, etc.

In this chapter we explain more clearly the context of this thesis by giving an overview of the VANETs and their features. Then, we classify VANET applications according to their requirements and functions. After that, we give an insight into inter-vehicle communication standardization and projects that are being developed in the field. Finally, we give a short summary of different standardization activities

with their shortcomings at the MAC layer and then we conclude.

Vehicular networks

Recent advances in wireless communications and networks have given birth to a new type of mobile network known as a VANET to improve road safety and efficiency.

VANET technology uses wireless LAN 1 , ad hoc technology and moving cars as nodes to achieve intelligent inter-vehicle communications. VANETs are distinguished from other kinds of MANETs 2 by high node mobility with constrained movements, ample energy and computing power and hybrid network architectures. In the following, we detail their features and communication architectures as well as research and standardization activities in this field.

Definition and architectures

VANETs, which are made up of mobile nodes (vehicles), can be considered as a special case of MANETs. They are both characterized by the movement and self-organization of the nodes, but they also differ in some ways such as network infrastructure components and a highly dynamic topology.

General characteristics

The special characteristics of VANETs make MANET architectures and protocols (MAC, routing, etc.) unsuitable in the VANET context. In the following, we highlight some characteristics related to vehicular networks that should be taken into consideration to enable the implementation of highly efficient communication protocols for VANET networks.

• High mobility of nodes: Unlike typical ad hoc networks, the nodes in VANETs are characterized by high speed mobility (between 30 km/h and 50 km/h in a city environment, between 50 km/h and 80 km/h in a countryside environment, and between 90 km/h and 150 km/h in a highway environment).

However, as the variability of the cars' speed is greater in VANET networks, it is important to implement protocols that can dynamically adapt to frequent changes of topology due to the nodes' high mobility and their different speeds.

• Availability of Geographical position: Several geographic protocols in VANETs consider that each vehicle in the network must know its position through a positioning system incorporating digital maps. The GPS 6 Positioning System [6,7], is the most widely used system in vehicular networks as it can provide an accurate real time three-dimensional position (latitude, longitude and altitude), direction, velocity and precise time.

• Mobility model:

A mobility model is one of the most important factors used to evaluate protocol behaviors in vehicular networks. This model should reflect reality (traffic lights, crossroads, and traffic-jams) as accurately as possible. To define a suitable mobility model, we distinguish the following environments:

-Highway: Open environment that is characterized by a high speed with a variable density of vehicles depending on the time and the day of the week.

-City: Lower speed with a high density of cars at certain times.

-Countryside: Characterized by an average speed with a lower density of cars.

We note that the vehicles' movements in VANETs are to some extent predictable due to the fact that the vehicles' movements are constrained by the road topology as illustrated by Figure 2.2 . It is also possible to test the performance of VANET protocols in real testbeds without establishing mobility models, however to do so would require more work to obtain meaningful results.

• No energy constraint: Unlike many other MANET nodes where energy is a major constraint that must be taken into consideration, VANET nodes have ample energy and computing power (i.e. both storage and processing) [START_REF] Kumar | Mobile Agent as an Approach to Improve QoS in Vehicular Ad Hoc Network[END_REF].

• Different QoS requirements: There are three main types of services foreseen by VANETs: Real-time applications including services related to road safety, traffic management applications and user-oriented applications, i.e. infotainment. These applications vary significantly in their QoS 7 requirements.

Real-time applications require guaranteed access to the channel and have strict requirements regarding end-to-end delay and packet loss ratio. Infotainment applications have stringent requirements on transmission rates. Due to the wide variety of VANET applications, MAC protocols need to be able to support a wide range of QoS requirements.

We conclude that VANETs have special characteristics which make them different from MANETs and represent a challenge for the design of low-access delay, high-throughput, scalable and robust MAC protocols. However, we note that there are some characteristics that can help us to design and develop efficient MAC protocols such as the sufficiently high electric power and the limited degrees of freedom in the nodes' movement patterns [START_REF] Fiore | Vehicular Mobility Simulation for VANETs[END_REF].

VANETs applications

Initially, VANET networks were deployed to increase traffic safety and efficiency by reducing the risk of road accidents. Nowadays, these networks are used for a wide range of applications which can be divided into the following three categories: safety services, traffic management and user-oriented services. In the following, we will briefly discuss each type of application, using significant examples. • Comfort services: The main goal of these applications is to offer comfort and convenience to drivers and/or passengers, e.g. Internet connection, multimedia services, messaging, games, radio channels, etc. In fact, Internet access can be provided through V2I communications, therefore, business services will be fully available in vehicles [START_REF] Gramaglia | Seamless internet 3G and opportunistic WLAN vehicular connectivity[END_REF]. Moreover, file sharing and video streaming services can be provided through V2V communications [START_REF] Guo | An Adaptive Collision-Free MAC Protocol Based on TDMA for Inter-Vehicular Communication[END_REF], making long trips more comfortable and enjoyable. Because this category of applications has different QoS requirements in terms of bandwidth and delay, guaranteeing real-time and reliable communications for delay-sensitive applications without impacting throughput-sensitive applications can be an extremely challenging task. In the next section, we review recent VANET standardization efforts as well as some research projects in the field of VANETs in Europe and beyond.

VANET standardization and research projects

VANETs have been designed to improve road safety, and traffic efficiency and to provide on board infotainment such as Internet access. Therefore, VANETs have attracted a great deal of attention in research, standardization and development.

Standardization

In this section, we present the recent standardization efforts and related activities in the field of VANETs.

• Dedicated Short Range Communication: Dedicated Short-Range Communication (DSRC) [START_REF] Shulman | Safety Communications in the United States[END_REF] was initially coined in USA [START_REF] Shulman | Safety Communications in the United States[END_REF] by the United States FCC shows a comparison between different regional standards for DSRC [START_REF] Kudoh | DSRC standards for multiple applications[END_REF] in Japan (ARIB 9 ), Europe (CEN 10 ) and in North America (ASTM 11 ). More detailed information on regional standards for DSRC is available in [START_REF] Bilstrup | Vehicular communication standards-DSRC[END_REF][START_REF] Yin | Performance evaluation of safety applications over DSRC vehicular ad hoc networks[END_REF][START_REF] Li | An overview of the DSRC/WAVE technology[END_REF]. Moreover the IEEE 802.11p [START_REF]IEEE standard for information technology-Telecommunications and information exchange between systems-local and metropolitan area networksspecific requirements part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) and physical layer (PHY) specifications amendment 6: Wireless access in vehicular environments[END_REF] standard was adopted as the MAC and PHY 12 specifications for the lower-layer DSRC standard.

Related projects

Several European, American and Japanese research projects are currently dealing with vehicular communications. FleetNet [43] is a European project which aims to propose and develop several solutions to ensure the safety and comfort of passengers.

PReVENT [START_REF]PReVENTive and Active Safety Applications[END_REF] is a European project which was initiated to contribute to road safety by developing applications and preventive road safety technologies. SAFESPOT [START_REF]SafeSpot (Cooperative vehicles and road infrastructure for road safety[END_REF] is an integrated research project co-funded by the European Commission Information Society Technologies, which aims to create dynamic cooperative networks where the vehicles and the road infrastructure communicate to share information gathered on board and at the roadside to enhance the drivers' perception of the vehicle's surroundings. C2C-CC (Car2Car Communication Consortium) is a non-profit organization [START_REF]CAR 2 CAR Communication Consortium[END_REF] supported Figure 2.8 shows some projects that have been funded by the European Union, the governments of the USA and Japan. These include COMeSafety [START_REF][END_REF], GeoNET [START_REF]Geo-addressing and Geo-routing for Vehicular Communications[END_REF],

SEVECOM [START_REF] Leinmuller | Sevecom -secure vehicle communication[END_REF], CarTALK [START_REF] Reichardt | Cartalk 2000: safe and comfortable driving based upon inter-vehicle communication[END_REF], coopers [START_REF]COOPERS project[END_REF], euroFOT [START_REF]EuroFOT EU project[END_REF], PRE-DRIVEC2X [START_REF]PRE-DRIVEC2X EU project[END_REF] and evita [START_REF]E-safety Vehicle Intrusion Protected Applications[END_REF] which are sponsored by the European Union, Advanced Highway Technologies in the USA and the Advanced Safety Vehicle Program (ASV) sponsored by the government of Japan which are presented in [START_REF] Zeadally | Vehicular Ad Hoc Networks (VANETs): Status, Results, and Challenges[END_REF].

Summary and discussion

Several inter-vehicle communication standardizations and projects have been established in Europe and beyond [START_REF] Zeadally | Vehicular Ad Hoc Networks (VANETs): Status, Results, and Challenges[END_REF]

Conclusion

Research in VANETs has attracted increasing interest over recent years due to its ability to improve road safety by using inter-vehicle communication. However, a challenging problem when designing communication protocols in VANETs is coping with high vehicle mobility, which causes frequent changes in the network topology and leads to frequent breaks in communication. In this chapter, we have described features of VANETs and their different types of vehicular communications. We classified vehicular applications into three main categories based on their improvement of safety on the road and their requirements in terms of delays and throughput. Moreover, we presented research and standardization activities in the field and we identified their shortcomings focusing particularly on the QoS at the MAC layer.

The next chapter will deal with MAC protocols in VANETs paying particular attention on those that are based on the Time Division Multiple Access (TDMA)

technique. We will explore some general MAC protocol design issues in VANETs, and we will set out the reasons for using collision-free MAC in this type of network.

Moreover, we will classify the recent TDMA-based MAC protocols into three different categories according to their network topologies. For each category, we will identify and describe TDMA problems that can arise and we will list some related protocols found in the literature.

Chapter 3 have been proposed for VANETs in an attempt to ensure that all the vehicles have enough time to send safety messages without collisions and to reduce the end-to-end delay and the packet loss ratio. In this chapter, we identify the reasons for using the collision-free MAC paradigm in VANETs. We then propose a topology-based classification and we provide an overview of TDMA-based MAC protocols that have been proposed for VANETs. We focus on the characteristics of these protocols, as well as on their benefits and limitations. Finally, we give a qualitative comparison, and we discuss some open issues that need to be tackled in future studies in order to improve the performance of TDMA-based MAC protocols for V2V communications.

Medium access control in VANETs

VANETs are designed to provide several services to enhance road safety. This objective can essentially be achieved by the use of efficient safety applications which should be able to wirelessly broadcast warning messages between neighboring vehicles in order to rapidly inform drivers about a dangerous situation such as an accident. To insure their efficiency, safety applications require reliable periodic data dissemination with low latency. MAC protocols in VANETs play a primary role in providing efficient delivery. Medium access protocols are situated in the Data Link Layer, which is itself not only responsible for ensuring fair channel access, but also for providing multi-channel operation and error control.

Classification of MAC protocols

Several MAC protocols have been designed for inter-vehicle communications. They can be classified into three categories depending on the channel access methods used, namely the contention-based medium access method such as IEEE 802.11p [START_REF]IEEE standard for information technology-Telecommunications and information exchange between systems-local and metropolitan area networksspecific requirements part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) and physical layer (PHY) specifications amendment 6: Wireless access in vehicular environments[END_REF], and the contention-free medium access method. The third category is a hybrid of the two previous methods. Figure 3 Contention-based and contention-free MAC protocols each have their own specific tools to reduce the packet loss ratio. In recent years, there have been several hybrid proposals, which try to combine these two mechanisms into a single architecture to enhance their capabilities to provide a high QoS and reduce the collision rate. All these protocols divide the access channel into two periods (random access period and contention-free access period), in which the first period is used by the nodes to create a channel access schedule to be used in the second period. In this chapter, we will assess and highlight MAC protocols using TDMA. In order to be able to implement time-slotted MAC protocols, clock synchronization between the vehicles in the network is an important requirement. This task can be made possible by using a GPS system in each vehicle.

VANET MAC protocol design issues

Providing efficient MAC protocols in a VANET raises several key technical challenges:

• High speed: Due to the high levels of speed, many vehicles can join a group of vehicles at any time. However, contention-free MAC protocols typically have a fixed parameter which specifies how many nodes can access the channel, whereas contention-less MAC protocols do not work well with high loads.

• Frequently changing network topology: The open and important question is how MAC protocols can seamlessly adapt to frequent changes in topology.

The MAC protocols must also be able to operate in highway and urban scenarios.

• No central coordination: Due to the lack of infrastructure in VANETs, there is generally no centralized coordinator. Therefore, the MAC protocol must take this constraint into consideration and the control must be distributed among the vehicles. In order to ensure a fair channel utilization without access collisions, neighboring vehicles must exchange control messages. Therefore, the MAC protocol must make sure that this overhead does not consume too much precious bandwidth.

• Scalability: MAC protocols should be designed to support an efficient channel utilization mechanism under different traffic load conditions (large and/or dense VANETs).

• Broadcast support:

The open question is how to support an efficient broadcast service in MAC protocols in order to announce some information with a regional scope.

• The hidden and exposed node problems: these two problems are the result of the broadcast nature of VANETs, since it is not possible to use RTS/CTS messages to prevent collisions for broadcasted messages [START_REF] So | Multi-Channel MAC for Ad Hoc Networks: Handling Multi-Channel Hidden Terminals Using A Single Transceiver[END_REF]. The hidden node problem occurs when two vehicles that are not within transmission range of each other perform a simultaneous transmission to a vehicle that is within the transmission range of each of them. On the other hand, the exposed node problem occurs when a vehicle is prevented from sending packets to other vehicles due to a neighboring transmitter.

• Different QoS requirements: Due to different QoS requirements in VANETs, MAC protocols should provide transmission services without collisions and with a bounded delay for high priority safety applications while, at the same time, ensuring a high throughput for infotainment applications. When safety messages are broadcasted, they should be given a higher access priority than other data messages.

• Time synchronization: In order to be able to implement time-slotted MAC protocols, clock synchronization between vehicles in VANETs is an important issue. Most contention-free TDMA-based MAC protocols assume that all the vehicles can be synchronized at the start of each TDMA frame by using the 1PPS signal provided by the GPS2 in each vehicle. It is generally assumed that each vehicle is equipped with a positioning system, which is not guaranteed to operate correctly in all the scenarios, for example when there are tunnels, high buildings, etc.

• Multichannel operation: Typically, a node in an ad hoc network has a transceiver allowing it to listen or transmit on one channel at a time. To ensure maximum connectivity, all the nodes tune their transceivers to the same channel. However, as the node density increases the collision rate increases.

To reduce collisions, the neighboring nodes can potentially transmit on different channels simultaneously. Therefore, the MAC protocols should implement a dynamic multichannel operation algorithm which is able to switch between different channels quickly to increase network throughput without a central coordinator. Although the FCC [16] has established the DSRC service defined on the frequency band of 5.9 GHz divided into seven channels, there are many MAC protocols which are limited to using a single channel. It is thus imperative to expand these protocols to allow them to use all seven channels in order to make them more scalable.

• Adjacent Channel Interference: The parallel usage of the Control CHannel (CCH) and the Service CHannels (SCHs) in order to increase the transmission rate and decrease the packet loss ratio impacts communication by generating interference signals. This problem is known as Adjacent Channel Interference (ACI) which has been evaluated for VANETs in [START_REF] Lasowski | Evaluation of Adjacent Channel Interference in Single Radio Vehicular Ad-Hoc Networks[END_REF].

Performance metrics

Due to the wide range of MAC protocols that have been proposed for VANETs, it is important to understand the metrics that will be used in the following sections to compare these MAC protocols. Naturally these metrics are delay, packet loss, throughput, fairness, stability and support for real-time and for user-oriented applications.

• Access Delay: The access delay is defined as an average time from the moment when a vehicle starts trying to send a packet until the beginning of its successful transmission [START_REF] Yeh | Simulation of local computer networks -a case study[END_REF]. It is also defined as the average time spent by a frame in the MAC queue. However, the access delay depends not only on the MAC protocol but also on the traffic rate produced by the other vehicles sharing the same channel. It is necessary to know which MAC protocols can support safety and real-time applications.

• Packet loss: Packet loss occurs when one control/data packet fails to be transmitted successfully. There are a variety of reasons that lead to packet loss including exposed/hidden nodes, collisions, low power signal, etc. The packet loss ratio can be defined as the ratio of the number of lost packets to the total number of packets sent.

• Throughput: Throughput can be defined as the fraction of the channel capacity used for data transmission. The goal of an efficient MAC protocol in a VANET is to maximize the throughput for user-oriented applications while minimizing the access delay for safety applications.

• Fairness: A MAC protocol is fair if all the vehicles have equal access to the medium during a fixed time interval. However fairness can also be defined as the ability to distribute bandwidth according to traffic priority when priorities are supported.

• Stability: Generally, VANETs become unstable when the vehicles' movements are high. Thus a MAC protocol is considered to be stable if it is able to operate under different vehicular traffic conditions.

• Support for safety Applications: In VANETs, each vehicle can exchange information to inform other vehicles about dangerous situations such as an accident or an event-triggered warning. These types of data have strict requirements in terms of access delay and transmission collision rates. This increases the need for an efficient MAC protocol.

• Support for user-oriented Applications: With the convergence of multimedia applications in VANETs (e.g., video/audio) and data (e.g., e-maps, road/vehicle traffic/weather information), it is now necessary for MAC protocols to support multimedia and data traffic. Since multimedia applications require lower latency than data applications, the MAC protocols should satisfy these latency requirements. Two methods can be used to process packets from various applications based on their latency constraints: access priority and scheduling. An access priority scheme provides differentiated services by allowing certain vehicles to access the medium with a higher probability than others, while scheduling can guarantee the required delay (e.g. TDMA-based MAC protocols).

TDMA-based MAC protocols

The MAC protocols based on the TDMA method have received an increasing amount of attention from the networking research community. This category of protocols has been used to control channel access in many kinds of wireless networks, e.g. the cellular network (GSM3 , 2G, 3G and 4G [START_REF] Pereira | Evolution of Mobile Communications: from 1G to 4G[END_REF]) and WSN 4 [START_REF] Ergen | TDMA scheduling algorithms for wireless sensor networks[END_REF].

Benefits of TDMA

The TDMA principle consists of allocating the bandwidth to all the vehicles by dividing the time into different frames and each frame is divided into several time slots (see Figure 3.2). In every frame, each vehicle that has access to one or more dedicated time slots can send data during this slot but it can only receive during the time slots reserved for other vehicles. This provides a big advantage compared to the IEEE 802.11p standard. The benefits of using TDMA MAC protocols are considerable and can be summarized as follows:

• Can provide equal access to the channel for all vehicle nodes.

• Efficient channel utilization without collisions.

• High reliability of communications.

• Deterministic access time even with a high traffic load.

• QoS for real-time applications.

Spatial reuse TDMA constraints

We assume the following notations:

• N cch (x): The set of one-hop neighbors5 of vehicle x on the control channel CCH.

• N 2 cch (x): The set of two-hop neighbors6 of vehicle x on the control channel CCH.

N 2 cch (x) = N cch (x) {N cch (y), ∀y ∈ N cch (x)} • N 3 sch i (x):
The set of three-hop neighbors of vehicle x on the service channel SCH number i, with i ≤ 6. This set contains the 1-hop, 2-hop and 3-hop neighbors of vehicle x.

Spatial reuse TDMA constraints on CCH

The control channel CCH is used for high priority safety applications and for topology management. The vehicular communications on the CCH channel are based on broadcast mode in which no acknowledgments (ACKs) are used. Thus, a time slot k is successfully acquired by vehicle x without interfering with another vehicle (Hidden terminal problem) if and only if:

∀y ∈ N 2 cch (x), T S(y) = k.
Where T S(x) is the time slot acquired by vehicle x.

Spatial reuse TDMA constraints on SCHs

The service channels are dedicated to data transmission for different services. The vehicular communication in the SCH channels is based on unicast mode in which a vehicle is allowed to transmit an immediate acknowledgment to confirm the reception of data. In this case, as shown in Figure 3.3, the two-hop neighbor set is not sufficient to avoid interference: Vehicle D acquired the same time slot used by A and the data message sent by A collides with the ACK message sent by C to vehicle D. Hence the three-hop neighbor set is needed to avoid collisions in the service channels. Thus, a time slot k is successfully acquired by vehicle x without interfering with another vehicle on the service channel i, if and only if:

∀y ∈ N 3 sch i (x), T S(y) = k.
Due to the fast movement of the vehicles, the network topology in VANETs is highly dynamic and is continuously changing. Therefore, ensuring that the two spatial reuse constraints in the CCH and the SCHs are satisfied at any given moment is not a simple task.

Classification of TDMA-based MAC protocols

VANETs usually include nodes that are moving fast and at different speeds, so the topology can change frequently. Therefore an efficient MAC protocol must be able to adapt to frequent topology changes and must assume as general a topology as possible, for instance the RSUs can access the channel via the same MAC protocol as the vehicles. A VANET topology can be described in terms of a hierarchy. In a centralized case, a base station (e.g., an RSU) controls or manages all the vehicles in the network, whereas in a clustered topology one vehicle in each cluster is elected to act as a local control entity. In a fully distributed VANET, the centralized control notion is absent and the nodes need to self-organize. We make a further and new classification of TDMA-based MAC protocols according to their topology. These protocols consider a wide spectrum of topologies based on the communication architectures (e.g. V2V or V2I) or applications for which they are designed. The majority of the MAC protocols considered in [START_REF] Park | Survey of MAC Protocols for Vehicular Ad Hoc Networks[END_REF][START_REF] Kakarla | A Survey and Qualitative Analysis of Multi-channel MAC Protocols for VANET[END_REF][START_REF] Booysena | Survey of media access control protocols for vehicular ad hoc networks[END_REF][START_REF] Menouar | A survey and qualitative analysis of MAC protocols for vehicular ad hoc networks[END_REF] have a common fully distributed network topology. Thus in our classification, the topology for which a MAC protocol was developed is considered to be another key design element in a VANET. This factor is absent from the previous survey papers [START_REF] Park | Survey of MAC Protocols for Vehicular Ad Hoc Networks[END_REF][START_REF] Kakarla | A Survey and Qualitative Analysis of Multi-channel MAC Protocols for VANET[END_REF][START_REF] Booysena | Survey of media access control protocols for vehicular ad hoc networks[END_REF][START_REF] Menouar | A survey and qualitative analysis of MAC protocols for vehicular ad hoc networks[END_REF]. In order to categorize the protocols, in this chapter we propose the three following classes:

• Protocols operating on a fully distributed VANET: These protocols coordinate channel access in a distributed way. They assume that each vehicle only needs to communicate with its one-hop neighbors in order to access the channel.

• Protocols operating on a cluster-based topology: This category of protocols assumes that one vehicle in each group is elected to act as a local channel access coordinator.

• Protocols operating on a centralized topology: These protocols assume that there are central points (RSUs) which are used to coordinate channel access for the vehicles in their coverage area.

Each class of protocols can also be further categorized according to different properties. One possible characterization could be done based on:

-Pure TDMA vs. hybrid solutions In order to make the implementation of a time-multiplexed protocol more efficient in a distributed network topology, there are some issues that must be addressed. In this section, we identify the TDMA problems that may occur in a fully distributed VANET due to the high mobility of the nodes, and we survey the main TDV protocols that have been proposed in the literature.

-

TDMA problem statement in a fully-distributed VANET

When a distributed scheme is used to allocate a time slot, two types of collision can occur [START_REF] Borgonovo | a Reliable R-ALOHA broadcast channel for ad-hoc inter-vehicle communication networks[END_REF]: access collision between vehicles trying to access the same available time slots, and merging collisions between vehicles using the same time slots.

As shown in Figure 3.10, an access collision problem [START_REF] Shih | Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks[END_REF] occurs when two or more vehicles within the same two-hop neighborhood set attempt to access the same available time slot. This problem is likely to happen when a distributed scheme is used.

TDV protocols

In the literature, various distributed TDMA-based MAC protocols have been proposed for VANETs. Each of them focuses on certain issues in specific mobility scenarios.

P1) Space-Orthogonal Frequency-Time Medium Access Control (SOFT MAC)

Abu-Rgheff et al. [START_REF] Abu-Rgheff | SOFTMAC: Spaceorthogonal frequency-time medium access control for VANET[END_REF] propose a MAC protocol for VANET networks based on a node wishing to reserve a slot during the RS period checks the status of the slots in the current frame and initiates a reservation request. The DMMAC protocol [START_REF] Lu | DMMAC : A dedicated multi-channel MAC protocol design for VANET with adaptive broadcasting[END_REF] is an alternative to the IEEE 802.11p standard. DM-MAC is designed for VANETs to support an adaptive broadcasting mechanism which provides collision-free and delay-bounded transmissions for safety applications under various traffic conditions. As shown in Figure 3.7, the DMMAC architecture is similar to IEEE 802.11p with the difference that, the CCH Interval is divided into an Adaptive Broadcast Frame (ABF) and a Contention-based Reservation Period (CRP). The ABF period consists of time slots, and each time slot is dynamically reserved by a vehicle as its Basic Channel (BCH) for collision-free delivery of safety messages or other control messages. The CRP uses CSMA/CA as its channel access scheme.

During the CRP, vehicles negotiate and reserve the resources on SCHs for non-safety applications. DMMAC implements a dynamic TDMA mechanism for BCH reservation based on the distributed access technique R-ALOHA (Reliable R-ALOHA [START_REF] Borgonovo | a Reliable R-ALOHA broadcast channel for ad-hoc inter-vehicle communication networks[END_REF]).

The length of the ABF frame is not uniform over the entire network. Each vehicle dynamically adjusts its ABF length according to its neighbors.

P3) Vehicular Ad Hoc Networks MAC (VeMAC)

VeMAC [START_REF] Zhuang | VeMAC: A novel multichannel MAC protocol for vehicular ad hoc networks[END_REF][START_REF] Omar | Evaluation of VeMAC for V2V and V2R Communications under Unbalanced Vehicle Traffic[END_REF][START_REF] Omar | VeMAC: A TDMA-Based MAC Protocol for Reliable Broadcast in VANETs[END_REF][START_REF] Omar | On Multihop Communications For In-Vehicle Internet Access Based On a TDMA MAC Protocol[END_REF] is a contention-free multi-channel MAC protocol proposed for VANETs. In contrast to DMMAC and SOFTMAC, VeMAC is completely contentionfree. This protocol supports efficient one-hop and multi-hop broadcast services on the control channel, which provides smaller rates of access collisions and merging collisions caused by node mobility. These broadcast services are presented in [START_REF] Borgonovo | ADHOC MAC: new MAC architecture for ad hoc networks providing efficient and reliable point-to-point and broadcast services[END_REF] for ADHOC MAC (see Section 3.5.2). In VeMAC, the merging collision rate is reduced by assigning disjoint sets of time slots to vehicles moving in opposite directions (Lef t, Right)

and to RSUs, see Figure 3.8.

In VeMAC, each node has two transceivers, the first one is always tuned to the control channel while the other can be tuned to any service channel. Synchronization between nodes is performed using the 1PPS signal provided by the GPS in each In contrast to the other protocols, VeMAC can make use of the seven DSRC channels, it supports the same broadcast service on the control channel and on the service channels, and decreases the rates of merging and access collisions. Although communications over the service channels are overhead-free, the overhead of the VeMAC protocol on the control channel is considerable due to the size of the control frame transmitted on the CCH. Moreover, in VANETs, particularly in a highway environ-ment, the number of vehicles in each direction is not equal. Thus, the size of the slots sets should be adjusted according to vehicle density. In addition, the merging collision problem can occur when vehicle density is high. Indeed, if a moving vehicle detects that it cannot access a time slot from the set of slots reserved for vehicles moving in its direction, then it will attempt to access any available time slot reserved for vehicles moving in the opposite direction.

P4) Adaptive TDMA Slot Assignment (ATSA)

An efficient MAC approach called ATSA [START_REF] Weidong | Adaptive TDMA slot assignment protocol for vehicular ad-hoc networks[END_REF][START_REF] Yang | TDMA-Based Control Channel Access for IEEE 802.11p in VANETs[END_REF] is an improvement of the previously proposed MAC protocol named the Decentralized Adaptive TDMA Scheduling

Strategy DATS [START_REF] Ke | A Decentralized Adaptive TDMA Scheduling Strategy for VANET[END_REF]. ATSA enhances the VeMAC protocol when the densities of vehicles moving in opposite directions are not equal (unbalanced traffic). Like VeMAC, ATSA divides the frame into two sets of time slots Lef t and Right. However in ATSA, when a vehicle accesses the network, it chooses a frame length and competes for one of the time slots available for its direction. To solve merging collisions under unbalanced traffic conditions, the frame length is dynamically doubled or shortened based on the binary tree algorithm, and the ratio of two slot sets is adjusted according to algorithm 1 as stated below. -S x (t): The frame length of vehicle x, namely the number of time slots of each frame.

-N x (t): The set of two-hop neighbors of vehicle x.

Algorithm 1 Adapting frame length algorithm

1. if (N x (t)/S x (t) > U max ) then 1.1. Double the frame length; 2. end if 3. else if (N x (t)/S x (t) < U min ) then 3.1.
divide the frame length by two;

end if

Although the results show that the ATSA protocol can reduce the number of collisions and have the minimal time delay and maximum channel utilization compared with the ADHOC and VeMAC protocols, a poor choice of U max and U min gives poor results, so it is essential to determine the optimal values of U max and U min in order to adapt the frame appropriately.

P5) Near Collision Free Reservation based MAC (CFR MAC)

Zou et al. in [START_REF] Zou | A near collision free reservation based MAC protocol for VANETs[END_REF] P6) CSMA and Self-Organizing TDMA MAC (CS-TDMA)

Zhang et al. in [START_REF] Zhang | A Scalable CSMA and Self-Organizing TDMA MAC for IEEE 802.11 p/1609[END_REF] have proposed a novel multichannel MAC protocol called CS-TDMA combining CSMA with TDMA and SDMA to improve the broadcast performance in VANETs. CS-TDMA is a multichannel version of the SOFTMAC protocol and it implements the same MAC frame structure as SOFTMAC. Moreover, CS-TDMA differs from all the other multichannel protocols in that the ratio between the CCH and SCH intervals is dynamically adjusted according to traffic density. When the density of vehicles is low, the CCH interval is reduced to guarantee a high throughput for non-safety applications. When the traffic density is high, the CCH duration is maximized to guarantee a bounded transmission delay for real-time safety applications. CS-TDMA achieves a significant improvement in DSRC channels utilization, but the performance evaluation of the CS-TDMA protocol has been limited only to a medium density of vehicles (80 veh/km). Moreover, Access collision and merging collision problems are not studied in [START_REF] Zhang | A Scalable CSMA and Self-Organizing TDMA MAC for IEEE 802.11 p/1609[END_REF].

P7) Hybrid Efficient and Reliable MAC (HER-MAC) for Vehicular

Ad hoc Networks

Dang et al. [START_REF] Dang | HER-MAC: A Hybrid Efficient and Reliable MAC for Vehicular Ad Hoc Networks[END_REF] developed and evaluated a Hybrid Efficient and Reliable MAC for VANETs, called HER-MAC, which is similar to the DMMAC protocol. The goal of this research work is to develop a contention-free Multichannel MAC protocol with an adaptive broadcasting algorithm, which improves data transfer rates for non-safety applications while guaranteeing timely delivery for safety applications in highway scenarios. The architecture and the operation of HER-MAC are similar to DMMAC, differing in that the CRP period is used by a vehicle to reserve a time slot during the ABF period or to exchange a 3-way WSA/RFS (WAVE Service Announcement/Request For Service) handshake. In fact, if a vehicle wishes to exchange non-safety messages, it has to broadcast the WSA during the CRP period to reserve a time slot on a certain SCH. Then, when a vehicle decides to use the service, it sends the RFS to the service provider which will confirm it with an ACK message.

On receiving the ACK packet, the vehicles can start exchanging non-safety messages without any risk of collisions with messages from their neighboring vehicles. However, a high level of coordination and overhead are required by the HER-MAC protocol, since each vehicle has to periodically broadcast a hello message containing information about the status of the time slots of its one-hop neighbors and to initiate the 3-way WSA/RFS handshake in order to be able to exchange safety and non-safety messages.

P8) Self-organizing Time Division Multiple Access (STDMA)

STDMA [START_REF] Bilstrup | On the Ability of the 802.11p MAC Method and STDMA to Support Real-Time Vehicle-to-Vehicle Communication[END_REF][START_REF] Yu | STDMA for Vehicle-to-Vehicle Communication in A Highway Scenario[END_REF] was developed for real-time communications. The method is currently employed in automatic identification systems [START_REF]Technical characteristics for universal shipborne automatic identification system using time division multiple access in the VHF maritime mobile band[END_REF]. STDMA is a decentralized scheme where the network members themselves are responsible for sharing the communication channel, and due to the decentralized network topology, synchronization between the nodes is done through a global navigation satellite system, GPS.

P9) Self-Organizing MAC Protocol for DSRC based Vehicular Ad Hoc Networks (VeSOMAC)

VeSOMAC [START_REF] Yu | A Self Reorganizing MAC Protocol for Inter-vehicle Data Transfer Applications in Vehicular Ad Hoc Networks[END_REF] uses an in-band control mechanism to exchange TDMA slot information during distributed MAC scheduling. The aim of this work is to develop a contention-free MAC protocol that can achieve fast TDMA slot reconfiguration without relying on roadside infrastructure or virtual schedulers such as leader vehicles, which can deliver improved throughput for such applications in highway scenarios.

VeSOMAC can operate in both synchronous and asynchronous modes. In the synchronous mode, all the vehicles are assumed to be time-synchronized by using GPS where they share the same frame and slot boundaries. In the asynchronous mode, each vehicle maintains its own frame boundaries.

Summary of TDV protocols

Nine distributed MAC protocols in fully distributed VANETs have been presented. Table 3.2 compares the performance and the features of these protocols. The features and the performance results are taken from the respective references indicated in Table 3.2.

In this section, we discuss some of the properties presented in Table 3.2. Several distributed protocols [START_REF] Abu-Rgheff | SOFTMAC: Spaceorthogonal frequency-time medium access control for VANET[END_REF][START_REF] Weidong | Adaptive TDMA slot assignment protocol for vehicular ad-hoc networks[END_REF][START_REF] Zou | A near collision free reservation based MAC protocol for VANETs[END_REF][START_REF] Bilstrup | On the Ability of the 802.11p MAC Method and STDMA to Support Real-Time Vehicle-to-Vehicle Communication[END_REF] consider the medium as a single channel in which all the vehicles in the network share the same medium for all their control, safety and data transmissions. There are two possible reasons why these protocols have been proposed for single channel operation. Firstly because multichannel operation has not yet been developed, and secondly because the authors developed these protocols for a specific class of applications. Since SOFT MAC is a single channel MAC protocol and it has been developed for multimedia and real-time applications, the probability of collisions occurring increases. Therefore, some protocols such as VeMAC, DMMAC, HER-MAC and CS-TDMA separate control and data transmission by dividing the medium into multiple data channels and one control channel (the seven DSRC channels). Thus, multi-channel protocols, which combine two or more MAC approaches such as TDMA, CDMA, FDMA, SDMA for channel separation, generally provide collision-free and delay-bounded transmissions for safety applications while guaranteeing high throughput for non-safety applications, which is not the case for single channel protocols.

VeMAC, CFR MAC and ATSA resolve the merging collision problem by assigning time slots to vehicles according to their directions. Moreover VeMAC decreases the probability of access collisions and merging collisions compared to other protocols such as DMMAC but does not completely avoid this type of collision. As a result, VeMAC operates well and achieves improved performance under high traffic load and for larger networks, as well as in high mobility situations. However access and merging collisions are possible for all the other protocols. Also STDMA and DMMAC perform well under high network loads and under high mobility conditions. Unlike VeSOMAC and SOFT MAC, DMMAC can operate well in dense networks because these protocols contain an adaptive frame length mechanism according to vehicle density. CFR MAC, ATSA, SOFT MAC and STDMA can be extended to support multi-channel operations to achieve higher throughput for non-safety applications as well as to reduce transmission collisions in highly loaded networks. In addition, a fixed frame length in VeSOMAC and SOFTMAC can either lead to inefficient channel utilization or a degradation in network performance when vehicle density increases.

There are three groups of protocols, the first one is suited only to real-time applications (e.g. STDMA,CFR MAC, DMMAC and ATSA), the second is only suited to multimedia applications (e.g. VeSOMAC) and the last group is suited to both real-time and multimedia applications (e.g. SOFTMAC, VeMAC, HER-MAC and CS-TDMA). Moreover, two methods can be used to support a wide range of applications with different requirements: access priorities (e.g. SOFTMAC) and channel separation (e.g. VeMAC). The first method is generally used for single channel protocols in which the bandwidth is distributed according to traffic priority while giving a high access priority to real-time messages. The second method consists of dividing the medium into multiple channels (the seven DSRC channels) which requires an efficient channel switching mechanism that should ensure bounded-delays for realtime applications while guaranteeing a high throughput for multimedia applications.

CS-TDMA is more adaptive and reliable in terms of transmission delay and network throughput than VeMAC because it implements an adaptive channel switching mech-anism which dynamically adjusts the time ratio between the CCH and SCHs intervals according to traffic density.

3.5 TDMA-based mac protocols in a cluster-based topology (TCBT)

Cluster-based TDMA MAC protocols have attracted attention for VANETs because they avoid access collisions due to concurrent access to the same available time slot, and limit channel contention as the number of vehicles increases. They also provide fair channel access within the cluster and effective topology control. In a clusterbased TDMA, one vehicle is elected to serve as the local network coordinator for each group. The elected cluster head is responsible for assigning time slots to its cluster members. Nevertheless, the main challenge in cluster-based TDMAs is the overhead generated to elect the cluster head and to maintain the cluster members in a highly dynamic topology.

TDMA problem statement in a clustered topology

When a cluster-based TDMA scheme is used to schedule and manage the time slots, an inter-cluster interference problem can occur [START_REF] Wu | Reducing Inter-cluster TDMA Interference by Adaptive MAC Allocation in Sensor Network[END_REF]. The inter-cluster collision problem occurs when a time slot is used by two neighboring vehicles belonging to neighboring clusters. Figure 3.10 shows an example of an inter-cluster interference situation when vehicle B in cluster 2 and vehicle D in cluster 1 are using the same time slot. Since B and D are within transmission range of vehicle E but not within transmission range of each other, a collision will occur at vehicle E.

TCBT protocols

Several cluster-based MAC protocols have been proposed in the literature for intervehicle communications in order to provide an efficient and fair channel utilization while minimizing intra-cluster and inter-cluster transmission collisions.

P1) AD HOC Medium Access Control (ADHOC MAC)

ADHOC MAC [START_REF] Borgonovo | ADHOC MAC: new MAC architecture for ad hoc networks providing efficient and reliable point-to-point and broadcast services[END_REF] is a MAC architecture where the vehicles are grouped into a set of clusters with no cluster head; each cluster contains a restricted number of vehicles that are one-hop away. ADHOC MAC provides an efficient broadcast [90]

[75]

[76]

[80]

[83]

[87]

[86] neighborhood. Thus, each vehicle broadcasts an additional frame to its two-hop neighborhood called the Frame Information (FI) during its BCH which is a vector with N entries specifying the status of each of the preceding N slots, as observed by the vehicle itself. ADHOC MAC also implements an optimal multi-hop broadcast service and parallel transmissions that uses a minimum set of relaying terminals able to cover the whole network.

In ADHOC MAC, each vehicle can access the channel if and only if N is larger than the maximum number of terminals M in any two-hop neighborhood. The simulation results show that if M = N , the acquisition of an available slot by each vehicle is more contentious and takes a long time.

P2) Cluster Based Medium Access Control Protocol (CBMAC)

A cluster based MAC protocol (CBMAC) has been proposed by Günter et al. [START_REF] Unter | Cluster-based medium access scheme for vanets[END_REF], in which the cluster head for each cluster is responsible for assigning bandwidth to the members of its cluster. The main goals of this approach are to reduce the hidden node problem and provide a fair medium access. In CBMAC, the access time is divided into The first slot is always used by the cluster head CH to periodically broadcast a HELLO message (CH-HELLO) to its cluster members in order to indicate the start of a frame, while the second slot is used by the CH to announce a control message which is a vector specifying the status of each slot and the identifier of the vehicle that is allowed to transmit in that slot. During the data link phase, each vehicle can use its slot to send data messages. In this phase the vehicles can also send their information to any one-hop neighbor. Finally, during the random access phase, when a vehicle needs to access the network, it sends a reservation request for a periodic time slot to the cluster head CH. As shown in Figure 3.11, the length of this phase is not uniform and depends on the number of slots which have been reserved for the data link phase. Each cluster head can dynamically adjust the length of the random access phase according to the number of its cluster members. However, in order to avoid collisions during the random access phase and guarantee the stability of the protocol, the authors propose a minimum length value which is fixed to 10% of the frame. In order to reduce inter-cluster interference, CBMAC contains a spatial reuse algorithm in which the neighboring cluster heads exchange their super-frame structures via gateway vehicles to determine which vehicles can use the same channel in the same time slots.

The MAC protocol proposed by Günter et al. has some serious drawbacks: The spatial reuse concept is not clear and this protocol was only evaluated for V2V communications with a single hop and does not cover communication between vehicles and RSUs. In addition, the merging collision problem is not handled, which could make CBMAC unsuitable for scenarios in which the vehicles are moving in opposite directions.

P3) Clustering-Based Multichannel MAC (CBMMAC)

Unlike ADHOC MAC and CBMAC, this protocol [START_REF] Su | Clustering-based multichannel MAC protocols for QoS provisionings over vehicular ad hoc networks[END_REF][START_REF] Su | Cluster-based multi-channel communications protocols in vehicle ad hoc networks[END_REF] channels. In the paper, the authors assume that each vehicle is equipped with two transceivers. CBMMAC deploys three main protocols: cluster configuration, intracluster and inter-cluster coordination communication.

The first protocol organizes vehicles moving in the same direction into clusters where one vehicle is elected as a coordinator in each cluster. At any given time each vehicle can act as a cluster-head, quasi-cluster-head if the vehicle is neither a cluster head nor a cluster member, or quasi-cluster-member which is a vehicle that temporarily loses contact with its cluster head.

The Intra-cluster Coordination and Communication Protocol is based on a MMAC protocol [START_REF] So | Multi-channel MAC for ad hoc networks: Handling multichannel hidden terminals using a single transceiver[END_REF]. First, each cluster head creates and manages the TDMA slot reservation schedule on the CRC channel. Second, each cluster member can use its assigned time slot to send safety messages and data channel reservation requests to its cluster head.

Third, the cluster head collects the safety messages and according to the data channel reservation requests, it assigns ICD and CRD channels (see Figure 3.12). Fourth, the cluster head broadcasts collected safety messages and the data channel schedule back to its cluster members. Finally, each cluster member tunes its transceiver 2 to the channel assigned to transmitting/receiving non-safety data.

For the inter-cluster communication protocol, once the cluster head has collected the safety messages from its cluster members, it uses a data fusion technique to combine the safety messages and then tunes to the ICC channel to forward the messages to its neighboring cluster heads. The ICD channel is assigned to one vehicle in each cluster and by using the contention-based MAC this vehicle can transmit or receive non-safety messages from other clusters.

However, CBMMAC has been evaluated only for simple highway scenarios where all the vehicles are moving in the same direction. As shown in Table 3.3, the cluster head can only send or receive real-time traffic. Moreover, The authors have not studied the inter-cluster interference problem when two or more clusters are in close This system has been proposed by Ding and Zeng [START_REF] Ding | A clustering-based multi-channel vehicle-to-vehicle (V2V) communication system[END_REF] to improve road safety by reducing the number of potential accidents. Unlike the IEEE 802.11p standard, in this system the medium is divided into multiple control channels and one data channel.

All the control channels use the CSMA/CA protocol, while the data channel uses TDMA/CDMA scheme to guarantee low transmission delay without collisions within each cluster. Firstly, all the vehicles tune to the control channel to form clusters. One cluster head CH is elected and each cluster member periodically sends its position and speed to its CH during its own TDMA time slot on the data channel. Then, in order to avoid inter-cluster interference, each CH selects a different orthogonal code from that of its neighboring CHs (the CDMA principle). This protocol contains a Vehicle Accident Avoidance Mechanism (VAAM) to inform close vehicles about a dangerous situation such as an accident or to warn them of some dangerous behavior.

The simulation results show that the CBMCS provides an efficient channel utilization and fast access delay for safety applications, but the evaluation was limited only to safety applications and for simple highway scenarios. The authors do not describe how the multiple control channels are utilized in this protocol and it remains unclear as to whether CBMCS can handle non-safety applications.

P5) Adaptive Real-time Distributed MAC (A-ADHOC)

A-ADHOC [START_REF] Miao | A-ADHOC: An adaptive real-time distributed MAC protocol for Vehicular Ad Hoc Networks[END_REF] In other words, each vehicle can tune to the Control Channel (CCH) or to specific service channels (SCHs) if needed during the time cycle.

A cluster formation algorithm based on the traffic flow [START_REF] Almalag | Using Traffic Flow for Cluster Formation in Vehicular Ad-hoc Networks[END_REF], which is used in TC-MAC, was proposed in order to provide a more stable clustering architecture with less communication overhead than is caused by cluster head election and cluster maintenance procedures. During the cluster formation process, each cluster member will be assigned a local ID by its cluster head which always has a local ID 1, while ID 0 is reserved for a virtual vehicle.

TC-MAC takes advantage of the local IDs that are assigned in the cluster formation algorithm. The medium access time is divided into several periodic time frames of length equal to 100 ms. Each frame is divided into N max /k time slots of fixed size τ ms, based on the data rate and the maximum packet size where N max is the maximum number of vehicles in the cluster and k is the number of slotted service channels (for the DSRC architecture, there are six service channels numbered from 0 to 5). Moreover, the time access on the control channel is also divided into periodic frames and each frame is divided into N max /k time slots. Each time slot on the CCH is divided into k mini-slots of size τ /6 ms used to broadcast beacons or safety messages. The main idea of the slot reservation schedule is that in each frame, each vehicle number j is allocated the time slot (j div k) on the service channel number (j mod k) and competes for one mini-slot on the control channel during the time slot (k div j) -1.

Then vehicle j uses its mini-slot to inform the other vehicles of its transmission during j s time slot on the SCH. Each new vehicle joining the cluster attempts to get the attention of the cluster head by transmitting in the mini-slot number 0 reserved for the virtual vehicle. TC-MAC has been used for intra-cluster management and safety message delivery within the cluster in which the cluster head is responsible for broadcasting safety or control messages. In addition, cluster members can use their time slots on the service channels to exchange non-safety data in unicast or multicast communication mode.

Although the simulation results show that TC-MAC performs better than IEEE 802.11p, it also has some failings. This protocol was designed for simple highway traffic in which all the vehicles are moving in the same direction, and thus the collision rate will be high in bidirectional traffic and urban scenarios due to the merging collision problem. This approach is intensely dependent on the local IDs delivered by the cluster heads in each cluster. Each cluster head should periodically update the table of the cluster members and their local IDs and then send this information to all cluster members, which increases the overhead. It is clear that one of the main benefits of using a clustering technique in TC-MAC is the efficient utilization of all the paper, in which period of time the cluster formation and cluster maintenance take place. Moreover, high collision levels when two or many clusters are in close proximity are caused by the inter-cluster interference problem. Since each time slot on the control channel is divided into six mini-slots, the throughput on each service channel is six times higher than on the control channel, which shows that TC-MAC has been designed to provide a high transmission rate for non-safety messages; this inevitably has a significant consequence for safety applications. or when a vehicle leaves the cluster and how its allocated time slot will be released and reallocated.

Summary of TCBT protocols

Eight cluster based TDMA MAC protocols have been presented. Table 3.4 gives a comparison of these protocols and contrasts their performances and features. All these TCBT protocols have been proposed only for one specific scenario (Highway) and do not address the different requirements presented by urban scenarios where it is more difficult to form stable clusters when there are traffic lights, crossroads, and trafficjams, as well as a high density of vehicles. Only CBMMAC [START_REF] Su | Clustering-based multichannel MAC protocols for QoS provisionings over vehicular ad hoc networks[END_REF][START_REF] Su | Cluster-based multi-channel communications protocols in vehicle ad hoc networks[END_REF] is purpose-made for highway scenarios where the vehicles are moving in opposite directions. In order to avoid merging collision and inter-cluster interference problems, CBMMAC separates the clusters by using the CDMA technique. As a result, CBMMAC operates well and achieves improved performance under high traffic load and for larger networks.

However, we note from the table that the inter-cluster interference is possible for the majority of TCBT protocols.

These protocols can perform well when used in specific scenarios. For example CBT and CBMAC perform well when node density is low. However, their performance degrades when vehicle density increases due to the high collision rate caused by the inter-cluster interference problem. In CBT, a high network load implies a high access delay and thus degrades the network performance. Multi-channel protocols (e.g. TC-MAC, CBMCS and CBMMAC) can support a wide range of applications and perform better under different traffic conditions than single channel protocols which are tuned for a short range of applications (only data messages).

TC-MAC and CBMAC can achieve a medium transmission range (respectively 300m and 500m), however the transmission ranges achieved by the other protocols (between 100m and 250m) are still unacceptable, since the inter-cluster collision rate increases as the transmission range decreases. Increasing the transmission range, de-creases the number of clusters in the network and thus the inter-cluster collision rate will automatically decrease. In contrast to ADHOC MAC and A-ADHOC, CBT, CAH-MAC and CBMAC do not support delay-sensitive applications and are limited only to throughput-sensitive applications as they are efficient only for data messages.

However, A-ADHOC can operate well under different traffic conditions, as it implements an adaptive frame length mechanism according to vehicle density. Moreover, we note that TC-MAC, CBMCS and CBMMAC perform even better when the average speed becomes higher. The average speed has no impact on the performance of these protocols because they implement stable cluster formation mechanisms.

TDMA-based MAC protocols in centralized topology (TCT)

A MAC protocol should exploit VANET characteristics like restricted mobility, the presence of RSUs, and the large transmission range of RSUs to ensure real-time and reliable delivery of messages. Centralized TDMA-based MAC protocols which exploit the existence of RSUs assign time slots and disseminate control information which can reduce channel allocation delay and scheduling overhead. The centralized slot allocation mechanism consists of two simple phases. In the first phase, each vehicle that has message ready to transfer requests the RSU for a slot on a specific channel. In the second phase, the RSU allocates a particular slot to the vehicles that are moving within its communication area. Then the RSU broadcasts the final slot allocation map to all the vehicles in its area.

TDMA problem statement in centralized networks

When a centralized scheduling and management of the time slots is used, some issues should be addressed in order to implement efficient and fair centralized TDMA-based MAC protocols:

Inter-RSUs interference

Each RSU adaptively creates and manages the TDMA slot reservation schedule for vehicles in its coverage. Thus, the same set of time slots can be allocated to vehicles in neighboring RSU regions. However, if there is an overlap between two neighboring RSUs that use the same frequency band, the messages broadcasted in one RSU region will affect the communications in the neighboring RSU region.

Short stay period in an RSU region

Due to their high speed, vehicles can join/leave an RSU region in short intervals of time, which leads to breaks in communication. Thus, the centralized MAC should ensure that a vehicle can continue to communicate at all times. Moreover, at any moment, the density of vehicles in an RSU region can vary rapidly from only a few vehicles to a high number of vehicles.

TCT protocols

In recent years, some centralized TDMA-based MAC protocols have been proposed

to guarantee real-time and reliable communications in VANETs while avoiding the access collision problem due to concurrent access to the same time slot. Each protocol has been proposed for a particular problem in a specific mobility scenario. protocol, it also has some drawbacks: the protocol does not handle communications between vehicles belonging to two different subnets. Moreover, due to high node 9 The vehicles that are within the same RSU area.

mobility, the interval of time in which the vehicle stays in an RSU region is very short, which can lead to breaks in communication.

P2) Risk-Aware Dynamic MAC (R-MAC) for delivering beacon messages. The CSMA segment size in a frame is determined by the average total number of potential collisions. For this, the authors have proposed a stochastic collision prediction model to compute the average total number of potential collisions within a platoon.

However, R-MAC has been proposed for a simple highway with one lane in which all the vehicles are moving in the same direction. Moreover, like the ACFM protocol, R-MAC can not support QoS for non-safety applications and it is limited only to safety applications.

P3) Cluster Based RSU Centric Channel Access (CBRC)

The RSU assisted frequency and TDMA allocation protocol has been proposed and evaluated by Tomar et al. in [START_REF] Tomar | Cluster based RSU centric channel access for VANETs[END_REF][START_REF] Tomar | RSU centric channel allocation in Vehicular Adhoc Networks[END_REF]. The goal of the work is to develop a contention-free MAC approach with centralized control in RSUs, which minimizes channel allocation time and management overhead.

CBRC works by dividing the frequency spectrum into a number of frequency bands separated by guard bands and each frequency band is shared between vehicles via a TDMA scheme in which the access time is divided into eight fixed time slots of equal size separated by guard times. CBRC operates both on the RSUs and the vehicles. Each RSU divides the road into static clusters and the RSU can be the head for all the clusters. It can broadcast beacon messages containing its identity and location to all the vehicles in its communication area. When a vehicle enters the communication coverage of an RSU and receives its beacon message, it will attempt to get the attention of the RSU by sending it a registration request.

In order to support service differentiation and give safety messages a higher access priority than data messages, each RSU maintains two different queues of channel requests: one for safety applications and one for non-safety applications and, higher priority access is given to the safety application requests. When a registered vehicle has a message ready to transfer, it uses the control channel to request a channel by sending the RSU a channel request containing the application type. Moreover, the protocol is able to solve hidden and exposed node problems by using a channel allocation matrix which keeps information about the currently free and assigned channels. When a vehicle sends a channel request to an RSU to transmit data or a safety message to a neighboring vehicle which is already in communication with an other vehicle, the RSU uses the channel allocation matrix, and refuses to allocate the channel. On the other hand, when an exposed node sends a channel request to RSU it will be assigned a different frequency channel that will not conflict with its neighboring vehicle already in communication. However, the approach proposed by

Summary of TCT protocols

Four TDMA-based MAC protocols in centralized network topologies have been presented. Table 3.5 compares the performance and features of these protocols. The results are taken from the references indicated in Table 3.5. R-MAC and UTSP are not able to solve inter-RSU interference whereas ACFM and CBRC separate neighboring RSU areas by using different orthogonal frequencies. Indeed, ACFM and CBRC are based on a hybrid FDMA/TDMA scheme, which combines the advantages of both TDMA and FDMA. Here, fixed frequencies are assigned to the RSUs in such a way that no interference will occur. These frequencies are reused along the road in such a way that there are no two neighboring RSU nodes using the same frequency band, and the required frequency channels should be minimized as much as possible.

Moreover, the vehicles share the frequency band through the TDMA technique to communicate with each other and with the RSUs. As a result, these hybrid protocols reduce the interference between RSUs themselves, and between RSUs and vehicles thereby achieving a high throughput and low access delay. segments make R-MAC more scalable. The major limitation of all these protocols is that they were proposed only for simple highway scenarios and do not address the different requirements presented in the urban scenarios. UTSP was evaluated in a highway scenario with two directions of traffic, while CBRC was evaluated in a realistic highway scenario where vehicles were moving on a two-way highway at different speeds and accelerations and where the vehicles can also turn in different directions at junctions. Thus CBRC and UTSP can enhance the performances of existing centralized MAC protocols. Unlike the ACFM and R-MAC protocols, CBRC can support both non-safety and safety applications by maintaining priority queues for the channel request packets of safety and non safety applications while giving greater access priority to safety request packets. However, the single-channel protocols can be extended to support multichannel operations and achieve higher throughput for multimedia applications as well as bounded transmission delays for real-time applications. Centralized topology MAC protocols or clustered topologies are more suitable to ensure the MAC QoS metrics in VANETs. Both of these categories of protocols generate a low control overhead compared to fully-distributed MAC protocols. However, centralized MAC protocols require the presence of RSUs installed along the road, which makes this category of protocols very expensive (see Table 3.6) as well as a wired backbone along the road. Although fully distributed MAC protocols support complex channel access mechanisms and produce a considerable control overhead, they are more generic protocols and assume as general a topology as possible, unlike centralized and clustered protocols which assume the presence of cluster heads and base stations, respectively. Moreover, free-contention multi-channel MAC protocols provide less delay for safety applications under different traffic conditions, and can achieve high throughput for non-safety applications. • Large speed variance: Several TDMA based MAC protocols fail to guarantee channel access fairness for vehicles traveling at different speeds. Vehicles moving at high speed have a limited time period to acquire the requested service within a certain range of communication. This fairness problem may occur frequently in vehicular environments where the velocities of different vehicles have a high relative variance. Therefore, this issue needs to be considered and addressed efficiently when developing MAC protocols for VANETs.

• Access and merging collision problems: Some TDMA-based MAC protocols assume that it is not possible to have central coordinating nodes positioned along the highway for economic reasons (related to the high cost of deploying RSUs) and assume as generalized a topology as possible. As a result of using distributed TDMA, access collision and merging collision problems can occur between vehicles trying to access the same time slots. However with the exception of [START_REF] Omar | Evaluation of VeMAC for V2V and V2R Communications under Unbalanced Vehicle Traffic[END_REF], these problems have not been studied in most TDV protocols.

Moreover, the solution proposed in [START_REF] Omar | Evaluation of VeMAC for V2V and V2R Communications under Unbalanced Vehicle Traffic[END_REF] needs to be studied in greater depth, particularly in a highway environment where densities of vehicles moving in opposite directions are both high but not equal. The design of future TDMAbased MAC protocols in fully distributed VANETs should address these problems caused by the mobility of nodes. However, in order to ensure a fair channel access without any access collisions, each vehicle should periodically exchange control messages with its one-hop neighbors, resulting in a significant amount of additional control overhead. Thus, the control overhead of distributed slot reservation mechanisms should be minimized in future work.

• Inter-RSU interference: Some TDMA-based MAC protocols assume that there are central points (RSUs) which are used to coordinate channel access for the vehicles in their coverage area. However, due to the overlapping area between two neighboring RSUs that use the same frequency band, future centralized TDMA schedules should contain an efficient inter-RSU communication mechanism that is able to reduce the effect of interference between vehicles in the overlapping regions. This should be done in such a way as to ensure QoS continuity, especially when a vehicle is leaving/joining an RSU coverage area.

• Cluster stability and inter-cluster interference: A great deal of attention has currently been paid to TDMA protocols where one vehicle in each group is elected to create and maintain a slot assignment schedule. Despite the research efforts to improve the performance of cluster-based TDMA in VANETs, there remain some open issues due to the rapid changes in network topology that require further study:

-The stability of clusters is a serious issue in VANETs. Cluster instability may decrease the performance of MAC protocols.

-Inter-cluster interference, which is a source of collisions can be addressed without having to use expensive spectrum and complex wide-band mechanisms such FDMA or CDMA.

-In VANETs, a vehicle can join or leave a cluster at any time. These two operations will only have local effects on the topology of the cluster if the vehicle concerned is a cluster member. However, if the vehicle is the cluster head, the channel access schedule is lost and collisions between messages will occur. Therefore, anticipating which vehicle will become the new cluster head should be investigated, particularly as it is possible to predict vehicles' movements in a VANET.

-Developing mechanisms for cluster formation and maintenance with less overhead will improve the performance of cluster based TDMA protocols in VANETs.

Conclusion

Improving road safety requires efficient and reliable MAC protocols. These MAC protocols can be based on TDMA schemes. This chapter, which presents an extensive overview of research related to TDMA-based protocols for VANETs, shows how well these protocols can satisfy the stringent requirements of safety and user-oriented applications. We have proposed a novel topology-based classification of these MAC protocols and we have highlighted the TDMA problem statement for each topology caused by the nodes' mobility. Furthermore, we have surveyed the existing TDMAbased MAC protocols. A comparison of these protocols has been provided based on their performance metrics. Additionally, we have given a comparison between the three classes of MAC protocols. This comparison was made in order to better understand the differences between the various protocols. We note that cluster-based TDMA MAC protocols have achieved the required QoS level, thanks to the significant research effort made on this topic. Centralized TDMA-based MAC protocols for VANETs have also received considerable attention over recent years. However, many distributed TDMA protocols which assume the topology to be as flat as possible, do not address the TDMA problem statement in a fully distributed VANET caused by the high levels of speed and the movement in opposite directions. To reduce interference between overlapping areas, some protocols make use of other access techniques such as CDMA and FDMA which make them more complex and expensive. Resolving these problems will require greater efforts in the future. Moreover, the topological fea-

tures

Introduction

Improving road safety is among the main objectives of VANET design as we have seen in the previous chapter. This objective can be achieved by using efficient safety applications which should be able to wirelessly broadcast warning messages between neighboring vehicles in order to inform drivers about a dangerous situation in a timely manner. To insure their efficiency, safety applications require reliable periodic data broadcasting with low latency and while minimizing the number of collisions. In this chapter, we present a novel Distributed TDMA based MAC protocol, named DT-MAC, developed specifically for a highway scenario. DTMAC is designed to provide the efficient delivery of both periodic and event-driven safety messages. The protocol uses the vehicles' location and a new slot reuse concept to ensure that vehicles in adjacent areas have a collision-free schedule. Simulation results and analysis in a highway scenario are presented to evaluate the performance of DTMAC and compare it with the VeMAC protocol.

DTMAC assumptions

A VANET in a highway scenario consists of a set of vehicles moving in opposite directions and under varying traffic conditions (speed, density). DTMAC is based on the assumption that each vehicle in a VANET is equipped with a GPS or a GALLILEO receiver that also allows it to obtain an accurate real-time three-dimensional geographic position (latitude, longitude and altitude), speed and exact time. Moreover, synchronization between vehicles may be performed by using GPS timing information. Each road is divided into small fixed areas (see Figure 4.1). Note that the area size depends on the transmission range of the vehicles (around 310m). Moreover, we assume that the vehicles are equipped with digital maps to determine which area they are in. In the following, we detail the slot scheduling mechanism in DTMAC and we show how this protocol can provide an efficient time slot utilization for the participating vehicles, while minimizing transmission collisions caused by the hidden node problem.

DTMAC preliminaries

We propose a completely distributed and infrastructure free TDMA scheduling scheme which exploits the linear feature of VANET topologies. The vehicles' movements in a highway environment are linear due to the fact that their movements are constrained by the road topology. Our scheduling mechanism is also based on the assumption that each road is divided into N small fixed areas, denoted by x i , i = 1, . . . , N (see Figure 4.1). Area IDs can be easily derived using map and GPS Information.

TDMA slot scheduling mechanism

Our distributed TDMA scheduling mechanism uses vehicles location and slot reuse concept to ensure that vehicles in adjacent areas have collision-free schedule. The channel time is partitioned into frames and each frame is further partitioned into three sets of time slots S 0 , S 1 , and S 2 of size equal to n1, n2 and n3, respectively. These sets are associated with vehicles moving in the areas x i , x i+1 , and x i+2 , respectively.

As shown in Figure 4.1, by dividing the time slots into three sets, vehicles v 1 and v 3 that are moving within the two areas x 1 and x 3 , respectively, can not transmit simultaneously to vehicle v 2 because they are accessing disjoint sets of time slots.

Therefore, our TDMA scheduling mechanism can decrease the collisions rate caused by the hidden node problem. In each area, the vehicles access the time slots associated to their locations with the same probability. In the rest of this chapter, we adopt the following notations:

• S j (v): The set of time slots associated to the area in which the vehicle v is traveling.

• N (v): The set of neighbors 1 of vehicle v on the transmission channel.

Every active vehicle in the network should be allocated a fixed slot in the frame for safety messages or other control packet transmissions. It is obvious that a vehicle's slot cannot be used by any neighboring vehicles within the same area or in adjacent areas, otherwise collisions will occur. The goal of this work is to propose an efficient slot reuse algorithm without having to use expensive spectrum and complex broadband mechanisms such as FDMA or CDMA. In fact, the three subsets of time slots will be reused between neighboring areas in such a way no vehicle in different adjacent areas can access the channel at the same time, and thus no interference will occur.

Let us suppose that an active vehicle v moving within the area x i needs to acquire a time slot on the transmission channel. Vehicle v starts listening to the channel during the set of time slots reserved for the area in which it is traveling, let S j (v), where j = (i + 2) mod 3.

• Each vehicle that hears exactly one node transmission in a time slot reserved for its location, will set the status of the slot to "busy" and record the ID of the vehicle accessing the channel in this time slot in the corresponding VC ID field.

• If a vehicle does not hear anything during a specific time slot, it will set its status to "free" in the FI.

• If a vehicle can not decode the data during a specific time slot, it will set its status to "collision" in the FI.

• When a vehicle A has sent data in a given slot, it looks in the field information of the next slots to discover whether its neighbors have correctly received its data. If a neighbor of A reports collision for this slot (in the FI) or even if this slot is reported to be "busy" but being sent by another node (say B in the VC ID), A considers that its transmission has led to a collision 2 .

1 The set of neighbors is the set of vehicles that are moving within the same area.

2 Actually a node A considers that its transmission is a success if and only if all its neighbors report a success in the FI of their slots specifying that the data was sent by node A.

At the end of the frame the vehicle v can determine the set N (v) and the set of busy slots in S j (v) used by each vehicle u ∈ N (v), denoted by B(v). In order to avoid any collision problem, this set of time slots can not be used by any neighboring vehicles. Therefore, vehicle v can determine the set of available time slots F (v) and then attempts to select one of them at random, say time slot k.

Algorithm 2 FI formation Input S j (v) : the set of time slots that the vehicle v can reserve.

α j , β j : are the indexes of the first and the last slot of the set S j (v), respectively.

1: for each slot index k = α j to β j do 2:

if only one vehicle u is heard in the slot k then if more than one vehicle is heard in the slot k then end if

12: end for Algorithm 2 outlines the details of how the frame information is built. In the algorithm, i is the index of the area in which a vehicle is traveling. If no other vehicle moving in the same area as vehicle v attempts to acquire a time slot k, no access collision occurs. In this case, the attempt of vehicle v is successful and all nodes u ∈ N (v) add vehicle v to their sets N (u) and record that vehicle v is using time slot k. However, if at least one node within the same area as vehicle v accesses time slot k, then all the transmissions fail and the time slot k is not acquired by any of the contending vehicles. In this case, vehicle v will discover that its attempt was unsuccessful as soon as it receives a packet from any node u ∈ N (v) indicating that vehicle v / ∈ N (u). Vehicle v then attempts to access one of the time slots in F (v), and so on until all nodes u ∈ N (v) indicate that node v ∈ N (u) and announce that the time slot has been allocated to vehicle v. However, when an access collision occurs among the vehicles that are moving in the same area, the probability of access collision in the next reservation is increased since the choice of available slots will be restrained in the new set F (v). In order to ensure channel access continuity, each vehicle should determine the expected available time slots on the set of time slots associated with the next area before leaving the area in which it is currently traveling. In fact, when a vehicle is using a given time slot in the set S j , it should acquire an available time slot in the set S (j+1) mod 3 as its future time slot before leaving its current area. Algorithm 3 outlines the details of the slot reservation mechanism. It is executed by each vehicle v which needs to reserve a time slot.

Algorithm 3 Slot reservation 1: Determine the area ID x i .

2: Determine the set of time slots S j associated with the area x i .

3: Determine the available time slots F in the set S j .

4: if V = { } then 5:
Randomly reserve an available time slot k. Go back to 4

13: end if

Access collision probability

In this section, we present a model to compute the average access collision probability.

We assume that the VANET scenario taken into account is a two-way highway of length equal to L. We assume that every area of the road has a unique index number such as 1, 2, . . . , N . The probability with which the vehicle in the i -th area decides to access the available j -th time slot reserved for its location is denoted by p ij . For instance, the probability of the vehicle in the fourth area accessing the 7-th slot is denoted by p 47 . First of all, we calculate the access collision probability when a vehicle tries to access an available time slot.

• A i : actual number of active vehicles in a given area x i .

• P aci : the access collision probability of the vehicle in area x i accessing the channel.

• α i , β i : the indexes of the first and the last time slots reserved for the area x i .

For DTMAC, the probability of accessing an available time slot j by a contending vehicle v in the area i is v) , where N succ i (v) is the number of vehicles in the area i which have successfully acquired a time slot as derived from the framing information received by vehicle v. Therefore, the access collision probability of a vehicle in area x 1 can be evaluated as:

p ij = 1 (β i -α i )-Nsucc i (
P ac1 = 1 -P nac1 (1)
P nac1 = β 1 j=α 1 p 1j * A 1 k=2 (1 -p 1j ) (2)
where P ac1 denotes the access-collision probability in area x 1 and in a given time slot, while P nac1 denotes the non access-collision probability in area x 1 and in a given time slot.

Based on the above derivation, the expression of the total access collision probability of the vehicles in all locations can be given by:

P act = 1 -P nact (3)
P nact = N i=1 P naci = N i=1 β i j=α i p ij * A i k=2 (1 -p ij ) (4)
where, P act represents the total access-collision probability of the vehicle accessing the channel, P nact represents the total non access-collision probability of the vehicle accessing the channel.

P aver-ac = 1 N * P act (5)
P aver-ac represents the average access collision probability of the vehicle accessing the channel. The simulation parameters used in our experiments are summarized in Table 4.5.1.

We have used a parameter, called the area occupancy (AO) [START_REF] Zhuang | VeMAC: A novel multichannel MAC protocol for vehicular ad hoc networks[END_REF], equal to Nv×R L h ×Ts in a highway scenario, where N v is the total number of active vehicles, R is the communication range, L h is the length of the highway, T s is the number of slots reserved for each area. DTMAC is evaluated based on the following metrics:

1. The access collision rate: is defined as the average number of access collisions per slot per area.

2. The merging collision rate: is defined as the average number of merging collisions per slot per area.

3. The broadcast coverage ratio: is defined as the average of the total number of vehicles that successfully receive messages to the total number of vehicles within the communication range of the transmitter.

4. The packet loss rate: is defined as the average of the total number of vehicles that do not successfully receive messages to the total number of vehicles within the communication range of the transmitter.

DTMAC performance evaluations

The performance of DTMAC depends on the sizes of the three sets of time slots n1, n2 and n3 that determine its behavior. An optimal tuning of these parameters can improve the QoS of DTMAC. For this, we evaluated several configurations in different speed scenarios (by varying the speed deviation σ between 20, 30 and 50 km/h) with different area occupancy values to find the optimal values of these parameters. than VeMAC even for a high AO since it assigns disjoint sets of time slots to vehicles moving in adjacent areas. However, in VeMAC, the vehicles that cannot access a time slot from the set of slots reserved for its direction, will attempt to access any available time slot reserved for vehicles moving in the opposite direction. Moreover, 3 In principle, the DTMAC algorithm prevents any merging collision. However when errors at the physical layer lead to a reception error (the FI is not coherent with the transmission), a node may consider that its transmission is a collision even if it has been the sole transmitter within its zone in the slot. Thus, if this error is not on the first attempt of the node to acquire a slot, we consider that it is a merging collision. For instance, at a AO = 0.96, the VeMAC protocol shows approximately 58.23% higher rate of packet loss than the DTMAC protocol.

Conclusion

Applying VANETs to reduce the number of accidents and enhance driver and passenger safety requires a fast and reliable broadcast service. MAC protocols play a primary role in providing efficient delivery and while avoiding data packet loss as much as possible . Although TDMA-based MAC protocols can provide deterministic access times without collisions, the scheduling mechanisms of these protocols must be able to dynamically adapt to changing network topologies. In this chapter, we propose a completely distributed and infrastructure-free TDMA scheduling scheme, named DTMAC which exploits the linear topology of VANETs. The way that slots are allocated and reused between vehicles is designed to avoid collisions caused by the hidden node problem. The analytical model of the average access-collision probability is proposed. The simulation results show that, compared to VeMAC, DTMAC provides a lower rate of access and merging collisions, which results in significantly improved broadcast coverage.

We focused on the periodic broadcast of safety messages between vehicles and their direct neighbors. However, a safety message can be transmitted over a long distance in a VANET through multiple intermediate vehicles for instance to warn far vehicles about a dangerous situation. In the next chapter we focus on multi-hop communication for safety message delivery and we show how some DTMAC features, such as knowledge of vehicles that are moving within the two neighboring areas, can be exploited to design an efficient routing protocol that can ensure coherent decisions between the MAC and the routing layers.

Introduction

Multi-hop communication is an effective method that can be used for information exchange over distances greater than the transmission range of the transmitting vehicle. However, the nodes in VANETs are characterized by their high mobility, so the network topology can change quickly and frequently [START_REF] Hadded | Tdmabased mac protocols for vehicular ad hoc networks a survey, qualitative analysis and open research issues[END_REF]. These conditions create additional difficulties to build and maintain a multi-hop routing path between a given source and its corresponding destination nodes. In this chapter, we focus on designing a TDMA aware Routing Protocol for Multi-hop wireless vehicular ad hoc networks (TRPM) in order to provide the ability to transmit/receive safety messages over long distances. The proposed routing scheme is based on a MAC protocol, in which the intermediate vehicles are selected based on the TDMA scheduling. Simulation results reveal that our routing protocol significantly outperforms other protocols in terms of average end-to-end delay, average number of relay vehicles and the average delivery ratio.

Problem statement

Generally, the routing protocols which are proposed for VANETs are designed to find the best path for end-to-end packet delivery, which can satisfy QoS requirements by considering the number of relay nodes and link lifetime. Although these protocols can achieve good performance in terms of the metrics studied, they are not simultaneously optimized to maximize the overall network performance. In 5.3 Cross-layer MAC and routing protocols in vehicular networks

Contention aware routing protocol

The simultaneous transmissions in VANETs due to multiple concurrent vehicles, lead to an increase in the collisions rate which can degrade the network performance in terms of packet delivery ratio and delay. The relevance of this issue has been confirmed by the development of a specific IEEE standard to support VANETs. The IEEE 802.11p [START_REF]IEEE standard for information technology-Telecommunications and information exchange between systems-local and metropolitan area networksspecific requirements part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) and physical layer (PHY) specifications amendment 6: Wireless access in vehicular environments[END_REF], which is the emerging standard deployed to enable vehicular communication, is a contention-based MAC protocol, using a priority based access scheme that employs both Enhanced Distributed Channel Access (EDCA) and Carrier

Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanisms [START_REF] Uzcátegui | WAVE: A Tutoriat[END_REF]. This standard is a contention-based MAC method that cannot ensure a reliable broadcast mechanism with bounded access delays. This disadvantage is particularly detrimental in VANETs which are specially designed to improve road safety. Despite that, several multi-hop routing protocols use this approach to transmit data. For instance, in [START_REF] Blaszczyszyn | Opportunistic broadcast in VANETs (OB-VAN) using active signaling for relays selection[END_REF] the authors have proposed an opportunistic broadcast protocol named OB-VAN to overcome the problem of packet delivery in VANETs. OB-VAN uses a modified IEEE 802.11 MAC layer through an active signaling mechanism to select a suitable next-hop relay from all the candidate vehicles that have correctly received the packet.

Qian et al. [START_REF] Qian | A next-hop selection scheme providing long path lifetime in VANETs[END_REF] developed and evaluated an AODV-based1 next-hop selection scheme called LPLS (Long Path Lifetime Scheme). The main goal of this work is to achieve a satisfactory lifetime during the route discovery process in which each relay node scans all its one-hop neighbors and uses the optimal stopping theory to select the best nexthop vehicle. Since neither of those protocols uses a contention-free MAC schemes, it is possible that they cannot operate well in sparse or dense mobility scenarios.

Free-contention aware routing protocol

Many alternatives exist to mitigate collision between vehicle transmissions by using a contention-free protocols at the medium access layer. For instance, the authors in [START_REF] Omar | On Multihop Communications For In-Vehicle Internet Access Based On a TDMA MAC Protocol[END_REF] have proposed a cross-layer MAC and routing scheme based on VeMAC protocol The main idea of TRPM is to select the next hop using the vehicle position and the time slot information from the TDMA scheduling. Like the GPSR protocol [START_REF] Karp | GPSR: greedy perimeter stateless routing for wireless networks[END_REF], we assume that each transmitting vehicle knows the position of the packet's destination.

In TRPM, the TDMA scheduling information and the position of a packet's destination are sufficient to make correct forwarding decisions at each transmitting vehicle.

Specifically, if a source vehicle is moving in area x i , the locally optimal choice of next hop is the neighbor geographically located in area x i+1 or x i-1 according to the position of the packet's destination. As a result, the TDMA slot scheduling obtained by DTMAC [START_REF] Hadded | An Infrastructure-Free Slot Assignment Algorithm for Reliable Broadcast of Periodic Messages in Vehicular Ad hoc Networks[END_REF] can be used to determine the set of next hops that are geographically closer to the destination. In fact, each vehicle that is moving in the area x i can know the locally optimal set of next hops that are located in adjacent areas x i+1 or x i-1 by observing the set of time slots S (i+3)%3 or S (i+1)%3 , respectively. We consider the same example presented above when vehicle G as the destination vehicle that will broadcast a message received from vehicle A. As shown in Figure 5.2, only two relay vehicles are needed to ensure a multi-hop path between vehicle A and G (one relay node in the area x 2 and another one in the area x 3 ).

In the following, the DTMAC protocol has been used by the vehicles to organize the channel access. The TDMA slot scheduling obtained by DTMAC is illustrated in Figure 5.2. Firstly, vehicle A forwards a packet to B, as vehicle A uses its frame information to choose a vehicle that is accessing the channel during the set S 1 . Upon receiving the packet for forwarding, vehicle B will choose by using its frame information a vehicle that's accessing the channel during the set of time slots S 2 (say vehicle D). Then, vehicle D will forward the packet to G, as G is moving in area x 4 (accessing the channel during the set S 0 ) and it is the direct neighbor of vehicle D. By using DTMAC as the MAC layer, we can note that the path A-B-D-G is the shortest, in terms of the number of hops as well as the end-to-end delay which is equal to 6 time slots (2 time slots between t 0 and t 2 as t 2 is the transmission slot for vehicle B, then 2 time slots between t 2 and t 4 as t 4 is the transmission slot for vehicle D and finally 2 time slots between t 4 and t 0 as t 0 is the transmission slot in which vehicle G will broadcast the message received from vehicle A).

Packet forwarding algorithm

The idea of TRPM is the following. Whenever a vehicle i accessing the channel during the set S k wants to send/forward an event-driven safety message, it constructs two sets of candidate forwarders based on its frame information FI as follows, where T S(j) indicates the time slot reserved by vehicle j.

• A i = {j ∈ N (i) | T S(j) ∈ S (k+1)%3 } //
The set of vehicles that are moving in the adjacent right-hand area.

• B i = {j ∈ N (i) | T S(j) ∈ S (k+2)%3 } //
The set of vehicles that are moving in the adjacent left-hand area.

Each source vehicle uses the position of a packet's destination and the TDMA scheduling information to make packet forwarding decisions. In fact, when a source vehicle i is moving behind the destination vehicle, it will select a next hop relay that belongs to set B i ; when the transmitter is moving in front of the destination vehicle, it will select a forwarder vehicle from those in set A i . Algorithm 4 outlines the behavior of our scheme during the procedure for sending an event-driven safety messages. For each vehicle i that will send or forward a message, we define the normalized weight function WHS (Weighted next-Hop Selection) which depends on the delay and the distance between each neighboring vehicle j. WHS is calculated as follows:

W HS i,j = α * ∆t i,j τ -(1 -α) * d i,j R (1)
Where:

• τ is the length of the TDMA frame (in number of time slots).

• j is one of the neighbors of vehicle i, which represents the potential next hop that will relay the message received from vehicle i.

• ∆t i,j is the gap between the sending slot of vehicle i and the sending slot of vehicle j.

• d i,j is the distance between the two vehicles i and j, and R is the communication range.

• α is a weighted value in the interval [0, 1] that gives more weight to either distance or delay. When α is high, more weight is given to the delay. Otherwise, when α is small, more weight is given to the distance.

We note that the two weight factors ∆t i,j τ and

d i,j
R are in conflict. For simplicity, we assume that all the factors should be minimized. In fact, the multiplication of the second weight factor by (-1) allows us to transform a maximization to a minimization. Therefore, the forwarding vehicle for i is the vehicle j that is moving in an adjacent area for which W HS i,j is the lowest value.

When a vehicle receives a message (as shown in Algorithm 5), it checks whether it is the destination of the packet (line 1), and if it is, it passes the packet to the upper layer (line 2). However, if the packet is destined for another vehicle, the receiver will check if the destination is moving in the same area (line 4), and if it is, the message will be transmitted immediately to its final destination (line 5). Otherwise, if the packet's destination is moving in another area, the receiver will calculate the next hop vehicle towards the destination (lines 7-11). If a relay node is found, the message will be forwarded (line 15), otherwise the message will be queued (line 17).

Each forwarding vehicle includes its area ID in the relayed message. These steps are repeated by each relay vehicle until the packet is received by its final destination vehicle. To deliver a packet from a source to a destination, each vehicle i receiving a Algorithm 4 Action at each vehicle which has an event-driven safety message to be sent 1: Input:

2: msg: An event-driven safety message

f rwd i ={k ∈ A i | W HS i,k = min (W HS i,l ∀ l ∈ A i )} 7: else 8: f rwd i ={k ∈ B i | W HS i,k = min (W HS i,l ∀ l ∈ B i )} 9: end if 10: if f rwd i ≥ 0 then 11:
send msg(msg.src, msg.dst, msg.f rwd i )

12: else 13:

go to 1 For instance, in the situation depicted in Figure 5.3, vehicle T X will send a message to vehicle RX. Since, the vehicle T X is moving ahead of vehicle RX, it will forward the message to vehicle F 1 that is moving in the area x 2 and accessing the channel during the set of time slots S 1 . Vehicle F 1 needs to wait until its slot to forward the packet (i.e. it needs to wait for T S(F 1) -T S(T X) slots). As vehicle F 1 has received the packet from vehicle T X which is moving in the area x 1 , vehicle F 1 will immediately select a forwarding vehicle from those located in the area x 3 which are accessing the channel during the set of time slots S 2 . Then, assuming that vehicle F 1 decides to choose vehicle F 2 as the next hop to relay the packet, once the slot starts, the vehicle F 1 will retransmit the message to vehicle F 2 which in turn will forward the packet directly to its final destination RX.

As shown in Figure 5.3, one frame is sufficient to deliver a message from TX to RX, because this message is forwarded three times (i.e. n 0 + n 1 + n 2 = τ slots).

Based on this example, we can theoretically estimate the End-to-End Delay (EED) needed to deliver a message from a source vehicle i to a destination vehicle j. EED is estimated as follows, where S d is the slot duration which is fixed to 0.001s.

EED i,j ≤ * dist i,j 3 * R * τ * S d (2)
Algorithm 5 Action at each vehicle which has received a safety message 1: Input:

2: msg: An event-driven safety message if msg.Area ID ≺ x j then 13:

f rwd i ={k ∈ A i | W HS i,k = min (W HS i,l ∀ l ∈ A i )} 14:
else 15:

f rwd i ={k ∈ B i | W HS i,k = min (W HS i,l ∀ l ∈ B i )} 16:
end if queue message(msg) and go to 1 5.5 Performance evaluation

Simulation plateform

In this section, we evaluate the performance of our proposed TDMA aware-routing protocol. To this end, we use the MOVE [START_REF] Karnadi | Rapid generation of realistic mobility models for VANET[END_REF] to generate vehicular traffic scenarios and SUMO [126] to perform real vehicular mobility simulations (see Figure 5.4).

Figure 5.4: Simulation framework.

Simulation scenarios and parameters

We generated a realistic VANET environment by selecting a real highway area from a digital map which took into account lane directions.

Simulation results

We compared the proposed TRPM with two multi-hop communication protocols having the same underlying principle (i.e. MAC-aware Routing Protocol). The first one is the Random TDMA2 aware Routing Protocol (RTDMA). In this protocol the time slots are allocated to vehicles randomly and the next hop decision for unicast traffic forwarding is based on the vehicles' positions and the time slot information from the random TDMA scheduling. The second protocol is the Contention aware Routing Protocol (CRP) which is based on classical flooding 3 , where every vehicle relays each packet received to all its one-hop neighbors at least once until the packet has been received by its final destination vehicle. These protocols are evaluated by varying the Source-to-Destination Distance (SDD) between 550m and 2550m. Considering a fixed highway length (i.e. 3km), we performed 10 experiments for each VANET scenario. Moreover, we evaluated these protocols on the same network scenarios in terms of the average end-to-end delay, average number of hops and average delivery ratio. The performance of TRPM depends on the value of alpha, which determines its behavior. In fact, when α is high, more weight is given to the delay. Otherwise, when α is small, more weight is given to the distance and thus to the number of hops.

Therefore, an optimal tuning of this parameter can improve the QoS of TRPM. For this, we evaluated several values of α in different scenarios (by varying the vehicle density to have 128, 192, 256 and 320 vehicles) to find the optimal value of this param-eter. Figure 5.6 shows the variation of the average end-to-end delay with the change in α values. We can see from this figure that the end-to-end delay is reduced to less than 150ms by choosing values of α between 0.3 and 0.6 under a high traffic condition scenario. However, when α < 0.3 or α > 0.6 the average end-to-end delay is high, the reason being that when α is small, more weight is given to the distance, hence the selected relay vehicles between the source and the destination generate more delay due to the high gaps between their sending slots. On the other hand, higher values of α give more weight to the delay than to the distance which provides routes that have a good delay but a greater number of relay vehicles as we can see in Figure 5.7.

In the following, we present the simulation results and we analyze the performance of our proposed protocol. For these results, the weight factor α was fixed to 0.4. show an average delay of 520.33ms and 626.3ms, respectively (i.e. approximately 122.2% and 167.47% higher than TRPM). This is mainly because, as discussed in Section 4 of this Chapter, the proposed protocol can reduce the gap between the sending slots of relay vehicles that are moving in adjacent areas by dividing the frame into three sets of time slots. Moreover, we can observe that RTDMA performs In Figure 5.9, we show the relationship between the average number of relay nodes and the source-to-destination distance. It is clear from this figure that the number of relay vehicles increases as the distance increases. We can note that TRPM can significantly reduce the number of relay vehicles required to deliver a message compared to RTDMA and CRP protocols. This is due to the fact that TRPM always selects only one relay vehicle for each area (i.e. one relay node for each 310m), in contrast to the RTDMA and CRP in which two or more relay vehicles can be successively selected within the same area. Unlike CRP and RTDMA, Figures 5.8 and 5.9 clearly show that TRPM achieves better performances in terms of both average end-to-end delay and average number of hops, since it uses a next-hop selection function that can balance the two metrics studied.

Figure 5.9: The average number of relay vehicles vs source-to-destination distance.

In order to assess the effect of collision in the performance of these protocols, we evaluate then on the following scenario where there is a background traffic that consists of a periodic message broadcasted by each vehicle every 100ms. It can be seen from Figure 5.10 that the average end-to-end delay of TRPM is the lowest for all the vehicle densities shown. We can conclude that vehicle density has no effect on the performance of TRPM. These results can be explained by the fact that the relay selection mechanism in TRPM is carefully designed so that the one-hop delay is always equal or less than τ /3. In order to validate the previous results, we evaluate the performance of these protocols in terms of delivery reliability. Figure 5.12 shows the average delivery ratio of the three protocols under consideration when varying vehicle density. As shown in this figure, TRPM achieves a considerably higher delivery rate of emergency messages than RTDMA and CPR. For instance for a high density (in the case of 280 vehicles), the TRPM protocol achieves an average delivery ratio of 98.4%, in contrast to RTDMA and CRP which show a rate of 75.91% and 65.52%, respectively.

We can note that TRPM maintains almost an average delivery ratio close to the ideal rate (i.e. 100%) for all VANET scenarios. This is because TRPM implements an optimized relay vehicle selection mechanism that completely avoids redundant transmissions. Moreover, TRPM is a contention-free based protocol that can reduce packet collisions in the presence of background traffic. We can also see that the CRP and RTDMA protocols have very poor performances. These results might well be expected for CRP since it is a flooding based routing protocol in which each vehicle retransmits the message received to all its neighboring vehicles without using any selection mechanism.

Figure 5.12: The average delivery ratio vs vehicle density.

Conclusion

The stringent requirements of VANET safety applications mean that their messages need to be delivered quickly and with a high degree of reliability. However, designing an efficient multi-hop communication protocol for safety message delivery is a major challenge in VANETs due to the rapid changes in network topology and the lack of infrastructure. In this chapter, we propose a novel TDMA aware routing protocol (TRPM) to allow a vehicle to send a safety message over a long distance through multiple relay vehicles. The message is delivered from a source vehicle to a destination vehicle using the geographic positions and the time slot information from the TDMA scheduling. Moreover, TRPM takes into account the efficiency of the relay selection by using a weighted next-hop selection function in order to make coherent next hop decisions in terms of both number of relay vehicles and end-to-end delay. The simulation results show that, compared to two other protocols, the cross layer protocol we propose provides better performances in terms of average end-to-end delay, average number of hops and average delivery ratio.

As discussed in Chapter 3, distributed TDMA-based MAC protocols produce a significant communication overhead to create and to maintain the TDMA schedules in highly dense networks. Moreover, the access collision problem may frequently occur between vehicles trying to access the same time slots when a distributed scheduling scheme is used. Thus, the focus of Part III of this thesis report will be the coordinatorbased TDMA scheduling mechanisms in which an RSUs in a centralized topology or the cluster head in a hierarchical topology is used as a local channel coordinator for the vehicles within their communication range. We will show that coordinator-based scheduling can solve some of the difficulties of the distributed TDMA scheme we have just developed. Actually, a great deal of attention has been paid to TDMA protocols where one vehicle in each group is elected to create and maintain a slot assignment schedule. Despite the research efforts to improve the performance of cluster-based TDMA, there remain some open issues due to the rapid changes in network topologies.

That is why, the next chapter will focus on cluster stability in VANETs.

Introduction

As mentioned in the previous chapter, cluster-based TDMA MAC protocols suffer from clustering instability due to the high mobility of nodes and rapid changes in network topology in VANETs. As breaks in communication links frequently occur in VANETs, ensuring cluster stability is difficult. Moreover, taking the vehicles' direction into account is not always sufficient to insure clustering stability in VANETs as can be seen in Figure 6.1 where the three vehicles v 1 , v 2 and v 4 are considered to be moving in the same direction and thus these vehicles can be grouped together to form a cluster. Since vehicle v 4 and vehicles v 1 and v 2 are not moving on the same road, vehicle v 4 will leave the cluster after a short period and it will need to join a new cluster. In this chapter, we identify and discuss certain essential features that the clustering protocols must satisfy to build stable clusters in VANETs and we propose two clustering algorithms to cope with cluster stability. The first is AWCP which is road map dependent and uses road IDs and movement direction in order to make clusters' structure as stable as possible. The second is an Angle-based Clustering Algorithm (ACA), which exploits the angular position and the direction of the vehicles to select the most stable vehicles that can act as cluster heads for a long period of time. However, the multiple control parameters of our AWCP, make parameter tuning a nontrivial problem. In order to optimize the protocol, we define a multiobjective problem whose inputs are the AWCP's parameters and whose objectives are: providing stable cluster structures, maximizing data delivery rate, and reducing the clustering overhead. We address this multi-objective problem with the Nondominated Sorted Genetic Algorithm version 2 (NSGA-II). We evaluate and compare its performance with other multi-objective optimization techniques: Multi-objective Particle Swarm Optimization (MOPSO) and Multi-objective Differential Evolution (MODE). Experiments reveal that NSGA-II improves the results of MOPSO and MODE in terms of spacing, spread, ratio of non-dominated solutions, and inverse generational distance, which are the performance metrics used for comparison.

Clustering in VANETs

When a vehicle node wishes to participate in a cluster head election, it firstly collects all the necessary one-hop neighbors information. In this section, we identify the rules that the clustering protocol must satisfy in VANET networks with the aim to form stable clusters, where re-clustering is reduced, and cluster members lifetimes are Rule 1. The cluster head vehicles should have sufficiently powerful radios to be able to communicate with the members of their clusters. This implies that the cluster heads should be close to the center of the cluster. Thus, the vehicle that has the minimum average Euclidean distance to their direct neighbors can be elected to act as the cluster head. The average Euclidean distance is:

δ(i, t) = P j √ (x i -x j ) 2 +(y i -y j ) 2 n(i,t) (1)
n(i, t) is the number of vehicles connected directly to i at instant t, where j is any vehicle that is connected to i.

Rule 2. To form a stable cluster, the cluster head should have similar mobility characteristics as the vehicles within its cluster. Indeed, if cluster heads are elected without taking speed into account, the number of vehicles that will quickly move out of communication range from their cluster head will increase. Thus, the vehicle whose current speed is the closest to the mean value is elected as the cluster head.

The average value of speed is:

ρ(i, t) = P j ν(j,t) n(i,t) (2)
ν(t, j) is the speed of vehicle j at instant t, where j is any vehicle that is in communication range of the cluster head candidate i.

Rule 3.

The formation of a high number of clusters increases the overhead and the inter-cluster interference and degrades the network performance. To overcome this, the cluster mechanism should group all vehicles in the network with a small number of cluster heads. Thus, we restrict the vehicle that has the maximum number of neighboring vehicles should be elected to act as the cluster head. However, this number i should be bounded by a capacity value β i which represents the maximum number of neighbors that vehicle i can optimally handle as a cluster head.

Rule 4. To provide a stable cluster structure, the cluster members should always remain within the transmission range of their cluster heads. Thus, the clustering protocol should take into consideration the mobility features of VANETs (e.g. multiple roads including road junctions, opposite-direction of the traffic flow).

Rule 4.1. The Mobility Direction (MD) is necessary information that can be used to form stable clusters. Indeed, the vehicles that are moving in different directions cannot remain within transmission range for a long period of time. Let us consider the VANET scenario shown in Figure 6.2. Vehicle v i can choose to join one of the two clusters y or n which are managed by the two vehicles v y and v n , respectively. If vehicle v i joins cluster y, it will quickly leave the cluster and it will need to choose another cluster head. However, if vehicle v i joins cluster n, they will both be moving in the left hand direction and as a result it will remain a member of this cluster for a longer period of time.

Rule 4.2. The mobility direction is not always sufficient to insure clustering stability in VANETs. As shown in Figure 6.2, based on the mobility direction metric the vehicle v j can join cluster k managed by the vehicle v k because they are moving on the same direction. However, they are not moving on the same road and vehicle v k may need to change its status and choose a new cluster head if the distance between the two roads becomes greater than the communication range of the cluster head.

Moreover, based on the definitions of the mobility directions given in [START_REF] Omar | VeMAC: A TDMA-Based MAC Protocol for Reliable Broadcast in VANETs[END_REF], the two vehicles v i and v j are considered to be moving in the same "left" direction and thus these vehicles can be grouped together to form a cluster. Since the two vehicles are not moving on the same road, vehicle v i will be out of the cluster j after a short period of time and it will need to join a new cluster. Thus, the Road ID (RID) is critical information to provide a more stable cluster structure and to reduce the average number of times a vehicle must change clusters. In this chapter, we impose that each vehicle only considers neighboring vehicles that are moving on the same road and in the same direction, and ignores control messages from vehicles on a different road and moving in the opposite direction. As a result, these protocols do not create a stable clustering architecture. Some of these proposed protocols are described below.

In [START_REF] Almalag | Using Traffic Flow for Cluster Formation in Vehicular Ad-hoc Networks[END_REF], the authors propose a lane-based clustering algorithm, named Traffic Flow, designed to extend the cluster lifetime and reduce the communication overhead. The cluster head is selected based on the lane where most of the vehicles will flow. The authors suppose that each vehicle knows its exact lane on the road via a lane detection system and an in-depth digital street map that includes lane information. A Lane Weight (LW) metric is applied for each traffic flow in order to select the most stable cluster head. The clustering algorithm involves only the cluster formation phase where all vehicles are assumed to follow a steady roadway and does not involve a cluster maintenance phase where the vehicles change their directions or lanes. An Adaptable Mobility-Aware Clustering Algorithm based on Destination positions, called AMACAD, is proposed and evaluated by Morales et al. [START_REF] Morales | An adaptable mobility aware clustering algorithm in vehicular networks[END_REF]. The goal of this work has been to develop a clustering protocol with an efficient message exchange mechanism, which improves the clustering stability in VANETs. AMACAD Table 6.1 compares the features of these protocols. It is clear from this table that while all of these protocols satisfy certain of these rules, none of them satisfies all of them. As result, these protocols may not work efficiently in VANET network.

In addition, the behavior of these clustering protocols is highly influenced by small changes in the set of their configuration parameters such as cluster size, hello interval, election interval, timeout interval, etc.). Moreover, the authors do not provide guidelines to tune and optimize them for various mobility scenarios. Therefore, finding the best setting of parameters for optimally configuring these protocols is a major issue.

That is why, this chapter proposes on the one hand two cluster protocols specifically designed for VANET which takes mobility information into account in order to provide stable clusters with a long lifetime and on the other hand a multi-objective formalization of the parameter tuning problem of our proposed clustering protocols.

An adaptive weighted clustering protocol 6.4.1 System model

Our protocol is based on the assumption that each vehicle in a VANET can know its road ID via a digital road map and a positioning system, e.g. GPS (Global Positioning System) or a GALLILEO receiver that also allows it to obtain an accurate real-time three-dimensional geographic position (latitude, longitude and altitude), direction, speed and exact time. In this section, we present the cluster setup and maintenance mechanisms of AWCP in detail.

Cluster head election

Initially, all vehicles are in the Undecided State (US). To divide the network into clusters, each active vehicle changes its state to Cluster Head Candidate (CHC) and it starts to broadcast a HELLO message periodically containing all the necessary information V ID, RID, M D, position, speed to its One-Hop neighbors (OH). In order to form stable clusters, each vehicle uses RID and MD to filter out any vehicle that is moving on another road or in the opposite direction. Upon reception of a HELLO message from all its one-hop neighbors, each vehicle i calculates its current weight W (i, t) using the following normalized function (3). The weight function consists of three parts, i.e., average-distance weight factor (1), average-speed weight factor (2), number of neighbors weight factor.

ω(i, t) = w 1 * δ(i,t) τ + w 2 * |ν(i,t)-ρ(i,t)| ϑ -w 3 * n(i,t) ψ (3)
Where w 1 , w 2 and w 3 are the balancing factors such that 3 k=1 w k = 1, τ is the maximum radius of the vehicles, ϑ is the maximum allowed speed on the highway and ψ is the cluster size. We note that the three weight factors are in conflict.

For simplicity, we assume that all the factors should be minimized. In fact, the multiplication of the third weight factor by (-1) allows us to transform a maximization to minimization. Then, each node i broadcasts a beacon message containing all the necessary information for the CH election algorithm V ID, RID, M D, W, CH -ID .

Vehicle i announces itself as a CH by assigning its own ID to the CH-ID field of the election beacon. When a vehicle i receives beacons from its one-hop neighbors, it sorts its neighbor list OH i according to the weights received in the beacons, and then it executes the cluster head election algorithm to change its status from CH to Cluster Member (CM), Cluster Gateway (CG) or remain CH.

W (i, t) = {min W (j, t) ∀ j ∈ OH i } (4), n(i, t) ≤ β i (5)
The vehicle i that satisfies the two properties (4) and ( 5) at instant t is elected as the CH. Then, all vehicles that are within transmission range of the CH become CMs or CGs and are not allowed to participate in another cluster head election procedure.

The CH election algorithm terminates once all the vehicles either become a CH, CM or a CG. Algorithm 6 outlines the details of the CH nodes' election. It is executed by each vehicle i having at least one neighboring vehicle. In Algorithm 6, i, j, and x represent three vehicles which are moving in the same road and on the same direction and are participating in the CH election process, timer 1 , timer 2 and timer 3 are three timers. In addition, ITJ Interval is the time interval for a CH vehicle to broadcast the Invite-To-Join (ITJ) message, PRE Interval is the time interval for a CM to signal its presence to its CH, while CH Timeout Interval is the time interval for a vehicle to elect itself as a CH, if it did not receive any ITJ messages during this period.

Cluster maintenance

In VANETs, a vehicle can join or leave a cluster at any time. These two operations will have only local effects on the topology of the cluster if the vehicle is a CM. However, if the vehicle is the CH, it must hand over the responsibility to one of the very close cluster members before leaving the cluster. The first reason for that is to maintain the cluster structure even if the current CH leaves. The second reason Algorithm 6 Cluster head election

1: S i ← CHC 2: OH i ← ∅ 3: while timer 1 ! = 0 do 4:
Upon reception of election beacon form vehicle j, vehicle i will check:

5:
if j is traveling in the same highway and in the direction then 6:

Receive and store W j value The vehicle i sorts its OH i list

13: v ← head of OH i 14: if (i == v) then 15: S i ←CH 16:
for every ITJ Interval second do 17:

Vehicle i broadcasts an ITJ message i sends an RTJ message to v 28:

while timer 3 ! = 0 do 29:

if i receives an ACK from v then 30:

S i ←CM

Clusters merging

When two or more CHs moving on the same highway and in the same direction receive an ITJ messages from each other with a signal strength greater than the predefined threshold Pr Threshold, only one of them will keep its CH responsibility while the others will switch to a CM. The CG between clusters becomes CM of the new cluster, and each CM whose CH has become a CM will remain a CM if it receives an ITJ message from the new CH, and will switch to CHC otherwise. The selection of a cluster head for merging clusters is done based on the weight W (i, t). The performance of AWCP depends on the selection of the parameter settings that determine its behavior. For instance, the detection of topological changes can be adjusted by changing the Hello Interval parameter. We have defined a solution vector of real variables that can be fine tuned by using an optimization technique with the aim of obtaining QoS efficient AWCP configuration. Table 6.

) R 0 1 -w 2 Neig Weight factor (w 3 ) R 0 1 -(w 1 + w 2 )
A given AWCP configuration is evaluated based on three of the most widely used QoS metrics in this area [START_REF] Rawashdeh | A novel algorithm to form stable clusters in vehicular ad hoc networks on highways[END_REF]: The Average Cluster Lifetime (ACL), which is the average time period from the moment when a vehicle becomes a CH, CM or CG to the time when it changes its state. The Control Packet Overhead (CPO), which is the rate of AWCP control packets used to form and maintain the cluster structures.

And finally, the Packet Delivery Ratio (PDR), which is the ratio of the number of data packets that are correctly delivered to their destinations. heuristic algorithms to optimize the QoS of the AODV protocol [START_REF] Garcìa-Nieto | Automatic parameter tuning with metaheuristics of the AODV routing protocol for vehicular ad-hoc networks[END_REF] and a file transfer protocol [START_REF] Garcìa-Nieto | Automatic tuning of communication protocols for vehicular ad hoc networks using metaheuristics[END_REF] in realistic VANET scenarios. In [START_REF] Abdou | Using an evolutionary algorithm to optimize the broadcasting methods in mobile ad hoc networks[END_REF] and [START_REF] Pèrez | Multi-objective Algorithms to Optimize Broadcasting Parameters in Mobile Ad-hoc Networks[END_REF], different multiobjective optimization algorithms are proposed to find an optimal parameter set for broadcasting methods in MANETs. Recently, Iturriaga et al. [START_REF] Iturriaga | A Parallel Multi-objective Local Search for AEDB Protocol Tuning[END_REF] presented a novel and a network simulator ns-2 to determine the optimal parameters of AWCP.

6.5 NSGA-II based approach for AWCP optimization 6.5.1 Overview of NSGA-II Optimizing a group of conflicting objective functions is no simple task. For simplicity, we assume that all objective functions should be minimized. In fact, the multiplication of some objective functions by -1 allows one to transform a maximization to minimization. Thus, the Multi-objective Optimization Problem (MOP) can be formulated as follows:

(M OP )        min f k ( - → x ), k = 1, . . . , m s.t lower(x i ) ≤ x i ≤ upper(x i ), i = 1, . . . , n
The vector -→ x = (x 1 , . . . , x n ) T ∈ S is the vector of n decision variables. The lower(x i )

and upper(x i ) are respectively the lower and upper bounds of the variable x i . These bounds define the decision space S. Let a minimization MOP be a solution -→ x i ∈ S which dominates the solution -→ x j ∈ S (it is denoted by -→ x i ≺ -→ x j ) if the following conditions are satisfied:

i) f k ( - → x i )) ≤ f k ( - → x j ) ∀ k ∈ {1, . . . , m} ii) ∃ k ∈ {1, . . . , m} such that f k ( - → x i ) < f k ( - → x j )
The set of optimal solutions is composed of the non-dominated vectors, often called the Pareto front and also denoted

P F * = { - → x ∈ S | - → x ∈ X, - → x ≺ - → x }.
In other words, the Pareto front is the set of compromise solutions. The goal of the multiobjective optimization is to find the Pareto front for a given problem. The NSGA-II algorithm [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF] is often used to solve the multi-objective optimization problem. This method is a multi-objective version of the genetic algorithm in which the solutions explored are classified into Pareto-optimal fronts.

Proposed approach

The proposed approach is based on the NSGA-optimization tool, a network simulator and the ns-2 trace analyzer (see Figure 6.5). These three modules cooperate to determine the optimal AWCP configuration in different mobility scenarios. Firstly, the optimization tool generates a set of possible parameters which are transmitted to the network simulator. Thereafter, the simulations are launched and the trace file is built. This file is passed on to the third module (trace analyzer) which computes the values of the fitness functions. The calculated objective values are then transmitted to the optimization tool which evaluates and ranks the solutions according to these values. Then, the optimization tool runs its operations to regenerate another set of possible solutions. This process starts again, until the stop criterion is reached.

Below, we describe the NSGA-II based optimization tool.

As shown in Algorithm ranking(F i , crowding distance)

22:

Itr ← Itr + 1 their given intervals, the resulting vector should satisfy the formulated constraints in Section V. The two most used types of crossover operators are two-point crossover and uniform crossover. In this study, we found that the NSGA-II using uniform crossover outperforms the NSGA-II using two-point crossover in terms of the obtained children quality. In uniform crossover operator, a crossover mask -→ x = (x i ) T ∈ {0, 1} n is randomly computed, which determines from which parent vector each gene will inherit. Then, each gene i will be assigned to the first parent if x i = 1, otherwise it will be assigned to the second parent. After recombination, the mutation operator is applied to randomly change some genes in an individual. This operator serves as a strategy to prevent solutions from being trapped in local optima. After mutation, if one or more of the genes in any new individual j are outside of their ranges, the individual -→ x j is repaired according to the flowing rule:

(x j i ) 1≤i≤n =        lower(x i ) + x j i +lower(x i ) 2 if x j i < lower(x i ) lower(x i ) + x j i -upper(x i ) 2 if x j i > upper(x i ) x j i otherwise
Since the crossover and the mutation operator generate a list of new solution vectors, a set of ns-2 simulations are launched to compute the objective values.

Simulation results and performance evaluation

We carried out a set of experiments to prove the ability of NSGA-II coupled with the ns-2 simulator to provide optimal performances, as well as its ability to fine tune the optimal values of the AWCP parameters. The optimization tool was implemented in Java while the simulation phase was carried out by running ns-2.34. Moreover, all our experiments were conducted using 2 desktop computers Intel Core i5 3.2GHz with 4

Gb of memory and O.S. Linux Ubuntu 12.04. In order to achieve the best optimal behavior of the AWCP protocol, several experiments on various VANET scenarios were necessary. In this section, we present the set of VANET scenarios used to obtain efficient QoS AWCP parameters and the experimental validation.

VANET scenarios

We generated a realistic VANET environment by selecting a real highway area from a digital map which took into account road directions, road intersection, and traffic rules. To generate vehicular traffic by MOVE and SUMO, we defined for each di-

NSGA-II results analysis and validation

This section presents and analysis the results of applying NSGA-II for the AWCP tuning problem. For these results, the size of the initial population was 30 individuals, the number of generations was fixed to 40, the crossover probability was 0.9, whilst the mutation probability was fixed to 0.1. We perform 30 independent runs of the NSGA-II algorithm in which the candidate individuals were evaluated by running the simulation in the High scenario. The computational time for each run was 37618.95 seconds (about 10.45 hours) with a deviation of 6.78 (about 13 days for 30 independent runs). After the experimentation, we identified a set of Pareto optimal solutions of size τ = 79 by gathering all the non-dominated solutions found in the 30 independent runs. These solutions give different degrees of trade-offs between three QoS metrics and they are bounded by a so-called ideal objective vector z ideal which contains the optimal value for each separate objective.

(z ideal j [START_REF] Yetgin | Multi-objective routing optimization using evolutionary algorithms[END_REF] and [START_REF] Ali | Energy-efcient clustering in mobile adhoc networks using multi-objective particle swarm optimization[END_REF], respectively.

) 1≤j≤k = min f j ( - → x i ) ; i = 1, . . . , τ
The parameter settings of these optimization algorithms are shown in

The spacing metric (S).

It measures the distribution of solutions in the obtained P F set. It is proposed by Schott in [START_REF] Schott | Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization[END_REF] and defined as:

S = 1 τ τ i=1 (d i -d) 2 d i = min x (j) ∈P F ∧j =i m k=1 |f k (x (i) ) -f k (x (j) )|
Where τ is the size of the Pareto front obtained, m is the number of objectives, and

d = P τ i=1 d i τ
is the mean value of all d j . A small value for this metric means that all non-dominated solutions in P F set are nearly spaced. Thus, the best multi-objective algorithm is the one that provides P F set with minimum spacing value.

The spread metric (D).

It determines the maximum range achieved among the obtained non-dominated solutions. A high value of the spread metrics means that the non-dominated solutions are widely distributed of over the objective space. Thus, a higher value of D indicates a better algorithm performance. This metric is proposed by Ranjithan in [START_REF] Ranjithan | Constraint Method-Based Evolutionary Algorithm(CMEA) for Multi-objective Optimization[END_REF] and defined as:

D = m k=1 (max τ i=1 f k (x (i) ) -min τ i=1 f k (x (i) )) 2 x (i) ∈ PF, j = 1, 2, . . . , τ

Ratio of Non-dominated Individuals (RNI).

The performance measure determines the ratio of the number of the known solutions whose are chosen in Pareto front for a given population P . This metric is mathematically formulated as:

RN I = n |P |
Where n is the number of non-dominated solutions in population P , and |P | is the size of population. In the situation where RN I = 1, all individuals in the population are non-dominated. While RN I = 0 means that none of the known solutions in the population are non-dominated.

Generational Distance (GD).

The generational distance introduced by Veldhuizen [START_REF] Veldhuizen | Multiobjective Evolutionary Algorithm Research: A History and Analysis[END_REF] measures how far the obtained Pareto front P F from the true Pareto font P F * 1 by using the Euclidean distance between each member of P F and the nearest one from the P F * sets. 1 An assumption made in several research work is that the true Pareto front is a priori known.

In this paper, we build the true Pareto front from the best non-dominated solutions found by the three considered MOEAs after 15 independent runs.

GD(t) =

P τ i=1 d i τ d i = min μ j=1 m k=1 (f k (x (i) ) -f k (x (j) )) 2
where τ and μ are respectively the size of the P F and P F * set. The algorithm that provides Pareto fronts with small GD values is desirable. Secondly, the minimization of the number of the clusters reduces the amount of ITJ messages broadcasted by the cluster heads. respectively. We can note from this figure that AWCP causes the lowest number of transitions. For instance, vehicle 14 in Figure 6.12-left kept its sate throughout the simulation time when AWCP was used, while it changes its state 3, 4, 5 and 8 times when CPM, WCA, LID and HD were used, respectively. These results can be explained by the fact that AWCP avoids the problem of merging multiple clusters into a single cluster at road junctions.

Angle-based clustering algorithm

AWCP is based on the assumption that each vehicle is equipped with a digital mapping device, thus it can not operate in environments where vehicles without maps are present. In this section, we suppose now that the vehicles are not equipped with digital road map devices and thus they can not obtain the road IDs on which they The angle θ between two given velocity vectors is given by the following expression [START_REF] Tian | Position-based directional vehicular routing[END_REF]:

-→ OA. --→ OB = || -→ OA|| × || --→ OB|| × cos θ (1)
θ = arccos( ∆x 1 * ∆x 2 +∆y 1 * ∆y 2 √ ∆x 2 1 +∆y 2 1 * √ ∆x 2 2 +∆y 2 2 ) ( 2
) ∆x = x -x ∆y = ŷ -y
After receiving of a HELLO message from all each of its one-hop neighbors, vehicle i only considers neighbors that have an angular directions equal to θ i ± δ, where θ i is the angular direction of vehicle i and δ is an angular value that represents the range of angles in which two vehicles are considered to be moving in the same direction. The authors in [START_REF] Naumov | Connectivity-aware routing (car) in vehicular adhoc networks[END_REF] propose that two velocity vectors are non-parallel if the smallest angle between the vectors is higher than 18 • . Moreover, vehicle i ignores all HELLO messages broadcasted from neighbors that have non-parallel velocity vectors.

Therefore, the direction of the vehicle's velocity vectors can help to build a stable cluster structure by grouping only the vehicles that have parallel velocity vectors in the same cluster, as shown in Figure 6.15. In ACA, a vehicle remains in the CM state as long as it receives an ITJ and has an acute angle with its cluster head. As shown in Figure 6.16, when a cluster member CM1 leaves its cluster, it will create an obtuse angle with its cluster head CH1. At instant t + k, the cluster head removes a CM1 from its cluster members list if the angle between their velocity vectors is greater than φ. In order to highlight the efficiency of ACA algorithm, we evaluate and compare it with the AWCP protocol in VANET scenarios where vehicles without maps are present. Figure 6.17 shows the Average Cluster Lifetime (ACL) for ACA and AWCP.

These protocols are evaluated when we vary the number of vehicles which are not equipped with a digital map device between 20%, 40% and 50%. As ACA is an angle-based clustering algorithm, the presence of vehicles that do not have map does not influence its performance. Moreover, when all the vehicles in the network have a map, the ACA and AWCP protocols have almost the same average cluster lifetime.

However, we can note that the ACL metric decreases for AWCP as the number of vehicles that have no map increases. These results can be explained by the fact that, each map-unequipped vehicle that is in the US 2 state joins any cluster without taking into account any road ID.

Figure 6.17: Average cluster lifetime under various traffic densities.

Conclusion

The design of a stable clustering algorithm becomes an even more challenging difficult task in VANETs when there are many road segments and intersections. we have identified the essential features that the clustering protocols must satisfy to build stable clusters in VANETs. Our contribution in this chapter is threefold. Firstly, we proposed an optimized clustering protocol, called AWCP, whose objective is to maximize the lifetime of the cluster heads and cluster members with a low control overhead. AWCP is a map-and GPS-based approach which takes advantage of knowing the road ID and the direction in which the vehicles are traveling. Our method of selecting cluster heads based on mobility features and a weight function is the key to achieving a more stable cluster. Secondly, due to the high number of feasible configurations of AWCP and the conflicting nature of its performance metrics, we formulated The focus of the next chapter will be the coordinator-based TDMA scheduling mechanisms in which an RSU in a centralized topology or the cluster head in a hierarchical topology is used as a local channel coordinator for the vehicles within its communication range. The clustering protocol that we have designed will be used with a TDMA scheme in the following of this work.

Introduction

Improving road safety is among the main objectives of VANETs design. This objective requires a reliable broadcast scheme with minimum access delay and transmission collisions, which increase the need for an efficient TDMA-based MAC protocol.

However, as the size of the VANET grows, the distributed TDMA slot scheduling algorithm produces a significant communication overhead to create and to maintain the TDMA schedules in highly dense networks. Moreover, the access collision problem frequently occurs in this category between vehicles trying to access the same time

slots. An effective solution to reduce the scheduling overhead as well as the access collision rate consists in using central coordinators to schedule and maintain time slot assignment for the vehicles in their coverage area. In this chapter, we focus on two types of TDMA-based MAC protocol: an infrastructure-assisted and a cluster-based TDMA MAC protocol. vehicle v randomly reserves a temporary time slot, say slot k.

5:

vehicle v sends a SREQ to RSU u during the time slot k. Moreover, when an RSU does not receive a message from a vehicle v during its slot, it considers that it has left its coverage area and it releases its time slot. Algorithm 9 outlines the behavior of our scheme during the procedure of slot scheduling at the RSU.

Algorithm 9 Slot scheduling procedure executed at each RSU 1: Input:

2: S j : The set of time slots managed by the RSU u. u broadcasts an SA message. u allocates the slot k to vehicle v.

9:

u sends a SREP to vehicle v. As defined in [START_REF] Zhuang | VeMAC: A novel multichannel MAC protocol for vehicular ad hoc networks[END_REF], in order to avoid the merging collision problem, we assume that the BS period in each frame is partitioned into two sets of time slots, left and right. The Left set is associated with vehicles moving in the left direction, while the Right set is associated with vehicles moving in the right direction. The CRP uses CSMA/CA as its channel access scheme. During the CRP, each vehicle that wishes to access the channel can send a slot reservation request to the cluster head CH to reserve a periodic time slot. Moreover, we assume that each set of time slots Right and Left is partitioned into three subsets of time slots: S 0 , S 1 and S 2 , as shown in Figure 7.5.

• S 0 is the set of time slots reserved for vehicles belonging to set A.

• S 1 is the set of time slots reserved for vehicles belonging to set B. • S 2 is the set of unused time slots, in which no vehicle within the cluster can access the channel.

ASAS description

Every vehicle should be allocated a fixed slot in the frame for safety messages or other control packet transmissions. It is obvious that a vehicle's slot cannot be used by any vehicles in the same cluster or within neighboring clusters, otherwise the inter-cluster interference problem will occur. As a result, the three sets of time slots are reused in ASAS between clusters in such a way that no vehicles in different neighboring clusters can access the channel at the same time.

In this section, we provide a detailed description of the proposed TDMA slot allocation strategy. When a CM vehicle needs to access the channel, it first sends a slot reservation request during the CR period to the cluster head for a periodic time slot. When the CH receives the reservation request, it will allocate to CM the first available slot to the CM as its owner slot in set S 0 or S 1 according to the CM's position included in the request message. Each CH determines its time slot allocation map according to the maps of their neighboring clusters obtained through the cluster gateways. Once a CH has allocated a time slot to a CM, it sends a reservation reply which includes the slot identifier. In ASAS, each CH constructs and maintains a Frame Information (FI) which contains the following fields: • Time slot allocation map: (S 0 , S 1 , S 2 ), (S 1 , S 2 , S 0 )or(S 2 , S 0 , S 1 ).

• Slot state: a vector of length equal to the number of time slots per frame containing the status of each slot which indicates whether the slot is Idle, Busy or in Collision.

After receiving the reservation reply from the CH, the CM keeps access to the same time slot on all subsequent frames unless it leaves its cluster or a collision problem occurs. Moreover, after a specific time interval, if the CH does not receive a beacon message from a CM during its slot, it considers that it has left its cluster and then the CH immediately releases the time slot and it removes the member from its cluster members list (i.e. the A or B set). Therefore, by using a cluster-based approach, we change the slot allocation process from random reservations to optimal allocations, which can improve the convergence performance of the MAC protocol and achieve an efficient broadcast service for the successful delivery of real-time safety information. Unlike the distributed TDMA scheduling algorithms where each vehicle needs to periodically broadcast its frame information to maintain its schedule vector, in ASAS, only the CHs periodically broadcasts its FI and each vehicle will update its FI based on the packet transmitted by its CH. Let us consider the VANET scenario shown in Figure ??. Table 7. We have used a parameter, called RSU Coverage Occupancy (RCO) [START_REF] Omar | Evaluation of VeMAC for V2V and V2R Communications under Unbalanced Vehicle Traffic[END_REF], equal to

N v × 2R L h × 2
τ in a highway scenario, where N v is the total number of active vehicles, R is the communication range and L h is the length of the section of the highway.

CTMAC is evaluated with the following metrics:

1. The access collision rate: the average number of access collisions per slot per RSU coverage area.

2. The merging collision rate: the average number of merging collisions per slot per RSU coverage area.

3. The packet loss rate: the average of the total number of vehicles that do not successfully receive messages divided by the total number of vehicles within communication range of the transmitter.

4. Overhead: the number of control packets used to allocate a time slot as well as to maintain the TDMA schedules. Occupancy (RCO). We can note from this figure that CTMAC produces fewer merging collisions than ADHOC MAC and VeMAC even for a high RCO. This is because CTMAC separates neighboring RSU areas by assigning disjoint sets of time slots to vehicles traveling in these areas. However, in VeMAC, the vehicles that cannot access a time slot from the set of slots reserved for their direction, will attempt to access any available time slot reserved for vehicles moving in the opposite direction. As a result, the merging-collisions occur frequently in VeMAC when traffic density is high, especially when the number of vehicles in each direction is not equal. However, these results might well be expected for the ADHOC MAC protocol since all vehicles randomly acquire a time slot in the frame without considering which direction they are moving in, which could make it susceptible to the merging collisions problem in highway scenarios where the vehicles are moving in opposite directions. show approximately 103.4% and 90.1% higher rates of packet loss than the CTMAC protocol, respectively. The rate of access collisions under different traffic densities is shown in Figure 7.12.

We can note that the CTMAC protocol generates a lower rate of access collisions than DTMAC, especially for a high traffic load. For instance, at a AO = 0.8, the CTMAC protocol achieves an access collision rate of 1.158%, in contrast to DTMAC which shows a rate of 1.531% (i.e. approximately 32.2% higher than DTMAC). The reason is that the assignment of time slots to vehicles is performed by the RSUs in a centralized manner. Moreover, CTMAC implements an Access Collision Avoidance mechanism that can prevent the access collision problem occurring more than twice between the same vehicles that are trying to access the channel at the same time. Chapter 8

Conclusion and Perspectives

Synthesis

Improving the safety of drivers and passengers on the road forms the main objective of the design of VANETs. Through V2V and V2R communications, VANETs can support a wide range of road safety applications such as cooperative collision warning, emergency braking, cooperative driving, and accident detection. Most of these applications, if not all, require an efficient and reliable broadcast mechanism in order to inform neighboring drivers about a dangerous situation in a timely manner. MAC protocols play a primary role in providing efficient delivery and while minimizing data packet loss. However, one of the major challenges of vehicular networks is designing an efficient MAC protocol which can cope with the hidden node problem, the high speed of the vehicles, the frequent changes in topology, the lack of an infrastructure, and QoS requirements of VANET safety applications. This thesis has provided three discussed some open issues that need to be tackled in future studies in order to improve the performance of TDMA in VANET.

In Part II, we tackled, the problem of periodic broadcast of safety messages in an infrastructure-free vehicular environment. We proposed a completely distributed TDMA scheduling scheme, named DTMAC, which exploits the linear topology of We then extended DTMAC to the context of safety and critical communications using multi-hop and V2V communications. To do so, we proposed a TDMA-aware Routing Protocol for Multi-hop VANETs, called TRPM. As in traditional routing protocols, TRPM provides multi-hop communication capabilities by using intermediate "relay" vehicles that are moving between the sender and receiver. The routing scheme is based on a cross-layer approach between MAC and the routing layer, in Although distributed-TDMA based MAC protocols can provide deterministic access time without collisions, these protocols generate a significant rate of overhead to create and to maintain the TDMA schedules in highly dense networks. Moreover, the access collision problem may frequently occur between vehicles trying to access the same time slots when a distributed scheduling scheme is used. Thus in Part III, we tackled , centralized environments where the RSUs were used to assign time slots to the vehicles within their communication range. We proposed a centralized TDMAbased MAC protocol, named CTMAC. Here, the slots are reused between the RSU's coverage areas in such a way that no interference problem will occur between vehicles in the overlapping regions. In addition, CTMAC implements an access collision avoidance mechanism that can prevent the access collision problem occurring more than twice between the same vehicles that are trying to access the channel at the same time. Simulations were conducted to evaluate the performance of this protocol in terms of several performance metrics. The simulation results show that, compared to the VeMAC and ADHOC MAC protocols, CTMAC has succeeded in providing a lower rate of access and merging collisions as well as the overhead required to create and maintain the TDMA schedules. However, fast moving vehicles will need to compute for new slots after a short period of time when they leave their current RSUs areas, which makes the scheduling operation very expensive if it is carried out in a centralized way.

An effective and cheap solution to address this issue consists in establishing a hierarchical clustering structure within the network where one vehicle in each group is elected to create and maintain a slot assignment schedule. As a result, the vehicles remain connected with their channel coordinator for a long period of time. However, designing a clustering algorithm is a daunting task in VANETs when there are many road segments and intersections. That is why we proposed an adaptive weighted clustering protocol called AWCP. This protocol is a road map dependent and uses road IDs and the vehicles' directions in order to make the clusters' structure as stable as possible. Due to the high number of feasible configurations of AWCP and the conflicting nature of its performance metrics, we formulated the AWCP parameter tuning as a multi-objective problem and we proposed an optimization tool which combines a non-dominated sorting genetic algorithm NSGA-II and the network simulator ns-2 to find the optimal parameters of AWCP that optimize its QoS. The simulation results

have confirmed the efficiency of our clustering protocol compared to the well-known protocols WCA, LID, HD. This is also the case when AWCP is compared to another protocol, CPM, which considers both the vehicles' positions and the directions.

Since AWCP is based on the assumption that each vehicle is equipped with a digital mapping device, it can not operate in environments where vehicles without maps are present. Hence, we proposed an improvement of AWCP called ASA which uses the angle between the velocity vectors of vehicles as a parameter to form stable clusters. The simulation results reveal that the enhanced technique significantly outperforms the AWCP protocol in VANET scenarios where vehicles without maps are present. Finally, we proposed ASAS, an adaptive slot assignment strategy for a cluster-based TDMA MAC protocol. This strategy is based on a cross-layer approach involving TDMA and AWCP in which some vehicles are elected to act as local channel coordinators for the vehicles within their clusters. The main goal of this work was to propose a new way to overcome the inter-cluster interference issue in overlapping areas by using vehicles' locations and directions when the slots are assigned by the cluster heads.

Perspectives

The TDMA based MAC and the routing protocols proposed in this manuscript have shown a very good performance. Nevertheless, several future research directions could be followed in order to improve these protocols, enabling them to perform better in realistic mobility scenarios.

Consideration of multiple MAC metrics

Unfortunately, DTMAC and CTMAC protocols are designed to achieve less transmission delay for safety applications at the expense of other MAC performance metrics.

However, fairness and stability are also critical performance metrics for complex applications such as multimedia applications (e.g., video/audio). Future MAC protocols should be able to achieve an optimal tradeoff between MAC performance metrics, which is a challenging task.

Wide range of applications

VANETs are also designed to provide drivers with services such as Internet connection. However, DTMAC and CTMAC have been developed for time-critical applications which need to broadcast messages between neighboring vehicles in a timely manner. They are devoted to specific applications and they are not able to support the wide range of applications envisioned. This would require a MAC protocol that can provide a bounded access delay for safety applications while providing wireless data transmission with appropriate data rates for non-safety applications. Research results in this field do exist but they are not completely satisfactory.

Reserved versus random access

ASAS divide a frame into two periods or phases. The random access period is based on CSMA/CA which is used by vehicles to communicate with a coordinator in order to obtain a time slot during the second period. The reserved period is based on the TDMA method, in which the scheduled nodes can send their data. Therefore, it is guaranteed that each vehicle can send its data messages in this phase without colliding with reservation messages sent in the random access period. The first period is necessary to create the TDMA slot reservation schedule. However, the varying vehicular densities caused by high node mobility has an important impact on the behavior of the ASAS protocol. This is because when there is high vehicle density, too short a length of the random access period will degrade the performance of these protocols. On the other hand, too great a length of this period will lead to unfair channel access for the vehicles. Hence, in order to ensure the stability of a MAC protocol, the length of the random access period should be dynamically adjusted according to vehicle density.

Multichannel operation

In order to increase throughput and support a wide range of applications in VANETs, the FCC [16] has established the DSRC service on the frequency band of 5.9 GHz divided into seven channels. However, the MAC protocols we have proposed can not make use of the seven DSRC channels and are limited to using only a single channel.

Therefore, in order to make them more scalable, it is necessary to expand them to use all seven channels without adjacent channel interference.

Mobility scenario

DTMAC, CTMAC and TRPM have been designed for highway scenarios and fail to take into account the different traffic conditions in urban scenarios where there are junctions, buildings, tunnels, traffic lights, etc. Future MAC protocols must be able to operate in both highway and urban scenarios.

3. 1 4 . 2

 142 Classification of TDMA-based MAC protocols . . . . . . . . . . . . . 3.2 The concept of time division multiple access . . . . . . . . . . . . . . 3.3 Collision with two-hop neighbors on a specific service channel . . . . 3.4 Access collision problem . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Merging collision problem . . . . . . . . . . . . . . . . . . . . . . . . 3.6 SOFT MAC frame structure [75] . . . . . . . . . . . . . . . . . . . . 3.7 Architecture of DMMAC . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Partitioning of each frame into three sets . . . . . . . . . . . . . . . . 3.9 Slot management mechanism in ATSA . . . . . . . . . . . . . . . . . 3.10 Access collision problem . . . . . . . . . . . . . . . . . . . . . . . . . 3.11 TDMA frame structure . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 TDMA frames in the CRC channel . . . . . . . . . . . . . . . . . . . 3.13 TDMA and MAC-layer frames in the CBT protocol . . . . . . . . . . 3.14 TDMA frame structure of the ACFM protocol . . . . . . . . . . . . . 3.15 Frequency assignment in ACFM . . . . . . . . . . . . . . . . . . . . . 3.16 Number of protocols versus MAC QoS metrics supported . . . . . . . 3.17 Number of protocols versus number of MAC QoS metrics supported . 3.18 Number of protocols versus MAC protocol design issues . . . . . . . . 3.19 Number of times of each MAC issue addressed for each year . . . . . 3.20 Percentage of TDMA-based MAC protocols (in each class) addressing a given MAC QoS metrics . . . . . . . . . . . . . . . . . . . . . . . . 3.21 Number of TDMA-based MAC protocols proposed for each years . . 4.1 TDMA slots scheduling principle. . . . . . . . . . . . . . . . . . . . . xii LIST OF FIGURES xiii Frame information (FI) structure. . . . . . . . . . . . . . . . . . . . . 4.3 VANET mobility scenario . . . . . . . . . . . . . . . . . . . . . . . . 4.4 The access collision probability for σ = 20 (left) and σ = 30 (right). . 4.5 The access collision probability for σ = 50. . . . . . . . . . . . . . . . 4.6 The rate of merging collision. . . . . . . . . . . . . . . . . . . . . . . 4.7 The rate of access collision. . . . . . . . . . . . . . . . . . . . . . . . 4.8 The rate of packet loss under various traffic densities. . . . . . . . . . 4.9 The coverage broadcast ratio under various traffic densities. . . . . . 5.1 VANET network using random TDMA scheduling scheme. . . . . . . 5.2 VANET network using DTMAC scheduling scheme. . . . . . . . . . . 5.3 Message propagation based on TDMA slot information. . . . . . . . . 5.4 Simulation framework. . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 San Jose (California) urban area captured from Google Maps (left) and exported to a VANET network topology by using MOVE/SUMO (right).102 5.6 Effect of changing α on average end-to-end delay. . . . . . . . . . . . 5.7 Effect of changing α on average number of hops. . . . . . . . . . . . . 5.8 The average end-to-end delay vs source-to-destination distance. . . . 5.9 The average number of relay vehicles vs source-to-destination distance. 5.10 The average end-to-end delay vs vehicle density. . . . . . . . . . . . . 5.11 The average number of relay vehicles vs vehicle density. . . . . . . . . 5.12 The average delivery ratio vs vehicle density. . . . . . . . . . . . . . . 6.1 Mobility direction based clustering . . . . . . . . . . . . . . . . . . . 6.2 Road-based clustering . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Vehicle state transition diagram . . . . . . . . . . . . . . . . . . . . . 6.4 Distribution of solutions on the objective space. . . . . . . . . . . . . 6.5 NSGA-II based approach for AWCP optimization. . . . . . . . . . . . 6.6 Uniform crossover operator example. . . . . . . . . . . . . . . . . . . 6.7 3D Pareto fronts returned by the NSGA-II, MOPSO and MODE algorithms for the S1 and S3 VANET scenario. . . . . . . . . . . . . . . . 6.8 ACL results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.9 CPO results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.10 PDR results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.11 The US average duration . . . . . . . . . . . . . . . . . . . . . . . . . 6.12 The number of vehicles' state transitions for the two scenarios S3 (left) and S4 (right). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.13 The eight basic directions and their ranges at a 4-road junction. . . . 6.14 Moving direction angle calculation. . . . . . . . . . . . . . . . . . . . 6.15 Angle-based Clustering. . . . . . . . . . . . . . . . . . . . . . . . . . 6.16 Highway exit scenario. . . . . . . . . . . . . . . . . . . . . . . . . . . 6.17 Average cluster lifetime under various traffic densities. . . . . . . . . 7.1 TDMA slots scheduling mechanism of CTMAC . . . . . . . . . . . . 7.2 Frame information (FI) structure. . . . . . . . . . . . . . . . . . . . . 7.3 Access collision avoidance. . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Network model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. 1 4 . 1 5 . 1 4 6 7 . 1

 141514671 Regional standards for DSRC . . . . . . . . . . . . . . . . . . . . . . 3.1 Comparison of contention-based and TDMA-based MAC protocols in high load conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Qualitative comparison of TDMA-based MAC protocols in flat-based network topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Channel allocation and MAC protocols used by CBMMAC scheme . 3.4 Qualitative comparison of TDMA-based MAC protocols in clusterbased network topology . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Qualitative comparison of TDMA-based MAC protocols in centralized network topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Comparison of different categories of TDMA-based MAC protocols . Simulation parameters . . . . . . . . . . . . . . . . . . . . . . . . . . Simulation parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Comparison of clustering protocols . . . . . . . . . . . . . . . . . . . 6.2 AWCP parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 VANETs scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.Simulation parameters in ns-2 . . . . . . . . . . . . . . . . . . . . . . 6.5 NSGA-II simulation results and optimized configuration . . . . . . . . 6.Parameter settings of the optimization algorithms . . . . . . . . . . . 6.7 Performance comparison of the three MOEAs for the S1, S2, S3 and S4 scenarios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The slot assignment obtained with ASAS . . . . . . . . . . . . . . . . xv Chapter 1

2. Contribution 2 : 3 .

 23 Fully distributed TDMA-based MAC protocol for reliable broadcast of periodic messages in VANETs This part of the thesis focuses on designing a novel distributed and locationbased TDMA scheduling scheme for VANETs, named DTMAC which exploits the linear topology of VANETs. The main goal of this work is to propose a MAC protocol that can provide a reliable broadcast service with bounded access delay. Our distributed TDMA scheduling mechanism uses geographic positions and a new slot reuse concept to ensure that vehicles in adjacent areas have a collision-free schedule. The simulation results confirm the efficiency of our proposal in terms of transmission collisions and broadcast coverage. Contribution 3: TDMA-aware routing protocol for multi-hop communications in VANETs

6 . 7 .

 67 Contribution 6: Centralized TDMA-based scheduling algorithm for real-Time communications in VANET networks Vehicular networks are usually dense and the high number of vehicles may not be well handled by a distributed scheduling solution. As the size of the VANET grows, the distributed TDMA slot scheduling algorithm produces more communication overhead to create and maintain the TDMA schedules. Moreover, in highly dense networks, the access collision problem occurs frequently between vehicles trying to access the same time slots. Therefore, we propose CTMAC, a centralized TDMA-based MAC protocol for real-time communications in VANET. CTMAC uses Road Side Units (RSUs) as central coordinators to schedule and maintain time slot assignment for the vehicles in their coverage areas. The simulation results reveal that CTMAC significantly outperforms distributed TDMA based MAC protocols in terms of transmission collisions and scheduling overhead. Contribution 7: Adaptive slot assignment strategy in cluster-based VANETs When a centralized scheduling scheme is used, each vehicle keeps accessing the same time slot on all subsequent frames unless it enters another area covered by another RSU. Thus it will need to acquire a new time slot very rapidly which makes a centralized scheduling operation very expensive. A great deal of attention has been paid to TDMA protocols where one vehicle in each group is elected to create and maintain a slot assignment schedule. As a result, the vehicles remain connected with their channel coordinator for a long period of time. This leads us to design a cluster-based adaptive slot assignment strategy, called ASAS. It is based on the AWCP protocol in which the cluster heads are used to assign disjoint sets of time slots to the members of their clusters.

2 . 3 .

 23 Part II: Distributed TDMA scheduling and routing in multi-hop wireless vehicular ad hoc networks In Chapter 4, we present the design of our fully Distributed TDMA based MAC protocol (DTMAC) which provides an efficient delivery of both periodic and event-driven safety messages. Simulation results are provided to evaluate the performance of our protocol. This work corresponds to Contribution 2. Chapter 5 develops our TDMA-aware routing protocol for multi-hop communication, called TRPM. Moreover, we give a theoretical estimation of the end-to-end delay needed to deliver one message from a source vehicle to a destination vehicle. This corresponds to Contribution 3. Part III: Coordinator-based TDMA Scheduling solution in Hierarchical as well as in Centralized VANET Network Topologies Chapter 6 develops our two proposed clustering protocols. This first is AWCP, an adaptive weighted clustering protocol whose objective is to maximize the lifetime of the cluster heads and cluster members. AWCP is a map-and GPSbased approach which takes advantage of knowing the road ID and the direction in which the vehicles are traveling. The second is ACA, Angle-based Clustering Algorithm which uses the angle between the velocity vectors of vehicles as a parameter to form stable clusters. We compare the performance of AWCP and ACA with other well-known clustering protocols proposed in the literature, This corresponds to Contribution 4. Moreover, we formulate the AWCP parameters tuning as a multi-objective problem which corresponds to Contribution 5 and

Figure 2 .

 2 1 shows the possible domains that a VANET network consists of. These include the Ad hoc, infrastructure and Internet domains. This figure also shows the different forms of communication in such networks: inter-vehicle communication V2V 3 , in which the vehicles can communicate with each other in an ad hoc fashion, vehicle-to-roadside communication V2I 4 , where the RSUs 5 are used as access points to connect moving vehicles to the network in-1 Local Area Network 2 Mobile Ad hoc NETworks 3 Vehicle To Vehicle 4 Vehicle To Infrastructure 5 Road Side Units frastructure which is connected to the Internet [5], and hybrid communication that combines between two types of previous communications. Moreover, a vehicle can communicate with the Internet directly through Hotspot devices installed along the road. Each vehicle is equipped with two devices: an On Board Unit (OBU), and an Application Unit (AU). The OBU is used to exchange information with RSUs or with other OBUs in the ad hoc domain, whereas the AU executes applications that can use the communication capabilities of the OBU.

Figure 2 . 1 :

 21 Figure 2.1: An overview of a VANET network

Figure 2 . 2 :

 22 Figure 2.2: An example of road map.

Figure 2 .

 2 4 shows another safety application: when a vehicle breaks suddenly, it broadcasts information about its current status (i.e., position, speed, deceleration, etc.), which is used by the surrounding vehicles to quickly detect the sudden braking.

Figure 2 . 3 :

 23 Figure 2.3: An accident detection by using V2V communication.

Figure 2 . 4 :

 24 Figure 2.4: Emergency brake warning.

Figure 2 . 5 :

 25 Figure 2.5: Channel assignment in DSRC

  by industry, launched in the summer of 2002 by European vehicle manufacturers. C2C-CC cooperates closely with the ITS group of ETSI and the ISO/TC 204 on the specification of the ITS European and ISO standards. The main goal of the C2C-CC Communication Consortium is to enable wireless communications between vehicles and their environment, which may be other vehicles or RSUs, in order to improve driving safety and traffic efficiency and provide information or entertainment services to the driver. Several other research projects have been created to design efficient communication protocols related to the environment of vehicular networks.

Figure 3 . 1 :

 31 Figure 3.1: Classification of TDMA-based MAC protocols

Figure 3 . 2 :

 32 Figure 3.2: The concept of time division multiple access

Figure 3 . 3 :

 33 Figure 3.3: Collision with two-hop neighbors on a specific service channel

  Channel vs. Multichannel Protocol -Low Mobility vs. High Mobility -All mobility models vs. special mobility model -Unidirectional vs. bidirectional vehicular traffic -Dense network vs. sparse network -Collision free vs. channel interference -Efficient broadcast service vs. no support of broadcast services 3.4 TDMA-based MAC protocols in a fully distributed VANET (TDV)

Figure 3 . 4 :-

 34 Figure 3.4: Access collision problem

Figure 3 . 5 :

 35 Figure 3.5: Merging collision problem

Figure 3 . 6 :

 36 Figure 3.6: SOFT MAC frame structure[START_REF] Abu-Rgheff | SOFTMAC: Spaceorthogonal frequency-time medium access control for VANET[END_REF]

Figure 3 . 7 :

 37 Figure 3.7: Architecture of DMMAC

Figure 3 . 8 :

 38 Figure 3.8: Partitioning of each frame into three sets

Figure 3 . 9 :

 39 Figure 3.9: Slot management mechanism in ATSA

  have proposed a near collision-free reservation based MAC protocol to further address the merging collision problem and to provide near collisionfree channel access. The scheduling mechanism of CFR MAC is based on the VeMAC protocol which takes into consideration the traffic flow and the relative speeds of each vehicle. Each frame is divided into two sets of time slots Lef t and Right which are assigned to vehicles that are moving to the left and right. However, the merging collision problem can occur in VANETs when vehicles are moving at different speeds. Therefore, in order to solve this problem, each slots set is further divided into three subsets associated to three speed intervals: High, Medium and Low. The CFR MAC protocol dynamically adjusts the number of time slots reserved for each direction and speed level. The simulation results show that CFR MAC significantly reduces the access delay and the collision rate compared with to VeMAC and IEEE 802.11p.

Figure 3 . 10 :

 310 Figure 3.10: Access collision problem

  time slots which are grouped into time-frames. The TDMA frame structure employed by CBMAC is shown in Figure3.11.

Figure 3 .

 3 Figure 3.11: TDMA frame structure

Figure 3 .

 3 Figure 3.12: TDMA frames in the CRC channel

  is based on the previous ADHOC MAC protocol. The A-ADHOC protocol is intended for real-time applications in large-scale wireless vehicular networks, offering another option of adaptive frame length. The simulation results show that A-ADHOC has surpassed the ADHOC MAC in both channel resource utilization and response time. In particular, the new protocol can avoid network failure regardless of traffic density, which is an inherent problem in the ADHOC MAC protocol. P6) TDMA Cluster-based MAC (TC-MAC) Almalag et al. in [101] propose a novel multi-channel MAC protocol called TDMA cluster-based MAC (TC-MAC) for VANETs. Their proposal uses a new TDMA slot reservation schedule managed by stable cluster heads. TC-MAC provides efficient time slot utilization for the participating vehicles. Unlike the IEEE 802.11p standard architecture, in TC-MAC, the frame is not divided into two intervals CCHI and SCHI.

  P7) Cooperative ADHOC MAC (CAH-MAC) for Vehicular NetworksBharati and Zhuang propose in[START_REF] Bharati | CAH-MAC: Cooperative ADHOC MAC for Vehicular Networks[END_REF][START_REF] Bharati | Performance analysis of cooperative ADHOC MAC for vehicular networks[END_REF] a Cooperative ADHOC MAC protocol, with the aim of improving throughput for non-safety applications. The scheduling mechanism developed by the CAH-MAC protocol is based on distributed TDMA similar to the one in ADHOC MAC in that the channel access time is divided into periodic frames and each frame is further divided into time slots. The goal of the research work is to propose a new way to overcome the transmission failure problem when it occurs due to poor channel conditions. In fact, upon detecting a transmission failure between the transmitter and the receiver, a neighboring node called a "helper node" offers cooperation to relay the packet that failed to reach the destination during an idle time slot. Compared to the ADHOC MAC protocol, the main disadvantage of CAH-MAC is that the use of any free time slots by the helper nodes for cooperative relay transmissions can lead to the access collision problem with the vehicles that attempt to obtain an available time slot. P8) Cluster-based TDMA system for inter-vehicle communications (CBT) Sheu and Lin[START_REF] Sheu | A Cluster-based TDMA System for Inter-Vehicle Communications[END_REF] have proposed and evaluated a Cluster-Based TDMA system (CBT) for inter-vehicle communications. The goal of this system is to develop contention-free intra-cluster and inter-cluster communications while minimizing collisions when two or more clusters are approaching each other. The protocol uses a simple transmit-and-listen scheme to quickly elect a VANET Coordinator VC. The CBT system assumes that each vehicle is equipped with a GPS positioning system and synchronization between the vehicles can be performed by using GPS timing information. The access time is divided into frames and each frame consists of n time slots. As shown in Figure3.13(a), the slot 0 in frame 1 (SYN) is used by neighboring vehicles to exchange an 8 byte beacon signal to indicate the start of a frame. However, the same slot serves in other frames which are used by the elected VANET Coordinator VC to broadcast a Slot-Allocation Map (SAM) to its VANET Nodes VNs. The slot 1 to slot n -1 in the first frame are used for VC election (VC-elected stage), while the slot 1 to slot n -1 in the other frames (Slot-allocation stage) are used by their designated vehicles to send data messages.

Figure 3 .

 3 Figure 3.13: TDMA and MAC-layer frames in the CBT protocol

Table 3 . 4 :

 34 Qualitative comparison of TDMA-based MAC protocols in cluster-based network topology

P1)

  Adaptive Collision-Free MAC (ACFM) Guo et al. in [107] propose an Adaptive Collision-Free MAC (ACFM) protocol based on a centralized dynamic time slot reservation mechanism in RSUs. Thus, by using a schedule, ACFM ensures efficient time slot utilization for the exact number of active vehicles.

Figure 3 .

 3 Figure 3.14: TDMA frame structure of the ACFM protocol

Figure 3 . 15 :

 315 Figure 3.15: Frequency assignment in ACFM

  Tomar et al. has some serious drawbacks. Although this protocol has been evaluated in scenarios where there are junctions, the authors do not detail inter-cluster communication at junctions where vehicles are moving in different directions. CBRC has a fixed number of slots which may degrade its performance when vehicle density is very high. Moreover, due to its high speed and frequent changes in velocity, a vehicle can join/leave an RSU region very quickly, which can lead to a break in communication. The authors do not describe multi-hop communication between vehicles and RSUs and how a new vehicle that is joining an RSU area can change from one slot to another while remaining in communication.P4) Unified TDMA-based Scheduling Protocol for V2I communications (UTSP)Zhang et al. have proposed in[START_REF] Zhang | A unified TDMAbased scheduling protocol for Vehicle-to-Infrastructure communications[END_REF] and[START_REF] Zhang | A Novel Centralized TDMA-Based Scheduling Protocol for Vehicular Networks[END_REF] a Unified TDMA-based Scheduling Protocol (UTSP) for V2I communications. The goal of the work is to optimize the throughput for non-safety applications in VANETs. In the proposed TDMA scheduling strategy, the RSU collects the necessary information including channel state information, the speed, and the Access Category AC characteristic of the vehicles within its communication range and then it assigns the time slots to the vehicles based on the weight function which consists of three factors, i.e. channel-quality weight factor, speed weight factor and AC weight factor. The first factor is used to maximize the network throughput, the second one is used to ensure fairness between vehicles that are moving at different speeds, while the last one distinguishes the access priorities of different slot reservation requests. The vehicle which has the maximum weight value will be served first by the RSU in the current TDMA frame. The simulation results prove that UTSP has good performance in terms of throughput and fairness compared with the traditional standard IEEE 802.11. However, UTSP was designed to support only VANET applications that are throughput-sensitive. In addition, the authors do not describe the mobility scenarios used to evaluate the performance of UTSP. Since the protocol was evaluated only for one RSU, an interference problem can occur between vehicles in the overlapping regions where several RSUs are used to coordinate access to the channel. As a result, UTSP cannot satisfy the requirements of VANET applications because they are mainly oriented to road safety issues.

  Due to the limited transmission range of vehicles (less than 250 m) and large transmission range of RSUs (up to 1 km), the performance of CBRC degrades when vehicle density or traffic load are high, making CBRC unscalable. The throughput of the ACFM protocol is high compared to the other protocols because ACFM enhances the MAC capacity through concurrent transmissions using different orthogonal frequencies. Frequency reuse also reduces the waiting time of a vehicle for channel allocation. The efficient slot allocation algorithms developed for CSMA and TDMA

Figure 3 .

 3 Figure 3.16: Number of protocols versus MAC QoS metrics supported

Figure 3 . 17 :Figure 3 .Figure 3 . 19 .

 3173319 Figure 3.17: Number of protocols versus number of MAC QoS metrics supported

Figure 3 . 18 :

 318 Figure 3.18: Number of protocols versus MAC protocol design issues

Figure 3 . 21 :

 321 Figure 3.21: Number of TDMA-based MAC protocols proposed for each years

4. 3

 3 DTMAC: Distributed TDMA-based MAC protocol 4.3.

Figure 4 . 1 :

 41 Figure 4.1: TDMA slots scheduling principle.

Figure 4 . 2 .

 42 Figure 4.2. Each time slot is dynamically reserved by an active vehicle (the vehicle whose communication device is transmitting) for collision-free delivery of safety messages or other control messages. The VC ID field contains the ID of the vehicle that is accessing this slot. Each vehicle is identified by its MAC address. The SLT STS field contains the status of each slot which indicates whether the slot is Idle, Busy or

Figure 4 . 2 :

 42 Figure 4.2: Frame information (FI) structure.

4. 5

 5 Simulation results and performance evaluation 4.5.1 Simulation scenarios and performance metrics In our work, we have used VanetMobiSim [114] to generate the mobility pattern of vehicles. We simulate different traffic conditions by varying the speed deviation and the vehicles density. We consider a VANET in a two-way highway scenario of size 2000m × 20m, where vehicles are moving along the highway in opposite directions. The parameters of VanetMobiSim consisted of the maximum number of vehicles, the starting and destination positions of each vehicle and the number of lanes per direction. During simulation time, each vehicle moves at a constant speed, and the number of vehicles on the highway remains constant. Then the traffic traces generated by VanetMobiSim were used in the ns2.34 simulations, as shown in the Figure 4.3.

Figure 4 . 3 :

 43 Figure 4.3: VANET mobility scenario

Figures 4 .

 4 Figures 4.4and 4.5 shows the average access collision probability under various traffic conditions for σ equal to 20, 30 and 50 km/h, respectively. The experiments were carried out for different values of n1, n2 and n3. It is clear from these three figures that the first configuration when the three sets of time slots have the same size equal to τ /3, is the best configuration that minimizes the probability of access collision under different traffic conditions.

Figure 4 . 4 :

 44 Figure 4.4: The access collision probability for σ = 20 (left) and σ = 30 (right).

Figure 4 . 5 :

 45 Figure 4.5: The access collision probability for σ = 50.

Fig 4 . 6

 46 Fig 4.6 shows the rate of merging collisions for DTMAC and VeMAC protocols when varying the Area Occupancy (AO). DTMAC 3 prevents more merging collisions

  the available time slot sets are allocated by the contending vehicles without considering their speed deviations. Therefore merging-collisions occur frequently in VeMAC when traffic density is high as well as when vehicles driving toward each other and at high relative speeds. It should be noticed that, in principle, the algorithm prevents any merging-collision for DTMAC.

Figure 4 . 6 :

 46 Figure 4.6: The rate of merging collision.

Figure 4 .

 4 Figure 4.7 shows the access collision rates of the two TDMA based MAC protocols.As shown in this Figure, DTMAC achieves a considerably smaller rate of access collisions than VeMAC, especially for a high AO (≥ 0.7). For instance, at a AO = 0.96, the DTMAC protocol achieves an access collision rate of 0.849%, in contrast to VEMAC which shows a rate of 1.598% (i.e. approximately 88.22% higher than DTMAC). These results can be explained by the fact that VeMAC has achieved a higher rate of merging collision compared to DTMAC. Indeed, upon detection of merging-collisions, the nodes in collision should release their time slots and request new ones, which can reproduce access-collisions.The packet loss rates of the two MAC protocols under consideration are shown in Figure4.8. For a AO ≤ 0.7, the DTMAC and VeMAC protocols have almost the same packet loss rate, while for a AO > 0.7, DTMAC starts to perform better than VeMAC. It can be seen that our MAC protocol has the lowest packet loss rate, especially for a high AO, due to its ability to handle the merging collision problem.

Figure 4 . 7 :

 47 Figure 4.7: The rate of access collision.

Figure 4 . 8 :

 48 Figure 4.8: The rate of packet loss under various traffic densities.

Figure 4 . 9 :

 49 Figure 4.9: The coverage broadcast ratio under various traffic densities.

Figure 5 . 1 ,

 51 we show an example of a situation where unsuitable routing decisions lead to a large end-to-end delay. The presented VANET scenario consists of 7 vehicles identified by letters (A to G), using a random TDMA scheduling represented by vectors of length equal to 6. Each element of a vector represents one time slot that can be used by only one vehicle to send messages. The shortest path in terms of the number of hops provided by the routing protocol does not always ensure the shortest end-to-end delay. For example, when considering vehicle G as the destination vehicle that will broadcast a message collected from vehicle A, the path A-B-D-G is the shortest in terms of the number of hops, but it produces a delay of 16 time slots (4 time slots to reach slot t4 which is the transmission slot for vehicle A, then 4 time slots between t4 and t2 as t2 is the transmission slot for vehicle B, then 5 time slots between t4 and t1 as t1 is the transmission slot for vehicle D and finally 3 time slots between t1 and t5 as t5 is the transmission slot in which vehicle G will broadcast the message received from vehicle A). This delay is greater than the delay of the path A-B-C-E-G which uses 3 relay nodes and requires 11 time slots (4 time slots to reach slot t4, 4 time slots between t4 and t2, then 1 slot between t2 and t3, 1 slot between t3 and t4 and 1 slot between t4 and t5).

Figure 5 . 1 :

 51 Figure 5.1: VANET network using random TDMA scheduling scheme.

[ 79 ]

 79 scheme is limited only to infotainment applications (i.e. Internet access) and does not support safety applications, which makes it unsuitable for VANETs which are specially designed to improve road safety. In this chapter, we focus on this category of approach and we propose a novel TDMA-aware routing protocol for multi-hop communications in VANETs, in which the next hop decisions are based on the TDMA scheduling at the MAC layer. Unlike[START_REF] Omar | On Multihop Communications For In-Vehicle Internet Access Based On a TDMA MAC Protocol[END_REF], our protocol allows a vehicle to send eventdriven safety messages over a large distance.

5. 4 5 . 4 . 1

 4541 TDMA-aware routing protocol for multi-hop communications System specifications

Figure 5 . 2 :

 52 Figure 5.2: VANET network using DTMAC scheduling scheme.

14 :

 14 end if message will use the weight function WHS to select a forwarding vehicle in the next area from those listed in the set A i or B i . By subtracting the area ID contained in the received message, the vehicle i can determine the appropriate set of potential relays.

23: end ifFigure 5 . 3 :

 53 Figure 5.3: Message propagation based on TDMA slot information.

Figure 5 .

 5 5 shows a metropolitan area from the Map of San Jose (California) of size 3000m × 100m exported from OpenStreetMap (OSM) and edited using Java OpenStreetMap Editor (JOSM). Then, we defined a vehicle flow which described a swarm of vehicles in each direction. The parameters of each vehicle flow consisted of the maximum number of vehicles, the starting road and destination of the flow, the time to start and end the flow. We assigned a random speed to each vehicle between 120km/h and 150km/h. Then, the traffic traces generated by MOVE were used in the ns2.34 simulator. The simulation parameters used in our experiments are summarized in Table5.1.

Figure 5 . 5 :

 55 Figure 5.5: San Jose (California) urban area captured from Google Maps (left) and exported to a VANET network topology by using MOVE/SUMO (right).

Figure 5 . 6 :

 56 Figure 5.6: Effect of changing α on average end-to-end delay.

Figure 5 .

 5 Figure 5.8 shows the average end-to-end delay for all the multi-hop communication protocols under consideration. We can note from this figure that the TRPM protocol performs very well compared to RTDMA and CRP, especially as the distance between the source and destination increases. For instance, when SDD = 2295m, the TRPM protocol achieves an average end-to-end delay of 234.16ms while RTDMA and CRP

Figure 5 . 7 :

 57 Figure 5.7: Effect of changing α on average number of hops.

Figure 5 . 8 :

 58 Figure 5.8: The average end-to-end delay vs source-to-destination distance.

Figure 5 .

 5 [START_REF] Shulman | Safety Communications in the United States[END_REF] shows the average number of relay vehicles for TRPM, RTDMA and CRP protocols when varying vehicle density. Unlike RTDMA and CRP, the average number of hops in TRPM is still constant as vehicle density increases. This is mainly due to the forwarding concept in TRPM which always selects only one forwarding vehicle in each area so that the number of relay vehicles always remains constant.

Figure 5 . 10 :

 510 Figure 5.10: The average end-to-end delay vs vehicle density.

Figure 5 . 11 :

 511 Figure 5.11: The average number of relay vehicles vs vehicle density.

Figure 6 . 1 :

 61 Figure 6.1: Mobility direction based clustering

Figure 6 . 2 :

 62 Figure 6.2: Road-based clustering

11 :

 11 while OH i ! = 0 and S i == CHC do 12:

Figure 6 . 3 :

 63 Figure 6.3: Vehicle state transition diagram

  2 shows the parameters of AWCP and their variation ranges. These parameters are four timers, four counters and three weighting factors. The variation ranges of the four timers and the first two counters are set based on the clustering protocols proposed in the literature. The Cluster Size is the maximum number of vehicles in the cluster which should be less than (R * l) * 2/(w + d), where R, l, w and d are respectively the transmission range, the number of road lanes, the standard length of the vehicles which is about 3m and the safety distance. P min is the received signal strength where the distance between two vehicles is equal to the safety distance, where P max is the received signal strength where the distance between two vehicles is equal to 3 * R/4.

Figure 6 .

 6 Figure 6.4 shows the values of the three optimized objectives for different AWCP configurations. From this figure, it is clear that the performance of AWCP depends on the choice of the tuning parameters. Due to the conflicting nature of the objective functions and the large size of the search space, AWCP parameter tuning is an NP-hard problem due to the huge number of possible configurations [135]. Several mono-and multi-objective optimization algorithm based approaches have been proposed in the literature for optimally configuring communication protocols in VANETs and MANET networks. For instance, Garcìa-Nieto et al. have used different meta-

Figure 6 . 4 :

 64 Figure 6.4: Distribution of solutions on the objective space.

23 :PFigure 6 . 6 :

 2366 Figure 6.6: Uniform crossover operator example.

  rection a vehicle flow which described a swarm of vehicles. The parameters of each vehicle flow consisted of the maximum number of vehicles, the starting road and destination of the flow, the time to start and end the flow and the probabilities of turning to different directions at each junction (0.4 to go straight, 0.3 to turn left and 0.3 to turn right). Then the traffic traces generated by MOVE were used in the ns-2 simulations. All the tests were performed on different VANET scenarios taking into account different vehicle densities and data loads: Low, Medium, High and Very High. The features of the VANET scenarios and the simulation parameters used in our experiments are summarized in Tables 6.3 and 6.4.

Figure 6 . 7 :

 67 Figure 6.7: 3D Pareto fronts returned by the NSGA-II, MOPSO and MODE algorithms for the S1 and S3 VANET scenario.

Figure 6 . 8 :

 68 Figure 6.8: ACL results.Figure6.9: CPO results.

Figure 6 . 9 :

 69 Figure 6.8: ACL results.Figure6.9: CPO results.

Figure 6 .

 6 Figure 6.10 shows the Packet Delivery Ratio (PDR) achieved by each clustering protocol for various VANET scenarios. It clearly shows that for varying traffic densities the AWCP protocol gives the best performance in terms of PDR, except for theHigh scenario, where WCA, HD and LID deliver a higher data rate. Although the network performance in terms of throughput significantly decreases when the vehicle density increases, on average, AWCP guarantees a better PDR than the other protocols. This is due to the fact that AWCP does not generate an excessive clustering

Figure 6 . 10 :

 610 Figure 6.10: PDR results.Figure 6.11: The US average duration

Figure 6 . 11 :

 611 Figure 6.10: PDR results.Figure 6.11: The US average duration

Figure 6 . 12 :

 612 Figure 6.12: The number of vehicles' state transitions for the two scenarios S3 (left) and S4 (right).

Figure 6 . 13 :

 613 Figure 6.13: The eight basic directions and their ranges at a 4-road junction.

Figure 6 . 14 :

 614 Figure 6.14: Moving direction angle calculation.

Figure 6 . 15 :

 615 Figure 6.15: Angle-based Clustering.

Figure 6 .

 6 Figure 6.16: Highway exit scenario.

  the parameter tuning problem of the AWCP protocol as a Multi-Ojective Linear Programming MOLP problem and we propose an optimization strategy in which the Non-dominated Sorting Genetic Algorithm, version 2 (NSGA-II) is combined with thr ns-2 simulator to solve the MOLP problem. The experimental results show that the NSGA-II algorithm obtains well-distributed solutions over the Pareto front and presents the best results in terms of performance metrics. Thus, NSGA-II algorithm is more suitable for the AWCP parameter tuning problem. Moreover, the simulation results show that AWCP clearly improves the clustering performance in VANETs in terms of cluster lifetime duration and communication overhead compared to the wellknown clustering protocols WCA, LID and HD. This is also the case when AWCP is compared with another protocol CPM, which also considers both the vehicles' position and the direction of movement. However, AWCP is based on the assumption that each vehicle is equipped with a digital mapping device, and thus it cannot operate in environments where vehicles without maps are present. Thirdly, we presented an Angle-based Clustering Algorithm (ACA), which uses the angle between velocity vectors of vehicles as a metric to form stable clusters. Instead of discovering neighboring vehicles by exchanging Hello packets over the entire communication range, we have used an angular technique that allows each vehicle to identify the stable neighbors that it can form a cluster with and does not consider neighboring vehicles that are moving at an obtuse angle. This angular methodology helps us to build stable clusters where vehicles without maps are present and to reduce the overhead generated by the re-clustering mechanism due to false merges at road intersections.

7. 2

 2 CTMAC: centralized TDMA based MAC protocol 7.2.1 CTMAC preliminariesIn this section, we present an infrastructure-based TDMA scheduling scheme which exploits the linear feature of VANET topologies.The vehicles' movements in a highway environment are linear due to the fact that their movements are constrained by the road topology. Our scheduling mechanism is also based on the assumption that the highway is equipped with some RSUs (i.e. one RSU for each 2 × R meters, where R is the communication range). Note that each area is covered by one RSU installed on the side of the highway and in the middle of the corresponding area. The time slots in each TDMA frame are partitioned into two sets S 1 , S 2 associated with vehicles in two adjacent RSU areas (see Figure7.1). Each frame consists of a constant number of time slots, denoted by τ and each time slot is of a fixed time duration, denoted by s.Each vehicle can detect the start time of each frame as well as the start time of a time slot. In the VANET studied, all the vehicles are equipped with a GPS and thus the one-Pulse-Per-Second (1PPS) signal that a GPS receiver gets from GPS satellites can be used for slot synchronization. The first time slot either in the set S 1 or S 2 is always used by the correspondent RSU to broadcast a Slot Announcement message (SA) to the vehicles within its coverage area. In the following, we detail the slot scheduling mechanism in CTMAC and we show how this protocol can provide an efficient time slot utilization for the participating vehicles, while minimizing transmission collisions caused by the hidden node problem.

Figure 7 . 1 :

 71 Figure 7.1: TDMA slots scheduling mechanism of CTMAC

Figure 7 . 2 :Algorithm 8

 728 Figure 7.2: Frame information (FI) structure.

3 :

 3 if current slot== T S(u) and F (u) = {∅} then 4:

7. 2 . 3

 23 Access collision avoidanceIn Figure7.3, we show an example of access collision avoidance mechanism implemented by CTMAC. The VANET scenario consists of 4 vehicles identified from (v1 to v4) and one RSU, using a CTMAC's scheduling represented by vectors (one vector for each node) of length equal to 5. Each element of a vector represents one time slot that can be used by only one node to send messages. We assume that two vehicles v 3 and v 4 have sent respectively their SREQ1, SREQ2 to RSU1 during the same time slot (ts = 3) in frame i, as shown in Figure7.3. The RSU did not confirm their reservations because their packets collided. Since the neighboring vehicles v 1 and v 2 have respectively received SREQ1 and SREQ2 without a collision problem, they will update their frame information by adding the vehicles v 3 and v 4 and then will send their new captured frame information to the RSU1 during the time slot ts = 2 and ts = 3 in frame i + 1, respectively. Upon reception, the RSU1 observes that v 3 and v 4 are trying to access the channel and to prevent the access collision problem occurring again, it will broadcast frame information including new time slots for vehicles v 3 and v 4 during the time slot ts = 1 in frame i + 2. When all vehicles receive a packet transmitted by an RSU1, they will update their FIs.

Figure 7 . 3 :

 73 Figure 7.3: Access collision avoidance.

7. 3

 3 ASAS: an adaptive slot assignment strategy in cluster-based VANETsIn this section, we describe an adaptive TDMA slot assignment strategy (ASAS) for cluster based TDMA MAC protocols. The proposed strategy is based on the AWCP protocol in which the cluster heads are used to assign disjoint sets of time slots to the members of their clusters. ASAS uses the vehicles' locations and directions as well as a slot reuse mechanism that can reduce inter-cluster interference under different traffic load conditions without having to use expensive spectrum and complex mechanisms such as CDMA or FDMA.

7. 3 . 1

 31 Network and system modelA cluster formation algorithm based on road ID (AWCP) is used in ASAS in order to provide a more stable clustering architecture with less communication overhead than is caused by cluster head election and cluster maintenance procedures. The VANET scenario taken into consideration is a highway scenario which consists of a set of vehicles moving in opposite directions and under varying traffic conditions (speed, density). As shown in Figure??, the vehicles are grouped into clusters and one vehicle in each cluster is elected to act as a cluster head to create and manage the TDMA slot reservation schedule for its cluster members. Each CH constructs two sets of cluster members based on their positions B (Behind) and A (Ahead), where B is the set of vehicles that are moving behind the cluster head and A is the set of vehicles that are moving ahead of the cluster head. In ASAS, the channel access time is partitioned into frames and each frame is divided into two periods namely: Broadcast Service (BS) period and Contention-based Reservation (CR) period. The BS period is TDMA-based time interval which consists of a set of time slots where each time slot can be used by one vehicle (CM or CH) to broadcast a safety message or a control message such as for topology management.

Figure 7 . 4 :

 74 Figure 7.4: Network model.

Figure 7 . 5 :

 75 Figure 7.5: System architecture

  [START_REF] Tse | Improving message reception in vanets[END_REF] shows the schedules provided by ASAS which are represented by vectors of length equal to 18 (9 slots for each direction). Each element of a vector represents one time slot that can be used by only one vehicle to send messages. The table shows an example of spatial reuse of time slots in ASAS and how it can avoid the inter-cluster interference problem due to the overlapping area between two neighboring clusters by exploiting the linear topology in VANET highway scenario. For instance, as shown in Figure?? and Table7.1, by dividing the time slots reserved for each direction into three sets, vehicles CM-3, CM-4 and CM-5 in cluster I and vehicles CM-6 and CM-7 in cluster II which are moving in the overlapping area cannot transmit their messages simultaneously because they are accessing disjoint sets of time slots.

7. 4

 4 Simulation results and performance evaluation 7.4.1 Performance evaluations of CTMAC

Figure 7 . 6 :

 76 Figure 7.6: The rate of merging collisions.

Figure 7 .

 7 Figure 7.6 shows the rate of merging collisions for the CTMAC, VeMAC and ADHOC MAC protocols presented in Chapter 3 when varying the RSU Coverage

Figure 7 . 7 :

 77 Figure 7.7: The rate of access collisions.

Figure 7 .

 7 Figure 7.7 shows the access collision rates of the three TDMA-based MAC protocols under consideration. For a RCO ≤ 0.6, all the protocols have almost the same access collision rate, while for a RCO ≥ 0.7, CTMAC starts to perform better than VeMAC and ADHOC MAC. These results are due to the fact that VeMAC and ADHOC MAC have produced a higher rate of merging collisions compared to CT-MAC. Upon detecting merging-collisions, the nodes in collision should release their time slots and request new ones, which can reproduce access-collisions. Moreover, as discussed in Section 7.2.3, by using the RSU as a central coordinator to schedule and maintain time slot assignment for the vehicles in its coverage area, one can prevent the access collision problem occurring more than once between the same vehicles that are trying to access the channel. The packet loss rates of the three MAC protocols under consideration are shown in Figure 7.8. It can be seen that our MAC protocol has the lowest packet loss rate, especially for a high RCO, due to its ability to handle the access and merging collision problems. For instance, at a RCO = 1, the VeMAC and ADHOC MAC protocols

Figure 7 . 8 :

 78 Figure 7.8: The rate of packet loss under various traffic densities.

Figure 7 .

 7 Figure 7.9 shows the overhead (in Mega octets) generated by each protocol over 120s. We can see from this figure that CTMAC has greatly reduced the overhead compared to VeMAC and ADHOC MAC. For instance, at RCO=0.96, the overhead is reduced by respectively 85.52% and 83.81% on average when CTMAC is used. This can be explained by the fact that CTMAC uses the RSUs to assign time slots and to disseminate the FI and then all the vehicles within their communication range will update their slot schedule tables based on the FI received, in contrast to VeMAC and ADHOC MAC that are fully distributed protocols in which each vehicle periodically broadcasts the FI to its direct neighbors in order to maintain the TDMA schedule table.

7. 4 . 2

 42 Comparative performance evaluation of CTAMC and DTMACIn this section, we compare the performance of DTMAC (distributed TDMA-based scheduling) with CTMAC (centralized TDMA-based scheduling) in terms of average number of vehicles acquiring time slot (evaluation of slot reuse), merging and access collision and the overhead (the control messages needed to establish and maintain a collision-free schedule).

Figure 7 . 9 :

 79 Figure 7.9: TDMA scheduling overhead.

Figure 7 . 10 :Figure 7 .

 7107 Figure 7.10: Average number of vehicles acquiring time slot: CTMAC versus DTMAC

Figures 7 .

 7 Figures 7.11 shows the rate of merging collisions for DTMAC and CTMAC. DT-MAC achieves a considerably lower rate of merging access collisions than CTMAC, especially for a high AO (≤ 0.4).

Figure 7 . 11 :

 711 Figure 7.11: Merging collision: CTMAC versus DTMAC

Figure 7 .

 7 Figure 7.13 shows the amount of overhead (in Mega octets) generated by DTMAC

Figure 7 . 13 :

 713 Figure 7.13: Overhead: CTMAC versus DTMAC

  MAC protocols to overcome existing MAC problems in VANETs as well to support safety applications. These protocols are called DTMAC, CTMAC and ASAS, and we have also designed a routing protocol to send event-driven safety messages over a long distance.Recently, several Time Division Multiple Access (TDMA)-based MAC protocols have been proposed for VANETs in an attempt to ensure that all the vehicles have enough time to send safety messages without collisions and to reduce the end-toend delay. To understand the reasons for using the collision-free MAC paradigm in VANETs and the major issues and advantages of TDMA in VANETs, we provided in Part I a comprehensive study of TDMA based MAC protocols proposed in the literature. Moreover, we gave a qualitative comparison of these protocols, and we

  VANETs. DTMAC was essentially designed to provide a reliable broadcast service with bounded access delay, while reducing access collisions and merging collisions under various vehicle densities without having to use expensive and complex spectrum mechanisms such as CDMA or OFDM. DTMAC is based on the assumption that the road is divided into small fixed areas and the time slots in each TDMA frame are partitioned into three sets associated with vehicles in three contiguous areas. The ways that slots are allocated and reused between vehicles in DTMAC are designed to avoid collisions caused by the hidden node problem. An analytical model of the average access-collision probability is proposed. Moreover, based on this model, we studied the behavior of the protocol's parameters and we derived an accurate configuration.The network simulator ns-2 and vehicular traffic simulator VanetMobiSim were used to evaluate the performance of DTMAC in comparison with the well-known protocol VeMAC in a highway scenario. The simulation results show that DTMAC provides a lower rate of access and merging collisions than VeMAC, which results in a significantly improved broadcast coverage. The simulation results underline the efficiency and benefits of our first contribution and justify continuing in this research direction.

  which the intermediate vehicles are selected based on DTMAC's scheduling technique. Moreover, our protocol takes into account the relay selection efficiency by using a weighted next-hop selection function in order to make coherent next hop decisions in terms of both the number of relay vehicles and end-to-end delay. The network simulator ns-2 and a vehicular traffic simulator MOVE/SUMO were used to evaluate the performance of TRPM in comparison with the contention aware routing CRP protocol and random TDMA based routing protoocol RTDMA in a realistic highway scenario. The simulation results show that, compared to CRP and RTDMA, our cross-layer protocol provides better performances in terms of average end-to-end delay, average number of hops and average delivery ratio. These two research efforts confirm our studies in Part I which shows that TDMA is a promising technology for both MAC and routing in vehicular communications, and a suitable solution that can replace contention-based MAC protocols such as the IEEE 802.11p standard.

  VANETs applications . . . . . . . . . . . . . . . . . . . . . . . 2.3 VANET standardization and research projects . . . . . . . . . . . . . 2.3.1 Standardization . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Related projects . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Summary and discussion . . . . . . . . . . . . . . . . . . . . . 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 TDMA-based MAC Protocols for Vehicular Ad Hoc Networks 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 An overview of a VANET network . . . . . . . . . . . . . . . . . . . . 2.2 An example of road map. . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 An accident detection by using V2V communication. . . . . . . . . . 2.4 Emergency brake warning. . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Channel assignment in DSRC . . . . . . . . . . . . . . . . . . . . . . 2.6 Channel access time in IEEE 802.11p standard . . . . . . . . . . . . . 2.7 Protocol stack of WAVE . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Overview of ITS activities in Europe and the rest of the world . . . .

	Table of Contents	viii
	List of Figures	xii
	List of Tables	xv
	1 General Introduction

1.1 Background and motivations . . . . . . . . . . . . . . . . . . . . . . . 1.2 Main contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Manuscript organization . . . . . . . . . . . . . . . . . . . . . . . . . I State of the Art 2 Vehicular Adhoc NETworks: Achitecture, Features and Standardization Activities 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Vehicular networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Definition and architectures . . . . . . . . . . . . . . . . . . . 2.2.2 General characteristics . . . . . . . . . . . . . . . . . . . . . . 2.2.3 3.2 Medium access control in VANETs . . . . . . . . . . . . . . . . . . . 3.2.1 Classification of MAC protocols . . . . . . . . . . . . . . . . . 3.2.2 VANET MAC protocol design issues . . . . . . . . . . . . . . 3.2.3 Performance metrics . . . . . . . . . . . . . . . . . . . . . . . 3.3 TDMA-based MAC protocols . . . . . . . . . . . . . . . . . . . . . . viii List of Figures 2

  8, we conclude this thesis by summarizing the main contributions and key results and then we present our future work and open research issues related to TDMA based MAC protocols design for VANETs.

	Chapter 2
	Vehicular Adhoc NETworks: Achitecture,
	Features and Standardization Activities
	Part I
	State of the Art

Contents 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Vehicular networks . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1 Definition and architectures . . . . . . . . . . . . . . . . . . 11 2.2.2 General characteristics . . . . . . . . . . . . . . . . . . . . . 12 2.2.3 VANETs applications . . . . . . . . . . . . . . . . . . . . . 14 2.3 VANET standardization and research projects . . . . . . 16 2.3.1 Standardization . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.2 Related projects . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3.3 Summary and discussion . . . . . . . . . . . . . . . . . . . . 21 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

•

  Safety Applications: As mentioned above, this category of VANET applications represents the main objective of inter-vehicular communications. These applications aim to reduce the number of accidents and enhance driver and passenger safety by enabling each vehicle to provide a warning in real time

	when a critical event is detected. The warning message can be either through a
	seat vibration, tone or visual display or combinations of these indicators. Fig-
	ures 2.3 and 2.4 show examples of safety applications that are based on V2V
	communications. As illustrated in Figure 2.3, when an accident is detected, a

vehicle can continuously broadcast information about this critical situation to the approaching vehicles.

  8 [16]. It was developed to support V2V and V2I communications. This standard supports vehicle speeds up to 190 km/h, a data rate of 6 Mbps (up to 27 Mbps) and a nominal transmission range of 300 m (up to 1000 m). DSRC is defined in the frequency band of 5.9 GHz on a total bandwidth of 75 MHz

	(from 5.850 GHz to 5.925 GHz). This band is divided into 7 channels of 10 MHz
	(see Figure 2.5). These channels are divided functionally into one control chan-
	nel and six service channels. The control channel, CCH, is reserved for the
	transmission of network management messages (resource reservation, topology
	management) and it is also used to transmit high priority messages (critical
	messages relating to road safety). The six other channels, SCHs, are dedicated
	to data transmission for different services. In addition, DSRC represents a

US standard and one which is also used in other parts of the world. Table

2

.1

Table 2 .

 2 1: Regional standards for DSRC

	Features	Japan (ARIB)	Europe (CEN)	North America (ASTM)
	Duplex	Half-duplex(OBU)	Half	Half
		Full-duplex(RSU)
	Communication system	Active	Passive	Active
	Radio frequency	5.8 GHz	5.8 GHz	5.8-5.9 GHz
	Bandwidth	80 MHz	20 MHz	75 MHz
	Channels	7	4	7
	Channel Separation	5 MHz	5 MHz	10 MHz
	Data rate	Down/Uplink:	Down-link: 500 Kbps	Down/Uplink:
		1 or 4 Mbps	Up-link: 250 Kbps	6-27 Mbps
	Coverage(m)	30	15-20	1000
	Modulation	RSU: 2-ASK	RSU: 2-ASK	OFDM
		OBU: 4-PSK	OBU: 2-PSK

p of the IEEE. This standard improves QoS by using the EDCA

13

functionality, derived from the IEEE 802.11e standard

[START_REF] Uzcátegui | WAVE: A Tutoriat[END_REF]

. The EDCA allows safety messages which have a higher priority (there are 4 categories) to have a better chance of being transmitted than messages with a lower priority. Prioritization is achieved by varying the Contention Windows (CWs) and the Arbitration Inter-Frame Spaces (AIFS), which increase the probability of successful medium access for real time messages. The channel access time is equally divided into repeating synchronization intervals of 100 ms

[START_REF]Wireless Access in Vehicular Environments (WAVE) Multi-Channel Operation[END_REF]

, and each synchronization interval is divided into CCH Intervals (CCHI) of 50ms and SCH Intervals (SCHI) of 50 ms, as shown in Figure

2

.6. During the CCHI all the vehicles tune to the CCH to send/receive high priority safety messages or to announce a service that will be provided on a specific service channel. If a vehicle decides to use this service on a specific SCH channel, it tunes to this channel during its SCHI. The standard also defines a Guard interval at the start of each channel interval. This interval is set to 4µs and it is used for radio switching and not for transmissions. Synchronization between vehicles is achieved by receiving the coordinated universal time (UTC) provided by the GPS equipped in each vehicle. In order to support different applications concurrently, IEEE 1609.4

[START_REF] Chen | IEEE 1609.4 DSRC Multi-Channel Operations and Its Implications on Vehicle Safety Communications[END_REF]

defines multichannel operation for the MAC of the IEEE 802.11p standard. However, if there are two antennas, the first one is tuned to the CCH, while the second one is tuned to the SCH, which will eliminate the need for any channel switching operation and thus enable each vehicle to broadcast safety messages throughout the 50 ms of the CCHI without a Guard Interval. Figure 2.6: Channel access time in IEEE 802.11p standard Moreover, IEEE 802.11p is currently the standard for Wireless Access in Vehicular Environment (WAVE). • Wireless Access in Vehicular Environment WAVE: WAVE is a mode of operation which is used by IEEE 802.11 devices to operate in the DSRC band. It is a protocol stack that defines the functions of protocols in each layer in VANETs, and describes the interaction between each layer and its upper and lower layers. As shown in Figure 2.7, the WAVE stack incorporates a number of protocols in conjunction with the family of the IEEE 1609 standards [22]. These include IEEE 1609.1 WAVE resource manager, IEEE 1609.2 WAVE security services for applications and management messages, IEEE 1609.3 WAVE networking services and IEEE 1609.4 WAVE multi-channel operation.

range of wireless access technologies including 2G/3G/LTE, wireless broadband access (e.g., WiMAX), IEEE 802.11, to provide broadcast, unicast, and multicast communications between mobile nodes, between mobile nodes and the infrastructure, and between fixed infrastructures

[START_REF]The CALM Forum Ltd[END_REF]

. A fundamental ability Figure 2.7: Protocol stack of WAVE

of the CALM concept is to support media-independent handovers between the various access technologies. This means that mobile nodes are not limited to a single access technology and are able to make an optimal decision to use the most appropriate access technology for message delivery. Moreover, in order to support vehicular ad hoc networking, CALM M5

[START_REF]Intelligent Transport Systems -Communications access for land mobiles (CALM) -M5[END_REF]

has been developed based on IEEE 802.11p, for V2V and for V2I communications. CALM M5 is intended for real-time road safety applications requiring bounded access channel delays and low communication overhead. A dedicated frequency band is allocated to such applications, while another frequency band is allocated to non-safety applications with more relaxed latency requirements

[START_REF] Hakegard | Assesssment of wireless technologies[END_REF]

.

• ETSI TC ITS: ETSI [39] has established a Technical Committee TC ITS (Intelligent Transportation System) in order to develop standards and specifications for the use of communication technologies in transport systems

[START_REF] Hess | Towards Standards for Sustainable ITS in Europe[END_REF]

.

  Frequency Division Multiple Access (FDMA) and Code Division Multiple Access (CDMA). These protocols allow each vehicle to access the channel by a predetermined time slot, frequency band or code sequence, respectively. The major advantage of such protocols is that there are no message collisions between vehicles in the same two-hop neighborhood.

	literature for inter-vehicle communications including Time Division Multiple Access
	(TDMA),
	.1 represents a classification of MAC protocols for
	VANETs. Contention-based MAC protocols represent the majority of MAC pro-
	tocols proposed for VANETs. There is no predetermined schedule and they allow
	vehicles to access the channel randomly when they need to transmit. As a result,
	transmission collisions are inevitable when the network load is high. The current
	IEEE 802.11p standard, which is presented in the previous section, is a contention-
	based protocol which can not guarantee the QoS requirements for critical road safety
	applications. Several techniques have been proposed to improve the scalability of
	contention-based MAC protocols under heavy load conditions in VANETs, see [60,61].
	These mechanisms consist in adaptively adjusting the most important parameters of
	the IEEE 802.11p standard, namely the physical carrier sense threshold, the mini-
	mum contention window, and the transmission power control. Khoufi et al. in [62,65]
	have applied the Transmit And Reserve (TAR) 1 channel access protocol, to vehicu-
	lar communications, especially for safety critical situations. Unlike contention-based
	MAC protocols, contention-free MAC protocols require a predetermined channel ac-
	cess schedule. Several contention-free MAC protocols have been proposed in the

Table 3 . 1 :

 31 Comparison of contention-based and TDMA-based MAC protocols in high load conditions

		Channel utilization	Collision rate	Throughput	Access delay	Fairness	Packet loss
	Contention-based	Inefficient	High	Medium	Unbounded	No	High
	MAC (CSMA/CA)
	Contention-free	Efficient	Low	High	Bounded	Yes	Low
	MAC (TDMA)

Table 3

 3

	.1 compares the performance and features of contention-based MAC pro-
	tocols and TDMA-based MAC protocols in high load conditions.

Table 3 . 2 :

 32 Qualitative comparison of TDMA-based MAC protocols in flat-based network topology

	HERMAC
	CFRMAC
	CSTDMA
	ATSA
	VeMAC
	DMMAC
	SOFTMAC
	STDMA
	VeSOMAC	[92]
		References

  has been developed to support both traffic safety applications and a wide range of non-safety applica-

	tions. Moreover, CBMMAC combines contention-free and contention-based MAC
	protocols. It redefines the functions of the seven DSRC channels, where CH178 and
	CH174 are respectively the Inter-Cluster Control (ICC) channel and the Inter-Cluster
	Data (ICD) channel. Ch172 is the Cluster Range Control (CRC) channel, and the
	remaining channels (Ch176, 180, 182, and 184) are the Cluster Range Data (CRD)

Table 3 . 3 :

 33 Channel allocation and MAC protocols used by CBMMAC scheme

	Vehicle State	TransceiverChannel MAC Protocol	Message Type
	Cluster Head CH	1	CRC	TDMA-based MAC	Safety/Control
		2	ICC	IEEE 802.11 MAC	Consolidated safety
	Cluster Member CM	1	CRC	TDMA-based MAC	Safety/Control
		2	CRD	Centralized Multichan-	Service
				nel Control Allocation
		2	ICD	IEEE 802.11 MAC	Service
	Quasi-Cluster HEAD QCD	1	ICC	IEEE 802.11 MAC	Safety
		2 (off)	--	--	--
	Quasi-Cluster Member QCM	1	ICC	IEEE 802.11 MAC	Safety
		2	CRC	TDMA-based MAC	Resume the communications
					with the previous CH

  Guo et al. in[START_REF] Guo | R-MAC: Risk-Aware Dynamic MAC Protocol for Vehicular Cooperative Collision Avoidance System[END_REF] propose an extension scheme of ACFM, named Risk-Aware Dynamic MAC Protocol for Vehicular Cooperative Collision Avoidance System. The goal of the research is to design a risk-aware dynamic medium-access control (R-MAC) protocol tailored to Cooperative Collision Avoidance CCA applications. One key element of CCA systems is the real-time and reliable delivery of warning messages as well as beacons between vehicles. As for the ACFM protocol, each frame is divided into an RSU segment and a vehicle segment. The RSU segment is reserved for RSUs to disseminate control messages. However, in contrast to the ACFM protocol, the vehicle segment is divided into two segments: a CSMA segment which is a contention-based segment, responsible for transmitting warning messages in emergency situations, and a TDMA segment which is a contention-free segment and used

Table 3 . 5 :

 35 Qualitative comparison of TDMA-based MAC protocols in centralized Analysis of the TDMA-based MAC protocols based on the MAC QoS metrics66

	network topology
		ACFM	R-MAC	CBRC	UTSP
	Channel	Single	Single	Single	Multiple
	Pure TDMA	No{TD,FD}MA	No{TD, CS}MA	No{TD, FD}MA	Yes
	Inter-RSU interference	Solved	Solved	Solved	Possible
	Access collision	Solved	Solved	Solved	Solved
	Mobility	High	High	High	Medium
	Density (scalability)	High	High	Low	Low
	Broadcast service	Yes	Yes	Yes	No
	Mobility model	Highway	Highway	Highway + Junctions	Highway
	Vehicular traffic	N/A	Unidirectional	Unidirectional	Bidirectional
	Traffic load	High load	High load	High load	High load
	Control overhead	Low	Low	Low	Medium
	Transmission range	N/A	Low	Low	Medium
	Multimedia applications	No	No	Yes	Yes
	Real-Time applications	Yes	Yes	Yes	No
	Positioning System GPS	Yes	Yes	Yes	Yes
	Time Synchronization	Yes	No	No	Yes
	Simulator	NS2	NS2	NCTUns 5.0 [113]	N/A

Table 3 .

 3

	6: Comparison of different categories of TDMA-based MAC protocols
		TDV Protocols TCBT Protocols TCT Protocols
	Complexity	High	Medium	Low
	Cost	Low	Low	High
	Overhead	High	Medium	Low
	Generic	Yes	No	No
	3.9 Open research issues
	In this chapter, we have given an overview of several scheduling-based MAC pro-

tocols developed for VANETs and which use TDMA. Although the research tries to improve the performance metrics of MAC protocols in VANETs, there remain a number of MAC research challenges and open questions that must be addressed to enable VANETs to support both safety and non-safety applications. In this section, we highlight some open issues in this field which may become new research areas in the future.

Table 4 .

 4

	1: Simulation parameters
	Parameter	Value
	Highway length	2 km
	Lanes/direction	2
	Vehicle speed	120 km/h
	Speed standard deviation (σ) 30 km/h
	Transmission range	300 m
	Slots/frame	100
	Slot duration	0.001 s
	Simulation time	120 s

Table 5 .

 5

	1: Simulation parameters
	Parameter	Value
	Highway length	3 km
	Lanes/direction	2
	Vehicle speed	120 km/h
	Speed standard deviation (σ) 30 km/h
	Transmission range	310 m
	Slots/frame	100
	n 0	τ /3
	n 1	τ /3
	n 2	τ /3
	α	0.4
	Slot duration	0.001 s
	Simulation time	120 s

  is to avoid using the re-clustering algorithm and thus no re-clustering overhead is generated when the CH leaves the cluster. Then, the current CH will order the CM to switch to CH and switch its own state to CM. Each cluster head periodically broadcasts an ITJ messages to its one-hop neighbors.Once a US or CHC vehicle receives an ITJ message, and if it wishes to join the cluster, it will check the received signal strength. The US or CHC vehicle will consider the ITJ message to be valid if its signal strength is greater than the predefined threshold denoted by Pr Threshold. When receiving a valid ITJ message, the vehicle sends a Request-To-Join (RTJ) message including the vehicle's ID, road ID and direction. When the CH receives the RTJ message, it checks the road ID on which the requesting vehicle moving and, if it is moving in the same direction, the CH sends an acknowledgment (ACK) including its ID number. After the reception of the ACK, the corresponding vehicle becomes a CM of this cluster. Once a US vehicle becomes a CM, it is not allowed to participate in another cluster head election procedure.Moreover, if a CM receives an ITJ message from another neighboring CH moving on the same road and in the same direction, the vehicle will switch from the CM state to the CG state. Figure6.3 shows the vehicle state transitions diagram. When the CM vehicle does not receive an ITJ message from its CH during CH Timeout Interval, it considers that it has lost contact with the CH and thus switches its state to CHC. Each CH updates a time stamp field for each CM based on the presence messages (PRE-MSG) received. The CH removes a CM from its cluster members list if the difference between the current time and the last time stamp of the PRE-MSG message received from it is greater than CM Timeout Interval. The CH will change its state to CHC, if its list of cluster members is empty.

	6.4.3.1 Join a cluster
	6.4.3.2 Leaving a cluster
	A vehicle remains in the CM state as long as it receives an ITJ message from its CH
	every ITJ Interval.
	31:	CH -ID ← v
	32:	end if
	33:	end while
	34:	end if
	35: end while

Table 6 .

 6

	2: AWCP parameters
	Parameter	Type Lower bound	Upper bound
	Hello Interval	R	0.5	15
	Election Interval	R	0.5	15
	ITJ Interval	R	1	15
	PRE Interval	R	1	15
	CH Timeout Interval	R	2	45
	CM Timeout Interval	R	3	45
	Cluster Size	Z	1	(R * l) * 2/(w + d)
	Pr Threshold	R	P min	P max
	Distance Weight factor (w 1 )	R	0	1
	Speed Weight factor (w 2

R

  7, NSGA-II begins from an initial population (P) made up of solution vectors called "individuals". At each iteration, an auxiliary population Itr ← P Itr ∪ {Q Itr }

	Algorithm 7 NSGA-II algorithm for AWCP optimization
	Input N, P c , P m , N br iteration max
	1: Itr ← 0
	2: P Itr ← {∅}
	3: initialize P Itr=0 = { -→ x i Itr=0 , . . . , -→ x N Iter=0 }
	4: evaluate P Itr=0
	5: while (Itr < N br iteration max) do
	6:	Q Itr ← {∅}
	7:	while (t ≤ popSize/2) do
	8:	parents ← selection(P Itr )
	9:	Child ← crossover(P c , parents)
	10:	E ← mutation(P m , Child)
	11:	compute objective values(Child)
	12:	Q Itr ← Q Itr ∪ {Child}
	13:	end while
	14:
	15:	R Itr = r i=1 F i and F 1 < F 2 < . . . < F r
	16:	P Itr+1 ← {∅}; i ← 0
	17:	while (|P Itr+1 | + |F i | < N ) do
	18:	P Itr+1 ← P Itr+1 ∪ F i
	19:	i ← i + 1
	20:	end while
	21:

Table 6 .

 6

		3: VANETs scenarios
	Scenario	Number of vehicles Number of CBR sources
	Low (S1)	25	5
	Medium (S2)	50	15
	High (S3)	100	25
	Very High (S4)	150

Table 6 .

 6 5 shows the solutions that give the best values for each AWCP QoS metric, which are the maximum ACL (max-ACL), maximum PDR (max-PDR), and minimum CPO (min-CPO), and the average values of the τ non-dominated solutions obtained on the Pareto front. As shown in this table, in our case the ideal vector has three values : 94.06, 91.39, 3.82. Moreover, the Euclidean distance of each solution in the non-dominated set to the ideal objective vector is calculated and the solution with the smallest Euclidean distance is selected (min-EUDT).

Table 6 . 5 :

 65 NSGA-II simulation results and optimized configuration EUDT ) presents the best trade-off between the three QoS metrics, since the min-EUDT configuration gives the best objective values for each QoS metric. The max-ACL configurations achieve a high cluster lifetime and have a high packet delivery performance but the clusters are formed and maintained with an excessive overhead (12.68%). The configuration that optimizes the PDR metric, max-PDR, delivers an important amount of data packets. However, it decreases the performance of the AWCP protocol in terms of ACL (79.71s). The configuration that creates clusters with the least overhead min-CPO, produces a significant reduction in the performance of AWCP in terms of ACL (45.81s) and it delivers a low packet delivery ratio although it has the advantage of fewer control messages. The min-EUDT AWCP configuration found by NSGA-II which is the most balanced setting of parameters on the Pareto front is Hello Interval =0.78, Election Interval =0.16, ITJ Interval =7.23, PRE Interval =9.16, Pr Threshold = 7.23E-16, CH Timeout Interval =12.75, W 1 = 0.716 CM Timeout Interval =12.7,Cluster Size=50, W 2 = 0.204, and W 3 = 0.07.

	Configuration	ACL	PDR	CPO EUDT
	max-ACL	94.06 s 89.05% 12.68%	9.16
	max-PDR	79.71 s 91.39% 7.15%	14.73
	min-CPO	45.81 s 87.46% 3.82%	48.41
	NSGA-II avg 72.75 s 86.92%	6.69%	21.97
	min-EUDT	90.02 s 88.54%	6.72%	5.73
	We can note that the closest configuration to the ideal objective vector (min-

Table 6

 6

	.6. To

Table 6 .

 6 7 presents the average (and the standard deviation) of the four metrics as well as the computational time taken by each MOEA over 15 independent runs. This table shows that the NSGA-II is significantly better than the other two MOEAs in terms of both sparsity, spacing, inverse generational distance and the ratio of non-dominated solutions. The average number of non-dominated solutions found by NSGA-II in the 15 independent runs is 80.49%, 85.16%, 83.61% and 86.56% for the S1, S2, S3 and S4 scenarios, respectively. Therefore, the NSGA-II algorithm provides a wide range of non-dominated solutions in every run, whilst MOPSO and MODE give a small number of solutions along the Pareto front. Table6.7 also shows that all the MOEOs take almost the same computational time. This is due to the fact that all the algorithms have the same number of fitness function evaluations. It can be seen that the Pareto fronts obtained by NSGA-II are the best regarding the spacing and spread metrics on all the test scenarios except for the S4 scenario, where MOPSO is the best in terms of the spread metric. The lowest spacing in scenario S3 is found by NSGA-In this section, we evaluate and compare the performance of AWCP with other well known clustering protocols proposed in the literature, namely WCA, LID, HD and CPM presented in Section 6.3. Figure6.8 shows the ACL of all the algorithms for different VANET scenarios. This figure shows that the ACL is increased by

	II with 51.7364.81% respectively better compared to MODE and MOPSO, and the
	largest spread is also found by NSGA-II (38% better, on average). Thus, the Pareto
	front solutions obtained by NSGA-II are better distributed with respect to the MODE
	and MOPSO. Similarly, in terms of inverse generational distance, NSGA-II had the
	best performance (both in terms of average value and standard deviation). Therefore,
	with respect to the performance metrics used for comparison, we can conclude that
	NSGA-II is the most suitable for the AWCP tuning problem. Moreover, the results
	show that MOPSO and MODE are both the second best with respect to spread,
	spacing metrics and inverse generational distance, and they are clearly the worst ones
	in terms of the ratio of non-dominated solutions
	6.6.3 AWCP performance evaluations

Table 6 .

 6 7: Performance comparison of the three MOEAs for the S1, S2, S3 and S4 scenarios. 6%, 62.2%, 59% and 45.5% on average when AWCP is used compared to the WCA, HD, LID, and CPM protocols. Therefore, we can conclude that the protocol proposed provides stable clusters which have a long lifetime. As AWCP takes into account road IDs and movement directions to form clusters, the CMs will be associated with their CHs for a longer period of time. We can also note that CPM performs better than WCA, LID and HD, because the CPM protocol forms clusters based on the mobility direction. The Clustering Protocol Overhead (CPO) of AWCP and the other protocols for various VANETs scenarios is shown in Figure6.9.It is clear from this figure that our protocol has a lower overhead than the other protocols. In fact, AWCP reduces the CPO by respectively 38.8%, 37.2%, 37.1% and 47.2% on average compared to WCA, HD, LID and CPM. There are two reasons

	Time (s)	AVG Sd. Dv	13714 9.2089	13709 1.5159	13709 1.7092	20371 15.427	20377 25.947	20365 2.2152	37622 8.7865	37621 12.347	37622 10.247	61610 54.656	61640 62.569	61636 47.275
	VANET MOEA Spacing Spread Genera. Dist Ratio of Non-dom	Sd. Dv Scenario AVG Sd. Dv AVG Sd. Dv AVG Sd. Dv AVG	0.029 NSGA-II 4.1489 1.3715 65.095 17.389 5.4758 1.1103 0.8049	0.0228 S1 MOPSO 8.7738 5.6502 64.690 16.728 7.8874 1.9543 0.3395	0.0816 MODE 5.5035 3.7038 41.039 9.012 9.0199 1.0459 0.3221	0.0379 NSGA-II 3.5356 1.3941 83.369 2.8632 2.9251 0.3465 0.8516	0.0382 S2 MOPSO 5.7282 3.0834 50.359 17.671 4.5398 0.7974 0.3374	0.04 MODE 6.0314 2.8168 53.727 4.8251 4.1715 0.5174 0.3354	0.0455 NSGA-II 2.6947 0.4488 63.215 11.051 3.1949 0.5783 0.8361	0.0211 S3 MOPSO 4.0883 4.6216 31.327 13.013 6.2029 1.5451 0.4447	0.071 MODE 4.4441 2.144 47.068 10.967 4.8543 0.4868 0.4047	0.0248 NSGA-II 2.9067 0.4681 56.359 13.905 4.072 1.1754 0.8656	0.0163 S4 MOPSO 3.725 0.5564 51.022 23.518 6.4324 2.4138 0.3632	0.0415 MODE 6.9209 1.4751 68.443 3.5244 4.7408 0.5202 0.4171	A bold font indicates the best metric value.

why AWCP decreases the overhead. Firstly because the maximization of the cluster heads' duration and the cluster members' duration decreases the number of control messages required to elect new cluster heads and to join a new cluster, respectively.

  When a vehicle receives an SA message, and if it wishes to access the channel, it tries to get the attention of the RSU by sending it a Slot REQuest message (SREQ) including its identity. Algorithm 8 outlines the details of the slot reservation mechanism. v represents the vehicle that needs to reserve a time slot, timer 1 is a timer and T S(v) is the time slot that is successfully acquired by vehicle v. When an RSU receives the SERQ message, it checks whether there is an available time slot and, if there is, the RSU sends a Slot REPly message (SREP) to the corresponding vehicle including Otherwise, if the timer expires and no response has been received from the RSU (lines 12-14), the vehicle v will repeat the same steps. If a vehicle receives an SA message from another RSU (line 17), the vehicle will send an SREQ to allocate a new time slot and if it receives an SREP from the RSU it will release its current time slot and it will start to broadcast its packet during the time slot allocated by the new RSU.

	6: end if
	7: while timer 1 ! = 0 do
	10:	end if
	11: end while
	13:	go to 2.
	18:	go to 2.
	19:	end if
	20: end while

8:

if vehicle v receives an SREP message from RSU u then 9: vehicle v starts to broadcast its message during the time slot SREP -> SLT ID.

12: if (time 1 == 0) and (T S(v) == ∅) then 14: end if 15: // TDMA schedule maintenance 16: while T S(v)! = ∅ do 17:

if M Y RSU ID! = SA-> N ODE ID then the slot index (SREP -> SLT ID). After the reception of the SREP, the vehicle v starts to broadcast its message during its time slot, T S(v) = SREP -> SLT ID.

Table 7 . 1 :

 71 The slot assignment obtained with ASAS

	Slot	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
	Cluster1										I	1	2	3	4	5	-1	-1	-1
	Cluster2										8	9		-1	-1	-1	II	6	7
	Cluster3	10	12		-1	-1	-1	III	11	13
	Cluster4	IV	17	18	14	15	16	-1	-1	-1

  Contents 8.1 Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 8.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 8.2.1 Consideration of multiple MAC metrics . . . . . . . . . . . 164 8.2.2 Wide range of applications . . . . . . . . . . . . . . . . . . 164 8.2.3 Reserved versus random access . . . . . . . . . . . . . . . . 164 8.2.4 Multichannel operation . . . . . . . . . . . . . . . . . . . . 165 8.2.5 Mobility scenario . . . . . . . . . . . . . . . . . . . . . . . . 165

The channel contention area is the region within which simultaneous transmissions from two vehicles can collide at the same destination.

Transmit And Reserve is a per-packet coordinated channel access scheme for IEEE 802.11 wireless networks. TAR avoids selecting Backoff values that have already been selected by other nodes.

Global Positioning System

Global System for Mobile communications

The set of one-hop neighbors of any vehicle x is the set of vehicles that are within transmission range of vehicle x.

The set of two-hop neighbors of any vehicle x is the set of vehicles that can be reached at a maximum of two hops from vehicle x.

AODV is defined in[START_REF] Perkins | Ad hoc on demand distance vector routing[END_REF]

Random TDMA is defined in[START_REF] Rhee | DRAND: Distributed randomized tdma scheduling for wireless ad hoc networks[END_REF]

Flooding based routing protocol is defined in[START_REF] Ko | Flooding-based geocasting protocols for mobile ad hoc networks[END_REF]

A Multi-Head Clustering Algorithm, called Center-Position and Mobility (CPM), was proposed in [START_REF] Lo | A Multi-Head Clustering Algorithm in Vehicular Ad Hoc Networks[END_REF]. This technique aims to create stable clusters and reduce reclustering overhead by supporting single and multiple cluster heads. In the cluster head election phase, vehicles within communication are organized into clusters and one vehicle for each cluster is elected to act as a Master Cluster Head (MCH). Then, some cluster members in the cluster are selected to be Slave Cluster Heads (SCHs).

In order to form stable clusters, the authors imposed that all the vehicles in a cluster are moving in the same direction. In [START_REF] Rawashdeh | A novel algorithm to form stable clusters in vehicular ad hoc networks on highways[END_REF], the authors proposed a multi-metric algorithm for cluster head elections, called Threshold-based Technique (TB), suitable for highway area. In addition to the position and the direction, this algorithm uses a speed difference metric as a new parameter to increase the cluster lifetime. The vehicles that are moving at high speed are regrouped into one cluster, while the vehicles moving at low speed are grouped into another cluster.

Several other clustering algorithms designed for MANETs are also used in VANETs and are frequently employed for comparison with other VANET clustering protocols.

For instance, the Lowest-ID clustering algorithm (LID) [START_REF] Gerla | Multicluster, mobile, multimedia radio network[END_REF] is based on electing a node with the smallest ID as a cluster head, where each node has a fixed ID. The Highest Degree algorithm (HD) [START_REF] Ramalingam | Associativity based cluster formation and cluster management in ad hoc networks[END_REF] selects a node as a cluster head based on the nodes' connectivity. The node with the maximum number of neighbors becomes the cluster head. MOBIC [START_REF] Basu | A mobility based metric for clustering in mobile ad hoc networks[END_REF] is a Mobility based clustering algorithm designed for MANETs which is also used in VANETs. MOBIC is a mobility based version of the Lowest-ID algorithm and uses a signal power level metric to elect cluster heads. The Weighted Clustering Algorithm (WCA) [START_REF] Chatterjee | A weighted clustering algorithm for mobile ad hoc networks[END_REF] elects a node to act as a cluster head based on a combined weight which includes its average speed, and battery-life, the number of its neighbors and their average. Q is formed by applying the crossover and mutation operators (lines 7 to 13). Then, both the current (P) and the new population (Q) are merged together to form one set of solutions R, which will be sorted according to the non-domination and crowded comparison (line 15). For more details, one can see [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF]. Finally, only the best individuals in R can be included in the next generation and will participate in the production step while the other individuals are deleted (lines 17 to 23). These steps are repeated until the maximum number of iterations is reached. Each individual i in iteration l is encoded as a multi-dimensional vector -→ x i itr=l = (x i 1 , . . . , x i n ) T . Each gene that encodes one AWCP parameter is defined by its type (real, integer), bounds and its precision p. The initial population P Itr=0 = { -→ x i Itr=0 , . . . , -→ x N Itr=0 } is generated by randomly choosing the value of each gene in its variation range (lower(x i ), upper(x i )).

Where N is the population size, n is the vector's dimension. Thereafter, the initial population is used by the circulated genetic operators to create a new population.

The crossover operator is one of the main parts of NSGA-II. The input of this operator consists of two solution vectors (known as parents), while the output is two child vectors, which have certain features from both parents [START_REF] Hadded | Combining Genetic Algorithm and Simulated Annealing Methods for Reconstructing HV-Convex Binary Matrices[END_REF] (see Figure 6.6). Because all the genes in each solution vector of the population are within