Cooperative task allocation in heterogeneous wireless sensor networks

Abstract

In a wireless sensor network, sensor nodes are strictly energy and capacity constrained, which makes it necessary for them to collaboratively execute a complex task. Thus, task allocation becomes a fundamental and crucial issue in wireless sensor networks. Most previous studies developed centralized methods to solve this problem. In addition, a common assumption is that all the sensor nodes are homogeneous, which is unfavorable in many real applications. In this article, a distributed task allocation strategy which can handle the problem in a heterogeneous wireless sensor network is proposed. The task is propagated from nodes to nodes and each node matches its own capacity with the required capacities until all the demanded capacities of the task are obtained. Building on this, an enhanced task allocation strategy based on self-organization is developed. By utilizing previous assigning information, the nodes with proper capacities will be selected as candidate nodes, then the paths to these nodes will be optimized. In so doing, a new arriving task can be allocated directly and quickly. Simulation results show the feasibility of the proposed approach. Furthermore, the overall performance of the self-organization-based strategy is validated through a comparison with a particle swarm optimization–based centralized method and the fundamental method.

Keywords

Wireless sensor networks task allocation heterogeneity capacity matching self-organization mechanism

Introduction

A wireless sensor network (WSN) is usually composed of a large amount of tiny, low-cost, intelligent, and spatially dispersed sensors. Each sensor node has a specific capability including sensing, collecting, computing, and delivering data. By integrating substantial such sensors into a connected network, a WSN can monitor and gather information of the target area, often inhospitable and/or remote regions, without a prior arrangement as a traditional network. Therefore, in the past decade, WSNs have drawn extensive attention from not only the scientific community but also the industry. Meanwhile, WSNs have been successfully employed in a wide range of applications, such as battlefield surveillance,¹ environmental monitoring,² key object tracking,³ and natural disaster rescue.⁴

In most cases, a WSN is designed and deployed for performing a hard and complex mission. As an essentially parallel and distributed system, a WSN can decompose a complicated task into small- and low-resource-required subtasks. However, to an individual node, it only has very restricted capacity and resource, such as limited computation capacity, narrow communication bandwidth, and little storage space, which further block its possibility for accomplishing tasks independently. Therefore, the strategy for task allocation plays a vital impact on the overall performance of WSNs.

Recently, a great deal of studies and efforts have been conducted on task allocation in WSNs, and numerous fruitful achievements have been made.^5–9 Most existing task allocation strategies focus on how to distribute various subtasks to sensor nodes properly so that the network performance can be optimized. This issue is normally modeled as a multi-objective constrained optimization problem which has been proved to be non-deterministic polynomial-time (NP)-hard.^10,11 Many approaches have been proposed to solve this problem effectively, including reducing energy dissipation, minimizing task execution time, and prolonging network lifetime. One common limitation of these methods is that they are operated in a non-distributed and centralized manner. They all assume there is a powerful and energy sufficient node, for example, a sink node, in WSN, and all information about each individual node, such as the state of capacity, resource, and energy, can be collected and updated timely by it. Meanwhile, a computationally intensive task allocation algorithm can also be executed with high efficiency. However, as a large-scale and highly distributed network, it is infeasible to designate a normal sensor node as the sink node for its constrained power storage and processing capability. Even a base station or a gateway is not suitable in some circumstances. For instance, in a battlefield surveillance scenario, these key nodes will become the focus of hostile attacks, and once they are destroyed, the whole network will be out of work. On the contrary, if a task allocation strategy is distributed, even if part of the WSN is destructed under opponent’s attacks, the remaining sensor nodes can still cooperatively assign and perform tasks. Consequently, the property of distribution is crucial to a high-quality and robust task allocation scheme.

Another main drawback of previous task allocation strategy is that it commonly assumes each node in WSN has the same or a similar capacity, that is, the WSN is homogeneous. Although there have been some literatures introduced the term “Heterogeneity” to describe distinct capacity of different nodes, they merely referred to that each node has different processing speeds and initial energy levels.¹² In real-world applications, WSNs often face complicated tasks. In order to accomplish these tasks, multiple types of resources are required, that is, a WSN usually consists of sensor nodes with distinguishing capabilities. For instance, to avoid a place to be polluted, a comprehensive monitoring WSN is devised and deployed in the location. The WSN should contain various sensor nodes which are equipped with a variety of sensing devices, including chemical element sensors to detect the content of specific chemical elements in soil, water quality sensors to analyze the characteristics of chemical elements in water, and atmospheric sensors to monitor the amount of carbon dioxide in the air. Obviously, existing task allocation strategies are not suitable for such applications, for that they only consider the computing and processing speed while neglecting different resources owned by the nodes. Therefore, an approach that can deal with task allocation in $heterogeneous$ WSNs for such applications is mandatory.

Moreover, task allocation is essentially a problem with high computation complexity, usually a NP-complete problem. That is, the computation load will increase exponentially with the size of WSN, which seriously restricts current methods to be applied in large-scale networks. One promising solution to this problem is that after completing a few tasks, the relations among nodes can be autonomously adapted to provide helpful guidance for future task assignment. In this article, we exploit the technology of “self-organization” to improve the performance of task allocation in WSN, and particularly concentrate on arranging and rearranging structure links in distributing tasks. Actually, self-organization has been widely used in the area of WSN, mainly adopted in wireless routing protocols.^13,14 By self-organization, nodes can autonomously adjust communication links between them in order to adapt to dynamically changing topology and environmental conditions in WSNs. In so doing, the energy dissipation can be reduced and balanced and the overall network life is significantly prolonged. However, to the best of our knowledge, self-organization technology has never been adopted in task allocation, and in this article, we attempt to integrate self-organization mechanism into task allocation to further improve the performance.

With this background, in this article, we concentrate on task allocation in $heterogeneous$ WSNs which are composed of sensor nodes with distinct capabilities. Accordingly, each task has various resource requirements that make it necessary for nodes to work cooperatively. To solve this problem, we propose a cooperative task allocation strategy in WSNs. This method primarily aims at assigning tasks to appropriate sensors with demanded resources and guarantee that the tasks can be accomplished successfully. Moreover, to further reduce energy consumption and allocation delay, self-organization mechanism is incorporated into the strategy. By self-organization, each node can dynamically adjust its structural links with other nodes based on past interaction and the adaptation will assist succeeding task allocation. Another remarkable feature of the presented strategy is its distributability which makes it superior against most of the existing schemes in terms of robustness and computation load.

Related work

In the past decade, a large number of emphasis have been given to task allocation in WSNs. To a WSN, the sensor nodes are battery-powered and the batteries are incapable of being replaced, which incurs the main challenge to task allocation, that is, minimizing energy consumption and extending the network lifetime. Meanwhile, in many real-world applications, delay of task execution is also very limited. Consequently, most existing literatures take these two aspects as the optimization objectives.

Tian and Ekici¹⁵ proposed an application-independent task mapping and scheduling algorithm in multi-hop homogeneous WSNs, named multi-hop task mapping and scheduling (MTMS). They consider not only mapping computation tasks to sensors but also scheduling communication tasks among sensors in different layers. In addition, they developed a dynamic voltage scaling (DVS) algorithm to further reduce energy consumption. However, MTMS only considers homogeneous WSNs, which limits its application in a variety of conditions.

Xie and Qin¹⁶ pointed out that in WSNs, energy savings and low delay are usually two conflicting objects in the context of task allocation. They presented a detailed model of energy consumption which contained energy dissipation of running as well as link. Based on the model, an energy-delay balanced heuristic strategy with an energy-adaptive window (EAW) is developed. By dynamically tuning the size of EAW, the trade-offs between power consumption and schedule length can be readily adjusted. However, residual energy of nodes and workload balance are neglected.

Based on Xie and Qin,¹⁶ Abdelhak et al.¹⁷ proposed an energy-balanced task scheduling and allocation strategy (EBSEL) with the purpose of extending the network’s lifetime in a single-hop cluster of homogeneous sensors. The tasks are first divided into groups while maintaining parallelism, then nodes are sorted in non-increasing order of their remaining energy. By setting a threshold, the nodes with more remaining energy are given the priority to be allocated with tasks. However, this work does not consider deadline constraints which makes it not suitable in emergent scenarios.

In Wang et al.,¹⁸ a task allocation algorithm based on score incentive mechanism (TASIM) is proposed for cluster-based WSNs. The whole sensor nodes are divided into three ranking domains according to their residual energy and performance in the previous task execution. The nodes in the first ranking domain have the highest priority to be selected as candidates. The score of each node is calculated and updated after task completion. Additionally, the uncompleted tasks on failed or dead nodes can be reallocated by cluster heads to improve the robustness. Nevertheless, in TASIM, the cluster head is responsible for both task allocation and information update, which will consume too much energy and the head may die earlier.

Due to the shortcomings of centralized approaches, such as being unsuitable for dynamic network conditions, being fragile to unstable communication links, and high computational complexity, in Pilloni et al.,¹⁹ an adaptive and decentralized task allocation negotiation (TAN) algorithm is developed for clustered WSNs. Based on non-cooperative game theory, sensor nodes negotiate with each other for task allocation. By adopting a well-known distributed stochastic algorithm (DSA), all nodes can find a suitable strategy that will reduce application execution time as well as save network energy consumption.

All the work mentioned above adopt traditional heuristic approaches to seek for optimal solution. As stated in section “Introduction,” the issue of task allocation in WSNs is usually modeled as a multi-objective optimization problem which has proven to be NP-hard. The space of feasible solutions will grow explosively which poses a huge challenge to the scalability of traditional methods. However, the bio-inspired stochastic intelligent optimization algorithms have prominent advantages over traditional heuristic methods and have been widely applied in WSNs.²⁰ Jin et al.¹² proposed an intelligent task allocation and scheduling (ITAS) approach which aims to maximize network lifetime under the required quality of service (QoS) constraints. A popular evolutionary algorithm, named genetic algorithm (GA), is adopted to search for the optimal solution. All chromosomes in GA are evaluated via a hybrid fitness function which includes both the computation and multi-hop communication costs. By GA operations, the chromosome with the best “genes” will be preserved as the final solution. However, the residual energy of nodes are not considered here and GA itself may be easily stuck into local optimum.

In Yang et al.,²¹ an energy-efficient task allocation scheme with guaranteed application deadlines is presented. Different from Jin et al.,¹² a modified version of binary particle swarm optimization (PSO) algorithm is employed for the problem. Each particle is encoded as a feasible solution which is in the form of a binary matrix, and the position of one particle is updated according to the v-shaped family of transfer function. Moreover, a mutation operation is adopted in the iteration to maintain swarm diversity and reduce the probability of being trapped into local minima. However, during the process of position update, many unfeasible particles which do not meet the constraints of task workload and connectivity are produced and thus massive computation is wasted.

One shared drawback of the aforementioned approaches is that they all assume that a sensor node only has the functionalities of computation and communication, they concentrate on how to assign computation and communication load among sensors. However, in real practice, a node is usually equipped with a specific device to sense and collect certain information from the environment. Correspondingly, to execute a task, distinct types of data are required. Obviously, our issue is essentially different from the previous one and the existing approaches cannot be directly adopted to solve our problem. Therefore, in this article, we propose an efficient mechanism to assign tasks in heterogeneous WSNs.

Problem formulation

In this article, we consider a new model that is quite different from previous ones. In the following, we first describe the model of network, task, and sensor nodes, and then the problem is formulated.

System model

In our framework, a WSN is devised and deployed for accomplishing various applications in rounds, and each application consists of a number of tasks which will be assigned to multiple nodes. Unlike the directed acyclic graph (DAG) model, we assume tasks are independent and without precedent constraints, that is, tasks can be executed in an arbitrary order or in parallel. This assumption is reasonable in many real scenarios, for instance, in a surveillance system, when an object enters the target area, several attributes of the object must be sensed and collected, such as the appearance, the weight, the volume, and the moving speed. These sensings show no dependence and sensor nodes can work simultaneously to provide a more accurate and timely data. Another important feature of our task model is that a task requires different types of capacities. Here, the capacities of a task is defined as the necessary resources for successfully completing the task. More specifically, only the required capacities of a task are totally fulfilled by various nodes, the task can be performed. Therefore, a task can be denoted as a tuple $(t_{j}, C_{t_{j}})$ ; where $t_{j}$ is the index of task, $C_{t_{j}} = 〈 c_{t_{j}}^{1}, c_{t_{j}}^{2}, \dots, c_{t_{j}}^{k} 〉$ is the required capacities of $t_{j}$ , $k$ is the total number of capacity types, and $c_{t_{j}}^{m} \in {0, 1} (m = 1, \dots, k)$ represents whether capacity $m$ is demanded for executing task $t_{j}$ .

A WSN is composed of a set of sensor nodes that are dispersed in the target area. The networked system can be represented as a graph of nodes and their point-to-point links, $W = (N, E)$ , where $N = {n_{1}, n_{2}, \dots, n_{l}}$ indicates the sensor nodes and $E = {e_{ij} | i, j = 1, 2, \dots, l}$ is the collection of undirected edges which stands for the communications among the nodes. Here, we are concerned with wireless multi-hop networks in which a node can communicate with other nodes through multiple hops. Two nodes can directly communicate with each other if and only if there is an edge between them which is determined by their physical distance. In more detail, if the distance between two nodes is within a pre-set threshold, they can transmit data directly, otherwise multiple hops are required. The delay for transmitting messages between two nodes is primarily dependent on the bandwidth of the connection, while has nothing to do with the physical distance between them. To be simple, but without loss of generality, we assume the bandwidth of all connections to be identical, that is, the latency of sending and receiving messages are the same to any direct pairs of nodes. Meanwhile, we also assume that the topological coverage is perfect in WSNs.

As simple, inexpensive, and power-limited units, sensor nodes are the basic building blocks of a WSN. A sensor node is equipped with a sensing device which can acquire parameters of physical environment, in addition, it also consists of data processing and communicating components. However, as a tiny device with restricted capacity, a sensor node is usually designed for accomplishing a particular action, such as temperature sensors, humidity sensors, and pressure sensors. Formally, a binary vector $C_{n_{i}} = 〈 c_{n_{i}}^{1}, c_{n_{i}}^{2}, \dots, c_{n_{i}}^{k} 〉$ is attached to a sensor node to denote its capacity, where $c_{n_{i}}^{m} \in {0, 1} (m = 1, \dots, k)$ and $\sum c_{n_{i}}^{m} = 1$ , that is, a sensor node has and only has a particular capacity. Building on this, we can introduce the term “Heterogeneity” investigated in this study, and a heterogeneous WSN comprises a great deal of sensor nodes with distinct functionalities, where each sensor node can only sense and collect $a specific type$ of information. It is worth noting that the meaning of “heterogeneity” is intuitively different from the counterpart interpretation in previous work, which mainly concentrates on distinct computation power or battery energy level. This consideration makes our WSN model more suitable for a variety of applications.

Problem statement

Given a set of applications and each application is composed of $p$ tasks $T = {t_{1}, t_{2}, \dots, t_{p}}$ , a WSN consists of a set of $l$ $heterogeneous$ sensor nodes $N = {n_{1}, n_{2}, \dots, n_{l}}$ , the task allocation problem in WSN is a mapping $o : (N \times T) \to {0, 1}$ , where $o (n_{i}, t_{j}) = 1$ implies that task $t_{j}$ is assigned with node $n_{i}$ ; otherwise, it is not. A $valid$ distributed task allocation in heterogeneous WSN should satisfy the following requirements:

Each node has a unique type of capacity and only this particular capacity can be utilized by the corresponding task to which it is associated with.

The allocated tasks must be accomplished. For a task, its capacity requirements should necessarily be covered by overall capacities of the group of nodes to which it is allocated, that is, $\sum_{t_{j} is allocated to n_{i}} C_{n_{i}} \geq C_{t_{j}}$ .

The task allocation procedure must be performed in a decentralized manner, that is, each sensor node should decide on which task to undertake by itself, no central or external controller is required.

According to the above description, it is obvious that the issue we deal with in this work has significant distinction from the counterpart which has been well studied in the past. Due to the new features and constraints, there are several challenges to our model: (1) in a $heterogeneous$ WSN that contains sensor nodes with different capacities, the primary and key problem is to ensure the assigned task can be successfully executed, the absence of any kind of capacity is unacceptable. Thus, in our framework, the vital point is reasonably selecting a group of nodes that can collaboratively perform the task; and (2) to a WSN, a decentralized task allocation strategy means that each node should make decisions by itself and only local information is available. No central node will coordinate the operations of nodes and no global and synchronous messages are provided. From above analysis, we can find that traditional approaches for task allocation in WSN are not suitable for our issue, for that heterogeneity in these methods mainly refer to different computation speeds and initial energy states of each sensor node. In particular, they do not take the successful task execution as a constraint, that is, the capacity requirements of the task must be satisfied by the nodes to which it is assigned. Thus, the solutions of these methods may not provide sufficient capacities for task execution, that is, they may produce an $invalid$ solution in our case, let along be an optimal solution. Moreover, the feature of distribution is often neglected, which makes serious constraints on the scalability and robustness of these schemes.

