1 Introduction

Owing to recent social developments, the increase of traffic on the roads has intensified [1] and as a result, more traffic problems are occurring. In response, the Intelligent Transportation System (ITS) has been proposed as a means of solving these traffic problems. In addition, research on Vehicular Ad-hoc Networks (VANETs) for the ITS has been taking place around the world (e.g., the European project Car2Car). In VANETs, Vehicle-to-Vehicle (V2V) and Vehicle-to Infrastructure (V2I) communications are practical and important research areas. For these research issues [2, 3, 4], international standardization is presently being undertaken by the IEEE 802.11p working group. The IEEE 802.11 Distributed Coordination Function (DCF) protocol [5] has been used as a basis for the new VANET standard. The core idea behind the use of V2V and V2I is the need to provide communication protocols to facilitate the exchange of different types of information between vehicles, road sensors, road signs and signals, and even pedestrians.

In a VANET, each vehicle has to be constantly aware of its surroundings (e.g., the speed and/or direction of other vehicles). For this reason, each car has to periodically broadcast a short control message, such as beacon. For safety-related applications, more frequent updates between vehicles are required. However, the probability of transmission delays and packet collisions increases when too many packets are transmitted in accordance with the IEEE 802.11 DCF protocol. In [6], Torrent-Moreno studied beacon broadcasting in regards to the IEEE 802.11p VANET protocol. In [7], a novel MAC Vehicular Mesh Network (VMESH) protocol that uses the multi-channel structure of the Wireless Access in Vehicle Environments (WAVE) method for V2I communication has been proposed. VMESH further divides the Control Channel (CCH) interval into a beacon period (BP), and a safety period (SP) that is reserved for safety applications only. The BP is divided into beacon slots during which each vehicle broadcasts its beacon, including information on its current position. Information regarding the reservation-based TDMA scheme applied to Service Channels (SCHs) and Roadside Units (RSU) is exchanged between nodes by means of the beacons. The main shortcoming of this approach is that, by dividing the CCH into these two periods, the opportunities for the transmission of safety messages are reduced. As a consequence, the transmission of safety messages could be delayed.

Therefore, more investigations into beacon broadcasting in VANETs are needed. Furthermore, the development of new analytical methods that are more precise and can help to develop ways to improve performance is also necessary. In this paper, an Efficient Beacon Scheduling (EBS) is proposed based on the WiMedia MAC. This protocol can be used to solve the problem of beacon collisions by incorporating it into the IEEE 802.11p VANET WAVE protocol.

The remainder of this paper is organized as follows: Section 2 provides an overview of the WAVE MAC and the WiMedia MAC architectures [8]. Our EBS proposal is described in Sect. 3. We evaluate our proposed scheme in Sect. 4 by comparing its performance with that of the legacy IEEE 802.11p solution via both numerical analyses and simulation experiments. Finally, in Sect. 5, we give our concluding remarks.

2 The Overview of WAVE and WiMedia

The IEEE 802.11p/WAVE protocol [9–17] is designed to see the presence of one CCH, which is reserved for system control and safety messages, and up to six SCHs that are used to exchange non-safety data packets (e.g., IP traffic) and WAVE-mode short messages. Coordination between the channels exploits a global time reference, such as Coordinated Universal Time (UTC), which can be provided by a global navigation satellite system. As shown in Fig. 1, the WAVE channel time is divided into synchronization intervals with a fixed length of 100 ms. The synchronization interval consists of a CCH interval and a SCH interval of 50 ms, respectively. According to the multi-channel operation, all vehicular devices have to listen for every CCH interval, and switch to SCH during the SCH interval. This operation allows for safety warning messages to be transmitted during CCH intervals, whereas non-safety data are exchanged during the SCH intervals.

Fig. 1
figure 1

WAVE channel time switching

Full size image

The topology of a VANET changes rapidly and expands to a multi-hop range network during communication. Therefore, in a VANET, each vehicle has to be constantly aware of its surroundings. For this reason, each car periodically broadcasts a beacon that includes information on its position. Therefore, a stable multi-hop MAC protocol between vehicles is required.

We chose the self-beaconing WiMedia MAC protocol to satisfy the above condition. The most problematic part of a multi-beacon protocol is beacon collision. Beacon conflict arises when a select beacon slot that has two or more devices within communication range is identical during the transmission of a beacon frame. The probability of beacon collision depends upon the number of devices in communication range and the total number of available beacon slots. When the number of devices in the same communication range increases and the number of available beacon slots is limited, the probability of beacon collisions increases.

