Keywords: Partage de medium, Contention, allocation localisée, protocole d'accès au canal radio, compromis capacité/énergie

Cascading Tournament Algorithm: Low Power, High Capacity Medium Sharing for Wireless Sensor Networks

Résumé : Les protocoles d'accès au medium radio existants pour réseaux de capteurs sans-fil réduisent l'activité de la radio afin d'améliorer la durée de vie du réseau, et ce, au prix d'une diminution de la capacité du réseau.

Ces protocoles sont peu adaptés pour les réseaux de capteurs contraints en énergie qui doivent supporter des trafics spatialement et temporellement hétérogènes. Ce rapport propose un algorithme d'allocation multi-ressources et décrit son implémentation sous forme de protocole de contrôle d'accès (MAC) au canal radio pour réseaux de capteurs. L'algorithme, appelé Cascading Tournament (CT), est un algorithme combiné de gestion de la contention/allocation localisé, dynamique et localisé. Il se repose sur des itérations de tournois en cascade pour allouer une pluralité de ressources à une pluralité de vainqueurs. CT-MAC est une implémentation de CT en tant que protocole MAC. En allouant plusieurs canaux logiques à chaque compétition, CT-MAC améliore la capacité du réseau pour un cycle d'endormissement donné ou diminue la consommation énergétique de la couche MAC pour une capacité du réseau donnée. Une étude complète par simulation montre l'intérêt de CT-MAC dans des scénarios de voisinage unique et multi-sauts. Ces simulations ont permis le calcul de métriques de performances pertinentes: consommation énergétique, capacité du réseau, délai et retransmissions. CT-MAC offre un compromis entre capacité du réseau et efficacité énergétique qui n'a pas de précédent. Il se présente donc comme un candidat sérieux pour les réseaux de capteurs contraints en énergie qui doivent supporter des trafics hétérogènes. Nos simulations ont montré que CT-MAC surpasse le protocole de l'état de l'art SCP-MAC.

Introduction

The network lifetime is a critical issue for commercial and industrial deployments of Wireless Sensor Networks as it determines their economic viability. Energy efficient Medium Access Control (MAC) protocols, e.g. [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF], [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF], [START_REF] Bachir | Micro-frame preamble mac for multihop wireless sensor networks[END_REF], [START_REF] Buettner | X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks[END_REF], [START_REF] Ye | Ultra-low duty cycle mac with scheduled channel polling[END_REF], have been proposed to meet lifetime requirements of such networks.

However, the energy savings achieved by aggressively duty-cycling the radio come at the expense of network capacity. Existing localized competition algorithms for MAC protocols allocate a single resource. Some that allocate multiple resources do exist, however they either rely on non-localized reservation algorithms, e.g. [START_REF] Pister | TSMP: Time synchronized mesh protocol[END_REF], or require to iterate localized competition algorithms for each resource, e.g. [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF]. In either case, allocating multiple resources comes at a significant energy cost.

Sensor networks must handle heterogeneous traffic loads, either in the temporal sense (bursty traffic) or in the spatial domain (funneling effect close to the sinks), while being drastically energy efficient. This is even more drastic in "Smart City" [START_REF] Dohler | Routing requirements for urban low-power and lossy networks[END_REF] applications where multiple applications are deployed on a single sensor network, e.g. pollution monitoring, water and gas metering, parking spots management etc. Traditionnally, in such energy-constrained networks, duty-cycle is adjusted to meet lifetime requirements and to support a periodic traffic load. Heterogeneous traffic loads may therefore saturate the network capacity and causes congestion, packet loss and significant delays. A naive solution would consist in setting the active time according to the maximum traffic load of the network, i.e. to match the network capacity to the traffic peak load. This solution is unsuitable when the traffic load is expected to vary widely. Adaptive duty-cycle MAC protocols may address the specific issue of the heterogenenous traffic loads but still incur energy costs for predicting/adapting the duty-cycle to traffics bursts.

This paper describes a novel localized medium-sharing algorithm: Cascading Tournament (CT) and its implementation as a Medium Access Protocol (CT-MAC). CT is a joint contention/allocation algorithm that both grants access to a multiplicity of winners and allocate them independant resources. In this paper, the ressources are logical channels obtained by partitioning the physical channel, e.g. in time (TDMA), frequency (FDMA) or code (CDMA).

Thanks to the multiple-ressource allocation feature of CT, CT-MAC supports higher traffic loads at a given duty-cycle than single-logical channels protocols do, e.g. [START_REF] Ye | Ultra-low duty cycle mac with scheduled channel polling[END_REF], [START_REF] Bachir | Micro-frame preamble mac for multihop wireless sensor networks[END_REF] and [START_REF] Buettner | X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks[END_REF]. This allows CT-MAC to operate at lower dutycycles and therefore to save energy at lower loads. Furthermore, by factoring the allocation of multiple channels in one large competition, CT-MAC reduces the allocation energy cost per channel allocated.

Contrary to existing multiple logical channels protocols, e.g [START_REF] Pister | TSMP: Time synchronized mesh protocol[END_REF], [START_REF] Coleri | Pedamacs: Power efficient and delay aware medium access protocol for sensor networks[END_REF], CT-MAC is a localized protocol and it does not rely on a priori traffic pattern assumptions to operate. CT-MAC therefore adapts to heterogeneous and unpredictable traffic patterns.

A performance evaluation through extensive simulations assesses the benefits of CT-MAC over the existing state-of-the-art SCP-MAC protocol [START_REF] Ye | Ultra-low duty cycle mac with scheduled channel polling[END_REF].

