Paper by Erik D. Demaine

Reference:

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.

BibTeX

@Article{Sensor_TON,
  AUTHOR        = {Jonathan L. Bredin and Erik D. Demaine and
                   MohammadTaghi Hajiaghayi and Daniela Rus},
  TITLE         = {Deploying Sensor Networks with Guaranteed Fault Tolerance},
  JOURNAL       = {IEEE/ACM Transactions on Networking},
  journalurl    = {http://www.ton.cs.umass.edu/},
  VOLUME        = 18,
  NUMBER        = 1,
  MONTH         = {February},
  YEAR          = 2010,
  PAGES         = {216--228},

  length        = {14 pages},
  papers        = {Sensor_MOBIHOC2005},
  doi           = {https://dx.doi.org/10.1145/1816288.1816305},
  dblp          = {https://dblp.org/rec/journals/ton/BredinDHR10},
  comments      = {This paper is also available from the
                   <A HREF="http://doi.acm.org/10.1145/1816288.1816305">ACM Digital Library</A>.},
}

Abstract:

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.

Comments:

This paper is also available from the ACM Digital Library.

Length:

The paper is 14 pages.

Availability:

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)