Time synchronization for long-chain-type wireless sensor networks

Abstract

In view of the requirement on time synchronization for a kind of typical wireless sensor networks with long-chain-type topologies, taking into account the three-dimensional network model currently used by the localization algorithms, one feasible time synchronization algorithm is proposed in this article. Under the three-dimensional topology, nodes in the wireless sensor networks are divided into three kinds: the sensing nodes, the relay nodes, and the measured nodes. By analyzing the distribution characteristics of these three kinds of nodes, with the introduction of the pairwise broadcast synchronization and the series multi-hop synchronization protocol, the estimation of the clock offset and the clock skew of all the nodes in the wireless sensor networks are performed by virtue of the joint maximum likelihood and the least-squares method, thus the time synchronization of the wireless sensor networks with long-chain-type topology is solved. Moreover, the sink node evaluates the network periodically and adjusts the synchronizing cycle based on the difference between the network synchronization error and the given synchronization accuracy. The feasibility and effectiveness of this scheme are analyzed by simulations from the synchronization accuracy, the number of synchronization message, and the synchronizing cycle points of view.

Introduction

Nowadays, wireless sensor networks (WSNs) are developed to provide fast, cheap, reliable, and scalable hardware solutions for a large number of industrial applications, ranging from surveillance and tracking to exploration, monitoring, and other sensing tasks. ¹ Sensors can detect, measure, and collect information from various environments. ² The information collected includes a variety of types, such as light, distance, vision, location, acceleration, sound, compass, rotation, magnetic, gravity, atmospheric pressure, temperature, and humidity. In many applications of WSNs, such as duty cycling, data fusion, localization, location-based monitoring, and routing, it is essential that the nodes in a network should act in a coordinated way, which implies all nodes must refer to a common notion of time, ³ that is to say, all the nodes in the network should be synchronized within the range of given synchronization errors. Moreover, the synchronization precision requirement is determined by the WSN’s application type, ⁴ and for the structures’ health monitoring scenario, the synchronization precision is to be around 0.25 ms, while for the location protocols, the precision needs to vary from 0.5 to 0.7 ms.

There is a special application scenario for WSNs: the underground supervision with long-chain-type topologies, ⁵ such as the underground utility tunnel supervision ⁶ and the underground coal mine supervision. ⁷ For this kind of WSNs, the wireless communication environments are supposed to be closed or semi-closed, and the communication channels are supposed to be the fading ones.^8–10 Taking the underground coal mine supervision system as an example, the communication environment in coal mine is becoming more and more complex since the underground pressure, the high-level water pressure, and the coal mine gases are the main threats for the coal mine safety mining.

Since the underground WSNs have many special features, such as the long-chain-type topology, the complex wireless communication environment, and varying time, those traditional time synchronization methods, such as the reference broadcast synchronization (RBS),^11,12 the flooding time synchronization protocol (FTSP),^13,14 the timing-sync protocol for sensor networks (TPSN),^15,16 and the average time-sync (ATS),^17–19 are difficult to meet with the time synchronization requirements and cannot be applied directly to underground WSNs with long-chain-type topologies. The particularities of underground coal mine environment ²⁰ put forward the active and passive time synchronization algorithm; ²¹ arrange all the perception layer nodes, including the sensing nodes and the measured nodes, along the hierarchical network structure; all the nodes acquire their time synchronization packet based on the overhearing mode. By analyzing the characteristics of WSN applications in underground coal mine and the particularities of the working face environment, based on the traditional FTSP time synchronization protocol and with the use of a threshold decision mechanism, ²² we proposed one fault-tolerant time synchronization algorithm.

Considering the characteristics of the coal mine tunnels, motivated by the network topology structure for the three-dimensional (3D) localization model proposed by Meng et al., ²³ in this article, we propose one 3D-localization-based time synchronization method, and it has the following advantages:

1. Based on the currently used 3D model in underground coal mine, the network topology for time synchronization is somewhat easy to maintain, moreover with the use of the global long-term time synchronization for the network is realized in this article;

2. The sender and receiver synchronization (SRS) two-way exchange and the receiver only synchronization (ROS) one-way receive packet transmission mechanism are utilized together to synchronize nodes in the network, where the sensing nodes and the measured nodes in the network are synchronized with the one-way overhearing, thus the total synchronization packet for the WSN is largely decreased, which is more suitable for the scenario in underground WSNs;

3. With the use of network evaluation, we can make a good compromise between the synchronization precision and the energy consumption, thus the energy efficiency of the proposed time synchronization protocol gets somewhat improved.

The article is organized as follows. Section “Time synchronization for long-chain-type WSNs” introduces the time synchronization scheme based on the 3D localization model in coal mine tunnels. Sections “Time synchronization for relay nodes” and “Time synchronization for the sensing nodes and measured nodes” introduce the time synchronization for the relay nodes and the sensing (measured) nodes, respectively. The simulation results and the conclusion remarks are given in sections “Simulations” and “Conclusion,” respectively. The article is based on its previous version; ²⁴ here, the results appear in improved forms along with more discussions.

Time synchronization for long-chain-type WSNs

In this section, based on the typically used 3D localization model, we mainly explain how to carry out our research on the time synchronization for WSNs in tunnels with long-narrow chain-type physical topology.

Network model

From the literature, ⁶ for WSNs in long-narrow chain-type tunnels, the wireless communication paths are narrow and staggered, meanwhile the tunnel’s top is a circular arc, thus those various types of nodes are often arranged in the hierarchical model. The 3D nodes’ arrangement is shown in Figure 1.

