Optimal Relay Location for Resource-Limited Energy-Efficient Wireless Communication

Abstract

In the design of wireless networks, techniques for improving energy efficiency and extending network lifetime have great importance, particularly for defense and civil/rescue applications where resupplying transmitters with new batteries is not feasible. In this paper we study a method for improving the lifetime of wireless networks by minimizing the length of the longest edge in the interconnecting tree with deploying additional relay nodes.Let P={p1, ..., pn} be a set of n terminals in the Euclideanplane. For a positive integer k, the bottleneck Steinertree problem (BSTP) asks to find a Steiner tree with atmost k Steiner points such that the length of the longest edge in the tree is minimized. We give a ratio - sqrt(3) + e polynomial time approximation algorithm for BSTP, where e is an arbitrary positive number.Keywords:wireless networks, power efficient, approximation algorithms, Steiner tree, bottleneck Steiner tree.