Data-aggregation techniques in sensor networks: a survey
---
paper_title: Directed diffusion: a scalable and robust communication paradigm for sensor networks

paper_content:

Advances in processor, memory and radio technology will enable small and cheap nodes capable of sensing, communication and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. In this paper, we explore the directed diffusion paradigm for such coordination. Directed diffusion is datacentric in that all communication is for named data. All nodes in a directed diffusion-based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network. We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network.
---
paper_title: Application-specific modelling of information routing in wireless sensor networks

paper_content:

Sensor network applications have a diverse set of requirements - some involve extraction of sensor data to a single point, others exploit sensor-to-sensor communication; some employ long-lasting data streams while connections in others are mainly ephemeral. Different variants of the directed diffusion routing protocol - pull-based, push-based and hybrid rendezvous-based - have been developed, along with in-network processing and geographic routing techniques. We mathematically model and analyze the performance of these routing techniques across a range of application scenarios (with varying numbers of nodes, sources, sinks, data settings etc.). Besides quantifying the conditions under which the different routing algorithms outperform each other, we obtain a number of useful design insights. Our analysis shows that algorithms mismatched to applications can result in drastically poor performance; demonstrates the desirability of reducing flooded interest and exploratory messages when data aggregation is used; and suggests that it may be difficult to implement efficient hybrid schemes because their performance is very sensitive to the optimal placement of rendezvous points.
---
paper_title: Power efficient data gathering and aggregation in wireless sensor networks

paper_content:

Recent developments in processor, memory and radio technology have enabled wireless sensor networks which are deployed to collect useful information from an area of interest. The sensed data must be gathered and transmitted to a base station where it is further processed for end-user queries. Since the network consists of low-cost nodes with limited battery power, power efficient methods must be employed for data gathering and aggregation in order to achieve long network lifetimes.In an environment where in a round of communication each of the sensor nodes has data to send to a base station, it is important to minimize the total energy consumed by the system in a round so that the system lifetime is maximized. With the use of data fusion and aggregation techniques, while minimizing the total energy per round, if power consumption per node can be balanced as well, a near optimal data gathering and routing scheme can be achieved in terms of network lifetime.So far, besides the conventional protocol of direct transmission, two elegant protocols called LEACH and PEGASIS have been proposed to maximize the lifetime of a sensor network. In this paper, we propose two new algorithms under name PEDAP (Power Efficient Data gathering and Aggregation Protocol), which are near optimal minimum spanning tree based routing schemes, where one of them is the power-aware version of the other. Our simulation results show that our algorithms perform well both in systems where base station is far away from and where it is in the center of the field. PEDAP achieves between 4x to 20x improvement in network lifetime compared with LEACH, and about three times improvement compared with PEGASIS.
---
paper_title: Aggregation tree construction in sensor networks

paper_content:

Large-scale wireless sensor networks are expected to play an increasingly important role in future civilian and military settings. Collaborative microsensors could be very effective in monitoring their operations. However, low power and in-network data processing make data-centric routing in wireless sensor networks a challenging problem. In this paper we propose heuristics to construct and maintain an aggregation tree in sensor networks. This aggregation tree can be used to facilitate data-centric routing. The main idea is to turn off the radio of all leaf nodes to save power, and thereby extending the network lifetime. Therefore, in order to save the number of broadcasting messages, only the nonleaf nodes in the tree are in charge of data aggregation and traffic relaying. In this paper, we propose an efficient energy-aware distributed heuristic to generate the aggregation tree, which we refer to as EADAT. Our EADAT algorithm makes no assumption on local network topology, and is based on residual power. It makes use of neighboring broadcast scheduling and distributed competition among neighbors. These novel concepts make EADAT very efficient and effective, as demonstrated by our simulation experiments with NS2.
---
paper_title: An application-specific protocol architecture for wireless microsensor networks

paper_content:

Networking together hundreds or thousands of cheap microsensor nodes allows users to accurately monitor a remote environment by intelligently combining the data from the individual nodes. These networks require robust wireless communication protocols that are energy efficient and provide low latency. We develop and analyze low-energy adaptive clustering hierarchy (LEACH), a protocol architecture for microsensor networks that combines the ideas of energy-efficient cluster-based routing and media access together with application-specific data aggregation to achieve good performance in terms of system lifetime, latency, and application-perceived quality. LEACH includes a new, distributed cluster formation technique that enables self-organization of large numbers of nodes, algorithms for adapting clusters and rotating cluster head positions to evenly distribute the energy load among all the nodes, and techniques to enable distributed signal processing to save communication resources. Our results show that LEACH can improve system lifetime by an order of magnitude compared with general-purpose multihop approaches.
---
paper_title: Negotiation-based Protocols for Disseminating Information in Wireless Sensor Networks

paper_content:

In this paper, we present a family of adaptive protocols, called SPIN (Sensor Protocols for Information via Negotiation), that efficiently disseminate information among sensors in an energy-constrained wireless sensor network. Nodes running a SPIN communication protocol name their data using high-level data descriptors, called meta-data. They use meta-data negotiations to eliminate the transmission of redundant data throughout the network. In addition, SPIN nodes can base their communication decisions both upon application-specific knowledge of the data and upon knowledge of the resources that are available to them. This allows the sensors to efficiently distribute data given a limited energy supply. We simulate and analyze the performance of four specific SPIN protocols: SPIN-PP and SPIN-EC, which are optimized for a point-to-point network, and SPIN-BC and SPIN-RL, which are optimized for a broadcast network. Comparing the SPIN protocols to other possible approaches, we find that the SPIN protocols can deliver 60% more data for a given amount of energy than conventional approaches in a point-to-point network and 80% more data for a given amount of energy in a broadcast network. We also find that, in terms of dissemination rate and energy usage, the SPIN protocols perform close to the theoretical optimum in both point-to-point and broadcast networks.
---
paper_title: A Dynamic Data Aggregation Scheme for Wireless Sensor Networks

paper_content:

Wireless sensor networks are formed of tiny, energy-constrained sensor nodes that could be mobile and may be deployed in unfamiliar environments in large numbers. Considering these unique characteristics, our network architecture is modelled around a data-centric approach that allows us to make use of in-network processing and data aggregation which in turn helps to maximize network lifetime. This paper suggests methods to improve network efficiency by combining Directed Diffusion [2] with clustering and by introducing a more elaborate data aggregation scheme. Our data aggregation scheme allows nodes to ::: process data collected from sensors and subsequently aggregate the data even in completely unfamiliar environments by including entire query definitions within interest messages. We also describe certain novel design features such as interest transformation, layered data aggregation and dynamic data aggregation points all of which would improve overall system performance.
---
paper_title: Application-Specific Protocol Architectures for Wireless Networks

paper_content:

In recent years, advances in energy-efficient design and wireless technologies have enabled exciting new applications for wireless devices. These applications span a wide range, including real-time and streaming video and audio delivery, remote monitoring using networked microsensors, personal medical monitoring, and home networking of everyday appliances. While these applications require high performance from the network, they suffer from resource constraints that do not appear in more traditional wired computing environments. In particular, wireless spectrum is scarce, often limiting the bandwidth available to applications and making the channel error-prone, and the nodes are battery-operated, often limiting available energy. ::: My thesis is that this harsh environment with severe resource constraints requires an application-specific protocol architecture, rather than the traditional layered approach, to obtain the best possible performance. This dissertation supports this claim using detailed case studies on microsensor networks and wireless video delivery. The first study develops LEACH (Low-Energy Adaptive Clustering Hierarchy), an architecture for remote microsensor networks that combines the ideas of energy-efficient cluster-based routing and media access together with application-specific data aggregation to achieve good performance in terms of system lifetime, latency, and application-perceived quality. This approach improves system lifetime by an order of magnitude compared to general-purpose approaches when the node energy is limited. The second study develops an unequal error protection scheme for MPEG-4 compressed video delivery that adapts the level of protection applied to portions of a packet to the degree of importance of the corresponding bits. This approach obtains better application-perceived performance than current approaches for the same amount of transmission bandwidth. These two systems show that application-specific protocol architectures achieve the energy and latency efficiency and error robustness needed for wireless networks. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)
---
paper_title: Chain-based protocols for data broadcasting and gathering in the sensor networks

paper_content:

In wireless sensor networks, the sensor nodes gather information and send the information to a base station periodically. Some important messages need to be broadcasted to all nodes. Data gathering and broadcasting are important operations that consume significant amounts of battery power. Due to the limited battery life, energy efficiency is becoming a major challenging problem in these power-constrained networks. Chain-based protocols construct a transmission chain connecting all nodes to save energy dissipation of data transmission. In this paper, we first review several existing chain-based protocols. We then present our multiple-chain scheme which outperforms the existing ones in the sparse-node distribution case. Furthermore, we develop an energy-efficient chain construction algorithm which uses a sequence of insertions to add the least amount of energy consumption to the whole chain. It consumes less transmission power compared to the closest neighbor algorithm.
---
paper_title: The impact of data aggregation in wireless sensor networks

paper_content:

Sensor networks are distributed event-based systems that differ from traditional communication networks in several ways: sensor networks have severe energy constraints, redundant low-rate data, and many-to-one flows. Data-centric mechanisms that perform in-network aggregation of data are needed in this setting for energy-efficient information flow. In this paper we model data-centric routing and compare its performance with traditional end-to-end routing schemes. We examine the impact of source-destination placement and communication network density on the energy costs and delay associated with data aggregation. We show that data-centric routing offers significant performance gains across a wide range of operational scenarios. We also examine the complexity of optimal data aggregation, showing that although it is an NP-hard problem in general, there exist useful polynomial-time special cases.
---
paper_title: HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks

paper_content:

Topology control in a sensor network balances load on sensor nodes and increases network scalability and lifetime. Clustering sensor nodes is an effective topology control approach. In this paper, we propose a novel distributed clustering approach for long-lived ad hoc sensor networks. Our proposed approach does not make any assumptions about the presence of infrastructure or about node capabilities, other than the availability of multiple power levels in sensor nodes. We present a protocol, HEED (Hybrid Energy-Efficient Distributed clustering), that periodically selects cluster heads according to a hybrid of the node residual energy and a secondary parameter, such as node proximity to its neighbors or node degree. HEED terminates in O(1) iterations, incurs low message overhead, and achieves fairly uniform cluster head distribution across the network. We prove that, with appropriate bounds on node density and intracluster and intercluster transmission ranges, HEED can asymptotically almost surely guarantee connectivity of clustered networks. Simulation results demonstrate that our proposed approach is effective in prolonging the network lifetime and supporting scalable data aggregation.
---
paper_title: Power efficient data gathering and aggregation in wireless sensor networks

paper_content:

Recent developments in processor, memory and radio technology have enabled wireless sensor networks which are deployed to collect useful information from an area of interest. The sensed data must be gathered and transmitted to a base station where it is further processed for end-user queries. Since the network consists of low-cost nodes with limited battery power, power efficient methods must be employed for data gathering and aggregation in order to achieve long network lifetimes.In an environment where in a round of communication each of the sensor nodes has data to send to a base station, it is important to minimize the total energy consumed by the system in a round so that the system lifetime is maximized. With the use of data fusion and aggregation techniques, while minimizing the total energy per round, if power consumption per node can be balanced as well, a near optimal data gathering and routing scheme can be achieved in terms of network lifetime.So far, besides the conventional protocol of direct transmission, two elegant protocols called LEACH and PEGASIS have been proposed to maximize the lifetime of a sensor network. In this paper, we propose two new algorithms under name PEDAP (Power Efficient Data gathering and Aggregation Protocol), which are near optimal minimum spanning tree based routing schemes, where one of them is the power-aware version of the other. Our simulation results show that our algorithms perform well both in systems where base station is far away from and where it is in the center of the field. PEDAP achieves between 4x to 20x improvement in network lifetime compared with LEACH, and about three times improvement compared with PEGASIS.
---
paper_title: Efficient Algorithms for Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks

paper_content:

The rapid advances in processor, memory, and radio technology have enabled the development of distributed networks of small, inexpensive nodes that are capable of sensing, computation, and wireless communication. Sensor networks of the future are envisioned to revolutionize the paradigm of collecting and processing information in diverse environments. However, the severe energy constraints and limited computing resources of the sensors, present major challenges for such a vision to become a reality.We consider a network of energy-constrained sensors that are deployed over a region. Each sensor periodically produces information as it monitors its vicinity. The basic operation in such a network is the systematic gathering and transmission of sensed data to a base station for further processing. During data gathering, sensors have the ability to perform in-network aggregation (fusion) of data packets enroute to the base station. The lifetime of such a sensor system is the time during which we can gather information from all the sensors to the base station. A key challenge in data gathering is to maximize the system lifetime, given the energy constraints of the sensors.Given the location of n sensors and a base station together with the available energy at each sensor, we are interested in finding an efficient manner in which data should be collected from all the sensors and transmitted to the base station, such that the system lifetime is maximized. This is the maximum lifetime data gathering problem. In this paper, we describe novel algorithms, with worst-case running times polynomial in n, to solve the data gathering problem with aggregation in sensor networks. Our experimental results demonstrate that the proposed algorithms significantly outperform previous methods in terms of system lifetime.
---
paper_title: On network correlated data gathering

paper_content:

We consider the problem of correlated data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. Two coding strategies are analyzed: a Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult. This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure. For the Slepian-Wolf setting, we derive a closed form solution and an efficient distributed approximation algorithm with a good performance. For the explicit communication case, we prove that building an optimal data gathering tree is NP-complete and we propose various distributed approximation algorithms.
---
paper_title: Optimal information extraction in energy-limited wireless sensor networks

paper_content:

The current practice in wireless sensor networks (WSNs) is to develop functional system designs and protocols for information extraction using intuition and heuristics, and validate them through simulations and implementations. We address the need for a complementary formal methodology by developing nonlinear optimization models of static WSN that yield fundamental performance bounds and optimal designs. We present models both for maximizing the total information gathered subject to energy constraints (on sensing, transmission, and reception), and for minimizing the energy usage subject to information constraints. Other constraints in these models correspond to fairness and channel capacity (assuming noise but no interference). We also discuss extensions of these models that can handle data aggregation, interference, and even node mobility. We present results and illustrations from computational experiments using these models that show how the optimal solution varies as a function of the energy/information constraints, network size, fairness constraints, and reception power. We also compare the performance of some simple heuristics with respect to the optimal solutions.
---
paper_title: Maximizing Data Extraction in Energy-Limited Sensor Networks

paper_content:

We examine the problem of maximizing data collection from an energy-limited store-and-extract wireless sensor network, which is analogous to the maximum lifetime problem of interest in continuous data-gathering sensor networks. One significant difference is that this problem requires attention to “data-awareness” in addition to “energy-awareness”. We formulate the maximum data extraction problem as a linear program and present a 1
---
paper_title: AIDA: Adaptive application-independent data aggregation in wireless sensor networks

paper_content:

Sensor networks, a novel paradigm in distributed wireless communication technology, have been proposed for various applications including military surveillance and environmental monitoring. These systems deploy heterogeneous collections of sensors capable of observing and reporting on various dynamic properties of their surroundings in a time sensitive manner. Such systems suffer bandwidth, energy, and throughput constraints that limit the quantity of information transferred from end-to-end. These factors coupled with unpredictable traffic patterns and dynamic network topologies make the task of designing optimal protocols for such networks difficult. Mechanisms to perform data-centric aggregation utilizing application-specific knowledge provide a means to augmenting throughput, but have limitations due to their lack of adaptation and reliance on application-specific decisions. We, therefore, propose a novel aggregation scheme that adaptively performs application-independent data aggregation in a time sensitive manner. Our work isolates aggregation decisions into a module that resides between the network and the data-link layer and does not require any modifications to the currently existing MAC and network layer protocols. We take advantage of queuing delay and the broadcast nature of wireless communication to concatenate network units into an aggregate using a novel adaptive feedback scheme to schedule the delivery of this aggregate to the MAC layer for transmission. In our evaluation we show that end-to-end transmission delay is reduced by as much as 80p under heavy traffic loads. Additionally, we show as much as a 50p reduction in transmission energy consumption with an overall reduction in header overhead. Theoretical analysis, simulation, and a test-bed implementation on Berkeley's MICA motes are provided to validate our claims.
---
paper_title: Efficient Algorithms for Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks

paper_content:

The rapid advances in processor, memory, and radio technology have enabled the development of distributed networks of small, inexpensive nodes that are capable of sensing, computation, and wireless communication. Sensor networks of the future are envisioned to revolutionize the paradigm of collecting and processing information in diverse environments. However, the severe energy constraints and limited computing resources of the sensors, present major challenges for such a vision to become a reality.We consider a network of energy-constrained sensors that are deployed over a region. Each sensor periodically produces information as it monitors its vicinity. The basic operation in such a network is the systematic gathering and transmission of sensed data to a base station for further processing. During data gathering, sensors have the ability to perform in-network aggregation (fusion) of data packets enroute to the base station. The lifetime of such a sensor system is the time during which we can gather information from all the sensors to the base station. A key challenge in data gathering is to maximize the system lifetime, given the energy constraints of the sensors.Given the location of n sensors and a base station together with the available energy at each sensor, we are interested in finding an efficient manner in which data should be collected from all the sensors and transmitted to the base station, such that the system lifetime is maximized. This is the maximum lifetime data gathering problem. In this paper, we describe novel algorithms, with worst-case running times polynomial in n, to solve the data gathering problem with aggregation in sensor networks. Our experimental results demonstrate that the proposed algorithms significantly outperform previous methods in terms of system lifetime.
---
paper_title: On network correlated data gathering

paper_content:

We consider the problem of correlated data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. Two coding strategies are analyzed: a Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult. This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure. For the Slepian-Wolf setting, we derive a closed form solution and an efficient distributed approximation algorithm with a good performance. For the explicit communication case, we prove that building an optimal data gathering tree is NP-complete and we propose various distributed approximation algorithms.
---
paper_title: in-network aggregation trade-offs for data collection in wireless sensor networks

paper_content:

This paper explores in-network aggregation as a power-efficient mechanism for collecting data in wireless sensor networks. In particular, we focus on sensor network scenarios where a large number of nodes produce data periodically. Such communication model is typical of monitoring applications, an important application domain sensor networks target. The main idea behind in-network aggregation is that, rather than sending individual data items from sensors to sinks, multiple data items are aggregated as they are forwarded by the sensor network. Through simulations, we evaluate the performance of different in-network aggregation algorithms, including our own cascading timers, in terms of the trade-offs between energy efficiency, data accuracy and freshness. Our results show that timing, that is, how long a node waits to receive data from its children (downstream nodes in respect to the information sink) before forwarding data onto the next hop (toward the sink) plays a crucial role in the performance of aggregation algorithms for applications that generate data periodically. By carefully selecting when to aggregate and forward data, cascading timers achieves considerable energy savings while maintaining data freshness and accuracy. We also study in-network aggregation's cost-efficiency using simple mathematical models. Since wireless sensor networks are prone to transmission errors and losses can have considerable impact when data aggregation is used, we also propose and evaluate a number of techniques for handling packet loss. Simulations show that, when used in conjunction with aggregation protocols, the proposed techniques can effectively mitigate the effects of random transmission losses in a power-efficient way.
---
paper_title: Energy-latency tradeoffs for data gathering in wireless sensor networks

paper_content:

We study the problem of scheduling packet transmissions for data gathering in wireless sensor networks. The focus is to explore the energy-latency tradeoffs in wireless communication using techniques such as modulation scaling. The data aggregation tree - a multiple-source single-sink communication paradigm - is employed for abstracting the packet flow. We consider a real-time scenario where the data gathering must be performed within a specified latency constraint. We present algorithms to minimize the overall energy dissipation of the sensor nodes in the aggregation tree subject to the latency constraint. For the off-line problem, we propose (a) a numerical algorithm for the optimal solution, and (h) a pseudo-polynomial time approximation algorithm based on dynamic programming. We also discuss techniques for handling interference among the sensor nodes. Simulations have been conducted for both long-range communication and short-range communication. The simulation results show that compared with the classic shutdown technique, between 20% to 90% energy savings can be achieved by our techniques, under different settings of several key system parameters. We also develop an on-line distributed protocol that relies only on the local information available at each sensor node within the aggregation tree. Simulation results show that between 15% to 90% energy conservation can be achieved by the on-line protocol. The adaptability of the protocol with respect to variations in the packet size and latency constraint is also demonstrated through several run-time scenarios.
---
paper_title: Aggregation in sensor networks: an energy-accuracy trade-off

paper_content:

Wireless ad hoc sensor networks (WASNs) are in need of the study of useful applications that will help the researchers view them as distributed physically coupled systems, a collective that estimates the physical environment, and not just energy-limited ad hoc networks. We develop this perspective using a large and interesting class of WASN applications called aggregation applications. In particular, we consider the challenging periodic aggregation problem where the WASN provides the user with periodic estimates of the environment, as opposed to simpler and previously studied snapshot aggregation problems. In periodic aggregation our approach allows the spatial-temporal correlation among values sensed at the various nodes to be exploited towards energy-efficient estimation of the aggregated value of interest. Our approach also creates a system level energy vs. accuracy knob whereby the more the estimation error that the user can tolerate, the less is the energy consumed. We present a distributed estimation algorithm that can be applied to explore the energy-accuracy subspace for a sub-class of periodic aggregation problems, and present extensive simulation results that validate our approach. The resulting algorithm, apart from being more flexible in the energy-accuracy subspace and more robust, can also bring considerable energy savings for a typical accuracy requirement (five-fold decrease in energy consumption for 5% estimation error) compared to repeated snapshot aggregations.
---
paper_title: Data-gathering wireless sensor networks: organization and capacity

paper_content:

In this paper we study the transport capacity of a data-gathering wireless sensor network under different communication organizations. In particular, we consider using a flat as well as a hierarchical/clustering architecture to realize many-to-one communications. The capacity of the network under this many-to-one data-gathering scenario is reduced compared to random one-to-one communication due to the unavoidable creation of a point of traffic concentration at the data collector/receiver. We introduce the overall throughput bound of λ = W/n per node, where W is the transmission capacity, and show under what conditions it can be achieved and under what conditions it cannot. When those conditions are not met, we constructively show how λ = Θ(W/n) is achieved with high probability as the number of sensors goes to infinity. We also show how the introduction of clustering can improve the throughput. We discuss the trade-offs between achieving capacity and energy consumption, how transport capacity might be affected by considering in-network processing and the implications this study has on the design of practical protocols for large-scale data-gathering wireless sensor networks.
---
paper_title: Data-gathering wireless sensor networks: organization and capacity

paper_content:

In this paper we study the transport capacity of a data-gathering wireless sensor network under different communication organizations. In particular, we consider using a flat as well as a hierarchical/clustering architecture to realize many-to-one communications. The capacity of the network under this many-to-one data-gathering scenario is reduced compared to random one-to-one communication due to the unavoidable creation of a point of traffic concentration at the data collector/receiver. We introduce the overall throughput bound of λ = W/n per node, where W is the transmission capacity, and show under what conditions it can be achieved and under what conditions it cannot. When those conditions are not met, we constructively show how λ = Θ(W/n) is achieved with high probability as the number of sensors goes to infinity. We also show how the introduction of clustering can improve the throughput. We discuss the trade-offs between achieving capacity and energy consumption, how transport capacity might be affected by considering in-network processing and the implications this study has on the design of practical protocols for large-scale data-gathering wireless sensor networks.
---
paper_title: CDA: concealed data aggregation for reverse multicast traffic in wireless sensor networks

paper_content:

End-to-end encryption for wireless sensor networks is a challenging problem. To save the overall energy resources of the network, it is agreed that sensed data need to be consolidated and aggregated on their way to the final destination. We present an approach that (1) conceals sensed data end-to-end, by (2) still providing efficient in-network data aggregation. The aggregating intermediate nodes are not required to operate on the sensed plaintext data. We apply a particular class of encryption transformation and exemplarily discuss the approach on the basis of two aggregation functions. We use actual implementation to show that the approach is feasible and flexible and frequently even more energy efficient than hop-by-hop encryption.
---
paper_title: SPINS: security protocols for sensor networks

paper_content:

As sensor networks edge closer towards wide-spread deployment, security issues become a central concern. So far, much research has focused on making sensor networks feasible and useful, and has not concentrated on security. We present a suite of security building blocks optimized for resource-constrained environments and wireless communication. SPINS has two secure building blocks: SNEP and μTESLA SNEP provides the following important baseline security primitives: Data confidentiality, two-party data authentication, and data freshness. A particularly hard problem is to provide efficient broadcast authentication, which is an important mechanism for sensor networks. μTESLA is a new protocol which provides authenticated broadcast for severely resource-constrained environments. We implemented the above protocols, and show that they are practical even on minimal hardware: the performance of the protocol suite easily matches the data rate of our network. Additionally, we demonstrate that the suite can be used for building higher level protocols.
---
paper_title: SIA: secure information aggregation in sensor networks

