{'fraction_non_alphanumeric': 0.04594786940663642, 'fraction_numerical': 0.011764967529579218, 'mean_word_length': 4.142383348581885, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exploiting Sparse Dynamics For Bandwidth Reduction In Cooperative Sensing Systems

Recently, there has been a significant interest in developing cooperative sensing systems for certain types of wireless applications. In such systems, a group of sensing nodes periodically collect measurements about the signals being observed in the given geographical region and transmit these measurements to a central node, which in turn processes this information to recover the signals. For example, in cognitive radio networks, the signals of interest are those generated by the primary transmitters and the sensing nodes are the secondary users. In such networks, it is critically important to be able to reliably determine the presence or absence of primary transmitters in order to avoid causing interference. The standard approach to transmit these measurements from sensor the nodes to the fusion center has been to use orthogonal channels. Such an approach quickly places a burden on the control-channel-capacity of the network that would scale linearly in the number of cooperating sensing nodes. In this paper, we show that as long as one condition is satisfied: the dynamics of the observed signals are sparse, i.e., the observed signals do not change their values very rapidly in relation to the time-scale at which the measurements are collected, we can significantly reduce the control bandwidth of the system while achieving the full (linear) bandwidth performance.


I. INTRODUCTION
Cooperative sensing is a promising technique that has received a lot of attention recently due to necessity for reliable decision-making. Here, a group of wireless nodes collects measurements about the some signals of interest. The observations are then reported to a central node, which in turn applies some appropriately-chosen decision rule to recover the signals. Such an architecture finds application in two closely-related and well-studied settings.
The first setting is (de-)centralized detection in sensor networks -a group of sensor nodes commanded by a fusion center -where the observed signals could be temperature or humidity readings, military targets, etc. Much work (see [1]- [4] and references therein), both theoretical and practical, has studied and optimized various aspects of the cooperative sensing architecture, e.g., quantization functions at the sensing nodes, the combining process and decision metric at the fusion center, the communication scheme between the sensing nodes and the fusion center, etc. This is a rich area of research and hence, our references are far from a comprehensive list.
The second setting is a cognitive radio network where the observed signals are other unlicensed (secondary) or licensed (primary) transmitters. While the ideas in this paper are applicable to both the aforementioned settings, we review some literature from the latter as it is most relevant to the technical developments proposed here.

A. Spectrum sensing in cognitive radio networks
Cognitive radio technology, introduced by J. Mitola [5], is a promising solution to the growing scarcity of wireless spectrum, one that can potentially increase the spectrum utilization efficiency as recognized by the FCC [6], [7]. Traditionally, a portion of spectrum is allocated or licensed for use by a specific group of users by regulatory agencies. On the other hand, cognitive radio networks call for cognitive (unlicensed/secondary) users to operate on the same frequency band as the primary licensed users while attempting to access the spectrum seamlessly. In other words, the cognitive users need to adjust their operating parameters to guarantee minimal impact to the primary licensed users. For example, DARPA's Next Generation program [8] has been interested in developing spectrum sensing techniques that prevent interference to existing occupants of the frequency band. To increase spectral efficiency, the FCC recently opened up TV whitespaces (54 MHz -806 MHz) for unlicensed use [9]. While the ruling calls for access to a central database to determine TV band availability, the traditional use-case for spectrum sensing, we believe it still plays an important role in providing acceptable quality-of-service (QoS) over unlicensed bands. For example, a database provider could provide multiple classes of service to a querying secondary user where the higher class would be provided with a per-TV-band estimate of the interference statistics from other unlicensed users in the band. Spectrum sensing might be necessary in this context in order to collect such statistics.
Cooperative or collaborative sensing in the context of cognitive radio networks consists of a group of secondary users or specially-placed sensor nodes that collect measurements over some sensing time window about the activity of the primary user and transmit these measurements to a central node. The central node or fusion center may often be the cognitive base station.
Cooperative sensing techniques can be classified appropriately based on the type of decision metric used at the fusion center. We focus on one of the simplest schemes that relies on energy detection. Most prior work on energy-detection-based cooperative sensing (see [10]- [14] and references therein), the signal is typically a single binary hypothesis modeling a system with one primary user that is either ON or OFF. In cooperative sensing, the measurements from each cognitive sensor node are typically linearly weighted and combined to form a decision statistic that is in turn compared against a threshold to produce a binary output. The paper by Ganesan and Li [10] constitutes one of the earliest contributions that establish the gains in detection (of a single primary user) probability due to cooperation in the presence of channel fading.
Peh et al. [11] and Lee [14] study the tradeoff between sensing time and throughput of the cognitive network since longer sensing times lead to higher primary detection probabilities but lower secondary throughputs. Quan et al. [12] further optimize the linear weighted combiner studied by Ganesan and Li [10] by choosing weights that maximize the detection probability.
While the above authors designed soft-combining systems where the sensors typically report their measurements to the fusion center without any processing, Li et al. [13] consider hard-combining where local decisions are made at each sensor, and design a voting rule to produce the final binary decision. Finally, Mishra et al. [15] compare the performance of hard-/soft-combining and study the effects of correlated fading on the detection probability. We refer the reader to a recent survey papers by Akyildiz et al. [16] and Yucek [17] for a more comprehensive list of references along with further discussion on the other types of cooperative spectrum sensing such as cyclostationary feature detection.

B. Our contributions
In almost all of the reviewed literature, the standard approach to transmit the measurements from the sensor nodes to the fusion center has been to employ orthogonal channels. This means that the control bandwidth demanded by the standard cooperative sensing scheme scales linearly in the number of sensing nodes. This immediately places a significant burden on the bandwidth requirements of the network and might be impractical in some scenarios as recognized by Akyildiz et al. [16]. In this work, we focus reducing the amount of control bandwidth required by the system by considering the structure that may often exist in the dynamics of the observed signals. Thus, we immediately build on and extend past models by adding a temporal dimension to the observed signal and by considering multiple discrete signals instead of a single binary hypothesis.
The key idea we exploit in this paper is the following: while the observed signals at a snapshot in time in general lives in some arbitrary high dimension, often, there is a time-scale separation between the sensing time window and the behavior of the observed process. For example, TV transmitters would turn ON/OFF on a significantly slower time-scale (in the order of minutes) than sensor measurement windows (in the order of milliseconds). Under these circumstances, the dynamics of the observed signal vector is likely to be sparse. It has long been known, and recently popularized under the name of compressive sampling, that whereas N linear measurements are required to reconstruct a vector or signal in R N , if it is S-sparse (i.e., it has S non-zero coefficients) then under appropriate conditions on the measurements, O(S log N) are enough [19], [20], [22]. By developing similar tools, and applying them on the dynamics, rather than the signal directly, we show that with greatly-reduced control bandwidth, our algorithms perform close to the linear control bandwidth case. The performance is measured in terms of the distance between the recovered signal and the true signal.
To the best of our knowledge, this is the first work in the space of wireless networks 1 to exploit sparsity in the dynamics of the observed signal. As this is likely much more prevalent than sparsity in the actual trajectory of the signal (of course, if the trajectory is sparse, then so are the dynamics) we expect this high-level idea to find broad application. More concretely, the 1 Sparse changes in the dynamics of the signal have been used in other areas such as image processing to achieve video compression [18]. main contributions in this paper are as follows: (1) A first (to the best of our knowledge) application of compressive sampling to reduce the control bandwidth in a cooperative sensing system.
(2) A proof that path-loss matrices satisfy the null space property thereby allowing for efficient acquisition or sensing of the observed signal using standard convex programs such as ℓ 1norm minimization and Lasso [28]. The proof technique is novel since path-loss matrices contain entries that have non-zero mean and are not independent, a scenario that has not been dealt with extensively in past research.
(3) Simulation results that establish the competitive performance of our algorithm in comparison to the full control bandwidth case.
The rest of this paper is organized as follows. In Section II, we introduce the system model for the cooperative sensing network under consideration. In Section III, we discuss the compressive sampling algorithm that enables cooperative sensing using significantly-reduced control overhead. We establish the "goodness" of path-loss sensing matrices in Section IV. The complete cooperative sensing algorithm is presented in Section V. Simulation results establishing the competitive performance of the algorithm are contained in Section VI. Concluding remarks are made in Section VII.
Notation: x ij denotes element (i, j) of matrix X while x i denotes element i of vector x. (.) T is the transpose operator. For x ∈ R N , x A , A ⊆ {1, 2, . . . , N} denotes the vector x restricted to the entries in A. For X ∈ R m×n , X A , A ⊆ {1, 2, . . . , m} denotes the sub-matrix of X formed by the rows contained in A. Finally, || · || p is the p-norm operator on vectors.

II. SYSTEM MODEL
We consider a network with N s sensing nodes and a single fusion center operating in slottedtime. We introduce the necessary measurement and signal models below.
Signal generation: We assume the signal of interest is being generated by multiple physical entities (e.g., TV transmitters) that are each dropped uniformly on a circle of radius r p centered at the origin. There are a total of N p such signal generators that are located at points where θ j ∼ U[0, 2π], ∀j. The vector signal emitted at time t is denoted by T where s m (t) corresponds to physical entity or signal generator m and comes from some finite, discrete set. Spatial distribution of sensing nodes: There are N s , N s ≥ N p sensing nodes that are placed on a collection of n c circles of radii {r s,1 , r s,2 , . . . , r s,nc } where N s is such that Ns nc is even. Circle c contains Ns nc interfering receivers located at fixed points {(r s,c , θ i )} Ns i=1 that are equally-spaced θ i = 2πnc Ns , i = 0, 1, . . . , Ns nc − 1 as shown in Fig. 1. We note that this would roughly be the case when N s becomes large and the users are uniformly distributed on this collection of circles.
The fusion center is located at some arbitrary point on the xy-plane.
The above spatial distribution model affords us analytical tractability. In the simulations section, we show that the proposed algorithms work even under a more general spatial model where both the sensing and signal nodes are scattered uniformly on a regular square grid. For the sake of the analysis, we will also partition the sensing nodes according to the circle they belong to thus creating n c partitions {C 1 , C 2 , . . . , C nc } such that nc i=1 C i = {1, 2, . . . , N s } and C i ∩ C j = ∅ for i = j. Within each circle, the nodes are numbered or ordered in diametrically opposite pairs as shown in Fig.1, a labelling rule that is feasible since Ns nc is even. In other words, all pairs (j, j + 1) ∈ C i , j odd, will correspond to a pair of diametrically opposite nodes on circle C i .  Channel model: The distance between the n-th signal generator at location (r p , θ n ) and m-th sensing node at (r m , θ m ) is given by which induces the following path-loss gain between the same. This model is an approximation of the free space path-loss model (with pathloss coefficient two) [21], a choice that affords us analytical tractability while compromising very little on modeling accuracy. The composite channel gain between n-th signal generator at location (r n , θ n ) and m-th sensing node at (r p , θ m ) is given by where g mn (t) ∼ CN (0, 1) models small-scale Rayleigh fading. Distances do not change as a function of time since sensor nodes are deterministically placed and signal nodes are assumed fixed, once drawn from a uniform distribution.

Sensor measurement model:
We adopt the sensing model in [11], [15], where each sensor collects a set of samples over a window of size W time slots. In particular, at time t sensor node m receives the signal where v m (t) is additive noise. Each sensor then forms the following measurement over a Wwindow of samples, The sensors then send their measurements to the fusion center via orthogonal error-free control channels. The fusion center is charged with the task of recovering the observed signal {s n (t)}.
In this work, we do not explicitly account for the time incurred in transmitting measurements to the fusion center and for subsequent actions such as data transmissions by the secondary network in the case of cognitive radio, as we are primarily interested in reducing the control bandwidth between the sensors and the fusion center. Thus, the time index t (and hence k) iterates only across sensing windows.
Sparse dynamics: Due to mismatches between the time-scale of the signal generators and the sensor sample collection period, we assume that the vector s(t) exhibits the following behavior.
The signal s m (t) remains constant through the k-th collection window kW + 1 ≤ t < (k + 1)W and is denoted by s m (k). Furthermore, only a subset of signals change between the k-th and the where (2); β n (k) is a noise term that models the inaccuracies of the LLN over finite averaging windows. It is well-known from the Central Limit Theorem that The term β(k) is referred to as LLN-noise through the remainder of this paper. Next, in the context of the measurement model in (4), we introduce the recovery algorithm that will be developed further through the course of this paper to exploit the sparse structure of the observed dynamics.

Recovery algorithm:
We assume that a subset Q ⊆ {1, 2, . . . , N s } of the measurements z Q (k) are transmitted through |Q| orthogonal control channels to the fusion center at the end of sensing window k. The fusion center must recover the signal s(k). The naïve approach to recovering s(k) would be to transmit all the measured values, i.e., set Q = {1, 2, . . . , N s } to the fusion center 2 . The above naïve solution would consume a control bandwidth of O(N s ). If the process s(k) is completely general, there is little that can be done to remedy this problem, and partial feedback (of only a subset of z) will necessarily result in degraded performance.
However, as discussed in the introduction, for networks where only a subset of signal generators (e.g., TV transmitters) change their state between two adjacent sensing windows, we show that it is possible to reduce the control bandwidth. Using ideas from subset selection and compressive sampling, the next section considers how sparse dynamics can be exploited in order to achieve near-optimal performance while reducing the bandwidth consumption.

III. RECOVERING DYNAMICS THROUGH COMPRESSIVE SAMPLING
In this section, we propose a compressive sampling approach to efficiently recover the signal s(k). Before we discuss the recovery algorithm, we take a short diversion into the topic of compressive sampling.

A. Compressive sampling
The topic of compressive sampling has received tremendous interest in the recent years [19], [20], [22]. The theory essentially states that one can recover sparse data exactly, given an underdetermined system of equations. Specifically, the generic problem is the following: Given a signal x ∈ R N , one receives q << N linear, potentially noisy measurements: y = Mx + w.
Here, M ∈ R q×N encodes the measurement matrix and w ∈ R q denotes additive noise, usually of bounded norm.
For a general vector x ∈ R N , N independent measurements are required to hope to reconstruct x. When q < N, the problem therefore is under-determined. If x is sparse, however, in some settings the problem is no longer under-determined, and can be solved exactly by considering standard convex programs such as arg min x∈R p : ||Mx − y|| 2 2 − ξ||x|| 1 for some chosen ξ > 0, in the noisy case and arg min : in the noiseless case. The former is the so-called Lasso [28] formulation for model selection (subset selection) while the latter ℓ 1 -norm minimization problem is called Basis Pursuit. Many such results have appeared in the literature, e.g., [19], [20], [22], [37] under the umbrella of compressive sampling 3 . Indeed, the results are attractive from an algorithmic perspective since the convex relaxation is easily solvable, with computation time that scales gracefully as the size of the problem increases, allowing the efficient solution of very large problems. The above convex programs succeed as long as the linear equations, or measurements, satisfy a property called Null Space Property (NSP), which essentially amount to the statement that there are no very sparse vectors in the null-space of the measurement matrix M. The theoretical connections between Lasso and Basis Pursuit have been well-analyzed by authors such as Tropp [38].

B. The recovery algorithm
Returning to our problem, we define ∆s(k) = s(k) − s(k − 1) and apply the model selection paradigm outlined above, to the dynamics vector ∆s(k) rather than the signal vector itself. We can assume that at some initial time k 0 , s(k 0 ) is known. At time k, we "query" a subset of sensors Q and receive measurements z Q (k) = Λ Q s(k) + β(k). We can then construct the difference in Since the left hand side, ∆z Q (k), is known, this falls precisely into the sparse recovery paradigm developed above. More concretely, let Q be the subset of queried users with size |Q| = q, q even.
Then, Q is chosen according to the following algorithm: Note that the output query set is not unique since the choice of node-pairs is left open. Let Q Algorithm 1 Protocol to choose query set Q of size |Q| = q 1: Set Q = ∅ and i = 0.

5: end while
be the set of all possible output query sets from Algorithm 1 above. For the example in Fig. 1, one possible output query set for q = 4 is Q = {1, 2, 7, 8}. It is necessary for a query set Q to be selected in this way for the sake of analytical tractability. As with the spatial distribution model, we adopt a more general querying model in our simulations section. Under such a querying model, it is of immediate interest to determine the smallest query size q (or control bandwidth) that the system requires in order to recover s(k) reliably using As mentioned earlier, in this work, we do not consider the number of bits required to communicate z Q (k) reliably to the fusion center as we are interested primarily in the scaling behavior of the control bandwidth.
Compressive sampling theory states that recovery of any S-sparse vector through Lasso or Basis Pursuit is possible in a noiseless setting if and only if the sensing matrix Λ Q , Q ∈ Q satisfies the NSP [32] of order S. This property is defined in the next section. We note that in our application, the sensing matrix is provided by the channel as opposed to traditional compressive sampling where the designer is allowed to choose a convenient sensing mechanism. In the next section, we present the main result of this paper, which states path-loss matrices Λ Q , Q ∈ Q make for good sensing matrices in the noiseless case, i.e., when W → ∞. Recovery results that are proved for Basis Pursuit, which, in the absence of noise, carry over to Lasso [38]. While the theory is developed for the noiseless case with W → ∞, our simulations consider finite averaging windows and demonstrate that sparse recovery still remains effective in this setting.

IV. NSP OF PATH-LOSS MATRICES
In this section, we establish that path-loss matrices Λ Q , Q ∈ Q satisfy the Null Space Property (which will be defined shortly) when the control bandwidth obeys q = O(Slog N p ). Lemma 4, Lemma 5 along with Theorem 4 constitute the main results in this section.

A. Preliminaries
Let the support set of x be denoted by S. A vector x is S-sparse if |S| ≤ S. We define the null space property from Gribonval et al. [34]. where S c = {1, 2, . . . , N} \ S. Based on this property, the following recovery result [34] has appeared both implicitly and explicitly in works such as [32], [35].
Theorem 1: [34] Let M ∈ R q×N . Then, any S-sparse vector may be recovered by solving (5) iff M satisfies the NSP of order S.

✷
The NSP is typically quite difficult to prove directly leading to the development of sufficient conditions that are easier to establish. One such sufficient condition is the restricted isometry property [37] that has become quite popular in recent years and is defined below.
holds for all sets T with |T | ≤ p. Here, (M T ) T is the sub-matrix of M T formed by rows in T .
Here ✷ Thus, the RIP with a sufficiently small constant immediately implies the NSP in the context of ℓ 1 -recovery. The approach we use to prove "goodness" of path-loss matrices Λ Q is motivated by the following observation. In general, the null space of a product of two matrices NM contains the null space of M and therefore if NM satisfies the NSP, so does M. This allows us to study the class of linearly-processed path-loss matrices and diag{·} is the standard block-diagonal operator; with β i ∼ Bernoulli 1 2 , ∀i and independent across i. The Bernoulli random variables have support {±1}. We focus our attention on establishing the recovery properties of A Q rather than Λ Q . We show that A Q satisfies the RIP with q = O(Slog N p ) measurements and hence the NSP.
The transformation W essentially subtracts rows of Λ Q corresponding to diametrically opposite pairs of sensors in the same partition. Thus, the dimension of G is still q ×q. The transformation B weights and adds adjacent rows of G.
According to our spatial distribution model, since the positions of the sensing nodes are fixed, the columns of Λ Q become stochastically independent since each interfering transmitter is independently thrown. At this point, we will rely heavily on recent results from Vershyin [39] and Adamcyzk et al. [40] that deal with sensing matrices containing independent columns.
Before we reproduce the RIP result [39], [40] for matrices with independent columns, we present a primer on sub-gaussian and sub-exponential random variables along with some useful results from non-asymptotic matrix theory.

B. Useful concentration inequalities
We refer the reader to the tutorial paper by Vershynin [39] for a great introduction to nonasymptotic matrix theory. Lemmas 1-3 below are well-known past results that are summarized in this paper [39]. The proofs are not reproduced due to lack of space.
Lemma 1: Let u be random variable. The following properties are equivalent with parameters K i > 0, i = 1, 2, 3, 4, differing from each other by at most an absolute constant factor.
✷ A random variable that satisfies the above property is called a sub-gaussian random variable.
Such random variables are often characterized by the ψ 2 -norm 4 , which is defined as It follows that if the ψ 2 -norm of u is finite, then u is a sub-gaussian random variable with ||u|| ψ 2 = K 2 . This is in fact the case for bounded random variables with symmetric distributions.

✷
In higher dimensions, a random vector u of dimension N is called sub-gaussian if u T x is sub-gaussian for every x ∈ R N .
be a collection of independent, zero-mean, sub-gaussian random variables. Then, u is a sub-gaussian random vector with ||u|| ψ 2 = C max i ||u i || ψ 2 for some C > 0.

✷
We are now ready to prove the RIP (hence NSP) for matrix A Q . Before we move on to this task, we require one more definition. A random vector m of dimension N is called isotropic if E[|m T x| 2 ] = ||x|| 2 for all x ∈ R N .

C. NSP of linearly-processed path-loss matrices A Q
We reproduce the recent RIP result [39], [40] concerning matrices with independent columns.
We refer the reader to [39], [40] for the proof. To finally prove the NSP of Λ Q , Q ∈ Q, we show that after left-multiplication by matrices B and G, the matrix A Q satisfies the sufficient conditions in Theorem 3. The following lemmas and theorem constitute the main theoretical results of this paper.

Lemma 4:
The matrix A Q = BWΛ Q , Q ∈ Q of size q × N contains independent, isotropic, centered, sub-gaussian columns.
Proof: See Appendix A.  We discuss in the next section, how this sparse recovery algorithm is incorporated into the development of a complete cooperative sensing algorithm. In particular, since we are estimating dynamics rather than the signal itself and due to the presence of LLN-noise, the real possibility of error propagation arises. This has not been heretofore addressed in the literature, to the best of our knowledge. In the next section, the algorithm introduces explicit steps to control this. The simulations in Section VI demonstrate the effectiveness of our approach.

V. COMPLETE COOPERATIVE SENSING ALGORITHM
The essential conclusion of the previous section is that the signal vector s(k) can be recovered by acquiring O(SlogN p ) noise-free measurements if the dynamics of s(k) are sparse.
The complete sensing algorithm is presented in Algorithm 2. Recall that we do not consider the actions taken post-sensing and the time taken (equiv. bandwidth per control channel) to transmit the measurements to the fusion center as we are only interested in scaling properties in this work. The algorithm operates in three modes; in dynamics mode, the algorithm retrieves signals dynamics incurring logarithmic control bandwidth and then estimates the recovery error.
If the estimated recovery error is too high, the algorithm switches to partial reset mode in the next sensing window or slot where the fusion center retrieves the signal directly while incurring linear bandwidth. Following partial reset, the system returns to dynamics mode. This operation is overlaid by a periodic (with a pre-set period) reset mode where again the fusion center again retrieves the signal directly incurring linear bandwidth.
In a typical sensing slot, the Lasso procedure in Step 8 recovers ∆s(k). The recovery is almost surely exact when ∆s(k) is sparse and when W is sufficiently large. However, as this might not always be the case in reality, error propagation is a critical aspect that needs to be managed when operating on the dynamics of the signal. The following remarks describe the steps taken by the algorithm to address the same: • The system selects a parameter T err that represents the number of sensing slots after which the fusion center must query all sensors and recover the absolute signal as opposed to the dynamics.
• During typical operation, i.e., when k(mod T err ) ≡ 0, we estimate the accuracy ofs(k) in Step 10 immediately following compressed sampling in Step 9. The technique is commonly referred to as cross-validation [41]. If the estimated error is larger than the threshold ǫ, we query all remaining N s − (q + q ′ ) sensors and recover the absolute signal in the next time slot.
• Once more, due to the sources of noise described above, the vector u(k) retrieved by Lasso in (10) and (12) will almost never be truly sparse. Thus, we introduce a thresholding function to recover a discrete signal.

VI. NUMERICAL RESULTS
In this section, we evaluate the performance of the proposed sensing algorithm using numerical experiments.

A. Simulation setup
The simulation setting is described in the following.

Algorithm 2 Sensing algorithm
1: Primary inputs: sensing window sizes W , number of sensors N s , number of signal emitters N p , sparsity factor S, error reset period T err > 0 2: Initialize mode[0] = "dynamics" 3: for each k = 1, 2, . . . , do 4: if k(mod T err ) ≡ 0 then 5: During time slots kW ≤ t + 1 < (k + 1)W , each sensor samples the signal of interest W times and averages the same to obtain z n (k) as per (4). 6: if mode[k-1] = "dynamics" then 7: The fusion center queries q = Θ(S log N p ) sensors indexed by set Q according to Algorithm 1 and computes the change in received signal levels {∆z Q (k)}.

8:
Dynamics mode: Once acquired, the fusion center estimates the change in measurements ∆s(k) = s(k) − s(k − 1) by solving the following optimization problem: and setting where φ ν i : R Np → R is a suitably-chosen thresholding function with ν that is used to recover discrete sparse signals in noisy environments. 9: The fusion center setss(k) =s(k − 1) + ∆s(k).

10:
The fusion center then queries and acquires extra measurements from q ′ additional sensors Q ′ ⊆ {1, 2, . . . , N s } \ Q, |Q ′ | = q ′ . Then, the fusion center computes which essentially represents the average recovery error on the extra measurements. 11: if e ≤ ǫ, i.e., the estimate is accurate, then 12: Sets(k) to be the final estimate of the signal. 13: Set mode[k] = "dynamics" 14: else 15: Set mode[k] = "partial reset" 16: end if 17: else if mode[k-1] = "partial reset" then 18: Partial Reset Mode: The fusion center queries all N s sensors and uses the measurements to directly recover the final estimates(k) by solving and again, settings

23:
Full Reset Mode: The fusion center then queries all sensors and uses the N s measurements to directly recover the final estimates(k) by solving (12). 24: Set mode[k] = "dynamics". 25: end if 26: end for Network geography -We consider a square region with side length 1 kilometer. We partition this square area into N = 49 micro-cells, each micro-cell is 143m × 143m square area, which is sufficiently small to ensure at most one signal generator or sensor per micro-cell. We index the micro-cells by i (1 ≤ i ≤ N), counted column-wise as shown in Figure 2. Each micro-cell contains one potential signal generator that is located at the center of the square micro-cell. The sensors are positioned one per micro-cell, i.e, N s = N = 49. Signal activity -In our simulations, we assume that the signals are binary-valued, i.e., s m (k) ∈ {0, P }, P > 0, ∀m, k. The activity of each signal generator or micro-cell s m (k) is modeled as a Markovian ON-OFF process where the transition probability from 0 to P is η 0 = η = 0.1 and from P to 0 is η 1 = η = 0.1. The probability that the signal changes state from sensing window to the next can be computed as 2η 0 η 1 (η 0 +η 1 ) = 2×0.1×0.1 (0.1+0.1) = 0.1. Thus, on average 10% or roughly S ave = 49 × 0.1 ≈ 5 signals change their state, which reflects the sparse dynamics.
As per our system model, we assume that P is known and thus, we are only interested in estimating the support at time k. Henceforth, the true support at time k be given by P(k) = {m : m = 1, 2, . . . , N, s m (k) = P }, while the estimated support by Algorithm 2 is given bŷ P(k) = {m : m = 1, 2, . . . , N,ŝ m (k) = P }.
Post-recovery thresholding -We use a simple per-element thresholding function to recover the actual sparse entries themselves. Note that we have to account for negative values for x i since u(k) represents differences in (10).
Performance metric -To measure the signal recovery accuracy of our algorithm, we use a set distance. Given two sets A, B ⊆ {1, 2, . . . , N}, the measure of distance that we use is In the context of our sensing problem, i.e., setting A = P(k) and B =P(k), we see that d(·) essentially counts the fraction of elements that are incorrectly recovered at time k. Now since we are dealing with a stochastic, time-varying system, we are interested in the long-term average distance that is given by where T is the length of our simulation counted as the total number of sensing windows.
Other algorithm parameters -The number of measurements for recovery and error measurement are set to q = S ave log N = 2η 2 (η 0 +η 1 ) log N = η log N = 29 and q ′ = 5 with associated query sets Q = {1, 2, . . . , k} and Q ′ = {k + 1, k + q ′ }. The regularization parameter is set to ξ = 0.01. The remaining parameters such as W ,η,ε and T err will be varied in our experiments.
Control bandwidth -Note that the parameters q, q ′ , ε, T err and N have a direct bearing on the bandwidth consumed by our algorithm. To analyze the bandwidth consumed in Algorithm 2, we basically count the fraction of time algorithm spends in each of the modes in Steps 8, 18 and 23. For a total communication duration of T sensing windows or slots, i.e., k = 1, 2, . . . , T , let the time spent in dynamics, semi-reset and reset mode be given by T d , T s−r and T r respectively.
Then, the bandwidth consumed, is given by and the savings over full (linear) control bandwidth can be expressed as 1 − B N . The control bandwidth, in addition to the distance measure in (14), is an important evaluation metric, one that forms the core motivation of this paper.
Through the remainder of this section, we explore the many interesting trade-offs that are inherent in our proposed sensing design in the context of the above parameters.

B. Simulation results
Having described our simulation setup in detail, we now proceed to analyze the performance of our algorithm. Since the baseline naïve algorithm in itself does not achieve perfect recovery due to LLN noise, we adopt the following methodology for comparison. We fix a target average distance and determine the minimum sensing window size W min needed to achieve this target when consuming full linear bandwidth, i.e., with q = N. Note that as the sensing window size grows, the average distance can be made arbitrarily small thereby approaching perfect recovery.
We show that with careful tuning, Algorithm 2 consumes considerably lesser bandwidth in achieving the same target average distance while maintaining the same window size of W min .
First, in order to determine W min , we analyze the average distance of the naïve algorithm versus W , i.e, set T err = 1 in Algorithm 2, which means that we always retrieves absolutes. We fix the target average distance to be 0.1. In Fig. 3, we plot the average distance of the naïve algorithm over the range W ∈ {50, . . . , 1000}. From Fig. 3, we see that for a target average distance of 0.1, we need 2000 samples to form (4). We therefore set W min = 2000 as the baseline window size for the naïve algorithm. Having identified W min , next we proceed to tune Algorithm 2 with the goal of outperforming the naïve algorithm. In particular, we study the accuracy-bandwidth performance of our approach while varying the error threshold ε, the reset period T err and the support threshold ν over the space (ε, T err , ν) ∈ {0.1P, 0.5P, P, 2P, 3P } × {P, 2P, 3P, 4P, 5P, 8P } × {0.25P, 0.5P, 0.75P }.
Note that this amounts a total of 5 × 6 × 3 = 90 configurations. The window size is set to index, which essentially maps to a (ε/P, T err /P, ν/P )-triplet as specified in Table I. From Table I Thus, by exploiting the structure in the emitted signal, we are able to achieve significant savings in control bandwidth over the naïve algorithm. Recognizing that the number of parameters that control the algorithm is quite large, we believe that with more extensive tuning/optimization of the various components, e.g., error measurement budget q ′ , further savings might be possible, especially as the scale or dimension of the problem grows. Finally, we note that the proposed compressive sampling approach has been applied to (even) more general spatial distribution models such as one where both the sensor and signal nodes are thrown uniformly at random on a square area, in the absence of a grid. The results are as promising but not presented here due to lack of space.

VII. CONCLUSIONS
In this paper, we apply ideas from the field of compressive sensing to reduce the control bandwidth in cooperative sensing systems. We are particularly interested in settings where the dynamics of the signals being observed are sparse. This is indeed what one typically expects for systems that exhibit a time-scale separation between the sensing network and the signal emitting process. We prove theoretical RIP-/NSP-based recovery results for path-loss matrices in networks with circular geometries. We then develop a complete cooperative sensing algorithm that addresses key issues such as error propagation. As the proposed algorithm requires many input parameters, we extensively tune these parameters in our numerical experiments. We demonstrate that our approach can provide significant bandwidth savings over the naïve linear bandwidth case under more general spatial distributions. Extending the theory to cover these general spatial distributions remains an open problem that deserves attention. Recall that Λ C i represent the sub-matrix of Λ Q containing the rows specified in C i . Then, the entries {λ ij } of sub-matrix Λ C i are identically distributed. This follows from the observation that any two sensor nodes on the circle of radius r s,i will perceive the same distribution of signal nodes since the latter nodes are distributed on a circle. Recall that the transformation G = WΛ Q essentially subtracts rows of Λ Q corresponding to diametrically opposite users on each circle.
Thus, the columns of G are independent and all entries are centered. The next step is to show that the entries g ij = λ ij − λ (i+1)j are symmetric. This is does not follow immediately from the fact that λ ij and λ (i+1)j are identically distributed when indices i and i + 1 come from the same partition since they are not independent. Hence, we appeal to the concept of exchangeable random variables, which is defined below for the special case of a pair of random variables.
Definition (Exchangeability): Two random variables X and Y are called exchangeable if their joint cumulative distribution function (cdf) is symmetric, i.e. if F X,Y (x, y) = F X,Y (y, x).
It is known the difference of two identically distributed, exchangeable random variables is indeed symmetric [43]. Thus, we only need to establish this fact for the case when λ ij and λ (i+1)j come from the same circle, say C c , since the definition of G in (8) precludes any other possibility.
To establish that λ ij and λ (i+1)j are exchangeable, we compute the joint cdf F λ ij ,λ (i+1)j (x, y), when i and i + 1 come from the same circle c, as follows where we have introduced the function d 2 (θ m , θ n ) = r 2 s,1 + r 2 p − 2r p r s,1 cos (θ m − θ n ), i = 1, . . . , α(k), for notational convenience through the remainder of the proof. The set R(θ j , θ i , x, y) is defined as Ns , y .
From this characterization, we can immediately conclude that V(R(r p , θ j , r s,c , θ i , x, y)) = V(R(θ j , θ i , y, x)), which gives our the desired result that λ ij and λ (i+1)j are exchangeable implying that the entries g ij = λ ij − λ (i+1)j are symmetric for all (i, j). It is clear from the above arguments that exchangeabilty essentially follows due to the uniform distribution of the signal emitters.
The symmetry of g ij is crucial for our next step where we argue that columns of A Q = BG remain independent. By definition, a ij = 1 √ Var{g i1 } β i g ij . Thus, to prove that the columns of . . a Np are independent, we need to show that a ij ⊥ a k for any arbitrary i, j and k = j. Since the Bernoulli random variables are independent across rows and since g ij ⊥ g mk , k = j, m = i, we clearly have that a ij ⊥ a mk , k = j, m = i. Thus, we only need to establish that a ij ⊥ a ik for k = j or equivalently that β i g ij ⊥ β i g ik . But this follows from the symmetry of g ij which means that knowledge of β i g ij reveals no information about the random variable β i . Thus, the columns of A Q are independent. In addition, there are identically distributed and hence we can now focus on studying the properties of column a 1 without loss of generality.
The random vector To prove that a 1 is sub-gaussian, we first condition on the position of the first signal emitter (r p , θ 1 ). This will allow us to apply Lemma 1 and Lemma 2 since g i1 is now completely known thereby making a i1 a collection of independent random variables. The elements a i1 are symmetric and bounded with |a i1 | ≤ |g i1 | √ when conditioned on position (r p , θ 1 ).
Proof: By definition, the distribution of g i1 for p Ns q < i ≤ (p + 1) Ns q depends on the distance between the corresponding diametrically opposite sensors on circle (p + 1) along with the distribution of the first interfering user. Since this distance always remains the same independent of i and k, the result follows. ✷ Hence, by Lemma 2 and since |g i1 | ≤ 1, a i1 is sub-gaussian with ||a i1 || ψ 2 |(rp,θ 1 ) ≤ 1 where M * = min p=1,...,q M p . Here, we have introduced notation ||·|| ψ 2 |(rp,θ 1 ) to indicate explicitly that we have conditioned on the location of the first interfering user. Now, from Lemma 1, we conclude that a 1 is a sub-gaussian vector when conditioned on the location of the first signal node with ||a 1 || ψ 2 |(rp,θ 1 ) ≤ 2C, C > 0. However, since the sub-gaussian norm ||a 1 || ψ 2 |(rp,θ 1 ) computed above is independent of (r p , θ 1 ), this implies that a 1 is a sub-gaussian vector with ||a 1 || ψ 2 ≤ 2C. To show almost-sure convergence of the norm of a 1 , we need to prove that ∃c * > 0 such that Pr lim k→∞ 1 k k i=1 a 2 i1 − c * = 0 = Pr lim k→∞ 1 k k i=1 g 2 i1 − c * = 0 = 1 where the probability is computed over the random location (r p , θ), θ ∼ U[0, 2π]. We instead prove the following more general statement that ∃c * > 0 such that Note that (19) is a completely deterministic convergence statement in contrast to the earlier probabilistic statement. From the proposed query protocol in Algorithm 1, we see that the number of sensors selected for feedback is a monotonically increasing function of k for all circles.
This mean that we can study the convergence of the norm for any one circle (a sub-vector of a 1 ) and draw conclusions about the norm concentration of the entire vector a 1 . Consider the first partition of sensors on circle C 1 and let the size of this partition be α(k). Then, we see that α(k) → ∞ as k → ∞ and hence, we can shift our focus to proving the property lim k→∞ i1 ] − c * = 0, ∀(r p , θ 1 ), θ 1 ∈ [0, 2π]. In fact, we show that c * = 1, i.e, Recall that the squared-distance between a signal generator located at (r p , θ 1 ) and sensor node i on C 1 is given by d 2 (θ i , θ 1 ) where d(·) is defined in (17)and where θ i = 2πiq k . Now let f (x, y) = 1 K+x − 1 K+y 2 , x, y > 0 where K is given in the definition (1). Then, g 2 i1 can equivalently be expressed as g 2 i1 = f d 2 (θ i , θ 1 ) , d 2 θ i + π 2 , θ 1 . Now, we proceed to prove (20) by observing that This claim follows from that fact that the expression on the left is essentially the Riemann sum of the integral on the right. This means that for any given ε > 0, we can find k ε such that when k ≥ k ε , we have that 1 By substituting (17) in (21) and (22), we see that the variable of integration may be switched and hence = 1 2π 2π 0 f d 2 (θ i , θ) , d 2 θ i + π 2 , θ dθ = 1 2π 2π 0 f d 2 (θ i , θ) , d 2 θ i + π 2 , θ dθ i , which implies that We can then establish convergence through i1 ] ε when k ≥ k ε . 29 The result follows since E[g 2 i1 ] is bounded below by Lemma 6. ✷