Loïc Le Guennec
email: leguennec@sancy.univ-bpclermont.fr

Nancy El Rachkidy

Alexandre Guitton
email: guitton@sancy.univ-bpclermont.fr

Michel Misson
email: misson@sancy.univ-bpclermont.fr

Karim Kelfoun
email: k.kelfoun@opgc.univ-bpclermont.fr

MAC Protocol for Volcano Monitoring using a Wireless Sensor Network

Many existing MAC protocols for wireless sensor networks try to achieve simultaneously low latency and low power consumption. For many monitoring applications, however, there are two separated types of traffic. Most of the traffic is periodic, and is not subject to latency constraints: energy savings is the main objective for this traffic. A small proportion of the traffic has strict latency requirements, and the energy consumed for this priority traffic is not an issue. In this paper, we introduce a MAC protocol that can achieve this traffic differentiation in a WSN. We propose to combine the low power listening approach for periodic traffic with opportunistic encounters mechanisms for urgent traffic. We show that our approach provides a good ratio of consumed energy per delivered packet of the periodic traffic, while keeping a low loss rate for the priority traffic.

I. INTRODUCTION

Wireless Sensor Networks (WSNs) cover a wide range of applications, including the monitoring of natural sites [START_REF] Barrenetxea | Wireless sensor networks for environmental monitoring: The sensorscope experience[END_REF], [START_REF] Chen | Natural disaster monitoring with wireless sensor networks: A case study of dataintensive applications upon low-cost scalable systems[END_REF]. Volcanoes are natural sites that are typically difficult to monitor, due to dangerous access. Deploying disposable wireless sensor nodes for extended periods is a way to collect environmental data periodically, without risking the loss of costly hardware when the volcano erupts. Two types of traffic can be identified for volcano monitoring: periodic traffic and urgent traffic. (i) Periodic traffic is collected when the volcano is sleeping, and the data collection has to be energyefficient so that the WSN can last for several months without human intervention. Periodic traffic is usually archived in large databases and processed to build long-term models. Thus, they have loose latency requirements. (ii) Urgent traffic is produced when the volcano becomes active. In this case, the traffic has to be forwarded quickly for two reasons: nodes might be destroyed during seismic events, and the data obtained during volcanic activity is important for scientists. Energy-efficiency is not an issue when these rare events occur.

There are many MAC protocols for WSNs that combine both energy constraints with latency constraints. They often achieve a trade-off of these two objectives. They are usually based on duty-cycling: each node alternates between a sleep state where nodes save energy, and a wake state where nodes can communicate. The BMAC [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF] protocol introduced a low power listening approach based on preambles in order to save energy at the receiver side. In this protocol, sender nodes transmit a long preamble before transmitting the actual data. Receivers wake up periodically to assess the channel. When they detect a preamble, they wait for the data. Otherwise, they go back to sleep. This approach has been improved in the literature in order to reduce the reception time of receivers.

However, our volcano monitoring application suggests two types of traffic that are independent (note that they are not generated at the same time, for instance). Most of the traffic consists of periodic data, which are not subject to latency requirements. However, the urgent traffic has to be delivered as quickly as possible, generally in a bounded time in order to be of value for the scientists. Thus, the main goal is not to have a MAC protocol that achieves a good trade-off in energy consumption and in latency, but a protocol that is able to deal with QoS differentiation at the MAC layer.

In this paper, we introduce a new MAC protocol for volcano monitoring with a WSN. Our protocol achieves QoS differentiation at the MAC level. Urgent traffic is sent using an asynchronous sender-initiated approach based on the X-MAC protocol. Periodic traffic is sent using an opportunistic mechanism that takes advantage of the duty-cycle mechanism. In addition, our protocol is able to exploit the convergence of data to a single destination, called sink: each node can transmit its data to the first neighbor towards the sink which wakes up rather than having to wait for a specific neighbor to wake up, thus dramatically reducing latency.

The rest of this paper is organized as follows. Section II presents a brief state of the art of MAC protocols for WSNs. Section III presents a description of our protocol. Section IV discusses the simulation results. Section V presents an overview of the prospects and concludes this paper.

II. RELATED WORK

Energy consumption is a critical issue in most WSN applications [START_REF] Akyildiz | Wireless sensor networks: A survey[END_REF]. Duty-cycling the radio is considered the most relevant technique to achieve power efficiency in the MAC sublayer [START_REF] Huang | The evolution of MAC protocols in wireless sensor networks: A survey[END_REF], as the radio module consumes the largest amount of energy among all the node components. Duty-cycling the radio allows nodes to switch periodically between an active state and an inactive state.

Synchronous MAC protocols alternate active and inactive periods, such that all nodes share their active periods at the same time [START_REF] Tang | SR-MAC: A low latency MAC protocol for multipacket transmissions in wireless sensor networks[END_REF]. This is achieved by implementing a synchronization mechanism at the beginning of the active period. Example of synchronous MAC protocols include S-MAC [START_REF] Ye | An energy-efficient MAC protocol for wireless sensor networks[END_REF], DW-MAC [START_REF] Sun | DWMAC: A low latency, energy efficient demandwakeup MAC protocol for wireless sensor networks[END_REF], or the beacon-enabled mode of IEEE 802.15.4 [START_REF]Part 15.4: low-rate wireless personal area networks (LR-WPANs)[END_REF]. The main advantage of synchronous MAC protocols is that all nodes share a common active period, with a limited period of idle listening. The main disadvantages are the following: the synchronization is generally complex and introduces a significant overhead, and the contention for the medium is high during the active period.

Asynchronous MAC protocols are based on independent schedules of active and inactive periods: the active period of a node might not match the active period of another node. Asynchronous MAC protocols have many advantages: they do not require synchronization, they are conceptually distributed, they are tolerant to network dynamicity, and nodes can achieve lower duty-cycles [START_REF] Tang | Low-latency ashynchronous dutycycle MAC protocol for burst traffic in wireless sensor networks[END_REF].

Asynchronous MAC protocols can be classified into senderinitiated protocols and receiver-initiated protocols. In receiverinitiated MAC protocols, receivers trigger communications by transmitting a probe. When active, the sender remains silent even if it has data to transmit, until it receives the probe from the receiver. Upon receiving this probe, the sender starts the transmission. The main advantage of receiver-initiated protocols is that the length of the probe is shorter than the preamble of sender-initiated protocols, which decreases transmission latency and channel occupancy. The drawbacks of receiver-initiated protocols are the following: (i) the cost of the communication is spent by the receivers, which are more numerous than senders in a WSN, (ii) frequent probe transmissions can cause channel congestion and delay data communications, which negatively impact the scalability.

In sender-initiated MAC protocols, the sender triggers the communications. A preamble is used to notify receivers about upcoming data transmission. The length of the preamble is set to a duration that is longer than the sleep period of the receiver, in order to ensure that the receiver wakes up during the preamble. The preamble also prohibits other neighboring nodes from transmitting, which reduces collisions. B-MAC [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF] sends a preamble with fixed length before starting data transmission. Once the preamble is detected, the node remains active until the end of the transmission or until the node switches to sleep mode. WiseMAC [START_REF] El-Hoiydi | WiseMAC: An ultra low power MAC protocol for the downlink of infrastructure wireless sensor networks[END_REF] allows receivers to piggyback their next wake up time in acknowledgment frames, which reduces the length of further preambles. X-MAC [START_REF] Buettner | X-MAC: A short preamble MAC protocol for duty-cycled wireless sensor networks[END_REF] uses short preambles to reduce the length of preambles.

In this paper, we focus our comparison on the X-MAC protocol, which is an asynchronous, sender-initiated MAC protocol. X-MAC [START_REF] Buettner | X-MAC: A short preamble MAC protocol for duty-cycled wireless sensor networks[END_REF] decreases the length of preamble by transmitting short preambles containing the destination address. When a receiver wakes up, it waits for the end of a short preamble, decodes the destination address, and can decide whether to wait for the frame (at the end of the sequence of short preambles), if it is the destination, or can decide to go back to sleep if it is not the destination. X-MAC also enables the intended receiver to acknowledge the short preamble, which notifies the sender to initiate the transmission immediately, rather than having to wait for the completion of the whole sequence of short preambles. Thus, X-MAC uses overhearing to reduce energy consumption and latency. X-MAC scales well with the network density, as nodes do not spend a large amount of energy while receiving unintended long preambles. X-MAC handles multiple senders in the following way. Senders refrain from sending short preambles if they detect another sender sending its preamble. After a frame exchange has been completed, senders that were waiting for the channel perform a random backoff. This backoff thus removes the synchronization of senders. Also, each sender listens to short preambles sent by other senders in the neighborhood. If a sender s 2 detects a short preamble from another sender s 1 for the receiver r, s 2 checks whether it has frames for r or not. If it has, s 2 attempts to send its frames quickly after the end of the frame exchange between s 1 and r, with a small random backoff. The main drawbacks of X-MAC are its lack of support of QoS and its energy consumption. We plan to address these two drawbacks.

III. PROPOSITION

In this paper, we propose an asynchronous, sender-initiated MAC protocol for volcano monitoring in a WSN. Our protocol shares many similarities with X-MAC (which is why we used X-MAC as the basis for comparison), but our protocol is able to provide QoS differentiation by distinguishing two types of traffic: priority traffic, and periodic traffic. Our protocol also benefits from the fact that in our volcano monitoring application, data is forwarded to a single sink, located far away from the hazardous area.

