Sage Journals: Discover world-class research

Abstract

Real-time information about the state (location, speed, and direction) of other vehicles in the system is critical for both safety and navigation applications in future intelligent transportation systems. However, reliably obtaining this information over multiple hops in a capacity constrained, contention-prone wireless network poses a significant challenge. In this paper, we describe an algorithm VCAST that addresses this challenge by exploiting a notion of distance sensitivity in information propagation, in which information is forwarded at a rate that decreases linearly with distance from the source. By doing so, the required communication overhead per node can be significantly reduced, thereby reducing channel contention, allowing higher information supply rates, and scaling to larger network sizes. VCAST can be used to improve safety against collisions and to enable dynamic routing and navigation techniques by providing aggregate traffic information in an extended neighborhood. The performance of VCAST is validated using extensive ns-3 simulations under different network sizes and densities with an IEEE 802.11b transmission model and the advantages of VCAST in comparison to non-distance-sensitive approaches are highlighted.

1. Introduction

Infrastructureless, vehicle-to-vehicle (V2V) wireless communication is expected to be the basis for both safety and navigation applications in future intelligent transportation systems [1, 2]. Examples of safety applications in transportation scenarios include collision warnings, guidance on lane change and lane merge, and stopped vehicle alert. Examples of intelligent navigation applications include dynamic travel-time computations and rerouting based on real-time traffic information. A building block for all these applications is a real-time vehicular traffic mapping system on board every vehicle, which portrays information about current position of other vehicles in its vicinity and provides guidance about accidents, approaching emergency vehicles and traffic congestion over an extended neighborhood. In this paper, we design VCAST, a scalable, infrastructureless, peer-to-peer wireless network service for computing such a real-time traffic map over a given region surrounding each vehicle (This paper is a significant extension of a shorter version that appeared in IEEE VTC 2012 [3]. The specific additions are as follows. (1) Simulations are carried out in ns-3 using an IEEE 802.11 b transmission model to quantify the impact of network size, vehicular density, vehicular mobility, and time-varying intervehicular separations on the achievable staleness. (2) The average communication cost incurred by each vehicle is quantified. (3) The performance is compared analytically and using simulations with schemes that do not incorporate distance sensitivity, and the significant impact on scalability using VCAST is highlighted. (4) Complete proofs are included for all lemmas and theorems).

We assume that vehicles are equipped with a differential GPS that can estimate its location to an accuracy of about 1-2 m. As a result, by advertising this information, vehicles can learn about traffic within a one hop communication range. However, estimating traffic maps over a large area using multihop wireless communication is a much more challenging task. (1) Firstly, we note that forwarding each vehicle's information over multiple hops at a constant rate is unlikely to be scalable as it will cause the amount of communication required at each vehicle to grow with the number of vehicles in the region over which traffic information is required. As a result, both the allowable broadcast rate and the accuracy of the traffic map obtained at each vehicle will decrease as vehicular density and size of the region increase. Hence effective forwarding algorithms need to be designed to ensure that the system remains scalable with vehicular density, information supply rate, and region size. (2) Secondly, there exist tradeoffs in choosing the rate and communication range of each broadcast. While higher broadcast rates and range promise greater tracking accuracy, in reality wireless channel contention can cause an adverse effect in tracking accuracy as these levels exceed a certain limit. Existing broadcast techniques for vehicular safety systems have primarily focused on balancing transmission rate and communication range to maximize the reliability of single hop wireless communication. However, in such an approach information about other vehicles is available only when intervehicular distance is too small which may not be enough to avert a collision [4] or to provide a timely re-route in the presence of traffic congestion. On the other hand, increasing the single-hop communication range or moving to multihop forwarding techniques to learn about vehicles in a larger area quickly decreases the achievable information supply rate from each vehicle (even those at smaller distances). Hence, there remains a need for multihop broadcasting techniques that are able to supply timely information over large distances without compromising on data supply rates at smaller distances.

Contributions. To address the above challenges and to ensure scalability when providing traffic maps over large regions in real time, we exploit a notion of distance sensitivity in propagating individual vehicle information: information about each vehicle is propagated at a rate that decreases linearly with the distance from the vehicle [5, 6]. The rationale behind exploiting distance sensitivity is that the reaction time available to a vehicle for taking safety actions or for computing new routes towards the destination is lesser with respect to the state of nearby vehicles than that of farther vehicles. VCAST maps this distance-dependent reaction time into delivery of information with quality that progressively decays as a function of distance.

We use staleness in vehicular state information as a metric for information quality as it reflects how old the current information about a particular vehicle is and show that traffic information in VCAST can be obtained with a worst-case staleness that is bounded by $O (d^{2})$ where d is the distance from the source of the information. Thus, VCAST provides traffic information with distance-sensitive precision in which the error does not grow with the number of vehicles in the region and is independent of traffic density and network size. At the same time, the average communication cost (the required transmission rate at each node) also is only bounded by $O (p \sqrt{N})$ , where p is the broadcast rate at the source. Lower communication overhead per node ensures lower channel contention and higher source broadcast rates, thus benefiting information supply at smaller distances. VCAST can be used to propagate actual vehicle location as well as to propagate aggregate traffic information such as average speed and density of vehicles over individual traffic cells inside a region. One possible scenario is to propagate actual vehicle location up to a distance of 500–1000 m and aggregate traffic information up to several miles. When propagating only aggregate cell information, we note that the required communication rate per node decreases further by a factor $r_{c}$ , where $r_{c}$ is the radius of each aggregation cell.

The performance of VCAST is validated using extensive simulations in ns-3, a discrete event simulator for wireless networks, under different network sizes, network densities, source broadcast rates, and communication ranges. The results of our evaluation show that, by using distance-sensitive forwarding, VCAST is able to scale to larger network sizes as well as support much higher broadcast rates compared to non-distance-sensitive techniques. The reason for scalability was shown to be the significantly lower message overhead which reduces the channel contention in the network. We have also characterized the performance of VCAST under severe random mobility and studied information staleness when aggregated data is transmitted as opposed to individual vehicle information.

Impact. By forwarding traffic information over multiple communication hops, we expect several advantages: (1) vehicle location over a vicinity will be available even if the communication range is extremely low because of high density, thus improving vehicular safety, (2) information about approaching emergency vehicles will be available, (3) information about lane changing and merging vehicles will be available even if they are outside a single communication range, and (4) information about road blocks, accidents, and impending congestion will be available from several miles ahead, thus permitting higher level applications that dynamically re-route based on this information. Some of these scenarios, from a vehicular safety perspective, are illustrated in Figure 1. To achieve scalability, VCAST provides traffic information with an accuracy that degrades with distance, but we expect this to be a reasonable condition that is still sufficient for both vehicular safety and intelligent navigation. Finally, we note that VCAST does not require any special hardware or modification to vehicular transmission standards; instead, it can simply piggyback on the proposed Here I am communication [1, 2] for vehicular networks.

