Abdulkader Benchi

Pascale Launay

Frédéric Guidec

JMS for Opportunistic Networks

Keywords: opportunistic networking, Java message service, message-oriented middleware

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

Introduction

Opportunistic networks constitute an appealing solution to complement fixed network infrastructures -or make up for the lack thereof-in challenged areas. In this type of mobile networks, contacts between devices are intermittent and are hardly predictable. Additionally, because of the sparse and irregular distribution of mobile devices, neither end-to-end connectivity nor transmission delays can be guaranteed. The many forwarding protocols designed for Mobile Ad hoc Networks (MANETs) over the last two decades are usually ineffective in such conditions. Unplanned radio contacts between neighbor devices must be exploited opportunistically instead, and network-wide information dissemination can only rely on the store-carry-and-forward principle: any Figure 1: Example of opportunistic network composed of user-carried mobile devices mobile device that gets an opportunity to obtain a message from a neighbor can serve as a mobile carrier (a.k.a. data mule) for this message for a while, and forward the message later to one or several other devices [START_REF] Khabbaz | Disruption-Tolerant Networking: a Comprehensive Survey on Recent Developments and Persisting Challenges[END_REF].

A typical opportunistic network is shown in Figure 1. In this example the mobile devices are smartphones, laptops or tablets carried by users. The network appears as a collection of distinct, continuously changing "islands" rather than as a single, connected network. Although no end-to-end path exists for example between islands 1 and 2, a user moving -deliberately or by chance-from island 1 to island 2 can serve as a carrier for messages addressed to devices located in island 2. The lack of end-to-end connectivity in the network is thus tolerated thanks to the mobility of devices. Yet there is no guarantee that a message ever gets delivered to its destination(s): message dissemination in an opportunistic network is a best-effort activity, which is directly constrained by how devices move and get in radio contact.

Many papers published in the last few years address the problem of supporting message dissemination in opportunistic networks (surveys can notably be found in [START_REF] Khabbaz | Disruption-Tolerant Networking: a Comprehensive Survey on Recent Developments and Persisting Challenges[END_REF][START_REF] Boldrini | Autonomic Behaviour of Opportunistic Network Routing[END_REF][START_REF] Nguyen | Routing in Opportunistic Networks[END_REF][START_REF] Triviño-Cabrera | Survey on Opportunistic Routing in Multihop Wireless Networks[END_REF][START_REF] Zhang | Delay/Disruption Tolerant Mobile Ad Hoc Networks: Latest Developments[END_REF]). In contrast, very little of them consider the problem of designing distributed applications capable of running in such challenged networks. Indeed designing applications that can tolerate long transmission delays and occasional -and sometimes frequent-message loss is a tedious task for developers. It is generally admitted that a peer-to-peer architecture should be preferred over a client-server one, because in most scenarios no device can be considered as stable and accessible enough to provide services to all other devices. Additionally, any form of synchronous interaction should be proscribed between different parts of a distributed application. Asynchronous communication is required in order to cope with long transmission delays.

The concept of middleware has long proved efficient in easing the development of distributed applications for traditional, fully-connected networks. It can be expected that carefully designed middleware systems bring similar benefits for opportunistic computing, that is, computing over opportunistic networks. Among the various types of middleware, message-oriented middleware (MOM) allows communication between application components by asynchronous message exchanges. This paradigm achieves decoupling of application components very naturally, making it well suited for developing distributed applications for opportunistic networks.

Despite a lack of standards defining MOM application programming interfaces (API), protocols and message formats, JMS (Java Message Service) is a MOM that is widely used by Java developers. Yet most existing JMS implementations have been designed for traditional wired networks, and they rely on server-based message repositories and name directories. Such implementations are clearly not usable in opportunistic networks, whose disconnected and continuously changing topology precludes resorting to a serverbased architecture.

In the remainder of this paper, we present JOMS (Java Opportunistic Message Service), a provider for JMS we designed specifically for opportunistic networks. Unlike other JMS providers JOMS uses a server-less model: message queues and topics are distributed in the network, and a distributed directory service is used to discover and locate destination objects. Additionally, message dissemination in the network relies on a content-driven epidemic model, whereas all mobile devices collaborate to disseminate messages network-wide.

The next sections of this article are structured as follows. Section 2 presents the general architecture and principles of JOMS, whose implementation is evaluated in Section 3. Related work is discussed in Section 4, and Section 5 concludes this paper and describes our plans for future work.

Java Opportunistic Message Service (JOMS)

Background

The Java Platform Enterprise Edition (Java EE) defines the JMS API, that specifies how MOM services are accessed, but not how those services should be implemented [START_REF] Hapner | Java Message Service API tutorial and Reference: Messaging for the J2EE Platform[END_REF]. The JMS specification defines two communication models: point-to-point and publishsubscribe. The point-to-point model is built on the concept of queues. A queue sender produces a message for a specific queue, from which a queue receiver can consume it asynchronously. This model provides one-to-one communication, since a given queue may have multiple senders and multiple receivers, but each message addressed to this queue by a sender can be consumed by one receiver only. The publish-subscribe model is based on the use of topics, that can be subscribed to by topic subscribers. Messages are published to a topic by topic publishers, and they can then be received asynchronously by all the corresponding topic subscribers. One message can thus be consumed by multiple subscribers. This model complements the point-to-point model in that it provides oneto-many communication.

Applications can learn about the available topics and queues (a.k.a., destination objects) through the Java Naming and Directory Interface (JNDI). JNDI is a Java API that provides a common interface to access various naming and directory services [START_REF] Lee | JNDI API Tutorial and Reference: Building Directory-enabled Java Applications[END_REF]. According to the JNDI specification, any directory service must provide a hierarchical structure, referred to as a namespace. Each name in a namespace is bound to an object and resides there until it is explicitly unbound. In a JMS-based application, a destination object is meant to be created via some administration tool, and bound to a name in a JNDI repository. From then on, applications typically use JNDI to discover names and look up the destination objects they require.

✐❞❂ ✏❢❢✼✽✾✑ ❞❡st✐♥❛t✐♦♥❴✐❞❂ ✏❙t✉❞❡♥t•r♦✉♣✑ ❞❡st✐♥❛t✐♦♥❴t②♣❡❂ ✏t♦♣✐❝✑ ❞❡❛❞•✐♥❡❂ ✏ ▼♦♥ ▼❛r ✷✹ ✷✵✿✺✹✿✵✸ ❈❊❚ ✷✵✶✹✑ •❛♥❣✉❛❣❡❂ ✏❊♥❣•✐s❤✑ (a) ❞❡st✐♥❛t✐♦♥❴✐❞❂ ✏❙t✉❞❡♥t•r♦✉♣✑ ❞❡st✐♥❛t✐♦♥❴t②♣❡❂ ✏t♦♣✐❝✑ •❛♥❣✉❛❣❡❂ ✏❊♥❣•✐s❤✑ (b) ✐❞❂ ✏❜✹✸❞❛✑ ❞❡st✐♥❛t✐♦♥❴✐❞ ❂ ✏❆•❛♥❅✶✸✼✷✺❢❝✼✼❞✑ ❞❡st✐♥❛t✐♦♥❴t②♣❡❂ ✏q✉❡✉❡✑ ♦♣❡r❛t✐♦♥❴t②♣❡❂ ✏r❡q✉❡st✑ ❞❡❛❞•✐♥❡❂ ✏ ❙❛t ▼❛r ✶✺ ✷✵✿✺✹✿✵✸ ❈❊❚ ✷✵✶✹✑ (c) ❞❡st✐♥❛t✐♦♥❴✐❞❂ ✏❆•❛♥❅✶✸✼✷✺❢❝✼✼❞✑ ❞❡st✐♥❛t✐♦♥❴t②♣❡❂ ✏q✉❡✉❡✑ (d)
The JMS API is widely used to develop distributed applications for traditional networks. It is commonly admitted that it helps software engineers build distributed systems that communicate in a loosely-coupled asynchronous manner. Many providers implement the JMS API for various deployment environments. Most of these providers rely on TCP, though, and they assume a synchronous or quasi-synchronous reliable communication layer. Some JMS providers have also been proposed for mobile ad hoc networks, but none of them is usable in opportunistic networks because they cannot cope with the absence of end-to-end connectivity in such networks.

