Patricia Marzin
email: patricia.marzin@imag.fr

Cédric D'ham

Eric Sanchez

How to scaffold the students to design experimental procedures? A proposition of a situation experienced by 108 high-schools students

. The labwork situation is described as a task tree, starting from the initial scientific or technical question to solve through the experiment. This kind of tree organisation refers to a downward analysis of a problem. Our analysis of the student production looks up the experimental procedures of the students in comparison with the reference task tree.

2) Methods and Samples,

The experimentation was held during 2 school years, in 2005 and 2006. The sample is composed of 108 students in the terminal level of the upper secondary school (ISCED level 3A-17/18 years old), composed by 6 groups of 18 students, distributed in 6 trinomials of 3 students (36 trinomials in all). Each sequence holds out 90 min. All the student activities were recorded on audio and video numeric support.

The concrete activity proposed to the students is a palaeontology experiment where they have to find a procedure in order to determine the facial angle of several homine crania. To solve this problem they have to choose 4 characteristic points on a cranium, and they have to project those points on a plan, to obtain 2 segments from which they can obtain the facial angle (Fig 1). This value depends on the prognathism of the cranium, which is an evolution indicator. To that, the students use a paper material that includes the description of the task to do and the problem to solve, some definitions (facial angle), the explanation of the measurement method and the work specifications. Students have the possibility to write a text, to complete the points on a cranium drawn beforehand or to write a free schema. The expert procedure is composed by this ten tasks: (T1) identification of the measurement points on the cranium, (T2) choice of two couples of points, (T3) fix the slide on the wall of the aquarium, (T4) place the cranium in the aquarium, (T5) place a laser pointer perpendicularly with transparency, (T6) aim each point, (T7) mark the points on the transparency, (T8) remove the transparency, (T9) plot the straight lines, (T10) measure the angles with a protractor. The experiment was held in three times: A. In a first exploratory experiment (18 trinomials), we tested how the students write an experimental procedure. Students had to find and to control the totality of the ten tasks by themselves. B. A new situation (12 trinomials) without the control of perpendicularity by the students: the teacher takes this task in charge and he/she controls it, because this task doesn't focus on the prognathism concept. We asked the students to write their measurement protocol and, in order to assess the quality of their protocol, to use the following criteria: (a) it leads to answer the scientific problem (i.e. evaluation of the prognathism -criteria of relevance) (b) it leads to obtain the same value of the facial angle for the same cranium (criteria of reproducibility) and (c) it can be used by another person (criteria of communicability). An additional criteria was used but not explicitly: (d) the protocol must be effective for measuring the diverse craniums of the sample (criteria of executability in the explored domain). C. In a third step (6 trinomials), we added to the second situation a communication situation between students: they had to write down their experimental procedure for an other group of students who had to do the measurements according to the given procedure.

3) Results,

A. The first experiment showed that most of students managed to write an experimental procedure. Only two trinomials didn't. We have identified two main kinds of problems: -Students had too much and too different tasks to lead, including the control of precision of the measurements, which is usually not devoted to them: for example they had difficulties to control the perpendicularity of the measurements (laser pointer, cranium position).

-Students had no possibility to think about criteria to choose the points on the cranium, and they had anything in the situation, which showed them if their results were relevant or not. B-In this experiment, students focused their attention on the points' choice. They found pertinent criteria, but most of them didn't write any experimental procedure. They placed their points on the cranium drawing, but the majority of the trinomials (10/12) did not write texts: they only described and justified the choice of the points, because they had not enough time to write them down. C -In this last step, we introduced a real communication situation. All the trinomials have written an experimental procedure, corresponding to our attempts: the tasks are clearly formulated, communicable, and relevant compared to the initial problem. Several tasks have been written by all the students (T4, T5, T9). The first two tasks are mainly written on the drawing with legends. Several tasks are almost not written, because they are explained by the drawing figure (T1, T2), or because they are related to a too high level of details (T8). It appeared that the text is different if it is addressed to the teacher or to an other trinomial who has to follow the procedure.

4) Conclusions Implications,

The proposition to make the students design an experimental procedure included:

a knowledge analysis combined to a task analysis, an evaluation of the distance between the tasks to do and the knowledge to learn, a selection of the tasks that are devoted to the students, and those devoted to the teacher, an analysis to anticipate the difficulties that the students may encounter and a proposition of related feedbacks from the components of the environment, and the proposition of a communication situation. This type of situation has been experimented in chemistry and in physics and it will be soon experimented with a concept of immunology (the antigen-antibody reaction). Finally an Intelligent Learning Environment will be conceived, based in particularly on the conclusions of 'naturals' experimentations with students in biology, chemistry, geology and physics.

α

  Fig 1: measurement of a cranium's facial angle

Acknowledgements:

We would like to thank the teachers who work with us: Daniel Devallois (lycée presentation de Marie) and Réjane Monod-Ansaldi (lycée Claude Bernard). These studies were conduct within the CoPEX project, supported by the French ministry of education.


Simon Bouget

Yérom-David Bromberg

Hugues Mercier

Etienne Rivière

Franc ¸ois Taiani

Mind the Gap: Autonomous Detection of Partitioned MANET Systems using Opportunistic Aggregation

Mobile Ad-hoc Networks (MANETs) use limitedrange wireless communications and are thus exposed to partitions when nodes fail or move out of reach of each other. Detecting partitions in MANETs is unfortunately a nontrivial task due to their inherently decentralized design and limited resources such as power or bandwidth. In this paper, we propose a novel and fully decentralized approach to detect partitions (and other large membership changes) in MANETs that is both accurate and resource efficient. We monitor the current composition of a MANET using the lightweight aggregation of compact membership-encoding filters. Changes in these filters allow us to infer the likelihood of a partition with a quantifiable level of confidence. We first present an analysis of our approach, and show that it can detect close to 100% of partitions under realistic settings, while at the same time being robust to false positives due to churn or dropped packets. We perform a series of simulations that compare against alternative approaches and confirm our theoretical results, including above 90% accurate detection even under a 40% message loss rate.

I. INTRODUCTION

Mobile Ad-hoc Networks (MANETs) do not rely on any fixed network infrastructure, but instead exploit mesh networking protocols [START_REF] Ruiz | Survey on broadcast algorithms for mobile ad hoc networks[END_REF], [START_REF] Akkaya | A survey on routing protocols for wireless sensor networks[END_REF] to overcome the mobility of nodes and the imperfect and unpredictable nature of wireless communications. Because they operate in open, dynamic and sometimes hostile environments, MANETs can easily become partitioned, for instance because some key nodes have failed, because nodes have moved out of reach from one another, or because environmental conditions hinder wireless communications. When this occurs, the network becomes disconnected, greatly hampering its overall operation.

A partition can be mitigated using different techniques. For instance, the transmission range of the wireless nodes may be increased; some of the nodes might fall back on an alternative wireless technology (e.g. a broadband cellular network) [START_REF] Grace | Experiences with open overlays: A middleware approach to network heterogeneity[END_REF]; or the system might leverage additional resources such as a supporting Flying Ad-Hoc Network (FANET) [START_REF] Bekmezci | Flying ad-hoc networks (FANETs): A survey[END_REF], [START_REF] Han | Optimization of MANET connectivity via smart deployment/movement of unmanned air vehicles[END_REF] to extend the routing coverage [START_REF] Blair | Holons: Towards a systematic approach to composing systems of systems[END_REF].

Before any explicit mitigating action can be taken, however, the partition must first be detected. Detecting a partition in a MANET is unfortunately a challenging task: MANETs typically lack any central element, forcing each node to build its own perception of the network's current state. This decentralized monitoring must also remain extremely lightweight in order to meet the memory, CPU, and energy constraints of mobile nodes.

Previous proposals to detect partitions in MANETs have either assumed extended node capabilities [START_REF] Milic | Prediction of partitioning in location-aware mobile ad hoc networks[END_REF], [START_REF] Hauspie | Partition detection in mobile adhoc networks using multiple disjoint paths set[END_REF] (such as GPS sensors or accelerators), thus limiting their applicability to high-end deployments, or have attempted to construct explicit membership and path information [START_REF] Conan | Failure, disconnection and partition detection in mobile environment[END_REF]- [START_REF] Ritter | A partition detection system for mobile ad-hoc networks[END_REF]. As MANETs reach several hundreds of nodes, gathering explicit node lists is increasingly problematic: explicit representations incur important communication costs and lead to a rapid depletion of energy resources.

