Deploying Sensor Networks With Guaranteed Fault Tolerance
We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multipath 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 th...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/69942 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0001-5473-3566 |
| _version_ | 1826217415336263680 |
|---|---|
| author | Hajiaghayi, Mohammad Taghi Bredin, Jonathan L. Demaine, Erik D. Rus, Daniela L. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Hajiaghayi, Mohammad Taghi Bredin, Jonathan L. Demaine, Erik D. Rus, Daniela L. |
| author_sort | Hajiaghayi, Mohammad Taghi |
| collection | MIT |
| description | We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multipath 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. |
| first_indexed | 2024-09-23T17:03:35Z |
| format | Article |
| id | mit-1721.1/69942 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:03:35Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/699422022-09-29T23:21:45Z Deploying Sensor Networks With Guaranteed Fault Tolerance Hajiaghayi, Mohammad Taghi Bredin, Jonathan L. Demaine, Erik D. Rus, Daniela L. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Bredin, Jonathan L. Demaine, Erik D. Rus, Daniela L. We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multipath 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. National Science Foundation (U.S.) (Grant IIS-0426838) National Science Foundation (U.S.) (Grant IIS-0225446) National Science Foundation (U.S.) (Grant ITR ANI-0205445) United States. Army Research Office. Multidisciplinary University Research Initiative. Scalable Swarms of Autonomous Robots and Mobile Sensors Project United States. Army Research Office. Multidisciplinary University Research Initiative. Smart Adaptive Reliable Teams for Persistent Surveillance United States. Army Research Office. Multidisciplinary University Research Initiative. Adaptive Networks for Threat and Intrusian Detection Or TErmination United States. Dept. of Homeland Security. Office for Domestic Preparedness (Award Number 2000-DT-CX-K001) 2012-04-04T21:32:47Z 2012-04-04T21:32:47Z 2010-02 2009-02 Article http://purl.org/eprint/type/ConferencePaper 1063-6692 1558-2566 INSPEC Accession Number: 11137956 http://hdl.handle.net/1721.1/69942 Bredin, J.L. et al. “Deploying Sensor Networks With Guaranteed Fault Tolerance.” IEEE/ACM Transactions on Networking 18.1 (2010): 216–228. Web. 4 Apr. 2012. © 2010 Institute of Electrical and Electronics Engineers https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0001-5473-3566 en_US http://dx.doi.org/10.1109/tnet.2009.2024941 IEEE/ACM Transactions on Networking Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers (IEEE) IEEE |
| spellingShingle | Hajiaghayi, Mohammad Taghi Bredin, Jonathan L. Demaine, Erik D. Rus, Daniela L. Deploying Sensor Networks With Guaranteed Fault Tolerance |
| title | Deploying Sensor Networks With Guaranteed Fault Tolerance |
| title_full | Deploying Sensor Networks With Guaranteed Fault Tolerance |
| title_fullStr | Deploying Sensor Networks With Guaranteed Fault Tolerance |
| title_full_unstemmed | Deploying Sensor Networks With Guaranteed Fault Tolerance |
| title_short | Deploying Sensor Networks With Guaranteed Fault Tolerance |
| title_sort | deploying sensor networks with guaranteed fault tolerance |
| url | http://hdl.handle.net/1721.1/69942 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0001-5473-3566 |
| work_keys_str_mv | AT hajiaghayimohammadtaghi deployingsensornetworkswithguaranteedfaulttolerance AT bredinjonathanl deployingsensornetworkswithguaranteedfaulttolerance AT demaineerikd deployingsensornetworkswithguaranteedfaulttolerance AT rusdanielal deployingsensornetworkswithguaranteedfaulttolerance |