From: Rini Kaushik [rinikaushik@yahoo.com] Sent: Tuesday, March 09, 2010 12:42 PM To: Gupta, Indranil Subject: CS525 review 03/09 Trickle: A Self Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks Trickle, is an algorithm for code propagation and maintenance in wireless sensor networks. An interesting observation made in the paper is that sending a few metadata packets costs the same as sending an entire program. The communication to learn when code is needed overwhelms the cost of actually propagating that code. Hence, Trickle aims to efficiently determine when motes should propagate code. It uses a “polite gossip” policy to achieve its goals. Pros: 1)Allows for load proportional traffic which translates into low traffic when the system is stable. 2)Scalable and dynamic, online algorithm which can adapt itself to the changes in the density and doesn’t need a-priori knowledge. Cons/Thoughts: 1)When a mote hears an older summary than its own, it broadcasts an update. .How does it distinguish between an old, lost packet finally making its way through the network? Isn’t there a window whereby the old information may clobber the new information? 2)Multiple motes may choose to respond to the old gossiper, leading to an increase in the traffic. This seems similar to the update coherency protocol used in the multiprocessors. And, hence similar arguments between update vs. invalidate coherency protocol would hold here. If the code updation is very frequent, the traffic in this scheme can be quite high if the motes do not arbitrate amongst themselves before responding to a straggler. 3)How is the detection done? Is it based on the timestamp? If yes, then how is time synchronization ensured and what is is the associated overhead? If it is based on the content of the new code, how is fast detection ensured? 4)What happens if the network partitions and then joins back? Will nodes get updated in the partitioned state? Which code will be considered new when the nodes rejoin? How is arbitration done then? 5)How sensitive is trickle to the polite gossip time interval? Too short an interval will lead to unnecessary traffic and too long an interval will lead to code being out of sync longer. Even though the paper proposes an adaptive interval, it would work effectively only in the scenario where code changes happen infrequently and there are long periods of no updates. 6)Trickle requires the motes to be up all the time for the updation and detection to work which is not energy-efficient. It saves on network costs while increasing the mote’s energy requirements. TAG: a Tiny Aggregation Service for Ad-Hoc Sensor Networks Tiny AGgregation (TAG) is a generic aggregation service for ad hoc networks of TinyOS motes. It provides a simple, declarative interface for data collection and aggregation in a time and power-efficient manner. Pros: 1)The in-network aggregation ability in TAG decreases the communication required to compute an aggregate versus a centralized aggregation approach. It also discards irrelevant data and creates more compact records. 2)It can tolerate disconnections and loss which is critical in sensor environments, where it is very likely that some aggregation requests or partial state records will be garbled, or that devices will move or run out of power. Cons: 1)In TAG’s decentralized architecture, if a node goes down while query aggregation is in process, the entire tree may need to be rebuild. On the other hand, in a centralized architecture, the authority node may have more awareness of the state of the nodes and just do a selective rebuild. If failures are a norm, this issue needs to be given more consideration. The failure scenarios, failure handling mechanisms are not elaborated enough. TAG further makes some assumptions such as an ability to deliver query requests to all the nodes and also to get at most one copy of every message which may not be feasible in such a dynamic environment. 2)Cached results may not be accurate if node failures or disconnections happen. 3)Performance suffers when the query rate is high. 4)The collection phase makes assumptions about the EPOCH length for aggregating readings of all devices in the network during the Epoch and doesn’t show sensitivity to the choice of the interval. From: pooja agarwal [pooja.agarwal.mit@gmail.com] Sent: Tuesday, March 09, 2010 12:21 PM To: Indranil Gupta Subject: 525 review 03/09 DS Review – 03/09/10 By: Pooja Agarwal Paper: TAG: A Tiny Aggregation Service for Ad-Hoc Sensor Networks Main Idea: The paper presents TAG service which describes a query model and environment to query and aggregate results over wireless sensor networks. The query model style is based on SQL and hence, provides a general interface to users for querying and attaining aggregated data from the network. The paper also classifies aggregates based on state requirements, tolerance of losses and sensitivity to duplicity. During network aggregation phase, the user sends the query from the root node. The motes form a routing tree rooted at root dynamically and receive the request from the root. The request is propagated to more motes as they join the tree. Once, all the nodes have joined, each node defines a epoch in which it waits for all it’s child nodes to compute and report to it the aggregated value at their nodes. The leaf nodes compute the query, and transmit the result to its parent. The parent nodes needs to aggregate all the results from it’s child nodes and sends the aggregate to it’s parent. Thus, a time driven aggregation is performed along the path back to the root. Apart from the basic idea, the paper also provides several optimizations around their central idea. They proposed to take advantage of shared channel (wireless) to recover any lost query packet by snooping to packets broadcasted on wireless near it. To improve tolerance to loss, the topology is dynamically updated to remove any node facing failure or low bandwidth. To overcome the problem of critical tree partitioning due to failures of central nodes, they proposed to keep more than one parent and send some portion of the aggregated result to each. This increases fault tolerance and better estimation of results during node failures. Paper also proposes to use caching at nodes to cache recent results from child nodes which can be used during child failures. Pros: 1) TAG discusses various relevant optimizations which greatly enhance the main idea. These optimizations can be used based on application and topology of the sensor nodes. Cons: 1) Though taxonomy of aggregates was presented, the impact of different types of aggregates is discussed deeply in the paper. 2) Although the idea of using several parents to send partial aggregate results is presented in the paper, it lacks a discussion of methods/algorithms used for partitioning aggregate results among more than one parents. There could be several issues involved like group based aggregation, type of aggregates,etc. 3) Need for synchronization between the parent and child nodes in terms of epochs. Paper: Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks. Main Idea: This paper presents Trickle which provides a low power solution for propagating and maintaining code updates in wireless sensor networks. The algorithm uses polite-gossip policy to broadcast code summary periodically to local peers and remain silent when if almost the same summary was recently heard from another node. Each mote transmits all the messages to the local broadcast address. If a mote receives a summary that is out of date, or if mote receives a newer summary then it broadcasts it’s own summary. It is assumed that as long as network is connected and there is a minimum connection rate, everyone will stay up to date. Trickle maintains a counter c, a threshold k, and a timer t. When a mote hears an update it increases c and it randomly chooses a value t in between 0 and T. If c < k at time t than it broadcasts its summary else not. Thus it ensures that there are only k*m transmissions in each time interval where m is non-interferring single hop network. Random sampling between 0 and T ensures load balancing of how many nodes transmit at a particular time. Trickle also analyses the performance of the above algorithm with respect to losses, synchronization, multi hop networks. It is shown that during network losses, the number of transmissions grows with density of O(log(n)), however during worst case the number of transmissions become linear. Due to short listen problem, some nodes might transfer more messages. It was shown that the number of extra messages are bounded by O(n^1/2). To overcome this problem, they introduced a listen time of T/2 before responding/sending any update. It is also shown that as the network size increases, the packet losses also increase due to hidden terminal problem. This, results in some performance loss in multi hop networks. The time interval can also be dynamically scaled based on the updates that have been coming and according to updates done locally on a mote. Pros: 1) Provides a method for code propagation using lesser number of broadcasts and hence, requires lower energy. 2) Analyses the performance of the proposed algorithm in different scenarios like losses, unsynchronized nodes, multi-hop networks and gives further enhancements to the basic algorithm for achieving better performance in these scenarios. 4) Use of randomized sampling of time t from time interval is a good way to incorporate load balancing in network usage. 3) The number of broadcasts is independent of number of nodes in the network. Cons: 1) Trickle assumes that motes are always on which due to energy conservation practices is not true. From: Shivaram V [shivaram.smtp@gmail.com] on behalf of Shivaram Venkataraman [venkata4@illinois.edu] Sent: Tuesday, March 09, 2010 12:17 PM To: Gupta, Indranil Subject: 525 review 03/07 Shivaram Venkataraman - 7 March 2010 TAG: A Tiny Aggregation Service for Ad-Hoc Sensor Networks This paper presents the Tiny Aggregation Service for use in low power, distributed, sensor networks. Traditionally aggregation of values from sensor nodes is performed by a central server which communicates with all the other nodes. Using efficient in-network aggregation techniques, TAG minimizes the amount of communication required to answer the query. Another important goal of TAG is to provide a declarative, high level language to express the query. The language used in TAG adopts an SQL like query syntax and supports queries over a single table called as 'sensors'. The query consists of a 'select' clause that specifies the arithmetic expression over one or more attributes, a 'selection predicate' which filters out individual sensors, a 'group by' clause which indicates the partitioning required of the sensor readings and finally a 'having' clause that suppresses groups not satisfying the predicate. In addition to these SQL like portions of a query, TAG includes a new field, 'epoch duration' which indicates how often updates are delivered. The aggregation operations supported by TAG include max, min, count, sum, average, median, count distinct and histogram and these operations are classified on different dimensions. This classification helps understand what optimizations will be applicable for each aggregation operation. TAG consists of two phases: a distribution phase where queries are routed down through the network and a collection phase where the results are aggregated and routed back up to the root of the routing tree. When a sensor node receives a query, it sends the query out to all its children in the routing tree and waits till their responses are returned. After aggregating their responses along with its own local data, the sensor node replies back to its parent. Knowing the epoch duration of a query and its depth in the tree, lets each node set an appropriate time interval for waiting. This pattern in the flow of data is important as it enables nodes to have their radio and processor idle for most of the time period. The grouping clause specified in a query may require a sensor node to store data and if the storage is full, the sensor node evicts some groups from the storage. The central root node needs to perform aggregation to form an accurate response. Additionally TAG can also tolerate disconnections of nodes and using a 'child cache' of responses from previous epoch, TAG can increase the percentage of nodes participating in the aggregation for a given query. Pros - High level language which removes the complexity of dealing with embedded systems or large distributed systems. Cons - Only a limited set of aggregates are possible and the amount of communication saved is limited for certain aggregates like median, count distinct. Interesting points - The authors suggest that a benefit of the child cache suggests that allocating RAM to application level caching may be more beneficial than allocating to lower level schemes. - When using redundancy of paths to send aggregate value to two parents, the motes could use an extra unique 'mote id' to prevent duplications. Trickle - A Self Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks This paper presents Trickle, an algorithm that can be used for efficient code propagation in sensor networks. Typically sensor nodes are deployed for a long duration at remote sites and there exists a need for the software present on the sensor node to updated. Propagating code fragments is a costly operation (in terms of power) and knowing how often to propagate is important. Also, it is desirable that new versions of the code are propagated as quickly as possible to ensure that all the sensor nodes are running the same version of the software. The proposed Trickle algorithm consists of the following clauses: 1. Each node picks a time interval t in the range [T/2, T], where T is known. 2. Whenever the node receives any metadata which matches the version present locally, increment a variable c. 3. If the node receives metadata which is older than what is present on the node, broadcast the updated code to all neighbors. 4. If the metadata received is newer, then the value of 'c' is reset and a new time interval is picked. 5. If 't' expires, and if c < k, then broadcast the metadata to all neighbors. The essential idea behind the algorithm is that a node will not transmit its metadata as long as it hears messages with the same metadata version. By choosing a random point in a specified time interval, each node will with a high probability only transmit one message under stable conditions. When there is an update and node listens to a message with older metadata, it immediately broadcasts the newer code fragments to all its neighbors thereby ensuring that the propagation time is low. One additional optimization proposed is to have two time intervals, T-high and T-low which are the upper and lower bounds for the time interval. When there is no change in the metadata, the value of T is doubled till T-high is reached. When an update of the metadata or code fragment is observed, T is reset to T-low. This provides two important characteristics: firstly the chatter during stable times is kept low, secondly when a new code fragment arrives it is propagated fast as the timer is reset. As the number of nodes in the sensor network increases, Trickle scales as O(log(n)) in multi-hop networks, where 'n' is the number of nodes in the system. Pros - Very low resource usage to provide an important functionality in sensor networks - Using two different values of T-high and T-low to satisfy the two goals of the problem. Cons - Trickle does not work around the 'Hidden Terminal' problem and the transmission scales as O(log(n)) due to that. - As the motes need to listen to broadcasts from neighboring motes continuously, they may not be able to turn off the radio to save power. From: Ghazale Hosseinabadi [gh.hosseinabadi@gmail.com] Sent: Tuesday, March 09, 2010 12:14 PM To: Gupta, Indranil Subject: 525 review 03/09 TAG: a Tiny Aggregation Service for Ad-Hoc Sensor Networks In this paper, Tiny Aggregation (TAG) method to be used in sensor networks is presented. The main features of sensor networks are their low power, distributed structure and ad-hoc wireless manner. TAG considers the ideas from selection and aggregation methods of database query languages and uses them data collection and aggregation by sensor motes. Furthermore, TAG considers resource constraints of motes as well as lossy wireless communication environment in its design. Aggregation queries of TAG are distributed and aggregated in a time and power-efficient manner. Data aggregation in TAG is done in network, instead of being implemented centrally in order to reduce bandwidth and power consumption. Whenever the base-station demands data aggregation by sensors, sensors route data back towards the base station via a routing tree rooted at the base station. As data flows up this tree, it is aggregated according to an aggregation function and value-based partitioning specified in the query. Aggregation mechanism is done at any parent node whenever it receives data from all its children.The authors designed a simple language for declaring queries in TAG. They also discussed the benefits of in network data aggregation. They also introduced a couple of optimizations to improve the performances. They also design some methods to decrease the loss of the results of aggregation. Pros: TAG is a complete protocol designed for data aggregation in sensor networks. The design is comprehensive. Different functionalities are designed. The way that different components of TAG are interacting with each other, introduces high efficient optimizations in the performance of TAG. It resembles the design of the whole protocol stack of networks. Cons: TAGs performance is based on constructing and maintaining a tree by sensor motes, which can be costly in some cases, where network is highly vulnerable to partitions or when sensor nodes have limited memory. Each parent is required to maintain list of its children, and in a dense network, it requires large amount of memory. No comparison with other methods introduced in the literature is presented. Theoretical analysis for the performance improvement achieved by each optimization scheme is not presented. It is not clear what percentage of improvement is achieved because of each optimization method. Trickle: A Self Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks In this paper, a scheme for propagating code updates in wireless sensor networks in presented. The designed method, is called Trickle. Trickle tries to reduce number of broadcasts needed to perform updates. Sensor nodes periodically broadcast a code summary to local neighbors but stay silent if they have recently received a summary identical to theirs, which means that no update has happened in the region including the sensor node and its neighbors. When a mote hears an older summary than its own, it broadcasts an update. This method decreases the amount of times the network is flooded. The effect of data loss as well as lack of synchronization on Trickle is considered and discussed. The authors investigated the performance of Trickle in terms of time needed to perform updates in a testbed of sensors. Pros: Trickle prevents unnecessary broadcasts by comparing the nodes code with the one received from neighbors in order to make sure that broadcasting is necessary to keep neighboring nodes updated. Cons: The comparison done at each sensor node after each broadcast might be costly if the code compared is lengthy. It consumes nodes power. The amount of time and power spend for these comparisons are not considered in the design and performance analysis. From: Vivek [vivek112@gmail.com] Sent: Tuesday, March 09, 2010 12:09 PM To: Gupta, Indranil Subject: 525 review 3/9 Core idea: In this paper, a technique and algorithm is presented where code is easily updated in a wireless sensor network. The ideas presented address the issues of "broadcast storms" in wireless sensor networks. It borrows ideas from gossip algorithms. Motes periodically broadcast to neighboring motes, but stay quiet if they have heard the update already. The ideas are established through a high-level algorithmic simulator, and then tested in a practical way on a real sensor network. Pros: - scales to thousands of motes - used in a wide range of networks - propagates code and reprogramming in seconds. This is very practical for sensor networks that are used in applications such as weather simulation, because updates may need to be made in a very short amount of time. Cons: - The design assumes that motes are always on. However, many motes use power-down mechanisms to save energy. While they acknowledge this in their design, it seems that more is needed to truly justify their results. - Regarding algorithmic simulation and TOSSIM, are these simulations extensible and applicable to other types of sensor networks? And how could they be used? This would really help to understand and compare the ideas presented in the paper to real-world sensor networks (but this is more of a suggestion to further improve the paper, not really a weakness). Core Idea: This paper presents an aggregation service for motes(specifically the new TinyOS). The aggregation service is intended to gather data and group it in such a way that is de-centralized and does not require the knowledge of the topology in advance. A routing tree has its root at a basestation, with each node that understands the query to be added to the tree through the aggregation operation. An important part of this paper is the programming model that they use for maximizing expressivity of applications involving data operations, for application programmers. Pros: - Demonstrates an actual program that can be used to generate their results. This gives the impression that the work has been well-thought out. - Provides the broader impact overall for TinyOS and TAG. - Show how in-network communication can dominate any type of centralized service that is used. Cons: - With all of this rich infomation, how do we know what programming model is the best? This is just one programming model, but have they truly been able to quantify and show that the programming model is indeed effective? -One issue that also seems to be problematic is the difference between what the user expects SQL to output, versus what it actually does behind the scenes. Furthermore, is performance really an issue? Or is it fault-tolerance? How much of each? From: Giang Nguyen [nguyen59@illinois.edu] Sent: Tuesday, March 09, 2010 11:49 AM To: Gupta, Indranil Subject: 525 review 03/09 CS 525 review 03/09/2010 nguyen59 TAG: A Tiny Aggregation service for ad-hoc sensor networks Wireless sensor network applications collect data from the network. In many cases, the researcher is interested some aggregation of the data, not the individual raw data points from individual sensors. This paper presents a generic aggregation service for ad hoc networks (of TinyOS motes) that provides a simple SQL-like interface for data collection and aggregation and intelligently distributes and executes the aggregation queries in the sensor network in a time and power-efficient manner. The communication model is the sensor network builds a tree that is rooted at the basestation node. The user enters a declarative query at the basestation node, which, during the distribution phase, distributes the query down the tree. Each node sends the query along with the time interval "I" during which it expects the result from its children, then each child repeats the same while setting the interval "I" to be before the interval its parent expects the result. During the collection ph! as! e, the leaf nodes send back raw data to their parents, which perform the aggregation function along with their own sensor readings, and forward the aggregated result (partial state record) to their parents, and so on, up the tree to the basestation. The nodes can implement optimizations such as snooping other nodes' partial state records (for example, if the aggregation function is MAX, and a node hears a partial state record that is higher than its own sensor reading, then it can suppress its communication). Pros: - In-network aggregation reduces the communication required, compared to all nodes sending its raw data (and forwarding others) to the basestation for aggregation. - Generic SQL-like language is easier for sensor network users who might not be familiar with programming the low-level of sensor network devices. - A thorough evaluation section (albeit simulation-based). Cons: - The network tree has to be built and maintained because nodes might fail or leave the network. - During periods of changes in the network tree, aggregated results might have errors. ------------------------------------------------------------ Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks Some sensor network deployments last months or years. The application developer needs the ability to reprogram the sensors (eg, to fix a bug) remotely without physically collecting them. There are several wireless reprogramming systems available for sensor networks. The user introduces new code to a node in the network, and the new code will be picked up by the rest of the network. Trickle presents an algorithm that efficiently manages and propagates new code in a wireless sensor network. For maintenance, in each interval T, each node randomly picks a time t within T, and broadcasts its "my code version" at time t unless it hears at least k other nodes broadcasting the same version before time t, in which case it suppresses its broadcast. Assuming a lossless, single-hop network of size n, the sum of transmissions over the network is 1/n. In a network with lost packets, the sum of transmissions is O(log(n)). The paper goes on to consider other issues that arise when there is ! no! t perfect synchronization among nodes and for multi-hop networks and adjust the algorithm to account for those issues. When a node hears a neighbor with older code version, it kickstarts propagation. Or when a node hears a neighbor with newer code version, it broadcasts its old version message to cause the neighbor to kickstart propagation. Since a higher interval T means slow propagation, and a lower T means higher maintenance communication, Trickle dynamically scales the interval T. It increases T (upperbound T_h) if there's no new code and resets T to T_l when there is new code. Pros: - The algorithm is quite simple, requiring very little state. - Maintenance communication overhead scales logarithmically with node density. - The empirical study shows maintenance overhead of 3 messages/hour while able to propagate new code throughout entire network in 30 seconds. Cons: - Assumes that the nodes are always on. - Paper doesn't describe the algorithm of code propagation. From: Kurchi Subhra Hazra [hazra1@illinois.edu] Sent: Tuesday, March 09, 2010 11:13 AM To: Gupta, Indranil Subject: 525 review 03/09 TAG: a Tiny Aggregation Service for Ad – Hoc Sensor Networks --------------------------------------------------------------------------------------- Summary ------------- This paper presents TAG, a generic aggregation service for ad hoc networks of TinyOS motes that uses a simple, SQL – like declarative language for expressing aggregation queries over sensor network data. The authors classify the kinds of aggregate functions and the ones that can be take advantage of such a setup. The language also allows for choosing attribute values by storing a small catalogue of attributes in every mote. In-network aggregation used in TAG has two phases. In the distribution phase, starting with a root at the base station, the query is distributed over the network by arranging all nodes in a routing tree. On receiving queries, sensor motes send data towards the root of the tree. As data flows up this tree, it is aggregated according to the aggregate function. This is known as the collection phase. Each mote waits for a specified duration for its child to respond with the aggregated data of the entire sub-tree that the child is responsible for. The authors also propose some optimizations to improve TAG performance. For example, they propose that motes snoop on the shared channels to be aware of any unheard aggregation going on in the network at present and participate in it. A guess on the aggregated value can also lead to elimination of entire sub trees from the aggregation process. In case of link failures, a child can maintain a list of neighbours with good links, and switch parents. The parent can deal with the inconsistency caused by such a switch by caching some of the results that the child passed on to it earlier. Experimental results show that TAG can achieve a 50% decrease in communication costs in terms of the number of messages, as compared to centralized approaches to aggregation. Pros ------ -- In-network aggregation, when well studied and fine-tuned, can lead to a cut in the communication costs as demonstrated in this paper. -- The simple query language enables individuals with little or no knowledge about low level sensor network details to use sensor networks. Cons ------- -- There are no experiments or statistics shown about the fanout in the trees constructed and how this fanout affects the communication costs or network congestion. The fanout should be an important factor here, since it will involve a tradeoff between the amount of communication and computation cost. -- Although the aim of the authors is to have a generic language, it is quite difficult to generalize a language and introduce optimizations for all kinds of possible aggregate functions without increasing code size. -- The authors propose caching when a link fails. However, the parents will be using stale data, which should not very effective in most sensor network queries. -- Caching will not work when a parent mote itself dies. -- The authors do not talk about how the epoch varies in case of failures. An even division of epoch will not work in this case. -- A lot of ideas in the paper have been merely proposed and not evaluated. Trickle: A Self- Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks -------------------------------------------------------------------------------------------------------------------------------------------------------- Summary ------------- This paper present Trickle, an algorithm for propagating code updates in wireless sensor networks, which uses “polite gossip” to exchange code metadata with network neighbours. To do this, each mote maintains a counter k, a threshold c and a timer t in the range [0,?], where ? is a time constant. Every time a mote receives metadata identical to its own, it increments c. At t, it broadcasts its metadata in case c