# Clock Synchronization in Wireless Sensor Networks: A New Model and Analysis Approach Based on Networked Control Perspective

Authors: Wang Ting; Cai Chun-yang; Guo Di; Tang Xiao-ming; Wang Heng
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Motivated by the importance of the clock synchronization in wireless sensor networks (WSNs), this paper proposes a new research approach and model approach, which quantitatively analyzes clock synchronization from the perspective of modern control theory. Two kinds of control strategies are used as examples to analyze the effect of the control strategy on clock synchronization from different perspectives, namely, the single-step optimal control and the LQG global optimal control. The proposed method establishes a state space model for clock relationship, thus making dimension extension and parameter identification easier, and is robust to changes under the condition of node failures and new nodes. And through the design of different control strategies and performance index functions, the method can satisfy various requirements of the synchronization precision, convergence speed, energy consumption and the computational complexity, and so on. Finally, the simulations show that the synchronization accuracy of the proposed method is higher than that of the existing protocol, and the former convergence speed of the synchronization error is faster.


---

## Body

## 1. Introduction

In the past years, significant attention has been directed towards wireless sensor networks (WSNs) technologies with a promising potential to be applied in various fields and high application value in national defense, environment monitoring, home automation, transportation, and so forth [1–4]. However, because of the imperfections of the clock oscillator, environmental changes, and delay, the clock of nodes is hard to be synchronized. And being the important technical support for WSNs, a common time frame is required in most of the applications and algorithms, such as data fusion, power management, and node location [5–7]. So the clock synchronization between nodes becomes an urgent problem at present.The issue of clock synchronization was proposed more than ten years ago. Over the years, some researchers made some researches on clock synchronization and gained some research results, such as TPSN [8], RBS [9], and FTSP [10]. Other researches develop the classical protocols. For example, [5, 11] improves the performance of TPSN. Tiny-Sync and Mini-Sync [12] reduce complexity on the basis of TPSN, but with long convergence time. These protocols adopt traditional method to estimate the clock skew and clock offset. In [13], clock synchronization of WSNs is modeled and analyzed by following a signal processing viewpoint in various network delay distributions. At the same time, the large-scale wireless sensor networks become the trend of future research and development, and the network structure and communication method become more varied and complicated. The existing synchronization protocols have significant limitations for expanding network scale and adapting to the variability. In addition, the latest researches developed a distributed algorithm which is easy to expand the network size. Reference [14] modeled the clock synchronization problem as a state space model and presented a distributed Kalman filter algorithm for the clock parameters of the entire network node tracking (the clock skew and clock skew). The model is easy to expand the network size, is robust to changes in network connectivity, and can maintain long-term precision of clock parameters. Reference [15] put forward a fully distributed algorithm for joint clock skew and clock skew estimation based on belief propagation. The algorithm estimates clock skew and clock skew in a completely distributed and asynchronous way and does not require any centralized information processing or coordination, so it is scalable with network size. As WSNs is introduced into the network control system with accompanied uncertain factors, a growing number of researches focus on control-included wireless sensor networks system, such as [3, 16–20], but a basic core problem in WSNs, the clock synchronization, as a fundamental question for sensing control and data scheduling of wireless sensor networks control system, has yet to be solved. Many researches based on control assume the clock synchronization has already been realized. As a result, control-included clock synchronization issue in WSNs has not been paid enough attention, thus, meriting the efforts to further explore and research.With the fast development of the large-scale integration technology and the microelectronic mechanical system, the integration of data acquisition, wireless communication, and computing ability on the same tiny devices is not a technical problem. In the literature [21], it is assumed that sensors have a certain computation capacity. And with the rapid development of technology, it is reasonable that the author assumes that sensor nodes not only have the ability of wireless communication and data acquisition but also have a certain computation and processing capacity. That is to say, for analysis of clock synchronization issue, sensor nodes also have the function of controller. Therefore, the control is executed in the local node.The existing literatures of network control theory have carried on a large number of early-stage studies of network control theory model which proved to be effective. Because of the uncertain factors of the introduced wireless network, namely, packet loss, delay, and so forth, together with the classic control theory, the random characteristics of communication channel should also be taken into consideration, which brings great challenge for studying the stability of dynamic system. Reference [22] devoted to looking for a certain threshold of the packet arrival rate above which, the expected value of the error covariance matrix, becomes bounded as time goes to infinity; [21] assumed some big margin of errors in the convergence and analyzed the stability of estimation from the perspective of probability; [23] considered the presence of observation packet loss and showed that error variance of the minimum mean square error of estimate is less than that of the linear minimum mean square error estimation and the former has wider application. Reference [17] considered control and state estimation problems under the unreliable network. The conclusion is in the TCP; like protocols, controller and estimator can be designed independently, and there is a network threshold, below which the optimal controller fails to stabilize the system; [16] designed two kinds of control schemes, a centralized control and a distributed control, for wireless network control system; [18] further compared the two kinds of control schemes, and concluded that the distributed control is more roust against packet loss and has lower computational complexity than the centralized control. Comparing the above control theory models, it is found that the clock synchronization issue can be modeled as a state space model. Reference [14] also modeled the clock synchronization problem as a state space model, presented a distributed Kalman filter algorithm for the clock parameters of the entire network node tracking. It also verifies that modeling the clock synchronization problem as a state space model is feasible, even has the incomparable advantage that it’s easy to expand to the distributed structure, over traditional estimation of the clock parameters. Differing from the view of research in [14], this paper, by using the clock relationships based on two-way message exchange mechanism, establishes a clock synchronization state space model, trying to analyze the clock synchronization issue from the perspective of the control theory.The clock synchronization method based on the control proposed in this paper can be described as follows: establish the clock synchronization state space model; and on this basis, introduce control; quantitatively analyze the clock synchronization issue by control strategy. Because of using two-way clock message exchange mechanism, and through contrasting with the network control theory, it is found that the clock synchronization control is conducted in the local. In this way, when the clock synchronization issue is analyzed in WSNs, there exists observation packet loss, but do not do control packet loss. However, the presence of observation packet loss will inevitably affect the performance of the system and even make the system unstable. The stability of packet loss has been strictly discussed and proved in [17, 20, 21, 24], and the bound of packet loss on the premise of guaranteeing stability of system has been gained. So, the author is able to quote packet loss limit and relevant conclusions in the presence of observation packet loss, analyzing the clock synchronization issue in WSNs.In this paper, the major contributions of the clock synchronization method based on the control are as follows. Firstly, the method establishes a state space model based on control, quantitatively analyzing the clock synchronization issue from the perspective of the control theory; moreover, through optimization control remedying error of estimation, the precision of clock synchronization is improved; then, when the network increases or decreases the number of nodes and even expands the scale of the network, system matrix dimensions can be extended to meet the change of the number of nodes. Therefore, in the context of large-scale network and variable network structure, the method has certain scalability; last but not least, in terms of performance requirements, we can reasonably design different control strategies or performance indexes to meet different requirements for synchronous performance. It not only can satisfy the requirement of synchronization precision but also can satisfy the various performance requirements of the convergence speed, energy consumption, and the complexity.The paper is organized as the following. In Section2, the author introduces the clock model, and on this basis, establishes the clock synchronization state space model between two nodes; and then control is introduced into the model; a clock synchronization state space model based on control can be gained; finally, in the presence of packet loss, the state space model is modified. Section 3 presents the clock synchronization control strategy. According to the separation principle, the section discusses the estimation and the control, respectively. Meanwhile on the control part, the author uses two kinds of control strategies as examples to analyze the effect of the control strategy on clock synchronization. In Section 4, a variety of simulation results are shown to assess the feasibility and effectiveness of our clock synchronization control method. Finally, the paper concludes with a summary of the results and gives directions for future work.


## 2. System Modeling

### 2.1. Clock Model

In a network every individual sensor has its own clock. As Figure1, ideally, the clock of a sensor node can be described as follows: C(t)=t, where t stands for the ideal or reference time. However, due to the imperfections of the clock oscillator and the effect of the environment, a clock will drift away from the ideal time even if it is initially rational tuned. In general, the clock function of the ith node is modeled as
(1)Ci(t)=θ+f·t,
where θ and f represent clock offset (phase difference) and clock skew (frequency difference), respectively.Figure 1
Clock model of sensor nodes.Even though in WSNs the number of nodes is thousands, or even more, the paper firstly uses two nodes as a springboard for modeling and analyzing in detail. After strictly discussing two nodes, we extend to many nodes. In this case, we assume that there are only two nodes in WSNs: NodeA and Node B. They drift away from the ideal time due to the changes of external environment temperature and the imperfections of their own clock oscillators. A graphical representation of the relationship is illustrated in Figure 1. From (1), the clock relationship between two nodes, Node A and Node B, can be represented by
(2)CB(t)=θAB+fAB·CA(t),
where θAB and fAB stand for the relative clock offset and skew between Node A and Node B, respectively. Obviously, if two clocks are perfectly synchronized, θAB=0, fAB=1. Otherwise, suppose Node B is the reference node, the task of clock synchronization is to estimate θAB, fAB such that Node A can adjust its own clock or translate its time message to Node B when necessary. If there are L nodes in the network, the global network synchronization requires Ci(t)=Cj(t) for all i,j=1,…,L or all the relative clock offsets and skews are estimated with respect to a reference node.


