Fault‐tolerant deployment withk‐connectivity and partialk‐connectivity in sensor networks
Juhua Pu, Zhang Xiong, Xiaofeng Lu · Wireless Communications and Mobile Computing · 2008
Abstract 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 isk‐connected or partiallyk‐connected.k‐connectivity means that each pair of the nodes, whether Steiner or original, is connected by at leastknode‐disjoint paths, while partialk‐connectivity only requires such connectivity among original nodes. The contribution lies in two aspects. First, the approximation ratio of an existingk‐connectivity repair algorithm is decreased fromO(k4α) toO(k3α), whereαis the approximation ratio of any algorithm that finds a minimum‐weightk‐connected spanning subgraph of a weighted complete graph. This is the best result ever obtained. Second, the first generic partialk‐connectivity repair algorithm is proposed. It is proved that the approximation ratio of this algorithm is at mostO(k3α). Copyright © 2008 John Wiley & Sons, Ltd.