Luciana Benotti
email: luciana.benotti@loria.fr

Incomplete Knowledge and Tacit Action: Enlightened Update in a Dialogue Game

. In particular, we shall discuss how this theory applies in a setup with incomplete background knowledge.

Introduction

In this paper we investigate, in a simplified and formalised setup, how the information that allows two interlocutors to understand each other correctly is constructed and exploited during a conversation.

Let us start, right away, with an everyday example of the phenomenon we want to investigate. A few days ago, my mother told my sister: "Please, buy some food for Tiffy." Then my sister took some money from a kitchen drawer, went to the grocery store that is near my primary school, bought a pack of low fat cat food with salmon flavour, and carried the food back home. And this is exactly how my mother expected her to act. Why? Because both of them know that my sister is always low in cash, that at home there is always money in a particular kitchen drawer, that the grocery store near my primary school is the cheapest one, and that Tiffy is our pet cat, who is getting a bit fat and likes salmon. Is that all? Not quite. They also know that in order to buy something you need money, that in order to open a drawer you need to pull it, and many other things that are usually taken for granted.

Here, my mother and my sister exploited the large amount of information they share in order to leave several actions tacit. In conversation, this strategy is not merely valid, it is frequent and pervasive. We are going to investigate it in a 'dialogue game,' a conversational setup simplified in several ways. To start with, i) the interaction is restricted to a set of requests1 between two interlocutors, with well defined preconditions and effects. Also, ii) the requests can be issued only by one of the interlocutors (who we will call 'the player'), the other (called 'the game') is limited to accepting and executing, or refusing the request. To complete the picture, iii) 'the game' has complete and accurate information about the conversational context (called 'the game scenario'), while 'the player' may have incomplete and even incorrect information.

Our setup is formalised in the implementation of a text adventure engine called FrOz Advanced (FrOzA). Text adventures are computer games that simulate a physical environment which can be manipulated by means of natural language requests (i.e., commands issued to the game). The system provides feedback in the form of natural language descriptions of the game world and of the results of the players' actions. FrOzA extends the text adventure FrOz [START_REF] Koller | Put my galakmid coin into the dispenser and kick it: Computational linguistics and theorem proving in a computer game[END_REF] with planning capabilities. This added inference ability allows FrOzA to discover actions left tacit by the player.

This paper has two main aims. The first is to show (in Section 2) how planning capabilities can be integrated into the Description Logic [START_REF] Baader | The Description Logic Handbook: Theory, Implementation, and Applications[END_REF] based inference architecture provided by FrOz. Second, we wish to demonstrate (in Section 3) that the resulting system, namely FrOzA, offers a natural laboratory for the theory of enlightened update presented in [START_REF] Thomason | Enlightened update: A computational architecture for presupposition and other pragmatic phenomena[END_REF]. The theory of enlightened update suggests how shared information (usually referred to as common ground [START_REF] Clark | Using Language[END_REF]) is exploited and constructed in the light of a computational framework for reasoning in conversation. We use FrOzA not only to obtain a concrete account of enlightened update theory, but to extend it for handling incomplete background knowledge as well.

FrOzA

The architecture of FrOzA is shown in Figure 1; its three main processing modules are depicted as ellipses. The language understanding module parses the command issued by the player and constructs its semantic representation. The language generation module works in the opposite direction, verbalising the results of the execution of the command. The action handling module is in charge of performing the actions intended by the player.

All three modules make heavy use of inference services (represented as dashed lines in the figure) in order to query and update the components of a game scenario (depicted as rectangles). The processing modules are independent of particular game scenarios; by plugging in a different game scenario the player can play a different game. In fact, it is in its reasoning abilities that FrOzA extends the original version of the system (FrOz). Thanks to its planning capabilities, FrOzA is able to discover actions intended by the player but left tacit by her. In order to infer these actions, FrOzA uses the planner Blackbox [START_REF] Kautz | Unifying SATbased and graph-based planning[END_REF]. Like FrOz, FrOzA uses the theorem prover RACER [START_REF] Haarslev | RACER system description[END_REF] to query and modify the Description Logic knowledge bases according to the instructions encoded in the action database.

In the rest of the section we will describe the components of FrOzA that are relevant for the purposes of this paper. In Section 2.1 we will describe how FrOzA models a game scenario in its knowledge bases. In Section 2.2 and 2.3 we will explain in detail how actions are handled; in particular, we show how the execution of an action depends on the current game scenario, and how the successful execution changes the scenario. This will pave the way for our discussion of enlightened update in Section 3.

Modelling a game scenario

FrOzA uses Description Logic (DL) knowledge bases (KB) to codify assertions and definitions of the concepts relevant for a given game scenario. A DL knowledge base is a pair (TBox, ABox) where the TBox is a set of definitions and the ABox a set of assertions about the objects being described in the KB (such objects are usually called individuals). Actually, FrOzA uses two knowledge bases, which share the TBox and differ only in their ABoxes. The common TBox defines the key concepts in the game world and how they are interrelated. Some of these concepts are basic notions (such as object) or properties (such as alive), directly describing the game world, while others define more abstract notions like the set of all the individuals a player can interact with (the individuals that are accessible to the player).

The ABoxes specify properties of particular individuals (for example, an individual can be an apple or a player). Relationships between individuals are also represented here (such as the relationship between an object and its location).

One of the knowledge bases (the game KB) represents the true state of the game world, while the other (the player KB) keeps track of the player's beliefs about the game world. In general, the player KB will not contain all the information in the game KB because the player will not have explored the world completely, and therefore will not know about all the individuals and their properties. In fact, it might also be the case that the player KB contains information that is inconsistent with the game KB. The game can deliberately hide effects of an action from the player; pushing a button might have an effect that the player cannot see.

Crucially, a game scenario also includes the definitions of the actions that can be executed by the player (such as the actions take or eat). Each action is specified (in the action database) as a STRIPS-like operator [START_REF] Fikes | Learning and executing generalized robot plans[END_REF] detailing its arguments, preconditions and effects. The preconditions indicate the conditions that the game scenario must satisfy so that the action can be executed; the effects determine how the action changes the game scenario when it is executed.

Handling a single action

In this section we are going to explain in detail how an action issued by the player can change the game scenario.

To illustrate our explanation, let us consider a concrete input and analyse how it is handled by the system. Suppose that the player has just said "Take the key." The semantic representation of this command (obtained by the language understanding module) will be the ground term take(key1) (where key1 represents the only key that the player can see in the current state of the game). This ground term will be passed to the next processing module in the architecture.

When a ground term is received by the action handling module, it is matched against the list of action schemas. The action schema that will match the ground term of our example is: action: take(X) preconditions: accessible(X), takeable(X), not(in-inventory(X)) effects:

add: in-inventory(X) del: has-loc(X indiv-filler(X has-loc)) player effects: add: in-inventory(X) del: has-loc(X indiv-filler(X has-loc))

The term X in the above schema is a variable that gets bound to the actual argument of the action. In our example, X would be bound to the constant key1, and thus the preconditions and effects will become ground terms. Once the action schema is instantiated, it is time to check that the action can be executed. An action can be executed if all its preconditions are satisfied in the current game KB. The preconditions can require that individuals belong to certain concepts or that they are related by certain roles. For example, the execution of the action take(key1) requires that the key is accessible to the player (accessible(key1)), that it is small enough to be taken (takeable(key1)) and that it is not carried by the player already (not(in-inventory(key1))). The theorem prover RACER is used to query the current game KB, thereby checking that the preconditions are satisfied.

If the action can be executed, the game KB is updated according to the effects of the action. In our example, the key will no longer be in its original location but it will be carried by the player. The original location of the key is obtained by sending the query indiv-filler(key1 has-loc) to RACER. A RACER query is embedded in an action schema when the action depends on properties of individuals not explicitly mentioned in the player command (such as the location of the key).

Once the game executed the action, the player needs to know that the action succeeded. To this end, the player effects in the action schema are communicated to the player by the generation component and asserted in the player KB.

If the command cannot be executed in the current game scenario, the first precondition that failed is communicated to the player and both KBs remain unchanged.

Interpreting the player intention

Now that we know how the actions module handles a simple action, let us explain how ambiguous commands and tacit actions are handled in FrOzA.

The input of the action module is not a single ground term but a list of possible readings of the input sentence. The list will contain exactly one reading only if the sentence is not ambiguous (as in the example in the previous section). Otherwise, the list will contain one entry for each different reading. For example, the sentence "Unlock the door with the key" is syntactically ambiguous and has two possible readings, one in which the propositional phrase "with the key" modifies the verb "unlock" and another in which it modifies the noun phrase "the door." Sentences can also be referentially ambiguous. For instance, the sentence "Take it" has as many readings as there are salient referents in the game scenario. Each reading is itself a list which represents a sequence of actions to be performed one after the other. For example, every reading of the sentence "Take the key and unlock the door with it" will contain two ground terms, one for each action in the sequence.

