New timestamp mark–based energy efficient time synchronization method for wireless sensor networks

Abstract

Aimed at the demands of wireless sensor networks for high energy-efficient time synchronization, the reduction of synchronization energy consumption is studied from the aspects of both accurate timestamps marking and synchronous information transmission mechanism. First, the network is divided into several parent–child groups periodically. The group-wise pair selection algorithm is used to select the network’s pairwise synchronization nodes, and chain-type network topology is thus generated. Second, the sequential multi-hop synchronization algorithm is introduced to realize the synchronization information exchange among pairwise synchronization nodes. The overhearing synchronization (OS) nodes obtain the synchronization information packet based on a one-way overhearing mechanism. Moreover, the accurate acquisition of the synchronization ack packet’s timestamp is carried out through the use of receiving-time-plus-fixed-delay mode. Third, the joint maximum likelihood method and the minimum variance unbiased estimation method are used to estimate the clock offsets of pairwise synchronization nodes and overhearing nodes to the parent nodes, respectively, based on which the child nodes adjust their local virtual clocks. Periodically, the pairwise synchronization nodes initiate the network’s time synchronization, estimate, and broadcast the relative offset to the gateway node, assisting the upper layer child nodes in synchronizing to the gateway node. Simulation results show that the proposed method not only achieves the millisecond level synchronization accuracy but also reduces the synchronization energy consumption and thus improves the network lifetime.

Introduction

Wireless sensor networks (WSNs) are composed of many self-organizing sensor nodes, which realize the interconnection between the physical world and the information world. It has been widely studied and applied in intelligent transportation, ¹ intelligent manufacturing, ² energy Internet of things,^3,4 and other fields. Many important applications in WSNs—such as data fusion, transmission scheduling based on time-division multiple access (TDMA), and energy management—require different sensor nodes to work under a unified time baseline. Time synchronization is a fundamental support technology for WSNs.^5–9 Due to the battery-powered characteristics of WSNs, energy efficiency is a virtual factor to be considered when designing corresponding time synchronization protocols. ¹⁰

In WSNs, the energy consumed by sensor nodes for communication (sending, receiving, and so on) is much larger than that consumed for computing, ¹¹ and the information exchange mode can significantly influence the energy consumed for time synchronization. Based on the information exchange mechanisms of time synchronization protocols, the existing hierarchical time synchronization schemes can be classified into the following three types: sender–receiver synchronization (SRS), receiver-only synchronization (ROS), and receiver–receiver synchronization (RRS). SRS relies on the traditional model of two-way message exchange between a pair of nodes. For example, both network time protocol (NTP) ¹² and time-sync protocol for sensor networks (TPSN) ¹³ rely on a series of heap synchronization that assumes two-way deterministic message exchanges. ROS is designed to minimize the number of timed messages and energy consumption required during synchronization while maintaining a high level of accuracy. ¹⁴ RRS is a method of synchronizing a set of child nodes that receive beacon information from a common transmitting node. Reference broadcast synchronization (RBS) ¹⁵ relies mainly on RRS because it requires message exchange pairs between child nodes to compensate for their relative clock offset. Pairwise broadcast synchronization (PBS) protocol is based on SRS of two-way synchronization message exchange between node pairs. ¹⁶ Inactive nodes located in the common communication domain of pair nodes can realize the clock synchronization with reference nodes by monitoring the two-way synchronization information exchange between pair nodes, which greatly reduces the node energy consumption. Therefore, PBS protocol is more suitable for WSN’s time synchronization with a limited power supply.

Moreover, it was pointed out in Freris et al. ¹⁷ that the transmission delay of synchronous information is a fundamental challenge to time synchronization, which directly makes it impossible for clocks between nodes to be synchronized. The time synchronization between nodes in WSNs essentially estimates the transmission delay. By recording multiple timestamps at both the sender and the receiver, the flooding time synchronization protocol (FTSP) method can effectively reduce the timestamp jitter of interrupt handling time and encoding/decoding time. ¹⁸ Timestamp-free synchronization method is a new mechanism that has attracted much attention in recent years.^19–24 It was pointed out in Etzlinger et al. ²⁰ that timestamp-free clock synchronization in a master–slave network, that is, synchronization where no timestamps were exchanged between the nodes, was considered. For the timestamp-free method, the synchronization process neither builds a special synchronous message nor requires any timestamp information interaction. In Etzlinger et al., ²¹ one following response mode was proposed to realize the timestamp-free synchronization protocols. The relative clock skew was estimated by sending back one ack packet and one following ack packet at two preset intervals. Wang et al. ²² proposed one dynamic response mode, and the dynamic response packet time interval was used to eliminate the dependence on the following packet. Combined with signal processing technologies, such as maximum likelihood estimation and linear unbiased estimation, the relative clock skew and clock offset were further estimated through multiple packet interactions between nodes.^21,22 In Wang et al., ²³ one hybrid synchronization scheme that uses one-way message dissemination and emerging timestamp-free synchronization was developed for WSNs without additional communication overhead. Under the Gaussian delay model, the maximum likelihood estimator for the joint estimation of clock offset, skew, and the fixed delay was derived, as well as corresponding Cramer–Rao lower bounds. Huan et al. ²⁴ proposed an asymmetric timestamp-free time synchronization scheme with two estimation methods tailored for resource-constrained WSNs. Since no timestamp information is exchanged among nodes, the timestamp-free synchronization mechanism reduces communication energy and bandwidth consumption. It also avoids potential malicious attacks on the timestamp information, improving the security of the time synchronization mechanism.

Considering the limited energy supply in WSNs, in this article, we extend the timestamp free for node level to the network level and propose one energy-efficient network-level time synchronization algorithm. First, the synchronization energy consumption reduction is studied using the timestamp marking method and the synchronization information exchange mechanism. Then, a new sequential multi-hop synchronization algorithm (SMA) based on the new timestamp mark method is proposed. The main contributions of this article are listed as follows: (1) during the two-way time information exchange between pairwise synchronization (PS) nodes, the receiving-time-plus-fixed-delay mode is introduced, and a new ack packet timestamp processing mechanism is proposed; in this way, the packaging process of the current sending time’s timestamp is avoided, and thus the uncertainty of transmission delay is reduced and (2) a global network time synchronization mechanism based on SMA and PBS is proposed; thus, the information exchange between OS nodes and parent nodes is avoided, while the amount of information exchange among PS nodes gets decreased, and the energy efficiency of the time synchronization method is thus improved.