Figure 1

Utilization of multihop vehicular information for safety applications. The arrows indicate multihop information flow towards car C. Knowledge of states of A and D will guarantee safe lane change to left and right, respectively. Knowledge of congestion will allow safe, timely reaction.

Outline of the Paper. In Section 2, we describe related work. In Section 3, we describe our system model, the VCAST algorithm, and provide an analysis for the expected accuracy and communication cost. In Section 4, we evaluate the performance of our system in simulations. In Section 5, we present conclusions and state future work.

2. Related Work

The design of routing protocols for vehicular ad hoc networks and more generally in mobile ad hoc networks is a well-researched topic and a good survey of these techniques can be found in [7–9]. Many of these protocols have focused on delivering aperiodic, low bandwidth data such as emergency vehicle information to either a single vehicle (unicast) or a group of vehicles in a geographic region (geocast) with low latency [10–17]. On the other hand, the focus in this paper is on broadcasting information from each vehicle at high rates to support the design of safety and navigation applications.

The design of wireless broadcast protocols has also received a lot of research attention lately [1, 18–22] in the context of vehicular safety applications. There have been several recent papers that have focused on the problem of balancing broadcast range and reliability so as to maximize the number of successful receptions in close proximity of the sender [18–21]. A common foundation in these papers to handle the tradeoff is to reduce the communication range in regions of high density so as to improve the reliability of reception. However, these papers mainly focus on reliable one-hop message reception and not on multihop propagation. As a result, the information about vehicles outside the communication range is not available even when the range has to be very low because of high density. The trade-off in single-hop broadcast schemes is that a higher communication range causes larger staleness even for nearby vehicles, while a lower communication range prevents information availability from beyond that range. On the other hand, the algorithm developed in this paper can be used to propagate both individual vehicle information and aggregate traffic information over several communication hops and yet retain high data supply rates at smaller distances.

We also note that rate and power control algorithms [1, 18–21] developed for a single hop vehicular broadcast are complementary and can be used in conjunction with the distance-sensitive multihop forwarding algorithm designed in this paper. Thus decisions on source broadcast rate and range can be made commensurate with traffic density using the techniques proposed in [1, 18–21], and VCAST can be used to aggregate and forward this information over multiple hops.

Multihop broadcast algorithms [23–29] for vehicular networks have mainly focused on the choice of optimal forwarding vehicles and on the reduction of redundant forwarding vehicles using one of several heuristics proposed in [30]. A good survey of multihop broadcast techniques in mobile ad hoc networks is presented in [31]. The idea of distance-sensitive broadcasting rates developed in this paper for ensuring scalable all-all information broadcast has thus far not been explored in the context of mobile ad-hoc and vehicular networks. The improvement in communication overhead gained by exploiting distance sensitivity is characterized in Section 3.3.

The concept of distance sensitivity has previously found applications in several other networking fields in different forms. For example, route aggregation in the Internet utilizes this concept for efficiently distributing routing information [32]. Fisheye routing [33] uses this idea to propagate routing tables in mobile ad hoc networks. Fractionally cascaded information [34] is a form of distance-sensitive key sharing that is widely used for speeding up traversal of data structures. Distance sensitivity has also been used in wireless sensor network based querying and tracking applications to model communication latency and information quality as functions of distance [35–38]. In the context of network-wide continuous broadcast of system states, an algorithm has been designed in [39] for supplying global state information to all nodes in a static sensor network with distance-sensitive latency and error. In this paper, we show that distance sensitivity is a valuable tool for efficient and scalable propagation of state information even for networks of mobile nodes (vehicles). Unlike the algorithm in [39], we design VCAST without assuming an underlying clustering or routing structure, thus avoiding the need for maintenance related communication.

3. System Description

In this section, we first state the system model and objective. We then describe VCAST and analytically characterize its accuracy and required communication rate.

3.1. System Model and Problem Statement

We model the vehicular network as a large geographic area with multiple traffic flows, each with potentially different traffic densities at different places. Let ρ denote the maximum density, that is, the maximum number of vehicles per unit area at any time in the whole region. Note that the geographic area will consist of regions with no traffic flows (i.e., no roads), as well as regions with high density traffic flows. When analyzing the impact of aggregation, we assume that the region is partitioned into geographic cells which allow representation of aggregated traffic information for that cell. The cells need not be of the same size, but for ease of explanation we assume that the area of each cell is constant and equal to $A_{C}$ with a radius of $r_{c}$ . In a realistic environment, these cells could be used to model critical traffic links such as the traffic in a region between two highway exits or traffic between two urban streets. Let $r_{h}$ denote the single hop communication range for a vehicle. The objective of our system is to provide each vehicle with information about all vehicles and all cells within a radius R around itself where $r_{h} ≪ R$ . We call this area of radius R around each vehicle the tracking zone (We note that our system can also be specialized to propagate individual vehicle information within a smaller radius than aggregate cell information).

Let N denote the maximum number of vehicles within the tracking zone of each vehicle. Thus $N = ρ π R^{2}$ . Let L denote the maximum number of cells in a radius of R around each vehicle. Thus $L = O (R^{2} / A_{c})$ . Note that by using a two dimensional model for the vehicular network, the bounds on communication cost in our analysis are expected to hold for dense urban traffic scenarios as well as highway traffic scenarios in which the number of vehicles is expected to be lower.

Let p denote the frequency at which each vehicle broadcasts its own information. Let $d (i, j)$ denote the geographic distance between vehicles i and j. Let $d_{c} (i, j)$ denote the distance between vehicle i and cell j in terms of the smallest number of cells traversed to reach cell j from i. In the following subsections, we first describe VCAST assuming that only vehicle location is propagated up to a distance R. Then we describe the required changes when aggregate cell information is propagated. The communication cost and accuracy for both these cases are characterized in Section 3.3.

3.2. Distance-Sensitive Broadcast Algorithm

