Cédric Lopez
email: lopez@lirmm.fr

Violaine Prince
email: prince@lirmm.fr

Mathieu Roche
email: mroche@lirmm.fr

How to Title Electronic Documents Using Text Mining Techniques

Keywords: Automatic titling, Text Mining, Information Retrieval, Morphosyntactic Characteristics, Noun Phrases;

Automatic titling of text is a task allowing to determine a well formed word group able to represent the text in a relevant way. The main difficulty of this task is to determine a title having morpho-syntactic characteristics close to titles written by concerned people. Our approach has to be relevant for all type of text (e.g. news, emails, fora, and so forth). Our automatic titling method is developed in four stages: Corpus acquisition, candidate sentences determination for titling, noun phrase extraction in the candidate sentences, and finally, selecting a particular noun phrase to play the role of the text title (ChTITRES approach). Evaluation shows that titles determined by our methods are relevant.

I. Introduction

A title definition met in any dictionary is 'word, expression, sentence, etc., serving to indicate a paper, one of its parts [...], to give its subject.' So it seems that a title role can be assumed by a well formed word group, an expression, a topic or a simple word, related to the text content, in one way or another. It ensues that some groups of well formed words can be convenient for a title, which means that a text might get several possible titles. A title varies in length (i.e. number of words), form and local focus. So, the human judgement on a title quality will always be subjective and several different titles might be judged as relevant to a given content. This paper deals with an automatic approach providing a title to a document, which meets the different characteristics of human issued titles. So, when a title is absent, for instance in e-mails without objects, the described method enables the user to save time by informing him/her about the content in a single glance. In addition, it is designed to meet at least one of the criteria of the standard W3C. Indeed, titling web pages is one of key fields of the web page accessibility, such as defined by associations for the disabled. The goal is to enhance the page readability. Moreover, a relevant title is an important issue for the webmaster improving the indexation of web pages.

Let us note that titling is not a task to be confused with automatic summarization, text compression, and indexation, although it has several common points with them. This will be detailed in the 'related work' section.

The originality of this method is that it relies on the morphosyntactic characteristics of existing titles to automatically generate a document heading. So the first step is to determine the nature of the morphosyntactic structure in titles and check whether it depends on the text style (e.g. e-mails, scientific papers, news) or if it is style independent.

A basic hunch is that a key term of a text can be used as its title. But studies have shown that very few titles are restricted to a single term. Besides, the reformulation of relevant elements of the text is still a quite difficult task, which will not be addressed in the present work.

The related work in automatic titling (section II) and our own corpus study (section III have stressed out the following hypothesis: It seems that the first sentences of a document, most of the time regardless of its style (except maybe for novels, but this is not the mainstream of web pages), tend to contain the relevant information for a possible title. Our ChTITRES approach (section IV) extracts crucial knowledge in these selected sentences and provide a title.

An evaluation by human judgement, obtained on real data is presented in section V.

II. Related Work

Titling is a process aiming at relevantly representing the contents of documents. It might use metaphors, humor or emphasis, thus separating a titling task from a summarization process, proving the importance of rhetorical status in both tasks [START_REF] Teufel | Sentence extraction and rhetorical classification for flexible abstracts[END_REF].

Titles have been studied as textual objects focusing on fonts, sizes, colors, … [START_REF] Ho-Dac | Sur la fonction discursive des titres[END_REF]. Also, since a title suggests an outline of the associated document topic, it is endowed with a semantic contents that has three functions: Interest and captivate the reader, inform the reader, introduce the topic of the text.

It was noticed that elements appearing in the title are often present in the body of the text [START_REF] Zajic | Automatic headline generation for newspaper stories[END_REF]. [START_REF] Baxendale | Man-made index for technical literature -an experiment[END_REF] has showed that the first and last sentences of paragraphs are considered important. The recent work of [START_REF] Belhaoues | Titrage automatique de pages web[END_REF], [START_REF] Jacques | Titres et structuration des documents[END_REF], [START_REF] Zhou | Headline summarization at ISI[END_REF] supports this idea and shows that the covering rate of those words present in titles, is very high in the first sentences of a text. [START_REF] Vinet | L"aspet et la copule vide dans la grammaire des titres[END_REF] notices that very often, a definition is given in the first sentences following the title, especially in informative or academic texts, meaning that relevant words tend to appear in the beginning since definitions introduce the text subject while exhibiting its complex terms. The latter indicate relevant semantic entities and constitute a better representation of the semantic document contents [START_REF] Mitra | An analysis of statistical and syntactic phrases[END_REF].

A title is not exactly the smallest possible abstract. While a summary, the most condensed form of a text, has to give an outline of the text contents that respects the text structure, a title indicates the treated subject in the text without revealing all the content [START_REF] Wang | Multi-document summarization using sentence-based topic models[END_REF]. Summarization might rely on titles, such as in [START_REF] Goldsteiny | Summarizing text documents: Sentence selection and evaluation metrics[END_REF] where titles are systematically used to create the summary. This method stresses out the title role, but also the necessity to know the title to obtain a good summary.

Text compression could be interesting for titling if a strong compression could be undertaken, resulting in a single relevant word group. Compression texts methods (e.g. [START_REF] Yousfi-Monod | Sentence compression as a step in summarization or an alternative path in text shortening[END_REF]) could be used to choose a word group obeying to titles constraints. However, one has to largely prune compression results to select the relevant group [START_REF] Teufel | Sentence extraction and rhetorical classification for flexible abstracts[END_REF].

A title is not an index: A title does not necessarily contain key words (and indexes are key words), and might present a partial or total reformulation of the text (what an index is not).

Finally, a title is a full entity, has its own functions, and titling has to be sharply distinguished from summarizing and indexing.

A rapid survey of existing documents helps to fathom some of title characteristics such as length, and nature of part-of-speech items often used. The first step is to determine the text type, i.e., its category (scientific article, newspaper article, e-mail, forum question or comment, ...), and to examine a possible relationship between a text type, and its title characteristics. Therefore, next section is devoted to this study.

III. Text Types Identification: A Step Prior To Titling

This section has for objective to identify text types according to title types. The statistical analyses enable to distinguish two groups of text.

A. Type Identification Protocol

The statistical analysis of titles is an essential preliminary stage that helps to understand which kind of title one has to assign to a given type of texts. Common sense leads us to suppose that the form of the title differs according to the aimed reader (e.g. children, adults, every public) or to the semantic contents of the text [START_REF] Van Halteren | Writing style recognition and sentence extraction[END_REF]. To ascertain the impact of text type on title form (and length) we have selected five categories of documents: Wikipedia articles (mechanics, computing, biology, biographies, vocabulary, objects, etc.), scientific papers (e.g. biology, physics, linguistics, computer science, etc.), news (the French newspaper 'Le Monde', for the year 1994, which belongs to a standard reference corpus, thus matching the English Brown Collins Corpus), e-mails, research mailing lists, and fora.

Since French was the main working language (we have also a project to shift to other European languages), we selected 100 French texts in each category.

Two items were chosen for analysis: What POS (part-of-speech) tags were the most frequent in titles, and how many words contained in the title were also frequent in the text. The POS tagging was performed by TreeTagger [START_REF] Schmid | Probabilistic part-of-speech tagging using decision trees[END_REF]. It allowed to know the titles composition according to the types of texts. The number of words present in both texts body and titles inform us about the place of the relevant information in the text and indicates if titling is possible from text chunks.

Next section tackles the morphosyntactic characteristics of titles according to the types of considered texts.

B. Analysis and Discussion

The results (see Table 1) show that the noun is the most used POS: Nouns are present in almost 90% in the titles of all categories. Within a title, the noun represents approximately 31% of the terms.

Named entities (NE) appear in 45% of the titles (all categories merged). If the titles of Wikipedia articles which use NE only in 7% of the cases are not taken into account, the average of presence of NE in titles is 60%. Its presence in a title enables to specify the sense evoked by the other terms. 44% of the retained titles contain adjectives. The main function of an adjective is to appoint in the noun to express a quality (qualificative adjective). Its strong presence in the titles indicates the same intention as the NE, i.e., specifying the nature of the subject.

Verbs are not as widely spread as nouns, NE and adjectives (or noun phrases (NP) in general). Moreover, it seems that verbs in a title are more representative of the journalistic style and the scientific articles (26%), where titles are long (see Table 1), close to a complete sentence [START_REF] Mitra | An analysis of statistical and syntactic phrases[END_REF], and thus contain verbs, whereas in Wikipedia articles, e-mails, mailing lists, or fora, verbs occur in only 6% of the titles. So this result is the first clue that title POS composition and text type might be related to each other.

Another interesting feature is punctuation. It is present in almost 50% of the scientific articles titles. More precisely, the colon appears in 42% and the question mark in 5%. A more detailed analysis showed that 50% of the scientific titles contain the word and. The strong presence of internal punctuation and coordination marked by conjunction indicates a will of bipartition such as it was described in [START_REF] Ho-Dac | Sur la fonction discursive des titres[END_REF].

The statistics about Wikipedia articles show that their titles are not "natural" (i.e. "formated") and that they deserve a more complex construction. Wikipedia article titles are very short: They only reach an average of three words. They are mainly composed of nouns (text keywords) and adjectives. This can be due to the structure of Wikipedia documents. The text block is cut in sections, having quite the same logic in titling, using 'the object to describe' as a title, and putting its description in the body of the text. In such a case, one should rather consider the title as a simple element, pointed by its description in the body of the article. So, Wikipedia article titles should rather be seen as sole textual signals, to the detriment of units endowed with semantic contents. [START_REF] Ho-Dac | Sur la fonction discursive des titres[END_REF]

C. What Type of Title, for Which Text?

According to the first rapid survey presented above, it seems that titles depend on text types, and the most important clues are the following: The nature of the effort in writing the text body, the presence of a verb in the title. Thus, we have splited the documents into two main groups. The first one (G1) contains those texts, in the titles of which, verbs are rare or absent: Mailing lists, fora, and e-mails. The second group (G2) contains the other texts, whose titles present a more complex syntax (related to longer titles, see Table 1), where verb(s) are more likely to appear. This involves a better representation of the semantic contents according to [START_REF] Mitra | An analysis of statistical and syntactic phrases[END_REF].

In this paper, we will focus on G1 documents, since titling procedures would not be the same in both groups. In this group, the expected titles to produce are noun phrases (if we want to stick to the existing titles characteristics studied in the collected corpus). The issue is then how to determine at least one relevant noun phrase that would be an acceptable title.

IV. The Automatic Titling Approach

Global process of Automatic Titling consists in three crucial steps. This section describes our process illustrated by numerous examples.

A. What Type of Title, for Which Text?

The statistical analysis of titles in the various categories of our corpus led to the design of a global process for automatic titling, composed of the following steps (see Fig. 1):

 Step 0: Corpus Acquisition: Determining the characteristics of the texts to be titled; Described in the previous section.

 Step 1: Candidate Sentence Determination. This part contains the peculiarity of our method. We assume that any text contains at least a few sentences that would provide the relevant sentence for titling. The goal of Step 1 consists in recognizing those sentences. A further investigation will show that, very often, the terms used in the title can be located in the first sentences of the text.



Step 2: Extracting Candidate Noun Phrases for Titling. This step uses syntactical filters relying on the statistical studies previously led. In particular, the length of these filters will be focused on.

 Step 3: Selecting a Title, the ChTITRES Approach. Last, a few candidate noun phrase remain, and they are ranked according to a score, for which we propose several computing procedures.

In the following sections, Steps 1 to 3 are described and illustrated by examples stemming from our program.

B. Candidate Sentences Determination and Extraction

The first elementary step (see Global Process, Stage 1) consists in determining the textual data from which we will build a title. These data have to contain the information necessary for the titling of the document. As said before, [START_REF] Jacques | Titres et structuration des documents[END_REF] showed that the title words can be often found in the first sentences of the text. In a recent study, [START_REF] Belhaoues | Titrage automatique de pages web[END_REF] has concluded that the maximal covering of the words of the title in the text, was obtained by extracting the first seven sentences and both last ones (for the studied corpus, the author obtains a covering rate at 72%).

In our corpus, when selecting the first two sentences, we potentially access 73% of the semantic content of the title.

During our study presented in this paper, we will stick to the first two sentences as a mining field for titling. Other methods we have developed are based on a position function in the document [START_REF] Lopez | Automatic titling of Articles Using Position and Statistical Information[END_REF].

How to Title Electronic Documents Using Text Mining Techniques

Corpus analysis showed that the titles of group G1 documents contain few verbs and are short (between approximately two and six words). Our aim is to extract the most relevant noun phrases in order to provide a title. We shall begin by proposing a list of noun phrases based on their size.

C. Selecting of the Maximal Noun Phrases

The step 2 of our approach begins with the extraction of noun phrase (NP). For that purpose, texts are tagged with TreeTagger, and is inspired from [START_REF] Daille | Study and implementation of combined techniques for automatic extraction of terminology[END_REF] This step process consists in selecting among this list of NP, the most relevant one. A first preselection allows to choose a NP based on its length, similarly to [START_REF] Barker | Using noun phrase heads to extract document keyphrases[END_REF], with lengths equivalent to L max and L max-1 where L max is the longest local candidate1. This technique prevents from pruning interesting candidates too quickly. These candidates are called NP max . Our aim is not to facilitate two words NP, since the results of our statistics indicate that the average size of G1 documents titles is greater than two words.

Among the NP of the previous list, the NP max preset will be:

-a student of FLIN304, -my TP examination, -people in the group, -TP time slots.

If there only one NP max preset, then it is presented as a title. Otherwise, to extract among this preselection the most relevant NP to exploit it as title, two methods are studied: Computing a score according involving each word in the candidate NP, and computing the NP most relevant word score. These two methods will rely on a very popular measure in NLP, the TF-IDF [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF]. This represents the stage 3 of the ChTITRES automatic titling process.

D. Selecting a Title Among the Candidate NP, the ChTitres Approach

Step 3 consists in selecting the most relevant NP for its use as title. In the following sections, we shall use the measure TF-IDF to calculate the score of every NP. This score can be the maximal TF-IDF obtained for a word of the SN (T MAX ) either the sum of the TF-IDF of every word of the NP (T SUM ).

1) T MAX : For each word of the candidate NP, the TF-IDF is calculated. The score for every candidate NP is the maximum TF-IDF of the words of the NP. With this method, discriminant terms are highlighted. For example, in the noun phrase research contribution (NP1) and new reading (NP2), NP1 will be retained, the term contribution being more discriminant than research, new and reading in our corpus.

