Yessin M Neggaz
email: myneggaz@laas.fr

Soufian Toufga
email: soufian.toufga@laas.fr

Temporal Property Testing in Dynamic Networks: Application to Software-Defined Vehicular Networks

Keywords: Dynamic networks, Software-Defined Vehicular Networks, SDN

With the recent advances in the area of wireless communication networks, a new kind of networks emerges where entities make contact over time with one another, which makes topology highly dynamic e.g UAV networks, wireless sensor networks, vehicular networks etc. A challenge in this context is to study dynamics patterns and temporal properties and decide if the evolution of the topology satisfies requirements for given protocol, algorithm, task etc. and adapt at different levels. In this paper we focus on testing temporal properties in dynamic networks, then we consider SDVN -Software-Defined vehicular networks as a case study where we propose the integration of a new component in SDVN architecture based on a framework that allows dynamic networks properties analysis and adaptation to a given dynamic context. We demonstrated how network control functions can take benefit from the provided information.

I INTRODUCTION

One of the major evolutions in the area of computer science, we note the emergence of dynamic networks. These networks consist of entities making contact over time with one another, which makes them different from static networks where the topology remains unchanged. Recently, the community has explored contexts where the dynamic is considered as a property of the network, rather then exception and several works have highlighted the importance of studying and defining mobility patterns and characterizing dynamic properties in a dynamic context. In a static context, the stability allows one to have all parameters to preview the execution on a given network. A major challenge in dynamic networks is difficulties to detect mobility patterns and decide whether the evolution of the topology satisfies requirements. From this point of view we distinguish two types of dynamic networks: Controlled dynamic networks where contacts and topological changes can be directed in a way such that they adapt to the execution of an algorithm; non-controlled networks where the evolution of the network topology is completely or partially independent from the execution and unpredictable without any analysis. The latter category represents a large part of the practical contexts, as vehicular networks, telephone networks, social networks etc. where the movements of communicating and computing units depend on the movements of the underlying mobile objects. The types of network dynamics are different, some of them are connected all the time [START_REF] Dell | Information dissemination in highly dynamic graphs[END_REF], others are not but give a temporal connectivity (connectivity over time) [START_REF] Jain | Routing in a delay tolerant network[END_REF], others are stable, periodic, etc. All of these contexts can be represented as temporal properties and dynamic graph classes [START_REF] Casteigts | Timevarying graphs and dynamic networks[END_REF]. In [START_REF] Casteigts | Characterizing topological assumptions of distributed algorithms in dynamic networks[END_REF] authors propose an analytical approach that aims to characterize how appropriate a given algorithm is to a given dynamic context and define based on this relevant temporal properties. Given a dynamic network, an interesting question to ask is what temporal property it has and how it evolves over time. Thus, being able to learn about the evolution of the network state is useful for determining which problem can be successfully solved. Furthermore, it can be useful to adapt at different levels or to control the network to satisfy a needed property. Different strategies were proposed in the literature for testing temporal properties in dynamic networks. In [START_REF] Casteigts | A generic framework for computing parameters of sequence-based dynamic graphs[END_REF] authors present a generic framework for computing maximum and minimum parameters, testing properties and show its application by solving some relevant problems. In this work we are interested in testing temporal properties and computing parameters in an emerging issue in the field of dynamic communication networks: SDVN -Software-Defined Vehicular Networks. We present an adaptation of the existing frameworks to a more general case and show its application by proposing a new component in the SDVN architecture allowing network control functions to learn about the network topology dynamics and adapt to its evolution.

The paper is organized as follows: In section II we present dynamic network model and some basic definitions on dynamic graphs. Section III discusses the characterization of temporal properties and their impact on algorithms and application suitability. In Section IV we present some existing strategies for testing properties and computing parameters, then a framework that we will apply in Section V to SDVN context where we highlight the benefit of our proposition.

II MODEL

In this section we present the dynamic networks model and some basic notions and concepts that will be used in this paper.

II-A Dynamic Graph Model

In a dynamic context, networks can be represented in many ways, it depends on the definition of the temporal domain in which the system evolves. Many models exist and are widely used in the literature, like Time-varying graphs [START_REF] Casteigts | Timevarying graphs and dynamic networks[END_REF], temporal networks [START_REF] Kempe | Connectivity and inference problems for temporal networks[END_REF] and link streams [START_REF] Viard | Computing maximal cliques in link streams[END_REF]. It is often suitable to represent the evolution of the network as a sequence of global graphs representing the general state of the network during a time interval. In what follows, we will use evolving graphs [START_REF] Ferreira | On models and algorithms for dynamic communication networks: The case for evolving graphs[END_REF] where the evolution of the graph is modelled by an indexed sequence of graphs {G i = (V, E i )}, each graph G i being associated to a time interval [t i , t i+1 ) during which it is available. Figure 1 shows an example. Formally: Definition 1 (Evolving Graph). Let G = (V, E) be a graph, an evolving graph G is represented by a triplet G = (G, S G , S T ) where S G is an indexed sequence {G i = (V, E i )} of G subgraphs and S T ⊆ T ⊆ N or R is the associated sequence of dates t 1 , t 2 , ... where ∀e ∈ E i , e is present in the time interval [t i , t i+1 ) (only the graph G i is present in this interval). In a more general case edges could be directed to represent non-symmetrical links. The state of the links and nodes could be presented by labels on the edges e.g QoS, capacity, load etc.

II-B Temporal Properties

In this work, we are interested in temporal and topological properties, in other words, characterizing and testing properties on the evolution of the topology but not only on the state of the network at a time t. For instance, an important property in dynamic networks is the connectivity between nodes. At no time, in Figure 1 in the graph G a is connected to e (in a classical sense). But by allowing the combination of edges from different graphs, e can be reached from a by means of a temporal path, e.g: ((a, c) ∈ E 1 , (c, e) ∈ E 4 ). This temporal aspect of a path gives the notion of journey (temporal path).

