DECHADE: DEtecting slight Changes with HArd DEcisions in Wireless Sensor Networks

Abstract

This paper focuses on the problem of change detection through a Wireless Sensor Network (WSN) whose nodes report only binary decisions (on the presence/absence of a certain event to be monitored), due to bandwidth/energy constraints. The resulting problem can be modelled as testing the equality of samples drawn from independent Bernoulli probability mass functions, when the bit probabilities under both hypotheses are not known. Both One-Sided (OS) and Two-Sided (TS) tests are considered, with reference to: (i) identical bit probability (a homogeneous scenario), (ii) different per-sensor bit probabilities (a non-homogeneous scenario) and (iii) regions with identical bit probability (a block-homogeneous scenario) for the observed samples. The goal is to provide a systematic framework collecting a plethora of viable detectors (designed via theoretically founded criteria) which can be used for each instance of the problem. Finally, verification of the derived detectors in two relevant WSN-related problems is provided to show the appeal of the proposed framework.

Keywords:

• Change detection
• Data Fusion
• Internet of Things
• Wireless Sensor Networks

Notes

No potential conflict of interest was reported by the authors.

1 Notation – Lower-case bold letters denote vectors, with $a_n$ being the nth element of $\mathit{a}$; upper-case calligraphic letters, e.g. $\mathcal{A}$, denote finite sets; $\mathbb{E}\{·\}$, ${(·)}^T$, $\bigvee$ and $\oplus$ denote expectation, transpose, logical OR and XOR, respectively; $P(·)$ denotes probability mass function (PMF), while $P(·|·)$ is the corresponding conditional counterpart; $\mathcal{B}(p)$ denotes a Bernoulli PMF with success probability p; $\mathcal{N}(\mu ,{\sigma }^2)$ denotes a Gaussian PDF with mean $\mu$ and variance ${\sigma }^2$; $\mathcal{Q}(·)$ denotes the complementary CDF of a standard normal random variable, i.e. $\mathcal{N}(0,1)$; $u(·)$ denotes the Heaviside unit-step function; ${\mathcal{D}}_{\mathrm{K}L}(·||·)$ denotes the Kullback-Leibler (KL) divergence between distributions (Cover and Thomas 2006). The notation $\widehat{(·)}$ is denoted to indicate the Maximum Likelihood (ML) estimate of the unknown parameter $(·)$. Also, the symbol $\sim$ means “distributed as” and “$\propto$” is used to underline statistical equivalence between decision statistics. Finally, the notation ${\mathit{\delta }}_1\ge .{\mathit{\delta }}_2$ means that each element of ${\mathit{\delta }}_1$ is greater or equal than the corresponding element of ${\mathit{\delta }}_2$, and at least one element of ${\mathit{\delta }}_1$ is strictly greater than the corresponding element of ${\mathit{\delta }}_2$.

2 All sensors transmit directly to the FC (which is assumed within their communication range). The framework may be extended to other network topologies (e.g. tandem, hierarchical) with fusion rules to be applied to the aggregation nodes. This aspect is beyond the scope of the paper.

3 The following short-hand notation has been employed: ${\mathcal{D}}^{\pi }\triangleq {\mathcal{D}}_{\mathrm{K}L}(\mathcal{B}({\widehat{\pi }}_1)||\mathcal{B}({\widehat{\pi }}_0))$, ${\mathcal{D}}^{\phi }\triangleq {\mathcal{D}}_{\mathrm{K}L}(\mathcal{B}(\widehat{\phi })||\mathcal{B}({\widehat{\pi }}_0))$, ${\mathcal{D}}^{\phi +}\triangleq {\mathcal{D}}_{\mathrm{K}L}(\mathcal{B}({\widehat{\phi }}^{+})||\mathcal{B}({\widehat{\pi }}_0))$, ${\mathcal{D}}_m^{\pi }\triangleq {\mathcal{D}}_{\mathrm{K}L}(\mathcal{B}({\widehat{\pi }}_{m,1})||\mathcal{B}({\widehat{\pi }}_{m,0}))$, ${\mathcal{D}}_m^{\phi }\triangleq {\mathcal{D}}_{\mathrm{K}L}(\mathcal{B}({\widehat{\phi }}_m)||\mathcal{B}({\widehat{\pi }}_{m,0}))$, ${\mathcal{D}}_m^{\phi +}\triangleq {\mathcal{D}}_{\mathrm{K}L}(\mathcal{B}({\widehat{\phi }}_m^{+})||\mathcal{B}({\widehat{\pi }}_{m,0}))$, $z_{k,i}\triangleq y_k[i]\oplus y_k[i+1]$, ${\chi }_0\triangleq \left(\widehat{\phi }-{\widehat{\pi }}_0\right)$, ${\chi }_{m,0}\triangleq \left({\widehat{\phi }}_m-{\widehat{\pi }}_{m,0}\right)$ and $v(p)\triangleq p(1-p)$.

4 With a slight abuse of notation we will use the symbol ${\mathrm{\Lambda }}_{\mathrm{L}}$ to denote both LMPT and LMMPT, depending on the specific scenario.