|M.Sc Student||Pinkovich Evgeni|
|Subject||Linear Programming Algorithms for Pairwise and Network|
|Department||Department of Electrical and Computer Engineering||Supervisor||PROF. Nahum Shimkin|
|Full Thesis text|
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 oﬀset 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 oﬀset 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 ﬁrst 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.