In a nutshell, our protocol uses the following mechanisms. A duty-cycle is used to parametrize the energy-consumption of the protocol in the case of periodic traffic. Priority traffic is sent using sender-initiated communications (similar as X-MAC), which yields a low delay at the cost of high energy consumption. Periodic traffic is sent using opportunistic communications, which is achieved using low energy consumption but yields potentially large delays. Delays are reduced by taking advantage of the many-to-one paradigm: a node can send the data to any neighbor closer to the sink, rather than waiting for a specific neighbor to wake up.

In our MAC protocol, a node switches between three states: sleeping, listening and sending. (1) In the sleeping state, the node has its radio module deactivated, and saves energy. The node switches to the listening state when an urgent frame is generated by the application, or according to its duty-cycle.

(2) In the listening state, the node waits to receive potential frames by listening to the channel for short preambles. When the end of a short preamble is detected, the receiver determines whether it is closer to the sink than the sender or not (using a distance metric). If it is the case, the receiver sends an early ACK after a randomized backoff, to reduce the risk of collisions among nodes closer to the sink than the sender. Upon receiving the early ACK, the sender sends the data frame. Upon receiving this frame, the receiver sends an ACK, and starts listening for other preambles. The node switches to the sleeping state at the end of its activity duration, provided that it has no urgent frames to send. The node switches to the sending state when it does not detect preambles, and if it has frames to send (either urgent or periodic). (3) In the sending state, the node has data to send. It performs two clear channel assessments in order to obtain the medium access, and starts sending short preambles. Between each short preamble, the node introduces a small delay to allow the reception of early ACKs by potential receivers (including the time required for the random backoff). Upon receiving the early ACK, the sender immediately sends the frame, and waits for an ACK. If no ACK is received, the frame is retransmitted immediately (without having to wait for another early ACK). If an ACK is received, the node starts sending a new preamble for the next frames. The node switches to the sleeping state when it has no more urgent traffic to send, or at the end of its activity duration if it has only periodic traffic in queue. Note that urgent traffic is always sent before periodic traffic. Nodes use two different traffic queues for this purpose.

IV. SIMULATION RESULTS

In this section, we evaluate our MAC protocol by simulation, and we compare it with two variations of the X-MAC protocol. The first variation, called Tree X-MAC, considers that the routing protocol determines for each node a single next-hop to the sink, resulting into a tree topology. The second variation, called DAG (Directed Acyclic Graph) X-MAC, considers that the routing protocol allows each node to route to any neighbor closer to the sink, resulting into a destination-oriented directed acyclic graph topology. Note that our protocol uses the same DAG topology as DAG X-MAC.

In Subsection IV-A, we describe our parameters, as well as our performance metrics. In Subsection IV-B, we focus on a scenario where only urgent traffic is generated. The main goal of this scenario is to compare our MAC protocol with X-MAC, as they share many similarities for the urgent traffic. In Subsection IV-C, we focus on a more realistic scenario where both urgent traffic and periodic traffic are generated.

A. Parameter settings and performance metrics

We developed a discrete-time simulator in C to implement the protocols. We considered topologies of 60 nodes randomly distributed over a 1000 m × 1000 m area. The communication range is set to 100 m. This large communication range is set to represent communications in open-space area (as vegetation is scarce on volcanoes) using a low frequency band of 433 MHz. We consider that the channel is lossless, and assume that a data frame transmission lasts for 10 ms. This large duration could account for retransmissions in a lossy context. The sink node is chosen to be the node closest to the middle of any border of the area. On average, each node has approximately 6 neighbors. We considered the following default parameters (unless specified otherwise): the duty-cycle is set to 5%, the cycle duration is set to 10 s, the frame queue size is set to 15 frames, and 1 frame is generated every 200 s for 2 hours. Simulation results are averaged over 100 repetitions.

To evaluate our protocol, we use three performance metrics. (1) The latency is the time interval between the first transmission of a data frame by the source and its first reception by the sink. Latency only takes in account the frames that are correctly received. (2) Frame loss is defined as the ratio of the number of data frames not received by the sink over the number of data frames generated by the source nodes. The frame loss ratio takes into account the losses due to queue overflows. (3) The real duty-cycle is defined as the proportion of time when nodes are active. The real duty-cycle is a good indication of the energy consumption, as WSN nodes consume a similar amount of energy when sending frames, receiving frames or listening for frames.

B. Scenario with urgent traffic

In this scenario, each source generates an urgent frame every 200 s for 2 hours. 10 source nodes are chosen randomly among the nodes (sink excluded). We compare our MAC protocol with both DAG X-MAC and Tree X-MAC. We also study the effect of queue overflows in our MAC protocol by evaluating a version of our MAC protocol with unlimited frame queues. This version is described as without queue limitations (or without queue for short).

The percentage of frame loss is 0% for duty-cycles varying from 3% to 7%, for all protocols. As the channel is lossless, queue overflows are the main source of losses. However, all protocols are able to handle one urgent frame per source every 200 s, without filling the queues.

Figure 1 shows the maximum latency below which 90% of urgent frames are received by the sink, as a function of the cycle duration. When the cycle duration is large (and for a fixed duty-cycle of 5%), nodes are inactive for larger durations. Thus, frames have to wait longer to be forwarded to the next hop. Our MAC protocol achieves lower latencies than both X-MAC variations because in our protocol, nodes remain active as long as they have a frame to send. By comparing the latency between Tree X-MAC and DAG X-MAC, we can see that using a DAG significantly reduces the latency. Overall, our protocol achieves a reduction of about 10 s on average when compared to DAG X-MAC. Cycle duration (s) Max. latency for urgent traffic (s) Figure 1. When nodes have urgent frames in queue, they remain active (without considering their duty-cycle). Thus, our MAC protocol achieves lower latency than both X-MAC variations.

Figure 2 shows the overall energy consumption as a function of the frame generation frequency. The frame generation period varies between 150 s and 250 s between frames. We notice that our MAC protocol consumes more energy than X-MAC. Indeed, when nodes have urgent frames in queues in our MAC protocol, they remain active. In X-MAC, nodes use their duty-cycle energy-saving mechanism even when they have urgent frames in queue. Frame generation frequency (frames/node/hour) Energy consumption Figure 2. Energy consumption is larger for our MAC protocol than for X-MAC as nodes are always active.

To summarize, our MAC protocol is able to transmit urgent frames faster than the X-MAC protocol, at the cost of higher energy consumption. Note that the approaches based on the DAG (that is, both DAG X-MAC and our MAC protocol) significantly reduce latency and energy consumption compared to the approach based on the tree (that is, Tree X-MAC).

C. Scenario with mixed traffic

In this scenario, each node generates periodic frames, and 10% of nodes are sources for the urgent traffic, with both traffic generated with the same frequency. The goal of this scenario is to show how our MAC protocol handles QoS differentiation. The queue size of both X-MAC variation is set to 15 frames. Our MAC protocol uses two queues: the periodic traffic queue size is set to 10 frames, and the urgent traffic queue size is set to 5 frames.

Figure 3 shows the maximum latency for urgent traffic as a function of the duty-cycle (used for periodic frames). We notice that the duty-cycle does not have a major impact on maximum latency. Indeed, for all protocols, frames experience a maximum latency when each sender has to wait for the receiver during a nearly full cycle. Thus, the main factors of maximum latency are cycle duration and maximum number of hops from a source to the sink, rather than duty-cycle. The variability of the Tree X-MAC results come from the variability of the length of the longest paths for each topology. It can be observed that the maximum latency with Tree X-MAC is significantly larger than with all the other protocols (due to the limitations imposed by the tree routing), and that our MAC protocol is able to achieve smaller latencies for the urgent traffic, even in the presence of periodic traffic.

Figure 4 shows the percentage of urgent frame loss, as a function of the duty-cycle. We notice that the loss is negligible for all the protocols (it is about 1.4% for Tree X-MAC, and less than 0.4% for our MAC protocol). Indeed, as the channel is considered lossless, the frame loss is due to queue drops Duty-cycle (%) Max. latency for urgent traffic (s) Figure 3. Maximum latency for urgent traffic, for a scenario with mixed traffic. The duty-cycle in our MAC protocol is used for the periodic traffic only.

mostly. This result show that the network load fits the network capacity, and that further latency results can be compared in a fair way (as latency only takes into account received frames). Duty-cycle (in %) Frame loss for urgent traffic (in %) Figure 5 shows the percentage of frame loss for periodic traffic as a function of the duty-cycle. The percentage of frame loss is small for both X-MAC variations (it is null for DAG X-MAC, and less than 5% for Tree X-MAC). However, our MAC protocol yields between 15% and 30% frame losses. This is due to the small size of the periodic frame queue (which is only 10 in our MAC protocol, instead of 15 for X-MAC). Our MAC protocol allows some periodic frames to be lost in order to save energy and delay. Indeed, we assume that periodic frames have a less priority than urgent frames. It can be noticed that when the queue size limitation is removed from our MAC protocol, there are no more packet losses.

