Coordinate-free quantification of coverage in dynamic sensor networks

• Each sensor has only a list of its neighboring sensors, with no coordinates, or inter-sensor distance information.
• Using these snapshots of local information, we describe the dynamic coverage properties of the network.
• Quantitative output is a weighted barcode, obtained using zigzag persistent homology.
• Estimated hole size and duration are encoded in this barcode.
• Method is able to distinguish between different sensor network mobility patterns.

We present a methodology for analyzing coverage properties in dynamic sensor networks. The dynamic sensor network under consideration is studied through a series of snapshots, and is represented by a sequence of simplicial complexes, built from the communication graph at each time point. A method from computational topology called zigzag persistent homology takes this sequence of simplicial complexes as input, and returns a ‘barcode’ containing the birth and death times of homological features in this sequence. We derive useful statistics from this output for analyzing time-varying coverage properties.In addition, we propose a method which returns specific representative cycles for these homological features, at each point along the birth–death intervals. These representative cycles are then used to track coverage holes in the network, and obtain size estimates for individual holes at each time point. A weighted barcode, incorporating the size information, is then used as a visual and quantitative descriptor of the dynamic network coverage.

Figure optionsDownload as PowerPoint slide