Reducing False Negative Reads in RFID Data Streams Using an Adaptive Sliding-Window Approach

3.1.1. Completeness Requirement

Each epoch is viewed as an independent Bernoulli trial (i.e., a sample draw for tag i) with success probability p_i,t using Equation (1) [16]. This implies that the number of successful observations of tag i in the window W_i with w_i epochs (i.e., W_i= (t − w_i, t)) is a random variable with a binomial distribution B(w_i, p_i,t). In the general case, assume that tag i is seen only in subset S_i ⊆ W_i of all epochs in the window Wi. Assuming that, the tag probabilities within an approximately sized window calculated using Equation (1), are relatively homogeneous, taking their average will give a valid estimate of the actual probability of tag i during window W_i [16]. Therefore, the average empirical read rate $p_i^{\mathit{\text{avg}}}$ over the observation epochs is given is given by Equation (2) [16]:

Also S_i can be seen as a binomial sample of epochs in W_ii.e., a Bernoulli trial with probability $p_i^{\mathit{\text{avg}}}$ for success and |S_i| as a binomial random variable with binomial distribution $B\left(w_i,p_i^{\mathit{\text{avg}}}\right)$. Hence, from standard probability theory the expected value and variance of |S_i| is given as:

The derived binomial sampling model is then used to set the window size to ensure that there are enough epochs in the window W_i such that tag i is read if it does exist in the reader's range. Setting the number of epochs within the smoothing window according to Equation (3) ensures that tag i is observed within the window W_i with probability >1 − δ [16]:

3.1.2. Adaptive Window Size Adjustment

In order to balance between guaranteeing completeness and capturing tag dynamics the WSTD algorithm uses simple rules, together with statistical analysis of the underlying data stream, to adaptively adjust the cleaning window size.

Assume Wi = (t − w_i, t) is tag i current window, and let W_1i′ = (t − w_i, t − w_i/2) denote the first half of window Wi and W_2i′ = (t − w_i/2, t) denote the second half of the window Wi. Let |S_1i| and|S_2i| denote the binomial sample size during W_1i′ and W_2i′ respectively. Note that the mid epoch (i.e., epoch at t − w_i/2) in inclusive on both range as shown in Figure 1.

Rule 1: Similar to SMURF, variation within the window is detected if the number of observed readings is less than the expected number of readings (i.e., $\left|S_i\right|<w_i\cdot p_i^{\mathit{\text{avg}}}$) and there is statistically significant variation in the tag observations using the Central Limit Theorem (CLT) $\left|\left|S_i\right|-w_i{p}_i^{\mathit{\text{avg}}}\right|>2\cdot \sqrt{w_i{p}_i^{\mathit{\text{avg}}}\left(1-p_i^{\mathit{\text{avg}}}\right)}$. However, we noted that this variation within the window could also be caused by missing tags and not necessarily only due to transition. Hence, to reduce the number of false positive due to transition and the number of false negative readings, which will be further introduced in case of wrong transition detection, the window size is reduced additively by reducing the window size by two epochs.

To improve the transition detection mechanism for the mobile tags we combine the mobile detection mechanism together with the observations of the second half of the window|S_2i| to estimate when the tag is exiting the detection range. The slope of the best-fit line using the least squares fitting with the observed tag i probabilities in the window $(\frac{\Delta p_{i,t}}{\mathit{\text{epochs}}})$ is used to determine if the tag is moving out. If the tag is detected with consistently falling p_i,t, within the window it is inferred as the tag is moving out. Hence, the negative slope of the best-fit line indicates that the tag is moving out.

Rule 2: If the tag is moving out and it was not detected in the second half of the window (i.e., |S_2i| = 0) the tag is assumed to have exited or is exiting the detection range. In this case the window size is halved to reduce the false positive readings. One weakness of this rule is that premature exit transition detection will also lead to a false negative reading due to a small window size.

Rule 3: The window size is increased if the computed window size using Equation (3) is greater than the current window size and the expected number of observation samples is less than the actual number of observed samples (i.e., $\left|S_i\right|>w_i{p}_i^{\mathit{\text{avg}}}$). Low expected observation samples indicates that the probability of detection $p_i^{\mathit{\text{avg}}}$ is low, in this case we need to grow the window size to give more opportunity for the poor performing tag to be detected. Otherwise, if the expected observation sample is equal or greater than the actual sample size it means that, the $p_i^{\mathit{\text{avg}}}$ is good enough and we do not have to increase the window size. This rule ensures that the window size is increased only when the read rate is poor.

