VANETs: To Beacon or not to Beacon?

Roberta Fracchia, Michela Meo, Dario Rossi

Politecnico di Torino, Italy
email: name.surname
@polito.it

Abstract— We address the broadcast problem in intervehicular neighbors. Finally, suburban tollbooths or intelligent traffic-
networks by considering two antipodean approaches: the first one lights in urban environments could receive and relay traffic
makes use of instantaneous information on vehicles position, while or road conditions information coming from infrastructured
the other one relies on its longer-term knowledge, gained through
a beaconing procedure. Using a realistic microscopic model to networks.
represent the vehicular traffic flow, we investigate and compare In this context, adopting a realistic microscopic model to
the performance of the proposed algorithms through simulation. represent the vehicular traffic, we investigate the performance
We show that a significant performance tradeoff exists: indeed, of two distributed algorithms for broadcast communication
though the approach based on longer-term knowledge proves in VANETs. The approaches we consider are orthogonal
to be more efficient in terms of the channel utilization, the
instantaneous strategy is intrinsically more robust to errors due in the sense that they are based on opposite mechanisms:
to the wireless channel. Finally, we show that this fundamental the B EACONLESS approach relies on instantaneous infor-
tradeoff can be turned into an advantage, and we investigate the mation on vehicles position only, whereas the B EACONED
effectiveness of an hybrid solution that combines the diversity of one exploits its longer-term knowledge, maintained through
the above approaches. the exchange of beacon packets. Let us anticipate that an
interesting performance tradeoff exists: though the B EACONED
approach is close to the optimum in terms of the channel
I. I NTRODUCTION
utilization, the B EACONLESS one is intrinsically more robust
In the last years, wireless communications have enjoyed to wireless channel errors. This tradeoff suggests that no
an amazing expansion in many different directions – from definite and unique answer exists to whether it is better to
bringing connectivity in many under-development areas at implement and exploit beaconing or not: different applications
lower costs with respect to cabling, to offering high-revenues or services may find more favorable either strategy depending
Internet connectivity services on-board of inter-continental on its specific requirements. Luckily though, we show that this
flights. This evergrowing thirst for connection is pushing for fundamental tradeoff can be also turned into an advantage,
the deployment of communication devices in a new area, i.e., and we investigate the effectiveness of an hybrid solution that
the so-called vehicular ad hoc networks (VANETs). combines the diversity of the above approaches.
Typically, given the intolerable number of deaths and in-
juries caused by car accidents, road-safety services are brought
II. R ELATED W ORK
as a paradoxical example of “killer application” in VANETs:
in this vision, vehicles sport on-board wireless communication The problem of routing in ad-hoc networks has been ex-
facilities so that, when dangerous situations are detected (either tensively studied in the context of Mobile Ad hoc Networks
by specific on board sensor devices or by drivers initiative), a (MANET), whose results have been the natural starting point
warning message can be automatically propagated to vehicles for VANET research as well. However, due to the intrinsic
that follow by adopting ad hoc networking capabilities. Wire- differences of these networks, when applied to VANETs, the
less technologies, such as Dedicated Short Range Communica- most promising routing strategies are not as effective as for the
tion (DSRC) [1], could be thus used to enhance the perceptive MANET context. Moreover, although unicast routing service
capabilities of the driver in a specular way to what the rear- may be required, it is well recognized that most applications
view mirror does, by providing a “networked spyglass” that often resort to broadcast communications [5]. Broadcast al-
allows to foresee dangers beyond the driver cognitive horizon. gorithms can be mainly divided into two groups: namely,
Inter-vehicular research [2]–[4] is also fueled by the beacon-less strategies versus beacon-based approaches. The
appeal of an entirely new market segment, which in- performance of these algorithms has been extensively studied
cludes geographically-contextualized advertisement, entertain- and compared in the MANET context [6], [7], adopting
ment applications and services aimed at improving passengers rather simple mobility models that neglect the existence of
traveling comfort. In many cases, the nature of the services and correlation among the mobile nodes: therefore, broadcast com-
the unknown and varying identity of the users will favor the munication needs further investigations in the VANET context
use of broadcast, rather than unicast, communication [5]: for – that feature very constrained string-type topologies, on the
example, road works could advertise their presence through one hand, but strongly correlated movements and very high
a wireless device beside the usual traffic signals and flags; speeds, on the other hand.
sensors on board of vehicles (or even directly deployed in the The beacon-less algorithms closest to ours can be found
concrete) may detect icy road pavement; under heavy fog, the in [7] and [8], where several (either beacon-based or beacon-
network itself could reveal the presence of otherwise invisible less) approaches designed for MANETs are compared. More
specifically, [7] introduces a uniform distributed waiting time, d(k+1,k)<0 d(k−1,k)>0
while our approach, instead, actually increases the lowest
waiting time in order to ensure that every node gathers suffi- xn xout x in xrx xtx x 1 BP
cient information of the system status. Moreover, the idea of x
letting the decision process depend on the distance is already E xk+1 xk xk−1
present in [8], but the decision process is threshold-based R
rather than probabilistic. Among the beacon-less algorithms Vehicles movement Broadcast propagation
specifically designed for inter-vehicle communication, we may
cite [9]–[11]. In [9] only one forwarding node is selected by Fig. 1. Schematic representation of the broadcast propagation
dividing the road portion within the transmission range into
segments and by choosing the vehicle in the further non-
empty segment; however, this broadcast algorithm requires in a highway-like scenario. Broadcast propagation may start
MAC layer modifications to the IEEE 802.11 standard and from any traveling vehicle or from stationary road-side units,
does not consider delay constraints. Finally, [10] introduces a and is targeted to all vehicles within a relevant area. Vehicles
waiting time, proportional to the distance from the transmitter, outside this area, instead, never relay the message, so that the
decremented by one unit at each idle slot, while in [11] the medium remains available for other possible communication
waiting time depends on the progress that the node can provide services.
towards the destination. In order to describe the algorithms, we adopt the notation
The use of beacons to discover and maintain neighbor sketched in Figure 1. Let the road be represented by an
relationships is gaining popularity in both unicast and broad- x-axis in the direction of vehicles movement: the relevant
cast inter-vehicular communications. In principle, the bea- area starts in the Broadcast Point ( 
), and comprises 
coning information could be used either in a topology- or a vehicles positioned along the x-axis at  . 
position-based fashion. Recent work [12] though, highlighted The broadcast message is forwarded over the relevant area
that topology-based approaches, while very appealing for exploiting multi-hop ad hoc communications: the message
MANETs, are not suitable for VANETs: indeed, the high propagates from  in the opposite direction with respect
vehicle mobility makes the topology discover and maintenance to the vehicles movement (i.e., toward decreasing values of ) 
task very expensive, introducing an excessive amount of and, hopefully, it should reach all nodes up to the -th one 
control message overhead. Therefore, approaches that rely that is the last one in the relevant area.
on the knowledge of the geographical position of nodes   !" #%$ '&
Let the distance between nodes and  
be denoted by
in the network, gathered through Global Positioning System , where, clearly, the distance is positive if
(GPS), are growing consensus in both academic and corporate 
node is closer to ( 
than node . The assumption of the
research: the basic idea is to exploit more precise information road linearity bares additional discussion: indeed, it could be
(i.e., position, direction and speed) while avoiding to maintain  )$+*,.-*/
argued that roads are actually quite convoluted and, in fact,
complex global topological information. This class can be   0$1*,
the geographical distance

can be smaller than
for some . However, we point out that, being
mainly divided in geographic forwarding [13], where each
node forwards incoming packets to exactly one of its neigh- vehicles equipped with GPS, they are also likely equipped
bors, and restricted flooding [14], where flooding is restricted with a navigation system as well: therefore, a digital map
to a given region. The broadcast beacon-based algorithms will be available at the receiver. In this case, the position
designed for VANETs and closest to ours are [15], [16]. A advertised by transmitters in the broadcast packets can be re-
routing algorithm for urban-like environments is presented in mapped to a “linearized” road portion, and thus the actual
[15]: every node decides to forward the message only if it road-distance, rather than the air-distance, could be easily
estimates to be closer to the trajectory toward the destination considered. Moreover, such road winding can be expected
with respect to its neighbors. In [16] the rebroadcast decision to occupy a relatively small highway portion compared to
is delayed of an amount of time proportional to the distance the roughly straight one. Finally, the study of a linear road
from the transmitter. As opposite to traditional beaconing in stretch is a preliminary but necessary step, before more
vehicular communications, where each node advertises only realistic but complex scenarios (e.g., involving intersection,
its speed and position, the approach requires each vehicle motorway overpasses and highway junctions) could be taken
to advertise its complete neighbor list, generating thus a into account.
remarkable amount of network traffic: our approach, instead, Another important remark is that, although broadcast pack-
is to seek for a mechanism that can be easily implemented, ets likely refer to a single traffic direction, they are nevertheless
while providing at the same time satisfactory performance received by both directions of the traffic flow. However, for the
even under realistic traffic. sake of simplicity, in the following we consider the road stretch
in the broadcast propagation direction only. First, we point
III. T HE N ETWORK S CENARIO out that this is basically equivalent to assume that vehicles
traveling in the opposite direction can discriminate, via the
A. Scenario Assumptions GPS, if the received message is pertinent to the direction of
In order to evaluate the effectiveness of the broadcast lanes they are traveling along (which can be done simply
communication, we consider a broadcast message propagation by testing whether the direction of the broadcast message
propagation is the opposite with respect to their traveling C. Vehicular Traffic Models
direction). Second, we stress that vehicles traveling in the The performance of wireless communication algorithms in
opposite direction could relay the non-pertinent messages on mobile ad hoc networks strongly depends on the adopted
purpose: indeed, in low density networks, these vehicles could mobility model, especially when, as in our case, a high
helpfully extend the network connectivity and the message mobility scenario is analyzed. In [17], by considering a number
coverage – although this may be challenging due to high of popular traffic models, we showed that, although network
relative speeds among vehicles, it may as well represent an connectivity remains largely unaffected by the specific used
advantage to exploit. model, the traffic model plays a critical role in determining
the performance of inter-vehicular communication algorithms
B. Communication Assumptions
under study. In this paper we adopt a realistic microscopic
Let us now elaborate on nodes communication capabilities. traffic model that falls in the category of Coupled Maps (CM)
We do not focus on a specific technology, but we assume models. These models have coarse-grained discrete time, while
that the on-board device transmits at a data rate of 2 Mbps on space is continue, and, as testified by independent empirical
a R=200 m transmission range, where the low data-rate has traffic measurements [18], [19], they display properties similar
been chosen by virtue of its better resilience to the wireless to the real traffic dynamics (considering both individual vehi-
channel errors. Also, we do not investigate the content of cle movements and the correlation between the behavior of
the broadcast message but we assume that i) the position of neighboring vehicles). The most popular CM model is due to
the broadcast initiator, and ii) the position of the last relay Gipps [20] but, in reason of its simpler notation, we report here
vehicle are reported, so that message rebroadcast can be easily
confined in the relevant area. Besides, we assume that packet
the formulation of Krauß’s [21]. Each vehicle is individually
represented by a state vector
 IKJ 
