Vincent Gramoli
email: vgramoli@irisa.fr

Michel Raynal
email: raynal@irisa.fr

Timed Quorum Systems for Large-Scale and Dynamic Environments ⋆

Keywords: Time, Quorums, Churn, Scalability, Probabilistic atomicity

This paper presents Timed Quorum System (TQS), a new quorum system especially suited for large-scale and dynamic systems. TQS requires that two quorums intersect with high probability if they are used in the same small period of time. It proposed an algorithm that implements TQS and that verifies probabilistic atomicity: a consistency criterion that requires each operation to respect atomicity with high probability. This TQS implementation has quorum of size O( √ nD) and expected access time of O(log √ nD) message delays, where n measures the size of the system and D is a required parameter to handle dynamism.

Introduction

The need of resources is a main motivation behind distributed systems. Take peer-to-peer (p2p) systems as an example. A p2p system is a distributed system that has no centralized control. The p2p systems have gained in popularity with the massive utilization of file-sharing applications over the Internet, since 2000. These systems propose a tremendous amount of file resources. More generally, there is an increasing amount of various computing devices surrounding us: IDC predicts that there will be 17 billions of traditional network devices by 2012. In such context, it is common knowledge that scalability has become one of the most important challenges of today's distributed systems.

The scale-shift of distributed systems modifies the way computational entities communicate. Energy dependence, disconnection, malfunctioning, and other environmental factors affect the availability of various computational entities independently. This translates into unregular periods of activity during which an entity can receive messages or compute tasks. As a result of this independent and periodic behaviors, these systems are inherently highly dynamic.

Quorum system is a largely adopted solution for communication in messagepassing system. Despite the interest for emulating shared-memory in dynamic systems [START_REF] Herlihy | Dynamic quorum adjustment for partitioned data[END_REF][START_REF] Lynch | RAMBO: A reconfigurable atomic memory service for dynamic networks[END_REF][START_REF] Friedman | Two abstractions for implementing atomic objects in dynamic systems[END_REF][START_REF] Chockler | Reconfigurable distributed storage for dynamic networks[END_REF], there is no scalable solution due to the cost of their failure handling mechanism or their operation complexity. This paper proposes a new quorum system, Timed Quorum System (TQS), whose quorums have a bounded lifetime and that intersect with high probability during their lifetime. We propose an implementation of TQS that emulates a probabilistic atomic memory, provided that each node is able to approximate the system size. We show that the resulting quorum size is O( √ nD). Factor n is the number of nodes and factor D is required to handle the dynamism of nodes in the system and can be bounded if operations are sufficiently frequent. That is, quorum size becomes O( √ n), which is optimal, as proved in [START_REF] Malkhi | Probabilistic quorum systems[END_REF], for static settings. Moreover, the expected time for an operation to contact a quorum is O(log √ nD) message delays.

Related Work. Dynamic quorum system is an active research topic. Some dynamic quorums rely on failure detectors where if a failure is detected, then the quorum is adapted. This adaption leads to a redefinition of the quorums [START_REF] Herlihy | Dynamic quorum adjustment for partitioned data[END_REF][START_REF] Naor | The load, capacity, and availability of quorum systems[END_REF] or to the replacement of the failed nodes in the quorums [START_REF] Nadav | The dynamic and-or quorum system[END_REF][START_REF] Abraham | Probabilistic quorum systems for dynamic systems[END_REF][START_REF] Gramoli | Square: Scalable quorum-based atomic memory with local reconfiguration[END_REF]. For example, in [START_REF] Abraham | Probabilistic quorum systems for dynamic systems[END_REF], a communication structure is continuously maintained to ensure that quorum intersects at all time (with high probability).

Other solutions relies on periodic reconfigurations [START_REF] Lynch | RAMBO: A reconfigurable atomic memory service for dynamic networks[END_REF][START_REF] Chockler | Reconfigurable distributed storage for dynamic networks[END_REF] where the quorum systems are subsequently replaced. These solutions are different from the previous ones since the newly installed quorums do not need to intersect with the previous ones. In [START_REF] Friedman | Two abstractions for implementing atomic objects in dynamic systems[END_REF] a quorum abstraction states requires two properties: (i) intersection and (ii) progress, in which the notion of time is introduced. First, a quorum of a certain type intersects the quorum of another type contacted subsequently. Second, each node of a quorum remains active between the time the quorum starts being probed and the time the quorum stopped being probed.

As far as we know TQS is the first quorum system that expresses guarantees that are both timely and probabilistic. Time and probability relax the traditional intersection requirement of quorums. We present a scalable emulation of a probabilistic atomic memory where each operation is atomic with high probability and where expected operation message complexity is O( √ nD) and expected operation time complexity is O(log √ nD). If operations are sufficiently frequent then D becomes a constant leading to quorum of size O( √ n).

2 System Model and Problem Definition

Model

The computation model is very simple. The system consists of n nodes. It is dynamic in the following sense. Every time unit, cn nodes leave the system and cn nodes enter the system, where c is an upper bound on the percentage of nodes that enter/leave the system per time unit and is called the churn; this can be seen as new nodes "replacing" leaving nodes. A node leaves the system either voluntarily or because it crashes. A node that leaves the system does not reenter it later. (Practically, this means that, when a node reenters the system, it is considered as a new node; all its previous knowledge of the system state is lost.) For the sake of simplicity, it is assumed that for any subset S of nodes, the portion of replaced nodes is c|S|. As explained below, the model can be made more complex. The universe U denotes all the nodes of the system, plus the ones that have already leave the system and the ones that have not joined the system yet.

Problem

Most of the dynamic models assume that dynamic events are dependent from each other: only a limited number of nodes leave and join the system during a bounded period of time. For instance in [START_REF] Chockler | Reconfigurable distributed storage for dynamic networks[END_REF], it is assumed that nodes departures are dependent: quorum replication ensures that all nodes of at least any two quorums remain active between two reconfigurations occur. However, in a real dynamic system, nodes act independently. Due to this independence, even with a precise knowledge of the past dynamic events, one can not predict the future behavior of a node. That is, putting this observation into the quorums context, it translates into the impossibility of predicting deterministically whether quorums intersect.

In contrast, TQS requires that quorums intersect with high probability. This allows to use a more realistic model in which there is a certain probability that nodes leave/join the system at the same time. That is, the goal here is to measure the probability that quorum intersect while time elapses. Observe that, realistically, the probability that k nodes leave the system increases at the time elapses. As a result, the probability that a quorum Q(t) probed at time t and that a quorum Q(t ′ ) probed at time t ′ intersect decreases as the period |t ′ -t| increases. In the following we propose an implementation of TQS where probability of intersection remains high.

More precisely, each quorum of our TQS implementation is defined for a given time t. Each quorum Q(t) has a lifetime ∆ that represents a period during which the quorum is reachable. Differently to availability defined in [START_REF] Naor | The load, capacity, and availability of quorum systems[END_REF], reachability does not depend on the number of nodes that are failed in a quorum system because this number is unpredictable in dynamic systems. Instead, a Q(t) quorum is reachable if at least one node of quorum Q(t) is reached with high probability: if two quorums are reachable at the same time, they intersect with high probability. More generally, let two quorums Q(t) and Q(t ′ ) of a TQS be reachable during ∆ time (their lifetime is ∆); if |tt ′ | ≤ ∆ then Q(t) and Q(t ′ ) intersect with high probability.

Probabilistic Atomic Object. Initially, any object has a default value v 0 that is replicated at a set of nodes and V denotes the set of all possible values present in the system. An object is accessed by read or write operations initiated by some nodes i at time t ∈ T that returns or modify the object value v. (T is the set of all possible time instants.) If a node initiates an operation, then it is referred to as a client. All nodes of the system, including nodes of the quorum system, can initiate a read or a write operation, i.e., all nodes are potential clients and the multi-reader/multi-writer model is used. In the following we only consider a single object accessed by operations that must satisfy probabilistic atomicity.

