# US 2024/0201728 A1 · Timestamp-free synchronization clock parameter tracking method based on extended kalman filter

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0201728 A1
- Document ID: US20240201728A1
- Status: Published application
- Kind: A1
- Application number: 17/791,920
- Filed: 2022-02-18
- Published: 2024-06-20
- Earliest claimed: 2021-06-25
- Applicants: Chongqing University of Posts and Telecommunications
- Inventors: Heng Wang; Zhengcen Peng; Rui Lu; Xi Guo; Ping Wang
- Web page: https://patentgrep.com/patent/US20240201728A1

## CPC

- G06F 1/12: Synchronisation of different clock signals {provided by a plurality of clock generators}
- G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06F 18/295: {Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models}
- Y02D 30/70: in wireless communication networks
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

The present invention relates to a timestamp-free synchronization clock parameter tracking method based on extended Kalman filter, and belongs to the technical field of wireless sensor networks. With a first order Gauss Markov model and a clock model as a state equation, evolution processes of clock skew and instantaneous clock offset is described. Then an observation equation constituted by observation models of timestamp-free synchronization and instantaneous clock offset is established, and clock skew and instantaneous clock offset are jointly tracked by a tracking method based on extended Kalman filter to realize synchronization between a node to be synchronized and a reference clock node. The method can track two time-varying parameters simultaneously by following a network data flow without needing a dedicated synchronization frame to exchange synchronization information, which reduces energy consumption and improves synchronization precision.

## Claims

### Claim 1

A timestamp-free synchronization clock parameter tracking method based on extended Kalman filter, characterized by comprising the following steps:
S1: with time-varying parameter models as a state equation, describing evolution processes of clock skew and instantaneous clock offset, wherein the time-varying parameter models are a first order Gauss Markov model and an iterative model of instantaneous clock offset;
S2: establishing an observation equation, and jointly tracking clock skew and instantaneous clock offset by a tracking method based on extended Kalman filter to realize synchronization between a node to be synchronized and a reference clock node, wherein the observation equation is constituted by observation models of timestamp-free synchronization and instantaneous clock offset.

### Claim 2 (depends on 1)

The timestamp-free synchronization clock parameter tracking method based on extended Kalman filter as claimed in claim 1, characterized in that: for the state equation in step S1, dynamically changing clock skew is considered as a random variable of which the characteristics are described with the first order Gauss Markov model, and the specific formula is as follows:
ρ[n]=mρ[n−1]+u[n]
wherein ρ[n] represents the clock skew of the node to be synchronized relative to the reference clock node at the nth sampling moment; m represents a coefficient less than and close to 1 and is assumed to be known; and u[n] represents Gaussian driving noise with the mean value of 0 and the variance of σu2;
the clock model is used to describe instantaneous clock offset, and the specific formula is as follows:
θ[n]=θ[n−1]+ρ[n]τ[n]
wherein θ[n] represents the clock offset of the node to be synchronized relative to the reference clock node at the nth sampling moment; and τ[n] represents the sampling interval of a nth sample and is assumed to be a fixed value, i.e., τ[n]=τ0;
the formulas of instantaneous clock offset and clock skew are combined to constitute a matrix form, thus obtaining a state equation as follows:
x
[
n
]
=
A
⁢
x
[
n
-
1
]
+
u
[
n
]
wherein
x
[
n
]
=
[
θ
[
n
]
ρ
[
n
]
]
,
A
=
[
1
m
⁢
τ
0
0
m
]
and
u
[
n
]
=
[
τ
0
⁢
u
[
n
]
u
[
n
]
]
.

### Claim 3 (depends on 1)