describing its spatial
header contains the iii) broadcast initiator identifier as well location, speed and distance from the vehicle ahead, and, at
as iv) a randomly chosen packet identifier, assigned once each time slot, the state vector of each vehicle is updated
by the original source: all nodes are required to cache this according to the following set of rules:
information on a soft-state table and, at every forwarding hop LMM
in the network, each node performs a table lookup, avoiding MM Velocity-update
to rebroadcast a message carrying the same identifiers more
N J>39PRQTSUVJ -XWZY [\ Z
than once. MM J W S93 V]^_%`Ja-cb dJ 39PQ/S dJfe Phgji
For what concerns the MAC protocol, nodes adopt a 0- MMO JkV]blI`/=KJ W S93 $mbonp i
persistent Carrier Sense Multiple Access (CSMA) mechanism: Motion-update
in order to avoid collisions, before starting a transmission, qrs-tJ
they sense whether the channel is busy. In the latter case,
the message transmission is delayed, for an amount of time
where b denotes the maximum vehicle acceleration, the u
slots 23547698:<;>=@?
s uniformly distributed between zero and
n
maximum deceleration, is the noise amplitude and is a p
v =F*w Jx
A)BCEDF* J   Jz-mJx K{f;
random number in . Moreover, if is the velocity of the
the contention window size , until the medium is
sensed idle.
y
car ahead at time , we further indicate with the k
Finally, in the case where a position-based routing layer average of the vehicles velocities used to determine the safe
is implemented by the communication device, we adopt the speed bound J,39PRQTS
. The first rules describe deterministic car-
common beacon format and the standard beaconing procedure following behavior: drivers try to accelerate except when the
described in the literature. To be more precise, beacons are gap from the vehicle ahead is too small or when the maximum
usually about 20 Bytes long and carry information regarding speed is reached. Vehicles speed is limited not only by the
i) the vehicle identifier, ii) its geographical position and iii) its maximum velocity J>e PRg
but also by the desired acceleration b
speed. Every vehicle caches the beacon information along with and by the safe speed bound J 3dPRQTS
, which depends on the local
the time of its reception, which will be later used to estimate conditions of the traffic. The speed is also subject to a random
the neighbor’s position. The inter-beacon transmission interval perturbation: with a probability , a vehicle ends up being p
 is usually a fixed value between 1 s and 5 s. Moreover, slower than what calculated deterministically: this parameter
simultaneously models effects of i) speed fluctuations at free
in order to avoid synchronization and beacon collisions, we
jitter the transmission of each beacon as in [13], so that driving, ii) over-reactions at braking and car-following, and iii)
the inter-beacon transmission time is uniformly distributed randomness during acceleration periods. In our simulations,
 
in [0.5 , 1.5 ]. We point out that the beacons transmission we set J e Phg to 135 km/hr and the time-step granularity is |y 
requires a very low channel utilization. Indeed, considering * s, even if these units are assumed implicitly and left out of the
 b uTnh}  =~;jK=F~ €F*,~ =l
20-Bytes beacons and  equal to 1 s, the beaconing task of equations. The parameters are set to
values that are standardly used in the literature [21].
,
every vehicle consumes 160 bps of physical layer bandwidth:
at the highest density we consider, namely 50 veh/Km, the
20 vehicles lying in the same transmission range would thus IV. B ROADCAST A LGORITHMS
use 3.2 Kbps. Given a physical layer channel capacity of In this section we describe the two algorithms that we use
2 Mbps, the channel utilization would be thus as low as 0.16%; to compare B EACONED and B EACONLESS broadcast commu-
similarly, we can derive a channel utilization of 0.03% when nications. For comparison purposes, in what follows we will
GH s. also consider the optimum centralized solution that selects the
 Listen for Receive new
T wait alert pkt

Receive new Forward pkt Avoid to Update yes Rx m>0 no Extract

alert pkt with 0-p CSMA rebroadcast dmin copies? u=U(0,1)

Forward pkt yes

Eval Coverage yes no
~x dmin >0 ? u<P( d min )?
C = x tx - R c < C+E? yes with 0-p CSMA

no no
Update Neighbor Select Closest Avoid to
~
Pos. Estimate Follower x c rebroadcast

Fig. 2. Flow-charts of the B EACONED algorithms Fig. 3. Flow-charts of the B EACONLESS algorithms

minimum rely nodes set that maximizes the message coverage, x #z  ƒ #-  y%$ y9ƒ #Š Jfƒ # , ‹ Œ:‚ ‰ g .
The receiver then individu-

as well as the very simple –flooding strategy, ruling that, upon ates the the closest follower Ž
among its neighbors: is Ž
ŽV>‘K’}“s”–•F#˜—f™>š   ‰ g!$ x #|=l
the reception of a new message, each node forwards the packet the closest neighbor in the message propagation direction,
with independent probability .  thus . Finally, decides to †T
rebroadcast the message when either i) Ž
is outside the
coverage range (i.e., Ž› œT y
in Figure 1), or ii) is Ž
A. Beaconed Algorithm inside the coverage range but within a distance from the ž
The basic idea of the B EACONED algorithm is that, when- coverage border (i.e., ŽŸŠ
). The above two rules, separately
ever some information that has to be broadcasted is received, described for the sake of clarity, can be expressed in a single
each node estimates the position of its neighbors by exploiting threshold-based decision: thus, the message is forwarded iff,
the information previously exchanged by routing layer through  x ¡  8‡g $¢ˆ-cž
.
the use of beacon packets: the neighbors’ position estimate is Observe that errors on the neighbors position estimation
then used to decide whether a message should be forwarded or have negative impact on the performance; in particular, the
not. The forwarding decision aims at trading-off the number sign of the error leads to opposite consequences: over-
of transmitted messages and the probability to inform the ve- estimating the distance of a neighbor raises the number of
hicles: the optimal trade-off is derived when only the furthest unnecessary relay nodes, whereas distance under-estimation
away informed vehicle forwards the message. reduces the number of reached vehicles, thus increasing the
We assume that the routing layer maintains neighborhood probability of a premature interruption of the broadcast prop-
state informations, called the neighbors set  fy ƒ #   #  J #
recording for ‚ agation. Therefore, the safety margin ž
is included in order
each neighbor the tuple  which stores the node ƒ ƒ to reduce the “missed forwarding” errors (i.e., nodes that

identifier , the time of the beacon transmission , the position yƒ # erroneously decide to avoid rebroadcasting) in the decision
ƒ #
and the speed Jƒ #
of the node at the beacon transmission  process, in order to account for: i) under-estimation of the
time. Moreover, neighbor table entries are maintained based on neighbor position and ii) possibly missing neighborhood in-
2
their age using a timer , which can be considered as an “age formation due to beacon loss.
threshold”: below the threshold , the routing-layer informa- 2
tion is considered to be up-to-date, whereas any member of the B. Beaconless Algorithm
‚ 2
set older than is discarded. By preliminary simulations,
The second approach we propose, orthogonal to the previous
we verified that, as the channel utilization due to the beaconing
one, does not rely on any topological information of the net-
is very low, the use of a jittered beacon transmission keeps
work: every node, being unaware of other vehicles’ position,
collisions of beacon messages negligible. As a consequence,
should decide independently, and thus probabilistically. The
when the wireless channel is error-free, in every beaconing