Other properties can be defined, for example on the stability of a (same) path e.g ((b, c), (c, d)) in {G i : 1 ≥ i ≥ 2}, the existence of a path between tow nodes during a given duration, the recurrence of a link (periodic, time-bounded, recurrent ...), properties on a set of links, on a part of the network etc. A natural question is "what gives sense to a given property and makes it interesting to consider?". An efficient approach is to analyze algorithms, protocols, tasks ... and to look at the assumptions made on the dynamic graph.

III CHARACTERIZING TEMPORAL PROPERTIES

In [START_REF] Casteigts | Characterizing topological assumptions of distributed algorithms in dynamic networks[END_REF] authors propose a framework that allows to examine what impact a property has on the execution of an algorithm and that aims to characterize how appropriate a given algorithm is to a given dynamic context. The workflow is presented in Figure 2. Algorithms are analyzed to characterize conditions that define temporal properties.

Their general methodology consists in considering a problem, then characterizing the conditions for the success of its algorithm execution in terms of network dynamics. They model this in two predicates: objective and condition. The objective O A defines the success of the execution of an algorithm A. For example, for a propagation algorithm A, which consists in transmitting an information I from a node u to all the other nodes of the graph, the objective O A is ∀v ∈ V, v has the information I. Property: There exists a journey from a node u to all other nodes of the graph, is proved to be a necessary condition for A.

A hierarchy of general classes of dynamic graphs, corresponding to temporal properties, was defined based on this process [START_REF] Casteigts | Characterizing topological assumptions of distributed algorithms in dynamic networks[END_REF] e.g Temporal Connectivity (for all pairs of nodes u, v ∈ V , there exist a journey), Constant Connectivity One could be interested in properties on a specific set of nodes in the graph or a specific path, link etc. Specific properties can be defined based on what exists or by considering new network problems and algorithms. This method can be generalized (Figure 3) to allow the characterization of specific temporal and topological requirements based on a practical evaluation of protocols, tasks, algorithms beside the existing analytical approach. In an online setting, where only a recent history of the network state is considered, it is more interesting to study the temporal property evolution instead of defining a property on the whole graph i.e temporal properties on windows of the network. For example, it gives more information to compute the Temporal diameter: the smallest duration in which every node can join all other nodes using a journey at any instant t, than merely test whether the dynamic network is temporally connected. This information about the evolution of the property is called Temporal parameter: Definition 2. p i is a parameter of G with respect to a given property P , at time i, iff {G i , G i+1 , ..., G i+pi-1 } verifies the temporal property P , that is, starting from time i, the property P is true for a duration p i .

(∀G i ∈ G, G i is connected), T-interval
Let's take for example Temporal connectivity, if every node can reach all the other nodes, using a journey, at time i in a duration of 5 but not 4 then p i > 4 is a parameter and 4 defines the temporal diameter of the graph at time i i.e minimization of the parameter p i . Different temporal parameters can be defined based on existing properties, and related information can be extracted. For instance, the smallest duration in which a set of links/paths reappear at least once, the largest duration in which a path is stable etc. Testing temporal properties and computing parameters allows one to collect information about the network based on which could decide which task, protocol or algorithm could be used and when, or adapt its behavior.

IV TESTING TEMPORAL PROPERTIES AND COMPUTING PARAMETERS

Dynamic graphs instances can be obtained from network traces generated from the collection of real-world networks or network topology estimation. Then testing temporal properties and computing parameters can give an indication about the suitability of a given algorithm in a mobility context. This allows one to adapt the execution of the algorithm, the behavior of a protocol or an architecture at a given level to the network dynamics, and conversely control the network topology evolution to guarantee needed properties. The workflow presented in Figure 4 shows a general representation for an automatic testing framework that produces information about the dynamics of the network with respect to a given temporal property. A key issue is that of understanding how far such a framework could be automated. Several works contributed to the automation of the core operations of Property testing and Parameter computation, by proposing strategies for the classification of dynamic graphs for specific classes like Temporal Connectivity [START_REF] Barjon | Testing temporal connectivity in sparse dynamic graphs[END_REF] and T-interval connectivity [START_REF] Casteigts | Efficiently testing t-interval connectivity in dynamic graphs[END_REF].

In [START_REF] Casteigts | A generic framework for computing parameters of sequence-based dynamic graphs[END_REF] authors present a generic framework for computing maximum and minimum parameters and testing properties in dynamic networks and show its application by solving minimization and maximization problems like computing the temporal diameter, the round trip temporal diameter of a given dynamic graph, the reappearance-bound of its edges and computing T for which a given G is T -interval connected.

The proposed algorithm computes a sequence of highlevel structures (graphs) {G (i,j) } with j ≥ i. Each structure G (i,j) corresponds to a sub-sequence {G i , G i + 1, ..., G j } of the original dynamic graph and represents information about the considered temporal property e.g transitive closures of journeys {G (1,3) , G (2,4) , ..., G (6,8) } in Figure 6. From this sequence, by testing the presence of an edge (u, v) in G (i,i+2) , one can directly test if a node v can be reached from a node u using a journey, in a duration of 3 starting at time i. This highlevel sequence is computed using a composition operation defined by the user for the considered property or parameter e.g transitive closure concatenation as operation to compute the sequence of transitive closure of journeys. So far, the generic framework is designed to solve minimization and maximization problems (i.e finding the smallest/largest duration for which a given temporal property is verified at any time). The framework can be directly extended to compute the needed high-level structures and extract the desired information about the network based on what information the user needs at a given time or depending on external events. Figure 5 shows a general presentation of this high-level computation framework. Depending on a specific temporal property, a composition operation is used to compute the high-level sequence from the dynamic graph given as input (see [START_REF] Casteigts | A generic framework for computing parameters of sequence-based dynamic graphs[END_REF] for more details about the composition operation). Then temporal parameters (w.r.t the considered property) can be computed directly from the resulting high-level structures. This hides the complexity of the network dynamics and allows one to focus only on the extraction of interesting information about the evolution of the temporal properties of the network and then adapt to changes at this level. For instance, if the application tolerates a maximum latency l using a store and forward adhoc communication, then the system/protocol must adapt if the temporal diameter (the considered temporal parameter in this case) exceeds l, for example, by using an other communication mode (e.g infrastructure). If the system can be completely or partially controlled, then the topology can be directed in a way to guaranty the needed requirement. More complex computation can be done using the framework to extract more precise information on the network. V CASE STUDY Intelligent Transport System (ITS) brings the idea of providing the vehicles and the transport infrastructure with communication capabilities, in an effort to improve their safety, reliability, efficiency and quality [START_REF]Its definition[END_REF]. To that end, a large variety of companies including car makers along with automotive industry suppliers, telecom operators, and research bodies are gathered to propose different ITS services, such as, Cooperative Collision Avoidance, Automated Overtake, Traffic information and recommended itinerary, and Vulnerable Road User Discovery [START_REF]Technical report, 5G-PPP, The 5G Infrastructure Public Private Partnership[END_REF]. Therefore, the next generation of vehicles will be equipped with one or more interfaces enabling it to communicate with the surrounding vehicles, as well as, the infrastructure, and organized in networks, known as Vehicular networks. In the last years, vehicular networks are attracting more attention, recent research activities [START_REF] Ge | 5g software defined vehicular networks[END_REF], [START_REF] Toufga | An SDN hybrid architecture for vehicular networks: Application to Intelligent Transport System[END_REF], [START_REF] Ku | Towards software-defined vanet: Architecture and services[END_REF] are investigating the possibility of applying Software Defined Network (SDN) paradigm to vehicular networks to bring the flexibility and programmability to such dynamic network, with the aim of efficiently supporting the emerging ITS services. The SDN paradigm advocates the idea of taking control plane functions out of network forwarding devices and relocating them on remote external computing machines called SDN controllers. By doing so, the network intelligence becomes logically centralized and the network nodes only forward packets according to the rules installed by the SDN controller [START_REF]Technical report, 5G-PPP, The 5G Infrastructure Public Private Partnership[END_REF].

V-A SDVN -software-defined Vehicular networks

Applying SDN to vehicular networks consists on the separation of data plane and control plane. The main objective of data plane is the forwarding of data , while the control decisions are taken by the control plane, for example, to decide from which interface each packet will be forwarded. As shown on Figure 7 and described on [START_REF] He | Sdvn: enabling rapid network innovation for heterogeneous vehicular communication[END_REF], the data plane is composed of various Forwarding Elements as Base Stations (3G/4G), Road Side Units (RSU), Vehicles, all under the control of SDN controller. Each node sends periodically to the SDN controller information about its status (connectivity, position, speed, direction . . . ) through the Southbound interface. These information are used in the control plan to build a global view of the network, which is exposed via the Northbound interface to the network control applications (routing, mobility management, ...) in order to generate the control decisions to be implemented by the data plane, In addition, the Business Applications (ITS services) can specify their requirements and the expected behavior of the network through the northbound interface.

The network control functions constitute the intelligence of the network, these functions benefit from a personalized and simplified representation of the underlying network, this representation is constructed and maintained by the topology discovery service using the information sent by the forwarding elements. for example a routing function needs the graph of the topology of the network and the capacities of the various links in order to compute the routing path. However, with the high mobility of vehicles, keeping this view up to date represents a challenging task, the authors in [START_REF] He | Sdvn: enabling rapid network innovation for heterogeneous vehicular communication[END_REF] propose the idea of using a topology prediction service based on the potential trajectory of a vehicle in order to expose an estimated view of the network.

V-B Temporal property testing in SDVN

In SDVN architecture, the SDN controller, which represents the control plane, constitutes the intelligence of the network, it executes various network control functions (known as SDN applications) allowing the control and management of the network in a centralized way. These network functions benefit from the information provided by the basic services of SDN, such as topology discovery service. In order to enrich the information provided to the network control functions, we propose to study the evolution of the graph topology using the framework presented in the previous sections. Multiple temporal properties and parameters can be computed using a historical graph sequence (provided by the topology discovery service), or an estimated one (provided by the topology prediction service).

Figure 8 shows the integration of the presented framework in the SDVN architecture. The defined component (Temporal property testing) operates in the control plane in interaction with the topology discovery and prediction services, which provide the needed information about the network topology evolution as a dynamic graph. Outputs are computed based on the desired property specified by the SDN application and then used directly to (1) make decision about the control policies (e.g switch from an adhoc strategy to a centralized one if the required property is not verified), (2) adapt the network control functions behavior to the network, and (3) control the network to satisfy the desired requirements.

One of the most important network control functions in such architecture is Routing. The main objective of this service consists in computing optimal routes to send information from a source node to one or many destination nodes. In general, the routing protocols use several metrics like hop numbers (shortest path), link quality (reliable, fastest path) etc. In a dynamic environment, communication link disconnections occur frequently. So, routing based only on classical metrics may not be efficient in such a context. Testing temporal properties and computing parameters in dynamic networks could give relevant information which can be considered in the optimal path computation. An important temporal parameter is the stability of paths over time [START_REF] Venkatramana | Scgrp: Sdn-enabled connectivity-aware geographical routing protocol of vanets for urban environment[END_REF]. By giving the right operation, the routing function can use the output of the introduced component (Temporal property testing) to test the stability of paths in a horizon of h (defined by the application) from the sequence given by the Topology prediction service i.e starting from a time t test if a path is shared by a sequence {G i , G i+1 , ..., G i+d-1 } with d ≤ h.

