Anouar Jammali
email: jammali.anouar@gmail.com

Mohamed Anis

Bach Tobji

Arnaud Martin
email: arnaud.martin@univ-rennes1.fr

Boutheina Ben
email: boutheina.yaghlane@ihec.rnu.tn

Indexing Evidential Data

Keywords: Dempster-Shafer theory, indexing data, evidential database

Querying imperfect data received increasing attention in the area of database management. The complexity and the volume of imperfect data requires advanced techniques for efficient access, and satisfying user-queries in a reasonable response time. In this paper, we are particularly interested in evidential databases, i.e., databases where imperfection is represented through Dempster-Shafer theory. To answer userqueries in such databases, we propose a new index system based on a tree data structure (e-Tree) that is adapted to the complexity of the evidential data. The experiments done on our solution showed encouraging results.

I. INTRODUCTION

Imperfect databases research field is receiving a quite important attention from academic and industrial researchers in the recent years. That is due to the need of database management systems (DBMS) that handle different data natures and support decision making process in presence of uncertainty.

Several real world applications suffer from data imperfection. For example, in medical applications, symptoms and diagnosis data are infected with imperfection (be it uncertainty, incompleteness or imprecision). Also, data collected from sensors deal with imperfections. The sensors of a unique system may have different precision levels, thus, the system that manages these data should be as robust as possible to correctly cope with data imperfection.

In this work, we are interested in imperfect data that are modeled through Dempster-Shafer theory [START_REF] Dempster | Upper and Lower Probability Function in a Context of Uncertainty[END_REF], [START_REF] Dempster | A Generalization of Bayesian Inference[END_REF], [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] called, evidential data. Evidential database is the system that stores and manages evidential data, with regarding to its complex nature. Handling uncertainty and imprecision via evidential database systems is an active research topic tackled in several works such as [START_REF] Bell | Generalized Union and Project Operations for Pooling Uncertain and Imprecise Information[END_REF], [START_REF] Abdelaziz | The Evidential Database Model[END_REF], [START_REF] Hewawasam | Rule Mining and Classification in Imperfect Databases[END_REF], [START_REF] Bach Tobji | Extraction des itemsets frequents a partir de donnees evidentielles : application a une base de donnees educationnelles[END_REF].

When we deal with huge volume of data [START_REF] Bayer | Organization and Maintenance of Large Ordered Indexes[END_REF], the cost of accessing these data becomes problematic. A trivial solution to minimize this cost is to use an indexing system. However, conventional indexes used in traditional (perfect) databases are unusable in evidential databases, because non adapted to the structure of the evidential data. Even index structures introduced in the uncertainty context, cope with probabilistic databases [START_REF] Li | A survey of queries over uncertain data[END_REF], [START_REF] Dong | Processing Probabilistic Range Queries over Gaussian-Based Uncertain Data[END_REF], [START_REF] Agarwal | Indexing Uncertain Data, Managing and Mining Uncertain Data[END_REF], [START_REF] Huang | Indexing and querying moving objects with uncertain speed and direction in spatiotemporal databases[END_REF] rather than with evidential ones.

In this work, we introduce a new tree based data structure as an indexing system adapted to the nature of data stored in evidential databases. The introduced structure is a single attribute index, i.e., an index based on a unique database column. To validate our contribution, we implemented the sequential access to the evidential database, which is the trivial solution to answer user-queries, the Rid Lists structure, introduced in [START_REF] Bach Tobji | A New Algorithm for Mining Frequent Itemsets from Evidential Databases[END_REF] and adapted in this paper to index evidential data, and finally the evidential tree, called e-Tree, introduced in this article. Then we led experiments on these methods to compare their efficiencies for various synthetic evidential databases.

This paper is organized as follows:

In section 2, we present the background material of our work. In subsection A, the basic notions of Dempster-Shafer theory are introduced, to present then, in subsection B, the evidential database concept which is based on the aforementioned theory. In section 3, we present the indexes of evidential data. Two solutions are presented; the RID Lists structure, initially proposed in [START_REF] Bach Tobji | A New Algorithm for Mining Frequent Itemsets from Evidential Databases[END_REF] for mining association rules, and the e-Tree structure that is the contribution of this work. Finally, in section 4, we present the experiments conducted on our index systems as well as the obtained results.

II. BACKGROUND MATERIAL

A. Dempster-Shafer (DS) Theory

A discernment frame is a set of mutually exclusive and exhaustive hypotheses where one of these hypotheses is likely to be the solution for the proposed problem. The uncertain information representation can be expressed by the mass function:

Let Ω be a frame of discernment, then, a function m : 2 Ω → [0, 1] is called a mass function whenever:

m(∅) = 0 A⊆Ω m(A) = 1 (1)
An element A of the set 2 Ω is called a focal element whenever m(A) = 0. The measure m(A) gives how much is true the hypothesis A.

From this definition are derived the definitions of belief (bel) and plausibility (pl).

The belief value of an attribute A, denoted by bel(A), is the total mass of all subsets of A. It reflects the total belief committed to A.

bel

Ω : 2 Ω → [0, 1] bel Ω (A) = B⊆A m Ω (B) (2)
The plausibility function is the dual function of belief. It measures the maximum amount of belief that could be given to a proposition A. This function gives how much the given information enforces the hypothesis A. It is defined on 2 Ω → [0, 1] as follows:

pl

Ω (A) = 1 -bel Ω ( Ā) pl Ω (A) = B∩A =∅ m Ω (B) (3)
where Ā is the complement hypothesis of A.

B. Evidential Database

An evidential database EDB is a database with X attributes and Y lines where each attribute A x (1 ≤ x ≤ X) has a domain Ω x containing all the possible hypotheses, i.e., values of A x . Ω x is the frame of discernment of the x th attribute. The value of the j th attribute in the i th line is called an evidential value denoted by V ij . An evidential value is a basic belief assignment (bba) defined through a mass function denoted by m ij . Table 1 is an example of an evidential database, where the attribute Disease stores the diagnosis of a patient. The diagnosis of a patient may be precise and certain, as the diagnosis of John. It may be uncertain, like the diagnosis of Robert. Also, it may be imprecise, like for the patient Maria. This evidential attribute may contain any imperfect information that could be modeled through the DS theory. In [START_REF] Lee | An Extended Relational Database Model For Uncertain and Imprecise Information[END_REF], the author introduced an interesting model of an extended relational evidential database. The main contribution of this work is a generalized relational algebra where five relational operators (projection, restriction, cross product, intersect and join) are redefined.

In this paper, we are content with giving a simple example of selection from one table. For more details, please refer to the articles [START_REF] Lee | An Extended Relational Database Model For Uncertain and Imprecise Information[END_REF] and [START_REF] Bell | Generalized Union and Project Operations for Pooling Uncertain and Imprecise Information[END_REF].

Assume we want to evaluate the following query:

SELECT * FROM diagnosis WHERE disease='flu'
In a perfect database, the result of this query contains every line whose attribute Diagnosis has the value flu. In evidential databases, attributes contain evidential values rather than precise values. Thus, the result contains the lines where belief of flu is strictly positive in the bba of the Diagnosis attribute (bel(f lu) > 0). It is formally defined as follows:

tab <attribute=v> = {l ∈ edb/bel l (v) > 0} (4)
where tab <attribute=v> is the restriction of the relation tab according to condition attribute = v, and bel l (v) is the belief of v in the record l.

Note the pseudo-attribute Bel added to the resulted relation (see Table 2). It represents the belief of the searched value (in our example flu) in the resulted line.

In [START_REF] Lee | An Extended Relational Database Model For Uncertain and Imprecise Information[END_REF], the resulted lines are those where pl(flu) is strictly positive (pl(f lu) > 0). A pseudo-attribute called Confidence Level (denoted by CL) is added to the returned relation. It is an interval delimited by the belief and the plausibility of each resulted line as shown in table 3. Thus, in the literature, there are two models for answering user-queries in evidential databases. In the first one, we return lines where believes of the searched value are positive. In the second model, returned lines are those whose plausibilities of the searched value are positive. In this paper, we focus only on the first model.

III. INDEXING EVIDENTIAL DATABASES

Answering a query of the form table < attribute = V > leads to computing the belief of the searched value (V ) in each line of the database. The DBMS has not only to look for the searched value, but also for the subsets of the searched value (see the definition of the belief function in section 2, subsection A). For example, assume that the searched value is V = {cancer, f lu}. The DBMS should find all lines that deal with {cancer, f lu}, but also with cancer and f lu values. If the searched value V has a size n, then the DBMS must return each line that deals with any subset A ⊆ V from the 2 n possible focal elements in the database that are subsets of V . Thus, answering queries in evidential databases is much more costly than answering queries in perfect databases. Consequently, it is obvious that efficient query processing techniques are needed. Indexing remains a key technique to this aim.

In this section, we will present two indexing techniques. The first one is derived from the work [START_REF] Bach Tobji | A New Algorithm for Mining Frequent Itemsets from Evidential Databases[END_REF], where RID Lists are used to mine frequent itemsets in evidential data. And the second one is introduced in this paper. It is a tree data structure that represents evidential data in a manner that accelerate the search operation.

A. The RID Lists structure

The RID Lists structure assigns to each focal element in the indexed attribute a list of couples. Each couple that concerns a focal element f e contains two information:

• The row identifier (ROWID) of the line that contains f e.

• The mass of f e in that line.

The RID Lists corresponding to the diseases' database (table 1) is presented in table 4. The construction algorithm of the RID Lists structure, corresponding to an evidential database, is detailed in [START_REF] Bach Tobji | A New Algorithm for Mining Frequent Itemsets from Evidential Databases[END_REF].

To evaluate the query table <attribute=v> , the RID Lists index is scanned, and every RID List related to a focal element included in v, is returned. To accelerate the search, the RID Lists is sorted in the construction phase.

B. The Evidential Tree

