Affoua Thérèse

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

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

MAC Mechanism for a Scalable Wireless Sensor Networks using Independent Duty Cycles

Wireless sensor networks (WSNs) are increasingly used in order to monitor the environment. It is important to ensure that protocols for WSNs are scalable (as WSNs can be composed of hundreds of devices) and energy-efficient (as they are designed to operate for years). In this paper, we show that in synchronized MAC protocols, synchronization requires a lot of energy, and in unsynchronized MAC protocols, it is difficult for neighbor nodes to communicate together in an energy-efficient manner (as they are not synchronized). We use a mathematical model to quantify the average communication delay for unsynchronized MAC protocols, and to compute the average probability that this delay is infinite. Then, we propose a distributed MAC mechanism, based on the beacon-enabled mode of IEEE 802.15.4, without the synchronization mechanism. Our mechanism greatly reduces the probability that the communication delay is infinite, allows nodes to communicate with their neighbors periodically (but not systematically), and ensures that the energy consumption is constant. Finally, we evaluate the performance of our mechanism by simulation, and conclude that it can be integrated into a scalable MAC protocol.

I. INTRODUCTION

Wireless sensor networks (WSNs) are composed of cheap devices that can sense the environment, perform some computations, and communicate together using wireless links. These advantages allow them to be used to monitor various environments, such as volcanoes [START_REF] Geoffrey | Monitoring volcanic eruptions with a wireless sensor network[END_REF], bridges [START_REF] Nagayamaa | Suspension bridge vibration measurement using multihop wireless sensor networks[END_REF], fields [START_REF] Hart | Environmental sensor networks: A revolution in the Earth system science?[END_REF], and bird nests [START_REF] Robert | An analysis of a large scale habitat monitoring application[END_REF]. These applications often require a large number of network devices, and they have to run for a long period (usually, several years).

The IEEE 802.15.4 standard [START_REF]Part 15.4: Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (WPANs)[END_REF] has been proposed to enable low-power communications in personal area networks, including wireless sensor networks. It has two operational modes: the non beacon-enabled mode and the beacon-enabled mode. In the non beacon-enabled mode, most devices wake up only when they have data to transmit, and go back to sleep afterwards. This requires some devices to always remain awake in order to receive data, which consumes a lot of energy. In the beacon-enabled mode, all devices are synchronized: they all wake up at the same time in order to communicate, and go back to sleep at the same time in order to save energy. However, the synchronization of devices is often difficult to achieve, and does not scale well.

In this paper, we propose a distributed MAC mechanism for WSNs which aims at improving the connectivity and the scalability of the IEEE 802.15.4 standard, while having a low energy consumption. Our mechanism is to remove the synchronization constraint of the IEEE 802.15.4 beaconenabled mode by having devices use independent duty cycles. Our approach improves the connectivity as devices will eventually (with high probability) share a common activity period and be able to communicate, even though they are not synchronized. Similarly, our approach improves the scalability as synchronization is no longer necessary when nodes wake up. Note that our mechanism can be used as an essential building block of a MAC protocol.

The paper is organized as follows. Section II gives a detailed explanation of the IEEE 802.15.4 standard, which is the basis of this work. Section III presents how independent duty cycles can improve the connectivity and scalability of the network. Section IV describes our simulation results, and shows that we are able to achieve a similar energy efficiency as IEEE 802.15.4. Section V discusses how our proposition can be implemented as a distributed mechanism. Finally, Section VI summarizes our work.

II. STATE OF THE ART

Most energy-efficient MAC protocols are based on a periodic sequence of activities and inactivities, called duty cycle. Nodes communicate during the activity period, and can sleep during the inactivity period, which spares energy. Those MAC protocols can be divided into two categories, depending on whether they are synchronized or not.

A. Synchronized MAC protocols

The IEEE 802.15.4 protocol [START_REF]Part 15.4: Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (WPANs)[END_REF] in beacon-enabled mode is one of the most common energy-efficient MAC protocols. Each full-function device (FFD) sends a beacon regularly, with a period called BI (for beacon interval). When a reducedfunction device (RFD) receives a beacon, it starts its activity period for a duration called SD (for superframe duration). The ratio SD/BI defines the duty cycle of the protocol. Note that all nodes share the same activity period, as they are synchronized by the beacon reception. The medium is accessed using the slotted CSMA/CA (carrier-sense multiple access with collision avoidance) algorithm.

In D-MAC [START_REF] Lu | An adaptive energyefficient and low-latency MAC for data gathering in sensor networks[END_REF], nodes are synchronized according to their depth on a collection tree. When nodes of depth d are in a transmission slot, nodes of depth d + 1 are in a reception slot. In Z-MAC [START_REF] Rhee | A hybrid MAC for wireless sensor networks[END_REF], a TDMA (time-division multiple access) approach is used to synchronize nodes. A slot is assigned to all nodes in the configuration phase, and is used in case of high contention. In case of low contention, all nodes access the channel simultaneously, with a contention access mechanism. In G-MAC [START_REF] Brownfield | Wireless sensor network denial of sleep attack[END_REF], time is divided into three periods: a collection period (where the medium is accessed by CSMA/CA), a period of traffic indication (whose role is to maintain synchronization between nodes) and a distribution period (where the medium is accessed by TDMA). All nodes have simultaneous activities during the first and the second periods, and non-simultaneous activities during the third period. In S-MAC [START_REF] Ye | An energy-efficient MAC protocol for wireless sensor networks[END_REF], each node propagates periodically its time schedule to its neighbors. Each node adapts its activity to the first schedule it receives. Thus, nodes can determine when to be active or inactive, depending on whether they have to communicate with a given neighbor or not. In [START_REF] Nordin | Effects and implications of beacon collisions in co-located IEEE 802.15.4 networks[END_REF], the authors show that higher performance can be achieved when different wireless personal area networks have disjoint activity periods. However, ensuring that activity periods are disjoint requires synchronization. In MC-LMAC [START_REF] Ozlem | MC-LMAC: A multi-channel mac protocol for wireless sensor networks[END_REF] nodes are synchronized but, use multiple channels dynamically. MC-LMAC is based on the single-channel protocol LMAC [START_REF] Yu | Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links[END_REF]. MC-LMAC maximizes throughput of LMAC by using a plurality of channels for transmission. The principle in MC-LMAC is as follows, firstly, nodes try to find time slots following the rule of LMAC. Second, the nodes that have not been able to find time slots invite their free neighbors to listen on an agreed channel. The problem with MC-LMAC is that most of the difficulties of synchronizing all MAC protocols duty cycle synchronous, dynamic scheduling interface change requires the generation of a large number of control message.

B. Not-synchronized MAC protocols

The IEEE 802.15.4 protocol in non beacon-enabled mode allows nodes to communicate without requiring a synchronization mechanism. When an RFD has to send data to an FFD, it simply wakes up and transmits the data. This requires, however, the FFDs to be active all the time, which consumes energy. The medium is accessed using the non-slotted CSMA/CA algorithm. Although the non beacon-enabled mode allows nodes to have non-simultaneous activities, it cannot be used in practice due to its energy requirements.

In B-MAC [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF], nodes are not synchronized but wake up periodically for a short duration. When a sender node has to communicate to a receiver node, the sender node sends a long preamble before its frame (which makes B-MAC a sender-initiated protocol). When the receiver wakes up, it detects the preamble and stays active until the end of the preamble and the reception of the frame. While this approach yields good performance, nodes have to stay awake frequently in order to receive frames, and therefore the energy consumption of B-MAC relies heavily on the traffic. In X-MAC [START_REF] Buettner | X-MAC: A short preamble MAC protocol for duty-cycled wireless sensor networks[END_REF], the same approach as B-MAC is used. Instead of using a long preamble, each sender sends several small frames, which allows the receiver to go back to sleep as soon as it has received the frame, rather than having to wait for the preamble. WiseMAC [START_REF] El-Hoiydil | WiseMAC: An ultra low power MAC protocol for multi-hop wireless sensor networks[END_REF], RI-MAC [START_REF] Sun | RI-MAC: a receiver-initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks[END_REF], ADB [START_REF] Yanjun | ADB: an efficient multihop broadcast protocol based on asynchronous dutycycling in wireless sensor networks[END_REF], PW-MAC [START_REF] Sun | PW-MAC: An energy-efficient predictive-wakeup MAC protocol for wireless sensor networks[END_REF], and EM-MAC [START_REF] Lei | EM-MAC: A dynamic multichannel energy-efficient MAC protocol for wireless sensor networks[END_REF] focus on a receiver-initiated approach. In WiseMAC, preambles are used, but their lengths is reduced by allowing the sender to wake up before the beginning of the activity period of the receiver. In RI-MAC, the receiver initiates the communication. RI-MAC is based on low power probing, where the receiver sends a beacon to express its ability to receive data packets. RI-MAC reduces channel occupation (as it does not require nodes to send preambles), but generates high energy consumption. The same authors proposed the protocol ADB, to provide essentially a broadcast service in RI-MAC protocol. And PW-MAC for reduce the listening time of the sender in RI-MAC, by having each node compute its awakening times according to a pseudo-random number generator rather than according to a fixed schedule. The drawback of PW-MAC is that sending the beacons before packet transmission generates overhead, and introduces a delay when listening the channel. As PW-MAC in EM-MAC, a node computing its moments of awakening using a pseudo-random generator. A node independently decides its wake-up time and exchange channel. The wake-up channel is not necessarily the same as the channel for exchanging data. In EM-MAC, the sender also knows the parameters of the pseudo-random generator and receiver wake-up channel. EM-MAC inherits the shortcomings of PW-MAC, and more, in EM-MAC, each node invokes twice a pseudo-random generator, hence, generation of additional overhead.

