Abstract
Inspired by the well-known Dipole and Yagi antennae we introduce and study a new theoretical model of directional antennae that we call double antennae. Given a set P of n sensors in the plane equipped with double antennae of angle φ and with dipole-like and Yagi-like antenna propagation patterns, we study the connectivity and stretch factor problems, namely finding the minimum range such that double antennae of that range can be oriented so as to guarantee strong connectivity or stretch factor of the resulting network. We introduce the new concepts of (2,φ)-connectivity and φ-angular range r φ (P) and use it to characterize the optimality of our algorithms. We prove that r φ (P) is a lower bound on the range required for strong connectivity and show how to compute r φ (P) in time polynomial in n. We give algorithms for orienting the antennae so as to attain strong connectivity using optimal range when φ ≥ 2 π/3, and algorithms approximating the range for φ ≥ π/2. For φ < π/3, we show that the problem is NP-complete to approximate within a factor \(\sqrt{3}\). For φ ≥ π/2, we give an algorithm to orient the antennae so that the resulting network has a stretch factor of at most 4 compared to the underlying unit disk graph.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bose, P., Carmi, P., Damian, M., Flatland, R., Katz, M.J., Maheshwari, A.: Switching to Directional Antennas with Constant Increase in Radius and Hop Distance. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 134–146. Springer, Heidelberg (2011)
Caragiannis, I., Kaklamanis, C., Kranakis, E., Krizanc, D., Wiese, A.: Communication in wireless networks with directional antennas. In: Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures, pp. 344–351. ACM (2008)
Cormen, T.H.: Introduction to Algorithms, 2nd edn. The MIT Press (2007)
Damian, M., Flatland, R.: Spanning properties of graphs induced by directional antennas. In: Electronic Proc. 20th Fall Workshop on Computational Geometry. Stony Brook University, Stony Brook (2010)
De Berg, M., Cheong, O., Van Kreveld, M.: Computational geometry: algorithms and applications. Springer-Verlag New York Inc. (2008)
Dobrev, S., Kranakis, E., Krizanc, D., Opatrny, J., Ponce, O.M., Stacho, L.: Strong Connectivity in Sensor Networks with Given Number of Directional Antennae of Bounded Angle. In: Wu, W., Daescu, O. (eds.) COCOA 2010, Part II. LNCS, vol. 6509, pp. 72–86. Springer, Heidelberg (2010)
Fleischner, H.: The square of every two-connected graph is hamiltonian. Journal of Combinatorial Theory, Series B 16(1), 29–34 (1974)
Gupta, H., Kumar, U., Das, S.R.: A topology control approach to using directional antennas in wireless mesh networks. IEEE International Conference on Communications 9(06), 4083–4088 (2006)
Gupta, P., Kumar, P.R.: The capacity of wireless networks. IEEE Transactions on Information Theory 46(2), 388–404 (2000)
Hu, L., Evans, D.: Using directional antennas to prevent wormhole attacks. In: Network and Distributed System Security Symposium, NDSS (2004)
Kranakis, E., Krizanc, D., Morales, O.: Maintaining connectivity in sensor networks using directional antennae. In: Nikoletseas, S., Rolim, J. (eds.) Theoretical Aspects of Distributed Computing in Sensor Networks, pp. 59–84 (2010)
Kranakis, E., Krizanc, D., Williams, E.: Directional Versus Omnidirectional Antennas for Energy Consumption and k-Connectivity of Networks of Sensors. In: Higashino, T. (ed.) OPODIS 2004. LNCS, vol. 3544, pp. 357–368. Springer, Heidelberg (2005)
Parker, R.G., Rardin, R.L.: Guaranteed performance heuristics for the bottleneck travelling salesman problem. Operations Research Letters 2(6), 269–272 (1984)
Schiller, J.H.: Mobile Communications. Addison Wesley (2003)
Yi, S., Pei, Y., Kalyanaraman, S., Azimi-Sadjadi, B.: How is the capacity of ad hoc networks improved with directional antennas? Wireless Networks 13(5), 635–648 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Eftekhari Hesari, M., Kranakis, E., MacQuarie, F., Morales-Ponce, O., Narayanan, L. (2012). Strong Connectivity of Sensor Networks with Double Antennae. In: Even, G., Halldórsson, M.M. (eds) Structural Information and Communication Complexity. SIROCCO 2012. Lecture Notes in Computer Science, vol 7355. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31104-8_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-31104-8_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31103-1
Online ISBN: 978-3-642-31104-8
eBook Packages: Computer ScienceComputer Science (R0)