A probabilistic atomic object aims at emulating a memory that offers high quality of service despite large scale and dynamism. For the sake of tolerating scale-shift and dynamism, we aim at relaxing some properties. However, our goal is to provide each client with a distributed shared memory emulation that offers satisfying quality of service. Quality of service must be formally stated by a consistency criterion that defines the guarantees the application can expect from the memory emulation. We aim at providing quality of service in terms of accuracy of read and write operations. In other words, our goal is to provide the clients with a memory that guarantees that each read or write operation will be successfully executed with high probability. We define the probabilistic atomic object as an atomic object where operation accuracy is ensured with high probability.

Let us first recall properties 2 and 4 of atomicity from Theorem 13.16 of [START_REF] Lynch | Distributed Algorithms[END_REF] which require that any sequence of invocations responses of read and write operations applied to x satisfies a partial ordering ≺ such that:

-(π 1 , π 2 )-ordering: if the response event of operation π 1 precedes the invocation event of operation π 2 , then it is not possible to have π 2 ≺ π 1 ; -(π 1 , π 2 )-return: the value returned by a read operation π 2 is the value written by the last preceding write operation π 1 regarding to ≺ (in case no such write operation π 1 exists, this value returned is the default value).

The definition of probabilistic atomicity is similar to the definition of atomicity: only Properties 2 and 4 are slightly modified, as indicated below.

Definition 1 (Probabilistic Atomic Object). Let x be a read/write probabilistic atomic object. Let H be a complete sequence of invocations responses of read and write operations applied to object x. The sequence H satisfies probabilistic atomicity if and only if there is a partial ordering ≺ on the successful operations such that the following properties hold:

1. For any operation π 2 , there are only finitely many operations π 1 , such that π 1 ≺ π 2 . 2. Let π 1 be a successful operation. Any operation π 2 satisfies (π 1 , π 2 )ordering with high probability. (If π 2 does not satisfy it, then π 2 is considered as unsuccessful.)

3. if π 1 is a write operation and π 2 is any operation, then either π 2 ≺ π 1 or π 1 ≺ π 2 ; 4. Let π 1 be a successful operation. Any operation π 2 satisfies (π 1 , π 2 )-return with high probability. (If π 2 does not satisfy it, then π 2 is considered as unsuccessful.)

Observe that the partial ordering is defined on successful operations. That is, either an operation π fails and this operation is considered as unordered or the operation succeeds and is ordered with respect to other successful operations.

Even though an operation succeeds with high probability, in an infinite execution it is very likely that at least one operation fails. However, our goal is to provide the operation requester (client) with high guarantee of success for each of its operation request.

Additional Notations and Definitions. This paragraph defines several terms that are used in the algorithm description. First, recall that a shared object is accessed through read operations, which return the current value of the object, and write operations, which modify the current value of the object. To clarify the notion of currency when concurrency happens, it is important to explain what are the up-to-date values that could be considered as current. We refer to the last value as the value associated with the largest tag among all values whose propagation is complete. We refer to the up-to-date values at time t as all values v that satisfies one of the following properties: (i) value v is the last value or (ii) value v is a value whose propagation is ongoing and whose associated tag is at least equal or larger to the tag associated with the last value.

Timed Quorum System

This section defines Timed Quorum Systems (TQS). Before being created of after its lifetime elapses, a quorum is not guaranteed to intersect with any other quorums, however, during its lifetime a quorum is considered as available: two quorums that are available at the same time intersect with high probability. In dynamic systems nodes may leave at any time, but this probability is bounded, thus it is possible to determine the intersection probability of two quorums.

Definition of Timed Quorum System (TQS). Next, we formally define TQS that are especially suited for dynamic systems. Recall that the universe U contains the set of all possible nodes, including the one that have not join the system yet. First, we restate the definition of a set system as a set of subsets of a universe of nodes.

Definition 2 (Set System). A set system S over a universe U is a set of subsets of U .

Then, we define the timed access strategy as an access strategy over a set system that may vary over time. This definition is motivated by the fact that an access strategy defined over a set S can evolve. To compare with the existing probabilistic dynamic quorums, in [START_REF] Abraham | Probabilistic quorum systems for dynamic systems[END_REF] the authors defined a dynamic quorum system using an evolving strategy that might replace some nodes of a quorum while its access strategy remains identical despite this evolution. Unlike the dynamic quorum approach, we need a more general framework to consider quorums that are different not only because of their structure but also because of how likely they can be accessed. The timely access strategy adds a time parameter to the seminal definition access strategy given by Malkhi et al. [START_REF] Malkhi | Probabilistic quorum systems[END_REF], A timely access strategy is allowed to evolve over time.

Definition 3 (Timed Access Strategy).

A timed access strategy ω(t) for a set system S at time t ∈ T is a probability distribution on the elements of S at time t. That is, ω : S × T → [0, 1] satisfies at any time t ∈ T :

s∈S ω(s, t) = 1.
Informally, at two distinct instants t 1 ∈ T and t 2 ∈ T , an access strategy might be different for any reason. For instance, consider that some node i is active at time t 1 while the same node i is failed at time t 2 , hence it is likely that if i ∈ s, then ω(s, t 1 ) = 0 while ω(s, t 2 ) = 0. This is due to the fact that a node is reachable only when it is active. Definition 4 (∆-Timed Quorum System). Let Q be a set system, let ω(t) be a timed access strategy for Q at time t, and let 0 < ǫ < 1 be given.

The tuple Q, ω(t) is a ∆-timed quorum system if for any quorums Q(t 1 ) ∈ Q accessed with strategy ω(t 1 ) and Q(t 2 ) ∈ Q accessed with strategy ω(t 2 ), we have:

∆ ≥ |t 1 -t 2 | ⇒ Pr[Q(t 1 ) ∩ Q(t 2 ) = ∅] ≥ 1 -ǫ.

Timed Quorum System Implementation for Probabilistic Atomic Memory

In the following, we present a completely structureless memory. The quorum systems this memory uses does not rely on any structure which makes it flexible. In contrast with using a logical structured overlay (e.g., [START_REF] Morris | Chord: A scalable peer-topeer lookup service for internet applications[END_REF]) for communication among quorum system nodes, we use an unstructured communication overlay [START_REF] Ganesh | Peer-to-peer membership management for gossip-based protocols[END_REF]. The lack of structure presents several benefits. First, there is no need to readapt the structure at each dynamic event. Second, there is no need for detecting failure. Our solution proposes a periodic replication. To ensure the persistence of an object value despite unbounded leaves, the value must be replicated an unbounded number of times. The solution we propose requires periodic operations and an approximation of the system size. Although we do not focus on the problem of approximating the system size n, we suggest the use of existing protocols approximating closely the system size in dynamic systems [START_REF] Merrer | Peer to peer size estimation in large and dynamic networks: A comparative study[END_REF].

Replicating during client operations. Benefiting from the natural primitive of the distributed shared memory, values are replicated using operations.

Any operation has at its heart a quorum-probe that replicates value. On the one hand, it is natural to think of a write operation as an operation that replicates a value. On the other hand, in [START_REF] Attiya | Distributed Computing. Fundamentals, Simulations, and Advanced Topics[END_REF] a Theorem shows that "read must write", meaning that a read operation must replicates the value it returns. This raises the question: if operations replicate, why does a memory need additional replication mechanism? In large-scale systems, it is also reasonable to assume that shared objects are frequently accessed because of the large number of participants.