In this work, we tackle partition detection in MANETs by coupling a probabilistic compact representation of a network's composition with a periodic and opportunistic aggregation procedure inspired by gossip protocols [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF], [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF] and designed to piggyback on existing communications required by routing protocols. These two primitives in tandem allow us to arbitrate the inherent tradeoffs arising between speed, accuracy, and cost of the detection. They offer an adaptable range of guarantees tailored to each system's requirements in a lightweight, decentralized and accurate fashion. We instantiate them so that partitions can either be self-detected by a MANET by identifying temporal discrepancies, or detected by a second external network by monitoring spatial discrepancies. The choice between these two use cases depends on whether mitigating measures should be triggered by the partitioned network (such as switching to an alternative wireless technology [START_REF] Grace | Experiences with open overlays: A middleware approach to network heterogeneity[END_REF]), or by some external system (such as offering bridging capabilities by a FANET [START_REF] Bekmezci | Flying ad-hoc networks (FANETs): A survey[END_REF], [START_REF] Blair | Holons: Towards a systematic approach to composing systems of systems[END_REF]).

More precisely, we make the following contributions:

1) We use random bit signatures to concisely encode a MANET's set of nodes, or membership list into a filter, and show that this compact and stochastic representation can detect large connectivity changes. 2) We present two partition-detection algorithms that combine our probabilistic representation with a periodic aggregation procedure. Our algorithms provide an internal self-detection mechanism (in which a MANET A detects it has partitioned), and an external third-party detection service (in which a system B detects that a MANET A has partitioned). 3) We develop a theoretical analysis to tune implementation parameters based on the environment in which the network is deployed. We show that as long as the filters are not completely saturated with '1's , we detect close to 100% of partitions and almost none of the non-partition events. 4) We demonstrate the practical relevance of our approach through an extensive series of simulations. As an example, we show that even with 40% message loss, performances are still satisfying with an error rate below 10%. In the following, we present our approach in Section II, analyze it formally in Section III, and present an in depth experimental evaluation in Section IV. We discuss related work in Section V and conclude in Section VI.

II. APPROACH

We start with a general overview of our approach, and then detail the two variants of our partition detection mechanisms.

A. Overview

A simple approach to partition detection consists in maintaining and propagating a list of a system's connected nodes [START_REF] Conan | Failure, disconnection and partition detection in mobile environment[END_REF]- [START_REF] Ritter | A partition detection system for mobile ad-hoc networks[END_REF]. If two lists for the same system are sufficiently different, the system is likely partitioned. Unfortunately, this direct approach is, in most cases, not tractable: it incurs a high overhead in large systems, both in terms of memory usage, bandwidth consumption, and hence energy consumption, a prime limiting factor in MANETs.

To overcome this difficulty, our approach (which we term MtG for Mind the Gap, as partitions create gaps in connectivity) replaces the explicit representation of reachable nodes by a potentially inaccurate but compact summary of a system's connectivity. More precisely, each node of a system repeatedly constructs a summary of the currently reachable network, and nodes infer a partition when two summaries about the same system differ markedly. In practice, this will detect any large change in system's connectivity, not only partitions, but nonpartition events often need to be addressed in the same way and can be easily filtered out with minor changes we won't detail here. 1) Constructing summaries: To be practical and scalable, summaries should ideally be accurate, compact, and robust to network delays and interference. Our approach uses fixed-size bit arrays, termed filters, which we construct over recurring periods of times, called epochs, using a wireless gossip aggregation procedure. This aggregation procedure is designed to leverage existing periodic communications in the MANET system, such as the periodic beacon messages employed by many MANET routing protocols [START_REF] Akkaya | A survey on routing protocols for wireless sensor networks[END_REF]. The size of the filters is fixed in advance and uniform in the system, but only requires a rough estimate of the network size (see Section III).

Figure 1 illustrates this construction in a small network of nine nodes. Upon initialization, each node is assigned an initial bit array (the node's signature) of the size of the summaries to be constructed. This initial filter contains only unset bits except for one of them. The set bit is selected uniformly at random when a node is configured. 1When an epoch starts, nodes initialize their local filter with their signature (Label in Fig. 1, here shown for nodes A, B, C). They then broadcast their current filter (Label ), and aggregate the filters received from other nodes with OR operations on each bit. This procedure is repeated over multiple asynchronous rounds during an entire epoch (Label ).

Eventually, provided the system is connected and the epoch is long enough, each node converges to a summary of the currently reachable network [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF], [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF]. This summary contains the bit-signatures of all participants the local node was able to hear from (Label , for clarity the figure only shows the signatures of nodes A, B, C). In the following we often use the words filter and summary interchangeably, privileging summary when denoting the state of a filter at the end of an epoch.

2) Detecting partitions: The system summaries constructed by individual nodes can be exploited in two ways: (i) Self-Detection to detect partitions from within a partitioned system, and (ii) Assisted-Detection to detect the partition of a monitored system from an external monitoring system.

Self-detection is illustrated in Figure 2. Suppose that a partition occurs just after the construction of the summaries of Figure 1 when Epoch e ends (Label ). The summaries constructed by each node during Epoch e+1 will therefore only encompass signatures from its connected subnetwork (Label ). The summary obtained by Node C for Epoch e + 1 will not contain the signatures of A or B. This summary will thus differ sufficiently from that of Epoch e, allowing C to detect a partition (Label ).

Assisted-detection works along the same lines but involves an external monitoring system, and uses discrepancies in space rather than in time. Both types of detection are presented more formally in Sections II-B and II-C.

3) Parameter tradeoffs: So far, we have assumed that the construction of summaries was done perfectly. In practice, two summaries of the same system might diverge for other reasons than a partition. First, individual nodes might crash, leading to small changes in individual summaries. Second, filters might propagate imperfectly over an epoch due to network failures or Algorithm 1: MtG/Self-detect: Filter aggregation (at p i ) Another cause of inaccuracy stems from the compact nature of node signatures and summaries. Signatures can collide, and a partition might only cause small changes in a network's summaries. Consider, in the worst case, a large network using small filters. It is highly probable that all the bits of the summaries will be set to one before and after a large partition. Using a very large filter solves this problem but is a waste of precious resources. The size of system summaries, the length of an epoch, the frequency of gossiping rounds, and the threshold used to detect partitions must therefore be selected with care, depending on the size, dynamism, memory and energy constraints of the system.

B. Self-detection protocol (MtG/Self-detect)

The first way we use summaries is to allow a system to monitor its own evolution over time and detect when it becomes partitioned, an ability we have termed self-detection. The protocol implementing this behavior, called MtG/Self-detect, is described by Algorithms 1 and 2. Table I of a duration for our timers ensures we leverage that loose synchrony and that the drifts don't accumulate over multiple epochs. The code of the joining mechanism is not shown in the presented pseudo-code for the sake of clarity.

We assume that nodes know the identifier of the system they belong to, and that they can ignore messages sent by nodes belonging to other systems, if necessary. When a node actively participates in an epoch, it periodically broadcasts its current filter (lines 1-2 of Alg. 1), typically by leveraging existing periodic beaconing messages used by the routing protocol. When a node receives a neighbor's filter for the system it belongs to, and for the epoch it currently participates in (lines 3-4), it incorporates the received filter into its own filter by using a logical OR over the two bit fields (line 5). Otherwise, the message is simply dropped. This simple process implements a push-based aggregation [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF], and is robust and efficient.

At the end of an epoch, each node stores its final filter as the system summary for this epoch (line 7 of Alg. 2) compares it to prior summaries by calculating the Hamming distance between the two filters (hdist(-, -), line 9), i.e. counting the number of bits in which they differ. The current filter is then reset (line 11) and a new aggregation epoch starts (lines 12-13).

If there is "enough" difference between filters (using the threshold γ at line 9), this is a sign of significant change in the MANET over the corresponding epoch and a partition is detected (with the PARTITION event at line 10). The main difficulty, and an important contribution of this work, is to determine the proper threshold parameter γ to detect actual partitions while avoiding false positives, a point we revisit in detail in our analysis of Section III.

C. Assisted-detection protocol (MtG/Assisted)

As an alternative to self-detection, summaries can also be used to provide assisted-detection, i.e. the detection by a monitoring MANET that the MANET being monitored has partitioned. We assume the monitoring system is strongly connected and does not suffer from the same issues as the monitored system. The corresponding protocol (termed MtG/Assisted) is detailed in Algorithms 3 and 4. The main idea consists in propagating within the monitoring MANET summaries constructed by nodes of the monitored system. This propagation makes it then possible to detect whether two nodes from the monitoring system have observed a large enough discrepancy in two summaries of the same monitored system for the same epoch, hinting at a partition. More specifically, nodes in the target system execute the same aggregation gossip as previously (cf. Alg. 1). At the end of an epoch, however, the nodes do not store the filter but instead broadcasts them with a SUMMARY message (line 15 in Alg. 3).

When a node from the monitoring system receives a SUMMARY message (line 19 in Alg. 4), it stores it (line 21). The monitoring system then executes its own gossip aggregation of the target system's signatures with SUMMARY SET messages (lines 23-28 in Alg. 4). When a node receives a SUMMARY SET message, it stores the new summaries (line 27) and then checks if it has two different enough summaries from the same epoch and for the same target system, indicating a potential partition (procedure CHECKPARTITION(), lines 29-33). Note that a more optimized and energy-aware variant could reduce the number of calls to CHECKPARTITION() and make sure that any partition event is raised only once.

III. ANALYSIS

To understand the behavior of summaries and therefore the MtG protocols, we first discuss how the threshold parameter γ should be set assuming ideal network conditions (Sec. III-B), before proposing a more in-depth analysis when considering an imperfect and hostile but realistic network (Sec. III-C).

A. Overview: The role of γ

Both MtG/Self-detect and MtG/Assisted use the parameter γ to decide when the hamming distance hdist(-, -) between two summaries is large enough to denote a partition with high probability. The difference between the two variants stems from how the two compared summaries are obtained. In MtG/Self-detect, the two summaries sum i [e] and sum i [e + 1] are computed by the same node n i over two consecutive epochs e and e + 1 (line 9 in Algorithm 2), whereas in MtG/Assisted, sum i [e] and sum j [e] are computed by two different nodes n i and n j over the same epoch e.

In both cases the threshold parameter γ captures the tradeoff between false positives and false negatives: a low γ will cause both protocols to react to small changes in summaries, decreasing the risk of missing actual partitions (false negatives), but increasing the risk of raising an alert when no partition has occurred (false positives). A high γ has a reverse effect.

The most challenging situation is when the two summaries sum 1 and sum 2 represent two sets of nodes S 1 and S 2 that have similar sizes. They are more likely to have bits in common, and hence a low Hamming distance. This situation is more likely to occur with the MtG/Assisted protocol, when the same network S becomes split into two equal parts S 1 and S 2 .

To investigate this case, we will consider the following scenario. A monitoring node n mon receives two summaries sum 1 and sum 2 for the same system i and same epoch e (i.e., (i, e, s 1 , sum 1 ) and (i, e, s 1 , sum 2 ) both belong to P at line 30 of Algorithm 4). Let us note S 1 the connected (sub)network from which sum 1 originated, and S 2 the one of sum 2 . n mon must decide based on the hamming distance between sum 1 and sum 2 whether they come from the same connected network 1 = S 2 = S, no partition), or if they originate from two disconnected subnetworks (S 1 = S 2 , there is a partition).

B. Operating in paradise: ideal network conditions

We first consider the case where network conditions are ideal, i.e., there is no churn, no noise, and no packet loss. If the duration of an epoch ∆ epoch is sufficiently long, all the summaries produced with a connected (sub)network are identical at the end of each epoch.

In this scenario, S 1 = S 2 implies that hdist(sum 1 , sum 2 ) = 0, and therefore, hdist(sum 1 , sum 2 ) > 0 implies S 1 = S 2 . In other words, under these ideal conditions, choosing γ = 0 in Algorithm 4 guarantees all PARTITION events raised by n mon correspond to an actual partition, i.e., there cannot be any false positive. The same reasoning applies to Algorithm 2.

hdist(sum 1 , sum 2 ) = 0 does not imply, however, that S 1 = S 2 . sum 1 and sum 2 may still originate from different subnetworks due to collisions in the random choice of the original node signatures, yielding a false negative (an undetected partition). We now evaluate the likelihood of such a scenario. Let B (sum) be the number of nonzero bits in a summary of size f when inserting n node signatures into it. Because the node signature are uniformly random, the expected number of bits set to '1' in the summary is

E B (sum) = f • 1 -1 -1 f n
. More precisely, it was shown in [START_REF] Barazzutti | Efficient and confidentiality-preserving content-based publish/subscribe with prefiltering[END_REF] that the probability of the same summary to contain j non-zero bits is P B (sum

) = j = ( f j )•j!•{ n j } f n
, where a b stands for the Stirling numbers of the second kind [START_REF] Graham | Concrete Mathematics[END_REF]. Stirling numbers are gruesome to handle and are usually tackled asymptotically, but since in this work we are ultimately interested in efficient implementations using small summaries, we resort instead to mathematical simulations. As n and f increase, the distribution of B (sum) is sharply concentrated around its expected value [START_REF] Motwani | Randomized algorithms[END_REF]. At first sight, this is disappointing: for instance with f = 32 and n = 64 the expected number of '1's in the summaries is 27.8. However, Figure 3 shows the distribution of the Hamming distance of the summaries for two disjoint subnetworks S 1 and S 2 of 64 nodes each (corresponding to a global network S = S 1 ∪ S 2 of 128 nodes partitioned in two equal halves) with summaries sum 1 and sum 2 of size 32 bits. In this example, the probability that the Hamming distance between sum 1 and sum 2 is zero (and hence the rate of false positives) is approximately 10 -5 .

Two partitions of equal size is the worst possible scenario since the probability that both summaries are identical decreases quickly as the size of each subnetwork diverges. Note that in the self-detection variant, there is no central authority that can compare the summaries from both partitions; if the size of the partitions greatly differs, the small subnetwork will easily detect the partition and trigger mitigating measures. This is further discussed in the next section.

Figure 4 shows the maximum network size allowing a probability of false negative of 10 -5 when partitioned into two partitions of equal size for different summary sizes (again this is the worst possible scenario). Under perfect network and convergence assumptions, MtG can thus easily handle partition detection with high accuracy in networks of 128 nodes or less with 32-bit summaries, in networks of 800 nodes or less with 128-bit summaries, and in networks of 4500 nodes or less with 512-bit summaries. The sub-linear trend is due to summaries being wrongly identical when they are entirely filled with '1's. This corresponds to the coupon collector problem, and it takes n.log(n) random node signatures to fill a n-bit filter.

C. Operating in reality: dynamism and imperfect aggregation

In a real deployment, of course, summaries may diverge within the same system connected S due to churn, node crashes, and imperfect aggregation caused by network contention, node mobility or a hostile environment. In other words, we might have hdist(sum 1 , sum 2 ) = 0, even though there is no partition. One should therefore set the threshold γ to a strictly positive value to account for these causes of divergence, thus reducing the chances that MtG/Self-detect and MtG/Assisted might erroneously detect partitions that do not exist. For our analysis, we model the effect of the above imperfections through a generic "churn" parameter c that seeks to capture the differences between sum 1 and sum 2 caused by isolated node failures and imperfect communication. More precisely, we will assume that sum 1 and sum 2 contain the nodes signatures of two sets S 1 and S 2 such that

|S 1 \ S 2 | = |S 2 \ S 1 | = c.
In the case of MtG/Assisted, this correspond to the situation in which c nodes of the global network S did not make it into sum 1 , and c other and distinct nodes did not make it into sum 2 . In the case of MtG/Self-detect, this correspond to a scenario in which c nodes present in epoch e fail in epoch e + 1, and conversely c nodes that were failed in epoch e appear in epoch e + 1. This simple model completely ignores topology because all nodes in a connected subset all have the same filter, so it doesn't matter where the churn happens.

Figure 5 shows the distribution of the Hamming distance of two summaries of size f = 32 used by a connected system of |S| = 64 nodes. Each gray curve corresponds to a churn level c varying from 1 to 10. For comparison, the blue points correspond to the situation in which S becomes partitioned into two equal halves of 32 nodes. The gray and blue probability mass functions are almost disjoint, thus if we set the partition threshold to γ = 7, we essentially detect 100% of the partitions and no false positives. In figure 6, we repeat the process with the same summary size but with systems of n = 128 nodes. There is a small overlap between the gray and blue curves, but by setting the partition threshold to γ = 2, we still detect 99% of the worst possible partitions and treat less than 1% of the normal events at c = 10 as partitions.

D. Discussion

