1. Introduction

In recent years, Vehicular Ad-hoc Networks (VANETs) technology has drawn interest of many researchers as a common platform for inter vehicle communication on highways or in urban environments [1-5].  As a special type of Mobile Ad-hoc Network (MANET), VANET provides communications among vehicles and between vehicle, and infrastructure via Road Side Units (RSUs).  The relevance of VANET has been confirmed by the development of a specific IEEE standard, 802.11p, to support VANETs [2].

Different from other ad-hoc networks, VANET has unique characteristics of high node mobility, dynamic topology changes and strict delay constraints. The applications devised for VANETs can be divided into the following three services: safety services, traffic management and user-oriented services. Among these services, safety services usually require bounded transmission delays as well as low access delays. As the IEEE 802.11p standard does not provide a reliable broadcast mechanism with bounded communication delay [2, 6], it is not sufficient for VANET applications which are primarily envisioned to improve road safety.

As opposed to IEEE 802.11p, Time Division Multiple Access (TDMA) is inherently a collision free scheme with bounded access delay. Several protocols have been proposed in VANETs using TDMA to provide fairness and to reduce interference among vehicles. By concatenating or rescheduling time slots based on access priority, TDMA based schemes can also assign bandwidth resources to different vehicles on-demand. However, for TDMA based Medium Access Control (MAC) protocol, an efficient slot management is very crucial to ensure fairness as well as reusability of unused slots. VANETs, which have very dynamic topology, are very much prone to allocating a time slot in overlapping areas. In this case, two types of collision may occur: access collision between vehicles trying to access the same available time slots, and merging collisions between vehicles using the same time slots. Some researchers worked on collision issues and some worked on fairness; however, a comprehensive protocol to ensure fairness and reallocation of unused slots is still missing.

In this work, we propose a new TDMA based MAC scheme, Dynamic Reallocation based Window Access MAC (DRWA-MAC), to achieve fair slot allocation as well as reallocation of unused slots dynamically. Our scheme allocates time slots to the registered vehicles evenly; then it monitors the usage of the assigned slots to ensure the dynamic reallocation of unused slots in a fair way. Simulation results in OMNET++ show that our proposed scheme outperforms several existing schemes. This work is an extension of our previous work originally presented and published in ECCE conference [1].

2. Related Work

VeMAC [7, 8] is a TDMA based scheme proposed for inter-vehicle communication in which vehicles in opposite directions (Left, Right) and roadside units (RSUs) are assigned with time slots in the same TDMA time frame by using logical segmentation. Though VeMAC can make use of the seven DSRC channels and decrease the rates of merging, and access collisions, it is burdened with the overhead of the size of the transmission control frame and cannot ensure reusability of an unused slot.

In ACFM [9], each RSU maintains a dynamic slot assignment cycle for vehicles in its coverage adaptively. Under the scenario of light traffic, ACFM controls the excessive increase of unassigned slots by shrinking slots assignment cycle frame by frame. When there is a mass of vehicles on roads, ACFM provides more available slots by expanding cycle. However, to avoid interference between adjacent segments, ACFM requires two orthogonal frequencies to ensure that the same frequency is not used for a distance of two hops.

TC-MAC [6] is a TDMA Cluster-based MAC protocol for VANET. It subdivides slots of control channel (CCH) into mini-slots to broadcast beacons or safety messages. Here, in each frame, each vehicle gets allocation on a time slot in service channel (SCH) and competes for a mini-slot on the CCH. A vehicle uses its mini-slot to inform the other vehicles of its transmission during time slot on the SCH. Cluster members can use their time slots on the service channels to exchange non-safety data in unicast or multicast communication mode. TC-MAC protocol was designed for simple highway traffic in which all the vehicles are moving in the same direction and it has high collision in bidirectional traffic and in urban scenarios due to the merging collision problem. TC-MAC also suffers from inter-cluster interference problem when two or more clusters are in close proximity.

PTMAC [10] is a prediction-based TDMA MAC protocol that predicts encounter collisions and effectively reduces the number of collisions while maintaining high slot utilization. Here, immediate vehicles within a two-hop neighborhood detects a potential collision if two vehicles occupies the same slot and the protocol removes the collision by asking one of them to change its current slot. As PTMAC makes TDMA slot assignment on a contention based approach, it is unable to ensure fairness.

FAWAC-MAC [1] is a TDMA based scheme that uses capture effect to send extra data in free or unused slots. Here, all vehicles, which are not the owner of the current slot, check whether its own slot is within a predefined window size. If not, they transmit their packets in low power while the original owner of the slot transmits packets in high power. Using capture effect, the RSU can distinguish the power levels. In the presence of a high power packet, all low power packets get discarded; while in the absence, low power transmission succeeds. When vehicle density is very high, FAWAC-MAC has a chance of low power packet collision in free slots and if the coverage area is large, then it may also be suffered by near-far effect.

