research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleCommunication in wireless networks with directional antennas
Bibtex cite IDRACTI-RU1-2008-60
Booktitle 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2008)
Year published 2008
Pages 344-351
Keywords Wireless networks,directional antennas,connectivity
We study the problem of maintaining connectivity in a wireless network where the network nodes are equipped with directional antennas. Nodes correspond to points on the plane and each uses a directional antenna modeled by a sector with a given angle and radius. The connectivity problem is to decide whether or not it is possible to orient the antennas so that the directed graph induced by the node transmissions is strongly connected. We present algorithms for simple polynomial-time-solvable cases of the problem, show that the problem is NP-complete in the 2-dimensional case when the sector angle is small, and present algorithms that approximate the minimum radius to achieve connectivity for sectors with a given angle. We also discuss several extensions to related problems. To the best of our knowledge, the problem has not been studied before in the literature.
Caragiannis, Ioannis
Kaklamanis, Christos
Kranakis, Evangelos
Krizanc, Danny
Wiese, A.
spaa08.pdf (main file)
Publication ID522