It is important to note that the choice of c is arbitrary. What is "normal churn" and what is "a partition" is entirely dependent on the context and the specific circumstances of a real world network, and the value of c should be chosen by a network operator depending on their objectives. Our goal is to show that the operator of a very noisy network can set c to a high value, so MtG won't raise too many false alerts, and that our approach still works in adversarial circumstances. In other words, in a real world deployment, the value of c is context-specific, but in this analysis, we want c as high as possible. The use of c to bound the amount of change under which our protocol should not detect any partition means that if a system S looses c nodes that become disconnected from the rest of S, but do not crash, S will no raise any alert when using MtG/Self-detect. However, in this case, the c nodes are still active and, from their point of view, a drastic partition just occurred. They will therefore produce an alert, and allow for mitigation actions.

Finally, we also emphasize that these results are conservative for two reasons. First, c = 10 and n = 64 corresponds to a churn rate of 15% per epoch. The operator of a network in such an environment might want to trigger mitigating measures even in the absence of a partition. Second, it assumes that the network is partitioned in two pieces of equal size. As mentioned earlier, this is the most pessimistic scenario (i.e., it will systematically yield the lowest Hamming distances between summaries for the different subsystems). It is thus clear that like for many applications of bit fields as a compact representation, such as Bloom filters [START_REF] Broder | Network applications of bloom filters: A survey[END_REF], the efficiency of our approach is uniquely determined by the size of the filters/summaries and the number of nodes in the network: with very small filters and very large networks, the filters, even once partitioned equally, will be filled with '1's. As a result, and similarly to the situation where we consider ideal network and convergence assumptions, under realistic settings MtG can still reliably detect partitions in networks of 128 nodes or less with 32-bit filters, in networks of size 800 nodes or less with 128-bit filters.

IV. EVALUATION

We evaluate our proposal along three dimensions. We first investigate whether filters can effectively distinguish between joined and partitioned networks (Section IV-B). We then assess the ability of MtG to detect partitions and compare them to two alternative approaches (Section IV-C). Finally, we explore the parameters space in Section IV-D.

Unless stated otherwise, we configure MtG to use 32-bit filters, asynchronous rounds of 0.3 second, and epochs of 16 rounds (i.e., roughly 5 seconds per epoch). Naturally, our results apply to lower communication frequencies, provided that the epoch time be adjusted accordingly to comprise the same number of rounds. Typically, the communication frequency is set by the beaconing frequency of the routing protocol, and aggregation messages piggyback on these beacon messages. During each round, each node can push its current filter to all neighbors in its communication range, which we set to be 100m. Nodes are positioned over a 400m×400m area. The exact number of nodes, their position, and their mobility depend on the experiment, as we detail below.

We use the Omnet++/Inet framework [START_REF] Varga | An overview of the OMNeT++ simulation environment[END_REF] for our simulations. Presented results are averages over 10 runs using different random seeds for nodes signatures and positions. We do not show error bars as they prove to be negligible. We use the following metrics:

• The normalized maximum pair-wise internal distance (internal distance for short) measures the maximum Hamming distance between the filters being maintained by two nodes of the same monitored system S, normalized by the size of the filters f (32 in our experiments). When S is connected, this distance should converge to zero at the end of each epoch. Formally, we have:

internal d(S) = max (pi,pj )∈S 2
hdist(filter i ,filter j ) f .

• The normalized minimum pair-wise inter-partition distance (external distance for short) measures the minimum Hamming distance between the filters of two partitions S 1 and S 2 of a system, normalized by the size of the filters. When S 1 and S 2 are disconnected, this distance should remain above the γ threshold, even in a converged state, in order to distinguish a partition from a connected configuration. Formally we have:

external d(S 1 , S 2 ) = min (pi,pj )∈ S1×S2 hdist(filter i ,filter j ) f .
• The error rate is the number of nodes belonging to a partitioned system that do not detect the partition (false negatives) summed with the number of nodes belonging to a fully connected system that raise a partition alert (false positives), over the total number of nodes. • The per-node per-round bandwidth (bandwidth for short) represents the amount of information sent by each node per round, measured in bits.

B. Effective representation

We set up a system S of 120 nodes divided into two groups S 1 and S 2 of 60 nodes each. S 1 and S 2 are initially distributed over the same 400m×400m area, but drift apart in opposite direction at 25 m/s, S 1 heading North and S 2 South. S 1 and S 2 thus become unable to reach each other at around 15 seconds into the experiment (end of the 3rd epoch). We monitor over time the internal distance of S and the external distance between S 1 and S 2 . Figure 7 shows that before the partition (0-15 seconds), the internal distance goes down to 0 very rapidly, in They converge when the system is connected, and they are clearly distinct when there is a partition. less than 2 seconds (6 rounds). Once the partition occurs (15-24 seconds), the external distance between the two partitions is always strictly positive, and converges quickly to a value noticeably above 0.

These two results combined demonstrate that filters are efficient to represent a system membership, in a quick, accurate, and compact manner. Even after only a few rounds, all nodes in a system agree on the same filter, while disconnected subsystems have very distinct filters, all the while using 32-bit filters for systems containing over a hundred nodes.

C. Partition detection

In this second set of experiments we compare the filters used by MtG with those of two baseline approaches:

• The graph-coloring baseline: Each node randomly choses a 16-bit integer, a color, and starts spreading it. When it receives a color announce from another node, it keeps the color with the biggest integer value and gossips this value thereafter. If a network is not partitioned, all nodes will eventually agree on the same color; if there is a partition, each subsystem will agree on a different color. Hence, the color can serve as a simple way to distinguish subsystems. Similarly to MtG, it uses a fixedsize information per node and for any gossip exchange. • The full-list baseline: Each node maintains an exhaustive list of all node identifiers it has encountered, and gossips it around. Nodes merge incoming lists with their local list using an union operator. At the end of an epoch, all connected nodes agree on the same list, which is the membership list of their subsystem. If two different lists are observed, it is a sign of a partition. Unlike MtG and the graph-coloring baseline, the space cost of this method is linear in the number of nodes in the system. We repeat the setup of the previous subsection: two 60-node groups moving away from each other. We run four experiments in which nodes execute either one of the variants of MtG or one of the two other protocols.

• In the first experiment, all 120 nodes execute MtG/Selfdetect, the self-detection version of our approach. • In the second one, we add a third group of nodes from an independent system in the middle, serving as the monitoring group, and we run MtG/Assisted, the third-party version of our protocol. The third group is constituted of 20 fixed nodes, set up to ensure the coverage of the whole area of the experiment. • In a third experiment, we used the graph-coloring baseline instead of our proposed filters to represent the network membership, in self-detect mode. • Finally in the fourth experiment, we used the full-list baseline instead of filters, in self-detect mode. The results are summarized in Table II. The bandwidth consumption assumes the following: filters are 32 bits long, node identifiers use 32 bits (size of an IPV4 address), and colors are 16-bit integers.

In both modes, our protocols accurately detect the partition when it happens, with modest bandwidth consumption, comparable to the graph-coloring approach. In contrast, the graph-coloring approach only detects the partition for half of the nodes. Indeed, the nodes in the group of the "winning" color do not see any change when the partition happens.

The extensive-list approach detects partitions accurately, but its bandwidth consumption is orders of magnitude bigger than with our approach, even with a system featuring as little as 120 nodes. Moreover, this bandwidth usage varies considerably over the execution of the protocol, with a low bandwidth usage at the beginning of an epoch (using small lists) and an unbounded usage as lists are aggregated to the full membership, e.g. up to 1,920 bits for a 60-node group, or 3,840 for a 120-node group. This bandwidth usage is orders of magnitude higher than with the filters, and increases linearly with the network size. Furthermore, it is in the expected common case when the lists are converged and that there is no partition that the usage is the highest, which is the opposite of the desired behavior.

D. Pushing the limits

In Section III, we mentioned that a network split perfectly in half was the worst case for MtG, because the summaries of each half are the closest to each other. This is clearly true in MtG/Assisted, however, in MtG/Self-detect a node compare its own summary to its summary from the previous epoch. When the network does not split exactly in half but instead in two subnetworks, one large and one small, the small group will converge to a significantly different summary. It will therefore detect the partition easily. The large subset on the other hand will observe a limited change between the summaries, and might miss a partition detection. To analyze this effect, we set up the same experiment as in subsection IV-B except that instead of 60 nodes in S 1 and S 2 each, we use varying proportions for the group sizes, from 50%-50% (S 1 = S 2 = 60 nodes) to 5%-95% (S 1 = 6 nodes, S 2 = 114 nodes).

