Online rate adjustment for adaptive random access compressed sensing of time-varying fields
Naveen Kumar1,
Fatemeh Fazel2,
Milica Stojanovic2 &
Shrikanth S. Naryanan1
We develop an adaptive sensing framework for tracking time-varying fields using a wireless sensor network. The sensing rate is iteratively adjusted in an online fashion using a scheme that relies on an integrated sensing and communication architecture. As a result, this scheme allows for an implementation that is both energy efficient and robust. The objective is to promote an "active" framework which uses the information extracted from the network data and iteratively adjusts the monitoring process to capture the temporal variations in the monitored field. We propose two metrics based on target detection/tracking for this feedback scheme that seek to trade off between energy efficiency and accuracy of the detection/tracking tasks. Our simulation results suggest that tying target detection with the rate adjustment algorithm ensures that the robustness to changes in the field can be achieved simultaneously with the end goal of accurate target detection. Compared to a baseline method that uses the correlation of the acquired field over time, our method exhibits better performance when the targets of interest have a smaller spatial spread.
The emergence of compressed sensing framework presents significant potential for efficient sensing and sampling systems [1–3] by helping to reduce sample complexity under realistic communication constraints. Sensor network technology greatly benefits from the compressed sensing paradigm [4–12]. Consider for example, large-scale networks that are deployed for long-term monitoring of dynamic fields such as the ocean bed that typically need to account for power consumption considerations. An efficient scheme in such cases requires performance optimization that jointly considers both the sensing and communication constraints.
To address this issue, Fazel et al. proposed a random access compressed sensing (RACS) scheme in [13, 14] for energy-efficient reconstruction of sensing fields. The proposed sensing scheme depends on integrating information from the communication and channel access modules into the data acquisition process. The method is simple to implement under realistic communication constraints and requires minimal assumptions on the field. However, the proposed RACS scheme is designed for stationary1 sensing fields, where the field being monitored is assumed to remain static during sensing. In order to monitor time-varying fields, in [15], the authors employed low-rank matrix recovery to reconstruct the space-time map of the field. However, this approach is offline and entails considerable delays since full recovery can be attained only after the data have been collected over multiple time segments. Moreover, it is assumed that the coherence properties of the underlying field are known a priori and remain unchanged throughout the full sensing duration. This assumption might be justified for the monitoring of natural phenomena, where the field is assumed to be either stationary or changing at a fixed rate. It is also common to find similar assumptions of stationarity in related works in object detection or classification in underwater fields [16, 17]. However, when the field being monitored undergoes a varying rate of change (e.g., when the process is impacted by a target that is moving at an unknown or variable speed), such assumptions may not hold.
In a more recent work, Kerse et al. [18] addressed this problem by proposing to unify target detection with reconstruction using a standard sparse identification technique. Targets are tracked from frame to frame and the authors further suggest that the tracking error could be used as a measure to adjust the sensing rate in turn. While their method does not require any a prioi knowledge of the number of targets or coherence properties of the underlying field, it relies on knowledge of the exact target signatures for both target localization and tracking. In this paper, we propose a rate adjustment method that does not require explicit knowledge of the target signature. Rather, knowledge of the family of models to which the field might belong is adequate as the field model parameters can be jointly estimated.
Similar to the work in [18], we consider that the end goal in sensing is to detect or track targets and incorporate these data processing aspects into the joint sensing and communication scheme. We propose a framework to adjust the sensing rate by estimating different attributes of the field to make an informed decision. Our adaptive rate adjustment procedure for compressed sensing iteratively adjusts the per-node sensing rate to capture the variations in the underlying field. First, we treat the field as piecewise stationary and apply random access compressed sensing within each sensing period. Second, we compute two heuristic metrics that seek to tie in the end goal of target detection/tracking with the rate adjustment scheme. Using the data collected in each segment, the fusion center (FC) relies on a detection algorithm to first determine the current state it is in. Finally, depending on the current state, a control algorithm instructs the FC to change the sensing rate if required.
A high rate of sensing would typically bode well for target detection/tracking, but it is not energy efficient. On the other hand, a low rate of sensing may not necessarily lead to poor performance in detection. Thus, there is a possible trade-off between energy efficiency and the target detection accuracy which the rate adjustment seeks to exploit. We perform simulation experiments using the proposed method and present results that suggest that the proposed sensing rate adjustment method exhibits better performance compared to the baseline method when compared on the following evaluation criteria: (a) mean-squared error of tracking the underlying coherence time and (b) F-score of the target detection accuracy.
The paper is organized as follows. In Section 2, we explain the basic sensing model for the stationary case, and in Section 3, we relax the stationarity assumptions. In Section 4, we describe the sample field model for simulation. In Sections 5 and 6, we describe an adaptive strategy for sensing the time-varying field. Finally, in Sections 7 and 8, we provide results for the simulation.
Random sensing network over stationary fields
Consider a grid network consisting of N=P×Q sensors, with P and Q sensors in the x and y directions, respectively. The underlying assumption is that most signals of interest (natural or man-made) vary smoothly spatially and hence are compressible in the spatial discrete Fourier transform (DFT) basis. We denote the sparsity of the signal by S. The data from the distributed sensors is conveyed to the FC, where a full map of the sensing field is reconstructed. This map can be used for target detection as will be shown in Section 5.
Inspired by the theory of compressed sensing, the architecture proposed in [13, 14] employs random sensing, i.e., transmission of sensor data from only a random subset of all the nodes. For a stationary field, each sensor node measures the signal of interest at random time instants—independently of the other nodes—at a rate of λ 1 measurements per second. It then encodes each measurement along with the node's location tag into a packet, which is digitally modulated and transmitted to the FC in a random access fashion. Owing to the random nature of channel access, packets from different nodes may collide, creating interference at the FC, or they may be distorted as a result of the communication noise. A packet is declared erroneous if it does not pass the cyclic redundancy check or a similar verification procedure. Since the recovery is achieved using a randomly selected subset of all the nodes' measurements, we let the FC discard the erroneous packets as long as there are sufficiently many packets remaining to allow for the reconstruction of the field.
The FC thus collects the useful packets over a collection interval of duration T. The interval T is assumed to be much shorter than the coherence time of the process, such that the process can be approximated as fixed during one such interval. Let R xx (τ) denote the temporal autocorrelation of the process, which quantifies the average correlation between two samples of the process separated by time τ. The coherence time T coh is then defined as the time lag during which the samples of the signal are sufficiently correlated, i.e., R xx (T coh)=q R xx (0), where q is the desired level of the correlation (e.g., q=98 %). We borrow the above random sensing strategy from Fazel et al. [13, 14]. In this strategy, in addition to the compressibility assumption mentioned earlier, we can reconstruct back the field using Eq. (1)
$$ \mathbf{y}=\mathbf{R}\boldsymbol{\Psi}\mathbf{v}+\mathbf{z} $$
where z represents the sensing noise, Ψ is the inverse DFT matrix, v is the sparse vector of Fourier coefficients, and R is a K×N matrix—with K corresponding to the number of useful packets collected during T—which models the selection of correct packets. Each row consists of a single one in the position corresponding to the sensor contributing the useful packet. The FC can form R from the correctly received packets, since they carry the location tag. We emphasize the distinction between the sensing noise z, which arises due to the limitations in the sensing devices, and the communication noise, which is a characteristic of the transmission system. The sensing noise appears as an additive term in Eq. 1, whereas the communication noise results in packet errors and its effect is captured in the matrix R.
The FC then recovers the map of the field using sparse approximation algorithms [19]. It suffices to ensure that the FC collects a minimum number of packets, \(N_{s}=\mathcal {O} (S\log N)\), picked uniformly at random, from different sensors, to guarantee accurate reconstruction of the field with very high probability. The random nature of the system architecture necessitates a probabilistic approach to system design using the notion of sufficient sensing probability [13] denoted by P s . This is the probability with which full-field reconstruction is guaranteed at the FC. Setting this probability to a desired target value, system optimization under a minimum energy criterion yields the necessary design parameter, i.e., the per-node sensing rate λ 1. The minimum per-node sensing rate can be expressed in terms of the system parameters as shown in [14]
$$ \lambda_{1s}=\frac{-1}{2NT_{p}\frac{b}{b+1}}\cdot W_{0}\left(\frac{2NT_{p}\frac{b}{b+1} e^{\frac{b}{\gamma_{0}}}}{T}\log\left(1-\frac{\alpha_{s}}{N}\right)\right) $$
where T p is the packet duration, b is the packet detection threshold, α s is the average number of packets that need to be collected in one observation interval T to meet the sufficient sensing probability, γ 0 is the nominal received signal-to-noise ratio (SNR), and W 0(·) is the principal branch of the Lambert W function. (More details can be found in [14]). Note that as shown in Fig. 1, λ 1s depends on the collection interval T, which in turn must be lower than T coh, for the stationarity assumption to hold.
Per-node sensing rate λ 1s vs. the collection interval T, for N=1000 nodes, S=10, T p =0.2 sec, b=4, α s =244 packets, and γ 0=15 dB
Adaptive sensing
In the above framework, the minimum per-node sensing rate λ 1s can be determined based on the properties of the field and is then kept fixed throughout the entire sensing process. However, most fields of interest are seldom stationary, and the coherence properties of a non-stationary dynamic field usually vary significantly over time. This calls for the design of an adaptive random sensing network for the monitoring of temporally varying fields. The objective is to transition from passive monitoring where only the map of the sensing field is reconstructed to an active framework where the relevant information is extracted (e.g., target detection/tracking) and exploited to instruct the sensor nodes to adjust their sensing rates. In practice, we assume the coherence properties of a non-stationary field to be piecewise constant over time, such that given prior information about the field at a particular time instant it can be assumed to be stationary within a single coherence time interval. To this end, we employ a detection method, which uses the collected data to determine the attributes of the underlying field. The FC can then use this information to determine any appropriate modifications to the per-node sensing rate, i.e., increase, maintain, or decrease the sensing rate. This cycle of sensing-decision-adjustment is illustrated in Fig. 2.
The adaptive sensing scheme
For a given collection interval T, the corresponding per-node sensing rate can be determined using Eq. (2), as shown in Fig. 1. The proper choice of T however depends on the rate of variations in the field and is adaptively tuned. In particular, we use an approach based on target detection, where we assume that an object/target model of interest is known beforehand. This is a common assumption in most supervised pattern recognition tasks. Given a reconstructed map, the location of targets is first estimated. Using this knowledge, we then estimate the parameters of the object model from the map. These parameters describe the detection system's understanding of the field and can be used to generate the map of the field. Comparing this model-based map with the observed one reconstructed using sparse approximation algorithms provides us with a reliability metric for reconstruction. In other words, if there is a difference in what the algorithm expects to see and what it sees, it indicates an error in either the acquisition of the field or the algorithm's understanding of the map. In either case, the FC needs to adapt its sensing rate. We specifically discuss our methods in the context of the following two cases:
Oversensing
This situation corresponds to the case when there occurs redundant sensing because the per-node sensing rate is much larger than the rate of change of the field, i.e., T<<T coh. Although this case favors reconstruction using the RACS architecture, it leads to a wastage of communication resources. Thus, we seek to lower the sensing rate in this case to an optimal point such that the accuracy of our end goal is not affected. Figure 7 shows the result for of oversensing for the example discussed in Section 5. In this case, we devise a scheme to estimate the motion of targets using multiple frames. We use the term frame here and elsewhere in the paper to refer to the field reconstructed from samples acquired within a single sensing time duration.
Undersensing
In this scenario, the rate of sensing per node is insufficient and the field changes within one collection interval since T>T coh. Thus, the per-node sensing rate λ 1s needs to be increased. The targets are no longer steady within the duration of a collection interval T leading to blurring, which makes target detection challenging. The estimation task in this case is further complicated by the fact that the packets from different frames may have been collected during the interval T. This scenario leads to a violation of the stationarity assumptions made initially. The reconstructed map is thus blurred because of different packets originating from different frames (Fig. 3). In this case, we use a specific error metric based on model fitting to estimate the reliability of reconstruction and object detection.
a–d The effect of the field changing at rate faster than the sensing rate. a is the original undistorted map that was sensed at T coh while (c) shows the same field obtained through temporal blurring after an observation interval T=10×T coh. d is the field obtained as a result of sensing at a rate 10 times slower than the field's underlying rate of change. Notice how (d) is more similar to the blurred map (c) than (a). This distortion in the sensed field is an example of undersensing
Simulation of a sample dynamic field
In this paper, we demonstrate the adaptive monitoring procedure using a sample model for the field. We demonstrate our adaptive scheme to adjust the per node sensing rate in RACS using a simulated example field in this paper. Using a realistic example allows us to control the coherence parameter T coh and monitor the effect of changing the collection interval T in accordance with the adaptive algorithm.
We first describe the example field that serves as our test case. Suppose, a field with M targets is being observed. Each target in the field is assumed to generate a signature (e.g., heat, sound, etc) decaying exponentially with distance from its location. At time t, the process observed by sensor node i at coordinate (x i ,y i ) is given by Eq. (3)
$$ u_{i}(t)=\sum\limits_{m=1}^{M}A_{m}e^{-p\sqrt{(x_{i}-a_{m}(t))^{2}+(y_{i}-b_{m}(t))^{2}}} $$
where a m (t) and b m (t) are the coordinates of the mth target at time t, A m is its strength, and p is the decay rate of the sources. The process then evolves over time as the sources move along random trajectories. Similar models are commonly found in the energy-based localization literature for static sensor networks [20–22] when the targets being detected are not moving.
Initially, the FC has no knowledge of the location of targets or the rate of variation in the field, i.e., the speed at which the targets are moving. It thus instructs the data collection to begin with an initial sensing rate \(\lambda _{1s}^{\text {init}}\). The initial sensing rate is determined using historical data by setting the desired parameters in Eq. (2). Once the map of the field G sa is recovered using sparse approximation techniques, the FC may now use the rate adjustment algorithm described later to decide if the sensing duration T needs to be adjusted. The sensors employ the adjusted sensing rate in the ensuing sensing duration. In this paper, we discuss metrics for the proposed rate adjustment algorithm for this family of field models, although the framework itself is quite general.
For simulating a map of the field as defined above, we start with a set of randomly chosen parameters. In addition, each target is assigned a random velocity and direction of movement. To simulate the undersensing case, we consider that collection occurs over N b coherence time intervals (referred to as frames) where T≈N b T coh. The randomly sampled packets are then collected uniformly over the last N b frames (Fig. 3). This effectively leads to motion blurring of the targets as mentioned before. To simulate the oversensing case, the collection interval is reduced to T ′=T coh while each target's velocity is scaled by T/T coh to make them appear to be moving slower. To deal with the issue of a finite field size, targets moving out of the field are replaced by new targets starting from the same location assigned a new random velocity and direction.
Adaptive field monitoring scheme
In this section, we discuss specific algorithms and metrics extracted using the reconstructed map, which are used for the adaptive rate control of per-node sensing in RACS. Although the algorithms discussed below have been adapted to this particular family of models used in the simulation example, we have attempted to layout broad steps whenever possible and provide a general scheme to be used in such cases. These algorithm stages have been presented in the block diagram shown in Fig. 4.
Block diagram for the adaptive feedback mechanism. G denotes the true measurements on the time varying field
Target localization
Before taking any decisions about the current sensing state, we first detect and localize the targets in the image. Similar to [18], by involving target detection in the feedback process, we would like to ensure that the rate of sensing is optimized for the end goal of target detection.
Traditionally, most energy-based localization methods [20–22] assume that the number of targets is known in advance. In addition, they assume a field model for target signature decay allowing for parameter estimation by model fitting. More recently, Kerse et al. proposed a method for direct target localization based on a standard sparse identification technique [18]. The advantage in their method is that target localization can be performed in a single step without first having to reconstruct the field. The number of targets can also be jointly estimated in this process using a sparsity constraint. However, the method still depends on exact knowledge of the field model.
To overcome this drawback, we propose a target localization algorithm based on local gradient ascent. The proposed method only requires that the target signatures be monotonically decaying away from the target. This technique is adapted from the mode seeking mean shift algorithm [23] which is frequently used for unsupervised clustering of data. Consequently, it can be interpreted as searching local peaks in the data histogram. In the task at hand, we are instead interested in finding local peaks in field intensity. We also modify the algorithm slightly to adapt to the discrete search space for this problem. Specifically, we start from a random initial point X on the map. A mean-shift-based gradient ascent technique is then used to update the location of this point in each iteration till a peak is found. Given the current location X, we estimate an intensity weighted mean X c for locations around X in a window of size W as shown in Eq. (4). Note that the direction from X to X c gives the direction of gradient ascent, along which X should be updated in the next iteration.
However, in the current problem, we are working on a space of discrete sensor locations. To make the algorithm better suited to such a scenario, we quantize the gradient direction to eight angular bins. Depending on the direction of the gradient, X is then shifted to one of its eight connected points. This process is explained using a schematic in Fig. 5. The iterations are repeated until X converges to a local maximum or reaches a point that has already been visited. The entire procedure is repeated multiple times with new random initial points till the peaks have been discovered. In practice, it is not necessary to traverse all points in the field to discover all the peaks (Fig. 6), and we restrict the algorithm to a fixed number of iterations. The parameter W in this algorithm serves as a mask over which the gradient can be estimated more robustly. The target detection procedure is explained in Algorithm 1.
Modified discrete step update scheme using quantized directions. Asterisk (*) indicates points on the grid. I denotes the P×Q grid of intensity values, and K(.) denotes our particular choice of kernel function used for computing mean
Figure on the left shows a sample map with sequential update steps for each point converging at local peaks (marked by diamond symbols). The figure on the right shows the window of width W=3 during the current iteration and the general direction of the gradient from the center
$$\begin{array}{*{20}l} &X_{c}=\frac{\sum\limits_{s} I(s) K(s-X)s}{\sum\limits_{s} I(s) K(s-X)},s\in P\times Q~\text{grid}\\ &K(s-x) = \left\{ \begin{array}{ll} 1 & \text{if}~ ||s-x||_{c}\leq W\\ 0 & \text{if otherwise} \end{array} \right. \end{array} $$
Once the positions a m and b m for the targets have been identified using the target localization algorithm described above, we try to obtain a minimum mean square error (MMSE) estimate of the field parameters defined in Eq. (3) using a method of comparison by synthesis to match the acquired map G sa against a model. The parameters of model denoted by G model comprise the target locations (a m ,b m ), their respective strengths A m , and the decay parameters of the target signature (p).
We estimate the parameters using a nonlinear regression [24] technique to optimize an MMSE formulation as shown in Eq. (5). We use the nlinfit function in MATLAB for solving this optimization problem. Since the optimization is not convex, the choice of initial points is important. We use the target localizations estimated earlier and a reasonable value for the decay as our initial point. The estimated parameters are then used to generate a map of the field G det (Fig. 7 d). G det represents what the control algorithm expects the field to look like based on the target localizations and its knowledge of the model.
Steps in rate adjustment. b shows the samples chosen at random, and (d) is the map generated using the parameters estimated on (c). Notice how (d) is approximately similar to (a) when detection is accurate
$${} {\fontsize{8.6pt}{9.6pt}{\begin{aligned} \widehat{\textbf{a,b,A}},p=\mathop{\arg\min}_{a_{m},b_{m},A_{m},p}\sum\limits_{i=1}^{P} \sum\limits_{j=1}^{Q}\left(\sum\limits_{m=1}^{M} G^{\text{model}}_{ij}(a_{m},b_{m},A_{m},p) -G^{sa}_{ij}\right)^{2} \end{aligned}}} $$
$${} G^{\text{det}}=G^{\text{model}}(\widehat{\textbf{a,b,A},p}) $$
Reliability metric for reconstruction
We obtain a reliability metric for reconstruction based on the error in the model fitting described above. We compare the model-based map G det against the non-model-based map G sa recovered via sparse approximation by projecting both of them on the DFT matrix and decomposing the error into a high-frequency (HF) and low-frequency (LF) term. The intuition is that G sa should be similar to G det, but for any errors resulting from issues in either sensing or localization. A gross mismatch between the coefficients will be captured by the LF term indicating an inaccurate detection while a large value of the HF term (denoted by e r ) is a characteristic of a poor reconstruction due to violation of the assumptions in RACS (Fig. 8 a, b). The definition of this error term is shown in Eq. (7) where \(\mathcal {F_{H}}\) denotes a 2D high-pass filter, and e r is obtained by convolving it with the difference between the images G det and G sa. The cutoff frequency for the filters can be chosen from a previous estimate of the field. The error metric e r thus comes in handy in the undersensing case when the acquired map G sa is either blurred or poorly reconstructed.
$$ e_{r}=\mathcal{F}_{\mathcal{H}}\ast\left(G^{\text{det}}-G^{sa}\right) $$
a HF and b LF components of the model-based error and the minimum average motion per frame for (c) L=5 and (d) L=10 cases. The system is in open-loop control, i.e., the error metrics are not being compensated for which can be noted by the flat T line
Measuring motion by target tracking
In addition to compensating for the dynamic nature of the field in the undersensing case, we would also like to eliminate any redundant sensing. Recall, that in the oversensing case, the field changes very slowly, yielding perfect reconstruction and detection. This makes it necessary to monitor the field over multiple frames for detecting any signs of oversensing.
To quantify motion in the field, we track the location of detected targets over the last L frames. Note that this is not trivial since the number of targets detected is not guaranteed to be consistent from one frame to another. Moreover, the target indices assigned by the detection algorithm are non-unique. To deal with this issue, we use a tracking approach based on dynamic programming that ensures tracking even if the object is not detected in some of the intermediate frames. More specifically, we recursively minimize the total distance moved by a target over L frames. If the targets are spaced sufficiently apart, this ensures tracking of the slowest moving target over multiple frames.
Suppose \(\left (\hat {a}_{i}^{t},\hat {b}_{i}^{t}\right)\) denote the location of the ith target detected in frame t and let \(d^{t}_{ij}\) be defined as the distance between the ith target detected in the frame t and the jth target detected in the frame t+1. Then the net distance D(n 1,n 2,…,n L ) moved by a target over L frames and detected at the indices {n 1,n 2,…,n L } is given by Eq. (8).
$$\begin{array}{*{20}l} D(n_{1},n_{2},\ldots,n_{L})&=\sum\limits_{t=1}^{L-1} d^{t}_{n_{t} n_{t+1}};~~~~1\leq n_{t}\leq M_{t} \end{array} $$
$$\begin{array}{*{20}l} d^{t}_{ij}&=\sqrt{\left({a^{t}_{i}}-a^{t+1}_{j}\right)^{2}+\left({b^{t}_{i}}-b^{t+1}_{j}\right)^{2}} \end{array} $$
where M t is the total number of targets detected at each frame. The optimization problem then boils down to finding the sequence of object location indices {n 1,n 2,…,n L } that minimizes the sum of total point-to-point distances over L frames. To normalize over the length of the temporal window, we use the minimum average distance moved as a tracking-based metric as shown in Eq. (10). This metric (denoted by e m ) is expected to be low when the targets move slowly in the oversensing case while it is expected to be much higher when the objects get blurred in the undersensing case.
$$ e_{m}=\frac{1}{L}\min_{n_{1},\ldots,n_{L}} D(n_{1},\ldots,n_{L}) $$
((10))
Feedback algorithm for rate adjustment
After computing the error metrics e r and e m , a control algorithm is used to determine if the current sensing rate needs to be changed. This information is fed back to the FC which makes any necessary changes to the sensing rate, thereby establishing a closed-loop control. The objective of control is to minimize the reconstruction error-based metric e r at the same time ensuring that the targets move significantly from frame to frame as indicated by the tracking error metric e r . This ensures that the system is in a sweet spot between undersensing and oversensing.
In this paper, we propose a dual threshold feedback scheme to keep the system in this "optimal" state. We define two parameters: a lower threshold t h m for the metric e m and an upper threshold t h r for e r , respectively. In the proposed scheme, the value of these two parameters is tuned adaptively. The control algorithm itself consists of two modes: an "adjust" mode and a "calibrate" mode. The system's current mode is decided based on which of the four system states (A–D) it currently is in. These system states are shown in Fig. 9.
Four states of the control algorithm as determined by the error metrics e r and e m based on the thresholds t h r and t h m . The ideal operating zone is shown by the shaded region
In the adjust mode (states A and D in Table 1), the collection interval T is incremented or decremented by a scalar update (κ>1) depending on the value of the metrics. In state A, the condition e m ≤t h m indicates oversensing and hence the algorithm would decide to increase T, thereby decreasing sensing rate. In state D, the condition e r ≥t h r indicates that the system is undersensing which would result in the control decision to decrease T thereby increasing the sensing rate. The mutually opposing nature of these two conditions gives rise to a "stable" or buffer region for T (see Table 1) where it is not updated. In this mode, we only adapt the width of the buffer region by adjusting the threshold values such that for the current value of T, the control is just within the stable zone. Note, that it might not be feasible to guess a value for t h m or t h r making this adaptive approach necessary.
Table 1 Control feedback rules ("adjust" mode: A, D ; "calibrate" mode: B, C)
In practice, the thresholds can be initialized to extreme values such that the buffer region is wide enough and the system is guaranteed to start in state B. In subsequent intervals, the thresholds are updated in the "calibration" mode to shrink this buffer region. The ideal operating zone, centered at (t h r ,t h m ), is shown by a shaded region in Fig. 9. If the system steps out of this operating zone, the thresholds are adjusted in a direction such that the current system state is contained within the operating zone. In the calibration mode, the thresholds are adjusted by predefined steps α and β such that the system stays within the operating zone. In other words, the aim of this adaptive control is to obtain the tightest stable region of control for T.
To provide an intuition of how the scheme works, consider the graphical illustration of the proposed feedback algorithm in Fig. 9. At any time instant, the system state can be represented as a point on the e r e m plane. The relative position of this point with respect to the thresholds t h r and t h m is then used to decide the next course of action. In general, the algorithm tries to maintain a narrow buffer region of control by keeping the operating point (e r ,e m ) close to (t h r ,t h m ). This can be achieved by either updating the sensing time period T (states A and D) or by adapting the thresholds (states B and C).
By observing how the states of the algorithm transition, we present an argument to show that the proposed algorithm is bounded-input bounded-output (BIBO) stable. This means that for a finite coherence time T coh, the controlled variable viz. the sensing time period T is always bounded. This can be shown by considering each of the four states of operation A, B, C, and D of the proposed algorithm above.
Suppose, we are currently in state A (oversensing) and the feedback algorithm responds by increasing T. This leads to an increase in both e m and e r since fewer samples are sensed per unit time. This, in turn, prevents the system from staying in state A and is most likely to cause a transition to states B or C. Similarly, if the system is in state D (undersensing), the algorithm responds by decreasing T. This leads to the net effect that both e r and e m decrease, taking the system out of state D. When the system is in states B or C, the thresholds are varied so that operating point is maintained close to the adapted thresholds. This ensures that the sensing time period T and in turn the error metrics e r and e m cannot grow unbounded for a given finite T coh. As an example, note the state transitions in Fig. 10 which shows the internal states of the algorithm for a simulated control scenario.
Figure shows the internal states of the algorithm as it makes various rate adjustment decisions. States are the same as described in Table 1
System operation
We presented an example of the control system in an open-loop operation earlier in Fig. 8 which showed the value of metrics e r and e m for a particular T coh profile. Figure 8 c, d suggests that a larger L might be related to a slower response time of e m as can be seen around t=80, 100 when the field's T coh changes. The error metrics based on model fitting (Fig. 8 a, b) are computed from the current frame and thus respond instantaneously to the changes in field coherence. It is also worth noting here that the HF errors (spatial high-frequency component) typically correspond to the reconstruction error in the undersensing case, while the LF error serves as a sanity check for detection.
In this section, we present an example of closed-loop control by using the feedback mechanism (Table 1) discussed earlier to compensate for the error metrics as shown in Fig. 11. Note that the collection time interval T now attempts to trace the underlying hidden parameter T coh as the system tries to keep both e r and e m within bounds. Figure 10 provides a better insight into the system by showing the feedback algorithm's underlying internal state. Recall that states A and D correspond to oversensing and undersensing respectively while in states B and C, the thresholds are adapted to achieve a tight buffer region of stability.
Closed-loop control
We run simulations with M=4 targets and different velocity and decay parameters, using the proposed feedback algorithm for sensing rate adjustment. We evaluate the performance of the algorithm using two different criteria. First, the average mean squared error (MSE) between the estimated sampling duration T (blue line in Fig. 11) and the coherence time ground truth T coh (red line in Fig. 11) is computed as a measure of the algorithm's ability to track and adapt to changes in coherence time. Secondly, we calculate the F-score measure for target detection in each frame. This is a reasonable criterion for our task since the end goal of such an application would be target detection and tracking. To calculate the F-score of target detection in a frame, we check how many of the localized targets correspond to actual target locations. F-score weights both the precision and recall of target detection as follows
$$\begin{array}{*{20}l} \text{Precision}&=\frac{\# \ \text{targets that were correctly localized}}{\# \ \text{targets that were localized}}\\ \text{Recall}&=\frac{\# \ \text{targets that were correctly localized}}{\# \ \text{targets actually present}}\\ F&=\frac{2.\mathrm{Precision.Recall}}{\mathrm{Precision+Recall}} \end{array} $$
Baseline algorithm
We compare the results against a baseline method based on correlation of the currently acquired field G sa with the field acquired in the previous cycle as suggested in [15]. Control decisions are taken depending on two fixed high (δ h ) and low (δ l ) thresholds on the correlation value. T is incremented if correlation exceeds δ h and decremented if correlation falls below δ l . T is not updated if correlation lies between these two thresholds. The sampling duration T is changed using a scaling parameter κ as earlier.
Figure 12 shows the results of our simulation for the baseline and proposed methods. The results, averaged for each run, are shown for different parameter settings of velocity and decay p as defined in Eq. (3). Remember that a high F-score indicates accurate target detection while a low MSE denotes accurate tracking of the underlying coherence time (T coh).
The values for averaged MSE and F-score evaluation criteria for (a) correlation baseline mechanism and the (b) proposed feedback algorithm at different velocity and decay parameter settings
Figure 12 a shows the results for the baseline method using correlation as a feedback metric. From the MSE and F-score plots, it is evident that the baseline algorithm performance drops with increase in decay parameter p. This is expected since the targets with a lesser spread do not affect the correlation metric significantly. In contrast, for our proposed feedback algorithm, the performance improves with increase in the decay parameter p since targets with lesser spread are easier to localize and hence field reconstruction is more accurate (Fig. 12 b). A similar trend can be seen for average MSE which is related inversely to the target detection F-score. In other words, this might indicate that poor tracking of the underlying T coh is related to poor target detection, thereby making a case for the proposed sensing rate adjustment in this paper.
Since velocity for each target is assigned uniformly at random in the simulation, we control the velocity range that can be assigned to each target as a parameter instead. We note that increase in velocity has a positive influence on the performance of both the algorithms. This can be easily explained by considering that an increase in velocity of the targets makes it easier to discriminate between the oversensing, adequate sensing, and undersensing states. This holds for both the algorithms, and hence, we notice a general increase in F-score and decrease in MSE with increase in velocity. Finally, we also note that our proposed detection-based feedback mechanism outperforms the baseline correlation-based method in terms of the accuracy of target detection as indicated by the higher F-score. The average target detection F-score obtained for the baseline algorithm was 0.32 while our proposed method achieved an average F-score of 0.45.
Simulations with measurement noise
Next, we test the noise robustness of our proposed method by adding synthetic sensor or measurement noise to the field. We simulate measurement noise by adding zero mean white Gaussian noise at different amplitudes (σ noise) while keeping the original field's intensity the same. Results are averaged on full runs for different noise level, and the F-score for target detection accuracy is shown in Fig. 13. Other simulation factors such as velocity-scale and decay were held constant at 1 and 0.3 respectively for the purposes of this simulation.
Simulation results with additive white Gaussian noise at different levels for the proposed and baseline methods
The results show a clear degradation in F-score for both the proposed detection-based and baseline correlation-based methods, as the SNR decreases. However, we note that for the baseline algorithm, the F-score initially increases with decrease in SNR hinting at suboptimality in processing. On further investigation, we found this peculiar trait to be an artifact of the control algorithm and the choice of metric used in the baseline scheme. As noise is added to the field value of the correlation metric drops, which leads the FC to confuse the current state as undersensing. This inference leads to a monotonic decrease in sampling duration T, temporarily increasing performance at the cost of energy efficiency. The target detection F-score peaks around σ noise=0.05 beyond which the accuracy of target-detection algorithm is significantly affected. On the other hand, this artifact does not affect the proposed method significantly, since the metric used for our control algorithm is based directly on target detection. As a result, we note that our proposed method exhibits a more graceful degradation in performance with increase in noise without compromising on energy efficiency.
In this work, we present a rate adjustment scheme for random access compress sensing (RACS) to monitor and compensate for the rate of change in time-varying fields. Adjustment of sensing rate for RACS is motivated by the trade-off between energy efficiency and the accuracy of tracking targets of interest. Although direct estimation of the coherence time might seem to be the best approach for sensing a time varying field, we note that it is not directly related to our end goal of target detection in the field. We also observe that the reconstruction error in RACS has a complex relation to the current coherence time of the field and factors like the position of targets, their velocity, etc. Thus, by making the algorithm depend on the detection and localization of targets, we ensure that the rate adjustment is tied in to our actual objective.
In this paper, we propose two unsupervised metrics to inform the rate adjustment scheme. A model-based field reconstruction is done after target localization for each acquired frame, and the model fit error e r is used as a metric to detect cases when the FC is undersensing. To account for oversensing in operation, we define a measure for the motion of detected targets in the past L frames. This motion based metric e m indicates any redundancy in sensing and can be used to decrease the collection time interval T if needed.
We proposed a dual-threshold-based feedback mechanism using these error metrics for rate sensing adjustments. The technique assumes minimum prior knowledge and adapts the threshold in an online fashion using reasonable assumptions about the field. We also show that the proposed control mechanism is BIBO stable. In addition, we compare our results against a baseline algorithm that uses temporal correlation of the acquired fields and show that the proposed rate adjustment mechanism performs better on an average in terms of target detection accuracy even in the presence of noise.
1 We use the term stationary in this paper to refer to fields that are temporally static during the sensing duration.
EJ Candes, J Romberg, T Tao, Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math. 59:, 1207–1223 (2005).
EJ Candes, J Romberg, T Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory. 52:, 489–509 (2006).
E Candes, J Romberg, Sparsity and incoherence in compressive sampling. Inverse Problems. 23:, 969–985 (2006).
WU Bajwa, J Haupt, AM Sayeed, R Nowak, in 5th Int. Conf. Information Processing in Sensor Networks (IPSN'06). Compressive wireless sensing, (2006), pp. 134–142.
WU Bajwa, J Haupt, AM Sayeed, R Nowak, Joint source-channel communication for distributed estimation in sensor networks. IEEE Trans. Inform. Theory. 53(10), 3629–3653 (2007).
CT Chou, R Rana, W Hu, in IEEE 34th Conference on Local Computer Networks (LCN). Energy efficient information collection in wireless sensor networks using adaptive compressive sensing, (2009), pp. 443–450.
C Luo, F Wu, J Sun, CW Chen, in Proceedings of the 15th Annual International Conference on Mobile Computing and Networking. MobiCom. Compressive data gathering for large-scale wireless sensor networks, (2009), pp. 145–156.
J Meng, H Li, Z Han, in 43rd Annual Conference on Information Sciences and Systems (CISS). Sparse event detection in wireless sensor networks using compressive sensing, (2009), pp. 181–185.
R Masiero, G Quer, D Munaretto, M Rossi, J Widmer, M Zorzi, in Proceedings of the 28th IEEE Conference on Global Telecommunications. GLOBECOM'09. Data acquisition through joint compressive sensing and principal component analysis, (2009), pp. 1271–1276.
R Masiero, G Quer, M Rossi, M Zorzi, in ICUMT'09. A Bayesian analysis of compressive sensing data recovery in wireless sensor networks, (2009), pp. 1–6.
S Lee, S Pattem, M Sathiamoorthy, B Krishnamachari, A Ortega, in GeoSensor Networks. Lecture Notes in Computer Science, 5659. Spatially-localized compressed sensing and routing in multi-hop sensor networks (Springer, 2009), pp. 11–20.
D Motamedvaziri, V Saligrama, D Castanon, in Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference On. Decentralized compressive sensing, (2010), pp. 607–614.
F Fazel, M Fazel, M Stojanovic, Random access compressed sensing for energy-efficient underwater sensor networks. IEEE J. Selected Areas Commun. (JSAC). 29(8), 1660–1670 (2011).
F Fazel, M Fazel, M Stojanovic, Random access compressed sensing over fading and noisy communication channels. Wireless Commun. IEEE Trans. 12(5), 2114–2125 (2013).
F Fazel, M Fazel, M Stojanovic, in Information Theory and Applications Workshop (ITA), 2012. Random access sensor networks: field reconstruction from incomplete data (IEEE, 2012), pp. 300–305.
S Reed, Y Petillot, J Bell, An automatic approach to the detection and extraction of mine features in sidescan sonar. Oceanic Eng. IEEE J. 28(1), 90–105 (2003).
N Kumar, QF Tan, SS Narayanan, in Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference On. Object classification in sidescan sonar images with sparse representation techniques (IEEE, 2012), pp. 1333–1336.
K Kerse, F Fazel, M Stojanovic, in Signals, Systems and Computers, 2013 Asilomar Conference On. Target localization and tracking in a random access sensor network (IEEE, 2013), pp. 103–107.
JA Tropp, SJ Wright, Computational methods for sparse solution of linear inverse problems. Proc. IEEE, Special Issue, Appl. Sparse Representation and Compressive Sensing. 98(6), 948–958 (2010).
D Li, YH Hu, Energy-based collaborative source localization using acoustic microsensor array. EURASIP J. Appl. Signal Process. 2003:, 321–337 (2003).
Article MATH Google Scholar
X Sheng, Y-H Hu, Maximum likelihood multiple-source localization using acoustic energy measurements with wireless sensor networks. Signal Process. IEEE Trans. 53(1), 44–53 (2005).
W Meng, W Xiao, L Xie, An efficient em algorithm for energy-based multisource localization in wireless sensor networks. Instrum. Meas. IEEE Trans. 60(3), 1017–1027 (2011).
Y Cheng, Mean shift, mode seeking, and clustering. Pattern Anal. Mach. Intell. IEEE Trans. 17(8), 790–799 (1995).
PW Holland, RE Welsch, Robust regression using iteratively reweighted least-squares. Commun. Statistics-Theory Methods. 6(9), 813–827 (1977).
This work was supported by ONR and NSF.
Signal Analysis and Interpretation Laboratory (SAIL), Electrical Engineering, University of Southern California, Los Angeles, CA, USA
Naveen Kumar & Shrikanth S. Naryanan
Department of Electrical and Computer Engineering, Northeastern University, Boston, MA, USA
Fatemeh Fazel & Milica Stojanovic
Fatemeh Fazel
Milica Stojanovic
Shrikanth S. Naryanan
Correspondence to Naveen Kumar.
Kumar, N., Fazel, F., Stojanovic, M. et al. Online rate adjustment for adaptive random access compressed sensing of time-varying fields. EURASIP J. Adv. Signal Process. 2016, 48 (2016). https://doi.org/10.1186/s13634-016-0348-9
Accepted: 07 April 2016
Random access
Compressed sensing
Joint communication and detection
Distributed and Centralized Estimation in Wireless Sensor Networks