| Abstract: |
In this paper, we are describing methods to perform time synchronization in a network of nodes that use wireless and ad-hoc communication, are decentralized, and have limited computing
capabilities. Several new results are described. Algorithms: A new synchronization Algorithm (LSA -- Local Selection Algorithms) is presented that achieves low-microsecond precision and jitter,
that is robust under instable connectivity and variable load conditions, and that requires only uni-directional communication. A variant of the algorithm (LSDC) is presented that dynamically
compensates clock drift. Formal Validation: The achievable jitter and precision depend on the synchronization-message arrival-pattern and the synchronization-message delays. We propose a new
analysis of clock synchronization algorithms under unknown pattern and delays, based on safety and liveness properties. LSA and LSDC are safe and live. Experimental Validation: Simulation results
show that LSDC achieves 10microseconds precision on 802.11b wireless LAN in ad-hoc mode under variable load conditions. |
