Broadcasting with Prediction and Selective Forwarding in Vehicular Networks

Abstract

Broadcasting in vehicular networks has attracted great interest in research community and industry. Broadcasting on disseminating information to individual vehicle beyond the transmission range is based on inter-vehicle communication systems. It is crucial to broadcast messages to other vehicles as fast as possible because the messages in vehicle communication systems are often emergency messages such as accident warning or alarm. In many current approaches, the message initiator or sender selects the node among its neighbors that is farthest away from it in the broadcasting direction and then assigns the node to rebroadcast the message once the node gets out of its range or after a particular time slot. However, this approach may select a nonoptimal candidate because it does not consider the moving status of vehicles including their moving directions and speeds. In this paper, we develop a new approach based on prediction of future velocity and selective forwarding. The current message sender selects the best candidate that will rebroadcast the message to other vehicles as fast as possible. Key to the decision making is to consider the candidates' previous moving status and predict the future moving trends of the candidates so that the message is spread out faster. In addition, this approach generates very low overhead. Simulations demonstrate that our approach significantly decreases end-to-end delay and improves message delivery ratio.

1. Introduction

Vehicular ad hoc networks (VANETs) are mobile ad hoc networks (MANETs) between road-bound vehicles such as cars and trucks. Vehicles play important roles in our daily life. Nowadays, vehicles are becoming more and more intelligent. Smart vehicles integrate environment-aware, route-planning, decision-making and drive-assistant technologies. The technologies contain computers, sensors, communication, artificial intelligence, and control technology [1]. VANET has attracted considerable attention from both research community and automotive industry. Many automobile manufacturers started planning to build communication devices into their vehicles for purposes of security, convenience, and comfort. In addition, the increasing importance of VANET has been recognized by the governmental organizations. The Federal Communications Commission (FCC) has allocated particular spectrum for intervehicle communications.

Many attractive applications have emerged [2] with the development of the VANET. The first application is “Collision Avoidance.” About 40 thousand deaths occur every year in USA [3]. Many of them are resulted from vehicles leaving the road or traveling unsafely through intersections. Communications between vehicles and between vehicles and the roads can save many lives and prevent injuries. Some of the worst traffic accidents involve many vehicles striking each other after a single accident suddenly halts traffic. In the application of “Collision Avoidance,” once a vehicle reduces its speed significantly, it will broadcast its location to its neighbor vehicles. The second one is “Cooperative Driving,” such as violation warning, turning conflict warning, curve warning, lane merging warning and [4, 5]. These services may dramatically reduce the accidents. As a matter of fact, many of the accidents come from the lack of cooperation between drivers. Good communications are able to prevent them. The third one is “Traffic Optimization.” Traffic delays continue to increase, wasting a great deal of time for the drivers. A significant reduction in these numbers is achieved through vehicular networks. Vehicles serve as data collectors and transmit the traffic condition information over the vehicular networks. In addition, transportation agencies utilize this information to actively relieve traffic congestion. In particular, each vehicle detects the number of its neighbor vehicles and their averages speeds and then relays this information to vehicles in order to prevent other vehicles approaching the busy location. In some scenario, the information can be relayed by vehicles moving in the other direction so that it may be propagated faster to the vehicles toward the congestion location. Vehicles can also collect the data about weather, road surface, construction zones, highway rail intersection, and emergency vehicle signal and relay them to other vehicles [6, 7]. Other applications related to vehicles are also emerged to VANET nowadays such as payment services like toll collection. It is very convenient and desirable to pass a toll collection without having to decelerate your car, waiting in line, looking for some coins or something like that. Moreover, services such as Location-based Services like finding the closest fuel station, restaurant, lodge, and so forth are not specific to the vehicular networks. Many GPS systems have such kinds of services already. But vehicular networks may not rely on the satellite like GPS and are able to update the most recent scenarios of the services. The scenario is geographic routing. Key to this kind of routing is regarding circumvention of holes [8].

