Keywords

1 Introduction

Vehicular Ad hoc networks (VANETS) are simply a collection of on-board units (OBU) and road side units (RSUs) which communicates using Dedicated Short Range Communications (DSRC) utilizing 75 MHz in 5.9 GHz frequency band for WAVE. The Fig. 1 shows frequency channel layout of WAVE which is divided into 7 channels with one channel for service safety applications and the remaining for service non-safety applications [1]. The nature of VANET environment being dynamic it is most likely that packet forwarding over varied time intervals may be disconnected causing network delays. In such a case the message containing information needs to be with the current vehicle until new node becomes active.

Fig. 1
figure 1

Channel layout of WAVE system with 1 control channel (CCH) and 6 service channel (SCH)

Full size image

In order to effectively utilize the seven channels IEEE 1609.4 and 802.11p provides co-ordination methods and channel access mechanisms. Extensive research has undergone in the area of VANETs for new utilization of these channels. The usage of the medium for communication may change with time of the day or vary over period of same days. Large number of studies have addressed to the problem of data aggregation in case of vehicular environments [2]. Now if every vehicle includes the complete path of itself and its neighbours it consumes large amounts of bandwidth which makes use of network resources, however this problem can be subdued by data encoding and compression.

But the question that comes is that what part of the path should be shared by the vehicle. Simply stating every vehicle may limit its sharing of path knowledge over a limited area around its location. As mentioned previously the WAVE has seven channels one for safety service and remaining for non-safety service both being controlled by time division [3]. With time being synced at default sync intervals of 100 ms. when the specific channel intervals begin it always starts with a guard interval which is used for accounting radio switching and inaccuracies in timing among different vehicles. The WAVE MAC interval architecture describes transit operations, data queuing, prioritization, channel selection and channel routing as shown in Fig. 2.

Fig. 2
figure 2

Internal architecture of WAVE MAC

Full size image

For reliable packet delivery conventional method used in case of VANET was Vehicle Assisted Data Delivery (VADD) which segments the roads and fastest route is selected around the current vehicle location as well as destination. The current vehicle considers adjacent vehicles in the same road segment to select the best path as next carrier [4]. In this paper a new approach is simulated in which time sharing is the main focus for every vehicle in order to carry a given message. Each vehicle is aware of high density segments in four opposite directions through its digital map. The aggregation includes time needed to reach any high density segment of the road. In the aggregation the probable vehicle trajectory is not important a vehicle does not act as a relay [5]. On the contrary in the case of relay after receiving the packet, relay mechanism uses location based broadcasting to relay packet towards destination.

Extensive studies have been conducted on propagation of messages in vehicular networks. Although the conventional methods are mainly focussed on homogenous traffic and high, low density in traffic is not considered. Figure 3 shows the mobile node structure in NS-3 which has been designed to support 802.11 MAC with a single channel [6, 7]. However this mobile node is not appropriate for WAVE multi-channel operation. Therefore we need to have every single MAC with its own priority based packet buffering. Figure 4 shows modified mobile node structure in order to support the multi-channel co-ordination as required by WAVE.

Fig. 3
figure 3

Structure of mobile node

Full size image
Fig. 4
figure 4

Structure of modified mobile node

Full size image

2 Packet Delivery in Vehicular Ad Hoc Networks

In case of VANETs the current location of the vehicle with corresponding geographical elements need to be considered in order to achieve high rate of reliable packet delivery. In this paper an approach is discussed to combine as well as distribute knowledge gained by a node regarding the best paths and is forwarded to interested nodes. While such information in case of VANETS is time bound i.e. if path information is not delivered within a few minutes it becomes useless and distribution of such information would simply occupy network resources [8]. Therefore the goal of the proposed algorithm is to provide information in a reliable fashion to areas of interest rather than to specific nodes.