Figure 2 shows a pseudo-code description of the WSTD adaptive per tag cleaning algorithm. Each individual tag is cleaned in its own window. The rules described above are used to adjust the tag's cleaning window size adaptively based on the statistical analysis of the underlying tag observations. Initially all new detected tag's windows are set to one epoch, the window sizes are then adjusted according to their detection rates with minimum window size set to three epochs.

Setting the minimum window size to three epochs strikes a balance between maintaining the smoothing effect of the algorithm and reducing the false positive errors. Similar to SMURF, WSTD also slides its window per single epoch (read cycle) and produces output readings corresponding to the midpoint of the window after the entire window has been read.

3.2.1. Adaptive Window Size Adjustment

The WSTD cleaning algorithm employs the random-sampling model and π-estimator concepts proposed in SMURF together with comparison of the two-window sub-range estimated tag counts to dynamically adapt its smoothing window size. Transitions are detected as statistically significant changes in aggregate estimates over sub-ranges of its current smoothing window. The transition detection model used is the main difference between our multi-tag cleaning algorithm and the SMURF multi-tag cleaning algorithm.

Assume W = (t − w, t) is current window, and let W₁′ = (t − w, t − w/2) denote the first half of window W and W₂′ = (t − w/2, t) denote the second half of the window W. Let ${\widehat{N}}_{W_1^{\prime }}$ and ${\widehat{N}}_{W_2^{\prime }}$ denote the π-estimators for tag population counts during W₁′ andW₂′ respectively. Note that the mid epoch (i.e., epoch at t − w/2) is inclusive in both ranges. The mid-point divides the window such that the numbers of epochs are equally spaced on either side of the window and this requires the use of an odd number window size. The transition is detected if there is significant change in tag counts between these two ranges.

In the SMURF multi-tag cleaning algorithm the transition is detected as a statistically significant transition in population count has occurred in the second half of the window compared to the whole window population count by using CLT condition $\left|{\widehat{N}}_W-{\widehat{N}}_{W_2^{\prime }}\right|>2\left(\sqrt{\mathit{\text{Var}}\left({\widehat{N}}_W\right)}+\sqrt{\mathit{\text{Var}}\left({\widehat{N}}_{W_2^{\prime }}\right)}\right)$. However in our model the transition is detected as a significant change in the population count by comparing the count estimates in the first half and the second half of the window by using the expression $\left|{\widehat{N}}_{W_1^{\prime }}-{\widehat{N}}_{W_2^{\prime }}\right|>2\left(\sqrt{\mathit{\text{Var}}\left({\widehat{N}}_{W_1^{\prime }}\right)}+\sqrt{\mathit{\text{Var}}\left({\widehat{N}}_{W_2^{\prime }}\right)}\right)$. Our experimental results verified that using the comparison of the sub-range population count estimates to detect population count variation within the window, gives a more accurate transition detection technique than comparison between full window count and the sub-range count estimates used by SMURF. SMURF detection condition detects any significant variation within the window, however, for transition detection mechanism we are more interested in detecting the edge transition, which signals that the tag is either entering or leaving the detection range and respond accordingly.

By comparing the population count of the two window sub ranges, it is possible to determine when the tag is exiting and entering the detection range eliminating the need to use mobile detection algorithm as proposed by SMURF. In the environment where tags are mobile there are two scenarios: one is tags exiting the detection range and the second is tags entering the detection range.

