MTSF: A Timing Synchronization Protocol to Support Synchronous Operations in Multihop Wireless Networks
Jungmin So, Nitin H. Vaidya · 2004
Abstract — In this paper, we propose a protocol for synchro-nizing time in multihop wireless networks. Protocols for power management or dynamic channel assignment often require syn-chronous operations, such as waking up at the same time or listen-ing to a common channel. Having the nodes synchronized in time is often crucial for these protocols to work. However, the exist-ing synchronization mechanisms do not work well with these pro-tocols because either they may fail to synchronize the time even without transient failures or packet loss, or they may require a large overhead. The proposed synchronization protocol, called MTSF (Multihop Timing Synchronization Function), successfully synchronizes time in a multihop network, at a low cost. In the absence of packet loss, MTSF guarantees an upper bound on the clock error between any two pair of nodes in the network. More-over, MTSF can tolerate packet losses to some extent and its per-formance degrades gracefully when the loss rate becomes high. The cost of MTSF increases very slowly as the number of nodes increase, which makes the protocol highly scalable. MTSF is fully distributed, and operates without a central coordinator. Finally, MTSF is self-stabilizing, which means that starting from an arbi-trary state, the protocol converges to a steady state. Due to these features, MTSF can support protocols that require synchronous operations at a low cost. I.