# High Velocity Aware Clocks Synchronization Approach in Vehicular Ad Hoc Networks

Khedidja Medani, Makhlouf Aliouat, Zibouda Aliouat

► To cite this version:

Khedidja Medani, Makhlouf Aliouat, Zibouda Aliouat. High Velocity Aware Clocks Synchronization Approach in Vehicular Ad Hoc Networks. 5th International Conference on Computer Science and Its Applications (CIIA), May 2015, Saida, Algeria. pp.479-490, 10.1007/978-3-319-19578-0_39. hal-01789945

HAL Id: hal-01789945

https://inria.hal.science/hal-01789945

Submitted on 11 May 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# High Velocity Aware Clocks Synchronization Approach
in Vehicular Ad Hoc Networks

Khedidja MEDANI¹, Makhlouf ALIOUAT¹, Zibouda ALIOUAT¹

¹Faculty of sciences, Ferhat Abbas University Sétif 1 Algeria.

Khadidja-medani@hotmail.fr

aliouat_m@yahoo.fr

aliouat_zi@yahoo.fr

**Abstract.** Clock synchronization plays an important role in communications organization between applications in Vehicular Ad hoc NETworks (VANETs) requiring a strong need for coordination. Having a global time reference or knowing the value of a physical clock (indeed with an acceptable approximation) of cooperative process involved in the provision of a service by distributed applications, takes on a fundamental importance in decentralized systems, particularly in VANETs. The intrinsic and constraining features of VANETs, especially the high mobility of vehicles make the clock synchronization mechanisms more complex and require a concise and a specific adequacy. The aim of the work reported in this paper is to propose a new protocol for clocks synchronization for VANETs, sufficiently robust, with a good precision, and convenient to the main constraint such high nodes mobility. Our proposed protocol, named Time Table Diffusion (TTD), was simulated using a combination of two simulators: VanetMobiSim and NS2 to evaluate its performance in terms of convergence time and number of messages generated. The obtained results were conclusive.

**Keywords:** VANETs, Clocks synchronization, Intelligent Transportation System, Worthwhile Road Traffic, Time Table Diffusion, TTD

## 1 Introduction

Over the last decade, the use of wireless ad hoc network in transportation domain has drawn particular researchers' attention in order to promote them to a satisfactory rank regarding to the numerous advantages they may provide. So, communications between vehicles (IVC: Inter Vehicular Communications) have becoming one of the most active researching area. This applicative aspect has given a new communication paradigm that ensures to the classical transportation systems more efficiency, security, conviviality, and performances. So this gives rise to the so-called intelligent transportation systems (ITS). Although vehicular ad hoc networks (VANETs) as well as Wireless Sensor Networks (WSNs) are derived from the same source namely Mobile Ad hoc NETwoks (MANETs), the satisfying results obtained from researches and works done in these fields cannot be directly applied in the context of VANETs, be-
cause the specificities of the latter are more stringent in one side and plentiful in the
other. For example, the velocity of nodes in VANETs may reaches extreme values
while energy is abundant and does not represent any constraint. So, the high mobility
environments related to road infrastructure imposes new constraints like radio obsta-
cles, the effects of multipath and fading.

Various common services such as communication, coordination, security, and time
distribution channel access method for time slot (TDMA: Time Division Multiple
Access) depend strongly on the existence of synchronized clocks of different nodes
(vehicles) of a considered VANET network. Thus, clock synchronization requires the
availability of a common time reference for all vehicles, and since these clocks drifted
naturally, it is crucial to realize synchronization with an appropriate period and accu-
racy.

In contrast to other dynamic networks, high mobility of VANETs imposes new re-
quirements in terms of immediate reactivity and high dynamic connectivity. Conse-
quently, the clock synchronization methods used in Ad Hoc networks (MANETs and
WSNs) are not suitable, it is therefore important to adapt them specifically to the con-
text of VANET or proposing new well suited. Few works devoted to the problematic
of clocks synchronization in VANETs were reported in the literature, such as: RBS
[1] CTS [2], TTT [3] and HCS [4].

