Cigdem Sengul

Aline Carneiro Viana

Roy Friedman

Marin Bertier

Anne-Marie Kermarrec

Aline Carneiro

Viana -Roy Friedman -Marin Bertier -Anne-Marie Kermarrec

May

Adaptive Forwarding to Match Mobility Characteristics in Delay Tolerant Networks

Keywords: opportunistic forwarding, buffer management, contact prediction, contact history maintenance, delay tolerant networks routage opportuniste, acheminement adaptive, mobilité, réseaux tolérants aux délais, estimation de contactes

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

Introduction

Delay Tolerant Networks (DTNs) are wireless networks in which a contemporaneous routing path may never exist between a sender and a receiver [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF]. Examples of DTNs include disaster response, underwater sensor, vehicular networks, and pocket-switched networks, which provide connectivity to users that carry their portable devices from one connectivity island to another. However, due to mobility of nodes in these networks, store-and-forward techniques can ensure eventual communication between any two nodes. Additionally, DTNs are frequently characterized by strict resource constraints in terms of memory, CPU and energy. Given these characteristics, any forwarding mechanism for DTNs must be frugal in its usage of computation and communication resources.

Note that an immediate solution that comes to mind for data forwarding in DTNs is to always relay through the node that is likely to meet the destination first. However, some nodes may never meet the destination, yet can still be good relays since they frequently meet other nodes that often meet the destination. Thus, it makes sense to evaluate the contact histories of all pairs of nodes. However, keeping track of all this information and propagating it to every node is too costly. Therefore, the main challenge becomes to adjust forwarding decisions on the fly and recover from bad decisions to perform under different mobility conditions with a low cost. This is essential to ensure reachability even when disconnections are frequent and hard to predict. Hence, current research on DTNs focuses on understanding mobility patterns, especially, human mobility and social network characteristics [5,6,4]. These efforts are motivated by the inefficiency or unsuitability of the existing protocols (e.g., MANET routing protocols) to DTNs. Recently, routing using knowledge of underlying mobility patterns is explored in [START_REF] Hui | BUBBLE Rap: Social-based forwarding in delay tolerant networks[END_REF][START_REF] Erramilli | Delegation forwarding[END_REF][START_REF] Spyropoulos | Efficient routing in intermittently connected mobile networks: The single-copy case[END_REF][START_REF] Balasubramanian | DTN routing as a resource allocation problem[END_REF]. However, these approaches either do not consider any resource constraints or present low adaptation capabilities.

Adjusting forwarding decisions on the fly while respecting resource constraints is thus an interesting challenge in DTNs and is the main focus of our research. To counter this challenge, Seeker, empowers nodes with the ability to make contact predictions that rely on local information (e.g., wireless connectivity and neighborhood variations). Hence, the novelty of Seeker is its ability to estimate good relays without having a global view. Nodes use simple online predictors, which estimate next contact opportunities based on a history of pair-wise contacts and their current context. This history includes both the quality of the connection between the nodes, whenever they meet, as well as the likelihood of successfully forwarding messages towards the destination. Nodes then make on the fly forwarding and data buffering decisions based on these estimations. Hence, Seeker takes advantage of the bias among different contacts [START_REF] Su | User mobility for opportunistic ad-hoc networking[END_REF] for more reliable communication. This behavior is especially advantageous, when the network is stable and the mobility patterns are highly predictable.

In addition, although a large amount of effort has been invested in designing routing algorithms for DTNs [START_REF] Hui | BUBBLE Rap: Social-based forwarding in delay tolerant networks[END_REF][START_REF] Erramilli | Delegation forwarding[END_REF][START_REF] Ramanathan | Prioritized epidemic routing for opportunistic networks[END_REF], the effect of buffer and bandwidth constraints in these algorithms has not received similar attention. Contrarily, Seeker respects these constraints and does not assume infinite buffers or bandwidth. Using contact-historybased estimations, Seeker propagates messages in a headlight fashion towards the destinations and so, maintains a reasonable memory, computation, and messaging overhead.

Finally, our protocol also considers that contact histories might not always be upto-date. Seeker drives opportunistic operation by taking advantage of new meetings and hence is not too tied to predictions. Nodes are able to rewind forwarding decisions and thus, save messages, based on local observations and through well-designed buffer management mechanisms. We assert this flexibility is the key to the adaptive operation of Seeker to different mobility conditions.

We study the performance of Seeker using simulations based on a synthetic mobility model and real mobility traces. The simulation results show that even if a simple prediction technique is used, Seeker is able to make good enough decisions to guarantee high reliability and acceptable delay in significantly different environments in terms of mobility. This flexibility to operate under different conditions renders Seeker invaluable for DTNs. Specifically, Seeker, with its adaptive behavior, is able to imitate the performance of best-performing option for each mobility scenario: maintains low overhead in static scenarios and high reliability in environments where connection opportunities are low. Finally, Seeker achieves these results with low control, buffering and forwarding overhead.

The remainder of this paper is structured as follows. In Section 2, we present the motivation for adaptive forwarding for DTNs and explain the design of Seeker. Sections 3, 4, 5 and 6 describe the main components of our protocol. Section 7 presents our evaluation study. Section 8 discusses the related work. Section 9 concludes with future work.

Emphasizing flexibility

The main goal of our research is to provide adaptive forwarding for matching mobility characteristics in DTNs. Additionally, when there are no disruptions due to mobility, it should be possible to take advantage of this and incur lower costs for higher reliability. To meet these challenges, we propose Seeker, which empowers nodes with the capability to learn and adapt based on past observations. Essentially, if a pattern exists among past contacts, future contacts can be estimated. Such estimations would be invaluable for managing message buffering and transmissions. On the flip side, however, when predictions do not match future behavior, it is necessary to rewind bad forwarding decisions to improve performance. Therefore, in the Seeker design, we emphasize flexibility to adapt to different situations to achieve a good trade-off between performance and cost.

