Luciano Da Fontoura
email: luciano@ifsc.usp.br

Luciano Da

F Costa

Toward Robust Data Classification

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

Introduction

The task of classification, be it in its supervised or unsupervised versions, has acquired substantial importance thanks to its potential application for the most of scientific and technological areas, as well as for its respectively implied challenges implied by the presence of outliers and overlap between the constituent groups (e.g. [START_REF] Jain | Statistical pattern recognition: a review[END_REF][START_REF] Fukunaga | Statistical Pattern Recognition[END_REF][START_REF] Da | Supervised and unsupervised pattern recognition and their performance[END_REF][START_REF] Da | Shape Classification and Analysis: Theory and Practice[END_REF][START_REF] Koutrombas | Pattern Recognition[END_REF]).

The present work describes an approach to data classification which is based on the recently reported [START_REF] Da | Similarity means: Seeking for robustness to outliers[END_REF] concept of similarity between a value and a set of values. This definition applies to several types of similarity indices, including the Jaccard (e.g. [START_REF]Jaccard index[END_REF][START_REF] Da | Further generalizations of the Jaccard index[END_REF]) and coincidence (e.g. [START_REF] Da | Further generalizations of the Jaccard index[END_REF][START_REF] Da | On similarity[END_REF][START_REF] Da | Multiset neurons[END_REF][START_REF] Da | Coincidence complex networks[END_REF]). That definition consists of taking the maximum similarity between the value and the set of values as the respective resulting similarity. The above concept is also generalized to the quantification of the similarity between a vector and a set of vectors as suggested in [START_REF] Da | Similarity means: Seeking for robustness to outliers[END_REF].

The main motivation for the reported approach stems from the fact that the Jaccard, and particularly the coincidence, similarity indices have been verified to provide several interesting characteristics, including enhanced se-lectivity and sensitivity while comparing values, incorporation of normalization of the data values, as well as marked robustness to data perturbations and presence of outliers (e.g. [START_REF] Da | Further generalizations of the Jaccard index[END_REF][START_REF] Da | On similarity[END_REF][START_REF] Da | Multiset neurons[END_REF][START_REF] Da | Coincidence complex networks[END_REF]).

As indicated by the results described in this work, which are respective to an adaptation of the traditional nearest neighbor method for supervised classification, the Jaccard similarity between a value and a set of values allowed substantially enhanced stability and consistency of the identified clusters even in presence of intense overlap between the original groups.

Two main types of data have been considered in the present work, respective to symmetric and asymmetric distributions. While the former case tended to promote enhanced robustness to data overlap, the latter case has been found to lead to substantial shifts of the arithmetic means and center of mass, with the Jaccard mean providing a markedly more stable approach.

The considered alternative approach involving the minimum sum of Euclidean distances also resulted robust to overlaps and outliers, but the Jaccard mean has been observed, at least for the considered cases, to provide more stable identification of the center of the main groups.

A distance-limited version of the minimum sum of Euclidean distances and maximum Jaccard similarity have also been suggested and illustrated, with good potential for classification problems involving non-convex original groups.

The present work starts by describing the similaritybased methodology to classification, which is then illustrated respectively to an array of circularly-symmetric gaussian groups in presence of increasing overlap.

Methodology

The Jaccard similarity between a single scalar value x and a set S of scalar values y y y has been defined [START_REF] Da | Similarity means: Seeking for robustness to outliers[END_REF] in terms of the multiset (e.g. [START_REF] Da | Multisets[END_REF]) operations of union (max) and intersection (min) as follows:

J(x, y y y) = N i=1 min {x, y i } N i=1 max {x, y i } (1)
where N is the number of points in the set S (i.e. its size or cardinality) , M is the number of elements (features) of the vectors. All values are assumed to be positive.

In the case of x corresponding to a a single M × 1 vector [y 1 , y 2 , . . . , y M ]

T , and a respective set of N vectors organized in terms of an N × M matrix y, the above equation can be rewritten (as suggested in [START_REF] Da | Similarity means: Seeking for robustness to outliers[END_REF]) as:

J(x x x, y y y) = = N i=1 min {x 1 , y i,1 } + . . . + N i=1 min {x M , y i,M } N i=1 max {x 1 , y i,1 } + . . . + N i=1 max {x M , y i,M } = = M j=1 N i=1 min {x j , y i,j } M j=1 N i=1 max {x j , y i,j } (2)
with 0 ≤ J(x x x, y y y) ≤ 1. The two equations above provide a means for developing respective classification methods involving the comparison of one data elements with a set of other data elements.

In the following, we illustrate the application of these two similarity approaches respectively to the traditional and widely employed supervised classification method known as nearest neighbors (e.g. [START_REF] Duda | Pattern Classification[END_REF][START_REF] Fukunaga | Statistical Pattern Recognition[END_REF][START_REF] Koutrombas | Pattern Recognition[END_REF][START_REF] Da | Shape Classification and Analysis: Theory and Practice[END_REF]).

More specifically, we identify the classes of new elements by taking as result the category of the trained data element that yields not the minimum Euclidean distance, but the largest respective similarity.

Experiments: Symmetric Case

The potential of the suggested methodology is illustrated in this section respectively to an orthogonal array of circularly-symmetric gaussian clusters with increasing dispersions.

Figures 1 illustrates a set of such clusters for σ = 1 (a), as well as the classification results obtained by using the traditional nearest neighbor approach (b), as well as by using the Jaccard similarity. Observe that the clusters have been distributed with a positive translation in order to obtain a more symmetric similarity comparison (e.g. [START_REF] Da | Similarity means: Seeking for robustness to outliers[END_REF]).

Figure 2 presents the results obtained for increasing dispersions of the original clusters.

Remarkably stable clusters, which are also consistent with the original group distribution, have systematically been obtained in all cases by the similarity approach, while increasing intermixed groups have obtained as the dispersion, and therefore overlap, between the original groups increase.

Though the stability of the groups obtained by the nearest neighbor approach can be improved by considering more than 1 neighbor, it will still be markedly jagged, noisy, and likely to present discontinuities and/or incorrect group classifications, and to miss and/or merge groups, as illustrated in Figure 3 respectively to σ = 9 when considering K = 7 and 21 neighbors.

Figure 4 illustrates the application of the same classification methods as above respectively to a irregularly distributed original groups (with σ = 9), again with stable results.

It is also interesting to consider an alternative approach to the above considered methods, which adopted nearest neighbors, arithmetic mean, and similarity indices. This alternative approach corresponds to defining the mean of a set of values as corresponding to the value x that minimizes the sum of distances from itself to the points in the reference set. Interestingly, when applied to the same data sets considered above (as illustrated in Fig. 5), this approach has been verified to yield results which are comparable to those obtained by the Jaccard mean though, as indicated in the following section, tending to be less robust to the present of skewed secondary groups.

Yet another method related to the minimum sum of Euclidean distances can be obtained by substituting the similarity in Equation 2 by squares of coordinate differences (the square root does not need to be taken into account since we are aimed at identifying the minimum overall distance, which is the same for the Euclidean distance or its squared value). In other words, in a manner that is analogue to that adopted while expressing the overall similarity between a data element and a set of data elements, we replicate the former point and use it in a higher dimensional formula for the squared Euclidean distance, yielding:

D(x x x, y y y) = N i=1 (x 1 -y i,1 ) 2 + . . . + (x M -y i,M ) 2 (3)
Figure 6 exemplifies the application of this minimum overall Euclidean distance method to orthogonally distributed groups with σ = 5.

It can be readily verified that, unlike with the Jaccard similarity, this overall method does not yield satisfactory results even for this relatively moderate dispersion of the original points. This is a consequence of the geometry of the comparisons implemented by the Euclidean distance and Jaccard similarity (e.g. [START_REF] Da | Further generalizations of the Jaccard index[END_REF][START_REF] Da | On similarity[END_REF][START_REF] Da | Multiset neurons[END_REF]).

Several other similar classification methods considering combinations of distances and similarities between each data element and the data elements in the reference set can be conceived. For instance, it would be possible to maximize the sum of the pairwise similarities between the data element to each of the reference data elements, instead of taking the similarity in a higher dimensional space.

Experiments: Asymmetric Case

All data considered in the previous section involved symmetric distribution of points implied by the circularly symmetric dispersion characterizing each original group. This type of symmetry favors the stability of the position (e.g. center of mass) of the detected groups.

In the present section, we consider data with asymmetric distribution. More specifically, we will still resource to groups of normal distribution of points organized as an orthogonal lattice. However, small enough dispersion, implied by σ, is adopted so as to completely avoid any overlap between the groups. This is achieved by taking the distance L between adjacent points in the orthogonal grid to be much. larger than the groups dispersion as quantified by σ, i.e. L ≫ σ.

The comparison of the arithmetic and Jaccard means obtained for a set of uniformly distributed groups with σ = 3, but presenting overlap only with one of the 4neighbors between the group regions, is illustrated in Figure 7, which indicates greater accuracy of the latter approach at least for this particular case.

As in the previous section, comparable results have also been obtained by considering the total sum of distances instead of the k-closest distances. This tendency of the Jaccard mean and and the minimum sum of distances mean to present similar results is illustrated in Figure 8.

While both approaches are markedly robust to the outlier group, the Jaccard mean (obtained for maximum Jaccard similarity) resulted closer to the center of the larger group {10, 11, . . . , 15}, being therefore less susceptible from the influence of the secondary (smaller) group (see also [START_REF] Da | Similarity means: Seeking for robustness to outliers[END_REF]).

