{'fraction_non_alphanumeric': 0.03953721149317004, 'fraction_numerical': 0.011393075836081018, 'mean_word_length': 4.592525518603885, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Proactive Doppler Shift Compensation in Vehicular Cyber-Physical Systems

In vehicular cyber-physical systems (CPS), safety information, including vehicular speed and location information, is shared among vehicles via wireless waves at specific frequency. This helps control vehicle to alleviate traffic congestion and road accidents. However, Doppler shift existing between vehicles with high relative speed causes an apparent frequency shift for the received wireless wave, which consequently decreases the reliability of the recovered safety information and jeopardizes the safety of vehicular CPS. Passive confrontation of Doppler shift at the receiver side is not applicable due to multiple Doppler shifts at each receiver. In this paper, we provide a proactive Doppler shift compensation algorithm based on the probabilistic graphical model. Each vehicle pre-compensates its carrier frequency individually so that there is no frequency shift from the desired carrier frequency between each pair of transceiver. The pre-compensated offset for each vehicle is computed in a distributed fashion in order to be adaptive to the distributed and dynamic topology of vehicular CPS. Besides, the updating procedure is designed in a broadcasting fashion to reduce communication burden. It is rigorously proved that the proposed algorithm is convergence guaranteed even for systems with packet drops and random communication delays. Simulations based on real map and transportation data verify the accuracy and convergence property of the proposed algorithm. It is shown that this method achieves almost the optimal frequency compensation accuracy with an error approaching the Cram\'{e}r-Rao lower bound.

of communication and control is a promising direction to enhance traffic safety and efficiency.
In vehicular CPS, vehicle safety information, e.g., speed, location, and acceleration, are shared with high reliability among different vehicles, so that cooperative vehicle control [1] can be applied to improve the driving safety and alleviate the traffic congestion. The U.S. Department of Transportation estimates that vehicular CPS could help address up to 81 percent of crash scenarios with unimpaired drivers, preventing tens of thousands of automobile crashes every year [2].
Doppler shift, which is the perceived change in frequency of wave emitted by a source which is moving relative to an observer, exists among vehicles due to their mobility. Since safety information is shared via wireless waves at specific frequency, the received waves would be moved from the desired frequency due to Doppler shift, which consequently decreases the reliability of the recovered safety information and thus jeopardizes the safety of vehicular CPS.
More specifically, safety information is shared via dedicated short range communications (DSRC) [3] and IEEE 802.11p protocal, which utilize orthogonal frequency division multiplexing (OFDM) carrier waves to improve spectrum efficiency on 5.9GHz band. Although IEEE 802.11p is considered the de facto standard for on-the-road communications [4], [5], researchers, manufacturers and stakeholder indeed have started to investigate the usability of Long Term Evolution (LTE), in which orthogonal frequency-division multiple access (OFDMA) is adopted for multiplexing, to support vehicular communications. Interesting readers please refer [5]- [10] and the references therein. Another interesting point is that several auto manufacturers are considering solutions for communication in inter-vehicle communication environments. As Fig. 1. Orthogonal sub-carriers are utilized for vehicle safety information sharing. At the frequency that one sub-carrier takes its peak value, all other sub-carriers are zero. Hence, sampling at frequencies that take peak values is important for safety information recovering at the receiver. reported in [5], several original equipment manufacturers have announced agreements with cellular carriers to use equipment from those specific carriers in their vehicles for Internet access and other services. This entails the use of a LTE modem installed in cars and the use of LTE (or LTE-advanced) networks of carriers for several services. Moreover, recently, the Qualcomm Snapdragon automotive development platform, which supports not only IEEE 802.11p but also LTE for dedicated short range communications (DSRC) [3], was released [9] to enable auto manufactures, suppliers and developers to rapidly innovate, test and deploy vehicular applications. The OFDMA signal can be described as a set of closely spaced frequency division sub-carriers. In the frequency domain, each sub-carrier is in sinc function form and sub-carriers are allocated to different users. To deliver the safety information, each sub-carrier is modulated with a conventional digital modulation scheme (such as QPSK, 16-QAM, etc.) and will be recovered at the receiver. As shown in Fig. 1, though the side lobes of different sinc signals overlap with each other, at the peak of each sinc signal, all other sinc signals are zero. This fact guarantees that there is no inter-carrier interference if the receiver samples exactly at these peak locations. The peak locations may deviate from the pre-defined frequency due to Doppler shift. Because the relative speed between vehicles may be high and results in large Doppler shift, the sampled frequency can not be exactly at the individual peak. Therefore, the sampled value contains not only the desired sub-carrier information but also those from other sub-carriers as interferences. Doppler shift would destroy the orthogonal property of different sub-carriers, and it is shown by theoretical analysis and verified by experiments that Doppler shift leads to degradation of system capacity and bit error rate [11].
Doppler shift compensation has been studied for one pair transceiver with centralized processing method. However, existing solutions [12]- [14] cannot be applied to vehicular CPS due to the following difficulties: 1) For communications between one pair transceiver, the frequency shift can be estimated and compensated at the receiver side [12]- [14]. In vehicular CPS, however, at each receiver safety information from different vehicles arrives at the same time on different subcarriers, therefore it is necessary to adjust the sampling frequency to compensate frequency offsets caused by different Doppler frequency shifts. Let i and j denote the transmitter and receiver respectively. Via training sequence based method [15], each receiver first obtains Doppler shift estimates f i,j and then adjusts the sampling frequency by multiplying exp(−ι 2πf i,j t M ) on the t th sample of the received baseband signal [12], with ι denoting the imaginary unit and M denoting the total parallel subcarriers adopted in the OFDMA scheme. It is evident that when receiver j October 3, 2017 DRAFT receives data from more than one transmitters, it cannot compensate all the Doppler shifts since the received signal is a linear superposition of signals from different transmitters. Therefore it is impossible to adjust the sampling frequency for compensating different frequency shifts. 2) Due to the moving property of vehicles, the network topology is highly dynamic, and vehicles may also randomly join and leave the network. Therefore, a distributed algorithm for frequency shift compensation is more suitable than the centralized method to adapt the varying network topology.
3) As vehicular CPS may have high density and transmit large volume of data [16], [17], it is prone to resulting in broadcasting storm [18], [19], and thus, an algorithm with communication overhead linearly scaling with the vehicle density is desired. To solve the above challenges, distributed algorithm is proposed and is adopted after each receiver obtains the Doppler shifts estimate with the training based method.

