1 Introduction
2 Problem definition
-
Input:1.The start and final time of monitoring, t 0(=t s) and t f2.The maximum bound of the sampling frequency of a sensor node, f max3.The step-size increment t ′ and the decrease factor α
-
Output: The sets of approximate extremum and inflection points in [t s,t f], X 1 and X 2
Symbols | Meanings |
---|---|
δ
| The relative error of the approximate critical point |
N
| The number of sensor nodes in a given WSN |
V={1,2,..N} | The set of sensors |
i
| The ID of a sensor node |
S
i
| The real physical world curve at node i’s location |
S
i
(t) | The sensed value of sensor node i at time t
|
S
i
(k)(t) | The k-order derivative of S
i
at time t. |
\(\widehat {S_{i}}^{(k)}(t)\)
| The estimation of the k-order derivative of S
i
at time t. |
X
1
| The extremum point set returned by our algorithm. |
X
2
| The inflection point set returned by our algorithm. |
t
s
| The start time of an observation period |
t
f
| The final time of an observation period |
t
c
| The current data sampling time slot |
f
max
| The maximum sampling frequency |
t
′
| The step-size increment |
α
| The decrease factor |
3 Mathematical foundations
4 Critical point aware data acquisition algorithm
-
Step 1. Sample sensory values at time t 0, \(t_{\frac {1}{2}}\), t 1, where \(t_{\frac {1}{2}}=t_{0}+\frac {1}{f_{\text {max}}}\) and \(t_{1}=t_{\frac {1}{2}}+\frac {1}{f_{\text {max}}}\). That is, we initialize h with the minimum sampling interval \(\frac {1}{f_{\text {max}}}\). Initialize c with 2, then execute a loop until t c >t f .
-
Step 2. Sensor node i (1≤i≤N) samples the sensory values at time \(t_{\frac {2c-1 }{ 2 }}\) and t c , where \(t_{\frac {2c-1 }{ 2 }}=t_{c-1}+h\) and \(t_{c}=t_{\frac {2c-1 }{ 2 }}+h\). Using the sensory values sampled in the current and last sampling intervals, i.e., S i (t c−2), \(S_{i}\left (t_{\frac {2c-3 }{ 2 }}\right)\), S i (t c−1), \(S_{i}\left (t_{\frac {2c-1 }{ 2 }}\right)\) and S i (t c ), the Lagrange interpolation polynomial can be constructed. Therefore, \(S_{i}^{(3)}(t)\) and \(S_{i}^{(4)}(t)\) can be obtained according to Formulas (5) and (6) for \(t\in \!\left [t_{\frac {2c-3}{2}},t_{c}\right ]\) and t∈ [t c−2,t−c] respectively.
-
Step 3. Call the extremum point retrieving algorithm to obtain the extremum point in current sampling interval and determine the length of the next possible sampling interval h 1, the detailed method is shown in Section 4.1.
-
Step 4. Similarly, call the inflection points retrieving algorithm to collect the inflection point and determine the length of the next possible sampling interval h 2. The detailed algorithm is given in Section 4.2.
-
Step 5. Finally, select the minimum one returned by the above two steps to be the adopted length of the next sampling interval, i.e., h=min{h 1,h 2}, which avoids omitting critical points. Go to step 2 with increasing c by 1, and start a new loop until t c >t f .
4.1 Extremum point retrieving algorithm
-
Step 2. Find extremum point in \(\left [t_{\frac {2c-3}{2}}, t_{\frac {2c-1}{2}}\right ]\). If \(\widehat {S_{i}}^{(1)}\left (t_{\frac {2c-1}{2}}\right)=0\), return the extremum point \(t_{\frac {2c-1}{2}}\). Otherwise, compare \(\widehat {S_{i}}^{(1)}\left (t_{\frac {2c-1}{2}}\right)\) and \(\widehat {S_{i}}^{(1)}\left (t_{\frac {2c-3}{2}}\right)\) calculated in last loop. If \(\widehat {S_{i}}^{(1)}\left (t_{\frac {2c-1}{2}}\right)\times \widehat {S_{i}}^{(1)}\left (t_{\frac {2c-3}{2}}\right)<0\), there must be an extremum point in \(\left [t_{\frac {2c-3}{2}},t_{\frac {2c-1}{2}}\right ]\). Then, retrieve the extremum point by curve tessellation techniques [29].
-
Step 3. There exists three cases that need to be considered when determining the length of the next sampling interval.
-
Step 4. Return h 1 and the extremum point.
4.2 Inflection point retrieving algorithm
-
Step 2. Find inflection point in \(\left [t_{\frac {2c-3 }{ 2 }}, t_{\frac {2c-1 }{ 2 }}\right ]\). If \(\widehat {S_{i}}^{(2)}\left (t_{\frac {2c-1 }{ 2 }}\right)=0\), inflection point is \(t_{\frac {2c-1 }{ 2 }}\) and return it. Otherwise, compare \(\widehat {S_{i}}^{(2)}\left (t_{\frac {2c-1 }{ 2 }}\right)\) and \(\widehat {S_{i}}^{(2)}\left (t_{\frac {2c-3 }{ 2 }}\right)\) calculated in last loop. If \(\widehat {S_{i}}^{(2)}\left (t_{\frac {2c-1 }{ 2 }}\right)\times \widehat {S_{i}}^{(2)}\left (t_{\frac {2c-3 }{ 2 }}\right) <0\), there must be an inflection point in \(\left [t_{\frac {2c-3 }{ 2 }},t_{\frac {2c-1 }{ 2 }}\right ]\) we have missed. Then, retrieve the inflection point by curve tessellation techniques [29].
-
Step 3. There exists three cases that need to be considered when determining the length of the next sampling interval.
-
Step 4. Return h 2 and the inflection point.
4.3 Discussion: the method for estimating missing critical points
-
Step 1. Judge whether t c−1 is a δ-approximate extremum point by Theorem 4.
-
Step 2. Use the the values \(\widehat {S_{i}}^{(1)}\left (t_{\frac {2c-3}{2}}\right)\), \(\widehat {S_{i}}^{(2)}\left (t_{\frac {2c-3}{2}}\right)\), \(\widehat {S_{i}}^{(1)}\left (t_{\frac {2c-1}{2}}\right)\) and \(\widehat {S_{i}}^{(2)}\left (t_{\frac {2c-1}{2}}\right)\) to locate the interval where the approximate extremum point is in.
-
Step 3. Use the Lagrange interpolation polynomial we constructed before to estimate the sampling value of the estimated extremum point.