Julien Haillot

Frédéric Guidec

Towards a Usenet-like Discussion System for Users of Disconnected MANETs

Applications that rely on the publish-subscribe model (such as those dedicated to news or event distribution) require a communication model whereby information can flow towards any interested receiver rather than towards set destinations. Content-based communication is a style of communication that perfectly fits the needs of such applications. Yet supporting this kind of communication in partially or intermittently connected mobile ad hoc networks (MANETs) is still a challenge, for end-to-end content-driven routing structures can hardly be constructed and maintained in such environments.

In this paper we provide an overview of a protocol we designed to support opportunistic, delay-tolerant, contentbased communication in a disconnected MANET. We also describe our project of using this protocol to implement a peer-to-peer, Usenet-inspired discussion system.

Introduction

The Internet has grown based on a technology enabling the deployment of a world-wide, resilient communication infrastructure. This infrastructure in turn has fostered the development and general acceptance of application services that rely on the traditional client-server model. In order to benefit from these services, users (or clients) need to connect to remote servers through long-distance, dependable communication links.

Mobile ad hoc communication now proposes an entirely different vision, in which human beings can be equipped with handheld devices capable of communicating directly with one another, based on proximate transmissions, and without relying on any kind of infrastructure network.

Consider the mobile ad hoc network (MANET) shown in Figure 1. This network is composed exclusively of usercarried devices, such as laptops, personal digital assistants (PDAs), tablet PCs, and smart phones. Its topology is therefore highly unstable and liable to change unpredictably as users get close to each other, or move away for a while. In such an environment, there is no guarantee that end-toend connectivity ever exists between any pair of handheld devices. Indeed, when devices are very sparsely or irregularly distributed, the whole network appears as a collection of distinct "islands". Communication between devices that belong to the same island is possible, but no temporaneous communication is possible between hosts that reside on distinct islands (such as between devices E and H in Fig. 1).

In such conditions, a method must be devised in order to allow communication between non-connected parts of the network. Delay-tolerant networking is an approach that can help with that respect [START_REF] Fall | A Delay-Tolerant Network Architecture for Challenged Internets[END_REF]. In a delay-tolerant network, a message can be stored temporarily on a host, in order to be forwarded later by this host when circumstances permit. If this network is a MANET, then mobility becomes an advantage, as it makes it possible for messages to propagate network-wide, using mobile hosts as carriers that can move between remote fragments of the network. Finally, since contacts between user-carried devices are usually hardly predictable, they must be exploited opportunistically for exchanging messages between these devices.

Opportunistic, delay-tolerant networking can thus help support communication in a disconnected MANET. Yet applications that require end-to-end, temporaneous connectivity between clients and servers can hardly be deployed in such an environment. Even asynchronous application services such as email or discussion groups must be revised if they are to be used in a disconnected MANET.

In this paper we address the dual problems of supporting communication in a disconnected MANET, and of implementing a realistic use-case application in such a challenged environment. We actually focus on supporting contentbased communication in a disconnected MANET. Contentbased communication is a style of communication that fits perfectly the needs of applications dedicated to information sharing. With this style of communication, the flow of information is interest-driven rather than destination-driven [START_REF] Carzaniga | Content-based Networking: a New Communication Infrastructure[END_REF]. Senders simply send (or "publish") information in the network without addressing it to any specific destination. Receivers specify the kind of information they are interested in (or "subscribe" to this kind of information), without regard to any specific source. In Section 2 we provide an overview of a protocol we designed in order to support this kind of communication in a disconnected MANET. In Section 3 we discuss our project of using this protocol to implement a peer-to-peer discussion service similar in principle to the legacy Usenet system. Like the Usenet system, this service should allow users equipped with handheld devices to post and selectively receive topical articles. Unlike the Usenet system, though, the service we consider should not rely on a distinct population of news servers for storing and providing articles on demand. Instead it should rely exclusively on the collaboration of handheld devices, so that articles disseminate by being stored, transported, and opportunistically exchanged by these devices. In Section 4 we discuss implementation details about this discussion system we plan to develop. Related work is mentioned in Section 5, and Section 6 concludes this paper.

A protocol for content-based networking in disconnected MANETs

In fully connected wired networks, content-based communication can be achieved by constructing an underlying communication system, whose role is to forward each piece of information from its sender to all interested hosts [START_REF] Carzaniga | Content-based Networking: a New Communication Infrastructure[END_REF]. This system is usually organised as a logical, content-driven routing infrastructure, which itself is implemented as an overlay network that covers the whole physical point-topoint network. This approach can hardly be applied in a disconnected MANET, since in such a network the absence of end-to-end connectivity between distinct islands precludes building any network-wide overlay. Consequently, the protocol we designed does not attempt to build any structure to support routing decisions. Instead it leverages on the principle of opportunistic, delay-tolerant networking. The general idea is to let neighbouring hosts opportunistically exchange pieces of information they are missing, based on their respective advertised profiles. A host that behaves as a receiver of a particular kind of information is expected to serve as a mobile carrier for this information, so while roaming the network it can help transport this information towards remote parts of this network.

Our protocol actually supports the content-driven dissemination of data units we refer to as "documents". A document is a structured piece of information a mobile host can publish in the network, so it can disseminate and ultimately be received by any host that shows interest for this particular kind of information. A document is composed of two parts: its descriptor, and its content (or payload). The descriptor can be perceived as a collection of attributes, which can provide any kind of information about the corresponding document, such as its identifier, its origin, its topic, a list of keywords, the type of its content, etc. It can typically be formatted in XML, as shown in Figure 2.

As a general rule, we assume that the size of a document is far greater than that of a descriptor, which is itself significantly greater than that of a document identifier. The protocol leverages systematically on this contrast in order to minimise the amounts of data exchanged by neighbouring hosts.

Each mobile host is characterised by its "interest profile", that is, a description of the kinds of documents it is interested in, and thus-implicitly-the kinds of documents for which it is willing to serve as a mobile carrier. For practical reasons, we define this profile as a predicate applicable to document descriptors. By applying this predicate to a descriptor, a host can decide if it must store the corresponding document in its cache or not. An example of a host's interest profile is shown in Figure 2. This profile can match any document whose descriptor refers to either the comp.networking newsgroup, or the comp.communication newsgroup, and that contains any of the specified keywords. (This profile therefore notably matches the descriptor shown in Fig. 2.)

Figure 3. Illustration of a transmission cycle around host A

The content-driven dissemination of documents in the network relies on a simple model, whereby transient contacts between mobile hosts are exploited opportunistically for exchanging documents between these hosts, according to their respective interest profiles. Each host periodically broadcasts an announce that combines a description of its own interest profile, and a catalog that contains the descriptors of locally cached documents that can be of interest to its neighbours (see Fig. 3.a). By broadcasting its own interest profile, a host lets its current neighbours know what kind of documents it is interested in. Conversely, by receiving similar information from its neighbours, each host can maintain an accurate vision of the kinds of documents they are interested in. Thus whenever a host needs to broadcast an announce, the catalog it contains can be adjusted in order to fit specifically the interest profiles of its neighbours. With this approach, the cost of broadcasting an announce periodically is kept at a minimum, as the size of the catalog a host broadcasts periodically is continuously adjusted in order to fit exactly the interest profiles of its current neighbours.

When a host discovers that one of its neighbours can provide a document it is interested in (that is, a document that matches its own interest profile and that is not already available in its own cache), it can request a copy of this document from this neighbour (Fig. 3.b). Upon receiving a request for a document that is available in its local cache, a host sends this document on the wireless channel (Fig. 3.c). Note that when a document is requested by several neighbours of the announcer, it is sent in broadcast mode, rather than being sent in unicast mode to each requester successively. This approach reduces the amount of duplicate transmissions on the wireless medium and, as a side-effect, it helps preserve the power-budget of mobile hosts.

This protocol has been fully implemented in Java, and embedded in DoDWAN 1 , a middleware platform we designed in order to evaluate and demonstrate the potential of opportunistic networking in challenged networking environments such as disconnected MANETs, vehicular net- works, or sensor networks. In its current implementation, DoDWAN relies on the transmission facilities of a standard IP protocol stack. Document descriptors are formatted in XML (as shown in Fig. 2), and all transmissions are performed by embedding control messages (i.e., announces and requests), descriptors, and documents in UDP datagrams. When a host needs to publish a large document (that cannot fit in a single UDP datagram), this document is segmented, and the resulting segments are encapsulated in a number of "fragment documents". These fragments are then published separately, so they can follow different routes in the MANET before being collected and reassembled only by hosts that are interested by the information they contain.

More details about the protocol can be found in [START_REF] Guidec | Opportunistic Content-Based Dissemination in Disconnected Mobile Ad Hoc Networks[END_REF], that also presents some of the results we obtained when evaluating its performance with a simulator, as well as in real conditions.

Towards a Usenet-like discussion service for disconnected MANETs

