Abstract
Sensor networks are characterized by limited energy, processing power, and bandwidth capabilities. These limitations become particularly critical in the case of event-based sensor networks where multiple collocated nodes are likely to notify the sink about the same event, at almost the same time. The propagation of redundant highly correlated data is costly in terms of system performance, and results in energy depletion, network overloading, and congestion. Data aggregation is considered to be an effective technique to reduce energy consumption and prevent congestion in wireless sensor networks. In this paper, we derive a number of important insights concerning the data aggregation process, which have not been discussed in the literature so far. We first estimate the conditions under which aggregation is a costly process in comparison to a non aggregation approach, by considering a realistic scenario where the processing costs related to aggregation of data are not neglected. We also consider that aggregation should preserve the integrity of data, and therefore, the entropy of the correlated data sent by sources can be considered in order to both decrease the amount of redundant data forwarded to the sink and perform an overall lossless process. We also derive the cumulative and the probability distribution functions of the delay in an aggregator node queue, which can be used to relate the delay to the amount of aggregation being considered. The framework we present in this paper serves to investigate the tradeoff between the increase in data aggregation required to reduce energy consumption, and the need to maximize information integrity, while also understanding how aggregation impacts the network propagation delay of a data packet.
Similar content being viewed by others
Notes
Though different approaches can be used in building trees, the analysis presented in the rest of the paper is independent of how each specific tree is established. Similarly, the analytical derivation is not affected by the particular distributed algorithm that nodes use to exchange information needed to estimate the energy consumption and the information entropy associated with aggregation.
Considering we are focusing on the aggregation process only, in the following analysis we disregard energy consumption related to MAC or routing protocol operations. If addressing these aspects too, we should definitely consider additional energy cost terms, e.g., related to the specific kind of routing protocols used (i.e., whether proactive or reactive), the probability of collisions experienced by the node when accessing the medium, and others.
Nodes upstream w.r.t. a node k are nodes met along the path going from node k up to the sink.
Differential entropy represents the extension of the entropy concept, i.e., a measure of the degree of “surprise” associated with a random variable, to the case of continuous variables [19].
With no loss of generality, we are assuming packets of unit length.
References
C. Shen, C. Srisathapornphat, C. Jaikaeo, Sensor information networking architecture and applications, IEEE Personal Communications, Vol. 8, No. 4, pp. 52–59, 2001.
J. M. Kahn, R. H. Katz, K. S. J. Pister, Next Century Challenges: Mobile Networking for "Smart Dust", ACM Mobicom, Seattle, WA, 1999.
G. Ahn, S. G. Hong, E. Miluzzo, A. T. Campbell, F. Cuomo, Funneling-MAC: a Localized, Sink-Oriented MAC for Boosting Fidelity in Sensor Networks, ACM Sensys, Boulder, CO, 2006.
C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidenmann, F. Siva, Directed diffusion for wireless sensor networking, ACM/IEEE Transactions on Networking, Vol. 11, No. 1, pp. 2–16, 2002.
A. Boulis, S. Ganeriwal, M. Srivastava, Aggregation in Sensor Networks: An Energy-Accuracy Tadeoff, IEEE SNPA, Ankorage, AL, 2003.
L. Galluccio, A. T. Campbell, S. Palazzo, Concert: Aggregation-Based Congestion Control for Sensor Networks, ACM Sensys, San Diego, CA, 2005.
C. Intanagonwiwat, D. Estrin, R. Govindan, J. Heidenmann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, IEEE ICDCS, Wien, Austria, 2002.
A. Scaglione, S. Servetto, On the Interdependence Between Routing and Data Compression, ACM Mobicom, Atlanta, GA, 2002.
R. Zheng, R. Barton, Toward Optimal Data Aggregation in Random Wireless Sensor Networks, IEEE INFOCOM, Anchorage, AL, 2007.
B. Krishnamachari, D. Estrin, S. Wicker, The Impact of Data Aggregation in Wireless Sensor Networks, DEBS, Wien, Austria, 2002.
D. Vass, A. Vidacs, Distributed Data Aggregation with Geographical Routing in Wireless Sensor Networks, IEEE ICPS, Istanbul, Turkey, 2007.
X. Su, A combinatorial algorithmic approach to energy efficient information collection in wireless sensor networks, ACM Transactions on Sensor Networks, Vol. 3, No. 1, pp. 40–46, 2007.
H. Gupta, V. Navda, S. R. Das, V. Chowdhary, Efficient Gathering of Correlated Data in Sensor Networks, ACM Mobihoc, Urbana-Champaign, IL, 2005.
R. Cristescu, B. Beferull-Lozano, M. Vetterli, R. Wattenhofer, Network correlated data gathering with explicit communication: NP completeness and algorithms, ACM/IEEE Transactions on Networking, Vol. 14, No. 1, pp. 41–54, 2006.
J. Gao, L. Guibas, J. Herschberger, Sparse Data Aggregation in Sensor Networks, IEEE IPSN, Cambridge, MA, 2007.
L. Kleinrock, Queueing Systems, Volume II: Computer Applications, Wiley, NY, 1976.
W. R. Heinzelman, A. Chandrakasan, H. Balakrishnan, Energy-efficient communication protocol forwireless microsensor networks, Proceedings of IEEE HICSS, Hawaii, HW, 2000.
W. Feng, H. Alshaer, J. M. H. Elmirghani, Energy Efficiency: Optimal Transmission Range with Topology Management in Rectangular ad-hoc Wireless Networks, Proceedings of IEEE AINA, Bradford, UK, 2009.
T. M. Cover, J. A. Thomas, Elements of Information Theory, 2nd ed. Wiley, NY, 1991.
E. Ertin, Gaussian Process Models for Censored Sensor Readings, IEEE/SP SSP, Madison, WI, 2007.
M. C. Vuran, I. Akyildiz, Spatial correlation-based collaborative medium access control in wireless sensor networks, ACM/IEEE Transactions on Networking, Vol. 14, No. 2, pp. 316–329, 2006.
Acknowledgments
This work has been partially supported by the Italian National Project: Wireless multiplatfOrm mimo active access netwoRks for QoS-demanding muLtimedia Delivery (WORLD), under grant no. 2007R989S and by the European Commission in the framework of the FP7 Network of Excellence in Wireless COMmunications NEWCOM++ under contract no. 216715.
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper has been presented at PIMRC 2008, Cannes (France).
Rights and permissions
About this article
Cite this article
Galluccio, L., Palazzo, S. & Campbell, A.T. Modeling and designing efficient data aggregation in wireless sensor networks under entropy and energy bounds. Int J Wireless Inf Networks 16, 175–183 (2009). https://doi.org/10.1007/s10776-009-0107-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10776-009-0107-z