Non-Convex Patterns

In the case of data types more general than those used so far in the present work, it would be interesting to consider the maximum Jaccard similarity between each point to be classified respectively to a set of trained points within a distance-limited region(e.g. circular) around the former point, which would pave the way to classification of nonconvex groups of points. More specifically, only the data elements in the reference set that are closer than R to the compared data element are taken into consideration during the classification of each new point. This approach paves the way to more effective classification to be performed in the case of non-convex groups by adapting to the local convexity of the data distribution, therefore allowing more accurate results.

Figure 10 illustrates this possibility (with R = 22) respectively to the two categories (red and blue) of points distributed as shown in (a). Each of these groups was obtained by normally distributing points along a half section of a circle, with the two circles then being interleaved, therefore yielding an S-shaped separation border. The backbone around which the points belonging to the two categories have been distributed is shown in Figure 9(a), while the respectively expected separation border is presented in (b). (a) (b) (c)

Figure 6: Comparison of the Jaccard mean and the minimum Euclidean distances (in a higher dimensional space, in analogy to the similarity approach) respectively to the uniformly distributed normal groups with σ = 5. This method can be readily verified not to lead to satisfactory results as a consequence of the type of geometry underlying comparison by Euclidean distance.

The result of first nearest neighbor classification, presented in (b), yields a separation border that is highly jagged and noisy. The results obtained by the sum of distances and Jaccard similarity approaches, illustrated in (c) and (d) respectively, are comparable and substantially more accurate, smooth and stable than the result obtained with nearest neighbors.

Though the two classification methods considered in this section provide a good estimation of the separation border between the two groups, relatively small isolated 'islands' of incorrect classification(e.g. red region within the blue region) can appear as a consequence of unbalanced number of reference points taken in a specific similarity comparison. These regions can be potentially identified and removed by considering that the have much smaller area than the two largest one, and also by considering the fact that they do not include any of the original data elements having the same identified category.

Another interesting possibility to avoid the above mentioned isolated groups consists of weighting the overall similarity Equation 2 in order to be weighted by the respective number of points in the reference set, i.e.:

J(x x x, y y y) = N M j=1 N i=1 min {x j , y i,j } M j=1 N i=1 max {x j , y i,j } (4)
which, however, is no longer characterized by having 0 ≤ J(x x x, y y y) ≤ 1.

The possibility is illustrated in Figure 12(d) for R = 12, which resulted in two separated classification regions that are now fully convex. Observe that the groups are organized as an orthogonal lattices, but have small dispersion which is not enough to imply overlap (a). Asymmetric overlap is incorporated by changing the category of some of the points in each group by the category of one of its 4-adjacent neighbors in the respective orthogonal lattice structure. This type of overlap implies a substantial shift of the respective arithmetic mean (a) when compared to the Jaccard mean (b), which is substantially more robust to this type of asymmetry.

(a) (b) (c) Figure ?? depicts the maximum Jaccard similarity mean values obtained for each of the points in the considered domain. Observe the marked gap of similarity resulting between the two C-shaped groups, which has been obtained thanks to the selectivity of the adopted approach.

An alternative adaptation, when comparing between k reference groups, is to weight the above expression not by N , but by the relative mass probability P k given as:

P k =
number of elements in group k total number of elements in all groups [START_REF] Koutrombas | Pattern Recognition[END_REF] When formulated in this manner, the suggested criterion for deciding the category of a new data element while performing similarity-based comparison with the elements in the reference groups can be understood to have an analogy with Bayesian decision theory (e.g. [START_REF] Duda | Pattern Classification[END_REF][START_REF] Da | Shape Classification and Analysis: Theory and Practice[END_REF]).

Concluding Remarks

This work has reported a similarity-based approach to classification, which considers the recently described [START_REF] Da | Similarity means: Seeking for robustness to outliers[END_REF] concept of similarity between a value and a set of values, here extended to take into account multidimensional data elements (feature vectors).

The obtained results, obtained respectively to the traditional nearest neighbor method as well as a respectively adaptation to similarity value, support the potential of the proposed approach to provide groups that are stable and consistent with the original data even in presence of intense overlap between the groups.

The alternative approach of considering the minimum sum of distances from a point to a set of points has been found to yield results comparable to those obtained by the Jaccard similarity, though the latter approach has also been verified, at least for the considered cases, to allow a more stable characterization of the groups and respective centers.

The possibility to constrain the minimum sum of Eu- clidean distances and maximum Jaccard similarity has also been described as a means to more effectively classify data involving non-convex groups. This approach has been verified to allow noticeable performance in the case of two interleaved concave groups. Enhanced results are expected to be obtained by using the coincidence similarity.

The described developments and results are respective to the adopted data sets and parameter configurations. Additional further evaluation of the proposed methodology is required respectively to other types of data, overlaps, dimensions, and parameter configurations, among other possibilities.

The encouraging described results pave the way to several further applications of the concept of the similarity between a vector and a set of vectors to many other problems in pattern recognition and deep learning (e.g. [START_REF] Hinton | Training products of experts by minimizing contrastive divergence[END_REF][START_REF] Schmidhuber | Deep learning in neural networks:an overview[END_REF]), including other supervised and nonsupervised (clustering) methods and applications. An-other promising research venue consists of adapting the concepts and methods described in the current work to classify nodes in respective complex networks, which can lead to new methods for community detection and identification of the origin of spreading dynamics in complex networks (e.g. [START_REF] Comin | Identifying the starting point of a spreading process in complex networks[END_REF]). net/publication/371852653_Similarity_Means_ Seeking_for_Robustness_to_Outliers, 2023.

Figure 1 :

 1 Figure 1: The original set of clusters (a), each with standard deviation σ = 3, as well as the classification results obtained by using the traditional nearest neighbor method (b) and the Jaccard similarity approach described in the present work (c).

Figure 2 :

 2 Figure2: Results obtained for increasing dispersions σ = 3, 5, 7 and 9 by using traditional nearest neighbor method method (second column) as well as the and the Jaccard similarity approach described in the present work (third column).

Figure 3 :

 3 Figure 3: The result of classification respective to σ = 9 with the nearest neighbor method considering 7 and 21 neighbors instead of 1 neighbor. The black dots in (c) indicate the center of mass of the respective original groups.

Figure 4 :

 4 Figure 4: The result of classification respective to irregularly distributed original groups with σ = 9. The black dots in (c) indicate the center of mass of the respective original groups.

Figure 5 :

 5 Figure 5: Comparison of the Jaccard mean and the minimum sum of Euclidean distances respectively to the uniformly distributed normal groups with σ = 7. Both approaches result markedly robust to the overlaps. Further enhanced robustness has been verified when adopting the coincidence similarity index [6].

Figure 7 :

 7 Figure 7: A uniform distribution of groups with σ = 3 (a) and the respective arithmetic means (centers of mass) (b) and Jaccard means (c).Observe that the groups are organized as an orthogonal lattices, but have small dispersion which is not enough to imply overlap (a). Asymmetric overlap is incorporated by changing the category of some of the points in each group by the category of one of its 4-adjacent neighbors in the respective orthogonal lattice structure. This type of overlap implies a substantial shift of the respective arithmetic mean (a) when compared to the Jaccard mean (b), which is substantially more robust to this type of asymmetry.

Figure 8 :

 8 Figure 8: Comparison of the Jaccard mean and the minimum sum of Euclidean distances mean respectively to a data containing a cluster of equally spaces points, namely the set {10, 11, . . . , 15} together with three outlier points {1, 2, 3}. The sum of Euclidean distances and the Jaccard similarity values are shown in green and salmon, respectively, with their extreme being identified by a respective point.

Figure 9 :

 9 Figure 9: Backboned around which the two categories have been distributed in order to generate the data sets considered for classification in the current section. The respectively expected separation region is shown in (b).

Figure 10 :

 10 Figure 10: Comparison of the classification methods based on first nearest neighbor (b), minimum sums of distances (c) and maximum Jaccard similarity (c) respectively to the supervised classification while taking into account the two groups (red and blue) in (a). The two latter methods considered R = 22.

Figure 11 :

 11 Figure 11: Comparison of the classification methods based on first nearest neighbor (b), minimum sums of distances (c) and maximum weighted Jaccard similarity (c) respectively to the supervised classification while taking into account the two groups (red and blue) in (a).Fully convex classification regions can now be observed and the identified separation border also resulted more similar to that implied by the original backbone in Fig.9. The two latter methods considered R = 12.

Figure 12 :

 12 Figure 12: The maximum similarity mean values obtained respectively to the classification result shown in Fig. 12(d).

Acknowledgments Luciano da F. Costa thanks CNPq (grant no. 307085/2018-0) and FAPESP (grant 15/22308-2).

Observations

As all other preprints by the author, the present work contains preliminary work subject to further revision and validation. Respective modification, commercial use, or distribution of any of its parts are not possible, as this work has author copyright. Many of the preprints by the author are also available in Hal and/or arXiv. This work can also be cited by using the DOI number or article identification link. It is also interesting to check for new versions of this work, as they may become available. Thanks for reading.


Mauro Caporuscio

Pierre-Guillaume Raverdy

Hassine Moungla

Valerie Issarny

ubiSOAP: A Service Oriented Middleware for Seamless Networking