B. Contributions and Organization of the paper
To address above challenges, we propose proactive Doppler shift compensation algorithm based on the probabilistic graphical model. We assume data are transmitted frame by frame.
Each time, when the transmitter sends a data frame out, it is reasonable to assume that Doppler shift for this data frame is a fixed constant due to the fact that the time duration for each data frame is much smaller than the vehicle speed change. The proposed algorithm compensates Doppler shift for each data fame in a distributed fashion. We study this algoirthm from both algorithm design and theoretical analysis perspectives.
From the algorithm design perspective, we construct a probabilistic graphical model to reveal the conditional independence structure of Doppler shifts in vehicular CPS. Though the classical belief propagation (BP) algorithm [20] can be applied to distributed frequency shift compensation, the number of messages involved in BP algorithm at each iteration grows quadratically as the number of vehicles increases, leading to information network congestion. To overcome this problem, we propose a novel distributed algorithm named as linear scaling belief propagation (LSBP) for its linear scalability to network density. We apply LSBP to a vehicular network with arbitrary topologies and with potential packet drops as well as random transmission and processing delays. It is shown that the total number of messages at each iteration simply equals to the number of vehicles.
From the theoretical analysis perspective, the convergence properties are analyzed for LSBP.
Note that though BP has gained great success in many applications, it is found that BP may diverge if the network topology contains circles, and the necessary and sufficient convergence condition is still an open problem. Thus, BP is not reliable for vehicular CPS. In contrast, the analytical analysis of the proposed LSBP algorithm shows that LSBP is convergence guaranteed for arbitrary vehicular network topology and is robust to packet drops and random delays.
Besides, even with different initial values, the LSBP converges to a unique point. The above theoretical analysis is also verified by simulations, and it is shown that the proposed LSBP algorithm converges quickly with the estimation mean-square-error (MSE) approaching the Cramér-Rao lower bound (CRLB) even under dynamic topologies. Previous works on distributed estimation [21], [22] focus on static network and convergence of standard BP for distributed estimation is analyzed. However, vehicular network is dynamic and may be very dense in certain area. This paper proposes LSBP algorithm, in which the updating procedure is designed in a broadcasting fashion to reduce communication burden and convergence guaranteed property is analytically shown.
The rest of the paper is organized as follows. A motivating example is shown in Section II to provide some intuitive insights. The general model and problem formulation are introduced in Section III. The distributed estimation algorism based on probabilistic graphical model is presented in Section IV. In Section V, convergence property of the proposed algorithm is analytically proved. Simulation results of proactive frequency shift compensation are illustrated in Section VI. Concluding remarks are given in Section VII.
Notations: Boldface uppercase and lowercase letters represent matrices and vectors, respectively. E denotes the statistical expectation operator. A −1 and A T denote the inverse and the transpose of matrix A, respectively. Notation N (x; µ, P ) stands for the probability density function (PDF) of a Gaussian random variable x with mean µ and variance P . Symbol ∝ represents the linear scalar relationship between two real valued functions, and diag{A} refers to taking the diagonal element of A.