Message dissemination is essential in support of the applications of VANET. Researchers are developing broadcasting approaches to disseminate messages to other vehicles. The design of effective vehicular broadcasting approaches poses a number of challenges. Similar to MANET, VANET has no fixed infrastructure and instead it relies on ordinary nodes to perform routing of messages. However, vehicular ad hoc networks behave in different ways than traditional MANETs. Vehicles move at a fast rate, moving in and out of the reception area of other vehicles participating in the network [9]. As a matter of fact, a pair of vehicles communicate for a limited amount of time. It is also expected that communication between nodes that have never interacted before and will never interact again will be the norm. Thus vehicular networks are very different from existing mobile ad-hoc networks. These characteristics imply that traditional ad-hoc protocols cannot be ruled effectively in the vehicular networking setting [2, 10]. Vehicle-based networks are the high-speed, driving rules-constrained, and road topology-limited mobility of their nodes [9]. The motion of cars in everyday traffic is very different from that of nodes participating in other kinds of mobile networks and influences the physical topology of vehicular networks in a unique way. Because communication protocols are strongly affected by the underlying connectivity structure, the study of the topological properties of a network built over moving vehicles is a basic step toward a full understanding of the behavior of networking techniques. In addition, the mobility constraints and high dynamics are unique characteristics of VANETs. Velocities are also restricted according to speed limits, traffic control mechanisms such as stop sign and traffic light, and the scenario of the road. Furthermore, VANETs encounter a major routing issue, that is, the broadcast storm problem. The broadcast storm problem occurs when mobile nodes send messages by flooding causing frequent link layer contention with other nearby broadcasting nodes and result in packet loss due to collisions. Therefore, it is extremely difficult to design a sound message broadcasting approach, especially the one that can broadcast the messages to other vehicles as fast as possible.

Current approaches focus on employing distance-based mechanism. In these schemes, the sender node tries to select the farthest node in the broadcasting direction and assign it the duty of forwarding the messages. However, these approaches may not select the best candidate that can forward the message to other nodes fastest. In this paper, we develop a prediction and selective forwarding based broadcasting algorithm. In this algorithm, each node maintains the acceleration and the variance of acceleration that can represent its historical mobility status. In addition, each node is able to predict its future mobility trend by considering the two parameters and their current velocity. In the broadcasting process, the sender disseminates a message to all its neighbors in the broadcasting direction. Then it selects the fastest candidate based on considering its neighbors' future mobility and then designates this candidate to rebroadcast the message. Moreover, because each node only needs to maintain two parameters, the overhead is very low. Our simulation results indicate that our approach can significantly decrease the end-to-end delay and improve the message delivery ratio, compared with existing approaches.

The rest of the paper is organized as follows. Section 2 discusses the related research on this topic. Section 3 proposes a novel method to broadcast messages to other vehicles as fast as possible. We evaluate the proposed schemes by simulations and describe the performance results in Section 4. Section 5 concludes the paper.

2. Related Work

The recent message broadcast protocols on vehicular networks are reviewed in this section. Unlike other forms of MANETs, applications developed for VANET have a very specific and clear goal of providing an intelligent and safe transport system. Emergency warning for public safety is one of many applications that is highly time-critical and requires a more intelligent broadcast mechanism than just blind flooding. In [11], the authors proposed a spatially aware packet routing algorithm to disseminate the message in VANETs. This algorithm predicts the permanent topology holes. Then, the geographic forwarding is conducted when the messages are disseminated to other nodes.

Ding et al. proposed SADV, a static-node assisted adaptive data dissemination protocol for vehicular networks [12], which employs mechanisms that enable the packet to wait at an intersection until the best path is available. To achieve this, they add static nodes at intersections that store and forward the packet when appropriate. In addition, to get a more accurate delay estimation of forwarding packets along each road, they let the static nodes measure the packet forwarding delay in real time. Therefore, the routing decision in each static node adapts to changing vehicle densities on the roads. They also study how multipath routing can help decrease the packet delivery delay by increasing the probability of hitting the optimal trajectory under inaccurate delay estimation of each road.

Fazio et al. proposed an interference aware routing scheme for multiradio vehicular networks, in which each node is equipped with a multichannel radio interface [13]. Transmission channels are switched on the basis of a periodical signal-to-interference ratio (SIR) evaluation in order to relieve the effects of the cochannel interference perceived by mobile nodes. A new metric is also proposed in this approach, which maximizes the average SIR level of the connection between source and destination.