The computing and networking capacities of today's wireless portable devices allow for pervasive services, which are seamlessly networked. Indeed, wireless handheld devices now embed the necessary resources to act as both service clients and providers. However, the seamless networking of services remains challenged by the inherent mobility and resource constraints of devices, which make services a priori highly volatile. This paper discusses the design, implementation and experimentation of the ubiSOAP service-oriented middleware, which leverages wireless networking capacities to effectively enable the seamless networking of services. ubiSOAP specifically defines a layered communication middleware that underlies standard SOAP-based middleware, hence supporting legacy services while exploiting nowadays pervasive connectivity.

Introduction

With network connectivity being embedded in most computing devices, networking environments are now pervasive. As a result, any networked device may seamlessly consume but also provide software applications over the network. Service-Oriented Computing (SOC) then introduces natural design abstractions to deal with pervasive networking environments [START_REF] Bellur | Towards service orientation in pervasive computing systems[END_REF]. Indeed, networked software applications may conveniently be abstracted as autonomous loosely coupled services, which may be combined to accomplish complex tasks. In addition, the concrete instantiation of SOC paradigms provided by Web Services (WS) technologies by means of Web-based/XML-based open standards (e.g. WSDL, UDDI, HTTP, SOAP) may be exploited for concrete implementation of pervasive services. However, while Web services standards and implementations targeting wide-area domains are effective technologies, supporting Web service access in pervasive networking environments is still challenging. In such kind of networking environments, mobile applications, acting as both service consumers and providers, often run on scarce resource platforms such as personal digital assistants and mobile phones, which have limited CPU power, memory, and battery life. Moreover, these devices are usually interconnected through one or more heterogeneous wireless links, which compared to wired networks are characterized by lower bandwidths, higher error rates, and frequent disconnections. The former issue has led to the introduction of lightweight middleware enabling base WS-oriented communication patterns among wireless portable devices (i.e., SOAP-based messaging and dynamic service discovery) [START_REF] Issarny | Developing ambient intelligence systems: A solution based on Web services[END_REF][START_REF] Aijaz | Towards peer-to-peer long lived mobile Web services[END_REF]. The latter issue has further led to examine alternative SOAP transports [START_REF] Gehlen | Mobile Web service communication over UDP[END_REF]. However, a key feature of pervasive networking environments is the diversity of radio links available on portable devices, which may be exploited towards seamless connectivity. Specifically, as nodes get connected via multiple radio links, thorough scheduling and handover across those links allow enhancing overall connectivity and actually making it seamless [START_REF] Wang | Policy-enabled handoffs across heterogeneous wireless networks[END_REF][START_REF] Qureshi | Horde: separating network striping policy from mechanism[END_REF][START_REF] Sorber | Turducken: hierarchical power management for mobile devices[END_REF]. This calls for making services network-agnostic [START_REF] Su | Haggle: Seamless networking for mobile applications[END_REF], so that the underlying middleware takes care of scheduling exchanged messages over the embedded links in a way that best matches Quality of Service (QoS) requirements [START_REF] Charlet | Energy-efficient middleware-layer multi-radio networking: An assessment in the area of service discovery[END_REF], and further ensures service continuity through vertical handover [START_REF] Huang | Improving TCP performance during soft vertical handoff[END_REF]. In this setting, a primary requirement for supporting service-oriented middleware is to provide a comprehensive networking abstraction that allows applications to be unaware of the actual underlying networks while still exploiting their diversities in terms of both functional and extra-functional properties.

This paper introduces the ubiSOAP communication middleware, which underlies SOAP-based middleware and strives to provide pervasive networking to services. Specifically, ubiSOAP defines a two-layer architecture composed of a multi-radio networking layer and a WS-oriented communication layer, which respectively provide network-agnostic connectivity and SOAP-based unicast and group communication in pervasive networking environments. The design rationale for ubiSOAP is further discussed in the next section, while Section 3 details its core constituents. Then, Sections 4 and 5 assess the proposed middleware, discussing respectively ubiSOAP usage for implementing an advanced middleware service (i.e., pervasive service discovery), and ubiSOAP performance based on experiment. Finally, Section 6 concludes with a summary of our contribution with respect to related work, and our perspectives for future work.

Design Rationale

With the drastic evolution of wireless technologies, software services can become truly pervasive, being not solely accessed but also hosted by wirelessly networked portable devices. As a result, legacy applications can become available anytime, anywhere, but also revisited to take full advantage of pervasive networking. Further, new application services may emerge, in particular based on the nomadic feature and ad hoc connectivity of wireless portable devices, as exemplified by emergency rescue scenarios, where mobile portable hosts serve sensing the environment and coordinating rescue actions. Still, enabling pervasive service provisioning on mobile hosts requires special care, as resources are far more constrained than resource-rich Internet servers originally targeted by service oriented computing and its Web Service instantiation. Further, the mobility of wireless hosts requires special attention. Indeed, early solutions introduced towards nomadic computing targeted service hosts with which connectivity can eventually be restored, while this cannot be assumed in general when services are hosted by mobile devices that connect in an ad hoc way [START_REF] Zarras | Engineering reconfigurable distributed software systems: Issues arising for pervasive computing[END_REF]. Overcoming resource constraints of wireless devices in the support of Web services has led to the introduction of custom SOAP engines, among which the open source iCSOAP engine from INRIA, which was developed as part of the WSAMI middleware1 featuring Web services for ambient intelligence [START_REF] Issarny | Developing ambient intelligence systems: A solution based on Web services[END_REF].

Regarding mobility issues, portable devices now embed multiple radio interfaces, which may be combined to bring seamless networking to mobile applications [START_REF] Su | Haggle: Seamless networking for mobile applications[END_REF]. Specifically, embedded networking technologies differ from several respects, among which range, latency, bandwidth, energy consumption, financial cost, availability and so on. Therefore, the scheduling of communications over embedded interfaces according to application requirements can significantly increase the overall QoS. The collection of wireless technologies may in particular be considered as hierarchical wireless overlay networks, which are structured according to respective coverage [START_REF] Katz | The case for wireless overlay networks[END_REF]. Then, the interface used for communication may simply depend on the location of the target host. However, different network parameters must be taken into account in the scheduling of communications, so as to meet applications' QoS requirements, while optimizing the overall resource usage [START_REF] Qureshi | Horde: separating network striping policy from mechanism[END_REF]. In particular, saving energy is critical for enhanced autonomy of hosts and thus requires selecting as far as possible the network interface that consumes the least energy among those eligible [START_REF] Sorber | Turducken: hierarchical power management for mobile devices[END_REF][START_REF] Charlet | Energy-efficient middleware-layer multi-radio networking: An assessment in the area of service discovery[END_REF]. Further, vertical handover across heterogeneous wireless networks must be supported so as to maintain connectivity with nodes despite their mobility across networks [START_REF] Wang | Policy-enabled handoffs across heterogeneous wireless networks[END_REF], and thus bring seamless connectivity to/from mobile nodes.

Among one of its major goals, the ubiSOAP communication middleware aims at effectively using the diverse networking technologies in the handling of serviceoriented communication, hence offering network-agnostic connectivity to/from nodes. As discussed above, this requires addressing a number of critical issues such as network availability, user and application QoS requirements and vertical handover. The latter issue is particularly important with respect to the service continuity requirement. In fact, when switching from a given network to one of a different type, the device is required to change its status according to the new environment it is entering. Indeed, changing the device's status affects also the status of all the devices that are currently interacting with it. Specifically, in an all-IP networking environment, the IP address meaning is twofold: end point identification (i.e., an IP address uniquely identifies a host in a given network) and location identification (i.e., the network in which the host is located). Hence, when a host changes its point of attachment (vertical handover between two networks), the IP address must be modified (i.e., the internal status) accordingly in order to route packets to the new network. Then, since the IP address is the base of any application-layer connection, all the ongoing connections break (i.e., the handover affects the status of the interacting parties). Furthermore, as devices can bind various networks at the same time, two interacting parties might communicate through multiple paths. Hence, choosing the best connection path to serve a given interaction is a key issue to deal with in pervasive networks, as this significantly affects the QoS at large (e.g., availability, performance with respect to both resource consumption and response time, security) [START_REF] Caporuscio | Energetic performance of service-oriented multi-radio networks: issues and perspectives[END_REF].

Multi-radio connectivity further allows deploying bridges in the network, effectively realizing a multi-network service overlay [START_REF] Grace | Addressing network heterogeneity in pervasive application environments[END_REF]. Specifically, resource-rich nodes (e.g., laptops or even reachable stationary nodes) that embed multiple radio interfaces may act as bridges that route messages across heterogeneous networks. Such a feature is beneficial for pervasive services, enabling to overcome the resource limitation and mobility of nodes and contributing to achieve seamless service connectivity. Indeed, this allows energy-limited devices to use the least consuming interface while being able to reach all the devices of the overlay. Further, a networked service that changes physical network following host mobility may still be reachable in the overlay.