A naive technique would be to require each vehicle to obtain information about all vehicles in its tracking zone at a constant interval of $1 / p$ seconds. However, in such a scenario each vehicle would have to broadcast information about at most N vehicles at p Hz, making the required communication rate at each node per unit time $O (N p)$ . Note that the required communication rate grows with the number of vehicles in the region and is therefore directly proportional to the vehicle density and the area of the region. Also if C denotes the allowable wireless channel transmission capacity at a node in bits per second, we observe that the allowable broadcast rate p is limited by $p < C / N$ , that is, inversely proportional to the number of vehicles. This in turn has an adverse effect on the latency with which traffic information is obtained and as a result the accuracy of the obtained traffic map information decreases with increasing vehicular density, which is not desirable.

To address these drawbacks, we propose to forward information about a vehicle at a rate that is proportional to the distance from that vehicle. Also, in VCAST, a vehicle suppresses forwarding of information about a vehicle in an interval, if some other vehicle has already forwarded information about the respective vehicle in that interval. By doing so, we show that the communication cost can be significantly reduced, leading to scalability. A more formal description of VCAST is presented below. A pseudocode in guarded command notation [40] is provided in Algorithm 1, which shows the program at each vehicle in the form of $〈 e v e n t \to a c t i o n 〉$ pairs.

Algorithm 1: VCAST: protocol actions at vehicle j.

Protocol: VCAST

Vehicle: j

Var:

$j \cdot V$ : List of vehicles within radius R

$j \cdot X_{i} \forall i \in V$ : Location of i

$j \cdot T_{i} \forall i \in V$ : Timestamp of i's record

$j \cdot ν_{i} \forall i \in V$ : Counter for i's information

$j \cdot λ$ : Sequence number of current interval

$j \cdot V_{λ}$ : Forwarding list for $j \cdot λ$

Actions:

$〈 A_{1} 〉$ :: Initialization: ⟶

$j \cdot V = j; j \cdot ν_{i} = 0; j \cdot λ = 0$ ;

Timer.start $(\frac{1}{p})$

$〈 A_{2} 〉$ :: Timer fired: ⟶

$j \cdot λ = j \cdot λ + 1$ ;

$j \cdot V_{λ} = j$ ;

$\forall i \in j \cdot V$

if (λ mod $d_{h} (i, j)$ == 0)

if $j \cdot ν_{i} < 2$

Add i to $j \cdot V_{λ}$

$j \cdot ν_{i} = 0$ ;

$\forall i \in j \cdot V_{λ}$

Send $j \cdot X_{i}, j \cdot T_{i}$

$〈 A_{3} 〉$ :: ${recv}_{i} (V)$ ⟶

$\forall k \in i \cdot V$

if $((j \cdot T_{k} < i \cdot T_{k}) \lor (k \notin j \cdot V))$

$j \cdot X_{k} = i \cdot X_{k}$ ; $j \cdot T_{k} = i \cdot T_{k}$ ; $j \cdot ν_{k} = 1$ ;

elseif $(j \cdot T_{k} = = i \cdot T_{k})$

$j \cdot ν_{k} = j \cdot ν_{k} + 1$

In VCAST, each vehicle j maintains a list $j \cdot V$ of vehicles that are within a distance R from itself. Associated with each vehicle $i \in j \cdot V$ is the location $j \cdot X_{i}$ of i as most recently heard by j, a timestamp $j \cdot T_{i}$ associated with the location and $j \cdot ν_{i}$ which is the number of times information about i has been heard since the last broadcast interval. A timer is fired at each vehicle every $1 / p$ seconds for broadcasting information and a randomness is introduced in this interval because of CSMA based transmission. Let $λ = 1,2, \dots$ denote the timer sequence at vehicle j. Let $j \cdot V_{λ}$ denote the set of vehicles whose information is forwarded in the interval number λ at vehicle j. $j \cdot V_{λ}$ is initially set to be equal to ${j}$ . Thus information about itself is broadcasted by a vehicle in every interval along with the current time which serves as the timestamp for this record. Node i is added into the set $j \cdot V_{λ}$ only if $λ \mod d_{h} (i, j) = 0$ and if information about i has not been broadcasted by any other vehicle within j's range in the last $d_{h} (i, j)$ intervals. This ensures that information about nodes at a distance of k communication hops is broadcasted at most once every k interval in each communication neighborhood. In the presence of channel interference, we note that nodes may occasionally duplicate the transmission of information of a vehicle within a neighborhood. But we expect this to cause a much smaller overhead when compared with all nodes transmitting. Finally, whenever information about a vehicle i is heard by a node j, it is added to the list $j \cdot V$ if the timestamp of the incoming record is more recent than $j \cdot T_{i}$ .

For the case where aggregate traffic information is to be propagated, each vehicle computes summary information such as density and average speed for the cell in which it resides based on the information it possesses about vehicles within its communication range. This summary is then propagated in a distance-sensitive manner: information about a cell at distance $d_{c}$ is forwarded at a rate of $p / d_{c}$ Hz.

3.3. Analysis

Theorem 1.

The average amount of data communicated per unit time by each node in VCAST to obtain information about all vehicles within a distance of R from itself is bounded by $O (R p / r_{h})$ .

Proof.

Let B denote the average amount of data communicated per unit time, by each node in VCAST. We discretize distance in intervals of $r_{h}$ (the communication range), as information forwarding rate decreases linearly after each time a vehicle's information is forwarded. The number of vehicles at a distance of at most $h r_{h}$ away from a vehicle is bounded by $O (ρ h^{2} r_{h}^{2})$ . The number of vehicles at a distance of at most $(h - 1) r_{h}$ away from a vehicle is bounded by $O (ρ h^{2} r_{h}^{2})$ . As a result, the number of vehicles between a distance of $h r_{h}$ and $(h - 1) r_{h}$ away from a vehicle is bounded by $O (ρ h r_{h}^{2})$ . Let us denote this as the distance interval h from the vehicle in terms of the communication range. Note that information about vehicles between a distance of $h r_{h}$ and $(h - 1) r_{h}$ is broadcasted only at $p / h$ Hz. Thus the total amount of data to be communicated about vehicles in the distance interval of h is $O (ρ p r_{h}^{2})$ . Note that this information is broadcasted by at most one vehicle in every area $π r_{h}^{2}$ . Hence, on average each node is responsible for communicating only $O (ρ p r_{h}^{2} / ρ r_{h}^{2})$ bits about vehicles at distance interval h from itself. Summing up over all distance intervals and by noting that each vehicle broadcasts its own state at p Hz, we get

\begin{matrix} B = O (p + \sum_{i = 1}^{(R / r_{h})} \frac{ρ p r_{h}^{2}}{ρ r_{h}^{2}}) = O (\frac{R p}{r_{h}}) . \end{matrix}

