Continuous aggregation is usually required in many sensor applications to obtain the temporal variation information of aggregates. However, in a hostile environment, the adversary could fabricate false temporal variation patterns of the aggregates by manipulating a series of aggregation results through compromised nodes. Existing secure aggregation schemes conduct one individual verification for each aggregation result, which could incur great accumulative communication cost and negative impact on transmission scheduling for continuous aggregation. In this paper, we identify distinct design issues for protecting continuous in-network aggregation and propose a novel scheme to detect false temporal variation patterns. Compared with the existing schemes, our scheme greatly reduces the verification cost by checking only a small part of aggregation results to verify the correctness of the temporal variation patterns in a time window. A sampling-based approach is used to check the aggregation results, which enables our scheme independent of any particular in-network aggregation protocols as opposed to existing schemes. We also propose a series of security mechanisms to protect the sampling process. Both theoretical analysis and simulations show the effectiveness and efficiency of our scheme.

When monitoring environments with wireless sensor networks, optimal sensor deployment is a fundamental issue and an effective means to achieve desired performance. Selecting best sensor deployment has a dependence on the deployment environments. Existing works address sensor deployment within three types of environments including one dimensional line, 2-D field and 3-D space. However, in many applications the deployment environments usually have network structures, which cannot be simply classified as the three types. The deployed locations and communications of sensor nodes are limited onto the network edges, which make the deployment problem distinct from that in other types of environments. In this paper, we study sensor deployment in network-structured environments and aim to achieve k-coverage while minimizing the number of sensor nodes. Furthermore, we jointly consider the optimization of sink deployment and routing strategies with the goal to minimize the network communication cost of data collection. To the best of our knowledge, this paper is the first one to tackle sensor/sink deployment under the deployment constraints imposed by the network structure. The hardness of the problems is shown. Polynomial-time algorithms are proposed to determine optimal sensor/sink deployment and routing strategies in tree-topology network structure. Efficient approximation algorithms are proposed for the general graph network structure and their performances are analyzed. Theoretical results and extensive simulations show the efficiency of the proposed algorithms.

In wireless sensor networks, the adversary may inject false reports to exhaust network energy or trigger false alarms with compromised sensor nodes. In response to the problems of existing schemes on the security resiliency, applicability and filtering effectiveness, this paper proposes a scheme, referred to as Grouping-enhanced Resilient Probabilistic En-route Filtering (GRPEF). In GRPEF, an efficient distributed algorithm is proposed to group nodes without incurring extra groups, and a multiaxis division based approach for deriving location-aware keys is used to overcome the threshold problem and remove the dependence on the sink immobility and routing protocols. Compared to the existing schemes, GRPEF significantly improves the effectiveness of the en-route filtering and can be applied to the sensor networks with mobile sinks while reserving the resiliency.

Data collection is a fundamental task in wireless sensor networks. In many applications of wireless sensor networks, approximate data collection is a wise choice due to the constraints in communication bandwidth and energy budget. In this paper, we focus on efficient approximate data collection with prespecified error bounds in wireless sensor networks. The key idea of our data collection approach ADC (Approximate Data Collection) is to divide a sensor network into clusters, discover local data correlations on each cluster head, and perform global approximate data collection on the sink node according to model parameters uploaded by cluster heads. Specifically, we propose a local estimation model to approximate the readings of sensor nodes in subsets, and prove rated error-bounds of data collection using this model. In the process of model-based data collection, we formulate the problem of selecting the minimum subset of sensor nodes into a minimum dominating set problem which is known to be NP-hard, and propose a greedy heuristic algorithm to find an approximate solution. We further propose a monitoring algorithm to adaptively adjust the composition of node subsets according to changes of sensor readings. Our trace-driven simulations demonstrate that ADC remarkably reduces communication cost of data collection with guaranteed error bounds.