The rest of this article is organized as follows. The WSN clock model and the network topology generation method are presented in section “Time synchronization scheme.” Section “Time synchronization between parent and child nodes” discusses the information transmission model between parent–child nodes, clock offset estimation, and clock information adjustment. Section “Network multi-hop time synchronization” describes the network time synchronization method. Finally, section “Simulation results and analysis” provides the numerical simulation results and analysis of the proposed time synchronization method, and section “Conclusion” concludes this study.

Time synchronization scheme

Clock model of nodes

The first-order time model for a node $i$ in the network can be specified as

$${\tau }_i(t)={\overline{\omega }}_{i}t+{\overline{\phi }}_i$$

(1)

where ${\overline{\omega }}_i$ and ${\overline{\phi }}_i$ are the clock skew and clock offset of the node $i$ , respectively. The value of ${\overline{\omega }}_i$ can be affected by node crystal accuracy, ambient temperature, pressure, supply voltage, and other factors. While ${\overline{\phi }}_i$ is affected by the node’s initial power-on time.

Note that ${\tau }_i(t)$ cannot be manually modified as other applications of the node, such as the periodic sampling and clock interruption of the operating system, should be performed according to the continuous timing of the local time ${\tau }_i(t)$ . During the time synchronization of network $G$ , a virtual clock $T_i(t)$ is set for each node $i$ in the network. ²⁵ There is a functional relationship between the virtual time $T_i(t)$ and the local time ${\tau }_i(t)$ , shown as

$$T_i(t)=f({\tau }_i(t))={\omega }_{i}t+{\phi }_i$$

(2)

Definition 1 (Network time synchronization)

For a WSN network G with $\kappa$ nodes, through the synchronization packet exchange between nodes, if $\underset{t\to \infty }{lim}(T_i(t)-T_j(t))=0$ holds true for $\forall i,j=1,2,\dots ,\kappa$ , then the time synchronization of network $G$ is realized; furthermore, if $\underset{t\to \infty }{lim}({\omega }_i-{\omega }_j)=0$ holds true for $\forall i,j=1,2,\dots ,\kappa$ , then the long-term time synchronization of network $G$ is realized; still further, if $\underset{t\to \infty }{lim}{\omega }_i=1$ holds, the synchronization of network $G$ to the external standard Coordinated Universal Time (UTC) time is realized.

Generation of chain-type network topology

Based on the communication between nodes in the network at the perception layer and the principle of the fewest parent–child groups, the whole network is divided into several parent–child groups starting from the gateway node, and appropriate PS nodes are selected for each parent–child group. Two-way time synchronization packets are exchanged between parent nodes (including the sink node) and PS nodes. Other nodes in the group overhear the time synchronization packets (recorded as OS nodes) to realize the time synchronization to their parent nodes.

The generation of chain-type network topology includes two steps: network spanning tree generation stage and group-wise pair selection algorithm (GPA)-based PS vector generation stage. Figure 1 shows an example of the GPA-based chain-type network topology. In Figure 1, there are four layers and five parent–child groups with layer number $l=0,1,2,3$ , and the node at layer $0$ is the gateway node.

Figure 1.

Example of chain-type network topology.

During the network spanning tree generation stage, the gateway node $1$ periodically broadcasts the lever-discovery packet (with its own layer number and ID number). All its single-hop neighboring nodes allocate their layers to be $1$ plus the layer variable in the received packet and mark the sink node as their parent node. Nodes $2$ and $3$ at layer $1$ broadcast the lever-discovery packet. This procedure proceeds until all nodes in the network have obtained their layer number. In the GPA-based PS vector generation stage, for the nth parent–child group, when the child node $k$ broadcasts the lever-discovery packet, if other child nodes $n$ in that group can receive this packet, they send back the ack packet to node $k$ . Then, node $k$ marks the connectivity among nodes as $M_{k,n}=1$ ; otherwise, it marks $M_{k,n}=0$ . The number of nodes that simultaneously connect to the parent node $i$ and child $k$ is denoted as $N_{\mathrm{ROS}}^{i,k}=\sum _{k\ne n}{M}_{k,n}$ . Nodes with the largest connectivity in that group are denoted as $\hat{k}=\arg \underset{k}{max}{N}_{\mathrm{ROS}}^{k,n}$ , and a PS pair of the nth parent–child group is recorded as $p[n]=p_{i,\hat{k}}$ . For a network with $15$ nodes shown in Figure 1, the PS vector based on GPA is calculated as $\mathit{p}=\{p_{1,3},p_{2,5},p_{3,8},p_{5,11},p_{8,14}\}$ .

Remark 1

During the time synchronization process, the apoptosis or weakening of nodes will affect the network’s communication topology. In some cases, the topology may be a disconnected one. Therefore, the network topology should be regenerated periodically to avoid the influence of apoptosis or the weakening of nodes on the time synchronization performance.

Time synchronization between parent and child nodes

In this section, we mainly introduce how to implement a network’s time synchronization method in a new timestamp-marked way, including the SMA-based time synchronization model, the timestamp processing method, the relative clock, and skew offset estimation, together with the adjustment of the node’s virtual clock.

Time synchronization information transfer model

To reduce the total amount of synchronization information transmitted in the WSNs, and improve the energy effectiveness of the time synchronization method, one continuous multi-hop time synchronization model and the overhearing-based synchronous message transmission mode are adopted in this article. The fundamental idea of SMA is that the upper and lower nodes can simultaneously receive the time information sent by the current node. While the overhearing node makes use of the overhearing mechanism of wireless communication. When the synchronization information is exchanged between two nodes, the information can be overheard by the nodes within their common communication range.

Information transmission model and timestamp process

