# A Probabilistic Protocol for Multihop Routing in VANETs

Authors: Junichiro Fukuyama
Journal: Journal of Electrical and Computer Engineering
 (2010)

---

## Abstract

Vehicular ad hoc networks (VANETs) allow communications over sequences of vehicles with radio devices. There are many possible applications over a VANET such as traffic jam warning, collision warning, parking lot reservations, camera
picture feed , and so forth. There have been quite a few results in the area seeking for a fast and reliable communication protocol due to
their potential. VANETs, however, are pointed out as difficult for numerical optimizations due to frequent changes in their
topologies. As a result, heuristic methods such as GPSR have been mainly used for routing packets over multihop communications.
In this paper, we present an algorithm to precompute the probability that  communication is possible between specified
source and destination in a VANET, under certain mathematical assumption. The proposed new protocol for multihop communication
refers to a lookup table containing the precomputed data to decide a good packet forwarder quickly.
We create a simulation testbed that seems challenging for all the existing multihop routing protocols for VANETs, in which we
test ours. We see much improved performances over GPSR after the algorithm is refined for some practical issues.


---

## Body

## 1. Introduction

Vehicular ad hoc networks (VANETs) enable communication between vehicles or between a vehicle and infrastructure. The idea of having intervehicle communications connected to a wired network has been investigated since the 1980s. Over a VANET, we can achieve traditional safety applications such as collision, icy road, and red light warnings, as well as nonsafety applications such as traffic information dissemination, reservation query, camera picture feed and so forth. Recently, there has been an emerging trend of utilizing mobile communication for environmental issues. It is possible to obtain significant information from VANETs to improve the uses of gas or other resources.When there are not sufficient roadside units (RSUs) or direct communications between distant vehicles are preferred, it usually takes more than one step of vehicle-to-vehicle (V2V) communications to send information from a specified source to destination. The transmission range of a radio device is normally 100–200 m for V2V, which is much smaller than the dimension of the considered area. Researchers have studied such multihop communications extensively not only because VANET applications have a large market potential, but also they are scientifically interesting [1–5].It has turned out very difficult to optimize parameters of a VANET due to its highly mobile nature. Links can be disconnected so frequently that it is occasionally impossible to accurately predict the existence of an end-to-end connection. Reference [6] sheds light on the theoretical aspect of this issue. As a result, carry-and-forward type heuristic methods have been mainly used for routing packets over multihop communications in VANETs.The current most common scheme for source-destination routing in VANETs is the so-called geographical forwarding. It chooses car(s) closest to the destinationd and pass the packet. Geographical forwarding was first introduced as GPSR in [7]. The result has been referred to many other papers that seek a better performance by similar methods. One of them, called PBRV [8], resolves the routing loop problem of GPSR.The main advantage of geographical forwarding is its computational speed per hop. It is a simple task to calculate the distance tod for every car in the proximity, and quick computation is very important to forward a packet in short latency. However, we can easily create counter examples for geographical forwarding such as the ones seen in [2] and Figure 1. A similar situation may happen more frequently when the market penetration rate, that is,  the ratio of the cars equipped with radio devices, is low.Figure 1
A counter example for geographical forwarding.Another protocol called MDDV is developed in [9]. It uses the following two in addition to the geographical forwarding. (i)
Trajectory-based forwarding:first determine an approximate trajectory from the source to the destination on the map then only considers cars that roughly follow it.(ii)
Opportunistic forwarding:chooses some cars that meet certain conditions to give them the right to broadcast the packet in the proximity.MDDV is designed for an arterial road or highway where considered cars are basically running in the same direction. It is reported to produce short latency and high delivery ratio in such a scenario but does not have a mechanism to treat a downtown situation.Recently, a protocol called VADD has been proposed [4]. It considers the probability for a packet to reach the destination in addition to the positions and directions of the moving cars in the proximity. VADD handles a situation as in Figure 1 better than the previous two. It, however, calculates the probability at every intersection, seeming to have large invehicle computational time. It is based on the idea of dynamic path-selection approach. Nevertheless, one can point out that a large amount of the input information to VADD is static: the fixed probability for a packet to be sent successfully from one intersection to another.There have been some other forwarding schemes known such as delaybounded routing [3], CAR [2], and GeOpps [1].In this paper, we present an algorithm to precompute the probability that the communication is possible between specified source and destination in a VANET, under certain mathematical assumption. We propose a new protocol for multihop communication that refers to a lookup table containing the pre-computed data to decide a good packet forwarder quickly.We create a simulation testbed that seems challenging for all the existing multihop routing protocols for VANETs, in which we test ours. After the algorithm is refined for some practical issues, it showed dramatically improved performances over GPSR.The rest of the paper is organized as follows: in Section2, we describe our general method to pre-compute such probabilities. Section 3 shows the simulation results, followed by conclusions stated in Section 4.


## 2. A Method to Precompute the Probability of Multihop Communication

The main idea of the probabilistic protocol we propose in this paper is to compute in advance the probability that it is possible to forward the packet from the sources to destination d. We call it the communication probability from s to d.Suppose for simplicity that two cars can communicate whenever they are within a given transmission rangeR of the radio. We will modify it later so the algorithm may better suit real situations. With this simplification, the communication from s to d is possible if and only if there is a sequence of cars to forward the packet as shown in Figure 2. We call such a sequence a communication path. Now, our communication probability is the probability that such a path exists. In this section, we present an efficient algorithm to compute the probability under certain assumption as well as a general way to measure its inputs. We will also consider how to refine the algorithm for practical use.Figure 2
An example of a communication path.Figure 3
The node differentiation problem.


### 2.1. Basic Notation

We assume that every considered object is on the mapM that is a Euclidean graph whose nodes are geographical locations or positions, and edges are roads. Denote by xa position on M, for which we write x∈M instead of x∈V(M). Let m be the number of positions on M. Notice that x is a two-dimensional vector.LetR be the transmission range of the radio. As stated before, we assume at this moment that any two cars within the distance can communicate with each other. A position x'∈M is called an  R-neighbor of x∈M if the Euclidean distance from x to x' is at most R.Consider that timet=0,1,2,…,T where T is the time limit. To express that a car is at position x∈M when time is t, it is convenient to couple t with x. A space  timeu=(x,t) is meant to be such pairing.Acarry is a pair h=(u1,u2) of space times. It means that a car appears at u1=(x1,t1) and moves to u2=(x2,t2). We can understand carries as the solid arrows in Figure 2, while the dotted ones represent hops. We say x1 and x2 are the source and destination of the carry, and t1 and t2 are start and arrival time, respectively.Formally, acommunication path is a k-tuple E=(h1,h2,…,hk)  of carries hi such that the start time of hi+1 equals the arrival time of hi, and the source of hi+1 is an R-neighbor of the destination of hi for every i<k. We require the integer k to be at most a given maximum numberHof hops. We can also say that E is a communication path from u to u', where u is the first space time of h1 and u' the second one of hk. The arrival time and destination of E are defined as those of u', respectively.Let a sources and destination d be given. A space time u=(x,t) is said to be reachable from(s,0)inkhops if there exists a communication path from (s,0) with no more than k carries whose destination is an R-neighbor of x and arrival time is at most t. The communication probabilityρ(s,d,T) from s to d with time limit T is the probability that (d,T) is reachable from (s,0) in H hops.Figure2 shows a communication path from (s,0) to (d′,t) with 4 carries and 3 hops. The space  time (d,t) is reachable from (s,0) in 4 hops.Our goal in this mathematical framework is to computeρ(s,d,T) efficiently. Once we have the communication probabilities, the averages of other various random variables could be computed quickly. For example, the expected delay time τ(s,d) to send a packet from s to d is(1)τ(s,d)=∑t=1Tt(ρ(s,d,t)-ρ(s,d,t-1))=Tρ(s,d,T)-∑t=0T-1ρ(s,d,t).


### 2.2. Assumptions to Reduce the Hardness of Computation

Denote by(A,u) the probabilistic event that car A appears at space time u and by P(A,u) its probability. In the rest of the paper, P(·) expresses the probability of the argument event, where we omit obvious parentheses, thatis, write P(A,u) instead of P((A,u)) and so forth. Let Ω be the set of all (A,u). Logical sum, product, and implication are denoted by ⋁, ⋀, and an arrow, respectively. Consider the discrete probability space (Ω,ℱ,P) as in Appendix A, where ℱ is the set of events over Ω. We will have all formal discussions in this framework.The probabilitiesP(A,u) are not sufficient information to compute the exact values of ρ(s,d,T), because the events (A,u) possibly depend on each other even for a single car A. For example, P((A,u1)⋀(A,u2)) may not be P(A,u1)P(A,u2) due to the dependence; if paths from the source s to ui overlap, P(A,ui) affect each other.We formulate the problem of computing communication probabilities as follows; given a mapM, initial positions of cars, time limit T, and transmission range R, assume that subsequent movements of two cars are independent of each other. That of every car A is restricted so that P((A,u2)|(A,u1)) is a given fixed value, where u1=(x1,t) and u2=(x2,t+1) are space times, and P(·|·) denotes conditional probability as defined in Appendix A. It means that the probability of A moving from x1 to x2 is given when time transits from t to t+1. Compute the communication probability from s∈M to d∈M for all the pairs of s and d from the above information. This problem seems hard to compute in polynomial time. We, in fact, conjecture that it is NP-complete even when the input instance is restricted such that the number of possible routes taken by each A is bounded by a polynomial in the problem size. (We define the size as the number of cars added by m+T+H.) The difficulty is attributed to the dependence between communication paths that are events in ℱ.We introduce the following assumption to reduce the hardness of computation. Denote by[u,k] the event in ℱ that the space time u is reachable from (s,0) in k hops.Steady traffic assumption: the following two are true in (Ω,ℱ,P).(i)
All the carries are independent.(ii)
[u,k] for each k≤H are independent.If it is true, the probabilityP([u,k]) takes a value that only depends on u for each fixed k, letting the reachability to u not affect each other. Then, the algorithm shown in Section 2.3 will compute the communication probability exactly.There are some input instances for which the assumption holds strictly. One such case is significant: when we have the exact schedule of every car, or(A,u) satisfy the following.Exact schedule assumption: P(A,u) is either 1 or 0 for every car A and space time u.It means that it is either true or false ifA appears at u. The following lemma says that it is only a special case of the steady traffic assumption.Lemma 1.
The exact schedule assumption implies the steady traffic assumption.Proof.
Suppose thatP(A,u) is either 0 or 1 for every (A,u). The probability of (A,u) given any condition is either 0 or 1. The probability that a communication path occurs is 0/1. Thus, P([u,k]) is also 0/1 for any k≤H. The event [u,k] is independent of the others as the last paragraph in Appendix A says. Since carries (u,k) have probabilities 0 or 1, it implies the steady traffic assumption.Thus, if we have exact schedules of the cars, we can simply use the algorithm in Section2.3 setting P(A,u)=1/0 to compute the exact communication probability.A natural question occurs; how true is steady traffic assumption in real traffic scenes? We think that[u,k] and carries are well independent in practice if considered u=(x,t) are distinct enough. Events [u,k] with similar x and t affect each other, since they share large common parts of major communication paths. In Section 3, we compare the performance of the probabilistic protocol with that of GPSR in a challenging simulation testbed. We choose 100 m and 5 seconds as the unit differences of x and t, respectively, to avoid considering similar u too often. With the coarse resolutions, the probabilistic protocol will successfully capture the tendency of the vehicle mobility to contribute to good communication performances.


### 2.3. The Basic Algorithm