We assume that a network may exhibit different levels of mobility, including being disconnected at certain times. Nodes, including destinations, might be static or mobile. All nodes are identical and have limited resources. Each node is able to communicate with a subset of neighbors that are in its transmission range. We do not assume symmetric communication. Nodes do not know their location or any topological information, such as where the destinations are. Given this model, our objective is to design a protocol that propagates messages to destinations in a headlight manner, thereby achieving high reliability and timely delivery with an acceptable overhead.

Clearly, these goals can be contradicting. The simplest way to achieve high reliability and timely delivery is epidemic routing [START_REF] Vahdat | Epidemic routing for partially-connected ad hoc networks[END_REF]. However, the good performance also comes with a high cost. Furthermore, if buffer and bandwidth constraints are taken into account, this performance might not be realized in practice. For instance, in a highly dense network with low mobility, epidemic routing might incur too much overhead, degrading also reliability (see Section 7). Current approaches for reducing this overhead require network topology awareness [START_REF] Ramanathan | Prioritized epidemic routing for opportunistic networks[END_REF] or highly predictable contact patterns [START_REF] Francois | Predictable disruption tolerant networks and delivery guarantees[END_REF]. Other approaches try to reduce the cost by selecting a few but good relays, by comparing the last meeting time with the destination or contact frequency, among other metrics [START_REF] Erramilli | Delegation forwarding[END_REF]. However, this might lead to being too conservative and losing good for-INRIA warding opportunities. To strike a balance, a protocol must be able to adapt to changes in the the node availability. To this end, Seeker enables nodes to learn their contact potential and base their forwarding decisions on this knowledge.

Intuitively, Seeker operates as follows. When node j receives messages from node i to deliver to a destination m, j takes charge of these messages probabilistically based on the expected connectivity to and connection quality with m. In other words, the more j believes it is on a good path leading to m, the more likely j is to carry and forward the message for i. This way, messages can be pulled towards destinations through higher quality paths. Paths with low connection quality or lower chance to meet the destination are weeded out since the nodes on these paths are gradually attached a low forwarding probability. Of course, in a generic DTN, connectivity and connection quality is not known ahead. Hence, Seeker needs to make estimations and be able to recover from bad decisions. This is achieved through four mechanisms:

• Contact history maintenance

• Contact prediction • Opportunistic forwarding • Buffer management
In Seeker, each node maintains a contact history. Based on this history, nodes make simple predictions about future meetings with their contacts. These predictions drive the opportunistic forwarding mechanism. Essentially forwarding decisions are left to the receivers of a message. Depending on their path quality to the destination of a message, nodes only forward the message at a time when they expect to meet their best contact for this job. However, when this time comes, nodes still locally broadcast the message to take advantage of other nodes in the vicinity. Finally, buffer management allows executing and rewinding the forwarding decisions. We present the details of these mechanisms in Sections 3 to 6.

Maintaining Contact History

In Seeker, a node builds a contact history as it meets other nodes in the network. By not limiting the contact information to destinations, nodes are able to exploit other communication opportunities through multi-hop paths. This information is essential for nodes that never come into contact with a destination [START_REF] Miklas | Exploiting social interactions in mobile systems[END_REF][START_REF] Su | User mobility for opportunistic ad-hoc networking[END_REF]. Next, we present how nodes detect connections and disconnections to other nodes.

Detecting connection

A node discovers it has come into contact with another node if it receives a message from the node. Since we do not assume symmetric communication, the reception of a message does not guarantee a bidirectional link, but a potential contact. Seeker utilizes the following messages:

• Data: The message to be sent to the destination.

• Ack: Sent by a destination for a received data message to the previous hop.

• Promise: Sent by a non-destination node to the previous hop, if it decides to forward the data message.

• Hello: Sent by all nodes to announce their presence.

Hello messages are sent periodically. Nevertheless, to reduce the control overhead, a node defers a hello message if it already sent other messages during the last period. In addition to well-used Hello messages for neighbor discovery in DTNs, we introduce two new messages, Ack and Promise, as indicators of path quality. An ack message, sent to the previous hop by the destination, confirms that it is able to receive the data messages. This is also important for determining connectivity quality to the destination. Similarly, promise messages enable nodes to verify connectivity with their non-destination contacts. Note that a promise only indicates a contact's willingness to forward the message but does not guarantee it. More specifically, on receiving a message from node j, a node i updates the following information in its contact table : (1) the time the first message is received, t start [START_REF] Benbadis | Elip: Embedded location information protocol[END_REF] the time the last message is received, t end and (3) for a specific destination m, the ratio of promise (or ack) messages sent by j to the number messages sent by i, d i j,m . Hence, for each neighbor j the following tuple is maintained: < t start , t end , .., (m, d i j,m ), .. >. While during the connection time, the node updates the same tuple for the given contact, a new tuple is started after a disconnection. We next present how a node detects a disconnection of a contact.

Detecting disconnection

Once connectivity is established with neighboring nodes, a node monitors if it is still connected to a given neighbor observing the time period between heard messages (i.e., hello, data, promise, ack). As the time interval between consecutive messages from a neighbor increases, it is assumed that the neighbor is moving away (and hence, its availability decreasing) and potentially a longer disconnection will ensue. A node i decides a disconnection has occurred if the availability for a neighbor node j, a i j falls below a threshold, δ. More specifically, availability is calculated as a i j = max{δ, 1silence/ silence} where silence is the time between observed messages and silence is maximum silence that can be tolerated by a node. Node i decides that node j disconnected, if a i j = δ. Discussion: We use fixed values for the silence and δ. We observed in our simulations that adapting silence based on the running average of inter-message times creates high dependency to traffic patterns and degrades performance. Therefore, silence is set as two times the hello interval. Additionally, when silence approaches 90% of silence (i.e., δ = 0.1), we suspect a disconnection. The reason behind not trying to set δ optimally is as follows. If δ is too low, nodes lose packets due to late disconnection detection and if δ is too high, nodes decide a disconnection too early and underestimate the contact quality. However, when calculating the contact quality, which is explained next, we take some measures to reduce these effect and hence, δ = 0.1 suffices.