Another of our goals for ubiSOAP is to support legacy Web services and thus transparently bring the added value of today's pervasive networking environments to existing services. This has in particular led us to layer ubiSOAP as a specific transport for SOAP engines (e.g., Axis2, iCSOAP) and to leverage WS-addressing to integrate multi-radio, multi-network connectivity in SOAP headers. In this context, it is crucial to examine carefully the performance of SOAP transports. In particular, it has been shown that the performance of default SOAP over HTTP is poor in wireless environments, further leading to study alternative transports such as TCP and UDP [START_REF] Lai | Efficient SOAP binding for mobile web services[END_REF][START_REF] Gehlen | Mobile Web service communication over UDP[END_REF]. While SOAP over UDP clearly offers the best response time, SOAP over TCP has the advantage of built-in reliability and is further suitable for applications with short requests. ubiSOAP thus realizes SOAP-over-TCP unicast messaging as a tradeoffs solution, while integrating SOAP over UDP is an area for future work. Still, another SOAP transport that is of much interest for pervasive networking environments is multicast group communication. Indeed, group-based interactions are central in a number of pervasive computing scenarios, due to the user-centric nature of pervasive computing and the innate group interaction skills of people [START_REF] Grudin | Group dynamics and ubiquitous computing[END_REF][START_REF] Wang | Supporting persistent social groups in ubiquitous computing environments using context-aware ephemeral group service[END_REF]. ubiSOAP thus features a base SOAP transport for group communication.

ubiSOAP Middleware for Pervasive Services

Following the above discussion, the architecture of ubiSOAP layers the following constituents below SOAP-based middleware functionalities (see Fig. 1): (i) multi-radio networking provides network-agnostic connectivity (see § 3.1), (ii) multi-network routing implements a multi-network overlay (see § 3.2), and (iii) point-to-point and group transports leverage multi-radio, multi-network message routing, and further introduce communication primitives targeted at pervasive computing systems (see § 3.3).

Network-Agnostic Service Connectivity

The multi-radio networking layer of ubiSOAP provides core functionalities to effectively manage multi-radio connectivity by providing: (i) a network-agnostic addressing scheme together with (ii) QoS-aware network link selection. Network-agnostic addressing. Devices embedding multiple network interfaces may have multiple IP addresses, at least one for each active interface. Thus, in order to identify uniquely a given application in the network we associate to it a Multi-Radio Network Address (MRN@). The MRN@ of an application instance is specifically the application's Unique ID, which resolves into the actual set of IP addresses (precisely, network ID ⊕ IP addresses) bound to the device (at a given time) that runs the given instance (see Fig. 2). Then, upper layers shall use MRN@ as part of their addressing scheme (e.g., through WS-addressing in the case of Web services), which replaces the traditional IP-based addressing scheme. MRN@s are automatically generated and managed by the multi-radio networking layer. Furthermore, the multi-radio networking layer allows for performing a lookup operation that, starting from an MRN@, returns the set of IP addresses actually bound to it. The basic operations provided by the multiradio networking layer are as follows. First, Registration allows the application to register within the multi-radio networking layer and generates the MRN@ that uniquely identifies it. In particular, the user application provides as input an identifier (locally unique), which is used to generate the MRN@ to be returned. Then, Lookup allows user applications to retrieve the actual set of IP addresses related to a given MRN@. If the resolution of MRN@ is not cached or needs to be updated, a request is multicasted to all the networks currently accessible and, if the device related to such MRN@ is reached, it will directly reply to the requester by supplying the actual set of IP addresses. Base unicast and multicast communication schemes are provided on top of MRN@ networkagnostic addressing: (i) Synchronous unicast is provided by means of a packet input/output stream that is used to read/write packets to be exchanged during the interaction between client and server applications; and (ii) Asynchronous multicast allows the user application to send multicast packets to all members of a given group.

QoS-aware interface activation and network selection.

Next to MRN@ addressing, it is crucial to activate and select the best possible networks (among Fig. 2. ubiSOAP multi-radio multi-network connectivity using MRN@ and bridging those available) with respect to required QoS. Interface activation allows the user application to activate the best possible interfaces (among those available) with respect to the required QoS. In particular, the application submits its QoS requirement (specified as set of pairs < QoS attribute , QoS value >) to the multiradio networking layer, which in turn compares it with the QoS of each available interface. In this case, since the interface is switched off, QoS refers to the theoretic values of a network interface declared by the manufacturer (e.g., GPRS maximum bitrate = 171.2Kb/s). If the interface satisfies the requirement posed by the application, within a given approximation expressed in percentage, it is activated. It is also possible to define priorities upon the various quantitative parameters, in order to specify if a given parameter is more important than the others. Network selection is performed during the establishment of the communication and takes into account the QoS attributes required by the client application that is initiating the connection, as well as the networks active on the server listening for incoming connections, as given by the server's MRN@. If the client and the server share only one network that satisfies the requirements, it is used to carry on the interaction. On the other hand, when the two parties share more than one network, the selection algorithm selects the one that best meets the required QoS.

Multi-network Service Overlay

Thanks to the ubiSOAP multi-radio networking layer, communication among nodes exploits the various network links that the nodes have in common, further selecting the link that provides the required QoS. However, in some cases, it might also be desirable for nodes to be able to access services that are hosted in networks that the requesting node is not directly connected to (e.g., to provide continuity of service despite node mobility). For this purpose, ubiSOAP introduces an overlay network that bridges heterogeneous networks, thus enhancing overall service connectivity. Specifically, nodes that are connected to two (or more) different networks through their network interfaces can assume the role of bridge nodes. Bridge nodes quite literally "bridge" between two separate networks, relaying point-to-point and multicast ubiSOAP messages across those networks. Still, we assume that nodes will not request services that would require the consecutive traversal of more than five wireless networks (see [START_REF] Gupta | The capacity of wireless networks[END_REF][START_REF] Li | Capacity of ad hoc wireless networks[END_REF] for a detailed analysis on wireless communication) in order to access them.

Multi-network point-to-point routing.

In ubiSOAP multi-network, multiradio environments, the network ID ⊕ IP address embedded in the MRN@ of a host contains, along with the network address of the service host, the network ID that uniquely identifies the network (e.g., a BSSID, MAC address of the Bluetooth master, etc.) that the host resides in under its given address. For instance, in Fig. 2, the of device Alice is connected to networks a, i, and n, through its various network interfaces. Clearly, the device can trivially access services hosted in these networks. However, in order to access services hosted in the distant networks x, y, and z, the device has to route its request through an appropriate bridge node (i.e., Bridges A, B and C, noting that each bridge node is displayed in each network it is part of). To achieve effective routing across bridges, we propose a straightforward approach based on the principle of Mobile Ad hoc NETwork (MANET) routing. In this approach, bridge nodes advertise their presence to the nodes in their corresponding networks and exchange routing information. For this purpose, bridge nodes run an instance of OLSR [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF] among each other. Instead of concrete node addresses, however, bridges store as destinations the identifiers of the various present networks (i.e., network ID) and as next hop the bridge that needs to be contacted next to eventually reach the target network. Being a proactive routing protocol, this inter-bridge OLSR instance gives each bridge the required routing information to reach all connected networks. Whenever a non-bridge node wants to access a service outside one of the networks it is itself connected to, it may simply route the request to any bridge of choice that will then forward the request accordingly. As mentioned above, bridge nodes periodically advertise their presence to the nodes in their respective networks. As a further optimization, bridge nodes may include in their advertisements their OLSR routing tables so that non-bridge nodes may choose bridge nodes according to metrics such as network hops, etc.

Multi-network multicast routing. It is crucial to support both point-to-point and group interactions in the multi-radio, multi-network environment. In particular, multicasting is central to advanced middleware services like dynamic discovery [START_REF] Zhu | Service discovery in pervasive computing environments[END_REF]. We thus introduce multi-network multicast routing, building upon multicast facilities of the composed networks. The base principles of the ubiSOAP multi-network multicast routing are depicted in Fig. 3; multicast routing is such that within an IP network, the network's multicast facility (i.e., IP multicast or higher level group communication like Java Groups) is used for communication among group members. Then, multicast messages are forwarded by ubiSOAP bridges up to a fixed number of hops (i.e., 5 as discussed previously), while avoiding cycles and duplication. The ubiSOAP multi-network routing facility enables the definition of application-level groups. Specifically, application-level groups are individually managed at the ubiSOAP middleware layer while a single ubiSOAP multi-network group is managed in the network layer. The latter is actually a composition of ubiSOAP multicast groups, one for each of the composed networks.

Custom SOAP Transports for Pervasive Services

In order to leverage the provided multi-radio, multi-network service connectivity, ubiSOAP introduces custom SOAP transports. Specifically: (i) the provided SOAP transport for point-to-point communication brings multi-radio multinetwork routing to legacy SOAP messaging, while (ii) the SOAP transport for group communication enhances the SOAP API to meet the corresponding base requirement of pervasive networking environments [START_REF] Kindberg | System software for ubiquitous computing[END_REF][START_REF] Grudin | Group dynamics and ubiquitous computing[END_REF][START_REF] Gehlen | Mobile Web service communication over UDP[END_REF][START_REF] Wang | Supporting persistent social groups in ubiquitous computing environments using context-aware ephemeral group service[END_REF][START_REF] Zhu | Service discovery in pervasive computing environments[END_REF].

Point-to-point communication.

