Distinguished Lecture Series 2009-2010: Cynthia Phillips

Scheduling Movements of Multiple Mobile Sinks to Maximize
Wireless-Sensor-Network Lifetime
Cynthia Phillips, Sandia National Laboratories

Abstract

Unattended sensor networks typically watch for some phenomena such as volcanic events, forest ?res, pollution, or movements in animal populations. Sensors report to a collection point periodically or when they observe reportable events. When sensors are too far from the collection point to communicate directly, other sensors relay messages for them. If the collection point location is static, sensor nodes that are closer to the collection point relay far more messages than those on the periphery. Assuming all sensor nodes have roughly the same capabilities, those with high relay burden experience battery failure much faster than the rest of the network. However, since their death disconnects the live nodes from the collection point, the whole network is then dead.

We consider the problem of moving a set of collectors (sinks) through a wireless sensor network to balance the energy used for relaying messages, maximizing the lifetime of the network. We show how to compute an upper bound on the lifetime for any instance using linear and integer programming. We present a centralized offline heuristic that finds sink movement schedules that produce network lifetimes within 1.4% of the upper bound for realistic settings. We also present a distributed online heuristic that produces lifetimes at most 25.3% below the upper bound for steady traffic.

This research is typical of the interdisciplinary research at Sandia National Laboratories. It draws upon techniques from operations research (linear and integer programming), combinatorial optimization (traveling salesman, graph matching), and homegrown software tools to provide a practical solution for a realistically-sized network management problem.

This is joint work with Stefano Basagni (Northeastern University), Alessio Carosi (Universita di Roma "La Sapienza"), and Chiara Petrioli (Universita di Roma "La Sapienza")

Biography

Cynthia Phillips is a senior scientist in the Discrete Mathematics & Complex Systems Department at Sandia National Laboratories. She received PhD in computer science from MIT in 1990. In her 20 years at Sandia National Laboratories she has conducted research in combinatorial optimization, algorithm design and analysis, and parallel computation with applications to scheduling, network and infrastructure surety, integer programming, graph algorithms, vehicle routing, computational biology, computer security, quantum computing, wireless networks, and experimental algorithmics. She is one of three main developers of the PICO massively-parallel integer programming code. One of her recent projects is the design and analysis of sensor placement algorithms for municipal water networks. The EPA uses the sensor-placement toolbox to design contamination warning systems for US cities. This work was a finalist in the 2008 Edelman award competition. She also won an R&D 100 award in 2006 as part of a team that created node allocation algorithms for tightly-coupled massively-parallel computers.

She was an officer for 5 years for the ACM Symposium on Parallelism in Algorithms and Architectures. She is currently the chair for SIAM Special Interest group on supercomputing, a member of the SIAM program committee, and a member of the oversight board for the SIAM Mathematics in Industry study. She has been a program committee member for many conferences including co-chair of the 2010 SIAM Conference on Parallel Processing for Scientific Computing, program chair for the 2010 IEEE International Parallel and Distributed Processing Symposium (IPDPS), and program chair for the 2010 ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). She has done math/science community outreach including writing and running a mathematics prize competition for 7th-12th graders.