As a result, the time needed to resolve beacon collisions can become long. In the worst case, the functionality of the VANET can be disrupted. In other words, if a VANET has high device mobility that changes in its network topology happen frequently. As a result, the occurrence of beacon collision is highly probable. Beacon conflicts need to be solved quickly in order to maintain a stable network structure.

Because the WiMedia MAC protocol is decentralized (it does not use a central coordinator); each device controls its channel access and transmits its own beacon in order to obtain information from neighboring devices. The beacon is periodically transmitted during the synchronized interval in a predefined beacon section. Therefore, it needs an improved technique in order to reduce the possibility of beacon collisions in a WAVE system. We present an algorithm that provides an efficient way to reduce beacon collisions, and also improves the reliability of distributed beaconing. In addition, this algorithm permits the curtailment of time when it is resolving beacon collisions. This is preferable in an environment where the network topology changes often.

Figure 2 shows an example of the constitution of an ad-hoc wireless communication network that operates according to IEEE 1609.4 standards. The devices shown in Fig. 2 are vehicles that are designed to communicate with each other via installed wireless interface On Board Units (OBUs). In order to keep a connection between all of the neighboring devices and to update each other’s information, the devices periodically broadcast their own beacon frame. Usually, this beacon frame carries network topology and transfer state information, for example, along with other information, such as the vehicle speed, acceleration/deceleration, direction, device service profile information, and device performance information.

Fig. 2
figure 2

An example of a wireless communication network between vehicles possessing high mobility

Full size image

Figure 3 shows the beacon frame format that is used in the WiMedia MAC protocol. In the WiMedia MAC protocol, all of the devices follow a system structure that is synchronized in a decentralized way; this includes a beacon period that consists of many beacon slots, as illustrated in Fig. 4.

Fig. 3
figure 3

WiMedia MAC beacon frame format

Full size image
Fig. 4
figure 4

Structure of the WiMedia MAC protocol superframe

Full size image

In the superframe structure depicted in Fig. 4. A superframe is composed of a beacon period and a data period, each period is divided into beacon slot and Media Access Slot (MAS), respectively. The Distributed Reservation Protocol (DRP) reservation section, wherein each device “precontracts” for data transmission on a beacon frame, has an advantage in that it can send data without competition. However, this is disadvantageous to emergency data transmissions because a transmission must be precontracted beforehand. The Prioritized Contention Access (PCA) section is the CSMA/CA data transmission section that uses the Enhanced Distributed Channel Access (EDCA) method to assign priority. This section is suitable for emergency data transmission because it does not require a special reservation and high priority data is transmitted first. However, because the WAVE system uses multiple channels, the WiMedia MAC protocol of single channel needs to be altered in order for it to also use multiple channels.

3 The EBS Scheme

3.1 The Applied WiMedia MAC

The channel structure illustrated in Fig. 5 is used in VANET protocols that operate according to IEEE 1609 standards.

Fig. 5
figure 5

An example of the applied WiMedia MAC protocol in the IEEE 1609.4 channel structure

Full size image

Figure 5 is divided into two major channel sections: the Control Channel (CCH) and the service channel (SCH). In the CCH section’s beacon period, all of the devices transmit a beacon frame, or exchange serious warning messages—these must be done in the control channel. The SCH section can be switched electively in order to service channels for different devices dealing with non-safety applications; however, all stations must switch back to the control channel before the start time of the next CCH section. As can be seen in Fig. 5, there is a contention period between the beacon period and the SCH interval, this section is used for emergency data transmission.

The beacon frame transmission of each device is done in the manner defined in the WiMedia MAC protocol. If a collision is detected, the stations associated with the collision must reselect available beacon slots in order to resolve the collision.

3.2 The EBS Scheme

As illustrated in Fig. 6, two devices, A and E, selected the third slot for their beacon transmission in the nth beacon period, resulting in a conflict being reported by the next device, device C. Devices A and E have to then randomly select a new slot in order to resolve the collision in the subsequent beacon period.

Fig. 6
figure 6

An example of beacon conflict and resolution

Full size image

In Fig. 7, A and E are once again in conflict for the third slot in the nth beacon period. To try and resolve this collision, devices A and E have once again randomly selected an available slot during the subsequent beacon period. However, since the available slots are limited in number, both devices selected the same fourth beacon slot and, as a result, must now resolve a new beacon conflict.

Fig. 7
figure 7

Situation when the beacon collision remains after one try

Full size image

Figure 8 shows the flowchart for our proposed algorithm. This can be applied to all of the wireless devices shown in Fig. 2, but the operation of device A is used here as an example.

Fig. 8
figure 8

Flowchart for our collision prevention algorithm

Full size image

At the start, device A searches in the beacon period to find an available beacon slot in order to transmit its beacon frame. However, a collision occurs in the beacon section since another device, E, is transmitting the same beacon frame for the third slot. When the next scan starts, the entire beacon period is scanned to advantageously find an available beacon slot. After the scan is performed once, device A selects one of the available beacon slots. In the next scan, device A receives a beacon frame that is transmitted by the other devices in the network. These beacon frames are known as estimated beacon frames. These estimated beacon frames are transmitted in the contention period in order to notify the devices of the intent to transmit a beacon frame to a specified beacon slot in regard to the other devices in the network. If these estimated beacon frames are received without conflict, device A transmits its beacon frame to the beacon slot that is selected for the next beacon period n + 1.

Now, suppose that device A detects that the estimated beacon frames received will cause a conflict. An estimated beacon is received from device E, which is trying to reserve the third slot for beacon frame transmission. Since device A has also selected the identical slot, a possible beacon conflict is detected. This procedure is repeated until the possibility of beacon collision is no more. After the possible beacon conflict is detected, device A selects another beacon slot for beacon frame transmission. (The fourth slot is selected in this example.) Device A then determines whether other arbitrary estimated beacons have been received. If a new estimated beacon has been received) although the procedure is continued if other estimated beacons are not detected), device A transmits an estimated beacon that notifies the other devices of its intention to use the fourth slot for beacon frame transmission in the next contention period. This estimated beacon includes the intended beacon slot number for the beacon frame that is to be transmitted in the next beacon period. The estimated beacon is transmitted in the contention access period. Therefore, before any device transmits its beacon frame, or before it changes its beacon slot, it has to transmit an estimated beacon in the contention period. The estimated beacon is transmitted using the CSMA/CA method after the random time delay from the starting point of the contention period.

Once device A transmits a successful estimated beacon, it continues transmitting in the beacon slot that is selected in the next beacon period. As can be seen in Fig. 9, no beacon collision occurs on this occasion because device A uses the fourth beacon slot while device E uses the third beacon slot.

Fig. 9
figure 9

An example of a beacon collision solution

Full size image

Using the above scenario, it is possible for a situation to occur in which devices A and E cannot communicate with each other but a third device can receive the estimated beacons from devices A and E. In this case, device C knows that the two devices have transmitted their intention to use the third slot. Device C can also detect the intended slot. In this example, device C can also detect that the third slot is occupied by the other communication devices. Thus, device C, immediately after the detection of a possible beacon collision, will transmit a collision warning beacon. The collision warning beacon’s transmission must also use the CSMA/CA method, and it also includes a conflict slot number. In this example, the information includes the third slot and the device identifiers (devices A and E in this example) related to the possible conflict. In the device identifier list, device E is notified by the collision warning beacon. Because of the estimated beacon received previously from device A, device E must defer to device A.

The collision warning beacon is used to resolve the intention of the two estimated beacons to use the same beacon slot in the next beacon period, and thereafter notifies the estimated beacon not to use the beacon slot that is already occupied by the other neighboring device. Thus, it is used to warn neighboring devices that a possible conflict has been detected. The collision warning beacon carries beacon slot information that a collision is predicted, and the sequence of device identifiers associated with the latent collision. The sequence order of device identifiers can be composed so that the devices may correlate priority orders that can use the beacon slot. If device A receives a collision warning beacon, it will retransmit in the newly selected beacon slot. In this example, device A retransmits its intention to use the fourth slot. Therefore, even if there is a hidden station problem, any possible latent collision is resolved before the next beacon period. This situation is illustrated in Fig. 9. Therefore, according to the characteristics of these warning beacon, device A listens to the warning beacons and if they signify a possible conflict and the estimated beacon transmitted by the current device has a low priority, the flowchart in Fig. 8 can be modified to select another beacon slot. In addition, since the active device catches estimated beacons, it can also catch warning beacons.

