Slawomir Grzonka

Christian Plagemann

Giorgio Grisetti

Wolfram Burgard

Look-ahead Proposals for Robust Grid-based SLAM

Simultaneous Localization and Mapping (SLAM) is one of the classical problems in mobile robotics. The task is to build a map of the environment using on-board sensors while at the same time localizing the robot relative to this map. Rao-Blackwellized particle filters have emerged as a powerful technique for solving the SLAM problem in a wide variety of environments. It is a well-known fact for sampling-based approaches that the choice of the proposal distribution greatly influences the robustness and efficiency achievable by the algorithm. In this paper, we present a significantly improved proposal distribution for grid-based SLAM, which utilizes whole sequences of sensor measurements rather than only the most recent one. We have implemented our system on a real robot and evaluated its performance on standard data sets as well as in hard outdoor settings with few and ambiguous features. Our approach improves the localization accuracy and the map quality. At the same time, it substantially reduces the risk of mapping failures.

Introduction

The ability to construct models of natural and human-build environments is widely regarded as a precondition for autonomous service robots. Such models are required for basic tasks such as localization and motion planning. The combination of a Rao-Blackwellized particle filter (RBPF) with occupancy grid maps represents an effective and flexible solution to the SLAM problem as it only makes mild assumptions about the structure of the environment. Theoretically, given infinitely many particles, RBPFs always converge to the correct map. In practice however, only a finite number of particles can be used. This number inherently limits the uncertainty which can be represented by the filter and in this way can lead to divergence. Consider, for example, the environment depicted in the upper picture of Figure 1. This environment consists of two box-like landmarks, which cannot be perceived at the same time due to a limited sensor range. The geometric shape of these boxes needs to be represented accurately in the map as otherwise the estimate about the orientation of the robot relative to the landmark quickly gets lost. When the robot drives around a box several times the standard RBPF mapping approach typically turns the squared shape into a circle, since slight pose errors are introduced by the limited number of particles and by the suboptimal proposal distribution used. As a consequence, In comparison, our approach using k-step look-ahead proposals retains the squared shape of the boxes and yields an accurate map (lower left). Note, that due to the limited laser range the hedge was visible only at Box 1.

the particle filter loses track of the heading of the robot and yields seriously wrong maps like the one depicted in the lower right diagram of Figure 1.

In this paper, we present the so-called look-ahead mapping approach which uses improved proposals for the robot pose to increase the accuracy of the particles after the proposal step. This is achieved by performing independent, k-step localization runs for the individual particles to better align them to their local maps. In this way, the filter can deal with higher levels of noise and operate in less structured environments. Experiments with real robots demonstrate that our approach can handle situations in which state-of-the-art RBPF-based approaches, like the one using a motion model based on the odometry error [START_REF] Murphy | Bayesian map learning in dynamic environments[END_REF] or laser scan-matching error [START_REF] Hähnel | An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements[END_REF] or the one using dynamically adapted proposal distributions based on local laser scan-matching [START_REF] Grisetti | Improving grid-based slam with Rao-Blackwellized particle filters by adaptive proposals and selective resampling[END_REF] fail.

Related Work

Originally, Murphy et al. [START_REF] Doucet | Rao-Blackwellized partcile filtering for dynamic bayesian networks[END_REF][START_REF] Murphy | Bayesian map learning in dynamic environments[END_REF] have introduced Rao-Blackwellized particle filters as an effective means to solve the SLAM problem. In a RBPF, each particle represents a possible robot trajectory and a map. The framework has been subsequently extended by Montemerlo et al. [START_REF] Montemerlo | Simultaneous localization and mapping with unknown data association using FastSLAM[END_REF][START_REF] Montemerlo | FastSLAM: A factored solution to simultaneous localization and mapping[END_REF] for SLAM with discrete sets of landmarks. To efficiently learn accurate grid maps, Eliazar and Parr [START_REF] Eliazar | DP-SLAM: Fast, robust simultainous localization and mapping without predetermined landmarks[END_REF] described an efficient map representation. Additionally, Hähnel et al. [START_REF] Hähnel | An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements[END_REF] proposed an improved motion model that substantially reduces the number of particles required. Recently, Howard presented an extension towards multi-robot systems [START_REF] Howard | Multi-robot simultaneous localization and mapping using particle filters[END_REF] in which he describes how to effectively merge the information obtained by different robots. Furthermore, Grisetti et al. [START_REF] Grisetti | Improving grid-based slam with Rao-Blackwellized particle filters by adaptive proposals and selective resampling[END_REF] proposed an extension of the approach by Hähnel et al. [START_REF] Hähnel | An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements[END_REF]. Instead of using a fixed proposal distribution, their algorithm computes an improved proposal distribution on a per-particle basis, in a way similar to FastSLAM-2, as presented by Montemerlo et al. [START_REF] Montemerlo | FastSLAM 2.0: An improved particle filtering algorithm for simultaneous localization and mapping that provably converges[END_REF] for the case of landmark-based mapping.

All of the above mentioned approaches perform mapping and localization as the data is available, that is, the pose and the map uncertainty result from the very same set of observations processed. In the work presented here, we use k "future" measurements to build up a look-ahead proposal distribution for the robot pose. In this way, the uncertainty in the robot pose is reduced and consequently, less map uncertainty has to be represented by the filter.

Mapping with Rao-Blackwellized Particle Filters

The key idea of the Rao-Blackwellized particle filter for SLAM is to reason about possible robot trajectories and the corresponding maps using a sample-based representation [START_REF] Hähnel | An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements[END_REF]. Formally, the task is to estimate the joint posterior p(x 1:t , m | z 1:t , u 1:t ) of the map m and the trajectory x 1:t = x 1 , . . . , x t of the robot, given observations z 1:t = z 1 , . . . , z t and odometry measurements u 1:t = u 1 , . . . , u t . In the particle filter framework, the posterior after each time step is represented by a set of weighted trajectories x

[j] 1:t and the corresponding maps m

[j] t generated from these trajectories. Using the factorization

p(x 1:t , m t | z 1:t , u 1:t ) = p(m t | x 1:t , z 1:t ) • p(x 1:t | z 1:t , u 1:t ) , (1)
we can derive a recursive filter that in each iteration updates the trajectory samples x i 1:t and then analytically builds the corresponding map m i t . Each filter iteration consists of the following steps:

1. Sampling: The next generation of particles {x

[j] t } is obtained from the generation {x [j]
t-1 } by sampling from a proposal distribution π. Often, a probabilistic odometry-based motion model is used for π.

Importance Weighting: Importance weights w [j]

t are assigned to the individual particles according to

w [j] t = p(x [j] 1:t | z 1:t , u 1:t ) π(x [j] 1:t | z 1:t , u 1:t ) ∝ p(z t | m [j] t-1 , x [j] t )p(x [j] t | x [j] t-1 , u t ) π(x t | x [j] 1:t-1 , z 1:t , u 1:t ) •w [j] t-1 .
(2) The weights account for the fact that the proposal distribution π is in general not equal to the target distribution of successor states [START_REF] Doucet | Sequential Monte-Carlo Methods in Practice[END_REF]. 3. Resampling: Particles are drawn with replacement proportional to their importance weight. 4. Map Estimation: For each particle, the corresponding map estimate p(m

[j] | x [j] 1:t , z 1:t ) is computed based on the trajectory x [j]
1:t of that sample and the history of observations z 1:t .

The robustness and efficiency of this procedure strongly depends on the proposal distribution π that is used to sample the new state hypotheses in the selection step. If the proposal distribution differs too much from the true posterior, there is a high risk of filter divergence. In the following section, we introduce a concrete proposal distribution π that utilizes a set of "future" sensor measurements to yield better pose estimates. The resulting weight update equation is straightforward to implement, while the new approach is more robust in standard and hard, poorly-structured environments.

Look-ahead Proposals

The standard RBPF mapping approach fails in situations, in which the particle distribution significantly differs from the true posterior. This can happen when the proposal distribution π provides a bad approximation to the true one, or when the environment does not provide enough structure to allow proper particle weighting. The latter situation is illustrated in the lower right diagram of Figure 1. Due to the limited structure of the environment, the robot is unable to localize itself properly and looses the fine structure of Box 2. Before returning to its starting location, the robot is clearly delocalized, such that Box 1 appears twice in the resulting map. Such a divergence can either be avoided by using an extremely large number of particles or by directing the given number of particles to more accurate locations. We follow the latter strategy by computing the pose prediction in each iteration based on the k next sensory inputs instead of just one. These k measurements are used to better localize each particle within its own map. Concretely, for each mapping particle at time t -1, we draw l localization particles and localize them k steps ahead within their map. The resulting pose posterior at time t + k is then used to sample the successor pose of the mapping particle at time t. This process is visualized in Figure 2. By using the additional sensory input, a more informed and thus more accurate proposal for the robot pose can be computed. Formally, the idea is to compute a better estimate for the pose x t , using the previous position x t-1 , the commands (odometry) u t:t+k , and the measurements z t:t+k up to time-index t + k. As stated in Equation ( 1), the Rao-Blackwellized particle filter is an approach for sequentially estimating the distribution

