# Clock Synchronization in Wireless Sensor Networks: Analysis and Design of Error Precision Based on Lossy Networked Control Perspective

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

---

## Abstract

Motivated by the importance of the clock synchronization in wireless sensor networks (WSNs), due to the packet loss, the synchronization error variance is a random variable and may exceed the designed boundary of the synchronization variance. Based on the clock synchronization state space model, this paper establishes the model of synchronization error variance analysis and design issues. In the analysis issue, assuming sensor nodes exchange clock information in the network with packet loss, we find a minimum clock information packet arrival rate in order to guarantee the synchronization precision at synchronization node. In the design issue, assuming sensor node freely schedules whether to send the clock information, we look for an optimal clock information exchange rate between synchronization node and reference node which offers the optimal tradeoff between energy consumption and synchronization precision at synchronization node. Finally, simulations further verify the validity of clock synchronization analysis and design from the perspective of synchronization error variance.


---

## Body

## 1. Introduction

From the present study [1], the purpose of establishing various models of the clock synchronization is to design a more optimized synchronization algorithm and improve the synchronization precision. For the analysis of synchronization precision, the studies focus on estimating the clock parameters; at the same time, deeply analyzing the synchronization error variance is also worthy of attention. For the network without packet loss, existing studies offered the quantitative equation of the synchronization error variance, which can be determined offline. Various optimized synchronization algorithms are aimed at decreasing the synchronization error variance as far as possible. However, due to the randomness of packet loss, the synchronization error variance is a random variable [2]. For given applications, the variance maybe exceeds the designed boundary of the synchronization variance. This brings serious hidden peril for wireless sensor networks.Therefore, this paper researches clock synchronization problems from the point of the synchronization error variance. How does packet loss affect the synchronization error variance? Can packet loss in the existing network satisfy the requirements of the synchronization precision? How to reasonably improve synchronization precision with a limited resource? It is the following cases that are common but not efficiently solved in reality.For a wireless sensor network with packet loss, packet loss has a serious influence on clock parameters estimation of the synchronization node. The more the packet is lost, the larger the estimation error of clock parameters is and the lower the clock synchronization precision is. And due to the randomness of packet loss, the synchronization error variance is a random variable. Further, different sensor networks have different requirements of synchronization precision according to the different application backgrounds. So can packet loss in the existing network satisfy the requirements of application background? For the synchronization error variance analysis issue, we look for a minimum clock information packet arrival rate in order to guarantee the precision requirement at synchronization node.Assume there is no packet loss in sensor network but the sensor node freely schedules whether to send the clock information. The more the clock information is exchanged, the higher the synchronization precision is, while the more the corresponding energy is consumed. We expect that the sensor nodes can consume as little energy as possible. At the same time, we hope that the clock synchronization is as highly precise as possible. At this point, it is important to consider how to set up network parameters in order to achieve the optimal tradeoff between energy consumption and synchronization precision. For the synchronization error variance design issue, we look for an optimal clock information exchange rate between synchronization node and reference node, which offers the optimal tradeoff between energy consumption and synchronization precision at synchronization node.For the issue of clock synchronization, early studies focus on the design of protocols, such as the Time Synchronization Protocol for Sensor Networks (TPSN) [3], the Reference-Broadcast Synchronization (RBS) [4], the Flooding Time Synchronization Protocol (FTSP) [5], and the Pairwise Broadcast Synchronization (PBS) [6]. Other researches optimize the classical protocols, such as [7–9]. In [1], clock synchronization of WSNs is modeled and analyzed by following a signal processing viewpoint in various network delay distributions. At present, the latest research proposes a distributed algorithm, which is scalable with network size. Reference [10] models the accumulated clock offset and skew as the evolution model and proposes a distributed Kalman filter algorithm. The algorithm only requires each node to exchange limited information with its direct neighbors and thus is robust to changes in network connectivity. Reference [11] estimates clock parameters of the global network from the perspective of probability distribution based on belief propagation and puts forward a full distributed algorithm which adopts asynchronous way and does not require any centralized information processing or coordination. In addition, [12] introduces two kinds of control strategy based on the state space model of the clock synchronization. From the perspective of network control, the literature improves the synchronization precision and speeds up the convergence of the synchronization. But these studies rarely analyze the random distribution of the synchronization error variance, let alone the analysis and design issues of the synchronization error variance beyond the designed boundary of the synchronization variance (or the probability of the synchronization error variance beyond the designed boundary of the synchronization variance). In order to solve, analyze, and design issues put forward above, this paper analyzes the clock relationship based on the two-way information exchange mechanism between the nodes in WSNs. Then regarding fixed delay and clock offset as unknown parameters and using the clock synchronization state space model, the paper establishes the model of synchronization error variance analysis and design issues.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. References [13, 14] introduce problems of the state estimation and stabilization of a LTI (linear time invariant) system with finite-communication bandwidth constraints. Reference [2] shows that there exists a critical rate of packet arrivals below which the modified Kalman filter diverges and converges otherwise. Reference [15] evaluates the performance of the estimator subject to packet loss from the perspective of probability. Reference [16] considers the presence of observation packet loss and shows the 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. In [17], author describes packet loss as two-state Markov chain process and analyzes the problems of Kalman filter in this case. Reference [18] improves the statistical stability and performance of Kalman filter over a large set of packet loss using multiple description coding. Reference [19] extends the theoretical results in [2] to closed loop control and points out that when the separation principle holds, the optimal linear-quadratic-Gaussian (LQG) controller is a linear function of the estimated state; when the separation principle does not hold, the optimal LQG controller is in general nonlinear. These theoretical achievements offer great reference value for analyzing the clock synchronization issue. In view of this, based on the unified framework of the clock synchronization state space model, this paper researches the synchronization error variance analysis and design issues from the perspective of the unified framework of network control.In this paper, the major contributions are as follows.(1)
By analyzing the clock relationship for the two-way information exchange mechanism in wireless sensor network and based on a unified framework of the clock synchronization state space model, we discuss the analysis and design issues between the synchronization error variance and packet loss rate.(2)
In the analysis issue, we prove that the steady-state error variance of Kalman filter in the statistical property is a monotonically decreasing function of packet arrival rate. Then we find a minimum clock information packet arrival rate by an efficient bisection search algorithm in order to guarantee synchronization precision at synchronization node.(3)
In the design issue, we establish a performance metric between energy consumption and synchronization precision at synchronization node. Then we obtain the optimal solution form of clock information exchange rate in order to achieve the optimal tradeoff between energy consumption and synchronization precision at synchronization node.This paper is organized as follows. In Section2, regarding fixed delay and clock offset as clock state variables, clock synchronization system models are established. Section 3 puts forward mathematical model of the synchronization error variance analysis and design issues. Some preliminaries are represented in Section 4. In Section 5, the proposed analysis issue is researched in detail. In Section 6, the proposed design issue is researched in detail. Some examples are given in Section 7. Finally, Section 8 discusses the future work and Section 9 summarizes the paper.


## 2. System Modeling

We consider the clock synchronization problem between two nodes. Referencing TPSN [3] synchronization protocol, we also adopt the classical mechanism [1, 3, 20] of two-way message exchange between two adjacent nodes, which is depicted in Figure 1. 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 reply message contains both T2,k and T3,k. Finally, Node A gets the reply 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(1)T2,k=fT1,k+τ+Xk+θ,T3,k=fT4,k-τ-Yk+θ.In the paper, most of basic values we used are listed in Value Definition. And there are three points emphasized.(1)
Assume thatXk and Yk obey the independent identically distributed (i.i.d) Gaussian distribution due to the central limit theorem. We take n simples from an arbitrary and i.i.d totality with mean μ and variance σ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 the addition of innumerable independent random process, the delay obeys the Gaussian delay model. And the test [4] showed that the variable delays can be modeled as Gaussian distributed random variables with 99.8% confidence.(2)
Assume that the size of data packet which includes the clock message exchange between two nodes is generally equal, and the transmission rate of data packet is the same, so there are the same 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 information exchange, so propagation time keeps invariable.(3)
Assume that clock skew (f) has no obvious changes and is known within one round of time-stamp exchange. The hypothesis is supported by two reasons. (a) Clock drift (variation of the clock frequency), which reflects the stability of crystal oscillator, is the second derivative of the clock. It has little influences on clock, so the relative clock skew (f) is slowly time-varying and we may think that clock skew (f) has no obvious changes in one synchronization period. From the point of control theory, the relative skew (f) can be processed by system identification parameter estimation. (b) References [8, 9] 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 variable delay is the Gauss distribution, but also apply to the case where the variable delay is the exponential distribution.Figure 1
Two-way timing message exchange between two nodes.


### 2.1. Clock Synchronization State Space Model without Packet Loss