We show below our basic algorithm to compute communication probabilities. Its primary input is thecarry probabilityP(u1,u2) that there exists a car that appears at the space time u1 and moves to u2 for every carry (u1,u2).Notice that(2)(u1,u2)=⋁everycarA(A,u1)⋀(A,u2),
in the probability space (Ω,ℱ,P), since the carry (u1,u2) is the event in ℱ that some A appears at u1 and moves to u2. Recall the problem of computing communication probabilities formulated in Section 2.2. Since the conditional probability of (x2,t+1) given that (x1,t) is input for all xi and t, it means that the probability of the event (A,u1)⋀(A,u2) is determined uniquely. Movements of distinct cars are independent. The probability of the carry (u1,u2) is uniquely determined by the input instance of the problem.Now, assume the steady traffic assumption.SteadyTraffic illustrated in Algorithm 1 computes the communication probability for any given pair of source and destination.Algorithm 1
Algorithm SteadyTrafficInputs:T: time limit,H: maximum number of hops,M: map with m positions,R: transmission range,P(u1,u2): carry probability for every (u1,u2), that is, probabilitythat a car appears at space timeu1 and moves to u2,s,d∈M: source and destination on the map M.Output:Communication probabilityρ(s,d,T) from s to d with time limit T.begin(1). /* The final value of Answer(x,t,k) will be the probability that thereexists a communication path from(s,0) to (x,t) with at most k carries. */(2). Forevery space time u=(x,t)doAnswer(x,t,0)=0;(3). Answer(s,0,0)=1;(4). fork=1toHdo4-1.for every space time u=(x,t)do4-1-1.Answer(x,t,k)=P((s,0),u);4-1-2.for every other space time u1=(x1,t1) such that t1≤tdo4-1-2-1./* Let D(x) for x∈M be the set of R-neighbors of x   */4-1-2-2.p1=1-∏x2∈D(x1)(1-Answer(x2,t1,k-1));4-1-2-3.p2=P(u1,u)·p1;4-1-2-4.Answer(x,t,k)=Answer(x,t,k)(1-p2)+p2;4-1-3.end    for4-2.end    for(5).end    for(6). return1-∏x∈D(d)t≤T(1-Answer(x,t,H));endIts correctness proof is found in AppendixB. We will present a general method to obtain P(u1,u2) from field data in Section 2.4 and a more practical version in Section 2.5.The asymptotic running time ofSteadyTraffic is found O(Hm2T2R2) in a straightforward manner. In our simulation test with a careful choice of the parameter set, it runs in few minutes to finish computation for each s and d.If the exact schedule assumption holds,P(u1,u2) is 1 if and only if there exists a car A such that P(A,u1)P(A,u2)=1. We can input them into SteadyTraffic to compute ρ(s,d,T).


### 2.4. To Measure Carry Probabilities from Field Data

The primary input to AlgorithmSteadyTraffic is the probabilities of P(u1,u2) of the carries. Theoretically, all we need is P((A,u1)⋀(A,u2)) for every car A and space times ui that is, the probability that the given car A appears at u1 and moves to u2. Then, the carry probability is computed as(3)P(u1,u2)0=1-∏everycarA(1-P((A,u1)⋀(A,u2))),
by (1) and (3).There are ways to computeP((A,u1)⋀(A,u2)) from field data. The following two steps provides a general one.Measure the intersection probabilities
Some nodesv on the map M represent intersections. The edges l from v are the roads from v. Theintersection probabilityQ(l,l′,v) is the probability that a car moves from the road l to l' at the intersection v. We first measure this quantity from real field data, by simply finding the ratio of the cars to choose the road l' out of all the cars running toward v on l.CalculateP((A,u1)⋀(A,u2))
We repeat the process below for a number of times to average the obtained values ofP((A,u1)⋀(A,u2)). At the beginning of each round, we configure the initial positions of the cars randomly but based on the real statistics. Then, do the following:     (1)
fix each carry(u1,u2) and car A. Let ui=(xi,ti) for i=1,2.(2)
At timet=0,1,2,…,t1, simulate the probabilistic movements of the car using the intersection probabilities so that we know the probability of A being at (x,t) for all x∈M and t≤t1. In the end, we know the probability of A at u1=(x1,t1). Store it into p1.(3)
Fix the position ofA at t=t1 as x1. Simulate the probabilistic movements of A at time t=t1+1,t1+2,…,t2. Find the probability of A at (x2,t2), and store it into p2.(4)
Now,P((A,u1)⋀(A,u2))=p1·p2 is the probability that A appears at u1 and moves to u2.


### 2.5. Practical Refinements

Although the method described so far is mathematically correct for the presented mobility model, we faced essential difficulties when we implementedSteadyTraffic on a testbed described in the next section. Abstracting the problems, we devised a variant of SteadyTraffic that is meant to be used for practice. It is illustrated in Algorithm 2 as SteadyTraffic 2.Algorithm 2:A practical variant of SteadyTraffic.
Algorithm SteadyTraffic2Inputs:T, H, M, R, P(u1,u2), s,d∈M: same as SteadyTraffic,ξ(x1,x2): 1 hop packet error ratio from x1∈M to x2∈M,e(x): expected car density at x∈M,β,ϵ∈(0,1): numeric parameters,dir∈{(0,-1),(0,1),(1,0),(-1,0)}: vector representing the movingdirection.Output:Approximate communication probabilityρ(s,d,T)froms to d with time limit T.begin(1). Forevery space time u=(x,t)doAnswer(x,t,0)=0;(2). Answer(s,0,0)=1;(3). fork=1toHdo3-1.for every space time u=(x,t)do3-1-1.Answer(x,t,k)=P((s,0),u);3-1-2.for every other space time u2=(x2,t2) and u1=(x1,t2)such thati)t2≤t,  ii) x1∈D(x2),  iii) P(u1,u)≥ϵ,iv)(x1-x2)·dir≥0 and iv) (x-x1)·dir≥0/*D(x) is the set of R-neighbors of x∈M*//*· represents the inner product of two vectors */do3-1-2-1.p1=P(u1,u)(e(x1)e(x))β;3-1-2-2.p2=Answer(x2,t2,k-1)(1-ξ(x1,x))p1;3-1-2-3.Answer(x,t,k)=Answer(x,t,k)(1-p2)+p2;3-1-3.end    for3-2.end    for(4).end    for(5). return1-∏x∈D(d)t≤T(1-Answer(x,t,H)(1-ξ(x,d)));endWe summarize below general deployment problems and our solutions in the modified algorithm. First, values computed bySteadyTraffic may include propagated errors. As stated as the steady traffic assumption in Section 2.2, we want the reachability events [u,k] and carries to be well independent of others. If we consider [u,k] with similar space times u=(x,t) too often, it is likely to increase the calculated communication probability much more than the real value. In other words, space times whose car density is large may not be much different from those with small density for the algorithm SteadyTraffic.We multiply, to handle the problem, carry probabilitiesP(u1,u2) by (e(x1)e(x2))β, where ui=(x1,ti) are space times, e(x) are the expected car densities at x∈M, and β∈(0,1) is a numeric parameter to adjust. Step3-1-2-1 of SteadyTraffic2 performs this data modification. It has an effect of emphasizing the differences between large and small car densities. We will choose β=1/2 in Section 3.We could also use coarse space and time resolutions to prevent the error propagation, that is, to use large values of unit differences ofx and t to avoid introducing similar u=(x,t). It also speeds up the algorithm significantly.Loop 3-1-2 ofSteadyTraffic2 has a slightly different structure from 4-1-2 of SteadyTraffic; the former finds any new carry (u1,u)  in the proximity of u2 such that i)–v) and updates Answer(x,t,k) at u simply assuming that the newly detected communication path is independent of the others. Condition iii) discards carries of low probabilities.The above schemes of simplification and data modification effectively compute good approximate values of communication probability with reasonable computational time. This practically solves our first problem of error propagation.Secondly, we have a node differentiation problem. Even if the communication probabilities are accurate, it is occasionally hard in run time to choose a good packet forwarder among the nearby vehicles. We illustrate the problem in Algorithem 1. To resolve it, we restrict considered communication paths so that they are not extended in a specified direction. Conditions iv) and v) of Loop 3–1–2 filter every path withx- or y-component running in the opposite direction to given dir. We call it north, south, west, and east mode when dir=(0,-1),(0,1),(1,0),and(-1,0), respectively. (The map origin is supposed to locate at the upper-left corner.) For example in the north mode, SteadyTraffic 2 does not extend a communication path to location more southern than the current position. It is suggested to combine values of more than 1 modes to refer to in run time to find a good packet forwarder.Third, the probability of successful packet transmission is usually not uniform in a real traffic scene. We approximate it by its time average, that is, we assume that1-hop packet error ratioξ(x1,x2) varies over positions xi∈M and is constant over time. Steps 3-1-2-2 and 5 of SteadyTraffic2 include related multiplications. We could use values of ξ measured in field data possibly in conjunction with an analytical formula such as the one in [10].