Figure 1.

Three-dimensional model of long tunnels nodes’ arrangement.

In Figure 1, nodes arranged in the top of the circular arc are usually used as the relay nodes, which mainly obtain information from the sensing nodes within their communication range, with the use of proper data fusion and then relay those fused information to the sink node in a multi-hope way. When it comes to the sink node, also called the gateway node, it is usually arranged in the entrance of the tunnels and can communicate with the backbone network through the means of wired communication. Moreover, the sensing nodes are arranged in the four oblique vertical angles of the rectangular and are usually used as the detection nodes. As for the measured nodes, they are usually carried by the moving persons, the moving machine, or the moving equipment, thus they are different from those static nodes mentioned above; they are dynamic nodes and their movements may be random. ²⁵

Clock model and time synchronization definition

In the WSNs, assuming that the clock of each node i has one oscillator that can be capable of incrementing a tick counter by one tick. The real period ${\Delta }_i$ of this oscillator is unknown, but the nominal value is known as $\overline{\Delta }$ . The value of node i’s tick counter is denoted by

$$s_i(t)=\lfloor \frac{t-t_0^i}{{\Delta }_i}\rfloor$$

where $t_0^i$ denotes the initial time of node i’s clock. Node i uses this tick counter to estimate the hardware clock time ${\tau }_i(t)$ ²⁶ shown as

$${\tau }_i(t)=\overline{\Delta }{s}_i(t)+{\tau }_i(t_0^i)$$

(1)

where ${\tau }_i(t_0^i)$ is the initial offset which is an estimate of $t_0^i$ . It should be mentioned that, for the oscillator equipped in nodes i, its value ${\Delta }_i$ varies due to the initial manufacturing tolerance, the temperature, the aging, and so on. The following linear equation can be used to describe the relationship between node i’s hardware clock and the reference time t ²⁷

$${\tau }_i(t)=a_i(t)t+b_i(t)$$

(2)

where $a_i(t)$ and $b_i(t)$ indicate the relative clock rate and clock offset of the hardware clock with respect to the reference time t, respectively. Since for nodes in the WSN, the values of $a_i(t)$ and $b_i(t)$ are different from each other, and the WSN cannot keep its time synchronization all the time without using proper time synchronization method.

Note that a hardware clock value ${\tau }_i(t)$ cannot be adjusted manually since other hardware components in the sensor node may depend on the continuous running of this hardware clock. ²⁸ Thus, a virtual clock which is proportional to ${\tau }_i(t)$ is set for each sensor node and the dynamics of each node’s virtual clock is as follows

$$T_i(t)={\hat{a}}_i(t){\tau }_i(t)+{\hat{b}}_i(t)$$

(3)

where ${\hat{a}}_i(t)$ is the relative rate of virtual clock with respect to the hardware clock and ${\hat{b}}_i(t)$ denotes the relative offset between the hardware clock and the virtual clock at time t. The value of $T_i(t)$ therefore can be calculated based on the tick counter reading according to equations (1) and (3)

Substituting equations (1) in (3), one can get

$$\begin{array}{c}{T}_i(t)={\hat{a}}_i(t)a_i(t)t+{\hat{a}}_i(t)b_i(t)+{\hat{b}}_i(t)\hfill \\ \multicolumn{1}{c}{:={\omega }_i(t)t+{\theta }_i(t)}\end{array}$$

(4)

where $T_i(t)$ , ${\omega }_i(t)$ , and ${\theta }_i(t)$ are the virtual local time, virtual clock rate, and virtual clock offset at time t, respectively.

Definition

For a WSN with N nodes and one sink node g, if, for any initial conditions ${\omega }_i(0)$ , ${\theta }_i(0)$ , and $\forall i=1,2,\dots ,N$ , the following are satisfied

$$\begin{array}{c}\underset{t\to \infty }{lim}|{\omega }_i(t)-{\omega }_g(t)|=0\hfill \\ \multicolumn{1}{c}{\underset{t\to \infty }{lim}|{\theta }_i(t)-{\theta }_g(t)|=0}\end{array}$$

(5)

then all the N nodes are synchronized to the sink node g, and the network WSN is said to have achieved its time synchronization.

Chain-type topology construction

In this article, we adopt the typically used 3D long-chain structure to construct the communication topology for time synchronization and utilize both the SRS two-way exchange and the ROS one-way receive packet transmission mechanism; the constructed communication topology for the long-chain-type tunnel is shown in Figure 2. The construction for the long-chain topology for time synchronization consists of the following steps:

1. The sink node, arranged in the entrance of the long-chain-type tunnel, is used as the root node, which is allocated to level 0 and broadcasts a level-discovery packet to its neighbors that contains its identification code and level;

2. When the subsequent relay node receives the node level-discovery packets, it allocates a level for itself which equals 1 plus the smallest one of the level numbers it extracted from all the tunnels’ level-discovery packets;

3. The subsequent relay node broadcasts a level-discovery packet containing this new level, and this process will get performed until the end relay node has obtained its level number and has determined which sink node it belongs to.

Figure 2.

Topology for WSNs in long-chain-type tunnels.

