Nader Salman

Mariette Yvinec

Surface Reconstruction from Multi-View Stereo *

We describe an original method to reconstruct a 3D scene from a sequence of images. Our approach uses both the dense 3D point cloud extracted by multi-view stereovision and the calibrated images. It combines depth-maps construction in the image planes with surface reconstruction through restricted Delaunay triangulation. The method may handle very large scale outdoor scenes. Its accuracy has been tested on numerous scenes including the dense multi-view benchmark proposed by Strecha et al. Our results compare favorably with the current state of the art.

Introduction

Motivations. Various applications in Computer Vision, Computer Graphics and Computational Geometry require a surface reconstruction from a 3D point cloud extracted by stereovision from a sequence of overlapping images. These applications range from preservation of historical heritage to e-commerce through computer animation, movie production and virtual reality walkthroughs.

Early work on reconstruction has been focused on data acquired through laser devices, with characteristics that the obtained 3D point cloud is dense and well distributed [START_REF] Ohtake | Multi-level partition of unity implicits[END_REF][START_REF] Kazhdan | Poisson Surface Reconstruction[END_REF][START_REF] Hornung | Robust reconstruction of watertight 3D models from non-uniformly sampled point clouds without normal information[END_REF]. Although these reconstruction methods have been reported as succesful, the nature of the laser scanners greatly limit their usefulness for large-scale outdoor reconstructions.

The recent advances in multi-view stereovision provide an exciting alternative for outdoor scenes reconstruction. However, the extracted 3D point clouds are entangled with redundancies, a large number of outliers and noise. Fortunately, on top of these point clouds, the additional information provided by the calibrated images can be exploited to help surface reconstruction.

In this work, our goal is to recover a meshed model from a multi-view image sequence. We assume that the images have been processed by a multi-view stereovision algorithm and start from the calibrated images and a set of tracks. Each track is a 3D point associated to a list of images where the point is visible. The model sought after is either a simplicial surface mesh or a 3D mesh of the objects in the scene.

Related Work. Over the past three decades there have been significant efforts in surface reconstruction from images, typically targeting urban environments or archaeological sites. The requirements for the ability to handle large-scale scenes discards most of the multi-view stereo reconstruction algorithms including the algorithms listed in the Middlebury challenge [START_REF] Seitz | A comparison and evaluation of multi-view stereo reconstruction algorithms[END_REF]. The methods which have proved to be more adapted to large-scale outdoor scenes are the ones that compute and merge depth-maps [START_REF] Strecha | Wide-baseline stereo from multiple views: a probabilistic account[END_REF][START_REF] Strecha | Combined depth and outlier estimation in multi-view stereo[END_REF][START_REF] Goesele | Multi-view stereo for community photo collections[END_REF][START_REF] Pollefeys | Detailed real-time urban 3d reconstruction from video[END_REF][START_REF] Tylecek | Depth map fusion with camera position refinement[END_REF]. However, in multiple situations, the reconstructed 3D models lack of accuracy or completeness due to the difficulty to take visibility into account consistently. Recently, two different accurate reconstruction algorithms have been proposed in [START_REF] Furukawa | Accurate, dense, and robust multiview stereopsis[END_REF][START_REF] Vu | Towards high-resolution large-scale multi-view stereo[END_REF]. We demonstrate the efficiency of our reconstruction results relying on the publicly available quantitative challenge from the review of Strecha et al. [START_REF] Strecha | On benchmarking camera calibration and multi-view stereo for high resolution imagery[END_REF] currently led by [START_REF] Furukawa | Accurate, dense, and robust multiview stereopsis[END_REF][START_REF] Vu | Towards high-resolution large-scale multi-view stereo[END_REF].

Contributions. Our reconstruction method is close to [START_REF] Hilton | Scene modelling from sparse 3d data[END_REF] and to the imageconsistent triangulation concept proposed by Morris and Kanade [START_REF] Morris | Image-consistent surface triangulation[END_REF]. It consists in a pipeline that handles large-scale scenes while providing control over the density of the output mesh. A triangular depth-map is built in each image plane, respecting the main contours of the image. The triangles of all the depth-maps are then lifted in 3D, forming a 3D triangle soup. The similarity of the triangle soup with the surface of the scene is further enforced by combining both visibility and photo-consistency constraints. Lastly, a surface mesh is generated from the triangle soup using Delaunay refinement methods and the concept of restricted Delaunay triangulation. The output mesh can be refined until it meets some user-given size and quality criteria for the mesh facets. A preliminary version of this work appeared as a video in the ACM Symposium on Computational Geometry 2009 [START_REF] Salman | High resolution surface reconstruction from overlapping multiple-views[END_REF].

Basic Notions

In this section we define the concepts borrowed from computational geometry that are required for our method. Let P = {p 0 , . . . , p n } be a set of points in R d that we call sites. The Voronoi cell V(p i ), associated to a site p i , is the region of points that are closer to p i than to all other sites in P :

V(p i ) = {p ∈ R d : ∀j = i, p -p i ≤ p -p j } The Voronoi diagram V(P) of P is a cell decomposition of R d induced by the Voronoi cells V(p i ).
The Delaunay complex D(P) of P is the dual of the Voronoi diagram meaning the following. For each subset I ⊂ P, the convex hull conv(I) is a cell of D(P) iff the Voronoi cells of points in I have a non empty intersection. When the set P is in general position, i.e. includes no subset of d + 2 cospherical points, any cell in the Delaunay complex is a simplex. This Delaunay complex is then a triangulation, called the Delaunay triangulation. It decomposes the convex hull of P into d-dimensional simplices. Let Ω be a subset of R d , we call Delaunay triangulation of P restricted to Ω and we note D Ω (P), the sub-complex of D(P), that consists of the faces of D(P) whose dual Voronoi faces intersect Ω. This concept has been particularly fruitful in the field of surface reconstruction, where d = 3 and P is a sampling of a surface S. Indeed, it has been proven that under some assumptions, and specially if P is a "sufficiently dense" sample of S, D S (P) is homeomorph to the surface S and is a good approximation of S in the Hausdorff sense [START_REF] Boissonnat | Provably good sampling and meshing of surfaces[END_REF]. Fig. 1 illustrates the notion of restricted Delaunay triangulation.

The Delaunay refinement surface meshing algorithm builds incrementally a sampling P on the surface S whose restricted triangulation D S (P) is a good approximation of the surface S. At each iteration, the algorithm inserts a new point of S into P and maintains the 3D Delaunay triangulation D(P) and its restriction D S (P). Insertion of new vertices is guided by criteria on facets of D S (P): minimum angle α; maximum edge length l; maximum distance d between a facet an the surface. The algorithm [START_REF] Boissonnat | Provably good sampling and meshing of surfaces[END_REF] has the notable feature that the surface has to be known only through an oracle that, given a line segment, detects whether the segment intersects the surface and, if so, returns the intersection points.

At last, we also use the notion of 2D constrained Delaunay triangulation based on a notion of visibility [START_REF] De Berg | Computational Geometry -Algorithms and Aplications (3rd)[END_REF]. Let G be the set of constraints forming a straight-line planar graph. Two points p and q are said to be visible from each other if the interior of segment pq does not meet any segment of G. The triangulation T in R 2 is a constrained Delaunay triangulation of G, if each edge of T is either an edge of G or a constrained Delaunay edge. A constrained Delaunay edge is an edge e such that there exist a circle through the endpoints of e that encloses no vertices of T visible from an interior point of e.

The Reconstruction Algorithm

The algorithm takes as input a sequence of calibrated images and a set of tracks provided by multi-view stereo. The algorithm consists of three steps: 1) merging, filtering and smoothing the tracks, 2) building a triangle soup, and 3) computing from the triangle soup a mesh modeling the scene. The different steps of our algorithm are illustrated in Figure 2.

The following sections describe the three steps of the algorithm in more detail.

Merging, Filtering and Smoothing

Each input track stores its 3D point location as well as the list of camera locations from which it was observed during acquisition. In the following, we call line-ofsight the segment from a camera location to the 3D position of a track seen by this camera. Despite the robust matching process used by the multi-view stereo algorithm, the extracted tracks require some preprocessing including merging, filtering and smoothing.

Merging. The first preprocessing step in our method consists in merging tracks whose positions are too close with respect to some threshold ξ 1 . When two tracks are merged in a single one their list of cameras is updated to include the union of the cameras of the two merged tracks.

Filtering. As tracks are coming from characteristic points detected in the images, their 3D locations should be densely spread over the surface of the scene objects. Thus, tracks which are rather isolated are likely to be outliers. Another criterion used to further filter out outliers, is based upon the angle between lines-of-sight. When a 3D point location is computed from lines-of-sight forming small angles, the intersection computation is imprecise and the 3D point is likely to be noisy. For these reasons we use two criteria to detect outliers in the set of tracks: The distance to neighbors and the cone angle.

-Distance to neighbors. We compute for each track with 3D position p i the average Euclidean distance d k1 (p i ) from p i to its k 1 -nearest neighbors and we remove a small percentage ξ 2 of tracks with largest value.

-Cone angle filtering. We compute for each track with 3D position p i the aperture angle of the smallest cone with apex at p i containing all cameras C i that observe point p i . Tracks with small cone angles ξ 3 are discarded.

