From Task Graphs to Concrete Actions: A New Task Mapping Algorithm for the Future Internet of Things
Authors:
- Benjamin BilletBBBenjamin Billet
- Valerie IssarnyVIValerie Issarny
- 1 October 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 24 (21556806) , 470-478
Abstract
Task mapping, which basically consists of mapping a set of tasks onto a set of nodes, is a well-known problem in distributed computing research. As a particular case of distributed systems, the Internet of Things (IoT) poses a set of renewed challenges, because of its scale, heterogeneity and properties traditionally associated with wireless sensor networks (WSN), shared sensing, continous processing and real time computing. To handle IoT features, we present a formalization of the task mapping problem that captures the varying consumption of resources and various constraints (location, capabilities, QoS) in order to compute a mapping that guarantees the lifetime of the concurrent tasks inside the network and the fair allocation of tasks among the nodes. It results in a binary programming problem for which we provide an efficient heuristic that allows its resolution in polynomial time. Our experiments show that our heuristic: (i) gives solutions that are close to optimal and (ii) can be implemented on reasonably powerful Things and performed directly within the network, without requiring any centralized infrastructure.Keywords
This publication has 22 references indexed in Scilit:
- Internet of Things (IoT): A vision, architectural elements, and future directionsFuture Generation Computer Systems, 2013
- A family of heuristics for agent-based elastic Cloud bag-of-tasks concurrent schedulingFuture Generation Computer Systems, 2013
- Adaptive energy-efficient scheduling for hierarchical wireless sensor networksACM Transactions on Sensor Networks, 2013
- Runtime optimisation in WSNs for load balancing using pheromone signalling2012
- An auction-based strategy for distributed task allocation in wireless sensor networksComputer Communications, 2012
- An Extensible Framework for Improving a Distributed Software System's Deployment ArchitectureIEEE Transactions on Software Engineering, 2011
- Battery-aware task scheduling in distributed mobile systems with lifetime constraint2011
- Energy-Efficient Task Mapping for Data-Driven Sensor Network MacroprogrammingIEEE Transactions on Computers, 2009
- In-network aggregation techniques for wireless sensor networks: a surveyIEEE Wireless Communications, 2007
- Energy-Balanced Task Allocation for Collaborative Processing in Wireless Sensor NetworksMobile Networks and Applications, 2005