Thrasyvoulos Spyropoulos

Thierry Turletti

Katia Obraczka

Utility-based Message Replication for Intermittently Connected Heterogeneous Networks

Keywords: routing algorithms, delay tolerant networks, episodic connectivity, opportunistic routing

Communication networks (wired or wireless) have traditionally been assumed to be connected at least most of the time. However, emerging applications such as emergency response, special operations, smart environments, VANETs, etc. coupled with node heterogeneity and volatile links (e.g. due to wireless propagation phenomena and node mobility) will likely change the typical conditions under which networks operate. In fact, in such scenarios, networks may be mostly disconnected, i.e., most of the time, end-to-end paths connecting every node pair do not exist. To cope with frequent, long-lived disconnections, opportunistic routing techniques have been proposed in which, at every hop, a node decides whether it should either forward and/or store-and-carry a message. As a result, a number of message replicas may be created and routed independently ("spraying"). Most opportunistic routing schemes to-date perform greedy replication handing over a copy of a message to the first nodes encountered. Yet, in a network with heterogeneous nodes, where some nodes may be much "better" relays than others, such greedy schemes waste a lot of message replicas (and thus energy, storage space, etc.) on "useless" relays. For this reason, we propose the idea of utility-based replication, where some fitness or utility function is maintained for all nodes in a distributed fashion, and a small budget of message replicas is allocated according to this utility only to the fittest nodes. We describe a number of variations using different utility functions, and show that an improvement of up to 5 -6× in delay can be achieved over greedy algorithms.

Mécanismes de Transmission basés sur l'Utilité des Noeuds pour Réseaux à Connectivité Épisodique

Résumé : Les réseaux de communication (filaires ou sans fil) font habituellement l'hypothèse que les noeuds restent connectés la plupart du temps. Cependant, cette hypothse s'avre moins réaliste avec l'arrivée des nouvelles applications (e.g., communication d'urgence aprs catastrophes naturelles, réseaux véhiculaires, etc.) et en raison de la volatilité des liaisons (e.g. due à la grande variabilité des caractéristiques des canaux de transmission sans fil et/ou à la mobilité des noeuds). Ainsi, avec ces nouveaux scénarios, les réseaux peuvent tre le plus souvent déconnectés: il nexiste pas toujours de chemin en permanence entre la source du message et le(s) destinataire(s). Des techniques de routage opportunistes ont été proposés pour ce type d'environnement dans lequel chaque noeud, à la réception d'un paquet, doit décider si il doit transmettre le paquet recu et/ou le conserver afin de l'acheminer à destination. Avec ce type de mécanisme, certains paquets peuvent être dupliqués à plusieurs reprises et routés de manière indépendante (i.e.,"spraying"). La plupart des algorithmes de routage opportuniste qui ont été proposés, transmettent des copies des messages recus aux premiers noeuds rencontrés (i.e., greedy replication). Cependant, lorsque les noeuds du réseau sont hétérogènes, certains noeuds sont de meilleurs relais que d'autres, et les algorithmes de routage peuvent émettre inutilement un grand nombre de copies de messages (et donc gaspillage de batterie, d'espace mémoire, d'occupation du canal, etc.) en utilisant des relais inutiles. Pour cette raison, nous proposons l'idée de réplication de paquets basée sur l'utilité des noeuds, o une fonction d'utilité est maintenue à jour pour tous les noeuds de manière distribuée, et un budget restreint de copies de message est alloué uniquement aux noeuds qui sont les plus utiles. Nous présentons dans ce rapport de recherche un ensemble de mécanismes qui utilisent différentes notions d'utilité des noeuds et nous montrons qu'un délai de transmission 5 à 6 fois moins élevé peut être obtenu de cette manière par rapport aux algorithmes de routage classiques (i.e., greedy).

Mots-clés : Algorithmes de routage, Réseaux à connectivité épisodique, Réseaux tolérants aux délai, Routage opportuniste.

Introduction

The traditional view of networks as a connected graph over which end-to-end paths need to be established might not be appropriate for modeling existing and emerging wireless networks. Due to wireless propagation phenomena, node mobility, low power nodes shutting down, etc., connectivity in wireless networks is more often than not intermittent. Under such intermittent connectivity many traditional routing protocols, both table-driven (e.g. based on link-state routing) and reactive ones (e.g. DSR, AODV), would have their performance deteriorate drastically as connectivity becomes increasingly sporadic and short-lived.

To perform routing under "episodic" connectivity, researchers have proposed a variety of opportunistic routing schemes [START_REF] Jones | Routing strategies for delay-tolerant networks[END_REF]2,3], where: (i) a message may be stored and carried by a node for long periods of time, until a communication opportunity arises ("mobilityassisted"), (ii) local forwarding decisions are made independently with the goal that a message will eventually be delivered ("opportunistic"), and (iii) multiple copies of the same message may be propagated in parallel in the above manner ("replication").

One of the schemes proposed that has shown promising performance is that of "Controlled Replication" or "Spray and Wait" [START_REF] Small | Resource and performance tradeoffs in delay-tolerant wireless networks[END_REF][START_REF] Neglia | Optimal delay-power tradeoff in sparse delay tolerant networks: A preliminary study[END_REF]3]. This scheme distributes a small and controlled number of message replicas to the first few nodes encountered (we'll be referring to this basic algorithm as "greedy" controlled replication, or simply "greedy replication", hereafter); then, each of the nodes that received a copy in this first phase is only allowed to give it to the destination itself1 . There are two desirable characteristics connected with this approach: (i) it consumes much fewer resources than epidemic routing [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF] and its variations [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF][START_REF] Juang | Energyefficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet[END_REF] with sometimes little or no penalty on performance [START_REF] Neglia | Optimal delay-power tradeoff in sparse delay tolerant networks: A preliminary study[END_REF]3], and (ii) due to its simplicity, it can be controlled to achieve the desired performance trade-off (resources used vs. delivery delay/probability), even in an almost unknown environment, by appropriately choosing the number of copies [3].

In a network where most nodes are highly "mobile" and make decisions independently (e.g. VANETs [START_REF] Blum | Challenges of intervehicle ad hoc networks[END_REF] 2 ), greedy replication could be a simple and efficient-enough solution; there, each relay carrying a message copy encounters new nodes quickly, and picking just a few (even randomly) could create enough redundancy to ensure one of them will encounter the destination soon. On the other hand, imagine a scenario where the majority of nodes tend to spend most of their time with the same nodes (e.g. employees on the same group or floor, animals in the same herd or family [START_REF] Juang | Energyefficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet[END_REF]), while only a small number of nodes tend to move often between disconnected parts of the network (e.g. vehicles, nodes with a more "social" daily routine, etc.). In such a scenario, handing over copies to the first few nodes encountered, implies that some or all of these copies will end up with nodes that may never encounter the destination. In general, when nodes in a network are heterogenous in terms of their ability to deliver a message, greedy replication may fail to discover the "better" relays, especially if the latter are much less common than the "not so good" ones.

To deal with this situation, it has been proposed to allow an initially chosen relay to hand-over its message replica to another node, if it is deemed that the latter one has a higher chance of encountering the destination (according to some agreed "utility" measure [3,[START_REF] Dubois-Ferriere | Age matters: efficient route discovery in mobile ad hoc networks using encounter ages[END_REF]). This scheme can discover better and better relays than the set of the initially chosen ones, and using a gradient-based approach can deliver a message to the destination faster. Although it still uses the same number of replicas per message, each replica may be transmitted more than once, and may even loop around due to the dynamic nature of the utility function maintained. What is more, unlike the case of controlled replication, it is significantly more difficult to analytically predict the number of transmissions and expected delay for this scheme [3].

Summarizing, although allowing multi-hop forwarding of each copy can improve the delivery delay of controlled replication in heterogeneous networks or networks with correlated mobility patterns, it does so at the expense of guaranteed resource usage. This can be a rather undesirable feature of the protocol for some applications. For example, assume an application has stringent energy constraints but some flexibility in the delivery ratio or delay of messages (e.g. a low power sensor network where there is inherent redundancy in the data transmitted). Then, it might be significantly more important to ensure that a bounded amount of energy will be spent per message rather than trying to maximize delivery ratio. As a different example, in a self-organized network where a credit-based system is used to incite collaboration between nodes [START_REF] Zhong | Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks[END_REF] it is important for the user to be aware exactly how many credits a message will consume.

To this end, we propose the idea of smart replication or utility-based replication. Similar to the basic, greedy replication algorithm, a fixed number of copies is used; these copies are distributed into a chosen set of relays, and no further forwarding is allowed. This ensures that the total number of transmissions (and thus other resources used) is controlled and known in advance. However, instead of naively (greedily) handing copies to the first nodes encountered, relays are chosen according to a utility function. This ensures that the fixed budget of message copies is allocated only to the "fittest" possible relays, and no copies are wasted on "non-useful" nodes. In short, our aim is to have control and predictability of resource usage at the highest priority, while at the same time try to achieve the best performance possible given this fixed set of message replicas.

In the next section, we will describe the basic utility-based replication algorithm, and present some variations of it. Additionally, we give some insight into how utility-based replication can be tuned to achieve the desirable performance tradeoff. Then, in Section 3 we'll present simulation results comparing different flavors of utility-based replication against greedy replication. Finally, we'll conclude and present some future work directions in Section 4.

Greedy Replication in Heterogeneous Environments

Controlled replication or "Spraying" is considered to be an efficient method to reduce the large overhead of epidemic-based schemes, without often incurring significant delay penalties [3,[START_REF] Small | Resource and performance tradeoffs in delay-tolerant wireless networks[END_REF][START_REF] Neglia | Optimal delay-power tradeoff in sparse delay tolerant networks: A preliminary study[END_REF]. The basic controlled replication algorithm is the following: Definition 2.1 (Spray and Wait) When a new message is generated at a source node, this node also creates L "forwarding tokens" for this message. A forwarding token implies that the node that owns it, can spawn and forward an additional copy of the given message. During the spraying phase messages get forwarded according to the following rules: if a node (either the source or a relay), carrying a message copy and c > 1 forwarding tokens for this message, encounters a node with no copy of the message3 , it spawns and forwards a copy of that message to the second node; it also hands over l(c) tokens to that node (l(c) ∈ [1, c -1]) and keeps the rest cl(c) for itself ("Spray" phase); when a node has a message copy and c = 1 forwarding tokens for this message, then it can only forward this message to the destination itself ("Wait" phase).

There are two flavors of the basic scheme that have been proposed. In the 2-hop version of the scheme [START_REF] Groenevelt | Message delay in manet (extended abstract)[END_REF], only the source may forward an extra copy (i.e. l(c) = 1 in the above description). In the (binary) tree-based version [3,[START_REF] Small | Resource and performance tradeoffs in delay-tolerant wireless networks[END_REF], l(c) = c 2 for any node with c > 1 tokens. The common characteristic of these two algorithms is that they're both greedy. By "greedy" here it is meant that any opportunity to forward one of the available copies to a new node with no copies will always be seized upon. In other words, the budget of L message replicas will be distributed to the L first nodes encountered.

The tree-based greedy algorithm is shown to be optimal in a homogeneous environment (I.I.D. node mobility) [3,[START_REF] Small | Resource and performance tradeoffs in delay-tolerant wireless networks[END_REF]. The intuition behind this it that, if all nodes are statistically equivalent [START_REF] Aldous | Reversible markov chains and random walks on graphs[END_REF], there is no benefit in waiting when a forwarding opportunity arises. Nevertheless, if nodes are heterogeneous (e.g. different mobility characteristics, different resources, etc.) greedy distribution of message copies can be easily shown to be sub-optimal. Consider, for example, an intermittently connected network of mobile nodes, where a percentage p of the nodes are not (that) useful in delivering a message to a remote destination (e.g. move very slowly, or encounter few new nodes over time). We'll call these "snail" nodes. If we assume uniform mixing rates [START_REF] Aldous | Reversible markov chains and random walks on graphs[END_REF] for both normal and snail nodes, then with greedy replication pL of the copies, on average, would end up with snail nodes 4 . Using the delay equations of [3] or [START_REF] Small | Resource and performance tradeoffs in delay-tolerant wireless networks[END_REF], it is not difficult to show that the performance degradation compared to the case where all nodes are "non-snail" ones is approximately given by Delay(p snail) Delay(normal)

≈ c 1 + c 2 1 -p ,
where c 1 , c 2 are constants, such that c 1 + c 2 = 1. This equation implies that if the number of snail nodes is large, then the delay of greedy Spray and Wait quickly increases. The reason for this is that greedy replication cannot identify nodes that are not useful, and mistakenly hands them over some copies. The larger the percentage of non-useful relays in the network, the larger the negative impact of greediness. Of course, a more appropriate comparison would be against the delay of the optimal algorithm given p snail nodes. Nevertheless, the above equation already provides enough insight about the expected performance degradation due to heterogeneity.

Utility-based Spraying

Based on the previous exposition we can draw the following conclusion: in a heterogeneous environment, where a limited budget of L message copies needs to be distributed to L relays, a mechanism is necessary that will distinguish the "better" relays, and avoid using the least useful ones. Ideally, we would like to find the L best relays in the network (given some optimization criterion). However, this problem is not trivial, even in moderately complex scenarios [START_REF] Jindal | Optimizing multi-copy routing schemes for resource constrained intermittently connected mobile networks[END_REF], especially given the fact that candidate relays appear (i.e. are encountered) not all-together, but in an online fashion. Therefore, here we will turn our attention to heuristic methods to decide on the fitness or utility of a given node as a relay. Definition 2.2 (Utility-based Spraying) Similarly to the basic spraying algorithm (see Def. 2.1), Utility-based Spraying uses forwarding tokens to grant a node the right to further forward message copies. Additionally, each node i maintains a utility function U i (j) for every other node in the network j. U i (j) reflects the probability that node i will deliver a message to node j, and it may be based on a number of different parameters (e.g. encounter history, mobility, friendship index with j, etc.) if a node i (either the source or a relay) carrying a message copy for a destination d and c > 1 forwarding tokens for this message encounters a node j with no copy of the message, it spawns and forwards a copy of that message to the second node according to one of the following rules:

rule 1: if U j (d) > U th for some U th threshold value ( absolute utility criterion);

-rule 2: if U j (d) > U i (d) ( relative utility criterion); INRIA It also hands l(c) = c
2 forwarding tokens to that node and keeps the rest c 2 for itself (i.e. tree-based) 5 ;

We are going to describe different variations of this basic algorithm in terms of the utility function they use. Each algorithm could use either of the forwarding rules above ("absolute utility" or "relative utility") or a combination of them (e.g. "use rule 1 to ensure a minimum utility and then rule 2 among the nodes that qualify"). Rule 1 requires a good threshold parameter U th to be found in every case. Rule 2 is easier to implement, yet it does not guarantee that all "bad nodes" will be avoided (e.g. "very low utility" nodes could still give copies to just "low utility" nodes).

Candidate utility functions could be broadly categorized into destination-dependent ("DD") and destination-independent ("DI") functions:

Destination-dependent (DD) Utility: One node may be the best relay for one destination (d 1 ), and another node the best relay for a different destination (d 2 ). In other words, for DD functions:

U i (d 1 ) > U j (d 1 ) but U i (d 2 ) < U j (d 2 ), d 1 = d 2 .
(

) 1
Examples of DD utility functions could be those based on age-of-last-encounter for a given destination [START_REF] Dubois-Ferriere | Age matters: efficient route discovery in mobile ad hoc networks using encounter ages[END_REF]2], social relation with a given destination [START_REF] Musolesi | A community based mobility model for ad hoc network research[END_REF], etc. Destinationdependent utility functions impose a larger overhead on nodes, as in essence they need to maintain an entry for every other node in the network. To reduce this overhead caching techniques could be used (e.g. storing only the m highest utility values).

Destination-independent (DI) Utility: The "utility" of a given node is independent of any destination; instead, it depends on some special characteristic(s) this node has. This implies that one node may be the best relay for most or all destinations. In other words, for DI functions it holds in general that:

U i (d 1 ) ≥ U j (d 1 ) ⇒ U i (d) ≥ U j (d),
for most or all j, d.

(

Examples of nodes which are highly preferable as relays for any destination would be nodes with high and frequent mobility (e.g. vehicles), nodes with many "friends" (e.g. hubs in scale-free networks), or nodes with higher resources (e.g. a "message ferry" [START_REF] Jones | Routing strategies for delay-tolerant networks[END_REF]). DI utility functions have a smaller overhead than DD functions as they require each node to maintain only a single utility value each. Yet, DI functions also imply that the "better" nodes might have to bear a higher forwarding overhead than others. This might result in poorer load-balancing and utilization of the total network capacity, and/or faster battery drainage of a few nodes.

We now turn our attention to specific replication algorithms, some using DD and others DI utility functions. Note that it is possible to define hybrid algorithms also that take into account both the general fitness of a node as well as destination-specific information when making a forwarding decision. Due to space limitations, we defer an investigation of such hybrid functions for future work. All algorithms hereafter are variations of the basic utility-based replication scheme described in Def. 2.2.

Last-Seen-First (LSF) Spraying

The basic idea is to choose as relays nodes that have seen the destination most recently. Thus, LSF is an example of a destination-dependent utility function.

Definition 2.3 (LSF Spraying) Each node i maintains a timer τ i (j) for every other node j in the network, which records the time elapsed since the two nodes last encountered each other as follows: initially set τ i (i) = 0 and τ i (j) = ∞, ∀i, j; if i encounters j, set τ i (j) = τ j (i) = 0; otherwise increase each τ i (j) at every time unit. Finally U i (j) = 1 1+τi(j) .

The basic idea of using age-of-last-encounter timers has been introduced to advance a single message copy towards its destination in a connected mobile network, using gradientbased routing [START_REF] Dubois-Ferriere | Age matters: efficient route discovery in mobile ad hoc networks using encounter ages[END_REF]. Rather than starting with a random set of relays and use age-of-lastencounter to find better and better ones as in [START_REF] Dubois-Ferriere | Age matters: efficient route discovery in mobile ad hoc networks using encounter ages[END_REF]3], LSF tries to choose a good set of relay nodes from the beginning, using age of last encounter to identify nodes that often see or recently saw the destination.

Most-Mobile-First (MMF) Spraying

This algorithm uses a destination-independent (DI) utility criterion. It assumes that some nodes are more "mobile" than others. This scheme would work well, for example, when the majority of nodes participating in the ad hoc network are pedestrians moving within a local area, while a few nodes are vehicles (e.g. buses, taxis, etc.) that tend to visit larger areas and with higher speeds (and thus have a higher chance of meeting new nodes). For now, we'll assume that each of these nodes carries a label that states the type of the node, e.g. "BUS","TAXI", "PEDESTRIAN", "BASE STATION". A similar label assignment is performed in [START_REF] Hui | How small labels create big improvements[END_REF] to assign labels based on affiliation. Although, in some scenarios, it wouldn't be too burdensome to manually configure a label (e.g. by setting some software parameter when installing a radio, say, on the top of a bus), in the next section we discuss one way of assigning labels automatically. Definition 2.4 (MMF Spraying) Assume there are m total node labels, LABEL 1 , LABEL 2 , . . . , LABEL m . Each node i is assigned one of the labels, let LABEL(i), and we define the utility of node i as U i (j) = U i = LABEL(i), ∀j. Finally, labels are put in a preference order ( ):

LABEL 1 LABEL 2 • • • LABEL m
This assignment of preference order to labels can be made offline, based on the general mobility statistics and perceived usefulness of different types of nodes. Furthermore, one INRIA could also have different preference orders depending one the type (label) of the destination. For example, nodes of LABEL j may not be good relays in general, but excellent candidates if the destination is also of LABEL j . This would actually bring the scheme somewhere in between DI and DD.

Most-Social-First (MSF) Spraying

In the previous scheme we assume that, somehow, information about the mobility characteristics of a node might be readily available. However, in many scenarios the same wireless device might be carried by a pedestrian, left at the office desk, or lie inside a vehicle at times. Hence, we need a mechanism that could estimate the "degree of mobility" online. What is more, some nodes might encounter more nodes than average not due to mobility, but just because they visit some "hub" locations (e.g. cafeteria) more often, or have more social links than the average node. This implies that a more appropriate metric of the utility of a node might be its sociability rather than its mobility. Definition 2.5 (Sociability) Let us look at a node i during a time interval t n = [(n -1)T, nT ], where T is the duration of the interval. Let us further define the indicator function I ij (t), which shows whether nodes i and j are neighbors at time t (e.g. have performed an "association" with Bluetooth). Finally, let N i (n) denote the set of nodes j such that

N i (n) = {j = i : ∃t ∈ [(n -1)T, nT ] for which I ij (t) = 1}.
Then, we define the sociability S i (n) of node i during the interval t n as

S i (n) = Ni(n) T .
In general, the sociability value of a node will be a function of the time interval during which it is measured. If a node's statistical behavior varies over time, then its sociability index might also change between time intervals. This implies that it might be more appropriate for a node to maintain a running average of its perceived sociability index, rather than just looking at the previous interval. Definition 2.6 (MSF Spraying) Each node i maintains a running average for the "sociability index" Ŝi as follows: for a given time interval t n = [(n -1)T, nT ] (T = sliding window duration) it counts the number of unique node IDs encountered, N i (n) 6 . Then, at the end of window n it updates Ŝi as

Ŝi = (1 -α) Ŝi + α N i (n) T ,
and proceeds to the next interval t n+1 . α is the weight given to the current measurement in the sliding window mechanism. Finally, the utility of node i is given by U i (j) = U i = Ŝi , ∀j. This is another example of a DI utility function.

Choosing the Protocol Parameters

Sliding Window for Sociability Estimation: Setting the sliding window parameters in MSF correctly (window duration T , and α) is not trivial in the general case. Whether or not the running sociability estimate Ŝi will be a useful predictor of future interactions depends on these parameters, the amount of "structure" in the interaction and mobility patterns of the nodes involved, and the desired "horizon" for the prediction. Although it is beyond the scope of this paper to deal with the general case, there are some situations that are easier to handle. For example, if a node's behavior is homogenous over time

E[S i (t n )] = E[S i (T )], ∀n (time-homogeneous).
In the time-homogeneous case, it is not important during which time window ones looks at a node's behavior. A node with a highly social past behavior, will also be a node with a very social future behavior. An example of this could be if all nodes move according to the Random Waypoint model, but different nodes move with different average speeds and/or pause times. A node i with higher speed and shorter pauses than another node j, will meet on average more new nodes in the same amount of time than j, at any time scale 7 .

Real-life mobility, unlike the above example, usually varies over time (e.g. people tend to have different mobility/interaction patterns during different times of the day). Yet, even in these cases, time homogeneity may also emerge given a large enough time horizon. It has been frequently observed that real-life mobility exhibits time-periodicity [START_REF] Hsu | Impact: Investigation of mobile-user patterns across university campuses using wlan trace analysis[END_REF]. Thus, if the duration of such a period is not prohibitive compared to the desired delivery delay, setting the sliding window to this value could produce a quite reliable predictor for different nodes' sociability. On the other hand, if finer granularity is needed (i.e. targeted delays are much smaller than this period), a shorter sliding window should be used, along with a smaller α to filter out situations where, for example, a node might occasionally meet a large number of nodes, but then few nodes for long stretches of time. Finally, maintaining higher moments of a node's past sociability might also help in identifying such pathological situations, and allowing a node to make more informed decisions.

Number of Copies: Another important protocol parameter is the number of copies L to be used. This number has been calculated for Greedy Spraying in a homogeneous network, in order to achieve a desired transmission-vs-delay tradeoff [3]. The same procedure could be modified for the case of MMF spraying. The main idea is that, if there are M total nodes and MMF uses only p percent of them based on their labels, then this is equivalent to a network of pM nodes (some care is needed though, regarding the effect of the other (1p)M nodes in the minimum/optimal delay [3]).

In the case of MSF Spraying, a different approach could be taken, as described by Lemma 2.1.

Lemma 2.1 Assume there are M total nodes in a network moving independently of each other. Let further each node use the MSF algorithm with a threshold sociability value S th = N th T (rule 1), according to Def. 2.5 and 2.6. If each message has a TTL value of T max , and the desired delivery probability for each message is R min , then the number of copies per message L min and sociability threshold must satisfy

1 -1 - N th T max Lmin ≥ R min . (3)
The above lemma is easy to derive by setting the sliding window duration T equal to the TTL value (T max ). Then, the probability that a chosen relay will not find the destination before the TTL expires is 1 -S th , and (1 -S th ) Lmin assuming the L min relays encounter other nodes in the network independently. Although this might not be realistic in practice, it could serve as a useful rule of thumb to either find a useful threshold value given L or the number of copies L min given S th .

In general, the problem of choosing the number of copies and the copy carriers optimally in a heterogeneous network is difficult. In [START_REF] Jindal | Optimizing multi-copy routing schemes for resource constrained intermittently connected mobile networks[END_REF] the authors formulate one version of the problem using dynamic programming and find the optimal (but centralized) solution only for some special cases. Another interesting effort to address such issues from the point of view of reliability borrows some ideas from modern portfolio theory [START_REF] Jain | Using redundancy to cope with failures in a delay tolerant network[END_REF]. Due to space limitations, we intend to address this issue further in future work.

Simulation Results

We have used a custom discrete event-driven simulator to evaluate and compare the performance of the different Utility-based Spraying algorithms against the basic (greedy) replication scheme (i.e. tree-based Spray and Wait [3,[START_REF] Small | Resource and performance tradeoffs in delay-tolerant wireless networks[END_REF]). A simplified version of the slotted CSMA (Carrier-Sense Multiple Access) MAC protocol has been implemented (further details about the simulator can be found in [3]).

We assume that 100 nodes move according to the "Community-based Mobility Model" [START_REF] Spyropoulos | Performance analysis of mobilityassisted routing[END_REF], which is motivated by real mobility traces like [START_REF] Chaintreau | Impact of human mobility on the design of opportunistic forwarding algorithms[END_REF]. In the Community-based model, each node has its own small community (network size = 500 × 500, community size = 50 × 50) inside which it moves preferentially for the majority of time (e.g. the user's department building on a campus). Every now and then it leaves its community (with probability 1p l ), roams around the network for sometime (e.g. going to the cafeteria, library), and then decides to return to its community (with probability 1p r ). Finally, to capture node heterogeneity, each node may have different mobility characteristics (p l , p r ) in addition to different communities (details about the model in [START_REF] Spyropoulos | Performance analysis of mobilityassisted routing[END_REF]). In Fig. 1 we depict the improvement in the delivery delay of greedy Spray and Wait ("SW"), when message replicas are handed over using LSF Spraying only to nodes that have a last-encounter timer value for the destination that is higher than some threshold value U th (i.e. rule 1 is used -threshold values for this scenario were 500 -1000 time units). As can be seen there, taking into account the age of last encounter when spraying the L copies can indeed improve performance. What is also interesting to note here is that, unlike the case where multi-hop forwarding is allowed (e.g. [2,3]), not having transitivity of utility [2] is preferable in this case. This is reasonable. If no further forwarding is allowed (except during the initial tree-based replication phase [START_REF] Small | Resource and performance tradeoffs in delay-tolerant wireless networks[END_REF]), we are only interested in relays that have a good chance of delivering a message themselves.

LSF Spraying

MMF Spraying

Here, we turn our attention to the MMF Spraying scheme. In Fig. 2 we compare the delivery delay of MMF Spraying and Greedy Spraying, in the same scenario as Sec. 3.1 (Scenario 1). We compare two levels of knowledge for the MMF scheme: (i) messages are given only to nodes of type "local" or type "roaming" but never to "static" or "community" (denoted as MMF1), and (ii) now a relay must also have {p l < 0.9 AND p r > 0.15} in addition to label "local" or "roaming" (MMF2). We show plots for both a very sparse network (< 8% of nodes are connected) and a denser one ("flakynet" -around 50% of nodes are connected). As can be seen by these plots, by choosing only nodes that actually have a chance to deliver a message we can get up to 2.5 -3× reduction in delay in this scenario. Greedy spraying wastes many copies by handing them over to community and static nodes.

Intuitively, the larger the amount of node heterogeneity the higher the improvement is expected to be by using "smarter" copy distribution algorithms. To confirm this, in this second scenario we assume only two types of nodes: (i) p% are "roaming" nodes that are useful as message relays and (ii) (1-p)% are "community" nodes that are useless as message carriers, unless the destination lies inside their community (small probability). In Fig. 3 we compare the performance of greedy Spray and Wait and MMF Spraying, which gives copies only to roaming nodes, as the percentage p of roaming nodes decreases.

From this figure, it is evident that the smaller the percentage of useful ("roaming") nodes the higher the delay improvement by using smarter spraying. This is because greedy forwarding makes an increasing number of errors, wasting more and more copies ((1p)L). On the other hand, we see that the achievable improvement peaks at a given value of p and starts becoming smaller again. At this point the number of useful relays is so small (smaller than the number of copies) that the smarter Spraying scheme takes a very long time to find them. captures how probable it is for that relay to encounter the destination in the near future. We have presented a number of different heuristics for the distribution of message copies, and have shown that choosing the relays carefully rather than picking the first few relays encountered [3,[START_REF] Small | Resource and performance tradeoffs in delay-tolerant wireless networks[END_REF][START_REF] Neglia | Optimal delay-power tradeoff in sparse delay tolerant networks: A preliminary study[END_REF], can significantly improve performance in heterogeneous scenarios.

MSF Spraying (Delivery

More sophisticated or hybrid heuristics could be envisioned to improve performance further, and the issue of optimal allocation of message replicas to relays in heterogeneous environments is open. Yet, we believe that this work clearly shows that utility-based replication is a desirable and often necessary routing primitive, when the number of total transmissions needs to be controlled (e.g. energy-constrained environments, credit/price-based systems for self-organized networks, etc.). Alternatively, using utility-based replication rather than greedy one during the initial distribution phase of message replicas could have an improvement on the performance of schemes that allow multi-hop forwarding also [3]. We intend to look further into this last issue in future work.

INRIA 5 2

 5 Utility-based Message Replication for Intermittently Connected Heterogeneous Networks Utility-based Replication

Figure 1 :

 1 Figure 1: Scenario 1: performance improvement of LSF Spraying over greedy Spray and Wait (SW); K =node's transmission range, L = number of copies.

Figure 2 :

 2 Figure 2: Scenario 1: performance improvement of MMF spraying over greedy Spray and Wait (SW), for two different connectivity scenarios (sparse and almost connected); L is the number of copies.

Figure 4 :

 4 Figure 4: Performance comparison of MSF, MMF, and greedy Spray and Wait, as a function of the percentage p of "useful" relay nodes.

In this sense, it is essentially an extension to the

2-hop scheme proposed by Grossglauser et. al, where at most 1 relay is used[START_REF] Grossglauser | Mobility increases the capacity of ad hoc wireless networks[END_REF].2 Due to street limits, traffic considerations, etc. drivers do not in general make decisions independently; yet, to the extent that two drivers will decide for example whether to take a turn or not in the next cross-street, this decision will be largely independent.RR n 6129

We assume that a message ID vector exchange similar to that performed in epidemic routing occurs[START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF].

This is not necessarily true; If snail nodes move less frequently around the network than normal ones, it may be the case that they are also encountered by other nodes less frequently; in that case, pL would just be an upper bound.RR n 6129

A more generic approach would be to make l(c), the number of tokens forwarded, a function of the relay's utility also: lc = f (c, U j (d)). This would increase the flexibility but also the complexity of the distribution algorithm. Due to space limitations, we choose not to address this issue here.RR n

If T is not too large, the overhead of maintaining a list of unique node IDs and look-up time when a new node is found is not significant.RR n 6129

We assume here that no encounters are missed. In reality, if a node moves very fast, it might not discover some contact opportunities which are short-lived, due to the workings of the neighbor discovery mechanism[START_REF] Chaintreau | Impact of human mobility on the design of opportunistic forwarding algorithms[END_REF].INRIA

RR n 6129

We have used L = 10 copies per message for all schemes, Tx range K = 30, the sliding window for MSF is 1000 time units, and α = 0.8; the sociability threshold was chosen manually trying different values.INRIA

MMF Spraying (Scenario 2)

MSF Spraying

In this last scenario we'll examine the more practical scheme, MSF Spraying. Unlike the MMF scheme which uses preprocessed information (LABELs) to identify globaly useful relays, MSF tries to estimate this utility online by observing the type and number of encounters the node gets involved into. Fig. 4 compares the delivery delay for a scenario similar to that of Fig. 3, where only a percentage p of nodes are useful as message relays. It compares the performance of MSF to Greedy Spraying, as well as MMF spraying (which knows beforehand which are the useful nodes) 8 . As can be seen there, both MSF and MMF improve the performance of Greedy spraying. What is more, MSF can approximate the performance of MMF without the fore-knowledge that the latter requires. (As a final note, although we do not have space to depict plots for the behavior of the running sociability estimates, we have observed that it manages to identify the "good" nodes after only a few windows.)

Conclusion

In this work, we have looked into the issue of efficient mobility-assisted or store-carryand-forward routing. Specifically, we have explored the issue of allocating a fixed budget of message replicas to a number of candidate relays, according to a utility function that


M J Swift

K V Horoshenkov

P Leclaire

D C Hothersall

K Fujiwara

H Torihama

On the effect of the bending vibration on the acoustic properties of thin poroelastic plates

An experimental study on the effect of bending vibration on the acoustic properties of thin porous plates is presented. Poroelastic plates are tested in a large impedance tube in the lower frequency range. It is shown that bending vibration can be excited by the incident sound and detected by measuring the acoustic impedance of a plate. This effect together with the effect of the flow resistivity on the values of the acoustic impedance of the plate are shown. The data from the large and small impedance tubes illustrate how these effects are reduced with the reduced size of the plate.

INTRODUCTION

There are a number of studies which have been carried out on the vibration of plates and structural damping. These have primarily been to investigate behavior of plates which are made from nonporous materials. The results of these studies are widely reported in the literature and a comprehensive summary of them can be found in Ref. 1. On the other hand, some studies have been carried out into the effect of the solid movement on the surface impedance of porous layers.

As an example, particular works by Bardot et al. [START_REF] Bardot | Frame decoupling at low frequency in thin porous layers saturated by air[END_REF] and Allard [START_REF] Allard | Propagation of Sound in Porous Media: Modelling Sound Absorbing Materials ͑Elsevier[END_REF] are concerned with the coupling effect between Biot's slow and fast waves excited in a layer of highly porous fibrous materials with an infinite lateral extend bonded by an impermeable rigid wall. The low rigidity in the thickness of these materials allows compressions and expansions of the porous layer associated with the passage of the airborne acoustic wave. In such a case, the rigid frame approximation where the solid is immobile is no longer valid.

In this article, a coupling between the solid motion and the fluid motion is also studied, but this coupling is of a different nature. Here, the solid movements are eventually taken into account but these correspond to the structural vibration of thin rectangular porous plates. [START_REF] Theodorakopoulos | Flexural vibrations of poroelastic plates[END_REF] The same assumption is made as in the standard theory of plates ͑nonporous͒ that only the in-plane stresses and deformations are considered while the deformations in the thickness are neglected. This assumption is often written in the standard plate theory as 33 ϭ0 where 33 is the component of the stress tensor normal to the middle surface. As a consequence, the plate is allowed to bend, but its thickness remains constant. Two conditions are required to make this assumption: the plate must be fairly thin and its Young's modulus must be much greater than that of the fluid ͑air in our case͒. These requirements are met by our samples.

In this configuration, the triple combination of the bending vibration, the presence of an air gap, and the well-known visco-thermal interaction in the pores are investigated experi-mentally. Their influence on the surface impedance and the absorption coefficient is studied. It is shown that the absorption coefficient of a thin poroelastic plate can be considerably increased at particular frequencies so that the low frequency acoustic performance can be improved.

I. EXPERIMENTAL PROCEDURE

An investigation has been carried out on three thin porous plates with varying values of flow resistivity, density, and Young's modulus. Two plates have been manufactured from foam granulates which are recovered from automotive waste. The other plate has been manufactured from flint particles consolidated with rubber-epoxy binder ͑Coustone™͒. The dimensions of the plates were 0.5 mϫ0.5 mϫ10 mm. Other material properties of the plates are listed in Table I.

The measurements have been carried out in the large impedance tube in the Kyushu Institute of Design and in a smaller Bruel and Kjaer 4206 impedance tube available in the University of Bradford. The larger impedance tube allows testing of 0.5 mϫ0.5 m samples of acoustic materials in the frequency range of 50-300 Hz ͑see Fig. 1͒.

The plates have been tested with 40-mm and 80-mm air gaps, depending on the material properties. They have been clamped in the larger impedance tube along their edges using a strong wooden frame and the edges have been carefully sealed ͑see Fig. 1͒. Care was taken to ensure good clamping conditions so that not to distort the panel from its ''natural'' resting position. All gaps between the edges of the frame and the wall of the chamber were blocked using sealing putty. Because of the clamping device, the effective area of the plate exposed to sound was reduced to 0.48 mϫ0.48 m.

It is assumed that the resonance frequencies for bending vibration in smaller samples tested in the smaller tube are considerably higher. The results from the normal incidence impedance and absorption from the large and small impedance tubes have been compared. From this comparison the effect of structural vibration on the visco-thermal absorption in the material is estimated. Some nonacoustic properties of the tested materials have been measured. These are the bulk density, Young's modulus, porosity, and flow resistivity. The flow resistivity and porosity have been measured using standard techniques of air flow tube and the method of water saturation under vacuum, respectively. The Young's modulus has been measured using rectangular strips of the material in a standard cantilever setup. The values of these parameters are compiled in Table I.

II. RESULTS AND DISCUSSION

The results for the real and imaginary parts of the surface acoustic impedance from the measurements in the large and small impedance tubes are compared in Figs. 234. The absorption coefficient as a function of frequency is shown in Figs. 567.

These figures seem to confirm that the vibration of certain modes in a clamped, porous, elastic plate can be generated by airborne sound in the low frequency range. These modes can be detected as resonances in the acoustic surface impedance ͑see Figs. 234. The frequencies corresponding to the bending vibration modes detected from the measurements are listed in Table I. These frequencies are reasonably close to the theoretical values provided by the classical theory of plates. [START_REF] Leissa | Vibration of Plates ͑Acoustical Society of America[END_REF] At these frequencies the values of the acoustic surface impedance can differ considerably from those measured in the small impedance tube, in which case the amplitude of vibration is considered to be negligibly small ͑see Figs. 234. In the vicinity of these resonances the absolute value of the imaginary part of the impedance can have a minimum, at which the relaxation processes are par-ticularly pronounced. In this region the absorption in the porous material can be noticeably improved ͑see Figs. 567.

In the case of a porous plate which is manufactured from consolidated foam G10 it is possible to observe two bending modes at frequencies 76.25 Hz and 150 Hz on the curve for the impedance ͑see Fig. 2͒. The frequencies of the modes correspond to the minima in the absorption spectrum ͑see Fig. 5͒. The minima in the impedance spectrum for this material are observed at 97.5 Hz and 168.75 Hz. At these frequencies the absorption is considerably improved in comparison with the data from the small impedance tube ͑see Fig. 5͒.

There is a resonance in the impedance spectrum corresponding to a mode which is clearly observed at 86.25 Hz in the case of a porous plate which is manufactured from consolidated foam YB10 ͑Fig. 3͒. There is a local maximum in the absorption spectrum at 76.25 Hz ͑Fig. 6͒.

In the case of the Coustone plate ͑C10͒ the resonance in the impedance spectrum is observed at 96.25 Hz ͑see Fig. 4͒. There is a local minimum in the spectrum immediately above this frequency, which results in some increase in the absorption spectrum at 103.75 Hz.

A precise quantitative analysis of the problem described in this article is still very difficult at the moment because of the lack of theoretical results. Nevertheless, a few remarks can be made from this study and some conclusions can be drawn with a reasonably good degree of confidence:

͑1͒ The acoustical properties of large acoustic panels measured in a large impedance tube clearly exhibit resonances. These are associated with bending structural vibra- tion of a finite-size, porous plate which has a fairly small thickness and the Young's modulus higher than that of air. The resonance frequencies seem to be close to predictions given by the standard theory of plates. These results show a noticeable enhancement of the absorption coefficient at some frequencies in the low frequency domain where the acoustic absorption is generally low. A physical interpretation of the resonances and of the mechanisms of the enhancement of the absorption coefficient is that a fraction of the acoustic energy carried by the incident sound wave is converted into the vibrational energy used to move the plate. This energy is then partly re-radiated at particular frequencies and partly dissipated in the frame. ͑2͒ It is known that the presence of an air gap with properly chosen dimensions can enhance the low frequency acoustic performances. [START_REF] Allard | Propagation of Sound in Porous Media: Modelling Sound Absorbing Materials ͑Elsevier[END_REF] It is also known that while increasing the absorption coefficient at some frequency areas, an air gap will decrease it at some others. [START_REF] Allard | Propagation of Sound in Porous Media: Modelling Sound Absorbing Materials ͑Elsevier[END_REF] Nevertheless, the combination of an air gap with the structural vibrations could be very useful. Depending on its thickness, the presence of an air gap is thought to favor or hinder the observation of the structural vibration, but not to change the resonance frequencies which are solely dependent upon the plate mechanical properties, the clamping conditions, and the microstructural parameters ͑porosity, tortuosity and flow resistivity͒. ͑3͒ The comparison of the damping of the resonances in the three examples investigated in this study shows that peaks in Fig. 5 seem to be smoother than those shown in Figs. 6 and7. It is thought that particular values of the flow resistivity exist that will result in a maximum loss of energy by viscous frictions at certain frequencies of vibrations of the plate structures. In the optimum case, the phase shift between the solid and fluid motions is maximum and the viscous losses are maximum. This will result in a very smooth resonance peak.

͑4͒ The visco-thermal interactions in porous media have been and are still the subject of active research ͑see Refs. 3,5͒. At low frequencies, the compressibility of air in the pores is isothermal and the absorption is dominated by the viscous frictions. At higher frequencies the compressibility is adiabatic and the viscous friction is also predominant. The thermal effects are particularly pronounced in the medium frequency range. Although they have less influence on the absorption than the viscous friction, their effect is not negligible. The combination of the visco-thermal effects and the effects described in ͑1͒-͑3͒ can provide an improved absorption spectrum in the whole frequency range.

III. CONCLUSIONS

An experimental study has been carried out to determine the effect of bending vibration on the acoustic properties of a clamped, porous, elastic plate. It has been shown that bending vibration of certain modes can be excited by incident sound in the plate and affect its acoustic impedance. The corresponding frequencies can be estimated a using a standard theory for clamped porous plates. [START_REF] Leissa | Vibration of Plates ͑Acoustical Society of America[END_REF] The measured values of the normal incidence plane wave absorption coefficient suggest that, in the vicinity of these frequencies, the absorption can be significantly improved as a result of relaxation processes which develop in the moving porous frame. In this way, porous plates with improved low frequency absorption can be designed. The experimental data also suggest that the acoustic impedance is more affected in porous plates with higher values of the flow resistivity as a result from a better coupling between airborne sound and bending vibration in the elastic frame.

FIG. 3 .

 3 FIG. 3. The real ͑a͒ and imaginary ͑b͒ parts of the normalized surface impedance of a 10-mm rectangular plate made of consolidated foam YB10. 80-mm air gap.

FIG. 5 .

 5 FIG. 5. The normal incidence absorption coefficient of a 10-mm-thick rectangular plate made from consolidated foam G10. 80-mm air gap.

TABLE I .

 I Summary table of material properties.

		YB10	G10	C10
	Material	Recycled	Recycled	Consolidated
		foam	foam	flint
	Plate thickness ͑m͒	0.010	0.010	0.010
	Density ͑kg/m 3 ͒	414	390	1464
	Young's modulus ͑Pa͒	2.29ϫ10 7	1.57ϫ10 7	6.20ϫ10 7
	Porosity	0.57	0.44	0.40
	Flow resistivity, Pa s m Ϫ2	190367	743200	31520
	Observed resonance	86.25	76.25	96.25
	frequency, Hz
	Frequency of bending	89.02 ͑3͒	82.54 ͑3͒	94.35 ͑3͒
	wave ͑mode͒, Hz

FIG. 1. Experimental setup. FIG. 2. The real ͑a͒ and imaginary ͑b͒ parts of the normalized surface impedance of a 10-mm-thick rectangular plate made from consolidated foam G10. 80-mm air gap.

ACKNOWLEDGMENTS

The authors gratefully acknowledge the support of the Engineering and Physical Sciences Research Council ͑Grant No. GR/L54905͒ and the contribution from the British Council in Tokyo toward the travel and expenses connected to the work which was carried out in Kyushu Institute of Design. The authors are also very grateful for the support given by Eric Chadwick and CEP Acoustics Limited, who manufactured and supplied samples of Coustone material.


Philippe Leclaire

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.

Book review

Fundamentals of Physical Acoustics D. T. Blackstock; Wiley & Sons Ltd, New York, 2000, 541pages, ISBN 0-471-31979 This book is an excellent piece of work. The text is extremely clear and goes a long way towards meeting the declared pedagogical target. The author has written a comprehensive text. The proportions of equations and explanations/interpretations are particularly well balanced. Throughout the book, the context and the validity domain for any equation derived are clearly stated. No doubt this book will be of invaluable help for students, academics and engineers. The structure of the book has a peculiar recursive pattern. Several topics are treated in each chapter, but these topics are the main subjects themselves of subsequent chapters (which can sometimes be found after several intermediate chapters). Although this means that the author returns to a subject more than once, no impression of redundancy comes out from the reading. This is due to a careful choice of the examples and the different angles from which the problems are viewed. The way in which the book is structured has a beneficial effect and undoubtedly participates in enhancing the pedagogical content. Essentially, each subject is treated in detail several times, thus giving the reader the opportunity to assimilate the concepts while still progressing in their discovery. Moreover the presentation and the layout of the book are excellent.

The fundamental concepts of Acoustics are introduced in Chapters 1and 2. Chapter 1 is fairly qualitative and presents the main aspects of Physical Acoustics with the minimum of Mathematics. The reader is not 'drowned' by equations, in being introduced to the basic principles that underpin Acoustics. Particularly remarkable, in Chapter 1 , is the excellent description of the Lagrange and Euler systems of coordinates. The examples given help to visualise the difference between the two systems. Also, the complex radiation impedance is described very well. The numerous footnotes in the book are helpful and pertinent. They enlarge the scope and provide useful information or explanations without interfering with the developments. Chapter 2 revisits Chapter 1in more detail. As mentioned by the author in the forewords, the role and position of Chapter 2 have a pedagogical motivation. Various extensions of the basic linear equation of wave propagation are presented. These extensions are necessary for treating the main situations that can be encountered in Engineering Acoustics. This idea is excellent and is beneficial to the clarity and comprehension. Although more mathematics is involved, the pedagogical skill of the author makes it agreeable to read.

1 Chapters 3-5 introduce the reader to problems of wave reflection and transmission at the interface between two fluids. A sudden change in cross-section area in a duct has the same effect on the transmission loss as a variation in impedance. The mathematical formulation of this problem is similar to that of waves at interfaces and the problem of wave propagation in ducts with variations in cross-section is also studied in Chapters 3 and 4. In Chapter 3, the normal incidence reflection and transmission coefficients for the pressure and for the sound power are derived in the time domain. The introduction of complex impedance is delayed and the expressions obtained are simpler. Therefore, a better understanding of the phenomena is gained. In addition, the reflection and transmission for waves of arbitrary waveform can be studied more easily. Harmonic time dependence is studied in Chapter 4 where complex reflection and transmission coefficients are considered. Chapter 4 is important as many Engineering applications involve a study in the frequency domain. Although useful problems are investigated, this reader feels that a bit more could perhaps have been written to introduce the standing waves since they are rather important in acoustics and vibration theory. Chapter 5 is concerned with transmission at oblique incidence and the refraction law is established. This chapter represents a good introduction to the ray theory presented in Chapter 8.

Chapter 6 is an introduction to vibration theory, normal modes, waveguides and dispersion. The description of the phenomena is very good. In particular, the description of the relationship between free and forced vibrations and the associated resonance frequencies is excellent. The phase velocity, the group velocity and wave dispersion are general concepts, not restricted to waveguides. These could perhaps have been introduced more generally to present the opportunity to discuss phenomena related to dispersion, such as wave packets and group velocity, the frequency content of a signal and the effect of dispersion on temporal waveforms, to a greater extent.

Chapters 7 and 8 are concerned with applications of a particular differential equation established in the linear approximation: the Webster horn equation. Although these two chapters deal with totally different subjects, propagation in ducts with varying cross section and vertical propagation in media with a (vertical) gradient of the properties are governed by the same differential equation. A general method for integrating this equation is presented and applied to both cases. When the propagation is not in the direction of the gradient, a differential form of Snell's law presented in Chapter 5 is used. This law is the origin of the ray theory presented in the second part of Chapter 8.

Chapter 9 reviews the main mechanisms of wave attenuation in fluids. This chapter is extremely well structured and is possibly the clearest. The diagram on page 299 is excellent. It gives a global view of the problem, which is excellent for serving the pedagogical purpose (it should always be like that in any book). It shows how the equations developed in the first chapters relate to each other and the origin of the attenuation coefficient and the velocity. This diagram is very general and it is believed that it could have been introduced even earlier. The relationship between the different contributions to wave attenuation and the validity of their superposition is also well explained (see footnote). The summary at the end of the chapter will be particularly useful for scientists.

Chapters 10 and 11 deal with spherical waves, cylindrical waves, sound radiation and circular membranes. By nature, these subjects are mathematical and it is necessary to introduce an array of spherical and cylindrical functions. All the appendices are very useful. However, perhaps there is an imbalance or injustice in the fact that an entire appendix is dedicated to the solution of Legendre's equation while none is devoted to Bessel, Neuman or Hankel functions. Is it the fact that Legendre polynomials appear in the general solution for spherical waves that influenced the author's decision to write appendix D?

The last chapters correspond to applications of previous chapters. Waveguides are important for example in flow duct acoustics or in building acoustics in general. Chapter 12 is a development of this subject, which is introduced in Chapter 6. The previous chapter on waves in cylindrical co-ordinates permits the study of cylindrical waves in circular waveguides or between infinite parallel planes, which was not possible in Chapter 6. As an application of the monopole source radiator, Chapter 13 introduces the Rayleigh integral (almost already there in Chapter 10) and applies it to the sound radiation from a piston. Starting from the study of a ring piston, the full disk piston is studied in the baffled case. The near field, the far field and the directivity are described. The Rayleigh distance is also introduced and physical interpretations are given. The fluid loading is accounted for through the calculation of the radiation impedance at the surface of the piston. Other cases are studied such as a nonharmonic translation velocity or a nonuniform piston for which the velocity depends on the position on the surface. The non baffled case is not treated but evoked in the introduction. Chapter 14 is concerned with diffraction. The introductory description of the phenomenon is particularly good. The Helmholtz-Kirchhoff integral theorem is presented and applied to basic sample problems. The chapter ends with Babinet's principle on the complementarity of diffracting objects. Finally, Chapter 15 studies the radiation of arrays of equally spaced point sources in line configuration and the radiation pattern as a function of the wavenumber and separation distance. Again, the explanations are clear and pedagogically very good. In the limit of infinite number of sources and when the separation distance tends to zero, it is shown in an elegant way, that the same expression for the directivity function is obtained as that obtained from the integration over a line source. This integration is similar to the calculation done for a circular piston in Chapter 13.

This comprehensive and pedagogically-sound book is a rigorous introduction to physical acoustics. Well suited for graduate students, it should be very useful also to academics and engineers.

P. Leclaire Department of Engineering

University of Hull, UK


Arthur Charpentier

AND Arthur David

Romuald Elie

Optimal Claiming Strategies in Bonus Malus Systems and Implied Markov Chains

come   L'archive ouverte pluridisciplinaire

Introduction

Bonus-Malus systems are well established tools used in motor insurance pricing based on past experience of drivers. A Bonus -a premium discount (with some lower bound) -is guaranteed by the policy when the driver reports no claims during a predetermined period of time. A Malus -an additional charge to the premium (with some upper bound) -is required when claims are reported. The obvious purpose of this mechanism is to penalize the bad (or unlucky) drivers and to provide incentives for drivers to try to reduce their claims frequency, as discussed in [START_REF] Franckx | Théorie du bonus[END_REF] or [START_REF] Hey | No Claim Bonus[END_REF]. From a mathematical perspective, standard Bonus-Malus systems are convenient because they might be modeled using Markov chains (see [START_REF] Lemaire | A comparative analysis of 30 bonus-malus systems[END_REF] and [START_REF] Lemaire | Bonus-Malus Systems in Automobile Insurance[END_REF] for a description of various existing systems). Markov chains properties (and associated invariant measures) can be used to describe the long term equilibrium of the system. But, as a by-product, this mechanism also generates some hunger for bonuses (as described in [START_REF] Lemaire | La soif du bonus[END_REF]): drivers might overtake small claims and not report them to their insurance companies, in order to obtain a reduced premium (and avoid also the additional charge). In this paper, we exhibit the optimal reporting strategy and address the problem of updating the Markov chain transition probability of class levels, in order to take into account the probability of not reporting a claim.

1.1. Discrete Bonus Malus System. The optimal claiming strategy for insured drivers was already addressed in [START_REF] Zachs | Claiming Strategies and Premium Levels for Bonus Malus Systems[END_REF], where a continuous time version of k-class bonus malus systems was considered: drivers are switched to a lower class if no claim were filed during a period T (that might depend on the previous class), while whenever a claim is filed, the insured is immediately switched to a higher level (as in [START_REF] De Pril | Optimal claim decisions for a bonus-malus system: A continuous approach[END_REF]). Here, we want to integrate this realistic feature in the more standard approach based on Markov chains modeling on a finite number of classes, discussed e.g. in [START_REF] Lemaire | Automobile Insurance: Actuarial Models[END_REF]. Namely, we intend to incorporate the optimal strategy for drivers not to report a loss whenever the considered amount is too small. Nevertheless, in a discrete model, if the transition is based on the number of claims, and not the occurrence (or not) of claims within a given period (usually one year), modeling hunger for bonus is much more complex. Intuitively, the optimal decision to report and claim a loss is not the same if the policy renewal (and associated premium level update) is either in 360 days, or only in 5 days. Moreover, insured drivers may (and often should) choose to regroup several minor claims and declare them as a large one. In order to avoid those issues and stick to a simple and easily interpretable model, we assume that only one claim per year might occur.

Charpentier received financial support from NSERC and ACTINFO chair. Elie received financial support from ACTINFO chair. Corresponding author is arthur.charpentier@univ-rennes1.fr.

1.2. Advantages of a Discrete Bonus Malus System. The continuous-time model described in [START_REF] Zachs | Claiming Strategies and Premium Levels for Bonus Malus Systems[END_REF] has nice mathematical properties, but on the other hand discrete-time Bonus Malus systems are interesting since they are easily interpretable, and can naturally be formalized via Markov chains. In order to illustrate this our model, let consider a benchmark very simple Bonus-Malus system, with 3 classes, similar to the one discussed in Section 6 of [START_REF] Zachs | Claiming Strategies and Premium Levels for Bonus Malus Systems[END_REF]. A different premium P i is associated to each class i = 1, 2, 3. If no claim occurs during one year, a driver is upgraded from class i to class i -1, as long as i ≥ 2. In case of claim report, the driver is downgraded from class i to class i + 1, as long as i ≤ 2. See Table 1 for a description of that scheme. class premium claim no claim 3 1. Transition rules for the 3 classe Bonus Malus system. Suppose that claims occurrence is driven by an homogeneous Poisson process, with intensity λ, given some initial class at time t = 0, as in standard actuarial models. Then the trajectory of classes for the driver can be described by a discrete Markov process. If p := e -λ denote the probability to have no claim over a year, the transition probability matrix of the Markov chain is given by

P 3 3 2 2 P 2 3 1 1 P 1 2 1 Table
M =   p 1 -p 0 p 0 1 -p 0 p 1 -p  
for the classes 1, 2 and 3 (in that order).

Based on this transition probability matrix, a quantitative figure of interest is the corresponding stationary distribution, describing the repartition of drivers within the classes in a stationary regime. Given this stationary distribution, one can then compute the corresponding average premium in the (long term) stationary state, see e.g. [START_REF] Lemaire | Bonus-Malus Systems in Automobile Insurance[END_REF] and related studies. But, unfortunately, this (standard) study of Bonus Malus schemes is almost always based on the unrealistic assumption that all car accidents are claimed to the insurance company. However, it might not be optimal for a client to claim all losses.

For instance, suppose that an insured in class 2 suffers a loss of level . Then,

• if the loss is claimed, next year premium will be P 3 as he will downgrade from class 2 to class 3; • if the loss is not claimed, he will loose and next year premium will be P 1 , as he will upgrade from class 2 to class 1.

So a basic short term economic reasoning indicates here that it is rational to not to claim a loss as soon as P 3 > + P 1 , i.e. < P 3 -P 1 . It is common knowledge that this type of reasoning is even suggested by the insurance company, as soon as a driver intends to report a reasonable claim. It indeed happened recently to one of the authors of the paper.

1.3.

A simplistic version of the Optimal Claiming Strategy. Any less short-term minded driver should take into account today's implications of a class level upgrade or downgrade on all the future premiums. Namely, a slightly more complex decision process can be obtained by considering not only next year premium, but premium over all the following years. Consider for example the same system as the one described above. Suppose that a driver suffers a claim of level while he was in class s at time t. Then,

• if he claims the loss, he will get a reimbursement as well as a some premium downgrading, making him start at time t + 1 in a class (s + 1);

• if he does not claim the loss, he will not get a reimbursement (so he will face a loss ), but he will not get the previous downgrading and hereby will start at time t + 1 from the class of level (s -1).

A naive approach may hence conclude that it is rational not to claim the loss whenever

≤ ∞ h=1 (1 + r) -h P s+1+h - ∞ h=1 (1 + r) -h P s-1+h ,
where r denotes the economic discount factor of the agent. Observe that we used here a slight abuse of notation, by denoting P k := P c, for k larger than the highest class level c as well as P k := P c , for k smaller than the smallest class level c.

For instance, consider the Bonus Malus system described in Table 1, and focus once again on a driver currently in class 2. Applying this reasoning, the discounted value of future premia when claiming a loss is

V (3) = P 3 1 + r + P 2 (1 + r) 2 + P 1 (1 + r) 3 + P 1 (1 + r) 4 + • • • ,
whereas the discounted value of future premia when not reporting the claim is

V (1) = P 1 1 + r + P 1 (1 + r) 2 + P 1 (1 + r) 3 + P 1 (1 + r) 4 + • • • .
Following this reasoning, it is rational not to claim loss as soon as

≤ d 2 := V (3) -V (1) = P 3 -P 1 1 + r + P 2 -P 1 (1 + r) 2 ,
where d 2 interprets as an implied deductible, as in [START_REF] Braun | Modeling the 'pseudo-deductible' in insurance claims decisions[END_REF] and [START_REF] Chappell | Optimal, near-optimal and rule-of-thumb claiming rules for a protected bonus vehicle insurance policy[END_REF].

But this approach is obviously too simple (or naively over-optimistic) since the driver assumes a deterministic trajectory for future bonus malus classes and related premia. He does not take into account the occurrence of new claims in the following years.

1.4. Agenda. Alternatively, a more natural and rational decision would be not to declare the claim whenever in class s, as soon as

(1) ≤ 1 1 + r (V t+1 (s + 1) -V t+1 (s)) ,
where the function V t+1 (k) represents the expected value of all future discounted claims and premia for the driver, whenever he starts from class k at time t + 1. This function V must integrate the occurrence of claims in the future, as well as the corresponding probabilistic evolution of the classlevel Markov Chain (S t+h ) h≥1 given S t , considering that the driver sticks to the optimal reporting strategy designed by [START_REF] Braun | Modeling the 'pseudo-deductible' in insurance claims decisions[END_REF].

The main purpose of this paper is to identify the optimal strategy for reporting losses. Applying this optimal reporting strategy, we observe that the corresponding level class process (S t ) t remains a Markov chain, with modified transition probabilities. In Section 2, we formalize the problem of interest and describe the related Markov chains. In Section 3, we derive and characterize the optimal reporting strategy of the driver and provide a simple algorithmic routine to approximate it. The algorithm will in particular be tested in a 5-state Spanish Bonus Malus scheme, see Section 4. Extensions including the addition of deductibles, as well as the consideration of heterogeneous or risk adverse drivers are presented in Section 5.

Problem formulation

2.1. Bonus Malus based on loss occured. Classical Bonus Malus transition probabilities are usually computed under the assumption that every claim is reported, as in e.g. [START_REF] Lemaire | Bonus-Malus Systems in Automobile Insurance[END_REF]. This gives rise to a Markov Chain dynamics for the class level of any driver. For example, a standard model for claims occurrence is the Poisson process. With an homogeneous Poisson process, with intensity λ, the Markov process is also homogenous.

Consider for instance the classical 3-classe Bonus Malus scheme described in Section 1.2 above. Recall that, in such system,a driver is upgraded whenever to claim occurs and is downgraded at the arrival of any claim, see Table 1. Whenever all losses are claimed to the insurance company, the level-class Markov chain associated to such Bonus-Malus system has the following transition matrix

M =   p 1 -p 0 p 0 1 -p 0 p 1 -p   ,
where p denotes the probability to have no claim on a one year period. Observe that the probability that a loss occurs does not depend on the class level s. This classical feature is due to the no-memory property of the Poisson process.

In a stationary regime, the invariant probability measure µ characterizing the repartition of the drivers within the 3 classes is given by

µ := 1 κ 2 + κ + 1 (κ 2 ; κ; 1) T , where κ := p 1 -p .
It can be visualized on Figure 1 for several values of p, associated to different level of claim frequency λ in a Poisson model. In addition, we deduce the average premium in the stationary regime, which is given by

P := κ 2 P 1 + κP 2 + P 3 κ 2 + κ + 1 .
In the numerical illustration, this asymptotic premium is used in order to enforce actuarial equilibrium between the driver and the insurer in the sense that

P = (1 -p) • E(L),
where L denotes the (random) loss amount of a claim.

2.2. Impact of claim reporting strategies. Observe that the previous stationary distribution of drivers within classes only depends on the frequency of the claims, via the probability parameter p.

In particular, it is not connected to the levels of the premiums (P k ) k or the possible severity of the claims. This feature relies on the fact that we unfortunately did not take into account the economic behavior of drivers, and in particular the fact that they may choose not to report small claims. They shall do this whenever the gain from reporting a claim does not compensate the impact of the class level downgrade on the future premia.

A loss reporting strategy for a driver is hereby given by a collection of thresholds d s , associated to any class s. Let A denote the collection of such strategies, i.e.

A := {(d s ) s∈S ,
π d s := P[L > d s ], s ∈ S , d ∈ A ,
where L is the level of the random loss. Focusing again on the classical 3-classes Bonus Malus scheme described above, the transition matrix of the class level Markov chain is modified in the following way

M d =   p + (1 -p)(1 -π d 1 ) (1 -p)π d 1 0 p + (1 -p)(1 -π d 2 ) 0 (1 -p)π d 2 0 p + (1 -p)(1 -π d 3 ) (1 -p)π d 3   , d ∈ A .
In order to interpret this matrix, focus for the example on the first entry of the matrix M d . The probability to remain in class 1 for a driver in class 1, is the sum of two disjoint probabilities: the one of not facing a claim equal to p, and the one of having a loss and not reporting it, i.e. (1 -p)(1 -π d 1 ).

Since the transition probabilities of the Markov Chain are affected, the stationary distribution of driver within class will automatically also be modified. For instance, in the 3 classes Bonus Malus scheme of interest, we obtain the corresponding stationnary repartition within classes, for any given d ∈ A:

µ d ∝ κ + (1 -π d 2 ); π d 1 ; π d 1 π d 2 κ + (1 -π d 3 ) T .
The reporting strategy of agents of course has a huge impact on the business model of the insurer as the new average premium rewrites

P d = K d (κ + (1 -π d 2 ))P 1 + π d 1 P 2 + π d 1 π d 2 κ + (1 -π d 3 ) P 3 , d ∈ A ,
where the renormalizing constant K d is given by

K d := κ + (1 -π d 3 ) (κ + (1 -π d 2 + π d 1 ))(κ + (1 -π d 3 )) + π d 1 π d 2 , d ∈ A .
A numerical application, to illustrate those quantities, is detailed in section 4.

2.3.

Towards an optimal claim reporting strategy. Now that the impact of the claim reporting strategy of the drivers has been clearly established and quantified from the insurer point of view, let's turn to the search of the optimal reporting strategy for drivers.

We assume that all the drivers are rational and risk-neutral. Their objective is to minimize the global cost of the insurance policy, which is characterized by the combination of all premia and non reported losses. These expenses are reported up to a chosen fixed time horizon T , which may be considered to be +∞, in particular if r is large. For ease of presentation, we do not consider here the addition of a deductible payment, but this question will be discussed in Section 5 below.

The discounting rate of the representative driver is denoted by r and we recall that the class-level Markov chain associated to reporting strategy d ∈ A is denoted S d . Hence, starting at time 0 in a class level s, the representative driver needs to solve at time 0 the following stochastic control problem

(2) V 0 (s) = inf d∈A E T t=0 1 (1 + r) t P S d t + 1 1 + r L t 1 Lt≤d S d t S d 0 = s ,
where L t denotes the loss occurred on the year t, which is simply valued 0 whenever no claim happens on this period, and is only reported whenever it exceeds the chosen threshold strategy (d s ) s .

We assume that the premia are paid at the beginning of each period, whereas the unreported losses are due at the end of the period.

The purpose of the next section is the resolution of this control problem and the numerical derivation of the corresponding optimal reporting strategy d .

3. Derivation of the optimal loss reporting strategy 3.1. A dynamic programming approach. In order to solve the control problem (2), the easiest way is to focus on its dynamic version and to introduce the value function at any date t = 0, . . . , T given by

(3) V t (s) = inf d∈A E T k=t 1 (1 + r) k-t P S d k + L k 1 L k ≤d S d k 1 + r S d t = s , t = 0, . . . , T .
In order to characterize the value function V , let focus on one arbitrary interval [t, t+1] and suppose that a driver starts in class s ∈ S at time t. We denote by s the new class in case of upgrade (i.e. no loss reported) and s the new class in case of downgrade. In order to decide wether he should or note report the claim, the economically rational driver will compare V t+1 (s) and V t+1 (s). He should report the claim if and only if the difference between the value functions exceeds the loss (which is also paid at time t + 1). This gives rise to the so-called implied deductible optimal strategy (d s ) s∈S and the associated probability of reporting a claim (π s ) s∈S , where

d s := V t+1 (s) -V t+1 (s) and π s = P[L ≥ d s ] , s ∈ S .
On the time interval [t, t + 1], the driver may or not encounter a claim, and then may choose to report it or not, depending on his threshold reporting strategy d . This gives rise to the following representation of the value function at time t in terms of the value function at time t + 1.

Lemma 3.1. The value function of the driver is given by V T (s) = P s together with

V t (s) = (1 -p) • π s • V t+1 (s) 1 + r (1)
+ p • V t+1 (s) 1 + r (2) + (1 -p)(1 -π s ) • E[L|L ≤ d s ] + V t+1 (s) 1 + r (3)
+ P s (4)
, for t < T . The first part (1) is the probability to get a loss, and to claim it, with probability π s , and downgrade to class s; the second part (2) is the probability to get no loss and to upgrade to class s; the third part (3) is the probability to get a loss and not to claim it. The expected loss is then

E[L|L ≤ d s ]
where d s is the implied deductible. And as discussed above

d s = V t+1 (s) -V t+1 (s)
The last part (4) is the premium paid at time t.

Proof. At terminal date T , it is always optimal to report a claim as upgrading or downgrading classes is not important anymore. Hence, a driver always reports a claim, leading to the enhanced terminal condition V T . The expression relating V t and V t+1 follows from the application of a dynamic programming principle in its simplest form. It indeed suffices to study separately the 3 different cases. If a claim does not occur (with probability p), the driver is upgraded to s and we obtain

p • V t+1 (s) 1 + r .
If a claim occurs with probability (1 -p) and the driver chooses to report it, because it is too large, i.e. with probability π s , he faces no immediate cost but is downgraded to level s. This gives rise to the term

(1 -p) • π s • V t+1 (s) 1 + r
Finally, the term (3) follows from the occurrence of a loss L which is too small to be claimed. This happens with probability (1 -p)(1 -π s ). Then, the driver pays the loss and is upgraded to s. Hence we obtain

(1 -p)(1 -π s ) • E[L|L ≤ d s ] + V t+1 (s) 1 + r
Recall that the implied deductible d is defined in terms of the value function V itself. Hence, the characterization of V is not complete yet. Besides, the attentive reader would have noticed that the implied deductible d depends on time in its current form, since it defines at any time t in terms of the difference between the value functions at time t + 1. In order to bypass this issue, one simply needs to focus on the stationary version of this problem, for which T = ∞. In this case, the value function does not depend on time anymore and neither does the implied deductible d . We simply denote by V the stationary value function associated to the infinite horizon valuation problem. We deduce the following characterization of V .

Proposition 3.2. In a stationary framework, the value function of the driver is given by

V (s) = (1 -p) • [1 -F (V (s) -V (s))] • V (s) -V (s) 1 + r + V (s) 1 + r + P s + (1 -p) • F (V (s) -V (s)) • G(V (s) -V (s)) ,
for any s ∈ S, where F is the cumulative distribution function of the loss L and

G : d → E[L|L ≤ d] .
Proof. For any horizon T , the value function of the driver satisfies

V t (s) ≤ ||P || ∞ + µ 1 + r ∞ k=0 1 (1 + r) k = (1 + r)||P || ∞ + µ r ,
since this upper bound corresponds to the case where the driver is always paying the highest premium, while never reporting any claim. Besides, the value function of the driver is obviously increasing with the maturity T , so that it converges as T goes to +∞. Then, the value function (V t ) t enters a stationary framework so that, at the limit, V t does not depend on time anymore. Recalling the expression of (d s ) s∈S and recalling that π s = 1 -F (d s ), a direct reformulation of the expression presented in Lemma 3.1 provides the announced result.

Numerical Resolution.

Observe that equations obtained in Proposition 3.2 yield a nonlinear system of |S| equations. It may rewrite in the form V = H(V ), where V is the collection of the (V (s)) s∈S . A solution -defined as an optimal strategy -is a fixed point of that system of equations.

In order to obtain a fixed point for such system, we consider some starting values V (0) = (V (s) ) s∈S and set, at step i + 1, V (i+1) = H(V (i) ), i.e. V (i+1) is the solution of the linear system

V (i+1) (s) = (1 -p) • [1 -F (V (i) (s) -V (i) (s))] • V (i) (s) -V (i) (s) 1 + r + V (i) (s) 1 + r + P s + (1 -p) • F (V (i) (s) -V (i) (s)) • G(V (i) (s) -V (i) (s)) ,
Starting values can for example be the myopic ones obtained as discussed in Section 1.3,

V (0) (s) = ∞ k=1 P max{s-k,1} (1 + r) k ,
where, starting from class s, we assume that no claims are reported in the future.

Proposition 3.3. The sequence of value functions (V (n) ) n∈N constructed by the above algorithm converges to the stationary value function V of the driver, as described in Proposition 3.2.

Proof. Observe that the algorithm presented above is built in such a way that the n th value function V (n) has a nice re-interpretation in terms of solution to a stochastic control problem.

Fix n ∈ N. Consider a driver with horizon T = n and trying to solve

V n 0 (s) := inf d∈A E n-1 k=0 1 (1 + r) k P S d k + L k 1 L k ≥d S d k 1 + r + V (0) (S d n )|S d 0 = s , s ∈ S .
Then, according to Lemma 3.1 and the constructing algorithm for V (n) , the value function V n 0 at time 0 exactly coincides with V (n) . Besides, following the same reasoning as in Proposition 3.2, V n 0 converges to the stationary limit V as n goes to infinity, since the horizon hereby converges to infinity and the terminal condition V (0) has no impact on the limit. Therefore, the algorithm produces a sequence of functions (V (n) ) n∈N which converges to the stationary limit V of interest.

3.3.

Reformulation of the algorithm for some parametric loss distributions. In order to provide a numerical illustration of the algorithm, an important quantity that we need to compute is G(V (s) -V (s)), based on the loss distribution. For convenience, let us consider some (standard) parametric loss distribution. Recall that for numerical applications, µ = E(L) = P /(1 -p).

If L has an exponential distribution with mean µ, the cumulative density function F is given by F ( ) = 1 -e -/µ when > 0. In that case, we compute

G : d → µ - d • e -d/µ 1 -e -d/µ .
If L has a Gamma distribution with shape parameter α and β, then its average is valued µ = αβ, and its density is given by

f : x → x α-1 Γ(α)β α e -x β .
In that case, we can compute

E[X1 X<d ] = d 0 x α Γ(α)β α e -x β dx = βd α Γ(α)β α e -d β + d 0 αβ Γ(α)β α x α-1 e -x β dx = β 1-α d α Γ(α) e -d β + αβF (d) .
And we deduce from the expression of the cumulative density function F that

G : d → β 1-α d α Γ(α, d/β) e -d β + αβ .
where Γ : (a, z) → z 0 t a-1 e -t dt.

4. Illustration on the 'Spanish Bonus-Malus' system

In order to provide a realistic illustration of our methodology, we consider the 'Spanish Bonus-Malus' scheme, as described in [START_REF] Lemaire | Automobile Insurance: Actuarial Models[END_REF], Appendix B-18. In this scheme, each driver is highly penalized in case of reported claims as they automatically downgrade to the worst possible class, independently of their current premium. This is summarized in the following transition rules table :   Class Premium Class After 0 Claim Class After 1 Claim 2. Transition rules for the 'Spanish Bonus-Malus' scheme.

Therefore, the associated transition is matrix is given by

M =        p 0 0 0 1 -p p 0 0 0 1 -p 0 p 0 0 1 -p 0 0 p 0 1 -p 0 0 0 p 1 -p       
where p denotes the probabity to have no-claim over a year. The associated Markov chain has a (unique) invariant probability measure µ that can be obtained numerically. For instance, when claims occurrence is driven by an homogeneous Poisson process, with intensity λ = 0.08, we compute p = 92.6% and the stationary measure whenever every driver reports his claims is given by 0.735 0.059 0.063 0.069 0.074 .

Based on the premiums given in Table 2, this leads to a stationary average premium P = 76.13. The stationary distribution of the drivers together with the evolution of P , for different choices of λ are respectively given in Figure 2 and Figure 3. As expected, for higher values of λ, more drivers are present in higher order classes. On the contrary, for λ = 0.04, we even have more than 90% of the population in the best class, numbered 1. Similarly, the level of the average stationary premium P increases with λ, as shown on Figure 3.

Recall that, in order to enforce the actuarial equilibrium, we chose for numerical applications to pick the average level of loss amount µ as q q q q q q q q q Figure 3. Asymptotic premium P , as a function of λ, with p = e -λ .

µ = E(L) = P /(1 -p) .
Hence, from λ and P , we can derive µ, as well as the function G, and apply our numerical algorithm in order to compute the stationary value function associated to each class as well as the optimal reporting strategy, characterized by the implied deductible d . In Table 3, V (0) is the discounted value of future premiums under the naive assumption that no claims will occur in the future. V ∞ is the stationary discounted value of future premium when the optimal strategy is considered. d is the implied deductible, and P(L ≤ d ) is the probability to declare no loss. Here µ = 993 and future values are discounted with a 5% interest rate.

Class 3. Impact of the optimal reporting strategy, Exponential losses, λ = 8% and r = 5%.

V (0) V ∞ d * P(L ≤
Observe that the deductible d s is increasing with the class level s ∈ S, as well as the premium. A driver with a high premium will be more likely to declare any loss, while a driver with a low premium will try to keep his (good) bonus and will avoid declaring losses on purpose.

The evolution of d s as a function of the discount rate r, when λ = 8% and for exponentially distributed losses can be visualized on Figure 4. As the interest rate increases, the rational driver will minimize the impact of a reported claim on his future costs, so that he will be eager to declare more claims, even with smaller levels. Indeed, we observe that the implied deductible d (s) is a decreasing function of r, for any class level s ∈ S.

The evolution of d s as a function of the claims frequency intensity λ, when r = 5% and claim severity is exponentially distributed can be visualized on Figure 5. Le minimal level for claim reporting slowly increases with the frequency λ of the claims.

Whenever the interest rate r is fixed at 5% and the frequency of claims is fixed by λ = 8%, Figure 6 shows the evolution of d s as a function of the coefficient of variation of losses, Var[X]/E[X], for Gamma distributed losses. We observe that high and low variance factors lead to higher deductible levels, meaning that a too small or too large uncertainty on the possible level of claim, provides incitations for the driver not to declare losses of small level. q q q q q q q q q q q q q q q q q q q q Discount Rate (%)

Probability not to Declare (%) q q q q q q q q q q q q q q q q q q q q Poisson λ (%)

Possible extensions

The model considered so far has on purpose been chosen in its simplest form in order to emphasize the effect of a rationally optimal claim reporting strategy. We now discuss several extension possibilities, which can be encompassed in our framework of study.

Addition of Deductibles.

In order for the model to be more realistic, one should take into account that any driver also has to pay a deductible, whenever a claim is reported, see e.g. [START_REF] Zachs | Claiming Strategies and Premium Levels for Bonus Malus Systems[END_REF]. The level of deductible D depends on the current class level s and will be denoted D s . In such a case, the optimization problem of the agent is replaced by where the extra term takes into account that one should pay the deductible D S d t whenever a claim is reported at time t.

V 0 (s) = inf d∈A E T t=0 1 (1 + r) t P S d t + 1 1 + r D S d t 1 Lt>d S d t + 1 1 + r L t 1 Lt≤d S d t S d 0 = s ,
This new formulation gives rise to an optimal strategy which takes the similar form as the one obtained in the no-deductible case:

d s = V t+1 (s) -V t+1 (s) ,
the only difference relying on the previous modification of the definition of the value function. The characterization for the solution presented in Proposition 3.2 as well as the approximating algorithm considered in Section 3.2 can be adapted to this setting in a straightforward manner. 5.2. Consideration of risk averse drivers. In the previous setting, the representative driver is considered to be risk neutral, namely he is neither afraid nor eager to take some risk. The rational behavior of the driver may also be represented using a utility function characterizing his choices under uncertainty. In this framework, the new optimization problem of the agent is given by

V 0 (s) = inf d∈A E T t=0 1 (1 + r) t U P S d t + 1 1 + r L t 1 Lt≤d S d t S d 0 = s ,
where U is the chosen risk adverse utility function of the agent. In such a case, once again, the implied deductible is characterized in a similar fashion and only the computation scheme for the value function is modified. Nevertheless, the dynamic programming principal allows us once again to characterize the value function of the agent as the solution to a non linear system of equations. The only difference is that each payment is computed via its utility value instead of solely its monetary one.

Consideration of heterogeneous agents.

A tempting extension is to try to incorporate heterogeneity in the driver economic behavior. It is quite classical to consider that drivers may have different probabilities of claim occurrence and severity but less in the actuarial literature to incorporate different economic behavior for agents. In our framework, we could consider a collection of driver types x ∈ X , so that each type x of driver is characterized by its own utility function U x together with his interest rate r x . In such a case, a driver of type x will solve the problem

V 0 (s) = inf d∈A E T t=0 1 (1 + r x ) t U x P S d t + 1 1 + r L t 1 Lt≤d S d t S d 0 = s .
Hence, one can solve these problems separately of any x ∈ X and deduce the corresponding collection of implied deductibles (d s (x)) s∈S,x∈X . Then, one can directly compute the corresponding stationary distribution (ν x s ) s∈S associated to any class x ∈ X . Hence, the average premium should by derivedby aggregating all the driver types and computing P = x∈X s∈S P s ν x (s)f (x)dx , where f represents the density function of the types in the population.

Conclusion

We have seen in this paper how hunger for bonus can be incorporated in order to obtain the 'true' transition matrix for class levels, not only based on claims occurrence, but considering the probability to report losses. The dynamic programming problem does not have simple and explicit solutions, but a simple numerical algorithms can be used in order to approximate the solution. We have observed the impact of the hunger bonus in the context of a simplistic bonus-malus scheme, but it can be extended easily to more complex ones, as discussed in particular in Section 5. The most difficult remaining task is clearly to obtain the extension to the case where the bonus-malus scheme takes into account the number of reported claims within a period. A way to solve it is to assume that the driver waits until the date of renewal, to decide how many losses are reported (and which ones), but if equations can be explicitly written (and solved), this approach is not realistic. This is clearly a difficult task for future research.

We chose in this paper not to consider the ex post or ex-ante moral hazard topics associated to the design of optimal insurance policy. The main reason is that, as long as the bonus malus policy is clearly announced in advance by the insurance company, the rational driver should not have any reason to dissimulate his driving skills, other than the economic one presented above. Finally, our model lacks realism since we assume that any driver is rational, able to take economies decisions as the one described above, and only wishes to make his claim reporting on based on solely economic reasoning, instead of e.g. more ethical ones. A natural extension of for such study would be to consider a chosen distribution of 'rationally reporting' type of drivers in the population. Finally, the most difficult part is probably that λ is usually unknown by drivers, and this (possibly heterogenous) ambiguity will indice an additional bias

Figure 1 .

 1 Figure 1. Invariant probability measure as a function of λ, with p = e -λ .

Figure 2 .

 2 Figure 2. Invariant probability measure, as a function of λ, with p = e -λ .

Figure 4 .

 4 Figure 4. Value of the Deductibles, d s as a function of r.

Figure 5 .

 5 Figure 5. Value of the Deductibles, d s as a function of λ.

Figure 6 .

 6 Figure 6. Implied deductible d as a function of the variance of losses.

  with d s ≥ 0 , for any s ∈ S} , where S denotes the collection of class levels. A driver will decide to report a claim while in class s, if and only if the severity of the claim exceeds the threshold d s , i.e. if and only if > d s .The choice of the reporting strategy d ∈ A for the driver has an important impact on the trajectory of his associated class level Markov chain, that we denote (S d t ) t . This can be precisely quantified, as the reporting strategy directly impacts the transition probabilities of the class level Markov chain S d . Let indeed denote by π d s the probability to report a loss (that indeed occurred) for a driver in class s ∈ S, whenever he follows a reporting strategy d ∈ A. Then, π d is given by