The evidential tree, denoted by e-Tree, is a tree data structure that stores the content of an evidential attribute A. The root of the tree is the empty set. A node of the tree has two information:

• A value x ∈ D A where D A is the domain of the attribute A.

• A list of couples (rid,bel).

Each couple (rid, bel) about the belief of the focal element f e in the line whose identifier is rid. f e is the focal element that is composed of values of A in the path that starts from the root, to the current node. For example, in figure 1, see the node cancer(4/1.0). It means that the focal element {anemia, cancer} (see the path that starts from the root and ends in the cancer node) has a belief equal to 1.0 in the line 4.

Note that e-Tree is sorted in breadth and in depth. It allows us to accelerate the search operation. In the following, we present two important algorithms. The first one is about the construction of the e-Tree from an evidential database. The second one deals with searching lines that cope with a search value, from an e-Tree structure.

1) Construction of the e-Tree:

The construction of e-Tree is described in the pseudo-code of the algorithm 1. In each line of the database, each focal element is inserted in depth into the e-Tree. For example, to insert focal elements of the line 2 in the database example (table 1), we begin by the element {cancer, f lu}. We look among the children of the root if there is a node relative to the value cancer. If we don't find it, we create a node with the label cancer. Then, we look among the children of this node for a node labeled f lu. If its exists, we update its RID Lists by adding the couple (2, 1.0), and not the couple (2, 0.7) since belief of {cancer, f lu} in the line 4 is equal to 1 (bel({cancer, f lu}) = mass({cancer, f lu}) + mass(cancer) = 1). Then, we handle the second focal element in line 2, that is cancer. We look for the node cancer in children's root, and we find it (it is just created). So we add the couple (2, 0.3) to its RID Lists. Algorithm 1 presents the pseudo-code of constructing the evidential tree from an evidential database. Figure 1 illustrates the evidential tree corresponding to the table Diagnosis. 2) Searching in the e-Tree: A user query may cope with a precise or imprecise value. For example, a user may search for lines with a precise diagnosis, such as flu. He also may look for lines with imprecise diagnosis, like {anemia, cancer}. If the searched value is precise, then e-Tree structure is scanned only at its first level. The other levels are about imprecise values, i.e., compound focal elements. That is an advantage relatively to the RID Lists structure, where singleton focal elements are not collected in a separate structure. In the e-Tree structure, singleton focal elements are stored as the children of the root node. If the searched value is precise, the search algorithm scans only n elements, while in the RID Lists, it scans up to 2 n elements. In this case, we can apply dichotomic search since nodes are sorted. Consequently, the complexity of the search algorithm is log 2 (n).

When the searched value V is imprecise, like {anemia, cancer}, the search algorithm looks for nodes that correspond to anemia and cancer in the first level. It also looks for the nodes that represent the focal element {anemia, cancer} which is at the second level. To make faster, when the searched value V is imprecise, each time we visit a node relative to an element e belonging to V , a depth-scan is performed to look for all children of e that are included (subsets) in V . In our example, when we visit the node anemia, we also scan its children, looking for the node cancer. This node, that represents the focal element {anemia, cancer} is also concerned by the search operation. The search algorithm returns the line 1 (with the belief 0.3), and then returns the line 4 (with the belief 1). Depth searching linked with the singleton anemia being complete, the search algorithm go to the next singleton element of V , that is cancer. The same recursive operation done for the node anemia is done for cancer.

A main advantage of e-Tree relatively to the RID Lists index, is that the hypotheses composing the focal elements are linked. Exploring a singleton value, leads directly to all nodes it prefixes, and that are subsets in V . In the RID Lists structure, subsets of V are separated, which necessitates more scan time.

Algorithm 2 is the general method to search a value V in an e-Tree structure. The output is a set of lines (identified by a rid) with the belief of V in each one (like in table 2). Algorithm 3 is the procedure used recursively in the main algorithm. The procedure SEARCH takes as input a node N in e-Tree, The searched value V and k as the level where the search will perform. It adds to the set of returned lines the couples of (rid, bel) that satisfy the search criterion in the level k. Note that in algorithms 1, 2 and 3, N.children[] is the set of the nodes that are children of the node N ; subsets(V, k) is the collection of all subsets of V whose sizes are equal to k; P AT H(c) returns the focal element that is composed of all nodes' elements that link the root node to the node Algorithm 1: Construction of e-Tree

IV. EXPERIMENTS AND RESULTS

A. Generation of evidential databases

We present in this section the experiments made on several synthetic evidential databases, in order to show the behavior of our indexes when processing user queries on scalable evidential data. Evidential databases are not abundant in real world, thus, we generated synthetic data. We implemented a generator program that produces a database with only one attribute. We recall that our indexes are single attribute based, i.e., indexes based on a unique attribute, so we do not need to databases with several attributes. The generation takes into account several parameters that cope with the evidential database nature.

The parameter D is the size of the database. It provides the number of lines in the database. The parameter N F E is about maximum number of focal elements in one bba. For example, in the database of table 1, N F E is equal to 2, since the maximum number of focal elements per line is 2 (see lines 1 and 2). The parameter SF E is the maximum size of compound focal element. In our database example, SF E is also equal to 2 (see lines 2 and 4 that include composed focal elements). The parameter CARD is the cardinality of the indexed attribute. It is the size of the frame of discernment. In our example, we have CARD = 3 because the diagnosis attribute has three possible values: anemia, cancer and flu. Finally, the parameter P CT IM P is about the rate of imperfect lines in the database. It is the ratio (number of imperfect lines ×100)/(D). In our example, P CT IM P = 75%.

The generation program produces exactly D lines. In each one, it generates n focal elements, where n is chosen in the interval [1, N F E]. Then, for each focal element, it chooses a value s ∈ [1, SF E], that is the size of the focal element. Thus, content of a focal element is composed of s hypotheses. Each one is generated such that value v of one element is taken from the interval [START_REF] Agarwal | Managing and Mining Uncertain Data[END_REF]CARD]. Finally the masses of the n focal elements are chosen each one in the interval [0, 1] under the condition n i=1 m(v) = 1. Values of n, s and v are computed in their respective intervals through the uniform law.

B. Evaluating the access methods

We created several synthetic databases with various values of the parameters above, and we implemented three access methods to evidential databases. The first access to the database uses the e-Tree index, the second one uses the RID Lists index, and the third one do not use any index system.

In the first experiment, we set the parameters N F E, SF E, CARD and P CT IM P respectively to 3, 3, 12 and 75%, and we varied the value of the parameter D from 300 to 1200. The figure 2 shows that performing an access without index is more expensive, in time execution, than an index based search. This expected result is due to the fact that using an index structure avoids scanning the whole of the database. Note that when the size of the database increases, the execution time is exponentially worse for the non-index method. Using indexes is much more efficient when the size of the database increases considerably. The e-Tree gives better results than the RID Lists index since searched elements are linked. For example, in the RID Lists, if the searched value is {A 1 , A 2 , A 3 }, then we have to find and to visit separately the lists of the focal elements A 1 , {A 1 , A 2 } and {A 1 , A 2 , A 3 }. With the e-Tree index, reading the path A 1 → A 2 → A 3 is sufficient to obtain the same information, which is composed of the row identifiers of the interesting lines, and also their believes in. This advantage is very clear in the experiment of varying the SF E parameter (see figure 3). In this experiment, we generate several databases where parameters D, N F E, CARD and P CT IM P are set respectively to 1000, 3, 12 and 75% with a variation of SF E from 1 to 3. When SF E is set to 2, using the e-Tree is more efficient than using RID Lists index. When SF E is set to 3, the performance of RID Lists index decreases considerably, contrary to the one of e-Tree that remains practically the same. The difference between the two methods' efficiencies is more considerable when the size of the indexed focal elements (SF E) increases as explained in the previous example. We also generated several databases with various imperfection rates. Values of the parameter P CT IM P were varied from 0% (all data are perfect) to 100% (all lines contain evidential values). The experiment's results are shown in figure 5. Note in this experiment that e-Tree and RID Lists give the same performance for a null value of P CT IM P . This result will be interpreted in subsection C. We performed another important experiment on variation of the CARD parameter. D, N F E, SF E, and P CT IM P are set respectively to 1000, 3, 3 and 75%, and the cardinality of the indexed attribute were varied from 10 to 20. Note that when the cardinality of the attribute is n, the total number of focal elements may reach 2 n . So when n is set to 20, the potential number of focal elements in the database is theoretically 2 20 . Of course, in real situations, focal elements do not include a great number of hypothesis especially when they are expressed by human experts [START_REF] Denoeux | Induction of decision trees from partially classified data using belief functions[END_REF]. Thus, setting the maximum size of focal elements to 3 is sufficient to mimic real bbas. In our case, the number of potential focal elements in the whole of the database, when CARD = 20 and SF E = 3 is equal to

3 k=1 C k 20 = 1350.
In other words, even though the cardinality of the indexed attribute is equal to 20, being imperfect, the attribute may be affected until 1350 different focal elements rather than 2 20 = 1048576, i.e., all subsets composed of 1, 2 or 3 elements of a total of 20 values. Figure 6 shows the results of the experiment. Again, e-Tree benefits from its condensed representation of compound focal elements.

C. The perfect and the probabilistic cases

In experiment related to the variation of the imperfection rate (figure 5), we mentioned that accessing a perfect database (P CT IM P = 0%) using the e-Tree index, or the RID Lists index gives the same result in term of answer time. When Figure 6. Behavior of access methods when CARD varies compound focal elements are absent, then the two structures are identical. In this case, the two structures consist in a collection of RID Lists that store the rid couples of each attribute's value (that is singleton, with belief equal to one).

Moreover, even when SF E = 1 (see figure 3), for any P CT IM P > 0% and N F E > 1, the two structures have exactly the same behavior. That is, when the indexed attribute has bbas with exclusively singleton focal elements (SF E = 1), the two index structures are equivalent. Note here that with these parameters the database is probabilistic.

D. Influence of queries' types

In our experiments, we noted that efficiency of access methods depends on the nature of the user-query. There is an important difference between user-queries with simple condition, and the ones with compound conditions. Query that looks for the value A 3 is much more simple than the one that looks for the values A 1 or A 2 or A 3 . To answer to the second query, we must verify 2 3 = 6 possible combinations in our index. Consequently, we did an experiment on the behavior of our three methods when performing a simple query, and when performing a more complicated query, i.e., query with a compound condition. In this experiment, the query's condition involves the search of three values. Table V shows execution time for the three access methods relatively to the two queries. Note that even for the simple query, e-Tree based method is better than the RID Lists one. In fact, when we deal with a simple condition query, the access method scans only the nodes (in the e-Tree) and the lists (in the RID Lists) of the singleton focal elements. Since singleton focal elements are collected only in the first level of the e-Tree, the scan is done on a maximum of CARD nodes. However in the RID Lists index, singleton focal elements are stored with the compound ones, and so search is more costly.

V. CONCLUSION

In this paper, we introduced a new index data structure, called e-Tree, used to accelerate searching operations in ev-idential databases. The e-Tree structure stores for each focal element in the database, the identifiers of the records where the belief of the searched value is positive. A construction method, and a search method were defined. The experiments we led to evaluate this solution were promising.

Figure 1

 1 Figure 1. e-Tree corresponding to the table Disease

2 :

 2 (f e)) to the leaf corresponding to f e ; / * It corresponds to the last node visited for the last v in f e Searching a value V in e-Tree input : e-Tree, V as the searched value output: returned lines as a set of couples (rid, bel) for each child c in root.children[] do if c in subsets(V ,1) then ADD c.ridlists TO returned lines; SEARCH(c, V, 2, returned lines); end end

Algorithm 3 :

 3 The procedure SEARCH input : N as a node in e-Tree, V as the searched value, k as the searched level output: returned lines as a set of couples (rid, bel) for each child c in N.children[] do if PATH(c) in subsets(V ,k) then ADD c.ridlists TO returned lines; SEARCH(c, V, k + 1, returned lines); end end

Figure 2 .Figure 3 .

 23 Figure 2. Behavior of access methods when D varies

Figure 4 .Figure 5 .

 45 Figure 4. Behavior of access methods when N F E varies

Table I .

 I Diagnosis: AN EXAMPLE OF EVIDENTIAL DATABASE

	Id	Patient	Disease
	1	Robert	0.7 flu, 0.3 anemia
	2	Celina	0.7 (cancer,flu), 0.3 cancer
	3	John	flu
	4	Maria	(anemia,cancer)

Table II .

 II Diagnosis <disease= ′ f lu ′ >

	Patient	Disease	Bel
	Robert	0.7 flu, 0.3 anemia	0.7
	John	flu	1

Table III .

 III Diagnosis <disease= ′ f lu ′ > ACCORDING TO MODEL OF[START_REF] Lee | An Extended Relational Database Model For Uncertain and Imprecise Information[END_REF]

	Patient	Disease	CL
	Robert	0.7 flu, 0.3 anemia	[0.7,0.7]
	Celina	0.7(cancer,flu), 0.3 cancer	[0,0.7]
	John	flu	[1,1]

Table IV .

 IV RID LISTS OF TABLE Diagnosis

	Focal element	Rid List
	anemia	(1,0.3)
	{anemia,cancer}	(4,1.0)
	cancer	(2,0.3)
	{cancer,flu}	(2,1.0)
	flu	(1,0.7)(3,1.0)

Table V .

 V COMPARISON ACCORDING TO THE NATURE OF USER-QUERIES

	Access method	Simple condition query	Compound condition query
	e-Tree	101 msec	167 msec
	RID Lists	161 msec	211 msec
	Without index	307 msec	332 msec


Juliette Lemaitre
email: juliette.lemaitre@hds.utc.fr

Domitile Lourdeaux
email: domitile.lourdeaux@hds.utc.fr

Caroline Chopinaud
email: caroline.chopinaud@masagroup.net

Towards a resource-based model of strategy to help designing opponent AI in RTS games

Keywords: Strategy, Behavior Modeling, Game Design, Player Experience, Adaptation

come     Copyright Towards a resource-based model of strategy to help designing opponent AI in RTS games Juliette Lemaitre, Domitile Lourdeaux, Caroline Chopinaud

INTRODUCTION

The Artificial Intelligence (AI) used for non-player characters (NPC) in commercial video games does not take full advantage of the academic research that exists on the subject. Some games have used planning systems [START_REF] Orkin | Applying goal-oriented action planning to games[END_REF] or even learning algorithms, but they remains exceptions. The main reason lies in a clear difference in goals and constraints that causes the solutions developed by the research community to be inadequate for the industry.

Indeed, during game development, the design of an AI for the NPCs is commonly a low priority task. Other aspects, like 3D graphics and animation, account for most of the time and money available for game design. The lack of time also leads to the creation of AI solutions from scratch, specific to a single game, producing underexploited and non-reusable AI. Hence, introducing a new AI system into the design process requires proposing a reusable and easy to understand and use solution.

Some video games, for which AI is at the heart of the scenario, need to provide interesting and complex AI. This is the case with real-time strategy (RTS) games: their environments present multiple challenges, widely studied by the research community. But even if the required complex behaviors constitute a necessarily important part of the game design, simple but ill-adapted solutions like finite state ma-chines (FSM) and behavior trees (BT) are used to design NPCs' behaviors rather than more advanced technologies like genetic algorithms or planification. Thus, simple and accessible solutions to design AI are preferred, but this simplicity is not the only requirement for an AI system.

Indeed, BT and FSM not only offer easier comprehension but also control and reliability. Most of the solutions provided by the research community lack one of these criteria: sometimes they do not provide a solution, making the NPC inanimate; when they do provide a solution, it is often difficult, even impossible, to customize it to obtain the desired behavior. Indeed, while in research most of the studies aim to improve the results of the AI (faster or better behaviors than the opponent), the goal of a video game is also and for the most part to entertain the players. If the two goals are not completely incompatible, they are rarely satisfied by the same solutions. In a game an NPC can have several roles: opponent, partner, assistant, populating the environment... Each one can bring fun to the game in different ways, which is the difficult part because there is no consensus on the explanation of fun; but game research and the industry have tried to understand it and several definitions have appeared in the last few years.

In short, AI in games has to be simple to design, accessible for the game designer, reusable and suitable for designing attractive scenarios. These criteria mean that the design process for behaviors of NPCs in a game have to be easy for designers to test, control and customize to achieve the desired behaviors. In order to address this issue, we propose a solution to conceive and efficiently test collective behaviors, commonly called strategy in RTS games. In this paper we present a model to design strategies accessible to the game designers. The proposed model aims to be used to design behaviors that are adaptable, reusable and reliable. To address the specific issue of entertainment, a semantic layer is added to the behavior model to clarify the impact of the behavior on the game experience. After presenting the related work and its limits, we will present our behavior model and then discuss the perspectives we foresee for this work.

RELATED WORK

2.1 RTS Research [START_REF] Ontanon | A survey of real-time strategy game AI research and competition in StarCraft[END_REF] has gathered most of the work related to RTS games AI, separating the work from Starcraft AI competitions in the CIG and AAAI conferences, and the work done for research purposes.

Both round-robin and single-elimination tournaments proposed during the CIG and AAAI conferences focus on the performance of the competitors. The AI system of each participant competes against the others and the only parameter that will determine the winner is the percentage of winning games. Moreover, the architectures created for the events are adapted specifically for Starcraft, broken down into several parallel and hierarchical modules [START_REF] Ontanon | A survey of real-time strategy game AI research and competition in StarCraft[END_REF]. It shows the importance of decomposition of the decision task, but the specialization of the modules makes it difficult to reuse them in another environment. With our model, we aim to provide a strategy structure that can be used in diverse environments.

The RTS environment has become widely used as a testbed in game research because of the multiple challenges that emerge from it [START_REF] Buro | Real-time strategy games: A new AI research challenge[END_REF]. Multiple IA techniques have been tested for their effectiveness but often lack usability required for commercial use. For example [START_REF] Dereszynski | Learning probabilistic behavior models in real-time strategy games[END_REF] uses sets of game logs from Starcraft to produce hidden Markov models. The resulting behaviors depend entirely on probability which makes it unpredictable and limits the game designers control. Case-based planning in [START_REF] Ontanon | Case-based planning and execution for real-time strategy games[END_REF], studied more extensively in [START_REF] Palma | Extending case-based planning with behavior trees[END_REF], also fails to provide the necessary control over obtained behaviors and requires experts to create example libraries. Furthermore, both use a learning process which does not integrate well in the creation process of a video game. Indeed, a learning process can only be performed properly on a completed game. If an incomplete version is used, it is faster to restart the learning process from scratch than to adapt the previous result to the final version. Automated planning has also been used in game research, [START_REF] Churchill | Build order optimization in StarCraft[END_REF] uses it to optimize build order in Starcraft. The computing time and the vast search spaces in RTS games prevent it from being used for the entire decision mechanism. We would like to provide a reusable solution where the game designer has control over the AI produced and can understand the resulting behaviors.

Defining Fun

A lot of studies have tried to explain the meaning of fun and how it can be triggered. The most studied aspect of fun is the level of difficulty, which needs to be challenging, neither too easy, nor too hard, to stay between anxiety and boredom as defined in the theory of flow [START_REF] Nakamura | The concept of flow[END_REF]. Most of the studies resulted in classifications of kinds of fun, [START_REF] Malone | What makes things fun to learn? heuristics for designing instructional computer games[END_REF][START_REF] Lazzaro | Why we play games: Four keys to more emotion without story[END_REF]. [START_REF] Read | Endurability, engagement and expectations: Measuring children's fun[END_REF] defined 3 dimensions of fun: endurability, engagement and expectations. Other studies focus more on the player, [START_REF] Bartle | Hearts, clubs, diamonds, spades: Players who suit MUDs[END_REF][START_REF] Bateman | 21st Century Game Design[END_REF]. When comparing these classifications, we can find some similarities but no consensus has been made on which one is the most accurate and their use in the creation of behaviors is still unexploited even though fun is at the heart of game design. In our solution, we want to allow the designer to create a behavior that reacts and adapts to the player, so that it provides a fun and interesting experience.

PROPOSITION

The goal of our work is to provide an accessible strategy model in order to simplify the design of complex behaviors. A strategy is defined as the decisionmaking process of the allocation of available resources, such as agents or objects, to sub-tasks in the pursuit of an overall goal. Our model aims to facilitate the designing of reusable, reliable and easily extendible collective behaviors through the description of strategies. It will therefore fit into the creation process of a new video game, during which several modifications of the game mechanisms are applied and require the adaptation of every element, including the AI of the NPC. We want the model to be apprehensible, to the extent that the reason for the occurrence of an unwanted behavior can be spotted easily and solved in order to allow designers to manage the coherence, credibility and fun of the designed behaviors.

The Strategy Model

Our model aims to facilitate the creation of collective behaviors in RTS, and more generally the behaviors of several agents which need to be coordinated. To construct the overall behavior, that we call strategy, we use a hierarchical structure to allow decomposition into simpler sub-behaviors and thus handle scalability. A behavior is then composed of a set of sub-behaviors and the strategy can therefore be represented by a Directed Acyclic Graph (DAG) with a unique root node as shown in figure 1. All vertices without outgoing edges are primitive tasks, meaning that it can be directly applied in the virtual world. A behavior is defined by a set of behaviors or primitive tasks, its type, and the resources it needs. The type of a behavior can either be logical or parallel. The parallel type allows the expression of collective behavior while the logical type allows the AI to choose a behavior according to the state of the game.

To avoid complexity, it has been decided to clearly separate them by defining a behavior as either logical or parallel rather than permitting a mixture of both in a single behavior. The parallel type requires additional information about the distribution of resources between its different sub-behaviors. The logical one needs information about the decision-making process to choose only one of its different sub-behaviors at each evaluation. They are detailed in 3.1.2 and 3.1.3.

Primitive Tasks

Primitive tasks are the smallest part of the decomposition of a behavior. They cannot be decomposed, but each one is linked to a piece of code that allows it to run in the virtual environment. They are defined by a set of resources that are required for it to work. Each resource is defined by a tuple <R, Min, Max> where R is the type of resource defined with the resource model presented in 3.2, Min is the minimum amount required, and Max is the maximum amount possible and can be set to -1 if there is no maximum. This offers more flexibility than a fixed number and is more suited to evolving numbers of resources which is the case in RTS games. For example, to represent the task of construction, a primitive task can be created with the following resources:

<<worker, 1, -1>, <ground, 1, 1>>
In this way, several workers can work on a construction that requires a unit of ground. To handle failure, a status of ending, success or failure, is returned to the parent behavior so it can adapt accordingly.

Logical Behaviors

A logical behavior represents the logic of selection of a sub-behavior from several. Its execution consists of selecting the sub-behavior to be executed, according to the previous one executed and the current state of the virtual world. It is represented by a tuple <B, M, SB, CB> where:

B is the set of sub-behaviors M is the set of triggers <OB, T, DB> SB is the starting sub-behavior CB is the current sub-behavior A trigger is composed of a transition T that triggers the selection of the sub-behavior DB if OB is the current sub-behavior. The new sub-behavior DB can be one of the predefined sub-behaviors Success or Failure, in which case the transition causes the end of the logical behavior and a signal corresponding to the selected status is sent to the parent behavior.

The transitions can be internal or external signals, or information requests: internal signals are the success or failure feedback from the current subbehavior, external signals come from modules dedicated to the game, and information requests are represented by predicates. For example, an external signal can come from a module that manages the state of the world if the condition is a partial world state, or it can come from a module of player modeling if it depends on the player state. In the case of an information request, the transition is activated if the predicate is true. Signals are used for punctual events whereas information requests are used to check more static conditions.

Consider an example consisting of 3 subbehaviors: Explore, Fight, and Gather. We define Explore as the initial sub-behavior, then if enemies are encountered or food is found during the exploration, the sub-behaviors Fight or Gather, respectively, are selected. When fighting of the enemy or gathering of food terminates successfully, the Explore subbehavior is again selected. In case enemies are spotted during the food gathering, the fight behavior is the preferred selection. This example can be expressed as follows. Note that here Gather is the currently selected sub-behavior. A logical behavior can thus be represented as a directed graph that can be cyclic, the sub-behaviors being the nodes and M being the edges with OB as the origin and DB as the destination. A graph illustrating the example above is shown in figure 2.

Parallel Behaviors

A parallel behavior handles the distribution of resources between its sub-behaviors. It is composed of priority levels that are represented by a tuple <M, C> where M is the maximum number of times the priority can be executed in parallel and C is a set of components. Sometimes there is no need for a maximum value for M, especially when assigning default tasks to all the remaining resources with the lowest priority levels. In this case by convention we use the value -1 for M, simply to indicate that no limit is required. A component is described as a tuple <B, W> where B is a sub-behavior and W is a weight. The resources are allocated to the first levels as long as possible and until the number M is reached. The weights W are used during the distribution of resources among the sub-behaviors of the priority level, but are not useful when there is a unique sub-behavior. A sub-behavior can appear in several priority levels, but it cannot appear more than once in a priority level. The priority and weight mechanisms allow the description of the distribution of resources without knowing the exact amount of available resources. Considering table 1 as the selected behavior and that each of its sub-behaviors need only 1 soldier, if we suppose that 10 soldiers are available, the resource allocator will proceed as follows: first it will use 3 soldiers for the first priority level, 1 for fighting, and 2 for covering. As the number associated (2) is not attained, the resource allocator will continue with the first priority level and allocate 3 soldiers again, 1 for fighting and 2 for covering. The first priority level has reached its maximum number of executions, so the resource allocator goes to the second priority level and assigns a soldier to alert the others. The maximum number of executions is also reached, so the third priority level is selected. As it does not have a number associated, the remaining 3 soldiers are assigned to the task Explore.

The Resource Model

A resource can be an object, an agent, but also a location, or a skill. A hierarchy of resources is defined by the game designer. Only the leaves can be used when creating a resource, to define its type, but all the types can be used to define the requirements of a primitive task, meaning that when a resource is required to execute a behavior or a task, the type can be more or less specific. For instance, figure 3 represents a hierarchy of types of resources. An agent of the game can be a Soldier or a Worker, and the environment also includes resources of type Sword and Shovel. This means that a primitive task that requires 1 resource of type Agent can be performed by a Soldier or a Worker. More advanced options allow the game designer to indicate if a task requires 2 resources of type Agent that are of the same subtype, or of a different subtype, or that it does not matter.

A resource is defined by the following characteristics: its type cannot change during its lifetime; it can be destroyed or created by a primitive task; it can be modified through destruction then creation of a new resource.

Semantics

A semantic layer will be applied to the behavior to clarify for the game designer the impact of the behavior on the game experience. To do that, a typology of feelings resulting from the experience of play will allow the tagging of the behaviors, and the game designer will be able to create the desired experience in a logic behavior by selecting sub-behaviors tagged with the appropriate feelings. For example an external module can spot that the player plays a decreasing number of actions per unit of times, deducing that the player is becoming less involved, and send a signal that will trigger an aggressive behavior, causing a battle requiring the player to be more active.

A USE CASE

The following example utilizes our model to build a basic behavior in an environment which employs the most common mechanisms found in RTS games: a search is performed for mineral resources which can then be extracted for the creation of buildings and units (workers or soldiers). The buildings upgrade knowledge and allow the construction of more efficient soldiers. To simplify the understanding of the proposed behavior, we will only provide a detailed description of a small section of the overall strategy.

The overall strategy itself is shown in figure 4: the strategy begins by creating buildings until it is considered necessary to start preparing an army by creating soldiers, this eventually leads to an attack on the enemy. Several reasons can be found to start building an army: it can be a length of time, the number of buildings created, but it can also be triggered by intelligence, for example if the enemy is also preparing an army. If it is too late to prepare an army because the enemy has managed to surprise us, combat mode is engaged directly. The Combat sub-behavior can be described as a parallel behavior, as represented in table 2. The soldiers engage in combat but the workers will continue to collect and transform resources to create more soldiers. Here, every soldier that attacks an enemy is covered by another soldier. The Collect sub-behavior is the default behavior so it is placed in the last position. If there are not yet enough resources to create a soldier, the sub-behavior Create soldier will not be assigned to workers and they will all collect resources. As soon as there are enough resources to create a soldier, a worker will be assigned to the task. The sub-behaviors Fight and Cover are detailed in Figure 5 and Figure 6, respectively. The Fight behavior is relatively simple: shoot at the weakest enemy, and if no enemy is in range, move toward the nearest enemy soldier. The Cover behavior is a little more complex and requires external signals and information requests concerning the environment. It consists of finding a hiding place and placing the soldier behind it, ducking if necessary, then shooting at visible enemies, and finally moving on if the covered soldier has moved and the hiding place is no longer suited.

PERSPECTIVES AND FUTURE WORK

We have presented a model that makes building collective behaviour easy. The first step of our future work is to extend expressivity by adding functionality while retaining usability. One way to achieve this objective is to present the model to game designers, with a view to making improvements following the reception of feedback that describes their needs. Indeed this is the principle purpose of this model. The second step will focus on the semantic layer; its purpose is to highlight the player's experience in the conception of AI behaviors. The associated vocabulary needs to be defined, based on the work presented in section 2. The goal is to be able to automatically compute the type of experience that a behavior can provide, so part of the work will be to match experience types with the characteristics of behaviors that cause them.

CONCLUSION

In this paper we presented a model for the definition of strategic behavior for RTS games, whose specificity is to combine ease-of-use with the ability to produce high-performing strategic behaviors. The model uses hierarchy and parallelism to be easily understandable. The agents are used as resources, using proportion and priority to separate them on possible tasks, making it adaptable for variable resources. A strategy can easily be modified and sub-behaviors can be extracted and reused. The model is part of a bigger project which aims to provide a behavior generator, meaning that the system could give to the game designer a first strategy to work with, simply by defining the primitive tasks. Future work will focus on making it more accessible by adding a semantic layer.

Figure

  Figure 1: Strategy.

Figure 2 :

 2 Figure 2: Simple example of logical behavior.

Figure 3 :

 3 Figure 3: Resources hierarchy.

Figure 4 :

 4 Figure 4: Overall strategy of the example.

Figure 5 :

 5 Figure 5: Fight logical behavior.

Figure 6 :

 6 Figure 6: Cover logical behavior.

Table 1 :

 1 Simple example of parallel behavior.

	Maximum iterations Behavior Weight
	2	Fight	1
		Cover	2
	1	Alert
	-1	Explore

Table 2 :

 2 Combat parallel behavior.

	Maximum iterations Behavior Weight
	-1	Fight	1
		Cover	1
	-1	Create soldier
	-1	Collect


Lionel Bertaux

Samir Medjiah

Pascal Berthou

Slim Abdellatif

Akram Hakiri

Patrick Gelard

Fabrice Planchou

Marc Bruyere

Software Defined Networking and Virtualization for Broadband Satellite Networks

Keywords: Broadband Satellite networks, Software Defined Networking, Network virtualization, Network Function Virtualization, OpenFlow I

Satellite networks have traditionally been considered for specific purposes. Recently, new satellite technologies have been pushed to the market enabling highperformance satellite access networks. On the other hand, network architectures are taking advantages from emerging technologies such as Software-Defined Networking (SDN), network virtualization and Network Functions Virtualization (NFV). Therefore, benefiting communications services over satellite networks from these new technologies at first, and their seamless integration with terrestrial networks at second, are of great interest and importance. In this paper, and through comprehensive use cases, the advantages of introducing network programmability and virtualization using SDN and/or NFV in satellite networks are investigated. The requirements to be fulfilled in each use case are also discussed.

INTRODUCTION

Software-defined networking (SDN) is a new paradigm shift in communication networks, receiving an increasing attention from industry and academia. Similarly, network virtualization and Network Functions Virtualization (NFV) are gaining adhesion in the telecom industry. Coupled together, they pave the way to new opportunities in network design, operation and management.

Terrestrial and satellite networks have always evolved differently. On one hand, terrestrial networks are in constant evolution and are already moving to embrace SDN and NFV [1]. On the other hand, satellite networks have traditionally been considered for specific purposes or as a backup technology (in established markets such as air and sea coverage) and thus rely on technologies locked down by major actors.

Network programmability, openness and virtualization are the key words of today networking architectures. Adopting these principles in satellite communications can help reducing CAPEX and OPEX, enhancing the performance and the QoS delivered to satellite communication end-users, extending the range of applications of satellite communications, and achieving seamless integration with terrestrial networks.

In this paper, we investigate how SDN, network virtualization and NFV can enhance satellite architecture to achieve the aforementioned objectives. Through practical usecases, we demonstrate benefits resulting from the integration of these emerging paradigms into communication satellite networks. We also highlight necessary requirements that have to be fulfilled. This paper is organized as follows: background knowledge on software-defined networking, network virtualization and network function virtualization is presented in Section II. Section III gives a brief overview of the satellite network architecture considered in this study. Section IV details use-cases where SDN, network virtualization and NFV can be beneficial to satellite networks. Finally, Section V concludes on their global contributions to communication satellite networks.

II. BACKGROUND

A. Introduction to Software-Defined Networks Recently, SDN [START_REF] Bruyere | SDN Architecture Overview[END_REF] has emerged as a new approach for network programmability and management, where the centralized control plane logic is decoupled from the dataforwarding plane. SDN architectures define a new entity (called controller) that centralizes control intelligence of one or more network elements (basically switches) as shown in Figure 1. Various open interfaces [START_REF] Astuto | A Survey of Sofware-Defined Networking: Past, Present, and Future of Programmable Networks[END_REF] have been defined to communicate between control plane and data plane (South Bound interface), and OpenFlow [START_REF]OpenFlow Switch Specificationversion 1.4.0[END_REF] is a de-facto standard. On the North interface of the controller, applications can be deployed with a network-wide view of data path elements. SDN opens up new opportunities. Most notably, it simplifies network management [START_REF] Hyojoon | Improving network management with software defined networking[END_REF] and allows automated customized on-demand networking with optimal network resource utilization.

B. Network Virtualization

Network virtualization enables the creation and coexistence of multiple isolated and independent virtual networks over a shared network infrastructure [START_REF] Mosharaf | Network virtualization: state of the art and research challenges[END_REF]. A virtual network is a logical network with some of its elements (network devices (or nodes) and links) virtual. A virtual node is an abstraction of a network device that is often hosted on a single physical node. It executes network functions such as routing, forwarding, etc. by consuming part of the resources of the hosting node. The resources allocated to a virtual network device are as diverse as CPU, Volatile Memory, network interfaces, storage, switching, etc. Similarly, a virtual link is an abstraction of a network link that is established on one or multiple physical links or physical paths. It consumes transmission resources (i.e. physical links' bandwidth) as well as switching resources at the traversed physical nodes.

C. Network Function Virtualization

Historically, the telecom industry has always privileged the use of dedicated equipment to provide network functions. However, this model inevitably leads to long time to market delays and important costs. This model is being questioned by the NFV concept [7]. Indeed, NFV advocates the virtualization of network functions as software modules running on standardized IT infrastructure (like commercial off-the-shelf servers), which can be assembled and/or chained to create services. This approach makes use of the experience on server virtualization got from the cloud computing industry since a virtual network function may be implemented on one or more virtual machines.

The main benefits of NFV are reduction of CAPEX and OPEX and improved network agility.

III. SATELLITE NETWORK ARCHITECTURE

This work considers a typical Broadband Satellite Network (BSN) that provides a multi-beam coverage with forward and return links. The ground segment of the BSN gathers multiple Hubs that are interconnected via a dedicated backbone network with some PoPs (Point of Presence) or gateways to external networks, typically the Internet (see Figure 2). Generally, a Hub supports bidirectional traffic on one or many beams. It combines a Forward Link Transmission Unit (FL-TU) and a Return Link Reception Unit (RL-RU) with a Gateway (GW) to terrestrial networks, a Network Control Centre (NCC) and a Network Management Centre (NMC). The FL-TU performs baseband related functions like DVB-S2 coding and modulation with Adaptive coding and modulation (ACM). The Gateway is typically a full-featured IP router with a strong set of functions and protocols (e.g. support for various routing protocols, Network Address Translation, Access Control Lists (ACLs) and firewall services, SNMP, QoS, etc.). The NCC provides control functions; it typically performs Satellite Terminals (ST) admission control and resources control/allocation on the forward and return links. The NMC performs all management functions, i.e. network element's (ST, Hub) configuration, as well as fault, performance, accounting and security management. Performance Enhancing Proxy (PEP) designed to improve TCP performance over satellite links may also be co-located at the Hub (or deported at the PoPs or closer to end-users).

The successful delivery of satellite communication services to end-users involves one or many real-life business actors, each playing one or many roles (with the set of functional responsibilities they assume). Referring to [START_REF][END_REF], three major roles are distinguished:

• Satellite Operator (SO): it owns the satellite and assumes its operation. It leases satellite capacity at the transponder level (physical layer) to one or several SNOs.

• Satellite Network Operator (SNO): it operates a

broadband satellite network with one or more satellite transponders and one or more satellite hubs. It provides satellite forward and return links to second-tier operators by dividing transponder level bandwidth. The NCC controls this bandwidth sharing. Via the NMC, the SNO provides a management interface to the purchased resources. • Satellite Virtual Network Operator (SVNO): Based on the satellite links contracted from one or multiple SNOs, it builds and provides end-to-end higher-level added-value services that are made available via a satellite access.

IV. USES CASES

A. Use case 1 : Inter-hub handover with Site Diversity 1) Description and current practices

In satellite communications, the use of high frequency bands such as Ka or Q/V makes Adaptive Coding and Modulation (ACM) mechanisms mandatory to counteract signal degradation due to meteorological events like clouds or rain.

In case attenuation is extreme, throughput reduction due to ACM and induced network congestion may not be in agreement with QoS constraints of some flows (VoIP, video conference). If meteorological degradations are due to weather disturbances over ST localization, using robust coding mechanisms cannot be avoided. If degradations concern Hub localization, using another distant site should be considered. The concept of connecting (successively or not) a single ST to several Hubs is called site diversity.

Site diversity deployment can follow two different approaches as described in [START_REF] Jeannin | Smart gateways for terabit/s satellite[END_REF]. The N+P approach relies on P redundant Hubs that can replace failing sites, resulting in a full handover (HO) of users. The N+0 approach uses frequency multiplexing to serve ST with carriers from different Hubs, a failing site inducing losing the corresponding portion of frequency band.

Both cases raise some challenges if network service continuity with performance impairments must be guaranteed. Indeed, a hub change (case N+P) or a carrier modification (N+0) has to be signaled to STs and executed. Simultaneously, routing tables have to be updated in the terrestrial network. Also, the handover decision problem is complex since it may concern hundreds of STs and account for several criteria such as flow observation, network knowledge, changing channels quality, etc. Current satellite networks follow the N+P approach with handover performed for a whole beam at a time.

2) SDN opportunities for site diversity

Obviously, applying SDN principles in the context of site diversity can help devising an effective handover decision algorithm as well as easing the execution of the handover. Basically, this can be achieved with the following enhancements shown in figure 3: -SDN-enabled switches to replace GWs in Hubs, -One SDN (OpenFlow) master controller located in a hub site running the network application in charge of inter-hub handover management. For clarity reasons, one SDN controller is depicted in Figure 3, however the use of several controller entities should be considered for scalability and reliability purposes. -Interfaces to NCC and NMC exposed to the handover application that gather monitoring information and allow triggering some ST configurations -Optional: a SDN enabled backbone network The handover management application decides when a handover is needed (and the flows or STs that are concerned by the handover) based on:

-Flow constraints: QoS requirements, specific user SLA, -Flow monitoring: to identify active services, the performance and resources (satellite and backbone) that they are receiving; -Satellite network as well as terrestrial backbone network performance indicators -SNO/SVNO policy: emergency cases or super-user demands, Two options can be considered:

-"Direct Path Routing": Flows are routed directly from their new hub to the nearest PoP. -"Traffic Redirection": Flows are still passing through their home hub site after having been redirected, at their new hub, via the backbone network, This is achieved thanks to SDN related programmable functionalities that are added to the packet-processing pipe. For example, OpenFlow can dynamically deploy forwarding rules matching packets based on:

-Incoming network interface, -IP/MAC addresses, -Classes of services or protocols used, -Rate of identified flow or group, -Deep Packet Inspection (DPI) using legacy functions.

In conclusion, SDN doubtless contributes to present and future satellite networks by easing the management of interhub handover enabled by site diversity, but also, by extending its capabilities.

B. Use case 2 : Enhancing VNO services 1) Description and state of the art

The need for Virtual Network Operator (VNO) services is clear and not new. VNO services allow SNOs to partition their satellite resources between multiple SVNOs efficiently by delivering dedicated satellite capacities with different levels of QoS guarantees. Typically, SVNOs in turn repackage these services to provide their customers with added-value end-to-end services. This business model has been for a while in the satellite market landscape. However, the level of control that SVNOs have on their purchased services (and underlying resources) is limited mainly because of the closed nature of satellite devices and the management interface between SNOs and SVNOs. Figure 4 presents on the one hand, the Network Management System (NMS) used by a SVNO, and on the other hand the SNO's NMC that manages the NCC, GW as well as all STs. Even if some management functionalities can be done directly from SVNO's NMS to its STs (e.g. routing, etc.), most must go through the NMC (e.g. to get STs' status and statistics). To this end, a management interface (I.SNO-SVNO) is provided by the SNO as part of the VNO service to let the NMS manage SVNO's satellite terminals. This interface is usually SNMP based complemented with some vendor specific solutions.

Figure 4 -SNO and SVNO Management relationships

The VNO services provided to SVNOs are dependent on the level of visibility and control capabilities exposed by the I.SNO-SVNO management interface that is far from being comprehensive. Moreover, some control capabilities require human intervention from the SNO to validate or perform the required configuration. From the SVNOs perspective, this refrains the development of novel services and complicates the provision process of the services they offer.

2) Network virtualization and network programmability opportunities for VNO services

SVNOs are asking for more control on their resources with reduced (if no) intervention from the SNOs. The issues are (1) quicker automated service provisioning processes, (2) enriching their service catalogue, and (3) enabling Satellite Communication as a Service consumption model.

Opening satellite devices via programmatic interfaces (with a rich set of instructions that goes beyond SNMP capabilities) exposed to second tier operators coupled with network virtualization is the way to follow in order to fulfill these goals. By applying device virtualization (i.e. server virtualization applied and adapted to network devices) to SNO satellite hubs, a virtual Hub can be assigned on a per SVNO basis (see Figure 5). With the guarantees brought by isolation -which is a key feature of network virtualization, and applies to data, control and management planes as well as to performance and security) -a SNO can delegate the full control and management of virtual hubs to their customer SVNOs. Therefore, SVNOs can independently enforce their own policies on their satellite virtual networks. Having the control on the NMC to NMS management interface (the range of its capabilities), SVNOs can make the provisioning process of the services delivered to their customers fully automated. Indeed, a provisioning engine can be used to orchestrate and perform all the required configurations by accessing the above-cited interface. Moreover, dynamic SLA can be easily supported. Indeed, a SVNO subscriber may ask via a secured portal to dynamically change his bandwidth requirement, the provisioning engine can then autonomously take the right configuration actions to provide and enforce the newly requested SLA within a time frame of few minutes (in fact, such service exists but with higher response times, often with human in the loop). New services, such as you pay what you use services can also be considered.

Figure 5 -Hub virtualization

A further step can be achieved by introducing programmability thus enabling a programmable virtual hub assigned to SVNOs. Programmability may concern the control plane (routing, forwarding, monitoring as stated in SDN) allowing SVNOs to devise their own customized traffic control schemes but also the data plane allowing SVNOs to devise customized packet processing algorithms (e.g. PEP, encryption). It paves the way for the diversification and enrichment of the services that SVNOs provide.

The road to programmable virtual satellite networks is just in its beginning. Network device virtualization with the stringent level of isolation that is required by satellite operators needs to be defined in order to extend the scope of the SVNO to SNO management interface (i.e. I.NMC-NMS). Some vendors already provide some form of Hub virtualization; it mainly concerns the gateway (GW) and the management center (NMC) with dedicated I.NMC-NMS to SVNOs. Extending the application of some form of virtualization to the other hub's elements is technically tractable within a reasonable time frame. But, devising a Hub virtualization technique that allows a comprehensive management interface between SNOs and SVNOs is still a research topic. Similarly, programming capabilities need to be identified and defined both at the control plane where SDN/OpenFlow capabilities need to be extended or completed with accompanying protocols, and possibly, at the data plane. This is another research topic with outstanding issues.

C. Use case 3 : Satellite and Terrestrial Networks Integration 1) Description and state of the art

Whether to provide data backhauling (mobile, military, marine, etc.), or to efficiently deliver communications services, along terrestrial access networks, in some deployments environments known as "gray areas" (areas with a limited internet connectivity i.e. <512Kbit/s), hybridation of different access networks with satellite would help providing an efficient service offer. Some of its advantages include:

-Capacity aggregation: some applications may require more bandwidth than what a single link provides. In this case, multi-link transmission will help achieving the total required bandwidth. To improve service quality, the additional links may be used to serve a specific purpose e.g. error correction data. -Load balancing: Data flows from different applications may be forwarded through different links in order to keep the link utilization at its lower level. Similarly, in order to enhance service functionality, the choice of link can be application driven.

To make such solution a reality, the system architecture should provide a fine-grained control over the carried data flows. Indeed, the ability to dispatch any data stream or any portion of it over the best link is essential. This routing should be done in a seamless fashion to the deployed applications. Nowadays, such control can be sought through a complex combination of various techniques such as Policy-Based Routing (PBR), multi-link protocols (MLPPP, SCTP, etc.), and traffic identification mechanisms (Packet marking, DPI, Layer-7 filters, etc.). However, it is worth to notice that all these techniques fail to provide the necessary control level for data flows dispatching over different links. Moreover, their behavior lacks dynamicity since forwarding rules are static and do not take into account the evolving link conditions and applications flows.

2) SDN-Enabled Satellite/ADSL Integration

SDN paradigm can play an important role in such solution. Indeed, SDN-based implementation of the hybrid architecture can bring the appropriate control level that current protocols and mechanisms cannot efficiently achieve. Moreover, since packets forwarding decisions are made upon matching rules on packets headers, convergence between the different involved networks, running different communication technologies, can be either achieved at level 3 or at a lower level (level 2). Figure 6 gives an overview of a network architecture that makes use of both an ADSL access network and a bidirectional satellite network. In this architecture, the global Network Provider (NP) operates both access networks. In this scenario, the network operator deploys SDNenabled devices within its network infrastructure, but also at the customer/user premises. Indeed, in this case, the home gateway becomes SDN-enabled and operates under the supervision of an SDN Controller hosted at the network operator. Thanks to a network application running on top of the SDN controller, data flows dispatching can be achieved at either the forward or the return links.

In the context of triple-play services over hybrid Satellite/ADSL architecture, the freedom in packet forwarding brought by SDN (i.e. OpenFlow packet forwarding rules) enables various scenarios. For example, when starting a phone call and in order to meet the QoS requirement of VoIP, lowlatency link (e.g. ADSL) can be temporarily and dynamically reserved to voice packets while all other data packets being transmitted over this link are redirected to the satellite link.

However, an SDN-based solution has the following requirements:

-Data flow identification: for efficient flow dispatching, the control application needs to identify the services data flows based on parameters such as: IP addresses, port numbers, TOS, or any byte pattern in packets headers or payloads. Thanks to OpenFlow rules expression, such patterns can be easily implemented. -Link monitoring: the control application needs to constantly monitor the links in terms of latency, available bandwidth, etc. in order to optimize the data flows dispatching. OpenFlow in its version 1.3 introduces metering tables, a powerful tool to gather per switch port or even per data flow statistics. -Dynamic forwarding rules generation and update: the control application needs to react to any changes in the links conditions and generate/deploy the appropriate forwarding rules or update the already established ones.

Finally, SDN can make hybrid architecture more efficient and ease its deployment. Moreover, it will enable novel and innovative services and applications. This use case is already a reality since SDN-enabled switches (e.g. OpenFlow compatible switches) are already on the market, however the hybridization applications and strategies have to be developed. SDN enabled hybrid and integrated setup boxes must also be proposed.

D. Use case 4 : middleboxes virtualization

Middleboxes are prevalent in the Internet architecture, and especially within specific networks such as satellite communication networks. These smart entities are used for various purposes as performance optimization, security, and address translation. This section analyzes how NFV can improve the classical PEP functions in satellite networks.

1) TCP performance optimization.