In this section we discuss the implementation of a peerto-peer discussion system that should make use of our content-based communication protocol, and provide users with a service that is inspired from the legacy Usenet system. We first give an overview of the Usenet system, highlighting its major characteristics, before considering the implementation of a system capable of providing similar services in an infrastructure-less wireless network.

Overview of the legacy Usenet architecture. Usenet is an effective, non-centralised discussion system that allows users to post topical articles to so-called newsgroups. It relies on a large, constantly changing set of interconnected servers, which are associated pair-wise in order to form a loose overlay over the physical Internet. Each server hosts a number of newsgroups, meaning it can store articles pertaining to these newsgroups, and provide these articles on demand to peer servers and to user-level client programs.

End-users must use a client program (a.k.a. newsreader) in order to access articles stored on a server. With such a program, a user can subscribe to some of the newsgroups hosted by the server, post new articles to these newsgroups, and fetch recent articles from the server. Peer servers synchronise regularly in order to exchange recent articles.

Interaction between peer servers, and between servers and clients, is supported by the Network News Transfer Protocol (NNTP). This protocol itself relies on TCP, which provides reliable, session-based data transport in IP networks.

A Usenet-like discussion system for disconnected MANETs. The Usenet system has been designed in order to rely on the resilient communication links provided by the Internet. Moreover, it leverages on a clear decoupling between clients and servers: users are assumed to run client programs, that must access remote servers in order to post or fetch new articles. Our objective is to design a discussion system we refer to as OppDNA (Opportunistic Dissemination of News Articles) in the remainder of this paper. The OppDNA system should closely mimic the Usenet system, while running exclusively on a collection of handheld mobile devices (such as laptops, PDAs, or smart-phones) interacting only based on proximate, ad hoc transmissions. With this system, a user should be able to post and receive topical articles, in a manner similar to that allowed by the Usenet system. Moreover, we would like to take benefit from the legacy software implemented in standard newsreaders, and from the fact that users are already familiar with such programs. Users should thus be allowed to rely on standard newsreaders (which are, basically, NNTP clients) in order to access newsgroups, even though the underlying system that maintains these newsgroups is liable to behave differently from that of the Usenet architecture.

In a disconnected MANET, no device can be considered as being stable enough, accessible enough, and resourceful enough to play the role of a dedicated news server. Consequently, the newsreader running on a user's handheld device cannot be associated with a stable, remote server. The solution we propose consists in having each device run a local pseudo-server, with which the user's newsreader can interact through NNTP sessions whenever the user wishes to either post or fetch new articles.

In the standard Usenet architecture, servers are administered explicitly by dedicated personnel. A server's administrator can create local newsgroups when needed. He is also responsible for deciding which newsgroups the server must host, with which peer servers (or "feeds") it should synchronise, and how often this synchronisation should be performed. In the OppDNA system, the owner of a handheld device must somehow be allowed to "administer" the OppDNA program running on this device. Since a hand- held device is usually severely resource-constrained, it is not reasonable to consider that a user should allow his device to host all newsgroups. Instead the list of locally hosted newsgroups should be defined cautiously by the user, considering how much storage resource can be devoted to this activity on the device, and selecting primarily newsgroups he is liable to subscribe to through his newsreader. Moreover, although Usenet administrators can rely on newsgroup lists (available world-wide) to select the newsgroups they wish to serve on their servers, this approach is not applicable in the OppDNA system. No device in a disconnected MANET can serve as a central repository for maintaining the list of all newsgroups. Instead a discovery mechanism is required for OppDNA users to learn about newsgroups.

Overview of the OppDNA system

General architecture. Figure 4 shows the general architecture of an OppDNA program. This program must run in the background on each mobile host that is expected to participate in the discussion system. It is organised in two main layers. The upper layer is in charge of managing newsgroups, and interact with the user's newsreader through a standard NNTP session. The lower layer manages the interactions of the OppDNA program with instances of the same program (or peers) that run on other mobile devices. In practise, whenever two mobile devices-and therefore two OppDNA peers-get in radio contact, they should use this opportunity to exchange articles pertaining to the newsgroups each peer is interested in. The content-based information dissemination protocol implemented in the DoD-WAN middleware (as described in Section 2) is perfectly suited to support such exchanges. Thus, whenever a user posts an article to a particular newsgroup, this article is simply passed from the newsreader to the associated OppDNA program. The article is first converted into a format the DoDWAN middleware can handle, and the resulting document is then deposited in the cache maintained by DoDWAN. Thence the article will disseminate among mobile devices by being passed opportunistically to any device whose advertised profile shows that it is interested in the newsgroup the article has been posted to.

Symmetrically, whenever the DoDWAN middleware obtains from a peer host an article that matches its "interest profile"-that is, an article that pertains to a newsgroup it has been ordered to host locally-this article is simply deposited in the local cache, and the upper layer of the Op-pDNA program is notified of this reception, so the article can be made available for the user's newsreader.

"Administration" of the OppDNA program. The interest profile that determines what kinds of documents the DoDWAN middleware should strive to collect from neighbouring devices must be set according to the user's preferences.

In the Usenet system, the newsreader can register the user's subscriptions, and fetch articles accordingly from the server. Yet it cannot instruct the server to subscribe to any newsgroup, as the server's subscriptions are controlled directly by its administrator. In the OppDNA system a method must be devised to allow a user to configure the local OppDNA program. Several alternatives can be considered, such as giving this program a user-friendly textual or graphical front-end. The approach we favour consists in using a dedicated "administration" newsgroup, and posting specially formatted articles to this newsgroup in order to pass instructions to the OppDNA program. Thus, assume a user wishes to create a new newsgroup called opportunistic.networking. This user simply needs to post to the oppdna.admin newsgroup an article with a Subject line of the form:

Subject: ANNOUNCE opportunistic.networking
The body of this article should contain a free-form description of the topics covered in this newsgroup.

By default the OppDNA program should be configured so as to receive all articles pertaining to the oppdna.admin newsgroup. A user that wishes to get informed about existing newsgroups therefore simply needs to read articles posted to oppdna.admin. Thus, assume that a user learns about the opportunistic.networking newsgroup, and decides that his handheld device should receive the corresponding articles (and therefore participate in their distribution in the network). This user can instruct the local OppDNA program to host this newsgroup, by "posting" to oppdna.admin an article with a Subject line of the form:

Subject: SUBSCRIBE opportunistic.networking
When such an article is received by the upper layer of the OppDNA program, it is not passed to the DoDWAN middleware. Instead the interest profile that rules the behaviour of the DoDWAN middleware is modified so that, from now on, it will strive to collect articles that pertain to the opportunistic.networking newsgroup.

The user can of course instruct the OppDNA program to stop hosting a particular newsgroup by posting an UNSUBSCRIBE command to the oppdna.admin newsgroup. The interest profile advertised by DoDWAN is then modified accordingly, and its cache is purged from all articles pertaining to this newsgroup.

Related work

A number of protocols have been designed in the last few years in order to support either destination-driven routing, plain broadcasting, or group-based multicasting in disconnected MANETs [START_REF] Zhang | Routing in Intermittently Connected Mobile Ad Hoc Networks and Delay Tolerant Networks: Overview and Challenges[END_REF][START_REF] Pelusi | Opportunistic Networking: Data Forwarding in Disconnected Mobile Ad Hoc Networks[END_REF][START_REF] Vahdat | Epidemic Routing for Partially Connected Ad Hoc Networks[END_REF][START_REF] Ott | Integrating DTN and MANET Routing[END_REF][START_REF] Karlsson | Delay-Tolerant Broadcasting[END_REF]. In contrast the support of content-based communication in such networks has not justified much research so far. A notable exception with that respect is [START_REF] Costa | Adaptive Content-Based Routing for Delay-Tolerant Mobile Ad Hoc Networks[END_REF], which describes an approach whereby a content-driven multi-hop routing structure (limited to a given horizon) is built around each host. A utility-based function is used to select the best carriers and/or forwarders for each kind of message, and mobile carriers are meant to transport messages between non-connected parts of the network. Our protocol relies on a slightly different approach. Instead of attempting to construct and maintain a routing structure, it relies on the principle of letting neighbouring hosts exchange documents they are missing, based on their respective advertised profiles. From this viewpoint it can be considered as being a member of the large family of gossipbased protocols [START_REF] Datta | Autonomous Gossiping: a Self-Organizing Epidemic Algorithm for Selective Information Dissemination in Mobile Ad-Hoc Networks[END_REF][START_REF] Baehni | Selective Information Dissemination in a Mobile Environment[END_REF].