### 2.2. The Challenge

Assume NodeA needs to be synchronized to reference Node B. When Node A sends its current time to Node A, if there is absolutely no delay in the message delivery, Node A can immediately know the difference between its clock and that of Node B. So only modifying own clock of Node A, Node A can be synchronized to Node B. Unfortunately, in a real wireless network, various delays affect the message delivery, making clock synchronization much more difficult than it seems to be. In general, a series of timing message transmissions are used to estimate the relative clock skews and offsets among nodes. In some sense, clock synchronization in WSNs can be regarded as the process of removing the effects of random delays from the timing message transmissions sent across wireless channels. The various delays present in a message delivery include the following components [10, 13]:(1)
send time: the time is used to build the message and submit the send request to the medium access control (MAC) layer on the sender. This delay is highly variable due to the system call overhead of the operating system and the current processor load;(2)
access time: after reaching the MAC layer, the waiting time for accessing the channel. This is the highly variable depending on the specific MAC protocol and the current network load;(3)
transmission time: the time spent in transmitting a message at the physical (PHY) layer of the sender. The delay is determined by the message length and sending rate;(4)
propagation time: the actual time for a message to be transmitted from the sender to the receiver in a wireless channel. It just depends on the distance between two nodes;(5)
reception time: the time required for receiving a message at the PHY layer of the receiver, which corresponds to the transmission time;(6)
receive time: the time to process the received message at the application layer of the receiver.The above delay components can be classified into two kinds: deterministic delay (fixed delay) and stochastic delay (variable delay). The variable portion depends on various network parameters (e.g., network status and traffic). Therefore, no single delay model can be found to fit for every case. Probability density function (PDF) models that have been proposed for modeling random delays in wireless networks include Gaussian, Exponential, Gamma, Weibull, and log-normal [25–27]. In a word, we have constructed that the equation described the clock of nodes and analyzed the clock relations between two nodes which need to keep the clock synchronization. If Node A needs to be synchronized to reference Node B, we need to estimate the skews and offsets between nodes and at the same time, considering the delay of message exchange, we need to know it.


### 2.3. Clock Synchronization State Space Model

The above has set up the clock model of two nodes; this section is specific to establish model of the clock synchronization between two nodes. Referencing TPSN synchronization protocol, we also adopt the classical mechanism [7, 8, 13] of two-way message exchange between two adjacent nodes, which is depicted in Figure 2. And in this figure, we consider that Node A needs to be synchronized to reference Node B. Assuming timing messages are exchanged N times, in the kth round of message exchange, Node A sends a synchronization message which carries T1,k to Node B at T1,k. Node B achieves that message at T2,k and then replies to Node A at T3,k. The replied message contains both T2,k and T3,k. Finally, Node A gets the replied message at T4,k. Note that T1,k and T4,k are the local clock of Node A, while T2,k and T3,k are the local clock of Node B. After exchanging N times, Node A receives a set of time stamps {T1,k,T2,k,T3,k,T4,k}k=1N. The above procedure can be mathematically modeled as
(3)T2,k=f(T1,k+τ+Xk)+θ,T3,k=f(T4,k-τ-Yk)+θ,
where f and θ denote the relative clock skew and offset of Node A with respect to Node B, respectively, τ is the fixed delay (assume that the fixed delay between two nodes is symmetrical), and Xk and Yk are the random delays in the transmissions from Node A to Node B and from Node B to Node A, respectively. In practice, the random delay is diverse and is described as different distributions according to different judgments and applications including Gaussian, exponential, Gamma, Weibull, and log-normal [13, 25–27]. In this paper, we assume Xk and Yk obey the independent identically distributed Gaussian distribution. According to the central limit theorem, a random sample of size n is drawn from distributions of expected values given by μ and variances given by σ2. When n is large enough, the sampling distribution of sample mean approximatively obeys normal distribution with mean μ and variance σ2/n. If the delay is accumulation result of innumerable independent random process, the delay confirms to the Gaussian delay model. And the test [9] showed that the variable delays can be modeled as Gaussian distributed random variables with 99.8% confidence.Figure 2
Two-way timing message exchange between two nodes.Note that there are two points we need to emphasize. Firstly, fixed delay between two nodes is assumed to be symmetrical. The hypothesis is supported by two reasons. First and foremost, the size of data packet which includes the time message exchange between two nodes is generally equal, and the transmission rate of date packet is the same, so there are identical transmission time and reception time between two nodes. Moreover, propagation time is decided by the distance between two nodes. Suppose that the relative position between two nodes does not change in the process of message exchange, so propagation time remains invariable. Secondly, clock drift (diversification of the clock frequency), which reflects the stability of crystal oscillator, is the second derivative of the clock. So it has little influence on clock, and we may think that clock skew (f) has no obvious changes in one synchronization period. But when it comes from different synchronization periods, clock skew will be different. For example, in period k, consider f=fk, k=0,1,2…, but fk≠fk-1. References [5, 11] presented the statistical signal processing approaches estimating the clock skew under known fixed delay and unknown fixed delay. The approaches adopting signal processing technology, not only apply to the case where the random delay is the Gauss distribution, but also apply to the case where the random delay is the exponential distribution. So the approaches break the constraint of standard statistical estimation and even have some advantages when applied to any delay model. In short, in every time of message exchange process, whichever method is adopted, we have always gotten the unchangeable clock skew in one period.Since the clock skewf can be obtained in the process of message exchange, we can assume that f is known and it is a fixed constant in one synchronization period. Here we notice that f in different synchronization periods is considered to be different. So (3), which only have two unknown parameters, can be transformed into
(4)T2,kf=T1,k+τ+Xk+θf,T3,kf=T4,k-τ-Yk+θf.To present the linear relationship betweenθ and τ, we transform the above equations into state space model:
(5)[T2,kf-T1,kT4,k-T3,kf]=[11f1-1f][τθ]+[XkYk].Equation (5) can be further simplified to
(6)[UkVk]=[11f1-1f][τθ]+[XkYk],
where Uk=(T2,k/f)-T1,k, Vk=T4,k-(T3,k/f).Define(7)xk=[τθ],C=[11f1-1f],yk=[UkVk],υk=[XkYk],so (6) can also be written as
(8)yk=Cxk+υk.Above having been confirmed, in this paper, the random delay obeys independent identically distributed Gaussian distribution, so it is assumed its mean is zero and correlation matrix of the covariance isE[υkυkT]=Rk, which is a diagonal matrix. But xk is unknown; we assume that the present state linearly relates to the state in previous time instance [16, 17, 28]. And because of slow changes, unknown state built a Gauss-Markov dynamic model:
(9)xk=xk-1+ωk-1,
where interference part ωk-1 is modeled as a Gaussian distribution with mean zero and covariance Qk-1, where correlation matrix is E[ωk-1ωk-1T]=Qk-1. Above, the state equation of clock synchronization has been established.Reference [14] modeled the clock synchronization problem as a state space model and presented a distributed Kalman filter algorithm for the clock parameters of the entire network node tracking (the clock skew and clock skew). The model is easy to expand the network size, is robust to changes in network connectivity, and can maintain long-term precision of clock parameters. The state space model established above and the state space model of [14] have similar form, but there are still some differences. (1) In this paper, the state vector is a matrix form about the clock offset and fixed delay and in [14] about the clock skew and accumulated clock offset; (2) in this paper, the measurement model directly considers the clock skew and in [14] the localized timestamp measurement model considers the relationship between the timestamps and the accumulated clock offset; (3) in the paper, we have lots of research work to be done for extending the state model and in [14] the model has be extended to multiple nodes.According to (8) and (9), the picture of clock synchronization process in the kth round of message exchange is shown in Figure 3. This picture is simply described as follows. In the kth round of message exchange, the observation value of the system state is obtained. Through some estimation method, the system state is estimated with the value, and then the logic clock of Node A is adjusted, to achieve the synchronization between Node A and Node B. Seen from the figure, obviously, the system built in the Node A belongs to the closed loop feedback system, but observation value is obtained by exchanging timing message of two nodes.Figure 3
Clock synchronization process of message exchange.The synchronization system, however, is not very stable and is easily affected by noise. Anti-interference ability is poor, and in the presence of packet loss, state estimation is greatly affected by observation value, leading to inaccuracy of the state estimation and affecting the precision of the synchronization.To sum up, we need to find an approach to resolve the above problems. The solution is inspired by [17], which considers control and estimation problems where the sensor signals and the actuator signals are transmitted to various subsystems over a network, where the observation and control packet may be lost, and puts forward a novel theory. In this theory, the architecture of the closed loop system based on TCP-like protocols is shown in Figure 4 [17], where the binary random variables νt and γt indicate whether packets are transmitted successfully or not. The model has a threshold, which affects the network reliability. If it is below the threshold, the best controller will fail to make the system stable. Moreover, the separation principle holds in the model. In other words, the design and analysis of estimator and controller can be separated. As a result, the best control is the linear function of the estimation value.Figure 4
Architecture of the closed loop system over a communication network under TCP-like protocols.The clock synchronization model in this paper is a closed loop feedback system and the observation value is acquired through an unreliable network, so whether it is possible that the clock synchronization is analyzed according to the method of modern control theory or not. Firstly, adding control in the clock synchronization model, we will have a closed loop feedback system with control. Secondly, some control strategies which we should study will weaken the influence of noise and improve the anti-interference ability of synchronization. Even in the rigorous conditions, for example, there are many pocket losses; we also use the control strategy to realize synchronization and guarantee high precision. On the basis of the clock synchronization model built, preliminary model adding control is obtained as shown in Figure5.Figure 5
Preliminary model adding control.


