
small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


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 reasons. 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 Communication 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 delivered 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. Finally, it has also been proposed that ideas fromnetwork coding could be useful to reduce the number of bytes transmitted 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 fading [ 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 mobilityassisted 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 disconnected 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 routing 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 protocol 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 implementation. 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 message 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. Additionally, 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 expressions 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 distributed 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 vehicles [ 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 exponentially 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 ensemble 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 “ coupled” 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 measures 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 altogether, 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 waypoint 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 performance 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 maintains 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 encounter 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 different 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 channel. 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 (“ optimal”). ( 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. ( Specifically, 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 function 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 networks 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 connectivity 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 Utility Flooding can improve the performance of epidemic routing they still have to perform way too many transmissions 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 connectivity. 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 transmission 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 destination, 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 communicating 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 distance 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 probability 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 simplify 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 different 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 distribution 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 direction 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 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 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 scheduler. 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 distance 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 between 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. Commonly used mobility models like random direction and random waypoint on a torus satisfy this assumption [ 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 exchange. 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 simultaneous 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 assume 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 taking place within one hop fromthe transmitter and the receiver, there is no restriction on simultaneous transmissions 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 probability 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 exchange 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 analysis, we make our first approximation here by replacing the random variable S by its expected value in the expression 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 interference 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 analysis. 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 achievable 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 intermeeting 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 geographic 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 direction 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 spatial 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 always 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 different 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 frequently 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 preference, 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 probability 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 timedependencies. 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 characteristics, 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 overlapping 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 belonging 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 section. 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 destination’s community in the focus phase significantly reduces the delay for the same L without significantly increasing the contention as it requires only one extra message per copy. Hence, fast spray and focus shows more performance 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 understand 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
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  Efficient routing for safety applications in vehicular networks 
Subject  Traffic safety.; Highway communications. 
Description  Text document in PDF format.; Title from PDF title page (viewed on August 1, 2009).; "March 2009."; Includes bibliographical references (p. 4042).; Performed under METRANS Project no. 
Creator  Psounis, Konstantinos. 
Publisher  METRANS 
Contributors  University of Southern California. Dept. of Electrical Engineering.; METRANS Transportation Center (Calif.) 
Type  Text 
Identifier  http://www.dot.ca.gov/newtech/researchreports/reports/2009/0812_final_report.pdf 
Language  eng 
Relation  http://worldcat.org/oclc/428900965/viewonline 
DateIssued  [2009] 
FormatExtent  42 p. : digital, PDF file (551 KB) with charts. 
RelationRequires  Mode of access: World Wide Web. 
Transcript  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 reasons. 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 Communication 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 delivered 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. Finally, it has also been proposed that ideas fromnetwork coding could be useful to reduce the number of bytes transmitted 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 fading [ 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 mobilityassisted 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 disconnected 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 routing 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 protocol 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 implementation. 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 message 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. Additionally, 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 expressions 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 distributed 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 vehicles [ 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 exponentially 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 ensemble 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 “ coupled” 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 measures 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 altogether, 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 waypoint 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 performance 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 maintains 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 encounter 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 different 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 channel. 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 (“ optimal”). ( 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. ( Specifically, 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 function 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 networks 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 connectivity 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 Utility Flooding can improve the performance of epidemic routing they still have to perform way too many transmissions 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 connectivity. 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 transmission 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 destination, 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 communicating 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 distance 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 probability 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 simplify 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 different 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 distribution 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 direction 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 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 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 scheduler. 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 distance 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 between 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. Commonly used mobility models like random direction and random waypoint on a torus satisfy this assumption [ 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 exchange. 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 simultaneous 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 assume 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 taking place within one hop fromthe transmitter and the receiver, there is no restriction on simultaneous transmissions 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 probability 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 exchange 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 analysis, we make our first approximation here by replacing the random variable S by its expected value in the expression 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 interference 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 analysis. 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 achievable 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 intermeeting 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 geographic 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 direction 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 spatial 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 always 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 different 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 frequently 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 preference, 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 probability 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 timedependencies. 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 characteristics, 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 overlapping 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 belonging 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 section. 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 destination’s community in the focus phase significantly reduces the delay for the same L without significantly increasing the contention as it requires only one extra message per copy. Hence, fast spray and focus shows more performance 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 understand 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 



B 

C 

I 

S 