Bai et al. [14] study the impact of nodes mobility on the topology of ad-hoc networks, by means of a protocol-independent characterization of connectivity. However, their contribution in that sense is part of a larger framework aimed at explaining the performance of routing protocols in mobile ad-hoc networks and thus suffers from a low level of detail. Also, these works only consider completely random motion representations and very approximated vehicular mobility models, inducing results hardly applicable to real world vehicular networks.

Perkins and Royer proposed a broadcasting algorithm for VANET called FROV [15]. This algorithm is applied in the scenario that the cars have heterogeneous transmission ranges. In addition, the transmission of a car varies while traveling, due to changes of environmental conditions, such as the humidity of the air, rain, snow, and fog. Moreover, topological conditions, such as tunnels, sharp curves, surrounding trees, and buildings, could further influence the transmission ranges. The main idea of FROV is that the node that is selected to rebroadcast a message is the one whose retransmission spans further than other nodes. To accomplish this task, FROV considers both the position and the transmission range, in the direction of the broadcast, for all the receivers of a message. This algorithm handles the scenarios with extreme weather or poor conditions, but it does not consider the mobility status of the vehicles that is essential in VANETs.

A multihop broadcast protocol for intervehicle communication was proposed in [16]. This protocol assigns the duty of forwarding and acknowledging the broadcast packet to only one vehicle by dividing the road portion inside the transmission range into segments and choosing the vehicle in the farthest nonempty segment without a priori topology information. When there is an intersection in the path of the message dissemination, new directional broadcasts are initiated by the repeaters located at the intersections. This protocol considers the longest distance factor when selecting the best rebroadcasting node.

Ni et al. proposed several threshold-based techniques in [17], the counter-based, distance-based, and location-based schemes. Depending on the scheme considered, a node receiving the broadcast packet compares the predetermined threshold value with its local information, that is, the number of duplicate packets received, the relative distance between itself and the sender, or the additional area that can be covered if it rebroadcasts the message. The criteria to adaptively adjust the thresholds according to the number of neighbors were also presented by Tseng et al. in [18]. The results show that the location-based scheme may offer good performance in terms of the packet penetration rate and the link load.

An approach that considers the mobilities of the vehicles was proposed in [19]. In this algorithm, vehicles are divided into several clusters. Each cluster header maintains the moving status and density of the vehicles in its cluster. This approach takes mobility into consideration, but it is very difficult to maintain clusters in VANETs.

3. Broadcasting Protocol with Prediction and Selective Forwarding

3.1. The Basic Idea

We illustrate our approach with a simple example in this section (Figure 1). We assume that all the vehicles (nodes) are distributed in a two-dimensional space and they are in the moving status. Each node has the same transmission range. In addition, errors of measurement for the mobility exist because of environmental conditions [15].

Figure 1

The basic broadcasting scenario.

