Thierry Ranchin

Lucien Wald

Data fusion of remotely sensed images using the wavelet transform: the ARSIS solution

Keywords: data fusion, remote sensing, Earth observation, wavelet transform, spatial resolution, multiresolution analysis

Earth Observation satellites are often constructed to deliver a high spatial resolution image and a set of high spectral resolution images with a lower spatial resolution. Users often want to take advantage of both the high spatial and high spectral resolutions. The ARSIS concept was specially designed to fulfill this requirement and to produce high spectral resolution images with the best spatial resolution available in the set of images with respect to the original spectral content. This concept is based on the wavelet transform and the multiresolution analysis. In this paper, the concept is presented and the different parameters are discussed. Examples of application of ARSIS to real case-studies are provided. Perspectives of use of such a concept are proposed and the benefits to user discussed.

INTRODUCTION

Earth Observation satellites, e.g., SPOT, deliver images of the Earth surface with different spatial and spectral resolutions. The geometrical description of the objects on Earth surface is reached through high spatial resolution but often one spectral band given few information about the physics of the observed processes. The radiometric description of the objects are reached through high spectral resolution images which have a lower spatial resolution. The end-users of remotely sensed data are often interested to reach the best possible description in terms of geometry and radiometry. This aim can be attained through the use of data fusion. Hence, from a set of images with different spatial and spectral resolutions, a set of images with the best available spatial resolution is constructed. Many solutions exist, but a few allow the synthesis of the images with respect to their original spectral content. The respect of the spectral content is of importance if further processing is to be applied on the synthesized images.

The ARSIS concept (from its French name Amélioration de la Résolution Spatiale par Injection de Structures) was designed to improve the spatial resolution of images in a set of images with different spatial and spectral resolutions, to the best available spatial resolution with respect to their original spectral content. This concept makes use of the wavelet transform and the multiresolution analysis. The hierarchical description of the information provided by the multiresolution analysis is combined to the wavelet transform from the image with the best spatial resolution, to synthesize the missing information in the images. This synthesis is made using a model of transformation of the wavelet coefficients which takes into account the physics of both images. Then a reconstruction is applied and the images are constructed. An evaluation of the different methods for improving the spatial resolution of images was performed to evaluate the preservation of the original spectral content, through statistical parameters. Compared to other methods, the ARSIS concept was shown as given the best achievable results [START_REF] Wald | Fusion of satellite images of different spatial resolutions: assessing the quality of resulting images[END_REF] .

In this paper, the ARSIS concept is first described. Then, different examples of application of the concept are demonstrated. Finally, some perspectives of development of the concept and some potential uses of the resulting images are enhanced.

. Further author information -T.R. (correspondence): Email: ranchin@cenerg.cma.fr; WWW: http://www-cenerg.cma.fr/~tr; Telephone: (33)

THE ARSIS CONCEPT

The ARSIS concept is based on the use of the wavelet transform and the multiresolution analysis. The multiresolution analysis allows the computation, from an original image, of coarser and coarser approximations. In this scheme, the wavelet transform allows to represents the difference of information between two successive approximations. These tools are often represented using a pyramidal scheme as proposed Figure 1. A more complete presentation of these tools in the field of remote sensing can be found in ².

Successive approximations of the original image

Original image Difference of information between two successive approximations Figure 1. Representation of the successive approximations of an image by the means of a multiresolution algorithm For all the merging processes, some pre-requisites are needed:

-images shall have different spatial and spectral resolutions, -images to merge shall represent the same area, -images shall be accurately registered, -no major change shall have occurred on the area during the interval between time acquisition of the source images.

If the last requirement is not satisfied, the aim of the merging process can be the updating of the observed area [START_REF] Ranchin | Merging SPOT-P and KVR-1000 for updating urban maps[END_REF] . These requirements are not limiting the merging process to images acquired by the same platform. The process can also apply to the merging of images acquired by airborne and spaceborne sensors. Many methods have been proposed to enhance the spatial resolution of images taking advantages of the presence of one or more images with a better spatial resolution [START_REF] Carper | The use of Intensity Hue Saturation transformations for merging SPOT panchromatic and multispectral image data[END_REF][START_REF] Chavez | Comparison of three different methods to merge multiresolution and multispectral data: Landsat TM and SPOT panchromatic[END_REF] . But, if one of the objectives is to bring each image at the best spatial resolution available, while retaining all the spectral content of the image to enhance, only a few of them satisfy it. A comparison of the most representative merging processes has been achieved by [START_REF] Wald | Fusion of satellite images of different spatial resolutions: assessing the quality of resulting images[END_REF][START_REF] Mangolini | Evaluation de la qualité des images multispectrales à haute résolution spatiale dérivées de SPOT[END_REF] .

In order to fulfill this objective, the ARSIS concept was first designed for the SPOT imagery and then generalized to the merging of images with different spatial and spectral resolutions. This concept uses the wavelet transform and the multiresolution analysis to decompose the two images to be merged as in Figure 2. Whatever this model is, the ARSIS concept preserves the spectral content of original image because of its very definition. A multiresolution analysis applied to the synthesized image B will allow the computation of an approximation similar to original image B.

As an example, Figure 3 presents the application of the ARSIS concept to the case of the SPOT imagery. The set of images is composed in this case of a panchromatic image at the spatial resolution of 10 m and three multispectral images XS1, XS2, XS3 at the spatial resolution of 20 m. The aim of the ARSIS concept is to compute the three XSi images at the spatial resolution of 10 m and to preserve the original spectral content. Two iterations of the multiresolution analysis using the wavelet transform are applied to the original panchromatic (P) image and one iteration to the original XSi image. The mother wavelet used is the one proposed by Daubechies [START_REF] Daubechies | Orthonormal bases of compactly supported wavelets[END_REF] . It is an orthogonal wavelet allowing the decorrelation of the structures between the different approximations and is implemented through a four coefficients filter. A model of transformation, for each direction, from the panchromatic wavelet coefficient images to the XSi wavelet coefficient images is estimated at the spatial resolution of 40 m. This model can be of various types. The simplest one is the identity model. A convenient one can be an adjustment of the mean and the variance of the histogram of the wavelet coefficient images. The model must take into account the physics of both images and the correlation and anti-correlation between both images. Several models have been tested [START_REF] Mangolini | Procédé et dispositif pour l'amélioration de la résolution spatiale d'images à partir d'autres images de meilleure résolution spatiale[END_REF] . The best results were achieved with a model taking into account the local variation between the P and the XSi wavelet coefficient images. The estimated model is inferred at the spatial resolution of 20 m. Then, it is applied to the transformation of the wavelet coefficient images representing the information between 10 and 20 m of the P image, into those corresponding to the XSi image. Finally, the multiresolution analysis is inverted and the XSi image at the spatial resolution of 10 m, XSi-HR, is synthesized from the original XSi image and from the wavelet coefficient images computed through the model.

Figure 4 presents the general scheme of the ARSIS concept. First a multiresolution analysis using the wavelet transform is used to compute the wavelet coefficients and the approximations of image A (1). The same operation is applied to the image B (2). The wavelet coefficients provided by each decomposition are used to compute a model of transformation of the known wavelet coefficients of image A into the known wavelet coefficients of image B. This model takes into account the physics of both images and the correlation or anti-correlation existing between both wavelet coefficients images (3). The model can have various forms and take into account more than one scale. This model is then used to compute the missing wavelet coefficients (4). The inversion of the multiresolution analysis (WT -1 ) allows the synthesis of the image B with the spatial resolution of image A (5).