As nodes detect connections and disconnections, they update their tables accordingly. In case the contact history table is full, the new contact might replace an old contact with low quality value. The size of the contact history and the number of tuples maintained for each contact are design parameters, which depend on the prediction method in use. Based on the recorded information, nodes estimate the quality of their contacts, which is the topic of the next section.

INRIA 4 Estimating Contact Quality

In Seeker, nodes that have good contacts have a high probability to forward a message. To evaluate contact quality, each node i uses its contact history to calculate (1) estimated remaining time to meet a contact j, t i j,wait and (2) expected service quality from the contact j, c i j,m (i.e., the rate of responding with ack or promise messages to data messages for destination m). Then, using t i j,wait and c i j,m , a node i calculates a quality value for each neighbor j for a given destination m, denoted as q i j,m , as follows:

q i j,m = e - t i j,wait t i j (k+1)) P • c i j,m (1)
As desired, q i j,m increases with increasing service quality and decreasing t i j,wait . Instead of using t i j,wait directly, t i j,wait is normalized with (t i j (k + 1)) P , the expected inter-contact meeting time between i and j, detailed hereafter. This is performed in order to avoid problems with varying time granularity with different mobility patterns.

In this section, we first present how t i j,wait and c i j,m are calculated. Second, we present how estimations that are necessary to calculate these values are made.

Calculating remaining time and service quality

The remaining time to meet a node, t i j,wait is calculated as follows. We denote the expected inter-contact meeting time between node i and node j for the (k + 1) th time as (t i j (k + 1)) P (where P indicates that this is a predicted value). At time t, given (t i j (k + 1)) P :

t i j,wait = t i j,last + t i j (k + 1)) P -t if disconnected 0 if connected (2)
where t i j,last is the last recorded meeting time of node j in node i's contact history table. However, if node i has not detected a disconnection to node j, then t i j,wait = 0. The service quality between nodes i and j for destination m, c i j,m , on the other hand, is determined by several factors. For instance, c i j,m depends on whether j = m, whether node i is currently connected to node j or not. Additionally, the number of messages sent in a row without hearing any promise or ack in response, referred as loss, is also indicative of low service quality. More specifically, if node j is not the destination and loss is greater than a threshold Δ, then node i concludes that it has a bad connection to node j. Essentially, this also allows saving messages when δ is selected too small, and hence, disconnection detection is slow. Finally, if node i is connected to node j, it uses the current delivery ratio, d i j,m , as a quality measure. The delivery ratio, d i j,m , is the ratio of promise or ack messages to the sent messages. If node i and node j are disconnected, node i relies on the predicted value of the delivery ratio, (d i j,m ) P as a service quality measure. The following formula summarizes the calculation of c i j :

c i j,m = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0 , j = m, loss ≥ Δ, d i j,m , j = m, loss < Δ, t i j,wait = 0, (d i j,m ) P , j = m, loss < Δ, t i j,wait > 0 min{1, β • d i j,m } , j = m, t i j,wait = 0, min{1, β • (d i j,m ) P } , j = m, t i j,wait > 0 (3) RR n°6816
Note that, using β > 1, the delivery ratio for a destination is artificially increased. Essentially, such boosting of the service quality of the destination allows prioritizing destinations over non-destination contacts. Hence, governed by the β parameter, node i improves its chances for waiting for the destination to send in one hop, unless the quality of the neighbor nodes are sufficiently high to motivate multi-hop communication.

Estimating remaining time and service quality

In this section, we discuss how we estimate inter-contact time, (t i j ) P and delivery ratio, (d i j,m ) P . Our estimations use exponential weighted moving average (EWMA), which gives higher priority to recent observations. This type of prediction is widely used by the networking community, for instance, for round trip time (RTT) estimation in TCP [START_REF] Paxson | Computing TCP's retransmission timer[END_REF]. Expected inter-contact meeting time: We calculate (t i j (k + 1)) P as follows:

(t i j (k + 1)) P = (1 -α) × (t i j (k)) P + α × t i j (k), (4)
0 ≤ α ≤ 1 is the constant smoothing factor, t i j (k) P is the previously estimated intercontact meeting time, and t i j (k) is the observed inter-contact meeting time. Estimating (t i j (k+1)) P more precisely may also be possible by using the results of current work on human mobility models, which show that pair-wise inter-contact meeting times exhibit a good fit with exponential or log-normal distributions [ 6]. Nevertheless, we chose to use EWMA for its simplicity. Furthermore, the current studies find a fit after examining the entire connectivity pattern. In our case, the parameters of the distribution need to be determined online as new contacts are established. Therefore, we leave the study of such estimators for inter-contact meeting time as future work. Expected delivery ratio: To calculate the expected delivery ratio for a destination m, the current delivery ratio of the neighbor, d i j,m (k) should be sampled during the connection time. Hence, nodes record d i j,m (k) at random sampling times until a disconnection is detected. On meeting node j after a disconnection, node i selects t s , which is the time to take a sample, based on the duration of the previous encounter (the default value is t hello if this is the first meeting). Hence, if the duration of the previous meeting is t prev d , the sampling time t s = U (0, t prev d ). Taking a sample consists of updating (d i j,m (k + 1)) P , with the current d i j,m (k) at t s , as follows:

(d i j,m (k + 1)) P = (1 -α) × (d i j,m (k)) P + α × d i j,m (k) (5)
After each sampling, the node resets its counters for sent, promise and ack messages and selects a new sampling time. This time, t s is chosen based on the length of current connection, t current d . Specifically, the new sampling time is

t s = U (0, t current d
). This continues until node i detects a disconnection, when it takes the last sample for this connection.

These estimations based on contact history allow a node to understand the quality of its contacts. In the next section, we present an opportunistic forwarding mechanism that adjusts forwarding decisions based on this contact quality.

Adaptive Forwarding