We use simple rules to detect when these transitions occur by comparing the estimated tag count in the two window sub ranges. The tags are said to be exiting the detection range if the transition is detected and there is more estimated tag counts in the first half of the window than in the second half of the window (i.e., ${\widehat{N}}_{W_1^{\prime }}>{\widehat{N}}_{W_2^{\prime }}$). In this case, the window size is reduced multiplicatively (i.e., divided in half) to circumvent false positive readings. Similarly the tag is said to be entering the detection region if transition is detected and there is more estimated tag count in the second half of the window than in the first half of the window (i.e., ${\widehat{N}}_{W_2^{\prime }}>{\widehat{N}}_{W_1^{\prime }}$). In this case, if the required window size is greater than twice the current window size, the window size is increased multiplicatively (i.e., doubled) if not, the window size is additively increased by two epochs. This is because as tag enters the detection range it is assumed to be on the far end of reader's detection ranges i.e., long distance from the reader's antenna. Increasing the window size gives more opportunity even for the weak performing tags to de detected.

When the tags are leaving and entering the detection range, false positive readings will be produced regardless of the window size because the readings are interpolated throughout the window. This problem is more prone to the bigger windows. To reduce false positive readings under these scenarios we made two estimation assumptions. These approximation assumptions are used to detect when the tag(s) completely exit(s) the detection range and when the tag(s) just entered the detection region as illustrated in Figure 3. In the first assumption, the tag(s) are said to have exited the reader's detection range if the overall window tag count is not zero, but the second half of the tag population count is zero (i.e., ${\widehat{N}}_W>0\wedge {\widehat{N}}_{W_2^{\prime }}=0$). This means that there was no tag observed in the second half of the window. In the second assumption, the tag(s) are said to have just entered the reader's detection range if the overall window tag count is not zero, but the first half of tag population count is zero (i.e., ${\widehat{N}}_W>0\wedge {\widehat{N}}_{W_1^{\prime }}=0$). This means that there was no tag observed in the first half of the window (t − w, t − w/2).

Considering that the cleaning window size slides by the midpoint, we assume that the observed tags under these scenarios are more likely to be a false positive readings caused by a bigger window size. Therefore, tag(s) observed in these scenarios are dropped and the window size is reduced for an exiting scenario and increased appropriately for an entering scenario.

By taking advantage of the π-estimator, which scales-up the reading in the window to estimate the underlying tag population, we can reduce the window sizes to enhance transition detection, hence the minimum window size can be reduced to 1 epoch. We introduce another estimation condition, which we call strong region detection. The aim of strong region detection is to detect when the tags within the window are observed with high probability of detection and when there is no significant variation in tag population within the two window sub-ranges.

Let S_i be a binomial sample of epochs in the current window W in which a single tag is observed and $p_i^{\mathit{\text{avg}}}$ be the average read rate as defined in the per-tag cleaning approach. Let Sw denote the sample of distinct tags read over the current smoothing window and $p^{\mathit{\text{avg}}}=\left(1/\left|S_W\right|\right)\cdot {\sum }_{i\in S_W}{p}_i^{\mathit{\text{avg}}}$ denote the average sampling probability over all observed tags and $S^{\mathit{\text{avg}}}=\left(1/\left|S_W\right|\right)\cdot {\sum }_{i\in S_W}{S}_i$ denote the average sample of epochs in the window in which the tags where observed.

The tags are then said to be observed in the strong detection region if the following condition holds $\left(p^{\mathit{\text{avg}}}>\left(1/W\right)\cdot S^{\mathit{\text{avg}}}\right)\wedge \left(\left|{\widehat{N}}_{W_1^{\prime }}-{\widehat{N}}_{W_2^{\prime }}\right|<\lceil 0.05\cdot \mathit{\text{min}}\left({\widehat{N}}_{W_1^{\prime }},{\widehat{N}}_{W_2^{\prime }}\right)\rceil \right)$. The second portion of the logical condition tests if the two window sub-range estimates have a relatively small difference of less than 5% of the lowest estimated tag counts. If the condition holds the window size is reduced by two epochs.

Figure 4 shows a pseudo-code description of the adaptive multi-tag cleaning algorithm. All the tags are cleaned using the same window. Similar to per-tag cleaning, the smoothing-window size is systematically adjusted based on the analysis of the observed tags binomial-sampling data and the transition is detected by comparing the window sub-range estimated population counts.

4.1.1. Experiment 1: Environment Reliability with Randomly Moving Tags

