### Skapa referens, olika format (klipp och klistra)

**Harvard**

Kranakis, E., MacQuarrie, F. och Morales-Ponce, O. (2013) *Approximation algorithms for the antenna orientation problem*.

** BibTeX **

@conference{

Kranakis2013,

author={Kranakis, E. and MacQuarrie, F. and Morales-Ponce, Oscar},

title={Approximation algorithms for the antenna orientation problem},

booktitle={Fundamentals of Computation Theory (19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings) Lecture Notes in Computer Science},

isbn={9783642401633},

pages={225-235},

abstract={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.},

year={2013},

keywords={Antenna Orientation Problem, Beamwidth , Connectivity, Directional Antenna , Wireless Sensor Networks},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 216332

A1 Kranakis, E.

A1 MacQuarrie, F.

A1 Morales-Ponce, Oscar

T1 Approximation algorithms for the antenna orientation problem

YR 2013

T2 Fundamentals of Computation Theory (19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings) Lecture Notes in Computer Science

SN 9783642401633

SP 225

OP 235

AB 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.

LA eng

DO 10.1007/978-3-642-40164-0_22

LK http://dx.doi.org/10.1007/978-3-642-40164-0_22

OL 30