Smoothing. The final preprocessing step smooths the remaining tracks using a smoothing algorithm based upon jet-fitting and re-projection [START_REF] Cazals | Estimating differential quantities using polynomial fitting of osculating jets[END_REF]. For each track, we compute a low degree polynomial surface (typically a quadric) that approximates its k 2 -nearest neighbors. We then project the track onto the computed surface. In all our experiments we used ξ 1 = 0.001β, where β is the half diagonal of the bounding box of the point cloud, ξ 2 is 0.06%, ξ 3 = 0.08 radian, k 1 = 150 and k 2 = 85. .

Triangle Soup Extraction

The next step in our method combines the preprocessed tracks and the input images to build in each image plane a triangular depth-map that comply with the image discontinuities. The triangles of each depth-map are then lifted into 3D space forming a triangle soup which will require further filtering to minimize violations of visibility and photo-consistency constraints.

Depth-Maps Construction Since contours in the images are natural indicators of surface discontinuities, it is expedient to include contour information in the depth-maps construction process. A simple yet powerful method for contour detection is to perform a contrast analysis into the input images using gradientbased techniques.

In each image, we then compute an approximation of the detected contours as a set of non-intersecting polygonal lines with vertices on the projection of the tracks. For this we consider in each image the projection of the tracks located in this image. We call contour track, or ctrack, a track whose projection on the image is close to some detected contour. We call a non-contour track, or nctrack, any other track. We consider the complete graph over all ctracks of an image and select out of this graph, the edges which lay over detected contours. The selection is performed by a simple weighting scheme using [START_REF] Needleman | A general method applicable to the search for similarities in the amino acid sequence of two proteins[END_REF]. Inherently, whenever there is n ctracks aligned on an image contour, we select the n(n-1) 2 edges joining these tracks. Albeit, we wish to keep only the (n-1) edges between consecutive ctracks on the contours. For these reasons we use a length criteria to further select a subset of non-overlapping edges fashioning the polygonal approximation of the contour.

Edges in the polygonal contour approximation are used as input segments to a 2D constrained Delaunay triangulation with all projected tracks, ctracks and nctracks, as vertices. The output is a triangular depth-map per image. The triangles of this depth-map are then lifted in 3D space using the 3D coordinates computed by the multi-view stereo algorithm. However, lifted depth-maps from consecutive images partially overlap one another and the triangle soup includes redundancies. When two triangles share the same vertices, only one is kept.

Triangle Soup Filtering The vast majority -but not all -triangles of the soup lie on the actual surface of the scene. In the sequel, we note ∆ = {T 0 , . . . , T n } the 3D triangle soup. We wish to filter ∆ to remove erroneous triangles.

(1) The visibility constraint states that the line-of-sight from a camera position to the 3D position of a track seen by this camera belongs to the empty space, i.e., it does not intersect any object in the scene. Therefore a triangle intersected by some line-of-sight should be removed from ∆. However, this rule has to be slightly softened to take into account the smoothing step (Section 3.1) where the tracks 3D positions have been slightly changed. More specifically, each triangle T i in ∆ gets a weight w i equal to the number of lines-of-sight intersecting T i . We then discard from ∆ any triangle with a weight w i greater than a threshold ξ 4 .

(2) We also filter out any triangle whose vertices, at least one of them, are only seen by grazing lines-of-sight. In practice, an angle greater than 80 degrees between the line-of-sight and the triangles normal is used in all our experiments to characterise a grazing line-of-sight.

(3) Depending on the density of the preprocessed tracks, the triangle soup can contain "big" triangles, i.e. triangles whose circumradii are big compared to the scale of the scene. We use shape and photo-consistency constraints to filter big triangles.

A triangle is said to be anamorphic if it has a too big radius-edge ratio,where the radius-edge ratio of a triangle is the ratio between the radius of its circumcircle and the length of its shortest edge. Anamorphic big triangles are likely to lie in free space and should be discarded.Big triangles with regular shapes are filtered using photo-consistency criteria: A 3D triangle T i in ∆ is photoconsistent, if its projections into all images where T i vertices are visible, correspond to image regions with the same "texture". To decide on photo-consistency, two common criteria are Sum of the Squared Difference (SSD) and Normalsed Cross-Correlation (NCC) between pixels inside the projected triangle in each image. In our experiments we use NCC because it is less sensitive to illumination change between the views. We only use images where the angle between the normal of the 3D triangle and the line-of-sight through the center of the image is small. This scheme gives head-on view more importance than oblique views.

Reconstruction

For the final step, we use the Delaunay refinement surface mesh generation algorithm [START_REF] Boissonnat | Provably good sampling and meshing of surfaces[END_REF] described in Section 2. Recall that this algorithm needs to know the surface to be meshed only through an oracle that, given a line segment, detects whether the segment intersects the surface and, if so, returns the intersection points. We implemented the oracle required by the meshing algorithm using the triangles of ∆ as an approximation of the surfaces. Thus, the oracle will test and compute the intersections with ∆ to answer to the algorithm queries.

Implementation and Results

The presented algorithm was implemented in C++, using both CImg and Cgal libraries.

The Cgal library [20] defines all the needed geometric primitives and provides performant algorithms to compute Delaunay triangulations in both 2D and 3D [START_REF] Boissonnat | Triangulations in cgal (extended abstract)[END_REF]. It provides all the elementary operations needed in the different steps of our algorithm: vertex insertion, vertex move, nearest neighbour query, various traversal queries and point set processing [START_REF] Alliez | Point set processing[END_REF]. Moreover, the Cgal library provides access to the AABB tree and the general triangulation data structures (C2T3) used respectively to store the triangle soup and the surface mesh. More importantly it provides us the Delaunay refinement surface meshing algorithm that we use in the last step of our algorithm.

