CPL - Chalmers Publication Library

# Approximation algorithms for the antenna orientation problem

E. Kranakis ; F. MacQuarrie ; Oscar Morales-Ponce (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) )
Fundamentals of Computation Theory (19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings) Lecture Notes in Computer Science (0302-9743). Vol. 8070 (2013), p. 225-235.
[Konferensbidrag, refereegranskat]

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 NP-Hard 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 well-known 2-connectivity, 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.

Nyckelord: Antenna Orientation Problem, Beamwidth , Connectivity, Directional Antenna , Wireless Sensor Networks

CPL Pubid: 216332

# Läs direkt!

Länk till annan sajt (kan kräva inloggning)