Low-Complexity,Distributed Characterization of Interferers in Wireless Networks

Abstract

We consider a large-scale wireless network that uses sensors along its edge to estimate the characteristics of interference from neighboring networks or devices. Each sensor makes a noisy measurement of the received signal strength (RSS) from an interferer, compares its measurement to a threshold, and then transmits the resulting bit to a cluster head (CH) over a noisy communication channel. The CH computes the maximum likelihood estimate (MLE) of the distance to the interferer using these noise-corrupted bits. We propose and justify a low-complexity threshold design technique in which the sensors use nonidentical thresholds to generate their bits. This produces a dithering effect that provides better performance than previous techniques that use different non-identical thresholds or the case in which all the sensor motes use an identical non-optimal threshold. Our proposed technique is also shown (a) to be of low complexity compared to previous non-identical threshold approaches and (b) to provide performance that is very close to that obtained when all sensors use the identical, but unknown, optimal threshold. We derive the Cramér-Rao bound (CRB) and also show that the MLE using our dithered thresholds is asymptotically both efficient and consistent. Simulations are used to verify these theoretical results.

1. Introduction

Large-scale deployments of wireless LANs in unlicensed RF bands are often subject to interference from many sources. We have encountered this problem in the e-Stadium wireless testbed [1], which enables football fans in the stadium at Purdue to access multimedia content related to the game [2] via 802.11b and 3G networks. The locations and coverage areas of the 802.11b access points (APs) in the stadium are shown in Figure 1. The two interfering APs also shown in the figure may disrupt eStadium services for fans sitting along the outer edge of the stands or in the tailgating area north of the stadium. The locations and settings of these interfering access points or devices change over time. The eStadium testbed must sense these changes and adapt its channel assignments and power levels to ensure that its users experience satisfactory Quality of Service (QoS).

Figure 1

The eStadium testbed at Purdue's Ross Ade stadium includes (1) twelve 802.11 APs with directional antennas that provide coverage, shaded in orange, of the outdoor seating area (2) ten APs with omni antennas that cover the indoor seating areas, (3) a Vivato network that serves the parking area north of the stadium, and (4) clusters of sensors in the concourse area of the stadium. Interfering APs are generally WiFi networks operating in the vicinity of the stadium.

The eStadium testbed includes clusters of wireless sensors that are distributed along the concourse area of the stadium [3]. They currently gather and process information from this area and make it available to fans and security personnel during games. We propose that these sensors perform the additional task of characterizing the sources of interference with the 802.11b-based portion of the eStadium testbed.

The information gathered about interferers by these sensors is not directly available to the eStadium APs because of their directional antennas or shadowing by the stadium's structure. A Smart WiFi system [4] would thus not be able to sense and adjust to the presence of these external interferers. This proposed use of the sensors, combined with algorithms to alter the 802.11b channel assignments and power settings, is thus a cognitive networking approach to enabling the coexistence of many systems in unlicensed bands.

The contributions of this paper include the following.

• (a)

Analysis and improvement of MLE approaches in which sensors conserve energy by minimizing the amount of data they transmit. Each sensor thresholds its noisy measurement of the interferer's signal strength, adds the resulting bit to a packet carrying other data, and transmits the packet to the CH via a noisy channel. We consider and justify the case in which each sensor uses a different threshold and compare it with cases in which every sensor uses the same threshold.

• (b)

  Proofs of the asymptotic efficiency and consistency of this new MLE approach and derivation of the Cramér-Rao bound (CRB). Given that the thresholds in our case are non-identical, the standard proofs of asymptotic consistency and efficiency do not hold.

• (c)

  Verification that the MLE based on the use of non-identical thresholds by the sensors performs: (i) as well as one based on the use of identical optimal thresholds, even when the number of sensors is small, (ii) significantly better than the one based on the use of identical non-optimal thresholds, and (iii) is of lower complexity and has a performance that is better than or as good as existing non-identical threshold techniques. Because the identical optimal threshold case requires prior knowledge of the true value of the unknown parameter, and existing non-identical techniques involve the solution of a complex optimization problem, our non-identical threshold approach is much more practical and of lower complexity in terms of the design of the thresholds.

In Section 2, we review the most relevant prior work in this area. Sections 3 and 4 describe the system model and the formulation of the sensor fusion problem. The performance of the algorithm is evaluated and compared with existing techniques in Section 5, and conclusions are provided in Section 7.

2. Related Work

In the context of transmitter location estimation for wireless networks, the authors in [5–7] propose expectation maximization (EM) algorithms to locate multiple transmitters using received power levels at arbitrarily placed receivers. The authors in [8] consider a cognitive wireless network in which secondary users measure signal strengths from primary users to estimate the distance to the primary users. They propose estimation algorithms under different channel fading conditions. In [9], the authors study an 802.11 cognitive mesh network (COMNET) in which mesh clients (MC) calculate their distances from the primary stations with triangulation-based localization techniques that use RSS measurements. These localization techniques assume that the MCs are synchronized and that they are located on the edge of the secondary 802.11 network; otherwise, they may not be able to detect the interference from the primary stations. In the above papers, the authors do not consider the use of thresholded measurements or the transmission of measurements over noisy channels.

In the context of distributed estimation in wireless sensor networks, the authors in [10, 11] consider 1-bit quantization using identical and non-identical thresholds and obtain the maximum-likelihood estimate of an unknown parameter. They account for measurement noise that is Gaussian or has an unknown distribution but do not consider other sources of error, such as noise in the communication channel. A similar situation is examined in [12], where multiple-bit quantized information is used to locate a target in a sensor field under error-free channel conditions. A nonparametric approach to density estimation using a sensor network was introduced in [13]. The authors considered the case where 1-bit quantized data is transmitted to the CH using random thresholds from a pmf. As with the previous papers, however, processing by sensors and the wireless channel between the sensors and the CH are considered to be error free, which is typically not the case in realistic situations. In [14], the authors study channel aware target localization using 1-bit quantized data. They analyze the effects on the root mean squared error (RMSE) of the MLE due to communication channel impairments. They consider the BSC, Rayleigh fading with coherent reception and non-coherent reception. However, in their work, they do not address the design of the 1-bit quantization algorithm for transmission over noisy communication channels.