In this paper, we may think that relative clock skew (f) has no obvious changes within one round of time-stamp exchange (emphasized in the third point above). So (1), which only has two unknown parameters, can be transformed into(2)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:(3)T2,kf-T1,kT4,k-T3,kf=11f1-1fτθ+XkYk.Equation (3) can be further simplified to(4)UkVk=11f1-1fτθ+XkYk,where Uk=T2,k/f-T1,k and Vk=T4,k-T3,k/f.Define(5)xk=τθ,C=11f1-1f,yk=UkVk,υk=XkYk,so (4) can also be written as(6)yk=Cxk+υk.In this paper, the random delay obeys independent identically distributed Gaussian distributions, which have been confirmed above, so it is assumed that its mean is zero and correlation matrix of the covariance isE[υkυkT]=R>0, which is a diagonal matrix.For (6), we describe all parameters as follows.(1)
We regard two unknown parameters, fixed delayτ and relative clock offset θ, as clock synchronization state x between synchronization node (namely, Node A in Figure 1) and the reference node (Node B in Figure 1).(2)
After exchanging the time-stamp information between synchronization node and reference node,T1,k,T2,k,T3,k,T4,kk=1N obtained are viewed as the measurement information of fixed delay and relative clock offset, namely, y∈y1,…,yk.(3)
Affected by the variable delay between nodes, the measurement informationy∈y1,…,yk cannot accurately reflect the fixed delay and relative clock offset information, and the error covariance is υk. This is equivalent to the fact that we measured unknown things and the measurement information affected by instruments, environment, and methods of measurement has some errors with the true values. We call the errors measurement noises.To sum up, (6) is described as follows. When measuring the unknown state xk, measurement yk (time-stamp information T1,k,T2,k,T3,k,T4,k) is influenced by the noise υk (the variable portion of delays). In this paper, the equation is treated as the measurement equation.Next, we analyze the unknown statex.(1)
The statex is a two-dimensional vector and includes two unknown parameters, which are fixed delay τ and relative clock offset θ.(2)
Clock model of sensor node is a linear function of timet, Ci(t)=θ+f·t [1], where θ and f, respectively, represent clock offset (phase difference) and clock skew (frequency difference). Modeling the clock relationship for the first order linear function is mainly due to neglecting the effect of clock drift on the clock. Clock drift (variation of the clock frequency), which reflects the stability of crystal oscillator, is the second derivative of the clock. So it has little influences on clock, and we may ignore its influence.(3)
In addition, fixed delay between nodes including transmission delay, propagation delay, and reception delay is related to the power of transceiver, the length of data packet, and the distance between the nodes. Generally, it can be considered to be fixed within one round of time-stamp exchange.Considering the three aspects above, we assume that the state of clock synchronization between synchronization node and the reference node changes slowly, and the present state linearly relates to the state in previous time instance [19, 21, 22]. Therefore, unknown state is built as a Gauss-Markov dynamic model:(7)xk=xk-1+ωk-1,where interference part ωk-1 is modeled as a Gaussian distribution with mean zero and correlation matrix E[ωkωkT]=Q≥0. Assume that the initial state x0 also obeys the Gauss distribution with mean zero and covariance P0. In order to facilitate the subsequent research, (7) is rewritten into(8)xk=Axk-1+ωk-1.Of course, matrixA is an identity matrix. We call (8) the system state equation of clock synchronization between synchronization node and the reference node.We need to explain that the coefficient matrixA, measurement matrix C, and the variance of noises Q and R in the model are assumed to be known and fixed. It is convenient to the analysis and study. But in the actual environment, the network is complex and changeable, and the local clock is easily influenced by environment and other unpredictable interference, and so forth, so it needs to make the corresponding adjustment according to the actual situation. In the paper, the constant coefficient is treated as an example, without generality.Above we build the clock synchronization state space model of synchronization node and the reference node, where two nodes are not isolated but are regarded as a whole, forming an orderly system. So, from the point of system, clock synchronization process based on two-way information exchange of sender-receiver can be interpreted as follows (shown as in Figure2): establish the unknown state xk; then by sending a synchronous request, obtain the measurement information yk of unknown state; finally, according to the measurement information, estimate the unknown state and revise the clock of node.Figure 2
Clock synchronization process of message exchange.


### 2.2. Latest Developments in the Clock Synchronization State Space Model

Reference [10] established the accumulated clock offset and skew evolution model and expanded the model to sensors network with multiple nodes. Reference [10] 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 ((6) and (8)) and the state space model of [10] have a similar form, but there are still some differences. (a) In this paper, the state vector is a matrix form about the relative clock offset and fixed delay, and, in [10], about the clock skew and accumulated clock offset. (b) In this paper, measurement model (6) directly considers the clock skew, and, in [10], the localized timestamp measurement model considers the relationship between the timestamps and the accumulated clock offset. (c) In the paper, the clock offset of the model is relative to neighboring node and in [10] the clock relationship is between one node and the only reference node in the entire network.Among literatures about the clock synchronization, there is little study related to synchronization error variance analysis and design issues proposed in this paper. In addition, variety and complexity of large-scale networks take some difficulties for synchronization error variance analysis and design issues presented in the paper. However, [10] proposed an efficient algorithm to solve the clock synchronization problem of large-scale and distributed network. Therefore, in order to simplify the study of problem and go deep into the essence of problem, the paper firstly uses two nodes as a springboard and focuses on discussing the effect of packet loss on the synchronization error variance in detail, which includes analysis and design of synchronization error variance. After strictly discussing two nodes, we are extending the result to the network with many nodes based on [10].


### 2.3. Clock Synchronization State Space Model under Intermittent Observation

As above, we have regarded fixed delay and relative clock offset as the unknown parameters and established state space model, but the introduction of wireless network brings many unreliable factors for clock synchronization, such as network delay and packet loss. Obviously, exchanging clock synchronization information must be affected by these uncertain factors. Thereby the estimation of clock synchronization parameters is affected. In this paper, due to adopting the clock synchronization mechanism of two-way message exchange, where one round 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 round is thought of as exchange of failure, namely, packet loss, shown as in Figure3. If the time-stamp information T1,k,T2,k,T3,k,T4,k arrives at Node A, we think that the information exchange is successful. That is to say that Node A receives the measurement information yk successfully.Figure 3
Clock synchronization process with intermittent observations.In the following, we will consider how to modify models (6) and (8) in two cases mentioned above; namely, Node A receives intermittent observations.In the first case, as shown in Figure3, network packet loss is considered. Let γk be the random variable indicating whether measurement information yk is dropped at time k or not, so γk=0 if the packet is dropped and γk=1 otherwise. We assume γk is an i.i.d Bernoulli random variable [23–25] with p(γk=1)=λ. λ represents the probability that the time-stamp information arrives at Node A, in short packet arrival rate.In the second case, there is no packet loss in sensor network. Measurement information always successfully arrives at Node A, but in one round of clock information exchange, there is a fixed unit energyΔ. Let γk be the random variable indicating that Node A freely schedules whether it exchanges clock information at time k or not, so γk=1 if Node A exchanges clock information and γk=0 otherwise. It is similar to the first case that we assume γk is an i.i.d Bernoulli random variable with p(γk=1)=λ. Herein, λ represents the probability that clock information is exchanged between Node A and Node B in one period of the clock synchronization, in short the packet exchange rate.From the above description,λ represents different meanings in the two cases. But in fact, we may transform the angle and we can uniformly think two cases are equivalent from the perspective of absence of clock information.Therefore, for the two cases have been mentioned above, we modify clock synchronization state space models (6)  and (8) and obtain the following clock synchronization state space model with intermittent observations:(9)xk=Axk-1+ωk-1,(10)yk=γkCxk+υ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 exchanges. If, in every one-way message exchange between two nodes, events of packet loss are independent of each other, the probabilities are not necessarily equal to each other, so we may use a matrix to describe communication situations, and it is given by(11)γ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 ranges are 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 [17]. But no matter how we build the model of packet loss, we still adapt the form described in (10), because it is more simple and it abstracts the event of packet loss.So far, we have established the clock synchronization state space model under intermittent observation, tracking clock state. However, due to the randomness of packet loss, the synchronization error variance is a random variable, which maybe exceeds the designed boundary of the synchronization variance. This does not make some applications depending on clock consistency work normally. Thus, we will discuss the analysis and design issues between the synchronization error variance and packet loss rate based on a unified framework of the clock synchronization state space model in the following work.


## 2.1. Clock Synchronization State Space Model without Packet Loss

