A Prediction-based TDMA MAC Protocol for Reducing - Projectsgoal

Loading...

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 1

PTMAC: A Prediction-based TDMA MAC Protocol for Reducing Packet Collisions in VANET Xiaoxiao Jiang and David H.C. Du Department of Computer Science and Engineering University of Minnesota, USA [email protected], [email protected]

Abstract— With the rapid development of wireless communications, Vehicular Ad-Hoc Network (VANET) has recently attracted great attention. Although IEEE 802.11p has been approved as the standard medium access control (MAC) protocol for V2V communications, its contention-based nature and inability to handle hidden terminal problem may incur high packet collision probability under high traffic density situation. To overcome the shortcoming of IEEE 802.11p, TDMA based protocols are proposed. However, packet collisions can still occur due to contention or multiple vehicles using the same slot while approaching each other called encounter collisions, especially in two-way traffic roads. Some proposed remedying the encounter collisions for two-way traffic by partitioning a frame into two sets: one for traffics in each direction. However, these proposed protocols are harder to adapt to the uneven traffic loads on both directions and cannot solve the problem of four-way intersections. In this paper, we propose a new TDMA protocol called PTMAC based on a novel way of predicting encounter collisions and effectively reducing the number of collisions. To the best of our knowledge, PTMAC is the first protocol that is designed for both two-way traffic and four-way intersections. It has shown that based on this predictability, the encounter collisions can be greatly reduced in both two-way traffic and four-way intersections regardless of the traffic loads on different road segments. Keywords: Medium Access Control (MAC), Time Division Multiple Access (TDMA), Packet Collision Prediction, VANET

I.

I NTRODUCTION

With the development of wireless communications, Vehicular Ad-Hoc Network (VANET) has recently attracted increasing attention. As a special type of Mobile Ad-Hoc Network (MANET), VANET provides communications among vehicles and between vehicle and infrastructure via RSUs (Road Side Units). In North America, The US Federal Communications Commission (FCC) has allocated 75MHz of spectrum in the 5.9GHz band for Dedicated Short-Range Communications (DSRC) to be used by Intelligent Transportation Systems (ITS). Different from other Ad-Hoc networks, VANET has the unique characteristics of high node mobility, dynamic topology changes and strict delay constrains. These issues must be considered in developing MAC protocols for VANET to support both safety and non-safety related applications. Copyright (c) 2015 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to [email protected]

Although the carrier sense multiple access/collision avoidance (CSMA/CA) based IEEE 802.11p [1] has been approved as the standard Medium Access Control (MAC) protocol, it has the problem of high collision probability if the traffic density is high, especially for packet broadcasting [2]–[5]. Broadcasting plays an important role on propagating safety related messages like vehicle accident warning and road condition alerting. Besides the event driven messages, Wireless Access in Vehicular Environments (WAVE) [6] also develops additional layer protocol including the basic safety messages (BSMs) and WAVE-Basic Service Advertisements (WSAs) [7], [8]. The BSM contains critical vehicle’s status information like its location and speed. To support most of the applications and make sure the potential dangers can be detected on time, every vehicle is required to broadcast and exchange BSMs periodically, that is, at least once in every 100ms [9]. WSAs are also needed to be periodically broadcasted by RSUs or vehicles to mostly support non-safety services. Based on IEEE 802.11p MAC protocol, if the channel is sensed as idle, a vehicle starts the transmission directly. Otherwise, it needs to randomly pick up a back-off value from the Contention Window (CW) and start a countdown procedure. Transmission will begin when the back-off value reaching 0. If multiple vehicles within two-hop communication range (two times communication range) try to access the channel simultaneously, a collision will happen and none of the packets can be received successfully. In this case, vehicles have to re-compete for the channel to resend the packets. An exponential back-off scheme which extends the contention window size for decreasing the possibility of contention collision is applied for unicast retransmission. However, as a contention based scheme, CSMA/CA has the drawback of potentially unbounded channel access delay [10]. If a vehicle has multiple packets, it has to contend for multiple times. Furthermore, 802.11p is vulnerable to the hidden terminal problem since it cannot use RTS/CTS mechanism for packet broadcasting [3]. In this case, the packet collision cannot even be detected right away. No exponential back-off scheme can be used for broadcasting and the probability of packet collision is potentially high [2]. To overcome the shortcomings of IEEE 802.11p, time division multiple access (TDMA) based MAC protocols have been proposed to facilitate efficient transmission in VANET [11], [12]. Basically, there are two types of TDMA based MAC protocols: distributed TDMA and centralized TDMA.

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 2

Each node manages its time slot by itself in distributed TDMA while all the time slots are allocated by a central node in a centralized TDMA [13]–[16]. [16] took advantage of RSUs to collect vehicle information and make schedule decision based on the channel quality, speed and AC. However, this scheme requires large number of RSUs and is only suitable for urban area. [13]–[15] used Cluster Heads as the central nodes and partitioned vehicles into several clusters. However, the clusterbased scheme faces the challenges of cluster forming, Cluster Head selection and cluster changing. Therefore, considering the high mobility nature of vehicles, we focus on distributed TDMA based MAC protocols which provide a more flexible way for slot management. The most basic distributed TDMA based protocol has been proposed in [11], [12] using time slotted structure. The time is partitioned into repeated frames and each frame is composed of a fixed number of slots as shown in Figure 1. Each vehicle selects a specific time slot to transmit data. If successful, it keeps on using the same slot at subsequent frames until a collision occurs or the slot is no longer needed. Since every vehicle is required to broadcast the slot information about all its one-hop neighbors, a vehicle is able to know which slot is still available. Therefore, the possibility of transmission collision is reduced and each node is guaranteed to access the channel at least once in each frame if the reservation is successfully made. There is no need for each individual packet to compete for the channel.

Fig. 1.

protocol (PTMAC) to reduce the possibility of encounter collisions. To the best of our knowledge, PTMAC is the first protocol that is designed for both two-way traffic and fourway intersections. Our main contributions in this paper can be summarized as follows: • Designing a new Prediction-based TDMA MAC protocol (PTMAC) for decreasing the probability of encounter collisions while maintaining high slot utilization and with very small additional overheads. Most of the encounter collisions can be predicted and potentially eliminated before they really happen. The prediction is based on the vehicle information that is already provided to support safety related application. • Our newly designed PTMAC protocol is demonstrated to be suitable for both two-way traffic scenario and fourway intersections in an urban area. Unbalanced traffic densities will not degrade the performance of PTMAC. • Through measuring and comparing our PTMAC protocol with ADHOC MAC [12] and Even-Odd TDMA MAC [17], we show that PTMAC has better performance with fewer collisions and higher delivery rate for both twoway and four-way intersection scenarios. The rest of paper is organized as follows: Section 2 overviews the related work. We introduce our proposed PTMAC protocol under two-way scenarios in Section 3 and extent it for four-way intersections in Section 4. Performance analysis of ADHOC MAC, Even-Odd MAC and PTMAC is provided in Section 5. In Section 6, we evaluate the performance of our PTMAC protocol and compare it with other TDMA-based MAC protocols and Section 7 gives a conclusion of our work.

Time Frame and Slot in TDMA

Considering a real traffic environment, a few distributed TDMA MAC protocols have been proposed for two-way traffic scenario [17], [18]. There are two types of collisions, one is contention collision which happens between newly joining vehicles who are trying to reserve the same available slot within two-hop communication range. The newly joining vehicles as those who have not reserved a slot and intend to transmit packets. Another type of collision is encounter collision which happens between vehicles that are currently occupying the same time slot. They are originally out of two-hop range but approach and encounter each other later. Although some slot partition methods like Even-Odd [17] are proposed for eliminating the encounter collisions between vehicles running at opposite directions, the slot utilization becomes low when the traffic density is high in one direction while low in another. Moreover, they cannot eliminate the encounter collisions among vehicles from the same direction. Furthermore, none of the previously proposed MAC protocols work well at four-way intersections. Base on the report by USDOT [19], vehicle information like speed, position and moving direction is required and should be broadcasted by every vehicle periodically to support the safety related applications in VANET. Therefore, we make an important observation that most of the encounter collisions can be predicted and potentially avoided base on such vehicle information. We design a new Prediction-based TDMA MAC