The CImg library (http://cimg.sourceforge.net) is a toolkit for image processing that defines simple classes and methods to manipulate generic images. In our code we use it for the contour detection, the constraint retrieval and the photoconsistency filtering step.

In our experiments, we used for the point cloud preprocessing step the parameters (ξ 1 , ξ 2 , ξ 3 , k 1 , k 2 ) values as listed at the end of Section 3.1. Moreover, the visibility constraint threshold ξ 4 , defined in Section 3.2, is set at 5 rays. Leaving aside the time required by the multi-view stereo processing (image calibration and track extraction), in our experiments the runtime of our reconstruction algorithm ranges from 9 minutes for 200 000 tracks on 8 images to 35 minutes for 700 000 tracks on 25 images on an Intel R Quad Xeon 3.0GHz PC.

Strecha et al. [START_REF] Strecha | On benchmarking camera calibration and multi-view stereo for high resolution imagery[END_REF] provide quantitative evaluations for six outdoor scene datasets. The evaluation of the reconstructed models is quantified through the cumulative error distribution, showing, for each deviation σ, the percentage of the scene recovered within an error less than σ. The deviation is estimated with respect to the ground truth model acquired with a LIDAR system. We have tested our approach on the fountain-p11, entry-p10, castle-p19 and Herz-Jesu-p25 particularly challenging datasets. Focusing on the fountain-p11 dataset, Fig. 3 shows, two of the images, the extracted triangle soup, our reconstruction Fig. 3: Top-left: 2 images of fountain-p11 and the extracted triangle soup. Bottom: our reconstruction (500 000 triangles). Top-right: the cumulative error distribution (SAL for our work) compared with VU [START_REF] Vu | Towards high-resolution large-scale multi-view stereo[END_REF], FUR [START_REF] Furukawa | Accurate, dense, and robust multiview stereopsis[END_REF], ST4 [START_REF] Strecha | Wide-baseline stereo from multiple views: a probabilistic account[END_REF], ST6 [START_REF] Strecha | Combined depth and outlier estimation in multi-view stereo[END_REF], ZAH [START_REF] Zaharescu | Transformesh: a topology-adaptive meshbased approach to surface evolution[END_REF] and TYL [START_REF] Tylecek | Depth map fusion with camera position refinement[END_REF]. and the cumulative error distribution compared with the distributions for other reconstructed methods. The stereovision cloud has 392 000 tracks from which 35 percent were eliminated at the preprocessing step. Our algorithm has succesfully reconstructed various surface features such as regions of high curvature and shallow details while maintaining a small number of triangles. The comparison with other methods [START_REF] Strecha | Wide-baseline stereo from multiple views: a probabilistic account[END_REF][START_REF] Strecha | Combined depth and outlier estimation in multi-view stereo[END_REF][START_REF] Tylecek | Depth map fusion with camera position refinement[END_REF][START_REF] Furukawa | Accurate, dense, and robust multiview stereopsis[END_REF][START_REF] Vu | Towards high-resolution large-scale multi-view stereo[END_REF][START_REF] Zaharescu | Transformesh: a topology-adaptive meshbased approach to surface evolution[END_REF] shows the versatility of our method as it generates small meshes that are more accurate and complete than most of the state-of-art while being visually acceptable. Fig. 5 shows our reconstruction results for the entry-p10 and the Herz-Jesu-p25 datasets. For extended results we refer the reader to the challenge website [START_REF] Strecha | On benchmarking camera calibration and multi-view stereo for high resolution imagery[END_REF].

To show the ability of our algorithm to cope with much bigger outdoor scenes and its ability to produce meshes that take into account the user budget for the size of the output mesh, we have chosen to test our method on the Aiguille du Midi dataset ( c B.Valet/IMAGINE). It includes 51 images, the extracted cloud has 6 700 000 points with lots of outliers. At the preprocessing step, 80 percent of the points were eliminated. The Delaunay refinement surface meshing is tuned through three parameters: the angular bound α controls the shape of the mesh facets, the distance d and the size parameter l govern respectively the approximation accuracy and the size of mesh elements. The reconstructions shown in Fig. 4 are obtained with α equals 20 degrees and d, l respectively set as (0.01, 0.035) and (0.002, 0.01) in unit of the bounding box half diagonal. We have tuned parameters d and l to adapt the mesh to a targeted size budget. This enabled us to reconstruct from a single extracted triangle soup output meshes of various resolutions (270 000 triangles and 1 000 000 triangles respectively in Fig. 4). Note that details such as antenas and bridges are recovered even in the coarsest model.

Conclusion

In this paper, we have proposed a novel 3D mesh reconstruction algorithm combining the advantages of stereovision with the power of Delaunay refinement surface meshing. Visual and quantitative assessments applied on various largescale datasets indicate the good performance of our algorithm. As for ongoing work, we want to explore the possibility to automatically pre-compute the thresholds such as (ξ 1 , ξ 2 , ξ 3 , ξ 4 ) from the images and incorporate in the reconstruction process a scale dependent sharp edges detection and recovery procedure to build geometrically simplified models.

Fig. 1 :

 1 Fig. 1: (a) the Voronoi diagram of a set of 2D points; (b) its dual Delaunay triangulation. (c) The Delaunay triangulation restricted to the blue planar closed curve is plotted in black. (d) The Delaunay triangulation restricted to the yellow region is composed of triangles whose circumcenters are inside the region.

Fig. 2 :

 2 Fig. 2: Reconstruction pipeline overview. Both images and camera projection matrices are used by the stereo vision algorithm to extract a 3D point cloud. (a) We will first preprocess the 3D point cloud. (b) Using the preprocessed 3D points and the camera projection matrices we extract a triangle soup that minimize visibility and photo-consistency violations. (c) Finally, we use the triangle soup as a surface approximation and build the output 3D model. Note that the triangles lying on the table were voluntary removed for readability.

Fig. 4 :

 4 Fig. 4: On the left: two images of the Aiguille du midi dataset ( c B.Vallet/IMAGINE); below: our low resolution reconstruction (270 000 triangles). On the right: our high resolution reconstruction (1 000 000 triangles). Note how most details pointed by yellow arrows are recovered in both resolutions.

Fig. 5 :

 5 Fig. 5: Top to bottom: 2 images of entry-p10 and 2 images of Herz-Jesu-p25; our reconstruction of entry-p10 (500 000 triangles); our reconstruction of Herz-Jesu-p25 (1 200 000 triangles).

Acknowledgments

We wish to thank Renaud Keriven and Jean-Philippe Pons for their point cloud extraction software and the Aiguille du Midi dataset, Laurent Saboret for his precious collaboration and Christoph Strecha for his challenge and his kind help.

* Work partially supported by the ANR (Agence Nationale de la Recherche) under the "Gyroviz" project (No ANR-07-AM-013) http://www.gyroviz.org


Simon Duquennoy
email: simon.duquennoy@lifl.fr

Gilles Grimaud
email: gilles.grimaud@lifl.fr

Jean-Jacques Vandewalle
email: jean-jacques.vandewalle@gemalto.com

Consistency and scalability in event notification for embedded Web applications

A new way to interact with small devices consists in embedding tiny Web servers, allowing the devices to serve fully-fledged Web applications. When the device needs to keep its users up-to-date of its internal state, the Web application has to use an event publication solution. Several works have recently been conducted in order to evaluate the trade-offs of various Web-based event notification solutions. In this paper, we propose to evaluate the feasibility of event notification in embedded Web applications. We conduct a large set of experiments in order to compare various push and pull based approaches for embedded systems. We show that a push-based approach can be very efficient in most situations, both in terms of client consistency and of scalability.

Introduction

A new way to implement embedded systems software consists in embedding Web servers in devices. Such servers can be used in sensors, home automation or routers, making these devices accessible from any computer, PDA or smart phone. Furthermore, Web application development is well-known and widespread. The global interconnection of devices based on Web technologies is called the Web of Things [START_REF] Stirbu | Towards a restful plug and play experience in the web of things[END_REF][START_REF] Guinard | Towards physical mashups in the web of things[END_REF][START_REF] Guinard | Towards the web of things: Web mashups for embedded devices[END_REF][START_REF] Duquennoy | The web of things: interconnecting devices with high usability and performance[END_REF].

Web technologies are based on a request/response model. HTTP allows clients to retrieve resources from servers, but disallows servers to push data to the clients. However, there are many use cases where servers would like to notify clients for event, e.g., auction Web site, stock ticker, news portal, forums, chat-rooms, etc. Usually, such behavior is implemented in AJAX applications by polling the server at a given interval. A new model named Comet [START_REF] Russell | Comet: Low latency data for the browser[END_REF] allows servers to push data over HTTP. Works have been conducted in order to evaluate the best strategies for Web-based event-notification [START_REF] Mesbah | A comparison of push and pull techniques for ajax[END_REF][START_REF] Bozdag | Performance testing of data delivery techniques for ajax applications[END_REF].

Intuitively pull-based approaches are simple to handle on the server-side, because it is stateless. Push-based approaches are not trivial to design, and require more resources on the server-side, which has to keep and manage information about the clients listening to events. Web push is often considered as a luxury for clients, with huge cost on the server-side [START_REF] Deolasee | Adaptive push-pull: disseminating dynamic web data[END_REF][START_REF] Mesbah | A comparison of push and pull techniques for ajax[END_REF][START_REF] Bozdag | An adaptive push/pull algorithm for ajax applications[END_REF].

Many Web of Things use cases also require eventnotification: sensors, routers, and home automation systems would like to trigger alerts or to notify some changes on their environment or internal state. In this context, where the server runs on a tiny device, the choice between push and pull-based approach is very important. It has a great impact on the scalability of the application, on the energy consumption of the system, on its hardware requirements, and on the reactivity and consistency obtained on the clientsside (some applications are very critical and require excellent reactivity).

We focus on the approach where each device runs a whole HTTP/TCP/IP stack rather than on solutions where the management of HTTP, TCP and IP are delegated to a gateway located between the client and the targeted device. This model is a user-centric architecture, where the embedded Web servers are organized around the client. This approach has been discussed in [START_REF] Duquennoy | Smews: Smart and mobile embedded web server[END_REF]. We showed in a previous work [START_REF] Duquennoy | The web of things: interconnecting devices with high usability and performance[END_REF] that it is possible to serve efficiently interactive AJAX [START_REF] Garrett | Ajax: A new approach to web applications[END_REF] applications over TCP/IP from devices with a CPU cadenced at a few MHz, with a few hundred of bytes of RAM and a few kilo-bytes of EEPROM.

In this paper, we discuss and evaluate the costs of the embeddability of server push for embedded Web applications. We compare push and pull based approaches in the context of the Web of Things, in order to highlight the trade-offs of each methodology. We base this analysis on the works of Bozdag et al. [START_REF] Bozdag | Performance testing of data delivery techniques for ajax applications[END_REF]: they evaluate the pros and cons of push and pull based event notification for usual (non embedded) AJAX applications.

This paper is organized as follows: Section 2 presents a state of the art of embedded Web servers and Web-based event notification. In Section 3, we present the challenges for embedding Comet in tiny Web servers. We conduct experiments in order to find the trade-offs of push and pull based approaches for the Web of Things in Section 4. We finally conclude in Section 5.

State of the art

In this section, we present a state of the art of embedded Web servers and Web-based event notification.

Embedded Web servers

Several works [START_REF] Domingues | A simple architecture for embedded web servers[END_REF][START_REF] Lin | An embedded web server for equipments[END_REF][START_REF] Priyantha | Tiny web services: design and implementation of interoperable and evolvable sensor networks[END_REF] have shown that it is possible to embed Web servers in tiny devices. Proposed solutions such as iPic [START_REF] Shrikumar | Ipic -a match head sized webserver[END_REF], WebIt [START_REF] Han | Webit: a minimum and efficient internet server for non-pc devices[END_REF] and Miniweb [START_REF] Dunkels | The proof-of-concept miniweb tcp/ip stack[END_REF] are stand-alone Web servers, with no underlaying operating system, but thought as the operating system itself. They do not rely on usual general-purpose networking interfaces like Berkeley sockets, but implement their own dedicated TCP/IP stack. That allows to design a cross-layer architecture instead of usual layered architectures, making possible many optimizations, thus saving memory, code size and energy. Their memory footprint is around one or two hundreds bytes of RAM and a few kilo-bytes of EEPROM.

Other works have been done on a more generic context, focusing on TCP/IP stack support for embedded systems: TinyTCP [START_REF] Cooper | Tinytcp[END_REF], mIP [START_REF] Shon | Protocol implementations for web based control systems[END_REF] and uIP [START_REF] Dunkels | Full tcp/ip for 8-bit architectures[END_REF]. It is possible to run a Web server on such stacks, but this forbids cross-layer optimizations for efficient Web contents service over TCP. The memory footprint of this kind of TCP/IP stack is of a few kilo-bytes of RAM and dozens of kilo-bytes of EEPROM.

As far as we know, no work has been done about the embeddability of push-based Web applications on tiny devices. In fact, many previous works on embedded Web servers mainly focus on the service of static Web pages, which are pre-processed and statically embedded in the server at compile time.

In [START_REF] Duquennoy | The web of things: interconnecting devices with high usability and performance[END_REF], we propose new solutions for efficient embedded Web applications support with very low memory requirements. We propose solutions based on off-line computations and cross-layer optimizations, where TCP is specialized for supporting an HTTP server. Our prototype, named Smews, is publicly available 1 and has been ported to various targets such as sensors and smart cards. It is able to serve efficiently fully-fledged Web applications made of static and dynamic contents, including push-based notification.

Web based event notification

HTTP was initially designed for retrieving resources on the Internet, so it is based on a simple request/response model. Today, Web servers manage dynamic applications, and sometimes need to keep their clients up-to date, in adequacy with the server state.

The simpler approach for keeping clients up-to date in a Web context consists in polling the server with an empirically chosen time interval. That can be done in dynamic AJAX [START_REF] Garrett | Ajax: A new approach to web applications[END_REF] Web applications. Small intervals improve the client-side coherence while big intervals improve scalability by saving network and server resources. A common solution for this problem is based on an adaptive Time To Refresh (TTR) [START_REF] Srinivasan | Maintaining temporal coherency of virtual data warehouses[END_REF][START_REF] Deolasee | Adaptive push-pull: disseminating dynamic web data[END_REF], trying to calculate a polling interval that fits with event publications. This approach is only efficient when the event publication tends to be constant.

Netscape introduced in 1996 a solution for pushing data from Web servers [START_REF] Netscape | An exploration of dynamic documents[END_REF], based on HTTP streaming. A longlived HTTP connection (initiated by the client) was used in order to send a streamed content. When a client notification is needed, a new part of the content is sent by the server, and the connection remains open. The browser has to be still waiting for the end of the HTTP response, which possibly never occurs. It receives notifications by chunks.

The usage of this solution in AJAX Web applications is known under the name of Comet [START_REF] Russell | Comet: Low latency data for the browser[END_REF]. A protocol draft (based on JSON and on a publish/subscribe model) named Bayeux [START_REF] Dojo | Dojo fundation bayeux protocol[END_REF] has been proposed for Comet support. The Cometd project [START_REF] Dojo | Cometd the scalable comet framework[END_REF] provides Bayeux implementations for various Web servers, such as Jetty [START_REF]Jetty web server[END_REF]. Google's DWR [START_REF]Direct web remoting[END_REF] also provides a Comet support, without relying on Bayeux.

Bozdag et al. propose a study of push and pull approaches for AJAX applications [START_REF] Mesbah | A comparison of push and pull techniques for ajax[END_REF][START_REF] Bozdag | Performance testing of data delivery techniques for ajax applications[END_REF]. They provide key metrics for performance analysis of Web-based event notification. They also conducted a large set of experiments in order to compare existing approaches (push vs. pull) and implementations (Cometd vs. DWR). The conclusion of this work is that Comet provides great reactivity, client coherence and low traffic overheads, while polling provides a better scalability in term of server-side CPU usage.

Both push and pull-based solutions have their own advantages. That is why some works [START_REF] Deolasee | Adaptive push-pull: disseminating dynamic web data[END_REF][START_REF] Bozdag | An adaptive push/pull algorithm for ajax applications[END_REF] propose adaptive solutions where the choice between push or pull is done at runtime, depending on the current server congestion and on the client requirements.

On Comet for embedded Web servers

In this section, we describe the challenges of Comet support on embedded Web servers.

Why supporting Comet?

Embedded devices such as sensors or home automation systems may offer various services, such requiring various interaction models with the client accessing them. We propose a classification of the different interactions schemes that can be needed by such systems:

On-demand information exchange: the client needs to send/receive data to/from the device (e.g., getting/sending applicative information, driving or managing the device).

Event triggering: the server needs to notify the client that something happened (e.g., the environment has changed, a precessing has ended).

Data sampling: the client needs to collect continuously data from the device (e.g., monitoring of the environment).

Since the Web of Things aims at designing embedded software using the Web applicative model, it has to provide solutions for handling each of these interaction schemes. The original REST model of HTTP (based on a requestresponse scheme) is well suited for on-demand information exchange (using GET/POST to retrieve/send data).

For supporting triggering or sampling, the device needs to push information to the client, which cannot be be done with the REST model in Web applications. That is why the support of Comet (i.e., server push in Web applications) is a key point in the design of the future Web of Things.

Long polling vs. streaming

In a general context, event-notification can be implemented easily by opening a connection from the server to the client, sending a data and closing the connection. In a Web context, a server can not establish a connection to the client, because (i) if the client is in a local network and uses address translation (NAT), it is not publicly visible and (ii) the request/response model of HTTP is always used in Web applications.

Comet implementations mainly propose two ways to notify clients on a Web context: long polling and streaming.

Long polling Each time a client needs to register to an event, it sends an HTTP request to the server. The server idles, sends the HTTP response when needed. The client connects again if it needs a new notification;

Figure 1. Comparison of long polling and streaming

Streaming When a client needs to listen for an event, it sends an HTTP request to the server. When event occurs, the server sends notifications in a chunk-encoded HTTP response, without ending it. The client is still listening. Next notification will be the following of this potentially neverending HTTP response.

Figure 1 shows the behavior of long polling and streaming approaches when notifying a client several times. With long polling, a single notification is involved per client request, while in streaming, the client receives multiples notifications per request. When the client needs to be notified multiples times, streaming generates a lighter traffic.

The Bayeux protocol provides a support for both long polling and streaming, but Cometd, the most common implementation, only provides a support for long polling. Google's DWR supports both approaches.

Server-side support of Comet

On usual Web servers, Comet is considered as heavy because it requires to manage many clients simultaneously, compared to pull-based approaches where connections are idle as soon as requests have been served.

Usual Web application containers associate server-side code to URLs (in Java for Servlets containers), and call this code for each incoming HTTP request.

Most Web servers (e.g., Apache, IIS, . . . ) allocate one thread/process per connected client, because they need one socket per connection, and because sockets are the most often managed via blocking routines. URLs handlers (e.g., Servlets) have to generate an output and to return. In Comet, this code has to enter a passive wait for an undetermined duration. As a consequence, for each client, a server based on this approach has an idle thread and TCP connection, thus wasting a lot of resources on the server.

New frameworks such as Cometd and DWR have been designed including a native support for Comet. Instead of using one blocking thread/process per client sockets, they use a common blocking routine that allows to listen on multiple sockets (based on the select POSIX system call). They provide special routines to URLs handlers (e.g., Servlets) allowing them to wait for events without idling a thread (as an example, Jetty uses continuations). When an event occurs, all URLs handlers listening for it are awaken and their associated clients receive the notification. With such strategy, no more resource is wasted for threads.

Breaking sockets, saving memory

Web servers for tiny embedded systems can work with no underlaying operating system. They use their own dedicated TCP implementation instead of usual Berkeley sockets. The most often, they are event-driven systems (they schedule their task with no thread). At a given time, only one packet is managed, either in input or in output.

In Smews, the structure used to store connections contains information about IP, TCP and HTTP. Smews is event driven and uses of only a few global buffers, shared by all the connections. Each connection only require almost 30 bytes of RAM. This allows to handle easily a large number of clients even in very constrained hardware.

Intuitively, event-driven architectures fit well with event notification. Instead of managing threads waiting for events, a simple event pool is used. This point makes possible Comet support in tiny Web servers. In Smews, when an event is generated in order to notify a set of clients, the HTTP response is built only once. It is placed in a buffer that will be used to send the notification to every listening clients in separate TCP segments (multi-cast is not supported by standard TCP). In usual OS architectures, the data is generated once per client and replicated on each socket.

Life size experiments

In this section, we put to the test various Web-based event notification methods on an embedded Web server.

Goals of the experiments

The objective of the experiments is to know the tradeoffs of various Comet and polling implementation for embedded Web applications. One of our aims is to know if the results of Bozdag et al. work [START_REF] Bozdag | Performance testing of data delivery techniques for ajax applications[END_REF] can be applied to tiny Web servers. We also evaluate the usability of push-based approach in embedded devices. The steps for achieving these goals are:

1. identifying the parameters of the various experiments, in order to benchmark different approaches on various context;

2. identifying relevant metrics in order to evaluate the trade-offs of each solution;

3. creating a Web application and implementing it for all push and pull-based approaches;

4. simulating clients connections in order to run the experiments;

5. analyzing the results of the experiments.

Experiments description

We describe here the environment of the experiments we conducted in order to compare various notification approaches in the context of the Web of Things.

Settings

We start from Bozdag et al. work, which describes a protocol for evaluating event-notification solutions. So use the same variables for the settings of our experiments.

Number of concurrent users

This variable allows to evaluate the scalability of each approach. Even in the context of Web of Things, scalability may be required: several clients may be each listening on several events of a same device. Because of embedded devices constraints and applicative needs, we choose lower interval than Bozdag et al.: Publish interval This is the frequency of event publication by the server. We used the same values than Bozdag et al.: 1, 5, 15, 30 and 50 seconds. We added a sixth configuration based on a random choice between 1 and 50 seconds, making the publication no more regular.

Pull interval When a pull approach is used, we used various intervals. We use the same values than Bozdag et al.: 1, 5, 15, 30 and 50 seconds. It may be interesting to try a strategy based on adaptive TTR, but since we measure asymptotic performance, it will provide the same result as a static interval equals to the publication interval. The sample application is very simple: the server gets a new value at a given interval. Each time, it notifies every listening clients. The application supports polling, long polling and streaming. During an experiment, a given number of clients connect to the server in order to receive notifications. All the clients use the same notification method.

The four variables described in Section 4.2.1 can be combined in 210 experiment settings. Each experiment has a duration between 5 and 10 minutes, and has been run 10 times. The results presented here are the mean of these 10 iterations, after the removal of the 2 lower and higher sampled values.

We used a script written in Python in order simulate the clients, allowing to run the experiments in the various settings described in Section 4.2.1. All the clients are simulated on the same machine and access the sensor using the same serial line.

The experiments we conduce aim at being as general as possible. The usage of a serial line, which is full-duplex and collision-free, allows the experiments to be independent from specific physical layer properties. In future works, we plan to analyze the impact of lossy links such as ZigBee, Wifi, or other shared lines.

Experimental results

In order to evaluate the trade-offs of each approach, we identified a set of relevant metrics and extracted them from our experiments. These metrics are inspired from Bozdag et al. works. In the following sections, we present and synthesize our benchmarks results (only a relevant subset of all the experiments conduced are shown).

Mean Publish Trip time (MPT)

The publish trip-time is the time elapsed between the creation of a data by the server and its reception by the client. It shows how long it takes for the client to be updated when an event occurs. In their study, Bozdag et al. showed that push-based approaches provide a lower Trip Time, so a better consistency.

Figure 2 shows the MPT we measured from our experiments, with a publication interval of 5 seconds or varying between 1 and 50 seconds.

With a few clients (less than 64), both streaming and long polling provide excellent trip times in comparison with polling. This is because with Comet, the server pushes data to all the clients as soon as an event occurs.

Long polling generates more traffic than streaming because it forces the client to send a HTTP request (around 600 bytes) between each notification (see Section 3.2). With more than 64 clients, long polling does not provide a significantly shorter trip time than polling, because clients registrations saturate the traffic.

Streaming provides the shortest trip times, because it generates a lightweight traffic. With a growing number of clients, it makes a gap with both long polling and polling approaches. Streaming approach provides low trip time with no scalability issue. With a publish interval of 5 seconds, the traffic is saturated in most configurations. Logically, in such case, the mean trip time is almost half the publication interval. In this context and with 256 clients, the streaming approach allows to reach a mean trip time of only 1 second.

Server Performance (SP)

The server performance shows the CPU usage of the server software. In Bozdag et al. experiments, it was used as the indicator of the server charge. The authors concluded that SP grows faster with Comet solutions, possibly causing scalability issues. In our experimental configuration, the performance bottleneck is the network capacity rather than the CPU, so we did not measure SP in our experiments.

Received Publish Messages (RPM)

The RPM is the mean amount of messages received by the clients. When presented as a percent of the published events, it shows the possible traffic overhead.

Figure 3 shows the RPM for a publish interval of 1 second and of 50 seconds. With Comet (long polling as well as streaming), the RPM never exceeds 100% because each published data is received only once by the clients.

With polling, the lower is the polling interval, the higher is the RPM. With 16 or less clients, a polling interval of 1 second and a publication interval of 50 seconds, 5000% of the publications are received; in other words, 98% percent of requests were unnecessary. We also notice that when using polling with a high rate, the RPM decreases with higher number of clients. This occurs when the serial line of the sensor is saturated with the traffic.

Received Unique Publish Messages (RUPM)

The RUPM is the mean amount of unique publications received by clients. It is given as a percent of the published events, and shows if clients miss any items.

Figure 4 shows the RUPM for a publish interval of 1 second or of 30 seconds. It shows that with a too big polling interval, the clients may miss many notifications. With many clients, the network bandwidth is saturated, also involving misses. The long polling approach provides a RUPM that is comparable (in fact, a bit worse) to the polling approach with an interval equals to the publication rate. This is because long polling requires one HTTP requests per notification, as well as polling.

With the streaming method, misses are quite rare. The RUPM is close to 100% even with 128 clients for a publication interval of 1 second. The only situation in which we obtained a RUPM significantly lower than 100% with streaming was with a publication interval of 1 second and more than 128 clients.

Logically, with slow publication rate, clients misses become more rare.

Received Message Percentage (RMP)

This variable was used by Bozdag et al. to have an indicator on packet losses. In our configuration, the network bottleneck was the serial line of the sensor, where losses never occur, so we did not measure the RMP.

Network Traffic in Packets (NTP)

The NTP allows to evaluate the network usage of a strategy.

Figure 5 shows the NTP for a publish interval of 1 second or varying between 1 and 50 seconds. For polling and long polling approaches, the network comes to saturation from almost 50 packets per second. This highlights the situations where the bottleneck is the traffic (with many clients and/or short polling intervals). With streaming, NTP grows up to 250 packets/second with a publication every second and 128 or more clients. This is because with streaming, the traffic is made of a lot of small TCP segments, allowing to send more packets with the same bandwidth limitations. In fact, this point helps the streaming approach in providing good performances.

Network Traffic in bytes (NTB)

This metric was not used by Bozdag et al., but our analysis of the NTP shows that it is not the best way to synthesize network congestions. That is why we also evaluate the net-work traffic in bytes per seconds.

Figure 5 shows the NTP for a publish interval of 1 second or varying between 1 and 50 seconds. It provides a precise overview of the network usage. It shows that long polling generates a heavy traffic; this is because it involves requests between each publication. With a large polling interval, polling allows a very low network usage (but provides less data coherence).

Streaming provides a lower traffic usage than long polling or polling with a short interval.

Mean Coherent Time (MCT)

Finally, we introduce a new metric in order to evaluate the client-side data coherence. Bozdag does not take into account client misses. A low trip time can be obtained even with many misses. MCT represents the amount of time spent by the clients with up-to-date data.

It provides a synthesis of all the metrics. Figure 7(a) and 7(b) show the MCT for a publication interval of respectively 1 and 50 seconds.

With a publication interval of 1 second, streaming makes a gap with long polling and polling with any frequency. With 128 clients, it reaches 50%, compared to results between 1% and 7% for polling and long polling.

With a publication interval of 50 seconds, MCT values are higher than with an interval of 1 second. Note that when polling exactly at the publication interval and when no congestion occur, the mean coherent time is of 50%. This is due to the lack of synchronization between the server and the clients. Some clients send their requests and retrieve a data that has just been published by the server, while other clients get their notifications a few seconds before their expiration.

Results analysis

We propose a summary of the results we presented in Section 4.3. We highlight the trade-offs of various event notification approaches in various contexts.

Impact of the network

The network capacity plays an important role in the quality of Web-based notification. In our experiments, the server is accessed via a serial line at 14400 B/s. Such a small throughput is common in embedded devices network links, which networking hardware often has no DMA and is unable to manage packets queues. With such simple hardware, which is very different from computer network interfaces, the network capacity is limited by the CPU speed.

The most efficient strategy in term of traffic usage is polling with big interval. In fact, with polling, the traffic generated by each client is very predictable and easy to control. The polling interval can be chosen depending on the number of clients and the network capacity. This is the main advantage of polling approaches.

The traffic generated by Comet approaches is not depending on a client interval but on the server publication interval. Long polling is sensibly heavier than streaming in practice, because it produces a lot of HTTP requests, which are of typically around 600 bytes, while notifications often contain only a few bytes of payload. Streaming produces mainly very small packets, involving low bandwidth usage.

Data coherence

In their paper [START_REF] Bozdag | Performance testing of data delivery techniques for ajax applications[END_REF], Bozdag et al. showed that Comet provides the best coherence. They only used solutions based on long polling, because streaming is still rarely implemented. In the context of embedded Web servers, our results show that long polling does not provide a great data coherence. The MCT obtained with long polling or with polling at the right interval are similar. Long polling allows to reach low trip time, but it involves traffic overhead when compared to polling, because of the cost of client registrations.

By implementing a support for HTTP streaming in our prototype, we were able to compare streaming to long polling and to polling. Our results show that streaming makes a gap with other solutions for all of our 210 benchmark settings. This is because it generates a small amount of requests, uses small packets and is very easy to manage on the server-side since it makes incoming requests very rare. Once the clients are registered, they are served very efficiently. This approach is also the most scalable.

Summary

We showed that Web servers embedded in very constrained devices are able to run Comet Web applications. Furthermore, thanks to very small dedicated connections, they are able to handle a large number clients when compared to the amount of volatile memory available.

Bozdag et al. obtained excellent performances with long polling in the context of powerful Web servers in [START_REF] Bozdag | Performance testing of data delivery techniques for ajax applications[END_REF]. We show that these results can not be applied directly on constrained Web servers, because tiny devices suffer of their slow network interfaces.

By proposing a streaming support in our prototype, we showed that Comet is a great solution for event notification in embedded Web applications. In fact, the streaming approach provides the best results in term of publish trip time, received events, non-redundancy of messages, data coherence and scalability.

In practice, long polling is never better than streaming, but is still interesting is some cases where a client needs to be notified only once of an event.

Polling may be interesting for event-notification only when a great number of clients are needed without requiring a high data coherence: by using a very large interval, the traffic required per client can decrease to very low values.

We identified in Section 3.1 three interactions schemes for Web applications. We summarize here how each of them should be handled in a Web of Things context:

On-demand information exchange: this is the basic scheme for Web interactions, for which Comet is not needed. Usual request-response interactions (like with polling) are well suited for it.

Event triggering: event triggering should be implemented with long polling, because this allows a client to listen only once for an event.

Data sampling: data sampling should be implemented with streaming, since this is the most efficient approach for continuous samples retrieval by a client, as shown by our experiments.

Conclusions and perspectives

The support of Comet in embedded devices is a key point in the design of the future Web of Things.

Server push solutions are known as reactive but not scalable. Bozdag et al. showed [START_REF] Bozdag | Performance testing of data delivery techniques for ajax applications[END_REF] that push-based approaches in Web applications are efficient in terms of reactivity, consistency and traffic. The only benefit of polling is the serverside resources usages, allowing a better scalability.

Based on this work, we conducted similar experiments in the context of the Web of Things. We first showed that by using an fully integrated Web server (with its own communication stack, with no OS), Comet can be supported in very constrained devices (256 simultaneous clients supported in only 10 kB of RAM).

The results of our benchmarks showed that Comet provides heterogeneous performances depending on the way it is implemented. Streaming makes a gap in term of performance with both polling and long polling approaches. As a big difference with Bozdag et al. results, streaming provides the best scalability.

The event-driven model used by embedded Web servers, coupled with their dedicated TCP/IP stack, allows to support efficiently event-notification. In such model, the whole system is event-driven, making push approaches easier to support. In fact, the well-known scalability issues of pushbased approaches seem to be due to traditional OS constraints, which break the native event-driven model of the hardware.

In future works, we plan extend the scope of this study to contexts with link losses and collisions. We also would like to analyze the energy consumption of the devices when notifying events in order to study duty cycle management.

[ 1 ;

 1 256], instead of [100;10000].

  Application mode For this variable, Bozdag et al. used three modes: polling, Cometd, DWR. Since Cometd and DWR can not be executed in tiny devices with no operating systems, we use our own Comet implementations. Our three modes are: polling, long polling, and streaming. Bozdag et al. did not use any streaming implementation.

Figure 3 .

 3 Figure 3. Received Publish Messages for a publish interval of 1s (a) or 50s (b)

Figure 4 .Figure 5 .

 45 Figure 4. Received Unique Publish Messages for a publish interval of 1s (a) or 30s (b)

Figure 6 .Figure 7 .

 67 Figure 6. Network Traffic in bytes for a publish interval of 1s (a) or varying between 1 and 50s (b)

Mean Publish Trip time for a publish interval of 5s (a) or varying between 1 and 50s

	Long Polling	Streaming	Pull 1s	Pull 5s	Pull 15s	Pull 30s	Pull 50s
	Figure 2.

(b)

4.2.2 Experiments configuration

We designed Web applications with event notification for the experiments. They are executed by our embedded Web server prototype, Smews (this is the only available embedded Web server that supports Comet). The device we choose for our experiments is a sensor named WSN430, with the following hardware configuration: 16 bits MSP430 CPU at 8 MHz, 10 kB of RAM, 48 kB of EEPROM and a serial line at 14400 B/s as communication interface. With its smallest configuration, Smews only requires 200 bytes of RAM and 8 kB of EEPROM.

  et al. made use of the MPT to evaluate it, but this metric is perfectible because it

	kilo-bytes per second				kilo-bytes per second
	10					10
	5					5
	0					0
	1	16	64	128	256	clients	1	16	64	128	256	clients
	(a) Publish interval: 1 second			(b) Publish interval: varying
	Long Polling	Streaming	Pull 1s		Pull 5s	Pull 15s		Pull 30s	Pull 50s

Smews source code available at: http://smews.gforge. inria.fr/


Amel Bennaceur

Singh Pushpendra

Pierre-Guillaume Raverdy

Valérie Issarny

Pushpendra Singh

The iBICOOP middleware: Enablers and Services for Emerging Pervasive Computing Environments

published or not. The documents may come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

Nowadays, users rely on various sets of connected devices and services to interact with each other: home gateways, laptops, smartphones, UMPC, enterprise servers, Web/cloud computing services... While for a long time interactions have been mostly Web-centric, users now routinely engage in usercentric interactions such as content sharing and social networking through mobile devices. Indeed, these devices have grown very powerful in terms of computational, visual, and storage capabilities. They are able to retrieve, display and manipulate content or information easily. They also offer compelling advantages with the realization of the fixed/mobile convergence that enables anywhere/anytime IP connectivity to all terminals with extended networking capabilities (e.g., 3G/HSPDA, Wi-Fi, Bluetooth). Cellular and IT networks can be seamlessly used by mobile phones, as well as laptops or mobile multimedia players that are now fitted with mobile phone connectivity. Multiple devices with multiple communication interfaces give users more than one way to access content and interact depending on their context and needs.

While mobile devices have become very capable of communicating with other devices, accessing or exchanging content is far from being easy: communication costs are still high, communication protocols are not uniformly supported, communication links are not always reliable... Another problem lies in the role usually assigned to mobile devices. Although mobile devices are the primary terminals for interaction, they have essentially focused on (i) acting as clients accessing services in the infrastructure (e.g., enablers in the IMS infrastructure for Telecoms networks, or Web services in the Internet), or (ii) manipulating content stored locally (e.g., multimedia content playback). However, there has been little success in truly integrating these mobile devices in the pervasive computing environment (i.e., acting also as resource or service providers) [START_REF] Issarny | Developing ambient intelligence systems: A solution based on web services[END_REF], [2].

Furthermore, the use of multiple devices, having large storage capabilities, has resulted in the scattering of content on a set of devices, which, ironically, is making access to all the content that one possesses a big challenge (where is this file? Is it the latest version?). This problem becomes acute when it comes to impromptu collaboration (e.g., in business meetings, conferences, or on the road). Such collaborations often require exchange of content, and have to wait till the user gets physical access to the device over which the required content (or the correct/latest version) is currently stored. Delay in accessing the content often cause frustration and missed opportunities.

Besides research community, recently a number of industry initiatives have also been announced that try to address these issues (Section II). However, these initiatives are mostly vendor centric, and focus on Internet-centric solutions (i.e., the "mobile as a client" approach). Indeed, providing an integrated environment for all the user's devices in a fixedmobile pervasive environment poses a number of specific challenges (Section III) such as ubiquitous content access, efficient connectivity management, flexible communications, or security and privacy. To answer these challenges, and better support interactions between mobile users, we develop the iBICOOP middleware (Section IV). Our middleware addresses these challenges by targeting both fixed and mobile devices, leveraging their characteristics (e.g., always on and unlimited storage for home/enterprise servers, ad hoc communication link between mobile devices), and by leveraging the capabilities of all available networks (e.g., ad hoc networks, Internet, Telecoms infrastructure networks). It also relies on Web and Telecoms standards to promote interoperability

II. BACKGROUND

As mobile computing emerged in the early 90's with the advent of notebooks and pre-Wi-Fi networks, much of the re-search focused on supporting disconnected operations, mobile file systems [START_REF] Noble | Agile application-aware adaptation for mobility[END_REF], [START_REF] Terry | Managing update conflicts in bayou, a weakly connected replicated storage system[END_REF], and algorithms for file or object replication [START_REF] Osrael | What service replication middleware can learn from object replication middleware[END_REF]. However, these approaches focused on powerful terminals (for the time) and mobile IP-based networks. For normal users. mobile computing was still vague. Mobile phones however started to incorporate Personal Information Management (PIM) applications (e.g., contacts, calendar...) and vendors started to release tools for synchronizing a user's desktop and mobile phone PIM data and content (e.g., Microsoft's ActiveSync or Nokia's PC Suite). Nowadays, users not only need tools to organize and synchronize their content and PIM information, they also want to share and exchange data with friends, family and colleagues. So, content distribution over a large set of devices and mobile services in general have attracted more attention from both major industry players and the research community. Microsoft has recently launched LiveMesh1 that proposes to offer a unified view of all the user's devices through live desktop; users can add or remove device to their live desktop and can manage applications and data over any of the device. They are proposing the LiveMesh sync service to synchronize data across multiple devices. Currently, only Windows-based PCs are supported but they plan to extend it to mobiles and other devices (Mac, Symbian etc.) in future. LiveMesh also allows creating shared spaces for multiple users. LiveMesh security is based around a combination of AES and RSA, along with SSL, for secure data transfer, while user identity relies on Windows Live ID.

Other approaches, offered by Apple MobileMe2 and Nokia OVI 3 , go beyond simple synchronization services that they used to offer through iTunes and PC Suite. OVI is a collection of services that help users in managing their personal information and media through the use of the Web-site of Ovi.com. Users get a personal space called "personal dashboard" and they can share photos with friends and manage their music or other medias. The main idea is to have a single location where users can manage their data (emails, contacts, bookmarks,...). Similarly, MobileMe is a set of services to keep the personal information such as e-mail, calendars, address books etc. synchronized on all user computers -Macs, Windows PCs, iPhones and iPod Touches. The idea is to use a server to store the master copy of all information over the Internet and when user machines come on-line, they synchronize. Users can get space in form of a virtual disk, where they can store and share their data, using the Web-site Me.com -managed by Apple.

Pervasive computing, mainly investigated in the research community, aims to provide computing and communication services anytime, anywhere, transparently, and invisibly, to the user using devices embedded in the surrounding environment. In the past few years, a number of pervasive computing systems have been developed. Smart Personal Information Network (Smart PIN) [START_REF] Lee | User-centric utilitybased data replication in heterogeneous networks[END_REF] is a performance and cost-aware personal information network, which uses a novel user-centric utility-based data replication scheme to exchange content automatically based on both network performance and user interests. There are also several research works that address content sharing in pervasive environments. In HomeViews [START_REF] Geambasu | Homeviews: peer-to-peer middleware for personal data sharing applications[END_REF], authors propose a peer-to-peer middleware system for building personal data management. They provide abstractions and services for data organization and distributed data sharing. To do so, HomeViews exposes, to applications, a database view abstraction of the file system, provides a capabilitybased access control scheme and defines a distributed query execution layer. XMIDDLE [START_REF] Mascolo | Xmiddle: A data-sharing middleware for mobile computing[END_REF] enables transparent sharing of XML documents across heterogeneous mobile hosts, allowing on-line and off-line access to data using wireless LAN and UDP; but it does not deal with heterogeneous networks. Light-Peers [START_REF] Christensen | Lightpeers: A lightweight mobile p2p platform[END_REF] proposes a platform for lightweight mobile pure P2P networking using different mobile devices such as Tablet PCs, PDAs and mobile phones to produce, organize, present and share digital material. The LightPeer architecture is composed of: a software stack of four component layers (Network, P2P, Sensors/Actuator and Application), a data model and a set of P2P networking protocols for transmitting data between devices. None of the three last middleware deals with security which is a key requirement of today's systems. AdhocFS [START_REF] Boulkenafed | Adhocfs: Sharing files in wlans[END_REF] investigates this issue and also offers manging coherency, dynamic ad hoc groups [START_REF] Boulkenafed | Using group management to tame mobile ad hoc networks[END_REF] and enhanced data availability on mobile nodes [START_REF] Boulkenafed | A middleware service for mobile ad hoc data sharing, enhancing data availability[END_REF]. Another system that deals with security is Mobile Gaia [START_REF] Chetan | Mobile gaia: a middleware for ad-hoc pervasive computing[END_REF]. Mobile Gaia is a services-based middleware that integrates resources of various devices. It manages several functions such as forming and maintaining device collections, sharing resources among devices and enables seamless service interactions. It also provides an application framework to develop applications for the device collection. Furthermore, Gaia Microserver extensions [START_REF] Chan | Gaia microserver: an extendable mobile middleware platform[END_REF], developed with J2ME, enables thin clients to fully access device specific features while respecting security through a standard interface as Gaia services.

III. COLLABORATION IN PERVASIVE ENVIRONMENTS

Enabling users to have full control over their data with alltime access is the major motivation behind our work. In this section, we present our motivations through a simple scenario, and then derive our requirements for a solution that should overcome the identified challenges.

A. Scenario

We consider Alice who leads a R&D team in a large company, and is on her way to a standardization meeting with a colleague and a contractor. Their documents for this meeting are scattered on several devices: the company servers, their laptops, and their mobile phones. Due to past interactions they all have each others certificates and device descriptions. Midway through her presentation, Alice needs specific results from recent experiments performed by the contractor. With his permission, she connects to his shared work folder, fetch the document, and display the relevant tables. For this interaction, the system needs to quickly identify which interface is the best to get the document on Alice's laptop immediately. As it is a work-related request, the company-paid 3G connection can be used to quickly connect to the company servers instead of using ad hoc connections to the consultant's smartphone using Bluetooth OBEX or the overloaded WiFi network.

Later, her colleague Stan makes his own presentation on the software developed by the team. During the demo, a participant asks some details about one of the tools used to develop the software. Alice connects to both Stan and the contractor's work folders and search for all documents on this topic. She then sends some relevant white papers to the person to complete Stan's response. In this case, Alice sends a search request to the local devices of her colleague and the contractor over WiFi. As processing the request may be power intensive, both devices forward the request to the enterprise server. The contractors device also forwards the request to the contractor's network. The returned documents are displayed on the work folder of Alice's laptop, but have only been copied on the enterprise server. The enterprise server thus processes her email request.

After the meeting, the same participant presents the tools they are developing to Alice. They exchange their contact information with their mobile phones and the person is then able to send some flyers and videos to Alice. As this is not an urgent matter, the new content will be synchronized on the companys server when she returns. At this stage, a new partnership needs to be established between Alice and the participant. As it is a first encounter, both provide limited information and access credentials (i.e., mobile phones only). And also the contents are exchanged in an ad-hoc way.

B. Requirements for a user-centric pervasive middleware

From the above scenario, we identify that despite the device and environment heterogeneity, users need seamless communications with each others as well as ubiquitous content access. Furthermore, these functionalities should be provided, taking into account key transversal issues such as contextawareness and trust. Finally, naming of resources should be user-friendly so as to solve conflicts easily and their discovery should be simple and efficient. These requirements are now detailed.

Device heterogeneity: The tremendous growth of the mobile market has resulted in variety of devices available for end users. While some countries like Japan have a dominant player that enforces software and hardware specifications for these mobile devices, others like Europe or the U.S. have very large variations in the actual capabilities of the devices. Furthermore, operators, there, also have very complex subscription plans. It then becomes complex and costly for application developers to address a significant share of the mobile market. This explains the slow growth of mobile data and also, ironically, the many incompatible initiatives for new mobile platforms. This problem is however for the device and system manufacturers, and Telecoms operators to solve.

In iBICOOP, we stress the use of well-accepted standards and promote solutions that interoperate with existing protocols and services using such standards.

Communication and reachability: nowadays, mobile devices have multiple networking interfaces (e.g., 3G, WiFi, Bluetooth). However, these interfaces, and the underlying networks they connect to, are mostly aimed at anytime, anywhere Internet access (i.e., mobile device acting as a client only). They are not well suited for pervasive computing interactions. Some devices prevent background processes to preserve energy, others have a shared hardware radio for Bluetooth and WiFi that limits concurrent communications, not all recent mobile devices support the PAN profile for Bluetooth (i.e., IP network). Telecoms operators also only provide dynamic IP addresses, block ports, and do not allow incoming connection to mobile devices for all customers. Finally, interactions in pervasive computing environments also often rely on lightweight group communication (i.e., IP multicast) that is not available in 2.5/3G networks. Distributed services working on both fixed and mobile devices then require advanced communication support able to bypass such limitations.

This requires to provide mechanisms that permit easy connection between different devices. As current day devices have more than one network interfaces available, the mechanisms should be able to exploit it.

Context-aware content management: content replication and sharing in mobile environments is more than a decade-old problem and many solutions have already been investigated. However, multi-devices, multi-users environments add new constraints for moving around content: multiple sources and/or multiple destinations may be available and the correct coupling depends on context information such as the communication cost, the use and the importance of the content.

Trusted interactions: One of the major requirements of content access and sharing is secure communication. While existing and well-established security mechanisms should be used, careful integration should be considered. Indeed, the security mechanisms employed to keep content access secure should not be too intrusive and complex to be at the risk of being ignored by users. Some solutions are emerging in the internet work in terms of Single-Sign-On4 and Windows Cardspace5 , but they have been designed for Web-site security and not pervasive computing devices. Impromptu collaborations also bring challenges for privacy along with security.

Users should be in control and aware of the content that they share. In particular it must be possible to provide transient information, or to reveal little information initially, and later complete one's information stored by other people as required.

Naming and discovery: With content and services scattered over sets of heterogeneous devices, a flexible naming scheme is required to easily and accurately locate resources. Moreover, it is important for end-users that this scheme is in human readable form to easily identify/validate the targeted resource. The process of assigning names should be easy and intuitive and users should be able to resolve conflicts if that happens. Given the heterogeneous nature of the underlying networks (e.g., IP multicast support) and the limited resources of mobile devices, especially energy which prevents continuous communication, a lightweight mechanism is required to announce and discover resources, making the best use of available infrastructure services. In particular, it should be possible for a client searching a specific resource to wait for its availability, or to setup a request for connection at a specific time (e.g., for content synchronization). Finally, searching or registering resources raise concerns for privacy and trust (knowing which services a user provides or search for may lead to specific attacks)

IV. IBICOOP ARCHITECTURE

The base architecture of the iBICOOP middleware, as depicted in Figure 1, consists of core modules on top of which we can develop applications that may arise in up-coming multi-device, multi-user world. Major constraints come in our work mainly from three dimensions -network characteristics, device characteristics, and software running on them -and we aim to solve them through the core modules of iBICOOP. Collaboration Services i.e., Replication Service and Exchange & Sharing Service are two major applications that we provide with iBICOOP. We believe that functionalities provided by iBICOOP are generic in nature and can be used to develop different applications in near future.

A. Core Modules

The core modules in the iBICOOP middleware provide base functionalities needed for more advanced applications:

1) Local File Manager: To support synchronization, replication, and sharing along with traditional file managing tasks, the iBICOOP Local File Manager has extra capabilities. The Local File Manager gives user clear cues to the files that have been replicated across multiple devices or shared among different users by using different icons. Users can also see if a conflict has resulted because of independent modifications on different devices.

The Local File Manager is also responsible for access control -on shared devices, users only see files, they have access to. Access control also goes to the operations that are allowed on a file by a specific user.

2) Communication Manager: The iBICOOP Communication Manager is aimed to come over the constraints of different network characteristics that different devices may have. The Communication Manager provides mechanisms to communicate over different available network interfaces of a device -Bluetooth, WiFi, Cellular -and also using different technologies e.g., Web services, http/tcp sockets, ad-hoc mode. The communication between two devices is always secured with SSL. Users can define criteria, such as low-cost or high-speed, to influence the decision of choosing a network interface over another or they can explicitly choose a particular interface [START_REF] Rong | Mobility management in b3g networks: a middleware-based approach[END_REF]. It will not always be possible to have all the network interfaces available for communication, in those case user choices will be limited.

We are using a proxy-based solution to overcome the problem of IP-reachability -especially in cellular (3G) or private networks. In those cases, iBICOOP asks users to register on a proxy server. When users can not be reached directly, their data is cached on the proxy and forwarded to their registered device. Unlike other available solutions such as OVI or MobileME, users can choose or deploy their own proxy server.

3) Security Manager: The iBICOOP Security Manager uses well-established techniques of cryptography and secure communication to provide necessary security. Presently, we are providing RSA, AES, DES, and Diffie-Hellman for generating keys that can be used for encryption/decryption of data for storing on device or sending over the net. Communication over the net is always secured using SSL.