Complementarily to papers addressing the development of communication protocols for disconnected MANETs, a few recent papers also discuss the design of applications capable of exploiting these protocols [START_REF] Scott | Haggle: a Networking Architecture Designed Around Mobile Users[END_REF][START_REF] Hyyryläinen | Opportunistic Email Distribution and Access in Challenged Heterogeneous Environments[END_REF][START_REF] Lenders | Wireless Ad Hoc Podcasting[END_REF]. Indeed, the very characteristics of opportunistic, delay-tolerant communication imply that these applications must be able to tolerate asynchronous-and possibly fail-prone-transmissions. Electronic mail (or E-mail) and news (or event) distribution are obvious candidates, as they can tolerate conditions in which temporaneous end-to-end connectivity between users is not guaranteed. Thus, several papers propose to rely on destination-driven, delay-tolerant routing protocols for implementing a messaging service capable of operating in a disconnected MANETs. [START_REF] Hyyryläinen | Opportunistic Email Distribution and Access in Challenged Heterogeneous Environments[END_REF] and [START_REF] Yoneki | Haggle Delivrable 6.1: User-Centred Design of Haggle Applications[END_REF] propose to link mobile hosts roaming a disconnected MANET with remote SMTP servers located in the wired Internet, using DTNenabled proxies or gateways as a means to bridge the gap between the disconnected and connected parts of the network.

Our project of implementing a discussion system for users of disconnected MANETs somehow differs from the abovementioned works. First, instead of relying on a destination-driven routing protocol for transporting messages towards a set destination, we rely on a contentdriven dissemination protocol for transporting topical arti-cles towards all interested receivers. Second, the system we describe relies exclusively on the collaboration of mobile devices without ever resorting to remote Internet-based servers (although a hybrid system allowing opportunistic synchronisations with NNTP servers is an option we consider for future work). Interestingly, [START_REF] Lenders | Wireless Ad Hoc Podcasting[END_REF] proposes to use a quite similar approach in order to allow mobile hosts to exchange typed content (such as small audio or video files), using topical channels as a means to selectively publishand subscribe for-different kinds of content.

Conclusion

In this paper we have provided an overview of a protocol we designed in order to support content-based delay-tolerant information dissemination in disconnected MANETs. This protocol opportunistically exploits transient contacts between mobile hosts for exchanging documents between these hosts, according to their respective interest profiles. We also presented our project of using this protocol to develop OppDNA (Opportunistic Dissemination of News Articles), a peer-to-peer discussion system that should be similar in principle to the legacy Usenet system, without relying on any server. OppDNA is meant to be used by users equipped with handheld devices. It should rely exclusively on the cooperation of these devices to disseminate newsgroup articles in the network. In the future we plan to give users of the OppDNA system a better control of the behaviour of their OppDNA-enabled handheld device, notably by setting priority levels on the newsgroups they host on this device. We would also like to give users the possibility to control the spatial and temporal scope of dissemination for the articles they post. Finally, we consider linking the OppDNA with the Usenet system, allowing OppDNA peers to post articles to-and fetch articles from-standard NNTP servers whenever they get a chance of connecting to the Internet.

Figure 1 .

 1 Figure 1. Illustration of a disconnected MANET composed of handheld devices

Figure 4 .

 4 Figure 4. Architecture of an OppDNA instance

Figure 2. Examples of a document's descrip- tor and of a host's interest profile

	<descriptor
	id="254d3g64z36cd"
	date="Fri Oct 12 09:52:11 CEST 2007"
	from="Fred"
	newsgroup="comp.networking"
	keywords="mobile,ad hoc,delay-tolerant,\
	opportunistic,gossip-based"	/>
	<profile
	newsgroup="comp.(networking|communication)"
	keywords="sensor|vehicular|opportunistic"	/>

Acknowledgements. This work is supported by the French Agence Nationale de la Recherche under contract ANR-05-SSIA-0002-01.


Frédéric Guidec

Yves Mahéo Valoria

Opportunistic Content-Based Dissemination in Disconnected Mobile Ad Hoc Networks

Content-based networking fosters a new kind of communication in which information flows towards interested hosts rather than towards specifically set destinations. Supporting this kind of communication in mobile ad hoc networks is still a challenge, though, especially in partially or intermittently connected networks. This paper addresses this problem by combining the concept of content-based communication with that of opportunistic networking. The protocol it describes exploits transient contacts between mobile hosts that exchange messages according to their respective interest profiles. A message thus disseminates in the network by being stored, carried, and forwarded by those hosts that

show some interest for this message. Experimental results as well as simulations confirm that this approach makes it possible to disseminate information efficiently, while minimising the resources implied in this dissemination.

Introduction

Content-based communication is a style of communication, whereby the flow of information is interest-driven rather than destination-driven [START_REF] Carzaniga | Content-based Networking: a New Communication Infrastructure[END_REF]. Receivers specify-or subscribe to-the kind of information that is of interest to them without regard to any specific source (unless that is one of the selection criteria). Senders simply send-or publish-information in the network without addressing it to any specific destination. The underlying communication system is responsible for delivering each message to those hosts that are interested in this kind of message.

Content-based communication allows a clear decoupling between senders and receivers. For this reason it is especially suited to being used in ubiquitous computing environments, in which it can serve as a communication paradigm for applications dedicated to information sharing, news distribution, service advertisement and discovery, etc.

In this paper we concentrate on the problem of supporting content-based communication in a disconnected mobile ad hoc network (MANET). A MANET is a network that is composed of a number of digital devices capable of communicating directly with one another using short-range wireless transmissions. Enabling technologies for building MANETs are Wi-Fi and Bluetooth. The topology of a MANET is often highly unstable and unpredictable, since it can evolve spontaneously as mobile devices themselves appear, move and disappear dynamically in/from the network. Furthermore, when the devices are very sparsely or irregularly distributed, temporaneous end-to-end connectivity between any pair of devices is not necessarily guaranteed. The network is then disconnected or partially connected. Figure 1 illustrates a typical example, where a disconnected MANET is composed of a number of user-carried laptops and PDAs. Notice that in such a scenario the devices are not within radio range of each other at all time. A device can for example be completely isolated at one time, and get close to one or several other devices at another time. In Fig. 1, device E is thus shown as being isolated (D is assumed to be in suspend mode), while B has two neighbours A and C. Another group of devices is shown in the distance. Although these remote devices are all close to one another, they are not within the transmission range of any member of the front group.

In connected wired networks, content-based communication can usually rely on a logical, content-based routing infrastructure, which itself can be implemented as an overlay network over the physical point-to-point network. This underlying infrastructure is then used to route each message towards interested hosts whenever needed [START_REF] Carzaniga | Content-based Networking: a New Communication Infrastructure[END_REF]. In contrast, in a disconnected MANET such as that shown in Fig. 1 there is no guarantee that a temporaneous end-to-end path (based on a succession of one-hop links) can ever exist between senders and interested receivers in the network.

In the remainder of this paper we present a protocol we designed in order to support content-based information dissemination in a disconnected MANET. While designing this protocol our main objectives were:

-to avoid building and maintaining an infrastructure for routing messages, as this approach is quite costly, and prone to fail in a non-connected environment;

1 A B C D E H G F A B C D E F G H (a)
-to avoid flooding the whole network with all messages, as this would amount to spamming mobile hosts with messages they are not necessarily interested in;

-to minimise the resources (wireless bandwidth, CPU, memory, etc.) involved in message dissemination.

The protocol we designed presents similarities with thesomehow more abstract-Autonomous Gossiping (A/G) algorithm [START_REF] Datta | Autonomous Gossiping: a Self-Organizing Epidemic Algorithm for Selective Information Dissemination in Mobile Ad-Hoc Networks[END_REF], with which it shares the abovementioned objectives, as well as the general approach of message dissemination. Basically, each message disseminates in the network by being stored, carried, and forwarded only by hosts that themselves have an interest for this kind of message.

Transient contacts between mobile hosts are exploited opportunistically for exchanging messages.

Notice that this approach requires that each mobile device has the ability to store messages before passing them to other interested devices when circumstances permit. This is actually the core principle of the DTN (Delay-Tolerant Networking) approach, as introduced in [START_REF] Fall | A Delay-Tolerant Network Architecture for Challenged Internets[END_REF]. It makes it possible for a message to eventually reach a destination that was not directly reachable at the time this message was sent originally in the network. For example, consider a message sent by device B in Fig. 1. This message may be received and stored by devices A and C (assuming they are interested by the message). A may then move towards F, G, and H, to which it could then forward the message. This simple example shows that the store, carry, and forward model makes it possible to compensate for the lack of end-to-end connectivity in a sparsely or irregularly populated MANET.

The remainder of this paper is organised as follows. The basics of our protocol are described in Section 2. Section 3 presents some of the results we obtained when evaluating this protocol in real conditions, as well as by running simulations. Related work is discussed in Section 4, and Section 5 concludes the paper.

Communication protocol

Overview

As mentioned in Section 1 our protocol is meant to be especially frugal with respect to the resources it consumes, and especially the wireless medium. For this reason it was designed so as minimise the global amount of data transmitted on the wireless medium, while avoiding unnecessary retransmissions. It notably uses broadcast transmissions rather than unicast transmissions whenever possible. Although broadcast transmissions are reputedly less reliable than unicast transmissions when using, for example, the Wi-Fi technology, experience shows that they can nevertheless give satisfactory delivery ratios, and at a far lesser price than a round of (point-to-point) unicast transmissions. Besides, because our protocol is meant to opportunistically exploit each contact between mobile hosts, it is inherently resilient to transmission failures. A host that fails to obtain a message from one its neighbours will hopefully get other chances to grab the same message later on (be it from the same neighbour, or from another one).