The aim of the work reported in this paper is to propose a new protocol, for synchro-
nizing node’s clocks in VANETs, independently of the network topology, based on a
decentralized approach, and requiring no use of a Global Positioning System (GPS)
component or an existing infrastructure. The proposed protocol should be able of
providing debrided synchronization where each node moves freely with the time of its
local clock, but stores the needed data to synchronize other nodes. It should also pro-
vide a good precision (of the order of micro seconds), robustness against failure of
nodes, and a low cost in terms of convergence time and number of messages generat-
ed.

This paper is organized as follows: After an introduction of the problematic in Section
I, Section II presents previous work related to clock synchronization in VANETs.
Section III is devoted to the presentation of our proposition (TTD: Time Table Diffu-
sion), while Section IV is dedicated to the exhibition of simulation results of TTD.
We conclude our work with a conclusion and future perspectives.

2 Related Work

Several protocols for clock synchronization in VANETs have been proposed. These
protocols are classified into two approaches (Fig. 1):

2.1 Centralized approach

Among the proposed algorithms in centralized approach include GNSS: Global Syn-
chronization for Satellite Navigation System [5] and Synchronization in ad hoc net-
works based on UTRA TDD [6]. These algorithms have the advantage of implemen-
tation simplicity, but however require the use of a GPS component, which may raise
the problem of transmission signals power which may interfere with communications
in progress within nodes.
## 2.2 Decentralized approach

Decentralized synchronization algorithms are sufficient for inter vehicular communications and better than the centralized ones in terms of fault tolerance. These algorithms are classified into three categories according to the time information exchange mode between vehicles [7] and are as follows:

*   **Burst position measurement:** Each node programs the periodic transmission of a pulse and corrects its own local after receiving the new burst.

*   **Continuous correlation of timing signals:** Each node continuously transmits a signal sequence and calculates the phase offset using the received sequence. Examples of synchronization protocols based on this method are presented in [8] [9].

*   **Clock-sampling methods:** Each node reads its clock time and transmits it explicitly to other neighboring nodes. At each reception, the offsets are calculated as the difference between the local time and the time clocks of neighboring nodes. This method is superior to the other two methods in terms of simplicity, because it directly exchanges time information, without regard to phase. Among the protocols based on this method include those described in [1] [2] [3].

<figure><img src="image_2.png" /><figcaption>Fig. 1. Clock synchronization protocols classification in VANETs.</figcaption></figure>
# 3 Clock Synchronization with Time Table Diffusion Protocol

Our proposition named Time Table Diffusion (TTD) exploits the idea of transferring a time table implemented by the TTT protocol [3] for clock synchronization in mobile sensor networks. The basic idea is to choose a transporter node (T) to transfer a time table containing the offsets related to different nodes. These offsets are calculated by the offset delay estimation method [10]. Transferring time table by the transporter node makes nodes able to calculate their relative clock offsets with the nodes in the time table without even having any message exchanges. Thus, this will offers a great advantage since it contributes to avoid network congestion.

TTD provides synchronization in vehicular environments independent of the network topology in which each node has a unique identity in the network.

TTT protocol uses nodes mobility to transfer time table. The clock offset associated to each node will be kept in the memory of node in a time table, and upon communicating with a new node, the time table would be transferred to the other node. This process provides a long convergence time (in order of seconds) which make a conflict with the real time applications of VANETs (alert messages ...).

To explain the functioning of TTD, synchronization steps are illustrated in Fig. 2.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Synchronization steps in TTD.</figcaption></figure>

The synchronization process begins with broadcasting of a message by the transporter node for collecting information. Neighboring nodes respond to transporter node to construct the time table (Time_table). Once the latter one is built, it should be broadcasted later by the transporter node. We describe these steps in the sequel:

## 3.1 Step 1