Symmetric Key algorithms are faster so we advocate their use between users, once the key has been exchanged. Secure exchange of keys is done using RSA. In some cases users can also use Diffie-Hellman to generate a symmetric secure key. However as the protocol is vulnerable to "man in the middle" attack, its use is at the discretion of users depending on the context of interaction.

The GUI of the Security Manager provides users a simple interface to create keys, using different algorithms that are available on that device, and also select files to encrypt or decrypt.

4) Partnership Manager: To overcome the challenges of device heterogeneity and provide context-aware content sharing and trusted interactions, it is necessary to have information about devices and users involved in the activity. The iBICOOP Partnership Manager provides this information in form of profiles -device profiles and user profiles. Profiles are stored as XML files. This allows us to easily integrate our profiles with the IMS architecture using XDMS (XML Data Management Server). We have defined XML schema for both device profile and user profile. The iBICOOP Partnership Manager provides a simple GUI to create and edit a profile.

A device profile is a set of information about the capabilities of the device. It contains information such as available network interfaces, reachability to/from Internet, available memory etc.

Every device in the iBICOOP middleware has a profile. The Partnership Manager provides tools to generate profile for a device which can then be edited/updated by the user. In case of mobile devices, users can transfer the profile XML file to a PC or laptop and can edit it there and then transfer back to the device -XML schemata ensure the integrity of profiles.