If the input sentence has more than one reading, FrOzA decides among them by trying each action sequence in parallel. When an action fails, the entire reading it belongs to is discarded. For example, the reading of the command "Take it and eat it" which resolves both occurrences of "it" to a key, will be discarded because a key is not edible, although it can be taken.

If only one reading succeeds, the game assumes that this is the command the player had in mind, and commits to the end result of the sequence. If more than one sequence is possible, the game reports an unresolved ambiguity. For instance, the game will report an ambiguity if both readings of the command "Unlock the door with the key" are executable in the current game scenario.

The inference capabilities discussed so far are common to FrOz and FrOzA; we now turn to what sets FrOzA apart and will lead us to discuss the theory of enlightened update: planning capabilities. Planning is used when no reading is executable, for analysing whether the command includes tacit actions. For each failed reading FrOzA tries to find a sequence of actions (i.e., a plan) which transforms the current game scenario into a scenario where the reading can succeed. If no such plan exists, the reading is discarded, otherwise the plan is concatenated before the reading, enlarging the original sequence of actions. The new list of readings built in this way is reinserted into the action handling module and its execution proceeds as usual.

In order to illustrate the previous behaviour of FrOzA, let us consider again the command "Unlock the door with the key" but now suppose that none of its two readings is executable in the current game scenario. One of the readings fails because there is no "door with the key" in the current game scenario. The other reading cannot be directly executed because the key is not in the player's hands but on a table in front of her. However, for this second reading a plan can be found, namely "to take the key" before unlocking the door; although "take the key" was left tacit by the player, it can be inferred from the game scenario. This plan is concatenated before the original reading and the extended reading is processed again by the action handling module. This time, the input of the action module will be the sequence of actions "Take the key and unlock the chest with it", making explicit the tacit action.