(1)

Note that this result makes an assumption that information about nodes at a distance of k communication hops is broadcasted at most once every k intervals in each communication neighborhood. In the presence of channel contention and hidden terminals, the assumption may be violated causing duplicate transmissions of vehicular information within a communication neighborhood and an increase in the amount of communication per node. The results of our simulation will include the impact of channel contention and duplicate transmissions.

Under a uniform distribution of vehicles in a 2d region, it can be inferred from the results of the previous theorem that the communication cost per node only grows as $O (p \sqrt{N})$ . In contrast, without distance-sensitive forwarding the average communication incurred per node is $O (N)$ , as discussed below.

Comparison with Multihop Broadcast Protocols without Distance Sensitivity. In order to analytically compare the bound on communication cost with multihop broadcast algorithms that do not incorporate distance sensitivity in message forwarding, first consider an algorithm in which information is simply flooded without suppression of redundant messages. In this case, each node broadcasts information about all nodes in the region at a rate of p times every second yielding a communication cost per node that is bounded by $O (ρ p R^{2})$ . This is clearly not scalable with the size of the network, and such an approach is likely to yield severe channel contention thus reducing the achievable broadcast rate p. Several heuristics have been proposed to address this broadcast storm problem so that redundant broadcasts of the same message can be eliminated; that is, information about every vehicle is broadcasted exactly once in every communication neighborhood per interval. In this case, the average communication cost reduces by a factor of $ρ π r_{h}^{2}$ over a naive flooding approach, yielding an average communication cost per node of $O (p (R / r_{h})^{2})$ , that is, $O (p N)$ . Thus, by comparison with Theorem 1, we see that the effective communication cost per node by applying distance-sensitive forwarding rules reduces by a factor of $\sqrt{N}$ . Reducing the amount of communication incurred by each node results in smaller channel contention and allows a higher broadcast rate at smaller distances. This is especially crucial when forwarding information over large areas because it ensures that information supply rates at smaller distances are not penalized for having to forward information over multiple hops.

We now obtain a bound on how outdated the state information possessed by a vehicle is because of distance-sensitive forwarding. We refer to this as staleness in the information possessed by a vehicle.

Definition 2 (staleness (j,i)).

The staleness $S (j, i, t)$ in the state of vehicle i as possessed by vehicle j at time t is the time elapsed since the timestamp of the state of i( $j \cdot T_{i}$ ). Thus $S (j, i, t) = t - j \cdot T_{i}$ .

Note that the staleness with respect to a vehicle is initially equal to the message latency from the source when information about the vehicle is received but continues to rise until the next update from the vehicle is received. The maximum staleness with respect to a vehicle thus occurs just before fresh information about the vehicle is received. Maximum staleness thus depends on the message latency as well as on the update interval. Staleness can further increase when messages containing information about a vehicle are lost. The effect of message losses will be quantified using simulations in Section 4.5.

Theorem 3.

The maximum staleness in the state of vehicle i at vehicle j in VCAST is bounded by $O (d (i, j)^{2} / p r_{h}^{2})$ .

Proof.

Consider a vehicle j at a distance between $h r_{h}$ and $(h - 1) r_{h}$ away from a vehicle i. Let us denote this by a distance-interval h from vehicle i in terms of the communication range $r_{h}$ . Thus $h = ⌈ d (i, j) / r_{h} ⌉$ . Note that at a distance interval of $h - 1$ from a vehicle i, information about i is updated only once every $h - 1$ broadcast interval. As a result, the maximum time before which j hears fresher information about i from some vehicle at distance interval $h - 1$ away from i is bounded by $(h - 1) / p$ seconds. Likewise, the maximum time elapsed between a vehicle at distance-interval $h - 2$ receiving information about i and a vehicle at distance-interval $h - 1$ obtaining the same information is bounded by $(h - 2) / p$ seconds. Summing from a distance interval of $1$ to h, we get that the maximum latency in communicating the state of vehicle i to a vehicle j is bounded by $O (d (i, j)^{2} / p r_{h}^{2})$ .

From Theorem 3, we note that the staleness at a distance d from a vehicle does not depend on the vehicular density or the region size, but only on the communication hop distance and the initial broadcast rate at the source. Hence, we expect that as the communication range increases the staleness should decrease. However, as the communication range increases, the interference within the vehicular transmission also increases and this can adversely affect the network reliability and system accuracy. In Section 4.5, we analyze the performance of our algorithm in large scale simulation and point out the impact of p and $r_{h}$ on the staleness at different distances.

We now state the average communication rate and staleness when aggregate cell information is propagated instead of actual vehicle location information.

Theorem 4.

The amount of data communicated by each node in VCAST per unit time, when aggregate cell information is propagated, to obtain information about each cell at distance up to R from itself is bounded by $O (R p / ρ r_{c} r_{h}^{2})$ .

Proof.

Let $B_{C}$ denote the average amount of data communicated per unit time, by each node in VCAST when aggregate cell information is propagated. Recall that $d_{c} (i, j)$ denotes the cell distance between vehicle i and cell j, that is, the smallest number of cells traversed to reach cell j from i. The number of cells at a cell distance of at most $d_{c}$ from a vehicle is bounded by $O (ρ d_{c}^{2} r_{c}^{2} / ρ r_{c}^{2})$ , that is, $O (d_{c}^{2})$ . As a result, the number of cells at exactly distance $d_{c}$ away from a vehicle is bounded by $O (d_{c})$ . Information about cells at distance $d_{c}$ away is broadcasted at $p / d_{c}$ Hz. Thus the total amount of data to be communicated about cells at distance $d_{c}$ away is $O (p)$ . Note that this information is broadcasted by at most one vehicle in every area $π r_{h}^{2}$ . Hence, on average each node is responsible for communicating only $O (p / ρ r_{h}^{2})$ bits about cells at distance $d_{c}$ away from itself. Summing up over all cell distances from $d_{c} = 1$ to $d_{c} = R / r_{c}$ , we get

\begin{matrix} B_{c} = O (\sum_{i = 1}^{R / r_{c}} \frac{p}{ρ r_{h}^{2}}) = O (\frac{R p}{ρ r_{c} r_{h}^{2}}) . \end{matrix}

(2)

In comparison with the result from Theorem 1, we note that the average communication rate reduces by a factor equal to the number of vehicles in each cell ( $ρ r_{c} r_{h}$ ) because only aggregate information about the cell is propagated with distance-sensitive rate as opposed to propagating information about each vehicle in the cell.

Theorem 5.