Proposed algorithm

To achieve task assignment in a $heterogeneous$ WSN, a group of sensor nodes that can satisfy the required capacities should first be selected out. Thus, a simple but decentralized algorithm that can guarantee the execution of the task is presented, where the energy conservation and task deadline are not considered as vital constraints. Building on this, a modified task allocation strategy based on self-organization is proposed to further improve the efficiency and performance in terms of energy consumption, load balance, and execution time.

Task allocation strategy based on node capacity

As described above, tasks in a $heterogeneous$ WSN usually demands various kinds of capacities, and each capacity must be covered by a specific node that has the exact resource. Hence, a set of sensor nodes with proper capacities should be selected out. Sensor nodes are deployed and distributed randomly in the target area, and once being disposed, they can hardly change their places. In addition, no central node exists means that the global topology of the network and the complete information about each node, mainly includes capacity possessed by a node, are not available. Therefore, task allocation should be accomplished from the perspective of each sensor node, that is, a sensor node itself will make a decision on whether to join a task or not. Since this article considers a cooperative network, the sensor node that has the required capacity will definitely contribute to the corresponding task. The core issue is converted to locate the sensor nodes with proper capacities. Moreover, as a decentralized mechanism, no central control nodes, such as sink node or gateway, are in WSNs. Instead, we assume the node that perceives a mission or takes a task from outside as the manager node which is responsible for task assignment. Note that here “responsible” indicates that the manager node only serves as an initiator of task allocation procedure (it may also take part in the task), it will not compute a solution that illustrates whether a node should or should not be assigned with the task. To reduce energy consumption for communication and time for allocation, we present a capacity negotiation–based strategy which considers the capacities of both task and nodes. In this approach, the manager node negotiates with other nodes from nearby to faraway by means of multi-hop until all the requested capacities of the task are satisfied. The details of the algorithm is shown in Algorithm 1.

Algorithm 1. Task allocation algorithm based on node capacity.
1: Initialization Determine the manager node $n_{mag}$ ; $R (t_{j}) = {}$ ; TTL; set flags of all nodes to 0 2: Create Queue (Q) 3: Insert Queue (Q, $n_{mag}$ ); set flag of $n_{mag}$ to 1 4: while $C_{t_{j}}! = {} & & TTL > 0 & & Q! = {}$ do 5: $n_{i} =$ Out Queue (Q) 6: if $C_{t_{j}} \cap C_{n_{i}}! = {}$ then 7: $C_{t_{j}} = C_{t_{j}} - C_{n_{i}}$ 8: $R (t_{j}) = R (t_{j}) \cup n_{i}$ 9: end if 10: $TTL = TTL - 1$ 11: for each neighbor node $n_{k}$ of $n_{i}$ do 12: if flag of $n_{k}$ is 0 then 13: $n_{i}$ sends capacity request message $q = {n_{mag}, C_{t_{j}}, TTL}$ to $n_{k}$ 14: Insert Queue (Q, $n_{k}$ ) 15: end if 16: end for 17: end while

Algorithm 1. Task allocation algorithm based on node capacity.

1: Initialization Determine the manager node

n_{mag}

;

R (t_{j}) = {}

; TTL; set flags of all nodes to 0
2: Create Queue (Q)
3: Insert Queue (Q,

n_{mag}

); set flag of

n_{mag}

to 1
4: while

C_{t_{j}}! = {} & & TTL > 0 & & Q! = {}

do
5:

n_{i} =

Out Queue (Q)
6: if

C_{t_{j}} \cap C_{n_{i}}! = {}

then
7:

C_{t_{j}} = C_{t_{j}} - C_{n_{i}}

R (t_{j}) = R (t_{j}) \cup n_{i}

9: end if
10:

TTL = TTL - 1

11: for each neighbor node

n_{k}

n_{i}

do
12: if flag of

n_{k}

is 0 then
13:

n_{i}

sends capacity request message

q = {n_{mag}, C_{t_{j}}, TTL}

n_{k}

14: Insert Queue (Q,

n_{k}

)
15: end if
16: end for
17: end while

In Line 1, some variables and parameters are first initialized; $R (t_{j})$ is the group of nodes to which the task is initially assigned; $TTL$ is the maximum number of hops that the task can be forwarded, it is equivalent to the task deadline; flag indicates if a node has been visited or not. In addition, a manager node is determined, in order to avoid excessive power dissipation, the manager node is selected randomly. Then, the manager node is inserted into a queue $Q$ . In each iteration, the first node in $Q$ is popped up and $TTL$ decreases by 1. If the node has the required capacity, it will be added to $R (t_{j})$ , in addition, the remaining required capacities of the task is updated. After that, the node will send a request message $q = {n_{mag}, C_{t_{j}}, TTL}$ to its neighbor nodes which have not been visited before. Message $q$ contains the ID of manager node $n_{mag}$ , the capacities that is currently lack of, as well as the residual hops $TTL$ . Meanwhile, the neighbor node will be inserted into $Q$ . The process will be operated by the neighbor(s) of current node until task is successfully fulfilled or $TTL$ becomes 0 or there is no node in $Q$ .

Improved task allocation strategy based on self-organization mechanism

