Marta Alós Ortí
email: martaalosorti@gmail.com

Joan Casanelles-Abella

François Chiron

Nicolas Deguines

Tiit Hallikma

Piia Jaksi

Patrycja K Kwiatkowska

Marco Moretti

Babette Muyshondtu

Ülo Niinemets

Pedro Pinho

Manuel João Pinto

Peedu Saar

Roeland Samson

Piotr Tryjanowski

Anskje Van Mensel

Lauri Laanisto

Babette Muyshondt

Pedro Pinho H Manuel

João Pinto

Negative relationship between woody species density and size of urban green spaces in seven European cities

Keywords: Urban vegetation, species richness, above-ground biomass, canopy cover, species-area relationship

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Plants constitute the vast majority of biomass in terrestrial ecosystems including highly anthropogenic ecosystems, and support directly and indirectly biodiversity [START_REF] Bar-On | The biomass distribution on Earth[END_REF].

Particularly, plants provide food, shelter and create microenvironmental conditions for other taxa in most ecological systems. Humans have been and are still transforming natural ecosystems into human-dominated biomes [START_REF] Ellis | Putting people in the map: anthropogenic biomes of the world[END_REF]. Therefore, plant species richness in urban ecosystems mainly depends on human practices [START_REF] Kühn | The flora of German cities is naturally species rich[END_REF] and on the type of built-up area [START_REF] Godefroid | Urban plant species patterns are highly driven by density and function of built-up areas[END_REF] and not only on natural processes related to dispersal, filtering and interactions [START_REF] Nielsen | Species richness in urban parks and its drivers: A review of empirical evidence[END_REF].