In this paper, we may think that relative clock skew (f) has no obvious changes within one round of time-stamp exchange (emphasized in the third point above). So (1), which only has two unknown parameters, can be transformed into(2)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:(3)T2,kf-T1,kT4,k-T3,kf=11f1-1fτθ+XkYk.Equation (3) can be further simplified to(4)UkVk=11f1-1fτθ+XkYk,where Uk=T2,k/f-T1,k and Vk=T4,k-T3,k/f.Define(5)xk=τθ,C=11f1-1f,yk=UkVk,υk=XkYk,so (4) can also be written as(6)yk=Cxk+υk.In this paper, the random delay obeys independent identically distributed Gaussian distributions, which have been confirmed above, so it is assumed that its mean is zero and correlation matrix of the covariance isE[υkυkT]=R>0, which is a diagonal matrix.For (6), we describe all parameters as follows.(1)
We regard two unknown parameters, fixed delayτ and relative clock offset θ, as clock synchronization state x between synchronization node (namely, Node A in Figure 1) and the reference node (Node B in Figure 1).(2)
After exchanging the time-stamp information between synchronization node and reference node,T1,k,T2,k,T3,k,T4,kk=1N obtained are viewed as the measurement information of fixed delay and relative clock offset, namely, y∈y1,…,yk.(3)
Affected by the variable delay between nodes, the measurement informationy∈y1,…,yk cannot accurately reflect the fixed delay and relative clock offset information, and the error covariance is υk. This is equivalent to the fact that we measured unknown things and the measurement information affected by instruments, environment, and methods of measurement has some errors with the true values. We call the errors measurement noises.To sum up, (6) is described as follows. When measuring the unknown state xk, measurement yk (time-stamp information T1,k,T2,k,T3,k,T4,k) is influenced by the noise υk (the variable portion of delays). In this paper, the equation is treated as the measurement equation.Next, we analyze the unknown statex.(1)
The statex is a two-dimensional vector and includes two unknown parameters, which are fixed delay τ and relative clock offset θ.(2)
Clock model of sensor node is a linear function of timet, Ci(t)=θ+f·t [1], where θ and f, respectively, represent clock offset (phase difference) and clock skew (frequency difference). Modeling the clock relationship for the first order linear function is mainly due to neglecting the effect of clock drift on the clock. Clock drift (variation of the clock frequency), which reflects the stability of crystal oscillator, is the second derivative of the clock. So it has little influences on clock, and we may ignore its influence.(3)
In addition, fixed delay between nodes including transmission delay, propagation delay, and reception delay is related to the power of transceiver, the length of data packet, and the distance between the nodes. Generally, it can be considered to be fixed within one round of time-stamp exchange.Considering the three aspects above, we assume that the state of clock synchronization between synchronization node and the reference node changes slowly, and the present state linearly relates to the state in previous time instance [19, 21, 22]. Therefore, unknown state is built as a Gauss-Markov dynamic model:(7)xk=xk-1+ωk-1,where interference part ωk-1 is modeled as a Gaussian distribution with mean zero and correlation matrix E[ωkωkT]=Q≥0. Assume that the initial state x0 also obeys the Gauss distribution with mean zero and covariance P0. In order to facilitate the subsequent research, (7) is rewritten into(8)xk=Axk-1+ωk-1.Of course, matrixA is an identity matrix. We call (8) the system state equation of clock synchronization between synchronization node and the reference node.We need to explain that the coefficient matrixA, measurement matrix C, and the variance of noises Q and R in the model are assumed to be known and fixed. It is convenient to the analysis and study. But in the actual environment, the network is complex and changeable, and the local clock is easily influenced by environment and other unpredictable interference, and so forth, so it needs to make the corresponding adjustment according to the actual situation. In the paper, the constant coefficient is treated as an example, without generality.Above we build the clock synchronization state space model of synchronization node and the reference node, where two nodes are not isolated but are regarded as a whole, forming an orderly system. So, from the point of system, clock synchronization process based on two-way information exchange of sender-receiver can be interpreted as follows (shown as in Figure2): establish the unknown state xk; then by sending a synchronous request, obtain the measurement information yk of unknown state; finally, according to the measurement information, estimate the unknown state and revise the clock of node.Figure 2
Clock synchronization process of message exchange.


## 2.2. Latest Developments in the Clock Synchronization State Space Model

Reference [10] established the accumulated clock offset and skew evolution model and expanded the model to sensors network with multiple nodes. Reference [10] 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 ((6) and (8)) and the state space model of [10] have a similar form, but there are still some differences. (a) In this paper, the state vector is a matrix form about the relative clock offset and fixed delay, and, in [10], about the clock skew and accumulated clock offset. (b) In this paper, measurement model (6) directly considers the clock skew, and, in [10], the localized timestamp measurement model considers the relationship between the timestamps and the accumulated clock offset. (c) In the paper, the clock offset of the model is relative to neighboring node and in [10] the clock relationship is between one node and the only reference node in the entire network.Among literatures about the clock synchronization, there is little study related to synchronization error variance analysis and design issues proposed in this paper. In addition, variety and complexity of large-scale networks take some difficulties for synchronization error variance analysis and design issues presented in the paper. However, [10] proposed an efficient algorithm to solve the clock synchronization problem of large-scale and distributed network. Therefore, in order to simplify the study of problem and go deep into the essence of problem, the paper firstly uses two nodes as a springboard and focuses on discussing the effect of packet loss on the synchronization error variance in detail, which includes analysis and design of synchronization error variance. After strictly discussing two nodes, we are extending the result to the network with many nodes based on [10].


## 2.3. Clock Synchronization State Space Model under Intermittent Observation

As above, we have regarded fixed delay and relative clock offset as the unknown parameters and established state space model, but the introduction of wireless network brings many unreliable factors for clock synchronization, such as network delay and packet loss. Obviously, exchanging clock synchronization information must be affected by these uncertain factors. Thereby the estimation of clock synchronization parameters is affected. In this paper, due to adopting the clock synchronization mechanism of two-way message exchange, where one round 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 round is thought of as exchange of failure, namely, packet loss, shown as in Figure3. If the time-stamp information T1,k,T2,k,T3,k,T4,k arrives at Node A, we think that the information exchange is successful. That is to say that Node A receives the measurement information yk successfully.Figure 3
Clock synchronization process with intermittent observations.In the following, we will consider how to modify models (6) and (8) in two cases mentioned above; namely, Node A receives intermittent observations.In the first case, as shown in Figure3, network packet loss is considered. Let γk be the random variable indicating whether measurement information yk is dropped at time k or not, so γk=0 if the packet is dropped and γk=1 otherwise. We assume γk is an i.i.d Bernoulli random variable [23–25] with p(γk=1)=λ. λ represents the probability that the time-stamp information arrives at Node A, in short packet arrival rate.In the second case, there is no packet loss in sensor network. Measurement information always successfully arrives at Node A, but in one round of clock information exchange, there is a fixed unit energyΔ. Let γk be the random variable indicating that Node A freely schedules whether it exchanges clock information at time k or not, so γk=1 if Node A exchanges clock information and γk=0 otherwise. It is similar to the first case that we assume γk is an i.i.d Bernoulli random variable with p(γk=1)=λ. Herein, λ represents the probability that clock information is exchanged between Node A and Node B in one period of the clock synchronization, in short the packet exchange rate.From the above description,λ represents different meanings in the two cases. But in fact, we may transform the angle and we can uniformly think two cases are equivalent from the perspective of absence of clock information.Therefore, for the two cases have been mentioned above, we modify clock synchronization state space models (6)  and (8) and obtain the following clock synchronization state space model with intermittent observations:(9)xk=Axk-1+ωk-1,(10)yk=γkCxk+υ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 exchanges. If, in every one-way message exchange between two nodes, events of packet loss are independent of each other, the probabilities are not necessarily equal to each other, so we may use a matrix to describe communication situations, and it is given by(11)γ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 ranges are 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 [17]. But no matter how we build the model of packet loss, we still adapt the form described in (10), because it is more simple and it abstracts the event of packet loss.So far, we have established the clock synchronization state space model under intermittent observation, tracking clock state. However, due to the randomness of packet loss, the synchronization error variance is a random variable, which maybe exceeds the designed boundary of the synchronization variance. This does not make some applications depending on clock consistency work normally. Thus, we will discuss the analysis and design issues between the synchronization error variance and packet loss rate based on a unified framework of the clock synchronization state space model in the following work.


## 3. Synchronization Error Variance Analysis and Design

In Section1, we have introduced that this paper researched clock synchronization issues from the point of the synchronization error variance. On the one hand, in the packet-dropping network, the synchronization error variance is a random variable. Existing studies about the clock synchronization primarily focused on the design of the synchronization estimation algorithm to improve the estimation error variance. But they rarely analyze the random distribution of synchronization error variance, let alone the analysis and design issues of synchronization error variance beyond the designed boundary of the synchronization variance (or the probability of synchronization error variance beyond the designed boundary of the synchronization variance). Therefore, the research on synchronization error variance is more necessary. On the other hand, the different application backgrounds have different requirements for synchronization error variance in reality. How could we ensure that the synchronization error variance is within the designed error variance border? How could we reasonably reduce the synchronization error variance with a limited resource? Thus, the research on synchronization error variance also has practical significance.In the following, we begin to analyze two cases mentioned above in this paper.Firstly, we define the following synchronization state qualities at synchronization node:(12)x^k≜Exk∣γ1y1,…,γkyk,Pk≜Exk-x^kxk-x^kT∣γ1y1,…,γkyk.The random variableγk is 0 or 1, representing whether the synchronization node has received the measurement information yk. The matrix Pk is the state estimation error variance, reflecting the estimation precision. The error between estimation state x^k and actual state value xk is smaller, while Pk is smaller.Because clock statexk contains clock error between two nodes, the estimation value x^k is much closer to actual value xk, which means that the estimation value of clock error is more precise. So, after adjusting, the synchronization error between two nodes is smaller, namely, the higher synchronization precision. Thus, the state estimation error variance matrix Pk could reflect synchronization precision, that is, the synchronization error variance in this paper.


