Luciana Arantes
email: luciana.arantes@lip6.fr

Roy Friedman

Olivier Marin

Pierre Sens
email: pierre.sens@lip6.fr

Probabilistic Byzantine Tolerance Scheduling in Hybrid Cloud Environments

This work explores scheduling challenges in providing probabilistic Byzantine fault tolerance in a hybrid cloud environment, consisting of nodes with varying reliability levels, compute power, and monetary cost. In this context, the probabilistic Byzantine fault tolerance guarantee refers to the confidence level that the result of a given computation is correct despite potential Byzantine failures. We formally define a family of such scheduling problems distinguished by whether they insist on meeting a given latency limit and trying to optimize the monetary budget or vice versa. For the case where the latency bound is a restriction and the budget should be optimized, we present several heuristic protocols and compare between them using extensive simulations.

introduction

High performance distributed computing (HPDC) is typically obtained by breaking large computational problems offering trivial parallelism into multiple independent compute tasks and scheduling each task to be executed in a distributed environment. This enables solving heavy computational tasks using commodity hardware and operating systems.

With cloud technology, it is common to submit computations to virtual machines hosted in the cloud. The benefit of clouds includes their increased dependability and availability. However, cloud usage for heavy computations involves substantial financial costs.

This motivates exploring hybrid computing architectures that combine desktop Grids with cloud hosted computing. In such a system, a large fraction of the computation is performed by donated machines, which significantly reduces the cost to the owner of the computation. Yet, when donated machines fail to ensure timely reliable completion, parts of the computation can be transferred to the cloud where they are ensured to obtain enough resources to complete.

Unfortunately, donated computers suffer from a non-negligible probability that some of them will not always return correct answers, i.e., act in a Byzantine manner. Such behavior might result, e.g., from malice on behalf of the owner of the machine, from intrusions to the machine, or from faults and bugs in hardware and software.

On the other hand, cloud servers and their VMs are likely to be more dependable than regular home machines. This is because cloud providers have a monetary incentive to protect their infrastructure from intrusions and to maintain their hardware and operating systems up to date. However, these cannot completely rule out intrusions and other forms of Byzantine hardware.

Finally, with recent trusted computing hardware, cloud providers can maintain a smaller set of fully trusted machines. Given the higher cost of trusted computing hardware, it is sensible to assume that these nodes will be scarce and their usage will be considerably more expensive than using standard cloud nodes.

Our contributions First, we define a probabilistic hybrid computing model for HPDC composed of both home donated machines and cloud nodes. In this model, each computational task has a minimal required reliability level, a latency bound, and a budget. Similarly, each node has a known computing speed, monetary cost, and reliability reputation. We distinguish between home donated nodes which are very cheap, but are also not very reliable, standard cloud nodes which are much more dependable and powerful, but are more expensive, and cloud fully trusted nodes, which are completely dependable, but much more costly than the others and are slower than the standard cloud nodes.

Second, we define corresponding scheduling optimization problems that need to ensure that computational tasks meet their requirements. In all of them, the scheduler's goal is to find compute nodes that can return a reply whose correctness is above a given reliability threshold. However, they vary in the latency and budget guarantees they provide. One set of problems ensure bounded latency and attempt to minimize the required budget while the others ensure a bounded budget and try to minimize the latency. Third, we devise several heuristic protocols for these problems. For lack of space, this paper focuses on solving the variant in which the latency bound must be observed while trying to minimize the required budget.

Last, we evaluate the performance of our protocols by simulation. Results show that in all tested workloads, an adaptive protocol, which schedules tasks on different groups of nodes, is efficient and successfully allocates all tasks within the latency constraints.

The rest of this paper is organized as follows: We survey related work in Section 2. Model assumptions are defined in Section 3. The problem statements as variations of optimization problems are presented in Section 4. Section 5 describes our scheduling protocols for bounded latency. Section 6 presents performance evaluation results of these protocols through extensive simulations. Finally, Section 7 concludes the paper.

Related Work

There is vast literature on Byzantine fault tolerance (BFT), mainly w.r.t. consensus and state replication, e.g., [START_REF] Aublin | The next 700 bft protocols[END_REF][START_REF] Castro | Practical byzantine fault tolerance and proactive recovery[END_REF][START_REF] Clement | Upright cluster services[END_REF][START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF][START_REF] Garcia | Efficient middleware for byzantine fault tolerant database replication[END_REF] to name a few. In particular, multiple works have studied the notion of probabilistic consensus, where either safety is always ensured and termination becomes probabilistic or vice versa, e.g., [5-7, 10, 16, 21, 24, 25, 30]. Such level of BFT requires a minimum of 3f + 1 replicas, resulting in significant resource overheads, especially when f can be larger than 1.

Reducing this inherent overhead has been explored in several ways. One example is the introduction of wormholes and other types of trusted hardware components [START_REF] Veronese | Efficient byzantine fault-tolerance[END_REF]. Another idea is separating ordering from execution as proposed in [START_REF] Yin | Separating Agreement from Execution for Byzantine Fault Tolerant Services[END_REF], such that the data itself is replicated only on 2f + 1 nodes. Yet, this requires a separate ordering service, often implemented by traditional BFT protocols, so the savings depends on data being much larger than control and meta-data sizes.

Several works have explored how to harden high performance distributed computing environments, such as [2, 3], against Byzantine failures [START_REF] Agbaria | A Replication-and Checkpoint-Based Approach for Anomaly-Based Intrusion Detection and Recovery[END_REF][START_REF] Bondavalli | An Adaptive Approach to Achieving Hardware and Software Fault Tolerance in a Distributed Computing Environment[END_REF][START_REF] Brun | Smart Redundancy for Distributed Computation[END_REF][START_REF] Sarmenta | Sabotage-Tolerance Mechanisms for Volunteer Computing Systems[END_REF][START_REF] Sonnek | Reputation-based scheduling on unreliable distributed infrastructures[END_REF]. Our model differs from theirs in the following ways: At the node level, we incorporate in our model the reliability level of each node, the computational power of each node, and the monetary cost of using each node. In particular, we assume a hybrid execution model composed of nodes from several levels of reliability, compute power, and cost. Further, at the computational task level, we combine a minimal reliability level, latency constraints, and budget constraints. Hence, the scheduling task in our work is much more involved.

A pull-based scheduler for hybrid distributed computing infrastructure (Desktop, Grid, and Cloud nodes) that relies on multi-criteria decision-making method for task assignment is presented in [START_REF] Moca | Multi-criteria and satisfaction oriented scheduling for hybrid distributed computing infrastructures[END_REF]. The multi-criteria method computes for each task a set of criteria according to the characteristics of the node requesting a task. Among the criteria, the authors propose the expected time and cost to complete the task, as well as the the estimated error impact of scheduling the task to the pulling node, taking into account both its reputation and the size of the task. Similarly to us, their aim is to find an optimal scheduling strategy in a hybrid environment that satisfies user constraints expressed in terms of cost, price, and reliability. To this end, they apply a filtering methodology denoted SOFT. Yet, contrarily to our approach, their scheduler is pull-based where idle nodes ask for task assignment, there is no Byzantine behavior, and the scheduler does not apply a per group selection approach as our adaptive protocol does in order to avoid combinatory explosion. Some hybrid Cloud platforms combine public and private Clouds. Some works [START_REF] Hong | Failure-aware resource scheduling policy for hybrid cloud[END_REF][START_REF] Javadi | Failureaware resource provisioning for hybrid cloud infrastructure[END_REF] focus on resource provisioning in the presence of failures. Private cloud nodes are usually considered free for users but prone to failures whereas public cloud nodes are trusted (failure-free) but users must pay to use them. As in our approach, task scheduling decisions depend on reliability requirements and cost constraints. For instance, in [START_REF] Javadi | Failureaware resource provisioning for hybrid cloud infrastructure[END_REF], the authors consider that failures in private cloud can be correlated in space and time. Hence, jobs that request more than a number of VM threshold or last more than a deadline threshold are redirected to public cloud nodes. That is, home nodes are expected to have relatively lower compute power and high churn rate, meaning that their availability and reliability are low. In particular, the probability of Byzantine behavior on their part is higher than all other nodes. Usage of home nodes is assumed to be very cheap, but not completely free of charge, as typically cloud providers charge a small amount of money for I/O outside the cloud.

Standard cloud nodes have relatively high compute power and can be allocated on demand. They are much more reliable than home nodes, but they might still occasionally fail including in a Byzantine manner. Utilizing standard cloud nodes involves paying a small fee.

