Efficient Routing for Safety Applications in Vehicular Networks
METRANS Project DTRS98- G0019
March 2009
Konstantinos Psounis
Electrical Engineering
University of Southern California
Los Angeles, CA 90089
1 Disclaimer
The contents of this report reflect the views of the authors, who are responsible for the facts and the accuracy
of the information presented herein. This document is disseminated under the sponsorship of the Department
of Transportation, University Transportation Centers Program, and California Department of Transportation
in the interest of information exchange. The U. S. Government and California Department of Transportation
assume no liability for the contents or use thereof. The contents do not necessarily reflect the official views
or policies of the State of California or the Department of Transportation. This report does not constitute a
standard, specification, or regulation.
1
2 Introduction
Vehicular ad hoc networks have received a lot of attention in recent years. This attention is due to two rea-sons.
First and foremost, there are a number of real- life applications that become possible in the presence of
such an ad- hoc infrastructure. Examples include increasing road safety by reducing the number of accidents
as well as reducing their impact in case of non- avoidable accidents, improving local traffic ow and efficiency
of road traffic, and offering comfort and business applications to driver and passengers. Second, it is now
technically possible to build such a network. Recent developments in radios, coupled with signicant research
work in the area of mobile ad- hoc networks, make it likely to build such applications within five to ten years.
While there has been significant effort to define applications, see for example, the Car to Car Communi-cation
Consortium [ 1], the Vehicle Safety communications Project of the Department of Transportation [ 4],
and the PReVENT project [ 5], there are still some hard technical challenges that need to be resolved. Perhaps
the hardest of them all is how to achieve communication in an environment where network nodes ( vehicles)
move so fast that the very concept of a wireless link between two nodes is meaningless for time scales larger
than a few seconds, and where the density of the nodes can vary drastically in space and time, making the
network intermittently connected. The fast mobility renders any proactive routing protocols, that establish
end- to- end paths between sources and destinations, useless. The intermittent connectivity renders reactive
protocols, that establish end- to- end paths upon demand, non- applicable either.
To address this challenge, we propose using a new approach of routing that is tailored to the needs
of vehicular ad hoc networks and is termed as mobility- assisted routing. Mobility- assisted routing departs
drastically fromthe traditional view of networking: When a node ( moving vehicle or a static roadside station)
wants to send a message to one or more nodes ( vehicles), it may transmit a number of copies of the message
to one or more distinct relay nodes. Each relay will carry the message further, and may transmit it to a new,
better relay or directly to a destination.
The first routing protocol of that type that comes to mind is flooding, according to which whenever
two vehicles are within range, they exchange all messages that they dont have in common [ 41]. The main
argument for such an approach is that while flooding clearly wastes some network resources, the majority of
VANET applications require the messages to reach a large number of vehicles anyway. Further, since the
network can be disconnected, sending the data to everybody should reduce delivery delays. However, recent
studies have shown that flooding creates so much contention for the wireless channel, that its performance
is, in practice, quite bad. There have a been a number of attempts to alleviate this problem. In [ 33] the authors
examine a number of different schemes to suppress redundant transmissions after a message has been deliv-ered
by flooding. In [ 40, 43] a message is forwarded to another node with some probability smaller than one,
i. e. data is gossiped instead of flooded. In [ 14, 27– 29] simple methods to take advantage of the history of past
encounters are implemented in order to make fewer and more informed forwarding decisions than flooding. Fi-nally,
it has also been proposed that ideas fromnetwork coding could be useful to reduce the number of bytes trans-mitted
by flooding [ 42]. Although all these schemes, if carefully tuned, can improve to an extent the performance
of flooding, they are still flooding- based in nature, and thus often exhibit the same shortcomings as flooding [ 38,
39].
We propose a different approach than flooding that signicantly reduces its overhead, while achieving
good performance. The idea is to distribute only a bounded number of copies to a number of relay- vehicles,
each of which can then deliver it to the destination or to a new, better relay- vehicle. We refer to these schemes
as spraying- based schemes. Spraying schemes keep the number of transmissions small while exploiting the
speed of flooding.
To design the optimal spraying scheme, we address the following important questions:
( i) How many copies should a scheme spray: We analyze how to choose the number of copies sprayed
by a scheme to achieve a given delay. We derive analytical expressions expressing the expected delay
in terms of the network parameters, and discuss how to solve for the number of copies. In vehicular
2
networks, most of the times its not possible to know the network parameters like the number of cars
on the highway. So we also describe an online algorithm to estimate the network parameters. Finally,
to show that spraying schemes scale, we show that as the number of nodes in the network increases,
the percentage of nodes that need to become relays in spraying schemes, in order to achieve the same
relative performance, is actually decreasing.
( ii) How to route each copy: Once the copies have been sprayed, how does each relay route this copy
towards the destination. We propose the use of the single- copy utility- based scheme from [ 37] for
this purpose. Each node maintains a timer for every other node in the network, which records the
time elapsed since the two nodes last encountered each other. These timers are similar to the age of
last encounter in [ 17], and are useful, because they contain indirect ( relative) location information.
We show that using these timers or other similar utility functions to route each copy leads to significant
performance improvement in the context of vehicular networks. We also discuss how to modify the
utility functions to incorporate the presence of roadside stations which have been installed specifically
to help delivery in vehicular networks.
( iii) How to distribute copies: The choice of spraying method directly affects the expected delay of
spraying phase. Further, this delay is independent of the particular single- copy routing scheme that is
used to route each copy in the second phase. We first show that if node movements are independent
and identically distributed ( IID), then allowing each relay to give away half of its copies till it has only
one remaining is the optimal strategy. We label this strategy binary spraying. We then show that if node
movements are not IID, but instead, each node has an utility associated for each destination, then if this
utility function is also used to route each copy through a single copy utility- based scheme, then binary
spraying still remains the optimal strategy.
Up till now, we ignore contention in the analysis. Incorporating wireless contention complicates the
analysis significantly. This is because contention manifests itself in a number of ways, including ( i) finite
bandwidth which limits the number of packets two nodes can exchange while they are within range, ( ii)
scheduling of transmissions between nearby nodes which is needed to avoid excessive interference, and ( iii)
interference from transmissions outside the scheduling area, which may be significant due to multipath fad-ing
[ 8]. To analyze how do the answers to the previous three questions change if we incorporate contention,
we first propose a general framework to incorporate contention in the performance analysis of mobility-assisted
routing schemes for ICMNs while keeping the analysis tractable. We then use this framework to
derive delay expressions for spraying schemes and use these expressions to understand whether and how do
our previous results change?
Our objective is to design highly efficient routing schemes for vehicular ad hoc networks ( VANETs),
that are tailored to supporting real- life safety- related applications. Hence, we want to understand how the
proposed routing algorithms work with realistic vehicle mobility. To accomplish this goal, we first propose
a new mobility model which captures the essential characteristics of human- driven mobility. The proposed
model is a time- variant community mobility model, and is referred to as the TVC model. Using empirical
traces, we first show that the TVC model captures the statistics observed in vehicular traces. Then we
derive delay expressions for spraying based schemes for a specific instantiation of the proposed mobility
model. Finally, we use these expressions to show that spraying schemes achieve very good performance
with realistic vehicle mobility too.
We also propose a new protocol to enable one- to- many communication while suppressing duplicate
transmissions. Finally, we use showcase applications to demonstrate the applicability and efficacy of the
proposed protocols. The end- result of this work is a library of protocols, which we label spraying schemes,
which offer a reliable and efficient method of routing messages between vehicles and between vehicles and
roadside stations, and support a wide range of safety applications.
3
3 Optimal Design of Spraying Scheme
In this section, we discuss the problem of efficient routing in vehicular networks, and describe our proposed
solution, Spray routing. Our problemsetup consists of a number of nodes ( vehicles) moving inside a bounded
area ( city) according to a stochastic mobility model. Additionally, we assume that the network is discon-nected
at most times, and that transmissions are faster than node movement ( i. e. it takes less time to transmit
a message x meters far - ignoring queueing delay - than to carry it for the same distance) 1).
Our study of single- copy routing algorithms [ 37] showed that using only one copy per message is often
not enough to deliver a message with high reliability and relatively small delay in a vehicular network. On the
other hand, routing too many copies in parallel, as in the case of flooding- based schemes ( e. g. epidemic rout-ing
or gossiping), can often have disastrous effects on performance [ 26]. The total transmissions performed
by epidemic routing are orders of magnitude higher than those performed by an optimal scheme. So, under
low traffic loads epidemic routing achieves close to optimal delays, but as the traffic input increases it begins
to suffer severely from contention and its delay very quickly increases.
Based on these observations, we have identified the following desirable design goals for a routing proto-col
in vehicular networks. Specifically, an efficient routing protocol in this context should:
• perform significantly fewer transmissions than flooding- based routing schemes, under all conditions.
• generate low contention, especially under high traffic loads.
• deliver a message faster than existing single and multi- copy schemes, and exhibit close to optimal
delays.
• deliver the majority of the messages generated;
Additionally, we would like this protocol to also be:
• highly scalable, that is, maintain the above performance behavior despite changes in car density.
• simple, and require as little knowledge about the network as possible, in order to facilitate its imple-mentation.
3.1 Spray andWait
Since too many transmissions are detrimental on performance, especially as the network size increases, the
proposed protocol, Spray and Wait, distributes only a small number of copies each to a different relay. Each
copy is then “ carried” all the way to the destination by the designated relay.
Binary Spray and Wait Binary Spray and Wait routing consists of the following two phases:
• spray phase: for every message originating at a source node, L message copies are initially spread to
L distinct relays. The source of a message initially starts with L copies; any node A that has n > 1
message copies ( source or relay), and encounters another node B ( with no copies), it hands over to B
⌊ n / 2 ⌋ of its copies and keeps ⌈ n / 2 ⌉ for itself; when it is left with only one copy, it switches to the wait
phase.
• wait phase: if the destination is not found in the spraying phase, each of the L nodes carrying a mes-sage
copy performs “ Direct Transmission” [ 37] ( i. e. will forward the message only to its destination).
1This is reasonable assumption with modern wireless devices. Assume, for example, that a node has a range of 100 m and a radio
of 1 M b p s rate. Then, it could send a packet of 1 K B at a distance of 100 m in only 8 m s . Even if that node is a fast moving car with a
speed of say 65 m p h , it could carry the same packet at a mere distance of less than 1 m in the same 8 m s .
4
Binary Spray and Wait decouples the number of transmissions per message from the total number of
nodes. Thus, transmissions can be kept small and essentially fixed for a large range of scenarios. Addi-tionally,
its mechanism combines the speed of epidemic routing with the simplicity and thriftiness of direct
transmission. Initially, it “ jump- starts” spreading message copies quickly in a manner similar to epidemic
routing. However, it stops when enough copies have been sprayed to guarantee that at least one of them
will reach the destination, with high probability. Since cars move quickly around the network and “ cover”
a sizeable part of the network area in a given trip, we will show that only a small number of copies can create
enough diversity to achieve close- to- optimal delays.
As we mentioned earlier, the basic idea behind Binary Spray and Wait ( i. e. extending the 2- hop scheme
of [ 20] to introduce more than one relays) is relatively simple and has been identified as beneficial by other
researchers also [ 15, 31, 33]. However, a number of important questions need to be answered first, before
the desirable performance can be achieved: ( i) How many copies should a scheme spray? ( ii) How should
these copies be distributed to different vehicles and roadside stations, i. e is it possible to do better than binary
spraying? ( iii) How should each of these copies be routed, i. e. is waiting for the destination after spraying the
best strategy?
3.2 Deciding the Right Number of Copies
In this section, we analyze how to choose the number of copies used ( denoted by L ) in order to achieve a
specific expected delay. Let us assume that there is a specific delivery delay constraint to be met. One
reasonable way to express such a constraint would be as a factor a times the optimal delay E D o p t ( a > 1 ),
since this is the best that any routing protocol could do2.
We first state theorems which express the expected delay of optimal routing and spray and wait in terms
of the network parameters. Throughout this section, we will be making the following assumptions:
Network: M nodes move on a √ N × √ N 2- dimensional torus. Each node can transmit up to distance
K ≥ 0 meters away, where K /√ N is much smaller than the value required for connectivity [ 22], and each
message transmission takes one time unit.
MobilityModels: We assume that all nodes move according to some stochastic mobility model (“ MM”).
We next define a mobility property. The statistics of this property will be used in the expected delay expres-sions
for different routing scheme.
Meeting Time Let nodes i and j move according to a mobility model ‘ mm’ and start from their stationary
distribution at time 0 . Let X i ( t ) and X j ( t ) denote the positions of nodes i and j at time t . The meeting time
( M m m ) between the two nodes is defined as the time it takes them to first come within range of each other,
that is M m m = m i n t { t : k X i ( t ) − X j ( t ) k ≤ K }.
We assume that the “ meeting times” of the mobility model “ mm” is approximately exponentially dis-tributed
or has an exponential tail, with expected meeting time equal to E M m m . It has been shown that a
number of popular mobility models like Random Walk [ 9], Random Waypoint and Random Direction [ 33,
35], as well as more realistic, synthetic models which are suitable to model contacts between moving ve-hicles
[ 24] exhibit such ( approximately) exponential encounter characteristics. Therefore, the subsequent
analysis and algorithms of this and the following section apply to all these models.
Contention: Throughout our analysis we assume that bandwidth and buffer space are infinite. In other
words, we assume that there is no contention for these resources. Later sections address how do the results
presented in this section after incorporating contention in the analysis.
The following theorem states the expected delivery time of the optimal algorithm.
2By this, we do not assume that E D o p t is always known to the user. If E D o p t is not known a could still be used as a measure of
how “ aggressive” the protocol should be.
5
Theorem 3.1 The expected message delivery time of the optimal algorithm E D o p t is given by
E D o p t =
H M − 1
( M − 1 )
E D m m , ( 1)
where H k is the k th Harmonic Number, i. e, H k = P k
i = 1
1
i =  ( l o g k ) .
We next state the expected end- to- end delay of Binary Spray and Wait. After the L copies have been
sprayed, each of the L relays will independently look for the destination to directly deliver the message ( if the
latter has not been found yet). We first state the delay of the wait phase in the following Lemma.
Lemma 3.1 Let E W denote the expected duration of the “ wait” phase, if needed, and let E M m m denote the
expected meeting time under the given mobility model. Then, E W is given by
E W =
E M m m
L
. ( 2)
The following theorem calculates the expected delivery time of Binary Spray and Wait. It defines a
system of recursive equations that calculates the ( expected) residual time after i copies have been spread,
in terms of the time until the next copy( i + 1 ) is distributed, plus the remaining time thereafter. It is important
to note that the following result is generic. By plugging into the equations the appropriate meeting time value
E M m m , we can calculate the expected delay of Spray and Wait for the respective mobility model [ 35].
Theorem 3.2 Let E D s w ( L ) denote the expected delay of the Binary Spray and Wait algorithm, when L
copies are spread per message. Let further E D ( i ) denote the expected remaining delay after i message
copies have been spread. Then, E D ( 1 ) ≈ E D s w ( L ) , where E D ( 1 ) can be calculated by the following
system of recursive equations:
E D ( i ) =
E M m m
i ( M − i )
+
M − i − 1
M − i
E D ( i + 1), i 2 » 1,
L
2 –;
E D ( i ) =
E D m m
i ( M − i )
+
M − i − 1
M − i „ 2 i − L
i
E D ( i ) +
L − i
i
E D ( i + 1) « , for i 2 » L
2
+ 1, L − 1–;
E D ( L ) = E W =
E M m m
L
.
The above result, albeit quite useful in accurately predicting the performance of Binary Spray and Wait,
is not in closed form. This makes it difficult to theoretically compare the performance of Binary Spray and
Wait to that of the optimal scheme, or to calculate the number of copies to be used in closed form. For this
reason, in the following lemma we also derive an upper bound that is in closed form, by assuming that Source
Spray and Wait is performed, that is, only the source can forward a new copy. Note that Source Spray and
Wait always has a larger delay than Binary Spray and Wait.
Lemma 3.2 The following upper bound holds for the expected delay of Binary Spray and Wait:
E D s w ≤ ( H M − 1 − H M − L ) E M m m +
M − L
M − 1
E W , ( 3)
where H n is the n th Harmonic Number, i. e, H n = P n
i = 1
1
i =  ( l o g n ) .
This bound is tight for a small L / M ratio, but becomes pessimistic as this ratio grows larger. This
is because the bound basically includes the full time until all copies are spread, regardless of whether the
destination is found in one of the initial steps of the spraying phase. However, when the number of copies is
6
Table 1: minimum L to achieve expected delay
a 1.5 2 3 4 5 6 7 8 9 10
recursion 21 13 8 6 5 4 3 3 3 2
bound N. A. N. A. 11 7 6 5 4 3 3 2
taylor N. A. N. A. 10 7 5 4 3 3 3 2
much smaller than the total number of nodes ( which is the case of most interest) this bound is very useful
when tuning the performance of Spray and Wait.
The following lemma states that the required number of copies only depends on the number of nodes, and
is straightforward to prove from Eq.( 3) or Theorem 3.2.
Lemma 3.3 The minimum number of copies L m i n needed for Binary Spray and Wait to achieve an expected
delay at most a E D o p t is independent of the mobility model, the size of the network N , and transmission
range K , and only depends on a and the number of nodes M .
The required number of copies L m i n ( M ) for Binary Spray and Wait to achieve a desired expected
delay can be calculated in any of the following three ways: ( i) solve the system of equations of Theorem 3.2
for increasing L , until E D s w ( L ) < a E D o p t , or ( ii) solve the upper bound equation Eq.( 3) for L , by letting
E D s w = a E D o p t , and taking ⌈ L ⌉, or ( iii) approximate the harmonic number H M − L in Eq.( 3) with its Taylor
Series terms up to second order, and solve the resulting third degree polynomial:
( H 3
M − 1.2) L 3 + ( H 2
M −
 2
6
) L 2 + „ a +
2 M − 1
M ( M − 1) « L =
M
M − 1
, ( 4)
where H r n
= P n
i = 1
1
i r is the n th Harmonic number of order r .
Method ( i) is obviously the most accurate one. However, it is also the most cumbersome. Since the upper
bound of Eq.( 3) is tight for small L / M values, if the delay constraint a is not too tight, we can use method ( ii)
or ( iii) to quickly get a good estimate for L m i n .
In Table 1 we compare results for L m i n , as calculated with each of these three methods for different
values of a . We assume the number of nodes M equals 1 0 0 . ‘ N. A’ stand for ‘ Non Available’ and means that
such a low delay value is never achievable by the bound. As can be seen in this table the L found through the
approximation is quite accurate when the delay constraint is not too stringent.
3.2.1 Estimating L when Network Parameters are Unknown
Throughout the previous analysis we’ve assumed that network parameters, like the total number of nodes
M , are known. This assumption might be valid in networks operated by a single authority ( e. g. sensor
networks), however, this assumption will not hold for vehicular networks. So, we next describe how to
produce and maintain good estimates of necessary network parameters, like M , and adapt L accordingly.
This problem is difficult in general. A straightforward way to estimate M would be to count unique IDs
of nodes encountered already. However, this method requires a large database of node IDs to be maintained
in large networks, and a lookup operation to be performed every time any node is encountered. Furthermore,
although this method converges eventually, its speed depends on network size and could take a very long
time in large disconnected vehicular networks. A better alternative is to produce an estimate of M by taking
advantage of inter- meeting time statistics. Specifically, let us define T 1 as the time until a node ( starting from
the stationary distribution) encounters any other node. It is easy to see from Lemma 3.2 that T 1 is exponen-tially
distributed with average T 1 = E M m m / ( M − 1 ) . Furthermore, if we similarly define T 2 as the time
until two different nodes are encountered, then the expected value of T 2 equals E M m m  1
M − 1 + 1
M − 2  .
Cancelling E M m m from these two equations we get the following estimate for M :
7
ˆ M
=
2 T 2 − 3 T 1
T 2 − 2 T 1
. ( 5)
Estimating M by the procedure above presents some challenges in practice, because T 1 and T 2 are en-semble
averages. Since hitting times are ergodic [ 9], a node can collect sample intermeeting times T 1 , k and
T 2 , k and calculate time averages ˆ T 1 and ˆ T 2 instead. However, the following complication arises: when a node
i meets another node j , i and j become coupled [ 18]; in other words, the next intermeeting time of i and j
is not anymore exponentially distributed with average E M m m . In order to overcome this problem, each node
keeps a record of recently encountered nodes. Every time a new node is encountered, it is stamped as “ cou-pled”
for an amount of time equal to the mixing or relaxation time for that graph, which is the expected time
until a node starting from a given position arrives to its stationary distribution [ 9]. Then, when node i mea-sures
the next sample intermeeting time, it ignores all nodes that it’s coupled with at the moment, denoted as
c k , and scales the collected sample T 1 , k by M − c k
M − 1 . A similar procedure is followed for ˆ T 2 . Putting it alto-gether,
after n samples have been collected:
ˆ T 1 =
1
n
n
X k = 1  M − c k
M − 1  T 1 , k ,
ˆ T 2 =
1
n
n
X k = 1   M − c k − 1
M − 1  T 1 , k − 1 +  M − c k
M − 2  T 1 , k  .
Replacing ˆ T 1 and ˆ T 2 in Eq.( 5) we get a current estimate of M . As can be seen by Eq.( 5), the estimator for
M is sensitive to small deviations of T 1 and T 2 from their actual values. Therefore it is useful for a node
to also maintain a running average of M . Specifically, the running estimate ˆ M
is updated with every new
estimate ˆ M
n e w as ˆ M
=  ˆ M
+ ( 1 −  ) ˆ M
n e w ( 0 <  < 1 , with values closer to 1 providing better stability).
We could now use this estimate of M to calculate the number of copies using one of the previous methods.
Figure 1 shows how the online estimate ˆ M
, calculated with our proposed method, quickly converges to
its actual value for a 2 0 0 × 2 0 0 network with 2 0 0 nodes, for both the random walk and random way-point
models, again validating the generality of our expressions. ( Note that even in this small scenario,
our method’s convergence is more than two times faster than ID- counting.) Finally, both our method and
ID- counting could take advantage of indirect information learning, where nodes exchange known unique IDs
or independently collected samples to speed up convergence.
We believe that similar estimators could potentially be constructed for other network parameters or
statistics, as well, ( e. g. approximate network area N , or various moments for encounter times) which could
be used to provide users with predictions of the service level available. We intend to look further into this
issue in future work.
3.3 Scalability of Spray andWait
Having shown how to find the minimum number of copies L m i n to achieve a delay at most a times the
optimal, it would be interesting, from a scalability point of view, to see how the percentage L m i n / M of
nodes that need to receive a copy behaves as a function of M . The reason for this is the following: If
we assume a large enough TTL ( time- to- live) value is used, flooding- based schemes will eventually give a
copy to every node and therefore perform at least M transmissions. Increased contention and the resulting
retransmissions will obviously increase this value significantly. On the other hand, Spray andWait performs
L transmissions, and produces very little contention compared to flooding- based schemes. Consequently,
the number of transmissions that Spray and Wait performs per message is at most a fraction L m i n / M of the
number of transmissions per message epidemic and other flooding- based schemes perform.
8
Estimation of M - Random Walk
0
100
200
300
400
0 1000 2000 3000 4000
number of samples
M value
Actual M = 200
Estimated M
Estimation of M - Rand. Waypoint
0
100
200
300
400
0 1000 2000 3000 4000
number of samples
M value
Actual M = 200
Estimated M
Figure 1: Online estimator of number of nodes ( M )— N = 2 0 0 × 2 0 0 , transmission range = 0 ,  = 0 . 9 8 ,
mixing time = 4 0 0 0 .
In Figure 2 we depict the behavior of L m i n / M as a function of M for different values of a . It is important
to note there that, as the number of nodes in the network increases, the percentage of nodes that need to
become relays in Spray and Wait, in order to achieve the same relative performance, is actually decreasing.
The intuition behinds this interesting result is the following: when L ≪ M the delay of Spray and Wait is
dominated by the delay of the wait phase; in that case, if L / M is kept constant, the delay of Spray and Wait
decreases roughly as 1 / M ( as M → ∞). On the other hand, the delay of the optimal scheme ( and also the
spraying delay) decreases more slowly as l o g ( M ) / M [ 34]. The following Lemma formally states the result.
Percentage of Nodes Receiving a Copy
0
2
4
6
8
10
12
14
100 1000 10000 100000
Number of Nodes ( M)
percentage (%)
 = 2
 = 5
 = 10