### 3.1. Synchronization Error Variance Analysis

In the first case, for a wireless sensor network with packet loss, packet loss has a serious influence on clock state estimation of the synchronization node. The more the packet is lost, the greater the estimation error for the synchronization node is and the lower the clock synchronization precision is. Further, each of the sensor networks has different requirements of synchronization precision according to the different application backgrounds. When the clock synchronization error variance cannot meet the requirements of the desired precision, the network cannot guarantee the normal operation. Thus, if the network packet loss is too large, the synchronization error variance may exceed a desired variance boundary. At this time, we attempt to judge whether the conditions of existing network can meet the requirements of the desired synchronization error variance or not.The description of packet loss is as the introduction in the first case of Section2.3. Assume that we can observe the probability that clock information packets in network arrive at the synchronization node, and tentatively consider it is λ0. And the desired clock synchronization precision (the desired synchronization error variance) is Pdesired. Due to the introduction of random variable γk, the estimation error variance of the synchronization node is also a random variable (shown in Section 4.1). It is because Pk is a random quantity due to the randomness of γk, the synchronization error variance may go beyond the desired boundary of the synchronization variance. And because the value of Pk cannot be obtained offline, the statistical properties of the error variance are considered in this paper.Particularly, we are interested in the following questions.Question 1 (synchronization error variance analysis).
For any given synchronization precisionPdesired>0, find a minimum packet arrival rate λmin⁡, satisfying(13)limk→NEPk≤Pdesired,where N is the times of clock information exchanges in one period of synchronization.
As to the problem, we will begin with the following critical questions.(1)
Because the exact value oflimk→N⁡EPk is difficult to obtain, we discuss the certain upper boundary of limk→N⁡EPk when N→∞.(2)
Judge the relationship between the upper boundary and packet arrival rate.(3)
Look for the minimum packet arrival rate using a search algorithm.


### 3.2. Synchronization Error Variance Design

In the second case, there is no packet loss in sensor network, but the synchronization node freely schedules whether it exchanges clock information with the reference node. The more the clock information is exchanged, the higher the synchronization precision is, while the more the corresponding energy is consumed, which is not expected for sensor node whose energy is limited. So, for the sensor node, the energy consumption and synchronization precision are mutually restricted. At this point, how should we set up the network parameters to achieve the optimal tradeoff between energy consumption and synchronization precision at the synchronization node?In this issue, the detailed description of the unit energy consumptionΔ and the clock information packet exchange rate λ is introduced as the second case in Section 2.3.Then, we will research the following questions.Question 2 (synchronization error variance design).
Find an optimal clock information packet exchange rate between synchronization node and reference node, minimizing (minimizing the trace)(14)limk→NEPk+λΔ,where the first part represents the limitation of mean estimation error variance during the synchronization; the second part represents mean energy consumption during the synchronization process.
As to the problem, we will begin with the following critical questions.(1)
As(1) of Question 1, find the certain upper bound of limk→N⁡EPk when N→∞.(2)
Prove that there exists the minimum of the mathematical model (14).(3)
Obtain the solution form of the optimal clock information exchange rate that minimizes the mathematical model (14).


## 3.1. Synchronization Error Variance Analysis

In the first case, for a wireless sensor network with packet loss, packet loss has a serious influence on clock state estimation of the synchronization node. The more the packet is lost, the greater the estimation error for the synchronization node is and the lower the clock synchronization precision is. Further, each of the sensor networks has different requirements of synchronization precision according to the different application backgrounds. When the clock synchronization error variance cannot meet the requirements of the desired precision, the network cannot guarantee the normal operation. Thus, if the network packet loss is too large, the synchronization error variance may exceed a desired variance boundary. At this time, we attempt to judge whether the conditions of existing network can meet the requirements of the desired synchronization error variance or not.The description of packet loss is as the introduction in the first case of Section2.3. Assume that we can observe the probability that clock information packets in network arrive at the synchronization node, and tentatively consider it is λ0. And the desired clock synchronization precision (the desired synchronization error variance) is Pdesired. Due to the introduction of random variable γk, the estimation error variance of the synchronization node is also a random variable (shown in Section 4.1). It is because Pk is a random quantity due to the randomness of γk, the synchronization error variance may go beyond the desired boundary of the synchronization variance. And because the value of Pk cannot be obtained offline, the statistical properties of the error variance are considered in this paper.Particularly, we are interested in the following questions.Question 1 (synchronization error variance analysis).
For any given synchronization precisionPdesired>0, find a minimum packet arrival rate λmin⁡, satisfying(13)limk→NEPk≤Pdesired,where N is the times of clock information exchanges in one period of synchronization.
As to the problem, we will begin with the following critical questions.(1)
Because the exact value oflimk→N⁡EPk is difficult to obtain, we discuss the certain upper boundary of limk→N⁡EPk when N→∞.(2)
Judge the relationship between the upper boundary and packet arrival rate.(3)
Look for the minimum packet arrival rate using a search algorithm.


## 3.2. Synchronization Error Variance Design

In the second case, there is no packet loss in sensor network, but the synchronization node freely schedules whether it exchanges clock information with the reference node. The more the clock information is exchanged, the higher the synchronization precision is, while the more the corresponding energy is consumed, which is not expected for sensor node whose energy is limited. So, for the sensor node, the energy consumption and synchronization precision are mutually restricted. At this point, how should we set up the network parameters to achieve the optimal tradeoff between energy consumption and synchronization precision at the synchronization node?In this issue, the detailed description of the unit energy consumptionΔ and the clock information packet exchange rate λ is introduced as the second case in Section 2.3.Then, we will research the following questions.Question 2 (synchronization error variance design).
Find an optimal clock information packet exchange rate between synchronization node and reference node, minimizing (minimizing the trace)(14)limk→NEPk+λΔ,where the first part represents the limitation of mean estimation error variance during the synchronization; the second part represents mean energy consumption during the synchronization process.
As to the problem, we will begin with the following critical questions.(1)
As(1) of Question 1, find the certain upper bound of limk→N⁡EPk when N→∞.(2)
Prove that there exists the minimum of the mathematical model (14).(3)
Obtain the solution form of the optimal clock information exchange rate that minimizes the mathematical model (14).


## 4. Preliminaries

As can be seen from the analysis of the above two sections, the key in the clock synchronization process is that, according to measurementyk received, the synchronization node estimates an unknown clock state xk with the reference node and then corrects the local clock, making it consistent with the reference node. Therefore, the estimation error variance determines the precision of the clock synchronization. For the two issues in the paper, we define the criteria with state estimation and estimation error variance as shown in (12).


### 4.1. Kalman Filtering under Intermittent Observations

In the case ofγk=1, it is obvious that the standard Kalman filter is the optimal linear state estimation, for the clock synchronization state space models (9) and (10), where state estimation process is divided into two steps, namely, innovation step (prediction step) and correction step (update step). It is easy to write the recursive formula of standard Kalman filter [26].However, for the two issues of the paper, it is not really that the synchronization node gets all of the clock informationyk. When some of yk are lost, it will affect the state estimation of the synchronization node. Reference [2] showed that the Kalman filter is still the optimal linear estimator in the setting when possibly γk=0. It is different from the standard Kalman filter that only the innovation step is performed when a measurement packet is dropped. And the modification of the Kalman filter equations is given as follows:(15)x^k∣k-1=Ax^k-1,(16)Pk∣k-1=APk-1AT+Q,(17)x^k=Ax^k-1+γkKkalyk-CAx^k-1,(18)ek=xk-x^k=I-γkKkalCAek-1-γkKkalυk+I-γkKkalCωk-1,(19)Pk=(1-γk)(APk-1AT+Q)+γkI-KkalCAPk-1AT+QI-KkalCTmmmmmc+KkalRKkalT=Pk∣k-1-γkKkalCPk∣k-1,(20)Kkal=Pk∣k-1CTCPk∣k-1CT+R-1.Unlike the standard Kalman filter where Pk is deterministic for any given initial value P0, the randomness of the packets loss γk makes Pk a random variable as well.


### 4.2. Kalman Filtering in the Statistical Property