Finally, fully trusted cloud nodes have a very low probability of suffering a crash failure, and never suffer from Byzantine failures. The number of fully trusted cloud nodes is bounded and their usage cost is significantly higher than using standard cloud nodes.

The existence of such fully trusted nodes is backed by recent advancements in trusted cloud computing hardware [START_REF] Veronese | Efficient byzantine fault-tolerance[END_REF], or alternatively can be realized by clustering standard cloud nodes using BFT techniques [START_REF] Aublin | The next 700 bft protocols[END_REF][START_REF] Castro | Practical byzantine fault tolerance and proactive recovery[END_REF][START_REF] Clement | Upright cluster services[END_REF]. Further, the scheduler, which accepts the computing tasks and distributes them to various compute nodes, runs on a fully trusted cloud node. That is, the scheduler is assumed to be fault-tolerant, always available, and it always obeys its prescribed protocol.

The communication in the system is performed by sending and receiving messages over a communication network. The network is assumed to be authenticated and reliable, with a bounded communication latency. That is, a message is only received if it was indeed sent by some node, and the receiver always knows who the true sender of a message is.

As mentioned before, the home nodes and standard cloud nodes may occasionally act in a Byzantine manner. That is, while executing a compute task, each such node p may return an incorrect answer (or not answer at all) with probability q p . We refer to the probability r p = 1 -q p that p returns a correct answer as the reliability or reputation of p. Notice that r p may change overtime. When the system starts, for any home node p i and arbitrary standard cloud node p j , r pi < r pj . Further, even when the reliability of nodes changes over time, the above inequality would remain true for the vast majority of home nodes and cloud nodes. Obviously, for a fully trusted node p, r p is always 1.

Whenever a scheduler node receives a compute task, it sends it either to a fully trusted cloud node or to multiple compute nodes. In the former case, the scheduler knows that it will get a correct answer. However, since fully trusted nodes are scarce and expensive, the scheduler often prefers the latter option. In these cases, when the replies arrive, the scheduler compares them. If they all agree, then the scheduler knows that this is the correct answer with a certainty that depends on the reputations of the chosen nodes. Otherwise, if some replies do not return within the deadline, the scheduler knows that these nodes are faulty and sends the same compute task to additional nodes. Yet, if the replies do not match, then the scheduler knows that at least some of the nodes acted in a Byzantine manner and may send the compute task to additional nodes until it has enough probabilistic confidence in one of the replies.

Each compute task τ has a normalized compute time T τ and that each compute node p has a known computing speed c p . So when there are no failures, a task τ that is scheduled to be computed on a node p completes its execution on p within time T τ /c p . Further, each compute node p charges d p units of money per second of computing (for home nodes d p = 0). Hence, the cost of computing task τ on node p is

Tτ •dp cp .
The number of nodes needed to execute each compute task to obtain a trusted reply as well as the expected compute time and cost are the main topic of this paper.

A Generic Model of Hybrid Computation

In the most generic case, compute nodes are divided into multiple groups {G i }, each characterized by an initial reputation value R i , its own scheme for managing the reputation by the scheduler F i , a range of compute power [C min ]. The reputation management scheme F i is a function that is invoked by the scheduler each time a computation that p was involved in terminates and sets a new value for r p based on its old value and all returned results for the compute task.

In the case of home machines, standard cloud nodes, and fully trusted cloud nodes, each of the above forms a group. For the fully trusted nodes At the other end, in the desktop group, R i < R k for any other group k, i.e., these nodes are the least trusted. Also, D min i ≤ D max i << D k for any other k, i.e., using these nodes is very cheap compared to the others.

R i = 1 and F i ( * ) = 1. Further, D min i > D max
Several works explored the reputation management schemes (F i s) and its effectiveness, e.g., [START_REF] Arantes | Probabilistic byzantine tolerance for cloud computing[END_REF][START_REF] Hoffman | A survey of attack and defense techniques for reputation systems[END_REF][START_REF] Resnick | Reputation systems[END_REF][START_REF] Sarmenta | Sabotage-Tolerance Mechanisms for Volunteer Computing Systems[END_REF]. For lack of space, we defer exploring the impact of F i to future work. In particular, the simulations in Section 6 assume that each node has a fixed reliability level.

Problem Statement

We present two variations of an optimization problem. Specifically, the goal of the scheduler is to submit each task to one or more compute nodes such that the reliability level of the result is equal or greater to a given threshold ρ. In one variant of the problem, each application, composed by a set of tasks, gets a maximum budget allocation, and the scheduler needs to minimize the expected latency until obtaining a correct answer. In the other variant, the application has a maximal latency and the scheduler needs to minimize the cost of the computation. Yet, in order to rigorously state the problem definitions, we must first develop adequate terminology. In the definitions below, for simplicity of presentation, we ignore the transmission times of messages.

Framework and Terminology

Schedules

Given a compute task τ , a schedule Γ τ is a sequence of tuples {< t i , p i >} representing a time t i and a compute node p i such that for each two tuples < t i , p i > and < t j , p j > in Γ τ , if p i = p j and < t i , p i > appears before < t j , p j > in Γ τ then t i ≤ t j . Intuitively, the schedule indicates the starting time of the task on each compute node.

Since we assumed that each task τ has a normalized compute time T τ and each node p has a compute power c p , each tuple in Γ τ is implicitly associated with a time t i = t i + Tτ cp such that if p is correct, the scheduler is guaranteed to obtain a reply from p by t i . In fact, if no reply is received by t i , then p is assumed to be faulty.

Reply Sequences

Suppose τ is sent to various compute nodes according to Γ τ . The replied values can be represented by a sequence V Γτ of tuples < t i , v i > where v i is the corresponding reply value arriving at time t i . If a reply does not arrive in time, the matching v i is set to ⊥. In case p i is correct, v i is the correct reply. A reply value sequence V Γτ is called complete if for each tuple in Γ τ there is a corresponding tuple in V Γτ and is said to be partial if it is a prefix of a complete reply sequence.

Runs

Next, we define a boolean stopping function ST (V Γτ ) = [true, false]. Intuitively, this function enables the scheduler to stop the schedule prematurely, before contacting all nodes indicated by the schedule, whenever the replies obtained so far meet the condition indicated by the stopping function. To that end, we define a stoppable schedule to be the combination of a schedule and a corresponding stopping function. Hereafter, we only deal with stoppable schedules. Hence, whenever we write schedule, we in fact mean stoppable schedule.

A (partial) reply sequence V Γτ is called minimal if ST (V Γτ ) = true and for each prefix V of V Γτ , ST (V ) = false. Each combination of a schedule and a minimal reply sequence defines a run σ.

Latencies and Budgets

Let < t 1 , * > be the first tuple in a schedule of a run σ and let < t k , * > be the last tuple in the matching reply sequence of σ. We define the latency of σ (denoted L σ ) to be t k -t 1 . Similarly, we define the budget spent during σ (denoted B σ ) as the total cost of all compute nodes whose replies appear in the corresponding reply sequence V Γτ . That is, let S σ be this set of compute nodes. We then have

B σ = p∈Sσ Tτ dp cp .

Two Families of Problems

We define two families of dual optimizations problems. In the first, latency must be kept below a given bound while the budget should be minimized. In the second, the budget must be kept below a given bound while latency should be minimized.

Bounded Latency

Given a task τ , a latency threshold ∆ τ and reliability threshold ρ τ for task τ , the scheduler's goal is to find a schedule Γ τ minimizing the corresponding budget B(Γ τ ) for computing τ while obtaining an answer whose reliability is above ρ τ and the latency L(Γ τ ) is at most ∆ τ time (assuming feasible).

Bounded Budget

Given a task τ , a budget threshold Φ τ and reliability threshold ρ τ for task τ , the scheduler's goal is to find a schedule Γ τ minimizing the corresponding latency L(Γ τ ) for computing τ while obtaining an answer whose reliability is above ρ τ and the budget B(Γ τ ) is at most Φ τ (assuming feasible).

As mentioned before, due to lack of space, in this paper we focus on solving the bounded latency problem.

Greedy Bounded Latency

In this section, we present several variants of scheduling protocols addressing the bounded latency problem. The first set of protocols always attempt to find a schedule from the same group of nodes (home, cloud, or trusted) in an iterative manner. Conversely, the other protocol employs an adaptive mechanism in which it considers all groups and chooses the cheapest option that still ensures timely termination.

Single Group Protocols

We identify three protocols in the single group category, nicknamed scrooge, moderate, and cautious. The only difference between these protocols is in the group of processes from which each of these protocols looks for its candidate nodes; scrooge only utilizes home nodes, moderate only accesses standard cloud nodes, while cautious only fully trusted nodes.