JOMS (Java Opportunistic Message Service) has been designed specifically to meet the needs of application developers targeting opportunistic networks. It is architectured as a two-layer system: the lower layer is devoted to supporting communication in an opportunistic network, while the upper layer provides JMS on top of this communication service. The upper layer is actually composed of two parts: the JMS provider per se, and a distributed directory service that complies with the JNDI specification. These three elements are detailed below.

Communication Layer

The communication layer implements a content-driven message dissemination model: messages flow towards interested receivers rather than towards specifically set destinations, and each receiver can serve as a "data mule", carrying messages for a while in a local cache so they can be transferred later to other interested receivers.

The communication layer in JOMS provides higher-layer services with a publish/subscribe API. Each message is given a descriptor that characterizes its content. This descriptor is composed of (name, value) tuples, as illustrated in Figure 2a and Figure 2c. An application service that needs to receive a particular type of messages must use the API to set a subscription accordingly. A subscription is characterized by a selection pattern, whose structure is similar to that of descriptors (see Figure 2b and Figure 2d). The interest profile of a device is basically a compilation of all the selection patterns that characterize local subscriptions.

The interaction scheme implemented in the communication layer takes inspiration from the Autonomous Gossiping (A/G) algorithm [START_REF] Datta | Autonomous Gossiping: A Self-Organizing Epidemic Algorithm for Selective Information Dissemination in Wireless Mobile Ad-Hoc Networks[END_REF], which itself defines a selective version of the epidemic routing model proposed in [START_REF] Vahdat | Epidemic Routing for Partially Connected Ad Hoc Networks[END_REF]. Each host periodically broadcasts an announcement in order to inform its neighbors (if any) about its identity and interest profile. By sending such an announcement periodically, a node informs its neighbors about its presence and about the kinds of messages it is interested in. Conversely, by receiving similar announcements a host discovers its neighbors, and learns about their own interest profiles. By matching its neighbor's profiles against the descriptors of the messages it maintains in its cache, a host can select descriptors of messages that might be of interest to at least one of its current neighbors. It can thus build an offer containing these descriptors, and incorporate this offer in its next announcement. Upon receiving such an offer, each host matches the descriptors it contains against its own interest profile in order to identify messages that match this profile and that are not already present in its local cache. If such messages are identified, then a request for these messages is sent to the announcer, which complies by sending the missing messages on the radio channel. Finally, when a host receives a message it has requested, this message is put in the local cache so it can later be proposed to other hosts met while moving in the network.

Figure 3 illustrates the gossiping between two hosts H1 and H2 as they exchange messages. In this example we can assume that H1 and H2 are within mutual transmission range, but that they are sometimes in suspend mode (though not necessarily at the same time). The same behavior could be obtained with these hosts moving and getting in a transient radio contact, though.

An application process P2 on H2 first publishes several messages a, b, c... j (label <1> in Fig. 3). Since H2 has no neighbor at that time, these messages are simply put in the host's local cache. H2 then enters suspend mode for a while (label <2>). H1 is started (for the first time, or resuming from suspend mode), and an application process on that host subscribes to receive messages that match a specific selection pattern (label <3>). H1 then begins announcing its presence, with an interest profile that includes the pattern specified by process P1 (label <4>). These announcements are not received by any host, though, since H1 currently has no neighbor.

H2 resumes (label <5>), and shortly after that it receives an announcement broadcast by H1 (label <6>). H2 thus discovers this neighbor, and it simultaneously learns what kind of messages H1 is interested in. Based on H1's interest profile, H2 can check its local cache and identify messages whose descriptors match this profile. H2 can thus sends an offer to H1 (label <7>). Upon receiving this offer H1 determines which of the Figure 3: Interaction diagram between two hosts exchanging a message offered messages it would actually like to receive (i.e., messages that are not already in its own local cache), and sends a request accordingly to H2 (label <8>). For each message thus requested, H2 sends the message to H1 (label <9>) and waits for an acknowledgement before sending the next message (label <11>). Each message received by H1 is put in the local cache, and the handler of the application process is called in order to process the message (label <10>). Although this is not represented in Fig. 3 for the sake of clarity, this interaction pattern involving H2 providing messages to H1 is also run symmetrically: H1 may likewise provide H2 with messages that match its own interest profile. Moreover, H1 and H2 may simultaneously be interacting with several other neighbor hosts. Finally, the interaction procedure between two hosts is stateless and can thus be interrupted at any time: both hosts will simply detect that they have lost a neighbor, and act accordingly.

Further details about this interaction schema and about how it performs in real conditions can be found in [START_REF] Haillot | A Protocol for Content-Based Communication in Disconnected Mobile Ad Hoc Networks[END_REF].

As a general rule, a host that subscribes to receive a particular kind of message is expected to serve as a mobile carrier for this kind of message. Yet a host can also be configured so as to serve as an altruistic carrier for messages that present no interest to the application services it runs locally. This behavior is optional, though, and it must be enabled explicitly by an administrator of the DoDWAN platform.

Cache overloading and network congestion are avoided by setting a deadline for each message. Whenever a message gets out of date, all copies of this message are removed from caches, so it stops disseminating in the network.

Directory Service

Application components must look up the JMS destination objects -topics or queuesthey intend to use in a directory service. The JMS specification states that objects discovery must be made through the JNDI API [START_REF] Lee | JNDI API Tutorial and Reference: Building Directory-enabled Java Applications[END_REF]. JOMS implements a distributed directory service, which complies with this API. Each host maintains a local directory that acts as a local namespace, from which application services can look up destination objects. When a destination object is created on a device, an entry for this object is added to the local namespace, and JOMS starts disseminating an advertisement about it. Devices that receive this advertisement update their own namespace accordingly.

An entry in a namespace must be characterized by a unique name. Topics created on different devices with the same name are considered as being the same topic, for all messages published in that topic will be received by all subscribers. In contrast queues must have unique names, as each queue is to be maintained on a single device (as explained in the next section). When a queue is created, the name specified by the user is appended with the local device's identifier, which is provided by the communication layer (this identifier can for example be the IMEI on a smartphone, or an auto-configured link-local IPv6 address). Figure 2c and Figure 2d respectively show a descriptor and a pattern that both refer to a queue whose identifier is "Alan@0013725fc77d".

The JNDI API defines primitives to unbind objects from a repository. Disseminating an unbind advertisement for an object in an opportunistic network does not ensure that the dissemination of the corresponding binding advertisement will effectively be stopped. For this reason, JOMS adds a deadline to JNDI entries in order to delete obsolete destination objects. A refresh mechanism is used to reset the deadline of entries automatically, as long as they are used by application services: whenever a device sends or receives a message to/from a specified destination object, the deadline for the corresponding entry is systematically prolonged in this device's namespace.

JMS Provider