Figure 2 illustrates the SMA-based information transmission strategy for a network with $\mathrm{four}$ layers, where all nodes are PS nodes. In Figure 3, denote nodes at layer $l(l=1,2,\dots )$ as the child nodes of nodes in layer $l-1$ , and those at the $l-1$ layer as the parent of nodes at layer $l$ . First, terminal PS nodes in the chain-type topology initialize the time synchronization. Then, other PS nodes two-way exchange synchronization packets with their parent nodes after receiving the initialization packet. Meanwhile, the OS nodes in the network acquire the syn packet, and the child nodes in each parent–child group complete the clock offset estimation relative to the parent nodes after $N$ rounds of packet transmission.

Figure 2.

Information transmission model for time synchronization.

Figure 3.

Overhearing-based synchronization packet exchange process.

In the SMA transmission, as shown in Figure 2, the PS child nodes at the third layer send a syn packet containing synchronization request to the parent nodes at the second layer, and the OS nodes in the third layer within the same parent group overhear those syn packets. After receiving the syn packets, the parent nodes at the second layer return an ack packet to the OS nodes in the third layer, which will be overheard by the OS nodes in the same parent–child group. As the PS nodes at the first layer also accept the ack from the second layer, it will also return an ack packet to the second layer. Meanwhile, the nodes at the first layer take the ack from the second layer as its synchronization requests packet syn. Similarly, nodes at the layer $0$ , the sink node, accept the ack from the first layer and return an ack packet. The above process will repeat $N$ times until $N$ rounds of packet transmission of the whole network are completed.

As shown in Figure 2, when a node at layer $l-1(l=1,2,\dots )$ sends an ack packet, its timestamp when it sends this packet should be packed into this ack packet, which puts high requirements on the accurate acquisition of this timestamp. Motivated by Wang et al., ²² in this article, we introduce a receiving-time-plus-fixed-delay mode to solve the timestamp problem of the sending time of the ack packet. A global time interval $\mathrm{\Delta }$ is set for the whole network. After receiving the syn packet from the upper layer, the node at layer $l-1$ will record the receiving time, pack this time into the ack packet, and send this ack packet back after a fixed delay $\mathrm{\Delta }$ . For this reason, the ack packet only needs to contain the receiving time of nodes at the second layer. Thus, the relationship between the time information in Figure 2 is listed as below