The staleness in the state of cell z at vehicle j in VCAST, when aggregate cell information is propagated, is bounded by $O (d_{c} (j, z) d_{h} (j, z) / p)$ , where $d_{h} (j, z)$ denotes the communication hop distance between j and the closest vehicle to j in cell z.

Proof.

Consider a vehicle j and cell z. The lowest broadcast rate about cell z that is available for vehicle j is $d_{c} (j, z) / p$ . Also the number of communication hops between j and the closest vehicle in z is $d_{h} (j, z)$ . Hence, latency in forwarding information about cell z to vehicle j is bounded by $d_{c} (j, z) d_{h} (j, z) / p$ . Also note that the subsequent update about cell z will be available within $d_{c} (j, z) / p$ seconds. The result follows.

4. Performance

We evaluate the performance of VCAST using simulations in ns-3, a discrete event simulator for wireless, and mobile ad hoc networks.

Network Models. We use an IEEE 802.11 b physical layer communication model with a DSSS rate of $11 Mbps$ at each node. We first model vehicular traffic by considering vehicles to be in grids of different sizes ( $28 \times 28, 25 \times 25, 20 \times 20$ , and $15 \times 15$ ) with uniform separation between the vehicles at all times (i.e., traveling with uniform speed). For the case of aggregated data forwarding, we have also simulated a network size of $3600$ nodes which allows us to test over larger intervehicular distances. We consider intervehicular separations of $60 m$ , 50 m, 40 m, and 30 m, thus simulating different densities. Note that a uniform separation of 45 m would correspond to a headway time of 1.5 s at a speed of $70$ mph (and a proportionately lower headway time at lower speed), which are typically observed separations on roadways. We have chosen densities that create vehicular separation around this range. We also consider source broadcast rates of 1 Hz, 5 Hz, and 10 Hz, and communication ranges of 75 m, 100 m, 125 m, and 150 m, which are within the range of expected transmission rate and range values of Here I am messages for intelligent transportation systems [1, 2]. These simulations characterize the performance of VCAST when it is used to disseminate vehicular state information to a network of the corresponding size. The grid model allows us to emulate 2d network traffic of different densities in a region and by simulating uniform velocity, the relative distance between vehicles is maintained during the course of the simulation allowing the clear characterization of distance versus information staleness. We use this model to compare VCAST with non-distance-sensitive approaches and to systematically study the impact of density, source broadcast rates, and communication range on the performance. Next, we consider a 2d model of vehicles with nonuniform mobility incorporated—the goal here is to study if time varying densities impact the performance and therefore we use a random waypoint model to simulate mobility which generalizes possible vehicular traffic patterns.

Measurement Strategy. Each vehicle's state information is assumed to be $10$ bytes long. In any given slot, a vehicle may transmit a variable number of such records. At each vehicle, we measure the maximum staleness with respect to every other vehicle by measuring the time elapsed since the information originated at the source, just before fresh information about a vehicle is received. For information aggregation, we consider the cell size to be equal to the communication range of each vehicle, propagate only aggregate cell information instead of individual vehicle information, and measure the maximum staleness with respect to every cell in the region. All simulations are run for 20 seconds except simulations at 1 Hz which are run for 40 second due to higher staleness values. We then group the maximum staleness based on pairwise distances between vehicle-vehicle and vehicle-cell, respectively. The average of these measurements over multiple experiments is used in our evaluations.

4.1. Impact of Distance Sensitivity

The objective of this section is to quantify the performance gains achieved by using distance-sensitive forwarding as opposed to forwarding information about all vehicles at the same rate.

Scaling in Number of Nodes. In Figure 2(a), we show the maximum staleness as a function of intervehicular distance for $p = 10 Hz$ at a network size of $225$ nodes for both VCAST as well as non-distance-sensitive forwarding; that is, information about all vehicles is forwarded at the source broadcast rate by every node. Here, we observe that the non-distance-sensitive scheme is able to keep staleness low at all distances and the growth is linear with distance. On the other hand, VCAST has low staleness at small distances while the staleness is observed to grow as $O (d^{2})$ at higher distances, as expected. However, at a network size of $625$ (see Figure 2(b)), the non-distance-sensitive approaches show much higher staleness even at smaller distances. However, VCAST is able to maintain low staleness at small distances while the staleness is observed to grow as $O (d^{2})$ at higher distances. Information within 400 m is obtained in under 300 ms using VCAST while it takes about $3$ seconds in the case of a non-distance-sensitive approach. The reason is that as the number of nodes increases, the channel contention increases at a much higher rate in the non-distance-sensitive forwarding causing message losses and consequently increase in staleness (i.e., quantified in our analysis on message complexity). By reducing channel contention, VCAST is able to achieve scalability in number of nodes. In Figure 3, we show the maximum staleness as a function of intervehicular distance for $p = 10 Hz$ at a network size of $225$ , $400$ , $625$ , and $784$ nodes for VCAST. We observe that staleness values are preserved at corresponding intervehicular distances, irrespective of network size.

Figure 2

Impact of network size: VCAST versus non-distance-sensitive forwarding. (a) Maximum staleness versus pairwise vehicular distance: $p = 10$ Hz at $225$ nodes. (b) Maximum staleness versus pairwise vehicular distance: $p = 10$ Hz at $625$ nodes.

Figure 3

Maximum staleness versus pairwise vehicular distance for VCAST: $p = 10$ Hz, network sizes of $225$ , $400$ , $625$ and $784$ vehicles, communication range 100 m, separation 50 m. Staleness values are preserved at corresponding intervehicular distances, irrespective of network size.

Scaling in Source Broadcast Rate. In Figures 4(a) and 4(b), we fix the network size to $784$ nodes and vary the source broadcast rate. In Figure 4(a), we observe that, at s source broadcast rate of 1 Hz, the-non-distance-sensitive scheme is able to scale to large distances and has lower latencies at larger distances compared with VCAST since there is no staggered forwarding. However, when attempting to reduce the staleness at smaller distances, by increasing the source broadcast rate, non-distance-sensitive forwarding fails. This is shown in Figure 4(b) for broadcast rates of $10 Hz$ . The non-distance-sensitive approaches show much higher staleness even at smaller distances. On the other hand, VCAST is able to deliver lower staleness at smaller distances even at a network size of $784$ nodes by increasing the source broadcast rate and progressively increasing the staleness at larger distances. This allows the network bandwidth to be utilized where it is needed and to achieve scalability.

Figure 4