Planting non-native species highly contribute to more diverse woody vegetation communities in urban areasalmost half of the non-native woody species in urban ecosystems are deliberately planted [START_REF] Aronson | A global analysis of the impacts of urbanization on bird and plant diversity reveals key anthropogenic drivers[END_REF][START_REF] Kowarik | Novel urban ecosystems, biodiversity, and conservation[END_REF]. Around 40% of plant species in European cities are non-native [START_REF] Pyńek | Alien and native species in central European urban floras: a quantitative comparison[END_REF], although lower (30%; [START_REF] Salinitro | Floristic diversity in different urban ecological niches of a southern European city[END_REF]) and higher (66%; [START_REF] Rahman | Green traces from past to future: the interplay of culture and ecological processes in European historical parks[END_REF] proportions have also been reported [START_REF] Kowarik | Prevalence of alien versus native species of woody plants in Berlin differs between habitats and at different scales[END_REF][START_REF] Tsiotsiou | Woody plants in urban biotopes: studies in Patras (Greece)[END_REF]. Plant diversity provides various ecological niches for a wide variety of birds, insects, cryptogams and other biota (e.g. [START_REF] Grote | Building an Urban LTSER: The Case of the Baltimore Ecosystem Study and the D.C./B.C. ULTRA-Ex Project[END_REF]Grove et al., 2013). Also composition and structure of vegetation and landscape attributes contribute to the overall J o u r n a l P r e -p r o o f biodiversity [START_REF] Threlfall | Variation in Vegetation Structure and Composition across Urban Green Space Types[END_REF]. Higher vegetation biomass can provide greater resources for many different organisms (e.g. Großmann et al., 2020), which consequently allows for larger and thereby more viable and stable populations. A global meta-analysis on biodiversity in cities [START_REF] Beninde | Biodiversity in cities needs space: a metaanalysis of factors determining intra-urban biodiversity variation[END_REF] concluded that in addition to patch size, vegetation structure together with species richness, tree cover and vegetative biomass play significant roles in providing better habitat for other organism groups that inhabit urban green spaces.

The role of woody vegetation in urban areas is especially crucial in providing habitat for other organisms [START_REF] Baruch | Increased plant species richness associates with greater soil bacterial diversity in urban green spaces[END_REF], and ecosystem services [START_REF] Capotorti | Biodiversity and ecosystem services in urban green infrastructure planning: A case study from the metropolitan area of Rome (Italy)[END_REF]. Vegetation of UGSs provides regulating ecosystem services (ESs) such as local climate regulation and air pollution removal [START_REF] Grote | Building an Urban LTSER: The Case of the Baltimore Ecosystem Study and the D.C./B.C. ULTRA-Ex Project[END_REF][START_REF] Locosselli | The role of air pollution and climate on the growth of urban trees[END_REF], supporting and provisioning ESs (e.g. primary production and food, respectively) as well as cultural ESs (e.g. recreation activities, [START_REF] Bjerke | Vegetation density of urban parks and perceived appropriateness for recreation[END_REF]. Therefore, municipalities have the opportunity and responsibility to implement ecosystem-based management and planning strategies for providing a higher quality environment for both humans and other organisms [START_REF] Beery | Perceptions of the ecosystem services concept: opportunities and challenges in the Swedish municipal context[END_REF].

European cities share common standards in the planning of green spaces based on transforming densely built-up cities -with a scarce consideration of ecological factors in the urban design process-into more sustainable living environments [START_REF] Kohout | Green space ideas and practices in European cities[END_REF]. As part of the new EU Biodiversity Strategy 2030, cities with a minimum population of 20,000 were requested to elaborate Urban Greening Plans by the end of 2021 with a special focus on increasing biodiversity among green infrastructure elements such as UGSs (EC, 2020). Therefore, knowing J o u r n a l P r e -p r o o f the current plant diversity and functioning in UGSs is a key tool for stakeholders involved in the urban planning process.

Many urban ecology studies focus on urbanization effects on biodiversity across urban-rural gradients (e.g. [START_REF] Mckinney | Urbanization, biodiversity, and conservation[END_REF]. Other studies have typically focused on single cities or locations, mainly assessing specific applied research goals using intra-urban transects, and metaanalysis conducted at broader scale commonly use existing data from different sources [START_REF] Beninde | Biodiversity in cities needs space: a metaanalysis of factors determining intra-urban biodiversity variation[END_REF]. Systematically sampled comparable data on woody vegetation in UGSs is relatively scarce, especially on large scales and at high resolution level that would comprise data from urban settlements in different countries [START_REF] Beninde | Biodiversity in cities needs space: a metaanalysis of factors determining intra-urban biodiversity variation[END_REF]. Thus, there is a knowledge gap on the taxonomic and structural diversity of woody vegetation stemming from common standardized surveys and at fine-grained detail comprising different urban spaces at the continental scale [START_REF] Yang | The compositional similarity of urban forests among the world's cities is scale dependent[END_REF] which we aim to fulfill. Here we also follow research directions highlighted by [START_REF] Pinho | Research agenda on biodiversity and ecosystem functions and services in European cities[END_REF] aimed at enhancing our understanding on urban biodiversity and ecosystem functions and services, particularly by including several key plant traits in our study and providing high resolution urban habitat maps.

Several studies in urban areas have found positive correlation between species richness and patch area [START_REF] Cornelis | Biodiversity relationships in urban and suburban parks in Flanders[END_REF][START_REF] Shwartz | Local and management variables outweigh landscape effects in enhancing the diversity of different taxa in a big metropolis[END_REF]. Nonetheless, different patterns of diversity in urban parks and other green spaces have been found [START_REF] Talal | Plant Community Composition and Biodiversity Patterns in Urban Parks of Portland, Oregon[END_REF], suggesting that the increase in the number of woody species is not always proportional to the increase of UGS size, but other factors play a role in shaping urban biodiversity (e.g. urbanization degree, McKinney ( 2008)). UGSs tend to have lower diversity than expected from their size. Woody species J o u r n a l P r e -p r o o f density (i.e., number of species per unit area) is thus expected to be negatively correlated with UGS size. However, such analyses for urban vegetation are so far missing from the literature.

We studied 225 UGSs in 7 European cities along a SW-NE latitudinal gradient, from Portugal to Estonia. We systematically sampled and mapped woody vegetation in UGSs with different degrees of size and fragmentation, as both landscape metrics have an effect on ecological processes (e.g. [START_REF] Shanahan | The influence of patch area and connectivity on avian communities in urban revegetation[END_REF]. Our main aim was to understand the influence of UGSs size on woody vegetation features. We tested this looking at i) species richness (expecting a relatively weak positive relationship), ii) species density (expecting an overall negative relationship), and iii) tree cover and biomass (expecting a non-significant effect).

Methods

Sampling sites selection

We selected 225 UGSs belonging to 7 European cities from Lisbon (38º N) to Tartu (58º N), covering most of the climatic variability in mainland Europe (Fig. 1). Selection was based on patches classified as 'Green urban areas' category (code 1.4.1. of the Urban Atlas) in the Pan-European Urban Atlas (2012), providing high-resolution land use and land cover maps for urban areas across Europe. To avoid major management differences between sites, we also manually excluded patches that were predominantly occupied by cemeteries and zoos, which are included in the 'Green urban areas' class. Other vegetated areas such as 'Forest' class (code 3.1. of the Urban Atlas, included in natural and semi-natural areas category) and private UGSs with no public access were left out in order to minimize heterogeneity due to type and intensity of management practices. Site selection was conducted based on two independent gradients: i) size J o u r n a l P r e -p r o o f of UGSs, and ii) their structural connectivity with other green elements embedded in the urban matrix (i.e., discontinuous low density urban fabric (10-30%), discontinuous very low density urban fabric (<10%) and forests), as landscape configuration plays a role in shaping several urban taxa diversity and distribution (e.g. insects and birds). Thus considering both size and connectivity degree in our sites selection allows cities and taxa comparison. The degree of connectivity was calculated using the Proximity Index in Fragstats software within a 5 km radius from every patch. Vegetation survey was conducted between June 2018 and June 2020. The survey consisted of a field assessment in each selected UGS, and subsequent analysis based on land cover maps of UGSs. All woody species throughout the UGSs were identified (i.e., woody species richness, Table 1) and separated by provenance into native and non-native species (see Supplementary Table S1 for source information). Species-specific mean height was recorded for each woody species (i.e., mean height of woody layer, Table 1). Then, a more detailed vegetation survey was carried out in the centroid of each selected UGS (Fig. 2a). If the geometric centroid was not available for sampling (e.g. inaccessible area, water bodies, area without trees), then the closest available area was chosen. The new sampling centroid had to accomplish two criteria: i) include woody vegetation that was representative of the UGS, and ii) occur as close as possible to the original centroid. Sampling in centroids was used in order to minimize the effects of surrounding urban non-green areas. From the five 5m x 5m plots in the sampling centroid all woody species were identified, the height, diameter at breast height (i.e., diameter of the trunk at 1.3 m from the ground, only for trees, DBH, Table 1) and crown or hedge size were measured on each woody individual in each plot (Fig. 2b). Woody species richness, both at the centroid and at the site scale were compared to UGS size to determine if the same relationship among total richness and patch size was also found at the plot level (i.e., if the patch size had an effect on species richness at every level, as expected in natural systems, or it rather depends on UGS design and management). When we refer to the percentages of native and non-native species, we mean the whole woody species pool in each city (i.e., all the species recorded across the UGSs of a given city) not to its predominance among UGSs. Lisbon (size=31868.26 m 2 ), land cover map and location of the sampling centroid (38°46'13.7"N, 9°10'33.9"W) (c).

J o u r n a l P r e -p r o o f

Land cover maps

A land cover map of each sampled UGS was made by photo-interpretation of the high resolution (i.e., 0.5 m) World Imagery basemap from 2015 using ESRI ArcMap 10.4. Photo-interpretation was done at a scale of 1:600 which allowed to distinguish between the different land cover types within the UGS (Fig. 2c). Tree species types (i.e., coniferous, broadleaf deciduous and broadleaf evergreen trees) were separated by checking images provided by Google Earth Pro v.7.3.2.5776 and street view in Google Maps from different phenological stages. The resulting vegetation maps were validated during the vegetation survey. Satellite imagery does not allow to precisely classify the extent of all land cover types due to overlapping vertical layers. Therefore, our land cover maps provided accurate information about the upper layer (i.e., tree canopy cover and canopy percentage, Table 1). Tree canopy cover was used to extend the aboveground biomass results of measured trees to the entire tree cover of each UGS.

Aboveground biomass calculation

Above-ground biomass (AGB, Table 1) of trees was calculated by using species-, genus-or plant functional type-specific allometric equations (see Supplementary Table S1 for source information). Species-specific allometric equations were used, but if not available, then genusspecific models were used, or generalized equations for either broad-leaved and coniferous trees J o u r n a l P r e -p r o o f were applied. The allometric models used were based on combinations of the measured plant traits, specifically DBH and plant height and calibrated across specific ranges of these plant traits. Therefore, we considered the trees whose traits fitted such ranges. This avoided possible under-and over-estimations of AGB, but restrained the AGB results to 154 UGSs from which 139 were used for analysis (i.e., 15 UGSs were outliers, see Statistical analysis section). When more than one equation was available, the mean was used.

Statistical analysis

All analyses were conducted in R v. 3.6.1 (R Core Team, 2019) (see Supplementary Table S1 for packages source information). In order to avoid distortions in descriptive metrics and statistical tests, AGB outliers highlighted in boxplots were removed from the dataset prior to analysis. The overall variables are described in Table 1, namely: UGS size, AGB, canopy cover (both in absolute and relative terms), mean height of the woody layer, woody species richness and species density.

Linear regression models for all cities together and separately were made for exploring the response of woody species richness, woody species density (number of woody species per unit area of UGS), canopy cover and AGB (i.e., response variables) to UGS size (i.e., explanatory variable). Logarithmic transformations were applied to both response and explanatory variables to better fit linearity. Coefficients of determination are shown as R 2 . Then, we performed linear mixed effects models (LMM) of those above mentioned relationships including cities as a random factor in order to account for variation of woody vegetation features in the studied cities.

Results

An overview of European UGSs vegetation

A total of 418 woody plant species from 76 families were identified across 225 European UGSs (Table 2 and Supplementary Table S2). Each UGS had a mean of 13 ± 0.8 species of woody plants with big differences among cities (i.e., from 6. J o u r n a l P r e -p r o o f 15 Overall, large green spaces hosted slightly more woody species (Fig. 3a). At the city level, this correlation was significant in Antwerp, Lisbon, Paris and Tartu (Fig. 3a and Supplementary Table S3). In the other cities (i.e., Poznan, Zurich and Almada), UGS size did not show significant effect on woody species richness (Fig. 3a). Centroid woody species richness was not related to the size of the UGS (p>0.05) (Supplementary Fig. S1). S3 for each city.

Woody species richness of the whole UGS was positively related to UGS size and city had a significant effect (β = 0.16, SE=0.02, t= 6.7, p < 0.0001). Woody species density was negatively J o u r n a l P r e -p r o o f correlated with the size of UGSs across all cities (R 2 =0.77) (Fig. 3b) with city having a significant effect (β = 0.98, SE=0.08, t= 11.9, p = 0.08). Within individual cities, the correlation coefficient varied from 0.72 in Zurich to 0.95 in Poznan (Fig. S3).

Tree cover and aboveground biomass

Bigger UGSs had generally more AGB and wider tree canopy cover (Fig. 4). Both correlations were significant in all the studied cities (Supplementary Table S3). The relationship between UGS size and canopy cover varied among cities (β = 1.03, SE=0.03, t= 34, p < 0.0001) (Fig. 4a), while UGS size and AGB relationship (Fig. 4b) was independent of the city (β = 0.98, SE=0.08, t= 11.9, p > 0.05). Not surprisingly, these two variables were highly correlated among them (Fig. S3), implying that wider canopies -normally belonging to bigger trees-inherently harbors more vegetative biomass. The strongest associations were observed between size and tree canopy cover, especially in Paris and Tartu (i.e., R 2 >0.90), indicating that tree cover in these cities was generally more correlated with the size of UGS than in other cities (e.g. Antwerp, R 2 =0.76). Size had also a strong effect on the amount of AGB contained in tree structure, especially in Paris (R 2 =0.76) and Almada (R 2 =0.66) compared to Lisbon (R 2 =0.43).

J o u r n a l P r e -p r o o f S3 for each city.

Table 3 displays the distribution of tree cover and AGB in the seven cities. Despite Almada displayed the lowest tree cover percentages, it had the highest mean tree biomass per UGS after Tartu. Heights of trees (i.e., woody plants higher than 3m) ranged from 8.2±0.4 m in Almada to 11.3±0.4 m in Antwerp, on average (Table 3). Tree DBH varied considerably between cities, with a mean ranging from 20 ± 2.3 cm in Zurich to 35 ± 3.3 and 36 ± 2.1 cm in Almada and Tartu, respectively.

J o u r n a l P r e -p r o o f

Discussion

We aimed to understand how different woody vegetation is in differently sized urban green spaces of seven European cities by testing species richness and density on UGSs size gradient.

Analyses confirmed our expectations -while the relationship between UGS size and woody species richness was overall positive, the relationship was weak and appeared only in certain cities (Fig 3a), while the species density had a strong negative relationship with UGS size in every studied city (Fig 3b). Bigger UGSs had more biomass and canopy cover only in absolute terms (Fig 4). Thus, woody vegetation that dominates in urban green spaces is currently managed in a way that the potential of these valuable urban areas is not by far fully realized, neither for humans nor other organisms living and visiting urban areas.

An overview of European UGSs woody vegetation

While cities tend to be more diverse in terms of plant species than the surrounding natural ecosystems (e.g. [START_REF] Kühn | Urbanization and homogenization -Comparing the floras of urban and rural areas in Germany[END_REF], a big proportion of that diversity in case of woody species is due to planting non-native specieson average 59 % in our sampled UGSs (Supplementary

J o u r n a l P r e -p r o o f

Table S2). The proportion of native and non-native species and predominance of the abundance of native species in our sample are in line with previous research from other urban areas [START_REF] Crosby | Urban street tree characteristics and benefits in city centre, Reykjavik, Iceland[END_REF][START_REF] Pauleit | Tree establishment practice in towns and cities -Results from a European survey[END_REF].

Planting woody individuals is a common practice in urban areas, but the species selection always comprises a trade-off between environmental, social and economic features. For instance, A.

platanoides, the most commonly found species in our European UGSs, has been shown to be effective in removing particulate matter (PM) and O 3 and storing CO 2 as part of its biomass [START_REF] Baraldi | An integrated study on air mitigation potential of urban vegetation: From a multitrait approach to modeling[END_REF]. Nevertheless, it can also cause damage in urban structures, mainly on kerbs and other impervious surfaces [START_REF] Scholz | Potential tree species for use in urban areas in temperate and oceanic climates[END_REF]. Another example, R. pseudoacacia, is also a widespread species among the studied UGSs. It has been planted in cities in the last decades in part due to its resistance to harsh environmental conditions and diseases, even if it is considered an invasive species, especially in Central and Southern Europe (Puchalka et al. 2020).

However, it has been shown to be less efficient than native species (Tilia cordata) in lowering temperature in cities [START_REF] Rahman | Green traces from past to future: the interplay of culture and ecological processes in European historical parks[END_REF], and it is suffering the negative consequences of climate change and urban air pollution (Wilkaniec et al., 2021). In contrast to the high abundance of R. pseudoacacia, Ailanthus altissima was only found in four UGSs in Paris. This is surprising given that A. altissima is a fast-growing N 2 -fixing tree adapted to urban conditions (i.e., it tolerates well high temperatures, drought and poor soil conditions). This species is a widespread invasive species in Europe and an important component of many urban areas across Europe (e.g. [START_REF] Casella | Ailanthus altissima (tree of heaven): Spread and harmfulness in a case-study urban area[END_REF]. Our results show that its within-city distribution may be restricted to other Woody community composition will determine the resilience and effectiveness of UGSs in maintaining urban biodiversity and providing ESs. Our results contribute to knowing the actual species composition in UGSs. This is especially important in the context of global change that will raise temperatures affecting urban ecosystems (e.g. increased climate stress, pathogen threats) and, consequently, their functions and processes that influence the health and well-being of urban residents.

Woody species richness and UGS size

The positive relationship among area and species richness in natural areas has been demonstrated

for vascular plants and other taxa also within city boundaries (e.g. [START_REF] Cornelis | Biodiversity relationships in urban and suburban parks in Flanders[END_REF].

According to our results, this correlation is weak and city-dependent suggesting that other local factors may play an important role on shaping urban biodiversity. Since both mean and median woody species richness in the centroid were four and the minimum species recorded in UGSs varied between three and four (with few exceptions), we can say that this is the minimum species richness threshold that the municipalities apply when designing and maintaining UGSs. By testing the relationship between size of UGS and species richness at two different scales (i.e., whole UGS and centroid) we confirmed that the positive relationship between species richness and UGS size did not happen at the centroid level (Supplementary Fig. S1) as expected in natural ecosystems.

J o u r n a l P r e -p r o o f

Our results suggest rather similar management practices at European scale, especially in the mean height of planted trees (between 8 and 11m height) and a preference for large trees (DBH>20cm). This is especially true for southern and northern cities (i.e., Lisbon, Almada and Tartu) where larger and older trees (i.e. mean DBH= 31-36cm) are maintained. Conserving old trees is important for ESs provision, natural heritage and cultural identity as well as for biodiversity (e.g. urban tree microhabitats, Großmann et al., 2020). Trees in Tartu displayed the biggest diameters (i.e., mean DBH = 36cm). This could be due to the increase in temperatures during the last decades (especially in urban areas, better known as urban heat island effect) that, combined with management practices that counteract some growth limiting factors, has overstimulated tree growth [START_REF] Chmielewski | Response of tree phenology to climate change across Europe[END_REF]. Also, urban trees in high latitudes are known to grow faster than their counterparts in rural areas or in warmer cities [START_REF] Smith | Live fast, die young: Accelerated growth, mortality, and turnover in street trees[END_REF]. Higher rain frequency in high latitudes, together with the urban environment (e.g. high CO 2 concentrations), might further foster tree growth rates in northern cities compared to meridional ones [START_REF] Pretzsch | Climate change accelerates growth of urban trees in metropolises worldwide[END_REF]. In warmer latitudes, climate may be a greater stressor for urban vegetation and act as a filter for plant species distribution and growth that is lessened by management.

Woody species density and UGS size

As expected, species density steeply decreased along the size gradient in all the sampled cities (Fig. 3b, Table S3), meaning that the current management policies do not use the full potential of urban parks in increasing biodiversity. Since the minimum amount of woody species used when designing and managing urban green spaces is ~4 woody species, park managers plant more species when more space is available, but only up to a certain limit that depends on the city (e.g. Using species density in urban ecosystems is so far an unexplored practice that can be used as an efficient indicator of how policy instruments have been incorporating biodiversity in UGSs. In our study we included all woody species, i.e., also shrubs when accounting for species richness and density, since they can contribute significantly to the overall diversity and also provide ESs (e.g. noise reduction) [START_REF] Moudrý | The role of the vegetation structure, primary productivity and senescence derived from airborne LiDAR and hyperspectral data for birds diversity and rarity on a restored site[END_REF].

Tree cover and aboveground biomass

Several studies have focused on how tree canopy properties in urban areas benefit city dwellers [START_REF] Doc_1&format=pdf Gillner | Role of street trees in mitigating effects of heat and drought at highly sealed urban sites[END_REF][START_REF] Pataki | Transpiration of urban forests in the Los Angeles metropolitan area[END_REF] and increase species richness of other organisms inhabiting urban ecosystems [START_REF] Moudrý | The role of the vegetation structure, primary productivity and senescence derived from airborne LiDAR and hyperspectral data for birds diversity and rarity on a restored site[END_REF]. [START_REF] J O U R N A L P R E -P R O O F Mouratidis | The impact of urban tree cover on perceived safety[END_REF] found that urban tree cover increased people's feeling of safety. One of the most studied ESs derived from urban trees is their capacity to cool the urban environment by means of evapotranspiration, canopy shadow and reflection of the solar radiation [START_REF] Venter | Linking green infrastructure to urban heat and human health risk mitigation in Oslo, Norway[END_REF][START_REF] Zardo | Estimating the cooling capacity of green infrastructures to support urban planning[END_REF]. This cooling effect increases with tree species richness [START_REF] Wang | Tree species richness and diversity predicts the magnitude of urban heat island mitigation effects of greenspaces[END_REF].

The positive correlation among UGS size and tree canopy cover in absolute terms (i.e., total extent of tree crowns) was not found when relative canopy cover (i.e., percentage of UGS covered by trees) was considered. We argue that analyzing the relative amount of canopy cover in UGSs (usually expressed in %) is misleading in case of smaller UGSs -only a few tree individuals are necessary to provide nearly 100% canopy cover in small UGSs. However it is not J o u r n a l P r e -p r o o f sufficient amount of canopy to provide habitat for diverse biota, as the other species are often specialized to certain evolutionary lineages, or woody species types (conifers vs. broadleaf trees)

and more specific traits (e.g. ridged bark). In addition, animals often tend to be highly territorial, which means that the high canopy cover percentage in an UGS does not ensure diverse biota inhabiting these UGSs. Which is why we used absolute, and not relative amount of canopy cover in our analysis (Fig. 4). However, relative canopy cover (Table 3) indicated that park designers promote non-tree land cover types (e.g. open lawns, paved surfaces) when planning and designing UGSs. All the studied cities had at least some UGSs that were fully covered by tree canopy (>90% of UGS extent), with 50 of them covering more than 75% of the entire UGS.

Percentage of tree canopy cover and vegetation structure have been proven to strongly and directly influence temperature in cities [START_REF] Chen | Roles of horizontal and vertical tree canopy structure in mitigating daytime and nighttime urban heat island effects[END_REF]. Therefore, local planning strategies should consider both horizontal and vertical components of the woody layer when designing management instruments in order to create a better urban environment.

Although large areas are slightly more biodiverse than smaller ones (Fig. 3a), increasing the size of a UGS is most probably not feasible in an already densely urbanized landscape, like in European cities. However, the strong negative relationship between species density and UGS size implicates that the existing UGSs could harbor much more species per unit area than they currently do. Planting more woody plant species that are suitable for the urban environmental condition is a cost-effective way to fulfill the demand for ESs in urban environments. Future policy regarding urban green planning should shift the focus more on community and ecosystem level functioning of UGSs, and woody vegetation is the fundamental foundation for enhancing the functionality and persistence of urban ecosystems (Hirons et al., 2019).

J o u r n a l P r e -p r o o f

The differences found among the general trends and correlations at city level indicate that other parameters not considered in the study could be influential. For instance, woody species richness displayed a positive relationship with canopy cover when considering all the UGSs together.

However, at the city scale, this correlation was only significant in Antwerp. This and other cityspecific effects can be overcome if key local factors are known (e.g. socio-economic preferences). Another possible hidden trend is that an underlying mechanism to explain the role of size in multiple vegetation parameters could rely on the influence of UGS management option, i.e., management options of the largest UGSs tend to be similar when compared to smaller sites. Moreover, the selection of the Urban Atlas as an homogeneous basis of LULC information for studied sites selection influences the type of green spaces considered in the study, as they consider different types of urban vegetated surfaces into 'Green urban areas' class.

However, since this happens in all the selected cities in comparable proportions, it probably does not imply any bias in our results. Still, we highlight that creating a continental scale comparable cartography with higher thematic classification is necessary to provide more details that allow future studies to separate the 'Green urban areas' class into sub-classes differing on the management practices or type of use.

Conclusion

Urban green spaces are multifunctional elements of the urban matrix, providing several social, environmental and economic benefits. Woody vegetation constitutes the main component of UGSs, providing valuable ecosystem services for humans, but also food and shelter for other organisms. However, there is very little comparable ecological data about vegetation in UGSs.

J o u r n a l P r e -p r o o f

This topic is of great interest not only for ecological research but also for urban planners and urban landscape designers.

Our extensive field survey in 225 UGSs with different sizes in seven European cities showed at all levels of analysis that: 1) species richness of UGS was only weakly related with UGS size;

while 2) the species density had a strong negative relationship with UGS size. Moreover, we provide a complete list of the most common species among the seven European cities. There seems to be a certain threshold of how much effort is put into management of urban green spaces in the context of woody diversity. Thus, there seems to be a so far unseized opportunity to increase species density in the largest parks by management change only. This could create more heterogeneity and thus improve conditions for both other organisms living in UGSs, but also enhance ecosystem services beneficial for humans.

The outcomes of this research will assist urban planners and policy makers through the current biodiversity in urban green spaces and their unused potential. This is especially useful in the frame of the EU Biodiversity Strategy to 2030 which calls on cities to develop Urban Greening Plans by the end of 2021, putting special attention on urban biodiversity. In addition, our findings can also be used in urban ecology research involving a variety of taxa and ecosystem services.

J o u r n a l P r e -p r o o f

Figure 1 .

 1 Figure 1. Location of the selected cities, with information on demography and climate provided.

Figure 2 .

 2 Figure 2. Sampling design (a), quadrat C is located in the sampling centroid of the urban green

  J o u r n a l P r e -p r o o f P-values for model comparison were obtained by likelihood ratio tests of the full model with the city effect against the model without the city effect.

  unit area) in UGSs per city was distributed as follows: Antwerp 4 spp./ha, Lisbon 4.7, Poznan 4.7, Almada 6.5, Zurich: 9.5, Tartu 10.6, Paris 23.2. Distribution patterns of woody species richness and density, coefficient of variation of woody plants height, mean height of the woody layer, relative canopy cover and AGB across all the studied cities are displayed in Fig.S2. The response variables (i.e., woody species richness and density, coefficient of variation of woody plants height (CV), canopy cover and AGB) accounted for 68.4% of the overall dataset variation (Fig.S3). A main trend was formed by tree cover and AGB, while CV, woody species richness and density displayed a different trend.Woody species richness and UGS sizeJ o u r n a l P r e -p r o o f 14 We found clear latitudinal differences in the predominance of species with different species being the most common in different cities (

Figure 3 .

 3 Figure 3. The relationship of UGS size with woody species richness (a) and woody species

Figure 4 .

 4 Figure 4. The relationship of UGS size with canopy cover (a) and AGB (b) per city. Both plots

  land cover types rather than to UGSs; for example, Paź-Dyderska et al., (2020) recorded the J o u r n a l P r e -p r o o f 20 species in Poznan recently, but only in paved and ruderal areas, claiming that management practices limit their ecological success.

J

  o u r n a l P r e -p r o o f the maximum species richness in a UGS was 11 in Poznan and 101 in Paris -even though the UGSs in this study were selected based on comparable size classes).

Table 1 .

 1 Description of the variables included in the analysis, their units, type of variable, scale of measure and data source.

	Variable	Description	Units	Scale	Source
	UGS size	Urban Green area extent	m 2	UGS	Urban Atlas 2012
		Tree above-ground			(see Supplementary Table
	AGB	biomass derived from	kg	Tree	S1 for source
		allometric models			information)
	Canopy cover	Absolute coverage of tree canopies	m 2	UGS	Photo-interpretation
	Canopy percentage	Relative coverage of tree canopies	%	UGS	Photo-interpretation
	Mean height woody layer	Species-specific mean height of the woody layer	m	UGS	Vegetation survey
	DBH	Diameter at breast height (~1.3m )	cm	Tree	Vegetation survey
	Woody species richness	Woody species richness	-	UGS centroid	Vegetation survey
	Species density	Amount of woody species per unit of UGA	nr. of spp./m 2 UGS	Vegetation survey

  Populusalba L. and Populus tremula L., also native in Europe, were very commonly found across the studied cities but presented a low abundance within city boundaries (i.e., they occurred in six cities in a total of 21 and 16 UGSs, respectively). In addition, the North American species Robinia pseudoacacia L., that is currently a widely-spread invasive species in Europe, was found in 55 UGSs from all the sampled cities.At city level, more than 50% of the species recorded were non-native, except in Antwerp (Table2). More than 60% of woody species in UGSs from Lisbon, Zurich, Paris and Tartu were nonnative. The woody layer (i.e., trees and shrubs) had a mean height of 8.7±0.2 m (ranging from 6.5m in Almada to 11.3m in Antwerp) and trees covered around 56% of the UGSs, ranging from 40% of UGSs in Almada and 74% in Tartu. Mean woody species density (number of species per

	1 in Poznan to 27.2 in Paris) and 9.3 species
	per hectare (9.3⋅10 -4 spp./m 2 ). The most commonly found plants were deciduous broadleaved

trees. Among them, the most widely represented species were Acer platanoides L. (occurring in 79 UGSs, 35% of the total, in five cities) and Quercus robur L. (60 UGSs, six cities). The most J o u r n a l P r e -p r o o f common conifer was Taxus baccata L. (60 UGSs, six cities) (Supplementary Table

S2

).

Table 2 .

 2 Table2). Highest woody species richness in a single UGS was found in Paris and Tartu (i.e., 101 and 48 woody species, respectively) (Table2).Mean woody species richness per UGS in Paris was 27.2±3.3 and, in the rest of the cities, it ranged from 6.1±0.3 in Poznan to 15.3±1.4 in Tartu. Woody species richness per city: total woody species (n species), mean and range (minimum and maximum) of species richness; percentage of non-native species; most predominant woody plant taxa per city; and number of UGSs investigated.

				Woody species richness
					Non-
					native	Most common genus
					species	and species (n
	City	n	Mean	Range	(%)	UGSs)	UGSs (n)
						Pinus spp. (13), Olea
	Almada	65	9.5 ± 1	4-18	54	europaea (12)	15
						Acer spp. (25),
	Antwerp	74	8.9 ± 0.6	1-18	40	Quercus robur (17), 35
						Pinus spp. (18), Olea
	Lisbon	102	8.2 ± 0.6	3-19	65	europaea (17)	34
						Acer spp. (27), Taxus
	Paris	231	27.2 ± 3.3 3-101	65	baccata (24)	36
						Acer spp. (27), Acer
	Poznan	56	6.1 ± 0.3	3-11	54	platanoides (21)	36
						Acer spp. (28),
						Betula pendula and
	Tartu	116	15.3 ± 1.4 4-48	61	Quercus robur (23)	34
						Acer spp. (26),
						Carpinus betulus
	Zurich	137	12 ± 1.2	2-27	64	(19)	35

Table 3 .

 3 Percentage of tree canopy cover, mean above-ground biomass, mean height of the woody layer and diameter at breast height (DBH) of tree plants in the seven cities.

			Mean
		Canopy	AGB	Mean
	City	cover (%)	(tons)	height (m) DBH (cm)
	Almada	40	133	8.2 ± 0.4	35 ± 3.3
	Antwerp	50	120 11.3 ± 0.4	23 ± 2.5
	Lisbon	50	105	9.3 ± 0.2	31 ± 1.5
	Paris	67	111	9.8 ± 0.2	24 ± 2.6
	Poznan	45	92 10.7 ± 0.5	26 ± 1.5
	Tartu	74	148	9.8 ± 0.2	36 ± 2.1
	Zurich	56	78 10.5 ± 0.3	20 ± 2.3

Declaration of Competing Interest

☒ The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

☐ The authors declare the following financial interests/personal relationships which may be considered as potential competing interests:

Highlights

• We recorded 418 woody species in 225 urban green spaces (UGSs) in 7 European cities • Selected cities cover a latitudinal gradient and UGSs vary in size and connectivity • Alien species were abundant ranging from 40% in Antwerp to 64% in Lisbon and Zurich • There is a strong negative correlation between UGS size and species density J o u r n a l P r e -p r o o f


Sandrine Robert

Résilience des réseaux routiers : l'exemple du Val-d'Oise

-La perception des voies dans la longue durée : les méthodes de recherche en archéogéographie

La recherche sur les voies anciennes constitue un des plus anciens thèmes de recherche en archéologie. Aux XIXe et XX e siècles, la recherche sur les voies antiques était un des chapitres essentiels de la recherche antique (GRENIER 1985(GRENIER (1934) ) : 1 -2). Les sociétés savantes naissantes réalisèrent à cette époque des inventaires départementaux ou régionaux qui sont souvent restés à la base de la recherche sur les voies anciennes jusqu'à aujourd'hui. Ils étaient déduits de l'étude des documents d'origine antique ou médiéval (carte de Peutinger, itinéraire d'Antonin etc.), de l'observation des cartes d'Etat-Major et des données de terrains (visites, recueil des observations réalisées par des agents voyers etc.). Ces tracés étaient souvent approximatifs et donnèrent lieu à de nombreuses polémiques concernant l'emplacement des lieux cités sur les documents antiques.

Aujourd'hui, cette recherche ancienne peut être renouvelée grâce aux données de terrain qui se sont multipliées avec le développement de l'archéologie préventive dans les années 1990 et grâce aux résultats de l'archéogéographie qui croise modélisation et tracés transmis. Ces informations ont l'avantage de proposer une localisation géographique précise des tronçons de voies, contrairement aux tracés souvent « flottants » de la recherche ancienne. Elles permettent aussi d'observer des itinéraires dans leur complexité et de comprendre leur interaction avec l'espace géographique (topographie, occupation etc.). D'un point de vue méthodologique, nous distinguons trois types d'approche dans l'analyse des voies anciennes.

-La reconstitution de tronçons datés

Elle consiste à cartographier des tronçons de voies observés dans des fenêtres archéologiques ou attestés par des sources historiques et à reconstituer le réseau à partir de la somme de ces observations. Cette méthode se confronte à une discontinuité importante des sources puisque la reconstitution dépend des conditions de conservation des sources anciennes, difficulté augmentée par l'espace couvert par ce type d'étude. Elle a été très tôt complétée par d'autres approches.

-La modélisation du réseau à partir des lieux habités

Plus généralement, on déduit le réseau routier à partir des noyaux d'occupation qu'il desservirait. Cette démarche s'appuie sur les sources historiques : elles décrivent avant tout des distances entre des lieux desservis par un itinéraire ou les points d'arrêt possibles (Carte de Peutinger, Itinéraire d'Antonin etc.). Depuis les années 1970, cette approche a été renforcée par une meilleure connaissance des occupations antiques sur les territoires qui donnèrent lieu à des programmes de prospection et de recueil systématique d'information archéologique (cf. programme Archéomedes, recherches sur le Lodévois, etc.). Aujourd'hui, par le biais des Systèmes d'Information Géographique (SIG), les chercheurs peuvent proposer une reconstitution théorique des anciens chemins par le biais de modèles, introduisant des contraintes géographiques comme le relief, le passage par les cours d'eau etc. (cf. GARMY et al. à paraître a et b). Dans ce type d'analyse, la difficulté se situe dans la confrontation du modèle avec le terrain. Il est nécessaire « d'accrocher » la reconstition théorique sur des tronçons attestés au sol et localisés précisément géographiquement.

-L'observation d'un état transmis du réseau

La transmission des tracés de voies sur les documents planimétriques contemporains (cadastres, carte d'Etat-Major puis photographies aériennes) permit d'enrichir cette recherche (ROBERT 2004). L'intérêt de ces sources est de donner une localisation géographique précise des tronçons. Dans les années 1990, un nouveau pas fut franchi avec l'observation d'un état transmis continu. Dans son travail sur le pays de Vaud, Eric Vion proposait de raisonner sur l'ensemble du réseau observable sur les plans contemporains plutôt que sur la somme de tronçons reconnus par la fouille ou les sources historiques. Il formula l'hypothèse suivante : « le réseau actuel est constitué de l'empilement de strates successives et [qu'] il contient en lui-même les indices de sa propre histoire. » (VION 1989 : 69). Il préconisa des tris graphiques, confrontés avec les sources classiques. Cette méthode a inspiré plusieurs études réalisées en archéogéographie planimétrique dans diverses régions de France (ROBERT 1996, MARCHAND 1997, LETURCQ 1997, JUNG 1999, ROBERT 2003a).

Aujourd'hui, l'utilisation des systèmes d'information géographique permet de synthétiser ces différentes approches à travers la compilation et le géoréférencement de l'ensemble des informations dans un même espace géographique. Puissant outil de modélisation, il facilite la comparaison entre les tracés théoriques et les données réelles sur les voies. Au Service Départemental d'Archéologie du Val-d'Oise (SDAVO), par exemple, l'utilisation du SIG a permis de développer une analyse du réseau routier sur l'ensemble du département.

-L'association des trois approches par le SIG : l'exemple du Val-d'Oise

Constitution de la base de données

Au SDAVO, une base de données a été constituée à partir du relevé systématique sur le cadastre du début du XIXe siècle, des routes, chemins, sentiers, droit de passage etc. (KRIER, SUMERA et WABONT 1996, ROBERT et COSTA à paraître). Les cadastres des 185 communes du département ont été géoréférencés, assemblés et relevés, constituant une base homogène, de 40 km sur 20km environ. Aux géométries, a été associé le nom du chemin indiqué sur le cadastre napoléonien et qui donne des informations sur les aboutissants et l'histoire du chemin. D'autres champs sémantiques ont été calculés automatiquement : la longueur du tronçon, son orientation au nord Lambert.

Modélisation

Nous sommes partis de l'hypothèse que les villes d'une certaine importance sont morphogénétiques pour le réseau des voies de grand parcours, c'est-à-dire qu'elles génèrent les formes et les transmettent dans le temps. Les villes portant le statut de "cité" étant identifiées traditionnellement comme pôles régionaux durant l'antiquité, nous avons relevé systématiquement les cités connues dans les départements limitrophes du Val-d'Oise. Dans un premier temps, nous avons relié par un axe rectiligne direct dit « attracteur » les différents points, sans introduire de contraintes de relief. Cette cartographie permettait de visualiser toutes les directions possibles d'itinéraires de grands parcours, traversant le Val-d'Oise, et d'en extraire des indications géométriques comme l'orientation. Elle permit aussi de visualiser à grande échelle le passage théorique de ces itinéraires. Cette base théorique a été confrontée avec la multitude des tracés relevés sur le cadastre.

Confrontation avec les données triées

Les données de la base élaborée à partir du cadastre napoléonien ont été classées suivant les critères suivants :

-Tri par orientation Un tri effectué sur l'ensemble des tracés a permis de relever les grandes tendances du réseau routier sur le département. On y retrouve les orientations des itinéraires historiques potentiels, connus par la bibliographie. Pour chaque itinéraire théorique, on a extrait sur la carte des voies du début du XIXe siècle, tous les tronçons entrant dans son orientation. Ils apparaissent innombrables et cette démarche nécessite un deuxième tri portant sur les données sémantiques associées à la voie.

-Tri sur le nom du tracé La recherche a porté sur le nom des aboutissants recherchés : par exemple, les villes de Senlis, Paris, Beauvais etc. A côté des routes royales connues, sont apparus des tronçons de voies portant sur quelques mètres le nom de "ancien" ou "vieux chemin de Beauvais", "rue d'Orléans" etc. En nous basant sur la synthèse faite par R. Chevalier, nous avons recherché aussi tous les toponymes pouvant révéler la présence de voies anciennes (CHEVALLIER 1997 pp. 168-171). Une carte des tronçons possédant une toponymie révélatrice de l'ancienneté de la voie a été ainsi établie.

-Proximité aux sites archéologiques Enfin, les linéaires des voies ont été croisés avec le réseau de points contenu dans la carte archéologique du SDAVO, par le biais de requêtes, non plus attributaires mais de localisation. Elles ont porté sur les sites caractérisant la présence de voies anciennes : fouilles de voiries, maladreries, nécropoles antiques ou du haut Moyen-Age. Nous avons extrait aussi les sites archéologiques, dont les structures en plan sont connues, traversés ou situés à moins de 300m des voies. Ce seuil était apparu à l'analyse de la carte archéologique autour de la chaussée Jules-César (ROBERT 2002). Pour certains sites ("Les Carreaux" à Marines1 ou "La Place" à Villers-le-Sec 2 ), les structures archéologiques s'organisent selon la voie ce qui permet de supposer une relation de contemporanéité entre les deux.

Reconstitution des tracés

Sur la base de l'ensemble de ces informations : orientation, indications toponymiques, observations archéologiques, on a associé les tronçons de voies entrant dans un même alignement pour reconstituer des tracés cohérents.

-Les résultats : des faisceaux associant voies arpentées et non arpentées

-Deux types de tracés

A côté des traditionnelles voies arpentées antiques ou modernes, caractérisées par leur tracé rectiligne sur plusieurs kilomètres, sont apparus de nombreux tracés plus sinueux mais cohérents et inscrits dans des itinéraires régionaux. Des études précédentes basées sur l'observation d'un état transmis du réseau avait déjà révélé leur existence. Dans le canton de Vaud, Eric Vion signalait dès 1989, ces innombrables « branches » constituant un itinéraire dans la durée. Il proposait de leur donner une origine pré-romaine (VION 1986 p. 90).

En Beauce, Samuel Leturcq a observé le même type de faisceau entre Etampes et la forêt d'Orléans. Il fait l'hypothèse qu'un « faisceau routier régulier et assez complexe » existait sur le plateau beauceron dès le haut Moyen-Age. Au moins deux branches principales parrallèles Paris-Orléans semblent coexister. Elles relèvent selon lui d'usages différents : la branche orientale constituant une liaison rapide pour les voyageurs légers (pélerins, voyageurs à pied, cavaliers, postes etc.), la branche médiane (actuelle RN 20) étant la route commerciale empruntée par les pondéreux (LETURCQ 1997 pp. 84-85).

Dans le Val-d'Oise, Pierre Ouzoulias déduit le même type de fonctionnement en faisceau pour l'axe Paris-Rouen à partir de l'étude des registres des visites paroissiales effectuées par Eudes Rigaud, archevêque de Rouen, entre 1248 et 1275. L'archevêque utilisait trois tracés différents pour se rendre de Paris à Rouen : la grande voie antique dite « Chaussée Jules-César », un tracé médiéval passant par la Villeneuve-Saint-Martin qui deviendra la RN 14 mais aussi un « Vieux Chemin », plus au sud. Ce dernier était utilisé préférentiellement par l'archevêque vraisemblablement parcequ'il desservait plusieurs centres villageois, qui faisaient partie des paroisses visitées. Il s'agissait alors ici d'une « spécialisation » selon un but donné (OUZOULIAS 1991).

Dans le Senonnais, Claire Marchand montre l'existence de ce type de faisceau et propose un développement antérieur au XIIe siècle -peut-être contemporain du VIIe siècle dans un cas-pour l'itinéraire Montereau-Fault-Yonne -Nemours (MARCHAND 1997).

Concernant la datation de ces voies en fouille, les données sont peu nombreuses (ou encore peu exploitées). Ces tracés sont peu connues par l'archéologie car moins spectaculaires que les grands axes stratégiques identifiés comme objets patrimoniaux depuis longtemps. De plus, véritables morphogènes du paysage, ils sont souvent encore actifs ce qui limite leur fouille. Quelques exemples confirment cependant leur ancienneté.

A Sénart, une voie présentant le même type de profil sinueux a été datée de la période antique et présentait une construction proche de celle des axes arpentés : dallage, recharges, fossés bordiers, caniveau (ROBERT 1996).

Dans le Val-d'Oise, les voies observées en fouille ont livré des datations de l'Antiquité au Moyen-Age. Elle présentait des types de constructions très divers : du simple chemin de terre à la construction en dur plus élaborée, en passant par la simple utilisation du sol géologique calcaire entayé directement par des ornières (JOBIC ET VERMEERSCH 1996, JOBIC 2001, DEVALS 2003). Certains tracés reconstitués passaient à proximité immédiate de nécropoles antiques et haut Moyen-Age. A Marines, un tronçon du « chemin de Traverse », ancien chemin de Dieppe, semble servir d'axe directeur aux structures d'occupation mérovingiennes et carolingiennes (DEVALS 2003 : 83-85).

En conclusion, ces voies inscrites dans des itinéraires régionaux mais non arpentées se développeraient au moins depuis la période antique. Leurs tracés perdurent jusqu'à aujourd'hui, même si elles ont perdu leur statut de grand parcours et la viabilité qui va avec. Elles ont coexisté avec des tracés arpentés antiques et modernes, et il n'est pas rare qu'elles aient servi de support aux tracés des routes royales qui se sont parfois contentées de redresser ces axes sineux inscrits dans les pratiques. L'Atlas de Trudaine qui superpose sur le même document les tracés à redresser et la route en projet, en montre de nombreux exemples (ex. ROBERT 2002). Leur tracé sinueux laisse penser qu'ils ne furent pas arpentés et résultent de l'usage. Certaines semblent guidées par les couloirs naturels (VION 1989 : 72) mais ce n'est pas toujours le cas. Dans le Val-d'Oise, certains tracés partent à l'assault des buttes stampiennes plus qu'ils ne les évitent (ROBERT 2003). Il faut y voir ici le rôle important joué par l'habitat qui capte à certains moments les tronçons de l'itinéraire jouant un rôle déterminant dans la dynamique de celui-ci.

-La dynamique du réseau dans la relation route/habitat

Les différents chercheurs s'accordent pour voir dans cette mobilité des tracés le résultat de la concurrence incessante des centres au cours du temps. Elle s'observe à toutes les échelles : concurrence entre les centres régionaux ou supra-régionnaux (VION 1989 p. 83), concurrence entre les centres locaux qui imposent des déviations et contournements. Les auteurs parlent alors de « captage » (VION 1989 p. 88) ou de « captures » (CHOUQUER 1983, ROBERT 2002, 2003). Ces phénomènes sont d'ailleurs utilisés pour tenter d'établir une chronologie des tracés : les lieux habités fournissent les éléments de datation qui font défauts pour les tronçons routiers. Dans le Val-d'Oise, ces exemples de captures sont nombreux et expliquent parfois l'implantation topographique contraignante adoptée par certaines voies de grands parcours. A Pontoise, l'itinéraire Paris-Rouen, matérialisé par la Chaussée Jules-César, « glisse » du plateau Saint-Martin vers l'éperon rocheux sur lequel s'implante la ville médiévale. Ces "captures" ne remettent pas en cause l'itinéraire et contribuent même à le maintenir puisqu'elles permettent l'entretien de la route aux périodes où les pouvoirs publics ne l'assurent plus (ex. pour la Chaussée Jules-César ou la Chaussée Brunehaut à partir du IIIe s. ap. J. -C.). Ainsi, l'habitat local contribue au maintien de l'itinéraire, donc à produire un niveau régional.

Inversement, le passage d'une voie de grand parcours est un facteur de pérennité pour l'habitat local, surtout si il associe une implantation topographique particulière (éperon, gué etc.) et un carrefour routier de plusieurs itinéraires. A Santeuil, par exemple, sur un transect d'environ 500m se sont succédés un site antique, une nécropole du haut Moyen-Age, et le village médiéval qui correspond au village actuel (ROBERT et al. 2001). Comme à Pontoise, c'est la convergence de plusieurs éléments : configuration gué-éperon, présence d'une rivière pour exploiter la force hydraulique, passage d'axes de grand parcours, existence d'une occupation ancienne, qui semblent intervenir dans la pérennité d'occupation.

On note que d'une manière générale, dès la période antique, voies arpentées mais aussi voies non arpentées jouent un rôle important dans l'implantation des sites. Dans le Vald'Oise, des occupations majeures comme le sanctuaire de Genainville ou l'agglomération antique d'Epiais-Rhus sont situées loin des grands axes arpentés connus. Par contre, elles sont desservies par ces voies sineuses. L'observation des réseaux de voie de l'antiquité à aujourd'hui permet de comprendre leur dynamique dans la longue durée. Ils apparaissent particulièrement résilients car, une grande partie des itinéraires connus pour l'Antiquité sont toujours actifs aujourd'hui. Cette résilience s'appuie sur la relation complexe entre les différents niveaux de formes qui constituent les itinéraires routiers.

-La résilience du réseau routier

3.1 -La dissociation itinéraire -tracé La mise en évidence de ces faisceaux complexes confirme, comme l'avaient déjà signalé Eric Vion et B. Lepetit, qu'il est nécessaire de dissocier la notion d'itinéraire et celle de tracé (VION 1989, LEPETIT 1984). On peut distinguer alors trois niveaux d'articulation des réseaux routiers : -le flux ou l'itinéraire global qui correspond à la circulation entre deux pôles.

-le tracé qui matérialise le flux dans une emprise au sol.

-le modelé qui est la forme construite de la voie, sa viabilité. Dans le Val-d'Oise, où la topographie est peu contraignante, l'itinéraire semble influencé avant tout par la distance la plus directe possible entre deux pôles, même si en contrepartie, il amène le tracé à entrer en contradiction avec la topographie locale. C'est le cas, par exemple de la Chaussée Jules-César, qui enjambe plusieurs "ravines" profondes perpendiculaires à l'axe du synclinal de la Viosne (ROBERT 2002). De même, la Chaussée Brunehaut, axe Orléans-Beauvais antique, traverse la vallée de la Viosne dans une position topographique très contraignante (ROBERT 2003). Cette distance la plus directe possible entre deux villes semble constituer l'attracteur de l'itinéraire : ce vers quoi il tend. On note que l'aboutissant peut être aussi un point topographique particulier attractif. Dans les régions au relief plus marqué, le passage d'un col peut constituer ainsi une contrainte majeure et diriger l'itinéraire (VION 1989). Dans les faits, l'itinéraire coïncide rarement exactement avec cet axe théorique représentant la distance directe. Il dessine plutôt un faisceau de tracés qui oscille de part et d'autre de cet axe, les tracés fluctuant au cours des âges, réadaptant constamment leur modelé à leur fonction.

Les différents temps des réseaux routiers

L'analyse sur la longue durée montre que les trois niveaux reconnus fonctionnent selon des temporalités différentes.

L'itinéraire (le flux à l'échelle régionale) présente une grande pérennité dans le temps. Sur les dix itinéraires observés dans le Val-d'Oise, sept sont attestés au moins depuis l'Antiquité, les troix autres depuis au moins le Moyen-Age. Deux ne se sont pas maintenus au delà de la période antique : les liaisons directes Orléans/Beauvais par le Vexin et Sens/Beauvais par le pays de France. Le développement de Paris comme noyau intermédaire semble avoir joué un rôle dans cet abandon, en capturant et redistribuant ces itinéraires.

Les tracés conservent rarement leur fonction de « grand parcours » de l'Antiquité à aujourd'hui. Dans le Val-d'Oise, la plupart tombent en désuétude au bout de trois à cinq siècles. C'est le cas, par exemple de la Chaussée Jules-César dans le Vexin (ROBERT 2002). Mais ils peuvent réinvestir cette fonction après une période de déclassement. On note ainsi d'intéressants cas de reprise de tracés anciens. La déviation de Marines, construite en 2001 pour dévier la route Paris-Dieppe du bourg, reprend le "chemin de Traverse", ancien tracé probable de l'itinéraire de grand parcours datant du haut Moyen-Age. Après un temps de hiatus, le tracé retrouve une fonction perdue gràce à la construction d'un nouveau modelé.

Le modelé possède lui-même une temporalité courte puisque les réfections sont constantes en fonction de l'usure et de l'évolution technique des moyens de locomotion. Lorsque l'on observe une route en coupe, on perçoit bien les recharges et reprises incessantes. C'est donc au niveau des tracés et du modelé que se joue la résilience du réseau, dans sa capacité à transformer des formes préexistantes ou non dans une réadaptation incessante des fonctions.

-La pérennité dans la mobilité : le rôle des tracés hérités

Au cours du temps, le flux entre constamment en conflit avec les modelés locaux liés à la route ou non : murs et portes d'enceintes, densification du bâti, topographie contraignante, viabilité inadéquate de la voie, etc. Dans nos exemples, ces conflits se règlent par la diversité des tracés potentiels hérités. Un nouveau chemin peut être tracé ou une emprise au sol, réutilisée (ex. reprise du "chemin de Traverse" à Marines). A Pontoise, au XIXe siècle, les rouliers utilisent progressivement les fossés de la ville pour éviter la ville intra-muros jugée incommode à traverser (ROBERT 2003). L'espace public transmis par les tracés hérités, constitue alors un réservoir pour la mobilité des tracés nécessaire à la résilience de l'ensemble du système routier. Mais, à l'échelle locale, on aura plutôt l'impression d'une forte mobilité.

A l'échelle régionale, on voit que cette mobilité est garante du maintien dans la longue durée de l'itinéraire. La complexité temporelle des tracés permet ces changements et leur constante mobilité maintient l'itinéraire dans son domaine d'attraction en réglant localement les conflits de flux et de modelés. Cette interaction entre flux, tracé et modelé local assure un équilibre entre le local et le régional qui est facteur de résilience, chaque échelle constituant le facteur de conservation de l'autre.

Fouille Christophe Devals en

2 Fouille François Gentili en[1995][1996]

ConclusionIl est donc important de mettre en lumière, à travers les études historiques et archéologiques, l'existence de ces faisceaux de voies. Ils peuplent nos cartes archéologiques relativement « vides » de réseaux en révélant à côté des routes arpentées, de nombreux axes relevant de l'usage. Ils montrent une dynamique complexe entre des réseaux régionaux et les implantations humaines qu'elles soient d'échelle régionale ou locale. Ils constituent, par ailleurs, des réservoirs potentiels pour l'aménagement des réseaux routiers actuels, constituant souvent encore des axes cohérents sur plusieurs kilomètres. La résilience de ces réseaux dans la longue durée nous montre aussi que l'approche historique peut enrichir le débat sur les aménagements contemporains.

Perspectives

Ce travail a été initié dans une thèse soutenue en 2003 à l'Université Paris I (ROBERT 2003). Il se prolonge aujourd'hui à travers la constitution d'un groupe de recherche autour de la dynamique des réseaux routiers du Bassin Parisien dans la longue durée, dans le cadre du programme Bassin Parisien de l'UMR 7041 ParisI-Paris X, Nanterre. Ce groupe associe archéologues et géographes et privilégie une approche diachronique de la protohistoire à aujourd'hui. Plusieurs axes de recherches sont explorés : Axe 1 : Méthodologie -approches mathématiques, modélisations, gestion de l'information renforcées par l'utilisation des SIG, -croisement des sources (traces matérielles, sources écrites, cartes anciennes, photographies aériennes etc.) , 1989. pp. 67-99.


Cristiana Gomes
email: cristiana.gomes@sophia.inria.fr

Stéphane Pérennes
email: stephane.perennes@sophia.inria.fr

Hervé Rivano
email: herve.rivano@sophia.inria.fr

Bottleneck Analysis for Routing and Call Scheduling in Multi-hop Wireless Networks

In this paper, we address the routing and call scheduling problem in which one has to find a minimum-length schedule of selected links in a TDMA (Time Division Multiple Access) based wireless network. As we deal with multi-hop networks, these selected links represent a routing solution (paths) providing enough capacity to achieve the routers requirements of bandwidth. We present a cross-layer formulation of the problem that computes joint routing and scheduling.

We use a branch-and-price algorithm to solve optimally the problem. A column generation algorithm is used to cope with the exponential set of rounds. The branch-and-bound algorithm provides mono-routing. We run experiments on networks from the literature, with different number of gateways. Experimental results as well as theoretical insights let us conjecture that the bottleneck region analysis is enough to find the optimal solution. The Integer Round-Up Property (IRUP) seems to hold for our problem.

I. INTRODUCTION

In wireless networks, the communication channels are shared among the terminals. Thus, one of the major problems faced is the reduction of capacity due to interferences caused by simultaneous transmissions [START_REF] Wang | Efficient interference-aware TDMA link scheduling for static wireless networks[END_REF]. In this work, we call a round a collection of links that can be simultaneously activated in the network. We address the problem called Round Weighting Problem (RWP) [START_REF] Klasing | On the complexity of bandwidth allocation in radio networks[END_REF] that consider joint routing and scheduling. We present a cross-layer formulation of the problem. We have to find a minimum-length schedule of selected links in a TDMA (Time Division Multiple Access) based wireless network. As we deal with multi-hop networks, these selected links represent a routing solution (paths) providing enough capacity to achieve the routers requirements of bandwidth. Scheduling methods such TDMA can guarantee achieving higher capacities by allowing time slots to be shared by simultaneous transmissions.

A communication graph G = (V, E) represents the network topology, where the nodes are the routers and the edges are the links. Interferences between links are given as a conflict graph G c . We consider the RWP as a flow routing problem. Therefore, the flows in the edges of the problem solution represent the allocated bandwidth.

We work with a special case of RW P where data are exchanged only between the routers in V r and the gateways in V g such as in Wireless Mesh networks (WMNs) or sensor networks. The input of the RW P corresponds to the communication graph G(V r ∪ V g , E), the conflict graph G c representing the edge interferences, and the network bandwidth b v required by each router v ∈ V r . In the output, each edge e ∈ E receives a positive value b e that represents the edge bandwidth from the routing problem solution. Simultaneously, we have to find a set of rounds R with their weights w(R i ) achieving the routers bandwidth ( Ri∋e w(R i ) ≥ b e ), such that the total time slots W = i w(R i ) is minimized.

We use a branch-and-price (BnP) [START_REF] Barnhart | Branch-and-price: Column generation for solving huge integer programs[END_REF] algorithm to solve optimally the problem with integer flows. A column generation algorithm is used to cope with the exponential set of rounds. The branch-and-bound algorithm provides mono-routing by turning integer the flow variables. The mono-routing is interesting to avoid dealing with the packet-reordering problem.

We run experiments on networks from the literature, with different number of gateways. Experimental results as well as theoretical insights let us conjecture that the bottleneck region analysis is enough to find the optimal solution. The bottleneck is usually the gateway considering almost uniform traffic. In particular, the Integer Round-Up Property (IRUP) seems to hold for our problem. As defined in [START_REF] Baum | Integer rounding for polymatroid and branching optimization problems[END_REF], an integer programming problem has the IRUP if its optimal value is given by the smallest integer greater than or equal to the optimal value of its LP relaxation.

In this work we study the problem of Routing and Call scheduling in multi-hop wireless networks. It can be considered as an upperbound for networks with distributed links scheduling, like in IEEE 802.11. It can also be useful in a context where centralized links scheduling is possible (e.g. IEEE 802.16) that can directly take advantage of our analysis.

This paper is organized as follows. In the next section, we discuss the related works. In section III we define the problem. In section IV, we give a description of the Branch and Price algorithm adopted. Experimental results and analysis of the bottleneck importance, mono-routing and and IRUP are presented in section V. We conclude the paper and give the future directions in section VI.

II. RELATED WORKS

A key issue in wireless networks is the interferences produced between neighboring routers. It is important to know what are the sets of transmission links that can be active at the same time, the rounds. The Round Weighting Problem RWP was introduced in [START_REF] Klasing | On the complexity of bandwidth allocation in radio networks[END_REF]. The authors make a primal/dual analysis and propose approximation algorithms for some specific network topologies. They show the NP-hardness of this problem by proving that the well-known NP-hard problem of finding the Fractional Coloring on unit graphs reduces to it. In a previous work [START_REF] Gomes | Bandwidth allocation in radio grid networks[END_REF], we gave exact bounds for the problem on grids graphs. We mainly prove that the throughput is determined by the bottleneck around the base station.

In [START_REF] Bermond | Efficient gathering in radio grids with interference[END_REF], a similar problem, the Round Scheduling Problem was treated. The relation with the round weighting problem is the following: if one must repeat rounds scheduling many times then the problem is equivalent to the RWP. The authors prove lower bounds on the number of rounds required for any two-dimensional grids and describe protocols for n x n grids with n odd that are optimal. Notice that, in [START_REF] Bermond | Efficient gathering in radio grids with interference[END_REF] the interference model is not symmetric because they deal with the exact case of gathering (directed interference).

An algorithm enumerating a tractably large subset of simultaneous transmission rounds has been developed in order to compute an approximated solution for maximum throughput using linear programming (LP) in [START_REF] Mukherjee | Throughput-range tradeoff of wireless mesh backhaul networks[END_REF]. Solving the full LP problem means generating an exponential set of scenarios which is intractable even for small networks as seen in [START_REF] Gomes | Optimal design of wireless mesh networks[END_REF]. To cope with this issue, column generation methods have been introduced, e.g. [START_REF] Gomes | Multiobjective analysis in wireless mesh networks[END_REF], [START_REF] Kompella | Multi-hop routing and scheduling in wireless networks subject to sinr constraints[END_REF], [START_REF] Zhang | Joint routing and scheduling in multi-radio multi-channel multi-hop wireless networks[END_REF] and [START_REF] Varbrand | Resource optimization of spatial tdma in ad hoc radio networks: a column generation approach[END_REF]. The work in [START_REF] Kompella | Multi-hop routing and scheduling in wireless networks subject to sinr constraints[END_REF] presents a round generation taking into account the SINR (Signal to Interference plus Noise Ratio) constraints. In [START_REF] Gomes | Multiobjective analysis in wireless mesh networks[END_REF], a multi-objective study about the Round Weighting Problem was presented that can be used to find bottlenecks position. To solve integer programs with a huge number of variables, the present work use a Branch-and-Price (BnP) [START_REF] Barnhart | Branch-and-price: Column generation for solving huge integer programs[END_REF] algorithm that combines Branch-and-bound with Column Generation. It is an extention of the work in [START_REF] Gomes | Joint gathering and coloring problem in wireless mesh networks[END_REF].

III. HYPOTHESES AND PROBLEM DEFINITION

In this section we give some definitions that will help to understand the problem. The RWP can be modeled as a graph problem. A wireless topology is represented as a digraph G = (V, E), the communication graph as illustrated in Figure 1(a).

The set of routers is represented by the set of nodes V . The set of edges E ⊆ V × V corresponds to the communication links from the real network. If a router j is located within the transmission range of a router i, considering range distance, obstacles, directional antennas, etc, then there is an edge (i, j) ∈ E.

The definition of round is flexible and permit the utilization of either binary models or physical models. The work in [START_REF] Kompella | Multi-hop routing and scheduling in wireless networks subject to sinr constraints[END_REF] presents a round generation taking into consideration the SINR constraints. As our analysis is based on flow contention (bottleneck) similar results should be obtained independently of the adopted model.

In the present work, a round is simply defined by any set of edges pairwise at distance at least d. It defines a symmetric interference model that permits the calls happen in both directions (download or upload). The most basic case is d = 1, where the set of rounds R is simply the set of the matchings of G. In other words, an active link (i, j) interferes with another links located within the interference range defined by d of the router i. The set I u,v is composed by all links interfering with the link (u, v) that defines the contention area.

In Figure 1(b), we can see an example in a grid graph.

We consider a symmetrical interference model (a link interferes all other links at distance d). It implies a symmetrical contention area in a way to permit communication in both directions. That is all edges in bold in Figure 1(b) will be interfered in both directions. This distance d is the same to all links. The conflict graph G c is the line graph power d, L d (G). For example, if d = 2 a round is an independent set of G c or an induced matching in G. In this case, the RW P is a strong edge-coloring (or a L(1,1) edge labeling) of the G with edge weights defined by the flow going through them given by a routing. These weights are simultaneously defined representing the best routing possible to reach the minimum number of colors W .

The bandwidth should be allocated between the set of nodes V r and the set of gateways

V g (V r ∪ V g = V and V r ∩ V g = ∅).
The input of the RW P corresponds to the communication graph G(V r ∪ V g , E), the conflict graph G c representing the edge interferences, and the network bandwidth b v to each router v ∈ V r . Let B = v b v . In the output, each edge e ∈ E receives a positive value b e that represents the edge bandwidth from the routing problem solution. Simultaneously to the routing problem, we have to find a set of rounds R with their weights w(R i ) achieving the routers bandwidth ( Ri∋e w(R i ) ≥ b e ), such that the total time slots W = i w(R i ) is minimized. From this set of rounds can be deduced the paths followed by the data.

IV. BRANCH AND PRICE ALGORITHM

The BnP combines Branch-and-bound (BnB) with Column Generation to solve integer program with a large number of variables. We use a Branch-and-Price (BnP) algorithm to turn integer the flow variables x of the model presented in IV-A.1.

As the BnP algorithm is well known, we give only a brief description. Each node of the BnB tree corresponds a linear program to be solved, a constraint stack that should be considered in this linear program, a list of variables that should be integer and a position in the execution stack. Each time, the execution stack saves only a part of the BnB tree. As we use a Depth-First approach, these parts correspond to exactly paths that we follow deep into the tree. We stop when we find the best objective, otherwise, a backtracking is needed. At each node of the tree, we solve a linear relaxation of the problem with column generation. Therefore, each node is repeated until no further variables price out favorably. With the optimal solution of the column generation we have a list of variables and we can choose among them how to bound the children nodes. We choose a non-integer variable to branch from the list of variables. We respect a priority order, the first variables corresponds to the flow variables around the gateway and the next ones are chosen randomly. We explain the section V why this priority order was adopted.

We start with a relaxed model at the root node with an empty constraint stack. For the execution of each node of the Branch-and-Bound tree we create two children with a copy of the father constraints stack and a new constraint each one. We push a child node of the BnB tree on the execution stack. This node is then on top of the execution stack and it will be executed next. If at any point the relaxed model of a BnB node becomes infeasible, this node is pruned. That is, it is popped out from the execution stack.

The best node is a BnB node with all its variables integer and the objective is better than the current best solution. So, this node will be used as current best solution. Otherwise, we continue splitting the problem in one or two new problems branching on a variable of the list of variables that is not integer yet. The figure 2 shows an example of a part of the BnB tree of the BnP algorithm.

Actually, we use the classical BnP algorithm with some adaptations to our problem, e.g. the branch process (priorities), which is sufficient since we observed this problem has particular characteristics that can be explored. It permits the algorithm to cut very early the BnB tree (as explained in section V), and the optimal solution is found efficiently.

A. Column Generation Method

The problem considered takes into account the complete set of rounds. Since the number of rounds is exponential, the number of columns of the constraint matrix of our model is also exponential. A column generation (CG) algorithm is used to avoid dealing with the complete set of rounds. Our CG algo-rithm has an exponential complexity (in the number of links) as well. The difference is that the brute force enumerating algorithms have the average case exponential complexity while the CG algorithm has only worst case exponential complexity.

The linear programming model to this problem is decomposed into a master problem and a sub-problem models as presented in [START_REF] Gomes | Multiobjective analysis in wireless mesh networks[END_REF]. We show this model in this section for the sake of completeness. Notice that in [START_REF] Gomes | Multiobjective analysis in wireless mesh networks[END_REF] the flow variables x are not integer that allows splitting the packet generating multiples paths. The present work makes analysis considering also these variables as integer.

We solve the master problem with a small subset of columns, which serves as an initial basis. The sub-problem is then solved to check the optimality of the solution under the current master basis and to generate new columns for the master problem. This procedure repeats until the master problem contains all columns necessary to find the optimal solution of the original problem. Considering the RWP, each column corresponds to one round.

In each iteration, if the sub-problem can find a new column that may improve the master solution, this column is inserted in the master basis and a new master solution is computed. If the sub-problem can not find, linear programming and duality theory ensure that the solution of the problem is optimal.

If we does not consider the flow variables x as integer, the master problem is a linear programming problem and therefore can be solved in polynomial time using the simplex algorithm. The complexity is solving the sub-problem which is combinatorial, and finding the optimal is NP-hard. We will see in section V that this complexity is limited to only a small part of the graph, the bottleneck region.

1) Master problem formulation: We define the following variables: Let the variable x v i,j be the flow from the router v over link i, j. The variable x v i,j is turned integer with the BnB algorithm or it remains relaxed when only column generation is employed. The integer demand from each router v is represented by the parameter b v . Let the binary parameter a r i,j be 1 if link (i, j) is active in the round r, and 0 otherwise. Recall that set I u,v is composed by all links interfering with (u, v). We define F (i,j) (u,v) = 0 if (i, j) ∈ I u,v and 1, otherwise. We define w r as the fraction of time that round r ∈ R is scheduled. Consequently, there is an induced edges capacity c i,j = r∈R a r i,j w r , ∀ (i, j) ∈ E. The master problem can be defined as follow: Given a graph G(V r ∪ V g , E), a set of routers demand b v with v ∈ V r and a set of rounds R, the problem is to assign a weight w r to each round r ∈ R. The weights represent the amount of time a round will be activated. The total amount of time needed to satisfy all demand will be w R = r∈R w(r). From the edges of the rounds can be deduced the paths followed by the data. The constraints of the master problem expressed as a linear programming model are the following:

i∈V / (v,i)∈E x v v,i = b v , ∀v ∈ V r (1)
j∈Vg i∈Vr/(i,j)∈E

x v i,j = b v , ∀v ∈ V r (2)
i∈Vr/(i,j)∈E

x v i,j - k∈V /(j,k)∈E x v j,k = 0, ∀j, v ∈ V r (3) r∈R a r i,j .w r - v∈Vr x v i,j 0, ∀i, j ∈ E (4)
Constraints (1-3) correspond to the flow constraints. Constraints (1) define the flow leaving its source router and constraints (2) define the flow arriving in a gateway. Constraints (3) represent the flow conservation, that is, the flow entering an intermediate router equals the flow leaving that router. Constraints (4) assign weights to the rounds to satisfy the flow in the edges.

2) Sub-problem formulation:

The sub-problem generates a round r with the minimal reduced cost

1 -(i,j)∈E p (i,j) .a r i,j
to enter the master basis. To express the sub-problem as a linear programming model, we have to define some additional notations. Let the parameter p (i,j) be given by the dual variable associated with the constraints (4) of the master problem. Consider the binary variable u (i,j) = 1 indicating if the edge (i, j) enters the round to be added to R, u (i,j) = 0 otherwise. The subproblem can be seen as the Maximum Weighted Independent Set Problem which is NP-hard [START_REF] Garey | Computers and intractability[END_REF]. The parameter p (i,j) corresponds to the weight of the edges. The objective function is to maximize the sum of the weights of all active edges respecting interferences. The formulation of the sub-problem is the following:

max (i,j)∈E p (i,j) u (i,j) (5)
u (i,j) + u (k,l) 1 + F (k,l) (i,j) , ∀ (i, j) ∈ E, ∀ (k, l) ∈ E (6)
The objective function (5) searches the maximum weight, which is equivalent to the minimum reduced cost. The parameter p (i,j) guides the column generation to select the best round. Constraints (6) avoid interferences according to the interference model in F .

If the value of the objective function in the sub-problem is strictly greater than 1 (e.g. the reduced cost is negative), a new column u (i,j) is found and the master basis is expanded. Otherwise, the master problem already gives the optimal solution to the original problem.

V. RESULT ANALYSIS

The model1 is implemented using the AMPL modeling language and the Branch-and-Price algorithm is implemented using ILOG Concert Technology. The instances are solved using the commercial software Cplex version 10, on a desktop PC with one gigabyte of RAM. We use the public graph representations of some mesh topologies from [START_REF] Orlowski | SNDlib 1.0-Survivable Network Design Library[END_REF] in a way to permit the reproduction of our tests. As our results are based on flow contention, they should be adequate for simplest graphs as these ones that represent an idealized view of wireless networks (e.g. unit disk graphs).

In our tests, we consider a simple interference model where each edge interferes with another one if the distance between them in graph G is lower than 2, but the model accepts other interference models. We consider equal bandwidth requirements b v = 1 for all routers, which can be interesting to provide fairness (uniform bandwidth).

We consider the RW P as a flow problem. Therefore, the flows in the edges represent the bandwidth. Table I gives the network topologies characteristics. The solutions W i (W with integer flow) to RWP obtained by the BnP algorithm are shown. Table I also shows the solutions W f (W with fractional flow) to RWP obtained using only Column Generation algorithm. The computation time to solve any instance was low, of the order of tenths of seconds.

The IRUP [START_REF] Baum | Integer rounding for polymatroid and branching optimization problems[END_REF] seems to hold for the RWP in our tests results. Table I shows that W i = ⌈W f ⌉. It does not mean that we can obtain an integer routing rounding the edges flow of a fractional solution. The IRUP is due to the fact that there is a huge concentration of traffic around the gateway (critical region) because all the flow goes toward it. Therefore, we give priority to these variables in the BnB algorithm. The work in [START_REF] Orlin | polynomial algorithm for integer programming covering problems satisfying the integer round-up property[END_REF] presents an algorithm that solve polynomially an integer program respecting the IRUP.

A. A Lower Bound

If n routers send the same b v units of flow during W slots of time, there is nb v units of flow on the edges around the gateway. If we transform these flows (weights) in new nodes of the conflict graph G c , we can see large cliques composed of the gateway and its neighborhood. The number of colors to cover the largest one is a lower bound to our problem solution. It is known that ω(G) χ f (G) χ(G) for any graph G, where ω(G) is the clique number of G, χ f (G) is the fractional chromatic number and χ(G) is the chromatic number of G.

We observe that the clique number represents already the optimal solution in our tests, as shown in Figure 3 (the letters represent the rounds). This fact is not usual. It happens only in special classes of graphs as the perfect graphs that is not the case of our graphs. Usually the clique number is derived from the bottleneck in the gateway. Otherwise, it will be derived from bottlenecks in other parts of the network. In [START_REF] Gomes | Multiobjective analysis in wireless mesh networks[END_REF] was presented an algorithm that can be used to find bottlenecks position. We can see in Table I that if there are 2 or more gateways, W is not exactly divided by the number of gateways because they have different absorption rates or because they are close and their critical regions make interference one with the other.

The RWP can be easily solved once we have covered the critical region. The links out of this region have slacks of activation. An edge have a slack when it has several possible options to get activated forming a round with edges on the critical region. It is easy to assign time slots (colors) to the edges out of this region because once we have covered the critical region they will have several possibilities to get activated whitout change the total routing time W . The traffic around the gateway is well distributed between the cliques because the model try to minimize the maximum clique, it results in cliques of the same size for the fractional result and almost the same size for the integer result. This explains why the integer coloring solution is simply the round up of the fractional coloring (W i = ⌈W f ⌉). It allows to cut efficiently the BnB tree in the BnB algorithm IV putting the current best solution objective value equal to ⌈W f ⌉ + 1.

We notice that the colors (time slots) used in the weighted min-max cliques around the gateways is enough to color all the paths. The weighted min-max cliques can be determined by a distribution of the total flow B over the links of the critical region. The cliques are generated in a way to minimize the maximal one, consequently it will minimize the total number of colors needed (total routing time W ).

We make some experiments in grid graphs with the gateway in the center. of time, and it corresponds to the optimal solution as proved by [START_REF] Gomes | Bandwidth allocation in radio grid networks[END_REF]. Another results can be seen in Figure 4, we test a larger network computing only W f . The result is already integer and if we are right it is also the result using integer flow.

B. Mono-routing

As b v = 1, the BnP algorithm give us a mono-routing that can be interesting to avoid dealing with the packet-reordering problem. With b v = 1 the BnP give only one path from each v to the gateway because the flow is turned integer. Recall that the result W f being integer does not necessarily mean the flow x is integer. In other words, the demand b v = 1 does not implie mono-routing if we permit x being fractional.

In our tests analysis, the path followed by the routers is close to a balanced spanning tree with the gateway being the root. The flows arriving at the gateway respect the min-max weighted cliques capacity. It means that distributed algorithms could solve optimally this problem considering a given optimal configuration of the critical region. Algorithms based in [START_REF] Madan | Distributed algorithms for maximum lifetime routing in wireless sensor networks[END_REF] may be an interesting option. There is an example in Figure 5 that shows the balanced spanning tree. We can also see, the complete routing with integer flows forming three cliques around of the gateway with the weights 18, 18 and 17.

VI. CONCLUSION AND PERSPECTIVES

In this article, we solve the Round Weighting Problem in order to satisfy a given demand subjected to the multiaccess interferences. We define a branch-and-price algorithm to solve optimally the non-relaxed version of this problem.

A column generation algorithm is used to avoid dealing with the whole exponential set of rounds. The branch-and-bound algorithm provides mono-routing. We make experiments with networks with different numbers of gateways.

Experimental results as well as theoretical insights let us conjecture that the bottleneck region analysis is enough to find the optimal solution. Therefore the RWP can be easily solved once we have covered this critical region. It is easy to assign time slots to the edges out of this region because, once we have covered the critical region, they will have several possibilities to get activated whitout change the total routing time W. Distributed algorithms could solve optimally this problem considering a given optimal configuration of the critical region.

The IRUP holds in our tests instances. Consequently the problem with integer flows is as easy as its relaxed version. We are getting further the proof of whether the integer roundup property holds for specific class of graphs.

  Fig. 1. Network modeling

Fig. 2 .

 2 Fig. 2. The Branch and Price algorithm

Fig. 3 .

 3 Fig. 3. Network D (B = 15) with solution W f = 18.5 and W i = 19

Figure 4 . 1 Clique 1 (Fig. 4 .Fig. 5 .

 41145 Fig. 4. Weighted Min-Max Cliques

The source code can be found at http://www-sop.inria.fr/mascotte/ personnel/Cristiana.Gomes/implementations.html

ACKNOWLEDGMENTS

The authors wish to thank Jean-Claude Bermond and Joseph Yu for helpful discussions. C. Gomes is funded by CAPES, Brazil. This work has been partially funded by European project IST/FET AEOLUS, ANR-JC OSERA, and ARC CARMA.