To compute this parameter one should be able to directly test the stability of a path from the corresponding highlevel structure. An option could be to compute G (i,i+h-1) containing all edges that appear in G i labeled with their stability: every edge e in G (i,i+h-1) is labeled with the largest k ≤ h such that e ∈ ∩{G i , G i+1 , ..., G i+k-1 }. This can be computed thanks to the Union composition operation that computes ∪{G i , G i+1 , ..., G i+h-1 } with all appearance dates of edges and then keeps on G (i,i+h-1) only edges belonging to G i with labels corresponding to first_disappearance_date-i (see [START_REF] Casteigts | A generic framework for computing parameters of sequence-based dynamic graphs[END_REF] for more details about composition operations in this framework). To test if a path is stable in the network for a duration d starting from a time i, it is sufficient to test the existence of the path in G (i,i+h-1) with labels ≥ d on all the edges. This can be done in a linear time in the number of edges. Figure 9 shows an example.

To have more information about the presence of links, all appearance dates could be kept on edges in {G (i,i+h-1) }. So, one can determine when missing links are needed to be established to ensure the stability of a specific path, then, request the Topology control function with this precise information in order to satisfy the general property (path stability) when possible. In this case (SDVN), thanks to the programmability offered by SDN, the topology and links can be controlled by adjusting the range of communication devices for example.

Other important SDN applications could benefit from the

G 1 G 2 G 3 G 4 G (1,3) 1 3 2 1 1 G (2,4) 1 3 1 3
Fig. 9. Example of high-level structure for testing path stability with h = 3.

Temporal property testing module in the same manner. Furthermore, an other utilization of the computed output could be the analysis of the computed parameters flow and its variation using analytical tools for the extraction of correlation relations with other parameters or other information on the network (e.g. using Pearson's correlation coefficient [START_REF] Cooper | Correlation and function fitting[END_REF]), in order to find relevant information and meaning. We can note that it is easier to predict high-level structures or parameter values based on the output computed before a given instant than predict the topology of the dynamic network itself. This could lead to predictive strategies using for example Long Short-Term Memory (LSTM) Based Recurrent Neural Network Architectures [START_REF] Hochreiter | Long short-term memory[END_REF] for sequence prediction.

VI CONCLUSION

In this paper, we presented an application of a general framework for testing temporal properties in Software-defined Vehicular Networks. We integrated a new component in the existing architecture allowing the network control functions to take benefit from the computed network evolution information, in order to efficiently control the network in such a highly dynamic context.

As a perspective, one direction could be to define new requirements and properties for other fundamental network control functions. Also, it could be interesting to extend the application of the framework to consider more properties. Finally, this work could profit from an experimental evaluation which would show its applicability.

Fig. 1 .

 1 Fig. 1. Example representation of a dynamic network as an evolving graph.

Fig. 2 .

 2 Fig. 2. Characterizing temporal properties [4].

  Connectivity (every sequence of length T in the dynamic graph G shares a common connected spanning subgraph), Time-bounded Reappearance of Edges, Periodic Reappearance of Edges etc. The defined classes are generic and define properties on the entire graph.

Fig. 3 .

 3 Fig. 3. Characterizing requirements.

Fig. 4 .

 4 Fig. 4. Automatic classification of dynamic networks and parameter computation.

Fig. 5 .

 5 Fig. 5. Simplified presentation of the framework.

Fig. 6 .

 6 Fig. 6. Example of high-level structures (transitive closure of journeys) to test temporal connectivity.

Fig. 7 .

 7 Fig. 7. Software-Defined Vehicular Networks Architecture.

Fig. 8 .

 8 Fig. 8. Temporal property testing in SDVN.

  TableIexposes some network control functions and related properties. Besides Path stability, Routing control function can take advantage from other properties like Temporal connectivity (presented in section II-B) and Link recurrence (periodic and time-bounded links reappearance), which enable different routing strategies (e.g. store-and-forward, foremost broadcast etc.). It also can be interesting for Load balancing control function to use information about the connectivity between a set of vehicles on one hand, and their connectivity with the infrastructure (e.g. Fog data centers), on the other hand: For instance, depending on the nature of transmitted data, a vehicle can use a distant data center (instead of directly connected one) using a stable path (e.g. for a continuous traffic, Instant connectivity otherwise) or a Journey (Temporal connectivity) if transmitted data tolerate a certain latency.

	Temporal Properties	Routing	Network Control Function Mobility Mgmt
			√
	Link recurrence	√	√
		TABLE I
	EXAMPLE OF TEMPORAL PROPERTIES FOR NETWORK CONTROL
		FUNCTIONS.


J W Vásquez
email: jwvasque@laas.fr

L Travé-Massuyès

A Subias
email: subias@laas.fr

F Jimenez
email: fjimenez@uniandes.edu.co

Enhanced chronicle learning for process supervision

Keywords: Alarm management, Diagnosis, Chronicles, Pattern recognition

Process alarm management can be approached as a pattern recognition problem in which temporal patterns are used to characterize different typical situations, particularly at startup and shutdown stages. This paper focuses on learning the temporal patterns, in the form of chronicles, by extending the previously proposed Heuristic Chronicle Discovery Algorithm Modified HCDAM . The proposed extension incorporates knowledge, in particular in the form of so called temporal runs, to focus the learning process and produce less conservative chronicles. The resulting Chronicle Based Alarm Management (CBAM) approach is hence based on a diagnosis process which permits situation recognition and provides the operators with relevant information about the failures inducing alarms flows in the startup and shutdown stages. The event sequences that represent a process situation are generated by simulation and including temporal runs, the chronicles are extracted using the extended version of HCDAM . Finally, the conclusion and future work are presented.

INTRODUCTION

In industrial environments, it is common for the plant operators to perform their duties by silencing process alarms. This is so because these alarms are too numerous and become noise rather than helping to detect and diagnose abnormal situations. Currently, it is very easy to set alarms on modern electronic control systems, and operators are inundated with "alarms" that do not help them to perform their tasks but, on the contrary, hinder them [START_REF] Stanley | Generic fault propagation modeling approach to on-line diagnosis and event correlation[END_REF]). However, the plant alarms should be administered according to: a philosophy that includes the purpose of the alarm system; procedures associated with the alarm system and other plant procedures; methods for prioritization; alarm classes; roles and operator responsibilities with respect to alarms; principles of the alarms; documentation required for each alarm; training; rates of key system performance; change management, and preservation of history of alarms (ISA 18.2).

