Vehicular Fog Computing Enabled Real-time Collision Warning via Trajectory Calibration ^††thanks: Corresponding author: Kai Liu

We analyze the application-layer transmission latency of DSRC based on real-world field-testing data. In Fig. 2, a field testing is carried out on a road intersection without traffic lights. Two vehicles equipped DSRC interfaces are able to communicate with RSU via V2I communication. In particular, we utilize Cohda Wireless MK5 RSU and OBU as DSRC communication interfaces. An RSU is installed at the intersection, which is connected with a notebook as a computation unit of fog node. Vehicles $V_{1}$ and $V_{2}$ are approaching the intersection, and they are sending vehicle status including GPS coordinates, velocity, acceleration, heading direction and timestamp via V2I communication periodically. Fog node receives the packet from vehicles and obtains the packet transmission latency of application-layer of V2I communication.

We employ a regression-type estimation to estimate four parameters of the Stable distribution. First, given observation data as a random simple $x_{1},x_{2},\cdots,x_{n}$ of size $n$, a simple characteristic function $\hat{\phi}(t)$ is defined by

when $\alpha\neq 1$, we denote:

The distribution is assumed symmetric about the center $0$ ($\beta=0,\mu=0$), then we can easily obtain:

We estimate $\alpha$ and $\sigma$ by regressing $y_{k}=\alpha\omega_{k}+b$, where ${b=\ln\left(2\sigma^{\alpha}\right)}$ and ${\omega_{k}=\ln\left(\left|t_{k}\right|\right)}$. We denote $f\left(t_{k}\right)=\ln\left(-\ln\left|\phi\left(t_{k}\right)\right|^{2}\right)$ and use linear regression to address estimation problem by minimizing the mean-square error.

Then, we use the least square method to get estimation value $\hat{\alpha}$ and $\hat{\sigma}$. We denote $E_{(\alpha,b)}=\sum_{k=1}^{K}\left(f\left(t_{k}\right)-y_{k}\right)^{2}$ and the estimated parameters are obtained by resolving the following equations:

The estimated parameters $\hat{\alpha}$ and $\hat{\sigma}$ are represented by:

where ${\hat{b}=\frac{1}{K}\sum_{k=1}^{K}\left(f\left(t_{k}\right)-\hat{\alpha}\omega_{k}\right)}$ and $\bar{\omega}=\frac{1}{K}\sum_{k=1}^{K}\omega_{k}$.

It is easy to see that the real and imaginary parts of $\phi(t)$, $\operatorname{Re}\phi(t)$ and $\operatorname{Im}\phi(t)$, are implied from Equation. 5.

The last two equations lead to

As the estimated parameters $\hat{\alpha}$ and $\hat{\sigma}$ are obtained according to Equation. 10, we estimate another two parameters $\beta$ and $\mu$ by regressing $q_{l}=\mu+cd_{l}$, where ${d_{l}=\operatorname{sgn}\left(t_{l}\right)\left|t_{l}\right|^{\alpha-1}}$ and ${c=\sigma^{\alpha}\beta\tan(\alpha\pi/2)}$. And we denote $\varphi\left(t_{l}\right)=\frac{1}{t_{l}}\arctan\left(\frac{\operatorname{Im}\phi\left(t_{l}\right)}{\operatorname{Re}\phi\left(t_{l}\right)}\right)$ and minimize the mean-square error between $\varphi\left(t_{l}\right)$ and $q_{l}$.

We denote $E_{(c,\mu)}=\sum_{l=1}^{L}\left(\varphi\left(t_{l}\right)-q_{l}\right)^{2}$, and the solution can obtained by resolving the follows:

The estimated parameters $\hat{\beta}$ and $\hat{\mu}$ are obtained by:

where

and $\bar{d}=\frac{1}{L}\sum_{l=1}^{L}d_{l}$.

With equations 10 and 16, and given the observed data set $X^{(0)}$, we obtain the four estimated parameter of the Stable distribution. First, the given observed data set is $X^{(0)}=(x_{1}^{(0)},x_{2}^{(0)},\cdots,x_{n}^{(0)})$. In the $pth$ iteration, we standardize the data by:

where ${\sigma_{0}=\left(x_{.72}-x_{.28}\right)/1.654}$ and $\mu_{0}=25\%$ truncated mean of origin data, $x_{f}$ is $f$ sample quantile fama1971parameter . We choose optimum $K^{(p)}$ point $t_{k}=\pi k/25,k=1,2,\cdots,K^{(p)}$ koutrouvelis1980regression to estimate $\hat{\alpha}^{(p)}$ and $\hat{\sigma}^{(p)}$ in Equation. 10.

where $f\left(t_{k}\right)=\ln\left(-\ln\left|\frac{1}{n}\sum_{j=1}^{n}\exp\left(it_{k}x_{j}^{(p)}\right)\right|^{2}\right)$.

And these estimated parameters are in turns to obtains another two estimated parameters $\hat{\beta}^{(p)}$ and $\hat{\mu}^{(p)}$ with optimum $L^{p}$ points $t_{l}=\pi l/25,l=1,2,\cdots,L^{(p)}$ koutrouvelis1980regression in Equation. 16.

where $\bar{\alpha}={\hat{\alpha}^{(p)}}$ , $\bar{\sigma}={\hat{\sigma}^{(p)}}$ and

After finite iteration, we obtain the four estimated parameters which are satisfy required accuracy. We estimate the Stable distribution model using 1804 data packet transmissions latency obtained by real-world field testing. Fig. 3 shows the probability density function (PDF) of the application-layer delay. The distribution of application-layer delay is almost symmetric ($\alpha=1.77395$) about the Mean ($\mu=72.7343$). We are 95 percent confident that the true Mean lies within the interval $71.9384$ and $73.5301$. As can be seen, the resulting distribution is characterized by the left-skewness ($\beta=1$) and the average of the not small squared differences from the Mean ($\sigma=13.3685$).

We propose a packet loss detection method in fog nodes based on the historical information including data transmission frequency and locations of vehicles. The general idea is described as follows. Each fog node obtains the ID set of vehicles, which are supposed to report their status according to uploading frequency. If the fog node does not receive the packets which are expected. There are two possible cases. First, the vehicle is out of DSRC communication range, thus, the packet cannot be delivered successfully. Second, the vehicle is within the DSRC communication range, however, the packet is lost in the transmission. For those packets, fog node figures out whether the vehicle is out of communication range according its historical position, if not, fog node supposes that the packet is lost.

Without loss of generality, we consider that the system consists of one fog node and a number of vehicles. Note that it can be straightforwardly extended to the scenario of multiple fog nodes. In the concerned scenario, we use set $E=(e_{1},e_{2},\cdots,e_{|E|})$ to denote the time slots, where $e_{k+1}-e_{k}=\frac{1}{\xi}$, $k=1,2,\cdots,|E|$, and $|E|$ is the number of the time slot set. We use set $V=(v_{1},v_{2},\cdots,v_{|V|})$ to denote vehicles, where $|V|$ is the number of vehicles. At time $e_{r}$, the position, velocity, acceleration, heading direction of vehicle $v_{i}$ are denoted by $l_{v_{i}}^{e_{r}}$, $s_{v_{i}}^{e_{r}}$, $a_{v_{i}}^{e_{r}}$ and $d_{v_{i}}^{e_{r}}$, respectively. The location of the fog node is denoted by ${l}_{f}$. And the communication range of DSRC is denoted by $R$. he distance between vehicle ${v_{i}}$ and the fog node at time $e_{r}$ is denoted by $dis({l_{v_{i}}^{e_{r}}},{l_{f}})$. If $dis({l_{v_{i}}^{e_{r}}},{l_{f}})\leq R$, vehicle ${v_{i}}$ can communicate with the fog node.

The fog node receives a number of packets denoted by $M_{e_{k}}={(m_{1},m_{2},\cdots,m_{|{M}_{e_{k}}|})}$ at time $e_{k}$, $e_{k}\in E$, where $m_{q}=({{{l}_{v_{i}}^{e_{r}}},{{s}_{v_{i}}^{e_{r}}},{{a}_{v_{i}}^{e_{r}}},{{d}_{v_{i}}^{e_{r}}}})$, $m_{q}\in{M}_{e_{k}}$ and $|{M}_{e_{k}}|$ is the number of the packets set. Meanwhile, fog node records the received packets of each time slot. At time $e_{k}$, we use set ${H_{e_{k}}}=({M_{e_{1}}},{M_{e_{2}}},\cdots,{M_{e_{k-1}}})$ to denote the historical records. The packet loss detection method is departed into two steps.