In this step, the transporter node broadcasts an advertisement message to initiate the synchronization process and to collect information needed to build the time table. The broadcasting message contains the identity of the transporter node T and $t_0$, the timestamp indicating the sending instant of this message.
Each node begins this step with sending CTS (Clear to Send) messages. The first node sending its CTS becomes the transporter node in its neighborhood.

## 3.2 Step 2

A node i that receiving the advertisement message of the transporter node T marks it at the receiving instant of $t_{1i}$, and then sends a response message to the transporter node T. The response message contains the identity i of the node, and the timestamps $t_0$, $t_{1i}$, and $t_{2i}$ where $t_{2i}$ represent the instant of sending response message. One node i may join more than one transporter node at the same time.

## 3.3 Step 3

When T receives the reply from node i at the instant $t_{3i}$, using timestamps $t_0$, $t_{1i}$, $t_{2i}$, and $t_{3i}$, T can calculate the offset relative to node i ($\Delta_{iT}$) according to the equation (1) below and saves the result in the time table where the index access is the identity of node i.

$$ \Delta_{iT} = ((t_{1i} - t_0) - (t_{3i} - t_{2i}))/2. \qquad (1) $$

Fig. 3 hereafter illustrates the messages exchange between the transporter node T and a node i:

<figure><img src="image_4.png" /><figcaption>Fig. 3. Messages exchange between the transporter node T and a node i.</figcaption></figure>

After T has completed the construction of the time table, it has to broadcast it to all its neighbors' node allowing them to build their own time tables.

## 3.4 Step 4

When a node i receives the time table from a transporter node T, it can build its own table as follows:

Node i will search in the received table the corresponding value to its identity ($\Delta_{iT}$), and stores the inverse of this value in its own table in the location corresponding to the identity of the node T ($time_table(T)=-\Delta_{iT}$). The principle is the following:

$$ \Delta_{iT} = C_i - C_T. \qquad (2) $$

Multiplying both sides of (2) by (-1), we obtain:

$$ \Delta_{Ti} = C_T - C_i. \qquad (3) $$
Where, C_T is the clock value of node T at the instant t, and C_i is the clock value of node i in the same instant t.

To synchronize itself with the rest of the nodes table, node i will add ΔTi value to all values in the table according to the following principle:

$$ \Delta_{jT} = C_j - C_T. \qquad (4) $$

$$ \Delta_{Ti} = C_T - C_i. \qquad (5) $$

By adding the two parts of (4) and (5) we obtain:

$$ \Delta_{jT} + \Delta_{Ti} = (C_j - C_T) + (C_T - C_i) = \Delta_{ji}. \qquad (6) $$

As shown in Fig. 4, depending on the transporter node (that depend on the random number generated by each node), we can find two neighbors not synchronized (node 2 and node 4 participate to the synchronization process under different transporter nodes, that make nodes 2 and 4 two neighbors not synchronized).

<figure><img src="image_5.png" /><figcaption>Fig. 4. Problem posed by the random time</figcaption></figure>

A solution to this problem is that inspired from [8] which consist to larger the range of synchronization packet transmission to be equal double that of data packet transmission. In this way, a transporter node T ensures the synchronization of the nodes joining with all its neighbors (one hop) and in most cases, the synchronization on multi-hop paths.
<figure><img src="image_6.png" /><figcaption>Fig. 5. Improved initial model of the synchronization by TTD.</figcaption></figure>

For mobility management, and since the clocks drifted naturally (the live duration of synchronization is an important evaluation criteria of synchronization’s algorithms), it is crucial to achieve often synchronization process cycles as shown in Fig. 6.

The number of messages necessary to accomplish the synchronization is calculated as follows: Assuming there are $N_i$ nodes within the synchronization scope of a transporter node $T_i$, where $T_i \in T$ (where T is the set of transporter nodes in the current cycle). We can summarize the number and content of messages required for synchronization, as shown in Table I.

According to this table, the number of messages (nbMsg) necessary to accomplish the synchronization can be estimated as follows:

$$nbMsg = \sum_{i=0}^{n_t-1} (N_i+2) \qquad (7)$$

<table><caption>Table 1. Exchange message type and their content.</caption><thead><tr><th>Message</th><th>Number</th><th>Content</th></tr></thead><tbody><tr><td>The avertissement message sent by the transporter node (ADV_T).</td><td>$n_t$, where $n_t$ is the number of transporter nodes in the current cycle.</td><td>Transporetr node identity and the timestamp $t_0$.</td></tr><tr><td>Neighbours reply (JOINseponse).</td><td>$\sum_{i=0}^{n_t-1} N_i$</td><td>Neignbord identity and timestamps $t_0, t_{1i}, t_{2i}$.</td></tr><tr><td>Time table (TIME_TABLE).</td><td>$n_t$</td><td>Time table built by the transporter node</td></tr></tbody></table>
<figure><img src="image_7.png" /><figcaption>Fig. 6. Clock synchronization using TTD.</figcaption></figure>

4 Simulation Results

We simulated the proposed protocol using the combination of the simulator NS2 and the mobility generator VanetMobiSim. Clocks values used in simulation are randomly generated according to the law of GAUSS (0 average, δ = 10 ppm) [11].

We tested a number of scenarios by changing essential parameters to evaluate the
performances of our proposed protocol where nodes are initially placed in random
positions and their movement direction follows the mobility model implemented by
VanetMobiSim in Intelligent Driver Model with Lane Changing (IDM_LC: It regu-
lates vehicle speed based on movements of neighboring vehicles (e.g., if a car in front
brakes, the succeeding vehicles also slows down). The implementation reflects re-
strictions of the spatial environment. Vehicles moving according to the IDM_LC
model support smart intersection management: they slow down and stop at intersec-
tions, or act according to traffic lights, if present. The implementation reflects re-
strictions of the spatial environment. Also, vehicles are able to change lane and perform overtaking in presence of multi-lane roads).

<table><caption>**Table 2.** Simulation Parameters.</caption><tr><td>Topologie (m2)</td><td>1000*1000</td></tr><tr><td>Nodes number</td><td>30/50/100/200/300</td></tr><tr><td>Speed (m/s)</td><td>7/10/15/20/25/30/35</td></tr><tr><td>Trafic light</td><td>6</td></tr><tr><td>Mobility model</td><td>Randomly according to IDM_LC with 2 obstacles every 100 m<sup>2</sup></td></tr><tr><td>Range data transmission (m)</td><td>250/500/1000</td></tr><tr><td>Simulation time (s)</td><td>1000</td></tr></table>

The metrics used to analyze the simulation results are the number of messages generated and the time of convergence (convergence time is the time required to accomplish the synchronization process).

Fig. 7 shows that the convergence time in TTD increases with increasing of nodes number, this is due to the large number of neighbors reply messages. In contrast, nodes speed has no influence on the convergence time because TTD solution uses broadcast (Fig.8). This property is an advantage for the proposed algorithm and makes it usable in different vehicles mobility environments (urban, suburban, and highway).

<figure><img src="image_8.png" /><figcaption>**Fig. 7.** Convergence time Vs nodes number in TTD.</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>Fig. 8. Convergence time Vs nodes speed in TTD.</figcaption></figure>

However, convergence time in TTT [3] increases in urban environments characterized
by a minimal speed compared to other vehicles mobility environments. This is be-
cause the TTT protocol uses node mobility as an essential factor for time table trans-
fer. Thus, the convergence time shown by our protocol is less than that shown by the
reference protocol TTT under the same conditions, as shown in Fig. 9.

<figure><img src="image_10.png" /><figcaption>Fig. 9. Convergence time in TTD Vs Convergence time in TTT</figcaption></figure>
The number of messages required to accomplish the synchronization process is not fixed and depends on two essential factors; nodes number and transporter nodes number (that depends on the transmission range). On one hand, the number of messages increases with a large number of nodes (as shown in Fig. 10); logically this is due to the phase of neighborhood replays, the most consuming phase in the synchronization process in term of messages number.