Simulation results outline the following main properties of CT and CT-MAC:

• CT is close to optimal in terms of logical channels usage, i.e. medium capacity.

• When using 32 logical channels, CT-MAC provides a capacity equivalent to that of SCP-MAC operating with a wake-up cycle 32 times faster while consuming up to 5.5 times less energy. However, this comes at the expense of some extra delay.

• CT-MAC outperforms SCP-MAC in terms of capacity and delay when operating at the same wake-up cycle period.

This paper makes three main research contributions. First, it describes a novel ressource sharing algorithm, Cascading Tournament (CT), that efficient allocates multiple resources. Second, it proposes an implementation of CT as a multi-channel MAC protocol, CT-MAC, specifically designed for energy constrained, realistic Wireless Sensor Networks. Third, it compares SCP-MAC to upper theoretical bounds and provides a fair and complete comparison against the state-of-the-art SCP-MAC protocol.

The rest of this paper is organized as follows: section 2 underlines the design objectives and requirements that outlined our proposal, section 3 states assumptions made in this study, section 4 reviews existing medium sharing algorithms, section 5 exposes CT design and CT-MAC implementation and section 6 and 7 presents simulations that assess the benefits of CT and CT-MAC. Finally, sections 8 and 9 unveils future work and summarizes this article.

Design Objectives and Requirements

Energy efficiency

• CT's energy cost to allocate multiple logical channels must be less than that of repeated existing contention algorithms allocating on logical channel each.

• CT must be distributed and must solely rely on local information, i.e. it must be a localized algorithm, because control messages exchange cost is considered prohibitive.

Adaptativity

• CT must not rely on a priori or dynamically discovered traffic pattern assumptions. It must self-adapt to fast-varying, bursty traffic.

• CT must cope with the traffic load heterogeneity of a collection network.

• CT-MAC's dimensioning must not depend on network topology, e.g. network diameter or connectivity.

Fairness

• CT must grant a fair medium access to all nodes.

INRIA

Requirements

Requirements to compare CT to existing contention algorithms have been derived from this set of objectives:

r heterogeneous the contention algorithm must cope with the spatially heterogeneous load of a collection network.

r dimensioning dimensioning of the contention algorithm must not depend on network topology, e.g. network diameter or connectivity.

r localized the contention algorithm must exclusively rely on local information and operate in a decentralized manner.

r assumption the contention algorithm must not depend on traffic pattern assumptions.

r adaptability the contention algorithm must self-adapt to fast-varying, bursty traffic.

r f airness the contention algorithm must grant a fair medium access to all nodes.

Assumptions

Most Wireless Sensor Network applications strongly rely on network synchronization. For example, in metering applications as in urban networks [START_REF] Dohler | Routing requirements for urban low-power and lossy networks[END_REF] or industrial networks [START_REF] Pister | Industrial routing requirements in low-power and lossy networks[END_REF], data relevance is often limited to a given time-frame and outdated packets are dropped for energy and congestion considerations. Such mechanisms compel packet sources and all the forwarding nodes to share a common time reference so as to compare timestamps to their clock, thus requiring network synchronization. Network synchronization also allows for various optimizations such as synchronous sleep schedules that shorten wake-up guard times or time-spread transmission schedules for congestion mitigation. Therefore, we will make the assumption that a network time synchronization mechanism such as [START_REF] Sommer | Gradient clock synchronization in wireless sensor networks[END_REF] or [START_REF] Maróti | The flooding time synchronization protocol[END_REF] is operating on the network.

Related work

Access control algorithms can be classified into three categories regarding the way nodes compete to access the medium: pre-reservation, random and hybrid access.

Pre-reservation access algorithms

Pre-reservation access relies on pre-established schedules of node emissions such as in [START_REF] Pister | TSMP: Time synchronized mesh protocol[END_REF] [8]: each wake-up period is dedicated to a specific communication providing it with a collision free logical channel. This access method allows for optimal support of periodic traffic loads. However, these algorithms adapt poorly to unpredictable traffics bursts and to network topology alterations. Indeed, each variation requires a new schedule, which implies energy cost and possibly outage during the dissemination of the new schedule.

Therefore, these algorithms meet the key requirement r heterogeneous . r f airness requirement may also be met, although it would require to schedule transmission for all nodes in the network which violates r dimensioning requirement. Finally, such algorithms do not meet r localized , r assumptions and r adaptability requirements.

Random access algorithms

Random access relies mostly on CSMA algorithms and can also be sub-divided into two sub-categories: unsynchronized and synchronized algorithms.

Unsynchronized algorithms

In unsynchronized algorithms such as described in [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF], [START_REF] Bachir | Micro-frame preamble mac for multihop wireless sensor networks[END_REF] and [START_REF] Buettner | X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks[END_REF], energy savings are achieved by a channel sampling mechanism. The sampling frequency is the same for all the nodes while the instants at which sampling occurs are different accross nodes. The competition algorithm is similar to those used in always-on radio protocols: Aloha, CSMA, etc. It consists in an optional random backoff to spread channel access attempts, followed by a Clear Channel Assessment (CCA). Such mechanisms cannot handle more than one packet per duty-cycle. Therefore, the wake-up period must be tuned according to the maximum expected traffic load or the network may face congestion, packet loss and/or delay issues. These preamble-sampling mechanisms also require sending a preamble prior to the packet to transmit. This preamble is either longer than the sampling period [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF] or composed of a strobe of small frames [START_REF] Bachir | Micro-frame preamble mac for multihop wireless sensor networks[END_REF], [START_REF] Buettner | X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks[END_REF]. Its goal is to tell the destination node that a packet will be sent. In any case, such preamble holds the channel for a long time, which is detrimentatl to network capacity and delay. Therefore, these mechanisms do not meet the r heterogeneous and r adaptability requirements while respecting r assumptions , r localized and r dimensioning .

Synchronized algorithms

Synchronized algorithms benefit from a shared knowledge of time by setting rendezvous times to perform the channel competition. A widely-used algorithm in energy efficient MAC protocols relying on nodes synchronization consists in the usage of a fixed contention window to grant access to the medium as described in [START_REF] Jamieson | Sift: A MAC protocol for event-driven wireless sensor networks[END_REF], [START_REF] Zakhia | CONTI: Constant-time contention resolution for WLAN access[END_REF] and [START_REF] Galtier | Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks[END_REF]. The fixed contention window algorithm involves a fixed-size time frame subdivided into K time slots. Nodes competing to access the medium, called contending nodes, choose one or more of these slots and mark them using a busy tone. When not transmitting, nodes perform CCAs. The decision to access the medium is computed locally at each node based on slot choices and CCAs returns.

These algorithms inherently meet r assumptions , r localized and r dimensioning requirements. r f airness requires all nodes to share the same algorithm parameters and independent successive channel access attempts, which are reasonable assumptions. However, existing algorithms lead to a binary decision, i.e. to access or to not access the medium. Such mechanisms can only allocate a single logical channel and thus need to be repeated for each logical channel, which is inefficient and not implemented in practice. As a result such algorithms do not INRIA adapt efficiently to the traffic variations that occurs in a collection network and do not meet r heterogeneous and r adaptability .

As described in section 5, CT use fixed contention window to manage the channel access. A description of existing fixed contention window algorithms is therefore provided here.

Single slot choice algorithms In congestion algorithms as in SIFT [START_REF] Jamieson | Sift: A MAC protocol for event-driven wireless sensor networks[END_REF], each node n i chooses a slot t i and marks it with a busy tone. Node n i listens to slots preceding t i . The first nodes to mark a slot gains access to the medium while the others retire until the next access competition.

Longest burst algorithms

The HIPERLAN [START_REF]Standard. HIgh PErformance Radio Local Area Network(HIPERLAN) Type 1; Functional Specification[END_REF] protocol defines a congestion resolution algorithm based on a longest burst policy. Contending nodes n i choose an integer number l i in the interval [1,K] where K is the size of the contention window. l i represents the size of n i 's burst. Node n i marks the l i first slots of the contention window with a busy tone. At the end of its burst, node n i performs a CCA. If the CCA returns a positive, then n i gains access to the medium, otherwise n i retires until the next competition. In other words, nodes with the longest burst are granted access to the medium.

Binary countdown algorithms

The CONTI protocol [START_REF] Zakhia | CONTI: Constant-time contention resolution for WLAN access[END_REF] and its improvment [START_REF] Galtier | Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks[END_REF] consider the K slots of the contention window as K rounds of competition. At each round, nodes n i mark the current slot with a busy tone with a probability p and perform a CCA with probability 1p. If n i 's CCA is negative then n i retires until the next competition by not participating in the following rounds. Nodes that haven't retired by the end of the contention window gain access to the medium.

All those algorithms inherently meet r assumptions , r localized and r dimensioning requirements. r f airness requires all nodes to share the same algorithm parameters and independent successive channel access attempts, which are reasonable assumptions. However, existing algorithms lead to a binary decision, i.e. to access or not to access the medium. Such mechanisms can only address a single logical channel and thus need to be repeated for each logical channel. Therefore, existing energy-efficient MAC protocols considered such overhead as unaffordable. As a result such algorithms do not adapt efficiently to the traffic variations that occurs in a collection network and do not meet r heterogeneous and r adaptability .

Hybrid algorithms

Hybrid algorithms as in [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF], combine both reservation and random access mechanisms. Logical channels are assigned to requesting nodes based on traffic predictions as done in reservation based access mechanisms and random access mechanisms take place when a logical channel is left unused by its legitimate owner. Such mechanisms provide a more adaptive solution to variable traffic patterns than pure reservation based algorithms. However, it still requires establishing and updating a communication schedule. Therefore those mechanisms suffer from the same limitations as pure reservation algorithms do. These

Existing solutions and adequacy to requirements

As previously seen, existing reservation based access algorithms (the hybrid ones included) do not meet r localized , r assumptions and r adaptability . Random access algorithms fail to meet r heterogeneous . Therefore, none of the reviewed algorithms satisfies all of our requirements, thus prompting for a new algorithm.

Cascading Tournament Algorithm

Core algorithm

The Cascading Tournament Algorithm core algorithm consists in a 3-tiers access competition algorithm and a data transmission window. Nodes competing to access the medium execute all tiers while others only execute tier 3.

Tier 1

This section refers to fig. 1 for details. Tier 1 involves a contention window: CW 1 . This contention window is divided into K 1 time slots. Each slot is long enough to perform a radio state transition Tx/Rx or Rx/Tx and a Clear Channel Assessment. Successive time slots are spaced by a time guard to prevent synchronization issues. See fig. 2 for details.

• Nodes participating in tier-1, N i∈1..n , first randomly choose one of the K 1 slots t i∈1..K1 and initialize two counters, c rank and c total to 0. c rank purpose is to store the number of occupied slots preceding t i while c total stores the total number of occupied slots.

• Participating nodes N i∈1..n perform CCAs in slots preceding t i and increment c rank and c total values for each negative CCA (channel is busy). • Nodes N i∈1..n eventually send a busy tone (non coherent transmission) in the t i slot after switching their radio to TX and incrementing c total .

INRIA

• Then, these nodes switch the radio to RX and perform CCAs in the t j∈i+1..K1 slots if any. Only the c total counter is further incremented for each new negative CCA. If c total reaches C log , it is no longer incremented for new negative CCAs.

• At the end of tier-1, participating nodes know the number of occupied slots prior to their own: c rank , and the total number of occupied slots: c total (capped at C log ). Nodes whose counters verify c rank == c total == C log cancel their participation to the channel access competition.

The others nodes then compete for the c th rank logical channel in the c th rank tier-2 contention window.

Tier 2

This section refers to fig. 3 for details. Tier 2 involves C log contention windows: CW 2,j∈0..(C log -1) of size K 2 slots.

• Each slot t i∈1..K2 consists in a competition round similar to CONTI [START_REF] Zakhia | CONTI: Constant-time contention resolution for WLAN access[END_REF], i.e. nodes n i mark the current slot with a busy tone with a probability p and perform a CCA with probability 1p.

• If n i 's CCA is negative then it cancels its participation to the current contention window and schedules a new competition in the first "free" CW 2,j window if any. If no "free" CW 2,j is found then n i renounces to send its packet in the current period. A CW 2,j is considered "free" when c total value is strictly less than j. Nodes that won access to a logical channel j send an advertisement packet in the j st advertisement slot and listen to remaining slots. Other nodes listen to all slots. When a node receives an advertisement in the ADV j slot and is the destination, it schedules a radio switch to RX in the j th data slot to receive the data.

Transmission window

Sending nodes transmit their data packet in the data slots and then switch their radio to RX, waiting for a data acknowledgment packet. The data packet does not contain a full MAC header but only the packet id and the data itself. When a node successfully receives a data packet, it sends back a data acknowledgement. The data acknowledgment contains only the packet id. If a data acknowledgment is received, sending nodes may dispose of the sent packet and free the packet buffer. (1) As described in 5.1, N 1..5 choose a random slot in the tier 1 contention window. In this scenario, Nodes N i ∈ 1..5 compete to access the medium and respectively choose slots 3, 1, 5, 3, 4.

Illustration of CT algorithm: detailed chronogram

• N 2 performs a busy tone in slot 1, its c rank is therefore 0. N 2 then increments c total to 1. N i∈{1..6}\{2} increment their c rank and c total counters to 1.

• There is no busy tone in slot 2. Neither c rank nor c total is incremented.

• N 1 and N 4 send a busy tone in slot 3, their c rank value is therefore 1. N i∈{1..6}\{1,2,4} increment c rank and c total . N {1,2,4} increment c total . • N 5 performs a busy tone in slot 4. It's c rank is therefore 2. N 3 increments both c rank and c total . Its c rank and c total values verify c rank == c total == C log , N 3 therefore retires of the medium access competition and turns its radio off. N i∈{1..6}\{3} increment c total , which reach C log . N i∈{1..6}\{3} thus cancel CCAs scheduled in slot 5 and 6.

(2) N 2 competes in the first tier 2 contention window: CW 2,0 . All CCAs performed by N 2 returns are positive. N 2 therefore decides to send an advertisement in the first advertisement slot.

(3) N 1 and N 4 compete in the second tier 2 contention window: CW 2,1 . In the first 3 slots, N 1 and N 4 perform the same actions therefore CCAs returns are positive. In slot 4, N 1 performs a CCA while N 2 send a busy tone. N 1 's CCA return is thus negative and N 1 cancels its participation to this contention window. Since c total value is equal to C log , N 1 sees no "free" tier-2 contention window and retires of the competition. N 4 finally decides to send an advertisement in the second advertisement slot.

(4) Similar to (2). N 5 decides to send an advertisement in the third, and last, advertisement slot.

(5) N 2 sends an advertisement to N r . Upon reception of the advertisement packet, N r schedule a radio wake-up on state Rx at the first data slot.

Other nodes ignore the advertisement. Similarly N 4 and N 5 send their advertisement packets in the 2 nd and 3 rd advertisement respectively. N r and N 6 schedule radio wake-up at the 2 nd and 3 rd data slots respectively.

(6) N 2 , N 4 and N 5 send the data packets and N r and N 2 send back acknowledgments.

Optimizations

Depending on the traffic load and constraints, CT-MAC implementation may includes the following optimizations.

Advertisement acknowledgment

When receiving an advertisement, a destination node may send back an acknowledgment to the sender. This optimization eventually prevents the sender to waste the necessary energy to send the data payload at the cost of sending an acknowledgment by the receiver for each packet. The trade-off lies in the ratio of the respective costs to send a data payload and an acknowledgment and in the channel error rate.

Adaptive listening

This section refers to fig. 5 for details. CT Core algorithm specifies that nodes listen to all C log advertisement slots. In case of light traffic conditions, this causes unwanted idle listening and therefore energy wastes. The adaptive listening optimization consists in a listening time-out. When nodes wake up to probe the channel for activity, they first schedule a listening period. This listening period consists in s adaptive advertisement slots for receiving-only nodes. Nodes that send advertisements schedule a listening period of s adaptive + s latest_slot When an advertisement is received or an advertisement slot is found busy, nodes extend the listening period to listen to the next s adaptive slots. The time-out is thus postponed to s current + s adaptive if it's not already scheduled later. This optimization helps preventing energy wastes due to the idle listening phenomenon. However, it may also induce early radio OFF switches and eventually make nodes unavailable for advertisements and data reception.

INRIA

Multiple channels access per node

This discussion relates to fig6.

The notion of "free" logical channel has been introduced in 5.1. When such logical channels exist, i.e. c total < C log , nodes that have multiple packets to send are given the right to compete for these "free" logical channels. Such nodes may therefore compete in the corresponding tier 2 contention windows CW 2 , j ∈ c total ..C log .

This optimization rely on the assumption that the communication stack buffer can store more than one packet, which is not always true, e.g. the Contiki operating system [START_REF]The contiki operating system[END_REF]. When this assumption is verified, this allows bottleneck sensor nodes to use more data slots and thus to handle higher traffic loads, which is particularly useful for nodes close to the network sink node.

Channel reuse

Section 5.2 shows that when multiple nodes compete in a tier 2 contention window, some of them will likely retire from the competition, i.e. when a node performs a negative CCA. When operating in a multi-hop wireless network, such situations may lead to unused data slots in given neighborhoods. Fig. 7(a) and Fig. 7(b) expose such a scenario. In this case, node 2 obtains the first logical channel. Node 1 and 4 competes for the second logical channel. Node 4 wins Figure 6: Multiple channels access per node optimization access to this channel in the tier 2 second contention window CW 2,1 while node 1 cancels its participation at slot 1. Therefore, if no channel reutilization method is used, the second logical channel is seen empty by node 3. One method to efficiently reuse these channels is that nodes schedule CCAs at the median slot in all tier-2 contention CW 2,j windows where they would not participating if strictly following the core algorithm. If the CCA is negative then these nodes do not further participate to the window (1). However, if the CCA is positive then the nodes may compete in the second half of the window for the associated logical channel [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF]. In order to guarantee that "legitimate" nodes, i.e. nodes that have chosen the CW 2,j window during tier 1, have priority over the "opportunistic" nodes, "legitimate" nodes that have not canceled their participation before the median slot, send a busy tone in the median slot. See. fig. 7(b) for details. This optimization helps maximizing the channel usage and thus the network throughput. However, it increases the collision probability for packets sent in these reused logical channels as their tournament access process relies only on the second half of the corresponding CW 2,j windows.

Evaluation

This section evaluates the CT algorithm and its implementation, CT-MAC. For comparison purposes, results are also provided for SCP-MAC [START_REF] Ye | Ultra-low duty cycle mac with scheduled channel polling[END_REF]. SCP-MAC is an ultra-low duty-cycle MAC protocol designed towards energy savings and it stands out as one of the most energy efficient protocol for Wireless Sensor Networks.

First, this section provides simulation results for the main CT-MAC (without optimizations) in a single-hop scenario with a perfect channel. This scenario Second, we simulated CT-MAC with optimizations in multi-hop scenarios. These results show the behavior of CT-MAC in a data collection network, i.e. with a converge-cast traffic, when facing a non-perfect channel. Throughput, power consumption, delay and retransmission rate results are provided and discussed.

Simulation settings

Simulations are conducted on the WSNET network simulator [START_REF] Elyes | Impact of the physical layer modeling on the accuracy and scalability of wireless network simulation[END_REF] 1 lists relevant simulation parameters. CT-MAC operates on a 10 s wake-up/sleep cycle and allocates 32 TDMA-based logical channels. The 10 s duty-cycle is inspired from existing commercial urban sensor deployments [START_REF] Dohler | Routing requirements for urban low-power and lossy networks[END_REF] while the number of logical channels has been chosen such that packets up to 80 bytes (including physical and routing headers) can be handled without fragmentation, which we deem sufficient for collection networks. The reference protocol, SCP-MAC, is simulated with both a 10 s and a 312.5 ms wake-up period, i.e. 1 and 32 operation cycles every 10 s. As verified in 6.2, this means that we compare our CT-MAC with one version of SCP-MAC operating at the same duty-cycle and with another version of SCP-MAC operating at the same theoretical capacity. In this paper, we will refer to these two specific versions of SCP-MAC as SCP-MAC(10 s) and SCP-MAC(312.5 ms). For SCP-MAC, we use the values K 1 = 32 and K 2 = 12 often seen in the litterature. To be fair in our comparison, we have implemented the obvious improvement to SCP-MAC that consists in using a CONTI algorithm in its tier-2 contention window, instead of a uniform backoff. Our algorithms therefore only differ in the tier-1 algorithm. Both CT-MAC and SCP-MAC use a uniform probability distribution for ther tier-1 contention window. For CT-MAC, we naturally picked the same value K 2 = 12 as for SCP-MAC. Because we compare CT-MAC to versions of SCP-MAC with a sleep period spanning more than an order of magnitude, we expect the population of contending nodes per CT-MAP period to be generally larger than that of SCP-MAC(10 s). We therefore picked K 1 = 128, which brings the collision occurence low enough that other practical factors such as channel error rate will dominate. Chosing a lower K 1 reduces the protocol overhead but increases the collision rate, and vice-versa. Optimizing K 1 , K 2 , C log for given application requirements (traffic load, collision rate, etc) is left INRIA as future work. The simulated time is a fixed 10 000 s. As an example, this means that a network of 100 nodes each generating 0.01 packet/second processes about 10 000 packets during the simulation run. Furthermore, for the multihop scenarios described in 6.3.1, one simulation is run on each of four different routing topologies of the same physical network, and results are averaged across these four simulation. In this scenario, n nodes share a common medium and compete to send packets to the sink node N r . All nodes are in one another's radio range. The channel is error-free. Packets that overlap in time generate collisions and are all lost. All the nodes generate one packet every wake-up period of CT-MAC and SCP-MAC(10s), i.e. every 10 s. They therefore all compete in each and every period. We ran a range of simulations to sweep values from 1 to 500 for n.

Single-hop scenario

Fig. 8 depicts the average throughput, computed as the rate of packets successfully received at the sink N r divided by the number of source nodes, averaged over the simulation time. Results are provided for four scenarios: CT-MAC, SCP-MAC and, in order to serve as upper theoretical bounds, a perfect algorithm for a medium comprising 32 logical channels and a perfect algorithm for a medium providing 1 single logical channel. The graph confirms our intuition that a globally shared medium is unable to deliver the requested load of 1 packet per source node per wake-up period when the number of source nodes exceeds the number of channels available, hence the sharp knee in the CT-MAC curve for n close to 32 and the hyperbolic decay in the right part of the graphs.

Both CT-MAC and SCP-MAC(10s) perform near-optimally, considering their respective number of logical channels. In both cases, the distance to the optimal value is due to residual collisions stemming from identical decisions being taken at different nodes. For example, two or more nodes send their advertisements in the same slot (with CT-MAC), or two nodes send their packets at the same time Because CT-MAC is near-optimal in allocating C log logical channels, it provides a network capacity up to C log times that of SCP-MAC operating at the same wake-up period. Conversely, at same network capacity, CT-MAC can use a much longer wake-up period, providing significant energy savings when and where the traffic is low. This will be verified in 6.3.5. This, however, comes at the cost of higher delays, as shown in 6.3.7.

Multiple-hops scenarios

Physical and routing topologies

This set of scenarios involves 3 physical topologies. Each physical topology consists in n source nodes, n ∈ {48, 80, 120}, and one sink node N r . The nodes are placed on a fixed pitch grid centered on N r . Topologies with more nodes span a larger physical area, with an identical spatial density. On each physical topology, we ran four times a distance-vector routing algorithm to build four different (logical) routing topologies, over which below-mentionned results were averaged.

We define ldsit, the logical distance of a node, as the number of routing hops from the node to the sink. The sink node N r has an ldist of 0 while nodes at x hops from N r get an ldist value of x. Fig. 9 depicts an example of such a topology.

Offered load

The n nodes all send their packets to the sink N r , potentially over multiple hop routes. Over multiple simulations, their packet generation interval is varied from 1000 s downto 34 s, i.e they all uniformely generate from 0.001 to 0.029 packets per second. Compared with the contention cycle of 10 s of CT-MAC and SCP-MAC(10 s), this means that, at the highest simulated offered load, each node injects a packet into the network about every third contention cycle.

INRIA

Performance metrics

This study evaluates the protocols based on the following performance metrics: Throughput As in 6.2, we define the throughput as the aggregate rate of nonduplicate packets that are received at the sink node N r , divided by the number of source nodes. This is averaged over the full simulation time.

Power consumption

The power consumption is the total power expenditure of all nodes during the simulation, divided by the number of nodes. This is averaged over the full simulation time. For further insight, we actually compute and display this metric for each ldist bin, i.e. we average and display the average power consumed by the nodes at ldist = 1 separately from the average power of the nodes at ldist = 2, etc. Indeed, the amount of traffic is significantly different across successive network rings, and it reflects in the power consumption. The consumption of edge nodes in low traffic scenarios depicts the base energy consumption of the protocol. Indeed, nodes rarely compete to access the medium and therefore they consume most of their energy probing it for incoming transmissions.

Traffic delay

The traffic delay is the difference between the time a packet was received at the sink node N r and the time it was created at the application layer of the source node. This delay is higly influenced by the sleep cycle period and the network capacity. For the same reason as mentioned above, we display average Traffic delays for each ldist bin.

Data retransmission rate Data retransmission rate is the rate of data packets that have been sent by a given node but not acknowledged by the on-link destination (not the final destination!), whether these packets originated at that node or were simply forwarded. We also display data retransmission rates averaged over each ldist bin of the sending nodes.

Throughput

This section discusses Fig. 6.3.4, which represents the average rate of nonduplicate packets received at the sink node N r per source node, versus the load offered by each node, under our three different MAC protocols and on three different network sizes. For all three network sizes, CT-MAC (with a 10 s sleep-cycle) and SCP-MAC with a 312.5 ms cycle offer a similar network-wide throughput: it increases linearly with the load, then falls off when the network gets saturated. The difference between CT-MAC and SCP-MAC(312.5ms) doesn't exceed 5%. All nodes don't fare equally well with respect to saturation, depending of their position in the network, but space limitations prevent us from presenting further details here. Clearly, CT-MAC hugely outperforms SCP-MAC(10 s). This is consistent with the single-hop simulations of section 6.2.

In Fig. 6.3.4, the 95% confidence interval, not displayed for clarity, never exceeds a width of 4% of the value plotted.

Power consumption