The timestamp-free synchronization clock parameter tracking method based on extended Kalman filter as claimed in claim 1, characterized in that: the steps of establishing the observation equation in step S2 are as follows:
S21: in the ith synchronization round, carrying out timestamp-free exchange between the node to be synchronized and the reference clock node, with the general synchronization formula as follows:
Δi=(1+ρi)[(T4,i−T1,i)−2δ−(νi+ωi)]
wherein Δi is the response time of the reference clock node, T1,i and T4,i respectively represent the time for the node to be synchronized to send data packets and the time for the node to be synchronized to receive data packets, δ is a fixed delay of message transmission between two nodes, and νi and ωi are random delays of unlink and downlink during message transmission and modeled as Gaussian distribution with the mean value of 0 and the variances of ε2 and σ2;
S22: repeating step S21, subtracting the general formula of the ith round from the general formula of the i+1th round, and assuming clock skew to be unchanged for two consecutive rounds, i.e., ρi+1+ρi, wherein i is an odd number, and the observation model of timestamp-free synchronization is obtained as follows
Δ
i
+
1
-
Δ
i
︸
Δ
j
′
=
(
1
+
ρ
i
)
[
S
i
+
1
-
S
i
︸
S
j
′
-
(
w
i
+
1
-
w
i
︸
w
j
)
]
wherein
j
=
i
+
1
2
,
i is an odd number, Si=T4,i−T1,i, and wi=νi+ωi;
S23: after sampling, obtaining the discrete observation model of timestamp-free synchronization of the node to be synchronized as follows:
S
′
[
n
]
=
1
1
+
ρ
(
A
⁢
R
)
[
n
]
⁢
Δ
′
[
n
]
+
w
′
[
n
]
wherein S′[n] is an observed value at the nth sampling moment, ρ[n] represents clock skew at the nth sampling moment, w′[n] represents observation noise at the nth sampling moment, and Δ′[n]=Δi+1−Δi;
S24: writing the observation model of instantaneous clock offset as: {tilde over (θ)}[n]=θ[n]+υ[n], wherein {tilde over (θ)}[n] is an observed value of instantaneous clock offset, and υ[n] represents Gaussian observation noise with the mean value of 0 and the variance of συ2;
combining the discrete observation model of timestamp-free synchronization and the observation model of instantaneous clock offset, thus obtaining an observation equation as follows:
R
[
n
]
=
h
⁡
(
x
[
n
]
)
+
W
[
n
]
wherein
R
[
n
]
=
[
θ
~
[
n
]
S
′
[
n
]
]
,
h
⁡
(
x
[
n
]
)
=
[
θ
[
n
]
Δ
′
[
n
]
1
+
ρ
[
n
]
]
and
W
[
n
]
=
[
υ
[
n
]
w
′
[
n
]
]
;
S25: tracking clock parameters by means of extended Kalman filter, and linearizing the observation equation before using the tracking method based on extended Kalman filter, with the specific steps as follows:
S251: carrying out first order Taylor series expansion of
h
⁡
(
x
[
n
]
)
=
[
θ
[
n
]
Δ
′
[
n
]
1
+
ρ
[
n
]
]
;
h
⁡
(
x
[
n
]
)
≈
h
⁡
(
x
ˆ
[
n
⁢
❘
"\[LeftBracketingBar]"
n
-
1
]
)
+
∂
h
∂
x
[
n
]
❘
"\[RightBracketingBar]"
x
[
n
]
=
x
^
[
n
⁢
❘
"\[LeftBracketingBar]"
n
-
1
]
(
x
[
n
]
-
x
ˆ
[
n
⁢
❘
"\[LeftBracketingBar]"
n
-
1
]
)
S252: respectively taking derivatives of θ[n] and ρ[n] by h(x[n]), and solving a jacobi matrix as follows
H
[
n
]
=
∂
h
∂
x
[
n
]
=
[
1
0
0
-
Δ
′
[
n
]
(
1
+
ρ
[
n
]
)
2
]
❘
"\[LeftBracketingBar]"
x
[
n
]
=
x
^
[
n
⁢
❘
"\[LeftBracketingBar]"
n
-
1
]
S253: rewriting the observation equation as follows:
R[n]=H[n]x[n]+W[n]+(h({circumflex over (x)}[n|n−1])−H[n]{circumflex over (x)}[n|n−1]).