Figure 6 shows the average latency for periodic traffic as a function of the duty-cycle. Both X-MAC variations show that the duty-cycle has a small influence on average latency, as mentioned earlier. In our protocol, it can be noticed that the latency decreases when the duty-cycle increases. Indeed, when the duty-cycle is large, the probability that nodes communicate with each other increases, and thus frames wait less in queues. When there is no queue limitation, the latency is higher than when there is a queue limitation, because when there is a queue Duty-cycle (in %) Frame loss for periodic traffic (in %) Figure 5. Frame loss for periodic traffic is important for our MAC protocol due to the priority given to urgent traffic. overflow, frames that are dropped tend to be frames having waited for a long time in queue, which artificially reduces the latency. X-MAC shows better performance in terms of latency than our MAC protocol. This is due to the fact that our protocol considers that periodic frames have no delay constraints, and thus does not attempt to transmit them quickly. It can be seen that on average, our MAC protocol sends periodic frames about four times slower than DAG X-MAC. Duty-cycle Av. latency for periodic traffic (s) Figure 6. Periodic traffic is not a priority. Therefore, it waits more time before it is treated especially when urgent frames are generated.

Figure 7 shows the real duty-cycle (which measures the consumed energy) as a function of the parametrized dutycycle. Recall that urgent frames increase the real duty-cycle compared to the parametrized duty-cycle. It can be seen that our MAC protocol provides a good trade-off in terms of energy consumption, especially when the parametrized duty-cycle is low. The duty-cycle of X-MAC is constant (it depends on the activity duration and on the cycle duration).

V. CONCLUSION Volcano monitoring applications based on WSNs generally produce two types of traffic: periodic traffic and urgent traffic. When nodes produce periodic traffic, the main goal is to increase the network lifetime by reducing the energy consumption, and delay is usually not an issue. However, when nodes produce urgent traffic, the main goal is to forward this traffic quickly, without focusing on energy savings. In this paper, Parametrized duty-cycle (in %) Real duty-cycle (in %) Figure 7. For X-MAC, both real and parametrized duty-cycles are similar.

we have proposed a MAC protocol that can achieve traffic differentiation. Our MAC protocol achieves a good trade-off between energy savings for the periodic traffic, and small latency for the urgent traffic. We show by simulation that our MAC protocol fills the gap of other MAC protocols of the literature, such as X-MAC.

Figure 4 .

 4 Figure 4. Frame loss is negligible for all the protocols: the network load fits the network capacity.

Acknowledgment: This work has been partially funded by the Clervolc laboratory of excellence.


Mathieu Lafourcade1
email: mathieu.lafourcade@lirmm.fr

Nathalie Le Brun2

Virginie Zampa3
email: virginie.zampa@u-grenoble3.fr

Keywords: association couleur-mot, réseau lexical, crowdsourcing Word Color Associations, Lexical Network, Crowdsourcing

En TAL et plus particulièrement en analyse sémantique, les informations sur la couleur peuvent être importantes pour traiter correctement des informations textuelles (sens des mots, désambiguïsation et indexation). Plus généralement, connaître la ou les couleurs habituellement associée(s) à un terme est une information cruciale. Dans cet article, nous montrons comment le crowdsourcing, à travers un jeu, peut être une bonne stratégie pour collecter ces données lexico-sémantiques.

Introduction