II. MOTIVATING EXAMPLE
Combating Doppler shift is also a problem in nature. Certain species of bats, who can produce constant frequency echolocation calls, compensate for the Doppler shift by lowering their call frequency as they approach a target. This keeps the returning echo in the same frequency range of the normal echolocation call. This dynamic frequency modulation was discovered by Hans Schnitzler in 1989 [23]. Inspired by this example, we propose proactive frequency shift compensation at each transmitter to mitigate each pair of Doppler shift in vehicular networks.
In the following we give a three-vehicle example to explain the main idea.
A vehicular CPS consisting of three vehicles as shown in Fig. 2 and f 2 + f 3 = f 2,3 , there will be no frequency offset for each received signal at any vehicle.
How to obtain f i (f 1 , f 2 , and f 3 in this example) is not an easy problem due to the following challenges: • f i,j (f 1,2 , f 1,3 and f 2,3 in this example) cannot be exactly known since the true relative frequency shift f i,j can only be approximated via statistical estimate [12] or measurements.
• Since the number of vehicles is large, the centralized method, which requires the information of all f i,j and the network topology of vehicular CPS, is difficult to be implemented. Hence, distributed estimation which only involves local computation at each vehicle is desired.
• The distributed method needs additional information exchange between neighbors for iterative updating, and the number of messages needed for updating should be linear scaling with the vehicle density.
• The distributed estimation algorithm should also be adaptive to the dynamic topology of vehicular CPS. Besides, convergence of the algorithm has to be guaranteed.

III. PROBLEM FORMULATION AND MODELING
A. Optimal Performance In practice, we can only obtain the measurement or estimate [12], [24] of f i,j , denoted as r i,j , between neighboring vehicles {i, j} ∈ E. Thus, we have where n i,j is the estimation error. It is known that the maximum likelihood estimates of n i,j is asymptotically Gaussian distributed [12], that is, n i,j ∼ N (n i,j ; 0, σ 2 i,j ). Letf i denote the estimate of f i . The estimation MSE, defined as E{(f i −f i ) 2 }, is used to evaluate the performance of the estimator with the lower bound of MSE given as the performance benchmark. Define (1) with respect to all i and j into a matrix form, we obtain where r is a vector containing r i,j with ascending indices first on i and then on j, and n containing n i,j with the indices i, j ordered in the same way as in r. Then, n ∼ N (n; 0, R), where R is a diagonal matrix with σ 2 i,j as diagonal elements which have the same order as r i,j in r. a 1 A is a matrix containing 0 and 1 to make (2) hold for each (i, j) ∈ E, and a 1 is its first column. Note that (2) is a standard linear model, so the Cramér-Rao lower bound (CRLB) of f , which provides the lower bound of the achievable MSE of any unbiased estimator, can be easily computed as [25] CRLB The maximum likelihood estimator is the best linear unbiased estimator approaching CRLB for the linear model of (2), and is given by [25] [f 2 , . . . ,f N ] T arg max Implementing (4), however, not only requires bringing all r i,j and σ 2 i,j to a central computing unit, but also needs the topology of G to construct r and A. Thus, the maximum likelihood estimator is not scalable with network size, which causes heavy communication burden by transmitting data from network border to control unit. Besides, (4) needs to be re-computed frequently due to the dynamic property of vehicular networks. Therefore, distributed estimation, where each vehicle performs estimation with local information, sounds promising [26]. However, achieving the optimal MSE as in (3) in a distributed fashion without global information is challenging. Leveraging statistical property of {f i } i∈V for distributed algorithm design is one promising direction. We next introduce the probabilistic graphical model to reveal conditional independence structure of Doppler shifts in vehicular CPS.

