Computer Science – Networking and Internet Architecture
Scientific paper
2009-07-30
Computer Science
Networking and Internet Architecture
Scientific paper
We address the problem of efficiently gathering correlated data from a wired or a wireless sensor network, with the aim of designing algorithms with provable optimality guarantees, and understanding how close we can get to the known theoretical lower bounds. Our proposed approach is based on finding an optimal or a near-optimal {\em compression tree} for a given sensor network: a compression tree is a directed tree over the sensor network nodes such that the value of a node is compressed using the value of its parent. We consider this problem under different communication models, including the {\em broadcast communication} model that enables many new opportunities for energy-efficient data collection. We draw connections between the data collection problem and a previously studied graph concept, called {\em weakly connected dominating sets}, and we use this to develop novel approximation algorithms for the problem. We present comparative results on several synthetic and real-world datasets showing that our algorithms construct near-optimal compression trees that yield a significant reduction in the data collection cost.
Deshpande Akshay
Khuller Samir
Li Jian
No associations
LandOfFree
On Computing Compression Trees for Data Collection in Sensor Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Computing Compression Trees for Data Collection in Sensor Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Computing Compression Trees for Data Collection in Sensor Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-267045