In the above section, we propose an ordinary but distributed approach which can provide a feasible solution to task allocation in $heterogeneous$ WSNs. The advantage is that this method can deal with tasks with distinct capacity requirements, while the main drawback lies in that it does not put special emphasis on energy consumption and real-time property in the process, which is taken as two crucial features to task allocation in WSNs. Traditional approaches integrate these two metrics into a target function and then an algorithm is devised to present the optimal or sub-optimal solution. Nevertheless, this method is not applicable in distributed WSNs for that it can hardly find a sensor node which can operate the algorithm due to its limited energy and computation capability. Consequently, we deal with this problem from two aspects in this study. In our framework, the key issue is to locate the nodes with requested capacities, this information can be acquired through past task allocation. Specifically, the manager node is able to collect the capacities of some nodes during previous task allocation, especially the final nodes in $R (t_{j})$ . This process can be described as follows: after receiving the task query $q$ , a node that has the lacked capacity of the task will send a response message to the manager node which contains the node’s ID and capacity, and the manager node will store this information on its local memory. Note that only the first node that provides the particular capacity is recorded by the manager node, even in the allocation of various tasks. Thus, for each node, it needs to send message to the manager node at most one time, this can bring great benefits to energy conservation of WSN. After having the capacity information of some nodes, the manager node can easily determine the target nodes when new tasks arrive. Another vital element which may severely affect the performance of task allocation mechanism is the structure of WSN, that is, how sensor nodes are arranged. In more detail, an optimized path will be established between manager node and target nodes with the purpose of minimizing energy expenditure and allocation time. In this work, we refer to these two processes as self-organization to task allocation in WSNs. In summary, the advantages of self-organization based task allocation strategy are listed as follows:

By utilizing past collaboration, sensor nodes with appropriate capacities can be quickly localized, which can effectively avoid the waste of energy and time due to blind search.

By setting up an optimized path between the pair of manager node and target node, the time and energy consumption can be further reduced.

The self-organization mechanism is briefly divided into two steps which is detailed as below.

Candidate sensor node selection

When a WSN is just deployed, each node has no knowledge about capacities possessed by other nodes. By adopting task allocation strategy in Algorithm 1, the nodes with distinct capacities can be sought out. To a manager node, after distributing a task successfully, it can acquire capacities of final nodes as well as intermediate nodes. Afterward, the manager node should record this information as it may be helpful to future task allocation. In particular, if a specific capacity associated with a node is detected for the first time, it will be kept by the manager node. As the search order is from nearby to faraway, the recorded nodes are relatively close to the manager. Thus, from the perspective of capacity exploration, those nodes will be considered as potential ones for self-organization. However, we assume that the capacities of tasks on a certain manager node are similar, this assumption is reasonable because sensor nodes distributed in a specific area are unlikely to perform a variety of different tasks. Thus, another important factor that may have an impact on the decision of candidate nodes is the frequency that a node has contributed its capacity during previous task allocation. In more detail, if a node often provides its capacity in the past, it will have a higher probability to be selected as a candidate, whereas a node whose capacity is occasionally required by tasks is unlikely to be helpful in subsequent task allocation. Thus, a candidate selection should be considered comprehensively from these two aspects, that is, the node’s capacity and the frequency of using the capacity. The process is demonstrated in Algorithm 2.

Algorithm 2. Candidate node determination.
1: Initialization Candidate nodes = {}, $Θ = {θ_{n_{1}}, θ_{n_{2}}, \dots, θ_{n_{l}}}, θ_{n_{i}} = 0, (i = 1, 2, \dots, l)$ 2: for each task $t_{j} \in T_{prev}$ do 3: for each node $n_{i} \in R (t_{j})$ do 4: $θ_{n_{i}} = θ_{n_{i}} + 1$ 5: end for 6: end for 7: for each node $n_{i}$ do 8: $R a_{n_{i}} = θ_{n_{i}} / #$ of tasks in $T_{prev}$ 9: if $R a_{n_{i}} \geq ρ$ then 10: Candidate nodes = Candidate nodes $\cup n_{i}$ 11: end if 12: end for

Algorithm 2. Candidate node determination.

1: Initialization Candidate nodes = {},

Θ = {θ_{n_{1}}, θ_{n_{2}}, \dots, θ_{n_{l}}}, θ_{n_{i}} = 0, (i = 1, 2, \dots, l)

2: for each task

t_{j} \in T_{prev}

do
3: for each node

n_{i} \in R (t_{j})

do
4:

θ_{n_{i}} = θ_{n_{i}} + 1

5: end for
6: end for
7: for each node

n_{i}

do
8:

R a_{n_{i}} = θ_{n_{i}} / #

of tasks in

T_{prev}

9: if

R a_{n_{i}} \geq ρ

then
10: Candidate nodes = Candidate nodes

\cup n_{i}

11: end if
12: end for

In Line 1, parameter $θ_{n_{i}}$ stands for the times that node $n_{i}$ has been successfully assigned with tasks, and it is initialized to 0. Then, $θ_{n_{i}}$ is calculated by counting how many times node $n_{i}$ has appeared in past allocated task set $T_{prev}$ (Lines 2–6), the number is normalized by the total amount of tasks in $T_{prev}$ (Line 8). Finally, a node $n_{i}$ is determined to be a candidate if the task allocation ratio $R a_{n_{i}}$ is greater than a predefined threshold $ρ$ , which means that the manager node often delegates tasks for node $n_{i}$ .

Structural adaptation for task allocation

To a general WSN, once it is deployed, a specific routing protocol will be operated automatically, which is primarily responsible for effective data transmission. As a power-constrained network, the routing protocol in WSN is mainly concerned with how to save energy of individual node and prolong the lifetime of the whole network. In comparison, the major role of a task allocation path is assigning tasks to appropriate nodes that can cooperatively perform the task. The principal consideration is constructing an efficient path between the manager node and the target nodes, and following it, the nodes with required resources can be reached as soon as possible. Obviously, in this work, we focus on arranging and rearranging a superior path for task allocation in terms of energy savings and allocation time.