### 2.4. The Synchronization Model Based on Control

Last part proposes an idea bringing the control into the model of clock synchronization, and then we will analyze the feasibility and advantages of the clock synchronization model based on control in detail. First of all, how to introduce the control into our model is difficult. If the design is unreasonable, we will not get what we expect. Therefore, we must carefully analyze the process of clock synchronization based control in detail.The control process of the clock synchronization between two nodes is depicted in Figure6. It can be described as follows (the Node B is reference node and Node A needs to be synchronized to Node B).(1)
State: at timek, θA,k, and θB,k stand for absolute clock offset of Node A and Node B, respectively. τA,k and τB,k are defined as the fixed delay (include transmission time and reception time, but propagation time is not considered because it is too small) generated when Node A and Node B, respectively, act as sender or receiver in a one-way message exchange. θk=θA,k-θB,k stands for the relative clock offset between Node A and Node B and the fixed delay in a one-way message exchange is τ=τA,k+τB,k. We put these two parameters into a matrix, and define xk=[τ,θk]T.  xk is called the state at time k.(2)
Time message exchange: in order to synchronize NodeA and Node B, Node A sends a synchronization message which carries T1,k to Node B at T1,k. Node B achieves that message at T2,k and then replies to Node A at T3,k. The replied message contains both T2,k and T3,k. Finally, Node A gets the replied message at T4,k. Note that T1,k and T4,k are the local clock of Node A, while T2,k and T3,k are the local clock of Node B as shown in the dotted frame of Figure 6.(3)
Packet loss: in the dotted frame, two dotted lines with arrows present time message exchange between two nodes, and the dotted line indicates that the packet may be lost in the process of message exchange, whereη1 stands for whether packet which Node A send to Node B are transmitted successfully or not. η1=1 if it is successful; otherwise η1=0. In the same way, η2=1 denotes that Node A receives the message from Node B successfully; otherwise η2=0. After one round of message exchange, Node A will get a set of time stamps {T1,k,T2,k,T3,k,T4,k} when η1η2=1, and these time stamps are observation values yk of state xk at time k as shown in (11).(4)
Getting clock skew (f): according to the received time stamps {T1,k,T2,k,T3,k,T4,k}, clock skew f in one synchronization period is easily obtained using the signal processing technology or system identification method in the field of control and it is regarded as an invariable in one synchronization period.(5)
The process of synchronization: from now on, we can estimate statex^k at time k using state estimation method after knowing clock skew f and getting observation value yk which Node A obtains. Further using the ideas of modern control theory, we can generate an optimal control uk under certain control strategy, and the control acts on the logic clock of Node A, modifying the logic clock of Node A and making the absolute clock offset of Node AθA,k→θA,k+1. At this time, the relative clock offset of Node A and Node B is θk→θk+1, and θk+1<θk; namely, xk→xk+1; state change can be abstracted as (10).(6)
Synchronization cycle: repeating process 5, afterN steps, the relative clock offset is small enough.Figure 6
Control process of the clock synchronization.AsN increases, θN becomes more and more small. Finally, the clock synchronization between two nodes is realized.The above is clock synchronization process of two nodes in detail after introducing the control. Now the relationship between the state and the control is assumed to be a linear time invariant (LTI) equation [16, 17, 28]. So clock synchronization state space model based on the control is as follows (regardless of packet loss):
(10)xk+1=Axk+Buk+ωk,(11)yk=Cxk+υk,
where xk is said to be the state of system at time k, which includes two parameters xk=[τkθk]T, τk denotes the fixed delay of two nodes at time k, and θk denotes the relative clock offset of two nodes; obviously, xk+1 is said to be the state of system at time k+1; yk presents the observation value obtained at time k; uk, which makes the state of system from time k to time k+1, realizing clock synchronization between two nodes step by step, shows the control generated according to the estimation of the state; ωk and υk are process noise and observation noise, respectively, which are assumed Gaussian, uncorrelated, white, with mean zero and covariance E[ωkωkT]=Qk and E[υkυkT]=Rk, respectively; coefficient matrix A=[1001], C=[111-1]; control coefficient matrix B is a diagonal matrix, where the diagonal values mean control weight.


### 2.5. Synchronization Model with Packet Loss

From what has been discussed above, although the clock synchronization model based control without packet loss has been established, it is far from requirements of the clock synchronization in WSNs. The main one of the reasons is that in the process of the clock message exchange between nodes, under ideal conditions, the exchange of message will actually be got; while in fact, there exist a series of unreliable factors that often lead to the loss of clock message when transmitted. In this case, the effect caused by the loss of clock message should be considered, so we must amend the clock synchronization model based on control.If we only consider clock message exchange in one step, there are only two things: success or failure. Due to adopting the clock synchronization mechanism of two-way message exchange, where one step includes the exchange message which two nodes send to each other, as long as there is one time of communication failure between two nodes, this step is thought of as exchange of failure, namely, packet loss. Letγk be the random variable indicating whether a packet is dropped at time k or not, so γk=0 if a packet is dropped and γk=1, otherwise. But if all the process of message exchange is considered, packet loss will be a random event and conforms to the Bernoulli random distribution [17, 18, 29, 30] with p(γk=1)=λ. But only considering packet loss is not enough, because the existence of packet loss will seriously affect the performance of the system and even the stability of the system. So we must find a packet loss limit to guarantee the robust stability of the system; namely, the error of time synchronization can be bounded and have the convergence. But given that [17, 18, 24] have in-depth studied the issue of packet loss, and [17] has proved that under the premise of guaranteeing the stability of the system, packet loss limit and relevant conclusions are given, this paper makes sure packet loss rate within the boundaries to guarantee the stability of the system.Compared with the model in [17], it is only observation value that is obtained through message exchange of the network between nodes. Because control is conducted in the local node, when the network is not reliable, there exists observation packet loss, but there is no control packet loss. Therefore, the observation equation is modified as follows:
(12)yk=γk(Cxk+υk).Describing packet loss, we have also considered other forms of description, for example, for the clock synchronization mechanism of the two-way message exchange between two nodes, in every step the observation equation includes two times of message exchange. If every one-way message transmission between two nodes events of packet loss are independent of each other, and the probabilities are not necessarily equal to each other, so we may use a matrix to describe communication situations, and it is given by(13)γk=[αk00βk],
where αk and βk are the Bernoulli random variables, respectively, indicating whether a packet is dropped from Node A to Node B or not and whether a packet is dropped from Node B to Node A or not, and their range is 0 and 1. In the process of communication, as long as |γk|=1, message exchange is successful; otherwise it is dropped.Also event of packet loss was built for the Markov chain model [31]. But no matter how to build the model of packet loss, we adapt the form described in (12). Because it is suitable for the more form and abstracts event of packet loss.Through the above analysis, the clock synchronization model based on the control established contrasts with the protocol methods; in synchronization protocols, estimating the clock parameters mainly uses various statistical signal estimation methods through the clock message exchange between nodes, and then the logic clock of synchronous nodes are amended with this estimation; therefore, it requires fewer computation amounts and less computation time in unit step. In addition, compensation based on the protocol is easy to be realized, which deals with the clock synchronization problem from the perspective of algorithm realization based on engineering. Finally, the compensation is also a kind of control, but it is not the optimal control and synchronization error is not optimal, while in the control method introduced in this paper an optimal control is generated with the estimation, obviously under some control strategies, and then the control affects the logic clock of synchronous nodes. The advantages are as follows.(1)
Controlling makes up the effect of the noise factors and that estimation precision of the estimation method itself is not high.(2)
With the same step of synchronization (meeting some requirements of the synchronization error), the synchronization error of stochastic optimal control under more computational cost is smaller in unit step than that of the protocol, achieving higher precision of synchronization. Under the same precision requirements, the synchronous steps based on optimal control are smaller than that of the protocol. Therefore, the former reduces the network packet exchange for synchronization and reduces the network communication load, which is also very important in the wireless sensor network.(3)
The synchronization approach based on the stochastic optimal control is more reliable and safe.Despite the fact that the clock synchronization based on optimal control has many benefits, it also has some disadvantages. (a) Compensation based on the optimal control, which deals with the clock synchronization problem from the perspective of control theory of state space model, is complicated to be realized. And the approach requires large amount of computation and lead to long time of computation in unit step. (b) The approach requires sensor nodes to pay more electricity power consumption, reducing the survival period of nodes to a certain extent.Note. In terms of implementation of control engineering of control theory, the calculation of control can also be done offline, after the system identification is carried out on the network parameters. Online look-up table completes online and real-time control, which compensates for the shortcomings of long computation time to some extent.


## 2.1. Clock Model