In [15, 16], the authors consider a 1-bit quantization framework for noisy Gaussian communication links. However, it is assumed that either all sensors use the same threshold or use one of two thresholds. More recently, in [17], the authors have proposed an MLE-based distributed estimation algorithm using 1-bit quantized data that is transmitted over a BSC. The context in which the estimation algorithm is analyzed is for secure data transmission in wireless sensor networks, but it is assumed that all the sensors use identical thresholds.

Several other papers, including [18–21], also study the distributed estimation problem, but their approach is based on the best linear unbiased estimate (BLUE) at the CH instead of the MLE. This approach is typically not appropriate or optimal when the received data at the CH is a nonlinear function of the unknown parameter.

Our approach is unique because it (a) exploits and justifies the use of different thresholds by the sensors when quantizing their noisy measurements and (b) accounts for noisy measurements by the sensors and error-prone processing and communications between the sensors and the CH. Our analysis of the MLE in this new approach will show that uniformly-spaced thresholds produces a dithering effect that leads to near-optimal performance when the only information available about the parameter being estimated is its support. This is very important because previous approaches based on the use of an identical threshold by all sensors work well only when the chosen threshold is either very near the unknown true value, or the number of sensors is very large. Furthermore, our non-identical threshold design algorithm is significantly less complex and performs as good as or better than existing non-identical threshold techniques, such as the one in [10].

3. System Model and Problem Motivation

3.1. System Characteristics and Considerations

The following characteristics of the wireless sensor network and sensor fusion algorithm are assumed in this paper. They are motivated by the eStadium project but are relevant to many other systems operating in unlicensed bands.

(a) Architecture

The system consists of a network of wireless APs and a single-hop cluster of N spatially distributed wireless sensors deployed along the edge of the wireless network. Each sensor measures the RSS from an interfering AP, compares it to its threshold, and relays the resulting bit to the CH. The CH fuses the bits it receives to produce an estimate of the signal strength and distance to the interfering AP.

(b) Measurement Errors

Due to large-scale fading and shadowing effects, the RSS $X(k)$ observed at sensor k is assumed to be log normally distributed, as in [22, 23]. The mean $\mu (R)$ of this distribution is a function of the distance R from the transmitter to the receiver while the variance ${\sigma }^2$ is independent of R. We assume that $\mu (R)$ follows a path-loss-exponent model; hence,

$\mu \left(R\right)=K-10\alpha \log \left(R\right),$

(1)

where α is the propagation law exponent, and K is the close-in reference power, that is, the power very close to the transmitter. In rest of the paper, the symbol μ will be used interchangeably with $\mu (R)$ . On a dB scale, the received RSS at the sensors can be expressed as

$X_k=\mu \left(R\right)+n_k,\hspace{1em}k=1\cdots N,$

(2)

where $\mu (R)$ is the mean and $n_k~𝒩(0,{\sigma }_n^2)$ is i.i.d. Gaussian noise that is independent of μ. The term ${\sigma }_n$ is commonly referred to as the dB spread of the log-normal shadowing and is typically between 4 dB and 12 dB. We refer to this noise as the measurement noise because it corrupts the SNR measurement of each sensor, and we assume that its characteristics are known by the CH. Furthermore, we assume that the sensors are close enough to each other relative to the distance from the interferer that the received RSS at each sensor has the same mean; however, relative to each other, they are spaced far enough to ensure that the noise processes affecting different sensors are independent. The case of dependent noise is left for future work.

(c) Energy Limits

Energy efficiency is critical in the design of battery-powered sensor networks, so sensor k thresholds the RSS value it observes to produce only one bit, denoted by $b_k$ , that is to be sent to the CH. The $b_k$ 's are transmitted over a parallel access, noisy communication channel to the CH. These bits may be transmitted individually over the wireless channel or may be combined with other data into packets transmitted over an 802.15.4 (ZigBee) channel [24].

(d) Communication Channel

The wireless channel between each sensor, and the CH is modeled as a binary symmetric Channel (BSC) with a crossover probability of ϵ [25]. We assume that the value of ϵ is perfectly estimated at the CH; this can be achieved by the use of pilot training data transmitted by the sensors to the CH during the initialization process. We further assume that the communication channel is static for a period of T seconds; hence, ϵ does not change during the estimation process. For completeness, in Section 5, we also analyze the performance degradation of our algorithms due to a mismatch between the estimated value of ϵ and the true value of ϵ. The choice of a symmetric channel is not required for our analysis but does simplify comparisons. Collisions of bits/packets in the communication channel are assumed to result in their loss and subsequent retransmission. The BSC model thus applies to transmitted bits/packets that are not involved in collisions. Alternatively, one could assume that the sensors' transmissions are scheduled via a collision-free protocol, such as the one in [26], or that they use the TDMA-based frame that is available under the 802.15.4 (ZigBee) protocol [24].

(e) Reliability and Trustworthiness

Noisy communications may not be the only source of errors affecting the sensors' decisions before they reach the CH. The sensors may make processing or storage errors. They may be compromised and intentionally report incorrect results with some probability in order to compromise performance without being detected. These additional error sources can be aggregated with the communication errors, resulting in a larger crossover probability. These chapter's results can thus be used to characterize the sensitivity of fusion algorithms to these error sources.

(f) Industrial, Scientific, and Medical (ISM) Band

