Connectivity and stretch factor trade-offs in wireless sensor networks with directional antennae

We consider the following Antenna Orientation Problem: Given a connected Unit Disk Graph (UDG) formed by n identical omnidirectional sensors, what is the optimal range (or radius) which is necessary and sufficient for a given antenna beamwidth (or angle) phi so that after replacing the omnidirectional sensors by directional antennas of beamwidth phi it is possible to find an appropriate orientation of each antenna so that the resulting graph is strongly connected? In this paper we study beamwidth/range tradeoffs for the Antenna Orientation Problem. Namely, for the full range of angles in the interval [0, 2 pi] we compare the antenna range provided by an orientation algorithm to the optimal possible for the given beamwidth. We propose new antenna orientation algorithms that ensure improved bounds for given angle ranges and analyze their complexity. We also examine the Antenna Orientation Problem with Constant Stretch Factor, where we wish to optimize both the transmission range and the hop-stretch factor of the induced communication network. We present approximations to this problem for antennas with angles pi/