In this experiment we determine how each technique reacts to different levels of environment unreliability with the randomly moving tags. Each tag is moved with its own random velocity between 0 to 90 cm/epoch and after every 100 epochs on average the tag change its state from moving to rest state and vice versa. When the tag resumes movement it chooses another random velocity, this movement pattern is referred as Fido in [16]. The strong-in-field region percentage is varied between 0 and 100%. The lower StrongPercentage corresponds to unreliable environment and higher values of StrongPercentage corresponds to a more controlled environment. At each StrongPercentage we measure the average errors produced by each scheme. The average error per epoch is calculated as ${\sum }_{i=1}^{\mathit{\text{NumEpochs}}}\left({\mathit{\text{FalsePositive}}}_i+{\mathit{\text{FalseNegative}}}_i\right)/\mathit{\text{NumEpochs}}$. Figure 6 shows the result of this experiment, the “raw” trace is truncated to enable clear view of other traces.

The WSTD scheme performs better than SMURF producing an improvement of approximately 25% less overall error in comparison to that produced by SMURF. This performance is attributed to its improved transition detection mechanism as shown in Figure 7. Comparing their cleaning-window sizes, WSTD uses a smaller window size in comparison to that used by SMURF as shown in Figure 8. The cleaning-window sizes decrease along with the decrease in environment noise.

Because of its small window size, WSTD is more efficient in detecting transition than SMURF; however, it also produces slightly more negative errors than SMURF as show in Figure 9. The increase in false negative errors in the noisy environment by WSTD can be associated with the premature transition detection by rule2 of the WSTD algorithm. As the noise decreases, their performance in compensating for missed readings become competitive and their difference decreases.

4.1.2. Experiment 2: Effect of Tag Speed

The effectiveness of the individual tag cleaning schemes are then compared as the tag velocity is varied. The StrongPercentage parameter is fixed at 70% to represent the controlled environment and the tags are moved in and out of the detection range at the same constant velocity. The velocity is varied from 0 to 90 cm/epoch the average errors produced by each scheme were measured. Figure 10 shows the result of this experiment and Figure 11 shows their positive and negative error contributions as the tag velocities are varied.

The WSTD scheme performs better than SMURF producing an improvement of approximately 30% less overall errors in comparison to that produced by SMURF. This performance improvement is attributed to its improved transition detection as shown in Figure 12, due to its use of small window sizes as shown in Figure 13. The cleaning-window sizes decreases with the increase in tag speed.

4.1.3. Experiment 3: Environment Reliability with Static Tags

We also evaluated the performance of different cleaning schemes in the environment where tags are stationary. To simulate this scenario we randomly distribute the tags uniformly within the detection range and varied the StrongPercentage parameter and measured the average errors produced by each scheme. Figure 14 shows the result of this experiment and Figure 15 shows the average cleaning-window sizes for the SMURF and WSTD schemes as the environment noise is varied.

In the static environment, both WSTD and SMURF schemes exhibit closely matching performances which can be attributed to their use of similar cleaning-window sizes as shown in Figure 15. From this observation we can conclude that the main difference between WSTD and SMURF is in the transition detection mechanism, and WSTD performs better than SMURF in the mobile environment.

4.2.1. Experiment 4: Effect of Tag Speed on Tags Aggregate Cleaning

We evaluate the tag count accuracy of the cleaning schemes as the tags' velocity is varied. The StrongPercentage parameter is fixed at 25% to represent the noisy environment and the tags are moved in and out of the detection range at the same velocity. The velocity is varied from 0 to 90 cm/epoch and we measured the RMS errors produced by each scheme. Figure 16 shows the result of this experiment.

Figure 17 shows the average number of overestimate and underestimate tag counts for the cleaning schemes and Figure 18 shows their average cleaning-window sizes as the tags' velocity is varied. The WSTD-π scheme has the smallest number of underestimate and overestimate errors and it also uses the smallest average cleaning-window sizes compared to other variable window schemes. The WSTD-π small overestimate errors are attributed to its smaller window size while its small underestimate errors are attributed to its use of π-estimator to estimate the number of tags.