Figure 1 gives an example in which A is the message sender. Node A broadcasts the message to all of its neighbors in the broadcasting direction. $A^{'} s$ neighbors $C_{1}$ , $C_{2}$ , and $C_{3}$ receive this message. Then, A will select one of them to rebroadcast the messages. A simple strategy lets A select the one that is the farthest away from A in the broadcasting direction. In this case, A selects $C_{1}$ . However, this may not necessarily be the best choice.

Let us assume that node $C_{1}$ is moving at a much lower speed than $C_{2}$ and $C_{3}$ . Further we assume that the historical velocities up to this moment of node $C_{2}$ are $[\dots, 50, 55, 59, 63]$ (miles/hour) and the velocities of node $C_{3}$ are $[\dots, 75, 71, 66, 64]$ . Our goal is to select a node that can rebroadcast the message fast to other nodes. Considering that $C_{2}$ and $C_{3}$ are moving much faster than $C_{1}$ , they are obviously better choices for carrying the message farther down the broadcast direction. If we only consider the current speed, A should choose $C_{3}$ . However, we want to select the one that gets out of the transmission range of A and conduct the rebroadcasting first. This achieves the goal of the fastest rebroadcast of the message. We predict future velocities of these nodes based on their historical and current velocities and then figure out which node is the first one that will get out of A's range. In this example, our strategy will let A choose $C_{2}$ .

3.2. Prediction Based Mechanism

The transmission range of the wireless network for vehicles is normally 300–400 meters long. It is much longer than the width of the road containing multiple lanes. Thus we use a line to represent the road as in Figure 2. Here l is a partial arc of the transmission range crossing the road. In addition, point P is the intersection of l and the road.

Figure 2

Simplified basic broadcasting scenario.

We need to compute which node is the first one that gets out of A's range. The moving trend obviously must be considered. The normal approach to find the moving trend is to let each node save all its history and current velocities and then each node represents its moving trend by curve-fitting approach that approximates its mobility trend. Apparently, this method costs too much. We come up with a model based on Kalman filtering method [20]. In this model, each node only maintains two parameters, its potential acceleration and variance of acceleration, to represent its mobility trend. Then its future velocity can be computed. Thus, node A can figure out the best node to be assigned to conduct the rebroadcasting subsequently.

We observe the discrete moving status with every period $Δ t$ . Suppose we are investigating the nodes at current time k. Node A wants to find the node that will reach P first and then assign it as the rebroadcasting node. We want to compute $c_{i}$ 's potential ability about how fast it can get out of A's range. We mark the transmission range of A as R, the velocity of node $C_{i}$ measured at time k as $v_{i k}$ , and the distance from A to $C_{i}$ as $| A C_{i} |$ . Then the time to reach P is $T_{i} = (R - | A C_{i} |) / | \hat{v_{i_{k}}} - v_{A} |$ . Here $\hat{v_{i_{k}}}$ is the predicted velocity of $C_{i}$ at time k. It indicates the potential ability to get out of A's range. The prediction is based on considering both $C_{i}$ 's historical and current mobility status. In our approach, we predict $C_{i}$ 's velocity for time $k + 1$ to compute $T_{i}$ . Once we know each $\hat{v_{i_{k}}}$ , we will figure out the node with the smallest $T_{i}$ . So our objective is to compute $\hat{v_{i_{k}}}$ .

The naive method of predicting the velocity of time $k + 1$ is as follows. Let node $C_{i}$ save all its historical and current (time k) velocities $v_{i_{0}}, v_{i_{1}}, \dots, v_{i_{k}}$ . Then it predicts its velocity for time $k + 1$ by the curve-fitting method that approximates its moving trend. The problem with this method is that it costs too much. So we devise a model based on stochastic filtering approach, particularly, Kalman filtering method. In our model, each node only needs to maintain values of two parameters, the potential acceleration, and the variance of acceleration at time $k - 1$ and measure the status at time k.

We define the following notations to represent the mobility status for node $C_{i}$ in Table 1. Note that all the notations of acceleration and velocity are vectors.

Table 1

Notations for the mobility status.

Notation	Meaning
$v_{i_{k}}$	The measured velocity at time k.
$\hat{v_{i_{k}}}$	The velocity predicted at time k.
$a_{i_{k}}$	The acceleration measured at time k.
$\hat{\bar{a_{i_{k}}}}$	The acceleration at time k evolved from time $k - 1$ .
$\hat{a_{i_{k}}}$	The potential acceleration at time k.
$p_{i_{k}}$	The variance of acceleration updated at time k.
$\bar{p_{i_{k}}}$	The variance of acceleration at time k evolved from time $k - 1$ .
Q	The error or noise in the process.
$K g_{i_{k}}$	The blending factor at time k.

At time k, $C_{i}$ measures its velocity $v_{i_{k}}$ . And then it computes $a_{i_{k}}$ as its measured acceleration by

\begin{matrix} a_{i_{k}} = \frac{(v_{i_{k}} - v_{i_{k - 1}})}{Δ t} . \end{matrix}

(1)

Node

C_{i}

updates

\hat{a_{i_{k}}^{-}}

and

p_{i_{k}}^{-}

in order to keep its historical moving trend to predict its future velocity. Therefore,

\begin{matrix} \hat{a_{i_{k}}^{-}} = \hat{a_{i_{k - 1}}} \\ p_{i_{k}}^{-} = p_{i_{k - 1}} + Q . \end{matrix}

(2)

Node

C_{i}

also computes the blending factor

K g_{i_{k}}

, which indicates how much the acceleration changes from last time to this time. Therefore,

\begin{matrix} K g_{i_{k}} = p_{i_{k}}^{-} {(p_{i_{k}}^{-} + Q)}^{- 1} = \frac{p_{i_{k}}^{-}}{(p_{i_{k}}^{-} + Q)} . \end{matrix}

(3)

Once

C_{i}

obtains the blending factor

K g_{i_{k}}

and the evolved acceleration

\hat{a_{i_{k}}^{-}}

, it knows how much the acceleration changes and how much the acceleration evolves. Additionally,

C_{i}

considers the measured acceleration

a_{i_{k}}

. Then it computes its potential acceleration

\hat{a_{i_{k}}}

. This acceleration will be used to predict its velocity for time

k + 1

. Therefore,

\begin{matrix} \hat{a_{i_{k}}} = \hat{a_{i_{k}}^{-}} + K g_{i_{k}} (a_{i_{k}} - \hat{a_{i_{k}}^{-}}) . \end{matrix}

(4)

C_{i}

updates the variance of acceleration for future utilization. So,

\begin{matrix} p_{i_{k}} = (1 - K g_{i_{k}}) p_{i_{k}}^{-} . \end{matrix}

(5)

Finally, the velocity predicted for time

k + 1

\begin{matrix} v_{i_{k + 1}} = v_{i_{k}} + \hat{a_{i_{k}}} Δ t . \end{matrix}

(6)

In the entire computation process at time k,

C_{i}

only needs to measure its velocity

v_{i_{k}}

and record two parameters

\hat{a_{i_{k - 1}}^{-}}

and

p_{i_{k - 1}}

. Then it can predict its velocity at time

k + 1

by the calculation.

The direction of the road may not be parallel or perpendicular to the coordinate axes. Moreover, a vehicle may suddenly change its moving direction or speed. So we decompose the velocity into two velocities parallel to the axes of the coordinate plane (Figure 3) to take care of the general scenarios.

Figure 3

Velocities of X and Y decomposition.

In the general scenario, node $C_{i}$ computes its velocity $\hat{v_{i_{{k + 1}_{x}}}}$ in X direction and $\hat{v_{i_{{k + 1}_{y}}}}$ in Y direction at time $k + 1$ and then computes $\hat{v_{i_{k + 1}}}$ = $\sqrt{{\hat{v_{i_{{k + 1}_{x}}}}}^{2} + {\hat{v_{i_{{k + 1}_{y}}}}}^{2}}$ . It further computes $T_{i}$ by $T_{i} = (R - | A C_{i} |) / | \hat{v_{i_{k + 1}}} - v_{A} |$ , the time that node $C_{i}$ gets out of the range of A. Then A figures out the desired node $C_{i}$ with minimal $T_{i}$ .

From node A's perspective, the moving direction of the vehicles and the message broadcasting direction can be identical or opposite. In addition, the message may need to be broadcast to the nodes in its same moving direction, such as siren in its back area that came from the emergency truck in its same moving direction, or to be broadcast to the nodes in its opposite moving direction, such as a car accident in its back area of opposite lanes, or to be broadcast to the nodes in both directions, such as warning of extreme weather. Node A should apply different broadcasting strategies under different cases. In order to describe the cases, we divide message propagation directions to two types. When the message propagation direction is the same as A's moving direction, it is type 1. Otherwise it is type 0. We further define the message in three types based on the intended broadcasting nodes. Type “S” is the message to be delivered to the nodes in A's same moving direction. Type “O” is the message to be delivered to the nodes in A's opposite moving direction. And type “B” is the message to be delivered to nodes of both moving directions. Node A performs six strategies to broadcast the message and then selects next rebroadcasting node. We use P to represent propagation direction and I to represent the message type based on the intended nodes to be delivered. For example, when the emergency truck with alarm is moving behind A and in the same direction of A, P is 1 because the propagation is the same as A's moving direction and I is S because the message will be delivered to the nodes in the lanes of A's same moving direction. The cases are as follows.

Case 1 (P is 1 and I is “S”).

Node A broadcasts the message to its neighbors in its same moving direction and then selects the rebroadcasting node $C_{i}$ of minimal $T_{i}$ from the nodes in its same moving direction (Figure 4).

Figure 4

Case 1.

Case 2 (P is 1 and I is “O”).

Node A broadcasts the message to its neighbors in its opposite moving direction and then selects the rebroadcasting node $C_{i}$ of minimal $T_{i}$ from the nodes in its same moving direction (Figure 5).

Figure 5

Case 2.

Case 3 (P is 1 and I is “B”).

Node A broadcasts the message to its neighbors in both moving directions and then selects two rebroadcasting nodes $C_{i}$ and $C_{j}$ of both directions. $C_{i}$ is the one with minimal $T_{i}$ from the nodes in its same moving direction. $C_{j}$ is the one with minimal $T_{j}$ from the nodes in its opposite moving direction. (Figure 6).

Figure 6

Case 3.

Case 4 (P is 0 and I is “S”).

Node A broadcasts the message to its neighbors in its same moving direction and then selects the rebroadcasting node $C_{i}$ of minimal $T_{i}$ from the nodes in its opposite moving direction (Figure 7).

Figure 7

Case 4.

Case 5 (P is 0 and I is “O”).

Node A broadcasts the message to its neighbors in its opposite moving direction and then selects the rebroadcasting node $C_{i}$ of minimal $T_{i}$ from the nodes in its opposite moving direction (Figure 8).

Figure 8

Case 5.

Case 6 (P is 0 and I is “B”).

Figure 9

Case 6.

3.3. Algorithm Description

In the broadcasting process, the location of the initiator is included in the broadcasting message. Once a node receives a broadcasting message, it computes the distance to the initiator. In order to avoid infinite broadcasting from the initiator, we define a distance threshold. The messages are only broadcast within this threshold. Rebroadcasting terminates out of the distance. The algorithms are shown in Algorithms 1 and 2.

We did experimentation to find the distance threshold by considering ratio of packet delivery and end-to-end delay. We derive that 1200 meters, is a good value. We then apply 1200 to the algorithm SFBB(). When initiating a broadcasting message or upon receiving a rebroadcasting signal, a node calls the algorithm SFBB(). The node handles different scenarios by the algorithm Handle_msg.

4. Performance Evaluation

Several simulators on VANETs were introduced [21]. We conduct simulations using the GloMoSim wireless network simulator [22]. We use the tool BonnMotion [23] to generate the mobile nodes. We set the size as Terrain-dimensions (2000, 2000). The MAC layer was 802.11 and the transport layer was UDP. The noise figure we set was 10.0 and the temperature was 290.0. The average speed of the nodes was 25 m/s (about 55 miles/hour). The number of vehicles varies from 50 to 300 with an increment of 50. We set the average packet generation rate from 0.1 to 0.9 per second, which represents the number of packets generated by a node per second.

Many broadcasting protocols are based on the idea that the current sender selects the node that is farthest away from itself to conduct the rebroadcast task. This method is called “DIST” in the comparison. We compare our statistical filter based broadcast protocol “SFBB” with the “DIST” method using two metrics. The first one is the package delivery ratio, which is the ratio of the number of vehicles that receive the broadcasting message over the total number of vehicles. The second metric is the end-to-end delay. It is the time elapsed from the packet generated until the packet reaches the receiver in the desired area. We also compare our “SFBB” with two other approaches. One is geographic based forwarding mechanism in vehicular networks [24] represented as “GEOG” in Figures 10, 11, and 12. The second one is probabilistic based protocol [25] represented as “PROB” in Figures 10, 11, and 12.

Figure 10

The packet delivery ratio.

Figure 11

The end-to-end delay.

Figure 12

The packet delivery ratio.

Figure 10 shows the average ratio of packet delivery when the number of nodes changes from 50 to 300 and the average packet generation rate is fixed as 0.5. The delivery ratio decreases when the number of nodes increases. This is because 802.11 protocol performs poorly with more nodes due to the packet collision. This figure indicates that the delivery ratios of SFBB and GEOG are close. They are higher than those of the other two mechanisms. That is because both SFBB and GEOG guarantee a high ratio of packet delivery while partial packets get lost in DIST and PROB.

Figure 11 shows the average end-to-end delay with the same configuration as Figure 10. It illustrates those the end-to-end delays of SFBB and PROB are close. They are lower than that of DIST and GEOG. DIST are GEOG are focused on distance rather than considering broadcasting speed. They even need to handle void areas. So the delays of the two are higher.

Figure 12 presents the ratio of packet delivery when the rate of packet generation varies from 0.1 to 0.9 and the number of nodes is fixed as 150. Similar to Figure 10, the ratios of SFBB and GEOG are higher because SFBB and GEOG guarantee a high ratio of packet delivery. Figure 13 shows the end-to-end delay of the approaches. This figure also indicates that SFBB and PROB have lower end-to-end delays than those of DIST and GEOG methods.

Figure 13

The end-to-end delay.

5. Conclusion

In this paper, we presented a new message broadcasting algorithm for vehicular networks. In this algorithm, a message sender selects the best node among its neighbors that rebroadcast the message fast to other nodes. Each node only keeps values of two parameters to record its moving trend. Together with the current velocity of each node, the sender determines which node is the best candidate. The simulations demonstrate that our approach improves the delivery ratio and decrease the end-to-end delay over distance based and probabilistic based algorithms.

Security is another very important issue in VANETs. We would apply our approach to WAVE [26] to achieve a more robust approach in the near future.

Algorithm 1: SFBB algorithm.

SFBB()

if it is the initiator

Call Handle_msg.

elseif the distance to the initiator is greater than the threshold

Stop re-broadcasting;

else Carry the message;

Call Handle_msg right after it gets out of the sender's range.

Algorithm 2: Handle_msg algorithm.

Handle msg()

if $P = = 1$ and $I = =$ “S”

Broadcast the message to its neighbors in its same moving direction;

Select the re-broadcasting node $C_{i}$ of minimal $T_{i}$ from the nodes in its same moving direction.

if $P = = 1$ and $I = =$ “O”

Broadcast the message to its neighbors in its opposite moving direction;

Select the re-broadcasting node $C_{i}$ of minimal $T_{i}$ from the nodes in its same moving direction.

if $P = = 1$ and $I = =$ “B”

Broadcast the message to its neighbors in both moving direction;

Select two re-broadcasting nodes $C_{i}$ and $C_{j}$ of minimal $T_{i}$ and $T_{j}$ from both moving direction.

if $P = = 0$ and $I = =$ “S”

Broadcast the message to its neighbors in its same moving direction;

Select the re-broadcasting node $C_{i}$ of minimal $T_{i}$ from the nodes in its opposite moving direction.

if $P = = 0$ and $I = =$ “O”

Broadcast the message to its neighbors in its opposite moving direction;

Select the re-broadcasting node $C_{i}$ of minimal $T_{i}$ from the nodes in its opposite moving direction.

if $P = = 0$ and $I = =$ “B”

Broadcast the message to its neighbors in both moving direction;

Select two re-broadcasting nodes $C_{i}$ and $C_{j}$ of minimal $T_{i}$ and $T_{j}$ from both moving direction.

Send a re-broadcasting signal to the node(s) selected.

References

Gao

ICAR hybrid network: a smart invehicle network for ScudWare

Proceedings of the 1st Chinese Conference on Harmonious Human Machine Environment (HHME '05)

October 2005

Kunming, China

Stampoulis

Chai

A Survey of Security in Vehicular Networks 2005

Yale University

Kranakis

Singh

Urrutia

Compass routing on geometric networks

Proceedings of the 11th Canadian Conference on Computational Geometry

1999

Fang

Gao

Guibas

L. J.

Locating and bypassing holes in sensor networks

Mobile Networks and Applications 2006 11 2 187 200

2-s2.0-33646734122

10.1007/s11036-006-4471-y

Yang

Fei

Bipartite graph based dynamic spectrum allocation for wireless mesh networks

Proceedings of the 28th International Conference on Distributed Computing Systems Workshops (ICDCS '08)

June 2008

Beijing, China

IEEE

96 101

2-s2.0-51849136104

10.1109/ICDCS.Workshops.2008.27

Takagi

Kleinrock

Optimal transmission ranges for randomly distributed packet radio terminals

IEEE Transactions on Communications 1984 32 3 246 257

2-s2.0-0021386815

Wisitpongphan

Bai

Mudalige

Sadekar

Tonguz

Routing in sparse vehicular ad hoc wireless networks

IEEE Journal on Selected Areas in Communications 2007 25 8 1538 1556

2-s2.0-35348956501

10.1109/JSAC.2007.071005

Yang

Fei

HDAR: hole detection and adaptive geographic routing for ad hoc networks

Proceedings of the 19th International Conference on Computer Communications and Networks (ICCCN '10)

August 2010

Zurich, Switzerland

IEEE

2-s2.0-77958452949

10.1109/ICCCN.2010.5560012

Fiore

Harri

The networking shape of vehicular mobility

Proceedings of the 9th ACM International Symposium on Mobile ad Hoc Networking and Computing

2008

10.

Yang

Fei

Statistical filtering based broadcast protocol for vehicular networks

Proceedings of the 20th International Conference on Computer Communication Networks

2011

Maui, Hawaii, USA

11.

Jacquet

Muhlethaler

Qayyam

Optimized link-state routing protocol

IETF MANET Internet Draft, 2002

12.

Ding

Wang

Xiao

A static-node assisted adaptive routing protocol in vehicular networks

Proceedings of the 4th ACM International Workshop on Vehicular Ad Hoc Networks (VANET '07)

September 2007

59 68

2-s2.0-37849007552

10.1145/1287748.1287758

13.

Fazio

Rango

F. D.

Sottile

An on demand interference aware routing protocol for vanets

Journal of Networks 2012 7 11 1728 1738

14.

Bai

Sadagopan

Helmy

The important framework for analyzing the impact of mobility on performance of routing protocols for adhoc networks

Ad Hoc Networks 2003 1 4 383 403

2-s2.0-10444234788

10.1016/S1570-8705(03)00040-4

15.

Perkins

C. E.

Royer

E. M.

Ad-hoc on-demand distance vector routing

Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA '99)

February 1999

New Orleans, La, USA

90 100

2-s2.0-34347349933

10.1109/MCSA.1999.749281

16.

Johnson

Maltz

Jetcheva

The dynamic source routing protocol for mobile ad hoc networks

IETF MANET Internet Draft, 2002

17.

Tseng

Chen

Sheu

The broadcast storm problem in a mobile ad hoc network

Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '99)

1999

151 162

18.

Tseng

Y.-C.

S.-Y.

Shih

E.-Y.

Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad hoc network

Proceedings of the 21st IEEE International Conference on Distributed Computing Systems

April 2001

481 488

2-s2.0-0035019894

19.

Park

V. D.

Corson

M. S.

Highly adaptive distributed routing algorithm for mobile wireless networks

Proceedings of the 16th IEEE Annual Conference on Computer Communications (INFOCOM '97)

April 1997

Kobe, Japan

1405 1413

2-s2.0-0031353437

20.

Basagni

Chlamtac

Syrotiuk

V. R.

Woodward

B. A.

A distance routing effect algorithm for mobility (DREAM)

Proceedings of the 4th annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '98)

1998

21.

Martinez

F. J.

Toh

C. K.

Cano

J.-C.

Calafate

C. T.

Manzoni

A survey and comparative study of simulators for vehicular ad hoc networks (VANETs)

Wireless Communications and Mobile Computing 2011 11 7 813 828

2-s2.0-79960522491

10.1002/wcm.859

22.

Zeng

Bagrodia

Gerla

GloMoSim: a library for parallel simulation of large-scale wireless networks

Proceedings of the 12th Workshop on Parallel and Distributed Simulation (PADS '98)

May 1998

154 161

2-s2.0-0031652485

23.

Nils

Ernst

Gerhards-Padilla

Schwamborn

Bonnmotion: a mobility scenario generation and analysis tool

Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques

2010

24.

Leontiadis

Mascolo

GeOpps: geographical opportunistic routing for vehicular networks

Proceedings of the IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WOWMOM '07)

June 2007

Espoo, Finland

2-s2.0-47749113660

10.1109/WOWMOM.2007.4351688

25.

Wisitpongphan

Tonguz

O. K.

Parikh

J. S.

Mudalige

Bai

Sadekar

Broadcast storm mitigation techniques in vehicular ad hoc networks

IEEE Wireless Communications 2007 14 6 84 94

2-s2.0-37249048864

10.1109/MWC.2007.4407231

26.

Ghandour

A. J.

Felice

M. D.

Artail

Bononi

Dissemination of safety messages in IEEE 802.11p/WAVE vehicular network: analytical study and protocol enhancements

Pervasive and Mobile Computing 2013

10.1016/j.pmcj.2013.03.003