According to the JMS specification, a JMS message is composed of a header, properties, and a body [START_REF] Hapner | Java Message Service API tutorial and Reference: Messaging for the J2EE Platform[END_REF]. The header and properties contain fields for the identification, control and routing of messages. JOMS uses those fields to manage the opportunistic dissemination of messages. The message body carries the message content. Its content is ignored by JOMS, which considers it as a simple payload. JOMS introduces a few discrepancies with respect to the standard JMS properties, in order to deal with the nature of opportunistic networks. Specifically, fields JMSExpiration and JMSMessageID are required in JOMS, while they are optional according to the JMS specification.

The JMS publish-subscribe model maps well to the communication API of JOMS. Messages published in a given topic are tagged with the topic name, as shown in Figure 2a. All subscribers to a topic define a pattern with this topic's name in their interest profile (see Figure 2b). Thus, a message for a given topic disseminates in the network thanks to the topic's subscribers that serve as data mules and carry it in their local cache. Topic subscribers can filter out messages beyond the topic name, though, using a selector property as defined in the JMS specification. This property is added to the interest profile, so message filtering is processed by the opportunistic content-based communication layer.

With the point-to-point model, a message sent to a queue must be consumed by only one queue receiver. In order to enforce this rule, each queue created with JOMS is maintained by a single queue manager (QM), which is the device on which the queue is created. Messages sent to a queue, and requests to get messages from that queue, are forwarded by JOMS towards the corresponding QM. Permanent interest patterns defined in the communication layer ensure that each device serves as a mobile carrier for messages sent to or read from queues. Note that when several requests reach the same QM simultaneously, the QM ensures that each message read from the queue is sent to only one receiver, thus enforcing the above mentioned rule. Additionally, requests can include a selection pattern, so the QM searches in the queue for a message whose properties match this pattern. Figure 2c represents a request to get a message from the queue "Alan@0013725fc77d". A QM with the selection pattern shown in Figure 2d will receive all the requests and messages for this queue.

The JMS specification allows programmers to specify the expected degree of reliability (guaranteed vs best-effort delivery), through the so-called persistent and nonpersistent delivery modes. Moreover, the standard JMSPriority property expresses the expected priority level when transmitting messages. Message delivery can hardly be guaranteed in an opportunistic network (unless specific assumptions are made on the characteristics of this network). JOMS however uses these JMS properties to define a metric that combines the requested delivery mode and priority level. This metric is defined in a privilege() function, which can be edited if needed by an application developer. It is used to increase the delivery probability for "important" messages by adjusting the cache management policy and the message selection policy of the communication layer. When a new message is created or received while the local cache exceeds its capacity, messages with lower privilege level are discarded first. When a contact is established between two devices, messages with higher privilege level are transferred first.

Experimental Evaluation

Evaluating the performance of a middleware system capable of running in an opportunistic network is a challenge. In the literature, protocols and middleware systems designed for such networks are often evaluated using simulators, and little or no effort is Figure 4: Battery drain when running JOMS in the background on a smartphone (in ad hoc mode) devoted to producing code that can be used in a real setting. In contrast, a salient feature of JOMS is that it has been fully implemented, and is now distributed under the terms of the GNU General Public License1 . Moreover its effectiveness and efficiency have been evaluated in real conditions. To this end, several measurement campaigns have been conducted, using either smartphones or netbooks as host devices. During these experiments it would have been most interesting to compare JOMS against other JMS providers. Unfortunately, JOMS is -to the best of our knowledge-currently the only JMS provider for opportunistic networks that is openly available for application developers.

Resource Consumption

An important factor in opportunistic networks is the resource-constrained nature of mobile devices, which are generally characterized by limited processing power, memory size, and power budget. We have developed an Android service using JOMS, on which a series of tests were performed to better determine how much resources it consumes on HTC Wildfire S smartphones.

In the first test, JOMS was kept running as a background Android service, with no application-level traffic but the episodic gossiping used by JOMS for neighbor detection and coordination. During this test, which lasted for 14.5 hours before the battery was drained, Android services together consumed 9.25 minutes of CPU activity (about 1% duty cycle), while JOMS itself consumed 16 seconds of CPU activity (about 0.03% duty cycle). Besides, once installed JOMS consumed about 3.63 MB of memory (with an empty message cache), which represents less than 1% of the 418 MB available on a Wildfire S smartphone.

In a second series of tests we measured the effect of running JOMS on the battery life of a smartphone. As a baseline, we measured the battery drain on a smartphone running no application, with the Wi-Fi chipset enabled and operating in ad hoc mode. We then repeated the test several times with JOMS running and sending a new message every 3 minutes, with a varying number of neighbors. The evolution of the battery level during these tests is shown in Figure 4. It can be observed that the beaconing used by JOMS for neighbor discovery (when no neighbor is there to respond) reduces the battery life of a smartphone by about 5%, and that the gossiping with one neighbor reduces the battery life by an additional 15%. The battery drain does not grow significantly with a higher number of neighbors, though. This figure confirms that the battery drain in a smartphone is mainly driven by the ad hoc mode, and only marginally by the beaconing and gossiping performed by JOMS. Our system therefore allows a smartphone to run for a long time, without consuming too much resources while running as a background service.

Performance Assessment in a Connected Environment

Before trying to observe how messages can propagate network-wide in an opportunistic network, we first strove to observe how they can propagate among connected devices, that is, within a single connectivity island.

To do so we used four netbooks deployed in adjacent rooms so as to form a straight line A-B-C-D. The connectivity links between these netbooks was such that each net-book could only communicate with up to two neighbors (e.g., B could only reach A and C). The tests relied on the queue-based transmission model. Message queues were created on B, C, D, and netbook A was configured as a subscriber to all these queues. Messages with sizes varying between 1 kB and 2.5 MB were deposited successively in each queue (by local deposits), and we measured the time required for these messages to reach subscriber A. In order to get baseline values, we used the network performance measurement tool Iperf, which allowed us to measure the maximal throughput achievable on statically defined routing paths at IP level. We also developed a simple reference application (hereafter referred to as refApp), capable of sending, relaying and receiving data bundles over UDP, with data fragmentation and reassembly if needed. This application allowed us to measure the throughput achievable at message level, without paying the cost of neighbor discovery or gossiping among neighbors. Of course Iperf and refApp can both only be used in a connected island, as they require temporaneous end-to-end connectivity and multi-hop forwarding.

The results of the tests are shown in Figure 5a, 5b and 5c for transmissions over 1, 2 and 3 hops, respectively. Each value presented has been averaged over 150 rounds, for each configuration.

It can be observed that JOMS shows 5% to 20% overhead over refApp, which is an indication of the cost of discovering neighbors and gossiping with them before exchanging actual applicative messages. This overhead gets lower when multi-hop forwarding is required, for in that case refApp must receive messages before forwarding them, just like JOMS. Moreover, the observed transmission rates globally decrease as the number of hops increases. This is because when host B must serve as a relay between A and C, the radio channel around B is twice as busy as when B interacts only with host A. The same observation applies for host C when it must serve as a relay between B and D.

These results have been obtained with the queue-based transmission model, but similar tests involving topic messages show very similar results, so they are not detailed in this article: the curves obtained with queue-based and topic-based transmissions would actually be superimposed in the figures.

Performance Assessment in a Disconnected Environment

The above mentioned tests demonstrated that JOMS can perform satisfactorily in a traditional connected environment, and show reasonable performances in such conditions. Yet the most interesting characteristic of JOMS is of course that it can ensure the delivery of messages in a disconnected network, where traditional JMS providers -or simple programs like Iperf or refApp for that matter-would be totally useless.

In order to demonstrate that JOMS can indeed support JMS messaging in an opportunistic network, eight volunteers were equipped with HTC smartphones. These devices ran a simple SMS-like2 application based on JOMS. This application offers two services: The public text service relies on topics: each message published in a topic can be received by all subscribers. With the private text service, each message is addressed to a single message queue, which is hosted on the smartphone of the recipient user.

This experiment spanned over the working hours of two consecutive days for a total duration of 32 hours. The volunteers were asked to carry their smartphone whenever possible, and use both text services while moving inside our laboratory or in its surroundings.

Figure 6a shows how long each volunteer actually "used" his/her smartphone (i.e., with the screen lit) during the experiment. It can be observed that the smartphones remained untouched on average during three-fourth of the experiment duration. This does not imply that JOMS remained idle during that time, though, as it can keep gossiping with neighbor devices when running in the background.

The cumulative distribution function (CDF) of the average number of neighbors perceived by all smartphones is shown in Figure 6b. It can be observed that, in average, a smartphone did not have more than two neighbors simultaneously during almost 80% of the duration of the experiment, and that it was actually alone (i.e., with no neighbor) during about 30% of that time. These figures confirm the disconnected nature of the network formed by the smartphones, and demonstrate the need for opportunistic transmissions in order to maintain communication in such conditions.

A timeline of the average number of neighbors during the first day is shown in Figure 7. The high number of neighbors during the first two hours of the experiment is explained by the fact that all volunteers were in the same room at that time, as the purpose and conditions of the experiment were explained to them. Later on all volunteers dispersed in the laboratory, and the timeline only shows episodic contacts between their smartphones. These results again confirm that a communication system requiring end- The traces collected by JOMS on each smartphone show that 230 text messages were sent by the volunteers during the two-day experiment. Figure 8a presents the cumulative distributed function (CDF) of the delivery time for topic-based and queue-based messages. It can be observed that nearly 80% of topic-based messages got delivered in less than 20 minutes, whereas most queue-based messages took about 40 minutes to be delivered. This difference is due to the fact that a message for a queue has to get through the manager of the target queue before being sent to the final receiver. In contrast, a message for a topic disseminates directly from host to host before getting delivered to subscribers. In any case, the figures show that during the experiment most of the messages got delivered to their destination(s) in less than 1 hour. Yet, about 3% of the messages could not be delivered. This is the consequence of the unpredictable -yet perfectly legitimate-behavior of the volunteers, who sometimes moved away from the campus, or even switched their smartphone off in order to preserve its battery budget. By doing so they prevented any further radio contact between their smartphone and those of other users, and this of course led to message loss.

During the experiment, 5729 contacts were observed between smartphones, with Figure 9: Distribution of contact durations an average contact duration of 121 seconds. The distribution of contact durations is presented in Figure 9. The majority of radio contacts lasted for less than a minute. Furthermore, it is worth mentioning that 2.5% of radio contacts were not exploitable by JOMS because they were asymmetric, that is, one smartphone could detect a neighbor, but the reverse was not true. Such a situation usually happens for only a few seconds, and it occurs when the smartphones involved are too far from each other, so their signal is barely above noise level.

Figure 10 shows the number of messages received by each smartphone (in parentheses), and the distribution of the number of hops required for messages to reach that smartphone. It can be observed that most of the smartphones received at least half of the messages after a multi-hop trip. This observation confirms the interest of having smartphones serve as benevolent message carriers in an network such as that considered in this experiment. In order to better illustrate this point, 8b shows how one particular message disseminated during the experiment. This message was first published in the public topic by mobile P1. After only a few minutes P1 established a radio contact with P2, which thus got a copy of the message and became a new carrier for this message. P1 later managed to forward the message to P3, and later to P7, while P2 forwarded it to P5. The message thus kept disseminating, until it reached the last subscriber P6, about 5 hours and 30 minutes after it was initially published.

The results presented in this section demonstrate that JOMS is effective and efficient in providing JMS services in a disconnected environment. An obvious advantage of implementing a provider that conforms with the JMS standard specification is that developers do not need to learn a new programming language, or get familiar with an exotic programming model or API. A developer can simply focus on writing a JMS application "as usual", and JOMS can take care of its execution in unusual conditions. Indeed, any pre-existing JMS application can theoretically be deployed using JOMS, and run satisfactorily in an opportunistic network. Yet there are a few common pitfalls developers should pay attention to while designing their code. Indeed, many standard applications based on JMS have been built with the implicit -but often wrong-assumption that the JMS provider can prevent message loss, and guarantee message ordering Figure 10: Amount of messages received in a direct/multi-hop manner by each smartphone and transmission delay. As a general rule, such favorable properties cannot be guaranteed in an opportunistic network, so developers that wish to deploy their code in an opportunistic network should refrain from making similar assumptions.

Related Work

Message routing in delay/disruption-tolerant networks -and more specifically in opportunistic networks-has justified a fair amount of research during the last decade. Recent surveys can notably be found in [START_REF] Khabbaz | Disruption-Tolerant Networking: a Comprehensive Survey on Recent Developments and Persisting Challenges[END_REF][START_REF] Boldrini | Autonomic Behaviour of Opportunistic Network Routing[END_REF][START_REF] Nguyen | Routing in Opportunistic Networks[END_REF][START_REF] Triviño-Cabrera | Survey on Opportunistic Routing in Multihop Wireless Networks[END_REF][START_REF] Zhang | Delay/Disruption Tolerant Mobile Ad Hoc Networks: Latest Developments[END_REF]]. Yet, as mentioned in [START_REF] Khabbaz | Disruption-Tolerant Networking: a Comprehensive Survey on Recent Developments and Persisting Challenges[END_REF], "rare are the [DTN] protocols that were implemented, tested in real-life and proven to be free of lethal stealthy assumptions."

A wide variety of application domains would benefit from opportunistic networking [START_REF] Voyiatzis | A Survey of Delay-and Disruption-Tolerant Networking Applications[END_REF][START_REF] Lindgren | The Quest for a Killer App for Opportunistic and Delay Tolerant Networks[END_REF]. Opportunistic computing is actually becoming a new distributed computing paradigm, involving transient and unplanned interactions between mobile devices [START_REF] Conti | From Opportunistic Networks to Opportunistic Computing[END_REF]. Some middleware systems have been proposed in order to ease the task of application programmers for mobile ad hoc networks (MANETs) [START_REF] Hadim | Trends in Middleware for Mobile Ad Hoc Networks[END_REF], adapting well-known middleware solutions or designing new ones. Our approach and those discussed below clearly fit in the first category, as they consist in developing JMS providers for ad hoc networks.

Vollset et al. describe a JMS implementation supporting non-persistent topics in MANETs [START_REF] Vollset | JMS on Mobile Ad Hoc Networks[END_REF]. This implementation uses a multicast routing protocol to provide publish/subscribe semantics by mapping JMS topics to multicast addresses. Since this protocol cannot disseminate messages beyond a single connected fragment of the network, it is hardly usable in opportunistic networks. It could probably be adapted, though, using a disruption-tolerant multicast routing protocol. In this system, no directory service (such as JNDI) is provided: all JMS clients are assumed to own a local copy of a configuration that contains information about all queues and topics. In the paper the authors propose some solutions to support JMS queues, but none of these solutions has actually been implemented. One of these solutions requires an agreement amongst mobile nodes through some consensus algorithm, which is hardly achievable in an opportunistic network. JIMS (JMS Implementation for MANETs using Sociable nodes) has been designed during a Master's project at University College London [START_REF] Chen | Reliable Asynchronous Middleware for Mobile Ad Hoc Networks[END_REF]. It defines the notion of social nodes. A social node is one that is supposed to meet many other nodes while moving in a MANET. It also has a lot of resources, so it can carry many messages, and never needs to be turned off while roaming the network. This idea of having privileged nodes that can serve as effective data mules is an interesting one. A similar behavior can actually be obtained with JOMS, as the amount of resources used by the system on each device can be adjusted accurately.

Epidemic Messaging Middleware for Ad hoc networks (EMMA) is an adaptation of JMS that targets MANETs presenting connectivity disruptions [START_REF] Musolesi | EMMA: Epidemic Messaging Middleware for Ad Hoc Networks[END_REF]. EMMA assumes the availability of a so-called synchronous protocol, which can be used to reach mobile hosts that belong to the same cloud -or island-as the sender. An asynchronous epidemic routing protocol is used to disseminate messages towards remote clouds. EMMA manages queues in a manner that is quite similar to that of JOMS: each queue is maintained by a single holder, which advertises this object periodically with a set lifetime, and which can accept subscriptions from other hosts. EMMA and JOMS differ in the way they deal with topics. In EMMA topics are maintained by a single holder, which can accept subscriptions from other hosts. In JOMS topic subscriptions can be set locally on any host. Another difference is that in EMMA the gossiping mechanism between neighbor hosts is such that all messages are systematically considered, so very large lists of message identifiers can be exchanged between neighbor hosts. In JOMS this gossiping is constrained by the interest profiles of neighbors. Finally, EMMA defines its own communication protocol for route discovery and maintenance, while JOMS presents a two-layer architecture: the upper layer is concerned with queue and topic management and utilization, and the lower layer supports opportunistic communication.

Although [START_REF] Vollset | JMS on Mobile Ad Hoc Networks[END_REF], [START_REF] Chen | Reliable Asynchronous Middleware for Mobile Ad Hoc Networks[END_REF] and [START_REF] Musolesi | EMMA: Epidemic Messaging Middleware for Ad Hoc Networks[END_REF] have been published almost a decade ago, the JMS providers they describe have never been openly distributed. To the best of our knowledge, JOMS is currently the only provider that is available for developers that wish to develop JMS-based distributed applications for opportunistic networks.

Conclusion

Developing distributed applications for opportunistic networks can be quite a challenge, since in such networks very long transmission delays and possible message loss should be expected at any time. JOMS (Java Opportunistic Message Service) is a message-oriented middleware system that is meant to ease the development of such distributed applications. It is basically a JMS provider, but unlike other providers it does not rely on a central message repository or service directory. Message queues and topics are distributed in the network, and a distributed directory service is used to discover and locate destination objects. Information sharing relies on a content-driven epidemic scheme, whereas all mobile devices collaborate to disseminate messages network-wide. This combination of unique features makes it possible for JOMS to perform effectively in an opportunistic network, while other JMS providers would be ineffective in similar conditions.

JOMS has been tested and evaluated in real conditions using Android-based smartphones (as reported in this article), but also using tablets, laptops, and netbooks. Future work involves leveraging JOMS to develop full-featured distributed applications that can benefit users of opportunistic networks, especially in disaster or economically challenged areas.

Figure 2 :

 2 Figure 2: Examples of message descriptors (up) and selection patterns (down)

  (a) Between 1-hop (direct) neighbors (b) Between 2-hop neighbors (c) Between 3-hop neighbors

Figure 5 :

 5 Figure 5: Transmission throughputs observed in a single connected island (with or without multi-hop forwarding)

  (a) Usage duration of smartphones (b) Cumulative distribution of the average number of neighbors

Figure 6 :

 6 Figure 6: Activity and "sociability" of smartphones

Figure 7 :

 7 Figure 7: Timeline of the average number of neighbors during the first day

Figure 8 :

 8 Figure 8: Message delivery time and dissemination of a message

http://www-casa.irisa.fr/joms

SMS: Short Message Service.


Romain Drouilly
email: romain.drouilly@inria.fr

Panagiotis Papadakis
email: panagiotis.papadakis@inria.fr

Patrick Rives
email: patrick.rives@inria.fr

Benoit Morisset

Local Map Extrapolation in Dynamic Environments

We present a generative approach to perform robot mapping that is based on an intelligent integration of static and dynamic entity classes within an environment, in order to extrapolate map information at various resolutions. Our framework differentiates from the conventional standpoint where different mapping levels are overlaid on one another, by fusing information from different mapping levels that allows us to infer new information within partially mapped environments. Towards this goal, we develop a class-dependent map extrapolation function that captures the discriminative relation between an environment entity and the mapping procedure. We illustrate the advantages in using heterogeneous contextual information when mapping an environment using a prototype implementation of our approach on an indoor robot platform, giving very promising results.

I. INTRODUCTION

There is a growing trend in robotics to consider contextual information as a means to augment the perceptual boundaries of contemporary robots. This is largely motivated by the increasing integration of robots into the real world wherein humans interact and operate by exploiting explicit as well as implicit knowledge. Likewise, integration of a priori knowledge into robotic skills is a required but not sufficient condition for deploying robots into increasingly complex environments, that should further be equipped with special skills in order to account for incomplete information. Among these skills, the ability to map the environment has for long been considered as a prerequisite for developing intelligent path-planning behaviours with most research efforts focusing on building maps that capture as precisely as possible the underlying environment structure. However, mapping precision deteriorates within changing environments due to dynamic events that cause occlusions or impede access to certain areas mainly due to human-incurred events. In turn, this results in maps that are inappropriate or insufficiently complete for robot operation since mapping techniques [START_REF] Hahnel | Map building with mobile robots in dynamic environments[END_REF] typically discard changes as outliers and instead seek to preserve only what appears to be spatially consistent over time.

When mapping the environment, the conventional approach is to progressively abstract information into various levels from the metric (2D or 3D) and topological [START_REF] Chapoulie | Topological segmentation of indoors/outdoors sequences of spherical views[END_REF] to the semantic [START_REF] Nüchter | Towards semantic maps for mobile robots[END_REF], [START_REF] Vasudevan | Cognitive maps for mobile robots-an object based approach[END_REF] and social layers [START_REF] Papadakis | Social mapping of humanpopulated environments by implicit function learning[END_REF] that are organized into a hierarchy where information is processed in a bottom-up fashion. We argue that a top-down analysis can assist in augmenting the information that has already been acquired, by performing extrapolation that is guided by a semantic interpretation of both its static and dynamic characteristics.

In the domain of robotic mapping, the use of cues that are related to dynamic events or static scene semantics has so far been exploited separately for each case. This is mainly due to the fact that mapping techniques aim at filtering out all nonstatic cues from the extracted environment map in an effort to derive a representation that is invariant to change and finally perform a labelling of the corresponding areas.

There is a rather sparse number of earlier works that partly address the problem of inference at the level of robotic mapping through the use of static semantic contextual information. In a preliminary account, Calisi et al. [START_REF] Calisi | Contextual navigation and mapping for rescue robots[END_REF] presented a pilot study showing the advantages of using contextual information of the environment and internal robot states in basic navigation and mapping tasks for urban search and rescue scenarios. In the domain of structured environments, Callaghan et al. [START_REF] Ocallaghan | Gaussian process occupancy maps[END_REF] developed a regression mechanism for space occupancy through the use of a Gaussian process that was trained on samples taken from earlier constructed maps and a non-stationary covariance function that adapted to the neighbourhood of query points. Their approach alleviated uncertainty due to occlusions or range limits as well as noisy measurements but without accounting for dynamic objects such as humans. In the topdown approach proposed by Nuchter et al. [START_REF] Nüchter | Towards semantic maps for mobile robots[END_REF] scene labels are used to correct pose estimation to limit drift along trajectory but without seeking to extrapolate scene structure beyond perceptual limits. Finally, the work of Pronobis et al. [START_REF] Pronobis | Large-scale semantic mapping and reasoning with heterogeneous modalities[END_REF] probably constitutes the most elaborate attempt to account for the static semantic content of an environment in robot mapping using a property-based scheme. However, inference is performed for areas that were already partially observed and in the complete absence of dynamic events.