III. IMPROVING THE ENERGY EFFICIENCY OF A LOW DUTY

CYCLE MAC PROTOCOL We identified two main issues in IEEE 802.15.4. First, when the non beacon-enabled mode is used, several nodes cannot sleep and the energy consumption is high. Second, when the beacon-enabled mode is used, the required synchronization is difficult to achieve for a large number of nodes, and the fact that all nodes share the same activity cycle reduces the performance of the MAC protocol (since they all compete for the medium at the same time).

In the following, we show additional drawbacks of the existing approaches. Even in the case where nodes start their activity at different times (which increases the performance of the MAC protocol), some nodes might never have a shared activity, which is detrimental for the network. We also study the delay a node has to wait, on average, to meet another node.

A. Study of the probability of shared activities

Let us suppose that nodes have the same beacon interval but start randomly within the beacon interval. Let us denote by n i each node, BI the duration of the beacon interval, and α ∈ [0; 1] the duty cycle (that is, each node is active during SD = α.BI). Without loss of generality, we can assume that n 1 starts at the beginning of its beacon interval (in this case, n 1 finishes its activity at α.BI).

First, we compute the probability P disjoint that n 1 and n 2 have disjoint activities. If α > 1/2, P disjoint = 0 as nodes are active during more than half of their beacon interval. Let us now consider that α ≤ 1/2. P disjoint is equal to the probability that n 2 starts its activity duration after n 1 finishes its own, and that n 2 finishes its activity duration before n 1 starts its next one. Thus, P disjoint is the probability that n 2 starts in [α.BI; BI -α.BI[. This interval always exists since α ≤ 1/2 yields to α.BI ≤ BI -α.BI. As we assume that the starting time of n 2 is uniformly distributed, we have P disjoint = (BI -2α.BI)/BI, that is P disjoint = 1-2α. For instance, when α = 1/4, P disjoint = 1 -1/2 = 1/2. When α = 1/8, P disjoint = 1 -1/4 = 3/4. When the duty cycle is low, the probability that some nodes never share a common activity is high, which is an important drawback of existing methods.

Second, we compute the probability P all that there is a time when n nodes are active simultaneously. Recall that all nodes have activity periods starting randomly (except for n 1 ). Since these activities are independently chosen, we can compute P all as

P all = i P (n i is active) = i α = α n .
For instance, when α = 1/2 and n = 3, P all = 1/8. When α = 1/2 and n = 4, P all = 1/16. It can be seen that when the number of nodes n is large, the probability that all nodes share a common activity is very low, which is also an important drawback of existing methods.

B. Study of the delay before a shared activity

It is important to know the delay before two nodes can have a shared activity, in addition to knowing that they will eventually meet. We define the average delay between two nodes n 1 and n 2 as the average duration between any instant when n 1 is active, and the first instant when n 1 and n 2 are active. Note that sometimes, n 1 and n 2 never meet: these cases are not taken into account in the average delay, but the probability that this occurs is P disjoint .

To compute the average delay, we examine two cases that are equally likely to occur. Case 1 is when n 2 starts within [0; α.BI[, and Case 2 is when n 2 starts within [BIα.BI; BI[. These two cases are depicted on Fig. 1. Notice that it is not possible for n 2 to start at other times, as this would cause an infinite delay.

node

n 1 node n 1 node n 2 node n 2 x x y y (Case 1) (Case 2)
Figure 1. Two cases that can occur when two nodes n 1 and n 2 meet.

Let d 1 be the average delay for Case 1. Let us denote by x the instant within the activity of n 1 (over which the average is performed), and by y the starting time of n 2 . According to Fig. 1, we have:

d 1 = 1 α 2 .BI 2 α.BI y=0 y-1 x=0 (y -x) + α.BI-1 x=y 0 = (α.BI + 1)(α.BI + 2) 6α.BI .
Let d 2 be the average delay for Case 2. Again, according to Fig. 1, we have:

d 2 = 1 α 2 .BI 2 BI-1 y=BI-α.BI y+α.BI-BI x=0 0 + α.BI-1 x=y+α.BI-BI (BI -x)   = - α(2α -3).BI 2 -3.BI -2 6α.BI .
The average delay d is thus: Figure 2 shows the delay d as a function of BI and α. It can be noticed that even when the delay is not infinite, the delay is relatively large. It reaches up to 70 s for BI = 256 and α = 6.25%.

d = d 1 + d 2 2

C. Description of our proposition

Our proposition can be summarized by the following items:

• allowing nodes to start their activity at a random time within the beacon interval,

• forcing nodes to have different beacon intervals while maintaining a given duty cycle,

• removing the constraint that all the nodes of the network have to agree on when to send their beacons. The first item ensures that all nodes are not always active simultaneously, which improves the performance of the MAC protocol. The second item ensures that nodes have a high probability to meet while maintaining the same energyefficiency as the beacon-enabled mode. The third item allows our mechanism to be independent of the number of nodes in the network, which enables its integration into a scalable MAC protocol. In this way, our proposition benefits from the energyefficiency of the beacon-enabled mode (as each node keeps the same duty cycle), without having the drawbacks of a global synchronization (as each node keeps its own time schedule).

Figure 3 shows the activities of three nodes as a function of time, with a duty cycle of 25% and when nodes start their activities randomly within the beacon interval. To ease the description, we made two simplifying assumptions: there are only 8 backoff periods per cycle (that is, BI = 8), and the backoff periods are synchronized for all the nodes. In general, the number of backoff periods per cycle is much larger: for a beacon interval of 2 6 × 15.36 ms, which is about one second, there are 3072 backoff periods of 320 µs each. Backoff periods cannot be synchronized for all the nodes when there is no global synchronization, but the desynchronization only impacts one backoff period at most, out of all the backoff periods of the beacon interval. Periodically, nodes n 1 and n 2 share a common activity period (at the end of the activity of n 1 and at the beginning of the activity of n 2 ). However, in the example depicted here, n 3 never shares a common activity with neither n 1 nor n 2 . Figure 4 shows the activities of three nodes as a function of time, for our proposition. Notice that for each node, the duty cycle is 25% (even if the beacon interval is different). Common activities between two nodes are no longer periodic: they appear depending on the beacon interval of each node. For instance, n 1 shares a common activity with n 2 at the beginning of the first activity period of n 1 , and at the end of its third activity period. Node n 3 shares a common activity with n 2 at the beginning of its first activity period, and a common activity with both n 1 and n 2 at the end of its second activity period. The main advantages of our proposition are the following:

node n 1 node n 2 node n 3 BI 1 BI 2 BI 3
• it does not require synchronization,

• the duration of the activity period is never exceeded,

• the probability that a node is isolated from the other nodes in range is low (see P disjoint ),

• as few nodes are active simultaneously on average, contention access MAC protocols can achieve higher performance,

• there are times when all nodes are active, which enables to broadcast frames efficiently.

IV. SIMULATION RESULTS

In order to evaluate the performance of our proposition, we ran some simulations using a set of Perl scripts. As a basis for our comparison, we use a model similar to the one depicted on Fig. 3: BI has a constant value of 128 backoff periods, and each node chooses randomly the beginning of its activity within the period. Our proposition, depicted on Fig. 4, allocates a random BI to each node, such that each BI is within [64; 256] and is a multiple of 4. The activity duration in our case varies for each node, but the duty cycle is constant for all nodes. Again, each node chooses randomly the beginning of its activity within its period. Each simulation lasts until a global periodicity is obtained (which happens after a number of backoff periods equal to the least common multiple of all the BIs). Note that all nodes are in range (that is, they are in the same cell). In the following plots, each point is averaged over 500 repetitions.

Figure 5 shows the average probability for all the nodes of a cell to be active simultaneously, as a function of the number of nodes. We evaluate two duty cycles: 50% and 25%, and we compare the probability when BIs are constant (which is denoted by BI is not random) and when BIs are different for each node (which is denoted by BI is random). For a given duty cycle, the probability that all nodes are active simultaneously decreases with the number of nodes, as expected. However, when BIs are random, the probability is much higher than when BIs are constant, and decreases linearly instead of exponentially. In all cases, our proposition yields a much higher probability than the state of the art. For instance, when the duty cycle is equal to 50% and for four nodes in a cell, the probability that they have a common activity is only 5% (out of active duration of nodes, which is only 50% of the time) when BIs are the same, while it exceeds 40% when BIs are random.

Figure 6 shows the average probability for several nodes in a cell to be active simultaneously, when the total number of nodes in the cell is seven. For instance, the probability that three nodes (out of seven) are active simultaneously for a duty cycle of 50% is about 60% when BIs are constant, and about 80% when BIs are random. The probability that six nodes (out of seven) are active simultaneously for a duty cycle of 50% is about 10% when BIs are constant, and about 40% when BIs are random. With our proposition, the probability that several nodes are active simultaneously decreases slowly.

Figure 7 shows the average delay (in backoff periods) as a function of the number of nodes in the cell. We compute here only the delay until two nodes are active simultaneously, without considering the MAC delay required for two active BI is random, 25% Figure 6. Average probability for several nodes to be active simultaneously, for a total of seven nodes in a cell. When BI is chosen randomly for each node, the probability that several nodes are active simultaneously decreases slowly with the number of active nodes.

nodes to communicate. The delay is averaged over all pairs of nodes, but does not take into account the infinite values. Notice that the percentage of infinite delays is very high when BI is not random, and very low when BI is random. For a duty cycle of 50%, the percentage of infinite delays varies between 0.5% and 1% when BI is not random, and is always 0% when BI is random (for our 500 repetitions). For a duty cycle of 25%, the percentage of infinite delays varies between 50% and 51% when BI is not random (which is very high), and varies between 1.5% and 2% when BI is random (which is very low). When BI is constant and the duty cycle is low, a large number of delays are infinite and are therefore omitted from the computation. When BIs are random, the delay is higher on average but only a small percentage of infinite delays are omitted.

V. IMPLEMENTATION AS A DISTRIBUTED PROTOCOL

In this section, we describe how to build a distributed and scalable protocol from our proposition. BI is random, 50% BI is not random, 25%

BI is random, 25% Figure 7. Average delay for two nodes in a cell to be active simultaneously.

When BI is chosen randomly for each node, the average delay is approximately twice higher than when BI is not random. However, when BI is chosen randomly, the probability that delays are infinite is very low.

Algorithm 1 presents our protocol. Note that all nodes share the following values: ∆ is a duration (generally large), BIs are chosen randomly within [minBI; maxBI], and dutyCycle is the fixed duty cycle for each node. We assume here that nodes start randomly and independently. Initially, each node chooses its own BI in [minBI; maxBI] according to our proposition, and operates according to this BI. After ∆ backoff periods, the node determines whether it has met any neighbor or not. When the first node joins the network, it keeps changing its BI as it does not meet any neighbor. When the second node joins the network, it is very likely that it will eventually meet the first (according to the results shown on Fig. 5). Even if it does not meet the first node with the current BI, the second node will eventually draw a new BI. The process continues in the same way for all nodes. The probability that two disjoint networks are created in the same cell is very low, as it would require all the nodes of a set N 1 to have disjoint activities with all the nodes of a set N 2 .

Our protocol is scalable and distributed, as it does not require any knowledge about other nodes, or a large overhead in terms of control messages. However, its convergence can be slow, depending on the value of ∆ and on the number of nodes in range.

VI. CONCLUSION

In WSNs, it is difficult to synchronize many nodes in an energy-efficient manner. Without synchronization, MAC protocols often require some nodes to remain active (which consumes energy) or to have disjoint activities (which forbids communications between nodes). In this paper, we proposed a distributed MAC protocol that guarantees that nodes share common activities (with a high probability) while having an energy consumption similar to the one of synchronized MAC protocols, but without the synchronization overhead. Our simulation results show that our mechanism achieves good performance in terms of percentage of shared activities. On average, the delay for our mechanism is larger than the delay of other protocols, but our mechanism has a very low probability of having infinite delays, contrarily to other protocols. Finally, our mechanism can be used as an essential building block of a MAC protocol.

Figure 2 .

 2 Figure 2. Numerical value of the delay d as a function of BI and α.

Figure 3 .

 3 Figure 3. Activities of three nodes as a function of time, with a duty cycle of 25%, and when activities start randomly within the beacon interval. Node n 3 never shares a common activity period with n 1 nor n 2 .

Figure 4 .

 4 Figure 4. Activities of three nodes as a function of time, with a duty cycle of 25%, for our proposition. All possibilities of shared activities (n 1 and n 2 , n 1 and n 3 , n 2 and n 3 , and all three nodes together) happen in this short example.

  in the cell Average delay (in backoff periods) BI is not random, 50%

  If it has not, it draws a new BI and starts again. Otherwise, it keeps the same value for BI. SD backoff periods new ←number of new neighbors discovered neighbors ← neighbors + new node is inactive during BI -SD backoff periods until ∆ backoff periods have passed until neighbors = 0 while true do node is active during SD backoff periods node is inactive during BI -SD backoff periods end while

	Algorithm 1 Scalable protocol using independent duty cycles.
	Require: ∆, minBI, maxBI and dutyCycle are global
	constants
	neighbors ← 0
	repeat
	BI ← 4.⌊rand(minBI, maxBI)/4⌋
	SD ← dutyCycle.BI
	repeat
	node is active during


Joanna Moulierac
email: joanna.moulierac@irisa.fr

Alexandre Guitton
email: alexandre@dcs.bbk.ac.uk

Miklós Molnár
email: miklos.molnar@irisa.fr

On the number of MPLS LSP using Multicast Tree Aggregation

Keywords: Multicasting, tree aggregation, MPLS, control and management of network

Multicast tree aggregation is an efficient proposition that can solve the multicast forwarding state scalability problem. Existing works on tree aggregation have focused on developing and simulating protocols that build trees dynamically. However, the underlying problem of the impact of the tree construction algorithm on the performance of the protocols remains untouched. In this paper, we propose a study on the number of trees that need to be configured in a domain depending on the tree construction algorithm. We ran extensive simulations on several real domains and with different tree construction algorithms. Our results show that for a given set of multicast groups, even when this set includes all the possible groups, the number of trees needed to be configured is small. This allows a network administrator to configure off-line all these trees in order to maintain a stable set of trees and to have knowledge of the routes used by the multicast packets. Knowing the set of all the possible trees is also useful to determine the best of its subset to configure and to give an upper bound of the number of different trees.

I. INTRODUCTION

The research in multicast has highly interested the researchers during the last decade but unfortunately, multicast is not well deployed yet over internet. However, as the number of multimedia applications including video on demand, television on internet and on line video games increases tremendously, multicast is becoming a necessity for network operators, in order to spare the network resources.

The multicast tree aggregation is an efficient proposition that allows the deployment of group communications. The main goal of tree aggregation is to keep only a small number of multicast forwarding states in the routers in order to spare the memory of the routers, to speed up the IP look-ups and to reduce the amount of control messages needed to maintain the forwarding states. Indeed, in multicast, aggregation of routing entries is more difficult than in unicast as the multicast IP addresses do not reflect the location of the members.

To reduce the number of entries, the multicast tree aggregation technique allows several multicast groups to share the same delivery tree. In other words, the packets for the groups can be multiplexed at entrance of the domain onto the same tree. This can be achieved using IP encapsulation or MPLS labels. In this case, the MPLS labels can be distributed among the routers using LDP.

Because of these two different ways of deploying multicast tree aggregation, we will talk in this paper indifferently about trees and about MPLS LSP.

Existing works on tree aggregation have focused on developing and simulating protocols that build trees dynamically. In this paper, our key concern is to study the impact of different tree construction algorithms on the performance of the protocol, which is still a research issue. The performance of a tree aggregation protocol is defined by the number of trees to be maintained and by the resource usage for each group. We first show that the way trees are built leads to major scalability issues. Then, we study several commonly used tree construction algorithms, along with the number of trees to be maintained in order to cover a set of multicast groups. We show with our simulations that it is possible to build a set of trees covering all the possible multicast groups in a given domain as this number is usually very small and few forwarding entries are needed in routers. This allows a network administrator to configure this stable set of trees in order to plan the routing for the future multicast groups, to be aware of the routes used by the multicast packets and to maintain a stable set of forwarding entries. Moreover, minimizing the number of MPLS LSP in a domain is of paramount importance for scalability issues.

The rest of the paper is organized as follows. Section II presents the main protocols achieving tree aggregation. In Section III, we present the main idea of our proposition and give an algorithm that computes the number of MPLS LSP required, i.e., the number of multicast trees. The results of the simulations are detailed in Section IV. Finally, the perspectives of our work are given in Section V.

II. MULTICAST TREE AGGREGATION

Tree aggregation reduces the number of multicast forwarding states and the tree maintenance overhead. To achieve this reduction, several multicast groups share the same delivery tree within a domain. Consequently, less trees are built ans less forwarding entries are stored than with traditional multicast.

A. Aggregation protocols

The protocol AM (Aggregated Multicast) was proposed in [START_REF] Gerla | Aggregated Multicast for Scalable QoS Multicast Provisioning[END_REF], [START_REF] Cui | Aggregated multicast -a comparative study[END_REF]. In AM, a centralized entity called the tree manager is in charge of matching groups to labels and informing the border routers of this matching.

Several recent protocols have addressed the scalability problems of AM. For instance, STA [START_REF] Guitton | Scalable Tree Aggregation for Multicast[END_REF] performs faster aggregations than AM by sorting the trees in the multicast tree set, addressing the time-scalability issue. In BEAM [START_REF] Cui | BEAM: A Distributed Aggregated Multicast Protocol Using Bi-directional Trees[END_REF], the task of the tree manager is distributed among several routers, called core routers. The protocol AMBTS [START_REF] Liu | AMBTS: A Scheme of Aggregated Multicast Based on Tree Splitting[END_REF] splits the native tree in sub-trees before aggregating, while the protocol TALD [START_REF] Moulierac | Multicast Tree Aggregation in Large Domains[END_REF] performs tree aggregation in large domains by splitting the network in several sub-domains and by managing the subdomains independently. AMBTS and TALD can be applied in large domains, where other approaches fail. The advantage of TALD over AMBTS is that no entity has the total knowledge of the domain.

In parallel, new protocols have been developed with additional constraints. The paper [START_REF] Cui | A Protocol to Improve the State Scalability of Source Specific Multicast[END_REF] studies ASSM protocols designed for source-specific groups. AQoSM [START_REF] Cui | Scalable QoS Multicast Provisioning in Diff-Serv-Supported MPLS Networks[END_REF] and Q-STA [START_REF] Moulierac | QoS Scalable Tree Aggregation[END_REF] perform tree aggregation under bandwidth constraints. In these two protocols, the links have limited bandwidth capacities and groups have bandwidth requirements depending on the multimedia application. Indeed, previous approaches assume links have infinite bandwidth capacity and therefore focus on the aggregation ratio. The protocol TOMA [START_REF] Lao | TOMA: A Viable Solution for Large-Scale Multicast Service Support[END_REF] deals with overlay multicast. Finally, the protocol AMFM [START_REF] Cui | An Architecture for Scalable, Efficient and Fast Fault-Tolerant Multicast Provisioning[END_REF] proposes a fault tolerant architecture.

In all these protocols, the tree construction algorithm is either unspecified or arbitrary. We believe that understanding how the tree construction algorithm impacts tree aggregation protocols can lead to further enhancement of the existing mechanisms, or to protocols based on new concepts.

B. On the number of trees

Our work is based on the frameworks proposed in [START_REF] Moulierac | On the number of multicast aggregated trees in a domain[END_REF] and in [START_REF] Moulierac | Distributed Multicast Tree Aggregation[END_REF]. Among the research papers on tree aggregation, the closest to our work is [START_REF] Lao | Tackling Group-Tree Matching in Large Scale Group Communications[END_REF], which also considers the number of trees in a domain. However, our work tackles the problem from another angle. First, we consider that the branching routers of the trees can lead to multicast members. Indeed, in real networks, the non-leaf routers used by a tree can be multicast capable and can be attached to members. Second, we propose an analysis of the upper-bound of the number of trees needed to span the set of all multicast groups considering different tree algorithm construction. Some scalability problems arise with this approach when the number of routers in the network is large, as the set of all the multicast groups can not be computed. However these problems can be solved (although not optimally) by using a similar approach as TALD, i.e., by splitting the domains into sub-domains and computing the set of trees into each sub-domain separately.

As we have said earlier, the previous works do not focus on the impact of the tree construction algorithms on the number of MPLS LSP or trees to be maintained. However, we believe that it is one of the most important parameter of tree aggregation protocols. That is why we are interested in answering the following questions:

• What is the impact of the tree construction algorithm on the number of different trees?

• How does the number of different trees evolves as a fraction of the bandwidth is allowed to be wasted?

III. ALGORITHM FOR CONFIGURING A SET OF TREES

In this section, we present an efficient way to reduce the number of trees and then we present the algorithm that computes a set of multicast trees for a given domain.

First of all, when we say that a router is a member of a group, it means that this router leads to group members. The real members of the group can be directly attached to the router or can be connected to it through several domains. In this way, we will define by group the set of the routers involved in the group. With this definition, two groups can be identical even if they do not have the same multicast address.

Second, since the main goal of the tree aggregation is to reduce the number of trees, we will consider shared tree to be built as usually made by tree aggregation protocols. However, our approach still holds when considering source-based trees. It can be noticed that for source-based trees, more trees are configured as all (source,group) tuples are considered whereas in case of shared trees, only the groups are considered. In the literature, shared trees are build with CBT [START_REF] Ballardie | Core Based Trees (CBT) Multicast Routing Architecture[END_REF] or with PIM-SM [START_REF] Estrin | Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification[END_REF]. The trees are rooted at a core router or at a rendezvous point and cover the members of the groups using shortestpath computed with Dijkstra algorithm. As the determination of this source is still a research issue in the literature, we will consider in this paper three different ways to chose this source for the groups and this is described later in Section IV. Shared trees can also be build with the objective of minimizing the cost and then approximate Steiner trees can be used [START_REF] Kou | A fast algorithm for Steiner trees in graphs[END_REF]. Then, even if such trees are not used in real networks, it gives a lower bound of the bandwidth to be used for a set of groups.

A. On reducing the number of trees

Previous works on tree aggregation were based on the following intuitive remark: two different multicast groups can be the same when projected on a domain. In other words, if we consider the routers that have members attached to them, it is easy to see that different members can be attached to the same set of edge routers. If n is the number of routers of the domain, the upper bound on the number of trees is only 2 n , instead of having as an upper bound the whole space of multicast addresses.

However, we can go a step further. Let us consider the example shown on Fig. 1. A tree, rooted at A and covering the routers {A B C D E F } is represented on the figure. This tree is the native tree for four different groups. Indeed, it can cover the group with members attached to routers {A C D F } but also the group {A C D E F }, the group {A B C D F } and the group {A B C D E F }. All these aggregations can be done without bandwidth wasted as the tree traverses the two branching routers B and E in order to reach the leaves C and F .

Therefore, the number of different trees is lower than the previous bound 2 n . We only noticed that packets for the groups traverse several routers that can be multicast capable before reaching the leaves. Note that in the previous description, no bandwidth is allowed to be wasted. To further reduce the number of different trees in a domain, it is realistic to consider that the network administrators allow a given percentage of the multicast bandwidth to be wasted in order to ease the aggregation process. Let us consider once more the example shown on Fig. 1. A group g having members attached to routers {B F D} can share the same tree as the one depicted, but some bandwidth will be wasted when packets for the group g reach router C unnecessarily. If the bandwidth used by the group g is small compared to the bandwidth available on the link (B, C), it could be better to have only one tree instead of two.

B. Description of the Algorithm

Algorithm 1 computes the set T of different trees given the bandwidth bound bw. No more than bw percent of bandwidth are allowed to be wasted. Every possible group is considered in turn. For each group g i ∈ G, the algorithm computes a native tree t i . If there is already a tree in T that covers the same edge routers as t i and that does not waste too much bandwidth, then there is no need to add t i in the set T .

Input: a domain with n routers, a tree construction algorithm

A, a bandwidth threshold bw Output: a set of trees T covering all the 2 n groups T ← ∅ for i = 1 to 2 n do g i is the i-th group of the 2 n possible groups of G compute a native tree t i covering g i with algorithm A if there is a tree t ∈ T that covers the routers covered by t i and if cost(t) ≤ (cost(t i ) + cost(t i ) * bw) then t i is ignored else add t i to T return T Algorithm 1: Computing the set of different trees

The algorithm running-time scales rather badly with the number of edge routers of the domain. However, previous works [START_REF] Moulierac | Multicast Tree Aggregation in Large Domains[END_REF] have shown that a large domain can be separated into several sub-domains having few edge routers, in such a way that the tree aggregation can be done separately in each sub-domain without suffering a significant drop of the performance. Therefore, if the domain is too large, it can be divided into several sub-domains, and then the algorithm presented above can be applied in each of the sub-domain in order to scale better.

The number of trees computed by Algorithm 1 applies for a worst-case scenario where each group has an equal probability of being requested. Previous studies have shown that real groups show a high degree of correlation and then they can be simulated using some affinity model. Our algorithm still applies for this scenario, and in this case, the number of trees needed to be configured is smaller. Moreover, our algorithm can be applied for only a set of multicast groups to be covered. This can be useful when a network administrator has traces of real multicast groups and wants to configure only a set of trees covering these groups.

IV. SIMULATION RESULTS

We made simulations of Algorithm 1 on different real graphs: the VSNL network [18] (which is given by an internet mapping tool called Rocketfuel [START_REF] Spring | Measuring ISP topologies with Rocketfuel[END_REF]), the Abilene network [START_REF]Abilene network[END_REF], the Nsfnet network [START_REF]Nsfnet network[END_REF] and the Geant network [START_REF] Network | [END_REF]. We ran the simulations for two bandwidth thresholds: when no bandwidth is wasted (bw = 0%) and when 20% of bandwidth is allowed to be wasted. In order to evaluate the number of trees by a comparison of the tree algorithm construction, we consider different ways of choosing the core or the rendez-vous point for CBT or PIM-SM. Recall that these protocols build shortest path trees rooted at a given core. We also consider MST trees. The compared algorithms are:

• CBT-Fixed: a core router is chosen arbitrarily among the routers of the network initially and all the trees are rooted at this core. • CBT-First: a core router is chosen among the members: first, the members are sorted according to a given order of the routers, and then the core is the first member. • CBT-Rand: the trees are rooted at a core randomly chosen among the members. • MST: a minimum spanning tree covering the routersmembers is built in the metrical closure graph. This tree is a 2-approximate Steiner tree.

A. Number of trees to be configured

Table I shows the total number of different groups and the number of trees needed to cover these groups. Note that for a domain with n multicast capable routers, there are (2 nn -1) different groups. Indeed, we take into account neither groups having one member nor groups having no member. The number of different trees is very low compared to the number of different groups. Therefore, it is possible to configure all the different trees in a domain.

When using CBT-Fixed, trees are very similar. Indeed, they are rooted at the same core and use frequently the same links (since shortest paths trees are built). This means that CBT-Fixed build few different trees. Oppositely, we can see that more trees are built with MST than with CBT-Fixed. Indeed, MST trees use less links and the link usage is distributed fairly in the network. Thus, the different trees built by MST are very different with each other, and less aggregation can be found. However, with CBT-Fixed, the links around the core router experience an important stress, since they are shared by most of the trees.

With CBT-First, the trees have frequently the same core. Then, there are few different cores and the link usage of trees with CBT-First is fairer than with CBT-Fixed, but more trees are required. Finally, CBT-Rand chooses randomly the core for each group which implies that the trees are rooted at several different sources. The link usage is balanced but more trees are needed than with all others CBT algorithms. This shows that the choice of the core router has a great impact on the number of trees to be configured. With the MST algorithm, we can get an upper bound of the number of trees needed when the metric considered is the network usage minimization.

On the impact of the topology: The topology of the network has also a great impact on the number of trees. Indeed, although the Abilene and the VSNL networks share the same number of nodes, the number of trees built in both is different. VSNL contains fewer links and several routers have a degree of 1. Because of this small number of branching routers, more trees are configured for VSNL than for Abilene.

To explain this phenomenon, let us consider a network with n routers where n -1 routers are leaves and are connected to the n-th router. This network is a star network. In this example, the number of trees is independent of the tree construction algorithm and is equal to 2 n-1 -1 (the number of permutations of the n -1 leaves minus the empty tree). In this example, the router linked to all others routers has to keep 2 n-1 -1 forwarding entries. Another example to be considered is a path of n routers. In this network, there are 2 leaves and n -2 routers with a degree of 2: the number of different trees is n(n -1) 2 , which is much smaller than on the previous example. These two examples show the impact of the network topology on the number of trees.

B. Number of forwarding entries per router

The figures Fig. 2 and Fig. 3 plot the number of forwarding entries per router for the Geant network and for Abilene. We compare the minimum, the maximum and the mean number of forwarding entries to be stored per router. The figures show that when bandwidth wastage is allowed bw = 20%, the number of forwarding entries is smaller than with bw = 0%. The number of forwarding entries is strongly related to the number of trees and then the impact of tree construction algorithm for both metrics can be explained in the same way. What can be noticed, is that the number of forwarding entries is small enough to be realistic to envisage to stored them in routers.

C. Mean cost of trees per group

The figures Fig. 4 where t(g) is the tree of minimum cost in T that covers g, cost(t(g)) is the cost of the tree t(g) in terms of number of links and |G| is the number of different groups. This metric reflect the number of links loaded and then gives an overview of the bandwidth used per group. These two figures show the compromise between the number of trees and the usage of the network resources. Indeed, the less trees to be maintained and the more the cost of trees per group and then the more links are loaded. For Geant network, which has more than 260 000 different groups, a network administrator can configure less than 2 000 trees with CBT-Fixed and with bw = 20%, but some bandwidth is wasted for each group, the trees have 12 links in average for each group. For a minimum bandwidth usage, MST with bw = 0% configures 75 000 trees and the trees have a little bit more than 9 links per group. It is interesting to notice that building MST trees with bw = 20% leads to approximately the same results as building CBT-Rand trees with bw = 0% for Geant network.

V. CONCLUSION AND FUTURE WORK

We proposed, in this paper, a study of the impact of tree construction on the number of trees to be maintained in a domain. During the simulations, we generated all the possible groups for a given domain and we computed the set of trees needed to cover all these groups while varying the tree construction algorithms. Our study showed that very few trees are needed to be configured in a domain and that it is possible for a network administrator to compute this stable set of trees off-line. This allows to manage more efficiently the domain and to be aware of the configured trees. In this paper, we also studied in this paper the compromise between the number of trees configured and the mean cost of trees per group. When the network administrator has real traces of multicast groups, only a sub-set of all these trees can be computed. Indeed, we proposed an algorithm that gives an upper bound on the the number of trees needed depending on the tree construction algorithm. When these trees are configured, usual group-tree matching protocols can be achieved.

The number of trees is also dependent on the topology of the network. When the network topology implies that the number of trees is still too high, then several investigation has to be done to further reduce this number. We plan to design, in this case, a new tree construction algorithm that builds few trees.

Fig. 1 .

 1 Fig. 1. The tree represented on the figure covers different multicast groups.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Number of forwarding entries for Abilene network.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Mean cost of trees per group for Abilene network [20].


Adonis Skordylis
email: adonis@dcs.bbk.ac.uk

Niki Trigoni

Alexandre Guitton
email: alexandre@dcs.bbk.ac.uk

A Study of Approximate Data Management Techniques for Sensor Networks

Recent developments in sensor network technology have enabled the instrumentation of the physical world with smart devices for monitoring purposes. A large variety of applications could benefit from the pervasive deployment of inexpensive wireless sensor nodes, ranging from environmental monitoring to emergency detection and response. A significant challenge is to prolong the monitoring operation of sensor nodes by efficiently using their limited energy, bandwidth and computation resources. In this paper, we survey approximate data management techniques for sensor networks that exploit the tolerance of most applications to small inaccuracies in the reported data in order to extend the network lifetime.

Introduction

Sensor networks are targeted to a large spectrum of applications, including habitat and environmental monitoring, health monitoring, traffic monitoring, security and surveillance, emergency scenarios and military applications. They consist of a large number of nodes deployed in extended areas over long periods of time. Each node in a sensor network is a small, radio-equipped, battery-powered computer with a number of sensors attached to it, which monitor the ambient environment. A database abstraction of sensor networks has recently gained interest in the sensor network community [START_REF] Yao | The Cougar approach to in-network query processing in sensor networks[END_REF][START_REF] Madden | TinyDB: an acquisitional query processing system for sensor networks[END_REF]. Each node can be viewed as a mini-repository of sensor data acquired and stored locally in its memory. The network can therefore be treated as a distributed sensor data management system. Sensor networks differ from traditional distributed databases in that they are limited by stringent processing, bandwidth and, most importantly, energy constraints.

Two ideas that are often used to address the issue of limited resources are aggregation and approximation. In-network aggregation reduces the load of data propagated in the network, by pushing part of the query computation to the sensor nodes. Data streams no longer consist of raw sensor readings, but of partial query results that are progressively merged at intermediate nodes in their way to the base station [START_REF] Intanagonwiwat | Directed diffusion: a scalable and robust communication paradigm for sensor networks[END_REF][START_REF] Yao | The Cougar approach to in-network query processing in sensor networks[END_REF][START_REF] Madden | TinyDB: an acquisitional query processing system for sensor networks[END_REF]. Note that in-network aggregation does not compromise the accuracy of query results, but simply distributes query computation to multiple sensor nodes.

In-network lossy compression exploits the fact that a large number of applications can tolerate approximate query results. In large sensor networks, it is not realistic to expect that query results will accurately reflect the current state of the network. Faults naturally occur in a number of places, for instance during measurement acquisition by sensor devices or in data propagation due to node and link failures. In the light of such uncertainty, users are generally prepared to tolerate various levels of precision for different queries. In this paper, we overview approximate data management techniques for sensor networks that exploit relaxed precision requirements, in order to reduce the communication and sensing load in the network.

Assumptions and Design Considerations

We start by discussing several assumptions and design aspects that will form the basis for comparing existing techniques: Data requirements: The techniques developed for approximate data management largely depend on the data requirements presented by the users of the sensor network. We will review techniques that aim at approximating results for different types of approximate queries, including aggregate and non-aggregate queries (e.g. time-series, range queries). We further distinguish approximate queries based on whether they require deterministic or probabilistic error guarantees. In the case of deterministic error guarantees, the estimated query answer must be an ε-approximation of the accurate answer with probability 100%. In the case of probabilistic error guarantees, we introduce a certain degree of confidence in the error of the estimated query answer, i.e. the estimated value of a query answer is within ε of the real value with probability p.

Mode of communication:

We distinguish three modes of communication, namely pure push, pure pull and hybrid push-pull. In the push mode, nodes are programmed to proactively forward their readings to the base station. In the pull mode, users inject short-lived queries at the base station, and these queries are propagated to the sensor nodes in order to pull data on-demand. In the hybrid push-pull model, sensors push data proactively towards the base station. In case this data is not accurate enough to answer all posed queries, additional information is pulled from the network in an on-demand fashion.

Mode of processing:

We distinguish between flat (2-tier) and hierarchical (multi-tier) network models. In the 2-tier model, processing can occur either at the source sensor nodes (first tier), or at the base station (second tier). To make this model more general, we also include scenarios where the network is divided into clusters and data is either processed at the cluster heads (first tier) or at the base station (second tier). In the hierarchical model, readings from different sensors can be accumulated and partially processed at intermediate nodes, as they are forwarded towards the base station. A typical example is tree-based in-network aggregation of COUNT, SUM, AVG, MIN and MAX queries. Use of data correlations: Whereas some of the techniques reviewed in this paper make no assumption about the model of the observed physical process, others try to exploit the strong correlations between observed values in order to reduce the sensing and communication overhead. We review techniques that focus on temporal and spatio-temporal correlations concerning one or more sensor attributes (e.g. correlations between humidity and temperature readings of nearby nodes over a time period). Adaptive distribution of error bounds: The experts of an application domain define carefully the degree of precision (also referred to as error bound) that they are willing to tolerate for their queries. Some of the techniques reviewed in this paper consider the prob-lem of distributing the input error bound to the individual nodes of the sensor network, whereas others ignore this problem (as irrelevant or out of scope). Node selection: In many cases, it is possible to answer a query at a required degree of precision by tasking different subsets of sensor nodes. In this paper we compare approximate data management techniques based on whether they are designed to consider alternative query execution plans that activate different sets of sensors. We will review competing approaches to selecting the most efficient plan that minimizes the sensing and communication overhead.

Paper Organization

We are now in a position to present an overview of recent work on approximate data management for sensor networks, which we organize in three major groups. In the first two groups, we consider related work from a query processing viewpoint and distinguish existing approaches based on whether they target aggregate queries or not. In the last group, we study approximate techniques from a storage management viewpoint.

Approximate Processing of Aggregate Queries

This section focuses on techniques for processing approximate aggregate queries in sensor networks. An aggregate query may use a standard aggregate operator (such as AVG, SUM, MEDIAN, MIN, MAX, COUNT) or a user-defined function. Aggregate operators are characterized according to a set of properties like idempotence, commutativity and distributed computation. An operator allows for distributed computation if, instead of applying the operator to an entire collection of input values, we can obtain the same result by applying it to separate segments of the input collection and merging the resulting partial results. For instance, MIN, MAX, AVG and COUNT are suitable for distributed computation, whereas MEDIAN is not. In this section we only consider operators that allow distributed computation. Before considering approximate aggregates, we introduce the main mechanism for processing accurate aggregate queries, referred to as tree-based partial aggregation [START_REF] Intanagonwiwat | Directed diffusion: a scalable and robust communication paradigm for sensor networks[END_REF][START_REF] Yao | The Cougar approach to in-network query processing in sensor networks[END_REF][START_REF] Madden | TinyDB: an acquisitional query processing system for sensor networks[END_REF]. In an initial network set-up phase, a tree is constructed using simple flooding algorithms [START_REF] Yao | The Cougar approach to in-network query processing in sensor networks[END_REF], data-centric reinforcement strategies [START_REF] Intanagonwiwat | Directed diffusion: a scalable and robust communication paradigm for sensor networks[END_REF] or energy-aware route selection schemes [START_REF] Singh | Power-aware routing in mobile ad hoc networks[END_REF][START_REF] Yu | Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks[END_REF]. After a tree is constructed, sensor nodes forward their readings along the paths of the tree, evaluating partial query results at intermediate nodes. Additional communication savings can be achieved by combining the processing of multiple aggregate queries over a fixed communication tree [START_REF] Trigoni | Multi-query optimization for sensor networks[END_REF].

In certain applications, users may wish to tolerate different degrees of precision for aggregate query results. Instead of letting the network configure the allocation of its limited resources to the current queries in an arbitrary manner, it makes sense to let users control these knobs according to their needs. We present two different approaches to expressing uncertainty in aggregate queries. In the first approach, users define the maximum deviation of the returned aggregate value from the correct answer. If the maximum deviation defined in the query is D and the answer to the query is the scalar value v, then the real value of the aggregate result must lie in the interval [v -D, v + D] with probability 1. In the second approach users determine accuracy requirements in probabilistic terms. They enforce a certain degree of accuracy in the estimated result, by defining that the estimated query result v should be within D distance from the real value with probability greater than a threshold p.

Aggregation with Deterministic Error Guaranties

Deligiannakis et al. [START_REF] Deligiannakis | Hierarchical in-network data aggregation with quality guarantees[END_REF] present an algorithm for processing continuous aggregate queries, which is designed for the aggregation tree model. Each node i in the aggregation tree maintains a filtering interval, depicting the range of likely aggregate values at the node. The intervals are set so that the total error at the root is within the desired error budget. If the latest aggregate value at a node lies within its filter, then there is no need to update the parent of the aggregate value, thus reducing communication and conserving energy. Since filters are installed on all network nodes except for the root, the algorithm exploits cases where fluctuations in the values of different sensors cancel each other out at a higher level in the hierarchy, thus avoiding further propagation of updates to the root. Error thresholds are continuously adjusted based on local traffic statistics; the parent evaluates the potential communication savings of increasing the error bounds of its children, and distributes error budgets to maximize the total expected benefit. Additionally, volatile sensor nodes are identified and ignored so that they do not use up most of the available error budget.

Yu et al. [START_REF] Yu | Approximate monitoring in wireless sensor networks[END_REF] present a similar hierarchical model for processing approximate aggregate queries with bounded quality constraints. The proposed Adaptive Approximate Aggregation Protocol (A 3 ) is built upon an aggregation tree, whose leaves represent source sensor nodes and intermediate tree nodes represent clusterheads residing on sensor nodes.

Each source node reports its value to its parent and the parent subsequently aggregates all values and reports to the higher level. The parent keeps track of his children's previous values and calculates a default value and error bound for each child. As in [START_REF] Deligiannakis | Hierarchical in-network data aggregation with quality guarantees[END_REF], a child is allowed to communicate only in the case that its value violates the error bound. The algorithms used to adaptively adjust the default values and error bounds of each node are slightly different in the two papers [START_REF] Deligiannakis | Hierarchical in-network data aggregation with quality guarantees[END_REF][START_REF] Yu | Approximate monitoring in wireless sensor networks[END_REF].

Cormode et al. [START_REF] Cormode | Holistic aggregates in a networked world: distributed tracking of approximate quantiles[END_REF] use quantile summaries to continuously track the full distribution of values in a highly distributed environment comprised of multiple data streams in remote sites. Their algorithms address large-scale monitoring applications in their generality and are applicable, albeit not specific to, sensor networks. The processing of quantiles differs from previous approaches ( [START_REF] Deligiannakis | Hierarchical in-network data aggregation with quality guarantees[END_REF], [START_REF] Olston | Adaptive precision setting for cached approximate values[END_REF]) in that it requires monitoring of the entire data distribution. The base station is responsible for answering user queries on the frequency distribution of the union of all streams. The allowed error tolerance is split into two parts (ε = φ + θ); each remote site monitors the local stream and if its deviations exceed the threshold defined by θ, the site sends to the base station an updated approximate quantile summary error-bounded by φ. In order to minimize the frequency of communication, the proposed scheme uses prediction models piggy-backed to the local quantile summaries. Cormode et al. extended their initial work on flat (2-layer) quantile processing to exploit the merging (cancelling out) of quantile updates in a hierarchical setting. The authors prove that the proposed scheme provides strong ε-approximation guarantees for quantile queries.

Aggregation with Probabilistic Error Guaranties

Considine et al. [START_REF] Considine | Approximate aggregation techniques for sensor databases[END_REF] and Nath et al. [START_REF] Nath | Synopsis diffusion for robust aggregation in sensor networks[END_REF] have indepedently developed techniques for approximate aggregation in the presence of packet loss and node failures. When a spanning tree approach is used for aggregation, a single node or link failure results in the loss of an entire subtree of values. Multipath routing has been proposed as an inexpensive solution to address this problem. For duplicate-sensitive aggregates (e.g., SUM and COUNT), however, multipath routing may lead to incorrect calculations. Both [START_REF] Considine | Approximate aggregation techniques for sensor databases[END_REF] and [START_REF] Nath | Synopsis diffusion for robust aggregation in sensor networks[END_REF] extend the theory of sketches to handle certain duplicate-sensitive aggregates, including SUM and COUNT.

For example, Nath et al. [START_REF] Nath | Synopsis diffusion for robust aggregation in sensor networks[END_REF] utilize order and duplicate-insensitive (ODI) synopses: these are small summaries of partial results that count each sensor's value only once, regardless of how many times or in which order they arrive at a node. The proposed mechanism of synopsis diffusion is based on three basic functions which have different implementations for each query type: Synopsis Generation (SG), which outputs a synopsis given a sensor reading, Synopsis Fusion (SF), which combines two synopses into one and Synopsis Evaluation (SE), used on the querying node to translate synopses back to an answer. Continuous queries are assumed and a ring topology is used in order to illustrate the advantages of multipath routing. The proposed techniques in [START_REF] Considine | Approximate aggregation techniques for sensor databases[END_REF] and [START_REF] Nath | Synopsis diffusion for robust aggregation in sensor networks[END_REF] enable the routing of partial aggregates through multiple paths, and provide fault-tolerant evaluation of approximate aggregates with probabilistic error guarantees.

Hartl et al. [START_REF] Hartl | Infer: A bayesian inference approach towards energy efficient data collection in dense sensor networks[END_REF] further reduce energy consumption in the network by activating a subset of the nodes and use their values to infer the values for the sleeping nodes through Bayesian inference. They specifically focus on the problem of obtaining the average reading in the monitored field. Bayesian inference uses posterior predictive distributions to arrive to conclusions about data that has not been observed, given the existing observations. The algorithm developed is called infer and consists of two phases: during the first phase, a distributed algorithm decides which nodes are going to be active or asleep for the next epoch, which contains several sensing rounds. Both node energy level and the values of sensed data are considered while making this decision, in order to achieve load balancing while making sure that important data will always be available to the sink. The second phase of infer concerns only the sink: it utilizes Bayesian inference in order to predict the average sensor reading of the network, based on the available incomplete dataset. The Bayesian inference approach has the potential of being applied to process a large spectrum of queries beyond aggregates.

Approximate Processing of Non-Aggregate Queries

Sensor networks offer new opportunities to monitor the real world at an unprecedented scale, since they have the potential of covering extended areas for large periods of time. From a research viewpoint, this becomes a real challenge when the application requires fine data granularity instead of data summaries. In this section, we study techniques that aim at processing non-aggregate queries in an energy-efficient manner. They rely on temporal and spatio-temporal correlations in the observed data to significantly reduce communication and increase network lifetime. In Section 3.1, we discuss techniques aimed at minimizing communication from a single sensor, and in Section 3.2, we extend our discussion to minimizing communication from multiple sensors.

Approximate Processing of One Sensor Stream

In [START_REF] Lazaridis | Capturing sensor-generated time series with quality guarantees[END_REF], Lazaridis et al. present techniques for compressing time series values produced by sensor nodes. Their approach focuses on capturing the complete history of a time series, arguing that knowledge of the way the quantity being monitored evolves is essential for a variety of scientific applications. They assume a network of multiple sensors, the producers and a central database, the archiver. The goal is to capture an approximate version of the time series on the archiver, with quality guarantees for each individual value, and to predict future values of the series based on this approximation. The authors utilizes a piecewise constant approximation (PCA) algorithm. PCA is a lossy compression scheme that represents a time series as a sequence of value-interval pairs called segments (c i , e i ), i.e. a constant value c i during e i epochs. They use Poor Man's Compression (PMC), an online version of PCA that computes PCA segments as each value arrives. For example, PCA-Mean samples values and computes their mean, until the mean differs from the minimum and maximum by more than a given threshold. The time required to compute a segment at the producer and send it to the archiver may be long if the time series consists of similar values. To address this problem, the authors consider embedding a prediction model to answer queries concerning current and future values that have not yet been covered by a segment. The model's precision interval can be adjusted using techniques similar to the ones described in [START_REF] Olston | Adaptive precision setting for cached approximate values[END_REF].

Earlier work on processing distributed data streams proposed the caching of data intervals at the source and the base station, and suggested that the source should refrain from propagating its values as long as they fall within the cached interval [START_REF] Olston | Adaptive precision setting for cached approximate values[END_REF]. Jain et al. [START_REF] Jain | Adaptive stream resource management using Kalman filters[END_REF] identified shortcomings in the approach of caching static data to reduce communication between the source and the base station. They propose the use of Kalman filters, and instead of caching data intervals they cache filter parameters that help predict the data. A Kalman filter is a recursive algorithm that predicts the future internal state of a system based on current state information and observations of its external behaviour. The recursive procedure is based on two mechanisms: Prediction, which estimates the system state at time k + 1 and Correction, which adapts the filter according to the actual values observed at time k + 1, making the filter a truly online adaptive model. The authors propose the Dual Kalman Filter Model, an architecture similar to the one described in [START_REF] Cormode | Holistic aggregates in a networked world: distributed tracking of approximate quantiles[END_REF]. Continuous queries are directed to a central server, accompanied by a precision constraint. For a query concerning node i, a Kalman filter KF i is installed on the server and a mirror of this filter is initiated on source i, simulating KF i's operation. The server uses the predictions of the Kalman filter to provide answers about i in the future. Updated values from sensor i are propagated to the server only when the mirror filter (and therefore KF i as well) is found to be incapable of predicting i's values within the specified constraint. The Kalman filter is able to model various processes, including non-linear and noisy ones, making it feasible to apply the same framework to a variety of scenarios.

In recent work, Deligiannakis et al. [START_REF] Deligiannakis | Compressing historical information in sensor networks[END_REF] present a new technique designed for historical data compression in sensor networks. They assume that each source node produces multiple streams of data, one for each type of sensor, and pushes them to a base station. They first construct a base signal from the node's time series and subsequently use it to approximate time series using regression. The authors' intention is to exploit correlations between different time series on a node. The algorithm presented is called Self-Based Regression (SBR): it is given a bandwidth constraint (maximum packet size) and the size of the base signal as inputs and tries to provide an optimal approximation to a node's time series with respect to these constraints. The base signal is initially constructed; SBR splits the locally-stored part of the time series into intervals of various sizes and for each one of them computes the benefit of approximating the rest. The interval that incurs the highest benefit is chosen as a part of the base signal and the process is repeated until the desired base signal size has been reached. The next step is to approximate the series data using the base signal; the algorithm concatenates data from all time series in a node, breaks the resulting stream into intervals and tries to approximate them using equal-sized base signal intervals. The error metric used is the sum squared error and it can be modified to any other appropriate metric. The algorithm was shown to outperform several approximation techniques, including Wavelets, Histograms and Discrete Cosine Transform (DCT), using various real-world datasets.

Approximate Processing of Multiple Spatially-Distributed Sensor Streams

In this section we present recent techniques for processing multiple sensor streams in an energy efficient manner. These techniques make use of both spatio-temporal correlations to perform data reduction.

Guestrin et al. [START_REF] Guestrin | Distributed regression: an efficient framework for modeling sensor network data[END_REF] propose an algorithm that manages spatio-temporal data in a distributed fashion. The network is assumed to contain multiple overlapping regions and in each region significant spatial correlations are expected to be observed. The authors The techniques discussed in Sections 2 and 3 are either push-based or pull-based. In the push mode, data is proactively forwarded from the sensor nodes to the base station, whereas in the pull mode, data is acquired on-demand only when users inject queries into the network. The push mode is suitable for classes of applications that require continuous monitoring at a constant level of precision. Results are forwarded to the base station periodically or when an interesting event occurs. The pull mode is suitable for classes of applications where monitoring is not needed continuously and throughtout the network area; users require data infrequently each time with a potentially different precision constraint. For a variety of applications that lie between the two extremes, neither the push nor the pull mode allow for energy-efficient data dissemination.

In this section, we discuss hybrid push-pull data management techniques that rely on the storage capabilities of sensor nodes. They allow the distributed caching of sensor data within the network at different levels of precision, and raise a number of interesting research problems: i) adaptive precision setting of sensor data, and ii) efficient aging of sensor data and iii) energy-efficient search and access of stored data.

In [START_REF] Olston | Adaptive precision setting for cached approximate values[END_REF], Olston et al. focus on the first problem of adaptively adjusting the precision of cached approximations to achieve optimal performance in a dynamic environment. They assume that an accurate data representation (e.g. an integer value) is stored locally at the source sensor node, and an approximate data representation (e.g. an interval) is forwarded and stored at one or more cache nodes where queries are injected. If the source detects that its value has drifted outside the interval, it initiates a transmission to update the cache, as in [START_REF] Deligiannakis | Hierarchical in-network data aggregation with quality guarantees[END_REF] and [START_REF] Yu | Approximate monitoring in wireless sensor networks[END_REF]. However, unlike [START_REF] Deligiannakis | Hierarchical in-network data aggregation with quality guarantees[END_REF] and [START_REF] Yu | Approximate monitoring in wireless sensor networks[END_REF], the approximate data stored in the cache is not always accurate enough to answer all of the injected queries. If a query's precision is higher that that offered by the cache, the query pulls the exact value from the source node. To avoid source-initiated refreshes, interval widths have to be increased so that the values remain within them. On the other hand, to avoid query-initiated refreshes interval widths have to be decreased, so that adequate precision is offered for most queries. Olston et al. propose an algorithm to search for the interval width that minimizes the probability of a refresh happening, and compare it with competing approaches like Divergence Caching [START_REF] Huang | Divergence caching in client-server architectures[END_REF].

In [START_REF] Ganesan | An evaluation of multiresolution storage for sensor networks[END_REF], Ganesan et al. focus on the problems of graceful aging and multi-resolution storage and search in sensor networks. They use wavelet compression to summarize the data in various resolutions and store the summaries in a hierarchical manner along a quad tree. At higher levels (near the root) summaries are highly compressed but correspond to a larger set of the network data. Querying is performed using a technique that is common in data-mining, called drill-down querying; each query is injected at the highest level, where only coarse summaries exist. Queries that ask for low-precision data are processed locally and the remaining ones are forwarded further to nodes that carry the relevant data at higher resolutions. In order to cope with limited storage, a parametric progressive data aging strategy is proposed, which determines how long each node must maintain summaries at various resolutions before discarding them. If training data is available, the aging function is tuned to maximize query quality, otherwise the authors propose the use of a greedy aging strategy.

In their recent work, Wu et al. [START_REF] Wu | Processing precision-constrained approximate queries in wireless sensor networks[END_REF] consider a push-pull approach to executing various types of one-shot approximate queries with bounded quality. They propose a two-tier data storage scheme, in which the base station stores an imprecise version of sensor data, and the sensor nodes retain their high-quality readings in local memory. Similarly to [START_REF] Deligiannakis | Hierarchical in-network data aggregation with quality guarantees[END_REF] and [START_REF] Yu | Approximate monitoring in wireless sensor networks[END_REF], sensor nodes initiate communication with their parents in the routing tree only when their values drift outside an approximation interval, defined by a specific error margin. The values are propagated all the way to the base node, which stores them together with their approximation intervals. When a query is administered at the base station, it is answered at no cost if its error tolerance exceeds that of the centrally stored data. Otherwise, the base station carefully selects which nodes to query in order to answer the query with minimum effort. Wu et al. present node selection (refresh) strategies for different types of queries, including top-k, range queries, id queries and aggregates. For example, for aggregate queries, the proposed algorithm aims at reducing the load of hot-spot nodes near the base station by favouring nodes in the same subtree. In addition, the algorithm prefers nodes with high energy levels and small hop distances from the base station.

Conclusions

Research in approximate data management for sensor networks is motivated by the fact that most applications do not require accurate reports of sensor data -as long as the data comes with deterministic or probabilistic error guarantees. The flurry of research in this area shows that there exists a great potential in trading the accuracy of query answers for energy savings and increased network lifetime. The techniques discussed in this paper make different assumptions about the mode of communication (flat vs. hierarchical) and computation (pure push, pure pull, or hybrid push-pull); they target a variety of query types, and focus on different research challenges (like adaptive adjustment of error bounds and node selection). They typically exploit correlations between the sensor values, in order to reduce the sensing and communication cost in the network. The different aspects of recent research efforts are summarized in Table 1.

In the near future, sensor networks are expected to be incorporated in a variety of domains, which will raise new application-specific challenges for approximate data management. As the number of competing techniques increases, an issue that we will need to address is how to identify the candidate that best fits the requirements and constraints of a specific sensor deployment.

Data requirements Communication Processing Correlations Paper

(aggr. vs non-aggr. / (pure vs. (flat vs (temporal vs determ. vs probab.) hybrid) hierarch.) spatio-temp.) Deligiannakis [START_REF] Deligiannakis | Hierarchical in-network data aggregation with quality guarantees[END_REF] aggr. determ. pure hierarch. temporal Yu [START_REF] Yu | Approximate monitoring in wireless sensor networks[END_REF] aggr. determ. pure hierarch. temporal Cormode [START_REF] Cormode | Holistic aggregates in a networked world: distributed tracking of approximate quantiles[END_REF] aggr. determ. pure both temporal Nath [START_REF] Nath | Synopsis diffusion for robust aggregation in sensor networks[END_REF] aggr. probab. pure hierarch. Hartl [START_REF] Hartl | Infer: A bayesian inference approach towards energy efficient data collection in dense sensor networks[END_REF] aggr. probab. pure hierarch. spatio-temp. Lazaridis [START_REF] Lazaridis | Capturing sensor-generated time series with quality guarantees[END_REF] non-aggr. determ. pure flat temporal Jain [START_REF] Jain | Adaptive stream resource management using Kalman filters[END_REF] non-aggr. determ. pure flat temporal Deligiannakis [START_REF] Deligiannakis | Compressing historical information in sensor networks[END_REF] non-aggr. determ. pure flat temporal Guestrin [START_REF] Guestrin | Distributed regression: an efficient framework for modeling sensor network data[END_REF] general pure hierarch. spatio-temp. Deshpande [START_REF] Deshpande | Model-driven data acquisition in sensor networks[END_REF] general probab. pure general Chu [START_REF] Chu | Approximate data collection in sensor networks using probabilistic models[END_REF] general determ. pure spatio-temp. Wu [START_REF] Wu | Processing precision-constrained approximate queries in wireless sensor networks[END_REF] general determ. hybrid flat temporal Olston [START_REF] Olston | Adaptive precision setting for cached approximate values[END_REF] non-aggr. determ. hybrid temporal Ganesan [START_REF] Ganesan | An evaluation of multiresolution storage for sensor networks[END_REF] non-aggr. determ. hybrid hierarch. spatio-temp.

Table 1: Design aspects of recent approximate data management techniques.

Acknowledgments

Our work was supported by the Engineering and Physical Sciences Research Council (EPSRC) under the TIME-EACM award EP/C547640/1.

introduce the usage of kernel functions; a region's kernel function maps a point x to a number, depending on the position of x in the region. Basis functions are chosen for each region and the kernel functions are used to weigh these basis functions accordingly during the regression process. Kernel regression is based upon a distributed version of Gaussian elimination which computes the weights for each basis function resulting in the kernel regression estimate that minimizes the mean square error for all the data in a region. A query specifies a set of kernels (regions) and a set of basis functions (e.g. polynomial with maximum degree 3) for each kernel, the parameters of which are computed and returned by the system. Neighbouring nodes need to exchange messages containing basis function coefficients in order to optimize the regression estimate. Regression was observed to perform better as the number of basis functions is increased, especially at times when values change dramatically.

Deshpande et al. [START_REF] Deshpande | Model-driven data acquisition in sensor networks[END_REF] propose the use of statistical models of real world processes to reduce the cost of sensing and communication in sensor networks. The prototype built, BBQ, consists of a declarative query processor and an underlying probabilistic model and planner, based on time-varying multivariate Gaussians. A multivariate Gaussian is the n-dimensional extension of the simple probability density function (pdf ), represented by means and covariances. The initial representation of the pdf is constructed during a training phase, with the use of historical data. The model runs at the base station, where users submit SQL-like queries that include error intervals and confidence bounds. Multiple one-shot queries are considered rather that continuous ones. The pdf is used to determine whether the model is able to answer a query within the target error and confidence bounds without requiring updated values from the network. If not, the query processor has to pick the best set of attributes to observe (called an observation plan) in order to bring the confidence up to the required threshold, while minimizing the sensing and communication cost. BBQ uses a greedy incremental heuristic to identify good observation plans in order to answer range, value and aggregate queries.

Chu et al. [START_REF] Chu | Approximate data collection in sensor networks using probabilistic models[END_REF] tackle the SELECT * problem for sensor networks. They propose a framework for selecting approximate data with bounded-loss guarantees, while minimizing communication costs throughout the network. The prototype built, Ken, utilizes a pair of dynamic probabilistic models, one running at the base station (sink) and the other one at each node in the network. Ken bears several similarities to BBQ proposed by Deshpande et al. [START_REF] Deshpande | Model-driven data acquisition in sensor networks[END_REF] as it evaluates a probability density function and exploits both spatial and temporal correlations between sensors. Their key difference lies in the fact that BBQ is pull-based, i.e. the base station acquires data from the network only when necessary in order to satisfy queries, while Ken is push-based: source nodes monitor their data continuously and only route values towards the sink upon detecting that the sink's model needs to be synchronized with the local ones. In effect, Ken addresses outlier detection, the basic weakness of BBQ. In order to utilize spatial correlations, Ken partitions the sources into clusters, called cliques, and inference is done on one node per clique, the clique root. Finding an optimal partitioning scheme for the network is an NP-hard problem so the authors provide a greedy heuristic that runs locally at the sensor nodes.