It is obvious that this method values named entities (NE), these being generally more discriminant than any other type of word in the corpus.

During our study, we shall use this method on the first sentence only (T MAX1 ) either on the first two sentences (T MAX2 ).

2) T SUM : For each word of the candidate NP, the TF-IDF is calculated. The score of every NP candidate is the sum of each term TF-IDF. This method favors long noun phrases. For example, if we have both 'soucis de vibration' (vibration nuisance) (NP3) and 'soucis de vibration avec Saxo' (Saxo vibration nuisance) (NP4) then NP4 will be privileged because it is a superset of NP3.

However, this method still allows to distinguish between noun phrases of the same size: NP2 obtains a better score than NP1 because the sum of the TF-IDF for the terms new and reading is higher than the sum for contribution and research.

The benefit of this method is to extract the noun phrase containing the most information, without worrying about the relevance of its words.

In this paper, we use T SUM1 being the first sentence T SUM score, and T SUM2 , which is the first two sentences scoring.

E. Lexical Selection

Named entities (NE), i.e., words or word groups designating names (such as names of persons, names of organizations or companies, names of places and so forth), can be excellent keywords allowing to quickly encircle the content of the text. For example, in a question answer system, QALC [START_REF] Ferret | Document selection refinement based on linguistic features for QALC, a question answering system[END_REF] uses NE in order to specify the type of the expected answer.

If a NE is located among three first ones NP max , then it favors selecting it as a title. Otherwise, the NP max retained will be the one of higher score with T MAX or T SUM .

V. Experiments

Evaluation of titles is a complex task. Indeed, several relevant titles might be possible for a same text. This section presents the experimental protocol used in order to evaluate our automatic titling process, and discuss the results.

A. Data Description

The experiments have been run on G1 group documents extracted from: the LN mailing list messages, fora, and e-mails. For each of these three categories, ten texts were selected.

Texts are variable in size (i.e. number of words), topics, technicality, and effort of writing.

B. Experimental Protocol

The evaluation has been proposed to ten experts via a web page (see Fig. 2). Thirty titled texts are proposed to the experts, by three groups of ten texts from G1. For every text, eight titles (same titles are not repeated) were suggested among all the titles determined according to the methods T MAX1 , T SUM1 , T MAX2 , and T SUM2 as well as the real title TR. Three other titles (A1; A2; A3) are exposed in a random way from the list of noun phrases extracted among those that were rejected by the process. Comparing the evaluation of rejected NP with selected ones will allow, in particular, the estimation of the selection process accuracy.

For every "candidate" title, the user has to appreciate its relevance to the document contents with the following scale: Very relevant (C1), Relevant (C2), I don"t know (C3), not very relevant (C4), not relevant at all (C5). For each of these C n judgements, a digital value is assigned: -2 for C5, -1 for C4, 0 for C3, +1 for C2 and+2 for C1. The final note obtained for a title is the mean value of the experts given grades. So, the higher the value, the more accurate the NP as a title (see Fig. 3).

C. Results

For every category of text (E-mails, Mailing lists, Fora), the results of evaluation are presented on Table 2. This table contains the average of the values corresponding to notation judgements previously exposed. We compare the automatic titling process results with the values obtained for the real titles.

1) E-mails: The e-mails proposed during this evaluation are personal e-mails, stemming from different persons, from different registers and from more or less looked writing. Titles A1, A2, and A3 correspond to random candidates being maximal NP, but not retained by the score computing methods.

With an average included between -0.55 and -1.44, the results are considered not very relevant (A2, A3) and not relevant (A1). Remember that -2 means 'not relevant at all', and -1 'not very relevant'. So A2 and A3 are a bit better than 'not very relevant'. They tend to be considered as not classifiable by human experts.

The real title TR obtains an average of 0.57, while the T MAX2 method obtains an average of 0.61. The titles determined by this last method are better than the real titles in e-mails. On average, all the methods seem to determine relevant titles. Let us note that the score obtained by the method T SUM1 is rather weak (0.38) compared with the score of the real title (0.57). So, for e-mails, it seems important to take into account first two sentences.

2) LN Mailing Lists: The results show that the real titles are very relevant5. The results of score computing methods indicate that the titles they select are globally relevant. Here, the T MAX methods seem to give better scores than the T SUM ones. T MAX2 returns the most relevant titles for this category of texts. Furthermore, 50% of the titles supplied by T MAX2 are very relevant with an average included between 1.5 and 2.

3) Fora: The evaluation texts, in this category, are extracted from fora randomly met on the Internet (forum of mechanics, numismatics, biology, and so forth). Once again, the titles A1, A2, and A3 are evaluated as irrelevant. Titles of fora can be formatted or not: Texts T7 to T10 belong to formatted fora, where the fora administrators reappointed the messages titles. This explains their real titles good results (1.15). The four score computing techniques results indicate that titling is relevant even if they are rather weak for T MAX2 . T SUM1 obtains here the best result with a score of 0.88. This can be explained by the fact that messages of for a are generally short and contain the main information in the first sentence. It seems that involving additional sentences brings here more noise than relevant information for titling.

For example, a real title is Service at home. The experts considered Service company at home, automatically extracted by our process, as a more relevant title.

D. Discussion

Generally, the four score computing methods determine relevant titles according to the human experts average opinion (see Table 2). The disparity in results can be explained by the fact that experts compare all candidate titles and determine the most relevant one, and then after, assign a judgement to the others. So, even if two titles are very relevant, only one will be privileged by being assigned the label Very relevant, while the other one will get Relevant. The evaluation experiment also shows that it seems better to use T MAX2 as a filtering method in order to title e-mails and mailing lists. The method T SUM1 seems to be more appropriate for fora messages titling. In the Forum category, results indicate that it is better to extract the first sentence, to avoid noise. However, in a general way, the score computing methods taking into account the first two sentences often offer better results (for two categories out of three).

Titling

The four methods enable to extract the most relevant NP max . Titles A1, A2, and A3 are always judged as little relevant (even not relevant at all) while score computing methods determine relevant titles (even very relevant). The titles built by the automatic titling process are thus of good quality, even if they obtain results slightly weaker than the real titles, for two categories on three.

Two remarks are appropriate: 1) real titles get an average of 1.17, all categories merged, which means that they are generally relevant, but not necessarily very relevant. Moreover, deviation is quite high in evaluation when browsing the text titles in a same category. 2) E-mail real titles get rather a low grade from the human judges. This tends to indicate a possible benefit of an automatic method that might build a more relevant title than a "real" one, and is a time saving procedure for an e-mail writer...

VI. Conclusion and Future Work

The quality of automatically computed titles strongly depends on the care brought to the text writing. Nevertheless, the ChTITRES approach proposes relevant titles for the G1 group documents (i.e. e-mails, fora, mailing lists). The results show all the same that improvements can be brought. Even if a part of the performance of this approach depends on Tree Tagger, it seems possible to improve results. As seen here, selection methods scores depend on the text type.

Methods presented in this paper were developed with PHP and the application is available on the following URL: http://www.lirmm.fr/~lopez/. The program (see Fig. 4) is described in [START_REF] Lopez | Text titling application[END_REF].

A combination of methods is contemplated, as a technique more robust to type variation. Naturally, G2 group texts, i.e., newspapers, scientific articles, and encyclopedias texts will be also studied and their titling experimented. However, this group requires a detailed syntactic analysis that we shall lead in our next work. According to our statistics, group G2 document titles must be built by taking into account the more significant presence of verbs, and the peculiarities of text goals. Finally, we plan to develop approaches which build titles by generation methods (e.g. [START_REF] Jin | A new probabilistic model for title generation[END_REF]), consisting of three steps: Generation of candidate titles, Assessments of the coherence of candidate titles, and Contextualisation of the titles through a lexical network.

Figure 1 .

 1 Figure 1. The Four Stages of the Titling Global Approach.

Figure 2 .

 2 Figure 2. Screen of ChTITRES application.

Figure 4 .

 4 Figure 4. Example of an evaluation screen.

Figure 3 .

 3 Figure 3. Scale of Relevance for Titling.

Table 1 .

 1 call this feature a thematic implication. Statistics on the Titles of Chosen Corpora.

	Nature	% N	% NE	% V	% NW
	Scientific art.	97	40	26	9
	Wikipedia art.	87	7	5	3
	Newspapers art.	86	88	25	9
	E-mails	73	53	6	5
	Mailing lists	86	99	5	6
	Forum	92	37	15	4

N: Noun; NE: Named Entity; V: Verb; NW: Number of Words

Table 2 .

 2 Average scores for each score computing methods, as well as real titles (TR) and randomly chosen NP candidates of maximal length (A1, A2, A3), all types of texts merged.

		TR	T SUM1	T MAX1	T SUM2
	E-mails	0.57	0.38	0.46	0.52
	Mailing Lists	1.8	0.28	0.56	0.43
	Forums	1.15	0.88	0.75	0.58
	Avg.	1.17	0.51	0.59	0.51

Author Biographies

Cédric Lopez


Kevin Samyn
email: k.samyn@brgm.fr

Adnand Bitri

Gilles Grandjean

K Samyn

Kévin Samyn

Imaging a near-surface feature using cross-correlation analysis of multi-channel surface wave data

Keywords: surface wave, cross-correlation, shear-wave velocity (Vs)

In this study, we demonstrate that cross-correlation gathers of multi-channel and multi-shot configurations provide accurate estimations of shear wave velocity (VS) perturbations from Rayleigh wave data for the reconstruction of two-dimensional (2D), high-resolution velocity distributions without requiring the systematic calculation of surface wave dispersions, as in the spectral analysis of surface waves (SASW). Data acquisition for cross-correlation analysis is similar to that for a 2D seismic common midpoint reflection survey. The data processing involved is similar to the coda wave interferometry used for seismological data but differs in the sense that the cross-correlation of the original waveform is calculated for active source seismic data. Data processing in cross-correlation analysis consists of the following three steps: First, crosscorrelations are calculated for every trace in each shot gather with the same offset trace as a reference shot to flatten the linearly sloping events of surface waves. A common receiver location stack section can then be obtained, which allows for the assessment of lateral variations in the elastic properties of the medium. Second, the maxima of the time-shifted cross-correlation gathers and the maxima of the shot gathers' envelope traces are picked for different frequencies, and trace values having the same receiver location are averaged to calculate Vs perturbations, as described in the theory of coda wave interferometry. Finally, a 2D Vs profile is reconstructed by applying the lateral Vs perturbation to a homogeneous Vs velocity profile obtained by inversion of the surface wave dispersion of the reference shot gather. Analyses of waveform data from numerical modelling and field observations indicate that this new method is valid and greatly improves the accuracy and resolution of nearsurface imagery using surface waves and reconstructed subsurface velocity distributions compared with a conventional SASW or multi-channel application.

Introduction

The delineation of shear wave velocity (Vs) structures down to a depth of approximately 30 m is of fundamental interest in engineering and environmental problems. P-wave and S-wave (PS) velocity logging has been adopted for this purpose for a number of years. The expense of drilling a borehole and operating a logging tool has led to a demand for more convenient methods for determining shallow surface wave structures. It is well known that the dispersion of the phase velocities of surface waves is mainly determined by the ground structure. The use of surface waves for near-surface delineation has been the subject of many studies in the past decade. For example, the spectral analysis of surface waves (SASW) has been used for the determination of 1D Vs structures down to a depth of 100 m [START_REF] Nazarian | Use of spectral analysis of surface waves method for determination of moduli and thickness of pavement system[END_REF][START_REF] Stokoe | In situ seismic testing with surface wave[END_REF][START_REF] Grandjean | 2M-SASW: inversion of local Rayleigh wave dispersion in laterally heterogeneous subsurfaces: application to Super-Sauze landslide (France)[END_REF]. The majority of the surface wave methods described to date employ a shaker or a vibrator as a wave source and exploit calculated phase differences between two receivers using a simple cross-correlation technique. Park et al., 1998a and[START_REF] Debeglia | Karst investigations using microgravity and MASW; Application to Orléans, France[END_REF] also discuss the feasibility of detecting near-surface features using dynamic linear moveout (dlmo) for surface wave imagery. A multi-channel analysis of surface waves (MASW) has been proposed by several authors [START_REF] Song | Sensitivity of near-surface shear-wave velocity determination from Rayleigh and Love waves[END_REF]Park et al. 1999a;[START_REF] Xia | Estimation of near-surface shear-wave velocity by inversion of Rayleigh waves[END_REF]. This method determines phase velocities directly from multi-channel surface wave data after applying an integral transformation to the frequency-domain waveform data. The integration directly converts time-domain waveform data (time-distance) into an image of phase velocity versus frequency (c-f). [START_REF] Hayashi | CMP cross correlation analysis of multichannel surface wave data[END_REF] show that the accuracy and resolution of (c-f) images can be improved using common mid-point (CMP) cross-correlation analysis of multi-channel surface wave data. The MASW method is more effective than the SASW method because MASW allows the fundamental mode of Rayleigh wave dispersion to be distinguished visually from body waves and from higher modes of the Rayleigh waves. Additionally, the MASW method avoids spatial aliasing, which is a problem in the SASW method [START_REF] Foti | Application of FK analysis of surface waves for geotechnical characterization[END_REF][START_REF] Neducza | Stacking of surface waves[END_REF]. [START_REF] Xia | Resolution of highfrequency Rayleigh-wave data[END_REF] and [START_REF] Miller | Multichannel analysis of surface waves to map bedrock[END_REF] applied the MASW method to continuous-profiling shot records and delineated 2D Vs structures and their resolution to determine phase velocities at low frequencies.

Importantly, Park et al. (1999a) noted that it is essential for the MASW method to use a receiver array that is as long as is practical. However, a longer receiver array can decrease the lateral resolution of a survey because the conventional MASW method provides a velocity model averaged over the total length of the array. We developed a novel method to address this trade-off. Developing an alternative to conventional surface wave methods for the determination of lateral variations in Vs structure required a unique approach based on the multichannel recording of surface waves and a cross-correlation analysis.

Surface wave response to a near-surface feature

A near-surface anomaly is defined here as a component of the near-surface materials that has elastic properties differing significantly from those of the remaining components, which are termed normal zones. The transition from a normal to anomalous zone may be either abrupt or gradual. During a surface waves survey, a near-surface anomaly leaves a signature of its presence in several forms on a multi-channel recording, the most common form being different phase velocities for those frequencies propagating through or near the anomaly; another form consists of differing attenuation characteristics.

In addition to differing phase velocities and attenuation characteristics, an anomaly may reveal its presence in the form of the generation of higher modes [START_REF] Bath | Introduction to seismology[END_REF][START_REF] Gucunski | Instrumentation for SASW testing In: Geotechnical Special Publication[END_REF], or reflected and diffracted [START_REF] Yanovskaya | Surface waves in media with weak lateral inhomogeneity[END_REF][START_REF] Sheu | Effect of reflected waves in SASW testing of pavements[END_REF] surface waves. The generation of these higher modes is closely related to the existence of a low-velocity zone underlain by and overlying high-velocity zones (a zone of velocity inversion) [START_REF] Stokoe | Characterization of geotechnical sites by SASW method[END_REF], and the energy of the higher modes typically becomes more significant at high frequencies (short wavelengths) [START_REF] Tokimatsu | Effects of multiple modes on Rayleigh wave dispersion characteristics[END_REF]. Reflected and diffracted surface waves are generated when the transition from normal to anomalous zones is abrupt. All of these anomaly signature types may appear on a multichannel record when either the source or the receivers are located at or near the surface location of an anomaly.

Theoretically, surface waves cannot penetrate through a void filled with air or fluid because of the lack of shear modulus inside the void. However, considering the retrograde elliptical motion of mass underneath a roll disturbance, the surface waves that penetrate above and below the void with dimensions of elliptical motion that significantly exceed the dimensions of the void may still propagate horizontally but with altered propagation characteristics with respect to attenuation, variations in phase velocity, or both.

Methodology

Principles

To improve the lateral resolution of multichannel surface wave methods, we considered the Vs perturbation relative to a reference shot gather through the cross-correlation of Rayleigh wave shot gather data recorded at different positions along a line. Cross-correlation is a standard method of estimating the degree to which two series are correlated. The cross-correlation function, R(Δt), represents the correlation coefficient between two seismic signals at time t = 0, S(0), and a later time t, S(t). The cross-correlation function can be expressed as follows:

) ( ) ( ) ( ) ( 2 1 0 2 1 m M S S m i S i S t R m M i              (1)
where m is an integer multiple of a time interval, , such that Δt=m (where 0<m<M). S 1 (t) and S 2 (t) are the time-dependant surface wave signals from traces 1 and 2, respectively. Both traces comprise M+1 data points spanning the period from t=0 to t=M . <S 1 > and <S 2 > are the mean intensities of the surface wave signal in traces 1 and 2, respectively.

Herein, we compare the surface wave signals. Our goal is to determine whether the two signals are correlated (i.e., fluctuating in concert) or uncorrelated (fluctuating independently). In modelling the autocorrelation in time, we assume that the correlation of a surface wave signal with itself decays from a perfect On a simplistic level, cross-correlation analysis is coincidence analysis. The cross-correlation function between traces therefore enables a determination of the manner in which the Vs structure varies in the near surface.

Data processing procedure

A cross-correlation analysis of surface waves (CCASW) is applied to each shot gather in the dataset. Data acquisition for the CCASW method is similar to that for a 2D seismic common midpoint reflection survey. The source-receiver geometry is based on the end-on spread, and both the source and the receivers move up along a survey line. The processing for the CCASW is summarised in the following: First, cross-correlations are calculated for every trace in each shot gather along the entire seismic line using the same offset trace of a user-selected reference shot gather from the overall dataset, which is considered to be unperturbed.

The reference location is a presumably normal zone within the survey line. The cross-correlation process allows us to correct for the offset effect and therefore, to flatten the linearly sloping events of surface waves in the same way as a dlmo (Park et al. 1998a, b). All of the common receiver location traces in crosscorrelated shot gathers can then be stacked together. The above procedure achieves the following effects after stacking:

• Frequencies that have the same phase velocity as that at the reference location will have large stacked amplitudes due to constructive interference.

• For those shot gathers obtained at or near the surface location of an anomaly, cross-correlation will result in time-shifted stacked traces or weak amplitudes traces due to destructive interference.

• All of the higher modes will be attenuated through destructive interference due to their different phase velocities.

• All non-planar, body waves will be attenuated due to destructive interference because of their nonlinear occurrence on a multi-channel record or because of wrong velocities used for moveout correction.

• All reflected surface waves will appear as diffractions in the final stack section.

• Random noise will be attenuated.

When the stacked traces are displayed, all of the normal zones will show large amplitudes, and the anomalous zones will be denoted by diffractions, attenuated amplitudes or time-shifted events. Such a stack section is thus a good method to obtain an initial view of the lateral variations in elastic properties along the survey line.

To quantify the observations made on the stack section, we then applied coda wave interferometry to our active source survey, stipulating that a homogeneous relative change in seismic velocity, dv/v, results in a time-shift dt [START_REF] Snieder | Coda wave interferometry for estimating nonlinear behavior in seismic velocity[END_REF][START_REF] Wegler | Fault zone monitoring with passive image interferometry[END_REF]

of: v dv t dt   (2)
For this purpose, the maxima of the cross-correlated gather is then picked to obtain the travel-time perturbation dt, and the maxima of the shot gather's

Numerical modelling

Two numerical tests were performed to evaluate the proposed method. Fig. 1 shows the source-receiver configuration used for data acquisition. Fig. 2 shows the velocity models used for numerical modelling. Both directions of the movingsource observations of surface waves on the survey line were tested. The two models are composed of a homogeneous half-space with Vp=1200 m/s and Vs=600 m/s and a low-velocity, vertical and buried defect with Vp=1000 m/s and Vs=500 m/s. The Seismic Unix (SU) suea2df function [START_REF] Juhlin | Finite-difference elastic wave propagation in 2D heterogeneous transversely isotropic media[END_REF], which is based on a stress-velocity, staggered grid, 2D finite-difference method [START_REF] Levander | Fourth-order finite-difference P-SV seismograms[END_REF][START_REF] Virieux | P-SV wave-propagation in heterogeneous media: velocitystress finite-difference method[END_REF], was used for the waveform calculation.

Synthetic seismic gathers were generated using a zero-phase Ricker wavelet.

The finite difference calculation was performed using 321 and 213 0.5 × 0.5 m cells, respectively, for the x and z axes and 12000 samples with a sample interval of 0.1 ms. The synthetic model size was chosen to be sufficiently large to get free from border effects. After the calculations, the data were resampled to 48 traces with 1 m spacing and 1000 samples with a 1 ms sample interval and processed using CCASW.

Fig. 3 presents a flow diagram illustrating the processing procedure for the synthetic shot gather data obtained through numerical modelling. Fig. 3a illustrates the cross-correlation operation for selected synthetic examples. The variables dt, t, and dv/v are highlighted in Figure 3b.

Figs. 4a, 4b, and 4c show the resultant stack section and calculated Vs perturbation (dv/v) for the vertical defect synthetic model. Evident velocity perturbation artefacts appear on both sides of the perturbation peak according to the direction of the moving-source observation. In fact, when the source location is centred on the position of the defect, the waveform is perturbed for all the shot gathers even when some traces lie outside of the anomaly. To remedy this phenomenon, only the maxima of both calculated Vs perturbations (dv/v) of the two moving-source datasets are retained. Fig. 4c shows that the value of dv/v around -20% obtained from CCASW of the whole seismic line is coherent with the inferred true Vs perturbation value of -17%, which provides a consistency check for the method.

To characterise the in-depth velocity perturbation, a zero-phase, sine-squared, tapered band-pass filter centred on the frequencies 10 Hz to 45 Hz, in increments of 5 Hz, was applied after the cross-correlation analysis. The variables dt and t were then obtained for different frequencies of the surface wave. A "pseudo-depth" for the calculated dv/v was retrieved considering the approximation of the half wavelength of the surface wave [START_REF] Wightman | Application of Geophysical Methods to Highway Related Problems[END_REF]:

f V d ph 53 . 0  (3)
where d is the depth, Vph is the phase velocity of the surface wave, and f is the frequency. Fig. 5 shows the 2D Vs profiles reconstructed by applying the calculated lateral velocity perturbation (dv/v) to the homogeneous half space.

Here, we observe that the CCASW allows for the reconstruction of the synthetic velocity models used for numerical modelling, and that the buried low-velocity defect is resolved using the frequency-depth conversion approximation.

Field test: Detection of a buried pipe

Data acquisition

Rayleigh wave shot gathers were acquired along a linear profile over a known buried pipe. To increase the speed and efficiency of the data recording and thereby reduce acquisition costs, a multichannel seismic cable was designed and manufactured with 24 takeouts at fixed intervals of 2 m. Each takeout is attached to a single self-orientating, gimballed, vertical geophone with a resonance frequency of 10 Hz. To ensure proper coupling, each gimballed geophone is housed in a heavy casing (~1 kg). To damp the motion of the sensor around its rotational axis, the inside of the casing is filled with viscous oil. The seismic cable was towed behind a vehicle. A 24-channel seismograph was used to record the impacts of a weight-drop electronic seismic source. The source-to-nearest-receiver offset was 2 m, whereas the source stations were separated by 10 m along the survey line. In this way, measurements were performed with a recovering distance, as shown in Fig. 1, between each position of the seismic antenna (meaning that consecutive shots have several common geophones) to improve the signal-to-noise ratio in the CCASW stack section.

Field test: Detection of a buried karst

Geological setting

As a feasibility test of the previously outlined method, an experiment was conducted to detect a near-surface buried karst as an anomaly. The geological information is provided by 3 the geotechnical soundings performed on the investigation site (Fig. 6a):

 The levee embankment consists of loamy materials and brown silt. This formation extends vertically from the surface to a depth around 4-5 m.

 A sedimentary formation is represented by the Loire River sandy alluviums and gravels. This formation extends vertically from depths between 4-5 m to 12-13 m.

The bedrock formation is composed of differentially weathered white limestone and marls that extend to a depth around 13 m. The presence of such easily dissolved bedrock (limestone and dolomite) near the ground surface is characteristic of karst terrain. Because carbonate rocks can be dissolved by groundwater, karst areas are often characterised by sinkholes, springs, and underground streams whereby some surface flows are lost to groundwater [START_REF] Waltham | Sinkholes and Subsidence, Karst and Cavernous Rocks in Engineering and Construction Series[END_REF][START_REF] Halbecq | Approche géomorphologique des brèches dans les levées de la Loire (Geomorphologic approach of breaches in Loire levees)[END_REF]).

Data acquisition

Rayleigh wave shot gathers were acquired along a linear profile at the top of a flood-protection levee along the Loire River in France (Fig. 6a). The survey site was located in a karst terrain near an area of surface collapses (Fig. 6b), which are among the known subsidence features of karst activity [START_REF] Waltham | Sinkholes and Subsidence, Karst and Cavernous Rocks in Engineering and Construction Series[END_REF][START_REF] Halbecq | Approche géomorphologique des brèches dans les levées de la Loire (Geomorphologic approach of breaches in Loire levees)[END_REF]). The purpose of the survey was to detect potential buried karstic features at the location of the collapse. The configuration used for this field test is the same as that used for the detection of the buried pipe and for the karst investigation in [START_REF] Debeglia | Karst investigations using microgravity and MASW; Application to Orléans, France[END_REF]; Which one gave good results in detecting karstic features to a depth around 15-20 m Simultaneously, 3 geotechnical soundings (S1, S2, and S3) were performed with the aim of verifying the validity and accuracy of the CCASW method.

Results

Detection of a buried pipe

A prerequisite to the application of the CCASW to field data was the identification of a reference shot gather that was representative of an unperturbed area for the survey line. The first shot gather was selected for the reference as it was situated at a location where no buried pipe was indicated on the pipeline plan. A CCASW stack section was then computed and a conventional dlmo processing (Park et al., 1998a,b) was also applied to the entire field surface wave dataset for comparison. Fig. 7 shows the comparison between the dlmo stack section (Fig. 7a) and the CCASW stack section (Fig. 7b). The buried pipe is revealed as a diffraction at X=70 m on both stack sections. The apex of the diffraction appears at the time 0.1 s. Here, we see that the CCASW better resolves the diffraction and allows for improved accuracy and resolution compared with conventional dlmo imagery.

Detection of a buried karst

A prerequisite to the application of the CCASW to field data was the identification of a reference shot gather that was representative of an unperturbed area for the survey line. This selection was realised using the shape of the phase-velocity-versus-frequency (c-f) dispersion images. The c-f images of the shot gathers located near (X=280 m) and far (X=50 m) from the collapse (X=290 m) were then compared for this purpose. The c-f image of the shot gather located near the collapse (Fig. 8b) exhibited the generation of higher propagation modes, whereas this was not the case for the shot gather located far from the collapse (Fig. 8a). As noted previously, the generation of higher modes is a good indicator of the presence of a complex medium lying below the surface location of the seismic antenna. For this field test, and in many cases, we admit that the generation of higher modes in the c-f image of a shot gather is an inadequate criterion for the choice of this shot gather as a reference. The shot gather at location X=50 m was thus selected as the reference shot for the study. Fig. 9 shows a shot gather located at X=100 m, away from the collapse, a shot gather located at 280 m, and the respective results of cross-correlation with the reference shot gather. A perturbation can be distinguished near the collapse on the basis of the time-shifted cross-correlation (approximately 0.02 s), whereas no consequent time shift is observed far from the perturbed area. CCASW processing was applied to the entire field surface wave dataset after a zero-phase, sine-squared, tapered band-pass filtering centred on the frequencies 8 Hz to 40 Hz every 2 Hz.

We note that this study was conducted in the operational context of a project aimed at assessing Loire River levee integrity over a total distance of approximately 70 km, and we thus did not acquire surface wave data in the two directions of the moving source observation. The calculated Vs perturbations (dv/v) are then likely to be somewhat distorted compared with their true values due to the effects of moving-source artefacts, as illustrated in Fig. 4.

Nevertheless, based on the numerical modelling results, we suggest that the general distribution of velocity perturbations constitutes a reasonable first-order approximation of the actual situation in the subsurface. Fig. 10 presents the resulting calculated Vs perturbation (dv/v) for the 16 Hz frequency. Here, a Vs perturbation (dv/v) of approximately -25% appears between the locations at 250 m and 300 m and almost centred on the location of the surface collapse. The frequency-depth conversion was then applied using the half-wavelength approximation, and a 2D Vs cross-section was reconstructed by applying the lateral velocity perturbations to a 1D Vs profile obtained by a non-linear leastsquares inversion [START_REF] Xia | Estimation of near-surface shear-wave velocity by inversion of Rayleigh waves[END_REF] of the reference shot gather dispersion curve. To ensure the correctness of reference shot gather's inversion, the authors paid attention to the fit between the observed and computed dispersion fundamental curves as in common practice in surface wave methods. A conventional MASW processing with fundamental mode inversion was also applied to the entire field surface wave dataset for comparison. Following the convention, the inverse results for each shot gather were located at the midpoint of each position of the seismic antenna. To assess the lateral variations of elastic properties with depth, the CCASW stack section was convolved with a 32-s linear sweep with frequencies decreasing from 40 to 5 Hz. This operation has the effect of separating the different frequencies of the surface wave. The frequency depth conversion was then applied using the half-wavelength approximation.

Figs 11a, 11b and 11c show the CCASW stack section and Vs profiles obtained from the MASW and the CCASW methods. The weathering index (A-value) curves obtained from the geotechnical soundings are superimposed on the resulting sections. This geotechnical parameter is defined as follows [START_REF] Pfister | Recording drilling parameters in ground engineering[END_REF]:

         max max 1 VA VAi PO POi A (4)
where Poi is the pressure on the drilling tool for depth i, POmax is the maximum pressure on the drilling tool during the sounding, VAi is the velocity of the drilling tool as it progresses in the ground for depth i, and VAmax is the maximum velocity of the progress of the drilling tool during the sounding; A-values vary between 0 for voids and 2 for highly competent materials. A coherent, weakamplitude, low-velocity anomaly (140-300 m/s) that trends north-west from 0 to 23 m depth is evident on the convolved CCASW stack and the CCASW Vs profile and is almost centred on the location of the surface collapse (X=300 m) (Fig. 11). The attenuation area is likely caused by destructive interference due to the generation of higher modes near the location of the collapse (Fig. 8b).

The anomaly decreases in coherence and magnitude down to a depth of 30 m.

It is evident that the shape of the anomaly is roughly consistent with the low to very low A-values (0-1) from the S2 and S3 soundings, revealing the presence of highly deconsolidated materials. The A-values from S1, showing no dramatic values (>1) of the weathering index, reveal the relative competency of the adjacent areas. The MASW Vs profile shows a vast zone with a lower Vs (approximately 450 m/s) between the depths of 20 and 40 m and a vertical shift related to the collapsing feature (Fig. 11b). This shift is likely due to the change in the shape of the fundamental mode in the c-f image, which trends towards lower velocities in the perturbed area compared with the reference c-f image (Fig. 8). Further the velocity depression of the fundamental mode due to the presence of weathered materials, generated higher modes reveal the complexity of the area near the collapse. Nevertheless, the velocity distribution obtained using the MASW does not coincide very well with the A-value curves, especially in the 10-20 m depth interval.

Discussion

The geology of the studied area consists of a levee embankment (brown silt) above a sedimentary formation that is composed of gravels and sand based on However, we note that this study considers only the fundamental mode and that the MASW Vs profile resolution could be improved when considering the recent achievements in the accurate assessment of Vs profiles using surface wave methods. For example, further studies should compare the results of the CCASW method with the multimode inversion results of c-f images or joint inversion using the effective dispersion of surface waves [START_REF] Hamimu | Improving the accurate assessment of a shear-wave velocity reversal profile using joint inversion of the effective Rayleigh wave and multimode Love wave dispersion curves[END_REF].

Conclusions

The study presents the CCASW method, a novel approach to seismic imaging based on the cross-correlation analysis of multi-channel surface wave data.

This method allows for high-resolution surface wav imagery and the accurate estimation of Vs perturbations and enables the reconstruction of twodimensional subsurface Vs distribution with high resolution without requiring the systematic processes of multichannel spectral analysis of surface waves: the computation of dispersion images and the picking and inversion of dispersion curves. The overall performance of the newly developed method in this study, demonstrates that it is a simple, reliable, and very sensitive technique for characterising lateral variations in near-surface mechanical properties. This method should be applicable to the detection of a variety of subsurface defects (e.g., voids, karsts, or structural heterogeneities). The applicability of this model extends to the characterisation of material properties, integrity assessment, and surface profiling in many types of geotechnical and environmental studies. Our analyses of waveform data derived from numerical modelling and field observations indicate that the CCASW method is valid as an operational sounding method and provides strong inputs for characterisation studies of near-surface features that allow for improved accuracy and resolution compared with conventional surface wave methods.

Figure captions

Fig. 1 The source-receiver geometry used in the numerical tests. Both directions of the moving-source observation of surface waves were tested. The shot positions for the gathers shown in Fig. 3 are highlighted. In the unperturbed case, the cross-correlations are centred on the time 0 s. In the perturbed case, the cross-correlations show a travel-time perturbation of approximately 0.01 s. b) Illustration of the calculation of the Vs perturbation (dv/v) using equation ( 2) and the variables dt and t, which are highlighted by white dotted and solid lines, respectively. In the perturbed case, the Vs perturbation is approximately -10% between traces 30 and 48.

  correlation at time zero to no correlation at infinite time. For the crosscorrelation between two surface wave signals at different locations, assuming seismic source repeatability, near-surface features and near-surface Vs structures create perturbations, and the two signals then fluctuate independently; thus, the correlation between them decays at a certain propagation time. Cross-correlation temporally correlates the intensity fluctuations of the seismic traces. In cross-correlation, only pairs of coherent samples from two distinct traces appear as a positive result at time t, whereas fluctuations in the surface wave signal created by a Vs perturbation generate a positive result at time t+dt, accounting for the travel-time perturbation dt.

  envelope traces are used to obtain the surface wave travel time, t. The trace envelope is an attribute of seismic traces computed using the function suattributes of the Seismic Unix (SU) package and corresponds to the envelope amplitude of the trace. These two variables are inserted into equation (2) to calculate the Vs perturbations dv/v. The Vs perturbations with the same receiver location are averaged. A Vs profile is reconstructed by applying the velocity perturbation model at different frequencies to a homogeneous Vs profile obtained by inversion of the surface wave dispersion of the reference shot gather.

  a white limestone bedrock. The CCASW stack section and CCASW Vs profile respectively reveal a weak amplitude and low velocities (approximately 140-300 m/s) in an area between 0 and 23 m deep at the location X=300 m, likely representing the complexity of the unconsolidated near surface weathered materials. The model presents significantly higher velocities in the adjacent areas. The low field velocities in the CCASW Vs profile likely result from the presence of a karstic collapse below a northwest-trending epikarst created by the flow of sediments into the karstic cavity. The MASW Vs profile shows poor agreement with the actual situation of the subsurface given by the A-value curves, indicating that the CCASW method greatly improves upon the accuracy and resolution of the reconstructed subsurface Vs distribution compared with the conventional surface wave methods with fundamental mode inversion.

Fig. 2

 2 Fig.2The Vs models used for the numerical tests. The locations of the seismic

Fig. 3

 3 Fig. 3 A diagram illustrating the processing of surface wave data. a) Examples

Fig. 4

 4 Fig. 4 a) A left-right moving source CCASW stack section for the vertical defect

Fig. 5

 5 Fig.5The Vs profiles obtained by CCASW processing of the data obtained

Fig. 6

 6 Fig. 6 a) An aerial photograph of the survey site. The black solid line denotes

Fig. 7 .Fig. 8 A

 78 Fig. 7. A comparison of the a) dlmo stack section and b) CCASW stack section

Fig. 9 Fig. 10

 910 Fig.9The calculation of cross-correlations from traces of the unperturbed shot

Fig. 11

 11 Fig. 11 a) The convolved CCASW stack section. b) Vs profile defined by the

Acknowledgements

The study was financed by the French Research and Environment ministry. The authors thank the technicians of the BRGM for acquiring the seismic data.

Finally, the authors thank the Near Surface Geophysics Editors, Barbara Luke and an anonymous reviewer for their comments and suggestions that led to a much-improved manuscript.


Abderrezak Rachedi
email: rachedi@univ-mlv.fr

Hakim Badis
email: badis@univ-mlv.fr

MIMODog: How to solve the problem of Selfish Misbehavior Detection Mechanism in MANETs Using MIMO Technology

Keywords: MANET, SPACE-MAC, MIMO, Selfish misbehaviors, Monitoring process

Mobile Ad-hoc Networks (MANETs) are based on a fundamental aspect, which is the cooperative parameter. This parameter may compromise the networks. The selfish misbehaving nodes can seriously affect the network performance. Moreover, the existing mechanisms based on the monitoring process to detect the misbehaving nodes are not efficient and suffer from an important false alarm rate. These weaknesses are mainly due to the interferences and the costs of the monitoring process. In MANET based on SISO (Single-Input Single-Output) technology, the interferences at the monitor node compromise the observation and the accuracy of the cooperation report. That is why in this paper, we focus on the MIMO (Multi-Input and Multi-Output) technology to overcome these drawbacks and to significantly improve the monitoring process. We propose a new MAC protocol called MIMODog-SPACE-MAC based on the well-known SPACE-MAC protocol. It allows the monitor node to avoid the collision during the monitoring process by adjusting the antennas weights in order to nullify the signal coming from other nodes than the monitored one. Therefore, the proposed solution contributes to significantly enhance the accuracy of the monitoring process. We show that for a MIMO network with randomly located nodes n, each equipped with M antennas, the achievable number of monitor nodes is Θ( M √ n ln n ). Indeed, theoretical results show that by using MIMODog-SPACE-MAC, the network can have a constant improvement M on an asymptotic number of monitor nodes compared to SISO 802.11 DCF MAC.