Our protocol is "document-oriented" rather than simply being "message-oriented". The main entities it relies on are briefly described below.

Documents, descriptors and identifiers -A document is composed of two parts: a descriptor and a payload. The descriptor can provide any kind of information about the document, such as its origin, its topic, a list of keywords, the type of its payload, etc. Basically, the descriptor can be perceived as a collection of attributes. Only two attributes must appear systematically in any descriptor: a unique document identifier, and a deadline (a document can disseminate in the network only until it reaches its deadline). As a general rule, we assume that the size of a document is far greater than that of a descriptor, which is itself significantly greater than that of a document identifier (typical orders of magnitude are O(10 kB) for a document, O(100 B) for its descriptor, and O(10 B) for its identifier). Our protocol leverages on this contrast between the size of a document and that of its descriptor or identifier whenever possible in order to minimise the amounts of data exchanged by neighbouring hosts.

Cache -Each host maintains a cache where documents can be stored. Although the protocol makes no assumption about the storage capacity on each mobile host, we recognise that this capacity is generally bounded, that it can be different on different hosts, and that each host can consequently implement its own caching policy.

Interest profile -Each host is assumed to be selective about the kinds of documents it is interested in. A host is thus characterised by its interest profile, which is a predicate we chose to restrict to document descriptors.

Protocol description

This protocol relies on a simple model whereby each host periodically informs its neighbours about its own interest profile and about the documents it maintains in its cache. Besides sending this announce periodically, each host simply reacts to messages it receives from neighbouring hosts. Basically a host iterates over a succession of three main phases, which are described below.

Announcing one's catalog and personal interest profile.

Each host n i periodically broadcasts a message that combines a description of its own interest profile prof (n i ) and a catalog cat (n i ) that is composed of the descriptors of locally cached documents that can be of interest to its neighbours. This catalog can occasionally be empty.

By broadcasting its own interest profile, a host lets its neighbours know what kind of documents it is interested in. Conversely, by receiving similar information from all its neighbours, each host can adjust the catalog it broadcasts periodically, thus avoiding to transmit a catalog pertaining to documents that cannot interest any of its current neighbours. This approach is consistent with our objective that the amount of data transmitted over the wireless medium should be minimised whenever possible.

In order to be selective about the documents it can propose to its neighbours, each host n i must maintain a collection of its neighbours' interest profiles, namely neighProf (n i ) = {prof (n j ) : n i and n j are neighbours}. This collection is used by host n i to calculate the catalog it must broadcast cat (n i ). The catalog is built by parsing the descriptors of all the documents that are available in n i 's local cache, and selecting among these descriptors those that match at least one of the profiles contained in neighProf (n i ).

Since the neighbourhood of each host can change continuously, the information a host maintains about this neighbourhood must also be adjusted continuously. In practise, neighProf (n i ) is reset to nil just after host n i has sent its catalog in the network. Afterwards, every time n i receives new information about one of its neighbours' profile, this information is inserted in neighProf (n i ). This approach allows host n i to keep only "fresh" information about its neighbourhood. Whenever it broadcasts its catalog, the profiles used to build this catalog are those of the neighbours host n i has heard about since the last time it sent its catalog.

Any host n j that receives a catalog from one of its neighbours n i (see Fig. 2-a) examines the descriptors it contains in order to identify documents whose characteristics match its own interest profile, and that are not already in its local cache. If there exist such documents, then n j builds a request that specifies the identifiers of the documents it would like to obtain from n j . This request is then sent to n i using a unicast transmission (see Fig. 2-b). This use of unicast transmission aims at avoiding that several neighbours of n j receive its request and assume that they are expected to answer to it. For example, in the configuration shown in Fig. 2-b the request sent by n 2 may be received by n 7 if it was not sent explicitly to n 1 . This would potentially lead to some documents being broadcast several times in answer to a single request, which is something we strive to avoid.

Processing requests. After sending its catalog, host n i may receive a number of requests from its neighbours. If n i receives no request, then it means either that it currently has no neighbour at all, or that none of its neighbours is interested in any document it can provide. Another reason might be either that the original catalog broadcast was lost, or that subsequent requests were lost, because of transient radio interferences. Such a failure is considered as being non-critical, as a mobile host that misses an opportunity to exchange documents with some of its neighbours will find many other opportunities to do so in the future (and possibly with different neighbours).

In any case, if n i receives no request after broadcasting its catalog, then no document will be broadcast unnecessarily. This is consistent with our objective that unnecessary transmissions should be avoided, and especially transmissions of documents since documents are assumed to be far larger than their descriptors.

If n i indeed receives a number of requests after broadcasting its catalog, then these requests are processed sequentially. For each document identifier that is mentioned in a request it has received from a neighbour n j , host n i retrieves the corresponding document from the local cache, and it broadcasts this document. Notice that this document is sent in broadcast mode rather than being sent only to n j in unicast mode. This is because, after host n i has broadcast its catalog, it may receive from its neighbours several requests for the same document. In such a case, all the neighbours requesting a specific document from host n i can be satisfied with a single broadcast of this document. For example, in Fig. 2-b host n 4 might request that n 1 send documents doc A and doc B , and host n 2 might request documents doc B and doc C . In order to avoid broadcasting the same document-such as doc B in this example-several times, host n 1 maintains a list L 1 of the identifiers of the documents it has broadcast since the last broadcast of its catalog. This list is reset to nil every time host n 1 rebroadcasts its catalog. When a given document is requested by one of its neighbours, host n i checks that this document has not already been broadcast recently. If the document's identifier appears in L i , then n i simply ignores the new request for this document. If the document's identifier is not in L i , then n i broadcasts the requested document, and adds its identifier in L i .

Receiving documents. When a document is broadcast, this transmission can be received by any neighbour of the sending host. Any host n k that receives a document verifies if the descriptor of this document matches its own interest profile and, if so, n k additionally verifies if this document is not already present in its local cache. If this is not the case, then n k puts the newly received document in its cache.

Notice that this communication model makes it possible for mobile hosts to collect documents they are interested in just by overhearing transmissions initiated by other hosts in their neighbourhood. A host n k can obtain a document by requesting explicitly this document from one of its neighbours n j , but it can also obtain this document because another host n l (which possibly is not even a neighbour of n k ) has requested that n j broadcast the document. Such a situation can occur because of the mobility and volatility of the hosts considered. For example a host that resumes from suspend mode, or that newly enters the radio range of the sender (like n 5 in Fig. 2-c), may receive a number of documents broadcast by one of its new neighbours, even though it has not received the catalog that was broadcast previously by this particular neighbour.

The experiments we have conducted confirm that this possibility for hosts to obtain documents they have not requested explicitly is an interesting consequence of our preferring broadcast transmissions to unicast transmissions whenever possible: a host that receives a document "just by chance" (and just because this document has been requested by another host) will later refrain from requesting this doc-ument explicitly, hence contributing to reduce the amount of transmissions in the network.

Evaluation

Demonstrator and simulation platforms. The protocol described in Section 2 has been fully implemented in Java, and embedded within the DoDWAN1 middleware platform. This demonstrator platform makes it possible to experiment with-and demonstrate-different kinds of applications (such as file sharing, news distribution, messaging, etc.) in disconnected MANETs. To date it has been deployed and used extensively on up to twenty laptops and PDAs with Wi-Fi capability. In order to evaluate how it can behave in larger networks, DoDWAN has also been interfaced with the MADHOC simulator [START_REF] Hogie | The MADHOC simulator[END_REF]. Based on this combination we run a number of simulations in order to observe how our protocol should perform in large networks, considering different kinds of mobility scenarios. The results of these simulations cannot all be described in the remainder of this paper because of size constraints. We thus only present some results we obtained when comparing our content-based, selective protocol and a non-selective dissemination protocol (referred to as the "greedy" protocol in the following).

Simulation parameters.

We consider a simulation scenario in which 120 hosts can move within a 1 km × 1 km area. Each host is assumed to be a user-carried laptop equipped with a Wi-Fi interface, with an omni-directional transmission range of 100 meters. In real life, a laptop is usually put in suspend mode while its owner is moving. The mobility model we used in this particular simulation run accounts for this observation: it extends the traditional random-waypoint model by switching a host "off" whenever it starts moving. In this particular simulation a host's speed could vary between 2 and 3 m/s, and a host could remain motionless (and was thus considered as being "on") for durations ranging between 30 seconds and 3 minutes. Communication scenario. Each active host sends a new 50 kB document in the network every 10 seconds. Since all hosts are not active simultaneously, new documents are introduced in the network at an average rate of one document every 2.5 seconds. Each document has a 60-minute lifetime, and it pertains to a specific topic. There are 16 different topics, but each host is interested in only 2 of these topics (hence 1/8 of the global traffic). No two different hosts in the network have exactly the same interest profile. Each host maintains a bounded cache, and whenever the cache is full one of the documents it contains is selected randomly and removed from the cache. Each host broadcasts an announce (containing its own profile and its catalog) every 15 seconds.

Reference protocol. In this particular simulation, our objective is to evaluate how our content-based, selective dissemination protocol performs, compared to a non-selective, more flooding-oriented approach. To achieve this goal we consider a variant of our selective protocol, in which each host behaves "greedily" with respect to the documents it can obtain from its neighbours. Basically, although each host is still interested in only a fraction of the documents that propagate in the network, it tries to obtain any document hold by its neighbours. A consequence of this greedy behaviour is that a host can benevolently store, carry, and forward documents it is not specifically interested in, but that might be of interest to some of its future neighbours.

Results. Figure 3 shows the evolution of the number of documents received by each host (on average), when using our selective protocol and its "greedy" counterpart. In the scenario used to produce these results, each host maintains a cache capable of storing 200 documents. In this figure the dotted line shows the number of documents sent in the network. It can be observed that with our selective protocol, the number of documents each host manages to receive from the network increases at a steady rate that is equivalent to the rate at which new documents are inserted in the network. The shift between the two curves along the x-axis corresponds to the time it takes for documents to disseminate in the network and reach interested hosts (that is, approximately 20 minutes with this scenario).

When using the greedy protocol, the number of documents received from the network increases rapidly at the beginning of the simulation, but shortly the curve falls below that of the selective protocol. This is because, at the beginning of the simulation, there is plenty of free space in each host's cache. Not surprisingly, the greedy approach is more efficient at disseminating documents in such circumstances, as it maximises the number of copies of each document in the network. However, with the greedy approach all caches saturate quickly and each host must remove documents (randomly chosen in this experiment) from its cache. Therefore some documents actually disappear from the network before they have reached all the interested hosts. This comparison shows that the selective approach is far more efficient at disseminating documents in the network, even though only a small subset of the hosts actually participate in the dissemination of each kind of document.

Table 1 compares the number of documents sent and received in the network using both protocols. These results were obtained by calculating the number of documents sent and received between time t=4000 and time t=12000 in the simulations shown in Fig 3 . The first line shows the rate at which documents are broadcast (or re-broadcast) in the network using each protocol. The selective protocol is obviously a lot less costly than the greedy protocol in terms of wireless medium bandwidth occupancy, as it consumes approximately 35 times less bandwidth for broadcasting documents. The second line in Table 1 shows that the greedy protocol is however less efficient in terms of document delivery, as it only manages to deliver 45 % of the documents, when the selective protocol gives a 98.4 % delivery ratio in the same conditions. Interestingly, the difference between the number of documents sent and received with the selective protocol shows that about 9 % of the document broadcasts benefit to more than one receiver. This confirms that by exploiting real broadcast transmissions at data-link level rather than multiple rounds of unicast transmissions, several hosts can occasionally benefit from the same transmission of a document.

Related work

A number of protocols have been designed in the last few years in order to support destination-driven routing in disconnected MANETs [START_REF] Zhang | Routing in Intermittently Connected Mobile Ad Hoc Networks and Delay Tolerant Networks: Overview and Challenges[END_REF][START_REF] Pelusi | Opportunistic Networking: Data Forwarding in Disconnected Mobile Ad Hoc Networks[END_REF]. In contrast content-based communication in such networks has not justified much research so far. Many papers about content-based communication have already been published, but most of these papers consider either stable, wired networks [START_REF] Carzaniga | Content-based Networking: a New Communication Infrastructure[END_REF][START_REF] Carzaniga | A Routing Scheme for Content-Based Networking[END_REF], or fully connected MANETs [START_REF] Baldoni | Content-Based Routing in Highly Dynamic Mobile Ad Hoc Networks[END_REF][START_REF] Costa | Semi-Probabilistic Content-Based Publish-Subscribe[END_REF][START_REF] Meier | STEAM: Event-Based Middleware for Wireless Ad Hoc Network[END_REF][START_REF] Petrovic | Content-Based Routing in Mobile Ad Hoc Networks[END_REF]. These papers usually propose to construct and maintain content-based routing structures in order to forward messages efficiently between publishers and subscribers. A notable exception with that respect is the protocol defined in [START_REF] Baldoni | Content-Based Routing in Highly Dynamic Mobile Ad Hoc Networks[END_REF]. Like ours this protocol does not attempt to build any structure to support routing decisions. Instead it relies (like ours) on broadcast transmissions, and it defers to hosts that receive a message the decision to forward this message to potential subscribers, based on an estimation of their distance from these subscribers. Yet this protocol requires that temporaneous end-to-end paths exist between senders and receivers. It could not run satisfactorily in a disconnected MANET.

Content-based dissemination in disconnected MANETs is addressed specifically in [START_REF] Costa | Adaptive Content-based Routing for Delay-tolerant Mobile Ad Hoc Networks[END_REF], which describes an approach whereby a content-driven multi-hop routing structure (limited to a given horizon) is built around each host. A utility-based function is used in order to select the best forwarders for each kind of message, and mobile carriers can help disseminate messages between non-connected parts of the network. Our protocol is somehow much simpler than that described in [START_REF] Costa | Adaptive Content-based Routing for Delay-tolerant Mobile Ad Hoc Networks[END_REF]. Like the Autonomous Gossiping algorithm described in [START_REF] Datta | Autonomous Gossiping: a Self-Organizing Epidemic Algorithm for Selective Information Dissemination in Mobile Ad-Hoc Networks[END_REF], it does not construct and maintain any routing structure. Instead it only exploits direct contacts between mobile hosts. The selection of carriers for a message is also straightforward: only those hosts that are interested by a message are enlisted as carriers for this message. Interestingly, experimental and simulation results confirm that in spite of its apparent simplicity this approach can give very good results in terms of message delivery, while consuming very few network resources.

Conclusion

In this paper we have presented a new protocol for content-based communication in disconnected mobile ad hoc networks. Unlike other protocols that rely on the construction of routing structures, our protocol only exploits opportunistic exchanges of documents between neighbouring nodes that present intersecting interest profiles. The dissemination of a document is thus performed only by hosts that show some interest for this document. Experimental results as well as large-scale simulations confirm that it is however efficient at disseminating documents, while minimising the resources consumed during their dissemination.

Figure 1 .

 1 Figure 1. Example of a disconnected MANET.

(a) n 1

 1 broadcasts its catalog.(b) n 1 receives requests from its neighbours.(c) n 1 broadcasts the requested documents.

Figure 2 .

 2 Figure 2. Transmission cycle around host n 1 .

Figure 3 .

 3 Figure 3. Comparison between the number of documents received using the selective and greedy protocols, for a bounded cache with a 200-document capacity.

Table 1 . Comparison of the number of docu- ments sent and received in the network using the selective and greedy protocols.

 1

	Protocol	Selective	Greedy
	# of doc. broadcast per s.	5.1 (×1)	179.5 (×35.2)
	# of doc. received per s.	5.6 (×1)	2.5 (×0.45)

DoDWAN stands for Document Dissemination in Wireless Ad hoc Networks.


Diogo Borges
email: diogobor@gmail.com

Mathieu Dupré

Magalie Duchateau

Quentin Giai

Julia Chamot-Rooke
email: julia.chamot-rooke@pasteur.fr

Using ProteoCombiner to integrate bottom-up and top-down proteomics data to improve proteoform identi cation

Keywords: proteomics, bioinformatics, top-down, bottom-up, mass spectrometry

Here we present a high-performance software for proteome analysis that combines different mass spectrometric approaches, such as, top-down for intact protein analyses and bottom-up, for proteolytic fragment characterization. ProteoCombiner capitalizes on the data arising from different experiments and proteomics search engines and presents the results in a user-friendly manner. Our tool also provides a rapid and easy visualization, manual validation and comparison of the identi ed proteoform sequences, including post-translational modi cations (PTM) characterization. Thus, ProteoCombiner is recommended for studies dealing with different proteomics strategies, in order to increase con dence in proteoform identi cation including PTMs.

Introduction

Proteoforms describe all combinatorial sources of variation from a single gene, including genetic variations, alternative splicing, and post-translational modi cations [1]. Proteoform analysis is nowadays of crucial importance since they have been proven to have a key role in biological systems [2] [3]. This includes both precise determination of the expressed sequence of the protein and the characterization of all Post Translational Modi cations (PTM), in particular their precise localization and determination of their combination (combinatorial PTM). Several proteomics strategies, including bottom-up, middle-down and top-down proteomics, have been developed to analyze the PTM at the peptide level or to directly target proteoforms. Nevertheless, there is a lack of bioinformatics tools able to combine such proteomics results and it is still di cult to map the PTMs identi ed in bottom-up data onto proteoforms obtained by top-down proteomics.