<figure><img src="image_11.png" /><figcaption>Fig. 10. Messages number Vs nodes number.</figcaption></figure>

On the other hand, depending on the transmission range, that affects the transporter nodes number, the number of messages increases with a the increasing of the number of transporter nodes. For example, in a topology 1000 * 1000 (m²) with a number of nodes equal to 30 (low density network), we can achieve a data transmission range up to 1000 m, in this case, only one transporter node is sufficient to achieve the synchronization process, so we can reach a minimum number of messages that is equal to the nodes number in the network plus one.

## 5 Conclusion

Although clock synchronization in VANETs is a very important research area, few works have been reported so far in the specialized literature. In this paper, we propose a new efficient synchronization protocol taking into account the specific constraints imposed by VANET environments. The proposed solution called TTD (Time Table Diffusion) provides released clock synchronization in a vehicular environment independently of the network topology. TTD achieves synchronization with a good accuracy of the order of a microsecond, and in most cases, synchronization of multi-hop paths. The proposed solution is simulated with the combination of VanetMobiSimNS2 to evaluate its performance in terms of number of messages generated and convergence time. The simulation results showed that TTD provides a best convergence
time compared to its homologues TTT (TTT provide best result than RBS in term of
convergence time).

6 References

1. J. Elson, L. Girod et D. Estrin, "Fine-Grained Network Time Synchronization using Ref-
erece Broadcasts," ACM, vol. 36, pp. 147-163, 2002.

2. W. Shizhun, P. Anjum et N. Maziar, "Converging Time Synchronization Algorithm for Highly Dynamic Vehicular Ad Hoc Networks (VANETs)," IEEE, vol. 6, pp. 443-448, 2010.

3. K. Reza, M. Lim, H. Sim, a. T. Tat Ewe et S. Wei, "Time Table Transfer Time Synchroni-
zation," in Mobile Wireless Sensor Networks, vol. 5, Beijing: PIERS Proceedings, 2009.

4. D. Sam et V. Cyril Raj, " A Time Synchronized Hybrid Vehicular Ad Hoc Network of Roadside Sensors and Vehicles for Safe Driving ", Journal of Computer Science, vol. 11, pp. 1617-1627, 2014.

5. R. Scopigno et H. Cozzetti, "GNSS synchronization in Vanets," IEEE New Technologies, Mobility and Security (NTMS), 2009 3rd International Conference on, vol. 5, n° 11, pp. 1-5, 2009.

6. A. Ebner, H. Rohling, R. Halfmann et M. Lott, "Synchronization in ad hoc networks based on UTRA TDD," Personal, Indoor and Mobile Radio Communications, 2002. The 13th IEEE International Symposium on, vol. 4, 2002.

7. C. H. Rentel, "Network Time Synchronization and Code-based Scheduling for Wireless Ad Hoc Networks," Ottawa, Ontario, Canada: Carleton University, 2006.

8. E. André, R. Hermann, L. Matthias et H. Rüdiger, "Decentralized Slot Synchronization In Highly Dynamic Ad Hoc Networks," IEEE, vol. 2, pp. 494 - 498, 2002.

9. E. Nakagawa et M. Sourour, "Mutual Decentralized Synchronization for Intervehicule Communications," IEEE, vol. 48, n° 16, 1999.

10. D. L. Mills, Internet Time Synchronisation: The Network Time Protocol, vol. 39, IEEE, 1991.

11. M. A. Lombardi, "Frequency Measurement. The Measurement, Instrumentation and Sen-
sors Handbook," CRC Press, 1999.

12. E. André, W. Lars et R. Hermann, "Aspects of Decentralized Time Synchronization in Vehicular Ad hoc Networks," 1st International Workshop on Intelligent Transportation, Hamburg, 2004.