Polina Lemenkova
email: pauline.lemenkova@gmail.com

GMT-based geological mapping and assessment of the bathymetric variations of the Kuril-Kamchatka Trench, Pacific Ocean

Keywords: GMT, Bathymetry, Modelling, Mapping, Geospatial Analysis

This manuscript summarizes the results of the geospatial analysis undertaken by means of Generic Mapping Tools (GMT). The comparative assessment of the bathymetry of the Kuril-Kamchatka hadal trench was performed for southern and northern segments separated by the Bussol Strait. The formation of the hadal trench is affected by the impacts of local geological and geophysical settings varying along the trench. The methodological approach is as follows. The profiling was undertaken using GMT modules 'grdimage', 'grdtrack' and 'psxy'. The modelling consists of the collected data of 10706 observation samples from 52 profiles in southern part and 12726 from 62 profiles in the northern segment. The GMT modules 'psrose' and 'pshistograms' were used to plot histograms and rose diagrams visualizing bathymetric variables of depths. The geology was mapped using GMT modules 'pscoast', 'grdcut', 'grdcontour' and 'psxy' to plot lineaments and geological objects (ophiolites, faults, earthquakes, trench, magnetic anomalies, tectonic slabs, fracture zones and volcanoes). The base map is based on the ETOPO Global Relief Model. The comparison of the bathymetry shown variations in the northern and southern segments: southern part reaches -8,200 m maximal depths while northern has -7,800 m. This is influenced by the geological settings: earthquakes magnitude and seismisity are higher in the south-west. The submarine terraces and floodplains were observed at -4000 m depth forming landforms located southwards off the Bussol Strait. This geospatial analysis contributes to the development of the geological mapping with an example of the Kamchatka area, a region with high seismisity and repeated earthquakes.

Introduction

The geographic object of this study is the Kuril-Kamchatka Trench, located in the north-west Pacific Ocean (Figure 1). The specific distinction of this hadal trench is its clear division into two parts: northern and southern segments separated by the Bussol Strait. The geological settings of the study area is characterized by high seismicity, repeated earthquakes, and tectonic instability caused by plate subduction. Geological factors differ in northern and southern parts of the trench, which naturally affects its geomorphology. The comparisons on the northern and southern parts of the Kuril-Kamchatka Trench seafloor are not assessed within the published literature. Therefore, the novelty of this study is a contribution towards the regional analysis of the geospatial variation of the trench geomorphology in its southern and northern parts.

The study aim is comparative geomorphic analysis of deep-sea oceanic trench: Kuril-Kamchatka Trench located in the geologically complex region of the north-western part of the Pacific Ocean. Complex geophysical settings results in formation of the trench, high seismicity, repetitive earthquakes and volcanism and geodynamic instability visualized on the thematic maps of geological and tectonic settings as the most important causes of the ocean trench formation. Cartographic objective of the study is to visualize bathymetry, geological settings, earthquakes, volcanoes and seismisity, depict lineaments of the tectonic slabs, areas of large igneous provinces, geomorphology, tectonic and geological settings of the trench. Additional aim is to perform statistical analysis for comparative depths distribution and aspect of the slopes in the southern and northern part of the Kuril-Kamchatka Trench.

The objective of this research was to detect differences in the northern and southern parts of the Kuril-Kamchatka Trench through performed comparative geostatistical analysis using a sequence of the presented GMT modules. Technically, this research is intended to establish a framework of the GMT based geospatial modelling and mapping using multi-source data to obtain a better understanding of the submarine shape of the Kuril-Kamchatka Trench, and to raise awareness of this unique location.

The tectonic properties of the study area mutually affect both land and submarine geomorphology. Thus, as noted by [START_REF] Pflanz | Neotectonics and recent uplift at Kamchatka and Aleutian arc junction, Kamchatka Cape area, NE Russia[END_REF], the location of the KKT at the meeting place of active Kuril-Kamchatka and Aleutian arcs causes the coastline of the Kamchatka Peninsula to be affected by strong tectonic activities. Fracture zones have variable influence on the uplift of the Kamchatka Peninsula. The geomorphic consequence include raise of the multi-level, highly uplifted marine terraces displaced along the active tectonic faults. Furthermore, the tectonic movements cause the uplift of the coastal sediments [START_REF] Pflanz | Neotectonics and recent uplift at Kamchatka and Aleutian arc junction, Kamchatka Cape area, NE Russia[END_REF].

Material and Methods

The research methodology is completely based on the use of the Generic Mapping Tools (GMT) cartographic scripting toolset that was used to map Figures 1,2, 3 and 4. The GMT is a highly effective professional tool designed for mapping and developed by Wessel in Smith [START_REF] Wessel | New version, of the Generic Mapping Tools re-leased[END_REF]. Comparing to the traditional GIS software, the advantages of the GMT consists in its flexibility provided by scripting approaches rather than GUI, as well as open source free availability. A great advantage is a cartographic functionality of this tool set: a large variety of the visualization, plotting, modelling, as well as advanced cartographic modules: mapping projections, modelling, grid raster data processing [START_REF] Wessel | Free software helps map and display data[END_REF]. Due to the advantages of the GMT that consists in its functionality, a wide range of the cartographic projections and availability of the modules the GMT was selected as the best cartographic tools for geospatial analysis that was performed using available documentation [START_REF] Wessel | The Generic Mapping Tools[END_REF][START_REF] Wessel | The Generic Mapping Tools[END_REF]. In contrast to the classic cartographic approaches having Graphical User Interface (GUI), e.g. ArcGIS based, in geodata visualization and mapping [START_REF] Suetova | Geoinformation mapping of the Barents and Pechora Seas[END_REF][START_REF] Klaučo | Determination of ecological significance based on geostatistical assessment: a case study from the Slovak Natura 2000 protected area[END_REF][START_REF] Gauger | Swathbathymetric mapping[END_REF][START_REF] Klaučo | Land planning as a support for sustainable development based on tourism: A case study of Slovak Rural Region[END_REF][START_REF] Lemenkova | Seagrass Mapping and Monitoring Along the Coasts of Crete, Greece[END_REF][START_REF] Kuhn | The response of quaternary climatic cycles in the South-East Pacific: development of the opal belt and dynamics behavior of the West Antarctic ice sheet[END_REF], the GMT is notable for its scripting algorithms as a core conceptual methodology.

Bathymetric mapping

Bathymetric mapping (shown on Figure 1) and plotting profiles was performed using ETOPO1 bathymetric grid with 1 minute resolution using existing methodology (Lemenkova, 2019g;Lemenkova, 2019h). The map was visualized on the study area square using a sequence of the GMT modules. A 'grdcut' module was used for cutting area of interest from the global grid earth relief 01m.grd by selecting coordinates -R, following by 'grdimage' module for visualizing the grid itself. Examples of the previous research on the semi-automated digitizing of the cross-section profiles in Quantum GIS for further modelling using R language were considered for general research workflow (Lemenkova, 2018a;[START_REF] Lemenkova | Factor Analysis by R Programming to Assess Variability Among Environmental Determinants of the Mariana Trench[END_REF]. The key code snippets are provided below:

First, selecting study area from the grid was done using 'grdcut' module: grdcut earth_relief_01m.grd -R140/170/40/60 -Gkkt_relief.ncgmt Second, the image was visualized using 'grdimage' GMT module: grdimage kkt_relief.nc -Cmyocean.cpt -R140/170/40/60 -JM6i -P -I+a15+ne0.75 -Xc -K > $ps Third, the key points for northern and southern segments were selected by the code: gmt pstext -R -J -N -O -K -F+jTL+f18p,Times-Roman,yellow+jLB >> $ps << EOF 161.0 48.3 Kuril-Kamchatka 161.0 47.5 Trench EOF Then the profiles were plotted using GMT 'grdtrack' module (example for the nortehrn part): gmt grdtrack trench2.txt -Gkkt_relief.nc -C400k/2k/10k+v -Sm+sstack2.txt > table2.txt The profiles were plotted using code: gmt psxy -R -J -W0.5p table2.txt -O -K >> $ps The text annotations were added using following (here example of Deryugin Basin): gmt pstext -R -J -N -O -K -F+jTL+f14p,Times-Roman,black+jLB+a-75 -Gwhite -Wthinnest >> $ps << EOF 145.0 54.5 Deryugin Basin EOF

Geological mapping

The geological mapping (Figure 2) is based on the use of the sequence of the GMT modules. Several auxiliary modules were then used both for cartographic purposes (color scale, scale bar, directional rose, grid ticks and lines, etc) and for the map embellishment (GMT logo) using available techniques [START_REF] Smith | Global seafloor topography from satellite altimetry and ship depth soundings[END_REF]. The shoreline vector layers were driven from the existing GMT data sets [START_REF] Wessel | A Global Self-consistent, Hierarchical, High-resolution Shoreline Database[END_REF]: tectonics, bathymetry, geomorphology and geology. The most important code are the following: The relief map from ETOPO5 was cut off using following code: gmt grdcut earth_relief_05m.grd -R140/170/40/60 -Gkkt_relief.nc -V Then the coatslines were added: gmt pscoast -R140/170/40/60 -JL155/50/45/55/6i -P -W0.1p -Gpapayawhip -Slightcyan -Df -K > $ps Bathymetric contours were added using the following GMT code by 'grdcontour' module: gmt grdcontour @kkt_relief.nc -R -J -C500 -A2000+f9p,Times-Roman -S4 -T+d15p/3p -W0.1p -O -K >> $ps Next step included plotting a sequence of the geological lineaments and objects:

 gmt makecpt -Crainbow -T0/700/50 -Z > rain.cpt  gmt psxy -R -J trench.gmt -Sf1.5c/0.2c+l+t -Wthick,red -Gred -O -K >> $ps  gmt psxy -R -J ridge.gmt -Sf0.5c/0.15c+l+t -Wthin,darkcyan -Gpurple -O -K >> $ps  gmt psxy -R -J LIPS.2011.gmt -L -Gpink1@50 -Wthinnest,red -O -K >> $ps Example of the geological mapping of the hadal trench using Quantum GIS with a case study of the Mariana Trench, the deepest trench on the Earth (Lemenkova, 2019a) includes application of R programming, various statistical approaches towards data modelling (Lemenkova, 2019i;[START_REF] Lemenkova | K-means Clustering in R Libraries {cluster} and {factoextra} for Grouping Oceanographic Data[END_REF], automatization in hydrographic data processing [START_REF] Schenke | Zur Frage der Meeresboden-Kartographie: Die Nutzung von AutoTrace Digitizer für die Vektorisierung der Bathymetrischen Daten in der Petschora-See[END_REF]. The scope of the research is more focused on the geological assessment than statistical analysis. Therefore, the special attention was paid to mapping geological lineaments, faults, trench extent, location of the Large Igneous Provinces, volcanic spots and earthquakes in the Kuril-Kamchatka Trench (Figure 2). Various depth of the earthquakes are presented in different colors, as well as fracture zones, ophiolites, magnetic anomalies and extension of the tectonic slabs (Figure 2).

 gmt psxy -R -J ophiolites.gmt -Sc0.1c -Gmagenta -Wthinnest -O -K >> $ps  gmt psxy -R -J volcanoes.gmt -Sc0.1c -Gpurple -Wthinnest -O -K >> $ps

Statistical 3D histograms

Plotting statistical 3D histograms (shown on Figure 3) was performed using following sequence of the GMT codes: First, the available grid (file kkt_bathy.nc) was uploaded to the GMT and converted to the xyz format: gmt grd2xyz kkt_bathy.nc > kkt_bathy.xyz Second, the file was checked up to define the depth/heights range: gmt info kkt_bathy.xyzThird, the 3D histogram from the data table was plotted using following code:gmt psxyz kkt_bathy.xyz -Bpxa4 -Bpya2 -Bsxg2a2 -Bsyg1a1 -Bz2000+l"Bathymetry and topography (m)" -BWSneZ+b+t"3D-histograms of the depth values: Kuril-Kamchatka Trench" -R144/162/40/50/-7600/2000 -JM10c -JZ7c -p215/30 -So0.083ub-6000 -P -Wthinnest -Glavenderblush -UBL/-15p/-35p -K > $ps

Statistical 2D histograms

Statistical histograms of data distribution were plotted using a sequence of the GMT modules: gmtset, psrose, pshistogram, pslegend, logo and psconvert. The histograms plots demonstrated frequency of the data distribution against bathymetric variables. The statistical techniques of the data analysis are widely used in geospatial studies, applied and described in previous works. Plotting statistical 2D histograms and rose diagrams (Figure 4) was done using following GMT code:

 gmt psrose table2.txt -i1,4 -R0/1/0/360 -A7r -S1.0in -Gthistle -Bx0.2g0.2 -By30g30+l"Cross-section profiles of the trench, northern part" -B+t"Rose diagram of the bathymetric data distribution"+givory1 -M0.5c+e+gred+n1c -W0.1p,red -Cm -UBL/-1.4c/-2.3c -Vv -K > $ps  gmt pshistogram table2.txt -i4 -R-9000/6/0/20 -JX4.8i/2.4i -X3.6i -Bpxg1000a1000f100+l"Bathymetry (m)" -Bpyg5a5f2.5+l"Frequency"+u" %" -Bsyg2.5 -BWSne+t"Histograms of the depths frequency distribution: northern part"+gsnow1 -Glightsteelblue1 -D+f7p,Times-Roman,black -L0.1p,dimgray -Z1 -W250 -N0+pred -N1+pblue -N2+pgreen -O -K >> $ps Statistical analysis of the geospatial data using histograms, Kernel Density Estimation Plots, boxplots, regression analysis and other types of statistical approaches and algorithms has been performed in previous research using Python programming with a case study of the Mariana Trench [START_REF] Lemenkova | Processing oceanographic data by Python libraries NumPy, SciPy and Pandas[END_REF][START_REF] Lemenkova | Testing Linear Regressions by StatsModel Library of Python for Oceanological Data Interpretation[END_REF]. Other examples demonstrate using IBM SPSS Statistics [START_REF] Lemenkova | Numerical Data Modelling and Classification in Marine Geology by the SPSS Statistics[END_REF], statistical landscape metrics [START_REF] Klaučo | Landscape metrics as indicator for ecological significance: assessment of Sitno Natura 2000 sites, Slovakia[END_REF] and Gretl software (Lemenkova, 2019d), AWK or Octave [START_REF] Lemenkova | AWK and GNU Octave Programming Languages Integrated with Generic Mapping Tools for Geomorphological Analysis[END_REF]. However, the particular feature of this research consists in using GMT both for cartographic visualization and mapping, and for statistical plotting by modules 'psrose' and 'pshistogram'.

Results

Southern segment of the Kuril-Kamchatka Trench

The summary interpretation of the 52 NE-SW cross-section profiles across the KKT in the southern part (highlighted as green line on the Figure 1) shows following results. At the southern region (located in the proximity of the active volcanic spots, see Figure 2), the seafloor depths are found to decrease with increasing latitude gradually while moving northwards. Trench morphology in the northern termination of the southern segment of the KKT, just approaching the Bussol Strait is at the U-trending seafloor rise. Besides, there is indication of the slab subduction along the NW margin of the trench facing the Sea of Okhotsk. Here the trench-parallel, linear system of the southern part of the Greater Kuril Chain Islands (Iturup, Urup, Shikotan and minor chain of islands) provides a natural barrier to the extensive downslope sediment transport from the southern Okhotsk Sea to the trench. To a certain extent, they are trapped behind the chain of islands and further restrict the supply of the sediments to the central part of the trench downslope.

The submarine terraces are presented along the southern part of the trench axis. A common trend is that southern part of the seafloor depths are found to vary considerably, even within neighboring selected profiles. The wedge-shaped body of the trench is being developed in its southern part on the westwards trench slope in front of the Sea of Okhotsk inner trench wall closer to the islands Kunashir, Urup and Iturup from the Kuril Greater Chain. It shows a typical and distinct morphologic impact from the nearby subduction zone. The areas of the submarine terraces interspersed with the floodplains have been observed in the southern part of the trench at -4000 m depth forming distinctive patterns on the landforms located immediately southwards the Bussol Strait. The southern part of the KKT near Kuril Basin (Figure 1) creates conditions for the short sediment transport from the islands between the terrestrial sediments of the Sakhalin Island and the Kurils with marine sediments sinking to the trench. In the southern segment, the sedimentation system goes in a transverse direction of the trench stretching: it brings the sediments from the islands located on the south of Okhotsk Sea: Hokkaido, Kunashir, Iturup, Urup and minor islands of the southern part of Greater Kuril Chain. The southern part of the trench here serves as a sink for the sediment dispersal systems along the active margins of the Kuril Islands. Therefore, it is longitudinally fed by the sediments derived from the southern Kuril. Besides, the location of the compression-extension tectonic slabs as demonstrated on the Figure 2 and the average deformation of the trench's axis is directly affected by the source of earthquakes located in the south of the Greater Kuril Chain.

Northern segment of the Kuril-Kamchatka Trench

The northern part of the KKT (highlighted as red line segment on the Figure 1) reflects in its morphological features the combined effects of tectonic slab subduction, collision, and sedimentation processes and closeness of the large igneous provinces (LIPs) in the northern part of the Pacific Ocean close to the Bering Sea. In particular they are being determined by the rate of the Pacific tectonic plate convergence, sediment supply, and the topography of the subducting seafloor. Fracture zones oriented in NW direction from the Pacific Plate towards the trench affect the sediment deposition in trench. Namely, the sediment deposits filling the trench are mostly controlled by the rate of the Pacific plate convergence towards Okhotsk tectonic plate. The analysis and interpretation of the 62 NE-SW cross-section profiles across the KKT in the northern part shows following results.

The sequence of profiles crossing the northern part of the trench show truncated landforms at the canyon walls of the Greater Kuril Chain, which rise ca. 1000 m a.s.l while southern part of the islands chain (Iturup and Urup islands) show ca. 400 m a.s.l. Processed numerical modelling based on the bathymetric ETOPO1 data from the area around the northern part of the trench identified features of the trench geomorphological system (submarine canyons, trench wedge, submarine ridges, and basins) in the northern part of the trench. The trench-parallel longitudinal sedimentation system carries sediments eroded from the Kamchatka orogenic system to the east, along the Kamchatka Peninsula. These deposits are then moved to the north-eastern part of the trench, shown as red line on Figure 1.

The northern part of the KKT receives the sediments transported in a southwest direction from the downslopes of the Kamchatka and northern islands. Trench-fill sediments are then mostly derived from the volcanic arcs formed by the Kamchatka and northern segment of the Kuril islands, as well as adjacent volcanic basins. From the Kurils the sediments are transported to the northern part of the trench bottom through the set of submarine canyons directed transverse to the axis of the northern KKT filling it by terrigenous sediments.

Orthogonal profiles line Nr. 1 and 7, located north of the KKT in perpendicular direction off the Academy of Sciences Rise (Figure 1) reveal the steeper shape form caused by the seismic characteristics and sedimentary accumulation patterns of the south-east parts of Sea of Okhotsk. The increased number of profiles while moving in northwards direction show shallower depths which illustrates previous discussion on the variations in the sedimentation processes of northern and southern part of the trench, and the landform of the profiles in the respective segments.

Farther down the trench and north-east of the Shiashkotan Island from the Kurils, profile line 42 and 49 cross take the form of an irregularly shaped trough of ca. 8 km width. The trench floor morphology here is characterized by the gentle slope patterns and depths not exceeding 7,400 m. On both profiles, the northern wall of the trench is the island-ward sloping surface of the Kuril islands. Profile line 56 shows mainly flat and parallel form at the shallower depths that extend to about 7,200 m in the seafloor. Further profile line 62 shows even more shallower depth and gentle slope shape following the enlargement of the trench valley starting northwards from the Paramushir Island. Stacks of local small hills and bulges across the trench indicate multiple sediment deposition processes along the trench slope in its northern part.

Discussion

Comparison of the southern and northern segments

Comparing northern and southern parts of the trench, the wedge-like or U-shaped morphology of the trench in two parts south-and northwards from the Bussol Strait are distinct not only from the inner-ward slope facing the Sea of Okhotsk and the Greater Kurils Chain, but also in longitudinal direction along the trench axis. This particular may be explained by the response to the gradual changes in seafloor topography patterns. Another impact can be added by the oceanological factors, such as intensive bottom currents. Diverse types of the sediment deposits filling the trench in its northern and southern part differ in substrate content: more volcanic sediments are in the south comparing to the northern part, which can be influenced by the different seismic settings and sediment transport paths. Steeper landforms are in general observed in the southern part of the trench comparing to those in its northern segment. In both southern and northern parts of the trench, the floor deposits are influenced by the lateral and longitudinal sediment supply.

The results of the comparative analysis of the two distinct parts of the trench located northand southwards from the Bussol Strait show that southern part is deeper reaching -8,200 m depth while northern part has -7,800 at maximal records. The data analysis was performed to examine the spatial variation of the trench geomorphology including the interrelationships of the factors affecting its variation (geodetic, seismic, geologic and bathymetric).

Variations in the earthquakes magnitude and seismisity in the study area that are higher in the south-western part of the trench, as well as to a lesser extent location in the magnetic anomalies located in the north-east, influence the bathymetric patterns that show deeper values in the southern part and geomorphic landforms distribution. The cross-section profiles across the northern part of the KKT show deeper values of the depth and less steep slopes comparing to the southern segment, which refer to the erosional moats and drift of the submarine sediments.

On the contrary, southern profiles along the trench, comparing to the northern segment, located near the intense volcanic area demonstrate erosional moats at -3000 m depths adjusting the Greater Kuril Chain. This reflects a series of recent earthquakes erupted near Shikotan Island in the southern part of the Kuril-Kamchatka Trench. Besides, the anomalous metallogeny of the southern Kuril segment is determined by the deep geodynamics, which provided the impact of fluid energy fluxes from sub-subduction and supra-subduction asthenospheric zones. The profiles in the southern segment of the trench show more complex pattern of the processes of erosion along the upper slope and sediment deposition comparing to the northern segment. Therefore, the landward oriented submarine ridges of the trench facing the Greater Kuril Chain form oblique landform shape towards the coast of the southern Kurils. Southern part of the trench follows the exposition to the erosion processes in NE to SW direction caused by the intense earthquakes located on the south of the Greater Kuril Chain.

Northern part of the trench affected by numerous earthquakes located on the Kamchatka Peninsula (Figure 2) is influenced by the large amount of the accumulated sediments. Necessarily it forms the shallower depths and gentle flat slopes in the morphology of the northern part of the KKT. On the contrary, the southern part is presented by V-shape formed slopes and steeper morphology which is affected by the specific geophysical conditions of the southern part of the Kuril Islands characterized by the magnetized anomaly zones of the oceanic crust. The junction of two different segments of the Kuril Islands, southern and northern, corresponds to a sub-latitudinal magnetic anomaly. The north-east direction of the magnetic anomalies are recorded on the oceanic slope of the trench up to its island slope while the southern segment of the trench axis is oriented in parallel.

The orthogonal bathymetric profiles across the southern and northern segments of the KKT identify two distinct U-and V-shaped morphologic features with affecting dominant processes: (1) in its northern segment, the dominant processes along the Kamchatka Peninsula are sediment deposition; (2) southern part located near the Hokkaido, Iturup and Urup islands and minor island of the Greater Kuril Chain are distinct by the processes of erosion and intense sediment transportation. The explosive volcanism in different parts of the KKT explain a high mass of sediments formed by gradual sediment accumulation.

The formation of the hadal trench is affected by the impacts of local geological, geophysical and oceanological settings that have resulted during the complex process of the tectonic plates movements and subduction. At the same time, there are local variations in northern and southern parts of the seafloor that influence the shape of the slopes. In the subduction zone of the Pacific plate, these cross-sections of the tilted trench illustrate the crustal processes of the subduction and deposition of deep-sea sediments into the trench in its both segments. The sediment dispersal system of the trench forms two distinct types: the first one is a trench-parallel and a second one is a trench-crossing system. The geological parameters visualized on the Figure 2 show fracture lines that predominantly have south-eastern direction showing perpendicular stretching towards the trench general direction.

The geomorphology of the KKT includes main submarine landforms related to the sedimentation processes, volcanic activities, tectonics, geologic formation history and regional oceanographic processes. The mote important of them are as follows: 1) system of connected canyons and channels; 2) gullies, and deep-sea fans located on the slopes; 2) turbidity currents; 3) Drifts, moats and abyssal channels driven by the ocean circulations; 4) rotational deep-seated landslides triggered by the instability of the trench slopes and mass-transportation connected to the geologic underlying rocks structure; 5) craters associated with deep-sea fluid-flow processes.

