Pierre-Édouard Portier

Noureddine Chatti

Elöd Sylvie Calabretto

Jean-Marie Pinon

MODELING, ENCODING AND QUERYING MULTI-STRUCTURED DOCUMENTS

Keywords: Multi-structured document, XML, MultiX, Multi-structured Document Querying, XQuery

INTRODUCTION

1.1 DOCUMENT STRUCTURING Document structuring is used in many applications such as document exchange, integration and information retrieval. Several types of structures (physical, logical, semantic …) [START_REF] Nanard | Adding macroscopic semantics to anchors in knowledge-based hypertext[END_REF] [START_REF] Poullet | Semantic Structuring Of Documents[END_REF] have been defined for several specific uses. Moreover, a document can actually be a vehicle for various media types that can themselves introduce other structural layers (such as the temporal dimension of an audio track).

A single document can be used in many contexts. Thus, its content might be presented through many structures. In this case, the structures are said concurrent or parallel, since they share the same content. Humanities provide numerous instances of such structures. For example, the study of medieval manuscripts often implies the creation of concurrent hierarchical structures. First, we can consider a ubiquitous and trivial case of overlapping: the physical book-structure of a manuscript (a sequence of pages, columns, lines, etc.) and its syntactical structure (a sequence of sentences, words, etc.). Less trivial would be a structure of the sequences of damaged characters. Figure 1 is an extract of such a medieval manuscript fragment with its transcription. It should be noted that damaged characters are overlapping with words and words are overlapping with lines. The emphasis on multi-structured documents comes with the possibility of formally encoding documentary structures with digital representations. The fact that we find numerous examples of multistructured documents in the TEI (Text Encoding Initiative) guidelines (TEI Consortium, 2011) should prove it. Among those examples, we can mention in verse drama, the structure of acts, scenes and speeches that often conflicts with the metrical structure. Indeed, poems often provide multiple concurrent structures. Poem 1 is an example of two stanzas from a poem by Lewis Carroll 1 with verses, speeches, and syntactic elements producing overlapping concurrent structures.

POEM 1 TWO STANZAS FROM THE HUNTING OF THE SNARK BY L. CARROLL FIGURE 1 A FRAGMENT OF AN OLD MANUSCRIPT AND ITS TRANSCRIPTION

1.2 CONSTRUCTION OF MULTI-STRUCTURED DOCUMENTS

INTRODUCTION

The work presented here will deal with the central issue of encoding multi-structured documents. However, in order to make clear the advantages of our model over existing solutions, we now introduce the important but little-studied problem of the construction of multi-structured documents. Indeed, in a large majority of real life situations, documents are not a priori given but have to be constructed. Moreover this construction is in most cases the work of a team. Thus, it is to be expected that the partition of the annotations in a number of different structures comes from this collaborative work. In other words, the construction of multi-structured documents is a dynamic process. How do structures emerge? How to check on their coherence? … In order to tackle these important issues, we need an adequate encoding for multi-structured documents.

In a previous work (Portier & Calabretto, Creation and maintenance of multi-structured documents, 2009) (Portier & Calabretto, DINAH, a philological platform for the construction of multi-structured documents, 2010) we explicitly studied the construction of multi-structured documents. Although the formal representation we then used was based on RDF rather than XML, this previous work offers a well-adapted and non-trivial applicative context for the XML based model we now propose. Moreover it gives us the opportunity to motivate the key choices behind our proposition.

CONTEXT

We studied how multi-structured documents are constructed in a multi-users context composed of philologists. Our work is based on experience gained working with Humanities researchers building digital editions of large archives of (mainly handwritten) manuscripts from various epochs. Digital editing covers the whole editorial, scientific and critical process that 1 http://www.gutenberg.org/files/13/13-h/13-h.htm "What's the good of Mercator's North Poles and Equators, Tropics, Zones, and Meridian Lines?" So the Bellman would cry: and the crew would reply "They are merely conventional signs! "Other maps are such shapes, with their islands and capes! But we've got our brave Captain to thank:" (So the crew would protest) "that he's bought us the best-A perfect and absolute blank!" leads to the publication of an electronic resource. In the case of manuscripts, editing mainly consists in the transcription and critical analysis of digital facsimiles, that is to say, the creation of a textual document associated with the images of a handwritten manuscript. We discovered that multi-structured documents construction was at the heart of their work. Indeed, they need to let coexist a multiplicity of structures in order to access a document according to many interpretations. Thus, we proposed a methodology promoting the emergence of multiple structures in a multi-users context.

SCENARIO

This study gave us a lot of scenarios similar to the following: a philologist finds a consistent subset about medicinal plants in a stack of pages of consequent size. He creates a new collection from this subset. He creates an association named "mainSubject" between this collection and the topic "Medicine". He starts to transcribe the collection and annotates some intervals of the text with terms such as "quotation", "prescription", etc. Later, he may discover that this collection is in fact a preparatory work for another piece of the archive. He then creates an association named "preparationFor" between the two collections. Etc.

How is it that, for example, a user chooses to place the term "citationTitle" within a structure named "Citations" while he affects the term "line" to the "Physical" structure? This kind of question brought us to define a methodology for the construction of multi-structured documents.

METHODOLOGY

First of all, we only consider content addressable by concrete intervals: characters intervals in a text, time intervals in an audio or video document. In order to offer some unity to the various structures emerging from the work of a group of users, we introduce an a priori rule: a structure must form a hierarchy. In other words, the annotated intervals of a structure should never overlap. By dynamically checking the validity of this rule we managed to ease the collaborative construction of multi-structured documents. We should now briefly illustrate this idea with the previous example of an old manuscript (see Figure 1).

We assume that the researchers made use of annotation terms such as: "line", "w" (for word) and "dmg" (for damaged characters). The transcription process continues until a word is overlapping with two lines (see strong & dashed lines of Figure 2).

FIGURE 2 METHODOLOGY FOR THE CONSTRUCTION OF MULTI-STRUCTURED DOCUMENTS: RESTRUCTURING IS NECESSARY SINCE A WORD IS OVERLAPPING WITH TWO LINES

The user will then be alerted about an incompatibility between the terms "line" and "w". Therefore the user is advised to re-organize the structures. The result of this operation might me similar to the one illustrated by Figure 3.

CONCLUSION

Finally, this strategy for the management of multi-structured documents promotes the construction of a multiplicity of structures that should reflect the perspectives adopted by the users working on a documentary archive. Each user has the liberty to create new structures. Moreover, when overlapping structures are detected, users are encouraged to solve the problem by introducing a new structure.

From this specific applicative aspect of multi-structured documents construction, we can infer some requirements for the encoding of such documents. In particular, the fragmentation approach appears to be a key feature. First of all, as we can learn from the multi-structured documents examples given by the TEI, in a large majority of cases, structures are sharing fragments of the raw content. Also, and we are inclined to stress this point, some of the non-trivial applications of multistructured documents seem to rely on a dynamic, and often collaborative, manipulation of documentary fragments. Indeed, multiple structures often appear when users are carrying out highly interpretative tasks that require a fine-grained analysis of the primary content. In these circumstances, the fragmentation is an all-pervasive operation that should be made as straightforward as possible: a structure should be able to combine any subset of fragments independently from other structures.

AGENDA

We have proposed [START_REF] Chatti | MultiX: an XML-based formalism to encode multi-structured documents[END_REF] a generic model called MSDM (Multi-Structured Document Model), in which we define the notion of a multi-structured document. In this paper we deal with the multi-structured documents encoding issue. Encoding (i.e. making explicit an interpretation of a text) is very often achieved through using markup languages (i.e. sets of markup encoding conventions). Therefore, XML as a metalanguage for the description of markup languages is the tool of choice for many document centric projects. Often, parallel structures are encoded separately in distributed XML files. Encoding these structures in separate files has many disadvantages, such as content redundancy and breaking interdependency. This kind of solution introduces significant document management problems.

To address these problems, it may be interesting to encode all structures in a single XML document (one file for all concurrent structures), by superimposing them to avoid content redundancy. As a matter of fact, it is very difficult to encode concurrent structures in a single XML file. Usually the overlapping problem makes it impossible to get a well formed XML document. XML is based on a tree model (and therefore elements cannot overlap). In this paper, we propose a new formalism called MultiX, which allows the efficient encoding of multi-structured documents. MultiX, which uses an XML syntax, is based on the MSDM model.

After a survey of related works (section 2), we present, in section 3, a formal description of the MSDM model and illustrate it with the previous example of a manuscript document. This same example will be used in section 4 to illustrate the MultiX formalism. Section 5 will be dedicated to the multi-structured document querying issue.

RELATED WORKS

INTRODUCTION

The problem of encoding concurrent structures has attracted much attention. Several approaches have been proposed to deal with this problem. We classify the main approaches into two categories. The first one contains the very first works on the representation of several hierarchical structures inside a same text; these solutions are often exclusively syntactical.

The second category includes works grounded on well-defined formal models. In a previous survey, [START_REF] Calabretto | Documents and multiple hierarchies: Towards Multi Structured XML Documents[END_REF] was referring to three categories making a distinction between "XML-compatible" models and the others. We choose to consider XML-compatibility as one of the dimensions against which the models will be studied.

DIMENSIONS RETAINED FOR THE ANALYSIS

We analyze each solution against six dimensions:

 Data model:
On what kind of model is the solution based? Is it a tree, a graph, something else?

