Abstract
The coverage area of a directional antenna located at point p is a circular sector of angle α, whose orientation and radius can be adjusted. The interference at p, denoted I(p), is the number of antennas that cover p, and the interference of a communication graph G = (P,E) is I(G) = max {I(p) : p ∈ P}. In this paper we address the question in its title. That is, we study several variants of the following problem: What is the minimum interference I, such that for any set P of n points in the plane, representing transceivers equipped with a directional antenna of angle α, one can assign orientations and ranges to the points in P, so that the induced communication graph G is either connected or strongly connected and I(G) ≤ I.
In the asymmetric model (i.e., G is required to be strongly connected), we prove that I = O(1) for α < 2π/3, in contrast with I = Θ(logn) for α = 2π, proved by Korman [12]. In the symmetric model (i.e., G is required to be connected), the situation is less clear. We show that I = Θ(n) for α < π/2, and prove that \(I=O(\sqrt{n})\) for π/2 ≤ α ≤ 3π/2, by applying the Erdös-Szekeres theorem. The corresponding result for α = 2π is \(I=\Theta(\sqrt{n})\), proved by Halldórsson and Tokuyama [10].
As in [12] and [10] who deal with the case α = 2π, in both models, we assign ranges that are bounded by some constant c, assuming that UDG(P) (i.e., the unit disk graph over P) is connected. Moreover, the \(O(\sqrt{n})\) bound in the symmetric model reduces to \(O(\sqrt{\Delta})\), where Δ is the maximum degree in UDG(P).
Work by R. Aschner was partially supported by the Lynn and William Frankel Center for Computer Sciences and by the Israel Ministry of Industry, Trade and Labor (consortium CORNET). Work by M.J. Katz was partially supported by the Israel Ministry of Industry, Trade and Labor (consortium CORNET), by grant 1045/10 from the Israel Science Foundation, and by grant 2010074 from the United States – Israel Binational Science Foundation. Work by G. Morgenstern was partially supported by the Lynn and William Frankel Center for Computer Sciences and by the Caesarea Rothschild Institute (CRI).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ackerman, E., Gelander, T., Pinchasi, R.: Ice-creams and wedge graphs. CoRR abs/1106.0855 (2011)
Aschner, R., Katz, M.J., Morgenstern, G.: Symmetric connectivity with directional antennas. CoRR abs/1108.0492 (2011)
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)
Burkhart, M., von Rickenbach, P., Wattenhofer, R., Zollinger, A.: Does topology control reduce interference? In: Proc. 5th ACM Internat. Sympos. on Mobile Ad Hoc Networking and Computing, pp. 9–19 (2004)
Caragiannis, I., Kaklamanis, C., Kranakis, E., Krizanc, D., Wiese, A.: Communication in wireless networks with directional antennas. In: 20th ACM Sympos. on Parallelism in Algorithms and Architectures, pp. 344–351 (2008)
Carmi, P., Katz, M.J., Lotker, Z., Rosén, A.: Connectivity guarantees for wireless networks with directional antennas. Computational Geometry: Theory and Applications 44(9), 477–485 (2011)
Carmi, P., Katz, M.J., Mitchell, J.S.B.: The minimum-area spanning tree problem. Computational Geometry: Theory and Applications 35(3), 218–225 (2006)
Damian, M., Flatland, R.: Spanning properties of graphs induced by directional antennas. In: Electronic Proc. 20th Fall Workshop on Computational Geometry. Stony Brook, NY (2010)
Erdös, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Mathematica 2, 463–470 (1935)
Halldórsson, M.M., Tokuyama, T.: Minimizing interference of a wireless ad-hoc network in a plane. Theor. Comput. Sci. 402(1), 29–42 (2008)
Johansson, T., Carr-Motycková, L.: Reducing interference in ad hoc networks through topology control. In: Proc. of the 2005 Joint Workshop on Foundations of Mobile Computing, pp. 17–23 (2005)
Korman, M.: Minimizing Interference in Ad-Hoc Networks with Bounded Communication Radius. In: Asano, T., Nakano, S.-i., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 80–89. Springer, Heidelberg (2011)
Kranakis, E., Krizanc, D., Morales, O.: Maintaining connectivity in sensor networks using directional antennae. In: Nikoletseas, S., Rolim, J.D.P. (eds.) Theoretical Aspects of Distributed Computing in Sensor Networks, ch. 3, pp. 59–84. Springer (2011)
Moaveni-Nejad, K., Li, X.-Y.: Low-interference topology control for wireless ad hoc networks. Ad Hoc & Sensor Wireless Networks 1(1-2) (2005)
von Rickenbach, P., Schmid, S., Wattenhofer, R., Zollinger, A.: A robust interference model for wireless ad-hoc networks. In: Proc. 19th IEEE Internat. Parallel and Distributed Processing Sympos. (2005)
Tan, H., Lou, T., Lau, F.C.M., Wang, Y., Chen, S.: Minimizing Interference for the Highway Model in Wireless Ad-Hoc and Sensor Networks. In: Černá, I., Gyimóthy, T., Hromkovič, J., Jefferey, K., Králović, R., Vukolić, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol. 6543, pp. 520–532. Springer, Heidelberg (2011)
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
Aschner, R., Katz, M.J., Morgenstern, G. (2012). Do Directional Antennas Facilitate in Reducing Interferences?. In: Fomin, F.V., Kaski, P. (eds) Algorithm Theory – SWAT 2012. SWAT 2012. Lecture Notes in Computer Science, vol 7357. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31155-0_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-31155-0_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31154-3
Online ISBN: 978-3-642-31155-0
eBook Packages: Computer ScienceComputer Science (R0)