Emil Andriescu
email: emil.andriescu@inria.fr

Roberto Speicys Cardoso
email: roberto.speicys_cardoso@ambientic.com

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

AmbiStream: A Middleware for Multimedia Streaming on Heterogeneous Mobile Devices

Keywords: multimedia streaming, mobile, smartphone, middleware

Multimedia streaming when smartphones act as both clients and servers is difficult. Indeed, multimedia streaming protocols and associated data formats supported by today's smartphones are highly heterogeneous. At the same time, multimedia processing is resource consuming while smartphones are resource-constrained devices. To overcome this complexity, we present AmbiStream, a lightweight middleware layer solution, which enables applications that run on smartphones to easily handle multimedia streams. Contrarily to existing multimedia-oriented middleware that propose a complete stack for multimedia streaming, our solution leverages the available highly-optimized multimedia software stack of the smartphones' platforms and complements them with additional, yet resource-efficient, layers to enable interoperability. We introduce the challenges, present our approach and discuss the experimental results obtained when executing AmbiStream on both Android and iOS smartphones. Our results show that it is possible to perform adaptation at run time and still obtain streams with satisfactory quality.

Introduction

The present generation of smartphones enables a number of applications that were not supported by previous generation cellular phones. Particularly, the greater processing power, better network connectivity and superior display quality of these devices allow users to consume rich content such as audio and video streams while moving. Not surprisingly, radios 3 and television channels 4 today provide mobile applications that allow access to their live media streams. Even video rental services 5 provide mobile applications that support movie streaming to smartphones.

All those applications, however, assume a centralized architecture where a powerful server (or a farm of servers) provide streams to lightweight mobile devices. Node heterogeneity also remains an issue: most of those applications are available for a single smartphone platform. Indeed, to support multiple phone platforms, developers must (i) modify the mobile application to support different sets of decoders, streaming protocols and data formats and (ii) generate multiple data streams on the server side to be consumed by each mobile platform. Hence, when a resourceful server is not available, as in the case of a smartphone to smartphone streaming scenario, this approach is impractical.

In this paper, we introduce AmbiStream, a middleware-layer solution to enable multimedia streaming among heterogeneous smartphones. Such a solution can be beneficial to a large number of applications. Examples of such applications include:

-Streaming a live event directly to other devices reachable on the network; -Sharing media on the fly between different devices (phone to tablet/TV); -Voice call applications; -Distributed processing of a video stream; -Mixing augmented reality with live remote user interaction for, e.g., a networked game; -Multimedia-rich collaboration among mobile users; -Audio/video sharing in crisis situations when infrastructure is unavailable; -Private communication of multimedia data between peers (without involving a third party server);

Today, to create such applications, developers must overcome a number of constraints. First, smartphones run different mobile operating systems, each supporting a different set of media encoders, decoders and streaming protocols. Second, communication is performed over wireless networks that are unstable and that do not support resource reservation, and thus streaming quality is managed by the protocol without cooperation from the network layer. Finally, the multimedia streaming software stack of each platform is highly optimized to deliver high quality audio and video while reducing resource usage.

Existing system support for multimedia streaming is unsuitable to face the smartphone challenges described above. Indeed, architectures for multimedia streaming on the Internet such as [START_REF] Cruz | A personalized HTTP adaptive streaming WebTV[END_REF][START_REF] Van Lancker | Implementation strategies for efficient media fragment retrieval[END_REF] suppose the existence of powerful servers that can adapt content on behalf of clients, which is infeasible when the streaming server is a resource-constrained smartphone. Solutions for multimedia streaming on ad hoc networks either do not consider the problem of content adaptation [START_REF] Andronache | Multimedia content distribution in hybrid wireless networks using weighted clustering[END_REF][START_REF] Do | Massive live video distribution using hybrid cellular and ad hoc networks[END_REF][START_REF] Vu | ishare: Exploiting opportunistic ad hoc connections for improving data download of cellular users[END_REF] or are cross-layered, such as those surveyed in [START_REF] Lindeberg | Challenges and techniques for video streaming over mobile ad hoc networks[END_REF]. Crosslayered solutions require cooperation between application layers and networking layers, e.g., integration between the video codec and the routing protocol to optimize streaming quality.

To enable multimedia streaming among heterogeneous devices, two main challenges must be solved. First, multiple incompatible protocols for multimedia streaming exist today, and each platform supports one or a small subset of them. As a result, smartphones must overcome the streaming protocol heterogeneity problem to be able to exchange multimedia streams with heterogeneous devices. Second, each smartphone platform generates and stores multimedia data using some specific container format, usually depending on the streaming protocols it supports. These data cannot be directly transmitted through a different streaming protocol because the media container format is specific to the protocol. Smartphones, then, must also adapt the media container format to enable translation from the native streaming protocol to non-native protocols supported by other peers.

To address the above challenges, we propose a lightweight middleware layer that complements existing software stack for multimedia streaming on smartphones with components that enable interoperability. The proposed layer defines an intermediate protocol and the associated container format for multimedia streaming among heterogeneous nodes. This layer also mediates the native media container formats and protocols to/from the intermediate streaming protocol.

The remainder of the paper is organized as follows. In the next section we review existing work on multimedia streaming in mobile environments, as well as research related to automated protocol adaptation. In Section 3 we detail the challenges involved in creating a layer to adapt multimedia streams in mobile heterogeneous environments. Section 4 presents the architecture of AmbiStream layer and explains how the main components operate: the format adapter, the protocol translator and the local media server. Section 5 discusses our initial experimental results on Android and iOS devices, which show that it is possible to adapt data and protocols at run time and also obtain streams with satisfactory quality. Finally, in Section 6, we draw our conclusions and discuss future work.

Related Work

Many multimedia-oriented middleware have been proposed in the literature. One of the earliest efforts in this direction was proposed in [START_REF] Coulson | A configurable multimedia middleware platform[END_REF], which provided applications with mechanisms for late binding based on QoS constraints. The proposed platform was later extended in [START_REF] Coulson | Supporting mobile multimedia applications through adaptive middleware[END_REF] to leverage CORBA's mechanisms for inspection and adaptation and enable applications to adapt the stream quality based on information obtained by inspecting middleware components. However, as predicted in [START_REF] Blair | On the failure of middleware to support multimedia applications[END_REF], the lack of mature multimedia support at the middleware level led the industry to develop platform-specific solutions to handle multimedia streaming quality. As a result, today, most existing streaming protocols integrate mechanisms to adapt video quality to network conditions. Other middleware solutions have been proposed to provide multimedia streaming services. Chameleon [START_REF] Curran | A middleware architecture for streaming media over IP networks to mobile devices[END_REF] is a middleware for multimedia streaming in mobile heterogeneous environments. It is implemented using pure Java Core APIs in order to be portable to all Java and JavaME handsets. In Chameleon, servers send streams with different levels of quality to different multicast groups, so that clients can select the best quality according to their available resources and also adapt to changes on resource availability by selecting a multicast group providing a stream with lower quality. This approach imposes a heavy burden on the server side, which has to keep multiple streams in parallel regardless of the number of clients. Furthermore, Chameleon implements the whole software stack required for streaming, which has a negative impact on performance.

Fewer works take into account the capabilities of current smartphones and their impact on mobile multimedia streaming. The evaluation of streaming mechanisms in [START_REF] Ransburg | An evaluation of mobile end devices in multimedia streaming scenarios[END_REF] for Android 1.6 and iOS 3.0 tries to identify which design is better suited for mobile devices. Traditional metrics such as bandwidth overhead, startup delay and packet-loss are used to evaluate the quality of multimedia streaming in various test situations. They observe that high network delays can result in non-continuous playback when using the HTTP Live protocol from iOS, while RTP streaming remains unaffected on Android.

Our approach to solve heterogeneity issues and enable multimedia streaming between heterogeneous mobile devices specifically stems from research on protocol translation and mediation. The work in [START_REF] Spalazzese | Towards a formalization of mediating connectors for on the fly interoperability[END_REF] proposes a framework to formalize the process of synthesizing connectors that mediate two incompatible protocols, and suggests that data mediation can be solved through ontology integration. However, it falls short from addressing the specifics of multimedia streaming protocols, where messages are dependent on time and where message data must also be adapted during mediation. Nakazawa et. al. [START_REF] Nakazawa | A bridging framework for universal interoperability in pervasive systems[END_REF] propose a taxonomy of bridging solutions among communications middleware platforms and present uMiddle, a system for universal interoperability, which supports mediation (entities and protocols are translated to an intermediate common representation) and is deployed as an infrastructureprovided service. This design choice is appropriate for bridging communications middleware, since it requires communication through different transport technologies that may not be available on all nodes. However, in our scenario, we want to enable peer-to-peer streaming between smartphones without using an untrusted third party server. As such, it is desirable that clients and servers are able to perform mediation independently from the infrastructure.

