Wishbone: Profile-based Partitioning for Sensornet Applications

Ryan Newton, Sivan Toledo, Lewis Girod, Hari Balakrishnan, Samuel Madden
NSDI 2009, Boston, MA, April 2009

The ability to partition sensor network application code across sensor nodes and backend servers is important for running complex, data-intensive applications on sensor platforms that have CPU, energy, and bandwidth limitations. This paper presents Wishbone, a system that takes a dataflow graph of operators and produces an optimal partitioning. With Wishbone, users can run the same program on a range of sensor platforms, including TinyOS motes, smartphones running JavaME, and the iPhone. The resulting program partitioning will in general be different in each case, reflecting the different node capabilities. Wishbone uses profiling to determine how each operator in the dataflow graph will actually perform on sample data, without requiring cumbersome user annotations. Its partitioning algorithm models the problem as an integer linear program that minimizes a linear combination of network bandwidth and CPU load and uses program structure to solve the problem efficiently in practice. Our results on a speech detection application show that the system can quickly identify good trade-offs given limitations in CPU and network capacity.

[PDF (2627KB)]

Bibtex Entry:

@inproceedings{newton2009wishbone,
   author =       "Ryan Newton and Sivan Toledo and Lewis Girod and Hari Balakrishnan and Samuel Madden",
   title =        "{Wishbone: Profile-based Partitioning for Sensornet Applications}",
   booktitle =    {NSDI 2009},
   year =         {2009},
   month =        {April},
   address =      {Boston, MA}
}