In a network every individual sensor has its own clock. As Figure1, ideally, the clock of a sensor node can be described as follows: C(t)=t, where t stands for the ideal or reference time. However, due to the imperfections of the clock oscillator and the effect of the environment, a clock will drift away from the ideal time even if it is initially rational tuned. In general, the clock function of the ith node is modeled as
(1)Ci(t)=θ+f·t,
where θ and f represent clock offset (phase difference) and clock skew (frequency difference), respectively.Figure 1
Clock model of sensor nodes.Even though in WSNs the number of nodes is thousands, or even more, the paper firstly uses two nodes as a springboard for modeling and analyzing in detail. After strictly discussing two nodes, we extend to many nodes. In this case, we assume that there are only two nodes in WSNs: NodeA and Node B. They drift away from the ideal time due to the changes of external environment temperature and the imperfections of their own clock oscillators. A graphical representation of the relationship is illustrated in Figure 1. From (1), the clock relationship between two nodes, Node A and Node B, can be represented by
(2)CB(t)=θAB+fAB·CA(t),
where θAB and fAB stand for the relative clock offset and skew between Node A and Node B, respectively. Obviously, if two clocks are perfectly synchronized, θAB=0, fAB=1. Otherwise, suppose Node B is the reference node, the task of clock synchronization is to estimate θAB, fAB such that Node A can adjust its own clock or translate its time message to Node B when necessary. If there are L nodes in the network, the global network synchronization requires Ci(t)=Cj(t) for all i,j=1,…,L or all the relative clock offsets and skews are estimated with respect to a reference node.


## 2.2. The Challenge

Assume NodeA needs to be synchronized to reference Node B. When Node A sends its current time to Node A, if there is absolutely no delay in the message delivery, Node A can immediately know the difference between its clock and that of Node B. So only modifying own clock of Node A, Node A can be synchronized to Node B. Unfortunately, in a real wireless network, various delays affect the message delivery, making clock synchronization much more difficult than it seems to be. In general, a series of timing message transmissions are used to estimate the relative clock skews and offsets among nodes. In some sense, clock synchronization in WSNs can be regarded as the process of removing the effects of random delays from the timing message transmissions sent across wireless channels. The various delays present in a message delivery include the following components [10, 13]:(1)
send time: the time is used to build the message and submit the send request to the medium access control (MAC) layer on the sender. This delay is highly variable due to the system call overhead of the operating system and the current processor load;(2)
access time: after reaching the MAC layer, the waiting time for accessing the channel. This is the highly variable depending on the specific MAC protocol and the current network load;(3)
transmission time: the time spent in transmitting a message at the physical (PHY) layer of the sender. The delay is determined by the message length and sending rate;(4)
propagation time: the actual time for a message to be transmitted from the sender to the receiver in a wireless channel. It just depends on the distance between two nodes;(5)
reception time: the time required for receiving a message at the PHY layer of the receiver, which corresponds to the transmission time;(6)
receive time: the time to process the received message at the application layer of the receiver.The above delay components can be classified into two kinds: deterministic delay (fixed delay) and stochastic delay (variable delay). The variable portion depends on various network parameters (e.g., network status and traffic). Therefore, no single delay model can be found to fit for every case. Probability density function (PDF) models that have been proposed for modeling random delays in wireless networks include Gaussian, Exponential, Gamma, Weibull, and log-normal [25–27]. In a word, we have constructed that the equation described the clock of nodes and analyzed the clock relations between two nodes which need to keep the clock synchronization. If Node A needs to be synchronized to reference Node B, we need to estimate the skews and offsets between nodes and at the same time, considering the delay of message exchange, we need to know it.


## 2.3. Clock Synchronization State Space Model

The above has set up the clock model of two nodes; this section is specific to establish model of the clock synchronization between two nodes. Referencing TPSN synchronization protocol, we also adopt the classical mechanism [7, 8, 13] of two-way message exchange between two adjacent nodes, which is depicted in Figure 2. And in this figure, we consider that Node A needs to be synchronized to reference Node B. Assuming timing messages are exchanged N times, in the kth round of message exchange, Node A sends a synchronization message which carries T1,k to Node B at T1,k. Node B achieves that message at T2,k and then replies to Node A at T3,k. The replied message contains both T2,k and T3,k. Finally, Node A gets the replied message at T4,k. Note that T1,k and T4,k are the local clock of Node A, while T2,k and T3,k are the local clock of Node B. After exchanging N times, Node A receives a set of time stamps {T1,k,T2,k,T3,k,T4,k}k=1N. The above procedure can be mathematically modeled as
(3)T2,k=f(T1,k+τ+Xk)+θ,T3,k=f(T4,k-τ-Yk)+θ,
where f and θ denote the relative clock skew and offset of Node A with respect to Node B, respectively, τ is the fixed delay (assume that the fixed delay between two nodes is symmetrical), and Xk and Yk are the random delays in the transmissions from Node A to Node B and from Node B to Node A, respectively. In practice, the random delay is diverse and is described as different distributions according to different judgments and applications including Gaussian, exponential, Gamma, Weibull, and log-normal [13, 25–27]. In this paper, we assume Xk and Yk obey the independent identically distributed Gaussian distribution. According to the central limit theorem, a random sample of size n is drawn from distributions of expected values given by μ and variances given by σ2. When n is large enough, the sampling distribution of sample mean approximatively obeys normal distribution with mean μ and variance σ2/n. If the delay is accumulation result of innumerable independent random process, the delay confirms to the Gaussian delay model. And the test [9] showed that the variable delays can be modeled as Gaussian distributed random variables with 99.8% confidence.Figure 2
Two-way timing message exchange between two nodes.Note that there are two points we need to emphasize. Firstly, fixed delay between two nodes is assumed to be symmetrical. The hypothesis is supported by two reasons. First and foremost, the size of data packet which includes the time message exchange between two nodes is generally equal, and the transmission rate of date packet is the same, so there are identical transmission time and reception time between two nodes. Moreover, propagation time is decided by the distance between two nodes. Suppose that the relative position between two nodes does not change in the process of message exchange, so propagation time remains invariable. Secondly, clock drift (diversification of the clock frequency), which reflects the stability of crystal oscillator, is the second derivative of the clock. So it has little influence on clock, and we may think that clock skew (f) has no obvious changes in one synchronization period. But when it comes from different synchronization periods, clock skew will be different. For example, in period k, consider f=fk, k=0,1,2…, but fk≠fk-1. References [5, 11] presented the statistical signal processing approaches estimating the clock skew under known fixed delay and unknown fixed delay. The approaches adopting signal processing technology, not only apply to the case where the random delay is the Gauss distribution, but also apply to the case where the random delay is the exponential distribution. So the approaches break the constraint of standard statistical estimation and even have some advantages when applied to any delay model. In short, in every time of message exchange process, whichever method is adopted, we have always gotten the unchangeable clock skew in one period.Since the clock skewf can be obtained in the process of message exchange, we can assume that f is known and it is a fixed constant in one synchronization period. Here we notice that f in different synchronization periods is considered to be different. So (3), which only have two unknown parameters, can be transformed into
(4)T2,kf=T1,k+τ+Xk+θf,T3,kf=T4,k-τ-Yk+θf.To present the linear relationship betweenθ and τ, we transform the above equations into state space model:
(5)[T2,kf-T1,kT4,k-T3,kf]=[11f1-1f][τθ]+[XkYk].Equation (5) can be further simplified to
(6)[UkVk]=[11f1-1f][τθ]+[XkYk],
where Uk=(T2,k/f)-T1,k, Vk=T4,k-(T3,k/f).Define(7)xk=[τθ],C=[11f1-1f],yk=[UkVk],υk=[XkYk],so (6) can also be written as
(8)yk=Cxk+υk.Above having been confirmed, in this paper, the random delay obeys independent identically distributed Gaussian distribution, so it is assumed its mean is zero and correlation matrix of the covariance isE[υkυkT]=Rk, which is a diagonal matrix. But xk is unknown; we assume that the present state linearly relates to the state in previous time instance [16, 17, 28]. And because of slow changes, unknown state built a Gauss-Markov dynamic model:
(9)xk=xk-1+ωk-1,
where interference part ωk-1 is modeled as a Gaussian distribution with mean zero and covariance Qk-1, where correlation matrix is E[ωk-1ωk-1T]=Qk-1. Above, the state equation of clock synchronization has been established.Reference [14] modeled the clock synchronization problem as a state space model and presented a distributed Kalman filter algorithm for the clock parameters of the entire network node tracking (the clock skew and clock skew). The model is easy to expand the network size, is robust to changes in network connectivity, and can maintain long-term precision of clock parameters. The state space model established above and the state space model of [14] have similar form, but there are still some differences. (1) In this paper, the state vector is a matrix form about the clock offset and fixed delay and in [14] about the clock skew and accumulated clock offset; (2) in this paper, the measurement model directly considers the clock skew and in [14] the localized timestamp measurement model considers the relationship between the timestamps and the accumulated clock offset; (3) in the paper, we have lots of research work to be done for extending the state model and in [14] the model has be extended to multiple nodes.According to (8) and (9), the picture of clock synchronization process in the kth round of message exchange is shown in Figure 3. This picture is simply described as follows. In the kth round of message exchange, the observation value of the system state is obtained. Through some estimation method, the system state is estimated with the value, and then the logic clock of Node A is adjusted, to achieve the synchronization between Node A and Node B. Seen from the figure, obviously, the system built in the Node A belongs to the closed loop feedback system, but observation value is obtained by exchanging timing message of two nodes.Figure 3
Clock synchronization process of message exchange.The synchronization system, however, is not very stable and is easily affected by noise. Anti-interference ability is poor, and in the presence of packet loss, state estimation is greatly affected by observation value, leading to inaccuracy of the state estimation and affecting the precision of the synchronization.To sum up, we need to find an approach to resolve the above problems. The solution is inspired by [17], which considers control and estimation problems where the sensor signals and the actuator signals are transmitted to various subsystems over a network, where the observation and control packet may be lost, and puts forward a novel theory. In this theory, the architecture of the closed loop system based on TCP-like protocols is shown in Figure 4 [17], where the binary random variables νt and γt indicate whether packets are transmitted successfully or not. The model has a threshold, which affects the network reliability. If it is below the threshold, the best controller will fail to make the system stable. Moreover, the separation principle holds in the model. In other words, the design and analysis of estimator and controller can be separated. As a result, the best control is the linear function of the estimation value.Figure 4
Architecture of the closed loop system over a communication network under TCP-like protocols.The clock synchronization model in this paper is a closed loop feedback system and the observation value is acquired through an unreliable network, so whether it is possible that the clock synchronization is analyzed according to the method of modern control theory or not. Firstly, adding control in the clock synchronization model, we will have a closed loop feedback system with control. Secondly, some control strategies which we should study will weaken the influence of noise and improve the anti-interference ability of synchronization. Even in the rigorous conditions, for example, there are many pocket losses; we also use the control strategy to realize synchronization and guarantee high precision. On the basis of the clock synchronization model built, preliminary model adding control is obtained as shown in Figure5.Figure 5
Preliminary model adding control.


