Hyun-Gul Roh

Claudia-Lavinia Ignat

Rapid and Round-free Multi-pair Asynchronous Push-Pull Aggregation

Keywords: aggregation, gossip protocol, asynchronous computation, peer-to-peer overlay network calcul formel, base de formules, protocole, différentiation automatique, génération de code, modélisation, lien symbolique/numérique, matrice structurée, résolution de systèmes polynomiaux

As various distributed algorithms and services demand overall information on large scale networks, the protocols that aggregate data over networks are essential, and the quality of aggregations determines the quality of those distributed algorithms and services. Though a variety of aggregation protocols have been proposed, gossip-based iterative aggregations have outstanding advantages especially in accuracy, result distribution, topology-independence, and resilience to network churns. However, most of iterative aggregations, especially push-pull style aggregations, suffer from two synchronization constraints: synchronized rounds and synchronized communication. Namely, iterative protocols generally need prior configurations to synchronize rounds over all nodes, and messages should be exchanged in a synchronous way in order to ensure accurate estimates in push-pull or push-sum protocols. This paper proposes multi-pair asynchronous pushpull aggregation (MAPPA), which liberates the push-pull aggregations from the synchronization constraints, and pursues a way to accelerate the aggregation speed. MAPPA considerably reduces aggregation times, and shows an improvement in fault-tolerance. Thanks to topology independence, inherent from gossip mechanisms, and its rapidness, MAPPA is resilient to network churns, and thus suitable for dynamic networks.

Introduction

In large scale networks, such as peer-to-peer overlay networks, wireless sensor networks, and content delivery networks, various distributed services and algorithms demand to aggregate global statistic information. For example, cloud storage services should collect the information of disk capacity spread over their huge clouds; the number of active nodes need to be monitored by network management services; and load balancing algorithms will use current states of loads as inputs. Reflecting such strong demand, for the past decade, various aggregation protocols have been explosively proposed.

Aggregation protocols can be classified under two large groups: topology dependent and independent ones [START_REF]A survey of distributed data aggregation algorithms[END_REF]. Topology dependent protocols, e.g., TAG [START_REF] Madden | Tag: a tiny aggregation service for ad-hoc sensor networks[END_REF], need prior efforts to constitute specific routing topologies such as trees, graphs, or rings. If such a hardship is endured, this class of aggregations are efficient in message overhead, but inflexible to network churns or fragile to single points of failures such as node crashes.

On the other hand, topology independent protocols are flexible in deployment and resilient to network changes. There are various kinds of topology independent aggregations exhibiting different characteristics. For example, Sample& Collide [START_REF] Massoulié | Peer counting and sampling in overlay networks: random walk methods[END_REF] and Hop-Sampling [START_REF] Kostoulas | Decentralized schemes for size estimation in large and dynamic groups[END_REF] rely on probabilistic sampling technique and probabilistic polling technique, respectively. Due to their probabilistic natures, these two aggregations are inaccurate even in fault-free environments [START_REF] Merrer | Peer to peer size estimation in large and dynamic networks: A comparative study[END_REF].

Iterative aggregation protocols (also called averaging protocols by [START_REF]A survey of distributed data aggregation algorithms[END_REF]), such as push-sum [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF], push-pull [START_REF] Montresor | Robust aggregation protocols for large-scale overlay networks[END_REF][5], A1/A2 [START_REF] Mehyar | Asynchronous distributed averaging on communication networks[END_REF], and Flow-Updating [START_REF] Jesus | Fault-tolerant aggregation for dynamic networks[END_REF], compute the aggregation by exchanging periodic messages. Especially, gossip-based iterative protocols are scalable and reliable, and constrain no specific network topologies due to the characteristics of gossiping, which randomly chooses messages recipients from neighbors. Generally, iterative protocols are of considerable merits in accuracy, result distribution and resilience of network churns [START_REF]A survey of distributed data aggregation algorithms[END_REF] [START_REF] Merrer | Peer to peer size estimation in large and dynamic networks: A comparative study[END_REF].

This paper sheds new light on the push-pull style aggregations [START_REF] Montresor | Robust aggregation protocols for large-scale overlay networks[END_REF][5] [START_REF] Mehyar | Asynchronous distributed averaging on communication networks[END_REF] from a practical point of view. We strive to find a way to liberate aggregations from two synchronization constraints: one is posed to most of the iterative aggregations, and the other is specific to the push-pull aggregations. Ultimately, we pursue a practical aggregation which is rapid and easily deployable.

The first constraint is that most of iterative protocols require all the nodes over large networks to synchronize their rounds, meaning that all nodes should coordinate the starting point of every round. A round is a unit of the iteration, in which estimates are exchanged and updated. Round-based protocols are conceptually simple, but synchronizing rounds in real-world networks cannot be achieved immediately and incurs non-negligible overhead. According to [START_REF] Babaoglu | Firefly-inspired heartbeat synchronization in overlay networks[END_REF], it takes dozens of seconds to reduce the time difference between the first and the last starting points of each round within 100 ms. In other words, round-based protocols need to lay the ground for their bootstrapping, and the length of a round should be long enough to cope with such a time difference.

The second constraint is related to the synchronization of message passing. In push-pull aggregations, if messages are exchanged asynchronously, interferences among asynchronous updates cause damage to system mass, which is the sum of estimates located at all nodes. The system mass conservation is a key property for the correct aggregations in the iterative protocols [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF], and many efforts [START_REF] Mehyar | Asynchronous distributed averaging on communication networks[END_REF][19] [START_REF]Impacts of asynchrony on epidemic-style aggregation protocols[END_REF] [START_REF]Gossip-based asynchronous and robust aggregation protocol -a pessimistic approach[END_REF] have been made in order to satisfy this property in the presence of the asynchrony. However, they still disallow certain kinds of asynchronous updates because interferences among such updates could result in damage to the system mass.

This paper proposes an adapted push-pull protocol named multi-pair asynchronous push-pull aggregation (MAPPA), which is free from these two synchronization constraints. We address a simple property, pair mass conservation that enables MAPPA to isolate asynchronous updates for avoiding interferences among them. By virtue of this permission for asynchrony, we also Inria liberate MAPPA from synchronized rounds. Consequently, MAPPA needs no prior setup for synchronized rounds, and is easy to be deployed in any large scale networks.

Furthermore, we take another step for rapid aggregations. By adopting multiple concurrent pushes rather than a single one, i.e., multi-pair asynchrony, we can accelerate convergences of estimates significantly, compared to other iterative protocols. Concomitantly but considerably, fault-tolerance is also enhanced in MAPPA. In our evaluations, we will show the behaviors of MAPPA under various conditions, and present comparisons with some other approaches. The results show that MAPPA takes a fraction of the convergence times needed in other approaches. Bringing out the best of the rapid convergence, we present an asynchronous overlapped restarting technique that enables all nodes to maintain convergent estimates, and prove that MAPPA is advantageous to dynamic networks.

This paper is organized as follows. Section 2 defines our system model and two synchronization constraints. Section 3 gives a survey of related work regarding iterative aggregations. We address the pair mass conservation in Section 4, and then Sections 5 and 6 propose MAPPA and the asynchronous overlapped restarting technique. In Section 7, MAPPA is evaluated with various experiments, and we conclude the paper in Section 8.

Background

System model

This section presents a model of our gossip-based asynchronous aggregation protocol that will be used throughout the paper. Let N = {1, 2, • • • , n} be a set of n nodes composing a network, and G i ⊂ N be a set of neighbors to which node i gossips messages. Each node i ∈ N has a value v i that should be aggregated across the entire system, and maintains an estimate vi (t). This paper defines an estimate vi (t) as a function of time t because it is non-periodically updated whenever node i asynchronously receives pushes and pulls. This paper focuses on the average aggregation because it is a basis of various aggregations such as sum, count, product, or variance [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF]. For a set of the values of all the nodes v={v 1 , v 2 , • • • , v n }, the goal of the average aggregation is for each node i to obtain an estimate vi that is equal to the average v = 1 n ∀k∈N v k . Therefore, every estimate should converge to the average as follows:

vi ≈ 1 n ∀k∈N vk for ∀i ∈ N (1)
According to this formula, the aggregation is determined by the sum of estimates ∀k∈N vk , called the system mass. Kempe et al. [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF] addressed the system mass conservation as a property for the correct aggregation. In Section 4, we propose a more elaborative definition of the system mass conservation with a solution to preserving the property in the presence of asynchrony.

This paper focuses on the push-pull style aggregation in which updates carry out pairwise. Namely, each node i pushes its local estimate to a random neighbor in G i , and then a certain value is pulled from the neighbor. We denote a push and a pull message by push[p s ] and pull[p l ], where p s and p l represent the delivered values of the push and pull, respectively.

Two synchronization constraints

In this section, we identify two synchronization constraints of the push-pull aggregation.

Inria

The first constraint is related to the communication of pushes and pulls. Following the pushpull protocol of Jelasity et al. [START_REF] Montresor | Robust aggregation protocols for large-scale overlay networks[END_REF][5] that takes arithmetic means fairly on both sides, Fig. 1 shows an example of synchronous and asynchronous communications. Specifically, the push-pull aggregations can be distinguished into synchronous and asynchronous ones as follows:

• Synchronous protocol: Any push synchronizes with its corresponding pull message. In other words, as shown in Fig. 1-(a), after a node sends push[y 0 ], the node should wait for pull[x 0 ] that responds to push[y 0 ] without doing anything.

• Asynchronous protocol: While a node is waiting for a pull responding to a sent push, it can deal with some events of pairwise updates. Between an update of push-pull, three types of events can happen as illustrated in Fig. 1-(b):

e1) receiving a push from any node and responding to it with a pull, e2) sending a new push to any node, e3) receiving a pull of any previous sent push.

Note that e2 and e3 are reciprocal each other. For example, between the update of push

[y 0 ] -e3(pull[x 0 ]), push[y 1 ] corresponds to e2 while pull[x 0 ] is e3 between the update of e2(push[y 1 ]) -pull[x 1 ].
If the push-pull aggregation of Jelasity et al. [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF] is operated with the asynchronous communication, the system mass is damaged due to the interferences among pairwise updates. For example, at node 2 of Fig. 1-(b), e1 and e3 make the values of y that are used in the updates of the both-side of pull[x 0 ] and pull[x 1 ] be different, thereby interfering with each other. As such interferences cause errors in calculating arithmetic means on both-sides of a pull, the asynchronous aggregation cannot conserve the system mass as in Fig. 1-(b). In Section 4, we introduce a simple and practical property to liberate this synchronization constraint.

