TY - JOUR
T1 - Fundamental limits on synchronizing clocks over networks
AU - Freris, Nikolaos M.
AU - Graham, Scott R.
AU - Kumar, P. R.
N1 - Funding Information:
Manuscript received December 02, 2008; revised November 20, 2009, May 13, 2010, and October 01, 2010; accepted October 05, 2010. Date of publication October 21, 2010; date of current version June 08, 2011. This work was supported in part by the National Science Foundation under Contracts ECCS-0701604, CNS 05-19535, and CCR-0325716, by Oakridge under DOE BATT 4000044522, by DARPA/AFOSR under Contract F49620-02-1-0325, and by AFOSR under Contract F49620-02-1-0217. Recommended by Associate Editor I. Paschalidis.
PY - 2011/6
Y1 - 2011/6
N2 - We characterize what is feasible concerning clock synchronization in wireline or wireless networks. We consider a network of n nodes, equipped with affine clocks relative to a designated clock that exchange packets subject to link delays. Determining all unknown parameters, i.e., skews and offsets of all the clocks as well as the delays of all the communication links, is impossible. All nodal skews, as well as all round-trip delays between every pair of nodes, can be determined correctly. Also, every transmitting node can predict precisely the time indicated by the receiver's clock at which it receives the packet. However, the vector of unknown link delays and clock offsets can only be determined up to an (n-1)-dimensional subspace, with each degree of freedom corresponding to the offset of one of the (n-1) clocks. Invoking causality, that packets cannot be received before they are transmitted, the uncertainty set can be reduced to a polyhedron. We also investigate structured models for link delays as the sum of a transmitter-dependent delay, a receiver-dependent delay, and a known propagation delay, and identify conditions which permit a unique solution, and conditions under which the number of the residual degrees of freedom is independent of the network size. For receiver-receiver synchronization, where only receipt times are available, but no time-stamping is done by the sender, all nodal skews can still be determined, but delay differences between neighboring communication links with a common sender can only be characterized up to an affine transformation of the (n-1) unknown offsets. Moreover, causality does not help reduce the uncertainty set.
AB - We characterize what is feasible concerning clock synchronization in wireline or wireless networks. We consider a network of n nodes, equipped with affine clocks relative to a designated clock that exchange packets subject to link delays. Determining all unknown parameters, i.e., skews and offsets of all the clocks as well as the delays of all the communication links, is impossible. All nodal skews, as well as all round-trip delays between every pair of nodes, can be determined correctly. Also, every transmitting node can predict precisely the time indicated by the receiver's clock at which it receives the packet. However, the vector of unknown link delays and clock offsets can only be determined up to an (n-1)-dimensional subspace, with each degree of freedom corresponding to the offset of one of the (n-1) clocks. Invoking causality, that packets cannot be received before they are transmitted, the uncertainty set can be reduced to a polyhedron. We also investigate structured models for link delays as the sum of a transmitter-dependent delay, a receiver-dependent delay, and a known propagation delay, and identify conditions which permit a unique solution, and conditions under which the number of the residual degrees of freedom is independent of the network size. For receiver-receiver synchronization, where only receipt times are available, but no time-stamping is done by the sender, all nodal skews can still be determined, but delay differences between neighboring communication links with a common sender can only be characterized up to an affine transformation of the (n-1) unknown offsets. Moreover, causality does not help reduce the uncertainty set.
KW - Clock offsets
KW - clock skews
KW - clock synchronization
KW - delays
KW - networked control
KW - scheduling
KW - sensor networks
UR - http://www.scopus.com/inward/record.url?scp=79958247985&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79958247985&partnerID=8YFLogxK
U2 - 10.1109/TAC.2010.2089210
DO - 10.1109/TAC.2010.2089210
M3 - Article
AN - SCOPUS:79958247985
SN - 0018-9286
VL - 56
SP - 1352
EP - 1364
JO - IEEE Transactions on Automatic Control
JF - IEEE Transactions on Automatic Control
IS - 6
M1 - 5605654
ER -