Since{γk}1k is a random sequence, the estimation error variance matrix Pk is also stochastic and cannot be determined offline. In this paper, the statistical properties of the error variance are considered. For the modified Kalman filter, the estimation error in the statistical property can be expressed as(21)e-k=Eλ(ek)=I-λKkalCAe-k-1-λKkalυk+I-λKkalCωk-1,where E[γk]=λ represents the expectation of random sequence {γk}1k. In Question 1 (clock synchronization analysis issue), λ indicates the clock information packet arrival rate, while in Question 2 (clock synchronization design issue), it denotes the clock information packet exchange rate.The steady-state error variance about (21) is defined as(22)P-=limk→∞Pk=limk→∞Eλ[ekekT].Now the concept of asymptotic stability in the error system is extended to the case containing packet loss. The definition of asymptotic stability in the error system is given in the statistical property.Definition 1.
For the expectationλ with a given random sequence {γk}1k, if the state estimation error (21) in the statistical property is Lyapunov asymptotically stable, it is called that the state estimation error (18) of Kalman filter in the statistical property is asymptotically stable, and the corresponding steady-state error covariance of Kalman filter P- satisfies(23)P-=1-λAP-AT+Q+λ·I-KkalCAP-AT+QI-KkalCT+KkalRKkalT.Note that Pr⁡[Pkbounded]=1 if and only if E[Pk] is bounded, so we mainly study the expected error variance E[Pk]=E[E[Pk∣Pk-1]] and E[Pk∣Pk-1] is the expectation of γk.In order to solve synchronization error variance analysis and design issues in this paper, we need to use a basic conclusion.Consider the following function:(24)ϕK,X=(1-λ)(AXAT+Q)+λI-KCAXAT+QI-KCT+KRKT.Lemma 2 (see [27]).
Under intermittent observations, there is a Kalman gainK which makes the system asymptotically stable, if and only if inequality of the matrix variable X(25)X>ϕ(K,X)exists positive-definite solutions. And steady-state error variance P of corresponding K satisfies(26)P=inf⁡XΩK,where Ω(K)={X∣X>ϕ(K,X),X>0}.Since Kalman filter is the optimal linear estimator, the error varianceP- of which is minimum, it satisfies P-<P for all P,K∈Ω=P,K∣X>ϕ(P,X),P>0 and P- is the infimum of Ω. And the corresponding Kalman gain is Kkal.


### 4.3. Definitions of Notation

In order to facilitate the following study of synchronization error variance analysis and design issues, the related formulas and notation are simplified in this section. Suppose(A,C,Q,R) is the same as described in Section 2. If the matrix X is positive definite, we write X>0. We define the following functions as [15](27)hX≜AXAT+Q,g~X≜X-XCTCXCT+R-1CX,g(X)≜g~(h(X)).Compared with the standard Kalman filtering, it can be easily seen that the functionh is a prediction step function of estimation error variance in the standard Kalman filter. And the function g represents an update step function of estimation error variance in the standard Kalman filter.Therefore, estimation error variance equations of the standard Kalman filter can be expressed using the above-defined function as follows:(28)Pk∣k-1=h(Pk-1),Pk=g~(h(Pk-1))=g(Pk-1).Steady-state error variance P- of the modified Kalman filter can be written as(29)P-=(1-λ)h(P-)+λg(P-).Namely, P- is the unique solution of the following equation:(30)X=1-λhX+λgX.


## 4.1. Kalman Filtering under Intermittent Observations

In the case ofγk=1, it is obvious that the standard Kalman filter is the optimal linear state estimation, for the clock synchronization state space models (9) and (10), where state estimation process is divided into two steps, namely, innovation step (prediction step) and correction step (update step). It is easy to write the recursive formula of standard Kalman filter [26].However, for the two issues of the paper, it is not really that the synchronization node gets all of the clock informationyk. When some of yk are lost, it will affect the state estimation of the synchronization node. Reference [2] showed that the Kalman filter is still the optimal linear estimator in the setting when possibly γk=0. It is different from the standard Kalman filter that only the innovation step is performed when a measurement packet is dropped. And the modification of the Kalman filter equations is given as follows:(15)x^k∣k-1=Ax^k-1,(16)Pk∣k-1=APk-1AT+Q,(17)x^k=Ax^k-1+γkKkalyk-CAx^k-1,(18)ek=xk-x^k=I-γkKkalCAek-1-γkKkalυk+I-γkKkalCωk-1,(19)Pk=(1-γk)(APk-1AT+Q)+γkI-KkalCAPk-1AT+QI-KkalCTmmmmmc+KkalRKkalT=Pk∣k-1-γkKkalCPk∣k-1,(20)Kkal=Pk∣k-1CTCPk∣k-1CT+R-1.Unlike the standard Kalman filter where Pk is deterministic for any given initial value P0, the randomness of the packets loss γk makes Pk a random variable as well.


## 4.2. Kalman Filtering in the Statistical Property

Since{γk}1k is a random sequence, the estimation error variance matrix Pk is also stochastic and cannot be determined offline. In this paper, the statistical properties of the error variance are considered. For the modified Kalman filter, the estimation error in the statistical property can be expressed as(21)e-k=Eλ(ek)=I-λKkalCAe-k-1-λKkalυk+I-λKkalCωk-1,where E[γk]=λ represents the expectation of random sequence {γk}1k. In Question 1 (clock synchronization analysis issue), λ indicates the clock information packet arrival rate, while in Question 2 (clock synchronization design issue), it denotes the clock information packet exchange rate.The steady-state error variance about (21) is defined as(22)P-=limk→∞Pk=limk→∞Eλ[ekekT].Now the concept of asymptotic stability in the error system is extended to the case containing packet loss. The definition of asymptotic stability in the error system is given in the statistical property.Definition 1.
For the expectationλ with a given random sequence {γk}1k, if the state estimation error (21) in the statistical property is Lyapunov asymptotically stable, it is called that the state estimation error (18) of Kalman filter in the statistical property is asymptotically stable, and the corresponding steady-state error covariance of Kalman filter P- satisfies(23)P-=1-λAP-AT+Q+λ·I-KkalCAP-AT+QI-KkalCT+KkalRKkalT.Note that Pr⁡[Pkbounded]=1 if and only if E[Pk] is bounded, so we mainly study the expected error variance E[Pk]=E[E[Pk∣Pk-1]] and E[Pk∣Pk-1] is the expectation of γk.In order to solve synchronization error variance analysis and design issues in this paper, we need to use a basic conclusion.Consider the following function:(24)ϕK,X=(1-λ)(AXAT+Q)+λI-KCAXAT+QI-KCT+KRKT.Lemma 2 (see [27]).
Under intermittent observations, there is a Kalman gainK which makes the system asymptotically stable, if and only if inequality of the matrix variable X(25)X>ϕ(K,X)exists positive-definite solutions. And steady-state error variance P of corresponding K satisfies(26)P=inf⁡XΩK,where Ω(K)={X∣X>ϕ(K,X),X>0}.Since Kalman filter is the optimal linear estimator, the error varianceP- of which is minimum, it satisfies P-<P for all P,K∈Ω=P,K∣X>ϕ(P,X),P>0 and P- is the infimum of Ω. And the corresponding Kalman gain is Kkal.


## 4.3. Definitions of Notation

In order to facilitate the following study of synchronization error variance analysis and design issues, the related formulas and notation are simplified in this section. Suppose(A,C,Q,R) is the same as described in Section 2. If the matrix X is positive definite, we write X>0. We define the following functions as [15](27)hX≜AXAT+Q,g~X≜X-XCTCXCT+R-1CX,g(X)≜g~(h(X)).Compared with the standard Kalman filtering, it can be easily seen that the functionh is a prediction step function of estimation error variance in the standard Kalman filter. And the function g represents an update step function of estimation error variance in the standard Kalman filter.Therefore, estimation error variance equations of the standard Kalman filter can be expressed using the above-defined function as follows:(28)Pk∣k-1=h(Pk-1),Pk=g~(h(Pk-1))=g(Pk-1).Steady-state error variance P- of the modified Kalman filter can be written as(29)P-=(1-λ)h(P-)+λg(P-).Namely, P- is the unique solution of the following equation:(30)X=1-λhX+λgX.


## 5. Synchronization Error Variance Analysis