The simplified topology with two communication chains is shown in Figure 3, where $d-1-4$ , $e-2-3$ , and $j-2-5$ are the end relay nodes of the link 1 and 2, which are belonging to sink nodes Sink1 and Sink2, respectively. In the symbol used for each relay node, the first character represents the identification code of itself, the second one indicates the number ID of the link it belongs to, and the last one denotes its level. For example, in order to obtain the minimum number of hops, relay node d selects one of the two links to join, namely, $d-1-4$ or $d-2-4$ , which is ultimately decided by the one that first arrives. During the topology generation stage, a sensing node may receive one or more level-discovery packets from the relay nodes, then it selects the larger level number from the relatively two stronger packets, and then joins the chain topology. Usually, a measured node dynamically selects to join in a relay node who transmits the strongest level-discovery packet to it and allocates a new level which is larger than the one within the packet it received with 1.

Figure 3.

Simplified chain-type network with two sink nodes.

Time synchronization for WSNs

In this article, we utilize the pairwise broadcast synchronization (PBS) method, that is, the two-way exchange and one-way overhear model, to realize the time information exchange among nodes in WSNs, where the information is two-way exchanged between the relay nodes, besides the sink node, and the sensing nodes and the measured nodes overhear those information in a one-way overhearing one. In one synchronization cycle, we exchange N packets between the relay nodes, and the ith synchronization packet exchange is shown in Figure 4, where a and b denote the relay nodes (besides the sink node), while s denotes the sensing node or the measured nodes.

Figure 4.

RSR two-way exchange and the ROS one-way receive synchronization packet transmit model.

In Figure 4, during the ith synchronization packet exchange phase, timestamps $T_{1,i}^{(b)}$ and $T_{4,i}^{(b)}$ are based on the local clock of node b, while timestamps $T_{2,i}^{(a)}$ and $T_{3,i}^{(a)}$ are based on a local clock of node a. Node b delivers one synchronization packet, denoted as SYN, including the level of node b, the identification code, and timestamp $T_{1,i}^{(b)}$ of node b. Node a receives the synchronization packet in $T_{2,i}^{(a)}$ and delivers an acknowledgment packet to node b, denoted as ACK, which contains the level of node a, the identification code, and timestamp $T_{2,i}^{(a)}$ , $T_{3,i}^{(a)}$ . Finally, node b receives the ACK packet sent from node a in $T_{4,i}^{(b)}$ . Moreover, when the two-way information exchange is conformed between nodes a and b, the sensing node s overhears the timestamp information. When node a receives synchronization packet from node b, node s can observe a set of time readings $\{T_{2,i}^{(s)}{\}}_{i=1}^N$ on its own local clock. Furthermore, by receiving the acknowledgment packet from node s, node s can also receive another set of timestamp $\{T_{2,i}^{(a)}{\}}_{i=1}^N$ .

Assuming that the transmission delay between nodes are Gaussian distributed ones, based on the data obtained from information exchange, all nodes in WSNs can adopt the joint maximum likelihood estimation (JMLE) algorithm or the least-squares method to estimate the clock skew and offset among nodes in the network, ²⁹ therefore the time synchronization of the network is achieved.

Time synchronization for relay nodes

In this section, based on the information exchange model shown in Figure 4, we will introduce the synchronization method for the relay nodes, including the following two stages: the single-hop synchronization stage and the multi-hop synchronization stage.

Single-hop synchronization

Assuming that the transmission delay between nodes obeys Gaussian distribution, based on the data obtained from information exchange, in this section, we adopt the JMLE algorithm to estimate the clock skew and offset among nodes in the network. ²⁹

With $T_{1,i}^{(b)}$ as the reference time, the ith uplink timestamp $T_{2,i}^{(a)}$ and down-link one $T_{3,i}^{(a)}$ of node a can be expressed as

$$\begin{array}{c}{T}_{2,i}^{(a)}={\omega }^{(\mathrm{ba})}(T_{1,i}^{(b)}+d^{(b)}+X_i^{(b)})+{\theta }^{(\mathrm{ba})}\hfill \\ \multicolumn{1}{c}{T_{3,i}^{(a)}={\omega }^{(\mathrm{ba})}(T_{4,i}^{(b)}-d^{(b)}-Y_i^{(b)})+{\theta }^{(\mathrm{ba})}}\end{array}$$

(6)

Assuming that $X_i^{(b)}$ and $Y_i^{(b)}$ are all mean independent Gaussian distributed random variables (RVs) with mean µ and variance ${\sigma }^2$ , then the joint probability density functions of $\{X_i^{(b)}{\}}_{i=1}^N$ and $\{Y_i^{(b)}{\}}_{i=1}^N$ are shown as

$$\begin{array}{c}{f}_{X^{(b)},Y^{(b)}}(x,y)=\frac{1}{{(2\pi {\sigma }^2)}^N}\hfill \\ \multicolumn{1}{c}{\times \exp \left\{\frac{\sum _{i=1}^N\{\frac{T_{2,i}^{(a)}-{\theta }^{(\mathrm{ba})}}{{\omega }^{(\mathrm{ba})}}-T_{1,i}^{(b)}-d^{(b)}-\mu \}}{-2{\sigma }^2}\right\}}\\ \multicolumn{1}{c}{\times \exp \left\{\frac{\sum _{i=1}^N\{T_{4,i}^{(b)}-d^{(b)}-\mu -\frac{T_{3,i}^{(a)}-{\theta }^{(\mathrm{ba})}}{{\omega }^{(\mathrm{ba})}}\}}{-2{\sigma }^2}\right\}}\end{array}$$

(7)