Another approach for the automatic translation of protocols is z2z [START_REF] Bromberg | Automatic generation of network protocol gateways[END_REF], which combines a language for specification of protocols and messages, a compiler that automatically generates protocol gateways using C code, and a runtime that executes and manages protocol gateways. Z2z can translate a large number of protocols, but it does not take into account timing requirements typical from real-time streaming protocols. In such protocols, state transitions are not defined by a fixed set of message exchanges but rather by the time deadlines that the protocol must meet. With regard to message contents, z2z protocol gateways can adapt messages by rearranging data from an input message to an output message. This is also not sufficient to overcome the complexity of multimedia streaming protocols, where timing limits may require that messages are processed and regenerated when adapting protocols. Z2z evolved to Starlink [START_REF] Bromberg | Starlink: runtime interoperability between heterogeneous middleware protocols[END_REF] which enables protocol translation dynamically at run time, a particularly important feature in systems where existing protocols are unknown at compile time. Our approach adopts an intermediate protocol and requires only clients to adapt their native protocols to the intermediate protocol, which can be done at compile time.

Challenges for Mobile Interoperable Media Streaming

As we mentioned in Section 1, two challenges must be solved to enable peer-topeer streaming of multimedia data between heterogeneous smartphones: (a) how to enable interoperability among incompatible streaming protocols, and (b) how to adapt media containers to consume multimedia data transmitted through an incompatible streaming protocol.

Here, we detail the challenges introduced above. Specifically, Section 3.1 reviews the process of streaming multimedia data from a server to heterogeneous clients. Then, based on this general schema, Section 3.2 details the challenges involved when translating multimedia streaming protocols, while Section 3.3 explains the issues caused by the different media container formats available on current smartphones.

The streaming process

Streaming to heterogeneous devices is classically done by servers supporting a set of audio/video codecs, media container formats and streaming protocols, and comprises three phases: media capture, media transmission and media presentation. The steps commonly required to stream multimedia between two devices are depicted in Figure 1 and are detailed below.

Considering the sequence of steps in Fig. 1, media container formats are used in multiple cases. At Step 1 the demuxing (or demultiplexing) phase refers either to the unwrapping from a disk container if the media source is a file, or to a streamable container if it is a media server or a camera. The elementary stream obtained from Step 1 can be transcoded to a different video/audio compression format and it is then re-multiplexed to a streamable container format in Step 3. The format of multiplexing used is dependent on the streaming protocol, since in most of the cases streaming protocols support a single format.

Streaming media Server

Streaming Client Media Capture : Media content can originate either from a camera, stored data or from a remote source via a streaming protocol. The input can be already wrapped inside a media container (for instance, MPEG-TS or RTP) by the source hardware, so the first (Demuxing) step is optional. Possibly the most important characteristic of multimedia content is its audio/video encoding. Indeed, being a highly resource demanding operation, multimedia encoding is subject to software and hardware optimizations on both personal computers and embedded devices. The availability of encoders and decoders therefore varies depending on the mobile operating system, platform and device. If a client does not support a decoder compatible with the server's encoder, the client cannot consume the media. When a server supports multiple encoders, multimedia data can be re-encoded on a format compatible with the client supported decoders (Step 2 in Fig. 1), but this process is resource consuming and can affect performance, especially when streaming live content.

Media Transmission : Since video and audio frames cannot be directly transferred over an IP network, they are wrapped within media containers that provide the necessary meta-information to facilitate the decoding and correct presentation at the receiver (i.e., client) side. The process of wrapping and unwrapping audio/video frames from a media container is also referred to as multiplexing and demuxing, respectively. This is related to the fact that in some container formats, frames (or frame fragments) from multiple audio and/or video tracks are interleaved. The media transmission also requires control and signalling. This task is assured by means of a communication protocol specifically designed to transport multimedia content. Streaming protocols can be divided in two subgroups:

Real-time streaming protocols are best suited for conversational content such as video conferences where user interaction with the streamed content is important. Video on-demand protocols are designed to offer better scalability and connectivity; are usually based on the higher level Hypertext Transport Protocol (HTTP) and introduces acceptable delays.

Media Presentation : In order to correctly reproduce an audio/video stream on a mobile phone, it is required that the platform supports the given streaming protocol, media container format, the audio/video codecs and the codec profile used by the encoder. Being a resource consuming activity, multimedia decoding is usually managed by the mobile platform through hardware decoders or by efficient native code implementations. To offer a satisfactory multimedia user experience on resource-constrained devices, mobile platforms provide a default media player that applications can access through a standard API. This approach has the advantage of providing a uniform multimedia experience regardless of applications. However, it limits the possibilities to improve audio/video handling in mobile devices since the exposed API is generally limited. For instance, existing decoders used by the player to display multimedia content might be inaccessible for use or extension by applications.

Streaming protocol heterogeneity

Most smartphone platforms support at least one streaming protocol client. The most well known protocols used in mobile phones today are: Real Time Streaming Protocol (RTSP) [START_REF] Schulzrinne | RTP: A Transport Protocol for Real-Time Applications[END_REF], Apple HTTP Live Streaming (HLS) [START_REF] Pantos | HTTP Live Streaming[END_REF], Microsoft Smooth Streaming6 and Adobe HTTP Dynamic Streaming (HDS) 7 (provided that the mobile platform supports Adobe Flash). The most commonly found on mobile platforms is RTSP, but because it uses UDP as transport protocol on unprivileged ports it is inappropriate for use in restricted networks such as 3G and public WiFi hotspots. A standard extension defined in [START_REF] Schulzrinne | Real Time Streaming Protocol (RTSP)[END_REF] Still, even if the streaming protocols are incompatible by default, the encoded video and audio elementary streams may be compatible with multiple devices. For example, HLS uses H.264 codec for video, but the same codec is also largely used to stream video over RTSP to Android devices. As it can be seen in Table 1, there exists a common set of video and audio decoders available on multiple mobile phone platforms. In contrast, streaming protocol support is increasingly heterogeneous on mobile platforms, with the arrival of new proprietary protocols such as HTTP Live Streaming and Microsoft Smooth Streaming. The currently supported streaming protocols on mobile phone platforms are presented in Table 2. From both tables, we conclude that multimedia data can be exchanged between heterogeneous smartphones without the need to perform costly transcoding operations. However, it is still necessary to adapt streaming protocols to enable streaming between heterogeneous devices.

Protocol / Platform iOS Android BlackBerry OS Windows Phone 7 RTSP - + + - RTSP interleaved - - - - RTSP -SRTP - - - - HTTP Live Streaming + + - - HLS with SSL + - - - MS Smooth Streaming - - - + MSS with SSL - - - +
Table 2: Streaming protocols supported on smartphones

Media container adaptation

The conversion between different media container formats is a critical requirement for assuring interoperability between heterogeneous streaming protocols. Supporting both real-time and video-on-demand protocols makes this task more complex due to the mismatching of properties of the protocol groups.

Encoded elementary multimedia data is stored on disk using a media container format (e.g., 3GPP, MP4, AVI). Such containers are designed to be used only in random access scenarios and therefore are not suited for streaming over a network connection. Another type of containers are streamable media containers (e.g., MPEG-TS, ASF, PIFF). They are designed to be transported over IP packet networks, provide methods for fragmenting audio and video streams and may also offer synchronization and recovery mechanisms to cope with network delays or packet losses. The wrapped media packets can contain multiplexed audio/video tracks (e.g., MPEG-TS, PIFF) or single tracks (e.g., RTP). Depending on the streaming protocol type (real-time/on-demand), multimedia fragments differ in size and structure. In general, real-time protocols use lightweight headers and small packet sizes, usually less than the MTU8 in order to reduce the transfer delay by avoiding packet fragmentation. Video-on-demand protocols regularly use large video fragments composing 10-30 seconds of audio/video each. Such formats commonly rely on the ISO base media file format9 structure which supports storing of multiple interleaved frames inside a single fragment, [START_REF] Bocharov | The Protected Interoperable File Format[END_REF][START_REF]Adobe Flash Video File Format Specification[END_REF]. Larger fragments reduce the need of receiver buffers but also introduce a start-up delay which is at least equal to the duration of the first fragment.

Real-time streaming protocols are generally designed over the UDP transport protocol because timeliness is much more important than the reliability offered by TCP. Consequently, simple reliability features, such as sequence numbers, sequence identification, synchronization codes, continuity counters, flags and timestamps are integrated in the media container layer to cope with the unreliable nature of the transport. Such features are not necessarily found in the same configuration in all formats. As a result, transforming a real-time stream to a video-on-demand fragment requires complex buffering and efficient transformation of real-time data. Such requirements impose strict temporal constraints for the transformation. It is true that real-time to on-demand protocol translation is less desirable, but interoperability should still remain possible.

AmbiStream Architecture

The aim of the AmbiStream middleware is to allow smartphones supporting different streaming protocols to directly connect to, and receive live multimedia content from, other smartphones without using an untrusted server for adaptation. AmbiStream consists of a set of portable server and client components as well as a plug-in interface, designed to reduce the effort of adding support for Fig. 2: The AmbiStream middleware architecture new protocols. The structure of the middleware is presented in Fig. 2, where the greyed components are not part of AmbiStream, but are elements of the mobile platform architecture or external components.

Our work extends the approach proposed by Starlink [START_REF] Bromberg | Starlink: runtime interoperability between heterogeneous middleware protocols[END_REF] in two directions. First, our approach enables the translation between real-time and on-demand streaming protocols, which requires buffering, dropping and combination of messages to deliver time-sensitive data at the right moment. Second, we support the translation of container formats, which in the case of multimedia is dependent on the streaming protocol.