## 2.4. The Synchronization Model Based on Control

Last part proposes an idea bringing the control into the model of clock synchronization, and then we will analyze the feasibility and advantages of the clock synchronization model based on control in detail. First of all, how to introduce the control into our model is difficult. If the design is unreasonable, we will not get what we expect. Therefore, we must carefully analyze the process of clock synchronization based control in detail.The control process of the clock synchronization between two nodes is depicted in Figure6. It can be described as follows (the Node B is reference node and Node A needs to be synchronized to Node B).(1)
State: at timek, θA,k, and θB,k stand for absolute clock offset of Node A and Node B, respectively. τA,k and τB,k are defined as the fixed delay (include transmission time and reception time, but propagation time is not considered because it is too small) generated when Node A and Node B, respectively, act as sender or receiver in a one-way message exchange. θk=θA,k-θB,k stands for the relative clock offset between Node A and Node B and the fixed delay in a one-way message exchange is τ=τA,k+τB,k. We put these two parameters into a matrix, and define xk=[τ,θk]T.  xk is called the state at time k.(2)
Time message exchange: in order to synchronize NodeA and Node B, Node A sends a synchronization message which carries T1,k to Node B at T1,k. Node B achieves that message at T2,k and then replies to Node A at T3,k. The replied message contains both T2,k and T3,k. Finally, Node A gets the replied message at T4,k. Note that T1,k and T4,k are the local clock of Node A, while T2,k and T3,k are the local clock of Node B as shown in the dotted frame of Figure 6.(3)
Packet loss: in the dotted frame, two dotted lines with arrows present time message exchange between two nodes, and the dotted line indicates that the packet may be lost in the process of message exchange, whereη1 stands for whether packet which Node A send to Node B are transmitted successfully or not. η1=1 if it is successful; otherwise η1=0. In the same way, η2=1 denotes that Node A receives the message from Node B successfully; otherwise η2=0. After one round of message exchange, Node A will get a set of time stamps {T1,k,T2,k,T3,k,T4,k} when η1η2=1, and these time stamps are observation values yk of state xk at time k as shown in (11).(4)
Getting clock skew (f): according to the received time stamps {T1,k,T2,k,T3,k,T4,k}, clock skew f in one synchronization period is easily obtained using the signal processing technology or system identification method in the field of control and it is regarded as an invariable in one synchronization period.(5)
The process of synchronization: from now on, we can estimate statex^k at time k using state estimation method after knowing clock skew f and getting observation value yk which Node A obtains. Further using the ideas of modern control theory, we can generate an optimal control uk under certain control strategy, and the control acts on the logic clock of Node A, modifying the logic clock of Node A and making the absolute clock offset of Node AθA,k→θA,k+1. At this time, the relative clock offset of Node A and Node B is θk→θk+1, and θk+1<θk; namely, xk→xk+1; state change can be abstracted as (10).(6)
Synchronization cycle: repeating process 5, afterN steps, the relative clock offset is small enough.Figure 6
Control process of the clock synchronization.AsN increases, θN becomes more and more small. Finally, the clock synchronization between two nodes is realized.The above is clock synchronization process of two nodes in detail after introducing the control. Now the relationship between the state and the control is assumed to be a linear time invariant (LTI) equation [16, 17, 28]. So clock synchronization state space model based on the control is as follows (regardless of packet loss):
(10)xk+1=Axk+Buk+ωk,(11)yk=Cxk+υk,
where xk is said to be the state of system at time k, which includes two parameters xk=[τkθk]T, τk denotes the fixed delay of two nodes at time k, and θk denotes the relative clock offset of two nodes; obviously, xk+1 is said to be the state of system at time k+1; yk presents the observation value obtained at time k; uk, which makes the state of system from time k to time k+1, realizing clock synchronization between two nodes step by step, shows the control generated according to the estimation of the state; ωk and υk are process noise and observation noise, respectively, which are assumed Gaussian, uncorrelated, white, with mean zero and covariance E[ωkωkT]=Qk and E[υkυkT]=Rk, respectively; coefficient matrix A=[1001], C=[111-1]; control coefficient matrix B is a diagonal matrix, where the diagonal values mean control weight.


## 2.5. Synchronization Model with Packet Loss

From what has been discussed above, although the clock synchronization model based control without packet loss has been established, it is far from requirements of the clock synchronization in WSNs. The main one of the reasons is that in the process of the clock message exchange between nodes, under ideal conditions, the exchange of message will actually be got; while in fact, there exist a series of unreliable factors that often lead to the loss of clock message when transmitted. In this case, the effect caused by the loss of clock message should be considered, so we must amend the clock synchronization model based on control.If we only consider clock message exchange in one step, there are only two things: success or failure. Due to adopting the clock synchronization mechanism of two-way message exchange, where one step includes the exchange message which two nodes send to each other, as long as there is one time of communication failure between two nodes, this step is thought of as exchange of failure, namely, packet loss. Letγk be the random variable indicating whether a packet is dropped at time k or not, so γk=0 if a packet is dropped and γk=1, otherwise. But if all the process of message exchange is considered, packet loss will be a random event and conforms to the Bernoulli random distribution [17, 18, 29, 30] with p(γk=1)=λ. But only considering packet loss is not enough, because the existence of packet loss will seriously affect the performance of the system and even the stability of the system. So we must find a packet loss limit to guarantee the robust stability of the system; namely, the error of time synchronization can be bounded and have the convergence. But given that [17, 18, 24] have in-depth studied the issue of packet loss, and [17] has proved that under the premise of guaranteeing the stability of the system, packet loss limit and relevant conclusions are given, this paper makes sure packet loss rate within the boundaries to guarantee the stability of the system.Compared with the model in [17], it is only observation value that is obtained through message exchange of the network between nodes. Because control is conducted in the local node, when the network is not reliable, there exists observation packet loss, but there is no control packet loss. Therefore, the observation equation is modified as follows:
(12)yk=γk(Cxk+υk).Describing packet loss, we have also considered other forms of description, for example, for the clock synchronization mechanism of the two-way message exchange between two nodes, in every step the observation equation includes two times of message exchange. If every one-way message transmission between two nodes events of packet loss are independent of each other, and the probabilities are not necessarily equal to each other, so we may use a matrix to describe communication situations, and it is given by(13)γk=[αk00βk],
where αk and βk are the Bernoulli random variables, respectively, indicating whether a packet is dropped from Node A to Node B or not and whether a packet is dropped from Node B to Node A or not, and their range is 0 and 1. In the process of communication, as long as |γk|=1, message exchange is successful; otherwise it is dropped.Also event of packet loss was built for the Markov chain model [31]. But no matter how to build the model of packet loss, we adapt the form described in (12). Because it is suitable for the more form and abstracts event of packet loss.Through the above analysis, the clock synchronization model based on the control established contrasts with the protocol methods; in synchronization protocols, estimating the clock parameters mainly uses various statistical signal estimation methods through the clock message exchange between nodes, and then the logic clock of synchronous nodes are amended with this estimation; therefore, it requires fewer computation amounts and less computation time in unit step. In addition, compensation based on the protocol is easy to be realized, which deals with the clock synchronization problem from the perspective of algorithm realization based on engineering. Finally, the compensation is also a kind of control, but it is not the optimal control and synchronization error is not optimal, while in the control method introduced in this paper an optimal control is generated with the estimation, obviously under some control strategies, and then the control affects the logic clock of synchronous nodes. The advantages are as follows.(1)
Controlling makes up the effect of the noise factors and that estimation precision of the estimation method itself is not high.(2)
With the same step of synchronization (meeting some requirements of the synchronization error), the synchronization error of stochastic optimal control under more computational cost is smaller in unit step than that of the protocol, achieving higher precision of synchronization. Under the same precision requirements, the synchronous steps based on optimal control are smaller than that of the protocol. Therefore, the former reduces the network packet exchange for synchronization and reduces the network communication load, which is also very important in the wireless sensor network.(3)
The synchronization approach based on the stochastic optimal control is more reliable and safe.Despite the fact that the clock synchronization based on optimal control has many benefits, it also has some disadvantages. (a) Compensation based on the optimal control, which deals with the clock synchronization problem from the perspective of control theory of state space model, is complicated to be realized. And the approach requires large amount of computation and lead to long time of computation in unit step. (b) The approach requires sensor nodes to pay more electricity power consumption, reducing the survival period of nodes to a certain extent.Note. In terms of implementation of control engineering of control theory, the calculation of control can also be done offline, after the system identification is carried out on the network parameters. Online look-up table completes online and real-time control, which compensates for the shortcomings of long computation time to some extent.