Historically, the KKT subduction zone experienced a variety of large tsunamis along the trench [START_REF] Zayakin | Catalogue of Tsunamis on Kamchatka[END_REF]. Reports on the seismisity of the KKT are provided by numerous studies [START_REF] Kao | The double seismic zone in Kuril-Kamchatka: the tale of two overlapping single zones[END_REF][START_REF] Gorbatov | Seismicity and structure of the Kamchatka subduction zone[END_REF][START_REF] Ruppert | Seismicity, earthquakes and structure along the Alaska-Aleutian and Kamchatka-Kurile Subduction Zones: a review[END_REF]. The maximum depth of the seismicity along the KKT changes gradually from ca. 600 km to ca. 300 km with latitude increasing in a central part from ca. 50°N to ca. 54°N [START_REF] Gorbatov | Seismic evidence for a mantle plume oceanwards of the Kamchatka-Aleutian trench junction[END_REF], and then decreasing sharply to a depth of 100 km northwards. The rate occurrence of the tsunami on the Shikotan Island, the southern end of the Kuril Island Chain, is one per 250 yr. The most active section of the KKT subduction zone is the southern Kuril Islands and Hokkaido sections with nine Mw 7.5-8.5 earthquakes (NGDC/WDS, 2014, cited by: MacInnes et al., 2016). Larger earthquakes estimated as Mw 9.0 occur only every ca. 500 yr on Iturup Island [START_REF] Iliev | Holocene tsunami traces on Kunashir Island, Kurile subduction zone[END_REF]. Such seismic situation in the KKT makes this area in the north-west Pacific coast a tsunami-prone region [START_REF] Gusiakov | Tsunamis on the Russian Pacific coast: history and current situation[END_REF]. The focal mechanism of the strongest earthquakes (M ≥ 5) in the southern part of the KKT affects the orientation of the trench in this part through the main fracture zones with respect to the direction and type of the geomorphic displacements.

The formation of a variety of landforms including terraces and slopes of the trench reflects the complex action of a range of factors. These include tectonic, sedimentary, oceanographic, biochemical processes and hydrodynamic phenomena. As a result, the morphological character of the seabed in both southern and northern part is depending on the local and regional factors. The Greater Kuril Chain forms a natural barrier dividing the Sea of Okhotsk basin from the Pacific Ocean by the chain of islands and adjacent KKT, as well as separated into two parts by the Bussol Strait. The lateral slopes of the KKT are formed by the cumulative effects of the geologic, seismic and sedimentary factors at the subducting tectonic plate boundaries.

Technically, the comparison of the two parts of the trench was performed by means of the set of the cross-section profiles plotted by GMT in an automatic regime for northern and southern part of the trench. The morphology of both segments was then compared with aim to identify the characteristics of the trench geomorphology.

Conclusion

The Kuril-Kamchatka subduction zone, a part of the circum-Pacific 'Ring of Fire', forms the northern part of the Kuril-Kamchatka volcanic arc in the North-West Pacific Ocean [START_REF] Portnyagin | Mantle temperature control on composition of arc magmas along the Central Kamchatka Depression[END_REF][START_REF] Gorshkov | Catalog of the Active Volcanoes of the World Including Solfatara Fields[END_REF]. The subduction rate of the Pacific plate beneath the Eurasian plate is ~79 mm yr-1 [START_REF] Demets | Current plate motions[END_REF][START_REF] Bindeman | Large-volume silicic volcanism in Kamchatka: Ar-Ar and U-Pb ages, isotopic, and geochemical characteristics of major pre-Holocene calderaforming eruptions[END_REF] or 8-9 m per century along the KKT [START_REF] Nanayama | Unusually large earthquakes inferred from tsunami deposits along the Kuril trench[END_REF]. This causes high seismic and volcanic activities, making this region one of the most tectonically active, seismic regions of the world. More specifically, one of the most active volcanic arcs in the world is located on the eastern coast of Kamchatka [START_REF] Gorbatov | Seismic evidence for a mantle plume oceanwards of the Kamchatka-Aleutian trench junction[END_REF]Pinegina et al., 2000). A number of studies analyzed earthquakes across the region of the southern Okhotsk Sea in in the adjusting Kamchatka Peninsula. Nowadays, there are 29 active, and ca. 300 extinct volcanoes located on the Kamchatka Peninsula near the KKT [START_REF] Solomina | Multiproxy records of climate variability for Kamchatka for the past 400 years[END_REF].

The KKT belongs to the Chilean tectonic subduction type, which has a gentle subduction dip advancing at a speed of ca. 2 cm yr-1 and inter-seismic elastic shortening of 1-2 mm yr -1 (DeMetz et al., 2010). Strong lateral velocity in the shallower mantle wedge accounts for both the compressional subduction tectonics and back arc compression in the KKT. This results in the seismic-velocity anomalies in the mantle under the KKT, as shown on the tomographic images by [START_REF] Yoshida | Trench dynamics: Effects of dynamically migrating trench on subducting slab morphology and characteristics of subduction zones systems[END_REF]. Despite the age of the Pacific plate, there is no sharp variation of the age on the seafloor along the KKT [START_REF] Renkin | Depth and age in the North Pacific[END_REF], and the old Pacific Plate is rejuvenated at the north of the KKT around the Meiji Guyot seamount.

Southern part of the KKT differ, as proved by recent findings [START_REF] Khomich | Geology, magmatism, metallogeny, and geodynamics of the South Kuril Islands[END_REF] where it is demonstrated on the example of South Kuril that intense fluid thermal fluxes in the continental lithosphere cause of the formation of magmatic chambers and the development of volcanism and multi-metal ores. Over 700 earthquakes with hypo-centers >50 km are recorded in the KKT focal zone [START_REF] Beck | Rupture process of the great 1963 Kurile Islands earthquake sequence: asperity interaction and multiple event rupture[END_REF]. Individual earthquakes show large variations in seismic slip and distribution of foreshocks and aftershocks that shows spatial heterogeneity in the stress level and geological settings along the tectonic plate boundary [START_REF] Ruff | The rupture process and asperity distribution of three great earthquakes from long-period diffracted P-waves[END_REF].

Northern part of the KKT located northwards from the Bussol strait presents a geographically complicated region with smaller islands than in other parts of the Kuril volcanic arc [START_REF] Macinnes | Paleotsunamis from the central Kuril Islands segment of the Japan-Kuril-Kamchatka subduction zone[END_REF]. This area is notable for the abnormally high heat flow in the ocean floor. Reduced thermal thickness of the Pacific Plate upon its subduction into the northern KKT indicates underlying mantle plume and point out that thermal thickness of the underlying plate is lesser than expected comparing to the normal oceanic plate of such age [START_REF] Smirnov | The terrestrial heat flow of Kamchatka[END_REF][START_REF] Selivestrov | Structure of the oceanic floor near Kamchatka and the geodynamics of the zone of Kuril-Kamchatka and Aleutians trenches Joint[END_REF]Smirnov & Sugrobov, 1980a;[START_REF] Smirnov | Terrestrial heat flow in the Kurile-Kamchatka and Aleutian provinces-III, Assessment of temperature at depth and thickness of the lithosphere[END_REF].

Figure 1 .

 1 Figure 1. Study area: bathymetric map of the Sea of Okhotsk and Kuril-Kamchatka Trench.

Figure 2 .

 2 Figure 2. Geological settings of the study area: seismisity and earthquakes, geological lineaments and tectonic slabs in the Sea of Okhotsk and Kuril-Kamchatka Trench.

