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 sensors.

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 BibTeX file.
Last updated April 8, 2014 by Erik Demaine.