In this section, we consider Question1 (synchronization error variance analysis issue) shown as the description in Section 3.1.Firstly, we consider the limited caseN→∞. It is mainly because the time of clock information exchanges is not determined in the process of synchronization and depends on two aspects: the design of synchronization algorithm and the setting of the desired synchronization variance. On the one hand, using high precision synchronization algorithm, the time of clock information exchanges is smaller. On the other hand, if the requirement of synchronization precision is different, the time of clock information exchanges is also different. In fact, there exist some limitations when discussing N→∞, but it has great value of the theoretical research.(1)
For anyN, limk→∞⁡E[Pk] is the low bound of limk→N⁡E[Pk].(2)
If we can find a minimum clock information packet arrival rateλmin⁡, satisfying limk→∞⁡E[Pk]≤Pdesired when N→∞, then the λmin⁡ is also treated as the minimum clock information packet arrival rate, satisfying limk→N⁡E[Pk]≤Pdesired.So in the section, we look for a minimum clock information packet arrival rateλmin⁡, satisfying limk→N⁡E[Pk]≤Pdesired for N→∞.However, unfortunately, it turns out that the exact value ofE[Pk] is difficult to find ever for scalar systems [2].(
1
) But we can find the upper bound of E[Pk] as follows:(31)EPk=EEPk∣Pk-1=EϕKkal,Pk-1=E1-λAPk-1AT+QI-KkalCT+KkalRKkalTmmmc+λI-KkalCAPk-1AT+Qmmmmmmc·I-KkalCT+KkalRKkalT=E1-λAPk-1AT+Q+EλI-KkalCAPk-1AT+QmmmmmcPk-1AT·I-KkalCT+KkalRKkalT=1-λEhPk-1+λEgPk-1≤1-λhE[Pk-1]+λgE[Pk-1],where the first equation is obtained due to the property of conditional expectation, and the inequality is because gX is a concave function of X (Lemma  1-e [2]) and Jensen inequality is used.According to (29), it can be seen that steady-state error variance P-λ in the Kalman filter is the unique solution to the following equation:(32)X=1-λhX+λgX.Use induction for inequality (31) and the limit is taken (proof process in detail appears in Appendix A), so it is easy to get(33)limk→∞EPk≤P-λ.(
2
) According to (33), only if we look for the minimum clock information packet arrival rate λmin⁡, satisfying(34)P-λ≤Pdesired,so,limk→∞EPk≤Pdesiredwill be guaranteed.To sum up, forN→∞, the synchronization error variance analysis issue is equivalent to looking for the minimum clock information packet arrival rate λmin⁡, making(35)P-λ≤Pdesired.(
3
) Then, we need to determine the function relationship between P-λ and λ such that the minimum clock information packet arrival rate λmin⁡ is found.Theorem 3.
For any given clock information packet arrival rateλ∈0,1, steady-state error variance P-λ of the Kalman filter is a monotonically decreasing function of λ.Proof.
For the packet arrival rateλ1 and Kalman gain K1, the steady-state error variance P-λ of the Kalman filter satisfies the following equation (from (23)):(36)P-λ1=1-λ1AP-λ1AT+Q+λ1I-K1CAP-λ1AT+QI-K1CTK1TmmmmmcAP-λ1AT+QI-K1CT+K1RK1T=AP-λ1AT+Q+λ1·I-K1CAP-λ1AT+QI-K1CT+K1RK1T-AP-λ1AT+Q.
For the Kalman filter, the steady-state estimation error variance is less than or equal to the estimation error variance of prediction step, that is,(37)I-KCAP-AT+QI-KCT+KRKT≤AP-AT+Q.For any λ1<λ2,(38)P-λ1≥AP-λ1AT+Q+λ2·I-K1CAP-λ1AT+QI-K1CT+K1RK1T-AP-λ1AT+Q.
If the above inequality takes the equality, it showsP-λ is equal in the case of λ1 and in the case of λ2, so P-λ1=P-λ2. If the inequality excludes the part of the equality, then (39)P-λ1>AP-λ1AT+Q+λ2·I-K1CAP-λ1AT+Q·I-K1CT+K1RK1T-AP-λ1AT+Q.
According to Lemma2, we know in the case of packet arrival rate λ2 any solution K,P of the inequality(40)P>APAT+Q+λ2·I-KCAPAT+QI-KCT+KRKT-APAT+Qhas P-λ2<P. This is because the Kalman filter is the optimal linear estimator and is the minimum value of all of the solution space above.
Contrasting inequalities (39) and (40), it can be seen that (P-λ1,K1) is a set of solutions at a packet arrival rate λ2, so we judge P-λ1>P-λ2. K2 is the Kalman gain in the case where packet arrival rate is λ2.
Therefore, the steady-state error varianceP-λ of the Kalman filter is a monotonically decreasing function of packet arrival rate λ.(
4
) Because P-λ is a monotonically decreasing function of λ, where λ∈0,1, for any given Pdesired>0, the minimum λmin⁡, which satisfies(41)P-λ≤Pdesired,can be efficiently found through the bisection search algorithm. The bisection search algorithm is a common search algorithm which has the good characteristic of search speed and mean performance. The specific idea of the algorithm can be found in [28].


## 6. Synchronization Error Variance Design

During the synchronization process, increasing the transmit power of sensor nodes can reduce the packet loss rate, and the synchronization nodes can obtain more clock information, so the estimation of clock parameters will be more accurate at the synchronization node. However, increasing the transmission power increases the corresponding energy consumption of the sensor nodes.Since the transmission power of sensor node has an impact on the packet loss rate and packet loss rate also affects the synchronization precision, how should we adjust transmission power of sensor node to make the clock synchronization estimation variance as small as possible? In other words, if there are multiple levels of transmission power, how should we schedule the transmission power of sensor node in order to improve synchronization precision as soon as possible with limited energy? At this point, in order to improve synchronization precision as much as possible, we will design the optimal transmission power scheduling sequence with the restriction condition of limited energy.It is as any research which needs a gradually in-depth process that, in order to achieve the purpose, we firstly need to fully understand the relationship between energy consumption and synchronization precision and, after all, the energy consumption and synchronization precision are mutually restricted. The more the clock information is exchanged, the more the corresponding energy is consumed, while the smaller the estimation error is. The different application backgrounds have different requirements for synchronization precision in wireless sensor networks and have different restrictions of the energy. The ideal situation is that we can achieve high synchronization precision and do not consume too much energy. Therefore, in order to further have more in-depth understanding of the mutually restricted relationship between energy consumption and synchronization precision, we firstly treat energy consumption and synchronization precision with the same importance in the paper. After comprehending the essential relationship between both, we will further extend to the generality.So, this paper firstly discusses the case where there is no packet loss in sensor networks, but the synchronization sensor node freely schedules whether it exchanges clock information with the reference node. Assuming the energy consumption in one round of clock information exchange for sensor nodes is fixed, the more the clock information is exchanged, the higher the synchronization precision is, while the more the corresponding energy is consumed. On the one hand, we expect that the sensor nodes can consume as little energy as possible; on the other hand, we hope that the clock synchronization precision is as high as possible. At this point, we attempt to reasonably adjust parameters in order to achieve the optimal tradeoff between energy consumption and synchronization precision at synchronization node.Now, we discuss the proposed design issues of synchronization error variance, shown as in Section3.2 described.(1)
Firstly, we consider the performance metric as follows, which reflects the relationship between clock synchronization precision and energy consumption:(42)limk→NEPk+λΔ,where the first part represents the mean estimation error variance in the process of clock synchronization, which determines the clock synchronization precision; the second part represents mean energy consumption in the process of clock synchronization.(2)
Then, seen from the above discussion about analysis issues, it is sure that (a) when discussingN→∞, it has some significance of the theoretical research; (b) limk→∞⁡EPk≤P-λ (33). So to minimize limk→N⁡EPk+λΔ (minimize the trace), we can replace it with minimizing P-λ+λΔ.(3)
In order to find an optimalλ, minimizing P-λ+λΔ, we need to judge the function property of P-λ+λΔ, where the function property of P-λ is critical. Because the function property of P-λ is not easy to be proved, we introduce the function P-λ-=AP-λAT+Q. By analyzing the property of the function P-λ-, we deeply judge the function property of P-λ. Firstly, we introduce the following lemmas. Omitted proofs appear in Appendix B.Define(1)
h(X)=AXAT+Q,(2)
g0=AXCTCXCT+R-1CXA,(3)
g-(X)=h(X)-g0(X).Lemma 4.
IfF(X) is a monotonically increasing function of X, AF(X)AT+Q is also a monotonically increasing function of X, where A is a diagonal matrix.Corollary 5.
ConsiderdP-λ/dλ≤0 and dP-λ-/dλ≤0.Lemma 6.
IfAF(X)AT+Q is a convex function of X, where A is a diagonal matrix, F(X) is a convex function of X.Lemma 7.
g
λ
(
X
)
=
A
X
A
T
+
Q
-
λ
A
X
C
T
(
C
X
C
T
+
R
)
-
1
C
X
A is a convex function of X, that is, gλ′′=h′′-λg0′′≥0, where h(X)=AXAT+Q and g0=AXCT(CXCT+R)-1CXA.Lemma 8.
g
λ
(
X
) is a monotonically increasing function of X, that is, gλ′=h′-λg0′≥0.Lemma 9.
Considerh(X)-g-(X)≥0.In the subsequent proof, for simplicity,F(X) is written as F; the derivative F′(X) of F(X) is written as F′; the second derivative F′′(X) of F(X) is written as F′′. In addition, h, g0, and gλ represent h(X), g0(X), and gλ(X), respectively.In(4) we have the following lemma.Lemma 10.
Ifλ∈0,1 and A, whose eigenvalues are not less than 1, is a diagonal matrix, P-λ- is a convex function of X, that is,(43)d2P-λ-dλ2≥0.Proof.
Consider the following equation:(44)X=1-λhX+λg-X,where P-λ- is the unique solution to the above equation.
Taking derivative on both sides of (44) with respect to λ leads to(45)dXdλ=-h+(1-λ)h′dXdλ+g-+λg-′dXdλ.After transposition, we obtain the following:(46)h-g-=[(1-λ)h′+λg-′-E]dXdλ,h-g-=h′-λg0′-EdXdλ.And because of Corollary 5 and Lemma 9, we get(47)h′-λg0′-E≤0.Taking again derivative on both sides of (46) with respect to λ leads to(48)(h′-g-′+g0′)dXdλ=h′′-λg0′′dXdλ2+h′-λg0′-Ed2Xdλ2.At the same time, according to (46) and (48), we have(49)2g0′(h-g-)h′-λg0′-E-1=(h′′-λg0′′)h-g-2h′-λg0′-E-12+h′-λg0′-Ed2Xdλ2.After transposition, we obtain the following:(50)(h′-λg0′-E)d2Xdλ2=2g0′h′-λg0′-E-h′′-λg0′′h-g-×(h-g-)h′-λg0′-E-12.According to Lemma 9, (47), and [(h′-λg0′-E)-1]2≥0, if we prove d2X/dλ2≥0, only we can prove(51)2g0′(h′-λg0′-E)-(h′′-λg0′′)(h-g-)≤0.And according to Lemma 7, Lemma 9, and (47), to prove (51) holds, we just need to prove(52)g0′≥0.Because of (47),(53)h′-E≤λg0′.Because h′(X)=AA′ and A, whose two eigenvalues are not less than 1, A is a diagonal matrix; therefore(54)h′(X)-E≥0.And because λ∈[0,1], (52) is set up; thus(55)d2Xdλ2>0.In other words, P-λ- is a convex function of λ.In(5) we have the following lemma.Lemma 11.
Ifλ∈0,1 and A, whose eigenvalues are not less than 1, is a diagonal matrix, P-λ is also a convex function of λ; that is, for any α∈(0,1), αP-λ1+(1-α)P-λ2≥P-αλ1+(1-α)λ2.Proof.
Firstly, from Lemma10, we have Pλ-=AP-λAT+Q which is a convex function of λ; then according to Lemma 6, Lemma 11 can be obtained.Next, we state a main result.In(6) we have the following theorem.Theorem 12.
λ
∗ which minimizes P-λ+λΔ can be obtained by solving the following two equations:(56)P-λ∗=1-λ∗h+λ∗g,(57)g-h=1-λh′+λ∗g′-EΔ.Proof.
Equation (56) can be obtained according to the definition. Because P-λ is a convex function of λ and λΔ is linear relationship with respect to λ, P-λ+λΔ is also a convex function of λ. Thus, P-λ+λΔ takes derivative of λ and then makes it equal to zero:(58)ddλ(P-λ+λΔ)=0,that is,(59)dP-λdλλ∗=-Δ.According to (46), λ∗ satisfies (57).
In one word, synchronization precision and energy consumption of sensor nodes are mutually restricted for clock synchronization. By solving the two equations (56) and (57), we can find an optimal clock information exchange rate, optimally trading off between synchronization precision and energy consumption of sensor nodes.