p(m t |x 1:t , z 1:t ) p(x 1:t |z 1:t , u 1:t ) . (3)
Here, p(x 1:t |z 1:t , u 1:t ) is approximated using a particle filter, whose samples we will call SLAM particles. In the standard approach, the SLAM particles are drawn from a proposal distribution based on the motion model p(x t |x t-1 , u t ). In our approach, we use the more informed proposal p(x t |x t-1 , u t , z t:t+k , u t+1:t+k , m t-1 ). Such a proposal results from performing an independent k-step localization for each SLAM particle. The localization algorithm is initialized with the map and the robot pose of the corresponding SLAM particle at time t -1. Our proposal can be rewritten more compactly, omitting m

inria-00275573, version 1 -24 Apr 2008

Here η = p(z t:t+k |x t-1 u t:t+k ) -1 is the Bayes normalizer. A particle approximation of Equation 5(the localizer particles) can be obtained by sampling a sequence of poses according to the sequence of motion commands.

Each sample i has a weight v (i) t:t+k proportional to the likelihood of the chain of observations starting at t -1.

x (i) t:t+k ∼ t+k j=t p(x (i) j |x (i) j-1 , u j ) v (i) t:t+k = t+k j=t p(z (i) j |x (i) j ). (6)
A sampled approximation of the integral in Eq. 4

p(x t |x t-1 , u t:t+k , z t:t+k ) ∼ x (i) t , v (i) t (7)
is recovered from the samples in Eq. 6. This is done by truncating each trajectory x (i)

t:t+k at time t and by back-propagating the weights of the trajectory, according to Fig. 2. Due to resampling operations, the evolution of these trajectories can be described as a tree [START_REF] Eliazar | DP-SLAM: Fast, robust simultainous localization and mapping without predetermined landmarks[END_REF], thus the sample x

(i) t receives a weight v (i)
t which is the sum of the weights of its successors. The set S = x

(i) t , v (i) t
is a sampled approximation of our proposal distribution. We can draw from this set N new SLAM particles x (j) t for time t, according to the importance weights. The true posterior p(x

(j) t |x (j)
t-1 , z t , u t ) (the SLAM particles) is recovered from this set by assigning to each newly drawn sample x (j) t a weight w t according to the importance sampling principle (see Eq. 2):

w [j] t ∝ w [j] t-1 p(x (j) t |x (j) t-1 , z t , u t ) p(x (j) t |x (j) t-1 , u t:t+k , z t:t+k ) (8) ∝ w [j] t-1 p(z t |x (j) t )p(x (j) t |x (j) t-1 , u t ) p(x (j) t |x (j) t-1 , u t:t+k , z t:t+k ) (9) ∝ w [j] t-1 p(z t |x (j) t ) v (j) t (10)
The last step follows directly from Equation 7and the fact that the trajectories x (i) t:t+k had been drawn including the motion u t between t -1 and t. Note that for updating the weight of a SLAM particle, we just need the weight of the drawn successor state at time t (first iteration of the nested localization run) and the corresponding weight at time t + k(= v t ). Both values are readily available from the localization run. Equation [START_REF] Murphy | Bayesian map learning in dynamic environments[END_REF] assures, that no information (odometry, measurements) is integrated more than once. Thus, the presented approach does not change the estimated posterior distribution, but only the way it is represented by the limited particle set of the filter.

Experiments

In this section, we present a set of experiments demonstrating that our mapping approach can be applied in both indoor and outdoor scenarios. Furthermore, we compared our approach using localization proposals (termed LP in this section) to a state-of-the-art technique [START_REF] Grisetti | Improving grid-based slam with Rao-Blackwellized particle filters by adaptive proposals and selective resampling[END_REF], which uses a dynamically adapted proposal based on scan matching (SMP) and to a standard RBPF using odometry-based proposals (OP). The results show that our approach is more robust in poorly structured situations, while also providing high quality maps in more structured environments.

Measuring Map Quality

To assess the quality of the resulting maps we evaluate a measure denoted as revisiting accuracy (RA), which reflects the error in the robot pose estimate at revisited places relative to previous visits. This measure captures the internal consistency of a map. It therefore better reflects the practical usefulness of the map than for example the absolute mean squared error of the corrected trajectory relative to an assumed true one. The latter measure is overly sensitive to distortions on a global level, which does in general not lead to practical problems, and it requires a ground truth trajectory.

For calculating the revisiting accuracy, we add color markers to the ground at places that are to be traversed several times during the experiment. We then recorded the timestamps at which the robot passed over these checkpoints. Let p be a checkpoint visited at times t 1 and t 2 . The revisiting accuracy for this location is defined as

ǫ p t 1 ,t 2 = j w [j] (1 -λ)((x [j] t 1 -x [j] t 2 ) 2 + (y [j] t 1 -y [j] t 2 ) 2 ) + λ(θ [j] t 1 -θ [j] t 2 ) 2 .
Here, x, y, and θ are the components of the pose vector and λ ∈ [0, 1] is a weighing factor for the rotational component. Intuitively, the revisiting accuracy for a given checkpoint is the (weighted) distance between the estimated positions within every map, weighted by the corresponding mapprobability.

Mapping an Office Environment

We tested our approach in the highly structured office environment depicted in Figure 3. Given this dataset, we compared our approach (LP) to SMP and OP in terms of the revisiting accuracy measure defined above. depicts the maps obtained using OP (left diagram) and our approach (right diagram) for 20 mapping particles. In our approach, we used 50 localization particles per map particle and a look-ahead of k = 3. The map generated using the SMP is similar to ours. The localization accuracy is between 5 cm and 10 cm for OP and less than 5 cm for both, our approach (LP) and SMP.

Overall, a localization error of less than 10 cm is considerably small with the given grid resolution of 5 cm per cell.

Mapping a Low-Structured Outdoor Environment

We compared our approach to those proposed by Hähnel et al. [START_REF] Hähnel | An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements[END_REF] and Grisetti et al. [START_REF] Grisetti | Improving grid-based slam with Rao-Blackwellized particle filters by adaptive proposals and selective resampling[END_REF] in the outdoor environment depicted in the upper left picture of Figure 4. The robot started at the checkpoint "X", moved around the cardboard box 15 times. Thereby it returned to the checkpoint every 5th run. The laser range was limited to 4 meters, so that the box was the only visible map element. Mean and standard deviation for the approaches (left) and the ratio of runs with an error less than 0.2 (right). Note that the OP-RBPF and the SMP-RBPF approach never had an revisiting accuracy error below 0.2. Thus the success rates of both approaches is 0.

LP approach (second and third upper diagram) using 50 SLAM particles. For generating the map, we used a look-ahead of k = 5 and 100 localization particles per SLAM particle. The three lower diagrams in Figure 4 depict typical paths estimated by the three mapping approaches. The distance between the checkpoint "X" and the box is around 4 m. As can be seen from these results, OP fails to map this environment and yields a highly inconsistent map. Although, when using SMP, the map quality is higher and the box has retained its squared shape, the resulting map is still inconsistent. Our approach, in contrast, is able to deal with this hard situation and generates accurate maps. To quantitatively evaluate the performance of the approaches, we analyzed the mapping results for different numbers of particles. Each approach was executed 30 times for each setting. We measured ǫ X t first ,t last , with t first and t last being the timestamps, when the robot moved over the checkpoint "X" for the first and the last time respectively. Figure 5 (left) gives the results of this experiment. For reasons of better readability we depicted the results obtained by 50 mapping particles only. Furthermore, Figure 5 (right) depicts the success rate of the runs, defined as the ratio of runs where the revisiting error ǫ was less than 0.2.

It can be seen from these experiments, that in situations with hardly identifiable features, the performance obtained using our proposal is higher than the one obtained by the other grid based RBPF mappers [START_REF] Grisetti | Improving grid-based slam with Rao-Blackwellized particle filters by adaptive proposals and selective resampling[END_REF][START_REF] Hähnel | An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements[END_REF]. Although the RBPF based on SMP outperforms the standard RBPF, it achieves significantly less accurate maps than the technique proposed in this paper. Our approach is able to "look through gaps" of low structure until enough structure is provided for proper localization. In this way, it can handle such a hard environment even with less mapping particles (see figure 5 (right), curve obtained with 20 mapping particles and 100 localization particles for each map).

inria-00275573, version 1 -24 Apr 2008 6 Conclusions

In this paper, we presented an extension to the Rao-Blackwellized particle filter for simultaneous localization and mapping (SLAM), which significantly improves the mapping in environments which are poorly structured. Our approach uses a novel proposal distribution that looks k steps "ahead in time" to yield a more informed pose estimate for the mapping decision. We provided a mathematical derivation of the approach and showed, that the weight update for our improved proposal takes a simple form. Our method has been implemented and tested on real robot data sets. We compared our technique to two state of the art mapping techniques. Experimental results suggest that our approach yields better maps, especially in environments with sparse features that facilitate accurate localization of particles.