I. INTRODUCTION

Mobile Ad hoc Networks (MANETs) are a set of nodes based on the cooperation aspect to form and manage a network without any infrastructure. The nodes in MANETs act as router and terminal at the same time and the lack of cooperation between them implies the absence of any network. That is why it is important to deal with the non cooperative or selfish nodes problem. The problem of selfish nodes is that they keep their energy to transmit and route their own packets. In other words, the selfish nodes refuse to route and forward the packets of other nodes. The question is why do nodes act as selfish and ignore the cooperation aspect? To answer this question, we investigate the motivation of nodes to adopt this misbehavior.

First of all, the resources in MANETs are limited in terms of energy, bandwidth, etc. Then, the nodes try to increase their lifetime duration by reducing their energy consumption and the cost of the transmission operation is important in terms of energy. Secondly, when the nodes route and forward the packets of other nodes, this increases the delay of their own packets transmission and reduces their own average throughput. Thus, this operation may be perceived by nodes as punishment and not as global network interest. In order to deal with this problem, many researchers focus on the monitoring mechanisms in order to detect the selfish nodes and to punish them [START_REF] Marti | Mitigating routing misebehaviour in mobile ad-hoc networks[END_REF], [START_REF] Rachedi | Toward a cross-layer monitoring process for mobile ad hoc networks[END_REF], [START_REF]Cross-layer approach to improve the monitoring process for mobile ad hoc networks based on ieee 802.11[END_REF], [START_REF] Michiardi | Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF]. However, all the proposed mechanisms are based on the classical SISO (Single-Input Single-Output) technology to monitor the communication channel and to detect the non forwarding nodes (selfish behavior). The most cited mechanism is Watchdog. Many proposed solutions are based on it, but it suffers from the high false alarm rate [START_REF] Marti | Mitigating routing misebehaviour in mobile ad-hoc networks[END_REF]. The main problem of these mechanisms is related to the interference at the monitor node which makes the results of its observations wrong.

That is why we propose a new MAC protocol called MIMODog-SPACE-MAC based on MIMO (Multi-Input Multi-Output) technology, particularly a SPACE-MAC protocol to significantly cancel the potential interferences at the monitor nodes and to enhance the accuracy of the monitoring results. Our contributions are summarized as follows:

• The monitoring problem persists in MANETs, even when we use MIMO technology,

• A new MIMO MAC protocol is proposed to cancel the interferences at the monitor nodes without affecting the total network capacity,

• A different impact on the monitoring process with: DCF MAC, SPACE-MAC and MIMODog-SPACE-MAC is presented and discussed. MIMODog-SPACE-MAC significantly enhances the monitoring process without affecting the network capacity.

• MIMODog network modelling is done and lower and upper bounds of the number of monitor nodes are investigated. Moreover, the obtained numerical results illustrate that the proposed solution overcomes the drawbacks of classical monitoring mechanisms. This paper is organised as follows: an overview of cooperation models based on monitoring mechanisms and the SPACE-MAC protocol are given in in section II. Section III illustrates the DCF and SPACE-MAC protocols vulnerabilities in the monitoring process. A new MAC protocol adapted to the monitoring process with more details on its design and its implementation is proposed in section V. Moreover, we present the theoretical model in order to assess the asymptotic bound related to the monitor nodes number. The numerical results are given and analysed. The final section concludes the paper and presents the future works.

II. RELATED WORK

In this section, we present the existing works related to cooperation models in MANETs and the SPACE-MAC protocol.

A. Cooperation Models

Two types of uncooperative nodes can be distinguished: malicious nodes and selfish nodes. The malicious nodes try to attack the system by selecting an uncooperative behaviour and create a disconnection in the network. However, the aim of selfish nodes is to maximize their benefits in terms of QoS (like throughput and delay) and minimize their costs like the energy consumption. In this paper, we focus on the selfish behaviour of the potential cooperative nodes. Cooperation is an important parameter in wireless networks, because without any packet forwarding, the ad hoc network cannot exist and the wireless coverage extension cannot be possible. The concept of cooperative communication (CC) technique in wireless networks was introduced in [START_REF] Nosratinia | Cooperative coomunication in wireless networks[END_REF].

In literature, two main solutions were proposed to overcome the problem of selfish nodes. The first one is based on the reputation mechanisms which consist in assessing a node's contribution like forwarding and routing functionalities [START_REF] Michiardi | Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF], [START_REF] Marti | Mitigating routing misebehaviour in mobile ad-hoc networks[END_REF], [START_REF] Buchegger | Performance analysis of the cofidant protocol[END_REF], [START_REF] Bansal | Observation-based cooperation enforcement in ad hoc networks[END_REF]. The reputation model called CONFIDANT is proposed to share the reputation metric and alarms messages in order to detect and punish the misbehaving nodes [START_REF] Buchegger | Performance analysis of the cofidant protocol[END_REF]. Another model called CORE is proposed to implement the reputation function by using the monitoring technique. Each node computes the reputation value for every neighbour and refuses to provide services to misbehaving nodes when their reputation is lower than a certain threshold . However, all these solutions are based on the classical monitoring mechanism like Watchdog [START_REF] Michiardi | Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF]. Consequently, they did not consider the problems of the false observation related to the collision and the performance of the potential relayed nodes.

B. SPACE-MAC protocol: Spatial Reuse Using MIMO Channel-Aware MAC

The SPACE-MAC is a Media Access Control protocol for networks with smart antennas which uses antenna weights to schedule simultaneous transmissions on a single collision domain. Antenna weights are exchanged via control packets (RTS and CTS) [START_REF] Park | Space-mac: Enabling spatial reuse using mimo channel-aware mac[END_REF].

The main contribution of SPACE-MAC work is the fully distributed MAC protocol that exploits the physical layer characteristics and cross-layer techniques to enable spatial reuse in scatter-rich multi-path environments. The main advantage of SPACE-PAC is that it allows multiple data streams at the same time in the same collision area, thereby increasing the overall capacity of the network. The channel control overhead introduced by channel estimation and beam coordination is minimal and effectively countered by the gain provided by the increase in the capacity of the MIMO channels.

In SPACE-MAC, the first station that gains access to the channel determines the silence period. All other stations must remain idle following their transmission until the silence period is completed. In SPACE-MAC, the silence period is required because any station currently involved in the transmission is unaware of any other transmission that began during its data packet or acknowledgement packet transmission phase. Additionally, any station that wishes to transmit must not interfere with this ongoing transmission and must not transmit if it cannot complete its entire packet exchange sequence before the end of the silence period.

Based on the RTS/CTS of the existing transmission and for each new communication in the same geographical vicinity, the new sender/receiver nodes will select their weights so that the signal from any existing communication node is nullified. This problem can be formulated as a quadratic optimization and reduced to an unconstrained optimization problem using the null space method which in turn is an eigenvalue problem. Any new additional transmission is only possible if both nodes of a same pair have enough degrees of freedom. For an M antenna system it can null out at most M -1 stations depending on the environment. M is also known as the Degrees of Freedom (DOF). Every time a node nulls out another node, it consumes a DOF.

III. MAC PROTOCOLS VULNERABILITIES IN MONITORING PROCESS

A. Case of 802.11 DCF MAC

The monitoring process acts on the different network protocol layers (MAC, Routing, ...). In this work, we focus on the network layer for the monitoring. The monitor node supervises the packet forwarding activities of its neighbor nodes and their packet integrity. Let us consider a small network illustrated in Figure 1.

B. Case of SPACE-MAC