II. R ELATED W ORK Besides the TDMA based MAC protocol, Space Division Multiple Access (SDMA) based schemes are also considered [20]–[22]. The basic idea of SDMA is to divide the road into separated cells and each cell has its own assigned time slot. However, the network utilization is potentially low when the traffic is sparse. It is a waste of bandwidth to assign slots to the cells with no vehicle. The fairness may also become a problem for different traffic densities on different cells. Therefore, we focus on TDMA based protocol in this paper. Detailed comparisons between CSMA/CA and TDMA based MAC protocols in VANET have been provided in some previous works [23]–[25]. They have shown that TDMA performs more reliable and robust when comparing with IEEE 802.11p. ADHOC MAC proposed by Borgonovo et al. in [12] is a basic TDMA based protocol. It was designed for AdHoc Networks to provide efficient and reliable data delivery service. It grouped a set of time slots into a frame and defined a concept of Frame Information (FI) which contains the time slot status. Each vehicle is responsible for broadcasting its FI to inform others the occupied slots by its one-hop neighbors and itself. In this way, every vehicle can get all its neighbors’ slot information within a two-hop range. A new joining vehicle needs to listen to the channel for a frame and then selects an available time slot to transmit data at the next frame. If other near-by vehicles receive the transmitted data, they will add

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 3

this new slot information into their FI messages to indicate the success of the slot contention. In this way, the new joining vehicle is able to learn if its slot contention is successful or not through the broadcasted FI messages from its neighbor vehicles. Once a vehicle gets a slot successfully, it keeps on using the same slot at subsequent frames until a collision happens or it does not need the slot anymore. However, this slot reservation scheme cannot handle the encounter collisions. Based on the slotted structure that has been proposed in [12], some improved TDMA based MAC protocols have been developed for VANET [26]–[28]. Liu et al. proposed an adaptive distributed MAC named A-ADHOC in [26]. Since the fixed-size frames may waste slots and introduce unnecessary delay under a sparse traffic condition, A-ADHOC dynamically adjusts the length of a frame based on the real-time traffic density. They showed that A-ADHOC can enhance the performance with less transmission delay. Yu and Biswas proposed a self-configuring protocol called VeSOMAC in [27]. Unlike other schemes that select a time slot randomly, the authors paid more attention to the ordering of time slots. They ordered time slots in the same sequence as the vehicles appear on the road to reduce the packets forwarding delay. In [28], Bharati et al. developed a cooperative protocol named CAH-MAC based on ADHOC MAC. Their scheme allows the neighbors who detected a transmission failure to retransmit the packet using an unreserved slot. But they ignored the fact that new joining vehicles may also contend for the same unreserved slot. Thus, more contention collisions are introduced. These proposed protocols only considered one-way traffic and did not focus on reducing the number of transmission collisions. A few MAC protocols have been designed for two-way traffic using slot partition [17], [18]. Zhou et al. proposed a MAC protocol based on Even-Odd partition in [17]. They regulated that vehicles heading right can only contend for even slots while vehicles running left can only contend for odd slots. In this way, encounter collisions caused by vehicles from the opposite directions can be totally avoided. However, the slot utilization is low when the traffic density is high in one direction while low in another direction. Omar et al. proposed another TDMA based MAC protocol called VeMAC in [18]. Each frame is partitioned into three sets of slots: L, R and F. The F set is related to the RSU while L and R sets are associated with the vehicles moving in Left and Right respectively. Unlike the MAC protocol in [17], this slot partition is not strict, that is, if a vehicle cannot reserve a slot successfully in a period of time, it is allowed to contend for a slot that originally assigned to the opposite direction. Although such a compromise can somewhat increase the slot utilization, its random slot borrowing scheme increases the probability of encounter collisions among vehicles at opposite directions. The more slots borrowed from the opposite direction, the more likely an encounter collision will happen. If the number of borrowed slots is large, the partition scheme become meaningless and it cannot efficiently eliminate the encounter collisions anymore. In addition, before a vehicle is allowed to contend for a slot which is assigned to the other direction, it may already experience several contention collisions. Although the TDMA based MAC protocols proposed in

[17], [18] using slot partition method can reduce the number of encounter collisions, they potentially incur low slot utilization and more contention collisions for the direction with heavier traffic density. They also cannot avoid the encounter collisions among vehicles heading the same direction. Furthermore, the traffic pattern at four-way intersections is much more complicated than two-way traffic and protocols that are proposed previously do not work anymore. Therefore, we design a novel prediction based MAC protocol to solve these problems. III. PTMAC PROTOCOL FOR TWO-WAY TRAFFIC We have made an important observation that most of the encounter collisions can be predicted and potentially avoided based on vehicles’ moving patterns and traffic condition. Therefore, instead of using slot partition method, we propose a novel MAC protocol that takes advantage of prediction to remove potential collisions. Our PTMAC protocol is described under two-way traffic scenario in this section and it will be extended to four-way intersections in the next section. For both two-way and four-way scenarios, there are three steps need to be processed in PTMAC protocol: Potential Collision Detection, Potential Collision Prediction and Potential Collision Elimination. A potential collision needs to be detected first based on the slot information. Then we can predict if this potential collision will really happen in the future based on the real-time traffic condition and vehicles information. Finally, we reschedule the slots to eliminate this potential collision. Detailed descriptions of these three steps will be provided in the following of this section. Notice that the collisions we mention here means encounter collisions, so as the following of this paper, unless we point out that it is a contention collision. Recall that in a TDMA based protocol, each vehicle will first contend for an empty slot in a frame. It will continuously use this slot if successfully transmitted first time. A contention collision happens if multiple vehicles within two-hop communication range contend for the same slot. An encounter collision is caused by two vehicles approaching each other while using the same slot in a frame. A. Assumptions Firstly, some assumptions are made based on the basic TDMA MAC protocol that has been proposed in VANET: 1. Every vehicle broadcasts a message at every frame which includes its own location, speed and moving direction. Such vehicle information is required by most of the safety related applications. This message also contains the Frame Information (FI) about all the occupied slots by its own and its one-hop neighbors. 2. Every vehicle keeps the slot information about its onehop and two-hop neighbors which are shared by its one-hop neighbors. 3. Each newly joining vehicle that has not obtained a slot and wants to get a slot needs to listen to the channel for one frame. Then, they can randomly choose an available slot at the next frame for transmission. 4. Each vehicle is equipped with a GPS device that provides the information about its own location, moving direction and

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 4

speed. Road information like road length is also available. Such information can also be obtained from RSU broadcasting. The assumptions about the slot information follow the ADHOC MAC proposed in [12]. ADHOC MAC does not need additional information other than the frame information and works well for one-way traffic. PTMAC needs more vehicle information for predicting the potential encounter collisions. Fortunately, information like vehicle speed, location and moving direction are generally required by most of the applications for safety purposes. To support most of the safety related applications, USDOT considers two types of safety messages as helpful for disseminated: event-driven messages and periodic messages [19]. The event-driven messages are sent when a dangerous condition is detected. Meanwhile, the periodic messages are broadcasted by every vehicle periodically. It usually contains the vehicle status information like speed, position and moving direction. Since each vehicle is aware of its neighbor vehicles, unsafe situation can be avoided. This type of packets is required to be broadcasted frequently enough in order to provide the most updated information. The Vehicle Safety Communications consortium (VSCC) suggests that the periodic messages should be broadcasted at a frequency of at least 10 messages per second. Example applications identified by VSCC include traffic signal violation warning, curve speed warning, emergency electronic brake lights, pre-crash warning, cooperative forward collision warning, left turn assistant, lanechange warning, and stop sign movement assistant [29]. The packet size basically ranges from 200 to 500 bytes [30]. For potential collision detection, vehicle information is unnecessary and the detection can be completed only by slot information. Therefore, there is typically no additional overhead for potential collision detection in PTMAC. On the other hand, vehicle information like speed, position and moving direction will be helpful for potential collision prediction. Once a potential collision is detected, such vehicle information will be requested and used for potential collision prediction. In this case, very small overhead is introduced for collision prediction in PTMAC since only the potential collided vehicle’s information will be transmitted upon the detected collision and request. More details will be discussed in the subsection of potential collision prediction. B. Potential Collision Detection We start from the first step of our PTMAC protocol: how to detect a potential encounter collision. Typically, two vehicles within their communication range (i.e. one-hop distance) using the same slot will cause a transmission collision. However, in a broadcast environment, a collision will happen if these two vehicles are within 2 times of their transmission range (i.e. two-hop distance) since a vehicle in between these two will not receive either broadcasting sent by these two vehicles. In order to detect a potential collision before it actually happens, we intend to identify any two vehicles using the same slot that are out of two-hop communication range from each other. That is, a vehicle needs to know the slot usage information of other vehicles that are beyond two-hop distance. The most naive solution is to require each vehicle to broadcast the information of its two-hop neighbors in addition