Quorum Probe. The algorithm is divided in three distinct parts that represent the state of the algorithm (Lines 1-11), the actions initiated by a client (Lines 12-39), and the actions taken upon reception of messages by a node (Lines 40-58), respectively. Each node i has its own copy of the object called its value val i and an associated tag tag i . Field tag is a couple of a counter and a node identifier and represents, at any time, the version number of its corresponding value val . We assume that, initially, there are q nodes that own the default value of the object, the other nodes have their values val set to ⊥ and all their tags are set to 0, 0 . Each read and write operation is executed by client i in two subsequent phases, each disseminating a message to q = O( √ nD) nodes, where D = 1/(1-c) ∆ is required to handle churn c during period ∆. 3 The two subsequent phases are called the consultation phase and the propagation phase. The consultation phase aims at consulting the up-to-date value of the object that is present in the system. (This value is identifiable since it associates the largest tag present in the system.) More precisely, client i disseminates a consultation message to q nodes so that each receiver j responds with a message containing value val j and tag tag j so that client i can update val i and tag i . In fact, i updates val i and tag i if and only if the tag i has either a smaller counter than tag j or it has an equal counter but a smaller identifiers i < j (node identifiers are always distinct); in this case we say tag i < tag j for short (cf. Lines 47 and 49). Ideally, at the end of the consultation phase client i has set its value val i to the up-to-date value. Read and write operations differ from the value and tag that are propagated by the client i. Specifically, in case of a read, client i propagates the value and tag pair freshly consulted, while in the case of write, client i propagates the new value to write with a strictly larger tag than the largest tag that i has consulted so far. The propagation phase propagates the corresponding value and tag by dissemination among nodes.

Next, we focus on the dissemination procedure that is at the heart of the consultation and propagation phases. There are two parameters, ℓ, k, that define the way all consultation or propagation messages are disseminated.

Algorithm 1 Disseminating Memory at node i 1: State of node i:

2: q = β √ n (1-c) ∆ 2
, the quorum size

3: ℓ, k ∈ N the disseminating parameters taken such that k l+1 -1 k-1 ≥ q 4:
val ∈ V , the value of the object, initially ⊥ 5:

tag , a couple of fields: 6:

counter ∈ N, initially 0 7:

id ∈ I, an identifier initially i 8:

marked , an array of boolean initially false at all indices 9:

sent-to-nbrs1 , sent-to-nbrs2 two sets of node identifiers, initially ∅ 10:

rcvd-from-qnodes , an infinite array of identifier sets, initially ∅ at all indices 11:

sn ∈ N, the sequence number of the current phase, initially 0 Parameter ℓ indicates the depth of the dissemination, it is used to set a time-to-live field ttl that is decremented at each intermediary node that participates in the dissemination; if ttl = 0, then dissemination is complete. Parameter k represents the number of neighbors that are contacted by each intermediary participating node. Together, parameters ℓ and k define the number of nodes that are contacted during a dissemination. This number is k ℓ+1 -1 k-1 (Line 3) and represents the number of nodes in a balanced tree of depth ℓ and degree k + 1: each node having at most k children. (This value is provable by recurrence on the depth ℓ of the tree.) Observe that ℓ and k are chosen such that the number of nodes that are contacted during a dissemination be larger than q as written Line 3.

There are three kind of messages denoted by message type: CONS, PROP, RESP indicating if the message is a consultation message, a propagation message, or a response to any of the two other messages. When a new phase starts at client i, a time-to-live field ttl is set to ℓ and a sequence number sn is incremented. This number is used in message exchanges to indicate whether a message corresponds to the right phase. Then the phase proceeds in sending continuously messages to k neighbors waiting for their answer (Lines 24-27 and Lines 34-37). When the k neighbors answer, client i knows that the dissemination is ongoing. Then client i receives all messages until a large enough number q of nodes have responded in this phase, i.e., with the right sequence number (Lines 29, 39). If so, then the phase is complete.

Observe that during the dissemination, messages are simply marked (if not so), responded (to client i), and reforwarded to other neighbors (until ttl is null). Messages are marked by the node i that participates into a dissemination for preventing node i from participating multiple times in the same dissemination (Line: 42). As a result, if node i is asked several times to participate, it first participates (Lines 45-58) and then it asks another node to participate (Lines 42-44). More precisely, if marked [sn] is true, then node i re-forwards messages of sequence number sn without decrementing the ttl . Observe that phase termination and dissemination termination depends on the number of participants rather than the number of responses: it is important that enough participants participate in each dissemination for the phase to eventually end.

Contacting Participants Randomly. In order to contact the participants randomly, we implemented a membership protocol [START_REF] Ganesh | Peer-to-peer membership management for gossip-based protocols[END_REF]. This protocol is based on Cyclon [START_REF] Voulgaris | Cyclon: Inexpensive membership management for unstructured p2p overlays[END_REF], thus, it is lightweight and fault-tolerant. Each node has a set of m neighbors called its view N i , it periodically updates its view and recomputes its set of neighbors. Our underlying membership algorithm provides each node with a set of m ≥ k + 1 neighbors, so that phases of Algorithm 1 disseminate through a tree of degree k + 1. This algorithm shuffles the view at each cycle of its execution so that it provides randomness in the choice of neighbors. Moreover, it has been shown by simulation that the communication graph obtained with Cyclon is similar to a random graph where neighbors are picked uniformly among nodes [START_REF] Iwanicki | Gossip-based dissemination of time[END_REF]. Finally, for a different purpose we already have simulated this variant of Cyclon in [START_REF] Fernández | Distributed slicing in dynamic systems[END_REF]: the results obtained was really similar to the one obtained with artificial uniformity.

For the sake of uniformity, the membership procedure is similar to the Cyclon algorithm: each node i maintains a view N i containing one entry per neighbor. The entry of a neighbor j corresponds to a tuple containing the neighbor identifier and its age. Node i copies its view, selects the oldest neighbor j of its view, removes the entry e j of j from the copy of its view, and finally sends the resulting copy to j. When j receives the view, j sends its own view back to i discarding possible pointers to i, and i and j update their view with the one they receive by firstly keeping the entries they received. The age of neighbor j entry denotes the time that elapsed since the last message from j has been received; this is used to remove failed neighbor from the list. This variant of Cyclon exchanges all entries of the view at each step and uses two additional parameters.

Correctness and Performance Results

This Section gives the result of our algorithm. We assume that, initially, at least q nodes own the default value of the object. Assume also that at least one propagation phase from a successful operation starts every ∆ time units and let the time of any phase be bounded by δ time units. Next, we assume that our underlying communication protocol provides each node with a view that represents a set of neighbors uniformly drawn at random among the set of all active nodes. Recall that Cyclon shuffles node views and provides communication graph similar to a random graph [START_REF] Iwanicki | Gossip-based dissemination of time[END_REF].

The first Theorem shows that the proposed solution implements a TQS. The second Theorem shows that our solution satisfies probabilistic atomicity. By lack of space, the proofs are given in the Appendix.

Theorem 1. Algorithm 1 implements a ∆-Timed Quorum System, where ∆ is the maximum time between two subsequent propagation starts.

Theorem 2. Algorithm 1 implements a probabilistic atomic object.

Next Lemmas show the performance of our solution: the first Lemma gives the message complexity of our solution while the second Lemma gives the time complexity of our solution. Observe first that operations complete provided that sent messages are reliably delivered. Building onto this assumption, an operation complete after contacting O( √ nD) nodes. The following Lemma shows this result.

Lemma 1. If messages are not lost, an operation complete after having contacted O( √ nD) nodes.

Proof. This is straightforward from the fact that termination of the dissemination process is conditioned to the number of distinct nodes contacted: Proof. The proof relies on the fact that q ′ nodes are contacted uniformly at random with replacement. In expectation, the number q ′ that must be contacted to obtain q distinct nodes is q ′ = q = O( √ nD). Since nodes are contacted in parallel along a tree of depth ℓ and degree k + 1, the time required to contact all the nodes on the tree is ℓ = O(log k q). That is, it is done in ℓ = O(log k √ nD) message delays. 2