Impact of source broadcast rate: VCAST versus non-distance-sensitive forwarding. (a) Maximum staleness versus pairwise vehicular distance: $p = 1$ Hz at $784$ nodes. (b) Maximum staleness versus pairwise vehicular distance: $p = 10$ Hz at $784$ nodes.

Message Complexity: The Reason Behind Successful Scaling in VCAST. In Figures 5(a) and 5(b), we show the number of vehicular records transmitted per second by every node for varying network sizes and varying source broadcast rates, respectively. These figures highlight the significantly lower message complexity in VCAST which reduces the contention even as network size and broadcast rates grow.

Figure 5

Comparison of message complexity: VCAST versus non-distance-sensitive forwarding. (a) Number of vehicular records transmitted per second per node at different network sizes for $p = 10$ Hz and range 100 m. (b) Number of vehicular records transmitted per second per node at different source broadcast rates for $784$ nodes and range 100 m.

4.2. Impact of Communication Range, Source Broadcast Rate, and Density

In this subsection, we evaluate the performance of VCAST under different communication ranges, source broadcast rate, and network densities. The aim is to highlight the scalability of VCAST and identify the tipping point in terms of each of these parameters for VCAST, that is, the point at which channel capacity is exceeded.

Communication Range. In Figure 6, we plot the maximum staleness in vehicle information against the intervehicular distance for a $784$ node network with $p = 10$ Hz at different communication ranges. As range increases from 75 m to 125 m, we observe that staleness at larger distances decrease (due to fewer number of hops), while the staleness at smaller distances increase slightly due to increased contention. However, starting from a range of 150 m, we observe that the channel contention within a single hop starts increasing and at a range of 200 m, we observe a tipping point leading to higher message losses and much higher staleness at smaller distances (the corresponding plot is shown in red).

Figure 6

Impact of communication range on VCAST: maximum staleness versus pairwise vehicular distance for VCAST: $p = 10 Hz$ , $784$ vehicles, separation $50 m$ , communication range 75 m, 100 m, 125 m, 150 m, and 200 m.

Source Broadcast Rate. In Figure 7(a), we plot the maximum staleness in vehicle information against the intervehicular distance for a $784$ node network with a communication range of 100 m for different source broadcast rates. As rate increases from $5$ Hz to 10 Hz, we observe that staleness decreases as expected. However, with a rate of 20 Hz, we observe that the channel contention starts increasing, leading to disproportionate staleness values at smaller distances. Figure 7(b) shows a zoomed-in version of Figure 7(a) at smaller distances. Here, we observe that staleness values for 20 Hz are higher than those at 10 Hz due to higher channel contention.

Figure 7

Impact of source broadcast rate on VCAST: (a) maximum staleness versus pairwise vehicular distance with $784$ vehicles, separation 50 m, communication range 100 m, source broadcast rates of 5 Hz, 10 Hz, and 20 Hz. (b) Zoomed-in version at smaller distances.

Network Density. In Figure 8(a), we plot the maximum staleness in vehicle information against the intervehicular distance for a $784$ node network with a communication range of 100 m and rate of 10 Hz for different intervehicular separations. Note that, in Figure 8(a), the plots for separations of 50 m, 40 m, and 30 m only extend to $2$ , $1.7$ , and 1.2 Km, respectively, because these are the possible maximum intervehicular distances at the corresponding densities for a given network size of $784$ vehicles. We observe that going from a separation of 60 m to 40 m, the staleness at larger distances decreases. This is because of fewer number of hops required to reach a given distance. However, with a separation of 30 m, we observe that channel capacity is exceeded causing message losses and higher staleness values (the corresponding plot is shown in red). In Figure 8(b), we have shown the corresponding message complexity at different intervehicular separations. Here we observe a drastic increase in messages per second, at a separation of 30 m which explains the corresponding increase in message losses and information staleness.

Figure 8

Impact of network density on VCAST: (a) maximum staleness versus pairwise vehicular distance with $784$ vehicles, Communication range 100 m, source broadcast rat 10 Hz, separation 60 m, 50 m, 40 m, and 30 m. (b) Number of vehicular records transmitted by each node per second with $784$ vehicles, communication range 100 m, source broadcast rat 10 Hz, separation 60 m, 50 m, 40 m, and 30 m.

4.3. Impact of Time Varying Intervehicular Separations

The aim of this subsection is to characterize the performance of VCAST in the presence of time varying intervehicular separations caused by nonuniform mobility patterns. We note that there are potentially several traffic mobility patterns that can arise in a real vehicular network scenario. Our goal here is to analyze the scalability of VCAST and one of the important underlying factors that can impact performance in the context of these mobility patterns is the time varying density. There could be instants when a vehicle has a lot of neighbors within communication range and also instances when there are no neighbors. Therefore, in this simulation, we have chosen the random 2d walk mobility pattern with time varying speeds in the range of 20 m/s to 40 m/s, a potentially severe form of mobility that captures the essence of time varying separations and interference zone, caused in a traffic scenario.

In Figures 9(a) and 9(b), we compare the information staleness graphs for the random and uniform mobility patterns at $5$ Hz and $10$ Hz source broadcast rates with $784$ nodes. As seen from these figures, the graphs are quite similar, highlighting that random mobility does not significantly impact the performance. Staleness values at larger distances are observed to be slightly higher for the case of random mobility. However, the reason for this is not higher communication cost but rather the fact that the severe random mobility scenario often creates sparse and disconnected regions within the network, thereby increasing the number of hops traversed between two vehicles at a given distance. This effect is more pronounced at larger distances. In Figure 10, we compare the average communication cost for the random and uniform mobility scenarios. This graph highlights the fact that communication costs do not increase in the random mobility scenario—in fact a small decrease is observed in the average communication cost over several random patterns.

Figure 9

Impact of time varying random mobility pattern on VCAST: (a) maximum staleness versus pairwise vehicular distance for uniform and random mobility with $784$ vehicles, communication range 100 m, source broadcast rate 5 Hz. (b) Maximum staleness versus pairwise vehicular distance for uniform and random mobility with $784$ vehicles, communication range 100 m, source broadcast rate 10 Hz.

Figure 10

Impact of time varying random mobility pattern on VCAST (comparison of communication cost): number of vehicular records transmitted by each node per second at $5$ Hz and $10$ Hz source broadcast rates under uniform and random mobility patterns.

4.4. Impact of Aggregation