La couleur, en tant qu'élément de notre vie quotidienne, est une donnée intéressante en Traitement Automatique du Langage Naturel. En effet, fournir des informations relatives aux associations mots-couleurs, en plus des données classiques (hyperonymes, parties de, rôle sémantique, etc.) à un système dédié à l'analyse sémantique de textes, pourrait en améliorer grandement les performances. Bien que ce soit une observation marginale par rapport au sujet de cet article, il existe indiscutablement une très forte liaison entre couleurs et émotions. Ainsi, si on relève souvent des associations entre des couleurs et des termes abstraits relatifs à des émotions (comme la crainte, la colère, le danger, l'espoir, etc.), c'est encore plus vrai pour les termes désignant des choses concrètes (comme le ciel, un lion, la mer, la neige, etc.).

En psychologie, de nombreuses études concernent les associations entre mots et couleurs et leur impact sur la communication (verbale ou non-verbale). Saif (2011a) montre que la notion de couleur est d'une importance capitale pour la qualité du message délivré, que ce soit en marketing [START_REF] Sable | Color: Cross cultural marketing perspectives as to what governs our response to it[END_REF], en conception de sites web [START_REF] Meier | Ace: a color expert system for user interface design[END_REF][START_REF] Pribadi | The use of color in computer interfaces: Preliminary research[END_REF], ou pour caractériser visuellement une information [START_REF] Christ | Review and analysis of color coding research for visual displays[END_REF][START_REF] Card | Readings in information visualization: using vision to think. Interactive Technologies[END_REF]. La couleur est indiscutablement une donnée très porteuse de sens. Mais pour de nombreux chercheurs, les significations attribuées aux couleurs dépendent de plusieurs facteurs. [START_REF] Luscher | The Luscher Color Test[END_REF], psychothérapeute auteur du test éponyme, le Lüscher color test, un outil qui permet d'évaluer l'état émotionnel d'une personne en fonction de ses préférences de couleurs, affirme que le choix de telle ou telle couleur par une personne dépend directement de (voire traduit) ses émotions et son état psychique. Child et al. (1968), et [START_REF] Ou | Age effects on color emotion, preference, and harmony[END_REF] montrent que les préférences en matière de couleurs varient en fonction de l'âge et du sexe. De plus, pour certaines couleurs, on rencontre des variations lexicales en fonction des langues et des cultures (par exemple, en turc et en hongrois, il existe deux mots différents pour rouge).

Savoir si la relation établie entre couleur et sens est indépendante de l'âge, du sexe, ou de la nationalité, reste une question très controversée qui fait actuellement l'objet d'un vif débat. Cela pourrait être le cas, par exemple, pour la relation entre la couleur rouge et la notion de danger, étant donné que le rouge est associé aux idées de sang et de feu dans de nombreuses langues/cultures. [START_REF] Berlin | Basic Color Terms: Their Universality and Evolution[END_REF] disent que les différences pourraient être classées hiérarchiquement, et qu'on retrouve un nombre limité de termes de couleurs de base dans différentes cultures. Cette analyse est issue d'une comparaison des mots désignant des couleurs dans 20 langues, mais elle est particulièrement controversée, en particulier concernant la méthodologie employée pour la collecte des données. Dans un même ordre d'idée, on pourrait remarquer que de nombreuses expressions faisant référence à une couleur ont le même sens dans différentes langues, a fortiori si elles sont culturellement proches, ce qui n'est guère surprenant. Par exemple, dark thoughts en anglais et idées noires en français ont des sens pratiquement équivalents, de même que to see red et voir rouge. Cependant, il s'agit évidement d'exemples issus de langues tellement proches linguistiquement et culturellement, que cela ne peut guère valider une quelconque universalité des associations possibles entre lexiques et couleurs.

LES COULEURS DES GENS

De nombreuses études, principalement en anglais, visent à établir des relations entre couleurs et mots, et en particulier couleurs et émotions. La plupart sont effectuées d'une manière classique en psycholinguistique, et leurs données brutes sont généralement de taille modeste et non librement accessibles. De plus, comme nous l'avons souligné précédemment, il est extrêmement délicat (et probablement imprudent) d'extrapoler directement le résultat de telles études d'une langue à une autre. Ainsi, il n'est actuellement pas possible d'aboutir à un consensus sur l'universalité des associations de mots et de couleurs quand il s'agit de sentiments, ou du moins de termes abstraits. [START_REF] Saif | Even the Abstract have Colour : Consensus in Word-Colour. Associations[END_REF], au terme de diverses expériences sur un échantillon de 11 couleurs, a conclu que plus de 30% des termes issus d'un dictionnaire de vocabulaire courant étaient fortement liés à une couleur. Environ 33% des catégories de thésaurus (comme Roget) révèlent des associations de couleurs, et les termes abstraits sont associés à des couleurs (principalement de façon métaphorique) presque aussi souvent que ceux désignant des objets, des entités physiques. De même, [START_REF] Nijdam | Mapping Emotion to Color, Human Media Interaction Human Media Interaction[END_REF] compare différents modèles issus de la recherche sur les liens entre couleurs et émotions, et propose une correspondance. Il conclut que si certains modèles de signification des couleurs ont des points communs et se recoupent partiellement, ils témoignent aussi d'une forte variabilité, sans doute parce que la couleur est appréhendée différemment suivant la situation affective/culturelle du sujet. En résumé, l'acquisition de données lexicales sur les associations motscouleurs se heurte à une forte variabilité, même au sein d'une même langue: plus le terme est abstrait, plus on doit s'attendre à une variabilité des couleurs qui lui sont associées. [START_REF] Ozbal | A Comparison of Unsupervised Methods to Associate Colors with Words. Affective Computing and Intelligent Interaction[END_REF] sont à l' origine d'une ressource qui répertorie des associations mots-couleurs en anglais. Sur une sélection de 200 mots (un sous-ensemble des mots utilisés dans [START_REF] Grefenstette | The color of things: Towards the automatic acquisition of information for a descriptive dictionary[END_REF]), ils ont utilisé trois méthodes automatisées pour comparer leur ressource avec les associations faites par le service Amazon Mechanical Turk (10 annotateurs-11 couleurs): analyse d'images, modèles de langages sur les données du web, et similarité entre mots et couleurs en utilisant LSA. Actuellement, pour autant que nous le sachions, [START_REF] Ozbal | A Comparison of Unsupervised Methods to Associate Colors with Words. Affective Computing and Intelligent Interaction[END_REF] sont les seuls à avoir tenté de réaliser une ressource lexicale d'associations mots-couleurs en anglais. Ce type de ressource est quasiment inexistant dans d'autres langues, et notamment, il n'existe rien de similaire en français. Cela dit, comme l'a fait remarquer [START_REF] Grefenstette | The color of things: Towards the automatic acquisition of information for a descriptive dictionary[END_REF], s'il y a une caractéristique qu'en général les gens connaissent à propos des choses (concrètes ou même abstraites), c'est bien leur couleur typique. C'est pourquoi cette information est généralement absente des dictionnaires et autres ressources lexicales, alors qu'elle serait d'un intérêt majeur pour de nombreuses applications informatiques, et en particulier en TAL. L'information de couleur peut être très utile dans le cadre de la désambiguïsation lexicale automatique (Word Sense Disambiguation -WSD). Par exemple, le mot tissu est polysémique et peut signifier -entre autres-étoffe ou tissu vivant. Si, dans un texte, le mot tissu est associé à bleu, cette information va pouvoir aider à choisir la signification appropriée, ou du moins permettre d'éliminer celle(s) qui est (sont) non pertinente(s). L'information relative à la couleur est également précieuse dans la situation où on cherche à retrouver un mot momentanément oublié mais qu'on a sur le bout de la langue, à l'aide d'une application informatique à laquelle on fournit des indices (Lafourcade 2012et Joubert 2012).

L'objectif de cet article est de montrer comment on peut générer efficacement et relativement vite une ressource lexicale d'associations entre couleurs et mots : c'est pour acquérir ce type de données que nous avons mis au point un GWAP (Game With A Purpose selon le concept défini par L. von Ahn. ( 2006)), baptisé ColorIt (accessible à http://www.jeuxdemots.org/colorit.php). Dans un premier temps nous évoquons l'intérêt que peut avoir l'information relative à la couleur dans le cadre de la WSD, puis nous exposons rapidement le fonctionnement du jeu ColorIt et poursuivons par une analyse détaillée des résultats obtenus.

ColorIt, un jeu pour associer des couleurs et des mots

Le but de ColorIt est de collecter des associations spontanées entre couleurs et termes, qu'il s'agisse de couleurs attribuées à des objets concrets, ou associées symboliquement et subjectivement à des verbes ou noms désignant des entités abstraites.

Intérêt des associations mots-couleurs pour la désambiguïsation lexicale

L'un des intérêts majeurs d'une ressource lexicale rassemblant des associations entre mots et couleurs est son exploitation dans le contexte de la désambiguïsation lexicale automatique (WSD). En effet, dans un texte donné, la précision apportée par l'indication de couleur est souvent le détail qui va permettre de sélectionner le sens approprié d'un terme polysémique. Dans de nombreux cas, l'association à une couleur spécifique est importante. Bien sûr, la technique a ses limites : il existe des mots pour lesquels l'information de couleur est sans objet (sans couleur), d'autres auxquels on peut associer de nombreuses couleurs (comme voiture), ou qui peuvent être simultanément de plusieurs couleurs (noir et blanc pour un pingouin, multicolore pour un arc-en-ciel). Sans prétendre à l'exhaustivité, nous donnons dans le tableau ci-après quelques mots pour lesquels l'information de couleur peut aider à lever l'ambiguïté résultant de la polysémie (les sens que l'on peut éliminer sont marqués par *, les ambiguïtés qui subsistent par ?). Les résultats présentés ci-dessous sont ceux obtenus par désambiguïsation endogène d'un terme associé à un contexte (la couleur) sur les données du réseau lexical JeuxDeMots.

Dans les coulisses

Le projet JDM [START_REF] Lafourcade | Making people play for Lexical Acquisition[END_REF][START_REF] Chamberlain | Using Games to Create Language Resources: Successes and Limitations of the Approach. Theory and Applications of Natural Language Processing[END_REF] Un algorithme heuristique a été conçu de manière à avoir une probabilité raisonnable de sélectionner un terme pour lequel l'information de couleur a du sens. Ainsi, nous évitons de lasser les joueurs en leur proposant trop de termes pour lesquels c'est la réponse pas de couleur qui s'impose. Cet algorithme qui choisit le terme à proposer au joueur est le suivant : nous sélectionnons aléatoirement, dans le réseau JeuxDeMots, un mot qui a au moins une relation de couleur positive. Nous proposons ensuite au joueur, via un pile ou face virtuel, soit ce terme soit un de ses voisins dans le réseau. Ceci entraine une propagation rapide de l'acquisition des relations de couleur à travers le réseau. Un terme qui aura été caractérisé comme sans couleur plusieurs fois sera retiré de la liste des voisins sélectionnables. De la même manière, les raffinements des termes "colorés" deviennent rapidement "colorés" euxmêmes. Le principe qui sous-tend cet algorithme de propagation est qu'il y a plus de chances de sélectionner un terme éligible pour l'information de couleur s'il est lié à un mot qui a déjà lui-même une caractéristique de couleur. Une sélection entièrement aléatoire serait contre-productive parce que la plupart du temps, aucune information de couleur ne pourrait être proposée par le joueur; en effet nous avons estimé par échantillonnage qu'environ 10% seulement des quelques 320 000 termes du réseau sont éligibles pour l'information de couleur.

Si une réponse fournie par le joueur existe dans le réseau mais n'est pas caractérisée comme une couleur ou une apparence, elle est alors proposée et sera validée (ou invalidée) en tant que telle par un administrateur. Si par contre le terme proposé n'existe pas dans le réseau, il doit d'abord y rentrer (toujours par validation), avant d'être caractérisé comme une couleur ou une apparence. L'interface Diko du réseau lexical JDM est un outil contributif permettant la validation des termes proposés (http://www.jeuxdemots.org/diko.php). L'algorithme de propagation a été amorcé avec les termes de couleurs proposés dans le jeu : blanc, gris, noir, rouge, rouge foncé, orange, jaune, vert clair, vert, bleu, bleu clair, violet, rose, beige, marron. Avant la création de ColorIt, ces couleurs étaient associées à de nombreux termes via d'autres relations que la couleur.

Collecte et évaluation des données

En neuf mois (août 2013 à avril 2014), plus de 28 000 associations mots-couleurs ont été créées et plus de 16 000 termes ont été dotés d'une information de couleur. Ainsi, en moyenne, un terme est associé à 2,2 couleurs (hors sans couleur). Le nombre total de votes de couleurs a excédé 192 000, le nombre de joueurs n'est pas connu avec précision (il n'est pas nécessaire de s'enregistrer pour jouer). D'après notre estimation sur le nombre de termes éligibles pour une information de couleur, nous pensons qu'actuellement la moitié des termes éligibles ont été dotés d'une information de couleur (soit environ 16 000 termes sur 10 % de 320 000).

Dès qu'une couleur a été associée à un terme, le réseau est mis à jour avec cette couleur ou apparence. Par exemple, le mot eau est associé avec différents bleus (bleu clair (26), bleu (9), bleu lagon (1), turquoise (1), etc.) plusieurs autres couleurs (verdâtre (4), vert (2), etc.) et différentes apparences (trouble (20), transparent (9+9), limpide (4), incolore (4), etc.). La possibilité d'ajouter des couleurs ou des apparences via le champ de texte libre permet de compléter le réseau avec des noms de couleurs spécifiques comme jaune chartreuse, mandarine, etc., des apparences comme rayé, translucide, etc., ou encore de nouvelles combinaisons de couleurs (la liste des couleurs est disponible à l'url http://www.jeuxdemots.org/colorit.php?action=colorlist). Actuellement, plus de 700 termes correspondent à des couleurs, des associations de couleurs ou des apparences. La Table 3 présente l'évaluation de l'accord entre joueurs en fonction de l'appartenance des termes à tel ou tel domaine (champ sémantique). La valeur de l'accord pour un terme donné est la moyenne du Kappa de Cohen entre les associations des joueurs prises 2 à 2 pour ce terme. La valeur de l'accord pour un champ sémantique est la moyenne des accords des termes de ce champ qui ont été joués. Certains termes peuvent appartenir à plus d'un champ. C'est pour le champ sémantique relatif aux plantes que l'accord entre joueurs est le plus élevé. Il semble que certains joueurs se réfèrent à des sources extérieures (comme par exemple Wikipédia) pour savoir quelle(s) couleur(s) affecter à une plante ou un animal inconnu, jouant ainsi le rôle d'identificateurs d'informations qu'il serait très difficile d'extraire automatiquement (communication personnelle avec certains des joueurs). L'accord le plus faible est celui relatif au champ sémantique des émotions, ce qui s'explique aisément par le haut degré de subjectivité des associations correspondantes (et ceci bien que notre expérience n'ait été réalisée qu'en français, et sur une population relativement homogène constituée de 70 % de femmes entre 30 et 50 ans). Concernant le champ sémantique des arts, on trouve beaucoup de noms de couleurs exprimés au moyen d'un vocabulaire recherché, mais qui une fois décryptés présentent finalement assez peu de variations.

Conclusion

Nous avons conçu un jeu simple mais stimulant et efficace pour collecter des données relatives aux associations termescouleurs. En quelques mois plus de 15 000 termes ont été associés à une ou des couleurs et environ 4 000 ont été caractérisés comme sans couleur. De nombreuses couleurs et apparences ont été introduites dans le réseau lexical JeuxDeMots via le jeu ColorIt. A notre connaissance, les données collectées constituent la première ressource (dynamique et libre) en français pour ce type d'association. L'une des difficultés dans la conception du jeu a été l'algorithme de propagation permettant de sélectionner des termes éligibles à une information de couleur, de façon à ne pas lasser les joueurs en leur proposant trop de termes auxquels il n'est pas pertinent d'attribuer une couleur.

Table 1 :

 1 Dans environ 70 % des cas, l'information de couleur permet de déduire le sens convenable et d'éliminer les autres sans ambiguïté. Parfois, une incertitude demeure, mais un niveau de confiance peut être calculé. Si la réponse du joueur correspond à une des plus fréquentes, il gagne des points, sinon il en perd. Le nombre de points gagnés est covariant avec le poids des couleurs liées au mot dans le réseau lexical selon une fonction logistique sigmoïde S. Si une couleur est faiblement associée (par rapport à d'autres), le joueur va gagner peu de points. Par contre si elle est très fortement associée, le gain sera plus grand mais plafonné. Le poids associé à la relation motcouleur est incrémenté de 1 à chaque réponse. Une relation de couleur nouvellement associée rentre dans le réseau lexical avec un poids de 1. Supposons par exemple, que dans le réseau le terme éléphant soit associé à gris avec un poids de p1 et à blanc avec un poids de p2. Si le joueur sélectionne gris il gagnera S(p1) points et le poids de la relation gris passera à p1+1. Si le joueur clique sur pas de couleur il perd S(p1+p2) points mais la relation pas de couleur est introduite et prend la valeur 1. Il n'y a pas d'avantage particulier à proposer des couleurs plutôt que pas de couleur.Ce système incite les joueurs à être honnêtes en sélectionnant des couleurs appropriées, et à essayer d'être originaux quand c'est possible. L'honnêteté présupposée de la grande majorité des joueurs a été vérifiée empiriquement et se révèle être une constante dans les GWAP pour lesquels nous avons ce type d'information[START_REF] Chamberlain | Using Games to Create Language Resources: Successes and Limitations of the Approach. Theory and Applications of Natural Language Processing[END_REF]. D'une part une erreur peut être coûteuse en termes de points, d'autre part un joueur qui chercherait à saboter les données en répondant systématiquement de manière incorrecte se lasserait très vite. Aucune tentative de sabotage n'a été détectée à ce jour. Tous les 100 points, le joueur passe au niveau supérieur et bénéficie d'un plus grand nombre de caractères autorisés dans le champ de texte libre. Les facteurs qui rendent le jeu motivant sont la possibilité de comparer sa (ses) réponse(s) avec celles des autres joueurs et la progression en termes de niveau, puisque plus le niveau est élevé plus on peut saisir de mots dans le champ de texte libre. L'expérience montre que la plupart des joueurs préfèrent entrer plusieurs réponses de couleur dans le champ de texte que se contenter de cliquer sur une des couleurs proposées. ColorIt de données lexico-sémantiques, aucune connaissance linguistique n'est requise pour jouer, et les données recueillies sont de bonne qualité (cf section 3) et parfois d'un niveau de précision et de nuance remarquable (voir liste des couleurs/apparences sur le site à jeuxdemots.org/colorit.php?action=colorlist). Ce niveau de précision va sans doute bien au-delà de ce qui est nécessaire pour de la désambiguïsation lexicale, mais reste parfaitement justifié en représentation des connaissances.

		DES COULEURS ET DES HOMMES
	lit blanc	lit > couche: blanc, rouge,	regard bleu/azur	regard> expression (symbolique)
		* lit>rivière	regard noir	* regard>trou
	trompe grise	trompe>éléphant	robe rose / bleu	robe>vêtement
	trompe dorée	*? trompe>instrument de musique	robe blanche /jaune	* robe>pelage (animal)
		* trompe>anatomie humaine	robe pie/alezane	? ambigu pour certaines couleurs
	bas noir	bas> sous-vêtement	tableau noir	tableau>école
		* bas>partie inférieure		? tableau>oeuvre d'art (improbable)
	manteau rouge	manteau>vêtement	feuille blanche	feuille>papier (le plus probable)
		* manteau>géologie		*? feuille>arbre (improbable)
			feuille rouge/jaune/vert	? ambigu pour certaines couleurs
	ours blanc/brun	ours>animal / peluche	canapé bleu	canapé>meuble
	ours rose	ours>peluche		* canapé>petit four
		* ours>imprimerie		? ambigu pour certaines couleurs
	piste blanche/ verte /	piste>ski (symbolique)	brioche dorée	brioche>viennoiserie
	rouge	*piste>chemin		*? brioche>ventre
	langue blanche / rose	langue>organe	savon noir / rose / blanc	savon>savonnette
		* langue>langage		*savon>réprimande
	sucre blanc/roux	sucre>substance	culotte bleu / rouge/	culotte>sous vêtement
	sucre gris	*? sucre>électricité	blanche	* culotte>boucherie
		(ambigu mais improbable)		* culotte>défaite
	costume anthracite	costume>tenue (le plus probable)	motif fleuri	motif>dessin
		*? costume>déguisement		*motif> raison

2.2 Principe du jeu

Un terme est proposé au joueur avec un choix réduit de couleurs via une palette. Il doit cliquer sur la couleur qu'il associe au mot. Il peut également cliquer sur sans couleur ou "passer" (s'il ne connait pas le mot par exemple). Passer n'est pas pénalisant. Enfin, si aucune des couleurs de la palette ne convient, ou s'il souhaite en mettre plus d'une, il peut la ou les saisir dans le champ de texte. Le terme présenté peut être ambigu (feuille) ou contextualisé (feuille>papier / feuille>plante), le réseau JDM contenant pour chaque terme polysémique ses raffinements.

Une fois que le joueur a validé son choix, une notification apparait avec son score ainsi que les réponses données par les autres joueurs pour ce mot. Le score dépend de l'adéquation entre la réponse du joueur et la distribution des couleurs déjà affectées au mot via les réponses des autres. Il existe deux types de réponses : une ou plusieurs couleurs ou bien sans couleur. s'avère être un jeu stimulant et très original si l'on en croit les nombreux retours positifs des joueurs. La variété du vocabulaire proposé et la présence de termes ambigus ou contextualisés (ours>animal, frégate>oiseau, magistrat>singe, avocat>fruit, avocat>justice) évite la monotonie. A côté de certains mots dont la couleur est évidente (comme neige, nuit, charbon, etc.) et ne se prête pas ou peu à une interprétation, d'autres peuvent avoir une large gamme de couleurs possibles, qu'elles soient objectives pour des noms concrets (comme fleur, voiture, etc.) ou subjectives pour des concepts abstraits (comme colère, tristesse, etc.), ou pas de couleur du tout (comme augmentation, audace, etc.). Choisir la couleur que l'on pense être la plus pertinente n'est pas une tâche facile et la confrontation avec les réponses des autres génère excitation, suspense, et… bonne ou mauvaise surprise ! Bien que le jeu ait pour but la LES COULEURS DES GENS collecte

  a pour but de construire un réseau lexical et sémantique le plus large possible par le biais de jeux (GWAP) et de crowdsourcing. Un tel réseau est composé de termes (les noeuds ou sommets) et de relations entre ces noeuds. Les relations sont typées, orientés et pondérées. La ressource contient actuellement plus de 320 000 termes et 9 millions de relations. Le réseau lexical JDM contient des termes, des significations de termes (raffinements), et différentes informations sémantiques(comme personne, être vivant, abstrait, concret, artefact etc.). Les relations sont pondérées (les plus évidentes ont les poids les plus élevés). Les relations affectées d'un poids négatif soulignent une impossibilité intéressante, comme une exception (par exemple: autruche agent: -100 voler). On notera qu'une telle approche peut être utilisée pour désigner des impossibilités en termes de couleurs. Les différentes significations d'un terme sont liées au terme principal par des raffinements. Par exemple, frégate est liée à frégate>navire et frégate>oiseau. Le raffinement frégate>navire est lui-même raffiné en frégate>navire>moderne et frégate>navire>ancien. Chaque raffinement ou sous-raffinement est lui-même connecté à d'autres termes dans le réseau.Dans ce réseau, l'information relative à la couleur n'était jusqu'à maintenant présente qu'à travers la relation caractéristique, donc mélangée à des attributs de nature variée. Etant donnée l'importance de cette relation en représentation des connaissances, elle fait désormais l'objet d'une relation spécifique que le jeu ColorIt permet d'enrichir de manière conséquente.

Table 2 .

 2 DES COULEURS ET DES HOMMESLes données collectées ont été évaluées manuellement, sur deux échantillons d'environ 500 termes, représentant à peu près 2 500 associations mots-couleurs. Le premier échantillon S C a été prélevé parmi les termes ayant au moins une association de couleur, le second S NC parmi ceux ayant au moins un vote de type sans couleur. Les termes de l'échantillon S C peuvent avoir des associations de type sans couleur, et vice-versa. Nous avons demandé à des volontaires de contrôler au hasard certaines associations mots-couleurs, et de dire si elles étaient correctes ou non, que ce soit dans le cas d'association de type couleur ou sans couleur. Cette méthode d'évaluation, où l'on demande à des volontaires de juger des associations (tâche fermée) est orthogonale avec la méthode d'acquisition où l'on demande aux gens de produire les associations (tâche ouverte). Notons que la méthode d'évaluation ne permet pas de se prononcer sur les associations de couleurs éventuellement omises (les silences). Evaluation des associations mots-couleurs et mots-sans couleur.L'évaluation par quelques dizaines de volontaires (via le jeu Askit : http://www.jeuxdemots.org/askit.php) a couvert environ 10 % des associations mots-couleurs générées par le jeu (acquisition). Les données collectées semblent contenir un pourcentage assez bas d'associations incorrectes (cf. Table2). En outre, un examen plus approfondi du réseau lexical montre que les associations incorrectes sont affectées d'un poids faible par rapport aux associations correctes. Par exemple, pour le terme soleil, on trouve une fois l'association avec bleu pour 100 fois l'association avec jaune. De plus, l'examen des termes polysémiques montre que les couleurs associées aux raffinements sont le plus souvent adéquates et pourront éventuellement être discriminantes dans le cadre de la désambiguïsation lexicale (WSD).

		S C Associations de couleur correctes	S C Associations de couleur incorrectes	S NC Associations sans couleur correctes	S NC Associations sans couleur incorrectes	Total
	# votes	13 308		366			708	81	14 463
	%	92 %		2,5 %			5 %	0,5 %	100%
		sous-total 13308/13674 = 97%		sous-total 708/789 = 90%
	Termes liés à	politique (2702 termes)	zoologie (3191 termes)	arts (2815 termes)	émotions (304 termes)	botanique (4481 termes)
	Accord entre joueurs		0.55	0.65		0.71	0.28	0.76

Table 3 .

 3 Kappa moyen entre les joueurs en fonction de différents champs sémantiques d'intérêt concernant les couleurs (réelles ou symboliques). Le chiffre entre parenthèses indique le nombre de termes reliés à ce champ sémantique dans le réseau lexical. Manifestement, les couleurs sont difficiles à accorder aux émotions.

Nous avons eu plusieurs surprises avec les données collectées grâce à ColorIt. Premièrement, le choix sans couleur a été initialement conçu pour servir d'échappatoire aux joueurs lorsque rien ne convenait. Mais il s'est rapidement avéré que la caractéristique sans couleur était précieuse pour éliminer certaines significations en cas de polysémie. En effet, dans le cadre de la désambiguïsation lexicale, la sélection de sens par les indications de couleur est plus souvent réalisée par élimination que par sélection ; cela s'explique, du moins partiellement, par la polysémie par métaphore: des sens abstraits (donc sans couleur) dérivent souvent de termes concrets. Deuxièmement, un effet collatéral et néanmoins positif du jeu a été d'enrichir le réseau JDM d'un grand nombre de couleurs et apparences qui n'y figuraient pas encore. En plus de vraies couleurs nouvellement introduites, le réseau contient maintenant de nombreux termes relatifs à l'aspect visuel, comme translucide, trouble, rayé, tacheté, etc.


Franc ¸ois Delobel
email: francois.delobel@udamail.fr

Nancy El

Alexandre Guitton
email: alexandre.guitton@univ-bpclermont.fr

Analysis of the delay of confirmed downlink frames in Class B of LoRaWAN

Wireless sensor networks have long been characterized by short range communications. Lately, long range wireless sensor networks such as LoRaWAN (long range wide area network) have emerged, increasing the communication range at the cost of reduced bit rate. This paper focuses on the MAC layer of LoRaWAN and studies communications from a gateway to an end-device. We propose a Markov chain model to estimate the delivery delay of an acknowledged communication (with retransmissions) and study the impact of the number of channels, the data-rate and the number of nodes.

I. INTRODUCTION

LPWANs (low-power wide area networks) are based on recent radio technologies for long range, low-power communications, such as LoRa [1], Sigfox [2] and Ingenu [3]. LPWAN technologies have started a new trend for Internet of Things (IoT) and monitoring applications. Indeed, unlike IEEE 802.15.4 [START_REF]Part 15.4 : low-rate wireless personal area networks (LR-WPANs)[END_REF], these long range technologies can efficiently cover wide areas such as whole cities [START_REF] Centenaro | Long-range communications in unlicensed bands: the rising stars in the IoT and smart city scenarios[END_REF], forests, etc.

LoRaWAN [START_REF] Sornin | LoRaWAN Specification[END_REF] specifies a MAC layer designed for the physical layer LoRa. Recently, researchers have started to study LoRaWAN, which is the only public standard for LPWANs.

General discussions on LoRaWAN can be found in [START_REF] Vangelista | Long-Range IoT Technologies: The Dawn of LoRa TM[END_REF], [START_REF] Song | Survey of radio resource management issues and proposals for energy-efficient cellular networks that will cover billions of machines[END_REF], [START_REF] Margelis | Low throughput networks for the IoT: Lessons learned from industrial implementations[END_REF]. In [START_REF] Vangelista | Long-Range IoT Technologies: The Dawn of LoRa TM[END_REF], the authors explain how LPWAN technologies can achieve ubiquitous IoT connectivity. In [START_REF] Song | Survey of radio resource management issues and proposals for energy-efficient cellular networks that will cover billions of machines[END_REF], the authors survey long range cellular networks for machine-to-machine communications, which includes LoRa. In [START_REF] Margelis | Low throughput networks for the IoT: Lessons learned from industrial implementations[END_REF], the authors discuss some security issues of LoRaWAN. A detailed discussion on LoRa is given in [START_REF] Goursaud | Dedicated networks for IoT: PHY / MAC state of the art and challenges[END_REF]: several of our hypotheses are based on this analysis. The only paper giving a performance study of LoRaWAN is [START_REF] Toussaint | Performance analysis of the on-the-air activation in LoRaWAN[END_REF]: the authors focus on the computation of the expected delay for the activation procedure.

LoRaWAN builds a star topology where low-power enddevices communicate with a network server through gateways. LoRaWAN defines three classes of communication: Class A, Class B and Class C. Class A enables low-power communications, initiated by end-devices. Class B enables periodic, low-power communications from the gateway to enddevices, called downlink communications. Class C enables frequent downlink communications, but requires high energy consumption for the end-devices.

In this paper, we study the delay for downlink communications. We focus on Class B of LoRaWAN because Class B is optimized for energy-efficient downlink communications.

Our contributions are three-fold: (i) we analyze in details the Class B specification, and we highlight some limitations, (ii) we propose an analytic model based on a Markov chain for downlink communications with retransmissions, and (iii) we compute the expected delay of these communications under a variety of parameters.

The remainder of this paper is as follows. Section II describes the LoRaWAN standard. Section III presents some issues of Class B and introduces our analytic model. Section IV shows our simulation settings and results. Finally, Section V concludes our work.

II. DESCRIPTION OF LORAWAN

The three classes of LoRaWAN [START_REF] Sornin | LoRaWAN Specification[END_REF] are described in the following. Note that Class B and Class C include all the mechanisms of Class A.

In Class A, communications are always initiated by an enddevice. When an end-device has data to send, it randomly selects an available sub-band and channel, and starts the transmission. Each transmission of an end-device is followed by two reception slots, which allow downlink communications from the gateway. These two reception slots are called receive windows, and are denoted RX1 and RX2. The channel used by the gateway for RX1 is the same as the uplink channel. The channel used by the gateway for RX2 is a predefined channel. The receive windows are the only possibility for downlink communications in Class A. After each transmission, a device cannot transmit again on the same sub-band for a long duration (typically 99 or 999 times the transmission duration, depending on the duty-cycle for this sub-band). This duty-cycle allows end-devices to sleep most of the time, and guarantees compliance with the regulations on medium usage. However, the gateway has to wait for an uplink communication in order to send downlink frames.

In Class B, the gateway broadcasts a periodic beacon every 128s. Between two beacons, each end-device opens N reception slots called ping slots. Downlink communications can occur during these ping slots, as well as during the reception slots that follow a transmission (according to Class A). With this mechanism, Class B enables downlink communications with bounded delay. The ping period is the delay between two ping slots, and is constant. The offset between the beacon and the first ping slot is pseudo-randomly chosen after each beacon by each end-device. Finally, the beacon transmission is protected by a reserved period of 5.12s, which includes a guard time of 3s. Figure 1 gives an example of Class B. The periodic beacons from the gateway are denoted b 1 and b 2 . According to the Class A feature, the end-device initiates the transmission of a data frame d 1 at an arbitrary time. After the transmission, the end-device opens the two receive windows, and refrains from sending on this channel until the time-off duration has expired. According to the Class B feature, the gateway sends a data frame d 2 at the beginning of the fourth ping period. The end-device detects the preamble during the ping slot, and remains active until it has received the whole frame. In Class C, each end-device is continuously listening for potential frames from the gateway. Class C enables low latency downlink communications, at the cost of a very high energy consumption. In the following, we do not consider Class C.

Confirmed downlink transmissions are implemented using an acknowledgment (ACK) and retransmission mechanism: when an end-device receives a confirmed data frame from the gateway, it replies with an ACK. If no ACK is received, the gateway retransmits the data frame. Note that the standard does not specify the ACK timeout nor the number of retransmissions of the data frame by the gateway.

III. DISCUSSION AND PROPOSITION

In this section, we first discuss some issues of Class B. Then, we present our Markov model. Finally, we describe how to compute the expected delay from the Markov model.

A. Discussion on limitations of Class B

We believe that there are issues in Class B in the current version of the standard (version 1.0 [START_REF] Sornin | LoRaWAN Specification[END_REF]). We discuss these issues in the following.

1) Duty-cycle limitation for the gateway: It is not possible for the gateway to send ACKs for a large number of confirmed uplinks. The gateway cannot acknowledge more than one frame every 66.3 seconds for each sub-band (for DR0 and with an ACK payload of 3 bytes). The gateway cannot acknowledge frames for three or more end-devices per sub-band, with saturated end-devices and a duty-cycle of 1% (for DR0 and for a payload of 30 bytes).

It is not possible for the gateway to use most ping slots of Class B. Indeed, each time the gateway sends a small data frame with 10 bytes of payload on a ping slot, it has to wait for 98.13 seconds (with DR0) before using the next ping slot (for all slots using this sub-band). Thus, the number of ping slots N impacts the delay for the first downlink communication, but has a limited impact on the downlink throughput.

In this paper, we consider that the gateway can acknowledge all data frames, and that it can use all ping slots if necessary.

2) Conflicts between Class A and Class B: The standard does not forbid an end-device to transmit during the beacon transmission of the gateway (as Class A end-devices are not aware of the timing of the beacons) or during the ping slots.

In this paper, we assumed that Class B end-devices refrain from sending during the beacon reserved time and ping slots.

3) Delay before ACKs and sub-band availability: The standard does not specify the delay between a confirmed downlink frame from the gateway and the ACK from the enddevice (unlike the random backoff during the transmission of a confirmed uplink frame and the reception of the ACK from the gateway, as the ACK is supposed to be received during RX1 or RX2). Moreover, the standard does not specify the delay between the retransmissions of the same frame.

