CSE658: Seminar on Topological Methods in Wireless Networking

Locations and Hours: Thursday 4-5:30pm @ CS building 2311.

Updates:

1.      Please send me the topics you would like to present (select from the OPEN slots first).

Seminar topics:

In this semester’s wireless seminar we will cover a bunch of papers that apply topological methods in wireless networking and in particular sensor networks. Topology is a branch of mathematics that studies the connectivity of spaces. Algebraic topology uses tools from abstract algebra to study topological spaces. Typical questions of interest include whether a space is path connected, whether it has holes or in the higher dimensional scenario, voids or handles. Topological ideas have been traditionally applied in modeling and computer graphics. In recent years there are increasing interests in applying topological methods in the analysis of point cloud data, the study of protein shapes, the connectivity of wireless sensors, etc. For example, it was discovered through the analysis of a-shape that some proteins have a handle; and the 3´3 patches in natural images have the topology of a Klein bottle.

In this seminar we will focus on the use of topological methods in wireless networks. There are a number of benefits in using topological methods, as they are location independent (thus do not require accurate location information which is still hard to obtain in large wireless networks) and often lead to simple and implementable algorithms with provable theoretical supports. Topics include:

·         Homotopy of shortest paths in the detection of holes.    

·         Target counting and the measure of Euler characteristics.

·         Homology, persistence homology and barcode.

·         The detection of sufficient sensor coverage and the existence of coverage holes;

·         The application of homology in discovering the topology of the environment through contact info of mobile wireless nodes.

·         Witness complex, Delaunay triangulation and applications in routing and network localization.

·         Morse-Smale complex and flow complex in network segmentation and signal analysis.

In topology heavy notations and math formulas may sometimes scare people away. However, the basic idea is often very fundamental and intuitive. It is a delicate balance to be maintained between formal analysis and definitions as well as intuitive descriptions and algorithmic results. We will include formal definitions of all the math statements, but no proofs, and focus on algorithmic results and applications in wireless networking.

You can register for 1 credit. Registered students will be expected to present in one of the seminars. If you are interested in attending either formally or informally, please send email to Jie Gao (jgao at cs) to be included in the mailing list.

Schedules for Spring08:

 

 

Lecture Topics

Required readings

1

2/7

Introductory lecture and presentation assignment

Afra’s notes.

2

2/14

Path homology, boundary detection

Sandra, [WGM06]

3

2/21

Persistence homology and applications

Xiaotian, [Ghrist08, ELZ02, CZ05]

 

2/28

No seminar

 

4

3/6

Winding number, surrounding problem

Ritesh

5

3/13

Sensor coverage problem

Mohammad

 

3/20

Spring break, no seminar

 

6

3/27

No seminar

 

7

4/3

Target enumeration

Rik

8

4/10

Witness complex, routing around holes

Rupa

 

4/17

INFOCOM’08, no class

 

9

4/24

Network localization

Girish, Sol

10

5/1

Flow complex, segmentation and Morse-Smale complex

Joondong

11

5/8

Contour tree, Reeb graph and applications in information-guided navigation

Dengpan,

 

Reading List:

 

  1. Introduction.
    1. Afra’s notes.
    2. Chap 1 in Allen Hatcher’s Algebraic Topology book.
  2. Basics
    1. Simplicial complex, afra’s notes, herbert’s notes.
  3. Path homotopy
    1. [WGM06] Yue Wang, Jie Gao, Joseph Mitchell, Boundary Recognition in Sensor Networks by Topological Methods, The 12th Annual International Conference on Mobile Computing and Networking (MobiCom'06), 122-133, September, 2006. (Find network boundaries and hole boundaries from the homotopy of shortest path trees.)
    2. Xianjin Zhu, Rik Sarkar, Jie Gao, Joseph S. B. Mitchell, Light-weight Contour Tracking in Wireless Sensor Networks, to appear in Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), May, 2008. (Use shortest paths to repair a deformation retract of a contour of interest.)

c.       R. Ghrist, Winding numbers for networks with weak angular data , to appear in Topology and Robotics, M. Farber, R. Ghrist, M. Berger, and D. Koditschek eds., Contemporary Mathematics 438, AMS, 1-18, 2007. (Test whether a target is surrounded or not.)