The ubiSOAP point-to-point transport is a connection-oriented transport for supporting communication between a client and a service. This transport interacts with the multi-radio networking layer to send and receive messages over the network based on the MRN@ that identifies the remote party. It also interacts with the SOAP engine or the client SOAP library to receive or dispatch SOAP messages locally. When sending a message, the ubiSOAP point-to-point transport must first evaluate if the destination is directly reachable (i.e., the MRN@ of the sender and of the destination share a common network). If true, the message is then sent directly to the destination. If not, the transport retrieves the MRN@ of a ubiSOAP bridge directly reachable, encapsulates as plain data the application's SOAP message into a specific forwarding message, and sends this forwarding message to the bridge. This message is forwarded between bridges until it reaches the destination where the application's SOAP message is extracted and dispatched. While the client blocks until the response is received, the forwarding message is routed between ubiSOAP bridges using connectionless communication. The response message may thus follow a different route. The first bridge returns the response to the client, or terminates the connection after a given timeout.

On the service side, the ubiSOAP point-to-point transport interacts with the SOAP engine to deliver the message to the appropriate service. For messages that have been routed by bridges, the destination must extract the actual SOAP message, and also set up properly the SOAP message parameters URL of the service, action to perform). This is achieved by storing (on the source side) and retrieving (on the destination side) the relevant information in the ubiSOAP header of the SOAP message. In particular, the set of IP addresses associated to an MRN@ is embedded in the header of request (for the client) and response (for the service) messages. This enables communicating devices in different networks to keep track of mobile nodes and maintain sessions (as long as a communication path exists). In some cases however (i.e., when both the client and the service simultaneously change the complete set of IP addresses associated to their MRN@), and no direct link exists), the session will close and the client will need to perform a service discovery (See Section X) to find the same service again and restart the communication.

Group communication.

The ubiSOAP group transport is a connectionless transport for one-way communication between multiple peers in multi-network configurations. The ubiSOAP group transport component interacts with the multi-radio networking layer to send group messages based on an MRN@ identifying the group, and with the SOAP engine to deliver the group's messages to the registered services. As noted above, groups are identified with an MRN@. Multicast-based applications usually assume that all group members agree beforehand on a specific IP address for the group. We therefore also assume that all group members use the same MRN@ for the group. While services are not able to directly return a result to a client (one-way multicast), a service may send a message (one-way unicast) on the group directed at a specific peer (i.e., similar to the sendTo socket call). As group communication in the underlying multiradio networking layer is multicast-based, it does not guarantee the ordering or the delivery of messages. While ordering may be easily achieved on the receiving side, the overhead to provide group reliability is deemed too costly due to the dynamics of pervasive networks. Also, while many mobile devices may run the same collaborative application, a user may only be interested in interacting with the ones at its location. Such scoping may be achieved by limiting the forwarding of group's messages or by adding forwarding constraints.

ubiSOAP in Action: Pervasive Service Discovery

ubiSOAP is being developed as part of a larger initiative on assisting the development of dependable services for pervasive networking environments, which is undertaken by the European IST PLASTIC project 2 . The PLASTIC project specifically investigates the development of the PLASTIC platform, decomposing into a development environment, service-oriented middleware and validation framework for the target pervasive services. ubiSOAP then defines the PLAS-TIC core middleware while advanced middleware services are being developed on top of it to address the requirements of pervasive networking (i.e., dynamic service discovery and composition, security and context management). Further, the PLASTIC platform is being assessed against actual case studies in the area of eHealth, eLearning, eBusiness and eVoting. This in particular allows us to extensively experiment with the ubiSOAP middleware. In this section, we focus on one use of ubiSOAP that is realizing dynamic discovery of pervasive services, which benefits from all the advanced features of ubiSOAP, i.e., group communication, and multi-radio, multi-network message routing.

Service discovery is an essential function of SOC as it enables the runtime association to the networked services. Three basic roles are identified for service discovery: (i) Service provider is the role assumed by a software entity offering a networked service; (ii) Service requester is the role of an entity seeking to consume a specific service; (iii) Service repository is the role of an entity maintaining information on available services and a way to access them. A service description formalism or language to describe the functional and non-functional properties (such as QoS, security or transactional aspects of networked services) complemented with a service discovery protocol enables service providers, requesters and repositories to interact with each other. Many academic and industry supported SDPs have already been proposed and leading SDPs in dynamic environments use a pull-based approach (SLP, WS-Discovery, Jini, SSDP), often supporting both the centralized and distributed modes of interaction: clients send requests to service providers (distributed pull-based mode) or to a thirdparty repository (centralized pull-based mode) in order to get a list of services compatible with the request attributes.

Building on the tremendous number of proposed service discovery protocols and accounting for the specifics of pervasive computing [START_REF] Zhu | Service discovery in pervasive computing environments[END_REF], we introduce a Pervasive Service Discovery (PSD) Service that provides dynamic, interoperable, context-aware service discovery. PSD is mainly a reengineering of the open source MUSDAC multi-protocol service discovery platform3 [START_REF] Raverdy | Efficient context-aware service discovery in multi-protocol pervasive environments[END_REF] on top of ubiSOAP in order to support service discovery in multi-radio, multi-network environments. PSD uses a hierarchical approach for service discovery in multi-network environments (see Fig. 4). Indeed, a (logically) centralized repository (PSD-S) coordinates service discovery within an independent network, while PSD-Ss in different networks communicate together in a fully distributed way to disseminate service information. While in MUSDAC service discovery and access were tightly integrated, PSD-Ss are only concerned with service discovery, and rely on ubiSOAP group communication to disseminate service information across networks. Changes in the multi-network topology (e.g., broken propagation paths) are then taken care of transparently. PSD-Ss (see Fig. 4) provide an explicit API supported by the PSD plugin that enables clients (resp. providers) in a network to discover (resp. advertise) a service in the multi-network environment. It further enables clients and providers to benefit from advanced discovery features (e.g., context-awareness) by directly issuing requests or advertisements in the PSDL format. Specific legacy SDP plugins register with the active SDPs in the network, and translate requests and advertisements in legacy formats to PSDL (e.g., SLP and UPnP in Fig. 4), which are stored in the PSD repository. The matching engine then combines various matching algorithms [START_REF] Mokhtar | Interoperable semantic & syntactic service matching for ambient computing environments[END_REF] to support the various elements of the service description (for both requests and advertisements), and thus provides comprehensive interoperability between SDPs. Finally, the dissemination manager controls the dissemination of local requests and the compilation of the results returned by distant PSD-Ss, while the location tracker collaborates with lower-level services in the ubiSOAP middleware to maintain the physical address of mobile services discovered in the environment.

As described above, the PSD repository stores PSDL service descriptions that are either generated by legacy SDP plugins (e.g., UPnP2PSD plugin) or directly registered by service providers using the PSD plugin. We use a hierarchical service description format that actually combines a number of distinct documents specifying different facets of the service. The PSDL description acts primarily as a top-level container for additional files describing facets of the service. For example, a WSDL document may be used to describe the service interface while non-functional properties can be described using existing QoS and context models. The ubiSOAP grounding of host, that identifies the networks and IP address at which the service's host is network-reachable (i.e., MRN@ and mapping) is described in such separate document thus facilitating dynamic updates.

Experimentation

We have implemented a prototype of the ubiSOAP middleware using Java for both desktop (J2SE) and mobile (J2ME CDC) environments. As mentioned previously, the ubiSOAP prototype is being extensively experimented with as part of the PLASTIC project, and has been released under open source license4 . To assess the efficiency of the ubiSOAP middleware, we evaluate the processing time to call a simple Echo Web service under various network configurations. We evaluate both the time required to call the Web service the first time, which includes the dynamic service creation/instantiation, and the time required to call the Web service after it is deployed. Tests are performed on a Windows XP PC with a 2.6GHz processor and 1 GB of memory for the desktop platform, and on shows that the time taken for service instantiation far exceeds the one of calls. The response time of ubiSOAP is further slightly higher than the one of HTTP, which is due to the management of MRN@ whose processing gets noticeable due to the fact that the communication is local. Configuration b) then demonstrates that ubiSOAP outperforms HTTP by about 25% at instantiation time. This is explained by the fact that the processing overhead (header and session management) is much lighter in ubiSOAP, and the difference in processing is emphasized by the limited capacities of the devices (slow task switching, memory access, ...). As shown by Configuration c), in the case where the service provider runs on the desktop, HTTP performance for instantiation is slightly better, because the difference in the management of session is negligible on the desktop, while ubiSOAP on the desktop adds the cost of MRN@ resolution through multicast. On the other hand, the ubiSOAP performance for calls is better, again due to lightweight session management on the client side and the fact that the MRN@ needs only to be resolved at the first call. Finally, Configuration d) aggregates the above results b) and c), showing the enhanced performance of ubiSOAP over HTTP when both client and service provider run on a PDA.

Figure 5.e) complements the above measures by showing the performance of wireless communications between PDAs using both WiFi and Bluetooth. The higher bandwidth of WiFi makes it obviously better positioned for handling communication compared to Bluetooth, even for small size messages. However, this takes into account performance only, while other criteria are of relevance like power consumption [START_REF] Charlet | Energy-efficient middleware-layer multi-radio networking: An assessment in the area of service discovery[END_REF], as addressed by the QoS-aware network selection realized by the ubiSOAP multi-radio networking layer. Although the theoretical bandwidth for Bluetooth and WiFi is significantly different, the actual bandwidth available to applications depends on the hardware, drivers, and, in our case, the Java JVM ability to cope with the load. As demonstrated in the experiments, the actual bandwidth for Java applications on PDA is almost identical for Bluetooth and WiFi.

