Loris Marchal
email: loris.marchal@ens-lyon.fr

Oliver Sinnen
email: o.sinnen@auckland.ac.nz

Frédéric Vivien
email: frederic.vivien@inria.fr

Scheduling tree-shaped task graphs to minimize memory and makespan

Keywords: scheduling, makespan-memory tradeoff, treeshaped task-graphs

This paper investigates the execution of treeshaped task graphs using multiple processors. Each edge of such a tree represents a large IO file. A task can only be executed if all input and output files fit into memory, and a file can only be removed from memory after it has been consumed. Such trees arise, for instance, in the multifrontal method of sparse matrix factorization. The maximum amount of memory needed depends on the execution order of the tasks. With one processor the objective of the tree traversal is to minimize the required memory. This problem was well studied and optimal polynomial algorithms were proposed.

Here, we extend the problem by considering multiple processors, which is of obvious interest in the application area of matrix factorization. With the multiple processors comes the additional objective to minimize the time needed to traverse the tree, i.e., to minimize the makespan. Not surprisingly, this problem proves to be much harder than the sequential one. We study the computational complexity of this problem and provide an inapproximability result even for unit weight trees. Several heuristics are proposed, each with a different optimization focus, and they are analyzed in an extensive experimental evaluation using realistic trees.

I. INTRODUCTION

Parallel workloads are often modeled as task graphs, where nodes represent tasks and edges represent the dependencies between tasks. There is an abundant literature on task graph scheduling when the objective is to minimize the total completion time, or Makespan. However, as the size of the data to be processed is increasing, the memory footprint of the application must be optimized as it can have a dramatic impact on the algorithm execution time. This is best exemplified with an application which, depending on the way it is scheduled, will either fit in the memory, or will require the use of swap mechanisms or out-ofcore techniques. There are very few existing studies on the minimization of the memory footprint when scheduling task graphs, and even fewer of them targeting parallel systems.

We consider the following memory-aware parallel scheduling problem for rooted trees. The nodes of the tree correspond to tasks, and the edges correspond to the dependencies among the tasks. The dependencies are in the form of input and output files: each node takes as input several large files, one for each of its children, and it produces a single large file, and the different files may have different sizes. Furthermore, the execution of any node requires its execution file to be present; the execution file can be seen as the program of the task. We are to execute such a set of tasks on a parallel system made of p identical processing resources sharing the same memory. The execution scheme corresponds to a schedule of the tree where processing a node of the tree translates into reading the associated input files and producing the output file. How can the tree be scheduled so as to optimize the memory usage? Modern computing platforms exhibit a complex memory hierarchy ranging from caches to RAM and disks and even sometimes tape storage, with the classical property that the smaller the memory, the quicker. Thus, to avoid large running times, one usually wants to avoid the use of memory devices whose IO bandwidth is below a given threshold: even if out-of-core execution (when large data are unloaded to disks) is possible, this requires special care when programming the application and one usually wants to stay in the main memory (RAM). This is why in this paper, we are interested in the question of minimizing the amount of main memory needed to completely process an application.

Throughout the paper, we consider in-trees where a task can be executed only if all its children have already been executed. (This is absolutely equivalent to considering outtrees as a solution for an in-tree can be transformed into a solution for the corresponding out-tree by just reversing the arrow of time, as outlined in [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF].) A task can be processed only if all its files (input, output, and execution) fit in currently available memory. At a given time, many files may be stored in the memory, and at most p tasks may be processed by the p processors. This is obviously possible only if all tasks and execution files fit in memory. When a task finishes, the memory needed for its execution file and its input files is released. Clearly, the schedule which determines the processing times of each task plays a key role in determining which amount of main memory is needed for a successful execution of the whole tree.

The first motivation for this work comes from numerical linear algebra. Tree workflows (assembly or elimination trees) arise during the factorization of sparse matrices, and the huge size of the files involved makes it absolutely necessary to reduce the memory requirement of the factorization. The sequential version of this problem (i.e., with p = 1 processor) has already been studied. Liu [START_REF] Liu | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF] discusses how to find a memory-minimizing traversal when the traversal is required to correspond to a postorder traversal of the tree. In the follow-up study [START_REF]An application of generalized tree pebbling to sparse matrix factorization[END_REF], an exact algorithm is shown to solve the problem, without the postorder constraint on the traversal. Recently, some of us [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF] proposed another algorithm to find a memory-optimal traversal, which proved to be faster on existing elimination trees, although being of the same worst-case complexity (O(n 2 )).

The parallel version of this problem is a natural continuation of these studies: when processing large elimination trees, it is very meaningful to take advantage of parallel processing resources. However, to the best of our knowledge, there exist no theoretical studies for this problem. The key contributions of this work are:

• The proof that the parallel variant of the pebble game problem is NP-complete. This shows that the introduction of memory constraints, in the simplest cases, suffices to make the problem NP-hard. • The proof that no algorithm can simultaneously deliver a constant-ratio approximation for the memory minimization and for the makespan minimization. • A set of heuristics having different optimizing focus.

• An exhaustive set of simulations using realistic tree shaped task graphs to assess the relative and absolute performance of these heuristics. The rest of this paper is organized as follows. Section II reviews related studies. The notation and formalization of the problem are introduced in Section III. Complexity results are presented in Section IV while Section V proposes different heuristics to solve the problem, which are evaluated in Section VI.

II. BACKGROUND AND RELATED WORK A. Sparse matrix factorization

As mentioned above, determining a memory-efficient tree traversal is very important in sparse numerical linear algebra. The elimination tree is a graph theoretical model that represents the storage requirements, and computational dependencies and requirements, in the Cholesky and LU factorization of sparse matrices. In a previous study, we have described how such trees are built, and how the multifrontal method organizes the computations along the tree [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. This is the context of the founding studies of Liu [START_REF] Liu | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF], [START_REF]An application of generalized tree pebbling to sparse matrix factorization[END_REF] on memory minimization for postorder or general tree traversals presented in the previous section. Memory minimization is still a concern in modern multifrontal solvers when dealing with large matrices. Among other, efforts have been made to design dynamic schedulers that takes into account dynamic pivoting (which impacts the weights of edges and nodes) when scheduling elimination trees with strong memory constraints [START_REF] Guermouche | Memory-based scheduling for a parallel multifrontal solver[END_REF], or to consider both task and tree parallelism with memory constraints [START_REF] Agullo | Robust memory-aware mappings for parallel multifrontal factorizations[END_REF]. While these studies try to optimize memory management in existing parallel solvers, we aim at designing a simple model to study the fundamental underlying scheduling problem.

B. Scientific workflows

The problem of scheduling a task graph under memory constraints also appears in the processing of scientific workflows whose tasks require large I/O files. Such workflows arise in many scientific fields, such as image processing, genomics or geophysical simulations. The problem of task graphs handling large data has been identified in [START_REF] Ramakrishnan | Scheduling data-intensiveworkflows onto storage-constrained distributed resources[END_REF] which proposes some simple heuristic solutions. Surprisingly, in the context of quantum chemistry computations, Lam et al. [START_REF] Lam | Memory-optimal evaluation of expression trees involving large objects[END_REF] have recently rediscovered the algorithm published in 1987 in [START_REF]An application of generalized tree pebbling to sparse matrix factorization[END_REF].

C. Pebble game and its variants

On the more theoretical side, this work builds upon the many papers that have addressed the pebble game and its variants. Scheduling a graph on one processor with the minimal amount of memory amounts to revisiting the I/O pebble game with pebbles of arbitrary sizes that must be loaded into main memory before firing (executing) the task. The pioneering work of Sethi and Ullman [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF] deals with a variant of the pebble game that translates into the simplest instance of our problem when all input/output files have weight 1 and all execution files have weight 0. The concern in [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF] was to minimize the number of registers that are needed to compute an arithmetic expression. The problem of determining whether a general DAG can be executed with a given number of pebbles has been shown NP-hard by Sethi [START_REF] Sethi | Complete register allocation problems[END_REF] if no vertex is pebbled more than once (the general problem allowing recomputation, that is, re-pebbling a vertex which have been pebbled before, has been proven PSPACE complete [START_REF] Gilbert | The pebbling problem is complete in polynomial space[END_REF]). However, this problem has a polynomial complexity for tree-shaped graphs [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF].

To the best of our knowledge, there have been no attempts to extend these results to parallel machines, with the objective of minimizing both memory and total execution time. We present such an extension in Section IV.

III. MODEL AND OBJECTIVES

A. Application model

We consider in this paper a tree-shaped task-graph T composed of n nodes, or tasks, numbered from 1 to n. Nodes in the tree have an output file, an execution file (or program), and several input files (one per child). More precisely:

• Each node i in the tree has an execution file of size n i and its processing on a processor takes time w i .

• Each node i has an output file of size f i . If i is not the root, its output file is used as input by its parent parent(i); if i is the root, its output file can be of size zero, or contain outputs to the outside world. • Each non-leaf node i in the tree has one input file per child. We denote by Children(i) the set of the children of i. For each child j ∈ Children(i), task j produces a file of size f j for i. If i is a leaf-node, then Children(i) = ∅ and i has no input file: we consider that the initial data of the task either reside in its execution file or are read from disk (or received from the outside word) during the execution of the task. During the processing of a task i, the memory must contain its input files, the execution file, and the output file. The memory needed for this processing is thus:

  j∈Children(i) f j   + n i + f i
After i has been processed, its input files and program are discarded, while its output file is kept in memory until the processing of its parent.