Since large number of sensor nodes are densely deployed, the two nodes that are direct neighbors are close to each other. Rather than sending information directly to the target node through single-hop communication which is usually correlated with high energy consumption, the multi-hop communication manner is preferred. Thus, for task allocation, the capacity request message $q$ is sequentially propagated from nodes to nodes until the task capacities are totally satisfied. From the perspective of energy conservation to an individual node, it intends to send messages to node(s) that is closest to it. Nevertheless, if the pairs of nodes along a path is close to each other, the path will contain many nodes. Each node will inevitably expends power for sending and receiving messages which may be unfavorable to energy savings of the whole network. However, real-time property is a primarily requirement to task allocation in many applications. With radio communication, the propagation delay for information is mainly determined by the bandwidth of the channel between the two nodes. As the bandwidth in the whole WSN is assumed to be identical, the time for allocating a task depends on the number of hops for task transmission. Therefore, it is clear that a good transmission path of a task should make a trade-off between communication distances of nodes and the number of hops.

So far, we can demonstrate the self-organization mechanism in WSN. This problem can be boiled down to the following: in the beginning stage, that is, when a WSN is initially deployed, no historical information is available; therefore, the manager node will adopt Algorithm 1 to assign tasks. After completing a certain amount of tasks, the manager node can obtain messages of a few nodes with distinct capacities that have been contributed in the past. Then, the nodes to which tasks are often assigned are added to the candidate set (Algorithm 2). Afterward, the manager node will adjust the original task propagation paths and establish new paths with the candidate sensor nodes. The purpose of this adaptation is minimizing energy dissipation and allocation time for future task allocation. From above analysis, in order to achieve this goal, an optimized task delivering path is to be built up between the manager node and target nodes. Here, the optimum means that a good balance should be kept between the communication distance over two nodes and the hop number. This issue can be converted to the problem of finding a minimum hop path under the constraint that any node through the path will forward the task allocation message only to node that is within its maximum communication range. We can map this problem to the traditional problem of searching shortest paths in graph theory by regarding manager node as the source node and setting the weight of each edge to be identical. Obviously, there exist a few algorithms that can be adopted to solve this question, such as Dijkstra algorithm, which is simple but efficient. It is worth noting that this self-organization is a continuous and dynamic process, that is, the paths for task allocation will evolve as new tasks arrive sequentially which can guarantee the suitability for dynamism of the environment.

We also notice that to self-organization mechanism, the nodes in the candidate set may be repeatedly assigned with tasks afterward. This is detrimental to the balance of energy expenditure in WSN. However, by optimizing task allocation paths, the sensor nodes which are originally along the transmitting route may be removed and they do not have to forward specific task information, this will significantly reduce energy consumption. Another noteworthy issue is that the proposed strategy still can operate even when some nodes are out of work. In fact, as long as the task information can be sent to the appropriate nodes, the task will be allocated successfully. In particular, if a node along the path is destroyed, any node(s) that will transmit the task to the target nodes can be used instead of it.

Computation and communication overhead analysis

Intuitively, the proposed task allocation strategy can be briefly divided into two parts, one is task allocation based on node capacity and the other is self-organization mechanism. To the former, inserting a node to $Q$ and removing a node from $Q$ need $O (1)$ operation, respectively, the matching process of a node’s capacity with a task’s capacity requires $O (1)$ calculation, and the update of $TTL$ can be done in $O (1)$ . During this process, only $O (1)$ message needs to be sent. Consequently, in the worse case, a task can be allocated after visiting all nodes, and the computation and communication complexity are both $O (l)$ , where $l$ is the number of nodes in WSN. To self-organization mechanism, candidate node determination can be done in $O (l_{prev})$ , where $l_{prev}$ is the number of nodes that has joined tasks in $T_{prev}$ . The adjustment of connections between nodes can be implemented by Dijkstra algorithm, it has the complexity of $O (l_{cand}^{2})$ , where $l_{cand}$ is the number of nodes in candidate node set.

Simulation and results

To evaluate the performance of the proposed task allocation strategy, we conduct a series of simulated experiments. To the best of our knowledge, there does not exist any mechanism that can deal with our issue which considers a different capacity request of task in the process of allocation. However, many approaches have been proposed to deal with traditional task allocation problems in WSN. Among these methods, the PSO-based task allocation algorithm has been widely used in WSNs and has been verified to be with good performance.²¹ However, the original PSO-based algorithm concentrated on task allocation in heterogeneous WSNs where the sensor nodes are different in processing speed and power expenditure. Obviously, this method cannot be directly applied to solve the problem that a task requires various capacities. Thus, we extend this approach to make it suitable for our model and make a comparison with the proposed strategy. In more detail, we assume each sensor node has a specific capacity, all sensor nodes are classified into groups according to their capacities. To allocate a task, an initial feasible solution (particle) can be generated by randomly choosing a node with required capacity from each group, then the velocity and position of each particle are updated according to the value of fitness function which is concerned with energy expenditure and load balance. When the predefined maximum number of iterations is reached, the particle with the global best fitness value is referred to as the ultimate solution. Furthermore, to reveal the performance improvements gained by employing self-organization strategy, we also compare the proposed two approaches with and without self-organization scheme.

Experimental setup

In our simulation study, the WSN consists of $n$ nodes that are distributed uniformly randomly in a rectangle region of 200 by 200 m. To heterogeneity, there are 12 types of capacities to be available to the tasks and nodes, a task demands eight different types of capacities which is set randomly and a sensor node is endowed with a random capacity. In the experiment, 30 tasks are grouped into an application and applications arrive at WSN sequentially, and to each application, a manager node is selected out randomly. Here, we adopt a popular energy consumption model as presented in Heinzelman et al.²² and Wang and Chandrakasan,²³ which calculated the energy dissipation for transmitting an l-bit data over a distance $d$ as

