Mohamed Hadded
email: mohamed.hadded@telecom-sudparis.eu

Paul Mühlethaler

Anis Laouiti
email: anis.laouiti@telecom-sudparis.eu

Rachid Zagrouba
email: rachid.zagrouba@cristal.rnu.tn

Leila Azouz Saidane
email: leila.saidane@ensi.rnu.tn

Paul Muhlethaler
email: paul.muhlethaler@inria.fr

• R Zagrouba

TDMA-based MAC Protocols for Vehicular Ad Hoc Networks: A Survey, Qualitative Analysis and Open Research Issues

Keywords: VANET, MAC Protocols, TDMA, QoS, V2V, V2I, collision-free, IEEE 802.11p, DSRC, Ad hoc !

published or not. The documents may come   L'archive ouverte pluridisciplinaire

INTRODUCTION

V Ehicular Ad hoc NETworks (VANETs) are primarily designed to improve safety on roads. They can also be used to improve traffic management conditions and to provide on-board infotainment such as Internet access, video streaming, etc. VANETs are an example of Mobile Ad hoc NETworks (MANETs) but with their 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 VANETs, communications can either be between vehicles V2V (Vehicle To Vehicle) or between vehicles and road side units V2I [START_REF] Tse | Improving message reception in vanets[END_REF] (Vehicle To Infrastructure). The applica-tions for V2V and V2I can be divided into the following three services: safety services, traffic management and user-oriented services [START_REF] Hartenstein | A tutorial survey on vehicular ad hoc networks[END_REF], [START_REF] Toor | Vehicle ad hoc networks: applications and related technical issues[END_REF]. 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. Medium Access Control will play an important role in satisfying these requirements.

In VANETs, the 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, channel sharing is the key issue when seeking to provide a high quality of service. Medium Access Control (MAC) schemes must be designed to share the medium between the different nodes both efficiently and fairly. However, due to the special characteristics of VANETs, which will be described in more detail in Section 3, 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: contentionbased 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 [START_REF] Ye | Congestion control to achieve optimal broadcast efciency in vanets[END_REF]. 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 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 this may cause problems such as packet loss, or large access delay. On the other hand, contentionfree 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 networks, MAC protocols must offer an efficient broadcast service with predictable bounded delays. 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 networks -specific 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 Std[END_REF], which is the emerging standard deployed to enable vehicular communication, is a Contention-based MAC protocol, using a prioritybased 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 tutorial[END_REF]. As shown in Section 4.3, the IEEE 802.11p standard does not provide a reliable broadcast mechanism with bounded communication delay. This disadvantage is particularly important 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 challenging task.

Currently, a great deal of research work on contentionfree 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 1 . 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 fre-quency. 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. By providing, in principle, Collisions may however occur with TDMA, this is discussed in Section 7.1 collision-free transmission with bounded access delay, TDMA is better suited to the requirements of VANETs. 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 collision, in order to operate efficiently they must be aware of the neighbors' slot allocation. 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 which can affect the performance of these protocols. Therefore, the scheduling mechanism in TDMA protocols should take into consideration the mobility features of VANETs so as to avoid collisions. Several TDMA-based MAC protocols such as VeMAC [START_REF] Omar | Vemac: A tdma-based mac protocol for reliable broadcast in vanets[END_REF], TC-MAC [START_REF] Almalag | Tdma cluster-based mac for vanets (tc-mac)[END_REF] and ACFM [START_REF] Guo | An adaptive collision-free mac protocol based on tdma for inter-vehicular communication[END_REF] proposed in the literature address the TDMA issues in such mobility scenarios. These protocols will be discussed in the next sections. In this paper, 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 as well as how well they can handle the highly dynamic topology and the various conditions of vehicular density that are often present in VANETs.

The remainder of this paper is organized as follows. In Section 2, we present an overview of the state of the art. Section 3 briefly introduces the characteristics of VANETs. In Section 4, we present an overview of many inter-vehicle communication standardizations and projects that are being developed for VANETs. Section 5 introduces a general classification and the design issues of MAC protocols in VANETs. Section 6 provides the framework of TDMA-based MAC protocols and presents a novel topology-based classification of these protocols. Following our classification, Sections 7, 8 and 9 introduce and evaluate several TDMA-based MAC protocols in fully distributed, clustered and centralized VANET topologies, respectively. Section 10 uses QoS MAC metrics to analyze the protocols presented in the three previous sections. Section 11 compares different classes of protocols. Section 12 discusses certain TDMAbased MAC research challenges and open questions. Finally, the conclusion is given in Section 13.

RELATED WORK

Many survey papers in the literature have been written in order to summarize and categorize MAC QoS issues and solutions for VANETs. The work in [START_REF] Park | Survey of mac protocols for vehicular ad hoc networks[END_REF], surveys some aspects and the role of MAC protocols in Vehicular Ad-Hoc Networks. The authors in this article outline MAC protocols in VANETs without any detailed analysis and classification. Menouar et al. in [START_REF] Menouar | A survey and qualitative analysis of mac protocols for vehicular ad hoc networks[END_REF] survey a number of MAC protocols designed for MANETs. However, the most recent protocol discussed in this article was published in 2004. Then a qualitative comparison is given between those that can be adapted for VANETs, i.e. ADHOC MAC and IEEE 802.11. The two protocols are analyzed according to certain characteristics such as time synchronization based, multicast/broadcast based, mobility-aware, and QoS and real-time capability. Booysena et al. in [START_REF] Booysena | Survey of media access control protocols for vehicular ad hoc networks[END_REF] provided an overview of many V2V MAC protocols including various VANET standards that were proposed for VANETs in 2009 and 2010. The authors focused on the benefits and limitations of the MAC protocols proposed. Their conclusions highlighted some challenges that still need to be addressed in future work to enable the implementation of highly efficient MAC protocols for VANETs. These challenges are outlined below:

• Contention-free protocols can satisfy QoS requirements for real-time applications but they need a high level of coordination due to the special characteristics of VANETs.

• Contention-based protocols are not suitable for important safety messages due to their unbounded delay and low performance in highly dense networks. Finally, some multi-channel MAC protocols proposed both for MANETs and VANETs to take full advantage of the seven available channels were surveyed in [START_REF] Kakarla | A survey and qualitative analysis of multi-channel mac protocols for vanet[END_REF]. The authors also provided a short overview of many issues involved in the design of multi-channel MAC protocols in VANETs. The novelty of our survey with respect to other survey papers in the same area is that it focuses on certain specific MAC protocols, namely those that are based on the TDMA method and it gives a novel topology-based classification of these protocols. We discuss and analyze them from a design perspective, i.e. how to coordinate channel access for neighboring vehicles, how to adapt the TDMA method to the particular characteristics of VANETs, how to optimize TDMA-based MAC protocols, what mobility scenarios and which metrics can be used to evaluate the performance of such protocols. In this paper, we provide an in-depth and comprehensive overview of many recent TDMA-based MAC protocols according to the nature of the topology of the network and we discuss how well these protocols address the above issues. The main contributions of the paper are listed below:

• We review the features of VANETs and the recent standardization activities in the field, together with their shortcomings at the MAC layer. • We give an insight into general VANET MAC protocol design issues, and we set out the reasons for using collision-free medium access control, e.g. TDMA, in VANETs. • We classify the recent TDMA-based MAC protocols into three different categories based on the network topology. For each category, we -Identify and describe the TDMA problems that can occur in each topology. -Review and discuss the available TDMA-based MAC protocols in the literature, and highlight their strengths and weaknesses. -Provide a comparison of these protocols for QoS provisioning in VANETs.

• We provide a statistical analysis to draw several important conclusions, e.g. to identify the most widely addressed MAC issues over recent years, and which QoS parameters have been the most studied. • The various protocols we survey enable us to establish some important research challenges related to TDMA-based MAC protocols in VANETs.

CHARACTERISTICS OF A VANET

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 selforganization of the nodes, but they also differ in some ways such as network infrastructure components and a highly dynamic topology. Figure 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, in which the vehicles can communicate with each other in an ad hoc fashion, and vehicle-to-roadside communication V2I, where the road-side-units (RSUs) are used as access points to connect moving vehicles to the network infrastructure which is connected to the Internet [START_REF] Moustafa | Vehicular networks: Techniques, standards, and applications[END_REF]. 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. However, 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 MAC 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 a MAC protocol that can dynamically adapt to frequent changes of topology due to the nodes' high mobility and their different speeds. Clearly, this high mobility also has an impact on the routing strategy, but the performance of the routing protocols will greatly depend on an efficient MAC protocol.

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. GPS, the Global Positioning System [START_REF] Hofmann-Wellenho | Global positioning system: Theory and practice[END_REF], [START_REF] Kaplan | Understanding gps: Principles and applications[END_REF], 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. It is also possible to test the performance of MAC 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 requirements. Real-time applications require guaranteed access to the channel and have strict requirements regarding end-toend 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, highthroughput, and 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]. In the next section, we review the recent research projects in the field of VANETs and VANET standardization efforts in Europe and beyond.