The main goal of our opportunistic forwarding mechanism is to use contact histories to make adaptive forwarding decisions. This approach is motivated by the recent user INRIA mobility traces that show a bias among different contacts [START_REF] Su | User mobility for opportunistic ad-hoc networking[END_REF]. Our goal is to utilize such bias for more reliable and resource-efficient communication. In the remainder of this section, we first explain the forwarding mechanisms and next, discuss how nodes take forwarding decisions. Finally, we conclude how these decisions can be modified based on current conditions.

Forwarding mechanism

In Seeker, forwarding is opportunistic as it makes use of nodes in the current neighborhood in addition to exploiting predictions based on contact history. Hence, while estimations based on the contact history suggest the best time to send the message, at the send time, the message is locally broadcast so that all neighbors receive it. As the message does not identify a next hop node, the responsibility of forwarding the data further is left to the receivers of the message. In Seeker, depending on the parameter setting, each message is sent up to x times to improve reliability. After a node processes a message, it adds the sequence number of the message to a table to gain immunity to further infections.

Forwarding decisions

In Seeker, on each message receipt, each node makes a "forward" or "not forward" decision. If the decision is "not forward", the message is still buffered for a short time to allow reevaluating decisions and saving messages. In the remainder of this section, we explain forwarding with and without contact history, and reevaluating forwarding decisions in more detail.

Forwarding without contact history

Initially nodes may not have enough history to make estimations, therefore, messages are broadcast with a fixed probability p. In this "no prediction" state, as a node receives hello, promise, ack, and data messages, it populates its contact history. When the node is able to make predictions, it switches to forwarding using contact history. We assume that once a node moves out of this "no prediction" state, it does not return to this state. However, if a node is disconnected, it might not be able to make accurate predictions. Nevertheless, the duration of bad decisions due to erroneous estimations is limited to the time interval of hello messages. A problem might arise only in the case where the neighbors of a node can hear the node but the node cannot hear anybody (i.e., all the links are asymmetric and outward), which we expect to be highly unlikely.

Forwarding with contact history

As a node i populates its contact table, it bases its forwarding decisions on the (1) number of contacts and (2) the quality of these contacts (i.e., q i j,m , which is explained in detail in Section 4.1). Hence, the messages are no longer forwarded with a fixed probability p but with a higher or lower probability depending on the state of contact history. In Seeker, the quality of contacts are used to determine this forwarding probability, p i as follows:

p i = max{p i max , p i avg 1 n }, (6)
where for all j, p i max = max q i j,m , p i avg = j q i j,m /n and n is the number of contacts. The goal of Eq. 6 is to emphasize both quality and the number of contacts, when deciding p i . For instance, if a node has the following list of q i j,m values, Q = {0.2, 0.3, 0.4, 0.5, 0.4}, p i = 0.76 due to a large number of contacts. This probability is 0.95 if the node has Q = {0.8, 0.9, 0.9, 0.9, 0.8} (i.e., the same number of neighbors but with better q i j,m ). On the other hand, if Q = {1, 0.1}, p i = 1 since the node has one very good contact.

Based on p i , if a node decides to forward a message, it places the message in its send buffer. Otherwise, the message is put in its quarantine buffer. (Buffer management is explained in detail in Section 6.) After putting a message in send buffer, the node sets a timer, the value of which is the t i j,wait of the contact with the best q i j,m . If the best contact is already connected (i.e., t i j,wait = 0), the message is still buffered for a short period of time, denoted as t jitter , to monitor the neighborhood and drop the message if there is much redundancy (see next section for further detail). Note that the value of the timer might change before it expires if a node hears new hello, promise or ack messages from good contacts. This actually drives the opportunistic operation of forwarding mechanism and allows taking advantage of new meetings without being too tied to the prediction mechanism.

When the send timer times out, the node sends the oldest buffered message for the given destination as a local broadcast. The send timer is rescheduled to the earliest time the next message can be sent based on the current conditions. This continues until all buffered data is sent.

Reevaluating forwarding decisions

Seeker allows rewinding forwarding decisions based on the current observations to improve performance and cost. For instance, since multiple nodes can rebroadcast a message, multiple copies of the same message might be received by a destination. To avoid this, nodes reevaluate their forwarding decisions as follows: [START_REF] Balasubramanian | DTN routing as a resource allocation problem[END_REF]The nodes that are in the vicinity of the destination and hear the destination send an ack, cancel the transmission of the message and (2) if a node hears a threshold number of promise messages for a data message, it again cancels the transmission. To realize this, nodes delay sending promise messages by t jitter . If the number of overheard messages reaches a threshold, overhear, before a promise message is sent, that transmission is canceled.

Based on [START_REF] Tseng | Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad hoc network[END_REF], if overhear > 4, the expected additional coverage from sending a broadcast is less than 5%. Hence, we calculate the threshold based on the number of neighbors, n nr as follows: overhear = min{4, nnr * fr}, (7) where f r represents the desired redundancy and 0 ≤ f r ≤ 1. On canceling a transmission, if a node needs to send x copies of a message, it reduces x by one. Since nodes that overhear each other's messages eventually drop these messages, the redundant copies are transmitted by nodes that do not hear each other. Hence, copies of the same message have a higher probability to be carried by independently moving nodes, increasing the chance to meet the destination. Therefore, reevaluating forwarding decisions in this fashion will allow reaching the destination through fewer nodes.

While rewinding a forward decision improves cost, rewinding a not forward decision might improve performance. A node changes its not forward decision if it observes no response for a message (i.e., a promise or an ack). Specifically, if a node does not hear any response during a threshold time t qack and its forwarding probability for this message is greater than 0, then it moves the message to its send buffer.

