Digital Signal Processing Reference
In-Depth Information
()
P
()
AP
T
−
θ
()
A
()
PA
2
,
i
o
=−− .
TdX
4
,
i
i
()
AP
1
+
θ
s
Since
d
,
X
i
(AP)
, and
X
i
(PA)
are all nonnegative, defining θ′
s
1/(1 + θ
s
(AP)
) and θ′
o
θ
o
(AP)
/(1 + θ
s
(AP)
), we obtain
()
A
()
P
()
A
T
≤ ′ + ′ ≤.
θ
T
θ
T
(13. 33)
1
,
i
s
2
,
i
o
4
,
i
(A)
,
T
2,
i
(A)
) is called a data point. With
N
message
exchanges, the goal is to find θ′
o
and θ′
s
such that they satisfy (13.33) for 1 ≤
i
≤
N
. In gen-
eral, this is a linear programming problem and there are an infinite number of solutions
for this problem [29]. Although more time stamps would generate tighter bounds on θ′
o
and θ′
s
, unfortunately, at the same time, the computational and storage requirements of
the linear programming approach also increase. Thus, such an approach appears to be
not suitable for implementation in wireless sensor nodes, which have strictly limited
memory and computing resources.
Tiny-sync and Mini-sync tackle the problem as finding the best-fit line that lies
between the bound sets defined by the data points. Based on the observation that not
all data points are useful, Tiny-sync preserves only four constraints (the ones that yield
the best bounds on the estimate) out of all data points. This results in a very efficient
algorithm. However, it is shown by a counterexample [28] that this scheme does not
always produce the optimal solution since some data points are considered useless and
discarded at a certain time, a step that actually might provide a better bound if it is prop-
erly considered with another data point that is yet to come.
Mini-sync is an improved version of Tiny-sync in the sense that it finds the opti-
mal solution with increased complexity (but still with lesser complexity than the linear
programming approach). Mini-sync basically uses an additional criterion to determine
whether the data point can be safely discarded.
(P)
, and
T
3,
i
The 3-tuple of time stamp (
T
1,
i
13.4.1.5 Reference Broadcast Synchronization (RBS)
RBS [18] is based on the RRS approach discussed in section 13.3.3. Let the time stamps
recorded at node A and node B for receiving the
i
t h
common packet be denoted as
T
2,
i
(A)
(B)
, respectively. The estimate of the clock offset between node A and node B is
proposed in [18] as
and
T
2,
i
N
1
∑
ˆ
θ
(BA)
()
A
()
B
=
TT
− ,
(13. 34)
2
,
i
2
,
i
N
i
=
1
where
N
stands for the total number of common packets received by node A and node B.
We have shown in section 13.3.3 that the above estimator is actually the ML estimator
for the clock offset, assuming the random portions of the delays in message deliveries
Search WWH ::
Custom Search