Research On High Efficient Data Delivery In Wireless Sensor Networks

Wireless sensor networks (WSNs) are integrated networks which can perform information gathering, processing and delivering. There are wide applications for WSNs in industry, agriculture, military affairs, environment monitoring, biomedicine, city managing and disaster succoring. As a basic issue in WSNs, data delivery determines how control packets are disseminated to sources and how data packets are gathered to sink through multi-hop routing. Moreover, high efficient data delivery determines the performance and energy efficiency in WSNs. The goal of high efficient data delivery is to bridge source and sink, so that they can exchange valid information with the least transimission cost and delay. However, WSNs are resource-constrained, bandwidth-constrained and of large scale, which bring us great challenges to achieve high efficient data delivery.High efficient data delivery in WSNs includes two main parts: high efficient data dissemination from sink to source and high efficient data gathering from source to sink. Recent works recently mainly focus on utilizing traditional techniques, such as unicast, broadcast and aggregation. Those works almost all suffer high transmission cost, high delay and poor scalability. Aiming at the inherent characteristics of WSN and the limitation of current works, this thesis studies four key problems on data dissemination and gathering comprehensively to minimize the total transmission cost: (1) multicast from sink to source; (2) sampling from sink to source; (3) aggregation of emergent packets from source to sink; (4) two directional data coordiantions between sink and source, data storge and query.This paper studies the multicast from sink to source to disseminate control information. Aiming at the high communication cost, energy inefficiency and poor scalability, we first propose a base-station model-based multicast protocol, SenCast, to decrease the transmission cost and delay. SenCast can compute an approximately multicast tree globally to route the multicast packets because sink owns more powerful CPU and larger storage. By introducing an MNN (Minimum Nonleaf Nodes) Steiner tree problem which is NP-hard, SenCast builds an MNN multicast tree using a global approximation algorithm. Theoretical analysis shows that SenCast is able to approximate the MNN problem to a ratio of ln|R| (R is the set of all destinations), the best known lowest bound. Consequently, the multicast traffic can be decreased significantly. We further design two scalable schemes, SRL and HLB which compress the multicast tree information and deliver the multicast messages without information loss. Experimental results demonstrate that SenCast is a scalable and energy efficient multicast protocol when the scale of WSN or the number of destination nodes is large.Efficient estimation of global information is a common requirement for many WSN applications. Aiming at the high communication cost and delay of recent works, we develop a novel protocol called FLAKE that can efficiently and accurately estimate the global information of large-scale sensor networks based on the fast release/capture sampling. As an example, we outline the basic idea of estimating the number of nodes alive in a large sensor network. We first uniformly disseminate m messages called seeds into the network, which is referred to as seed release. Then a small number of nodes (say m) are queried about whether they have received a seed, which is referred to as seed capture. Suppose the number of seeds received by the n'nodes is m'. The total number of alive nodes in the network can be estimated as mn'/m'. The similar idea can be easily applied to capture other global information of a network. Moreover, to reduce the number of nodes to query in seed capture, FLAKE is based on the inverse sampling theory. Specifically, a query is injected into the network to count the number of seeds. The query process stops immediately after the total of number of seeds found reaches a given threshold. Our analysis show that, by controlling the number of seeds to release and capture, a desirable trade-off between the accuracy of information and the communication overhead can be achieved. To implement the aforementioned idea, FLAKE employs a distributed sparese sampling algorithm that adaptively expands the branches of seed dissemination based on neighborhood sizes. The algorithm can effectively lower the delay of seed release and achieve the global information within the accuracy bound. Our theoretical analysis and simulations show that FLAKE significantly outperforms several existing schemes on message overhead, delay and scalability.Works in WSNs recently seldom use the differentiated services, priority based packets classification and scheduling method, which causes large overhead and poor delay of packets transimission when bursty events happen. The cluster-based data aggregation has emerged as a basic and general technique in WSNs. However, there is a trade-off issue between aggregation waiting (AW) delay and aggregation accuracy. Therefore, we propose a DSFC model to solve the trade-off issue. Morevoer, we present a new inter-cluster congestion avoidance mechanism, EPCR to accelerate the transmission of emergent packets in the inter-cluster routing. We try to find the optimal point for the trade-off between AW delay and accuracy. That is to decrease AW delay as much as possible within the accuracy bound. In this paper, a distinguished feedback control model is proposed to adaptively aggregate partial data in a delay sensitive manner while not damage the gathering accuracy. EPCR differentiates packets with different priority and adopts a method of channel reservation to avoid inter-cluster congestion and accelerate the transmission of emergent packets. EPCR builds a fast end-to-end path for emergent packets which alleviates the congestion between emergent packets and regular packets. Simulation results verify the performance of DSFC and EPCR, and demonstrate their attractions in accuracy, real-time, energy efficiency and ratio of packets loss. Storage and query are also important problems in WSNs. There are unstructured and structured methods to solve the problem. While the structured methods need an index or hash function to get the locations of replicas beforehand. There are some problems on structured methods, such as high delay, hot spot on popular data, and long stretch. Contrarily, unstructured methods need not know where the replicas are, or need not any storage structure and index. It is more simple and flexible. But a few unstructured methods mainly focus on theory and are not energy efficient. In this work, we focus on unstructured random data storage and query. Since the energy is one of the most precious resources, we formulate an MESQ optimization problem whose aim is to select the optimum number of replicas and queries that minimize the total energy cost, (d, q), subject to unrestrained or restrained storage. In order to make our works more practical, we also design a localized data dissemination algorithm, BubbleGeocast. BubbleGeocast uses (d, q) as parameters and branch adaptively to diffuse data replicas and queries as soon as possible based on vitual multicast tree. We show by theoretical analysis and simulations that our BubbleGeocast achieves the distinguished performance on energy efficiency and delay, within the bound of successful query.In summary, aiming at scalability, less transmission cost and delay on high efficient data dissemination and gathering, our works present solutions to several key problems of multicast, sparese sampling, aggregation in clustered networks and unstructured storage and query, which have academic and practical value for advancing the theory and practicability of high efficient data delavery in WSNs.