A Study on Priority-based Centralized TDMA Slot Scheduling Algorithm for Vehicular Ad hoc NETworks.
Vehicular Ad hoc NETworks, known as VANETs, are regarded as a promising communication technology that can meet various requirements of Intelligent Transportation System (ITS) applications which aim to help improve traffic safety and efficiency . Through Vehicle-to-Vehicle (V2V) and Vehicle-to-Infrastructure (V2I) communications, each vehicle can exchange information to warn other vehicles about the current state of the traffic flow or the existence of a dangerous situation such as an accident. Road safety and traffic management applications require a reliable broadcast scheme with minimal transmission delays and collisions, which increases the need for an efficient MAC protocol . Recently, Contention-free 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 in order to handle the network access and transmission with minimum packet loss.
In the past few years, several distributed TDMA-based protocols for medium access channel have been published to offer reliable and real-time communications in Vehicular Ad hoc NETworks while trying to attenuate the effect of the merging collision problem and access collision problem . Every protocol has been designed for a specific problem considering a particular scenario for mobility. As an example, in , Borgonovo et al. have proposed ADHOC MAC protocol (AD HOC Medium Access Control) to insure an efficient broadcast mechanism for V2V communications and cope with some medium access channel issues, like the hidden-exposed node problem in order to guarantee a certain Quality of Service. ADHOC MAC protocol is a contention-less medium access protocol based on a dynamic TDMA technique which provides fast access to the channel. This mechanism can be seen as an extension of the Reliable ALOHA technique (R-ALOHA ). Each car is able to access the channel in every frame in a random manner to choose a time slot as its Basic CHannel (BCH). The car is insured to access the channel at least once in a given frame.
In ,  Omar et al. designed and studied a protocol called VeMAC. VeMAC proposed for VANETs is a contention-free MAC protocol adapted to the V2V multi-channel radio system that offers efficient one-hop and multi-hop broadcast services on the control channel and get rid off the hidden node problem originated by vehicle mobility. In addition, VeMAC  is able to attenuate the merging collision rate by allocating different sets of time slots to cars traveling towards different directions (Right, Left) and to RSUs (1). As VeMAC is a fully distributed protocol, an access collision problem may happen frequently among cars attempting to gain access to the same time slots under high traffic density situations.
Another completely distributed TDMA scheduling scheme, named DTMAC which takes benefit from the linear topology of VANETs is proposed and presented in . This latter is based on the assumption that the road is partitioned into equal small size areas and the time slots in every TDMA frame are divided into three sets which correspond to cars in three successive areas. In DTMAC slots allocation and reuse procedures are designed in order to reduce the effect of collisions that are originated by the hidden node problem.
These distributed-TDMA based MAC protocols show some improvements compared to the IEEE 802.11p standard and can support QoS requirements of safety applications, however, when the size of the vehicular network increases, the access collision problem frequently occurs among different vehicles that try to transmit at the same time slots. Moreover, the scheduling mechanisms of these protocols produce a significant overhead to set up and adjust the TDMA schedules in highly dense networks.
An efficient solution to mitigate the access collision rate while reducing the scheduling overhead consists in using RSUs as primary coordinators to set up and adjust the time slots allocation for the cars in their communication range. For instance, the authors have proposed in  an Adaptive Collision-Free MAC (ACFM) protocol based on a centralized and dynamic time slot assignment mechanism. Each frame in ACFM is partitioned into a predefined number of time slots: one RSU time Slot (RS) is dedicated to an RSU to transmit control messages to the cars located in its vicinity and within its communication range. In addition, 36 Data time Slots (DS) can be used by the cars to transmit their data packets to their immediate neighboring vehicles. An RSU periodically diffuse a control message containing the DS allocation schedule for the cars located in its radio range along with the time synchronization information. Unfortunately, the protocol does not handle communications between vehicles belonging to two different RSU coverage areas.
The authors have proposed in  and  an Unified TDMA-based Scheduling Protocol (UTSP) especially designed for Vehicle to Infrastructure communications. The main purpose of this research work is to maximize the useful bandwidth for user-related applications in VANETs. Hence, each RSU gathers the needed information like, the channel occupancy information, the vehicle velocity, and the Access Category properties of the cars located in its coverage area. Then it allocates the time slots to the cars depending on the weight function that takes into account three elements: speed weight factor, AC weight factor and channel-quality weight factor. However, the authors did not take into consideration the interference problem that may happen between cars in overlapping areas where each area is covered by a different RSU.
Despite the research efforts spent to improve the performance of TDMA in VANETs, most of these TDMA-based MAC protocols do not support service differentiation and act similarly with various types of data traffic without giving a higher access priority for safety applications. In this paper, we extend our protocol CTMAC , a Centralized TDMA based MAC protocol for VANET to support service differentiation. In this extended version, the RSU will serve time slot reservation requests with higher level of access priority sooner than other requests. The rest of the paper is organized as follows. Section 2 describes the system models and briefly presents the CTMAC protocol . Section 3 describes our Priority-based QOS Centralized TDMA MAC protocol, called PQCTMAC. Section 4 presents the simulation results and the performance evaluation. Finally, conclusions is reported in Section 5.
2. Centralized TDMA based MAC protocol
The key idea of CTMAC protocol , a TDMA protocol based, is the use of a collision free scheduling mechanism over adjacent areas. CTMAC avoids that vehicles traveling in two adjacent areas use the same time slot to access the radio channel.
In CTMAC, the road is partitioned into several contiguous areas, where each of them is covered by one RSU located in the middle of it. The radio range of an RSU is denoted by R, and the length of an area is equal to 2R.
Like traditional TDMA access channel based protocols, the time is divided into successive time frames. In addition, each time frame is divided into two sets of time slots denoted by [S.sub.1] and [S.sub.2]. These two sets are repeatedly used along the road so that no vehicles located in the same set of two-hop neighbors are using the same time slot.
Figure 1 shows a highway divided into several adjacent areas where in each of them, one RSU, having a radio range equal to R, is installed in its center. According to the CTMAC rules, vehicles traveling in the area covered by RS[U.sub.1] and those covered by RS[U.sub.2] are accessing non overlapping sets of time slots. The set [S.sub.1] of time slots is used by the vehicles that are moving within the coverage area of RS[U.sub.1], while the set [S.sub.2] is used by the vehicles that are moving within the coverage area of RS[U.sub.2].
The major benefit of CTMAC is the limited effect of interferences between each two successive RSUs. Consequently, the scheduling mechanism is able to reduce the collision rate for vehicles accessing to the radio channel without using any complex bandwidth allocation technique.
Each time a vehicle enters a new area, it gets a new time slot (see next paragraph for more details). This time slot will be used by the vehicle to access to the channel and transmit its data as long as it is traveling within the same area or once a merging collision happen.
Each RSU builds and updates a Frame Information (FI) composed of [tau] fields. [tau] corresponds to the number of time slots in the frame. Each field, denoted as IDF (ID Field) describes the corresponding time slot in the frame. Three sub fields are used for this purpose: SLT_STS, VC_ID and PKT_TYP. The SLT_STS sub field tells whether the slot is used (occupied), in Collision, or Idle. The VC_ID sub field stores the ID of the car that is using this slot. Whereas the PKTJTYP sub field gives information about the type of packet transmitted: i.e. event-driven safety messages or periodic packets. In CTMAC and unlike the ADHOC MAC and VeMAC protocols, the frame information is periodically broadcasted only by the RSU and each vehicle will update its local FI based on the FI broadcasted by its RSU. Nevertheless, if an access collision is detected, a vehicle is allowed to broadcast its frame information to its neighbors (and RSU) to warn them about this event.
An RSU u is able to identify the set of available time slots at the end of each frame. This set is denoted by F(u). When free slots are available a Slot Announcement (SA) message along with the FI message are broadcasted during the first slot of the corresponding RSU subset time slots (notice that the first slots of sets [S.sub.1] or [S.sub.2] are reserved for the RSU transmissions). Based on this information, a vehicle v traveling in that area that wishes to access the channel is able to pick randomly one of the available slots. It then broadcasts a Slot REQuest message (SREQ) during the selected slot to attract the attention of the RSU and express its intention. When the RSU gets the SREQ message, it checks whether a time slot is available or not. The RSU will send its Slot REPly message (SREP) containing its allocation decision including the allocated time slot index. Actually the decision is simply integrated within the next FI announcement. Eventually, the vehicle v can start using the assigned time slot to transmit its data. Otherwise, the vehicle v will reiterate the same reservation steps if a predefined timer expires and no reply has been arrived from the RSU. An RSU considers that a given vehicle v has left its communication range, when it does not receive a packet from the vehicle v during its time slot.
As stated before, the vehicle v will keep using the same time slot while traveling in the same area and without any collision. In case of collision, the vehicle will try to get a new time slot as described above. If the moving vehicle v detects different RSU announcements than the current one, it will start a handover procedure to get a new time slot from the new detected RSU. The vehicle will send an SREQ message to get allocated a new time slot and if it receives an SREP message from the RSU it will free its current time slot and it will resume its transmissions during the time slot newly allocated by the new RSU.
3. Priority-based QOS Centralized TDMA MAC protocol(PQCTMAC)
Currently, VANETs are used for various kinds of applications with different degrees of safety. However, safety-critical applications must be served in a short time with a high degree of reliability, because they are critical for driving safety. Therefore, MAC protocols should provide transmission services with a bounded access delay for high priority safety applications. To do so, we classified applications of VANET into three different classes with different priorities according to data type. Namely
* class 0 for the highest priority used to send safety message data,
* class 1 is reserved for less sensitive information like vehicular traffic control and route optimization, and
* class 2 is used for infotainment data.
With these priority classes, the original CTMAC time slot reservation request and allocation procedures are slightly modified and described as follows:
* Allocating time slot procedure according to priority levels: With PQCTMAC, the time slot allocation is achieved taking into account the priority of the request. At the end of each frame, the RSU u will analyze and classify the different requests received, and function of the available free time slots it will serve first the highest priority requests. The requests are successfully served as long as there are available slots. However, if all the slots become occupied and there still high priority requests not yet processed, the RSU has to decide which time slots may be revoked to serve the remaining requests. Initially, the RSU will revoke the lowest priority (class 2) time slot assigned to vehicle v, and allocate it to a higher priority requestor vehicle (class 0 or class 1 if there is no more class 0 request). The RSU will apply the same principle to revoke class 1 priority time slots and replace them with class 0 priority time slots once it runs out of class 2 time slots. In this manner we insure that higher priority allocation requests are given better chances to get access to the channel than the lower priority requests.
* Requesting time slot procedure: As described in the previous section, when a vehicle v needs a time slot to send its data, it will try to select randomly a free time slot among the available ones, and send its request message (SREQ) to the RSU. With PQCTMAC, an additional information is added to the SREQ message to precise the priority class that the vehicle v is requesting. Hence, the RSU is able to process the request as mentioned above. However, it may happen that all the time slots are already occupied by a lower priority class data. In this case we rely on the Access Collision Avoidance (ACA) mechanism integrated in CTMAC to handle these situations and let the RSU update its scheduling. The idea is to allow the vehicle v to send its request SREQ during an already allocated time slot (with lower priority class), and use one of its neighbors v' as a potential relay to deliver this request within its Frame Information (FI) that has to be sent to the RSU. The RSU is then able to re arrange and change the time slot allocation according to class priorities.
4. Simulation results
In this section, we provide the simulation results to evaluate and compare the performance of PQCTMAC protocol with the classical version CTMAC.
4.1. Simulation scenarios and parameters
We use MOVE  to generate vehicular traffic scenarios and SUMO  to perform real vehicular mobility simulations (see Figure 2).
In our simulations we considered a real highway area digital map to generate a VANET environment close to real highway configurations taking into account different lane directions. In Figure 3 we can see a metropolitan area taken from a Map of San Jose (California) of size 3000m x 100m. This map was exported from OpenStreetMap (OSM) and adapted with the help of OpenStreetMap Editor (JOSM). The resulted roads are then populated with a bunch of vehicles in every direction. Each flow of vehicles is characterized by a set of parameters which consisted of the starting and ending time of the flow, the initial point and the destination of the flow and the maximum number of vehicles. In this environment, each vehicle is assigned a random speed between 120km/h and 150km/h. The resulted traffic traces generated by MOVE were injected in the Network Simulator ns2.34. Table I summarizes the simulation parameters that we have used in our scenarios.
4.2. Simulation results
To the best of the author's knowledge, this is the first priority based centralized TDMA scheduling mechanism especially designed for VANETs. We notice that in a previous paper  we showed that CTMAC outperforms other TDMA protocols for VANETs, VeMAC  and ADHOC-MAC . That is why in this paper, we have compared the performance of PQCTMAC protocol with a non-priority-based protocol, namely the CTMAC protocol. The Figure 4 shows the number of safety messages sent during 100 frames. We can note from this Figure that PQCTMAC can send more safety messages than CTMAC. For instance, at a frame number 38, 61.8 (on average) safety packets have been sent by PQCTMAC protocol, in contrast to CTMAC which shows an average of 50.5 (i.e. approximately 22,38% lower than the PQCTMAC). These results can be explained by the fact that the scheduling mechanism of PQCTMAC gives preference to high priority slot reservation request rather than low priority request which allows certain vehicles that have safety-related information to gain rapid access to the channel and send their messages in the network.
The Figure 5 shows the average number of received safety messages within 100 frames. As shown in this Figure, PQCTMAC achieves a considerably higher average of received safety messages than CTMAC, especially at frame number 32, PQCTMAC has achieved an average number of 3424,95, whilst CTMAC achieves a smaller average of 2911,6 (approximately 17.65% lower than the PQCTMAC). These results can be explained by the fact that PQCTMAC protocol has achieved a higher average number of safety messages transmitted compared to CTMAC.
Applications for Vehicular Ad hoc Network (VANET) ranges from road safety messages and traffic management to infotainment. However, due to their strong time constraints, safety applications should be given a higher access priority than other applications in order to improve traffic safety and efficiency and reduce the risk of road accidents. In this paper, we propose a priority based centralized TDMA based MAC protocol (PQCTMAC) for vehicular networks in which data priority levels are used to differentiate among slot reservation requests. The simulation results presented show that PQCTMAC protocol provides better performances in terms of safety message broadcasting efficiency.
 P. Papadimitratos, A. d. L. Fortelle, K. Evenssen, R. Brignolo and S. Cosenza, Vehicular Communication Systems: Enabling Technologies, Applications, and Future Outlook on Intelligent Transportation, IEEE Communication Magazine, vol. 47, no. 11, pp. 84-95, 2009.
 M. Hadded, R. Zagrouba, A. Laouiti, P. Muhlethaler, and L. A. Saidane, An optimal strategy for collision-free slots allocations in vehicular adhoc networks, in Advances in Intelligent Systems and Computing, vol. 306, Kuala Lumpur, Malaysia, Jun. 2015, pp. 15-30.
 F. Borgonovo, A. Capone, M. Cesana, and L. Fratta, Adhoc mac: new mac architecture for ad hoc networks providing efficient and reliable point-to-point and broadcast services, Wireless Networks, vol. 10, no. 4, pp. 359-366, 2004.
 F. Borgonovo, A. Capone, M. Cesana, and L. Fratta, Rr-aloha, a reliable r-aloha broadcast channel for ad-hoc intervehicle communication networks, in IEEE IFIP Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net), Baia Chia, Italy, 2002.
 W. Zhuang, H. A. Omar, and L. Lio, Vemac: A novel multichannel mac protocol for vehicular ad hoc networks, in IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Shanghai, China, Aug. 2011, pp. 413-418.
 H. A. Omar, W. Zhuang, and L. Li, Evaluation of vemac for v2v and v2r communications under unbalanced vehicle traffic, in IEEE Vehicular Technology Conference (VTC Fall), Quebec City, Canada, Sep. 2012, pp. 1-5.
 M. Hadded, A. Laouiti, P. Muhlethaler, and L. A. Saidane, An infrastructure-free slot assignment algorithm for reliable broadcast of periodic messages in vehicular ad hoc networks, in Vehicular Technology Conference (VTC Fall), Montreal, Canada, Sep. 2016, pp. 1-6.
 W. Guo, L. Huang, L. Chen, H. Xu, and J. Xi, An adaptive collisionfree mac protocol based on tdma for inter-vehicular communication, in International Conference on Wireless Communications and Signal Processing (WCSP), Anhui, China, Oct. 2012, pp. 1-6.
 R. Zhang, J. Lee, X. Shen, X. Cheng, L. Yang, and B. Jiao, A unified tdma-based scheduling protocol for vehicle-to-infrastructure communications, in International Conference Wireless Communications and Signal Processing (WCSP), Hangzhou, Oct. 2013, pp. 1-6.
 R. Zhang, X. Cheng, L. Yang, X. Shen, and B. Jiao, A novel centralized tdma-based scheduling protocol for vehicular networks, IEEE Transactions on Intelligent Transportation Systems, vol. PP, no. 99, pp. 1-6, Aug. 2014.
 M. Hadded, A. Laouiti, P. Muhlethaler, and L. A. Saidane, A centralized TDMA based scheduling algorithm for real-time communications in vehicular ad hoc networks, 24th International Conference on Software, Telecommunications and Computer Networks (SoftCOM 2016), Split, Croatia, Sep. 2016, pp. 1-6.
 F. Karnadi, Z. Mo, and K. chan Lan, Rapid generation of realistic mobility models for VANET, in IEEE WCNC, Hong Kong, China, Mar. 2007, pp. 2506-2511.
 SUMO Simulator: http://sumo.sourceforge.net.
