Abstract
Consider a set \(S\) of sensors in a plane, each equipped with a directional antenna of beamwidth \(\frac{\pi }{2}\) and radius \(r\in O(1)\). The antennas are symmetric, i.e. for two sensors \(u\) and \(v\) to communicate, \(u\) has to be covered by the antenna of \(v\) and vice versa. Assuming the Unit Disc Graph (\(\mathrm{UDG}\)) of \(S\) is connected, the problem we attack is: How to orient the antennas so that the resulting connectivity graph is a \(k\)-spanner of the \(\mathrm{UDG}\), while minimizing the radius used?
We provide two results: (a) \(7\)-spanner using radius \(33\), and (b) \(5\)-spanner, still using \(O(1)\) radius. This significantly improves the previous state of the art (\(8\)-spanner), even improving upon the pre previous best result (\(6\)-spanner) for beamwidth \(\frac{2\pi }{3}\).
Supported by VEGA 2\0136\12.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Recall that \(r(v)\) and \(l(v)\) are the counter-clockwise and clockwise rays of antenna \(v\), respectively.
- 2.
It starts at least \(p\), due to padding; the relevant place to look is at distance \(14+p\) from \(c(C_i)\), as that it according to Lemma 5 the furthest place in \(D(C_i)\) containing any vertices.
References
Aschner, R., Katz, M.J.: Bounded-angle spanning tree: modeling networks with angular constraints. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 387–398. Springer, Heidelberg (2014)
Aschner, R., Katz, M.J., Morgenstern, G.: Symmetric connectivity with directional antennas. Comput. Geom. 46(9), 1017–1026 (2013)
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 20th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 344–351. ACM (2008)
Carmi, P., Katz, M.J., Lotker, Z., Rosen, A.: Connectivity guarantees for wireless networks with directional antennas. Comput. Geom. Theor. Appl. 44(9), 477–485 (2011)
Damian, M., Flatland, R.: Spanning properties of graphs induced by directional antennas. In: Electronic Proceedings of 20th Fall Workshop on Computational Geometry. Stony Brook, NY (2010)
Dobrev, S., Eftekhari, M., MacQuarrie, F., Manuch, J., Morales Ponce, O., Narayanan, L., Opatrny, J., Stacho, L.: Connectivity with directional antennas in the symmetric communication model. In: Mexican Conference on Discrete Mathematics and Computational Geometry. Oaxaca, Mexico (2013)
Dobrev, S., Kranakis, E., Krizanc, D., Morales-Ponce, O., Opatrny, J., Stacho, L.: Strong connectivity in sensor networks with given number of directional antennae of bounded angle. Discret. Math. Algorithms Appl. 4(03), 72–86 (2012)
Eftekhari Hesari, M., Kranakis, E., MacQuarie, F., Morales-Ponce, O., Narayanan, L.: Strong connectivity of sensor networks with double antennae. In: Even, G., Halldórsson, M.M. (eds.) SIROCCO 2012. LNCS, vol. 7355, pp. 99–110. Springer, Heidelberg (2012)
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. Springer, Heidelberg (2010)
Kranakis, E., MacQuarrie, F., Morales-Ponce, O.: Stretch factor in wireless sensor networks with directional antennae. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 25–36. Springer, Heidelberg (2012)
Morris, W., Soltan, V.: The Erdős-Szekeres problem on points in convex position—a survey. Bull. Am. Math. Soc. New Ser. 37(4), 437–458 (2000)
Shepard, C., Yu, H., Anand, N., Li, E., Marzetta, T., Yang, R., Zhong, L.: Argos: Practical many-antenna base stations. In: Proceedings of the 18th Annual International Conference on Mobile computing and Networking, pp. 53–64. ACM (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dobrev, S., Plžík, M. (2015). Improved Spanners in Networks with Symmetric Directional Antennas. In: Gao, J., Efrat, A., Fekete, S., Zhang, Y. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2014. Lecture Notes in Computer Science(), vol 8847. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46018-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-662-46018-4_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46017-7
Online ISBN: 978-3-662-46018-4
eBook Packages: Computer ScienceComputer Science (R0)