In this scheme, many wavelets bases have been tested. The first tests were made using bi-orthogonal wavelets, and the orthogonal wavelets provided by Daubechies [START_REF] Daubechies | Orthonormal bases of compactly supported wavelets[END_REF] . The best results in the case of the SPOT imagery were achieved using the shortest orthogonal filter from Daubechies 7 . But the dyadic filters limit the application of the ARSIS scheme to a ratio which is a power of two between the images. Hence, other wavelets were used as the one provided by the iterated rational filters banks [START_REF] Blanc | Using iterated rational filter banks within the ARSIS method for producing 10 m Landsat multispectral images[END_REF][START_REF] Blanc | Using iterated filter banks within the ARSIS concept for producing 10 m Landsat multispectral images[END_REF] . These filters provide a (q-1/q) ratio between two successive approximations of the original image. These filters were used in the merging of SPOT HRV Panchromatic (10 m of spatial resolution) and Landsat Thematic Mapper (spatial resolution: 30 m). The low-pass and the high-pass filters used in this scheme have impulsional responses of respectively 21 and 11 coefficients. They introduce Gibbs effects in the synthesized images, which is degrading the visual quality of the results. In accordance to the experience, it is recommended to use the shortest filter possible in this scheme. Another solution to merge images with a ratio of spatial resolution different of a power of two is to interpolate the low spatial resolution images until such a ratio is obtained. Then the scheme could be applied and the multispectral set of images synthesized at the highest spatial resolution available.

EXAMPLES

The first example deals with the SPOT imagery. The SPOT HRV sensor delivers one panchromatic image with a spatial resolution of 10 m in the spectral range of 0.51 to 0.73 µm and three multispectral XS images with a spatial resolution of 20 m (spectral ranges: XS1 0.5 to 0.59 µm; XS2 0.61 to 0.68 µm; XS3 0.79 to 0.89 µm). The images were acquired simultaneously on September 11, 1990 over Barcelona (Spain). Barcelona is a large city located in the north-east of Spain, on the Mediterranean seashore. The complete area presents a harbor, an airport, urban areas with roads and motorways, rivers, agricultural lots, montaneous areas and a Mediterranean vegetation. Figure 5a presents an extract of the XS1 image on this area. This extract contains agricultural lots mixed with urban area. The roads and the motorways are clearly visible, though the interchanges on the motorways are difficult to distinguish. Figure 5b presents the same extract as Figure 5a provided by the Panchromatic sensor of SPOT. In this extract, one can clearly evaluate the difference of spatial resolution between 20 and 10 m. In the case of the panchromatic image, the interchanges can be easily follow.

The ARSIS concept allows to synthesize the multispectral images (image B) with the spatial resolution of the panchromatic image (image A), i.e. 10 m. The resulting images are called XSi-HR. The XS1-HR image is presented Figure 5c. In order to facilitate the comparison of the images, the original XS1 image was interpolated using a nearest-neighbor algorithm. The visual quality of the XS1-HR image is due to the injection of the information extracted from the panchromatic image. This information was modeled in order to reach the requirement of being as close as possible of the one that will be provided by a multiresolution analysis if the sensor have the spatial resolution of 10 m. On the XS1-HR image, one can clearly distinguish the interchanges on the motorways, the road network in the upper left corner of the image and the large buildings. The ARSIS concept allows the computation of XS images at the spatial resolution of 2 m. Figure 6b shows a composition of these synthesized images. In this case, the gap between the spatial resolution of image A and of image B is important. This area is composed of a large interchange of two urban motorways, a lot of buildings and some sandy areas. The large object at the right side of the motorway, in the lower part of the Figure 7b, is a mall. Due to the small details which appear in the synthesized image it is possible to distinguish the structures of this mall, and all the buildings in this area. The preservation of the spectral content of XS images, allows the application of a classifier, automatic or not, in order to extract the roads and the buildings.

Hence, they can be used for classification, or for other methods that need to use the multispectral content provided by the whole set of images with the best spatial resolution available. Ranchin and Wald [START_REF] Ranchin | Benefits of fusion of high spatial and spectral resolutions images for urban mapping[END_REF] have shown the improvement brought by the use of the ARSIS concept, to extract roads in urban areas by the means of classification methods.

CONCLUSION

In this paper, the ARSIS concept was introduced and exposed. This concept is a general framework for the improvement of the spatial resolution of images in a set of images with different spatial and spectral resolutions. This concept fills the requirement of preserving the spectral content of the original images. In this framework, the wavelet transform is used to model the difference of information between the different images. Many wavelet bases were tested, and it was found that the shorter the filter, the better the results. The physical part of the ARSIS concept is contained in the model of transformation of the wavelet coefficients of both images.

This concept was successfully applied to the merging of SPOT 1,2,3 HRV P and XS images, of Landsat TM 6 (120 m) and other TM images (30 m) [START_REF] Ranchin | Applications de la transformée en ondelettes et de l'analyse multirésolution au traitement des images de télédétection[END_REF] , of Landsat TM (30 m) and SPOT P (10 m) images [START_REF] Blanc | Using iterated rational filter banks within the ARSIS method for producing 10 m Landsat multispectral images[END_REF][START_REF] Blanc | Using iterated filter banks within the ARSIS concept for producing 10 m Landsat multispectral images[END_REF] and to KVR-1000 and XS images. It was also demonstrated that the concept can be applied to the future SPOT 4 [START_REF] Ranchin | Preparation of SPOT 4 mission: Production of high resolution (10 m) multispectral images using the ARSIS method[END_REF] and the future SPOT 5 [START_REF] Ranchin | Contribution of sensor fusion to urban mapping: application to simulated SPOT 5-6 data[END_REF] cases.

In a very near future, ARSIS will be applied to the merging of airborne (0.8 m) and SPOT 5 simulated images (P: 5 m; Bi: 10 m). The concept shall also be used in the improvement of the multispectral images of the future high resolution satellites like Earlybird, Quickbird, Orbview3, IKONOS 1, ... up to the spatial resolution of the panchromatic images of these sensors.

An evaluation of the quality, the potential and the usefulness of the synthesized images will be also realized in applications such as urban mapping, air quality, ecology and geology.

Figure 2 .

 2 Figure 2. The use of the multiresolution analysis in the ARSIS concept.A multiresolution analysis using the wavelet transform is applied to image A and image B, describing image A and image B at different spatial resolutions and the differences of information between the successive approximations of image A and image B. The wavelet coefficients provided by the multiresolution analysis of the high spatial resolution image A, between the scale of image A and the scale of image B, describe the missing information for the synthesis of the image B at the same spatial resolution than the one of image A.The simplest solution is to shift the wavelet coefficients from pyramid A to pyramid B and to use them to synthesize image B at the spatial resolution of image A. If the wavelet coefficients provided by image A are used without modifications, the synthesized image B will not be equivalent to "what would be seen by sensor B if it had the spatial resolution of sensor A". Hence, to improve the quality of the synthesized image, the model, to transform the wavelet coefficients provided by the multiresolution analysis of image A in the wavelet coefficients needed for the synthesis, should take into account the physics of the environment.

Figure 3 .

 3 Figure 3. Application of the ARSIS concept to the SPOT imagery

Figure 4 .

 4 Figure 4. General scheme of the ARSIS concept.

Figure 5 .Figure 6 .

 56 Figure 5. (a) Original XS1 image (20 m). Copyright CNES-SPOT Image (1990). (b) original panchromatic image (10 m). Copyright CNES-SPOT Image (1990). (c) Synthesised XS1-HR image (10 m).


Thierry Ranchin

Lucien Wald

Marc Mangolini

Efficient data fusion using wavelet

come


Xavier Pessoles

Christophe Tournier
email: christophe.tournier@lurpa.ens-cachan.fr

Automatic polishing process of plastic injection molds on a 5-axis milling center Journal of Materials Processing Technology

Keywords: Automatic Polishing, 5-axis milling center, mirror effect, surface roughness, Hilbert's curves, trochoidal curves

The plastic injection mold manufacturing process includes polishing operations when surface roughness is critical or mirror effect is required to produce transparent parts. This polishing operation is mainly carried out manually by skilled workers of subcontractor companies. In this paper, we propose an automatic polishing technique on a 5-axis milling center in order to use the same means of production from machining to polishing and reduce the costs. We develop special algorithms to compute 5-axis cutter locations on free-form cavities in order to imitate the skills of the workers. These are based on both filling curves and trochoidal curves. The polishing force is ensured by the compliance of the passive tool itself and set-up by calibration between displacement and force based on a force sensor. The compliance of the tool helps to avoid kinematical error effects on the part during 5-axis tool movements. The effectiveness of the method in terms of the surface roughness quality and the simplicity of implementation is shown through experiments on a 5-axis machining center with a rotary and tilt table.

