M.Sc Thesis

M.Sc StudentCohen Maxime
SubjectNetwork Time Synchronization Using Decentralized Kalman
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Nahum Shimkin
Full Thesis textFull thesis text - English Version


   Accurate clock synchronization is important in many distributed applications, both in wire line and wireless computer networks. Time synchronization between the nodes of a network was extensively treated in the literature, where several methods and algorithms were proposed to solve this problem efficiently. In the Internet for example, the “Network Time Protocol” (NTP) is the most widely accepted standard for clock synchronization.

In some recent work, improved algorithms that rely on Least-Squares estimation were introduced. The accuracy of clock synchronization was improved by imposing the global constraints for all the loops in the multihop network and the use of a distributed algorithm employing only local broadcasts. A central characteristic of these methods is their decentralized structure that requires only local communication with neighbors. In this research, we will extend the Least-Squares framework by developing algorithms that estimate the offset of the local clock at each network node, using a Kalman Filter framework. We will present a synchronous decentralized implementation of the filtering algorithm that employs only local broadcasts and we will prove that it converges to the optimal centralized solution. The Kalman Filter framework allows exploiting some a-priori knowledge and providing different weights to the measurements according to their accuracy. The next step is to consider the multiple measurement case and to present a recursive version of these algorithms. The recursive algorithm computes the optimal offsets and the corresponding variances after receiving each set of measurements in a decentralized manner. Finally, we will extend the results to the estimation of the clock skew (i.e., rate deviation) in addition to its offset. Then, we will consider different extensions of the basic algorithm. We will incorporate a discount factor in the objective function and treat the case where temporary communication failures are considered.

We also present simulation results over several network topologies for evaluating and comparing the accuracy of the proposed time synchronization schemes. We will provide several interesting comparisons and as expected, the Kalman Filter approach outperforms the existing algorithms.