The true mean value of the RSS distribution (see (b), above), denoted by ${\mu }_0$ , is an unknown parameter that lies in the interval $[{\mu }_l,{\mu }_u]$ . The lower bound, ${\mu }_l$ , corresponds to the maximum range at which the sensors are able to receive and decode a packet from the interferer. The upper bound, ${\mu }_u$ , is related to the maximum transmission power defined by the incumbent network's communication standard. In the eStadium network, these bounds are determined by a typical 802.11b AP operating in the 2.4 GHz band. For a specific example, we use the specs of a Cisco Aironet 1200 series AP [27] with an omni-directional antenna. Its maximum transmission power of 100 mW at a distance of $R=1\hspace{0.17em}\text{m}$ from the transmitter corresponds to the upper bound; that is, ${\mu }_u=-10$  dB or 20  dBm. For the lower bound, the maximum distance at which a typical commercial 802.11 device can receive and decode a packet from an Aironet AP is $R=200$  m, which corresponds to ${\mu }_l=-67$  dB or $-37$  dBm. Figure 2(b) shows the relationship between μ and R for the signal received from a typical AP.

Figure 2

Plot shows the relationship between μ and R with $K=-10$  dB, and $\alpha =2.5$ .

(g) Periodic Updates

We assume that the estimates μ and R are updated every T seconds to capture any changes in the set of interferers. T is assumed to be greater than the time required for all sensors to collect a measurement and transmit their bits to the CH. In this paper, we focus on the performance of estimates for a single time period of length T. The better the estimate produced in this period, the faster an iterative algorithm based on it will converge. An iterative algorithm that builds on the results is presented in [28].

In summary, sensor k transmits a single bit of information $b(k)$