In order to infer tacit actions, FrOzA uses the planning services provided by the planner Blackbox [START_REF] Kautz | Unifying SATbased and graph-based planning[END_REF]. Blackbox works by fixing the length of the plan in advance and iteratively deepening it. This behaviour makes it particularly well suited for our needs because it finds optimal plans (minimal in the number of actions) and does it fast. Fast responses are essential for a natural interaction with the player. For a detailed description of the performance of Blackbox in FrOzA see (Benotti, 2006a;[START_REF] Benotti | Enhancing a dialogue system through dynamic planning[END_REF]. Moreover, optimal plans are crucial, otherwise actions which are executable in the game scenario but completely irrelevant to the player command might be included as tacit actions. For example, a non-optimal planner might not only "take the key" as in our example, but also take and drop other arbitrary objects as well.

The input required by Blackbox are STRIPSstyle problems specified in the Planning Domain Definition Language [START_REF] Gerevini | Plan constraints and preferences in PDDL3[END_REF] which includes the standard elements of a planning specification: the initial state, the available actions, and the goal.

In next section we will present a theoretical account of the intuitions hinted at here by making use of the insights provided by the theory of enlightened update. In particular, we will analyse what information the elements of the planning specifications should contain.

Enlightened update in FrOzA

We will now use FrOzA as a laboratory for exploring the theory of enlightened update [START_REF] Thomason | Enlightened update: A computational architecture for presupposition and other pragmatic phenomena[END_REF]. Using FrOzA we shall construct, step by step, an accurate account of the main principles behind this theory.

The intuition behind enlightened update theory is that when the speaker utters a sentence, as my mother did in our first example, she is not only trying to achieve the obvious effects of the utterance, but is also communicating the ways in which she assumes the world to be, and on which the success of the utterance depends.

Let us make this approach concrete through an example in our game setup. Suppose that the player is inside a room with a locked door while she is holding a golden key in her hands. Then she inputs the command "Unlock the door with the golden key," which is mapped to the semantic representation unlock(door1 key1). The intention behind this utterance is twofold. It is clear that the player wants the game state to be updated according to the effects of the action, that is, she wants to have the door unlocked. But the player also expects the game to recognise the assumptions she is making and on which the success of the utterance depends. In particular, she assumes that the golden key fits into the door lock.

This strategy for updating the shared knowledge is stated formally as the following principle:

ENLIGHTENED UPDATE (EU): "An agent's public performance of an action [A]

that is mutually known to require a commitment C for its successful performance will add to the mutual information the proposition that the agent believes C." (Thomason et al., 2006, p.15).

It is important to notice that in order to be able to perform an EU it must be mutually known that the action, which is being performed publicly, requires its preconditions. In our setup this means that we assume that the exact preconditions required for the successful performance of the action unlock are mutually known (by the player and the game). Such an assumption is represented in the action schema below, which specifies the player preconditions to be equal to the original preconditions of the action.

action:

unlock(door1 key1) preconditions: locked(door1), key(key1), in-inventory(key1), fits-in(key1 door1) player preconditions: locked(door1), key(key1), in-inventory(key1), fits-in(key1 door1) effects:

del: locked(door1) add: unlocked(door1) player effects: del: locked(door1) add: unlocked(door1)

After this action (unlock(door1 key1)) is executed successfully, the player will believe that "the golden key" is a key, and that it is in her hands, facts that she already knew. However, she will also believe that the door is now unlocked, the obvious effect of the action; and that the golden key fits in the door lock, the assumption she made and was confirmed by the success of the action. This means that, when an action is executed, the player KB will be updated not only with the effects of the action but also with its preconditions. When performing this update, the order in which the changes are made is important in order to leave the KB in the intended state. Concretely, the KB should be first updated with the player preconditions and then with the player effects. Otherwise, the preconditions might undo the effects of the action. Moreover, the updates that retract information from the KB have to be performed before the ones that assert information, in order to avoid introducing an inconsistency in the KB. This is the easy case, but what if the action cannot be directly executed (that is, some of its preconditions are false) in the current game scenario?

The EU principle extends naturally to cover these cases. And, in fact, these are the cases where the theory of enlightened update is able to bridge the gaps that arise in everyday interactions.

Enlightened Update with Tacit Actions

To analyse how the EU principle is extended, let us modify our running example a bit in order to return to the game scenario we analysed intuitively in Section 2.3. Suppose that the player does not have a key and she is looking around searching for a way to unlock the door when the game says that there is a golden key lying on a table in front of her. Then she inputs the command "Unlock the door with the golden key." Hence, according to the EU principle, the player knowledge base should be updated with the preconditions of the action. However, one of the preconditions of this action, namely in-inventory(key1), is false in the current game scenario (that is, in both KBs). Clearly, the precondition cannot just be added to the player KB because this will cause a contradiction, but this precondition can be made true in the game scenario by performing the appropriate actions.

The theory of enlightened update defines the following refinement of the EU pattern to handle exactly this situation: [tacitly] to make C true, and S expects H to so act." (Thomason et al., 2006, p.36) In our example, the player is not holding the key and she knows it, and she is trying to unlock the door anyway, knowing that in order to unlock a door you need to have the key in your hands. Hence, FrOzA should act to make in-inventory(key1) true. And it does so by executing tacitly the action take(key1).

EU WITH TACIT ACTIONS (EU/TA): "[Assume that] C is a condition that can be manipulated by an audience H. An agent S is observed by H to be doing A while C is mutually known to be false. H then acts

We should notice here that an action can be left tacit by the speaker, and recognised correctly by the hearer, only if the effects of the action are mutually known by the conversation partners.

Enlightened Update and Incomplete Background Knowledge

In [START_REF] Devault | Scorekeeping in an uncertain language game[END_REF] the theory of Enlightened Update is implemented and tested in COREF, a conversational agent which uses enlightened update to interactively identify visual objects with a human user. In FrOzA we also implement and test the theory of enlightened update but with an added kind of uncertainty: incomplete background knowledge. In COREF, both interlocutors are assumed to have the same background information. In FrOzA, on the other hand, the game has complete and accurate information about the game world, while the player starts the game without information and acquires it as the game evolves. In this setup, modelling enlightened update highlights the issues involved when one of the interlocutors has incomplete background knowledge. Moreover, it illustrates the point that, as conversation evolves, background knowledge accumulates and that a conversational system can use this information to engage in more flexible and robust conversation.

The key question in FrOzA is how it is able to infer the 'appropriate' tacit actions in a setup with incomplete background knowledge. In principle, it just needs to provide Blackbox with the 'appropriate' inputs mentioned in Section 2.3: the initial state, the goal, and the available actions. However, the question of 'what these three elements should contain' raises a number of subtle issues. Their discussion will highlight the kinds of problems that need to be considered when background knowledge is incomplete.

The initial state

The first question is to decide the information that is needed for the initial state. In FrOzA, two types of information are registered: the objective information in the game KB and a subjective view in the player KB. Which of these should be used in order to discover tacit actions? In fact, we need both. Let us analyse this decision by extending our example once again. Suppose that the golden key, which was lying on the table, was taken by a thief without the player knowing. As a consequence, the key is on the table in the player KB, but in the game KB the thief has it. In this new scenario, the player issues the command "Unlock the door with the golden key." If we included in the initial state the objective information of the game KB, FrOzA would automatically take the key from the thief (for example, by using the steal action) and unlock the door for the player, while the player is not even aware where the key actually was. This is clearly inappropriate. Now, if our initial state includes the information in the player KB, FrOzA would decide to take the key from the table and unlock the door with it. But this sequence of actions is not executable in the game world because the key is no longer accessible (the thief has it). More generally, a sequence of tacit actions found by reasoning over the player KB might not be executable in the game world because the player's KB may contain information that is inconsistent with respect to the game KB. Hence, we need both KBs: we infer the actions intended by the player using the information in her KB but we have to verify this sequence of actions on the game KB to check if it can actually be executed. The action inference step is done using the planning services provided by Blackbox on the subjective information, and the action executability step is done using the reasoning services provided by RACER on the objective information. In COREF, by way of contrast, once the tacit actions are inferred they do not need to be checked for executability on the objective information. This is because the COREF setup does not allow any of the interlocutors to have a subjective view of the information; both interlocutors are assumed to share the objective information and hence, tacit actions are inferred solely on the basis of objective information.

An interesting consequence of the fact that the FrOzA setup handles incomplete background knowledge is that we can investigate how this background knowledge accumulates and how it affects the interaction. And it turns out that the more the player knows about the game world, the more actions can be left tacit. For example, suppose that after opening the door, the player locked it behind her and continued to the following rooms investigating the game world. After a while she is back and wants to open the door again. This time it is enough for her to say "Open the door", instead of "Unlock the door with the golden key", because she already knows, and the game knows that she knows, which key fits into this lock.

As a consequence, we can drop a simplifying assumption made in [START_REF] Thomason | Enlightened update: A computational architecture for presupposition and other pragmatic phenomena[END_REF], namely that whether an action is public or tacit is a static matter, corresponding to an arbitrary split in the action database. In FrOzA this distinction is dynamic and correlates with the growth of background information.

The goal

The two remaining questions are what the goal and the actions of the planning problem should be. We believe that answering these two questions is also non-trivial, as it was not trivial to define the initial state. However, we have not yet analysed the subtleties involved in these two issues; here we simply present our initial approach.

Let us start defining what the goal should be. According to EU principles, the game should act to make the preconditions of the action true with two restrictions. First, it must be possible for the game to manipulate the preconditions. And second, the action must be mutually known to require its preconditions. Hence, we define the goal as the player preconditions of the action commanded by the player, excluding those that cannot be manipulated by the actions in the action database.

For example, when the player says "Unlock the door with the key" the goal of the planning problem will only include the atoms:

locked(door1), in-inventory(key1),
The preconditions that cannot be manipulated by the actions available in the action database, such as key(key1) (something that its not a key cannot be transformed into one) and fits-in(key1 door1) (if the key does not fit into the lock it is not possible to make it fit) are not included in the goal.

The actions

To complete the picture, the actions available to the planner are all the actions in the game action database. Its preconditions will correspond to the player preconditions and its effects to the player effects. For the moment, we are assuming that the preconditions and the effects of the actions are shared by the game and the player. Hence, the player preconditions and the preconditions of an action coincide; as well as the player effects and the effects. Relaxing this simplifying assumption, would introduce more dynamism in the distinction between tacit and public actions, and hence would better reflect the case of real conversation.

Conclusions

In this paper we have described FrOzA and used it to explore the enlightened update theory.

The FrOzA setup shows that enlightened update can be implemented using an off-the-shelf reasoning tool such as Blackbox. At present, the solution provided by this setup is not logically complete because our two inference tools (RACER and Blackbox) work independently and are not capable of sharing information (see [START_REF] Benotti | Enhancing a dialogue system through dynamic planning[END_REF] for the technical details). However, we believe that the present implementation is the kind of laboratory that theories such as enlightened update needs. We leave the study of complete reasoning mechanisms and a comparison between our setup and the one implemented in [START_REF] Thomason | Enlightened update: A computational architecture for presupposition and other pragmatic phenomena[END_REF] for further research. We mention in passing that integrating planning capabilities in the framework of a Description Logic reasoner is a topic of current research (see [START_REF] Baader | Integrating description logics and action formalisms: First results[END_REF][START_REF] Liu | Reasoning about actions using description logics with general TBoxes[END_REF]).

We have tested the theory of enlightened update with an added kind of uncertainty common in conversation: incomplete background knowledge. This test yielded two interesting consequences. First, the theory applies but raises a number of subtle issues on the kind of required information, and second, the division between tacit and public actions becomes dynamic. In [START_REF] Thomason | Enlightened update: A computational architecture for presupposition and other pragmatic phenomena[END_REF] whether an action is public or tacit is a static matter, corresponding to an arbitrary split in the action database. In FrOzA, this distinction correlates with the growth of background information; we believe this to be in line with 'the granularity of conversation' as defined in [START_REF] Michiel Van Lambalgen | The Proper Treatment of Events[END_REF] another point which requires further work.

But more remains to be done. There is a deeper kind of incomplete background knowledge, namely when the action preconditions and effects are not mutually known, i.e. when the task model is not shared by the interlocutors. We believe that accounting with such uncertainty in a conversation is one of the most challenging problems that theories such as enlightened update face nowadays.

RIA for an enthusiastic welcome, and lively discussions.

  Figure 1: Architecture of FrOzA

By 'request' we refer to the first part of an adjacency pair (request, acceptance/refusal) as defined in[START_REF] Clark | Contributing to discourse[END_REF]

Decalog 2007: Proceedings of the 11th Workshop on the Semantics and Pragmatics of Dialogue, pages 17-24.Trento, Italy, 30 May -1 June 2007. Edited by Ron Artstein and Laure Vieu.

Acknowledgements

I would like to thank the members of the Dialogue Discussion Group of the TALARIS Team at LO-


Jacques Ginestié

FORMER À L'UNIVERSITÉ LES PROFESSIONNELS DE L'ENSEIGNEMENT, DE L'ÉDUCATION ET DE LA FORMATION : UNE DÉMARCHE DE PROJET AMBITIEUSE

Universitariser la formation professionnelle aux métiers de l'enseignement, de l'éducation et de la formation est l'ambition affichée par la loi de refondation de l'École de la République. L'adoption d'une construction en mode projet engage l'Université et l'académie à s'accorder sur un partenariat de mise en commun de ressources et de moyens nécessaires pour élaborer, mettre en oeuvre et développer une politique ambitieuse articulant recherche, formation et terrain. Cette dynamique de projet est portée par chacun des directeurs d'ÉSPÉ et ses équipes. Ce projet complexe couvre un large empan qui vise tout autant l'installation d'un continuum de formation allant des premiers pas de professionnalisation des étudiants de licence jusqu'à la formation continue des professionnels que la structuration de la recherche à laquelle sont adossée les formations ou au développement du rôle des établissements comme lieu de formation. Il repose sur le rapprochement et le développement de collaborations entre des acteurs très différents afin que de leurs complémentarités naissent une dynamique susceptible de faire évoluer durablement les métiers de l'enseignement, de l'éducation, de la formation. Quatre ans après leur création, les ÉSPÉ ont surmonté la plupart des difficultés. Il reste à conforter ces éléments de structuration, à développer et à renforcer certaines pistes encore mal définies, et à poursuivre les évolutions d'une formation pour qu'elle soit réellement universitaire et professionnalisante.

Instituer une formation universitaire professionnalisante

La création des trente-deux ÉSPÉ au 1 er septembre 2013 est une réelle transformation de la formation des professionnels de l'enseignement, de l'éducation et de la formation. Le recrutement par l'Éducation nationale de ses enseignants et conseillers principaux d'éducation (CPE) se faisait, déjà, depuis 2009-2010, au niveau du master mais sans professionnalisation aux métiers pour lesquels elle recrutait. En ne définissant pas de manière explicite les enjeux de compétences professionnelles, ou plus exactement en les réduisant à la seule maitrise des savoirs de référence qui fondent les disciplines scolaires, cette « première mastérisation » niait le caractère professionnel de ces métiers. De fait, les jeunes enseignants ou CPE recrutés découvraient la réalité de leur métier de manière brutale et abrupte en assurant leurs missions sans aucune préparation et après avoir réussi un concours qui laissait peu de place à l'appréciation de leurs compétences à exercer ce métier.

La loi de Refondation de l'École de la République pose les bases d'une formation universitaire professionnalisante aux métiers de l'enseignement, de l'éducation et de la formation (MEÉF) ; la création des masters MEÉF vise à articuler trois niveaux de maitrise : outre la maitrise des savoirs de référence, l'objectif est bien de développer la maitrise de l'enseignement de ces savoirs et la maitrise du rôle joué par ces professionnels dans le système éducatif et sa nécessaire évolution, afin de permettre à ces jeunes professionnels d'assurer de manière experte les missions d'enseignement et d'éducation qui leurs sont confiées.

En créant les ÉSPÉ comme composante d'une université ou d'une communauté d'universités et d'établissements (COMUE), le caractère universitaire de cette formation est clairement explicité : il appartient à l'Université de s'organiser pour former aux métiers de l'enseignement, de l'éducation et de la formation (MEÉF). En instituant l'obligation de concevoir et de mettre en oeuvre un projet académique de formation universitaire professionnalisante, le cahier des charges invitait plusieurs partenaires à se mettre autour d'une même table pour instituer ce projet et pour le piloter de manière conjointe. Outre l'université intégratrice de la composante ÉSPÉ, le partenariat s'est construit avec les autres universités d'une même académie et avec l'académie elle-même. Cette association partenariale visait bien à assurer la double articulation universitarisation et professionnalisation.

Chaque partenariat est différent selon les contextes locaux : d'une part, une ou plusieurs universités, des universités pluridisciplinaires ou spécialisées, l'existence de COMUE, de très petites ou de très grandes universités… d'autre part, une grande diversité des académies (leur taille en nombre d'élèves et d'enseignants, leur démographie et leur répartition territoriale, leur contexte social…). Chaque projet d'ÉSPÉ est forcément différent car forcément adapté à chacun de ces contextes.

En instituant ce mode projet, c'est-à-dire en invitant l'ensemble des acteurs à construire un projet collectif commun, la dynamique ainsi créée engageait chacun des partenaires à s'accorder sur le sens dans la double acception de signification et d'orientation, au terme formation universitaire professionnalisante aux MEÉF. L'organisation en mode projet, d'une manière générale, est assez ordinaire dans la conduite de la plupart des grands chantiers et les universités sont coutumières de ce mode, habituées à faire des projets pluriannuels pour la formation et la recherche. Elle est originale en soi pour installer et développer une organisation de formation universitaire professionnalisante en rupture avec une forme traditionnelle de formation des enseignants et de cette ampleur que ce soit en termes de couverture géographiquetrente-deux académiesou en termes des effectifs d'étudiants concernésprès de quarante mille étudiants par an -ou encore l'empan des partenariats construits. Elle place le directeur de l'ÉSPÉ au coeur du processus en lui conférant le rôle de chef de projet et donc d'animateur de cette dynamique d'articulation et de construction de sens entre universitarisation et professionnalisation.

Une démarche de projet ambitieuse

Le point de départ de toutes démarches de projet est bien la définition d'un but à atteindre et de la délimitation de ce but et des moyens pour l'atteindre par un cahier des charges. Dans tout projet, il y a une maitrise d'ouvrage, un maitre d'oeuvre et des opérateurs. La maitrise d'ouvrage est assurée ici par le Ministère de l'Éducation nationale, de l'Enseignement supérieur et de la Recherche (initialement, il y avait deux ministères : Éducation nationale, d'une part, et Enseignement supérieur et de la Recherche, d'autre part). Le travail de coordination entre les trois directions générales concernées (Direction générale de l'enseignement supérieur et de l'innovation pédagogique, Direction générale de l'enseignement scolaire et Direction générale des ressources humaines) a été très vite étendu aux autres acteurs que sont la Conférence des présidents d'université, le Réseau national des ÉSPÉ et les Recteurs d'académie. Une structure emboitée a été mise en place entre le projet nationalmettre en place sur tout le territoire national une formation universitaire professionnalisante aux MEÉFet chacun des projets académiques.

Cette maitrise d'ouvrage nationale distingue la démarche de projet mise en place d'autres formes plus classiques. Elle institue simultanément chaque académie comme le bénéficiaire (dans d'autres situations, on parlerait du « client ») des résultats du projetformer les enseignants et les CPE que l'Éducation nationale va recruter pour les affecter dans chaque académieet comme un partenaire actif des organisations mises en place pour les former ; cette simultanéité de rôle n'a pas réellement été prise en compte dans le cahier des charges initial et l'ambiguïté qui peut en résulter a conduit à accroitre la diversité des situations locales. Le paysage universitaire local pèse également largement sur la diversité des situations, notamment de par les rapports institués entre l'université intégratrice de la composante ÉSPÉ et les autres. Ainsi, localement, les partenariats entre université intégratrice, autres universités et académie se sont constitués avec des acceptions très différentes d'une académie à l'autre. Cette diversité est en soi une rupture profonde avec l'idée même d'un modèle unique de projets académiques ; c'est également une richesse qui, dès lors qu'elle fait l'objet d'échanges et de confrontations des choix, renforce la dynamique de construction et d'amélioration des solutions retenues. Il n'y a pas une seule bonne solution modélisable pour être appliquée partout mais une grande variété de solutions adaptées (ou en cours d'adaptation) à la demande nationale et aux contextes locaux. La gestion de ce partenariat peut assez vite se révéler délicate ; bien que non instituée dès le départ, l'installation d'une instance de pilotage du partenariat s'est très vite avérée indispensable.

Ces instances réunissant les présidents des universités, le recteur de l'académie, le président du conseil d'école et le directeur de l'ÉSPÉ ont été constituées (ou sont en cours de constitution) ; elles ont pour objectif de délimiter l'empan du projet académiquemaster MEÉF, professionnalisation en licence, formation continuée en T1 et T2, formation continue diplômante, qualifiante, certificatrice, structuration de la recherche en éducation en lien avec le terrain…de définir ce qui relève de ce projet et ce qui n'en relève pas et d'arrêter le modèle économique de chacune des organisations incluses. De fait, il s'agit de fiabiliser les ressources apportées par chacun des partenaires dans leur engagement à mettre en place les organisations qui sont ainsi décrites dans le projet académique accrédité par le MENESR. L'instance de pilotage a donc une fonction déterminante dans l'élaboration du projet académique en définissant son empan et en arrêtant les ressources affectées et dans le suivi et la régulation du projet une fois qu'il a été accrédité. Le budget de projet devient l'outil de pilotage du projet académique en définissant la part des ressources et en suivant son exécution sur les cinq années des contrats quinquennaux.

Ainsi, se dessinent les grands traits du pilotage des projets académiques avec une instance de pilotage du partenariat, chargée de s'accorder sur le modèle économique du projet, le conseil d'école de l'ÉSPÉ chargé de définir la politique de mise en oeuvre du projet dans le cadre budgétaire fixé par les partenaires et le directeur de l'ÉSPÉ chargé de la mise en oeuvre du projet et de l'animation des équipes qui la prenne en charge.

Un projet ambitieux à concrétiser

La mise en oeuvre du projet académique est en elle-même complexe. Nous pouvons identifier trois axes principaux d'opérationnalisation qui sont en interactions et qui doivent être développés pour pouvoir répondre aux ambitions portées par la loi de refondation : (1) le continuum de formation, (2) l'adossement à la recherche et (3) le pilotage des actions entreprises.

Le continuum de formation

Anticipant sur l'harmonisation de de l'offre de formation des structures Licence-Master, le premier niveau de structuration du master MEÉF était arrêté par le MESR, à savoir sa dénomination et son organisation en quatre mentions (Premier degré, Second degré, Encadrement éducatif et Pratiques et Ingénieries de la formation). Le master est l'élément pivot qui structure le continuum de formation évoqué précédemment.

L'articulation universitarisation et professionnalisation repose sur la constitution d'équipes pédagogiques qui portent cette articulation et sont représentatives de la diversité des acteurs. Le concept initial portait sur leur caractère pluridisciplinaire (disciplines scolaires et universitaires) et pluri-catégoriel (du professeur des écoles au professeur des universités). À ces deux traits, il faut ajouter le caractère pluri-institutionnel afin de rendre compte des réalités des différents partenaires engagés dans le projet. Spontanément, il est assez normal que les personnels affectés dans les ÉSPÉ prennent une part prépondérante dans ces équipes (avec les limites induites par le fait que la proportion des enseignants-chercheurs affectés est très faible, environ 30% en moyenne) ; pour autant, la participation des autres composantes des universités engagées ou de formateurs de terrain mis à disposition est un enjeu pour assurer la pluralité des approches et l'articulation recherche, formation, terrain.

La part de professionnalisation est importante tant en licence qu'en master avec des stages professionnels qui accompagnent les étudiants depuis la seconde année de licence jusqu'à la formation en alternance lors de l'année de stage. Le stage en responsabilité pour les fonctionnaires-stagiaires ne représentent qu'un quart des effectifs concernés par ces stages professionnels. L'accueil d'étudiants en stage est une activité importante qui ne saurait se réduire à des accords de gré à gré entre les étudiants et un enseignant qui les accueille dans sa classe ; la contribution des établissements et des écoles à la formation initiale est une activité à part entière qui implique une coordination entre les partenaires afin de rendre cette activité formative, inscrite dans la progression des enseignements. L'opérationnalisation du concept d'établissement formateur est un enjeu essentiel dans le processus mis en place qui implique un haut niveau de coordination entre les équipes pédagogiques en charge de ces formations et les équipes pédagogiques des établissements qui les accueille. L'accompagnement à l'entrée dans le métier et, par la suite, les organisations de formation continue prolonge le continuum au-delà de la formation initiale dans une perspective de formation tout au long de la vie. On le voit, plusieurs niveaux d'articulation sont en jeu avec la création et le développement d'interactions entre les professionnels de terrain -qu'ils soient tuteur d'un stagiaire, formateur de terrain ou eux-mêmes stagiaires d'une action de formation continueet les chercheurs, mais aussi entre les établissements scolaires et les composantes de l'université (l'ÉSPÉ, les unités de recherche, les UFR…). L'universitarisation de la formation aux métiers du MEÉF repose sur le développement et l'opérationnalisation de ces liens ; elle est un axe primordial de la politique portée par les projets académiques et mise en oeuvre par chaque ÉSPÉ (avec des degrés d'avancée encore très hétérogène d'une académie à l'autre).

L'adossement à la recherche

L'adossement à la recherche est essentiel dans ce processus d'universitarisation. Or, force est de constater que l'on devrait plutôt parler d'adossement à des recherches tant leur diversité est grande, depuis la diversité des recherches dans les domaines de référence des disciplines scolaires jusqu'à la diversité des domaines de recherches qui intéressent l'éducation. Depuis la création des ÉSPÉ, un important travail est accompli pour structurer ce domaine des recherches en éducation comme le montrent plusieurs rapports (Fabre, Penloup, Feliu, & Dubosq, 2016;Ginestié & Roussel, 2016). Des initiatives nationales ont été prises dans cette perspective.

Par exemple, l'appel à projet des territoires numériques éducatifs e-Fran lancé dans le cadre de la 2 e vague des projets d'investissements d'avenir (PIA2) posait clairement la relation recherche, formation, terrain en demande à ce que les projets soient construits en collaboration entre une ou plusieurs unités de recherche, une ou plusieurs ÉSPÉ, une ou plusieurs académies, les collectivités territoriales et des entreprises.

Ainsi, on voit également apparaitre localement des organisations qui visent à fédérer les unités de recherche qui s'intéressent aux recherches en éducation. C'est le cas des onze structures fédératives de recherche qui existent actuellement, à l'initiative des ÉSPÉ et qui regroupent une grande diversité de laboratoires allant des neurosciences à la diffusion des sciences, en passant par la psychologie, la sociologie, l'anthropologie, les sciences de l'éducation… L'université d'Aix-Marseille est allé un peu plus loin dans cette direction en inscrivant dans sa politique scientifique un domaine transverse intitulé « Apprentissage et Éducation ».

L'adossement à la recherche ne relève pas simplement du volontarisme des acteurs, il suppose un double mouvement de structuration au niveau national et au niveau local, le premier devant permettre, par une politique d'investissement sur ces domaines de recherche, la structuration au niveau local en soutenant les efforts fait dans ce sens.

Le pilotage des actions

Les enjeux de création des ÉSPÉ vont bien au-delà de la mise en place de masters MEEF, ils engagent les universités dans la structuration d'un secteur éducation organisant enseignement et recherche : enseigner est un métier qui s'apprend et il s'apprend à l'université dans des formations universitaires ancrées sur les terrains où ce métier s'exerce et adossé à des recherches qui se préoccupent tout autant de comprendre les processus d'apprentissage des élèves que d'apprécier l'efficacité des processus d'enseignement-apprentissage ou de qualifier l'impact des contextes et des milieux dans lesquels il s'exerce. Les projets académiques sont des projets globaux qui visent tout autant à inscrire la professionnalisation des étudiants à ces métiers dans un continuum d'une progression qu'à l'éclairer par la recherche.

Manager de tels projets repose sur l'institution d'instances de dialogues entre les acteurs afin de délimiter les plans d'actions, d'identifier les actions à entreprendre, de réunir les compétences nécessaires pour conduire ces actionset, au passage, de réunir les conditions rendant possible la réalisation de ces actionset de gérer les organisations humaines en veillant à maintenir la cohérence du projet global et sa pertinence en regard des visées institutionnelles mais également des visées des partenaires. Ce management dynamique repose pour l'essentiel sur le directeur de l'ÉSPÉ et l'équipe de direction qui l'entoure. Gestionnaires d'une composante universitaire, coordonnateurs d'équipes pédagogiques et de recherche, négociateurs des engagements de chacun des partenaires, impulsant des dynamiques poussant chacun des acteurs à innover et construire un ensemble performant, les directeurs et leurs équipes sont les porteurs de l'ambition politique de l'universitarisation des formations professionnelles aux métiers de l'enseignement, de l'éducation et de la formation. La réussite de l'entrepriseet les premiers résultats, quatre années après la création des ÉSPÉ sont encourageantssuppose de contredire le premier principe de la théorie des systèmes qui dit que le tout est strictement égal à la somme des parties lorsque celles-ci s'ignorent entre elles. Améliorer les performances du système éducatif français, réduire les inégalités sociales par une École qui intègre et non pas qui exclue, lutter efficacement contre toutes les formes de déterminisme, viser l'excellence par l'élargissement de l'égalité des chances… autant de formes des objectifs de refondation de l'École de la République, d'objectifs qui montrent à quel point la formation universitaire professionnalisante des professionnels en charge, par l'exercice de leur métier, de les atteindre, est un des piliers porteur de ce processus de refondation. C'est la mission des directeurs d'ÉSPÉ et de leurs équipes de direction.

Références

Pr. Jacques Ginestié

Aix-Marseille Université, EA 4671 ADEF Directeur de l'ÉSPÉ Aix-Marseille Directeur de l'unité de recherche EA 4671 ADEF et de la fédération de recherche FED 4238 SFERE-Provence Président du Réseau National des ÉSPÉ

  Fabre, C., Penloup, M.-C., Feliu, F., & Dubosq, J. (2016). Enquête nationale sur les forces de recherche impliquées dans le champ de l'apprentissage et de l'éducation (DGESIP, Trans.) (pp. 84). Paris: Ministère de l'Education nationale, de l'Enseignement supérieur et de la Recherche. Ginestié, J., & Roussel, G. (2016). Les recherches en éducation et leur articulation avec la formation et le terrain. (112 p.), Paris: R-ESPE.


Liviu-Octavian Varga

Martin Heusse

Roberto Guizzetti

Andrzej Duda

Improving Robustness of Beacon-Enabled IEEE 802.15.4 with Round-Robin Channel Diversity

Keywords: Wireless Sensor Networks, multi-channel, beaconenabled 802.15.4, IPv6, auto-configuration

Reliable wireless communication even in adverse conditions is the key for building the energy efficient and dependable Internet of Things. In this paper, we explore the benefits of channel diversity for enabling efficient wireless communication: we propose MRR (Multi-channel Round-Robin), a backwardcompatible evolution of beacon-enabled IEEE 802.15.4 in which energy constrained nodes take advantage of additional active periods operating on different channels in a round-robin way. Each active period starts with a beacon sent on a cyclically changing channel, which then allows an associated device to transmit data on the channel used for the beacon. MRR schedules the additional active periods at carefully selected instants to avoid direct beacon collisions.

To motivate our work, we first experimentally corroborate previous findings that channel diversity is an effective way of mitigating variable or poor transmission conditions. Then, we observe that channel diversity improves the quality of transmission even better than expected-it appears that wireless sensor nodes have a radiation pattern that changes significantly from one frequency channel to another, which often results in a considerably improved gain when using the right communication channel. The evaluation of the MRR scheme through measurements on a real indoor multihop testbed shows that the proposed scheme results in significantly improved Packet Reception Ratio even without resorting to e.g. channel blacklisting. These results confirm the benefits of multichannel operation and exhibit a fully functional solution that does not add a large overhead compared to using a single channel.