B. Primer on Probabilistic Graphical Model
In a probabilistic graphical model, each vertex (node) represents a random variable, and there are a set of edges joining some pairs of vertices. The graph gives a visual way of understanding the joint distribution of an entire set of random variables on graph [16], [27]. Fig. 3 shows an example of a graphical model for a vehicular CPS with 9 vehicles. Vertex i in the graph corresponds to f i that needs to pre-compensate on vehicle i. According to (1), the probabilistic relationship between f i and f j is captured by N (r i,j ; f i +f j , σ 2 i,j ) and denoted on the graph by an edge linking these two variables. Hence, the probabilistic graphical model has the same network topology as the vehicular CPS. In this model, the absence of an edge between two vertices has a special meaning: the corresponding random variables are conditionally independent given one node's neighboring nodes. These neighbors are known as Markov blanket, i.e., f i and f j are Inspired by BP, a distributed estimation algorithm named as linear scaling BP (LSBP), which has low communication overhead and is convergence guaranteed, is then proposed. Notice that communication scheme [28] that is robust to Doppler shift can be adopted for message exchange before Doppler shifts are compensated.

A. Belief Propagation Algorithm
With Gaussian belief propagation (BP) [20] algorithm for linear Gaussian model, at every iteration, each node sends a (different) message to each of its neighbors and receives a message from each neighbor. The message from vehicle j to vehicle i is defined as the product of the with messages received from all neighbors except i, and then maximized over all involved variables except f i . Mathematically, it is defined as The message m (l) j→i (f i ) is computed and exchanged among neighbors. One possible scheduling for message exchange is that all vehicles perform local computation and message exchange in parallel [29]. In any round of message exchange, a belief of f i can be computed at each vehicle i locally, as the product of all the incoming messages from neighbors, which is given by Note that the message and belief updating rules denoted by (5) and (6) are naturally distributed: (5) is computed internally by j, and then sent to its neighbor i. After receiving all the messages from its neighbors, i computes the belief b (l) (f i ) according to (6).
The message exchange between neighboring vehicles can be realized via local communications; however, as packet drops and random delays are the bottleneck of communication in vehicular CPS [30], their impact on message exchange should be addressed. To do so, totally asynchronous scheduling is adopted. More specifically, each vehicle still performs message and belief computations at the individual predefined time, even when it doesn't receive newly updated messages from some of its neighbors. This totally asynchronous scheduling is defined as follows.
Definition 1 (Totally Asynchronous Scheduling): The message available to j at time l is m The physical meaning of the above definition is that, even though packet drops and random delays may cause some updated messages failed to be received, local computation at each vehicle can still continue with part of the updated messages and part of the outdated messages received at the last iteration. The outdated messages can eventually be replaced by successfully received messages in the future updating. Each vehicle j keeps a buffer with the most recently received messages from all its neighbors, i.e., m (τ k→j (l−1)) k→j (f j ) at iteration time l. Therefore, under packet drops and random delays, the outgoing message m (5) can be computed as Similarly, the belief in (6) can be computed as