In this section, we evaluate VCAST when aggregate information about a cell is transmitted over multiple hops as opposed to individual vehicle information. The region being simulated is divided into square cells of equal size. The width of each cell is assumed to be equal to the single hop communication range. In this evaluation, we have increased the network size to $3600$ nodes, thereby allowing us to evaluate staleness over larger distances. Figure 11 shows the information staleness graphs with a communication range of 100 m ad 150 m, both with a source broadcast rate of 10 Hz. As seen in these graphs, information up to $4$ Km can be obtained in less than $5$ seconds, without the need for any infrastructure—while still maintaining extremely low staleness values at smaller distances.

Figure 11

Impact of aggregation on VCAST: maximum staleness versus vehicle-cell distance with $3600$ vehicles, source broadcast rat 10 Hz, communication range 100 m and 150 m.

4.5. Summary of Results

Our experimental results show that by using distance-sensitive forwarding, VCAST is able to scale to larger network size as well as support much higher broadcast rates compared to non-distance-sensitive techniques. The reason for scalability is the significantly lower message overhead which reduces the channel contention in the network. We also characterized the performance of VCAST under severe mobility and studied information staleness when aggregated data is transmitted as opposed to individual vehicle information.

From all of the above experimental evaluations, we note that an ideal parameterization for VCAST is to set communication range to a small value and increase the source broadcast rate. By doing so, information at smaller distances can be obtained at high rates with low contention due to the small communication range. At the same time, information to larger distances can be transmitted with progressively increasing staleness. Moreover, by limiting the propagation of individual vehicular information up to distances of about 500–1000 m (for utilization by safety applications) and only propagating aggregate information beyond that, we observe that information from several miles ahead can be obtained within a few seconds without the need for any communication infrastructure.

5. Conclusions

We have presented an algorithm, VCAST, for obtaining individual vehicle location and aggregate traffic information over a multihop wireless vehicular network without the need for expensive roadside infrastructure, any special hardware, or modification to vehicular transmission standards. To ensure scalability in forwarding information over multiple hops, traffic information is propagated at a rate that decreases linearly with distance from the source. By doing so, the required communication rate per node can be reduced when compared with schemes that do not utilize distance sensitivity in information forwarding. This results in lower channel contention, thereby enabling higher source broadcast rates and better information quality at smaller distances while still being able to propagate information to large distances. Despite staggered forwarding, traffic information can be obtained with a staleness, which is a measure of error in the traffic information that is bounded by $O (d^{2})$ where d is the communication hop distance from the source of the information.

The performance of VCAST was validated using extensive ns-3 simulation under different network sizes, network densities, source broadcast rates, and communication ranges. The results of our evaluation showed that by using distance-sensitive forwarding, VCAST is able to scale to larger network sizes as well as support much higher broadcast rates compared to non-distance-sensitive techniques. The reason for scalability was shown to be the significantly lower message overhead which reduces the channel contention in the network. We also characterized the performance of VCAST under severe mobility and studied information staleness when aggregated data is transmitted as opposed to individual vehicle information.

In future work, we would like to integrate VCAST with control algorithms for vehicular safety and navigation that utilize information with distance-sensitive quality. We would like to design optimal control laws for vehicular acceleration under models of distance-sensitive information availability that ensures the safety of the integrated control-communication system. We would also like to integrate our vehicular traffic mapping service with a navigation front end for dynamic computation of alternate routes and evaluate the impact of distance sensitivity on the quality of navigation performance.

References

Fallah

Y. P.

Huang

Sengupta

Krishnan

Design of cooperative vehicle safety systems based on tight coupling of communication, computing and physical vehicle dynamics

Proceedings of the 1st ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS '10)

April 2010

159 167

2-s2.0-77954566972

10.1145/1795194.1795217

U. S. Department of Transportation

Achieving the vision: from VII to IntelliDrive

Policy white paper, 2010

Kulathumani

Fallah

Vcast: an infrastructure-less vehicular traffic information service with distance sensitive precision