These corrective measures are similar to the ones described in [START_REF] Drabkin | RAPID: reliable probabilistic distribution in wireless ad-hoc networks[END_REF], which are shown to be effective to improve broadcast in wireless networks. A counter-based scheme which drops packets after overhearing a threshold number of the same packet is also INRIA proposed in [START_REF] Tseng | Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad hoc network[END_REF] to reduce broadcast overhead. Additionally, some of the inspiration comes from directed diffusion [START_REF] Intanagonwinat | Directed diffusion: A scalable and robust communication paradigm for sensor networks[END_REF], where higher quality paths are reinforced via interest dissemination. However, in directed diffusion, such reinforcement is explicitly triggered by the sender, whereas, in our case, it is enabled in an implicit manner, through opportunistic forwarding. Next, we explain buffer management of Seeker, which enables this type of reinforcements.

Buffer Management

Buffer management in Seeker becomes important as it allows storing data in the expectation of meeting a good contact. Furthermore, it allows rewinding some forwarding decisions. Hence, Seeker uses two different buffers:

• Send buffer: Stores messages that are waiting to be sent. If the node chooses to meet a better contact, the message is buffered until the meeting time of that contact.

• Quarantine buffer: If a node decides not to forward a message, it is stored for a short time in quarantine buffer.

In send buffer, the entry of each message contains the time the message is inserted into the buffer, the time the message should leave the buffer, the number of times it has been sent, the number of promise messages overheard, and whether a promise message has been sent. Based on these fields, the node does the bookkeeping of (1) if all x copies are sent, (2) if overhear is reached and (3) if the message can be deleted from the buffer.

The quarantine buffer has the same structure except the fields that record (1) the number of times the message has been sent and (2) whether a promise message has been sent. When the node overhears an ack or hears an overhear number of promise messages, it can safely drop the message.

When deleting messages from send buffer, we use source prioritized drophead policy [START_REF] Zhang | Performance modeling of epidemic routing[END_REF], where a node drops the oldest relay messages first followed by the oldest source messages. It is shown that with this policy, epidemic routing achieves almost the same performance as with an infinite buffer. As this complexity is not necessary in quarantine buffer, here, oldest messages are deleted first. While we chose these policies for their simplicity and good performance, Seeker can also work with more complex buffer management policies, which choose the messages to be discarded optimally [START_REF] Krifa | Optimal buffer management policies for delay tolerant networks[END_REF].

Performance Evaluation

Seeker is designed to take into account both the past behavior and current conditions to guide forwarding decisions. The goal of our evaluation is to show how such a design enables flexibility in significantly different environments in terms of mobility. Essentially, Seeker is expected to behave like the best performing choice and even achieve performance gains when node buffers and bandwidth are stressed, at each environment. We study four environments: (1) static network, (2) small network with a single mobile relay that guarantees connectivity and two networks, where the connectivity patterns of nodes follow the traces collected for (3) the Reality Mining project at MIT [START_REF] Eagle | CRAWDAD data set mit/reality (v. 2005-07-01)[END_REF] and ( 4) Haggle project at Cambridge [START_REF] Scott | CRAWDAD data set cambridge/haggle[END_REF]. We compared Seeker with the following protocols.

• Epidemic Routing (Epidemic): When two nodes meet, they exchange their packet summaries and based on this, exchange request packets that are not in their buffers [START_REF] Vahdat | Epidemic routing for partially-connected ad hoc networks[END_REF].

• Delegation Forwarding -Frequency (D-F) [START_REF] Erramilli | Delegation forwarding[END_REF]: Each node i records the total number of nodes it meets as τ i . A node i forwards a message to a node j, if j has a larger total number of contacts (i.e., τ i < τ j ). Node i adopts τ j as its new quality threshold.

• Delegation Forwarding -Destination Last Contact (D-DLC) [START_REF] Erramilli | Delegation forwarding[END_REF]: Each node i records the time it met a destination m as τ im . A node i forwards a message to node j, if node j met the destination m more recently than node i (i.e., τ im < τ jm ). Node i sets τ jm as its new quality threshold.

Additionally, for the static network study, we compare Seeker with DSDV [START_REF] Perkins | Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers[END_REF] (the best performing choice of this scenario). All protocols were implemented using ns2. To evaluate reliability and cost, we use five metrics: (1) delivery ratio, which is the ratio of packets delivered to the destination, (2) control overhead, which is the number of hello, ack, packet summary messages per data message, (3) message overhead, which is the buffering and forwarding count in the network per data message, (4) hop count defined as the average number of hops to destination, (5) delay defined as the time between a message is generated and delivered (including buffering delays). The protocol parameters used in simulations are summarized in Table 1. The network settings are presented in their respective sections. The transmission range of nodes is 250 m. Each source generates 256 B packets CBR. Different than previous studies, our evaluations neither assume infinite buffers nor infinite bandwidth.

Case 1: Static network

We first evaluate Seeker in a static environment, where 39 nodes are distributed uniformly random in 500 × 1500 m 2 . The average node degree is ≈ 7.1. Given a high number of neighbors and a connected network, our goal is to show that Seeker is able to find and use stable routes.

Fig. 1 depicts the delivery ratio when the percentage of senders in the network is 25-100% of all nodes. Each sender generates messages at 2 Kb/s to a single destination for INRIA Figure 1: Static network: Delivery ratio. 300 s. Despite its opportunistic operation, Seeker performs similar to DSDV when the number of senders is low. However, as the number of senders increases, the delivery ratio degrades from 0.9 to 0.62. This is due to Seeker sending an ack for each data message, which increases contention. As future work, we plan to try sending a single ack for a window of messages. This will be similar to Epidemic, which has a lower control overhead (in terms of packets, not bytes) as one summary message is sent for all buffered messages. However, the overhead of Epidemic is still high as each message is forwarded to each contact. Even for 25% senders, ≈ 75% of nodes forward a message in Epidemic, compared to ≈ 48% in Seeker. This high overhead also results in high contention and hence, low delivery ratio. In contrast, D-F and D-DLC suffer from being too conservative. In D-F, each node waits for a node that has higher number of contacts than seen so far, which might not ensure a path to the destination. In D-DLC, each node waits for a node that has met the destination later than any node it has seen so far. However, this information might propagate slowly in a static network. Hence both D-F and D-DLC forwards fewer messages, which results in poor delivery ratio.