## 2.1. Basic Notation

We assume that every considered object is on the mapM that is a Euclidean graph whose nodes are geographical locations or positions, and edges are roads. Denote by xa position on M, for which we write x∈M instead of x∈V(M). Let m be the number of positions on M. Notice that x is a two-dimensional vector.LetR be the transmission range of the radio. As stated before, we assume at this moment that any two cars within the distance can communicate with each other. A position x'∈M is called an  R-neighbor of x∈M if the Euclidean distance from x to x' is at most R.Consider that timet=0,1,2,…,T where T is the time limit. To express that a car is at position x∈M when time is t, it is convenient to couple t with x. A space  timeu=(x,t) is meant to be such pairing.Acarry is a pair h=(u1,u2) of space times. It means that a car appears at u1=(x1,t1) and moves to u2=(x2,t2). We can understand carries as the solid arrows in Figure 2, while the dotted ones represent hops. We say x1 and x2 are the source and destination of the carry, and t1 and t2 are start and arrival time, respectively.Formally, acommunication path is a k-tuple E=(h1,h2,…,hk)  of carries hi such that the start time of hi+1 equals the arrival time of hi, and the source of hi+1 is an R-neighbor of the destination of hi for every i<k. We require the integer k to be at most a given maximum numberHof hops. We can also say that E is a communication path from u to u', where u is the first space time of h1 and u' the second one of hk. The arrival time and destination of E are defined as those of u', respectively.Let a sources and destination d be given. A space time u=(x,t) is said to be reachable from(s,0)inkhops if there exists a communication path from (s,0) with no more than k carries whose destination is an R-neighbor of x and arrival time is at most t. The communication probabilityρ(s,d,T) from s to d with time limit T is the probability that (d,T) is reachable from (s,0) in H hops.Figure2 shows a communication path from (s,0) to (d′,t) with 4 carries and 3 hops. The space  time (d,t) is reachable from (s,0) in 4 hops.Our goal in this mathematical framework is to computeρ(s,d,T) efficiently. Once we have the communication probabilities, the averages of other various random variables could be computed quickly. For example, the expected delay time τ(s,d) to send a packet from s to d is(1)τ(s,d)=∑t=1Tt(ρ(s,d,t)-ρ(s,d,t-1))=Tρ(s,d,T)-∑t=0T-1ρ(s,d,t).


## 2.2. Assumptions to Reduce the Hardness of Computation

Denote by(A,u) the probabilistic event that car A appears at space time u and by P(A,u) its probability. In the rest of the paper, P(·) expresses the probability of the argument event, where we omit obvious parentheses, thatis, write P(A,u) instead of P((A,u)) and so forth. Let Ω be the set of all (A,u). Logical sum, product, and implication are denoted by ⋁, ⋀, and an arrow, respectively. Consider the discrete probability space (Ω,ℱ,P) as in Appendix A, where ℱ is the set of events over Ω. We will have all formal discussions in this framework.The probabilitiesP(A,u) are not sufficient information to compute the exact values of ρ(s,d,T), because the events (A,u) possibly depend on each other even for a single car A. For example, P((A,u1)⋀(A,u2)) may not be P(A,u1)P(A,u2) due to the dependence; if paths from the source s to ui overlap, P(A,ui) affect each other.We formulate the problem of computing communication probabilities as follows; given a mapM, initial positions of cars, time limit T, and transmission range R, assume that subsequent movements of two cars are independent of each other. That of every car A is restricted so that P((A,u2)|(A,u1)) is a given fixed value, where u1=(x1,t) and u2=(x2,t+1) are space times, and P(·|·) denotes conditional probability as defined in Appendix A. It means that the probability of A moving from x1 to x2 is given when time transits from t to t+1. Compute the communication probability from s∈M to d∈M for all the pairs of s and d from the above information. This problem seems hard to compute in polynomial time. We, in fact, conjecture that it is NP-complete even when the input instance is restricted such that the number of possible routes taken by each A is bounded by a polynomial in the problem size. (We define the size as the number of cars added by m+T+H.) The difficulty is attributed to the dependence between communication paths that are events in ℱ.We introduce the following assumption to reduce the hardness of computation. Denote by[u,k] the event in ℱ that the space time u is reachable from (s,0) in k hops.Steady traffic assumption: the following two are true in (Ω,ℱ,P).(i)
All the carries are independent.(ii)
[u,k] for each k≤H are independent.If it is true, the probabilityP([u,k]) takes a value that only depends on u for each fixed k, letting the reachability to u not affect each other. Then, the algorithm shown in Section 2.3 will compute the communication probability exactly.There are some input instances for which the assumption holds strictly. One such case is significant: when we have the exact schedule of every car, or(A,u) satisfy the following.Exact schedule assumption: P(A,u) is either 1 or 0 for every car A and space time u.It means that it is either true or false ifA appears at u. The following lemma says that it is only a special case of the steady traffic assumption.Lemma 1.
The exact schedule assumption implies the steady traffic assumption.Proof.
Suppose thatP(A,u) is either 0 or 1 for every (A,u). The probability of (A,u) given any condition is either 0 or 1. The probability that a communication path occurs is 0/1. Thus, P([u,k]) is also 0/1 for any k≤H. The event [u,k] is independent of the others as the last paragraph in Appendix A says. Since carries (u,k) have probabilities 0 or 1, it implies the steady traffic assumption.Thus, if we have exact schedules of the cars, we can simply use the algorithm in Section2.3 setting P(A,u)=1/0 to compute the exact communication probability.A natural question occurs; how true is steady traffic assumption in real traffic scenes? We think that[u,k] and carries are well independent in practice if considered u=(x,t) are distinct enough. Events [u,k] with similar x and t affect each other, since they share large common parts of major communication paths. In Section 3, we compare the performance of the probabilistic protocol with that of GPSR in a challenging simulation testbed. We choose 100 m and 5 seconds as the unit differences of x and t, respectively, to avoid considering similar u too often. With the coarse resolutions, the probabilistic protocol will successfully capture the tendency of the vehicle mobility to contribute to good communication performances.