Proceedings of the IEEE Vehicular Technology Conference (VTC '12)

2012

Liu

Dion

Safety assessment of information delays on intelligent vehicle control system performance

2006

Proceedings of Transportation Research Board Conference

Kulathumani

Arora

Aspects of distance sensitive design of wireless sensor networks

Proceedings of the IEEE Workshop on Spatial Computing

October 2008

2-s2.0-64849090838

Kulathumani

Arora

Ramagiri

Pursuit control over wireless sensor networks using distance sensitivity properties

IEEE Transactions on Automatic Control 2011 56 10 2473 2478

2-s2.0-80053655313

10.1109/TAC.2011.2163849

Wang

Routing in vehicular ad hoc networks: a survey

IEEE Vehicular Technology Magazine 2007 2 2 12 22

2-s2.0-39449084181

10.1109/MVT.2007.912927

Lee

K. C.

Lee

Gerla

Survey of routing protocols in vehicular ad hoc networks

Advances in Vehicular Ad-Hoc Networks: Developments and Challenges 2009

IGI-Global

149 170

Lin

Y.-W.

Chen

Y.-S.

Lee

S.-L.

Routing protocols in vehicular Ad Hoc networks: a survey and future perspectives

Journal of Information Science and Engineering 2010 26 3 913 932

2-s2.0-77953670422

10.

Zhao

Cao

VADD: vehicle-assisted data delivery in vehicular ad hoc networks

Proceedings of the 25th IEEE International Conference on Computer Communications

April 2006

2-s2.0-34248646800

10.1109/INFOCOM.2006.298

11.

Lochert

Mauve

Fera

Hartenstein

Geographic routing in city scenarios

ACM SIGMOBILE Mobile Computing and Communications Review 2005 9 1 69 72

12.

Chen

Y.-S.

Lin

Y.-W.

Pan

C.-Y.

DIR: diagonal-intersection-based routing protocol for vehicular ad hoc networks

Telecommunication Systems 2011 46 4 299 316

2-s2.0-79851482271

10.1007/s11235-010-9294-2

13.

Naumov

Gross

T. R.

Connectivity-aware routing (CAR) in vehicular ad hoc networks

Proceedings of the 26th IEEE International Conference on Computer Communications

May 2007

1919 1927

2-s2.0-34548321656

10.1109/INFCOM.2007.223

14.

Taleb

Sakhaee

Jamalipour

Hashimoto

Kato

Nemoto

A stable routing protocol to support ITS services in VANET networks

IEEE Transactions on Vehicular Technology 2007 56 6 3337 3347

2-s2.0-36749036607

10.1109/TVT.2007.906873

15.

Sun

Yamaguchi

Yukimasa

Kusumoto

GVGrid: a QoS routing protocol for vehicular ad hoc networks

Proceedings of the 14th IEEE International Workshop on Quality of Service (IWQoS '06)

June 2006

130 139

2-s2.0-34250660402

10.1109/IWQOS.2006.250460

16.

Skordylis

Trigoni

Delay-bounded routing in vehicular ad-hoc networks

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

May 2008

341 350

2-s2.0-57349182166

10.1145/1374618.1374664

17.

Joshi

H. P.

Sichitiu

Kihl

Distributed robust geocast multicast routing for inter-vehicle communication

Proceedings of the WEIRD Workshop on WiMax, Wireless and Mobility

2007

18.

Poellabauer

Balancing broadcast reliability and transmission range in VANETs

Proceedings of the IEEE Vehicular Networking Conference (VNC '10)

December 2010

247 254

2-s2.0-79951778692

10.1109/VNC.2010.5698263

19.

Torrent-Moreno

Mittag

Santi

Hartenstein

Vehicle-to-vehicle communication: fair transmit power control for safety-critical information

IEEE Transactions on Vehicular Technology 2009 58 7 3684 3703

2-s2.0-69749093972

10.1109/TVT.2009.2017545

20.

Cheng

Shakya

VANET Adaptive power control from realistic propagation and traffic modeling

Proceedings of the IEEE Radio and Wireless Symposium

January 2010

665 668

2-s2.0-77952349437

10.1109/RWS.2010.5434251

21.

Yang

Guo

Channel adaptive one hop broadcasting for VANETs

Proceedings of the 11th International IEEE Conference on Intelligent Transportation Systems (ITSC '08)

December 2008

369 374

2-s2.0-60749130200

10.1109/ITSC.2008.4732578

22.

Chigan

A delay-bounded dynamic interactive power conftol algorithm for VANETs

Proceedings of the IEEE International Conference on Communications (ICC '07)

June 2007

5849 5855

2-s2.0-38549124471

10.1109/ICC.2007.969

23.

Bachir

Benslimane

A multicast protocol in ad hoc networks inter-vehicle geocast

Proceedings of the 57th IEEE Semiannual Vehicular Technology Conference (VTC '03)

April 2003

2456 2460

2-s2.0-0042970277

24.

Chen

Y.-S.

Lin

Y.-W.

Lee

S.-L.

A mobicast routing protocol in vehicular Ad-Hoc networks

Mobile Networks and Applications 2010 15 1 20 35

2-s2.0-76549086258

10.1007/s11036-009-0176-3

25.

Mariyasagayam

M. N.

Osafune

Lenardi

Enhanced multi-hop vehicular broadcast (MHVB) for active safety applications

Proceedings of the 7th International Conference on Intelligent Transport Systems Telecommunications (ITST '07)

June 2007

223 228

2-s2.0-47349094425

10.1109/ITST.2007.4295866

26.

Fukuyama

A probabilistic protocol for multi-hop routing in VANETs

Proceedings of the IEEE International Conference on Communications Workshops

June 2009

2-s2.0-70449455978

10.1109/ICCW.2009.5208064

27.

Kumar

Kherani

A. A.

Altman

Route lifetime based optimal hop selection in VANETs on highway: an analytical viewpoint

Proceedings of the International IFIP-TC6 Networking Conference

2006

28.

Fukuhara

Warabino

Ohseki

Saito

Sugiyama

Nishida

Eguchi

Broadcast methods for inter-vehicle communications system

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '05)

March 2005

2252 2257

2-s2.0-24944504865

29.

Bai

Stancil

D. D.

Krishnan

Toward understanding characteristics of Dedicated Short Range Communications (DSRC) from a perspective of vehicular network engineers

Proceedings of the 16th Annual Conference on Mobile Computing and Networking (MobiCom '10)

September 2010

329 340

2-s2.0-78649279855

10.1145/1859995.1860033

30.

Tseng

Chen

Sheu

The broadcast storm problem in a mobile ad hoc network

Proceedings of the ACM/IEEE international conference on Mobile computing and networking

1999

31.

Williams

Camp

Comparison of broadcasting techniques for mobile ad hoc networks

Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '02)

June 2002

194 205

2-s2.0-0042032991

32.

Peterson

Davie

Computer Networking: A Systems Approach 2011

Elsevier

33.

Pei

Gerla

Chen

T.-W.

Fisheye state routing in mobile Adhoc networks

Proceedings of the ICDCS Workshop on Wireless Networks

June 2000

71 78

2-s2.0-0033681686

34.

Dehne

Ferreira

Rau-Chaplin

Parallel fractional cascading on hypercube multiprocessors

Computational Geometry 1992 2 3 141 167

2-s2.0-38249008278

35.

Funke

Guibas

Zhang

Distance sensitive information brokerage in sensor networks

Proceedings of the International Conference on Distrbuted Computing in Sensor Systems (DCOSS '06)

2006

Springer

234 251

36.

Demirbas

Arora

Kulathumani

Glance: a lightweight querying service for wireless sensor networks

Theoretical Computer Science 2009 410 6-7 500 513

2-s2.0-58549099286

10.1016/j.tcs.2008.10.013

37.

Kulathumani

Arora

Sridharan

Demirbas

Trail: a distance-sensitive sensor network service for distributed object tracking

ACM Transactions on Sensor Networks 2009 5 2 1 40

2-s2.0-65849263083

10.1145/1498915.1498921

38.

Gao

Guibas

L. J.

Hershberger

Zhang

Fractionally cascaded information in a sensor network

Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN '04)

April 2004

311 319

2-s2.0-3042698242

39.

Kulathumani

Arora

Distance sensitive snapshots in wireless sensor networks

Principles of Distributed Systems 2007 4878 143 158

40.

Dijkstra

E. W.

Self-stabilizing systems in spite of distributed control

Communications of the ACM 1974 17 11

VCAST: Scalable Dissemination of Vehicular Information with Distance-Sensitive Precision

Abstract

1. Introduction

2. Related Work

3. System Description

3.1. System Model and Problem Statement

3.2. Distance-Sensitive Broadcast Algorithm

Algorithm 1: VCAST: protocol actions at vehicle j.

3.3. Analysis

Theorem 1.

Proof.

Definition 2 (staleness (j,i)).

Theorem 3.

Proof.

Theorem 4.

Proof.

Theorem 5.

Proof.

4. Performance

4.1. Impact of Distance Sensitivity

4.2. Impact of Communication Range, Source Broadcast Rate, and Density

4.3. Impact of Time Varying Intervehicular Separations

4.4. Impact of Aggregation

4.5. Summary of Results

5. Conclusions

References