$Record):$ Fog node maintains a vehicles ID set ${ID}_{e_{k}}$, which records ID of all vehicles under the coverage of the fog node at time $e_{k}$. ${{ID}_{e_{k}}}$ initialize as ${{ID}_{e_{k}}}={{ID}_{e_{k-1}}}$. When the fog node receives a number of packets $M_{e_{k}}$ at time slot $e_{k}$. For $m_{q}=({{{l}_{v_{i}}^{e_{r}}},{{s}_{v_{i}}^{e_{r}}},{{a}_{v_{i}}^{e_{r}}},{{d}_{v_{i}}^{e_{r}}}})$, ${m_{q}}\in M_{e_{k}}$, if the fog node receives the packet of vehicle $v_{i}$ at the first time, ${v_{i}}\notin{ID}_{e_{k}}$, then adds ${{v_{i}}}$ into ${ID}_{e_{k}}$, ${{ID}_{e_{k}}}={ID}_{e_{k}}\cup\{{v_{i}}\}$. Fog node searches $M_{e_{k}}$ and adds all vehicle ID into the set ${ID}_{M_{e_{k}}}$.

$Detection):$ For the vehicle ${v_{i}}$, ${v_{i}}\in{ID}_{e_{k}}\cup{{ID}_{M_{e_{k}}}}$, there are two cases: a) ${v_{i}}\in{{ID}_{e_{k}}}\setminus{{ID}_{M_{e_{k}}}}$, vehicle $v_{i}$ can communicate with fog node, however, fog node does not receive the packet from it; b) ${v_{i}}\in{{ID}_{e_{k}}}\cap{{ID}_{M_{e_{k}}}}$, vehicle $v_{i}$ can communicate with fog node, and fog node receives its packet. Therefore, for case a, fog node searches ${H_{e_{k}}}$ to get its laster new position ${{l}_{v_{i}}^{e_{r}}}$. Fog node use a distance threshold $\tau$ and a time threshold $\gamma$ to detect whether the vehicle is out of communication range. If the vehicle is within the communication range, fog node detects whether the packet is lost in transmission. If the distance between vehicle ${v_{i}}$ and fog node $dis({l_{v_{i}}^{e_{r}}},{l_{f}})\geq R-\tau$, that means vehicle ${v_{i}}$ is leaving the communication range. So that, fog node remove ${v_{i}}$ from ${{ID}_{e_{k}}}$, ${{ID}_{e_{k}}}={{ID}_{e_{k}}}\setminus\{{v_{i}}\}$. If $dis({l_{v_{i}}^{e_{r}}},{l_{f}})<R-\tau$, that means vehicle $v_{i}$ can communicate with fog node, however, fog node does not receive its packet. The estimated received time is ${e_{r}}+\frac{1}{\xi}$, if ${e_{k}}-{e_{r}}>\frac{1}{\xi}+\gamma$, fog node assume the packet is lost. Otherwise, vehicle $v_{i}$ does not send the packet yet, or the packet is delay due to the wireless communication.

The general procedures of TCCW are described as follows. First, we estimate the transmission latency of each data packet and update their real-time status according to their velocity and acceleration. Second, we detect the lost packets and update their status using packets records in the fog node. Third, we calibrate vehicle trajectories using simulated transmission latency. Then, we predict the future trajectories based on calibrated trajectories. Finally, we predict the potential collisions by calculating the headway of each pair of vehicles and using the headway threshold. At time ${e_{k}}$, vehicle ID set ${ID}_{e_{k}}$, received packets $M_{e_{k}}$, packets records $H_{e_{k}}$ are known as the input of the algorithm. The output of TCCW is the warning message set $W_{e_{k}}$. The detailed procedures of TCCW are presented as follows and the pseudo-code is shown in Algorithm. 1.

