Paper by Erik D. Demaine
- Jonathan L. Bredin, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Daniela Rus, “Deploying Sensor Networks with Guaranteed Fault Tolerance”, IEEE/ACM Transactions on Networking, volume 18, number 1, February 2010, pages 216–228.
We consider the problem of deploying or repairing a sensor network to
guarantee a specified level of multi-path connectivity (k-connectivity)
between all nodes. Such a guarantee simultaneously provides fault tolerance
against node failures and high overall network capacity (by the max-flow
min-cut theorem). We design and analyze the first algorithms that place an
almost-minimum number of additional sensors to augment an existing network
into a k-connected network, for any desired parameter k.
Our algorithms have provable guarantees on the quality of the solution.
Specifically, we prove that the number of additional sensors is within a
constant factor of the absolute minimum, for any fixed k. We have
implemented greedy and distributed versions of this algorithm, and demonstrate
in simulation that they produce high-quality placements for the additional
- This paper is also available from the ACM Digital Library.
- The paper is 14 pages.
- The paper is available in PostScript (22857k), gzipped PostScript (6246k), and PDF (1566k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Sensor_MOBIHOC2005 (Deploying Sensor Networks with Guaranteed Capacity and Fault Tolerance)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 3, 2020 by