A Novel Rapid-flooding Approach with Real-time Delay Compensation for Wireless Sensor Network Time Synchronization

Synchronization is the typical problem in distributed system, and it still remains a popular topic in smart grid [PDU_Grid], Internet of Things (IoT) [IoT1, IoT2], wireless sensor networks (WSNs) [WSN], networked synchronization control [DisControl2, DisControl4], and so on. Specifically, the time synchronization, which aims to correct the local time information on the distributed nodes and drive a common time notion network-wide, is an essential portion of some WSN/IoT applications, e.g., providing accurate time interval for distributed data acquisition and processing [DataSync, Sleep1], and scheduling [Scheduling]; measuring time delay in industrial wireless feedback control system [SyncCtrl]. However, the large-scale wireless network application imposes exceedingly strict requirements on time synchronization, for instance, they require an accuracy of about $\pm 100$ µs and $\pm 96$ µs in the industrial automation standards ISA100.11a [ISA-100.11a] and WirelessHART [WirelessHART], respectively; about 120 µs for the damage localization in the structural health monitoring [SHM_erro, SHM_S]. Considering WSN is being used in many applications, e.g., industrial automation, monitoring, and is resource-constrained, low-cost, large scale and unreliable connection, therefore its time synchronization problem is representative.

The early researches focused on developing novel synchronization structures, reducing the dependence of the algorithms on the network topology management, and improving the robustness of the algorithms in dynamic networks. As is known to all, due to the requirement of additional protocol to manage the topology of network, the RBS [RBS] and the TPSN [TPSN] are difficult to be deployed in a large-scale complex network, which has large diameter and dynamic topology. Many of the derived algorithms were expected to optimize the implementation complexity, e.g., the clustered-based algorithm [cluster-Conse-sync-1, PulseSS, cluster-Conse-sync-2, cluster-Conse-sync-3] and low-power interested approach in [CESP], the improved two-way message exchange time synchronization approaches in [TSync, Timing-sync, Star-Structure, Elsharief2017DensityTable, R-Sync, Q_TTME, TT_K, TT_W].

In recent years, the flooding time synchronization algorithms [FTSP, FCSA, PulseSync, RMTS] and the consensus-based approaches [ATS2007A, ATS, DCTS, GTSP] are widely studied to meet the accurate synchronization in the large-scale complex WSN. These time synchronization algorithms do not require any topology management, so the problems mentioned above are naturally avoided. Moreover, they are robust and scalable, and can adapt quickly to the changes in network connectivity and clock drifts. However, there are limitations to both of the flooding and the consensus-based methods. In other words, they are different from each other and can be used to meet the time synchronization requirements in different WSNs.

Considering a consensus-based time synchronization algorithm, it is easy to implement and robust in dynamic networks. However, its convergence rate is very slow due to the iteration. For instance, the convergence time is up to 120 rounds of synchronization intervals in ATS ($5\times 7$ grid network) [ATS], and studies in [CCS, EventDriven_ATS, MTS, DiStiNCT, HE2017C, MACTS] are interested in improving the convergence rate. However, It cannot to be synchronized by an external clock or the heterogeneous network [EGsync]. What it matters is not the value of the reference clock but the fact that all clocks converge to one common virtual reference, thus it cannot be synchronized with an external clock or the heterogeneous network [EGsync].

Fortunately, flooding time synchronization algorithm can easily avoid the problems in a consensus-based method. It employs a special node as the reference, meanwhile it distributes the reference’s time information network-wide and aims to synchronize all of the nodes to the reference. A number of line networks are automatically generated while the referenced time information is flooded. Therefore, a complex network is simplified as lines, and the distance of line is the main factor of network to affect the algorithm. The rapid-flooding protocol leads the algorithms to build a stable synchronization after a few synchronization intervals, e.g., about 3 rounds in RMTS ($5\times 5$ grid network) [RMTS]. Moreover, the rapid-flooding is a synchronous method in which the time interval of node transmission can be predicted, thus it is possible and easy to meet synchronous sleep/wake scheduling for low-duty cycle WSN [Chase, Splash]. Hence, the flooding time synchronization algorithm will be a very efficient solution for the time synchronization in the large-scale WSNs.

However, distance of flooding path, flooding latency, packet delay, and clock drift, which cause the unpredictable by-hop error accumulation problem, pose the main challenges to a flooding time synchronization algorithm. Such problems have been significantly improved by the previous studies, and most of the recent studies on flooding time synchronization focus on improving the accuracy, e.g., PulseSync [PulseSync_1, PulseSync], Glossy [glossy], FCSA [FCSA], RMTS [RMTS]. The improvements of flooding time synchronization are simple and effective, i.e., shortening the flooding latency and removing the delay, meanwhile compensating the clock drift. However, there is no better way to calculate packet delay in existing one-way broadcast-based synchronization protocols, but using the prior constant, e.g., the method used in PulseSync and RMTS. Hence, before deploying WSN, a lot of preliminary experiments are required to calculate the prior constant; actual delay may change due to hardware and environment changes.