paper_content:

Sensor networks promise viable solutions to many monitoring problems. However, the practical deployment of sensor networks faces many challenges imposed by real-world demands. Sensor nodes often have limited computation and communication resources and battery power. Moreover, in many applications sensors are deployed in open environments, and hence are vulnerable to physical attacks, potentially compromising the sensor's cryptographic keys.One of the basic and indispensable functionalities of sensor networks is the ability to answer queries over the data acquired by the sensors. The resource constraints and security issues make designing mechanisms for information aggregation in large sensor networks particularly challenging.In this paper, we propose a novel framework for secure information aggregation in large sensor networks. In our framework certain nodes in the sensor network, called aggregators, help aggregating information requested by a query, which substantially reduces the communication overhead. By constructing efficient random sampling mechanisms and interactive proofs, we enable the user to verify that the answer given by the aggregator is a good approximation of the true value even when the aggregator and a fraction of the sensor nodes are corrupted. In particular, we present efficient protocols for secure computation of the median and the average of the measurements, for the estimation of the network size, and for finding the minimum and maximum sensor reading. Our protocols require only sublinear communication between the aggregator and the user. To the best of our knowledge, this paper is the first on secure information aggregation in sensor networks that can handle a malicious aggregator and sensor nodes.
---
paper_title: Aggregation in sensor networks: an energy-accuracy trade-off

paper_content:

Wireless ad hoc sensor networks (WASNs) are in need of the study of useful applications that will help the researchers view them as distributed physically coupled systems, a collective that estimates the physical environment, and not just energy-limited ad hoc networks. We develop this perspective using a large and interesting class of WASN applications called aggregation applications. In particular, we consider the challenging periodic aggregation problem where the WASN provides the user with periodic estimates of the environment, as opposed to simpler and previously studied snapshot aggregation problems. In periodic aggregation our approach allows the spatial-temporal correlation among values sensed at the various nodes to be exploited towards energy-efficient estimation of the aggregated value of interest. Our approach also creates a system level energy vs. accuracy knob whereby the more the estimation error that the user can tolerate, the less is the energy consumed. We present a distributed estimation algorithm that can be applied to explore the energy-accuracy subspace for a sub-class of periodic aggregation problems, and present extensive simulation results that validate our approach. The resulting algorithm, apart from being more flexible in the energy-accuracy subspace and more robust, can also bring considerable energy savings for a typical accuracy requirement (five-fold decrease in energy consumption for 5% estimation error) compared to repeated snapshot aggregations.
---
paper_title: in-network aggregation trade-offs for data collection in wireless sensor networks

paper_content:

This paper explores in-network aggregation as a power-efficient mechanism for collecting data in wireless sensor networks. In particular, we focus on sensor network scenarios where a large number of nodes produce data periodically. Such communication model is typical of monitoring applications, an important application domain sensor networks target. The main idea behind in-network aggregation is that, rather than sending individual data items from sensors to sinks, multiple data items are aggregated as they are forwarded by the sensor network. Through simulations, we evaluate the performance of different in-network aggregation algorithms, including our own cascading timers, in terms of the trade-offs between energy efficiency, data accuracy and freshness. Our results show that timing, that is, how long a node waits to receive data from its children (downstream nodes in respect to the information sink) before forwarding data onto the next hop (toward the sink) plays a crucial role in the performance of aggregation algorithms for applications that generate data periodically. By carefully selecting when to aggregate and forward data, cascading timers achieves considerable energy savings while maintaining data freshness and accuracy. We also study in-network aggregation's cost-efficiency using simple mathematical models. Since wireless sensor networks are prone to transmission errors and losses can have considerable impact when data aggregation is used, we also propose and evaluate a number of techniques for handling packet loss. Simulations show that, when used in conjunction with aggregation protocols, the proposed techniques can effectively mitigate the effects of random transmission losses in a power-efficient way.
---
paper_title: Energy-latency tradeoffs for data gathering in wireless sensor networks

paper_content:

We study the problem of scheduling packet transmissions for data gathering in wireless sensor networks. The focus is to explore the energy-latency tradeoffs in wireless communication using techniques such as modulation scaling. The data aggregation tree - a multiple-source single-sink communication paradigm - is employed for abstracting the packet flow. We consider a real-time scenario where the data gathering must be performed within a specified latency constraint. We present algorithms to minimize the overall energy dissipation of the sensor nodes in the aggregation tree subject to the latency constraint. For the off-line problem, we propose (a) a numerical algorithm for the optimal solution, and (h) a pseudo-polynomial time approximation algorithm based on dynamic programming. We also discuss techniques for handling interference among the sensor nodes. Simulations have been conducted for both long-range communication and short-range communication. The simulation results show that compared with the classic shutdown technique, between 20% to 90% energy savings can be achieved by our techniques, under different settings of several key system parameters. We also develop an on-line distributed protocol that relies only on the local information available at each sensor node within the aggregation tree. Simulation results show that between 15% to 90% energy conservation can be achieved by the on-line protocol. The adaptability of the protocol with respect to variations in the packet size and latency constraint is also demonstrated through several run-time scenarios.
---
paper_title: Data-gathering wireless sensor networks: organization and capacity

paper_content:

In this paper we study the transport capacity of a data-gathering wireless sensor network under different communication organizations. In particular, we consider using a flat as well as a hierarchical/clustering architecture to realize many-to-one communications. The capacity of the network under this many-to-one data-gathering scenario is reduced compared to random one-to-one communication due to the unavoidable creation of a point of traffic concentration at the data collector/receiver. We introduce the overall throughput bound of λ = W/n per node, where W is the transmission capacity, and show under what conditions it can be achieved and under what conditions it cannot. When those conditions are not met, we constructively show how λ = Θ(W/n) is achieved with high probability as the number of sensors goes to infinity. We also show how the introduction of clustering can improve the throughput. We discuss the trade-offs between achieving capacity and energy consumption, how transport capacity might be affected by considering in-network processing and the implications this study has on the design of practical protocols for large-scale data-gathering wireless sensor networks.
---
paper_title: On network correlated data gathering

paper_content:

We consider the problem of correlated data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. Two coding strategies are analyzed: a Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult. This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure. For the Slepian-Wolf setting, we derive a closed form solution and an efficient distributed approximation algorithm with a good performance. For the explicit communication case, we prove that building an optimal data gathering tree is NP-complete and we propose various distributed approximation algorithms.
---

Title: Data-aggregation techniques in sensor networks: a survey

Section 1: Introduction
Description 1: Introduce the concept of wireless sensor networks (WSNs), their applications, and the importance of data aggregation. Explain the definition of data aggregation and its significance in conserving energy and bandwidth in WSNs.

Section 2: Performance Measures for Data Aggregation
Description 2: Define and discuss critical performance measures for data-aggregation algorithms, such as network lifetime, data accuracy, and latency. Explain how these measures impact the efficiency of data-aggregation algorithms.

Section 3: Data-Aggregation Protocols Based on Network Architecture
Description 3: Explore different data-aggregation protocols designed for various network architectures. Compare flat networks, hierarchical networks, chain-based data aggregation, tree-based data aggregation, and grid-based data aggregation.

Section 4: Network-Flow-Based Data-Aggregation Protocols
Description 4: Describe data-aggregation protocols that model the sensor network as a graph and focus on optimization of network lifetime using network flow techniques. Discuss approaches like maximum lifetime data aggregation and flow optimization.

Section 5: QoS-Aware Data-Aggregation Protocols
Description 5: Detail protocols that focus on guaranteeing quality of service (QoS) metrics, such as bandwidth, end-to-end delay, and information throughput, in addition to optimizing energy efficiency.

Section 6: Handling Trade-offs in Data Aggregation
Description 6: Discuss how various protocols handle trade-offs between different performance measures like energy, latency, and data accuracy. Offer insight into different approaches to manage these trade-offs effectively.

Section 7: Security Issues in Data Aggregation
Description 7: Address security concerns in data aggregation for sensor networks, including data encryption, secure transmission, and the impact of compromised nodes. Highlight different approaches to secure data aggregation.

Section 8: Conclusions
Description 8: Summarize the comprehensive survey of data-aggregation algorithms, highlighting their focus on network lifetime, data latency, data accuracy, and energy consumption. Discuss the future research directions and challenges in data aggregation for sensor networks.