I. INTRODUCTION

The IEEE 802.15.4 standard [START_REF]IEEE Standard for Local and metropolitan area networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs)[END_REF] is an efficient and lowpower communication technology for wireless sensor networks. In the beacon-enabled mode, time is divided in superframes composed of active and inactive periods (cf. Fig. 1). During inactive periods, a node can switch off the radio to save energy. Multihop operation requires a cluster-tree topology that nodes may create based on Incoming and Outgoing superframes (cf. Fig. 2): a node associates with a parent coordinator, uses the Incoming active period to send frames to the parent, and acts itself as a coordinator on behalf of child nodes by communicating with them during the active period of its Outgoing superframes.

The goal of our work is to improve the communication quality in terms of the packet delivery ratio by exploiting channel diversity in wireless sensor networks based on IEEE 802.15.4. The main issue with taking advantage of channel diversity is to avoid deafness-two nodes that want to communicate in a multi-channel setting, need to agree on the common channel to use. Moreover, nodes need additional mechanisms to discover used channels and assess their quality. They also need to choose channels and beacon transmission times in a way to avoid interference and distribute the load over the channels [START_REF] Zhou | MMSN: Multi-Frequency Media Access Control for Wireless Sensor Networks[END_REF], [START_REF] Chowdhury | CMAC -A multi-channel energy efficient MAC for wireless sensor networks[END_REF], [START_REF] Chen | A Multi-Channel MAC Protocol for Wireless Sensor Networks[END_REF], [START_REF] Jovanovic | TFMAC: Multi-channel MAC Protocol for Wireless Sensor Networks[END_REF], [START_REF] Kim | Y-MAC: An Energy-Efficient Multi-channel MAC Protocol for Dense Wireless Sensor Networks[END_REF], [START_REF] Borms | Low-Overhead Dynamic Multi-channel MAC for Wireless Sensor Networks[END_REF], [START_REF] Wu | Realistic and Efficient Multi-Channel Communications in Wireless Sensor Networks[END_REF], [START_REF] Incel | MC-LMAC: A multi-channel MAC protocol for wireless sensor networks[END_REF]. Our aim is to minimize the overhead of such operations yet enable an efficient use of multiple channels while remaining backward compatible with the 802.15.4 standard (legacy 802.15.4 devices can still operate in the network comprising nodes with the enhanced multi-channel operation).

Based on an experimental evaluation of channel performance in outdoor and indoor conditions, we propose MRR (Multi-channel Round-Robin), a scheme for using multiple channels in a round-robin way by extending the standard operation of beacon-enabled 802.15.4. In the scheme, a node schedules additional active periods operating on different channels during the inactive period of the standard beacon interval. Each active period starts with a beacon sent on a cyclically changing channel so that associated devices may send their packets on the channel used for the beacon. MRR schedules the additional active periods at random instants to avoid beacon collisions. The scheme keeps backward compatibility with nodes that do not support multi-channel operation.

We start the paper with an experimental study of 802.15.4 motes in real radio conditions. The study shows that transmissions on different channels exhibit significantly different performance both in outdoor and indoor environments. This first insight corroborates the previous research results and we posit that the observed differences come from antenna radiation patterns variations whereas multipath fading is in general the We then introduce the proposed scheme and evaluate its performance through measurements on a realworld multihop testbed deployed indoor. The measurements show that the scheme results in a significantly improved PRR (Packet Reception Ratio) without having to resort to complex schemes to adapt to channel quality variations.

II. EXPERIMENTS WITH MULTI-CHANNEL TRANSMISSIONS Much recent research pointed out the benefits of multichannel transmissions [START_REF] Watteyne | Mitigating Multipath Fading through Channel Hopping in Wireless Sensor Networks[END_REF], [START_REF] Srinivasan | Understanding the Causes of Packet Delivery Success and Failure in Dense Wireless Sensor Networks[END_REF], [START_REF] Bardella | An experimental study on IEEE 802.15.4 multichannel transmission to improve RSSIbased service performance[END_REF], [START_REF] Wu | Realistic and Efficient Multi-Channel Communications in Wireless Sensor Networks[END_REF], [START_REF] Chen | Enhanced MAC channel selection to improve performance of IEEE 802.15.4[END_REF]. In this section, we corroborate their finding on our specific hardware with experimental measurements and provide a new possible explanation for the improved gain from channel diversity that is not usually put forward in the literature. In the measurements, we use sensor motes with a Cortex-M3 clocked at 12 MHz with 32KB RAM and 256KB flash as well as a 802.15.4 2.4GHz radio transceiver. They run a fully operational IP protocol stack based on Contiki [START_REF] Durvy | Making Sensor Networks IPv6 Ready[END_REF] that integrates the IEEE 802.15.4 beacon-enabled mode and supports IP routing over 6LoWPAN adaptation.

A. Outdoor Radiation Pattern

The first experiment takes place outdoors on a large empty parking lot with the receiver node in the middle, one meter above the ground and the sender on a robot that circles around the receiver. The constant distance between the two nodes is maintained using a string between the center of the circle and the robot. Fig. 3 shows the average RSSI (Received Signal Strength Indicator) at each robot position at which, the sender transmits three trains of 20 packets on three different channels. We perform measurements one after the other so the atmospheric conditions remain constant during the experiment. We can observe that the signal strength notably varies with the aspect angle. For instance, the pattern in Figure 3b is expected-it corresponds to a typical dipole radiation pattern. What is less expected, though, is the difference of up to 10dB from one channel to another in many directions. Furthermore, channel 11 has a higher signal reception strength in many, but not all directions.

This observation for the outdoor case, in which there is a single path between the sender and the receiver, sheds light on the more complex case with multiple paths, i.e. indoor [START_REF] Watteyne | Mitigating Multipath Fading through Channel Hopping in Wireless Sensor Networks[END_REF]. The power fractions of the signal sent on each of the multiple paths between the sender and the receiver change when the sender uses different channels. At the receiver, the reception gain for each of the path will also vary. So, the signal that results from the combination of the incident radio waves will strongly depend on the channel used. The antenna radiation pattern variations have a significant effect at any distance between the sender and the receiver and it adds up to the radio channel multipath fading sensitivity to the wavelength, which is usually rather limited at a short distance (for path lengths differing by 1m, the coherence band is as large as the entire 2.4GHz ISM band [START_REF] Watteyne | Mitigating Multipath Fading through Channel Hopping in Wireless Sensor Networks[END_REF]). In essence, both effects combine and add up to each other [START_REF] Varga | Why is frequency channel diversity so beneficial in wireless sensor networks?[END_REF].

B. Indoor Measurements

Indoor conditions are different from those observed outdoors with multiple paths even when a sender and a receiver are in the same room. Our experiment involves a fixed transmitting node and a mobile receiver that moves away from the sender by steps of 1.5 cm, which is well below the wavelength. In each position, the sender transmits three bursts of 20 packets on different channels, then the receiver moves to the next position.

Fig. 4 presents the number of received packets at each position. The position of the receiver has a major impact on the signal strength and consequently on PRR. We performed several runs to assess the stability of the results, even though only one is presented here due to space constraints. We note that, in general, channel 11 gives better results than other channels, which reflects the overall better gain observed for this channel outdoor. Nevertheless, there are positions, e.g. around step 700 where other channels give much better results.

Figure 5 represents the histograms of the RSSI variation when changing channel over one third of the ISM band at various positions at a distance of 8 to 10 meters. RSSI changes of 10dB or more are routinely witnessed, which confirms the previous findings.

The results show that we can greatly benefit from better transmission performance by taking advantage of channel diversity, both in indoor and outdoor cases. However, we still need to organize the operation of nodes, since they already have their place in a cluster-tree topology. Actually, we have chosen to enhance the 802.15.4 beacon-enabled mode with the MRR (Multi-channel Round-Robin) proposal to notify other nodes with what channel to use and when.

Packets received

Position (cm)

q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 200 400 600 800 sent by a coordinator node on a given main channel delimit the beacon interval that begins with an active period for communication between child nodes and the coordinator. The proposed MRR scheme consists of scheduling additional active periods during the standard beacon interval. Each active period starts with a beacon sent on a cyclically changing channel (the channels are different from the main channel). In this way, associated devices can transmit data on the channel used for the beacon, in the immediately following active period.

Fig. 6 illustrates the principle of the MRR scheme: Node 1 sends 3 additional beacons on 3 different channels during the standard beacon interval (the Beacon Order BO of 6 on a single channel is equivalent to BO=4 on all 4 channels). The choice of channels allows covering the entire frequency band of 802.15.4 with four channels: 11, 16, 21, 26. An adaptive mechanism can be implemented, like blacklisting a channel when a low PRR is experienced.