The communication is realised in a client-server mode. The streaming server, as well as the client, reside entirely on mobile devices. The current server implementation is designed to support a single streaming protocol. This protocol is translated by the client device to another protocol depending on its native protocol support. On the server side, a platform specific API interface has to be designed to access the Camera data stream. On the other hand, File access for streaming from pre-recorded content can be designed in a portable fashion. We assume that any input data is already multiplexed in the platform's native format (e.g., RIMM proprietary video format for BlackBerry). It is true that demuxing might not be needed if the platform's API gives access to elementary frame buffers. That is why there is an initial demuxing step in Fig. 2. Once the data is Demuxed (unwrapped) from its container we obtain the elementary stream tracks (e.g., the audio track) and the necessary meta-data such as sample sizes and frame durations. Considering that the middleware should enable applications to stream both in real-time and on-demand, we use RTP [START_REF] Schulzrinne | RTP: A Transport Protocol for Real-Time Applications[END_REF] as an intermediate streaming protocol. As a consequence, the middleware translates from the intermediate protocol to each existing streaming protocol, thus considerably reducing the total number of bridges required. However, this does not imply that any of the mobile platforms or devices should support this intermediate protocol natively. RTP alone is not sufficient to describe the payload characteristics such as audio/video encoders, sampling frequency, packet fragmenting method, and other media information. AmbiStream thus introduces a negotiation phase where the server sends a XML-formatted description message to clients for the middleware to correctly instantiate the client protocol bridge and the media container format adapter.

The client receives the Media description, and instantiates the appropriate protocol translator (e.g., P1 or P2 ) and media container adapter. Streaming protocol translators and media container adapters (e.g., C1 or C2 ) are used as pluggable components created at compile time. To simplify support for a large array of protocols, these components are generated automatically from descriptions of messages and behaviour given in the form of DSL (domain specific language), as detailed in Section 4.1. The plug-ins could as well be generated at run-time, but since the required plugin of the platform is known at compile-time the only use would be to support more legacy devices. Received RTP packets are Re-composed into elementary streams and, once a sample is complete, they are passed to the Media container adapter (which is detailed in Section 4.2). Depending on the adapted protocol, the samples might be buffered at this point. A Local server is managed by the protocol translator that composes the necessary control messages for establishing a streaming session.

The adaptation server running on the client device can be also used as a mediator agent to solve interoperability for streaming enabled legacy devices. This is done using at least three nodes: a server running AmbiStream, a mediator also relying on our middleware and a legacy client (i.e., without AmbiStream or any other additional software installed). The mediator smartphone translates the server streaming protocol to the one supported by the legacy device.

The AmbiStream architecture enables smartphones to stream multimedia between each other without involving a third party server, since all the adaptation is performed on the client side. In terms of privacy, this solution is superior to other architectures that require the stream to pass through an untrusted server for adaptation and/or distribution. So, even though data passes through probably untrusted peers, the authenticity of the stream can still be established using an efficient security protocol such as TESLA [START_REF] Perrig | Timed Efficient Stream Loss-Tolerant Authentication[END_REF]. Even legacy clients, that receive the streaming from an intermediate node instead of directly from the server can select a trusted peer based on any trust establishment protocol. The diversity of existing legacy devices such as TVs, tablets, and mobile phones motivate the use of distributed translation nodes instead of a centralised server.

Streaming protocol translation

Because writing protocol adapters for each existing streaming protocol implies a high development effort for a large number of platforms, we introduce an automated protocol translation solution, to enable easier integration of additional protocols. To achieve this, we base our solution on existing research in the domain of automated protocol translation. However, while advanced solutions for interoperability between heterogeneous protocols exist [START_REF] Bromberg | Automatic generation of network protocol gateways[END_REF][START_REF] Tegawendé | Bridging the gap between legacy services and web services[END_REF][START_REF] Bromberg | Starlink: runtime interoperability between heterogeneous middleware protocols[END_REF], streaming protocols tend to be more complex because of the constant data flow, time constraints and multimedia wrapper formats.

Our approach is inspired by Starlink [START_REF] Bromberg | Starlink: runtime interoperability between heterogeneous middleware protocols[END_REF], a run-time solution for protocol interoperability. Although run-time adaptation of the media format and protocol is more flexible and enables adapting protocols that are unknown at compile-time, in our case the availability is only subject to the support of mobile platforms, thus making possible to know in advance the adaptation requirements of each mobile device. Also, the adaptation only concerns the client-side since, at the server side we use an intermediate protocol. We thus propose a simpler compiletime interoperability solution based on Starlink.

