Geometry Methods in Sensor Networks
Alexander Kröller, Technische Universitaet Braunschweig
- https://computing.phd.upc.edu/en/esdeveniments/geometry-methods-in-sensor-networks
- Geometry Methods in Sensor Networks
- 2015-11-23T10:00:00+01:00
- 2015-11-23T11:00:00+01:00
- Alexander Kröller, Technische Universitaet Braunschweig
When
Nov 23, 2015 from 10:00 AM to 11:00 AM (Europe/Madrid / UTC100)
Where
10 to 12, Room S215, Omega building, Campus Nord, UPC
Add event to calendar
The course is open to any interested person. Please confirm to mcomputing at lsi.upc.edu your interest.
For Master in Computing students, this is a 1ECTS course.
A wireless sensor network can be seen - or simplified - as a geometric graph, that is, a
directed or undirected graph with an embedding of the nodes into R2 or R3, where the
presence of edges is controlled by a boolean function. A substantial amount of WSN
research assumes this embedding is known to the nodes, or attempts to reconstruct it. The
latter de nes a class of problems, collectively known as Localization.
The aim of this course is to see how we can exploit the geometry of a WSN without
having to solve the localization problem.
We begin by reviewing why localization is a notoriously hard problem [1, 2, 3, 4], and
why we should therefore seek algorithms that do not need the actual embedding of the
nodes. In the following, we will concentrate on algorithms that use methods from Com-
putational Geometry to establish topological knowledge in the network, without requiring
localization. We will see how to identify the boundary of the WSN [6, 7, 8] and how to
construct topologically meaningful segmentations [6, 9]. We will also see how to use such
structures in applications, for example routing [5].
[1] J. Aspnes, D. K. Goldenberg, and Y.R. Yang. On the computational complexity of sensor network
localization. In Proc. ALGOSENSORS'04, pages 32-44, 2004.
[2] A. Basu, J. Gao, J.S.B. Mitchell, and G. Sabhnani. Distributed localization using noisy distance and
angle information. In Proc. MobiHoc'06, pages 262{273. ACM Press, 2006.
[3] H. Breu and D. G. Kirkpatrick. Unit disk graph recognition is NP-hard. Computational Geometry:
Theory and Applications, 9(1-2):3-24, 1998.
[4] J. Bruck, J. Gao, and A. Jiang. Localization and routing in sensor networks by local angle information.
In Proc. MobiHoc'05, pages 181{192. ACM Press, 2005.
[5] J. Bruck, J. Gao, and A. Jiang. MAP: Medial axis based geometric routing in sensor networks. In
Proc. MobiCom'05. ACM Press, 2005.
[6] A. Kröller, S.P. Fekete, D. P sterer, and S. Fischer. Deterministic boundary recognition and topology
extraction for large sensor networks. In Proc. SODA'06, pages 1000-1009, 2006.
[7] O. Saukh, R. Sauter, M. Gauger, P.J. Marr on, and K. Rothermel. On boundary recognition without
location information in wireless sensor networks. In Proc. IPSN'08, pages 207-218, 2008.
[8] Y.Wang, J. Gao, and J.S.B. Mitchell. Boundary recognition in sensor networks by topological methods.
In Proc. MobiCom'06, pages 122-133. ACM Press, 2006.
[9] X. Zhu, R. Sarkar, and J. Gao. Shape segmentation and applications in sensor networks. In Proc.
INFOCOM'07, pages 1838-1846, 2007.
For Master in Computing students, this is a 1ECTS course.
Abstract
A wireless sensor network can be seen - or simplified - as a geometric graph, that is, a
directed or undirected graph with an embedding of the nodes into R2 or R3, where the
presence of edges is controlled by a boolean function. A substantial amount of WSN
research assumes this embedding is known to the nodes, or attempts to reconstruct it. The
latter de nes a class of problems, collectively known as Localization.
The aim of this course is to see how we can exploit the geometry of a WSN without
having to solve the localization problem.
We begin by reviewing why localization is a notoriously hard problem [1, 2, 3, 4], and
why we should therefore seek algorithms that do not need the actual embedding of the
nodes. In the following, we will concentrate on algorithms that use methods from Com-
putational Geometry to establish topological knowledge in the network, without requiring
localization. We will see how to identify the boundary of the WSN [6, 7, 8] and how to
construct topologically meaningful segmentations [6, 9]. We will also see how to use such
structures in applications, for example routing [5].
References
[1] J. Aspnes, D. K. Goldenberg, and Y.R. Yang. On the computational complexity of sensor network
localization. In Proc. ALGOSENSORS'04, pages 32-44, 2004.
[2] A. Basu, J. Gao, J.S.B. Mitchell, and G. Sabhnani. Distributed localization using noisy distance and
angle information. In Proc. MobiHoc'06, pages 262{273. ACM Press, 2006.
[3] H. Breu and D. G. Kirkpatrick. Unit disk graph recognition is NP-hard. Computational Geometry:
Theory and Applications, 9(1-2):3-24, 1998.
[4] J. Bruck, J. Gao, and A. Jiang. Localization and routing in sensor networks by local angle information.
In Proc. MobiHoc'05, pages 181{192. ACM Press, 2005.
[5] J. Bruck, J. Gao, and A. Jiang. MAP: Medial axis based geometric routing in sensor networks. In
Proc. MobiCom'05. ACM Press, 2005.
[6] A. Kröller, S.P. Fekete, D. P sterer, and S. Fischer. Deterministic boundary recognition and topology
extraction for large sensor networks. In Proc. SODA'06, pages 1000-1009, 2006.
[7] O. Saukh, R. Sauter, M. Gauger, P.J. Marr on, and K. Rothermel. On boundary recognition without
location information in wireless sensor networks. In Proc. IPSN'08, pages 207-218, 2008.
[8] Y.Wang, J. Gao, and J.S.B. Mitchell. Boundary recognition in sensor networks by topological methods.
In Proc. MobiCom'06, pages 122-133. ACM Press, 2006.
[9] X. Zhu, R. Sarkar, and J. Gao. Shape segmentation and applications in sensor networks. In Proc.
INFOCOM'07, pages 1838-1846, 2007.
Support
Supported by the MICINN program "ayudas de movilidad de profesores en másters oficiales" 2008-2009.
Share: