Hajar Ait Addi

Christian Bessiere

Redouane Ezzahir
email: r.ezzahir@uiz.ac.ma

Nadjib Lazaar
email: lazaar@lirmm.fr

Time-bounded Query Generator for Constraint Acquisition

QUACQ is a constraint acquisition algorithm that assists a non-expert user to model her problem as a constraint network. QUACQ generates queries as examples to be classified as positive or negative. One of the drawbacks of QUACQ is that generating queries can be time-consuming. In this paper we present TQ-GEN, a time-bounded query generator. TQ-GEN is able to generate a query in a bounded amount of time. We rewrite QUACQ to incorporate the TQ-GEN generator. This leads to a new algorithm called T-QUACQ. We propose several strategies to make T-QUACQ efficient. Our experimental analysis shows that thanks to the use of TQ-GEN, T-QUACQ dramatically improves the basic QUACQ in terms of time consumption, and sometimes also in terms of number of queries.

Introduction

Constraint programming (CP) has made considerable progress over the last forty years, becoming a powerful paradigm for modeling and solving combinatorial problems. However, modeling a problem as a constraint network still remains a challenging task that requires some expertise in the field. Several constraint acquisition systems have been introduced to support the uptake of constraint technology by non-experts. Freuder and Wallace proposed the matchmaker agent [START_REF] Freuder | Suggestion strategies for constraint-based matchmaker agents[END_REF]. This agent interacts with the user while solving her problem. The user explains why she considers a proposed solution as a wrong one. Lallouet et al. proposed a system based on inductive logic programming with the use of the structure of the problem as a background knowledge [START_REF] Lallouet | On learning constraint problems[END_REF]. Beldiceanu and Simonis have proposed MODELSEEKER, a system devoted to problems with regular structures and based on the global constraint catalog [START_REF] Beldiceanu | A model seeker: Extracting global constraint models from positive examples[END_REF]. Bessiere et al. proposed CONACQ, which generates membership queries (i.e., complete examples) to be classified by the user [START_REF] Bessiere | Query-driven constraint acquisition[END_REF][START_REF] Bessiere | Constraint acquisition. Artificial Intelligence p[END_REF]. Shchekotykhin and Friedrich have extended CONACQ to allow the user to provide arguments as constraints to speed-up the convergence [START_REF] Shchekotykhin | Argumentation based constraint acquisition[END_REF].

Bessiere et al. proposed QUACQ (for Quick Acquisition), an active learning system that is able to ask the user to classify partial queries [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF][START_REF] Bessiere | New approaches to constraint acquisition[END_REF]. QUACQ iteratively computes membership queries. If the user says yes, QUACQ reduces the search space by discarding all constraints violated by the positive example. When the answer is no, QUACQ finds the scope of one of the violated constraints of the target network in a number of queries logarithmic in the size of the example. This key component of QUACQ allows it to always converge on the target set of constraints in a polynomial number of queries. Arcangioli et al. have proposed the MULTIACQ system as an attempt to make QUACQ more efficient in practice in terms of number of queries [START_REF] Arcangioli | Multiple constraint acquisition[END_REF]. Instead of finding the scope of one constraint, MULTIACQ reports all the scopes of constraints of the target network violated by the negative example. Despite the good theoretical bound of QUACQ-like approaches in terms of number of queries, generating a membership query is NP-hard. It can then be too time-consuming when interacting with a human user. For instance, QUACQ can take more than 20 minutes to generate a query during the acquisition process of the sudoku constraint network.

In this paper, we introduce TQ-GEN, a time-bounded query generator. TQ-GEN generates queries in an amount of time not exceeding a waiting time upper bound. We incorporate the TQ-GEN generator into the QUACQ algorithm to reduce the time complexity of generating queries. This leads to a new version called T-QUACQ. Our theoretical and experimental analyses show that the bounded waiting time between queries in T-QUACQ is at the risk of reaching a premature convergence state and asking more queries. We then propose strategies to make T-QUACQ efficient. We experimentally evaluate the benefit of these strategies on several benchmark problems. The results show that T-QUACQ combined with a good strategy dramatically improves QUACQ not only in terms of time needed to generate queries but also in number of queries, while achieving the convergence state in most cases.

The rest of this paper is organized as follows. Section 2 presents the necessary background on constraint acquisition. Section 3 presents the algorithm TQ-GEN for time-bounded query generation. Section 4 describes how we use TQ-GEN in QUACQ to get the T-QUACQ algorithm. Section 5 analyzes the correctness of the algorithm. Experimental results and strategies to make T-QUACQ efficient are reported in Section 6. Section 7 concludes the paper

Background

The constraint acquisition process can be seen as an interplay between the user and the learner. User and learner need to share a vocabulary to communicate. We suppose this vocabulary is a set of n variables X = {x 1 , . . . ,x n } and a domain D = {D(x 1 ), . . . , D(x n )}, where D(x i ) ⊂ Z is the finite set of values for x i . A constraint c Y is defined by a sequence Y of variables of X, called the constraint scope, and the relation c over D of arity |Y |. An assignment e Y on a set of variables Y ⊆ X violates a constraint c Z (or e Y is rejected by c Z ) if Z ⊆ Y and the projection e Z of e Y on the variables in Z is not in c. A constraint network is a set C of constraints on the vocabulary (X,D). An assignment on X is a solution of C if and only if it does not violate any constraint in C. sol(C) represents the set of solutions of C.

In addition to the vocabulary, the learner owns a language Γ of relations, from which it can build constraints on specified sets of variables. Adapting terms from machine learning, the constraint bias, denoted by B, is a set of constraints built from the constraint language Γ on the vocabulary (X,D), from which the learner builds the constraint network. We denote by B[Y ] the set of all constraints c Z in B, where Z ⊆ Y . The target network is a network C T such that for any example e ∈ D X = Π xi∈X D(x i ), e is a solution of C T if and only if e is a solution of the problem that the user has in mind.

A membership query ASK(e) is a classification question asked to the user, where e is a complete assignment in D X . The answer to ASK(e) is yes if and only if e ∈ sol(C T ). A partial query ASK(e Y ), with Y ⊆ X, is a classification question asked to the user, where e Y is a partial assignment in We say that the learning process reached a premature convergence if only (1) is guaranteed. If there does not exist any C L ⊆ B such that C L agrees with E, we say that we have collapsed. This can happen when C T ⊆ B.

D Y = Π xi∈Y D(x i ).
We finally define the class of biases that are good for a given time limit, that is, those biases on which bounding the query generation time does not hurt.

Definition 1 (τ -good). Given a bias B on a vocabulary (X,D), given the maximum arity k of a constraint in B, and given τ a time limit, B is τ -good on (X,D) if and only if ∀Y ⊂ X such that |Y | = k, ∀C i ,C j ⊂ B[Y ], finding an assignment e on Y such that e ∈ sol(C i ) \ sol(C j ), or proving that none exists, takes less than τ .

Time-bounded Query Generation

To be able to exhibit its nice complexity in number of queries, QUACQ must be able to generate non redundant queries. A query is non redundant if, whatever the user's answer, it allows us to reduce the learner's version space (i.e., the subset of 2 B currently agreeing with all already classified examples). In the context of QUACQ, a query ASK(e) is non redundant if e does not violate any constraint in the currently learned network C L , and it violates at least one constraint of the current bias B in which we look for the missing constraints (i.e., κ B (e) = ∅), We denote such an example e by e |= (C L ∧ ¬B). QUACQ has to solve an NP-hard problem to generate a non redundant query. Therefore, the user can be asked to wait a long time from a query to another.

We propose TQ-GEN, a query generator able to generate a query in a bounded amount of time (time bound). We will see later that this bounded time is at the risk of reaching premature convergence and/or asking more queries than necessary. The Algorithm 1: TQ-GEN

[Y ]∧¬B[Y ]), for some set Y ⊆ X.

Description of TQ-GEN

The algorithm TQ-GEN (see Algorithm 1) takes as input the set of variables X, a reduction factor α ∈ ]0,1[, a solving timeout τ , a time limit to generate a query time bound, an expected query size , a current bias of constraints B, and a current learned network C L . We start by initializing the counter time of the time TQ-GEN has already consumed in its main loop. In line 5, we set τ so that the next execution of the main loop cannot exceed time bound. In line 7, we choose a subset Y of size . To be able to generate a non redundant query on Y , it is required that B[Y ] is not empty. To guarantee that such an Y exists, we need to never be smaller than the smallest arity in B (line 6). In line 8, TQ-GEN tries to generate a query on Y of size in a time less than τ . If such a query is found in less than τ , we return it in line 9. Otherwise, either

C L [Y ] ∧ ¬B[Y ] is unsatisfiable and τ is sufficient to prove it, or C L [Y ] ∧ ¬B[Y ] is too hard to be solved in τ . If C L [Y ] ∧ ¬B[Y ] is unsatisfiable, the constraints in B[Y ]
are redundant to C L and they can be removed from B (line 12). These constraints have to be put in C L to avoid generating later a query violating one of these redundant constraints, but they are useless in terms of the set of solutions represented by C L . They can safely be removed from C L at the end of the learning process.

If C L [Y ] ∧ ¬B[Y ]
is too hard, we reduce the expected query size with a factor α (line 13). In line 14, the time spent to try to generate a query is recorded in order to ensure that TQ-GEN will never exceed the allocated time time bound (see line 4). The last attempt shall not exceed the remaining time (i.e., time boundtime) (line 5). In this section, we present T-QUACQ (Algorithm 2), an integration of TQ-GEN into QUACQ. T-QUACQ differs from the basic version presented in [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF] at the shaded lines (i.e., lines 2, 4, 7, 10 and 15). 1T-QUACQ initializes the constraint network C L to the empty set (line 1). In line 2, the parameters of TQ-GEN are initialized such that α ∈ ]0..

1[ and ∈ [minArity(B), |X|].

In line 4, we call TQ-GEN to generate a query in bounded time. If no query exists (i.e., B = ∅), then the algorithm reaches a convergence state (line 6). If a query exists and TQ-GEN is not able to return it in the allocated time, T-QUACQ reaches a premature convergence (line 7). Otherwise, we propose the example e to the user, who will answer by yes or no (line 8). If the answer is yes, we can remove from B the set κ B (e) of all constraints in B that reject e (line 9). We can also adjust the expected size of the next query following a given strategy (line 10). This function is discussed later in section 6. [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. If the answer is no, we are sure that e violates at least one constraint of the target network C T . We then act exactly as QUACQ by calling the function FindScope to discover the scope of one of these violated constraints and FindC to select which constraint with the given scope is violated by e (line 12). If a constraint c is returned, we know that it belongs to the target network C T , we then add it to the learned network C L (line 13). If no constraint is returned (line 14), this is a condition for collapsing as we could not find in B a constraint rejecting one of the negative examples. Functions FindScope and FindC are used exactly as they appear in [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. When the answer is no, we can also adjust the expected size of the next query following a given strategy (line 15).

Theoretical Analysis

In this section we analyze the correctness of TQ-GEN and T-QUACQ. The role of TQ-GEN is to return a query that is non redundant with all queries already asked to the user. Proof. If time bound < ∞, it is trivial. Suppose now that B is τ -good on (X,D), time bound = ∞, and TQ-GEN never goes through line 9 (which would terminate TQ-GEN). At each execution of its main loop, TQ-GEN executes either line 12 or line 13. decreases strictly at each execution of line 13. Hence, after a finite number of times, will be less than or equal to the maximum arity in B. As B is τ -good, the cutoff τ will no longer be reached in line 8, and the next executions of the loop will all go through line 12. Thanks to line 6, cannot be less than the smallest arity in B. Thus, the set Y chosen in line 7 is guaranteed to have a non empty B[Y ]. As a result, B strictly decreases in size at each execution of line 12, B will eventually be empty, and TQ-GEN will terminate.

We now show that under some conditions TQ-GEN cannot miss a non redundant query, if one exists. Proof. TQ-GEN finishes by either returning a query in line 9 or nil in line 15. If a query is returned, we are done as TQ-GEN is sound (Proposition 1). Suppose nil is returned in line 15. According to the assumption on time bound and the fact that each execution of the main loop of TQ-GEN takes at most τ seconds, we know that TQ-GEN has enough time to execute |B| + log α ( k n ) times its main loop before returning nil in line 15. In each of these executions, line 12 or line 13 is executed. Each time line 13 is executed, is reduced by multiplying it by the factor α ∈ ]0..1[. As cannot be greater than n when entering TQ-GEN, after log α ( k n ) executions, we are guaranteed that

≤ n • α logα( k n ) ≤ n • k n = k. As B is τ -good,

Experiments

In this section, we experimentally analyze our new algorithms. We first describe the benchmark instances. Second, we evaluate the validity of the time-bounded query generation by comparing a baseline version of T-QUACQ to the QUACQ algorithm. This baseline version allows us to observe the fundamental characteristics of the approach. Based on these observations, we discuss possible strategies and parameter settings that may make our approach more efficient. The only parameter we will keep fixed in all our experiments is time bound, that we set to 1 seconds, as we consider it as an acceptable waiting time for a human user [START_REF] Lallemand | Enhancing user experience during waiting time in hci: Contributions of cognitive psychology[END_REF]. All tests were performed using the Choco solver2 version 4.0.4 with a simulation run time cutoff of 3 hours, 2 Gb of Java VM allowed memory on an Intel(R) Xeon(R) @ 3.40GHz.

Benchmarks

We used four benchmarks from the original QUACQ paper [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF] (Random, Sudoku, Golomb ruler, and Zebra), and two additional ones (Latin square, Graceful graphs). Random. We generated binary random target networks with 50 variables, domains of size 10, and m binary constraints. The binary constraints are selected from the language Γ = {=, =, , , <, >}. We have launched our experiments with m = 12, and m = 122. Sudoku. The sudoku logic puzzle with 9 × 9 grid must be filled with numbers from 1 to 9 in such a way that all the rows, all the columns, and the 9 non overlapping 3 × 3 squares contain the numbers 1 to 9. The target network has 81 variables with domains of size 9, and 810 binary = constraints on rows, columns and squares. We use a bias of 19,440 binary constraints taken from the language Γ = {=, = , , <, >}. Golomb ruler. (prob006 in [START_REF] Jefferson | CSPLib: A problem library for constraints[END_REF]) The problem is to find a ruler where the distance between any two marks is different from that between any other two marks. Golomb ruler is encoded as a target network with n variables corresponding to the n marks. For our experiments, we selected the 8, 12, 16 and 20 marks ruler instances with bias of 660, 3,698, 12,552, and 32,150 constraints, respectively, generated using the language Γ = {= 0 , = 0 , , , < , >, zt xy , zt xy } where = 0 and = 0 respectively denote the unary constraints "equal zero" and "not equal zero", and zt xy and zt xy respectively denote the distance constraints |x -y| = |z -t| and |x -y| = |z -t|. Latin square. A Latin square is an n × n array filled with n different Latin letters, each occurring exactly once in each row and exactly once in each column. We have taken n = 10 and the target network is built with 900 binary = constraints on rows and columns. We use a bias of 29,700 constraints built from the language Γ = {=, =, , , <, >}. Zebra. Lewis Carroll's zebra problem has a single solution. The target network has 25 variables of domain size 5 with 5 cliques of " =" constraints and 14 additional constraints given in the description of the problem. We use a bias of 3,250 unary and binary constraints taken from a language with 20 basic arithmetic and distance constraint. Graceful graphs. (prob053 in [START_REF] Jefferson | CSPLib: A problem library for constraints[END_REF]) A labeling f of the n nodes of a graph with q edges is graceful if f assigns each node a unique label from 0,1, . . . ,q and when each edge (x, y) is labeled with |f (x) -f (y)|, the edge labels are all different. The target network has node-variables x 1 , x 2 , . . . x n , each with domain {0,1, . . . ,q}, and edge-variables e 1 , e 2 , . . . e q , with domain {1, 2, . . . , q}. The constraints are: x i = x j for all pairs of nodes, e i = e j for all pairs of edges, and e k = |x i -x j | if edge e k joins nodes i and j. The constraints of B were built from the language Γ = { = , =, z xy , z xy } where z xy and z xy denote respectively the distance constraints z = |x -y| and z = |x -y|. We used three instances that accept a graceful labeling [START_REF] Petrie | Symmetry breaking in graceful graphs[END_REF]: GG(K 4 × P 2 ), GG(K 5 × P 2 ), and GG(K 4 × P 3 ), whose number of variables is 24, 35, and 38 respectively, and bias size is 12,696, 40,460, and 52,022 respectively. For all our benchmarks, the bias contains all the constraints that can be generated from the relations in the given language. That is, for a commutative relation c (resp. non-commutative relation c ) of arity r, the bias contains all possible constraints c Y (resp. c Y ), where Y is a subset (resp. an ordered subset) of X of size r.

Baseline version of T-QUACQ

The purpose of our first experiment is to validate the approach of time-bounded query generation and to understand the basics of its behavior. We defined a baseline version of T-QUACQ, called T-QUACQ.0, that we compare with QUACQ. T-QUACQ, presented in Algorithm 2, is parameterized with time bound, α, τ and used by function initialize, and what function adjust does.

Once time bound has been fixed, as said above, to 1 seconds, there remains to specify the other parameters and function adjust. In T-QUACQ.0, to remain as close as possible to the original QUACQ, we set to |X| and the function adjust at lines 10 and 15 of Algorithm 2 simply resets to |X|. The impact of the parameters α and τ will be discussed later. For this first comparison between T-QUACQ.0 and QUACQ, we use two CSP instances: sudoku and GG(K 5 × P 2 ). They are good candidates for this analysis because QUACQ can be very time-consuming to generate queries on them.

Table 1 reports the comparison of QUACQ and our baseline version T-QUACQ.0 on the sudoku and GG(K 5 × P 2 ) instances. The performance of T-QUACQ.0 is averaged over ten runs on each instance. In this first experiment, we have arbitrarily set α to 0.5. #q denotes the total number of asked queries, totT denotes the total time of the learning process, #Conv denotes the number of runs of T-QUACQ.0 in which it reached convergence, and %Conv denotes the average of the convergence rate over the ten runs. We estimated the convergence rate by the formula 100.

|C T |-#missingto(C L ) |C T |
, where #missingto(C L ) is the number of constraints that have to be added to the learned network C L to make it equivalent to the target network C T .

From Table 1, we observe that when τ = 5ms, for both instances, T-QUACQ.0 is able to converge on the target network, as QUACQ (obviously) does. The interesting information is that T-QUACQ.0 does this in a total cpu time for generating all queries that is significantly lower than the time needed by QUACQ. QUACQ needs 46 minutes to converge on the instance of sudoku and 52 minutes to converge on the instance of graceful graphs, whereas T-QUACQ.0 converges in 1 minute or less on both instances.

Let us focus a bit more on how the two algorithms spend their time. Figure 1 reports the waiting time from one query to another needed by QUACQ and T-QUACQ.0 to learn GG(K 5 × P 2 ). We selected a fragment of 100 queries near to the end of the learning process for each algorithm. On the one hand, we see that T-QUACQ.0 never exceeds the bound of time bound = 1 second between two queries, thanks to its TQ-GEN time bounded generator. On the other hand, we observe that in these 100 queries close to convergence, generating a query in QUACQ is time consuming because it requires solving a hard CSP. There are three negative queries (that is, queries followed by small queries of FindScope and FindC) requiring from 20 to 50 seconds to be generated, and many positive queries (that is, not followed by small queries) requiring from 20 to 200 seconds to be generated. Once the approach has been validated by this first experiment, we tried to understand the behavior of T-QUACQ.0 when pushing τ to the limits of the range 0..time bound. We instantiated τ to a very small value: 0.001ms, and a very large value, close to time bound: 900ms. Results are reported in Table 1.

When τ takes the large value of 900ms, T-QUACQ.0 fails to converge (the convergence rate is 94% in sudoku, and 41% in GG(K 5 × P 2 )). The explanation is that τ is so close to time bound that if TQ-GEN fails to produce a query of size |X| in 900ms, there remains only 100ms to produce a query of size α • |X|. In case TQ-GEN cannot make it, T-QUACQ.0 returns premature convergence because the time limit has been reached.

When τ takes its small value 0.001ms, T-QUACQ.0 fails to converge (the convergence rate is 1% on both instances). The explanation in this case is that τ is so small that the bias is not τ -good. That is, the solver at line 8 of TQ-GEN fails to terminate even for the smallest sub-problems of two variables. Thus, TQ-GEN will spend time looping through lines 8, 13, and 6 until reaching time bound.

After having tried these extreme values for τ , let us now use Theorem 1 to theoretically determine the values of τ that guarantee convergence. (Remember that α is set to 0.5.) According to Theorem 1, τ must be less than 1/(19440+log 0.5 (2/81)) = 0.05ms on sudoku and less than 1/(40, 460+log 0.5 (3/35)) = 0.0247ms on GG(K 5 ×P 2 ). We launched an experiment with τ = 0.024ms, which meets the theoretical bound for both sudoku and GG(K 5 × P 2 ). The results are reported in Table 1. T-QUACQ.0 converges on sudoku but returns premature convergence on GG(K 5 ×P 2 ) with a convergence rate equal to 93%. On sudoku, the bias is τ -good when τ = 0.024ms, so the two conditions for convergence of Theorem 1 are met. On GG(K 5 × P 2 ), τ = 0.024ms is too small for ensuring τ -goodness because the bias contains ternary constraints. Thus, the first condition for convergence of Theorem 1 is violated and T-QUACQ.0 fails to converge.

Our last observation on Table 1 is related to the number of queries. We consider only the cases where the learning process has converged, that is, sudoku with (α,τ ) = (0.5,0.024) and (α,τ ) = (0.5,5), and GG(K 5 × P 2 ) with (α,τ ) = (0.5,5). We observe that T-QUACQ.0 respectively asks 1%, 4%, and 14% more queries than QUACQ. To understand T-QUACQ.0 asks more queries than QUACQ on GG(K 5 × P 2 ), we launched T-QUACQ.0 with different values of α. (τ is kept fixed to 5ms.) Interestingly, we observed that the number of queries varies significantly with α. For α taking values 0.2, 0.5, and 0.8, T-QUACQ.0 requires respectively, 6,654, 5,610, and 5000 queries to converge. We then measured the size of queries in T-QUACQ.0 with these three values of α. Figure 2 reports the size of queries asked by T-QUACQ.0 to learn GG(K 5 × P 2 ) with α equal to 0.2, 0.5, and 0.8. We make a zoom on the 400th to 450th iterations of T-QUACQ.0. We observe that the larger α, the greater the size of the query returned by TQ-GEN and the smaller the number of queries. When α is small, this often leads to queries of very small size. For α = 0.2, all queries have size α • 35 = 7 (because GG(K 5 × P 2 ) has 35 variables). For α = 0.5, a few queries have size α • 35 = 17 but almost all have size α 2 • 35 = 8. Generating queries of small size can be beneficial at the beginning of the learning process, when queries are often negative, because function FindScope will quickly find the right scope of the missing constraint inside a small subset Y . But at the end of the learning process, when most queries are positive, a short query leads to very few constraints removed from B in line 9 of Algorithm 2. Hence, convergence is slow in terms of number of queries. This is what happened in Table 1 on GG(K 5 × P 2 ) with α = 0.5 and τ = 5ms. These observations led us to propose more flexible ways to adjust the query size during the learning process.

Strategies and Settings

Following our first observations on our baseline version T-QUACQ.0, we expect that there is room for improvement by making the use of the query size less brute-force (reset to |X| after each query generation in T-QUACQ.0). We propose here to adjust it in a more smooth way, to let T-QUACQ concentrate on the size of query that is the most beneficial at a given point of the learning process.

We propose the following adjust function (see Algorithm 3). Given a query generated by TQ-GEN, if the answer is yes, adjust increases by a factor α, and if the answer is no, adjust decreases by a factor α. The intuition behind such adaptation To validate the observations made on graceful graphs, and in order to select the most promising value of τ , we extended our experimentation to Golomb rulers. Golomb rulers have the nice property that the basic model does not only contain binary constraints. It also contains ternary and quaternary constraints, which makes query generation more difficult. We used four instances of Golomb rulers of size n = 8, 12, 16, and 20. We set α to 0.8, and vary τ from 10µs to 1s. We added the value τ = 50ms (that is, log 10 (50ms) = 4.7) inside the interval [10ms, 100ms] as these values were looking the most promising for convergence in our previous experiment. The results of T-QUACQ.1 on those problems are shown in Figure 4, where the x-axis and the y-axis are respectively labeled by log 10 (τ ) in µs, and the problem size n.

We first analyze the impact of τ on the convergence rate. The results in Figure 4 show us that the larger the problem size, the greater the value of τ for convergence. We observe that T-QUACQ.1 converges for no instance at τ = 10µs, 1 instance at 100µs, 2 instances at 1ms, and 3 instances from 50ms to 1s. For n = 20, convergence is never reached, but τ = 10ms and τ = 50ms give the best results. If we combine these results with those obtained on graceful graphs, it leads us to the conclusion that the best value for τ is 50ms. Let us now analyze the impact of τ on the number of queries when T-QUACQ.1 converges. We observe that for all the instances, the number of queries required for convergence is almost the same regardless of the value of τ . In the following we set τ to 50ms.

We finally validate this optimized version of T-QUACQ.1 on other benchmark problems. Table 2 reports the results of QUACQ and of T-QUACQ.1 with the parameters α = 0.8 and τ = 50ms. totT is the total time of the learning process, M T (q) the maximum waiting time between two queries, and #q the total number of asked queries.

The first important observation is that T-QUACQ.1 has converged for all instances presented in Table 2. Second, what we saw with the baseline version T-QUACQ.0 remains true with T-QUACQ.1: Time to generate queries is short, almost always orders of magnitude shorter than with QUACQ. Finally, the good surprise comes from the number of queries. Compared to T-QUACQ.0, the number of queries in T-QUACQ.1 drops significantly thanks to the smooth adjustment of the size of the queries. The number of queries in T-QUACQ.1 is even smaller than the number of queries in QUACQ on all but two instances, despite QUACQ is free to use as much time as it needs to generate a query.

Conclusion

We have proposed TQ-GEN, a query generator that is able to generate a query in a bounded amount of time, and then to satisfy users tolerable waiting time. TQ-GEN is able to adjust the size of the query to generate so that the query can be generated within the time bound. We have also described T-QUACQ, a QUACQ-like algorithm that uses TQ-GEN to generate queries. Our theoretical analysis shows that the bounded waiting time between queries is at the risk of reaching a premature convergence. We have then proposed strategies to better adapt query size. Our experiments have shown that T-QUACQ combined with a good strategy dramatically improves QUACQ in terms of time needed to generate queries and also in number of queries, while still reaching convergence.

  This work was supported by Scholarship No.7587 of the EU METALIC non redundant program.

Algorithm 2 : 5 if e = nil then 6 if 8 if 9 B 12 c

 2568912 T-QUACQ 1 CL ← ∅ ; 2 initialize(α, τ, time bound, ) ; 3 while true do 4 e ← TQ-GEN (α,τ,time bound, ,B,CL) ; B = ∅ then return "convergence on CL" ; 7 return "premature convergence on CL" ; Ask(e) = yes then ← B \ κB(e) ; 10 adjust( , yes) ; 11 else ← FindC(e,FindScope(e,∅,X,f alse)) ; 13 if c = nil then CL ← CL ∪ {c} ; 14 else return "collapse" ; 15 adjust( , no); 4 Using the TQ-GEN Algorithm in QUACQ

Proposition 1 (

 1 Soundness). TQ-GEN is sound. Proof. The only place where TQ-GEN returns a query is line 9. By construction, e Y is an assignment which is solution of C L [Y ] and that violates at least one constraint from B[Y ] (line 8). Thus, κ B (e Y ) = ∅, and by definition e Y is a non redundant query.Proposition 2 (Termination). Given a bias B on the vocabulary (X,D), if time bound < ∞ or if B is τ -good on (X,D), then TQ-GEN terminates.

Proposition 3 (

 3 Completeness). If the bias B is τ -good, and time bound > (|B| + log α ( k n ) ) • τ , with n = |X| and k the maximum arity in B, then TQ-GEN is complete.

Theorem 1 .

 1 TQ-GEN will be able to solve the formula C L [Y ] ∧ ¬B[Y ] in less than τ seconds for all Y , as |Y | = ≤ k. As a result, TQ-GEN has enough time for |B| executions of the loop before reaching the time bound limit. Thanks to line 7, we know that the set Y has a non empty B[Y ]. Thus, line 12 removes at least one constraint from B, and B will be emptied before the time limit. Therefore, we have converged, and there does not exist any non redundant query. If C T ⊆ B, T-QUACQ is guaranteed to reach (premature) convergence. If in addition B is τ -good and time bound > (|B| + log α ( k n ) ) • τ , with n = |X| and k the maximum arity in B, then T-QUACQ converges. Proof. (Sketch.) We first prove premature convergence. Let E be the set of all examples generated during the execution of T-QUACQ and C L be the returned network. If C L does not agree with E this means that there exists e Y ∈ E such that e Y is positive and e Y |= C L , or e Y is negative and e Y |= C L . As FindScope and FindC are sound, we only consider examples classified in line 8 of T-QUACQ. Suppose first that in line 8, e Y is positive (e + Y ). By construction, e Y has been generated by satisfying C L [Y ] (line 4), that is, ∃c Z ∈ C L [Y ] | e Y |= c Z at the time of generating e Y . As line 9 removes from B all constraints rejecting e Y , we are guaranteed that C L agrees with {e + Y } at the end of T-QUACQ. Suppose now that e Y is negative (e - Y ). As C T ⊆ B, FindC returns a constraint c rejecting e Y (line 12) and c is added to C L in line 13. Thus, C L agrees with {e - Y } at the end. We now prove that T-QUACQ converges when B is τ -good and time bound > (|B| + log α ( k n ) ) • τ . By Proposition 3 we know that under this assumption, TQ-GEN always returns a non redundant query if one exists. As a result, TQ-GEN returns nil only when B has been emptied of all its redundant constraints in line 9, which means that T-QUACQ has converged on C L .

Fig. 1 :

 1 Fig. 1: Time to generate queries on GG(K5 × P2) (T-QUACQ.0 versus QUACQ).

Fig. 2 :

 2 Fig. 2: Size of queries generated by TQ-GEN on GG(K5 × P2) with τ = 5ms.

  (a) GG(K4 × P2) (b) GG(K5 × P2)

Fig. 3 :

 3 Fig. 3: Number of queries and convergence rate performed by T-QUACQ.1 on graceful graphs. Darker color in color bar indicates higher number of queries, and the number in each cell of the map indicates the convergence rate.

Fig. 4 :

 4 Fig. 4: Number of queries and convergence rate performed by T-QUACQ.1 on Golomb rulers.

  The answer to ASK(e Y ) is yes if and only if e Y does not violate any constraint in C T . A classified assignment e Y is called a positive or negative example depending on whether ASK(e Y ) is yes or no. For any assignment e Y on Y , κ B (e Y ) denotes the set of all constraints in B rejecting e Y . We now define convergence, which is the constraint acquisition problem we are interested in. We are given a set E of (complete/partial) examples labeled by the user as positive or negative. We say that a constraint network C agrees with E if examples labeled as positive in E do not violate any constraint in C, and examples labeled as negative violate at least one constraint in C. The learning process has converged on the learned network C L ⊆ B if: 1. C L agrees with E, 2. For any other network C ⊆ B agreeing with E, we have sol(C ) = sol(C L ).

  GEN is that instead of looking for an assignment e on X such that e |= (C L ∧¬B), we look for a partial assignment e Y such that e Y |= (C L

	1 In α, τ, time bound: parameters;
	2 InOut : parameter; B: bias; CL: learned network;
	3 time ← 0 ;
	4 while B = ∅ and time < time bound do
	5	τ ← min(τ, time bound -time) ;
	6	← max( , minArity(B)) ;
	7	choose Y ⊆ X s.t. |Y | = ∧ B[Y ] = ∅ ;
	8	eY ← solve(CL[Y ] ∧ ¬B[Y ]) in t < τ ;
	9	if eY = nil then return eY ;
	10	else
	11	if t < τ then
	12	CL ← CL ∪ B[Y ] ; B ← B \ B[Y ] ;
	13	else ← α • ;
	14	time ← time + t ;
	15 return nil ;
	idea behind TQ-

Table 1 :

 1 T-QUACQ.0 versus QUACQ (time bound = 1s) CSP Algorithm (α, τ (in ms)) #q totT (in seconds) #Conv %Conv

		QUACQ	-	9,053	2,810	-100%
			(0.5, 0.001)	12	14	0	1%
	sudoku 9 × 9	T-QUACQ.0	( 0.5, 0.024) 9,132 ( 0.5, 5) 9,612	37 62	10 100% 10 100%
			(0.5, 900) 9,557	41	5	94%
		QUACQ	-	4,898	3,144	-100%
			(0.5, 0.001)	11	62	0	1%
	GG(K5 × P2)	T-QUACQ.0	( 0.5, 0.024) 7,495 ( 0.5, 5) 5,610	56 43	0 10 100% 93%
			(0.5, 900) 1,888	40	0	41%

Table 2 :

 2 T-QUACQ.1 versus QUACQ, α = 0.8, τ = 50ms

	Benchmark	Algorithm	totT	M T (q)	#q
	(|X|, |D|, |C|)		(in seconds) (in seconds)
	Zebra	QUACQ	1.29	0.13	706
	(25, 5, 64)	T-QUACQ.1	1.34	0.11	547
	rand-50-10-12	QUACQ	204	5.01	253
	(50, 10, 12)	T-QUACQ.1	13	0.36	325
	rand-50-10-122	QUACQ	88	1.68 1,217
	(50, 10, 122)	T-QUACQ.1	21	0.22 1,222
	GG(K4 × P2)	QUACQ	976	13 1,989
	(24, 16, 164)	T-QUACQ.1	47	0.39 1,273
	GG(K5 × P2)	QUACQ	3,144	512 4,898
	(35, 25, 370)	T-QUACQ.1	110	0.65 2,317
	GG(K4 × P3)	QUACQ	7,206	367 5,796
	(38, 26, 417)	T-QUACQ.1	150	0.89 2,883
	Sudoku 9 × 9	QUACQ	2,810	1,355 9,053
	(81, 9, 810)	T-QUACQ.1	69	0.33 6,873
	Latin-Square	QUACQ	7,200	1,234 12,204
	(100, 10, 900)	T-QUACQ.1	120	0.56 7,711
	Golomb-ruler-12	QUACQ	11,972	2,808 2,445
	(12, 110, 2,270)	T-QUACQ.1	1,184	0.94	916

QUACQ also contains a line for returning "collapse" when detecting an inconsistent learned network. This line has been dropped from T-QUACQ because we allow it to learn a target network without solutions.

www.choco-solver.org

of the query size is that when we are in a zone of many no answers (early learning stage), short negative queries lead to less queries needed by FindScope to find where the culprit constraint is, whereas in a zone of yes answers (late learning stage), larger positive queries lead to the removal of more constraints from B, and thus faster convergence. T-QUACQ using this version of the function adjust is called T-QUACQ.1 in the following.

We expect that the efficiency of T-QUACQ.1 will depend on the initialization of the parameters α and τ in function initialize (line 2 of Algorithm 2). Concerning the parameter , we observed that its initial value has negligible impact as it is used only once at the start of the learning process. We thus set function initialize to always initialize to |X|.

Concerning α and τ , to find the most promising values of these parameters, we made an experiment on graceful graphs. On these problems, our base version T-QUACQ.0 performed worse than QUACQ. The results of T-QUACQ.1 are shown in sub-figures (a), (b), and (c) of Figure 3. The x-axis and the y-axis are respectively labeled by α ranging from 0.1 to 0.9, and log 10 (τ ) in µs (that is, each value of y corresponds to 10 y µs) ranging from 10µs to 1s. Darker color indicates higher number of queries. The number in each cell indicates the convergence rate %Conv.

Let us first analyze the convergence rate of T-QUACQ.1. We observe the same results as already seen with our baseline version, that is, premature convergence when τ is too small (10µs) or very large (1s), When τ does not take extreme values, we observe convergence in many cases. The range of values of τ that lead to frequent convergence (in fact convergence for all values of α except 0.9) goes from [1ms, 100ms] on the small instance to [10ms, 100ms] on the larger. Concerning α, we observe that its value does not have any impact on convergence except the very large value 0.9, which leads T-QUACQ.1 to return premature convergence on the harder instances even for values of τ that give convergence with all other values of α. (See α = 0.9 in sub-figures (b) and (c) of Figure 3.) This is explained by the fact that with such a large α, finding the right size of the query to generate can require too many tries (when τ is reached) and lead to exhaust the time bound

Let us now study the impact of τ and α on the number of queries asked by T-QUACQ.1. We restrict our analysis to the cases where T-QUACQ.1 has converged. We observe that when T-QUACQ.1 converges, the larger τ , the lower number of query (see sub-figures (a), (b), and (c) of Figure 3). Concerning the impact of α on the number of queries, we observe that, the greater α (except 0.9 which leads to premature convergence), the lower the number of queries. The reason is that a large α leads to a smooth adjust-


Martine Poux

Nicolas Roche

HAL is

OATAO is an open access repository that collects the work of Toulouse researchers and makes it freely available over the web where possible Any correspondence concerning this service should be sent to the repository administrator: tech-oatao@listes-diff.inp-toulouse.fr In September 2015, the city of Nice, France, will host the 10th European Congress of Chemical Engineering (ECCE10) in conjunction with the 3rd European Congress of Applied Biotechnology (ECAB3) and the 5th European Process Intensification Conference (EPIC5). This will be the most important scientific event in chemical and biochemical engineering in Europe in 2015. The global theme for this group of events is "Chemical and biochemical engineering for a new sustainable process industry in Europe".

Key features and objectives

The economic crisis affecting Europe has brought back the typically taboo term "reindustrialization" into everyday vocabulary. Reindustrialization is the economic, social, environmental and political process of organizing national resources for the purpose of revitalizing industry and is often achieved through the development of new and innovative activities. This is a means to the neoindustrialization of Europe.

Industrial development is certainly one means for reindustrialization, especially since it will aid in restructuring the economy. Here, R&D sectors have a vital role in providing innovation and technical expertise and knowledge, which are essential for any ambitious industrial revitalization. Further, reindustrialization aims at developing traditional industries via the integration of new technologies and sustainability. For example, resolution of the petroleum crisis will require an entire reorganization of the economy, whereby less and less carbon energy is employed and replaced by sustainable solutions. In this situation, it is obvious that chemical engineering and biochemical engineering will play an important role.

As reported by several economists, the reindustrialization and the development of industries of the future will need to consider three key fields: environmental preservation and remediation, energy efficiency and human health protection, involving adapted education to new industrial challenges. This group of events aims at participating in this large economical project, which concerns all countries in Europe. Through scientific sessions, workshops and symposia, scientists and industrialists will present their steps towards a new sustainable process industry.

Congress topics

ECCE10-ECAB3-EPIC5 will focus on new advances and opportunities in the core chemical and biochemical engineering disciplines with emphasis on four main societal challenges: -Energy: new and unconventional resources, conservation and management -Water management and treatment -Biotechnology and food -Industrial ecosystems ECCE10-ECAB3-EPIC5 will also include four symposia: -3rd Symposium on Thermodynamics: Industrial Use of Thermodynamics A selection of communications will be proposed for publication as full papers in a number of special issues of international journals.

Student events

Four types of fun activities that combine scientific knowledge, games and prizes are open to PhD students and young scientists:

-Student quiz and happy hour -My PhD is a masterpiece -Meet your idol -Jobs forum.

And more…

An open space dedicated to exhibitors will be a unique opportunity for companies and organizations to share their latest advances in the field of chemical and biochemical engineering via the exhibition of their products, services and expertise. ECCE10-ECAB3-EPIC5 are organized under the auspices of the European Federation of Chemical Engineering (EFCE), the European Society of Biochemical Engineering Sciences (ESBES) and the French Society of Chemical Engineering (SFGP).

Coordinators

  This is an author's version published in: http://oatao.univ-toulouse.fr/20352 To cite this version: Poux, Martine and Roche, Nicolas 10th European Congress of Chemical Engineering (ECCE10)/3rd European Congress of Applied Biotechnology (ECAB3)/5th European Process Intensification Conference (EPIC5) -Nice, France, September 27-October 1, 2015. (2015) Green Processing and Synthesis, 4 (2). 151-152. ISSN 2191-9542 Official URL: https://doi.org/10.1515/gps-2015-0012

-

  Martine Poux, Laboratoire de Génie Chimique, INP/ CNRS/UPS, University of Toulouse, France -Nicolas Roche, Laboratoire de Mécanique, Modélisation et Procédés propres, Aix Marseille University, France Scientific chairs -Chair of ECCE10 Scientific Committee: Jean-Marc Le Lann -Chairs of EPIC5 Scientific Committee: Jean-Pierre Brunelle, Michel Cabassud, Christophe Gourdon -Chair of ECAB3 Scientific Committee: Guilherme Ferreira. Information: www.ecce2015.eu

10th European Congress of Chemical Engineering (ECCE10)/3rd European Congress of Applied Biotechnology (ECAB3)/5th European Process Intensification Conference (EPIC5) -Nice, France, September 27-October 1, 2015

  Laboratoire de Mécanique, Modélisation et Procédés propres, Aix Marseille University, 38 rue Joliot-Curie 13451 Marseille, France, e-mail: nicolas.roche@univ-amu.fr Martine Poux* and Nicolas Roche*

	DOI 10.1515/gps-2015-0012

*Corresponding authors: Martine Poux, Laboratoire de Génie Chimique, INP/CNRS/UPS, 4 allée Emile Monso, BP 84234, 31432 TOULOUSE, Cedex 4, France, e-mail: martine.poux@ensiacet.fr; and Nicolas Roche,


Rodrigo Silva
email: rodrigo.silva@imt-atlantique.fr

Jean-Marie Bonnin
email: jean-marie.bonnin@irisa.fr

Thierry Ernst
email: thierry.ernst@yogoko.fr

An ITS-based Architecture for Opportunistic Networking

Keywords: TC 204, ETSI TC ITS, ITS station communication architecture, C-ITS, decision making

For a smarter use of transportation systems, vehicles need to increase their environment awareness. This could be achieved by enabling vehicles to communicate with their environment. Once vehicles become connected, an ecosystem of applications and services could be developed around them, enabling the information exchange with other connected devices and contributing for a Cooperative Intelligent Transportation Systems (C-ITS). The environment of connected and cooperative vehicles is characterized by its heterogeneity, i.e., there are a wide variety of applications, a variety of users with different communication preferences. Moreover, countries may have specifics regulations. A single access technology to connect all these heterogeneity is impossible. For ubiquitous connectivity it is necessary to use existing wireless technologies (e.g., vehicular WiFi (ITS-G5, DSRC), urban WiFi, 802.15.4, and cellular). In such heterogeneous network environment, applications and services cannot take into account all technology particularities. It is necessary a communication architecture that hides the underlying differences of access networks from applications, providing seamless communication independently of the access technology. Based on the ITS architecture proposed by International Organization for Standardization (ISO) and European Telecommunications Standards Institute (ETSI), we propose a Decision Maker (DM) architecture that is capable to manage requirements and preferences from different actors (e.g., applications, users, administrators and regulators), it takes into account the short-term prevision about the network environment, it considers the context information (e.g., vehicle speed, battery level). And it also takes into account the route conditions between two communicating devices in order to make proactive decisions.

I. INTRODUCTION

The number of connected devices is growing fast around the world. These objects are components of a network known as the Internet of Things (IoT), where each object has the possibility to exchange data with others. This scenario enables the development of smart cities, where vehicles are supposed to be one of the communicating objects. According to Gartner research company, connected cars would be a major element of the IoT, representing 20% of all IoT devices [START_REF] Gartner | a Quarter Billion Connected Vehicles Will Enable New In-Vehicle Services and Automated Driving Capabilities[END_REF].

For a smarter use of transportation systems, vehicles need to increase their environment awareness. This could be achieved by enabling vehicles to communicate with their environment. The connection could be local between nearby devices or global, i.e., connection over the Internet. Once vehicles become connected, an ecosystem of applications and services can be developed around them. Nowadays, we are connected to Internet through our computers and smartphones. In the future, the vehicles will be directly connected too, supporting a variety of applications (like smartphones do). For example, vehicles could connect to the Internet to enhance driver and passenger experience, e.g., improving the navigation and offering on-board Internet connectivity. Vehicles can to connect and exchange information with other devices in a smart city environment. In this context, users, devices and vehicles need to be connected anywhere, anytime with anything. Such connections will enable the information exchange between vehicles and their environment for a Cooperative Intelligent Transportation Systems (C-ITS).

However, a single access technology to connect all these heterogeneity of services and devices is impractical or even impossible. For ubiquitous connectivity it is necessary to use existing wireless technologies, such as vehicular WiFi (ITS-G5, DSRC), urban WiFi, 802.15.4, WiMAX, cellular (3G, 4G, and 5G under preparation) [START_REF]ETSI ES 202 663[END_REF]- [START_REF] Chakrabarti | IPv6 over Low-Power Wireless Personal Area Network (6LoWPAN) ESC Dispatch Code Points and Guidelines[END_REF]. Each of these networks has specific characteristics in terms of bandwidth, data rate, security and others. Due to this network heterogeneity and its complementary characteristics, more connectivity opportunities are available. Mobile devices equipped with multiple communication capabilities could use multiple access technologies simultaneously in order to maximize flows satisfaction (e.g., to maximize communication bandwidth, to reduce latency, and others) and to satisfy communication requirements (e.g., security, monetary cost, traffic load balancing among available networks, and others).

The environment of connected and cooperative vehicles is characterized by its heterogeneity. For example, there are a wide variety of applications, each one with specific requirements. There are a variety of users with different preferences. Countries could have specifics regulations. There are a variety of access technologies, each one with specific characteristics in terms of bandwidth, data rate, security and others. Moreover, vehicles can move at high speed and frequently change its network environment.

In such heterogeneous and dynamic network environment, applications and services cannot take into account all technology particularities, unless they explicitly need it. The communication architecture has to hide the underlying differences of access networks from applications, providing seamless communication independently of the access technology. It should be capable to handle multiple access technologies simultane-ously while select the most appropriate access network for each flow. Such an architecture should choose the path, i.e., the route between two communicating nodes that best meets the communication requirements (e.g., a local connection between nearby devices or a global connection over the Internet). Moreover, in such dynamic environment the communication architecture should perform proactive decisions taking into account the short-term prevision about the network availability.

Based on some research work and also based on the ITS architecture proposed by International Organization for Standardization (ISO) and European Telecommunications Standards Institute (ETSI), we propose a Decision Maker (DM) architecture. Such architecture is capable to manage requirements and preferences from different actors (e.g., applications, users, administrators and regulators), it takes into account the short-term prevision about the network environment, it considers the context information (e.g., vehicle speed, battery level). And it also takes into account the route conditions between two communicating devices in order to make proactive decisions. The proposed DM architecture is developed in an ISO/ETSI standard compliant way.

The remainder of this paper is organized as follows. Section II overviews the reference ITS station communication architecture proposed by ISO and ETSI. Section III reviews some related work. The proposed DM architecture is described in Section IV. And Section V concludes the paper and proposes future directions.

II. THE REFERENCE ITS STATION COMMUNICATION

ARCHITECTURE

In order to establish an harmonized communication-centric architecture for ITS, ISO and ETSI have proposed a reference ITS communication architecture supported by nodes called ITS Stations (ITS-S), where each ITS-S (e.g., vehicles) can handle its communication [START_REF]ISO 21217 Intelligent Transport Systems -Communications Access for Land Mobiles (CALM) -Architecture[END_REF]. Such architecture is shown on Figure 1. The concept of the ITS-S communication architecture is to abstract applications from both the access technologies and the networks that transport the information between communicating nodes. Therefore, applications are not limited to a single access technology, but they could take advantage from all available technologies. While the lower layers can be independently managed, without impacting applications.

In such architecture, two cross layers entities, i.e., "ITS Station Management" and "ITS Station Security" are responsible to station management functionalities and to provide security and privacy services, respectively. Since applications are developed regardless to communication networks, "ITS Station Management" entity is responsible to choose the best network interface for each application. In order to manage different process in the ITS-S, such cross layers entities communicate with the horizontal layers: "ITS Station Access Technologies" layer that is responsible for media access control and provides data transmission through different access technologies, such as vehicular WiFi (ITS-G5, DSRC), urban WiFi, 802.15.4, WiMAX, and cellular (3G, 4G, and 5G under preparation); "ITS Station Networking & Transport" layer, which is responsible to execute operations like packet routing, path establishment, path monitoring and Internet Protocol (IP) mobility; "ITS Station Facilities" layer that provides applications, information and communication supports (e.g., encode/decode message support, time-stamping and geo-stamping) and "ITS Station Application" layer that provides Human-Machine Interface (HMI).

Network Mobility Basic Support Protocol (NEMO) [START_REF] Petrescu | Network Mobility (NEMO) Basic Support Protocol[END_REF] has been chosen by several standardization bodies for IP-based mobility management, including ISO and ETSI. NEMO allows a Mobile Router (MR) to manage the IP mobility for all mobile network attached to it. The MR maintains a bi-directional tunnel (protected by IPsec) to a server in the cloud referred to as the Home Agent (HA), as shown on Figure 2. For the mobile network, it is allocated an IPv6 prefix identifying the mobile network in the IP addressing topology as permanently attached to the HA. Based on this prefix, the MR assigns unchangeable addresses to its attached nodes called Mobile Network Nodes (MNN). When a new network is available, MR generates a new auto configured IP address (Care-of-address (CoA)) within the new visited network and notifies them to the HA. Only the MR and the HA are aware of the network change, since MNNs remain connected to the MR through their permanent IP address.

MRs can be equipped with multiple communication interfaces. Multiple Care of Addresses Registration (MCoA) [START_REF] Soliman | Flow Bindings in Mobile IPv6 and Network Mobility (NEMO) Basic Support[END_REF] is used to managed these communication interfaces simultaneously, as illustrated on Figure 2. MCoA enables the registration of several CoAs for a single MR. In this case, the MR could establish multiple tunnels through each of its communication interfaces and the HA.

The possibility of having multiple applications in an ITS-S simultaneously competing for communication resources leads to the need for a controlled access to these resources. In such a control, requirements and objectives presented by Authors of [START_REF] Suciu | Towards a highly adaptable user-centric terminal architecture[END_REF] proposed a modular architecture for multihomed mobile terminals. In such architecture, a middleware interacts with "higher-layers" and "low layers". The "high layers" gather the user and the administrator preferences, handle the applications' requirements, and detect the current terminal capabilities. The "low layers" detects the available networks and provides real-time information about the interfaces and access networks capabilities as well as it handles the selection execution process, i.e., it maps the application's flows on the preferred access network. It does not consider the path condition of a given flow between sender and destination nodes. And it does not consider the near future of the network environment, i.e., the short-term prevision about the availability of networks.

Paper [START_REF] Rayana | A Smart Management Framework for Multihomed Mobile Nodes & Mobile Routers[END_REF] proposes a context-aware management solution to maximize the satisfaction of the applications while respecting the stakeholders policy rules. The proposed framework collect and combining policies from stakeholders (e.g., user, administrators and applications). Based on such policies and context information, it evaluates the network that better match the communication requirements. Once the best network is chose, the flow routing is enforced on the device using NEMO and MCoA. Such architecture does not consider the path condition experienced by a flow or the near future of the network environment.

Paper [START_REF] Santa | A Framework for Supporting Network Continuity in Vehicular IPv6 Communications[END_REF] proposes a framework for supporting network continuity in vehicular IPv6 communications. Such framework follows the ISO/ETSI guidelines for the development of cooperative ITS systems and is based on standardized technologies, such as NEMO protocol to provide an integral management of IPv6. However, it considers cooperation between mobile devices and networks based on the 802.21 standard (Media Independent Handover (MIH)), i.e., it considers that all networks support the specific functionalities from 802.21 standard [START_REF]IEEE 802.21 -Standard for Local and metropolitan area networks -Part 21: Media Independent Handover Services[END_REF].

IV. THE ITS-BASED DM ARCHITECTURE

This section describes the modular DM architecture for opportunistic networking in heterogeneous access network environment. The proposed architecture is based on the previously described ITS-S communication architecture and designed to meet the main challenges for communication profile and path selection in C-ITS environment.

A. Expected properties

As described by [START_REF] Silva | Opportunistic Networking for ITS[END_REF], the environment of connected and cooperative vehicles is characterized by a large heterogeneity. There are a wide variety of applications with different communication requirements. There are different wireless access technologies each one with specific characteristics in terms of bandwidth, data rate, security and others. In such an environment, the process to select the best suited communication profile and path for each data flow presents some challenges.

Different actors are able to present their requirements, preferences, constraints and policies in the decision making process. For example, applications can request a specific bandwidth, data rate or security level. Users can present their preferences, e.g., defining a priority or security level for a given message. Industrial and mobility service providers (i.e., operators) can present their policies, such as network constraints and particular billing procedures. Moreover, these wide variety of objectives could be contradictory. The DM architecture should be capable of managing these multiple objectives simultaneously.

The DM architecture should be able to monitor a variety of information in order to enable more accurate solutions in the decision making process. One essential piece of information to be monitored is the wireless networks availability as well as the performance of the networks in use. Moreover, it is necessary to monitor flows and their characteristics (e.g., used bandwidth, flow status).

Besides network monitoring, other significant parameters could be monitored. Vehicles would be able to take information from their environment, as vehicle's battery level, geographical position (e.g., GPS) or vehicle's speed in order to adjust the decision's strategies. For example, a power consuming network interface could be deactivated if the vehicle's battery level is under a certain threshold. Or a WiFi network could be privileged if the vehicle is stationary, while a cellular network could be preferred if the vehicle is moving.

The DM architecture should be capable of handling communication profile and communication path for each flow. A data flow is defined by ISO as an identifiable sequence of packets [START_REF]ISO/DIS 24102-6 Intelligent Transport Systems -Communications Access for Land Mobiles (CALM) -ITS station management -Part 6: Path and flow management[END_REF]. And packets are dependent upon applied protocols, links and nodes characteristics. For example, packets sent over different communication paths (routes) to the same destination node experience distinct network conditions/performances. Such distinct experiences are consequence of the applied protocol stacks (communication profile) and the specific characteristics of the traversed path (e.g., delay, throughput, security level, etc.). Therefore, on the Flow-Interface mapping process, it is not enough to indicate only what access network a given flow should use. In addition, according to flow requirements and paths characteristics it is necessary to determine the communication profile and path for each flow.

Moreover, due the vehicle's high speed the networks availability could change rapidly. In such highly dynamic mobility the decision making process should take into account the shortterm prevision about the network environment condition. If the DM is aware about the near future of the network environment it can perform proactive and fine-grained decision. For example, it can decide to increase the data buffer for a given video streaming, if the vehicle is going to cross a wireless dead zone. Or, an on-board application could decide to delay a data transmission if it knows that a better network will soon be available.

The short-term prevision can be obtained in different ways. It can be obtained by cooperation with networks, e.g., using the IEEE 802.21 standard if the network support such protocol. The vehicle can store network information from a previous traversed route, e.g., for an user who uses the same route every day, the database could stores information about network conditions in such route. Or, the short-term information can be obtained by cooperation with neighbors vehicles. For example, two vehicles in opposite directions could exchange information about access points in their upcoming route. For this purpose, a vehicle stores the position of each access point in its traversed route, and give them to another passing-by vehicle.

B. Architecture design

To achieve the expected properties, we propose a modular DM architecture based on the ISO/ETSI standards. Figure 3 shows such proposed DM architecture.

For a better understanding, we split the DM architecture in five main parts, which are described below.

1) Requirement gathering: As mentioned before, different actors are able to present theirs requirements in the decision making process. In our proposed architecture we consider four main actors. Applications -it could request a specific bandwidth, data rate, security level and more. A middleware enables different applications to send their requirements to DM. Users -they can present their preferences through a Graphical User Interface (GUI), e.g., defining priority or security level for a given message. Administrators, i.e., industrial and mobility service providers -they could present their policies, such as network constraints and particular billing procedures. And regulator bodies -each country or region could define some specific rules, such as the prohibition of certain frequency ranges in certain areas. The requirements from all actors are stored in decision maker's databases and used by the DM to choose the communication interface that better matches the actors requirements.

2) Monitoring modules: We defined four monitoring modules. Network monitoring module -in this process, the network monitoring module listens to the wireless interfaces and informs DM about the available wireless networks and their performances. Such monitoring module should be able to monitor network information even if no specific monitoring functionality, such as 802.21 [START_REF]IEEE 802.21 -Standard for Local and metropolitan area networks -Part 21: Media Independent Handover Services[END_REF], is implemented on the network side. Context monitoring module -this module is responsible for vehicle surrounding monitoring. It is responsible to monitor information like location of the neighboring vehicles, traffic jam, vehicle's speed, and others. These information are part of the Local Dynamic Map (LDM) functionalities, i.e., the conceptual data store located within an ITS-S as outlined in [START_REF]ETSI EN 302 895 Intelligent Transport Systems (ITS); Vehicular Communications; Basic Set of Applications; Local Dynamic Map (LDM)[END_REF]. Therefore, we aim to rely this monitoring module on such conceptual data store. Flow monitoring module -this module should inform whether a flow is alive or not and evaluate flows' performance, like the currently used bandwidth, the currently latency, etc. Path monitoring module -this module is responsible to obtain various information (e.g., throughput, security level, latency, etc.) about the controllable end points where packets will be routed and to keep track of all the candidate and available paths.

3) Near Future: In order to take into account the shortterm prevision about the network environment, we propose a network database that store the historical information about the access networks (e.g., network performance and access point location) and a filtering entity that is responsible to analyze such network database and, based on the context information of the vehicle (e.g., movement speed), to choose the potential networks to be considered in the decision making process.

4) Decision making process: The decision making process is responsible to take into account the application's requirements, user profiles, administrative rules (regulation and policies) as well as different monitored information in order to manage flows and paths. The decision making process is detailed in section IV-C.