The results are given by Table III.

As expected, the small group S 1 always detects the partition. Even with only 20% of nodes leaving (24 nodes in S 1 ), nodes in the larger group S 2 still detect the partition as well. It is only when S 1 contains 15% or less of the network (18 nodes or less) that S 2 begins to miss the partition. It is interesting to look more precisely at the distance between the signatures of each group before and after the partition. This is shown by Figure 8. The distances for both groups converge toward the same value when the original group is split exactly in half. This confirms that the even split is the worst scenario, even in MtG/Self-detect. In other cases, the detection and the triggering of mitigation measures is systematically easier for the smaller group resulting from the split.

We now explore specific adversarial conditions that MtG may encounter, and suggest countermeasures. First, the length of the epochs is a tradeoff between the quality of convergence between filters and the freshness of the information they contain. While a long epoch provides better convergence guarantees, shorter epochs avoid keeping information about crashed or unreachable nodes. The length of the epochs needs to be adapted to the size of the considered systems. To illustrate this, we set up an experiment with systems of increasing sizes. We keep the density of nodes constant between all experiments, simply distributing a larger number of nodes over a larger area, resulting in systems of increasing diameters, from 4 to 16 hops. The length of rounds and epochs is constant between experiments. Figure 9 shows the evolution of the internal distance of these systems over time. As the diameter increases, the convergence is slower. Past a certain diameter, filters do not have enough time to converge anymore, as the distance does not reach zero.

Given the number and types of devices deployed in a MANET and the physical area over which they are deployed, a network operator can get a rough estimation of its system's diameter. Based on our experiments, we recommend to set the length of an epoch (in rounds) to twice the expected maximal diameter of the system (in hops).

Finally, we test the resilience of MtG to bad communication conditions and message losses. We set up a system of 120 nodes distributed in two groups of 60 nodes each and make them drift apart under the scenario previously described. In order to stress the system, we reduce the length of the epoch to only 6 rounds, and we tune the drifting speed so that a 10 shows the fraction of nodes that raise an alert during each epoch. With 20% of lost messages, the detection rate is not affected. With 40% message loss, barely 10% of the nodes confuse the effect of bad communication conditions with a real partition in epoch 2. It is however only when reaching a tremendous level of 60% message loss that a noticeable fraction of MtG nodes raise a false alert before the partition actually happens. We argue that under such harsh conditions, a system operator has more pressing issues than partitions, and will want to trigger available counter-measures just as if a real partition was happening. This makes us confident that MtG is resilient to message loss rates under all the circumstances where its detection capabilities can prove useful.

V. RELATED WORK

Partitions are known to be problematic for MANETs and Wireless Sensor Networks, and have therefore been investigated in the past. To the best of our knowledge, however, none of these earlier approaches considered the use of compact filters as MtG does. In the following we review related work on partition detection, as well as on related problems, such as cut detection, partition prediction, and partition recovery.

a) Membership and partition detection: The work of Arantes et al. [START_REF] Conan | Failure, disconnection and partition detection in mobile environment[END_REF], [START_REF] Arantes | Partition participant detector with dynamic paths in mobile networks[END_REF] formalizes the notions of partition detector and partition participants detector in a manner similar to the classical formalization of failure detectors [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. The two algorithms they propose accumulate information about broadcast propagation paths over epochs in order to construct local reachability information. When the set of nodes in the system is known beforehand [START_REF] Conan | Failure, disconnection and partition detection in mobile environment[END_REF], a partition is detected when some of these nodes become unreachable (possibly because of crashes). This approach is extended to systems with an arbitrary number of unknown participants [START_REF] Arantes | Partition participant detector with dynamic paths in mobile networks[END_REF], for which the detector is able to return the set of nodes present in the local partition, provided that the local partition eventually stabilizes. The accumulation of network participants in a list is similar to the way we accumulate members in our filters. For large networks, however, such an explicit approach is likely not to scale as we show in our evaluation.

Ritter et al. [START_REF] Ritter | A partition detection system for mobile ad-hoc networks[END_REF] propose an approach to detect partitions in MANETs in which a subset of active nodes exchange beacon messages that traverse the network. The proposed heuristic tends to position active nodes at the border of the network, in order to maximize the network nodes covered by a beacon propagation path. When beacons repeatedly fail to propagate between two active nodes, a partition is suspected. In contrast to MtG, this strategy assumes that border nodes can be reliably detected, and only change slowly.

Khelil et al. [START_REF] Khelil | Hypergossiping: A generalized broadcast strategy for mobile ad hoc networks[END_REF] present a broadcast strategy for partitionable MANETS based on hypergossiping, the selective rebroadcasting of partially broadcast messages. This strategy includes a mechanism to detect partition joins, i.e. the rejoining of the two parts of a previously disconnected network. This mechanism exploits Last Broadcast Received (LBR) lists, a list of the identifiers of the k last broadcast messages received by a node. Nodes periodically exchange this list, and conclude that they are rejoining a partitioned subnetwork when their local LBR substantially differ from that of their neighbors. Because the main goal of this approach is to maximize the delivery ratio of system-wide broadcasts, the partition join detection mechanism tends to err on the side of over-detection, with numerous wrong detection decisions in some instances [START_REF] Khelil | Evaluation of partition-aware manet protocols and applications with ns-2[END_REF].

b) Cut detection: Cut detection is a problem related, but distinct from partition detection in MANETs, and focuses on mostly static Wireless Sensor Networks, in which sensors forward their readings to dedicated sink nodes. A cut occurs when some nodes become disconnected from the sink.

The work of Barooah et al. [START_REF] Barooah | Cut detection in wireless sensor networks[END_REF] allows each sensor node to detect when it becomes disconnected from the sink, and whether other sensor nodes have become disconnected. Won et al. [START_REF] Won | Towards robustness and energy efficiency of cut detection in wireless sensor networks[END_REF] target only the second problem and adds consideration about energy and robustness to malicious nodes. Because of the specific topology of sink-based sensor networks, these approaches are however not applicable here. c) Partition prediction: Some works try to predict partitions before they happen, but require more powerful primitives than MtG. Some use GPS information (regarding both location and speed) to build a mobility model of the network and predict when nodes are likely to get out of range [START_REF] Milic | Prediction of partitioning in location-aware mobile ad hoc networks[END_REF]. Other proposals [START_REF] Hauspie | Partition detection in mobile adhoc networks using multiple disjoint paths set[END_REF] assume the existence of a distributed algorithm that returns the set of disjoint paths between two nodes, and predict partitions based on the number of paths and their length. By comparison, our solution makes no assumption regarding the higher level capabilities of a network, and only assumes a one-hop broadcast primitive. d) Address allocation: A few papers focus on allocating addresses to nodes, including after a network partition. The work of Singh et al. [START_REF] Singh | Address allocation for MANET merge and partition using cluster based routing[END_REF] only deals with graceful partitions (i.e. nodes detect and announce when they will leave/merge with the network), and propose a protocol to elect a new cluster head when a partition looses access to the initial head, but does not consider the kind of abrupt partitions we deal with. The solution of Zhou et al. [START_REF] Zhou | Prophet address allocation for large scale manets[END_REF] is designed to address this problem even in case of partitions, and so does not consider the problem of detecting them.

e) Partition recovery: Some works look at the problem of partition recovery, once a partition has been detected. For example, Han, Swindlehurst and Liu [START_REF] Han | Optimization of MANET connectivity via smart deployment/movement of unmanned air vehicles[END_REF] consider the optimal placement of Unmanned Aerial Vehicles (UAV) to overcome the disconnection of ground-based MANETs. Their approach is based on heuristics that seek to maximize different metrics of connectivity, but assumes a central location where all relevant information about MANETs nodes and UAV positions can be aggregated and processed, an assumption we do not make.

VI. CONCLUSION & FUTURE WORK

We presented in this article MtG, a lightweight method to detect partitions in a MANET, either by the nodes forming the MANET themselves or by an external supporting system. Our analysis and evaluation show the ability of our approach to detect such partitions even under aggregation imperfection and imperfect networking conditions. For our future work, we are interested in developing a more formal method to derive the partition threshold γ based on the filter and network sizes, or at least to provide these thresholds for a larger number of parameters. In particular, as mentioned in Section III we do not leverage the number of bits set to '1' in our summaries. When a system is partitioned, two general cases can occur. If both partitions have the same size, the summaries from one epoch to the next will very likely contain significantly less bits set to '1'. If one partition is small and the other is large, the large partition might view its evolution as a normal churn event, but the small partition will see an even higher reduction in its number of summary bits set to '1' between consecutive epochs. Considering the number of bits set to '1' may allow us to tackle higher noise levels, as well as larger systems with good accuracy, without increasing the filter size. It would also avoid triggering an alert when a large number of nodes join the network or when two partitions reconnect, since this events increase the number of '1' in the filters, but are still detected with our current approach as large changes in membership.

Figure 1 .

 1 Figure 1. Starting from their individual signature, nodes progressively aggregate other nodes' signatures in their local filter. At an epoch's end, they converge to a summary representing the composition of the subnetwork they were able to hear from (shown only for the nodes A, B, C for simplicity).

5 Figure 2 .

 52 Figure 2. When a partition occurs, the summaries between two successive epochs change suddenly, as the signatures of unreachable nodes are no longer aggregated in the converged summary. This sudden change can be detected, and a partition detection event raised.

Figure 3 .Figure 4 .

 34 Figure 3. Distribution of the Hamming distance of two summaries of size f = 32 with n = 64 inserted signatures coming from independent subnetworks.

Figure 5 .

 5 Figure 5. Distribution of the Hamming distance of two summaries of size f = 32 with n = 64 inserted signatures and churn parameter c ∈ {1, 2, 3, . . . , 10} (gray curves). The blue points correspond to two partitioned systems of 32 nodes. Probability mass functions calculated with 10 5 randomized experiments.

Figure 6 .

 6 Figure 6. Distribution of the Hamming distance of two summaries of size f = 32 with n = 128 inserted signatures and churn parameter c ∈ {1, 2, 3, . . . , 10} (gray curves). The blue points correspond to two partitioned systems of 64 nodes. The probability mass functions are calculated with 10 5 randomized experiments.

Figure 7 .

 7 Figure 7. Filters are an effective representation of a network membership.They converge when the system is connected, and they are clearly distinct when there is a partition.

  Size of the bit arrays hdist(s 1 , s 2 )Hamming distance between the bit arrays s 1 and s 2 . PARTITION(i, e)Event representing a partition in system i at epoch e.

		Table I
		NOTATIONS AND VARIABLES
	Constants and functions
	∆ epoch	Duration of an epoch.
	γ	Threshold used to detect a partition.
	f
	Variables maintained by a node p i in a monitored system
	sysID i	The ID of the system the node p i belongs to.
	clock i	p i 's local clock.
	epoch i	p i 's current epoch number.
	node sig i	The one-bit signature of p i .
	filter i	The system summary being constructed by p i
	sum i []	An array of the system summaries observed by p i at
		the end of each past epoch, indexed by epoch numbers
		(used for self-detection)
	Variables maintained by a node p i in a monitoring system
	sumSet i	The set of summaries propagated to the monitoring
		node. (id, ep, s) ∈ sumSet i means that a node from
		system id generated a system summary s at the end
		of epoch ep, and that p i is aware of this summary.

  BROADCAST AGG sysID i , epoch i , filter i 3 on receive AGG sysID, epoch, filter do 4 if epoch i = epoch and sysID i = sysID then 5 filter i ← OR(filter i , filter )

	1 every X seconds do
	2
	Algorithm 2: MtG/Self-detect: Change of epoch (at p i )
	6 on expiration EPOCH TIMER do
	7	sum i [epoch i ] ← filter i
	8	for t ∈ 0..epoch i -1 do
	9	if hdist(sum i [epoch i ], sum i [t]) > γ then
	10	raise PARTITION(sysID i , epoch i )
	11	filter i ← node sig i	Resetting p i 's filter
	12	epoch i ← clocki ∆epoch	New epoch
	13	set timer EPOCH TIMER at (epoch i + 1) × ∆ epoch
	if an epoch is too short with respect to the network diameter.
	Such imperfect propagation will lead to variations in the
	summaries constructed by a same node over successive epochs
	(used for self-detection), and by different nodes over the same
	epoch (used for assisted-detection).

  provides a summary of the variables and notations used.When a node p i starts participating to the system, it does not take part in the current epoch(its epoch i variable is set to ⊥), and waits for the next epoch to start at time clocki ∆epoch + 1 × ∆ epoch before joining the protocol, where ∆ epoch is the duration of an epoch, and clock i represents p i 's local clock. We assume that clocks are loosely synchronized between all nodes, with a drift remaining small compared to the duration of an epoch ∆ epoch , so that all nodes in the MANET work for the same epoch during a large fraction of ∆ epoch . Using a date instead Algorithm 3: MtG/Assisted: Change of epoch at a node p i belonging to a monitored system 14 on expiration EPOCH TIMER do 15 BROADCAST SUMMARY sysID i , epoch i , filter i 16 filter i ← node sig i resetting p i 's filter

17 epoch i ← clocki ∆epoch New epoch 18 set timer EPOCH TIMER at (epoch i + 1) × ∆ epoch

Algorithm 4 :

 4 MtG/Assisted: Signature aggregation at a node p i belonging to a monitoring system 19 on receive SUMMARY sysID, epoch, filter do 20 if sysID i = sysID then 21 sumSet i ← sumSet i ∪ (sysID, epoch, filter ) , s 2 ) | hdist(s 1 , s 2 ) > γ ∧ (i, e, s 1 ), (i, e, s 2 ) ⊆ sumSet i 31 For all (i, e, s 1 , s 2 ) ∈ P do 32 sumSet i ← sumSet i \ (i, e, s 1 ), (i, e, s 2 )

	22	CHECKPARTITION()
	23 every Y seconds do
	24	BROADCAST SUMMARY SET sysID i , sumSet i
	25 on receive SUMMARY SET sysID, sumSet do
	26	if sysID i = sysID then
	27	sumSet i ← sumSet i ∪ sumSet
	28	CHECKPARTITION()
	29 procedure CHECKPARTITION() is
	30	P ←	(i, e, s 1

33

raise PARTITION(i, e)

Table II PARTITION

 II DETECTION PERFORMANCE.

			Bandwidth
	Approach	Error rate	(bits sent/round/node)
			average	max
	graph-coloring	50%	16	16
	full-list	0%	1995	3840
	MtG (self-detect)	0%	32	32
	MtG (monitoring node)	0%	32	64
	(monitored node)		32	32

Table III DETECTION

 III IN CASE OF UNEVEN NETWORK SPLIT.

	Share of	Detection by S 1	Detection by S 2
	nodes in S 1	(small group)	(large group)
	50%
	20%
	15%
	5%

  Figure 10. Fraction of nodes detecting a partition, under varying message loss levels. A real partition happens at the end of epoch 2. MtG resists message loss until a certain level where it can start to confuse the effect of message loss with partition. partition happens at the end of the second epoch. MtG should hence raise a partition alert during epoch 3.Figure

	#bits swaps after partition	1	0.2 S1 (smaller group) 0.3 S2 (larger group)	0.4	0.5	distance (normalized)	0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8	0	2 d > 4 d > 8	4	6 d > 12 d > 16	8	10	% nodes raising an alert	0% 20% 40% 60% 80% 100%	1 20% msg loss 2 40% msg loss 60% msg loss	3	4
		Fraction of nodes in the smaller group					time (s)					epoch
	Figure 8. Numbers of bits swapping in the signature	Figure 9. With fixed epoch and round durations,
	of each group after a partition (120 nodes overall,	the larger the network is, the longer it takes to
	in the 2-group scenario of Sec. IV-B)			converge. If the network is too large, the filters do
						not converge anymore, so it is important to adapt
						the length of an epoch to the size of the network.

Note we could have used a hash function on the node identifier to derive a node's signature, in effect constructing a Bloom filter with a single hash function[START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF]. Bloom filters offer additional but unneeded features, so an initial random bit is both simpler and sufficient.

ACKNOWLEDGMENT

The research leading to these results has received funding from the French Agence Nationale de la Recherche (ANR) under project PAMELA (ANR-16-CE23-0016), from CHIST-ERA under project DIONASYS, from the EU's H2020-The EU Framework Program for Research and Innovation 2014-2020 under Grants 653884 and 692178, and from the Swiss National Science Foundation (SNSF) under grant 155249.


Anne-Solene Dris

Francois Lehericey

Valerie Gouranton

Bruno Arnaldi

OpenBIM Based IVE Ontology: an ontological approach to improve interoperability for Virtual Reality Applications

Keywords: Building Information Modeling (BIM), Ontology, Virtual and Augmented Reality, Interoperability

In this paper, we propose an ontology improving the use of Building Information Modelling (BIM) models as a virtual interactive environment (IVE) generator. The result is not only the ability to create a bidirectional link between the informed 3D database and the virtual reality application, but to automatically generate object-specific functions and capabilities according to their taxonomy. We present the results based on the Risk-Hunting training application. In this context, the notions of weight, object handles and, scheduling of the construction are essential for the immersion of the future trainee and educational success.

Introduction

1.1 AECO in France, a sector highly exposed to occupational accidents

The Architecture, Engineering, Construction and Owner-operated (AECO) industry is the most accident-prone sector in France. In 2014, 145 construction sector employees (excluding temporary workers) died while working in France.

The construction industry employed 8.6% of employees and recorded 16.3% of "accidents with stop" and 26% of deaths. As for the causes of accidents, manual handling is by far the most challenged category, accounting for more than half of all work stoppages () with a rate of up to 53%. Followings are falling full on foot with 13%, falls from height with 12%, and the use of hand tools with 9%. An economic approach to the question shows that their cost, globalized with that of occupational diseases, would amount to 1.3% of the national wealth, ie the theoretical equivalent of more than ten additional holidays on the calendar. These few figures illustrate the very dangerous nature of the sector and lead to an interest in the problem of accident prevention in construction.

Training, essential lever

Various reasons can help to explain the difficulties that prevention poses in this sector of activity: risk factors are of human, technical, organizational, material and often interdependent origins. Statistics show that workers benefiting from reduced support in the company, including posted workers, foreigners, temporary workers or apprentices, are most prone to workplace accidents. As an example, mention can be made of the INRS report [START_REF]Statistiques Prvention[END_REF] which stipulates that accident victims of foreign origin (non-European) are three times more numerous in the building and civil engineering sector than in other sectors, the same is true for European foreign employees. These statistics highlight the lack of training and experience of these categories of workers, especially for foreigners, but also the lack of support for temporary workers, who change their job and work environment regularly. Even in large groups such as Vinci, which for many years has been conducting a comprehensive prevention policy with the "zero accident" plan, the difference in frequency rates between employees and temporary workers is still worrying. One of the difficulties encountered in the management of training is related to temporary workers who do not always benefit from the same level of information and knowledge related to the materials and methods of construction specific to the site on which they intervene. Recent studies demonstrate the benefits of virtual reality training [START_REF] Ho | Construction safety training via e-Learning: Learning effectiveness and user satisfaction[END_REF] compared to traditional training methods. But the costs involved are still high [START_REF] Gao | Serious games vs. traditional tools in construction safety training : a review[END_REF] in the case of virtual reality. In both cases, the training is sequenced and does not allow the real situation, each construction project is unique. However, the work environment has a considerable impact on the perception of risk and therefore on the behavior of employees . The arrival of BIM, a working process commonly used in the construction industry, makes it possible to obtain a virtual double of the act of building.

Goal

The purpose of this study is to present a virtual reality training scenario generation method that allows the trainee to be immersed in the unique configuration of the site he / she is involved in.

Related Works

Overview Several reasons [START_REF] Choudhry | Why operatives engage in unsafe work behavior: Investigating factors on construction sites[END_REF] explain the risky behaviour of the workers: the lack of knowledge of the safety rules, the lack of respect of these rules, a nonconducive environment such as high productivity targets, psychological factors, the pride of "hard leather" in male environments such as construction, lack of training, organization of the site and a sequencing of the tasks to be performed that do not take into account the needs of the workstation.

Traditional training in risk prevention / Training in virtual reality

Virtual reality provides a relevant response to the act of training to perform tasks without dangers, train many people from different locations [START_REF] Barot | V3S: A virtual environment for risk-management training based on human-activity models[END_REF] at lower costs, understand abstract concepts or absolve from the language barrier (written or oral), and put into practice.

We also note that traditional training does not allow trainees to adapt to a changing environment [START_REF] Verna | Virtual reality and tele-operation: a common framework[END_REF] so immersion into a risk hunt in virtual reality (VR) can enrich learning.

In the particular case of risk prevention, the hazard reflex is the expected result. According to the work of JB Watson, the reflex can be conditioned by the senses and participates in the acquisition of knowledge [START_REF] Beauchesne | La formation, conditionnement ou appropriation? : rflexion pour une dmarche pdagogique partir de lexprience : un exemple, la formation lanalyse des conditions de travail[END_REF] in humans. We agree with Sutherland's (1965) view that "the ultimate (virtual reality) device would be an environment in which the computer could control the existence of objects (and our interaction with them). The five senses can therefore be solicited simultaneously [START_REF]Virtual reality: concepts and technologies[END_REF], which increases the interest and commitment of the participant [START_REF] Cherrett | Making training more cognitively effective: Making videos interactive[END_REF] in his training thus improving the acquisition of knowledge. The limits of VR in relation to Real Education today are of a technical nature related to the use of a new technology: technical and professional skills of the developer, acceptability of interaction techniques by trainees not accustomed to video games, the orientation can be disrupted by the reduction of the field of vision and the movements whose latency can be problematic. We also remember that motion sickness can disrupt immersion in the interactive virtual environment (IVE).

Generate the virtual world

Costs Building a real-world simulation tool like Risk Hunting is comparable to flight simulators [START_REF] Kozak | Transfer of training from virtual reaality[END_REF]: expensive and long. In the field of construction, using BIM as a support to generate the IVE [START_REF] Dris | Integration concept and model of Industry Foundation Classes (IFC) for interactive virtual environments[END_REF] allows more flexibility and considerable cost reduction.

Ontologies OpenBIM Based IVE, however, has its limits: the interaction and the definition of the objects on which it is possible to interact is not treated by the IFC (Industry Foundation Classes) standard. The development of an ontology meets the needs to enable the reuse [START_REF] Noy | Ontology development 101: A guide to creating your first ontology[END_REF] of knowledge of a specific area and to share a common structure of information. From the computing point of view, and more particularly knowledge engineering, the most commonly accepted definition is that of (Gruber, 1993): "an ontology is an explicit specification of a conceptualization of a domain". Conceptualization makes it possible to identify by an abstraction process the essential concepts referenced by the terms of the domain and the specification makes explicit the meaning associated with these concepts by associating them with a definition.

Few ontologies have been created for the construction sector; for information processing [START_REF] Zhang | Development of IFC-based construction industry ontology for information retrieval from IFC Models[END_REF] a complete study of which has been presented by Issa and Mutis [START_REF] Raja | Ontology in the AEC Industry: A Decade of Research and Development in Architecture[END_REF] in the description of BIM uses [16] and BIM objectives but also in asset management [START_REF] Tibaut | Ontologizing the Heritage Building Domain[END_REF] and in the description of the field of action of BIM [START_REF] Zhang | Development of IFC-based construction industry ontology for information retrieval from IFC Models[END_REF]. All these researches agree on the need for a field that is digitalized to develop these ontologies.

Contribution The interaction needs of VR have not yet been formally addressed and this is the part that our research addresses by proposing a specific domain [START_REF] Costin | Requirements for Ontology Development in the AECO Industry[END_REF] ontology. Focusing on the Noy&McGuinness Seven-Step method based on Protege software, we offer a common working environment for interactive VR applications whose virtual environment is derived from OpenBIM.

Proposed Solution and Results

The creation of ontologies

Several methodologies have been proposed for the construction of ontologies. These methodologies propose to use different types of information media to start the ontology such as terminology databases, technical documentation, ontologies, interview reports, questionnaires. We can cite inter alia Cyc methods (Lena and Guha, 1990) Steps iv to vii are repeated as many times as necessary in the ontologization process. In view of OpenBIM Based IVE ontology, the addressed domain is that of OpenBIM and interaction in virtual reality. We mainly used IFC ontologies [START_REF] Beetz | IfcOWL: A case of transforming EXPRESS schemas into ontologies[END_REF] as the basis for project development. Working groups are currently collaborating to use these data and technologies to support their developments such as the buildingSMART Data Dictionary [START_REF]buildingSMART Data Dictionary. ISO 12006-3 based ontology for the building and construction industry[END_REF] (bSDD). We will therefore evolve the model with the results of their studies. The acquisition of knowledge of the domain is the phase allowing enumeration of the main terms of the domain. For this we have studied the numerous working documents, standards and processes of the various IVE general services as well as the existing Risk Hunting Courses and their specifications. Based on the Omniclass [START_REF]OmniClass Construction Classification System. A classification system for the construction industry[END_REF] table 35 -Tools in order to qualify object classes, we were then able to develop the properties inherent in the interaction such as the ability to grab an object and how it can be manipulated.

Example: Concrete bins are of the class IFCBuildingElementProxy with the Omniclass property number 35-51 31 31 11 51 which allows us to qualify the use of the object to which we add the definition of manual handles on which we can interact to move the object on wheels or the lifting hooks that the crane can use. These two properties have been developed with the ontology presented here.

The evaluation phase is continued on different virtual reality applications. In our case, we chose the Risk Hunting Course because it seems to us to be one of the most complete VR applications in terms of interaction with the virtual environment: moving around a building model, moving objects , collaborative work, note taking and exchange with the crane operator.

Design of the application

BIM models loading. A virtual Risk Hunting Course will be more meaningful to the companions following the training if it is based on the site to which they will be transferred or on which they currently work. Starting from this principle, up to eight BIM models will be used: BIM PIC corresponding to the model of the Bureau of Study of the Organization Methods of Construction site, which will make it possible to visualize the installation of the building site in the phases of BIM PLB, execution model of the plumbing design office. On these eight digital models, only the model of structure is necessary to the models of the methods but did not need to be loaded directly in the virtual environment of Risk Hunting. The seven other BIM models are loaded in IFC format in the game engine via the integrator.

Interactive Environment To display and interact with the virtual environment, we can use different kind of devices with varying degree of immersion. These devices include a screen mouse and keyboard, a head mounted display (HMD) or a CAVE TM . We decided to use a HMD (HTC Vive) in our case because these kinds of system can be easily transported and deployed in training centres while allowing a good degree of immersion. The trainee wears a headset that cover his field of view and shows him the virtual environment and can move in a limited play-area by physically walking. The trainee also has two controllers to interact with the environment in a few different ways (shown in Figure 4): Walking and teleportation is used to navigate in the environment. The trainee can physically move in the play-area to navigate through the virtual environ-ment. The play-area being much smaller than the virtual environment, a second way of navigating through teleportation is implemented. By pointing with the left controller, the user is able to teleport (which move the play-area location in the virtual environment) to reach unattainable locations. Additionally, the trainee can use a hologram-map to see a miniature view of the building and directly teleport across the whole environment. Both the teleportation and the hologram map use the semanic of the IFC to know where the trainee is allowed to go and what to display in the hologram-map through filtering of IFC classes. As the IFC classes does not define the semantic of teleportation target areas, the filtering has to be done manually either by adding a custom property on the IFC objects or by manually listing which IFC classes can be teleprotation targets. Use and grab objects. Some object in the scene are usable and interacting with them can trigger certain effects (e.g. interacting with a closed door will open it). To interact with an object, the trainee has to point it with the left controller and press the interact button. This method allows to interact with an object without having to physically reach it. We use the IFC properties to define which object are interactable and automatically add the interaction metaphor (similarly to teleportation). Additionally, we can define interactions on specific part of a IFC object by using sub-products to identify which area trigger which interaction. For example an concrete bins have a two type of interaction : The green parts trigger a manual interaction to move the bin whereas the yellow parts are used to hook the bin to the crane (see Figure 4). Also, some object in the scene are grabbable. These objects can be grabbed by pointing them with the right controller and hold the grab button. IFC properties can be used to automatically define which objects are grabbable by looking at their size and weight in the IFC properties.

Scenario To address the issue of reusability of the application, we build a model of Virtual Risk Hunting to self-generate randomly possible serious errors based on the integrated IFC. Thus, depending on the projects, the scenario adapts to it and proposes a different set of errors for each launch. To achieve this goal, we decomposed this problem in two parts : error insertion and error scriptwriting.

For error insertion, we defined different kind of errors to be automatically applied to the virtual environment. We rely on the ontology of the IFC to detect every possible occurrence of each error that can be applied in the environment (by adding, removing or modifying object in the scene). For example, by knowing the semantics of fixings, PTE platforms and walls, we can automatically misplace a fixing above an opening (see Figure 5).

For error scriptwriting, we write for each kind of error a scenario that define it's behaviour and how to correct it. Scenarios are defined with the #SEVEN model [START_REF] Claude | Short Paper : # SEVEN , a Sensor Effector Based Scenarios Model for Driving Collaborative Virtual Environment[END_REF] which is based on a petri net model and use sensors and effectors to handle the interaction with the environment. For the PTE platform example, we wrote a scenario where platforms collapse if the trainee don't fix the fixing position when he is close to the platform (see Figure 5). We use both the semantics of the IFC and the sensor/effector model of #SEVEN to write generic scenario that can be applied generically to any situation. This is done by having custom sensor and effector that communicate with the IFC semantic. On the left, one fixing is misplaced (above an opening). On the right, this is what the trainee will see if he walks away from the PTE platform if he does not signal error.

Collaboration A collaborative virtual environment (CVE) [START_REF] Chellali | Haptic Communication to Support Biopsy Procedures Learning in Virtual Environments[END_REF] is an application that uses a virtual environment that supports human-computer-human communications. CVEs have many applications in medicine, architecture, learning or simply entertainment. In the context of prevention training, this option offers trainees and trainers a way to communicate and collaborate synchronously [START_REF] Churchill | Collaborative virtual environments: An introductory review of issues and systems[END_REF] and seamlessly. The BIM Collaboration format (BCF) was introduced following an idea from Tekla and Solibri to separate the communication of the messages describing the problems [START_REF]The worldwide authority driving the transformation of the built asset economy through creation & adoption of open, international standards[END_REF] discovered on the digital model from the model itself. Indeed, before the BCF was introduced, users who wanted to exchange data, conflict detection or modification requests on the model had to send the entire model. The receiver of the model had to compare it with the previous version to be sure to see all the changes. The BCF format allows you to attach comments, small portion of the BIM model and views, and create it as a virtual post-it.

Questionnaire Design During our research on the benefits that virtual reality can bring compared to traditional training methods, we have been faced with the problem of lack of existing studies. The return of the experiments carried out does not make it possible to establish a concrete result. If the finding seems clear about the benefits of this technology during the training, its interest in the long term remains to be proven. We therefore designed a questionnaire system based on three sheets. The first categorizes the trainee in terms of knowledge prior to training and in terms of technology. It is proposed in preamble to the formation. At the end of the training in VR, a second questionnaire makes it possible to evaluate the acquisition of knowledge according to the trainee's assessment. Then, a month later, the same questionnaire is submitted to them again. This test phase will be continued in the coming weeks.

Conclusion and Future Works

The various areas of AECO industry requiring the formalization of knowledge is still vast but through this study, we propose a solution improving the interoperability between virtual reality and OpenBIM, developing the works of BuildingSmart on the IFC, the bSDD, rankings and BCF in the field of VR.

In the future, it will possible to reiterate the ontology construction process by studying the implementation of the error creation system and the needs of the ontology by studying the actions of trainees during their training. We are also thinking of using it on other virtual reality applications by studying the possibility of co-activity, adding stress levels according to people's roles, and qualifying men's security objects in order to make them more effectives.

Fig. 1 .

 1 Fig. 1. Evolution of frequency rate (TF) = (number of accidents in first settlement / hours worked) x 1,000,000.

  and SENSUS (Swartout et al., 1997), the KACTUS approach (KACTUS, 1996), METHONTOLOGY methodologies (Gomez-Perez et al., 1996) and On-To-Knowledge (Staab et al., 2001). The process of building an ontology is composed of several phases such as described in Figure 1 (The life cycle of an ontology (Fernandez et al., 1997). The Seven Steps Method proposed by Noy & McGuiness breaks down its activities as follows: i. Determine the domain and the scope of the ontology. ii. Consider reusing existing ontologies. iii. Enumerate important terms of the ontology. iv. Define the classes and the class hierarchy. v. Define the properties of classes -slots. vi. Define the facets of the slots. vii. Create instances.

Fig. 2 .

 2 Fig. 2. Ontology Lifecycle

Fig. 3 .

 3 Fig. 3. OpenBIM based IVE Onthology -Protege

Fig. 4 .

 4 Fig. 4. Examples of the different ways to interact with the environment. From left to right: teleporting to a new location by pointing, teleporting to a new location by using the hologram-map and interacting with an object.

Fig. 5 .

 5 Fig. 5. Example of misplacement of fixings of PTE platform in the virtual environment.On the left, one fixing is misplaced (above an opening). On the right, this is what the trainee will see if he walks away from the PTE platform if he does not signal error.