B. Platform model and objectives

In this paper, our goal is to design the simpler platform model which allows to study memory minimization on a parallel platform. We thus consider p identical processors which share a single memory. We do not consider here a hard constraint on the memory, but we rather include memory in the objectives. We thus consider multi-criteria optimization with the following two objectives:

• Makespan. Our first objective is the classical makespan, or total execution time, which corresponds to the times-span between the beginning of the execution of the first leaf task and the end of the processing of the root task. • Memory. Our second objective is the amount of memory needed for the computation. At each time step, some files are stored in the memory and some task computations occur, which induces a memory usage. The peak memory is the maximum usage of the memory over the whole schedule, which we aim at minimizing.

IV. COMPLEXITY RESULTS IN THE PEBBLE GAME MODEL

Since there are two objectives, the decision version of our problem can be stated as follows.

Definition 1 (BiObjectiveParallelTreeScheduling). Given a tree-shaped task graph T provided with memory weights and task durations, p processors, and two bounds B Cmax and B mem , is there a schedule of the task graph on the processors whose makespan is not larger than B Cmax and whose peak memory is not larger than B mem ?

This problem is obviously NP-complete. Indeed, when there are no memory constraints (B mem = ∞) and when the task tree does not contain any inner node, that is, when all tasks are either leaves or the root, then our problem is equivalent to scheduling independent tasks on a parallel platform which is an NP-complete problem as soon as tasks have different execution times [START_REF] Lenstra | Complexity of machine scheduling problems[END_REF]. On the contrary minimizing the makespan for a tree of same-size tasks can be solve in polynomial-time when there are no memory constraints [START_REF] Hu | Parallel sequencing and assembly line problems[END_REF]. In this section, we consider the simplest variant of the problem. We assume that all input files have the same size (∀i, f i = 1) and no extra memory is needed for computation (∀i, n i = 0). Furthermore, we assume that the processing of each node takes a unit time: ∀i, w i = 1. We call this variant of the problem the Pebble Game model since it perfectly corresponds to pebble game problems introduced above: the weight f i = 1 corresponds to the pebble put on one node once it has been processed and its results is not yet discarded. Processing a node requires to put an extra pebble on this node and is done in unit time.

In this section, we first show that even in this simple variant, the introduction of memory constraints (a limited number of pebbles) makes the problem NP-hard (Section IV-A). Then, we show that when trying to minimize both memory and makespan, it is not possible to get a solution with a constant approximation ratio for both objectives (Section IV-B).

A. NP-completeness Theorem 1. The BiObjectiveParallelTreeScheduling problem is NP-complete in the Pebble Game model (i.e., with ∀i, f i = w i = 1, n i = 0).

Proof: First, it is straightforward to check that the problem is in NP: given a schedule, it is easy to compute its peak memory and makespan.

To prove the problem NP-completeness, we perform a reduction from 3-PARTITION, which is known to be NPcomplete in the strong sense [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF]. We consider the following instance I 1 of the 3-PARTITION problem: let a i be 3m integers and B an integer such that a i = mB. We consider the variant of the problem, also NP-complete, where ∀i, B/4 < a i < B/2. To solve I 1 , we need to solve the following question: does there exist a partition of the a i 's in m subsets S 1 , . . . , S m , each containing exactly 3 elements, such that, for each S k , i∈S k a i = B. We build the following instance I 2 of our problem, illustrated on Figure 1. The tree contains a root r with 3m children, the N i 's, each one corresponding to a value a i . Each node N i has 3m×a i children, which are leaf nodes. The question is to find a schedule of this tree on p = 3mB processors, whose peak memory is not larger than B mem = 3m × B + 3m and whose makespan is not larger than B Cmax = 2m + 1.

Assume first that there exists a solution to I 1 , i.e., that there are m subsets S k of 3 elements with i∈S k a i = B. In this case, we build the following schedule: root

N 1 L 1 1 L 1 2 . . . L 1 3m×a1 N 2 L 2 1 L 2 2 . . . L 2 3m×a2 . . . N 3m L 3m 1 L 3m 2 . . . L 3m 3m×a3m Figure 1.
Tree used for the NP-completeness proof

• At step 1, we process all the nodes L i1 x , L j1 y , and L k1 z with S 1 = {a i1 , a j1 , a k1 }. There are 3mB = p such nodes, and the amount of memory needed is also 3mB. • At step 2, we process the nodes N i1 , N j1 , N k1 . The memory needed is 3mB + 3.

• At step 2n + 1, with 1 ≤ n ≤ m -1, we process the 3mB = p nodes L in x , L jn y , L kn z
with S n = {a in , a jn , a kn }. The amount of memory needed is 3mB + 3n (counting the memory for the output files of the N t nodes previously processed).

• At step 2n + 2, with 1 ≤ n ≤ m -1, we process the nodes N in , N jn , N kn . The memory needed for this step is 3mB + 3(n + 1). • At step 2m + 1, we process the root node and the memory needed is 3m + 1. Thus, the peak memory of this schedule is B mem and its makespan B Cmax .

On the contrary, assume that there exists a solution to problem I 2 , that is, that there exists a schedule of makespan at most B Cmax = 2m + 1. Without loss of generality, we assume that the makespan is exactly 2m + 1. We start by proving that at any step of the algorithm there are at most three of the N i nodes that are processed. By contradiction, assume that four (or more) such nodes N i1 , N i2 , N i3 , N i4 are processed during a certain step. We recall that a i > B/4 so that a i1 +a i2 +a i3 +a i4 > B and thus a i1 +a i2 +a i3 +a i4 ≥ B + 1. The memory needed at this step is thus at least (B + 1)3m for the children of the nodes N i1 , N i2 , N i3 , and N i4 and 4 for the nodes themselves, hence a total of at least (B+1)3m+4, which is more than the prescribed bound B mem . Thus, at most three of N i nodes are processed at any step. In the considered schedule, the root node is processed at step 2m + 1. Then, at step 2m, some of the N i nodes are processed, and at most three of them from what precedes. The a i 's corresponding to those nodes make the first subset S 1 . Then all the nodes L j

x such that a j ∈ S 1 must have been processed at the latest at step 2m -1, and they occupy a memory footprint of 3m aj ∈S1 a j at steps 2m -1 and steps 2m. Let us assume that a node N k is processed at step 2m-1. For the memory bound B mem not to be satisfied we must have a k + aj ∈S1 a j ≤ B. (Otherwise, we would need a memory of at least 3m(B + 1) for the involved L j

x nodes plus 1 for the node N k ). Therefore, node N k could have been processed at step 2m. We then modify the schedule so as to schedule N k at step 2m and thus we add k to S 1 . We can therefore assume, without loss of generality, that no N i node is processed at step 2m -1. Then, at step 2m -1 only children of the N j nodes with a j ∈ S 1 are processed, and all of them are. So, none of them have any memory footprint before step 2m -1. We then generalize this analysis: at step 2i, for 1 ≤ i ≤ m -1, only some N j nodes are processed and they define a subset S i ; at step 2i-1, for 1 ≤ i ≤ m-1, are processed exactly the nodes L k x that are children of the nodes N j such that a j ∈ S i .

Because of the memory constraint, each of the m subsets of a i 's built above sum to at most B. Since they contain all a i 's, their sum is mB. Thus, each subset S k sums to B and we have built a solution for I 1 .

B. Joint minimization of both objectives

As our problem is NP-complete, it is natural to wonder whether there exist approximation algorithms. Here, we prove that there does not exist schedules which approximates both the minimum makespan and the minimum memory with constant factors 1

.

Theorem 2. There is no algorithm that is both an α-approximation for makespan minimization and a βapproximation for memory peak minimization when scheduling in-tree task graphs.

Below is a sketch of the proof of Theorem 2. A comprehensive proof can be found in the companion research report [START_REF] Marchal | Scheduling treeshaped task graphs to minimize memory and makespan[END_REF].

Proof: To establish this result, we proceed by contradiction. We therefore assume that there is an integer α, an integer β, and an algorithm A that processes any input tree T in a time not greater than α times the optimal execution time while using a peak memory that is not greater than β times the optimal peak memory.

The tree. Figure 2 presents the tree used to derive a contradiction. This tree is made of n identical subtrees root whose roots are the children of the tree root. The values of n and δ will be fixed later on.

cp 1 1 d 1 1 a 1,1 δ a 1,1 δ-1 ... a 1,1 2 a 1,1 1 cp 1 2 d 1 2 a 1,2 δ-1 ... a 1,2 2 a 1,2 1 cp 1 δ-1 d 1 δ-1 a 1,δ-1 2 a 1,δ-1 1 b 1 δ b 1 δ+1 cp 2 1 d 2 1 a 2,1 δ a 2,1 δ-1 ... a 2,1 2 a 2,1 1 cp 2 2 d 2 2 a 2,2 δ-1 ... a 2,2 2 a 2,2 1 cp 2 δ-1 d 2 δ-1 a 2,δ-1 2 a 2,δ-1 1 b 2 δ b 2 δ+1 . . . cp n 1 d n 1 a n,1 δ a n,1 δ-1 ... a n,1 2 a n,1 1 cp n 2 d n 2 a n,2 δ-1 ... a n,2 2 a n,2 1 cp n δ-1 d n δ-1 a n,δ-1 2 a n,δ-1 1 b n δ b n δ+1
Optimal execution time. The optimal execution time is equal to the length of the critical path, as we have made no hypothesis on the number of available processors. The critical path has a length of δ + 2, which is the length of the path from the root to any b i δ+1 , a i,δ-1