to its one-hop neighbors. The major drawback of this approach is that significant overheads will be introduced with longer packet length. Therefore, to avoid such additional overheads, we use “intermediate vehicles” to detect the potential collisions between vehicles currently out of two-hop range. Since each vehicle is able to obtain the information of its two-hop neighbors from its one-hop neighbors, the intermediate vehicles are able to get knowledge of its two-hop neighbors ahead and twohop neighbors behind. In this way, these intermediate vehicles can detect potential collisions between vehicles out of two-hop range but within three or four-hops range who are reserving the same slot. This is the most essential observation for our proposed protocol.

Fig. 2.

Potential Collision Detection for Same Direction

The process of potential collision detection can be described as: based on the message containing the frame information received from other vehicles (one-hop neighbors), every vehicle needs to check if any two of its one-hop or two-hop neighbors are occupying the same time slot. Every vehicle learns the information of its two-hop neighbors from its onehop neighbors. So a potential collision can be detected among two vehicles at most four-hop away. Actually, since each vehicle tries to avoid reserving the same slot with other vehicles within two-hop range, a potential collision can only be detected before it happens between two vehicles that are threehop or four-hop away. However, since two vehicles with fourhop potential collision are still far away from each other and will be safe for a period of time, we only need to concern the potential collisions detection for vehicles that are between two to three hops distance. For example, Figures 2 and 3 display the potential collisions that are detected among vehicles at the same direction and opposite directions respectively. In both cases, vehicles A and B are currently out of two-hop range but within three-hop range. They are occupying the same slots i but they cannot find this potential collision by themselves. Instead, the intermediate vehicles X and Y have the slot information about both A and B, so they are able to detect this potential collision between A and B.

Fig. 3.

Potential Collision Detection for Opposite Direction

Notice that if the traffic density is very low, intermediate vehicle may not exist between the two vehicles with a potential

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 5

collision. For example, in Figure 3, at least two intermediate vehicles X and Y are needed to inform each other the slot information of A and B. If there is only one or no intermediate vehicle, the potential collision cannot be detected. In this case, the PTMAC protocol performs similar to ADHOC MAC. Vehicles get encounter collision will re-contend for an available slot to transmit packet. Meanwhile, the packet collision will not become a problem in such sparse traffic condition.

C. Potential Collision Prediction When an intermediate vehicle detects a potential collision between two other vehicles, let’s say vehicle A and B, it needs to predict whether A and B will “encounter” each other and the potential collision will really happen. In this paper, the “encounter” means that two vehicles come into two-hop communication range of each other. This prediction can be done based on the vehicle information includes locations, the speeds and moving directions of these two potential collided vehicles (in term of transmission). Since every vehicle periodically broadcasts its vehicle information to meet the requirement of safety related applications, the intermediate vehicle has the vehicles information of one of the potential collided vehicles which is its one-hop neighbor. However, it has no knowledge about the other potential collided vehicle which is its two-hop neighbor. To obtain the vehicle information of the potential collided vehicle in two-hop distance, the intermediate vehicle needs to add a request to its broadcast message. Other intermediate vehicles that require the same information do not need to send duplicated requests. The vehicle (must also be an intermediate vehicle) that hears such request and is a one-hop neighbor of the requested potential collided vehicle will add the requested vehicle information into its broadcast message. Similarly, other vehicles receive the same request and find the required information has already been broadcasted can ignore this request. Once the requested vehicle information is received, the intermediate vehicle will begin the potential collision prediction. For example, in Figure 3, the intermediate vehicle X and Y have the slot information about both A and B. Thus, they can detect the potential collision between A and B. However, X only knows the vehicle information about A and needs Y to pass B’s information to finish the prediction. For a three-hop potential collision (two vehicles are between the two and three times communication range), assuming the communication range is 300m and vehicle speed is 30m/s (67Mph), even the two potential collided vehicles are running toward each other, it will take 5s (50 frames) before these two vehicles encounter each other. Therefore, there is plenty of time for an intermediate vehicle to request for and get the needed vehicle information. A potential collision that is predicted to happen is considered as “active”. We classify the potential encounter collisions into two types: potential collisions among vehicles running at the same direction and among vehicles driving at the opposite directions. Different methods will be used for these two types of potential collisions to predict if they are active or not.

1) Same Direction Potential Collision Prediction: For vehicles running along the same direction, they are likely to catch up with each other if the one behind has much faster speed. The distance between two vehicles may shorten to or less than two-hop communication range (2R) in a short duration of time from now due to their speed difference. Assuming vehicle A locates behind B and they are occupying the same slot, this potential collision is regarded as active if the distance between them can be reduced to 2R in a short duration of times, where R is the communication range of a vehicle. This is shown in Equation 1.  (if Vb < Va )  (Va − Vb ) × T ≥ D − 2R (1) Lb  T = min{K, } Vb Va and Vb are the speeds of vehicle A and B respectively. Lb is the length of the road that B has not finished and D is the current distance between A and B. T stands for a short duration time which is used to check if vehicle A and B can run into two-hop range of each other within this short duration T or not. It is unnecessary for a potentially collided vehicle to change its slot too early. If two potential collided vehicles will not encounter each other within time T, the potential collision can be removed later. K represents a short period of time that enables a potentially collided vehicle to change its slot with high success probability. It is still possible that a potentially collided vehicle can safely switch its slot to a new slot, but get a potential collision with another three-hop neighbor. If we set a larger K, the potentially collided vehicle will have multiple chances to switch its slot and higher probability of removing the collision can be achieved. On the other hand, if we set K to be too large, the original slot for the potentially collided vehicle will be open for competition and other vehicles may take over this slot. In this case, a new potential collision may appear right away and the whole process needs to be done again. Therefore, a smaller K can save resource and slot utilization. T equals to either K or the time before B leaves the road, depends on whichever is smaller. Since T is a really short period of time (for example, less than 1s), we regarded Va and Vb as constant within T and their variability is less important. If A is faster than B and Equation 1 is satisfied, this potential collision is considered as active and has to be eliminated. Otherwise, if Va is not larger than Vb or Equation 1 is not satisfied, this potential collision is currently harmless. 2) Opposite Direction Potential Collision Prediction: For vehicles running at opposite directions, potential collisions may be detected between vehicles that are running toward each other or farther away from each other. An example is shown in Figure 4. Vehicles A and B are reserving the same slot and driving toward each other. Thus, the potential collision detected by intermediate vehicle I1 and I2 will definitely happen in the future. On the other hand, if intermediate vehicle I1′ and I2′ detect a potential collision between vehicle A and B’, this collision can be ignored since A and B’ are running farther away from each other. We setup two conditions for intermediate vehicles to check if the potential collided vehicles are approaching or running farther away from each other:

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 6

1. The intermediate vehicle finds that one of the potential collided vehicles which is running at the same direction locates behind it. 2. Meanwhile, the other potentially collided vehicle which running at the opposite direction locates ahead of it. If both conditions are satisfied, the intermediate vehicle knows that the two potential collides vehicles are approaching each other. Otherwise, this potential collision can be ignored. Assuming the DSRC communication range is 300m and vehicle speeds are 30m/s (67Mph) on highway, for a three-hop potential collision, the time to shorten the distance between two potential collided vehicles to two-hop range is about 5s. Therefore, there is plenty of time for a potentially collided vehicle to change its slot since every vehicle needs to broadcast its information at least every 100ms. Similar to the same direction collision, only if the distance between A and B can be reduced to 2R in a short duration of time T, the potential collision is active. This is shown in Equation 2. (Va + Vb ) × T ≥ D − 2R

(2)

Where T equals to the K in Equation 1. When an intermediate vehicle finds that two potential collided vehicles are approaching each other and Equation 2 is satisfied, it regards this potential collision as active.

Fig. 4.

intermediate vehicle to broadcast a notification about this potential collision. Meanwhile, the potentially collided vehicle within one-hop of this responsible intermediate vehicle is selected as the switching vehicle. In this way, the responsible intermediate vehicle can directly inform the switching vehicle without further forwarding. Notice here that the intermediate vehicles detect the same potential collision must be in the communication range of each other. Thus they are able to receive the notification about the potential collision from each other. A one bit flag will be added into the broadcasted Frame Information (FI) of the responsible intermediate to indicate that a slot has an active potential collision. Assuming slot i is currently occupied by the switching vehicle A, the responsible intermediate vehicle will broadcast its FI with an active flag on slot i. Therefore, when vehicle A receives the FI from the intermediate vehicle, it finds its slot will conflict with another vehicle and can conclude that it has to change its slot. Other intermediate vehicles found the same active potential collision can just broadcast their FIs without adding an active flag on the same slot. After the switching vehicle changes to a new slot, it will update its FI and transmit using its new slot. Vehicles that received such updated FI from A will update their frame information. We can also allow a switching vehicle to use its original slot one more time to preannounce which slot it will switch to. In this way, other vehicles received such messages can avoid selecting the same slot. The contention collisions among multiple switching vehicles from different potential collisions and newly joining vehicles can be prevented.