Fig. 1 .

 1 Fig. 1. A mobile robot with a limited sensor range navigates through the low structured environment depicted in the upper image, which consists of two cardboard boxes placed on flat, open terrain. The robot starts at Box 1, moves to Box 2, and revolves around it several times before returning to its origin. Standard mapping approaches cannot deal with the large amount of pose uncertainty build up when circling around the second box, which results in a seriously diverged map (lower right).In comparison, our approach using k-step look-ahead proposals retains the squared shape of the boxes and yields an accurate map (lower left). Note, that due to the limited laser range the hedge was visible only at Box 1.

Fig. 2 .

 2 Fig. 2. The algorithm for look-ahead pose sampling using k steps: For each mapping particle at time t -1 (first diagram), draw l localizing particles (second). Move them according to ut+i and weight them according to zt+i until t + k (third diagram). Propagate back the weights of the particles to the initial situation at time t (forth) and draw the successor state according to this distribution (right diagram). The charts above the diagrams visualize the current weights of the individual localization particles at the highlighted timeindex.

Fig. 3 .

 3 Fig. 3. Maps obtained from the indoor environment using OP (left) and LP (right).

Fig. 4 .

 4 Fig. 4. Mapping a low-structured environment (upper left): Maps obtained by OP (upper middle) and our approach (upper right). Traveled paths of the robot using OP (lower left), SMP (lower middle) and our LP approach (lower right). All approaches used 50 mapping particles. Our approach used additionally 100 localization particles per map and a lookahead of k = 5.

Figure 4

 4 Fig.5. Mean and standard deviation for the approaches (left) and the ratio of runs with an error less than 0.2 (right). Note that the OP-RBPF and the SMP-RBPF approach never had an revisiting accuracy error below 0.2. Thus the success rates of both approaches is 0.

Acknowledgment

This work has been supported by the EC under contract number FP6-IST-034120, Action line: Micro/Nano Based Sub-Systems


domain: sdv sde shs

text:
est destinée au dépôt

Radiation measurements

Atmospheric long wave radiation over Guadeloupe was measured during years 2003 to 2005. A "Pyrgeometer" (Precision Infrared Radiometer, Eppley Laboratory Inc.), a special radiation sensor using a silicon hemispheric filter transparent to thermal infrared radiation, was used.

Longwave downward radiation (Rld) data were compared to simultaneous climatic records for testing daily and annual evolution.

Main results

Pyrgeometer and radiation sensors on field

This sensor was carefully calibrated against a reference black body build in our laboratory

Hourly averages of

  Measurement and variation of the downward longwave radiation (RId) in humid tropical area (Guadeloupe) Raymond R. Bonhomme, François Bussière To cite this version: Raymond R. Bonhomme, François Bussière. Measurement and variation of the downward longwave radiation (RId) in humid tropical area (Guadeloupe). Science and Technology in a Caribbean environment, May 2006, Le Gosier (Guadeloupe), France. hal-02755741 Comment citer ce document : Fouere, A., Bonhomme, R., Bussière, F. (2006). Measurement and variation of the downward longwave radiation (RId) in humid tropical area (Guadeloupe). In: 15. Meeting of the Caribbean academy of sciences (p. p. 87). Presented at Science and Technology in a Caribbean environment, Le Gosier (Guadeloupe), FRA (2006-05-21 -2006-05-23). The Caribbean Academy of Sciences, May 21-23, 2006 Le Gosier, Guadeloupe (French West Indies) The thermal longwave downward radiation emitted by atmospheric constituents is a main component of the radiation budget at the soil surface, and is directly related to greenhouse effect. An accurate estimate of this infrared radiation is required in agronomy and forestry sciences. Direct measurements are complex and unusual in mid-latitude countries and are nearly non-existent in tropical regions. Classical estimating formulae (Ångström 1915, Brunt 1932, Brutsaert 1975, etc.) have not been calibrated for the humid tropics.

  .m -2 (compared to about 150 W.m -2 for mid-latitude clear atmospheres), corresponds to an atmospheric equivalent black-body emission from 7 to 25°C (compared to -20°C ), has a very small daily and annual variation. Repartition of hourly averages of Rld (14227 data) Conclusion


domain: sdv shs info

text:
est destinée au dépôt

Biodiversity and animal feed -future challenges for grassland production • The grassland landscape as a base for animal production -present, past and future • Biodiversity and productivity in grasslands -strategies and limitations • Forage as part of the food chain • Efficient resource utilisation for sustainable conventional and organic grassland production • Grassland-based production in Europe -pathways for future success The programme will offer plenary, parallel and poster sessions. Master-classes will be organised for young scientists. A major multidisciplinary Swedish research programme 'Management of Seminatural Grasslands -Economy and Biodiversity (HagmarksMistra)' will present final reports during the meeting.

All scientific sessions and the poster exhibition will take place at Ultuna Campus, Swedish University of Agricultural Sciences, 5 km south of Uppsala centre.

Sightseeing in Uppsala -Cathedral, Garden of Anatomical Theatre, Old Uppsala. Visit to Stockholm, the Venice of the North -Old Town, Stockholm Castle and the Vasa museum, with the only intact 17 th Century ship in the world -or shopping.

Welcome reception, BBQ and conference dinner.

Pre-conference tour to western Sweden: Farm land rich in biodiversity and beautiful scenery, castles and cultural sites, SLU -Skara campus, research farms, private farms with beef, dairy, sheep and horse breeding, agricultural industries. Mid-conference tours around Uppsala: University farm, private dairy and beef farms, equestrian centre, field research, biodiversity research on seminatural pastures. Post-conference tour to northern Sweden, Land of the Midnight Sun: Lapland -reindeer and culture, SLU -Umeå campus, forage research, forage-based milk and meat production. Hotels are in Uppsala city but some are close to the Campus. Bus transfer will be available between city hotels and the conference venue.

The fee 4 000 SEK (approx €400) includes scientific programme, proceedings, lunches and coffee, welcome reception, BBQ evening and Mid-conference tour

  Towards nitrogen self-sufficiency in mixed crop organic dairy systems: legumes and protein-rich plants contributions Xavier X. Coquil, Damien Foissy, Jean-Marie Trommenschlager, Claude Bazard, Luc Delaby, Ségolène Despres To cite this version: Xavier X. Coquil, Damien Foissy, Jean-Marie Trommenschlager, Claude Bazard, Luc Delaby, et al.. Towards nitrogen self-sufficiency in mixed crop organic dairy systems: legumes and protein-rich plants contributions. 22. General meeting of the European Grassland Federation, Jun 2008, Uppsala, Sweden. hal-02755742

European Grassland Federation

 Uppsala, Sweden 9-12 June 2008

Sweden is a small nation in a big country -fewer than nine million inhabitants in an area larger than California and nearly as large as France or Spain.

Forages, which cover one third of the arable land in Sweden, are important for maintaining a biodiverse landscape and as feed for cattle, sheep and horses. The long, moderately hot days of summer result in with a high nutritional value for livestock. Sweden has large areas (approx 500,000 ha) of seminatural grasslands that are among its most species-rich habitats, harbour many rare species and have significant historical and cultural values.

Uppsala is the fourth largest city in Sweden, with a population of around 190,000.

The city retains the charm of a small town while offering major urban opportunities and attractions. It is home to two universities, Uppsala University and SLU (Swedish University of Agricultural Sciences), and Uppsala is considered to be the religious and historical centre of Sweden. The city has a solid base of knowledge and traditions from which to progress. At the same time, the atmosphere is youthful, and more than 40,000 university students are a significant factor in this exuberance.

Sweden's oldest botanical garden, the Garden of Linnaeus, is situated in Uppsala. Carl Linnaeus' professorial residence is situated within the garden, while just outside the city is his summer residence, Linnaeus' Hammarby.

Uppsala boasts the largest cathedral in Scandinavia, one of Sweden's most famous locations of prehistoric artefacts (Old Uppsala), the unique anatomical theatre built in the 1600s by Olof Rudbeck the Elder, the great university library (Carolina Rediviva) with the Silver Bible, Uppsala Castle dating back from the mid-1500s, and many more marvellous sites and attractions.

Uppsala is located only 30 minutes from Stockholm-Arlanda international airport and 40 minutes from Stockholm, the Swedish capital, which makes it an attractive venue for meetings.


Stefano Mocali

Carlo Galeffi

Alessandro Florio

Melania Migliore

Francesco Canganella

Giovanna Bianconi

Elena Di Mattia

Elena Perrin

Anna Benedetti

Renato Fani

Electricity generation of bacterial communities using microbial fuel cells

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


Hussein Hijazi
email: hussein.hijazi@lis.inpg.fr

Laurent Ros
email: laurent.ros@lis.inpg.fr

Genevieve Jourdain

OFDM Channel Parameters Estimation used for ICI Reduction in time-varying Multipath Channels

Keywords: OFDM, ICI, SIS, channel estimation, timevarying channels. I

In this paper, we present an improved channel matrix estimation algorithm for orthogonal-frequency-divisionmultiplexing downlink mobile communication systems using comb-type pilot. The channel matrix, which contains the channel frequency response and the coefficients of inter-sub-carrierinterference (ICI), is estimated using parametric multipath channel model. In the algorithm, we assume the delays are timeinvariant over several symbols. With delays information, the multipath complex gains time average over the effective duration of each OFDM symbol are estimated using LS or LMMSE criteria. After that, the time-variation of the multipath complex gains within one OFDM symbol are obtained by using lowpass interpolation. Hence, the channel matrix can be calculated and the ICI can be reduced. The simulation results show that the proposed method, with less number of pilots and without suppression of interference, gives a good performance over LS and LMMSE estimators with low-pass interpolation and becomes better with starting interference suppression.