interval , nodes gather a complete information of their
B EACONLESS approach is based on two main ideas: i) to
base the forwarding decision on the distance from the closest
neighborhood. However, in order to increase the robustness
neighboring relay node, and ii) to introduce a short waiting
in case of lossy wireless media, we select the age threshold to
be 2„ ;>
, thus considering valid the information received
time before the message forwarding. The rationale behind the
idea of letting the decision depend on the distance is the
during the last or the second-last beaconing cycle.
following: when a node hears the message for the first time
Considering the nodes of Figure 1, let us assume that at
and its distance from the transmitting node is small, then the
time node y †T
receives a message from node . The re- y5
broadcasting decision process at , sketched in the flow- †/ additional coverage that can be achieved by re-broadcasting
the message is also small1 : thus, the decision to forward the
chart of Figure 2, initially evaluates the broadcast message
message should be taken with low probability. The role of
coverage area as the zone from to ; note that  8‡g F8‡g$ˆ the waiting time is to allow nodes to listen for new copies
this information is precise, since the actual transmitter po-
sition  ‡8 g
is piggybacked in the broadcast packet header.
of the broadcast message: this yields to a better estimate of
Then, †T
updates the estimate of its neighbors position, 1 This assumption is particularly relevant if vehicles have the same trans-
by using the information stored on its neighbor set as ‚z‰ g mission range and in the case of unidirectional propagation.
the smaller relay distance, which is then used to tune the 1 16
forwarding decision process. 0.9 14
The B EACONLESS scheme, whose flow-chart is presented in
Figure 3, works as follows. As soon as a node has received T†  0.8 12

 e #
for the first time a broadcast message from node , the node   y5@d†T y5 Reliability

Accuracy Pinfo
0.7 10

Overhead ο
1
sets the variable to the distance and starts
sensing the channel for a time 2£ Ph#78
, during which the node
0.6
0.95
8

checks if other copies of the same message are received. The 0.5 6

waiting time 2£ Ph#¤8

is set proportional to the time necessary 2 8‡g 0.4 0.9 4
to transmit a full-siwe message augmented by a factor plus ¥ Optimum

v =A)Bw 2@3_4–698 0.3 B=1s 2

a random amount uniformly distributed in of 0.85 B=3s
B=5s
long time-slots: 0.2 0
10 20 30 40 50 10 20 30 40 50

2 £ PR#¤8|V¥ 2'8‡g¦- §¨v =FA)Bw©2ª3547698 (1)

Fig. 4.
Vehicular Density ρ [veh/km]
B EACONED system performance: beaconing interval ¾ impact
Notice that 2ª£ Ph#78 is composed by a fixed and a variable
component. The role of the fixed component ¥ 2 8‡g is to ensure
that node †/ can acknowledge if other vehicles are forwarding delays, transmission times, CSMA delays and implements the
the message, and thus decide to refrain from rebroadcast2. The vehicular traffic model described in Section III-C.
role of the variable component §sv =A)Bw–2 3_476d8 is twofold: first, The performance metrics we consider are: i) the accuracy of
it avoids the synchronization of retransmissions from nodes the message propagation, defined as the percentage of vehicles
that decided to rebroadcast the message; second, and most reached by the broadcast message, that is also the probability
important, it allows the unordered retransmission of nodes that a vehicle is informed; ii) the reliability, defined as the ratio
belonging to the same transmission range. of the accuracy with respect to a reference (e.g., optimum)
Assume that, after time 2 £ Ph#78
, node has collected †T ] value; iii) the propagation overhead, expressed in terms of the
copies of the message from nodes ] . If at least   ~~~d e number of transmitted messages, iv) the redundancy, defined
as the ratio of the overhead with respect to a reference (e.g.,
# such that
  I#dK†/'«¡¬=
one node is further away from the BP, i.e., it exists a node
, then can safely avoid to †T optimum) value, and v) the timeliness expressed as the delay
forward the message: indeed, the message has already covered by which the last informed vehicle receives the message. The
an area which is outside the transmission range of and †T performance indices are obtained with a confidence level of
a re-broadcast from †T
would be useless. Otherwise, if all 99% and a confidence interval of 2%, considering a 2 km long
†T relevant area out of a 8 km long simulated road stretch.
‹     # d†T'­®=
the transmitting nodes are closer to BP than , i.e., if
T†  In the following, when we talk about optimum strategy we
e # sq¯“k”–• # `  e # '   # K†/' i
, then computes the minimum estimated
distance and enters a new refer to the case in which the only node that relays a message is
waiting phase. the furthest node receiving the message. This strategy, when
Conversely, when during the sensing period no copies of the the wireless channel is error-free, is the optimal one, since
it jointly minimizes the number of transmitted messages and
˜
message are received, the message is then forwarded with a
 e  #  e # F
probability , increasing with the minimum estimated maximizes the number of informed vehicles. As a results, on
distance from the relaying hosts. Thus, in the case a linear topology, also the number of collided messages is
where the node decides to rebroadcast, the broadcast message minimized.

 °  e # 
is delivered to the MAC layer. Among the several function
families that can be used to set the probability , we A. Ideal Wireless Channel
choose: In this section we evaluate the performance of the proposed
 ° e #  «*U$  *¦$  e #  {fˆ d±k³²´µ* (2) algorithms, compared to that of the optimal strategy, when the

Note that in the support e # ¶ Œ·v =FKˆaw , the curves are
wireless medium is error free.
Let us first consider the B EACONED approach. Figure 4
monotonically increasing in both e #  and ² , and that the depicts the algorithm performance as a function of the density

function degenerates into e #  {fˆ when ²¸ * . The impact ¿ and for different values of the beaconing interval ÀŒ
of ² in (2) is thoroughly discussed in the next section. ,` *,KDFH i s; initially, we do not consider any error margin on
the position estimate, thus we set žÁ¯= m. The very left
V. P ERFORMANCE E VALUATION plot of Figure 4 reports the algorithm accuracy  info , that is
the percentage of informed vehicles. The optimum centralized
Results reported in this section are obtained with a dis-
strategy is also reported as a reference. It is interesting to
crete event simulator that accurately describes the scenario
notice that when vehicles are in free-flow ( veh/km), ¿ ¡";f=
presented in Section III-B. In particular, the simulator properly
B EACONED performance is very close to the best case –which
describes networking dynamics like collisions, propagation
is mainly driven by the network connectivity– for any of the
2 Since we verified by simulation that the performance results are only 
considered values of : indeed, since the road is uncongested,
marginally affected by any value of ¹.º0»
, in the following we set . ¹U¼0½ vehicles unlikely modify their speed in 5 seconds or less and
Reliability Ratio Versus Optimum Versus B=1s, E=0m

1.00 1 40

0.95 0.9 35

E=8m 0.8 30
E=2m 0.90
E=0m

Accuracy Pinfo
0.7 25

Overhead ο
Reliability
1
0.6 20
Redundancy Ratio

1.20 0.9
0.5 0.8 15
1.10
0.4 0.7 10
1.00 0.6 Optimum
0.3 K=8 5
0.90 0.5 K=2
K=1
0.2 0
10 20 30 40 50 10 20 30 40 50 10 20 30 40 50 10 20 30 40 50
Vehicular Density ρ [veh/km] Vehicular Density ρ [veh/km]

Fig. 5. B EACONED system performance: error margin  impact Fig. 6. B EACONLESS system performance: exponent Ê impact

the position estimate is thus very accurate. On the contrary, relay redundancy: in other words, only about two additional
when traffic is jammed, vehicles speed may rapidly change and messages per broadcast cycle are needed, but at the same time
the accuracy of the position estimate is possibly significantly the periodic beaconing overhead is reduced by a factor of 5.
threatened as increases.  Observing the left plots, it can be seen that the introduction
The inset plot depicts the relative system reliability, that is of an error margin m brings the ËÈÌ¬Í s system ÎÏÌÑÐ
the relative accuracy with respect to the optimum strategy. In- performance very close to the optimum in terms of reliability,
terestingly, reliability shows a negative peak around the critical at the expense of a redundancy increase lower than 25%.
density irrespectively of the beaconing frequency. However, Let us now consider the performance of the B EACONLESS
for higher densities, a smaller beaconing interval translates approach when the wireless medium is error free. Figure 6
into higher system reliability, whereas for large values of the  depicts the results for different values of in (2) as function Ò
¿
reliability decreases as increases above the critical threshold. of the vehicular traffic density. More on details, the figure
Finally, the right plot of Figure 4 reports the algorithm reports the accuracy (left plot), the reliability (inset plot),
Ã
overhead , expressed as the amount of traffic generated in the and the overhead (right plot), achieved by the B EACONLESS
relevant area in terms of the number of transmitted messages. approach and by the optimum centralized strategy, used again
Note that we do not include the beaconing messages overhead, as a reference. First of all, notice that, for high values of
reported in Section III-B in terms of channel utilization, Ò , reliability can be made arbitrarily close to the one of
thus directly investigating the overhead due to the broadcast the optimum strategy, even around the critical density region
message propagation. Notice that also corresponds to the à where the B EACONED algorithm has significant performance
number of relay nodes, since every vehicle forwards the problems. Moreover, unlike in the B EACONED case, reliability
message at most one time: it can be seen that, when s Ä1* increases with vehicular density, because the probability that
or GD
s, the number of relay nodes running this distributed at least one node forwards the message increases. Finally, the
algorithm only slightly exceeds the optimum one obtained by overhead, that also increases as the vehicular density increases,
a centralized strategy. When rÅH
s, a systematic distance in the ÒCÌÓÍ
case is at most three times the one of the
under-estimation leads nodes to refrain from rebroadcasting optimum case.
(i.e., a lower overhead) which in turns reduces the algorithm For what concerns the delay, shown in Table I, it is worth
effectiveness (i.e., a lower accuracy). noticing that, as the overall distance covered by the broadcast
In order to reduce the beaconing overhead and ameliorate
message increases ( Ô¨Õ
20 veh/Km), the average delay incurred
by the message increases as well. At higher densities, the
the system reliability as well, let us now introduce an error
ž
margin on the position estimate: intuitively, the higher the
B EACONLESS delay further increases because the number of
probabilistically chosen relay increases and thus the average
adopted error margin is, the higher the accuracy is. Consider-
ing the worst case „«H
s, we analyze the benefits of intro-
time to access the medium. Conversely, the B EACONED delay,
ducing the error margin , by considering ž m. ž<Œµ`/=F;jÆ i accordingly with the optimum one, slightly reduces, since the
number of necessary relay nodes, that are the furthest vehicles
Figure 5 depicts the reliability (top) and redundancy (bottom)
in the coverage area, reduces as the density arises.
ratios with respect to the optimum strategy (left) and with
respect to the case with s and À·*
m (right). žÇÈ=
Observing the top right plot, it can be gathered that the B. Non-ideal Wireless Channel
introduction of an error margin m makes the ž 1Æ
s  ³H
" The previous section has highlighted some important dif-
system more reliable with respect to systems with higher ferences between the B EACONED and the B EACONLESS
beaconing frequency and without error margin (i.e., s, „X* approach: the former is the least redundant and the most
žÉ¶= m). Also, considering the bottom right plot, these performing in terms of delivering time, while the latter is
benefits come at the expense of a modest 10% increase on the the most reliable. However, these differences are marginal,
 TABLE I