Potential Collision Prediction in Opposite Directions (a) Before Potential Collisions Elimination

D. Potential Collision Elimination If an active potential collision is found, we need to prevent this collision to happen in the near future. One of the potential collided vehicles needs to give up its current reserved slot and switch to another available slot. Since there may be multiple intermediate vehicles detect the same potential collision, we need to select one of them to handle this potential collision. Then the selected intermediate vehicle has the responsibility to decide which one is the “switching vehicle” to release its current reserved time slot. Finally, the switching vehicle needs to switch to another empty slot after receiving a switching notification from the responsible intermediate vehicle. Recall that we only focus on the potential collisions detected between vehicles three-hop away. The basic rule is selecting the potentially collided vehicle which is a one-hop neighbor of the responsible intermediate vehicle as the switching vehicle. There may be more than one intermediate vehicle that can detect the same potential collision. When an intermediate vehicle finds an active potential collision, it first listens to the channel until its own reserved slot comes. If it has not received any notification from others about this active potential collision, it becomes the responsible

Fig. 5.

(b) After Potential Collision Elimination Potential Collision Elimination

We take Figure 4 as an example and the original slot arrangement is shown as Figure 5(a). Vehicle A and B are occupying the same slot 3. This potential collision will be detected by both the intermediate vehicle I1 and I2 . Since I1 has not received a notification about the detected potential collision, it will become the responsible intermediate vehicle who needs to broadcast a notification about this potential collision. As I1 ’s one-hop neighbor, vehicle A will be selected as the “switching vehicle”. Meanwhile, since the slot of vehicle I2 is behind the slot of I1 , I2 is able to hear the switch notification from I1 and does not need to broadcast a duplicated notification. As shown in Figure 5(b), when vehicle A receives the notification, it will randomly switch to another available slot. After A switches to a new slot, all its neighbors will update their Frame Information about A. Therefore, the potential collision between vehicle A and B can be eliminated before it really happens.

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 7

IV. PTMAC PROTOCOL FOR FOUR-WAY TRAFFIC A. More Assumptions and Traffic Model After explaining our PTMAC under two-way traffic scenario, we extend it into a four-way intersection scenario. Vehicles can drive at four possible directions: North, South, West and East. We consider a Traffic Light Model in which the intersection has traffic light for controlling the traffic from all four directions. Vehicles can go straight, turn right, turn left or make a U-turn at a four-way intersection. More assumptions besides what we mentioned in Section 3 are made for fourway traffic: 1. Each vehicle periodically broadcasts their turning direction at the coming intersection before passing the intersection. This information can come from the turning left/right signal or from GPS device base on a predetermined route. 2. The location of an intersection and the phases of its traffic lights are provided by RSU broadcasting. The PTMAC protocol still processes with the three steps for four-way intersection scenario. The steps of Potential Collision Detection and Potential Collision Elimination are similar to what we described in the two-way traffic scenario. We will focus on explaining the most different part: Potential Collision Prediction under four-way scenario. Similar to the two-way scenario, the intermediate will first request for the information about the potential collided vehicle that is two-hop away and then begin the prediction. We further separate the Potential Collision Prediction into two parts: road segment prediction and intersection prediction. The road segment prediction concerns the collisions between vehicles running on the same road segment, either heading the same direction or the opposite directions. The intersection prediction pays attention to the potential collisions among vehicles driving on different road segments while approaching to or leaving the intersection. Since the road segment prediction is the same as what we has explained in two-way traffic scenario, we concentrate on describing the intersection prediction which is used to check whether two vehicles are currently out of two-hop range and reserving the same slot will encounter each other or not. B. Potential Collision Prediction at An Intersection We take an example of four-way intersection scenario as shown in Figure 6 to explain our PTMAC protocol. Vehicles A and B are occupying the same slot i and are currently threehop away from each other. After the intermediate vehicle X and Y detected this potential collision, they need to predict whether this collision is active or not. We consider the potential collision prediction in three possible cases based on the current locations of two potentially collided vehicles A and B. The first case is that both A and B have passed the intersection. The second case is that one of them has passed the intersection while the other one has not. The third case is that none of them have passed the intersection. In the first case, both A and B already passed the intersection and are driving away from the intersection. If A and B have turned to different directions, they are running farther away from each other and no collision will happen. If A and B have turned to the same direction, the prediction problem becomes

Fig. 6.

Potential Collision in a Four-way Intersection

TABLE I.

I NTERSECTION C OLLISION P REDICTION WITH D IFFERENT P OSITIONS OF V EHICLE A AND B

A passed √ √

B passed √

×

×

×

Action of Intermediate Vehicle N/A Check if potential collision is active before B passes the intersection Check if potential collision is active before one of A and B passes the intersection

the road segment prediction. The second possible case is that A has already passed the intersection, but B has not. B will turn to the same or different direction as A’s. If B did not encounter A before it passes the intersection and turns to the same direction as A, the problem will become road segment prediction again. On the other hand, if B did not encounter A before it passes the intersection and turns to a different direction as A, their distance will become larger and they have no more chance to encounter each other. Thus, we only need to check whether the potential collision is active before B passes the intersection. We also consider the third case that neither A nor B has passed the intersection. The distance between these two vehicles will be shortened before one of them passes the intersection. Assuming A passes the intersection first, if A turns to the opposite direction of B’s current driving direction of the same road segment, then the problem becomes road segment prediction. If A turns to other directions, then the problem becomes similar to the second case. Thus, for this case, we only need to check whether the potential collision is active or not before one of A and B passes the intersection. We summarize all the cases in Table I. In order to check whether two vehicles can encounter each other before passing the intersection, we first need to compute when they will pass the intersection. Based on a travel time estimation model proposed in [32], we develop an improved model to estimate the travel time that a vehicle needs before it passes the intersection. We provide more accurate estimation with the help of VANET communication and real-time information. The total travel time Tt from vehicle’s current position to the intersection is separated into two components: signal delay time Ts and cruise time Tc . Vehicles’ behaviors are complicated when they approaching to the intersection and they are greatly influenced by the traffic lights, especially

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 8

when they need to wait for a red signal. In this paper, we use the simplified Webster formula which is the widely used model to estimate the signal delay. It is computed based on the traffic light phases, traffic volume (vehicles/sec) and degree of saturation. The degree of saturation is the traffic volume to capacity ratio. The capacity is the maximum rate at which vehicles can pass through a point in a period of time. Both the capacity and the traffic volume can either be estimated by an individual vehicle or from RSU broadcasting. Knowing the current locations and speeds of all its two-hop neighbors, an intermediate vehicle can compute the number of vehicles passing a point in a period of time and then get the traffic volume. Actually, this information is also widely used in many traffic control applications like intelligent traffic light [33]. Each vehicle also receives the red and green light phases information at an intersection from RSU broadcasting. Therefore the signal delay can be calculated by the intermediate vehicle. On the other hand, we modify the model in [32] by computing the cruise time based on real-time traffic information from vehicles periodically broadcasting information instead of using loop detector. The cruise time will be the time cost from a vehicle’s current location to the end of the queue at an intersection. Since every vehicle has its two-hop neighbor’s location and speed information, one simple way to estimate the queue length is counting the number of vehicles whose speeds are 0. Therefore, an intermediate vehicle is also able to compute the cruise time of two potentially collided vehicles. Actually, the way we compute cruise time is more accurate than that in [32], since they considered the cruise time is from a vehicle’s current location to a fix point (loop detector) regardless of the current queue length. We set Ta and Tb as the total travel times needed for A and B to pass the intersection respectively. La and Lb stand for the current distance from A and B to the intersection respectively. Va and Vb are the speeds of vehicles A and B. We regard Va and Vb as constant in a short period of time. Tac and Tbc are the cruise times of vehicles A and B while Taq and Tbq are the waiting times of vehicles A and B respectively. If they do not need to wait for the signal, the cruise time will be exact the total travel time. For the second case that A already passed the intersection, if Va < Vb , then we directly check if Equation 3 or 4 is satisfied or not. K is the short duration of time that we set for switching vehicle to change slot. If K < Tb , Equation 3 is used. If K ≥ Tb , then Equation 4 will be checked. In Equation 3, the first sub-equation checks two vehicles that are running at different directions and different road segments. The second sub-equation is used for two vehicles running at the same direction but different road segments. Similarly, in Equation 4, Y and Y’ are used for two vehicles that are running at different directions and the same direction on different road segments respectively. The shortest distance between A and B may appear at two points: when B reaches the waiting queue and when B is passing the intersection. Therefore, we check both points. X in Equation 4 estimates the distance between A and B when B reaches the waiting queue. Y or Y’ stands for the distance between A and B when B is passing the intersection. If Equation 3 or 4 can be satisfied, the potential collision is considered as active.