When the fixed transmission delay $d^{(b)}$ is known as a constant, the likelihood function based on observations $\{T_{1,i}^{(b)}{\}}_{i=1}^N$ , $\{T_{2,i}^{(a)}{\}}_{i=1}^N$ , $\{T_{3,i}^{(a)}{\}}_{i=1}^N$ , and $\{T_{4,i}^{(b)}{\}}_{i=1}^N$ are as follows

$$\begin{array}{c}L({\theta }^{(\mathrm{ba})},{\omega }^{(\mathrm{ba})},{\sigma }^2)=\frac{1}{{(2\pi {\sigma }^2)}^N}\hfill \\ \multicolumn{1}{c}{\times \exp \left\{\frac{\sum _{i=1}^N\{\frac{T_{2,i}^{(a)}-{\theta }^{(\mathrm{ba})}}{{\omega }^{(\mathrm{ba})}}-(T_{1,i}^{(b)}+d^{(b)})-\mu \}}{-2{\sigma }^2}\right\}}\\ \multicolumn{1}{c}{\times \exp \left\{\frac{\sum _{i=1}^N\{(T_{4,i}^{(b)}-d^{(b)})-\mu +\frac{{\theta }^{(\mathrm{ba})}-T_{3,i}^{(a)}}{{\omega }^{(\mathrm{ba})}}\}}{-2{\sigma }^2}\right\}}\end{array}$$

(8)

From equation (8), the JMLE of the clock offset and skew can be calculated as

$${\hat{\theta }}^{(\mathrm{ba})}=\frac{\sum _{i=1}^N(T_{1,i}^{(b)}+T_{4,i}^{(b)})\sum _{i=1}^N({(T_{2,i}^{(a)})}^2+{(T_{3,i}^{(a)})}^2)-\sum _{i=1}^N(T_{2,i}^{(a)}+T_{3,i}^{(a)})Q}{\sum _{i=1}^N(T_{2,i}^{(a)}+T_{3,i}^{(a)})\sum _{i=1}^N(T_{1,i}^{(b)}+T_{4,i}^{(b)})-2\mathrm{NQ}}$$

(9)

$$\begin{array}{c}{\hat{\omega }}^{(\mathrm{ba})}=\frac{-2N{\hat{\theta }}^{(\mathrm{ba})}}{\sum _{i=1}^N(T_{1,i}^{(b)}+T_{4,i}^{(b)})}+\frac{\sum _{i=1}^N(T_{2,i}^{(a)}+T_{3,i}^{(a)})}{\sum _{i=1}^N(T_{1,i}^{(b)}+T_{4,i}^{(b)})}\hfill \end{array}$$

(10)

where $Q=\sum _{i=1}^N(T_{1,i}^{(b)}{T}_{2,i}^{(a)}+T_{3,i}^{(a)}{T}_{4,i}^{(b)}+(T_{2,i}^{(a)}-T_{3,i}^{(a)})d^{(b)})$ . The value of Q is determined by the fixed transmission delay $d^{(b)}$ , which means that the final values of the clock estimation of ${\hat{\theta }}^{(\mathrm{ba})}$ and ${\hat{\omega }}^{(\mathrm{ba})}$ are somewhat influenced by $d^{(b)}$ .

Multi-hop synchronization

In this section, we continue to explain how to realize the multi-hop synchronization for the relay nodes. Here, we adopt the series multi-hop synchronization algorithm (SMA) to achieve the multi-hop time synchronization of relay nodes, and the synchronization strategy is shown in Figure 5.

Figure 5.

Continuous multi-hop synchronization model.

In Figure 5, node 3 delivers the synchronization packet SYN, containing a time stamp $T_1$ , to node 2, and then node 2 returns an acknowledgment packet ACK to node 3, which contains timestamps $T_1$ , $T_2$ , and $T_3$ . Since node 1 also receives the ACK of node 2, it returns an ACK packet to node 2, which contains the timestamps $T_4$ , $T_5$ , and $T_6$ . At this point, node 1 takes the ACK transmitted from node 2 as synchronization packet delivered by node 2. Similarly, the reference node 0 receives the ACK transmitted from node 1, and then returns an ACK packet to node 1. The above process is repeated N times to increase the estimation accuracy on clock offset for the corresponding node at each level. Finally, node 1 estimates and adjusts its own clock offset and skew, and sends them to node 2, to assist node 2 synchronized to the reference clock, and node 2 and next nodes repeat the above process, so that each node in the network can be synchronized to the reference clock. The above operation can be easily extended to the entire chain network, and the relay node in the end of each link initiates timing synchronization step by step up to the sink node. Through N times of synchronization information exchanges, all relay nodes estimate each clock offset and skew relative to the upper-level node, and then, the upper-level relay node in turn transmits the estimated values of relative clock offset and skew, to assist the lower-level relay node synchronized to the sink node, and ultimately achieves time synchronization of the entire chain network.

From what we have stated above, the clock expression of any relay node to the sink node on a chain link can be expressed as $T_0^H={\hat{\omega }}_{r,0}^{\mathrm{ZH}}{T}_r^Z+{\hat{\theta }}_{r,0}^{\mathrm{ZH}}$ , where 0 denotes the level of sink node, $r=1,2,\dots$ denotes the levels of relay nodes; ${\hat{\omega }}_{r,0}^{\mathrm{ZH}}$ denotes the clock skew of relay node with level r to the sink node, and satisfies ${\hat{\omega }}_{r,0}^{\mathrm{ZH}}={\hat{\omega }}_{r,r-1}^{\mathrm{ZZ}}{\hat{\omega }}_{r-1,0}^{\mathrm{ZH}}(r=2,3,\dots )$ , and here, ${\hat{\omega }}_{r-1,0}^{\mathrm{ZH}}$ denotes the clock skew level $r-1$ relay node to the sink node and ${\hat{\omega }}_{r,r-1}^{\mathrm{ZZ}}$ denotes the clock skew of level r relay node to level $r-1$ relay node; ${\hat{\theta }}_{r,0}^{\mathrm{ZH}}$ denotes the clock offset of level r relay node to the sink node, and satisfies ${\hat{\theta }}_{r,0}^{\mathrm{ZH}}={\hat{\omega }}_{r,0}^{\mathrm{ZH}}{\hat{\theta }}_{r,r-1}^{\mathrm{ZZ}}+{\hat{\theta }}_{r-1,0}^{\mathrm{ZH}}$ , where ${\hat{\theta }}_{r-1,0}^{\mathrm{ZH}}$ denotes clock offset of level $r-1$ relay node to the sink node, and ${\hat{\theta }}_{r,r-1}^{\mathrm{ZZ}}$ denotes clock offset of level r relay node to level $r-1$ relay node.

Time synchronization for the sensing nodes and measured nodes

It has been mentioned before that, the measured nodes are usually objects which are need to be positioned, and select to synchronize or not to the sink node according to actual demands. Therefore, the synchronization method for measured nodes are similar to that of sensing nodes. For the case of brevity, in this section, we will introduce the time synchronization method for both the sensing nodes and measured nodes in the network simultaneously.

Similar as the synchronization method for those relay nodes, here, we also divide the time synchronization into two stages: the single-hop stage and the multi-hope stage.

Single-hop synchronization

In Figure 4, when considering the influence of clock offset and skew simultaneously, in the ith uplink information, the receiving time $T_{2,i}^{(a)}$ of relay node a and $T_{2,i}^{(s)}$ of sensing (measured) node s can be expressed as

$$T_{2,i}^{(a)}=T_{1,i}^{(b)}+{\theta }^{(\mathrm{ba})}+{\omega }^{(\mathrm{ba})}(T_{1,i}^{(b)}-T_{1,i}^{(b)})+d^{(a)}+X_i^{(a)}$$

(11)

and

$$T_{2,i}^{(s)}=T_{1,i}^{(b)}+{\theta }^{(\mathrm{bs})}+{\omega }^{(\mathrm{bs})}(T_{1,i}^{(b)}-T_{1,1}^{(b)})+d^{(s)}+X_i^{(s)}$$

(12)

where ${\theta }^{(\mathrm{ba})}$ , ${\omega }^{(\mathrm{ba})}$ and ${\theta }^{(\mathrm{bs})}$ , and ${\omega }^{(\mathrm{bs})}$ are the clock offset and clock skew between node b, node a and node b, node s, respectively, $d^{(a)}$ , $X_i^{(a)}$ and $d^{(s)}$ , and $X_i^{(s)}$ are the fixed transmission delay from node b to node a and from node b to node s, respectively. Moreover, in this article, we assume that $X_i^{(a)}$ and $X_i^{(s)}$ are Gaussian distributed RVs with mean µ and variance ${\sigma }^2$ .

Subtracting equation (12) from equation (11), we can derive

$$\begin{array}{c}{T}_{2,i}^{(a)}-T_{2,i}^{(s)}={\theta \prime }^{(\mathrm{sa})}+{\omega \prime }^{(\mathrm{sa})}(T_{1,i}^{(b)}-T_{1,1}^{(b)})\hfill \\ \multicolumn{1}{c}{+d^{(a)}-d^{(s)}+X_i^{(a)}-X_i^{(s)}}\end{array}$$

(13)

where ${\theta \prime }^{(\mathrm{sa})}={\theta }^{(\mathrm{ba})}-{\theta }^{(\mathrm{bs})}$ and $\omega {\prime }^{(\mathrm{sa})}={\omega }^{(\mathrm{ba})}-{\omega }^{(\mathrm{bs})}$ .

Let us continue to introduce how to use the linear regression method to estimate the clock offset of sensing (measured) node s with respect to the relay node a. In equation (13), denote $Y_i=T_{2,i}^{(a)}-T_{2,i}^{(s)}-(d^{(a)}-d^{(s)})$ , $T_i=T_{i,1}^{(b)}-T_{1,1}^{(b)}$ , and ${\epsilon }_i=X_i^{(a)}-X_i^{(s)}$ , where $i=1,\dots ,N$ . ε_i is the Gaussian noise variable with zero mean, then all the above observations satisfy the first-order linear regression model

$$y=\theta {\prime }^{(\mathrm{sa})}+\omega {\prime }^{(\mathrm{sa})}t$$

(14)

Utilizing the least-squares method yields

$$\hat{\theta }{\prime }^{(\mathrm{sa})}={\hat{\theta }}^{(\mathrm{ba})}-{\hat{\theta }}^{(\mathrm{bs})}=\frac{\sum _{i=1}^N{T}_i^2\sum _{i=1}^N{Y}_i-\sum _{i=1}^N{T}_i\sum _{i=1}^N[T_i{Y}_i]}{N\sum _{i=1}^N{T}_i^2-{\left[\sum _{i=1}^N{T}_i\right]}^2}$$

(15)

and

