Retrieval Technology Research For Wireless Sensor Networks

With the rapid increase of retrieval users on wireless sensor networks, sensor networks are finding wider application aspects when the scale of WSN becomes larger. It is hard for traditional retrieval infrastructure to meet these challenges with the limitation of sensor network such as power consumption of nodes. This situation calls for new technologies.Top-k query has long been an important topic in many fields of computer science. Efficient implementation of the top-k queries is the key for information searching. With the new frontier such as the cyber-physical systems, where there can be a large number of users searching information directly into the physical world, many new challenges arise for top-k query processing. Also as one of most important functions among many aggregate functions in wireless sensor networks, top-k query is crucial for many applications such as environment monitoring, network management, and biology analysis. One application is that users may want to continuously extract rough or aggregated data such as historical top-k results from the networks for analysis later. The approach used in continuous top-k monitoring does not work in the historical scenario. Unlike the data centers used for searching in the database community or cyber-space, these sensor nodes are often extremely resource-constrained and system efficiency is of paramount importance. Besides, from the client's perspective, different users may request different set of information, with different priorities and at different times. Thus, the top-k search not only should be multi-dimensional, but also across time domain. From the system's perspective, the data collection is usually carried out by small sensing devices.Data gathering plays a vital role in wireless sensor networks (WSNs), and data query from different users is among the most common tasks. Gathering information in an energy efficient way is critical to long-running sensing applications. Recently, compressive sensing, a generic technique for recovering sparse signal from fewer and compressed measurements has been developed, which exploits sparsity in many real-world traces. But existing com-pressive sensing solutions often do not work well since the sparsity of spatial traces at any one time is often not low enough and the relative order of spatial traces is not fixed.The works of this dissertation concentrate on retrieval in wireless sensor networks, the contributions of the dissertation are:(1)In this thesis, a framework that can effectively process the continuous historical top-k query is proposed. A simple top-k extraction algorithm based on aggregation is used for the user query processing and two additional steps on the filter setting by which individual nodes do not have to reports all their readings are proposed to further reduce communication cost. To the best of our knowledge, this is the first work for continuous historical top-k query processing in sensor networks; and our simulation results show that our schemes can reduce the total communication cost and life time by up to two orders of magnitude, compared to the centralized scheme or a straightforward extension from previous top-k algorithm on continuous monitoring query.(2) In this thesis, a framework that can effectively satisfy the two ends is proposed. The sensor network maintains an efficient dominant graph data structure for data readings. A simple top-A extraction algorithm is used for the user query processing and two schemes are proposed to further reduce communication cost. Our proposed methods can be used for top-k query with any linear convex query function. Our framework is adaptive enough to incorporate many advanced features; and we show how approximate queries and data aging can be applied. To the best of our knowledge, this is the first work for continuous multi-dimensional top-k query processing in sensor networks; and our simulation results show that our schemes can reduce the total communication cost by up to 90%, compared with the centralized scheme or a straightforward extension from previous top-k algorithm on one-dimensional sensor data.(3)An Efficient Data Collection Approach (EDCA) based on recent matrix completion techniques for data query is proposed in this thesis. In our method, energy consumption significantly decreases because the sampling rate is reduced and thus fewer packets are transmitted. To do so, we randomly select a portion of nodes from the whole sensor network to sample at each time instance and directly forward the data to the Sink. To recover the data precisely, a rank minimization problem, which is NP-hard, is transferred to a convex optimization one. Experimental results demonstrate that the recovery error is quite small and EDCA substantially outperforms the existing centralized exact method in both energy consumption and lifetime.(4) STCDG is introduced in this thesis, which is an energy efficient data gathering method for uniform or arbitrary sensor networks with predetermined working schedules by utilizing the low rank and short term stability of data matrix. The proposed method is able to reduce overall system communication cost and prolong the network life span with controllable errors, without introducing intensive computation or complicated transmission control. Besides, we prove that the network transmission can achieve high capacity. The errors of our approach have been validated through MATLAB simulations of recovery on real and synthetic traces. The network transmission latency and drop rate have been proved by NS2 simulation on grid topology. Furthermore, we propose a synchronized TDMA link scheduling optimization scheme and verify its effectiveness through the networking latency examination on grid and random topology using MATLAB. The results show that the energy efficiency and transmission capacity of the proposed scheme outperforms centralized exact and CDG.The achievements of the dissertation can be used to promote the development of retrieval technologies in wireless sensor networks.