In all three protocols, the scheduler invokes the following iterative loop, as outlined in Algorithms 1, 2, 3, and 4: First, it looks for the cheapest set of available nodes from the corresponding group (home, standard cloud, or trusted) such that the probability that all of them are Byzantine is below the required reliability threshold and the maximal latency of any of them for the given compute task is below its latency requirement. The task is then sent to all chosen nodes to be computed and the scheduler waits until it receives either a reply from all of them or a timeout equal to the longest expected latency has passed. If all replies have arrived and all have the same value, then the scheduler returns this value.

Otherwise, suppose some value v has appeared in the maximal number of replies (breaking symmetry arbitrarily). The scheduler looks for another set of processes such that if they all return v, then the probability that v is the correct value is above the required threshold. Here again, the cheapest possible set that meets the remaining latency deadline is chosen. This process repeats until either the probability that some returned value is correct meets the reliability threshold, or it is not possible to find additional nodes that can compute the task within the required deadline.

Algorithm 1 Probabilistic Functions

1: // Returns true if the probability that all nodes in S are Byzantine is ≤ q 2: function AllByz(S, q) 3:

return p i ∈S (1 -ri) ≤ q
4: 5: // Returns the probability that at least one of the nodes in values whose value is v is correct and all nodes proposing other values are Byzantine 6: // Also, return the needed probability from additional set of supporters of v to ensure that v is correct if not already obtained 7: function ProbCorrectValue(v, values, q) 8:

if v == ⊥ then 9:
return (0,0) 10:

S1 = {pi|(vi, pi) ∈ values vi == v} 11: AtLeastOneCorrect = 1 -p i ∈S 1
(1 -ri)

12:

S2 = {pi|(vi, pi) ∈ values vi = v} 13: AllByzantine = p i ∈S 2 (1 -ri)
14:

ProbCorrectV = AtLeastOneCorrect • AllByzantine 15:
if ProbCorrectV < q then 16: To understand the calculation for ExtraNeeded in Algorithm 1, let's denote ProbCorrectV by A, AllByzantine by C, and the calculation pi∈S1 (1-r i ) by D. Obviously, we can write A = (1 -D)C. Similarly, we can write q = (1 -DX)C where X is the probability that all nodes in the added set (that is required) are Byzantine. In other words, 1 -DX is the probability that the combined set of existing nodes that support v and all added nodes will include at least one correct node. Using simple algebra, we get that X = C-q C-A , or as written in Figure 1, ExtraNeeded = AllByzantine-q AllByzantine-ProbCorrectV .

ExtraNeeded = AllByzantine-q AllByzantine-ProbCorrectV

The Adaptive Protocol

As before, in the adaptive algorithm too we allow multiple sequential invocations of the task until some returned value obtains enough reliability to be considered the correct reply value. However, here we allow to switch between the different groups of nodes (home, cloud, trusted). That is, home nodes are the cheapest, but may not be able to provide a reliable answer within the deadline due to their low reliability. Trusted nodes always return a correct answer, Algorithm 2 Helper Functions

23:

wait for replies from each pi ∈ set or timeout after latency time

24:

replies = set of tuples (vi, pi) of replied values and corresponding nodes who returned these values

25:

for nodes pi that failed to return any value by the latency timeout, the value is vi = ⊥

26:

return replies but are expensive and scarce, and hence are likely to run out if we insist on only using them. Cloud nodes are more reliable than home nodes, but might still fail and are considerably more expensive than the home nodes.

Hence, we start with the cheapest set among all groups that is likely to produce a correct result. But, this time, we reserve enough latency so that in the worst case, we can resort to a trusted node, or to at least a collection of cloud nodes, in order to ensure reliable termination.

Obviously, trying all possible combinations of nodes to determine the optimal one is too expensive. Hence, in each iterative step we always select sets of nodes from the same G i group. Moreover, we identify a few subsets in each group and try combinations of these subsets such that the total latency is below the threshold while the ensured reliability is above return first(first(values))

12:

else 13:

If the probability that the majority value v is correct is high enough, return it. Otherwise, try collecting additional answers from the cheapest set of additional nodes from G such that they can return the reply in the remaining time before the deadline and if they all return v as well, it will be certain that v is correct return Schedule(G T , Tτ , ∆τ , ρ) the threshold. We then choose the set whose cost is minimal among them.

Specifically, in each iteration we first identify the cheapest and fastest available trusted nodes that can compute T τ within the remaining deadline ∆ . Obviously, in the first iteration, the above is done w.r.t. the entire deadline, i.e., ∆ = ∆. Denote the faster of these nodes p F T and the cheaper p E T (so F stands for fast and E for economic and T for trusted). Similarly, denote the latency and budget that would be spent when executing on p F T by L F T and B F T respectively. In symmetry, denote the latency and budget that would be spent when executing on p E T by L E T and B E T respectively. Considering these two latencies, we now identify sets of standard Cloud nodes that can potentially compute T τ with the required reliability (if all return the same value) within ∆ F = ∆ -L F T and ∆ E = ∆ -L E T , respectively. For each of these corrected latency bounds, we search for the cheapest and fastest sets of cloud nodes. Denote these sets of cloud nodes S F F C , S F E C , S EF C , and S EE C . Similarly, we denote the corresponding latency and budget to be spent by each of these sets by

L F F C , B F F C , L F E C , B F E C , L EF C , B EF C , L EE C and B EE C .
Finally, for each of the above latencies, we identify sets of home nodes that can potentially compute T τ with the required reliability level (if all return the same value) within

∆ F F = ∆ F -L F F C , ∆ F E = ∆ F -L F E C , ∆ EF = ∆ E -L EF C ,
L F F H , B F F H , L F E H , B F E H , L EF H , B EF H , L EE H and B EE H . Considering p F T = S F T and p E T = S E
T , once we have all the 10 sets, the scheduler picks the one whose budget is smallest, sends the computation to that set and waits either for all replies or a timeout.The scheduler then checks if some value has enough support to be deemed correct with the required reliability threshold. If yes, then this value is returned. Otherwise, the scheduler continues to the next iteration. The pseudo-code for this protocol appears in Algorithms 5 and 6.

Evaluation

We evaluate our algorithms and show the advantage of the adaptive approach. Our experiments consist of simulating the various protocols described in Section 5 along the metrics defined in Section 6.1 below. The parameters for the simulations are detailed in Section 6.2.

Metrics

We define the following metrics for comparing the performance of the various protocols: if cands == ∅ then

5:

return {(∅, 0, 0), (∅, 0, 0)}

6:

else 7:

Identify the cheapest set, break ties arbitrarily 8:

sets = {Si ⊆ cands| All- Byz(Si, ρ)} Siis minimal such set} 9: cheapests = {Si ∈ sets| p i ∈S i T d i c i is minimal in sets} 10: if |cheapests| > 1 then 11: cheapest = Si| min p i ∈S i ci

20:

Return found sets with their budget and latency

21:

if cheapest == fastest then

22:

return {FleshOut(cheapest, T ),(∅, 0, 0)}

23:

else

24:

return {FleshOut(cheapest, T ),FleshOut(fastest, T )} is submitted and the time it responds (both the average and the distribution); (iv) Task deadlines satisfaction (fail ratio): Percentage of task deadlines that were satisfied w.r.t. latency (deadline) and reliability constraints. A failure of a task is due either to wrong answers from Byzantine nodes which delay the response time or an overload of compute nodes; (v) Distribution of scheduled nodes: The total number of home, standard cloud, and fully trusted nodes used by each of the protocols; (vi) Scheduler compute time: The amount of CPU time used by the protocol to schedule all the tasks. This metric indicates the computational complexity of the protocol, which is important for scalability.

Simulation setup

Our simulations are conducted with Matlab 1 . Since the proposed algorithms need to compute all subsets Algorithm 6 Adaptive Algorithm 1: Main code: 2: values = ∅ 3: reqrel = 1 -ρ 4: loop 5:

(S E T , B E T , L E T , S F T , B F T , L F T ) = Find2Sets(G T , Tτ , ∆, reqrel) 6: (S EE C , B EE C , L EE C , S F E C , B F E C , L F E C ) = Find2Sets(G C , Tτ , ∆ -L E T , reqrel)
7:

(S EF C , B EF C , L EF C , S F F C , B F F C , L F F C ) = Find2Sets(G C , Tτ , ∆ -L F T , reqrel)
8:

(S EE H , B EE H , L EE H , -, -, -) = Find2Sets(G H , Tτ , ∆ - L EE C , reqrel)
9:

(S EF H , B EF H , L EF H , -, -, -) = Find2Sets(G H , Tτ , ∆ - L EF C , reqrel)
10:

(S F E H , B F E H , L F E H , -, -, -) = Find2Sets(G H , Tτ , ∆ - L F E C , reqrel)
11:

(S F F H , B F F H , L F F H , -, -, -) = Find2Sets(G H , Tτ , ∆ - L F F C , reqrel)
12:

set = S ∈ {S E T , S F T , S EE C , S F E C , S EF C , S F F C , S EE H , S EF H , S F E H , S F F H }| S = ∅
the corresponding budget is minimal

13:

L S denotes the latency of S

14:

if set == ∅ then

15:

raise no schedule found

16:

values = values ScheduleStep(set, Tτ , LS )

17:

if |values| == 1 this value = ⊥ then

18:

If all nodes replied the same value, return it

If the probability that the majority value v is correct is high enough, return it. Otherwise, try collecting additional answers from the cheapest set of additional nodes from G such that they can return the reply in the remaining time before the deadline and if they all return v as well, it will be certain that v is correct

22:

v = the most frequent value in values 23:

∆ = ∆ -LS

24:

(rel, reqrel) = ProbCorrectValue(v, values, ρ)

25:

if rel ≥ ρ then

26:

return v of nodes that satisfy a criteria of cost and/or time which may lead to a combinatory explosion, an exhaustive search of all subsets is too costly. For instance, assigning 1,000 tasks with normalized duration of 180 seconds to 300 nodes by the Moderate algorithm takes 2887 seconds on a 2 cores Intel core I7 at 1.8GHz. Inspired by the power of two random choices [START_REF] Mitzenmacher | The power of two choices in randomized load balancing[END_REF], we circumvent this combinatorial explosion by random sampling of subsets and then choosing among them the one that satisfies the criteria. For instance, the 10 sampling version of the Moderate algorithm generates results which are 93% close to the original algorithm's in less than 0.5 second. Consequently, the performance results shown here correspond to the modified versions of our algorithms that use a 10 random sampling.

Nodes setting We consider 3 sets of nodes (Trusted, Cloud, and Home). Each of them is associated to some computing power and financial cost per hour.

