# Achieving Relative Time Synchronization in Wireless Sensor Networks

Authors: Salman Ahmed; Feng Xiao; Tongwen Chen
Journal: Journal of Control Science and Engineering
 (2013)

---

## Abstract

Time synchronization is required for a variety of distributed control applications in wireless sensor networks (WSNs). In this paper, a novel distributed time synchronization technique for WSNs is presented. The proposed technique does not require all the sensor nodes to have the same time periods or starting times. Furthermore, the communication topology of the WSN is not assumed to be static; it can change with time. The WSN is modeled by a time-varying discrete-time system. The objective is to design local control inputs to achieve relative time synchronization by using the neighbor sensor nodes information. By employing tools from nonnegative matrix and graph theories, the convergence analysis is presented. Numerical examples are presented to demonstrate the effectiveness of the proposed protocol.


---

## Body

## 1. Introduction

Distributed time synchronization in wireless sensor networks (WSNs) has been an important topic of research in the control community [1–3]. In most distributed control applications, coordination among sensor nodes requires precise time synchronization [4, 5]. Time synchronization in a WSN is also required for many other tasks such as data fusion, transmission scheduling, and nodes sleep and wake-up scheduling. Therefore, it is important to design distributed protocols to achieve time synchronization in a WSN.A common approach to design time synchronization protocols is to create a hierarchical structure within the WSN. The most prominent examples are the reference broadcast Synchronization (RBS) [6], timing-sync protocol for sensor networks (TPSN) [7], and flooding time synchronization protocol (FTSP) [8]. The implementation of RBS requires that the WSN should be divided into distinct clusters and each cluster should have a leader or reference node, all the leader nodes synchronize themselves with respect to each other and sensor nodes within the same cluster synchronize themselves with respect to their leader node. The implementation of TPSN and FTSP requires that a spanning tree rooted at a reference node should be built in the WSN and the time difference of any sensor node can be obtained with respect to the reference node. Although the hierarchy-based protocols have been experimentally tested in [8] and their performance is remarkable, they require substantial overhead to rebuild the spanning tree or clusters if a sensor node dies or a new sensor node is added.Distributed time synchronization protocols which do not require a hierarchal structure have been proposed in [3, 9, 10], where the authors have considered a continuous time system to represent the clock of a sensor node. It is assumed that the clock of a sensor node has the same continuity property as the physical time and it can measure in any time interval. In actual implementation, the clock of a sensor node has some frequency or time period. A clock cannot measure a time interval which is shorter than its time period. Hence, it is more reasonable to use a discrete-time system to model a clock.Discrete-time systems to model clocks in a WSN have been used in [1, 11, 12]. For the design of time synchronization protocol, the authors have assumed that all the sensor nodes should periodically exchange and update their clock states at the same time instants. This assumption is unrealistic since it requires synchronization of all clocks, which is the goal of the protocol. In this paper, we propose a time synchronization protocol which relaxes the three main assumptions used in the literature. First, the proposed protocol does not require all the sensor nodes to have the same time periods or starting times. Second, all the sensor nodes are not restricted to exchange and update their clock states at the same time instants. Third, the communication topology of the WSN is not assumed to be static. We use the discrete-time clock model presented in [1]. We assume that each sensor node knows its time period but does not know its exact starting time. Each sensor node exchanges its clock readings with its neighbors. The objective of the time synchronization protocol is to synchronize the clocks in a WSN with respect to a virtual clock, which is not physically present or accessible to any sensor node. The virtual clock is only used to demonstrate the concept of time synchronization in a WSN as the time periods and starting times of sensor nodes can be different.The remainder of this paper is structured as follows: Section2 presents some basic definitions and results from graph and matrix theories. The problem is formulated in Section 3. The main results and analysis are presented in Section 4. Numerical examples to demonstrate the effectiveness of the proposed protocol are presented in Section 5. Finally, concluding remarks are given in Section 6.


## 2. Preliminaries