Streaming protocols are a mix of control and complex data messages. We discuss the translation of the control part of streaming protocols below, while dealing with multimedia data adaptation in Section 4.2. To create a new protocol translator, the developer must provide a high level description in the form of two DSL-based models. One describes the format and structure of messages and the other outlines the protocol states, transitions and the sequence of actions performed at each protocol state. The model is expressive enough for generating message parsers and composers for multiple existing streaming protocols. The model obtained in this form is passed on to a compiler (which is part of the currently presented solution) that produces multi-language (Java, C and C#) protocol bridges in the form of plug-ins (e.g., P1 and P2 in Fig. 2) for our middleware.

An schematic example of a message description for HLS protocol is shown in Fig. 3. The description is divided in Input and Output to differentiate between incoming messages that should be parsed into structured data types and outgoing messages that are composed. This distinction is more important with text protocols, where messages have loose requirements in terms of line order, optional parameters, delimiters, spacing characters and so on. The DSL proposed here supports protocols that use either binary, text or XML message formats. To assure a sufficiently expressive message description, we extract the required fields using value capture patterns defined using Posix regular expressions for text protocols, XPath for XML and based on field size and location for binary protocols. The choice of Posix regular expression for text protocols was driven by its availability on most of the platforms, most notably that it is part of the GNU C library and is compatible with the regular expressions integrated in Java standard library (java.util.regex).

Real time protocols do not usually follow a request-response messaging pattern, as implemented by on-demand ones, but rather a one-way pattern. The problem here is that a protocol translator can not produce a response by calling the real-time inner protocol. In fact, the translator must buffer the messages of the real-time protocol and, upon a request of the video-on-demand client, generate the corresponding message.

Media container format adaptation

Translating the control part of streaming protocols is not sufficient to distribute multimedia between incompatible protocols. The format in which audio/video content is wrapped also differs depending on the protocol. To achieve a complete solution, the translation between media container formats must also be taken into account. The most important factors that led to the decision to separate <Protocol type="text"> <Input> <Header name="http_head"> <Var name="Url" type="String"/> <Rule test="capture_order(Url)">1</Rule> <Capture var="Method"> [RegEx] </Capture> <Finish test="empty_line"/> </Header> <Message name="GET_IDX"> <Insert>http_head</Insert> ... </Message> ... </Input> <Output> <Message name="IDX"> <Var name="$TargetDuration" type="Integer"/> <Line>#EXTM3U</Line> ... </Message> ... </Output> </Protocol> Fig. 3: DSL describing message formats for the HLS protocol this part from the protocol translation model are: the much higher complexity of multimedia packets, the dependence relation between messages (order, timing, fragmenting), the buffering requirements, and the multiplexer logic required to interleave multiple media tracks inside one packet/message. We further divide the media container adaptation in four distinct steps: sample fragmenting, fragment packaging, multiplexing and final adjustment. The process of adapting a stream composed of two tracks (one audio and one video) is presented in Fig. 4. Each of the four phases is defined by the developer using a DSL to describe multimedia containers, different from the ones used for protocol description. Similarly to the generation of protocol translation plug-ins, the description of the multimedia container adaptation is compiled to be deployed to designated platforms. To simplify the description, a number of media packetrelated parameters are exposed through the DSL. Parameters include: the length of the media payload, media encoding, fragmentation flag, sampling frequency, sequence number, inner frame sequence number and first/last fragment flag. The components for protocol description and container adaptation are considered to be independent, thus allowing, for example, a protocol to choose between multiple supported data formats. The Sample Re-composing middleware component (see Fig. 2) provides real-time input to the container adapter in the form of elementary stream samples for audio and frames for video.

Because we use a real-time protocol (i.e., RTP) for transporting multimedia data, the problem of timing should also be taken into account. We thus add a time-stamp reference to each packet resulting from any of the four phases of media format adaptation. Fragments of one frame share the same time-stamp information, while messages composing multiple frames contain the time-stamp of the first frame and their duration. The time required for a frame to pass through Fig. 4: Adapting the media container format all of the phases required by the format should not exceed the sampling interval of the content. Failing to assure this property can cause the client to run out of buffered data, resulting in playback stalls. In order to prevent such behaviour, frames should be explicitly dropped such that the output of the conversion is completed at the right time to assure a fluent playback. At this moment, no QoS related limits of packet drops are considered. The fragmenting step defines the way large audio or video samples are divided into smaller segments according to the limits imposed by the streaming protocol, by the media container or by the network configuration. For example, in the case of MPEG-TS, the samples are split into fragments which are inferior in size to 184 bytes, such that they can be correctly wrapped inside the standard 188 byte packets. For RTP, fragmentation follows the standard RTP Payload Format depending on the codec used (for instance, the one described in [START_REF] Wang | RTP Payload Format for H.264 Video[END_REF]). We note that a simplified description of the packet format is very useful in the case of RTP, where there are multiple payload formats depending on the media encoder used. In the case where media content is composed of multiple tracks (i.e., one video and one audio track), two separate fragmenting units are used. The number of fragments created from single frames is variable. Each fragment contains a reference to the time-stamp of its originating frame. The time required for fragmenting one frame should never exceed the sampling interval of the content.

The packaging stage adds individual packet headers. This transformation conforms to [START_REF] Schulzrinne | RTP: A Transport Protocol for Real-Time Applications[END_REF] for RTP packets and [START_REF]Generic coding of moving pictures and associated audio information[END_REF] for MPEG-TS. Depending on the protocol, the resulting packets are passed to the multiplexer or sent directly to the protocol translator.

The multiplexing phase assures time-division multiplexing for a set of given fragments or frames of multiple data tracks. Depending on the format, the multiplexing is done at a frame level or at a frame-fragment level. In order to achieve multiplexing at frame level, phase one of the adaptation should be skipped. This phase outputs only at a given time or data limit. Such a limit is necessary to be able to produce media fragments of specified duration or size. The split is always done at random access points of the stream, such that no reference between frames is lost.

The final transformation adds extra headers or packets, such that the resulting fragment is recognised as valid by standard client protocol implementations.

Many existing media container formats also contain a number of specific fields which are particularly hard to model. One example is the MPEG2 Transport Stream [START_REF]Generic coding of moving pictures and associated audio information[END_REF], which requires a 32-bit cyclic redundancy check value to be added to the Program Association Table package. In such a case we offer the possibility to add function"hooks" inside the DSL media container description. The compiler uses these to generate function templates, that developers can later implement.

Experimental Results

In order to evaluate the presented solution, we have implemented AmbiStream in Java and Objective-C and used it on Android and iOS. The goal of the experiments presented here is to evaluate the overall performance of the middleware and the achievable stream quality. The experiments were performed on both Android and iPhone smartphones. In both of the experiments presented below, the same set of source media files was used. The test files have a duration of 210 seconds, are encoded with a single (H.264-avc video) track, have a CIF frame-size (352 by 288), and a framerate of 30 fps. The test is conducted for 16 different bit-rates between 50kbps and 1500kbps using the mentioned file format and content. Each set of tests is repeated at least three times, so each of the metrics presented is characterized by 168 minutes of video streaming to each client device. In total, more than 16 hours of streaming between smartphones were necessary. The mobile phones used are mentioned in Table 3. The first two (Samsung GT-I9000 and Google Nexus One) are used in the first experiment, and all three in the second one.

Collecting mobile device performance data

Although RTSP provides out-of-band feedback of stream quality through RTCP, we have decided not to use this feature to obtain information related to the quality of service. This is due to the fact that in the case of the media framework Pocket Video OpenCore (used by Android platform in versions preceding 2.3) the information provided is not sufficiently precise. For example, the interval jitter value reported, used to observe the effect of network packet delays, is usually ten times higher than what we found at network level or on the client device. Furthermore, on the newer Stagefright media framework the feedback always reports no packet loss and inter-arrival jitter equal to zero. Android also provides an information callback from the media player service. Unfortunately, this information is limited to a small set of event codes and does not include any metric.

We have chosen to favour system-wide metrics to more specific ones (i.e., metrics of the application process) because we also make use of native system services and because mobile platforms do not frequently provide equivalent metrics. We use as metrics for device performance: the total CPU utilization and the system-wide used RAM memory. Quality of service metrics considered are the packet delay variation (also referred to as inter-arrival jitter, described in [START_REF] Schulzrinne | RTP: A Transport Protocol for Real-Time Applications[END_REF]) and packet loss ratio. The quality metrics are only provided for the case where the protocol is adapted. The values are obtained at the middleware level and should indicate the maximum bit-rate achievable while still providing satisfactory quality. The reference test cases, used to compare the overall performance, make use of system media services directly.

On Android mobile phones, the CPU and memory information is obtained by accessing the proc filesystem, used as an interface to the operating system kernel on most Linux based distributions. The logs are stored in the internal memory of both Android phones. To avoid that the access to the filesystem and data parsing are influencing the final results, the access to the /proc/stat and /proc/meminfo is done every five seconds, and the same file-descriptors are reused multiple times until the end of the test. On the iOS platform, system performance information was collected using the tools integrated with the development kit.

Translating to RTSP between Android smartphones

In this first experiment, we show that adaptation from the middleware intermediate protocol to RTSP/RTP/UDP is sufficiently efficient to be used in mobile multimedia-enabled applications. Since in this case the message format used by the client protocol is equivalent to the middleware transport protocol, the wrapping and unwrapping of messages is simpler than in other cases. Nevertheless, this client protocol is the only real-time streaming protocol currently available on mobile phones, and is thus interesting to analyze the feasibility of streaming real-time multimedia data through the middleware. Another experiment involving a more complex media format adaptation is presented at the end of this section. In this test we use two server implementations: one using the AmbiStream intermediate protocol and the other using RTSP. The RTSP server is not part of the solution but it is used in this experiment to determine the overhead of the adaptation (on the client-side) with reference to the native RTSP support. In the case of protocol translation to RTSP, the performance of the client device (realising the content and protocol adaptation) is not badly affected, with a processing overhead of less than 20% compared to a native RTSP session (see Fig. 5a). As with all of the experiments conducted, the memory usage remains constant, or increases slightly because of buffers required for higher data-rates (Fig. 5b). The fact that our solution uses slightly less memory than the reference one is due to the way jitter buffers are managed internally by the RTSP client, most probably being influenced by the different transport protocols (UDP and TCP). The quality of the stream remains within acceptable limits in terms of inter-arrival jitter (see Fig. 6a) and packet loss (Fig. 6b), for all the test cases (from 50 to 1500kbps) considered.

Translating to HLS between Android and iOS smartphones

The second experiment consists of translating the intermediate middleware protocol to HTTP Live Streaming, using two different client platforms: Android 2.3.4 and iOS 4.2.1. The choice of the smartphones is motivated by their native support of HLS. This way we can reason about the overhead introduced by our middleware layer with two different devices. Contrary to the first experiment, this one requires data conversion between RTP and MPEG-TS. MPEG-TS is one of the most used multimedia formats, most notably for digital television. The conversion from RTP to MPEG-TS requires a large number of transformations, thus providing a good impression of achievable on-the-fly conversion limits of media formats on current generation smartphones.

Because HLS protocol requires the existence of a cached amount of content on the server-side before a client can connect (and begin playback), while the intermediate AmbiStream protocol does not, a 30s start-up delay is introduced by the middleware layer to allow protocol translation. This aspect restricts the use of the middleware for real-time applications in this situation. This is not the case when the device supports a real-time protocol. During this delay period, less memory and CPU are used. To better evaluate the performance of the devices, we divide the experiment run in four periods (e.g., as shown in Fig. 7 for CPU utilisation): (I) the buffering period (only multimedia data adaptation is performed), (II) the media-player start-up (causes a short increase in CPU usage), (III) the streaming period (both data adaptation and playback are performed) and (IV) the stream-end (the source has finished streaming, but the playback is continued until buffer depletion). Thus, only the part (III) of the observation was used to produce the results presented in Figures 9 and10.

As expected, the difference in container formats (RTP and MPEG-TS), increases the overhead of AmbiStream. For Android platform, the tests for bit-rates inferior to 400kbps (in Figures 9a and9b) were discarded due to the existence of a minimal caching size, requiring a longer start-up delay. While on the Nexus One, the overhead introduced does not reach a quality limit for bit-rates below 1500kbps, the iPhone 3G is only able to adapt streams of up to 400kbps. Above this limit, the packet loss (see Fig. 8) becomes noticeable and the media- player suffers playback stalls. The results on the iPhone are worse due to the significantly lower processing power and memory (see Fig. 3). Nevertheless, according to the mobile platform providers, a 400kbps video bit-rate is considered to be medium/high quality for smartphones 10 11 . Considering the results in Figure 10b, we see that the memory usage is decreasing (in the case of AmbiStream) for higher video bit-rates. This behaviour is normal considering the packet loss (see Figure 8).

Conclusions and Future Work

In this paper we have identified the challenges raised by the heterogeneity of the streaming protocols of existing mobile phone platforms. Further, we have introduced the AmbiStream multimedia-oriented middleware architecture, designed to enable the multi-platform and multi-protocol interoperability of streaming services. We have also shown the applicability of the presented solution with an experiment on two different platforms and two different streaming protocols.

AmbiStream was modelled taking into consideration the architecture of modern smartphone platforms, such that resource critical operations (e.g., multimedia decoding) are managed by each platform internally. We prove that automated streaming protocol adaptation can be done locally on mobile phone platforms without sacrificing performance or extensibility. Furthermore, we enable legacy devices to employ unsupported streaming protocols by using an AmbiStreamenabled device as mediator intermediary.

We intend to continue this work by extending the current model, taking into account challenges such as routing over different networks and multi-peer collaboration. We will then integrate AmbiStream with iBICOOP [START_REF] Bennaceur | The iBICOOP middleware: Enablers and services for emerging pervasive computing environments[END_REF], a middleware designed to enrich the user collaboration and provide seamless access across different networks and devices. Such an integration will complement the existing solution with features such as discovery, distributed storage and partnership 10 http://developer.apple.com/library/ios/# technotes/tn2224/ index.html 11 http://developer.android.com/guide/appendix/media-formats.html management, enabling the development of rich cross-platform and multimediaenabled applications. We will also port the solution to Blackberry and Windows Phone to evaluate the approach on a greater number of mobile platforms.

Fig. 1 :

 1 Fig. 1: Multimedia streaming process

Fig. 5 :

 5 Fig. 5: AmbiStream performance on Nexus One (RTSP)

Fig. 6 :

 6 Fig. 6: Adapted stream quality (RTSP)

Fig. 7 :Fig. 8 :

 78 Fig. 7: Data capture (HLS)

Fig. 9 :

 9 Fig.9: AmbiStream performance on Nexus One (HLS)

Fig. 10 :

 10 Fig. 10: AmbiStream performance on iPhone 3G (HLS)

Table 1 :

 1 enables interleaving messages over the TCP control connection, but is not supported by most implementations. Protocols designed for video-on-demand scenarios, such as HLS and HDS, are almost equivalent in terms of functionality and concept, but differ in message formats and media containers. Audio/video decoders supported for streaming on smartphones

	Decoder / Platform	iOS Android BlackBerry OS Windows Phone 7
	H.263	-	+	+	-
	H.264	+	+	+	+
	MPEG-4	+	+	+	+
	AAC-LC, AAC+, eAAC+ +	+	+	+
	AMR-NB	-	+	+	+
	MP3	+	+	-	+

Table 3 :

 3 Test smartphones used

www.npr.org/services/mobile

www.nasa.gov/connect/apps.html

itunes.apple.com/us/app/netflix/id363590051

http://www.microsoft.com/silverlight/smoothstreaming/

http://www.macromediastudio.biz/products/httpdynamicstreaming/

Maximum transmission unit (less than 1500 bytes for Ethernet)

ISO/IEC 14496-12:2008

Acknowledgement. This work is partially supported by the FP7 ICT FET IP Project CONNECT.


E Delande

E Duflos

P Vanheeghe

D Heurguier

MULTI-SENSOR PHD BY SPACE PARTITIONING: COMPUTATION OF A TRUE REFERENCE DENSITY WITHIN THE PHD FRAMEWORK

Keywords: Probability Hypothesis Density, Multi-sensor system, Multi-target tracking

In a previous paper, the authors proposed an extension of the Probability Hypothesis Density (PHD), a well-known method for singlesensor multi-target tracking problems in a Bayesian framework, to the multi-sensor case. The true expression of the multi-sensor data update PHD equation was constructed using finite sets statistics (FISST) derivative techniques on functionals defined on multi-sensor and state space named "cross-terms". In this paper, an equivalent expression in a combinational form is provided, which allows an easier interpretation of the data update equation. Then, using the joint partitioning proposed by the authors in the previous paper, an exact multi-sensor multi-target PHD filter is efficiently propagated on a benchmark scenario involving 10 sensors and up to 10 simultaneous targets where the brute force approach would have been extremely burdensome. The availability of a true reference PHD then allows a validation of the classical iterated-corrector approximation method, albeit limited to the scope of the implemented scenario.

INTRODUCTION

In the general multi-sensor multi-target Bayesian framework, an unknown (and possibly varying) number of targets whose states x1, ...xn 1 are observed by several sensors which produce a collection of measurements z1, ..., zm at every time step k. Mahler's work on FISST ( [START_REF] Mahler | Handbook of Multisensor Data Fusion, chapter 14[END_REF]) provides a mathematical framework to build multi-object densities and derive the Bayesian rules. Randomness on object number and their states are encapsulated into random finite sets (RFS), namely multi-target (state) sets X = {x1, ..., xn} and multi-sensor (measurement) set Z k = {z1, ..., zm}. The objective is then to propagate the multi-target probability density f k|k (X|Z (k) ) using the Bayesian set equations at every time step k:

f k+1|k (X|Z (k) ) = f k+1|k (X|W )f k|k (W |Z (k) )δW (1)
f k+1|k+1 (X|Z (k+1) ) = f k+1 (Z k+1 |X)f k+1|k (X|Z (k) ) f k+1 (Z k+1 |W )f k+1|k (W |Z (k) )δW (2)
This work was supported by the Direction Générale de l'Armement (DGA) and the Centre National de la Recherche Scientifique (CNRS) 1 The target state x i ∈ X is usually composed of a position, a velocity, etc.

where Z (k) = t k Zt is the collection of measurements up to time k, f k|k (W |Z (k) ) is the current multi-target posterior density in set W , f k+1|k (X|W ) is the current multi-target Markov transition density, from set W to set X, f k+1 (Z|X) is the current multi-sensor multi-target likelihood function.

Even though equations ( 1), ( 2) are well built within the FISST framework, they are untractable because of the set integrals and the probability densities defined on multi-object spaces. Mahler proposed in [START_REF] Mahler | Multitarget bayes filtering via first-order multitarget moments[END_REF] to limit the propagation of the multi-target probability density f k|k (X|Z (k) ) to its first-moment density, the PHD D k|k (x|Z (k) ). The PHD encapsulates information on both target number and states but, being defined on the single-state space X , its propagation does not require the computation of cumbersome set integrals or multiobject densities. Under certain assumptions on the target motion and the observation models, Mahler provided in [START_REF] Mahler | Multitarget bayes filtering via first-order multitarget moments[END_REF] the tractable PHDequivalents of Bayesian set equations ( 1) and ( 2), the latter in the single-sensor case only.

In a previous paper ( [START_REF] Delande | Multisensor phd: construction and implementation by space partitioning[END_REF]), the authors extended Mahler's work and provided a true multi-sensor data update equation in a derivative form. Here, an equivalent expression in a combinational form is given; it allows an intuitive intepretation of the data update equation and made easier the comparison with Mahler's own extension to the two-sensor case ( [START_REF] Mahler | The multisensor phd filter, i: General solution via multitarget calculus[END_REF]), which turned to be conclusive. This paper also provides simulation results from the comparison between the PHD propagated by the true data update equation and by the classical iterated-corrector approximation on a given scenario. Note that the theoretical results presented here are more detailed in [START_REF] Delande | Multitarget phd filtering: proposition of extensions to the multi-sensor case[END_REF], and that a full understanding of this work requires some knowledge about FISST theory and calculus rules which may be found in [START_REF] Mahler | Handbook of Multisensor Data Fusion, chapter 14[END_REF].

MULTI-SENSOR DATA UPDATE EQUATION

Following the time update step and with the same assumption than exposed by Mahler ([2]), the updated distribution f k+1|k (X|Z (k) ) is assumed Poisson with parameter µ and intensity µs(x)2 . Since f k+1|k (X|Z (k) ) is Poisson, its intensity µs(x) equals the time updated PHD D k+1|k (x|Z (k) ) ( [START_REF] Mahler | Multitarget bayes filtering via first-order multitarget moments[END_REF]). Note that the following notations were chosen as close as possible to Mahler's work for clarity's sake.

Observation model

Assume that, following target transition between time steps k and k + 1, each sensor j ∈ [1 N ] produces measurements independently of the others according to the observation model described as follows:

• Target i is detected with probability p

[j] d (x i k+1 ) 3 ; • If detected, target i produces a single measurement z ∈ Z [j] with probability distribution f

O,[j] k+1 (z|x i k+1 ) = L [j]
z (x i k+1 ); • False alarms are Poisson with parameter λ [j] and intensity

[j] c [j] (z);

• Observation processes on each target are independent conditionally on the multi-target set X k+1 .

Cross-terms

Generalizing the single-sensor case led the authors to the introduction and the definition of the cross-terms ( [START_REF] Delande | Multitarget phd filtering: proposition of extensions to the multi-sensor case[END_REF]) which played an important role in the construction of the multi-sensor data update equation:

Definition 2.1. For each sensor j ∈ [1 N ], let g [j]
be a realvalued function on observation space Z [j] such that ∀z ∈ Z [j] , 0 g [j] (z) 1. Let h be a real-valued function on state space X such that ∀x ∈ X , 0 h(x) 1. The cross-term β[g [1] , ..., g [N ] , h] is the functional defined by: β[g [1] , ..., g [N ] , h]

= N j=1 (λ [j] c [j] [g [j] ] -λ [j] ) + µs h N j=1 1 -p [j] d + p [j] d p O,[j] g [j]
µ (3)

where p O,[j] g [j] (x) = g [j] (z)f O,[j]
k+1 (z|x)dz, c [j] [g [j] ] = g [j] (z)c [j] (z)dz and s[h] = h(x)s(x)dx.

Using FISST calculus rules ( [START_REF] Mahler | Multitarget bayes filtering via first-order multitarget moments[END_REF]), the cross-term β can be differention a single-target space point x ∈ X and/or an tuple of various single-sensor observation points z [j] ∈ Z [j] ( [START_REF] Delande | Multitarget phd filtering: proposition of extensions to the multi-sensor case[END_REF]). The analytical expressions of the differentiated cross-terms allows an intuitive interpretation as "likelihoods" 4 ; for example, with N = 3:

• δβ[g [1] ,g [2] ,g [3] ,h] δx g [i] =0,h=1

= µs(x)

3 j=1 1 -p [j] d (x) : a
target is in state x and was not detected by any sensor;

• δ 3 β[g [1]
,g [2] ,g [3] ,h] δxδz [1] δz [2] g

[i] =0,h=1 = µs(x) 2 j=1 p [j] d (x)L [j] z [j] (x) 1 -p [3]
d (x) : a target is in state x, generated measurements z [1] and z [2] and was not detected by sensor 3;

• δ 2 β[g [1]
,g [2] ,g [3] ,h] δz [1] δz [2] g

[i] =0,h=1 = µs 2 j=1 p [j] d L [j] z [j] 1 -p [3] d
: a single target generated measurements z [1] and z [2] and was not detected by sensor 3.

3 p

[j] d (.) = p [j]
d,k+1 (.), time subscripts are omitted for simplicity's sake 4 "Likelihood" should not be interpreted in its classical Bayesian sense Each cross-term above denotes a "likelihood" of a "link" between points in the single-state space X and/or the observation spaces Z [j] , hence their name.

Data update equation

Denote by Z

[j] k+1 = {z [j] 1 , ..., z [j] m[j]
} the set of current measurements produced by the j-th sensor, and by Z k+1 = (Z [START_REF] Mahler | Handbook of Multisensor Data Fusion, chapter 14[END_REF] k+1 , ..., Z

[N ] k+1 ) the current multi-sensor measurement set. The authors proposed in [START_REF] Delande | Multisensor phd: construction and implementation by space partitioning[END_REF] a multi-sensor data update equation constructed as a set differentiation of the cross-term β[g [1] , ..., g [N ] , h]:

D k+1|k+1 (x|Z (k+1) ) = δ δx δ m[1]+...+m[N ] δz [1] 1 ...δz [N ] m[N ] e β[g [1] ,...,g [N ] ,h] g [i] =0,h=1 δ m[1]+...+m[N ] δz [1] 1 ...δz [N ] m[N ] e β[g [1] ,...,g [N ] ,h] g [i] =0,h=1 (4)
Since a single target, if detected by sensor j at the current time step, cannot generate more than one measurement in Z [j] , one can expect β vanish if differentiated in at least two points from the same observation space Z [j] ; this is indeed the case within the FISST calculus rules. That is, remaining cross-terms in (4) are differentiated in measurements z [k 1 ] , ..., z [kn] from different sensors k1, ..., kn or, equivalently, on a tuple (z [k 1 ] , ..., z [kn] ) defined on the cartesian product Z [k 1 ] × ... × Z [kn] .

Thus, if we denote by:

• ŽN the set of (unordered) q-tuples, 1 q N , defined on current measurement set Z k+1 , with at most one measurement from each observation space; [1] , ..., g [N ] , h]