In practice, we can consider that the gateway is able to estimate the sub-band availability of each end-device, by tracking all frames sent by each end-device. When the gateway receives a data frame, it can compute the time-off duration for the end-device, based on the data-rate and on the frame length. When a data frame is not received by the gateway, the gateway assumes that the sub-band is available for the end-device: in this case, the gateway under-estimates the subband availability. However, it is not possible for the gateway to over-estimate the sub-band availability: it is not possible for an end-device to send a frame while the gateway assumes that the sub-band is unavailable.

In this paper, we considered that the ACK transmission from an end-device occurs as soon as possible (that is, immediately after the sub-band becomes available). After waiting for one symbol, if no transmission is detected, the gateway initiates the retransmission procedure: it retransmits the data frame during either the next ping slot or the next receive window. Figure 2 shows an example of several transmissions. First, an end-device sends a frame d 1 which is received by the gateway. Then, the gateway sends a frame d 2 during a ping slot. The gateway knows that it cannot receive the ACK until the beginning of the third ping period and initiates the timeout accordingly. When the timeout expires, which is depicted by the dotted line, the gateway expects to receive the ACK. However, a 1 is dropped. Then, the gateway resends the frame d 3 at the beginning of the next ping slot. The enddevice is unable to send another ACK, and has to wait. In the meanwhile, the gateway keeps retransmitting the frame (see frame d 4 ), due to the under-estimation of the sub-band availability. Finally, the end-device sends the ACK a 2 during the last ping period. It is important to notice that during the timeout (which occurred during the whole second ping period), it is not possible for the end-device to send a data-frame, as all sub-bands were busy. Thus, the gateway either retransmits the frame at the ping slot that follows the timeout (which was the case for frame d 3 on this example), or it is possible that the end-device sends a data frame between the end of the timeout and the beginning of the next ping slot. The standard also mentions that RX2 uses a predefined channel. If RX2 is shared by all end-devices and is used by the gateway for one end-device, it cannot be used again until the sub-band becomes available. Note that RX2 is generally used by the gateway when the transmitting end-device chose for RX1 a sub-band which was not available for the gateway.

0 0 0 0 0 0 0 1 1 1 1 1 1
In this paper, we assumed that RX2 can be used whenever needed. In other words, we assume that either it uses a subband with a large duty-cycle, or that it is on a different subband for each end-device.

B. Analytic model

We make the three following hypotheses: (i) there is no queuing delay: the gateway has a single frame to send, (ii) uplink and downlink communications do not interfere with each other (due to the use of an opposite chirp [START_REF] Goursaud | Dedicated networks for IoT: PHY / MAC state of the art and challenges[END_REF]), and (iii) we ignore the capture effect: if two end-devices transmit simultaneously on the same channel, both frames are dropped.

Figure 3 shows our Markov chain model for confirmed downlink communications in Class B of LoRaWAN. The Ready state corresponds to the generation of a frame by the gateway. The Beacon state represents the beacon reserved period. The PSlot i states (for i ∈ [1; N ]) represents the ith ping slot, while PSlot N +1 represents a virtual ping slot where no transmission is possible (it is used only for the delay computation). The PWait 1 state represents the random duration between the beacon and the first ping slot. The PWait i state, for i ∈ [2; N ], represents the ping period between the (i-1)-th ping slot and the i-th ping slot. The PWait N +1 state represents the (random) duration between the N -th ping slot and the beacon. The Data 1 i (for i ∈ [1; N ]) represents the transmission of data during the i-th ping slot (that is, Class B transmission). The Data 2 i (for i ∈ [1; N + 1]) represents the transmission of data during the i-th ping period (that is, during the receive window of a Class A transmission). The ACK state, which is final, represents the reception of an ACK from the end-device. The NoAck j i states indicates that no ACK was received after state Data j i , and that a retransmission will occur.

