Skip to Main content Skip to Navigation
Journal articles

Energy-Efficient Task Mapping for Data-Driven Sensor Network Macroprogramming

Abstract : Data-driven macroprogramming of wireless sensor networks (WSNs) provides an easy to use high-level task graph representation to the application developer. However, determining an energy-efficient initial placement of these tasks onto the nodes of the target network poses a set of interesting problems. We present a framework to model this task-mapping problem arising in WSN macroprogramming. Our model can capture placement constraints in tasks, as well as multiple possible routes in the target network. Using our framework, we provide mathematical formulations for the task-mapping problem for two different metrics -- energy balance and total energy spent. For both metrics, we address scenarios where a) a single or b) multiple paths are possible between nodes. Due to the complex nature of the problems, these formulations are not linear. We provide linearization heuristics for the same, resulting in mixed-integer programming (MIP) formulations. We also provide efficient heuristics for the above. Our experiments show that our heuristics give the same results as the MIP for real-world sensor network macroprograms, and show a speedup of up to several orders of magnitude. We also provide worst-case performance bounds of the heuristics.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00723797
Contributor : Animesh Pathak Connect in order to contact the contributor
Submitted on : Friday, September 7, 2012 - 3:13:39 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on: : Saturday, December 8, 2012 - 2:55:08 AM

File

pathak-prasanna-taskmapping-TC...
Files produced by the author(s)

Identifiers

Collections

Citation

Animesh Pathak, Viktor Prasanna. Energy-Efficient Task Mapping for Data-Driven Sensor Network Macroprogramming. IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2010, 59 (7), pp.955-968. ⟨10.1109/TC.2009.168⟩. ⟨hal-00723797⟩

Share

Metrics

Record views

224

Files downloads

373