This work has been presented in IEEE Global Communication Conference (GLOBECOM 2014), and published in IEEE Transactions on Signal Processing. Please refer to the following links to access the papers:
Conference paper IEEE
Journal paper: IEEE ArXiv
Summary: In this work, we focus on the sparse event detection (SED) problem in wireless sensor networks (WSNs), where a set of sensor nodes are placed in the field of interest to capture sparse active event sources. The SED problem in WSNs is represented from a coding theory perspective by using capacity approaching analog fountain codes (AFCs) and further solved with a standard belief propagation (BP) decoding algorithm. We show that the sensing process in WSNs produces an equivalent analog fountain code at the sink node, with code parameters determined based on the sensing capability of sensor nodes and channel gains. We analyze the probability of false detection of the proposed approach and show it to be negligible. Simulation results show that the proposed approach, namely sparse event detection with AFC (SED-AFC), achieves a significantly higher probability of correct detection (PCD) compared to existing schemes at various SNR values, with a negligible probability of false detection (PFD). Moreover, we show that the minimum sampling ratio in high SNRs for the proposed scheme reaches the lower bound which is mainly characterized by the sensing coverage of the sensors and field dimensions.
Motivations: The Compressive Sensing (CS) theory has been widely used in wireless sensor networks (WSNs) and has shown great performance improvements in terms of network lifetime, energy efficiency and overall system throughput. CS mechanisms are beneficial to WSNs as sensor nodes usually have constrained sensing, limited memory and processing capability, as well as small communication bandwidth. A special scenario is sparse event detection (SED) in WSNs, where a set of monitoring sensors try to capture a small number of active events randomly distributed in the sensing field.
Our solution to the SED problem was inspired by our recent work on capacity approaching analog fountain codes, where modulated symbols are directly generated from a linear combination of information symbols with real wight coefficients. The sensing process in WSNs can then be represented as the encoding process of AFCs, where the real weight coefficients are channel gains, and the code degree is mainly determined by the sensing capability of sensors and number of event sources and sensor nodes. Therefore, the standard belief propagation (BP) decoder can be effectively used for the SED problem by treating sensor readings and event sources as check nodes and binary variable nodes, respectively. More specifically, we characterize the code degree, defined as the number of event sources inside the sensing coverage of a sensor node, and variable node degree, defined as the number of sensors which have covered an event source, for two scenarios of random and uniform deployment of sensor nodes.
Fig. 1. M active sensors are capturing k out of n active events randomly distributed within field S.
We consider a total n event sources, E1, E2,…, En, randomly placed in a sensing field S with a total area of S as depicted in Fig. 1. Each event source Ei randomly generates an event ei to be measured by the sensor nodes and further detected by a sink node. An event is defined with a binary signal, which is 0 or 1 (or a constant value) with a certain probability determined by the physical properties of the sensing field. We refer to those events which have the value of 1 as active events, where the number of simultaneously active events, denoted by k, is much smaller than n, i.e., k<<n.
The event sources are captured by m active monitoring sensors, which can be deployed in the sensing field S in many ways, from which we consider two general cases. In the first case, namely random deployment, sensors are randomly placed in the sensing field. In this approach, some event sources may not be covered by any sensors; thus, we cannot detect those events. In the second case, namely uniform deployment, sensors are uniformly placed within the field to fully cover the sensing filed. The sensing range of each sensor is assumed to be Rs, which means that a sensor can receive the signal from event sources within a distance of at most Rs. Let hi,j denote the channel gain between the ith event source and the jth sensor node in the field, then hi,j is modeled by the path loss model and Rayleigh fading.
The received signal yj at the jth sensor is then given by:
yj=∑i ∈ Sj hi,j ei+zj,
where Sj is the set of event sources inside the sensing range of the jth sensor and zj is the thermal measurement noise at the jth sensor. The received signal vector Y can then be written as follows:
where H=[hi,j], z=[zj] and e=[ei].
The sink node is assumed to have full knowledge of the channel matrix H and all sensors’ readings are sent to the sink node at SNR γ. More specifically, the received signal at the sink node can be shown as follows:
where w is the m×1 additive white Gaussian (AWGN) noise vector with zero mean and variance σ2.
Our goal is to then find the active events from the received signal of all sensors given the channel matrix H. As the sensing range of each sensor is limited, the number of active events inside the sensing range of each device, or simply the number of nonzero elements of each row of H, is limited. As a result, we can consider the SED problem as a binary compressive sensing problem, where event sources are mapped to sparse binary signal elements and sensors readings are mapped to measurements with measurement matrix H.
1.The following lemma gives the probability distribution of the sensor degree in random deployment scenarios and gives a lower bound on the minimum number of sensors to have a minimum event degree of at least 1.
2. The following lemma gives an upper bound on the probability of false detection (PFD), defined as the probability that a nonactive event is falsely detected as active.
3. This figure shows the minimum sampling ratio required to successfully detect all active events versus the signal sparsity order s and Rs for the uniform deployment scenario. As can be seen in this figure, with increasing s, a larger number of sensors have to be deployed in the sensing field. This is because of the fact that a larger number of active event sources are connected to each sensor nodes; thus, the proposed sum verification decoder with T = 2 requires a larger number of measurements for sparse event detection. Moreover, when Rs increases, a smaller number of sensor nodes is required to be deployed in the sensing field to successfully recover all active events. However, when the signal sparsity order increases, a lower number of sensor nodes is required when the sensor coverage radius is low compared to the case that the sensing coverage radius is high.
4. The following figure shows PCD versus the sampling ratio at different SNR values, when n = 1000 event sources are randomly distributed in an area of 1000 m by 1000 m, k = 10, and α = 3. As can be seen in this figure, the proposed AFCS scheme outperforms both BCS and SCS in terms of PCD for different SNRs. Moreover, the number of required sensor nodes in SCS is relatively large (500), which significantly increases the total number of transmissions, leading to poor energy efficiency. It is important to note that the existing approaches need to know the number of active events to achieve a relatively good performance in terms of PCD; however, the proposed AFCS approach does not need to know the sparsity level of the events and can work for various numbers of active events. Moreover, the achievable PCD for the AFCS scheme with random deployment is very close to that for the SCS approach , and so we removed the respective curve from the figure for a clearer representation.
5. The following figure shows the minimum sampling ratio versus SNR in order to achieve a PCD larger than or equal to 99%, when α = 3 and n = 256 event sources are randomly distributed within 500 m by 500 m area. As can be seen in this figure, in low SNRs, the proposed approach can detect the active events with a large number of sensor nodes, where a WSN with sensors with a high coverage radius is more robust to the noise effect in terms of the sampling ratio. Note that in the random deployment scenario, more sensor nodes are required as some event sources may not be covered by any sensor nodes, leading to a lower percentage of correct detection.
- Shirvanimoghaddam, M.; Yonghui Li; Vucetic, B., “Sparse event detection in wireless sensor networks using analog fountain codes,” in Global Communications Conference (GLOBECOM), 2014 IEEE , vol., no., pp.3520-3525, 8-12 Dec. 2014. URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7037353&isnumber=7036769
- Shirvanimoghaddam, M.; Li, Y.; Vucetic, B.; Yuan, J.; Zhang, P., “Binary Compressive Sensing Via Analog Fountain Coding,” in Signal Processing, IEEE Transactions on , vol.63, no.24, pp.6540-6552, Dec.15, 2015. URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7219476&isnumber=7323913