Abstract
We consider the problem of topology control of a wireless ad-hoc network on a given set of points in the plane, where we aim to minimize the maximum interference by assigning a suitable transmission radius to each point. By using computational geometric ideas and ε-net theory, we attain an \(O(\sqrt{\Delta})\) bound for the maximum interference where Δ is the interference of a uniform-radius ad-hoc network. This generalizes a result given in [8] for the special case of highway model (i.e., one-dimensional problem) to the two-dimensional case. We also give a method based on quad-tree decomposition and bucketing that has another provable interference bound in terms of the ratio of the minimum distance to the radius of a uniform-radius ad-hoc network.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P.K.: Range Searching. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, vol. 31, pp. 575–598. CRC Press, Boca Raton (1997)
Burkhart, M., von Rickenbach, P., Wattenhofer, R., Zollinger, A.: Does Topology Control Reduce Interference? In: Proc. MobiHoc 2004, pp. 9–19 (2004)
Haussler, D., Welzl, E.: ε-Nets and Simplex Range Queries. Discrete & Compu. Geom. 2, 237–256 (1987)
Matoušek, J.: Geometric Discrepancy. An Illustrated Guide. Springer, Heidelberg (1999)
Matoušek, J., Seidel, R., Welzl, E.: How to Net a Lot with Little: Small ε-Nets for Disks and Halfspaces. In: Proc. 6th Symp. on Computational Geometry, pp. 16–22 (1990)
Moscibroda, T., Wattenhofer, R.: Minimizing Interference in Ad Hoc and Sensor Networks. In: Proc. DIALM-POMC Joint Workshop 2005, pp. 24–33 (2005)
Preparata, F.P., Shamos, M.I.: Computational Geometry, an Introduction, Texts and Monographs in Computer Science, 2nd edn. Springer, Heidelberg (1988)
von Rickenbach, P., Schmid, S., Wattenhofer, R., Zollinger, A.: A Robust Interference Model for Wireless Ad-Hoc Networks. In: Proc. IPDPS 2005 (2005)
Yao, A.C.-C.: On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems. SIAM J. Comput. 11, 721–736 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Halldórsson, M.M., Tokuyama, T. (2006). Minimizing Interference of a Wireless Ad-Hoc Network in a Plane. In: Nikoletseas, S.E., Rolim, J.D.P. (eds) Algorithmic Aspects of Wireless Sensor Networks. ALGOSENSORS 2006. Lecture Notes in Computer Science, vol 4240. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11963271_7
Download citation
DOI: https://doi.org/10.1007/11963271_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69085-6
Online ISBN: 978-3-540-69087-0
eBook Packages: Computer ScienceComputer Science (R0)