(1.) Road Side Units
Institut Superieur de Technologie
Universite Paris Descartes
143 Avenue de Versailles, 75016 Paris, France
SAMOVAR, Telecom SudParis, CNRS
9 rue Charles Fourier 91011 EVRY, France
Caption: Figure 1. TDMA slots scheduling mechanism of CTMAC
Caption: Figure 2. Simulation framework.
Caption: Figure 3. VANET network topology captured from Google MAP.
Caption: Figure 4. Average number of transmitted safety messages vs frame number
Caption: Figure 5. Average number of received safety messages vs frame number
Table I. Simulation parameters Parameter Value Simulation duration 120 (s) Speed 120 (km/h) Speed standard deviation 30 (km/h) Number of slots per frame ([tau]) 100 Slot duration 0.001 (s) Highway length 2.5 (km) The number of lanes per direction 2 The radio range (R) 310 (m)
|Printer friendly Cite/link Email Feedback|
|Title Annotation:||time-division multiple access|
|Author:||Hadded, Mohamed; Laouiti, Anis|
|Publication:||International Journal of Digital Information and Wireless Communications|
|Date:||Apr 1, 2018|
|Previous Article:||A Study of Multi-Operator Resource Sharing using Markov Chain Model.|
|Next Article:||Low Noise Power Amplifier in 28-nm UTBB FDSOI Technology with Forward Body Bias.|