Figure 3 .

 3 Figure 3. Statistical 3D histograms showing depths distribution in the southern part of the Sea of Okhotsk and Kuril-Kamchatka Trench.

Figure 4 .

 4 Figure 4. Statistical 2D histograms and rose diagrams showing comparative depths distribution in the southern and northern part of the Kuril-Kamchatka Trench. Rose diagram shows the aspect of the slopes.

Acknowledgements

This research was funded by the China Scholarship Council (CSC), State Oceanic Administration (SOA) Marine Scholarship of China, Grant#2016SOA002, Beijing, China.

Conflict of Interest:

The author declare that they have no conflict of interest.

Ethical approval:

For this type of study formal consent is not required.


Marc Deneire

This paper attempts to question the image of a one-sided monolithic French resistance to the spread of English. For this purpose, a corpus of over one thousand articles from newspapers and magazines traditionally associated with different political views such as Le Monde and Liberation for the left and Le Figaro for the right, as well as newsletters and other materials published by the corporate world and trade-unions is analysed using Hyperbase for a principal component analysis and Alceste for a descending hierarchical classification that breaks the corpus down in different classes. . The purpose of the paper is to establish relations between various social strata, institutional environments, ideological positions, and economic interests on the one hand, and the different attitudes towards English, ranging from enthusiastic adoption by the business world to fierce ideological opposition based on centuries-old forms of anti-Americanism and linguistic protectionism. The results show that traditional cultural resistance to English is limited to a small set of national newspapers, regardless of ideological orientation. At the opposite end, business-oriented newspapers and magazines tend to encourage the use of English. Finally, the issue is almost completely absent from the widelyread regional press, which suggests that it is of minor importance for most of the French in their daily lives.

Through this study, I hope to give a more nuanced and diverse picture of French attitudes towards English than that which is usually presented in the English-speaking press and in academia.

Introduction

French efforts to protect their language against the invasion of English have often met with scathing criticism in the English-speaking world which sees these as many signs of French dirigisme, Jacobinism, and democratic deficit. The first piece of language policy, the Edict of Villers-Cotterêt, which intended to progressively replace Latin with French, is described as a first step in the imposition of French upon a largely multi-lingual population.

Another favorite target in conferences and publications is the Académie Française whose "irreproachable uselessness," in the words of French linguist Robitaille (2002: 15) is often misrepresented as a guardian that holds the French language back instead of letting it live its own life as English does. For Carla Power (2007), the members of the Academy "are given swords and charged with defending the sanity of the French language," and Campbell writes in the Sunday Times that while "English borrows liberally from French, (. . . ) the French are less laissez-faire: a hallowed academy of elders known as "immortals" zealously polices the official lexicon against English intruders and 'Globish'" (cited in Estival and Pennycook 2011: 328). Even David Crystal argues that the supposed role of the Academy in "forbidding" loanwords has, as it were, constrained the French language in a stand and prevented it from developing. For him, the absence of an academy has allowed English to develop freely: "What would have happened to the English language if it had forbidden the arrival of loanwords? It would be a language a tenth of the size it is today, and it would never have become the language of science. English has, like a vacuum cleaner, sucked in words from 350 languages during the past 1,000 years" (2005: 10). Finally, French language policy has often been ridiculed for its limited success. For example, the 1994 Toubon law, which aimed at protecting monolingual workers and consumers from documents and labels they don't understand, has been criticized for its limited success (Kibbee 1993: 210) and its naïveté when faced with the users linguistic creativity, especially in advertising (Martin 2007: 171).

Even though these mostly American reactions against French language policy are often clearly biased and uninformed, French reactions against English do exist, as recent articles and books by linguists and commentators decrying the use of English words attest. [START_REF] Flaitz | The Ideology of English: French Perceptions of English as a World Language[END_REF], Martin 1998[START_REF] Deneire | English in the French workplace: Realism and anxieties[END_REF] for field studies and Euridyce 2008 for statistics in education). In the present paper, I will use an extensive corpus of newspapers and magazines to offer a more nuanced picture of French attitudes toward English today and to give a mmore complex picture than the often simplistic and reductionist views discussed above.

Theoretical assumptions

In choosing media, I follow the footsteps of a large number of discourse analysts who take for granted that newspapers and magazines reflect and reproduce opinions and ideologies [START_REF] Fairclough | Critical Discourse Analysis: The Critical Study of Language[END_REF]: 46, Blommaert 2005: 3). As Van Dijk has argued (1988: 24), media discourse instantiates ideologies as "mental structures" in social situations. Media are economically highly dependent on their readership for survival, as regular efforts by major newspapers (Le Monde, Libération) to change their presentation and adapt to their readers' modes of consumption attests [START_REF] Motte | Nouvelle version du Monde.fr. News Resources[END_REF]. Therefore, we may assume a dialectic relationship in which: (1) media texts reflect the collective view of a large number of their readers [START_REF] Bell | The Language of News Media[END_REF]; (2) they affect the horizons of their readers through the selection of information, textual structure; and processes of foregrounding and backgrounding; and (3) they frame the world in particular ways. In the words of A. Bell, "Media 'discourse' is important for what it reveals about a society and because it contributes to the character of society" (1998: 64). Finally, we can also assume that the existence of several major newspapers is a reflection of different worldviews that circulate in society, otherwise, they would not survive. For this reason, I included all major French newspapers in my corpus.

Media are organized differently from country to country; however, in most Western nations, a distinction can be made between the general press that contains political information and commentaries and is read by a relatively small educated elite on the one hand, and the popular press that contains almost no such information but rather local events, gossip (in French: les potins) and sports (see older and more recent surveys in Bourdieu, 1979: 519, Dumartin and Maillard, 2000, and PAR66 One, 2011). In France, the former includes most national newspapers (Le Monde, Le Figaro, Libération), and the latter consists of the regional press. Tabloids equivalent to the British Sun or Daily Mirror have disappeared completely in France and been replaced with popular magazines of which the French are avid readers (an average of 7.3 magazines per person every year; [START_REF] Duval | La presse -La presse et ses lecteurs[END_REF]. Some magazines also focus on general information (Le Point, L'Express) or on specific information (Capital, (economy) L'informatique, (computer science)). As table 1 shows, 50 percent of the French above the age of 15 read a newspaper everyday: 36 percent of them read a regional newspaper everyday (63 percent at least once a week) while 15,5 percent, that is less than one person out of six, read a national newspaper ever day. Thus, there is a clear divide between the readership of the major newspapers that consists of a relatively small cultured elite, and that of the regional press that mainly includes workers, farmers, and retired people. Finally, an increasing number of people read the free newspapers (Metro, 20 minutes) that become available in most larger cities. However, these are not represented in the corpus for this study.

Sampling and methodology.

The corpus for this study was built with a concern for diversity with the criteria outlined above in mind. Articles from magazines were also included because, as mentioned above, the latter represent an important part of what the French read every day. Using the academic databases Nexis Lexis and Europress, I selected that articles that contained the words "anglais", "français", and "langue" in the newspapers listed in table 2 between 2005 and 2011. The articles that were obviously unrelated to the topic (e.g., concerning culinary matters or fashion) were removed. This yielded a corpus of more than 1000 articles, that is, around 831 thousand words. 43), l'Est Républicain (85), etc.

I used three complementary tools for analysis: Wordsmith Tools (version 4) for word lists and the extraction of collocates, Hyperbase to establish the lexical distance (that is, the number of words that are present or absent in each part of the corpus and the frequency of these words; Bonin and Dallo 2003: 393) between the different newspapers and magazines and Alceste for factor analysis. Both Alceste and Hyperbase perform correspondence factor analysis, a multivariate clustering technique that detects associations and oppositions between words and/or text segments and associates the resulting clusters with specific parts of the corpus, in this case, specific newspapers and magazines. The Alceste program provided confirmation of this analysis using a descending hierarchical classification whereby the corpus is first split into two parts, and then each part is further split into parts in an iterative way until a number of irreducible "classes" are produced.

Analysis and results

A first test using lexical distance in Hyperbase shows a clear split between the general press (Le Monde, Le Figaro, etc.) in the lower part of the tree in figure 1 and the economic press in the upper part, with the regional press squarely associated with the latter.

Surprisingly, newspapers that are at opposite ends on the ideological spectrum are very close in this corpus, that is, as a close reading of the pertinent articles from these newspapers confirms, they basically share the same worldview concerning language matters and their opposition to English. A closer look at the corpus allows to explain these results: (1) It appears that traditionally "progressive" newspapers and magazines (Le Monde, Le Monde Diplomatique, Marianne) are often very conservative when dealing with cultural and language issues; (2) English is often associated with Americanization which commentators from both the left and the right strongly resent, and (3) the circle of commentators who have "the authority" (in Bourdieu's sense; 1991: 109) to express their opinion is very small; as a result, the names of "authorized" scholars such as Claude Hagège and the late Claude

Duneton appear in all national newspapers. All things considered, this first analysis demonstrates that the concerns of this very small elite is not shared by the rest of the population. Indeed these articles are completely absent in the regional press. The results of the second analysis using Alceste confirm the results of the first analysis and help us further refine them. The analysis resulted in 5 classes (figure 2): classes 2 and 3 cluster around the economic press with slightly different focuses, one on economic strategies, that is, the role of English in business communication, management, and corporate social responsibility, and the other on human relations such as employability, job hunting, etc. The regional press (class 4) is closely associated with these concerns, especially in the areas of 1 For Bourdieu (1979: 518) the elitist character of the general press is not surprising. Indeed, "the reading of national newspapers, especially the most legitimate ones, is closely related to the educational level as a result of statutory attribution. A recognized school certificate strongly contributes to the feeling of rightfully belonging to the legitimate political and cultural universe, including feeling of being entitled to read a legitimate newspaper.

employment, schooling and training. The general newspapers address two main themes: cultural politics (class 1), including language matters such as the defense of the French language, reactions against English, and traditional anti-Americanism, and (class 5) the worlds of music and literature. The world of music is often blamed for its "uncritical" adoption of English. English literature (or, as the French like to say, "la langue de Shakespeare") is used to contrast the noble and pure language of the great authors with the language of globalization, "Globish" and "sabir" (pidgin) that is making inroads into the French communication sphere.

Figure 2: Descending hierarchical analysis (Alceste)

Here are some of the words that are most specific of each of the classes: The two-dimensional projection of the results offered by Hyperbase (figure 3) shows that the different classes overlap considerably. There is almost complete overlap between classes 2 and 3 on the left, and 1 and 5 on the right, while class 4 overlaps with both groups, but considerably more with the first group. Thus the graph shows a strong opposition (30% of the variance) between the left and the right half on the horizontal axis, that is, between the general press and the economic and regional press, and a weaker opposition between the top and the bottom half, that is, between the regional press and the national press, be it general newspapers (bottom right) or economic newspapers and magazines (bottom left) (18% of the variance). The important overlap between economic and regional press is also confirmed with a smaller area of overlap between regional and general press, mainly in the domains of education and culture. Emphasize negative things about them.

De-emphasize negative things about us

De-emphasize positive things about them" I used the term "neutral" for the economic and regional press because attitudes cannot be labeled positive, that is, there is no clear support for the use of English. Rather, they present their viewpoint as realistic, that is, as the result of a socio-linguistic context that is being imposed on us all. The media adopt a more laissez-faire attitude in which French people are encouraged strategically to adapt to a world in which English has become a necessary tool for success and economic survival. Whether this attitude is less ideological is of course a matter of definition2 , but, in any case, the term "acceptance" would be more appropriate than enthusiastic support.

As a next step in the analysis, Wordsmith was used to detect the most common collocations and colligations in the corpus. Colligations, or grammatical constructions in general (l'anglais est devenu, qu'on le veuille ou non), are more rare but tend to be more productive in terms of ideological positioning than collocations (langue de Shakespeare, langue de communication) which tend to be more descriptive.

Concordances using these constructions were produced with the Hyperbase program.

Below is a list of the main findings3 : In short, newspapers unsurprisingly present English as a language of wider communication that, as such, is used for practical purposes, but it also has become a language of prestige, especially among the young and the professionally mobile.

A. Functions of English in today's world (l'anglais est devenu …; English has become)

B. The "inner" qualities of English

In business newspapers and magazines, English indexes images of dynamism, internationalism and modernity. Here again, even though English is often presented as "just a tool," symbolic values are at least as important as instrumental values. As a result, English often becomes a "company language," not for its practical value but for the image of the company:

 English is the language of business. Using it makes us sound more However, a number of articles mention the stress that is generated when a company "turns to English." Trade unions are particularly active in organizing meetings and conferences where they explain that a large number of managers lose their jobs after takeovers by international companies. One case often mentioned is that of a France Telecom engineer who committed suicide after being immersed against his will in an international context where his low proficiency in English made him unable to do his job. Another example is that of a PSA (Peugeot-Citroën) manager who said that the use of French in corporate meetings had been accepted in the past, but that it would no longer be tolerated after General Motors had purchased 7% of the company's shares (both cases heard by this author when attending these meetings). Here are some statements from our corpus that illustrate these anxieties:

 Foreign languages (i.e. English) generate "stress and insecurity," "mental fatigue," "possible discrimination in career evolution and in recruiting," and D. English as an international language is considered as a "nonlanguage"

It is "not the language of Shakespeare" (106 occurrences) but rather "Globish," a term coined by former IBM executive Paul Nerrière in his popular book entitled "Parlez Globish. Don't speak English." (2011).



The harm does not come from English, but from the American-like « sabir » … This kind of soft rubber American-like thing that contaminates the language. What exasperates me is that the French crawl to that American sabir. (Le Figaro)



The « sabir » has always exerted a beguiling charm among the colonized because it pulls the wool over their eyes. Ours is no exception. (Le Figaro)



French administrations are forced to work using this « sabir » for « European coordination », to bend to the Commission's obstinate americanophonia.

(Le Figaro)

The term "sabir" (pidgin) is also frequently used (30 occurrences) to indicate that the English language used in daily communication is of lower quality. This term is particularly shocking when used by linguists and sociolinguistics such as Claude Hagège, whose "normal" agenda as a sociolinguist, one would expect, is to show that all languages are equally valid.

In our corpus the word "sabir" not only refers to language but also to a reaction against American cultural imperialism. The use of English is perceived as a sign of submission; for Jean Dutourd, for example: "Everything started when the Americans won the war in our place."

E. The invasion of English: Trojan horse or perfidious Albion

American imperialism is presented as a Trojan horse, one that numbs the French before invading European space. The British, on the other hand, in their traditional role as a "perfidious Albion"4 , are accused of taking advantage of their entry to the EU to anglicize

Europe. The difference between the two countries is often blurred though, and presented as "Anglo-Saxon influence":



The EU of six with four languages, of which French was a working language, became, after 20 years, in 1973, the EU of nine where English, the

F. Images of French

Adopting a strategy of distinction (Bourdieu 1979, E. Hall andM. Hall 1990) and in line with Van Dijk's ideological square mentioned above, authors and commentators present the French language as the positive mirror-image of English. As opposed to the language of business and science, it is the language of conversation (i.e., of culture and not communication, of alterity not of egoism) that is endowed with human character and democratic values. Following the old clichés shaped during the 17 th and 18 th centuries, French continues to be presented as inherently rational and English as inherently pragmatic:

 Its traditional calling, ever more precious in the global market of a language of conversation, civil and hospitable among the non-businessed and the nonspecialists. (Le Figaro)



The opposition is between one language, English, that privileges concrete and detailed observation, and another, French, which generalizes on the basis of particular cases and privileges logical articulations (Hagège). (Les Echos)

Finally, unlike English which has turned into Globish and/or a number of pidgins, French has kept its purity, even though, in spite of a heroic resistance, it is now being contaminated by English:



The French language is not an object, it is a passion. It is a besieged fortress, a beauty that is being butchered, a purity that is being polluted. (Le Monde)

Conclusion

In recent years, the French have come to advocate multilingual policies within Europe as a new strategy in the defense of the French language. Many would now agree with the Martiniquais author Patrick Chamoiseau when he states in one of the articles in the present corpus that "French will remain powerful and magnificent where all languages are powerful and magnificent," that is, where all languages receive equal respect and recognition. This study shows through the press that a majority of the French, those who read the regional press and magazines, share Chamoiseau's opinion and do not see language contact between English and French as language conflict. However, the opinions expressed in the general press remain unchanged; if anything, they have grown more radical in recent years under the influence of a diminishing number of dominant voices. There are other voices in the French-speaking world, mainly outside Metropolitan France, that call for linguistic diversity, dialogue, and mutual enrichment. Besides Chamoiseau, we can mention Tahar Ben Jelloun, Amin Maalouf, Assia Djebar, and others, but these voices remain suspiciously absent from the major French newspapers. This study has shown that the press that is traditionally read by foreign scholars, journalists and commentators reflects the opinions of a very small and very conservative French cultural elite, not that of the majority of the French people. Indeed, most if not all the negative comments we cited here are from general elite newspapers, none from the regional press. This may provide an explanation for the strangely 5 biased views that are often heard and read concerning French views towards English.

  For example, Claude Hagège's Combat pour leFrançais (2008) and his numerous newspaper articles that are used in my corpus continue a line of conservative essays that started with the late Etiemble's Parlez vous Franglais? Along the same lines, philosopher Michel Serres (who lives in the United-States) asserted that "We see more English words on the walls of Toulouse today than [we saw] German words during the occupation" (2013), attesting to the polemical nature of these arguments. Yet, as many studies and statistics have demonstrated, most French people claim to be open to the learning and use of the English language (see Flaitz

  Figure 1: Lexical distance between different newspapers and magazines (Hyperbase).

Figure 3 :

 3 Figure 3: Factor analysis of terms and publications. See terms above



  … a prerequisite to find a job (Le Figaro)  ... the corporate language in many companies (Le Figaro)  … the language of science and publication (Le Figaro)  … the sole vehicle for scientific thought in the world (Le Monde)  … the symbol of internationalism (Le Figaro)  … the language of communication (Le Monde)  … the language of the EU (Le Monde, Le Point)  … la langue du cool and of mainstream American culture (Le Point)  … the indispensable language for any European citizen (L'Est Républicain)  … the vernacular language … today's Latin (L'Expansion)

  credible, more aggressive, especially in marketing. (Les Echos)  Chris Viehbacher (CEO Sanofi-Avensis) speaks the language of the financial community and attempts to erase the franco-French (fr: franco-français) image of the company. (L'Express)  Entre-temps, bien sûr, l'anglais s'impose peu à peu. C'est vrai dans les domaines déjà fortement américanisés que sont les sciences hard, la médecine soft, l'écologie green, l'alimentation light, mais aussi l'entertainment avec ses pitches, l'information avec ses lives, le business avec ces CEO, sans parler de tout le domaine d'Internet où la langue anglaise est constamment réinventée par les geeks et autres nerds (sic, no translation ; Le Point).

"

  costs in training." (Marianne)  An intranet site in English (Areva) "generates additional stress because it takes more time to read and understand". (Le Monde)  Stress can be assimilated to a new form of slavery. (L'Expansion)  The stress generated by this measure [adoption of English] initially had negative consequences on the productivity of a number of employees. (Le Monde) C. English as a necessary evil ("Qu'on le veuille ou non …") The common expression "Qu'on le veuille ou non …" (17 occurrences) refers to a kind of forced acceptance, often a sense of inevitability. This feeling is dominant in the economic press and in magazines, it is less present in the general press that still has faith in the fight against English.  It's the clay pot against the iron pot. We are expected to be European, and therefore to speak English as it is the sole idiom of the new Europe. (Le Figaro)  Whether we want it or not, soft power now speaks English [about music] (Le Point)  Whether we want it or not, whether it pleases us or not, English is now the common language (langue véhiculaire) of the business world. (Les Echos)  English has become, … the Esperanto of the planet. (Le Monde)

Table 1 :

 1 Newspaper readership in 2011

		(PQR66 One, 2011)*
	Readership	In 1000	In %
	Total	25.54	50.2
	Regional press	18.55	36.5
	National press	7.892	15,5
	Free press	7.668	11,7

*Based on 35600 interviews, of which at least 300 in each of the 96 départements

Table 2 :

 2

The corpus (with approximate number of articles)  National newspapers -General Le Monde (60), Le Monde Diplomatique (36), Le Figaro (80), Libération (40), l'Humanité (57).  Economic/business newspapers La Tribune (48), Les Echos (136), Informatique (43), L'Expansion (22)  National magazines Le Point (50), L'Express (42), Marianne (56)  Regional newspapers Le Télégramme (50), La Nouvelle République du Centre Ouest (57), Ouest-France(

  Class 2 : capital, commercial, financier, Asie, Chine, international, entreprise, dirigeant, dollar, marché (capital, commercial, financial, Asia, China, international, enterprise, leader, dollar, market).

	Class 3 : humain, évolutif, emploi, cadre, candidat, embaucher, évaluer, collaboration,
	compétent.( human, progressive, employment, manager, candidate, hire, evaluate,
	collaboration, competent)
	Class 4 : primaire, secondaire, obligatoire, enseignement, établissement, études, réussite,
	section, séjour, enseigner, bénéficier. (primary, secondary (education) compulsory,
	teaching, school, studies, success, section, stay-abroad, benefit)
	Class 5 : Chanteur, auteur, album, écrivain, film, lecteur, romancier, musical, concert (singer,
	author, album, writer, film, reader, novelist, musical, concert.)

Class 1: africain,

fédéral, fondamental, hégémonie, domination, danger, combat, fonctionnaire, identité, peuple, république, résistance, gouvernement (african, federal, fundamental, hegemony, domination, danger, fight, civil servant, identity, people, republic, resistance, government)

  To spread words … What Americans call "soft power." A power that is no longer based on arms, but on "meanings" which Americans noticed were more effective than physical confrontation.(Le Point)

	
		Trojan
	horse of American influence … (Le Figaro)
		His success "Dance" … makes us forget that since "Je t'aime moi non
	plus …" the francophonie never managed to break into Albion (Libération)
		Concerning M. Serres: "Returning from 10 trips, here is what he sees:
	more English words on the walls of our cities or in the headlines of our newspapers
	than German during the occupation" (L'Humanité)

Indeed, Marxist theorists would probably call it "false consciousness"; see e.g.,Eagleton (1991:89).

Note that these are my own translations, which are deliberately as close to the French as possible, with an unavoidable loss of idiomaticity.

For a history of the term, see http://www.historia.fr/web/expressions/la-perfide-albion-21-10-2010-44359


Sara Mehar

Sidi Mohammed Senouci

Ali Kies
email: kies_ali@univ-usto.dz

An Optimized Roadside Units (RSU) Placement for Delay-Sensitive Applications in Vehicular Networks

Keywords: Covering location optimization, real-time applications, delay constraints, genetic algorithm, deployment cost. I

Over the last few years, a lot of applications have been developed for Vehicular Ad Hoc NETworks (VANETs) to exchange information between vehicles. However, VANET is basically a Delay Tolerant Network (DTN) characterized by intermittent connectivity, long delays and message losses especially in low density regions [1]. Thus, VANET requires the use of an infrastructure such as Roadside Units (RSUs) that permits to enhance the network connectivity. Nevertheless, due to their deployment cost, RSUs need to be optimally deployed. Hence, the main objective of this work is to provide an optimized RSUs placement for delay-sensitive applications in vehicular networks that improves the end-to-end application delay and reduces the deployment cost. In this paper, we first mathematically model the placement problem as an optimization problem. Then, we propose our novel solution called ODEL. ODEL is a two-steps technique that places RSUs only in useful locations and allows both vehicle-to-vehicle and vehicle-toinfrastructure communication: (i) the first step is comprehensive study that looks for the RSUs candidates locations based on connectivity information, and (ii) the second step uses genetic algorithm and Dijkstra algorithm to reduce the number of RSUs based on the deliverance time requirement and the deployment cost. We show the effectiveness of our solution for different scenarios in terms of applications delay (reduced by up to 84%) and algorithm efficiency (computation performance reduced by up to 79% and deployment cost reduced at least by up to 23%).

INTRODUCTION

In the latest years, the innovative progress in both transportation and communications technologies made information exchange possible on roads using smart cars [START_REF] Lorenzo | Vehicular Technologies -Deployment and Applications[END_REF]. Through communication, Vehicular Ad Hoc Network (VANET) is created. VANET is composed of a set of high mobile nodes, which results in a frequently changing network topology with intermittent connectivity. In VANET, there are two possible ways to communicate: vehicle to vehicle (V2V), vehicle to infrastructure (V2I) or both called V2X [START_REF] Almeida | [END_REF]. V2I communication capabilities have a huge impact on the network reliability and information exchange [START_REF] Lorenzo | Vehicular Technologies -Deployment and Applications[END_REF]. To enhance the network coverage and hence the quality of services, the infrastructure must be optimally installed. Infrastructures deployment is not trivial and needs intensive investigations. In this paper, we focus on road-side units (RSUs) placement. RSUs act as wireless access points. We studied and analyzed the existing works to find out their limitations. Some works focus on urban scenarios and propose to put RSUs in intersections to communicate information to a large number of cars; some others suggest distributing RSUs randomly or uniformly on the road. In addition, most of related work limit the communication to the RSUs only instead of using both V2I and V2V communications. Consequently, initial RSUs locations are not optimized to support frequent network disconnection. Hence, they are not adapted to delay-sensitive applications as the delay constraint is not respected.

In this work, we propose a novel location solution called ODEL (An Optimized Roadside Units Placement for Delay-Sensitive Applications in Vehicular Networks). The later is a two-steps solution that optimizes RSUs deployment for vehicular networks applications with delay sensitive constraints. In the first step, we develop an algorithm to find the most relevant RSUs candidate locations based on network connectivity and hence avoiding the useless positions with high density where vehicles can communicate with each other's without using any additional infrastructure. In fact, from a given map and traffic information (density, speed), we calculate the probability of connectivity in each road segment. Then, we choose RSUs candidate positions in segments' midpoints with low connectivity probability. In segments with high probability of connectivity, the information is exchanged using V2V communication capabilities. The second step is an optimization phase in which we select the best RSU locations for final installation based on both the application constraints in terms of delay and the infrastructure deployment cost. For that, we combine two optimization algorithms: Genetic heuristic [START_REF] Maric | An Efficient Genetic Algorithm for Solving the Multi-Level Uncapacitated Facility Location Problem[END_REF] and Dijkstra algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] as detailed in Section IV. The results show that ODEL allows reducing significantly both the communication delay and the deployment cost. This paper is structured in five sections: In the second Section, we introduce the most important related work about Road-Side units placement. We give the mathematical modeling and the corresponding complexity of RSUs location in Section III. In Section IV, we describe the main steps of the resolution and evaluate the performances of our solution in Section V. Section VI summarizes and concludes the paper.

II. RELATED WORK

Road-side units positioning is a covering location optimization problem. In covering location problems, the goal is to find the optimal positions to cover all the clients (vehicles), while taking several constraints into account such as deployment cost and applications quality of services requirements. A plethora of work is done to cover the field of RSUs optimized siting. In [6][7][8] [START_REF] Liu | File downloading oriented Roadside Units deployment for vehicular networks[END_REF], the authors aim to place RSUs optimally in order to enhance connectivity. They consider intersections as best locations in urban scenarios since the density in intersections is usually higher and information can propagate in all directions. In [START_REF] Cavalcante | Roadside unit deployment for information dissemination in a VANET[END_REF], the authors aim to improve data dissemination in an urban area. They model the location problem as a Maximum coverage with Time Threshold Problem (MCTTP [START_REF] Trullols | A Max Coverage Formulation for Information Dissemination in Vehicular Networks[END_REF]). To optimally deploy RSUs to cover the maximum vehicles in the road, they use a genetic heuristic to solve the MCTTP and get the best RSUs placement. In [START_REF] Aslam | Optimal roadside units placement in urban areas for vehicular networks[END_REF], the goal is to find the optimal positions for RSUs to cover the vehicles in urban roads and reduce the delay of safety messages propagation. The authors consider intersection positions as potential locations to deploy RSUs. They mathematically model the problem and use two methods to resolve it: (i) analytical Binary Integer Programming (BIP) [START_REF] Altınel | Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks[END_REF] to find best time to broadcast in the whole area, and (ii) Balloon Expansion Heuristic (BEH) method to find best time over each route. In [START_REF] Sun | Roadside Units Deployment for Efficient Short-Time Certificate Updating in VANETs[END_REF], the authors propose a cost-efficient RSUs deployment scheme. They aim to update security certificates in urban area within short delay using the deployed RSUs. In this scheme, they suppose that each vehicle can communicate with RSUs in bounded driving time whatever its actual position, and the extra overhead time used for adjusting routes to update certificates. They model the problem as a setcovering problem and use the polynomial-time approximation algorithm called "Greed Set Cover" [START_REF] Aloisio | FPGA implementation of a greedy algorithm for set covering[END_REF] to solve it. In [START_REF] Liu | File downloading oriented Roadside Units deployment for vehicular networks[END_REF], the authors propose an RSUs siting strategy for file downloading in the case of urban scenario. The main goal is to guarantee file downloading success ratio and delay requirement with the lowest deployment cost. They also use intersections as RSUs initial placement and consider only V2I communications. To improve file downloading success ratio, they first model the inter-meeting time between vehicles and RSUs as a time continuous homogeneous Markov chain with two states (disconnected and connected to RSU). Then, they deduce the objective function that relates RSUs deployment and file download ratio success and delay. After that, they model the road network as a weighted undirected graph where each edge represents the average passing time on the corresponding road. Finally, they use the depth-first traversal algorithm to get optimal placement to deploy RSUs. However, the authors in [START_REF] Cavalcante | Roadside unit deployment for information dissemination in a VANET[END_REF][7] [START_REF] Sun | Roadside Units Deployment for Efficient Short-Time Certificate Updating in VANETs[END_REF][9] consider only V2I communications, which introduce a large delay when no car is available to drive toward the RSUs. In [START_REF] Xiong | Optimal Roadside Gateway Deployment for VANETs[END_REF], the authors study the problem of deploying gateways to provide the required coverage while minimizing the deployment cost in urban area. They formulate the problem as a Maximum Coverage Problem (MCP) [START_REF] Apollonio | The maximum vertex coverage problem on bipartite graphs[END_REF].They extract and analyze traffic data over several hours in a given area. They divide the studied area in uniform zones and count the number of vehicles entering and leaving each zone for each time unit to obtain the distribution of transition probability between two zones. The later is used to find the candidate zones to deploy gateways. Finally, they develop their own heuristic algorithm called "MobGDeploy" to find the optimal gateways locations. However, the authors try to cover the maximum clients by choosing to put gateways in the zones with high density; so the solution does not take into account the delay requirement especially in low-density cases. Such a solution is also not efficient to transmit safety messages for example. In [START_REF] Lochert | Data aggregation and roadside unit placement for a vanet traffic information system[END_REF], the authors aim to optimize the travel time between neighbors landmarks. They try to optimally find the best RSUs positions in urban area in order to efficiently aggregate traffic information on the road and use it to improve route planning. They use genetic algorithm to find best positions. For each iteration of the genetic algorithm, they use NS2 [START_REF]The Network Simulator -ns-2[END_REF] simulator to evaluate the current solutions and to estimate the required travel time by simulation. However, they choose a random candidates deployment positions, which increase the complexity of the solution and does not take into account density information. In [START_REF] Rashidi | Placement of Road Side Units for floating car data collection in highway scenario[END_REF], the authors' goal is to study the size of the gaps between RSUs to improve data collection and delivery ratio in a highway scenario. They initially distribute RSUs along the road equidistantly and formulate the distance upper bound between RSUs. Then, they use Omnet++ simulator [START_REF]Omnet++[END_REF] to evaluate the considered system under realistic settings to find the best gap between every two successive RSUs. In [START_REF] Aslam | Optimal roadside units placement along highways[END_REF], the authors' goal is to minimize the average reporting time of information to a given RSU. To effectively collect data in highway scenario, they propose to use a uniform initial RSUs distribution (each twice radio range distance). To reduce the deployment cost and get the best RSUs placement, they develop a heuristic based on balloon expansion method. However, the authors in [START_REF] Rashidi | Placement of Road Side Units for floating car data collection in highway scenario[END_REF] and [START_REF] Aslam | Optimal roadside units placement along highways[END_REF] propose their solution only for a single road. In addition, the uniform distribution is not the best initial distribution, as it does not take into account the density of the cars in the road and increase the delivery delay of information. In [START_REF] Ho | Stochastic Model and Connectivity Dynamics for VANETs in Signalized Road Systems[END_REF], the authors model the network connectivity using a fluid model and a stochastic model. They propose RSUs assignment as an application of their model. The fluid model is used to compute the network density. The stochastic model takes into account the vehicles' random behavior. This model is different than the Poisson-arrival-location model (PALM) described in [START_REF] Massey | Networks of infinite-server queues with nonstationary Poisson input[END_REF]. In fact, this model is designed for urban scenarios; it takes into account traffic light and interactions between vehicles. It allows determining the degree of connectivity in a given road. Then, it assigns the RSU to enhance the connectivity where the number of connected nodes is lower than a threshold. However, the authors find the best positions to place RSUs although they do not optimize the number of RSUs. In [START_REF] Kafsi | VANET Connectivity Analysis[END_REF] the authors study the connectivity in VANETs based on results of percolation theory. They consider cars density, the rate of equipped vehicles, and communication coverage to study the distribution of isolated nodes and the impact of putting the RSU in intersections. The authors show that RSUs placement in crossroads does not impact significantly the proportion of isolated cars. From the related work, we can observe that the problem of RSUs deployment depends on the application. Many works consider only V2I communication i.e. the vehicle must be in the RSUs' radio range to communicate messages. In addition, the authors choose to use intersections in the case of urban scenario and uniform distribution in the case of highway scenario, which are not the best RSUs positions. Consequently, in our work, we deal with RSUs deployment in both urban and highway scenarios for delay-sensitive applications. We use V2X communications to enhance the network connectivity and reduce unnecessary infrastructures.

III. OPTIMIZATION PROBLEM MODELING

For our siting problem, we aim to find the best RSUs locations in urban or highway scenarios. The challenges consist on ensuring the application delay constraint and reducing the deployment cost. In fact, our objective is to find the best RSUs placement and respect the delay required to transmit messages while minimizing the number of RSUs. In this work, we take into account the following assumptions: we consider V2X communications i.e. messages are transmitted through both vehicles and RSUs; we assume that all RSUs are connected to each other through wired links (therefore, we considered only the message delivery delay to the closest RSU. The delay from this RSU to the final destinationa server within the cloudis supposed fixed); for initial distribution positions, we consider low connectivity segments as the best RSUs location candidates, so our solution can be applied to both urban and highway scenarios; then, for final placement, we reduce the delay constraint and deployment cost by modeling the location problem and solving it. Herein we give our mathematical modeling of RSUs siting problem followed by the complexity details of the exact solution.

A. Optimization problem modeling

Let I={1,…,m} be the set of candidate positions to install RSUs, a i be the RSUi deployment cost, J={1,…,n} be the set of all road segments in the studied area and t j be the required delay to route the message from road segment j to the closest RSU. Let also y i be the variable that indicates if the RSU I is open (deployed) or not. These variables are summarized in Table I. The number of RSU candidates m

The number of road segments n

Vehicles' radio range r

Application delay threshold T_threshold

To solve the RSU placement problem, we model it using equations (1) to [START_REF] Cavalcante | Roadside unit deployment for information dissemination in a VANET[END_REF]. Equation (1) represents the objective function to minimize. It is a weighted function composed of two sub-functions: (i) F1 representing the RSUs installation cost and (ii) F2 representing the delay to reach the closest RSU.

𝐹 = 𝛼𝐹1 + 𝛽𝐹2 (1)
Where α and β represent the weight of each sub-function. We choose α=1/3, β=2/3 as the delay constraint is the most important.

𝐹1 = 𝑚𝑖𝑛 a i y i 𝑚 𝑖=1 (2)
𝐹2 = 𝑚𝑖𝑛 t j 𝑛 𝑗 =1 (3)
𝑡 𝑗 = min 1<𝑠<𝑚 t js (4)
Equation ( 4) indicates the shortest delay t j to send messages from road segment j to any RSU and t js is the required delay to send a message from segment j to the RSU number s. The solution feasibility must respect the constraints given by equations: [START_REF] Cormen | Introduction to Algorithms[END_REF] to ensure that delay t j to transmit message from road segment j is lower than a given application threshold T_threshold; (6) and ( 7) represent the integrity constraints.

𝑡 𝑗 < 𝑇 𝑡ℎ𝑟𝑒𝑠 ℎ𝑜𝑙𝑑 ∀ 𝑗 ∈ {1 … 𝑛} (5)
y i 𝑚 𝑖=1 ≤ m (6)
𝑦 𝑖 ∈ {0,1} (7)

B. Exhaustive solution complexity

RSUs placement is a NP-hard problem [START_REF] Arora | Polynomial time approximation schemes for dense instances of NP -hard problems[END_REF] and requires huge computation capacities to find the best solution. We give in equation ( 8) the complexity of exhaustive solution to show the number of possible combinations to solve it. In fact, in this problem, we need to find the optimal number of RSUs to be deployed and their optimal positions. Therefore, we need to find the optimal number of k RSUs from m possible initial positions (see table I) (k<=m). We can write it as a mathematic combination 𝐶 𝑚 𝑘 . However, k is unknown and it is in the interval {1...m}. Consequently, the problem complexity becomes 𝐶 𝑚 𝑘 𝑚 𝑘=1

. In addition, to calculate the time to the closest RSU, we need to apply a short path algorithm to evaluate the delay to send messages to nearest RSUs for each solution combination. Therefore, for each possible solution, we add the complexity of the short path algorithm that is given by o(n²), where n is the number of total segments on the studied area (see table I). We get finally equation [START_REF] Sun | Roadside Units Deployment for Efficient Short-Time Certificate Updating in VANETs[END_REF].

𝐶 𝑚 𝑘 * 𝑜(𝑛 2 ) 𝑚 𝑘=1 (8)
Due to the problem complexity and the heavy computation required by the exhaustive method, we propose to use a heuristic to solve it in order to reduce the resolution computation time and get the best solution. In the next section, we explain in details our proposed solution ODEL and the several adaptations introduced to the genetic heuristic to solve the delay-sensitive RSUs placement problem.

IV. ODEL STEPS

In our work, the objective is to find the optimal number of RSUs to be deployed and their optimal positions while respecting the application delay requirements and the deployment cost constraint. To do that, we propose two processing steps as depicted in Fig. 1. To apply ODEL, we need to introduce several parameters such as: the map of the studied area, the traffic information, the application delay constraints and deployment cost information. Then, we apply the two steps solution as explained below.

A. First-step resolution: initial selection of RSUs candidate positions

In this phase, we calculate RSUs initial positions. In contrast to related work that choose initial positions randomly, uniformly or in intersections, we study the area and find the strategic positions based on the probability of connectivity. In fact, several work use the connectivity to optimize the information collection and dissemination between vehicles or mobile nodes [START_REF] Dung | A modeling framework for supporting and evaluating performance of multi-hop paths in mobile ad-hoc wireless networks[END_REF][25] [START_REF] Abboud | Modeling and Analysis for Emergency Messaging Delay in Vehicular Ad Hoc Networks[END_REF][27] [START_REF] Agarwal | Analytical Model for Message Propagation in Delay Tolerant Vehicular Ad Hoc Networks[END_REF]. Though, the connectivity information is not used to determine best RSU positions except in [START_REF] Ho | Stochastic Model and Connectivity Dynamics for VANETs in Signalized Road Systems[END_REF]. However, the authors did not optimize the number of RSUs candidates. Herein we explain how to get the initial candidates positions. For a given area, we extract information about density and speed in each segment of length 2*r meters using Simulation of Urban Mobility (SUMO) [START_REF]Sumo: Simulation of Urban MObility[END_REF]. Then, we use some scripts that we developed to calculate the connectivity probability. For urban scenario we use formula of connectivity probability ( 9) and [START_REF] Trullols | A Max Coverage Formulation for Information Dissemination in Vehicular Networks[END_REF] proposed in [START_REF] Kafsi | VANET Connectivity Analysis[END_REF]. Due to lack of space, the formula for a highway scenario is not described in this paper; but the reader can refer to [START_REF] Artimy | Connectivity in inter-vehicle ad hoc networks[END_REF] for more details.

𝑝𝑢 = 1 𝑖𝑓 0 ≤ 𝐿 < 𝑟 -𝜆𝑒 -𝜆𝑟 𝐿 -𝑖𝑟 𝑖 𝑖! 𝐿 𝑟 𝑖=0 -𝑒 -𝜆𝑟 -𝜆𝑒 -𝜆𝑟 𝐿 -𝑖 + 1 𝑟 𝑖 𝑖! 𝑖𝑓 𝐿 ≥ 𝑟 𝐿 𝑟 -1 𝑖=0 (9) 𝑝𝑙 = -𝜆𝑒 -𝜆𝑟 𝐿 -𝑖 -1 𝑟 𝑖 𝑖! 𝐿 𝑟 +1 𝑖=0 -𝑒 -𝜆𝑟 -𝜆𝑒 -𝜆𝑟 𝐿 -𝑖𝑟 𝑖 𝑖! 𝐿 𝑟 𝑖=0 ( 10
)
Where pu is the probability that there is a sequence of connected nodes in the road segment, pl is the sufficient condition to have a distance between two consecutive vehicles at most equal to the radio range r. 𝜆 is the vehicle arrival rate and L is the road segment length. After that, we choose the segment with lower connectivity probability as best candidate locations.

Also, based on the traffic information and road topology, we deduce the adjacency matrix. This matrix contains the neighborhoods of all road segments and the propagation delay in each road segment.

B. Second-step resolution: Optimal placement

As mentioned above, our solution takes into consideration both the application delay requirement and the deployment cost related to RSU deployment. To ensure that, we implement two optimization algorithms: (i) Dijkstra to find best routing time from any segment on the road to the closest RSU, and (ii) Genetic algorithm to find the best deployment positions for RSUs that satisfies the application time constraints and takes into account the deployment cost. This cost includes RSUs and network installation costs. The main entries of the second-step are: the adjacency matrix (a neighborhood matrix), the RSUs candidates vector and related deployment cost. We explain below our optimization algorithm with the different adaptations introduced to resolve RSUs locations problem.

1) Genetic algorithm

We apply the Genetic algorithm illustrated in Algorithm 1. We run this algorithm many times. Each iteration consists of natural operations: selection, crossover, mutation and recombination [START_REF] Maric | An Efficient Genetic Algorithm for Solving the Multi-Level Uncapacitated Facility Location Problem[END_REF]. In order to enhance the efficiency of the genetic algorithm, we use the Gaussian mutation [START_REF] Tinos | Evolution Strategies with q-Gaussian Mutation for Dynamic Optimization Problems[END_REF] to create a new chromosome by modifying one or more genes value and Roulette-wheel selection [START_REF] Lipowski | Roulette-wheel selection via stochastic acceptance[END_REF] to stochastically choose new offspring chromosomes from the pool for the new generation. Where P c is the crossover probability and P m is the mutation probability. The genetic algorithm generates and evaluates many solution combinations coded as a genetic chromosome or code and look for the best one as final results.

Algorithm 1Genetic algorithm <Adjacency matrix Madj, RSU Candidate Tcand, deployment cost>

2) Genetic code

We code each solution combination using a suitable binary code as depicted in Fig. 2. The binary code is composed of m bits; each bit is equal to one if the RSU is on, else it takes the value 0. We evaluate the chromosome using the objective function detailed below.

3) Objective function