$b_k=\{\begin{array}{cc}+1\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{X}_k>{\tau }_k\hfill \\ -1\hfill & \text{otherwise},\hfill \end{array}$

(3)

where ${\tau }_k$ is the threshold used at sensor k to quantize the RSS $X_k$ to one bit. The set of $b(k)\prime s$ are transmitted to the CH, which uses them to estimate μ and then estimate R via (1). Figure 3 shows the system model and the signal processing block diagram of the cluster of sensors.

Figure 3

System block diagram for a cluster of wireless sensors. The sensor' RSS measurements are quantized using the dithered quantization technique. The resulting 1-bit values are transmitted over a BSC to the CH, which calculates the MLE of R.

3.2. Optimal Identical Threshold Design

The optimal threshold can be defined to be the threshold that minimizes the Cramér-Rao bound (CRB) for any unbiased estimator of μ. This optimization criteria is similar to that proposed in [10, 11] for the error-free communication scenario. In this case, all the sensor motes use the same optimal threshold derived by solving the optimization problem. The thresholds can be expressed as ${\tau }_k={\tau }^{\text{opt}}$ for $k=1\cdots N$ , where ${\tau }^{\text{opt}}$ denotes the optimal threshold. The CRB for any unbiased estimator μ, denoted by $\bar{\mu }$ and derived in Section 5, is given by

$\mathrm{Var}\left(\bar{\mu }\right)\ge \mathcal{I}{\left(\mathbf{\tau },{\mu }_0\right)}^{-1},$

(4)

where $ℐ(\mathit{\tau },{\mu }_0)$ is called the Fisher information (FI). As derived later in the paper, the FI is expressed as

$\mathcal{I}\left(\mathbf{\tau },{\mu }_0\right)={\displaystyle \sum }_{k=1}^N\mathcal{I}\left({\tau }_k,{\mu }_0\right),$

(5)

where

$\begin{array}{cc}\hfill & \mathcal{I}\left({\tau }_k,{\mu }_0\right)\hfill \\ \hfill & =\frac{{\left(\left(1-2ϵ\right)f_n\left({\tau }_k-{\mu }_0\right)\right)}^2}{ϵ+\left(1-2ϵ\right){\bar{F}}_n\left({\tau }_k-{\mu }_0\right)\left(1-ϵ-\left(1-2ϵ\right){\bar{F}}_n\left({\tau }_k-{\mu }_0\right)\right)}\hfill \end{array}$

(6)

is the FI for sensor k, $\mathit{\tau }=[{\tau }_1\cdots {\tau }_N]$ , ${\mu }_0$ is the true value of μ, and ${\bar{F}}_n(·)$ and $f_n(·)$ are the complementary cumulative distribution function (ccdf) and pdf of the measurement noise n, respectively. Due to lack of space, we only outline the general technique to obtain the critical points of the CRB function. Calculating the gradient of the r.h.s of (4) with respect to ${\tau }_k$ for $k=1\cdots N$ , it can easily be shown that when ${\tau }_k={\mu }_0$ for each k, the N equations are simultaneously equal to zero, and the Hessian of the CRB function is positive definite. Hence, the optimal threshold is ${\tau }^{\text{opt}}={\mu }_0$ . Note that this choice of threshold is not feasible because ${\mu }_0$ is not known in advance.

An interesting observation is that the optimal identical threshold choice does not depend on ${\sigma }_n$ or ϵ. It is only a function of the true unknown value ${\mu }_0$ . Furthermore, the performance of the identical threshold scheme is very sensitive to the choice of threshold, as shown in Section 6. Even a slight deviation of the threshold value from the true value of μ can result in significant performance degradation. Hence, our goal is to design a quantization scheme which is independent of the true value of μ and has a performance comparable to the optimal identical threshold case.

3.3. Threshold Design for Dithered Quantization

Because use of the optimal identical threshold for the 1-bit quantization step requires prior knowledge of the unknown parameter, we propose a framework in which each sensor uses a different threshold. This ensures that at least a few thresholds will be close to the true value of the unknown parameter. Furthermore, using non-identical thresholds at the sensors for the 1-bit quantization produces a dithering effect that reduces the bias in the estimator (as shown in Section 5). We thus refer to this technique as dithered quantization. Since it is well known that the uniform distribution has maximum entropy among all continuous distributions with compact support [25], we assume that μ is uniformly distributed over the interval $[{\mu }_l,{\mu }_u]$ and hence space the quantization thresholds equally over this interval. This leads to the thresholds being assigned for sensor mote k according to the following equation:

${\tau }_k={\mu }_l+\frac{k\left({\mu }_u-{\mu }_l\right)}{N+1}.$

(7)

3.4. Binning-Based Nonidentical Threshold Design

Another approach to the use of non-identical threshold was proposed in [10]. They consider designing the threshold vector $\mathit{\tau }=\{{\tau }_k,k\in \mathbb{Z}\}$ and the associated frequency vector $\mathit{\rho }=\{{\rho }_k,k\in \mathbb{Z}\}$ to minimize the weighted asymptotic variance. The frequency for threshold ${\tau }_k$ is defined as ${\rho }_k=N_k/N$ , where $N_k$ is the total number of sensors transmitting binary information using threshold ${\tau }_k$ , and N is the total number of sensors in the network. Although the problem studied in [10] was for the error-free communication channel scenario, it can be modified for the BSC case. Hence, for our setup, this optimization problem for a uniform weighting function between $[{\mu }_l,{\mu }_u]$ denoted by $𝒲(\mu )=1/({\mu }_u-{\mu }_l)$ can be formulated as the following second-order cone program (SOCP) with auxiliary variable t as

$\begin{array}{cc}\hfill & {\mathbf{\rho }}^{\star }=\underset{\left(t,\mathbf{\rho }\right)}{\text{argmin}}\hspace{0.17em}t,\hfill \\ \hfill & s.t.\Vert \mathbf{s}-\mathbf{P}\mathbf{\rho }\Vert \le t,\hfill \\ \hfill & \hspace{1em}\mathbf{\rho }\ge \mathbf{0},\hspace{1em}{\mathbf{\rho }}^T\mathbf{1}=1,\hfill \end{array}$

(8)

where $\mathbf{s}:=[S({\mu }_0)\cdots S({\mu }_M){]}^T$ , $\mathit{\rho }:=[{\rho }_1\cdots {\rho }_L{]}^T$ , L is the number of thresholds, M is the number of discrete points at which the function $S(\mu )$ is evaluated, the function $S(\mu )$ is given by

$S\left(\mu \right)=\mathcal{K}{\mathcal{W}}^{1/2}\left(\mu \right),\hspace{1em}\hspace{1em}\mathcal{K}=\frac{{\int }_{-\infty }^{+\infty }{\left(\left(1-2ϵ\right)f_n\left(u\right)\right)}^2/\left(\left(ϵ+\left(1-2ϵ\right){\bar{F}}_n\left(u\right)\right)\left(1-ϵ-\left(1-2ϵ\right){\bar{F}}_n\left(u\right)\right)\right)du}{{\int }_{-\infty }^{+\infty }{\mathcal{W}}^{1/2}\left(\mu \right)d\mu },$

(9)

and P is a $M\times L$ matrix with its $(i,j)$ th entry given by

${\left[\mathbf{P}\right]}_{ij}=\frac{{\left(\left(1-2ϵ\right)f_n\left({\tau }_j-{\mu }_i\right)\right)}^2}{\left(ϵ+\left(1-2ϵ\right){\bar{F}}_n\left({\tau }_j-{\mu }_i\right)\right)\left(1-ϵ-\left(1-2ϵ\right){\bar{F}}_n\left({\tau }_j-{\mu }_i\right)\right)}.$

(10)

Using numerical techniques to approximate the numerator of 𝒦, $S(\mu )$ can be expressed as

$\begin{array}{c}S\left(\mu \right)=\frac{{\int }_{-\infty }^{+\infty }{\left(\left(1-2ϵ\right)f_n\left(u\right)\right)}^2/\left(\left(ϵ+\left(1-2ϵ\right){\bar{F}}_n\left(u\right)\right)\left(1-ϵ-\left(1-2ϵ\right){\bar{F}}_n\left(u\right)\right)\right)du}{\left|{\mu }_u-{\mu }_l\right|}.\end{array}$

(11)

For the rest of the paper, we refer to this technique as the binning-based non-identical threshold approach. In Section 5, we compare the performance of all three threshold design schemes.

3.5. Effect of Network Topology on Threshold Design

Wireless sensor networks change with time because sensors can fail as their batteries die, or new sensors may be added to an existing network. Our threshold design is robust to these changes, since when the number of sensors is large, the thresholds are densely distributed over the interval, the loss of a few sensors will not result in a significant loss of information. When the number of sensors is small, the thresholds are coarsely spread over the interval. A few failures might thus result in a significant decrease in the number of bits received by the CH. The CH can then reassign thresholds by communicating with the sensors over the wireless channel. When a new sensor joins the network, it can request a threshold from the CH, choose one based on its unique MAC address, or the CH can reassign all sensors' thresholds according to the algorithm in Section 3.3. On the other hand, the binning-based non-identical threshold technique requires the solution to the optimization problem (8) each time the thresholds need to be assigned. Hence, compared to our proposed approach, the binning-based approach is of much higher computational complexity and therefore cannot easily adapt to changes in the network topology.

4. Sensor Fusion Algorithm

We use maximum-likelihood estimation (MLE) techniques to estimate μ and then use the invariance property of MLE's [29] obtain an estimate for R. For sensor mote k, we denote ${ℛ}_k$ to be the random variable (r.v) for the received bit and $r_k$ to be the value of the r.v. Since the received bits ${ℛ}_k$ are independent, nonidentically distributed (i.n.i.d) Bernoulli random variables (rv's),

$\begin{array}{c}\text{Pr}\left({\mathcal{R}}_k=1\hspace{0.17em}|\hspace{0.17em}\mu \right)=ϵ+\left(1-2ϵ\right){\bar{F}}_n\left({\tau }_k-\mu \right),\\ \text{Pr}\left({\mathcal{R}}_k=-1\hspace{0.17em}|\hspace{0.17em}\mu \right)=\left(1-ϵ\right)-\left(1-2ϵ\right){\bar{F}}_n\left({\tau }_k-\mu \right),\end{array}$

(12)

where ${\bar{F}}_n(·)$ is the complementary cumulative distribution function (ccdf) of the measurement noise $n~𝒩(0,{\sigma }_n^2)$ . Denoting the likelihood function of each received bit by $f(r_k\hspace{0.17em}|\hspace{0.17em}\mu )$ , the likelihood function for the received vector of observations $\mathbf{r}=[r_1,\dots ,r_N]$ becomes

