Applications of Compressive Sensing in Wireless Sensor Networks
- 주제(키워드) Information Network
- 발행기관 고려대학교 대학원
- 지도교수 백승준
- 발행년도 2015
- 학위수여년월 2015. 8
- 학위구분 박사
- 학과 대학원 전기전자전파공학과
- 원문페이지 113 p
- 실제URI http://www.dcollection.net/handler/korea/000000059969
- 본문언어 영어
- 제출원본 000045841443
초록/요약
In this thesis, we consider the data collection problem in Wireless Sensor Networks (WSNs). Compressive Data Gathering (CDG), which adopts the Compressive Sensing (CS) technique to collect data, is used to collect data. CDG is able to reduce the energy consumption and evenly distribute the network load when compared with the conventional data collection. However, most of the works on CDG use a dense sensing matrix. We adopt a sparse random matrix as the sensing matrix under the CDG framework, which is called as the Sparse Random Sampling (SRS). In SRS, only a subset of nodes, i.e., source nodes, is required to report data to the sink during the process of collecting each measurement. Depending on the objective, we propose two data collection schemes. Specifically, three objectives are considered: network lifetime, total energy consumption and latency. For maximization of the network lifetime, we propose a greedy algorithm. The greedy algorithm collects measurements round by round. During each round, we uniformly and randomly select source nodes. Given the source nodes, we intend to construct a data aggregation tree such that 1) it is rooted at the sink and spans every source node; 2) the minimum residual energy of nodes in the data aggregation tree is maximized. We theoretically formulate this problem as an optimization problem and prove its NP-completeness. Then we propose a polynomial time approximation algorithm, which is referred to as AMREST (Approximately Maximum Residual Energy Steiner Tree), to construct an approximately optimal data aggregation tree. Analysis shows that the gap of the minimum residual energy between AMREST and the optimal data aggregation tree is irrespective of the network size. Furthermore, the gap of the minimum residual energy between AMREST and the maximum achievable minimum residual energy of any other polynomial time algorithm is a constant unless P=NP. Simulation results also show that AMREST has a good performance. For the reduction of total energy consumption or latency, we propose a Connected Dominating Set (CDS) based algorithm. The CDS serves as a backbone and each node communicates with the sink through the CDS. We show that the optimality of total energy consumption or latency can be achieved by properly controlling s, the nonzero probability of each entry in the sensing matrix, and the communication range r. In this thesis, we also study signal reconstruction from compressed sensing measurements. New sufficient conditions for stable recovery under the assumption that partial support information is available, are provided. Weighted L1-minimization is adopted to recover the original signal under three noise models. The proposed approach is to use Ozeki’s inequality and shifting inequality in order to bound the errors in the associated weighted L1-minimization. Our result offers generalized performance bounds on recovery capturing known support information. Improved sufficient conditions for recovery are derived based on our results, even for the cases where the accuracy of prior support information is arbitrarily low.
more목차
List of Figures
List of Tables
Acknowledgments
Abstract
1 Introduction
1.1 Overview of Compressive Sensing
1.2 Preliminaries
1.2.1 Norms of a vector
1.2.2 Sparse signals and compressible signals
1.3 Problem Formulation
1.3.1 A linear model
1.3.2 Sensing matrices
1.3.3 Recovery algorithms
1.4 Applications of CS in WSNs
1.5 Outline of the Thesis
2 Sufficient Conditions on the Weighted L1-Minimization
2.1 Contributions
2.2 Weighted L1-minimization
2.3 Discussion
2.4 Extensions
3 Sparse Random Sampling
3.1 Introduction
3.2 Related Work
3.3 Examples of Sparse Random Sampling
3.4 Problem Formulation
3.5 Proposed Algorithm
3.5.1 Basic notions
3.5.2 Outline
3.5.3 Example
3.5.4 Unblocking procedure
3.6 Conclusions
4 Capacity Analysis of Sparse Random Sampling
4.1 Introduction
4.2 The proposed scheme
4.2.1 Routing
4.2.2 Scheduling
4.2.3 Correctness
4.3 Performance Analysis
4.3.1 Energy Consumption
4.3.2 Latency
5 Simulations
6 Conclusions
Appendix
Acronyms
Bibliography