√   (La + Va × T )2 + (Lb − Vb × T )2 ≤ 2R (La + Lb ) + (Va − Vb ) × T ≤ 2R   T = min{K, Tbc }         

Y =



(3)

X = La + Va × Tb (La + Va × Tbc )2 + (Lb − Vb × Tbc )2 Y ′ = (La + Lb ) + (Va − Vb ) × Tbc min{X, Y (Y ′ )} ≤ 2R

(4)

For the third case, assuming Tb > Ta , that is, vehicle A will pass the intersection first, Equation 5 or 6 will be used to check if the distance between A and B can reduce to 2R or smaller before A passes through the intersection. If K < Ta , then Equation 5 is used while Equation 6 will be checked when K ≥ Ta . In Equation 5, the first sub-equation checks two vehicles that are running at different directions and different road segments. The second sub-equation is used for two vehicles running at the same direction but different road segments. Equation 6 checks the distance between A and B when A is passing the intersection. If Equation 5 or 6 is satisfied, this potential collision is active. Otherwise, we need to check whether the distance between A and B can be reduced to 2R or smaller before B passes the intersection using Equation 3 or 4. This becomes the same situation as the second case. √  (La − Va × T1 )2 + (Lb − Vb × T2 )2 } ≤ 2R    (La − Va × T1 ) + (Lb − Vb × T2 ) ≤ 2R  T1 = min{K, Tac }    T2 = min{K, Tbc } { Lb − Vb × T ≤ 2R T = min{Ta , Tbc }

(5)

(6)

V. P ERFORMANCE A NALYSIS A. Probability of Contention Collisions As a reminder, there are two types of collisions: contention collision and encounter collision. We first investigate the contention collisions probability of the three MAC protocols. N denotes the totally number of slots in each frame. NE and NR stand for the number of empty slots and reserved slots respectively. M is defined as the number of new joining vehicles within two-hop communication range. They currently do not occupy slots but are trying to compete for slots. Here we only consider the case that M is larger than 1. Otherwise, no contention collision will happen. For the basic ADHOC MAC protocol, if NE is greater than 1, the probability that a vehicle among these M competitors can reserve a slot successfully is computed as Equation 7. If the NE is less or equal to 1, the contention collision will definitely happen and no one can make a reservation successfully. PS = (1 −

1 M −1 ) NE

(7)

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 9

If the number of current empty slots is equal to or larger than the number of competitors, that is, NE ≥ M , then the probability that all these M vehicles can successfully gain a slot is computed as Equation 8. Since PTMAC does not use slot partition method, the way of computing the contention collision probability for PTMAC is similar to ADHOC MAC. ∏M −1 PALLS =

(NE − i) NE M

i=0

(8)

For Even-Odd MAC protocol, the total number of available slots is halved for each direction. Assuming the traffic densities are totally balanced for both directions, there will be N2E empty slots left for each direction. The contention collision can be analyzed in two cases. In the first case, if there are M number of competing vehicles from the same direction and N2E is greater than 1, the probability that one of them can reserve a slot successfully is computed as Equation 9. PS = (1 −

2 M −1 ) NE

(9)

Then if N2E ≥ M , the probability that all these M vehicles gain a slot successfully is computed as Equation 10. ∏M −1 PALLS =

i=0

( N2E − i)

( N2E )M

(10)

In another case, if there are totally M competing vehicles within two-hop communication range, half of them are running to the left while half of them are driving to the right, the probability that one of them can reserve a slot successfully is computed as Equation 11. And if NE ≥ M , the probability of all these M vehicles gaining slots successfully in this case will be computed as Equation 12. PS′ = (1 −

′ PALLS

2 M −1 )2 NE

∏ M2 −1 =(

i=0

( N2E − i) M

( N2E ) 2

(11)

)2

(12)

Therefore, we can see that when using Even-Odd MAC, more contention collisions are introduced in the first case while smaller contention collision probability is achieved in the second case. However, since more contentions are happen between newly joining vehicles and they are heading the same direction, the first case happens more frequently. The second case is more suitable for the collisions that happen between new joining vehicles and re-competing vehicles or among recompeting vehicles. For all the three MAC protocols, the contention collisions are not only caused by the newly joining vehicles, but also from the vehicles who have suffered encounter collisions and have to re-compete for new slots. Therefore, reducing the number of encounter collisions is also helpful for decreasing the number of contention collisions.

B. Probability of Encounter Collisions An encounter collision is caused by two vehicles that are currently reserving the same slot and out of two-hop range, but will encounter each other in the near future. Assuming there are two newly joining vehicles A and B and they are trying to reserve their slots. If we know that they will encounter in the future (for example, driving at opposite directions and approaching each other), the probability that A and B will select the same slot (an encounter collision will happen) is computed as Equation 13. PEC =

NE (A ∩ B) NE (A) × NE (B)

(13)

Notice here that vehicle A and B have different neighbors and slots allocations. NE (A) and NE (B) stand for the numbers of empty slots from the view of A and B respectively. NE (A ∩ B) expresses the number of empty slots from both A and B’s views. Notice here that for Even-Odd MAC protocol, there is no encounter collision happens between vehicles running at opposite directions. But it cannot avoid the encounter collisions from the same direction. Actually, since the number of available slots is halved in Even-Odd protocol, the probability of the encounter collision from vehicles at the same direction is increased. C. Probability of Removing Potential Collisions In our proposed PTMAC protocol, it is likely that a detected potential collision cannot be successfully removed under heavy traffic density. One possible situation is that there is no other empty slot for the switching vehicle to switch to. Another possible situation is that the switching vehicle switches its slot to a new slot, but this new slot incurs a new potential collision with another vehicle. So under a dense traffic density, this vehicle may have to keep on changing its slot until it finds a slot without potential conflict with others or the collision really happens. Assuming a vehicle A is detected having a potential collision with vehicle B, the probability that this potential collision can be removed at the next frame is expressed as Equation 14. Here NE (A) is the number of empty slots and A(E) expresses the empty slots from A’s view. A(3) stands for the three-hop neighbors of A and they will encounter A within T (a short duration). We call those neighbors as threehop encounter neighbors. So N (A(E) ∩ A(3)) expresses the number of slots which are empty from A’s point of view and meanwhile are occupied by A’s three-hop encounter neighbors. PRM 1 = 1 −

N (A(E) ∩ A(3)) NE (A)

(NE (A) > 0)

(14)

As long as the potential collision has not really happened, vehicle A still has chance to switch to elsewhere. If A has NSW number of chances to change its slot, the probability that vehicle A can eventually remove the potential collision is computed as Equation 15. Therefore, we can see that with higher traffic density, a vehicle may need to switch it slot multiple times in order to avoid the encounter collision. This

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 10

is also the reason that T should not be too small. Otherwise, A only has one or two chances to switch it slot, which may cause failed collision elimination especially under heavy traffic density scenario. PRM = 1 −

N∏ SW i=0

N (A(E) ∩ A(3)) − i NE (A) − i

(NE (A) > i) (15)

VI. S IMULATION AND P ERFORMANCE E VALUATION In this section, we evaluate the performance of our proposed PTMAC protocol. We use MATLAB and SUMO to construct a simulation environment where both two-way and four-way traffic scenarios are considered. SUMO is a traffic simulator to generate real world mobility models including road map, traffic light information and vehicle’s moving pattern. Vehicles’ speeds are adjusted based on the traffic condition and traffic light information when they are approaching an intersection. A mobility trace file which contains the position of each vehicle at any time is generated by SUMO and input to MATLAB. MATLAB is used for building a VANET communication environment and implementing the MAC protocols. We compare our PTMAC with ADHOC MAC [12] and Even-Odd TDMA protocol [17]. TABLE II.

S IMULATION PARAMETERS S ETTING

Parameter Highway Road Length Urban Road Length before Traffic Light Vehicle Max Speed Green Light Phase Number of Lanes (each direction) Traffic Density (number of vehicles per direction) Communication Range Per Frame Length Data Rage Packet Size Simulation Time

Highway 2000m N/A 25-32m/s N/A 4 200, 400, 600 300m 0.1s 6Mbps 400 Bytes 600s

Intersection N/A 1500m 20-25m/s 42s 3 150, 175, 200 300m 0.1s 6Mbps 400 Bytes 600s

The first simulation scenario is a highway with two-way traffic. Vehicles are running at different speeds within different maximum speeds. A vehicle can catch up with and pass over other vehicles if its speed is faster. We measure the performances using different traffic densities. In total 200, 400 and 600 vehicles are generated for each direction during 600s simulation time. We also investigate the impact of unbalanced traffic densities for different directions on these three MAC protocols. The second simulation scenario is an intersection with four-way traffic. There are three lanes for each direction. The right lane is for vehicles turning right, the middle lane is for vehicles go straight while the left lane is used for vehicles turning left or making a U-turn. The number of vehicles that has been generated for each direction is varied from 150 to 200 vehicles within 600s simulation time. For both scenarios, the packet size is assumed as 400 Byte and the data rate is 6 Mbps. To ensure the driving safety, the 3-second rule is generally used which suggests that a vehicle should stay 3 seconds behind the vehicle in front of it. For highway scenario, we consider two-way traffic and each direction with 4 lanes.

Assuming the average vehicle speed is 30 meters per second (67 mph), the distance between the two vehicles should be 90m. Assuming the average vehicle length is 4m, one vehicle will have maximum 48 neighbor vehicles in its communication range (6 vehicles for each lane). For urban area, the average vehicle speed is assumed as 20 meters per second (45mph) and the distance between the two vehicles should be 60m. If there are 3 lanes for each direction, maximum 54 vehicles will be in the communication range (9 vehicles for each lane). Considering the aggressive driving and stops at the intersection, we vary the number of slots in a frame from 64 to 88 and investigate its impact on the performance. The detailed simulation parameters are summarized in Table II. To focus on the packet collisions, the simulation runs using an ideal physical channel, that is, the packet will be successfully transmitted within the communication range if there is no packet collision. A. Two-way Simulation Results We first evaluate the performance of these three MAC protocols under two-way traffic with balanced traffic densities. We focus on two metrics: packet delivery rate and total number of collisions. Figure 7 shows the results of number of packet collisions and packet delivery rate with 200 vehicles generated for each direction. In Figure 7(a), every bar is separated into two parts by a black line. The part below the line stands for the number of encounter collisions while the part above the line is the number of contention collisions. From the results we can see that with the increment of the number of slots, all of the three MAC protocols get better performance since more available slots decreases the collision probability. With 64 slots per frame, PTMAC works better than ADHOC MAC and EvenOdd with 92.7% and 50% fewer collisions respectively. This is because that PTMAC not only eliminates the collisions among vehicles from opposite directions, but also avoids the collisions from the same direction. The delivery rate of PTMAC also improves by 2.6% and 0.5% comparing to ADHOC MAC and Even-Odd respectively. PTMAC also has fewer contention collisions. The number of contention collisions is affected by the number of encounter collisions since the collided vehicles have to re-compete for slots. Therefore, reducing the number of encounter collisions is also helpful for decreasing the number of contention collisions. Since the traffic density is pretty low in this case, the problem of packet collision is not severe. Then we increase the traffic density by generating 400 vehicles for each direction. Results about the number of collisions and packet delivery rate are shown in Figure 8. With 64 slots per frame, PTMAC has 90.6% and 29.7% fewer collisions than ADHOC MAC and Even-Odd respectively. The packet delivery rate of PTMAC improves about 5.8% and 0.4% comparing to the ADHOC MAC and Even-Odd respectively. We continue increasing the traffic density to 600 vehicles for each direction and Figure 9 shows the results. The number of contention collisions of Even-Odd protocol is sharply increased in this case. Basically, Even-Odd scheme has no great impact on the number of contention collisions among vehicles driving at different directions since both the number

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 11

contention collisions comparing with the Even-Odd.

Number of Collisions: 200 vehicles for each direction 300 ADHOC MAC Even−Odd MAC PTMAC

Number of Collisions: 400 vehicles for each direction

250 1800

ADHOC MAC Even−Odd MAC 1600

PTMAC

1400 150 1200

Number of Collisions

Number of Collisions

200

100

50

1000

800

600

400 0

64

72

80

88

Total Number of Slots 200

(a) Number of Collisions 0

64

Packet Delivery Rate: 200 vehicles for each direction

72

80

88

Total Number of Slots

100

(a) Number of Collisions Packet Delivery Rate: 400 vehicles for each direction

99.5

100

99

98

98.5

Packet Delivery Rate

Packet Delivery Rate

99

98

97.5

97

96

ADHOC MAC 95

Even−Odd MAC PTMAC 97

65

70

75

80

85 94

Total Number of Slots

ADHOC MAC Even−Odd MAC

(b) Packet Delivery Rate Fig. 7.

PTMAC 93

Performance with 200 Vehicles Each Direction on Highway

65

70

75

80

85

Total Number of Slots

(b) Packet Delivery Rate Fig. 8.

of available slots and the number of competing vehicles has been halved. However, if a contention happens among vehicles at the same direction (among newly joining vehicles and recompeting vehicles), higher probability of contention collision may occur since only half of the slots are available. Higher traffic density means more newly joining vehicles are generated and more encounter collisions happen among vehicles along the same direction. Thus, more contention collisions are introduced for Even-Odd scheme. On the other hand, PTMAC has a little bit more encounter collisions than Even-Odd MAC protocol with 64 and 72 numbers of slots in a frame. This is because the total number of available slots is not enough. Even if a potential collision has been identified, there is no other available slot to change to. Besides, it is likely that a switching vehicle switches to another slot but collides with another vehicle. However, even with 64 slots per frame under this dense traffic, the proposed PTMAC still has better overall performance with 9.2% and 3.4% higher delivery rate than ADHOC MAC and Even-Odd respectively. When we increase the number of slots in a frame to 80 and 88 (i.e. enough number of slots is provided for vehicles to switch to when eliminating the potential collisions), PTMAC has fewer encounter and

Performance with 400 Vehicles Each Direction on Highway

Additionally, we study the influence of unbalanced traffic densities on these three MAC protocols. Here we define a new parameter called Traffic Balance Rate (TBR). It is computed as the ratio of the number of vehicles in the direction with sparser traffic to the number of vehicles in the direction with denser traffic. Therefore TBR equals to 1 when exactly the same number of vehicles are generated for each direction during the simulation. A small TBR means a scenario with severe unbalanced traffic densities. We fix the total number of vehicles that are generated through the simulation as 800 and measure the packet delivery rates using different TBRs. Figure 10(a), (b), (c) and (d) represent the packet delivery rates with 64, 72, 80 and 88 numbers of slots in a frame respectively. The performances of ADHOC MAC and PTMAC are not greatly impacted and degraded by the unbalanced traffic densities since these two protocols do not use slot partition method. On the other hand, Even-Odd protocol shows its sensitivity to a small TBR with low packet delivery rate, especially for smaller number of slots in a frame. With 64 slots in a frame, the performance of Even-Odd is worse than the ADHOC MAC when TBR is set as 1/7 or 1/3. Thus, vehicles in the direction

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 12

Number of Collisions: 600 vehicles for each direction 6000 ADHOC MAC Even−Odd MAC PTMAC 5000

Number of Collisions

4000

3000

2000

numbers of slots in a frame and traffic densities. Four MAC protocols are compared for four-way traffic. For Even-Odd MAC protocol, we regulate that vehicles moving to the East and North can only use even slots while vehicles heading West and South can only reserve odd slots. Besides, we measure another MAC protocol called Four-Part MAC. In Four-Part MAC, all the slots in each frame is evenly partitioned into four disjointed parts: one part for each direction. Therefore, there will be no interference between vehicles running to the different directions. Number of Collisions: 150 vehicles for each direction

1000

5000 ADHOC MAC Even−Odd MAC

4500

Four−Part MAC

0

64

72

80

88

PTMAC

Total Number of Slots

4000

(a) Number of Collisions 3500

Number of Collisions

Packet Delivery Rate: 600 vehicles for each direction 100

3000

2500

2000

1500

Packet Delivery Rate

95

1000

500

0

64

90

72

80

88

Total Number of Slots

(a) Number of Collisions Packet Delivery Rate: 150 vehicles for each direction

ADHOC MAC

100

Even−Odd MAC PTMAC 85

65

70

75

80

85

Total Number of Slots

(b) Packet Delivery Rate Packet Delivery Rate

95

Fig. 9.

Performance with 600 Vehicles Each Direction on Highway

with heavier density will suffer high probability of contention collision, even there are many empty slots left in another direction. With 64 slots and 1/7 TBR, PTMAC has higher delivery rate of 6.4% and 12.5% comparing to ADHOC MAC and Even-Odd respectively. In addition, for Even-Odd, if a vehicle finds that all the slots assigned for its direction have been occupied, it will not have a chance to access the channel even if there are still empty slots left for the other direction. It cannot begin the slot contention until someone in its direction release the slots. In this case, the slots of the sparse traffic density side will be wasted and contentions will be considered as failed. These failed contentions are unnecessary and can be fully prevented if the number of available slots can be well adapted. Both PTMAC and ADHOC MAC do not suffer such unnecessary failures since vehicles freely select any available slots for channel contention. B. Four-way Simulation Results We also evaluate the performances of the MAC protocols under four-way intersection scenario. Similar to the twoway scenario, we measure their performances using different

90

ADHOC MAC Even−Odd MAC Four−Part MAC PTMAC 85

65

70

75

80

85

Total Number of Slots

(b) Packet Delivery Rate Fig. 11.

Performance with 150 Vehicles Each Direction at Intersection

Figures 11, 12 and 13 represent the results under different traffic densities. From the simulation results we can see that PTMAC works the best with the least number of collisions and highest delivery rate. Since ADHOC MAC allows a vehicle to contend for any empty slot without considering vehicles’ mobility nature, it is only suitable for one-way traffic and its performance is severely impacted by the huge number of encounter collisions under such four-way intersection scenario. Meanwhile, both Even-Odd and Four-Part MACs do not have obvious improvement for this four-way intersection scenario. They even perform worse when traffic density becomes heavier. More encounter collisions happen among vehicles at the

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 13

Packet Delivery Rate: 64 Slots

Packet Delivery Rate: 72 Slots

100

100

99

98

97

Packet Delivery Rate

Packet Delivery Rate

95

90

96

95

94

93

92 ADHOC MAC

ADHOC MAC 91

Even−Odd MAC

Even−Odd MAC

PTMAC 85

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

PTMAC 90

1

0.2

0.3

0.4

Traffic Balance Rate

0.6

0.7

0.8

Packet Delivery Rate: 88 Slots 100

99

99.5

98

99

97

98.5

Packet Delivery Rate

100

96

95

94

93

98

97.5

97

96.5

92

96 ADHOC MAC

91

ADHOC MAC 95.5

Even−Odd MAC

Even−Odd MAC

PTMAC 0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

PTMAC 1

Traffic Balance Rate

Fig. 10.

1

(b) 72 Slots Per Frame

Packet Delivery Rate: 80 Slots

90

0.9

Traffic Balance Rate

(a) 64 Slots Per Frame

Packet Delivery Rate

0.5

(c) 80 Slots Per Frame Packet Delivery Rate with 800 Vehicles and Different TBRs

same direction in this four-way intersection since a vehicle ahead may need to stop and wait for the red signal so it is easy to be caught up by other vehicles behind. Such collisions cannot be handled by Even-Odd and Four-Part. Besides, EvenOdd MAC cannot avoid the contention collisions that happen near the intersection between vehicles using the same set of slots (like vehicles heading North and East that both use the even slots). For the Four-Part MAC, although no contention collision will happen between vehicles that originally driving at different directions, vehicles may change their directions at the intersection. Furthermore, the quartered number of available slots not only increases the probability of contention collisions but also causes more encounter collisions between vehicles running at the same direction. Contrasting with ADHOC MAC, Even-Odd and Four-Part protocols, PTMAC performs better with 48.1%, 44.7% and 47.9% fewer collisions respectively when we set 64 slots in a frame and 150 vehicles for each direction. In the same environment, the packet delivery rate of PTMAC improves about 8.6%, 7.4% and 8.5% comparing to ADHOC MAC, Even-Odd and Four-Part protocols respectively. When we increase the traffic density to 175 vehicles for each direction, PTMAC has 10.9%, 10.7% and 10.8% higher delivery rate

95

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Traffic Balance Rate

(d) 88 Slots Per Frame

comparing with ADHOC MAC, Even-Odd and Four-Part. For heavier traffic density with 200 vehicles for each direction, the efficiency of PTMAC is weakened with smaller number of slots in each frame since the number of slots is not enough. But it still has 5.5%, 10.5% and 8.8% higher delivery rate than that of ADHOC, Even-Odd and Four-Part respectively for 64 slots per frame.

VII.

C ONCLUSION

In this paper, we propose a new Prediction-based TDMA MAC protocol (PTMAC) for decreasing the number of packet collisions, especially for encounter collisions. Potential collisions among vehicles who are currently out of two-hop communication range can be detected by intermediate vehicles, predicted and then eliminated before they really occur. Our simulations show the effectiveness of the proposed protocol. Since no slot partition is used, unbalanced traffic densities will not degrade the performance of PTMAC. Unlike a few existing MAC protocols that only work for one-way or twoway traffic scenarios, PTMAC is also suitable for handling four-way traffic.

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 14

Number of Collisions: 175 vehicles for each direction

Number of Collisions: 200 vehicles for each direction

4

14000

3

x 10

ADHOC MAC

ADHOC MAC

Even−Odd MAC

Even−Odd MAC

Four−Part MAC 12000

Four−Part MAC

PTMAC

PTMAC

2.5

10000

Number of Collisions

Number of Collisions

2

8000

6000

1.5

1 4000

0.5 2000

0

0

64

72

80

64

88

72

80

88

Total Number of Slots

Total Number of Slots

(a) Number of Collisions

(a) Number of Collisions

Packet Delivery Rate: 175 vehicles for each direction

Packet Delivery Rate: 200 vehicles for each direction

100

100

95 95 90

85

Packet Delivery Rate

Packet Delivery Rate

90

85

80

80

75

70

65 75

70

ADHOC MAC

ADHOC MAC Even−Odd MAC Four−Part MAC PTMAC 65

70

75

80

VIII.

ACKNOWLEDGEMENT

65

70

75

80

85

Total Number of Slots

(b) Packet Delivery Rate Performance with 175 Vehicles Each Direction at Intersection

Four−Part MAC PTMAC

55

85

Total Number of Slots

Fig. 12.

Even−Odd MAC

60

(b) Packet Delivery Rate Fig. 13.

Performance with 200 Vehicles Each Direction at Intersection

This work was partially supported by NSF awards CNS1217572 and CNS-1205640.

[6] Ieee standard for wireless access in vehicular environments (wave)– networking services corrigendum 1: Miscellaneous corrections. IEEE Std 1609.3-2010/Cor 1-2012 (Corrigendum to IEEE Std 1609.3-2010), pages 1–19, July 2012.

R EFERENCES

[7] C. Campolo, A. Vinel, A. Molinaro, and Y. Koucheryavy. Modeling broadcasting in ieee 802.11p/wave vehicular networks. IEEE Communications Letters, 15(2):199–201, February 2011.

[1]

[2]

[3]

[4]

[5]

802.11-2012. Ieee standard for information technologytelecommunications and information exchange between systems local and metropolitan area networksspecific requirements part 11: Wireless lan medium access control (mac) and physical layer (phy) specifications. 2012. T.V. Nguyen, F. Baccelli, Kai Zhu, S. Subramanian, and Xinzhou Wu. A performance analysis of csma based broadcast protocol in vanets. In 2013 Proceedings IEEE INFOCOM, pages 2805–2813, April 2013. Quincy Tse, Weisheng Si, and J. Taheri. Estimating contention of ieee 802.11 broadcasts based on inter-frame idle slots. In 2013 IEEE 38th Conference on Local Computer Networks Workshops (LCN Workshops), pages 120–127, Oct 2013. K. Bilstrup, E. Uhlemann, E.G. Strom, and U. Bilstrup. Evaluation of the ieee 802.11p mac method for vehicle-to-vehicle communication. In IEEE Vehicular Technology Conference (VTC 2008-Fall), pages 1–5, Sept 2008. Zhe Wang and Mahbub Hassan. How much of dsrc is available for non-safety use? In Proceedings of the ACM International Workshop on VehiculAr Inter-NETworking (VANET 2008), pages 23–29, 2008.

[8] C. Campolo, A. Molinaro, and A. Vinel. Understanding the performance of short-lived control broadcast packets in 802.11p/wave vehicular networks. In 2011 IEEE Vehicular Networking Conference (VNC), pages 102–108, Nov 2011. [9] National Highway Traffic Safety Administration (NHTSA). Technical report. [10] M.I. Hassan, H.L. Vu, and T. Sakurai. Performance analysis of the ieee 802.11 mac protocol for dsrc safety applications. Vehicular Technology, IEEE Transactions on, 60:3882–3896, Oct 2011. [11] Flaminio Borgonovo, Antonio Capone, Matteo Cesana, and Luigi Fratta. Rr-aloha, a reliable r-aloha broadcast channel for ad-hoc inter-vehicle communication networks. In Proceedings of Med-Hoc-Net 2002, 2002. [12] Flaminio Borgonovo, Antonio Capone, Matteo Cesana, and Luigi Fratta. Adhoc mac: New mac architecture for ad hoc networks providing efficient and reliable point-to-point and broadcast services. Wireless Networks, 10:359–366, 2004. [13] A. Ahizoune, A. Hafid, and R. Ben Ali. A contention-free broadcast protocol for periodic safety messages in vehicular ad-hoc networks. In

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2016.2519442, IEEE Transactions on Vehicular Technology 15

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29] [30]

