Fault-tolerant deployment with k-connectivity and partial k-connectivitv in sensor networks
Wireless sensor networks are prone to failure, so prolonging their lifetime and preventing loss of connectivity are significant. A simple but efficient strategy is to place redundant sensor nodes to establish multi-connectivity. This paper explores how to add as few as possible nodes (called Steiner nodes) to a sensor network such that the resulting network is k-connected or partially k-connected. k-connectivity means that each pair of the nodes, whether Steiner or original, is connected by at least k node-disjoint paths, while partial k-connectivity only requires such connectivity among original nodes. The contribution lies in two aspects. First, the approximation ratio of an existing k-connectivity repair algorithm is decreased from O(k(4)alpha) to O(k(3)alpha), where alpha is the approximation ratio of any algorithm that finds a minimum-weight k-connected spanning subgraph of a weighted complete graph. This is the best result ever obtained. Second, the first generic partial k-connectivity repair algorithm is proposed. It is proved that the approximation ratio of this algorithm is at most O(k(3)alpha). Copyright (C) 2008 John Wiley & Sons, Ltd.
deployment k-connectivity sensor networks approximation ratio