$$\{\begin{array}{c}{T}_{3,k}=T_{2,k}+\mathrm{\Delta }\hfill \\ \multicolumn{1}{c}{T_{6,k}=T_{5,k}+\mathrm{\Delta },k=1,\dots ,N}\\ \multicolumn{1}{c}{T_{9,k}=T_{8,k}+\mathrm{\Delta }}\end{array}$$

It should be pointed out that although $\mathrm{\Delta }$ is a global variable, its time length is measured according to the individual clock of each node.

Synchronous information transmission model

First, the two-way exchange information transmission process between the terminal PS node and its parent node is presented. Under the designed information timestamp method, the PS node periodically initiates the time synchronization process and the information exchange process between the terminal PS node (denoted as $i$ ) and its parent node (denoted as $j$ ) is shown in Figure 3.

The kth information change between the terminal PS node $i$ and its parent node $j$ contains following steps: (1) Node $i$ initiates the synchronization request at the local time $T_{1,k}(k=1,\dots ,N)$ , and sends the syn packet to node $j$ (including its ID), (2) Node $j$ receives the syn packet at the local time $T_{2,k}$ and sends back the ack packet (including its ID and its local time $T_{2,k}$ ) at local time $T_{3,k}=T_{2,k}+\mathrm{\Delta }$ , and (3) Node $i$ receives the ack packet at timestamp $T_{4,k}$ . In this way, after $N$ times of information exchange, the child node $i$ obtains the exact timestamp $T_{3,k}$ as per $T_{2,k}+\mathrm{\Delta }$ , and stores $\{T_{1,k},T_{2,k},T_{3,k},T_{4,k}\}{|}_{k=1}^N$ . Let the synchronization period of the terminal PS node be $T_{\mathrm{sync}}$ . Assume that the PS node and its parent node two-way exchange packets $N$ times in a synchronization period, then the period of the terminal node sending syn packets is $T_{\mathrm{\Delta }}=T_{\mathrm{sync}}/N$ .

As for the synchronization information exchange of other PS nodes in the network, set the maximum number of network layers as $L$ . As the SMA information transmission strategy shown in Figure 2, the time synchronization between the PS nodes and their parent nodes at layer $l(l=1,2,\dots L-1)$ is initiated by the PS nodes at the previous layer. For example, the time synchronization of nodes at the second layer is activated by PS nodes at the third layer. Similarly, the synchronization of nodes at the first layer is activated by PS nodes at the second layer. During the information transmission of nodes at layer $l(l=1,2,\dots ,L-1)$ , the packets needed are the acks of the nodes at the previous layer, including the IDs and their $T_{2,k}$ ; their acks are the acks from nodes at the next layer, including the IDs and their $T_{2,k}$ .

All the OS nodes in the network acquire their synchronization information packets based on the overhearing mode. As shown in Figure 3, in the kth two-way information exchange between PS child node $i$ and its parent node $j$ , the child node $m$ within their communication range overhears the synchronization packets sent by $i$ and $j$ under the one-way overhearing mode. The OS node $m$ receives the syn packet at time $T_{2,k}^m$ , and the ack packet at $T_{2,k}$ sent by node $j$ . After $N$ times of information overhearing, the OS node $m$ at layer $l(l=1,2,\dots L-1)$ stores the corresponding time information $\{T_{1,k},T_{2,k},T_{2,k}^m{\}}_{k=1}^N$ , while those at layer $L$ stores the time information $\{T_{2,k},T_{2,k}^m{\}}_{k=1}^N$ .

Clock offset estimation for two-way information exchange nodes

Taking the PS child node $i$ and the parent node $j$ as an example, this section describes the bidirectional information exchange synchronization process between parent and child nodes. The local virtual time of nodes $i$ and $j$ is

$$T_i(t)={\omega }_{i}t+{\phi }_i,T_j(t)={\omega }_{j}t+{\phi }_j$$

(3)

where ${\omega }_i,{\phi }_i$ and ${\omega }_j,{\phi }_j$ are, respectively, the time rate and initial clock offset of nodes $i$ and $j$ . Let the relationship between the two nodes be

$$T_j(t)={\omega }^{\mathrm{ij}}{T}_i(t)+{\phi }^{\mathrm{ij}}$$

(4)

where ${\omega }^{\mathrm{ij}}={\omega }^j/{\omega }^i$ and ${\phi }^{\mathrm{ij}}={\phi }^j-{\omega }^{\mathrm{ij}}{\phi }^i$ are, respectively, the relative clock skew and phase clock offset of nodes $i$ and $j$ . Thus, $T_{2,k}$ and $T_{3,k}$ can be written as

$$\{\begin{array}{c}{T}_{2,k}={\omega }^{\mathrm{ij}}(T_{1,k}+d+X_k^{\mathrm{ij}})+{\phi }^{\mathrm{ij}}\hfill \\ \multicolumn{1}{c}{T_{3,k}={\omega }^{\mathrm{ij}}(T_{4,k}-d+X_k^{\mathrm{ji}})+{\phi }^{\mathrm{ij}}}\end{array}$$

(5)

where $d$ is the fixed transmission delay; $X_k^{\mathrm{ij}}$ and $X_k^{\mathrm{ji}}$ are the random transmission delay from node $i$ to node $j$ and that from node $j$ to node i, respectively. Besides, one has $T_{3,k}=T_{2,k}+\mathrm{\Delta }$ . Also, delay $d$ , $X_k^{\mathrm{ij}}$ , and $X_k^{\mathrm{ji}}$ are all expressed at the clock of node $i$ .

In this article, we assume that $X_k^{\mathrm{AB}}$ and $X_k^{\mathrm{BA}}$ are independent identically distributed random numbers that follow the normal distribution $N(\mu ,{\sigma }^2)$ with mean $\mu$ and variance ${\sigma }^2$ . Let $T_{2,k}-{\phi }^{\mathrm{ij}}/{\omega }^{\mathrm{ij}}$ and $T_{3,k}-{\phi }^{\mathrm{ij}}/{\omega }^{\mathrm{ij}}$ be $T{\prime }_{2,k}$ and $T{\prime }_{3,k}$ , respectively. Then, the joint probability density function of $\{X_k^{\mathrm{AB}}{\}}_{k=1}^N$ and $\{X_k^{\mathrm{BA}}{\}}_{k=1}^N$ is

$$\begin{array}{l}{f}_{X^{ij},X^{ji}}(x,y)\\ =\frac{1}{{(2\pi {\sigma }^2)}^N}\times {\exp }^{-\frac{1}{2{\sigma }^2}\sum _{i=1}^N\left({\left({T^{\prime }}_{2,k}-T_{1,k}-d-u\right)}^2+{\left(T_{4,k}-d-{T^{\prime }}_{3,k}-u\right)}^2\right)}\end{array}$$

Assume that the fixed delay $d$ is a constant value, then the likelihood function based on the observed quantity $\{T_{1,k},T_{2,k},T_{3,k},T_{4,k}\}{|}_{k=1}^N$ will be

$$\begin{array}{l}L({\phi }^{ij},{\omega }^{ij},{\sigma }^2)\\ =\frac{1}{{(2\pi {\sigma }^2)}^N}{\exp }^{-\frac{1}{2{\sigma }^2}\sum _{i=1}^N\left({\left({T^{\prime }}_{2,k}-(T_{1,k}+d)-u\right)}^2+{\left(T_{4,k}-d-{T^{\prime }}_{3,k}-u\right)}^2\right)}\end{array}$$

(6)

According to the likelihood function formula (6), the joint maximum likelihood estimation of ${\phi }^{\mathrm{ij}}$ and ${\omega }^{\mathrm{ij}}$ can be obtained as below after some calculations

$$\begin{array}{c}{\hat{\phi }}^{\mathrm{ij}}=\hfill \\ \multicolumn{1}{c}{\frac{\sum _{k=1}^N(T_{1,k}+T_{4,k})\sum _{k=1}^N({(T_{2,k})}^2+{(T_{3,k})}^2)-\sum _{k=1}^N(T_{2,k}+T_{3,k})Q}{\sum _{k=1}^N(T_{2,k}+T_{3,k})\sum _{k=1}^N(T_{1,k}+T_{4,k})-2\mathrm{NQ}}}\\ \multicolumn{1}{c}{-\frac{\sum _{k=1}^N(T_{2,k}+T_{3,k})Q}{\sum _{k=1}^N(T_{2,k}+T_{3,k})\sum _{k=1}^N(T_{1,k}+T_{4,k})-2\mathrm{NQ}}}\end{array}$$

(7)

and

$$\begin{array}{c}{\hat{\omega }}^{\mathrm{ij}}=\frac{-2N\left[\sum _{k=1}^N(T_{1,k}+T_{4,k})\sum _{k=1}^N({\left(T_{2,k}\right)}^2+{\left(T_{3,k}\right)}^2)\right]}{(M-2\mathrm{NQ})\sum _{k=1}^N(T_{1,k}+T_{4,k})}\hfill \\ \multicolumn{1}{c}{+\frac{2N\sum _{k=1}^N(T_{2,k}+T_{3,k})Q}{(M-2\mathrm{NQ})\sum _{k=1}^N(T_{1,k}+T_{4,k})}}\\ \multicolumn{1}{c}{+\frac{\sum _{k=1}^N(T_{2,k}+T_{3,k})}{\sum _{k=1}^N(T_{1,k}+T_{4,k})}}\end{array}$$

(8)

where $Q\stackrel{\mathrm{\Delta }}{=}\sum _{k=1}^N[(T_{1,k}{T}_{2,k}+T_{3,k}{T}_{4,k}+(T_{2,k}-T_{3,k})d]$ , $T_{3,k}=T_{2,k}+\mathrm{\Delta }$ , and $M\stackrel{\mathrm{\Delta }}{=}\sum _{k=1}^N(T_{2,k}+T_{3,k})\sum _{k=1}^N(T_{1,k}+T_{4,k})$ . After $N$ times of synchronous packet exchange, the node will estimate the clock offset relative to the parent node according to equations (7) and (8), and adjust the clock according to $T_i(t)={\hat{\omega }}^{\mathrm{ij}}{T}_i(t)+{\hat{\phi }}^{\mathrm{ij}}$ .

Clock offset estimation for one-way overhearing nodes

This section focuses on how the OS node in Figure 1 is synchronized to its parent node. Based on equation (3), the time relationship between the local time of the node $m$ and the PS node $i$ is written as follows

$$T_m(t)={\omega }_{m}t+{\phi }_m,T_m(t)={\omega }^{\mathrm{im}}{T}_i(t)+{\phi }^{\mathrm{im}}$$

(9)

where ${\omega }^{\mathrm{im}}={\omega }^m/{\omega }^i$ and ${\phi }^{\mathrm{im}}={\phi }^m-{\omega }^{\mathrm{im}}{\phi }^i$ are the relative clock skew and clock offset of the node $i$ to the node $m$ , respectively. Thus, for OS node $m$ at the kth group exchange, one has

$$T_{2,k}=T_{1,k}+{\phi }^{\mathrm{ij}}+({\omega }^{\mathrm{ij}}-1)(T_{1,k}-T_{1,1})+d^{\mathrm{ij}}+X_k^{\mathrm{ij}}$$

(10)

$$T_{2,k}^m=T_{1,k}+{\phi }^{\mathrm{mi}}+({\omega }^{\mathrm{mi}}-1)(T_{1,k}-T_{1,1})+d^{\mathrm{im}}+X_k^{\mathrm{im}}$$

(11)

By combining equations (10) and (11), one can get

$$T_{2,k}-T_{2,k}^m={\phi }_1^{\mathrm{mj}}+{\omega }_1^{\mathrm{mj}}(T_{1,k}-T_{1,1})+d^{\mathrm{ij}}-d^{\mathrm{im}}+X_k^{\mathrm{ij}}-X_k^{\mathrm{im}}$$

(12)

where the relative clock offset and clock skew satisfy ${\phi }_1^{\mathrm{mj}}={\phi }^{\mathrm{ij}}-{\phi }^{\mathrm{mi}}$ and ${\omega }_1^{\mathrm{mj}}={\omega }^{\mathrm{ij}}-{\omega }^{\mathrm{mi}}$ , $d^{\mathrm{ij}}$ and $d^{\mathrm{im}}$ are the fixed transmission delays, and $X_k^{\mathrm{ij}}$ and $X_k^{\mathrm{jm}}$ are the random transmission delays.

In this article, we assume that the values of $d^{\mathrm{ij}},d^{\mathrm{im}}$ are constant while those of delays $X_k^{\mathrm{ij}}$ and $X_k^{\mathrm{jm}}$ are random variables following the Gaussian distribution. Define that $z(k)=d^{\mathrm{ij}}-d^{\mathrm{im}}+X_k^{\mathrm{ij}}-X_k^{\mathrm{im}}=\mu \prime +X_k^{\mathrm{ij}}-X_k^{\mathrm{im}}$ , $w(k)=z(k)-\mu \prime$ , and $x(k)=T_{2,k}-T_{2,k}^m-\mu \prime$ , where $\mu \prime =d^{\mathrm{ij}}-d^{\mathrm{im}}$ . Then, motivated by Mills, ¹² we can get the matrix format of equation (12) as

$$\begin{array}{c}\mathit{x}=\left[\begin{array}{c}x(1)\hfill \\ \multicolumn{1}{c}{x(2)}\\ \multicolumn{1}{c}{\cdots }\\ \multicolumn{1}{c}{x(N)}\end{array}\right]=\left[\begin{array}{cc}1\hfill & 0\hfill \\ \multicolumn{1}{c}{1}& T_{1,2}-T_{1,1}\hfill \\ \multicolumn{1}{c}{\cdots }& \cdots \hfill \\ \multicolumn{1}{c}{1}& T_{1,N}-T_{1,1}\hfill \end{array}\right]\left[\begin{array}{c}{\phi }^{\mathrm{mj}}\hfill \\ \multicolumn{1}{c}{{\omega }^{\mathrm{mj}}}\end{array}\right]+\left[\begin{array}{c}w(1)\hfill \\ \multicolumn{1}{c}{w(2)}\\ \multicolumn{1}{c}{\cdots }\\ \multicolumn{1}{c}{w(N)}\end{array}\right]\hfill \\ \multicolumn{1}{c}{={\mathit{H}}^T\mathbf{\theta }+\mathit{w}}\end{array}$$

where

$$\begin{array}{c}{\mathit{H}}^T=\left[\begin{array}{cc}1\hfill & 0\hfill \\ \multicolumn{1}{c}{1}& T_{1,2}-T_{1,1}\hfill \\ \multicolumn{1}{c}{\cdots }& \cdots \hfill \\ \multicolumn{1}{c}{1}& T_{1,N}-T_{1,1}\hfill \end{array}\right],\mathbf{\theta }=[{\phi }_1^{\mathrm{mj}},{\omega }_1^{\mathrm{mj}}{]}^T\hfill \\ \mathit{w}=[w_1,\cdots ,w_N{]}^T\hfill \end{array}$$

According to Theorem 3.2 in Kay Steven ²⁶ if $\mathit{g}(\mathit{x})$ satisfies $\partial \ln p(\mathit{x},\mathbf{\theta })/\partial \mathbf{\theta }=\mathit{I}(\mathbf{\theta })(\mathit{g}(\mathit{x})-\mathbf{\theta })$ , then the minimum variance unbiased estimation of $\mathbf{\theta }$ is $\hat{\mathbf{\theta }}=\mathit{g}(\mathit{x})=({\mathit{H}}^T\mathit{H}{)}^{-1}{\mathit{H}}^T\mathit{x}$ , where $\mathit{I}(\mathbf{\theta })$ is the Fisher information matrix. With some manipulations, the joint maximum likelihood estimation of ${\phi }_1^{\mathrm{mj}}$ and ${\omega }_1^{\mathrm{mj}}$ can be obtained as

$${\hat{\phi }}_1^{\mathrm{mj}}=\frac{\sum _{k=1}^N{D}_k^2\sum _{k=1}^{N}x(k)-\sum _{k=1}^N{D}_k\sum _{k=1}^N[D_{k}x(k)]}{N\sum _{k=1}^N{D}_k^2-{\left(\sum _{k=1}^N{D}_k\right)}^2}$$

(13)

and

$${\hat{\omega }}_1^{\mathrm{mj}}=\frac{N\sum _{k=1}^N[D_{k}x(k)]-\sum _{k=1}^N{D}_k\sum _{k=1}^{N}x(k)}{N\sum _{k=1}^N{D}_k^2-{\left(\sum _{k=1}^N{D}_k\right)}^2}$$

(14)

where $D_k\stackrel{\mathrm{\Delta }}{=}{T}_{1,k}-T_{1,1}$ .

Let $T_j(t)={\omega }^{\mathrm{mj}}{T}_m(t)+{\phi }^{\mathrm{mj}}$ . From equations (3) and (9), one has $T_j(t)={\omega }^{\mathrm{ij}}/{\omega }^{\mathrm{im}}(T_m(t)-{\phi }^{\mathrm{im}})+{\phi }^{\mathrm{ij}}$ . Then, the estimation of relative clock skew and clock offset of the node $m$ to the parent node $j$ can be

$${\hat{\omega }}^{\mathrm{mj}}=\frac{{\hat{\omega }}^{\mathrm{ij}}}{{\hat{\omega }}^{\mathrm{im}}},{\hat{\phi }}^{\mathrm{mj}}={\hat{\phi }}^{\mathrm{ij}}-\frac{{\hat{\omega }}^{\mathrm{ij}}}{{\hat{\omega }}^{\mathrm{im}}}{\hat{\phi }}^{\mathrm{im}}$$

(15)

where ${\hat{\omega }}^{\mathrm{im}},{\hat{\phi }}^{\mathrm{im}}$ can be calculated from ${\hat{\phi }}^{\mathrm{mi}}={\hat{\phi }}^{\mathrm{ij}}-{\hat{\phi }}_1^{\mathrm{mj}}$ and ${\hat{\omega }}^{\mathrm{mi}}={\hat{\omega }}^{\mathrm{ij}}-{\hat{\omega }}_1^{\mathrm{mj}}$ , respectively. After $N$ times of synchronization packet exchange, according to equations (13), (14), and (15), node $m$ can estimate the clock offset relative to its parent node $j$ ; then, it adjusts the clock as $T_m(t)={\hat{\omega }}^{\mathrm{mj}}{T}_m(t)+{\hat{\phi }}^{\mathrm{mj}}$ to synchronize to its parent node $j$ .

It should be pointed out that, in equations (13) and (14), $D_k$ is the time difference between the syn packets sent at the kth time and the first time from the PS nodes that is within the same parent–child group as node $m$ , and its value is to be determined. The maximum number of the network layers is denoted as $L$ . For the OS nodes at the layers lower than layer $L$ , their syn information packets are essentially the ack information packets of the previous layer in which there is local information when the nodes at the previous layer send the ack packets. For example, as shown in Figure 2, one has $T_{3,k}=T_{2,k}+\mathrm{\Delta },T_{6,k}=T_{5,k}+\mathrm{\Delta },\cdots$ . Thus, $D_k$ can be directly calculated as $D_k=T_{1,k}-T_{1,1}$ . For the OS nodes at the layer $L$ , as the syn packets in their parent and child groups do not contain the value of the node sending time, the value of $T_{1,k}(k=1,\dots ,N)$ cannot be obtained directly. However, the time synchronization of the entire network is initiated by the PS child node at the end of the chain, and the synchronization period is denoted as $T_{\mathrm{sync}}$ . Then, the time length for the PS node in the same parent–child group to periodically send syn packets will be $T_{\mathrm{sync}}/N$ , which is counted according to the clock frequency of the PS node. Thus, for the OS nodes at the layer $L$ , the value of $D_k$ can be determined by $D_k=k{T}_{\mathrm{sync}}/N$ .

Network multi-hop time synchronization

Based on the time synchronization between the parent and child nodes, we will continue with how to achieve time synchronization at the network level in this section.

Network synchronization process

The time synchronization at the network level can be summarized in the following three steps:

• Step 1. The PS node at the end of each link initiates synchronization periodically according to the synchronization period $T_{\mathrm{sync}}$ , and performs the two-way time synchronization information exchange with the parent node in the SMA mode step by step, until the synchronization information is transmitted to the sink node.

• Step 2. After, respectively, $N$ rounds of synchronization information exchange and overhearing, with the stored synchronization information $\{T_{1,k},T_{2,k},T_{3,k},T_{4,k}\}{|}_{k=1}^N$ and $\{T_{1,k},T_{2,k},T_{2,k}^m{\}}_{k=1}^N$ , all the PS and OS nodes estimate their own clock offsets and clock skews to their parent nodes at the previous layer according to equations (7)−(8) and equations (13)−(15), respectively.

• Step 3. Time synchronization at the network level is carried out periodically. Starting from the first layer, the PS node sends the estimated relative clock offset and clock skew to the parent nodes at the previous layer, assisting the child nodes at the previous layer to be synchronized to the sink node. This process continues until all nodes at the $L$ layer are synchronized to the sink node.

With some manipulations, the clock expression of the nodes at any layer $l(l=1,\cdots ,L)$ to the sink node at layer 0 can be expressed as

$$T_0(t)={\omega }_{l,0}{T}_l(t)+{\phi }_{l,0}$$

(16)

where ${\omega }_{l,0}$ and ${\phi }_{l,0}$ are the relative clock skew and clock offset of the relay nodes at the layer $l$ to the sink node, respectively. Let ${\omega }_{l,l-1}$ and ${\phi }_{l,l-1}$ be the relative clock skew and clock offset of the nodes at the layer $l$ to those at the layer $l-1$ , respectively. Then, we can get

$$\{\begin{array}{c}{\omega }_{l,0}={\omega }_{l-1,0}+{\omega }_{l,l-1}\hfill \\ \multicolumn{1}{c}{{\phi }_{l,0}={\phi }_{l-1,0}{\phi }_{l,l-1}+{\phi }_{l-1,0}}\end{array}$$

(17)

In this case, when nodes at layer $l-1$ send the clock offset ${\phi }_{l-1,0}$ and the clock skew ${\omega }_{l-1,0}$ relative to the sink node to their parent nodes, they can assist the relay nodes at layer $L$ to synchronize to the sink node. The nodes at the layer $l$ (including the PS and OS nodes) will overhear and receive ${\phi }_{l-1,0}$ and ${\omega }_{l-1,0}$ . According to equation (16), the clock offset ${\omega }_{l,0}$ and ${\phi }_{l,0}$ relative to the sink node can be calculated and the adjustment of virtual clock can be carried out as $T_l(t)={\omega }_{l,0}{T}_l(t)+{\phi }_{l,0}$ .

Network estimation stage

After finishing the time synchronization phase, the terminal node at each end of the chain network obtains the maximum clock and skew offset related to the sink node (reference time). Then, to meet the clock synchronization accuracy $\epsilon$ requirement, those terminal nodes adjust the synchronization period $T_{\mathrm{sync}}$ and the synchronization information exchange time $N$ . For example, as assumed in Elson et al., ¹⁵ the upper limit of clock synchronization accuracy is 10 ms, the worst synchronization error is 50 µs, and the worst clock skew is 4.75 µs/s. Then, the maximum time synchronization period can be calculated out from $10\mathrm{ms}=50\mathrm{\mu }\mathrm{s}+4.75\mathrm{\mu }\mathrm{s}/\mathrm{s}\times T_{\mathrm{sync}}$ , and the $T_{\mathrm{sync}}=35min$ .

Simulation results and analysis

The effectiveness of the proposed time synchronization method is verified on the MATLAB platform.

Simulation parameter setting

In simulating the network communication topology in a narrow space environment, 30 nodes (one of which is a sink node) are randomly arranged in a rectangular area, and the communication radius of the nodes is set to 25 m. If the distance between two nodes is less than 25 m, the two nodes are neighbor nodes. On the premise that the network contains at least one spanning tree, the initial topology of the generated network is shown in Figure 4(a), where the sink node is located at (0,3), and the big black solid point represents the sink node and the solid blue line represents the communication between nodes.

Figure 4.

Network communication topology. (a) Initial topology and (b) GPA-selected topology.

The sink node provides the reference clock for the entire network with the clock skew set as 1, and the clock offset set as $0$ . The initial clock skew ${\omega }_i(i=1,\dots 29)$ and offset ${\phi }_i(i=1,\dots 29)$ of other $29$ nodes are randomly selected within $[0.99,1.01]$ and $[-1,1]\mathrm{s}$ . The packet sending period of the terminal PS node at the end of the link is $T_{\mathrm{\Delta }}=0.1\mathrm{s}$ , $\mathrm{\Delta }=1\mathrm{ms}$ , and $d=1\mathrm{ms},{\sigma }^2=1\mathrm{ms}$ . The maximum number of synchronization information exchanges in a synchronization period is set to $N_{\max }=50$ . All figures are plotted as the average of $1000$ runs. The primary parameter settings are shown in Table 1.

Table 1.

Parameters’ settings.

Parameters	Setting
Number of nodes $\kappa$	$30$
Communication radius	$25\mathrm{m}$
${\omega }_i(i=1,\dots ,29)$	$[0.99,1.01]$
${\phi }_i(i=1,\dots ,29)$	$[-1,1](\mathrm{s})$
Fixed delay $d$	$1\mathrm{ms}$
Variance of random delay	$1\mathrm{ms}$
$N_{\max }$	$50$
$T_{\mathrm{\Delta }}$	$0.1\mathrm{s}$
$\mathrm{\Delta }$	$1\mathrm{ms}$

PS node selection

GPA algorithm is run on the initial network topology shown in Figure 4(a) to select PS nodes, and the network topology constructed is shown in Figure 4(b). In Figure 4(b), solid red circles represent the parent nodes (including the sink node), solid green circles represent the PS nodes, and solid black ones represent the OS nodes. The red outer ring with a green filling represents the node that is not only the PS node in the previous group but also the parent node in the next group. The blue dotted thin lines represent the group’s communication between PS nodes and OS nodes; the red dotted lines represent the communication between parent nodes and OS nodes; while the blue dotted thick lines represent the communication between parent nodes and PS nodes in a group. By comparing Figure 4(a) and (b), it can be seen that the number of nodes that need bidirectional exchange in the network is only 3 through the selection of PS node pairs, which can significantly reduce the synchronization information transmitted in the network.

Synchronization error analysis

First, the synchronization error simulation analysis of single-hop nodes is carried out. After $N$ times of packet exchange, the mean square errors (MSEs) of clock skew and clock between child node $n(n=i,m)$ and its parent node $j$ are defined as

$$\begin{array}{c}\mathrm{MS}{\mathrm{E}}_{\omega }=\sum _{k=1}^{1000}{({\hat{\omega }}^{\mathrm{nj}}(k)-{\omega }^{\mathrm{nj}}(k))}^2/1000\hfill \\ \mathrm{MS}{\mathrm{E}}_{\phi }=\sum _{k=1}^{1000}{({\hat{\phi }}^{\mathrm{nj}}(k)-{\hat{\phi }}^{\mathrm{nj}}(\mathrm{k}))}^2/1000\hfill \end{array}$$

(18)

respectively. For PS and OS nodes, Figure 5(a) shows the relationship between the clock offset estimation MSE and the synchronization information exchange time $N$ ; Figure 5(b) shows the relationship between their skew offset estimation MSE and the synchronization information exchange time $N$ .

Figure 5.

Relationship between one-hop clock estimation MSE and number of transmissions $N$ . (a) Clock offset and (b) clock skew.

We can see from Figure 5 that (1) as the number of transmissions $N$ increases, the MSEs of clock offset estimation and clock skew estimation both decrease; when $N=10$ , the phase offset MSE and clock skew MSE of PS nodes and OS nodes are, respectively, $3.5\times {10}^{-4}\mathrm{s}$ , $7.4\times {10}^{-4}\mathrm{s}$ and $6\times {10}^{-9}$ , $2\times {10}^{-9}$ ; the relative clock skew and phase offset estimation methods proposed in this article are effective with certain synchronization accuracy and (2) the synchronization accuracy of PS nodes is better than that of OS nodes because PS nodes have more synchronization information as compared with the OS nodes; the overhearing-based time synchronization method improves synchronization energy efficiency by decreasing accuracy.

Next, the synchronization errors of nodes at different layers relative to the sink node are simulated. For a child node $i(i=1,\dots ,29)$ , we define its synchronization errors of clock skew and clock offset relative to the sink node as

$$\begin{array}{c}{\omega }_e^i=\sum _{k=1}^{1000}|{\hat{\omega }}^{i0}(k)-{\omega }^{i0}|/1000,\hfill \\ {\phi }_e^i=\sum _{k=1}^{1000}|{\hat{\phi }}^{i0}(k)-{\phi }^{i0}|/1000\hfill \end{array}$$

(19)

By taking the maximum estimation errors of nodes at the same layer as the estimation error of that layer relative to the sink node, we can obtain the relationship curves between the clock skew estimation error and clock offset estimation error of nodes at different layers to the sink node concerning the number of transmissions $N$ , as shown in Figures 6 and 7.

Figure 6.

Skew error to sink node for nodes at different layers. (a) PS nodes and (b) OS nodes.

Figure 7.

Offset error to sink node for nodes at different layers. (a) PS nodes and (b) OS nodes.

From Figures 6 and 7, one has:

1. The time synchronization method proposed in this article can realize time synchronization at the network level: when the number of synchronization information exchanges is set as $N=10$ , the estimation errors of the maximum skew and clock offset of the network nodes relative to the sink node are $1.5\times {10}^{-3}(\mathrm{s})$ and $2\times {10}^{-4}$ , respectively. Therefore, the method proposed in this article can realize time synchronization at the network level with a certain accuracy.

2. The clock skew and clock offset synchronization errors of nodes relative to the sink node increase with the increase in network hierarchy; therefore, the number of layers $L$ can be reduced by expanding the communication radius of nodes in the network topology control stage, to improve the synchronization accuracy of the network.

3. For PS nodes, as the number of synchronization information exchanges increases, the synchronization errors of all hierarchical nodes relative to the sink node decrease significantly. Increasing $N$ value can improve the synchronization accuracy.

4. The estimation errors of OS nodes are larger than those of PS nodes, and the declining trend is gentle with the increase in $N$ , indicating that the relative offset estimation based on the overhearing mode only needs a small amount of synchronization error information exchange.

Analysis of synchronization energy consumption

Data transmission in time synchronization accounts for the majority of the energy consumption of the time synchronization algorithm.^11,27 Thus, the energy consumption of the algorithm is measured by the synchronization data amount of the algorithm, that is, the total amount of packet needed in one time synchronization period. For the network topology shown in Figure 4, the number of nodes to be synchronized is 29, and $\left|\mathit{p}\right|=3$ is the number of PS vector elements of the algorithm. After the chain-type network topology generation stage is completed, the algorithm in this article needs to be grouped $(\left|\mathit{p}\right|+1)N=4N$ times in the time synchronization stage, and PS nodes need to be grouped $\left|\mathit{p}\right|$ times to estimate the synchronization error relative to the sink node layer by layer. Therefore, the total synchronization data amount is $4N+3$ times of grouping. Similarly, the synchronization data amount required by PBS algorithm is $\left|\mathit{p}\right|\times 2N+\left|\mathit{p}\right|=6N+3$ . The RBS needs to rely on an effective clustering method to achieve time synchronization of the whole network. Based on a clustering situation in Figure 4, the number of groupings for the cluster head sending data is $5N$ , and the number of information exchanges within the clusters is $(6+4+5+7+3)N$ . Hence, the total synchronization data amount is $30N$ . Also, the synchronization data amount for TPSN is $29\times 2N$ , and that of FTSP is $29N$ .

The comparison between the synchronization method in this article and the other three typical time synchronization algorithms is shown in Figure 8. From Figure 8, one can have that the method proposed in this article consumes the least synchronized data amount. That is because the GPA method is adopted in this article for network PS node selection and the SMA mechanism is introduced into the time synchronization at the network level.

Figure 8.

Synchronization packet amount comparison among some time synchronization methods.

As seen in Figures 6–8, the introduction of an overhearing-based time synchronization mechanism can significantly reduce the synchronization information transmitted in the network and improve time synchronization accuracy. However, the effect of the overhearing mechanism on improving accuracy is worse than that of the bidirectional information exchange mechanism. In practical design, the compromise between synchronization accuracy and synchronization information amount can be achieved through a reasonable selection of PS nodes.

Conclusion

A continuous multi-hop time synchronization method based on a new-marked timestamp has been proposed in this article. First, one receiving-time-plus-fixed-delay mode has been introduced to realize the accurate acquisition of the synchronization ack packet’s timestamp. Then, the reduction of the synchronization data amount has been studied from three aspects: the GPA chain-type network topology generation, the continuous multi-hop time synchronization method, and the overhearing-based synchronization information acquisition. Also, the PS node nearest to the sink node periodically initiates the time synchronization at the network level. Other PS nodes in the network assist the upper layer child node in being synchronized to the sink node. Finally, some numerical simulations have been carried out to show the effectiveness of our proposed time synchronization method. How to design a time synchronization method robust to communication topology and delay in the constrained communication environment is the beacon of our future research.