[31] [32]

[33]

IEEE 35th Conference on Local Computer Networks (LCN), pages 48– 55, 2010. S. Sharafkandi and H.C.D. David. A new mac layer protocol for safety communication in dense vehicular networks. In IEEE 35th Conference on Local Computer Networks (LCN), pages 637–644, 2010. M.S. Almalag, S. Olariu, and M.C. Weigle. Tdma cluster-based mac for vanets (tc-mac). In 2012 IEEE International Symposium on World of Wireless, Mobile and Multimedia Networks (WoWMoM),, pages 1–6, June 2012. Rongqing Zhang, Xiang Cheng, Liuqing Yang, Xia Shen, and Bingli Jiao. A novel centralized tdma-based scheduling protocol for vehicular networks. IEEE Transactions on Intelligent Transportation Systems, 16(1):411–416, 2015. Xuejun Zhuo, Sha Hua, Limin Miao, and Yiqi Dai. Direction matters: A decentralized direction-based tdma scheduling strategy for vanet. In IEEE 13th International Conference on Communication Technology (ICCT),, pages 566–571, Sept 2011. H.A. Omar, Weihua Zhuang, and Li Li. Vemac: A tdma-based mac protocol for reliable broadcast in vanets. IEEE Transactions on Mobile Computing, 12(9):1724–1736, Sept 2013. Michael McGurrin. Vehicle information exchange needs for mobility applications version 3.0. Technical Report FHWA-JPO-13-065, April 2013. J.J. Blum and A. Eskandarian. A reliable link-layer protocol for robust and scalable intervehicle communications. IEEE Transactions on Intelligent Transportation Systems, 8(1):4–13, March 2007. R. Mangharam, R. Rajkumar, M. Hamilton, P. Mudalige, and Fan Bai. Bounded-latency alerts in vehicular networks. In 2007 Mobile Networking for Vehicular Environments, pages 55–60, May 2007. Z. Doukha and S. Moussaoui. A sdma-based mechanism for accurate and efficient neighborhood discovery link layer service. IEEE Transactions on Vehicular Technology, PP(99):1–11, 2015. Katrin Bilstrup, Elisabeth Uhlemann, ErikG Strom, and Urban Bilstrup. On the ability of the 802.11p mac method and stdma to support realtime vehicle-to-vehicle communication. pages 1–13, 2009. K. Sjoberg, E. Uhlemann, and E.G. Strom. Delay and interference comparison of csma and self-organizing tdma when used in vanets. pages 1488–1493, July 2011. A. Alonso and C.F. Mecklenbrauker. Stabilization time comparison of csma and self-organizing tdma for different channel loads in vanets. In 12th International Conference on ITS Telecommunications (ITST), pages 300–305, Nov 2012. Fei Xie, K.A. Hua, Wenjing Wang, and Y.H. Ho. A-adhoc: An adaptive real-time distributed mac protocol for vehicular ad hoc networks. In Communications and Networking in China 2009, pages 1–6, 2009. Fan Yu and S. Biswas. Self-configuring tdma protocols for enhancing vehicle safety with dsrc based vehicle-to-vehicle communications. volume 25, pages 1526–1537, 2007. S. Bharati and Weihua Zhuang. Cah-mac: Cooperative adhoc mac for vehicular networks. Selected Areas in Communications, IEEE Journal on, 31(9):470–479, September 2013. NHTSA. Vehicle safety communications project final report. Technical Report DOT HS 809 859, 2005. C. L. Robinson, L. Caminiti, D. Caveney, and K. Laberteaux. Efficient coordination and transmission of data for cooperative vehicular safety applications. In Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Networks, VANET ’06, pages 10–19, 2006. SAE. Dedicated short range message set (dsrc) dictionary. Technical Report Tech. Rep. Standard J2735, 2006. X. Xie, R. Cheu, and D. Lee. Calibration-free arterial link speed estimation model using loop data. Journal of Transportation Engineering, 127:507–514, 2001. Mircea Augustin ROSCA and Aura RUSCA. Methods for green times allocation in under-saturated signalized intersection. UPB Scientific Bulletin, Series D, 74, Oct 2012.

Xiaoxiao Jiang received a BE degree in Information Engineering from Beijing University of Posts and Telecommunications, Beijing, China in 2010, and a MS and PhD degrees in Computer Science from the University of Minnesota, Twin Cities, USA in 2015. She is currently a System Architect at Verizon Lab, USA. Her research interests include vehicular ad-hoc networks, wireless networks, cloud computing and Big Data. She is a member of the IEEE.

David H.C. Du received a BS degree in mathematics from National Tsing-Hua University, Taiwan, R.O.C. in 1974, and a MS and PhD degrees in Computer Science from the University of Washington, Seattle, in 1980 and 1981 respectively. He is currently the Qwest Chair Professor at the Computer Science and Engineering Department, University of Minnesota, Minneapolis. His research interests include cyber security, sensor networks, multimedia computing, storage systems, high-speed networking, high-performance computing over clusters of workstations, database design and CAD for VLSI circuits. He has authored and co-authored more than 230 technical papers, including 110 referred journal publications. He has also graduated 54 Ph.D. and 80 M.S. students. Dr. Du is an IEEE Fellow and a Fellow of Minnesota Supercomputer Institute. He is currently served on a number of journal editorial boards. He has also served as guest editors for a number of journals including IEEE Computer, IEEE and Communications of ACM. He has also served as Conference Chair and Program Committee Chair to several conferences in multimedia, database and networking areas.