1

, or a i,δ-1 2 node, with

1 ≤ i ≤ n.
Optimal peak memory. Let us consider any sequential execution that is optimal with regard to the peak memory usage. Under this execution, let d i 1 be the last processed node among the d j 1 nodes, 1 ≤ j ≤ n. We consider the step at which node d i 1 is processed. As, by hypothesis, all the d j 1 nodes, 1 ≤ j ≤ n and j = i, have already been processed, there are in memory at that step at least n -1 results. The processing of d i 1 requires δ + 1 memory units as this node has δ children. Hence, a total memory usage of at least (n-1)+(δ+1) = δ+n for the processing of d i 1 . This is obviously a lower bound on the optimal peak memory usage. We now show that this bound can be reached.

We consider the following schedule:

• Completely process first the subtree rooted at cp 1 1 , then the subtree rooted at cp 2 1 , and so on. • The subtree rooted at cp i 1 is processed as follows: for j going from 1 to δ -1, process the δ -j + 1 children of node d j i , then node d j i ; then process nodes b i δ+1 , b i δ , and nodes cp i δ-1 to cp i 1 . Under this schedule, the peak memory usage during the processing of the subtree rooted at cp i 1 is i + δ. The overall peak memory usage of the studied schedule is then n + δ which is thus the optimal peak memory usage.

Lower bound on the peak memory usage of A. The peak memory usage is not smaller than the average memory usage. We derive the desired contradiction by using the average memory usage of algorithm A as a lower bound to its peak memory usage.

By hypothesis, algorithm A is α competitive with regard to makespan minimization. Therefore the processing of the tree by algorithm A should complete at the latest at time α(δ + 2). To ensure that, the n cp i 1 nodes, 1 ≤ i ≤ n, must all be executed at the latest at time α(δ + 2) -1. Therefore, all the descendants of these nodes must be executed between time 0 and time α(δ + 2) -2. All together, the nodes cp i 1 , for 1 ≤ i ≤ n have n δ 2 +5δ-4 2 descendants. We consider the memory footprint of each of these nodes between time step 0 and time step α(δ +2)-2. The result of the processing of each of theses nodes must be in memory for at least two steps in this interval, the step at which the node is processed and the step at which its parent node is processed, except for the nodes d 1 j , 1 ≤ j ≤ n, and cp k 2 , for 1 ≤ k ≤ n, whose parents need not have been processed in that interval and thus need only to be present in memory during one time step. The overall memory footprint between time 0 and α(δ+2)-2 is then: n δ 2 + 5δ -6 . The average memory usage during that period is thus:

n δ 2 + 5δ -6 α(δ + 2) -2 .
This is obviously a lower bound on the overall peak memory usage. This bound enables us to derive a lower bound lb on the approximation ratio ρ of algorithm A with regard to memory usage:

ρ ≥ lb = n(δ 2 +5δ-6) α(δ+2)-2 n + δ = n δ 2 + 5δ -6 (α(δ + 2) -2)(n + δ) .
We then let δ = n 2 . Therefore,

lb = n n 4 + 5n 2 -6 (α(n 2 + 2) -2)(n + n 2 )
.

Then, lb tends to +∞ when n tends to infinity. There is thus a value n 0 such that, for any value n ≥ n 0 , the right-hand side is greater than 2β. We let n = n 0 and we obtain:

lb = n 0 n 4 0 + 5n 2 0 -6 (α(n 2 0 + 2) -2)(n 0 + n 2 0 ) ≥ 2β,
which contradicts the definition of β.

V. HEURISTICS

Given the complexity of optimizing the makespan and memory at the same time, we have investigated heuristics and propose three algorithms: PARSUBTREES, PARINNER-FIRST, and PARDEEPESTFIRST. The intention is that the proposed algorithms cover a range of use cases, where the optimization focus wanders between the makespan and the required memory. PARSUBTREES employs a memoryoptimizing sequential algorithm for its subtrees, hence its focus is more on the memory side. In contrast, PARINNER-FIRST and PARSUBTREES are list scheduling based algorithms, which should be stronger in the makespan objective. Nevertheless, PARINNERFIRST tries to approximate a postorder in parallel, which is good for memory in sequential. PARDEEPESTFIRST's focus is fully on the makespan.

The minimal memory requirement M is achieved by using the optimal sequential algorithm [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF], i.e., using p = 1 processor. Employing more processors cannot reduce the amount of memory required, yet the sequential algorithm is of course only a p-approximation of the optimal parallel makespan C * max .

A. Heuristic PARSUBTREES

The most natural idea to process a tree T in parallel is arguably its splitting into subtrees and their subsequent parallel processing, each using the sequentially memoryoptimal algorithms [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF], [START_REF]An application of generalized tree pebbling to sparse matrix factorization[END_REF]. An underlying idea is to give each processor a whole subtree in order to enable a lot of parallelism while allowing to use single-processor memoryoptimal traversals on each subtree. Algorithm 1 outlines such an algorithm, together with the routine for splitting T into subtrees given in Algorithm The makespan obtained using PARSUBTREES is denoted by C PARSUBTREES max . In this approach, q subtrees of T , q ≤ p, are processed in parallel. Each of these subtrees is a maximal subtree of T . In other words, each of these subtrees includes all the descendants (in T ) of its root. The nodes not belonging to the q subtrees are processed sequentially. These are the nodes Algorithm 1: PARSUBTREES (T , p)

1 Split tree T into q subtrees (q ≤ p) and remaining set of nodes, using SPLITSUBTREES (T , p). 2 Concurrently process the q subtrees, each using memory minimizing algorithm, e.g. [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. 3 Sequentially process remaining set of nodes, using memory minimizing algorithm.

where the q subtrees merge, the nodes included in subtrees that were produced in excess (if more than p subtrees were created), and the ancestors of these nodes. An alternative approach, as discussed below, is to process all subtrees in parallel, assigning more than one subtree to each processor, but Algorithm 1 allows us to find a makespan-optimal splitting into subtrees, established shortly in Lemma 1.

As w i is the computation weight of node i, W i denotes the total computation weight (i.e., sum of weights) of all nodes in the subtree rooted in i, including i. SPLITSUBTREES uses a node priority queue P Q in which the nodes are sorted by non-increasing W i , and ties are broken according to non-increasing w i . head(P Q) returns the first node of P Q, while popHead(P Q) also removes it. P Q[i] denotes the i-th element in the queue.

SPLITSUBTREES starts with the root and continues splitting the largest subtree (in terms of W) until this subtree is a leaf node (W head(P Q) = w head(P Q) ). The execution time of Step 2 of PARSUBTREES is that of the largest of the q subtrees, hence W head(P Q) of the splitting. Splitting subtrees that are smaller than the largest leaf (W j < max i∈T w i ) cannot decrease the parallel time, but only increase the sequential time. More generally, given any splitting s of T into subtrees, the best execution time for s with PARSUBTREES is achieved by choosing the p largest subtrees for the parallel Step 2. This can be easily derived, as swapping a large tree included in the sequential part with a smaller tree included in the parallel part cannot increase the total execution time.

Lemma 1. SPLITSUBTREES returns a splitting of T into subtrees that results in the makespan-optimal processing of T with PARSUBTREES.

Proof: The proof is by contradiction. Let S be the splitting into subtrees selected by SPLITSUBTREES. Assume now that there is a different splitting S opt which results in a shorter processing with PARSUBTREES.

Let r be the root node of a heaviest subtree in S opt . Let t be the first step in SPLITSUBTREES where a node, say r t , of weight W r is the head of P Q at the end of the step (r t is not necessarily equal to r, as there can be more than one subtree of weight W r ). There is always such a step t, because all subtrees are split by SPLITSUBTREES until at least one of the largest trees is a leaf node. By definition of r, there cannot be any leaf node heavier than W r . The cost Algorithm 2: SPLITSUBTREES (T , p)

1 Compute weights W i , ∀i ∈ T 2 P Q ← root 3 seqSet ← ∅ 4 Cost(0) = W root 5 s ← 1 / * splitting rank * / 6 while W head(P Q) > w head(P Q) do 7 node ← popHead(P Q) 8 seqSet ← seqSet ∪ node 9 P Q ← Children(node) 10 C PARSUBTREES max (s) = W head(P Q) + i∈seqSet w i + |P Q| i=P Q[p+1] W i 11 s ← s + 1 12 Select splitting x with C PARSUBTREES max (x) = min s-1 t=0 C PARSUBTREES max (t)
of the solution of step t is C PARSUBTREES max (t) = W r + Seq(t), hence parallel time plus sequential time, denoted by Seq(t). Seq(t) is the total weight of the sequential set seqSet plus the total weight of the surplus subtrees (that is, of all the subtrees except the p ones of largest weights). The cost of S opt is C * max = W r + Seq(S opt ), given that r is the root of a heaviest subtree of S opt by definition.

The splitting at step t (and any other splitting considered by SPLITSUBTREES) cannot be identical to S opt , otherwise SPLITSUBTREES would have selected that splitting. All subtrees that were split in SPLITSUBTREES before step t were strictly heavier than W r . Thus, there cannot exist any subtree in S opt , whose subtrees are part of the splitting at step t. Hence for every subtree T j in the splitting at step t the following property holds: either T j is part of S opt or a splitting of T j into subtrees is part of S opt . It directly follows that Seq(t) ≤ Seq(S opt ), because every splitting of a tree into subtrees increases the sequential time by at least the root's weight. As the parallel time is identical for t and S opt , namely W r , it follows that C PARSUBTREES max (t) ≤ C * max , which is a contradiction to S opt 's shorter processing time.

Complexity: We first analyse the complexity of SPLITSUBTREES. Computing the weights W i costs O(n). Each insertion into P Q costs O(log(n)) and calculating C PARSUBTREES max (s) in each step costs O(p). Given that there are O(n) steps, SPLITSUBTREES's complexity is O(n(log(n) + p)). The complexity of the sequential traversal algorithms used in Steps 2 and 3 of PARSUBTREES cost at most O(n 2 ), e.g., [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF], [START_REF]An application of generalized tree pebbling to sparse matrix factorization[END_REF], or O(n log(n)) if the optimal postorder suffices. Thus the total complexity of PARSUBTREES is O(n 2 ) or O(n log(n)), depending on the chosen sequential algorithm.

PARSUBTREES has the following guarantees for the memory requirement and makespan. Memory: PARSUBTREES is a (p+1)-approximation algorithm for peak memory minimization. During the parallel part of PARSUBTREES the total memory used is less than p times the memory for the complete sequential execution (M seq ), M p ≤ p • M seq . This is because each of the p processors executes a maximal subtree and that the processing of any subtree uses, obviously, less memory (if done optimally) than the processing of the whole tree. During the sequential part of PARSUBTREES the memory is bounded by M s ≤ M seq +p•max i∈T f i ≤ (p+1)M seq , where the second term is for the output files produced by the up to p subtrees processed in parallel. Hence, in total: M ≤ (p + 1)M seq Makespan: PARSUBTREES delivers a p-approximation algorithm for makespan minimization. In other words, the makespan achieved by PARSUBTREES can be up to p times worse than the optimal makespan and thus may be not faster than the sequential execution. This can be derived readily with a tree of height 1 and p • k leaves (a fork) and w i = 1, ∀i ∈ T , where k is a large integer (this tree is depicted on Figure 3). The optimal makespan for such a tree is C * max = kp/p + 1 = k + 1. With PARSUBTREES the makespan is

C max = 1 + (1 + pk -p) = p(k -1) + 2.
When k tends to +∞ the ratio between the makespans tends to p.

Given the just observed worst case for the makespan, a makespan optimization for PARSUBTREES is to allocate all produced subtrees to the p processors instead of only p. This can be done by ordering the subtrees by non-increasing total weight and allocating each subtree in turn to the processor with the lowest total weight. Each of the parallel processors executes its subtrees sequentially. This optimized form of the algorithm shall be named PARSUBTREESOPTIM. Note that this optimization should improve the makespan, but it will likely worsen the peak memory usage.

B. Heuristic PARINNERFIRST

PARSUBTREES is a high level algorithm employing sequential memory-optimized algorithms. An alternative is to design algorithms that directly work on the tree in parallel and we present two such algorithms. From the sequential case it is known that a postorder traversal, while not optimal for all instances, provides good results [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. Our intention is to extend the principle of postorder traversal to the parallel processing. To do so we establish the following rules. Parallel Postorder:

1) If an inner node (i.e., a non-leaf node) is ready to be processed (i.e., its input files are all in memory) then execute it.

2) Otherwise, select and process the leaf node that is closest (in terms of edges to be traversed) to the previously selected leaf. These rules do not correspond to the usual formulation of postorder but, when applied using a single processor, they give rise to a postorder traversal of the tree. Due to the concurrent processing of nodes with p processors, the resulting order will not be a perfect postorder, but hopefully a close approximation.