We also calculate the route quality of Seeker as the percentage of messages that are sent over longer routes compared to the ideal case, i.e., the shortest-path for each flow is computed offline. Our results for 25% senders case show that 73-87% of the messages are delivered with at most 1-hop increase. Furthermore, given the number of messages received by the destination, r k , and the number of unique messages received by the destination, u k , for a flow k, the redundancy factor is (r ku k )/r k and in Seeker, range between 17-38%. This shows that Seeker is able to find and use good routes effectively.

Case 2: Single mobile relay

In DTNs, it is essential to exploit transitive contacts to enable message delivery. To show Seeker is able to learn and to adapt accordingly, we use the following example, where the source s and destination d are separated by 600 m and a relay node i travels this distance enabling connectivity between them. There is also a second static node j, which is in the range of s and sometimes i, when i gets close enough to s. The only way to ensure delivery is to forward the data to node i. The scenario is simple but significantly challenging since there is a highly available neighbor, j, which seems attractive for forwarding but useless to reach the destination.

In our simulations, s generates a message every ≈ 5 s until 200 messages (i.e., at a rate 0.2 Kb/s). The simulation run is 4555 s. Fig. 2 depicts the control and message overhead, and the delivery ratio. Except D-F, all protocols have high delivery ratio. The delivery ratio of D-F is 0 since i and s have the same number of contacts. D-DLC has 100% delivery ratio but also the highest control overhead since for each message, the destination contact times are compared. Furthermore, with D-DLC the first message is forwarded at time ≈ 198 (i.e., after i met d and returned to s) compared to ≈ 104 both in the case of Seeker and Epidemic. Note that Epidemic incurs 39% more control overhead than Seeker as it sends a summary message to both its neighbors. We also see the same effect when we calculate the ratio of messages that are sent when i is not in s's neighborhood (S-R miss ratio) and when d is not in i's neighborhood (R-D miss ratio). When calculating these ratios, a batch of messages is counted as one message if the time difference between transmissions is ≈ 0. Hence, with Epidemic S-R miss ratio is ≈ 80% (since s forwards each message to j as it generates them, while it sends a batch of messages when i returns). In comparison, Seeker has 28% S-R miss ratio, which shows that s was able to learn about the better relay i. However, the R-D miss ratio of Seeker is 18% due to wrong predictions, while with Epidemic, i always forwards messages to d timely.

Case 3: Mobility based on traces

In this section, we present how Seeker behaves when the nodes follow a mobility pattern based on MIT and Cambridge traces. For each run, 16 source nodes are selected uniformly random to send 10 messages to a single destination. Next, we filter the flows which do not have a path or do not stay connected long enough to the destination by running Epidemic with each source separately. The results with multiple destinations are not presented for the sake of brevity as they show similar trends with lower delivery ratios.

MIT Reality Mining traces Due to the long length of MIT traces, we chose 3 different days with the highest number of connections. The results depict an average of 30 scenarios with 2-10 randomly generated flows.

The characteristic of MIT traces is that connectivity opportunities are scarce: ≈ 50% of the nodes meet only once and ≈ 94% of the nodes meet at most three times. Therefore, Epidemic achieves the best delivery ratio as it forwards messages to all neighbors (see Fig. 3). In contrast, D-F and D-DLC, which are more conservative, achieve low delivery ratios, 59% and 47%, respectively. Additionally, D-DLC incurs the highest control overhead. We evaluated Seeker's performance when nodes forward a message up to x = 2 -6 times. Essentially, increasing x improves the delivery ratio without much effect on the overhead. Note that such tuning is not possible with D-F or D-DLC. However, as this does not mean x distinct neighbors receive the message (since Seeker does not identify the next hop in the message), the additional copies might be wasted by being received by the same nodes. Therefore, while Seeker does not reach 91% delivery ratio, the delivery ratio improves to ≈ 80% with x = 6. However, note that this is the best case scenario for Epidemic, as its control, forwarding, and buffering overhead could be amortized by its high delivery ratio. It would incur similar overhead even though it cannot deliver any messages, whereas the message overhead of Seeker is low when the delivery ratio is low (e.g., less messages are acked). Fig 4 depicts the delay and the hop count. While Seeker and Epidemic perform similarly, D-F and D-DLC have slightly lower delays due to shorter hop counts. As expected, in D-F and D-DLC messages do not find a chance to be propagated far and hence the hop counts are short. However, they incur additional delays for waiting for better contacts.

Cambridge Haggle Traces

The experiments in this section were run similarly to MIT traces. The results depict an average of 10 scenarios, which include 4-8 flows. In contrast to MIT traces, in Cambridge traces, contact opportunities are plenty: only The results also verify our expectations, as Seeker is able to achieve better delivery ratio than Epidemic due to its lower overhead (see Fig. 5). Note that, although Seeker has comparable control overhead compared to Epidemic (due to sending an ack for each message as discussed in section 7.1) it is able to reduce the number of times each message is forwarded and buffered. Additionally, since there are more contact opportunities, increasing x does not necessarily yield better performance; however, it does not hurt the performance either. Also note that, D-F and D-DLC both perform similarly to MIT traces and hence, are not able to take advantage of the higher number of contacts. Finally, Fig. 6 shows that Seeker achieves better delay compared to all protocols. These results are an outcome of Seeker's ability to choose better relays and hence, to reduce message forwarding overhead. In comparison, D-F and D-DLC incur highest delays as both protocols wait too long to pass the message to their neighbors.

In summary, our performance evaluation shows that blindly trying to reduce forwarding and buffering overhead might degrade performance in terms of both delivery ratio and delay. Learning from the past and adapting to the current conditions allows Seeker to perform with high performance and low overhead in environments with significantly different mobility.

INRIA 8 Related Work