Equation ( 1) is equivalent to equation ( 12). This formula is used in the genetic algorithm to evaluate each chromosome. In this equation, we calculate the deployment cost and the delay required to transmit messages to the closest RSU using our adapted Dijkstra algorithm as further explained below.

𝐹 = min( 𝛼 𝑎 𝑖+ 𝑚 𝑖=1 𝛽 𝑚𝑖𝑛 𝑖=1…𝑚 𝐷𝑖𝑗𝑘𝑠𝑡𝑟𝑎 𝑗, 𝑖 𝑛 =1 ) (12)

4) Dijkstra algorithm adaptation

We adapt the Dijkstra algorithm to our problem to reduce its complexity from o(n²) to o(Nb*n). In fact, each vertex has at most Nb neighbors. Given the adjacency matrix "Madj" got from the first-step of the solution, we construct a graph "G" to apply Dijkstra algorithm, each edges E in the graph G is the distance in term of delay from road segment v1 to its neighbor v2. Dijkstra calculates the delay from a given source vertex to all other vertices in the graph G. Only the shortest path toward the RSUs candidates is used to evaluate the solution. The Dijkstra adaptation is mainly done in line 9 of Algorithm 2.

Algorithm2

end while

Where "Tdistance" is an array of distances from the source "s" to each vertex V. "Previous" is an array of vertices' predecessors, "List" is the list of visited vertices and "Unvisited" is a set of remaining vertices.