Density ρ=20 [veh/km] Density ρ=40 [veh/km]
O PTIMUM , B EACONLESS AND B EACONED AVERAGE DELAY [ MS ] 1
BED: Bernoulli 0.9
BED: Transitional
BSS: Bernoulli 0.8
Density Optimum B EACONED B EACONLESS BSS: Transitional
0.7
[veh/Km] E=0m E=8m K=1 K=8

Accuracy Pinfo
0.6
5 39 41 38 84 131
20 58 59 60 214 303 0.5
50 47 54 50 271 419 0.4
0.3
0.2
0.1
since by tuning the algorithm parameters, the B EACONED
approach can be made more reliable (e.g., increasing ) and ž 0 0.1 0.2 0.3 0.4 0.5 0 0.1 0.2 0.3 0.4 0.5
0

the B EACONLESS less redundant (e.g., decreasing ). In order ² Average Loss Probability

to complete our comparative analysis of the two approaches Fig. 7. B EACONLESS (BSS ) and B EACONED (BED ) accuracy as a function
of wireless channel errors, for Transitional and Bernoulli channel models, at
we now introduce more realistic wireless channel models, so low (left) and high (right) vehicular density
that we can also assess the robustness of the two algorithms to
errors over the wireless channel. If not otherwise specified, we
consider the B EACONED strategy with s and ĵH m žXÆ
and the B EACONLESS with . ²ÖÆ notice that the B EACONLESS algorithm is far more robust
Let us now introduce two wireless channel models: in with respect to the B EACONED service irrespectively of the
the first one, the probability that a message is not correctly channel model. Indeed, even in the worst case, when half of the
×
received is Bernoulli with probability , independently from packets are lost due to wireless channel errors, more than half
the receiver distance from the transmitter. Conversely, in the of the vehicles are effectively warned by the B EACONLESS
second model the loss probability depends on the distance algorithm, whereas this percentage drops to less than one fifth
between transmitter and receiver: indeed, it is well known that when the B EACONED strategy is considered. The reason is
the electromagnetic signal degrades with the distance, and em- that for the B EACONLESS strategy packet losses have the
pirical studies [22], [23] show that a transitional region exists. effect of virtually reducing the density of the relay nodes,
We denote by @Ø ˆ  *I$ÙØ%9ˆ
the amplitude of the transitional region and and, thanks to the high redundancy, the effect of errors is
visible only at low density (e.g., 20 veh/Km) and high error
ii) within
 *Ú$ÛØzdˆ
we assume that: i) below
ˆ
communication is lossless,
and the packet loss probability sharply probabilities. The forwarding decision taken by B EACONED
ˆ
increases and iii) above , that is outside the transmission approach is instead based on nodes position estimate so as to
range, communication will certainly fail. In the following, we reduce redundancy; therefore, if error probability is large it can
usually refer to the average channel loss probability, which is easily translate in the interruption of the message propagation.
×
equal to and Øzˆ!{f;
for the Bernoulli and transitional channel Notice also that we consider the possibility that beaconing
respectively. Summarizing, messages too may be lost due to radio errors, leading to
a more imprecise neighborhood knowledge. Moreover, the
¨ß
@Ü%S ‰ ˜  Ý Þ × * ifif  ®ˆˆ
B EACONED strategy is not only affected by the loss amount,
but it is also sensitive to their “placement”: indeed, since the
L ¨ß« *U$¢Ø%9ˆ algorithm is very effective in selecting only the farther relay
NO = 
@à ‰ P  ˜ È
if
WY@á Y'â,ã‡ä if  ¨ß ˆ nodes, and since the transitional channel yields higher loss
* â>ä if
 *U®ˆ$mØ%9ˆX¡ probabilities at longer distances, the performance degradation
is more remarkable under the transitional channel model. On
The above models, despite their simplicity, allow a first the contrary, the performance of the B EACONLESS strategy is
grade inspection of the system behavior in presence of non- almost the same for the two channel models and it is driven
ideal wireless channels; besides, an advantage of this level only by the amount of losses.
of abstraction is that such models are not tied to a peculiar Given the non-ideality of the wireless channel, it is no
physical modulation, nor to a specific hardware platform, nor longer possible to devise an optimum centralized solution to
to a given environment, but are applicable to a more general the problem. We use as a reference the simple probabilistic
extent. Also, we point out that wireless channel models such as å –flooding strategy, regulating the access to the channel with
Gilbert’s [24], which introduce time-correlation in the wireless æ
the -p CSMA: when å Ì1ç
the system reliability is enforced,
channel, are not suited for our setup: indeed, since the message but at the price of a broadcast packet storm; conversely, by
propagation happens only once along a given channel, the å
lowering , to e.g. 1/2, the redundancy is halved at the expense
effect of the time-correlation is likely to be negligible. On of lower reliability. Figure 8 depicts, for a vehicular density
the contrary, we expect the effect of the space-correlation of Ô Ì·è,æ
´ veh/km, the reliability and redundancy of the
introduced by the transitional model to play a remarkable role. B EACONED strategy ( s with m and ÎGÌÐ s with ˳ÌVÍ ÎXÌ«ç
Figure 7 depicts, as a function of the average loss proba- ˬÌéæ m), the B EACONLESS and 1/2–flooding approaches
bility, the accuracy of the B EACONLESS and the B EACONED ç
normalized versus the –flooding performance for both the
algorithms, for two different values of the vehicular density, considered wireless channel models. Note that, although the
namely 20 veh/km (left plot) and 40 veh/km (right plot). First, B EACONLESS algorithm reduces the redundancy of about
 Hybrid Reliability Ratio Hybrid Redundancy Ratio
90
0.50
Transitional Channel Bernoulli Channel
1 80
3.00
Reliability Ratio

0.8 70

Hybridation Degree H [%]

2.50 0.40 8.00
0.6
2.00 60
flood1/2 6.00
BSS (K=8) 0.4
BED (B=1, E=0) 1.25 50
BED (B=5, E=8) 0.2 0.30 4.00
0 40
0.5 2.00 30
Redundancy Ratio

0.4
0.90 0.20 20
0.3 0.75
0.2 0.50 vs Beaconed 10
0.1
0.30 vs Beaconless
0
0 5 10 15 20 25 30 35 40 45 50 10 15 20 25 30 35 40 45 50
0.1 0.2 0.3 0.4 0.5 0.1 0.2 0.3 0.4 0.5
Vehicular Density ρ [km/hr]
Average Loss Probability Average Loss Probability
Fig. 9. Hybridating the B EACONLESS and B EACONED approaches: Relia-
Fig. 8. B EACONLESS (BSS ) and B EACONED (BED ) reliability (top) and
bility, redundancy contour plot as a function of the hybridation degree  and
redundancy (bottom) ratio over the 1-flooding algorithm, for Transitional (left)
the vehicular density 
and Bernoulli (right) channel models

60%–70%, its reliability is practically indistinguishable from weighted by a factor

þ that represents the hybridation degree.
ç–flooding. For instance, comparing the B EACONLESS to the
1/2–flooding strategy, observe that for the Bernoulli channel We run several simulations, considering different settings of
with ê¢ÌµæFë Ð
, the B EACONLESS approach successfully alerts the B EACONED and B EACONLESS algorithms, channel error
28% more vehicles using 8% less messages. Conversely, the models and probabilities, and different hybridation degrees
B EACONED approach reduces of about 95% the number of as well. In order to quantify the effectiveness of the hybrid
exchanged messages, but the system reliability drops signifi- solution, we report results for the Bernoulli channel with
cantly (slightly more than 20% in the worst case), and even packet loss probability . We consider s and êXÌ æFë Рθ̛Ð
the introduction of a safety error margin does not mitigate the Ë Ì Í m for the B EACONED approach, and for Ò Ì¶Í
effect of the wireless channel errors. the probabilistic rebroadcast function (2). Figure 9 depicts
the contour plot for the redundancy and reliability ratio of
C. To Beacon or Not To Beacon? the hybrid approach over both the pure-B EACONED and the
The previous sections highlighted that several tradeoffs exist pure-B EACONLESS algorithms, as a function of the vehicular
Ô
density and of the hybridation degree . For example, let
þ
between B EACONLESS and B EACONED approaches. However,
it is not possible to give a definite and unique answer to us focus on reliability (left plot). As expected, the hybrid
whether it is worth introducing a beaconing procedure or approach allows to greatly enhance reliability of B EACONED
not in the VANET context: indeed, different applications or (of even a factor of 3), in a way which is far more effective
services may prefer one solution or the other, depending than what was provided by the introduction of the error
on their specific requirements. For example, a road-safety Ô
margin. When  , it is possible to double the B EACONED >æ
service should implement a B EACONLESS algorithm, since its effectiveness (line labeled with 2.0 for the B EACONED) while
intrinsic redundancy guarantees high reliability and robustness achieving half of the B EACONLESS effectiveness (line labeled
to wireless channel error. On the contrary, when the safety of with 0.5 for the B EACONLESS). The curves diverge for Ô ý
the drivers in no longer endangered, the smaller overhead of >æ
 , where a higher hybridation degree is required to keep a
the B EACONED strategy may be preferred. factor 2 gain over the B EACONED approach. The hybridation
Another option consists in proposing hybrid solutions that required to achieve half of B EACONLESS reliability, instead,
trade-off among reliability, robustness and overhead. In hybrid sharply decreases as the vehicular density decreases, because
solutions, the decision of whether to relay the packet is for sparser networks connectivity and wireless errors dominate
taken by combining the decisions that the B EACONED and the performance of the algorithms. Figure 9 also suggests
þ
B EACONLESS approaches would take. Let and Î ì@íîmï/æFðç>ñ that the hybridation degree should not be kept constant
Î.òoò®îµï/æFðç>ñ
be the boolean random variables representing over all vehicular densities, rather it should be adaptively
the output of the decision processes of the B EACONED and adjusted to the traffic conditions. As an ongoing work, we
B EACONLESS algorithms, respectively. is set according Î)òoò are exploring the possibility to estimate the vehicle density
to the function ó¨ô˜õoöÚ÷–øFù
in (2). In the hybrid solution, the through the beaconing procedure so as to adaptively set the
two decisions are combined in the following way: the packet values of the hybrid strategy parameters: intuitively, whenever
þ ù|ÿmÎ òoò
is forwarded according to the boolean variable Î)ìIí+ú¢û–ô‡üÛý the estimated vehicular density is low, the hybridation degree
ü

, where is a uniform random number in . û æFðç should be higher and vice-versa.
In other words, the probability that the packet is forwarded in Finally, Figure 10 depicts the delay at the farmost informed
the B EACONED strategy is increased by the probability to be node as a function of the vehicular density for the Bernoulli
forwarded in the B EACONLESS strategy, and the last term is channel with ê«Ì æëÐ
for different hybridation percentages.
 140 one strategy or the other depending on their specific require-
ments. For example, by being more accurate and robust, the
120

Delay at Maximum Distance [ms]

