Skip to Main content Skip to Navigation
New interface
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 : Tuesday, November 29, 2022 - 11:50:04 AM
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 K. Prasanna. Energy-Efficient Task Mapping for Data-Driven Sensor Network Macroprogramming. IEEE Transactions on Computers, 2010, 59 (7), pp.955-968. ⟨10.1109/TC.2009.168⟩. ⟨hal-00723797⟩

Share

Metrics

Record views

74

Files downloads

242