An assumption is taken into consideration that most of the commuters follow a repetitive path about 60% of the time. The same assumption can be used to statistically exploit such repetitive patterns between vehicles. This pattern can be used to calculate the degree to which the given information is useful to a vehicle when it receives from its neighbours [9, 10]. This can be used as a measure to whether this information can be used and/or forwarded by using the channel provided by WAVE. In order to verify maximum channel utilization and interval access operation we use the same simulation which is explained in details in further sections of the paper. In the simulation nodes are created using the modified mobile node structure and one set of nodes are configured for sending and the other set for receiving packets. The nodes sending packets generate a control packet (CCH) and a signalling packet (SCH) which is sent to either CCH or SCH [11]. For proper transmission a packet in CCH interval moving towards SCH must wait for SCH interval. Packet creation and sending times are extracted from the trace files generated by NS3 are explained in Table 1. It can be clearly seen that a given packet T1 with CCH interval is formed at 11.03 s and immediately sent at 11.0302 s. Similarly packet T2 with SCH interval formed at 11.03 s was delayed because of the CCH interval and was sent at 11.0632 s with SCH interval.

Table 1 Creation time and sending time of packets
Full size table

Each vehicle stores its own path traversed based on which future path is predicted. When two or more vehicles encounter they exchange information regarding previous knowledge of path traversed by each vehicle, the information also contains knowledge about time taken by a packet for delivery reliably. Every delay in measurement is not same as a result of which the variation in delays may be large [12, 13]. Hence information exchange should be considered as an aggregation of information similar to previously captured information. Since storage is limited and recording multiple hops would lead to large amounts of information, the proposed algorithm’s main objective is to combine the various encounters and measure delay in message delivery towards popular paths. Advantage of this process is that it results in greater degree of precision.

3 Performance Evaluation of Proposed Algorithm

In this section the proposed algorithm’s performance evaluation is explained in detail. However before going into the details certain assumptions that were made need to be discussed, which are that each node has a copy of information that is being distributed which means more than one copy of a message may be moving around in the network. The simulation is setup in such a manner that each segment of the road is part of an intersection. A general assumption is taken that for a given road segment the vehicle in that segment is identifiable as being at one place [14]. On longer road segments there is a possibility that cars may not meet however this proposed algorithm only functions when a given vehicles are within the range of communication. The vehicle is assumed to be moving along a road segment i.e. the vehicle is either covering the whole road segment or partially covering it before moving out of the network.

For the sake of keeping things simple a given road segment is considered to be having exclusive density characteristics with respect to traffic. Thus each vehicle on a given road segment would identify same density of traffic. Although these features vary with time the inter-vehicle distances have an exponential distribution which has a mean distance of \( 1/\alpha_{k} \) where \( \alpha_{k} \) is simply the density of vehicles on a given road segment ‘k’. Now as assumed that traffic density sensed by each vehicle in given road segment is uniform, the same assumption is used to define \( l_{k} \) which is simply the delay in packet forwarding for a given road segment and equals to:

$$ l_{k} = \left( {1 - e^{{ - P\alpha_{k} }} } \right)\frac{{Q_{k} }}{P}b + e^{{ - P\alpha^{k} }} \frac{{Q_{k} }}{{S_{k} }} \ldots \ldots \ldots \ldots $$
(1)

Density of vehicles \( \alpha_{k} \) in a given road segment ‘k’ can be computed using previously known data or by using the count of neighbours in a given road segment k. the traffic on a given road segment k could be high or low. Traffic in a given road segment is considered to be high if delay of relay in a packet is lesser than that for actually carrying it by a factor of ‘\( \rho \)’:

$$ \left( {1 - e^{{ - P\alpha_{k} }} } \right)\frac{{Q_{k} }}{P}b < \rho e^{{ - P\alpha_{k} }} \frac{{Q_{k} }}{{S_{k} }}\quad 0 < \rho < 1 \ldots \ldots \ldots \ldots $$
(2)

Where P is the range of transmission and \( Q_{k} \) is length of a given road segment ‘k’. ‘b’ is a constant which approximates the delay for packet relay for a given pair of neighbours. \( S_{k} \) is simply the travel speed in a road segment ‘k’. The same categorization of road segments is used later on as well in order to select path with lowest delay in packet relay. Realistic simulations of vehicular traffic makes it clear that uniform distribution of traffic is not present [15]. High traffic road segments show that a single connected mesh is created with time or smaller meshes may be formed of low traffic. Each pair of source and destination can either be surrounded by high traffic road segments or separated by a road segment. In both scenarios nodes relaying information could end up with selecting the best path, including segments of high traffic.