Another synchronization constraint is related to the round (also known as cycle), which is a time unit most of iterative aggregations [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF][5] [19][21][20] [START_REF] Jesus | Fault-tolerant aggregation for dynamic networks[END_REF] are adopting. Rounds have to be synchronized so as to proceed in a lock-step mode; in other words, the same round r should have physically identical starting and ending times at all nodes. As stated in Introduction, however, the round synchronization in real-world networks cannot be achieved immediately, and cannot avoid errors [START_REF] Babaoglu | Firefly-inspired heartbeat synchronization in overlay networks[END_REF]. The round-based push-pull aggregations are encouraged to complete a pairwise update in a round, and thus a push and a pull generated at round r should arrive to another node in the same round r. This constraint is hard to meet because of arbitrary propagation delays. The event types e2 and e3 defined above can be associated with the synchronized round: e2) sending multiple pushes to multiple neighbors in a round, e3) receiving an out-of-round push or pull.

In Section 3, we will examine how to deal with these events in existing iterative protocols.

In our proposed protocol, each node cyclically sends one or more pushes in parallel regardless of the completions of the previous pairwise updates. Besides, a push and a pull generated at a node are accepted by another node regardless of the receiver's state, meaning pairwise updates of each node proceeds independently without synchronization. To distinguish such characteristics with those of the round, this paper uses the term cycle.

Related Work

The aggregation protocols can be classified according to two perspectives: the network topologies and computation methods on which the algorithms reply [START_REF] Merrer | Peer to peer size estimation in large and dynamic networks: A comparative study[END_REF] [START_REF]A survey of distributed data aggregation algorithms[END_REF]. Different classes of aggregation protocols impose different restrictions and trade-offs when other distributed applications adopt them. Since our proposed protocol is a gossip-based push-pull aggregation that is irrespective of specific network topologies and based on iterative computations, this section focuses on the similar category of the aggregation algorithms.

According to the comparative works of [START_REF] Merrer | Peer to peer size estimation in large and dynamic networks: A comparative study[END_REF] and [START_REF]A survey of distributed data aggregation algorithms[END_REF], push-sum [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF], push-pull [START_REF] Montresor | Robust aggregation protocols for large-scale overlay networks[END_REF][5] [START_REF] Mehyar | Asynchronous distributed averaging on communication networks[END_REF], and Flow-Updating [START_REF] Jesus | Fault-tolerant aggregation for dynamic networks[END_REF] protocols belong to the category of iterative aggregations. They have advantages in accuracy, topology-independence, result distribution, and fault-tolerance, over other approaches, such as TAG [START_REF] Madden | Tag: a tiny aggregation service for ad-hoc sensor networks[END_REF], Sample&Collide [START_REF] Massoulié | Peer counting and sampling in overlay networks: random walk methods[END_REF] and Hop-Sampling [START_REF] Kostoulas | Decentralized schemes for size estimation in large and dynamic groups[END_REF]. However, as iterative aggregations need periodic message passing among nodes, the synchronization issues addressed in Section 2.2 are important. We, therefore, look into the existing iterative aggregations in terms of the synchronization issues.

Kempe et al. [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF] proposed a push-sum aggregation protocol, where nodes send only pushes. However, this protocol requires an acknowledgment for every push in order to cope with faults such as message loss. Using the values delivered with many pushes, nodes update local estimates at the end of every round. Although pushes can transfer with arbitrary delays, synchronized rounds are encouraged so that any push should arrive to another node in the same round as at the sending node [START_REF]Impacts of asynchrony on epidemic-style aggregation protocols[END_REF].

As stated in Section 2.2, Jelasity et al. [START_REF] Montresor | Robust aggregation protocols for large-scale overlay networks[END_REF][5] presented the synchronous push-pull aggregation protocol. Rao et al. [START_REF]Impacts of asynchrony on epidemic-style aggregation protocols[END_REF] applied asynchrony to the protocol of Jelasity et al. and the push-sum protocol. They permit loosely synchronized rounds that allow different nodes not exactly same time to begin any round r. Nevertheless, to some extent, the rounds should be synchronized so that messages generated at round r should be delivered to other nodes at the same round r; otherwise, out-of-round messages are ignored. Therefore, the two adapted protocols let the round length be long enough, and permit only the event type e1, but not e2 and e3 (see Section 2.2). As a result, interferences among updates are suppressed, but cannot be eliminated all, thereby admitting errors in estimates. In their comparison between the push-pull and push-sum protocols, the former is faster than the latter, but accuracy is impaired more seriously in the former.

Rao et al. presented two additional push-pull protocols [START_REF] Rao | A gossip-based asynchronous aggregation protocol for p2p systems[END_REF] and [START_REF]Gossip-based asynchronous and robust aggregation protocol -a pessimistic approach[END_REF] for asynchrony. Though the authors claim that rounds are asynchronous, these protocols also require the loosely synchronized rounds likewise as in their previous protocol [START_REF]Impacts of asynchrony on epidemic-style aggregation protocols[END_REF]. Instead, if a node receives any push and pull of a different round, it computes some recovery shares in order to resolve the interferences caused by asynchrony. The protocols are classified into optimistic [START_REF] Rao | A gossip-based asynchronous aggregation protocol for p2p systems[END_REF] and pessimistic [START_REF]Gossip-based asynchronous and robust aggregation protocol -a pessimistic approach[END_REF] ones according to when nodes update estimates. In the optimistic one [START_REF] Rao | A gossip-based asynchronous aggregation protocol for p2p systems[END_REF], nodes update estimates just after receiving pushes or pulls, but the pessimistic one [START_REF]Gossip-based asynchronous and robust aggregation protocol -a pessimistic approach[END_REF] updates the estimates at the completion of every round. The optimistic protocol can handle a number of e1 events pushed in the same round, while the pessimistic one permits only a single e1 in a round and abandons subsequent ones. Both of the protocols permit e3, but not e2, which means that a node can send only one push in a round.

Rao et al. encouraged the length of the loosely synchronized rounds to be as long as the maximum round trip time (RTT) 1 . For secure aggregation, the long round lengths were chosen in the papers [START_REF]Impacts of asynchrony on epidemic-style aggregation protocols[END_REF][19] [START_REF]Gossip-based asynchronous and robust aggregation protocol -a pessimistic approach[END_REF], i.e., about from 0.8 to 1.7 sec, and thus there is a limitation to accelerate convergence speeds.

Mehyar et al. proposed A1 and A2 algorithms in the distributed averaging domain, which is in principle equivalent to the distributed aggregation [START_REF] Mehyar | Asynchronous distributed averaging on communication networks[END_REF]; A1 is a push-pull type while A2 is a push-only one.

In A1 protocol, a node that is in the middle of a pairwise update blocks every e1 event and sends back a negative acknowledgment. As no overlapping updates are allowed, all the events e1, e2, and e3 could not happen in A1 protocol. Unlike the protocol of Jelasity et al. [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF] doing the homogeneous updates, a pair of nodes in A1 protocol updates their estimates heterogeneously; after one of the pair updates its estimate by using both of the estimates, the other node compensates the counterpart update. In fact, this pairwise update is similar to our proposed protocol's. However, they missed the significant aspect of such heterogeneous updates, which will be explained in Section 4, and thereby A1 pursues the synchronous communication by the blocking mechanism, though it needs no synchronized rounds.

A2 protocol indirectly computes estimates by using additional symmetric values between neighbors. Authors claim that maintaining a symmetric value for every neighbor enables to conserve the system mass in case of node crashes, but symmetric links need to be predefined among nodes. Hence, it is difficult to take advantage of the gossip mechanisms that make protocols topology-independent, scalable, and reliable. In A2, each node not only periodically broadcasts STATE messages containing its estimate to all its neighbors, but also send a REPLY message in order to update symmetric values. Though it is unclear how to treat e2 and e3 events in the paper, a node can send a REPLY again to the same neighbor after having received the TCP ACK of the previous REPLY. A2 is asynchronous because it requires no blocking constraints and no synchronized rounds like our proposed protocol. In Section 7.2, we compare our protocol with A2, and give a further analysis with Experiment 2.

Recently, Jesus et al. [START_REF] Jesus | Fault-tolerant aggregation for dynamic networks[END_REF] introduced Flow-Updating to enhance fault-tolerance. Flow Updating is progressive as it is resilient to message loss. Similarly to A2, Flow Updating uses symmetric values called flows. If a crashed node is detected by failure detectors in all its neighbors, the protocol has a way to recover from the damage of the system mass. However, implementing such a practical and instantaneous failure detector is not a simple issue [START_REF] Li | On the analysis of overlay failure detection and recovery[END_REF]; we will discuss this issue in Sections 6 and 7.

Flow-Updating requires synchronized rounds, in which flows and estimates should be symmetrically pushed to every pair of neighbors (push-only). Though the length of rounds in Flow-Updating can be taken as a half of RTT, round synchronization also imposes some restrictions on the deployment in real-world overlay networks. In addition, Flow-Updating must maintain symmetric links among neighbors, via which node i has to send its flow and estimate to node j if node j sends its ones in the same round. Therefore, before starting Flow-Updating, nodes in overlay networks should set up the symmetric links. This means that Flow-Updating needs a preliminary configuration and has a difficulty in being used in dynamic topology networks. In Section 7.2, Experiment 6 will illustrate such difficulty.

In Table 1, we summarize the constraints of the existing iterative aggregation protocols. Notice that there is no iterative protocol that is not only fully topology-independent, i.e., gossipbased, but also round-free and completely asynchronous. In Sections 4 and 5, we propose a gossip-based round-free push-pull aggregation protocol supporting asynchronous communication.

Roh & Ignat

Type

Protocols Topology Allowed Rounds dependency events push -only push-sum [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF] gossip none sync. Rao's push-sum [START_REF]Impacts of asynchrony on epidemic-style aggregation protocols[END_REF] gossip e1 loosely sync. A2 [START_REF] Mehyar | Asynchronous distributed averaging on communication networks[END_REF] symmetric async. round-free FU [START_REF] Jesus | Fault-tolerant aggregation for dynamic networks[END_REF] symmetric e1, e2 sync.

push -pull

Jelasity [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF] gossip none sync. Rao's push-pull [START_REF]Impacts of asynchrony on epidemic-style aggregation protocols[END_REF] gossip e1 loosely sync. Rao '10 [19] gossip e1, e3 loosely sync. Rao '11 [START_REF]Gossip-based asynchronous and robust aggregation protocol -a pessimistic approach[END_REF] gossip e1, e3 loosely sync. A1 [START_REF] Mehyar | Asynchronous distributed averaging on communication networks[END_REF] gossip none round-free Table 1: Constraints of iterative aggregation protocols