In this protocol, we describe the key steps for using ProteoCombiner, a powerful tool capable of integrating proteomics datasets obtained from different experiments (bottom-up and top-down proteomics) and different search engines, such as, PatternLab for Proteomics [START_REF] Carvalho | Integrated analysis of shotgun proteomic data with PatternLab for proteomics 4.0[END_REF], MaxQuant [START_REF] Cox | Andromeda: A Peptide Search Engine Integrated into the MaxQuant Environment[END_REF], Comet [START_REF] Eng | Comet: an open-source MS/MS sequence database search tool[END_REF], ProsightPD [START_REF]ProSightPD 1.1: Integrating Top Down Searching in Proteome Discoverer 2[END_REF], pTop [START_REF] Sun | pTop 1.0: A High-Accuracy and High-E ciency Search Engine for Intact Protein Identi cation[END_REF] and TopPIC [START_REF] Kou | TopPIC: a software tool for top-down mass spectrometry-based proteoform identi cation and characterization[END_REF], in order to increase the con dence of proteoform identi cation and facilitate the characterization of PTMs. A video demonstrating ProteoCombiner v1.0 in action is available at https://proteocombiner.pasteur.fr/video.

Reagents Equipment

Hardware

•

A computer with at least 8 GB RAM and 2 computing cores is recommended.

Software

• Windows 10 (32 or 64 bits) or later.

•

The .NET framework 4.7, which will be automatically updated by ProteoCombiner if necessary.

• ProteoCombiner software is available at https://proteocombiner.pasteur.fr.

Data les

• ProteoCombiner v1.0 is compatible with output data les from PatternLab for Proteomics [START_REF] Carvalho | Integrated analysis of shotgun proteomic data with PatternLab for proteomics 4.0[END_REF], MaxQuant [START_REF] Cox | Andromeda: A Peptide Search Engine Integrated into the MaxQuant Environment[END_REF], Comet [START_REF] Eng | Comet: an open-source MS/MS sequence database search tool[END_REF], ProsightPD [START_REF]ProSightPD 1.1: Integrating Top Down Searching in Proteome Discoverer 2[END_REF], pTop [START_REF] Sun | pTop 1.0: A High-Accuracy and High-E ciency Search Engine for Intact Protein Identi cation[END_REF] and TopPIC [START_REF] Kou | TopPIC: a software tool for top-down mass spectrometry-based proteoform identi cation and characterization[END_REF] and can work directly with Thermo®, ABSciex®, Agilent® and Waters® RAW les. The software is also compatible with mzML 1.1.0, MS2 and Mascot Generic Format (MGF).

•

ProteoCombiner saves results in its own format (i.e., *.pcmb) and exports them as Excel® (*.xlsx) and PDF® format les. Procedure 1.

Software installation: Download ProteoCombiner by clicking on the Download button at https://proteocombiner.pasteur.fr.

Work ow

The following work ow demonstrates how to combine proteomics data using ProteoCombiner.

2.1. Execute the ProteoCombiner tool (Figure 1)

[Figure 1]
2.2. Specify the directory containing all result les from bottom-up proteomics experiments. In this directory can also have the database used in the search and the original RAW les in one of these formats: mzML 1.1.0, MS2, Mascot Generic Format (MGF), ABSciex®, Agilent®, Waters® and Thermo® RAW.

2.2.1. Bottom-up proteomics 2.4.1. Remove Contaminants: This option allows to remove all protein sequences that represent a contaminant.

Remove

Reverse Sequence: This option allows to remove all decoy protein sequences.

2.5. To start combining data, click on the OK button in the Combine tab.

PS: Although ProteoCombiner capitalizes on the data arising from different proteomics search engines, we recommend using a single software-tool to analyze all experiments for proteolytic fragment characterization, and another to analyze intact proteins experiments.

Exploring the results

Note: At this point we recommend saving results by selecting Save from File menu or by pressing CTRL + S.

3.1. Filter 3.1.1. All results are pre-ltered according to the following parameters designated on the top of the Results Browser window, as shown in Figure 2: 3.1.1.1. CombScore: Results containing identi cation scores greater than or equal to this value will be displayed.

3.1.1.2. Peptide Count: Only identi ed proteins containing at least this value as identi ed peptide amount (by bottom-up) will be displayed.

3.1.1.3. Spectral Count: Only identi ed proteins containing at least this value as identi ed spectra amount will be displayed.

3.1.1.4. Unique peptide: Only identi ed proteins containing at least this value as identi ed unique peptide amount will be displayed.

3.1.1.5. Search: Only results from peptides or proteins containing the sequence input to this eld will be displayed. The user can further search by ProteinID (protein accession number), protein description or le name.

3.1.1.6. By clicking on Filter button, this operation is accomplished using all of the parameters described above.

3.1.1.7. By clicking on Reset button, all initial values are restored.

[Figure 2]

Combined results

All identi ed proteins that contain a valid sequence* will be displayed on this tab sorted by Score followed by Sequence Coverage. The protein score is represented by the best proteoform score.

*Protein sequence present in the database.

3.2.1. By clicking on an identi ed protein, all respective identi ed proteoforms will be displayed* below the protein table sorted by CombScore**.

*If there is no identi ed proteoform for a respective protein, all possible identi ed peptides will be displayed instead.

**CombScore is calculated by summing two different scores: i) a score related to the TDP identi cation software (which is normalized between 0 and 1; and ii) the percentage of the proteoform sequence coverage based on the peptides, obtained in BUP approach, that match to this proteoform. This score also ranges between 0 and 1.

3.2.1.1. The can assess each identi ed proteoform by clicking on the Is valid checkbox.

3.2.1.1.1. At this point, we recommend saving results once again so that the personal assessments can be included. This is done by selecting Save from File menu or by pressing CTRL + S.

3.2.1.2. By clicking on an identi ed proteoform, all respective identi ed peptides will be displayed below the proteoform table sorted by Peptide Score.

3.2.1.2.1 By double-clicking on an identi ed peptide, the tandem mass spectrum, which contains the best identi cation score, will be displayed on Spectrum Viewer. (Figure 3)

[Figure 3]
3.2.2. By double-clicking on an identi ed protein, a new window will be opened that shows the Protein Coverage (section

Bottom-up proteomics results

All identi ed proteins and the corresponding peptides will be displayed on this tab.

3.3.1. By clicking on an identi ed protein, all respective identi ed peptides will be displayed below the protein table.

3.3.1.1. By clicking on an identi ed peptide, all respective identi ed tandem mass spectra be displayed below the peptide table.

3.3.1.1.1. By double-clicking on an identi ed tandem mass spectrum, the Spectrum Viewer will be opened. (Figure 3) 3.3.2. double-clicking on an identi ed protein, a new window will be opened that shows the Protein Coverage (section 3.5).

Top-down proteomics results

All identi ed proteoforms will be displayed on this tab grouped by Theoretical Mass in Da.

3.4.1. By double-clicking on the Scan Number column of an identi ed proteoform, the Spectrum Viewer will be opened. (Figure 3). By clicking on any other column, new window will be opened that shows the Protein Coverage (section 3.5).

3.5. Protein Coverage 3.5.1. the window is opened, the information will be displayed on the top tab: Protein description, Monoisotopic and Average protein mass* and Sequence coverage. (Figure 4) *If Protein coverage window is opened from the click of a speci c proteoform, its monoisotopic and average mass will be displayed instead of the protein mass.

[Figure 4] 3.5.2. The left box will display all approaches used to identify the proteoforms and/or peptides. By clicking on each item, all respective lines will be high-lighted in the right box.

3.5.2.1. Bottom-up and middle-down approaches, represented by the blue color, 3.5.2.2. Top-down approach is represented in three different colors: Expected proteoforms in orange, which means all identi ed proteoforms by the full theoretical mass; non-expected proteoforms in cyan, which represents all identi ed truncated proteoforms; and tagged proteoforms in red, which means all proteoforms that identi ed by a part of the protein sequence.

3.5.2.3. All identi ed PTMs will also be displayed in this box.

3.5.3. The right box will display all identi ed proteoforms and/or peptides that will be represented by different lines. All of them will be displayed sorted by CombScore. On the top will be displayed the full protein sequence and all theoretical cations in the database) as can be seen in Figure 4.

All theoretical chains will be shown below protein sequence in gray dash lines. The user is able to check all information about the modi cation or theoretical chain by passing the mouse over the line or the modi ed amino acid. (Figure 4) 3.5.3.1. Each proteoform will be displayed according to the classi cation: expected, non-expected or tagged proteoform. By right-clicking on each line, the user is able to assess the proteoform identi cation (valid or invalid); in addition, it's possible to highlight only the peptides that t into the proteoform. (Figure 5). By hovering over each line, some information will be shown: Proteoform sequence, Score, Search engine that identi ed this speci c sequence, Start and End positions.

3.5.3.2. All identi ed PTMs will also be displayed and by hovering over each one, it is possible to check their position and description.