We define a superframe slot as an active period of SD duration placed at integer multiples of SD (SD is the superframe duration, cf. Fig. 1). Beaconing nodes can choose any slot and any channel for their additional beacons-Section III-A proposes a simple algorithm for choosing the slots and channels.

Note that MRR is backward compatible with the 802.15.4 standard: a device that does not implement MRR can still associate with a coordinator and communicate with other nodes on a single channel. In other words, we replicate the superframe on several channels to improve PRR while remaining standard compliant on each individual channel.

As our solution is based on the beacon-enabled 802.15.4 mode, each coordinator will have several associated devices. We recall that if two or more nodes have frames to send in the same superframe, they use the standard slotted CSMA/CA method to avoid colliding repeatedly.

A. Determining StartTimes on Multiple Channels

In the standard, the StartTime parameter is the time offset between the Incoming and the Outgoing superframes. In MRR, there is one StartTime per channel and several Incoming superframes.

To avoid beacon collisions, we propose to start with a random choice of slots for the additional beacon transmission times-the choice comes from a uniform distribution of available slots (cf. 6). After an initial selection of slots, a joining node first listens during those slots to check if they are used by other nodes. If any activity is detected, this particular slot is marked as not available and another one is considered (cf. Fig. 7). The slots of the parent node are marked not available from the start. Such a distributed solution is suitable for networks with sub-cluster trees having different parameters of superframe durations and beacon intervals, giving a high degree of flexibility to schedule the instants of sending beacons.

A node includes the information on the number of additional beacons to send, their slots, and their channels in beacon frames. We need one byte to represent the current slot and another one for the total number of slots used. Then, for each extra slot, we need two bytes for the slot and the corresponding channel (see Figure8). The payload of a single beacon is thus enough for a node that tries to join the network to get the necessary information to synchronize with other nodes. This mechanism allows for great flexibility in choosing beacon slots. The same slots can be used for different channels, but also on the same channel in different regions of the network, if two nodes do not hear each other. The mechanism does not guarantee that beacons do not collide with a third node, but beacon collisions are generally not harmful, since IEEE 802.15.4 transmissions are effectively quite robust [START_REF] Varga | GreenNet: an Energy Harvesting IP-enabled Wireless Sensor Network[END_REF].

The only overhead of the solution is the extra information included in beacons. If we target a specific duty cycle, the multichannel solution will not consume more energy than the standard beacon-enabled mode. However, it is clear that if certain nodes do not support MRR communication, their potential data rate will be reduced as they will have to wait more between two slots on the same channel.

B. Dealing with Multicast Frames

Multicast frames need special handling if legacy nodes are present as they only listen to beacons on a single channel. In this case, if we send a multicast frame on a different channel than the one on which a single-channel node operates, it will be received by all other nodes, but not by the legacy one. To overcome this issue, we propose to change multicast frames into a series of unicast frames for the associated devices, which guarantees that the frame will be received by all the nodes, even when they wake up for a subset of beacons. When the single-channel node wakes up, it will retrieve the multicast frame using the usual unicast transmission procedure: it gets notified that it has a pending frame in the beacon and requests its transmission.

IV. EVALUATION AND PERFORMANCE RESULTS

We have implemented MRR on the previously described motes running Contiki and set up an indoor testbed for validating the performance of MRR:

6 nodes arranged in a line separated by a distance of typically 2 office rooms (or 10m to 15m, cf. Fig. 9). Even though the setup is of a limited size, the environment allows for obtaining realistic results in a deployed operational network: all kinds of interference are taken into account (interference from WLANs, humans, obstacles, etc.). In this set up, even though we use the maximum transmission power (6 dBm), many packets are lost. However, by using 4 channels [START_REF] Srinivasan | Understanding the Causes of Packet Delivery Success and Failure in Dense Wireless Sensor Networks[END_REF][START_REF] Varga | Why is frequency channel diversity so beneficial in wireless sensor networks?[END_REF][START_REF] Abdeddaim | Multi-Channel Cluster Tree for 802.15.4 Wireless Sensor Networks[END_REF]26) evenly spread along the whole ISM 2.4GHz band, at least one of them always leads to a PRR over 50%.

Recall that beacons are broadcast frames, they do not use neither retransmission nor clear channel assessment. Hence, to ease the comparison with unicast frames, we have configured no retransmissions for unicast frames when the acknowledgment is not received, so nodes attempt to transmit each frame only once.

Each run lasts long enough for the transmission of 15,000 beacons on each channel. As for unicast frames, depending on the node placement in the chain topology and the channel number, the number of acknowledged frames or missed ones varies from 200 to 15,000 (except for two cases in which there were only about 20 frames on a particular channel between two nodes). The unicast frame size is 22 bytes and the beacon frame size is 61 bytes. Figs. 10 and 11 represent the percentage of received beacons and acknowledgments averaged over 10 runs. The performance of some channels is highly variable, so it readily appears that choosing a channel and sticking to is not a viable strategy.

Continuously using multiple channels for packet transmission is a double-edge sword, though: packets are transmitted alternatively on good and bad channels, so we need to estimate the real gain of spreading transmissions on several channels with a metric that reflects the transmission quality on a given channel. For this purpose, we have chosen the familiar Expected Transmission Count (ETX) metric [START_REF] De Couto | A High-Throughput Path Metric for Multi-Hop Wireless Routing[END_REF] that captures the average number of attempts required to transmit a frame. ETX is inversely proportional to PRR:

ETX = 1/PRR.
We extend this metric to communication on several channels by defining Multichannel ETX (METX): Eq. 1 represents the probability of missing a transmission on one or several channels until the frame is received. We first define F (l), the probability that a frame is successfully received after l attempts (or maybe dropped after the k-th attempt):

F (1) = 1 n n-1 i=0 P i F (2) = 1 n n-1 i=0 (1 -P i )P (i+1) mod n METX_2 METX_3 METX_4 METX_5 METX_6 Sum_ETX_26 Sum_ETX_21 Sum_ETX_16 Sum_ETX_11
F (k -1) = 1 n n-1 i=0 k-3 j=0 (1 -P (i+j) mod n ) P (i+k-2) mod n F (k) = 1 n n-1 i=0 k-2 j=0 (1 -P (i+j) mod n ) and METX = k j=1 jFj, (1)
where P i is the probability of a successfully reception on channel i (equal to 1-PRR), n is the number of channels (n = 4 in our example), and k the maximum number of retransmissions. In a nutshell, METX represents how many retransmissions are needed to send a packet, taking into account different transmission probabilities on each channel.

To better understand the trade-offs of multi-channel communication, Figure 12 shows the average (along with the standard deviation) METX for each hop (indexed by the node number) and the sum of ETX or METX for different combinations: i) Sum_ETX_26, Sum_ETX_21, Sum_ETX_16, Sum_ETX_11 are the sums of ETX_n when channel n is used for all hops, ii) Sum_METX, the sum of METX over all hops (we take into consideration all channels and the number of expected transmissions based on the performance of each channel), and iii) minETX, the ideal ETX metric, which corresponds to the one we got on the best performing channel for each hop (a posteriori).

The sum of METX comes often close to minETX, which is notable because METX corresponds to a systematic frame transmission on all channels in a round-robin way without any evaluation of the channel quality, whereas implementing minETX would require at least a periodical channel probing mechanism and a significant signaling traffic. METX is a poor metrics for node 6 because the only usable channel is 11. This effect would call for some channel blacklisting mechanism and it is also the reason why Sum_METX is larger than Sum_ETX_11.

The fact that upward frames are always transmitted after a beacon reception effectively increases the probability of a successful transmission: the upward ETX does not grow as notably as in the downward direction, when the conditions worsen (Fig. 12).

Our multi-channel scheme contributes to the good performance of the network. The main drawback of using a single channel is probably the fact that a joining node might not be able to receive beacons on a specific channel (or just a few). Consequently, it cannot associate and join the network. The Multi-channel Round-Robin scheme overcomes this problem by enabling the use of other channels.

Another important aspect to point out is that although the nodes did not move at all between the experiments, in one case, channel 26, at the end of the spectrum band, performed the best. In the other case, it was channel 11 at the other end of the spectrum band. As the environment is dynamic (for example, people moving around), the quality of a WSN can be drastically impacted. In a real deployment of a WSN, the distance between nodes could be in the range of 5 to 10 meters. Hence, channel diversity becomes necessary to attain good performance.