5) Applying decision: In the applying decision process, the policies and information produced by the decision making process are applied in the system. In this process, the decision maker could interact with controlled entities in all layers of the ITS station communication architecture. Once the best access network and path is selected, i.e., the path and access network that better match the communication requirements, the DM request the "Flow-Interface mapping" module to enforce the flow routing decision. To enforce the decision's polices at the network layer in an IP-based environment, we are considering NEMO and MCoA. These protocols allow mobile routers to manage multiple access technologies simultaneously and to improve path and flow management.

Since the decision making process take into account the short-term prevision about the network environment, proactive decisions are enforced in order to maintain flows always best connected. However, unexpected changes can occur in a wireless environment (e.g., a given access network can drops). In order to adapt to the network conditions in real time, the DM maintain an hierarchical solution database with all suboptimal solutions for each flow. This database is used by the "Flow-Interface mapping" module in case of emergency, i.e., when the best network solution drops unexpectedly and until the DM finds another better solution.

C. Decision Making Process

As mentioned before, the decision making process takes into account the application's requirements, user profiles, administrative rules as well as information from a variety of monitoring modules in order to manage flows and paths. We split our decision making process in three modules, as shown on Figure 3. Below we describe each one of these modules:

Hierarchy/Filtering: This module is responsible to receive and manage requirements, preferences, and policies from different actors. Since actors may have their own specific preferences and requirements, we need to "filter" (in Computer Science acceptation) the various values defined for the same parameter. Moreover, it is necessary to define a priority order between actors in order to manage contradictory objectives. For example, if the administrator sets a forbidden network for a user, and the user set the same access network to preferred, then it is necessary to define who has the priority. The output of such module is a list of filtered and hierarchical requirements.