Figure 2: Required percentage of nodes L m i n / M receiving a copy for spray and wait to achieve an expected
delay of a E D o p t
Lemma 3.4 Let L / M be constant and let L ≪ M . Let further L m i n ( M ) denote the minimum number of
copies needed by Spray and Wait to achieve an expected delay that is at most a E D o p t , for some a . Then
L m i n ( M )
M is a decreasing function of M .
This behavior of L m i n / M implies that Spray and Wait is extremely scalable. While, usually, the perfor-mance
of many schemes ( including flooding- based ones, in our case) deteriorates as the number of nodes
increase, the relative performance of Spray andWait improves, making its performance advantage even more
9
pronounced in large networks. This property is a must for a vehicular network in a large metropolitan area
like Los Angeles, where the number of vehicles is expected to be very large.
3.4 Routing Each Copy Separately - “ Spray and Focus” Routing
Although Binary Spray and Wait combines simplicity and efficiency, it can be optimized further. Consider
a vehicular network in which vehicles move closely within separate, and often sparsely located groups. In
such situations, partial paths may exist over which a message copy could be quickly transmitted closer to
the destination. Yet, in Spray andWait a relay with a copy will naively wait until it moves within range of the
destination itself. This problem could be solved if some other single- copy scheme is used to route a copy
after it’s handed over to a relay, a scheme that takes advantage of transmissions ( unlike Direct Transmission).
We propose the use of the single- copy utility- based scheme from [ 37] for this purpose. Each node main-tains
a timer for every other node in the network, which records the time elapsed since the two nodes last
encountered each other3 ( i. e. came within transmission range). These timers are similar to the age of last en-counter
in [ 17], and are useful, because they contain indirect ( relative) location information. Specifically, for
a large number of vehicular mobility models, it can be shown that a smaller timer value on average implies a
smaller distance from the node in question. Further, we use a “ transitivity function” for timer values ( see
details in [ 37]), in order to diffuse this indirect location information much faster than regular last encounter
based schemes [ 17]. The basic intuition behind this is the following: in most situations, if node B has a small
timer value for node D , and another node A ( with no info about D ) encounters node B , then A could safely
assume that it’s also probably close to node D . We assume that these timers are the only information available
to a node regarding the network ( i. e. no location info, etc.).
We have seen in [ 37] that appropriately designed utility- based schemes, based on these timer values, have
very good performance in scenarios were mobility is low and localized. This is the exact situation were Spray
and Wait loses its performance advantage. Therefore, we propose a scheme were a fixed number of copies
are spread initially exactly as in Spray and Wait, but then each copy is routed independently according to
the single- copy utility- based scheme which uses a utility function based on these timers. We call our second
scheme Spray and Focus.
Spray and Focus Spray and Focus routing consists of the following two phases:
• spray phase: for every message originating at a source node, L message copies are initially spread – by
binary spraying – to L distinct “ relays”.
• focus phase: let U X ( Y ) denote the utility of node X for destination Y; a node A, carrying a copy for
destination D, forwards its copy to a new node B it encounters, if and only if U B ( D ) > U A ( D ) + U t h ,
where U t h ( utility threshold) is a parameter of the algorithm.
3.4.1 Evaluation of Spraying Schemes
We have used a custom discrete event- driven simulator to evaluate and compare the performance of differ-ent
routing protocols under a variety of mobility models and under contention. A slotted collision detection
MAC protocol has been implemented in order to arbitrate between nodes contenting for the shared chan-nel.
The routing protocols we have implemented and simulated are the following: ( 1) Epidemic routing
(“ epidemic”), ( 2) Randomized flooding with p = ( 0 . 0 2 − 0 . 1 ) (“ random- flood”), ( 3) Utility- based flooding
(“ utility- flood”), ( 4) Optimal ( binary) Spray andWait (“ spray& wait”), ( 5) Spray and Focus (“ spray& focus”),
( 6) Seek and Focus single- copy routing (“ seek& focus”) [ 34], and ( 7) Oracle- based Optimal routing (“ opti-mal”).
( We will use the shorter names in the parentheses to refer to each routing scheme in simulation plots.)
3In practical situations, each node would actually maintain a cache of the most recent nodes that it has encountered, in order to
reduce the overhead involved in a large network.
10
We choose the number of copies L for Spray and Wait according to the theory of Section 3.1. ( Specifi-cally,
such that the delay of Spray and Wait would be about 2 × that of the Oracle- based Optimal if the
nodes were performing random walks.) For Spray and Focus and all other protocols we have tried to tune
their parameters in each scenario separately, in order to achieve a good transmissions- delay tradeoff. Finally,
in all schemes that use a utility function, including Utility- based flooding, we have used our own utility func-tion
proposed in [ 37], which has been shown to perform better than existing utility functions [ 29] for most
mobility models.
We first evaluate the effect of traffic load on the performance of different routing schemes ( Scenario A).
We then examine their performance as the level of connectivity changes ( Scenario B).
Scenario A - Effect of Traffic Load: 1 0 0 nodes move according to the random waypoint model [ 13] in a
5 0 0 × 5 0 0 grid with reflective barriers. The transmission range K of each node is equal to 1 0 . Finally, each
node is generating a new message for a randomly selected destination with an increasing rate resulting in
average traffic loads ( total number of messages generated throughout the simulation) from 2 0 0 ( low traffic)
to 1 0 0 0 ( high traffic).
Fig. 3 depicts the performance of all routing algorithms, in terms of total number of transmissions and
average delivery delay. Epidemic routing performed significantly more transmissions than other schemes
( from 5 6 0 0 0 to 1 4 4 0 0 0 ), and at least an order of magnitude more than Spray and Wait. Therefore, we do
not include it in the transmission plots, in order to better compare the remaining schemes. We also depict two
plots for Spray andWait for two different L values, in order to gain better insight into the transmissions- delay
tradeoffs involved. Finally, note that, in this scenario, Spray and Focus had similar performance with Spray
and Wait, and thus we don’t include results for it. In the next section, we will see in detail scenarios where
Spray and Focus can significantly improve the performance of Spray and Wait.
As is evident by Fig. 3, Spray and Wait outperforms all single and multi- copy protocols discussed and
achieves its performance goals set at the start of this section. Specifically: ( i) under low traffic its delay
is similar to Epidemic routing and is 1 . 4 − 2 . 2 times faster than all other multi- copy protocols; it performs
an order of magnitude less transmissions than Epidemic routing, and 5 − 6 times less transmissions than
Randomized and Utility- based, and ( ii) under high traffic it retains the same advantage in terms of total
transmissions, and outperforms all other protocols, in terms of delay, by a factor of 1 . 8 − 3 . 3 .
As a final note, the delivery ratio of almost all schemes in this scenario was above 9 0 % for all traffic
loads, except that of Seek and Focus which was about 7 0 % , and that of Epidemic routing which plummeted
to less than 5 0 % for very high traffic, due to severe contention.
0
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
Total Transmissions
random- flood
utility- flood
seek& focus
spray& wait( L= 10)
spray& wait( L= 16)
0
500
1000
1500
2000
2500
3000
3500
4000
4500
epidemic
random flood
utility flood
spray& wait( L= 10)
spray& wait( L= 16)
seek& focus
Delivery Delay ( time units)
Increasing traffic
Increasing traffic
Figure 3: Scenario A - performance comparison of all routing protocols under varying traffic loads.
Scenario B - Effect of Connectivity: In this scenario, the size of the network is 2 0 0 × 2 0 0 and the traffic
load is medium. We would like to evaluate the performance of all protocols in networks with a large range
11
of connectivity characteristics, ranging from very sparse, highly disconnected networks, to almost connected
networks.
Before we proceed, it is necessary to define a meaningful connectivity metric. Although a number of
different metrics have been proposed ( for example [ 16]), no widespread agreement exists, especially if one
needs to capture both disconnected and connected networks. We believe that a meaningful metric for the net-works
of interest is the expected maximum cluster size defined as the percentage of total nodes in the largest
connected component ( cluster). This indicates what percentage of nodes have already conglomerated into the
connected part of the network, with “ one” implying a regular connected network ( with high probability).
The above connectivity metric measures “ static” connectivity. It indicates how connected a random
snapshot of the connectivity graph will be. However, in situations where mobility is exploited to deliver
traffic end- to- end, “ dynamic” connectivity also plays an important role on performance. Dynamic connec-tivity
can be seen as a measure of how many new nodes are encountered by a given node within some time
interval. If nodes move in an IID manner, this is directly tied to the mixing time for the graph representing the
network [ 9]. The larger the mixing time, the more “ localized” the node movement, and the longer it will take
a node to carry a message to a remote part of the network.
In order to evaluate the effect of dynamic connectivity on different protocols, we present two sets of
results, one where nodes move according to the random waypoint model and one where nodes perform
random walks. The random waypoint has one of the fastest mixing times (  ( √ N ) ), while the random walk
has one of the slowest (  ( N ) ) [ 9]. Furthermore, for each mobility model we vary the transmission range K
to span the entire static connectivity range.
Figure 4 and Figure 5 depict the number of transmissions and the average delay for the random waypoint
and the random walk scenarios, respectively, as a function of transmission range ( respective connectivity
values are shown in the parentheses).
There are a number of interesting things to notice about these plots. First, although Randomized and Util-ity
Flooding can improve the performance of epidemic routing they still have to perform way too many trans-missions
to achieve competitive delays. Further, when nodes move according to the random waypoint model,
Spray and Wait outperforms all protocols, in terms of both transmissions and delay, for all levels of connec-tivity.
Its performance is close to the optimal, and thus Spray and Focus cannot offer any improvement. On
the other hand, when nodes perform random walks, Spray and Wait may exhibit large delays, if the network
area is large enough. Here the few copies are spread locally, and then each custodian takes a very long time to
traverse the network and reach the destination. Even if the number of copies were increased, it would be the
spraying phase that would take a long time, since new nodes are found very slowly. Spray and Focus can
overcome these shortcomings and excel ( when the network is not too sparse), achieving the smallest delay
with only a few extra transmissions. Note though that despite the better utility function used, Utility Flooding is
still plagued by its flooding nature and choice of threshold. This problemwas even more pronounced when other
existing utility functions were used.
Finally, both Spray and Wait and Spray and Focus are quite scalable and robust, compared to other
multi- copy or even single- copy options. Epidemic routing and the rest of the schemes manage to achieve a
delay that is comparable to the spraying schemes for very few connectivity values only, but perform quite
poorly for the vast majority of scenarios. Spray and Wait and Spray and Focus, on the other hand, exhibit
great stability. They performs few transmissions across all scenarios, while achieving a delivery delay that
decreases as the level of connectivity increases, as one would expect.
3.5 Distributing Copies
In this section, we study how to distribute these L copies. The choice of spraying method directly affects
the expected delay of spraying phase. Further, this delay is independent of the particular single- copy routing
scheme that is used to route each copy in the second phase.
12
0
50
100
150
200
epidemic
utility- flood
random- flood
spray& wait
spray& focus
Transmissions ( thousands)
K = 5 ( 2.5%)
K = 10 ( 4.4%)
K = 20 ( 14.9%)
K = 30 ( 68%)
K = 35 ( 92.5%)
0
500
1000
1500
2000
epidemic
utility- flood
random- flood
spray& wait
spray& focus
Delivery Delay ( time units)
Figure 4: Scenario B - RandomWaypoint Mobility: Total transmissions and delay as a function of transmis-sion
range K ( respective connectivity values are shown in parentheses).
0
10
20
30
40
50
60
70
utility- flood
random- flood
spray& wait
spray& focus
Transmissions ( thousands)
K = 15 ( 7.8%)
K = 20 ( 14.9%)
K = 25 ( 35.9%)
K = 30 ( 68%)
K = 35 ( 92.5%)
0
500
1000
1500
2000
2500
3000
epidemic
utility- flood
random- flood
spray& wait
spray& focus
Delivery Delay ( time units)
Figure 5: Scenario B - Random Walk Mobility: Total transmissions and delay as a function of transmission
range K ( respective connectivity values are shown in parentheses).
13
We first state the following theorem which formally shows that binary spraying is optimal when node
movement is independent and identically distrbuted ( IID).
Theorem 3.3 When all nodes move in an IID manner, Binary Spraying minimizes the expected time until all
copies have been distributed.
Proof: Let us call a node “ active” when it has more than one copies of a message. Let us further define a
spraying algorithm in terms of a function f : N → N as follows: when an active node with n copies
encounters another node, it hands over to it f ( n ) copies, and keeps the remaining n − f ( n ) . Any spraying
algorithm ( i. e. any f ) can be represented by the following binary tree with the source as its root: assign the
root a value of L ; if the current node has a value n > 1 create a right child with a value of n − f ( n ) and a left
one with a value of f ( n ) ; continue until all leaf nodes have a value of 1 .
A particular spraying corresponds then to a sequence of visiting all nodes of the tree. This sequence is
random. Nevertheless, on the average, all tree nodes at the same level are visited in parallel. Further, since
only active nodes may hand over additional copies, the higher the number of active nodes when i copies
are spread, the smaller the residual expected delay until all copies are spread. Since the total number of tree
nodes is fixed ( 2 1 + l o g L − 1 ) for any spraying function f , it is easy to see that the tree structure that has the
maximum number of nodes at every level, also has the maximum number of active nodes ( on the average) at
every step. This tree is the balanced tree, and corresponds to Binary Spraying. 2
Now, if the node movements are not IID, but instead, each node has an utility associated for each destina-tion,
which is the most common case in vehicular networks, how does the spraying phase gets modified? We
first find the optimal spraying policy under the following set of assumptions, and later discuss what do our
results imply for general vehicular networks.
( i) M nodes perform independent random walks on a √ N × √ N 2D torus ( finite lattice). Each node
moves one grid unit in one time unit.
( ii) Each node can transmit up to K ≥ 0 grid units away, where K p N
is much smaller than the value
required for connectivity [ 22]. We use Manhattan distance d a b = k a x − b x k + k b x − b y k to measure
proximity between two positions a and b ( or between two nodes).
( iii) There is no contention in the network. In other words, the buffer space is infinite, and any communicat-ing
pair of nodes do not interfere with any other simultaneous transmission.
( iv) Let the number of copies distributed by the spraying based schemes be denoted by L .
We next state a lemma which will be used in the derivation of the optimal spraying policy.
Lemma 3.5 Let E [ M ( d ) ] denote the expected time until two independent random walks, starting at a dis-tance
d from each other, first meet each other. E [ M ( d ) ] can be derived by solving the following set of linear
equations:
E [ M ( d ) ] =   
p d , d − 2 E [ M ( d − 2 ) ] + p d , d
E [ M ( d ) ] + p d , d + 2 E [ M ( d + 2 ) ]
d > K
0 d ≤ K
, ( 6)
where p d 1 , d 2 denotes the probability that the two walks are at a distance d 2 from each other in the next
time slot given they are at a distance d 1 from each other in the current time slot and, for d 1 > 3 , it equals
 
  
1 6 d 1 − 2 0
6 4 d 1
d 2 = d 1 − 2
1 6 d 1 + 1 2
6 4 d 1
d 2 = d 1 + 2
3 2 d 1 + 8
6 4 d 1
d 2 = d 1
, for d 1 = 3 , it equals   
7
4 8 d 2 = 1
1 5
4 8 d 2 = 5
2 6
4 8 d 2 = 3
, for d 1 = 2 , it equals   
3
3 2 d 2 = 0
1 1
3 2 d 2 = 4
1 8
3 2 d 2 = 2
,
for d 1 = 1 , it equals 7
1 6 and 9
1 6 for d 2 = 3 and d 2 = 1 respectively and for d 1 = 0 , it equals 4
1 6 and 1 2
1 6 for
d 2 = 2 and d 2 = 0 respectively.
14
Now we present an algorithm which will answer the following question: ‘ Two nodes A and B are
within range of each other and A has l ≤ L copies of a packet while B has none. The utility of both the
nodes is known. Then how many of the l copies should A give to B such that the expected delivery delay is
minimized.’ Before we proceed, we first specify the utility function we will use. Amongst the different utility
functions used in the literature ( see [ 34]), we choose ‘ the distance to the destination’ for our analysis.
Now we derive the algorithm to find the optimal spraying policy. Let a node ( label it node A ) be a
distance d from the destination and has l copies of the packet. Let D ( d , l ) denote the time this node will
take to deliver the packet to the destination. In the future time slots, either one of the following two events can
happen first: ( i) E 1 : Node A meets the destination and delivers the packet. ( ii) E 2 : Node A meets one of the
potential relays. Let the time duration elapsed till event E i occurs be denoted by T i , i = 1 , 2 . By definition,
T 1 is exponentially distributed with mean E [ M ( d ) ] . To derive the distribution of T 2 , we use the fact that the
time it takes to meet one particular relay node is exponentially distributed with mean E [ M ] , where E [ M ] is
the expected meeting time of two random walks. T 2 is the minimum of M 4 such exponentials which
is also an exponential with mean E [ M ]
M . Thus, the time duration till one of these two events occur is equal
min ( T 1 , T 2 ) and is exponentially distributed with mean 1
1
E [ M ( d ) ] + M
E [ M ]
.
Let node A encounter a potential relay ( lets label it node B ) before meeting the destination. ( The proba-bility
of this event is equal to
M
E [ M ]
1
E [ M ( d ) ] + M
E [ M ]
.) Let node A and B be at a distance d A and d B from the
destination when they meet. Node A has l copies of the packet while B has none. Let D M ( d A , d B , l ) denote
the minimum additional delay to deliver the packet to the destination. Then,
E [ D ( d , l ) ] =
1
1
E [ M ( d ) ] + M
E [ M ]
+
M
E [ M ]
1
E [ M ( d ) ] + M
E [ M ] X d A , d B
P ( d A , d B ) E [ D M ( d A , d B , l ) ] , ( 7)
where P ( d A , d B ) is the probability that the two nodes are at a distance d A and d B from the destination when
they meet.
Node A can give any number from 0 to l − 1 copies to the B . If i of the l copies are given to B , then the
delivery delay to the destination is the minimum of D ( d A , l − i ) and D ( d B , i ) . Hence,
E [ D M ( d A , d B , l ) ] = min 0  i < l ( E [ min ( D ( d A , l − i ) , D ( d B , i ) ) ] ) ( 8)
Note that the solution to Equation ( 8) gives the optimal spraying policy.
Equations ( 7) and ( 8) form a system of non linear equations. Solving these equations will give the
optimal spraying policy, but solving a non linear system is not easy. So, we make approximations to sim-plify
these equations. ( Note that due to these approximations, the spraying policy obtained is not really the
optimal, but it will give an intuition into the structure of the optimal policy.)
First, we assume that the sum of two exponentially distributed random variables is also exponential. With
this approximation, the distribution of both D ( d , l ) and D M ( d A , d B , l ) can be derived to be exponential.
Thus, Equation ( 7) reduces to the following:
E [ D ( d , l ) ] =
1
1
E [ M ( d ) ] + M
E [ M ]
+
M
E [ M ]
1
E [ M ( d ) ] + M
E [ M ] X d A , d B
P ( d A , d B ) min 0  i < l   1
1
E [ D ( d A , l − i ) ] + 1
E [ D ( d B , i ) ] ! . ( 9)
Equation ( 9) is still a system of non linear equations which are not easy to solve. So, we make another
approximation by replacing d A by its expected value. For the random walk mobility model, E [ d A ] is equal
4The number of potential relays is equal to the number of nodes which do not have a copy of the packet. This number is upper
bounded by the total number of nodes, M . Since the number of potential relays is unknown at a given time, we use the upper bound
on this value.
15
20 40 60 80 100 120
0
1
2
3
4
d A
Number of copies transmitted to B
d A − d B = K
d A − d B = − K
d b £ K
( a)
20 40 60 80 100 120
0
5
10
15
20
d A
Number of copies transmitted to B
d A − d B = − K
d A − d B = K
d B £ K
( b)
0 5 10 15 20
0
0.2
0.4
0.6
0.8
1
Total number of copies ( l)
fraction of copies transmitted
d A − d B = K
d A − d B = − K
l th
( c)
0 5 10 15 20
0
0.2
0.4
0.6
0.8
1
Total number of copies ( l)
fraction of copies transmitted
d A − d B = 1
d A − d B = − 1
l th
( d)
Figure 6: Studying the optimal spraying policy for Spray and Wait. Network Parameters: N = 1 5 0 ×
1 5 0 , M = 4 0 , K = 2 0 . ( a) Number of copies given to node B as a function of d A for l = 4 . ( b) Number of
copies given to node B as a function of d A for l = 2 0 . ( c) Proportion of copies given to node B as a function
of l for d A = 7 5 . ( d) Proportion of copies given to node B as a function of l for d A = 7 5 .
to d as the probability of moving in any direction is the same. Replacing d A by d in Equation ( 9) yields,
E [ D ( d , l ) ] =
1
1
E [ M ( d ) ] + M
E [ M ]
+
M
E [ M ]
1
E [ M ( d ) ] + M
E [ M ] X d B
P ( d B | d A = d ) min 0  i < l   1
1
E [ D ( d , l − i ) ] + 1
E [ D ( d B , i ) ] ! . ( 10)
In Equation ( 10), the value of E [ D ( d , l ) ] depends only on those E [ D ( ˆ d , ˆ l
) ] for which either ˆ l
< l or
ˆ l
= l , ˆ d ≤ d . So, a dynamic program can be used to solve Equation ( 10).
The dynamic program will be initialized with the value of E [ D ( d , 1 ) ] which depends on how each copy
is routed towards the destination. Section 3.5.1 and 3.5.2 finds its value for Spray and Wait and Spray and
Focus.
The only unknown in Equation ( 10) is P ( d B | d A = d ) . Since node B is within range of A , d B will lie
within d − K and d + K . P ( d B | d A = d ) can be derived using elementary combinatorics to be equal to
  