## 3. Control Strategy in Clock Synchronization

The clock synchronization model based on control is established, and seen from Figure6, the main task of the clock synchronization is to complete the selection and design of estimation and control, the quality of which directly affects the synchronization precision and the stability of the system. Since the observation (8) established is according to TPSN protocol, and the equation of state (10) is based on the TCP, like model in [17], this model only contains the observation packet loss, and the successful transmission of the packet is acknowledged at the receiver. Therefore, the estimation and the control of the clock synchronization model based on control also apply to the separation principle.Estimation. Since it is a linear system that we establish, the optimal choice of linear system state parameter estimation is Kalman filtering. Kalman filtering, which only needs the last state estimation and the present observation and does not store a large number of historical datum, can estimate the present state, reducing the storage capacity and computing complexity and at the same time reaching the minimum mean square error. As a result, the Kalman filtering is selected. The modified Kalman filtering iterative equation is as follows (the following results are proved in Appendix A):
(14)x^k+1|k=Ax^k+Buk,(15)x~k+1|k=x^k+1|k-xk+1=Ax^k-ωk,Pk+1|k=APkAT+Qk,x^k+1=x^k+1|k+γk+1Kk+1[yk+1-Cx^k+1|k],x~k+1=x^k+1-xk+1=(I-Kk+1γk+1C)x~k+1|k+γk+1Kk+1υk+1,Pk+1=(I-γk+1Kk+1C)Pk+1|k,Kk+1=Pk+1|kCT(CPk+1|kCT+Rk+1)-1.Control. Although we have established the clock synchronization state space model based on control, quantitatively analyzing the clock synchronization issue must further discuss control strategy. Because the clock synchronization considers many factors, such as synchronization precision, the synchronization time, synchronous cycle, and the more important energy constraints, which are only parts of the challenge clock synchronization face and because of the uncertainty of wireless sensor network communication and delay, those factors bring great difficulty in synchronization control research. In this paper, the problem solving is the first one giving an index to evaluate control; namely, what kind of control for clock synchronization is the best of controls? The following analyzes the synchronization control strategies, separately from different starting point, that is, the single-step optimal control and LQG global optimal control.


### 3.1. Single-Step Optimal Control

So-called single-step optimal control means that in every control, the state of the system gets as soon as possible close to the ideal value, namely, the target state. However, the single-step optimal control described in this paper is the following: under the estimation of the system state based on Kalman filtering, getting the optimal control through the single-step optimal control strategy and finally achieving to the clock synchronization between two nodes.We design synchronous performance index function which is in the following form(16)gk≜g(xk)=(xk-z)TD(xk-z)=xkTDxk+2hTxk+zTDz,
where z is the expected value of the system state xk and the setting of the value stands for the purpose of the single-step optimal control to some extent. Obviously here it is to achieve the clock synchronization. D is nonnegative, h=-Dz, and xkTDz is a scalar, so xkTDz=zTDxk. If the controller is uk, we have
(17)xk+1=rk+Buk,
where rk=Axk+ωk. Then the expectation of the performance index function at the next step is
(18)g^k+1|k≜E[g(xk+1)]=E[g(rk+Buk)]=E[rkTDrk+2rkTDBuk+ukTBTDBuk]+2E[hTrk+hTBuk]+zTD1z=g^(rk)+2(r^kTDB+hTB)uk+ukTHuk,
where
(19)g^(rk)=E[rkTDrk+2hTrk]+zTD1z,r^k≜E[rk]=Ax^k,H=BTDB.The optimal control at stepk is obtained by
(20)Min⁡2(r^kTDB+hTB)uk+ukTHukis.t.uk∈[u_,u¯].However, above nonlinear quadratic programming is very computational costly, so in the following, a conditional simplified solution to calculate the optimal control is developed. IfH is invertible, without considering the constraint of control, then the optimal control at step k is
(21)uk*=-H-1(r^kDB+hTB)T,
as long as uk*∈[u_,u-].Proof.
Because(22)∂∂ukg^k+1|k=2Huk+2(r^kDB+hTB)T,
it is well known that the solution for the linear equation (∂/∂uk)g^k+1|k=0 is uk*. Then
(23)∂2∂ukukTgk+1|k|uk*=2H.
It is easily to be proved that matrixH is nonnegative. Hence, if the condition that uk*∈[u_,u-] is satisfied, uk* is the optimal control; that is,
(24)uk*=argmin⁡ukg^k+1|k.


### 3.2. LQG Global Optimal Control

From the perspective of global performance indicators, linear quadratic optimal feedback controller can achieve the global optimal control, which is a set of orderly sequences of the optimal control. The linear quadratic optimal controller is based on state space technology to design an optimal dynamic controller. System model is presented in a state space form. The objective function of the model is a quadratic function of state and control, which gets the state close to the desired value and limits the energy consumption of control at the same time. Since this paper considers process and observation noise, it belongs to the linear quadratic Gaussian optimal control problem.Consider the following cost function:(25)J=12[xNTQ0xN+∑k=0N-1(x^kTQ1x^k+ukTQ2uk)],
where x^k and uk indicate the estimation of the system state and optimal control of synchronization; xN indicates the finally desired value of the synchronization state, and the setting of the value stands for the purpose of the single-step optimal control to some extent. Obviously here it is to achieve the clock synchronization; then both Q0∈R2×2 and Q1∈R2×2 belong to positive semidefinite of real symmetric matrices; finally Q2∈R2×2 is a positive definite of real symmetric matrix. According to the linear quadratic Gaussian optimal control theory [32], we have (the following conclusions are proved in Appendix B)
(26)uk=-Lkx^k,
where the gain matrix is
(27)Lk=(BTSk+1B+Q2)-1BTSk+1A.
And S is obtained by the following Riccati equation:
(28)Sk=AT(Sk+1-Sk+1B(BTSk+1B+Q2)-1BTSk+1)A+Q1,SN=Q0.So based on the quadratic performance index of control and state, the global optimal control is obtained. Then the result also shows that the gain matrixLk makes no difference with the initial value of the state, so it can be computed offline and reduces the amount of calculation.


### 3.3. Difference of “Compensation”-Correction

Above we put forward two kinds of the clock synchronization of stochastic optimal control. But in practice, it is not just confined to the two approaches, and we can design to the control strategies meeting the requirements according to the actual demand and requirements of parameters. But no matter what kind of optimal control is adopted, the clock synchronization based on the stochastic optimal control is to decrease the synchronization error in synchronous cycle, namely, improve the synchronization accuracy, rather than to realize synchronization stability problem.The “compensation”Δ of the clock synchronization based on stochastic optimal control and the clock synchronization based on the protocol is contrasted.(a)
The “compensation”Δs of clock synchronization based on the single-step optimal control is to optimize the every step of the synchronization state. Consider
(29)Δs≜uk*=-H-1(r^kDB+hTB)T,whereH=BTDB, r^k≜E[rk]=Ax^k.(b)
The “compensation”Δl of the clock synchronization based on the LQG global optimal control is to optimize the synchronization state in the synchronization cycle, from a global perspective, rather than considering one step of the optimum. Consider
(30)Δl≜uk=-Lkx^k,whereLk=(BTSk+1B+Q2)-1BTSk+1A and S is obtained by the following Riccati equation:
(31)Sk=AT(Sk+1-Sk+1B(BTSk+1B+Q2)-1BTSk+1)A+Q1,SN=Q0.(c)
The “compensation”Δp of the clock synchronization based on the protocol is to be easy for engineering realization, and the estimate is directly acted as the compensation. Consider
(32)Δp=x^k.Actually, the compensation based on the protocol can also be modeled as the most simple control (without any gain coefficient correction), but it is not the most optimal control.


## 3.1. Single-Step Optimal Control