In this paper, we are interested in a real-time and agile delay estimation to improve the rapid-flooding time synchronization. If the clock skew estimation is fast convergence and independent of the clock offset estimation, meanwhile if a two-way message exchange can be constructed in the one-way-broadcast model, then the real-time delay compensation can be implemented. It is worth mentioning that this strategy has been inspired by the two-way message exchange model based clock offset estimation in [DRJeskeMLE, KLNohMLE, QMChaudhariMLE]. To achieve the objective, the Maximum Likelihood Estimation (MLE) proposed in [MLE] is employed to generate an accurate clock skew estimation at the second round of synchronization; meanwhile an improved two-way message exchange model is constructed on one-way-broadcast model; then a joint clock skew-offset MLE is obtained , and the real-time delay estimation is also given. As a result, a new rapid-flooding multi-broadcast time synchronization with real-time delay compensation (RDC-RMTS) protocol is further developed. The main contributions of this work are as follows.

1) A novel two-way message exchange model is ingeniously designed in the one-way broadcast-based flooding time synchronization, which utilizes redundant broadcasting without any additional packet transmission.

2) The proposed joint clock skew-offset MLE provides the real-time delay estimations and the accurate clock offset estimation, which results in better scalability to RDC-RMTS.

3) An innovate implementation is developed for the RDC-RMTS, in which an adaptive clock offset estimation is designed to guarantee the accurate estimation over unreliable network.

Moreover, the actual performances of flooding time synchronization in a large-scale complex network are discussed. Basically, the performance evaluation indicate that the network mainly affect the time synchronization in a way of increasing the flooding path.

The rest of the paper is organized as follows. In Section II, the challenges to the flooding time synchronization is discussed in detail, and the motivation of this paper is provided. The system model is provided in Section III and the RDC-RMTS is proposed in Section IV. The implementation of RDC-RMTS is described in Section V. The RDC-RMTS is evaluated and discussed in Section VI, where the testbed is provided, and the experimental results in FTSP, FCSA, FloodPISync, PulseSync, PulsePISync, and RMTS are also reported. The discussions and simulations results in complex network are reported in Section VII. Finally, conclusions are drawn in Section VIII.

Flooding time synchronization protocol is easy to implement, and does not require topology management. In addition, flooding operations decompose a complex network into multi-line networks, then the nodes on the line synchronize itself to the reference node (root). However, the time synchronization on a multi-hop node depends on the time information forwarded by relay nodes, thus relay node synchronization error will accumulate on a hop-by-hop basis, i.e., by-hop error accumulation problem [RMTS], which is the major challenge to flooding time synchronization.

A by-hop error accumulation is mainly caused by flooding latency, packet transmission delay, and clock drift. In addition, it is proportional to the distance of reference node and multi-hop node. Definition $E$ is the synchronization error of the node relative to the reference node, then the synchronization error on the $k$-hop node $E[k]$ which is derived in [RMTS], is given by

where $T_{wait}[h]$, which is less than the synchronization interval ($period$), is the flooding latency at the $h$-hop node, and $\varphi_{h}^{h-1}$ is the relative clock rate between $h$-hop and ($h-1$)-hop.Variable $D[h]$ is one-way broadcast packet transmission delay at the $h-$hop node, which comprises variable portion $D_{var}$ and uncertain portion $D_{unc}$ [RMTS]. Moreover, $D_{var}=D_{fixed}+d$, where constant $D_{fixed}$ is the mean of $D_{var}$, and variable $d\sim N(0,\sigma^{2})$ ($\sigma$ is the standard deviation of $D_{var}$). Hence, $D=D_{fixed}+d+D_{unc}$. Because relative clock rate or clock frequency offset is usually described in parts per million (PPM), a multiplier $10^{6}$ is used in (1).

Summaries of the existing flooding time synchronization algorithms are shown in Table I. It should be noted that, according to the [FCSA, PISync], although they don’t seems emphasize the use of $\hat{D}_{fixed}$ to compensate clock offset estimation, we prefer to do this in our experiments to get better experimental results. Moreover, $\hat{D}_{fixed}$ is calculated during the experimental phase based on the previous experimental results, and it is a constant when the algorithm is evaluated.

Lenzen et al. pointed out that, when the referenced time information is flooded network-wide, it will lose accuracy due to clock drift and flooding latency [PulseSync_1]. The PulseSync suggests to distribute time information as fast as possible, and is expected to adapt to fast change in clock drift. Unlike FTSP, which uses slow-flooding, PulseSync uses a rapid-flooding protocol. The Glossy and RMTS are also rapid-flooding approaches.

The FCSA tries to minimize the undesired effect of flood waiting times on the synchronization accuracy by using a clock rate agreement algorithm, and expects to force all nodes to agree on a common clock rate. Even so, the slight estimation error on clock skew estimation may cause serious interference to time synchronization accuracy. Especially, the FCSA use linear regression (LR) to estimate the clock skew, where the $D$ is directly introduced in observations. By using LR, the problem in FCSA also exists in FTSP and PulseSync. The PISync employs a Proportion Integration (PI) control method to optimize the clock skew estimation, however the delays in the observations are not optimized. Unlike that, the MLE in [MLE, RMTS] tries to minimize the delay and could obtain more accurate clock skew estimation than LR and PI method [MLE].

The existing flooding time synchronization algorithms use accurate clock parameter estimation methods and rapid-flooding protocol, and are expected to against the by-hop error accumulation problem. Considering the by-hop error accumulation model in (1), the FCSA tries to minimize $\varphi_{h}^{h-1}$, moreover, the PulseSync and RMTS are also to minimize $T_{wait}$. As discussed in [RMTS], the summary of the synchronization error in flooding time synchronization algorithms is shown in II. It is clear that, the accuracy is significantly improved in the existing flooding time synchronization algorithms.

PulseSync and RMTS use a fixed delay estimation for clock offset estimate compensation that pose challenges to flexible deployment, as it entails that a lot of preliminary experiments need to be completed for the delay estimation. Testbed is needed to collect experimental results and calculate delay estimation, and the estimation cannot be changed after being deployed. Thus, the synchronization accuracy of algorithm may decrease results from the timely changes in delay.

In the light of the above discussion, the main motivation of this paper is to obtain a timely delay estimation, and then propose a new rapid-flooding time synchronization algorithm with real-time delay compensation against the by-hop error accumulation problem.

The WSN is modeled as the graph $\mathcal{G}=(\mathcal{N},\mathcal{E})$, where $\mathcal{N}=\{1,2,\ldots,n\}$ represents the nodes of the WSN and $\mathcal{E}$ defines the available communications links. The set of neighbors for $v_{i}$ is $\mathcal{N}_{i}=\{j|(i,j)\in\mathcal{E},i\neq j\}$, where nodes $v_{i}$ and $v_{j}$ belong to $\mathcal{N}$, and $j\in\mathcal{N}_{i}$. In our work, there are two time notions defined for the time synchronization algorithm, i.e. the hardware clock notion $H(t)$ and logical clock notion $L(t)$. Hardware clock $H(t)$ is defined as

where $H(t)$ is the hardware clock notion. Parameter $h(\tau)$ is the hardware frequency rate (clock speed) of the clock source, meanwhile it is the inherent attribute of crystal oscillator and cannot be changed or measured. Any node considers itself to have the ideal clock frequency (i.e. nominal frequency) and $h(\tau)=1$. Variable $t_{0}$ is the moment that node is powered on, and $\theta(t_{0})$ is the initial relative clock offset. It should be noticed that $H(t)$ cannot be changed either, and the timestamps on $H(t)$ are used to estimate the relative clock speed for the proposed algorithm.

The logical clock $L(t)$ is defined as

where $\varphi(t)$ is the logical relative clock rate and initialized as 1, it can be changed to speed up or slow down $L(t)$. With respect to the reference node, $\varphi(t)$ is always set as 1. The timestamps on $L(t)$ are used to estimate the relative clock offset for the proposed algorithm. Variable $L(t)$ is used to supply the global time service for the synchronization applications.

Considering the arbitrary nodes $v_{i}$ and $v_{j}$, $L_{i}(t)$ and $L_{j}(t)$ are the logical times respectively, and $\varphi_{i}^{j}$ is the relative logical frequency rate which is

where, in consideration of arbitrary moments $t_{1}$ and $t_{2}(t_{1}<t_{2})$, $t_{\Delta}=t_{2}-t_{1}$. The relative clock offset increment in $t_{\Delta}$ is $\theta_{\Delta}=(H_{j}(t_{2})-H_{i}(t_{2}))-(H_{j}(t_{1})-H_{i}(t_{1}))$. Parameter $\varphi_{i}^{j}$ is the changing rate on the relative clock offset in $t_{\Delta}$. It is common estimated by any two clock offset estimations and used to compensate the clock skew in the time synchronization algorithms.

Considering the one-way broadcast based time synchronization protocols, and assuming that the clock skew is fixed in a short time, the key idea of RDC-RMTS is that: the clock skew estimation is independent of clock offset estimation, and convergence fast and accurate, then; an improved two-way message exchange can be structured for the clock offset estimation based on the one-way broadcasts, and the delay can be estimated and compensated timely in the RDC-RMTS.

The proposed RDC-RMTS removes the $D_{fixed}$ from clock offset estimation based on the improved two-way message exchange model without any prior knowledge. It is well known that the two-way message exchange model based synchronization algorithms (e.g. TPSN) calculate the clock offset estimation and delay separately. In this part, we demonstrate an innovative implementation for the two-way message exchange based joint clock skew-offset MLE proposed in (12) and (14).