Rank Alternatives: This module is responsible to find all alternatives for flow-interface mapping. It is a first filter to avoid forbidden networks or networks that do not match with flows' requirements. Such module receives the coherent list of requirements from "Hierarchy/Filtering" module, network information (e.g., networks availability and networks performance), and context information in order to find the potential solutions. The output of this module is a list of all potential solutions for each flow.

Decision Algorithm: This module receives the list of all potential solutions created in the "Rank Alternatives" module and apply decision making algorithm in order to evaluate the matching degree of communication requirements with networks and path characteristics. An utility function calculates a score, representing the matching degree for each solution. Higher the score, better is the solution. The solutions are sorted by descending order of score and stored on the hierarchical solution database. Such database is used by the enforcement module in case of emergency, i.e., when the best network drops unexpectedly, the "Flow-Interface mapping" module redirect the flow through the first available sub-optimal network while the DM finds a new better solution.

As described by [START_REF] Silva | Opportunistic Networking for ITS[END_REF], several decision making algorithms have been used in the network selection process. For example, the ones based on the game theory, the ones based on Multi-Objective Optimization (MOO) and the algorithm that uses Multi-Attribute Decision Making (MADM) techniques. The most used are the MADM methods (e.g., Simple Additive Weighting (SAW), Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) and Analytic Hierarchy Process (AHP)). Despite the MADM techniques present advantage as relative low computation complexity, this approach has some issues. For example, it is very difficult to choose the best weight for each attribute. Moreover, MADM algorithms could present ranking abnormality, i.e., change in one of the parameters of the objective function could determine a very different best solution. The design of a decision making algorithm is outside the scope of this paper. Such topic will be addressed in future works.