The Ready state is the initial state of our Markov chain. Then, the chain goes to the Beacon state, if the frame was generated during the beacon reserved period, or to a PWait state, if the frame was generated during a ping period. If the frame is generated during the beacon reserved period, the chain goes to the PWait 1 state. Let us now focus on this first ping period, represented by the dashed rectangle in the middle of the figure, as it is similar to all other periods (except the (N + 1)-th period). Two cases can occur: either the gateway waits for the ping slot to occur, which corresponds to PSlot 1 , or a Class A transmission occurs during this ping period, which corresponds to the Data 2 1 state. After PSlot 1 , the data is sent in the Data 1 1 state and is either acknowledged (Ack state) or not (NoAck 1 1 state). After Data 2 1 , the data is either acknowledged (Ack state) or not. When there is no ACK, the chain goes to a PWait j state, possibly several ping periods later, depending on the retransmission delay. Let us now focus on the (N + 1)-th ping period, represented by the dashed rectangle on the left. There is no ping slot, so the PSlot N +1 state goes directly to the beacon reserved period (without Data 1 N +1 state). Let B be the beacon period and N the number of ping slots. Ping period P is (B -5.120)/N . Each end-device transmits with probability τ ∈ [0; 0.01.n sb ]. α is the channel quality. There are n A other activated end-devices in the network. Let us denote by q A = 1τ /(n c • n sb ) the probability that an end-device does not transmit on a given channel.