Trusted nodes. These secure cloud nodes do not need replicated execution. Alas, they are more expensive and slower than Cloud nodes. Each Trusted node has the processing power of a medium Home node with 8 ECUs (EC2 Computing Units). One ECU provides equivalent CPU capacity of 1.0-1.2 GHz 2007 Opteron. A Trusted node cost corresponds to a high power node in Amazon (c4.8xlarge), which is 1.763 dollars per hour according to EC2 pricing (https://aws.amazon.com/ec2/).

Cloud nodes. These cloud nodes are less secure but more powerful than Trusted nodes. In our simulations, Cloud nodes consist of three types of EC2 Amazon nodes from medium to high computing performance (c4.large, c4.xlarge, and c4.2xlarge instances) corresponding to Intel Xeon E5-2666v3 with 8, 16, and 31 ECUs respectively. The EC2 computing cost per hour for these node types is 0.11, 0.22, and 0.441 dollars respectively.

Home nodes. These home nodes are cheaper and less trusted than the other two kinds of nodes. Their compute power varies from 2 to 16 equivalent ECUs (2, 4, 8, and 16). To estimate their cost, we consider their electric consumption. We assume that each node consumes 100 Watt per hour and that the cost of energy is between 10 and 40 cents per KW/h (the average cost of energy in north America and Europe). Their resulting costs are 0.01, 0.015, 0.02, and 0.04 dollar per hour.

For our simulation experiments, we consider an environment with 5,000 Home nodes, 500 Cloud nodes, and 50 Trusted nodes. In particular, there are 10 times more Home nodes than Cloud nodes and 10 times more Cloud nodes than Trusted nodes. Further, the percentage of Byzantine nodes in the Home nodes group is higher than in the Cloud nodes group while correct nodes in the latter have higher reputation than in the former. Table 2 summarizes our nodes setting for the three groups of nodes. In the table, the reputation value of correct is denoted r and Byzantine nodes rb, while the percentage of Byzantine nodes is denoted b. Application setting We consider a bag of tasks (BoT) application representative of private Home Grid deployments [START_REF] Delamare | Spequlos: a qos service for hybrid and elastic computing infrastructures[END_REF]. The reliability threshold is ρ τ = 0.999. We generated two scenarios with different loads with regard to the number of concurrently submitted tasks: low load (5,000 tasks) and high load (20,000 taks), as summarized in Table 3. The duration of tasks follow a normal distribution with a mean duration around 180 seconds on one ECU. Both the mean duration of tasks and the standard deviation are set to be the same as the ones of BoT application deployed on the Home Grid of the University of Notre Dame [START_REF] Rood | Multi-state grid resource availability characterization[END_REF]. The deadline of every task is 2.5 times the completion time on one ECU.

Low workload evaluation

Table 4 summarizes the cost, completion time, fail ratio, and the time spent by the scheduler for the four algorithms. We observe that Scrooge has the lowest cost among the single group algorithms. Scrooge is competitive since its nodes are cheap and abundant so they can easily handle the load within the deadline constraints. Moderate and Scrooge allocate additional nodes when wrong responses are received: on average, a task is replicated 4.225 times in the case of Home nodes and 2.227 times in the case of Cloud nodes. On the other hand, even if Trusted nodes are never replicated, they cannot ensure the execution deadline of most of the tasks. The adaptive protocol also succeeds to execute all the tasks within their deadline. Compared to the cheapest single protocol, i.e., Scrooge, the response time for the application is 2.48% lower. However, even if the cost of the adaptive protocol is 10.58% smaller than Scrooge, we cannot conclude that the adaptive protocol is always the cheapest since the difference of costs is due to the heterogeneity of nodes and the load distribution.

Table 5 shows the distributions of load in terms of the number of tasks executed by nodes of different groups. A Trusted node executes 21 tasks and then fails to satisfy deadlines. The load is unbalanced in both Cloud and Home nodes since the power of nodes is highly heterogeneous. Powerful nodes execute a large number of tasks. In both Scrooge and Adaptive, Home nodes are not used since the number of tasks is relatively low.

Figure 2 gives the computation time of each task. We observe that only 1,050 tasks are completed before their deadline in the Cautious algorithm, the Moderate algorithm fails to complete 19 tasks, and only Scrooge and Adaptive succeed in completing all tasks. In the adaptive approach, we observe that Trusted and Home nodes execute all the tasks, i.e., no task is assigned to nodes of the Cloud group. Interestingly, even in the relatively low load configura- Table 7: Distribution of tasks on nodes with high load tion, the application benefits from the algorithm since it distributes the load among the cheapest nodes but assigns a task to a Trusted node whenever the execution of this task cannot be performed on the Home group.

High workload evaluation

Table 6 summarizes the results with heavy load. Since there is no sharing of tasks between the three groups for the single group approach, the three algorithms fail to complete the deadline for a large number of tasks. Having a higher number of nodes (20,000), Scrooge is clearly the most efficient with regard to fail deadline ratio. However, costs are not representative since the algorithms do not succeed in executing all the tasks. The average costs in dollars per scheduled tasks are 0.011, 0.0025, 0.00064 in Cautious, Moderate, and Scrooge respectively. The adaptive algorithm succeeds in executing all the tasks within their deadline. Compared to the single group algorithms, the response time for the application is lower than Scrooge and the global cost is higher since all tasks are scheduled. The average cost per task is 0.00089 dollars. The cost per task is 38,4% higher than with Scrooge since the adaptive scheduler needs to use expensive Trusted nodes in this scenario. Table 7 provides the tasks distribution per node for each group. The load distributions are similar to the low load scenario. The algorithms favor choosing powerful nodes; even if the latter are more costly, they succeed more often to complete tasks within the deadline. Thus, their short response time reduces costs. Notice that the adaptive algorithm uses all three sets of nodes. Figure 3 shows the computation time of each task. In the single group approach, a large number of tasks cannot meet their deadline and are, thus, not scheduled. As shown in Figure 3(a), after 1,000 tasks, no other task is scheduled by the Cautious protocol. The gaps without load after the number of scheduled tasks reaches 5,500 in Figure 3(b) indicate that many tasks could not be scheduled in the Moderate protocol. Some tasks, denoted "faulty tasks", are scheduled on Cloud and Home nodes but fail to meet their deadline because of the high number of additional nodes needed to obtain enough correct answers. Among the 6, 753 tasks it schedules, Moderate generates 173 faulty tasks (2.56%) while Scrooge generates 332 faulty tasks among its 17, 253 scheduled tasks (1.92%). Figure 3(d) gives the computation time of each task with Adaptive. We observe that Trust nodes start participating in the computation after 8,000 scheduled tasks. After 15, 000 tasks, Trust and Home nodes become overloaded and then tasks are mainly scheduled on the nodes of the Cloud group. Ultimately, 17, 308 tasks are scheduled on Home nodes, 2, 692 on Cloud nodes, 116 on Trusted nodes. Among these tasks, 109 are "hybrid", i.e., replicated both on Home and Trusted nodes. Figure 4 gives the cumulative number of replicas associated to each set.

Conclusion

We have explored a hybrid computing model composed of groups of home, standard cloud, and trusted cloud nodes, where each node has a given computing speed, monetary cost, and reliability reputation. We presented four protocols (Scrooge, Moderate, Cautions, and Adaptive) for scheduling tasks in such environments aiming at ensuring BoT applications' requirements in terms of bounded latency and reliabil- Performance results show that in both workloads, Scrooge (resp., Cautious) is the cheapest (most expensive) and has the smallest (resp., the highest) task deadline fail ratio. Yet, it takes more (resp., less) time to schedule tasks since, due to the low (resp., high) reputation of the home (resp., trusted) nodes, a single task must be submitted to more (resp., just one) nodes. In contrast, in high workload, these metrics increase, and Scrooge can no longer ensure all tasks' deadlines.

In both workloads, all tasks are successfully scheduled by Adaptive and meet their deadline since Adaptive distributes the load among the cheapest nodes, but assigns tasks to more reliable nodes whenever this task cannot be executed in Home nodes. Fur-ther, its response time is slightly faster than with Scrooge. Such good results confirm the advantage of the adaptive protocol.

As future work, we intend to propose and evaluate protocols for the Bounded Budget scheduling optimizing problem, described in section 4.2. We also plan to investigate the impact of different reputation management strategies on the protocols' performance.

Figure 1 :

 1 Figure 1: Hybrid cloud architecture

  each group G i and for each node p ∈ G i , the initial reputation of p, r p = R i . The compute power c p ∈ [C min i , . . . , C max i ] and the computing cost d p ∈ [D min i , . . . , D max i

  k for any other k, i.e., they are the most expensive nodes. However, C max i < C min k when k is standard cloud nodes, as trusted hardware is assumed to be slower than commodity one.

Algorithm 3

 3 Parameterized Single Group 1: // Schedule T whose deadline is ∆ on nodes from G with reliability ≥ ρ 2: function Schedule(G, T, ∆, ρ)

loop 6 : 7 : 9 :

 679 try (set, budget, latency) = FindSet(G, T, ∆, reqrel) catch no schedule found raise no schedule found 8: values = values ScheduleStep(set, T, latency) if |values| == 1 this value = ⊥ then 10: If all nodes replied the same value, return it 11:

14 :vAlgorithm 4 3 : 4 : 6 : 7 :

 1443467 = the most frequent value in values 15: ∆ = ∆latency 16: (rel, reqrel) = ProbCorrectValue(v, values, ρ) 17: if rel ≥ ρ then 18: return v The Specific Single Group Instances 1: function Scrooge(Tτ , ∆τ , ρ) 2: return Schedule(G H , Tτ , ∆τ , ρ) function Moderate(Tτ , ∆τ , ρ) 5: return Schedule(G C , Tτ , ∆τ , ρ) function Cautious(Tτ , ∆τ , ρ) 8:

  (i) Budget (financial cost): the total budget actually spent by the protocol; (ii) Completion time (response time): The overall completion time of the application; (iii) Computation time: The difference between the time a task Algorithm 5 Helper Function for Adaptive Algorithm 1: // Returns the fastest and cheapest sets of nodes from group G than can compute T with reliability ≥ ρ and latency ≤ ∆ 2: function Find2Sets(G, T, ∆, ρ) 3: cands = {pi ∈ G|T /ci ≤ ∆} Find qualifying nodes in G 4:

Figure 2 :

 2 Figure 2: Computation time of tasks with low load

Figure 3 :Figure 4 :

 34 Figure 3: Computation time of tasks with high load

Table 1 :

 1 Main symbols used in this paper

	p	A compute node	B(Γτ )	Budget of schedule Γτ
	p i , p j	Distinguishing between com-	∆τ	A latency threshold for τ
		pute nodes
	q	A probability	Φτ	A budget threshold for τ
	qp	Probability that p will re-turn an incorrect answer	G T	Group of fully trusted nodes
	rp	Reliability of p (1 -qp)	G C	Group of standard cluster nodes
	cp	Compute speed of node p	G H	Group of home nodes
	dp	Cost of node p	G i	A group of nodes of the same
				type
	τ	A compute task	σ	A run
	Tτ	Normalized compute time	Lσ	The latency of σ
		for τ
	ρτ	A reliability threshold for τ	Bσ	The latency of σ
	Γτ	A schedule for τ	Sσ	Set	of	nodes	producing
				replies in σ
	V (Γτ )	A reply values sequence for	t i	Time
		Γτ
	L(Γτ )	Latency of schedule Γτ	v i	Reply value

  Send T to all members of set and wait for replies 21: function ScheduleStep(set, T, latency) 22:

	1: // Add the corresponding budget and latency to a schedule
	2: function FleshOut(S, T )
	3:	budget =	p i ∈S	T d i c i
	4: 5:	T c i return (S, budget, latency) latency = max p i ∈S
	6:
	7: // Find a set that can compute T fast enough whose members
	satisfy the required reliability
	8: function FindSet(G, T, ∆, q)
	9:	cands = {pi ∈ G|T /ci ≤ ∆}	find all nodes that are fast
	enough
	10:	if cands == ∅ then
	11:	raise no schedule found
	12:	else
	13:	sets = {Si ⊆ cands| AllByz(Si, q)} All possible sets
	14:	finalists		=	{Si	∈
	sets| p i ∈S i	Tτ d i c i	is minimal in sets}	Filter for the
	cheapest
	15:	if finalists == ∅ then
	16:	raise no schedule found
	17:	else
	18:	return FleshOut(first(finalists, T ))	Return
	one of the cheapest
	19:
	20: //

foreach pi ∈ set send(pi, T )

  and ∆ EE = ∆ E -L EE C , respectively. Here, it is enough to identify the cheapest such sets of home nodes, denoted S F F

	H , S F E H , S EF H , H . Their corresponding latency and budget and S EE
	are denoted

  = {Si ∈ sets| min p i ∈S i ci is maximal in sets}

		is maximal in cheapests	break symmetry
		arbitrarily
	12:	else
	13:	cheapest = first(cheapests)
	14:	Identify the fastest set, break ties arbitrarily
	15:
	16:	if |fastests| > 1 then
	17:	fastest = Si| p i ∈S i	T d i c i	is minimal in fastests
		break symmetry arbitrarily
	18:

fastests else 19: fastest = first(fastests)

Table 2 :

 2 Hybrid cloud configuration

Table 3 :

 3 Workload configurations

	Workload	# tasks	mean	stddev	min	max
	low	5,000	179.9923	4.1528	162.307	194.5323
	high	20,000	180.0023	4.1274	162.307	196.209
	Algorithm	Time (sec)	Cost ($)	Sched. time (sec.)	fail ratio
	Cautious	476.98	11.588	0.041		79 %
	Moderate	477.32	11.979	0.555		0.38 %
	Scrooge	454.79	3.189	2.153		0 %
	Adaptive	443.77	2.884	5.683		0%

Table 4 :

 4 Time and cost for protocols with low load

Table 5 :

 5 Distribution of tasks on nodes with low load

	Algorithm	Time (sec)	Cost ($)	Sched. time (sec.)	fail ratio
	Cautious	476.98	11.588	0.115	94.75 %
	Moderate	485.35	16.594	1.476	66.23 %
	Scrooge	492.94	11.064	3.770	14.04 %
	Adaptive	471.52	17.816	13.391	0 %

Table 6 :

 6 Time and cost with high load

	Algorithm	# nodes	mean	stddev	min	max
	Cautious	50	21	0	21	21
	Moderate	500	30.358	11.997	10	65
	Scrooge	4999	14.413	8.4422	0	39
	Adaptive
	Trust set	45	2.32	1.53	0	7
	Cloud set	377	12.38	8.17	0	31
	Home set	4949	14.56	10.29	0	40

http://mathworks.com/


Mario Eltabach

Sophie Sieg-Zieba

Guanghan Song

Zhongyang Li

Pascal Bellemain

Nadine Martin

Vibration condition monitoring in a paper industrial plant

Keywords: Signal processing, Failure diagnosis, Cyclostationary, Ceptrum, Spectrum analysis

This paper presents a condition monitoring methodology applied to the suction roll and the Press roll of a paper machine. Experimental results obtained for the detection and identification of many defects that may occur to different mechanical components are presented. To this end, many fault indicators are calculated using a set of signal processing methods. We endeavor to propose robust fault indicators with respect to the variations of the operation parameters as the speed variation. Cyclostationary and cepstral approaches are used in order to make vibration source separation and to extract pertinent indicators closely related to the health of the paper machine. AStrion strategy, a stand-alone, data-driven and automatic tracking analyzer, is applied in order to characterize a sensor failure on the suction roll and a fault on the motor that drives the press roll. The trends of these parameters have shown the effectiveness of these methods to detect and identify the failure modes of the equipment thus allowing the reduction of the overall maintenance cost.

Introduction

Non-stationary signals can be defined as signals which satisfy a non-property, i.e. they do not satisfy the property of stationarity. It is not possible to define a general theory which treats non-stationary signals. The non-stationary behavior of each signal has to be individually evaluated. For instance time-frequency analysis can be considered a useful tool to analyze the amplitude and frequency non-stationarities within a signal. In the case that signals present periodic energy variations, which are synchronous with the machine cycle, a particular class of non-stationary signals can be defined as cyclostationary signals [1]. A signal is said cyclostationary if it contains cyclic transfer of energy. The amplitude modulated signal is an intuitive example of these signals. Cyclostationarity may be classified into several orders: 1st-order cyclostationarity: the cyclic energy flow is carried by deterministic components (sum of sinusoids plus stationary noise as for example the gear noise. 2nd-order cyclostationarity: the cyclic energy flow is carried by random components. 2st-order pure cyclostationarity: the signal does not contain 1st order cyclostationarity (time synchronous average of signal is zero) 2nd-order impure cyclostationarity: some of the cyclic energy of the signal comes from 1st order cyclostationarity (time synchronous average of signal is nonzero).

Signal Processing Techniques: Formulation and Properties

Cyclostationary indicators

The procedure for computing the four cyclostationary indicator is illustrated by Figure 1, [2]. The procedure of calculating of these indicators uses the angular vibration signal sampled with 'SmpRev' samples per revolution and two order frequencies in order to extract two sets of the four cyclostationary indicators related to the two last orders. First we can see that the angular vibration signal is averaged with respect to a reference frequency in order to extract the mean signal. By subtracting the mean from the original angular signal we obtain the residual one. The first cyclostationarity indicator is computed from the mean signal and the three other indicators from the residual one. Generally when computing the Cyclostationary Indicators we exclude all the nonsynchronous frequencies (with respect to the reference) and we exclude all the meshing ones. This will help to quantify cyclostationarity related to mechanical defects that appear respectively in the mean signal, in the power2, power3 and power4 of the residual signal.

Figure 1. Computation of the four cyclostationary indicators

Cepstral prewhitening

This method has the ability to separate the deterministic/random parts of a vibration signals. It uses the cepstrum computation [3]. It is well adapted to rolling element bearing fault detection and is crucial in vibration gear and bearing source separation.

The method is illustrated by Figure 2.

Figure 2. Schematic diagram of the Cepstral prewhitening

Astrion: an automatic spectrum analyzer

Due to the periodic nature of the vibration signals of rotating machines, spectrum-based analysis is a common approach in mechanical fault diagnosis. AStrion is a spectrum analyser which combines 5 different spectrum estimators to optimize the resolution and to reduce the variance. The analysis process is totally automatic and modulized in the following order: AStrion-A (optional): angular resampling, AStrion-D: data validation, AStrion-I: peak identification, AStrion-K (optional): kinematic Association, AStrion-H: harmonic and sideband identification, AStrion-M: sideband demodulation, AStrion-T: feature trajectory tracking, AStrion-S: surveillance. A more detailed description of the architecture can be found in [4] [5].

There are many difficulties with the system-driven fault detection approach or by the manual spectral inspection. This type of method often requires a careful configuration to work correctly on each individual machine. The accuracy fault detection and tracking are also heavily depends on the configuration or the user. Therefore a correct conclusion requires the expert knowledge. It consists of another risk in application that the possible frequency band where the fault will appear has to be located before the fault is detectable.

AStrion as a data-driven approach is the answer to these challenges [6]. It works in a standalone and self-governed manner, the modules are configured by themselves, and no user-defined information is required to detect the fault, to track the evolution of the faults or to trigger the alarms. AStrion performs an exhaustive analysis of the entire spectrum, making it possible to detect and track the faults in an automatic and reliable way. Moreover, some types of faults can be detected simply at the phase of the data validation, without being processed by the following modules.

Application

Critical machines in paper industry

In the beginning of the project supreme, a visit to the paper industry has shown that the main maintenance activities are focused at the suction roll and the press P2 parts. In fact, these parts of the paper machine are equipped by DC motors and gears see Figure 3.

Figure 3 Critical machine in the paper industry: The suction roll

The time life maintenance on Condat industry

Hereafter the time life maintenance that occurs on the suction roll over the period of the project (2013-2015), see Figure 4.

Standard vibration analysis Results

The evolution of simple condition monitoring parameters is extracted from different vibration signals. Figure 5 show the evolution of one of the global velocity RMS value calculated from the axial direction of the vibration signal coming from motor accelerometer.

Figure 5 Evolution of standard condition monitoring indicator Vrms from axial direction vibration signal

We notice that this indicator has increased in august 2013 which mean that it was very sensitive to motor faults. Inspection confirms a broken elastic ring in a rolling element bearing of the motor.

Cylostationary analysis Results

Looking to the cyclostationary indicators (Figure 6), their evolution were quiet stable in the beginning of the project and increased drastically between 19 of May and 22 of June 2014 because of a sensor fault and in October 2014 since the gearbox was replaced! In order to isolate the fault that occurs in October 2014 that makes the cyclostationary indicators increases, we make deeper spectral analysis by comparing spectra before and after October 2014. Indeed this analysis reveals that a hunting frequency appears on the new gearbox at very low frequency (0.01Hz) reflecting localized tooth fault due, perhaps, to fault manufacturing, see Figure 7.

Cepstral Results

On the press P2 we were interested to detect felt wear. Figure 8 show the peak to peak condition monitoring indicator over the project period. In fact we remark that this indicator (Peak-peak indicator) extracted from the horizontal direction of the roll bearing vibration signal was sensitive to the felt wear: level increased before the felt replacement and decreased just after. Seven periods of wear felt were detected from July 2013 till August 2015. It seems that the vibration levels are more sensitive to a particular type of the roll felt.

Figure 8. Spectral analysis from the gearbox vibration signal

Spectral analysis show a modulation phenomenon at 0,57Hz around deterministic frequencies (38X roll speed=144Hz). In order to isolate the source of this fault we used the cepstral prewhitening. Figure 9 shows a comparison between envelopes spectra of vibration signal (raw and whitened) and for a healthy and faulty felt. From Figure 9B we notice that the amplitude of the characteristic frequency increases when felt wear appear. From Figure 9D we notice that fault characteristic frequency disappear from the whitened signal. This reveals clearly that fault source is deterministic and occurs periodically due to felt face fault.

Figure 9 Cepstral analysis: A) Comparison between envelope spectra of raw vibration signals, B) Zoom of envelope spectra for raw signals. C) Cepstral whitened envelope spectrum comparison, D) zoom of the whitened envelope spectra