$\begin{array}{cc}\hfill f\left(\mathbf{r}\hspace{0.17em}|\hspace{0.17em}\mu \right)& ={\displaystyle \prod }_{k=1}^{N}f\left(r_k\hspace{0.17em}|\hspace{0.17em}\mu \right)\hspace{0.17em}\hspace{0.17em}\hfill \\ \hfill & ={\displaystyle \prod }_{k=1}^N\text{Pr}{\left({\mathcal{R}}_k=1\hspace{0.17em}|\hspace{0.17em}\mu \right)}^{{\mathbb{1}}_{\left\{r_k=1\right\}}}\text{Pr}{\left({\mathcal{R}}_k=-1\hspace{0.17em}|\hspace{0.17em}\mu \right)}^{{\mathbb{1}}_{\left\{r_k=-1\right\}}}.\hfill \end{array}$

(13)

Let ${\mathscr{H}}_k(\mu )=ϵ+(1-2ϵ){\bar{F}}_n({\tau }_k-\mu )$ , then the log-likelihood function is given by

$\begin{array}{cc}\hfill & \ln f\left(\mathbf{r}\hspace{0.17em}|\hspace{0.17em}\mu \right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}={\displaystyle \sum }_{k=1}^N\left[{\mathbb{1}}_{\left\{r_k=1\right\}}\ln \left({\mathcal{H}}_k\left(\mu \right)\right)+{\mathbb{1}}_{\left\{r_k=-1\right\}}\ln \left(1-{\mathcal{H}}_k\left(\mu \right)\right)\right].\hfill \end{array}$

(14)

Thus, the MLE $\widehat{\mu }$ is obtained by solving the following constrained maximization problem,

$\begin{array}{cc}\hfill & \underset{\mu }{\text{argmax}}\hspace{1em}{\displaystyle \sum }_{k=1}^N\left[{\mathbb{1}}_{\left\{r_k=1\right\}}\ln \left({\mathcal{H}}_k\left(\mu \right)\right)+1_{\left\{r_k=1\right\}}\ln \left(\mathbb{1}-{\mathcal{H}}_k\left(\mu \right)\right)\right],\hfill \\ \hfill & \text{s}.\text{t}.\hspace{1em}{\mu }_l\le \mu \le {\mu }_u,\hfill \end{array}$

(15)

and because the function relating μ to R in (1) is one to one, the MLE $\widehat{R}$ can be obtained directly from $\widehat{\mu }$ . Note that we have assumed that the CH has perfect knowledge of the dB spread of the log-normal shadowing, that is, ${\sigma }_n^2$ and the cross-over probability ϵ. The former can usually be obtained offline by conducting field measurements in the area of deployment and then performing regression analysis using the experimental data [30]. As for ϵ, this is typically known a priori depending on the modulation and coding scheme used. For example, for transmission of information over fading channels, the probability of bit error ( $p_e$ ) is well known when standard digital modulation (BSPK, QPSF, 64-QAM, etc.) schemes are used with error control coding strategies such as Turbo or LDPC codes. Hence, $p_e$ can be used as the value for ϵ.

5. Performance Analysis of Dithered Quantization Approach

This section contains (i) proofs of the asymptotic consistency and efficiency of the MLE for μ and R using the proposed dithered quantization approach (ii) derivation of the Cramér-Rao bound (CRB) for the variance of any unbiased estimator for μ and R, and (iii) Monte Carlo simulations that validate the asymptotic results and compare the performance of the dithered quantization technique with the identical threshold-based quantization approach. Since the constrained ML optimization in (15) is analytically intractable, there is no closed-form expression for the estimates or the distribution of the estimates. Hence, to study the bias of the MLE's, we prove that the estimators are asymptotically strongly consistent and hence asymptotically unbiased. Furthermore, although the $ℛ(k)$ 's are i.n.i.d Bernoulli r.v's, we prove that MLE's are asymptotically normally distributed and efficient. Monte Carlo simulations confirm these results and, as shown later, demonstrate that these desirable asymptotic behavior is effectively achieved with as few as $70~100$ sensors.

5.1. Asymptotic Properties

For the following results, we define ${\widehat{\mu }}_N$ , ${\widehat{R}}_N$ to be the MLE of μ and R, respectively, obtained with N sensors using the dithered quantization technique.

Proposition 1.

The MLE ${\widehat{\mu }}_N$ is unique and asymptotically strongly consistent $\text{Pr}({\lim \hspace{0.17em}}_{N\to \infty }{\widehat{\mu }}_N={\mu }_0)=1$ , where ${\mu }_0$ represents the true value of μ.

Proof.

See Appendix A.

Proposition 2.

${\widehat{\mu }}_N$ is asymptotically efficient $({\widehat{\mu }}_N-{\mu }_0)\underset{𝒟}{\to }𝒩(0,1/(ℐ({\mu }_0)))$ , where ${\mu }_0$ represents the true value of μ, $ℐ(·)$ is the Fisher information (FI), and $\underset{𝒟}{\to }$ means convergence in distribution.

Proof.

See Appendix B.

The following two corollaries are immediate consequences of the invariance property of functions of MLE's and the one-to-one mapping between μ and R.

Corollary 1.

The MLE ${\widehat{R}}_N$ is unique and asymptotically strongly consistent $\text{Pr}({\lim \hspace{0.17em}}_{N\to \infty }{\widehat{R}}_N=R_0)=1$ , where $R_0$ represents the true value of R.

Corollary 2.

${\widehat{R}}_N$ is asymptotically efficient $({\widehat{R}}_N-R_0)\underset{𝒟}{\to }𝒩(0,1/(ℐ(R_0)))$ , where $R_0$ represents the true value of R.

5.2. Cramér-Rao Bound

In this subsection, we derive the CRB for any unbiased estimator of μ denoted by $\bar{\mu }$ . The MLE $\widehat{\mu }$ derived previously may be biased for small N, but since we have proved that it is asymptotically unbiased, the CRB is useful as a lower bound of the variance of $\widehat{\mu }$ for medium-to-large numbers of sensor motes.

Theorem 1.