In the next Section we present and analyze the different ODEL's results.

V. RESULTS AND PERFORMANCE

We develop automatic scripts in order to generate different maps, traffic scenarios and to extract density and speed information in each road segment using traffic simulator [START_REF]Sumo: Simulation of Urban MObility[END_REF], awk, shell and xml. The density changes over the time and from one road segment to another. Then, we develop Dijkstra and genetic algorithms and the different adaptations inside evolutionary framework proposed in [START_REF] Nguyen | A Probabilistic Memetic Framework[END_REF] using c++. We run several tests with different scenarios for both low and high density. We carry out all the performance tests on virtual machine with Intel i5 64Bits processor and 3 Gb. of memory. In Table II we present the parameters used in our tests and we summarize the optimization results in Table III, IV and V. To evaluate our solution's performances, we choose three criteria: (i) the delivery delay required to send messages from any road segment toward the nearest RSUs, (ii) the number of necessary RSUs to guarantee applications delay requirements and (iii) the computation performance in term of number of iterations to find best solutions. In RSUs siting problem, we want to activate only some RSUs candidates. In fact we do not need to cover the whole area. Table III illustrates 9 different examples; for each example we give the total number of segments, the number of possible candidates positions found in step 1, and the number of RSUs found as best solution in step 2. The cost efficiency is obtained by dividing the number of RSUs "off" (non-deployed) resulting from step 2 by the number of RSUs candidates resulting from step 1. These results show that our solution can meet the requirement of the application without siting unnecessary RSUs. We note that the optimization results depend on the delay constraint T_threshold of the application given in the last column of table V (e.g. in example 1, the total number of segments in the studied area is 60, it requires 15 RSUs candidates by applying step 1 and 11 RSUs "On" (deployed) by applying step 2 to ensure the application threshold of 3 seconds is satisfied. In example 2 (respectively 3), the number of RSUs "On" (deployed) after the step 2 is 26 (respectively 7) to have a delay lower than the T_threshold of 1 second (respectively 5 seconds.)).The cost efficiency results show that our solution reduces at least 23% of the deployment cost comparing to the deployment cost without the optimization of step 2. And it could reach 79% of efficiency if the delay constraint are larger (see example 3). IV between the number of iterations (complexity) of our Genetic algorithm and those required by the exhaustive solution explained further above in equation [START_REF] Sun | Roadside Units Deployment for Efficient Short-Time Certificate Updating in VANETs[END_REF]. Equation ( 8) is equivalent to 2 m by using the generalized hypergeometric function [START_REF] Dziok | Classes of analytic functions associated with the generalized hypergeometric function[END_REF]. The number of iterations depends on the number of total road segments and the number of candidate positions as defined in table III. We can see in table IV that the number of iterations in our solution is significantly lower. We note that the number of iterations increases at expense of the total number of segments in the studied examples as the delay is measured in each road segment and not only in candidate ones. However, it is always lower than the number of iterations of the exhaustive resolution method (e.g. In the example 1 in table IV, genetic solution requires 31 times unit while the exhaustive solution for the same scenario requires 32768 times unit, which corresponds to 2 15 combination in exact solution). In Table V, we calculate the delay efficiency of our solution; we compare the minimum delay to deliver messages from all road segments to the closest RSUs. These results show that our solution is a much more effective (e.g. for example 1, the average delay required to transmit data to the destination is 0.31 second which is lower than 340 second without using RSU but only V2V communications). Finally, simulation results show that our solution ODEL achieves desirable efficiency in term of delay requirement, while preserving necessary coverage in the whole area using both V2I and V2V communication capabilities. In addition, our solution is designed to support large scale scenarios and reduce significantly the computation operation. We note that ODEL aims to improve the delay by deploying RSUs in road with low density unlike the related work that improve connectivity only in the intersections. However, when the density is lower than the density considered in our study, neither our solution, nor the related work contributions achieve a low delay. In fact, our solution optimizes the number of deployed RSUs to ensure a full covered area over V2X communication. Moreover, when density is very low, it is more interesting to use 3G or LTE solutions as the number of messages is very low and does not consume huge cellular network resources.

VI. CONCLUSION AND FUTURE WORK

In this work, we focus on the delay requirement for delaysensitive vehicular networks applications. We aim to reduce the message communication delay and cope with intermittent connectivity by optimally siting new infrastructure (roadside units). To do that, we propose a mathematical modeling of infrastructure placement with high delay constraints and we propose ODEL solution. ODEL finds first strategic locations candidates based on a study of traffic information in the studied area. Then, it optimizes the number of final RSUs locations using two optimization algorithms Genetic and Dijkstra algorithms. In contrast of the existing work that deploy RSUs without considering application delay constraints and generally place RSUs randomly, uniformly or in intersections, ODEL provides very interesting delay boundaries and could be applied in different scenarios. As a future work, we plan to test our solution to optimize the routing and dissemination end-toend delay for delay-sensitive applications and extend our solution to support different road geometry and radio obstructions.

Figure 1 .

 1 Figure 1. ODEL solution

1 .

 1 Pop.Create ("random", initial population) 2. Pop.CalculateFitness() 3. While (!Max _Iterations) 4. {Offspring = Select ("Roulette-wheel", Pop, Nbchromosoms) 5. Offspring.Crossover(uniform, P c ) ; 6. Offspring.Mutation("Gaussian", P m ) ; 7. Offspring.Permut () ; 8. Recombination("Keep-Best", Offspring, Pop) 9. } Pop.BestSolution() <Nb CS, position CS>

Figure 2 .

 2 Figure 2. Binary-chromosome

TABLE I

 I

	.	NOTATION
	Variable		Notation
	deployment cost to build RSU i		ai
	Decision variable to open or not the RSUi	yi
	Minimum delay to transmit a message from a vehicle in road segment j to the closest RSU	tj

TABLE II .

 II PARAMETERS TABLE

	Parameter	Value
	Radio range r	250
	Number of total road segments	60-500
	Number of RSU candidates	25-150
	Road density (vehicle/km)	1-30
	Vehicles average speed (km/h)	15-50
	Road segment length (m)	500
	T_threshold (s)	0.1-10
	Crossover probability Pc	0.3-0.5
	Permutation probability Pm	0.8
	Population size	50

TABLE III

 III

			.	RESULTS1: FINAL RSU NUMBER
	Exa	Total	Applicatio	Candidate	Number of	Cost
	mple	number	n	segments	final	Efficiency
		of	delayT_th	number	positions
		segmen	reshold	(found in	(found in
		ts		step1)	step2)
	1.	60	3	15	11	26.66%
	2.	60	1	34	26	23.52%
	3.	60	5	34	7	79.41%
	4.	144	5	25	19	24%
	5.	144	5	64	42	34%
	6.	144	7	64	33	48%
	7.	220	5	60	40	33.33%
	8.	220	6.5	88	37	57.95%
	9.	220	7	74	26	64.86%

For the same examples of Table III, we compare in Table

TABLE IV

 IV

						Applica
					Example	Number of exhaustive iteration	Number of genetic iteration	tion delay T_thres	Genetic Computation time
						hold
					4.	33x10 6	1000	5	141
					5.	≅18x10 18	1000	5	105
					6.	≅18x10 18	1000	7	120
					7.	≅1.15x10 18	1000	5	1100
					8.	≅3.09x10 26	1000	6.5	1500
					9.	≅ 1.8x10 22	1000	7	532.31
		.	.RESULTS2: COMPUTATION
				Applica
	Example	Number of exhaustive iteration	Number of genetic iteration	tion delay T_thres	Genetic Computation time
				hold
	1.	32768	1000	3	31
	2.	≅1717x10 7	1000	1	30.39
	3.	≅1717x10 7	1000	5	19.6

TABLE V

 V

		.	.RESULTS3: DELAY EFFICIENCY
	Exampl e	Delay when no RSU is deployed	Delay with optimal RSU number	Average Delay	Delay Efficiency	Applica tion delay T_thres hold
	1.	340.4	18.76	0.31	94.5%	3
	2.	423.74	11.73	0.19	97.2%	1
	3.	340.4	53.23	0.88	84.36%	5
	4.	1279.22	388.93	2.7	69.66%	5
	5.	1762.4	105	0.72	94.04%	5
	6.	1762.4	157.74	1.09	89.5%	7
	7.	1359.06	99.36	0.45	92.68%	5
	8.	1436.83	99.36	0.45	93.08%	6.5
	9.	1019.26	156.65	0.71	84.63	7