### Claim 4 (depends on 3)

The timestamp-free synchronization clock parameter tracking method based on extended Kalman filter as claimed in claim 3, characterized in that: the step of jointly tracking clock skew and instantaneous clock offset by a tracking method based on extended Kalman filter in step S2 specifically comprises:
recording a timestamp of timestamp-free exchange by the node to be synchronized, calculating an observed value according to the timestamp, and jointly tracking instantaneous clock offset and clock skew by the tracking method based on extended Kalman filter in combination with predicted values of state models of clock skew and offset, wherein the formula of extended Kalman filter is as follows:
Prediction: {circumflex over (x)}[n|n−1]=A{circumflex over (x)}[n−1|n−1]
Predicted minimum mean square error: M[n|n−1]=AM[n−1|n−1]AT+Cs
Kalman Gain:
K
[
n
]
=
M
[
n
|
n
-
1
]
⁢
H
T
[
n
]
C
o
+
H
[
n
]
⁢
M
[
n
|
n
-
1
]
⁢
H
T
[
n
]
Correction: {circumflex over (x)}[n|n]={circumflex over (x)}[n|n−1]+K[n](R[n]−h({circumflex over (x)}[n|n−1]))
Minimum mean square error: M[n|n]=(I−K[n]H[n])M[n|n−1]
wherein {circumflex over (x)}[n|n−1] represents a predicted value matrix of instantaneous clock offset and clock skew at the nth sampling moment, A is an update coefficient matrix, M[n|n−1] represents a predicted minimum mean square error matrix at the nth sampling moment,
C
s
=
[
τ
0
2
⁢
σ
u
2
τ
0
⁢
σ
u
2
τ
o
⁢
σ
u
2
0
]
represents a covariance matrix of driving noise, K[n] represents a Kalman gain matrix at the nth sampling moment, H[n] represents a Jacobi matrix at the nth sampling moment,
C
o
=
[
σ
υ
2
0
0
σ
ω
′
2
]
is a covariance matrix of observation noise, {circumflex over (x)}[n|n] represents a corrected value matrix of corrected instantaneous clock offset and clock skew at the nth sampling moment, R[n] represents an observed value matrix at the nth sampling moment, h({circumflex over (x)}[n|n−1]) represents a transformation matrix from state variables to ideal observation of instantaneous clock offset and clock skew at the nth sampling moment, and M[n|n] represents a corrected minimum mean square error matrix at the nth sampling moment.

### Claim 5 (depends on 1, 2, 3, 4)

The timestamp-free synchronization clock parameter tracking method based on extended Kalman filter as claimed in any one of claims 1-4, characterized in that: the method comprises the following specific steps:
D1: starting a clock parameter tracking process;
D2: initializing an extended Kalman filter;
D3: carrying out timestamp-free exchange between the node to be synchronized and the reference clock node, and recording the respective time to receive and send data packets;
D4: judging whether the number of synchronization rounds is an odd number; if yes, entering flow D5; otherwise, entering flow D6;
D5: increasing the number of synchronization rounds by 1, and entering flow D3;
D6: calculating the observed value R[n] and the observation matrix H[n] according to the timestamp information and the known response time by the node to be synchronized, predicting a first parameter state vector {circumflex over (x)}[n|n−1] at moment n based on values of clock skew and offset at moment n−1 according to the state equation, and finally calculating the predicted minimum mean square error;
D7: calculating Kalman gain according to the observation matrix H[n];
D8: calculating corrected values and minimum mean square errors of instantaneous clock offset and clock skew at moment n according to Kalman gain and the observed value R[n];
D9: judging whether the number of synchronization rounds reaches a predicted value; if no, entering flow D10; otherwise, entering flow D11;
D10: increasing the number of synchronization rounds by 1, and entering flow D3;
D11: ending the tracking process of instantaneous clock offset and dynamic clock skew.