4 Analysis and Experiments

We analyze the identification delay of DFSA with muting and that of the proposed policy. In order to get valid analytical models for both IEEE 802.11p and EBS, the following assumptions were made in this study: (1) The underlying channel is ideal and has no transmission error. (Packet error occurs only when two packets collide.) (2) The impact from the mobility of the devices on the packet transmission is insignificant. (3) The system is in a saturated and stable state, i.e., each device always has a packet to transmit. We calculated and compared the saturation throughput reached by each protocol during a beacon period.

The relevant MAC parameters used in the EBS scheme are listed in Table 1. tCLKP is the PHY clock period; tOP is the time MAC output data, which is valid from the rising edge of MCLK (MAC to PHY); tSU is the setup time to the rising edge of PCLK (PHY to MAC); tH is the hold time from the rising edge of PCLK; and tCLKd is the delay from the PCLK edge to the MCLK edge, which is used to maintain backward compatibility.

Table 1 The MAC signal timing values
Full size table

The delay in the general Beacon Period (D BP ) for the beacon frame transmission is expressed by (1). The t PBP is the time of the Pure Beacon Period; and the t G is the time of the Guard Interval in the Beacon Period. In addition, the t PBP is expressed by (2). The t PBP_Slot is the time for one Beacon Slot in the Beacon Period and n is the number of vehicles. The delay in the Sync Interval Period (D SIP ) is expressed by (3). The time for the Contention Period and the Contention-free Period is represented by t CP and t CFP , respectively, in addition to the run time for t CP and t CFP . However, if a collision occurs, the delay is longer. There is no beacon period in the IEEE 802.11p scheme, but the delay is longer than our scheme because of a collision during the Contention-free Period. Therefore, it needs a more accurate scheduling method. The minimum collision delay is calculated using (4) for the Sync Interval Period (CD SIP-802.11p ) in a collision. On the other hand, the minimum delay in our EBS algorithm (CD SIP-EBS ) consists of the scheduling in the Beacon Period (CD BP-EBS ) and the guard interval in a collision. The collision delay for the Beacon Period and the sync interval period can be calculated using (5) and (6), respectively.

$$ D_{BP} = t_{PBP} + t_{G} $$
(1)
$$ t_{PBP} = n \times t_{PBP\_Slot} $$
(2)
$$ D_{SIP} = D_{BP} + t_{CP} + t_{CFP} $$
(3)
$$ CD_{SIP - 802.11p} = 2 \times (D_{BP} + t_{CP} + t_{CFP} ) $$
(4)
$$ CD_{BP - EBS} = 2 \times t_{PBP} $$
(5)
$$ CD_{SIP - EBS} = CD_{BP - EBS} + t_{G} $$
(6)

We evaluated our protocol in terms of robustness and efficiency by examining the delay using the mathematical results with respect to a collision. It is natural that our protocol reduces the delay much better than the existing protocols with respect to collisions from the above mathematical analysis. The amount of delay is closely related to the total throughput and the energy consumption. However the energy consumption is also related to the source data rate, which is independent of the protocol. Therefore, the overhead needs to be examined separately in order to analyze the efficiency of the protocol. Based on the assumptions given at the beginning of the previous section, the SCH channel resources can be reserved by devices following the EBS protocol. The reservation is done through CCH beaconing and no signal overhead is introduced to the SCHs.

The packet is generated by each device on Poisson distribution independently and randomly. Each device generates n packets in t time. The expected value for the interval of packet generation is 1/λ. The expected value is calculated by the device number—its probability (P n (t)) is expressed by (7).

$$ P_{n} (t) = \frac{{{\text{e}}^{ - \lambda t} (\lambda t)^{n} }}{n!} $$
(7)

The probability (P 0 (t)) of no packet generation in t is e−λt. Therefore, the first packet is generated as 1 − e−λt after t. The general form for the probability of the packet generation is expressed by (8). The traffic and the total device number are represented by G and D num , respectively. The time for one packet transmission is T time , while the expected value for the packet generation is T int .

$$ p(t) = \frac{G}{{D_{num} }} = 1 - {\text{e}}^{{\frac{{T_{time} }}{{T_{\text{int}} }}}} $$
(8)

