20130903
Approximation algorithms for the antenna orientation problem
Publication
Publication
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) φ so that after replacing the omnidirectional sensors by directional antennae of beamwidth φ we can determine an appropriate orientation of each antenna so that the resulting graph is strongly connected? The problem was first proposed and studied in Caragiannis et al. [3] where they showed that the antenna orientation problem can be solved optimally for φ ≥ 8π/5, and is NPHard for φ < 2π/3, where there is no approximation algorithm with ratio less than √3, unless P = NP. 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π] we compare the antenna range provided by an orientation algorithm to the optimal possible for the given beamwidth. We employ the concept of (2,φ)connectivity, a generalization of the wellknown 2connectivity, which relates connectivity in the directed graph to the best possible antenna orientation at a given point of the graph and use this to propose new antenna orientation algorithms that ensure improved bounds on the antenna range for given angles and analyze their complexity.
Additional Metadata  

Keywords  Antenna Orientation Problem, Beamwidth, Connectivity, Directional Antenna, Wireless Sensor Networks 
Persistent URL  dx.doi.org/10.1007/9783642401640_22 
Citation 
Kranakis, E, MacQuarrie, F. (Fraser), & Morales Ponce, O. (Oscar). (2013). Approximation algorithms for the antenna orientation problem. doi:10.1007/9783642401640_22