We should see that in most cases the solutions will be based on a tree, a set of trees or a generic graph. However, a few of them will use more exotic models. Moreover, there are the syntactical only solutions with no clearly defined data model. We consider the presence of a well-defined formal model as a most important feature. It is a quality criterion ensuring the continued evolution of the solution. Also, most of the time, this dimension will not be independent from others. Indeed, it can affect the query mechanisms, the possibility to update a multi-structured document, etc.

 XML-compatibility: Is the solution compatible with the XML formalism?

XML is nowadays the de facto standard for the representation of electronic documents. Among other things, the formalism is associated with numerous standard and efficient tools for processing documents: XSLT, XPath, XQuery, etc. Thus, XML-compatibility is essential. A solution doesn't achieve XML-compatibility by merely managing XML files but by allowing a straightforward use of the aforementioned tools. Regarding this last point, different approaches are encountered. Some of them modify the XML model itself; some modify the XPath or XQuery specification while others manage not to alter the XML core. We incline toward this last category since we consider solutions modifying the core of the XML model unsustainable compared to solutions taking advantage of the "galaxy" of XML tools with light, nonintrusive, approaches.

 Master structure: Does the solution rely on a master structure or are all the structures on a same level?

As we shall see, the solutions can be divided in two main categories with respect to how they manage overlapping of elements. Firstly, there are the solutions that build the documents around a main or master structure with all the remaining structures being defined in relation to it. Secondly, there are also solutions that give no privilege to any structure. For the later, as far as the model is concerned, all the structures are equal. As we have tried to show in the introduction, non-trivial use of multi-structured documents tend to call for such an a priori equality of structures. Thus, we favor this last category of solutions.

 Queries: Does the solution come with adapted query mechanisms?

With no doubt, the possibility to make complex queries is one of the most useful features of electronic documents. Multi-structured documents, particularly when they cause some overlapping of structure elements, often ask for subtle queries that couldn't be performed with the existing query engines. Thus, good solutions will come with new query functions and take into account the overlapping situations.

 Updates: Once a multi-structured document exists, how can it be modified?

Because of the complexity of managing multiple structures for a same document, some solutions will not provide any easy way to modify an existing multi-structured document. Due to the kind of use cases aforementioned in the introduction, we give great importance to the possibility of building documents and so we rank higher the solutions allowing the modification of existing multi-structured documents.

 Performance / Implementation: Is there an implementation? How efficient is it?

Finally, due to the very practical aspect of multi-structured documents and the urgent need to provide effective solutions for their management, we will consider the performance issue of the existing implementations.

SYNOPTIC VIEW OF THE SOLUTIONS

The Table 1 is a summary of the works being evaluated in the following parts of this survey section.

MSDM / MultiX

Same as above.

Yes and it only needs some XQuery functions.

Same as above.

Thanks to a few XQuery functions.

Yes, thanks to a specialized parser.

The MXQ library of XQuery functions is available on the Web.

HISTORICAL WORKS

CONCUR

CONCUR (ISO 8879, 1986) is an optional SGML feature with which one can define several parallel DTD for the same content.

In such an SGML document, all structures share a single file. For each structure, the annotations are decorated with a specific prefix identifying a given DTD (see Listing 1 for an illustration of CONCUR with the manuscript example introduced above).

LISTING 1 CONCUR ILLUSTRATION

Meanwhile, relationships can't be established between the different structures. Moreover, as noted by [START_REF] Hilbert | Making CONCUR work[END_REF], when two elements of different DTD are qualifying exactly the same region, the order of their "start" and "end" tags is irrelevant. Obviously, as an SGML option, CONCUR is not compatible with XML. Though, as we should see, there have been initiatives to adapt it to the XML world. We are not aware of any query mechanism for CONCUR. The

<(S1)Line><(S2)Word>hu</(S2)Word> <(S2)Word>þu</(S2)Word> <(S2)Word>me</(S2)Word> <(S2)Word>haefst</(S2)Word> <(S2)Word>afrefredne</(S2)Word> <(S2)Word>aeg</(S1)Line> <(S1)Line>þer</(S2)Word> <(S2)Word>ge</(S2)Word> <(S2)Word>mid</(S2)Word> <(S2)Word>þinre</(S2)Word> <(S2)Word>smealican</(S2)Word> <(S2)Word>sprae</(S1)Line> <(S1)Line>ce</(S2)Word>, <(S2)Word>ge</(S2)Word> <(S2)Word>mid</(S2)Word> <(S2)Word>þinre</(S2)Word> <(S2)Word>wynsumnesse</(S2)Word> <(S2)Word>þines</(S2)Word></(S1)Line> </(S2)Words> </(S1)Lines>
document being unique, structures and data changes are easy. Finally, this solution has rarely been implemented and even Charles Goldfarb (as recalled in [START_REF] Hilbert | Making CONCUR work[END_REF]), the main developer of the SGML standard, did not recommend its use.

TEI

The XML standard, although based on SGML, did not retained nor adapted the CONCUR modeling of multi-structured documents. However the needs were more than ever present. Thus, the XML version of the TEI (Text Encoding Initiative) guidelines offers several methods for the encoding of multiple hierarchies (TEI Consortium, 2011). These methods can be classified in four different categories : redundant encoding of information in multiple forms (C1) ; empty elements to delimit the boundaries of non-nesting structures (C2) ; breaking non-nesting elements into smaller elements linked by a 'reference' attribute (C3) ; stand-off markup approach that separates the content and the elements describing it (C4). These solutions are more like recipes than well-defined models.

With the first three categories of solutions, the standard XML tools (XPath, XQuery …) can't be used straightforwardly. It quickly becomes very difficult to express even simple queries. For the fourth solution, the guidelines advise us to use the XInclude2 standard to establish the links between structures and content. However, the TEI also uses third-party XPointers schemes, and no generic parsing tools implement XInclude with support for such schemes [START_REF] Baoski | Why TEI stand-off annotation doesn't quite work[END_REF].

For redundant encoding of information, there is obviously no master structure. For empty elements, and fragmentation, the elements of encoding that do not make use of the recipes can be said to belong to a master structure, and only this structure will be easy to work with (query, etc.). For stand-off markup, the structures will make reference to a decomposition of the content in elementary fragments and no master structure is as such required.

Moreover, since XPath and XQuery can't be used in a standard way, queries are either difficult or even impossible.

Updating facilities vary. For the first category (redundant encoding), updates are of course very costly. For categories C2 and C3, since the representations of the structures share a same file, updates are easy. For stand-off markup, no mechanism is provided to ease the updating process.

Finally, those solutions only consist of recipes and no implementation per se is provided. However, numerous projects seem to follow these recommendations for the representation of multi-structured documents when overlapping occurs ony rarely.

FORMAL MODELS

TEXMECS

To make up for the limits of existing markup languages, other studies have been carried out in order to define new syntaxes. MECS (Multi-Element Code System) made the overlapping of elements possible. TexMECS [START_REF] Huitfeldt | TexMECS An experimental markup meta-language for complex documents[END_REF]) is a follow-up of MECS where complex structures can be defined with elements having many parents (see Listing 2 for an illustration of a TexMECS encoding of the manuscript example introduced above).

LISTING 2 TEXMECS ILLUSTRATION

In general, TexMECS documents are not isomorphic to XML documents and so the XML tools cannot be used. However, for documents with no overlaps, a direct translation to XML is feasible. As far as we know, no query mechanisms have been developed. Moreover, all the structures and the primary data sharing a same representation (i.e. a file), it remains easy to update them. Finally, a TexMECS well-formed-ness checker has been implemented

MULAX

MuLaX [START_REF] Hilbert | Making CONCUR work[END_REF] document for each layer). Each projection results in a well-formed XML document. Listing 4 is an example of the MuLaX syntax applied to our running example.

LISTING 4 MULAX ILLUSTRATION

Standard XML tools can only be used on the individual XML projections. Thus, inter-structural relationships remain out of reach. No query operators are defined but the authors give some hints on how XPath could be extended to navigate in a MuLaX document. Moreover, updates are difficult because working on MuLaX documents implies frequent projections to XML files. Indeed one should never modify a projection but only the main document. Finally, an editor has been developed as an Eclipse plugin for the creation of MuLaX documents.

ANNOTATIONS GRAPH

Annotation graphs [START_REF] Bird | Annotation Graphs as a Framework for Multidimensional Linguistic Data Analysis[END_REF] appeared in the context of language analysis. Thus, they take into account linguistic domains (phonetics, prosody, morphology, syntax, etc). In our context, these domains can be considered as multiple structures. The same text fragment could be annotated by edges belonging to different structures (as shown in Figure 4). The data fragmentation corresponds to words or to characters if it is necessary. The labels associated with the oriented edges identify elements of annotation within a specific structure (for example 'S2:w').

FIGURE 4 ANNOTATIONS GRAPH ILLUSTRATION

The physical model could be serialized to XML (using attributes of types ID and IDREF). Thus available XML tools and languages can be used for each extracted hierarchical structure. However, the document as a whole cannot be the object of any treatment by standard XML tools. A prototypical query language (Bird, Buneman, & Tan, Towards a Query Language for Annotation Graphs, 2000) has been defined for annotations graphs. Moreover, structures remain easy to update since they share the same data. Finally, there exists an implementation called AGTK (Annotation Graph Toolkit)

5

.

5 http://agtk.sourceforge.net/ <?mlx version="1.0" encoding="iso-8859-1"> <( 1)Lines><(2)Words> <( 1

RDFTEF