In DTNs, communication experiences frequent and long disconnections. Therefore, current research focuses on opportunistic forwarding. In [START_REF] Grossglauser | Mobility increases the capacity of ad-hoc wireless networks[END_REF], messages are forwarded to the first relay met, which in turn forwards the data to the destination. Since the goal was to show that mobility can improve the capacity of wireless networks, the relays were chosen purely based on a first contact opportunity. However, the expected delay of two-hop forwarding may grow to infinity for some mobility models. This is the case under some power-law distributions, which characterizes the aggregate intercontact time in some DTNs [5]. Therefore, when selecting contacts, the underlying connectivity patterns should be considered. For instance, bounded delay is possible, if the message is forwarded to multiple nodes instead of one. However, the results on empirical studies vary as a more optimistic result is given in [ 6], where pairwise inter-contact times are found to be exponentially or log-normally distributed. Empirical evidence also shows that contacts with friends are more valuable than strangers [START_REF] Miklas | Exploiting social interactions in mobile systems[END_REF][START_REF] Su | User mobility for opportunistic ad-hoc networking[END_REF]. Nevertheless, these studies show that there is a bias among different contacts. The knowledge of contact patterns is thus, expected to improve forwarding performance.

In an ideal world, if each node knew the contact probability, waiting times [START_REF] Francois | Predictable disruption tolerant networks and delivery guarantees[END_REF][START_REF] Jain | Routing in a delay tolerant network[END_REF], buffer limits, and traffic demands [START_REF] Jain | Routing in a delay tolerant network[END_REF], the delivery probability and delay of different strategies could be computed. However, as these are not typically available, one approach is to disseminate similar information to the entire network. PREP [START_REF] Ramanathan | Prioritized epidemic routing for opportunistic networks[END_REF] exchanges link availability to drop packets that have worse chance of delivery. In [START_REF] Su | An empirical evaluation of the student-net delay tolerant network[END_REF], a link-state protocol records the expected delay to each node in the network and a message is forwarded to a node only if the message would experience less delay. However, the performance is worse than epidemic routing due to the significant warm-up time of link-state tables, conflicting decisions due to state changes, and the lack of replication. While these approaches propagate information to the entire network, more local algorithms also exist [START_REF] Spyropoulos | Efficient routing in intermittently connected mobile networks: The single-copy case[END_REF][START_REF] Dubois-Ferriere | Age matters: Efficient route discovery in mobile ad hoc networks using encounter ages[END_REF][START_REF] Benbadis | Elip: Embedded location information protocol[END_REF].

Similar to Seeker, several approaches also estimate a delivery likelihood [ 3,[START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF], which is based on the frequency of meeting with contacts. However, although nodes exchange their entire information with all contacts, [ 3] shows that the majority of savings come from prioritizing messages based on the current hop count and disseminating acks to delete delivered messages from buffers. More suited to social DTNs, BUBBLE [START_REF] Hui | BUBBLE Rap: Social-based forwarding in delay tolerant networks[END_REF] and SimBet [7] use information about social community structures to choose good relays. Essentially, using such quality information improves routing cost, although it does not always improve reliability [START_REF] Erramilli | Delegation forwarding[END_REF][START_REF] Spyropoulos | Efficient routing in intermittently connected mobile networks: The single-copy case[END_REF].

Most importantly, the majority of the approaches assume infinite buffers and bandwidth, while exceptions are [START_REF] Balasubramanian | DTN routing as a resource allocation problem[END_REF][START_REF] Krifa | Optimal buffer management policies for delay tolerant networks[END_REF]3]. In [START_REF] Balasubramanian | DTN routing as a resource allocation problem[END_REF], at each forward opportunity, nodes evaluate if the gain from replicating a message justifies the resources used. However, such an evaluation relies on information about the replicas of a message in the entire network. This problem is addressed in [START_REF] Krifa | Optimal buffer management policies for delay tolerant networks[END_REF], where the total number of replicas are estimated locally to decide which messages to replicate or drop to achieve either minimum delay or maximum delivery ratio. Nevertheless, nodes are still required to maintain a history of each message forwarded by each node they meet.

In Seeker, we use similar information with existing approaches to make simple predictions about future meetings. However, our goal is to learn from contact and communication patterns to gracefully adapt to different mobility conditions. This consequently improves both reliability and cost by maintaining and exchanging as less information as possible.

Conclusion

Routing in DTNs requires careful selection of relays, scheduling transmissions, and managing buffers to guarantee reliable, timely and low-cost delivery. To this end, many approaches rely on a quality metric in an attempt to achieve a trade-off between forwarding cost and performance. In this paper, we show that this may be too conservative and hence, degrade performance in the presence of different levels of mobility. The main contribution of this paper is a new adaptive forwarding protocol, Seeker, which is indeed able to match different mobility patterns. Seeker does not consider infinite buffers or bandwidth and allows nodes to modify their forwarding strategy based on their perception of the past and current conditions. Hence, Seeker achieves high flexibility, which is invaluable for DTNs, with a simple prediction mechanism. Nevertheless, for future work, we plan to investigate the benefit of more advanced prediction mechanisms on performance.

Figure 2 :

 2 Figure 2: Single mobile relay: Control and message overhead (left y axis) and delivery ratio (right y axis).

Figure 3 :

 3 Figure 3: MIT Trace: Control and message overhead (left y axis) and delivery ratio (right y axis).

Figure 4 :

 4 Figure 4: MIT Trace: Delay (left y axis) vs. hop count (right y axis)

Figure 5 :

 5 Figure 5: Cambridge Trace: Control and message overhead (left y axis) and delivery ratio (right y axis).

Figure 6 :

 6 Figure 6: Cambridge Trace: Delay (left y axis) vs. hop count (right y axis)

Table 1 :

 1 Simulation Parameters

	Contact history and prediction parameters
	K	Contact history size	10
	Δ	Consecutive loss threshold	3
	α	EWMA constant (Eq. 4)	0.9
	β	Sink priority (Eq. 3)	2
	Opportunistic forwarding parameters
	p	Initial forward prob.	0.7
	SB	Send buffer size	64
	QB	Quarantine buffer size	50
	t hello	Hello interval	5 s
	t qack	Quarantine timeout	1 s
	x	Max. # of gossips	1-6
	fr	Desired redundancy	0.5
	tjitter	Observation jitter	0.01 s