consist generally to estimate the channel at pilot frequencies and to interpolate the channel frequency response. The estimation of the channel at the pilot frequencies for comb-type channel estimation can be based on Least Square (LS) or Linear Minimum Mean-Square-Error (LMMSE). LMMSE has been shown to have better performance than LS [START_REF] Hsieh | Channel estimation for OFDM systems based on comb-type pilot arrangement in frequency selective fading channels[END_REF]. In [START_REF] Edfors | OFDM channel estimation by singular value decomposition[END_REF], the complexity of LMMSE is reduced by deriving an optimal low-rank estimator with singular-value-decomposition. The interpolation techniques used in channel estimation are linear interpolation, second order interpolation, low-pass interpolation, spline cubic interpolation and time domain interpolation. In [START_REF] Coleri | Channel estimation techniques based on pilot arrangement in OFDM systems[END_REF], low-pass interpolation has been shown to perform better than all the interpolation techniques.

In [START_REF] Yang | Channel estimation for OFDM transmisson in mutipath fading channels based on parametric channel modeling[END_REF] the channel estimator is based on a parametric channel model, which consists to estimate directly the time delays and complex attenuations of the multi-path channel. This estimator yields the best performance among all comb-type pilot channel estimators, with the assumption that the channel is invariant within one OFDM symbol.

In this paper, we present an improved channel matrix estimation algorithm for orthogonal frequency-division multiplexing mobile communication systems using comb-type pilot. The channel matrix, which contains the channel frequency response and the coefficiens of ICI, is computed by estimating the parameters of the multipath channel as in [START_REF] Yang | Channel estimation for OFDM transmisson in mutipath fading channels based on parametric channel modeling[END_REF] but with considering the time variation within one OFDM symbol. Typically in Radio-Frequencies communications, phases and magnitudes of the channels coefficients vary considerably faster than the channel delays. This channel nature can be exploited to design tracking algorithm, as we already did in CDMA context [START_REF] Simon | Synchronization over rapidly timevarying multipath channel for CDMA downlink RAKE receivers in Time-Division mode[END_REF] [START_REF] Simon | Adaptive multipath channel estimation in CDMA based on prefiltering and combination with a linear equalizer[END_REF]. In the present proposed algorithm, we assume that the delays are invariant (over several OFDM symbols) and perfectly estimated and only the complex gains of the paths have to be estimated. Note that an initial very performant multipath time delays estimation can be obtained by using the ESPRIT (estimation of signal parameters by rotational invariance techniques) method [START_REF] Yang | Channel estimation for OFDM transmisson in mutipath fading channels based on parametric channel modeling[END_REF] [START_REF] Roy | ESPRIT-Estimation of signal parameters via rotational invariance techniques[END_REF]. With the multipath time delays information and for a block of OFDM symbols, the complex gains time average over the effective duration of each OFDM symbol of the different path are estimated using LS or LMMSE criteria. After that, the time variation of the different path complex gains within one OFDM symbol are obtained by using low-pass interpolation. Hence, the matrix channel can be computed and the ICI can be reduced by using the succesive interference suppression (SIS). Note that instead of SIS, other detection schemes could be used from the estimated channel matrix. This paper is organized as follows. Section II introduces the OFDM baseband model and section III the improved channel matrix estimation. Next, Section IV gives some simulation results that demonstrate the effectiveness of the proposed method. We conclude the paper in Section V.

N otation: Superscripts (•) T and (•) H stand for transpose and Hermitian operators, respectively. • and (•) * are the magnitude and conjugate of a complex number, respectively.

• and • denote a vector and a matrix, respectively. A[m] denotes the mth entry of the vector A and A[m,n] denotes the [m, n]th entry of the matrix A.

II. SYSTEM MODEL

Suppose the symbol duration after serial-to-paralllel (S/P) conversion is T u . The entire signal bandwith is covered by N subcarriers, and the space between two neighboring subcarriers is 1/T u . Denote the sampling time by T s = T u /N , and assume that the length of the cyclic prefix is T g = N g T s with an integer N g . The duration of an OFDM symbol is T = (N + N g )T s . In an OFDM system, the transmitter usually applies an N -point IFFT to data block QAM-symbols {X n [k]}, where n and k represent respectively the OFDM symbol index and the subcarrier index, and adds the cyclic prefix (CP), wich is a copy of the last samples of the IFFT output, to avoid intersymbol-interference (ISI) caused by multipath fading channels. In order to limit the periodic spectrum of the discrete time signal at the output of the IFFT, we use an appropriate analog transmission filter G e (f ). As a result, the output baseband signal of the transmitter can be represented as [START_REF] Yang | Channel estimation for OFDM transmisson in mutipath fading channels based on parametric channel modeling[END_REF]:

x(t) = ∞ n=-∞ N 2 -1 k=-N 2 X n [k]φ k (t -nT ) ⊗ g e (t) (1)
where ⊗ denotes the convolution, g e (t) is the impulse response of the transmission analog filter, and φ k (t) is the subcarrier pulse that can be described by:

φ k (t) = 1 Tu e j2π k Tu t t ∈ [-T g , T u ] 0 otherwise (2)
It is assumed that the signal is transmitted over a multipath Rayleigh fading channel characterized by:

h(t, τ ) = L l=1 α l (t)δ(τ -τ l T s ) ( 3
)
where L is the total number of propagation paths, α l is the complex gains of the lth path and τ l is the lth delay normalized by the sampling time (τ l is not necessary an integer number). {α l (t)} are wide-sense stationary (WSS) narrow-band complex Gaussian processes with the so-called Jakes' power spectrum [START_REF] Jakes | Microwave Mobile Communications[END_REF] and the different path gains are uncorellated with respect to each other. At the receiver side, after passing to discret time through low pass filter and A/D and removing the guard time with the assumptions that the CP length is no less than the maximum delay, a N -point FFT is applied to transform the sequence into frequency domain. The kth subcarrier output of FFT during the nth OFDM symbol can be represented by:

Y n [k] = N 2 -1 m=-N 2 X n [m]G e [m]G r [m]H n [k, m] + W n [k] (4)
where W n [k] is a white complex Gaussian noise with variance σ 2 , G e [m] and G r [m] the transmitter and receiver filter frequency response values at the mth transmited subcarrier frequency, and H n [k, m] are the coefficients of the channel matrix from mth transmited subcarrier frequency to kth received subcarrier frequency given by:

H n [k, m] = 1 N L l=1 e -j2π m N τ l N -1 q=0 α n l [qT s ]e j2π m-k N q m, k ∈ -N 2 , N 2 -1 (5)
where {α n l [qT s ]} is the T s spaced sampling of lth path complex gain during the nth OFDM symbol.

If we assume a N transmission subcarriers within the flat region of the transmitter and receiver filter frequency response then, by using the matrix notation and omitting the index time n, (4) can be rewritten as:

Y = H X + W (6)
where G e [m] and G r [m] are assumed to be equal to one at the flat region, where X, Y , W are N × 1 vectors given by:

X = X[- N 2 ], X[- N 2 + 1], ..., X[ N 2 -1] T Y = Y [- N 2 ], Y [- N 2 + 1], ..., Y [ N 2 -1] T W = W [- N 2 ], W [- N 2 + 1], ..., W [ N 2 -1]
T and H is an N × N channel matrix, which contains the time average of the channel frequency response H[k, k] on its diagonal and the coefficiens of the inter-carrier interference

(ICI) H[k, m], k = m, otherwise.

III. CHANNEL MATRIX ESTIMATION

In this section, we propose a promising technique based on a parametric channel model where the channel matrix H given by ( 5) is estimated using L-path channel. In order to get an estimation of the channel matrix H, with the assumption that the delays are invariant and perfectly estimated, we have to estimate the sampled complex gains {α l [qT s ]} with sampling period T s .

To estimate the sampled complex gains, we propose a method based on comb-type pilot and multipath time delays information. The N p pilots are equally spaced inserted into the N subcarriers as shown in Fig 1 where L f denotes the interval in terms of the number of subcarriers between two adjacent pilots in the frequency domain. L f can be selected without the need for respecting the sampling theorem as in [START_REF] Yang | Channel estimation for OFDM transmisson in mutipath fading channels based on parametric channel modeling[END_REF] Fig. 1. Comb-Type Pilot Arrangement with L f = 3 [START_REF] Coleri | Channel estimation techniques based on pilot arrangement in OFDM systems[END_REF]. However, for the existence of matrix inverse as we will see with equation (13), N p must fulfill the following requirement:

N p ≥ L ( 7
)
Let P denote the set that contains the index positions of the N p pilot subcarriers. Then

P = {p s | p s = s L f - N 2 , s = 0, ..., N p -1} (8)
The received pilot subcarriers without ICI components are given by:

Y p = X p H p + W p (9)
where X p is an N p × N p diagonal matrix, Y p , W p are N p × 1 vectors given by:

X p = diag{X[p 0 ], X[p 1 ], ..., X[p Np-1 ]} Y p = Y [p 0 ], Y [p 1 ], ..., Y [p Np-1 ] T W p = W [p 0 ], W [p 1 ], ..., W [p Np-1 ]
T and H p is an N p × 1 vector with elements given by:

H[p s ] = L l=1 α l e -j2π ps N τ l with α l = 1 N N -1 q=0 α l [qT s ] (10)
α l is the time average over the effective duration of OFDM symbol of the lth complex gain. H p can be writen as the Fourier transform for the different complex gains time average {α l }:

H p = F p α (11)
where F p and α are respectively the N p × L Fourier transform matrix and the N p × 1 vector given by: By neglecting the ICI contribution, the estimator of α by using LS or LMMSE criteria [START_REF] Coleri | Channel estimation techniques based on pilot arrangement in OFDM systems[END_REF] [5] is:

F p =     e -j2π p 0 N τ1 • • • e -j2π p 0 N τL . . . . . . . . . e -j2π p Np -1 N τ1 • • • e -j2π p Np -1 N τL     α = [α 1 , ..., α L ] T (12)
α LS = F p H F p -1 F p H X p -1 Y p α LM M SE = F p H F p + σ 2 σ 2 p C α -1 -1 F p H X p -1 Y p (13)
where σ 2 p is the pilot variance, and C α = diag{σ 2 α1 , ..., σ 2 αL } is the covariance matrix of α where σ 2 α l is variance of α l , which will be estimated later, given by (see Appendix I):

σ 2 α l = σ 2 α l N 2 N -1 q1=0 N -1 q2=0 J 0 [2πf D (q 1 -q 2 )] (14)
The method proceeds as following:

Step 1: We group the OFDM symbol in blocks of K OFDM symbols each one. Each two consecutive blocks are intersected in two OFDM symbols as shown in Fig 2.

Step 2: For a block, we estimate the K complex gains time average of each path over the effective duration by using LS LMMSE estimator given by (13). The variance of each path can be estimated as:

σα l = var({α lLS }) (15)
where {α lLS } is the set of K complex gains time average estimated by LS of the lth path during one block of K OFDM symbols and var(•) is the variance operation.

Step 3: We suppose that the estimated complex gains time average of each path is an estimation of one T s -spaced sampling of the complex gain taken in the middle of the effective duration of OFDM symbol. Then by using the lowpass interpolation [START_REF] Coleri | Channel estimation techniques based on pilot arrangement in OFDM systems[END_REF], we interpolate by a factor (N + N g ) the K estimated samples of the complex gains for each path. Thus, we obtain the sampled complex gains {α l (qT s )} at time T s for each path during K OFDM symbols. Since the complex gain of each path exhibits a significant correlation over an interval of length the coherence time of the channel T coh , so we can choose K such as KT ≤ T coh .

Step 4: Hence, the channel matrix for each OFDM symbol can be calculated from ( 5). This is done without considering the first and the last OFDM symbols in order to avoid limiting effects of interpolation. The received data subcarriers without contribution from pilot subcarriers are given by:

Y d = H d X d + W d ( 16
)
where X d the data transmited, Y d the data received and W d the noise at data subcarrier positions are (N -N p ) × 1 vectors and H d is an (N -N p ) × (N -N p ) data channel matrix obtained by elimination rows and columns at P position in channel matrix H. By successive interference suppresion (SIS) scheme with the optimal ordering and one tap frequency equalizer the data will be estimated. The optimal ordering, which are calculated from the large to the small magnitude of the diagonal elements of the data channel matrix H d , are given by:

O = O 1 , O 2 , ..., O N -Np | (17) i < j if H d [O i , O i ] > H d [O j , O j ]
The detection algorithm can now be described as follows:

initialisation : i ← 1 O = O 1 , O 2 , ..., O N -Np Y d[i] = Y d recursion : Xe d [O i ] = Y d[i] [O i ]/H d [O i , O i ] Xd [O i ] = Q(Xe d [O i ]) Y d[i+1] = Y d[i] -Xd [O i ](H d ) Oi i ← i + 1
where Q(.) denotes the quantization operation appropriate to the constellation in use and (H d ) Oi denotes the O i th column of the data channel matrix H d .

IV. SIMULATION RESULTS

In this section, we test the performance of the improved algorithm in a multipath Rayleigh fading normalized channel. The simulations are concentrated on comparison between the LS and LMMSE channel estimations with low-pass interpolation [START_REF] Zahao | A novel Channel estimation method for OFDM Mobile Communications Systems based on pilot signals and transform domain processing[END_REF] [4] and proposed method using the LS criteria (we do not need the estimation of σ 2 α l as for LMMSE criteria (14)). The bit error rate (BER) performances in terms of the average signal-to-noise ratio (SNR) [5] [4] for Rayleigh fading channel are examined. In this paper, we use the same simulation environment as in [START_REF] Hsieh | Channel estimation for OFDM systems based on comb-type pilot arrangement in frequency selective fading channels[END_REF]. This scenario corresponds to a 16QAM-OFDM system with carrier frequency of 1GHz and bandwith of 2 MHz (note that (SN R)dB = ( E b N0 )dB + 6dB). The number of subcarriers is N = 1024, the length of the cyclic prefix is N g = 56 and the number of uniformlydistributed pilot subcarriers is 128 or 64 (i.e., L f = 8 or 16). The normalized channel model are Rayleigh as recommended by GSM Recommendations 05.05 [START_REF]European Digital Cellular Telecommunication System (Phase 2); Radio Transmission and Reception[END_REF] The proposed method is evaluated under fast-fading radio channel to have an important ICI level. So, We choose a fast vehicle speed V = 150km/h, corresponding to the high Doppler spread (normalized by 1/T ) 0.075, and K = 14 OFDM symbols in each block. The parameter R g means that we have estimated 2R g diagonals arround the main diagonal in channel matrix (in total (2R g + 1) diagonals estimated and zeros otherwise).

The legends "suppression interference, inverse diagonal (estimated), inverse diagonal (exact), LS and LMMSE pilot" denote estimation of the channel matrix with SIS and one tap frequency equalizer, estimation only of the diagonal channel matrix by the proposed method with one tap frequency equalizer, the exact diagonal channel matrix with one tap frequency equalizer, LS and LMMSE channel estimations at pilot frequencies with low-pass interpolation [START_REF] Zahao | A novel Channel estimation method for OFDM Mobile Communications Systems based on pilot signals and transform domain processing[END_REF] [4], respectively. gives the BER performance for our proposed method with R g = 1 (only 3 diagonals of channel matrix are calculated) and R g = 0 (only the main diagonal of channel matrix are calculated), LS and LMMSE estimators with L f = 8. This result shows that, without interference suppresion, our method performs better than LS and LMMSE estimators with frequency interpolation and its performance is closer to the performance of exact estimator and becomes better with starting interference suppresion. Fig 4 gives the performance of our proposed method for R g = 1, 4 and 12. It is very clear that this method offers an improvement in BER by increasing R g . The performance improved more when passing from R g = 1 to R g = 4 than passing from R g = 4 to R g = The results shows that when using more pilots, performance will be better. Moreover, with less pilots and without suppression interference, our method performs better than LS and LMMSE estimators and becomes better with starting interference suppression.

For illustration, Fig 7 shows the real and the imaginary part of the exact and estimated complex gain of all paths for one channel realization over 12 OFDM symbols with SN R = 20dB. Because the error of data detection and complex gains estimation, the ICI are not completely eliminated and give rise to an error floor as we see in all performance figures.

V. CONCLUSION

In this paper, we have presented an improved algorithm to estimate the channel matrix and mitigate the inter-sub-carrierinterference (ICI) for OFDM system by using comb-type pilots. The proposed method, with less number of pilots and without suppression of interference, gives a good performance over LS and LMMSE estimators with low-pass interpolation and becomes better with starting interference suppression. Our further work is to make a theoretical analysis in terms of channel estimation mean square error and to improve the performance of this method by making several iterations between channel estimation and interference suppression.

APPENDIX I COMPLEX GAIN TIME AVERAGE VARIANCE

The variance of the complex gain time average of the lth path given by ( 10) is calculated as:

σ 2 α l = E α l α l * = 1 N 2 N -1 q1=0 N -1 q2=0 E α l [q 1 T s ]α * l [q 2 T s ] (18)
where E[•] is the expectation operation. Since α l (t) is wide-sense stationary (WSS) narrow-band complex Gaussian processes with the so-called Jakes' power spectrum [START_REF] Jakes | Microwave Mobile Communications[END_REF] then:

E α l [q 1 T s ]α * l [q 2 T s ] = σ 2 α l J 0 [2πf D (q 1 -q 2 )] (19)
where σ 2 α l is the variance of lth path complex gain, J 0 [•] denotes the zeroth-order Bessel function of the first kind and f D is the maximum Doppler frequency normalized by 1 Ts . Inserting (19) into (18) yields the expression of the complex gain time average variance of the lth path:

σ 2 α l = σ 2 α l N 2 N -1 q1=0 N -1 q2=0 J 0 [2πf D (q 1 -q 2 )] (20)

Fig. 2 .

 2 Fig. 2. The diagram of complex gains estimator

Fig. 3 .

 3 Fig. 3. Channel matrix estimation with Rg = 1 and Lf = 8

Fig 3

 3 Fig 3 gives the BER performance for our proposed method with R g = 1 (only 3 diagonals of channel matrix are calculated) and R g = 0 (only the main diagonal of channel matrix are calculated), LS and LMMSE estimators with L f = 8. This result shows that, without interference suppresion, our method performs better than LS and LMMSE estimators with frequency interpolation and its performance is closer to the performance of exact estimator and becomes better with starting interference suppresion. Fig4gives the performance of our proposed method for R g = 1, 4 and 12. It is very clear that this method offers an improvement in BER by increasing R g . The performance improved more when passing from R g = 1 to R g = 4 than passing from R g = 4 to R g =

Fig. 4 .

 4 Fig. 4. Comparison of BERs with Rg = 1, 4 and 12 and Lf = 8 12. This is because the power of the interference which decreases quickly while moving away from the main diagonal as shown in Fig 5 for one OFDM symbol channel realization.

Fig. 5 .

 5 Fig. 5. Power of diagonals of the channel matrix

Fig. 6 .Fig. 7 .

 67 Fig. 6. Comparison of BERs with Rg = 1 and Lf = 8 and 16

  [START_REF] Zahao | A novel Channel estimation method for OFDM Mobile Communications Systems based on pilot signals and transform domain processing[END_REF], with parameters shown in the table below.

		Rayleigh Channel
	P ath N umber Average P ower(dB) N ormalized Delay
	1	-7.219	0
	2	-4.219	0.4
	3	-6.219	1
	4	-10.219	3.2
	5	-12.219	4.6
	6	-14.219	10


Azza Jedidi
email: azza.jedidi@irisa.fr

Frédéric Weis
email: frederic.weis@irisa.fr

CACHING AND SCHEDULING MECHANISMS FOR H.264 VIDEO FLOW DELIVERY OVER DISCONTINUOUS COVERAGE WIRELESS NETWORKS

Keywords: Mobility, logical discontinuous coverage wireless network, caching, scheduling, scalability, start-up delay, resource management

The past few years have witnessed the deployment of a wide variety of multimedia applications over wireless networks. As a consequence, mobile users are demanding fast and efficient connectivity, especially concerning start-up delays and flow quality. Wireless networks aim at providing an everywhere coverage without spending prohibitive deployment costs. Thus, the coverage of each access point is extended with detriment to the mean throughput of the radio cell. The coverage is continuous, but radio conditions met by users are not homogeneous. Actually, data rate is varying according to user mobility. In the context of streaming applications, intermittent high rate availability may lead to service disruption, especially when user's number increases. Thus, it is essential to design a network architecture able to efficiently deliver video flows to mobile users. In our works, a new equipment, called network cache, is introduced. The latter performs efficient flow caching and scheduling, in order to guarantee service continuity. The simulation shows that the proposed architecture gives satisfying service start-up delays and improves system scalability.

I R I S A

Mécanismes de gestion de caches et de distribution de flux H.264 pour des réseaux à couverture discontinue Résumé : Les réseaux sans fils les plus récents proposent des services et applications multimédias de plus en plus évoluées. Face à une telle offre, les utilisateurs mobiles deviennent de plus en plus exigeants, en particulier en termes de qualité des flux reçus et de rapidité du démarrage du service.

Les réseaux sans fils visent à offrir une couverture omniprésente et ce à des coûts raisonnables. L'idée est d'étendre la couverture de chaque point d'accès, au détriment du débit moyen de la cellule. La couverture radio est continue, néanmoins les conditions radio ne sont pas homogènes pour tous les utilisateurs. Le débit de données dépend en effet de la mobilité des utilisateurs. Dans le cadre particulier des applications de streaming, une baisse ponctuelle de débit peut amener à une interruption du service, en particulier lorsque la densité d'utilisateurs augmente. Il s'avère donc important de concevoir une architecture réseau capable de distribuer efficacement les flux vers les utilisateurs mobiles. Dans nos travaux, on définit un nouvel équipement réseau, appelé cache réseau (network cache). Il permet de stocker ,de conserver et d'ordonnancer efficacement les flux afin d'assurer la continuité du service. Les simulations montrent que l'architecture ainsi obtenue apporte des résultats satisfaisants en termes de latence de démarrage du service et de passage à l'échelle du système.

Mots clés : Mobilité, réseau à couverture logiquement discontinue, mise en cache, ordonnancement, mise à l'échelle, latence de démarrage de service, gestion de ressource.

Introduction

Wireless data transfers play an important role in nowadays multimedia communications, especially thanks to the increase of available bandwidth and the growing needs for mobility. As a consequence, users are demanding fast and efficient ubiquitous connectivity. They require «any-time any-where» services, without delays or disruptions. Therefore, new network infrastructures had to be designed in order to guarantee ubiquitous coverage and to face wireless network constraints, in terms of bandwidth, error rates and other perturbations linked to environment heterogeneity. In this context, the logical discontinuous coverage wireless network model has been proposed. This new model consists of a set of access points, i.e. antennas around of which are defined the radio cells. Those antennas are discontinuously spread on the network area, thus providing a «many-time many-where» service. Actually, the idea of coverage discontinuity brings two major advantages. First, as it implies the use of a fewer number of access points, the architecture deployment will be cheaper. Second, radio cells disjunction hypothesis simplifies the radio frequency band management and avoids interference problems. The mechanisms defined in the framework of discontinuous radio coverage network model can be easily applied to the context of continuous radio coverage networks, where bandwidth is highly varying. High bandwidth areas are similar to coverage areas, and low bandwidth areas are similar to out of coverage areas. The main idea is to discriminate terminals by their radio conditions in order to select the data to be sent. In fact, terminals are supplied with data when they cross high bandwidth areas (transfer areas). And, low bandwidth areas are dedicated to detecting terminals presence (presence areas). Our research team has proved through simulations that avoiding data transfer in low bandwidth areas enhances the throughput use over the network and improves system scalability [START_REF] Luu | Improving Wireless Network Capacity by Introducing Logical Discontinuous Coverage Report[END_REF]. This new logically discontinuous vision of the network makes this model fit to 3 rd generation networks, where coverage is continuous but with important bandwidth fluctuations, as well as 4 th generation networks, where radio coverage could be physically discontinuous. Even if this model simplifies network deployment, the connectivity intermittent induces important challenges in order to avoid service disruption. Thus, terminals have to take advantage of the high bandwidth available when crossing a transfer area in order to store some part of the multimedia flow on their own caches, and to consume it when crossing presence areas.

Our works focus on logical discontinuous coverage wireless networks, and aim at providing a multitude of services. In this paper, our main goal consists in designing a scalable unicast streaming service, while reducing the start-up delays. On the one hand, streaming servers are usually located in «classical» IP networks. Such networks are submitted to many constraints, like bandwidth variations. On the other hand, mobile terminals evolve in wireless logical discontinuous coverage areas, constituted of several access points. Each access point defines a high bandwidth area in each radio cell. The main idea we propose in the context of such networks, is to design an intermediate equipment that «catches» the video flows sent by the content server, and then efficiently distributes them to mobile terminals in the network. This equipment is called the network cache (see figure 1).

In a previous version of our works, the network cache acted as a temporary storage memory. Actually, it temporarily stored the part of the flow to be delivered to the mobile terminal, while the latter PI n1878

Figure 1: Logical discontinuous coverage wireless network crossed a presence area. Then, when the terminal entered a transfer area, the network cache rapidly delivered the stored flow to him, taking benefit of the high bandwidth available. More precisely, the network cache was provided with a set of buffers. Each buffer was related to a single streaming request and contained the part of the flow to be sent to the corresponding mobile terminal [START_REF] Luu | Improving Wireless Network Capacity by Introducing Logical Discontinuous Coverage Report[END_REF]. The use of buffers considerably enhanced the network scalability. In fact, it allowed users, crossing transfer areas, to take advantage of the high bandwidth available, in order to rapidly dispose of the requested flow. Flow delivery was no more subject to the bandwidth limitations at the content server level, as the flows were already stored in the network cache. Terminals also were provided with buffers to store some parts of the flow in advance (when the the terminal crosses transfer area), in order to consume it while crossing out of coverage areas and, thus, avoid service disruption. Moreover, the network cache played a scheduling role. It classified flows in priority queues, depending (1) on terminal positions in the network and (2) on terminal buffers content. The scheduling policy favored terminals which were in transfer areas, as they will rapidly receive their flows thanks to the high bandwidth available. It also favored terminals whose buffer level was under a certain threshold, in order to avoid service disruption. We proved through simulations that, thanks to the network cache buffers and the scheduling policy, the scalability of the network was considerably enhanced as the service disruption was avoided for a larger terminal density [START_REF] Luu | Improving Wireless Network Capacity by Introducing Logical Discontinuous Coverage Report[END_REF]. Nevertheless, buffers are temporary storage memories. So, the flow stored in a buffer is used by only Irisa one user, and could not benefit to users who ask for the same file later. In this paper, we propose to replace the buffers in the network cache with caching mechanisms. Actually, a copy of any requested video flow will be kept in the network cache, after the end of the streaming request. Later requests to the same video flow will be accessed faster as the flow is already stored in the cache network, nearer to the terminal than if it was in the content server. The delivery is no more subject to «classical» IP network bandwidth constraints (i.e. bandwidth constraints in the path between the content server and the network cache). Buffers, in the terminal, will also be replaced by a cache structure in order to store sufficient parts of the flow and to avoid service disruption. Moreover, we propose to bring a more efficient scheduling mechanism in the network cache, taking into account some properties of the video flow in addition to terminal position and cache level. As H.264 flows are more and more used for nowadays mobile video applications, we chose to consider H.264 video flows for our streaming service. The remainder of this paper is organized as follows: first we make a brief study of the main video flow caching and scheduling mechanisms. Then, we present the mechanisms we choose in the context of our network. After that, the targeted architecture is detailed. Finally, the performances of our solution are evaluated.