0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

Loading...

A Prediction-based TDMA MAC Protocol for Reducing - Projectsgoal

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final pub...

2MB Sizes 2 Downloads 9 Views

Recommend Documents

An Enhanced Reservation-Based MAC Protocol for IEEE - MDPI
Mar 30, 2011 - www.mdpi.com/journal/sensors. Article. An Enhanced Reservation-Based MAC Protocol for. IEEE 802.15.4 Netw

A Protocol for Dying - Hintjens.com
Apr 21, 2016 - It can be horribly awkward to talk to a dying person (let's say "Bob"). Here are the ... My kids are twel

Reducing Disaster Risk: A challenge for development
community is facing a critical challenge: How to better anticipate — and then manage and reduce — disaster risk by .

PROTOCOL FOR GASTROSCHISIS
Gastroschisis is rarely associated with other congenital anomalies or syndromes. .... and adhesive bowel obstruction are

PowerPoint for Mac 2011 Help - PowerPoint for Mac - Office Support
Follow this roadmap of training and Help topics to learn how to use Microsoft PowerPoint for Mac 2011 in a systematic, s

Detune for mac download
KarmaFX - Audio Music Software - Virtual Instruments and.

Best proxy for mac
It forwards network traffic from applications that do not support proxies and avoids complex Nov 05, 2017 · Download Be

Guidelines For Completing A Research Protocol For - UCL
Apr 9, 2010 - The aim of this guide is to help researchers write a research study protocol for an observational study. .

Tian Jiutherapy for allergic rhinitis: study protocol for a randomized
Standard Protocol Items: Recommendations for Interventional Trials. SPSS. Statistical Packages for the Social Sciences.

EazyDraw For Mac
Vector drawing software application for Mac. ... Easy enough for everyone but with the depth your project will need. Inc