$$\hat{\omega }{\prime }^{(\mathrm{sa})}={\hat{\omega }}^{(\mathrm{ba})}-{\hat{\omega }}^{(\mathrm{bs})}=\frac{N\sum _{i=1}^N[T_i{Y}_i]-\sum _{i=1}^N{T}_i\sum _{i=1}^N{Y}_i}{N\sum _{i=1}^N{T}_i^2-{\left[\sum _{i=1}^N{T}_i\right]}^2}$$

(16)

With the above conclusion, the estimation results of the difference between the relative clock offset and skew can be obtained.

Since the relative clock relationship between nodes b and a, and nodes b and node s can be expressed as

$$T^{(a)}={\omega }^{(\mathrm{ba})}{T}^{(b)}+{\theta }^{(\mathrm{ba})}$$

(17)

and

$$T^{(s)}={\omega }^{(\mathrm{bs})}{T}^{(b)}+{\theta }^{(\mathrm{bs})}$$

(18)

the relative clock offset and skew between nodes s and a are in the following form

$$T^{(a)}=\frac{{\omega }^{(\mathrm{ba})}}{{\omega }^{(\mathrm{bs})}}{T}^{(s)}+{\theta }^{(\mathrm{ba})}-\frac{{\omega }^{(\mathrm{ba})}}{{\omega }^{(\mathrm{bs})}}{\theta }^{(\mathrm{bs})}$$

(19)

From equation (19), we can write the clock offset and skew between nodes s and a in the following form

$${\hat{\theta }}^{(\mathrm{sa})}=\frac{{\hat{\theta }}^{(\mathrm{ba})}-{\hat{\omega }}^{(\mathrm{ba})}}{{\hat{\omega }}^{(\mathrm{bs})}·{\hat{\theta }}^{(\mathrm{bs})}}$$

(20)

and

$${\hat{\omega }}^{(\mathrm{sa})}=\frac{{\hat{\omega }}^{(\mathrm{ba})}}{{\hat{\omega }}^{(\mathrm{bs})}}$$

(21)

It should be mentioned that ${\hat{\theta }}^{(\mathrm{bs})}$ and ${\hat{\omega }}^{(\mathrm{bs})}$ are unknown, but with equations (15) and (16), they can be estimated as ${\hat{\theta }}^{(\mathrm{bs})}={\hat{\theta }}^{(\mathrm{ba})}-\hat{\theta }{\prime }^{(\mathrm{sa})}$ and ${\hat{\omega }}^{(\mathrm{bs})}={\hat{\omega }}^{(\mathrm{ba})}-\hat{\omega }{\prime }^{(\mathrm{sa})}$ .

Multi-hop synchronization

It can be seen from Figure 2 that, when the level $r-1$ relay node delivers ${\hat{\theta }}_{r-1,0}^{\mathrm{ZH}}$ and ${\hat{\omega }}_{r-1,0}^{\mathrm{ZH}}$ , the clock offset and clock skew with respect to the sink node, to assist the level r relay node to synchronize with the sink node, all the level r sensing (measured) nodes can overhear ${\hat{\theta }}_{r-1,0}^{\mathrm{ZH}}$ and ${\hat{\omega }}_{r-1,0}^{\mathrm{ZH}}$ . Similarly, when the level r relay node delivers the clock offset ${\hat{\theta }}_{r,0}^{\mathrm{ZH}}$ and skew ${\hat{\omega }}_{r,0}^{\mathrm{ZH}}$ to assist the level $r+1$ relay nodes to synchronize with the sink node, all the level r sensing (measured) nodes can overhear ${\hat{\theta }}_{r,0}^{\mathrm{ZH}}$ and ${\hat{\omega }}_{r,0}^{\mathrm{ZH}}$ . Hence, the level r sensing (measured) nodes can estimate the clock offset and clock skew between level r relay node and level $r-1$ node as follows

$${\hat{\theta }}_{r,0}^{\mathrm{ZH}}={\hat{\omega }}_{r-1,0}^{\mathrm{ZH}}{\hat{\theta }}_{r,r-1}^{\mathrm{ZZ}}+{\hat{\theta }}_{r-1,0}^{\mathrm{ZH}}$$

(22)

and

$${\hat{\omega }}_{r,0}^{\mathrm{ZH}}={\hat{\omega }}_{r-1,0}^{\mathrm{ZH}}{\hat{\omega }}_{r,r-1}^{\mathrm{ZZ}}$$

(23)

where $r=2,3,\dots$ refer to equations (15) and (16), and denoting ${\hat{\theta }}_{r,r}{\prime }^{\mathrm{GZ}}$ and ${\hat{\omega }}_{r,r}{\prime }^{\mathrm{GZ}}$ as the estimations of the level r sensing (measured) node, we can deduce the clock offset and skew of the level r sensing (measured) node to the level r relay node, which can be expressed as

$${\hat{\theta }}_{r,r}^{\mathrm{GZ}}={\hat{\theta }}_{r,r-1}^{\mathrm{ZZ}}-{\hat{\theta }}_{r,r}{\prime }^{\mathrm{GZ}}$$

(24)

and

$${\hat{\omega }}_{r,r}^{\mathrm{GZ}}={\hat{\omega }}_{r,r-1}^{\mathrm{ZZ}}-{\hat{\omega }}_{r,r}{\prime }^{\mathrm{GZ}}$$

(25)

Referring to equation (19), we can also deduce the general expression about the clock offset and clock skew between level r sensing (measured) node and level $r-1$ relay node as