2 Related works

Video flow Caching mechanisms

Video flow caching algorithms depend on different criteria linked to the flow itself (like the flow size or encoding) or related to the network (like the available bandwidth) or even to the terminals. In fact, the choice of a caching mechanism is tightly coupled with the homogeneity or heterogeneity of terminals.

Video flow Caching mechanisms for homogeneous terminals

Several existing caching algorithms are based on the hypothesis that terminals are homogeneous. It means that they have identical, or at least similar, performances and configurations. Thus, any video object is supposed to meet the capabilities of all terminals, in terms of bandwidth and format. Those algorithms focus on how to efficiently choose the part of the flow that should be cached.

Sliding-interval caching

This method is based on caching a sliding interval of a video flow to exploit prospective sequential access to that flow. In fact, the first request recuperates the flow from the server and incrementally stores it into a proxy cache. The second request, if it occurs after a short delay, may then access the cached flow in the proxy, and flushes it after the access [START_REF] Tewari | Resource-based caching for Web servers[END_REF]. This approach may be applied for more than two requests, arriving in a short time. In that case, a set of adjacent intervals can be grouped to form a «run». The cached flow is flushed when the last request is satisfied.

Prefix Caching This approach consists of caching the prefix of a video flow, i.e. its initial portion in a proxy. Since a client requests a video flow the proxy immediately delivers to him this flow prefix. Simultaneously the proxy fetches the suffix (i.e. the remaining part of the flow) from the server and transmits it to the client [START_REF] Sen | Proxy prefix caching for multimedia streams[END_REF]. This approach reduces significantly the start-up delay as the proxies are generally closer to the clients than the media server .

Segment-based distance-sensitive caching This method proposes to group the frames of a media object into variable-sized segments. The segment length increases exponentially. Thus, the size of segment i is 2 i-1 , which consists of frames [2 i-1 , 2 i-1 +1 ... , 2 i -1]. As a consequence, the last segment length is half the cached portion length [START_REF] Wu | Segment-based proxy caching of multimedia streams[END_REF]. Such segmentation is especially interesting regarding the cache replacement policy. Indeed the latter will delete segments starting from the end of the cached flow. So, it will rapidly discard as big chunks as needed (see figure 2). Rate-Split Caching This approach consists of partitioning the video flow along the rate axis: the upper part is cached in the proxy, while the lower part remains stored at the video server (see figure 3) . It is especially interesting in the context of VBR streaming, since only the lower part, which is of a nearly constant rate, is delivered through the backbone network [START_REF] Zhang | Video staging: A proxy server-based approach to end-to-end video delivery over wide-area networks[END_REF].

Figure 3: Rate-Split Caching

Video flow Caching mechanisms for heterogeneous terminals

In some cases terminals asking for the same video flow may have quite different requirements. They may need different streaming rates or encoding formats. A solution widely adopted in commercial streaming systems is to produce replicated streams of different rates and formats. Nevertheless, this approach is very demanding in terms of bandwidth and storage. An other possibility is to transcode Irisa flows from one form to another of a lower rate or a different encoding format in an on demand way [START_REF] Tang | Streaming media caching algorithms for transcoding proxies[END_REF]. The transcoding induces intensive computation overhead, which makes this approach not scalable. A more efficient approach is the layered encoding and transmission method. Layer coders compress the flow in several layers. The base layer contains the data representing the most important elements of the flow. It represents the video flow in its minimal quality. Thus, it is the most significant layer. The other layers are hierarchically added to refine progressively the flow quality [START_REF] Kangasharju | Distributing layered encoded video through caches[END_REF].

Depending on its capabilities, the terminal will subscribe to a set of cumulative layers to reconstruct the stream.

Video flow scheduling mechanisms

In the context of logical discontinuous coverage wireless networks, video flow scheduling may become a very hard task as it is subject to a multitude of constraints, such as bandwidth limitation and asymmetry, important error rates and the high probability of service disruption due to client mobility.

Multirate wireless fair queuing (MR-FQ) algorithm consists in transmitting the video flow at different rates depending on the channel conditions [START_REF] Wang | MR-FQ: A Fair Scheduling Algorithm for Wireless Networks with Variable Transmission Rates[END_REF]. This algorithm takes into consideration both time and service fairness. This algorithm increases the overall system throughput and guarantees fairness and bounded delays.

Layered Quality Adaptation algorithm consists in adding and dropping layers of a layer encoded video stream to perform smooth flow adaptation [START_REF] Rejaie | Design Issues for Layered Quality Adaptive Internet Video Playback[END_REF]. The main goal of the algorithm is to fit available bandwidth changes, without rapid and disturbing variations in quality. Actually, congestion control changes the transmission rate rapidly, over several round-trip time, whereas, hierarchical encoding permits smooth video quality adjustment, over long periods of time. The difference between both timescales is obtained thanks to data buffering at the receiver, which smooths the rapid variations in available bandwidth and allows an almost constant number of layers to be played.

Buffer Sensitive Bandwidth Allocation algorithm recommends that a client maintains sufficient video frames at the buffer in order to improve the system adaptability and minimize the impact of overloading [START_REF] Yuen | A Fair and Adaptive Scheduling Protocol for Video Stream Transmission in Mobile Environment[END_REF]. The video playback starts only after reaching a determined buffer level. Based on the play rate of a video, the system calculates the buffer playback duration. The main idea of the method is to allocate the available bandwidth at a base station, which will serve the concurrent requests in the cell, based on their playback buffer durations.

Conclusions

Many caching algorithms could be adopted in order to design the network cache. In our works, the considered terminals are supposed to be identical. However, the constraints brought by logical coverage discontinuity can be assimilated to those linked to terminals heterogeneity. In fact, homogeneous terminals will need to receive the same file in different sizes, because they will be subject to different constraints, in terms of terminal cache level and available bandwidth. Moreover the targeted video flows are H.264 SVC (scalable video coding) ones. Those flows are layer encoded, which means that they are constituted of a base layer that represents the flow in a minimal quality, and some enhancement layers that could be hierarchically added to the base layer in order to enhance its quality. In our study, we use a model for the H.264 SVC video flows with a base layer and two enhancement layers, as shown in figure 4. The layered caching approach seems to be the most appropriate caching strategy in the context of such flow model. The layer encoded flow model that we Figure 4: Layer encoded flow model adopted suggests the quality adaptation as the most appropriate scheduling approach. Moreover, this approach favors system scalability. Our scheduling algorithm, presented in the next section, is also inspired by the Buffer Sensitive Bandwidth Allocation strategy, as we took into account the terminal cache level, when the user enters in the radio cell.

H.264 SVC flow delivery over a logical discontinuous coverage wireless network

The key element for video flows delivery in the designed network is the network cache. This equipment is mainly made of two modules: the cache and the scheduler.

The cache is divided into three parts, each of them corresponds to the memory storage of one layer. Thus, for each flow, each layer is stored in the corresponding part of the cache. And, these parts are provided with a mapping table in order to match the memory cells with the corresponding flow identifiers. A similar cache structure is adopted for terminal caches. The goals of the scheduler are (1) to guarantee the continuity of the streaming service and (2) to shorten the start-up delay. To aim that target, it has to efficiently distribute the video flows to the terminals.

In the previous version, the scheduler dynamically classified the video flows in priority queues, taking into account the terminal position (i.e. transfer area / presence area) and its buffer filling level. The streaming service was started when the buffer reached a «start-up buffer level» that corresponds to a playback duration of 30 seconds. Now, the scheduler classifies the flow layers separately. In fact, it considers the hierarchical order of layers, in addition to terminal position and cache level. As a consequence, the streaming service starting is only linked to base layer caching. Since the equivalent of 30 seconds of playback duration is cached in the terminal, the video playback starts. Moreover, as the scheduling privileges the base Irisa layer transmission, enhancement layers could be delayed or even omitted in order to guarantee service continuity. In fact, service continuity in such a flow model is equivalent to base layer streaming continuity. Actually, the level of terminal cache filling-up necessary to streaming start-up is defined by making a compromise between (1) a short start-up delay on the one hand, and (2) caching a part of the flow, sufficient to cross an out of coverage area without service disruption, on the other hand. Depending on the network conditions (i.e. available bandwidth, terminal density, etc.), enhancement layers could be progressively added or omitted, in order to "smoothly" adapt the quality of the received flows.

