4.3 Article Proceedings Paper

Scale-free aggregation in sensor networks

期刊

THEORETICAL COMPUTER SCIENCE
卷 344, 期 1, 页码 15-29

出版社

ELSEVIER
DOI: 10.1016/j.tcs.2005.06.023

关键词

sensor networks; aggregation; random walk; collision time; routing; simultaneous optimization

向作者/读者索取更多资源

Sensor networks are distributed data collection systems, frequently used for monitoring environments in which nearby data have a high degree of correlation. This induces opportunities for data aggregation, that are crucial given the severe energy constraints of the sensors. Thus, it is very desirable to take advantage of data correlations in order to avoid transmitting redundancy. In our model, we formalize a notion of correlation, that can vary according to a parameter k. Then we relate the expected collision time of nearby walks on the grid to the optimum cost of scale-free aggregation. We also propose a very simple randomized algorithm for routing information on a grid of sensors that satisfies the appropriate collision time condition. Thus, we prove that this simple scheme is a constant factor approximation (in expectation) to the optimum aggregation tree simultaneously for all correlation parameters k. The key contribution in our randomized analysis is to bound the average expected collision time of non-homogeneous random walks on the grid, i.e. the next hop probability depends on the current position. (c) 2005 Elsevier B.V. All rights reserved.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据