Mapping the non-static constituents of an environment is a relatively new problem and hence there is a limited number of earlier works that could be referred. Recently, Alempijevic et al. [START_REF] Alempijevic | Bootstrapping navigation and path planning using human positional traces[END_REF] employed Gaussian processes to refine the probability of occupancy in free space by tracing human trajectories. The individual poses along the tracked trajectories were used as training points for fitting the likelihood function which was updated in parallel to the execution of a controversial path planner that favoured the mostly visited areas. Grzonka et al. [START_REF] Grzonka | Mapping indoor environments based on human activity[END_REF] demonstrated the ability to build approximate environment maps by using door closure/opening events as candidate loop closure positions and room delimiters. A conditioned dilation operation on the 2D image of a human trajectory was employed in order to emerge the coarse structure of the environment, yet the fact that human motion was tracked remotely using MOCAP suits worn during each trial limits the utility of that approach. An interesting perspective was proposed by Jiang et al. [START_REF] Jiang | Hallucinated humans as the hidden context for labeling 3d scenes[END_REF], wherein the hidden context behind scene structure is revealed by selective sampling of a fixed, distinctive set of human poses within empty space and learning humanobject and object-object affordances. While that approach bears similarities from the point of view of using humans to interpret scene structure, it is used for the purpose of bottomup scene labelling while we are concerned with performing map extrapolation along both directions.

Towards this goal, we propose a framework to extrapolate map information within a partially mapped indoor environment using contextual information by interpreting the static as well as dynamic semantic content of the environment (example shown in Fig. 1). We achieve this by developing a classdependent map extrapolation function that allows us to account for both static and dynamic aspects of an environment. In this way, our approach allows a robot to significantly augment its perceptual capacity, in contrast to earlier works that either consider one of the two constituents individually or impose an explicit distinction between them. The advantages of our approach are shown through a set of concrete examples that highlight the added value of extrapolating map information instead of mapping solely the observed areas.

We organize the remainder of the paper as follows. In Section II, we present the details of our approach and solidify its advantages within a set of characteristic use-cases, in Section III we demonstrate the efficacy of our method in various examples using an indoor robot platform and finally, summarize our findings in Section IV.

II. PROPOSED APPROACH

When mapping an environment there will always be areas that remain uncovered by a robot resulting in the construction of an incomplete map. The distinguishing factors that are responsible for this can be static, quasi-static and dynamic entities of an environment such as physical barriers that occlude an area of interest and events incurred by human activity. Our purpose is to specifically account for those entities when mapping an environment and in particular, for those that mostly affect the mobility of a robot. More particularly, we rely on a set of mapping functions (i.e. robotic processes) M l (.) : I l → O l , l = 1, 2, ...L, each of which captures a particular aspect of the environment through the analysis of a specific set of attributes, where I l , O l correspond to the input and output domain of the corresponding function. In the present work, the roles of the functions are determined through a set of L = 3 in total increasing environment map abstraction layers enumerated as; (1) metric, (2) semantic and (3) social where each level of abstraction is dedicated for a certain task. The first two mapping levels have well-known, distinct roles [START_REF] Thrun | Exploring artificial intelligence in the new millennium[END_REF], [START_REF] Nüchter | Towards semantic maps for mobile robots[END_REF], namely, the metric is used for obstacle avoidance and local navigation and the semantic for task-based, intelligent pathplanning while social mapping is mainly useful for allowing socially-compliant human-robot interaction [START_REF] Papadakis | Social mapping of humanpopulated environments by implicit function learning[END_REF].

For the construction of our map structure, more specifically, we follow an ego-centric approach wherein information from the different layers is integrated into locally consistent submaps globally connected in a graph structure, whose edges denote the reachability among the sub-maps. Each sub-map describes the environment from a particular viewpoint in the joint domain

O = O 1 × O 2 × O 3 .
Our ultimate objective is then to augment the situation awareness of the robot either through the addition of new sub-maps or the augmentation of the current sub-map, using information that is already available within the mapping hierarchy and is encapsulated within the semantics of the static and dynamic scene.

A. Local and Global Map Definition

A local sub-map S constitutes a multi-layered, ego-centred representation holding the decomposition of the environment into the metric, static semantic and human social activity level. As such, it consists of several different types of information that are characteristic of each layer, however, we will limit our formal description to only those parts that are used by the proposed methodology and only selectively refer to the remaining parts whenever necessary.

We denote a local sub-map as S = {P; R;U} ∈ O wherein P is the set of points sensed in the local environment, R is the set of groups of points p ∈ P wherein each group forms an entity assigned with a semantic label and U is the set of 2D cells on a rectangular 2D occupancy grid that encode the navigational area for the robot. There are in total N P number of points as prescribed by the sensor resolution, N R number of detected entity regions as obtained by the semantic entity labelling of the local sub-map (see sections II-C, II-D, II-E) and N U occupancy grid cells as defined by the resolution of the occupancy map. Each particular entity r ∈ R groups the corresponding points and is appointed with a vector that holds the entity's pose (3D translation t = (t x ,t y ,t z ) T ∈ R 3 and orientation o = (φ , θ ) T ∈ [0, π) × [0, 2π)) and a set of class-dependent attributes c. We denote this vector as a r = (t T , o T , c T ) T .

Local sub-maps are globally connected in a graph G = {V, E} ∈ G where V is the set of sub-maps, E the set of edges that connect sub-maps and G the set of possible graphs. We distinguish between two sets of sub-maps so that we denote V = S O ∪ S P where S O are the set of observed sub-maps and S P the set of predicted sub-maps. Edges correspond to relative transforms between two sub-maps. Finally, we segment the graph in topological places that are delimited through the existence of static or quasi-static entities. Then two sub-maps are considered belonging to the same topological place if they are not connected through these entities. According to this definition, elements of S P are considered as belonging to different topological place than those of S O .

B. Map Extrapolation

We construct an entity-dependent extrapolation function that serves as a guiding model for local map extrapolation. This function propagates information either within the local sub-map hierarchy or the global graph map. We denote the extrapolating function as M (.) : O → O and unfold our approach using a number of selected static, quasi-static and dynamic entity classes. The general form of this function is as follows:

M (S i ) = δ i j S ′ i + (1 -δ i j )S j (1)
where δ i j is the Kronecker delta function, i denotes the index of the current sub-map S i where the robot is placed and j the index of a newly created sub-map S j that could be created as a result of map extrapolation. Essentially, eq. ( 1) states that new information will either be inserted to the current sub-map S i that will be updated to S ′ i or a completely new sub-map S j will be generated, depending on the entity class. In the next sections, we will develop different forms of this function according to the semantics of the particular entity class.

C. Static entity based extrapolation

Among the various static entity classes within the environment, some are of particular interest for robot navigation as they connect different parts of the environment. Thus, they are powerful topological cues that could be used to infer the presence of navigable space within unobserved areas.

In this work, we perform map extrapolation using staircases as static entities. To detect a staircase we first filter the 3D point cloud P i of map S i by extracting a voxel-based representation and then obtain planar surface patches through the application of the RANSAC algorithm. If a patch normal is oriented around 45 • from the vertical axis and has an overall surface area greater than a minimal size it is recognized as stairs. Once the staircase is detected and its position t is obtained as the centroid of the patch, we set its orientation o as follows. Let n be the normal of the staircase plane, z the vertical coordinate axis and w = (n × z) × n. The orientation corresponding to the ascending stairs direction is obtained as o = w • sng(w T z).

