Rim El Ballouli

Saddek Bensalem

Marius Bozga
email: marius.bozga@univ-grenoble-alpes.fr

Joseph Sifakis

Rim El

Programming Dynamic Reconfigurable Systems

Keywords: architectural motifs, components, reconfigurable systems

DR-BIP is an extension of the BIP component framework intended for programming reconfigurable systems encompassing various aspects of dynamism. It relies on architectural motifs to structure the architecture of a system and to coordinate its reconfiguration at runtime. An architectural motif defines a set of interacting components that evolve according to reconfiguration rules. With DR-BIP, the dynamism can be captured as the interplay of dynamic changes in three independent directions 1) the organization of interactions between instances of components in a given configuration; 2) the reconfiguration mechanisms allowing creation/deletion of components and management of their interaction according to a given architectural motif; 3) the migration of components between predefined architectural motifs which characterizes dynamic execution environments. The paper lays down the formal foundation of DR-BIP, illustrates its expressiveness on few examples and discusses avenues for dynamic reconfigurable system design.

Introduction

Modern computing systems exhibit dynamic and reconfigurable behavior. They evolve in uncertain environments and have to continuously adapt to changing internal or external conditions. This is essential to efficiently use system resources e.g. reconfiguring the way resources are accessed and released in order to adapt the system behavior in case of mishaps such as faults, and to provide the adequate functionality when the external environment changes dynamically as in mobile systems. In particular, mobile systems are becoming important in many application areas including transport, telecommunications and robotics.

There exist two complementary approaches for the expression of dynamic coordination rules. One respects a strict separation between component behavior and its coordination. Coordination is exogenous in the form of an architecture that describes global coordination rules between the coordinated components. This approach is adopted by numerous Architecture Description Languages (ADL) (see [START_REF] Bradbury | Organizing definitions and formalisms for dynamic software architectures[END_REF] for a survey). The other approach is based on endogenous coordination by using explicitly primitives in the code describing the behavior of components. Most programming models use internalized coordination mechanisms. Components usually have interfaces that specify their capabilities to coordinate with other components. Composing components boils down to composing interfaces. This approach is in particularly adopted by formalisms such as dynamic wright [START_REF] Allen | Specifying and analyzing dynamic software architectures[END_REF], leda [START_REF] Canal | Specification and refinement of dynamic software architectures[END_REF], pilar [START_REF] Quintero | Dynamic coordination architecture through the use of reflection[END_REF], scel [START_REF] De Nicola | A formal approach to autonomic systems programming: The SCEL language[END_REF] to name just a few based on process algebra. The obvious advantage of endogenous coordination is that programmers do not have to build explicitly a global coordination model. The absence of such a model makes the validation of coordination mechanisms and the study of their underlying properties much harder. In contrast, exogenous coordination is advocated for enabling the study of the coordination mechanisms and their properties. It motivated numerous publications and the development of 100+ ADLs [START_REF] Malavolta | What industry needs from architectural languages: A survey[END_REF]. In this case, the coordination model is external to the behavior and can therefore be used to perform some analysis almost independently from the behavior.

There exists a huge literature on architecture modeling reviewed in detailed surveys classifying the various approaches and outlining new trends [START_REF] Garlan | Software architecture: a travelogue[END_REF] and needs from an industrial perspective [START_REF] Malavolta | What industry needs from architectural languages: A survey[END_REF]. Despite the impressive amount of work on this topic there is no clear understanding about how different aspects of architecture dynamism can be characterized.

We consider that the degree of dynamism of a system can be captured as the interplay of dynamic change in three independent aspects. The first aspect requires the ability to describe parametric system coordination for arbitrary number of instances component types. For example, systems with m Producers and n Consumers or Rings formed from n identical components. The second aspect requires the ability to add/delete components and manage their interaction rules depending on dynamically changing conditions. This is needed for a reconfigurable ring of n components e.g. removing a component which self-detects a failure and adding the removed component after recovery. So adding/deleting components implies the dynamic application of specific interaction rules depending on their type. This is also needed for mobile components which are subject to dynamic interaction rules depending on the state of their neighborhood. The third aspect is currently the most challenging. It meets in particular, the vision of "fluid architectures" [START_REF] Taivalsaari | Liquid software manifesto: The era of multiple device ownership and its implications for software architecture[END_REF] which allows components/services to seamlessly roam and continue their activities on any available device or computer. Applications and objects live in an environment which is conceptually an architecture motif. They can be dynamically transported from one motif to another. Supporting dynamic migration of components allows a disciplined and easy-toimplement management of dynamically changing coordination rules. For instance, self-organizing systems may adopt different coordination motifs to adapt their behavior so as to meet a global property.

The paper presents Dynamic Reconfigurable BIP (DR-BIP) component framework, an extension of BIP [START_REF] Basu | Modeling heterogeneous real-time components in BIP[END_REF][START_REF] Basu | Rigorous componentbased system design using the BIP framework[END_REF] which encompasses all these three aspects of dynamism. DR-BIP has been introduced in [START_REF] Ballouli | Programming dynamic reconfigurable systems[END_REF] and represents one further step in our research toward extending BIP with dynamic features. This research was initiated with Dy-BIP [START_REF] Bozga | Modeling dynamic architectures using Dy-BIP[END_REF] for BIP with dynamic interactions and more recently continued with Functional BIP [START_REF] Edelmann | Functional BIP: embedding connectors in functional programming languages[END_REF] and Java BIP [START_REF] Mavridou | Coordination of dynamic software components with Jav-aBIP[END_REF] for BIP with dynamic components and interactions. As such, DR-BIP follows an exogenous approach respecting the strict separation between behavior and architecture. It directly encompasses multiparty interaction [START_REF] Bliudze | The algebra of connectors -structuring interaction in BIP[END_REF] and is rooted in formal operational semantics allowing a rigorous implementation. DR-BIP privileges an imperative and exogenous style characterizing dynamic architecture as a set of interaction rules implemented by connectors and a set of configuration rules.

Although DR-BIP does not allow adhoc dynamism, it directly encompasses several kinds of dynamism at run time namely, programmed dynamism and in addition adaptive dynamism, and self-organizing dynamism according to the classification in [START_REF] Bradbury | Organizing definitions and formalisms for dynamic software architectures[END_REF]. It provides support for component creation and removal at run time. Moreover, DR-BIP directly supports component migration from one motif to another. It supports programmed reconfiguration and triggered reconfiguration as defined in [START_REF] Butting | A classification of dynamic reconfiguration in component and connector architecture description[END_REF]. The big advantage from using motifs is that when a component is created, its type defines the interaction with other components. So, a motif is a "world" where components live and from which they can migrate to join other "worlds" as in fluid architectures [START_REF] Taivalsaari | Liquid software manifesto: The era of multiple device ownership and its implications for software architecture[END_REF].

This paper is an extended version of two recent conference papers, namely [START_REF] Ballouli | Programming dynamic reconfigurable systems[END_REF] presenting the formal foundation and [START_REF] Ballouli | Four exercises in programming dynamic reconfigurable systems: Methodology and solution in DR-BIP[END_REF] introducing additional examples of DR-BIP. It was restructured to provide a comprehensive introduction and clarification of key DR-BIP concepts as well as to fully illustrate its modeling expressivity on a complete set of benchmarks. It justifies the proposed concepts, discusses their limitations and identifies potential improvements from a practical point if view. Furthermore, it provides an extended discussion of related work.

The paper is organized as follows. Section 2 provides a brief overview of DR-BIP and major design principles. Section 3 briefly recalls the key concepts of BIP and its operational semantics. Section 4 introduces formally the motif concept and its semantics and Section 5 introduces formally motif-based systems. Section 6 presents several examples with benchmarks using the DR-BIP implementation as well as some lessons learned from these experiments. We discuss related work in section 7. Finally, section 8 presents conclusions and future work directions.

DR-BIP Overview

The DR-BIP framework is designed to cover the practical needs for the design of dynamic systems, and therefore, fulfill specific requirements for rigorous design and analysis. It allows to:

specify architectural constraints/styles, i.e. define architectures as parametric operators on components guaranteeing by design specific properties, describe systems with evolving architectures, i.e define system architecture that can be updated at runtime using dedicated primitives, support separation of concerns, i.e. keeping separate the component behavior (functionality) from the system architecture to avoid blurring the behaviors with information about their execution context and/or reconfiguration needs, provide sound foundation for analysis and implementation, i.e. rely on a well-defined operational semantics, leveraging on existing models for rigorous component-based design.

The following motivating example belongs to the category of dynamic systems we are interested to consider for DR-BIP. This example will be used along the paper to illustrate the newly proposed concepts.

Example 1 (dynamic token ring) A token ring consists of two or more identical components interconnected using uni-directional communication links according to a ring topology. A number of tokens are circulating within the ring. A component is busy when it holds a token and idle otherwise. A component can do specific internal actions depending on its state, busy or idle. It can receive a token from the incoming link only its idle and send its token on the outgoing link only when its busy.

A token ring is dynamic if idle components are allowed to leave the ring at any time as long as at least two components remains in the ring. New idle components are allowed to enter the ring at any time (as long as the maximal allowed ring size is not reached). A token ring system consists of one or more, pairwise disjoint, token rings. A token ring system is dynamic if every ring is dynamic, and moreover, two rings are allowed to merge into a single one provided their overall size is not exceeding the maximal allowed ring size.

Motifs for Dynamic Architectures

In DR-BIP, a motif is the elementary unit used to describe dynamic architectures. A motif encapsulates (i) behavior, as a set of components, (ii) interaction rules dictating multiparty interaction between components and (iii) reconfiguration rules dictating the allowed modifications to the configuration of a motif including the creation/deletion/migration of components. Motifs are structurally organized as the deployment of component instances on a logical map as illustrated in Both sets of rules are interpreted on the current motif configuration. Formal-params denotes (sets of) component instances and defines the scope of the rule. Rule-constraint defines the conditions under which the rule is applicable. Constraints are essentially boolean combinations on deployment and map constraints built from formal-args. An interaction rule also defines the set of interacting ports (interaction-ports), the interaction guard (guard ) and the associated interaction actions (interaction-action). The guard and the action define respectively a triggering condition and an update of the data of components participating in the interaction. Finally, a reconfiguration rule defines a reconfiguration guard (guard ) and a number of reconfiguration actions (reconfiguration-action) to update the content of the motif. Such actions include creation/deletion of component instances, and change of their deployment on the map as well as change of the map itself, i.e. adding/removing map positions and their interconnection. Notice that rule constraints and guards deal with complementary aspects. The former are constraints on motif configuration (map and deployment) whereas the later are constraints on component data only. In a similar way, reconfiguration actions update motif configurations whereas interaction actions update component data only.

Example 3 (motif rules)

