Journal
IEEE-ACM TRANSACTIONS ON NETWORKING
Volume 18, Issue 1, Pages 216-228Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2009.2024941
Keywords
Approximation algorithms; augmentation; graph algorithms; sensor networks
Categories
Funding
- NSF [IIS-0426838, IIS-0225446, ITR ANI-0205445]
- MURI SWARMS, MURI SMARTS, and MURI ANTIDOTE
- U.S. Department of Homeland Security [2000-DT-CX-K001]
Ask authors/readers for more resources
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. 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available