Abstract
The approach of using topology control to reduce interference in wireless sensor networks has attracted attention of several researchers. There are at least two definitions of interference in the literature. In a wireless sensor network the interference at a node may be caused by an edge that is transmitting data [15], or it occurs because the node itself is within the transmission range of another [3], [1], [6]. In this paper we show that the problem of assigning power to nodes in the plane to yield a planar geometric graph whose nodes have bounded interference is NP-complete under both interference definitions. Our results provide a rigorous proof for a theorem in [15] whose proof is unconvincing. They also address one of the open issues raised in [6] where Halldórsson and Tokuyama were concerned with the receiver model of node interference, and derived an \(O(\sqrt {\Delta})\) upper bound for the maximum node interference of a wireless ad hoc network in the plane (Δ is the maximum interference of the so-called uniform radius network). The question as to whether this problem is NP-complete in the 2-dimensional case was left open.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bilò, D., Proietti, G.: On the Complexity of Minimizing Interference in Ad-Hoc and Sensor Networks. Theorectical Computer Science 402, 43–55 (2008)
Buchin, K.: Minimizing the Maximum Interference is Hard (2008), http://arxiv.org/abs/0802.2134
Burkhart, M., von Rickenbach, P., Wattenhofer, R., Zollinger, A.: Does Topology Control Reduce Interference? In: MOBIHOC 2004, pp. 9–19 (2004)
Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time Approximation Schemes for Geometric Intersection Graphs. SIAM J. Comput. 6(34), 1302–1323 (2005)
Erlebach, T., van Leeuwen, E.J.: Domination in Geometric Intersection Graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 747–758. Springer, Heidelberg (2008)
Halldórsson, M.M., Tokuyama, T.: Minimizing Interference of a Wireless Ad-Hoc Network in a Plane. In: Nikoletseas, S.E., Rolim, J.D.P. (eds.) ALGOSENSORS 2006. LNCS, vol. 4240, pp. 71–82. Springer, Heidelberg (2006)
Hunt III, D.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC- Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs. Journal Algorithms 2(26), 238–274 (1998)
Johansson, T., Carr-Motyckovaá, L.: Reducing Interference in Ad Hoc Networks Through Topology Control. In: DIALM-POMC 2005, pp. 17–23 (2005)
Lichtenstein, D.: Planar Formulae And Their Uses. SIAM J. of Compt. 11(23) (1982)
Marx, D.: Parameterized Complexity of Independence and Domination on Geometric Graphs. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 154–165. Springer, Heidelberg (2006)
Moaveni-Nejad, K., Li, X.-Y.: Low-Interference Topology Control for Wireless Ad Hoc Networks. Ad Hoc and Wireless Sensor Networks 1, 41–64 (2005)
Rickenbach, P.V., Schmid, S., Wattenhofer, R., Zollinger, A.: A Roburst Interference Model for Wireless Ad-Hoc Networks. In: Proc. 19th IEEE Int. Par. and Dist. (2005)
Valiant, L.: Universality Considerations in VLSI Circuits. IEEE Trans. on Compupters C-30, 135–140 (1981)
van Leeuwen, E.J.: Better Approximation Schemes for Disk Graphs. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 316–327. Springer, Heidelberg (2006)
Wu, K.-D., Liao, W.: On Constructing Low Interference Topology in Multihop Wireless Networks. Int. J. of Sensor Networks 2, 321–330 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nguyen, T.N., Huynh, D.T. (2009). Minimum Interference Planar Geometric Topology in Wireless Sensor Networks. In: Liu, B., Bestavros, A., Du, DZ., Wang, J. (eds) Wireless Algorithms, Systems, and Applications. WASA 2009. Lecture Notes in Computer Science, vol 5682. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03417-6_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-03417-6_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03416-9
Online ISBN: 978-3-642-03417-6
eBook Packages: Computer ScienceComputer Science (R0)