The energy consumption results are shown in figures 6.3.5 , 6.3.5 and 13 times as is the case with SCP-MAC, the nodes running CT-MAC only listen to the first few s adaptive slots of the announcement phase. At the other extreme, let's compare CT-MAC with SCP-MAC(10 s). Fig. 13 is the counterpart to Fig. 12(a) and 11(a). The energy consumption is much less but saturation appears at very low loads. For loads approaching zero, CT-MAC consumes 3.5 times more than SCP-MAC(10 s). This is the price to pay for the 32x flexibility in network capacity. With a few simple calculations, we can conclude that our protocol CT-MAC consumes at very light loads about the same as SCP-MAC with a 1.8s sleep period, yet it provides a capacity 5.5x greater when and where it is needed.

For legibility, the 95% confidence intervals are not plotted on the graphs, but are discussed here. For CT-MAC and SCP-MAC(312.5 ms), their width is always less than 8% of the plotted value, for all data points. For high loads, SCP-MAC(10 s) shows an interval width up to 27% of the mean value at the sink node (ldist = 0). In high load scenarios, less packets indeed reach the sink node due to congestion and packet collisions, and the number of reception varies more significantly. Consumption values for other ldist values are less affected since they are averaged on all nodes sharing the same logical distance. The 95% confidence interval width is therefore smaller, less than 10% of the plotted values.

Data retransmission rate

Figures 14(a) and 14(b) show the data retransmission experienced at nodes in the 120 nodes network. In the saturated regime, CT-MAC boasts only about half the data retransmission rate of SCP-MAC(312.5 ms) at nodes belonging to the first ring. This is because , in the saturated regime, all nodes always contend for the medium. CT-MAC benefits from its wider tier-1 contention window (128 slots compared to 32 for SCP-MAC). Conversely, at low offered loads, SCP-MAC has a lower retransmission rate. The explanation is that, at low loads, nodes only seldom contend for the medium. SCP-MAC organizes thirty-two separate contests spread over time whereas CT-MAC organizes just one contest with 32 times as many contenders. This 32x downsampling of the contender population with SCP-MAC turns out to be more beneficial than the wider tier-1 contention window of CT-MAC. Compared to SCP-MAC(10 s), the downsampling effect does not kick in, and CT-MAC at very low loads exhibits Since the channel model is the same for CT-MAC and SCP-MAC simulations, the difference in the retransmission rates directly relates to the difference in the number of collisions, which are direct effects of the underlying algorithms. Another source for retransmissions is the adaptive listening optimization described in 5.3.2: if s adaptive is too small, receiver nodes might stop listening for advertisements in the announcement phase, therefore ignoring ensuing transmissions. Our s adaptive value for this study was adjusted empirically. Its optimization is still to be explored. The 95% confidence interval on data retransmission rates varies significantly from one scenario to another. We observe a maximum interval confidence width of up to 97% of the mean value (ldist = 5 for 120 nodes) with an average width of 24% of the mean value for all scenarios and ldist. As shown in figures 14(a) and 14(b), retransmissions are rare events (at most 50 retransmissions on all ring-1 nodes over 10 000 s for CT-MAC), and the large confidence intervals are related to the smallest numbers of retransmissions (< 5retransmissions). This comforts our confidence in our results, which are accurate enough to back our claims above.

Traffic Delay

Figures 15 and 16 illustrate the traffic delays observed in simulation on 48 and 120 nodes networks. SCP-MAC(312.5 ms) processes the transmission requests thirty-two times in a 10 s interval, while CT-MAC regroups those requests for one more sophisticated allocation mechanism every 10 s. It therefore comes as no surprise that, at low loads and with packets generated at random instants, one hop with CT-MAC requires about 10 seconds (Fig. 15(a)) while SCP-MAC needs only about 300 ms per hop (Fig. 15(b)). SCP-MAC(10 s), not shown here, results in delays similar to that of CT-MAC. When the network goes into saturation, the end-to-end delay is related to queue lengths more than On these delay results, all the 95% confidence intervals have a width of less than 7% of the plotted value.

Results synthesis

Both single-hop and multiple-hops simulations show that the CT algorithm allows for allocating multiple logical channels to nodes competing to access the medium.

Single-hop scenario results assert of the CT algorithm near-optimality for a perfect channel scenario.

Multiple-hops scenarios show that CT-MAC is able to allocate as much logical channels, i.e. C log , as SCP-MAC with a sleep-cycle C log times shorter. Because CT-MAC groups the medium access contention in one concentrated phase, it reduces energy consumption when compared to a fast running SCP-MAC providing similar capacity, and it also drastically increases the capacity compared to a slow running SCP-MAC, with similar idle energy consumption. Most important, it dynamically adapts, spatially and temporally, to the load, and can do both extremes mentioned above with no parameter changes.

7 Discussion: fulfillment of the requirements As stated in section 2.4, CT-MAC has to comply with the following requirements: r heterogeneous , r dimensioning , r localized , r assumption , r adaptability and r f airness . r heterogeneous the contention algorithm must cope with the traffic load heterogeneity of a collection network.

CT-MAC allows for a high network capacity while saving energy by using long sleep-cycles. Its high network capacity allows it to cope with large traffic load heterogeneity, as seen in collection networks. CT-MAC therefore meet the r heterogeneous requirement.

r dimensioning dimensioning of the contention algorithm must only depend on application requirements: traffic load requirement, delivery rate and not on network topology, e.g. network diameter.

CT-MAC does not depend on network topology information such as the network diameter and neighbors IDs. CT-MAC dimensioning only relies on traffic load, energy and delay requirements and therefore meet the r dimensioning requirement.