Probabilities p r,b and p r,wi (for i ∈ [1; N +1]) are the probability that the data is generated during the beacon transmission or during the i-th ping period. Those probabilities depend on the duration of each period: p r,b is equal to the probability that the data is generated during the beacon reserved period (including the guard time), p r,wi is the same for all i ∈ [2; N ], and p r,w1 and p r,wN+1 depend on the expected value of the ping offset, which is chosen randomly within [0; P [. p r,b = 5.120/B, (1) p r,w1 = p r,wN+1 = P/(2B),

(2) ∀i ∈ [2; N ], p r,wi = P/B.

(

Probability p w1,d 2 1 is the probability that the end-device sends a data frame during the ping offset period (which lasts on average P/2), and that this frame is correctly decoded by the gateway. Probabilities p wi,d 2 i , for i ∈ [2; N ], and p wN+1,d 2

N +1
are similar, except that the corresponding ping periods last respectively P and P -P/2 on average.

p w1,d 2 1 = p wN+1,d 2 N +1 = α • τ • P/2, (4) p w1,s1 = p wN+1,sN+1 = 1 -p w1,d 2 1 , (5) ∀i ∈ [2; N ], p wi,d 2 i = α • τ • P, (6) ∀i ∈ [2; N ], p wi,si = 1 -p wi,d 2 i . (7)
Probability p d 1 i ,a , for i ∈ [1; N ], is the probability that the end-device has correctly received the data frame from the gateway (modeled by α), that there is no interference with the ACK sent by the end-device, and that the ACK is correctly decoded by the gateway.

1 1 1 1 1 1 Ready PWaitN+1 Beacon PWait1 PWaitj Data 2 N+1 PSlot1 PSlotN+1 Data 2 1 NoAck 2 N+1 Ack Data 1 1 NoAck 2 1 PWait k NoAck 1 1 pr,w N +1 p r,b pr,w 1 pr,w j p w N +1 ,d 2 N +1 pw 1 ,s1 p w 1 ,d 2 1 p d 2 N +1 ,na 2 N +1 p d 2 N +1 ,a p d 2 1 ,a p d 2 1 ,na 2 1 p d 1 1 ,na 1 1 p d 1 1 ,a pw N +1 ,s N +1
∀i ∈ [1; N ], p d 1 i ,a = α • q nA A • α, ( 8
) ∀i ∈ [1; N ], p d 1 i ,na 1 i = 1 -p d 1 i ,a . (9)
Probability p na 1 i ,wj , for i ∈ [1; N ], is equal to one for a given j due to the sub-band availability under-estimation. The value of j depends on the value of i and of the duration of the timeout. It is computed in Subsection III-C.

Probability

p d 2 i ,a , for i ∈ [1; N + 1],
is the probability that the end-device has correctly received the data frame (modeled by α), that there is no interference with the ACK sent, and that the ACK is correctly decoded by the gateway.

∀i ∈ [1; N + 1], p d 2 i ,a = α • q nA A • α, ( 10
) ∀i ∈ [1; N + 1], p d 2 i ,na 2 i = 1 -p d 2 i ,a . (11)
Figure 4 represents the three cases where the gateway sent the data frame d 2 during a receive window of a frame d 1 and has to retransmit the frame. Case 1 is when the ACK is not received, which yields to a sub-band under-estimation. In this case, the gateway keeps resending the data frame at each ping slot (d ′ 2 and d ′′ 2 ), until it receives the ACK a ′ 2 . Case 2 is when d 2 is not received by the end-device, and the end-device has no other data frame to send. In this case, the gateway uses a ping slot to retransmit the data frame. Case 3 is when the d 2 is not received by the end-device, and the end-device has another data frame d 3 to send. In this case, the gateway retransmits the data frame during RX1 or RX2, and waits for the sub-band to become available for the end-device in order to receive a 2 . All these cases correspond to different timings.

Probability p na 2 i ,wj , for all i ∈ [1; N + 1], is equal to one: after the timeout for the ACK, the gateway is in a ping period, and the retransmission can occur either during the ping slot (see Cases 1 and 2) or a receive window (see Case 3).

C. Computation of expected delay

Recall that the time when the ACK should be received depends on the sub-band availability. This duration depends

d 1 d 1 d 1 d 2 d 2 d 2 d ′ 2 d ′ 2 d ′ 2 d ′′ 2 d 3 a 2 a 2 a 2 a ′ 2 Case 1 Case 2 Case 3 Figure 4.
When the gateway has to retransmit a data frame due to a frame loss, three cases can occur, leading to different timings.

on the network saturation: if τ = 0.01 • n sb , the network is saturated, and the expected delay for the sub-band availability is t of f /2. Otherwise, the delay is

d timeout = p of f • t of f /2,
where p of f = 1-(0.01-τ /n sb )/0.01 and t of f = 99•t f rame . After this duration, the Markov chain is in the j-th ping period (by neglecting the beacon reserved periods), where both values j = 1 and j = N + 1 are equally likely with probability 0.5 if (i + ⌊d timeout /P + 1/2⌋) mod N = 0 (that is, the first and the last ping periods), or j = 1 + ((i + ⌊d timeout /P + 1/2⌋) mod N ) with probability one otherwise.

The expected delay of the confirmed downlink can be computed from our Markov chain model with I • N • D, where I represents the initial state of the chain, N = (1-Q) -1 is the fundamental matrix of our absorbing chain, Q is our matrix without the absorbing states, and D is the column-vector with the delay of each state.

The delays of D for each state are the following. D r = 0. D b = 5.120 as it is the duration of the beacon reserved period (including the guard time). D a = d ack , where d ack is the time on air of the ACK frame. D wi = 0 for all i ∈ [1; N + 1], as we decided to take into account the delay either in the s i state, or in the d 2 i state. This is due to the fact that the Markov chain can reach a Wait i state either at the beginning of ping period i (after the beacon period for instance), or at an arbitrary time during ping period i (after a timeout). D s1 = D sN+1 = P/4 as the duration of the first and the last ping periods is P/2. D si = P/2, for i ∈ [2; N ] as the duration of the other ping periods is P . D d 1 i = d f rame + d subband1 for all i ∈ [1; N ]: indeed, the duration corresponds to the time on air of the data frame plus the average remaining time before a sub-band becomes available for the end-device. d subband1 = d timeout . We also have

D d 2 1 = D d 2 N +1 = P/4 + d f rame + d subband2 and D d 2 i = P/2+d f rame +d subband2 , for i ∈ [2; N ]
, where d subband2 is the average remaining time before a subband becomes available for the end-device, given that the enddevice just sent a data frame. The only difference between d subband1 and d subband2 is that we know that one of the subbands is busy in this case. If n sb = 1, d subband2 = t of f -1d ack (if we assume that RX1 is used by the gateway). Otherwise, d subband2 = d subband1 . Note that P/4 or P/2 is added here as we included in this state the delay of the ping period.

D na 1 i = sym, for i ∈ [1; N ], and
D na 2 i = sym, for i ∈ [1; N + 1],
where sym is the symbol duration. This delay is used by the gateway to detect if the ACK is sent or not. Also note that in our model, d subband1 and d subband2 do not depend on the number of sub-bands: this is because we consider that each sub-band is homogeneously saturated (due to the fact that τ depends on n sb ).

IV. PERFORMANCE EVALUATION

In this section, we present our simulation results. We focused on the EU863-870MHz ISM band regional settings of the standard. ETSI regulations [START_REF] Etsi | Electromagnetic compatibility and radio spectrum matters (ERM); short range devices (SRD); radio equipment to be used in the 25 MHz to 1000 MHz frequency range with power levels ranging up to 500 mW; part 1: Technical characteristics and test methods[END_REF] for the ISM band specify the following four sub-bands (for a bandwidth of 125kHz): sub-band G with 15 channels and 1% duty-cycle, sub-band G1 with 3 channels and 1% duty-cycle, sub-band G2 with 2 channels 0.1% duty-cycle, sub-band G3 with 1 channel and 10% duty-cycle, and sub-band G4 with 1 channel and 1% duty-cycle. In the following, we assumed that all subbands have a duty-cycle of 1%. We varied the number of subbands n sb from 1 to 3, and the number of channels per subband n c from 1 to 3. Given the fact that the gateway has no energy limitation and that its confirmed frames are likely to be important, we assumed that there is no limitation of the number of retransmissions. The link quality is set to α = 0.99.

A. Delay as a function of the data-rate

Figure 5 and Figure 6 show the delay of confirmed downlink frames as a function of the data-rate, for respectively N = 2 and N = 4 ping periods. We assumed here that there are n A = 10 competing nodes.

Figure 5 shows that the data-rate has a large impact on the delay, as expected, since increasing the data-rate reduces the time on air of frames, and thus the time-off duration. The number of sub-bands n sb also has a significant impact: the larger n sb , the smaller the delay, as there are more opportunities to transmit a frame. Increasing the number of channels has a limited impact on the delay, however. Figure 6 shows that the data-rate has a large impact on the delay. However, both n sb and n c have a limited impact. By comparison with Figure 5, it can be seen that increasing the number of ping periods from N = 2 to N = 4 significantly reduced the delay.

n sb = 1, n c = 1 n sb = 1, n c = 3 n sb = 3, n c = 1 n sb = 3, n c = 3
n sb = 1, n c = 1 n sb = 1, n c = 3 n sb = 3, n c = 1 n sb = 3, n c = 3

B. Delay as a function of other nodes

Figure 7 and Figure 8 show the delay of confirmed downlink frames as a function of the number of competing nodes, for respectively N = 2 and N = 4 ping periods. We assumed here that the data-rate is DR0.

Figure 7 shows that the number of competing nodes greatly impacts the delay, especially when the number of channels is low. Indeed, all competing nodes are likely to send frames on the same channel, which results into collisions and retransmissions. Increasing the number of sub-bands from 1 to 3 results into a delay reduction which varies between 25% and 30%.

C. Summary

In practice, the choice of N is a trade-off between the energy consumption of end-devices (as they have to wake up shortly at each ping period) and the delay of downlink frames. It is likely that in many Class B scenarios, N will be larger than 4, which guarantees that a downlink frame can be sent in less than 32s. Thus, according to Figure 6 and Figure 8, we expect n sb and n c to have a limited impact on the delay of Class B downlink frames, while the data-rate and n A have a significant impact on the delay.

V. CONCLUSION

LoRaWAN is a recent MAC standard from the industrial community for long range, low-power communications. In this paper, we focus on the delay of frames that have to be acknowledged by end-devices. Consequently, we focus on Class B of the standard, which enables downlink communications with bounded delay. We first discuss some limitations of the current version of the standard. Then, we propose a Markov chain model for the delay. Our simulation results show that the data-rate and the number of sub-bands have a significant impact on the delay. Moreover, when the number of competing nodes is large, a large number of channels significantly decreases the delay.

Figure 1 .

 1 Figure 1. Class B of LoRaWAN. Dark rectangles represent transmissions, and white rectangles represent receptions.

Figure 3 .

 3 Figure 3. Markov chain model for Gateway using class B.

Figure 5 .

 5 Figure 5. Delay as a function of the data-rate, for N = 2 ping periods. Increasing the data-rate and n sb significantly reduces the delay.

Figure 6 .

 6 Figure 6. Delay as a function of the data-rate, for N = 4 ping periods. Increasing the data-rate significantly reduces the delay.

  seconds)n sb = 1, n c = 1 n sb = 1, n c = 3 n sb = 3, n c = 1 n sb = 3, n c = 3

Figure 7 .

 7 Figure 7. Delay as a function of the number of competing nodes, for N = 2 ping periods. Increasing the number of competing nodes or reducing the number of sub-bands significantly increases the delay.

Figure 8

 8 Figure8shows similar results as Figure7. Again, increasing the number of sub-bands from 1 to 3 results into a delay reduction which varies between 18% and 22%. By comparison with Figure7, it can be shown that increasing N significantly reduces the delay.

Figure 8 .

 8 Figure 8. Delay as a function of the number of competing nodes, for N = 4 ping periods. Increasing the number of competing nodes or reducing the number of sub-bands significantly increases the delay.

  Figure2. When the gateway estimates the timeout for an ACK from an enddevice, it is not possible for the gateway to receive another transmission from this end-device during the timeout.

	0 0 0 1 1 1 d 1	00 00 00 11 11 11 d 2	1 00 00 00 11 11 11 a 1	0 0 0 1 1 1 d 3	0 0 0 1 1 1 d 4	a 2
	0000000 0000000 1111111 1111111 00000000 00000000 11111111 11111111	00 00 11 11

Acknowledgment: This work has been partially funded by the Clervolc laboratory of excellence.