q = O( √ nD), with D = (1 -c) -∆ (cf.

Conclusion

This paper addressed the problem of emulating a distributed shared memory that tolerates scalability and dynamism while being efficient. TQS ensures probabilistic intersection of quorums in a timely fashion. Interestingly, we showed that some TQS implementation verifies a consistency criterion weaker but similar to atomicity: probabilistic atomicity. Hence, any operation provided by some TQS satisfies the ordering required for atomicity with high probability. The given implementation of TQS verifies probabilistic atomicity, provides lightweight (O( √ nD) messages) and fast (O(log √ nD) message delays) operations, and does not require reconfiguration mechanism since periodic replication is piggybacked into operations.

Since we started tackling the problem that node can fail independently, we are now able to implement probabilistic memory into more realistic models. Previous solutions required that a very few amount of nodes could fail at the same time. More realistically, a model should allow node to act independently while requiring that failures occurring at the same time are unlikely.

An interesting question is: what probabilistic consistency can TQS achieve in such a realistic model?

A Correctness Proof

Here, we show that Algorithm 1 implements a timed quorum system and that it emulates the probabilistic atomic object abstraction defined in Definition 1. The key points of this proof is to show that quorums are sufficiently re-activated by new operations to face dynamism and that subsequent quorums intersect with very high probability to achieve probabilistic atomicity.

Assumptions and notations. First, we only consider executions starting with at least q nodes that own the default value of the object. In these executions, at least one propagation phase from a successful operation starts every ∆ time units and let the time of any phase be bounded by δ time units. We assume that during a propagation that propagates a value v to q nodes and that executes between time t and t + δ, there is at least one instant t ′ where the q nodes own value v simultaneously. This instant, t ′ , can occur arbitrarily between time t and t + δ. Even if this assumption may not seem realistic since propagation occurs in parallel of churn (i.e., at the time the propagation contacts the q th node the first contacted node may have left the system), our motivations for this assumption comes from the sake of clarity of the proof and we claim that the absence of this assumption leads to the same results.

Second, we assume that our underlying communication protocol provides each node with a view that represents a set of neighbors uniformly drawn at random among the set of all active nodes. This assumption is reasonable since, as already mentioned, the underlying algorithm is based on Cyclon that shuffles node views and provides communication graph similar to a random graph [START_REF] Iwanicki | Gossip-based dissemination of time[END_REF].

Next, we show that Algorithm 1 implements a probabilistic object. Observe that the liveness part of this proof relies simply on the activity of neighbors, and the fact that messages are eventually received. More precisely, by examination of the code of Algorithm 1, messages are gossiped among neighbors while neighbors are uniformly chosen. It is clear that operation termination depends on eventual message delivery. As a result, only the safety part of the proof follows. In the following, val (φ) (resp. tag (φ)) denote, the value (resp. tag) consulted/propagated by phase φ.

Correctness proof. First, we restate a Lemma appeared in [START_REF] Gramoli | Core persistence in peer-to-peer systems: Relating size to lifetime[END_REF] that computes the ratio of nodes that leave the system as time elapses, given a churn of c. The result is the ratio of nodes that leave and join, and helps computing the probability that up-to-date values remain reachable despite dynamism.

Lemma 3. The ratio of initial nodes that have been replaced after τ time units is at most

C = 1 -(1 -c) τ .
For the proof of the above Lemma 3, please refer to [START_REF] Gramoli | Core persistence in peer-to-peer systems: Relating size to lifetime[END_REF]. The following Lemma gives a lower bound on the number of nodes that own the up-to-date value at any time in the system. (Recall that an up-to-date value is either the value with the largest tag and whose propagation is complete, or any value with a larger tag, but whose propagation is ongoing.) Lemma 4. At any time t in the system, the number of nodes that own an up-to-date value is at least q(1c) ∆ , where ∆ is the maximum time between two subsequent propagation starts, q is the quorum size, and c is the churn of the system.

Proof. With no loss of generality, let ρ 1 , ..., ρ k be all the ongoing propagations at time t and let ρ 0 be the latest successful propagation that is already finished at time t. By definition, all v(ρ i ) for any i ≥ 0 are the up-to-date values in the system. Propagations ρ 1 , ..., ρ k must all have started after time tδ. By the periodicity assumption of propagation phase, propagation ρ 0 can not start earlier than time t -∆ + δ. Due to propagation ρ 0 , there must be q nodes with value v(ρ 0 ) between times t -∆ + δ and t -∆ + 2δ.

Since the number of replaced nodes increases as time elapses, assume a worst case scenario in which q nodes own value v(ρ 0 ) at time t 1 = t-∆+δ, we show that at least q(1c) ∆ nodes with value v(ρ 0 ) remain in the system at time t 2 = t+δ. By Lemma 3, we know that during period t 2 -t 1 = ∆ exactly ⌊q(1 -(1c) ∆ )⌋ nodes with value v(ρ 0 ) are replaced. Since propagations ρ 1 , ..., ρ k are ongoing, there may be some successful propagations among those ones that overwrite some node values. Observe that if this overwriting happens only to nodes that already own value v(ρ i ), then the number of nodes with value v(ρ i ) remains at least q(1c) ∆ at time t + δ; if this overwriting happens to nodes that do not own value v(ρ i ) then this number increases. That is, q(1c) ∆ is a lower bound of the number of nodes with value v(ρ i ) at time t + δ, which leads to the result.

2

The following Fact gives this well-known bound on the exponential function, provable using the Euler's method.

Fact 3 (1 + x n ) n ≤ e x for n > |x|.
Next Lemma lower bounds the probability that any consultation consults an up-to-date value v. Recall that sometime it might happen that a value v ′ is unsuccessfully propagated. This may happen when a write operation fails in consulting the largest tag just before propagating value v ′ . Observe that in any case, a successful consultation returns only successfully propagated values.

Lemma 5. If the number of nodes that own an up-to-date value is at least q(1c) ∆ during the whole period of execution of consultation φ, then consultation φ succeeds with high probability (≥ 1e -β 2 , with β a constant).

Proof. The consultation of Algorithm 1 draws uniformly at random q nodes, without replacement. To lower bound the probability P that any consultation consults an up-to-date value v, we compute the probability that this value is obtained after q drawings with replacement. It is clear that the probability of obtaining a specific node after q drawings is larger without replacement than with replacement. The probability for a node x uniformly chosen at random not to own the value v is Pr

[x / ∈ Q] = 1 -q(1-c) ∆ n
that is, the probability not to consult value v after q drawings, with replacement, is Pr

[x 1 / ∈ Q, ..., x q / ∈ Q] = 1 -q(1-c) ∆ n q . By Fact 3, Pr[x 1 / ∈ Q, ..., x q / ∈ Q] ≤ e -q 2 n (1-c) ∆
. By replacing the q by the quorum size given at Line 2 of Algorithm 1 in the contrapositive P ≥ 1e -q 2 n (1-c) ∆ we obtain the result P ≥ 1e -β 2 . 2

This corollary simply concludes the two previous Lemmas stating that any consultation executed in the system succeeds by returning an up-to-date value.

Corollary 1. Any consultation φ succeeds with high probability (≥ 1-e -β 2 , with β a constant).

Proof. The result is straightforward from Lemma 4 and Lemma 5.

2

Last but not least, the two theorems conclude the proof by showing that Algorithm 1 implements a ∆-TQS and verifies probabilistic atomicity.

Theorem 1. Algorithm 1 implements a ∆-Timed Quorum System, where ∆ is the maximum time between two subsequent propagation starts.

Proof. First observe that the set of quorums is the set of subsets of q active nodes over the system at time t. The timed access strategy at time t over the set of all quorums is the uniform access strategy over all quorums since each node is chosen with a uniform access strategy among the active nodes at time t. By Corollary 1, it is clear that the intersection between two quorums is ensured with high probability as long as one quorum starts being contacted ∆ timed before the other ends being contacted. 2

Theorem 2. Algorithm 1 implements a probabilistic atomic object.

Proof. The proof shows that it exists an ordering ≺ defined by the tags verifying Definition 1. This ordering is such that π i ≺ π j is equivalent to either tag (π i ) = tag (π j ) and π i is a write and π j is a read, or tag (π i ) < tag (π j ). Each property of Definition 1 is proved separately.

1. Property 1 is deduced straightforwardly from the other Properties.

2. The proof is done in two parts. First, we show that Property 2 holds if consultation phase of operation π 2 obtains an up-to-date value. Second, we show that this consultation phase obtains an up-to-date value with high probability.

(a) On the one hand, we denote by φ i and by ρ i the respective consultation phase and propagation phase of any operation π i . We show by contradiction that Property 1 holds if φ 2 consults an up-to-date value. By absurd, assume that it is false. That is, assume that φ 2 consults an up-to-date value, the response of π 1 precedes the invocation of π 2 , and π 2 ≺ π 1 . Since φ 2 consults an up-to-date value, we have tag (φ 2 ) ≥ tag (π 1 ). Now there are two cases to consider: either π 2 is a read or a write. First, if π 2 is a write then tag(π 2 ) > tag (φ 2 ) ≥ tag(π 1 ) by examination of the code of Algorithm 1 (cf. Lines 20). By definition of ≺, if tag (π 2 ) > tag (π 1 ) and π 2 is a write, then it can not happen that π 2 ≺ π 1 . Second, if π 2 is a read then tag(π 2 ) = tag (φ 2 ) ≥ tag(π 1 ) by examination of the code of Algorithm 1 (cf. Lines 14). By definition of ≺, if tag (π 2 ) ≥ tag(π 1 ) and π 2 is a read, then it can not happen that π 2 ≺ π 1 . As a result, this contradicts the assumption, showing that Property 1 holds if φ 2 obtains an up-to-date value. (b) On the other hand, Corollary 1 shows that any consultation obtains the most up-to-date value with high probability. Since Property 2 holds if a consultation of π 2 consults an up-to-date value, and since any consultation consults an up-to-date value with high probability, the result follows. 3. Property 3 follows simply from the way tags are chosen. Let π 1 and π 2 be any two operations. On the one hand, if π 1 and π 2 are initiated at node i, then they have distinct tag counters. On the other hand, if π 1 and π 2 are initiated at two distinct nodes, then they have distinct tag identifiers i and j. As a result, two operations have different tags and either tag(ρ 1 ) > tag(ρ 2 ) or tag (ρ 1 ) < tag (ρ 2 ) holds. 4. Property 4 fails only if the read operation is unsuccessful. The probability P π for an operation π to be unsuccessful is lower than the probability P φ that its consultation φ is unsuccessful. Since we know by Corollary 1 that this later probability P φ is very low (P φ = e -β 2 ), the probability P π that an operation is unsuccessful is very low too (P π < e -β 2 ). It follows that Property 4 holds with high probability (≥ 1e -β 2 ).

  Line 2). Since there are two disseminating phases in each operation, an operation is executed after contacting

	O( √ Next Lemma indicates that an operation terminates in O(log nD) nodes.	√	2 nD) mes-
	sage delays, in expectation.
	Lemma 2. If messages are not lost, the expected time of an operation is O(log √ nD) message delays.