In general, the scheduling of communication over network interfaces shall account for the QoS requirements of networked applications. Such requirement and specifically conflicts between different applications should be taken into account when activating/desactivating network interfaces or performing handover. We thus have implemented a version of ubiSOAP, which deals with coordinated usage of the network interfaces, so that the actual network used for communication is selected according to the applications that are currently run. Specifically, a daemon process is introduced, which coordinates the usage of the network interfaces. However, such a solution suffers from the resource availability of PDAs that is still currently limited, and accommodates poorly the concurrent execution of applications. Indeed, as shown by results of Figure 5.f) that provides the response time of ubiSOAP with the daemon running, while the overhead on the desktop is reasonable, it increases dramatically when performed on the PDA due to the constant process switching.

Conclusion

Service-oriented computing appears as a promising paradigm for pervasive computing systems that shall seamlessly integrate the functionalities offered by networked resources, both mobile and stationary, both resource-rich and resource-constrained. In particular, the loose coupling of services makes the paradigm much appropriate for wireless, mobile environments that are highly dynamic. However, enabling service-oriented computing in pervasive networking environments raises key challenges among which overcoming resource constraints and volatility of wireless, mobile devices. This has in particular to introduce lightweight service-oriented middleware [START_REF] Issarny | Developing ambient intelligence systems: A solution based on Web services[END_REF][START_REF] Bellur | Towards service orientation in pervasive computing systems[END_REF][START_REF] Aijaz | Towards peer-to-peer long lived mobile Web services[END_REF][START_REF] Mokhtar | Easy: Efficient semantic service discovery in pervasive computing environments with QoS and context support[END_REF]. However, to the best of our knowledge, none of the existing solutions comprehensively integrate the full capacity of today's pervasive networking environments, which allow wireless devices to interact via multiple network paths. Such a feature actually enables seamless networking and in particular overcoming the nodes' mobility through vertical handover across networks. This further allows for tuning network usage according to application requirements, and thus enhancing overall QoS.

Exploiting multi-radio connectivity has led to the definition of various algorithms for optimizing the scheduling of communications over multiple radio interfaces, e.g., [START_REF] Katz | The case for wireless overlay networks[END_REF][START_REF] Wang | Policy-enabled handoffs across heterogeneous wireless networks[END_REF][START_REF] Qureshi | Horde: separating network striping policy from mechanism[END_REF][START_REF] Sorber | Turducken: hierarchical power management for mobile devices[END_REF][START_REF] Charlet | Energy-efficient middleware-layer multi-radio networking: An assessment in the area of service discovery[END_REF]. Building on this effort, this paper has introduced ubiSOAP, which implements SOAP transports that leverage multi-radio, multi-network connectivity and may be coupled with lightweight engines like iCSOAP [START_REF] Issarny | Developing ambient intelligence systems: A solution based on Web services[END_REF]. As a result ubiSOAP enables the seamless networking of Web services that may be deployed on various devices, including mobile devices like today's smart phones embedding multiple radio interfaces. ubiSOAP is now being extensively experimented as part of the PLASTIC European project, being the basis for the development of various pervasive services, ranging from middleware-layer pervasive service discovery to application-layer services in the area of eBusiness, eHealth, eLearning and eVoting. Experiment further shows that the performance of ubiSOAP are in general better than default SOAPover-HTTP transport, thanks to lightweight session management.

Our current work relates to the aforementioned experimentation of ubiSOAP for thorough assessment prior to its release under open source license. Our future work relates to further evolution of ubiSOAP to meet the numerous requirements of pervasive computing. Part of this effort lies in introducing additional SOAP transports, like an UDP-based one, which significantly improves response time, while affecting reliability [START_REF] Lai | Efficient SOAP binding for mobile web services[END_REF]. Obviously, ubiSOAP needs to be complemented with a number of middleware services to deal with QoS; such an issue is addressed as part of the PLASTIC project where middleware solutions for security and context awareness are being investigated. We are also examining the coupling with semantic-based solutions to enable more precise, yet more flexible, descriptions of pervasive services, as introduced in, e.g., [START_REF] Mokhtar | Easy: Efficient semantic service discovery in pervasive computing environments with QoS and context support[END_REF].

Fig. 1 .

 1 Fig. 1. ubiSOAP software architecture

Fig. 3 .

 3 Fig. 3. ubiSOAP multi-network multicast routing

Fig. 4 .

 4 Fig. 4. Pervasive Service Discovery

Fig. 5 .

 5 Fig. 5. ubiSOAP performance

http://www-rocq.inria.fr/arles/download/ozone/

http://www.ist-plastic.org/

http://www-rocq.inria.fr/arles/download/ubisec/

ubiSOAP is composed of the Multi-radio Networking and B3GSOAP packages available at http://www.ist-plastic.org/

Available at http://www-rocq.inria.fr/arles/download/ozone/

funded by the European Commission, FP6 contract number 026955, http://www.ist-plastic.org/


Francoise Sailhan
email: sailhan@ieee.org

Julien Bourgeois
email: julien.bourgeois@univ-fcomte.fr

Valérie Issarny
email: valerie.issarny@inria.fr

A Security Supervision System for Hybrid Networks

Keywords: Distributed intrusion detection, host-based and network intrusion detection, security and protection management, event notification

The traditional way of protecting networks and applications with e.g., firewalls and encryption, is no longer sufficient to protect effectively emerging hybrid wired-cum-wireless networks including ad hoc networks. Intrusion detection mechanisms should be coupled with preventive measures so as to identify unauthorised abuses. To this end, we propose a novel Hybrid Distributed Security Operation Center (HD-SOC) which collects logs that are generated by any application/service, layer of the protocol stack or resource (e.g., router), providing a global view of the supervised system based on which complex and distributed intrusions can be detected. Our HDSOC further (i) distributes its capabilities and (ii) provides extensive coordination capabilities for guarantying that both the networks and the HDSOC components do not constitute isolated entities largely unaware of each others.

Introduction

Until recently, most systems were operating over wired networks and were intended to be used as part of specific applications or in localised settings (e.g., building, campus or corporation). Spurred by the emergence of Wifi technologies and the advance of generalised eCommerce and pervasive applications (e.g., rescue and military application), interest has moved towards the provision of a global solution that interconnects in a secure manner changing sets of clients, services and networks. This construction of Internet-scale applications introduces new challenges consisting in securing large-scale wired-cum-wired networks, including Wifi-enabled ad hoc networks, which are spanning geographically dispersed sites and distinct administrative domains. The traditional way of protecting these networks and applications with e.g., firewalls and encryption is no longer sufficient due to the following reasons. First, ad hoc networks introduce security holes due to their vulnerability to a variety of factors e.g., open medium, cooperative algorithms. In addition, the best protection is always vulnerable to attacks due to unknown security bugs and improper configuration. It is therefore clear that preventive measures should be coupled with intrusion detection mechanisms so as to identify unauthorised use and abuse. The Distributed Network Intrusion Detection Systems (DNIDSs) that have been proposed in the literature [START_REF] Anantvalee | A survey on intrusion detection in mobile ad hoc networks[END_REF] [START_REF] Axelsson | Intrusion detection systems: A survey and taxonomy[END_REF], are extremely diverse in the mechanisms they employ to gather, analyse data and identify intrusion. However, DNIDSs share in common the fact that they glean intrusion data by monitoring the traffic and intercepting the network communications. More specifically, they mostly operate on the IP and transport layer headers and packets as well as the packet content, providing in depth packet analysis. Consequently, while DNIDSs are in a very convenient position wherein it has a complete access to all traffic traversing the managed network, their perspicacities suffer from:

• the cost (in term of processing usage) associated with the in depth analysis of the intercepted traffic. Note that one class of attacks commonly launched against DNIDS, lies in letting this DNIDS in a lethal state by spamming it with a large number of spurious traffic. • the absence of information owned by the DNIDS on resources (hosts, services, protocols and applications) that constitute the network, which renders the DNIDS impotent to detect, correlate and report a wide range of (host, service, protocol and application-specific) intrusions.

This inefficiency of actual DNIDSs engaged us to propose a novel approach to intrusion detection, which were based on a Distributed Security Operation Center (DSOC) [START_REF] Ganame | A high performance system for intrusion detection and reaction management[END_REF][START_REF] Ganame | A global security architecture for intrusion detection on computer networks[END_REF]. Rather than relying exclusively on a resource-consuming and prone to attack traffic monitoring system, our DSOC collects logs that are generated by any application, service, DNIDS, layer of the protocol stack or resource (e.g., router) composing the managed system. As a result, our DSOC owns a global view of the supervised system -the state of any component being reported -based on which it can detect complex intrusions that are possibly originated by any component of the protocol/application stack and any hardware resource.

Based on this preliminary work, we propose a novel Hybrid DSOC (HDSOC) which is dedicated to provide intrusion detection in a large-scale hybrid network built upon wired-cum-wireless networks, which are geographically-dispersed and include Wifi-based ad hoc networks. Our HDSOC takes into account the specificities of ad hoc networks:

• Wireless hosts may operate under severe constraints e.g., limited bandwidth.

This requires defining an HDSOC that reduces the overhead caused by its usage. • The dynamics of hybrid networks including ad hoc networks, diminish the resilience of the HDSOC and necessitates to increase the decoupling of the HDSOC components so as to enable this latter to react and reconfigure in a timely way to network dynamics.