FAWAT-MAC [1] uses time slot reassignment mechanism to transmit data in unused slots.  Here, if an RSU detects no ongoing transmission within one fourth of the beginning time of a slot, it selects the slot as unused and invites another vehicle to transmit data in that slot. Upon reception of the invitation packet, the specific vehicle transmits data for the remaining time of the slot in a collision free manner. The slot allocation process of FAWAT-MAC can cause merging and one-hop neighboring collision for boundary vehicles. In this protocol, the waiting time for some of the high speed boundary vehicles can be so high that by the time they got their assigned slot, they may have left the corresponding RSU.

3. Proposed System

In this work, we propose Dynamic Reallocation based Window Access MAC (DRWA-MAC), an extension of the FAWAT-MAC protocol [1]. Our proposed protocol operates as a TDMA based MAC protocol in a centralized topology where RSUs control distribution and reallocation of slots.

3.1.  Assumptions

We made the following assumptions regarding VANET’s context in which DRWA-MAC operates:

• Each vehicle and RSU has a unique ID.
• Vehicles and RSUs are equipped with GPS and are perfectly time synchronized.
• At the beginning of each frame, the RSU transmits registration beacon and then, each vehicle, which receives that message, broadcasts a registration response message with its own ID, location and data size. For a certain amount of time, the whole registration response system is a contention based process.
• Each newly joined vehicle that does not have a slot and wants to get a new slot shall listen to the channel for one frame. Then, after receiving the registration beacon, they can register to the RSU.

Figure 1: Right and left direction of vehicle movement as defined in the protocol

3.2.  System Design

In our proposed DRWA-MAC protocol, we consider RSU based centralized VANET with a set of vehicles moving in lanes consisting of two-way traffic. In a two-way traffic system, we define a vehicle as positioned in left direction of a RSU’s broadcasting area if it is placed in the west half and right direction, if it is placed in the east half, as shown in Figure 1.

Our scheme consists of three processes: (i) a contention based registration process, (ii) a fair slot distribution process and finally, (iii) a network monitoring process for reallocating unused slots. Considering the effect of these processes, the states of a vehicle and RSU in our proposed scheme is depicted in Figure 2 and Figure 3 respectively.

As shown in Figure 2, upon reception of RSU’s registration beacon, a vehicle moves into the registration state from its initialize state and sends back a registration response. Then, after receiving RSU’s response, the vehicle moves into the network monitoring state; once a slot is assigned, the vehicle moves to the data transmission state where it transmits data in the slot assigned to it. At the end of the slot, the vehicle moves back to the network monitoring state and waits for additional slots from the RSU. When data transmission is complete, the vehicle moves back to the initialize state.

Figure 2: Vehicle state diagram in our scheme where a vehicle can be in one of the four states: initialize, registration, network monitoring, and data transmission

Figure 3: RSU state diagram in our scheme where the RSU can be in one of the four states: initialize, registration, slot allocation, and network monitoring

As shown in Figure 3, after transmitting registration beacon, an RSU enters into the registration state where it receives response from vehicles for a short amount of time. After receiving registration response(s) from the vehicles, the RSU enters into the slot allocation state where it allocates available slot to the vehicles; then, it transmits a registration response message and moves to the network monitoring state where the RSU monitors network for free slots. If any free slot is detected, the RSU moves back to the slot allocation state; otherwise, it moves to the initialize state at the end of the TDMA frame.

4. Details of the DRWA-MAC Protocol

4.1.  Registration Process

At the beginning of the TDMA frame, RSU transmits a registration beacon for all the vehicles in its broadcasting area. Upon reception of the registration beacon, each vehicle sends back a registration response message to the RSU using a contention based approach. To accommodate the vehicles response, this contention based procedure continues for a certain predefined amount of time. Within registration response message, vehicles send back their ID, location and data size.

4.2.  Slot Distribution Process

After registration process, RSU’s usually have N number of participating vehicles that need to be assigned with S number of slots. As the registration response from each vehicle consists of location information, RSU can differentiate the L number of vehicles on its left and the remaining (N-L) number of vehicles on its right direction in a road with two-way traffic. Our protocol divides the available S slots into S/2 ODD, and S/2 EVEN sets. Then, the S/2 ODD slots are distributed among the L left directional vehicles and S/2 EVEN slots to (N-L) right directional vehicles. Our protocol uses a repeated round robin approach for channel assignment. In case the number of vehicles is less than the number of slots, i.e., S>N, one or more vehicle may get multiple slots in the same frame. An example is shown in Figure 4 where there are 8 slots in a frame with two left direction vehicles (V[1], V[3]), and two right direction vehicle (V[2], V[4]); a repeated round robin distribution will allocate slot 1, and 5 to V[1], slot 2, and 6 to V[2], slot 3, and 7 to V[3] and slot 4, and 8 to V[4]. On the other hand, if L < S/2 and (N–L) > S/2, one or more left directional vehicles will get multiple slots but (N–L–S/2) right directional vehicles will not get any slot allocation. Our slot distribution algorithm is shown in Algorithm 1.

Algorithm 1: TDMA Slot Distribution
1:	foreach available slot s in frame f
2:	calculate even slot es and odd slot os
3:	foreach registered vehicle v
4:	If vehicle v is right directional and es>0
5:	assign an  even slot es to vehicle v
6:	es = es – 1;
7:	else if os>0
8:	assign an odd slot os to vehicle v
9:	os = os – 1;
10:	s = s – v;

Figure 4: Example of slot allocation in our proposed scheme using repeated round robin distribution where the index represents vehicle ID. In this example, there are 4 vehicles where each vehicle received 2 slots each

4.3.  Transmission Monitoring Process

After slot assignment, vehicles usually begin transmission in their assigned slots. Even though all the vehicles register for TDMA slot, some of them may not use all of their assigned slot(s); this could be due to early completion of data transmission, passing over RSU’s broadcasting area, detection of the safety message that is already broadcasted, etc. To avoid wastage, for each slot, our protocol employs a monitoring process at the RSU end to check whether an existing transmission is going on or not; if not, then it ensures reallocation. Here, an RSU detects transmission status by monitoring the first one fourth of the beginning time of a slot; if no data is transmitted during this period, the RSU mask the slot as a free and broadcasts a very light NULL packet similar to a becon signal. Inside the NULL packet, RSU sends the ID of the vehicle having maximum data size; this is possible because at the beginning of the frame, each vehicle registers with its data size. Upon reception of the NULL packet, the specific vehicle transmits data for the remaining time of the slot and hence, reallocation of unused slots is achieved in a collision free manner.

Figure 5 shows operation of the proposed DRWA-MAC in detail. Here, V[1], and V[3] are left directional vehicles and V[2], V[4] are right directional vehicles. V[1], V[2], V[3], and V[4]  have 24MB, 22MB, 4MB, and 4MB of data to transmit respectively. These vehicles V[1], V[2], V[3], V[4] are assigned with slots (1,5), (3,7) and (2,6), (4,8) respectively by our slot allocation algorithm. Considering max data size of each slot as 4 MB, at slot 7, RSU will detect that there is no ongoing transmission in channel as V[3] has no data left to send and therefore, will select V[1] as it has 16 MB data remaining for transmission (out of 24 MB, V[1] has transmitted 8 MB in slot 1 and 5). So, V[1] will be able to send 3 MB of data in the remaining 3/4 of the slot and will have 13 MB data left for transmission. At slot 8, RSU again will detect that there is no ongoing transmission in the channel as V[4] has no data left to transmit and will select V[2] as it has 14 MB data remaining while V[1] has 13 MB of data remaining to transmit.

5. Effectiveness

In our protocol, the use of “time slot reassignment” technique makes use of most of the wasted slots and hence, increases overall throughput of the TDMA network. As our protocol works in RSU based centralized topology, it is free of access collision. Since the proposed protocol uses RSU’s guidance based “time slot reassignment” technique where a single vehicle is selected by RSU to send message in free slots, it is also free from hidden node collision.

Figure 5: Operation of proposed DRWA-MAC with four vehicles and 8 slots in each frame where 4MB of data can be transmitted in each slot. Initial slot assignment is as shown in Figure 4

Instead of straight forward segmentation like VeMAC, our protocol divides and allocates slots in ODD-EVEN basis and it balances waiting time of the partitioned vehicles. This distribution process also avoids or minimizes merging collision and one-hop neighboring collision. To support our argument, an example scenario is depicted in Figure 6. In this scenario, there are 2 RSUs, RSU[0], and RSU[1]. We show that vehicle V[4], V[6] of RSU[0] and V[5], V[7] of RSU[1] are one hop neighboring collision free as RSU[0] assigns EVEN slots to V[4], and V[6] and on the other hand, RSU[1] assigns ODD slots to the vehicles v[5], and v[7]. Additionally, if we consider the position of vehicle V[5] of RSU[1] and V[1] of RSU[0], we can claim that our protocol also minimizes merging collision because both V[5] and V[1] are placed in left/west half of their respective RSU and each is assigned with ODD slots. By the time V[5] enters into the coverage area of  RSU[0], V[1] may leave and the slot freed by V[1] can be reassigned to V[5] so that V[5] can transmit data in the  running frame.