In[START_REF] Malkhi | Probabilistic quorum systems[END_REF], it has been showed that q = O( √ n) is sufficient in static systems.

Acknowledgments. We are grateful to Anne-Marie Kermarrec and Achour Mostéfaoui for fruitful discussions about gossip-based algorithms and dynamic systems.


Erwan Le Merrer
email: erwan.lemerrer@orange-ft.com

Vincent Gramoli

Anne-Marie Kermarrec

Aline C Viana
email: aline.viana@irisa.fr

Marin Bertier
email: marin.bertier@irisa.fr

Energy Aware Self-organizing Density Management in Wireless sensor networks

Keywords: C.2.1 [Computer-Communication Networks]: Network Architecture and Design-distributed networks, wireless communication Wireless sensor networks, topology management, peer-topeer distributed systems

Energy consumption is the most important factor that determines sensor node lifetime. The optimization of wireless sensor network lifetime targets not only the reduction of energy consumption of a single sensor node but also the extension of the entire network lifetime. We propose a simple and adaptive energy-conserving topology management scheme, called SAND (Self-Organizing Active Node Density). SAND is fully decentralized and relies on a distributed probing approach and on the redundancy resolution of sensors for energy optimizations, while preserving the data forwarding and sensing capabilities of the network. We present the SAND's algorithm, its analysis of convergence, and simulation results. Simulation results show that, though slightly increasing path lengths from sensor to sink nodes, the proposed scheme improves significantly the network lifetime for different neighborhood densities degrees, while preserving both sensing and routing fidelity.

INTRODUCTION

Context. Area monitoring is one of the most typical applications of wireless sensor networks (WSNs). It consists in deploying a large number of sensors in a given geographic area, for collecting data or monitoring events. It is not unusual that in this situation, human intervention is not feasible. Sensors are then thrown in mass, for example from a plane, and must be able to form a network and to operate in a decentralized self-organized manner, maintaining connectivity and area monitoring as long as possible. In addition, because of the absence of wire and the small physical size of sensors, WSNs have strong power restrictions. Mechanisms for energy optimization in WSNs constitute then an important requirement. This optimization targets not only the reduction of energy consumption of a single sensor node but also the extension of the entire network lifetime. The sensor network lifetime is defined as the period during which the routing fidelity and the sensing fidelity of the network are guaranteed. Guaranteeing sensing fidelity means that any monitored stimulus in the area will always be sensed by at least one sensor. Routing fidelity means the existence of a path between any sensor node and at least one base station. Our goal is then to leverage node redundancy in WSNs to reduce and distribute the computational and communication energy consumption of the network between sensors. We consider that the cooperative nature of sensors offers significant opportunities to manage energy consumption.

Given the potentially large number of sensors in a WSN and their limited resources, it is also crucial to deploy fully decentralized solutions and to evenly spread the load over the network. Recent works in Peer-to-Peer (P2P) systems can be successfully adapted to explore new solutions for energy consumption distribution in sensor networks. Contributions. This paper describes an adaptive and fully decentralized topology management scheme, called SAND (Self-organizing Active Node Density). SAND significantly extends network lifetime by reducing nodes activity. The major contribution of SAND is its simple algorithm: each node takes local decision based on the observation of its neighborhood in order to ensure the properties of routing and sensing fidelity. Moreover, SAND as a whole converges towards the expected properties. In order to manage energy consumption, we leverage P2P's cooperation paradigms and explore local node information and sensors resolution through neighborhood communication only. No node location information is required, and our approach is independent of any wireless routing protocol.

For any configuration of the energy-aware topology, we show that SAND guarantees that routing and sensing fidelity will be extended. In comparison with the case where no topology management is applied, SAND considerably ex-tends network lifetime at the price of the slightly increasing paths lengths from sensor to sink nodes. Moreover, simulations of SAND suggest that network lifetime and SAND's robustness increases proportionally to node density. Outline. The rest of this paper describes and evaluates SAND. In Section 2, we discuss the advantages in performing power management of radios in wireless networks and describe our system model. We review related works in Section 3. In Section 4, we describe the SAND approach, analyse interesting properties, and discuss design issues. We present the performance results in Section 5. Finally, in Section 6, we conclude this paper and discuss future works.

FOREWORD

Where does the energy go?

Power dissipation analyses of a sensor node in the literature show that wireless communication is a major energy consumer during system operation [START_REF] Raghunathan | Energy-aware wireless microsensor networks[END_REF][START_REF] Estrin | Next century challenges: Scalable coordination in sensor networks[END_REF]. Results show that (i) the overhearing process increases power consumption,1 and (ii) energy optimizations must turn off the radio and not simply reduce packet transmission and reception. SAND, therefore, incorporates power management into the communication process. We optimize energy consumption by completely turning off radio whenever possible, conserving energy both in Idle state when no traffic exists and in overhearing due to data transfer.

We also take advantage of the sensor network density for energy savings. SAND also powers down sensor nodes that are equivalent from a sensing perspective. In summary, SAND is a very simple topology management scheme, which generates low communication overhead. SAND applies in the context of nodes that are able to:

1. turn off their radios for communication power conservation, while still maintaining connectivity between sensors and sinks, i.e. the routing fidelity; 2. completely power down for sensing power conservation, while still ensuring a correct stimuli monitoring, i.e. the sensing fidelity.

System model

We consider a distributed system consisting of a finite set of n sensors and s sinks, each uniquely identified. Nodes (sensors or sinks) are spread into a delimited area. We consider that both sensor and sink nodes form a connected network or that all network partitions contain at least one sink node. Nodes may crash and recover during the network lifetime, we do not consider Byzantine failure. We assume that, although there is no need for synchronized clocks, there is an upper bound on the drift rate of local clocks. We define δ as an upper bound on the transmission time of a message between two neighbors. We consider that sensing and communication ranges are equal.

SAND does not require any node location information. We explore density determination by assuming that nodes communicate only by 1-hop broadcast toward nodes in their neighborhood, corresponding to their transmission range. Finally, a node may be in one of the four following energy states: sleep, sensor-only, router-sensor, and gateway. Each state corresponds to a defined node activity and one or several services provided to the network (see Table 1). SAND guides nodes' energy state switching independently of the underlying wireless routing protocol. Interactions between SAND and the routing protocol are part of a future work.

RELATED WORKS

Topology management techniques, called SPAN [START_REF] Chen | Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks[END_REF] and GAF [START_REF] Xu | Geography-informed energy conservation for ad hoc routing[END_REF], have similar goals to those of SAND: they trade network density for energy savings while preserving the forwarding capacity of the network. Nevertheless, they do not exploit the absence of traffic in the active sensing state. Besides the energy consumption reduction in the sensing state, the STEM [START_REF] Schurgers | Optimizing sensor networks in the energy-latency-density design space[END_REF] scheme also proposes to ensure a satisfactory latency for transitioning to the routing state. Authors then suggest integrating STEM with scheme such as GAF and SPAN. SAND coordinates the radio sleep and the wakeup switch for sensing and/or routing states in a unique scheme, being no integration necessary. 2 Several algorithms have been proposed for exploiting the area coverage problem in sensor networks [START_REF] Carle | Preserving area coverage in wireless sensor networks based on surface coverage relay dominating sets[END_REF][START_REF] Tian | A coverage-preserving node scheduling scheme for large wireless sensor networks[END_REF][START_REF] Carle | Localized sensor area coverage with low communication overhead[END_REF]. Contrary to SAND, all these solutions assume that the sensors are aware of their own positions. Authors in [START_REF] Tian | A coverage-preserving node scheduling scheme for large wireless sensor networks[END_REF] do not address the connectivity problem and require every sensor to know all their neighbors positions before making its monitoring decisions [START_REF] Tian | A coverage-preserving node scheduling scheme for large wireless sensor networks[END_REF]. The proposal presented by Carle and Simplot-Ryl [START_REF] Carle | Preserving area coverage in wireless sensor networks based on surface coverage relay dominating sets[END_REF] specifies that each sensor needs to construct its subset of relays and broadcast it to its neighbors, which generates higher communication overhead than SAND. The solution proposed by A. Gallais et al. [START_REF] Carle | Localized sensor area coverage with low communication overhead[END_REF] relies on low communication overhead and does not need any neighborhood discovery. Nevertheless, nodes have to memorize the positions and the decisions of their neighbors in order to make appropriate monitoring decisions. In SAND, however, nodes need a small amount of information (e.g. only a partial neighborhood discovery) and perform a low processing overhead to take their activity decisions. Clustering algorithms can be also used to select router nodes. As an example, M. Chatterjee et al. in [START_REF] Chatterjee | Wca: A weighted clustering algorithm for mobile ad hoc networks[END_REF] use quite sophisticated concepts and heuristics to decide which nodes should be cluster heads. SAND instead, has as a major contribution the simplicity for router election procedure.

SAND DESIGN RATIONALE

A major issue in sensor-based applications is the diffusion of the sensed data to a specific entity that can store and process it -the sink node. Mechanisms that ensure this diffusion are important components in WSNs and have been the subject of many researches in the literature [START_REF] Al-Karaki | Routing techniques in wireless sensor networks: A survey[END_REF]. In this context, the cooperation between energy conserving and information diffusion robustness is crucial. 2 The insurance of a satisfactory latency for transitions of state is not our focus here. We take advantage of information provided by routing layer and/or information related to the envisaged application to determine when the radio is not needed. We consider that during network lifetime, sensor nodes can alternate their energy consumption between four states (see Fig. 1):

Sensor Router Sleep

Sleep order from router

Gateway

Wake-up order from router 2 routers and no gateway in its No router in its area

Same function detected area that already link them

(1) sleep, where all hardware components are powered off, (2) sensor-only, where only sensor and some pre-processing circuity are powered on, and (3) gateway and router-sensor, where all hardware components are powered on. 3 SAND performs then the energy-aware topology management by controlling the routing and the sensing fidelity during the network lifetime.

Forwarding nodes distribution

The forwarding nodes distribution is performed in two consecutive phases. The first one distributes nodes in routersensor state uniformly in the network. The second one consists in connecting close router-sensors by selecting nodes to switch to the gateway state. These two phases are based on the SONDe's principle [START_REF] Merrer | Sonde: Self-organizing density for peer-to-peer network services[END_REF]: if a node does not detect any neighbor in each one of these two states then it turns itself into the missing state. else status ← sensor-only 13: else if status = gateway then 14:

status ← sensor-only Algorithm overview. The SAND algorithm is presented in Algorithm 1. Each period of time ∆ > 2δ, the routersensor nodes send Hello messages containing their current state and a timestamp ts. Observe that we do not focus on specifying the message retransmission in case of collision; we rather assume that this is implemented at a lower layer. The timestamp ts of node i contains: the time i spent in its current state and its identifier (tie breaker). Each sensoronly node in the network checks if there is a router-sensor node in its immediate neighborhood, by listening during a timeout Ton with Ton > ∆ + δ. If no router-sensor node is detected, then the sensor-only node becomes a router-sensor node (Lines 2-3). If a router-sensor node detects the presence of another router-sensor node in its transmission range with a higher timestamp than its own, it comes back to the sensor-only state (Lines 4-6). While the first phase guarantees a good distribution of router-sensor, the second phase (Lines 8-14) elects gateways to connect them. A sensor-only node becomes gateway if it detects two routers and no gateway with a lower timestamp than its own and that already makes a link path between those two routers. A gateway node informs with a period ∆ about the routers it sees. If a gateway detects another gateway which connects the same router-sensor and with a higher timestamp than its own, it comes back to the sensor-only state (Line 12). Independent-dominating set convergence. In the following, we show that SAND presents two interesting properties borrowed from graph theory. First, to help routing to a sink node, each node is in the neighborhood of a routersensor node or is itself a router-sensor node. Second, to prevent energy consumption waste, a subset of nodes becomes router-sensor nodes. There are solutions for related problems known as vertex cover and minimal dominating set, which guarantees activated sensors to form such a set.

The minimality problem of the aforementioned solutions might involve many state changes each time a router-sensor crashes. Here, we rather ensure that the sensor-router nodes satisfy both domination and independence properties. This helps at reducing, yet making it sufficient, the number of router-sensor nodes, while this number has not to be minimal. Roughly speaking, the router-sensor nodes satisfy (i) dominance: all nodes are either router-sensor or a neighbor of a router-sensor and (ii) independence: no routersensor node is a neighbor of another router-sensor node.

The following proof shows that the algorithm converges to a configuration verifying both properties under system stabilization. Let a real-router (resp. real-sensor ) denote a router-sensor node (resp. sensor-only node) that became router-sensor (resp. sensor-only) Ton time ago, and which did not revert its state since then.

Theorem 1. The SAND algorithm converges towards an independent-dominating set.