## 2.3. The Basic Algorithm

We show below our basic algorithm to compute communication probabilities. Its primary input is thecarry probabilityP(u1,u2) that there exists a car that appears at the space time u1 and moves to u2 for every carry (u1,u2).Notice that(2)(u1,u2)=⋁everycarA(A,u1)⋀(A,u2),
in the probability space (Ω,ℱ,P), since the carry (u1,u2) is the event in ℱ that some A appears at u1 and moves to u2. Recall the problem of computing communication probabilities formulated in Section 2.2. Since the conditional probability of (x2,t+1) given that (x1,t) is input for all xi and t, it means that the probability of the event (A,u1)⋀(A,u2) is determined uniquely. Movements of distinct cars are independent. The probability of the carry (u1,u2) is uniquely determined by the input instance of the problem.Now, assume the steady traffic assumption.SteadyTraffic illustrated in Algorithm 1 computes the communication probability for any given pair of source and destination.Algorithm 1
Algorithm SteadyTrafficInputs:T: time limit,H: maximum number of hops,M: map with m positions,R: transmission range,P(u1,u2): carry probability for every (u1,u2), that is, probabilitythat a car appears at space timeu1 and moves to u2,s,d∈M: source and destination on the map M.Output:Communication probabilityρ(s,d,T) from s to d with time limit T.begin(1). /* The final value of Answer(x,t,k) will be the probability that thereexists a communication path from(s,0) to (x,t) with at most k carries. */(2). Forevery space time u=(x,t)doAnswer(x,t,0)=0;(3). Answer(s,0,0)=1;(4). fork=1toHdo4-1.for every space time u=(x,t)do4-1-1.Answer(x,t,k)=P((s,0),u);4-1-2.for every other space time u1=(x1,t1) such that t1≤tdo4-1-2-1./* Let D(x) for x∈M be the set of R-neighbors of x   */4-1-2-2.p1=1-∏x2∈D(x1)(1-Answer(x2,t1,k-1));4-1-2-3.p2=P(u1,u)·p1;4-1-2-4.Answer(x,t,k)=Answer(x,t,k)(1-p2)+p2;4-1-3.end    for4-2.end    for(5).end    for(6). return1-∏x∈D(d)t≤T(1-Answer(x,t,H));endIts correctness proof is found in AppendixB. We will present a general method to obtain P(u1,u2) from field data in Section 2.4 and a more practical version in Section 2.5.The asymptotic running time ofSteadyTraffic is found O(Hm2T2R2) in a straightforward manner. In our simulation test with a careful choice of the parameter set, it runs in few minutes to finish computation for each s and d.If the exact schedule assumption holds,P(u1,u2) is 1 if and only if there exists a car A such that P(A,u1)P(A,u2)=1. We can input them into SteadyTraffic to compute ρ(s,d,T).


## 2.4. To Measure Carry Probabilities from Field Data

The primary input to AlgorithmSteadyTraffic is the probabilities of P(u1,u2) of the carries. Theoretically, all we need is P((A,u1)⋀(A,u2)) for every car A and space times ui that is, the probability that the given car A appears at u1 and moves to u2. Then, the carry probability is computed as(3)P(u1,u2)0=1-∏everycarA(1-P((A,u1)⋀(A,u2))),
by (1) and (3).There are ways to computeP((A,u1)⋀(A,u2)) from field data. The following two steps provides a general one.Measure the intersection probabilities
Some nodesv on the map M represent intersections. The edges l from v are the roads from v. Theintersection probabilityQ(l,l′,v) is the probability that a car moves from the road l to l' at the intersection v. We first measure this quantity from real field data, by simply finding the ratio of the cars to choose the road l' out of all the cars running toward v on l.CalculateP((A,u1)⋀(A,u2))
We repeat the process below for a number of times to average the obtained values ofP((A,u1)⋀(A,u2)). At the beginning of each round, we configure the initial positions of the cars randomly but based on the real statistics. Then, do the following:     (1)
fix each carry(u1,u2) and car A. Let ui=(xi,ti) for i=1,2.(2)
At timet=0,1,2,…,t1, simulate the probabilistic movements of the car using the intersection probabilities so that we know the probability of A being at (x,t) for all x∈M and t≤t1. In the end, we know the probability of A at u1=(x1,t1). Store it into p1.(3)
Fix the position ofA at t=t1 as x1. Simulate the probabilistic movements of A at time t=t1+1,t1+2,…,t2. Find the probability of A at (x2,t2), and store it into p2.(4)
Now,P((A,u1)⋀(A,u2))=p1·p2 is the probability that A appears at u1 and moves to u2.


## 2.5. Practical Refinements