Figure 6: Example scenario of proposed DRWA-MAC protocol which depicts that the protocol is free from one-hop neighboring collision and merging collision

6. Simulation Results and Analysis

In our simulation experiments, we have compared the performance of our proposed DRWA-MAC protocol with ACFM, VeMAC, PTMAC, FAWAC-MAC and FAWAT-MAC in terms of number of successfully transmitted data packet, average delay, and data loss ratio on overall road traffic network.

6.1.  Simulation Environment

We have implemented DRWA-MAC protocol on the VEINS [11] framework of OMNET++ [12] network simulator. The vehicle movement and related realistic road traffic scenario is generated using SUMO [13] urban mobility traffic generator.

Figure 9: Performance comparison in term of successfully transmitted data packets when 10% of the vehicles are not using their assigned slots

In our scenarios, we considered a 2000m×1000m rectangular two way road traffic network with ten junctions as shown in Figure7, where each junction contains three lanes. We have covered our road network segment with three non-overlapping RSUs as shown in Figure 8.

For comparison, we have devised five scenarios with 22, 41, 61, 83, and 102 vehicles and measured the performance of the mentioned protocols in cases where 10%, 15% and 20% of the registered vehicles were not using their assigned slots. Configuration of the simulation is listed in Table 1.

Figure 7: 2000m×1000m rectangular traffic network with ten junctions and 3×3 lane road in SUMO

Figure8: OMNET++ view of the road network with RSUs

Table 1: Simulation Parameters
Parameter	Value
Number of lanes	3+3
Number of scenario	5
Number of vehicles	22, 41, 61, 83 and 102
TxPower	20mW
TxDatasize	10Mbps
Number of slots per frame	256
Slot time	50ms
Registration time	2s
Simulation time	2 frames, on 258s to 288s

6.2.  Simulation Result

In this section, we show performance comparison of DRWA-MAC with the aforementioned protocols.

Figure 9 shows performance comparison in terms of successfully transmitted data packets when 10% of the vehicles are not using their assigned slots. As shown in Figure 9, initially at light traffic, only FAWAC-MAC performed better than DRWA-MAC. However, the performance of FAWAC-MAC gradually decreased with the increase of traffic. In high traffic scenarios, the performance of VeMAC, ACFM, PTMAC and FAWAT-MAC degraded noticeably. This is because these protocols suffer from merging collision and one-hop neighboring collision. On the other hand, DRWA-MAC minimized these collisions and outperformed all the other schemes when network density is higher.

Figure10: Performance comparison in terms of average delay when 10% of the vehicles are not using their assigned slots

Figure 12: Performance comparison in terms of successfully transmitted data packets when 15% of the vehicles are not using their assigned slots

Figure 10 shows performance comparison in terms of average delay when 10% of the vehicles are not using their assigned slots. Though for a single channel, the overall throughput of VeMAC is not optimum, it has the most favorable average delay. On the other hand, our proposed DRWA-MAC performed better by maintaining almost the same average delay as ACFM, PTMAC, FAWAC-MAC and FAWAT-MAC.

Figure11: Performance comparison in terms of data loss ratio when 10% of the vehicles are not using the slots assigned to them

Figure 13: Performance comparison in terms of successfully transmitted data packets when 20% of the vehicles are not using their assigned slots

Figure 11 shows performance comparison in terms of data loss ratio where 10% of the registered vehicles are not transmitting data in the assigned slots. Because of inherent huge low power transmission, as shown in Figure 11, FAWAC-MAC is having high data loss, though those low power packets were bearing opportunistic data. VeMAC has the lowest data loss ratio while DRWA-MAC has similar data loss ratio compared to other protocols.

In Figure 12 and 13, we show performance comparisons in terms of successfully transmitted data packets for cases where 15% and 20% of the registered vehicles are not transmitting data in their assigned slots respectively. With the increase of free slots, the performance of VeMAC, ACFM and PTMAC decreased as these protocols do not have any process to ensure reusability of slots. However, as FAWAC-MAC, FAWAT-MAC and DRWA-MAC can unsure reusability of free slots, their performance were not affected significantly. From Figure 9, 12 and 13, we can conclude that though FAWAT-MAC and DRWA-MAC improves the amount of successful data transmission by ensuring reallocation of free slots even though one fourth of the data capacity of those free slots degraded due to the detection delay of the RSU.

Figure 14: Bar diagram of successfully transmitted data packets by grouping scenarios where 10%, 15% and 20% of the vehicles are not using their assigned slots

Figure 14 shows a bar diagram of successfully transmitted data packets for 102 cars in the network by grouping scenarios where 10%, 15% and 20% of the vehicles are not using their assigned slots. This diagram is also shows that with the increase of free slots, the performance of VeMAC, ACFM and PTMAC decreased, but the performance of FAWAC-MAC, FAWAT-MAC and DRWA-MAC were not affected significantly. As shown in the figure, DRWA-MAC outperforms all other schemes in terms of successfully transmitted data packet in all the experimental scenarios.

7. Conclusion

This article proposes a dynamic reallocation based window access scheme, DRWA-MAC, for centralized TDMA based VANETs. The proposed scheme maintains a balanced waiting time for vehicles by dividing TDMA slots into ODD slots and EVEN slots and then, by evenly distributing all TDMA slots among the registered vehicles in a rational way. Our slot allocation algorithm ensures fairness in slot allocation among the vehicles as well as reduces merging collision and one-hop neighboring collision. By dynamically monitoring and reallocating unused slots using “time slot reassignment” mechanism, the proposed DRWA-MAC achieved significantly higher throughput compared to other conventional TDMA based centralized protocols. Simulation results show the effectiveness of the proposed protocol in terms of successfully transmitted data packets, average delay and data loss ratio on overall road traffic network in different scenarios.

1. Amirul Islam, Shafika Showkat Moni and Mohammad Shah Alam, “A Fixed Assignment Based Window Access Scheme for Enhancing QoS of Vehicular Adhoc Networks” in International Conference on Electrical, Computer and Communication Engineering (ECCE), February 16-18, 2017.
2. Mohamed Hadded, Paul Muhlethaler, Anis Laouiti, Rachid Zagrouba, Leila Azouz Saidane, “TDMA-based MAC Protocols for Vehicular Ad Hoc Networks A Survey, Qualitative Analysis and Open Research Issues” inIEEE Communication Surveys and Tutorials, Volume: 17, Issue: 4, February 2015.
3. Laouiti, Anis, Qayyum, Amir, Mohamad Saad, Mohamad Naufal, “Vehicular Ad-hoc Networks for Smart Cities” in First International Workshop(Advances in Intelligent Systems and Computing), 2014.
4. J. Booysen, S. Zeadally, G.-J. Van Rooyen, “Survey of media access control protocols for vehicular ad hoc networks”in IET Communication, 2011, Vol. 5, Iss. 11, pp. 1619–1631.
5. Georgios Karagiannis, Onur Altintas, Eylem Ekici, Geert Heijenk, Boangoat Jarupan, Kenneth Lin, and Timothy Weil, “Vehicular Networking: A Survey and Tutorial on Requirements, Architectures, Challenges, Standards and Solutions” in IEEE Communications Surveys & Tutorials, Volume: 13, Issue: 4, 2011.
6. Mohammad S. Almalag, Stephan Olariu, Michele C. Weigle, “TDMA Cluster-based MAC for VANETs (TC-MAC)” in IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), June 2012.
7. Omar, W. Zhuang, and L. Li, “VeMAC: A Novel Multichannel MAC Protocol for Vehicular Ad Hoc Networks” in IEEE Conf. Computer Communications Workshops (INFOCOM WORKSHOPS), April 2011, pp. 413–418.
8. Omar, W. Zhuang, and L. Li, “VeMAC: A TDMA-Based MAC Protocol for Reliable Broadcast in VANETs” in IEEE Transactions on Mobile Computing, Volume: 12, Issue: 9, September 2013, pp. 1724 – 1736
9. Weijie Guo, Liusheng Huang, Long Chen, Hongli Xu, Jietao Xie, “An Adaptive Collision-Free MAC Protocol Based on TDMA for Inter-Vehicular Communication” in International Conference on Wireless Communications & Signal Processing (WCSP), 2012.
10. Xiaoxiao Jiang and David H.C. Du, “PTMAC: A Prediction-based TDMA MAC Protocol for Reducing Packet Collisions in VANET” in IEEE Transactions on Vehicular Technology (Volume: PP, Issue: 99), 19 January 2016.
11. Christoph Sommer, “Veins – The open source vehicular network simulation framework”, Web Link “http://veins.car2x.org/”.
12. András Varga, “OMNeT++, Discrete Event Simulator”, Web Link “https://omnetpp.org/”.
13. DLR – Institute of Transportation Systems, “SUMO, Simulation of Urban MObility”, Web Link “http://sumo-sim.org/”.

(Click to view)

(Click to view)