The CRB for any unbiased estimator $\bar{\mu }$ obtained using the dithered quantization technique with the BSC model is

$\mathrm{Var}\left(\bar{\mu }\right)\ge {\left[{\displaystyle \sum }_{k=1}^N\left\{\frac{{\left(\left(1-2ϵ\right)f_n\left({\tau }_k-\mu \right)\right)}^2}{\left(ϵ+\left(1-2ϵ\right){\bar{F}}_n\left({\tau }_k-\mu \right)\right)\left(1-ϵ-\left(1-2ϵ\right){\bar{F}}_n\left({\tau }_k-\mu \right)\right)}\right\}\right]}^{-1}.$

(16)

Proof.

See Appendix C.

Using the CRB for $\bar{\mu }$ and observing that (1) is a one-to-one transformation, the CRB for any unbiased estimator of R, denoted by $\bar{R}$ , can be derived using the invariance property of MLE's and functions of MLE's. The following lemma relates the variance of $\bar{\mu }$ to the variance of $\bar{R}$ .

Lemma 1.

If $R=g(\mu )$ , then the variance of any unbiased estimate of R is given by

$\mathrm{Var}\left(\bar{R}\right)\ge \frac{{\left(\partial g/\partial \mu \right)}^2}{\mathcal{I}\left({\mu }_0\right)}.$

(17)

Proof.

A proof of this lemma can be found in [29, Chapter 3, Appendix $3\text{A}$ ].

Corollary 3.

The CRB for any unbiased estimator for $\bar{R}$ using the dithered quantization technique with the BSC model is

$\mathrm{Var}\left(\bar{R}\right)\ge \frac{{\left(\left(\ln 10\right)10^{\left(K-\mu \right)/10\alpha }/10\alpha \right)}^2}{\mathcal{I}\left(\mu \right)},$

(18)

where

$\begin{array}{cc}\hfill & \mathcal{I}\left(\mu \right)\hfill \\ \hfill & ={\displaystyle \sum }_{k=1}^N\left\{\frac{{\left(\left(1-2ϵ\right)f_n\left({\tau }_k-\mu \right)\right)}_k^2}{\left(ϵ+\left(1-2ϵ\right){\bar{F}}_n\left({\tau }_k-\mu \right)\right)\left(1-ϵ-\left(1-2ϵ\right){\bar{F}}_n\left({\tau }_k-\mu \right)\right)}\right\}\hfill \end{array}$

(19)

is the FI.

Proof.

Using Lemma 1 and the relationship between R and μ given by $R=10^{(K-\mu )/10\alpha }$ , the result follows.

Figures 4(a) and 4(b) show the behavior of the square root of the CRB of $\widehat{R}$ when we vary the number of sensors, N, and the crossover probability, ϵ, respectively. The CRB is a monotonically increasing function of ϵ for $0\le ϵ<0.5$ and, due to its symmetry about $ϵ=0.5$ , is a monotonically decreasing function for $0.5<ϵ\le 1$ . As $ϵ\to 0.5$ the CRB tends to ∞ because, from (1), the Fisher information converges to 0. From Figure 4(a), we observe that the CRB is a monotonically decreasing function of N, which is expected because more sensors means more observations, thus, lower CRB values. Although MLE's tend to have a significant bias for small sample sizes, we have proved that the MLE for our scheme is asymptotically strongly consistent and efficient. Therefore, the analytic derivations above for the CRB for $\bar{\mu }$ and $\bar{R}$ hold in the asymptotic region. The simulation results in the following subsection show that the asymptotic behavior is achieved even with a small number of sensors.

Figure 4

${(\text{CRB})}^{1/2}$ of $\bar{R}$ with $R_0=50$  m, $K=-10$  dB, $\alpha =2.5$ , and ${\sigma }_n=4$  dB.(a) shows that the analytic expression for the square root of the CRB function is monotonically decreasing function with respect to the number of sensor motes. (b) shows that the analytic expression for the square root of the CRB function is monotonically increasing for the range $0\le ϵ<0.5$ and as ϵ approaches 0.5 the function approaches ∞ as the Fisher information converges to 0.

5.3. Numerical Simulation Results

To evaluate the performance of the dithered quantization scheme and compare it with the identical and the binning-based non-identical threshold approaches, we now conduct numerical Monte Carlo simulations. In these simulations (i) the number of sensors is varied from 10 to 200 and (ii) both a low ϵ of 0.05 and a high ϵ of 0.1 are considered. The value of $R_0$ is set to 50 m, which corresponds to ${\mu }_0\approx -52.5$  dB and K is set to −10 dB, the maximum transmission power allowed for 802.11b. We use the typical value of 2.5 for the path-loss exponent α. The standard deviation of the RSS distribution observed at the sensor motes is set to 4 dB; that is, ${\sigma }_n=4$  dB.

The results obtained were averaged over 2000 realizations of the measurement noise process. It can easily be shown (see Appendix D) that the log-likelihood function is not a concave function of μ for both non-identical threshold-based approaches. Hence, we implemented an 1-dimensional iterated grid search algorithm [31] to locate an approximate maximal value of the log-likelihood function denoted by ℒ. We employed an equidistance grid of size n points given as:

$\mathcal{S}=\left\{x_k\hspace{0.17em}|\hspace{0.17em}{x}_k={\mu }_l+\frac{k\left({\mu }_u-{\mu }_l\right)}{n-1},\hspace{1em}k=0\cdots n-1\right\}.$

(20)

Using the grid 𝒮, the values $ℒ(x_1),ℒ(x_2)\cdots ℒ(x_n)$ are used in the grid search algorithm. An approximate local maximum is located by choosing the grid point $x_k$ that has the largest value for $ℒ(x_k)$ . Using this initialization point, we then used Matlab's sequential quadratic programming (SQP) method to perform the local optimization to determine the MLE.

To characterize the computational complexity of the optimization algorithm, we note that the local optimization using SQP has quadratic convergence rate. The computational complexity of the iterative grid search algorithm can be expressed as $𝒞(n,r)=r{n}^m$ , where m is the dimension of the parameter space, n is the grid size, and r is the number of iterations. In our simulation experiments, we found that with $r=10$ and a grid size of $n=100$ the algorithm converged to an approximate local maximal point quickly. Hence, the computational complexity of the grid search for our case is $O(n)$ . In our Matlab implementation of the grid search algorithm, we were able to reduce the complexity to $O(n\hspace{0.17em}\log \hspace{0.17em}\hspace{0.17em}n)$ , by the use of sorting algorithms to find the grid point $x_k$ that would correspond to the largest value of the log-likelihood function $ℒ(x_k)$ . In a practical setting, the search grid will be precomputed, and the algorithm will be executed on the CH. Since the CH typically has more processing power than other motes, in a practical setting the convergence of the algorithm would be very fast.

The non-identical thresholds for the dithered quantization technique are generated using the technique described in Section 3, and, for the binning-based technique the SOCP 7 is solved in Matlab using cvx software [32]. As mentioned in [10], the threshold spacing for the binning technique is set to $2{\sigma }_n$ , and hence we have ${\tau }_{k+1}-{\tau }_k=8$  dB, therefore the number of threshold bins $B=({\mu }_u-{\mu }_l)/8=8$ . For the case where an identical threshold is used by all sensor motes, we consider two scenarios. In the first case, the optimal threshold is used; that is, $\tau ={\mu }_0$ , which corresponds to $\tau \approx -52.5$  dB. In the second case, an identical nonoptimal threshold is used, this corresponds to choosing τ above/below the true mean value of the RSS distribution; that is, $\tau =({\mu }_0+\mathrm{\Delta })$  dB. For simulation purposes, we set $\mathrm{\Delta }=8$ ; this corresponds to $\tau \approx -44.5$  dB. Similar simulation results are obtained for the case when $\tau >{\tau }^{\text{opt}}$ .

In Figures 5(a) and 5(b), we plot the root mean squared error (RMSE) of $\widehat{R}$ for the low and high ϵ cases. We observe that the RMSE using the dithered quantization approach is lower for a small number of sensor motes compared to the non-optimal identical threshold approach and the binning-based non-identical approaches. As the number of sensor motes is increased the RMSE of the binning-based non-identical technique converges to the dithered quantization technique. This is expected since for the binning based approach as the number of sensor motes is increased the threshold frequency ( ${\rho }_k$ ) increases which leads to the improvements in the performance.

Figure 5

RMSE of $\widehat{R}$ with $R_0=50$  m, $K=-10\hspace{0.17em}\text{dB}$ , and $\alpha =2.5$ , ${\sigma }_n=4$  dB. In (a) $ϵ=0.05$ and in (b) $ϵ=0.1$ . In both cases the dithered quantization technique has a lower RMSE compared to the non-optimal and binning-based thresholding techniques particularly for a low number of sensor motes.

Figures 6(a) and 6(b) show the bias of $\widehat{R}$ versus the number of sensor motes. We notice that the bias of the MLE using the dithered quantization technique is lower than the non-optimal estimators. Furthermore, we also observe that the bias decreases at an exponential rate with respect to the number of sensor motes and approaches close to 0 with about 100 sensor motes. Figures 5 and 6 also show that the asymptotic properties of the MLE are achievable with about 50 sensor motes for low values of ϵ and about 70 sensor motes for high values of ϵ.

Figure 6

Bias of $\widehat{R}$ with $R_0=50$  m, $K=-10\hspace{0.17em}\text{dB}$ , and $\alpha =2.5$ , ${\sigma }_n=4$  dB. In (a) $ϵ=0.05$ and in (b) $ϵ=0.1$ . In both cases the dithered quantization technique has a lower bias compared to the non-optimal and binning-based thresholding techniques especially for a low number of sensor motes.

In Figures 7(a) and 7(b), we compare the performance loss incurred using the different thresholding techniques. We define the ${\text{CRB}}_{\text{Loss}}={\text{CRB}}_{\text{non-opt}}-{\text{CRB}}_{\text{opt}}$ , where CRB_non-opt is the CRB of any unbiased estimator using either the dithered quantization, binning-based or identical non-optimal thresholding techniques, and CRB_opt is the CRB of any unbiased estimator using the optimal identical threshold. This metric serves as a good benchmark as, for large number of sensor motes, the MLE's are unbiased, and hence the MSE is equal to the CRB. Figures 7(a) and 7(b) show the CRB_Loss versus the number of sensors. We observe that for low and high ϵ values the loss is significantly less for the dithered quantization technique compared with the other schemes, particularly for a small number of sensor motes which is important from a practical point of view.

Figure 7

${(\text{CRB})}^{1/2}$ with $R_0=50$  m, $K=-10$  dB, $\alpha =2.5$ , and ${\sigma }_n=4$  dB. In (a) $ϵ=0.05$ and in (b) $ϵ=0.1$ , in both cases the loss incurred using the dithered quantization technique is significantly less compared to the other techniques, particularly for low number of sensor motes.

Figure 8 shows the robustness of our scheme due to a mismatch in the true value of ϵ and the value of ϵ used by the CH for the ML estimation. We notice that even if there is a mismatch, the performance degradation is not significant. The performance of having a perfectly estimated value of ϵ can be replicated using more sensor motes under the condition of a mismatch in ϵ. Furthermore, the gap between the performance between the perfectly estimated ϵ and the mismatched ϵ decreases as the number of sensor motes increases.

Figure 8

shows the RMSE of $\widehat{R}$ using dithered quantization technique with $R_0=50$  m, $K=-10\hspace{0.17em}\text{dB}$ , $\alpha =2.5$ , and ${\sigma }_n=4$  dB for various values of ϵ. The plot shows the robustness of our estimation scheme due to a mismatch in the true value of ϵ and the estimated value of ϵ used by the CH.