D. Integration in the ITS-S communication architecture

The ITS-S communication architecture functionalities could be implemented into a single physical unit, as the practical implementation showed on paper [15], or distributed into several physical units. Once applied to a vehicle, these functionalities could be performed by different modules in the vehicle's electric/electronic architecture.

Moreover, the NEMO environment mainly separate the applications and communications into MNN and MR. Therefore, the five functions described in Section IV-B can also be separated into such nodes. For example, the requirement gathering can be implemented in the MNN, the monitoring modules can be implemented in both MR and MNN, while the near future, the decision making process and applying decision are functions of the MR.

The proposed DM architecture is designed in an ISO/ETSI standard compliant way. Figure 4 shows one way how we can integrate such architecture in the ITS-S communication architecture. However, the standards give some guidelines to the developers, leaving some room in the way to implement the ITS-S communication architecture.

V. CONCLUSION AND FUTURE WORK

In this paper, we proposed a modular decision maker architecture that is capable to choose the best available communication profile and path for each data flow in an heterogeneous and dynamic network environment. The proposed DM architecture is designed in an ISO/ETSI standard compliant way and we show how to integrate it in the ITS-S communication architecture.

Besides the access network selection, the proposed architecture is able to choose the best path for a given flow, i.e., the route between two communicating nodes that best meets the communication requirements (e.g., a local connection between nearby devices or a global connection over the Internet).

Different actors are able to present theirs requirements in the decision making process, e.g., applications, users, network administrators, etc. And this wide variety of objectives could be contradictory. The proposed DM architecture is capable of managing these multiple objectives simultaneously. Moreover, the DM receives information from a variety of monitoring modules (network, context information, path, and flows monitoring modules), that enable fine-grained decisions.

The proposed architecture address the short-term prevision about the network environment. This short-term prevision allows proactive decisions, which is very useful in vehicular environments that are characterized by highly dynamic mobility.

Once the best access network and path is selected for a given flow, the decision's polices are enforced at the network layer using standardized protocols, such as NEMO and MCoA. These protocols allow mobile routers to manage multiple access technologies simultaneously and to improve path and flow management.

We highlight the importance of the DM architecture validation. As future work, we will simulate the proposed architecture using different scenarios and existing decision making algorithms. We will also design and simulate a decision making algorithm capable to take advantage of the entire proposed architecture for smart and fine-grained decisions. Moreover, it is valuable to conduct such architecture in a real test-bed.

Figure 1 .

 1 Figure 1. The reference ITS station communication architecture.

Figure 2 .

 2 Figure 2. NEMO and MCoA.

Figure 3 .

 3 Figure 3. Proposed Decision Maker Architecture.

Figure 4 .

 4 Figure 4. Integration of DM Architecture in the ITS-S communication architecture.