Distributed Hypothesis Testing over Noisy Broadcast Channels

In Internet of Things (IoT) networks, data are collected at sensors and transmitted over a wireless channel to remote decision centers, which decide on one or multiple hypotheses based on the collected information. In this paper, we study simple binary hypothesis testing with a single sensor but two decision centers. The results can be combined with previous studies focusing on multiple sensors and a single decision center to tackle the practically relevant case of multiple sensors and multiple decision centers. We consider a single sensor for simplicity and because our main focus is on studying the tradeoff between the performances at the two decision centers that can arise because the single sensor has to send information over the channel that can be used by both decision centers. A simple, but highly suboptimal, approach would be to time-share communication and serve each of the two decision centers only during a part of the transmission. As we will see, better schemes are possible, and, in some cases, it is even possible to serve each of the two decision centers as if the other center was not present in the system.

In this paper, we follow the information-theoretic framework introduced in [1,2]. That means each terminal observes a memoryless sequence, and depending on the underlying hypothesis $\mathcal{H}\in \{0,1\}$, all sequences follow one of two possible joint distributions, which are known to all involved terminals. A priori, the transmitter, however, ignores the correct hypothesis and has to compute its transmit signal as a function of the observed source symbols only. Decision centers observe outputs of the channel, and, combined with their local observations, they have to make a decision on whether $\mathcal{H}=0$ or $\mathcal{H}=1$. The performance of the decision center is measured by its type-II error exponent, i.e., the expontial decay in the length of the observations of the probability of deciding on $\mathcal{H}=0$ when the true hypothesis is $\mathcal{H}=1$. As a constraint on the decision center, we impose that the type-I error probability, i.e., the probability of deciding $\mathcal{H}=1$ when the true hypothesis is $\mathcal{H}=0$, vanishes (at any desired speed) with increasing observation lengths. The motivation for studying such asymmetric requirements on the two error probabilities stems, for example, from alert systems, where the miss-detection event is much more harmful than the false-alarm event, and, as a consequence, in our systems we require the miss-detection probability to decay much faster than the false-alarm probability.

This problem setting has first been considered for the setup with a single sensor and a single decision center when communication is over a noiseless link of given capacity [1,2]. For this canonical problem, the optimal error exponent has been identified in the special cases of testing against independence [1] and testing against conditional independence [3,4].

The scheme proposed by Shimokawa–Han–Amari in [3,4] yields an achievable error exponent for all distributed hypothesis testing problems (not only testing against conditional independence) [3,4], but it might not be optimal in general [5]. The Shimokawa–Han–Amari (SHA) scheme has been extended to various more involved setups such as noiseless networks with multiple sensors and a single decision center [2,6,7]; networks where the sensor and the decision center can communicate interactively [8,9]; multi-hop networks [10]; networks with multiple decision centers [10,11,12,13].

The works most closely related to the current paper are [10,12,13,14,15,16]. Specifically, Refs [10,12,13,14] consider a single-sensor multi-detector system where communication is over a common noiseless link from the sensor to all decision centers. Focusing on two decision centers, two scenarios can be encountered here: (1) the two decision centers have the same null and alternate hypotheses, and as a consequence, both aim at maximizing the error exponent under the same hypothesis $\mathcal{H}$; or (2) the two decision centers have opposite null and alternate hypotheses and thus one decision center wishes to maximize the error exponent under hypothesis $\mathcal{H}=0$ and the other under hypothesis $\mathcal{H}=1$. The second scenario is motivated by applications where the decision centers have different goals. Hypothesis testing for scenario 1) was studied in [10,12,13,14], and the results showed a tradeoff between the exponents achieved at the two decision centers. Intuitively, the tradeoff comes from the fact that communication from the sensor is serving both decision centers at the same time. Scenario 2) was considered in [12,13]. In this case, a tradeoff only occurs when the sensor’s observation alone provides no advantage in guessing the hypothesis. Otherwise, a tradeoff-free exponent region can be achieved by the following simple scheme: the sensor takes a tentative guess on the hypothesis based only on its local observations. It communicates this tentative guess to both decision centers using a single bit and then dedicates the rest of the communication using a dedicated SHA scheme only to the decision center that wishes to maximize the error exponent under the hypothesis that does not correspond to its guess. The other decision center simply keeps the transmitter’s tentative guess and ignores the rest of the communication.

In this paper, we extend these previous works to memoryless broadcast channels (BC). Hypothesis testing over BCs was already considered in [10], however, only for above scenario 1 where both decision centers have the same null and alternate hypothesis and in the special case of testing against conditional independence, in which case the derived error exponents were proved to be optimal. Interestingly, when testing against conditional independence over noisy channels, only the capacity of the channel matters but not the properties, see [15,16]. General hypothesis testing over noisy channels is much more challenging and requires additional tools, such as joint source-channel coding and unequal error protection (UEP) coding [17]. The latter can, in particular, be used to specially protect the communication of the sensor’s tentative guess, which allows one to avoid a degradation of the performance of classical hypothesis testing schemes.

We present general distributed hypothesis testing schemes over memoryless BCs, and we analyze the performances of these schemes with a special focus on the tradeoff in exponents they achieve for the two decision centers. We propose two different schemes, depending on whether the sensor can distinguish with error probability $\ne 1/2$ the two null hypotheses at the two decision centers. If a distinction is possible (because the decision centers have different null hypothesis and the sensor’s observations follow different marginal distributions under the two hypotheses), then we employ a similar scheme as proposed in [12,13] over a common noiseless link, but where the SHA scheme is replaced by the UEP-based scheme for DMCs in [15]. That means, the sensor makes a tentative guess about the hypothesis and conveys this guess to both decision centers using an UEP mechanism. Moreover, the joint source-channel coding scheme in [15] with dedicated codebooks is used to communicate to the decision center that aims to maximize the error exponent under the hypothesis that does not correspond to the sensor’s tentative guess. This scheme shows no tradeoff between the exponents achieved at the two decision centers in various interesting cases. Sometimes, however, a tradeoff arises because even under UEP the specially protected messages can be in error and because the decision centers can confuse the codewords of the two different sets of codebooks. For the case where the sensor cannot reasonably distinguish the alternate hypotheses at the two decision centers (because both decision centers have the same alternate hypotheses or the sensor’s observations have the same marginal observations under both hypotheses), we present a scheme similar to [10] but again including UEP. In this scheme, a tradeoff between the exponents achieved at the two decision centers naturally arises and mostly stems from the inherent tradeoff in distributed lossy compression systems with multiple decoders having different side informations.

Consider the distributed hypothesis testing problem in Figure 1, where a transmitter observes sequence $X^n$, Receiver 1 sequence $Y_1^n$, and Receiver 2 sequence $Y_2^n$. Under the null hypothesis: and under the alternative hypothesis: for two given pmfs $P_{X{Y}_1{Y}_2}$ and $Q_{X{Y}_1{Y}_2}$. The transmitter can communicate with the receivers over n uses of a discrete memoryless broadcast channel $(\mathcal{W},{\mathcal{V}}_1\times {\mathcal{V}}_2,P_{V_1{V}_2|W})$ where $\mathcal{W}$ denotes the finite channel input alphabet and ${\mathcal{V}}_1$ and ${\mathcal{V}}_2$ the finite channel output alphabets. Specifically, the transmitter feeds inputs to the channel, where $f^{\left(n\right)}$ denotes the chosen (possibly stochastic) encoding function Each Receiver $i\in \{1,2\}$ observes the BC ouputs $V_i^n$, where for a given input $W_t=w_t$, Based on the sequence of channel outputs $V_i^n$ and the source sequence $Y_i^n$, Receiver i decides on the hypothesis $\mathcal{H}$. That means it produces the guess for a chosen decoding function

There are different possible scenarios regarding the requirements on error probabilities. We assume that each receiver is interested in only one of the two exponents. For each $i\in \{1,2\}$, let ${\mathsf{h}}_i\in \{0,1\}$ be the hypothesis whose error exponent Receiver i wishes to maximize, and ${\overline{\mathsf{h}}}_i$ the other hypothesis, i.e., ${\overline{\mathsf{h}}}_i\in \{0,1\}$ and ${\mathsf{h}}_i\ne {\overline{\mathsf{h}}}_i$. (The values of ${\mathsf{h}}_1$ and ${\mathsf{h}}_2$ are fixed and part of the problem statement.) We then have:

To simplify the notation in the sequel, we use the following shorthand notations for the pmfs $P_{X{Y}_1{Y}_2}$ and $Q_{X{Y}_1{Y}_2}$.

For each $i\in \{1,2\}$: and

We propose two coding schemes yielding two different exponent regions, depending on whether or

Notice that (13) always holds when ${\mathsf{h}}_1={\mathsf{h}}_2$. In contrast, given (14), then obviously ${\mathsf{h}}_1\ne {\mathsf{h}}_2$.

Before presenting our main results, we recall the achievable error exponent over a discrete memoryless channel reported in [15] (Theorem 1).

Fix $\mu >0$, a sufficiently large blocklength n, auxiliary distributions $p_T$, $p_{T_1|T}^1$ and $p_{T_2|T}^2$ over $\mathcal{W}$, conditional channel input distributions $p_{W|T{T}_1}^1$ and $p_{W|T{T}_2}^2$, and conditional pmfs $p_{S|X}^1$ and $p_{S|X}^2$ over a finite auxiliary alphabet $\mathcal{S}$ such that for each $i\in \{1,2\}$:

The mutual information in (33) is calculated according to the joint distribution:

For each $i\in \{1,2\}$, if $I_{p^i}(S;X)<I_{p^i}(W;V_i|T,T_i)$, choose rates

If $I_{p^i}(S;X)\ge I_{p^i}(W;V_i|T,T_i)$, then choose rates

Again, all mutual informations in (35)–(38) are calculated with respect to the pmf in (34).

Code Construction: Generate a sequence $T^n=(T_1,\dots ,T_n)$ by independently drawing each component $T_k$ according to $p_T$. For each $i\in \{1,2\}$, generate a sequence $T_i^n=(T_{i,1},\dots ,T_{i,n})$ by independently drawing each $T_{i,k}$ according to $p_{T_i|T}^i(.|t)$ when $T_k=t$. In addition, construct a random codebook superpositioned on $(T^n,T_i^n)$ where the k-th symbol $W_k(i;m)$ of codeword $W^n(i;m)$ is drawn independently of all codeword symbols according to $p_{W|T{T}_i}^i(·|t,t_i)$ when $T_k=t$ and $T_{i,k}=t_i$. Finally, construct a random codebook by independently drawing the k-th component $S_k(i;m,\ell )$ of codeword $S^n(i;m,\ell )$ according to the marginal pmf $p_S^i$.

Reveal all codebooks and the realizations $t^n,t_1^n,t_2^n$ of the sequences $T^n,T_1^n,T_2^n$ to all terminals.

Transmitter: Given source sequence $X^n=x^n$, the transmitter looks for indices $(i,m,\ell )\in \{1,2\}\times \{1,\dots ,\lfloor 2^{n{R}_1}\rfloor \}\times \{1,\dots ,\lfloor 2^{n{R}_i^{\prime }}\rfloor \}$ such that codeword $s^n(i;m,\ell )$ from codebook ${\mathcal{C}}_S^i$ satisfies and the corresponding codeword $w^n(i;m)$ from codebook ${\mathcal{C}}_W^i$ satisfies

(Notice that when $\mu$ is sufficiently small, then Condition (41) can be satisfied for at most one value $i\in \{1,2\}$, because $p_X^1\ne p_X^2$.) If successful, the transmitter picks uniformly at random one of the triples $(i,m,\ell )$ that satisfy (41), and it sends the sequence $w^n(i;m)$ over the channel. If no triple satisfies Condition (41), then the transmitter sends the sequence $t^n$ over the channel.

Receiver $i\in \{1,2\}$: Receives $v_i^n$ and checks whether there exist indices $(m^{\prime },{\ell }^{\prime })$ such that the following three conditions are satisfied:

If successful, it declares ${\widehat{\mathcal{H}}}_i={\overline{\mathsf{h}}}_i$. Otherwise, it declares ${\widehat{\mathcal{H}}}_i={\mathsf{h}}_i$.