In a realistic situation in which the mean of the RSS distribution at the sensor nodes is unknown priori, there is no way to choose the optimal τ for the identical threshold case. It will thus be difficult to achieve good/reliable estimates using non-optimal identical thresholds. In this type of practical scenario, if both approaches (non-optimal identical and non-identical thresholds) use the same number of sensors, and each sensor samples the RSS once, then using the non-identical threshold approach would produce a much more accurate estimate.

Although both non-identical thresholding approaches require fewer sensors than the non-optimal identical threshold technique to achieve near-optimal performance, we observe that compared to the binning approach our thresholding scheme is of low complexity, as it does not involve solving any complex optimization problem to design the thresholds. Furthermore, the dithered quantization technique performs better in terms of having a lower RMSE, variance, and bias compared with the binning and non-optimal identical thresholding techniques, particularly when the number of sensors is small, which is the typical case in a practical scenario.

In summary, the dithered quantization technique has significant advantages over other techniques in terms of either the number of sensors required to achieve a given accuracy or the accuracy of estimates achievable with a fixed number of sensors.

6. Drawbacks of the Identical Threshold Approach

In this section, we study the disadvantages of using the identical threshold approach and the effect on $\widehat{R}$ using this technique. As observed in previous work [10, 11], with the error-free communication channel, the disadvantage of the identical threshold approach is that the CRB for $\widehat{\mu }$ grows exponentially with $[(\tau -{\mu }_0{)}^2/{\sigma }_n{]}^2$ . A similar observation can be seen for the CRB of $\bar{R}$ when the identical threshold is used under a BSC model. Using the tight Chernoff bound for the ccdf of the Gaussian distribution (i.e., ${\bar{F}}_n(\tau -\mu )\le e^{-(\tau -\mu {)}^2/2}/2$ ), the CRB for $\bar{R}$ can be bounded as follows:

$\begin{array}{cc}\hfill & \text{CRB}(ϵ,\tau ,R_0)\hfill \\ \hfill & \hspace{1em}=G\frac{\left[ϵ+\left(1-2ϵ\right){\bar{F}}_n\left(\tau -{\mu }_0\right)\right]\left[\left(1-ϵ\right)-\left(1-2ϵ\right){\bar{F}}_n\left(\tau -{\mu }_0\right)\right]}{{N\left[\left(1-2ϵ\right)f_n\left(\tau -{\mu }_0\right)\right]}^2}\hfill \\ \hfill & \hspace{1em}\le G\frac{\pi {\sigma }_n^2{e}^{{\left(\tau -{\mu }_0\right)}^2/2{\sigma }_n^2}}{2N{\left(1-2ϵ\right)}^2}\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\times [\left(2ϵ+\left(1-2ϵ\right)e^{-(\tau -{\mu }_0{)}^2/2{\sigma }_n^2}\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times \left(2\left(1-ϵ\right)-\left(1-2ϵ\right)e^{-(\tau -{\mu }_0{)}^2/2{\sigma }_n^2}\right)],\hfill \end{array}$

(21)

where $G=((\ln \hspace{0.17em}10)10^{(K-{\mu }_0)/10\alpha }/10\alpha {)}^2$ . Figure 9(a) shows the exponential increase with respect to $(\tau -{\mu }_0)/{\sigma }_n$ for $ϵ=0.01$ and $ϵ=0.1$ for the CRB of $\widehat{R}$ . We notice that the Chernoff bound is tight and that a small deviation of τ from the true unknown value ${\mu }_0$ will result in a significant loss in performance. Although a similar result has previously been widely reported for the error-free channel case [10, 11], to the best of our knowledge, no one has studied the performance of the MLE's in terms of the MSE and variance effects using the identical threshold approach. Hence, to further analyze the effects of using this technique, Figure 9(b) shows the MSE and variance plot as $(\tau -{\mu }_0)/{\sigma }_n$ is varied. As with the CRB plot, the performance degradation in terms of the MSE is also exponential as τ deviates from ${\mu }_0$ . However, we notice the existence of multiple critical points. This effect is because the MSE can be decomposed into the ${(\text{bias})}^2$ and variance. The figure shows that for small deviations from ${\mu }_0$ the ${(\text{bias})}^2$ is nearly zero, and the variance increases exponentially; however, when $\tau \gg {\mu }_0$ , the variance starts to decrease, but the bias increases linearly with $(\tau -{\mu }_0)$ . These combined effects reiterate the fact that using identical thresholds could potentially result in estimators with very high bias and MSE.

Figure 9

In (a) the CRB and the Chernoff bound for $\widehat{R}$ is shown for varyious values of τ at $R_0$ = 50 m ( ${\mu }_0\approx -52.5$  dB), $N=100$ and ${\sigma }_n=4$  dB. Observe that the performance degradation is exponential as $(\tau -{\mu }_0)/{\sigma }_n$ increases for different crossover probabilities. (b) shows the MSE, variance and ${(\text{bias})}^2$ for $\widehat{R}$ with varying τ with $R_0=50$  m ( ${\mu }_0\approx -52.5$  dB) $N=100$ and ${\sigma }_n=4$  dB. The MSE also has an exponential growth with respect to $(\tau -{\mu }_0)/{\sigma }_n$ ; however, we notice the peculiar behavior of multiple critical points due to the bias and variance effect of the MLE of R.

7. Conclusion

In this paper, we proposed and analyzed a sensor fusion algorithm for interference characterization in wireless networks. To minimize energy usage, each wireless sensor in the network transmits only 1-bit of quantized, noisy RSS information to the FC over a BSC.

Unlike previous approaches that used identical thresholds for all sensors or use non-identical thresholds based on solving a complex optimization problem, we propose a simple and low complexity threshold design technique of uniformly distributing the thresholds over the range of possible values of the mean of the RSS distribution. This approach performs (i) as well as the optimal identical threshold approach and (ii) significantly better than the identical non-optimal threshold design approaches and has a performance that is more accurate or as good as previously proposed non-identical threshold techniques. The optimal identical threshold case is highly unrealistic because the optimal threshold cannot be known in advance; our non-identical threshold technique is much more practical, reliable, and of low complexity design compared to previously proposed techniques based on either using non-identical or identical non-optimal thresholds.