[ 3.6. Loading results 3.6.1. ProteoCombiner loads results in its own format (*.pcmb). This can be accomplished in three ways, the easiest one is by double-clicking on a ProteoCombiner results le. If the Results Browser window is opened, another way to launch the le is by clicking on Load option from the File menu or by pressing CTRL + O, as seen in (Figure 6). Otherwise, if the main window is opened, select Load Results from File menu (or press CTRL + O), as seen in Figure 7.

[

Protein coverage window: All identi ed proteoforms and/or peptides are displayed here in different lines.

The theoretical sequences (proteoforms) are displayed in gray dash lines and the theoretical PTMs above protein sequence. The information about the PTM and theoretical sequences are shown when the mouse is hovered over them.

An assessment can be applied for each identi ed proteoform in order to increase the con dence of the evaluation. The user can also highlight only peptides that t with a speci c proteoform.

Save or Load ProteoCombiner results from Results Browser window. The user can also export the results as an Excel® or PDF format le.

Figure 5 ] 3 . 5 . 3 . 3 .

 53533 The identi ed proteoforms and/or peptides can be displayed in a single line or in multiple lines. The user can change the way to visualize in Utils menu, by selecting Custom Protein Visualization option in Results Browser window (or by pressing ALT + C).

1 . 6 1 Graphical

 161 Figures

Figure 2 Filter

 2 Figure 2

Figure 3

 3 Figure 3

Acknowledgements

The authors thank the Agence Nationale de la Recherche (project ANR-15-CE18-0021) for nancial support. This work is also part of the European Joint Programme One Health EJP from the European Union's Horizon 2020 research and innovation programme (Grant Agreement 773830).

Load ProteoCombiner results from main interface.


domain: spi phys

text:
Yohann Constans

Sophie Fabre

Hervé Carfantan

Michael Seymour

Vincent Crombez

Xavier Briottet

Yannick Deville

Fusion of Panchromatic and Hyperspectral Images in the Reflective Domain by a Combinatorial Approach and Application to Urban Landscape

Keywords: Image fusion, panchromatic, hyperspectral, reflective domain, urban, combinatorial analysis

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

INTRODUCTION

Remote sensing applications for Earth observation require both high spatial and spectral resolutions. As sensor characteristics are limited and cannot simultaneously provide such resolutions, a solution is combining images jointly acquired by two different sensors. On the one hand, panchromatic (PAN) images provide high spatial resolution with one broad spectral band in the visible range [0.4 µm -0.8 µm]. On the other hand, hyperspectral (HS) images provide numerous spectral bands covering the reflective range [0.4 µm -2.5 µm], with a lower spatial resolution. This fusion process is called hyperspectral pansharpening (HS pansharpening).

A comparative study performed in the reflective domain highlighted the main limitations of these HS pansharpening methods [START_REF] Loncan | Hyperspectral pansharpening: A review[END_REF]. It notably showed that scenes with a strong spatial heterogeneity relatively to the spatial resolution of the hyperspectral sensor cause reconstruction errors by the fusion process. Indeed, these scenes induce mixed pixels (pixels whose spectrum is a combination of several material spectra), which are not well processed by HS pansharpening methods. This issue mainly affects urban areas, where 40-50 % of the pixels are mixed at a 4 m spatial resolution [START_REF] Wu | Quantifying high-resolution impervious surfaces using spectral mixture analysis[END_REF].

The Spatially Organized Spectral Unmixing method (SOSU) has been designed [START_REF] Loncan | Fusion of hyperspectral and panchromatic images with very high spatial resolution[END_REF] and recently improved [START_REF] Constans | Fusion of hyperspectral and panchromatic data by spectral unmixing in the reflective domain[END_REF] to handle this limitation. It is based on an existing fusion process for spatial information preservation, called the Gain method [START_REF] Constans | Fusion of hyperspectral and panchromatic data by spectral unmixing in the reflective domain[END_REF]. SOSU supplements Gain with a preprocessing step based on spectral unmixing and spatial reorganisation, to detect mixed pixels and better handle them. This preprocessing locally extracts spectra of pure materials constituting the scene (also called endmembers) from the HS image, and derives an image in which it judiciously assigns these endmembers to the different pixels, to follow the spatial organisation of the scene at the finer PAN spatial resolution. Notably, SOSU provided better results than Gain for agricultural and peri-urban scenes [START_REF] Constans | Fusion of hyperspectral and panchromatic data by spectral unmixing in the reflective domain[END_REF].

More recently, SOSU-2020 has been designed by adapting SOSU to urban scenes [START_REF] Constans | Fusion of hyperspectral and panchromatic data by spectral unmixing in the reflective domain[END_REF]. Associated results revealed that the spatial reorganisation step was not totally suited to complex urban landscapes. Indeed, this step was based on a combinatorial analysis of all possible combinations of pairs constituted of one homogeneous region and one endmember, and could not fully process mixed pixels implying a too large number of combinations. This significant proportion of non pre-processed mixed pixels (59 %) led to reconstruction errors as compared with errors provided by Gain.

The aim of the present article is to introduce an evolution of SOSU-2020, called SOSU-2021, which has been obtained by enhancing the spatial reorganisation step of the method to limit fusion errors for urban scenes (Section 2.2). We compare the fusion results obtained with SOSU-2021 for an urban dataset (Section 3) with those of SOSU-2020 and Gain (Section 4). To this end, we perform numerical and visual analyses, using spatial, spectral and global measures (Section 2.3).

METHODOLOGY

The presented method assumes the following hypotheses:

1. The HS and PAN images are fully registered, and the HS/PAN spatial resolution ratio, ρ, is an integer;

2. The HS and PAN images respectively cover the reflective and visible spectral domains; 3. All images consist of spectral radiances; 4. Each subpixel (i.e. pixel at the finer PAN spatial resolution) is pure (i.e. non-mixed), so its spectrum corresponds to one single endmember.

Presentation of the general SOSU method

The SOSU method includes six main steps, described in detail in [START_REF] Constans | Fusion of hyperspectral and panchromatic data by spectral unmixing in the reflective domain[END_REF] and [START_REF] Constans | Fusion of hyperspectral and panchromatic data by spectral unmixing in the reflective domain[END_REF]. The first five steps constitute SOSU preprocessing, whereas the last one is the fusion process:

1. The segmentation step aims to split the PAN image (which has the finer spatial resolution) into several regions of homogeneous radiance values; 2. Separately for each segmented region consisting of a set of HS pixels, the endmember extraction step estimates the associated endmembers; 3. The mixed pixel detection step identifies the mixed HS pixels from the radiance variations of the PAN image; 4. The endmember selection step gathers, for each mixed pixel (step 3), a list of possible endmembers depending on the corresponding segmented regions (steps 1 and 2) and the neighbouring pure pixels; 5. For each mixed pixel, the spatial reorganisation step assigns the right endmembers to the right subpixels (following hypothesis 4 in Section 2), to preserve as much as possible the spatial and spectral contents of the PAN and HS images. 6. The Gain process [START_REF] Constans | Fusion of hyperspectral and panchromatic data by spectral unmixing in the reflective domain[END_REF] inserts the spatial information from the PAN image into the reorganised one.

Improved step of SOSU-2021: spatial reorganisation

For each mixed pixel, step 5 performs a combinatorial analysis of every possible combinations of pairs constituted of one segmented region present in this mixed pixel (step 1) and one potential endmember (step 4). For a given combination, we generate the corresponding test pixel by assigning each chosen endmember to all the subpixels of the paired regions. The best combined test pixel is the one minimizing the reconstruction error (defined in Section 2.2.1) with the corresponding PAN and HS input pixels. In previous work [START_REF] Constans | Fusion of hyperspectral and panchromatic data by spectral unmixing in the reflective domain[END_REF], we recursively tested all the combinations. This method was limited by the number of combinations which could become very high and forced us to set a combination threshold (10 6 ), above which a mixed pixel could not be processed. In this article, we reformulate the full combinatorial analysis as an optimisation problem, to solve it with adapted solvers.

Integer programming model

The chosen combined pixel is the one which minimizes a linear combination of both PAN and HS reconstruction errors:

E tot = α • E HS + (1 -α) • E PAN ( 1
)
where α is a weighting parameter set between 0 and 1. E PAN and E HS are the normalized reconstruction errors respectively defined as:

       E PAN = j |P j -mean λ (R j,λ )| j P j E HS = λ |H λ -mean j (R j,λ )| λ H λ (2)
where j, λ and λ are indices respectively spanning the ρ × ρ associated subpixels, the spectral bands included in the reflective range and in the visible range; P j stands for the radiance value of the j th corresponding PAN subpixel; H λ represents the radiance value of the λ th spectral band of the corresponding HS pixel; and R j,λ stands for the radiance value of the λ th spectral band of the j th subpixel in the generated reconstructed pixel to be tested. The mean operators in the expressions of E PAN and E HS stand for integrations (consisting in weighted averages) on domains where the response of the measuring instrument is uniform. Thus, these integrations are mere unweighted averages.

The expression of the tested combined pixel R j,λ can be expressed in terms of combinatorial choices:

R j,λ = k e k,λ • I k,j (3)
where k is an index spanning the list of all the potential endmembers; e k,λ stands for the λ th band of the k th endmember of the list; and I k,j is a boolean variable equal to 1 if the k th endmember e k is assigned to the j th subpixel, 0 otherwise. We impose k I k,j = 1 ∀j, to ensure one single endmember is assigned to each subpixel (hypothesis 4, Section 2).

In addition, as all the subpixels of a single segmented region present in the mixed pixel correspond to the same endmember, I k,j can be expressed in terms of these regions:

I k,j =         
1 if e k assigned to region 1 and subpixel j ∈ region 1 1 if e k assigned to region 2 and subpixel j ∈ region 2 ... 0 otherwise (4) As a subpixel j belongs to one single region, one and only one of the conditions listed in Eq. ( 4) can be met, so we simplify all these conditions into a single sum:

I k,j = r I k,r • I j,r (5)
where r is an index spanning all the segmented regions in the processed mixed pixel, I j,r a boolean constant (fixed by the segmentation step) equal to 1 if and only if the j th subpixel belongs to the r th region, and I k,r a boolean variable equal to 1 if and only if the k th endmember is assigned to the r th region. This variable notably fulfills the sum-to-one conditions with respect to the index k (i.e. one endmember per region):

k I k,r = 1, ∀r (6)
Thus, E PAN and E HS can be expressed relatively to the region-endmember pairs thanks to the boolean variable I k,r , each other term being independent of the tested combination:

                 E PAN (I k,r ) = j |P j -1 N λ • λ k e k,λ • r I k,r • I j,r | j P j E HS (I k,r ) = λ |H λ -1 Nj • j k e k,λ • r I k,r • I j,r | λ H λ (7)
where N λ is the number of spectral bands in the visible range, and N j is the number of associated subpixels.

The absolute values, expressing the L 1 -norm used to quantify the error, can be converted into a linear problem of the boolean variable I k,r . Thus, both E PAN and E HS , and consequently E tot , can be treated as linear functions of I k,r . As the goal is to find the value of I k,r minimizing the cost function E tot (I k,r ) by respecting the sum-to-one constraints in Eq. ( 6), this whole step can therefore be regarded as a Mixed Integer Linear Programming (MILP) problem [START_REF] Linderoth | Noncommercial software for mixed-integer linear programming[END_REF].

Solving strategy

To process as many mixed pixels as possible, we jointly use two solvers adapted to the MILP case, namely COIN-OR branch and cut (CBC) [START_REF] Forrest | COIN branch and cut. COIN-OR[END_REF], and Solving Constraint Integer Programs (SCIP) [START_REF] Achterberg | SCIP: solving constraint integer programs[END_REF]. For a given mixed pixel, we start by applying the CBC solver. If a solution is not found, we apply the SCIP solver. If this second solver does not find a solution, we choose to keep the mixed pixel unchanged to avoid reorganisation errors which would degrade the fusion result. Therefore, in this case, we assign the spectrum of the mixed pixel to all subpixels covering the same area in the reorganised image.

To prevent too important time constraints, we apply a spectral downsampling to the endmembers and the HS spectrum used to model the HS reconstruction error. In the following, we set the downsampling factor to 3. For the PAN reconstuction error, which has a lower computational cost, we keep the chosen endmembers unchanged.

Performance assessment protocol

The proposed performance assessment method follows Wald's protocol [START_REF] Wald | Fusion of satellite images of different spatial resolutions: Assessing the quality of resulting images[END_REF], which consists in simulating the HS and PAN input images by degrading an initial HS image called the reference image, and then measuring the gap between the fused image and the reference image. To this end, we selected four adapted quality criteria, each of them focusing on evaluating the spatial or spectral quality of the fusion process: SAM (spectral), Cross-Correlation or CC (spatial), RMSE (global) and ERGAS (global). These quality criteria, detailed in our previous work [START_REF] Constans | Fusion of hyperspectral and panchromatic data by spectral unmixing in the reflective domain[END_REF], are complementary and among the most reliable criteria [START_REF] Pei | Performance evaluation of different references based image fusion quality metrics for quality assessment of remote sensing image fusion[END_REF]. In addition, we calculate the percentage of fully preprocessed mixed pixels, referred to as p.

DATA SET

The chosen reference image is extracted from an HS image of the city center of Toulouse (France), acquired at a 1.6 m spatial resolution in the reflective domain by the HySpex instrument during the 2012 UMBRA (ONERA-IGN) airborne campaign [START_REF] Adeline | Description de la campagne aéroportée umbra: Étude de l'impact anthropique sur les écosystèmes urbains et naturels avec des images thr multispectrales et hyperspectrales[END_REF]. The reference image covers a reduced scene (96 × 96 pixels) representing the Halle aux Grains and neighbouring buildings (Figure 1(b)). This scene is further detailed in [START_REF] Constans | Fusion of hyperspectral and panchromatic data by spectral unmixing in the reflective domain[END_REF]. After removing the spectral bands whose wavelengths correspond to an atmospheric transmission coefficient lower than 80 %, the reference image contains 234 spectral bands. Following Wald's protocol, we get the PAN image by spectral concatenation of all the spectral bands of the reference image included in the visible domain (Figure 1(a)), whereas we get the HS image by spatial averaging of all the ρ × ρ subpixels associated with each HS pixel (Figure 1(c)). Here, a ρ value of 4 has been chosen. Table 1. Criteria computed for mixed pixels.

Table 1 shows the quality criteria computed on mixed pixels for Gain, SOSU-2020 and SOSU-2021 with varying values of α for the spatial reorganisation step (see Section 2.2.1).

For the other steps of the method, the same parameters have been used for SOSU-2020 and SOSU-2021, as defined in [START_REF] Constans | Fusion of hyperspectral and panchromatic data by spectral unmixing in the reflective domain[END_REF]. Results reveal that SOSU-2021 always performs better and processes significantly more mixed pixels than SOSU-2020. Moreover, the higher α, the better the quality criteria and the percentage of pre-processed mixed pixels. However, increasing α also gives more weight to the HS reconstruction error, and thus fewer spatial details of the PAN image are preserved in the fused image. This phenomenon at the pixel scale can be confirmed by checking the percentages of mixed pixels which have a better or equal local SAM value with SOSU-2021 than with Gain. This percentage is 63 % with α = 0.1, but decreases to 56 % with α = 0.9. As a comparison, this percentage is only 47 % with SOSU-2020.

A compromise with α = 0.3 is visually depicted in Fig. 2. The image fragment fused with SOSU-2021 contains slightly fewer artifacts than the ones fused with SOSU-2020 and Gain alone (notably with the high-radiance reflective objects, identified in red boxes). In this article, SOSU-2021 has been applied to an urban dataset at a 1.6 m spatial resolution. It provided better numerical results and pre-processed a higher proportion of mixed pixels than SOSU-2020. Locally, from 56 % to 63 % of mixed pixels were better or equally treated by SOSU-2021 than with Gain, depending of the α parameter. However, increasing α also limited the preservation of the spatial information.

Our future work will include testing additional solvers to pre-process a larger proportion of mixed pixels, and evaluating the final method for multiple urban landscapes, with varying spatial resolutions (sampling rates and modulation transfer functions) and ρ values (from 2 to 10).

Fig. 1 .

 1 Fig. 1. PAN, reference and HS images (spatial resolutions in brackets) -Red-Green-Blue representations. 4. RESULTS AND DISCUSSION SAM ( • ) RMSE ERGAS CC p (%) Gain 8.1 4.2 8.1 0.93 / SOSU-2020 8.6 5.1 10.3 0.89 41 SOSU-2021 α = 0.1 8.5 4.8 9.6 0.91 71 α = 0.2 8.4 4.7 9.4 0.91 73 α = 0.3 8.3 4.7 9.3 0.91 75 α = 0.4 8.1 4.6 9.1 0.92 75 α = 0.5 8.0 4.6 9.1 0.92 79 α = 0.6 8.1 4.6 9.0 0.92 83 α = 0.7 8.0 4.4 8.7 0.92 86 α = 0.8 8.0 4.2 8.2 0.93 88 α = 0.9 8.0 4.2 8.1 0.93 88

Fig. 2 .

 2 Fig. 2. Fragments of the reference and fused images (1.6 m spatial resolutions) -Red-Green-Blue representations.5. CONCLUSIONSOSU-2021, a new version of SOSU which is more adapted to complex urban landscapes, has been obtained by modifying the spatial reorganisation step of SOSU-2020. To this end, we reformulated the combinatorial analysis of the spatial reorganisation step as a Mixed Integer Linear Programming optimisation problem, and used adapted solvers.In this article, SOSU-2021 has been applied to an urban dataset at a 1.6 m spatial resolution. It provided better numerical results and pre-processed a higher proportion of mixed pixels than SOSU-2020. Locally, from 56 % to 63 % of mixed pixels were better or equally treated by SOSU-2021 than with Gain, depending of the α parameter. However, increasing α also limited the preservation of the spatial information.Our future work will include testing additional solvers to pre-process a larger proportion of mixed pixels, and evaluating the final method for multiple urban landscapes, with varying spatial resolutions (sampling rates and modulation transfer functions) and ρ values (from 2 to 10).

ACKNOWLEDGMENT

The authors want to thank Sonia Cafieri and Marcel Mongeau for helpful discussions.