The interaction rule given in Fig. 2 (top) reads as follows: for components x 1 , x 2 deployed on adjacent nodes (that is, D(x 1 ) → D(x 2 )) connect their ports x 1 .out and x 2 .in 1 . This rule defines three interactions between the components namely {b 1 .out b 3 .in}, {b 3 .out b 2 .in}, and {b 2 .out b 1 .in}. The reconfiguration rule given in Fig. 2 (bottom) allows to extend the ring by adding one more component. The rule is applicable as long as the number of component instances |B| is less than or equal to 10. When executed, a new component x of type C is created at initial state idle (that is, x := B.create(C, idle)), a new node n is added to the cycle map (that is, n := H.extend()) and the component x is deployed on the node n (that is, D.attach(x, n)).

Notice that the distinction between reconfiguration and interaction rules allows separation of concerns in modeling dynamic architectures. On one hand, reconfiguration rules are used to update the motif structure (components, map, deployment) under specific conditions (as depicted by the the red arrows in Fig. 1). On the other hand, interaction rules use the motif structure to define how the components of the motif are interconnected (as depicted by the green arrows in Fig. 1). This approach associates interaction rules with motifs and these rules remain unchanged when components are created or removed.

The reason for choosing maps and deployments as a mean for structuring motifs is their simplicity. On one hand, maps and deployments are common concepts, easy to understand, manipulate and formalize. On the other hand, they adequately support the definition of arbitrarily complex sets of interactions over 1 The dot operator is used interchangeably to access a component's port/data, and to access a motif's components/deployment/map, and to apply primitives over a motif's deployment/map. components by relating them to connectivity properties (neighborhood, reachability, etc). Moreover, maps and deployments are orthogonal to behavior. Therefore they can be manipulated/updated independently and they also provide a very convenient way to express various forms of reconfiguration. Both maps and deployments are implemented as dynamic collections of objects, with specific interfaces, in a similar way to standard collection libraries available for standard programming languages.

Motif-based Systems

Several types of motifs may be defined separately by specifying the types of hosted components, parametric interactions and reconfiguration rules. Then, systems are described by superposing a number of motif instances of certain motif types. In this manner, the overall system architecture captures specific architectural/functional properties by design.

Systems are defined as collections of motifs sharing a set of components as depicted in Fig. 3. Each motif can evolve independently of the others, depending only on its internal structure and associated rules. Furthermore, several motifs can synchronize all together to jointly perform a reconfiguration of the system. Coordination between motifs is therefore possible either implicitly by means of shared components or explicitly by means of inter-motif reconfiguration rules. These rules allow joint reconfiguration of several motif instances. They also allow two additional types of actions, respectively creation and deletion of motif instances, and exchanging component instances between motifs.

Both coordination mechanisms were proven useful and easy to use in practice. On one hand, global reconfiguration rules provide an imperative way of changing several motifs simultaneously e.g., to migrate a component between motifs, to merge several motifs into a single one, etc. On the other hand, sharing a component between several motifs allows controlling local reconfiguration in the motifs. For instance, local reconfiguration rules may be enabled in some motif, and disabled in another one, depending on the state of the component.

How these two coordination mechanisms are combined depends on the dynamics of the considered system architecture. In some cases, the dynamics can be captured by a fixed number of motifs with a very restricted form of global reconfiguration (e.g., only migration of components between motifs). This is the situation for the dynamic multicore task system in section 6.1 and the self-organizing robot colonies in section 6.3. In other cases, the dynamics is captured by an evolving number of motifs and complex global reconfiguration (e.g., merging or splitting existing motifs). This is the situation for the dynamic token ring example, as well as for the highway traffic system in section 6.

1 b 2 c 1 c 2 c 4 c 3 b 1 b 2 c 1 c 2 c 3 c 4 b 1 b 2 c 1 c 2 c 4 c 3 b 3 c 5
Fig. 4: An example of system reconfigurations

Execution Model

The evolution of motif-based systems in DR-BIP is defined in a compositional manner. Every motif defines its own set of interactions based on its local structure. This set of interactions and the involved components remain unchanged as long as the motif does not execute a reconfiguration action. Hence in the absence of reconfigurations, the system keeps a fixed static architecture and behaves like an ordinary BIP system. The execution of interactions has no effect on the architecture. In contrast to interactions, system and/or motif reconfigurations rules are used to define explicit changes in the architecture. However, these changes have no impact on components, i.e. all running components preserve their state although components may be created/deleted. This independence between execution steps is illustrated in Fig. 5. BIP [START_REF] Basu | Modeling heterogeneous real-time components in BIP[END_REF][START_REF] Basu | Rigorous componentbased system design using the BIP framework[END_REF] is the underlying component-based framework for DR-BIP. In BIP, systems are constructed from atomic components, which are finite state automata, extended with data and ports. Communication between components is by multiparty interactions with data transfer. BIP systems are static in the sense that components and interactions are fixed at design time and do not change during system execution. We briefly recall the key BIP concepts and their operational semantics.

Component types and instances

A component type B t is an extended labeled transition system (L, P, V, T ), where L is a finite set of control locations, P is a finite set of ports, V is a finite set of data variables and T ⊆ L × P × G(V ) × F(V ) × L is a finite set of labeled transitions, where G(V ) and F(V ) are respectively Boolean guards and update functions defined over variables V . Every transition τ = ( , p, g, f, ) ∈ T is equivalently denoted as τ = p g f ---→ ∈ T . For every port p ∈ P , we associate a subset of variables V p ⊆ V exported and available for interaction through p.

For a component type B t = (L, P, V, T ), its set of states is Q = L × V where V is the set of all valuations defined on V . A valuation of a set of variables V is a function v : V → D, where D is an underlying domain of data values. The semantics of a component type B t is defined as the labeled tran-