The development of High Speed Machining (HSM) has dramatically modified the organization of plastic injection molds and tooling manufacturers. HSM in particular has made it possible to reduce mold manufacturing cycle times by replacing spark machining in many cases. In spite of these evolutions, HSM is not enable to remove the polishing operations from the process. In this paper, we deal with the realization of surfaces with high quality of surface finishing and mirror effect behavior. This means that the part must be perfectly smooth and reflective, without stripes. Such a quality is for example necessary on injection plastic mold cavities in order to obtain perfectly smooth or completely transparent plastic parts. From an economic point of view, polishing is a long and tiresome process requiring much experience. As this process is expensive in terms of price and downtime of the mold, automatic polishing has been developed. Our objective is to use the same means of production from machining to polishing, leading to cost reduction.

The aim of the paper is thus to propose a method of automatic polishing on a 5-axis machine tool.

Literature provides various automated polishing experiments. Usually, the polishing is carried out by an anthropomorphic robot, [START_REF] Wu | New polishing technology of free form surface by GC[END_REF]. Anthropomorphic robots are used for two main reasons. First, their number of axes enables them to have an easy access to any area of complex form. Second, it is possible to attach a great variety of tools and particularly spindles equipped with polishing force control mechanisms. Automatic polishing studies have been also carried out on 3 or 5-axis NC milling machine with specially designed tool to manage polishing force [START_REF] Huissoon | Automated Polishing of Die Steel Surfaces[END_REF] as well as on parallel robots [START_REF] Roswell | Modelling and analysis of contact stress for automated polishing[END_REF].

Indeed, the polishing force is a key parameter of the process. The abrasion rate increases when the polishing pressure increases [START_REF] Lin | A study of the effects of polishing on material removal rate and non-uniformity[END_REF]. But as mentioned in [START_REF] Roswell | Modelling and analysis of contact stress for automated polishing[END_REF] the contact pressure depends on the polishing force and also on the geometrical variations of the part.

An adequate polishing force facilitates the removal of cusps and stripes left on the part during milling or previous polishing operations. Nevertheless, the contact stress has to be as constant as possible to avoid over-polishing and respect form deviation tolerances.

Many authors have thus chosen to develop abrasive systems allowing a dynamic management of the polishing force. In [START_REF] Nagata | Robotic sanding system for new designed furniture with free-formed surface[END_REF], Nagata et al. use an impedance model following force control to adjust the contact force between the part and the sanding tool. In [START_REF] Ryuh | An automatic tool changer and integrated software for a robotic die polishing station[END_REF], Ryuh et al. have developed a passive tool, using a pneumatic cylinder to provide compliance and constant contact pressure between the surface and the part. A passive mechanism is also used in [START_REF] Mizugaki | Development of a Metal-Mold Polishing Robot System with Contact Pressure Control[END_REF]. The contact force is given by the compressive force of a spring coil.

In order to carry out an automatic polishing, it is important to use adapted tool trajectories. According to [START_REF] Tsai | Efficient automatic polishing process with a new compliant abrasive tool[END_REF], polishing paths should be multidirectional rather than monotonic, in order to cover uniformly the mold surface and to produce fewer undulation errors. Moreover, the multidirectional polishing path is close to what is made manually.

