Research on the Fault Tolerance Deployment in Sensor Networks

摘要

In this paper, we consider the problem of how to place redundant sensor nodes in an arbitrary sensor network to establish multi-connectivity. Specifically, after exploring the existing general k-connectivity algorithm, this paper proves that its approximation ratio is upper-bounded by only O(k~3α), asymptotically one order of k lower than that presented before. Since establishing k-connectivity is not cost-efficient for many applications, this paper further relaxes k-connectivity to partial k-connectivity and upper-bounds the approximation ratio of partial k-connectivity with O(k~4 α).