Although the method described so far is mathematically correct for the presented mobility model, we faced essential difficulties when we implementedSteadyTraffic on a testbed described in the next section. Abstracting the problems, we devised a variant of SteadyTraffic that is meant to be used for practice. It is illustrated in Algorithm 2 as SteadyTraffic 2.Algorithm 2:A practical variant of SteadyTraffic.
Algorithm SteadyTraffic2Inputs:T, H, M, R, P(u1,u2), s,d∈M: same as SteadyTraffic,ξ(x1,x2): 1 hop packet error ratio from x1∈M to x2∈M,e(x): expected car density at x∈M,β,ϵ∈(0,1): numeric parameters,dir∈{(0,-1),(0,1),(1,0),(-1,0)}: vector representing the movingdirection.Output:Approximate communication probabilityρ(s,d,T)froms to d with time limit T.begin(1). Forevery space time u=(x,t)doAnswer(x,t,0)=0;(2). Answer(s,0,0)=1;(3). fork=1toHdo3-1.for every space time u=(x,t)do3-1-1.Answer(x,t,k)=P((s,0),u);3-1-2.for every other space time u2=(x2,t2) and u1=(x1,t2)such thati)t2≤t,  ii) x1∈D(x2),  iii) P(u1,u)≥ϵ,iv)(x1-x2)·dir≥0 and iv) (x-x1)·dir≥0/*D(x) is the set of R-neighbors of x∈M*//*· represents the inner product of two vectors */do3-1-2-1.p1=P(u1,u)(e(x1)e(x))β;3-1-2-2.p2=Answer(x2,t2,k-1)(1-ξ(x1,x))p1;3-1-2-3.Answer(x,t,k)=Answer(x,t,k)(1-p2)+p2;3-1-3.end    for3-2.end    for(4).end    for(5). return1-∏x∈D(d)t≤T(1-Answer(x,t,H)(1-ξ(x,d)));endWe summarize below general deployment problems and our solutions in the modified algorithm. First, values computed bySteadyTraffic may include propagated errors. As stated as the steady traffic assumption in Section 2.2, we want the reachability events [u,k] and carries to be well independent of others. If we consider [u,k] with similar space times u=(x,t) too often, it is likely to increase the calculated communication probability much more than the real value. In other words, space times whose car density is large may not be much different from those with small density for the algorithm SteadyTraffic.We multiply, to handle the problem, carry probabilitiesP(u1,u2) by (e(x1)e(x2))β, where ui=(x1,ti) are space times, e(x) are the expected car densities at x∈M, and β∈(0,1) is a numeric parameter to adjust. Step3-1-2-1 of SteadyTraffic2 performs this data modification. It has an effect of emphasizing the differences between large and small car densities. We will choose β=1/2 in Section 3.We could also use coarse space and time resolutions to prevent the error propagation, that is, to use large values of unit differences ofx and t to avoid introducing similar u=(x,t). It also speeds up the algorithm significantly.Loop 3-1-2 ofSteadyTraffic2 has a slightly different structure from 4-1-2 of SteadyTraffic; the former finds any new carry (u1,u)  in the proximity of u2 such that i)–v) and updates Answer(x,t,k) at u simply assuming that the newly detected communication path is independent of the others. Condition iii) discards carries of low probabilities.The above schemes of simplification and data modification effectively compute good approximate values of communication probability with reasonable computational time. This practically solves our first problem of error propagation.Secondly, we have a node differentiation problem. Even if the communication probabilities are accurate, it is occasionally hard in run time to choose a good packet forwarder among the nearby vehicles. We illustrate the problem in Algorithem 1. To resolve it, we restrict considered communication paths so that they are not extended in a specified direction. Conditions iv) and v) of Loop 3–1–2 filter every path withx- or y-component running in the opposite direction to given dir. We call it north, south, west, and east mode when dir=(0,-1),(0,1),(1,0),and(-1,0), respectively. (The map origin is supposed to locate at the upper-left corner.) For example in the north mode, SteadyTraffic 2 does not extend a communication path to location more southern than the current position. It is suggested to combine values of more than 1 modes to refer to in run time to find a good packet forwarder.Third, the probability of successful packet transmission is usually not uniform in a real traffic scene. We approximate it by its time average, that is, we assume that1-hop packet error ratioξ(x1,x2) varies over positions xi∈M and is constant over time. Steps 3-1-2-2 and 5 of SteadyTraffic2 include related multiplications. We could use values of ξ measured in field data possibly in conjunction with an analytical formula such as the one in [10].


## 3. Simulation Results

### 3.1. Testbed Design

We did a performance evaluation of the probabilistic protocol in a simulation testbed shown in Figure4. Its dimension is 1000 m in height and 2000 m in width. A similar road configuration can be found in a big city in the United States such as the one in Chicago downtown. There are 121 intersections in total, the top-left and bottom-right ones of which are assumed to locate at the positions (0,0) and (1000,2000), respectively.Figure 4
The Simulation Testbed.An RSU is placed at(0,1000). Roads 1, 11, 12, and 22 are called arterial and are busy, while the other paths are not. A car with a packet called packet holder enters the testbed at position (1000,x) and time 0, where x is either 0, 200, 400, 600, 800, or 1000. The cars keep moving in the next 70 seconds trying to forward the packet to the RSU.Because the inner roads have sparser vehicles, and there is only one RSU in a fairly large area, it is not easy for the geographical forwarding scheme to have a packet reach the destination. The usual best way is to make a detour on arterial roads. It is essential toquickly inform the cars of a good forwarding path computed from the likelihood of packet reachability. However, the number of intersections is large so that there are many choices for a forwarding path. These make the testbed challenging for the existing routing protocols.A car moves at the speeds of 35 and 25 mph on arterial roads and paths, respectively, except around intersections. Within a 50 m radius of every intersection, the car speed drops down to 15 mph. The following is the list of parameters input to the traffic simulator.(1)
r1: the probability for a car to turn from an arterial road to another, or from a path to another.(2)
r2: the probability for a car to turn from an arterial road to a path.(3)
r3: the probability for a car to turn from a path to an arterial road.(4)
r4: the probability that a car enters the testbed in each half second, at the start/end position of an arterial road.(5)
r5: the probability that a car enters the testbed in each half second, at the start/end position of a path.We tested two scenarios with different parameter sets shown in Table1. Although the car movement rules are made relatively simple, both scenarios create traffic situations sufficiently realistic to a preliminary multihop packet forwarding test. Figure 4 is a snapshot of Scenario 1. Scenario 2 has sparser paths.Table 1
Parameter values to the traffic simulator.
r1r2r3r4r5Scenario 10.40.10.940.30.01Scenario 20.40.060.970.30.01In this setting, we assume transmission rangeR=150m with one hop packet error ratio ξ(x1,x2)=0.15 for every distinct pair of xi∈M.All the cars are equipped with radio devices sending their positions to the nearby cars per second asheart beat (beacon) messages. The relative velocity of two cars does not exceed 70 mph or 31.11 m/sec. With heartbeat messages broadcasted every second, where R=150m, we can assume that each car A knows by its background job the existence of every other car A' in the proximity. Once A receives a packet, it quickly computes the necessary values for A' to decide the next packet holder.It is a common agreement that the initialization time over IEEE 802.11 p standard is about 300 msec. The total time necessary to forward a packet is no more than 500 msec if it is not too large. Assume also that all the cars have a common clock so that packet transmission processes are performed in global half second time slots. The time resolution of the traffic simulator is set as 0.5 second.Setting the maximum numberH of hops as 20, we run SteadyTraffic2 to pre-compute the communication probabilities. We averaged the values in the north and west modes in the left half of the testbed and the ones in the north and east modes in the right half. It took about 3 hours on average to finish computation for each scenario. We stored the obtained values in a lookup table to refer to in run time.