• For any tuple Ti = (z [k 1 ] , ..., z [kn] ) ∈ ŽN , β[Ti, h] the cross-term δ n δz [k 1 ] ...δz [kn] β[g
g [i] =0
. then (4) can be expanded as follows (see [START_REF] Delande | Multitarget phd filtering: proposition of extensions to the multi-sensor case[END_REF] for details):

D k+1|k+1 (x|Z (k+1) ) = β[∅, δx] + T ∈T ( ŽN ) T i ∈T     β[Ti, δx] T j ∈T T j =T i β[Tj, 1]     T ∈T ( ŽN ) T i ∈T β[Ti, 1] (5)
where:

• T ∈ P( ŽN ) is a combinational term, i.e. a set of tuples containing each measurement in Z k+1 once and only once; • T ( ŽN ) ⊆ P( ŽN ) is the set of all combinational terms. Note that equations ( 4) and ( 5) are different forms from the same multi-sensor data update equation and therefore are equivalent. The combinational form (5) provides an easier interpretation of the data update process since, similarly to the cross-terms, each combinational term can be interpreted intuitively as a "likelihood" linking the whole measurement set Z k+1 to the state space X .

For example, with N = 2 and Z k+1 = {z

[1] 1 , z [1] 2 , z [2]
1 }, one of the combinational terms is {(z

[1] 1 , z [2] 1 ), (z [1]
2 )} and it appears in [START_REF] Delande | Multitarget phd filtering: proposition of extensions to the multi-sensor case[END_REF] through the following products:

• β[(z [1] 1 , z [2] 1 ), 1]β[(z [1]
2 ), 1]: a target generated both z [START_REF] Mahler | Handbook of Multisensor Data Fusion, chapter 14[END_REF] 1 and z [START_REF] Mahler | Multitarget bayes filtering via first-order multitarget moments[END_REF] 1 , another source generated z [START_REF] Mahler | Handbook of Multisensor Data Fusion, chapter 14[END_REF] 2 only (either target or false alarm);

• β[(z [1] 1 , z [2] 1 ), δx]β[(z [1]
2 ), 1]: a target is in x and generated both z [START_REF] Mahler | Handbook of Multisensor Data Fusion, chapter 14[END_REF] 1 and z [START_REF] Mahler | Multitarget bayes filtering via first-order multitarget moments[END_REF] 1 , another source generated z [START_REF] Mahler | Handbook of Multisensor Data Fusion, chapter 14[END_REF] 2 only (either target or false alarm);

• β[(z [1] 1 , z [2] 1 ), 1]β[(z [1]
2 ), δx]: a target is in x, generated z [START_REF] Mahler | Handbook of Multisensor Data Fusion, chapter 14[END_REF] and was not detected by sensor 2, another target generated both z

Simplification by state and sensor partitioning

In [START_REF] Delande | Multitarget phd filtering: proposition of extensions to the multi-sensor case[END_REF] the authors showed that if the sensor FOVs do not all overlap with each other, many differentiated cross-terms are likely to vanish in the multi-sensor data update [START_REF] Delande | Multitarget phd filtering: proposition of extensions to the multi-sensor case[END_REF]. That is why the joint partitioning of the sensors and the state space was proposed ( [START_REF] Delande | Multitarget phd filtering: proposition of extensions to the multi-sensor case[END_REF], [START_REF] Delande | Multisensor phd: construction and implementation by space partitioning[END_REF]):

Definition 2.2. For any sensor j ∈ [1 N ], let F [j]
k+1 ⊂ X denote its field of view at time k + 1 defined as:

∀x ∈ X , x ∈ F [j] k+1 ⇔ p [j] d,k+1 (x) = 0 (6)
Define the equivalence relation "cross" (↔) between sensors as:

∀i, j ∈ [1 N ], (i ↔ j) ⇔ (F [i] k+1 ∩ F [j] k+1 = ∅) (7)
Let {PS(p)} P p=1 be the sensor partition of [1 N ] formed by the equivalence classes of the transitive closure of the "cross" relation. Let {PT (p)} P p=0 5 be the space partition of the state space X defined by: Then, equation ( 5) can be simplified ( [START_REF] Delande | Multitarget phd filtering: proposition of extensions to the multi-sensor case[END_REF]) and is equivalent to: where βp is the cross-term restricted to sensors j ∈ PS(p) ⊂ [1 N ] and to the subregion PT (p) ⊂ X , T ( Ž(p) Np ) is the set of combinational terms restricted to measurements from sensors j ∈ PS(p). As illustrated on a simple scenario in [START_REF] Delande | Multisensor phd: construction and implementation by space partitioning[END_REF], the "brute force" (5) and the partition method (9) both yield the true data updated density since (5) and (9) are equivalent, yet the partition method spares itself the computation of vanishing cross-terms and is therefore significantly lighter.

PT (p) =            N j=1 F [j] k+1 (p = 0) j∈P S (p)
D k+1|k+1 (x|Z (k+1) ) =                                    D k+1|k (x|Z (k) ) (x ∈ PT (0)) βp[∅, δx] + T ∈T ( Ž(p) Np ) T i ∈T     βp[Ti, δx] T j ∈T T j =T i βp[Tj, 1]     T ∈T ( Ž(p) Np ) T i ∈T βp[Ti, 1] (x ∈ Pt(p), p = 0) (9

SIMULATION

Since the single-sensor equivalent of equation ( 4) has a nice analytical expression and is easy to compute ( [START_REF] Mahler | Multitarget bayes filtering via first-order multitarget moments[END_REF]), Mahler introduced the classical iterated-corrector approximation in which the singlesensor data update equation is applied N successively, considering the measurements from sensor i at the i-th iteration. That the "iterated" method proceeds with sensors sequentially rather than in a whole. However, to the authors' knowledge, the quality of the approximation provided by the iterated method is unknown since it lacks a comparison with a true reference. The objective of this simulation is to evaluate the iterated method on a given scenario by comparing the PHD updated through the iterated method with the true reference PHD, available thanks to the partition method. The PHD multi-target tracker was implemented with a particle filter ( [START_REF] Vo | Sequential monte carlo methods for multi-target filtering with random finite sets[END_REF]), in this particular case the "cross" relation ( 7) is restricted as follows: two sensors j1, j2 are said to cross each other if and only if at least one particle xi belongs to both FOVs. Note (fig. 1) that the FOV configuration is such that the sensor partition at any time is a subdivision of the coarse partition {1-3-4-7, 2, 5-6-10, 8-9}. Thus, the computational gain of the partition method over the brute force approach is likely to be significant regardless of the particle spreading.

Scenario description

Results

The same scenario (i.e with identical target behavior) has been run 10 times, maintaining simultaneously a partition-based PHD and a iterated-based PHD. The two densities are compared through the estimated target number (fig. 2) and the OSPA distance [START_REF] Vo | Random Finite Sets in Multi-Object Filtering[END_REF] between the set of real targets and the sets of PHD-extracted estimated targets (fig. 3). These two figures show that, on this scenario, the iterated method has similar performances than the partition method; although it does not appear in this paper for lack of space, this is further illustrated by the almost identical trajectories in the 2D position subspace of the PHD-extracted tracks given by both methods. Since the partition method is based on the propagation of the true PHD, this comparaison provides grounds for a validation of the iterated method within the PHD framework, albeit limited to this scenario and depending on the particle filter approximation. Note that this comparison could not have been properly implemented with the brute force approach: propagating the true density in this scenario without the partitionning proved to be too computationally demanding on a desktop computer using Matlab (with some embedded C code) whereas each run was performed in about two and a half minutes with the partition method.

CONCLUSION AND FURTHER WORK

In this paper, a new formulation of the partioning method for the practical implementation of an exact multi-sensor multi-target PHD filter has been proposed. Thanks to this method, the computational cost of the implementation of the multi-sensor multi-target data update step is significanlty reduced whenever the configuration of the sensor FOVs is favorable to a partitioning. This method is of practical interest because it allows the efficient computation of a reference density which is exact in the sense of Bayesian inference within the PHD framework. In this paper, the classical iterated-corrector approximation was compared to the exact multi-sensor PHD filter,

F

  Finally, for any element PS(p) ot the sensor partition, let np = |PS(p)| denotes the number of sensors in PS(p), and let p1, ..., pn p denote the increasing indexes in [1 N ] of sensors belonging to PS(p).

) 5 {P

 5 S (p)} P p=1 = {P S,k+1 (p)} P k+1 p=1 and {P T (p)} P p=0 = {P T,k+1 (p)} P k+1 p=0 , time subscripts are omitted for simplicity's sake.

A

  target state x ∈ R 4 is composed of position (x, y) and velocity ( ẋ, ẏ) variables. Targets evolve according to a nearly constant velocity (NCV) model. The birth process is Poisson with a constant rate, new targets are spread uniformly in the state space. Targets die whenever reaching the edges of the 2-D position subspace. The test scenario lasts 500 time steps and involves up to 12 simultaneous targets. The ten sensors provide measurements with an independant Gaussian noise on range, bearing and eventually radial velocity. False alarms are Poisson and uniformly spread inside the FOV. Each sensor has its own set of sensing parameters (detection probability, FOV shape, false alarm rate, noise variances). Their FOVs are assumed fixed and spread as follows:

Fig. 1 :

 1 Fig. 1: Sensors' positions (dots) and FOVs in position subspace

Fig. 2 :Fig. 3 :

 23 Fig. 2: Target number (true and estimated)

µs(.) = µ k+1|k s k+1|k (.), time subscripts are omitted for simplicity's sake

available through the partition method, on a 10-sensor scenario. The results seem to indicate similar performances, for target number as well as target state estimation.Furthermore, the partitioning method seems to offer new perspectives on the multi-sensor PHD problem. First, the same comparison could be implemented on various scenarios in order to validate the iterated approximation method on a broader range of situations involving different sensor and/or target behaviors. Then, since the partitioning shows that the data update step can be processed independently each partition element of the state space, the authors believe that the approximation in the iterated-corrector method depends only on the order in which sensors are processed within their respective partition element rather than within all the sensors; should this result be verified, it could provide new leads for the resolution of the well-known sensor order issue in the various PHD iterative approximations. Finally, one may think of applying a similar partitioning technique in order to obtain a tractable PENT-based[START_REF] Mahler | Sensor management with non-ideal sensor dynamics[END_REF] multi-sensor manager; this is currently under consideration by the authors.


Duyhoa Ngo

Zohra Bellahsene

Remi Coletta

A Generic Approach for Combining Linguistic and Context Profile Metrics in Ontology Matching

Keywords: Ontology matching, matcher combination, context profile, linguistic metrics

Ontology matching is needed in many application domains. In this paper, we present a machine learning approach for combining metrics, which exploits various linguistic and context profiles features in order to discover mappings between entities of different ontologies. Our approach has been implemented and the experimental results over Benchmark and Conference test cases on OAEI 2010 campaign 1 demonstrate its effectiveness and efficiency in terms of quality of matching and flexibility.

Introduction

Numerous similarity metrics have been proposed so far for ontology mapping. According to [START_REF] Euzenat | Ontology matching[END_REF], element metrics can be categorized in three groups: terminological, structural and semantic matching-based techniques. Metrics in the first group exploit text features such as name, labels and comments to calculate the similarity score between entities; whereas metrics of the last two groups exploit the hierarchy and semantic relations features.

Despite the fact that metrics in the first group are less semantic than that of the second and third, they are widely used in most of the matchers. During the matching process, mappings discovered by these metrics can be used as input mappings to other metrics of the second and third groups. Obviously, the more precise results terminological metrics are the more accurate results structural and semantic metrics have. Therefore, the aim of designing a high performance quality matcher exploiting terminological features becomes an importance task.

Due to the various types of heterogeneity of data sources, there is no single best metric overall matching scenarios. It is beneficial and necessary to combine several methods for improving matching quality. However, it is very difficult and time consuming even for experts to find a good combination. Therefore, the use of supervised and machine learning approache is a promising way in order to reduce the required manual effort.

According to these necessity, we aim to build a high quality ontology matcher which utilizes machine learning approach to combine terminological similarity metrics. This matcher will be a premise for us to work in next step with structural and semantic matching methods.

The main contributions of this paper are the following. (i) We propose metrics dealing with terminological and context profile features of entities in ontology.

(ii) We propose to use decision tree model to combine similarity metrics and strategies to select metrics and training data for the learning process. (iii) Experimental results performed on the benchmark and conference tests of OAEI 2010 campaign show that our system achieved stable and good results in comparison with other participants.

This paper is organized into 5 sections. Section 2 presents similarity metrics working with terminological and context profile features. Next, Section 3 contains our approach for combining similarity metrics. In Section 4 we describe the setting of experiments and show experimental results. Finally, we conclude and plan future work in Section 5.

Feature Extraction and Similarity Metrics

Similarity Metrics for Terminological Features

Terminological features of an entity consist of text information encoded in itself in ontology such as entities' URI(name space and local name), labels and comments. Terminological metrics can be categorized in two main groups: stringbased and linguistic-based. String-based metrics take advantage of similar characters from two strings, whereas, linguistic-based metrics compare the meaning of strings.

Most of string-based metrics (e.g. Levenstein, SmithWaterman, JaroWikler, Qgrams, MongeElkan, etc.) are taken from open-source libraries SeconString2 and SimMetric3 . Additionally, we also implemented other string-based metrics such as Equality, Prefix, Suffix, Longest Common SubString [START_REF] Euzenat | Ontology matching[END_REF] and Stoilois [START_REF] Stoilos | A string metric for ontology alignment[END_REF]. To deal with linguistic features, we implemented Lin, JiangConrath and Wu-Palmer [START_REF] Lin | A survey of exploiting wordnet in ontology matching[END_REF] metrics working on WordNet4 dictionary.

Because ontologies are designed by different people, consequently, names or labels indicating even to the same object or concept may be heterogeneous. For example, "MscThesis" and "Ms.dissertation" are different but they both indicate a master's thesis. Due to the heterogeneity of naming convention, primitive string-based or linguistic-based metrics mentioned above may be not sufficient.

In order to deal with the heterogeneity problem, we perform analyses on terminological features of entities and propose solutions for each case.

Firstly, labels and names of entities usually are compound of tokens. The whole strings may be not matched but their tokens may be highly similar. Therefore, a pre-processing procedure is needed to split a string into proper tokens. Afterward, tokens can be compared by primitive string and linguistic metrics.

Secondly, tokens may exist in various types of morphological forms of a word. To deal with this issue, we need a thesaurus or dictionary. In our system, we propose a generic algorithm to combine string and linguistic metrics at token level as follows:

In the Algorithm 1, function MorphologicalForms takes a token as input and finds all possible senses and morphological forms of token existing in Wordnet dictionary. For example, MorphologicalForms("published") returns { verb: "publish" , adjective: "published"}; MorphologicalForms("publishing") returns { noun: "publishing", verb: "publish"}. Because two obtained sets of senses have a common {verb: "publish"}, therefore token "published" and token "publishing" are similar.

Algorithm 1: Compute similarity between two tokens

Input: token1, token2 two tokens, dictM etric a linguistic metric, stringM etric a string metric Output: score a numerical value

1 M F1 ← M orphologicalF orms(token1) 2 M F2 ← M orphologicalF orms(token2) 3 if (M F1 = ∅) ∧ (M F2 = ∅) then 4 score ← max (pos i ,st i )∈M F 1 ,(pos j ,st j )∈M F 2 (dictM etric(sti, stj) | posi = posj) 5 else score ← stringM etric(token1, token2)
Next, similarity score between two set of tokens is computed by two modifications of MongeEklan algortihms. One is proposed in [START_REF] Jimenez | Generalized mongue-elkan method for approximate text string comparison[END_REF] and the second is our proposal:

sim m (a, b) = 1 |a| |a| i=1 sigmoid(max{sim(a i , b j )} |b| j=1 ) (1)
Here, sigmoid(x) = 1 1+e -10×(x-0.5) is a promoted function which makes the higher similar tokens is more informative than the lower ones. The idea and effectiveness of using promoted function can be seen in [START_REF] Jimenez | Generalized mongue-elkan method for approximate text string comparison[END_REF] for more detail.

Thirdly, name of entity may be an abbreviation (e.g. "Misc." instead "Miscellaneous" ), an acronym (e.g. "SW" instead "Semantic Web") or even a sequence of symbols which is not understandable. To deal with these cases, we expect that entities provide some human-readable labels in annotation information. In our approach, a local name is treated as a label of entity. The similarity measure between two entities based on their labels can be formulated as follows:

sim(e i , e j ) = max (lp∈labels(ei), lq∈labels(ej )) (sim(l p , l q )) (2) For example, class Chapter in ontology #101 and class dzqndbzq in ontology #201 5 have the same label "BookPart". Therefore two classes are matched.

An entity may also have several comments. They usually consist of a long descriptive text. Therefore, calculating similarity of two comments by comparing word by word is not a good choice. In our approach, we use comments in building text profile for each entity. Calculating similarity based on entities' profiles are explained in detail in the next section.

Similarity Metrics for Context Profile Features

In order to take advantage of relations information in ontology, we build variety types of text profile for each entity from its context. We divide context profiles of entities into three groups: IndividualProfile, SemanticProfile and ExternalProfile. Let us demonstrate how to build these profiles following a fragment of ontology in Fig. The IndividualProfile of an entity is simply a string concatenation of its local name, labels and comments. For example: Individual profile of class Book is "Book Book A book that may be a monograph or a collection of written texts".

The SemanticProfile of an entity is an union of individual profiles of itself with individual profiles of its neighbors. Neighbors of a class consist of its sub-classes and all restricted properties. Neighbors of a property consist of its sub-properties, classes included in domain and range. For example: Semantic profile of class Book is created from individual profiles of {Monograph, title, publisher, author, edition}.

The ExternalProfile of an entity is created from texts taken from ontology instances. An external profile of a class is a string concatenation of texts of all instances belonging to either this class or its descendants. An external profile of a property is a string concatenation of value data corresponding to this property in all instances. For example: External profile of class Book is created from text value of instance a108048723. Therefore, external profile of class Book is "Object-oriented Data Modeling".

Having context profile for every entity, a similar technique described in [START_REF] Qu | Constructing virtual documents for ontology matching[END_REF] is used to compute similarity scores between entities. Let sim IP rof ile (e i , e j ), sim SP rof ile (e i , e j ) and sim EP rof ile (e i , e j ) are similarity scores between entities (e i , e j ) calculated by IndividualProfile, SemanticProfile and ExternalProfile respectively. To combine all of types of context profiles of entities, we propose the following generic formula:

sim(e i , e j ) = f (sim IP rof ile (e i , e j ), sim SP rof ile (e i , e j ), sim EP rof ile (e i , e j )) [START_REF] Euzenat | Ontology matching[END_REF] Where f may be weighted average, max, etc. If the combination function returns only similarity score achieved by SematicProfile, then our context profile metric is similar to metrics used in [START_REF] Cruz | Agreementmaker: Efficient matching for large real-world schemas and ontologies[END_REF][START_REF] Qu | Constructing virtual documents for ontology matching[END_REF]. If the combination function returns only similarity score achieved by ExternalProfile, then our context profile is similar to the instance-based metric. This property makes our context profile metric more flexible.

Combining Similarity Metrics with Decision Tree Model

We have implemented a system named YAM++ -an extension of [START_REF] Duchateau | A flexible approach for planning schema matching algorithms[END_REF], which is based on decision tree model to combine our proposed similarity metrics above.

In our approach, a decision tree is a tree whose non-leaf nodes are the similarity metrics, leaf nodes values are either 1.0 ore 0.0 indicating if there is a match or not. At a non-leaf node, a similarity value of to-be-matched entities is computed by the similarity metric in ongoing node. The returned value is compared with condition values on outgoing edges from current node in order to decide which child node will be reached. This process will start at root node and iterate until a leaf node is reached. The value of destination leaf node indicates whether the two entities should match or not. See [START_REF] Duchateau | A flexible approach for planning schema matching algorithms[END_REF] for more detail of the advantages of using decision tree model.

Experiments and Evaluations

Selection of Metrics and Training Data

In our system, similarity metrics are divided in three main groups: (i) name metrics exploit name feature; (ii) label metrics exploit label feature; (iii) context metrics exploit different types of context profiles. The selection of the most representative metrics for each group is based on the hypothesis "A good feature subset is one that contains features highly correlated with the class" [START_REF] Hall | Correlation-based feature selection for discrete and numeric class machine learning[END_REF]. The correlation value is calculated by Pearson's formula6 between similarity scores obtained by a metric and values provided by experts for each test in Benchmark datasets. Finally, the similarity metrics having the highest average values in each of three groups above are selected.

Next, training data for learning process are selected from Benchmark datasets. It is based on our heuristic: a training data is representative with the respect to a feature if this feature is highly correlated to the class. For each test in Benchmark datasets, our system computes the average correlation coefficient for all selected metrics above. Then, tests having the highest average of correlation values are selected to build training data.

Experimental Evaluations

Two experiments were designed as follows: (i) The first experiment shows the effectiveness of our proposed metrics in different scenarios over Benchmark datasets. (ii) The second experiment presents the performance quality of our approach on Conference datasets and shows the comparison results with other participants on OAEI 2010 campaign. Generally, our system achieves very high precisions (≈1.0) in all scenarios (Fig. 2a). This trend is exactly what we expected because our similarity metrics focus to high accuracy in calculating similarity scores between entities. Besides, the recall increases step by step thanks to adding metrics exploiting new features (Fig. 2b). Now, we look at particular scenarios in detail.

In the TestGroup1, our string, linguistic and their combination metrics work well. Based on these metrics, our system discovered most of commonly real patterns used to name entities (e.g., synonym, different naming conventions). However, there are other real patterns requiring more knowledge of domain, for example ("Academic", "StudentReport"), ("LectureNotes", "CourseMaterial"). That is why using only string and linguistic metrics (in SimSet1 and SimSet2) our system obtained good recall (≈0.8) but not ideal (1.0). Thanks to context metrics (in SimSet3 and SimSet4), more mappings have been discovered.

In the TestGroup2, with name metrics only, our system achieves 0.41 for recall. Although this value is low but it is the expected number. Let see the description on test ontologies in this group. The average number of altered names of entities is (20% + 40% + 60% + 80% + 100%)/5 = 60%. It mean that the maximum number of mappings found by name metrics is 100% -60% = 40%. This number is in line with the recall value (41%) obtained by our system. Similarly to TestGroup1, by adding new metrics (labels, contexts), our system discovered more mappings.

In the TestGroup3, recalls achieved by running with SimSet1, SimSet2 and SimSet3 are the same (0.41). That is because the test ontologies in this group do not support any annotation information. Only when running with SimSet4, thanks to ExternalContext profile, our system discovered more mappings.

Results on Conference datasets

In order to evaluate the performance of our approach with matching scenarios in another domain which is independent with training data, we select Conference datasets for testing. After running 10 times with different selected training datasets, we obtain precision (0.75), recall (0.52) and f-measure (0.61) in harmonic mean. Fig. 3 shows the performance quality of our system among participants in OAEI 2010 campaign.

Most of participants need to set a confidence threshold for finding mappings. Threshold values in the Fig. 3 are found for the optimal f-measure value for matchers. Like CODI system, we do not need to set threshold to our system. We obtain the second position (under CODI) in term of harmonic mean F-measure among all participants in campaign OAEI 2010. In this paper, we have proposed new similarity metrics exploiting both terminological and context profile features. We also proposed a machine learning approach to combine these similarity metrics. Experiments over OAEI datasets show that our proposed metrics work effectively. Our system achieved high position among participants of OAEI 2010 campaign in Conference track. Additionally, our combining approach is automatic, flexible and extensible. In the future work, we plan to integrate structural and semantic methods to our system in order to improve its performance.

1

 1

Fig. 1 .

 1 Fig. 1. Three types of context profile of class Book

  Result on Benchmark datasets According to terminological features described in Benchmark datasets, we select three representative groups of tests as follows: (i) TestGroup1 contains various types of naming convention using in designing real ontologies. The typical selected tests are: #104 (identical string), #204 (different naming conventions) and #205 (synonym words). (ii) TestGroup2: Names and labels of entities in test ontologies of this group are substituted by random meaningless strings. To discover mappings, we should take advantage from other features. We select tests #201, #201-2, #201-4, #201-6 and #201-8 for this group. Names and labels of entities in these tests are replaced by random strings with proportion 100%, 20%, 40%, 60% and 80% respectively. However, they support annotation information and data instances for entities. (iii) TestGroup3: Test ontologies in this group are similar to ontologies in the second group except that they do not support annotation information for entities. We select tests #202, #202-2, #202-4, #202-6 and #202-8 for this group. Tests in the first group are suitable for name and label

Fig. 2 .

 2 Fig. 2. H-mean of Precision and Recall on different scenarios

Fig. 3 .

 3 Fig. 3. Optimal results of participants in Conference track

http://oaei.ontologymatching.org

http://secondstring.sourceforge.net

http://sourceforge.net/projects/simmetrics

http://wordnet.princeton.edu

http://oaei.ontologymatching.org

http://en.wikipedia.org/wiki/Correlation and dependence

Supported by ANR DataRing ANR-08-VERSO-007-04.