News Archives

  • UNM
  • >Home
  • >News
  • >2010
  • >September
  • >[Colloquium] Scheduling Movements of Multiple Mobile Sinks to Maximize Wireless-Sensor-Network Lifetime

[Colloquium] Scheduling Movements of Multiple Mobile Sinks to Maximize Wireless-Sensor-Network Lifetime

September 3, 2010

Watch Colloquium: 

 M4V file (1643 MB)


  • Date: Friday, September 3, 2010 
  • Time: 12noon — 12:50 pm 
  • Place: Centennial Engineering Center, Room 1041

Cynthia Phillips
Senior Scientist Sandia National Laboratories

Abstract: Unattended sensor networks typically watch for some phenomena such as volcanic events, forest 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”)

Bio: Cynthia Phillips is a senior scientist in the Discrete Mathematics & Complex Systems Department at Sandia National Laboratories. She received a 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 and analysis, vehicle routing, computational biology, computer security, quantum computing, wireless networks, and experimental algorithmics.