B. Message Computation for BP
From (8) and (9), m is a Gaussian function, according to (5), m At this point, we can compute the messages at any iteration. In general, for the l th (l = 2, 3, · · · ) round of message exchange, let the available messages variance and mean at from k to j are C (τ k→j (l−1)) k→j −1 and η (τ k→j (l−1)) k→j , respectivly. Then, j computes and transmits the outgoing messages to each of its neighbors individually. After some straightforward but tedious derivations, reciprocal of the message variance is given by and the message mean is expressed as Due to packet drops and random delays, C (l) j→i −1 and η (l) j→i , may or may not be successfully received by i for updating b (l) (f i ). Following Definition 1, C (τ j→i (l)) j→i −1 and η (τ k→j (l−1)) j→i are used to denote the available information of i at iteration l, then i can compute the BP estimates via (9), which can be easily shown to be b Let l max denote the maximum updating times for each vehicle, and the algorithm terminates when the maximum number of iteration l max is reached, or when ∆ i v th is a threshold. The BP algorithm for proactive Doppler shift compensation is summarized in Algorithm 1.
It is well known that the convergence of BP is not guaranteed for topology with loops.
Consequently, the BP algorithm may either converge or diverge, resulting in unreliable estimates.
Moreover, it is apparent that the outgoing messages, i.e., (10) and (11), to different neighbors are different, and thus, huge amount of information is broadcasted in the network. Such problem is especially serious in dense traffic and leads to information network traffic congestion [18], [19].
To address the above problems, in the next section, we design a novel distributed algorithm, which not only guarantees the iterative updating convergence but also has the property that the amount of information exchange among vehicles is linear to the traffic density.

C. Design of Linear Scaling BP
To get some insights on low communication overhead message passing algorithm, we start by investigating BP in the simplest possible graph: a tree graphical model. In this model, BP computes the maximum likelihood estimate in an efficient way with convergence guaranteed.
In a tree graphical model as shown in Fig 4, for each pair of variables connected by an edge, the variable near the root is named as parent, while the other variable is named as child. Then, the messages of BP can be categorized into two kinds: one is from parent to child denoted as m  c→p (f c ) is a constant for message from child to parent.

Proof 1 See Appendix A.
With Property 1, we can exactly compute the maximum likelihood function for the tree network topology. Then, we apply it to a network containing loops. By simply generalizing Property 1, the message in a loopy graph is computed bym j→i (f i ). For networks with random delays and packet drops, the message updating equation can be easily obtained asm and the outgoing message isb Note that (14) differs from the standard BP of (8) in that each vehicle only transmitsb (l−1) (f j ) to all its neighbors at one time, thenm (l) j→i (f i ) is computed at node i and then the beliefb (l) (f i ) can be obtained according to (14). Because the message need to be transmitted at each iteration equals the number of vehicles, the proposed method is named as linear scaling BP (LSBP).  (16)) for each node only depend on message transmitted from neighbor nodes and are independent of network topology, which further implies that there is no need to construct a tree topology for message scheduling. Next, the explicit message expression of LSBP is computed.

D. Message Computation for Linear Scaling BP
To start the recursion, in the first round of message exchange, the initial incoming message is is a Gaussian pdf, according to (14),m j→i (f i ) is still a Gaussian function. In addition,b (1) (f i ), being the product of Gaussian functions in (15), is also a Gaussian function [31], [38]. Consequently, in LSBP, during each round of message exchange, all the messages are Gaussian functions, and only the mean and the variance need to be exchanged between neighbors.
At this point, we can compute the messages of LSBP at any iteration. In general, in the l th (l = 2, 3, · · · ) round of message exchange, vehicle i with the available message b (τ j→i (l−1)) j (f j ) ∝ N (f j ; µ (τ j→i (l−1)) j , P (τ j→i (l−1)) j ) from its neighbors, computes the outgoing messages via (14). By putting the explicit expression of b τ j→i (l−1) j (f j ) into (14) and after some tedious but straightforward computations, we havem and η (l) Furthermore, during each round of message exchange, each vehicle computes the belief for f i via (15), which can be easily shown to beb The updating is iterated between (16), (17) and (18), (19) at each vehicle in parallel. One way to terminate the iterative algorithm is that all vehicles stop updating when a predefined maximum number of iterations l max is reached. Since LSBP is convergence guaranteed as proved in the next section, the termination can also be implemented once the algorithm converged. The LSBP algorithm is summarized in Algorithm 2.
as can be seen from Table I, the number of messages exchanged in the network with BP is Thus the total number of messages, grows quadratically when the vehicle number N increases, leading to information network congestion. While with LSBP it is only N . Therefore, the number of messages involved in BP increases much faster than that with LSBP which leaves the network vulnerable to information congestion. To get further insights of the proposed LSBP algorithm, its convergence property is studied in the following section.