sition system [[B t ]] = (Q, Σ, - →)
where the set of labels 2) the guard g holds on the current state valuation v, (3) v p is a valuation of exported variables V p and ( 4

Σ = {p(v p ) | v p ∈ V p } and transitions - →⊆ Q × Σ × Q are defined by the rule: τ = p g f ---→ ∈ T g(v) v p ∈ V p v = f (v[v p /V p ]) B t : ( , v) p(v p ) ---→ ( , v ) That is, ( , v ) is a successor of ( , v) labeled by p(v p ) iff (1) τ = p g f ---→ is a transition of T , (
) v = f (v[v p /V p ])
that is, the next-state valuation v is obtained by applying f on v previously updated according to v p . Whenever a p-labeled successor exists from a state, we say that p is enabled in that state.

We consider a given finite set of component types. A component instance b is a couple (B t , k) for some k ∈ N. We denote respectively by ports(b), states(b), labels(b) the set of ports, states and labels associated to the instance b according to its type.

Example 4 (component type) Fig. 6 (left, top) illustrates graphically a component type. The component has two ports (in, out) attached with variables (respectively u, v. It has two control locations (idle, busy) and three transitions labeled by the ports. For example, the transition labeled by in changes control location from idle to busy while performing the computation v := u+1. ) is a set of ports, G a is a Boolean guard, and F a is an update function. By definition, P a must use at most one port of every component in B, that is, |P i ∩ P a | ≤ 1 for all i ∈ {1..n}. Therefore, we simply denote P a = {b i .p i } i∈I , where I ⊆ {1..n} contains the indices of the components involved in a and for all i ∈ I, p i ∈ ports(b i ). G a and F a are defined on the variables exported by ports in P a (i.e., p∈Pa V p ).

The semantics of a system S = Γ (B) is defined as the labeled transition system

[[S]] = (Q, Σ, - →) where the set of states Q = b → q | b ∈ B, q ∈ states(b)
, the set of labels Σ ⊆ P(ports(B) × P(V)) contains the ports and sets of values exchanged on interactions and transitions -→ are defined by the rule:

a = ({b i .p i } i∈I , G a , F a ) ∈ Γ G a ({v pi } i∈I ) {v pi } i∈I = F a ({v pi } i∈I ) ∀i ∈ I. B t i : ( i , v i ) pi(v p i ) ----→ ( i , v i ) ∀i ∈ I. ( i , v i ) = ( i , v i ) Γ (B) : b 1 → ( 1 , v 1 ), . . . , b n → ( n , v n ) {bi.pi(v p i )} i∈I ----------→ b 1 → ( 1 , v 1 ), . . . , b n → ( n , v n )
For each i ∈ I, v pi above denotes the valuation v i restricted to variables of V pi . The rule expresses that S can execute an interaction a ∈ Γ enabled in state (( 1 , v 1 ), . . . , ( n , v n )), iff (1) for each p i ∈ P a , the corresponding component instance b i can execute a transition labeled by p i , and (2) the guard G a of the interaction holds on the current valuation v pi of exported variables on ports in a. Execution of a triggers first the update function F a which modifies exported variables V pi . The new values obtained, encoded in the valuation v pi , are then used by the components' transitions. The states of components that do not participate in the interaction remain unchanged. Example 5 (system of components) Fig. 6 (left, bottom) depicts a binary interaction between two ports out, in, having guard true and update function u := v. That is, whenever the interaction is executed, the data is transferred from the out port to the in port. Fig. 6 (right) illustrates a system obtained by composing six b i instances with six out in interactions in a ring structure.

Motifs for Dynamic Architectures

Motifs are dynamic structures composed of interacting components. Their structure is expressed as a combination of three concepts namely, behavior, map and deployment. The behavior consists of a set of components. The map is an underlying logical structure (backbone) used to organize the interaction of components. The deployment provides the association between the components and the map. The components within a motif run in parallel and synchronize using multiparty interactions. The set of multiparty interactions is defined by interaction rules evaluated on the structure of the motif. Finally, the motif structure is also evolving. Any of the three constituents can be modified i.e., components can be added/removed to/from the motif, the map and/or the deployment can change. The motif evolution is expressed using reconfiguration rules, which evaluate and update the motif structure accordingly. The following subsections present formally all the motif-related concepts.

Maps and deployments

Maps and deployments are abstract concepts used to organize the motifs. Maps denote arbitrary dynamic collections of inter-connected nodes (positions). They are defined as particular instances of generic map types H t characterized by (i) an underlying domain N (H t ) of nodes, (ii) a set of primitives Ω(H t ) to update/access the map content and (iii) a logic L(H t ) to express constraints on the map content.

We use maps as dynamic data structures (objects). For a map H of type H t , its set of nodes is denoted by dom(H) and is a subset of N (H t ). For any primitive op ∈ Ω(H t ) we use the dotted notation H.op(...) to denote the update and/or access to the map H according to op. Moreover, for any ψ ∈ L(H t ) we will use H |= ψ to denote that the constraint ψ is satisfied on H.

Example 6 (maps as directed graphs) Map types can be directed graphs (V, E) where vertices V denote the positions and edges E ⊆ V × V expressing the connectivity between these positions. Such a map type (i) has the domain V , (ii) can be manipulated explicitly using primitives such as addVertex, remVertex, addEdge, remEdge and (iii) has predicates allowing to express edge constraints • → •, path constraints • → * •, etc, with the usual meaning.

Example 7 (maps as cycle graphs) In the dynamic token ring example from Fig. 2 the map type is a cycle graph consisting of a single cycle, where (i) vertices compose the domain, (ii) primitives include init, extend, remove to respectively initialize to an empty cycle, extend by one vertex (inserted arbitrarily), remove one specified vertex from the cycle and (iii) predicates allows for checking edge constraints • → •, as usual.

Deployments are partial mappings of a set B of component instances to the nodes of a map H, formally D : B → dom(H) ∪ {⊥}. As for maps, deployments are dynamic data structures defined as particular instances of a generic deployment types D t . We consider a set of primitives Ω(D t ) to update and/or access the deployment as well as a logic L(D t ) to express constraints on it. In particular, we will use the primitive attach to associate a component instance to a node of the map. the triple (B, H, D) consists of motif meta-variables, that is, typed symbols used to denote respectively the set of component instances, the map and the deployment of component instances on the map, -IR is a set of motif interaction rules of the form (Z, Ψ , P I , G I , F I ) where Z is a set of rule parameters, Ψ is a rule constraint, and (P I , G I , F I ) is the interaction specification, namely the set of ports of involved components, the guard and the data transfer, -RR is a set of motif reconfiguration rules of the form (Z, Ψ , G R , Z L , A R ) where as before Z is a set of rule parameters, Ψ is a rule constraint, G R is a reconfiguration guard, Z L are local rule parameters, and A R is a (sequence of) reconfiguration action(s).

The motif configuration is defined by a valuation of meta-variables B, H, D as respectively B, H, D where (i) B is a finite set of components instances with types belonging to the predefined set of component types, (ii) H is a map instance of the type of H, (iii) D is a deployment instance of the type of D which associates component instances from B to nodes of the map, formally D : B → dom(H) ∪ {⊥}.

The meaning of the rules is explained in the next subsections. Note that motif configuration can dynamically change as the meta-variables are being updated in reconfiguration rules. Furthermore, component instances can interact as dictated by interaction rules. Overall, we tacitly restrict to syntactically consistent motif definitions, that is, where the interaction and reconfiguration rules are restricted to use only the map and deployment primitives defined for the types of H and D respectively. Moreover, we consider that our Ring motif type contains one interaction rule denoted as sync-ring-inout for defining interactions and three reconfiguration rules denoted respectively do-ring-init, do-ring-insert and do-ringremove for dynamic reconfiguration, as follows: For the sake of readability, we use the generic textual syntax of rules proposed in section 2. This textual representation is actually a readable alternative for the abstract representation introduced in Def. 1. The relation between the two representations will be clarified in the following subsections.

sync-ring-inout(x 1 , x 2 : C) ≡ when D(x 1 ) → D(x 2 ) sync x 1 .out x 2 .in true → x 2 .u := x 1 .v do-ring-init() ≡ when B = ∅ do x 1 := B.create(C,

Rule parameters and constraints

The motif evolution is defined by interaction and reconfiguration rules. The set of rule parameters Z include typed symbols denoting (sets of) component instances or map nodes and interpreted as (subsets) elements of B or dom(H) respectively. Rule constraints Ψ are boolean combinations of map, deployment and basic constraints built using parameters in Z and meta-variables B, H, D:

Ψ ::= ψ 0 | ψ H | ψ D | Ψ 1 ∧ Ψ 2 | ¬Ψ
In the above, Ψ 0 denotes any basic constraint using equality and/or set constraints on parameters, Ψ H denotes a constraint on the map (conforming to the map logic L(H t ), for H t being the type of H) and Ψ D denotes a constraint on the deployment (conforming to the deployment logic L(D t ), for D t being the type of D). For example, the sync-ring-inout interaction rule in Example 8 has two parameters x 1 , x 2 denoting components of type C. The rule constraint D(x 1 ) → D(x 2 ) checks if x 1 and x 2 are deployed on adjacent nodes on the map, using the → predicate defined for cycle graphs.

For fixed motif configuration in terms of B, H, D, for given interpretation ζ of parameters, the constraint satisfaction B, H, D, ζ |= Ψ is defined recursively on the structure of Ψ as follows: The symbols x, X are rule parameters denoting respectively component instances or sets of component instances. Moreover, p is a component port, v is a component (exported) data variable and op d (resp. op d ) are operations on (resp. sets of) data values. A rule is syntactically well-formed iff all parameter names used in expressions (part of the guard or data transfer) are also used as part of the interacting port specification. That is, only data from components participating in the interaction can be used.

B, H, D, ζ |= ψ 0 iff ζ ∪ [B/B, H/H, D/D] |= ψ 0 B, H, D, ζ |= ψ H iff H, ζ ∪ [B/B, D/D] |= ψ H B, H, D, ζ |= ψ D iff D, ζ ∪ [B/B, H/H] |= ψ D B, H, D, ζ |= Ψ 1 ∧ Ψ 2 iff B,
For given B, H and D in a motif, the set of multiparty interactions Γ (r) corresponding to an interaction rule r = (Z, Ψ, P I , G I , F I ) is defined as:

Γ (r) =        (P a , G a , F a ) B, H, D, ζ |= Ψ P a = ζ(P I ), G a = ζ(G I ), F a = ζ(F I ) (P a , G a , F a ) is well formed       
In the above, we tacitly lift the interpretation of ζ to port interactions P I , guards G I and actions A I which are all constructed from rule parameters Z. The resulting triple P a , G a , F a is considered well formed iff it conforms to the definition of multiparty interactions, namely if P a does not contain replicated or multiple ports of the same components, as well as if G a and F a use and update only variables exported on ports in P a .

Example 9 (interaction rules) The ring motif type presented in Example 8 has a unique interaction rule denoted sync-ring-inout. The rule connects the out port of a component x 1 to the in port of the component

v).

The set of all defined interactions, for all interpretations of rule parameters satisfying the rule constraint, is depicted in Fig. 6.

Reconfiguration rules

Reconfiguration rules are used to define actions impacting the content / organization of the motif. These actions essentially include creating/deleting component instances, updating the map structure and/or the deployment of component instances to the map. They are expressed as specific updates on the corresponding B, H, D meta-variables. For enhanced expressiveness, reconfiguration rules might use additional local parameters (that is, the local context Z L ) with arbitrary types (component instances, map nodes, maps, deployments, etc). The local context is updated using standard assignments. As mentioned already, we tacitly restrict to syntactically correct rules, that is, where primitive operations conform to the types of the different symbols used, including meta-variables as well as rule parameters.

The syntax of reconfiguration guards and actions is as follows:

guard: G R ::= G I action: A R ::= x := B.create(B t , q) | B.delete(x) | z := H.update H (e R , • • • e R ) | z := D.update D (e R , • • • e R ) | z := e R | A R , A R expression: e R ::= z | B | H | D | op(e R , • • • e R )
That is, guards are the same as for interaction rules and define constraints on components data. In the definition of reconfiguration actions, the symbol x denotes a rule parameter interpreted as component instance, z denotes an arbitrary local rule parameter. The intuitive meaning of reconfiguration actions is as follows. The action x := B.create(B t , q) denotes the creation of a new component instance of type B t . The newly created instance is x and is added to the set of components instances B. The parameter q denotes the initial state for the instance. The action B.delete(x) denotes the deletion of the component x from the motif, that is, the removal of the component instance x from the set B. The action z := H.update H (...) denotes an update of the map according to a primitive operation update H from Ω(H t ), for H t being the type of H. Whenever an extra-value is returned by the primitive, it can be (optionally) assigned to the local parameter z. If no extra-value is returned, the assignment to z is omitted. Similarly, the action z := D.update D (...) denotes an update of the deployment according to a primitive operation update D from Ω(D t ), for D t being the type of D. Finally, the action z := e R denotes an update of a rule parameter z according to the expression e R . Expressions are constructed from rule parameters z and meta-variables B, H, D using a set of predefined operations op, with given interpretation.

Formally, the semantics [[A R ]] of a reconfiguration

action A R is defined as a function 2 updating the motif configuration (B, H, D), the set of component configurations (b) and the parameter interpretation (ζ):

[[x := B.create(B t , q)]](B, H, D, b, ζ) = (B ∪ {b}, H, D , b , ζ ) where b = (B t , k) fresh, D = D[b → ⊥], b = b[b → q], ζ = ζ[x → b] [[B.delete(x)]](B, H, D, b, ζ) = (B \ {b}, H, D |B\{b} , b, ζ) where b = ζ(x) ∈ B [[z := H.update H (e 1 , • • • e n )]](B, H, D, b, ζ) = (B, H , D |H , b, ζ ) where H , v = H.update H (ζ(e 1 ), • • • ζ(e n )), ζ = ζ[z → v ] [[z := D.update D (e 1 , • • • e m )]](B, H, D, b, ζ) = (B, H, D , b, ζ ) where D , v = D.update D (ζ(e 1 ), • • • ζ(e m )), ζ = ζ[z → v ] [[z := e]](B, H, D, b, ζ) = (B, H, D, b, ζ[z → ζ(e)]) [[A R1 , A R2 ]](B, H, D, b, ζ) = ([[A R2 ]] • [[A R1 ]])(B,

Operational semantics

The semantics of component composition within a motif involve two categories of atomic interleaved steps, namely, interaction steps and reconfiguration steps. An interaction step corresponds to the execution of an interaction (as in BIP) from a set of interactions defined by the interaction rules. Reconfiguration steps correspond to the execution of a reconfiguration rule. Formally, the operational semantics of a motif type M t = ((B, H, D), IR, RR) is defined as the labeled

Γ = ∪ r∈IR Γ (r) Γ (B) : b α -→ b M t : (B, H, D, b) α -→ I (B, H, D, b ) (Mot-R) (Z, Ψ, G R , Z L , A R ) ∈ RR B, H, D, ζ |= Ψ (ζ(G R ))(b) = true [[A R ]](B, H, D, b, ζ) = (B , H , D , b , ζ ) M t : (B, H, D, b) ρ -→ R (B , H , D , b )
The rule (Mot-I) says that the motif executes a multiparty interaction α and change the configurations of components instances from b to b iff (1) α belongs to the set of valid interactions Γ defined from the interaction rules (that is, according to the operational semantics in the static case presented earlier in section 3) and (2) a valid step labeled by α is indeed allowed between b and b according to the component-based semantics. The rule (Mot-R) says that the motif executes a reconfiguration if (1) some reconfiguration rule is enabled at the current motif configuration, when both its constraint Ψ and guard G R are satisfied for the given interpretation of parameter ζ and configurations of component instances b and (2) the current and next motif configuration are related according to the semantics of the action A R . The dichotomy between interaction and reconfiguration steps ensures separation of concerns for execution within a motif as previously discussed in section 2 and illustrated in Fig. 5.

Motif-based Systems

We consider systems defined as finite collection of motif instances, with predefined types, and sharing a finite set of component instances. In such systems, every motif can evolve independently of the others, depending on its internal structure and associated rules. In addition, several motifs can also synchronize altogether and perform a joint reconfiguration over the system.

Two ways of coordination between motifs are therefore possible: implicit coordination, by means of shared components and explicit coordination, by means of inter-motif reconfiguration rules.

This section introduces formally inter-motif reconfiguration and defines the operational semantics of motif-based systems. Henceforth we consider a given finite set of motif types. As for components, a motif instance m is a couple (M t , k) for some motif type M t and k ∈ N.

Inter-motif reconfiguration rules

The rules for inter-motif reconfiguration allow joint reconfiguration of several motif instances. In addition to the application of local reconfiguration actions, these rules allow two additional types of actions, respectively creation and deletion of motif instances, and exchanging component instances between motifs.

Inter-motif reconfiguration rules are defined as tuples (Z , Ψ , G , Z L , A R ) similar to local reconfiguration rules. The set of rule parameter Z might include additional symbols denoting motif instances (y). The constraints Ψ * are defined by the grammar:

Ψ * ::= Ψ 0 * | y : Ψ | Ψ * 1 ∧ Ψ * 2 | ¬Ψ *
In the above, Ψ 0 * denotes some basic equality and/or set constraint expressed on context parameters, y : Ψ denotes a local constraint Ψ to be checked in the context of the motif instance y. These constraints are evaluated on motif configurations extended with context parameters. Motif configurations are tuples (M, m) where M is a set of motif instances and m = m → (B, H, D) | m ∈ M provides the structure of these instances in terms of behavior, map and deployment. The constraints are evaluated as follows:

M, m, ζ |= Ψ 0 * iff ζ m |= Ψ 0 * M, m, ζ |= y : Ψ iff B, H, D, ζ m |= Ψ where m → (B, H, D) ∈ m, ζ(y) = m M, m, ζ |= Ψ * 1 ∧ Ψ * 2 iff M, m, ζ |= Ψ * 1 and M, m, ζ |= Ψ * 2 M, m, ζ |= ¬Ψ * iff M, m, ζ |= Ψ *
In the above, ζ m denotes an extended context, including valuations for all meta-variables B, H, D accessed using parameters y of ζ: where

ζ m = ζ ∪ y.B → B, y.H → H, y.D → D | ζ(y) = m, m → (B,
m = ζ(y) ∈ M, m → (B 1 , H, D) ∈ m, ζ(x) → b ∈ B, m = m[m → (B 1 ∪ {b}, H, D[b → ⊥])] [[ y : A R ]](M, m, B, b, ζ) = (M, m , B , b , ζ ) where m = ζ(y) ∈ M, m → (B 1 , H, D) ∈ m, [[A R ]](B 1 , H, D, b, ζ) = (B 1 , H , D , b , ζ ), m = m[m → (B 1 , H , D )], B = B ∪ B 1 [[z := e]](M, m, B, b, ζ) = (M, m, B, b, ζ[z → ζ m (e)]) [[A * R1 , A * R2 ]](M, m, B, b, ζ) = ([[A * R2 ]] • [[A * R1 ]])(M, m, B, b, ζ)
In The rule allows merging two ring motif instances y 1 , y 2 into a single one, whenever their sets of component instances are disjoint and altogether their number does not exceed 10. The new motif is created by taking the union of component instances, the union of deployments and the merging of the two underlying cyclic maps. The original motifs y 1 and y 2 are deleted.

Operational semantics

A motif-based system S is defined as a tuple ((B t i ) i , (M t j ) j , RR * )) consisting of a set of component types (B t i ) i , a set of motif types (M t j ) j and a set of intermotif reconfiguration rules RR * .

A motif-based system evolves either by executing interactions and/or reconfiguration within any of the motifs, or by executing some inter-motif reconfiguration. Formally, the semantics of motif-based systems S is defined as the labeled transition system [[S]] = (Q, Σ, -→) where:

-the set Q of system configuration contains tuples (M, m, B, b) where M = {m 1 , m 2 , ...} is a set of motif instances, m = m j → (B j , H j , D j ) | m j ∈ M, B j ⊆ B
m j → (B j , H j , D j ) ∈ m M t j : (B j , H j , D j , b j ) α -→ I (B j , H j , D j , b j ) b = b[B j → b j ] S : (M, m, B, b) α -→ I (M, m, B, b ) (M-R1) m j → (B j , H j , D j ) ∈ m M t j : (B j , H j , D j , b j ) ρ -→ R (B j , H j , D j , b j ) m = m[(B j , H j , D j )/m j ] B = B ∪ B j b = b[b j /B j ] S : (M, m, B, b) ρ -→ R (M, m , B , b ) (M-R2) (Z * , Ψ * , G * , Z * L , A * R ) ∈ RR * M, m, ζ |= Ψ * (ζ(G * ))(b) = true [[A * R ]](M, m, B, b, ζ) = (M , m , B , b , ζ ) S : (M, m, B, b) ρ * --→ R (M , m , B , b )
Rules (M-I) and (M-R1) lift the transitions (steps) allowed within the motifs at the level of the system, respectively for interactions and reconfigurations. The rule (M-R2) handles inter-motif reconfiguration. These transitions are allowed if (1) some inter-motif reconfiguration rule is enabled and ( 2) the current and next system configurations are related by the semantics of A * R .

Implementation and Experiments

We have developed a prototype implementation of DR-BIP including a concrete language to describe motifbased systems and an interpreter (implemented in Java) for the operational semantics. The language provides syntactic constructs for describing component and motif types, with some restrictions on the maps and deployments allowed 3 . The interpreter allows the computation of enabled interactions and (inter-motif) reconfiguration rules on system configurations, and their execution according to predefined policies (interactive, random, etc). The DR-BIP prototype can be retrieved from [START_REF] Verimag | DR-BIP Prototype[END_REF].

We have effectively used DR-BIP for programming reconfigurable systems in different application domains [START_REF] Ballouli | Four exercises in programming dynamic reconfigurable systems: Methodology and solution in DR-BIP[END_REF]. We provide tentative solutions using the DR-BIP formalism and evaluate their performance at executing dynamically changing configurations.

Dynamic Multicore Task System

A multicore task system consists of a fixed n × n grid of interconnected homogeneous cores, each executing a finite number of tasks. Every task is either running or completed; running tasks may execute on the associated cores and get eventually completed. The load of a core is defined as the number of its associated tasks, both running and completed. A multicore task system is dynamic if the overall number of tasks and their allocation to cores may change over time. More specifically, new running tasks may enter the system at the core c 11 and completed tasks may be withdrawn from the system at the core c nn . Moreover, any task is allowed to migrate from its core to any of the neighboring cores (left, right, top or bottom) in the grid, provided the load of the receiving core is smaller than the load of the departing core minus some constant (K). Fig. 8 presents the overall structure of the motifbased system for four cores. We distinguish two types of atomic components, namely Task and Core. Multiple cores are interconnected together in a motif of type Processor. The interconnecting topology reflects the platform architecture (e.g., a 2 × 2 grid in the figure) and is enforced using a similar grid-like map and deployment. An additional CoreTask motif type is used to represent every core with its assigned tasks.

The interactions in the system are defined within the CoreTask motif. The execution of a task by the core and the task completion are represented by the rules: sync-coretask-exec(x 1 : Core, x 2 : Task) ≡ sync x 1 .work x 2 .exec sync-coretask-fin(x : Task) ≡ sync x.fin

The migration of a task from one core to another is modeled using an inter-motif reconfiguration rule which involves three distinct motifs. A task x 3 migrates from motif y 1 (of type CoreTask) to motif y 2 (of type Core-Task) if the core x 1 of y 1 is connected to the core x 2 of y 2 (according to the processor motif Processor) and if the number of tasks in y 1 exceeds the number of tasks in y 2 by constant K: do-migrate(y 1 , y 2 : CoreTask, y 3 : Processor,

x 1 , x 2 : Core, x 3 : Task) ≡ when y 1 : x 1 ∈ B and y 2 : x 2 ∈ B and y 3 : D(x 1 ) → D(x 2 ) and |y 1 .B| > |y 2 .B| + K and

x 3 ∈ y 1 .B do y 2 .B.migrate(x 3 ), y 1 : B.delete(x 3 )
To simplify notations in reconfiguration rules, we rely henceforth on sandwiching constraints / actions with angle brackets to specify the scope. For example y 1 : Fig. 9: Task load across 3000 steps Fig. 9 illustrates the execution of the dynamic multicore task system with 3 × 3 cores for 3000 steps. Each core is initialized with a random load between 1 and 20. The constant K is set to 3, hence tasks are allowed to migrate to neighboring cores (left, right, top or bottom) that differ in task load by at least 3 tasks. The cores c 11 , and c 33 are used to respectively create new tasks and withdraw completed tasks. These two cores retain the maximum and minimum load. As tasks migrate, the task load of cores converges and balances along the execution having at most a difference of 3 tasks between neighboring cores. For example, in core c 21 the task load increased from 6 to 14. As expected the cores (c 21 , and c 12 ) closest to c 11 maintain a high load and as we move away from c 11 the core's load gradually decreases. This highlights the task migration process cascading from the top left core to the bottom right core. Fig. 10 illustrates the evolution of the dynamic multicore task system for different initial configurations. We vary the number of cores in the processor from 4 to 36 cores. Each core is initialized with a random load as discussed above. The system initial size varies between 46 and 482 component instances as depicted in the figure. Each configuration is simulated for 1000 random steps. As the number of cores increases in size the execution time increases reaching a maximum of 7.3 seconds. The motif instance count remains constant across each configuration, however the component instance count varies as tasks are being created and deleted once completed. Also note that the average ratio of executed interactions vs reconfigurations is 0.7, since the task load converges to a similar value across cores and less task migrations (i.e. reconfigurations) are required. Fig. 10: Dynamic multicore task system measurements -the x-axis indicates the number of motifs in the initial configuration (i.e. n 2 + 1 for n = 2, 3, 4, 5, 6). The meaning of y-axis is indicated at the top

x 1 ∈ B is a constraint stating that x 1 is a component instance in motif y 1 .

Autonomous Highway Traffic System

This exercise is inspired from autonomous traffic systems for automated highways [START_REF] Bergenhem | Approaches for facilities layer protocols for platooning[END_REF]. The system consists of a single-lane one-way road where an arbitrary number of autonomous homogeneous self-driving cars are moving in the same direction, at different cruising speeds. Cars are organized into platoons, i.e. groups of cars cruising at the same speed and closely following a leader car. Platoons may dynamically merge or split. A merge takes place if two platoons are close enough, i.e. the distance between the tail car of the first platoon and the leader car of the second is smaller than some constant K. After the merge, the speed of the new platoon is set to the speed of the first platoon. A platoon may split when an arbitrary car requests to leave the platoon e.g., in order to perform some specific maneuver. After the split, the leading platoon will increase its speed by 2% whereas the tail platoon will reduce its speed by 2%. The Road motif type contains all cars without additional structuring. The Platoon motif type is structured as a chain of cars. The map of the platoon motif is a (dynamic) linear graph of locations and the deployment assigns a single car to every position of the map. The Road motif defines a single interaction by the rule sync-road-move, which synchronizes the move ports of all cars and therefore performing a joint update of their positions. The Platoon motif defines several interactions by the rules sync-platoon-speed and sync-platoon-split. The first rule synchronizes the speed of the leading car with the speed of all follower cars. The second rule allows any follower car to initiate a split maneuver and become a leader in a newly created platoon. sync-road-move(X : Car) ≡ when X = B sync X.move sync-platoon-speed(x : Car, X : Car) ≡ when X = B \ x and D(x) = head(H) sync x.setSpeed X.getSpeed true → X.v := x.v sync-platoon-split(x 1 , x 2 : Car) ≡ when D(x 1 ) = head(H) and Note that we use specific map primitives head, and tail which point respectively to the position of the leader and tail of a platoon, namely the beginning and the end of the list. Furthermore, we use the primitive append which appends and links two maps of type linked list together. Finally, primitives sublist 1,2 extract sublists from a linked list, respectively ending before / starting at the node given as argument. The primitive extract computes a restricted deployment for component instances attached to a subset of nodes of the map. Fig. 12 illustrates the evolution of the system involving 200 cars along 2000 sampled steps. Each line describes a configuration of the system. We show 13 sampled nonconsecutive configurations. A thin black rectangle represents a platoon. Its length is proportional to the number of cars contained. Its position in the line corresponds to its position on the road. For reference, we show the evolution of a particular car by highlighting it in yellow. Initially, all the cars belong to the same platoon. As the system evolves the initial platoon splits into several platoons, which then keep splitting/merging back, etc. Fig. 12: Automated highway traffic evolution along few steps Fig. 13 summarizes the execution of several initial configurations. We evaluate the performance and track the system evolution while varying the number of cars in the initial platoon from 200 to 600 cars. Each configuration is simulated for 3000 random steps. Notice that the component instance count remains constant across each configuration as cars only rearrange within different platoons. However the motif instance count varies as platoons merge/split. Finally, execution time increases reaching a maximum of 5 minutes and the average ratio of executed interactions vs reconfigurations is 0.77. This exercise is inspired by swarm robotics [START_REF] Nouyan | Teamwork in self-organized robot colonies[END_REF]. A number of identical robots are randomly deployed on a field and have a mission to locate an object (the prey) and to bring it near another object (the nest). The robots know neither the position of the nest nor the position of the prey. They have limited communication and sensing capabilities, i.e. they can display a status (by turning on/off some colored leds) and can observe each other as long as they are physically close in the field. We consider hereafter the swarm algorithm proposed in [START_REF] Nouyan | Teamwork in self-organized robot colonies[END_REF]. In a first phase, the robots self-organize into an exploration path starting at the nest. The first robot detecting the nest initiates the path, i.e. stops moving and displays a specific (on-path) status. Any robot that detects (robots on) the path, begins moving along the path towards its tail, explores a bit further its neighborhood and gets connected as well (i.e. becomes the new tail, stops moving and displays the on-path status). Two cases may occur, either no new robot gets connected to the path within some delay, hence the tail robot disconnects and moves randomly (away from the path), or the tail robot detects the prey and the second phase starts. The path stays in place while additional robots converge near the prey. When enough robots have converged, they start pushing the prey along the path towards the nest. The path gets consumed, and the system will stop when the prey gets close enough to the nest.

x 1 = x 2 sync x 1 .ack split x 2 .split
We model the first phase of the algorithm above using three different types of components and three different types of motifs as illustrated in Fig. 14. The Arena motif contains all the robots, the nest and the prey component instances. No map and deployment are used as no specific architecture is enforced by this motif. This motif defines a global tick interaction used to model the synchronous passage of time within the system. Whenever the tick interaction is triggered the robots update their positions, i.e. they move on the field. For every robot, its Neighborhood motif is used to represent its visibility range, i.e the set of robots physically close to it in the field. This motif uses a star-like location map. The inner robot is deployed at the center and the visible neighbors on the leaves. The motif defines a set of binary observe status interactions which are used by the inner robot to collect all the available information from its neighbors. Finally, the Chain motif represents the exploration chain linking robots to the nest. It uses a linear map to deploy the robots belonging to the chain. This motif defines a set of binary next prev interactions which are used to communicate along the chain.

For this example, reconfiguration is used to redefine the content of the Neigborhood and Chain motifs. For the former, as robots are moving in the field, they continuously enter or leave the visibility range of other robots. We use two inter-motif reconfiguration rules to update the neighborhood information: do-neighborhood-enter(y 1 : Neighborhood, y 2 : Arena,

x 1 , x 2 : Robot) ≡ when y 1 : D(x 1 ) = center(H) and ¬(x 2 ∈ B) and

y 2 : x 2 ∈ B do dist(x 1 .pos, x 2 .pos) ≤ R min → y 1 .B.

Lessons learned

Although very preliminary, these experiments allowed us to draw some conclusions and identify potential lines for improvement:

-Arbitrarily complex interaction and/or architectural reconfiguration patterns are usually decomposable as a super-position of motifs, which moreover, use relatively restricted forms of maps and addressing functions. No example required a map topology different than the ones mentioned so far (chain, cycle, star).

-While DR-BIP semantics leaves unspecified the choice of next rule to be executed between multiple interaction and reconfiguration rules, some control mechanism is needed to restrict non-determinism and enforce a desirable scenario. For instance, giving high priority to specific reconfiguration rules may enforce atomicity on a long reconfiguration sequence by avoiding interference with execution of interactions (e.g., for migrating a task to some final executing core). In contrast, giving higher priority to interaction rules may be useful when reconfiguration is triggered by external events and will take place only when the system reaches some stable state (e.g., for constraining the insertion of new tasks in the task system).

-The handling of time is very rudimentary. Actually, synchronous time progress is modeled using a multiparty interaction rule involving all timed components in a global motif. For example, all cars are synchronized for making their move action in the Road motif, similarly, all robots are synchronized in the Arena motif, etc. Whereas semantically correct, this representation is cumbersome and shall be improved by using clock variables like in Real-Time BIP [START_REF] Abdellatif | Modelbased implementation of real-time applications[END_REF] and an implicit semantics of time allowing to separate time-dependent system evolution from functional (interaction, reconfiguration) behavior.

-Going beyond toy examples would require a new implementation of DR-BIP concepts integrating a fullfledged representation of component types (e.g., as in BIP or Real-Time BIP) as well as richer types of maps and of addressing functions (e.g., defined as abstract data types in some implementation language). This is needed for building detailed models, that could be used both for analysis with simulation-based techniques or for concrete implementation and deployment as part of real systems.

Related Work

There exists a significant number of frameworks dealing with dynamic software and system architectures. We recommend [START_REF] Bradbury | A survey of self-management in dynamic software architecture specifications[END_REF][START_REF] Butting | A classification of dynamic reconfiguration in component and connector architecture description[END_REF] for exhaustive surveys and classification of existing approaches and [START_REF] Garlan | Software architecture: a travelogue[END_REF][START_REF] Malavolta | What industry needs from architectural languages: A survey[END_REF] for an overview of current and foreseen design challenges. In this section, we restrict ourselves to formal frameworks dealing with an explicit notion of architecture in terms of components and connectors and providing primitives to express architectural reconfigurations. In particular, we do not consider general-purpose programming languages or domain specific languages.

We distinguish between frameworks for specification or for programming architectural reconfiguration. In the first category, we include frameworks based on temporal logics such as [START_REF] Aguirre | A temporal logic approach to the specification of reconfigurable component-based systems[END_REF][START_REF] Dormoy | Using temporal logic for dynamic reconfigurations of components[END_REF], hybrid logics such as [START_REF] Sanchez | On the verification of architectural reconfigurations[END_REF] or extended configuration logics such as dream [START_REF] De Nicola | DReAM: Dynamic reconfigurable architecture modeling[END_REF]. These frameworks allow characterizing reconfiguration from the perspective of an external observer. Nonetheless, they do not provide support for implementation of reconfiguration within the system.

The DR-BIP framework is part of the second category dealing with explicit programming of reconfiguration within the system. Most of the reconfigurable ADL frameworks belong to this category. Usually, they can be classified according to the underlying formalism for programming reconfiguration and/or defining their operational semantics e.g., based on process algebra such as π-ADL [START_REF] Cavalcante | Supporting dynamic software architectures: From architectural description to implementation[END_REF], montiarc [START_REF] Heim | Retrofitting controlled dynamic reconfiguration into the architecture description language MontiArcAutomaton[END_REF], pilar [START_REF] Quintero | Dynamic coordination architecture through the use of reflection[END_REF], darwin [START_REF] Magee | Dynamic structure in software architectures[END_REF]; using graph rewriting rules such as [START_REF] Métayer | Software architecture styles as graph grammars[END_REF], [START_REF] Taentzer | Dynamic change management by distributed graph transformation: Towards configurable distributed systems[END_REF]; using chemical reaction rules such as cham [START_REF] Wermelinger | Towards a chemical model for software architecture reconfiguration[END_REF]; using specific rules such as gerel [START_REF] Endler | Programming generic dynamic reconfigurations for distributed applications[END_REF], c2sadel [START_REF] Medvidovic | A language and environment for architecture-based software development and evolution[END_REF], rapide [START_REF] Luckham | Specification and analysis of system architecture using Rapide[END_REF] to cite only a few. According to this classification, the reconfiguration rules of DR-BIP are a specific class of graph rewriting rules allowing to change the architecture seen as a hyper-graph of interconnected BIP components. Our originality lies in the use of maps and addressing functions to express reconfiguration constraints and to organize the different types of rewriting rules as reconfiguration and interaction rules.

The distinction between exogeneous and endogeneous reconfiguration is another criteria for the classification of existing approaches. Frameworks such as leda [START_REF] Canal | Specification and refinement of dynamic software architectures[END_REF] are endogenoeus as they allow to freely use reconfiguration primitives e.g., to create and remove components and connectors, as regular actions of components. π-adl [START_REF] Cavalcante | Supporting dynamic software architectures: From architectural description to implementation[END_REF] allows for both endogeneous (within components) and exogeneous (within subsystems) reconfiguration. Nevertheless, most frameworks are exogeneous and try to isolate as best as possible reconfiguration from applicative component behavior. For example, mode-based reconfiguration in montiarc [START_REF] Heim | Retrofitting controlled dynamic reconfiguration into the architecture description language MontiArcAutomaton[END_REF], aadl-slim [START_REF] Cimatti | Model-based run-time synthesis of architectural configurations for adaptive MILS systems[END_REF] or graph-rewriting rules in [START_REF] Métayer | Software architecture styles as graph grammars[END_REF] are both examples of exogeneous reconfiguration. It is also the case of DR-BIP where reconfiguration and interaction rules are kept fully separated from the behavior of components.

Finally, let us briefly discuss the positioning of DR-BIP in the BIP landscape. The BIP framework introduced in [START_REF] Basu | Modeling heterogeneous real-time components in BIP[END_REF] and the big majority of its descendants including Real-Time BIP [START_REF] Abdellatif | Modelbased implementation of real-time applications[END_REF], Distributed Send/Receive BIP [START_REF] Bonakdarpour | A framework for automated distributed implementation of component-based models[END_REF], Stochastic Real-Time BIP [START_REF] Nouri | Performance evaluation of stochastic real-time systems with the SBIP framework[END_REF], etc, are restricted to static architectures, that is, with a fixed number of components and fixed connectors. The different variants consider specific models for components, semantics of time, specific forms of interaction, etc. The first extension towards dynamic reconfigurable systems has been Dy-BIP [START_REF] Bozga | Modeling dynamic architectures using Dy-BIP[END_REF] allowing for changes on the connecting topology, whereas the set of components remain fixed. Later on, fully reconfigurable extensions have been studied in relation with specific implementations on some host languages. For example, the Functional-BIP [START_REF] Edelmann | Functional BIP: embedding connectors in functional programming languages[END_REF] allows for implementation in functional languages whereas Java-BIP [START_REF] Mavridou | Coordination of dynamic software components with Jav-aBIP[END_REF] has been developed to support concrete use of BIP concepts in relation with industrial Java-based software platforms. With DR-BIP we try to re-unify these different dynamic variants behind a unique high-level framework, independent of target host languages and/or application domains to provide a common platform for analysis and implementation of dynamically reconfigurable systems.

Discussion

The DR-BIP framework for programming dynamic reconfigurable systems has been designed to encompass three complementary structuring aspects of componentbased coordination. Architecture motifs are environments where live instances of components of predefined types subject to specific parametric interaction and reconfiguration rules. Reconfiguration within a motif supports in addition to creation/deletion of components, the dynamic change of maps and the mobility of components. Maps are a common reference structure that proves to be very useful for both the parametrization of interactions and the mobility of components. It is important to note that a map can have either a purely logical interpretation, or a geographical one or a combination of both. For instance, a purely logical map is needed to describe the functional organization of the coordination in a ring or a pipeline. To describe mobility rules of cars on a highway a map is needed representing at some abstraction level their external environment e.g. the structure of the highway with fixed and mobile obstacles. Finally a map with both logical and geographic connectivity relations may be used for cars on a highway to express their coordination rules. These depend not only on the physical environment but also on the communication features available.

Structuring a system as a set of loosely coordinated motifs confers the advantage that when components are created or migrate, we do not need to specify associated coordination rules; depending on their type, components are subject to predefined coordination rules of motifs. Clearly these results are too recent and there are many open avenues to be explored. One is how we make sure that the modeled systems meet given properties. The proposed structuring principle allows a separation of concerns between interaction and reconfiguration aspects. To verify correctness of the parametric interacting system of a motif we can extend the approach adopted for static BIP: assuming that dynamic connectors correctly enforce the sought coordination, it remains to show that restricting the behavior of deadlockfree components does not introduce deadlocks. We have recently shown this approach can be extended for parametric systems [START_REF] Bozga | Checking deadlock-freedom of parametric component-based systems[END_REF].

To verify the correctness of reconfiguration operations a different approach can be taken. If we have already proven correctness of the parametric interacting system of a motif, it is enough to prove that its architecture style is preserved by statements changing the number of components, move components and modify maps and their connectivity. In other words the architecture style is an invariant of the coordination struc-ture. This can be proven by structural induction. The architecture style of a motif can be characterized by a formula of configuration logic φ [START_REF] Mavridou | Configuration logics: Modeling architecture styles[END_REF]. We have to prove that if a model m of the system satisfies φ then after the application of a reconfiguration operation the resulting model m satisfies φ.

Fig. 1 .Fig. 2 :

 12 Fig. 1. Maps are arbitrary graph-like structures consisting of interconnected positions. Deployments relate components to positions on the map.

Fig. 3 :

 3 Fig. 3: Motif-based System Concept

  b

Fig. 5 :

 5 Fig. 5: Reconfiguration vs Interaction Steps

Fig. 6 :

 6 Fig. 6: Component types, interactions and systems in BIP

  Given a deployment D : B → dom(H) ∪ {⊥}, for a subset of components B ⊆ B we denote by D |B the restriction of D to B , that is, the partial function D B : B → dom(H) ∪ {⊥} where D |B (b) = D(b) for all b ∈ B . Similarly, for an arbitrary map H we denote by D |H the restriction of D to H , that is, the partial function D |H : B → dom(H ) ∪ {⊥} where D |H (b) = D(b) if D(b) ∈ dom(H) ∩ dom(H ) and ⊥ otherwise.

4. 2

 2 Motif typesHenceforth we consider a given finite collection of component types, map types and deployment types.Definition 1 A motif type M t is a tuple ((B, H, D), IR, RR) where:

Example 8 (

 8 dynamic token ring motif type) Fig.7illustrates the structure of a Ring motif type defined for the dynamic token ring system. In any configuration, the behaviour B contains several component instances, all of the same type C presented in Example 4. The map H is a cycle graph (or equivalently, a circular linked list) with specific primitives presented in Example 7. The deployment D assigns components to locations of the map in a bijective manner.

Fig. 7 :

 7 Fig. 7: A configuration of the dynamic token ring motif type

  H, D, ζ |= Ψ 1 and B, H, D, ζ |= Ψ 2 B, H, D, ζ |= ¬Ψ iff B, H, D, ζ |= Ψ That means, equalities and/or set constraints are evaluated in the usual way on the context ζ extended with the current valuation for meta-variables B, H, D. Map constraints are evaluated as defined by their underlying logic L(H t ) on the map H and the context ζ extended with the valuation for meta-variables B, D. The evaluation of deployment constraints is similar.4.4 Interactions rules Interaction rules are used to define multiparty interactions on the components instances within the motif. The syntax of the interaction specification part is as follows: ports: P I ::= x.p | X.p | P I P I guard: G I ::= true | e I | G I ∧ G I | ¬G I action: F I ::= | x.v := e I | X.v := e I | a I , a I expression: e I ::= x.v | op d (e I , • • • e I ) | op d (X.v)

x 2

 2 deployed next to it on the map. Consider the motif configuration depicted in Fig. 7. The interpretation of rule parameters ζ = {x 1 → b 3 , x 2 → b 4 } satisfies the rule constraint and therefore defines the binary interaction (P a , G a , F a ) where P a = {b 3 .out, b 4 .in}, G a = true, F a = (b 4 .u := b 3 .

  H, D, b, ζ) In the above, for an expression e we denoted by ζ(e) its valuation given the interpretation ζ of rule parameters and the implicit assignment of meta-variables (B → B, H → H, D → D). Example 10 (reconfiguration rules) The ring motif type introduced in Example 8 contains three reconfiguration rules. The rule do-ring-init initializes the motif with a ring of two components. The rule do-ring-create creates a new component in the ring. The rule do-ringremove(x:C) removes an idle component x from the ring, provided it contains more than three components.

  transition system [[M t ]] = (Q, Σ, -→) where the states of set Q correspond to motif configurations B, H, D consistently extended with configurations for all component instances b = b → q | b ∈ B, q ∈ states(b) , 2 up to the choice of fresh component instance the labels of Σ correspond to valid interactions α constructed on components and an additional reconfiguration action label ρ, the transitions -

  H, D) ∈ m Inter-motif reconfiguration guards and actions are defined by the following grammar: guard: G R ::= G I action: A R ::= y := M.create(M t , (e R , e R , e R )) | M.delete(y) | y.B.migrate(x) | y: A R | z := e R | A R , A R expression: e * R ::= z | y.B | y.H | y.D | op(e R , • • • , e R )That is, guards are the same as for interaction rules. For inter-motif reconfiguration actions, we use the M symbol to refer the current set of existing motif instances. Also, the y symbol denotes a rule parameter interpreted as motif instance, and z a rule parameter of arbitrary type. The action y := M.create( M t , (e B , e H , e D )) denotes the creation of a new motif instance y of type M t , with initial structure defined by the valuation of e B , e H , e D . The action M.delete(y) denotes the deletion of the motif instance y, that is, its removal from the set of motif instances. The action y.B.migrate(x) denotes the insertion of an existing component instance x within the set of component instances of the motif y. Finally, the action y : A R denotes any local reconfiguration action A R to be executed in the context of the motif instance y and z := e R an assignment of expression e R to a local rule parameter z. As for intra-motif reconfiguration rules, expressions e R are constructed from rule parameters z and meta-variables B, H, D associated to motif instances y, using a set of available primitives op. Formally, the semantics [[A * R ]] of inter-motif reconfiguration actions is defined as a function updating motif configurations (M, m), component configurations (B, b) and context parameters (ζ), as follows: [[y := M.create(M t , (e B , e H , e D ))]](M, m, B, b, ζ) = (M ∪ {m}, m , B, b, ζ ) where m = (M t , k) fresh, m = m ∪ m → (ζ m (e B ), ζ m (e H ), ζ m (e D )) , ζ = ζ[y → m] [[M.delete(y)]](M, m, B, b, ζ) = (M \ {m}, m |M \{m} , B, b, ζ) where m = ζ(y) ∈ M [[y.B.migrate(x)]](M, m, B, b, ζ) = (M, m , B, b, ζ)

  are the motif configurations, B is the set of components instances, and b = b → q | b ∈ B, q ∈ states(b) are the component configurations, the set of labels Σ correspond to valid interactions α on component instances, a local reconfiguration action label ρ and an inter-motif reconfiguration action label ρ * , the set of transitions -R * correspond to execution of respectively multiparty interactions as defined by interaction rules (-→ I ), local reconfiguration as defined by local reconfiguration rules (-→

Fig. 8 :

 8 Fig. 8: Multicore Task System

Fig. 11

 11 Fig. 11 illustrates the motif-based system in DR-BIP. We use a component type Car to model the behavior of a car. Each car maintains its position pos and speed v. The position pos is updated on the move transition. Transitions setSpeed and ack split are used by leader cars only to respectively define the platoon speed and acknowledge a platoon split. Similarly, transitions getSpeed and split are used by follower cars only to respectively synchronize on the leader speed and initiate a platoon split.

Fig. 11 :

 11 Fig. 11: Automated Highway Traffic System

  Two reconfiguration rules do-platoon-merge and do-platoon-split handle the merging and the splitting of platoons respectively: do-platoon-merge(y 1 , y 2 : Platoon, x 1 , x 2 : Car) ≡ when y 1 : D(x 1 ) = tail(H) andy 2 : D(x 2 ) = head(H) do abs(x 1 .pos -x 2 .pos) < K → z B := union(y 1 .B,y 2 .B), z H := append(y 2 .H, y 1 .H), z D := union(y 1 .D, y 2 .D), M.create(Platoon, (z B , z H , z D )), M.delete(y 1 ), M.delete(y 2 ) do-platoon-split(y : Platoon, x : Car) ≡ do y : n := D(x), z H1 := sublist 1 (H, n), z D1 := extract(D, z H1 ), z B1 := components(z D1 ), z H2 := sublist 2 (H, n), z D2 := extract(D, z H2 ), z B2 := components(z D2 ) , M.create(Platoon, (z B1 , z H1 , z D1 )), M.create(Platoon, (z B2 , z H2 , z D2 )) , M.delete(y)

Fig. 13 :

 13 Fig. 13: Measurements on automated highway traffic systems

Fig. 14 :

 14 Fig. 14: Self-organizing robot colonies

  the above, for an expression e we denoted by ζ m (e) its valuation in the extended context ζ m . , y 2 : Ring) ≡ when y 1 .B ∩ y 2 .B = ∅ and |y 1 .B| + |y 2 .B| ≤ 10 do z B := union(y 1 .B, y 2 .B), z

	Example 11 (inter-motif reconfiguration rule) Consider
	an inter-motif reconfiguration rule for two ring motifs:
	do-ring-merge(y 1

H := merge-cycle(y 1 .H, y 2 .H), z D := union(y 1 .D, y 2 .D), M.create(Ring, (z B , z H , z D )), M.delete(y 1 ), M.delete(y 2 )

  1 , x 2 : Robot) ≡ when y 1 : D(x 1 ) = center(H) and x 2 ∈ B andx 1 = x 2 and do dist(x 1 .pos, x 2 .pos) ≥ R max → y 1 : n := D(x 2 ), B.delete(x 2 ), H.remove(n)The rules above describe the reconfiguration allowing any robot x 2 to enter (resp. leave) the neighborhood y 1 of any different robot x 1 whenever the distance between x 1 and x 2 is smaller than R min (resp. greater than R max ). The evolution of the chain is also described by reconfiguration. At any time, the tail can disconnect or a robot can connect if it is close enough to the tail.do-chain-connect(y 1 : Chain, y 2 : Neighborhood, x 1 , x 2 : Robot) ≡ when y 1 : D(x 1 ) = tail(H) and x 2 ∈ B and y 2 : D(x 1 ) = center(H) and x 2 ∈ B do y 1 .B.migrate(x 2 ), y

migrate(x 2 ), y 1 : n := H.extend(), D.attach(x 2 ,n) do-neighborhood-leave(y 1 : Neighborhood, x 1 : n := H.extend(), D.attach(x 2 ,n) do-chain-disconnect(y 1 : Chain, x 1 : Robot) ≡ when y 1 : D(x 1 ) = tail(H) do x 1 .timeout → y 1 : n := D(x 1 ), B.delete(x 1 ), H.remove(n)

maps are restricted to simple graphs e.g., chain, cycle, star

The research leading to these results has received funding from the European Union Horizon 2020 research and innovation programme under grant agreement no. 700665 CITADEL (Critical Infrastructure Protection using Adaptive MILS)


Firooz Tabkhi

Azzaro-Pantel Catherine

Pibouleau Luc

Serge Domenech

Modelling of gas pipeline networks: impact of hydrogen injection in natural gas infrastructures

Keywords: Gas pipeline networks, Compressor station, Hydrogen, Mathematical Programming

Confronting more and m ore u rgent t oday's en vironmental chal lenges, suc h as t he co ntrol o f t he discharges o f t he ga s wi th greenhouse ef fect, and facing with t he e ver-increasing shortage i n t he fossil resources, t he radi cal chan ges i n ener gy pol icies seem now i nevitable. Am ong t he various domains, hydrogen is one o f the most energy alternatives full of pr omise. Preliminary studies have shown that the transport of a mixture of natural gas and hydrogen is possible without modification of the network and perturbs little the flui d m echanics constrai nts of th e syste m as long as t he m ass fraction of hydrogen remains sufficiently low. This work in terested ex clusively in th e transmissio n pipeline o f hydrogen gas a nd m ore exact ly i n t he adaptation of th e current transmission networks of th e natural gas to its tran sport. The study is ai med to develop a m athematical model for su ch transmission networks. The quantitative estimation and analysis of the maximal hydrogen c ontents that are a cceptable in t he transported gas passing t hrough the e xisting infrastructures of the natural gas distribution are proposed in this paper. The optimization procedure has been i mplemented by m eans o f a nonlinear p rogramming m ethod i nvolving t he C ONOPT res olution module within the General Algebraic Modelling System (GAMS) environment. Some typical results are then presented and discussed.

Introduction

In a world where en ergy d emand is growing at unprecedented rates, pipelines will con tinue to play an important role in safely an d efficiently transporting oil and gas from often remote areas to their markets. Hydrogen is foreseen as an important and reliable ener gy carrier in the future sustainable energy society. This energy vector, which can be p roduced from different primary sources among which the renewable energies, is exploitable in different stationary or portable applications. Thorough technical and economic studies on the whole energy chain including production, storage, transport, distribution and utilization are the first steps to provide new industrial perspectives. The addition of hydrogen to the natural gas modifies its transport and calorific properties [START_REF] Schouten | Effect of H 2 -injection on the thermodynamic and t ransportation properties of natural gas[END_REF]. Besides, a gas wi th high-content hydrogen can have an im pact on the safety of t he transmissiondistribution-utilization ch ain, th e d urability an d th e reliab ility o f th e g as p ipeline and th e u tilization performances for the end user. The transitio n to wards th e situation in wh ich h ydrogen b ecomes an important en ergy carrier needs decades but worl dwide great efforts are made in the field of hydrogen production, delivery, storage and utilization. In this view, an analysis of the potential of using the actual natural gas pipeline system for the delivery of hydrogen is a valid argument. Defining the conditions under which hydrogen can be added to natural gas constitutes a first step of this investigation. The chemical and physical properties of hydrogen and natural gas differ significantly, which may have an effect on safety related to gas transport and use as well as on the integrity of the network.

Gaseous hydrogen can be transported using several modes like pipeline, railroad, tanker truck, and tanker ship. The chosen method depends on the distance of transportation, the production method, the use etc. Regarding t ransportation of h ydrogen, al ong wi th con ventional m eans, t ransportation vi a pi pelines ha s been employed to cater for a specific range of m ass consuming users. The cu rrent aggregated length of pipelines fo r hydrogen tr ansport th at ar e known to be either in servi ce, under construction, o r un der planning reaches almost 2000 km. Of course, the idea of i njecting hydrogen into gas pipelines to satisfy the increased demand for energy will req uire chan ges in th e natu ral g as p ipeline in frastructure in th e fo rm o f en hanced reliab ility o f th e existing system, as well as the development of new pipeline infrastructure. Some authors have examined hydrogen transport by pipeline and a few reports discuss the use of existing natural gas pipelines to transport hydrogen or hydrogen-natural gas blends. Among the recent works, the influence of hydrogen on the pressure drop in the pipelines has been calculated by [START_REF] Schouten | Effect of H 2 -injection on the thermodynamic and t ransportation properties of natural gas[END_REF]. In (Parker, 2004), the construction costs of natural gas transmission pipelines have been analyzed and the impact of hydrogen in the global cost has been studied. From an economic viewpoint, the cost of natural gas pipelines is a funct ion of pipe diameter and t he cost of a hy drogen pipeline can be 50%-80% higher than that of a natural gas pipeline of the same size [START_REF] Veziroglu | Emerging Technology Series, Hydrogen Energy Technologies[END_REF]. Regional transportation costs could be as m uch as five times higher than natural gas, primarily because of the lower volumetric energy density of hydrogen [START_REF] Kirk-Othmer | Encyclopaedia of C hemical Technology, Pipeli nes[END_REF]. Besides, hydrogen embrittlement of the steel under the high pressures environment of hydrogen constitutes a major concern: consequently, the transportation of a hydrogen-rich g as requ ires a g reat attention since h ydrogen em brittlement is ch aracterized by a loss of ductility of a steel (Sherif et al., 2005). This paper is devoted to the modelling of gas pipeline networks and to the influence of hydrogen injection in natural gas infrastructures. This paper has not the ambition to give an answer to all questions that may arise, b ut m ay hel p t o a pproach t he potential chal lenges of t he e xploitation o f hy drogen as an e nergy carrier using current pipeline systems. The possibility of low am ounts of hydrogen injection into natural gas pipelines will be analysed from a process engineering viewpoint.

Governing equations

A mathematical modelling of the gas transportation problem in networks is presented here. The model is general enough to take i nto account various gases. As abovementioned, the case of mixtures of natural gas an d hy drogen, t he so -called hy thane i s part icularly exam ined here . The p ressure dr op i n a ga s pipeline, i.e., the essential parameter to determine the required compression power for the transmission is derived f rom t he differential m omentum bal ance. Friction between fluid boundary l ayer an d i nterior surface of the tube induces energy losses and, consequently, reduces the gas pressure. The material balance and the equations of momentum conservation on the basic elements of the network as well as the other governing e quations c onstitute the modelling c ore. The necessary equations in t he system of the gas transmission network in order to determine the dynamic conditions such as pressure and flow rat e are devel oped. F irst of al l, t he momentum balance f or a si ngle pi peline i s gi ven. The formulation related to a co mpressor is p resented. Th en, t he associate d incide nce m atrix is deduce d to facilitate the transmission network design.

Gas pipeline hydraulics

The governing equation to calculate the pressure at each point of a straight pipe can be derived as follows:

0 = ) ( + 2 + 2 2 v ρ dx d v ρ D f dx dP (1 )
This relationship is obtained from the one di mensional momentum balance around a c ylindrical control volume in steady state. Th e Darcy fr iction f actor, f, i s a di mensionless val ue t hat i s a fu nction o f t he Reynolds num ber, Re, and relativ e ro ughness o f th e pipeline, ε/D (Darcy friction fact or is num erically equal to four times of the Fanning friction factor that is preferred by some engineers).

Let us mention that the SI system of units is used. In turbulent flow, the wall roughness is often a limiting factor as compared with the Reynolds number Re to find out the value of the friction factor. In of fshore gas pi pelines, fo r example, where Re h as an ord er o f mag nitude o f 1 3000, the wall roughness will strongly influence the pipeline pressure drop. In such pipelines, it is a c ommon practice to apply coating on pi pe walls t o reduce wall ro ughness and p ressure drop ( Sletfjerding a nd Gudmundsson, 2 003).

Another example concerns flow around merchant ships where the viscous drag dominates the resistance, and the wall roughness has a significant influence on drag [START_REF] Grigson | Drag losses of new ships caused by hull finish[END_REF]. Since the flow is considered fully devel oped he re, t he friction fact or i s est imated t hrough t he eq uation de duced by v on Karman [START_REF] Romeo | Im proved expl icit equat ions f or est imation of t he fri ction factor in rough and smooth pipes[END_REF]:

2 - ) 71 . 3 / log 2 - ( = D ε f (2 )
The relation between gas density and p ressure is represented by Equation ( 3) and mass flow rate (pipe throughput) can be used as a function of average gas velocity using Equation ( 4):

ZRT PM ρ = (3) v D ρ m 2 7854 . 0 = & (4)
Considering E quations ( 3) a nd ( 4), t he m omentum bal ance i n t erms o f p ressure an d throughput ca n be written with the following equation:

0 = ) ( 16 + 8 + 4 2 2 5 2 2 P ZT dx d MD π m R P MD π m fZRT dx dP & & (5 )
By integrating the differential Equation ( 5) between the points i and j, the following equation is obtained and will be used in the numerical formulations. By assu ming that temperature and compressibility factor are constant between the points i and j, the following expression can be deduced:

0 = 16 + ln 32 - - 5 2 2 4 2 2 2 2 M D π L m fZRT P P MD π m ZRT P P j i j i & & (6 )
This pressure/flow rel ationship e xhibits a hi gh degree of nonlinearity. It e valuates th e pressure dr op corresponding to a gi ven flow magnitude and direction. This equation is used t o estimate the pipeline's pressure profile and ca n incorporate the pressure head that occurs due to the location of the pipeline via the elevation changes. Although the compressibility factor can be calculated using an equation of state, it is estimated here from an empirical equation proposed for simulation goals in the literature [START_REF] Mohring | Automated model reduction of c omplex gas pi peline net works, 3 6 th An nual Meet ing of Pip eline Si mulation In terest Group[END_REF]. This factor is a fu nction of the critical properties of t he gas mixture, average pressure of the pipe segment and the temperature that have been considered constant:

c ij c P P T T RT ρ PM Z ) 533 . 0 - 257 . 0 ( + 1 = = (7 )
Average pressure is calculated from two end pressures (Equation 8):

) + - + ( 3 2 = j i j i j i ij P P P P P P P (8 )

Maximum admissible operational pressure

The pressure at all points of the equipment should be less than maximum admissible operational pressure (MAOP) which i s a desi gn param eter i n the pi peline en gineering. T his up per l imit is cal culated us ing Equation ( 9) which linked it with the so-called specified minimum yield strength (SMYS):

t D t SMYS f f f MAOP T E F - . . . . 2 = (9 )
SMYS is a mechanical property of e quipment const ruction m aterial. The fact ors f F , f E, f T re present respectively the design, seam joint factor and temperature deration factor, respectively. The design factor is usually 0.72 for cross-country gas pipelines, but can be as low as 0.4, depending on class location and type of construction. The class lo cations, in turn, depend on the population density in the v icinity of the the n atural g as is calcu lated fo r different en ergetic cap acities o f th e pip eline. On e of th e con sidered optimization cri terion i s bas ed o n t he m inimization of f uel con sumption i n t he c ompressor st ations.

Another st andpoint i s t he est imation o f t he m aximal capaci ty of t he pi peline i n v arious cases. The procedure o f o ptimization i s implemented by means of a no nlinear p rogramming method by usi ng t he module of resolution CONOPT withi n the environment GAMS. Let us recall that GAMS was designed upon th e prin ciples of relational d atabase t heory an d m athematical p rogramming m ethods. Relatio nal database t heory provides a structure d fra mework f or devel oping general dat a organization a nd transformation capabilities (Brooke et al., 2004). GAMS creates nonlinear models that will be solved with the CONOPT module, which is a NLP algorithm. GAMS/CONOPT is well-suited for models with very nonlinear co nstraints, w hich is t he case i n our w ork. C ONOPT uses S equential Li near Pr ogramming (SLP) and Sequential Quadratic Programming (SQP) algorithms [START_REF] Drud | GAMS: The Solver Manuals, CONPT[END_REF]. The approach is illustrated here by typical results obtained on several examples of applications.

Studied pipeline network

The considered pipeline network consists of three long pipelines of 100 kilometers. There is a compressor station bet ween these two pipelines. T hese stations operate to com pensate fo r pres sure dr op in the transportation system. Each compressor station includes three parallel centrifugal compressors. This case study is shown in Figure 1. In each station, there are six pipelines of about one hundred meters linked to the entrances and outlets of the compressors. The specification of the pipelines of this system is proposed in Table 1.

Fuel minimization and power maximization for a reference case (% H 2 = 0)

The first o ptimization p roblem is th e m inimization o f th e to tal rate o f fu el co nsumption in two compressor st ations si multaneously. The pressure i s c onsidered t o be equal t o 60 bars at the entrance point of the network and the lower bound of the delivery pressure is assumed to bet set at 60 bars too. The composition of natural gas is considered as follows: respectively 70, 25 and 5 m olar percent of methane, ethane and propane. The computed mass percentage of the input gas that will be consumed in the stations is equal to 0.496. The transm itted power of the pi peline (that is the product of the pipeline delivery throughput and the lower heating value of t he natural gas) is equal to 3313 M W at this optimum point. Another example is the maximization of the transm itted power in the sam e pressure conditions as above. The result of this problem is given by the pipeline capacity at these end point pressures, which is equal to 4323 MW. At this m aximum pi peline t hroughput, 0.98 percent s of t he suppl y gas are burnt i n t he furnaces of the pressure stations. The results of these two problem s corresponded to the tip points of the curve in Figure 2. The curve in this figure represents the results of t he fuel consumption minimization problem at several fixed transm itted power of the pipeline system along with the results of the maximization problem of the transm itted power thr ough the pipeline system . In the latter problem, the fuel consumption has been kept const ant i n t he form of a const raint. The opt imal Paret o front of t he problem is presented in Figure 2 [START_REF] Dedieu | Design and retrofit of multiobjective batch plants via a multicriteria genetic algorithm[END_REF].

Optimization problems in the presence of hydrogen

In this section, the gas running through the pipeline network is assumed to be a mixture of hydrogen and natural gas. The composition is the same as the reference problem presented above. Different operational conditions such as del ivery pressure or hy drogen fraction in hythane can be c onsidered as the objective function. The same structure of the network and specifications as those mentioned in Figure 1 and Table 1 are used.

Initially, the am ount of hydrogen that can be adde d to natural gas is m aximized. Here, the supply pressures of the network as well as the lower bound of the delivery pressure are considered to be equal to 50 bars. The results of this optimization probl em are present ed i n Fi gure 3. The m aximum am ount of added h ydrogen is p resented in m ass an d v olume p ercent versus transmitted power. Each computation point is o btained b y co nsidering th e p ower tran smitted b y th e p ipeline as a co nstant v ia a co nstraint introduced in the optimization procedure. The object ive funct ion i s t he m ass fract ion of hy drogen i n hythane. It i s necessary t o say t hat bey ond t he t ip poi nt of the curves presented in Figure 2 and 3, the optimization procedure falls into an infeasible solution. According to Figure 3, for this studied network, the maximum achievable fraction of hydrogen that can be added to natural gas is around 6 mass percents. Only some quantitative results are shown in Figures 4 and5 and corre spond to a supply pressure of 60 bars. In Figure 4, each point corresponds to a hydrogen m ass fraction in hythane considered as constant via a const raint and t he optimization procedure has been performed by taking the supply pressure as t he objective function. The transm itted power correspondi ng to each delivery pre ssure of the pipeline network is shown in Figure 5 as well. Accordi ng t o Fi gures 4 and 5, for pure hy drogen t ransport, optimum delivery pressure will be 59.7 bars and the transmitted power at this pressure is only 387 MW . This am ount is extrem ely lower th an the transm itted power of the pipeline for natural gas without hydrogen which is 3900 MW at this supply pressure.

Conclusions

A m athematical m odelling f ramework f or gas pipeline networks w as proposed in th is stud y. A m ajor interest of t his wo rk i s t o t ake i nto acc ount t he am ount o f hy drogen t hat can be ad ded t o t he pi peline network traditionally devoted to the transportation of natural gas without any modification in the system. Defining the conditions under which hydrogen can be added to natural gas constitutes a key point of this investigation.

Several operat ional variables were selected as deci sion v ariables of gas pipeline o ptimization problem. Optimization pr ocedures i ncluding f uel co nsumption m inimization, ad ded hydrogen, t ransmitted powe r and delivery pressure m aximization were perf ormed for di fferent ga s mixtures o f nat ural ga s and hydrogen using CONOPT/GAMS. It has been shown that the maximum achievable fraction of hydrogen that can be add ed to natural gas is arou nd 6 mass percent. Addition of hydrogen to natural gas decreases the transm itted p ower sign ificantly. Acco rding t o th is st udy, an ada ptation of t he c urrent networks of transmission of natural gas to the transport of hydrogen seems to be possible until this limit.

List of symbols

Figure 1 .

 1 Figure 1. Schema of the considered pipeline network in the case study

Figure 2 .

 2 Figure 2. Pareto optimal front corresponding to fuel minimization and transmitted power maximization

Figure 4 .

 4 Figure 4. Optimized supply pressure versus added hydrogen to natural gas for a supply pressure of 60 bars

Table 1 .

 1 Specification of the pipelines of the system

	Pipeline tag	G1 G2		G3	G4 G5
	Diameter (m)	0.787 0.889		0.330	0.381 0.330
	Length (m)	1E+5	1E+5	200	300	100
	Pipeline tag	G6	G7	G8	G9	G10
	Diameter (m)	0.330 0.330		0.330	0.381 0.330
	Length (m)	200 100		200	100 100
	Pipeline tag	G11 G12		G13	G14 G15
	Diameter (m)	0.432 0.330		0.330	0.330 0.838
	Length (m)	100	100	400	100	1E+5

* corresponding authors: Firooz.Tabkhi@ensiacet.fr, Catherine.Azzaropantel@ensiacet.fr