Home
Speakers
Schedule
Location and Directions
Hotel Information
Ali Jadbabaie
University of Pennsylvania
Title: Finding sparse sensor covers and verifying coverage in blind sensor networks
Abstract: In this talk, we will demonstrate how tools from algebraic topology (specifically homology theory and discrete Hodge theory) can be used to verify coverage in blind (GPS-free) mobile sensor networks in a purely decentralized fashion and without location information. Based on the recent work of Vin De Silva and Rob Ghrist, I will show that coverage verification questions can be cast in the language of algebraic topology. Furthermore, we will use discrete Hodge theory to implement the coverage verification algorithm in a decentralized fashion using the combinatorial Laplacian operators. Next, we will use L1-norm minimization to search for sparsest generators of homology groups and show that this heuristic is in fact exact for several instances of this particular problem formulation. This will allow ``localization" of coverage holes even when location information is not available. Next, we will show that the same technique can be used to find sparse sensor covers by finding sparse generators of second homology groups relative to the boundary and turning off redundant sensors. Finally, we will discuss some interesting parallels between these problems and network flow problems on graphs and their distributed implementation with subgradient algorithms.