$1)\ Updating\ the\ vehicle\ set:$ The purpose of updating the vehicle set is to maintain the vehicle ID set ${{ID}_{e_{k}}}$. We initialize vehicle ID set ${{ID}_{e_{k}}}$ at time ${e_{k}}$ and the ID set ${{ID}_{M_{e_{k}}}}$ of received packets ${M_{e_{k}}}$. ${{ID}_{M_{e_{k}}}}$ contains every vehicle ID in received packets, and if the vehicle ID is not contained by ${{ID}_{e_{k}}}$, then fog node add the vehicle ID into ${{ID}_{e_{k}}}$. The detailed procedure of updating the vehicle set is shown in lines 1-8 in Algorithm. 1.

$2)\ Detecting\ packet\ loss:$ Fog node detects the packet loss in transmission using the method introduced in Section. 4.2. For those vehicles that fog node do not received from them, fog node searches packets records ${H}_{e_{a}}$ to get last new vehicle state information, and add it into ${M_{e_{b}}}$. The detailed procedure of detecting packet loss is shown in lines 9-20 in Algorithm. 1.

$4)\ Predicting\ future\ trajectories:$ For vehicle $v_{i}$, fog node predicts the future trajectories in time slot $({e_{k}},{e_{k}}+{e_{pre}})$, where ${e_{pre}}$ is fog node prediction time. Fog node calculates the vehicle position in every $\frac{1}{\xi}$ second, and appends the position into the trajectory set ${Tra}_{v_{i}}$ of vehicle $v_{i}$. The detailed procedure of predicting future vehicle trajectories is shown in lines 25-32 in Algorithm. 1.

$5)\ Predicting\ potential\ collisions:$ Fog node use a set of warning message ${W_{e_{k}}}=\{{w_{v_{1}}^{e_{k}}},{w_{v_{2}}^{e_{k}}},\cdots,{w_{v_{|V|}}^{e_{k}}}\}$, ${w_{v_{i}}^{e_{k}}}$ is a binary variable to indicate whether vehicle $v_{i}$ has the potential collision. For ${l_{v_{i}}^{e_{u}}}\in{{Tra}_{v_{i}}}$ and ${l_{v_{j}}^{e_{v}}}\in{{Tra}_{v_{j}}}$, fog node calculates the distance of the two vehicles $dis({l_{v_{i}}^{e_{u}}},{l_{v_{j}}^{e_{v}}})$. We assume that vehicle $v_{i}$ and $v_{j}$ pass the same point if the distance $dis({l_{v_{i}}^{e_{u}}},{l_{v_{j}}^{e_{v}}})<d_{col}$. The elapsed time between the front of the lead vehicle passing a point on the roadway and the front of the following vehicle passing the same point is defined as the headway vogel2003comparison . Fog node calculates the headway ${h}_{ij}=|e_{u}-e_{v}|$, and if ${h}_{ij}<\imath$, where $\imath$ is the headway threshold, warning message will be triggered, ${w_{v_{i}}^{e_{k}}}={w_{v_{i}}^{e_{k}}}=1$. Lines 32-42 in Algorithm. 1 show the detailed procedure of predicting potential collisions.

To further demonstrate the performance of our algorithm, we carry out another real-world field testing, and obtain 600 packet transmission delay via two different architectures, both fog computing and cloud computing architecture. In the field testing experiment, when a vehicle is approaching the road intersection, it uploads its status including GPS coordinates, velocity, acceleration, heading direction to fog node. In detail, the vehicle uploading frequency is 1 HZ, in another word, vehicles send packets in every one second. 600 packets, which are transmitted to fog node via DSRC and cloud node via 4G-LTE respectively, are collected and analyzed. Fig. 4 shows that the average delay of packets transmission in cloud computing architecture is 120${ms}$, otherwise, the average delay of the fog computing architecture is 77${ms}$. It is obvious that packet transmission latency in the fog computing based architecture is lower than that in the cloud computing based. Undoubtedly, the results conclusively demonstrate the superiority of vehicular fog computing enabled collision warning system for supporting low latency and safety-critical services. The real-world communication latency obtained by a field-testing experiment is utilized as transmission delay of each packets in the simulation experiment.