With the careful formulation of the parallel postorder we are able to base the heuristic on an event-based list scheduling algorithm [START_REF] Hwang | Scheduling precedence graphs in systems with interprocessor communication times[END_REF]. Algorithm 3 outlines a generic list scheduling, driven by node finish time events. At each event at least one node has finished so at least one processor is available for processing nodes. Each available processor is given the respective head node of the priority queue. The order in which nodes are processed in Algorithm 3 is determined by two aspects: i) the node order O given as input; and ii) the ordering established by the priority queue P Q.

For our proposed parallel postorder algorithm, called PARINNERFIRST, the priority queue uses the following ordering: 1) inner nodes, ordered by non-increasing depth; 2) leaf nodes as ordered in the input order O. To achieve a parallel postorder, the node ordering O needs to be a sequential postorder. It makes heuristic sense that this postorder is an optimal sequential postorder, so that memory consumption can be minimized [START_REF] Liu | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF].

Complexity: The complexity of PARINNERFIRST is that of determining the input order O and that of the list scheduling. Computing the optimal sequential postorder is O(n log n) [START_REF] Liu | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF]. In the list scheduling algorithm there are O(n) events and n nodes are inserted and retrieved from P Q. An insertion into P Q is O(log n), so the list scheduling complexity is O(n log n). Hence, the total complexity is also O(n log n).

1 1 • • • • • • p -1 • • • • • • k -1 1 • • • • • • p -1 k 2k
In the following we study the memory requirement and makespan of PARINNERFIRST.

Memory: There is no limit on the required memory compared to the optimal sequential memory M seq . This is derived considering the tree in Figure 4. All output files have size 1 and the execution files have size 0 (f i = 1, n i = 0 for any node i of T ). When optimally processing with p = 1, we process the leaves in a deepest first order. The resulting optimal memory requirement is M seq = p+1, reached when processing a join node.With p processors all leaves have been processed at the time the first join node (k -1) can be executed. (The longest chain has length 2k.) At that time there are (k -1) • (p -1) + 1 files in memory. When k tends to +∞ the ratio between the memory requirements also tends to +∞.

Makespan: PARINNERFIRST schedule is a (2 -1 p )approximation algorithm for makespan minimization because PARINNERFIRST is a list scheduling algorithm [START_REF] Graham | Bounds for certain multiprocessing anomalies[END_REF].

C. Heuristic PARDEEPESTFIRST

The previous heuristic PARINNERFIRST is motivated by good memory results for sequential postorder. Going the opposite direction, a heuristic objective can be the minimization of the makespan. For trees, all inner nodes depend on the leaf nodes, so it makes heuristic sense to try to process the deepest nodes first to reduce any possible waiting time. For the parallel processing of the tree, the most meaningful definition of the depth of a node i is the w-weighted length of the path from i to the root of the tree. This path length includes the w i . The deepest node is the first node of the critical path of the tree.

PARDEEPESTFIRST is our proposed algorithm that does this. Due to the general nature of the list scheduling presented in Algorithm 3, we can implement PARDEEPEST-FIRST with it. To achieve the deepest first processing the priority queue P Q orders the nodes as follows: 1) deepest nodes first (in terms of w-weighted path length to root); 2) inner nodes before leaf nodes; 3) leaf nodes are ordered in Instead of implementing an intricate algorithm with O(n2 ) complexity such as Liu's algorithm [START_REF]An application of generalized tree pebbling to sparse matrix factorization[END_REF] to obtain minimum sequential memory, we have chosen to estimate this minimum memory using the optimal post-order traversal. We have shown in [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF] that this traversal was optimal in 95.8% of the tested cases, with an average increase of 1% with respect to the optimal. This justifies this choice. Since the reference sequential task-graph traversal serves as a basis for ordering nodes in a number of our heuristics, a large complexity would be prohibitive for this first step.

B. Data set