V. CONVERGENCE ANALYSIS FOR LSBP
As BP may diverge if the network topology contains circles [32], [33], which is often the case in vehicular CPS, BP is not reliable. In this section, we analytically proved that the proposed LSBP algorithm is convergence guaranteed with feasible initial values, and µ

A. Convergence of Message Variance
By substituting (16) into (18), the updating equation of P (l) i is given by Let p (l) be a vector containing of all the message variance at the l th iteration, i.e., p (l) N ] −1 ] T and define an evolution function F as p (l+1) = F(p (l) ). We will say that a p (0) > 0 is a feasible initial value if p (0) > 0 satisfies F(p (0) ) ≥ p (0) ) or F(p (0) ) ≤ p (0) .
Notice that one easy obtained feasible p (0) is by setting P (l) i −1 = 0. Next, it is shown that the function F(·) has the following properties for arbitrary p (0) > 0.

Proof 2 See Appendix B
Then we can prove the convergence property of the belief variance in LSBP.
With the same argument, we can prove that if p (1) ≤ p (0) , p (l) is a monotone decreasing positive sequence, which is convergence guaranteed.
In the subsequent, the unique property of the converged p (l) for a specify network topology is proved by contradiction. Suppose p * andp * are two distinctive fixed point, and without loss of generality assume p * >p * . Due to the elements in p andp are all positive, there exists α > 1 such that αp * ≥ p * and for some particular index i that On the other side, following the definition of fixed point, we have p where the inequality comes from the monotonic property (P2-3). Then following the scalability property (P2-2), we have Hence, (21) and (22) is a contradiction, and p * andp * are the same fixed point a specify network topology. Therefore the element P Next, we focus on the convergence property of the estimate µ (l) i with the conclusion that P (l) i has converged.

B. Convergence of Message Mean
Suppose the converged value of P (l) j is P * j , then following (16), we have C j→i is also convergence guaranteed, and then the converged value is denoted by C * j→i . Putting C * j→i into (18) and substituting the result into (19), we have In the subsequent, we prove the following theorem for the convergence property of µ (l) i .
Theorem 2 For asynchronous updating, with feasible initial P (0) j , the mean of LSBP algorithm, i.e., µ (l) i in (23), converges to a fixed point irrespective of the network topology.
then (23) can be expressed as Due to the fact that f 1 is the reference for pre-compensated frequency shift estimation, thus µ to be investigated. Hence, we separate µ 1 from j∈B(i) , K j,i µ (l−1) j in (24), and the result can be expressed as where 1 j,i is an indicator random variable with 1 j,i = 1 if {j, i} ∈ E otherwise is 1 j,i = 0.
Next, the convergence of µ Piling up (26) for all µ i with the increasing order on i, we obtain the updating equation for all µ as with the i th row of K being k T i . According to the definition of k i above (26), the summation of k i can be written as Therefore, K is a nonnegative matrix having row sums less than or equal to 1 with at least one row sum less than 1.