E_{Tx} (l, d) = {\begin{matrix} l E_{elec} + l ε_{fs} d^{2} d < d_{0} \\ l E_{elec} + l ε_{mp} d^{4} d \geq d_{0} \end{matrix}

and to receive the data, a node consumes energy as

E_{Rx} (l) = E_{elec} l

where $E_{elec}$ , $ε_{fs}$ , and $ε_{mp}$ are hardware dependent variables, and these parameters are set as follows: $E_{elec} = 50 nJ / bit$ , $ε_{fs} = 10 pJ / bit / m^{2}$ , and $ε_{mp} = 0.0013 pJ / bit / m^{4}$ . The length $l$ of messages for allocating tasks is set randomly in the range [4000, 6000] bits. Generally, other parameters are set as follows: the maximum communication distance of two sensor nodes is set to be 50 m and the deadline of each task is selected from a random distribution in [25, 30].

To comprehensively validate the effectiveness of the proposed approaches, four performance metrics are taken into account, which are as follows:

Energy consumption. It is the total energy expended by all the sensor nodes in WSN. To each task allocation, it includes energy expenditure with transmitting and receiving messages from manager node to intermediate nodes and target nodes.

Energy distribution. It is measured by the standard deviation of residual energy of all nodes, and this metric has a significant impact on the lifetime of WSN. A network with a balanced energy distribution can surely survive for a long time.

Deadline missing ratio. It is an index for real-time characteristic and is calculated by the ratio between the successfully assigned tasks and total tasks.

Algorithm execution time. It is the time for operating various algorithms themselves; here, the time is calculated as the total time for assigning an application that includes 30 tasks.

For ease of reference, we refer to our fundamental method as task allocation with node capacity (TA-NC), its extension by employing self-organization is called TA-S, and the benchmark which allocates tasks by PSO is referred to as TA-PSO.

Results and analysis

Performance with the number of tasks

In the first set of experiments, we examine the performance impact of varying the number of tasks. Here, the number of sensor nodes is set to be 100, and the number of applications changes from 1 to 10 (indicating task increases from 30 to 300 with a step of 30). The results are shown in Figure 1. From Figure 1(a) and (b), it can be seen that TA-S and TA-PSO exhibit similar performance in energy consumption and energy standard deviation, both noticeably outperform TA-NC. Obviously, with the increase in the task number, energy dissipation of all the three algorithms rises proportionally. However, TA-S and TA-PSO expend much less energy compared with TA-NC, and the gap is increasing with the growing of task number, this is because TA-S employs self-organization technology to fully utilize historical interaction information. In so doing, it can effectively avoid having access to nodes with undesired capacities which will otherwise incur excessive energy consumption. To TA-PSO, one of its goals is to minimize energy consumption, thus it can surely provide a solution that has the highest quality. For the similar reason, TA-S and TA-PSO achieve remarkable improvement in terms of energy consumption deviation in comparison with TA-NC, which implies that TA-S and TA-PSO can significantly extend network lifetime. Furthermore, Figure 1(c) demonstrates the deadline missing ratio of various methods, and we observe that TA-S is much more competent to allocate tasks before their deadlines (in all cases, the deadline missing ratio is below 30%), while TA-PSO shows the poorest performance (usually over 90% task cannot be successfully allocated due to the missing of deadlines). This can be explained by the fact that by adopting self-organization, the manager node can establish optimal paths between itself and the target nodes which have proper capacities; thus, when a new task arrives, the manager node will transmit it to the desired nodes through paths with lowest hops. In comparison, TA-PSO does not take hop into account, it may find nodes that are remote from the manager node which will inevitably improve the hop for task allocation. Regarding the execution time of various approaches, the result is illustrated in Figure 1(d). There is no doubt that TA-PSO consumes much more time than the other two methods, almost several orders of magnitude higher. TA-NC runs with minimum time for its extreme simplicity and is superior to TA-S, but the gap between them is slight. In summary, from above experiments, we can conclude that TA-S has the best comprehensive performance.

Figure 1.

Performance with the number of tasks: (a) energy consumption, (b) energy standard deviation, (c) deadline missing ratio, and (d) algorithm execution time.

Performance with the number of nodes

In this section, a group of experiments are done to examine the impact on the three algorithms’ performance with different number of nodes, which can verify the scalability of the these approaches. We scaled the number of nodes in WSN from 70 to 160, and the number of applications is set to 1 (30 tasks). Figure 2 plots the results. Figure 2(a) shows the energy consumption of various approaches, to TA-NC and TA-S, and they allocate tasks by delivering messages and matching the capacities within a local range of the WSN, thus the energy expenditure has little to do with the size of the network. To TA-PSO, as the power depleted for operating the algorithm itself is not taken into account, energy consumption is independent of the number of nodes. Here, both TA-S and TA-PSO outperform TA-NC, and the former two schemes achieve comparable performance. Likewise, on deadline missing ratio shown in Figure 2(c), the results are unpredictable, whereas TA-S can successfully assign much more tasks than the other two methods. With regard to the energy standard deviation, from Figure 2(b), it is dropping with the increase in the number of nodes; the reason is that when the size of the WSN becomes larger, the workload will be distributed on more nodes which can better balance energy dissipation. Similar to the outcomes in the last section, in terms of execution time, TA-NC has the top performance, TA-S needs a little more time to be implemented, while the computation complexity of TA-PSO is excessively higher compared with the other two approaches, and it is dramatically affected by the node number due to the exponential increment in searching space with the number of nodes. In conclusion, the proposed TA-S strategy performs well in scalability and is able to adapt to large-scale WSNs.

Figure 2.

Performance with the number of nodes: (a) energy consumption, (b) energy standard deviation, (c) deadline missing ratio, and (d) algorithm execution time.

Conclusion

In this article, we study the issue of task allocation of collaborative applications in heterogeneous WSNs. We assume that a task may require distinct types of capacities, and accordingly, sensor nodes have various capacities that can be exploited for task execution. A novel scheme is developed to deal with this problem. The main idea is by transmitting the task through part of the network, the nodes with the appropriate capacities will form a group to be assigned with the task. Compared with conventional task allocation methods in WSN, the proposed approach has two desired features. First, only local information is needed, that is, it is a distributed strategy which makes it especially suitable for large-scale networks. Second, it considers heterogeneity in WSN, which makes it more applicable in more general situations. In addition, an improved version of the approach that synthesizes self-organization concept is presented. By referring to the previous information, the sensor nodes that are frequently allocated with tasks are selected as candidates, then the structural relations among nodes will be adapted such that subsequent tasks can be assigned to proper nodes immediately and in time. We conducted a series of experiments to evaluate the feasibility and effectiveness of our approaches, and the results show that the self-organization-based approach has the best comprehensive performance. Compared with PSO-based method, it achieves significant improvement in task deadline missing ratio as well as execution time. Compared with the fundamental approach, it reduces energy consumption and balances workload.

In this study, only a simple self-organization mechanism is adopted, and in the future, we intend to develop a more comprehensive self-organization mechanism to further improve the performance of the strategy. Moreover, we are also interested in applying the proposed approaches in real-world scenarios to test their practical performance. Another valuable issue is how to guarantee the topological coverage after the connections among nodes are adjusted.

Footnotes

Handling Editor: Valerio Freschi

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported, in part, by the National Natural Science Foundation of China under grant nos 61472344 and 61401387, the Natural Science Foundation of Jiangsu Province under grant no. BK20150460, and the Innovation Foundation of Yangzhou University.

References

Wan

Han

Shu

et al . Distributed parameter estimation for mobile wireless sensor network based on cloud computing in battlefield surveillance system. IEEE Access 2015; 3: 1729–1739.

Wang

Gao

et al . An energy-efficient reliable data transmission scheme for complex environmental monitoring in underwater acoustic sensor networks. IEEE Sens J 2016; 16(11): 4051–4062.

Lersteau

Rossi

Sevaux

. Robust scheduling of wireless sensor networks for target tracking under uncertainty. Eur J Oper Res 2016; 252(2): 407–417.

Reina

Askalani

Toral

et al . A survey on multihop ad hoc networks for disaster response scenarios. Int J Distrib Sens N 2015; 2015(3): 1–16.

Chen

Guo

Chen

. Research on dynamic alliance of task allocation and its algorithms in wireless sensor networks. J Commun 2009; 17(3): 48–55.

Dai

Chang

Shen

. An optimal task scheduling algorithm in wireless sensor networks. Int J Comput Commun 2011; 6: 101–112.

Dai

Chen

et al . A multi-objective optimization algorithm of task scheduling in WSN. Int J Comput Commun 2014; 9(2): 160–171.

Wang

Han

Jiang

et al . A distributed task allocation strategy for collaborative applications in cluster-based wireless sensor networks. Int J Distrib Sens N 2014; 2014: 964595.

Delicato

Pires

et al . Efficient allocation of resources in multiple heterogeneous wireless sensor networks. J Parallel Distr Com 2014; 74(1): 1775–1788.

10.

Yang

Qiu

Meng

et al . Task coalition formation and self-adjustment in the wireless sensor networks. Int J Commun Syst 2014; 27(10): 2241–2254.

11.

Salman

Ahmad

Al-Madani

. Particle swarm optimization for task assignment problem. Microprocess Microsy 2002; 26(8): 363–371.

12.

Jin

Gluhak

et al . An intelligent task allocation scheme for multihop wireless networks. IEEE T Parall Distr 2012; 23(3): 444–451.

13.

Heinzelman

Chandrakasan

Balakrishnan

. An application-specific protocol architecture for wireless microsensor networks. IEEE T Wirel Commun 2002; 1(4): 660–669.

14.

Liao

. Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks. IEEE Sens J 2013; 13(5): 1498–1506.

15.

Tian

Ekici

. Cross-layer collaborative in-network processing in multihop wireless sensor networks. IEEE T Mobile Comput 2007; 6(3): 297–310.

16.

Xie

Qin

. An energy-delay tunable task allocation strategy for collaborative applications in networked embedded systems. IEEE T Comput 2008; 57(3): 329–343.

17.

Abdelhak

Gurram

Ghosh

et al . Energy-balancing task allocation on wireless sensor networks for extending the lifetime. In: Proceedings of the 53rd IEEE international Midwest symposium on circuits and systems (MWSCAS), Seattle, WA, 1–4 August 2010, pp.781–784. New York: IEEE.

18.

Wang

Han

Jiang

et al . A task allocation algorithm based on score incentive mechanism for wireless sensor networks. Int J Distrib Sens N 2015; 2015: 5.

19.

Pilloni

Navaratnam

Vural

et al . TAN: a distributed algorithm for dynamic task assignment in WSNs. IEEE Sens J 2014; 14(4): 1266–1278.

20.

Kulkarni

Venayagamoorthy

. Particle swarm optimization in wireless-sensor networks: a brief survey. IEEE T Syst Man Cy C 2011; 41(2): 262–267.

21.

Yang

Zhang

Ling

et al . Task allocation for wireless sensor network using modified binary particle swarm optimization. IEEE Sens J 2014; 14(3): 882–892.

22.

Heinzelman

Chandrakasan

Balakrishnan

. Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Hawaii international conference on system sciences, Maui, HI, 7 January 2000, pp.3005–3014. New York: IEEE.

23.

Wang

Chandrakasan

. Energy-efficient DSPs for wireless sensor networks. IEEE Signal Proc Mag 2002; 19(4): 68–78.