A user profile is a collection of information about the user, devices owned by user, and available security mechanisms. To use any of the service of the iBICOOP middleware, users start by creating a basic profile about them -much like user account on a Web-site. Using XML schema, they can create it using any XML editor of their choice or they can use the GUI tool provided by the Partnership Manager. This profile contains only high-level basic information -e.g., emails, id, contact information. Later as user adds a device, the corresponding device profile is added to the user profile. Creation of security keys will also show up in the user profile as available security mechanisms. This profile grows to include other information as users use iBICOOP.

In the iBICOOP middleware, profiles are used by core modules to make a service available for user. For example user profiles will need to be exchanged before starting any collaboration between users. The profiles can be exchanged over several means -email, Bluetooth OBEX. Then the Communication Manager modules on both side can extract the embedded device profile in it and use it to establish a communication.

To make our solution privacy-aware, the Partnership Manager module provides filters to control the information exchanged in a profile. To start with we define three types of filters: public, trusted or private. A filter declares what field will be exchanged, e.g., a public filter is limited to share only the type of network interfaces (e.g., WiFi, Bluetooth) while a trusted filter can share the IP addresses of the interfaces too. A user can choose a filter at the beginning of an exchange and only the information corresponding to that filter will be shared. The iBICOOP Partnership Manager module provides GUI tools for users to override the fields, defined by a filter, thus allowing them to create their own filters with any relationship as they deem appropriate.

