DATA COLLECTION ALGORITHMS IN WIRELESS SENSOR NETWORKS EMPLOYING COMPRESSIVE SENSING By MINH TUAN NGUYEN Bachelor of Electrical Engineering University of Transport and Communications Hanoi, Vietnam 2001 Master of Electrical Engineering Military Technical Academy Hanoi, Vietnam 2007 Submitted to the Faculty of the Graduate College of Oklahoma State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY December, 2015 COPYRIGHT ⃝ c By MINH TUAN NGUYEN December, 2015 DATA COLLECTION ALGORITHMS IN WIRELESS SENSOR NETWORKS EMPLOYING COMPRESSIVE SENSING Dissertation Approved: Dr. Teague Dissertation Advisor Committee Member: Dr. George Scheets Committee Member: Dr. Qi Cheng Committee Member: Dr.
Johnson Thomas Dr. Sheryl Tucker Dean of the Graduate College iii ACKNOWLEDGMENTS Firstly, I would like to express my sincere gratitude to my advisor Prof. Teague for the continuous support of my Ph.D study and related research, for his patience, motivation, and immense knowledge. His guidance helped me in all the time of research and writing of this thesis.
I could not have imagined having a better advisor and mentor for my Ph. I also would like to thank his wife, Mrs. Sherry Teague for everything she did for my family and myself. Thank you both very much for helping our colleagues from TNUT to visit OSU.
Besides my advisor, I would like to thank the rest of my thesis committee: Prof. George Scheets, Prof. Qi Cheng from School of Electrical and Computer Engineering and Prof. Johnson Thomas from Computer Science department for their insightful comments and encouragement, but also for the hard question which incented me to widen my research from various perspectives.
I also would like to thank some professors from Electrical and Computer engineer- ing (ECE), Dr. Martin Hagan, Dr. James West, Dr. Guoliang Fan and Dr.
Weihua Sheng for their classes and their knowledge they shared with me. I really appreciate that. Being far away from my home country and my institute has been given me a big gap of culture. I would like to thank the department staffs, Hellen Daggs, Brian Ritthaler, especially Lory Ferguson for being supportive all the time.
I thank my fellow labmates, Ali Talari, Behzad Shahrasbi, Sheng Wang from CWN lab for the stimulating discussions, for the tough time we were working together, and for all the fun we have had in the last few years. iv My sincere thanks to all my Vietnamese families and friends here in Stillwater, Oklahoma. ”chu Xuong”, ”chu Loi”, ”chu Nho”, ”em Dinh”, ”em Loan”, Ha Do, Son Bui, Hung La, Hoa Nguyen, etc. You all have made us the second family here in the US.
I am grateful to the Vietnamese Student Association (VSA) with useful activities that brought us, our Vietnamese students at OSU close together. Last but not the least, I would like to thank my little family, Ally Nguyen, Hang Nguyen and Thuong Nguyen for being with me, going together through tough time and enjoying happiness together. Without you, I would not have done this far with effort and succeed. I am very grateful to my big family, my parents, my brother, my nephew and niece for supporting me spiritually throughout writing this dissertation and my life in general.
I would like to thank the big family in Ha Noi, especially grandpa Khien Trong Nguyen, for being supportive me while I was preparing to study abroad. Thank you all very much!!! Thanks the others I did not list their names here. Five years generally may not be considered as a long time, but for me, we do not have many this five years in our lives. So, it is precious.
Thanks Stillwater, the very peaceful land and suitable for studying. I may not see You again but I appreciate every moment here in Oklahoma, USA. Thank You! v TABLE OF CONTENTS Chapter Page 1 INTRODUCTION 1 2 BACKGROUND AND LITERATURE REVIEW 3 2.1 Wireless Sensor Network Overview .2 Challenges for Data Collection Method Design in WSNs .3 Data Collection Method Protocols in WSNs .2 Introduction to Compressive Sensing .1 CS Based Data Collection Algorithm in WSNs .2 Minimizing the Number of CS Measurements. 51 3 RANDOM WALK BASED DATA GATHERING IN WIRELESS SENSOR NETWORKS 53 3.2 Background and Problem Formulation .3 Compressive Sensing Based Random Walk Data Collection Algorithm (CSR) .2 The CSR Algorithm .3 Analysis of the Measurement Matrix: CS Recovery Perfor- mance and Network Coverage .4 Analysis of the Trade-off between the Transmission Range and the Random Walk Length .4 Directly Forwarding the CS Measurements to the Base-station (D-CSR) 63 3.2 D-CSR Power Consumption Analysis .3 D-CSR Simulation Results .5 Multi-hop Relaying Data from Random Walks to the Base-station (M- CSR) .2 Multi-hop Relaying Data Algorithm .3 M-CSR Power Consumption Analysis .4 M-CSR Simulation Results .6 Conclusion and Future Work.
79 4 CLUSTER BASED DATA COLLECTION IN WIRELESS SENSOR NETWORKS 81 4.2 Block Diagonal Matrices .3 CCS: Cluster-Based Compressive Sensing for Data Collection in WSNs 88 4.4 Directly Send CS Measurements to the BS (DCCS) .2 Power Consumption Analysis for DCCS .3 Simulation Results for DCCS .5 Inter-cluster Multi-hop Routing in CCS (ICCS) .2 ICCS Power Consumption Analysis .3 ICCS Simulation Results .6 DCT Compression Transmitting only k Large Coefficients .2 Communication Power Consumption. 120 5 TREE-BASED DATA GATHERING IN WIRELESS SENSOR NET- WORKS 122 5.2 Tree-base Energy-Efficient Data Gathering (TCS) .3 Power Consumption Analysis .4 Conclusions and Future Work. 137 6 NEIGHBORHOOD BASED DATA COLLECTION IN WIRELESS SENSOR NETWORKS 138 6.2 Neighborhood Based Data Collection Algorithm (NeiCS) .3 Power Consumption Analysis .4 Conclusion and Future Work. 151 7 CONCLUSIONS 152 BIBLIOGRAPHY 154 A RANDOM WALK BASED DATA GATHERING IN WIRELESS SENSOR NETWORKS 174 A.1 Additional Analysis for D-CSR to calculate EdtoBS in order to compare with M-CSR.
174 ix LIST OF TABLES Table Page 4.1 Comparison between the existing data collection methods and CCS. 85 x LIST OF FIGURES Figure Page 2.1 K-means clustering algorithm with k = 10 clusters .2 EEHC algorithm with single level of clustering .3 FLOC program consists of 6 actions .4 Unequal size clusters in EEUC clustering algorithm .5 Packet transmission and global transmission schedule on location-aware in PEACH .6 Cluster structure of a network with MRPUC .7 S-Web clustering algorithm .8 HEECH divides WSN into six tracks with the same width .9 An illustration of Directed Diffusion in WSN .10 State transitions in GAF .11 Some common normed vectors .12 Random projection matrix .13 Restricted Isometric Constant Function .14 Sparsifying signals in a proper domain with ψ matrix .15 Compare four Compressive Sensing reconstruction schemes .1 Illustration of a simple RW routing in a WSN with 8 nodes and the projection matrix created from each RW.2 Sensor neighborhoods defined by the sensor transmission range R .3 An illustration of RWs collecting data when BS at the center .4 RWs collecting data when the BS is outside the sensing area at (Li , L2 ).5 The average number of neighbors of each sensor when changing the sensor transmission range R .6 The mixing time reduces as the sensor transmission range R increases 69 3.7 Sampling coverage the network with different number of random walks length 48 (τ = 48) .8 The average square distance (E[d2toBS ]) between RWs and the BS at different positions Li ≥ 0.5L up to Li = 5L .9 Total power consumption of the network versus sensor transmission ranges when BS at the center of the sensing area .10 Comparison between the full dense Gaussian and the sparse binary matrix collected different number of RWs: random walk length τ = 48 with different number of measurements .11 Total power consumption through all data collection processes with M = 90 measurements, transmission range R* = 14 in different RW’s lengths when the BS at the center of the sensing area .12 Tree-based relaying measurements after each RW to the base-station formed with 500 nodes and transmission range R = 14.13 Total number of hops from all sensor nodes to the BS as we increase the transmission range R .14 The total power consumption applied M-CSR versus different trans- mission ranges R when BS at the center; R* = 12 .15 Compare the total power consumption in two random walk routing method when BS at the center and R = 14.1 Average reconstruction error versus the fraction of the measurements collected from the first cluster (T = M1 /M ). The error is minimize when T is equal to the fraction of the nodes in the first cluster (N1 /N = 0.2 A clustered WSN with BS outside the sensing area (Li > L).3 Histogram of number of sensors in each cluster for K-means and LEACH.4 Number of measurements required to satisfy target error = 0.1 for a 100-sparse signal (sparse in canonical basis).5 Total power consumption when BS at the center of the sensing area.6 Total power consumption when BS at 1L (Li = L).7 Total power consumption when BS at 2L (Li = 2L).8 Total power consumption when BS at 3L (Li = 3L).9 Number of measurements required when Wavelet is considered as the sparsifying basis.10 Total power consumption when the BS is at the center of the sensing area.11 Total power consumption when Li = L.12 Total power consumption when Li = 3L. Here, Nc∗ = 2 or 3 (depend- ing on the clustering scheme).13 Total power consumption when Li = 5 × L.14 Number of measurements required when DCT is considered as the sparsifying basis.15 Total power consumption when the BS at the center of the sensing area.16 Total power consumption when the BS outside the sensing area at Li = 3L.17 All transmissions in the clustered network with inter-cluster multi-hop routing when the BS at the center.18 Total number of hops routing when changing the broadcasting radius R 110 4.19 The total power consumption when change the broadcast radius R .20 Intra-cluster power consumption when BS at the center in a circle sensing area .21 Inter-cluster power consumption when BS at the center in a circular sensing area .22 Total power consumption for ICCS and DCCS in a circular area net- work with R0 = 50 .23 Unsorted sensory readings from 2000 sensors and the DCT transformed coefficients .24 Descending sorted readings from 2000 sensors and the DCT trans- formed coefficients .25 Reconstruction error versus number of measurements with different of clusters .26 Reconstruction error versus number of clusters with different of mea- surements .27 CS reconstruction error versus measurements with noise .28 DCT compression reconstruction error versus measurements with noise and noiseless .1 An example of a tree formed by MTT algorithm with 1000 nodes de- ployed in a arbitrary network when BS at the center .2 A simple example illustrates TCS algorithm with 8 sensors .3 Compare total numbers of transmissions between three algorithms in different lattice topology networks .4 Total energy consumption in arbitrary networks with different numbers of nodes with M = 500, p = 1/3 .5 The reduction ratio of power consumption of TCS over MTT in ar- bitrary networks versus the various number of sensors(M = 500, p = 1/3) .6 Total number of transmission hops in various transmission range (N = 2000; M = 500; p = 1/3) .7 Power consumption affected by increasing transmission range (N = 2000; M = 500; p = 1/3) .8 Power consumption reduced with sparser projection matrices in both MTT and TCS in arbitrary networks (N = 2000; M = 500) .9 CS reconstruction error when reducing the probability of non-zero el- ements in sparse measurement matrices .1 M random neighborhoods are sampled in an arbitrary network with 500 sensors; transmission range R = 9 defines N neighborhoods in the graph G(V, E).2 Tree formed by the greedy algorithm with 500 nodes and transmission range R = 14 to relay measurements from random sensors to the BS.3 Comparison between full Gaussian measurement matrix and the one created by NeiCS .