AStrion Results

In this paragraph, two examples on the Condat paper factory, a partener of the SUPREME project, are shown to demonstrate the capability of AStrion in the automatic detection of real-world mechanical faults. The first example is a sensor fault while the second is a mechanical fault of a motor bearing.

Results on the detection of a cable disconnection of an accelerometer

During April 17 th and June 25 th 2014, a cabling problem had been identified at the accelerometer n.5 installed with a 45 degree angle at the gearbox of the suction roll. The sensor location in the overall mechanical configuration is shown as in Figure 10.

Sensor fault Without being alerted by a specialist, AStrion is able to autonomously detect the fault. Due to the cabling fault, the accelerometer did not contain the vibration-induced spectrum structure, the dominant spectral content was the instrumentation noise, and some high frequency resonance components, therefore some data validation features provided good indicators of the fault, as presented in Figure 11. In Figure 11, the signals are transformed to order domain using AStrion-A (angular resampling) and the features are computed using AStrion-D (data validation). Since the cable was detached, the accelerometer no longer measured the vibration of the gearbox, therefore the absence of the vibration components significantly suppress the signal power compared to the noise. The Signal-To-Noise (SNR) decreased dramatically compared to the signals under the normal operational condition.

Moreover, the observed signal can be considered as the composition of two types of spectral structure. The first is the vibration components, under normal operational condition they dwell on low frequency range and concentrate high power; the second is the high frequency resonance, which is normally overwhelmed by the vibration components. During the cabling fault, the vibration components were not captured, therefore, the dominant power of the signal will be the high frequency resonance. The significant increase of the dominant power frequency and the fundamental frequency clearly reveal this phenomenon.