VI. EXPERIMENT EVALUATIONS
In this section, realistic data traces and simulation tools are employed to evaluate the proposed algorithm for proactive Doppler shift compensation. As shown in Fig. 6, a real street map covering a 3km × 4km area of Montreal is generated from OpenStreetMap [35]. Hereafter, and unless stated otherwise, 100 vehicles are generated on the map by simulation tool SUMO [36].
The traffic data generated by SUMO includes vehicular positions, destinations, travelling paths and speeds. These parameters are also within practical limitations as in Fig. 6. For example, vehicle speeds are within the speed limitation of corresponding street. According to [3], the communication range of each vehicle is set to be 800m. The true Doppler shift between each Fig. 6. The street map covering a 3km × 4km area of Montreal from OpenStreetMap [35], with 100 vehicles generated by SUMO [36]. The yellow triangles stand for vehicles running on streets.
pair of vehicles within communication range can be computed according to where v i,j is the relative velocity between vehicles i and j, f 0 is the carrier frequency, and c is the speed of waves.
In practice, message exchange between vehicles may fail due to various factors, like separation distance, signal propagation environment, received signal strength, transmission power and modulation rate [30]. In the following experiments, different packet delivery ratio (PDR), which is the ratio of the number of packets successfully delivered to destination compared to the number of packets that have been sent out by the transmitter, is set to show the impacts of packet drop on proposed algorithms.
First, the convergence property of P (l) i as shown in Theorem 1 is verified by simulations.
The network topology is randomly generated by SUMO, and PDR is set to be 80%. The initial message variance for each P is demonstrated in Fig. 7 as an example. It is clear that though P (l) 6 keeps monotonic increasing or decreasing with different initial values, they converge to the same point.
Thus, the conclusion of Theorem 1 is verified by simulations that with arbitrary feasible initial value, the belief variance P (l) i of LSBP shown in (20) converges to a unique fixed point.
Next, the accuracy and convergence property off i is investigated. Average MSE, defined , is adopted as the performance criteria. Fig. 8 shows that for different PDRs (60% and 80%), the convergence speeds of BP and LSBP algorithms differ. Nevertheless, even for PDR as low as 60%, both BP and LSBP converge to a fixed estimate point within 10 iterations, and thus, they are robust to packet drops. Besides, LSBP has the MSE performance that approaches the CRLB. Note that BP can also reach the CRLB as shown in Fig. 8, but its  convergence for loopy topology network is not guaranteed, and its communication overhead is large as shown in Table I. BP and LSBP is compared in Fig. 10. It is shown that as the vehicle number increases from 70 to 120, the number of messages required to be transmitted in BP increases quickly, which may lead to information network congestion [18], [37]. It verifies the analysis of Table I that  of messages increases quadratically for dense network. In contrast, the number of messages involved in LSBP increases mildly, which, in fact, is simply equal to the number of vehicles.
Next, the number of iterations with BP and LSBP for different scales of vehicles are studied.
As shown in Fig. 11 Take a network with 100 vehicles as an example, as shown in Fig. 11, the average number of iteration is around 7. Since the proposed method is a parallel algorithm, the transmission time is smaller than 0.4 × 7 = 2.8ms, which is a acceptable overhead for wireless communication.
At last, we show that even for highway environment where the network topology is linear and the nodes are sparsely connected the proposed LSBP algorithm still works. We assume 10 vehicles scattered as a line in a highway and each vehicle's speed is generated by SUMO simulations. It is assumed that each vehicle can only communicate with its front and back neighbors. The convergence performance of estimation MSE is given in Fig. 12. It is shown that it is less accurate than the dense network topology case that we considered in Fig. 8 where the third equation is from N (x; µ, σ 2 ) = N (µ; x, σ 2 ), and the fourth equation comes from the fact that maximum value of Gaussian PDF only relates to its variance. Next, we compute the message from p to its parent p . According to (5) where the first equation is due to m We first prove P2-1. Since σ 2 i,j > 0 and P (0) j > 0, according to (20), it is obvious that [P (1) i ] −1 > 0. Then, it can be easily proved by induction that for arbitrary l, P Furthermore, according to (20) it is shown that P Next, we prove P2-2. Let F i (p (l) ) denote the i th element in F(p (l) ), then according to (20), for arbitrary α > 1, we have αF i (p (l) ) = α j∈B(i) Besides, the corresponding i th element in F(αp) is given by Computing (31)-(32), we have As α > 1 and σ 2 i,j > 0, it can be concluded that in (33), αF i (p (l) ) − F i (αp (l) ) > 0. The above inequality is satisfied for arbitrary i, so we have ∀α > 1, αF(p) > F(αp). Thus, the scalability is proved. Then, according to (20), P Vehicle j with j = 1, · · · , N in parallel 4: Compute the outgoing messages C Vehicle j with j = 1, · · · , N in parallel If ∆ i f (l) i −f