If we observe manual polishers, we can notice that they go back on surface areas according to various patterns such as trochoidal polishing paths (or cycloidal weaving paths [START_REF] Tsai | Efficient automatic polishing process with a new compliant abrasive tool[END_REF] (fig 1). Therefore, it could be profitable to follow such a process in order to obtain the required part quality. For instance, some papers use fractal trajectories like the Peano Curve fractal [START_REF] Mizugaki | Fractal Path Generation for a Metal-Mold Polishing Robot System and Its Evaluation by the Operability[END_REF], which is an example of a space-filling curve, rather than sweepings along parallel planes [START_REF] Tam | Robotic polishing of free-form surfaces using scanning paths[END_REF].

Elementary pattern

Elementary pattern

Multidirectional polishing

Multidirectional polishing

Figure 1 -Manual polishing patterns

This brief review of the literature shows that there is no major difficulty in using a 5axis machine for automatic polishing with a passive tool. This paper aims at showing the feasibility of automatic polishing using 5-axis machine tools and proposing some polishing strategies. In the first section, we expose how automatic polishing is possible using a 5-axis HSM center. In particular, we present the characteristics of the passive and flexible tools used. A specific attention is paid to the correlation between the imposed displacement of the tool and the resulting polishing force. Once the feasibility of 5-axis automatic polishing is proved, the various dedicated polishing strategies we have developed are detailed in section 2. These strategies are for the most part issued from previous experiences as for fractal tool trajectories coming from robotized polishing or cycloidal weaving paths representative of manual polishing. In section 3, the efficiency of our approach is tested using various test part surfaces. All the parts are milled then polished on the same production means : a 5-axis Mikron UCP710 milling centre. In the literature, the effectiveness of polishing is evaluated using the arithmetic roughness Ra [START_REF] Huissoon | Automated Polishing of Die Steel Surfaces[END_REF]. However, as it is a 2D parameter, this criterion is not really suited to reflect correctly the 3D polished surface quality. We thus suggest qualifying the finish quality of the polished surface through 3D parameters. This point is discussed in the last section as well as the comparison of the surface roughness obtained using automatic polishing with that obtained using manual polishing, a point hardly addressed in the literature. 3D surface roughness measurements are performed using non-contact measuring systems.

2 Experimental Procedure

Characteristics of the tools

As said previously, our purpose is to develop a very simple and profitable system.

Therefore, the tools used are the same than those used in manual polishing. The polishing plan is divided into two steps, pre-polishing and finishing polishing. Pre-polishing is performed with abrasive discs mounted on a suitable support. The abrasive particle size is determined by the Federation of European Producers of Abrasives standard (FEPA).

This support is a deformable part made in an elastomer material fixed on a steel shaft that allows mounting in the spindle. We thus deal with a passive tool. Hence, we do not have a force feedback control but a position one. We have studied the relationship between the deflection of the disc support and the polishing force applied to the part.

To establish this relationship, we use a Quartz force sensor Kistler 9011A mounted on a specially designed part-holder. The sensor is connected to a charger meter Kistler 5015 itself connected to the computer through a data-collection device Vernier LabPro to save the data. The experimental system is depicted in figure 2. In addition, the used sensor is a dynamic sensor. The effort must therefore change over time otherwise there would be a drift of the measure. To do so, the movement imposed on the tool over time is a triangular signal. In order to ensure the evacuation of micro chips during the polishing and guarantee a nonzero abrasion speed at the contact between the part and the tool, the tool axis u is tilted relatively to the normal vector to the polished surface n and to the feed direction f. The tilt angle θ (figure 3) is defined as follows :

Spindle

n u q f v Ce Cc Workpiece C L Figure 3 -Tool axis tilting u = cos θ • n + sin θ • f (1)
Polishing tests have been conducted considering three different tilt angles [START_REF] Nagata | Robotic sanding system for new designed furniture with free-formed surface[END_REF][START_REF] Tam | Robotic polishing of free-form surfaces using scanning paths[END_REF][START_REF] Griffits | Toolpath based on Hilbert's curve[END_REF] between the tool axis and the normal vector to the surface in the feed direction. The correlation between the tool deflection and the polishing force is shown in figure 4. The green curve (5 deg) is interrupted because the abrasive disks unstick when the tool deflection is too large. In this configuration, the tilt angle is too low and the body of the disk support, which is more rigid, comes in contact with the workpiece, which deteriorates and unsticks the disk. With a 10 or 15 degrees tilt angle, this phenomenon appears for a higher value of tool deflection, outside the graph. However, low tilt angle configurations allow faster tool movements since the rotation axes of the 5-axis machine tool are less prompted [START_REF] Lavernhe | Kinematical performance prediction in multi-axis machining for process planning optimization[END_REF]. Furthermore, it has been showed that trochoidal tool paths require a dynamic machine tool to respect the programmed feedrate [START_REF] Rauch | Hascoet, Rough pocket milling with trochoidal and plunging strategies[END_REF]. Then in simultaneous 5-axis configurations, polishing time will be greater with low tilt angles. In addition, the flexibility of the tool will help to reduce or avoid 5-axis kinematic errors [START_REF] Munlin | Optimization of a 5-axis milling machine near stationary points[END_REF].

Polishing force

Indeed, interfences between the tool and the part could happen because of great tool axis orientation evolutions between two succesive tool positions. Therefore, the disc support deflection would avoid the alteration of the mold surface.

If one considers the law of Preston [START_REF] Preston | The theory and design of plate glass polishing machine[END_REF], the material removal rate h in polishing is proportional to the average pressure of contact, P , and to the tool velocity relative to the workpiece, V :

h = K P P V (2)
where

K P is a constant ( m 2 •s
N ) including all other parameters (part material, abrasive, lubrification, etc.). Hence, in order to reach an adequate contact pressure, we must increase the tool deflection and consequently we raise the shear stress and the disk unsticks. From a kinematical behavior point of view, low rotational axes movements lead to decrease the polishing time. So we must use a rather low tilt angle (5-10 degrees) and a quite high tool deflection to ensure a satisfactory rate of material removal.

5-axis polishing tool path planning

To generate the polishing tool path, the classical description of the tool path in 5axis milling with a flat end cutter is used. This leads to define the trajectory of the tool extremity point C E as well as the orientation of the tool axis u (i, j, k) along the tool path.

With regards to polishing strategy, we use trochoidal tool paths in order to imitate the movements imparted by the workers to the spindle. To avoid marks or specific patterns on the part, we choose to generate trochoidal tool path on fractal curves in order to cover the surface in a multidirectionnal manner. We use more particularly Hilbert's curves which are a special case of the Peano's curve. These curves are used in machining as they have the advantage of covering the entire surface on which they have been generated [START_REF] Griffits | Toolpath based on Hilbert's curve[END_REF]. We will develop below the description of the Hilbert's curve which is used as a guide curve for the trochoidal curve then we will examine the trochoidal curve itself.

Hilbert's curve definition

The use of fractal trajectories presents two major interests. The first one is that tool paths do not follow specific directions which guarantees an uniform polishing. The second one is linked to the tool path programming. Indeed, tool paths are computed in the parametric space u, v of the surface, that is restricted to the [0, 1] 2 interval. Hilbert's curves are known as filling curves, covering the full unit square in the parametric space [START_REF] Sagan | Space-Filling Curves[END_REF], and consequently, the Hilbert's curves fill the 3D surface to be polished. Hilbert's curves can be defined with a recursive algorithm, the n-order curve is defined as follows :

-If n = 0 :    x 0 = 0 y 0 = 0 (3)
-Else :

   x n = 0.5[ -0.5 + y n-1 -0.5 + x n-1 0.5 + x n-1 0.5 -y n-1 ]
y n = 0.5[ -0.5 + x n-1 0.5 + y n-1 0.5 + y n-1 -0.5 -

x n-1 ] (4)
It is then easy to compute first, second or third-order and so Hilbert's curves (fig 5). In order to maintain a tangency continuity along the Hilbert's curve which is the guide curve of the trochoidal tool path, we have decided to introduce fillets on the corners of the polishing fractals. Otherwise, at each direction change on the fractal curve, the polishing tool path would be discontinuous. Resulting Hilbert's curve is depicted in figure 6. Based on this representation, the curve is easy to manipulate. For example, one could project this parametric representation directly in the 3D space or use it as the guide curve for building trochoidal curves (fig 7) as can be seen in the next section.

Mathematical definition of trochoidal curves

Based on the description of trochoidal curves proposed in [START_REF] Yates | A Handbook on Curves and Their Properties[END_REF], we define a trochoidal curve as follows. Let C(s) be a 2D parametric curve, where s is the curvilinear length (fig 8).

f(s) C ci C i n i r C D TR O i C j n j C cj O j q i q j
P(s) = C(s) + p 2π n(s) + D tr   cos( 2πs p ) sin( 2πs p ) -sin( 2πs p ) cos( 2πs p )   n(s) (5)
The issue is now to link the trochoidal curve parameters to the polishing parameters.

The amplitude A of the trochoidal curve is equal to twice its diameter A = 2•D tr . However, Indeed, when the tool is laid flat, the contact area is a disk, as can be seen in figure 9.

However, when the tool is tilted and a given displacement e is imposed to the tool, the contact area is a disc portion. The effective tool diameter can be computed with the following expressions :

D ef f = 2 D 2 2 -(l) 2 (6)
with :

l = D 2 sin θ -e tan θ (7)
and :

E = A + 2 D ef f 2 = 2D tr + D ef f (8)
This yields to the definition of the parameter D tr adjusted to build the trochoidal curve.

D tr = E -D ef f 2 = D ef f 6 = 1 3 D 2 2 - D 2 tan θ -e tan θ 2 (9)

Tool path generation

Whatever the nature of the considered surface, the polishing tool paths generation consists of three steps : computation of the tool path in the parametric space, computation of the resulting tool path in the 3D space and computation of the tool axis orientation.

Tool path generation relies on the trochoidal curve as described above. The trajectory is defined discretly. The only difficulty is to calculate the normal vector. This is done by using the points C i-1 and C i+1 and by calculating the next cross product :

n i = Z ∧ -----→ C i-1 C i+1 (10)
We now describe the method for calculating the direction of the tool axis u (figure 3). In a first approach we only use the tilt angle defined in the plane (f; n) where f is the tangent vector to the guide curve, i.e., the Hilbert's curve and n the normal vector to the machined surface. The tool axis u is tilted in relation to the Hilbert's curve tangent f rather than to the trochoidal curve in order to minimize the movements' amplitude of the rotational axes of the machine tool.

In order to compute the tangent vector f i at the contact point C Ci between the tool and the part, the following expression is used :

f i = n ∧ -------→ C Ci C C(i+1) ∧ n || -------→ C Ci C C(i+1) || (11)
The location of the tool extremity C E , which is the driven point during machining, depends on the polishing mode, i.e., by pulling or pushing the tool. The polishing mode is defined by the parameter δ :

--→ OC E = --→ OC C + r • n + δ (R -r) • v -r • u -e • z (12)
with :

v = u ∧ n ||u ∧ n|| ∧ u (13)
by noting δ = 1 when θ > 0 and δ = -1 when θ < 0.

Experiments

Within the context of plastic mold injection, we study more particularly the injection molds of electrical devices such as power sockets and switches (figure 10). We thus deal with small slender surfaces. In order to test our approach, we use two single patch test surfaces, a plane surface and a convex surface, whose curvature is a little bit larger than the mold curvature. These are machined in 50x50mm section bloks made of X38CrMoV5 steel. The Rockwell hardness of the part is 53 HRC after heat treatment.

Figure 10 -Industrial part and mold

The part is machined on a 5-axis Mikron UCP710 machine tool to reach a milling finishing state before polishing. We use four different grades of abrasive for pre-polishing (FEPA 120, 240, 600, 1200). Abrasives are 18mm diameter disks sticked on the flexible support.

For 120, 240 and 600 grades, the abrasive is made of aluminium oxide (Al2O3) within a polymeric material and of silicon carbide on paper for 1200 grade. For the final polishing, we use three synthetic diamond pastes of grade 9µm, 3µm and 1µm. Concerning the tool path, trochoidal trajectories based on Hilbert's curves for final polishing and based on straight lines for pre-polishing are used. The milling and polishing sequence is summarized in table 1.

In order to reach high feedrates during polishing, the optimization features of the Siemens Sinumerik 840D controller have been activated. In particular, the real-time inverse kinematical transformation (TRAORI) as well as real-time polynomial interpolation (COMPCURV) to produce smoother axes movements.

Results and discussion

Industrially, the resulting quality of the polished surfaces is first validated by the polisher himself by visual inspection. Surface roughness measurements with contact devices is strictly forbidden to avoid surface damages. However, new non-contact measuring technologies allow the scanning of the 3D topography of the part and data processing according to the international standard for 3D surface roughness. The International standard [START_REF]Geometrical product specifications (GPS) -Surface texture : Areal -Part 2 : Terms, definitions and surface texture parameters[END_REF] aims at characterizing 3D surface roughness through numerous parameters. Among them, it is important to identify those which are the most appropriate to qualify a mirror effect behavior. To our knowledge, there are no 3D parameter set features of a mirror effect surface. Industrial practices indicate only a Ra around 20nm.

A study by Suh et al. [START_REF] Suh | Detailed surface roughness characterization of engineering surfaces undergoing tribological testing leading to scuffing[END_REF] on the surface texture parameters shows that Sa and Sq parameters are not adequate to identify scratches on surfaces. They advise to use the parameter Ssk. Hilerio et al. [START_REF] Hilerio | 3D measurements of the knee prosthesis surfaces applied in optimizing of manufacturing progress[END_REF] also give an interpretation of the standard criteria Ssk and Sku in the context of the control of a polished prosthetic knee.

Ssk represents the symmetry of the profile :

-Ssk = 0 : profile is symmetrical to the median line, -Ssk > 0 : profile has more peaks than valleys, -Ssk < 0 : profile has more valleys than peaks.

Sku represents the distribution averaging :

-Sku > 3 : the distribution is wide (the surface is rather plane), -Sku < 3 : the distribution is tighted (the surface has a tendency to present peaks or valleys).

Once the parts are polished, we perform 3D surface roughness measurements using a non-contact measuring system (Talysurf CCI 6000). We perform measurements on polished parts with our approach (the plane and the convex surface) and on a plane that has been polished manually by a professional (figure 11). Measurement results are reported in table 2.

It can be observed that the convex surface automatically polished presents larger geometric deviations as well as a higher Sa and Sq than those observed for the planar surface.

In other words, the rate of material removal is not as good as on the planar surface while trajectories are the same in the (u, v) parametric space. There are several explanations for this behavior. First, the used polishing pattern, generated in the parametric space, is the same than the planar surface whereas the surface area of the convex part is greater.

The result is a lower coverage rate. This can also be explained by the machine kinematical behavior during polishing for each part. The planar surface is polished with a 3 axes kinematic while the convex surface requires simultaneous interpolation of the 5 axes of the machine tool. During machining, the relative feedrate between the tool and the part does not match the programmed one due to the slow rotary axes of the 5-axis machining (A : 15rpm ; C : 20rpm) [START_REF] Lavernhe | Kinematical performance prediction in multi-axis machining for process planning optimization[END_REF]. This leads to a slower and less smooth trajectory, reducing the polishing efficiency.

Sa and Sq are larger for the convex surface but the polished part provides a mirror effect behavior anyway. This confirms the remarks mentioned in [START_REF] Suh | Detailed surface roughness characterization of engineering surfaces undergoing tribological testing leading to scuffing[END_REF] and [START_REF] Hilerio | 3D measurements of the knee prosthesis surfaces applied in optimizing of manufacturing progress[END_REF] as well as the "mean effect" of these parameters. Mirror effect behavior seems to depend on the Ssk and Sku parameters. Indeed, their values for the convex surface are in adequation with those observed for planar surfaces, which also provide mirror effect behavior. Regarding the peaks and valleys, the three examples exhibit the same order of magnitude for the parameter Sku with a small advantage for manual polishing. The numerical values correspond fairly well with the observations. Finally, we can suppose that the polishing process should be optimized regarding the Ssk and Sku parameters prior to the Sa and Sq parameters.

Conclusion

In this article, we propose a solution to produce mirror effect polished surfaces on a 5-axis machine tool normally dedicated to molds' milling. The passive tool used is simple to implement. A preliminary calibration allows us to correlate the polishing force and the tool deviation. We have also developed polishing tool paths similar to the patterns used in manual polishing in order to avoid marks on the polished part. The polishing quality is comparable to the manual method and polishing time is similar. However, in order to maintain a constant coverage rate, we should take into consideration the effective area of the part to be polished when generating the tool paths in the (u, v) plane. From roughness point of view, the polishing process must reduce the amplitude of the peaks and valleys which is characterized by a Sku parameter superior to 3. For complex shapes, kinematic performances of the machine tool are very important in order to guarantee a tool feedrate as high as possible and smooth, thus leading to a good rate of material removal. In particular, rotary axes have to be very performing to respect the programmed feedrate. We seek now to develop polishing strategies that allow the polishing of small radius blending surfaces on the injection moulds.

  Geometric parameters C E (X E , Y E , Z E ) tool extremity point (u, v) coordinates in the parametric space Trochoidal curve parameters s curvilinear abscissa C (s) parametric equation of the guiding curve P (s) parametric equation of the trochoide curve n (s) normal vector of the guiding curve p step of the trochoid D tr diameter of the usefull circle to construct the trochoid A amplitude of the trochoid Step step between two loops of trochoide Technological parameters D tool diameter D ef f effective diameter of the tool during polishing E amplitude of the envelope of the polishing strip e displacement induced by the compression of the tool θ tilt angle of the tool axis u (i, j, k) tool axis f tangent vector of the guide curve C c point onto the trochoidal curve Ra arithmetic average deviation of the surface (2D) Sa arithmetical mean height of the surface (3D) Sq root-mean-square deviation of the surface Ssk skewness of topography height distribution Sku kurtosis of topography height distribution 1 Introduction

Figure 2 -

 2 Figure 2 -Experimental set-up

Figure 4 -

 4 Figure 4 -Polishing forces vs displacement

Figure 5 -

 5 Figure 5 -Hilbert's curves (first, second and third order curve)

Figure 6 -

 6 Figure 6 -Fourth order cornered Hilbert's curve

Figure 7 -

 7 Figure 7 -Polishing trajectories on a convex free form

Figure 8 -

 8 Figure 8 -Trochoidal curve parameters

Figure 9 -

 9 Figure 9 -Contact area between the tool and the part

Sq : Root-mean-square deviation of the surface. This is a dispersion parameter defined as the root mean square value of the surface departures within the sampling area.

Ssk : Skewness of topography height distribution. This is the measure of asymmetry of surface deviations about the mean plane.

Sku : Kurtosis of topography height distribution. This is a measure of the peakedness or sharpness of the surface height distribution.


Daniele Miorandi
email: daniele.miorandi@dei.unipd.it

Carlo Caimi
email: carlo.caimi@dei.unipd.it

Andrea Zanella
email: andrea.zanella¡@dei.unipd.it

Performance Characterization of a Bluetooth Piconet with Multi-Slot Packets

Keywords: Bluetooth, S.A.R., multislot packets, performance evaluation

In this paper we present a framework for performance evaluation of a Bluetooth piconet using multislot packets. In particular, under some classical assumptions, we develop a model of a Bluetooth network and derive the complete statistics of the one-hop delay, and other significant metrics such as the channel utilization parameter. Stability conditions are investigated and it is shown that the use of multi-slot packets enlarges the achievable rate region. Simulations results are then shown, which validate the proposed analysis.

I. INTRODUCTION

Originally born as a wireless replacement for cables connecting electronic devices, Bluetooth [1] has been gaining a lot of consideration and attention by the scientific community in the last few years [START_REF] Haartsen | The Bluetooth radio system[END_REF], [START_REF] Haartsen | Bluetooth: Vision, goals, and architecture[END_REF], [START_REF] Johansson | Bluetooth: an enabler for personal area networking[END_REF]. The development of this technology is now focused on the so-called Wireless Personal Area Networks (WPANs), which are foreseen as the major application for Bluetooth devices in the short and mid-term future. While the diffusion of Bluetooth devices is believed to experience a rapid growth in the next years, thanks to its expected low cost (down to ¢ USD, according to leading man- ufacturers), the success of such a technology will still be linked to its ability to track the demand for advanced applications. Indeed, performance improvement schemes have become an active research field, in order to let Bluetooth networks being able to support demanding services, like Internet, MP3 audio and low-quality video. The basic brick to build up a Bluetooth-based network is the so-called piconet, a cluster of nodes (not more than £ ) communicating with each-other by sharing a common FH channel. Access control to the radio channel is achieved by using a master-driven TDD scheme, based on a master-slave architecture. Piconets may communicate by sharing, on a time division basis, a device, called inter-piconet unit, which acts as gateway among the piconets it belongs to. Even if much attention has been devoted to performance evaluation of Bluetooth networks, most of the results have been obtained through numerical simulations. Indeed, the literature still lacks an in-depth analytical investigation of Bluetooth network performance. Not even the analysis of a single piconet with multi-slot packets has been completed, even if some considerable effort has been devoted in the last years [START_REF] Bruno | Bluetooth: architecture, protocols and scheduling algorithms[END_REF], [START_REF] Misic | On Bluetooth piconet traffic performance[END_REF]. In this paper, we aim at providing a mathematical framework which, under some simplifying but classical assumptions, allows us to evaluate the performance obtainable with the use of multi-slot packets. In particular, we provide the packetdelay statistics for one-hop transmissions. In this sense, our approach resembles that used in [START_REF] Misic | On Bluetooth piconet traffic performance[END_REF], from which it differs for some model assumptions, in particular on the role of the master and on the possibility of having different statistics for the packet length at different nodes. Furthermore, we provide a characterization of the channel utilization parameter and an in-depth investigation of the stability regions achievable under a given Segmentation And Reassemly (SAR) policy, showing that the use of multi-slot packets provides an enlargement of the achievable rate region. The paper is organized as follows: Section II deals with the characteristics of the Bluetooth communications profile and describes the system model which will be used for the analysis. Section III deals with the performance analysis of a Bluetooth piconet, in terms of single-hop delay, together with an investigation of the achievable capacity regions. Finally, Section IV presents some concluding remarks and open issues for future work.

II. BACKGROUND: THE BLUETOOTH TECHNOLOGY

Bluetooth operates in the ¤ ¦¥ § GHz ISM unlicensed band, providing a raw bit rate of ¨ Mb/s by using a binary Gaussian- shaped FSK modulation. In order to reduce interference with other devices operating in the ISM band, Bluetooth adopts a frequency hopping (FH) spread spectrum technique, spanning

©

RF carriers, ¨ -MHz wide each. In order to communicate, two up to eight Bluetooth units may connect in a small network, called piconet. In each piconet, a unit acts as master, controlling the channel access by means of a simple polling scheme. Time is divided into consecutive slots of ¤ ¢ s each, that are used for downlink (master-to-slave) and uplink (slave-to-master) transmissions, alternatively, in a time division duplex (TDD) fashion. Namely, each time-slot is associated to a hop in the hopping sequence, resulting in a nominal hop rate of ¨ hop/s. The master can transmit in even-numbered time slots, whereas odd-numbered slots are reserved for slaves' transmissions. The standard provides two types of service, Asynchronous ConnectionLess (ACL) and Synchronous Connection-Oriented (SCO). The latter provides a way of sending delay-sensitive services (tipically voice) over Bluetooth, and is based on a reservation scheme which estabilishes a virtual circuit between a slave and the master. The other type of link, ACL, provides packet-switching on PSfrag replacements shortened Hamming code or none) and packet length (¨and ¢ time slots), as depicted in Fig. 1. A resume of the EC F packet characteristics is reported in Tab.I.

¤£ ¦ ¤£ ¦ ¤£ ¦ ¤£ ¨ § ¤£ § £ ¨ § £ ¨ § ¤£ § ! ¤£ § ! ¢¡ ¤£ ¨ § ¢¡ ¤£ ¨ § ¢¡ ¤£ ¨ § £ ¨ § % £ ¨ § % £ ¨ § % $" ¨' E y z ¥ ¥ ¥ © ¥ ¥ ¥ ¥ ¥ ¥ # ¥ # ¥ # ¥ ¥ ¥ ¥ % )( Fig.
Different piconets are associated to independent FH channels. This allows more piconets to share the same physical space and spectrum without increasing excessively the mutual interference. Piconet may communicate by sharing a device on a time division basis, forming what is commonly referred to as a scatternet. Both a piconet and a scatternet consisting of G IH PF piconets are depicted in Fig. 2.

A. System Model

To carry on our analysis, we need some simplifying assumptions on the considered network. First of all, we limit our analysis to the simplest polling scheme, Pure Round Robin (PRR), also referred to as Limited-¨ polling. Although many efficient polling schemes have been proposed in the last few years [START_REF] Capone | Efficient polling schemes for Bluetooth picocells[END_REF], [START_REF] Kalia | Data scheduling and sar for Bluetooth mac[END_REF], at this time available devices implement a basic PRR scheme. This is essentially due to the necessity of keeping the complexity of the firmware as low as possible, in order to reduce the manufacturing costs and lower the power consumption. PRR does not require complex logic to be Fig. 2. Topologies of Bluetooth networks: piconet & scatternet embedded on the chip and, thus, it results the most attractive choice for low-cost and power-aware solutions. Furthermore, in the following, we will consider ACL links only and limit our analysis to the use of unprotected packets (Q SR UT , where T VH ¨¢ WC ¢F ¨C ). In fact, it has been shown [START_REF] Valenti | On the throughput of Bluetooth data transmissions[END_REF] that, in most operating conditions (namely for not too low signal-to-noise ratios) the use of Q SR UT packets results in higher goodput with respect to Q SG XT . We start by considering a piconet consisting of Y a`¨ nodes, Y cb © ; the network may, then, be represented by a set of ¤ dY interacting queues. Since the solution for problems of interacting queues is still far from coming, we assume that the arrival processes at the various queues are independent. To treat also slave-to-slave communications, we will employ the classical tool of statistical routing [START_REF] Levy | Polling systems: applications, modeling and optimization[END_REF], which enables us to get an approximate analysis of the network performance. In other words, the traffic from the master to a particular slave, say e , will be computed as the sum of the traffic generated in the whole piconet for that particular slave, and the various resulting flows will be considered independent. To get a more mathematically comprehensive framework, we need to introduce some preliminary notations. Let us enumerate units in a piconet from

to Y . Let f Sg C ¥ ¥ ¥ ¡ )C ¢Y be the B D master ID. For each h 5C $e ig C ¥ ¥ 8C Y ¡ , we use the suffix ¥ h 5C $e
to denote the link between node h and e . Note that, in case both h and e are slave units, the link is "virtual", since each packet exchange between two slaves has to be routed through the master, that will forward the packet to the recipient slave. The arrivals are modeled with a Poisson process with bulk arrivals and rate p rq s t (expressed in packets/slot). The probabilities of packets generated at node h to node e being one, three

B D B D B D
and five slots long, are u vq s t ¨ , u wq s t F and u wq s t ¢ , with

x Py B & D s )s u q s t H ¨ . We assume that no segmentation-and- reassembly (SAR) procedures take place when a slave-toslave communication passes through the master. A complete characterization of the piconet is thus given by:

B $ D H f C 5 EC ¡ (1) B $ D
where B D is the polynomial end-to-end traffic matrix, whose h 5C $e -th entry is defined as:

y B $ D B D ¦ q s t H Pp q s t u q s t ¥ (2)
y s )s B & D
The end-to-end traffic matrix can be associated to the effective traffic matrix B & D , which describes the actual traffic flowing between the master unit and each slave unit:

B & D B & D e f y q s t H q s t q s t ¥ (3)
y s s ¨d
Due to our assumptions of statistical routing and absence of SAR in slave-to-slave communications, we obtain:

h g i q s j kH x ml
x tl t fn fn p rq s t WC oh pH C ¥ ¥ ¥ )C ¢Y UC qe rH f s j 6s t H q p q s e rH dx { C ~}¥ ¥ ¥

q s B D H ¡ £¢ ¥¤ x m t u q s t B D p q s t C h pH C ¥ ¥ ¥ C Y UC H ẄC F C d d 6st B B & D D H ¡ ¤ ¢ x t q u q s t B D p q s t e rH ¦ C ¥ ¥ ¥ rC Y UC H ẄC ¢F ¨C q s t H h 5C $e H f C H C F C ¥ ¨¢ d
(5) There is, however, a more elegant way to pass directly from

B $ D B $ D
to . Let us define the matrix § as:

¨ ¨ ¥ ¥ ¥ ¨ C (6) ¥ ¥ ¥ . . . . . . . . .
where the f -th row is the only non-zero one, and as the all-

B D
zero matrix presenting a single one in position f C ¢f . Then, we may write:

B & D B & D B ! D B & D B ! D H § $# C § (7)
where is the identity matrix.

III. PERFORMANCE ANALYSIS B D

The delay on the link h ¢C e , & q s t , consists of two components, the access delay ' )( ¢ 0¤ 1 (i.e. the time it takes for a packet to get to the head of the queue and start the service) and the transmission delay ' 32 ¥4 ¢ 0¤ 1 . By using the corresponding LSTs (Laplace-Stieltjes transforms) we have:

B & D B & D B & D 65 Q q s t H ( ¢ ¥¤ 1 7 852 ¥4 ¢ 0¤ 1 C 7 85 (8)
B & D x B D ¦ DC ¢ ¥¤ 1 where 7 2 ¥45 ¢ ¥¤ 1 H s )s q s t f H ¡ ¢ ¥¤ 1 . @9 BA d
The access delay itself may be expressed as the sum of two components:

' ( ¢ ¥¤ 1 E' GF H' )I ¢ ¥¤ 1 C (9)
H where ' F is the time elapsed between the packet arrival and the first time the queue gets the token, whereas the second term takes into account the time spent for transmitting all the packets found waiting in queue. Passing to the corresponding LSTs, we obtain:

B & D B & D B & D 7 85 ( ¢ ¥¤ 1 P7 85 H F 7 85I ¢ ¥¤ 1 ¥ (10)
The first term may be thought as the residual life in a renewal process with renewal period equal to the cycle time. Thus, from the theory of random look [START_REF] Kleinrock | Queueing Systems[END_REF] we have for the pmf:

! X Y #B bV D Q UT B V D Ḧ c ed f Ug `h C (11) W `Y ia f pg
where is the probability distribution of the r.v. . Passing to the LSTs, we get:

! Xq 5 Y ia B & D B $ D 785F H c ed f g h (12)
The other term in (9) may be found by considering the equivalent G ¨ model of the queue, with an @r s er equivalent service time equal to the cycle time, thus getting, in terms of LSTs,

B ! ut v D B & D ¨ q s t 7 I 5 ¢ ¥¤ 1 H 3! q s t ! wq s t q Y Sa 5 B & D C (13)
where v t q s t is the equivalent load factor for the B h 5C $e D -th queue ¢ ¨s (see w III-A for more details).

f g

Now we need to find the LST of the cycle time . The cycle period may be expressed as the sum of the times spent for B D ¢ ¨s data exchange on the h 5C $e -th link, f yx ¢ 0¤ 1 , which, due to our assumptions, are assumed independent, and thus:

q 5 Y ia B & D B $ D H s %5 t ¥ (14) q s q s t Y i B & D c d ¢ 0¤ 1 h
According to the notation of [START_REF] Misic | On Bluetooth piconet traffic performance[END_REF] we set s 5 q s t H . Finally, considering that in case of no data packets available a one-slot long dummy packet (POLL/NULL) is sent, we find:

B $ D B t B D B ! ut D ¦D s %5 q s t H v q s t q s t ¨¨ v q s t d v t q s t q s t B F D e t v q s t q s t B ¢ D ¦ ¥ (15) d d
On the whole, we get:

B & D ¨ ! q Y Sa 5 B & D Q q s H c ed f Bg `h 65 t B ! ut v D ¨ q s t B D 3! ! q Y a B $ D q s t f ¥ (16) q s t q s t 5 s )s d
Equation ( 16) provides the complete statistics of the delay on the link