Although we used an average number of overestimate and underestimate tag counts per epoch as a metric to compare the performance of these schemes, we noticed that most of the undercounting errors occur during the transition periods. This is caused by the nature of algorithms whereby the window size is reduced when an exit transition is detected. While this measure limits the false positive errors, it also leads to false negative errors due to resulting small window size in case of premature exit transition detection. In addition, when the tags are entering the detection region on the far edge of the detection range due to a small window size and a weak read rate, leads to a high number of undercounting errors. Figure 19 shows the comparison of the reported estimated tags count and that of the actual tag count for the three variable window schemes SMURF, WSTD and WSTD-π with the tags moving at a velocity of 0.4 m/epoch. WSTD-π provides close accurate tag-count estimation compared to other schemes.

4.2.2. Experiment 5: Effect of Environment Reliability with Randomly Moving Tags

In this experiment we determine how each multi-tag cleaning technique reacts to different levels of the environment's unreliability with the randomly moving tags. The experimental parameters are the same as the ones used for the individual tag-cleaning experiment, except that in this experiment we used 100 moving tags instead of 25 tags. The strong-in-field region percentage is varied between 0 and 100% and at each StrongPercentage we measure the RMS errors produced by each scheme. Figure 20 shows the result of this experiment, “raw” trace is truncate to enable a clear view of other traces.

Figure 21 shows average number of overestimate and underestimate tag counts and Figure 22 shows the average cleaning-window size of the variable window schemes as the environment noise is varied.

From Figure 21 looking at per-tag cleaning schemes; SMURF has consistently more overestimate errors than WSTD, while in a noisy environment WSTD has more underestimate errors than SMURF. However, as the noise decreases and the reader produce more reliable data, the WSTD-undercount errors also decrease and at a highly controlled environment, its performance outperforms that of SMURF. WSTD-π on the other hand, consistently produces relatively stable overestimate errors irrespective of the environment condition; however, its underestimate errors decrease with the decrease of the environment noise (see Figure 21). These constant overestimate errors might be caused by the fact that WSTD-π uses the same window size to clean all the tags. In this scenario each tag moves randomly in and out of detection range with random velocities. WSTD-π transition mechanism is not able to effectively detect transition in this scenario; as a result the π-estimator overestimates the tags' count. The per-tag variable window cleaning schemes—SMURF and WSTD—outperform a single variable window scheme—WSTD-π—in the noisy environment because they clean and adjust their window size for each single tag independently depending on its individual tag behaviour and how the environment is affecting that particular tag. Figure 23 shows the comparison of the reported estimated tags' count and that of the actual tag count for these three variable window schemes. The tags are operating in the semi-controlled environment with StrongPercentage parameter set to 50%. Hence, this experiment results demonstrate that in the environment where each tag displays its own independent random behaviour the best result is obtained by adjusting each individual tag cleaning window independently.

4.2.3. Experiment 6: Effect of Environment Reliability with Static Tags

We also evaluated the performance of different sliding-window based multi-tag cleaning schemes in the environment where tag(s) are stationary. To simulate this scenario we randomly distributed 100 tags uniformly within the detection range and varied the StrongPercentage parameter and measured the root mean square error produced by each scheme. Figure 24 shows the result of this experiment, the “raw” trace is truncate to enable clear view of other traces.

Similar to the per-tag cleaning in the static environment scenario, SMURF and WSTD schemes have the same performance in cleaning the tag aggregations in the static environment as shown in Figure 24.

Since they both count the distinct tag available within each tag's cleaning window they have no overestimate errors and their underestimate decrease with the decrease in noise as shown in Figure 25. In a highly noisy environment the performance of per tag cleaning schemes is highly affected by the poor performing tags on the far edge of the detection region. In the noisy environment the far edge static tags cleaning window grows linearly with distance and becomes very large (results not shown). Because the cleaning window sizes for individual tags might be different based on their detection rates, the decision at whether the tag is present or not is taken at different epochs. Therefore, the tags are not ready for processing (i.e., the readings for all epochs in its window have not been accumulated) will delay the output and highly affect the performance of the scheme.

On the other hand, the WSTD-π scheme, which estimates the tag count based on tag detections and π-estimator, produces both underestimate and overestimate errors as shown in Figure 25. Its performance increases with the reduction of environment noise with both its overestimate and underestimate errors decreasing. The WSTD-π scheme uses the smallest cleaning-window sizes compared to other schemes as shown in Figure 26. We can conclude that WSTD-π performance strikes a balance between accuracy and processing speed, by providing a considerably good estimate in a much shorter time.