### 3.2. Decision for the Next Packet Holder

Now, we have a good set of communication probabilitiesρ(x,x′,T) from x∈M to x'∈M such that if x or x' is on a path, they are usually distinguishably smaller than values with both x and x' on arterial roads. However, it is still not obvious how to make a good decision for the next packet holder with ρ(x,x′,T).We also pre-computed theeffective average numbers(4)k¯(x)=∑0≤t≤T0<k≤Hk(Answer(x,t,k)-Answer(x,t,k-1))∑0≤t≤TAnswer(x,t,H),
of hops with Answer(x,t,k) obtained when we run  STEADY TRAFFIC. They turned out to be excellent index values for deciding a good packet forwarder.LetΔH(x) be the horizontal distance from x∈M to d, and ΔV(x) the vertical distance from x to d. Furthermore, define(5)Δ(x)={ΔH(x)ifΔH(s)≥ΔV(s),ΔV(x)otherwise.
It measures the distance to the destination from x that is designed suitable for the probabilistic protocol.In run time, decide the next packet holder as follows: ifΔ(x) is much smaller than Δ(s), say at most 1/4, then we regard that the packet is approaching to the destination, so we choose, within the transmission range, a car closest todamong the ones with relatively high values ofρ(x,d,T)and lowk¯(x). If Δ(x)>1/4Δ(s), we choose a car farthest fromswith relatively highρ(x,d,T)and lowk¯(x), regarding that the packet is not close enough to the destination. We call the former and latter cases approach and detour modes, respectively.More precisely, find if(6)S=(ρ(x,d,T)≥maxραρ)⋀(k¯(x)≤mink¯αk¯),,for every car at position x in the proximity. Here, αρ and αk¯ are input constants, maxρ is the maximum value of ρ(x,d,T) and mink¯ the minimum value of k¯(x) in the proximity, respectively. Setting αρ=0.4 and αk¯=1.05 in the approach mode, pass the packet to the car closest to d such that S is true. In the detour mode with αρ=0.8 and αk¯=1.05, pass to the car farthest from s such that S.The above decision process is quick since it does not require heavy in-vehicle computation. The running time is comparable to that of GPSR.


### 3.3. Measured Data

We show the measured delivery ratio and delay time in Figure5, plotting them over the horizontal position x of the packet holder at time t=0. We executed 20 trials for both Scenarios 1 and 2, each of which run for 70 seconds. The performances of the probabilistic protocol are compared with those of GPSR. We summarize the related parameter values in Tables 2 and 3.Table 2
Run-time parameter values for data measurement.
Iteration count20Clock cycle0.5 secTrial time70 secTransmission range150 mNumeric parameterαρ in the approch mode0.4Numeric parameterαρ in the detour mode0.8Numeric parameterαk¯1.05Table 3
Parameter values forsteadytraffic2.
Time resolution5 secSpace resolution100 mTime limitT60 secMaximum numberH of hops20Packet error ratioξ(x1,x2)0.15 uniformNumeric parameterβ1/2Measured delivery ratio and delay time.
(a)(b)As mentioned before, we runSteadyTraffic2 in north and east modes for each source in the west half of the testbed. The east half is handled symmetrically. We took the average of the two modes to refer to in the run time.When the probabilistic protocol run in both scenarios, we observed expected packet trajectories in most cases. They initially run on the south arterial road (no.22) either to east or west, then go north to reach the RSU on the north arterial road. Our scheme of switching from the detour to approach mode functioned well.This did not happen for GPSR; occasionally, the packet could not find a forwarder in the north effectively so that it migrated in the middle of the testbed for a long time.As a result, the probabilistic protocol dramatically improves the delivery ratio over GPSR. Its average delay time over all start positionx is smaller than that of GPSR. The improvement, however, is not as drastic as that of the delivery ratio. It is due to the lengths of trajectories why it tends to produce not too small latency, that is, packets move on a much longer way than those controlled by GPSR.


## 3.1. Testbed Design

We did a performance evaluation of the probabilistic protocol in a simulation testbed shown in Figure4. Its dimension is 1000 m in height and 2000 m in width. A similar road configuration can be found in a big city in the United States such as the one in Chicago downtown. There are 121 intersections in total, the top-left and bottom-right ones of which are assumed to locate at the positions (0,0) and (1000,2000), respectively.Figure 4
The Simulation Testbed.An RSU is placed at(0,1000). Roads 1, 11, 12, and 22 are called arterial and are busy, while the other paths are not. A car with a packet called packet holder enters the testbed at position (1000,x) and time 0, where x is either 0, 200, 400, 600, 800, or 1000. The cars keep moving in the next 70 seconds trying to forward the packet to the RSU.Because the inner roads have sparser vehicles, and there is only one RSU in a fairly large area, it is not easy for the geographical forwarding scheme to have a packet reach the destination. The usual best way is to make a detour on arterial roads. It is essential toquickly inform the cars of a good forwarding path computed from the likelihood of packet reachability. However, the number of intersections is large so that there are many choices for a forwarding path. These make the testbed challenging for the existing routing protocols.A car moves at the speeds of 35 and 25 mph on arterial roads and paths, respectively, except around intersections. Within a 50 m radius of every intersection, the car speed drops down to 15 mph. The following is the list of parameters input to the traffic simulator.(1)
r1: the probability for a car to turn from an arterial road to another, or from a path to another.(2)
r2: the probability for a car to turn from an arterial road to a path.(3)
r3: the probability for a car to turn from a path to an arterial road.(4)
r4: the probability that a car enters the testbed in each half second, at the start/end position of an arterial road.(5)
r5: the probability that a car enters the testbed in each half second, at the start/end position of a path.We tested two scenarios with different parameter sets shown in Table1. Although the car movement rules are made relatively simple, both scenarios create traffic situations sufficiently realistic to a preliminary multihop packet forwarding test. Figure 4 is a snapshot of Scenario 1. Scenario 2 has sparser paths.Table 1
Parameter values to the traffic simulator.
r1r2r3r4r5Scenario 10.40.10.940.30.01Scenario 20.40.060.970.30.01In this setting, we assume transmission rangeR=150m with one hop packet error ratio ξ(x1,x2)=0.15 for every distinct pair of xi∈M.All the cars are equipped with radio devices sending their positions to the nearby cars per second asheart beat (beacon) messages. The relative velocity of two cars does not exceed 70 mph or 31.11 m/sec. With heartbeat messages broadcasted every second, where R=150m, we can assume that each car A knows by its background job the existence of every other car A' in the proximity. Once A receives a packet, it quickly computes the necessary values for A' to decide the next packet holder.It is a common agreement that the initialization time over IEEE 802.11 p standard is about 300 msec. The total time necessary to forward a packet is no more than 500 msec if it is not too large. Assume also that all the cars have a common clock so that packet transmission processes are performed in global half second time slots. The time resolution of the traffic simulator is set as 0.5 second.Setting the maximum numberH of hops as 20, we run SteadyTraffic2 to pre-compute the communication probabilities. We averaged the values in the north and west modes in the left half of the testbed and the ones in the north and east modes in the right half. It took about 3 hours on average to finish computation for each scenario. We stored the obtained values in a lookup table to refer to in run time.


## 3.2. Decision for the Next Packet Holder

Now, we have a good set of communication probabilitiesρ(x,x′,T) from x∈M to x'∈M such that if x or x' is on a path, they are usually distinguishably smaller than values with both x and x' on arterial roads. However, it is still not obvious how to make a good decision for the next packet holder with ρ(x,x′,T).We also pre-computed theeffective average numbers(4)k¯(x)=∑0≤t≤T0<k≤Hk(Answer(x,t,k)-Answer(x,t,k-1))∑0≤t≤TAnswer(x,t,H),
of hops with Answer(x,t,k) obtained when we run  STEADY TRAFFIC. They turned out to be excellent index values for deciding a good packet forwarder.LetΔH(x) be the horizontal distance from x∈M to d, and ΔV(x) the vertical distance from x to d. Furthermore, define(5)Δ(x)={ΔH(x)ifΔH(s)≥ΔV(s),ΔV(x)otherwise.
It measures the distance to the destination from x that is designed suitable for the probabilistic protocol.In run time, decide the next packet holder as follows: ifΔ(x) is much smaller than Δ(s), say at most 1/4, then we regard that the packet is approaching to the destination, so we choose, within the transmission range, a car closest todamong the ones with relatively high values ofρ(x,d,T)and lowk¯(x). If Δ(x)>1/4Δ(s), we choose a car farthest fromswith relatively highρ(x,d,T)and lowk¯(x), regarding that the packet is not close enough to the destination. We call the former and latter cases approach and detour modes, respectively.More precisely, find if(6)S=(ρ(x,d,T)≥maxραρ)⋀(k¯(x)≤mink¯αk¯),,for every car at position x in the proximity. Here, αρ and αk¯ are input constants, maxρ is the maximum value of ρ(x,d,T) and mink¯ the minimum value of k¯(x) in the proximity, respectively. Setting αρ=0.4 and αk¯=1.05 in the approach mode, pass the packet to the car closest to d such that S is true. In the detour mode with αρ=0.8 and αk¯=1.05, pass to the car farthest from s such that S.The above decision process is quick since it does not require heavy in-vehicle computation. The running time is comparable to that of GPSR.


## 3.3. Measured Data

We show the measured delivery ratio and delay time in Figure5, plotting them over the horizontal position x of the packet holder at time t=0. We executed 20 trials for both Scenarios 1 and 2, each of which run for 70 seconds. The performances of the probabilistic protocol are compared with those of GPSR. We summarize the related parameter values in Tables 2 and 3.Table 2
Run-time parameter values for data measurement.
Iteration count20Clock cycle0.5 secTrial time70 secTransmission range150 mNumeric parameterαρ in the approch mode0.4Numeric parameterαρ in the detour mode0.8Numeric parameterαk¯1.05Table 3
Parameter values forsteadytraffic2.
Time resolution5 secSpace resolution100 mTime limitT60 secMaximum numberH of hops20Packet error ratioξ(x1,x2)0.15 uniformNumeric parameterβ1/2Measured delivery ratio and delay time.
(a)(b)As mentioned before, we runSteadyTraffic2 in north and east modes for each source in the west half of the testbed. The east half is handled symmetrically. We took the average of the two modes to refer to in the run time.When the probabilistic protocol run in both scenarios, we observed expected packet trajectories in most cases. They initially run on the south arterial road (no.22) either to east or west, then go north to reach the RSU on the north arterial road. Our scheme of switching from the detour to approach mode functioned well.This did not happen for GPSR; occasionally, the packet could not find a forwarder in the north effectively so that it migrated in the middle of the testbed for a long time.As a result, the probabilistic protocol dramatically improves the delivery ratio over GPSR. Its average delay time over all start positionx is smaller than that of GPSR. The improvement, however, is not as drastic as that of the delivery ratio. It is due to the lengths of trajectories why it tends to produce not too small latency, that is, packets move on a much longer way than those controlled by GPSR.


## 4. Conclusions

We have presented the notion of a communication path and probability in a general framework that handles the nature of multihop routing in a VANET. Under certain mathematical assumption, the communication probability is proven computed accurately by the algorithmSteadyTraffic. Use this quantity to decide a good packet forwarder in a real VANET. The simulated results show that the probabilistic protocol improves the performances much in a very challenging testbed, after the algorithm is refined for the practical issues.For further research, it is significant to find a method to useSteadyTraffic or SteadyTraffic2 in real-time computation. It is possible that a car is provided road density information by an extra method such as cellular network. It would be nice if one can find, quickly without precomputation, good paths over V2V multihop communications for a packet or a group of packets. The running time of the algorithms must be improved much.In addition, it is theoretically interesting to seek for a way to efficiently compute the probability of logical sum∨((e∈S)e) for an event set S⊂ℱ that is not necessarily independent. The hardness of computing communication probabilities derives from the mutual dependence of communication paths. There may be a scheme for fast computation under an assumption of restricted dependence.



---

*Source: 185791-2010-10-11.xml*