The nature of alarms and other procedure actions makes that many of the aspects of industrial processes can be captured by discrete events. The supervision problem thus must fit the formal recognition of behaviors in the context of Complex Event Processing (CEP). This corresponds to developing reliable tools that support the analysis of event streams to recognize activities that can generate normal or abnormal situations in complex flows. The dynamics of a process can be represented by an approach that depicts the process behavior using the events that occurs. Then, identifying the transition from normal operation to abnormal operation corresponds to detect symptoms. For do this, the systems must be monitored and the diagnostic algorithms are therefore based on observations that the system provides. It must have a sufficient set of strategically placed sensors, providing useful indicators. This information is then used to reconstruct the state of the system and this observations coupled with a diagnostic algorithm allow to introduce the concept of diagnosability. A system is diagnosable with a diagnostic algorithm if it detects with certainty the occurrence of faults in the system, and is able to discriminate them in finite time. The formal definition of diagnosability may be different if one is interested in continuous systems [START_REF] Basseville | On fault detectability and isolability[END_REF]) or discrete events [START_REF] Pencolé | Diagnosability analysis of distributed discrete event systems[END_REF]). Diagnosability provides an efficient criterion to assess the relevance of the observations in each situation.

In this context, chronicles [START_REF] Dousson | Alarm driven supervision for telecommunication network: On-line chronicle recognition[END_REF], [START_REF] Ghallab | On chronicles : Representation, online recognition and learning[END_REF]) have been applied in many diagnosis applications but one of the biggest difficulties is to obtain automatically a base of chronicles that represents each situation. To obtain relevant chronicles from a set of event sequences representing a given situation, it is often necessary incorporate expert knowledge. This paper enhances the results of the chronicle learning algorithm proposed in [START_REF] Subias | Learning chronicles signing multiple scenario instances[END_REF]) by incorporating expert knowledge in the form of temporal runs, as well as additional information that allows us to limit the conservatism of chronicles.

The paper is divided into 5 sections. After the introduction, Section 2 presents the chronicles representation with its formal concepts. Section 3 presents the learning approach. An extension of the HCDAM is described with an example. In the section 4, a case study related with an illustrative application in the petrochemical sector is used to apply the tree steps of the CBAM. Finally, in Section 5 the conclusion and future work are presented.

CHRONICLE REPRESENTATION

A chronicle is a set of events linked by temporal constraints and the occurrence of which is subject to a certain context. A chronicle is expressed as a constraint graph in which events are represented by nodes and time constraints are the labels of the arcs that connect the nodes. Time is represented as a linearly ordered discrete set of instants, whose granularity is fine enough compared to the dynamics of the environment and the means of observation. The "Chronicle Recognition System" named CRS was introduced in [START_REF] Dousson | Alarm driven supervision for telecommunication network: On-line chronicle recognition[END_REF] and extended in [START_REF] Dousson | Extending and unifying chronicle representation with event counters[END_REF]. A system of chronicles is composed of three parts:

(1) A set of predicates (2) A set of temporal constraints concerning these predicates (3) A set of actions to apply when chronicle is recognized (optional).

The latter part is used to react following the recognition of a chronicle; for example, the reaction may be a maintenance operation. This part does not concern the subject of training and therefore is not addressed in the following.

To recognize chronicles, CRS must detect all subsets of occurrences of events in the input stream. These subsets correspond to all the sets of patterns of the chronicle taking into account the various constraints that compose it. To achieve this result, CRS creates partial instances. A partial instance corresponds to a partial subset of the chronicle event pattern. It is only when this subset is complete that the chronicle is recognized.

Concepts and formalization

Before defining a chronicle, it is good to remember that it is based on the verification of time constraints. The check is directly inspired by a Simple Temporal Problem (STP) introduced by [START_REF] Dechter | Temporal constraint networks[END_REF]. The occurrence of different events in time represents the system's dynamics in a given situation. The concept of event type expresses a change in the value of a given domain feature or set of features. E expresses the set of all event types. Note σ an event type where σ ∈ E. We can thus define the concept of event.

Definition 1: An event e is defined as a pair e = (σ, t), where σ ∈ E is an event type and t is a variable of integer type called the event date.

Several events can have the same event type, but do not necessarily have the same date, for instance e 1 = (a, 3) and e 2 = (a, 6) are two events carrying the same type of event a.

A flow of activity generated by a system is represented by a sequence. A sequence consists of several events in an orderly manner, which leads us to the following definition:

Definition 2: A sequence is defined as an ordered set of events denoted S = {e i } where i ∈ N , i = 1, ..., l and t i < (t i+1 ), i = 1, ..., l -1 where l is the length of the time sequence S.

