M.Sc Thesis

M.Sc StudentPinkovich Evgeni
SubjectLinear Programming Algorithms for Pairwise and Network
Clock Synchronization
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Nahum Shimkin
Full Thesis textFull thesis text - English Version


Clock synchronization over a communication network is a crucial issue due to the wide use of networks with simple nodes, such as the Internet, wireless sensor networks and Ad Hoc networks. We present novel algorithms for synchronization of pairs of clocks based on Maximum Margin Estimation of the oset and skew between pairs of clocks. Our algorithms are inspired by the well-known Support Vector Machines (SVM) algorithm from machine learning and have sound geometrical intuition for our model. We derive Mean Square Error bounds and error probability bounds for the oset and skew estimation of our algorithms under exponentially-distributed noise. In addition, we provide two enhancements to these algorithms, which are also applicable to existing synchronization algorithms. The first addresses robustness to measurement outliers. The second allows fusing synchronization measurements from all over the network, providing more accurate all-network synchronization. Simulation experiments demonstrate the improved performance of the suggested algorithms compared to state of the art schemes.