Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334308 | Theoretical Computer Science | 2005 | 15 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mihaela Enachescu, Ashish Goel, Ramesh Govindan, Rajeev Motwani,