As a collaboration happens, user profiles will be updated to include the information about the partnership. Users can also manage partnerships in groups if they wish so; in this case new partners share their profiles, using public filter at first, and then can manage the relationship as they wish. A user profile gets updated with every status of partnership that takes place or gets terminated by user. We also aim to make use of IMS presence service to provide real-time information about the partners of a user.

5) Naming & Discovery: As a general rule a naming scheme should be scalable and provide unique reference to a resource. We also insist that names are human-readable and users should be able to make a quick reference to the resource by just looking at the name. This brought us to not use autogenerated GUID (Globally Unique ID).

To ensure these goals, iBICOOP's naming scheme is based on hierarchical names in the pattern of URI scheme6 ; A similar approach has been advocated in [START_REF] Chung | Non-anchored unified naming for ubiquitous computing environments[END_REF], [START_REF] Ford | User-relative names for globally connected personal devices[END_REF]. We combine names of protocol, devices, services, email etc. to give a humanreadable name to a resource. For example an iBICOOP user is identifiable uniquely by using email of a user as a central part of ID; devices that a user owns are identifiable through user id and then combining the unique name of the device within that user's domain; similarly names are derived for services available from a particular device. An example for a service is : "ibic://john@work.com:ipaqpda/axis2/services/exchange". We feel that a user can comprehend clearly about a resource by just looking at the name. As emails are unique, users will be uniquely identifiable, which will ensure that every resource related to them are also identifiable.