d.      R. Ghrist, D. Lipsky, S. Poduri, and G. Sukhatme, Surrounding nodes in coordinate-free networks, Proc. Workshop in Algorithmic Foundations of Robotics, 2006. (The conference version of the previous paper.)

  1. Target enumeration and Euler characteristics
    1. Y. Baryshnikov and R. Ghrist, Target enumeration via Euler characteristic integrals I: sensor fields , preprint. (Consider the scenario of a sensor network detecting some targets/events, each target may cause multiple sensors to receive non-zero values. One would like to count how many targets there are. The solution, in short, is to solve the Minesweeper game.)
  2. Homology and persistance Homology
    1. Afra’s notes, herbert’s notes.
    2. [Ghrist08] Barcodes: The Persistent Topology of Data, Robert Ghrist, American Math Society, Volume 45, Number 1, January 2008, Pages 61-75.
    3. [ELZ02] Topological Persistence and Simplification. Herbert Edelsbrunner, David Letscher and Afra Zomorodian, Discrete and Computational Geometry, 2002 (invited), 41st Symposium on Foundations of Computer Science, Redondo Beach, CA, 2000
    4. [CZ05] Computing Persistent Homology. Gunnar Carlsson, Afra Zomorodian, Discrete and Computational Geometry, 2005 (ps.gz) (Errata), 20th ACM Symposium on Computational Geometry, Brooklyn, NY, 2004 (ps.gz)
  3. Network coverage holes

a.      R. Ghrist and A. Muhammad, Coverage and hole detection in sensor networks via homology, in Proc. IPSN, 2005. (Use homology theory on Cech and Rips complexes for sensor networks.)

    1. V. de Silva and R. Ghrist, Coverage in sensor networks via persistent homology, Alg. & Geom. Topology, 7, 339-358, 2007. (A more detailed version of the above paper.)
  1. Witness complexes
    1. V. de Silva, “A weak characterization of the Delaunay triangulation.” PDF (This paper gives the theoretical support of witness complex in the Euclidean space. It says the witness complex with all points in the Euclidean space as witnesses is the same as the Delaunay triangulation.)
    2. G. Carlsson, V. de Silva, “Topological approximation by small simplicial complexes.” PDF (Definition of Witness complex, and use it to compute homology of a point cloud data set.)
    3. D. Attali, H. Edelsbrunner, Y. Mileyko, “Weak Witnesses for Delaunay Triangulations of Submanifolds”, Proc. of ACM Symposium on Solid Physical Modeling, 2007. pdf-file (Extend the weak witnesses for points lying on a submanifold.)
    4. Q. Fang, J. Gao, L. Guibas, V. de Silva, L. Zhang, “GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks,” 24th Annual Conference of the IEEE Communication Society (INFOCOM), Miami, FL, March 13–17, 2005. PDF PS (Use geodesic Delaunay triangulation for routing around holes via virtual coordinates.)
    5. Gunnar Carlsson’s talk on Topology and the Analysis of High-Dimensional Data.
    6. Sol Lederer, Yue Wang, Jie Gao, Connectivity-based Localization of Large Scale Sensor Networks with Complex Shape, to appear in Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), May, 2008. (Use geodesic Delaunay triangulation for anchor-free network localization.)
  2. Morse-Smale complex, flow complex
    1. Xianjin Zhu, Rik Sarkar, Jie Gao, Shape Segmentation and Applications in Sensor Networks, Proc. of the 26th Annual IEEE Conference on Computer Communications (INFOCOM'07), 1838-1846, May, 2007. (This paper uses flow complex in segmenting a network with complex shape.)
    2. Herbert Edelsbrunner, John Harer, and Afra Zomorodian, Hierarchical Morse-Smale Complexes for Piecewise Linear 2-Manifolds, SoCG’01. (Compute Morse-Smale complex in 2D.)

Additional reading:

·         Geometry and topology for mesh generation, Herbert Edelsbrunner, Cambridge University Press, 2001.

·         Curve and surface reconstruction, algorithms with mathematical analysis, Tamal K. Dey, Cambridge University Press, 2007.

·         Algebraic Topology, Allen Hatcher, Cambridge University Press, 2002.

·         Topology learning.

·         Afra Zomorodian’s course notes and slides.

·         Vin de Silva’s paper list.

·         Robert Ghrist’s paper list.

·         Herbert Edelsbrunner’s Computational Topology course webpage.