B h 5C $e D .
In particular, the average value, Q q s t H c ed & q s t h may be found to be:

! e Q 5 q s t B $ D c ed f G g h Q q s t H H d f g h ¤ c ed f G g h ¤ B ¨ ! q s t wq s t c ed f g h D B ¨¤ d q s t B F D d q s t B ¢ D ¦D C (17) f g
where the moments of may be found by deriving expression (14). Finally, the average packet delay may be computed as:

x q s t q s t Q q s t Q H x ¥ ( 18
)
q s t q s t

A. Stability Conditions v

Generally speaking, the load factor of a queue is defined as [START_REF] Kleinrock | Queueing Systems[END_REF]:

v c d h c ed h H C (19)
where is the service time and the arrival rate. A polling system employing PRR is stable if and only if the following conditions are both verified [START_REF] Levy | Polling systems: applications, modeling and optimization[END_REF]:

v H v q s t ẄC (20) q s t t v q s t ËC h ¢C e H C ¥ ¥ )C ¢Y ¥ ¥ (21)
where the first condition applies to the system as a whole, whereas the second ensures that also every single queue is stable. According to the notation previously introduced, each load factor of the h -th queue may be described by: v q s t H

wq s t c d ' 2 ¥4 ¢ 0¤ 1 v h t H q s t d ¤ q s t B F D q s t B D h
. The equivalent ¨¢ d d load factor, q s t may be calculated by considering the equivalent G @r s er system, which presents a service time equal to the