## 7. Simulation Analysis

In this section, for synchronization error variance analysis and design issues, we will simulate and illustrate the theories and algorithms proposed in the previous sections by some examples. Firstly, we start with analysis issue.


### 7.1. Analysis Issue

Consider the system parameters of clock synchronization state space model with(60)A=1001,C=111-1.Three graphs in Figure4 indicate the relationships between the trace of Kalman filter steady-state error variance Tr⁡P-λ (when k→∞) and clock packet arrival rate λ as well as the relationship between the mean error variance E[Pk] (when k→∞) and clock packet arrival rate λ with different circumstances of the system noise and the same observation noise as R=diag(10-3,10-3), where E[Pk] (when k→∞) is obtained by Monte Carlo simulation. As can be seen from the figure, with different system noise, Tr⁡P-λ is tight approximation to E[Pk] (when k→∞). And with the weakening of system noise, the effect of replacing E[Pk] with P-λ (when k→∞) approximately is more and more perfect. Two diagrams in Figures 5 and 4(b) represent that the observation noise is different and the system noise is the same as Q=diag(10-5,10-5). From the comparison of figures, the change of observation noise has no effect on the degree of approximation between Tr⁡P-λ and E[Pk] (when k→∞). Seen from the comparison and analysis of Figures 4 and 5, Tr⁡P-λ can be used to replace E[Pk] approximately (when k→∞), and Tr⁡P-λ is a monotonically decreasing function of λ. It shows again that the higher the probability that clock information arrives at the synchronization node is, the higher the precision of clock synchronization is.Figure 4
Mean error variance and clock information packet arrival rate with different circumstances of the system noise.
(a)
Q
=
diag
(
1
0
-
6
,
1
0
-
6
)
(b)
Q
=
diag
(
1
0
-
5
,
1
0
-
5
)
(c)
Q
=
diag
(
1
0
-
4
,
1
0
-
4
)Figure 5
Mean error variance and clock information packet arrival rate with different circumstances of the observation noise.
(a)
R
=
diag
(
1
0
-
2
,
1
0
-
2
)
(b)
R
=
diag
(
1
0
-
4
,
1
0
-
4
)Assume that the loop termination condition of bisection search algorithmε=0.01, the system noise correlation matrix Q=diag(10-5,10-5), and the observation noise correlation matrix R=diag(10-3,10-3). The simulation results show that the algorithm can obtain the minimum λ after five steps. For example, while Pdesired=1.5∗10-4∗I2, λ=0.5601; while Pdesired=2.5∗10-4∗I2, λ=0.2511; while Pdesired=4∗10-4∗I2, λ=0.1305. At the same time, I2 is a 2×2 identity matrix.


### 7.2. Design Issue

In this problem, the system parameters are the same with Section7.1. In addition, we consider three different unit costs of sensor node, Δ=10-4∗I2, 5∗10-4∗I2, and 25∗10-4∗I2, respectively. From Theorem 12, the optimal λ∗ that minimizes Tr⁡(P-λ+λΔ) can be obtained by (56) and (57). The solutions of λ∗ and P^λ∗ are as follows:(61)λ∗=0.4402,P-λ∗=3.43∗10-4,whileΔ=10-4;λ∗=0.2511,P-λ∗=4.864∗10-4,whileΔ=5∗10-4;λ∗=0.1098,P-λ∗=8.013∗10-4,whileΔ=25∗10-4.We also draw the relationship betweenTr⁡(P-λ+λΔ) and λ. As is confirmed in Figure 6, Tr⁡(P-λ+λΔ) is a convex function of λ. And it can be seen easily from the figure that the optimal λ that minimizes Tr⁡(P-λ+λΔ) is the same as the λ∗ calculated from (56) and (57).Figure 6
Tradeoff between energy consumption and estimation error variance of sensor nodes.


## 7.1. Analysis Issue

Consider the system parameters of clock synchronization state space model with(60)A=1001,C=111-1.Three graphs in Figure4 indicate the relationships between the trace of Kalman filter steady-state error variance Tr⁡P-λ (when k→∞) and clock packet arrival rate λ as well as the relationship between the mean error variance E[Pk] (when k→∞) and clock packet arrival rate λ with different circumstances of the system noise and the same observation noise as R=diag(10-3,10-3), where E[Pk] (when k→∞) is obtained by Monte Carlo simulation. As can be seen from the figure, with different system noise, Tr⁡P-λ is tight approximation to E[Pk] (when k→∞). And with the weakening of system noise, the effect of replacing E[Pk] with P-λ (when k→∞) approximately is more and more perfect. Two diagrams in Figures 5 and 4(b) represent that the observation noise is different and the system noise is the same as Q=diag(10-5,10-5). From the comparison of figures, the change of observation noise has no effect on the degree of approximation between Tr⁡P-λ and E[Pk] (when k→∞). Seen from the comparison and analysis of Figures 4 and 5, Tr⁡P-λ can be used to replace E[Pk] approximately (when k→∞), and Tr⁡P-λ is a monotonically decreasing function of λ. It shows again that the higher the probability that clock information arrives at the synchronization node is, the higher the precision of clock synchronization is.Figure 4
Mean error variance and clock information packet arrival rate with different circumstances of the system noise.
(a)
Q
=
diag
(
1
0
-
6
,
1
0
-
6
)
(b)
Q
=
diag
(
1
0
-
5
,
1
0
-
5
)
(c)
Q
=
diag
(
1
0
-
4
,
1
0
-
4
)Figure 5
Mean error variance and clock information packet arrival rate with different circumstances of the observation noise.
(a)
R
=
diag
(
1
0
-
2
,
1
0
-
2
)
(b)
R
=
diag
(
1
0
-
4
,
1
0
-
4
)Assume that the loop termination condition of bisection search algorithmε=0.01, the system noise correlation matrix Q=diag(10-5,10-5), and the observation noise correlation matrix R=diag(10-3,10-3). The simulation results show that the algorithm can obtain the minimum λ after five steps. For example, while Pdesired=1.5∗10-4∗I2, λ=0.5601; while Pdesired=2.5∗10-4∗I2, λ=0.2511; while Pdesired=4∗10-4∗I2, λ=0.1305. At the same time, I2 is a 2×2 identity matrix.