So-called single-step optimal control means that in every control, the state of the system gets as soon as possible close to the ideal value, namely, the target state. However, the single-step optimal control described in this paper is the following: under the estimation of the system state based on Kalman filtering, getting the optimal control through the single-step optimal control strategy and finally achieving to the clock synchronization between two nodes.We design synchronous performance index function which is in the following form(16)gk≜g(xk)=(xk-z)TD(xk-z)=xkTDxk+2hTxk+zTDz,
where z is the expected value of the system state xk and the setting of the value stands for the purpose of the single-step optimal control to some extent. Obviously here it is to achieve the clock synchronization. D is nonnegative, h=-Dz, and xkTDz is a scalar, so xkTDz=zTDxk. If the controller is uk, we have
(17)xk+1=rk+Buk,
where rk=Axk+ωk. Then the expectation of the performance index function at the next step is
(18)g^k+1|k≜E[g(xk+1)]=E[g(rk+Buk)]=E[rkTDrk+2rkTDBuk+ukTBTDBuk]+2E[hTrk+hTBuk]+zTD1z=g^(rk)+2(r^kTDB+hTB)uk+ukTHuk,
where
(19)g^(rk)=E[rkTDrk+2hTrk]+zTD1z,r^k≜E[rk]=Ax^k,H=BTDB.The optimal control at stepk is obtained by
(20)Min⁡2(r^kTDB+hTB)uk+ukTHukis.t.uk∈[u_,u¯].However, above nonlinear quadratic programming is very computational costly, so in the following, a conditional simplified solution to calculate the optimal control is developed. IfH is invertible, without considering the constraint of control, then the optimal control at step k is
(21)uk*=-H-1(r^kDB+hTB)T,
as long as uk*∈[u_,u-].Proof.
Because(22)∂∂ukg^k+1|k=2Huk+2(r^kDB+hTB)T,
it is well known that the solution for the linear equation (∂/∂uk)g^k+1|k=0 is uk*. Then
(23)∂2∂ukukTgk+1|k|uk*=2H.
It is easily to be proved that matrixH is nonnegative. Hence, if the condition that uk*∈[u_,u-] is satisfied, uk* is the optimal control; that is,
(24)uk*=argmin⁡ukg^k+1|k.


## 3.2. LQG Global Optimal Control

From the perspective of global performance indicators, linear quadratic optimal feedback controller can achieve the global optimal control, which is a set of orderly sequences of the optimal control. The linear quadratic optimal controller is based on state space technology to design an optimal dynamic controller. System model is presented in a state space form. The objective function of the model is a quadratic function of state and control, which gets the state close to the desired value and limits the energy consumption of control at the same time. Since this paper considers process and observation noise, it belongs to the linear quadratic Gaussian optimal control problem.Consider the following cost function:(25)J=12[xNTQ0xN+∑k=0N-1(x^kTQ1x^k+ukTQ2uk)],
where x^k and uk indicate the estimation of the system state and optimal control of synchronization; xN indicates the finally desired value of the synchronization state, and the setting of the value stands for the purpose of the single-step optimal control to some extent. Obviously here it is to achieve the clock synchronization; then both Q0∈R2×2 and Q1∈R2×2 belong to positive semidefinite of real symmetric matrices; finally Q2∈R2×2 is a positive definite of real symmetric matrix. According to the linear quadratic Gaussian optimal control theory [32], we have (the following conclusions are proved in Appendix B)
(26)uk=-Lkx^k,
where the gain matrix is
(27)Lk=(BTSk+1B+Q2)-1BTSk+1A.
And S is obtained by the following Riccati equation:
(28)Sk=AT(Sk+1-Sk+1B(BTSk+1B+Q2)-1BTSk+1)A+Q1,SN=Q0.So based on the quadratic performance index of control and state, the global optimal control is obtained. Then the result also shows that the gain matrixLk makes no difference with the initial value of the state, so it can be computed offline and reduces the amount of calculation.


## 3.3. Difference of “Compensation”-Correction

Above we put forward two kinds of the clock synchronization of stochastic optimal control. But in practice, it is not just confined to the two approaches, and we can design to the control strategies meeting the requirements according to the actual demand and requirements of parameters. But no matter what kind of optimal control is adopted, the clock synchronization based on the stochastic optimal control is to decrease the synchronization error in synchronous cycle, namely, improve the synchronization accuracy, rather than to realize synchronization stability problem.The “compensation”Δ of the clock synchronization based on stochastic optimal control and the clock synchronization based on the protocol is contrasted.(a)
The “compensation”Δs of clock synchronization based on the single-step optimal control is to optimize the every step of the synchronization state. Consider
(29)Δs≜uk*=-H-1(r^kDB+hTB)T,whereH=BTDB, r^k≜E[rk]=Ax^k.(b)
The “compensation”Δl of the clock synchronization based on the LQG global optimal control is to optimize the synchronization state in the synchronization cycle, from a global perspective, rather than considering one step of the optimum. Consider
(30)Δl≜uk=-Lkx^k,whereLk=(BTSk+1B+Q2)-1BTSk+1A and S is obtained by the following Riccati equation:
(31)Sk=AT(Sk+1-Sk+1B(BTSk+1B+Q2)-1BTSk+1)A+Q1,SN=Q0.(c)
The “compensation”Δp of the clock synchronization based on the protocol is to be easy for engineering realization, and the estimate is directly acted as the compensation. Consider
(32)Δp=x^k.Actually, the compensation based on the protocol can also be modeled as the most simple control (without any gain coefficient correction), but it is not the most optimal control.


## 4. Simulation and Performance Evaluation