In this section, we will show that the monitor nodes cannot recover collided packets using the standard SPACE-MAC protocol. Let us consider the last network (Figure 1). We assume that all nodes are silent at the beginning, i.e., there is no on-going communication and each node has 4 antennas. Node B wants to forward A's packets to C and D wants to communicate with E. Node B transmits a RTS using the default weight vector, [1 1 1 1]/ √ 4, or a random vector. The vector is normalized to have an equal signal power regardless of the number of antennas. The weight vector used to transmit the RTS will be used to transmit the following data packet and to receive the corresponding CTS and ACK. Once node C receives the RTS, it responds with a CTS packet using the current weight vector. The weight vector used to transmit the CTS will be used to receive the following data packet and to send an ACK. The receiver estimates the SIMO (Single-Input Multi-Output) channel vector h BC = w H B H BC , where w B is weight vector of node B and H BC is M × M MIMO channel matrix with elements h ij and the superscript H denotes hermitian operation. In fact, as there is no ongoing communication, nodes C (receiver) and A (monitor) can switch their weight vectors to w C = h t BC and w A = h t BA which maximize the combined channel and array gain. When a node other than the designated receiver and the neighbor monitor receives the RTS, say node K, it estimates the effective channel H and adjusts the weight vector so that the signal from the RTS sender is nullified (i.e., h BK C K = 0) for the duration of time specified in the RTS duration field. When a node other than the sender of the RTS (B) receives the CTS, say node L, it estimates the effective channel and stores the weight vector for the duration specified in the CTS duration field. After the RTS/CTS handshaking, node B sends, C receives and A supervises a data frame using respectively the weight vectors w B , w C and w A chosen as described above. Now let us say node D wants to initiate a transmission toward E. Since node D is not currently aware of the antenna weight used by node B (node D cannot overhear B's RTS and C's CTS), it cannot adjust its weight vectors meeting these conditions: w H D H DA w A = 0 (D's signals cannot be nullified by A). Consequently a collision will occur at node A. The example shown in Figure 3 describes such a process problem.

IV. MIMODOG-SPACE-MAC PROTOCOL

In order to avoid the interferences at the monitor node, each new transmitting nodes must be aware not only about the the weight vectors of the existing transmissions in the cover area, but also about the weight vectors used by the monitor nodes. To deal with this issue, we propose a new MIMO MAC protocol called MIMODOG-SPACE-MAC. The basic idea is that the monitor nodes simulate a real reception by sending CTS packet control before starting their monitoring process. We use the previous example to illustrate our MIMO MAC protocol functioning.

A. Basic protocol operation

When monitor node A hears a RTS packet from its forwarding node B:

1) it estimates the SIMO channel vector h BA = w H B H BA and switches its weight vector to w A = h t BA to well receive B's packets for monitoring; 2) it sends a CTS packet after a SIFS time using a weight vector ŵA meeting this condition: ŵH A H AB w B = 0 (the A's CTS signal is nullified at B to avoid collisions with C's CTS and to assure that node B will not change its behaviour if it is malicious). The A's CTS contains the weight vector w A and transmitted using ŵA . The goal of this operation is to make all the future transmitters in the neighborhood believe that node A will receive packets and that its weight vector w A should be considered. On reception of the CTS packet from A, each node should estimate the effective channel from A. Now, the transmission of D should ensure that the reception of A is not disturbed. So, it picks W D meeting w H D H DA w A = 0 before transmitting its RTS.

The process is graphically explained in Figure 4.

B. RTS/CTS Control Packet Format

In order to selectively tune in or tune out a particular transmission, the stations have to be aware of the antenna weights that are in use by transmitting stations. This requires a mechanism to convey the antenna weights to all neighboring stations. MIMODog-SPACE-MAC uses RTS and CTS control packets to convey antenna weights. The proposed format for RTS and CTS control packets is shown in Figure 5. A separate s byte field is inserted in the payload of the RTS and CTS packets that stores M antenna element weights currently in use. A linear function f is used to obtain the value of s. For example, as each antenna weight can be a complex number, we can store them as a pair of real numbers occupying 4 bytes (per one complex number) and so f (M ) = 4M . RTS and CTS packets are also used to perform channel estimation using pilot symbols embedded in the physical (PHY) preamble. We consider a random multi-hop MIMO ad hoc network with n nodes, where each node, equipped with M antennas, is randomly located in a unit square area. Each node acts as a source node and transmits data to a randomly chosen destination node. The per-node throughput λ(n) is defined as the minimum data rate that can be sent from each source to its destination via multi-hop routing. The maximum data rate that a single data stream can support is W . We assume that a node's transmitter is limited to a transmission range r(n). When a source node cannot transmit data to its destination node in one hop, multi-hop routing is needed to relay the data. Each node also has an interference range (1 + ∆)r(n), where ∆ is non negative-constant.

A. Lower bound of the number of monitor nodes

In [START_REF] Gupta | The capacity of wireless networks[END_REF], Gupta and Kumar showed that a capacity lower bound for a single-antenna ad hoc network is Ω( W √ n ln n ) by constructing a feasible routing and scheduling scheme. Thus, by adopting the same routing and scheduling scheme in our MIMODodog ad hoc networks as in [START_REF] Gupta | The capacity of wireless networks[END_REF], a number of monitor nodes lower bound of Ω( M √ n ln n ) can be obtained.

B. Upper bound of the number of monitor nodes

As shown in [START_REF] Jiang | On the asymptotic capacity of multi-hop mimo ad hoc networks[END_REF], we partition the unit square of the network into small squares, with the size of each small square being cleverly chosen so that the maximum data rate that can be received by the nodes inside the small square can be accurately computed. This method allows to estimate the number of monitor nodes. ∆.r(n) ⌉ (as shown in Figure 6), the maximum number of total data streams that can be received by the nodes inside the square at any time slot for any routing scheme is not greater than M regardless of the number of receiving nodes inside the square. Using our MIMODog-SPACE-MAC, the presence of a monitor node in the square area consumes exactly one DOF. Let P j (t, i) be the probability that node i is a monitor at time t in a square j. The number of monitor nodes in square j is given by n i=1 P j (t, i). Consequently, the new maximum number of total data streams that can be received by nodes inside a square j is not greater than M -n i=1 P j (t, i) (M ≥ n i=1 P j (t, i)). In the same square and using SISO systems, the maximum number of total data streams that can be received by nodes inside the square is 1. Only one monitor node can be functioning properly. So, there are at most M -1 times fewer monitor nodes with SISO 802.11 DCF than with MIMODog-SPACE-MAC.

Based on Lemma 1, we can now compute the maximum number of monitor nodes that can be supported in the unit square network by taking the sum of the number of monitor nodes among all small squares. Theorem 1. For a random multi-hop MIMO ad hoc network, a number of monitor nodes upper bound for all possible routing and scheduling schemes is O( M √ n ln n ) with a high probability when n → ∞.

Proof: The proof is similar to the proof of Theorem 1 in [START_REF] Jiang | On the asymptotic capacity of multi-hop mimo ad hoc networks[END_REF]. We can easily obtain this equation:

NMN ≤ 2M √ π ∆ 2 D √ n ln n + 2 √ 2M ∆Dn + M √ ln n) Dn √ πn = O( M √ n ln n ), (1)
where NMN is the number of monitor nodes and D is the average length of source-destination lines.

Combining the lower and upper bounds of the number of monitor nodes, we can see that the number of monitor nodes in a random multi-hop MIMO ad hoc network with n nodes is Θ( M √ n ln n ). By running 1000 instances, we obtain the average length of source-destination lines D = 0.52 (see [START_REF] Jiang | On the asymptotic capacity of multi-hop mimo ad hoc networks[END_REF]). We set ∆ = 1. Using equation 1 and under different values of M = 1, 2, 3, 4 we obtain the results shown in figure 7. With M = 1 antenna, MIMODog-SPACE-MAC is exactly the 802.11 DCF MAC. We can extract 2 elements :

C. Numerical results

• when the number of used antennas increases, the number of monitor nodes increases,

• when the number of nodes increases, the upper bound of monitor nodes decreases. This is explained by the fact that the network is more and more dense with a high multihop connectivity and so MIMO interference cancellation is limited.

VI. CONCLUSION

In this paper, we propose a new scheme for exploiting adaptive antenna arrays in wireless communications in a multiparty propagation channel to efficiently detect the selfish nodes. The proposed scheme nullifies the beam to competing nodes to enable concurrent transmissions and monitor in the same collision domain. A distributed MAC protocol called MIMODog-SPACE-MAC, that supports the exchange of channel state and antenna information is described.

A different impact on the monitoring process with: DCF MAC, SPACE-MAC and MIMODog-SPACE-MAC is presented and discussed. Moreover, we have studied the number of monitor nodes scaling laws for MIMO ad hoc networks with M antennas. We have shown that the number of monitor nodes is at most M -1 times larger based on MIMODog-SPACE-MAC than with SISO 802.11 DCF MAC.

In our future works, we plan to evaluate the proposed solution by extensive simulations with different parameters like density of selfish nodes, mobility models, traffic models, etc.

Fig. 1 .

 1 Fig. 1. An ad hoc network scenario

Fig. 2 .

 2 Fig. 2. Monitoring problem based on 802.11 DCF MAC protocol

Fig. 3 .

 3 Fig. 3. Monitoring problem based on SPACE-MAC protocol

Fig. 4 .

 4 Fig. 4. Monitoring mechanism with MiMoDog-SPACE-MAC

Fig. 5 .

 5 Fig. 5. Access Control Packets

Fig. 6 . 2 ∆

 62 Fig. 6. The receivers in a square with side length

Fig. 7 .

 7 Fig. 7. The upper bounds of the number of the monitor nodes versus the number of nodes