All these factors circumvent the need for supporting a global low-overhead HD-SOC that is adapted to the network topology and characteristics (e.g., its dynamics, organisation) as well as the medium of communication which may be e.g., unreliable and subject to unexpected disconnection. In order to increase the resilience of the HDSOC, we propose to (i) distribute its capabilities and (ii) provide extensive coordination capabilities for guarantying that both the networks and the HDSOC components do not constitute isolated entities largely unaware of each others. The proposed security operation center collects logs for detection and correlation without consuming significant network bandwidth while addressing missing, conflicting, bogus, and overlapping data. Further support for dynamic reassign correlation, and intrusion detection management responsibilities is provided to nodes as the topology evolves. The remainder of this paper is organised as follows. We introduce the proposed Distributed Security Operation Center ( § 2) before detailing each of its constitutive component ( § 3). Then, we conclude this paper with a summary of our results along with directions for future works ( § 4).

Design Rational

HDSOC aims to detect intrusion in a hybrid network composed of a collection of ad hoc networks which either (i) operate in physically isolated geographic sites (e.g., disaster-affected areas) or (ii) extend the coverage of e.g., public hot-spots, corporate buildings or large-scale urban areas. Each of these geographically dispersed ad hoc networks is further connected to a (wired) wide area network thanks to some gateway nodes (see Figure 1 for an overview of the network and the HDSOC architecture). The main challenge in collecting logs in ad hoc networks stems from the need to minimise the generated traffic and the computational load. This calls for: 1. parsing logs (i.e., extract only relevant data) rather than collecting raw logs that are characterised by a large size and prone to overload our system (as it is the case with attacks on the log size), 2. enabling resource-constrained devices that are incapable of parsing locally their logs, to delegate this parsing activity to a remote device which offers sufficient capabilities. 3. parsing logs as close as close as possible from the device that generates it so as to diminish the number of long distant communications.

In order to answer to these commitments, our approach lies in collecting and parsing logs locally whenever possible. For this purpose, a lightweight collector and parsing agent (hereafter referred as Embedded Collection Box or simply ECBox) is embedded on the devices that show sufficient memory and computing resources. Alternatively, for resource-constrained nodes, we rely on a service discovery protocol ( §3.4), which discovers dynamically ECBoxes. Among potential candidates, the closest ECBox is selected so as to keep to a minimum long distance communication. The selected ECBox is further assigned the task of collecting and parsing logs on behalf of resource-constrained devices. After parsing and extracting relevant data from logs, local/remote ECBoxes generate event notifications that are further disseminated over the network, causing a slight increase of the network traffic due to the lightweight size of event notifications. The dissemination of events is performed by an event notification service which aims to ensure that each device is delivered the information (i.e., events) relating to the distributed intrusion to which that devices participates. This information gives to the device a global view of the intrusion (i.e., intrusion state, intrusion development and its level of implication), helping it in reporting in early stage any intrusion furtherance. In order to prevent the device from flooding the network whenever an intrusion is reported while providing to the devices a global view of the intrusion attempts to which it takes part, we rely on a publish/subscribe distributed event notification service whereby:

• consumers (e.g., devices taking part in the intrusion attempt, security administrator's computer) express their demands to producers (e.g., devices taking part in the intrusion) during a subscription process, • event producers transfer to subscribers the description of any relevant event that has been triggered locally.

This event system faces the requirements (namely scalability, autonomy and timeliness) driven by HDSOC by disseminating in a distributed way events over a self-configured delivery structure organised as a cluster-based hierarchy (Figure 3). This cluster-based hierarchy provides convenient aggregation and correlation points while rending our HDSOC more adaptable to network failures and less vulnerable to attacks due to its distributed nature.

Distributed Operation Center for Hybrid Networks

We propose an hybrid distributed security operation center which attempts to detect intrusions within a large-scale network including geographically-dispersed wired or wireless networks (e.g., ad hoc networks). Such detection necessitates to collect logs ( §3.1) so as to identify intrusion attempts ( §3.2) and initiate proper reactions. Rather than collecting bandwidth-consuming raw logs, our approach lies in parsing logs so as to extract only security-relevant information and generate compact event notifications and alarms that are beside disseminated at low cost ( § 3.3). Note that such parsing is either performed locally, i.e., on the device that generated the logs if its capacities are sufficient) or alternatively remotely; such delegation of the parsing task being enabled by a pervasive service discovery protocol ( § 3.4).

Local Event Collection

Prior developing mechanisms for detecting intruders, it is crucial to understand the nature of attacks1 as well as the possible security holes that characterise ad hoc and hybrid networks. In ad hoc networks, intruders take advantage of the lack of physical protection inherent to the absence of clear physical boundary (no protection being applied inside the network by any layer 3 resources, e.g., gateways), the collaborative nature of algorithms and the resource-limited capacity of the network (devices being more likely to be exhausted). This renders network components particularly vulnerable. These components include:

• Networking components (e.g., MAC, zeroconf and routing protocols) included in the physical/link/network layers are subject to eavesdropping, jamming, interceptions (physical layer), identity falsification (zeroconf protocol) and finally attacks initiated on routing tables (routing protocol) with e.g., the so-called wormhole and blackhole attacks. • Security components, including DNIDS, cryptographic facilities, motivation functionalities which recompense collaborative nodes, and reputation and exclusion mechanisms whereby nodes vote and attribute a reputation to each node. • Transport components, applications and services which are affected by session hijacking or flooding and application/service/scenario-specific attacks.

Each of these software components generates logs expressed in different formats including standard formats (e.g., syslog, MIB, HTML) or proprietary/applicationspecific formats. These logs can be easily collected relying on standard Xmit protocols (e.g., SNMP, SMTP, HTTP) as it is the case in traditional monitoring architectures. For instance, OLSR [START_REF] Clausen | Optimized link state routing protocol[END_REF][START_REF] Clausen | Optimized link state routing protocol (olsr)[END_REF] logs can be collected using MIB format that is defined and used in [START_REF] Pacheco | An administration structure for the olsr protocol[END_REF][START_REF] Albers | Security in ad hoc networks: a general intrusion detection architecture enhancing trust based approaches[END_REF]. The pervasiveness of these protocols ensures a significant level of interoperability to our HDSOC despite the heterogeneity of hardware and software platforms. We therefore consider a HDSOC in which each device generates logs whose collection is enabled thanks to a protocol agent. In practice, this protocol agent corresponds to a collection of clients which implement standard Xmit protocols (Figure 2). Collecting logs from heterogeneous sources implies setting up a dispatcher and an application agent. The dispatcher determines the source-type of an incoming event and then forward it to the appropriate application agent which formats it in a common format (i.e., a format understandable by any HDSOC module). In practice, this dispatcher performs the following tasks:

• listening for incoming message transmitted by a protocol agent through an particular channel (e.g., as socket, named pipe, system V message queue), • identifying the message source and the Xmit protocol used. More precisely, a patterns database is pre-loaded in the device memory (for performance considerations) and is used to find patterns matching the message. • redirecting the original message to the application agent responsible for managing the messages generated by that type of source and Xmit protocol.

This application agent parses the message and expresses it in a common format that is transmitted to the event notification agent.

Distributed Intrusion Detection

After translating events into a common format that is understandable by any DSOC component, events are analysed and correlated so as to avoid transmitting all the events across the network. The main objective of correlation lies in producing a succinct overview of security-related activities. This necessitates to (i) filter events for the purpose of extracting only relevant events, and (ii) aggregate events so as to generate a compact representation of those events that eases the intrusion detection. Broadly sketched, event filtering aims to eliminate events that are not relevant, i.e.,

• duplicate events that do not provide additional information while consuming significant bandwidth. • events that match policy criteria e.g., administrator login, identification, authorisation or restriction processes. • events that are not critical to the supervised system, excluding events that relate to some vulnerabilities whose system is not exposed to. For this purpose, the device stores and maintains (structural, functional and topology-related) information about security breaches and insecure behaviour that either impact the overall security level or that can be exploited by an attacker.

Relevant events (i.e., events that went thought the filtering pipe) are further aggregated so as to provide a more concise view of what is happening in the system. This actual system view called context is stored locally with the previously generated contexts, before being transmitted by the event notification service.

Based on the collection of contexts owned by the device, intrusion detection may take place. Intrusion detection consists in analysing a sequence of events so as to identify event sequence patterns characterising intrusion attempt. Note that during this process, time considerations are taken into account so as to take into account slow intrusions. In practice, such intrusion detection consists in matching a sequence of events (a context) against a set of attack signatures whose structure is described bellow.

Attack signature

A conquering attack can be broken down into a collection of successive steps that are successfully completed. This renders an attack characterisable as an attack signature, which corresponds to a labelled tree rooted by a node representing the goal, and intermediate nodes representing an attack step (i.e., an observable event) with a succession of children defining a way of achieving it. An attack scenario (i.e., the overall set of attacks that can threat the supervised system) is then represented as a forest of trees, with some part of trees being shared when a subset of steps involved in two distinct attacks is similar. Such attack scenarios are defined by the security administrator based on vulnerabilities specific to the network and the past attacks. Such tree-based representation of attack signatures renders intrusion detection easy to carry out. Indeed, an attack attempt is easily identifiable by matching attack signatures against a context, i.e., against a succession of (possibly distributed) events occurring on a specific set of systems (e.g. devices, collection of devices, network segments). From a practical point of view, an attack identification therefore consists in matching an attack signature on the instance of a particular context. Central to intrusion identification is therefore the context accuracy. This accuracy is maintained by the event notification service, which updates the context of each device (its system view) with the most up-to-date events arising in the network.