$${\hat{\theta }}_{r,r-1}^{\mathrm{GZ}}=\frac{{\hat{\theta }}_{r,r-1}^{\mathrm{ZZ}}-{\hat{\omega }}_{r,r-1}^{\mathrm{ZZ}}}{{\hat{\omega }}_{r,r}^{\mathrm{GZ}}·{\hat{\theta }}_{r,r}^{\mathrm{GZ}}}$$

(26)

$${\hat{\omega }}_{r,r-1}^{\mathrm{GZ}}=\frac{{\hat{\omega }}_{r,r-1}^{\mathrm{ZZ}}}{{\hat{\omega }}_{r,r}^{\mathrm{GZ}}}$$

(27)

Therefore, the clock offset and clock skew between the level r sensing (measured) node and the sink node are shown as

$${\hat{\theta }}_{r,0}^G={\hat{\omega }}_{r-1,0}^Z{\hat{\theta }}_{r,r-1}^{\mathrm{GZ}}+{\hat{\theta }}_{r-1,0}^Z$$

(28)

and

$${\hat{\omega }}_{r,0}^G={\hat{\omega }}_{r-1,0}^Z{\hat{\omega }}_{r,r-1}^{\mathrm{GZ}}$$

(29)

Thus, the synchronization between the sensing (measured) nodes and the sink node has been finished.

Network evaluation

When designing the time synchronization algorithm for WSNs, there are many important factors to be considered, such as the synchronization precision and the energy consumption, which may compromise with each other. For nodes in WSNs, in many contexts, it is hard to recharge the batteries or scavenge energy from the environment, so when designing the time synchronization parameters, such as the synchronization period τ, the number of synchronization packets N transmitted during one period and so on, one of the most crucial factors to be considered is the energy consumption; ³⁰ the smaller the τ, the lower the synchronization error, but more the energy consumption. The accuracy of the time synchronization to large extent is determined by the synchronization period. For example, according to Elson et al., ¹¹ assuming that the upper limit of the clock synchronization accuracy is 10 ms, and in the most crucial case, the synchronization error is 50 µs, together with the clock skew is 4.75 ppm, then the maximum synchronization period can be calculated as

$$\begin{array}{c}\multicolumn{1}{c}{{\tau }_{max}=\frac{10\times {10}^{-3}-50\times {10}^{-6}}{4.75\times {10}^{-6}}\mathrm{s}}\\ =2094.7\mathrm{s}\hfill \\ =34.9min\hfill \end{array}$$

In this article, we propose one easy way to realize the method which is to regulate the synchronization period τ according to the synchronization error e(t) performed by the sink node during the network evaluation phase. For level i, define the synchronization error with respect to the sink node g

$$e_i(t)=\frac{\sum _k{e}_{\mathrm{ik}}(t)-\underset{e_{\mathrm{ik}}}{max}(t)-\underset{e_{\mathrm{ik}}}{min}(t)}{N_i}$$

(30)

where $e_{\mathrm{ik}}(t)$ is the synchronization error of sensing (measured) node k with respect to the sink node g defined as follows

$$e_{\mathrm{ik}}(t)=T_{\mathrm{ik}}(t)-T_g(t)=({\omega }_{\mathrm{ik}}-{\omega }_g)t+{\phi }_{\mathrm{ik}}-{\phi }_g$$

(31)

and $N_i$ is the number of nodes in chain i, including the sensing nodes and the measured nodes. Therefore, for the whole WSN, the synchronization error e(t) is defined as

$$e(t)=\sum _i\frac{e_i(t)}{r}$$

(32)

where r is the maximum level of the considered network and is determined during the topology construction phase.

The network evaluation is launched by the sink node g, and the evaluation is performed as follows:

1. When the sink node g wants to evaluate the network, all the nodes b in Figure 4 embed one special symbol to the SYN packet;

2. All the nodes s in Figure 4 acquire this symbol from the SYN packet, and after they have estimated the clock skew and clock offset, they send these two estimations to the relay node at the same level;

3. The relay node at the level obtains the synchronization error of sensing (measured) node to the sink node (which means the reference time) according to equation (31), then calculates the average synchronization error of this level based on equation (30), and delivers this average error to the sink node with the aid of all the top level relay nodes;

4. The sink node g receives all the $e_i(t)(i=1,2,\dots ,r)$ and calculates the synchronization error e(t) according to equation (31), and then dynamically adjusts the synchronization period τ as follows