Having gotten the clock synchronization control from the perspective of the theory above, in this section, simulation results and analysis are shown. Simulations are conducted within Matlab 7.1 environment and assumed that there only exist two nodes between which there is no packet loss or clock skew, and it stands to reason that multiple hop transmission else is impossible between only two nodes in the ideal network.(1)
According to being built the state-space model of the clock synchronization (10) and (11), the initial state of the system x0=[τ0θ0]T=[0.010.012]T, where τ0 denotes the initially fixed delay and θ0 denotes the initially relative clock offset between two nodes. We also preset some initial values about the estimation, including initial state estimation x^0=[0.020.015]T and initial error covariance P0=E[(x0-x^0)(x0-x^0)T].(2)
The parameters of clock synchronization state space model are as follows: system matrix, observation matrix, and noise covariance matrix, respectively, are as follows:A=[1001], C=[111-1], E[ωkωkT]=Q=[1×10-8001×10-8], E[υkυkT]=R=[1.8×10-5001.8×10-5].(3)
In the single-step optional control, because of the restrict respect to the matrixB, namely, B is invertible, we choose the control coefficient matrix to be B=[1001]. The weight matrix of the single-step control D=[1004] increases the control proportion of the relative clock offset. Finally desired value of the state is set to be z=[0.010]T.(4)
In the LQG optimal control, aiming at the clock synchronization, the termination state of performance index shows that the fixed delay and clock offset between two nodes are eventually attained by controlling. In the simulations, we get two sets of termination state; namely,xN=[00]T and xN=[0.010]T. The weight coefficient matrices are the following: Q0=[1001], Q1=[0.5000.5],Q2=[1001]. Note: if there are no special instructions in the following, the initial conditions are mentioned above.Figure7 contrasts the relative clock offsets and the estimation of the fixed delays based on the control with that based on compensation of the protocol (compensation of the protocol described in this paper is defined as follows; according to the thought of the classical synchronization protocol [8], the compensation of the protocol refers to use of the abstracted observation of the two-way data exchange and estimation model and directly compensate the local clock with the estimation. In order to fully compare the different effect of the clock synchronization between the optimal control and compensation of the protocol, the premise in process of the clock synchronization-based including the modeling method and the estimation methods is the same) [5, 8, 13] in the process of clock synchronization, where the states include the relative clock offset θ showed on the left ordinate and the estimation of the fixed delay τ^ showed on the right ordinate. Because both the clock offset and the clock skew result in the clock nonsynchronization and the above have mentioned that the clock skew is known, even set 1, now the clock synchronization is determined by the relative clock offset. That is to say, the relative clock offset actually reflects the clock synchronization error of two nodes.The comparison of the relative clock offsets and the estimation of the fixed delays of the three methods with regard to various termination statesxN.
(a)
x
N
=
[
0
0
]
T
(b)
x
N
=
[
0.01
0
]
TIt is shown by simulations in Figure7 about the relative clock offset that the relative clock offsets based on the control both come to be less than that based on the protocol after five steps, and then the difference has still remained. So considering the above mentioned, the simulation results make clear that the synchronization errors of the synchronization methods based on the control both are less than that based on the protocol. Nevertheless with respect to the relative offsets of the two methods based on the control, it is obvious from Figure 7 that the convergence speed of the single-step is faster than that of the LQG, and especially the change is drastic in the first one. This is mainly due to that the single-step one generates the next control which is optimal in every step and only considers the present state estimation, while the LQG, which accumulates the global message and then obtains the control of the every step, is globally optimal. Thus, the single-step has a drastic change, but the LQG is relatively smooth. On the change trend of the relative clock offset, the LQG is slower than the single-step one, even slower than the protocol, but considering the expenditure of the energy, the LQG has some advantages. After all, the control is solved by minimizing a quadratic performance index. That is to say, the method getting the optimal control minimizes to expend the energy of control on the premise of meeting the required state. Furthermore, after stabilizing the state, its relative clock offset is also smaller than the protocol.In addition, the others above indicate the estimation of the fixed delay. The three methods all can accurately converge to the desired fixed delay, but looking closely, the methods based on the control both faster converge to the required value, especially the single-step. Note the difference of the estimation of the fixed delay between (a) and (b) in the LQG optimal control. WhenxN=[00]T, namely, the desired fixed delay τN=0, the LQG optimal control makes the fixed delay converge to the zero; while when xN=[0.010]T, namely, the desired fixed delay τN=0.01, the LQG optimal control makes the fixed delay converge to 0.01. So, the LQG optimal control can achieve the required state under the different termination states.From Figure7, we can see that after N steps, θk converges to a small range, which is indicated by δ. The reason why it changes in a small range is the influence of noise. So, to analyse the relationship of clock synchronization error between the three methods from the perspective of quantitative, we define the following random process.Assuming afterN steps θk converges to a small range, we define in the t time clock synchronization, synchronization error convergence average; namely, the average of θk after it converges is denoted:
(33)θ-t≜1L-N+1∑K-NLθk,
where L indicates the synchronization cycle. So, {θ-t,t=1,2…} is a random process.Figure8 shows M=100 times of sampling experiment results of stochastic process {θ-t,t=1,2…}. Every time of clock synchronization runs 50 times of two-way timestamp information exchange and synchronization operation (include estimation, optimal control, and compensation).Figure 8
The comparison of averages of the relative clock offset after stabilizing the state.θ
-
t, which represents that the average of θk when it converges is denoted, reflects the size of the average of θk after it converges in one time of clock synchronization. It is shown in Figure 8 that θ-t based on the protocol is larger than θ-t based on the stochastic optimal control, so it suggests that synchronization error convergence average based on the stochastic optimal control is smaller than that based on the protocol; namely, the clock synchronization approach based on the stochastic optimal control improves the accuracy of clock synchronizationThe variance ofθ-t can reflect the degree of deviation from the average. However, there are 100 times of sampling experiment results, so the variance of the sampling experiment results is defined:
(34)D(θ-t)=1M∑t=1M[θ-t-E(θ-t)][θ-t-E(θ-t)].
In the 100 times of the sampling experiment, the variance of synchronization error convergence average is shown in Table 1.Table 1
The comparison of the variance of synchronization error convergence average among three methods.
Protocol
Single-step
LQG
Variance(D(θ-t))
2.66
E
-
08
8.74
E
-
10
5.52
E
-
09For the experiments, it is visually seen in Figure8 that the fluctuation of θ-t based on the protocol is large, while the fluctuation of θ-t based on the optimal control is small. Seen from Table 1, the variance D(θ-t) of synchronization error convergence average based on the stochastic optimal control is smaller than D(θ-t) based on the protocol, so the smaller variance indicates that fluctuation of synchronization error convergence average is smaller and long-term running network; the synchronization approach based on the stochastic optimal control is more reliable and safe.Both Figures7 and 8 contract the three methods under the same condition. Below, we simulate the relationship between the convergence of the methods based on the control and initial conditions. But taking into account the length of this paper, the paper uses the convergence of single-step as an example for discussing in the following. As a matter of fact, the LQG is the same.Figure9 shows the dependencies of the single-step optimal control state on the different desired values of the fixed delay. In the picture, the relative clock offset θ is shown on the left ordinate and the estimation of the fixed delay τ^ is showed on the right ordinate. Clearly seen from the figure, under the different desired values of the fixed delay, all of the estimations of the fixed delays quickly approach and finally converge to the desired value. At the same time, all of the relative clock offsets also converge to zero. As a result, there are no dependencies with the state on the different desired fixed delays.Figure 9
The comparison of the state when the single-step optimal control is under desired values of the fixed delay.The above pictures, which are from Figures10, 11, 12, and 13, respectively, express the dependencies of the single-step optimal control state on the different initial estimations of the relative clock offset θ^0, the different initial estimations of the fixed delay τ^0, the different initial values of the relative clock offset θ0, and the different initial values of the fixed delay τ0. In these figures, the relative clock offset θ is shown on the left ordinate and the estimation of the fixed delay τ^ is shown on the right ordinate, as well. As can be seen from these figures, under the different conditions, all of the relative clock offsets can quickly converge to zero, and all of the estimation of the fixed delays can also quickly converge to the desired value. Consequently, there are also no dependencies with the state on the different conditions mentioned above.Figure 10
The comparison of the state when the single-step optimal control is under the different initial estimations of the relative clock offset.Figure 11
The comparison of the state when the single-step optimal control is under the different initial estimations of the fixed delay.Figure 12
The comparison of the state when the single-step optimal control is under the different initial values of the relative clock offset.Figure 13
The comparison of the state when the single-step optimal control is under the different initial values of the fixed delay.Figure14 indicates every step performance index of single-step optimal control under different initial estimations of the state, where what is shown on the left ordinate is the performance index under the different initial estimations of the relative clock offset, which are, respectively, 0.005, 0.01, and 0.05. Seen from the drawing, all of the performance index can converge to zero, but the total of the performance index ∑k=050gk is different and is correspondingly 3.3578×10-4, 4.5245×10-4, and 0.0159, so there are different costs to achieve the convergence. Meanwhile what is shown on the right ordinate is the performance index under the different initial estimations of the fixed delay, which are respectively, 0.0005, 0.015, 0.05. To achieve the convergence, their costs are different as well.Figure 14
The comparison of the every step performance index when the single-step optimal control is under different initial estimations of the state.Figure15 indicates every step energy consumption of LQG optimal control under different initial estimations of the state, where the so-called energy consumption just means the one of every step, namely,
(35)Jk=xkTQ1x+ukTQ2uk.Figure 15
The comparison of the every step energy consumption when the LQG optimal control is under different initial estimations of the state.In this map, what is shown on the left ordinate is the performance index under the different initial estimations of the relative clock offset, which are, respectively, 0.005, 0.01, and 0.05. Seen from the drawing, all of the energy can converge to zero, but the total of the energy∑k=050Jk which is equal to J mentioned above is different and is correspondingly 9.1983×10-5, 1.0342×10-4, and 2×10-3, so there is different energy consumption in the whole process of the synchronization. Meanwhile what is shown on the right ordinate is the one under the different initial estimations of the fixed delay, which are, respectively, 0.0005, 0.015, and 0.05. To achieve the convergence, there is also the same difference.In short, in Figures7 and 8 it can be seen that the relative clock offsets based on the control are less than that based on the protocol, so analyzing the context, we make sure the clock synchronization error based on the control between two nodes is smaller and this method has some advantages when the high precision of the synchronization error is required. As can be seen from Figures 9 to 13, firstly, the method based on the control has certain adaptability, which does not depend on the initial conditions where the convergence is not affected. Moreover, in the process of the synchronization based on the control, there exists relative independence between the two values in the state, where they do not seem to affect each other. So this provides the convenience of the further study and analysis in the future with some foundation. Finally, the clock synchronization method based on the control is more reliable in the process of the clock synchronization. Figures 14 and 15 verify that setting the difference of the initial conditions signifies the difference of the energy consumption to complete the synchronization. Therefore, reasonably setting the initial conditions can save energy to a certain extent.


## 5. Conclusion and Future Directions

The author has put forward a new research approach and modeling approach from the perspective of control theory and quantitatively analyzed the clock synchronization, which is called the clock synchronization method based on the control. This method has firstly analyzed the clock relationship based on the two-way message exchange mechanism between nodes in WSNs, building the state space model of the clock synchronization between two nodes. Then, the author used the ideas in modern control theory and introduced control as the state space mode is established to quantitative analyze the clock synchronization issue from the perspective of control. Finally, two kinds of control strategies have been discussed in detail: a single-step optimal control (based on the present time information) and LQG optimal control (based on the global information).At the beginning, the paper uses two nodes as a springboard for modeling and analyzing in detail. For multiple nodes in (WSNs), system matrix dimensions are extended according to the number of nodes. This method can also analyze the clock synchronization issue. Meanwhile, the author assumed that the random time delay obeys Gaussian distribution. But for the statistical signal processing technique was applied to clock synchronization in WSNs, estimation of the parameters has been expanded from the Gaussian distribution to the general random distribution. Therefore, in the case of obeying other random distributions, the clock synchronization method based on the control is applied as well. Simulation results reveal that the proposed clock synchronization method based on control has higher precision and faster convergence rate than the classic TPSN synchronization; moreover, after convergence of synchronization error, the former has smaller fluctuation of synchronization error; anti-interference performance of the former is stronger. In addition, according to the network features (delay, packet loss, node number, etc.) and the control objectives, the author set up reasonable performance index functions and designed different control strategies to meet the overall demand of communication and control. Furthermore, different control strategies have their own advantages; the single-step optimal control ensures any clock synchronization is the fastest moving to the target and convergence speed is the fastest, so that the required synchronization time is the shortest, while LQG optimal control based on global information maintains the smooth and steady control over the clock synchronization. So, according to different needs in reality, the appropriate control strategy should be chosen.The future research direction is to analyze the packet loss impact on the convergence of the system and synchronization accuracy. For the different simulation data, prove the convergence of the single-step optimal control from the perspective of the convex optimization theory. To the unreliable network of a certain scale, can control strategy meet the requirement of synchronization precision? As for whether control strategy can also control clock skew or not, it also requires us to further study the problem in the future.



---

*Source: 731980-2014-08-31.xml*