Pair Mass Conservation

Let us consider an asynchronous update precisely; in Fig. 2, between two nodes i and j, there are three timings t 1 , t 2 and t 3 ; (t 1 ) when node i sends a push with a parameter p s ; (t 2 ) when node j pre-updates vj and sends back a pull with a parameter p l ; and (t 3 ) when node i post-updates vi .

Regarding the estimates at these timings, we can present a simple property of a pairwise update.

Definition 1. [Pair mass conservation] For vi (t) and vj (t) that are the estimates of nodes i and j, the pair mass conservation holds on the pairwise update iff:

lim t→t - 3 vi (t) + lim t→t - 2 vj (t) = vi (t 3 ) + vj (t 2 ). (2)
In the above one-sided limits of estimate functions, t - 3 and t - 2 represent the times immediately before the updates. Hence, this definition means that a pairwise update, i.e., the pre-update and post-update occurring on the both sides of a pull, should conserve the mass of their estimates. In our proposed protocol, the pair mass conservation is ensured by delivering a pull with the following parameter p l :

p l ← vj (t 2 ) -lim t→t - 2 vj (t)
After that, node i subtracts p l from vi . Thus, regardless of the pre-update, the post-update can be defined as follows:

vi (t 3 ) = lim t→t - 3 vi (t) -p l = lim t→t - 3 vi (t) + lim t→t - 2 vj (t) -vj (t 2 )
Note that vj is updated at t 2 but until t 3 vi is not, which results in the change of the amount of the system mass between t 2 and t 3 . In the asynchronous communication, such a change of the system mass is inevitable, and the system mass would not be conserved transiently. For instance, in Fig. 1-(b), at t 1 before interferences happen, the system mass is not preserved as x 1 + y 1 + z 1 = 0.3 + 0.25 + 0.25 = 0.8. We consider that the rest of the mass 0.2 is migrating. This paper, therefore, introduces v on (t) as a global online value being in transit, which is also included in the system mass as follows: Definition 2. [System mass] System mass is defined as After a pre-update, the parameter of a pull, p l is added to v on , and conversely p l is subtracted from v on after a post-update. Then, we can present a definition of the system mass conservation for asynchronous protocols. Definition 3. [System mass conservation] For any times t 1 and t 2 (t 1 = t 2 ), the system mass conservation is ensured iff: M(t 1 ) = M(t 2 ).

M(t) = ∀k∈N vk (t) + v on (t). ( 3
)
Inria Node i Node j push[ ] pull[ ]
The system mass conservation can be guaranteed if every pairwise update satisfies the pair mass conservation. Intuitively, this also can be understood by the idea that pulls induce system mass to migrate among nodes via v on . Remind that pull[x 0 ] in Fig. 1-(b) conveys estimate x 0 that will be used in computing the arithmetic mean, but the post-update of e3 cannot exactly calculate the mass change in its corresponding pre-update due to asynchrony. Contrarily, in our approach pulls deliver mass changes caused by pre-updates, instead of estimates, and postupdates can exactly compensate the change. In other words, each of our pull and post-update based on the pair mass conservation involves only two nodes in a mass migration. Even if multiple updates are asynchronously mingled, each migration is isolated and never interferes with the others. We can prove the following theorem by tracing migrations of the mass. Theorem 1. If the pair mass conservation holds for every asynchronous update, the system mass conservation is guaranteed.

Proof. For any two times t 1 and t 2 (t 1 < t 2 ), assume M(t 1 ) = ∀k∈N vk (t 1 ) + v on (t 1 ) and M(t 2 ) = ∀k∈N vk (t 2 ) + v on (t 2 ). Given any pull[p l ] between node i and j, let t s be the time when node i invokes the pull[p l ], and t e be the time when node j receives the pull[p l ]. Then, the following four cases can affect M(t 1 ) and M(t 2 ):

• t s < t 1 ≤ t e ≤ t 2 : p l moves from v on to vj at t e .

• t s < t 1 < t 2 < t e : No mass moves.

• t 1 ≤ t s < t e ≤ t 2 : p l moves from vi to v on at t s , and after then moves from v on to vj at t e .

• t 1 ≤ t s < t 2 < t e : p l moves from vi to v on at t s .

RR n°8044

In any case, this pull does not change the system mass. Hence the system mass conservation is guaranteed.

In fact, the updates of A1 protocol also satisfied the pair mass conservation, but Mehyar et al. [START_REF] Mehyar | Asynchronous distributed averaging on communication networks[END_REF] apparently never recognized the property in terms of the asynchronous communication; hence, they provided even a blocking mechanism in order to prevent A1 from actual asynchronous communication (see Section 3). None of previous works [START_REF]Impacts of asynchrony on epidemic-style aggregation protocols[END_REF][19] [START_REF]A survey of distributed data aggregation algorithms[END_REF][21] recognized the property of A1. In this regard, it is worthy emphasizing the significance of recognizing the pair mass conservation, which is a basis of our proposed protocol making the best use of the asynchrony in the next Section.

Inria 5 Multi-pair asynchronous push-pull aggregation

The goal of the average aggregations can be written as

vi (t) ≈ M(t) n for ∀i ∈ N and t > 0
In other words, the estimates of all the nodes should reach the convergence on the average. In our protocol, pulls convey the changes of estimates, and v on (t) indicates the mass of ongoing pulls; hence, v on (t) should approach to zero in the stage of the convergence. To this end, the pre-update needs to be designed so that v on converge to zero. Obviously, taking an arithmetic mean of a pair of the estimates in the pre-updates can make v on converge to zero if estimates are getting equal.

Algorithm 1 Multi-pair asynchronous push-pull aggregation protocol

} else if(agg.mode = PULL){ // post-update vi ← vi -agg.v; } }
To boost the benefits of the asynchrony, we propose multi-pair asynchronous push-pull aggregation (MAPPA), which allows every node to send multiple pushes concurrently to different neighbors. MAPPA introduces m as the value of the multi-pair asynchrony. In Algorithm 1, PeriodicPushing method, which is called by each node every cycle, sends m pushes concurrently. Each pre-update takes an arithmetic mean of a pair of only 1/m of estimates, and adds it to the rest (m-1)/m of the estimate. Thus, the pre-update that node j receives p s = vi (t 1 ) at t 2 in Fig. 2 is computed as follow.

vj (t 2 ) = (m -1) m lim t→t - 2 vj (t) + 1 2 lim t→t - 2 vj (t) m + vi (t 1 ) m = lim t→t - 2 vj (t) + 1 2m vi (t 1 ) -lim t→t - 2 vj (t) (4)
In formula (4), the right term corresponds to the change in the updated estimate, which becomes the parameter of the responding pull. In Algorithm 1, the pre-update is presented in lines 14-18 inside EventReceiving method that is invoked upon arrival of messages. Since the post-update of line 20 satisfies the pair mass conservation, the system mass is conserved in MAPPA despite the multi-pair asynchrony. In Fig. 3, the asynchronous communication of MAPPA is illustrated for m=2, where we present the pushes and pulls related to only node a for simplicity's sake. At t 1 , node a sends two pushes at once to neighbors c and g (e2), and asynchronously receives their responding pulls. Node a receives two pushes from nodes b and e, and responds to them with pulls (e1). At t 2 when a cycle passes, node a can send m=2 pushes again regardless of cycles of the other nodes (round-free), even if some pulls replying to the previously sent pushes, e.g., the pull from node c, have not yet arrived (e3). In result, MAPPA is round-free and permits all the asynchronous event types.

Although each node chooses different m, estimates can converge to the correct value. Nevertheless, if a node pushes its estimates in parallel to m neighbors by PeriodicPushing method, it is natural that each of the m neighbors uses the same m in EventReceiving method because it is considered that m parallel arithmetic means are taken by dividing the estimate into m pieces. If each node uses different m, it should send every push with its m. Therefore, we fix the values of m at all the nodes for convenience sake and for simplicity in the analysis.

Inria

In principle, the average aggregation comes close to the average by distributing extremely segmentalized shares (pieces) of the initial values v={v 1 , v 2 , • • • , v n } to all the nodes. MAPPA accelerates the convergence by encouraging an estimate to be more extensively distributed to other nodes and to be mixed with numerous shares. In Fig. 3, at the second cycle t 2 , the estimate of node a would be reconstituted with the shares of the values of nodes b, e, and g, but not yet c.

Just for analysis purpose, let us assume that cycles are synchronized and every pairwise update is completed at the end of each cycle. Initially, an estimate of each node has a single full share of its own initial value. By m pairwise updates in a cycle, an estimate is mixed with the shares of m estimates belonging to the neighbor set G. On the other hand, as every node sends m pushes, a node asymptotically receives m pushes from other nodes on the assumption that each node has uniformly random neighbors. As a result, at the end of a cycle, the estimate of a node includes the shares of 2m+1 estimates of the previous cycle. Let S m (c) be the function that returns the number of shares of initial values which an estimate includes at cycle c, permitting duplicates of initial values. Based on these inferences, at each cycle, S m (c) can be derived as a geometric sequence:

S m (0) = 1 S m (1) = (2m + 1)S m (0) = (2m + 1) S m (2) = (2m + 1)S m (1) = (2m + 1) 2 • • • S m (c) = (2m + 1)S m (c -1) = (2m + 1) c (5)
According to this formula, the number of shares grows exponentially with growth rate m. Thus, a larger value of the multi-pair asynchrony m leads to a more rapid convergence. For example, regarding m=1, 4, and 13, S 1 (c) = 3 c , S 4 (c) = 9 c = 3 2c , and S 13 (c) = 27 c = 3 3c which means MAPPAs with m=4 and 13 could take half cycles and one-third cycles of m=1, respectively, to include the same number of shares. Indeed, shares are more rapidly mixed than the indication of the formula because updates are asynchronously (immediately) reflected on estimates. In Fig. 3, when node a receives a push from node b, the estimate of node a has already included the shares of nodes e and g; hence, the pre-update of the push is delivered with those shares. Though such nondeterministic cases are difficult to be modeled by a formula, Experiment 4 in Section 7.2 shows that MAPPA with m=4 takes far less cycles than the expectation of formula [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF].

The initial values in v = {v 1 , v 2 , • • • , v n } can be selected as shares, allowing duplicates. The probability for a certain value in v to be chosen depends on the characteristics of network topologies. If the underlying topology is a purely random graph, built according to the Erdős-Rényi (ER) model [START_REF] Erdős | On the evolution of random graphs[END_REF], any initial values could be selected with a similar probability; thus, estimates can rapidly converge. Meanwhile, if the topology is a locally clustered graph such as Watts-Strogatz graph with β = 0 [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], geographically dispersed initial values are difficult to be mixed into an estimate, which ends in a slow convergence (see Experiment 5).

Meanwhile, under the asynchrony, some pathological problems impeding convergences are also observable as shown in Fig. 4. First, look at the two pairwise updates between nodes 1 and 2 (see the chunky arrows). If two pairwise updates cross, both of the effects are offset each other; in the post-updates, nodes 1 and 2 recovers as much values as the ones changed by the corresponding pre-updates. Besides, if the initial deviation of estimates is large and if the cycle of sending pushes is much shorter than the period of a pairwise update, a respectable amount of the system mass might hover in transit. If M(0)=1 in Fig. 4, v on (t 1 )= 31 32 at t 1 due to the ongoing pulls. As subsequent updates cannot reflect the whole system mass, estimates may oscillate without convergence (see Experiment 3). To make things worse, if some of those pulls accompanying a large portion of system mass are lost, the system mass is seriously damaged, which means the aggregation is fault-intolerant.

Consequently, various factors, such as multi-pair asynchrony values m, cycle lengths, and network topologies, should be considered for the convergence. Since analytic analysis has a limitation on the consideration of all of those factors, we will present various evaluation results in Section 7.

Inria 6 Asynchronous overlapped restarting technique

Aggregations can be used for continuous monitoring that unceasingly provides effective estimates. In dynamic systems, however, network churns incurred by crashes and inflows of nodes lead to changes in the system mass. The mass added by a newly joined node is spontaneously reflected to the aggregation. Though the sign-off technique can deal with voluntary departures of nodes [START_REF]Gossip-based asynchronous and robust aggregation protocol -a pessimistic approach[END_REF], a sudden crash of a node results in damage of the system mass, which cannot be recovered in the push-pull aggregation by itself. To recover from the damaged mass of dynamic networks, Jelasity et al. proposed the restarting technique [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF].

Although A2 protocol [START_REF] Mehyar | Asynchronous distributed averaging on communication networks[END_REF] and Flow Updating [START_REF]A survey of distributed data aggregation algorithms[END_REF] can correct damage of crashes by maintaining symmetric values (see Section 3), such a correction is only possible when every node can detect failures of its neighbors. However, it also takes a certain amount of time to detect failures securely, as stated in the paper [START_REF] Li | On the analysis of overlay failure detection and recovery[END_REF], after then additional time is needed for estimates to re-converge to the corrected one. If the convergence time from restarting is shorter than the sum of the failure detection and re-convergence times, the restarting technique might be effective rather than A2 and Flow Updating.

In the restarting technique of Jelasity et al., all nodes have to synchronize their restarts based on epoch, which is a fixed number of rounds. As no synchronized rounds are used, MAPPA restarts aggregations asynchronously based on hops. An instance of an aggregation records hops which increase whenever sending a push. If the hop of a local instance is different from the one of any received push or pull, the larger one becomes the hops of the local instance and the responding pull.

Instead of restarting a new instance in series, we let two instances of aggregations to overlap their lifetimes so that a new instance should warm up for a certain period. Note that all of the iterative aggregations go through a disequilibrium in which nodes have unstable and untrustworthy estimates. To avoid such a disequilibrium, we let each node to prepare two instances in an aggregation called adult and child, and only the value of adult is used as an estimate. Initially, both of adult and child begin the same pairwise updates. If a child reaches to a predefined number of hops, the child is promoted to adult, and a new instance is generated so that a child should restart with its initial value.

An aggregation containing an adult and a child has a generation number. If a node promotes its child, it augments the generation number of its aggregation. If a node receives a push or a pull with an aggregation of a higher generation number, it tunes its aggregation to the received one by promoting its current child and restarting a new child. In the opposite case that a node receives a push of a lower generation number, the node likewise tunes the aggregation of the responding pull to its own aggregation. If a node receives a pull of a lower generation number, its aggregation is updated by considering the generation number of the pull.

In this way, MAPPA can asynchronously restart new instances in the overlapping manner. This can ensure all the nodes monitor convergent estimates most of the times. In Experiment 7, we will show the effects of this asynchronous overlapped restarting technique and compare it with the behaviors of Flow-Updating protocol.

Evaluation

Experimental setup

We implemented MAPPA with the event-driven simulator, Peersim [START_REF] Montresor | Peersim: A scalable p2p simulator[END_REF]. Every node sends pushes on the same length of cycle, but the cycles of nodes are not synchronized. We let the propagation latency of any push or pull to be distributed uniformly between 50 and 350 ms. Considering that about 90% of messages complete a round trip within 500 ms [START_REF] Lee | Has internet delay gotten better or worse?[END_REF], this unidirectional latency is reasonable and long enough.

In our evaluation, the count aggregation, which estimates the network size n, is carried out because it is the most representative and extreme case of the average aggregation [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF]. It begins over the network which has only one node with value 1 and the other n -1 nodes with value 0. As the aggregation proceeds, each estimate approaches to the average 1/n; thus, we can obtain the network size by taking the reciprocal.

We have MAPPA run generally on Erdős-Rényi (ER) random graphs [START_REF] Erdős | On the evolution of random graphs[END_REF] as underlying networks, but also evaluate Watts-Strogatz (WS) model networks [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] in Experiment 5. Most of our experiments are performed with n=1000 nodes, and every node has twenty gossip neighbors, i.e., |G|=20. Following the gossip principle, each node sends pushes to only m neighbors in G. The size of G rarely affects the performance of MAPPA, which can be identified in Experiment 2. Instead, a large number of neighbors reinforces reliability against node crashes. According to the paper [START_REF] Kaashoek | Koorde: A simple degree-optimal distributed hash table[END_REF], the network where each node has log n neighbors can avoid a partitioning, even if half nodes suddenly die. To emulate dynamic topologies in Experiment 5 and to eliminate crashed neighbors in Experiment 7, we use Simple Newscast [START_REF] Jelasity | The peer sampling service: experimental evaluation of unstructured gossip-based implementations[END_REF].

We have conducted each experiment 30 times with different random seeds, and took averages of the estimates of the 30 runs for each individual node. This section presents two sorts of timeseries graphs: estimates distribution graph and coefficient of variation of the root-mean-square deviation, abbreviated to CV(RMSD), graph. The former illustrates how estimates diverge and converge along time by marking spots of the reciprocals of estimates of all nodes. Meanwhile, CV(RMSD) is a normalized RMSD to a correct mean, i.e., RMSD/v. Unlike the standard deviation relying on the mean of given populations, RMSD is a deviation from a given mean v, and is computed by the following formula.

RM SD(t) = n i=1 (v i (t) -v) 2 n (6)
CV(RMSD) is a good measure to compare convergence speeds; the faster the values of CV(RMSD) approach to zero, the more rapid its convergence speed is. This section presents seven experiments with the following six parameters on the count aggregations.

• n: the number of nodes in the network.

• c: the cycle length.

• m: the multi-pair asynchrony value.

• e: the ratio of message loss in delivery.

• tc: the length of the cycle at which the network topology changes by Simple Newscast protocol. If tc = ∞, network topology is static.

• h: the number of hops to restart a child instance (see Section 6).

The parameters fixed in each experiment are specified in the caption of the graph of each result. Let us call the asynchronous push-pull aggregation following Jelasity et al. as "single fair asynchronous push-pull aggregation (SFAPPA)" because each node sends a single push and both of nodes fairly update their estimates by arithmetic means. As interferences among asynchronous updates hinder SFAPPA from satisfying the system mass conservation, all the estimates converge to incorrect values, as shown in estimates distribution graphs of Fig. 5. As a result, high values of CV(RMSD) is lasting in the convergence state because (v i (t) -v) 2 in formula ( 6) does not approach to zero.

In meantime, our proposed protocol MAPPA always converges to the correct network size thanks to the pair mass conservation. Notice that in the convergence state, due to the postupdate wherein differences are subtracted, estimates can be negative; hence, as estimates oscillate between wider range, MAPPA with m=1 somewhat slowly converges than SFAPPA. Surprisingly, convergence speeds are significantly improved if a node concurrently sends multiple pushes. If m=4, it takes only less than 5 sec to reach the CV(RMSD) to 0.01, while m=1 takes more than 13 sec. We compare MAPPA with some other aggregation protocols. As a comparison group, A2 and Flow-Updating are chosen because each of them is, respectively, the only round-free asynchronous protocol and one of the up-to-date protocols. Since these two protocols exchange messages only through predefined symmetric links, we predefined a set of symmetric links SL for each node (see Section 3). We run the two protocols over the networks of |SL|=4 and |SL|=8 utilizing all the links. On the other hand, MAPPA works on asymmetric networks, wherein each node has a set of neighbors G. We constraint |G|=4 for the sake of fairness, and each node pushes to only m=1 or m=4 neighbors. It is worthy noting that the performance of |G|=4 is similar to that of |G|=20, i.e., the default size of G in other experiments.

Roh & Ignat

According to the paper [START_REF] Mehyar | Asynchronous distributed averaging on communication networks[END_REF], A2 requires two parameters γ and φ for updating estimates and symmetric values. The authors claim they should satisfy the conditions 0 < γ < 1 |SL|+1 and 0 < φ < 1 2 in order to achieve the convergence, but no exact values were recommended in the paper. Moreover, it is unclear whether each node pushes REPLY messages to multiple links or randomly chosen one. After implementing A2 with event-driven Peersim, we have tried to tune the protocol, and found out two facts not given in the paper [START_REF] Mehyar | Asynchronous distributed averaging on communication networks[END_REF]. First, concurrent pushing to multiple neighbors reduces convergence time also in A2. Second, even if the conditions of the two parameters hold, estimates frequently diverged. Instead, we found that if γ = 1 and φ = 1 |SL| , A2 can always achieve more rapid and stable convergence. In fact, these conditions make A2 be similar to MAPPA.

In A2 protocol, we make REPLY messages toward each neighbor be propagated like a relay race; that is, each node sends a new REPLY immediately after receiving an ACK of the previous REPLY. Estimates are accompanied with REPLY and ACK and updated every 100 ms. In Flow-Updating, we let the round length be 500 ms so that messages of the maximum 350 ms delay should be delivered even if rounds are slightly out of step.

Fig. 6 shows that MAPPA is faster, despite m=1, than the other protocols. Like m of MAPPA, a larger |SL| of A2 leads to a more rapid convergence. Interestingly, Flow-Updating is much faster with |SL|=4 than with |SL|=8; namely, parallel updating rather impedes convergences. For rapid aggregations, Flow-Updating would need to constitute network topologies of few links, but of short node-to-node distances (see Experiment 5). However, since overlay networks need enough links to avoid a partitioning against network churns, Flow-Updating Inria could encounter a tug-of-war between reliability and performance. In any case, even if message overhead is considered and the round synchronization time is not included, MAPPA with m=4 outperforms all the other aggregation protocols. The result of Fig. 7 indicates that cycle lengths are a sensitive factor affecting convergence speeds. As aforementioned in Section 5, if cycles are too short, aggregations heavily go through the pathological problems such as excessive wafting of the system mass to v on ; hence, convergences are delayed, or estimates rather diverge as illustrated in the graph of c=100 ms in Fig. 7-(a) where m=1. If m=4, as segmentalized estimates are distributed to more nodes, negative effects are slightly suppressed; thus, even under c=100 ms, MAPPA with m=4 converges. In any case, the convergence speeds increase to some degree of cycle lengths, but there exist certain cycle lengths when convergence speeds go into reverse; regarding m=1, the cycle length of the fastest convergence speed is c=550 ms, and then longer cycle lengths make convergences slower.

Meanwhile, we observed that the convergence with 550 ms cycle insignificantly is faster than that of 400 ms cycle over a static topology (tc=∞), but over the dynamic topology (tc=10 sec) the convergence is faster with 400 ms cycle than with 550 ms one as shown in Fig. 7-(b). According to additional experiments, against the propagation delay of 50∼350 ms, MAPPA with c=400 ms is generally fastest regardless of multi-pair asynchrony (m > 1) and network topologies. As a result, we choose 400 ms as a default cycle length. The effects of dynamic topologies will be precisely discussed in Experiment 5. Clearly, Fig. 8-(a) proves that multi-pair asynchrony can improve convergence speeds. As discussed in Section 4, the convergences are accelerated more than the prediction of formula (5): S m (c) = (2m + 1) c . For example, the rise of m from 1 to only 2 almost halves the cycles required to reach the same convergence states. However, according to the formula, we can infer that increasing m logarithmically reduces c required to have the same number of shares. In other words, as m is getting larger, the amount of the reduction in convergence times declines sharply. Therefore, m should be chosen considering the trade-off between performance and message overhead that is proportional to m; so, we use m=4 as default in our evaluation.

Roh & Ignat

Network size has a weaker correlation with convergence speeds than the multi-pair asynchrony as shown in Fig. 8-(b). Though a larger network converges a little slowly, the inclinations of CV(RMSD) graphs are invariable with respect to n. Considering the results of Fig. 8-(b), it is highly expected that the graphs are horizontally shifted to the right proportionally to log n. To enhance scalability and reliability in overlay networks, gossip mechanisms encourage topologies to be altered dynamically [3][4]. In this experiment, we make each node dynamically change its neighbors every tc second by the Simple Newscast protocol [START_REF] Jelasity | The peer sampling service: experimental evaluation of unstructured gossip-based implementations[END_REF]. Fig. 9-(a) shows that although too frequent changes of topologies retard the latter half convergence, the delays of the primary stage are negligible. As stated in Experiment 3, the cycle length c influences convergence in dynamic topologies. Short cycle lengths make convergence speeds almost identical, but with long cycle lengths the latter half of convergences, at which enough accuracy is already secured, is slightly slacker. Characteristics of network topologies are crucial to the convergence time. Our evaluations have been conducted over the topologies following Erdős-Rényi (ER) model [START_REF] Erdős | On the evolution of random graphs[END_REF]. ER model produces purely random graphs with a short average node-to-node distance and a small clustering coefficient. Watts and Strogatz addressed small world properties that many real-world networks have a small average node-to-node distance, but a higher clustering coefficient than the graphs of ER model [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. They presented Watts-Strogatz (WS) model, in which nodes are wired in the shape of a ring lattice so that random graphs should have a high clustering coefficient. The model also introduced a parameter β, which is a probability to rewire any pair of randomly selected nodes. If β=0, no nodes are rewired, and thus random graphs have a long average node-to-node distance. If β=1, all nodes are randomly rewired, thereby producing pure random graphs similar to those of ER model. In Fig. 9-(b), aggregations are performed over ER and WS random graphs. With respect to β of the WS model, convergences take on significantly different aspects. If β=0, estimates hardly converge despite a large m. Though aggregations succeed in convergence for β > 0, there are limits, correlating with β, in reducing convergence times. If β=0.15 and β=0.3, the convergence speeds are no longer improving for m ≥ 2 and m ≥ 3, respectively. Therefore, we can presume that networks of WS graphs have maximum feasible convergence speeds with respect to β, and MAPPA can make the best use of the networks. However, before the speeds are saturated in the WS graphs, i.e., m < 2 and m < 3 for β=0.15 and β=0.3, respectively, for equal m, the aggregations over the WS graphs almost coincides with the aggregation over the ER graph regardless of β; e.g., for m=1, the aggregation over the ER graph almost coincides with those over the WS graphs of β=0.15 and β=0.30. MAPPA makes a significant improvement in fault-tolerance. To show the effects of message loss, we drop 5%, 10%, and 20% of messages against different levels of multi-pair asynchrony. In Fig. 10, estimates of 1000 nodes, which are obtained by averaging 30 runs per node, are distributed for different fault ratios. Besides, a boundary of each distribution is also marked, which indicates the maximum and minimum of estimates any node has along time without averaging 30 runs. Regardless of fault ratios, estimates always converge to a certain value, but a higher fault ratio leads to a larger deviation of convergence values from the correct average. Nevertheless, as we can identify from the boundaries, a larger m remarkably reduces the deviation. Such an improvement in the fault tolerance is originated from the fact that the parameters of pulls are getting smaller as m grows, thereby mitigating the damage of system mass against message loss.

Meanwhile, note that the converged estimates averaging 30 runs nearly approach to the correct value. Jelasity et al. enhanced accuracy in the presence of faults by averaging estimates of multiple instances [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF]. Our results prove that the technique is still effective in MAPPA. We compare MAPPA and Flow-Updating (FU) with a scenario of continuous monitoring over a dynamic network. In this scenario, there are initially 1000 nodes, and we impose three types of network churns for 200 seconds as below:

• Sudden churn: At 25 sec, 400 random nodes suddenly crash. After then new 400 nodes join the network at 50 sec.

• Gradual churn: From 75 sec to 80 sec, 80 random nodes gradually crash every second. After then new 80 nodes join gradually every second from 105 sec to 110 sec.

• Mixed churn: At 135 sec, the crashes of 400 random nodes coincide with the inflows of new 200 nodes. After then 200 random nodes crash, and simultaneously new 400 nodes join at 160 sec.

We run MAPPA and Flow-Updating under different conditions reflecting their characteristics. MAPPA restarts a child instance whenever its hop count encounters h=35 and h=50 (see Section ). Meanwhile, we let each node of Flow-Updating be connected along maximum 4 and 8 symmetric links, i.e., |SL|=4 and |SL|=8, in advance, and the links are fully utilized to exchange messages every 500 ms round. In the case of the inflows, new nodes are connected so that |SL| of each node should not exceed the maximum symmetric links, though those connections are impossible without global topology information.

Fig. 11 shows the results. In graph (a), we compare CV(RMSD) of MAPPA and Flow-Updating for the message loss ratio e=0.0. Generally, MAPPA has more accurate estimates over the dynamic networks. The other graphs present the estimates distributions; graphs (b)-(e) for e=0.0 and graphs (f)-(i) for e=0.1. In graphs (b), (c), (f) and (g), MAPPA allows the majority of nodes to have nearly convergent estimates thanks to the asynchronous overlapped restarting technique, while estimates of Flow-Updating are divergent most of times as shown in graphs (d), (e), (h) and (i).

In detail, MAPPA can instantly compute the initial network size. If MAPPAs with h=35 and h=50 meet the crashes of the sudden and gradual churns, they reflect them after about 10 and 15 seconds, respectively. Those relatively long time-lags are originated from the warmingup time of the overlapped restarting technique. Contrarily, the large inflows of the sudden and gradual churns are caught up with by MAPPA in an instance. In the case of the mixed churn, the inflow hidden by a large crash immediately increases the estimates. Since the system mass of 400 nodes, each of which estimate is about 0.001, is vanished, the remained system mass, about 0.6, is distributed to the new 200 nodes, and thus the estimates soars around 800/0.6≈1333. After restarting, the system mass is reset to 1. Likewise, at the end of the mixed churn, the similar effects occur. In MAPPA, hop counts affect the responsiveness against the crashes, but take no effects on inflows.

Flow-Updating, at the beginning, takes longer times to obtain effective estimates than MAPPA; if |SL|=8, nodes can hardly have convergent estimates up until the sudden churn. Like MAPPA, Flow-Updating by itself cannot reflect any crash. In these experiments, a node regards its neighbor as crashed one if it receives no message subsequently 8 times, i.e., 4 seconds. We took this specified number of times because failures were falsely detected in the presence of 10% of message loss if the number of times is less than 8. When wholesale nodes randomly die at the beginning of the sudden and gradual churns, some nodes were isolated over the network of |SL|=4, i.e., network partitioning. As a result, the estimates fail to converge during the sudden and gradual churns for |SL|=4. In the network of |SL|=8, partitioning can be avoided, but the overall aggregation is getting slower. Regarding the inflows of the sudden and gradual churns, convergence of Flow-Updating is relatively faster than at its initial stage, but still slower than MAPPA. Interestingly, the gradual inflows make the estimates more divergent than the sudden inflow, and thus more time is spent on re-converging. In the case of the mixed churn, convergence of the end is faster than that of the beginning.

We also conducted the same experiments with 10% message loss (e=0.1). MAPPA has aggregation errors in convergent estimates, but the errors seem not to seriously distort the tendency of changes of the network size. In Flow-Updating, message loss retards the convergence, and thus effective estimates are barely obtained by the end of the churns. Nevertheless, if networks are unchanged for a long time, Flow-Updating can converge to the correct network sizes despite message loss.

To sum up, MAPPA outperforms Flow-Updating in convergence speeds, even if the restarting technique is used. The overlapped restarting technique rather enables all nodes to maintain convergent estimates. We expect that this property is useful because algorithms operating on distributed nodes can use almost convergent aggregated data as inputs by MAPPA. Meanwhile, in this experiment, we identify that network churns might demand on Flow-Updating additional configurations to repair symmetric links; thus it is not completely topology independent. Addi-tionally, the efforts to synchronize rounds would be also required to begin Flow-Updating over large networks. Nevertheless, Flow-Updating is an innovative approach because it can compute correct estimates in spite of message loss. In conclusion, MAPPA is in better position over dynamic networks while Flow-Updating is better in faulty environments over static networks.

Discussion on message overhead

In our evaluation, the message overhead of MAPPA, i.e., the number of messages for a certain period of time, is comparable to that of other iterative aggregation protocols A2 and Flow-Updating, because they also send periodic messages in parallel to multiple neighbors. However, from the cost-effective point of view MAPPA is superior to the other approaches, as shown in Experiments 2 and 7.

In MAPPA, the number of messages along time t follows the formula: N M (t) = 2mnt/c. Apparently, as the level of the multi-asynchrony increases, message overhead with respect to a specific time rises. For instance, if m=4, the overhead is 4 times higher than that with m=1 after the same time t. However, the message overhead required to achieve a certain level of accuracy is acceptable in spite of m > 1. To illustrate, let us consider the time to reach the accuracy CV(RMSD)(t) = 0.01 in Fig. 8-(a). For each of m=1, 2, and 4, it takes about t=13.5 sec, 6.2 sec, and 4.5 sec, respectively. According to the above formula, MAPPAs with m=2 and m=4 require 91% and 133% of messages used in MAPPA of m=1 reaching CV(RMSD)(t)=0.01. Therefore, if the aggregation is just one-off event that computes a predefined accuracy level of estimates, MAPPA with an appropriate m incurs affordable overhead, but provides considerable benefit not only in the convergence time but also in the fault-tolerance, as addressed in Experiments 4 and 6.

Inria 8 Conclusion

This paper proposed the gossip-based multi-pair asynchronous push-pull aggregation protocol (MAPPA) that allows asynchronous communication of push-pull style updates and requires no synchronized rounds. We introduced the pair mass conservation as a property that ensures the system mass conservation by isolating migrations of the system mass incurred by asynchronous updates. Based on this property, we addressed the multi-pair asynchrony, which enables MAPPA significantly to reduce convergence times and to enhance fault-tolerance to message loss. Since MAPPA is round-free and follows the principles of gossip mechanisms, it is completely topology independent and unconstrainedly deployable in large scale networks. In addition, we also suggested the asynchronous overlapped restarting technique that can provide mostly convergent estimates in dynamic networks. We have showed these achievements with a number of experiments and comparisons with other iterative protocols. The comparisons show that MAPPA holds a dominant position in the practicality and performance, compared to other iterative aggregation protocols.

Figure 1 :

 1 Figure 1: An example of synchronous and asynchronous aggregations. The estimates of nodes 1, 2, and 3 are x, y, and z. In (b) asynchronous protocol, system mass is not conserved.

Figure 2 :

 2 Figure 2: Asynchronous pairwise push-pull update.

Figure 3 :

 3 Figure 3: Asynchronous communication of MAPPA for m = 2. Only the pushes and pulls associated with node a are given.

Figure 4 :

 4 Figure 4: Pathological problems of asynchronous pairwise updates. Assume that except node 2, all the other nodes have initial value 0.

Inria

7. 2 Figure 5 :

 25 Figure 5: [Exp. 1: n=1000, c=400ms, e=0.0, tc=∞, h=∞] Estimates distribution graphs (left y-axis) and CV(RMSD) graphs (right y-axis) of MAPPA and single fair asynchronous push-pull aggregation (SFAPPA).

Figure 6 :

 6 Figure 6: [Exp. 2: n=1000, c=400ms, e=0.0, tc=∞, h=∞] CV(RMSD) graphs of MAPPA, A2, and Flow-Updating.

Experiment 3 :Figure 7 :

 37 Figure 7: [Exp. 3: n=1000, e=0.0, tc=10 sec, h=∞] CV(RMSD) graphs with respect to cycle lengths c.

Experiment 4 :

 4 The effects of multi-pair asynchrony and network size[Fig. 8]

Figure 8 :

 8 Figure 8: [Exp. 3: c=400 ms, e=0.0, tc=∞, h=∞] CV(RMSD) graphs with respect to different levels of multi-pair asynchronism and different network size.

Experiment 5 :

 5 The effects of the network topologies[Fig.9]

Figure 9 :

 9 Figure 9: [Exp. 4: n=1000, c=400 ms, m=4, e=0.0, h = ∞] CV(RMSD) graphs with respect to network topologies.

Figure 10 :

 10 Figure 10: [Exp. 5: n=1000, c=400ms, tc=∞, h=∞] Estimates distribution graphs with respect to different message loss and multi-pair asynchrony.

Experiment 7 :

 7 Continuous monitoring of a dynamic network[Fig. 11]

Inria

6

 6

Figure 11 :

 11 Figure 11: [Exp. 6: c=400 ms, m=4, tc=5 sec] MAPPA and Flow-Updating in dynamic networks

RR n°8044

(RTT) According to the recent study[START_REF] Lee | Has internet delay gotten better or worse?[END_REF], 0.2, 0.5, and 1 sec are taken for about 50%, 90%, and 95% of messages to complete a round trip, respectively. The maximum RTT is far longer than 1 sec.

Roh & Ignat


Farah Mourad
email: farah.mourad@utt.frhichem.snoussi@utt.fr

Hichem Snoussi

Michel Kieffer
email: kieffer@lss.supelec.fr

Cédric Richard
email: cedric.richard@unice.fr

Robust interval-based localization algorithms for mobile sensor networks

Keywords: connectivity measurements, interval analysis, localization outliers, sensor networks, set-membership estimation

This paper considers the localization problem in mobile sensor networks. Such a problem is a challenging task, especially when measurements exchanged between sensors may contain outliers, i.e., data not matching the observation model. This paper proposes two algorithms robust to outliers. These algorithms perform a set-membership estimation, where only the maximal number of outliers is required to be known. Using these algorithms, estimates consist of sets of boxes whose union surely contains the correct location of the sensor, provided that the considered hypotheses are satisfied. This paper proposes as well a technique for evaluating the number of outliers to be robust to. In order to corroborate the efficiency of both algorithms, a comparison of their performances is performed in simulations using Matlab.

I. INTRODUCTION

M

OBILE Sensor Networks (MSNs) have recently emerged as a challenging research field. A MSN consists of a large number of low-cost smart sensors with limited computational capacities and energy resources [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF]. Due to the lack of a fixed infrastructure in MSNs, the sensors are able to move in an uncontrolled manner.

For this reason and since sensed data are related to the locations of the sensors in almost all MSN applications, many researchers have focused on the localization problem. A first solution for sensor localization is to equip all sensors with Global Positioning Systems (GPS) [START_REF] Hofmann-Wellenhof | Global Positioning System: Theory and practice[END_REF]. However, this solution is non-practical in MSNs, since GPS are expensive, high energy consuming and having great sizes. The alternative solution consists of equipping a few number of sensors with GPS receivers. These sensors, aware of their locations, are called anchors. The remaining sensors, called non-anchor nodes or simply nodes, have unknown locations, and hence they need to be localized.

Many anchor-based algorithms have been proposed for sensor localization. For instance, Doherty et al. [START_REF] Doherty | Convex position estimation in wireless sensor networks[END_REF] propose a centralized technique for position estimation. Localization in [START_REF] Doherty | Convex position estimation in wireless sensor networks[END_REF] is formalized as a convex optimization problem, having connectivity measurements between sensors as constraints. In [START_REF] Capkun | GPS-free positioning in mobile ad-hoc networks[END_REF], [START_REF] Niculescu | Ad-hoc positioning system (APS)[END_REF], [START_REF] Savarese | Locationing in distributed ad-hc wireless sensor networks[END_REF], different approaches requiring few anchors have been proposed. Local maps with relative positions are constructed using measured distances between nodes and their neighbors. A combination of these maps with known positions of anchors leads to absolute positions. Nevertheless, these techniques are not very robust, because of errors accumulation while combining the maps. Authors in [START_REF] Moore | Robust distributed network localization with noisy range measurements[END_REF] propose a distributed static algorithm, where each node defines its position as the center of all observed anchors. In a different scenario [START_REF] Galstyan | Distributed online localization in sensor networks using a moving target[END_REF], Galstyan et al. propose an online distributed technique, where nodes use their detection of a moving target to update their position estimates. Blatt and Hero [START_REF] Blatt | APOCS: a rapidly convergent source localization algorithm for sensor networks[END_REF] address the problem of source localization using sensors measurements. The problem is formulated as a convex problem, that is solved using the Aggregated Projection Onto Convex Sets (APOCS) method. In [START_REF] Hu | Localization for mobile sensor networks[END_REF], [START_REF] Baggio | Monte-Carlo localization for mobile wireless sensor networks[END_REF], [START_REF] Jiyoung | Multi-hop-based Monte Carlo localization for mobile sensor networks[END_REF], dynamic approaches, based on sequential Monte-Carlo [START_REF] Doucet | On sequential Monte-Carlo sampling methods for Bayesian filtering[END_REF], are considered to estimate the positions of the nodes.

The posterior distribution of the unknown positions is estimated recursively with a set of particles. Terwilliger et al. [START_REF] Terwilliger | Localization in ad hoc and sensor wireless networks with bounded errors[END_REF] propose to cover all possible solutions with the smallest enclosing disk. Alternative dynamic algorithms for sensor localization, using interval analysis [START_REF] Jaulin | Applied interval analysis[END_REF], have been proposed in [START_REF] Mourad | Anchor-based localization via interval analysis for mobile ad-hoc sensor networks[END_REF], [START_REF]Model-free interval-based localization in manets[END_REF]. Position estimates are boxes covering the possible locations of the sensors.

Existing methods have mainly considered the localization problem with the hypothesis that all measurements are consistent with the considered measurement model. However, in practical situations, outliers, i.e., data not matching the measurement model, are encountered. Previously-mentioned estimation techniques are not very robust to such outliers. In [START_REF] Jaulin | Guaranteed robust nonlinear parameter bounding[END_REF], Jaulin et al. propose a set-membership estimator robust to outliers based on interval analysis.

Savarese et al. [START_REF] Savarese | Robust positioning algorithms for distributed ad-hoc wireless sensor networks[END_REF] present a distributed robust algorithm for sensor localization. The method is separated into two phases: the start-up phase, where first estimates of node positions are computed using hop counts to anchors; and the refinement phase, where nodes communicate with their neighbors to update their positions using a least squares triangulation technique. Nevertheless, a number of factors influence the convergence of the refinement phase, such as the accuracy of first estimates and the magnitude of ranging errors. In [START_REF] Rabbat | Robust decentralized source localization via averaging[END_REF], Rabbat et al. introduce a robust localization algorithm of an isotropic energy source using kernel averaging techniques. The proposed estimator is more robust than the least squares estimator under a variety of conditions. Leger and Kieffer [START_REF] Leger | Guaranteed robust distributed estimation in a network of sensors[END_REF] present a distributed version of the estimation algorithm [START_REF] Jaulin | Guaranteed robust nonlinear parameter bounding[END_REF], assuming that the maximal number of outliers is known. In particular, a static distributed algorithm is proposed for source localization using Received Signal Strength (RSS) measurements. The proposed method adapts the Set Inversion Via Interval Analysis (SIVIA) algorithm [START_REF] Jaulin | Applied interval analysis[END_REF] to evaluate a solution set.

In this paper, we propose an original adaptive approach for sensor localization in presence of outliers. Assuming only that the maximal number of outliers is given, the proposed approach uses connectivity measurements in addition to a mobility model to address the localization problem. The solution is then given using either SIVIA or an alternative combinatorial technique. Another contribution of the paper is that it proposes a technique for evaluating the maximal number of outliers to be robust to. Moreover, using a connectivity-based observation model, the paper compares the performances of both robust localization algorithms.

The rest of the paper is organized as follows. Section II introduces the localization problem. A description of the SIVIA algorithm and the combinatorial technique is then given in Section III. Section IV provides simulation results whereas Section V concludes the paper.

II. PROBLEM STATEMENT

The proposed method is an anchor-based method where each node exchanges information with anchors to localize itself. Consider a network of anchors and mobile nodes. All sensors are assumed to be in the same plane: their locations at time are given by ( ) = ( ,1 ( ), ,2 ( )) , = 1, . . . , , for anchors and ( ) = ( ,1 ( ), ,2 ( )) , = 1, . . . , , for nodes. In order to reduce the communication costs during the localization process, the proposed method assumes that each mobile node does not exchange information with other nodes. For this reason and without loss of generality, we focus on the localization of one generic mobile node ( ) = ( 1 ( ), 2 ( )) and we thus drop the index .

A. Observation model

At time , the mobile node receives signals from a set ( ) ⊆ {1, . . . , } of anchors with specific Received Signal Strengths (RSSs), denoted by ( ), ∈ ( ). These RSSs are assumed to follow the Okumura-Hata model [START_REF] Medeisis | On the use of the universal Okumura-Hata propagation prediction model in rural areas[END_REF],

( ) = 0 -10 log 10 ( ( )) 0 + ( ). (1)
In ( 1), ( ) is in , 0 is the power measured (in ) at a reference distance 0 from the anchor ( ),

is the path-loss exponent, ( ( )) = ∥ ( ) -( )∥ is the Euclidian distance between the anchor ( ) and the considered node and ( ) is the measurement noise, modeled as zero-mean Gaussian with variance 2 .

In practice, 0 and may vary from one anchor to the other and 2 may be quite large. Given the RSS values, the proposed model may lead to inaccurate distance estimates. For this reason, only connectivity information are employed: (1) is only used to determine whether the node is in the vicinity of the -th anchor. Let be some RSS threshold corresponding to a distance , which is the sensing range of the sensors. Then, if ( ) ≥ , the distance ( ( )) from the anchor to the node is deemed less than . Anchors for which ( ) ≥ are called detected anchors. Only detected anchors are then taken into account for the localization. The observation model is then given by

( 1 ( ) -,1 ( )) 2 + ( 2 ( ) -,2 ( )) 2 ≤ 2 , ∈ ( ), (2)
where ( ) ⊆ ( ) is the set of indices of detected anchors, i.e. whose emitted signals have RSS at the node ( ) larger than . The observation model is thus given by a set of disk equations centered on the detected anchors and having as radius.

In real environments, measurements may not follow exactly the observation model. Indeed, due to the additive noise and the inaccuracy of the parameter values, a measured RSS ( ) could be less than while ( 2) is satisfied for real and vice-versa. In the first case, the anchor is assumed to be out of the vicinity of the node, which is not true, and thus a correct measurement is omitted whereas in the second case, an outlier is obtained. The proposed approach takes such outliers into consideration. Using the connectivity-based model, it assumes that the maximal number of outliers is known and denoted by . In other words, it considers that | ( )|measurements at minimum are correct at each time step.

B. Mobility model

The proposed method takes also advantage of the mobility of the nodes to improve the estimation accuracy. Any available information about the motion of the node could be used to define the mobility model. This paper proposes a very general mobility model where only the maximal velocity of the node is assumed to be known. Then, the positions of the generic node at time steps -Δ and satisfy

( 1 ( ) -1 ( -Δ )) 2 + ( 2 ( ) -2 ( -Δ )) 2 ≤ Δ 2 . 2 . (3)
More generally, the mobility model could be reformulated as follows,

( ( -Δ ), ( ), ) = 0, (4)
where is some parameter only known to belong to some known interval [ ] (here [ ] = [0, ]).

C. Description of the robust set-membership localization

Estimating the location of the sensor at time consists of finding the set ( ) of all locations consistent with the mobility model ( 4 Assume that ( -Δ ) belongs to some set ( -Δ ). According to this approach, and to compute ( ), a predicted set is first evaluated using the mobility model

* ( ) = { | ∃ ′ ∈ ( -Δ ), ∃ ∈ [ ], ( ′ , , ) ≤ 0}. (5)
Measurements are then taken into account to correct * ( ) as follows

( ) = ∪ ∈ | ( )|- ( ) ( ∩ ℓ∈ ℓ ( ) ) , (6)
where

| ( )|- ( )
is the set of all (| ( )| -)-combinations of indices in ( ), is a set of indices belonging to

| ( )|- ( ) and ℓ ( ) = { ∈ * ( ) | ∥ -ℓ ( )∥ ≤ }. (7)
Then, ∩ An alternative definition of ( ) inspired by [START_REF] Lahanier | OMNE: a new robust membership set estimator for the parameters of nonlinear models[END_REF] is

( ) = { ∈ * ( ) | Σ ∈ ( ) ( , ( )) ≥ | ( )| -}, (8)
where

( , ( )) = ⎧  ⎨  ⎩ 1 if ∥ -( )∥ ≤ ,
0 otherwise. This definition does not involve any combinatorial. One may easily prove that ( 6) and ( 8) are equivalent. This technique would be used in the following to solve the localization problem.

III. LOCALIZATION ALGORITHMS

Solving the localization problem in a guaranteed way consists of finding the set of all node locations that satisfy the problem constraints while being robust to outliers. In this paper, interval analysis [START_REF] Jaulin | Applied interval analysis[END_REF] is employed to achieve this goal. At each time step, the proposed method computes a set of non-overlapping boxes, called subpaving [START_REF] Jaulin | Applied interval analysis[END_REF], whose union covers the solution set ( ). Assume that [ ]( ) is the solution subpaving containing the actual position of the generic node at time . One has

[ ]( ) = ∪ 1≤ ≤ ( ) [ ]( ), (9)
where

[ ]( ) = [ ,1 ]( ) × [ ,2
]( ) is a two-dimensional box and ( ) is the number of boxes in [ ]( ). As shown in Section II-C, finding [ ]( ) involves a prediction phase followed by a correction phase.

A. Prediction phase

Assume that [ ]( -Δ ) is the subpaving obtained at time -Δ . Computing the predicted set [ ] * ( ) may be done by evaluating [START_REF] Niculescu | Ad-hoc positioning system (APS)[END_REF], where ( -Δ ) is replaced by [ ]( -Δ ), which is quite difficult. Nevertheless, ) has to be compliant with the mobility model (3), leading to the following constraint

for each box [ ]( -Δ ) = [ ,1 ]( -Δ ) × [ ,2 ]( -Δ ) ∈ [ ]( -Δ ), the corresponding box [ ] * ( ) = [ ,1 ] * ( ) × [ ,2 ] * ( ) ∈ [ ] * (
([ ,1 ] * ( ) -[ ,1 ]( -Δ )) 2 + ([ ,2 ] * ( ) -[ ,2 ]( -Δ )) 2 ⊆ [0, Δ 2 . 2 ]. (10)
Relaxing [START_REF] Hu | Localization for mobile sensor networks[END_REF] yields the following expressions of [ ,1 ] * ( ) and [ ,2 ] * ( )

[ , ] * ( ) = [ , ]( -Δ ) + [-Δ . , Δ . ], = 1, 2. (11)
Let [ ˜ ] * ( ) = ∪ [ ] * ( ) be the set of all boxes evaluated with [START_REF] Baggio | Monte-Carlo localization for mobile wireless sensor networks[END_REF]. One may prove that [ ] * ( )

⊂ [ ˜ ] * ( ). The convex hull [ ] * ( ) = [ 1 ] * ( ) × [ 2 ] * ( ) [15] of [ ˜ ] * ( ) is the smallest box containing [ ˜ ] * ( ). Its components are defined as [ ] * ( ) = [ min ≤ ( -1) ( * , ( )), max ≤ ( -1) ( * , ( ))], = 1, 2, (12)
where * ,1 ( ) and * ,1 ( ) are the low and high endpoints of [ ,1 ] * ( ) respectively. [ ] * ( ) is a rectangular area that covers all possible locations that could be taken by the node at time according to its mobility model. The convex hull is used in the correction phase instead of [ ˜ ] * ( ) to reduce the computational complexity.

B. Correction using the SIVIA algorithm

The SIVIA algorithm [START_REF] Jaulin | Applied interval analysis[END_REF] performs a succession of bisections and selections of boxes compliant with the localization constraints. Let [ ] be a box, set initially to [ ] * ( ). The following test function is evaluated

([ ]) = ⎧      ⎨      ⎩ 1 if ∑ ∈ ( ) ([ ], ) ≥ | ( )| -, -1 if ∑ ∈ ( ) ˜ ([ ], ) > , 0 otherwise, (13)
where Fig. 1. Robust localization with the SIVIA algorithm.

([ ], ) is equal to 1 if sup(∥[ ]-∥) ≤ and 0 otherwise while ˜ ([ ], ) is equal to 1 if inf(∥[ ]-∥) >

C. Correction using the combinatorial technique

In this algorithm, both the combinatorial formulation ( 6) and the convex hull [ ] * ( ) including all propagated boxes using ( 12) are considered. Based on (6), the proposed algorithm consists in contracting the initial domain

[ ] * ( ) with each combination ∈ | ( )|- ( )
of observations. For this reason, all observation equations indicated in are iterated in the forward-backward contractor [START_REF] Jaulin | Applied interval analysis[END_REF]. This contractor iterates all constraints without any prior order until no contraction is possible. The resulting region is the smallest box covering the intersection of [ ] * ( ) with all the observation disks of . In order to use each constraint of (2) in the forward-backward contractor, one should express 1 ( ) as a function of 2 ( ), and vice versa as follows,

⎧  ⎨  ⎩ ,1 ( ) -,1 ( ) ≤ 1 ( ) ≤ ,1 ( ) + ,1 ( ), ,2 ( ) -,2 ( ) ≤ 2 ( ) ≤ ,2 ( ) + ,2 ( ), (14)
for each detected anchor where ,1

( ) = √ 2 -( 2 ( ) -,2 ( )) 2 and ,2 ( ) = √ 2 -( 1 ( ) -,1 ( )) 2 .
Using intervals and having an initial box [ ], these inequalities would lead to the contracted box [ ′ ] defined as follows,

⎧  ⎨  ⎩ [ ′ 1 ] = [ ,1 ( ) -,1 ( ), ,1 ( ) + ,1 ( )], [ ′ 2 ] = [ ,2 ( ) -,2 ( ), ,2 ( ) + ,2 ( )], (15)
where ,1 ( ) = sup([

√ 2 -([ 2 ] -,2 ( )) 2 ]) and ,2 ( ) = sup([ √ 2 -([ 1 ] -,1 ( )) 2 ]
). Then, considering the combination of constraints, and starting with the predicted domain (initially [ ] = [ ] * ( )), the contracted box [ ] would be obtained by performing the following steps. The first solution leads to two boxes, the box 1 ⃝ and the one in dashed line. Using the depriving technique, three non-overlapping boxes 1 ⃝, 2 ⃝, and 3 ⃝ (in bold line) are then selected covering the exact solution (in light gray).

while [ ] is contracted do for ∈ do ,1 ( ) = sup([ √ 2 -([ 2 ] -,2 ( )) 2 ]); [ 1 ] = [ 1 ] ∩ [ ,1 ( ) -,1 ( ), ,1 ( ) + ,1 ( )]; ,2 ( ) = sup([ √ 2 -([ 1 ] -,1 ( )) 2 ]); [ 2 ] = [ 2 ] ∩ [ ,2 ( ) -,2 ( ), , 2 ( )

D. Evaluation of the number of outliers to tolerate

Consider the vector of RSS measurements. Determining from the maximal number of outliers , which have to be tolerated, may be done by choosing such that Pr ( ≤ | ) > 1 -, where Pr ( ≤ | ) is the probability that or less outliers have occurred knowing and ∈ [0, 1] is some tuning parameter. One has

Pr ( ≤ | ) = ∑ =0 Pr ( = | ) = ∑ =0 ∑ (s∈{0,1} , ∑ = ) Pr ( = , s| ) , ( 16
)
where s is some pattern indicating whether anchor = 1, . . . , is providing an outlier ( = 1) or a reliable measurement ( = 0). Now Pr ( = , s| ) = Pr ( = |s, ) . Pr (s| ) .

Let and * be the noisy and noiseless RSS measurements provided by the -th anchor. The probability that the -th anchor provides an outlier is null ( = 0) if < since in this case, the anchor is not detected and will thus not provide any outlier. Otherwise, is given as follows,

= Pr ( * < r | ≥ r ) = Pr ( - * > -r ) = Pr ( > -r ) = 1 2 ( 1 -erf ( -r √ 2 2
)) ,

where is the -th measurement noise. Then, assuming that all measurement noise samples are independent

Pr (s| ) = ∏ =1 ( + (1 -) (1 -)) . (19)
Now, since

Pr ( = |s, ) = Pr ( = |s) = ⎧    ⎨    ⎩ 1, if ∑ = 0, otherwise , (20)
one is able to evaluate Pr ( ≤ | ) and to choose .

IV. SIMULATIONS

In this section, we compare the SIVIA-based method (SBL) to the combinatorial-based one (CBL). We consider a group trajectory model where sensors are moving along similar trajectories over 100 . We deploy 31 sensors in a 100 m×100 m area, 30 of them being anchors. Since nodes use only anchors information to localize themselves, we consider the localization of a single mobile node. The simulated trajectory of the node is with a maximal velocity of 2.3 m. -1 and a localization step Δ of 1 . RSS measurements are generated using the distances between the considered node and all anchors and model ( 1) with 0 = 100 , 0 = 1 m and = 4. Moreover, is set to 10 m and to 60 . In order to compare the SBL algorithm to the CBL algorithm, we take different values of the variance 2 of the measurement noise, leading to different numbers of outliers. In fact, for each value of 2 , is evaluated using the results in Section III-D, with = 0.1.

Note that the initial position of the node is supposed to be known. One may also use the whole deployment area With = 1, Fig. 3 shows the subpavings obtained with both SBL and CBL methods. Note that the threshold of SIVIA is set to 1 m. The plot shows that both results cover the actual position of the node. The average ratio of the areas of subpavings obtained with SBL over those obtained with CBL is equal to 0.827. SBL leads to a more accurate estimate. However, the average time required for the localization process is equal to 0.471 per time step with SBL and to 0.051 with CBL. This difference is due to the limited number of combinations considered in CBL at each time step (6 ≤ | | ≤ 10 with = 1). The average number of boxes per subpaving is equal to 120

with SBL, whereas it is equal to 3 with CBL. Here, CBL is less memory consuming. Note that with a precision parameter higher than 1 m in SIVIA, SBL needs less computing time but provides larger subpavings.

In a second set of experiments, varies from 1 to 15 . Fig. 4 shows the maximal number of outliers , the total number of considered anchors | |, the average computing time per step and the ratio of the average subpaving areas obtained with SBL over CBL as a function of . The simulated data are generated ten times for each , the results are thus average values over the set of simulations. The plot shows that CBL is faster than SBL when the standard deviation is less than 8 . In these cases, is less than 4 and the maximal number of considered anchors is less than 13. When the noise variance increases, the computation time of the CBL method becomes quite large compared to SBL. Choosing one algorithm or the other depends on the anchor density and on the proportion of outliers.

V. CONCLUSION

This paper proposes and compares two techniques for mobile sensor localization, that are robust to any fixed number of erroneous measurements. Using interval analysis, the estimates are sets of non-overlapping boxes containing the actual location. The SIVIA-based algorithm (SBL) bisects the search region leading to many boxes describing efficiently the solution set; the combinatorial method (CBL) leads to larger boxes including the solution as well. In terms of computing time, CBL is more efficient than SBL for a small number of outliers, whereas the

  ) and at least | ( )|observation constraints[START_REF] Hofmann-Wellenhof | Global Positioning System: Theory and practice[END_REF]. In other words, these locations should be in the vicinity of at least | ( )|detected anchors. A set-membership estimator[START_REF]Bounding Approaches to System Identification[END_REF] robust to outliers[START_REF] Lahanier | OMNE: a new robust membership set estimator for the parameters of nonlinear models[END_REF] at time is then obtained, since any | ( )|measurements instead of | ( )| measurements are considered for the estimator.

  ℓ∈ ℓ ( ) denotes the set of locations of * ( ) that satisfy the specific observation constraints denoted in ; whereas ( ) denotes the set of locations of * ( ) that satisfy any (| ( )| -) observation constraints. The number of combinations to be considered in (6) is ( ) = | ( )|! (| ( )|-)! ! where ! denotes the factorial of .

and 0

 0 otherwise. Graphically, ([ ], ) = 1 means that the box [ ] is entirely included in the connectivity disk centered on the anchor , whereas ˜ ([ ], ) = 1 means that the box [ ] is entirely outside the connectivity disk centered on the anchor . The box [ ] is added to the solution [ ]( ) if ([ ]) = 1, meaning that all ∈ [ ] satisfy at least | ( )|observation constraints. Boxes inconsistent with more than observation constraints ( ([ ]) = -1) are withdrawn, whereas others having a non-empty intersection with the solution set ( ([ ]) = 0) are bisected. The box [ ] is [ ] * ( )

Fig. 2 .

 2 Fig. 2. Robust localization with the combinatorial technique.

+ , 2 ( 1 :

 21 Computation of the contracted box using the forward-backward contractor. Each non-empty box [ ] , ∈ | ( )|-( ) , is added to the solution [ ]( ) at time . The boxes in [ ]( ) may have non-empty intersections. Consequently, in order to obtain non-overlapping boxes, one could apply the following procedure: (i) Consider an empty final set, (ii) Sort all boxes of [ ]( ) according to their decreasing areas, (iii) Add the largest box to the final set, (iv) Select the following box in the sorted list, (v) Deprive it from all boxes already added to the final set, (vi) Add the result to the set. Steps (iv) to (vi) are repeated until all sorted boxes are considered. Recall that depriving a box [ ] from a box [ ] yields a set of non-overlapping boxes covering all the points of [ ] not included in [ ]. An illustration of the proposed method is given in Fig. 2. It shows four detected anchors, one of them yielding an erroneous observation.

  as initial domain. All simulations are performed on an Intel(R) Core(TM)2 CPU at 2.40 and 1 RAM, using MATLAB 6.1. We first set = 3 , yielding either none or only one outlier per time step. Applying the results of Section III-D one obtains Pr ( = 0) = 0.4161, Pr ( ≤ 1) = 0.9109 and Pr ( ≤ 2) = 0.9958. With = 0.1, one gets = 1. With = 0.01, one would take = 2, which leads to less accurate estimates (less measurements are taken into account) but still containing the solution set. Note that if too less outliers are tolerated, one may obtain empty solution sets or sets not containing the actual location of the node.

Fig. 3 .

 3 Fig. 3. An illustration of the subpavings obtained with the SBL and the CBL algorithms.

Fig. 4 .

 4 Fig. 4. An illustration of and | | at the top plot, the computing times in the middle plot and the ratio of the subpavings areas (SBL over CBL) in the bottom plot.

complexity of SBL is almost constant whatever the number of tolerated outliers.