V. RELATED WORK The IEEE 802.15.4e amendment [START_REF]IEEE Standard for Local and metropolitan area networks-Part 15.4[END_REF] updated the previous standard [START_REF]IEEE Standard for Local and metropolitan area networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs)[END_REF] to accommodate new functionalities such as channel hopping: Time-Slotted Channel Hopping (TSCH) and Deterministic and Synchronous Multi-Channel Extension (DSME). TSCH mode [START_REF] Thubert | IETF 6TSCH: Combining IPv6 Connectivity with Industrial Performance[END_REF] basically defines a couple of timeslots and channel frequencies for each communication link between two devices. The major challenge in this mode is node synchronization as well as allocating slots between two synchronized devices. At the same time, TSCH has the advantage of the fact that once it has a well established schedule of slots allocated to nodes, there is no need of CSMA/CA as in most cases, only two nodes will communicate during the same slot on any single channel.

The DSME variant uses periodical standard beacons and enables multiple-channel communications only during the contention-free period (CFP): it assigns one or more slots to any associated device that asks for a Guaranteed Time Slot (GTS). The main drawback of this variant is that if the beacon is not received, there will not be any communication afterwards (no CFP), so the channel on which beacons are sent must be carefully chosen.

Watteyne et al. showed that multipath fading can cause destructive interference, which results in no signal seen at the receiver [START_REF] Watteyne | Mitigating Multipath Fading through Channel Hopping in Wireless Sensor Networks[END_REF]. To overcome the deep fading, the first solution is to move the node by a few centimeters (it can cope with fading at the node, but it may also decrease the quality of a link to another node) or by changing the channel. The authors explained that a change of 5 MHz (the difference between two adjacent channels) is enough to overcome adverse multipath fading.

Srinivasan et al. observed that Telos and MicaZ sensors exhibit link asymmetry, a "grey region" of reception, and temporal variations in packet loss [START_REF] Srinivasan | Understanding the Causes of Packet Delivery Success and Failure in Dense Wireless Sensor Networks[END_REF]. Packet losses are highly correlated over short time periods, but they are independent over longer periods. They also underlined that long-term asymmetries are rare.

Many authors proposed to take advantage of multiple channels in cluster-tree sensor networks. MC-LMAC (Multi-Channel Lightweight Medium Access Control) [START_REF] Incel | MC-LMAC: A multi-channel MAC protocol for wireless sensor networks[END_REF] is based on a scheduled access: each node controls a timeslot to transmit on a particular channel. Nodes use a common channel to exchange control information. TMCP (Tree Based Multi-channel Protocol) is a centralized solution proposed to minimize the interference within the tree by creating several subtrees rooted at the PAN coordinator: each subtree operates on an orthogonal channel [START_REF] Wu | Realistic and Efficient Multi-Channel Communications in Wireless Sensor Networks[END_REF]. However, nodes in the same subtree keep on colliding mainly because TMCP only reduces collisions among the 1-hop neighborhood of the PAN coordinator. Several other papers had similar objectives [START_REF] Zhou | MMSN: Multi-Frequency Media Access Control for Wireless Sensor Networks[END_REF], [START_REF] Chowdhury | CMAC -A multi-channel energy efficient MAC for wireless sensor networks[END_REF], [START_REF] Chen | A Multi-Channel MAC Protocol for Wireless Sensor Networks[END_REF], [START_REF] Jovanovic | TFMAC: Multi-channel MAC Protocol for Wireless Sensor Networks[END_REF], [START_REF] Kim | Y-MAC: An Energy-Efficient Multi-channel MAC Protocol for Dense Wireless Sensor Networks[END_REF], [START_REF] Borms | Low-Overhead Dynamic Multi-channel MAC for Wireless Sensor Networks[END_REF], but their proposals all involve non-backward compatibility with the standard 802.15.4 protocol.

Abdeddaim et al. proposed MCCT (Multi-Channel Cluster Tree), a cluster-tree construction protocol for nodes in IEEE 802.15.4 beacon-enabled mode [START_REF] Abdeddaim | Multi-Channel Cluster Tree for 802.15.4 Wireless Sensor Networks[END_REF]. By using several orthogonal channels throughout the network, it reduces collisions between control and data frames, which leads to better packet delivery ratio and improved fairness. MCCT includes a method to build a cluster-tree suitable to minimize beacon collisions: the neighbor discovery procedure uses a dedicated control channel in parallel to the superframe structure of IEEE 802.15.4. This control channel is used for channel assignment and superframe scheduling with channel diversity. Romaniello et al. designed a Multi-Channel Beacon Train (MCBT) protocol [START_REF] Romaniello | Fast and energy-efficient topology construction in multi-hop multichannel 802.15.4 networks[END_REF] that accelerates the process of joining the network, which is critical for energy harvesting nodes. They can indeed scan the channel continuously for much shorter periods than non-rechargeable battery operated nodes. Nevertheless, in both discussed schemes, the association and further communication between any given device-coordinator pair takes place on a single channel, so that, in a cluster, communications do not benefit from any channel diversity.

Discussion

Compared to MCCT or MCBT, the scheme proposed in this paper brings a significant improvement of the Packet Delivery Ratio by enabling communication on several channels between device-coordinator pairs. We do not compare it experimentally with TSCH or DSME, because implementing the variants requires a major additional effort while the main point of the paper is to confirm experimentally the benefits of multi-channel transmissions and propose a simple backward compatible scheme that shows the improved performance over the standard. Competing with the variants was not the primary goal of the paper, however, we plan to port OpenWSN that includes TSCH on our motes and compare its performance with MRR on a larger testbed.

Nevertheless, compared to TSCH, MRR is a fully operational solution that includes the routing mechanism and requires no additional signaling. There is no doubt that TSCH could lead to a more efficient operation, because the communication channels between each two nodes can be fine tuned and completely avoid channel interferences when several nodes communicate in the same time. But MRR has also a room for improvement, like banning those channels that do no work well for a majority of nodes.

One notable difference between MRR and DSME is that in MRR, beacon transmission benefits from channel diversity, which can notably increase the effective coverage of each coordinator, as well as frame reception reliability. DSME restricts the use of several channels to contention-free transmissions after an explicit reservation handshake, which may only happen on a given fixed channel.

VI. CONCLUSIONS Our experimental results show that taking advantage of multiple channels is paramount to improve the quality of communications that use publicly available radio bands. Indoor environments often vary (people move around, doors open/close etc.) so the radio channel quality changes in a unpredictable way. The best way to fight fading and interference is to use multiple channels that span the whole available frequency band.

In this paper, we have proposed MRR (Multi-channel Round-Robin), a scheme that uses multiple channels in a round-robin way. A node schedules additional active periods operating on different channels during the inactive period of the standard beacon interval. Active periods start with beacons sent on different channels. A joining node can transmit a data packet on the same channel as the received beacon. We have also proposed a random allocation scheme to choose the instants of the additional active periods to avoid beacon collisions. MRR integrates perfectly well with beacon-enabled 802.14.5 by using beacons on multiple channels to invite nodes to use a given channel for communication.

The evaluation of the proposal through measurements on a real-world multihop testbed deployed indoors shows that the scheme results in significantly improved PRR.

A simple and efficient extension to MRR would be to to avoid using the channel on which beacon transmission results in poor performance. The change needs to be done with caution though, as not all associated devices perceive the same link conditions, so the change requires an explicit feedback from all nodes. A device can simply just skip beacons sent on a channel that exhibits poor performance. Along the similar lines, a node may avoid sending unicast packets on particular channels if their PRR is low. Nodes that do not have any associated devices can save energy by only sending beacons once in a while or on a single channel until they receive a request for association, as it has been proposed elsewhere [START_REF] La | Energy-Efficient Multi-Hop Broadcasting in Low Power and Lossy Networks[END_REF].

Figure 1 :Figure 2 :

 12 Figure 1: 802.15.4 superframe structure. Our motes only use the Contention Access Period (they do not use the Contention Free Period).

Figure 3 :

 3 Figure 3: Reception patterns for an 802.15.4 device

FigureFigure 5 :

 5 Figure Number of received packets on different channels when the receiver moving away from the sender.

Figure 6 :

 6 Figure 6: Principle of MRR. During the standard beacon interval delimited by two beacons on the same channel (Channel #1), a node sends additional beacons on different channels (Channels #2, #3, #4) to take advantage of channel diversity. The beaconing slots are delimited by the black vertical lines.

Figure 7 :

 7 Figure 7: Distributed slot selection for nodes joining the network. Random selection of beaconing slots and avoidance of overlapping active periods.

Figure 8 :

 8 Figure 8: Extra information included in the beacon payload.

Figure 9 :

 9 Figure 9: Node placement in the experiments.

Figure 10 :Figure 11 :

 1011 Figure 10: Mean and standard deviation of Beacon Reception Ratio at each node.

Figure 12 :

 12 Figure12: Mean and standard deviation for the METX metric at each node, sum of ETX when using the same channel along the chain of node, METX for multi-channel operation and ETX if each hop used the best available channel