For energy conservation, a wireless sensor network is usually designed to work in a low-duty-cycle mode, in which a sensor node keeps active for a small percentage of time during its working period. In applications where there are multiple data delivery tasks with high data rates and time constraints, low-duty-cycle working mode may cause severe transmission congestion and data loss. In order to alleviate congestion and reduce data loss, the tasks need to be carefully scheduled to balance the workloads among the sensor nodes in both spatial and temporal dimensions. This paper studies the load balancing problem, and proves it is NP-Complete in general network graphs. Two efficient scheduling algorithms to achieve load balance are proposed and analyzed. Furthermore, a task scheduling protocol is designed relying on the proposed algorithms. To the best of our knowledge, this paper is the first one to tackle multiple task scheduling for low-duty-cycled sensor networks. The simulation results show that the proposed algorithms greatly improve the network performance in most scenarios.

In-network aggregation provides an energy-efficient way to extract summarization information from sensor networks. Continuous aggregation is usually required in many sensor applications to obtain the temporal variation information of some interesting aggregates. However, for the continuous in-network aggregation in a hostile environment, the adversary could manipulate a series of aggregation results through compromised nodes to fabricate false temporal variation patterns of the aggregates. Existing secure aggregation schemes conduct one individual verification for each aggregation result. Due to the high rate and the long period of a continuous aggregation, directly applying these schemes to detect false temporal variation pattern would incur a great communication cost. In this paper, we identify distinct design issues for protecting continuous in-network aggregation and propose a novel scheme to detect false temporal variation patterns. Compared with the existing schemes, our scheme greatly reduces the communication cost by selecting and checking only a small part of aggregation results to verify the correctness of the temporal variation patterns in a time window. The checking of the aggregation results uses a sampling-based approach, which enables our scheme independent of any particular in-network aggregation protocol. We also propose a series of security mechanisms to protect the sampling process. Both theoretical analysis and simulations show the effectiveness and efficiency of our scheme.

Due to lack of precise control on network topology, cut vertices often exist in wireless sensor networks (WSNs). A cut vertex is defined as a sensor node whose removal breaks network connectivity. Failures of such nodes make a network disconnected and block data transmission, hence it is vital to detect cut vertices in WSNs. This paper proposes a distributed algorithm CVD to identify cut vertices. The algorithm travels the nodes of a network in parallel, colors the edges based on the interval-coded spanning tree, and then determines the cut vertices by counting the 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 the communication cost of the algorithm. The correctness of the algorithm is proved and its performance is analyzed theoretically. Theoretical analysis shows that it requires O (dn) communication cost and has O (dn) time delay, where n is the number of nodes in a WSN, and d is the maximum degree of sensor node. Both the simulation results and the experiments on real sensor networks show that the algorithm outperforms previous algorithms with lower communication cost and shorter time delay.

Data collection is a fundamental issue in wireless sensor networks. In many application scenarios for sensor networks, approximate data collection is a wise choice due to the constraints in communication bandwidth and energy budget. In this paper, we focus on efficient approximate data collection with given error bounds in wireless sensor networks. The key idea of our data collection approach ADC (Approximate Data Collection) is to divide a sensor network into clusters, discover local data correlations on each cluster head, and perform a global approximate data collection on the sink according to model parameters uploaded by cluster heads. Specifically, we propose a local estimation model to approximate the readings of several subsets of sensor nodes, and prove rated error-bounds of data collection using this model. In the process of model-based data collection, we formulate the problem of selecting the minimum subset of sensor nodes into a minimum dominating set problem which is known to be NP-hard, and use a greedy heuristic algorithm to find an approximate solution. We also propose a monitoring algorithm to adjust these subsets according to the changes of sensor readings. Our trace-driving simulation results show that our data collection approach ADC can notably reduce the communication cost with given error bounds.

A wireless sensor network is often deployed for environment monitoring and event inspection. Among these applications, the sink of the network usually requires the data generated on each sensor node periodically, and such a network is called a data-gathering sensor network. In each round of the data gathering process, a sensor node sends its reading via a single-hop or multi-hop path to the sink. Because the sensor nodes are usually battery-powered with limited energy, efficient routing strategy is required to reduce and balance the energy consumption of the sensor nodes in data transmission. This paper studies the problem of maximizing the lifetime of a data-gathering sensor network, which is defined as the number of rounds until the first node depletes its energy. We prove that the problem is NP-complete, and then formulate it as an integer program to get close to optimality. We further propose a polynomial-time and provably near optimal algorithm to reduce the tremendous computation and storage cost of the integer program. Finally, we evaluate the efficiency of our algorithms by extensive experiments.