The stairs are further characterized by the step width w and the expected height of the new floor h at the top endpoint of the staircase so the corresponding parameter vector is expressed as a s = (t T , o T , (h, w) T ) T . Fig. 2 gives an example of staircase detection annotated with the corresponding parameter vector.

Upon detection of the staircase, a new sub-map S j is generated by adding a node to the graph. It is connected to the current sub-map S i by the edge E i j that corresponds to the position of the expected top of the stairs expressed in the S i reference frame. S j is initialized by copying entityrelated data of S i that are assumed to be shared between the two sub-maps. It is denoted as S j = {P S ; R S ; ⊘} where P S corresponds to stairs points and R S the corresponding group. Then it is complemented as S j = {P S ; R S ;U j } where U j is obtained through extrapolation of free space via the rule:

U j = {u ∈ R 2 | f s (u) > p th } (2)
where f s (.) is a bivariate normal probability density function (pdf) denoted as N (0, Ω) with covariance matrix Ω = Iσ 2 , σ is proportional to the staircase step width w and u ∈ U j is an arbitrary point within the local occupancy map. The f s (.) function encodes the confidence for the existence of free space up to a certain distance from the origin 0 of the new sub-map reference frame which is controlled by p th .

D. Quasi-static entity based extrapolation

Quasi-static entities are defined as entities that change occasionally and their state can have a direct effect on the mobility of a robot. The most typical example corresponds to doors due to their functional property for space delimitation, that are defined by their fixed rotational axis which limits their motion range. If a planar patch that was detected in the previous stage is orientated orthogonally to the ground it is analysed further to find potential doors. In detail, we extract salient points [START_REF] Shi | Good features to track[END_REF] in the 2D image of the planar patch that we subsequently cluster in two groups: (i) those that are close to the ground and are candidates to belong to the bottom edge of the door and (ii) those that are close to the door height and are candidates to belong to the top edge of the door. Then, we seek the points from the two groups that are vertically aligned and for each pair we search whether there exists another pair that resides at a distance equal to the expected width of a door. Finally, we find the rotational axis of the door by searching for the door handle. We rely on the reasonable argument that salient points will concentrate around the door handle and count the number of points at the two possible locations on the left and on right side of the door. The side that contains the highest number of salient points is then used to infer the rotational axis of the door, as illustrated in Fig. 3.

Once the door is detected and its position t is obtained as the centroid of the patch, we set its orientation o as follows. Let n be the normal of the closed door plane and z the orientation of the robot, then the orientation of the door is obtained by o = n • sgn(n T z).

As in the previous case (see section II-C), a new submap S j is created and added to the vertex set V of the graph G . A new edge E i j is added to E that corresponds to the relative position of S j with respect to the current sub-map S i expressed in S i reference frame. The new sub-map is placed at the distance d behind the closed door in the direction given by o and initialized with entity data so as S j = {P D ; R D ; ⊘} where P D are the door's points that are assumed to be observed from both sides of the door and R D the corresponding group. Then it is updated as S j = {P D ; R D ;U j } where U j is obtained through extrapolation of free space according to the following rule:

U j = {u ∈ R 2 | f d (u) > p th } (3)
where the function f d (.) is a bivariate skew-normal (SN) probability density function denoted as Ñ and centered at t ′ which is the position of the rotational axis of the door in S j reference frame. The family of skew-normal distributions [15] constitutes a superset of the normal distribution N , being further parameterized by the so-called shape parameter that controls the amount of skewness. Following [START_REF] Azzalini | The multivariate skew-normal distribution[END_REF], this is achieved by setting f d (.) to be a probability density function distributed as Ñ (t ′ , Ω, α) defined as:

f d (u) = 2φ (u)Φ(α T u) (4)
where u ∈ U j is a cell within the local occupancy map, φ denotes the normal pdf N (0, Ω) with covariance matrix Ω = Iσ 2 , Φ is the respective cumulative distribution function of φ and α = (α 1 , α 2 ) T is the parameter vector of the SN pdf that controls the skewness and 0 the origin of S j reference frame.

We have chosen to employ the skew-normal pdf due to the fact that doors, in contrast to staircases, cannot be properly modelled with a symmetric form due to their constrained motion as defined by their rotational axis. The SN pdf allows us to capture this asymmetry by regulating the function' s skewness parameter vector α along the orientation of the door and in proportion to the door' s width w. On this basis, skewness is introduced by setting α = (0, c • w) T , therefore, the overall parameter vector for the door entity is denoted as a d = (t T , o T , α) T . Fig. 3 gives an example of door detection annotated with its distinctive parameters.

E. Dynamic entity based extrapolation

Through the detection of humans and analysis of their motion history we are able to extrapolate map information with respect to space occupancy based on the fact that a human trajectory always traverses navigable space, which is a reasonable argument for indoor environments. For the detection of the articulated human motion we rely on the use of the OpenNI library [START_REF] Shotton | Real-time human pose recognition in parts from single depth images[END_REF] and perform map extrapolation strictly within the current sub-map S i since the position of a human is dynamic and arbitrary and grounding a new local sub-map is not reasonable. Therefore, we exploit the nature of human navigation in order to infer the presence of areas that are conditionally unoccupied in the current sub-map, in two distinct scenarios. In the first scenario, a human enters or exits the perceptual range of the robot either by entering/exiting a room via a door or by entering/exiting the field of view of the underlying sensor. In both cases, we extrapolate in time (either backward or forward) a short-term human trajectory that in turn allows the extrapolation of free space. In the second scenario, a human upper body is detected while the lower is occluded due to a physical barrier. In that case, extrapolation of free space is performed by attributing the occluded local area along the human trajectory as unoccupied.

These areas are considered as conditionally unoccupied since the robot would only be able to traverse them in the absence of humans. To address these scenarios, our approach is to treat a human as a non-stationary kernel function which quantifies the notion of personal space introduced by Hall [START_REF] Hall | The Hidden Dimension: Man's Use of Space in Public and Private[END_REF] within proxemics theory and to utilize this function as a guide for extrapolating the "free space" class, map information along the human trajectory.

Following the description given in section II-A, the first step is to compute the human' s pose and class-dependent attributes of the corresponding entity region R. Towards this end, we collect the dominant human social spacing cues, in particular, (i) the 2D position of the human t = (t x ,t y ) T ∈ R 2 , (ii) the 2D orientation θ ∈ [0, 2π) and (iii) the dominant side d ∈ {-1, +1} where -1, +1 correspond to the left and right side of the human respectively. The position of the human is taken as the body centroid while the orientation from the torso orientation. The dominant side can be inferred implicitly by the minimum lateral distance of the human from occupied space within the metric map, based on the hypothesis that people maintain a smaller distance from their dominant side and vice versa. In this fashion, the parameter vector for a person is denoted as a h = (t T , θ , d) T .

In the sequel, we update the current sub-map S i as S ′ i = {P; R;U ′ } where U ′ = U ∪ U i , and U i is obtained through extrapolation of free space via the rule:

U i = {u ∈ R 2 | f h (u) > p th } (5)
where the function f h (.) is a bivariate skew-normal (SN) probability density function denoted as Ñ (t, Ω, α) and u ∈ U ′ is a cell within the local occupancy map. The f h (.) function serves the role of quantifying a human' s personal space which we exploit here in order to extrapolate navigable areas along his trajectory. Fig. 4, left, gives a visual example of an individual' s personal space as expressed by the function f h (.).

