Energy aware task allocation algorithms for wireless sensor networks

Abstract

Complex wireless sensor network (WSN) applications, such as those in Internet of things or in-network processing, are pushing the requirements of energy efficiency and long-term operation of the network drastically. Energy aware task allocation becomes crucial to extend the network lifetime, by efficiently distributing the tasks of applications among sensor nodes. Although task allocation has been deeply studied in wired systems, the resulting approaches are insufficient for WSNs due to limited battery resources and computing capability of WSN nodes, as well as the special wireless communication. This work focuses on designing energy aware task allocation algorithms to extend the network lifetime of WSNs. More precisely, this work firstly proposes a centralized static task allocation algorithm (CSTA) for cluster based WSNs. Since a WSN application can be modeled by a directed acyclic graph (DAG), the task allocation problem is formulated as partitioning the modeled DAG graph into two subgraphs: one for the slave node and the other for the master node. By using a binary vector variable to represent the partition cut, CSTA formulates the problem of maximizing network lifetime as a binary integer linear programming (BILP) problem. It provides one fixed time invariant partition cut (task allocation solution) for each slave node to balance the workload distribution of tasks. Moreover, motivated by the fact that using multiple partition cuts can achieve more balanced workload distribution, this work extends CSTA to a centralized dynamic task allocation algorithm, CDTA. By using a probability vector variable to stand for partition cuts with different weights, CDTA formulates the dynamic task allocation problem as a linear programing (LP) problem. Due to the high complexity of centralized algorithms, this work further proposes a very lightweight distributed optimal on-line task allocation algorithm (DOOTA). Through an indepth analysis, it proves that the optimal task allocation solution consists of at most two partition cuts for each slave nodes. Based on this analysis, DOOTA enables each slave node to calculate its own optimal task allocation solution by negotiating with the master node with a very short time. These contributions significantly improve the application performance for WSNs, but also for other domains, e.g, mobile edge/fog computing. Furthermore, the proposed task allocation algorithms are extended for different task scenarios and network structures, i.e., applications with conditional tasks, joint local and global applications and multi-hop mesh network. Given a condition triggered application, it is modeled by a DAG graph with conditional branches. This conditional DAG is further decomposed into multiple stationary DAG graphs without conditional branches according to the satisfaction probability of each condition. Based on this modeling, a static and a dynamic condition triggered task allocation algorithms (SCTTA and DCTTA) are proposed by considering the multiple stationary DAG simultaneously. Targeting the joint local and global applications, this work designs a static and a dynamic joint task allocation algorithms, SJTA and DJTA, based on BILP and LP, respectively. The modeling of local task allocation problem does not change, while the global task allocation problem is modeled by dividing the global DAG graph into different subgraphs mapping to the slave and master nodes. Besides the extensions for different task scenarios, this work presents a dynamic task allocation algorithm for multi-hop mesh networks (DTA-mhop) as well. The corresponding task allocation problem is modeled by dividing the DAG graph of each sensor node into multiple subgraphs mapping to itself, the routing and sink nodes. By using the summation of assigned tasks for each node, DTA-mhop formulates the lifetime maximization as a LP problem. The proposed task allocation algorithms are firstly evaluated using simulations and real WSN applications, in terms of network lifetime increase and algorithm runtime. In order to investigate the algorithm's performance in realistic scenarios, the CSTA, CDTA and DOOTA algorithms are implemented in a real WSN based on the OpenMote platform. Both the simulation and implementation results show that the network lifetime can be dramatically extended. Remarkably, the network lifetime improvements are more significant for addressing complex applications. The proposed task allocation algorithms are therefore suitable for WSNs, and they can also be easily adapted to other wireless domains.