K + 1
4 K d B = d − K
2
4 K d − K + 2 ≤ d B ≤ d + k − 2
K + 1
4 K d B = d + K
.
3.5.1 Spray andWait
In this section, we first study the optimal spraying policy for spray and wait, then study the spraying policy
obtained by solving Equation ( 10), and finally present a simple heuristic which achieves a expected delay
very close to the optimal.
In Spray and Wait, each relay node routes the copy towards the destination using direct transmission.
Thus, E [ D ( d , 1 ) ] is the expected time it takes for the relay to meet the destination and is equal to E [ M ( d ) ] .
Now, we study the spraying policy obtained by solving Equation ( 10). Let node A which has l copies
of the packet meet node B which has none. Let the distance to the destination of both the nodes be denoted by
d A and d B respectively. Figure 6( a)- 6( b) plots the number of copies given to node B versus d A for different
values of l . For l = 4 , the node which is closer to the destination gets most of the copies while for l = 2 0 ,
most of the times, nearly half of the copies are given away to node B . This observation suggests that the
optimal policy behaves differently for different values of l . ( Note that node B gets only one copy when it is
within the transmission range of the destination because the packet will be delivered at the next transmission
opportunity.)
To study the behavior of the optimal policy as l changes, we plot the proportion of copies given to node B
as a function of l for different values of d A − d B in Figures 6( c)- 6( d). In all the cases, there exists a threshold
16
0 5 10 15 20
0
500
1000
1500
2000
2500
3000
3500
L
Expected end− to− end delay
Binary Spraying
Dynamic Program
Heuristic
Figure 7: Comparison of the expected end- to- end delay performance of binary spraying, the optimal policy
and the proposed heuristic. Network parameters: N = 1 5 0 × 1 5 0 , M = 4 0 , K = 2 0 .
for l below which most of the copies are kept by the node closer to the destination and above which the copy
splitting is more or less half and half. We label this threshold as l t h .
Based on the above observation, we propose a simple heuristic to distribute copies. ( i) If l is less than l t h
and node A is closer to the destination, then node B is not given any of the copies. ( ii) If l is less than l t h and
node B is closer to the destination, then node B is given l − 1 copies. ( iii) If l is greater than l t h , then node B
is given half of the copies. Figures 7- 8 compare the performance of the optimal policy, the proposed heuristic
and binary spraying for different network parameters. It is easy to see that the proposed heuristic performs
very close to the optimal and has a better performance than binary spraying.
3.5.2 Spray and Focus
In this section, we first study the optimal spraying policy for spray and focus, then study the spraying policy
obtained by solving Equation ( 10), and finally present a simple heuristic which achieves a expected delay
very close to the optimal.
In Spray and Focus, each relay node performs utility based forwarding towards the destination. First, we
derive the value of E [ D ( d , 1 ) ] to initialize the dynamic program which is used to solve Equation ( 10).
Lemma 3.6 E [ D ( d , 1 ) ] can be derived by solving the following set of non linear equations:
E [ D ( d , 1 ) ] =
1
1
E [ M ( d ) ] + M
E [ M ]
+
M
E [ M ]
1
E [ M ( d ) ] + M
E [ M ] X d 2
P ( d 2 | d ) E [ D ( m i n ( d , d 2 ) , 1 ) ] . ( 11)
Proof: In the future time slots either of the following two events can happen first: ( i) The node meets
the destination and delivers the packet. This time duration is exponentially distributed with mean E [ M ( d ) ] .
( ii) The node meets a potential relay node. This time duration is exponentially distributed with mean E [ M ]
M .
Let the relay node be at a distance d 2 from the destination. Then if d 2 < d , then the relay node is closer to
the destination and it will be given the copy of the packet. The additional time it will take to deliver the packet
will be equal to E [ D ( d 2 , 1 ) ] . But if d 2 ≥ d , the original node will retain the copy and the additional time it
will take to deliver the packet is still equal to E [ D ( d , 1 ) ] . 2
17
10 15 20 25 30
0
500
1000
1500
2000
2500
3000
K
Expected end− to− end delay
Binary Spraying
Dynamic Program
Heuristic
Figure 8: Comparison of the expected end- to- end delay performance of binary spraying, the optimal policy
and the proposed heuristic. Network parameters: N = 1 5 0 × 1 5 0 , M = 4 0 , L = 5 .
20 40 60 80 100 120
0
1
2
d A
Number of copies transmitted to B
d A − d B = − K
d A − d B = K
( a)
20 40 60 80 100 120
0
5
10
15
20
d A
Numbr of copies transmitted to B
d A − d B = − K
d A − d B = K
d B £ K
( b)
5 10 15 20
0
0.2
0.4
0.6
0.8
1
Total number of copies ( l)
fraction of transmitted copies
d A − d B = − K
d A − d B = K
( c)
5 10 15 20
0
0.2
0.4
0.6
0.8
1
Total number of copies ( l)
fraction of transmitted copies
d A − d B = − 1
d A − d B = 1
( d)
Figure 9: Studying the optimal spraying policy for Spray and Focus. Network Parameters: N = 1 5 0 ×
1 5 0 , M = 4 0 , K = 2 0 . ( a) Number of copies given to node B as a function of d A for l = 2 . ( b) Number of
copies given to node B as a function of d A for l = 2 0 . ( c) Proportion of copies given to node B as a function
of l for d A = 7 5 . ( d) Proportion of copies given to node B as a function of l for d A = 7 5 .
A particular value of E [ D ( d , 1 ) ] depends only on those values of E [ D ( ˆ d , 1 ) ] for which ˆ d ≤ d . Hence, a
dynamic program can be used to solve Equation ( 11).
Now, we study the optimal spraying policy obtained by solving Equation ( 10) after substituting the value
of E [ D ( d , 1 ) ] derived in Lemma 3.6. Figure 9( a)- 9( b) plots the number of copies given to node B versus
d A for different values of l . The curves show that most of the times, nearly half of the copies are handed
over to node B irrespective of the value of l . To confirm this observation, we plot the proportion of copies
given to node B as a function of l for different values of d A − d B in Figures 9( c)- 9( d). For all the cases, nearly
half of the copies are handed over to node B . This suggests that binary spraying should perform close to the
optimal policy. Figures 10- 11 compare the performance of binary spraying with the optimal policy for differ-ent
network parameters. These figures show that binary spraying has near optimal performance for Spray and
Focus. The near optimal performance of binary spraying is explained by the following two observations: ( i)
If a node distributes its copies to bad nodes ( nodes which have a higher expected delivery delay), it still has its
own copy which it can give to a good node whenever it meets one. ( ii) Moreover, a bad node will have a chance
to give up its copy to good nodes later in the future. Thus, spraying copies as fast as possible will achieve a good
18
0 5 10 15 20
0
100
200
300
400
500
L
Expected end− to− end delay
Binary Spraying
Dynamic Program
Figure 10: Comparison of the expected end- to- end delay performance of binary spraying and the optimal
policy. Network parameters: N = 1 5 0 × 1 5 0 , M = 4 0 , K = 2 0 .
10 15 20 25 30
0
500
1000
1500
K
Expected end− to− end delay
Binary Spraying
Dynamic Program
Figure 11: Comparison of the expected end- to- end delay performance of binary spraying and the optimal
policy. Network parameters: N = 1 5 0 × 1 5 0 , M = 4 0 , L = 5 .
19
delay performance for Spray and Focus.
3.5.3 Discussion
We now generalize the intuition derived in the previous section to general utility functions. For Spray and
Wait, if a smaller utility always means a smaller distance to the destination, there always exists a threshold l t h
such that the following heuristic performs well: ( i) If l is less than l t h and node A is closer to the destination,
then node B is not given any of the copies. ( ii) If l is less than l t h and node B is closer to the destination, then
node B is given l − 1 copies. ( iii) If l is greater than l t h , then node B is given half of the copies. All the utility
functions discussed in Section 3.4 satisfy this constraint, hence, the proposed heuristic was found to be very
efficient in vehicular networks.
For Spray and Focus, irrespective of the utility function, binary spraying always yields efficient results
because the focus phase allows fixing any “ wrong” or “ bad” decisions made earlier. Hence, for vehicular
networks, Binary Spray and Focus was found to be the best spraying protocol.
3.6 Collaboration of communication- capable vehicles and roadside stations
In addition to vehicule to vehicule communication, another form of communication is expected to take
place between vehicles and roadside stations along the road. Such stations are envisioned to be installed in
intersections, or at regular distances along highways. The correct operation of the binary spray and focus
protocols in a vehicular network does not depend on the existence of such infrastructure. Nevertheless, if
such stations become available, they can be used to signicantly improve performance.
Spray and focus treats roadside stations similarly to vehicles. However, an important difference is that
these stations are assumed to be interconnected, and once a message is received by one of them, it can reach
very fast distant locations. So, the utility of these stations is the same for each destination. In other words,
if a roadside station comes within range of the destination, then all roadside stations can be assumed to be
within the range of the destination. Hence, these stations tend to have a higher utility in general, so it is very
likely that vehicles will communicate with each other through roadside stations. We always observed better
expected delays and higher delivery probabilities in presence of these roadside stations.
Introducing roadside stations introduces the following change to the analysis. Roadside station is static
while the vehicle is moving according to a given mobility model. The duration after which they come
within range of each other is no longer one meeting time. This duration is equal to the hitting time which is
rigorously defined as follows.
Hitting Time Let a node i move according to mobility model “ mm”, and start from its stationary distribu-tion
at time 0 . Let j be a static node with uniformly chosen X j , then the hitting time ( T m m ) is defined as the
time it takes node i to first come within range of node j , that is T m m = m i n
t { t : k X i ( t ) − X j k ≤ K }.
We next state expressions of the expected hitting time for the two most common mobility models - the
Random Direction and the Random Waypoint mobiity models.
We first define the Random Direction mobility model and then state the expression for its expected
hitting time.
Random Direction In the Random Direction ( RD) model each node moves as follows: ( i) choose a di-rection
 uniformly in [ 0 , 2  ) ; ( ii) choose a speed according to assumption ( d); ( iii) choose a duration T of