Distributed Event Notification

Our event notification service aims to deliver events to devices so as to enable them to update their context, giving that device a global view of the intrusion attempts and hence rending the detection of intrusions more accurate. In order to prevent the device from blindly flooding the network whenever an intrusion is reported, our event model derives from the asynchronous publish/subscribe paradigm. From a communication perspective, our distributed event notification consists in exchanging notifications and control messages (i.e., subscriptions and un-subscriptions) between producers and subscribers through a collection of intermediate event agents (Figure 1). Note that a potential event agent (hereafter simply called agent) designates a device which holds our notification service. In practice, this collection of intermediate agents is organised into a cluster-based structure wherein each agent corresponds is a cluster leader and maintains information and connectivity with its cluster members and its clusterhead2 . This underlying structure is then used for delivering control messages (subscriptions and un-subscriptions) to producers, as well as notifications to consumers. When delivering a notification, the main objective pursued by agents lies in forwarding that notification to an agent only if, toward this direction, there exists a consumer interested in receiving it. For the purpose of forwarding selectively notifications, each agent holds a subscription repository that includes each received subscription along with the respective neighbouring agent which forwarded it. Note that a neighbouring router constitutes the potential candidate for forwarding notifications. This repository is used to define if there exists a consumer along the direction of the considered router that subscribed for this notification. Based on this event notification, security information can be efficiently disseminated to the HDSOC.

Event notification Delivery Structure

In order to support an efficient event dissemination over a hybrid network, we propose a distributed event system, which distinguishes itself by:

• providing seamless integrated event notification over a network composed of different types of networking technologies (wired versus wireless, infrastructure-less versus infrastructure-based networks) and possibly spanning geographically dispersed domains/sites.

• addressing the problem relating to the support of extensive control, security and autonomy by mean of a distributed event notification system based on a overlay infrastructure, which organise the nodes for delivering event notifications.

In practice, in order to distribute the events management, we based our event notification system on a distributed grouping communication which organises nodes into a self-organised delivery structure (Figure 3) deployed of the hybrid network, as defined in [START_REF] Banerjee | Scalable application layer multicast[END_REF]. This structure corresponds to a cluster-based hierarchy of n L layers (n L =log(n n ), with n n designating the number of nodes that are expected to join the event system), each layer being portioned into a set of bounded-size clusters (let k be that size) controlled by a cluster head. The reason for setting bounds on the number of layers and on the cluster size is twofold. First, it ensures a control overhead ranging about log(n n ) at each node. Second, the length of the path used for delivering notifications, and hence the related delay, is bounded by o log(n n ). In order to prevent a cluster of size k from changing continuously its configuration whenever it gains or looses a member, the admitted bounded-size of a cluster ranges from k up to 2k cluster members.

In practice, to warrant a loop-free structure, each node belongs to the lowest layer (L 0 ) and only the leader of cluster located in a layer L i belongs to the upper layer L i+1 . This delivery structure is created and maintained by a grouping solution. Considering the fact that there exists no unique grouping protocol that is optimal for any kind of network, we use a specialised grouping solutions for each type of network along with a mechanism for integrating them. We rely on the Nice protocol [START_REF] Banerjee | Scalable application layer multicast[END_REF] which has been specifically designed for operating in infrastructure-based large-scale network (e.g., the Internet) and the Madeira protocol that comes from our previous research on network management [START_REF] Sailhan | Wireless mesh network monitoring: Design, implementation and experiments[END_REF] and is customised to operating over ad hoc networks. The reason that motivates our choice for the Nice protocol, is twofold. First, this application-level protocol can operate over a large-scale network spanning different administrative domains.

In addition, it were originally developed to support video streaming and hence meets the requirements driven by real-time delivery.

For scalability reasons, a node does not manage information concerning the overall group. Instead, a member or cluster head maintains information restricted to its cluster(s); each member sending periodically a keep-alive message. This limited knowledge permits to keep to a minimum the number of control messages exchanged for maintaining up-to-date membership information.

Distributed Service Discovery

The resource constraints of networked devices (e.g., routers, or devices belonging to ad hoc networks) coupled with the financial cost inherent to the deployment of additional functionalities on devices, circumvents the need for enabling HDSOC to delegate to remote devices a part of the functionalities relating to intrusion detection, e.g., log parsing and signature matching. The effective delegation of these functionalities, which are traditionally performed by ECBoxes, necessitates to discover on the fly the service(s) offered in the network that best match(es) these functionalities requirements. The following introduces a service discovery protocol [START_REF] Sailhan | Scalable service discovery for manets[END_REF] that meets this requirement. This protocol is aimed at hybrid networks including ad hoc networks. In the ad hoc network, our primary goal is to keep to a minimum the traffic generated by the service discovery process, so as to minimise consumption of resources and in particular energy. Specifically, our discovery architecture is structured around a subset of HDSOC nodes, called lookup agents or simply agents, that are responsible for discovering ECBox functionalities and capabilities (see Figure 4). These lookup agents are deployed so that at least one lookup agent is reachable in at most a fixed number of hops, H, whose value is dependent upon the nodes density. Agents cache the descriptions of ECBoxes' functionalities (services) available in their vicinity which is defined by H. Hence, HDSOC nodes (excluding lookup agents) do not have to maintain a cache of service descriptions, and the network is not flooded by service advertisements. A resource-constrained HDSOC device looking for a service (i.e., an ECBox or one of its embedded functionality), simply sends a query to the lookup agent for local service discovery. If the description of the requested service is not cached by the local agent, this agent selectively forwards the query to other lookup agents so as to perform global discovery. The selection of the lookup agents toward which service queries are forwarded, is based on the exchange of profiles among agents. The agent profile provides a compact summary of the agent's content and a characterisation of the host capacity. Agent profiles allow both guaranteeing that service queries are issued to agents that are likely to cache the description of the requested service and to keep to a minimum the generated traffic. Another critical issue lies in providing convenient features so as to enable discovery of services over the hybrid network. This is supported through gateways that (i) advertise their capabilities (e.g., with a related gateway protocol, a zeroconf protocol, or using our protocol), and (ii) are assigned a local or remote lookup agent, implementing the cooperative behaviour as discussed above. A gateway lookup agent then holds the description of services available in all the networks composing the hybrid network, and advertises itself to the networks it bridges composing the hybrid network. Furthermore, to support service discovery in an infrastructure-based network in which a network administrator deploys agents, clients and service providers behave differently. Since clients and service providers do not need to elect a agents, they can listen for agents announcements or rely on the DHCP protocol. Using this service discovery protocol, a resource-constrained DHSOC device can delegate to a remote device the resource-consuming functionalities that implement intrusion detection. For this purpose, it discovers dynamically the ECBoxes, located within the overall hybrid network, which offer the functionalities that best match its requirements. Then, it cooperates with the selected ECBoxe's service, utilising the provided service description, so as to contribute to the global effort for detecting intrusions.

Conclusion

In this paper, we propose a Hybrid Distributed Security Operation Center (HD-SOC) which collects logs that are generated by any application/service, layer of the protocol stack or resource (e.g., router), providing a global view of the supervised system based on which it complex and distributed intrusions can be detected. Rather than directly transmitting these logs over the network, causing its overload, logs are parsed in an early stage so as to easily extract intrusion-related information and distribute it by the mean of compact event notifications and alarms. This HDSOC couples a lightweight distributed intrusion detection components with a distributed event system and a distributed service discovery protocol for an efficient delegation of resource-consuming tasks and a bandwidth-saving cluster-based collection of the events across the hybrid network. Our Hybrid Distributed Security Operation Center further addresses the main commitments of hybrid networks: scalability, flexibility, autonomy, and fault-tolerance. More precisely,

• Scalability comes from the distribution of load relating to the log parsing and the intrusion detection, on the devices • Autonomy is the consequence of using a group based event notification service and a discovery protocol that are (i) automatically deployed without requiring human intervention and (ii) adapt dynamically to network changes (e.g., topology changes). • Fault-tolerance is attributed to (i) a loosely-distributed event delivery that adapts dynamically to any permanent or transient network failure and a service discovery protocol that permits to discover dynamically an alternative to a faulty service.

Fig. 1 .

 1 Fig. 1. HDSOC Architecture

Fig. 2 .

 2 Fig. 2. Device Architecture

Fig. 3 .

 3 Fig. 3. Event Delivery Structure

Fig. 4 .

 4 Fig. 4. Discovery Structure

R. Lee (Ed.): Soft. Eng., Arti. Intel., Net. & Para./Distri. Comp., SCI 149, pp. 137-149, 2008. springerlink.com c Springer-Verlag Berlin Heidelberg 2008

Interest reader can refer to[START_REF] Wu | A survey on attacks and countermeasures in mobile ad hoc networks[END_REF] for a comprehensive survey on attacks and countermeasures in ad hoc networks.

The root of the delivery structure maintains information restricted to its cluster member.

Acknowledgements

Authors would like to acknowledge the implementation work carried by R. Bidou (University of Franche Comté), R. Chibout (INRIA), E. Cuadrado-Salamanca (EIRC, LM Ericsson Ltd), P. Farrell (EIRC, LM Ericsson Ltd) and A.K. Ganame (University of Franche Comté).