In a very similar way to the Annotation Graph proposal, RDFTef [START_REF] Tummarello | Toward Textual Encoding Based on RDF[END_REF]) makes use of the RDF (Resource Description Framework) formalism to provide a framework for the modeling of multi-structured documents. This method takes advantage of the RDF graph model, which may be used to encode complex structures with overlapping elements. However, contrary to the Annotation Graphs, RDFTef is based on a well-defined standard formalism. Moreover, this RDF based proposal is not oriented toward a specific domain. RDF can be serialized to XML but since the model is a graph the use of standard XML tools is not satisfactory. However, standard RDF query tools (such as SPARQL) can be used but medium complexity queries can be difficult to formulate. Moreover, structures and data changes are theoretically possible since there is only one graph. Finally, a prototype implementation based on the Jena Java RDF library is available online 6 .

EARMARK

Among the RDF based solutions, EARMARK [START_REF] Peroni | Annotations with EARMARK for arbitrary, overlapping and out-of order markup[END_REF]) is certainly the most convincing one. The notions of "location", "range", "markup item", etc. used for the modeling of multi-structured documents are precisely defined within an OWL ontology (see Figure 5 for an excerpt of the ontology).

FIGURE 5 EXCERPT FROM THE EARMARK ONTOLOGY

Tools are provided to convert an EARMARK instance into an XML document with, for example, empty elements. However, standard XML tools can't be used directly with an EARMARK document. Being a graph model, EARMARK doesn't make any low-level distinction between structures. Moreover, the SPARQL language can be used for querying the documents. For updates, the graph can be easily manipulated through standard RDF APIs. Finally, a prototype implementation exists, though it doesn't seem to be available on the Web. However, the main contribution lies in the OWL ontology and can be implemented with any standard OWL engine.

GODDAG

The GODDAG (General Ordered Descendant Directed Acyclic Graph) [START_REF] Dekhtyar | A framework for management of concurrent XML markup[END_REF]) logical model can be used for the creation of an internal representation of concurrent XML structures. The obtained graph structure resolves the overlapping problem. As shown on Figure 6, several trees are defined over the same content by sharing their leaves (for example: textual fragments). All nodes have at least one common ancestor: the document root. First of all, functions for importing (resp. exporting) from (resp. to) XML are defined. Moreover, new axes are provided for the XPath language. Therefore, the standard XML tools can be used in a natural way. For querying GODDAG, the authors propose an extension of the XPath language. This extension is based on a set of new axes that lead to nodes according to their relations and independently from the structures to which they belong: it is possible to reach every ancestor (axis xancestor) of a node in every hierarchy to which it belongs. In a similar way, other axes are defined: xdescendant, xfollowing, xpreceding, overlapping, following-overlapping and preceding-overlapping. Moreover, operators are defined to manage changes in the structures. However, the raw data cannot be updated. Finally, the implementation is based on a generalization of the DOM tree for the representation of multi hierarchical XML documents.

MCT

The MCT model (Multi-Colored Trees) [START_REF] Jagadish | Colorful XML: one hierarchy isn't enough[END_REF]) is an extension of the XML model making possible the representation of multiple trees that share a same content. It relies on the tree coloring technique. A color is associated with each tree. A node may have multiple colors: the color of the main tree to which it belongs and colors for other trees. Figure 7 illustrates this model with our running example of a manuscript transcription. We see that three of the unit nodes share two colors: one for the syntactical structure of words and another one for the physical structure of lines.

hu þu me haefst afrefredne aegþer ge mid þinre smealican sprae line line w w words lines manuscript Etc. etc. etc. Etc. etc. etc. Etc. etc. etc. legend : Physical structure : Syntactical structure

FIGURE 7 ILLUSTRATION OF THE MCT MODEL

Navigation inside the multi-hierarchy is possible by means of the multicolored nodes. Indeed, the XPath step has been extended with color choice. Thus, the model can be manipulated with standard XML tools. However, one has to choose a first color. Then the new structures are built relatively to this first structure which becomes a master structure. Together with the new XPath step, an XQuery extension has been proposed for, among others features, creating new colored nodes. Moreover, concerning updates, the authors believe that, through the XPath extension they offer, the XUpdate language could be adapted. Finally, the model has been implemented as an extension to the Timber7 XML database.

DELAY NODES

The XDM 8 data model on which are based XPath and XQuery, distinguishes seven kinds of nodes in a document tree: document, element, attribute, text, namespace, processing instruction, and comment. To address the problem of concurrent hierarchy, Jacques Le Maître in [START_REF] Le Maître | Describing multistructured XML documents by means of delay nodes[END_REF] adds a new kind of node: the delay node. A delay node is the virtual representation, by an XQuery query, of some of the descendant of one of its ancestors as shown in Figure 8.

hu

FIGURE 8 ILLUSTRATION OF THE DELAY NODES ("EXP" REPRESENTS THE DELAY NODE)

After the XDM model has been modified by the addition of delay no XPath nor XQuery extensions are needed. However the ability to navigate among the concurrent trees is only valid for the descending axis: child and descendant.

Going upward from a delay node is not possible. Moreover, one structure is considered as the main structure, while others make use of delay nodes. Except for the inability to navigate inside concurrent trees differently than along the descending axis, XQuery can be used quite straightforwardly. However, changes in data or structures are very difficult to achieve since we should modify the queries of the delay nodes at a syntactical level. Finally, in [START_REF] Le Maître | Describing multistructured XML documents by means of delay nodes[END_REF], it is said that a prototype has been implemented on top of the authors' own XQuery engine. However, it doesn't seem to be available on the Web.

MSXD

MSXD (Multi-Structured XML Documents) [START_REF] Bruno | Describing and querying hierarchical XML structures defined over the same textual data[END_REF]) is a proposal that provides a formal model and a query language defined as an extension of XQuery that let the structure of an XQuery unchanged. Moreover, users can annotate structural elements. MSXD is also one of the first attempts to define a schema for multi-structured textual documents. However, from a practical point of view, the need to define (a great number of) constrains between structures is not obvious. The core model of MSXD is based on the use of hedges (the foundation of RelaxNG). In fact, each structure must be hierarchical and is associated with a RelaxNG Schema. Then, Allen's relations (after, equals, overlaps, etc.) can be defined between fragments of different structures. Thus, the individual structures are classic XML documents. Moreover, syntax has been defined to represent the union of the multiple structures in a single XML document. XQuery functions are provided in order to deal with multi-structured documents (the core of the XPath/XQuery model doesn't need to be modified). However, modifications of structures and data remain impossible. Finally, a prototype implementation is available online9 with both the MSXD model and the new XQuery functions.

MONETDB / XQUERY

MonetDB/XQuery is an XML DBMS. MonetDB/XQuery stand-off extension [START_REF] Alink | Efficient XQuery Support for Stand-Off Annotation[END_REF]) is an efficient implementation of query operators for multi-structured documents represented by stand-off markup. Stand-off annotations are modelled with a subset of the interval algebra. The annotated binary object (text, video, etc.) must be addressable with intervals. An interval is a couple (start,end) where start and end positions must be of the same data type and this data type must support full ordering (for example integers). Since the solution supports the annotation of noncontiguous regions, the interval algebra is reduced to the two relations of containment and overlap. See Listing 5 for an illustration of the MonetDB stand-off extension syntax.

LISTING 5 ILLUSTRATION OF MONETDB / XQUERY SYNTAX

With the provided XPath steps and the integration to an existing XML management system; this proposal can be used with the standard XML tools. Moreover, this solution offers an efficient implementation of stand-off joins as new XPath steps. Thus, the multi-structured documents can be queried quite naturally. However, as for other stand-off solutions, updates can be difficult, no specific tools being provided. Finally, this solution relies on MonetDB, a well-known, efficient and open-source DBMS 10

. However, the development of MonetDB/XQuery has been frozen in March 2011 11 and the project will not be ported to MonetDB version 5.

10 http://monetdb.cwi.nl/ 11 http://www.monetdb.org/XQuery <?xml version ="1.0" encoding ="utf -8"? > <manuscript> <physical> <lines> <line start="1" end="28"/> <line> <region> <start>29</start> <end>59</end> </region> </line> <!--Etc. etc. --> </lines> </physical> <syntactical> <words> <word start="1" end="2"/> <!--Etc. etc. --> <word start="27" end="31"/> <!--Etc. etc. --> </words> </syntactical> </manuscript> 2.6 CONCLUSION Finally, from the set of dimensions we chose to keep and the requirements we expressed for each one of them (see paragraph 2.2 p. 6), we can now explain what makes our own model necessary. We should sum up some important points of the previous solutions.

The TEI solutions are not based on a proper formal model and can't be used with standard XML tools. CONCUR was certainly interesting but came with no tools for dealing with multi-structured documents.

MuLaX transposed the CONCUR idea to the XML world but, since there is no convenient way for querying MuLaX document, this solution can't be retained.

TexMECS and LMNL chose to develop new models, grammars and syntaxes to answer the needs of multi-structured documents management; however with their current limitations they cannot be considered as generic solutions.

Annotation Graphs, RDFTef and then EARMARK avoid the problems caused by the tree model of XML by considering formalisms and models that work directly with graphs. The choice of RDF with SPARQL, its query language, makes a welladapted solution. However, we strongly believe that the XML-compatibility criterion is essential. Indeed, a large number of the existing projects dealing with complex electronic documents are using XML. Moreover, standardization initiatives, such as the TEI or EAD (Encoded Archival Description)

12 etc. are also using XML.

Among the stand-off markup solutions, Delay Nodes and MCT are very clever ones. Their models are interesting. However, they have to give privileges to one of the structures; and it has been explained, in paragraph 1.2.5 page 5, that a free fragmentation of the raw content and truly independent structures are essential characteristics for a satisfactory multistructured documents management system.

MonetDB and MSXD are based on the GODDAG stand-off markup solution but none of them can easily manage the modifications of data and structures (this is common to many stand-off techniques). Moreover, MonetDB and MSXD both rely on extensions of XPath with new steps. This choice tends to make the solutions dependent on a particular implementation.

Thus, we now propose our own model: MSDM, a Multi-Structured Document Model. It is based on a stand-off markup approach and thus relies on a well-defined formal model of multiple rooted trees. Being implemented through a few XQuery functions, it remains fully compatible with the galaxy of known XML tools. It doesn't rely on any privileged master structure and is therefore well adapted for the modeling of complex multi-structured documents. Finally, updating is possible thanks to a specialized parser. This model will now be described in full details.

MSDM: MULTI-STRUCTURED DOCUMENT MODEL

To answer the problem of multiple structuring, we have proposed a specific model called the Multi-Structure Document Model (MSDM) [START_REF] Chatti | MultiX: an XML-based formalism to encode multi-structured documents[END_REF]. As many of the previous solutions, ours is based on the stand-off markup method where structures point to the content stored separately. However, we approach the problem in a more general way. In fact, we assume that multiple structures can share the exact same content fragments, and not necessarily exactly the same content. Thus, for our model, concurrent structures are a particular case of multi-structured documents.

In this model, which is inspired by the model defined in [START_REF] References Abascal | Modéliser la structuration multiple des documents[END_REF], a multi-structured document is defined using the three following notions:

 Documentary Structure (DS): this is a description of a document content defined for a specific use. Such a structure may be, for example, a physical structure used for presentation purposes, or a syntactical structure defined for statistical analysis, etc.

 Basic Structure (BS): this structure organizes the content in disjoint elementary fragments. These fragments are then composed in order for the documentary structures to refer to their content by pointing to these composition nodes.

 Correspondences: a correspondence is a relationship between two elements of two distinct structures. The source of a correspondence is always an element of a documentary structure. When the target is a composition node of the basic structure, the correspondence is used for identifying the content of a documentary structure node.

Otherwise, it indicates a relation between two documentary structures, the nature of which depends on the context of the application, it could, for example, indicates a synonymy between two nodes of two distinct DS, it could also, as in our manuscript example, link the transcription of a line to the corresponding region of the manuscript's image, etc. We present in this section the formal description of our multi-structured document modeling approach. We first define the concept of multi-structured document and then we describe formally all the necessary notions.

Definition 1 (Multi-structured Document):

A multi-structured document D is a graph defined by the triplet D = BS, , C where:  BS is an oriented graph called the basic structure of D;   is a set of graphs called the documentary structures;  C is a set of relations between nodes of -graphs or BS. We call these relations correspondences between structures.

BASIC STRUCTURE

Notations:

 F(D) designates the set of all possible content fragments of a document D.  (D) = { : (F(D)) p  F(D) | p  1} is the set of all the functions that compose a piece of content from a series of smaller pieces. For example, the function that creates the string "ab" by concatenation of the two fragments (a,b)  F(D) 2 is an element of (D).

The compositions are possible only for fragments with a same media type: this is the homogeneity constraint for compositions. To ensure a minimum level of abstraction, we do not debate here the details of composition functions. However, we will later illustrate our model with an example where a specific use of fragment compositions will appear.

Definition 2 (Basic Structure):

The basic structure of a multi-structured document D is an internal structure that stands as a base for sharing the same content among several structures. It is formally defined as a graph BS = (v,e) where:

 root is the root node of BS, each node is part of a path originating from it. This node has no associated semantic; it only provides connectivity to the graph.

 F Base (D)  F(D) is the set of all disjoint fragments, called base fragments, from which other fragments can be composed and associated to document structures through correspondences. Each node n  F Base (D) is the destination of one or more edges from composition nodes.

 N comp is the set of composition nodes, i.e. the nodes that represent parts of content composed of smaller fragments. Each node n  N comp is the destination of exactly one edge with origin the root node. So the subgraph of BS whose nodes are {root}  N comp is a trivial tree. Moreover each node n  N comp is labelled with a function f  (D) that prescribes the composition of the elements of F Base (D) linked to n.

 v = {root}  N comp  F Base (D)
is the set of vertices of BS  comp(n) with n  N Comp is the set of all the edges from the composition node n to one or more elements of F Base (D). Each of these edges is labeled with an integer, that makes comp(n) a totally ordered set. This order may be used by a function f  (D) associated with n to compose the elements of F Base (D) in the appropriate order.

 e = {(root,c) | c  N comp }  ( n  Ncomp comp(n))
is the set of edges of BS.

DOCUMENTARY STRUCTURES Definition 3 (documentary Structure):

A documentary structure is a set of structured descriptors applied to documentary content. Formally, a documentary structure is a tree defined by: DS = E, A, L, l E , l A  where:

 E is a finite set of vertices we call structural elements.  A  E x E is a finite set of binary relations between structural elements. These relations must form a tree.  L is a finite set of labels.

 l E : E  L is a function that associates each structural element in E with a label in L.  l A : A  L is a function that associates each edge in A with a label in L.

In this definition we followed a simple approach in the representation of documentary structures. The most important thing in our model is not the representation of documentary structures, but the representation of the basic structure and of the correspondences.

CORRESPONDENCES

The multi-structured document is a graph consisting of a set of graphs (documentary structures and a basic structure) whose elements (i.e. composition nodes of the basic structure and structural elements of the documentary structures) can be linked by correspondence relationships.

A correspondence, noted DS  BS, associates the document structures with their original contents (PCDATA for the textual content, in XML terminology) reconstructed from the basic structure. There are also DS  DS correspondences and the following MultiX formalism offers a way for representing them, however they can also be implemented by means of any XML linking mechanism and don't per se belong to the MSDM model.

In the next section, the MultiX formalism is used to XML-encode the multi-structured document created from these four structures.

MULTIX: XML APPLICATION BASED ON MSDM MODEL

The MultiX formalism is an XML application based on the MSDM model. It consists in the serialization of a multi-structured document into a well formed XML document. We call a multi-structured document encoded within this formalism: a MultiX document. Such a document is composed of three parts: the documentary structures (DS), the basic structure (BS) and the correspondences. A MultiX document must have the skeleton depicted on Figure 10.

FIGURE 11 SKELETON FOR THE BASIC STRUCTURE

For example, the composition enabling the reconstitution of the content of the first line element in the physical structure will be encoded as follows:

<msd:comp id="CL1" idrefs="F1 SP F2 SP F3 F4 SP F5 SP F6 SP F7"/>

The 'id' attribute identifies the composition element. The 'idrefs' attribute value is a sequence of fragment identifiers. Each composition provides a string obtained by concatenating the identified content fragments. The 'SP' fragment must always be available and provides a single space character.

The 'msd:compositions' element of the basic structure must contain all the compositions necessary for rebuilding the documentary structures content.

ENCODING OF DOCUMENTARY STRUCTURES AND CORRESPONDENCES

A MultiX document may have several documentary structures encoded inside 'msd:DS' elements. A documentary structure in the MultiX formalism is similar to its standard XML representation except for the actual content that is replaced by 'DSBS' correspondences pointing to composition nodes.

In general, a correspondence has a source, a target and a label. For the 'DSBS' correspondences the target is always a composition in the basic structure. The source of this correspondence type represents the position in the documentary structure where the composed content should be placed.

Inside a MultiX document, the correspondences are defined in the 'msd:correspondences' element (see Figure 12). The source is located by the 'msd:anchor' element inserted at the desired position in the documentary structure. We then create the 'msd:clink' elements as follows:

<msd:correspondences> <!--... --> <msd:clink target="BS" label="text content" from="A.lne.3.1" to="CL3_1"/> <msd:clink target="BS" label="text content" from="A.lne.3.2" to="CL3_2"/> <!--... --> </msd:correspondences>

The target attribute of the 'msd:clink' element indicates the type of the correspondence: "BS" for a DSBS correspondence, and "DS" for a DSDS correspondence. With this external form of correspondences the anchors can be reused. For example, an anchor that is a source of a DSBS correspondence can also be used as the source or the target element of relations between documentary structures. In addition, compared with XPath expressions, the use of an anchor minimizes the required correspondences' updates after the modification of the documentary structures.

QUERYING MULTIX DOCUMENTS

There are several XML query languages that may be used to query MultiX documents. However, when using these languages the MultiX documents are viewed as pure XML documents. An important effort is then necessary to create queries that take into account the semantic of the MultiX formalism. To be queried easily, the MultiX formalism needs an adapted query language. XQuery (W3C, 2010) is a powerful language and a W3C recommendation inspired by SQL. In order to adapt this language to MultiX, we have implemented a library of XQuery functions (MXQ 13 ) for exploiting MultiX documents. These functions aim at simplifying the writing of queries involving several structures. With them, we can for example check if some content is shared by two or more structures. Moreover, it becomes easy to explore relations between elements of different structures. Before demonstrating how to use our library through some examples, we shall describe a specific function called 'rebuild'.

DOCUMENTARY STRUCTURE RECONSTITUTION

If we apply queries on MultiX documents, items returned are incomplete or incomprehensible. Indeed, instead of textual content we get references to correspondences to the basic structure. Other elements, referring to relations between documentaries structures can also be found. Therefore it is essential to translate these references properly, and to present the results in a readable form, as if the structures were encoded separately. These transformations are performed in a transparent way thanks to the 'rebuild' function. This function has the following signature: mxq:rebuild($elem-seq as element()*) as element()* With this function we can rebuild a sequence of elements belonging to document structures. The goal of the recovery is to reproduce the tree structure, transforming the DSBS correspondences into their calculated content.

Thanks to this feature, we do not have to handle independently multiple versions of the structures. The dependent form, within a MultiX document, ensures structure scalability and consistency. But the independent form can be useful for treatments; it is in particular better suited for query operations when there is no necessity to take into account the interactions between structures. Thus, MXQ can always provide updated and coherent structures of a MultiX document in the form of classic XML documents.

FIGURE 3

 3 FIGURE 3 METHODOLOGY FOR THE CONSTRUCTION OF MULTI-STRUCTURED DOCUMENTS: A USER HAS DEFINED THREE NEW STRUCTURES (SYNTACTICAL, PHYSICAL AND DAMAGED)

  <!DOCTYPE S1 SYSTEM "dtds/physical.dtd"> <!DOCTYPE S2 SYSTEM "dtds/syntaxical.dtd"> <(S1)Lines> <(S2)Words>

  Markup and aNnotation Language)[START_REF] Tennison | The Layered Markup and Annotation Language (LMNL). Extreme Markup Languages[END_REF] defines a specific syntax based on the notion of range, allowing the encoding of multiple structures where elements can overlap (see Listing 3 for an illustration). However, LMNL is first of all a data model and not only a syntactical representation. A LMNL document is based on a text layer made of a sequence of atoms (for example: Unicode characters). Ranges are used to define fragments of content. Ranges can be annotated with new text layers that themselves can have ranges… LISTING 3 LMNL ILLUSTRATION Pathways exist to convert to and from XML documents by way of milestones (i.e. empty elements). Obviously, when overlapping happens, it then becomes difficult to use standard XML tools. As far as we know, no query mechanisms have been developed. Moreover, all the structures and the primary data sharing a same file, it remains easy to update them. Finally, XSLT stylesheets have been developed to deal with the XML representation of a LMNL document 4 .

  FIGURE 6 ILLUSTRATION OF THE GODDAG MODEL

Figure 9

 9 Figure9illustrates these notions on the previous example of a manuscript transcription.

FIGURE 12 SKELETON

 12 FIGURE 12 SKELETON FOR THE CORRESPONDENCESFor example, to rebuild the original PCDATA of the third line element of the physical structure, we can define two correspondences by inserting anchors in appropriate positions: <line n="3"><msd:anchor id="A.lne.3.1"/><msd:anchor id="A.lne.3.2"/></line>

TABLE 1 SUMMARY OF THE EVALUATION OF RELATED WORKS

 1

	Solution	Data model	XML-compatibility	Master structure	Queries	Updates	Implementation
	CONCUR	Syntactical only solution, no model.	SGML option.	The structures are independent.	No	Easy, since file. there is only one	None
	redundancy			No		No!
	Empty					Not too
	elem.		XPath and		Standard XML	difficult but	No needs. They
			XQuery can't		tools are not	no tools	are syntactical
			be used		usable	exist for	only solutions.
	Virtual					automating
	elem.					this
		No model is				process.
	TEI guidelines	provided. These are syntactical	No generic parsing tool implements	Yes
		solutions.	XInclude
	Stand-off markup		with third-party XPointers schemes.		Only in theory	Only in theory	No suitable implementation of XInclude
			Therefore,
			this solution
			is not fully
			usable.
	MECS / TexMECS	A new language with a grammar overlaps that allows	No. A hierarchical TexMECS document is document. to an XML isomorphic	No. The structures are all equal.	No	Yes, since only one document.	Parsers have been implemented.

  is an adaptation of the SGML CONCUR option to the XML formalism. It is intended as a document format that can merge in a uniform way a collection of several XML documents into one document. A layer ID prefixes each tag name. A MuLaX document can be projected onto its initial XML documents (one XML

	<lines|<words|
	<line|<word|hu|word> <word|þu|word> <word|me|word> <word|haefst|word>
	<word|afrefredne|word> <word|aeg|line><line|þer|word> <word|ge|word>
	<word|mid|word> <word|þinre|word>
	<word|smealican|word><word|sprae|line><line|ce|word>, <word|ge|word>
	<word|mid|word><word|þinre|word> <word|wynsumnesse|word>
	<word|þines|word>|line>
	|words>|lines>

3 http://decentius.aksis.uib.no/servlets/mlcd/web/WFCheck.jsp 4 http://www.piez.org/wendell/LMNL/lmnl-page.html

[Manuscript [Title}Manuscript 1{title]} [Lines}[Words} [Line}[Word}hu{Word]… … [Word}haefst{Word] [Word}afrefredne{Word] [Word}aeg{Line] [Line}þer{Word]… … {Words]{Lines] {Manuscript]

  þu me haefst afrefredne aegþer ge mid þinre smealican sprae

		manuscript
		lines			words
	line	w	w		w
	exp
	u	Etc. etc. etc.	u	u	Etc. etc. etc.	u	Etc. etc. etc.
			legend
	exp :	(../..//u) [position() = 1 to 6]

  <lines> <line n="1">hu þu me haefst afrefredne aeg</line> <line n="2">þer ge mid þinre smealican sprae</line> <line n="3">ce, ge mid þinre wynsumnesse þines</line>

	<physical>
	</lines>
	</physical>
	<syntactical>
	<words>
	<w>hu</w> <w>þu</w> <w>me</w> <w>haefst</w> <w>afrefredne</w> <w>aegþer</w>
	<w>ge</w> <w>mid</w> <w>þinre</w> <w>smealican</w> <w>spraece</w> <w>ge</w>
	<w>mid</w> <w>þinre</w> <w>wynsumnesse</w> <w>þines</w>
	</words>
	</syntactical>
	<damaged>
	<res>þu m</res> <dmg>er</dmg> <dmg>mid</dmg> <dmg>ae</dmg> <dmg>g</dmg>
	<dmg>þ</dmg> <dmg>re</dmg> <dmg>e</dmg> <res>s</res>
	</damaged>

www.w3.org/TR/xinclude/

http://rdftef.sourceforge.net/

http://www.eecs.umich.edu/db/timber/

http://sis.univ-tln.fr/msxd/

http://www.loc.gov/ead/

http://liris.cnrs.fr/~peportie/multix/mxq.html

QUERYING MULTIX DOCUMENTS WITH XQUERY

When querying MultiX documents, multiple structures can be involved through their correspondences. The DSBS correspondences can provide information about the content shared by various structures. This information can be obtained through the fragments of the basic structure. Moreover, the exploration of relations between documentary structures can be very helpful and always depends on the semantic of the document's domain.

Apart from the "rebuild" function introduced above, the MXQ library includes the following functions:

1. Functions handling DSBS correspondences: a. share-content($e as element()) as xs:Boolean tests if the argument share some content with elements from other documentary structures than the one it belongs to. N.B. the special 'SP' fragment representing a single space is not considered in the process of finding shared content.

b. share-content-with($e as element(), $str_name as xs:string) as element()* returns the elements from $str_name documentary structure pointing to a subset of the BS nodes composing the first argument.

c. share-fragments($e1 as element(), $e2 as element()) as xs:Boolean tests if the arguments share some content.

d. get-shared-fragments($e1 as element(), $e2 as element()) as element(msd:frag)* returns the fragments shared by the arguments.

e. include-fragments-of($e1 as element(), $e2 as element()) as xs:Boolean tests if the content of the second argument is included in the first; the order of the fragments is not meaningful.

f. same-fragments($e1 as element(), $e2 as element()) as xs:Boolean tests if the two arguments are equal in content.

g. include-content-of($e1 as element(), $e2 as element()) as xs:boolean tests if the content of the second argument is included in the first; the order of the fragments being relevant.

Functions handling relations between documentary structures:

a. get-corr-target-from($e as element(), $label as xs:string) as element()* returns the elements target of a DSDS correspondence that originates in the first argument and is labeled by the second.

b. get-corr-target($label as xs:string, $d as document-node()) as element()* returns the targets of a DSDS correspondence that originates in any of the elements of the second argument and is labeled by the first.

c. get-corr-source($label as xs :string) as element()* returns the elements source of a DSDS correspondence labeled by the argument.

d. exists-corr-between($e1 as element(),$e2 as element()) as xs:Boolean tests if there is a DSDS correspondence from the first argument to the second.

e. is-correspondence($e1 as element(), $e2 as element(), $label as xs:string) as xs:Boolean tests if there is a correspondence named by the last argument and linking the first to the second.

We now illustrate the use of these functions on our manuscript example.

Q1: Find all damaged words that only contain damaged characters. for $l in $doc//msd:DS[@name = "lines"]//str1:line, $w in $doc//msd:DS[@name = "words"]//str2:w where mxq:share-fragments($l, $w) and not(mxq:include-content-of($l, $w)) return mxq:rebuild($w) } </TEST> We use the fact that a word that splits on two lines only shares parts of its fragments with each line.

Result:

<?xml version="1.0" encoding="UTF-8"?> <TEST xmlns:msd="http://www.msdm.org/2006/MULTIX"> <w>aegþer</w> <w>spraece</w> </TEST> Q3: Find all words with restored characters. Indicate for each of them the restored characters and the region of the manuscript image where those characters can be seen.

xquery version "1.0"; import module namespace mxq = "multixlib" at "multixlibrary.xquery"; declare namespace msd = "http://www.msdm.org/2006/MULTIX"; declare namespace str1 = "http://exemple.org/lines"; declare namespace str2 = "http://exemple.org/words"; declare namespace str3 = "http://exemple.org/damaged"; declare namespace str4 = "http://exemple.org/text-regions";

<TEST xmlns:msd="http://www.msdm.org/2006/MULTIX"> { let $doc := doc("manuscript.xml") for $w in $doc//msd:DS[@name = "words"]//str2:w, $r in $doc//msd:DS[@name = "damaged"]//str3:res where mxq:share-fragments($r, $w) return <words-with-rest-char> {mxq:rebuild($w), <rest-char>{mxq:get-shared-fragments($r, $w)/text()}</rest-char>, for $l in $doc//msd:DS[@name = "lines"]//str1:line where mxq:share-fragments($r, $l) return mxq:get-corr-target-from($l, "localisation") } </words-with-rest-char> } </TEST> description="ligne 1"> <zone xtop="43" ytop="50" xdown="460" ydown="94"/> <msd:anchor id="A.reg.1"/> </region> </words-with-rest-char> <words-with-rest-char> <w>þines</w> <rest-char>s</rest-char> <region xmlns="http://exemple.org/text-regions" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" num="reg.3" description="ligne 3"> <zone xtop="43" ytop="166" xdown="536" ydown="210"/> <msd:anchor id="A.reg.3"/> </region> </words-with-rest-char> </TEST>

We have shown some applications of the MXQ library. Its main purpose was to demonstrate the exploitability of multistructured documents. Work has been done in [START_REF] Alink | Efficient XQuery Support for Stand-Off Annotation[END_REF] to determine the best ways of extending XQuery in the context of multi-structured documents represented by stand-off markup; it could certainly be used to efficiently implement the MXQ functions.

CONCLUSIONS

In this paper, we have defined a formal model for multi-structured documents: MSDM. The logical model of MSDM is a graph. A basic structure organizes the content in disjoint elementary fragments. Documentary structures point to the basic structure by way of composition nodes. Correspondences can be modeled between a documentary structure and the basic structure, as well as between distinct documentary structures. The model takes into account inter-dependencies of structures with shared content.

XML is a widely used language and the basis of several other formalisms. That's why we proposed MultiX, an XML instance of the MSDM model. It can therefore benefit from several existing XML tools and formalisms. Thus, for example, we can use the XSLT language to extract and format the documentary structures of a MultiX document. Moreover, we have developed a library of XQuery functions to easily explore multi-structured documents through elaborate queries. With these tools, we could now consider "Multi-Structured Information Retrieval". This concept could be attached to the Web of Data in order to provide many points of view on the same raw content.

The creation of a multi-structured document from structures that share content is generally not an easy task for a human operator. The complete or partial automation of this task is sometimes necessary. We have already implemented the MXP parser (Multi-XML parser) [START_REF] Chatti | Documents multi-structurés : de la modélisation à l'exploitation[END_REF] in order to create an internal representation of a multi-structured document from XML structures encoded separately.

Finally, we have introduced the non-trivial problem of multi-structured documents construction. Although the XML enforcement of tree structures was considered for a long time the heart of the multi-structured document problem, we used it in the context of a new solution where the emergence of overlapping hierarchies triggers the creation of a new structure that has to be validated by a community of users. Thanks to the MSDM model, we have been able to address this new problem.


Rémi Bonnefoi
email: remi.bonnefoi@centralesupelec.fr

Christophe Moy
email: christophe.moy@centralesupelec.fr

Jacques Palicot
email: jacques.palicot@centralesupelec.fr

Advanced Metering Infrastructure Backhaul Reliability Improvement with Cognitive Radio

The monitoring of the smart distribution grid requires a reliable telecommunication system. In this paper, we propose to use cognitive radio to enhance the reliability of smart grid communications. We show that, in case of failure of the primary wireless communication network used for the advanced metering infrastructure (AMI) backhaul, cognitive radio can be used to connect aggregators to a backup network. The chosen backup network can be a cellular network or an IoT (internet of things) network. Then, an analysis of the reliability of the AMI backhaul in an IoT network is done and we show how cognitive radio and machine learning algorithms can be used to enhance the communications reliability.

I. INTRODUCTION

The real time monitoring of the electricity grid allows to reduce the number and the impact of power failures. The distribution grid was first monitored by the Supervisory Control and Data Acquisition (SCADA) system designed for the monitoring of industrial systems. When SCADA is used for the distribution grid, remote terminal units (RTU) and programmable logic controllers are placed all along the grid. These devices send measures and receive orders from a general controller. In a smart grid, the monitoring of the distribution grid is done by the advanced metering infrastructure (AMI), the distribution automation (DA) and the management of distributed energy ressources (DER) [START_REF] Brown | Impact of smart grid on distribution system design[END_REF].

In AMI, a two ways flow of information is used between control centers and consumers. On one way, the meters installed in consumers' homes measure the electricity consumption and send it to control centers. On the other way, smart meters receive information (such as the electricity price) for demand response (DR), this information can be used by the consumer or by smart appliances to adapt their power consumption.

Many Smart Grid applications (such as AMI, DA and DER) require a reliable network for real time communications. Wireless communication networks can be a low cost and reliable way to carry out Smart Grid communications. Indeed, in case of failure of the grid, power line communications (PLC) are no longer usable and wired communications can be damaged by earth potential rises (EPR) [START_REF] Cleveland | Use of wireless data communications in power system operations[END_REF]. Moreover, cellular networks such as 2G, 3G and 4G are already widely deployed in many country and have a large coverage. They are, consequently, a promising solution for the Smart Grid [START_REF] Gao | A survey of communication/networking in smart grids[END_REF].

The use of cellular networks for the smart grid has already been studies in the litterature. In [START_REF] Karagiannis | Performance of lte for smart grid communications[END_REF], the authors analyze the throughput and the packet loss ratio of an LTE network used for the Advanced Metering Infrastructure (AMI) and for the remote control of the Grid. In [START_REF] Brown | Key performance aspects of an LTE FDD based smart grid communications network[END_REF], the performance of an LTE network used for data transmission from phasor measurement units (PMU) to control centers is evaluated. In [START_REF] Madueo | Reengineering gsm/gprs towards a dedicated network for massive smart metering[END_REF], GSM and GPRS base stations are reengineered to be used for smart grid communications. However, the reliability of cellular networks worries distribution system operators (DSO). That is why we propose an innovative solution for the improvement of the reliability of cellular networks used for Smart Grid.

If an element of the smart grid can access to several telecommunication networks, it can use one of them as a default communication network (or primary network) and the others as backup networks used in case of failure of the default network. This increases the reliability of the communications. Moreover, a cognitive radio (CR) [START_REF] Mitola | Cognitive Radio -An Integrated Agent Architecture for Software Defined Radio[END_REF], [START_REF] Haykin | Cognitive Radio : Brain-Empowered Wireless Communications[END_REF] can sense its environment and reconfigure itself to fit it. With cognitive radio, a device on the grid can access multiple standards without having multiple communication systems. Reconfiguration is proposed by the Gridman task group to increase the reliability of Smart Grid communications [START_REF] Zhou | Greater reliability in disrupted metropolitan area networks: use cases, standards, and practices[END_REF]. This task group proposes a reconfigurable backhaul to increase the reliability of WiMAX base stations. In case of backhaul connection break, the base station can reconfigure its backhaul and becomes a relay node to another base station or to a mobile station to avoid data loss.

In this paper, we focus on the use of cognitive radio for the AMI backhaul. PLC or another communication technology can be used between smart meters and aggregators and we suppose that GPRS (General packet Radio Service) is used between the aggregators and the control center. The transceiver of the aggregators is a cognitive radio used to communicate with the control center through the GPRS network. In case of failure of the GPRS network, the cognitive radio chooses one of the available backup standards to communicate. The radio equipment can use another cellular network or can use an existing Internet of Things (IoT) network. When a cellular network, such as UMTS (Unified Mobile Telecommunication System) or LTE (Long Term Evolution), is used, the quality of service (QoS) can be maitained. On the contrary, the insertion of the AMI backhaul in an IoT network (or Low Power Wide Area Network (LPWAN)) can reduce the quality of service of both networks. In this paper, we evaluate the reliability of the AMI backhaul and of the IoT network and we show how cognitive radio and machine learning algorithms can be used to enhance this reliability.

The rest of this paper is organized as follows, the system model is introduced in section II. Reconfigurable aggregators are described in section III. In section IV, we introduce the reliability of the AMI backhaul in an IoT network and in section V we show how cognitive radio can facilitate the insertion of aggregators in an existing IoT network. In section VI some numerical results are presented and section VII concludes this paper.

II. SYSTEM MODEL

A. Context

We suppose several residential areas in which houses are equipped with smart meters. Each residential area is connected to the distribution grid by a substation in which an aggregator is installed. The aggregator communicates with smart meters through PLC and with a control center using the GPRS network. The system is illustrated in figure 1. The RF transceiver of the aggregator is a cognitive radio which can reconfigure itself and access multiple wireless standards. If the aggregator has difficulty connecting to the primary network, the cognitive radio can be reconfigured and a new communication standard is used to communicate with the control center.

Communications considered for normal operation (PLC and GPRS) are these used by ERDF (Electricité Réseau Distribution France) for the deployment of the French smart metering system. In this country, 35 millions of smart meters and 700 000 aggregators will be deployed by 2021 [START_REF] Mamo | Distribution automation: The cornerstone for smart grid development strategy[END_REF]. Each smart meter makes a measure of the home's power consumption every 10/30 or 60 minutes and sends it to the aggregator. On average, an aggregator is connected to 50 meters. As a consequence, a large number of aggregators will be installed in cities (1000 for a city of 50 000 inhabitants).

We suppose that the aggregator aggregates the data received from smart meters and sends the total power consumption to a control center in a small message (which can be a SMS in a cellular network). After receiving the power consumptions, the control center use them to estimate the state of the distribution grid and to compute the new electricity price. Then, the control centers send back a short message to aggregators. This message (or packet) can contain the new electricity price and can be an acknowledgement to the aggregator.

With this ackowledgement, we can ensure the QoS (reliability) for the AMI backhaul. This quality of service, or reliability, depends on the number of lost packets. In [START_REF]Communications Requirements of Smart Grid Technologies[END_REF], the U.S. Department of Energy recommended a reliability of 99-99.99% for the AMI backhaul.

If the aggregators and the control centers have an ID (e.g. an IP address) they can communicate through any wireless network. In case of failure of the GPRS base station, the aggregator can reconfigure its RF chain to access to other wireless networks. For example, if the aggregator is in the coverage of a UMTS or a LTE base station, it can use them to transmit information.

B. Cognitive Radio

A cognitive radio, is a radio frequency equipment which adapts its communications to its environment. Figure 2 shows the simplified cognitive cycle.

Fig. 2. Simplified cognitive cycle

A cognitive radio has sensors which are used to acquire knowledge of its environment. The result of the sensing is used to make decisions and to reconfigure the radio frequency equipment. Cognitive radio is usually used for dynamic spectrum access (DSA) [START_REF] Jouini | Upper confidence bound based decision making strategies and dynamic spectrum access[END_REF]. In a DSA scenario, secondary users want to access to licensed channels unused by primary users. Before accessing a channel, a secondary user must sense if a primary user uses this channel. With the sensing result, the secondary user decides if it access to this channel or chooses another channel for data transmission.

In this paper, the cognitive radio of the aggregator is mainly used for the selection of the backup standard in case of failure of the GPRS network. During the sensing part of the cognitive cycle, the cognitive radio senses the available and usable backup standards and detects the failures of the standard in use. When a failure occurs, the aggregator decides which standard should be used. Then, during the adaptation phase, the transceiver is reconfigured to use the selected backup standard.

C. Model

In case of failure of mobile networks, aggregators can use an IoT network (or LPWAN) to maintain the communication between aggregators and control centers. In LPWAN, each

This article is a corrected version of an article published in IEEE SmartGridComm 2016 message is encapsulated in a packet. We suppose that IoT base stations can transmit and receive packets from devices (or connected objects). We also suppose that time and frequency are slotted in the IoT network and that devices randomly access to slots as illustrated on figure 3. We denote T the slot duration which depends on the IoT standard. We suppose that each connected object uses only one channel. Several slots are used by connected objects and others are free. These free slots can be used by aggregators. Fig. 3. A slotted IoT network [START_REF] Pister | Tsmp: Time synchronized mesh protocol[END_REF]. All the slots unused by connected objects can be used by aggregators in case of failure the primary network For the analysis of the reliability, we only consider the packets lost because of collisions and we don't considers packets lost because of propagation conditions. We also suppose that the RF transmit power used by aggregators and that used by connected objects have the same order of magnitude. As a consequence, when an aggregator and a connected object send or receive a packet in the same slot, both are lost.

To maintain a certain level of reliability, aggregators should know if a collision occurred. To know it, an aggregator can sense collisions or the base station can send an acknowledgement to the aggregator when the packet is received. If two devices far from one another send a packet in the same slot, it can be difficult to sense the collision. In this paper, we focus on reliability and we suppose that the base station sends an acknowledgement to the aggregator when a message is successfully sent.

In the following section, we introduce the mechanism used for the selection of the backup standard used in case of failure of the GPRS network and we detail scenarios in which backup standards can be used.

III. MULTI-STANDARD COMMUNICATIONS FOR A BETTER

RELIABILITY

The reconfiguration of the RF chain can be done efficiently only if the aggregator has knowledge of the usable standards. To acquire this knowledge, the aggregator must sense its environment to detect the available networks. For this detection, aggregators can have a prior knowledge of the available standards or can use blind standard recognition algorithms [START_REF] Lopez-Benitez | Spectral occupation measurements and blind standard recognition sensor for cognitive radio networks[END_REF]. Once neighboring standards have been detected, the aggregator can establish a connection with them to evaluate if the available base stations are usable. The available and usable standards are stored in a database.

To update the database of usable standards, the aggregator should detect and connect to usable base stations regularly. For example this update can be done once a week during off peak hour.

The best available standard is chosen according to the criteria of the distribution system operator (DSO). From the DSO point of view, the best choice is to use the cheaper reliable way to exchange AMI information. This justifies the use of GPRS as a default standard. Moreover, since the DSO has a contract with a mobile operator for the use of a GPRS network, this contract can include the use of the UMTS or LTE networks for backup. Others backup solutions such as IoT networks can be emergency solutions used in case of failure of all cellular networks.

The selection of the backup standard is done based on the information sensed and on the information received from the control center. If the aggregator hasn't received information from the control center, it first uses its default network. If the transmission fails, the aggregator selects another standard. The selected backup standard is the best backup standard according to the DSO criteria. If this standard is not operational, the aggregator will choose the next standard in its database and so on.

The standard chosen at the end of the selection process depends on the severity of the failure. We propose to classify failures in three categories, minor, medium and major failures. Table I lists some example of failures. If the aggregators try to establish a connection with a saturated base station (minor failure), the aggregator can reconfigure its RF chain and use another cellular network. At the next data sending, the base station will try to use the GPRS network and use it if it is not saturated.

In case of medium failure, the aggregator will use the best available backup network. This backup network will be used until the fixing of the GPRS base station. The aggregator will use its cognitive radio to regularly sense if the GPRS base station was repaired.

If a major failure happens, all the surrounding base stations are unusable. For example, this can happen if the backhaul of mobile networks is broken or if the failure of the GPRS network has caused traffic jams. In this case, aggregators will have to connect to more distant base stations. They will use This article is a corrected version of an article published in IEEE SmartGridComm 2016 long range communication standards such as SigFox 1 or LoRa [START_REF] Sornin | LoRaWAN Specification[END_REF]. These networks can be good solutions for maintaining the link between aggregators and control centers. It can be noted that, after a natural disaster, the number and the nature of the messages exchanged between control centers and aggregators can change. One of the main issues of IoT networks is their reliability. Indeed, a large number of aggregators can use the IoT network at the same time (100 or 500 if the problem affects a small city). If the AMI backhaul is inserted in a dense IoT network, the number of collisions and the number of lost packets will be high and the reliability of the backhaul will be very low.

In the following section, we define the reliability of the AMI backhaul in an IoT network and we show how cognitive radio can improve the reliability of the AMI communications in an IoT network.

IV. RELIABILITY OF THE AMI BACKHAUL IN AN IOT NETWORK

We suppose that many connected objects communicate through the IoT network. In this network, time and frequency are slotted. Each object uses only one of the m possible frequency channels of same bandwidth. We suppose that the time is divided in slots of duration T . The slot duration depends on the packet size and on the throughput. For example, in a LoRa network, the packet size can be 50 bytes and the throughput is between 0.293 and 38.4 kb/s thus the time slot can be between 10 ms and 1.365 s.

For the analytical analysis of the reliability in each channel, we suppose that connected objects and aggregators access to the channel following a Bernoulli distribution.

For one of the connected objects, we define the communication probability as the probability that this device uses the channel and we define the occupancy probability of the channel as the probability that at least one connected object uses the channel. In channel j, we denote P j this probability:

P j = 1 - nj i=1 (1 -p i ) (1)
Where n j is the number of devices in band j and p i the probability that the device i uses the band. We can see that this probability increases with the number of devices and with the devices' communication probabilities.

If n a aggregators with a communication probability p a,k , k ∈ 1; n a begin to use only the channel j, the probability that at least one aggregator uses the channel is:

P j a = 1 - na k=1 (1 -p a,k ) (2)
For the analysis of the reliability in a channel, we use the packet delivery ratio (PDR) which can be defined as the ratio between the number of AMI successful communications 1 www.sigfox.com and the number of packets sent for AMI backhaul (sent by aggregators or by the control center).

R AM I =

E{Nb of successful AMI communications} E{Nb of packets sent for AMI} [START_REF] Gao | A survey of communication/networking in smart grids[END_REF] In one temporal slot, we have a successful transmission if there are no collisions in this slot. I.e. if only one packet is sent in the temporal slot and the expectation of the number of successful communications is equal to the probability of successful communication:

P succ = nj i=1 (1 -p i ) na l=1 p a,l na k=1,k =l (1 -p a,k ) = nj i=1 (1 -p i ) na k=1 (1 -p a,k ) na l=1 p a,l 1 -p a,l (4)
Furthermore, in one temporal slot, the expectation of the number of packets sent for AMI backhaul is equal to:

E{Nb of packets for AMI} = na l=1 p a,l (5)
This expression of the reliability in channel j can be deduced from equations ( 4) and ( 5):

R AM I = nj i=1 (1 -p i ) na k=1 (1 -p a,k ) na l=1 p a,l 1-p a,l na l=1 p a,l R AM I = (1 -P j )(1 -P j a ) na l=1 p a,l 1-p a,l na l=1 p a,l (6)
If we suppose that all aggregators have the same probability to use the channel, we can denote p a this probability and the reliability of the AMI backhaul becomes:

R AM I = (1 -P j ) (1 -p a )
na-1 [START_REF] Mitola | Cognitive Radio -An Integrated Agent Architecture for Software Defined Radio[END_REF] We can evaluate the probability of occupancy of an aggregator in a LoRa network. Indeed, an aggregator sends and receives a packet every 10/30 or 60 minutes. If we suppose that time is divided in slots which last between 10 ms and 1.365 s, the probability of occupancy of an aggregator varies between 2.8 × 10 -6 and 2.3 × 10 -3 .

These numerical evaluations show that p a ≪ 1, with a first order Taylor expansion, we can approximate the reliability of the AMI backhaul:

R AM I = (1 -P j ) (1 -(n a -1)p a ) (8)
In the same way, we can define the reliability of the IoT network in which the AMI backhaul is inserted:

R IoT = na k=1 (1 -p a,k ) nj i=1 (1 -p i ) nj i=1 pi 1-pi nj i=1 p i (9)

This article is a corrected version of an article published in IEEE SmartGridComm 2016

Likewise, if all aggregators have the same occupancy probability, (9) becomes:

R IoT = (1 -p a ) na-1 nj i=1 (1 -p i ) nj i=1 pi 1-pi nj i=1 p i (10)
Which can be approximated by:

R IoT = (1 -(n a -1)p a ) nj i=1 (1 -p i ) nj i=1 pi 1-pi nj i=1 p i (11)
Equations ( 8) and [START_REF]Communications Requirements of Smart Grid Technologies[END_REF] show that the reliabilities of the AMI backhaul and of the IoT network decrease linearly with the occupancy probabilities of connected objects and with the number of aggregators in the band.

To enhance the reliability of the AMI backhaul, aggregators can send their packets until they receive an acknowledgement. This increases the number of packets sent and leads to a degradation of the reliability of the IoT network.

To maintain the reliability of both the AMI backhaul and the IoT network below a given threshold (required reliability) in each channel, aggregators should use channels with a low P j . In the next section, we show how cognitive radio and reinforcement learning algorithms can be used to enhance the reliability of both networks.

V. COGNITIVE COMMUNICATIONS THROUGH AN IOT NETWORK

In an IoT network, aggregators can use machine learning algorithms for the selection of the least occupied channel. With these algorithms, aggregators will first have an exploration phase during which they will try all the channels to evaluate the occupancy probabilities. After this exploration phase, they can choose the best channel and use it for all transmissions, this is called the exploitation phase. In this section, we propose to use the upper confidence bound (UCB) algorithm to learn which channel has the lower occupancy probability. This agorithm has been proposed in cognitive radio for opportunistic spectrum access [START_REF] Jouini | Upper confidence bound based decision making strategies and dynamic spectrum access[END_REF]. It presents a very low footprint (in memory and processing power) and learns effectively the probability of occupancy of all channels. Moreover, UCB starts exploiting within the exploring phase, so no time is lost.

We denote t the number of data transmission realized by an aggregator and T j (t) the number of selection of the channel j. When channel j is selected for data transmission, an aggregator considers that a transmission is successful if it receives an acknowledgement and unsuccessful else. We define the reward of the data transmission in channel j as:

r t (j) = 1 if the transmission is successful 0 else (12)
To evaluate the average reward in channel j, we use a confidence bound of its sample mean. If we denote a t the channel selected for transmission t, the sample mean of the reward in channel j after T j selections is:

X j (t) = t-1 l=1 r l (j)1 {a l =j} T j (t) (13)
Where 1 {a l =j} is the indicator function. We define the upper confidence bound algorithm indexes in each channel as [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]:

B j (t) = X j (t) + A j (t) (14)
Where A j is an upper confidence bias. With the UCB algorithm, the selected channel is that with the higher upper confidence bound:

a t = argmax j (B j (t)) (15)
For the UCB 1 algorithm, this bias is equal to:

A j (t) = α ln t T j (t) (16)
Where α is the exploration coefficient. During the exploration phase, T j (t) is low and A j (t) is high, as a consequence during this phase, the algorithm will explore all the channels. When t and T j (t) increases, A j (t) decreases and the aggregator will transmit most of the time in the channel with the higher empirical reward, this exploiting past experience results.

The duration of the exploration phase depends on the value of α. The exploration phase is longer when α is high. When α ≪ 1, the exploration phase is very short, this can lead to a bad channel selection. When α ≫ 1, the exploration phase is very long. This can cause data losses because channels with high occupancy probabilities are used many times.

In an IoT network, the probability of occupancy is often low, but, when many aggregators begin to use the network, the IoT network can become overloaded. Moreover, aggregators use the network only for a few days. As a consequence, they don't have time for a long exploration phase. Then learning fast convergence is of outmost importance.

VI. NUMERICAL RESULTS

For simulations, we suppose that several aggregators use an IoT network. All these aggregators have the same probability to send a packet equal to p agg = 10 -4 . If the IoT base station receives a packet from an aggregator during one slot, it sends the acknowledgment in the same channel during the next slot.

Since this acknowledgement is sent only when the packet sent by the aggregator is received by the base station, the probability of occupancy of an aggregator does not exactly follow a Bernoulli distribution with probability 2p agg . Actually, if the reliability of the channel is not too low and if p agg is sufficiently low, the probability of occupancy of an aggregator can be approximated by a Bernoulli distribution with probability 2p agg .

We first suppose a band with a probability of occupancy P = 0.1 and we show the evolution of the reliability of the AMI backhaul versus the number of aggregators in one channel. Fig. 4 shows that when the number of aggregators is below 500, the reliability of the AMI backhaul can be approximated by equation [START_REF] Haykin | Cognitive Radio : Brain-Empowered Wireless Communications[END_REF] with p a = 2p agg .

Number of aggregators in the channel

We now suppose an IoT network divided in m = 10 channels. Each channel has its own probability of occupancy, without loss of generality, channel are sorted in ascending order of P j , these probabilities are equal to P j = {0.01 ; 0.02 ; 0.03 ; 0.04 ; 0.05 ; 0.06 ; 0.1 ; 0.13 ; 0.17 ; 0.2}. Fig. 5 shows the evolution of the reliability of the AMI backhaul in the 10 bands versus the number of aggregators. We now suppose that 100 aggregators are using the IoT network. Each aggregator uses the UCB 1 algorithm to find the channel with the highest reliability (the lowest probability of occupancy). Aggregators don't use the IoT network for a long time, thus, the learning phase should be short and the exploration coefficient α should be low. We consider 1 × 10 7 temporal slots (approximately 1 day for time slots of 10 ms) and for all aggregators, α = 0.3. We focus on the effect of the UCB algorithm on the reliability and we suppose that aggregators don't resend packets if they don't receive the acknowledgement. Fig. 6 shows the proportion of selections of each channel by aggregators. We can see that the more free is a channel, the more it will be chosen by aggregators. Moreover, most of the communications occur in the channels with a reliability of 95% or more. The whole reliability of the AMI backhaul can be defined as the total number of successful communications divided by the number of packets sent, we can compare the total reliability of the AMI backhaul with and without the UCB algorithm. With the UCB algorithm, this reliability is equal to 95.5% whereas without it we have a relability of 91.7 %. The average reliability in the IoT network is slightly below the required reliability of 99%. As a consequence, the reliability of the IoT network studied is not sufficient to use it as a default network but it allows to maintain the connection between aggregators and the control center in case of failure of the mobile networks.

When the UCB 1 algorithm is used, the reliability of the AMI backhaul in the IoT network increases with time. During the exploration phase, aggregators use all the channels and the reliability is equal to 91.7%. During the exploitation phase, each aggregator uses only one channel and the reliability is higher. For α = 0.3, the reliability of the AMI backhaul after one day of exploration is equal to 96.2%. Figure 7 shows the evolution of the reliability with time for different values of α.

We can see on figure 7 that the lower is α, the higher is the reliability after one day of exploration. When α increases, the duration of the exploration phase increases, this decreases the reliability after one day of exploitation but can increase the long term reliability.

VII. CONCLUSION

In this paper, we presented cognitive radio as a solution for improving the reliability of Smart Grid communications. We proposed to use cognitive radio to switch between the primary network (or default network) and backup networks in case of failure. When the backup network is an IoT network, cognitive radio and reinforcement learning algorithms can be used to enhance the reliability of the AMI backhaul and to reduce the impact of the AMI backhaul on the IoT network.

This article is a corrected version of an article published in IEEE SmartGridComm 2016

We have shown how cognitive radio can be used to enhance the reliability of the AMI backhaul. In future work, we are going to study the use of cognitive radio to enhance the reliability of others Smart Grid applications such as distribution automation and we will extend the analysis to others backup standards.

Fig. 1 .

 1 Fig. 1. Communications of the advanced metering infrastructure

Fig. 4 .

 4 Fig. 4. Reliability of the AMI backhaul in one channel versus the number of aggregators in the channel

Fig. 5 .

 5 Fig. 5. Reliability of the AMI backhaul in each channel versus the number of aggregators in the channel

Fig. 6 .

 6 Fig. 6. Proportion of selection of each channel with α = 0.3

Fig. 7 .

 7 Fig. 7. Evolution of the reliability with time for different values of α

ACKNOWLEDGEMENT

Part of this work is supported by the project SOGREEN (Smart pOwer GRid for Energy Efficient small cell Networks), which is funded by the French national research agency, under the grant agreement coded: N ANR-14-CE28-0025-02 and by Région Bretagne, France.