An example of sequence representing an activity stream may be given by a sequence S 1 = {e 1 , e 2 , e 3 , e 4 , e 5 , e 6 } = {(a, 2), (b, 4), (c, 5), (a, 8), (b, 9), (a, 10)} with l 1 = 6.

Finally, a chronicle is a set of event types associated with time variables and a set of temporal constraints between time variables.

Definition 3: A chronicle is defined as a triplet C = (ξ, T , G) such that:

• ξ ⊆ E.
Where ξ is called the typology of the chronicle.

• T is the set of temporal constraints of the chronicle.

• G = (V, A) is a directed graph where:

• V represent the event types of ξ • The arcs A represent the different time constraints between event types. The edge i → j is associated to the constraint τ ij ∈ T

Considering the two events (e i , t i ) and (e j , t j ), we define the time interval as the pair τ ij = [t -, t + ], τ ij ∈ T corresponding to the lower t -and upper t + bounds on the temporal distance between the two event dates t i and t j . If the event e 2 occurs after e 1 , then it exists a directed link A from e 1 to e 2 associated with a time constraint.

A chronicle C = (ξ, T , G) is recognized in a given sequence S when ξ ⊆ ξ (ξ set of event types associated to S ) and all temporal constraints T are satisfied.

C inst = (ξ, T v )
where T v is a valuation of T , is an instance of C.

LEARNING CHRONICLES

The chronicle exploration process corresponds in discovering all the chronicles, whose instances occur in a given sequence. In many cases, the same situation does not implies perfectly identical sequences. This is the reason of that HCDAM uses several sequences as input.

Learning chronicles with HCDAM

The algorithm HCDAM learns the chronicles, whose instances occur in all event sequences representing the same situation [START_REF] Subias | Learning chronicles signing multiple scenario instances[END_REF]). Given a set of sequences S and a minimum frequency threshold, it finds all minimal frequent chronicles present in all sequences.

The chronicle learning algorithm has the following three phases:

(1) Filtering (2) Building a constraint database from the input sequences.

(3) Generating a set of candidate chronicles.

Phase 1:

The f iltering operation is a preliminary process on sequences and it can be summarized as follows:

• Filter the event types that are not present in all input sequences S: if ∃S k ∈ S such as ∃σ i ∈ S k , then remove σ i from all the other sequences in S. • Filter on a given set of event types Ψ = {σ 1 , σ 2 , ..σ r } if we are only interested in those event types for the learning process.

3.1.2. Phase 2: Phase two builds a constraint data base D by considering each pair of event types and its temporal constraints in a constraint graph with tree structure.

In this constraint tree, time constraints are nodes and arcs represent the relationship is parent of defined as:

Definition 5: A node e i [t -, t + ]e j corresponding to the time constraint between e i and e j is parent of e i [t -, t + ]e j if and only if [t -, t + ] ⊂ [t -, t + ] and there does not exist

e i [t -, t + ]e j such that [t -, t + ] ⊂ [t -, t + ] ⊂ [t -, t + ].

Phase 3:

The generation of a set of candidate chronicles initializes with a set of chronicles that were proved to be frequent and it uses the constraint database to explore the chronicle space [START_REF] Cram | A complete chronicle discovery approach: application to activity analysis[END_REF]).

• The set of candidates initiates with the set of tree roots • Use the operator "add ε". This operator, checks at the constraint graphs in order to find the restrictions of ε with all elements of E. • Determine the minimal number of occurrences of the candidate in S

The details of the algorithm HDCAM can be found in [START_REF] Subias | Learning chronicles signing multiple scenario instances[END_REF]).

3.2 Improving restrictivness/conservatism 3.2.1. Integration of process knowledge Expert knowledge can be represented by temporal runs that express a known time constraint between two event type dates. These temporal runs are gathered in an expert data base D e . To integrate this knowledge, Phase 2 of HCDAM is modified. One first checks the existence of a temporal run T R ij for each pair of event types (e i , e j ). Temporal run, which replaces the tree root of this pair of event types. The effect of the integration of temporal runs corresponds to focus the learning process and produce less conservative chronicles; it means that the number of chronicles that represents a specific scenario could be reduced using the expertise knowledge.

Definition 6: A temporal run is defined as a partial order of time points with time restrictions between each pair. For the pair of event types (e i , e j ), a temporal run is defined as

T R ij = e i [t -, t + ]e j
Example of the "charge oven" activity: the results of learning obtained without the inclusion of temporal runs and with the inclusion of temporal runs are given in a simple example of activity consisting in a charging an oven as represented in Figure . 1. The event types are given by E = {a, b, c, d}, where a (b) is the event of detecting product a (b) entering the oven, c is the event corresponding to putting the heaters on, and d is the event of setting the heaters to high temperature. The event sequences that express normal startup of this process are: Using the extended version of the algorithm HCDAM , the results including temporal runs provide 4 chronicles reducing the number of chronicles by 50%.