The data set contains assembly trees of a set of sparse matrices obtained from the University of Florida Sparse Matrix Collection (http://www.cise.ufl.edu/research/sparse/ matrices/). The chosen matrices satisfy the following assertions: not binary, not corresponding to a graph, square, having a symmetric pattern, a number of rows between 20,000 and 2,000,000, a number of nonzeros per row at least equal to 2.5, and a number of nonzeros per row at most equal to 5,000,000; and each chosen matrix has the largest number of nonzeros among the matrices in its group satisfying the previous assertions. At the time of testing there were 76 matrices satisfying these properties. We first order the matrices using MeTiS [START_REF] Karypis | MeTiS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4[END_REF] (through the MeshPart toolbox [START_REF] Gilbert | Geometric mesh partitioning: Implementation and experiments[END_REF]) and amd (available in Matlab), and then build the corresponding elimination trees using the symbfact routine of Matlab. We also perform a relaxed node amalgamation on these elimination trees to create assembly trees. We have created a large set of instances by allowing 1, 2, 4, and 16 (if more than 1.6 × 10 5 nodes) relaxed amalgamations per node. At the end we compute memory weights and processing times to accurately simulate the matrix factorization: we compute the memory weight n i of a node as η 2 + 2η(µ -1), where η is the number of nodes amalgamated, and µ is the number of nonzeros in the column of the Cholesky factor of the matrix which is associated with the highest node (in the starting elimination tree); the processing cost w i of a node is defined as 2/3η 3 + η 2 (µ -1) + η(µ -1) 2 (these terms corresponds to one gaussian elimination, two multiplications of a triangular η × η matrix with a η × (µ -1) matrix, and one multiplication of a (µ -1) × η matrix with a η × (µ -1) matrix). The memory weights f i of edges are computed as (µ -1) 2 .

The resulting 608 trees contains from 2,000 to 1,000,000 nodes. Their depth ranges from 12 to 70,000 and their maximum degree ranges from 2 to 175,000. Each heuristic is tested on each tree using p = 2, 4, 8, 16, and 32 processors. Then the memory and makespan of the resulting schedules are evaluated by simulating a parallel execution.

C. Results

The comparison of the heuristics is summarized in Table I the best heuristics for memory minimization. On average they use less than 2.5 times the amount of memory required by the best sequential postorder (whose memory usage is very close to the optimal sequential memory as noted above), when PARINNERFIRST and PARDEEPEST-FIRST need respectively 3.7 and 5.2 times this amount of memory. PARINNERFIRST and PARDEEPESTFIRST perform best for makespan minimization, having makespans very close on average to the best achieved ones. As the scheduling problem, without memory constraints, is already NP-hard, we do not know what the optimal makespan is. We have seen however that PARINNERFIRST and PARDEEPESTFIRST are 2-approximation algorithms for the makespan. Furthermore, given the critical path oriented node ordering, we can expect that PARDEEPESTFIRST's makespan is close to optimal. PARINNERFIRST outperforms PARINNERFIRST for makespan minimization, at the cost of a noticeable increase in memory. PARSUBTREES and PARSUBTREESOPTIM may be better trade-offs, since their average deviation from best makespan is under 35%. Figures 6,7, and 8 provide complete results of the simulations. In each figure, a point represent one scenario (one heuristic on one tree with a given number of processors). To better visualize the distribution, we also plot a "cross" for each heuristic: the center of this cross is the average performance, while the branches represent the scope of each objective between the 10th and the 90th percentile of the distribution.

On Figure 6, we plot the results of all simulations compared to some estimations of the lower bounds. The lower bound for memory minimization is the memory usage of the best sequential postorder, which is known to be very close to the optimal sequential traversal. The lower bound for the makespan is the maximum between the total processing time of the tree divided by the number of processors, and the maximum weighted critical path. This figure exhibits the same trends for average values as noted in Table I. When the maximum deviation from the lower bound on the makespan is around 4, the ratio of the parallel memory usage to the optimal sequential one can be far larger, as it is larger than 100 for the extreme cases.

In the following figures, the results of the heuristics is normalized by the results of PARSUBTREES (Figure 7) or PARINNERFIRST (Figure 8). As expected, PARSUB- TREESOPTIM gives results close to those of PARSUBTREES, with better makespans but slightly worse memory usage. PARDEEPESTFIRST always use more memory than PARIN-NERFIRST, while having comparable makespans. In most cases, PARINNERFIRST gives slightly better makespan than PARSUBTREES, but uses more memory.

VII. CONCLUSION In this study we have shown that the parallel version of the pebble game on trees is NP-complete, hence stressing the negative impact of the memory constraints on the complexity of the problem. More importantly, we have shown that there does not exist any algorithm that is simultaneously an approximation algorithm for both makespan minimization and peak memory usage minimization when scheduling treeshaped task graphs. We have thus designed heuristics for this problem. We have assess their performance using real task graphs arising from sparse matrices computation. These simulations showed that two of the heuristics, PARSUB-TREES and PARSUBTREESOPTIM, only needed, for their parallel executions, and on average, 2.5 times the sequential memory, while achieving makespans that were less than 35% larger than best achieved ones. These heuristics appear thus to deliver interesting trade-offs between memory usage and execution times. In the future work, we will consider designing scheduling algorithms that take as input a cap on the memory usage.

Figure 2 .

 2 Figure 2. Tree used for establishing Theorem 2.

Figure 3 .

 3 Figure 3. PARSUBTREES is at best a p-approximation for the makespan.

Algorithm 3 : 4 popHead(eventSet) 5 6 P a ← available processors 7 while 9 Assign node to proc 10 eventSet

 34567910 List scheduling(T , p, O) 1 Insert leaves in P Q, ordered as in O 2 eventSet ← {0} / * ascending order * / 3 while eventSet = ∅ do / * event:node finishes * / Insert new ready nodes in P Q / * available parents of nodes completed at event * / P a = ∅ and P Q = ∅ do 8 proc ← popHead(P a ); node ← popHead(P Q) ← eventSet ∪ f inishT ime(node)

Figure 4 .

 4 Figure 4. No memory bound for PARINNERFIRST.

Figure 7 .Figure 8 .

 78 Figure 7. Comparison to PARSUBTREES.

  . It shows that PARSUBTREES and PARSUBTREESOPTIM are

	Heuristic	Best memory	Within 5% of best memory	Avg. deviation from optimal (seq.) memory	Best makespan	Within 5% of best makespan from best makespan Avg. deviation
	PARSUBTREES	81.1 %		85.2 %		133.0 %		0.2 %	14.2 %	34.7 %
	PARSUBTREESOPTIM	49.9 %		65.6 %		144.8 %		1.1 %	19.1 %	28.5 %
	PARINNERFIRST	19.1 %		26.2 %		276.5 %		37.2 %	82.4 %	2.6 %
	PARDEEPESTFIRST	3.0 %		9.6 %		325.8 %		95.7 %	99.9 %	0.0 %
						Table I
	PROPORTIONS OF SCENARII WHEN HEURISTICS REACH BEST (OR CLOSE TO BEST) PERFORMANCE, AND AVERAGE DEVIATIONS FROM OPTIMAL
				MEMORY AND BEST ACHIEVED MAKESPAN.
									PARSUBTREES
		80 100							PARDEEPESTFIRST PARINNERFIRST PARSUBTREESOPTIM
	Relative memory compared to the lower bound	60 40 20 10 8 6 4
		2
		1
		1	1.2	1.4	1.6	1.8	2	2.5	3
					Relative makespan compared to the lower bound
				Figure 6. Comparison to lower bounds.

This is equivalent to say that there is no Zenith or simultaneous approximation.

The code and the data sets are available online at http://graal.ens-lyon. fr/ ∼ lmarchal/scheduling-trees/

ACKNOWLEDGEMENT

We thank Bora Uc ¸ar for his help in creating and managing the data set used in the experiments. We gratefully acknowledge that this work is partially supported by the Marsden Fund Council from Government funding, Grant 9073-3624767, administered by the Royal Society of New Zealand.

the input order O. Note that the leaf order is only relevant for leaves of the same depth. This order should nevertheless be "reasonable", i.e., it should not alternate between leaves from different parents, which would be bad for the memory consumption. Such an order is again easily achieved when O is a sequential postorder.

Complexity: The complexity is the same as for PARIN-NERFIRST, namely O(n log n). See PARINNERFIRST's complexity analysis. Now we study the memory requirement and the makespan of PARDEEPESTFIRST.

Memory: The required memory of PARDEEPESTFIRST is unbounded compared to the optimal sequential memory M seq . Consider the tree in Figure 5 with many long chains, assuming the Pebble Game model (i.e., f i = 1, n i = 0, and w i = 1 for any node i of T ). The optimal sequential memory requirement is 3.The memory usage of PARDEEPESTFIRST will be proportional to the number of leaves, because they are all at the same depth, the deepest one. As we can build a tree like the one of Figure 5 for any predefined number of chains, the ratio between the memory required by PARDEEPESTFIRST and the optimal one is unbounded.

Makespan: PARDEEPESTFIRST schedule is a (2 -1 p )approximation algorithm for makespan minimization because PARDEEPESTFIRST is, like PARINNERFIRST, a list scheduling algorithm [START_REF] Graham | Bounds for certain multiprocessing anomalies[END_REF].

VI. EXPERIMENTAL VALIDATION

In this section, we experimentally compare the heuristics proposed in the previous section, and we compare their performance to lower bounds.

A. Setup

All heuristics have been implemented in C. Special care has been devoted to the implementation to avoid complexity issues. Especially, priority queues have been implemented using binary heap to allow for O(log n) insertion and minimum extraction 2 .


Milan Erdelj

Nathalie Mitton

Enrico Natalizio

Applications of Industrial Wireless Sensor Networks

Introduction

Recent advances in wireless sensing technology encourages the further optimization and improvement of the product development and service provision processes. Industrial Wireless Sensor Networks (IWSN) are an emerging class of WSN that faces specific constraints linked to the particularities of the industrial production. In these terms, IWSNs faces several challenges such as the reliability and robustness in harsh environments, as well as the ability to properly execute and achieve the goal in parallel with all the other industrial processes. Furthermore, IWSN solutions should be versatile, simple to use and install, long lifetime and low-cost devices -indeed, the combination of requirements hard to meet.

In this chapter we discuss the applications of WSNs in industrial environments. Based on the specific requirements of the industrial production, the IWSN applications can be classified into three groups (Figure 1.1):

1. Environmental sensing. This group generally represents the widest field of WSN application nowadays. IWSN applications for environmental sensing cover the problems of air, water (together with waste water) pollution, but covers the production material pollution monitoring as well. Furthermore, in hazardous environments, there are numerous needs for fire, flood or landslide sensing. Finally, the security issues arise in markets with competing product and service providers, where IWSN are used for point of interest, area and barrier monitoring.

2. Condition monitoring. This group generally covers the problems of structural condition monitoring, providing both the structure health information (the condition of the buildings, constructions, bridges, supply routes, etc.) and machine condition monitoring including possible automatic maintenance. Therefore, this group of IWSN applications is vital for the production in all the branches of industry.

3. Process automation. The last group of applications provides the users with the information regarding the resources for the production and service provision (including the materials, current stock and supply chain status, as well as the manpower included in the industrial process). Finally, one of the most important issues from the user perspective is the production performance monitoring, evaluation and improvement, that are achieved through IWSNs.

Table 1.1 provides the list of major industry branches and sectors with the specific group of applications applicable to the particular branch. Here we consider 4 industry sectors: primary (the extraction of resources directly from Earth, includes farming, mining and logging with no product processing), secondary (primary sector product processing), tertiary (service provision) and quaternary (research of science and technology). Currently, the needs and possibilities of WSNs in all the industry sectors and branches are wide spread. The pace of industrial development pushes and encourages the development of IWSN even more. In this chapter, we analyze and evaluate current applications of IWSN and discuss possible future trends in this area.

• • • • • • I,II Power/Energy • • • • • • I,II Agriculture • • • • II Chemical/Biotechnology • • • • II Civil engineering • • • • II Electrical engineering • • • • • II Mechanical engineering • • • • • II,III Product processing • • • • • III Transportation • • • • • III Military/Defense • • • • • • • III Healthcare • • • III Communication • • • III,IV Security R&D • •
In the following sections, we address some of the biggest challenges in IWSN in Section 1.2. Then, we provide the taxonomy of the IWSN applications for environmental sensing in Section 1.3, condition monitoring in Section 1.4 and process automation in Section 1.5. In Section 1.6 we present the extensive list of IWSN solutions and service providers. Finally, we discuss some possible future IWSN trends in Section 1.7.

Technological challenges

The deployment and the set up of Wireless Sensor Networks are extremely challenging tasks, which become even more challenging in industrial applications. The environment where IWSNs are deployed in order to monitor environmental or production processes is extremely dynamic, it can depend on the specific product, the phase of life of the product and the kind of service provision considered. In fact, each kind of product or phase of life has different requirements and imposes on the monitoring system different constraints. In this Section we will try to give a general description that can be useful for IWSNs' designers.

One of the challenges to face is the impact of the propagation environment. When the IWSN is deployed inside a factory to assess the production process quality, the designer has to deal with the interference and the radio environment produced by the production machines. In this case, the IWSN has to be deployed and calibrated not only to guarantee the correct assessment of the production process, but above all not to interfere with the production process. The same logic holds for IWSNs used to monitor electricity, water and gas consumption. Often nodes of the IWSN are immersed into the goods inside containers or any transportation means. For this kind of environments, the radio characteristics of the goods and the container have to be carefully investigated in order to determine the most efficient and effective way to make nodes communicate in spite of probable signal degradations.

In general, radio waves will not follow the same behavior according to the environments in which sensors are deployed. If the network is deployed outdoor, the radio propagation can be assimilated to a free-range perturbation, with an almost omni-directional propagation. However, it will be impacted by the weather, more or less depending of the frequency used. For instance, frequencies around 2.4GHz may be stopped by a thick fog. When wireless sensor networks are deployed indoor, the data propagation is far from being omnidirectional. In this environment it is even harder to make the classical assumptions on the shape and extension of the communication range for sensors. In fact, sensors that are placed within the communication range might be invisible, whereas sensors that should be considered out of range are actually in the neighbors' set. This can be explained by the fact that waves can bounce on walls, machinery, etc. This amplifies the signal in some locations and cancel it in other locations. Similarly, presence of metal and liquid greatly impacts the propagation. Indeed, metallic equipment may extend the propagation area for the radio signal or may prevent the signal to reach close areas beyond the equipment. These challenges, strictly dependent from physical factors, are not easy to handle. The environment in which sensors will be deployed needs to be studied in order to determine the optimal locations for sensors.

Operation lifetime, as a result of the power management policy, is one of the key issues in all the WSN applications, including the IWSN. Several IWSN applications, especially in the field of environmental monitoring, require the autonomous power supply from alternative power sources, such as wind or solar power. Although it is possible to obtain a constant power supply in some industrial environments, sensors tend to be battery powered in order to keep the monitoring non-intrusive. However, in most cases, batteries are not expected to be reloaded or changed. Thus, energy should be preserved. There exist many ways to do so, both in software and hardware. From the hardware point of view, it is important to carefully choose the components. These latter should be low energy consuming while providing the needed capacity. In some particular applications, energy harvesting modules can be envisioned, like solar cells or kinematic sensors, etc., but their usage is still marginal. From the software point of view, energy should be preserved by controlling the number of messages to be sent and the range. Indeed, radio activities, such as sending and receving data are the activities that consume more energy in WSN compared with processing and sensing activities. Thus, it is important to monitor carefully the amount of data to send and the frequency at which it is sent, i.e. the number and size of messages, while preserving the quality of service expected by the application. Similarly, the further the messages are sent the more the energy needed and the more the interferences generated. Thus, it is important to monitor the transmission range based on the target to reach.

Another challenge in this field of application is the heterogeneity that the IWSN must deal with. In fact, heterogeneity is present in at least two different facets in industrial sensing applications: heterogeneity of data collected and heterogeneity of objective network to integrate with. The heterogeneity of data collected comes from the need of creating the dataset used to assess the quality of the production process/service provision by including a range spectrum of parameters. In turn, this requires to enable proper data fusion/data aggregation schemes for the acquisition/transmission of data, and powerful techniques of data analysis for the reception side. The heterogeneity of objective network is focused especially on logistics applications, where the IWSN used to monitor the transportation of some goods must be able to integrate with the IWSN deployed in both the production site and the delivery site, in order to acquire and exchange relevant information about the transported goods.

The third main technological challenge is that IWSNs for process and service monitoring have to operate autonomously. The operation of the IWSN should not represent an additional burden for the human involved in the sensor network operation, instead the IWSN should be able to autonomously configure and deploy when the deployment site is inaccessible for humans. In this context, maintainability is one of the important design challenges in the IWSN as well. The deployed IWSN and its components should be easily repairable or replaceable by maintenance personnel in the case of failures.

The requirements of the industrial process impose the need for reliable and secure IWSN. Reliability in this context refers to the monitoring system that has to provide accurate and real-time information regarding the monitored process even in harsh industrial environments under extreme vibration, noise, humidity or temperature conditions. The information gathered during the monitoring process is vital for proper system operations, given that even the smallest errors can produce fatal consequences for both the system and the product. Therefore, system security concludes our list of main challenges in the IWSN design.

1.3 Environmental sensing applications

1.3.

Concept and objectives

Environmental sensing has been the basic WSN application, since WSN appeared in industrial processes. Nowaday, environmental sensing is widely spread in almost every field of industry. The common element that combines all the application scenarios together is the need for real-time information about the industrial environment, whether it is the production material, ambient or the process itself. Three different paradigms can be distinguished in this context: pollution, hazard and security monitoring, that will be discussed further in this section. General objective in the environmental monitoring is an efficient information gathering, used both for prevention (real-time or postponed) and analysis. The migration from the wired sensor networks to their wireless counterpart brings numerous advantages by facilitating the deployment and information gathering process. However, the compromise is always present -WSNs still have to cope with the problems of erroneous communication, robustness, lifetime and cost constraints.

In this section we analyze some existing research works in the field of environmental sensing. Such environmental monitoring applications are the first ones that have been developed for wireless sensor networks. In fact, due to their small size, sensors can be easily and quickly deployed over large scales at low cost. Their wireless features that makes them independent from any costly and fixed infrastructures also contributed to their success. Environment sensing is a very broad area that comes from monitoring for disaster prevention, like volcano monitoring, to healing operations when sensors indicates a critic area.

Existing solutions

Pollution

The importance of the pollution detection both in materials for the production as well as in the production ambients makes the pollution monitoring one of the most widely spread field of application in environmental sensing. Constant advance in the sensing technology supports this statement as well. In [START_REF] Kim | Sewersnort: A drifting sensor for in-situ sewer gas monitoring[END_REF], authors propose a low-cost, fully automated, end-to-end in-sewer gas monitoring system based on floating-drifting embedded sensor platform. This system provides the user with accurate information regarding the gas readings and its localization. Authors of [START_REF] Santini | First experiences using wireless sensor networks for noise pollution monitoring[END_REF] focus primarily on the noise pollution in urban areas. They present a prototype of a platform for collection and logging of the outdoor noise pollution measurements. These measurements can be used for the analysis of pollution effect on manpower productivity and social behavior. There also exist many other kinds of applications for detecting and/or preventing pollution like also air or water pollution continuously or after an event like for instance a volcano eruption which may spread in the atmosphere some toxic gas.

Hazard

Industrial facilities are often localized in environments that are riskier than residential areas, especially in the case of oil, gas and coal mining industries or agricultural companies. Therefore, proper early warnings or predictive disaster detection might be a valuable asset, resource and life saver. In [START_REF] Basha | Model-based monitoring for early warning flood detection[END_REF], authors implement the river flood detection. A sensor network is used for flood prediction based on the previous measurements. By using a small number of sensor nodes with self-monitoring for failure capabilities, they cover and secure large geographical area under the threat of disaster (Figure 1.3). In [START_REF] Lee | Using mobile wireless sensors for in-situ tracking of debris flows[END_REF], authors propose the debris flow monitoring system that allows in-situ real-time debris flow tracking. A number of robust sensors with self-localization capabilities are thrown into the flow, thus providing the real time flow direction and volume information used for early warning issuing.

Security

The concept of security in industrial environments is indeed widely spread over almost all the industry branches in all sectors. The security itself can refer to the security of the information and the security of the people, products and equipment. In this chapter, we focus on the latter. In this context, the applications for security monitoring usually focus on the area, barrier and point of interest monitoring. In [START_REF] Kim | Design of a fence surveillance system based on wireless sensor networks[END_REF], authors present a fence surveillance system that comprises the robot and camera sensor network and two types of nodes, ground and fence nodes. The network reports the acquired data to the basestation with issues commands to mobile robots that extend the communication distance of the system.

Condition monitoring applications

Concept and objectives

Why there is a need for WSN applications in condition monitoring? Every industrial system faces the problem of equipment amortization that introduces the maintenance cost into the equation. Moreover, there is a need for structural and equipment monitoring techniques that could provide global picture on subject condition and accurately predict equipment failures and therefore improve component and equipment reliability and performance. Furthermore, structural monitoring system detects system damages before possible failures and minimizes the time that production line spends out of service, and thus increases the profit. Without automated monitoring system, it is necessary to schedule regular system checks and preventively replace production equipment, which can also include the risk of sending maintenance workers into hazardous environments.

WSN intended for condition monitoring avoids all the aforementioned problems and suits the application requirements in comparison with wired sensing systems, since:

• it is easily deployable and reconfigurable even in an inaccessible areas such as moving (rotating) machine parts,

• it is easily reconfigurable,

• it reduces the system installation and condition monitoring cost in general.

In this context, we distinguish two classes of condition monitoring applications: structural health monitoring (public, private and transportation infrastructure) and equipment condition monitoring (mechanical and manufacturing equipment).

Existing solutions 1.4.2.1 Structural health monitoring

Wireless sensor networks are well suited for the structural health monitoring since they are easily deployable and configurable for this purpose. Here we cite some of the recent works that tackle the problem of structural monitoring (notably the vibration monitoring) on buildings [START_REF] Xu | A wireless sensor network for structural monitoring[END_REF], wind turbines [START_REF] Swartz | Structural monitoring of wind turbines using wireless sensor networks[END_REF], coal mines [START_REF] Li | Underground coal mine monitoring with wireless sensor networks[END_REF], tunnels [START_REF] Stajano | Smart bridges, smart tunnels: Transforming wireless sensor networks from research prototypes into robust engineering infrastructure[END_REF] and bridges [START_REF] Kim | Health monitoring of civil infrastructures using wireless sensor networks[END_REF][START_REF] Picozzi | Wireless technologies for the monitoring of strategic civil infrastructures: an ambient vibration test on the fatih sultan mehmet suspension bridge in istanbul, turkey[END_REF].

In [START_REF] Xu | A wireless sensor network for structural monitoring[END_REF], authors deployed a wireless data acquisition system that is used for damage detection on the building. Their proposed system continuously collects structural response data from a multi-hop network of sensor nodes, displays and stores the data in the base station. They propose the system design and evaluate their approach by practical WSN implementation. Prior to the monitoring system implementation, it is necessary to characterize the structure under consideration. In [START_REF] Swartz | Structural monitoring of wind turbines using wireless sensor networks[END_REF], authors deploy wireless sensor network on two wind turbines in order to gather the vibrational output data and to provide better models of wind turbine dynamic behavior and response to loading (Figure 1.5). Authors made the acquired data available for future structure health monitoring designs.

Authors in [START_REF] Li | Underground coal mine monitoring with wireless sensor networks[END_REF] discuss the design of a structure-aware self-adaptive approach that rapidly detects structure variations in coal mines caused by underground collapses. The goal of their system design is to detect the collapsed area and report it to the sink node, to maintain the system integrity when the structure is altered and to provide a robust mechanism for query handling over the network under unstable circumstances. They conducted field experiments and deployed a prototype system that proves the approach feasibility.

One of the hot topics in structural monitoring research are bridges, as a part of the public infrastructure. Numerous research papers are written on this topic and there are numerous attempts to propose solutions and practical implementations for bridge health monitoring. We present only most recent works in this field. In [START_REF] Kim | Health monitoring of civil infrastructures using wireless sensor networks[END_REF], authors describe requirement, challenges, their design and implementation of WSN for health monitoring of Golden Gate Bridge in San Francisco Bay, USA. Authors identify requirements needed to obtain data of sufficient quality to have a real scientific value to civil engineering researchers for structural health monitoring. Furthermore, they propose the monitoring system that is scalable and applicable to different kinds of monitoring applications and address the typical problems encountered during the monitoring system practical implementations. In [START_REF] Picozzi | Wireless technologies for the monitoring of strategic civil infrastructures: an ambient vibration test on the fatih sultan mehmet suspension bridge in istanbul, turkey[END_REF], authors present a lowcost wireless sensing unit designed to form dense wireless mesh networks. This device is developed for earthquake early warning projects, but it can be efficiently used as a tool for wireless structural monitoring as well. In order to determine the suitability of proposed system for structural monitoring appli-FIGURE 1.5 Locations of wireless sensors used for turbine health monitoring [START_REF] Swartz | Structural monitoring of wind turbines using wireless sensor networks[END_REF]. cations, they conduct experiments on Fatih Sultan Mehmet Bridge in Istanbul, Turkey. Finally, in [START_REF] Stajano | Smart bridges, smart tunnels: Transforming wireless sensor networks from research prototypes into robust engineering infrastructure[END_REF], authors tackle some problems and solutions for structural health monitoring (especially for tunnels and bridges), but also discuss the current state and limitations of the sensing and wireless technology that is currently used. Their work presents advices for future experimental practice and lessons learned from three deployment sites in United Kingdom: Ferriby Road Bridge, Humber Bridge and London Underground tunnel.

Equipment condition monitoring

The production process speed and quality depends on the equipment condition and accuracy. In this section we present some of the recent works in the field of industrial equipment condition monitoring for pipelines [START_REF] Murphy | Development of a wireless sensor network for collaborative agents to treat scale formation in oil pipes[END_REF][START_REF] Stoianov | Pipeneta wireless sensor network for pipeline monitoring[END_REF] and machinery [START_REF] Krishnamurthy | Design and deployment of industrial sensor networks: Experiences from a semiconductor plant and the north sea[END_REF][START_REF] Tiwari | Wireless sensor network for machine condition based maintenance[END_REF][START_REF] Wright | Condition monitoring in end-milling using wireless sensor networks[END_REF].

In [START_REF] Murphy | Development of a wireless sensor network for collaborative agents to treat scale formation in oil pipes[END_REF], authors develop the wireless network system for a team of underwater collaborative autonomous agents that are capable of locating and repairing scale formations in tanks and pipes within inaccessible environments. Authors describe in detail ad-hoc network hardware used in their deployments, that comprises the pH, proximity, pressure sensors and repair actuator. Furthermore, they describe the communication protocol and sensor/actuator feedback loop algorithms implemented on the nodes. Another work that focuses on WSN for pipeline monitoring is [START_REF] Stoianov | Pipeneta wireless sensor network for pipeline monitoring[END_REF], where authors describe the WSN whose aim is to detect, localize and quantify bursts, leaks and other anomalies (blockages or malfunctioning control valves) in water transmission pipelines. Authors report the results and experiences from real deployment and provide algorithms for detecting and localizing the exact position of leaks that is tested in laboratory conditions. The system presented in this work is also used for monitoring water quality in transmission and distribution water systems and water level in sewer collectors. In this context, the work can be classified as the process evaluation group of works (Section 1.5.2.1) as well.

In [START_REF] Tiwari | Wireless sensor network for machine condition based maintenance[END_REF], authors develop a WSN for machinery condition-based maintenance and they present design requirements, limitations and guidelines for this type of WSN applications. Furthermore, they implement their condition monitoring system in Heating & Air Conditioning Plant in Automation and Robotics Research Institute in University of Texas.

Authors of [START_REF] Wright | Condition monitoring in end-milling using wireless sensor networks[END_REF] propose the use of accelerometer based monitoring of machine vibrations and tackle the problem of predictive maintenance and condition-based monitoring of factory machinery in general. They demonstrate a linear relationship between surface finish, tool wear and machine vibrations thus proving the usability of proposed system in equipment monitoring.

In [START_REF] Krishnamurthy | Design and deployment of industrial sensor networks: Experiences from a semiconductor plant and the north sea[END_REF], authors focus on preventive equipment maintenance in which vibration signatures are gathered to predict equipment failure. They analyze the application of vibration analysis for equipment health monitoring in a central utility support building at a semiconductor fabrication plant that houses machinery to produce pure water, handle gases and process waste water for fabrication lines. Furthermore, authors deploy the same sensor network on an oil tanker in order to monitor the onboard machinery. In the end, they discuss design guidelines for an ideal platform and industrial applications, a study of the impact of the platform on the architecture, the comparison of two aforementioned deployments and a demonstration of application return on investment.

1.5 Process and service monitoring applications

1.5.

Concept and objectives

The last group of applications that we have considered are those concerned with monitoring processes and services. In our acception, the former is industry-oriented and it consists of all the activities performed by human workers or machines to produce goods; whereas the latter is user-oriented and it consists of the operations needed to provide end-users with specific services, such as electricity or water provision.

Process monitoring involves many industrial fields, since it focuses on tracking the quality of the entire life of a product, step by step from the materials provision used for its production till its disposal. Therefore, all the IWSN applications dealing with manpower and production materials tracking as well as logistics and transportation systems fall in this category. The role of IWSNs in these applications is driven by the need for evaluating and improving each and every step of goods production-distribution-consumption process as well as the cycle as a whole.

Service monitoring is mainly related to evaluating the quality of the provision of a specific service to end-users. The quality assessment can be performed in terms either of the efficiency of the provision line or the effectiveness of the service provision at the end-user's location. In the first case, service monitoring overlaps with the public/private infrastructure monitoring already investigated in Section 1.4, whereas the second is object of study in what follows. In service monitoring applications the IWSNs have the important role of offering both the provider and the consumer valuable information about the provision. From providers' perspective, remote monitoring/metering of electricity power, heat, water or gas is a simple and effective solution, in fact it has gained a great momentum in the last years. From consumer's perspective, IWSNs' applications represent a remarkable step in the direction of the green building deployment because they allow end-users to constantly estimate their energy expenditure as well as the quality of the environment where they live.

The applications for both the fields studied in this section would highly benefit from the integration of the actuator system in order to automatically improve the process/service provision and achieve the desired results. For this reason, we split the existing solutions subsection in two parts: the first describes research works aimed at evaluating and monitoring processes and services provision, whereas the second includes also the actuation, which allow the designer to close the feedback control loop and move towards completely automated systems.

Existing solutions FIGURE 1.6

Process automation and service provision monitoring.

Process and service provision evaluation.

In this subsection we present some recent research works on developing IWSN applications aimed at gathering all the needed information from the product/service in order to asses the quality of the production/provision process. This kind of applications are very useful from both the private citizen's or company's perspective and the public system's perspective. For example, in the United States, the Environmental Protection Agency claims that more than $18 billion a year could be saved by reducing the water consumption by 30% and that the American public water supply and treatment facilities consume about 56 billion kWh per year, which is enough electricity to power over 5 million homes [START_REF]Watershed assessment, tracking and environmental results[END_REF]. In [9], authors present an easy-to-install self-calibrating system that provides users with information on when, where, and how much water they are using. The approach is non-intrusive, cost-effective and easy to deploy. It is based on wireless vibration sensors attached to pipes, which are able to measure the water flow passing through the pipe and estimate consumption with a mean absolute error of 7%.

The United States Department of Energy in [START_REF]Energy Consumption Characteristic of Commercial Building HVAC System[END_REF] estimated that 10% of the total energy used by commercial sector is wasted by parasitic energy use in commercial building HVAC systems. Green building deployment is the best response to this energy waste, but it will take some years before local and international communities and politics will accept and implement a different way to design and build public and private constructions. In the meantime, HVAC monitoring system are very useful to evaluate waste and consumption. For example, in [START_REF] Jiang | Design and implementation of a high-fidelity ac metering network[END_REF], authors present a system for AC energy monitoring in large and diverse building environments. Their system provides real, reactive and apparent power measurements and comprises the metering control interface, IP compatible network structure and software that provides various powercentric applications.

As we said, the monitoring activities can involve also the life-cycle of a

FIGURE 1.7
Sensors deployed in a field for improved automated irrigation [START_REF] Mcculloch | Wireless sensor network deployment for water use efficiency in irrigation[END_REF].

product, from its production to its disposal. Specifically, we have selected two research works that fall in the subcategory of resource tracking and logistics, in order to show how IWSNs, because of their intrinsic capability to deal with dynamic process, are well suited to be used in highly constrained and resource demanding processes. In [START_REF] Bijwaard | Industry: using dynamic wsns in smart logistics for fruits and pharmacy[END_REF], authors present a way to apply the dynamic WSN in temperature controlled supply chain (cold chain) for fruit and pharmaceutical product storage and transport to avoid degradation and spoilage. The approach supports real-time monitoring and remote maintenance via wired and mobile wireless network access. In [START_REF] Riem-Vis | Cold chain management using an ultra low power wireless sensor network[END_REF], author presents the architecture and implementation of a self-configuring WSN used in a cold chain management tool that contributes to quality improvement and waste reduction.

1.5.2.2 Process and service provision improvement.

WSN dedicated for industrial process improvement represent maybe the most important part of all the industrially applicable WSNs since they usually comprise the actuator components as well. In this way, these IWSN could be observed as Automated Industrial Wireless Sensor and Actuator Systems, used for complete process automatization that are, therefore, wide spread and present in all the branches of industry. Backed up with the development of the sensing and communication component technology they represent the future of the Intelligent Process Automation Systems used in industry. A great number of works focuses on the agriculture production process amelioration. In [START_REF] Mcculloch | Wireless sensor network deployment for water use efficiency in irrigation[END_REF], authors describe the design, development and deployment of a WSN that improves the water efficiency in the field irrigation located in dry regions. In this way, with the use of temperature and humidity information it is possible to implement the automated control system that consume irrigation water in efficient manner (Figure 1.7).

Authors of [START_REF] Morais | A zigbee multi-powered wireless acquisition device for remote sensing applications in precision viticulture[END_REF] present the architecture, hardware and the software of the platform used for precision viticulture. A major feature of this platform is its power-management subsystem, able to recharge batteries with energy harvested from the surrounding environment. It allows the system to sustain operation as a general-purpose wireless acquisition device for remote sensing in large coverage areas. The platform is currently being used as a simple and compact yet powerful building block for generic remote sensing applications, with characteristics that are well suited to precision viticulture.

In [START_REF] Agarwal | Duty-cycling buildings aggressively: The next frontier in hvac control[END_REF], authors tackle the problem of energy consumption control by presenting a novel control architecture that uses occupancy sensing to guide the operation of a building heating ventilation and air-conditioning systems. By interacting between sensing and actuating part of the HVAC control, they achieve significant results in energy saving.

In the context of highly dynamic processes in modern factory facilities, authors in [START_REF] Korber | Modular wireless real-time sensor/actuator network for factory automation applications. Industrial Informatics[END_REF] present a conceptual study of a wireless real-time system dedicated for remote sensor/actuator control in production automation. They discuss the emphasis on timing behavior and power consumptions and review the system design aspects such as network topology, multiple access schemes and radio technologies suitable for these constrained application environments.

Commercial solutions for IWSN

Commercial solutions for infrastructural and equipment monitoring include complete wireless system solution, comprising wireless data acquisition, vibration sensors, signal conditioning for vibration sensors, and signal processing software for equipment failure prediction and diagnostic. The sensors and network hardware used in these solutions is capable of coping with most of the aforementioned technological challenges. Table 1.2 provides a list of services and solution providers to which an interested reader should refer. Environmental sensing. Depending on the environment in which sensors will be deployed, the hardware should be carefully studied. Indeed, environment monitoring refers to outdoor applications. Thus, sensors should be water-proof, prone to shocks, etc. This has a cost which represents a real challenge since such applications require the deployment of a great number of sensors, which can not be done if each single sensor is expensive. An important feature of wireless sensor networks deployed for environment monitoring is that the environment is not controlled, not controllable and possibly not easily accessible, i.e. if a sensor is moved (by animals or wind for instance), the network must continue to work properly. Network basic mechanisms such as neighbor discovery or routing must adapt this mobility. This remains a great challenge.

Condition monitoring. Recent technological advances will permit the development of intelligent sensors and therefore the development of low-cost intelligent monitoring systems capable of reliable equipment failure prediction. Furthermore, technological advances allow the development of structures, production lines and individual equipment components with built-in sensors, emergence of self-monitoring equipment that would behave as an ad-hoc network and that would easily communicate with other parts of condition monitoring system. In the context of automation and maintainability, the integration of complex software solutions onto sensing network and sensor firmware that would introduce the concept of failure prediction and real-time problem diagnostics. In the end, all the acquired condition monitoring information provide important guidelines and could serve the purpose of "to do" list for future civil infrastructure and production equipment design and construction.

Process automation. Designers and developers of Wireless Sensor Networks have lost their initial view of WSN as a single system composed of simple and homogeneous devices. From the referenced works, we have seen that, especially in industrial applications of WSNs for process and service monitoring, the trend is to deploy pervasive systems of heterogeneous capabilities. These systems look at the nodes capabilities as the constituent blocks for designing new applications and, in turn, this calls for a standard communication paradigm. The process monitoring also offers the possibility to pave the way for the concept of "plug-in network", which is a network of heterogeneous device able to become part of a larger network, when some spatial proximity condition is satisfied. Therefore, we can imagine networks of devices deployed in a container to monitor the transportation conditions of some goods, which are able not only to communicate immediately with the "driver" if a problem occurs, but also participate in successive phases of the consumption phase once they arrive on the delivery site. Specifically for service provision monitoring, as we have already said the IWSN deployed to measure consumption and quality of the service provided represent an important step towards the design of green building where the consumption of energy is limited by new construction techniques, but IWSN can ensure a continuous and constant monitoring and fixing of consumptions, failures, wastage, etc. IWSN applications for process and service provision have gained a lot of market in the last years, because of the complete control they offer in the whole life-cycle of a product, it is very likely that the growth of this technology in the years to come will be even stronger, if designers and developers are able to create high-specialized products for specific needs as well as cheap and customizable platforms for householders and small companies.

FIGURE 1 . 1

 11 FIGURE 1.1 Taxonomy of industrial wireless sensor network applications.

FIGURE 1 . 2

 12 FIGURE 1.2 Environmental sensing applications.

FIGURE 1 . 3

 13 FIGURE 1.3Installation of water level sensor prototype for hazard prevention[START_REF] Basha | Model-based monitoring for early warning flood detection[END_REF].

FIGURE 1 . 4

 14 FIGURE 1.4 Condition monitoring applications.

7

 7 ABB

TABLE 1 . 1

 11 Main industry branches in 4 sectors.

	Sector	Branch	Environmental	Condition	Process
			Poll. Haz. Sec. Struc. Equip. Eval. Impr.
	I	Mining, logging

TABLE 1 . 2

 12 Commercial solution and service providers for IWSN