Data Collection And Query Processing Techniques For Wireless Sensor Networks

Wireless sensor networks (WSNs) composed of micro sensor nodes greatly extendthe ability for human-beings to feel the physical world, and therefore have wide applica-tions and receive much concern from the research communities. However, the attributesof a WSN including limited-resources, self-organization, and robustlessness brings manydifficulties in data collection and query processing in a WSN. First, the limited energy isa big problem in deploying a WSN for long-term use, while there are often long-distancedata transmissions and high data rates in large-scal WSNs. The above two factors severlyaffect the lifetime of a WSN by greatly increasing the energy consumption rates of thenodes. Therefore, how to extend the network lifetime in data collection and aggregationbecomes the first challenge. Second, the objects that the user concerns are not alwaysthe same as the sensing objects, and the users may be interested in useful informationand knowledge hidden in the original data. It is an important way to execute in-networkexecutions rather than sending all the original data to the sink. Because the limited com-puting and storage resources on a node, new query type and query processing becomesthe second challenge. Finally, since WSN has many dynamic attributes, the reliability ofdata collection and query processing is less than that in other ad-hoc networks. How toimprove network reliability in these applications becomes the third challenge. To addressthe above three challenges, optimization techniques and algorithms are presented for datacollection and query processing in a WSN. The main contributions of this dissertation arelisted as follows.First, optimization strategies are proposed for prolonging the network lifetimes ofa data-gathering network and a network with many-to-many aggregation, resp. (1) theproblem of maximizing the lifetime of a data-gathering sensor network is studied, whichis defined as the number of rounds until the first node depletes its energy. The prob-lem is proved as NP-Complete, and then it is formulated as an integer program to getclose to optimality. Furthermore, a polynomial-time and provably near optimal algo-rithm is proposed to reduce the tremendous computation and storage cost of the integerprogram.Finally, the efficiency of the algorithms is evaluated by extensive experiments.(2) the problem of how to generate energy efficient aggregation plans to optimize many- to-many aggregation in WSNs is studied, which involves a many-to-many relationshipbetween the nodes providing data and the nodes requiring data. The problem is shown asNP-Complete considering both routing and aggregation choices, and three approximationalgorithms for two special cases and the general case of the problem are presented. Byutilizing the approximation algorithms for the minimal Steiner tree, approximation ratioson the energy cost of the generated plan against optimal plans are provided.Second, query processing methods and optimization strategies are proposed to en-able two new queries in WSNs, which are peak region query and pr-skyline query. (1)given a radius R, peak region queries return the extreme value of all the disk regionswith radius R in the sensor network. The value of a disk region is defined as an aggre-gation of the readings of all the sensors in it. A novel distributed approach EXQ that notonly reduces the energy cost but also balances the workload of the sensors is proposed.The energy efficiency and load balance between EXQ and the centralized approach arecompared analytically and experimentally. (2) the Pr-Skyline problem is investigated,i.e., how to compute the skyline with the highest existence probability in a computationaland energy-efficient way. The problem is formulated and proved, and the results showthat it is NP-Complete and cannot be approximated in a given expression. However,the proposed algorithm SKY-SEARCH with pruning techniques can guarantee the com-putational efficiency given relatively large input size, while the filter-based distributedoptimization strategy significantly reduces the transmission cost and the required storagespace of the sensor nodes. Extensive experiments verify the efficiency and scalability ofSKY-SEARCH and the distributed optimizing strategy.Third, optimization strategies are proposed aiming at improving the robustness ofquery processing. (1) A distributed algorithm CVD to identify cut vertices in a WSN isproposed. The algorithm travels the nodes of a network in parallel, colors the edges basedon the interval-coded spanning tree, and then determines the cut vertices by countingthe edge colors. The parallel style of the algorithm significantly reduces the time delay.Further more, optimization strategies based on interval coding are proposed to reduce thecommunication cost of the algorithm. The correctness of the algorithm is proved and itsperformance is analyzed theoretically, and both the simulation results and the experimentson real sensor networks show that the algorithm outperforms previous algorithms withlower communication cost and shorter time delay. (2) The load balancing problem for multiple tasks in a low-duty-cycled WSN is proposed, it is proved as NP-Complete ingeneral network graphs. Two efficient scheduling algorithms to achieve load balance areproposed and analyzed. Furthermore, a task scheduling protocol is designed relying onthe proposed algorithms. The simulation results show that the proposed algorithms greatlyimprove the network performance in most scenarios.