B EACONLESS approach is suitable for road safety applica-
tions. Second, and most important, we showed that hybrid
100
approaches are a promising alternative, as they provide the
freedom of finely tuning the performance tradeoffs based on
80
the application needs.
60
R EFERENCES
H=75%
40 H=50% [1] Dedicated Short Range Communications (DSRC), http://www.
H=25% leearmstrong.com/DSRC/DSRCHomeset.htm
(BED) H=0% [2] eSafety Forum, http://europa.eu.int/information_
20
5 10 15 20 25 30 35 40 45 50 society/programmes/esafety/text_en.htm
[3] CarTALK2000, http://www.cartalk2000.net
Density ρ [veh/km] [4] Fleetnet, http://www.fleetnet.de
Fig. 10. Hybridating the B EACONLESS and B EACONED approaches: Delay [5] Q. Xu, T. Mak, J. Ko, R. Sengupta, “Vehicle-to-Vehicle Safety Messag-
at maximum distance, for different hybridation degrees  , as a function of ing in DSRC,” Proc. of ACM VANET’04, Page(s): 19-29, 2004
the vehicular density [6] B. Williams and T. Camp, “Comparison of Broadcast Techniques for
Mobile Ad Hoc Networks,” ’ Proc. of ACM MOBIHOC’02, Jun. 2002
[7] Y.C. Tseng, S.Y. Ni, E.Y. Shih, “Adaptive Approaches to Relieving
Broadcast Storms in a Wireless Multihop Mobile Ad Hoc Network,”
IEEE Transactions on Computers, May 2003, Vol. 52, No. 5
The picture not only confirms the small B EACONED delay, but [8] S.Y. Ni, Y.C. Tseng, Y.S. Chen, J.P. Sheu, “The broadcast storm problem
in a mobile ad hoc network,” ’ Proc. of ACM/IEEE MOBICOM’99, 1999.
it also shows that hybridation provides a mean for smoothly [9] G. Korkmaz, E. Ekici, F. Ozguner, U. Ozguner, “Urban Multi-Hop
tuning performance between the two orthogonal algorithms. Broadcast Protocol for Inter-Vehicle Communication Systems,” Proc.
of ACM VANET’04, Oct. 2004.
Also, it should be kept in mind that the delay performance is [10] E. Fasolo, R. Furiato, A. Zanella, “Smart Broadcast Algorithm for Inter-
very effective, since vehicles at the end of the relevant area vehicular Communications,” Proc. of WPMC’05, Sep. 2005.
[11] H. Fuessler, H. Hartenstein, J. Widmer, M. Mauve, W. Effelsberg,
-that is 2 Km away from the danger- are informed in a few Contention-Based Forwarding for Street Scenarios, Proc. of WIT’04,
tenths of second, when they thus had the chance of moving Mar. 2004.
of a few meters only. [12] M. Mauve, A. Widmer, H. Hartenstein, “A survey on position-based
routing in mobile ad hoc networks,” IEEE NetworkMagazine, Vol. 15,
Iss. 6, pp. 30-39, Nov.-Dec. 2001.
[13] B. Karp and H.T. Kung, “GPSR: Greedy Perimeter Stateless Routing for
VI. C ONCLUSION Wireless Networks,” Proc. of IEEE/ACM MOBICOM’00, Aug. 2000.
In this paper we explored the design space of broadcast [14] S. Basagni, I. Chlamtac, V.R. Syrotiuk, B.A. Woodward, “A distance
routing effect algorithm for mobility (DREAM),” Proc. of IEEE/ACM
communication services for VANETs, considering two kinds MOBICOM’98, Oct. 1998.
of algorithms: the B EACONLESS one, that relies solely on [15] J. LeBrun, C. Chuah, D. Ghosal, M. Zhang, “Knowledge-Based Oppor-
tunistic Forwarding in Vehicular Wireless Ad Hoc Networks,” Proc. of
instantaneous information on vehicles position, and the B EA - IEEE VTC’05, Jun. 2005.
CONED one, that maintains and exploits longer-term knowl- [16] H. Alshaer and E. Horlait, “An Optimized Adaptive Broadcast Scheme
for Inter-vehicle Communication,” Proc. of IEEE VTC’05, Jun. 2005.
edge of the vehicular network topology. [17] R. Fracchia, M. Meo and D. Rossi, “On the Impact of Traffic Models
By extensive simulation, we compared the different ap- on Inter-vehicular Broadcast Communications” Proc. of IEEE MedHoc-
Net’06, Jun. 2006
proaches under a realistic microscopic traffic model. Results [18] S. Panwai and H. Dia “Comparative Evaluation of Microscopic Car-
show that, in the case of ideal wireless channel, by prop- Following Behavior” IEEE Transaction on Intelligent Transportation
Systems, Vol. 6, No. 3, Sep. 2005
erly tuning the system parameters both algorithms accurately [19] B. S. Kerner, “Experimental features of the emergence of moving jams
propagate a broadcast message. Moreover, if the beaconing in free traffic flow,” J. Phys. A 33,, pp. 221-228, 2000.
[20] P.G. Gipps, “A behavioural car following model for computer simula-
overhead is neglected, the B EACONED approach is more tion,” Transportation Res. B, (15)1981, pp. 105–111.
efficient in terms of the channel utilization. Conversely, the [21] S. Krauß, P. Wagner. C. Gawron, “Metastable states in a microscopic
redundancy connatural to the probabilistic decision makes the model of traffic flow,”, Phy. Review E, (55)1998
[22] G. Anastasi, E. Borgia, M. Conti, E. Gregori and A. Passarella, “Un-
B EACONLESS algorithm intrinsically more robust with respect derstanding the real behavior of Mote and 802.11 ad hoc networks: an
to errors due to the wireless channel. experimental approach,” Pervasive and Mobile Computing (Elsevier),
vol. 1, Jul. 2005, pp. 237–256.
Two interesting conclusive considerations can be drawn. [23] M. Zuniga and B. Krishnamachari, “Analyzing the Transitional Region
First, it is not possible to clearly state a winner of the contest: in Low Power Wireless Links, ” Proc. of IEEE SECON’04, Oct. 2004.
[24] E.N. Gilbert, “Capacity of a burst-noise channel,” Bell Sysr. Tech. J., p.
indeed, different applications or services may prefer to use 1253, Sept. 1960.