movement from an exponential distribution with average L
v ; ( iv) move towards  with the chosen speed for T
time units; 5 ( v) after T time units pause according to assumption ( e) and go to step ( i).
5If the boundary is reached, the node either reflects back or re- enters from the opposite side of the network ( torus).
20
Theorem 3.4 The expected hitting time E T r d for the Random Direction model is given by:
E T r d =  N
2 K L   L
v
+ T s t o p  . ( 12)
We next define the Random Waypoint mobility model, then state a lemma stating the average distance
covered by a node in one epoch, and then state the expression for the expected hitting time RandomWaypoint
mobility.
Random Waypoint In the RandomWaypoint ( RWP) model, each node moves as follows [ 13]: ( i) choose a
point X in the network uniformly at random, ( ii) choose a speed v uniformly in [ v m i n , v m a x ] with v m i n > 0
and v m a x < ∞. Let v denote the average speed of a node, ( iii) move towards X with speed v along
the shortest path to X , ( iv) when at X , pause for T s t o p time units where T s t o p is chosen from a geometric
distribution with mean T s t o p , ( v) and go to Step ( i).
Lemma 3.7 Let L be the length of an epoch, measured as the distance between the starting and the finishing
points of the epoch. Then E L r w p = 0 . 3 8 2 6 √ N .
Theorem 3.5 The expected hitting time E T r w p for the Random Waypoint model is given by:
E T r w p =  N
2 K E L r w p   E L r w p
v
+ T s t o p  . ( 13)
3.7 Incorporating Contention
Up till now, we have ignored contention in the analysis. The assumption of no contention is valid only for
very low traffic rates, irrespective of whether the network is sparse or not. For higher traffic rates, contention
has a significant impact on the performance, especially of flooding- based routing schemes. Given the small
contact durations in vehicular network, contention will have a even more severe affect on performance.
To demonstrate the inaccuracies which arise when contention is ignored, we use simulations to compare the
delay of three different routing schemes in a sparse network, both with and without contention, in Figure 12.
The plot shows that ignoring contention not only grossly underestimates the delay, but also predicts incorrect
trends and leads to incorrect conclusions. For example, without contention, the so called spraying scheme has
the worst delay, while with contention, it has the best delay.
Incorporating wireless contention complicates the analysis significantly. This is because contention man-ifests
itself in a number of ways, including ( i) finite bandwidth which limits the number of packets two nodes
can exchange while they are within range, ( ii) scheduling of transmissions between nearby nodes which is
needed to avoid excessive interference, and ( iii) interference from transmissions outside the scheduling area,
which may be significant due to multipath fading [ 8]. So, we first propose a general framework to incorporate
contention in the performance analysis of mobility- assisted routing schemes for ICMNs while keeping the
analysis tractable. This framework incorporates all the three manifestations of contention, and can be used
with any mobility and channel model. The framework is based on the well- known physical layer model [ 21].
Prior work has used the physical layer model to derive capacity results, see, for example, [ 19, 21, 32], and
has assumed an idealized perfect scheduler. We are interested in calculating the expected delay of various
mobility- assisted routing schemes under realistic scenarios, and for this reason we assume a randomaccess sched-uler.
21
3.6% 4.8% 6.3% 8.6% 11.9% 17.3%
0
100
200
300
400
500
600
Expected Maximum Cluster Size
Expected Delay ( time slots)
Epidemic Routing ( No Contention)
Randomized Flooding ( No Contention)
Spraying Scheme ( No Contention)
Epidemic Routing ( Contention)
Randomized Flooding ( Contention)
Spraying Scheme ( Contention)
Figure 12: Comparison of delay with and without contention for three different routing schemes in sparse networks.
The simulations with contention use the scheduling mechanism and interference model described in Section 3.7.1. The
expected maximum cluster size ( x- axis) is defined as the percentage of total nodes in the largest connected component
( cluster) and is a metric to measure connectivity in sparse networks [ 38]. The routing schemes compared are: epidemic
routing [ 41], randomized flooding [ 40] and spraying based routing [ 39].
3.7.1 The Framework
We assume that there are M nodes moving in a two dimensional torus of area N . We also assume that each
node acts as a source sending packets to a randomly selected destination. Finally, we assume the following
radio model.
RadioModel: An analytical model for the radio has to define the following two properties: ( i) when will two
nodes be within each other’s range, ( ii) and when is a transmission between two nodes successful. ( Note that
we define two nodes to be within range if the packets they send to each other are received successfully with a
non- zero probability.) If one assumes a simple distance- based attenuation model without any channel fading
or interference from other nodes, then two nodes can successfully exchange packets without any loss only if
the distance between them is less than a deterministic value K ( also referred to as the transmission range),
else they cannot exchange any packet at all. The value of K depends on the transmission power and the dis-tance
attenuation parameter. However, in presence of a fading channel and interference fromother nodes, even
though two nodes can potentially exchange packets if the distance between themis less than K , a transmission
between themmight not go through. A transmission is successful only when the signal to interference ratio ( SIR)
is greater than some desired threshold.
We assume the following radio model: ( i) Two nodes are within each other’s range if the distance be-tween
them is less than K , and ( ii) any transmission between the two is successful only if the SIR is greater
than a desired threshold  . Note that this model is not equivalent to a circular disk model because any
transmission between two nodes with a distance less than K is successful with a certain probability that
depends on the fading channel model and the amount of interference from other nodes.
We now present the framework for a mobility model with a uniform node location distribution. Com-monly
used mobility models like random direction and random waypoint on a torus satisfy this assump-tion
[ 12, 35]. The proposed framework can be easily extended to any other mobility model [ 26] in which the
process governing the mobility of nodes is stationary and the movement of each node is independent of each
other.
22
We first identify the three manifestations of contention and describe how do they affect message ex-change.
Finite Bandwidth: When two nodes meet, they might have more than one packet to exchange. Say two
nodes can exchange s B W packets during a unit of time. If they move out of the range of each other, they will
have to wait until they meet again to transfer more packets. The number of packets which can be exchanged
in a unit of time is a function of the packet size and the bandwidth of the links. We assume the packet size and
the bandwidth of the links to be given, hence s B W is assumed to be a given network parameter. We also
assume that the s B W packets to be exchanged are randomly selected from amongst the packets the two nodes
want to exchange6.
Scheduling: We assume an ideal CSMA- CA scheduling mechanism is in place which avoids any simultane-ous
transmission within one hop from the transmitter and the receiver. Nodes within range of each other and
having at least one packet to exchange are assumed to contend for the channel. For ease of analysis, we also as-sume
that time is slotted. At the start of the time slot, all node pairs contend for the channel and once a node pair
captures the medium, it retains the medium for the entire time slot.
Interference: Even though the scheduling mechanismis ensuring that no simultaneous transmissions are tak-ing
place within one hop fromthe transmitter and the receiver, there is no restriction on simultaneous transmis-sions
taking place outside the scheduling area. These transmissions act as noise for each other and hence can lead
to packet corruption.
In the absence of contention, two nodes would exchange all the packets they want to exchange whenever
they come within range of each other. Contention will result in a loss of such transmission opportunities. This
loss can be caused by either of the three manifestations of contention. In general, these three manifestations
are not independent of each other. We now propose a framework which uses conditioning to separate their
effect and analyze each of them independently.
Main Idea: Lets look at a particular packet, label it packet A . Suppose two nodes i and j are within range
of each other at the start of a time slot and they want to exchange this packet. Let p t x S denote the proba-bility
that they will successfully exchange the packet during that time slot. First, we look at how the three
manifestations of contention can cause the loss of this transmission opportunity.
Finite Bandwidth: Let E b w denote the event that the finite link bandwidth allows nodes i and j to ex-change
packet A . The probability of this event depends on the total number of packets which nodes i and j
want to exchange. Let there be a total of S distinct packets in the system at the given time ( label this event
E S ). Let there be s , 0 ≤ s ≤ S − 1 , other packets ( other than packet A ) which nodes i and j want to exchange
( label this event E S
s ). If s ≥ s B W , then the s B W packets exchanged are randomly selected from amongst these
s + 1 packets. Thus, P ( E b w ) = P S P ( E S )  P s B W − 1
s = 0 P ( E S
s ) + P S − 1
s = s B W
s B W
s + 1 P ( E S
s )  . To simplify the analy-sis,
we make our first approximation here by replacing the random variable S by its expected value in the ex-pression
for P ( E b w ) 7 ( see Equation ( 14) for the final expression for P ( E b w ) ). Note that simulations results
presented in [ 26] verify that this approximation does not have a drastic effect on the accuracy of the analysis.
Scheduling: Let E s c h denote the event that the scheduling mechanism allows nodes i and j to exchange
packets. The scheduling mechanism prohibits any other transmission within one hop from the transmitter
and the receiver. Hence, to find P ( E s c h ) , we have to determine the number of transmitter- receiver pairs which
6Note that assuming a random queueing discipline yields the same results as FIFO in our setting ( yet simplifies analysis).
This is so because a work conserving queue yields the same queueing delay for constant size packets irrespective of whether the
queue service discipline is FIFO or random queueing. In addition, due to packet homogeneity ( all packets are treated the same) the
expected end- to- end delay will also be the same. Of course, if packet homogeneity is lost, for example by assigning higher priority to
packets that are closer to their destination, the expected end- to- end delay will decrease as packets with a smaller end- to- end service
requirement will be serviced first.
7We incorporate the arrival process through E [ S ] in the analysis. E [ S ] depends on the arrival rate through Little’s Theorem.
Thus, after deriving the expected end- to- end delay for a routing scheme in terms of E [ S ], Little’s Theorem can be used to express the
delay in terms of only the arrival rate.
23
have at least one packet to exchange and are contending with the i - j pair. Let there be a nodes within one
hop from the transmitter and the receiver ( label it event E a ) and let there be c nodes within two hops but not
within one hop from the transmitter and the receiver ( label it event E c ). These c nodes have to be accounted
for because a node at the edge of the scheduling area can be within the transmission range of one of these
c nodes and will contend with the desired transmitter/ receiver pair. Let t ( a , c ) denote the expected number of
possible transmissions contending with the i - j pair. By symmetry, all the contending nodes are equally likely
to capture the channel. So, P ( E s c h | E a , E c ) = 1 / t ( a , c ) .
Interference: Let E i n t e r denote the event that the transmission of packet A is not corrupted due to inter-ference
given that nodes i and j exchanged this packet. Let there be M − a nodes outside the transmitter’s
scheduling area ( this is equivalent to event E a ). If two of these nodes are within the transmission range of
each other, then they can exchange packets which will increase the interference for the transmission between
i and j . Lets label the event that packet A is successfully exchanged inspite of the interference caused by
these M − a nodes as I M − a . Then, P ( E i n t e r | E a ) = P ( I M − a ) .
Packet A will be successfully exchanged by nodes i and j only if the following three events occur: ( i) the
scheduling mechanism allows these nodes to exchange packets, ( ii) nodes i and j decide to exchange packet
A from amongst the other packets they want to exchange, and ( iii) this transmission does not get corrupted
due to interference from transmissions outside the scheduling area. Thus,
p t x S = P ( E b w ) X a , c
P ( E a , E c ) P ( E s c h | E a , E c ) P ( E i n t e r | E a )
=  
s B W − 1
X s = 0
P ( E E [ S ]
s ) +
E [ S ] − 1
X s = s B W
s B W P ( E E [ S ]
s )
s + 1  
× X a , c
P ( E a ) P ( E c | E a ) P ( I M − a )
t ( a , c )
. ( 14)
Expressions for the unknown values on Equation ( 14) can be easily derived using geometric arguments.
Please refer to [ 26] for details.
We next study how does the optimal spraying scheme change after incorporating contention in the analy-sis.
We first state a sequence of lemmas which state the expected delay expressions for source spray and wait
( spraying scheme in which only source is allowed to spray copies) and fast spray and wait [ 26] ( which yields
a lower bound on binary spray and wait). We will then use these delay expressions to illustrate if and how the
conclusions drawn in the previous sections change.
Before stating the lemmas, we define two additional mobility properties. The delay expressions will be
stated in terms of these two.
Inter- Meeting Time Let nodes i and j start from within range of each other at time 0 and then move out of
range of each other at time t 1 , that is t 1 = m i n t { t : k X i ( t ) − X j ( t ) k > K }. The inter meeting time ( M +
m m )
of the two nodes is defined as the time it takes them to first come within range of each other again, that is
M +
m m = m i n t { t − t 1 : t > t 1 , k X i ( t ) − X j ( t ) k ≤ K }.
Contact Time Assume that nodes i and j come within range of each other at time 0 . The contact time  m m
is defined as the time they remain in contact with each other before moving out of the range of each other, that
is  m m = m i n t { t − 1 : k X i ( t ) − X j ( t ) k > K }.
Now we state the delay expressions for the two spraying schemes. Let E [ D m m
s s w ( m ) ] denote the expected
time it takes for the number of nodes having a copy of the packet to increase from m to m + 1 for source spray
and wait routing. First, we state the value E [ D m m
s s w ( m ) ] , and then state the expected end- to- end delay for
source spray and wait ( denoted by E [ D m m
s s w ] ) in terms of E [ D m m
s s w ( m ) ] .
Lemma 3.8 E [ D m m
s s w ( m ) ] = ( E [ M m m ]
( M − 1 ) p s s w
s u c c e s s
1 ≤ m < L
E [ M m m ]
L p s s w
s u c c e s s
m = L
where p s s w
s u c c e s s = 1 − ( 1 − p s s w
t x S ) E [  m m ] .
24
Theorem 3.6 E [ D m m
s s w ] = P L
i = 1 p s s w
d e s t ( i ) P i
m = 1 E [ D m m
s s w ( m ) ] .
Similarly, let E [ D m m
f s w ( m ) ] denote the expected time it takes for the number of nodes having a copy
of the packet to increase from m to m + 1 for fast spray and wait routing. Again, first we state the value
E [ D m m
f s w ( m ) ] , and then state the expected end- to- end delay for fast spray and wait ( denoted by E [ D m m
f s w ] ).
Lemma 3.9 E [ D m m
f s w ( m ) ] = ( E [ M m m ]
m ( M − m ) p f s w
s u c c e s s
1 ≤ m < L
E [ M m m ]
L p f s w
s u c c e s s
m = L
where p f s w
s u c c e s s = 1 −  1 − p f s w
t x S  E [  m m ]
.
Theorem 3.7 E [ D m m
f s w ] = P L
i = 1 p f s w
d e s t ( i ) P i
m = 1 E [ D m m
f s w ( m ) ] .
We now re- visit the three fundamental questions related to spraying- based schemes and comment on
how do the conclusions drawn without considering contention change after incorporating contention in the
analysis.
50 100 150 200
0
5
10
15
20
25
Target Expected Delay ( time slots)
L
Without Contention
With Contention
( a)
0 5 10 15 20 25
100
150
200
250
L
Expected Delay ( time slots)
( b)
Figure 13: ( a) Minimum value of L which achieves the target expected delay for source spray and wait.
( b) L against expected delay ( with contention). Network parameters: N = 1 0 0 × 1 0 0 , K = 8 , M = 1 5 0 ,  =
5 , E [ S ] = 7 0 , T s t o p = 0 , v = 1 , s B W = 1 .
3.7.2 Deciding the Right Number of Copies
This section studies the error introduced by ignoring contention when one has to find the minimum value of
L ( the number of copies sprayed) in order for a spraying- based scheme to achieve a specific expected
delay. ( Note that we want the minimum value of L which achieves the target delay as bigger values of L
consume more resources.) We choose the source spray and wait scheme with the random waypoint mobility
model as the case study in this section. We numerically solve the expression for E [ D r w p
s s w ] in Theorem 3.6 to
find the minimum value of L which achieves a target delay and plot it in Figure 13( a) both with and without
contention for a sparse network. ( For the expected delay of source spray and wait without contention, we use
the expression derived in [ 39].) This figure shows that an analysis without contention would be accurate for
smaller values of L ( smaller values of L generate lower contention in the network), however it would predict
that one can use a large number of copies to achieve a target expected delay which actually will not be achiev-able
in practice due to contention. For example, the analysis without contention indicates that a delay of 5 0 time
units is achievable with L = 2 3 while the contention- aware analysis indicates that it is not achievable. Figure 13( b)
25
shows that L = 2 3 results in an expected delay of more than 1 1 8 time units, which is also achievable by L = 5 .
Thus choosing a value of L based on predictions froma contention- ignorant analysis led to a value of delay which
is not only much higher than expected but also would have been achieved by nearly four times fewer copies. Thus,
we conclude that the analysis without contention will give accurate results only for smaller values of L , and larger
values of L should not be chosen as they merely create more contention without reducing the expected delay.
0 200 400 600
0
5
10
15
20
25
30
35
Time ( time slots)
Expected number of copies spread
Source spray and wait( M= 100)
Fast spray and wait( M= 100)
Source spray and wait( M= 250)
Fast spray and wait( M= 250)
Figure 14: Comparison of fast spray and wait and source spray and wait: Expected number of copies spread vs time
elapsed since the packet was generated. Network parameters: N = 1 0 0 × 1 0 0 square units, K = 5 ,  = 5 , s B W =
1 packet/ time slot, L = 2 0 . Expected maximum cluster size ( metric to measure connectivity) for these network
parameters is equal to 4 . 6 % for M = 1 0 0 and 5 . 2 % for M = 2 5 0 .
3.7.3 Routing Each Copy Separately
Utility- based forwarding reduces the number of copies required ( L ) to achieve a given delay. Thus it reduces
contention in the spraying phase. However, after copies have been distributed, it requires multiple message
exchanges in the focus phase which increases contention. Amongst the two, the contention reduction in the
spraying phase dominates, hence, the conclusions drawn without incorporating contention in the analysis
still hold. We give a numerical example to support this claim in Section 4.4.3.
3.7.4 Distributing Copies
As shown in Section 3.5, spraying copies as fast as possible is the best way to spread copies if all the
relay nodes are equal/ homogeneous. To answer whether spraying the copies as fast as possible is optimal
with contention, we compare fast source spray and wait and source spray and wait for the random waypoint
mobility model. Since fast spray and wait spreads copies whenever there is any opportunity to do so, it has
the minimumspraying time when there is no contention in the network. On the other hand, since source spray
and wait does not use relays to forward copies, it is one of the slower spraying mechanisms when there is no
contention in the network.
Now we study how fast the two schemes spread copies of a packet when there is contention in the
network. Figure 14 plots the number of copies spread as a function of the time elapsed since the packet
was generated. Somewhat surprisingly, depending on the density of the network, source spray and wait
26
can spray copies faster than fast spray and wait. This occurs because fast spray and wait generates more
contention around the source as it tries to transmit at every possible transmission opportunity. Such a
behavior is expected for dense networks, but these results show that increased contention can deteriorate
fast spray and wait’s performance even in sparse networks. This issue is more aggravated in vehicular
networks as contact durations are small. In general, unless the network is very sparse, strategies which
spray copies slower yield better performance than more aggressive schemes thanks to reducing contention.
4 Analysis with Realistic Mobility Models - “ Community- based Mobility
Model”
To understand the performance of spray and focus routing with realistic vehicle mobility, we propose a new
mobility model. Like a good mobility model, the proposed model has the following three characteristics:
( i) it captures realistic vehicular mobility patterns of scenarios in which one wants to eventually operate
the network; ( ii) at the same time the proposed model is mathematically tractable; this is very important
to allow the derivation of performance bounds and to understand the limitations of various protocols under
the given scenario; ( iii) finally, it is flexible enough to provide qualitatively and quantitatively different
mobility characteristics by changing some parameters of the model, yet in a repeatable and scalable manner
as designing a new mobility model for each existing or new scenario is undesirable.
The proposed model is a time- variant community mobility model, and is referred to as the TVC model.
One salient characteristic in the TVC model is location preference. Another important characteristic is the
time- dependent, periodical behavior of nodes. To our best knowledge, this is the first synthetic mobility
model that captures non- homogeneous behavior in both space and time.
To establish the flexibility of our TVC model we show that we can match its two prominent properties,
location visiting preferences and periodical re- appearance, with a vehicle mobility trace[ 2].
Finally, in addition to the improved realism, the TVC model can be mathematically treated to derive
analytical expressions for important mobility properties of interest, such as the meeting time, the inter-meeting
time etc. We illustrate how to derive the statistics of these quantities, and then use them to derive
expressions for spray and focus routing for a particular instantiation of the model.
4.1 Time- variant Community Mobility Model
After analyzing a large number of traces [ 24], we observed two important properties that are common in all
of them: ( a) skewed location visiting preferences and ( b) time- dependent mobility behavior [ 23]. Spcifically,
the location visiting preference refers to the percentage of time a node spends at a given location and the
time- dependent mobility behavior refers to the observation that nodes visit different locations, depending on
the time of the day. We believe that these two properties are prevalent in any human- driven mobility. This
belief is supported by typical daily activities of humans: most of us tend to spend most time at a handful of
frequently visited locations, and a recurrent daily or weekly schedule is an inseparable part of our lives. It
is essential to design a model that captures such spatial- temporal preferences of human mobility in many
contexts.
We next present the design of our time- variant community ( TVC) mobility model. We illustrate the model
with an example in Fig. 15 and use this example to introduce the notations we use ( see Table 2) in the rest of
the paper.
First, to induce skewed location visiting preferences, we define some communities ( or heavily- visited ge-ographic
areas). Take time period 1 ( TP1) in Fig. 15 as an example, the communities are denoted as C o m m 1 j
and each of them is a square geographical area with edge length C 1
j .8 A node visits these communities with
8For all parameters used in the paper, we follow the convention that the subscript of a quantity represents its community index,
27
Table 2: Parameters of the time- variant community mobility model 1
N Edge length of simulation area
V Number of time periods
T t Duration of t - th time period
S t Number of communities in time period t
C t
j Edge length of community j in time period t
C o m m t
j The j - th community during time period t
p t i , j The probability to choose community j when
the previous community is i , during time period t
 t
j Stationary probability of an epoch in
community j during time period t
v m i n , v m a x , v Minimum, maximum, and average speed1
D m a x , j , D j Maximum and average pause time after each epoch1
L j Average epoch length for community j
P t m o v e , j | P t
p a u s e , j Probability that a node is moving | pausing
when being in community j during period t
P t
j Fraction of time the node is in
state j ( P t
j = P t m o v e , j + P t
p a u s e , j )
K Transmission range of nodes
A ( a t
j , b t
k ) The overlapped area between C o m m t
j of node a
and C o m m t
k of node b
w t A specific relationship between a target coordinate
and the communities in time period t

 t The set of all possible relationships between
a target coordinate and the communities in time period t
P h ( w t ) Unit- time hitting probability
under the specific scenario w t
P H ( w t ) Hitting probability for a time period t
under specific scenario w t
P t m
Unit- time meeting probability in time period t
P t M Meeting probability for a time period t
28
different probabilities ( details are given later) to capture its spatial preference in mobility. In the TVC model,
the mobility process of a node consists of epochs in these communities. When the node chooses to have an
epoch in community j ( we say that the node is in state j during this epoch), it starts from the end point of
the previous epoch within C o m m 1 j
and the epoch length ( movement distance) is drawn from an exponential
distribution with average L j , in the same order of the community edge length. The node then picks a random
speed uniformly in [ v m i n , v m a x ] , and a direction ( angle) uniformly in [ 0 , 2  ] , and performs a random direc-tion
movement within the chosen community with the chosen epoch length9. The first difference between the
TVC model and the standard RandomDirection model is hence the spatial preference and location- dependent
behavior. Note that, a node can still roamaround the whole simulation area during some epochs, by assigning an
additional community that corresponds to the whole simulation field ( e. g. C o m m 1 3
). We refer to such epochs as
roaming epochs.
We next explain how a node selects the next community for a sequence of epochs. At the completion of
an epoch, the node remains stationary for a pause time uniformly chosen in [ 0 , D m a x , j ] . Then, depending on
its current state i and time period t , the node chooses the next epoch to be in community j with probability
p t i , j . This community selection process is essentially a time- variant Markov chain that captures the spa-tial
and temporal dependencies in nodal mobility and thus makes the community selection process in the
TVC model non- i. i. d., an important feature absent in many synthetic mobility models even if they consider
non- uniform mobility features. Now, if the end point of the previous epoch is in C o m m t
j ( this can be the case
when the node has two consecutive epochs in C o m m t
j , or C o m m t
j contains C o m m t i
), the node starts the
next epoch directly. If, on the other hand, the node is currently not in C o m m t
j , a transitional epoch is inserted
to bridge the two epochs in disjoint communities. The node selects a random coordinate point in the next
community, moves directly towards this point on the shortest straight path with a randomspeed drawn from [ v m i n ,
v m a x ] , and then continues with an epoch in the next community. Hence the movement trajectory of a node is al-ways
continuous in space.
We next introduce the structure in time. To capture time- dependent behavior, one creates multiple time
periods with different community and parameter settings. As an example, there are V = 3 time periods with
duration T 1 , T 2 , and T 3 in Fig. 15. These time periods follow a periodic structure ( e. g., a simple recurrent
structure in Fig. 15 or the weekly schedule in Fig. 16). This setup naturally captures the temporal preferences
( e. g., go to work during the days and home during the nights) and periodicity in human mobility. On the time
boundaries between time periods, each node continues with its ongoing epoch, and decides the next epoch
according to the new parameter settings in the new time period when it finishes the current epoch.
As a final note, we choose to construct the TVC model with simple building blocks introduced above
due to its amenability to theoretical analysis [ 35] and flexibility. To further explain the flexibility of our TVC
model, we note that the number of communities in each time period ( denoted as S t ) can be different, and
the communities can overlap ( as in TP1 in Fig. 15) or contain each other ( as in TP2 in Fig. 15). Finally, the
time period structure, communities, and all other parameters could be assigned differently for each node to
capture node- dependent mobility ( e. g., people following different schedules, with different working places,
etc.), while nodes can share some communities ( i. e., the popular locations) as well. This construction allows
for maximum flexibility when setting up the simulations for nodes with heterogeneous behaviors10.
and the superscript represents the time period index.
9To avoid boundary effects, if the node hits the community boundary it is re- inserted from the other end of the area ( i. e., ” torus”
boundaries). Note that we could also choose random waypoint or random walk models for the type of movement during each epoch.
10When necessary, we use a pair of parentheses to include the node ID for a particular parameter, e. g., C t
j ( i ) denotes the edge
length of the j - th community during time period t for node i .
29
5 H S H W L W L Y H  W L P H  S H U L R G  V W U X F W X U H   9    7 L P H
7 3  7 3  7 3  7 3  7 3  7 3  7 3 
7 L P H  S H U L R G    7 3   7 L P H  S H U L R G    7 3   7 L P H  S H U L R G    7 3  
& R P P 

& R P P 

& R P P 
& R P P  

& R P P 

& R P P 

& R P P 

& R P P 

& R P P 

1
& 

& 

& 
 & 

& 

& 

& 

& 

& 

7  7  7 
6     6     6    
Figure 15: Illustration of a generic scenario of time- variant mobility model, with three time periods and
different numbers of communities in each time period.
7 L P H
7 3  7 3  7 3  7 3  7 3  7 3  7 3  7 3  7 3  7 3  7 3  7 3  7 3  7 3 
: H H N G D \ V : H H N H Q G
Figure 16: An illustration of a simple weekly schedule, where we use time period 1 ( TP1) to capture weekday
working hour, TP2 to capture night time, and TP3 to capture weekend day time.
4.2 Model Validation
The TVC model described in the previous section provides a general framework to model a wide range of
mobility scenarios. In this section, our aim is to demonstrate the model’s flexibility and validate its realism
by generating synthetic traces from the model, with matching mobility characteristics to a well- known,
publicly- available VANET trace. However, it is important to note that the use of such a model is not merely
to match it with any specific trace instance available; this is only done for validation and calibration purposes.
Rather, the goal is to be able to reproduce a much larger range of realistic mobility instances than a single
trace can provide11.
We first outline a general 3- step systematic process to construct specific mobility scenarios. Then,
we demonstrate our success to generate matching mobility characteristics with three qualitatively differ-ent
traces. All the parameter values we use in this section are also available in [ 6].
STEP 1: Determine the Structure in Space and Time
• ( 1.1 Number of communities) Each community in the TVC model corresponds to a location visited fre-quently
by nodes. The number of communities needed is thus determined by how closely one wants the
mobility characteristics to match with the curves. Due to the nature of skewed location visiting prefer-ence,
in our experience, only two or three communities are needed to capture up to 8 5 % of the user
online time spent at the most popular locations. Such a simple spatial structure yields simple theoretical
expressions. However, if one wants the model to capture more details ( e. g., for detailed simulation), the user
can instantiate as many communities as needed to explicitly represent the less visited locations.
11We havemade ourmobility trace generator available at [ 6]. The tool providesmobility traces in both ns- 2 compatible format and
time- location ( i. e., ( t , x , y )) format.
30
• ( 1.2 Location of communities) If the map of the target environment is available, one should observe the
map and identify the points of attraction in the given environment to assign the communities accordingly.
Alternatively, if the map is not available, one can instantiate communities at random locations.
• ( 1.3 Time period structure) Typically, human activities are bounded by daily and weekly schedules so a
time period structure shown in Fig. 16 would suffice for most applications. If capturing finer behavior based
on time- of- day is necessary, one could additionally split the day into time periods with different mobile node
behavior.
STEP 2: Assign Other Parameters After the space/ time structure is determined, one has to determine the
remaining parameters for each community and time period. This includes  t
j , D t j
, and L t
j , which represent
the stationary probability ( which is calculated after selecting proper p t i , j ’ s that lead to a desired stationary
distribution using simple Markov chain theory), average pause time, and average epoch length, respectively,
at community j during time period t .
• The average epoch length in each community, L t
j , should be at least in the same order as the edge length
of the community, C t
j . This is to ensure that the end point of the epoch becomes almost independent of its
starting point, since the mixing time of the corresponding process becomes quite small. ( The motivation for
this requirement is to keep the theoretical analysis tractable.)
• The average duration the node stays in community j is given by  t
j ( D t j
+ L t
j / v ) . The ratio between the
durations the node stays in each community shapes the location visiting preference curve.
• The highest peak of the re- appearance probability curve is determined by the weighted average proba-bility
of the node appearing in the same community during the same type of time period. This value is
P V
t = 1
T t
P V
k = 1 T k P S t
j = 1 ( P t
j ) 2 , where P t
j denotes the fraction of time the node spends in community j .
STEP 3: Adjust User On- off Pattern ( Optional) The mobility trace generated by the TVC model is an
“ always- on” mobility trajectory ( i. e., the mobile nodes are always present somewhere in the simulation
field). However, in some situations some nodes might be absent occasionally. Thus one may need to make
optional adjustments to turn nodes off in the generated trace, depending on the actual environment to match
with. To address this we assign a probability P o n , j as the probability for the node to be “ on” in community j .
We now show that skewed location visiting preferences and periodical re- appearance are also prominent
mobility properties in vehicle mobility traces. We obtain a vehicle movement trace from [ 2], a website that
tracks participating taxis in the greater San Francisco area. We process a 40- day trace obtained between Sep.
22, 2006 and Nov. 1, 2006 for 549 taxis to obtain their mobility characteristics. The results are shown in
Figures 17( a) and 17( b) with the label Vehicle- trace.
We use 3 0 communities and the weekly time schedule in ( STEP1). We need more communities for
this trace as the taxis are more mobile and visit more places than people on university campuses. From the
actual trace, we discover that the taxis are offline ( i. e., not reporting their locations) when not in operation.
Hence we assume that the nodes are “ on” only when they are moving. The pause times between epochs are
considered as breaks in taxi operation. Therefore in ( STEP3), P t
o n , j = ( L t
j / v ) / ( D t j
+ L t
j / v ) , and we adjust
the parameters in a similar way as described in the previous section. The curves in Figures 17( a) and 17( b)
with label Model match with the curves with Vehicle- trace label well. As a final note, although vehicular
movements are generally constrained by streets and our TVC model does not capture such microscopic
behaviors, designated paths and other constraints could still be added in the model’s map ( for vehicular or
human mobility) without losing its basic properties. We defer this for future work.
4.3 Derivation of Meeting and Inter- meeting Times
One of the biggest advantages of our model is that, in addition to the realism, it is also analytically tractable
with respect to the important mobility properties required to analyze protocol performance. In this section,
we demonstrate this property by deriving the meeting and the inter- meeting times for a specific instantiation
31
1. E- 06
1. E- 05
1. E- 04
1. E- 03
1. E- 02
1. E- 01
1. E+ 00
1 11 21 31 41 51
Fraction of visit time
Vehicle- trace
Model
Location sorted by visit time
( a)
Time gap ( days)
Re- appearance probability
0
0.05
0.1
0.15
0.2
0.25
0.3
0 1 2 3 4 5 6 7 8
Vehicle- trace
Model
( b)
Figure 17: Matching mobility characteristics of the synthetic trace to the vehicle mobility trace. ( a) Location
visiting preferences. ( b) Periodical re- appearance.
of the model. We refer to this instantiation as the community- based mobility model as it ignores the time-dependencies.
Community- based Model Nodes move inside the network as follows:
• each node i has a local community C i of size k C i k = c 2 N , c ∈ ( 0 , 1 ] ; a node’s movement consists of a
sequence of local and roaming epochs.
• a local epoch is a Random Direction movement12 restricted inside area C i with average epoch length
L c equal to the expected distance between two points uniformly chosen in C i .
• a roaming epoch is a Random Direction movement in the entire network with expected length L .
• ( local state L) if the previous epoch of node i was a local one, the next epoch is a local one with
probability p ( i )
l , or a roaming epoch with probability 1 − p ( i )
l .
• ( roaming state R) if the previous epoch of node i was a roaming one, the next epoch is a roaming one
with probability p ( i )
r , or a local one with probability 1 − p ( i )
r .
Lemma 4.1 calculates some useful probabilities, and follows easily from elementary probability theory.
Lemma 4.1 Let us denote as  ( i )
l and  ( i )
r the probability that a given epoch of node i is a local or a
roaming one, respectively. Let us further denote the probability that, at any time, the node is: ( a) moving in
local epoch as p ( i )
m l , ( b) moving in roaming epoch as p ( i )
m r , ( c) pausing after a local epoch as p ( i )
p l , ( d) pausing
after a roaming epoch as p ( i )
p r . Then:
 ( i )
l =
1 − p ( i )
r
2 − p ( i )
l
− p ( i )
r
,  ( i )
r =
1 − p
( i )
l
2 − p
( i )
l − p
( i )
r
p ( i )
m l =
 ( i )
l
L c
v
 ( i )
l T l +  ( i )
r T r
, p ( i )
m r =
 ( i )
r
L
v
 ( i )
l T l +  ( i )
r T r
, p ( i )
p l =

( i )
l
T
l
s t o p

( i )
l
T l + 
( i )
r T r
, p ( i )
p r = 
( i )
r T s t o p

( i )
l
T l + 
( i )
r T r
.
Table 3 summarizes the new notation specific to the community model described above. We will focus
here on the case where each node i has its own community C i , but all nodes have the same mobility charac-teristics,
that is, p ( i )
l = p l and p ( i )
r = p r , ∀ i ( i. e. drop the ( i ) from all probabilities). The heterogeneous case is
only a straightforward extension of this [ 35].
Meeting Time: To compute the expected meeting time, we break the problem into the following two cases:
( i) non- overlapped communities, which refers to the case where the communities of the two nodes under
study are disjoint, and ( ii) overlapped communities, which refers to the case where the communities of the
two nodes are the same. ( We ignore partial overlap to simplify analysis.) Each of these two cases are analyzed
separately, and then we take a weighted average over the two cases. The following theorem states the result.
12Note that each node could also perform Random Waypoint movement in each epoch, instead of Random Direction.
32
Table 3: Notation for the Community- based mobility model
C i community of node i : k C i k = c 2 N , c ∈ ( 0 , 1 ]
p l probability that next epoch is local,
given that previous epoch was local
p r probability that next epoch is roaming,
given that previous epoch was roaming
 l probability that a given epoch is a local one
 r probability that a given epoch is a roaming one
p m r probability that a node is in roaming state and moving
p m l probability that a node is in local state and moving
p p r probability that a node is in roaming state and pausing
p p l probability that a node is in local state and pausing
L c expected length of local epoch
T
l
s t o p expected pause time for a local epoch
T l expected local epoch duration ( L c / v + T
l
s t o p )
T r expected roaming epoch duration ( L / v + T s t o p )
Theorem 4.1 The probability distribution of the meeting time M c o m m under the Community- based mobility
model can be approximated by the weighted sum of two exponential distributions, with expected v alue:
E M c o m m = ( 1 − c 2 ) E M c o m m , d i f f + c 2 E M c o m m , s a m e . ( 15)
where,
E M c o m m , d i f f = » 2 K v
N ` ˆ v r d ( ( p m r + p m l ) 2 − p 2
m l ) + ( 2 p m r ( p p r + p p l ) ) + ( 2 p m l p p r ) ´ –− 1
E M c o m m , s a m e = " 2 K v
N   ˆ v r d p 2
m l
c 2
+
2 p m l p p l
c 2
+ ˆ v r d “ ( p m r + p m l ) 2 − p 2
m l ” + 2 p m r ( p p r + p p l ) + 2 p m l p p r ! # − 1
are the expected meeting time for nodes with non- overlapping and overlapping communities, respectively.
As a special case, in some real- life situations each node tends to move most of the time in a very
small area that is different for each node ( e. g. at home), and that could be entirely covered by the node’s
antenna, while the network might be much larger ( e. g. a city- wide wireless Metropolitan Area Network). In
this case, the probability distribution for the meeting time can be again approximated by a single exponential,
simplifying some derivative results.
Corollary 4.1 ( Small Community) When the community size of nodes is much smaller than the network
area ( k C i k ≪ N ) , the meeting time E M ( s m a l l )
c o m m under the Community- based Random Direction model is
exponentially distributed with mean value:
E M ( s m a l l )
c o m m =
E T r d + 1 − p r
1 − p l
N
2 K L
T
l
s t o p
p c
m ˆ v r d + 2 ( 1 − p c
m )
, ( 16)
where p c
m = ( 1 − p l ) L / v
( 1 − p r ) T
l
s t o p + ( 1 − p l ) T r
.
Inter- meeting Time: To calculate the inter- meeting times, we again condition on the two subcases of over-lapping
and non- overlapping communities. We first state the result for the simpler case of non- overlapping
communities.
33
10 20 30 40 50 60 70
0
2000
4000
6000
8000
10000
12000
14000
K
Expected Meeting Time ( time units)
Simulation ( c= 0.1)
Theoretical ( c= 0.1)
Simulation ( c= 0.25)
Theoretical ( c= 0.25)
( a)
10 20 30 40 50 60 70
0
2000
4000
6000
8000
10000
12000
14000
K
Expected Inter− meeting Time ( time units)
Simulation ( c= 0.1)
Theoretical ( c= 0.1)
Simulation ( c= 0.25)
Theoretical ( c= 0.25)
( b)
Figure 18: Simulation and analytical results for the Community- based mobility model. ( a) Meeting time. ( b)
Inter- meeting time. Network parameters: N = 5 0 0 × 5 0 0 , L = 1 5 0 , p l = 0 . 9 , p r = 0 . 5 , v = 1 . 0 , T s t o p =
T
l
s t o p = 0 .
Lemma 4.2 The expected inter- meeting time for nodes with non- overlapped communities is E M +
c o m m , d i f f =
E M c o m m , d i f f .
When the communities of the two nodes overlap, then the situation becomes slightly more complicated.
Specifically, if the two nodes meet within their community, there is a high probability that they will meet
again quite fast. The following lemma states the result.
Lemma 4.3 The expected inter- meeting time for nodes with overlapping communities is
E M +
c o m m , s a m e = p + 1
E [ M +
1 ] + p + 2
E [ M +
2 ] + ( 1 − p + 1
− p + 2
) E M c o m m , s a m e , ( 17)
where ( i) p + 1
is the probability that when the two nodes met, both were in their local states and only one of the
nodes was moving, and E [ M +
1 ] is the expected inter- meeting time for this case, ( iii) p + 2
is the probability that
when the two nodes met, both were in their local states and moving, and E [ M +
2 ] is the expected inter- meeting
time for this latter case.
We next state the value of the expected inter- meeting time, E M +
c o m m , in terms of E M +
c o m m , s a m e and
E M +
c o m m , d i f f in the following theorem.
Theorem 4.2 The expected inter- meeting time of the Community- based mobility model is
E M +
c o m m = ( 1 − c 2 ) E M +
c o m m , d i f f + c 2 E M +
c o m m , s a m e . ( 18)
More results as well as the derivation of all the results presented in this section and the expressions for
p + 1
, E [ M +
1 ] , p + 2
and E [ M +
2 ] can be found in [ 36].
Accuracy of the Analysis: Figures 18( a) and 18( b) compare the analytical and simulation results for the
expected meeting and inter- meeting times under the Community- based mobility model. As can be seen,
theory matches simulations quite closely.
4.4 Analyzing Spraying- based Routing Schemes
In this section, we state the expected delay values for epidemic routing, fast spray and wait and fast spray
and focus. Please refer to [ 26] for the derivation of these values. We study epidemic routing as it forms
34
the basic building block of fast spraying. To simplify the presentation in this section, we assume that there
are r small communities, and these communities are assumed to be small enough such that all nodes within a
community are within each other’s range. We also assume that the nodes spend most of their time within their
respective communities. Finally, we assume that the number of nodes sharing a community is equal across all
r communities, that is the number of nodes sharing a community is equal to M
r .
4.4.1 Epidemic Routing
This section derives the expected delay of epidemic routing for the community- based mobility model. Since
each node spends most of its time within its community ( which implies E [ M c o m m , d i f f ] > > E [ M c o m m , s a m e ] ),
we make an approximation to simplify the exposition by assuming that with high probability, a node starting
from its stationary location distribution will first meet a node within its own community than a node belong-ing
to a different community. This implies that once a node gets a copy of a packet, with high probability,
all members of its community will get the copy before any node outside its community. A simple outcome of
this is that the first M
r − 1 nodes to get a copy of the packet belong to the source’s community.
We first state how much time it takes for all nodes within the source’s community to get a copy of the
packet. This derivation is different from all the derivations in previous sections because E [ M c o m m , s a m e ] 6 =
E [ M +
c o m m , s a m e ] . Thus, we need to keep track of which pair of nodes have met in the past but were unable
to successfully exchange the packet. We model the system using the following state space: ( m , m p ) where
1 ≤ m ≤ M
r is the number of nodes which have a copy of the packet and 0 ≤ m p ≤ m 􀀀 M
r − m  is the number
of node pairs such that only one node of the pair has a copy of the packet, they have met at least once after
the node ( which has the copy) received its copy, and they were unable to successfully exchange this packet
in their past meetings. Let E [ D i n ( m ) ] denote the expected time it takes for the number of nodes having a
copy of the packet to increase from m to m + 1 given m < M
r ( which implies that all nodes within the source’s
community have not yet received a copy of the packet).
Lemma 4.4 E [ D i n ( m ) ] = P
m ( M
r − m )
m p = 0 p m , m p
E [ T m , m p ]
1 − p s e l f
m , m p
, where E [ T m , m p ] is the expected time elapsed till one
of the nodes not having a copy meets a node having a copy of the packet given that the system is in state
( m , m p ) , p s e l f
m , m p is the probability that the system remains in the state ( m , m p ) after these nodes ( which met
after E [ T m , m p ] ) are unable to successfully exchange the packet, and p m , m p is the probability that the system
visits state ( m , m p ) .
Please refer to [ 26] for the expressions of E [ T m , m p ] , p s e l f
m , m p and p m , m p .
Next, we state the value of E [ D c o m m
e p i d e m i c ( m ) ] which is the expected time it takes for the number of nodes
having a copy of the packet to increase from m to m + 1 .
Lemma 4.5 E [ D c o m m
e p i d e m i c ( m ) ] = ( E [ D i n 􀀀 rem 􀀀 m , M
r   if rem 􀀀 m , M
r  6 = 0
E [ M c o m m , d i f f ]
m ( M − m ) p e p i d e m i c
s u c c e s s 2
if rem 􀀀 m , M
r  = 0
where p e p i d e m i c
s u c c e s s 2 = 1 −
 1 − p e p i d e m i c
t x S 2  E [  c o m m , d i f f ]
and rem ( x , y ) is the remainder left after dividing x by y .
Finally, we derive the expected delay of epidemic routing for the community based mobility model
( denoted by E [ D c o m m
e p i d e m i c ] ) in terms of E [ D c o m m
e p i d e m i c ( m ) ] .
Theorem 4.3 E [ D c o m m
e p i d e m i c ] = P M − 1
i = 1
1
M − 1 P i
m = 1 E [ D c o m m
e p i d e m i c ( m ) ] .
35
4.4.2 Fast Spray and Wait
This section derives the expected delay of fast spray and wait routing scheme for the community- based
mobility model. As before, first we derive the value of E [ D c o m m
f s w ( m ) ] . For m < L ( in the spray phase), the
value of E [ D c o m m
f s w ( m ) ] is derived in a manner similar to the derivation of E [ D c o m m
e p i d e m i c ( m ) ] as flooding is used
to spread the L copies in the spray phase. Next, we state the value of E [ D c o m m
f s w ( L ) ] which is the expected time
to find the destination in the wait phase.
Lemma 4.6 E [ D c o m m
f s w ( L ) ] =
M
r − ˆ l
M − L  P
ˆ l
( M
r − ˆ l
)
m p = 0 p ˆ l
, m p
E [ T m p
M
r − ˆ l
]  +  1 −
M
r − ˆ l
M − L  E [ M c o m m , d i f f ]
L p f s w
s u c c e s s 2
, where ˆ l
= rem 􀀀 L , M
r  ,
E [ T s ] is the expected time till the destination receives a copy of the packet given there are s nodes belonging
to the destination’s community which were unable to successfully exchange the packet with the destination in
the past, and p f s w
s u c c e s s 2 = 1 −  1 − p f s w
t x S 2  E [  c o m m , d i f f ]
.
Finally, we derive the expected delay of fast spray and wait for the community based mobility model
( denoted by E [ D c o m m
f s w ] ) in terms of E [ D c o m m
f s w ( m ) ] .
Theorem 4.4 E [ D c o m m
f s w ] = P L
i = 1 p f s w
d e s t ( i ) P i
m = 1 E [ D c o m m
f s w ( m ) ] .
200 400 600 800 1000
0
10
20
30
40
Target Expected Delay ( time slots)
Average number of Transmissions
Fast Spray and Wait ( with contention)
Fast Spray and Focus ( with contention)
Fast Spray and Wait ( without contention)
Fast Spray and Focus ( without contention)
Figure 19: Comparison of fast spray and wait and fast spray and focus. Average number of transmissions required
to deliver the packet to the destination vs target expected delay. Network parameters: N = 5 0 0 × 5 0 0 square units,
M = 4 0 , K = 2 0 ,  = 5 , s B W = 1 packet/ time slot, p l = 0 . 8 , p r = 0 . 1 5 , r = 4 .
4.4.3 Fast Spray and Focus
For community- based mobility models, [ 25] proposed the use of a simpler function as a utility function for
their ‘ Label’ scheme: If a relay meets a node which belongs to the same community as the destination, the
relay hands over its copy to the new node. We use this simple and effective utility function to route copies of
the packet in the focus phase. For example, handing over the copy of the packet to a vehicle which shares the
parking lot with the destination will get the message delivered faster and reliably.
This section derives the expected delay of fast spray and focus for the community- based mobility model.
As before, first we derive E [ D c o m m
f s f ( m ) ] . Since flooding is used to spread the copies in the spray phase,
36
E [ D c o m m
f s f ( m ) ] for m < L can be derived in a manner similar to the derivation of E [ D c o m m
e p i d e m i c ( m ) ] . The next
lemma derives the value of E [ D c o m m
f s f ( L ) ] which is the expected time it takes for the packet to get delivered to
the destination in the focus phase.
Lemma 4.7 E [ D c o m m
f s f ( L ) ] =
M
r − ˆ l
M − L   P
ˆ l
( M
r − ˆ l )
m p = 0 p ˆ l
, m p
E [ T m p
M
r − ˆ l
] ! + „ 1 −
M
r − ˆ l
M − L « „ E [ M c o m m , d i f f ]
L M
r
p
f s f
s u c c e s s 2
+
M
r − 1
M
r “ E [ M c o m m , s a m e ]
+
( 1 − p
f s f
s u c c e s s s 1 ) E [ M +
c o m m , s a m e ]
p
f s f
s u c c e s s 1 ” « , where ˆ l
= rem 􀀀 L , M
r  , p f s f
s u c c e s s 1 = 1 −  1 − p f s w
t x S 1  E [  c o m m , d i f f ]
and p f s f
s u c c e s s 2 =
1 −  1 − p f s w
t x S 2  E [  c o m m , s a m e ]
.
Now we derive the expected delay of fast spray and focus for the community based mobility model
( denoted by E [ D c o m m
f s f ] ) in terms of E [ D c o m m
f s f ( m ) ] .
Theorem 4.5 E [ D c o m m
f s f ] = P L
i = 1 p f s f
d e s t ( i ) P i
m = 1 E [ D c o m m
f s f ( m ) ] , where p f s f
d e s t ( i ) =  1
M − 1 i < L
M − L
M − 1 i = L
.
We now use the analysis presented in this section to validate the claims made in Section 3.7.3 through
a numerical example. We study how much performance gains are achieved by spray and focus over spray and
wait ( for the community- based mobility model) both with and without contention in the network by plotting
the minimum value of the average number of transmissions it takes to achieve a given target expected
delay for both the schemes in Figure 19. We first find the minimum value of L which achieves the given
target expected delay for both the schemes and then find the average number of transmissions which is equal
to P L
i = 1 i p R d e s t ( i ) . ( The minimum value of L is computed using the analytical expressions derived in this sec-tion.
The value of p R d e s t ( i ) for both the schemes was derived in Theorems 4.4 and 4.5.) We observe that fast
spray and focus outperforms fast spray and wait even with contention in the network, with gains being larger
with contention. Since E [ M c o m m , d i f f ] > > E [ M c o m m , s a m e ] , forwarding a copy to any node in the destina-tion’s
community in the focus phase significantly reduces the delay for the same L without significantly increas-ing
the contention as it requires only one extra message per copy. Hence, fast spray and focus shows more per-formance
gains over fast spray and wait after incorporating contention.
5 Support for Multicasting
While there are safety applications that involve two vehicles only, for example, applications that prevent
accidents resulting from changing lanes when a vehicle is in the blind spot of another, the majority of safety
applications, or example, pre- and post- crash warnings, involve a large number of vehicles.
In such one- to- many communication scenarios it is important to avoid duplicate transmissions. To under-stand
what this means, consider a scenario where two vehicles 0 1 and 0 2 have a collision on a highway which
results in blocking a number of lanes. These vehicles would broadcast a warning message, that would be
received by vehicles close to the collision, say vehicles 1 i , i = 1 , 2 , 3 , . . .. These vehicles, in turn, would
forward the warning message to vehicles further away from the collision, say vehicles 2 i , i = 1 , 2 , 3 , . . .. A
duplicate transmission would result if 0 i would send two messages to 1 i , one for itself and one to be
forwarded to 2 i . A duplicate transmission would also result if 2 i would directly receive a second warning
message from 0 i once it is closer to the collision. Simple rules, translated into utility values for each potential
receiver can be used to suppress such duplicate transmissions.
To suppress duplicate transmissions, we use the following idea. Let 0 1 and 0 2 broadcast