S 1 = {(a, 2

Integration of event information

Another type of expert knowledge that is often available is the occurence frequency f (ei) of a single event e i . This information is not taken into account in HDCAM . Nevertheless it can be very useful to reduce the number of learned chronicles.

With the event Φ we can to obtain the occurrence frequency of each event type that occurs in S k . This occurrence frequency permits improved the restrictiveness in the system of chronicles; for example, in a scenario represented by 7 chronicles of frequency 1 and 3 chronicles of frequency 2, the use of the event Φ enables to analyze the system with only one unique chronicle, not 10.

Definition 7: We define the event Φ as the initial event in all the event sequences S such that the occurrence frequency f (ei) for each event type e i in the sequence S k is determined from this event Φ.

Assuming the above example, we use the integration of event information for structure an unique chronicle reducing the number of chronicles in 90% see Figure . 2. In this chronicle, the concept of frequency is assumed as the occurrence frequency for each event type in a sequence, not as the occurrence frequency of a pair of events.

CASE STUDY -VACUUM OVEN

This section presents a case study from the Cartagena Refinery in Colombia. Our proposal aims at helping the operator to recognize specific operation (i.e normal and/or faulty operation) during the startup and shutdown stages

Event type identification

The set of event types E considered in the chronicles is defined by E = Σ ∪ Σ c where:

• Σ is the set of procedural actions performed during standard operating procedures • Σ c is the set of event types associated to the behavior of the continuous variables .

Procedural actions concern mainly the valves of the oven and Σ = {V 1, V 2, V 3, v1, v2, v3, M 2A}. where V 1 (resp.

V 2, V 3) denotes the switch of the valve V1 (resp. V2,V3) from closed to opened. v1 (resp v2, v3) the switch of the valve V1 (resp. V2,V3) from opened to closed. The event M 2A corresponds to the change from manual to automatic operating, closing the control loops. In the reminder we assume that this event is the only unobservable event of the system i.e. Σ uo = {M 2A}.

Continuous variables are associated to the different flows (F 1, F 2, F 3) and different temperatures (T 1, T 2, T 3 and T 4) (see Figure 3). For each evolution of a continuous variable (obtained by simulation) upper and lower bounds are defined from experience feedback. Then the continuous values of the variable are mapped to ranges defined by these limits. We propose to define three ranges: High when the value of the continuous variable is higher than the upper bound, Medium when the value is between the upper and lower bounds, and Low when the value is under the lower limit bound. Form this qualitative abstraction of the continuous variable evolution we consider that an event is generated each time a transition between qualitative domains (i.e ranges) occurs. So, for a continuous variable noted v i four event types can be considered: L vi (resp. l vi ) for a transition from the range L to the range M (resp. M to L). H vi (resp h vi ) for a transition from the range M to the range H (resp. H to M) [START_REF] Vasquez | Alarm management based on diagnosis[END_REF]). For the vacuum oven the set of event types associated to the behavior of the continuous variables is then defined by:

Σ c =        L F 1 , l F 1 , H F 1 , h F 1 , L F 2 , l F 2 , H F 2 , h F 2 , L F 3 , l F 3 , H F 3 , h F 3 , L T 1 , l T 1 , H T 1 , h T 1 , L T 2 , l T 2 , H T 2 , h T 2 , L T 3 , l T 3 , H T 3 , h T 3 , L T 4 , l T 4 , H T 4 , h T 4 (1)

Learning event sequences generation

The learning event sequences are generated according to the behavior of the system in a given scenario (scenario of normal operating, faulty scenario with a fault on valve, etc...). In this section we consider a scenario of normal behavior during the start up of the oven. By simulation we have obtained three different event sequences (S 1 , S 2 and S 3 ) all of them associated with the same scenario.

Figure 4 shows one simulation of the scenario leading to the generation of the sequence S 1 given by:

S 1 = (V 3, 1), (L T 1 , 3), (L F 3 , 5), (V 1, 6), (L T 4 , 7), (L F 1 , 8), (H F 1 , 12), (v1, 13), (V 2, 14), (H T 1 , 15), (h F 1 , 16), (L F 2 , 17), (H T 4 , 19), (H F 2 , 22), (l F 1 , 24), (h T 1 , 25), (h T 4 , 26), (h F 2 , 27), (V 1, 42), (L F 1 , 45)
The two others sequences S 2 and S 3 are identical to S 1 in term of sequence of event types but differ to S 1 in term of event occurrence dates.

S 2 = (V 3, 1), (L T 1 , 7), (L F 3 , 13), (V 1, 18), (L T 4 , 21), (L F 1 , 24), (H F 1 , 32), (v1, 35), (V 2, 37), (H T 1 , 40), (h F 1 , 45), (L F 2 , 48), (H T 4 , 54), (H F 2 , 61), (l F 1 , 65), (h T 1 , 68), (h T 4 , 72), (h F 2 , 76), (V 1, 96), (L F 1 , 101)

S 3 = (V 3, 2), (L T 1 , 6), (L F 3 , 9), (V 1, 12), (L T 4 , 14), (L F 1 , 16), (H F 1 , 22), (v1, 24), (V 2, 25), (H T 1 , 27), (h F 1 , 30), (L F 2 , 32), (H T 4 , 36), (H F 2 , 41), (l F 1 , 43), (h T 1 , 45), (h T 4 , 48), (h F 2 , 50), (V 1, 68), (L F 1 , 71)
This scenario can be interpreted from the standard procedure. For the startup stage, the initial conditions are that the oven (Ov) is empty and the valves V1, V2 and V3 are closed. In this situation, the values for all the continuous variables are below its low limits (F 1, F 2, F 3, T 1, T 2, T 3, T 4 ). Then the scenario starts with the opening of the valve V3 that is to say the occurrence of an event of type V 3. After this event type occurrence, the system is in a mode of operation where only the valves V1 and V2 are closed. The variable T 1 increases and and event of type L T 1 must occur indicating that the internal oven temperature has passed the limit of low. Then the flow of the fuel gas reaches its low limit and an event of type L F 3 occurs. So, the ordered sequence of event types that has occurred is V 3, L T 1 , L F 3 . Passing the low limit of F 3 is the condition for continuing the procedure by the action Open V1 (V 1). When the operator opens the valve V1, the system evolves to a mode of operation where the internal flow in the vacuum oven starts. In this situation, the flow F 1 and the outflow temperature T 4 increase(event of type L T 4 followed by an event of type L F 1 ). The next event that occurs is of type H F 1 indicating that the flow F 1 has passed its high level. At this stage, the ordered sequence of event types is given by: V 3,

L T 1 , L F 3 , V 1, L T 4 , L F 1 , H F 1 .
The next procedural action is the closing of the valve V1 (v1) followed by the opening of the valve V2 (V 2). Then, the high limit of the temperature T 1 is reached and an event of type H T 1 occurs. The flow F 1 decreases from its high limit (event type h F 1 ). An event of type L F 2 occurs because the flow in V2 increases. The high limit in the temperature T 4 induced and event of type (H T 4 ). Following up with the procedure, due to the high limit of F 2 an event of type H F 2 . At this time point, the ordered sequence of event types that has occurred is

V 3, L T 1 , L F 3 , V 1, L T 4 , L F 1 , H F 1 , v1, V 2, H T 1 , h F 1 , L F 2 ,H T 4 , H F 2 .
In this situation, an unobservable event of type M 2A occurs and the control loops are closed, carrying the system to a steady state. Note that in this study,we assume that the control loops are closed immediately after and event of type H F 2 . Then, F 1, T 1 and T 4 decrease (event types l F 1 , h T 1 and h T 4 . Finally, the sequence ends by and event of type h F 2 and by the opening of the valve V1 so that the last event that occurs in this normal startup is of type L F 1 .

Construction of the chronicle database

A complex process (P r) such the Cartagena Refinery is composed of n ∈ N different units or areas P r = {Ar 1 , Ar 2 , ...Ar n } where each area Ar m , m = 1, ..., n has K ∈ N operational modes (e.g startup, shutdown ..) noted O i , i = 1, ..., K. The process behavior in each operating mode can be either normal or faulty. We define the set of failure labels ∆ f = f 1 , f 2 , ...., f r and the complete set of possible labels is ∆ = N ∪ ∆ f , here N means normal.

To monitor the process and to recognize the different situations (normal or faulty) of the operational modes, we propose to build a chronicle base for each area. For a given area, a learned chronicle C m ij is associated to each couple (O i , l j ) where l j ∈ ∆:

CAr m = O 1 O 2 . . . O k N f 1 f 2 . . . f r    C m 10 C m 11 C m 12 . . . C m 1r C m 20 C m 21 C m 22 . . . C m 2r . . . . . . . . . . . . . . . . . . . . . C m k0 C m k1 C m k2j . . . C m kr    (2)
When l j = N , the chronicle is a model of the normal behavior of the considered system, otherwise (l j = f i ) the chronicle is a model of the behavior of the system under the occurrence of the fault f i .

For the vacuum oven we have considered a normal startup, a normal shutdown and several faulty cases. For instance, a startup stage during which a fault occurs on the control valve V3. We present in this section only the chronicle C 2 10 learned from the input sequences S 1 , S 2 and S 3 capturing a normal startup operating mode of the vacuum oven (area number 2 of the Cartagena Refinery).

In this case of normal startup stage, expert knowledge is available and integrated in our proposal by three temporal runs:

T R V 3,L F 3 =V 3[6, 8]L F 3
, this temporal run expresses that the lower limit of the flow in F 3 arrives between 6 and 8 time units after that the valve V3 is opened. -76, 82]L F 1 , this temporal run indicates that the lower limit of the flow in F 1 can occur 76 time units before that the valve V1 is opened or 82 time units after that.

T R V 1,L F 1 =V 1[
T R L F 2 ,V 2 =L F 2 [2, 8]V 2, this temporal run indicates that the valve V2 is opened between 2 and 8 time units after that the lower limit of the flow in F 2 happen.

The output of the extended HCDAM in this case is a chronicle that represents the behavior of the system taking as reference the representative event sequences obtained by simulation and the temporal runs obtained from the expertise knowledge. The directed graph associated to the chronicle C 2 10 is given Figure 5. As we can see in the chronicle resulted C 2 10 , this chronicle expresses the temporal pattern for a normal start up of this system. Although the three representative event sequences in this scenario are similar, this temporal pattern can represent other cases where the order of the event types could be different between the learning event sequences. The frequency of occurrence of the event types V 1 and L F 1 are f V 1 =2, f L F 1 =2 and for the others event types it is 1. With this information and the use of temporal runs, the resulted chronicle is only one for this scenario.

CONCLUSION AND FUTURE WORK

A new methodology for an alarm management based on a diagnosis process has been proposed. The proposal is based on a hybrid causal model of the system and a chronicle based approach for diagnosis. An illustrative example of the vacuum oven has been considered to introduce the main concepts of the approach. The algorithm HCDAM is a tool for the automatic generation of the chronicles from the representative event sequences and partial temporal runs. Transposing this methodology to large-scale systems would benefit from a decentralized approach in which local chronicles would be learned and then integrated thanks to shared events.

Future work

The following work will be related to the testing and validation of the model of chronicles. A new approach to carry into account negative examples and forgetting capabilities in the chronicle learning algorithm will be proposed.

  Fig. 1. Example of the "charge oven" activity

Fig. 3 .

 3 Fig.3. Vacuum oven of the vacuum oven unit described Figure3. This section illustrates then the learning of the chronicle base that will be considered by a recognition system to recognize these normal or faulty situations when they occur, and in the next subsections the CBAM methodology is applied with its three steps: 1. Event type identif ication, 2. Learning event sequences generation and 3. Construction of the chronicle database,[START_REF] Vasquez | Chronicle based alarm management in startup and shutdown stages[END_REF],[START_REF] Vasquez | Alarm management based on diagnosis[END_REF].

Fig. 4 .

 4 Fig. 4. Simulation of a normal startup (normalized values)

Fig. 5 .

 5 Fig. 5. Directed graph (G) of the chronicle C 2 10

ACKNOWLEDGEMENTS

The ECOPETROL -ICP engineers Carlos Agudelo, Jorge Prada, Francisco Cala and Gladys Valderrama help us to develop and validate the simulations.