Besides the data-validation, the following spectral analysis of the harmonic and sideband structure also provides reliable indicators of the fault, as Figure 12 shows. Normally, the harmonics and the sidebands are generated by the vibration of the mechanical parts. When the sensor was disconnected, these spectral structures vanished, the number of the harmonic families and the sidebands also significantly decreased. Moreover, in Figure 12, the number of harmonic series and the sidebands correspond only to those with kinematic associations. Since during the sensor fault, these components were inexistent, both numbers were therefore close to zero.

Results on the detection of a bearing fault in a motor

It has been reported by a maintenance technician at the end of October 2014 that there had been a failure of the motor in the Suction roll. But the faulty part of the motor had not been identified. However, AStrion carried out continuous surveillance and was capable to automatically detect the fault from the accelerometer signal. The location of the motor and the accelerometer under study are shown in Figure 13. Since the rotational speed of the motor is time-varying, especially over different days, the spectral content of the signal also varied in frequency. It consists of the major difficulty of the tracking of the spectral components by the frequency, as shown in Figure 14. Figure 14 shows the difference in the frequency of the same kinematic component. The frequency shift is proportional to the difference of the rotational speed. After the angular resampling, the signal is synchronized to the angular rotational speed. The frequency spectrum can be transformed to an order spectrum on which the difference of the rotational speed is cancelled, as shown in Figure 15. and more robust. Over the order spectrum, AStrion-H, the harmonic and sideband identification module, identified a significant increase of the energy of the harmonic family B7.FTF (Fundamental Train Frequency of the bearing 7) of the signal, shown in Figure 16. Using Astrion, it is not only possible to detect the fault, but also able to deduce the faulty part before the teardown and the inspection of the motor.

Conclusions

Significant increase = indicator sensitive to default on B7.FTF

Introduction

Non-stationary signals can be defined as signals which satisfy a non-property, i.e. they do not satisfy the property of stationarity. It is not possible to define a general theory which treats non-stationary signals. The non-stationary behavior of each signal has to be individually evaluated. For instance time-frequency analysis can be considered a useful tool to analyze the amplitude and frequency non-stationarities within a signal. In the case that signals present periodic energy variations, which are synchronous with the machine cycle, a particular class of non-stationary signals can be defined as cyclostationary signals [1].

A signal is said cyclostationary if it contains cyclic transfer of energy. The amplitude modulated signal is an intuitive example of these signals. Cyclostationarity may be classified into several orders: 1st-order cyclostationarity: the cyclic energy flow is carried by deterministic components (sum of sinusoids plus stationary noise as for example the gear noise. 2nd-order cyclostationarity: the cyclic energy flow is carried by random components.

2 2st-order pure cyclostationarity: the signal does not contain 1st order cyclostationarity (time synchronous average of signal is zero) 2nd-order impure cyclostationarity: some of the cyclic energy of the signal comes from 1st order cyclostationarity (time synchronous average of signal is nonzero).

Signal Processing Techniques: Formulation and Properties

Cyclostationary indicators

The procedure for computing the four cyclostationary indicator is illustrated by Figure 1, [2]. The procedure of calculating of these indicators uses the angular vibration signal sampled with 'SmpRev' samples per revolution and two order frequencies in order to extract two sets of the four cyclostationary indicators related to the two last orders. First we can see that the angular vibration signal is averaged with respect to a reference frequency in order to extract the mean signal. By subtracting the mean from the original angular signal we obtain the residual one. The first cyclostationarity indicator is computed from the mean signal and the three other indicators from the residual one. Generally when computing the Cyclostationary Indicators we exclude all the nonsynchronous frequencies (with respect to the reference) and we exclude all the meshing ones. This will help to quantify cyclostationarity related to mechanical defects that appear respectively in the mean signal, in the power2, power3 and power4 of the residual signal. The method is illustrated by Figure 2. There are many difficulties with the system-driven fault detection approach or by the manual spectral inspection. This type of method often requires a careful configuration to work correctly on each individual machine. The accuracy fault detection and tracking are also heavily depends on the configuration or the user. Therefore a correct conclusion requires the expert knowledge. It consists of another risk in application that the possible frequency band where the fault will appear has to be located before the fault is detectable.

AStrion as a data-driven approach is the answer to these challenges [6]. It works in a standalone and self-governed manner, the modules are configured by themselves, and no user-defined information is required to detect the fault, to track the evolution of the faults or to trigger the alarms. AStrion performs an exhaustive analysis of the entire spectrum, making it possible to detect and track the faults in an automatic and reliable 4 way. Moreover, some types of faults can be detected simply at the phase of the data validation, without being processed by the following modules.

Application

Critical machines in paper industry

In the beginning of the project supreme, a visit to the paper industry has shown that the main maintenance activities are focused at the suction roll and the press P2 parts. In fact, these parts of the paper machine are equipped by DC motors and gears see Figure 3.

Figure 3 Critical machine in the paper industry:

The suction roll

The time life maintenance on Condat industry

Hereafter the time life maintenance that occurs on the suction roll over the period of the project (2013-2015), see Figure 4.

Figure 4 The time life maintenance over the project for the suction roll

We can see clearly that:

--The motor of the Suction Roll 'SR' is replaced on September 2013 (bearing fault) due to excessive vibrations.

--Cardan looseness fixed on November 2013.

--Integrated Gearbox replaced October 2014 due high axial vibration.

Standard vibration analysis Results

The evolution of simple condition monitoring parameters is extracted from different vibration signals. Figure 5 show the evolution of one of the global velocity RMS value calculated from the axial direction of the vibration signal coming from motor accelerometer. We notice that this indicator has increased in august 2013 which mean that it was very sensitive to motor faults. Inspection confirms a broken elastic ring in a rolling element bearing of the motor.

Cylostationary analysis Results

Looking to the cyclostationary indicators (Figure 6), their evolution were quiet stable in the beginning of the project and increased drastically between 19 of May and 22 of June 2014 because of a sensor fault and in October 2014 since the gearbox was replaced! In order to isolate the fault that occurs in October 2014 that makes the cyclostationary indicators increases, we make deeper spectral analysis by comparing spectra before and after October 2014. Indeed this analysis reveals that a hunting frequency appears on the new gearbox at very low frequency (0.01Hz) reflecting localized tooth fault due, perhaps, to fault manufacturing, see Figure 7.

Cepstral Results

On the press P2 we were interested to detect felt wear. Figure 8 show the peak to peak condition monitoring indicator over the project period. In fact we remark that this indicator (Peak-peak indicator) extracted from the horizontal direction of the roll bearing vibration signal was sensitive to the felt wear: level increased before the felt replacement and decreased just after. Seven periods of wear felt were detected from July 2013 till August 2015. It seems that the vibration levels are more sensitive to a particular type of the roll felt.

Figure 8. Spectral analysis from the gearbox vibration signal

Spectral analysis show a modulation phenomenon at 0,57Hz around deterministic frequencies (38X roll speed=144Hz). In order to isolate the source of this fault we used the cepstral prewhitening. Figure 9 shows a comparison between envelopes spectra of vibration signal (raw and whitened) and for a healthy and faulty felt. From Figure 9B we notice that the amplitude of the characteristic frequency increases when felt wear appear. From Figure 9D we notice that fault characteristic frequency disappear from the whitened signal. This reveals clearly that fault source is deterministic and occurs periodically due to felt face fault.

Results on the detection of a cable disconnection of an accelerometer

During April 17 th and June 25 th 2014, a cabling problem had been identified at the accelerometer n.5 installed with a 45 degree angle at the gearbox of the suction roll. The sensor location in the overall mechanical configuration is shown as in Figure 10. 9

Sensor fault Without being alerted by a specialist, AStrion is able to autonomously detect the fault. Due to the cabling fault, the accelerometer did not contain the vibration-induced spectrum structure, the dominant spectral content was the instrumentation noise, and some high frequency resonance components, therefore some data validation features provided good indicators of the fault, as presented in Figure 11. In Figure 11, the signals are transformed to order domain using AStrion-A (angular resampling) and the features are computed using AStrion-D (data validation). Since the cable was detached, the accelerometer no longer measured the vibration of the gearbox, therefore the absence of the vibration components significantly suppress the signal power compared to the noise. The Signal-To-Noise (SNR) decreased dramatically compared to the signals under the normal operational condition.

Moreover, the observed signal can be considered as the composition of two types of spectral structure. The first is the vibration components, under normal operational condition they dwell on low frequency range and concentrate high power; the second is the high frequency resonance, which is normally overwhelmed by the vibration components. During the cabling fault, the vibration components were not captured, therefore, the dominant power of the signal will be the high frequency resonance. The significant increase of the dominant power frequency and the fundamental frequency clearly reveal this phenomenon.

Besides the data-validation, the following spectral analysis of the harmonic and sideband structure also provides reliable indicators of the fault, as Figure 12 shows. Normally, the harmonics and the sidebands are generated by the vibration of the mechanical parts. When the sensor was disconnected, these spectral structures vanished, the number of the harmonic families and the sidebands also significantly decreased. Moreover, in Figure 12, the number of harmonic series and the sidebands correspond only to those with kinematic associations. Since during the sensor fault, these components were inexistent, both numbers were therefore close to zero.

Results on the detection of a bearing fault in a motor

It has been reported by a maintenance technician at the end of October 2014 that there had been a failure of the motor in the Suction roll. But the faulty part of the motor had not been identified. However, AStrion carried out continuous surveillance and was capable to automatically detect the fault from the accelerometer signal. The location of the motor and the accelerometer under study are shown in Figure 13. Since the rotational speed of the motor is time-varying, especially over different days, the spectral content of the signal also varied in frequency. It consists of the major difficulty of the tracking of the spectral components by the frequency, as shown in Figure 14. Figure 14 shows the difference in the frequency of the same kinematic component. The frequency shift is proportional to the difference of the rotational speed. After the angular resampling, the signal is synchronized to the angular rotational speed. The frequency spectrum can be transformed to an order spectrum on which the difference of the rotational speed is cancelled, as shown in Figure 15. 12 and more robust. Over the order spectrum, AStrion-H, the harmonic and sideband identification module, identified a significant increase of the energy of the harmonic family B7.FTF (Fundamental Train Frequency of the bearing 7) of the signal, shown in Figure 16. Using Astrion, it is not only possible to detect the fault, but also able to deduce the faulty part before the teardown and the inspection of the motor.

Conclusions

Significant increase = indicator sensitive to default on B7.FTF

Figure 4

 4 Figure 4 The time life maintenance over the project for the suction roll

Figure 6 Figure 7 .

 67 Figure 6 Evolution of one of cyclostationary indicator coming from the gearbox vibration signal

Figure 10 .

 10 Figure 10. The location of the faulty accelerometer in the suction roll, as marked by the red arrow.

Figure 11 .

 11 Figure 11. AStrion-D (data validation) result of the faulty accelerometer of Figure 10 from March 15 th , 2014 to June 30 th , 2014. Above: The SNR; Middle: The dominant power periodicity; Bottom: The fundamental frequency.

  Figure 12. AStrion-H (harmonic and sideband identification) result of the faulty accelerometer of Figure 10.

Figure 13 .

 13 Figure 13. The location of the faulty motor and the accelerometer (marked by the red arrow) on which AStrion is applied.

Figure 14 .

 14 Figure 14. The spectrogram of the accelerometer in Figure 13 zoomed around the same kinematic component (2 nd harmonic of the shaft speed on the low speed gear) at May 27 th 2014 and May 28 th 2014.

Figure 15 .

 15 Figure 15. The order spectrogram of the signals under different rotational speed in Figure 13, calculated after being transformed to the order domain by AStrion-A.

Figure 16 .

 16 Figure 16. The energy of the harmonic family of B7.FTF of the signals of the accelerometer n.2 of Figure 10.

Figure 17 .

 17 Figure 17. Location of the bearing 7 in the faulty motor.

Figure 1 . Computation of the four cyclostationary indicators 2 . 2

 122 Figure 1. Computation of the four cyclostationary indicators

Figure 2 .

 2 Figure 2. Schematic diagram of the Cepstral prewhitening

Figure 5

 5 Figure 5 Evolution of standard condition monitoring indicator Vrms from axial direction vibration signal

Figure 6 Figure 7 .

 67 Figure 6 Evolution of one of cyclostationary indicator coming from the gearbox vibration signal

Figure 9

 9 Figure 9 Cepstral analysis: A) Comparison between envelope spectra of raw vibration signals, B) Zoom of envelope spectra for raw signals. C) Cepstral whitened envelope spectrum comparison, D) zoom of the whitened envelope spectra