## 7.2. Design Issue

In this problem, the system parameters are the same with Section7.1. In addition, we consider three different unit costs of sensor node, Δ=10-4∗I2, 5∗10-4∗I2, and 25∗10-4∗I2, respectively. From Theorem 12, the optimal λ∗ that minimizes Tr⁡(P-λ+λΔ) can be obtained by (56) and (57). The solutions of λ∗ and P^λ∗ are as follows:(61)λ∗=0.4402,P-λ∗=3.43∗10-4,whileΔ=10-4;λ∗=0.2511,P-λ∗=4.864∗10-4,whileΔ=5∗10-4;λ∗=0.1098,P-λ∗=8.013∗10-4,whileΔ=25∗10-4.We also draw the relationship betweenTr⁡(P-λ+λΔ) and λ. As is confirmed in Figure 6, Tr⁡(P-λ+λΔ) is a convex function of λ. And it can be seen easily from the figure that the optimal λ that minimizes Tr⁡(P-λ+λΔ) is the same as the λ∗ calculated from (56) and (57).Figure 6
Tradeoff between energy consumption and estimation error variance of sensor nodes.


## 8. Future Work of Synchronization Error Precision Analysis and Design

This paper deeply researches certain respect on the synchronization error variance analysis issue from the perspective of statistical mean. At the same time, we are aware that it has a certain limitation in practice. For example, we assumed that packets are dropped independently in this paper, which is certainly not true in the case where burst packets are dropped or in queuing networks where adjacent packets are not dropped independently. Besides, we also use the mean of the synchronization error variance as the measure of performance. Reference [15] pointed out that this can conceal the fact that events with arbitrarily low probability can make the mean diverge, and we should ignore such events with extremely low probability.


### 8.1. Investigating Synchronization Error Variance Analysis from the View of Probability

From the front analysis, it is seen that there exists packet loss such thatPk is a random variable. It is because Pk cannot be determined in one synchronization process that the analysis from the perspective of statistical mean only shows statistical synchronization error variance of multiple information exchanges and may omit some of small probability events. Statistical synchronization error variance of multiple information exchanges does not represent all of synchronization error variance which is not beyond the desired boundary of the synchronization variance. In a period of synchronization, there exists the possibility that some of synchronization error variance goes beyond the desired boundary. For high reliability, if the synchronization error variance goes beyond the desired boundary, it brings serious hidden peril for sensor networks. Motivated by [15] which analyzed that packet loss affects the state estimation variance from the perspective of probability and by [11] which estimated clock parameters from the perspective of probability distribution based on belief propagation, can we analyze the probability that the synchronization error variance goes beyond the desired boundary by the same way?Therefore, in future research, based on the latest synchronization state space model [10] or the research framework in [11], we could discuss the probability distribution of synchronization error variance under the condition of packet loss and analyze the probability of the synchronization error variance beyond the designed boundary of synchronization variance. Then Question 1 proposed in this paper is shown as follows.For a given packet arrival rate, we estimate a different performance metricPr⁡[Pk≤M], that is, the probability Pr⁡[Pk≤M] that Pk is bounded by a given variance M, where notation Pr⁡[·] takes the probability.Compared with the performance metricE[Pk], which maybe omits some of small probability events, we will discuss the synchronization error variance from the point of probability. Due to including small probability events, the high reliability requirement for synchronization precision boundary can be satisfied.


### 8.2. Optimizing the Performance Metric of Synchronization Error Variance Design

Combining synchronization precision and energy consumption into a cost function, as the performance metric ((42) in the paper), reflects the tradeoff between energy consumption and synchronization precision at synchronization node. However, in practice, the energy used to synchronize is limited and we prefer to improve the synchronization precision with the limited energy as much as possible. In fact, the latest literatures have preliminary study, but there is no in-depth study about clock synchronization. Thus, in future research, we need to further optimize the performance metric built in the paper.Since the transmission power of sensor node has an impact on the packet loss rate and packet loss rate also affects synchronization precision, how should we adjust transmission power of sensor node to make the clock synchronization estimation variance as small as possible? In other words, if there are multiple levels of transmission power, how should we schedule the transmission power of sensor node in order to improve synchronization precision as soon as possible with limited energy? At this point, in order to improve synchronization precision as much as possible, we will design the optimal transmission power scheduling sequence with the restriction condition of limited energy.


## 8.1. Investigating Synchronization Error Variance Analysis from the View of Probability

From the front analysis, it is seen that there exists packet loss such thatPk is a random variable. It is because Pk cannot be determined in one synchronization process that the analysis from the perspective of statistical mean only shows statistical synchronization error variance of multiple information exchanges and may omit some of small probability events. Statistical synchronization error variance of multiple information exchanges does not represent all of synchronization error variance which is not beyond the desired boundary of the synchronization variance. In a period of synchronization, there exists the possibility that some of synchronization error variance goes beyond the desired boundary. For high reliability, if the synchronization error variance goes beyond the desired boundary, it brings serious hidden peril for sensor networks. Motivated by [15] which analyzed that packet loss affects the state estimation variance from the perspective of probability and by [11] which estimated clock parameters from the perspective of probability distribution based on belief propagation, can we analyze the probability that the synchronization error variance goes beyond the desired boundary by the same way?Therefore, in future research, based on the latest synchronization state space model [10] or the research framework in [11], we could discuss the probability distribution of synchronization error variance under the condition of packet loss and analyze the probability of the synchronization error variance beyond the designed boundary of synchronization variance. Then Question 1 proposed in this paper is shown as follows.For a given packet arrival rate, we estimate a different performance metricPr⁡[Pk≤M], that is, the probability Pr⁡[Pk≤M] that Pk is bounded by a given variance M, where notation Pr⁡[·] takes the probability.Compared with the performance metricE[Pk], which maybe omits some of small probability events, we will discuss the synchronization error variance from the point of probability. Due to including small probability events, the high reliability requirement for synchronization precision boundary can be satisfied.


## 8.2. Optimizing the Performance Metric of Synchronization Error Variance Design

Combining synchronization precision and energy consumption into a cost function, as the performance metric ((42) in the paper), reflects the tradeoff between energy consumption and synchronization precision at synchronization node. However, in practice, the energy used to synchronize is limited and we prefer to improve the synchronization precision with the limited energy as much as possible. In fact, the latest literatures have preliminary study, but there is no in-depth study about clock synchronization. Thus, in future research, we need to further optimize the performance metric built in the paper.Since the transmission power of sensor node has an impact on the packet loss rate and packet loss rate also affects synchronization precision, how should we adjust transmission power of sensor node to make the clock synchronization estimation variance as small as possible? In other words, if there are multiple levels of transmission power, how should we schedule the transmission power of sensor node in order to improve synchronization precision as soon as possible with limited energy? At this point, in order to improve synchronization precision as much as possible, we will design the optimal transmission power scheduling sequence with the restriction condition of limited energy.


## 9. Conclusion

In this paper, regarding fixed delay and relative clock offset as the unknown clock state variables and based on a unified framework of clock synchronization state space model, we discuss the analysis and design issues between the synchronization error variance and packet loss rate.In the analysis issue, we theoretically prove that the steady-state error variance of Kalman filter in the statistical property is a monotonically decreasing function of clock information packet arrival rate. And in order to guarantee the desired synchronization precision of sensor node, we find a minimum clock information packet arrival rate by an efficient bisection search algorithm. In the design issue, in order to achieve the optimal tradeoff between energy consumption and synchronization precision, we obtain the optimal solution form of clock information exchange rate.It is as indicated in the sections of the synchronization error variance analysis and design issues in this paper. It has great theoretical significance to discuss the synchronization error variance in limited case from the perspective of statistical mean and the performance metric considering both energy consumption and synchronization precision, but it has a certain limitation in practice. However, the estimation performance metric with the view of probability in network control theory brings another research perspective for the analysis and design issues proposed in this paper. In addition, in order to simplify the study of problem and go deep into the essence of problem, the paper firstly uses two nodes as a springboard and focuses on discussing the synchronization error variance analysis and design in detail. For multinode wireless sensor networks, we can use the latest clock synchronization system model. So, based on the latest model of distributed clock synchronization system, we will further discuss the influence of packet loss on synchronization error variance analysis and design issues from the point of probability and assess the reliability of the synchronization error variance beyond the designed boundary of the synchronization variance in future research.There are some works further researched. Discuss the possibility of the synchronization error variance beyond the designed boundary of the synchronization variance from the view of probability. Design an optimal transmission power scheduling sequence of sensor node to make the synchronization precision as high as possible with the limited energy of sensor nodes. The synchronization error variance analysis and design issues will be extended to the distributed network.



---

*Source: 346521-2015-04-08.xml*