Most service discovery protocols for pervasive computing require IP multicast support (e.g., SLP, SSDP) either for distributed advertisement/request, or for discovering a centralized repository in the local network. While this scheme is effective in WiFi or intranets, it cannot be used over the Internet or in Telecoms networks. For such environments, UDDI-like repositories, with complex API and well-known addresses are usually available. While context-aware service discovery service can be devised for pervasive environments [START_REF] Raverdy | Efficient context-aware service discovery in multi-protocol pervasive environments[END_REF], they require powerful nodes to forward discovery messages across networks in the environment, and raise energy and security problems. As for iBICOOP, we rely on SLP to find nearby services on currently active network interfaces that support IP multicast. The search syntax is however extended to discover all resources for a specific user or a specific device in a network. As for the communication's proxy server, we consider all users have a dedicated repository where they register their resources. If a user knows the repository's address of another user via his profile, the repository can be queried to discover resources of another user. Finally, users may dynamically register resources to any repository given they provide the appropriate credentials (e.g., temporary repository service set up for a conference or trade show). Setting up partnerships between users (bootstrapping a relationship) may also use the discovery service, and may happen after a multicastbased local discovery (e.g., over WiFi) for any Partnership Manager service, or by searching for such services on a public repository,

B. Collaboration Services

The goal of the iBICOOP middleware is to provide abstractions that makes it easier to build services dealing with heterogeneous networks, different devices and security. We propose two collaboration services built on iBICOOP core modules: the Replication Service and the Exchange & Sharing service.

1) Replication Service: With more and more devices per user, easy replication and synchronization of files has become a key requirement for many users. The iBICOOP Replication Service keeps track of the files that are replicated over the user workspace. A workspace is the total space available on all the user devices. User are made aware of conflicts if they try to synchronize with a copy that has been modified on another device. Users can add or remove files from replication service when they wish so. A multi-criteria algorithm is used to choose the best way to transfer data during replication.

2) Exchange & Sharing Service: While the Replication Service allows data management and synchronization between heterogeneous devices of the same user, using the concept of workspace, the Exchange and Sharing Service takes the abstraction to a higher level by allowing several users to interact and collaborate in various scenarios. No matter where data is located, users can transfer and share data between their workspaces. Let us consider two users, Alice and Bob. Alice has a phone with only 3G access and Bob has a PDA connected to Internet through WiFi. Alice wants to transfer a file to Bob. She knows that this file is in her workspace but she can not recall where it is exactly located. The Exchange & Sharing Service can locate all the copies of the file and present all the possibilities to transfer the file between one of Alice's devices and Bob's device.

The service allows users to choose the best way of exchanging data considering the context and their preferences. The aim of this service is to make long-term collaborations or impromptu exchanges an easier and secure task. Using this service, users can set partnerships with other users using different security mechanisms that are available to them. The iBICOOP modules provides support for different network interfaces and help overcome many of the challenges described in III-B. Once a partnership is established, connection between two devices can become immediate except for cases when device or protocol-based restrictions has to be dealt by user. Sharing a document can notify user of modifications and ability to synchronize with latest version.

C. Implementation Status

We currently implement the iBICOOP middleware in Java, using IBM J9's JVM with CDC 1.1 for Windows mobile PDA and smartphones, as well as native CLDC/MIDP for other phones and smartphones. On the infrastructure side, services (e.g., Communication proxy service and Discovery service) are developed in Java 1.6, and deployed on Apache Tomcat and on the Alcatel 5350 IMS application server (for the IMS infrastructure). A number of core modules have already been implemented (Partnership Manager, Security Manager, and Communication Manager) on specific devices and are being ported. We plan to implement iBICOOP as a tight integration between services on the Internet, local networks, and in the IMS architecture thus providing a solution for both the Telecoms and Internet world.

V. CONCLUSION

In iBICOOP, we are developing a middleware to allow ubiquitous access of user data from a multitude of devices with heterogeneous capabilities and running on different platforms. The services that we are building on top of iBICOOP aim to show viability of iBICOOP as a standard-based platform for future advance services. Leveraging Telecoms and Internet world, integration with IMS architecture, is one of the salient feature of iBICOOP that we have not found in other proposed solutions. To conclude iBICOOP offers a complete solution for end-user with regards to content-sharing and data management in emerging pervasive computing environments.

Fig. 1 .

 1 Fig. 1. the iBICOOP Architecture

https://www.mesh.com/

http://www.apple.com/mobileme

http://www.ovi.mobi/ovi/app/ovi/index

http://openid.net/

http://msdn.microsoft.com/en-us/library/aa480189.aspx

http://tools.ietf.org/html/rfc3986