The TCP/IP model was shown to be not optimum, in terms of performance, in certain WAN and particularly in constrained environments, such as satellite networks. Various TCP protocol versions targeting satellite networks were proposed with the objective of improving the performance of TCP. They were, however, confronted with issues related to their deployment on user terminals. The solution that was found and which is still in use today is to insert devices, at the boundaries of the satellite network, to transform the operation of TCP into a satellite compatible version. These devices, called Performance Enhancing Proxy (PEP) [START_REF] Border | Performance Enhancing Proxies Intended to Mitigate Link-Related Degradations[END_REF], were spread in the satellite networks, offering by the same occasion advanced services such as Web Caching.

Protocol optimizations provided by PEPs are not compatible with several scenarios, in particular, in military or aeronautical contexts where security and mobility constraints are present. For instance, implementing a mobile architecture, such as mobile IP, poses complex problems to solve for PEPs. The most problematic case happens during a hybrid handover, i.e. from a satellite network requiring PEP optimization to a network where it is no longer necessary (and potentially counter-productive). In this scenario, TCP connections managed and accelerated by a PEP should survive to a deactivation of the PEP (or more generally to a change of PEP). However, PEPs are physically locked to the infrastructure and cannot move to follow the end-user. Solutions to this problem are proposed in [START_REF] Dubois | Enhancing TCP based communications in mobile satellite scenarios: TCP PEPs issues and solutions[END_REF] for hybrid satellite/terrestrial; they require context exchanges between PEPs.

Other middleboxes that provide advanced services in satellite networks (NAT, firewall, security, etc.) are also subject to the same issues.

2) PEPs and Network Function Virtualization

The Network Function Virtualization paradigm aims at implementing data-plane processing or control-plane functions in high volume data centers or network elements. This open a new era in thinking middleboxes, as they could be easily deployed, on demand, and under the control of an operator to provide advanced services. Moreover, these middleboxes could be mobile, as it is only relying on software that can be migrated from a standard server to another.

Considering use case #1 presented above (on site diversity), PEPs are typically implemented in the satellite hubs. When a Satellite Terminal hands over to a new hub, its TCP connections that cross the PEP will be broken as the new PEP will not be aware of connections' contexts.

With the NFV paradigm, PEPs will no longer be implemented as a dedicated middlebox but rather in software that can be run on different devices. Moreover, the PEP function can be dedicated to a communication context (dedicated to an ST for instance) and can be tuned according to the application requirements (security, mobility, performances, etc.) If an ST makes a handover from one satellite hub to another one, its "dedicated virtual PEP" will migrate to the new hub and will continue to perform the appropriate TCP optimization.

Several cloud computing platforms support NFV and already offer a solution to deploy Virtual Network Functions (VNF). Virtual functions implementing TCP optimization and acceleration for web application servers are proposed by some vendors. From a technical perspective, PEP virtualization can shortly become a reality.

V. CONCLUSION

Through the description of four real world use cases, this paper has shown some opportunities brought by the SDN and NFV paradigms to broadband satellite networks as well as their impacts on typical satellite system architecture. SDN and NFV are complementary solutions. SDN brings flexibility, automation and customization to the network. NFV brings agility in the delivery of services and reduces time-to-market development of new services. There is no doubt that they will take a central place in future satellite communication systems.

Figure 1 -

 1 Figure 1 -Network vision with the Software-Defined Network (SDN) approach.

Figure 2 -

 2 Figure 2 -Satellite Communication Architecture.

Figure 3 -

 3 Figure 3 -SDN architecture of terrestrial network in site diversity context Once handover of certain flows or STs is decided, the application automatically: -Informs concerned ST and FL/RL-TU to change their frequencies if needed, -Updates forwarding rules in the GWs and backbone network.

Figure 6 -

 6 Figure 6 -SDN-Enabled Satellite/ADSL Hybrid Architecture

ACKNOWLEDGEMENTS

This work is partially funded by the French National Research Agency (ANR), the French Defense Agency (DGA) under the project ANR DGA ADN (ANR-13-ASTR-0024) and the French Space Agency (CNES).

BIOGRAPHIES

Lionel Bertaux received a PhD (2013) in computer science from the University of Toulouse, France. He is a postdoctoral researcher at the Laboratory for Analysis and Architecture of Systems of the French National Centre for Scientific Research (LAAS-CNRS).

Samir Medjiah received a PhD (2012) Fabrice Planchou graduated from ENSEEIHT (Toulouse, 1990), belongs to Airbus Defence & Space (ex-Astrium) since 1990, dealing with telecom space systems. He heads an engineering team devoted to R&T and satellite telecom system validation. His main interest is the promotion of space systems within the telecom service market. Main researches and developments are based around terrestrial/satellite hybrid systems, mobiles systems, for both broadband and broadcast services, and also the M2M domain.

Marc Bruyere Marc Bruyere is a Technical Consultant at Dell-Force10 and a Phd student at the LAAS /CNRS at Toulouse. In 1996 he worked for the ISP Club-Internet.fr. He worked for Cisco, Vivendi Universal, Credit Suisse First Boston, Airbus/Dimension Data, Force10 Networks and Dell. He is a Cisco Certified Internetwork Expert #16651. He is involved in the NetFPGA project for few years and his thesis is about a new architecture for IXP OpenFlow/SDN environment.


M El Kodadi

Fouad Malek

Abdelkrim Ramdani

Driss Eddike

Monique Tillard

Claude Belin

Mohamed El Kodadi

Synthesis, Crystal structure and catecholase activity

published or not. The documents may come   L'archive ouverte pluridisciplinaire

ABSTRACT: A new tripodal ligand, N,N-Bis(3,5-dimethylpyrazol-1-ylmethyl)-1hydroxy-4-aminobutane (bpmhb), has been synthetized. Reaction of (bpmhb) with Copper (II) chloride dihydrate [CuCl 2 , 2H 2 O] in methanol produced the new complex Cu(bpmhb)Cl 2 . The complex crystallizes in the monoclinic system, space group P2 1 , the cell dimensions are a = 7.990 Å, b = 14.620 Å, c = 8.590 Å, α = 90°, β = 95.80°, γ = 90°, V= 998.3 Å 3 and Z =2.

The single-crystal X-ray structure of the title compound, N,N-Bis(3,5-dimethylpyrazol-1ylmethyl)-1-hydroxy-4-aminobutane Copper(II) dichloride shows that the surrounding geometry of the copper (II) ion can be described as being intermediate between a distorted square pyramid and a trigonal bipyramid. The OH group function form an intramolecular hydrogen bonding with the chloride atom Cl 1 . With molecular oxygen as oxidant, this complex catalyzed the conversion of catechol to quinone with a good catalytic activity. Keywords: Crystal structure, copper complex, tripodal ligand, pyrazole, oxidation, catalysis.

INTRODUCTION:

Notable progress has been made to mimic tyrosinase activity using copper complexes coordinated to multidentate heterocyclic amine ligands [START_REF] Karlin | Bioinorganic Chemistry of Copper[END_REF]. The binding ability and reactivity properties of the synthetic complexes towards small molecules can be readily modulated and compared to the biological systems.

Hemocyanin and tyrosinase have been studied in detail [START_REF] Robb | Copper Proteins and Copper Enzymes[END_REF][3][START_REF] Wilcox | [END_REF], tyrosinase is found widely in mammals, plants, bacteria, and fungi. It acts as both a monooxygenase through the hydroxylation of phenols to catechols and as an oxidase via the further oxidation of catechols to quinones. The copper centers of metalloproteins catalyze a variety of substrate oxidation or oxygenation reactions or bind and transport dioxygen [5], leading to extensive efforts by bioinorganic chemists to learn about the structures and mechanism of action of the protein active sites [6]. This approach involves the synthesis and characterization of low molecular weight compounds that can duplicate the protein active sites and mimic their functional attributes [6].

In previous papers we have reported the synthesis and crystal structures of [N,N-

Bis(3,5-dimethylpyrazol-1-ylmethyl)-1-hydroxy-2-amino ethane] copper(II) dinitrate [Cu(bpmhe)(NO 3 )L 0 ] (NO 3 ) [7] and [N,N-Bis(3,5-dimethylpyrazol-1-ylmethyl)-1-hydroxy- 2-amino ethane] copper(II) dichloride [Cu(bpmhe)Cl] 2 . 2[Cl, H 2 O] [8].
In this paper we describe the preparation of the new tripodal organic ligand [N,N-Bis(3,5-dimethylpyrazol-1-ylmethyl)-1-hydroxy-4-aminobutane] (bpmhb) capable of donating three nitrogens (two pyrazoles and one aliphatic) per metal as well as the synthesis, the characterization by X-ray analysis and the catecholase activity of his copper (II) complex Cu(bpmhb) Cl 2 .

RESULTS AND DISCUSSION

Synthesis of (bpmhb):

The synthesis of the new tropical nitrogen ligand (bpmhb) was carried out by condensation of 2 equivalents of 1-hydroxymethyl-3,5-dimethylpyrazole and one equivalent of 4-aminobutanol in the absence of solvent for 3 hours at 60°C. The compound was obtained with excellent yield (90%).

without solvent N N C H 3 CH 3 O H O H N N N C H 3 CH 3 N N C H 3 CH 3 bpmhb O H NH 2 3h /

X-ray experiment:

On a bulk synthetised , some crystals were selected and checked for singularity by preliminary oscillation and weïssenberg photographs. The best diffractant crystal was used for intensity measurements on a CCD diffractometer (Xcalibur, Oxford Diffraction), it displays The strain imposed on the metal coordination environment by the tripodal ligand is reflected in the chelate angle N 1 -Cu-N 3 of only 79.8(7)° and N 1 -Cu-N 4 of 81.4(6)° wich are similar to those observed in other pyramidal complexes (averaging 79.03(15)° when the ligand is N,N-bis(pyrazol-1-ylmethyl)benzylamine [START_REF] Burnett | ORTEP3: Oak Ridge Thermal Ellipsoid Plot Program for Crystal Structure Illustrations[END_REF].

The Cu-N 1 and Cu-N 3 bond distances (respectively 2.190(13) and 1.976( 15)) are similar to those found in other pyramidal complexes CuLCl 2 [START_REF] Burnett | ORTEP3: Oak Ridge Thermal Ellipsoid Plot Program for Crystal Structure Illustrations[END_REF]

Catalytic activity for the oxidation of catechol:

The catalytic oxidation of catechol has been studied as a model reaction for the catecholase activity of tyrosinase and catechol oxidase [15][16][17][18]. It has been shown that rigidity planar mononuclear complexes are not active as catalysts while non-planar complexes will catalyze the oxidation [19]. Since our complexes are non-planar, we anticipated that they would catalyze this reaction. The kinetic studies on the oxidation of catechol were carried out by the method of initial rates by monitoring the increase in the characteristic quinone absorption band at 390 nm under air as a function of time. The metal complex (0.3 ml of a 1 x 10 -3 M methanol solution) and a 2.0 ml solution (1 x 10 -1 M methanol solution) of catechol were equilibrated separately to 25 °C and then added together in a spectrophotometric cell at 25 °C. Figure 2 shows the dependence of the reaction rates on the catechol concentration for the oxidation reaction catalyzed by three copper (II) complexes while the activities are shown in table 3. 0 , 0 0 , 1 0 , 2 0 , 3 0 , 4 0 , 5 0 , 6 0,0

CONCLUSION:

We report the synthesis of a new tridentate ligand, bpmhb, with a functional hydroxy group and its copper dichloride complex. The geometry of the Copper (II) ion can bee described as being intermediate between a distorted square pyramid and a trigonal bipyramid.

The OH group well arranged to form an intramolecular hydrogen bonding with the chloride atom Cl 1 .

In summary, the tree complexes catalyze the oxidation of catechol to quinone but at different rates. These results show that variation in the arm lengths does drastically affect the catalytic properties of the resultant copper complex. Work is in progress to ascertain the relationship between the structures of the complexes and their reactivity.

EXPERIMENTAL:

General:

The melting point was measured on a BUCHI 510 apparatus and is uncorrected.

Proton NMR spectra of the compound bpmhb dissolved in CDCl 3 , was obtained with an AC 200 MHz Bruker spectrometer. Infrared spectra were recorded in KBr pellets using a Perkin-Elmer 1310 infrared spectrophotometer. UV-Visible spectra were followed by JAS.CO 7800.

The crystal structure data was collected on CrysAlis CCD diffractometer at 173°K

Synthesis of [bpmhb]:

A mixture of 1-hydroxymethyl 3,5-dimethylpyrazole (2gr, 16 mmol) and 4-amino-1butanol (0.72gr, 8 mmol) placed In a tree necked round bottom flask equipped with a condenser was heated for 3 hours at 60°C with Marie bath. The reaction mixture was extracted with dichloromethane and washed with water to eliminate the residual butanolamine. The solvent of the dried organic solution was eliminated under reduced pressure to give a white solid.

RESUME:

  Un nouveau ligand, tridenté N,N-Bis(3,5-diméthylpyrazol-1-ylméthyl)-1hydroxy-4-aminobutane (bpmhb), a été synthétisé. La réaction de (bpmhb) avec le chlorure de cuivre (II) dihydraté, (CuCl 2 ,2H 2 O) dans le méthanol conduit au nouveau complexe Cu(bpmhb)Cl 2 . Ce complexe cristallise dans le système monoclinique, groupe spatial P2 1 , les paramètres de maille sont : a = 7.990 Å, b = 14.620 Å, c = 8.590 Å, β = 95.80°et Z = 2.L'étude en diffraction de rayons X sur monocristal de ce complexe montre que la coordination du cuivre peut être décrite comme intermédiaire entre une pyramide à base carré déformée et une bipyramide à bases triangulaires. Le groupement hydroxyle forme une liaison hydrogène intramoléculaire avec l'atome de chlore Cl1. Avec l'oxygène moléculaire comme oxydant, ce complexe catalyse la conversion du catéchol en quinone avec une bonne activité catalytique.

2 :

 2 Scheme1

  the monoclinc system, space groupe P2 1 , with parameters a = 7.990Å, b = 14.620Å and c = 8.590Å, α = 90°, β = 95.80° and γ = 90°.The recorded frames, with theta max = 25.62° gave a total of 5918 reflections of wich 1693 were unique and 1689 observed. All crystallographic and data collection parameters are given in Table1

- 5 [Figure 2 :

 52 Figure 2: Dependence of the initial rate of the quinone production on the concentration of substrate, catechol, at constant concentration of catalyse (1 x 10 -4 M) in methanol.

Table 1 :

 1 Crystal and experimental data of Copper(II) complex Cu(bpmhb)Cl 2 .Addison et al[START_REF] Sheldrick | SHELXL97: A computer program for refinement of crystal structures[END_REF], were β is the largest angle and α the next in the Cu(II) coordination sphere, gives a value of 0.405 between the values of τ = 0.0 for a regular square pyramid and

	Empirical formula	C 16 H 27 Cl 2 Cu N 5 O
	Formula weight	439.88
	Temperature	298(2) K
	Wavelength	0.71073 Å
	Crystal system	Monoclinic
	Space group	P2 1
	Unit cell dimensions	a = 7.990Å α = 90°
		b = 14.620Å β = 95.80°
		c = 8.590Å γ = 90°
	Volume	998.3 Å 3
	Z	2
	Density (calculated)	1.463 Mg/m 3
	Absorption coefficient	1.376 mm -1
	F(000)	458
	Crystal size	0.50 x 0.40 x 0.20 mm
	Theta range for data collection	2.92 to 25.62 °.
	Index ranges	-9<=h<=9; -16<=k<=16; -10<=l<=10
	Reflections collected	5918
	Independent reflections	1693 [R(int) = 0.1130]
	Reflections observed (>2σ)	1689
	Data Completeness	0.484
	Absorption correction	None
	Refinement method	Full-matrix least-squares on F 2
	Goodness-of-fit on F 2	1.170
	Final R indices [I>2σ(I)]	R 1 = 0.0914 wR 2 = 0.2296
	R indices (all data)	R 1 = 0.0916 wR 2 = 0.2297
	Absolute structure parameter	0.0(4)
	Largest diff. peak and hole	0.863 and -0.560 e.Å -3

  If the function alcohol doesn't participate in the coordination of the copper ion because of the length of the side chain, the hydrogen atom is well arranged to form intramolecular hydrogen bonding with the chloride atom Cl 1 , with O to Cl 1 distance of 3.153(19) Å .

	and [Cu(ddae) Cl 2 ].C 2 H 5 OH
	[14] 2.182(4) and 2.181(4) respectively.

Table 3 .

 3 Kinetic data for the oxidation of catechol by copper complexesThe three complexes catalyze the oxidation of catechol to quinone but at differentrates. The complexes [Cu(bp1mae)Cl] 2 . 2[Cl, H 2 O] [8] and [Cu(bp1mae)(NO 3 )L 0 ].(NO 3 ) [7]in which the OH participate to the complexation of the copper shows similar Turnover (min -1 ) (of 16.1 and 15.40 respectively), but the [Cu(bpmhb)Cl 2 ] complex in which the function alcohol doesn't participate in the coordinaton of the copper ion because of the length of the side chain, shows significant catalytic activity.

	Complex	Activity (μmol substrate/mg	Turnover	K M (mol/l )	Vmax
		catalyst per min)	(min -1 )		(mol/l/min)
	[Cu(bpmhe)Cl] 2 . 2[Cl, H 2 O]	24.38	16.10	0.084	2.74 10 -5
	[Cu(bpmhe)(NO 3 )L 0 ]. (NO 3 )	27.48	15.40	0.073	2.62 10 -5
	[Cu(bpmhb)Cl 2 ]	56.97	25.04	0.047	4.25 10 -5

X-Ray structure Determination:

The crystal structure solution of the title compound was carried out with SHELXS97 [9] using Patterson method. The copper, chlorides and some nitrogen atoms are determined.

The other Non-hydrogen atoms were found by Fourier difference synthesis. The atomic parameters and anisotropic temperature factors were refined using full-matrix least squares methods of SHELXL97 [10]. Hydrogen atoms were positioned via HFIX. The final agreement factor is 0.0914. The molecular viewer used is ORTEP3 [START_REF] Sheldrick | SHELXS97: Program for crystal structure solution[END_REF]. The Cu(II) ion is coordinated to two pyrazole nitrogens, at 1.942(15) Å and 1.976 (15) Å, two chlorine ions at 2.390(4) Å and 2.291(4) Å and an amine nitrogen at 2.190 [START_REF] Burnett | ORTEP3: Oak Ridge Thermal Ellipsoid Plot Program for Crystal Structure Illustrations[END_REF]

Synthesis of [Cu(bpmhb)Cl 2 ]:

The Copper (II) complex was prepared by the addition of a solution of tridentate ligand bpmhb (0.305gr; 1mmol) in methanol (3 mL) to a solution of the Copper(II) dichloride[CuCl 2 , 2H 2 O] (0.1704gr; 1mmol) in methanol (3 mL). The resulting solution was filtered and allowed to stand at 25°C. Green crystals formed after a few days, which were filtered and washed with small amounts of cold methanol and dried in air (118.8mg); melting point: 180-182°C (methanol); IR (KBr, cm -1 ): 3480, 3320, 3080, 2900, 2740, 2720, 1610, 1550, 1440, 1390, 1290, 1260, 1150, 1110, 1080, 1060, 980, 870, 810. UV-Vis (CH 3 OH; λ max , nm (ε, M -1 cm -1 )): 205(10500); 232.5(8906); 250(8437); 737.5(44).