RR n°6816

Sengul & Carneiro Viana & Friedman & Bertier & Kermarrec


Benjamin Camblor

Nassim Benhabib

David Daney

Vincent Padois

Jean-Marc Salotti

Signaling

Signaling Motions for communication in human-robot interaction

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

The experiment does show a positive effect of both postural encoding and breathing motions on performance and safety.

The signaling motions appeared to enhance the participants mental model during interactions with the two cobots.

The results are not only caused by a learning effect. One one hand, a slight intra-modality learning effect can be observed on the completion time. On the other hand, a strong decreases can be observed if we look at the inter-modality differences.

6

These communication motions are called signaling motions. They are superimposed on the main motion of the cobot (used for its task) using the unused degrees of freedom for the task. They allow to provide information to the operator about the task or the state of the cobot. The particularity of these additional movements is that they do not affect the main task of the cobot and only act as a complement.

In this work two signaling motions have been defined:

• An explicit motion: it is linked to the task, keeps the human involved in the task and helps in decision making;

• A diffuse motion: it is independent of the task, covers a wide range of contexts and user expertise and informs about the cobot status.

SIGNALING MOTIONS

The integration of collaborative robots (cobot) in industrial environments depends on their acceptance by operators and the potential for symbiotic work between these partners. The safety of operators is thus a priority in the implementation of these industrial environments.

The complexity and variability of tasks and workspaces can lead to hazardous situations for operators. It is therefore important to study the means of communication available to reduce risks in industrial environments.

In this work, it has been proposed to use the cobot's motion to communicate with an operator and improve his performance and safety.

CONTEXT

The purpose of this work was to evaluate the effects of two signaling motions on participants task performance and behavior toward a cobot.

More specifically, the experiment consists of a simulated wood cutting task that requires a joint effort between a robot (Cobot 1) and an operator. In addition, the behavior of the individual is also studied when moving near a second robot (Cobot 2) sharing the same workspace.

-Cobot 1 performs an explicit motion during the task, called postural encoding. This motion is intended to facilitate the understanding and execution of the task. -Cobot 2 performs a diffuse motion, called breathing. This motion aims to enhance the safety of the individual in the working environment.

  Benjamin Camblor, Nassim Benhabib, David Daney, Vincent Padois, and Jean-Marc Salotti. 2022. Task-Consistent Signaling Motions for Improved Understanding in Human-Robot Interaction and Workspace Sharing. In Proceedings of the 2022 ACM/IEEE International Conference on Human-Robot Interaction (HRI '22). IEEE Press, 275-283.


Maria Vilkman

Mari Ylikunnari

Olli Sorsa

Anssi Laukkanen

Doniyor Urishov

Samuel Malburet

Yassine Nait Abdi

Manuel Maréchal

Said Sadki

Patrice Rannou

Materials and processing methods for stable lithium-metal batteries

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Marja Vilkman: Materials and Processing Methods for Stable Lithium-Metal Batteries

Materials and Processing Methods for Stable Lithium-Metal Batteries

Marja Vilkman 1 , Mari Ylikunnari 2 , Olli Sorsa 1 , Anssi Laukkanen 1 , Doniyor Urishov 2 , Samuel Malburet 3 , Yassine Nait Abdi 4 , Manuel Marechal 5 , Said Sadki 5 , and Patrice Rannou 4 Solid-state Lithium-Metal (Li°) Batteries (LMBs) are foreseen as enablers for safer-by-design and higher e nergy density post-Lithium-ion electrochemical energy storage 2.0 s olutions. They a re considered as part of the solutions to address the United Nation Sustainable Development Goal N°7 and to reach a carbon neutral European continent by 2050. As LMB-based materials are (at least in part) different from the ones currently used in state-of-the art Li-ion Batteries (LiBs), this is creating a technology push to adjust processing methods for manufacturing Generation 4b batteries. Shifting paradigm from LiBs to LMBs is also calling for major improvements of their lifetime as their interfaces are (i) prone to degradation or (ii) can suffer from dendrite growth or contact loss.

Soft-matter-based organic electrolytes offer here an innovative and scalable materials platform to manufacture LMBs and ways to improve their lifetimes through varying their chemical structures and processing. We will present results implementing this strategy from the ongoing Battery 2030 + HIDDEN project [1], where Thermotropic Ionic Liquid Crystals (TILCs), the 'materials marriage' of Thermotropic Liquid Crystals (TLCs) with ionically conducting materials, have been developed as a new generation of self-healing electrolytes (see Figure 1) aiming specifically at (i) mitigating Li° dendrite growth and (ii) increasing the lifetime of LMBs.

TLCs are fluid-like but dynamically ordered self-assemblies under a certain temperature range. If used as electrolytes, TLCs need to be engineered to encode ionic transport features for generating TILCs specifically designed to assist controlled Li + transport and to ensure smooth Li deposition onto a Li° electrode, preventing dendrite formation. We will discuss how HIDDEN has leveraged this concept through a series of TILCs enabling a scalable process to coat the electrolytes onto/within the electrodes and to generate data for modelling, thereby implementing the MAP and BIG-MAP concepts at the heart of the Battery 2030 + initiative. In closing, we will also disclose a few highlights from two other projects where we are developing materials and processing methods with polymeric electrolytes for LMBs: A national Finnish project NextGenBat [2] and the just-started Horizon Europe project SOLiD.

Figure 1 .

 1 Figure 1. Schematic of the self-healing method based on a liquid crystalline electrolyte.

Acknowledgments: This research is funded by the European Union's Horizon Europe (SOLiD project) and Horizon 2020 research and innovation programmes (HIDDEN project: Grant agreement N°957202), and by Business Finland's Smart Mobility and Batteries from Finland program.