Combining those different criteria, we conceived the algorithm detailed below. BL refers to the base layer. EL1 represents the first enhancement layer and EL2 the second one. TA means that the terminal is located in the Transfer Area. HL refers to the critical terminal cache filling-up level. The priority queues are numbered from one to six, classified with a decreasing order of priority. Let us consider a flow requested by a terminal. The three layers of that flow will have to be classified by the scheduler. Finally for each layer, the following algorithm will be iterated. This algorithm favors service continuity as it guarantees, with the highest priority, the delivery of the base layer to terminals whose cache is under the critical threshold. Moreover, it clearly appears that it favors flow delivery to terminals which are in transfer area. In fact, they take benefit of the high bandwidth available, which allow them to store some extra part of the flow in their cache to avoid service disruption while crossing presence areas.

Our solution has been evaluated in the framework of a discrete event modeling based on a Java simulator, which uses DESMO-J (Discrete event simulation framework in Java) library [11]. The simulated surface is 1 km 2 . There are one network cache and six Access Points (AP). The server streaming rate is 1 Mb/s ( 256 kb/s for the base layer, 256 kb/s for the first enhancement layer and 512 kb/s for the second one). The simulated environment is dense urban environment like Manhattan. Each AP defines a radio cell, with a range of 50 m. A set of terminals move in a Manhattan topology, randomly crossing different radio cells and out of coverage areas, at a speed of 50 km per hour. Their cache content allows them staying out of coverage at most during 240 seconds without service disruption. The terminal may ask for any video flow in the streaming server. If this flow is already stored in the network cache, its layers are scheduled and transmitted directly from the network cache to the terminal. Else, the three layers are sent from the server, scheduled by the network cache and transmitted to the terminal, while being simultaneously stored in the network cache. The terminal can start playing the video flow since the base layer reaches the start-up threshold, which is equivalent to a playback duration of 30 seconds. In order to evaluate our system, it seems important to point out our main goals. In fact, we need to support an important number of terminals while guaranteeing short start up delays, and service continuity. To aim at that target, we adopted a layered flow model, and we took this model into account for the design of the caching and scheduling mechanisms. The main principle was to distribute the layers depending on the terminal position and cache level. We choose to guarantee service continuity, even if we had to temporarily degrade the flow quality, by omitting some enhancement layers. In the next sections, the performances of the designed system are evaluated, considering the start-up delay (section 4.1) and the system behavior when the terminal density increases (section 4.2).

Starting of the streaming application

In the starting of our streaming application, the network cache is empty. Let us consider a terminal, alone in the network. First, the terminal requests a video flow which is not already cached in the network cache. The flow is sent to the terminal from the streaming server, and simultaneously stored in the network cache. Here, our main goals are (1) to provide as quickly as possible the amount of data required at first to start the streaming application (i.e. terminal cache level = 30 s * Service Data Rate) and (2) to avoid service disruption (i.e. terminal cache level = 240 s * Service data rate). Therefore, we introduced a fast start-up period during which the network cache is able to retrieve the beginning of the stream two times faster than the normal service rate (Fast start-up rate = 2 Mb/s, normal service rate = 1 Mb/s). As the terminal is provided with a doubled data rate, the time necessary to start the streaming application decreases from 30 s to 15 s [START_REF] Luu | Improving Wireless Network Capacity by Introducing Logical Discontinuous Coverage Report[END_REF]. This fast start-up phase lasts after 240 seconds, and the flow starts to be delivered at the normal application data rate (1 Mb/s). Figure 5 illustrates the network cache content during the experiment. In this figure, the whole flow (the total of the three layers) is represented. At 240 seconds, the figure illustrates that application data rate decreases after the fast start-up phase (the graph's slope decreases). After that (at 250 seconds), the terminal decides to stop this first streaming request. At that moment, the terminal did not ended the whole flow streaming. We may notice that the flow is not totally stored in the network Irisa cache at that moment (see figure 5). The terminal cache empties at the end of the streaming request. Nevertheless, in the network cache, the part of the flow stored is kept there. Now (at 250 seconds), the terminal asks for the same flow, a second time. The second streaming request starts. A part of the flow is already cached in the network cache as shown in figure 5. This figure shows that, during this second streaming request, the part of the flow, remaining at the content server level, is still delivered to the network cache. At 400 seconds, the whole flow is stored in the network cache.

Figure 6 represents the evolution of the terminal cache content. In this figure, the flow layers are 6 shows that the terminal cache starts filling until its content reaches the playback start level (at 15 seconds). Then, the terminal starts playing the video flow at a 1 Mb/s rate, while it continues receiving the flow from the network cache at a 2 Mb/s rate. Since 240 seconds, the fast start-up period lasts and the application rate become equal to 1 Mb/s. The mobile terminal consumes its flow at the same rate it receives it, that is why we observe a plateau during this period. At 250 seconds, the terminal ends the first streaming request and empties its cache. At 250 seconds, the terminal asks for streaming the same video flow a second time. The second streaming request starts. Figure 6 shows that the base layer, and the first enhancement layer are sent at 256 kb/s, while enhancement layer 2 is transmitted at 512 kb/s. The second enhancement layer is thus received more rapidly than both the base layer and the first enhancement layer. The figure also shows that the layers are scheduled in the defined hierarchical order, which highlights the role of the scheduler. Now, the terminal cache fills-up faster, as the flow is stored at the network cache level. As a consequence, the start-up threshold is reached more rapidly (The start-up threshold is the terminal cache level which corresponds to a playback duration of 30 seconds). Actually, the start-up threshold is reached in about 2 seconds in the second request while it is reached in about 15 seconds for the first one. This demonstrates the network cache impact during service starting. We may notice that, at the beginning of the first streaming request, the network cache was empty, but when the second request starts, a part of the requested flow is already cached at the network cache. As a consequence, this part of the flow is very rapidly delivered to the terminal thanks to the high bandwidth available. Actually, as the flows are located in the network cache, they are not submitted to the bandwidth constraints at the video server level.

During the starting of a streaming request, some images might be played while only one or two layers are received. If only the base layer is received, the image is in base quality. If base layer and enhancement layer 1 are received, the quality is good. Finally, if all the layers are received, the quality is excellent. Table 1 details the percentage of images received, in each quality, by the considered terminal.

Scalability of the solution

If a terminal, alone in the network, requests a video flow already stored in the network cache, the three layers are almost immediately received in the terminal cache. As terminal density increases, reception becomes slower, because the available bandwidth is shared between users. Moreover, the flow quality may need to be degraded (by omitting enhancement layers) in order to send base layers to the whole users without service disruption. Figure 7 represents the filling-up of the cache of one terminal, for different values of terminal densities. The figure shows that the enhancement layers reception is delayed as the number of terminals increases. The idea is that the base layer of the requested flows must be sent to all terminals in order to maintain service continuity. Enhancement layers could be delayed or even omitted in order to avoid service discontinuity.

Conclusion

We work on extending logical discontinuous coverage networks to a multitude of services. This paper addresses the streaming service. We actually tried to deliver unicast video flows to a multitude of mobile terminals, in a logical discontinuous coverage network. The main goal was to guarantee a good quality of service, especially thanks to short start-up delays and system scalability. To achieve this goal, appropriate cache and scheduling modules have been designed, taking into consideration the video flow model adopted. The network cache plays a crucial role. As it is nearer to the terminals than the origin server, start-up delays are considerably reduced. Actually, flow delivery is no more submitted to bandwith limitations at content server side. Terminal caches allow flow storing in order to avoid service disruption while being in out of coverage areas, or low throughput areas.

The layered flow scheduling guarantees system scalability, thanks to the possibility of quality degradation, in order to maintain the service without any disruption. Our future work will concentrate on establishing replacement policies for the network cache, and performing new simulations while varying the scheduling algorithm.

Irisa

  A T O I R E S P U B L I C A T I O N I N T E R N E N°1878

Figure 2 :

 2 Figure 2: Segment-based distance-sensitive caching

Figure 5 :

 5 Figure 5: Network cache filling

Figure 6 :

 6 Figure 6: Terminal cache filling

Figure 7 :

 7 Figure 7: Terminal cache filling

Table 1 :

 1 Moreover, acknowl-Received images quality Received images quality Excellent quality 94,4 % edgments sent by terminals allow the network cache to avoid sending enhancement layers of images already played at the client side with base quality.Table 2 illustrates how the system progressively

	Irisa

Table 2 :

 2 Received images quality

			Received images quality
	terminals density	10	15	20	25	30	40
	Base quality	4,03 % 7,15 %	2,84 %	6,99 % 19,76 % 39,86 %
	Good quality	3,15 % 4,26 %	6,54 % 15,04 % 27,09 % 42,68 %
	Excellent quality 92,8 % 88,57 % 90,61 % 77,95 % 53,14 % 17,45 %

PI n1878