First, we employ a vehicle mobility dataset of real taxi trajectory in the experiment. The dataset is collected on an area of about 400 square kilometers from Cologne, Germany for a period of 24 hours in a typical working day uppoor2013 . There are more than 1.2 million individual vehicle trajectories, which contains 3.5 billion points of vehicular positions. The dataset contains vehicles positions in a broad range as a whole city, we choose some different road intersection to implement the system, therefore, the experiment scenarios have different traffic conditions. The features of five scenarios are listed in Table. 2. We evaluate the traffic features with different scenarios in terms of vehicle number, average speed, and average acceleration. Vehicle number is a variable to generally describe vehicular density of the scenario using a number of vehicles on the road or pass through in a period. Average speed is the average speed of vehicles in the scenario. As follows is specific data of vehicle number, average speed and average acceleration in five selected scenarios. In scenarios 1, 2 and 3, fog node is located in a road intersection shown in Fig. 5(a), and scenarios 1, 2, 3 start the experiment at 10 PM, 8 AM and 7 PM, respectively. The fog node is located in center of Fig. 5(b) in scenario 4 and 5. It starts the experiment at 4 PM and 6 PM. Fog node is installed in $(10422.0,12465.3)$ of the first three scenarios and in $(6097.1,14870.0)$ of the last two scenarios. X and Y coordinates represent location of vehicle with two-dimensional in meters.

Apart from the five selected scenarios, we also implement the system under different headway and packet loss rate. Headway is a time slot between two vehicles passes through one point, but in the experiment, there is a headway threshold to determine whether the potential collision warning happened. If the headway threshold is small, the prediction collision number will less. The duration of each experiment is 100 seconds, and DSRC communication range is 500 meters. We conduct three sets of experiments, for each set of experiments, we change different parameters including scenario, headway and packet loss rate. We can find that performance of proposed system in several scenarios where traffic conditions are different.

In specific, there are predicted collision warning message set ${W_{p}}$ and expected collision warning set ${W_{d}}$ in the experiment. The number of expected warnings $\left|{W_{d}}\right|$ is the number of expected collision warning according to experimental setup, the number of predicted collision warning message $\left|{W_{p}}\right|$ is the number of potential collisions predicted by the collision warning system. Further, $\left|{{W_{d}}\cap{W_{p}}}\right|$ means the number of expected collision warnings which are actual predicted success, in another word, the number of successful predictions. $\left|{{W_{d}}-{W_{p}}}\right|$ is the number of expected warnings which should be triggered but not be predicted successful by collision warning system, in a word, it is failed predictions in ${W_{p}}$. In the same, $\left|{{W_{p}}-{W_{d}}}\right|$ is the number of wrong predictions, namely, it is potential collision predicted by collision warning system, however, it is not expected collision warning. We define precision and recall as follows:

Comparing the superiority of distributed fog computing architecture to centralized cloud computing, we implement the system in both cloud computing and fog computing architecture. To compare the performance of our algorithm, we implement the collision system with three different algorithms as below:

Fig. 6 shows the precision and recall of three algorithms under different experiment scenarios. It is obvious that the trajectories calibration improve the performance in both precision and recall in no matter what traffic conditions. With the benefit of trajectory calibration in the fog node, vehicle status are much closer to the real-time status, in other words, vehicle positions with trajectories calibration are more closer to the real vehicle positions.

Fig. 7 compares the precision and recall of three algorithms with different headway thresholds. Fig. 7 shows the headway threshold increases from 1 to 5 seconds. As the headway threshold increases, precision has improved. Since headway threshold turns large, the number of predicted collisions get larger, in another word, $\left|W\right|$ get bigger. Thus, the precision of proposed system is improved, on the other hand, recall reduces as headway threshold increased.

Fig. 8 compares the precision and recall of three algorithms with different packet loss rates. As shown in Fig. 8, when the packet loss rate increases from 0% up to 6%, performance of CBW and FWC become worse, however, performance of TCCW is better than the two algorithms with the help of trajectory calibration. The experiment result shows that due to the low communication latency supported by fog computing architecture, the performance of FWC is better than CBW. And we can also find that with the help of trajectory calibration, the performance of TCCW is better than both CBW and FWC.