This paper proposes a novel discrete-time second-order distributed consensus time synchronization (SO-DCTS) algorithm for wireless sensor networks. The consensus properties and convergence rates of the SO-DCTS algorithm are analyzed for both directed and undirected networks. Additionally, the convergence region and optimal convergence rate of the SO-DCTS algorithm are determined for undirected networks and this convergence rate is shown to be superior to that of the first-order DCTS (FO-DCTS) algorithm under careful algorithm design. Furthermore, the asymptotic expectation and mean square synchronization error are investigated for the SO-DCTS algorithm when there is Gaussian delay between network nodes. Finally, simulation results are provided to verify these analytical results.
1. Introduction
Wireless sensor networks are typically comprised of inexpensive, small-sized, power-limited terminals. In a variety of applications, these sensor nodes are collectively required to maintain accurate time synchronization, for example, moving object acquisition and tracking, habitat monitoring, reconnaissance and surveillance, environmental monitoring, traffic control, and so forth [1]. This necessitates network algorithms that achieve and maintain global time synchronization at all network nodes, that is, algorithms that align all network nodes to a common notion of time.
Due to imperfections in low-cost hardware nodes and the decentralized nature of wireless sensor networks, global time synchronization has been recognized as a particularly challenging task. Conventional synchronization protocols such as time-synchronization protocol for sensor networks (TPSNs) [2], reference broadcast synchronization (RBS) [3], and flooding time synchronization protocol (FTSP) [4] aim to perform centralized global synchronization for all nodes in wireless sensor network [5]. These protocols achieve synchronization via time-stamped packet exchanges with a root node or a data fusion center and are thus vulnerable to failure of these central nodes.
Advertisement
Recently, several distributed time synchronization algorithms have been proposed. One important class of such algorithms is referred to as distributed consensus time synchronization (DCTS) [6]. In the DCTS approach, a global time consensus can be sufficiently reached within a connected network by averaging pair-wise local time information at network nodes. In [7], Olfati-Saber et al, established a theoretical framework for the analysis of consensus synchronization algorithms. Later, a fully distributed, asynchronous DCTS algorithm was proposed in [8]; this scheme was designed to reach agreement on time offset and skew offset between network nodes using media access control (MAC) layer time-stamped packet exchanges. As an alternative, a physical layer-based DCTS algorithm was introduced in [9] by modeling sensor nodes as coupled discrete-time oscillators. In particular, the algorithm adopts instantaneous received powers as weighted coefficients when updating local clocks.
To the best of our knowledge, existing literature on DCTS methods assumes that local timing update at each node is done using only current timing information, that is, via a first-order DCTS (FO-DCTS) approach. In contrast, a second-order DCTS (SO-DCTS) algorithm would utilize not only current timing information but also that available from the previous iteration of the algorithm to update local clocks. Such an extension to the basic consensus algorithm was first reported for a continuous time approach in [10]. Subsequent papers have analyzed this second-order continuous time consensus method assuming fixed network topologies [11], time delay [12], and switching topologies [13]. In this paper, we apply the principles of the second-order consensus approach to the distributed timing synchronization problem in wireless sensor networks. Specifically, we propose a novel discrete-time SO-DCTS algorithm for wireless sensor networks and examine its convergence properties.
The major contribution of this paper is the theoretical analysis of the convergence characteristics of the SO-DCTS algorithm for both directed and undirected networks. Moreover, we investigate the convergence region and optimal convergence rate of the SO-DCTS algorithm in undirected networks and claim that the optimal convergence rate of the SO-DCTS algorithm is superior to that of the FO-DCTS algorithm under an appropriate algorithm design. Finally, we present the asymptotic expectation and mean square synchronization error of the SO-DCTS algorithm when the timing offset between network nodes is Gaussian distributed.
This paper is outlined as follows. Section 2 describes the system model and background for the proposed SO-DCTS algorithm. Section 3 presents the convergence properties of the SO-DCTS algorithm in directed and undirected networks. Section 4 discusses the convergence region and optimal convergence rate of the SO-DCTS algorithm in undirected networks. In Section 5, we present some convergence results for the SO-DCTS method when network nodes have Gaussian delay between each other. Simulation results are presented in Section 6, and we conclude our discussion in Section 7.
Advertisement
2. Background and System Model
2.1. Proposed So-Dcts Algorithm
Timing information between network nodes can be exchanged either using time-stamped packets at the MAC layer or by estimating arrival times of neighboring nodes' physical layer pulse signals. In the following, we describe the SO-DCTS method regardless of whether it is implemented at the MAC or physical layers. In each iteration of the SO-DCTS algorithm, each node processes and decodes the time-stamped message from its neighbors or estimates the arrival time of its neighbors' pulse signals. Each node then updates its local clock using the weighted average of the current time differences between itself and its neighboring nodes as well as stored time differences from the previous iteration of the algorithm. It should be noted that in the SO-DCTS algorithm, each node needs to store time information from its neighbor nodes for both the previous and current iterations; this is in contrast to the FO-DCTS approach where only the current time information is processed in the current iteration.
The timing update rule of the SO-DCTS algorithm at each node is given as
(1)
where is the local time at node during iteration ; is the set of neighboring nodes that can communicate reliably with node ; is a constant step size; is a constant for each iteration. We assume that initial conditions of the SO-DCTS algorithm are , where is initial time offset for node . It is worth mentioning that when , the SO-DCTS algorithm reduces to the FO-DCTS algorithm.
2.2. Network Model and Some Preliminaries
In the following, we model a wireless sensor network as a graph , consisting of a set of nodes and a set of edges . Each edge is denoted as where and are head and tail of the edge , respectively. In a wireless sensor network, the presence of an edge indicates that node can communicate with node reliably. We assume here a connected graph; that is, there exists a directed path connecting any pair of distinct nodes in the network. Throughout our discussion, we assume a time-invariant and connected network unless otherwise stated.
Given this network model, we denote as the adjacency matrix of such that
(2)
Then, the in-degree and out-degree of a node (denoted as and , resp.,) are given as , and Specifically, is also equal to the number of neighbors of node from which it can receive information reliably, that is, .
Next, we let be the graph Laplacian matrix of which is defined as , where is the degree matrix of . Given this matrix , we can show that , where , and . In particular, for a connected graph, the rank of is . Furthermore, for a balanced directed network, the in-degree and out-degree of a node are equal, that is, , thus we see that .
For an undirected network, the presence of an edge indicates that nodes and can communicate with each other reliably. Under this condition, we can also show that . Additionally, in this case, is a symmetric positive semidefinite matrix (implying that its eigenvalues are nonnegative), and its eigenvalues can be arranged in increasing order as [14].
Let us define . The evolution of the SO-DCTS algorithm in (1) can be written as
(3)
with the initial conditions , where . Here, denotes the identity matrix.
3. Convergence Properties of The So-Dcts Algorithm
In this section, we investigate the consensus properties of the SO-DCTS algorithm in directed and undirected networks. Additionally, we discuss the convergence rate of the SO-DCTS algorithm in such networks.
3.1. Consensus Analysis of The So-Dcts Algorithm
The main result regarding the average consensus property of the SO-DCTS algorithm in directed networks is stated in the following theorem.
Theorem 1.
For a time-invariant, connected, directed network, consider the SO-DCTS algorithm,
(4)
with initial conditions . Define
(5)
where and is the left eigenvector of associated with . When , a global consensus is achieved asymptotically, or equivalently,
(6)
where denotes the spectral radius of a matrix.
Proof.
The proof of this theorem is similar to [11, 15]. Here, we present a sketch proof. Let us define . Then, the SO-DCTS algorithm in (4) can be rewritten as
(7)
which implies To calculate the eigenvalues of , we have [16]
(8)
Thus, the eigenvalues of are
(9)
For a time-invariant, connected, directed network, has only one eigenvalue . Then, we know that has two eigenvalues and . Additionally, the eigenvalues of agree with those of except that is replaced by [16]. Since , we see that the eigenvalues of stay inside the unit circle except for . Thus, we have
(10)
where is the Jordan form matrix corresponding to eigenvalues [16], and are left and right eigenvectors of corresponding to , respectively, and . In particular, and . Plugging and into (10) and considering the SO-DCTS algorithm in (7), we have
(11)
which indicates that
(12)
This completes the proof.
According to Theorem 1, we see that in general, although average consensus is not achieved for directed networks, all nodes in the network can still reach a global agreement. By "average consensus" we mean that all nodes converge to the same timing which is determined by the average of the initial timing differences between the nodes. However, when the SO-DCTS algorithm is employed in either an undirected network or a balanced directed network, average consensus can be achieved asymptotically. We show this via the following theorem.
Theorem 2.
Consider the SO-DCTS algorithm in (4) in a time-invariant, connected, directed balanced network or a time-invariant, connected, undirected network, with initial conditions . When , an average consensus is achieved asymptotically, or equivalently,
(13)
We know that in a time-invariant, connected, directed balanced or undirected network, and . The rest of proof is similar to that of Theorem 1 and thus omitted here.
3.2. Convergence Rate for So-Dcts Algorithm
One of the most important measures of any distributed iterative algorithm is its convergence speed. As we show next, the convergence speed of the SO-DCTS algorithm is determined by the spectral radius of , which is similar to the FO-DCTS algorithm [17].
Let us define the global consensus value in each iteration as . In the SO-DCTS algorithm, this value remains invariant during each iteration since
(14)
We now define the disagreement vector as , which indicates the difference between the updated times and the global consensus times of the network nodes. Then, the evolution of the disagreement vector is obtained as
(15)
Given this dynamic of the disagreement vector, we note the following Lemma.
Lemma 1.
For the SO-DCTS algorithm in (4) in a time-invariant, connected network with initial conditions and , a global consensus is exponentially reached in the following form:
(16)
where denotes the norm of a vector.
Proof.
Let us define the error vector as which can be obtained from , where
(17)
Based on this definition, we see that the error vector results in the following evolution:
(18)
The above equation is valid because and . Then, we have
(19)
which is equivalent to (16). This completes the proof.
Therefore, we see that the convergence rate for the SO-DCTS algorithm in both directed and undirected networks is determined by the spectral radius of .
4. Convergence Region and Optimal Convergence Rate for So-Dcts Algorithm in Undirected Networks
In this section, we investigate more specific convergence results (i.e., the convergence region and optimal convergence rate) for the SO-DCTS algorithm in undirected networks. Without loss of generality, we assume that and are real values, and .
4.1. Convergence Region for So-Dcts Algorithm in Undirected Networks
From Theorem 2, we know that when , the SO-DCTS algorithm in an undirected network can achieve average consensus asymptotically. Let us define the convergence region to satisfy . After some algebraic derivations (outlined in Appendix A), the convergence region for the SO-DCTS algorithm in undirected networks is
(20)
where , and .
The convergence region of the SO-DCTS algorithm in undirected networks is shown in Figures 1 and 2 using a three-dimensional and two-dimensional perspective, respectively. We see that compared to the FO-DCTS algorithm where the range of the step size is , the range of in the SO-DCTS approach increases to .
Figure 1
Convergence region for the SO-DCTS algorithm in undirected networks: three-dimensional view.
Figure 2
Convergence region for the SO-DCTS algorithm in undirected networks: two-dimensional view.
×
×
4.2. Optimal Convergence Rate for So-Dcts Algorithm in Undirected Networks
Next, we investigate the fastest convergence rate of the SO-DCTS algorithm based on and . Recall that in the FO-DCTS algorithm, the constant step size which minimizes convergence time is given as [15]
(21)
Additionally, the convergence rate for is determined by the second largest absolute eigenvalue of the Perron matrix [18], that is,
(22)
As we show next, the convergence rate of the SO-DCTS algorithm can be superior to that of the FO-DCTS algorithm by choosing suitable and . However, as stated in the following lemma, the convergence rate of the FO-DCTS algorithm is faster under some circumstances.
Lemma 2.
For the SO-DCTS algorithm in (4) in a time-invariant, connected, undirected network with initial conditions and in (20), if , the convergence rate of the SO-DCTS algorithm is less than that of the FO-DCTS algorithm with the optimal constant step size in (21).
The proof of this lemma is omitted here since it can be readily extended from the following result. Consider two real values and with , then . Thus, we have , which implies .
Based on the above lemma, we see that there may exist possible choices of and (e.g., when ) such that the convergence rate of the SO-DCTS method is faster than the FO-DCTS algorithm. To see this, we formulate the following spectral radius minimization problem to find the optimal and for the SO-DCTS algorithm:
(23)
Using the steps outlined in Appendix B, the optimal and to minimize (23) can be obtained as
(24)
It is worth noting that . Recall that the convergence rate for the SO-DCTS algorithm in undirected networks is determined by the spectral radius of , that is,
(25)
We see that and only when . Thus, we have the following theorem for the convergence rate of the SO-DCTS algorithm.
Theorem 3.
For the SO-DCTS algorithm in (4) in a time-invariant, connected, undirected network with initial conditions and in (20), there exists a pair of and such that the convergence rate of the SO-DCTS algorithm is greater than or equal to that of the FO-DCTS algorithm with the optimal constant step size in (21).
5. So-Dcts Algorithm with Gaussian Delay in Undirected Networks
In this section, we investigate the convergence properties of the SO-DCTS algorithm in undirected networks when there is both deterministic and random (Gaussian) delay between network nodes during local time information exchange. In [19], we motivate why the Gaussian assumption is appropriate to model the undeterministic timing differences between nodes exchanging either MAC layer or physical layer timing information. We do not reiterate those arguments here but rather present convergence results for the SO-DCTS algorithm when such timing differences exist. We have separately examined the performance of the SO-DCTS algorithm considering alternate delay distributions, for example, exponential delay distribution [20]. Results show similar performance bounds as those presented in this paper for the Gaussian assumption. For this reason, we constrain our discussion here to the more common Gaussian delay model.
With Gaussian delay, the timing update rule of the SO-DCTS algorithm at each node is given as
(26)
where ; is a constant (deterministic) delay; is the distance between node and ; is light speed (thus, is the propagation delay between nodes and ); are independent identical distributed (i.i.d) Gaussian random variables, with zero mean and variance . Local time information exchange between node and under this delay model is shown in Figure 3.
Figure 3
SO-DCTS algorithm with Gaussian delay during local time information exchange.
×
The SO-DCTS algorithm in (26) can be rearranged as
(27)
where .
Let us define the noise vector . Based on this definition, the evolution of SO-DCTS algorithm in (27) can be written as
(28)
We now define and , where . Then, the noise vector in (28) is given as .
Let us additionally define . Then, (28) can be rewritten as
(29)
Recall that for undirected networks, the average value in each iteration is . Thus, the mean and variance of the average value are given in the following lemma.
Lemma 3.
For the SO-DCTS algorithm in (28), the mean and variance of the average value are given as
(30)
The proof of this lemma is straightforward and thus omitted from this paper. It can be seen that as iteration time increases, both mean and variance in (30) increase linearly with the time index , that is, as the algorithm evolves. Furthermore, the variance of increases linearly with the variance of the random Gaussian delay, . As we will see in our numerical results, although the average value grows linearly with iteration time when there is Gaussian delay in the network, an average consensus may still be achievable under certain network topologies.
5.1. Expectation and Second Central Moment of Error Vector
In order to understand the convergence property of SO-DCTS algorithm with Gaussian delay, we first quantify the overall impact of uncertainty by computing the first two moments of the disagreement vector.
With Gaussian delay, we see that the error vector results in the following evolution:
(31)
where and . Then, we have the following lemma.
Lemma 4.
For the SO-DCTS algorithm in (28), the expectation of the error vector is given by
(32)
where
The proof of this lemma is straightforward and thus omitted from this paper.
Let us define the second central moment of the error vector as and the covariance matrix of the error vector as . It is worth mentioning that , where denotes the trace of a matrix. Additionally, let us denote the covariance matrix of as which is given as
(33)
Given these definitions, we next note Lemma 5.
Lemma 5.
For the SO-DCTS algorithm in (28), the covariance matrix of the error vector is given as
(34)
and the second central moment of the error vector is given as
(35)
The proof of this lemma is similar to [19] and thus omitted from the paper.
5.2. Asymptotic Expectation of Global Synchronization Error
Using Lemma 4, we see that the steady state of expectation of the error vector is
(36)
The above equation holds because . Before we investigate the convergence property of SO-DCTS algorithm with Gaussian delay, we give the following lemma for block matrix inversion.
lemma 5.4.
Consider matrices , , , and , when and are nonsingular, then [16]
(37)
Based on this lemma, the steady state of error vector is
(38)
where and . The above equation is valid because , which implies , which in turn implies . Specifically, we see that the eigenvalues of are and Additionally, the steady state of the disagreement vector is upper half of the vector , that is,
(39)
For this , we can show the following theorem.
Theorem 4.
In an undirected network with fixed connected topology, in (39) is a constant vector independent of the constant values of and .
Proof.
Let us denote the eigenvectors of as . It is easy to check that the eigenvector corresponding to is . in (39) can thus be rewritten as
(40)
Therefore, does not depend on and . This completes the proof.
Thus, for constants and , the steady state of the expectation of the disagreement vector is a constant vector regardless of and . In other words, in an undirected network with fixed topology, the expectation of global synchronization error is the same regardless of the speed of synchronization. We observed the same phenomena in the FO-DCTS algorithm with Gaussian delay [19]. Let us now define the asymptotic expectation of pair-wise synchronization error as
(41)
Hence, the maximum asymptotic expectation of the global synchronization error between any two nodes is Then, we have the following definition.
Definition 1.
A connected network is called "average consensus achievable with tolerable synchronization error" if the maximum asymptotic expectation of the global time synchronization error is less than a predefined threshold when applying the SO-DCTS algorithm in (28), that is, when .
A network is called "time delay balanced network" if the delay
(42)
or equivalently, .
5.3. Asymptotic Mean Square Time Synchronization Error
Using Lemma 5, the steady state of the second central moment of the error vector is
(43)
where . Note that satisfies the following condition:
(44)
Let us denote the covariance matrix and second central moment of the disagreement vector as and , respectively. We see that
(45)
Therefore, as , the steady state of second central moment of disagreement vector is
(46)
We now define the asymptotic mean square time synchronization error as
(47)
which indicates the amount of error by which the updated time at each node differs from the average value over all nodes. We see that
(48)
6. Simulation Results
In the following simulation results, we assume that the initial time offset of node is , where microseconds unless otherwise stated (trends similar to the ones noted below were observed when initial time offsets between nodes were arbitrary (e.g., when they were uniformly distributed over [0,T]). We use this fixed offset assumption here for comparison purposes).
6.1. Structured Networks
In our simulations, we examine the convergence performance of the FO-DCTS and SO-DCTS algorithms for several structured, undirected networks. Specifically, we study the following network topologies.
Definition 3.
"A Ring Network with Equal Distance ": A ring network is a network that consists of a single cycle. The ring network with equal distance is a ring network that has nodes, edges, and for and .
Definition 4.
"A Path Network with Equal Distance ": A path network is a network that consists of edge set . The path network with equal distance is a path network that has nodes, edges and for and .
Definition 5.
"A Star Network with Equal Distance ": A star network is a network that consists of edge set. The star network with equal distance is a star network that has nodes, edges, and for and .
Figure 4 shows examples of these networks: a ring network , a path network , and a star network . Based on Definition 2, we see that is a "time delay balanced network" and . We now explore the convergence properties of the SO-DCTS algorithm for these structured networks via simulation.
Figure 4
Structured networks: (a), (b) , (c) .
×
Optimal Convergence Rate
First we compare the convergence speeds of the SO-DCTS and FO-DCTS algorithms for the above structured networks assuming that the convergence rate is defined as , and there is no Gaussian delay between nodes. Table 1 gives the numerical values of the optimal convergence rate for the SO-DCTS and FO-DCTS algorithms under the , , and topologies. As expected, the SO-DCTS algorithm converges faster than the FO-DCTS algorithm in all three cases. Specifically, we see that the optimal convergence rate of the SO-DCTS algorithm is nearly twice as that of the FO-DCTS algorithm for all three types of networks.
Table 1
Numerical results comparing convergence rates of FO-DCTS and SO-DCTS algorithms in , , .
FO-DCTS Alg.
0.9267
0.0762
0.9808
0.0194
0.8824
0.1252
SO-DCTS Alg.
0.8634
0.1469
0.9623
0.0384
0.7895
0.2364
Convergence Properties of So-Dcts Algorithm with Gaussian Delay
In our simulations of the SO-DCTS algorithm with Gaussian delay, we assume microseconds and the optimal values of and from (24). The simulation results and the asymptotic mean square time synchronization errors for the , , and networks are shown in Figure 5. For each network topology, the asymptotic mean square time synchronization error is calculated from (48). It can be seen that as time index increases, mean square time synchronization error approaches the steady-state value when utilizing SO-DCTS algorithm with Gaussian delay. Additionally, we see that the SO-DCTS algorithm performs poorest in a path network where it has the largest value of and the slowest convergence speed. This is not surprising since in such networks information flow from node 1 to node requires hops.
Table 2 summarizes the asymptotic results of the SO-DCTS algorithm for structured networks. As expected, the maximum asymptotic expectation of global time synchronization error for is 0 since is a time delay balanced network. Furthermore, the SO-DCTS algorithm in has the largest because of its highly unbalanced time delay structure. It is worth mentioning that the SO-DCTS algorithm in star networks has relatively small values of and . In fact, the SO-DCTS algorithm for a star network can be seen as a type of centralized time synchronization algorithm in which a root node determines and propagates the average of local time information of all other nodes in the network.
In Figure 6, we show the asymptotic value of as a function of the number of nodes in these structured networks. It can be seen that when using the optimal and , the asymptotic mean square time synchronization error for a star network is nearly constant as the number of nodes increases. However, is an increasing function of the number of nodes for both path and ring networks.
Table 2
Asymptotic results for the SO-DCTS algorithm in structured networks with Gaussian delay.
0
35
8.75
305.8075
13329
84.2996
Figure 5
as a function of the iteration time index for the SO-DCTS algorithm in structured networks (, , ) with Gaussian delay.
Figure 6
as a function of the number of nodes for the SO-DCTS algorithm in structured networks with Gaussian delay.
×
×
6.2. Random Networks
We also present here simulation results for a random network comprised of nodes that were randomly generated with uniform distribution over a unit square kilometer; two nodes were assumed connected if the distance between them was less than , a predefined threshold. One realization of such a network with 16 nodes is shown in Figure 7. We assume that the average distance between two nodes is .
Figure 7
Random network with 16 nodes used to obtain simulation results in Figure 9.
×
Figure 8 shows the simulation results for the convergence rates of the FO-DCTS and SO-DCTS algorithms in random networks with 256 nodes when without Gaussian delay between network nodes. Specifically, we plot the mean square time synchronization error (defined as ). In simulating random networks, we average results over 5000 network realizations. To obtain these results, we chose for the FO-DCTS algorithm and and for the SO-DCTS algorithm. In Figure 8, we observe that the optimal convergence rate of the SO-DCTS algorithm is faster than that of the FO-DCTS algorithm. In addition to the results shown here, we ran this simulation setup for various realizations of random networks, assuming both and a smaller network with . Overall, the results show a similar trend, that is, the convergence rate of the SO-DCTS algorithm exceeds the FO-DCTS algorithm.
Figure 8
Evolutions of the FO-DCTS and SO-DTS algorithms in random network with 256 nodes whenwithout Gaussian delay between network nodes.
×
Figure 9 shows the simulation results when the SO-DCTS algorithm is implemented in a random network of Figure 7 assuming Gaussian delay between network nodes. As expected, we see here that an asymptotic global synchronization error persists between some pairs of nodes, that is, microseconds for this random network. If we specify a threshold to be greater than or equal to this , we call this network as "average consensus achievable with tolerable synchronization error" as described in Definition 1.
Figure 9
Evolution of the average disagreement of the SO-DCTS algorithm in random network (see Figure 7) with Gaussian delay between network nodes.
×
7. Conclusions
In this paper, we propose a novel discrete-time SO-DCTS algorithm to address the global timing synchronization problem in wireless sensor networks. We analyze several important convergence characteristics of the SO-DCTS algorithm for directed and undirected networks. Additionally, we investigate the convergence region and optimal convergence rate of the SO-DCTS algorithm in undirected networks and claim that the optimal convergence rate of the SO-DCTS algorithm is superior to that of the FO-DCTS algorithm under an appropriate algorithm design. Furthermore, we investigate the asymptotic expectation and mean square synchronization error of the SO-DCTS algorithm when there is Gaussian delay between network nodes. In the future, we intend to investigate the effects of skew, link failure, and other practical conditions when utilizing the SO-DCTS algorithm in wireless sensor networks.
Appendices
A. Convergence Region for So-Dcts Algorithm in Undirected Networks
Let us denote the pairs of eigenvalues of corresponding to as and , that is,
(A1)
Now, we examine the convergence region for the SO-DCTS algorithm based on conditions , and .
Case 1.
When and are real values: in this case, we have that is,
(A2)
In the following, we assume that unless otherwise stated.
(1)First, we consider the convergence region for . After some manipulations, we can show that the convergence region is
(A3)
(2)Then, we consider the convergence region for which is given as
(A4)
Combining the convergence region for and with (A.2), the convergence region for this case is
(A5)
Case 2.
When and are complex values: In this case, we have , that is,
(A6)
Here, and . Thus, we only need to examine the convergence region for . In order to satisfy the conditions, we have
(1) the real part of should be less than 1, that is, , then we have
(A7)
(2)the imaginary part of should be less than 1, that is, , then we have
(A8)
(3)the absolute value of should be less than 1, that is, , then we have
(A9)
Combining the above results, the convergence region for this case is
(A10)
By taking the union of in (A.5) and in (A.10) and considering the increasing order of , the convergence region for the SO-DCTS algorithm in (20) is obtained.
B. Solution for Minimization Problem
Here, we give a sketch solution to the spectral radius minimization problem in (23). Since , the optimization problem is equivalent to minimize
(B1)
(1)First, we find the optimal given to minimize (B.1). Here, we consider four different cases depending on whether are real values or complex values. After algebraic derivations, we can show that the minimum of (B.1) given can be achieved when and are real values and and are complex values. Additionally, the following equation should be satisfied:
(B2)
Thus, we have
(B3)
(2)Next, we find the optimal given to minimize (B.1). Again, this can be achieved by taking . Then, we have the following relationship between and :
(B4)
Combining (B.3) with (B.4), we get (24).
Acknowledgment
This work was supported in part by research grants from Thales Communications, Inc., Md, USA, and the National Science Foundation.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
is given as
is the local time at node
during iteration
;
is the set of neighboring nodes that can communicate reliably with node
;
is a constant step size;
is a constant for each iteration. We assume that initial conditions of the SO-DCTS algorithm are
, where
is initial time offset for node
. It is worth mentioning that when
, the SO-DCTS algorithm reduces to the FO-DCTS algorithm.
, consisting of a set of
nodes
and a set of edges
. Each edge is denoted as
where
and
are head and tail of the edge
, respectively. In a wireless sensor network, the presence of an edge
indicates that node
can communicate with node
reliably. We assume here a connected graph; that is, there exists a directed path connecting any pair of distinct nodes in the network. Throughout our discussion, we assume a time-invariant and connected network unless otherwise stated.
as the adjacency matrix of
such that
(denoted as
and
, resp.,) are given as
, and
Specifically,
is also equal to the number of neighbors of node
from which it can receive information reliably, that is,
.
be the graph Laplacian matrix of
which is defined as
, where
is the degree matrix of
. Given this matrix
, we can show that
, where
, and
. In particular, for a connected graph, the rank of
is
. Furthermore, for a balanced directed network, the in-degree and out-degree of a node are equal, that is,
, thus we see that
.
indicates that nodes
and
can communicate with each other reliably. Under this condition, we can also show that
. Additionally, in this case,
is a symmetric positive semidefinite matrix (implying that its eigenvalues are nonnegative), and its eigenvalues can be arranged in increasing order as
[14].
. The evolution of the SO-DCTS algorithm in (1) can be written as
, where
. Here,
denotes the
identity matrix.
. Define
and
is the left eigenvector of
associated with
. When
, a global consensus is achieved asymptotically, or equivalently,
denotes the spectral radius of a matrix.
. Then, the SO-DCTS algorithm in (4) can be rewritten as
are
has only one eigenvalue
. Then, we know that
has two eigenvalues
and
. Additionally, the eigenvalues of
agree with those of
except that
is replaced by
[16]. Since
, we see that the eigenvalues of
stay inside the unit circle except for
. Thus, we have
is the Jordan form matrix corresponding to eigenvalues
[16],
and
are left and right eigenvectors of
corresponding to
, respectively, and
. In particular,
and
. Plugging
and
into (10) and considering the SO-DCTS algorithm in (7), we have
. When
, an average consensus is achieved asymptotically, or equivalently,
and
. The rest of proof is similar to that of Theorem 1 and thus omitted here.
, which is similar to the FO-DCTS algorithm [17].
. In the SO-DCTS algorithm, this value remains invariant during each iteration since
, which indicates the difference between the updated times and the global consensus times of the network nodes. Then, the evolution of the disagreement vector is obtained as
and
, a global consensus is exponentially reached in the following form:
denotes the
norm of a vector.
which can be obtained from
, where
and
. Then, we have
.
and
are real values, and
.
, the SO-DCTS algorithm in an undirected network can achieve average consensus asymptotically. Let us define the convergence region
to satisfy
. After some algebraic derivations (outlined in Appendix A), the convergence region for the SO-DCTS algorithm in undirected networks is
, and
.
is
, the range of
in the SO-DCTS approach increases to
.
and
. Recall that in the FO-DCTS algorithm, the constant step size
which minimizes convergence time is given as [15]
is determined by the second largest absolute eigenvalue of the Perron matrix [18], that is,
and
. However, as stated in the following lemma, the convergence rate of the FO-DCTS algorithm is faster under some circumstances.
and
in (20), if
, the convergence rate of the SO-DCTS algorithm is less than that of the FO-DCTS algorithm with the optimal constant step size in (21).
and
with
, then
. Thus, we have
, which implies
.
and
(e.g., when
) such that the convergence rate of the SO-DCTS method is faster than the FO-DCTS algorithm. To see this, we formulate the following spectral radius minimization problem to find the optimal
and
for the SO-DCTS algorithm:
and
to minimize (23) can be obtained as
. Recall that the convergence rate for the SO-DCTS algorithm in undirected networks is determined by the spectral radius of
, that is,
and
only when
. Thus, we have the following theorem for the convergence rate of the SO-DCTS algorithm.
and
in (20), there exists a pair of
and
such that the convergence rate of the SO-DCTS algorithm is greater than or equal to that of the FO-DCTS algorithm with the optimal constant step size in (21).
is given as
;
is a constant (deterministic) delay;
is the distance between node
and
;
is light speed (thus,
is the propagation delay between nodes
and
);
are independent identical distributed (i.i.d) Gaussian random variables, with zero mean and variance
. Local time information exchange between node
and
under this delay model is shown in Figure 3.
.
. Based on this definition, the evolution of SO-DCTS algorithm in (27) can be written as
and
, where
. Then, the noise vector in (28) is given as
.
. Then, (28) can be rewritten as
. Thus, the mean and variance of the average value
are given in the following lemma.
are given as
, that is, as the algorithm evolves. Furthermore, the variance of
increases linearly with the variance of the random Gaussian delay,
. As we will see in our numerical results, although the average value
grows linearly with iteration time when there is Gaussian delay in the network, an average consensus may still be achievable under certain network topologies.
results in the following evolution:
and
. Then, we have the following lemma.
is given by
and the covariance matrix of the error vector as
. It is worth mentioning that
, where
denotes the trace of a matrix. Additionally, let us denote the covariance matrix of
as
which is given as
is given as
is given as
is
. Before we investigate the convergence property of SO-DCTS algorithm with Gaussian delay, we give the following lemma for block matrix inversion.
is
and
. The above equation is valid because
, which implies
, which in turn implies
. Specifically, we see that the eigenvalues of
are
and
Additionally, the steady state of the disagreement vector
is upper half of the vector
, that is,
, we can show the following theorem.
in (39) is a constant vector independent of the constant values of
and
.
as
. It is easy to check that the eigenvector corresponding to
is
.
in (39) can thus be rewritten as
does not depend on
and
. This completes the proof.
and
, the steady state of the expectation of the disagreement vector is a constant vector regardless of
and
. In other words, in an undirected network with fixed topology, the expectation of global synchronization error is the same regardless of the speed of synchronization. We observed the same phenomena in the FO-DCTS algorithm with Gaussian delay [19]. Let us now define the asymptotic expectation of pair-wise synchronization error as
Then, we have the following definition.
when applying the SO-DCTS algorithm in (28), that is, when
.
.
. Note that
satisfies the following condition:
and
, respectively. We see that
, the steady state of second central moment of disagreement vector is
nodes. We see that
is
, where
microseconds unless otherwise stated (trends similar to the ones noted below were observed when initial time offsets between nodes were arbitrary (e.g., when they were uniformly distributed over [0,T]). We use this fixed offset assumption here for comparison purposes).
": A ring network is a network that consists of a single cycle. The ring network with equal distance is a ring network that has
nodes,
edges, and
for
and
.
": A path network is a network that consists of edge set
. The path network with equal distance is a path network that has
nodes,
edges and
for
and
.
": A star network is a network that consists of edge set
. The star network with equal distance is a star network that has
nodes,
edges, and
for
and
.
, a path network
, and a star network
. Based on Definition 2, we see that
is a "time delay balanced network" and
. We now explore the convergence properties of the SO-DCTS algorithm for these structured networks via simulation.
, (b)
, (c)
.
, and there is no Gaussian delay between nodes. Table 1 gives the numerical values of the optimal convergence rate for the SO-DCTS and FO-DCTS algorithms under the
,
, and
topologies. As expected, the SO-DCTS algorithm converges faster than the FO-DCTS algorithm in all three cases. Specifically, we see that the optimal convergence rate of the SO-DCTS algorithm is nearly twice as that of the FO-DCTS algorithm for all three types of networks.
,
,
.
microseconds and the optimal values of
and
from (24). The simulation results and the asymptotic mean square time synchronization errors for the
,
, and
networks are shown in Figure 5. For each network topology, the asymptotic mean square time synchronization error
is calculated from (48). It can be seen that as time index increases, mean square time synchronization error approaches the steady-state value when utilizing SO-DCTS algorithm with Gaussian delay. Additionally, we see that the SO-DCTS algorithm performs poorest in a path network where it has the largest value of
and the slowest convergence speed. This is not surprising since in such networks information flow from node 1 to node
requires
hops.
is 0 since
is a time delay balanced network. Furthermore, the SO-DCTS algorithm in
has the largest
because of its highly unbalanced time delay structure. It is worth mentioning that the SO-DCTS algorithm in star networks
has relatively small values of
and
. In fact, the SO-DCTS algorithm for a star network can be seen as a type of centralized time synchronization algorithm in which a root node determines and propagates the average of local time information of all other nodes in the network.
as a function of the number of nodes in these structured networks. It can be seen that when using the optimal
and
, the asymptotic mean square time synchronization error for a star network is nearly constant as the number of nodes increases. However,
is an increasing function of the number of nodes for both path and ring networks.
as a function of the iteration time index for the SO-DCTS algorithm in structured networks (
,
,
) with Gaussian delay.
as a function of the number of nodes for the SO-DCTS algorithm in structured networks with Gaussian delay.
nodes that were randomly generated with uniform distribution over a unit square kilometer; two nodes were assumed connected if the distance between them was less than
, a predefined threshold. One realization of such a network with 16 nodes is shown in Figure 7. We assume that the average distance between two nodes is
.
without Gaussian delay between network nodes. Specifically, we plot the mean square time synchronization error (defined as
). In simulating random networks, we average results over 5000 network realizations. To obtain these results, we chose
for the FO-DCTS algorithm and
and
for the SO-DCTS algorithm. In Figure 8, we observe that the optimal convergence rate of the SO-DCTS algorithm is faster than that of the FO-DCTS algorithm. In addition to the results shown here, we ran this simulation setup for various realizations of random networks, assuming both
and a smaller network with
. Overall, the results show a similar trend, that is, the convergence rate of the SO-DCTS algorithm exceeds the FO-DCTS algorithm.
without Gaussian delay between network nodes.
microseconds for this random network. If we specify a threshold
to be greater than or equal to this
, we call this network as "average consensus achievable with tolerable synchronization error" as described in Definition 1.
corresponding to
as
and
, that is,
, and
.
and
are real values: in this case, we have
that is,
unless otherwise stated.
. After some manipulations, we can show that the convergence region is
which is given as
and
with (A.2), the convergence region
for this case is
and
are complex values: In this case, we have
, that is,
and
. Thus, we only need to examine the convergence region for
. In order to satisfy the conditions, we have
should be less than 1, that is,
, then we have
should be less than 1, that is,
, then we have
should be less than 1, that is,
, then we have
for this case is
in (A.5) and
in (A.10) and considering the increasing order of
, the convergence region for the SO-DCTS algorithm in (20) is obtained.
, the optimization problem is equivalent to minimize
given
to minimize (B.1). Here, we consider four different cases depending on whether
are real values or complex values. After algebraic derivations, we can show that the minimum of (B.1) given
can be achieved when
and
are real values and
and
are complex values. Additionally, the following equation should be satisfied:
given
to minimize (B.1). Again, this can be achieved by taking
. Then, we have the following relationship between
and
:
