Mathieu Brugidou
email: mathieu.brugidou@edf.fr

Pierre Le Queau
email: pierre.le-queau@upmf-grenoble.fr

Analysis of non directive interviews with the « bundle » method by

This article presents the results of work on the analysis of non-directive research interviews (ENDR). The identification of a series of terms which are repeated to a significant extent at the same time in a short sequence of text (i.e. 'bundles') enables us to see the 'meaning packets' which make up the episodes. By following these bundles of terms, we hope to be able to locate thematic ruptures (the end of a series of bundles), i.e., the passages where the thread of the narrative unfolds as a new theme (or in this case, an episode) is developed (new series of bundles). The algorithm of the bundles has been incorporated in the semantic analysis software TROPES. We intend to demonstrate the utility of this method for the analysis of non-directive interviews. In particular we will seek to combine a lexicometric approach (bundles formed from graphic forms) and a semantic approach (bundles formed from classes of terms considered as equivalent in terms of meaning). NDRI, narrative, structural analysis of narrative, analysis of discourse, lexicometry, bundle.

Graphique 1 : les différents types de distribution d'une forme *

Semi-directive or non-directive interviews are currently employed by sociologists. However, it would seem that the status given to "people's words" is not altogether clear. Either we consider that the interviews constitute a generally reliable source of information (once the information has been extracted from the subjective 'chaff' of the interview) or we see them as a discourse whose singularity is irreducible and which can only be reported word for word, thereby abandoning all hope of real analysis. While the latter view leaves the interviews intact (with analysis being abandoned for a simple functional expression of the interviews), the former view often leads to a "deconstruction" of the interview. The analysis of the thematic content is the most common methodological approach. The discourse is broken down and reduced to a certain number of themes which are then transformed into hypotheses subjected to quantitative validation. The uncertainty surrounding the status of the interview is compounded therefore by doubts regarding the analytic methods. These difficulties appear to be linked, in part, to the fact that we do not consider the interview as a narrative, i.e., a story with a beginning, a middle and an end, whose coherence is ensured by a "plot." We thus lack knowledge on the social effects specific to the narrative where the narrator puts forward for the interviewer -and sometimes for himself -his own story. We do not fully understand the narrator's operational modes: the identification and narration of individualized moments and their articulation in the form of "episodes" in a coherent "plot" which renders them comprehensible to us.

Indeed, what we must be able to identify is, on the one hand, the different episodes or sequences and, on the other hand, the cohesion of the narrative (which renders intelligible what would otherwise be a series of unlinked episodes). The cohesion of meaning cannot therefore be the proposition but rather the sequence. We propose here a method for highlighting these sequences and the way they are linked together.

The identification of a series of terms repeated at the same time in the same period in a short sequence of text (i.e. 'bundles') enables us to see the 'meaning packets' which make up the episodes. By following these bundles of terms, we hope to be able to locate thematic ruptures (the end of a series of bundles), i.e., the passages where the thread of the narrative unfolds as a new theme (or in this case, an episode) is developed (new series of bundles). The algorithm of the bundles has been incorporated in the semantic analysis software TROPES. We intend to demonstrate the utility of this method for the analysis of non-directive interviews. In particular we will seek to combine a lexicometric approach (bundles formed from graphs) and a semantic approach (bundles formed from classes of terms considered as equivalent in terms of meaning).

"Bundles"

The dynamics of the narrative

Repetition is the motor of the spoken narrative. The notion of "bundles" reflects this. Research on this form was directly inspired by P. Lafon who highlighted the value of a sequential approach using lexicometry [START_REF] Lafon | Statistique des localisations des formes d'un text[END_REF][START_REF] Lafon | Dépouillement et statistiques en lexicométrie[END_REF]. By adopting this approach, he demonstrated that it was possible to estimate the regularity of the distribution of a form in a "homogenous text with a beginning and an end". Irregularity seems to be the rule insofar as the forms tend to arrive "in bundles" which are grouped together in a limited part of the text, whereas regularity is rarer and characterized by "athematic" forms. Thus it should be possible to identify the themes and thematic sequences within a spoken narrative.

Within the framework of an analysis of television interviews with politicians 1 , a specific method of lexicometric processing was developed which enables us to identify the repetitions which are an inevitable feature of politicians' speech. The program is only interested in a certain number of these repetitions. It identifies and measures the "remarkable" redundancy of certain terms, essentially nouns, which organize the development of the discourse. Within this context, "remarkable" is defined as an irregular distribution of these words. The method was subsequently tested for the processing of non-directive interviews (of biographical narratives) as part of university research (M. [START_REF] Brugidou | L'analyse des entretiens non directifs par la methode des rafales[END_REF]. Within this context, the repetition takes on a wholly different meaning. The initial project aimed to identify the succession of themes, without thematic injunction on the part of the interviewer. Although it may appear trivial at first sight, it is interesting to note that in comparison with a television interview with a politician, the narrative of an "ordinary" person talking about himself, appeared infinitely "poorer". The different bundles are much less numerous, but longer. In other words, given comparable "texts", an ordinary person telling his life story uses a far more limited vocabulary than a politician taking part in a television program. R. Ghiglione's team is responsible for the development and improvement of the processing of bundles in the TROPES software. Discussing psycho-socio-cognitive theory in a recent work, R. Ghiglione developed the idea that the distribution of propositions in a text is subject to certain rules which condition the text's internal coherence. We find in particular the human memory's capacity to "process" a text in only very short cycles: "five to ten propositions are processed in a cycle, some are kept in a 'buffer' memory, allowing a before/after link" (1998, p. 25). Short-term memory (MCT) and its role in cognition is also discussed in Cognitivo-discursive analysis, a work which goes into more detail on the production of referential coherence. To sum up, it would seem that repetition, in either literal or anaphoric form, is a way of compensating for memory gaps, and is an essential tool in the production of the internal and sequential coherence of the narrative.

2. The algorithm of bundles

The aim of P. Lafon's work was to characterize the entire distribution of a form. Some of these forms, as we have seen, are known to be very irregular. Others are more frequent. Here we are concerned with identifying all the passages in the text where any form is repeated to a noticeable extent, i.e., overused given its overall frequency in the text. In other words, we are not interested in the overall distribution but rather its localized characteristics. It is in our interest therefore to 'optimize' the bundle, ie., to retain only the most dense part/s in the distribution of a form, where the differences between the different addresses of the form under consideration will be the smallest. One of the consequences of this choice is that one form can give rise to several "bundles".

Diagram 1

1 The study included different TV programs but the detailed analyses are taken from "l'Heure de verité". M. Brugidou: L'election presidentielle: discours et enjeux politiques, Paris, L'Harmattan, 1995. Built by the TROPES software, diagram 2 represents all the bundles identified in a non-directive interview using the algorithm presented previously. All the graphic forms have been retained and grammatical words) 3 . We should note that the notion of the graphic form, neither prejudges the syntactic category of the term, nor its meaning. This presents considerable disadvantages: the forms are not lemmatized (the distinction between plural and singular, the different forms marked by a verb, etc.), and furthermore homonyms are not indicated (e.g. the French word "livre" may have any one of several meanings: a book, a unit of weight, pound sterling, or the third person of the verb "livrer").

Without entering the debate over the pros and cons of lemmatizing [START_REF] Salem | Pratique des segments répétés[END_REF][START_REF] Tournier | D'où viennent les fréquences de vocabulaire? Le lexicométrie et ses modèles[END_REF], it is worth reminding ourselves that by using the graphic form, we temporarily refuse to interpret the text. We are not attempting to anticipate meaning: lemmatizing would be to interfere in a process which is inherently unpredictable. To remove the ambiguity from the forms (the unit of weight vs. the currency) is clearly necessary, where our understanding may be compromised. Unable then to fix a clear boundary, we must therefore temporarily abandon the search for meaning. This decision is a compromise solution which enables us to advance.

The diagram reads from left to right and from top to bottom: from the first occurrence of the text to the 7639 th which marks the end of the interview. The form "troisieme" (here meaning the 'third year' in secondary school) is the first bundle of the interview. It occurs four times grouped together in this first section of the text. The 2 It is easy to imagine the case of a form repeated often at the beginning and reappearing later -at quite regular intervals -in the rest of the text. An estimation of the overall distribution would not point out the localized concentration of the form. 3 Given the nature of the test used in the algorithm (normal law), we will not retain the terms whose frequencies are too low (f lower than or equal to 10; for lower frequencies Poisson distribution should be used). interviewee states that his consumption of cigarettes increased in "troisieme", then in "seconde", a term repeated five times at the beginning of the interview. We are thus able to follow the bundles symbolized by discontinuous lines with a dot at each end (first and last occurrence 4 ) until the end of the text "je" ('I' in English). The interview finishes with the tale of a car accident provoked by smoking: "D'autant plus que je m'étais planté avec ma voiture cette fois" ("All the more since this time I'd crashed my car"). Moreover we may note that certain forms form the basis of several bundles: "fumer" -'to smoke' -(here distinct from the third person plural form "fument") recurs three times up to address 4181 while its use in the second half of the interview is noticeably reduced. The first person singular recurs up to ten times over the course of the interview. Thus, the personal pronoun of the first person singular, while appearing very frequently in this type of text (472 times here) does not have what can really be called regular distribution.

The diagram also illustrates that the use of the third person plural of the verb "fumer" corresponds to the only moment of the interview where the first person singular does not come in a bundle. Although this may appear unimportant, it allows us to characterize a passage in the middle of the text in which the interviewee talks about face-to-face confrontations between the smoker and non-smokers. Here the "subject" of the narrative becomes collective, proof that the absence of lemmatization can be illuminating.

In the same vein, we can see a difference between the singular and plural use of "augmentation" (increase) positioned closely within the text. This difference would appear to translate a movement of generalization of thought where there is a shift from multiple "augmentations", each one being therefore specific, to the generic category of "l'augmentation" (the increase). In short, by induction, the subject is generalizing about his experience.

Finally, we can see that recurrence is limited (in fact, repetition leads to a sort of mechanical regularity, although the example of the personal pronoun "je" ('I') qualifies this observation). Few bundles recur: the verb "arrêter" ('to stop') appears three times during the interview (7 occurrences, then 4 then again 7).

Given that it is the central theme of the interview, it is suprising therefore to find only one bundle of "cigarette". This illustrates perhaps one of the weaknesses of the lexicometric approach. It neglects plural forms, while distinguishing between "clopes" and "cigarettes". Similarly, "tabac" (tobacco) or "legeres" (low-tar cigarettes)

4 The wording of the bundle is located close to the bundle's address. We thus note that the bundle formed by "etais" (was) has 10 occurrences. The software identifies the address of the first occurrence -380-and the last -1673-. It enables us to edit the contexts of each occurrence and to "navigate" in the text.

can be considered, if not as synonyms then at least as "equivalents".

3. 2. Classes of equivalent

The TROPES software enables us to go beyond the lexicometric approach by taking into account, on the one hand, certain morphosyntactic aspects, and on the other hand, by proposing a semantic analysis of substantives. It can be useful to classify grammatical words into different types of conjunctions (addition, disjunction, cause, condition, goal etc.) categories of modalization (negation, intensity, time, place etc.), or more typically into different forms of pronouns, in particular for the analysis of thematic sequences (to highlight the construction of the episodes of the narrative).

Causal conjunctions (therefore/so, because, since etc.) are a good example. They are used extensively at the beginning of the interview, when the inquiry exposes the different factors which led the narrator to smoke. We thus observe the following sequences at the very beginning of the interview: TROPES will consider the forms "donc", "puisque", "car" (which can be roughly translated as, respectively, 'so', 'since' and 'because') as functionally equivalent. A long bundle of 14 occurrences of 'causal conjunctions' was thus identified before the bundle "famille" 5 located at the start of the interview.

"Ben,
Diagram 3: distribution of causal conjunctions per 300 word block

4 4 1 2 0 0 1 3 2 1 1 1 0 0 3 1 0 0 0 1 1 0 0 3 2 4 7639 0 Joncteur Cause
We can see, furthermore, that the use of negation modalizations increases significantly after the first third of the narrative when the critical remarks concerning smoking multiply ("Mais les vrais copains ne fument pas" -"but real friends don't smoke").

TROPES constructs classes of semantic equivalence. These classes all resemble hyponyms of a term: for example "famille", "parents", "frangin" (colloquial for 'brother') etc. are considered as equivalents of /famille/. The software proposes three levels of classification for the "references", from the widest (sphere 1) to the narrowest ("reference"). Here we will consider only the narrowest level. The construction of the "script" allows 5 For reasons of readability, we have not included bundles formed from grammatical words on the diagrams. us to build our own classes of semantic equivalence "by hand", wherever we can, by pushing the initial logic of the software which then prioritizes the references within the substantives, and includes adjectives, verbs, etc.

Diagram 4 presents the diagram of bundles formed from the classes of semantic equivalence proposed by TROPES. The comparison with the preceding diagram of bundles (cf. diagram 2) constructed from all the graphic forms, highlights certain differences linked to the semantic approach used by the software. Only the classes of semantic equivalence formed from substantives appear on this diagram. Adjectives and verbs are not considered in the analysis. Grammatical words are grouped according to the principle outlined above but they are not presented in this diagram 6 . The merit of this approach (selection of substantives and semantic equivalence only) is that it renders the representation of the text clearer. At the same time, it would appear to notably reduce the quantity of information. Detailed analysis of the diagram enables us to qualify this initial observation. If we are to consider the substantives alone, the semantic approach would appear on the contrary, to be richer. The following diagram, constructed from graphic forms, illustrates this. The semantic approach gives us the bundle "ami" (friend), formed from "copain" (colloquial for friend), in both plural and singular form 7 . This is due more to lemmatization than semantic analysis. Its usefulness is clearly 6 The bundles are also therefore calculated according to syntactic classes of equivalent. They can be made to appear on the diagram. Nevertheless for reasons of readability, these bundles are not represented here. 7 " T'est_entraîne par des copains et t'as envie d'essayer pour voir ce_que ça donne et_puis…" ('You're influenced by your mates and you want to try just to see what it's like and then…') " y a des copains " ('there're your friends…') " il_y_a un copain qui m'a_propose une certaine marque et depuis " ('a friend offered me a particular brand and since then…') visible however since it enhances our understanding of the place of "copains" in the smoker's narrative. The same can be said for "paquet" (packet). However the presence of "famille" 8 , "jour" (day) or "cigarette", included in the terms "cigarette(s)" and "clope(s)", can be explained by semantic equivalence.

The finished canvas would appear to be more complete, giving a role to the leading players (friends, family...), evoking "cigarette". Here too our remarks need to be qualified. We have seen that most differences are due to problems of lemmatization. An interesting example is the variation between "clope" 9 and "cigarette". Moreover, the semantic approach would seem at times to be approximative. Thus the bundle "durée" ('length of time') groups together "heures" ('hours') of the day and "seconde" in the same category, mixing the unit of time and the class, "seconde". The "scripts" however, enable us to improve, even correct, these classifications.

Finally, we observe once more that the second sequence reconstructed by the two diagrams are remarkably similar: all the bundles are common with the exception of "machin" (colloquial for 'a thing') for the 'formal' approach and "moment" for the semantic analysis. Similar differences and confusion exist throughout the interview. We can also see that the semantic approach is better adapted to taking the less structured part of the interview into account. This is why we are now going to look at the "concurrence" of bundles, i.e., the formation of the sequence in the text via the notion of an "episode".

"Episodes"

1. The unity of narrative meaning

For many, the sequence, or episode, represents the "missing link" in the analysis of the narrative in its longitudinal or syntagmatic dimension. It is here that non-directive interviews are an indispensable tool. The process highlights the groupings, in which bundles appear numerous and inter-linked, thus forming units of coherent text. The totality of these bundles work towards the evocation of a theme.

The graphic representation of the distribution of the bundles in the text points out the existence of a relative "vacuum". Furthermore, the presence of conjunctions (temporal in particular: before, after, then…), leads us to suppose that at these moments, the narrator is in the process of exhausting the subject, a moment of his life, and is searching for a way to "switch" to another. We lack the means to objectives this shift with any degree of certainty, unless it introduces a cut-off point where in reality there is a real attempt to create continuity. The authors of the software developed a procedure allowing us to objectivize the sequence. It consists of processing the bundles, or repetitions, which enables the text to be cut into episodes, an episode being a unit corresponding to "the point where bundles begin and end" (1998, p. 83).

It is primarily therefore the congruence of certain bundles which form what R. Ghiglione & al. call an "argumentative block", possessing its own referential coherence. Here in effect the bundle is no more than a visible formal indicator of all that is woven in with the referents: relationships the narrator attemps to build between the characters, events and situations that he describes. The technical contribution of the team of "cognitivists" is however more complete and more complex. In particular, they take into account the presence of "argumentative operators" (e.g. modalization of time or space) to determine, despite the prolonging or overlapping of one or several bundles, this "passage" from one episode to another.

Finally, the episode takes into account a "micro-sphere" of evocations, with its own internal coherence. This sphere can communicate with others in different ways: chronological succession, causality, metaphorical " je me laissais plus_ou_moins entraîner par des copains. " ('I let myself be more or less influenced by my mates') 8 "Aucun dans ma famille," ('Nobody in my family')

"Ben, aucun dans la famille avec une petite nuance tout_de_même puisque si je m'en souviens c'est que cela m'a_marqué." ('Well, nobody in my family -although not quite because if I remember well it struck me') "J'avais_vu mon frangin qui avait donc quatre ans de plus_que moi et" ('I'd seen my brother who was then four years older than me and…') " En seconde, mes parents ont_commencé à le savoir et j'ai_augmenté franchement ". ('In the fourth year my parents started to catch on and I increased alot') " parce_qu'avec mes parents, on s'entendait franchement pas." ('because I really didn't get on with my parents') 9 "Clopes" (slang for cigarettes) is often used in a negtative context: "on a plus de clopes" ('we've got no more "clopes").

Moreover, these terms translate distinct levels of language, where the register shifts from colloquial to formal and back again. redundancy, etc. What is remarkable, in any case, is the mechanism of successive integrations which enables the method to be updated. Here the cognitivists' proposition coincides with that of structural analysis developed notably by C. Bremond, for whom "elementary sequences combine to form complex sequences" (1966, p. 61). In other words, the initial 'stammering' of the discourse, which is simply a search for and production of coherence at the level of the proposition, produces by integration a superior scale of meaning. The narrative thus appears as an unfolding plot (articulation-integration) of several episodes, each containing a part of the meaning the narrator plans to produce.

The experimental work we will consider here, consists of testing the operability of this identification procedure. We will also explore its meaning, particularly in the context of a sociological approach. A doubt remains concerning the significance of the episode, and what it may contribute to our 'understanding' of the narrative, and the intentions of the narrator. Our interrogation is due to the fact that this method can be applied to any text. Indeed, analysis of Gustav Flaubert's classic, Madame Bovary, points out the existence of bundles which in turn enable us to identify the episodes. These episodes do not necessarily coincide with the organization of the novel by chapter, for example. Given that the rules of literary composition have little in common with those of narrative, what is the significance of the repetitions in this context and what is the significance of the episodes that the procedure identifies?

This examination will look therefore at the "level", to quote R. Barthes, that we consider to define the episode, based on the hypothesis that a narrative is essentially a series of interlocking sequences implying quite different levels of reference.

The algorithm

It is via the mode of identification of the episode (or the sequence) that TROPES enables us to resolve a certain number of difficulties.

Our aim here is to dispose of a reliable method, capable of identifying these sequences and their linking while remaining 'as close as possible' to the text. We will use therefore a formal representation of the text (that given by the algorithm of the bundles) and attempt to identify co-occurrences of bundles, i.e., the parts of the text where the concentration of bundles is significant. At the same time, we hope to be able to identify thematic ruptures, those passages where the thread of the narrative unravels as other melodic lines begin.

The difficulty lies in this overlapping of sequences, and its degree of concentration. Ruptures can be strong or weak. A formal approach is therefore necessary to follow the "respiration" of the narrative. Considered one by one, each bundle seems, in its rapid staccato, to give the text its own rhythm. And yet their interweaving in packets creates deeper and more muted echoes. It is this, the narrative's rhythmic thread, that we must find.

Let us suppose that a new episode has begun when a large number of bundles begin and end. This treatment can be used on all four levels of classification of the reference available in Tropes (i.e. Spheres of reference 1 and 2, References used, Scenario). In all cases, certain A.P.D. (Analyse propositionel de discours, a method developed by Ghiglione et al) meta-categories (performative verbs, conjunctions, modalizations and personnel pronouns) are used.

When all the episodes have been identified, TROPES uses the bundle addresses (the average number of occurrences of the words included) to give the bundles their episodes of belonging. In the bundles diagram, the wording of each bundle is centered on its address. Although the bundles always participate in the construction of an episode, an episode may be empty if it contains no bundle address (the episode contains bundles which 'cross' it, but which do not 'belong' to it). Since the episodes are defined by the edges (beginning and end) of the bundles, and not their addresses, this must not be considered as an anomaly.

Concerning the stability of the partitioning: given that several levels of classification of the reference may be used, the number of episodes depends on the desired level of generality.

3. The level of experience

The validity of the episodes proposed by TROPES must still be verified. We will test therefore the stability of the classes of bundles, notably by varying the nature of the bundle (graphic or reference form?). This validation is purely formal however; the validity of the proposed sequences must still be demonstrated from the point of view of 'meaning'.

The episodes create an 'equivalent' between the different objects of the discourse. They represent an important moment in the integration of the narrative. Our aim here is to build a transition between the level of formal description of the text represented by the bundles and the episodes and their level of description proposed by the structural analysis of the narrative.

3. 1. Stability of the classes of bundles.

A simple method for ensuring the validity of the episodes is to test the internal coherence of the method. In other words, if we vary certain 'technical' parameters, like for example the type of bundles considered do we observe stability in the classes of bundles, i.e., the episodes? If the partitioning proposed by the algorithm is very different, the method is invalid. If it varies little, we are led to conclude that there is a certain consistence in the 'phenomenon observed'. Given the specificity of the algorithm of the episodes, it is essentially the number of bundles taken into account in the analysis which determines the partitioning of the text. In other words, any changes liable to modify the number of bundles are important. If only the substantives or all the forms of words are considered, this parameter changes. Similarly, if we favor an approach by class of equivalence (semantic and syntactic for the grammatical words), the number of bundles changes 10 .

These two parameters can of course be crossed: The experiment has been simplified here:

-The lines show either the substantives and the grammatical words in classes (types of conjunctions, moralization etc.), or all the syntactic categories (substantives, adjectives, verbs... and the grammatical words which are not grouped in classes), -In the columns, the alternative between the graphic forms and the classes of semantic equivalence is tested.

By neutralizing the 'grammatical words in classes' variable we note an important effect linked to the classes of semantic equivalence. The algorithm identifies ten episodes (B) and not seven (A). However, if we consider all the syntactic categories, the difference linked to the groups of substantives in classes of equivalence is zero, in quantitative terms (twelve episodes in C and D). We know therefore that 'qualitatively', the semantic approach produces certain effects. By neutralizing the graphic forms variable we note that if we consider all types of word the number of episodes increases significantly (from seven -A-, to twelve -C-). Conversely, if we consider all the syntactic categories the increase is smaller (ten -B-to twelve -D-). This effect must be viewed in a different light: by considering both the number of episodes and the definition of these episodes. Returning to the diagram confirms the stability of the proposed groupings.

10 To be complete, we should add that all manipulations of frequency thresholds have an influence on the number of bundles. For example, if we only consider bundles longer than 3, 4 or 5 etc., but also if we only consider bundles formed from words whose frequency is above a certain threshold (here above or equal to 10).

In effect, the partitioning into episodes proposed in option A (cf. diagram 5) is not questioned by the other options but rather improved. The new classes of bundle exist in effect in all cases except one 11 inside those classes already identified. In other words, the B options (taking into account of semantic equivalence within the substantives), C and D (taking into account of all words) enables us to identify all sequences inside a larger sequence that we can therefore consider as 'stable'. The change of viewpoint enables us to ensure the stability of the episodes which are not here artifacts due to the method and to enrich the interpretation of the episodes by identifying sequences inside the episodes identified. We thus highlight the 'Russian doll' nature of the narrative. Moreover these comparisons are interesting because they outline the first stages of an interpretative method based on the following two stages: Verification of the validity of classes of equivalence on the substantives ==> Identification of sub-sequences in the episode, distinction between the rheme and the theme through the study of other types of word

3. The theme and the rheme

The comparison of the different options for analyzing the text draws our attention to another phenomenon of fundamental importance. We have seen that the taking into account all types of word (as opposed to substantives only) does not dramatically modify the partitioning of the narrative into an episode. This description is simply more precise. We will observe nevertheless, that the distribution of the substantives by bundle and the distribution of the 'other words' (adjectives, verbs, grammatical words...) is not identical.

Let us consider diagram 6 (or 2) and compare it to diagram 4 (or 5). We can see that there is a significant concentration of the 'other words' between the groups of bundles formed by the substantives. In other words, between each large grand episode identified, we can see a series of verbs and grammatical words. Thus between episodes 2 and 4 of diagram 4, we observe a series of 10 terms (etais (was), jamais (never), fumer (to smoke), ai tenu ((I) held), quand (when), et puis (and then), avais (had), arrêter (to stop), arrêtes (stop), quelque part (somehow/somewhere) positioned between the last substantive of episode 2 ("vacances") and the first of sequence 4 ("jour"). The software therefore identifies a third episode formed solely from grammatical words.

Similarly, between episodes 4 and 5, we identify a series of six 'other words' (legeres (lights), aucun (none), reprends (start again), quand (when), il y a (there is/are), souvent (often)) positioned between "ami" and "compensation". The phenomenon is not as clear between episodes 5 and 6 (only 2 terms) unlike between 6 and 7 where we count six terms: fument (they smoke), arrêter, autre (other), moins (less), fumer, crois (believe/think), etc.; and between episodes 7 and 8 (five terms). The last two transitions between sequences are less clearly marked by such concentrations of 'non-substantives'.

It is now possible to reconstitute the construction of episodes by distinguishing between the reference (theme or topic) and the commentary (rheme). From the bundles diagrams, we will therefore make a first schematization of the narrative. In the following table, we have considered only the largest episodes (cf. diagrams 4 and 5). In column one, we find the substantives, in column two, the other types of word.

The substantives are grouped in a very large class of equivalents. In sequence A for example: "ami" (friend) and "famille" indicate people; "paquet" (packet) and "cigarette" refer to the same object; "etudes" (studies), "jour" (day), "vacances" (holidays) refer to periods of time. The provisional classifications identify the narrative functions at work in the text. Secondly, we must characterize the type of relation that exists between these different objects by identifying the narrative functions. Here we assume functional equivalence between these objects. Only the level of formalization proposed by the structural analysis enables us to confirm this.

Furthermore, between sequences, we have identified transitions between episodes, passages where the narrative flows primarily through the 'commentary'. This table indicates the levels of transformation between the different episodes of the smoker's narrative.

We note for example strong continuity between sequences A and B. Certain bundles disappear (famille, paquet, etude, vacances) although the structure of the theme does not appear to be significantly modified. The transition between the two sequences (passage A/B) constitutes a variation on the verbs "arrêter" , "fumer" and "tenir" (respectively to stop, smoke and hold).

Here, the narrative 'changes foot', no longer evoking the origins of the smoker's history (imitating friends, facing up to his family), but rather the realization that a habit is setting in. The beginning of two new bundles, "habitude" (habit) and "besoin" (need), indicates a new melodic line which overlaps the first, sometimes modifying it profoundly.

Returning to the text makes the different mechanisms of the unfolding story clear, identifying the actors and the forces at work behind the scenes. The concepts of narrative structural analysis must now take over: the representation of the proposed text must constitute the first substrata of this analysis by indicating the principal sequences, and identifying the linking the ruptures.

Conclusion

The experiment confirms the relative stability of the episode objectivized, in the order of the narrative, by the bundle method. The program identifies this minimal unit around which the narrative is built, and also brings out the logic of integration of its different episodes. This work is intended as one of the possible methodological translations of the propositions, made notably by R. Barthes at the end of the 1960s, which aimed to found a structural analysis of narrative. It is based on the two fundamental functions implied by all narratives: the integration of secondary episodes in the broader meta-episodes, and the articulation of these meta-episodes.

The utility of identifying the episode, and its constitutive logic, has been confirmed by members of the cognitive sciences. The contribution of the 'words' research group is particularly influential here, in that it demonstrates the fundamental mechanism of the search for referential coherence, and the limits of memorization. But these arguments, though explanative, remain largely incomprehensible for the interpretive sociologist who must focus on the 'target meaning' of the narrator, in the sense given by M. Weber to this expression.

Diagram 4 :

 4 Bundles and episodes (Base: Classes of equivalence -reference)

  Bundles and episodes (Base: classes of equivalence and graphic forms on non-substantives)

  aucun dans la famille avec une petite nuance tout de même puisque si je m'en souviens c'est que cela m'a marque." (Well, nobody in the family -although not quite because if I remember well it struck me) "J'avais vu mon frangin qui avait donc quatre ans de plus que moi et..." (I'd seen my brother who was then four years older than me…)

"donc à l'epoque il devait avoir 16/17 ans," (So at the time he must have been 16 or 17…) " je me marrais interieurement parce que j'avais dejà fume" (I laughed inside because I'd already smoked) "Donc,ça c'etait au tout debut," (So that was right at the beginning…) "donc,ensuite,en troisieme,j'ai augmente." (So in the third year I smoked more…) "Dejà parce que je me suis libere un peu," (Already because I had some freedom) "Oui, donc, c'etait pas vraiment du stress," (Yes, so, it wasn't really stress…) "j'avais un peu un decalage vis-à-vis des autres donc," (so I was a bit out of step with the others…)

Note that taking into account all words (vs. substantives only) erases the last sequence based around "voiture" (car) (passage from A and B to C and D).

Exemple 1 : cas d'une forme régulière (mot-outil) d'une forme irrérégulière (mot-thème)


Yves Mahéo

Romeo Said Valoria

Service Invocation over Content-Based Communication in Disconnected Mobile Ad Hoc Networks

Keywords: disconnected MANETS, services, opportunistic networking, content-based networking

This paper presents a middleware platform for the provision of services in disconnected MANETs, focusing on service invocation. This middleware exploits content-based communications (through a publish/subscribe paradigm) and employs a store-carry-and-forward approach for the network-wide opportunistic dissemination of messages. Service invocation is implemented on top of these communication features. The paper first describes the main aspects of the middleware and then details the service invocation mechanism. We namely show that the potential multiplicity of service providers can be exploited in order to increase the client satisfaction and that several network healing techniques allow the reduction of the network load. The paper ends by a description of some simulation experiments in a realistic scenario, whose results reflects the performance of the approach in terms of client satisfaction and network load.

I. INTRODUCTION

The service oriented computing model has proved successful for the development and the exploitation of distributed applications. In this approach the interactions between service clients and service providers take place in two main phases: the first one is a discovery phase during which the client learns what services are available in its environment and identifies the providers that implement these services. In a second phase, the client establishes a binding with a chosen provider and remotely invokes the methods it proposes. When possible, a directory is used to gather the descriptions of the provided services. In this case, providers register their offer with the directory and clients can retrieve from it information about the services they want to use. Unlike traditional client/server, the service oriented approach introduces a late binding between the client and the provider, thus easing the support of the dynamicity of the environment. When a change occurs in the environment, for example a degradation of the connectivity or the appearance of other interesting service providers, the binding between a client and a provider can be undone and re-established with a new provider without completely stopping the whole application, or at least without rebuilding it.

The decoupling between interacting entities that characterizes the service-oriented approach makes it well suited for mobile ad hoc networks (MANETs) that are formed out of a number of mobile devices that communicate thanks to short-range wireless transmissions. The main advantage of a MANET that it can be used without deploying a specific -and sometimes costlyinfrastructure. Several application domains have already been identified that mainly or even specifically target MANETs. They include information sharing during disaster relief interventions, traffic information in town centers, or tourist services in infrastructure-less sites.

MANETs actually cover a wide variety of situations depending on the density of nodes in the network, their volatilitythat is the fact that they may temporarily be switched off-or their mobility scheme. The large majority of research work done so far on MANETs concerns what we call connected MANETs. In a connected MANET, some routing mechanism is available, implemented by each node of the network that plays the role of a router. Hence, although the topology of the network may vary, the assumption is made that, at any time, any two nodes in the network can communicate temporaneoulsy through one-hop or multi-hop transmissions. Several implementations of well-mastered routing algorithms such as OLSR [START_REF] Clausen | Optimized Link-State Routing Protocol (OLSR)[END_REF] or AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] are now available. In this context, implementing a middleware support for service-oriented applications poses problems essentially in the design of the discovery phase: no centralized directory can be implemented easily because there is no fully stable node to host this directory, and given the fact that global message diffusion is prohibitive in terms of network load, network-wide discovery is an issue. Nevertheless, the invocation phase does not generally raise particular difficulties as routing provides the ability to perform multi-hop transmissions between the client and the provider.

In this paper we address a particular class of MANETs we will refer to as disconnected MANETs. Disconnected MANETs show a low density and/or a high mobility of nodes and do not guarantee end-to-end connectivity. Because of their mobility, their limited radio-range and their volatility, the devices in such networks form so-called communication "islands" whose topology evolves continuously. Figure 1 illustrates a snapshot of such a disconnected MANETs: nodes represent individuals that can move inside buildings and pass from one building to another via fixed paths. Temporaneous communication is impossible between distinct islands. Moreover, an inactive node does not communicate. As a consequence, routing techniques designed for fully connected MANETs cannot be used. When it comes to apply the service-oriented approach, issues concerning service discovery are similar to those found when targeting connected MANETs. On the other hand, service invocation is not as straightforward: new means must be found to transfer the invocation request from the client to the provider and ensure that the response arrives back to the client, even if the provider does not reside in the same communication island as the client.

Our overall objective is to build a service platform that will support the execution of service-oriented applications in disconnected MANETs. To our knowledge, this specific issue has not bean studied as such in other previous research work.

The key idea of our proposal is to base the network-wide service provision on opportunistic content-based communication. Communication is said opportunistic because message forwarding is performed when a node gets the chance to encounter -in its radio-range-another node ready to relay the message. As in the disruption-tolerant networking approach proned by the DTNRG 1 , a message can be temporarily stored in a node before being forwarded to other nodes. This store-carry-and-forward form of communication allows a message to disseminate in the network despite its fragmentation, thanks to the mobility of the nodes, as devices can carry messages when moving from an island to another. Communication is content-based because a node is willing to relay a message according to the content of this message, making the flow of information interest-driven rather than destination-driven [START_REF] Carzaniga | Content-based Networking: A New Communication Infrastructure[END_REF]. The paradigm associated with this communication scheme is that of content-based publish/subscribe [START_REF] Patrick | The Many Faces of Publish/Subscribe[END_REF]. A node publishes a message network-wide, and this message is eventually consumed by the nodes that have subscribed for some form of content that turns out to be present in the message.

We chose to exploit this kind of content-based publishsubscribe for the two phases of service provision. Indeed content-based publish/subscribe is well adapted to service discovery insofar as a fully distributed service directory is prefered to a centralized one. Providers publish the description of the services they propose (In our case this publication is performed network-wide). Service clients subscribes for descriptors that match their needs to finally learn the existence of some services they are interested in. As far as service invocation is concerned, it must cope with the fact that the reachability of the devices is unpredictable due to the fragmentation of the disconnected MANETs. So replacing destination-based communication (in which senders specify the address of the receiver in messages) by content-based publish/subscribe is likely to be beneficial. Moreover, this eases the capacity of exploiting the fact that some services may be proposed by more than one provider in the network, thus enhancing the probability for a client to see its invocation request rapidly answered.

The remaining of this paper is organized as follows. An outline of the main features of our service middleware for disconnected MANETs is detailed in Section II. We namely describe in this section the lower layer of the platform that serves as a communication support and the part of the upper layer that implements service discovery. In Section III are detailed the different mechanisms we devised for service invocation. Section IV presents simulation results of the middleware's performance. The paper ends with related work in Section V and a conclusion in Section VI.

II. OVERVIEW OF THE PLATFORM

The service platform we designed is structured in two main layers. The first layer is a high-level service layer that is in charge of all service-oriented processing, enabling discovery and invocation interactions between clients and providers. The second layer is a communication layer that provides means to disseminate messages in the entire network, through a publish/subscribe interface. We sketch out in the remainder of this section the communication layer and the discovery mechanisms implemented in the service layer. Little detail will be presented on service discovery as it can be viewed as a "natural" extension of the publish/subscribe functionality. On the other hand, the invocation implementation will be more precisely described in Section III.

A. Opportunistic Content-based Communication

The lower part of our middleware consists in a communication support adapted to disconnected MANETs. It ensures a network-wide content-driven dissemination of information, despite the fragmentation of the network into isolated communication islands. It implements a model that manipulates structured pieces of information we referred to as "documents". A document is composed of two parts: its header, and its content. The header can be perceived as a collection of attributes, which can provide any kind of information about the corresponding document, such as its origin, its topic, a list of keywords, the type of its content, etc. Some storage capacity in each node is dedicated to a local cache of documents, so this node can serve as a mobile carrier for these documents while moving in the network. The dissemination model is not mere flooding. Indeed, each node in the network is associated an "interest profile", that determines the kind of information it is interested in, and thus implicitly the kinds of documents for which it is willing to serve as a mobile carrier. Therefore, uninterested nodes do not participate in the dissemination. A gossip-like communication protocol orchestrates interactions between neighboring nodes, allowing them to exchange documents according to their respective interest profiles. Interaction between mobile nodes relies on a simple scheme, whereby each node periodically broadcasts its own interest profile and a catalogue of the document headers that are currently available in its local cache. When a node discovers that one of its neighbors can provide a document it is interested in (that is, a document header that matches its own interest profile and that is not already available in its own cache), it can request a copy of this document from this neighbor. Upon receiving one or several requests for a particular document from its neighbors, the owner of this document broadcasts it on the wireless medium, so it can be received by all requesters simultaneously. Transient contacts between mobile nodes are thus exploited opportunistically for exchanging documents between these nodes, based on their respective interest profiles, and based on the documents they can provide each other on demand. The protocol is designed so as to maximize the document delivery ratio while remaining very frugal as far as the number and the volume of messages are concerned. Further information about the protocol can be found in [START_REF] Haillot | A Protocol for Content-Based Communication in Disconnected Mobile Ad Hoc Networks[END_REF].

B. Service Discovery

The service discovery implemented in our platform directly leverages on the content-based communication facilities described above. No global service directory is maintained. Instead, by exploiting the content-based publish/subscribe paradigm, we resort to a peer to peer approach in which each provider proactively advertises its services by way of publication and clients are informed of the existence of the services they need through subscriptions.

The service discovery process begins with the description of services by the provider, using all the information needed by potential clients to select the appropriate service. A service descriptor is a document that starts with a header built from a number of freely chosen couples attribute/value that describe the non-functional characteristics of the service (including QoS or semantic information such as a category or a required security level for example). The functional interface of the service is then given in WSDL so that the client can formulate its invocation requests.

A directory module gathers all the descriptors of the services proposed by the node (if it plays the role of a provider). These descriptors are published in the network, so they disseminate until they eventually reach client nodes. The directory module maintains also a list of learned distant descriptors. Indeed, on the client side, another document called service pattern must be created to convey the wishes of a client hoping to discover a suitable service. The service pattern contains components similar to those of the service descriptor, with the possibility to include wildcards and expressions on attribute values. All the service patterns built by a client serve as subscriptions in the publish/subscribe module, and therefore form the interest profile managed by the communication layer. The subscriptions enable a content-based matching process between the client's preferences expressed in the patterns and the descriptors that are disseminated in the network. If a match is made by the publish/subscribe module, the received descriptor is passed up to the directory for service-level caching. The client can now select the descriptor cached in the directory and formulate its requests accordingly.

III. SERVICE INVOCATION A. Principle

Once a client has discovered a service, it should be able to invoke this service. More precisely, the objective for the client is to send a request to a provider of the service, and to eventually receive a response computed by this provider. In the case of stateless services -which do not require memorization of the state of the conversation between the client and the providerthe client is most of the time only interested in the response to its request without concern on which provider has processed its request.

Content-based Invocation: In our platform, an invocation request is therefore not addressed to a particular provider but contains only the description of the wanted service. We use the publish/subscribe facility for implementing these contentbased invocations. The client formulates a request that includes a reduced version of the service description and publishes it in the network. Providers subscribe for any request matching the reduced version of the descriptors of the service they provide. Therefore a request for a service will eventually reach all the "compatible" providers. The main objective of this approach is to increase the probability for an invocation request to be (rapidly) answered, despite of the lack of connectivity inherent in disconnected MANETs. The provider's response is transferred back to the client also thanks to the publish/subscribe mechanism. The published response message contains a destination attribute, and clients subscribe for messages with a destination attribute matching their own identity. The request and the response messages are composed of a header containing a list of valued attributes and a payload consisting in a SOAP document describing respectively the method call and its return value (cf. Figure 2).

Invocation Deadline: Invocations are supposed to be to some extent tolerant to the communication delays induced by the very nature of disconnected network environments. The lifetime of an invocation is set by the client through a deadline property included in the client invocation request and also in the corresponding responses computed by the providers. The communication layer interprets this deadline as an order to no longer propagate the concerned messages: out of date requests and responses are deleted from communication caches and, consequently, are no longer relayed. The deadline property should be set to the minimum of the two following deadlines: (1) an application-related deadline: the application needs to receive the response before a certain date in order to perform other processing ; (2) a mobility-related deadline: the mobile node knows that it will be leaving its current network environment at a certain time, hence it can fix the deadline accordingly.

Response Management Policy: Addressing a service instead of a unique provider increases the reactivity of the system but also possibly generates multiple responses for a single invocation request. We consider two policies for managing this multiplicity. In a first policy (called "multiple") all the responses to a client request are delivered to this client. Indeed, there are situations in which a client could see it as an advantage. Consider for example a client using a service designed for translating an English sentence into French. Multiple responses can be useful to an end-user who can choose the best answer. Similarly, it could be useful that a call to a temperature service in a sensor network let multiple responses reach the client which would average the received values. On the contrary, in the case only one response is useful, we apply a "first" policy, in which only the first received response is delivered to the client whereas the following are discarded. A train schedule information service for example-allowing requests such as 'at what time are the departures to Paris between 12:00 and 18:00'is normally invoked with a "first" policy for any extra response received after the first one is obviously redundant. The response management policy is chosen by the client and specified in each invocation request.

B. Network healing: Redundant Response and Request Reduction

Benefiting from the fact that several providers are allowed to answer a single invocation request incurs an network extra cost in the case only one response is expected by the client (i.e. when the response management policy is set to "first"): the redundant responses will continue to propagate until their deadline is reached, consuming network bandwidth and storage capacity in the relay nodes. We devised mechanisms for reducing the number of redundant responses (and useless relayed requests) in order to minimize this extra cost. These mechanisms will be referred to as Redundant Response and Request Reduction (R4) in the remainder of this paper. It must be noticed that traditional techniques that consist in performing some form of distributed election among all the providers to ensure a unique response is not applicable because the set of providers is not known a priori and the absence of full connectivity of the network precludes learning its composition in a reasonable time. Our objective is more realistic and so less ambitious: it will not guarantee that only one response reaches the client node but rather tries to cancel the propagation of redundant messages.

Reactive Cancellation: The first R4 technique, that we call "Reactive Cancellation", is always applied. A provider subscribes for messages holding responses to requests it could himself respond to. When a provider P1 receives such response issued by another provider P2, and if P1 has not yet himself answered the request, it gives up attempting to answer the request and rather starts to relay the response of P2. If P1 had already answered the request, it compares the issued date of the response of P2 and the one of its own response and cancels the more recent one (i.e. it stops participating in the dissemination of the more recent response by removing it from Figure 3. Examples of healing control messages its communication cache). Moreover, any provider answering a request also cancels this request. It is indeed not useful to continue propagating the request as it would anyway travel with the corresponding response to the other providers, and the treatment of the response described above makes the request obviously redundant. Reactive Cancellation is clearly always profitable in terms of reduction of the number of transmitted messages (no extra messages are added) and it does not delay the arrival of the first response at the client.

Client-initiated Cancellation: The second R4 technique, called "Client-initiated Cancellation", is more intuitive. When a client has received its first answer, it creates and starts to disseminate a control message (of type CureAll) that includes the request id and its deadline. The role of this message is to inform all the other nodes that they should cancel all the requests and the corresponding responses until the deadline is reached. A large number of nodes, if not all, are supposed to subscribe for control messages of this type in order to ensure their rapid dissemination. As extra messages are transmitted, this tends to increase the network load but it is worth noticing that control messages have a very small size so the elimination of pending requests and responses-whose size can be orders of magnitude larger-compensate in most cases for this augmentation. As in some particular network conditions-that can be hardly modeled but almost never encountered in practice-this healing technique may be not profitable, it is not systematically applied but only when a healing attribute containing 'client' is present in the request header.

Provider-initiated Cancellation: The third R4 technique, the "Provider-initiated Cancellation", is a form of combination of the two previous ones. It consists in starting the dissemination of cancellation messages by the providers before a response is known to have reached the client. A provider answering a request creates and starts disseminating a control message of type CureOthers, similar to a CurAll message but that also includes the identity P of the provider. This message is a command to cancel all the instances of the specified request as well as all the corresponding responses but the one issued by P. A network node reacts only to the first CureOther message it receives for a given request, the subsequent ones are simply discarded. A CureOther message is useful only if it is relayed by more nodes than the providers of the concerned service (again this type of control message should be relayed by almost all the nodes). The objective is that a CureOther message issued by a provider P reaches the other providers quicker that the response computed by P, and consequently eliminates more redundant messages. However, in unfavorable network conditions, it may happen that a CureOther message reaches a provider which would have otherwise issued a response that would have been the first one to arrive at the client. Thus, this healing technique may theoretically delay the arrival of the response to the client. Experiments we conducted tend to show that this delay is negligible whereas the gain in redundant message cancellation is significant (see section IV). The provider-initiated Cancellation is applied when the healing attribute of the request header contains 'provider'.

C. Destination-based Invocation

If we consider that, in general, a client wants to use a service independently of its provider, we reckon with situations in which a specific provider is expected to be addressed when transferring the invocation request. This can occur because a provider is known to be the only one to ensure a certain quality of service or because of the very nature of the service (For example a service providing refreshed images of a given geographical spot is likely to be implemented on a single provider located in this spot.). In our platform, this is viewed as a particular case of the content-based approach described above, as the request can contain a destination attribute specified by the client to identify the wanted provider. Providers do not respond to requests that contain such an attribute if its value does not match their own identity.

In the case of destination-based invocations, the Providerinitiated Cancellation described above is (optionally) performed: as soon as the provider receives the request, it disseminates a control message that will cancel this request, for this request will be of no use elsewhere.

D. Stateful Invocations

Stateful services require that the state of the conversation between a client and a single provider be maintained during a period of time. A sequence of invocations takes place in a session, whose state is generally handled by the provider. In the kind of environment we consider, a session cannot be considered as reliable. A session loss occurs in case the provider goes down or remains unreachable for too long a period of time. We have adapted solutions for session recovery sometimes implemented in connected MANETs. The general idea is to let the session be managed by the client itself. The session state information is returned back to the client with every response, and is carried out by this client so that it can find another provider in case the original one is unreachable. The content-based invocation scheme described above allowed us to perform such a session management simply but efficiently. When a client wants to use a session, it issues an initial invocation request holding a 'session' attribute. This request is disseminated over the network, and can be answered potentially by several providers. When the first response (issued by a provider P) reaches the client, the session is considered opened with P from the client point of view, and subsequents requests in the session are addressed to P (with a destination attribute set to P). The state information maintained by P is appended to each response. Any provider is supposed to be able to exploit this information to re-establish on demand a consistent conversational state.

The session is considered broken when the last request deadline has passed. The client recovers the session by re-issuing this request but this time without any destination attribute, as it did with the initial session request. This request contains the state information possessed by the client so the session can be resumed with a new compatible provider. Because any compatible provider in the network can be used for session recovery (and given the fact that the first to respond will be chosen), this mechanism is efficient in terms of the time taken to re-establish the session.

IV. EVALUATION

The service platform described in this paper has been fully implemented in Java and a number of experiments have been conducted in networks composed of a few devices. In order to assess the performance of our approach in larger configurations, we interfaced the service platform with the MADHOC simulator [START_REF] Hogie | The MADHOC simulator[END_REF]. Contrary to more popular wireless network simulator, Madhoc allows us to run the actual code of our platform, hence taking into account not only algorithmic issues but all the implementation choices we made.

A. Simulation experiments

Network environments present different topologies and mobility behaviors that directly influence the quality of the service provision. We strove to adopt an as realistic as possible an environment that is intended to model an urban area with buildings and road mobility restrictions. We considered an area of 500×900 m 2 in which 100 individuals can stay temporarily in one of the four buildings, and take roads to go from one building to another at variable human walking speeds. At any time an individual may stop for a random period of time (between 1 and 6 minutes). Nodes in the network represent users equipped with wireless handheld devices that are switched on and off in a random manner. Nodes have different wireless ranges whether they are indoor (20 m) or outdoor (50 m). A node has affinities with some buildings and is not capable of accessing all the environment areas during a simulation run.

On each node of the network is deployed our service platform. One of the nodes plays the role of a service client that tries to use only one type of service. The service is proposed by a variable number of provider nodes. The remaining nodes are neither providers nor clients but are used as simple message relays. In an environment of N nodes, containing p provider nodes, we call r = (100 * p / N) the percentage of service replication in the environment. In the scenario we studied in the simulation, the client discovers the service once. Then, it performs a succession of invocation requests all along the simulation period. We focus here on the evaluation of the invocation phase.

Two types of measurement are performed. Our first objective is to estimate the client satisfaction in terms of delay (the delay between the time at which the client publishes its invocation request and the time at which it receives its response). Our

B. Exploitation of service replication

The content-based approach we followed is intended to accelerate the invocation process when several providers propose the service. Figure 4 shows, for several service replication rates, a comparison of the invocation satisfaction delay obtained when (a) content-based invocation requests can reach any compatible provider and the client exploits the first received response and (b) when the invocation requests are sent with destinationbased messages, to a pre-discovered provider. Each curve plots the cumulative distribution of the percentage of successful invocations against the measured average delay. As an example, in figure 4-(a), we see that around 70% of the invocations are completed in less than 10 minutes when the service replication is of 5% (that is, when the service is provided by 5 of the 100 nodes).

The results show that the use of content-based invocation effectively takes advantage of service replication: the more the percentage of replication the quicker the curves reaches high values, whereas replication has little effect when destinationbased invocations are used. The curves in figure 4-(b) show for example that, when considering a percentage of 80% of the invocations completed, the satisfaction delay passes from 24 minutes with no replication to 20 minutes with 30% replication (compared to a change from 24 to 3 minutes when using content-based invocations in the same conditions). Moreover, it is worth noticing that the gain brought about by contentbased invocations is significant even for a low percentage of service replication.

In the remaining of the presented results, we will consider only one value for the service replication, fixing it at a 10%. A low value has been chosen, knowing that the actual replication rate could vary a lot according to the nature of the application services.

C. Cost of redundant response reduction

Provider replication increases the network load by adding extra full load response messages. That is why we implemented in our platform healing techniques in order to eliminate as much as possible unneeded messages. Here we show the effectiveness of the three R4 techniques described in Section III-B, through their impact on the number of messages sent in the network as well as on the amount of data transferred. We also show that the healing does not influence the satisfaction of clients.

Figure 5 shows the cumulative distribution of the number of responses sent by the providers against time when applying the R4 techniques, namely the Reactive Cancellation, Clientinitiated Cancellation and Provider-initiated Cancellation. A reference curve has been added that gives the results obtained without any healing (by removing the code of the Reactive Cancellation that is normally systematically active). For the scenario considered, the number of sent responses is drastically reduced by all the three techniques (by a factor of up to 4.7), even by those which are not always profitable in theory. Interestingly, although the Provider-initiated Cancellation may When considering the network load, the impact of network healing is even more important. Extra messages are added but they have a small footprint and they allow saving requests and responses (which may be of relatively large size). In practice, the volume of the request and responses saved can largely compensate the volume of extra control messages. This is confirmed by the results given in Figure 6. This figure plots the cumulative network load sent by all the nodes into the network medium when no healing is applied as well as when the three R4 techniques we presented are used together. The network load is divided in two values: the cumulative useful payload (i.e. the requests and responses), and the cumulative size of control messages (at the service and the communication level, including extra control messages due to healing). We considered an average size of 26 kB for requests and responses. As expected, the amount of control data slightly increases when the healing is activated, but this extra cost is very small compared to the amount of data that is required for redundant requests and responses when no healing is applied: for the entire experiment, 27 MB of control messages are added but 142 MB of useful payload are saved.

D. Session recovery

We compared the efficiency of our session discovery mechanism based on content-based invocation to a more classic approach used in MANETS. In this latter approach, communication can only take place inside an island, using multi-hop transmissions that exploit a routing algorithm. We measured the time taken for session recovery in a simulated scenario where a client tries to maintain a session with a service provider, within which it periodically sends invocation requests with a 5-minute timeout (The session is considered broken if the response has not arrived 5 minutes after the request is sent.). Each of the providers are randomly turned off and back on 5 times during a simulation run.

In the routed scheme, the client iterates on the following steps: (1) it discovers a list of providers that propose the service it wants by broadcasting a discovery request in its entire communication island and by waiting for a discovery response ;

(2) it opens a session with the first provider that responds ; (3) it performs a sequence of invocations to the chosen provider until the session is broken. The scenario with our session recovery scheme is simpler as the discovery phase has not to be repeated: after having discovered the existence of the wanted service, the client iterates on the following steps: (1) it performs a first content-based invocation, opening a session with the first provider that responds ; (2) it performs a sequence of destination-based invocations to this provider until the session is broken.

Figure 7 shows the cumulative distribution of the percentage of session recovery in the two schemes. Our session recovery scheme clearly outperforms the routed scheme. For example, with our approach, 60% of the sessions are recovered in less than 20 minutes whereas only 25% of the sessions are recovered in less that this same duration with the routed scheme. Two main reasons explains it: the discovery phase is performed only once, and our communication method is not limited to the communication island so it allows the client to reach any provider in the network when trying to re-establish a session.

V. RELATED WORK

A number of research works are concerned with communication in disconnected MANETs, mainly with the objective of providing destination-based communication [START_REF] Zhang | Routing in Intermittently Connected Mobile Ad Hoc Networks and Delay Tolerant Networks: Overview and Challenges[END_REF], [START_REF] Pelusi | Opportunistic Networking: Data Forwarding in Disconnected Mobile Ad Hoc Networks[END_REF] and sometimes proposing content-based approaches [START_REF] Costa | Adaptive Content-based Routing for Delay-tolerant Mobile Ad Hoc Networks[END_REF]. A noticeable contribution in this area has been made in the European Haggle project [START_REF]Haggle Project[END_REF]. All of these works however focus on communication issues and do not address the problems of the design and the implementation of a service platform targeting disconnected MANETs. On the other hand service-oriented programming in pervasive environments has been the object of many research activities. Most of them primarily focus on service discovery protocols using traditional centralized service directories over infrastructure-based (LAN) or single-hop wireless networks ( [START_REF] Zhu | Service Discovery in Pervasive Computing Environments[END_REF] presents a survey of the main protocols).

Recently, the characteristics of MANETs (dynamicity, low resources, unreliable transmissions) have been taken into account, With the development of specific discovery protocols, as part of the routing layer [START_REF] Chakraborty | Integrating Service Discovery with Routing and Session Management for Ad-hoc Networks[END_REF], [START_REF] Engelstad | Service Discovery Architectures for On-Demand Ad Hoc Networks[END_REF] or as part of the service layer with no dependency on routing [START_REF] Helal | Konark : Service Discovery and Delivery Protocol for Ad-hoc Networks[END_REF]. In these protocols, communications are still considered achievable and to some extent sustainable (routes between hosts can always be established). Konark [START_REF] Helal | Konark : Service Discovery and Delivery Protocol for Ad-hoc Networks[END_REF] uses a distributed multi-hop advertisement/discovery scheme but relies on a local multicast and implements connected invocations that are not suitable for disconnected environments. Other efforts try to create a virtual higher-level network in MANETs where some selected nodes are assigned special functionalities. Some of them implement semi-centralized directories for discovery [START_REF] Sailhan | Scalable Service Discovery for MANET[END_REF] where each interconnected network (small connected network island) has one directory, while others assign network service brokers [START_REF] Nedos | Service*: Distributed Service Advertisement for Multi-Service, Multi-Hop MANET Environments[END_REF] or create network backbones [START_REF] Kozat | Network Layer Support for Service Discovery in Mobile Ad Hoc Networks[END_REF]. Our prototype does not assume any viable interconnections so each host is responsible for its own service repository. In addition, we do not use overlay network structures nor maintain discovery routes. Other solutions propose session management over routed MANETs. GSR-S [START_REF] Chakraborty | Integrating Service Discovery with Routing and Session Management for Ad-hoc Networks[END_REF] enables group-based service discovery using discovery requests and advertisements, and reuses the paths of discovery to also handle data transmission for routing invocations with session failure management. "Follow-me" sessions [START_REF] Handorean | Context Aware Session Management for Services in Ad Hoc Networks[END_REF] are built on the same concept of interchangeably invoking compatible providers in a MANET. A form of content-based addressing is used for maintaining opened sessions but the focus is put on server code migration rather than on the support of a possible fragmentation of the network.

VI. CONCLUSION

We presented in this paper the outline of a service middleware platform that specifically targets disconnected MANETs. The originality of our approach resides in the fact that we build service-level facilities on top of a communication layer that provides network-wide dissemination of messages based on content-based and opportunistic communication. This communication layer is used through a publish/subscribe interface not only for service discovery but also for service invocation.

We described the implementation of a form of content-based invocation that can benefit from the potential multiplicity of providers of a given service in the network. Several compatible providers can reply to an invocation request issued by a client, enhancing the probability for this request to be rapidly answered, which can prove crucial in a context where frequent contacts between clients and providers are not guaranteed. As exploiting multiples providers generates redundant responses, we proposed several healing techniques to compensate the extra cost in terms of network load. The approach is applied for the invocation of stateless services and is also used for session recovery when using stateful services.

Simulations experiments involving the real code of the platform have been conducted. The simulation conditions were as realistic as possible, modeling pedestrians in an urban environment. Of course the delays observed for service invocation are directly correlated to the mobility of the network nodes.

As we rely on a store-carry-and-forward approach for message dissemination, some messages need to be physically transported, at human speed. However, simulation results namely show that the multiplicity of compatible providers is effectively exploited as the satisfaction delays perceived by the clients can be drastically reduced even with a relatively low percentage of replication of the service providers. Moreover, as far as network load is concerned, the implemented healing techniques proved efficient: the number of redundant messages can be significantly decreased while keeping the satisfaction ratio at a high value.

Figure 1 .

 1 Figure 1. Illustration of a disconnected MANET

Figure 2 .

 2 Figure 2. Examples of invocation request and response messages

Figure

  Figure of service replication on invocation satisfaction

Figure 5 .

 5 Figure 5. Effect of the three R4 techniques on the suppression of redundant responsestheoretically delay useful responses and even prevent them from arriving at the client, the results for the considered scenario do not reveal such a loss. This is illustrated by the two

Figure 6 .

 6 Figure 6. Cumulative load sent into the network medium

7 .

 7 Session management.

Delay Tolerant Networking Research Group, http://www.dtnrg.org