Accession Number:

ADA455438

Title:

Relay Placement Approximation Algorithms for k-Connectivity in Wireless Sensor Networks

Descriptive Note:

Research rept.

Corporate Author:

MARYLAND UNIV COLLEGE PARK INST FOR SYSTEMS RESEARCH

Personal Author(s):

• Kashyap, Abhishek
• Khuller, Samir
• Shayman, Mark

Report Date:

2006-01-01

Pagination or Media Count:

11.0

Abstract:

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.

Descriptors:

• *DETECTORS
• *FAULT TOLERANCE
• *NETWORK TOPOLOGY
• ALGORITHMS
• WIRELESS LINKS
• RELAYS
• APPROXIMATION(MATHEMATICS)

Subject Categories:

• Computer Systems
• Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE