Adaptive Data Storage And KNN Query Processing In Wireless Sensor Networks

Wireless sensor networks(WSNs) have become an extremely popular topic,which receive great attention from micro-electronics,communication,network and database research communities due to their promising applications.By integrating sensing,data processing, and communication abilities,WSNs provide the users with massive data in the fashion of data-centric networks.Data storage and query processing are two important research issues in WSNs.Data storage in WSNs deals with two problems:where the data is stored in the network, and how queries are routed to the stored data.It involves the producers(such as sensor nodes) storing a large amount of data that they have collected and the consumers(e.g.base stations, users,and nodes) then issuing data requests,kNN query processing in WSNs is to search the k nearest neighbors(sensors or sensed values) in the networks.This thesis studies adaptive data storage and value-based kNN query processing in WSNs,major contributions are as follows.1.Adaptive data storage in WSNs with only one storage position(or node) is addressed. We formalize the data storage problem into three scenarios:o'ne-to-one(one producer and one consumer),many-to-one(m producers and one consumer),and many-to-many (m producers and n consumers).We propose two approaches to determine the storage position(s) based on the data rates of producers and the query rates of consumers. The optimal data storage(ODS) approach produces the global optimal data storage position (s);the near-optimal data storage(NDS) approach,an approximate scheme,can greatly reduce computational overhead while achieving local optimal position(s).An optimal data transmission scheme is also developed.Experimental results show that NDS not only reduces substantially computational cost but also performs as effective and efficient as ODS in over 70%of tested cases.2.Adaptive data storage in WSNs with multiple storage positions(or nodes) is investigated. We analyze the costs of data storage and query processing,and investigate the problem in both tree and mesh topological networks.In tree topologies,we explore deterministic data placement and present an optimal data storage method based on dynamic programming.In mesh topologies,we formulate the data storage nodes selection problem as nodes clustering and propose a clustering-based distributed data storage strategy (CBDS) that can adjust the storage nodes adaptively to minimize the energy dissipation in the networks.We develop three algorithms for sensor nodes clustering.Extensive experiments are conducted to evaluate the performance of the proposed approaches and find that CBDS demonstrates substantial performance advantage over two existing approaches.3.Value-based kNN queries evaluation in WSNs is studied.We study in-network query processing mechanisms for snapshot and continuous value-based kNN queries respectively. For snapshot queries,we propose a hash mapping approach,named h-kNN,which exploits a locality-preserving geographic hash.For continuous queries,a filter-based approach f-kNN and a clustering-based approach c-kNN are proposed,f-kNN significantly reduces the cost by setting filter for each node in the networks,c-kNN takes advantage of the spatial-temporal property of WSNs that the data sensed in two consecutive rounds and nearby nodes will not deviate too much,and utilizes clustering analysis to find the data storage nodes.We evaluate the performance of these approaches,experimental results illustrate that the three proposed approaches outperform the naive approach by cutting down energy consumption significantly.