Figure 10 .

 10 Figure 10. The location of the faulty accelerometer in the suction roll, as marked by the red arrow.

Figure 11 .

 11 Figure 11. AStrion-D (data validation) result of the faulty accelerometer of Figure 10 from March 15 th , 2014 to June 30 th , 2014. Above: The SNR; Middle: The dominant power periodicity; Bottom: The fundamental frequency.

  Figure 12. AStrion-H (harmonic and sideband identification) result of the faulty accelerometer of Figure 10.

Figure 13 .

 13 Figure 13. The location of the faulty motor and the accelerometer (marked by the red arrow) on which AStrion is applied.

Figure 14 .

 14 Figure 14. The spectrogram of the accelerometer in Figure 13 zoomed around the same kinematic component (2 nd harmonic of the shaft speed on the low speed gear) at May 27 th 2014 and May 28 th 2014.

Figure 15 .

 15 Figure 15. The order spectrogram of the signals under different rotational speed in Figure 13, calculated after being transformed to the order domain by AStrion-A.

Figure 16 .

 16 Figure 16. The energy of the harmonic family of B7.FTF of the signals of the accelerometer n.2 of Figure 10.

Figure 17 .

 17 Figure 17. Location of the bearing 7 in the faulty motor.

This work has been done within the SUPREME project, funded by the European Commission, under the FP7 program. In this paper we present condition monitoring methodology applied to the suction roll and the Press roll of a paper machine. Experimental results obtained for the detection and identification of many defects that may occur to different mechanical components are presented. The trends of multiple simple and advanced condition monitoring parameters have shown the effectiveness of indicators to detect and identify the failures that may occur to critical machines.

This work has been done within the SUPREME project, funded by the European Commission, under the FP7 program. In this paper we present condition monitoring methodology applied to the suction roll and the Press roll of a paper machine. Experimental results obtained for the detection and identification of many defects that may occur to different mechanical components are presented. The trends of multiple simple and advanced condition monitoring parameters have shown the effectiveness of indicators to detect and identify the failures that may occur to critical machines.

This work has been done within the SUPREME project, funded by the European Commission, under the FP7 program. This work has been done within the SUPREME project, funded by the European Commission, under the FP7 program.

Vibration condition monitoring in a paper industrial plant: Supreme project

Mario Eltabach, Sophie Sieg-Zieba CETIM Av. Félix Louat, 60304, Senlis, France +33 3 44 67 33 25 +33 3 44 67 36 94 firstname.lastname@cetim.fr Guanghan Song, ZhongYang Li, Pascal Bellemain, Nadine Martin, Univ. Grenoble Alpes, GIPSA-Lab, F-38000 Grenoble, France CNRS, GIPSA-Lab, F-38000 Grenoble, France firstname.lastname@gipsa-lab.grenoble-inp.fr

Abstract

This paper presents a condition monitoring methodology applied to the suction roll and the Press roll of a paper machine. Experimental results obtained for the detection and identification of many defects that may occur to different mechanical components are presented. To this end, many fault indicators are calculated using a set of signal processing methods. We endeavor to propose robust fault indicators with respect to the variations of the operation parameters as the speed variation. Cyclostationary and cepstral approaches are used in order to make vibration source separation and to extract pertinent indicators closely related to the health of the paper machine. AStrion strategy, a stand-alone, data-driven and automatic tracking analyzer, is applied in order to characterize a sensor failure on the suction roll and a fault on the motor that drives the press roll. The trends of these parameters have shown the effectiveness of these methods to detect and identify the failure modes of the equipment thus allowing the reduction of the overall maintenance cost. This work has been done within the SUPREME project, funded by the European Commission, under the FP7 program.