Proof sketch. The proof is divided in three parts. First we show that the independent-dominating property is an invariant. Consider the communication subgraph containing only real-routers and real-sensors whose real-routers form an independent dominating set when the system stabilizes. That is, any real-sensor node receives a message from a realrouter in each Ton period of time and does not become a router. Similarly the real-routers stay in their state.

Second we show that independence can never be violated. Observe that nodes are initially in their sensor-only state and thus can not violate independence by awakening. Before stabilization, real-router can crash but independence is never violated since message delay remains bounded.

Finally, we show that the number of locations where the dominance is violated eventually decreases, let G be any communication subgraph whose set of real-routers is not dominant. After some time, some nodes of G become routers. This might happen in the meantime at different places in the same neighborhood. After a Ton delay, messages are exchanged between routers and the one with the lowest ts is chosen to become exclusively the real-router of the neighborhood. Other router nodes, so as sensor-only nodes, become real-sensor.

Experiment described in Fig 2(a) confirms our theoretical analysis and shows the result of our router selection after three simulation rounds: this simulation leads to 50 routersensor nodes (black circles) for 450 sensor-only nodes (gray circles). Provided these properties, we claim that a sufficient sensor nodes density will provide enough gateway candidates to ensure the connection between two close router-sensors. Consequently, SAND does not determine the optimal minimum number of forwarding nodes to maintain sink connectivities, ensuring then, that there are several paths between any node and at least one sink. This redundancy makes the routing fidelity more resilient to failures. Our claim is satisfied by the experiments obtained in Fig. 2(b) commented hereafter. Specifying a protocol to obtain a path among all router-sensors from a dominating set is left as an open work.

Sensing guarantee

Fidelity in stimuli sensing can be ensured only by routersensor and gateway nodes, because they are uniformly distributed in the network and their sensing range is equal to their transmission range. Nevertheless, for reliability issues and for the cases where a specific sensor node density should be ensured, SAND allows the control of the sensoronly nodes resolution in each target area, while performing the sensing load distribution among nodes.

To this end, router-sensor nodes are in charge of selecting nodes to switch to sleep or sensor-only state. This selection depends on the envisaged reliability degree of the monitored area. Thus, nodes that are for a long time in the sensoronly state will be selected to switch to sleep state, and vice versa. Each sensor-only node periodically turns on its radio and sends Hello messages containing its current state and its estimated lifetime (el). 4 Nodes in sleep state also periodically turn on their radio, but never send messages. 5 Upon reception of sensor-only el of sensor-only neighbors, router-sensor nodes compute the average (by considering the el of the last switched-to-sleep nodes too) and the standard deviation (by considering only the sensor-only nodes that have lower el than the resulting average). Finally, routersensor nodes send 1-hop "switch-to-sleep" order messages to sensor-only nodes that have their el level lower than the resulting standard deviation. The switch of sensor-only to sleep state is performed as soon as another sensor-only node 4 el corresponds to the expected remaining node energy and is set by assuming that nodes will have a start energy level and they will consume energy (related to their state) until they die. 5 We assume their estimated lifetime is the same of the last el sent when they were in the sensor-only state. appears in the monitored area. Sensor-only nodes also turn on their radio if any local collected data has to be transmitted to the sink (e.g., for full memory resource).

Router-sensor nodes also control the switch from sleep to sensor-only states, by sending "switch-to-sensor" order messages. 6 In this case, nodes in the sleep state switch to the sensor-only state if they have ( 1) their radio turned on, and (2) their el level is higher than the computed average. In addition, like sensor-only nodes, nodes in the sleep state with the radio turned on, verify their router-sensor node connectivity. If no Hello message from a router-sensor node is received, a sleep node becomes a sensor-only node and then, based on the SAND bootstrap procedures, can switch to the router-sensor or gateway state.

Discussion

We now discuss some design choices. Outlining parameters: The radio of sleep and sensoronly nodes is periodically turned on for fidelity verifications at intervals T of f and stay on for at least a timeout value Ton. The range of T of f can be influenced by the time that nodes have been conserving their energy during the sleep state. Optimizations of these parameters are under evaluation.

Outlining advantages: Contrary to some existing area coverage solutions, SAND does not require nodes position information or geographic coverage computing for ensuring connectivity. Therefore SAND has a low computing overhead. Moreover, since nodes do not need to perform a complete neighborhood discovery to take their state decisions, SAND has also as advantage a low communication overhead.

What if disconnections occur: Considering the poor failure resilience of sensor nodes and the SAND's guarantee of sink connectivity, it may occur that failed nodes cause temporary disconnections. This can also occurs if Hello messages from router-sensor nodes are lost, causing gateway nodes to become sensor-only nodes. Nevertheless, since SAND allows disconnection detection and restores connectivity by state switching, we consider that disconnection periods will not be long. Nodes may store their messages and wait for connectivity restoration. In the case of router-sensor Hello message losses, gateway nodes can be instrumented to wait at least a timeout value of 2 × Ton before deciding to switch to sensor-only state. This kind of improvements is subject to future works.

PERFORMANCE EVALUATION

We have conducted a number of simulation experiments over 800 rounds, using a simulator consisting of the SAND engine and a network emulation environment. We experiment on a large scale static network with 4,700 nodes. Nodes are uniformly distributed over a square area of 700 m on a side and have a transmission range of 37 m. The dynamism of the created topology is imposed by fail nodes only.

The simulator is a discrete time-based engine, in which actions are performed per round of simulation. We have set T of f to be 2 rounds. We consider that nodes send order or Hello messages at each round. We also consider that sensor-only nodes send Hello messages at each ∆ period, where ∆ and Ton are initially set to 1 round.

We set all nodes with an estimated lifetime el of 100,000 unities (u). Our energy consumption model is based on the power consumption of the sensor node described in [START_REF] Sinha | Dynamic power management in wireless sensor networks[END_REF]. We consider thus, the costs described in Table 2. The network lifetime column shows approximated values for the estimate maximum lifetime corresponding to nodes in each state.

We uniformly generated 1,000 stimuli over the network. Unless otherwise specified, we set the reliability degree of each monitored stimulus to 5 nodes. No wireless routing protocol is implemented. Thus, to evaluate the routing fidelity of our approach, we simply verify if there is a path between a source node (i.e., a sensor-only, a gateway, or a routersensor node) and at least one sink node. Path verification is performed each time a stimulus is generated. Unless otherwise specified, sink nodes are uniformly distributed over the network and correspond to 1% of all nodes. To examine the impact of the neighborhood density in the network lifetime, we vary the number of nodes from 1,000, to 1,900, 2,800, and 4,700 (corresponding to approximately 10, 20, 30, and 50 neighbors in range, respectively), while keeping constant the area and the transmission range of nodes. We evaluate SAND along the following metrics: (i) the network lifetime and the energy conservation; (ii) the forwarding robustness; (iii) the sensing fidelity preservation; and (iv) the effects of network density. Experimental results. One of the SAND goals it to preserve network routing fidelity. We consider that if paths in the gateway/router-sensor nodes backbone exist, there are similar non-conflicting paths in the underlying network. Fig. 3(a) evaluates the robustness of SAND in ensuring a sink connectivity in a 1,900-nodes network. For this purpose, we vary the sink node density from 0.5%, 1%, and 1.5% of the total number of nodes. As expected, as sink resolution decreases, more active nodes are needed to ensure sink connectivities. This results in a decrease of the network lifetime and the faster energy exhaustion of nodes. Nevertheless, compared to results obtained in Without-SAND topology with 1% of sink density, SAND still extends the number of forwarding paths of network (95% of paths are ensured for a double of time than in Without-SAND), even with a lower sink resolution of 0.5%.