By using knowledge of traffic characteristics roads can be categorised as to having high or low traffic however such methods as also used by VADD for selecting paths with lowest packet delay are not effective when traffic density is very low in which finding appropriate path with lowest packet delay becomes problematic. In case of VADD it selects the next best possible path on the basis of currently available vehicles in range [16, 17]. However lacks knowledge of future candidate vehicles for information relay. In such cases VADD ends up selecting a bad candidate for relay resulting in greater delay in packet transmission and also increases un-reliability. The proposed algorithm however proves to be more effective than VADD as it is able to find better paths with lowest delay as well as it is able to utilize knowledge gained for future path prediction maintaining high levels of privacy [18, 19]. A heuristic approach is used to reduce number of possible path selections in a few decisions. These decisions are taken in such a manner that the path selected would have road segments with shortest path not necessarily directly pointing towards destination but road segments of high traffic density. The advantage of doing so is that high density road segments provide mesh type connectivity among vehicles with lower delay in packet relay.

Now as mentioned earlier 60% of vehicle trips are on previously traversed paths and each vehicle keeps a copy of knowledge it has gained. Therefore the same knowledge of path can be used for future path prediction as well as computing forwarding time which is expected for a given road segment ‘k’ referred to as \( M_{{f_{k} }} \):

$$ M_{{f_{k} }} = \left\{ {\begin{array}{*{20}l} {\frac{{Q_{k} }}{{S_{k} }},} \hfill & {for\,k \in high\, density\,traffic} \hfill \\ {l_{k} ,} \hfill & {for\,k \in low\,density\,traffic} \hfill \\ \end{array} } \right. \ldots \ldots \ldots \ldots $$
(3)

The equation mentioned above is based on the fact that vehicles in high density road segments are able to quickly relay packets towards their destinations. As this approach is over and above VADD, which acts as the basis for forwarding time computation for a given expected path and is relative to node density for a given road segment [20, 21]. In order to remove the requirement of global knowledge on travelling time, each vehicle calculates delay in delivery for a message. Dijkstra’s shortest path calculation is used to compute delay in delivery for a road segment.

The expected time of travel for a given road segment ‘k’ is defined by keeping in mind the heavy traffic segments surrounding the segment in question as \( G_{exp}^{u} (k) \). This value is initially kept equal to the summation of expected times of travel for different vehicles, starting with the current segment in question till that vehicle is reached which is present on the first heavy traffic road segment [22]. With each iteration for a given road segment the initial value is changed based on the experienced time of travel and is given by \( G_{exp}^{v} (k) \) [23, 24]. Each moment of time in which a vehicle is able to locate a new surrounding vehicle it tries to synch it’s time of travel that it has experienced. Whenever a new time is sent from a surrounding vehicle given as \( G_{exp}^{n} (k) \) an update is made as per the following:

$$ G_{exp} \left( k \right) = \beta (\alpha G_{exp}^{n} \left( k \right) + \left( {1 - \alpha } \right)G_{exp}^{o} \left( k \right) + \left( {1 - \beta } \right)T_{exp}^{V} (k) \ldots \ldots \ldots $$
(4)

Β being the weighing factor used to adjust vehicle time in order to compute overall travel time:

$$ \beta = e^{{ - log_{2} \frac{{\gamma^{2}. neigbouring\,vehicles\,count}}{{\gamma^{2}. average\,of\,vehicle\,times}}}} \ldots \ldots \ldots $$
(5)

Each vehicles broadcasts its new time of travel in the high traffic road segment if there is a vehicle which has not got updates. This process is done periodically and occurs at every \( Z_{int} \). As explained in the previous section the rate at which information is synched is based on the fact of traffic sensed in the background [25]. If network resources are heavily consumed and time taken to sync is too long then the sync broadcasts are not sent at all. Time sync can be computed as \( E_{sn} \) where:

$$ E_{sn} = e^{ - A.C.B} \cdots \cdots \cdots \cdots $$
(6)

Such that

$$ C = \frac{1}{{C_{pp} \frac{1}{n}\mathop \sum \nolimits_{i = 1}^{n} \frac{1}{{\left[ {\frac{{C_{rc} \left( i \right)}}{{C_{su} }}} \right] + \in }}}} \cdots \cdots \cdots \cdots $$
(7)

And

$$ B = \frac{{\mathop \sum \nolimits_{j = 1}^{m} \frac{{F_{j} }}{{X_{j} }}}}{{C_{su} }} \cdots \cdots \cdots \cdots $$
(8)

Where ‘A’ is the adjustment factor, ‘C’ is the urgency in time required for sending sync broadcast with \( C_{rc} \) as remaining time, \( C_{su} \) as time interval between updates, \( C_{pp} \) is period of prediction, ‘B’ acting as utilization factor for the network and F, X representing bits per transmission and rate of transmission respectively [26].

4 Simulation Parameters and Results

In order to validate the results of the proposed algorithm it is compared with VADD. In the research community VADD is considered as the basis for implementation in a large amount of VANET based applications. NS-3 is used as a simulator for broadcasting and syncing transmissions among vehicular nodes. The traces generated by SUMO are recorded and are used to simulate in NS-3 which acts as the urban simulator for mobility. The screenshot of SUMO is shown in Fig. 5 which depicts the road map created. The trace files contain large amounts of data so in order to simplify only a randomly selected selection from the trace file is simulated in NS-3 [27, 28]. The performance results of the proposed algorithm are compared with VADD. Important parameters used in the simulation are mentioned in the Table 2.

Fig. 5
figure 5

Roadmap created for the simulation

Full size image
Table 2 Simulation Parameters Used
Full size table

In the setup 150 vehicles are considered which are flowing in from both direction of the two roundabouts and the cross-section of the high speed highway traffic density is considered to be from low to high with vehicles moving in high traffic road segments as well as low traffic road segments. Comparison is done on the basis of delivery rate, delay and overhead.

In the Fig. 6 delivery rate is shown as a function of total number of iterations. With each iteration the knowledge gained by the vehicle is adjusted based on previous iterations. The timer stops even if delivery to vehicle continues in case of the desired vehicle receiving its packet. The graph shows that initially the proposed algorithm (PA) has a very low delivery rate but with time by making use of previous knowledge and adjustment factor it shows better performance than VADD. The reason for this better performance is due to the usage of prior gained knowledge for a given road segment for each vehicle which is broadcasted and synced with other vehicles in the same road segment.

Fig. 6
figure 6

Data delivery rate versus number of iterations

Full size image

In the Fig. 7 the average delay in delivery is shown, the proposed algorithm performs better than VADD in case of high traffic and low traffic road segments this is because as mentioned earlier the PA uses relay which reduces packet delay significantly even in case of large number of packets being generated in the network for distribution. In Fig. 8 the effect of overhead distribution of prior gained knowledge is shown. The generated data is compared with control packets at the time of full network utilization. Comparative to VADD the proposed algorithm shows better results this is because the PA keeps a check on the rate of sync between vehicular nodes which does not result in over utilization of network resources which if occurs is bad as VANETs have mainly been used for safety based applications.

Fig. 7
figure 7

Average delay of delivery versus number of sources

Full size image
Fig. 8
figure 8

Generated traffic per KB versus number of sources

Full size image

5 Conclusion

The proposed algorithm shows functioning of environmental aware distribution method which can be used in VANETs. The algorithm is based on the assumption that most vehicles over a period of time follow a repetitive path which can be used as knowledge gained over a period of time to predict the future path of the vehicle. The main objective is to simply provide a high rate of data delivery among vehicles moving from source to destination with reliability. In order to provide better results low density traffic road segments need to be considered with relaying. The results show promising improvements in delay of packets with contained overhead. For future work more performance based comparisons can be shown with larger network diversity and different traffic conditions. Also improvement is required in data packet queuing when packets are carried by a vehicular node. Certain traffic conditions are not considered such as traffic jams and accidents during the execution of simulations however that can be included in the future.