$$\tau =\{\begin{array}{cc}\frac{E_{max}}{e(t)}\tau \hfill & e(t)\ge 1.05E_{max}\hfill \\ \multicolumn{1}{c}{\frac{e(t)}{E_{max}}\tau }& e(t)\le 0.95E_{max}\hfill \\ \multicolumn{1}{c}{\tau }& \mathrm{otherwise}\hfill \end{array}$$

(33)

so as not to only meet with the clock synchronization accuracy requirements $E_{max}$ but also to reduce the energy consumption for time synchronization.

Simulations

In this section, we will illustrate the proposed time synchronization method for WSNs via some numerical simulations. All the figures and table are drawn from the results of the average over 1000 runs with the randomized initial conditions.

We set the simulation parameters, such as the mean and the variance of the Gaussian distribution RVs, based on Table 1 in the literature, ¹⁵ and set them as follows: the random delay is set to Gaussian distribution with the mean 2.5 µs and variance 1 µs, and the fixed delay is d = 1 µs.

Table 1.

Statistics of synchronization error (only magnitude).

	TPSN	RBS
Average error (µs)	16.9	29.13
Worst case error (µs)	44	93
Best case error (µs)	0	0
Percentage of time error is less than or equal to average error	64	53

TPSN: timing-sync protocol for sensor networks; RBS: reference broadcast synchronization.

According to the features of long-chain-type tunnel, during the simulation, we denote the height and width of the tunnel both to be 6 m, then the topology of a tunnel with 100-m length is shown in Figure 6, with 1 sink node, 5 relay nodes, and 27 sensing (measured) nodes, the communication ranges between the sink node and the relay node is 21 m, and the range between the sensing node and the measured node is 12 m.

Figure 6.

Network simulation topology.

Effectiveness of the proposed algorithm

In this section, we will show the effectiveness of the proposed time synchronization method for the relay and sensing nodes. It should be mentioned that TPSN method has not estimated the clock skews between nodes and it is a short-time synchronization method. The comparisons on the mean square errors (MSEs) of the clock offset and the skew estimation with respect to the synchronization packet number N among the relay nodes, the sensing nodes in this article, and the errors of the TPSN method proposed in Ganeriwal et al. ¹⁵ are shown in Figure 7(a) and (b), respectively, where the MSEs of the clock offset and the skew estimation are defined as $\sqrt{\frac{1}{N}{({\omega }_i(t)-{\omega }_g(t))}^2}$ and $\sqrt{\frac{1}{N}{({\theta }_i(t)-{\theta }_g(t))}^2}$ , respectively.

Figure 7.

Mean square error curves of the clock estimations: (a) offset estimation (MSE) and (b) skew estimation (MSE).

It can be seen from Figure 7 that:

1. With the increase in synchronization packet number N, the MSEs of the clock offset and skew estimations of relay and sensing nodes of this article all showed decreasing trends, which means that the more the value of N, the closer their estimation values to the actual clock offset and skew;

2. The convergence speed of the estimation MSE curves for the relay nodes and sensing nodes is different, since they use different methods to estimate the clock skews and offsets, and the speed of the pairwise synchronization SRS mechanism adopted by relay nodes is faster than that of the overhearing ROS mechanism adopted by the sensing nodes.

Comparisons on $N_{\mathrm{um}}$

Denote the synchronization packet number in one period as N, and the total packet number for the WSN as $N_{\mathrm{um}}$ . For the protocol proposed in this article, $N_{\mathrm{um}}$ contains the N times two-way packet exchange between the sink node and the 5 relay nodes, together with the synchronization error packet broadcasted by the 32 nodes, that is to say for this article, $N_{\mathrm{um}}=6\times N+32$ . As for the TPSN protocol proposed in Ganeriwal et al., ¹⁵ the two-way packet exchange needs to be done among all the nodes, thus $N_{\mathrm{um}}=33\times 2N$ . When it comes to the RBS protocol proposed in Elson et al., ¹¹ assume that the network shown in Figure 6 is divided into 5 clusters, then the packet needed contains the following: the one-way packet broadcasted by the 5 head nodes, the two-way packet exchange done by the left 27 nodes, and the wo-way packet exchange done by the 5 head nodes and the sink node, thus $N_{\mathrm{um}}=5N+54N+10N=69N$ . The relationship between $N_{\mathrm{um}}$ and N for the three mentioned time synchronization protocol is shown in Figure 8.

Figure 8.

Comparisons on $N_{\mathrm{um}}$ .

It can be seen from Figure 8 that, for the long-chain-type topology in underground WSNs, the protocol proposed by this article deserves the least synchronization overhead and can save most of the energy, thus it is more suitable for the underground WSNs.

Network evaluation

We first set the synchronization accuracy as 1 ms and run the protocol for 100 cycles, then change the accuracy to 0.1 ms and run the protocol for another 100 cycles, where the simulation time is 22513.5 s and the network is evaluated by the sink node every 10 cycles. The curves for synchronization error and the synchronizing cycle are shown in Figure 9.

Figure 9.

Curves for synchronizing cycle τ adaption and the synchronization error e.

It can be seen from Figure 9 that (1) the synchronization error can change with the change in $E_{max}$ and can maintain in the stable region of $E_{max}$ ; (2) when the error zone Δ is defined as $0.95E_{max}-1.05E_{max}$ , the synchronizing cycle gets decreased when the $e(t)\ge 1.05E_{max}$ , and the cycle gets increased when the $e(t)<0.95E_{max}$ , and the cycle remains unchanged when the e(t) is in the error zone Δ.

Conclusion

Aimed at the requirement of time synchronization for one long-chain-type WSNs in underground coal mines, taking advantage of the currently used 3D localization model in the tunnels, one feasible time synchronization scheme is proposed in this article and its effectiveness is verified by simulations. The time synchronization is solved with the joint use of SRS and ROS packet transmission mechanism, thus the number of synchronization packet gets greatly decreased, which means that the energy efficiency gets improved. The estimation of clock skew and clock offset relative to the sink node is carried out by virtue of the joint maximum likelihood and the least-squares method, thus the global time synchronization of the WSN is realized. During the network evaluation phase, the synchronizing cycle in the whole network is adjusted according to the difference between the accuracy requirement and the realtime synchronization error, so that the energy consumption gets further reduced. Therefore, the proposed protocol can make a good compromise between the synchronization precision and the energy consumption.

As a preliminary study, this article just describes the general process of the adaptive adjustment of the entire network and has not analyzed it systematically, which is the main task for our future works. We will verify the effectiveness of the proposed method in the hardware sensor nodes.