In this section, we present some definitions and results from graph and matrix theories which will be used in this paper.Let1=[1,…,1]T∈ℝn, In∈ℝn×n denote an identity matrix, and the symbol ℕ denote the set of nonnegative integers. A matrix S is nonnegative if all its elements are nonnegative [13]. A non-negative, finite, and square matrix S is called stochastic if the sum of each row is 1. A stochastic matrix S is called indecomposable and aperiodic (SIA) if there exists a column vector w such that limk→∞Sk=1wT [14]. Let ∏i=1k‍Si=Sk,Sk-1,…,S1 denote the left product of the matrices Sk,Sk-1,…,S1. For any matrix S, we write spq to represent the element which lies in the pth row and qth column of S.Consider an undirected (directed) graph𝒢 which consists of a vertex set, 𝒱(𝒢)={v1,…,vn}, and an edge set, ℰ(𝒢)⊂{(vi,vj):vi,vj∈𝒱(𝒢)} where an edge is an unordered (ordered) pair of vertices [15]. The index set of neighbors of vertex vi is denoted by 𝒩i={j:(vj,vi)∈ℰ(𝒢),j≠i} and its cardinality by |𝒩i|. A path from vi1 to vik is a sequence, vi1,…,vik of distinct vertices such that (vij,vij+1)∈ℰ(𝒢) for any j=1,…,k-1. An undirected (directed) graph 𝒢 is connected (strongly connected) if there is a path between any two distinct vertices. A directed tree is a directed graph where every vertex except the root vertex has exactly one parent vertex and the root vertex can be connected to any other vertices via paths. A spanning tree of directed graph 𝒢 is a directed tree whose edge set belong to ℰ(𝒢) and vertex set is the same as 𝒱(𝒢). The Laplacian matrix of 𝒢 is denoted by L=[lpq]∈ℝn×n and is defined as follows:
(1)lpq={-1ifp≠q,q∈𝒩p,|𝒩p|ifp=q,0otherwise.
Let S=[spq]∈ℝn×n be a nonnegative matrix. Then, 𝒢(S) is defined as a directed graph having vertex set 𝒱(𝒢(S))={v1,…,vn}, and edges from vq to vp if and only if spq>0. We present some lemmas which will be used later.Lemma 1 (see [16]).
LetS be a stochastic matrix. If 𝒢(S) contains at least one spanning tree such that the root vertex of that spanning tree has a self-loop in 𝒢(S), then S is SIA.Lemma 2 (see [14]).
LetΓ={S1,S2,…,Sk} be a finite set of SIA matrices such that for each sequence Si1,Si2,…,Sij of positive length, the matrix product Sij,Sij-1,…,Si1 is SIA. Then, for each infinite sequence Si1,Si2,…, there exists a column vector w such that the following holds:
(2)limj→∞Sij,Sij-1,…,Si1=1wT.


## 3. Problem Formulation

We consider a WSN havingn sensor nodes. Each sensor node has a local clock which consists of a software program and a hardware oscillator. The oscillator periodically generates time interrupts using its time period and the software computes the local time of the sensor node at those time instants when the interrupts are generated [1]. Let τi, xi and t0i denote the time period, clock value, and starting time of sensor node i, respectively, where i=1,…,n. Each sensor node knows its time period but does not exactly know its starting time. Rather, its estimate, denoted by t^0i for sensor node i, is known. Let Ti={t~ki:k=0,1,….,} represent the sequence of time instants when the clock of sensor node i updates its state, where t~ki:=kτi+t0i. The time computed locally by sensor node i can be expressed as follows:
(3)xi(t~k+1i)=xi(t~ki)+τi,xi(t~0i)=t^0i,i=1,…,n.
If each sensor node does not exactly know its starting time, then the clocks in the WSN would not be synchronized. To achieve time synchronization, we apply a control input to adjust the clock readings of sensor nodes. The control input is applied periodically at a certain known integer multiple of the local clock time period. Let tsi:=t~0+szii be the time instants when the control input is applied to the clock of sensor node i, where zi is a known integer, s∈ℕ and i=1,…,n. We can write the following:
(4)xi(ts+1i)=xi(tsi)+ziτi+ui(tsi),xi(t0i)=xi(t~0i),
where ui(tsi) denotes the control input or protocol which is needed to be designed. A virtual continuous time clock can be expressed as follows:
(5)v(t)=at+b,
where t represents the time of WSN, v represents the clock readings, and a and b represent the time period and initial offset of the virtual clock, respectively. The virtual clock is not available to any sensor node. It is only used to demonstrate the concept of relative time synchronization. The clocks in a WSN are said to be synchronized if there exists a common virtual clock in the form of (5) such that the following holds:
(6)limt~k→∞i(xi(t~ki)-(t~ki+b))=0,∀i=1,…,n.
As each clock knows its own time period, we use a=1 for the common virtual clock. The sensor nodes communicate with their neighbors and exchange clock readings. The communication topology of the WSN can be modeled by a time-varying undirected graph, 𝒢(tsi), where i=1,…,n and s∈ℕ. The neighbors of sensor node j at tsi consist of those sensor nodes which are able to communicate with node j at tsi, where i,j=1,…,n and s∈ℕ. Let 𝒩i(tsi) denote the index set of sensor node i neighbors and let L(tsi) represents the Laplacian matrix associated with 𝒢(tsi). The following assumptions are required to ensure that the clocks can be synchronized.(A1)
There exists a known integerκ such that each sensor node i can obtain information at least once from any possible neighbor during [tsi,ts+κi], where i=1,…,n and s∈ℕ.(A2)
There exists an integerp≥0 such that the union of graphs 𝒢(tsi),𝒢(ts+1i),…,𝒢(ts+pi), is connected, for all i=1,…,n, and s∈ℕ.(A3)
For any two sensor nodesi and j, the following holds:
(7)tsi∈Tj,∀s.It should be noted that (A1) is made to ensure that each senor node can receive information from its possible neighbors in a finite interval of time. Assumption (A2) is made to ensure that union of communication topologies during a specific time interval remains connected, although at some particular time instants the communication topology may not be connected. Assumption (A3) is made so that by using the proposed protocol the relative time synchronization error in the WSN can be driven to zero. In actual implementation, if (A3) can not be ensured to hold for all sensor nodes, then it can be relaxed to consider neighboring nodes only. If (A3) is not ensured for neighboring nodes, then a small approximation error may exist due to the fact that the starting times and time periods of the sensor nodes may be different. In the next section, we present the main results to achieve relative time synchronization.


## 4. Main Results

We present the following protocol for achieving time synchronization:(8)ui(tsi)=αi(tsi)∑j∈𝒩i(tsi)‍(xj(tsi)-xi(tsi)),i=1,…,n,
where αi(tsi) denotes a gain which needs to be designed. For synchronized distributed control systems, a protocol similar to (8) has been presented in [17]. In this paper, we study protocol (8) for asynchronous distributed control systems. The following theorem presents the main results.Theorem 3.
Consider a WSN which satisfies assumptions (A2) and (A3). Then, the clocks of the sensor nodes achieve relative time synchronization using protocol (8) if αi(tsi)∈(0,1/|𝒩i(tsi)|), ∀i=1,…,n and s∈ℕ.Remark 4.
If the communication topology of the WSN is static, then we can allowαi(tsi)∈(0,1/d), ∀i=1,…,n and s∈ℕ, where d denotes the maximum of the diagonal entries of L.The proof of Theorem3 consists of three main steps. In the first step, we combine the local clock models and define a new time sequence to represent the local clock models by a single time-varying system. In the second step, we use the new time sequence to compute an upper bound on the time interval in which each sensor node obtains information at least once from all its neighbors. Finally, we complete the proof by utilizing the properties of connected graphs and product of SIA matrices.


### 4.1. Representation by a Single System

Before grouping the local clock models to represent them by a single system, we define a new state as follows:(9)yi(tsj)=xi(tsj)-(tsj-t0),i,j=1,…,n.
We rewrite the model expressed by (4) and control protocol (8) as follows:
(10)yi(ts+1i)=yi(tsi)+ui(tsi),yi(t0i)=xi(t0i),ui(tsi)=αi(tsi)∑j∈𝒩i(tsi)‍(yj(tsi)-yi(tsi)),i=1,…,n.
Let th=max{t~0i,i=1,…,n}, and we define a new time sequence T:={tr}, where r∈ℕ, which is the union of the distinct values of the sequences {tsi≥th,i=1,…,n,s∈ℕ}. We order the values of T such that tr<tr+1. We mention here that the distances between consecutive elements of T are nonuniform. The time-synchronization objective can be rewritten as follows:
(11)limtr→∞(yi(tr)-b)=0,i=1,…,n,
for some b. Let y(tr)=[y1(tr),…,yn(tr)]T denote the group state vector. The dynamics of the overall system can be written as follows:
(12)y(tr+1)=(In-A(tr)L(tr))y(tr),
where A(tr)=[apq], L(tr)=[lpq],
(13)apq={αp(tr)ifp=q,∃ss.t.tr=tsp,0otherwise,lpq={-1ifq∈𝒩p(tr),∃ss.t.tr=tsp,|𝒩p(tr)|ifp=q,∃ss.t.tr=tsp,0otherwise.
It should be noted that L(tr) is a time-varying Laplacian matrix which can be unsymmetric and the graph associated with L(tr) may not be strongly connected. Let Φ(tr)=In-A(tr)L(tr), the solution of (12) can be written as follows:
(14)y(tr)=Φ(tr)Φ(tr-1)⋯Φ(t0)y(t0),r=0,1,….
If αi(tsi)∈(0,1/|𝒩i(tsi)|)∀i,s, then Φ(tr) are always stochastic matrices with positive diagonal entries. The product Φ(tr)Φ(tr-1)Φ(tr-2)⋯Φ(t0) is also a stochastic matrix with positive diagonal entries. With this preparation, we proceed to the next step.


### 4.2. Computation of an Upper Bound on the Time Interval

The following lemma is quite useful in the computation of an upper bound on the time interval in which each sensor node can obtain information at least once from its neighbors.Lemma 5.
Letg=max{ziτi}/min{ziτi} where i=1,…,n. For any sensor node i=1,…,n and s=1,2,…, the number of elements in the set {tp:tp∈[tsi,ts+1i)} is not greater than h, where h=(⌈g⌉)(n-1)+1 and ⌈g⌉ denotes the smallest integer not less than g.Proof.
Letj be the sensor node such that zjτj≥ziτi where i=1,…,n,i≠j. When sensor node j updates its control input at tsj, the maximum number of times any sensor node i can update its control input before the time instant ts+1j cannot exceed ⌈g⌉, where i=1,…,n,i≠j. Since there are n-1 possible values of sensor node i (excluding i=j), we conclude that the number of elements in {tp:tp∈[tsj,ts+1j)} is not greater than h.Using Lemma5 and assumption (A1), we can state that each sensor node obtains information from all its neighbors at least once during the time interval [tm-κh,tm], where m=κh,κh+1,….


### 4.3. Technical Analysis

Let𝒢-(tm) be the graph obtained by the union of 𝒢(Φ(tm)),…,𝒢(Φ(tm-κh)). Using (A2), we conclude that 𝒢-(tm) is strongly connected. If 𝒢-(tm) is strongly connected, then, by using Lemma 1 together with [18, Lemma 3.9], we establish that the product of Φ(tm)⋯Φ(tm-q) is SIA.LetF0=∏l=0h-1‍Φ(tl), F1=∏l=h2h-1‍Φ(tl), F2=∏l=2h3h-1‍Φ(tl) and so on. Then, it can be easily shown that all possible unique Fj’s are finite, where j=0,1,…. Any product which involves a finite combination of the unique Fj’s is SIA. So, we can apply Lemma 2 to get the following conclusion:
(15)limk→∞∏j=0k‍Fj=1wT.
The vector w depends on the order in which the matrices Φ(tl) are multiplied, where l=0,1,…, and it cannot be computed in advance. We can further write the following:
(16)limtr→∞y(tr)=1wTy(t0)=(wTy(t0)⋮wTy(t0)).
Hence, we complete the proof of time synchronization protocol by taking b=wTy(t0).


## 4.1. Representation by a Single System

Before grouping the local clock models to represent them by a single system, we define a new state as follows:(9)yi(tsj)=xi(tsj)-(tsj-t0),i,j=1,…,n.
We rewrite the model expressed by (4) and control protocol (8) as follows:
(10)yi(ts+1i)=yi(tsi)+ui(tsi),yi(t0i)=xi(t0i),ui(tsi)=αi(tsi)∑j∈𝒩i(tsi)‍(yj(tsi)-yi(tsi)),i=1,…,n.
Let th=max{t~0i,i=1,…,n}, and we define a new time sequence T:={tr}, where r∈ℕ, which is the union of the distinct values of the sequences {tsi≥th,i=1,…,n,s∈ℕ}. We order the values of T such that tr<tr+1. We mention here that the distances between consecutive elements of T are nonuniform. The time-synchronization objective can be rewritten as follows:
(11)limtr→∞(yi(tr)-b)=0,i=1,…,n,
for some b. Let y(tr)=[y1(tr),…,yn(tr)]T denote the group state vector. The dynamics of the overall system can be written as follows:
(12)y(tr+1)=(In-A(tr)L(tr))y(tr),
where A(tr)=[apq], L(tr)=[lpq],
(13)apq={αp(tr)ifp=q,∃ss.t.tr=tsp,0otherwise,lpq={-1ifq∈𝒩p(tr),∃ss.t.tr=tsp,|𝒩p(tr)|ifp=q,∃ss.t.tr=tsp,0otherwise.
It should be noted that L(tr) is a time-varying Laplacian matrix which can be unsymmetric and the graph associated with L(tr) may not be strongly connected. Let Φ(tr)=In-A(tr)L(tr), the solution of (12) can be written as follows:
(14)y(tr)=Φ(tr)Φ(tr-1)⋯Φ(t0)y(t0),r=0,1,….
If αi(tsi)∈(0,1/|𝒩i(tsi)|)∀i,s, then Φ(tr) are always stochastic matrices with positive diagonal entries. The product Φ(tr)Φ(tr-1)Φ(tr-2)⋯Φ(t0) is also a stochastic matrix with positive diagonal entries. With this preparation, we proceed to the next step.


## 4.2. Computation of an Upper Bound on the Time Interval

The following lemma is quite useful in the computation of an upper bound on the time interval in which each sensor node can obtain information at least once from its neighbors.Lemma 5.
Letg=max{ziτi}/min{ziτi} where i=1,…,n. For any sensor node i=1,…,n and s=1,2,…, the number of elements in the set {tp:tp∈[tsi,ts+1i)} is not greater than h, where h=(⌈g⌉)(n-1)+1 and ⌈g⌉ denotes the smallest integer not less than g.Proof.
Letj be the sensor node such that zjτj≥ziτi where i=1,…,n,i≠j. When sensor node j updates its control input at tsj, the maximum number of times any sensor node i can update its control input before the time instant ts+1j cannot exceed ⌈g⌉, where i=1,…,n,i≠j. Since there are n-1 possible values of sensor node i (excluding i=j), we conclude that the number of elements in {tp:tp∈[tsj,ts+1j)} is not greater than h.Using Lemma5 and assumption (A1), we can state that each sensor node obtains information from all its neighbors at least once during the time interval [tm-κh,tm], where m=κh,κh+1,….


## 4.3. Technical Analysis

Let𝒢-(tm) be the graph obtained by the union of 𝒢(Φ(tm)),…,𝒢(Φ(tm-κh)). Using (A2), we conclude that 𝒢-(tm) is strongly connected. If 𝒢-(tm) is strongly connected, then, by using Lemma 1 together with [18, Lemma 3.9], we establish that the product of Φ(tm)⋯Φ(tm-q) is SIA.LetF0=∏l=0h-1‍Φ(tl), F1=∏l=h2h-1‍Φ(tl), F2=∏l=2h3h-1‍Φ(tl) and so on. Then, it can be easily shown that all possible unique Fj’s are finite, where j=0,1,…. Any product which involves a finite combination of the unique Fj’s is SIA. So, we can apply Lemma 2 to get the following conclusion:
(15)limk→∞∏j=0k‍Fj=1wT.
The vector w depends on the order in which the matrices Φ(tl) are multiplied, where l=0,1,…, and it cannot be computed in advance. We can further write the following:
(16)limtr→∞y(tr)=1wTy(t0)=(wTy(t0)⋮wTy(t0)).
Hence, we complete the proof of time synchronization protocol by taking b=wTy(t0).


## 5. Numerical Examples

In this section, we present two examples to demonstrate the effectiveness of the proposed time synchronization protocol.Example 1 (static topology, small-size WSN).
We consider a WSN having10 sensor nodes and label them as 1,…,10. We assume that the communication topology of the WSN is not changing with respect to time (κ=0) and is shown in Figure 1. Using Theorem 3, we choose αi=0.3,∀i. The values for different parameters satisfying (A2) and (A3) are listed in Table 1. By applying protocol (8), the WSN was simulated for 50 seconds. Figure 2 shows a plot of the clock readings for 50 seconds. Figure 3 illustrates a plot of the local control inputs applied to the sensor nodes. Based on the plots, it can be concluded that this WSN achieves distributed time synchronization using the proposed protocol.Table 1
Parameter values used to simulate the WSN as shown in Figure1.
Sensor nodes
1
2
3
4
5
6
7
8
9
10
Time period (sec)
0.01
0.02
0.01
0.05
0.04
0.02
0.1
0.01
0.2
0.4
Actual starting time (sec)
0.1
0
1.3
1.01
1
0.04
0.12
0.4
0.16
0
Estimated starting time (sec)
1.5
−12.5
3.19
−25.19
10.04
−7.34
2.19
3.25
0
14.58
Value ofz
80
100
100
100
80
100
80
10
10
10Figure 1
Communication topology of a WSN considered in Example1 having 10 sensor nodes. The lines indicate the presence of communication channels for exchanging clock readings.Figure 2
Plot of the local clock readings of a WSN considered in Example1. The topology of the WSN is shown in Figure 1.Figure 3
Plot of the local control inputs applied to the WSN considered in Example1. The topology of the WSN is shown in Figure 1.Example 2 (switching topology, medium-size WSN).
We consider a WSN having45 sensor nodes and label them with 1,…,45. We consider that the communication links in the WSN are changing randomly with respect to time. Figure 4 shows the union of possible communication topologies of the WSN. We randomly select the parameter values for different sensor nodes from Table 1 and choose κ=3. For simulation purposes, we compute the relative time synchronization error of sensor node i with respect to its neighbor nodes, denoted by ei(tr), as follows:
(17)ei(tr)=∑j∈𝒩(𝒢i(tr))‍|(xi(tr)-xj(tr))|,i=1,…,45.
Applying Theorem 3, we simulate the WSN for 80 seconds and select the values for αi at run time based on the communication topology. Figure 5 shows a plot of the sum of time synchronization errors. Based on the plots, it can be concluded that, by using protocol (8) and applying Theorem 3, this WSN also achieves distributed time synchronization.Figure 4
The graph of union of communication topologies of a WSN considered in Example2 having 45 sensor nodes labeled as 1,…,45. The lines indicate the presence of communication channels only and do not indicate if at a particular time instant any information is exchanged on the communication link.Figure 5
Plot of the sum of the relative time synchronization errors in the WSN considered in Example2. The graph of the union of communication topologies of the WSN is shown in Figure 4.


## 6. Conclusions and Future Research Directions

In this paper, we presented a distributed time synchronization protocol for WSNs. The time periods and starting times of the sensor nodes were not restricted to be the same. By employing tools from stochastic matrix and algebraic graph theories, we presented the convergence analysis. In this paper, we considered that a sensor node could access the clock readings of its available neighbors without any delays. In actual implementation, time delay occurs between transmission and reception of information in a WSN. In the future work, we can consider this by modifying the protocol to handle time-delayed measurements from neighbors.



---

*Source: 538181-2013-09-11.xml*