The expected value for the packet generation and the time for one packet transmission are expressed by (9) and (10), respectively. The P(t) is represented by x.

$$ T_{\text{int}} = - \frac{{T_{time} }}{{\log \left( {1 - \frac{G}{{D_{num} }}} \right)}} $$
(9)
$$ t = - T_{\text{int}} \times \;\log (1 - x) $$
(10)

The saturation throughput of the proposed MAC on the SCH can be easily calculated by dividing the amount of information successfully sent in one DRP reservation by the duration of the DRP reservation length:

$$ S_{EBS} = \frac{Information\;Sent\;In\;One\;Reservation}{Duration\;Of\;Reservation\;Length} $$
(11)

The DRP transmission is illustrated in Fig. 5. Equation (11) can be written as (12), where Np is the maximum number of packets that can be transmitted in a reservation with the given reservation length Tres. E is the size of the transmitted packets.

$$ S_{EBS} = \frac{{N_{p} \cdot E}}{{T_{res} }} $$
(12)

Figure 10 shows the calculated maximum throughput of the EBS for the SCH according to the packet size.

Fig. 10
figure 10

Throughput of the EBS MAC for SCH

Full size image

We also examined the average percentage of collisions, the end-to-end delay, and the total throughput using a simulator. The performance of the EBS was examined in simulation experiments using network simulator 2 (NS2). The performance metrics were the collision, the delay, and the total throughput. In the simulation, the wireless NS 2.27 communication modules were used with their default parameters. 802.11 DCF was used as the underlying MAC protocol [3, 18–22]. The essential parameters for the proposed scheme and IEEE 802.11p were as follows: The simulated area was 10 km (a three-lane highway). The speed of the vehicles and their density were set to range from 80 to 120 km/h in 20 km/h increments and from 100 vehicles to 600 vehicles in 100 vehicle increments, respectively. The transmission range was 250 m. The data packet size was 64 B. The control packet size was 36 B. The message risk zone was 1 km and the percentage of alert generating vehicles was set from 10 to 50 % in 10 % increments. All of the performance figures refer to scenarios where 30 % of the vehicles generated one alert message per second. (We do not show the results obtained with other percentages, since they were qualitatively equivalent for the analysis.)

Figure 11 confirms this interpretation, by showing the average collision percentage obtained at the MAC layer in the VANET, with respect to the total amount of message transmissions performed. The 802.11-based flooding scheme produced a significant 10–40 % collision risk, as a function of the vehicle density range and the transmission message load. The collision probability was reduced by 802.11p MAC due to the priority-based effect of the biased back-off scheme. The collisions were significantly reduced when our proposed MAC was adopted, due to the beacon scheduling. Figure 12 shows the average end-to-end delay obtained by messages to cover a variable distance (x) in a low-density scenario (200 vehicles over 10 km). The 802.11p MAC protocol produced a poorer average delay than the flooding protocol. This problem was caused by the contention window settings. Figure 13 shows the results under a low traffic load; the throughputs achieved by the three protocols were quite similar. However, when the traffic load increased, the EBS protocol outperformed the other protocols in terms of throughput. The results illustrate the benefits of a collision free access protocol with regards to beacon scheduling for guaranteeing a stable throughput.

Fig. 11
figure 11

Average percentage of collisions

Full size image
Fig. 12
figure 12

MAC end-to-end delay

Full size image
Fig. 13
figure 13

SCH throughput comparison

Full size image

5 Conclusion

Delay and throughput for the frequent topology updates in VANETs must be guaranteed. The existing IEEE 802.11p/WAVE MAC protocol consists of CCH and SCH periods. If a collision problem is not resolved in a CCH period, then both the delay and the throughput get degraded. Therefore, we applied the multi-beacon method for the efficient exchange of information.

In this paper, we presented a method that enables efficient dissemination in VANETs by means of beacon scheduling. Our proposed EBS scheme reduces the delay and data collisions—as shown by mathematical analyses and simulation results. In addition, our algorithm improves the total throughput, and is compliant with IEEE 802.11 DCF and IEEE 802.11p. The performance of the EBS has been compared with other schemes and shows general advantages in performance, such as better reliability and overhead reduction. For our future work, we will undertake performance optimization of the EBS MAC protocol using various types of information obtained via beaconing.