r localized the contention algorithm must rely exclusively on local information and operates in a decentralized manner.

CT-MAC does not rely on neighbors informations of any sort and operates in a localized manner. Therefore, CT-MAC also meet the r localized requirement.

r assumption the contention algorithm must not depend on traffic assumptions. CT-MAC does not rely on traffic forecasts and/or traffic assumptions to operate. Therefore, CT-MAC meets the r assumption requirement.

INRIA r adaptability the contention algorithm must self-adapt to fast-varying, burst traffic.

CT dynamically allocates channels and therefore adapts to fast-varying, burst traffic.

r f airness the contention algorithm must grant a fair medium access to all nodes. Each iteration of CT-MAC is independent of the others. All nodes participating to the tournaments share the same parameters and algorithm and have therefore the same probability to access the medium. CT-MAC is thus inherently fair and meet the r f airness requirement.

Future Work

CT-MAC relies on a novel competition algorithm that allocates multiple logical channels to nodes competing to access the medium. Studies on existing contention algorithms. e.g [START_REF] Galtier | Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks[END_REF] and [START_REF] Jamieson | Sift: A MAC protocol for event-driven wireless sensor networks[END_REF], show that significant improvements on collisions can be achieved by tuning the probability distribution used for choosing slots in the contention window. A near-optimal probability law has been proposed by [START_REF] Jamieson | Sift: A MAC protocol for event-driven wireless sensor networks[END_REF] for single-slot choice algorithms that allocate a single resource. [START_REF] Galtier | Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks[END_REF] exposes a similar result for binary countdown mechanisms, which we use in the tier 2 contention windows of CT-MAC. Therefore, we are currently addressing the optimization problem of reducing the collision probability in the CW 1 contention window that is used for allocating C log resources. We are also investigating how to prioritize the medium access such that we can differentiate traffic loads depending on their relative application requirements. This study includes discussions on how to bound the channel access time and how to derive deadline requirements into probability distributions for the CW 1 and CW 2,j contention windows.

Finally, further work will address the adaptive listening time-out mechanism and the dimensioning of the s adaptive value for given channel conditions and traffic assumptions.

Conclusion

This paper makes three main research contributions. First it describes a novel distributed resource-sharing algorithm, Cascading Tournament (CT), that allows for efficient allocation of multiple resources. Second, it proposes an implementation of CT as a MAC protocol, CT-MAC, specifically designed for energy constrained, realistic Wireless Sensor Networks. Simulations compare CT-MAC against theoretical bounds and provide a fair and complete comparison with the state-of-the-art SCP-MAC protocol, under diverse conditions.

The simulation results show that CT-MAC dynamically adapts to the load, providing an unprecedented trade-off between maximum throughput and quiescent power consumption.

CT-MAC is therefore an excellent candidate to handle the spatially and temporally heterogeneous traffic of real-world Wireless Sensor Networks. Optimizations to fit various application areas are in the work.

Figure 1 :

 1 Figure 1: Tier-1 competition structure

Figure 2 :

 2 Figure 2: Structure of a contention window

Figure 3 :

 3 Figure 3: Tier-2 competition structure and algorithm.

Fig. 4 Figure 4 :

 44 Fig.4depicts a chronogram that shows how CT-MAC is operated. 6 nodes, N 1..5 and N r , compose a set of nodes in a one-hop neighborhood. N 1..5 have packets to transmit. N r has no packet to send. The tier 1 contention window CW 1 has 6 slots, the tier 2 contention windows CW 2,j have 5 slots and the

Figure 5 :

 5 Figure 5: Adaptive listening optimization

Figure 7 :

 7 Figure 7: A channel reuse scenario

Figure 8 :

 8 Figure 8: Throughput: CT allocation is near-optimal

Figure 9 :

 9 Figure 9: Multiple-hops topology example

  (a) 48 nodes network (b) 80 nodes network (c) 120 nodes network

Figure 10 :

 10 Figure 10: Throughput versus offered load. X and Y units are per node.

Figure 11 :

 11 Figure 11: Power consumption: SCP-MAC(312.5 ms). The units are per node.

  (a) 48 nodes network (b) 80 nodes network (c) 120 nodes network

Figure 12 :

 12 Figure 12: Power consumption: CT-MAC. The units are per node.

INRIA

Figure 13 :

 13 Figure 13: Power consumption: SCP-MAC(10 s), 48 nodes network. The units are per node.

Figure 14 :

 14 Figure 14: Data retransmission rates: 120 nodes network

Figure 15 :

 15 Figure 15: Traffic delay (48 nodes)

Figure 16 :

 16 Figure 16: Traffic delay (120 nodes)

Table 1 :

 1 .

	radio bitrate	20 kbits/s
	radio output power	0 dBm
	radio RX, TX power consumption	53.7, 65.7 mW
	radio wake-up cost	0.16 mJ
	carrier-sense sensitivity	-97 dBm
	tournament slot	1 ms
	advertisement slot	8 ms
	data payload	200 bits
	wake-up period (CT-MAC)	10 s
	wake-up periods (SCP-MAC)	312.5 ms, 10 s
	C log	32 (TDMA)
	CW 1 , CW 2	128, 12
	SCP-MAC pre, post wake-up CW	32, 12
	s adaptive	6
	propagation model	perfect channel, 2-ray ground
	simulation duration	10 000 s

simulation parameters Table

RR n°7705

Acknowledgments

This work has been partially founded by French Agence Nationale de la Recherche under contract VERSO 2009-017.