VANET RESEARCH AND STANDARDIZATION

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] Jiang | Design of 5.9 ghz dsrc based vehicular safety communication[END_REF] was initially coined in USA [START_REF] Shulman | Safety communications in the united states[END_REF] by the FCC (Federal Communication Commission) [21]. It was developed to support vehicle-to-vehicle and vehicle-to-infrastructure 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). These channels are divided functionally into one control channel 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 1 shows a comparison between different regional standards for DSRC [START_REF] Kudoh | Dsrc standards for multiple applications[END_REF]. More detailed information on regional standards for DSRC is available in [START_REF] Bilstrup | Vehicular communication standards-dsrc, calm m5, wave and 802.11p[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 networks -specific 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 Std[END_REF] standard was adopted as the Medium Access Control (MAC) and Physical Layer (PHY) specifications for the lower-layer DSRC standard.

IEEE 802.11p

The IEEE 802.11p [START_REF]IEEE standard for information technology -Telecommunications and information exchange between systems -local and metropolitan area networks -specific 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 Std[END_REF] standards, which improve the existing IEEE 802.11 [START_REF]Wireless LAN medium access control (MAC) and physical layer (PHY) specifications Std[END_REF] to support VANETs, have been proposed by the Task Group p of the IEEE. This standard improves QoS by using the Enhanced Distributed Channel Access (EDCA) functionality, derived from the IEEE 802.11e standard [START_REF] Uzcátegui | Wave: A tutorial[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 Draft Standard[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 3. 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 multichannel 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. proposes a comprehensive mobile network architecture called Communications Access for Land Mobiles (CALM) [START_REF]Intelligent Transport Systems Communications Access for Land Mobiles (CALM) Architecture Std[END_REF]. CALM uses a wide 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 handbook Std[END_REF]. A fundamental ability 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 Std[END_REF] has been developed based on IEEE 802.11p, for V2V and for V2I communications. CALM M5 is intended for realtime 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 nonsafety applications with more relaxed latency requirements [START_REF] Hakegard | Assesssment of wireless technologies[END_REF].

ETSI TC ITS ETSI [34] 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]. TC ITS is organized into five working groups: WG1 -User Application requirements, WG2 -Architecture and cross layer issues, WG3 -Transport and Network, WG4 -Media and related issues, and WG5 -Security. In WG3 for example, they are interested in geographic addressing and routing. Moreover, ETSI TC ITS has converged in harmonization with ISO TC204 WG16 towards the ITS communication architecture, known as the ITS station architecture [START_REF]Intelligent transport systems -Communications access for land mobiles (CALM) Architecture Std[END_REF], [START_REF]Intelligent Transport Systems (ITS)[END_REF].

Projects

Several European, American and Japanese research projects are currently dealing with vehicular communi-cations. FleetNet [START_REF]Fleetnet-internet on the road[END_REF] 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] Figure 5 shows some projects that have been funded by the European Union, the governments of the USA and Japan. These include COMeSafety [42], GeoNET [START_REF]Geonet project (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 intervehicle communicatio[END_REF], coopers [START_REF]Coopers project[END_REF], euroFOT [47], PRE-DRIVEC2X [START_REF]Pre-drivec2x eu project[END_REF] and evita [49] 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

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]. Moreover, in order to collaborate on the common goals, many standardization organizations in Europe such as ETSI ITS are cooperating with world standardization bodies such as IEEE [51], ISO [52] and IETF [53] (see Figure 5). Despite these standardization efforts and research activities which aim to enable the expected VANET services to operate efficiently in vehicles on roads, there are still some open issues that need to be further studied by the standardization organizations. Firstly, safety applications have strict QoS requirements in terms of delay and loss rate that cannot be guaranteed by IEEE 802.11p, particularly in heavy traffic conditions [START_REF] Abu-Rgheff | Softmac: Space-orthogonal frequency-time medium access control for vanet[END_REF]. Indeed, when the safety messages are transmitted in broadcast mode on the CCH channel, no ACK messages are transmitted to confirm the reception and no RTS/CTS exchange is used. This increases the collision probability in the presence of hidden nodes. For the broadcast mode, no ACK is transmitted because it is not practical to receive an ACK from each vehicle for each message that has been broadcasted. If acknowledgments are used, a problem known as the ACK explosion problem [START_REF] Yao Ni | The broadcast storm problem in a mobile ad hoc network[END_REF] will occur. Moreover, the VCS Virtual Carrier Sensing mechanism is not used for broadcasted messages because it would flood the network with traffic. As a result of employing the enhanced distributed channel access (EDCA) [START_REF]Wireless LAN medium access control (MAC) and physical layer (PHY) specifications Std[END_REF] technique, collisions are possible between messages that have the same Access Category (AC). Another major limitation is that the IEEE 802.11p standard is a Contention-based MAC method that cannot provide a bound on access delays, which is necessary for high priority safety applications [START_REF] Abu-Rgheff | Softmac: Space-orthogonal frequency-time medium access control for vanet[END_REF].

Secondly, in the WAVE standard, a single DSRC radio can switch between the CCH on which safety messages are broadcasted and the SCHs on which unicast data messages are transmitted. Since the DSRC standard uses static time intervals during which the radio is assigned to CCH and SCH channels, the DSRC cannot support both safety and non-safety applications with a high degree of reliability when traffic densities are high. To support safety application requirements and ensure reliability, Wang and Hassan in [START_REF] Wang | How much of dsrc is available for non-safety use?[END_REF] propose maximizing the CCHI and minimizing the SCHI. Their results indicate that as traffic density increases, ensuring CCH reliability requires compromising SCH throughput. Therefore, due to the overhead latency of the channel switching process, safety messages could be lost while the radio is busy switching channels. Thus, retransmissions are usually needed to ensure reliable delivery. It is important to have a multichannel MAC protocol that contains an efficient channel switching algorithm which dynamically maximizes the time interval for real-time safety applications while guaranteeing a high transmission rate for throughput-sensitive applications over the six other service channels (SCHs). Recently, the National Highway Traffic Safety Administration (NHTSA) has assessed the readiness of V2V technology for application implementation in [START_REF] Harding | Vehicle-to-vehicle communications: Readiness of v2v technology for application[END_REF]. In this report, the authors have clearly established the problems of using one single DSRC radio and a consensus is forming that future DRSC devices should be equipped with two antennas, one of which is dedicated to transmitting safety messages. This will negate the need for a channel switching mechanism and will enable the vehicle to broadcast Basic Security Messages (BSMs) immediately and at any time.

Moreover, several standards and projects such as ETSI [34], CALM M5 [START_REF] Hakegard | Assesssment of wireless technologies[END_REF] and C2C-CC [START_REF]Car 2 car communication consortium[END_REF] basically follow the specification of the IEEE 802.11p standard at the MAC layer. This common point can be seen as an advantage for possible interoperability between different systems. But, as this layer is based on CSMA to organize the channel access, it is well-known that collisions may occur when broadcasted messages are transmitted. Moreover this MAC layer does not guarantee bounded channel access delays under high traffic loads. Therefore, they do not meet the inherent QoS requirements for safety applications for vehicle-to-vehicle communication. These issues are very important for VANETs since the reliability of message transmission, the fairness and the correctness of the transfer in a timely manner are the corner stone to all the above communicating layer mechanisms. Safety functions depend on the performance of this lower layer. The MAC layer for VANETs must ensure fairness between all the neighboring cars and must be highly reliable to deliver broadcasted messages efficiently.

In the following section, we analyze and classify the MAC protocols designed for VANETs.

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. Medium Access Control (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 Medium Access Control Protocols

Several MAC protocols have been designed for intervehicle 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 networks -specific 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 Std[END_REF], and the contentionfree medium access method. The third category is a hybrid of the two previous methods. Figure 6 represents a classification of MAC protocols for VANETs.

Contention-based MAC protocols represent the majority of MAC protocols 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 [START_REF] Stanica | Local density estimation for contention window adaptation in vehicular networks[END_REF], [START_REF]Physical carrier sensing in vehicular ad-hoc networks[END_REF]. These mechanisms consist in adaptively adjusting the most important parameters of the IEEE 802.11p standard, namely the physical carrier sense threshold, the minimum contention window, and the transmission power control. Khoufi et al. in [START_REF] Khoufi | Tar channel access mechanism for vanet safety-critical situations[END_REF], [START_REF] Khoufi | Tar channel access mechanism: A study of a highway ramp car merge case[END_REF] have applied the Transmit And Reserve (TAR)2 channel access protocol, to vehicular communications, especially for safety critical situations.

Unlike contention-based MAC protocols, contentionfree MAC protocols require a predetermined channel access schedule. Several contention-free MAC protocols have been proposed in the literature for intervehicle communications including Time Division Multiple Access (TDMA), 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. 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 This paper will assess and highlight MAC protocols using Time Division Multiple Access (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 Global Positioning System (GPS) 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 contentionless 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 medium access control 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 Global Positioning System (GPS) in each vehicle. It is generally assumed that each vehicle is equipped with a positioning system, e.g. GPS, 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 (Federal Communication Commission) [21] 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 useroriented 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 attracted 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 GSM (Global System for Mobile communications) network, Mobile Ad hoc NETworks, Vehicular Ad hoc NETworks, Wireless Sensor Networks, Mesh Networks, etc.

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 7). 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 Fig. 7: The concept of time division multiple access benefits of using TDMA MAC protocols are considerable and can be summarized as follows:

• 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. Table 2 compares the performance and features of contention-based medium access control protocols and TDMA-based medium access control protocols in high load conditions.

Spatial reuse TDMA constraints

We assume the following notations:

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

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

N 2 cch (x) = N cch (x) ∪ {N cch (y), ∀y ∈ N cch (x)} • N 3 schi (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. We denote by T S(x), the time slot acquired by 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 6.2.

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 8, 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 schi (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 RoadSide Units (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, 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 central control entity of the group. In a fully distributed VANET, the centralized control notion is absent and all the nodes can be both nodes and routers. We make a further and new classification of TDMAbased 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] 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].

In order to categorize the protocols, in this paper 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

TDMA-BASED MAC PROTOCOLS IN A FULLY DISTRIBUTED VANET (TDV)

In order to make the implementation of a timemultiplexed 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 | Impact of user mobility on the broadcast service efficiency of the adhoc mac protocol[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 9, 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. On the other hand, merging collisions [START_REF] Borgonovo | Impact of user mobility on the broadcast service efficiency of the adhoc mac protocol[END_REF] occur when two vehicles in different two-hop sets accessing the same time slot become members of the same two-hop set due to changes in their position. Generally, in VANETs, merging collisions are likely to occur in the following cases:

• Vehicles moving at different speeds • Vehicles moving in opposite directions • There are RSUs installed along the road Figure 10 shows an example of the second case of the merging collision problem, when vehicle B in the first two-hop set moving in the opposite direction to vehicle

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.

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

Abu-Rgheff et al. [START_REF] Abu-Rgheff | Softmac: Space-orthogonal frequency-time medium access control for vanet[END_REF] propose a MAC protocol for VANET networks based on a combination of CSMA, SDMA 5 , OFDMA 6 and TDMA techniques. TDMA is used to ensure contention-free channel access, while OFDMA and SDMA are used to perform simultaneous transmissions. In SOFT MAC, the frequency bands and slots are pre-assigned according to the vehicles' locations by dividing the road into cells of radius R and a portion N c of the available sub-carriers is assigned to each cell. Maps are pre-installed in the vehicles identifying which sub-carriers are allocated to each portion of the road. Then, these sub-carriers are shared between vehicles within the same cell via a TDMA. Each vehicle uses its current position, obtained by the GPS system, to know the set of sub-carriers. The SOFT MAC protocol has two periods, namely the reservation period RS of duration d R and the transmission period TS of N T S transmission slots. The RS period is accessed via a contention-based CSMA, while the TS period is accessed via a prior reservation. The RS period is used to transmit short messages and to reserve the channel resource for the coming TS period which is used to transmit a large amount of data. Transmissions made in the TS period 5. Space Division Multiple Access is a channel access method used in radio telecommunication systems such as mobile cellular networks. It consists in reusing the same set of cell phone frequencies over a given area.

6. Orthogonal Frequency Division Multiplexing is a modulation method that consists in dividing a given channel into multiple orthogonal sub-channels or sub-carriers. also contain the information about the status of each slot (Busy or Free) in the frame, the current number of TS slots N T S , the ID of the vehicle transmitting in a busy slot and other information required for the SOFT MAC protocol (see Figure 11). Each 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. Although this protocol shows improvements in throughput compared to the IEEE 802.11 standard and can support QoS requirements, the use of SDMA, CDMA and OFDMA techniques make SOFT MAC a very expensive and complex MAC mechanism. Bad choices of parameters (N T S , d R , R and N c ) are likely to degrade the performance of SOFT MAC. Moreover, SOFT MAC assumes that all vehicles are equipped with digital road maps and, therefore, this protocol can not ensure its interoperability in environments where vehicles without digital maps are present.

Dedicated Multi-channel MAC with Adaptive Broadcasting (DMMAC)

The DMMAC protocol [START_REF] Lu | Dmmac : A dedicated multichannel mac protocol design for vanet with adaptive broadcasting[END_REF] is an alternative to the IEEE 802.11p standard. DMMAC 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 12, 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 | Rr-aloha, 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. The simulation model used to evaluate DMMAC does not take into account velocity variations, the joining/leaving of vehicles and bidirectional traffic. It was limited only to the case of a straight road scenario with a number of slots that was significantly smaller than the maximum number of vehicles in network. Moreover, its random slot assignment technique does not perform a contiguous slot allocation. In addition, there are some issues that have not been studied, such as access collisions and merging collisions which can degrade the performance of DMMAC in highway scenarios where the vehicles are moving in opposite directions and under different traffic conditions.

Vehicular Ad Hoc Networks MAC (VeMAC)

VeMAC [START_REF] Omar | Vemac: A tdma-based mac protocol for reliable broadcast in vanets[END_REF], [START_REF] Zhuang | Vemac: A novel multichannel mac protocol for vehicular ad hoc networks[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 multichannel MAC protocol proposed for VANETs. In contrast to DMMAC and SOFTMAC, VeMAC is completely contention-free. 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 8.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 road side units (RSUs), see Figure 13. 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 vehicle. Each frame transmitted on the control channel is divided into four main fields: header, announcement of services (AnS), acceptance of services (AcS) and high priority short applications. As for 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], to avoid any hidden terminal problem, the header field of each message transmitted must include the time slots used by all the other vehicles within its one-hop neighborhood. Thus by reading the packet received from its one-hop neighborhood, each vehicle can determine the set of time slots used by all the vehicles within its two-hop neighborhood and the set of accessible time slots. It can attempt to acquire a time slot by randomly accessing any free time slot. The assignment of time slots to nodes on the service channels is performed by the providers in a centralized way. A provider is a vehicle which announces a service offered on a specific service channel in the AnS field on the control channel. A user is a vehicle which receives the announcement for a service and decides to make use of this service. It is the responsibility of the provider to assign time slots to all the users and it announces this slot assignment on the service channel in a specific time slot called the provider's main slot. When the provider receives the acceptance of the service in the AcS field, it tunes its second Transceiver to the specific service channel and starts offering the service in the time slots announced in the AnS field.

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 environment, 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.

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.

In their paper, the authors propose a slot management mechanism based on a binary tree in which the two-hop neighbors' slot allocation information of each vehicle can be mapped into a binary tree of k layers according to vehicle density. The set of vehicles on the left sub-tree can be regarded as the Left set of slots, while the set of vehicles on the right sub-tree are seen as the Right set of slots. As an example, when vehicle 3 in Figure 14 receives the slot allocation information from its two-hop neighbors, it establishes a binary tree and maps the slots that have been used by those two-hop neighbors to a fourlayer binary tree. Then vehicle 3 determines which slot to compete for. Each vehicle can halve the frame length to improve channel utilization when vehicle density is low, or double the frame length when vehicle density is high to ensure that each vehicle can access the channel. Two thresholds U min and U max have been defined to minimize or maximize the frame length (see Algorithm 1). The following notations are introduced for a specific moment in time t and for a specific vehicle x:

• S x (t): The frame length of vehicle x, namely the number of time slots of each frame.

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, it only uses a single channel which limits its performance in VANETs. The model considered is very limited and restricted to two-lane highway scenarios. Moreover, 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.

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

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.x in vanets[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.x in vanets[END_REF].

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 Vehicular Ad hoc Networks, called HER-MAC, which is similar to the DM-MAC 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 3way 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 its one-hop neighbors time slots and to initiate the 3-way WSA/RFS handshake in order to be able to exchange safety and non-safety messages.

Other TDV protocols

There are other TDV protocols for VANETs, each of them focusing on particular issues. These protocols have already been analyzed in previous survey papers [START_REF] Booysena | Survey of media access control 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].

• STDMA (Self-organizing Time Division Multiple Access) [START_REF] Yu | Stdma for vehicle-to-vehicle communication in a highway scenario[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] 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 Std[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.

• VeSOMAC (Self-Organizing MAC Protocol for DSRC based Vehicular Ad Hoc Networks) [START_REF] Yu | A self reorganizing mac protocol for intervehicle 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 contentionfree 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. VeSO-MAC 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 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.

In this section, we discuss some of the properties presented in Table 3. Several distributed protocols [START_REF] Abu-Rgheff | Softmac: Space-orthogonal 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). However, DMMAC has been presented as a dedicated Multi-channel protocol but it has only been evaluated for a single channel. 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 protocol such as AD HOC MAC [START_REF] An | An analytical model for tdma-based mac protocols in vanets[END_REF] 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, DM-MAC 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 multichannel 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 real-time 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 mechanism which dynamically adjusts the time ratio between the CCH and SCHs intervals according to traffic density.

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 clusterbased 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. There are two types of inter-cluster interferences [START_REF] Wu | Reducing inter-cluster tdma interference by adaptive mac allocation in sensor network[END_REF]: One-Hop Neighboring Collision and the Hidden Node Collisions.

One-Hop Neighboring Collision (OH-Collision) occurs

when a time slot is used by two neighboring vehicles belonging to neighboring clusters. Figure 15 shows an example of an OH-collision situation when vehicle C in cluster 1 and vehicle D in cluster 2 are using the same time slot. Since C and D are within transmission range of vehicle B, a collision will occur at vehicle B.

On the other hand, Hidden Node Collision (HN-Collision) occurs when two vehicles are in communication range of another node, but not within transmission range of each other. Let us consider the situation in Figure 16, when vehicle B in cluster 1 and vehicle D in cluster 2 are using the same time slot. Since these two vehicles are outside transmission range of each other, a collision will occur at vehicle C of cluster 1.

TCBT protocols

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

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 service for inter-vehicle communications and solves MAC issues such as the hidden-exposed terminal problem and QoS provisioning. ADHOC MAC is a contention-free medium access protocol which implements a dynamic TDMA mechanism that is able to provide prompt access based on distributed access technique, R-ALOHA (Reliable R-ALOHA [START_REF] Borgonovo | Rr-aloha, a reliable r-aloha broadcast channel for ad-hoc inter-vehicle communication networks[END_REF]), where the time is divided into frames and each frame is divided into N slots. Each vehicle can access the channel at least once in each frame by randomly selecting a time slot as its basic channel (BCH). To resolve the hidden node problem, each node should know the status (BUSY or FREE) of the N slots in a two-hop 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 use 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. Unlike the IEEE 802.11p standard, ADHOC MAC is a single channel protocol, not suitable for the DSRC architecture.

Cluster Based Medium Access Control Protocol (CBMAC)

A cluster based medium access control protocol (CB-MAC) 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 time slots which are grouped into time-frames. The TDMA frame structure employed by CBMAC is shown in Figure 17. 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 17, 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: CBMAC uses a single channel protocol, and thus it is not suitable for a DSRC architecture. The spatial reuse concept is not clear and this protocol was only evaluated for vehicle to vehicle 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.

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] has been developed to support both traffic safety applications and a wide range of non-safety applications. Moreover, CBMMAC combines contention-free and contention-based medium access control 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) channels. In the paper, the authors assume that each vehicle is equipped with two transceivers. CBMMAC deploys three main protocols: cluster configuration, intra-cluster 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 multi-channel 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 18). 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 4, 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 proximity or the merging collision problem. Although CBMMAC can support QoS for real-time applications while efficiently utilizing the wireless bandwidth for non real-time traffic, the use of two transceivers and one GPS system for each vehicle makes this system very expensive.

A Clustering-Based Multi-channel vehicle-to-vehicle Communication System (CBMCS)

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.

Adaptive Real-time Distributed MAC (A-ADHOC)

A-ADHOC [START_REF] Miao | A-adhoc: An adaptive realtime distributed mac protocol for vehicular ad hoc networks[END_REF] is based on the previous ADHOC MAC protocol. The A-ADHOC protocol is intended for realtime 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.

TDMA Cluster-based MAC (TC-MAC)

Almalag et al. in [START_REF] Almalag | Tdma cluster-based mac for vanets (tc-mac)[END_REF] 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. 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 trafc flow for cluster formation in vehicular ad-hoc networksr[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 (see Figure 19). Then vehicle j uses its mini-slot to inform the other vehicles of its transmission during j ′ s time slot on the SCH.

As an example, let N = 37 and k = 6. As shown in Figure 20, the vehicle with local ID 22 has access to service channel (22 mod 6) = 4 during slot (22 div 6) = 3, as well as the 5th mini-slot on the control channel in slot 3-1=2. Each new vehicle joining the cluster attempts to get the attention of the cluster head by transmitting in the mini-slot 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 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 7 channels within one group without access collisions. However, it is not clear from 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.

Cooperative ADHOC MAC (CAH-MAC) for Vehicular Networks

Bharati and Zhuang propose in [START_REF] Bharati | Cah-mac: Cooperative adhoc mac for vehicular networks[END_REF], [START_REF]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 AD-HOC 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.

Cluster-based TDMA system for inter-vehicle communications (CBT)

Sheu and Lin [START_REF] Sheu | A cluster-based tdma system for intervehicle 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 Figure 21 Once the VC has been elected, it periodically transmits a beacon signal during slot 0 in each TDMA frame. If no other beacon signal is received from another neighboring VC, the cluster remains in the intra-cluster communication state. Otherwise, it means that a collision has occurred caused by another VC in close proximity. In this case the two neighboring clusters will cooperate through VC-to-VC contact to build inter-cluster communications. To prevent inter-cluster interference during slot 1 to n-1, the two neighboring VCs exchange their SAMs by using the transmit-and-listen scheme. The first VC to successfully send its SAM to the other is the winner, and the second VC to successfully receive the SAM becomes the loser. The winning VC will not change its scheduled time slots, while the losing VC must reschedule the time slots for its VNs. It is not clear how VCs can remain synchronized in a multi-hop topology since the paper does not describe inter-cluster communication in detail when the distance between neighboring VCs of overlapping clusters is greater than 1-hop. The CBT protocol certainly has some shortcomings: the VANET Coordinator is randomly elected based on the simple transmit-and-listen scheme and, in fact, the life time of a VC may be very short and thus the resulting clusters will be unstable, which degrades the performance of CBT. The CBT protocol is limited to using only a single channel. The authors do not study the problem of merging collisions when vehicles are moving in opposite directions and do not discuss what happens if a new vehicle joins a cluster 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 5 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 traffic-jams, 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 300 m and 500 m), however the transmission ranges achieved by the other proto-cols (between 100 m and 250 m) are still unacceptable, since the inter-cluster collision rate increases as the transmission range decreases. Increasing the transmission range, decreases 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 CEN-TRALIZED TOPOLOGY (TCT)

A MAC protocol should exploit VANET characteristics like restricted mobility, the presence of Roadside Units (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 TDMAbased 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

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.

Adaptive Collision-Free MAC (ACFM)

Guo et al. in [START_REF] Guo | An adaptive collision-free mac protocol based on tdma for inter-vehicular communication[END_REF] propose an Adaptive Collision-Free MAC (ACFM) protocol based on a centralized dynamic time slot reservation mechanism in Roadside Units (RSUs). Thus, by using a schedule, ACFM ensures efficient time slot utilization for the exact number of active vehicles. As shown in Figure 22, the time is divided into frames and each frame is divided into a fixed number of time slots: one RSU Slot (RS) which is used by an RSU to broadcast control messages to the vehicles within its coverage area and 36 Data Slots (DS) which can be used by the vehicles to broadcast their beacon data to their neighboring vehicles. The control message that is periodically diffused by an RSU contains the DS assignment schedule for vehicles under its coverage and time synchronization information.

Therefore, each RSU independently and dynamically maintains a slot schedule cycle of a maximum time equal to 100 ms for vehicles in its coverage. The cycle consists of N frames, where N varies from 1 to 5 according to vehicle density in the coverage area of the RSU. However, to avoid interference between adjacent segments, the authors have proved that two orthogonal frequencies are needed to ensure the same frequency is not used for a distance of two hops (see Figure 23). Moreover, the vehicles in the intersection of two segments must select and tune to one of the two frequencies to send messages based on the RSSI (Received Signal Strength Indication).

A cycle length expansion and shrinking mechanism has been added to ACFM to ensure the fairness of the channel access protocol. When vehicle density is low in a protocol, it also has some drawbacks: the protocol uses a single channel and does not exploit the seven available WAVE channels as well as being limited only to periodic messages and does not support QoS for non-safety applications. The protocol does not handle communications between vehicles belonging to two different subnets. Moreover, due to high node mobility, the interval of time in which the vehicle stays in an RSU region is very short, which can lead to breaks in communication.

Risk-Aware Dynamic MAC (R-MAC)

Guo et al. in [START_REF] Guo | R-mac: Riskaware 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 mediumaccess 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 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 is a single channel protocol and 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.

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 ad-hoc networks[END_REF]. The goal of the work is to develop a contention-free MAC approach with centralized control in Roadside Units (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 cluster 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 nonsafety 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 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.

Unified TDMA-based Scheduling Protocol for V2I communications (UTSP)

Zhang et al. have proposed in [START_REF] Zhang | A unified tdma-based 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.

Summary of TCT protocols

Four TDMA-based MAC protocols in centralized network topologies have been presented. Table 6 compares the performance and features of these protocols. The results are taken from the references indicated in Table 6.

As shown in this table, we note that all the protocols consider the medium as a single shared channel for their safety or/and data transmissions. Although these protocols have been proposed recently (2012, 2013 and 2014), we found that most of them do not exploit the seven channels provided by the DSRC technology, which confirms that they were developed for a specific class of applications.

Unlike CBRC and UTSP, ACFM and R-MAC do not support throughput-sensitive applications and are limited only to delay-sensitive applications which make ACFM and R-MAC unsuitable for VANETs. R-MAC only addresses the need to create a protocol to efficiently deliver beacon and warning messages, while ACFM only addresses the need to develop a protocol to efficiently send beacon messages. However, 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.

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

ANALYSIS OF THE TDMA-BASED MAC PROTOCOLS BASED ON THE MAC QOS MET-

RICS

In this section we summarize the features present in each protocol. The QoS metric-based comparison is shown in Table 7. This table helps us to draw several important conclusions. Figure 24 presents the number of TDMAbased MAC protocols which support each metric described in Section 5.3. All the existing protocols have been developed to provide less access delay for safety applications at the expense of other MAC QoS metrics such as throughput, stability, fairness and packet loss. 26 illustrates the number of times each of the TDMA-based MAC design issues was addressed by the protocols presented in this survey. Having no central coordination and supporting an efficient broadcast service on the CCH appear to be the most popular MAC issues in VANETs, and have been addressed in more than 17 and 13 protocols, respectively. However, mobility scenarios (both highway and urban), scalability, different QoS requirements have not been taken into account for many protocols. Thus, these issues need to be considered and addressed efficiently in future TDMA-based MAC protocols.

The number of times each issue has been addressed in recent years is shown in Figure 27. Initially, only a small number of MAC issues were addressed, but the number has risen subsequently. Figure 28 gives the percentage of protocols in our three classes (TDV, TCBN, TCN) which address a given QoS metric. It is clear from this figure that the centralized TCN protocols are the most suitable for VANETs with respect to the QoS performance metrics. Moreover, we note that the TCBN protocols are the second best, except for the throughput metric where the TDV protocols are the second best.

The number of MAC protocols designed and published over the years is shown in Figure 29

COMPARISON AND SUMMARY

It is no simple task to establish a fair comparison between TDMA-based MAC protocols as each of them has been developed with a different architecture and for a specific class of applications. The nodes in VANETs are characterized by their high mobility, so the network topology can change quickly and frequently. Therefore,

A-ADHOC None

TC-MAC

Multi-channel CBMAC None CBT None CBMCS Multi-channel CBMMAC Multi-channel

CAH-MAC None

TCT Protocols

ACFM None

R-MAC Access priority

CBRC

Access priority

UTSP

Multi-channel and access priority an efficient MAC protocol in VANETs must assume as general a topology as possible. In this section, we summarize the benefits and drawbacks of the different classes of protocols and the effect a particular topology has on the network's performance.

TDMA-based MAC protocols in a fully distributed VANET assume that each vehicle needs only to communicate with its direct neighbor in order to acquire a time slot. Thus these protocols are referred to as single hop protocols. VeMAC, ATSA, STDMA, DMMAC, HER-MAC, CFR MAC, VeSOMAC and SOFTMAC are all examples of this category. Since each vehicle has a local view of the network, the access delay increases exponentially and the throughput decreases continuously in the network as vehicle density and traffic load increase. DMMAC and ATSA provide a dynamic and adaptive frame length according to vehicle density in order to add scalability and adaptability to this class of topology. SOFTMAC differentiates between services by attribut-ing access priority in order to provide fair channel access and make better use of the common channel. VeSOMAC, DMMAC, HER-MAC and VeMAC provide multiple channels to achieve a high throughput and less transmission delay under different network conditions. VeMAC offers a novel TDMA slot assignment strategy to reduce transmission collisions caused by node mobility. Although these protocols support efficient slot reservation techniques, they produce a significant communication overhead in highly dense networks. For instance, in order to ensure that a vehicle's established reservation will not conflict with another reservation within its twohop neighborhood, the vehicle must periodically broadcast frame information including the slot ID and their states to all its one-hop neighbors, which is likely to lead to a high communication overhead, specially in a dense scenario thus reduce the overall bandwidth. Even if collision-free transmission is ensured, the high mobility of nodes increases the communication overhead, which may be avoided in a hierarchy or centralized topology in which the TDMA slot reservation schedule is managed by central node in each sub-network.

In contrast to fully-distributed VANET protocols, cluster-based TDMA has attracted more attention over recent years, in order to provide fair channel access without access collisions due to concurrent access to the same available time slot. In a clustered or hierarchical topology, one vehicle among a group of vehicles is elected to act as the cluster head to create and manage the TDMA slot reservation schedule for its cluster members. The clustered topology protocols attempt to reduce the overhead in a one-hop neighborhood by centralizing the slot allocation function at the cluster head. TC-MAC, CBMCS, CBMMA, CBT, ADHOC MAC, A-ADHOC, CAH-MAC and CBMMAC are all examples of clustered topology protocols. However the main challenges in a cluster-based TDMA is the communication overhead in terms of exchanging messages needed to elect a cluster head and to maintain the cluster members in a highly dynamic topology, as well as inter-cluster interference when two or more clusters are approaching each other. Moreover, clustered topology protocols are not suitable for high density networks, as the cluster stability decreases when the density of vehicles increases. TC-MAC supports a stable clustering method that produces a longer cluster head lifetime thereby reducing the overhead of re-clustering. CBT uses a simple transmit-and-listen scheme to reduce the overhead of cluster head election and to quickly resolve inter-cluster collisions when two or more clusters are approaching each other by re-allocating time slots in one of the clusters. CBMMAC and CBMCS use a CDMA technique combined with TDMA to enable vehicles that belong to two neighboring clusters to communicate with each other without inter-cluster interference. To do so, a transmission code is assigned to each cluster for intracluster communications. CBMMAC, CBMCS and TC-MAC incorporate multi-channel operation in order to support traffic with different services and achieve a high throughput for non-safety applications with less transmission delay for safety applications under different network conditions. ADHOC MAC uses a prioritybased scheduling algorithm to make better the use of the single common channel by giving high access priority to safety messages. Although the clustered topology protocols can effectively control the network topology, avoid access collisions, provide fairness to channel access and increase throughput by the spatial reuse of time slots, the high mobility of the vehicles in VANETs affects the stability of the cluster heads which leads to network problems and performance degradation, which is not the case for a centralized topology. R-MAC, ACFM, CBRC and UTSP are examples of centralized topology protocols. All these protocols require the presence of RSUs to coordinate channel access, in which the RSUs maintain slot assignment frames for the vehicles in their coverage areas. Hence, the presence of the RSUs can minimize the communication overhead and provide fairness to channel access. However, as with clustered topology protocols, when RSUs are used to manage the slot assignment schedule, an interference problem can occur between vehicles in the overlapping regions. Thus messages transmitted in one region may affect communications in another region. Only ACFM allows two neighboring RSUs to communicate without affecting communication within an RSU's region by using different orthogonal frequencies. Based on the different priorities between messages in CBRC, R-MAC and UTSP, the RSU allocates time slots to the vehicles in its communication area, which ensures the timely delivery of safety messages.

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 fullydistributed 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 8) 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.

Reserved versus random access

Hybrid protocols, particularly those that combine TDMA with CSMA, 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 each other or 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 hybrid MAC protocols. 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 and according to the number of time slots in the reserved period which can be assigned to vehicles. Although, there are proposals to tune the lengths of the reserved and random access periods, we believe that we are still far from an optimal tuning of these parameters. This tuning is all the more difficult as vehicle density may vary significantly.

Consideration of multiple MAC metrics

Unfortunately, most existing TDMA-based MAC protocols are designed to achieve less transmission delay for safety applications at the expense of other MAC performance metrics. However, fairness, packet loss 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, the majority of MAC protocols surveyed 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.

Multichannel operation

In order to increase throughput and support a wide range of applications in VANETs, the FCC (Federal Communication Commission) [21] has established the DSRC service on the frequency band of 5.9 GHz divided into seven channels. However, the majority of MAC protocols presented 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.

Supporting varying densities of vehicles

A challenging problem when designing MAC protocols in VANETs is coping with vehicle mobility, which leads to great variations in vehicle densities over time. However, the majority of TDMA-based MAC protocols that were surveyed have a fixed number of vehicles that can access the channel at any one time. Therefore, they cannot handle both sparse and dense mobility scenarios. As a result, future MAC protocols should take this feature into account by supporting an adaptive frame length according to the number of vehicles. Indeed, they should be able to increase the TDMA frame length when vehicle density is high to ensure that each vehicle is assigned a slot, and reduce it when vehicle density is low to ensure a bounded waiting time.

Large speed variance

Several TDMA based MAC protocols fail to guarantee channel access fairness for vehicles travelling 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.

Mobility scenario

Many MAC protocols 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. As all cluster-based TDMA protocols have only been designed for highway scenarios, designing a cluster-based TDMA MAC protocol that can operate in both highway and urban scenarios is an open research topic, and one that may require further study and evaluation of the TCT protocols proposed in the literature.

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 TDMA-based 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.

12.9 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 wideband 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 in VANETs requires efficient and reliable MAC protocols. These MAC protocols can be based on TDMA schemes. This paper, 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 useroriented applications. This paper has presented a broad overview of VANETs characteristics that should be taken into consideration to enable the implementation of reliable MAC protocols and the ITS activities both in Europe and further afield. In addition to describing and giving the strengths and weaknesses of each protocol, we have proposed a novel topology-based classification of these MAC protocols. Producing an efficient TDMA-based MAC protocol is a challenging task in the context of VANETs due to their special characteristics such as high node speed, frequently changing network topologies, the hidden and exposed node problems, different QoS requirements, etc. All these issues have been identified and discussed in this paper.

The paper has also 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 the 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 help readers better understand the difference between the various protocols. We note that cluster-based TDMA MAC protocols have reached the QoS level required, due 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 made use of other access techniques such as CDMA and FDMA which make them more complex and expensive. Resolving these problems requires more efforts in the future. Moreover, the topological features of VANETs in highway and urban environments can be used as part of the MAC design guideline in future work.

Finally, we have specified certain MAC research challenges and open questions which may be future research directions to enable VANETs to efficiently support both safety and non-safety applications. Despite the research efforts to improve the performance of TDMA-based MAC protocols in VANETs, there is no ideal solution that can meet the QoS requirements at the MAC layer and resolve all the problems caused by the special characteristics of VANETs. Therefore, this survey paper is a call for VANET researchers to focus on the challenges we have set out.

Fig. 1 :

 1 Fig. 1: Heterogeneous vehicular communication architecture.

Fig. 2 :

 2 Fig. 2: Channel assignment in DSRC.

Fig. 3 :

 3 Fig. 3: Network synchronization

Fig. 4 :

 4 Fig. 4: Protocol stack of WAVE

Fig. 5 :

 5 Fig. 5: Overview of ITS activities in Europe and the rest of the world

Fig. 6 :

 6 Fig. 6: Classification of TDMA-based MAC protocols

Fig. 8 :

 8 Fig. 8: Collision with two-hop neighbors on a specific service channel.

Fig. 9 :

 9 Fig. 9: Access collision problem.

Fig. 10 :

 10 Fig. 10: Merging collision problem

Fig. 11 :

 11 Fig.11: SOFT MAC Frame Structure[START_REF] Abu-Rgheff | Softmac: Space-orthogonal frequency-time medium access control for vanet[END_REF]

Fig. 12 :

 12 Fig. 12: Architecture of DMMAC

Fig. 13 :

 13 Fig. 13: Partitioning of each frame into three sets

Fig. 14 :

 14 Fig. 14: Slot management mechanism in ATSA

Fig. 15 :

 15 Fig. 15: One-Hop neighboring Collision (OH-Collision).

Fig. 16 :

 16 Fig. 16: Hidden Node Collision (HN-Collision).

Fig. 17 :

 17 Fig. 17: TDMA frame structure

Fig. 18 :

 18 Fig. 18: TDMA frames in the CRC channel

19 :

 19 TDMA frame structure in bidirectional traffic and urban scenarios due to 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

Fig. 20 :

 20 Fig. 20: An example of TDMA slot scheduling

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

Fig. 21 :

 21 Fig. 21: TDMA and MAC-layer frames in the CBT protocol

Fig. 23 :

 23 Fig. 23: Frequency assignment to subnet

Fig. 22 :

 22 Fig. 22: TDMA frame structure of the ACFM protocol

  . Only one protocol was published in 2004. During the years 2005 and 2006, no protocols were proposed. Then, the number of protocols increased significantly until 2009, with 2008 being an exceptionally poor year. The number of protocols saw a decline in 2010 and 2011, but the number began to pick up and has continued to rise since then. The highest number of new MAC protocols appeared in 2009, 2013 and 2014.

Fig. 24 :Fig. 25 :Fig. 26 :Fig. 27 :Fig. 28 :Fig. 29 :

 242526272829 Fig. 24: Number of protocols versus MAC QoS metrics supported

TABLE 1 : Regional standards for DSRC Features Japan (ARIB a ) Europe (CEN) North America (ASTM b )

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

	Duplex	Half-duplex(OBU)/Full duplex(RSU)	Half-duplex	Half-duplex
	Communication system	Active	Passive	Active
	Radio Frequency	5.8 GHz band	5.8 GHz band	5.9 GHz band
	Band	80 MHz bandwidth	20 MHz bandwidth	75 MHz bandwidth
	Channels	7	4	7
	Channel Separation	5 MHz	5 MHz	10 MHz
	Data Transmission rate	1 or 4 Mbits/s	Down-link: 500 Kbits/s / Up-link: 250 Kbits/s	6-27 Mbits/s
	Coverage	30 meters	1520 meters	1000 meters
	Modulation	2-ASK, 4-PSK	RSU: 2-ASK/OBU: 2-PSK	OFDM
	a. Association of Radio Industries and Businesses
	b. American Society for Testing and Materials
	4.1.3 As shown in Figure 4, the WAVE stack incorporates a
	number of protocols in conjunction with the family of
	the IEEE 1609 standards [29]. 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.

TABLE 2 :

 2 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 medium	Inefficient	High	Medium	Unbounded	No	High
	access protocols (CSMA/CA)
	Contention-free	medium	Efficient	Low	High	Bounded	Yes	Low
	access protocols (TDMA)

  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

• N x (t): x (t) < U min ) then 3.1. divide the frame length by two;

TABLE 3 :

 3 Qualitative comparison of TDMA-based MAC protocols in fully distributed VANET

		CFR MAC	HER-MAC	VeMAC	ATSA	CS-TDMA
	References	[76]	[78]	[70], [8] and [69]	[73]	[77]
	Published	2014	2014	2011	2013	2014
	Channel	Single	Multiple	Single/Multiple	Single	Multiple
	Pure TDMA	Yes	No	Yes	Yes	No
	Merging collision	Solved	Possible	Solved	Solved	Possible
	Access collision	Solved	Possible	Solved	Possible	Possible
	Mobility	High	N/A	High	N/A	N/A
	Density (scalability)	High	Low	High	Medium	Medium
	Broadcast service	Yes	Yes	Yes	No	Yes
	Mobility model	Highway	Highway	Highway/Urban	Highway	Highway
	Vehicular traffic	Bidirectional	Bidirectional	Bidirectional	Bidirectional	Bidirectional
	Data Traffic load	High load	High load	High load	N/A	High
	Control overhead	Medium	High	Low:SCH/High:CCH	Low	Medium
	Transmission range	Low	N/A	Short	N/A	N/A
	Multimedia applications	No	Yes	Yes	No	Yes
	Real-Time applications	Yes	Yes	Yes	Yes	Yes
	Positioning System GPS	Yes	Yes	Yes	Yes	Yes
	Time Synchronization	Yes	Yes	Yes	Yes	Yes
	Simulator	N/A	Matlab	MATLAB and NS2	MATLAB	Matlab

TABLE 3 (continued):

 3 Qualitative comparison of TDMA-based MAC protocols in fully distributed VANETs

	VeSOMAC	STDMA	SOFTMAC	DMMAC

TABLE 4 :

 4 Channel allocation and MAC protocols used by CBMMAC scheme

	Vehicle State	Transceiver Channel	MAC Protocol	Message Type
	Cluster Head CH	1	CRC	TDMA-based MAC	Safety/Control messages
		2	ICC	IEEE 802.11 MAC	Consolidated safety messages
	Cluster Member CM	1	CRC	TDMA-based MAC	Safety/Control messages
		2	CRD	Centralized Multichannel	Non real-time traffics
				Control Allocation
		2	ICD	IEEE 802.11 MAC	Non real-time traffics
	Quasi-Cluster HEAD QCD	1	ICC	IEEE 802.11 MAC	Safety messages
		2 (off)	--	--	--
	Quasi-Cluster Member QCM	1	ICC	IEEE 802.11 MAC	Safety messages
		2	CRC	TDMA-based MAC	Resume the communications
					with the previous CH

TABLE 5 :

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

	ADHOC MAC	A-ADHOC	TC-MAC	CBMAC

TABLE 6 (continued):

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

	CAH-MAC	CBT	CBMCS	CBMMAC

TABLE 6 :

 6 Qualitative comparison of TDMA-based MAC protocols in centralized network topology

	ACFM	R-MAC	CBRC	UTSP

TABLE 7 :

 7 Classification and analysis of existing TDMA-based MAC protocols for VANETs

	Metrics

TABLE 8 :

 8 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
	12 OPEN RESEARCH ISSUES
	Medium Access Control (MAC) protocols play a pri-
	mary role in providing fair channel access with efficient
	delivery among all vehicles and avoiding data packet
	loss as much as possible. In this paper, we have given

an overview of several scheduling-based MAC protocols 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.

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.

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.

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.