Relay Placement Approximation Algorithms for k-Connectivity in Wireless Sensor Networks
MARYLAND UNIV COLLEGE PARK INST FOR SYSTEMS RESEARCH
Pagination or Media Count:
Sensors typically use wireless transmitters to communicate with each other. However, sensors may be located in a way that they cannot even form a connected network e.g, due to failures of some sensors, or loss of battery power. In this paper we consider the problem of adding the smallest number of additional relay nodes so that the induced communication graph is k-connected. The problem is NP-hard. We develop algorithms that find close to optimal solutions for both edge and vertex connectivity. For k-connectivity between sensor nodes, we prove the algorithms have an approximation ratio of Ok2 for vertex connectivity and Ok for edge connectivity. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal regions obstacles. We prove that the algorithms for k-connectivity between sensor and relay nodes have an approximation ratio of Ok3 for vertex connectivity and Ok2 for edge connectivity.
- Computer Systems
- Radio Communications