f g v t c d f g h service time
. Thus, q s t H P wq s t . Substituting, after a few algebra we get that condition (21) implies (20) and is thus not only necessary but also sufficient to get a stable network.

In Fig. 3 we reported the results for the case when only Q R UT packets are used on both forward and reverse links for a piconet with Y H ¨slave. The achievable rate region for Y H ¨, is shown in Fig. 4. Note that, as expected, due to the higher efficiency (in terms of payload/packet length ratio), enabling the use of multi-slot packets effectively enlarges the achievable rate region. The same reasoning applies to the general case of a piconet with Y slaves, where the achievable rate region may be depicted as a polyhedron in a ¤ dY -dimensional space.

B. Channel Utilization

In wireless systems, bandwidth is a scarce resource and, hence, it is of vital importance to fully exploit the available bandwidth. The time division duplex (TDD) architecture of Bluetooth systems makes impossible to fulfil this requirement in the case of strongly asymmetric traffic. (An example may be a multicasting in a conference room, where downlink traffic only is present). Hence, a metric of great interest is the socalled channel utilization parameter, defined as the average percentage of slots occupied by data packets. The channel utilization parameter, which will be denoted by , may be obtained by the ratio between the total number of slots used to send data during a service cycle and the cycle duration expressed in slots. Hence, using average values we get:

H ced f Ug `h 6 q s t t v q s t c d ' 2 ¥4 ¢ 0¤ 1 h H q s t q s t c ed ' 2 ¥4 ¢ 0¤ 1 h ¥ (22)

C. Numerical Results

In this section we report some results obtained through numerical simulations. To validate our model, we implemented a simulator using OPNET; we considered a scenario of a full piconet (Y H © ), with download traffic only and various SAR policies. The results, in terms of average packet delay, are plotted in Fig. 5 for

d B & D H C H ẄC F C ¢ .
In Fig. 6, we reported the impact of the number of slaves on the packet delay for various Y , in a balanced scenario with

d q s t B & D H
for any

B h 5C $e D .
In case of slave-to-slave communications, the end-to-end packet delay clearly depends on the order the master polls the slaves. To avoid such a dependency (which results in fairness loss), we should consider a PRR in which the polling order is randomized at each cycle; thus, an approximate expression of the packet delay for a B h 5C $e D communication may be given by: To show how the assumption of independent flows affects the results, we simulated a piconet with ¤ slaves communicating each other: theoretical and simulation results are shown in Fig. 7. It may be noted that the assumption of independent flows, although providing good results at low traffic load, leads to substantial mismatch with the simulation results as the system gets close to the stability limit. Finally, we investigated the impact of the SAR policy employed: namely, we analyzed a piconet with Y H F slaves; two of them communicate with the master at a bit rate of £ Kb/s, using Q R ¨packets only (which can be thought as a model for voice over ACL), whereas the third slave is downloading from the master at a rate of F Kb/s. We varied the d B D for the last connection, and plotted the channel utilization parameter and the average packet delay on the voice links, in Fig. 8 and Fig. 9 respectively. The results are worth some comments: the use of multi-slot packets, indeed, while enlarging the capacity region, achieves lower efficiency in terms of bandwidth utilization. This result is, in practice, due to the higher efficiency of multi-slot packets, and, thus, the terms in (22) decreases when longer packets are used. Furthermore, longer packets may result in detrimental impact on links carrying delay-sensitive flows. In a QoS-oriented scenario, it is clear that the choice of using multi-slot packets should be somehow negotiated at the master side, taking into account the possibly negative effects on link performances.

Q iq s t H tQ iq s j `Q j 6s t ¥ (

IV. CONCLUSION

In this paper we presented a mathematical framework, based on queueing theory tools, for performance evaluation in a Bluetooth piconet using multi-slot packets. We discussed stability conditions and showed that the use of multi-slot packets, due to their higher efficiency, effectively enlarges the boundaries of the achievable capacity region. We showed how the channel utilization parameter, a significant metric in wireless networks performance, may be calculated, and discussed the tradeoffs involved in the choice of a given SAR policy. Three subjects seem to be of great interest for future work. The first is the study of how channel failures impact on piconet performances, and their integration into a queueingtheoretic framework. The second is the effective modeling of more realistic SAR policies, in which the packet length is chosen in function of the buffer length, and, as a consequence, the analysis of the packet delay at L2CAP level. The last interesting issue would be the extension of such a framework to accomodate a scatternet structure, where other problems (the modeling of the gateways' behavior and inter-piconet interference) arise.

π k,3 (3)
π k,3 (5)

Fig. 3 .Fig. 4 .

 34 Fig. 3. Stability region, ¢¡ 0 , in terms of offered traffic (£ ¥¤ §¦ packets only)

Fig. 5 .Fig. 6 .

 56 Fig. 5. Average packet delay versus offered traffic, ©¡ U1

Fig. 7 .

 7 Fig. 7. Average packet delay for a slave-to-slave communication, ¡ 2

Fig. 8 . 7 0

 87 Fig. 8. Channel utilization parameteras a function of 4 and 7

Fig. 9 .

 9 Fig. 9. Average packet delay for the delay-sensitive application as a function of 4 and 7

This work was supported by MIUR within the framework of the PRIMO project FIRB RBNE018RFY


Ivana Maric
email: ivanam@winlab.rutgers.edu

Roy Yates
email: ryates@winlab.rutgers.edu

Performance of Repetition Codes and Punctured Codes for Accumulative Broadcast

1 Problem Formulation.

In the problem of minimum-energy broadcasting in a wireless network, the objective is to broadcast data reliably to all network nodes at a fixed rate with minimum transmitted power. In [START_REF] Wieselthier | On the construction of energy-efficient broadcast and multicast trees in wireless networks[END_REF], this problem was formulated as a minimum-cost broadcast tree problem and the well-known heuristic for constructing energy-efficient broadcast trees, the Broadcast Incremental Protocol (BIP), was proposed. In this paper, we look to increase the energy efficiency by employing an accumulative broadcast strategy [START_REF] Maric | Efficient multihop broadcast for wideband systems[END_REF] that allows nodes to collect the energy of unreliably received signals. As a message is forwarded through the network, a node will have multiple opportunities to reliably receive the message by collecting energy during each retransmission. While we allow nodes to collect unreliably received signals, we impose a reliable forwarding constraint that each node can forward a message only after reliably decoding that message. The constraint of reliable forwarding imposes an ordering on the network nodes. The order in which nodes become reliable is referred to as a reliability schedule.

Under these assumptions, we formulate the minimum-energy accumulative broadcast problem for two coding schemes: punctured codes with general coding and simple repetition codes. Punctured codes are generated as described in [START_REF] Caire | The throughput of hybrid-ARQ protocols for the gaussian collision channels[END_REF] and are used by different nodes to broadcast a message through the network. In particular, for a network of nodes, a channel code ¡ with ¢ ¤£ ¦¥ codewords of length § ©¨for some ¨ is generated and assumed known at all the nodes. Codewords are divided into ¨subblocks of length § , each transmitted in one slot. We let ¡ for ¤ ¨denote the punctured code with codewords of length § ! formed from the first subblocks of each codeword in ¡ . The " th relaying node transmits the " th subblock. An unreliable node, after receiving signals, attempts to decode ¡ for each # , until the decoding is successful. For repetition coding, only a code ¡ %$ is generated. A codeword of length § transmitted by the source is retransmitted by each relaying node. An unreliable node collects signals received from different nodes until it can reliably decode ¡ $ .

In [START_REF] Maric | Efficient multihop broadcast for wideband systems[END_REF], accumulative broadcast was employed using repetition coding. The network was assumed to be operating in the low-SNR regime where simple repetition coding is optimal. In this work, we examine the benefit of punctured codes with general coding for accumulative broadcast.

Approach.

With each transmitting node & we associate an AWGN channel of bandwidth ' such that each receiving node is characterized by a frequency non-selective link gain ( 0) . We further assume that each node is assigned to transmit in an orthogonal channel thus causing no interference to other transmissions. To formulate the accumulative broadcast problem, we first determine the maximum achievable rate at every node for a given set of transmit powers for both coding schemes. Given the achievable rate at the nodes, we then present a solution to the accumulative broadcast problem employing two subproblems. The first step is finding the best reliability schedule and the second is determining the optimum power levels for that schedule. The solution will specify the nodes that should transmit and their transmission power levels. A reliability schedule can be represented by a matrix 1 where 2 43 65 7 if node 8 becomes reliable after node " 9 otherwise

(1) Each 2 3 @5 is an indicator that a node 8 collects energy from a possible transmission by node " . For repeti- tion codes, the solution to the second subproblem can be found by linear programming as given in [START_REF] Maric | Efficient multihop broadcast for wideband systems[END_REF]. In the case of punctured codes, for a given schedule 1 , the subproblem can be defined as a convex optimization problem in terms of the vector A of transmitted powers B 4C 1 ED F HG PI RQ TS VU WA [START_REF] Maric | Efficient multihop broadcast for wideband systems[END_REF] subject to ¢ YX `5 ba $ 4c ed ¤f C hg ( 3 @5 2 3 @5 bi p5 rq ' D s ¢ ¤'

A t vu W

where s is a required data rate in bits/s. For the simpler case of repetition coding, the problem of finding the best schedule was shown in [START_REF] Maric | Efficient multihop broadcast for wideband systems[END_REF] to be NPcomplete. To find a good schedule, we employ a simple heuristic algorithm presented in [START_REF] Maric | Efficient multihop broadcast for wideband systems[END_REF] for repetition coding. We modify the algorithm to be used with punctured coding and evaluate the algorithm performance for both coding schemes. The algorithm starts with a partial reliability schedule that contains only the source. In each step, a reliable node that maximizes the fill rate of the unreliable set is chosen for the next transmission. The node transmits with enough power to make one more node reliable and that node is appended to the schedule. Once the schedule is determined, the optimization routine will find the optimum power levels for that schedule.

In the above algorithm, a reliable node that is chosen to transmit several times, will in fact consolidate its multiple transmissions into a single transmission. The actual power level is found by the optimization routine. As argued in [START_REF] Maric | Efficient multihop broadcast for wideband systems[END_REF], a node using a repetition code cannot gain from successive retransmissions of the same codeword. In the power-limited regime, this property holds for punctured codes as well.

However, when the system is bandlimited and the nodes are operating in higher SNR, the efficient bandwidth utilization becomes important. The above strategy will not, in general, utilize the available network bandwidth if the orthogonal channels are assigned to all the users a priori. In this case, bandwidth will be wasted on the users not chosen by the heuristics to relay the data.

To increase the efficiency of bandwidth utilization in the above scheme, we let the heuristic algorithm allocate the available bandwidth in addition to deciding on the schedule. The bandwidth allocation follows directly when the consecutive transmissions at the nodes are allowed. Therefore, there is no need for further modification of the heuristic. In particular, since the heuristic makes one unreliable node reliable in each step, at most xw transmissions are needed to broadcast a message. Then the available system bandwidth can be divided into yw channels and a reliable node that is chosen as the best filling node v times, will be allocated channels to transmit times rather then just once. The power levels determined by the heuristic are the actual power levels to be used for broadcasting; no additional optimization is performed. In such a scenario, punctured codes where a node would transmit a new subblock in each new transmission become crucial. If a node would use repetition coding, resending the same codeword in each of channels would not result in any benefit. To benefit from additional bandwidth, a new repetition code would have to be constructed with codewords of length § $ 0 T § . Figure 1 shows the algorithm performance for both coding schemes and for different broadcast data rates. For punctured coding, we evaluated the performance of both strategies described above. The performance was evaluated in a network of 9 nodes. The transmit- ted power was attenuated as s ¦ for propagation exponent ¢ . Results demonstrate the benefit of using the punctured codes over the repetition coding in the high-SNR regime due to the higher achievable rates. The gain diminishes in the low-SNR regime, as expected.

Figure 1 :

 1 Figure 1: Power used for broadcasting.