Additionally, for different neighborhood densities, we show that despite using fewer forwarding nodes, SAND does not significantly increase the number of hops of paths to sink nodes. Table 3 shows the average (τ ) and the standard deviation (σ) path length of SAND and Without-SAND, calculated while 90% of the generated stimuli are sensed and corrected forwarded. SAND constructs forwarding paths with only a slightly higher number of hops, on average 18% of more hops. Fig. 3(b) shows the average of energy remaining at each node after 40 simulation rounds under different neighborhood densities. In this simulation round, all nodes in the network are still alive. The figure also compares the energy conservation resulted in SAND with the case where no power management is performed. We observe that SAND provides a considerable amount of energy saving over Without-SAND. This is because all nodes in Without-SAND topology have the same energy consumption as router-sensor nodes. In SAND, however, nodes switch when ever possible to sleep or sensor-only states, as a few forwarding nodes are present in each transmission range. We also check that the energy saving increases proportionally to the neighborhood density. This is due to the fact that as the density increases, a lower fraction of alive nodes is composed of forwarding nodes (the highest consumer of energy state), while a higher fraction are in the sleep state (see Fig. 3(e)).

Fig. 3(c) evaluates the robustness of SAND with respect to sensing fidelity, in a 1,900-nodes network. We vary the required sensor node density in the network from 2, 7, and 10 nodes, and show the rate of success sensed stimuli for each density. Compared to the results obtained in Without-SAND topology (where all nodes are sensing for all the simulation time), SAND extends the number of sensed stimuli over the network lifetime, even when a lower sensor node resolution of 2 is used per target area. SAND ensures for a triple of time, 95% of sensing fidelity than Without-SAND. As expected, the increase of the number of required sensor density, impacts the energy consumption of nodes and consequently, decreases the network lifetime. Fig 3(d) shows the results of the performance of SAND in ensuring sink connectivity for different neighborhood densities (for 20 and 50 neighbors in range) and sink resolution (for 0.5%, 1%, and 1.5% of the total number of nodes). As expected, SAND is less impacted by sink resolution when the neighborhood density increases. This is because the increase of neighborhood density, increases the number of forwarding candidates, and consequently, increases the probability of finding paths to sink nodes. after 120 rounds of simulation (among many experiments), under different neighborhood densities. Here, we compare the fraction of active and forwarding nodes over the total number of nodes in the network and over the total number of alive nodes. We show that the potential of saving energy of SAND depends on the node density, since the fraction of active and forwarding nodes depend on the number of nodes per radio coverage area. We can easily verify that the higher the node density, the lower the percentage of active nodes in the network. Also the rate of forwarding nodes over the number of active nodes decreases as the neighborhood density increase. On the other hand, despite the increase of the rate of forwarding nodes over the total number of nodes, the number of forwarding nodes becomes almost constant for higher neighborhood densities (e.g., for 30 and 50 neighbors in range).

CONCLUSION

In this paper, we have presented SAND, an approach to energy conservation for wireless sensor networks. Energy consumption is one of the most important factors that determines sensor node lifetime. SAND is a fully decentralized, simple, and efficient algorithm able to significantly extend not only sensor lifetime but also the entire network lifetime. SAND focuses on turning off the nodes radio as much as possible while still ensuring stimuli sensing and multi-hop routing fidelity. We have presented the algorithm analysis and the simulation of SAND. Our experiments show that SAND guarantees for a longer time, (1) the existence of paths between any sensor node to at least one sink node in the network and (2) the correct sensing of stimulus in a monitored sensor network. SAND improves considerably network lifetime proportionally to node density, at the price of the slightly increasing paths length from sensor to sink nodes. Additional analyses are being performed to evaluate the network behaviour of SAND as nodes move. We also intend to study network partitions and to validate our results with physical hardware in real scenarios.

Figure 1 :

 1 Figure 1: Energy state transition diagram in SAND.

Algorithm 1 :

 1 The SAND Algorithm 1: Phase 1: 2: if ¬router-detection() then 3: status ← router-sensor 4: else if r ← router-detection() then 5: if r.ts > ts then 6: status ← sensor-only 7: Phase 2: 8: if |routers ← detected-routers()| ≥ 2 then 9: if ¬(g ← gateway-detection()) ∨ (g.ts < ts) 10: ∧¬(routers ⊆ g.routers) then 11: status ← gateway 12:

Figure 2 :

 2 Figure 2: A 300×300 m area network with an average of 20 neighbors per node representing: (a) the router selection, (b) the energy state distribution.

  Fig. 2(b) shows the result of the SAND energy state distribution at a random point in time. The figure presents 68 router-sensor nodes (black circles), 47 gateway nodes (squares) and 385 sensor-only and sleep nodes (gray circles). The line connecting points represents the connectivity among forwarding nodes. The network connection among forwarding, sleep, and sensor-only nodes is not represented here. This shows that the generated forwarding topology is connected.

Fig 3 (Figure 3 :

 33 Fig.3(b) shows the average of energy remaining at each node after 40 simulation rounds under different neighborhood densities. In this simulation round, all nodes in the network are still alive. The figure also compares the energy conservation resulted in SAND with the case where no power management is performed. We observe that SAND provides a considerable amount of energy saving over Without-SAND. This is because all nodes in Without-SAND topology have the same energy consumption as router-sensor nodes. In SAND, however, nodes switch when ever possible to sleep or sensor-only states, as a few forwarding nodes are present in each transmission range. We also check that the energy saving increases proportionally to the neighborhood density. This is due to the fact that as the density increases, a lower fraction of alive nodes is composed of forwarding nodes (the highest consumer of energy state), while a higher fraction are in the sleep state (see Fig.3(e)).Fig.3(c) evaluates the robustness of SAND with respect to sensing fidelity, in a 1,900-nodes network. We vary the required sensor node density in the network from 2, 7, and 10 nodes, and show the rate of success sensed stimuli for each density. Compared to the results obtained in Without-SAND topology (where all nodes are sensing for all the simulation time), SAND extends the number of sensed stimuli over the network lifetime, even when a lower sensor node resolution of 2 is used per target area. SAND ensures for a triple of time, 95% of sensing fidelity than Without-SAND. As expected, the increase of the number of required sensor density, impacts the energy consumption of nodes and consequently, decreases the network lifetime.Fig 3(d) shows the results of the performance of SAND in ensuring sink connectivity for different neighborhood densities (for 20 and 50 neighbors in range) and sink resolution (for 0.5%, 1%, and 1.5% of the total number of nodes). As expected, SAND is less impacted by sink resolution when the neighborhood density increases. This is because the increase of neighborhood density, increases the number of forwarding candidates, and consequently, increases the probability of finding paths to sink nodes. Fig 3(e) shows the fraction of active and forwarding nodes

Table 1 :

 1 Energy state description

	State	Energy consumption	Activity	Provided service
	Sleep	very low	none	-periodically turns on the radio for receiving control msg
	Sensor-only	low	sensing	-sensing
				-periodically turns on the radio for receiving/sending control msg
				-sending local data, when needed
	Gateway	high	sensing	-sensing
			routing	-receiving/sending control msg
				-sending/forwarding data
	Router-sensor	high	sensing	-sensing
			routing	-receiving/sending control msg
				-sending/forwarding data
				-managing sensor density

Table 2 :

 2 Energy consumption

	Node	Radio	Energy	Estimated
	state Sleep	state radio OFF	consumption ± 10u	lifetime ∼ =3300
	Sensor-only	radio ON radio OFF	± 70u ± 200u	rounds ∼ =450
	Gateway and	radio ON radio ON	± 270u ± 1040u	rounds ∼ =96
	Router-sensor			rounds

Table 3 :

 3 Path length results.

	SAND	W/o-SAND

In[START_REF] Tsiatsis | Architecture strategies for energy-efficient packet forwarding in wireless sensor networks[END_REF], authors show that for typical sensor network scenarios, around 65% of all packets received by a sensor node need to be forwarded to other destinations.

Router-sensor and gateway nodes can also optimize local energy consumption by changing the power state of their memory and/or processor.

In the case of the reception of two contrary order messages, the priority is given to the "switch-to-sensor" messages.