Recalling the earlier mentioned scenarios, forward temporal extrapolation of the human trajectory is applied when the human exits the perceptual field of view of the robot while backward temporal extrapolation is applied upon entry. We perform a linear prediction based on the fact that humans paths are mostly composed of linear segments. Furthermore, since we are only interested in making short-term predictions any changes in human orientation that may occur within the region of interest should have negligible effect. The formula for obtaining the extrapolated parameter vector for the case of the human entity becomes a h (t + k) = a h (t) + k • ȧh (t) where t is the time of the last observed human pose and k the desired (negative, or positive) prediction time. Fig. 4, right shows the idea of linear trajectory prediction in a synthetic example.

III. EXPERIMENTS

To evaluate the utility of the proposed approach we have performed a series of indoor mapping experiments using a Neobotix MP-500 robot which employs a two-wheel differential drive mobility system. The robot is equipped with a front-facing 2D laser scanner that has been used in this work as a means for obtaining an accurate estimate of 2D space occupancy. For acquiring RGB-D point clouds of the indoor environment, we have used the Asus XtionPRO Live camera which captures synchronized RGB-D images at a high frame rate. The environment under consideration consists of various spaces with diverse roles, namely, offices, corridors, stairs, reception desk, printing room, meeting rooms, etc.

The experimental scenario is structured as follows. The robot navigates in a supervised mode by a remote operator while encountering various entities (static, quasi-static and dynamic) along its path. To facilitate the subsequent processing of information, during the detection of a human within the scene the robot is halted in order to minimize the interference of scene motion into human motion analysis. The detection of an entity triggers the corresponding class-dependent extrapolation process as described in section II.

a) Graph extrapolation:

To estimate the capability of our algorithm to add new nodes whenever necessary we have evaluated the performance of our entity detector in the case of static and semi-static entities detection. We use the recall (R) as a performance measure which is defined as the ratio of true positives to the total number of images where the corresponding entities are present. The overall performance for our experiments is shown in Table I. In the case of staircases, we attain a high detection performance as their structure is very characteristic within indoor environments, relying on a large 3D form within the scene and therefore being less sensitive to noise. Door detection performance is lower probably due to the requirement of detecting all four corners of the door which can be more challenging within cluttered scenes. Despite this shortcoming, the concerned entities within our environment were consistently detected whenever the robot could have a complete view of the corresponding entity. For both static and quasi-static categories, all instances were detected and the corresponding nodes were added to the global graph so that our approach was able to capture the complete structure of the test environment.

Figure 5 demonstrates the increased capacity of our approach to map an environment through the use of scene context that we exploit to compensate for the lack of information.

It shows graph extrapolation results at the right and ground truth at the left. We see that for all unobserved rooms as for the upper floor there is a corresponding predicted node in the graph. It demonstrates the ability of our algorithm to capture the topology of the environment despite some parts are not accessible at the exploration time. In our case, instead of considering that the environment is only one room, the robot is able to predict the possible existence of three additional rooms and another floor. This definitely increases the environment awareness of the robot and extend the map considerably. b) Free space extrapolation: We have quantitatively evaluated our approach for free space extrapolation using a total of three confidence levels as expressed by the parameter p th , namely, p th ∈ {0.5, 0.6, 0.7}. To measure the performance for each confidence level, we use the precision score (PR) which is defined as the ratio between the number of true positive (TP) predictions of free space and the total number of positive predictions which includes the false positive (FP), i.e. PR = T P/(T P + FP). The overall performance as well as for each individual entity class is shown in Table . II.

Clearly, we attain a very high precision in predicting the existence of free space in all different entity classes and across all three confidence levels. These results confirm our hypothesises to a high degree regarding the strong relation that exists between different mapping levels, in this case, between the high-level semantic/social with the lower space occupancy level. Regarding the variation in performance between the chosen confidence thresholds p th , we could not distinguish a characteristic trend, although one could naturally expect that performance would decrease as p th decreases. In our experiments, this did not eventually occur because as we increase the area in which we extrapolate free space, new true positives occur along with the false positives and therefore the overall performance remains largely unchanged.

One reason for not using longer-range predictions through the lowering of p th , is that results become less significant when distance increases. The predicted free space extends beyond the boundaries of rooms and no longer corresponds to the free space accessible through the entity class that is used for prediction. It highlights one limitation of our approach: we use the high-level semantic/social information to predict free space without accounting for the surrounding environment structure. Nevertheless our method produces globally consistent predictions that definitely increase the quality of the map.

Finally, we provide some qualitative examples of the performance of our approach for different entities. Fig. 6 shows an example of map extrapolation by exploiting the dynamic entity (human) where the robot is placed at the end of corridor when it encounters a human who enters within the field of view of the robot and then exits through a passage. The consecutive frames show the extrapolation result that happens along the observed human trajectory and its short-term prediction after exiting. Figure 7 provides a larger example wherein map extrapolation occurs due to doors detection. The left part shows the corresponding environment when the doors were opened while the right part the mapping output of our approach when the doors were closed. The surface mapped with our approach is up to 10% higher when p th = 0.7 than what would be otherwise obtained and 20% higher when p th = 0.5. This performance could be even higher within an office environment where there are more semantic cues like doors or humans. This demonstrates the practical utility in performing map extrapolation using our approach, as a way to extend the situation awareness of the robot in realistic conditions.

IV. CONCLUSIONS

We have presented a new approach for robot mapping that accounts both for the static as well as the dynamic semantic content of the environment. Our approach exploits the hidden context within the environment at different layers in order to extrapolate map information to unobserved areas, allowing for a significant augmentation in the situation awareness of a robot. We have evaluated the capacity of our approach using a prototype implementation on an indoor robot platform, obtaining very promising results in various scenarios. Among the various directions in which this work could be extended, we believe that through the treatment of additional entity classes we could discover new relations in the various levels of the mapping hierarchy and arrive to a more coherent robot mapping framework, allowing the development of more advanced path-planning behaviours for various applications.

Fig. 1 .

 1 Fig. 1. Examples of map extrapolation by scene context interpretation.

Fig. 2 .

 2 Fig. 2. Static entity class staircase along with its parameters.

Fig. 3 .

 3 Fig. 3. Door detection example (left) and extracted parameters (right).

Fig. 4 .

 4 Fig. 4. Left: instance of the atomic space function attributed to a human. Right: trajectory prediction upon entering/exiting the robot' s field of view.

Fig. 5 .

 5 Fig. 5. Left: ground truth map and topology. Top Right: test map of the environment with robot path superimposed. White parts correspond to observed areas, blue nodes to observed sub-maps, green nodes to predicted sub-maps. Red rectangle illustrates staircase while purple lines highlight detected closed doors. Bottom right: Blue circle illustrates observed topology and green dashed circles predicted topology.

Fig. 6 .

 6 Fig. 6.Local map extrapolation along the observed and the short-term prediction of human trajectory. The robot position is shown as the green crossmark, extrapolated free map information is shown in light grey, unknown space in dark gray and obstacles in black.

Fig. 7 .

 7 Fig. 7. Map extrapolation using static entities. Ground truth complete map is shown on the left while free space extrapolation is shown on the right in light gray for three confidence thresholds.

TABLE I .

 I Detection performance

			TABLE II. Extrapolation performance
	Entity class Stairs Doors	Recall 0.95 0.67	Entity class Static Quasi-Static Dynamic	p th threshold 0.6 0.7 0.91 0.5 0.93 0.93 0.98 0.99 0.99 0.95 0.94 0.93
			Overall	0.95	0.95	0.95