From: w SpamElide on behalf of Will Dietz [wdietz2 SpamElide] Sent: Thursday, March 17, 2011 12:34 PM To: Gupta, Indranil Subject: 525 Review 03/17 3-17-2011 cs525 Will Dietz "Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks" Sensors networks are widely deployed today, and one common problem they face is how to update the code. Sensor networks can be expensive to deploy, and manually updating the code is often impractical or otherwise undesirable. But how to send code updates? They are many important issues to tackle such as energy consumption, how to encode the updates, and the like. One things the authors point out that I found interesting was that such a propagation effort must be *continuous*--due to intermittent (and transient) communication failures, propagation must always be active such that any newly rejoined sensor node can be updated accordingly. Additionally the propagation mechanism must be "low maintenance"--it must use as few packets as possible in steady-state to preserve energy, it must be propagate *quickly* so that the network can continue to be useful (half of the network running different code might not be the best), and in has to scale. One interesting thing the authors use as a design point based on this last point is that their algorithm doesn't have any "a priori" density information. With all this in mind, these Berkeley researchers present "Trickle", their algorithm for handling all this, that provides a few knobs to make it fit your network appropriately. The heart of this is their "polite gossip" idea, essentially attempting to periodically broadcast information if no one says anything, but if someone says something interesting (they have a different version of the code, newer or older) they speak up and send updates as they can. Most importantly with regards to energy consumption, if someone else is saying what you want to say (your version of code), you stay quiet, providing the "polite" part of this gossiping. I was rather fond of the way this work was presented--by starting from the more accessible model with a number of assumptions about the network, and synchronization--and then iteratively removing those assumptions and showing how to handle them. It's how I'd want to explain it to someone, and it's how I might tackle a similar problem. Nice change from "here's all the low level details for problems you probably don't know exist because we spent the last 3 years figuring them out ourselves" :). Finally, I'm a tad curious about how these networks encode the code updates themselves. They mention some high-level bytecode is used sometimes, so presumably these devices have some kind of VM or compiler to make that into something they can run, but I'm curious for details. One interesting thought I had while pondering this was that one way you might want to encode an update is a small diff--say you're changing the value of a constant or something similar. Sending the entire binary might be a problem in that regard. However, while they don't seem to mention this, their algorithm seems to assume that any version of the code can be updated to any OTHER version of the code, simply by sending the code from the newer to the older. It's an interesting problem because sending an incremental update might conserve packets and energy, but since you can never guarantee/know/bound when a node might join from 2+ versions ago, you'd have to do something clever. Storing all the incremental updates would probably be impractical, etc. Just a thought. "TAG: A Tiny Aggregation Service for Ad-Hoc Sensor Networks" ...More Berkeley researchers (plus an Intel guy). Interesting. Berkeley do a lot of sensor network stuff in general, or these just two isolated data points? Anyway TAG is a system that builds upon some of the same goals as Trickle--low power and effecient communication on sensor networks (in particular looking at TinyOS motes again), but this time the focus is on providing a service for handling queries. The big contribution here isn't the communication itself--they build upon an existing ad-hoc communication system of a tree rooted at the broadcast center. The center sends the query, and the query is sent out and comes back up through the nodes. What's the most interesting part of this is how they build their query language around aggregate functions that provide an abstraction such that as the query response is routed it can be, well, aggregated and this results in energy savings through communication and processing gains. The simple example they give of this is trying to count the number of motes--the leafs in the tree return '1' and all the interior nodes return 1+the sum of their children, and this way, by exposing the aggregation logic in their query language, only 1 message is sent back at each node up the tree, as opposed to a less expressive query might result in every node having to send a message all the way back to the root. ~Will Dietz From: kevin larson [kevinlarson1 SpamElide] Sent: Thursday, March 17, 2011 12:24 PM To: Gupta, Indranil Subject: 525 review 03/17 The authors of Trickle present the problem of updating software in a sensor network in a power efficient manner. They had to fight with changing topology and as a result an inconsistent set of neighboring motes. On top of this, they had to fight with the standard issues facing wireless networks, with packet loss and interference. On top of this, the authors wanted it to be scalable, with a maximum increase in O(log n) increase efficiency/latency as nodes increase. Despite all this, they still pushed for rapid propagation. All these goals other than fighting the network topology seem to be proportional to how many packets the nodes send out. The authors propose a heartbeat maintenance scheme, which is built around the potential for a node to not have to respond after hearing two others over the course of an interval, unless that node hears that it has an out of date version of software. They test their algorithm in an ideal environment and it performs very well. They slowly relax their ideal assumptions. As a result of this, their performance dropped, but still maintained their O(log n) goal. The authors did very well in describing their motivations and goals for their project and describing their decisions in terms of these motivations. It was particularly interesting to see how the non-ideal conditions affected various metrics of the performance of Trickle. The topology visualizations as well as the empirical testbed were very informative. TAG proposed using aggregation to reduce the network traffic, and as a result, the power consumption of sharing and computing data. They architect a tree to aggregate the data through. They analyze various calculations and aggregations for various calculations and analyze how much data can be aggregated at each step up the tree. They use Epochs to allow for nodes to shut off their radios to decrease power consumption and allow for adequate time for aggregation. They propose a couple methods for managing child and parent nodes in the case of failure, ranging from discovery techniques to supporting multiple parents. They evaluate their implementation in a simulated test-bed with a few metrics attempting to model ideal to realistic network properties. The authors did a good job explaining their architecture and how it worked with the various types of aggregation. They also thoroughly evaluated and explained their various optimizations and the marginal improvements they provided. Although the breadth of the evaluation was interesting, it could have had more detail. Modeled implementations only go so far, and they only had a very simple implementation, which they didn’t even describe in too much detail. From: Long Kai [longkai1 SpamElide] Sent: Thursday, March 17, 2011 12:24 PM To: Gupta, Indranil Subject: 525 review 03/17 TAG: a Tiny Aggregation Service for Ad-Hoc Sensor Networks Summary: Tiny AGgregation is an aggragation service for low-power, distributed, wireless environment. The interface uses declarative queries like SQL and distributed the aggregation computation in the ad hoc network and executed efficiently. Time, power and bandwidth are efficiently saved. TAG processes aggregates in the network by computing over the data as it flows through the sensors, discarding irrelevant data and combining relevant readings into more compact records when possible. Users pose aggregation queries from a powered, storage-rich base station. Operators that implement the query are distributed into the network by piggybacking on the existing ad hoc networking protocol. Sensors route data back towards the user through 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. Pro: TAG is much more efficient than centralized approach in terms of power, time and bandwidth. TAG allows more complicated optimization and it is very flexible to upper level operations. Cons: The topology of the network may change dramatically and it is hard to maintain the structure of the network in aggregate data without duplication and loss. Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks Summary: We present Trickle, an algorithm for propagating and maintaining code updates in wireless sensor networks. Motes periodically broadcast a code summary to local neighbors but stay quiet if they have recently heard a summary identical to theirs. When a mote hears an older summary than its own, it broadcasts an update. By using a dynamic communication rate, Trickle achieves a reprogramming rate comparable to frequent transmissions while keeping overhead comparable to infrequent transmissions. Pro: Trickle achieves low maintenance, rapid propagation and scalability by using the techniques in gossiping and epidemics. Cons: Motes in the system are not always on for energy reason and this would make the system much more complicated. -- Larry From: harshitha.menon SpamElide on behalf of Harshitha Menon [gplkrsh2 SpamElide] Sent: Thursday, March 17, 2011 12:17 PM To: Gupta, Indranil Subject: 525 review 03/17 TAG TAG is Tiny AGgregation service for aggregation in low-power, distributed, wireless environments. TAG allows users to express simple, declarative queries and distribute them efficiently in networks. TAG processes aggregates in the netowrok by computing over the data as it flows through the sensors, discarding irrelevant data and combining relevant readings into more compact records. The routing of the data to the user is through a routing tree where the user is at the root. Pros: -Gives a high level language for aggregating data -Since the data is aggregated as it flows through the sensors and irrelevant data is discarded, it reduces the communication required and thus energy. -Even if some of the motes are unavailable, TAG would still be able to give the aggregated result. -TAG uses the notion of epoch, which is a regular interval at which data is propagated. It waits for epoch interval for the child node to transmit the result. This reduces the energy since the processors are idle the rest of the time. Cons: -Since the routing is based on a tree, if any node fails, the tree has to be rebuilt. Maintaining this tree would be the overhead. -If any mote is unavailable, then the cached result given back to the user could be stale. -This will work in only certain aggregation operations like total count etc but for other kinds of operations the whole data would be passed around in the network which doesnt serve the purpose of reduced communication. -How does the epoch interval vary during failures? This hasnt been discussed Trickle Trickle is an algorithm for propagating and maintaining code updates in wireless sensor networks. It uses gossip protocol for this. A node transmits the metadata information to its neighbors. If a node receives a metadata which is older than its state, it sends an update. Similarly if it receives a metadata which is newer than itself, then it updates the interval. Pros: -Is highly scalable and the propagation is within seconds. -If the system is stable, then it requires metadata exchange infrequently ie traffic is lower when the network is stable. This is due to dynamic selection of interval to transmit the metadata. -Since it is using gossip protocol, it is highly reliable. Cons: -In gossip based communication, a mote could talk to the already affected neighbor which is a wastage of energy. -This requires motes to be always on which would reduce the energy. From: anjalis2006 SpamElide on behalf of Anjali Sridhar [sridhar3 SpamElide] Sent: Thursday, March 17, 2011 12:06 PM To: Gupta, Indranil Subject: 525 review 3/17 TAG: A Tiny Aggregation service for ad-hoc sensor networks, S. Madden, et al, OSDI 2002 TAG is an in-network approach to data aggregation in low-power, distributed, wireless environments. It provides an interface that is similar to the database queries. The two constraints of sensor networks – memory and power are taken into consideration by aggregating in the network over the data flows. The users query from a powered storage rich base station. This base station is the root of the tree over which the sensor data is aggregated. The main difference between the SQL statements and the adopted query language in TAG is that the sensor data is a stream of values as opposed to a single one in SQL. TAG assumes symmetric links in the broadcast medium. It also assumes that all nodes are reachable, there is more than one route to the root of the tree and there is no duplication. TAG is able to provide an order reduction in bandwidth when compared to centralized data aggregation. The simple declarative query structure provided for end users provides abstraction from the routing protocols and loss tolerance that is implemented. In the aggregate tree constructed, there is no mention of the maximum number of children that a node can have. This leads to a non-uniform usage of power resources in the sensor network. It is also seen that the lesser the depth of the sensor node, the more the data that will need to be transmitted. It is unclear how this unfairness is dealt with. The selection of the epoch interval is decided by the depth of the tree constructed. However it is unclear as to how the network will obtain this value as the tree is constructed. The paper also mentions that in results from the real world experiments, the loss rate is as high as 20%. Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks, P. Levis et al, NSDI 2004. Trickle is a protocol used to communicate code changes to all the nodes in a sensor network ensuring the minimal use of power and scalability of the network. It uses a polite gossip which is essentially a node responding only when it realizes that the update it hears is outdated. The nodes also adjust the time interval during which they overhear packets. If they hear an outdated packet they broadcast more often to propagate the new code. A node transmits code metadata at a random point in an interval. If a node hears an old update, it broadcasts the new code to update everyone else it stays quiet. If a node hears a new update, it broadcasts its old metadata in order to trigger the broadcasting of the new code. Since synchronization between nodes is hard, the first half of all intervals is designated to be the listen only interval. This prevents premature broadcasting of metadata. Trickle provides a way of maintaining a sensor network by broadcasting updates with limited number of messages. By listening to the current updates and using the right suppression technique, the need for updates is broadcasted. Trickle does not scale well when the density of networks increases. This is because of the hidden terminal problem. The collisions due to this result in packet loss. Hence redundancy increases leading to more transmissions than required. Redundancy is mentioned only in terms of packet loss. However there could be more than one node broadcasting the same new code. The paper does not talk about suppression techniques regarding that. The creation of network partition and the churn of nodes can also lead to sudden updates; the paper does not mention these issues. From: Simon Krueger [skruege2 SpamElide] Sent: Thursday, March 17, 2011 12:02 PM To: Gupta, Indranil Subject: 525 review 03/17 TAG: A Tiny Aggregation service for ad-hoc sensor networks, S. Madden, et al, OSDI 2002 Core idea of the paper: Tiny AGgregation (TAG) service is for performing aggregation operations in a network of distributed low-power wireless sensors (i.e., UC Berkeley motes). Motes are used to monitor and collect data for civil engineers, biologist, and computer administrators. All of the applications must aggregate the data they collect. Previously aggregation was viewed as a specific mechanism that is coded into the devices, but they present TAG which places aggregation as a core service of the system and presents the interface to the service has a high level abstraction rather than a low level C API. This allows non expert users to collect data. Pros: Declarative interface for data collection and aggregation, similar to selection and aggregation in SQL Distributes and executes aggregation queries in the sensor network in a time and power efficient manner Sensitive to resource constraints and loosely communication properties of wireless sensor networks. TAG queries are a stream of values rather than a single aggregated value which is useful in monitoring applications. They classify aggregates according to their state requirements, tolerance of loss, and duplication sensitivity, and monotonicity. They use a simple tree-based routing scheme Aggregations are computed when ever possible to lower the number of message transmissions, latency, and power consumption TAG can tolerate disconnected nodes. TAG has a mote send a single message per EPOCH Power can be saved by idling the processor during an EPOCH They do no worse than the centralized approach in each type of aggregation query Cons: Grouping may cause the data size to be larger than the nodes capacity causing certain groups to be evicted from local storage. Their evaluations are mostly simulation based. Thoughts on how the paper can be furthered developed: How well does it work with node failures? Any questions, criticisms, thoughts, doubts, or wanderings: This paper sounds vary similar to pig latin. I think it was a novel idea and their evaluation shows that it is better than normal centralized queries but I am wondering if the declarative query language is enough? Will it be able to collect all types of data? Or will there be some special types of data or special types of query operations that will be required and that the declarative language does not support? Synopsis diffusion for robust aggregation in sensor networks, S. Nath et al, ACM TOSN, 2008 Core idea of the paper: Instead of using a spanning tree that does effectively handle node and transmission failures they present synopsis diffusion which decouples aggregation from message routing which allows the use of multi-path routing. An example of one such routing topology is Rings, which organizes the nodes into a set of rings around a querying node. Pros: Can get redundant message routing for an energy consumption tradeoff. Rings generates the same optimal number of messages as tree-based approaches Since there are multiple paths, Rings are more robust (to node and transmission failures) They present a formal foundation for duplicate-insensitive aggregation Cons: ? Thoughts on how the paper can be furthered developed: ? Any questions, criticisms, thoughts, doubts, or wanderings: A large core of this paper seems to be on ODI which did not seem very interesting to me. Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks, P. Levis et al, NSDI 2004 Core idea of the paper: They present Trickle which uses a polite gossip policy for propagating and maintaing code updates in wireless sensor networks. Pros: Motes adjust the length of their gossiping attention span when there is new code Trickle uses a few packets an hour Propagates updates across multi-hop networks in tens of seconds Scales to thousand fold changes in network density Trickle handles network repopulation, network loss, and disconnection, and requires very little state Decouples code advertisement from code transmission Cons: Motes are assumed to be always on and does not account for duty cycles Thoughts on how the paper can be furthered developed: Maybe consider security? What if other people try to hijack your motes? Simon Krueger From: Michael Ford [mdford2 SpamElide] Sent: Thursday, March 17, 2011 11:51 AM To: Gupta, Indranil Subject: 525 review 03/17 Synopsis Diffusion for Robust Aggregation in Sensor Networks The authors present a technique called order- and duplicate-insensitive (ODI) synopses to address typical problems in sensor networks. Traditionally, sensor network queries are reported in a tree structure. This requires nodes to either expend large amounts of power on reliable transmission or to accept large inaccuracies in the reported data. ODI takes advantage of the wireless transmission medium and creates a ring topology surrounding the querying node. Synopses are generated and propagated to smaller rings in successive epochs. ODI assumes loose clock synchrony between nodes. Although this is a limitation when requiring exactness, in reality, loose synchrony may be enough to provide good-enough results. The real magic is coming up with algorithms that can be aggregated without affecting the results. One example given is using a probabilistic bit flipping approach for counting active nodes. Most of the algorithms described hinge on probability. The paper does not put bounds on the accuracy of the algorithms other than mentioning that maintaining multiple values in the same query response will increase accuracy. Using the ring topology proves to be a much more reliable architecture, while the ODIs produce good enough results. Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks Trickle has become a well known update mechanism for low power sensor networks. It is based on a polite gossip protocol, only sending summaries periodically and if it has not received a transmission differing from its own summary. When a node receives an out of date summary, it triggers a code update. The polite nature of the gossip protocol selected implies that all nodes must periodically send their summary; otherwise no one would hear if a node needs to be updated (due to the hidden terminal problem). Using more strict communication protocols would avoid this issue, but due to the transient nature of failures in sensor networks, alternative approaches, if correct, would incur huge costs while keeping track of state. The distance-based communication nature of sensor networks allows the authors to use propagation topography graphs to illustrate the speed of their approach. It is one of the most effective uses of graphics that we have seen in our reading. The paper does not address piggybacking on duty cycles. Sleeping nodes act like transient failures, which affect the speed and scalability of Trickle. From: Agarwal, Rachit [rachit.ee SpamElide] on behalf of Rachit Agarwal [agarwa16 SpamElide] Sent: Thursday, March 17, 2011 11:47 AM To: Gupta, Indranil Subject: 525 review 03/17 Rachit Agarwal ---- Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks This paper presents a distributed algorithm for propagating code updates in wireless sensor networks. The proposed algorithm borrows techniques from gossip and multicast algorithms, and is targeted to achieve low maintenance, rapid propagation and scalability. The paper is interesting from multiple perspectives: it is a well-written paper that tries to handle all corner cases and does provide guarantees in stable network scenarios. My ideas/thoughts on the paper: 1. A quick question on the motivation for this work: I believe most of the sensor network applications take readings in some infrequent intervals. If that is indeed the case, why do we need rapid propagation of the code as a primary motivation factor? It would be good to have that, but probably we could design better schemes if we can relax that requirement. 2. Some implementation questions: how complex is it to describe a code as a metadata? More importantly, how complex is it to compare two metadata? I believe if metadata is some sort of hashing, it would be easy but hashing is not exactly "metadata". Finally, the paper assumes reliable broadcast .. really? 3. The authors argue that "average number of transmission per mote" is no less interesting than transmissions per mote. I quite disagree. I believe it is more important to reduce the utilization of radio per mote -- the network lifetime of networks (more so for sparse networks) may be the same as minimum among the lifetime of the nodes in the network. ---- Synopsis Diffusion for Robust Aggregation in Sensor Networks Sensor network aggregation is a difficult problem. If a protocol uses a single-path routing for aggregation, it is energy efficient but is not robust to network failures. On the other hand, if the protocol uses multiple paths, it is robust to failures but is neither energy efficient nor provides high aggregation accuracy. This paper presents a synopsis diffusion scheme that uses multiple paths (and hence, is robust to failures) and does not consume *too much* extra energy while providing high accuracy. I really like the theoretical approach taken in this paper -- the use of approximation algorithms in the context of order- and duplicate-sensitive aggregations was really interesting. My ideas/thoughts on the paper: 1. The use of broadcast in the paper was rather surprising for two reasons. First, broadcast is mostly unreliable and it is not clear how to implement reliable broadcast without significant messaging overhead (and hence, extra energy consumption). Second, If I remember well, the energy spent in listening to the channel in sensor motes could be significant. Broadcast results in a significant number of redundant packets in the network, possibly increasing energy consumption (of course, also depends on network topology and density). 2. The design of Synopsis diffusion seems very inflexible to me -- it requires very specific implementation of the mechanisms described in the paper to achieve the observed performance. What performance should we expect if we switch to a slightly different way of implementing the routing schemes, for instance? 3. Synopsis diffusion offloads the transformation responsibilities to the users. It would have been really interesting to have a class of libraries that would allow ease of implementation. ---- -- Siebel Center for Computer Science, University of Illinois at Urbana-Champaign, Web: http://agarwa16.wikidot.com ---- Sing as if No one is Listening, Dance as if No one is Watching, Dream as if You'll Live Forever, Live as if You'll Die Today !! From: Andrew Harris [harris78 SpamElide] Sent: Thursday, March 17, 2011 11:24 AM To: indy SpamElide Subject: 525 review 03/17 Review of “Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks”, Levis et al, and “TAG: a Tiny Aggregation Service for Ad-Hoc Sensor Networks”, Madden et al Trickle is a scheme for pushing code updates to wireless sensor motes in a mesh network. It functions by limiting the update payload to small incremental pieces that are sent as part of the packet header of control packets in the network in a gossip-like fashion (called “polite gossip”, in that the update isn’t pushed to nodes which do not need it). This has the overall effect of better resource utilization, with a power expenditure no greater than that of a network with no updates pushed. This is in contrast to the typical scheme for pushing updates across a mesh network, where each update is pushed in full, requiring orders of magnitude more power consumption. Trickle also addresses data redundancy in that, if a node is near an ongoing update, it will not itself attempt to reproduce the update unless there is some set of nodes reporting that they have not received the beginning of the update. The group shows that such an update model can push updates to all the nodes in a simulated mesh within a reasonable amount of time (seconds to minutes), again at low power cost. Trickle is suitable for mesh networks using nodes with very limited onboard code. The example motes used in the paper have no more than tens of kilobytes of onboard ROM that would need to be updated. Trickle is fine in pushing this amount of data across its control packets, however it would not be suitable at all for motes requiring, say, megabytes of information. Where the update size may vary, the packet header size remains a fixed implementation, unless packet headers themselves are re-engineered to be of larger or variable size (which defeats the purpose of packets anyway). Trickle also has apparent issues with networks whose overall communication is very limited. Consider motes that must be operational for weeks or months on end, whose heartbeats and similar communication are limited to intervals of hours or longer. This would be the case for applications like wildlife or nature monitoring, where the motes would not have updates to send for long periods of time. Trickle would fail to push updates in a timely fashion across such a network, as the low overall communication would hinder data transmission. TAG is a method used to queue and aggregate data transfers across a mesh network, to reduce the overall number of transmissions (and thus reduce power consumption) across that network. The group designs in a database query-like language, so that programmers can issue data pulls without needing to worry about implementation details, and so that the implementations can be optimized for certain operations (fairly straightforward). Data is forwarded inward toward the aggregating node in the mesh, with nodes along the way withholding their own updates until receiving from their outer relay partners. The group offers a prototype implementation of the TAG system, and demonstrates a few synthetic benchmarks of different epoch caching thresholds. TAG is also not a perfect solution, especially for query tasks requiring large amounts of RAM per mote. If a requested update requires an amount of RAM per mote that approaches or equals a mote’s capacity, then the network performance is no better than an unaltered mesh network where information is passed immediately. Furthermore, it may be that the act of aggregating instead of immediately passing causes some incoming pieces of information to be lost, as more central motes scramble to send their information out when incoming information that would go outside their cache is detected. This would also be the case for extremely active mesh networks, where high amounts of traffic or many queries are pushed per unit of time. TAG also may have problems for very inactive sensor networks. Consider again the example of a nature monitoring system with very infrequent updates. A caching system such as TAG would hold incoming pieces of information for relatively long periods of time depending on its epoch configuration; this may cause the data to itself be outdated upon arrival, defeating the entire purpose of the network query. It isn’t, of course, that these schemes are useless. Trickle is especially suited for very lightweight sensor networks, whose sensors’ onboard memory is close in magnitude to the size of a packet header. For limited hardware, Trickle functions fine. TAG is suitable for networks with reasonable data payloads per node, which falls to the implementer to ensure per their network. It isn’t likely that in most applications the amount of memory needed per payload would approach the size of a node’s onboard memory, so the above concerns about TAG are more edge cases to consider in the design of such mesh networks.From: muntasir.raihan SpamElide on behalf of muntasir raihan rahman [mrahman2 SpamElide] Sent: Thursday, March 17, 2011 10:05 AM To: Gupta, Indranil Subject: 525 review 03/17 Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks Summary: Trickle is an algorithm for wireless sensor networks for efficiently propagating and updating code updates. The basic idea is to use polite gossiping: i.e. talk only when there is new information. Dynamic gossip adjustment is used to improve the performance. The authors initially assume a loss-less, synchronized and single hop network to develop a base-line trickle algorithm. The assumptions are removed one at a time to make the algorithm more practical. For evaluation, the authors develop a purely algorithmic simulator, and two TOSSIM simulators using TinyOS motes. The algorithm works as follows: (1) Time is divided into T lenght intervals. (2) There is a counter c for each transmission in T. (3) Nodes transmit at a random time t in [0,T]. (4) If c < k, at time t, the node transmits meta-data, otherwise it remains silent. (5) If a node hears old meta-data, it transmits an update. (6) If a node hears new meta-data, it transmits its old meta-data to provoke another node to send updates. The authors first introduce a loss model to make the algorithm more practical. Even in the best-case, this can result in O(log n) message overhead. To avoid synchronization problems, the authors suggest listening on the interval [0,T/2], and choosing t from [T/2,T] only. The gossiping interval T is dynamically updated to account for more gossip when there is a new update, and less when there are no new updates in the network. For a multi-hop network, the hidden terminal problem kicks in and affects the effective density. However given the low network utilization, the algorithm scales as expected. The paper discussed the details of an implementation in Matte and simulations using TOSSIM. Pros: (1) Trickle inherits all the desirable properties of gossip protocols including low overhead and high reliability using probabilistic information dissemination. (2) Ensures logarithmic scaling in the face of loss, asynchronous environment and multiple hops. Cons: (1) Trickle does not consider energy efficiency, since there is no sleep period for the nodes. (2) Trickle cannot scale to dense networks. Future Works: (1) The paper proposes various ad-hoc optimizations to deal with practical issues in wireless sensor networks. A mathematical analysis of the performance of these optimizations would be interesting. Synopsis Diffusion for Robust Aggregation in Sensor Networks Summary: This paper deals with evaluating queries in sensor networks using in-network aggregation. The authors develop the concept of order and duplicate insensitive (ODI)-synopsis and use it in conjunction with multi-path routing to perform robust aggregation. Multi-path routing is better at dealing with failures in the underlying network compared to tree based aggregation (TAG), but runs the risk of duplicates and out of order delivery. This is overcome using ODI-synopsis. There are three types of synopsis functions: SG(), SF(), and SE(). The authors show a very simple test for ODI - correctness and prove that it exists when all possible synopsis combinations produce the same result as that of a canonical left deep tree. As it turns out, ODI - correctness also has an underlying semi-lattice structure which has practical consequences for using synopsis as implicit acknowledgments. The communication error of SD (synopsis diffusion) is avoided using good routing topologies. As a result the authors focus on approximation errors. They show that an existing approximation ratio analysis in a centralized model carries on in the distributed SD setting. The paper provides aggregation algorithms for a large number of problems including max, min, count, sum, uniform sampling, frequent items, range aggregates and so on. The algorithms are extensively evaluated using a TAG simulator and compared with existing approaches. Discussion Points: (1) Although ODI-correctness can be checked easily, it still incurs substantial computational overhead. In practice, such a complicated scheme might lose to simple ad-hoc policies for aggregation. (2) Some of the aggregation algorithms (e.g. for count, sum) are based heavily on existing data stream algorithms (e.g the FM algorithm). (3) Is it possible to utilize the semi-lattice structure of ODI-synopsis for other sensor network processing tasks? (4) One of the strong points of this paper is that it actually discovers some underlying structure of the problem and uses it to find elegant generalized solutions as opposed to quick and dirty systems solutions that we have seen in many earlier papers discussed in class. -- Muntasir From: lewis.tseng.taiwan.uiuc SpamElide on behalf of Lewis Tseng [ltseng3 SpamElide] Sent: Thursday, March 17, 2011 1:25 AM To: indy SpamElide Subject: 525 review 3/17 CS 525 - Review: 03/17 In-network processing TAG: A Tiny Aggregation service for ad-hoc sensor networks, S. Madden, et al, OSDI 2002 This paper proposed an integration of aggregation service for Ad-Hoc Sensor Network, called Tiny AGgregation (TAG). First, the paper argued that a generic and simple high-level programming abstraction similar to database query languages conducted over streaming data is essential for aggregation in wireless environment. Second, based on such SQL-like language, TAG performs aggregation intelligently in distributive manner. Moreover, the paper also presents several optimization techniques and efforts to improve fault-tolerance. For example, snooping in wireless network is utilized to reduce communication complexities and cache can be used to tolerate packet loss. The first contribution is an explicit examination of the usual types of aggregation queries and a proposal of taxonomy. The classifications of aggregation are based on four dimensions: state requirements, loss-tolerance, duplicate sensitivity, and monotonicity. Such taxonomy is important, because some optimization techniques are specific to only subset of classifications. Moreover, after understanding and studying taxonomy more rigorously, the process of data collecting might be improved. The second contribution is the integration of aggregation techniques and TAG SQL-like language. Finally, the result of experiment on prototype implementation seems to be encouraging, which somewhat gives public confidence in in-network aggregation. Comments/questions/critiques: The paper argued that with properly implementation of in-network aggregation, communication complexity, power consumption, and latency can be reduced. While I understand that the cause of the first two is because of lower number of message transmissions, I do not quite understand why latency can be shortened. TAG requires a parent to wait for messages from all children in every epoch. Wouldn’t this practice indeed increase latency? Especially, when there are some nodes are significantly slower than others. Worse, what if some crash failures happens? Can TAG be easily integrated with failure detection algorithms? TAG adopts an end-to-end approach, which is different from the data-centric approach adopted by directed diffusion. The paper argued that it is because mainly for overcoming the network loss on aggregation. However, it is interesting to see how well this end-to-end scheme scale, since in directed diffusion paper, they argued that data-centric approach is much more scalable, which should be the usual case and one important concern in sensor network. One other design related to scalability issue is the central catalog processor. This might be the bottleneck. Let along the question whether such processor is realistic in real deployment of sensor network in a wide filed. TAG does not implement its own Ad-Hoc Routing algorithm. One the plus side, TAG can run on top of any algorithms suitable for the deployed environment. However, a system integrated with routing algorithm might have several advantages. It might be interesting to examine the tradeoff. Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks, P. Levis et al, NSDI 2004 This paper first identified three main challenges of code propagation: when and how often to propagate code for how long. Then the paper proposed a scheme called Trickle that has three properties: low maintenance, rapid propagation and scalability. Trickle is based on one very simple primitive: polite gossip: “every once in a while, transmit unless you’ve heard a few other transmissions.” While the core idea is simple, the paper still had some essential contributions. First, the paper built a simulator TOSSIM based on TinyOS that are suitable for experiments in sensor network. Second, the paper had designed three different experimental environments to intensively test Trickle: abstract simulation, TOSSIM and TinyOS motes. Based on these experiments, the paper provided some insights on code propagation. For example, the paper suggested that O(logn) to be the desired scalability, and polite gossip somewhat achieves fair load distribution. Third, the extremely simple policy can be adapted to other fields. For example, polite gossip might be useful in streaming peer-to-peer services where many servers exist. Comments/questions/critiques: While the experiment results are promising, I would like to see more theoretical analysis. In particular, there are many papers on wireless network capacity with existence of channel conflicts. However, the paper just used simulations to back up their claims, such as Trickle’s scalability in dense network, which does not seem very convincing to me. Having the “listen-only” period to solve synchronization problem is simple and clever, but as a result, the performance is only order optimal. Is there any way to decrease the constant term? In sensor network, churn rate and failure rate are common issues. I am surprised that the paper did not discuss about it, since gossip should be relatively more reliable to these two issues due to redundancy of information. Would the “polite” feature somehow affect this fault-tolerance ability? How to select “good” parameters is unclear. How to adapt them smartly? Would the adjustment overshoot easily without deliberate policy? From: Shen LI [geminialex007 SpamElide] Sent: Thursday, March 17, 2011 1:11 AM To: Gupta, Indranil Subject: 525 review 03/17 Name: Shen Li Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks This paper proposes an idea for wireless sensor networks to propagate new code across the whole network. Their objective is to save energy during propagation while shorten the during of this phase. The basic idea is "polite gossip", which means try not to repeat what other people have just said. The transmission is triggered by two kinds of event, heard of an old version of code or have just received a new version of code. They also point out that the the basic design is based on synchronized networks while synchronization will cost a lot of energy. So they provide a technique to loose the condition, which is, during every interval every node has a listen only period set to t/2. In this way, each transmission will at least silent its neighbours for t/2. Pros: 1. Philip Levis as the developer of TinyOS knows the sensor network very well. Many of his approaches share the same philosophy, which is, simple but efficient. This paper also followed this footstep. Cons: 1. In their TOSSIM simulation, they assume that the link error rate is constant. However it is not true in real cases. Wireless communications are highly influenced by its surrounding environments. The change of environment may lead to link quality dynamics. 2. Their code update algorithm is actually transmission driven. During the propagation, the updates are transmitted when one node heard of an out-of-date version or received a new version. As they mentioned in the paper, the propagation during is very important since the longer time spent in this phase, the more energy will be wasted. I can understand that they design Trickle in this way to save energy. But how does it compare to an more aggressive algorithm which is able to shorten the length of propagation phase while itself cost more energy. TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks This paper proposes to aggregate data messages in wireless sensor network which helps to save energy. Their basic idea is applying a TDMA like approach in the tree based collection protocols. There are two phases in TAG: distribution phase and collection phase. In the first phase, queries are pushed down into the network. In the second phase, the parent node assign specific intervals for its children nodes to report their information. Then, the parent node aggregate the information it received, and send the aggregated packets to higher level nodes. They also provide a SQL like language that eases the data collection operation for wireless sensor network users. Pros: 1. I am not sure whether this is the first paper that talks about the aggregation policies in wireless sensor network. If it is, this paper actually initiated a huge new branch of WSN researches. Cons: 1. They claim that TAG is able to help tree based collection protocols. I am curious about how good TAG can do in non-tree protocols, such as backpressure collection protocol. 2. Their TDMA like approach calls for fair accurate synchronization, while synchronising the whole network can cost extra energy. It is not clear whether the benefit brought by TAG can overcome the cost. From: Tengfei Mu [tengfeimu SpamElide] Sent: Thursday, March 17, 2011 12:10 AM To: Gupta, Indranil Subject: 525 review 03/17 1. Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks This paper introduces Trickle, a novel mechanism for code propagation and maintenance over an entire network. By deploying ‘polite gossip’ policy which broadcasts update messages when there are indentified inconsistencies in nodes’ metadata, Trickle successfully minimizes the number of update messages flowing through the network. The node will still send out periodic updates if it does not receive the incoming update messages between a certain period of time. If it receives, then the node compares its received update with its current state, then updates its own node and broadcast a new update message with the up-to-date node metadata if it finds inconsistence. Overall, Trickle achieves scalability, fast update propagation as well as low maintenance overhead. Pros: 1. The fast update propagation, scalability and low maintenance overhead 2. Trickle can be used to improve the TinyOS network Cons: 1. The authors does not consider much about the nodes failure cases. 2. TAG: a tiny aggregation service for ad-hoc sensor networks This paper introduces a novel Tiny Aggregation (TAG) service that works in low power, distributed and wireless environments. Especially TAG service could achieve order of magnitude reduction in bandwidth consumption over approaches where data is aggregated and processed centrally. TAG algorithm is based on a routing tree ad hoc network structure that is continuously being updated and monitored for joining and leaving sensors. It could process data as they are transmitting within the sensor network, and it will discard the unnecessary information and aggregate certain data into compact records. Thus, the messages flowing within the wireless network could only be recognized and processed by the nodes with symmetric links between them, and the packets received from the other sensors in this range will be ignored. Pro: 1. TAG service could achieve order of magnitude reduction in bandwidth consumption compared to centralized approaches. 2. TAG support node awake/asleep modes. Con: 1. The authors does not consider the failure cased on the communication network. From: iitb.ankit SpamElide on behalf of Ankit Singla [singla2 SpamElide] Sent: Thursday, March 17, 2011 12:05 AM To: Gupta, Indranil Subject: 525 review 03/17 1. Synopsis Diffusion ------------------------------ Summary: The core problem the paper addresses is the desire to use multipath routing of data for aggregation while simultaneously avoiding duplicates in the aggregation. The utility of multipath routing is in its resilience to failures, which is why prior methods like building spanning trees do not work as well. For this purpose, they propose the use of "order and duplicate insensitive synopses", which are small-sized digests of the partial results seen at any sensor node. A query is first distributed through the network and a corresponding topology is created for the aggregation of the results. Each node computes its local synopsis and on receipt of other synopses, updates its synopsis. The query node finally translates the synopsis to a query-answer. The key element in all this working properly is the order and duplication insensitivity of the synopses. The topology they use is fairly intuitive, robust and power-efficient - concentric rings based on hop-distance from the querying node. They give a simple example of a 'count' function being evaluated using their scheme. In this example the properties of the specific order-functions are very evident. Comments: The technique they propose is fairly general -- in fact, in our work on compact routing over general networks, we proposed that Synopsis Diffusion be used to estimate the number of nodes in the network (which is an often ignored but non-trivial problem.) I think their observation that the synopses could also be used effectively as implicit acknowledgements is clever. 2. Trickle -------------- Summary: The paper tackles the problem of propagating new code to sensor motes efficiently. This is done using a 'polite gossip' protocol, which is based on reacting to the metadata-messages a node sees. On receipt of identical metadata, a mote stays quiet; on receiving old metadata, a mote starts the gossip to make sure all nodes are up to date. The scheme is fairly simple - a node maintains an idea of how new its metadata is by counting the number of identical metadata it receives. If this number exceeds a threshold, then the node assumes its metadata is up to date and well known, so it doesn't propagate it. This is done periodically. In addition, there's an element of randomness added to the time each node decides to transmit, to ensure low probability of interference. Comments: Motes always being on is a fairly strong assumption for such long-lived motes which see multiple reprogamming events over their lifetime. On the whole, I find their technique very similar to epidemic algorithms. It is simple and ensures spread of updates efficiently. How do people tackle the gaping security problem here? – Any arbitrary person should not be able to reprogram the motes! It seems like reprogrammable motes face other (more significant?) challenges. Ankit -------------------------------------------------------------------- Ankit Singla Graduate Student, Computer Science University of Illinois at Urbana-Champaign (UIUC) http://www.cs.illinois.edu/homes/singla2/ From: wzhou10 SpamElide Sent: Wednesday, March 16, 2011 11:50 PM To: Gupta, Indranil Subject: CS525 Review 03/17 Review on “Synopsis diffusion for robust aggregation in sensor networks” Core idea This paper presents a new framework, Synopsis Diffusion (SD), for in- network aggregation in sensor networks. It decouples aggregation and routing, and optimizes the former one independently by using Order- and Duplicate- Insensitive (ODI) synopses. There are three functions: synopsis generation (SG), synopsis fusion (SF), and synopsis evaluation (SE). SG converts sensor reading into a synopsis, e.g., bit-vector. SF combines multiple synopses into one. Finally, SE converts synopsis into result. Like TAG, SD has two phases: 1) distribution phase, when an aggregation query is flooded and an aggregation topology is generated, 2) aggregation phase, the reading values at sensors are aggregated using above mentioned functions and routed to the querying node. Pros 1. SD avoids double-counting and is topology independent, so robust multi- path routing can be used. 2. The choice on synopsis functions is flexible, as long as they satisfy the necessary and sufficient conditions for ODI correctness. 3. Implicit acknowledgement can be used to estimate link quality and adapt aggregation topology dynamically. 4. SD exploits the broadcast nature of wireless medium. Cons There’s a tradeoff between accuracy and message size. So if a high level accuracy is required, synopses must be large, and thus the overhead and complexity at each sensor are high. However, sensors are usually assumed less capable to hand high complexity and energy limited. Review on “Trickle: A Self Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks” Wireless sensor networks usually consist of large number of small resouce- constrained nodes, and operate for long durations, so code update and propagation over the networks needs to be quickly and efficiently. Trickle is proposed as an algorithm for propagating and maintaining code updates in wireless sensor networks, aiming to reduce number of broadcasts needed for code update. The two design goals are rapid propagation and low maintenance overhead. It borrows the idea of polite-gossip policy: if a node hears gossip with metadata identical to its own, it keeps quiet; otherwise, if it hears an old gossip, it broadcasts a code update. Moreover, Tickle utilizes transmission suppression to address short-listen problem. Pros 1. Trickle borrows epidemic/gossip techniques to rapidly propagate code in wireless sensor networks with less number of broadcasts, and thus saving more resources, e.g. energy, which is essential to sensor motes. 2. Trickle uses randomized time value t to balance load. 3. The algorithm is simple, intuitive. It’s robust to loss and disconnection and requires very little state. 4. Communication overhead scales well, logarithmically with cell size, so it’s able to be used effectively in very dense networks. Cons 1. Nodes are assumed always on. 2. It might be hard for a node to tell whether or not a packet is old-version or simply delayed in the network. If it’s the later case, there will be unnecessary updates. 3. There’s no detailed discussion about the sensitivity of Trickle to the choice on time interval value threshold T. Thanks. Wenxuan From: Chi-Yao Hong [cyhong1128 SpamElide] Sent: Wednesday, March 16, 2011 9:28 PM To: Gupta, Indranil Subject: 525 review 03/17 ---- TAG: a Tiny Aggregation Service for Ad-Hoc Sensor Networks, OSDI’02 ---- With the increasing popularity of ad-hoc sensor networks, more and more people are building the sensor networks using small embedded systems. These sensor nodes usually have low computational power and very limited battery power. Monitoring is an important task usually performed by sensor networks. To collect the sensed information, sensor nodes need to collaboratively aggregate the information. However, the overall amount of the collected information could be large, and transferring the information over wireless media would consume considerable energy. Therefore, in-network data aggregation is usually preferred to reduce the power consumption. However, the current practice of building the desired aggregation functions is to program the device using low-level language like C. To simplify this task, the authors proposed TAG, an ad-hoc sensor network service that provides high-level declarative query interfaces for data aggregation. In particular, TAG allows network administrator to define the aggregation queries with a simple SQL-like declarative language. Pros: 1. It is smart to use snooping in sensor networks to improve the transmission efficiency (e.g., bits/Joule). Many researchers are working along the same track in 2004-2006 where they generalize this idea and called it “opportunistic network.” 2. Sensor is an error-phone environment where communications and node failures are frequently happen. To deal with errors, the authors perform measurement study and propose optimizations (caching and redundancy) which seem to be promising and comprehensive. Cons: 1. Many sensor network optimization designs consider battery characteristics. It is not hard to obtain the battery information, and this could be important information for the system designing. For example, if a node is going to exhaust its power, then we should avoid using the node to perform complicated operations like caching. 2. Authors claimed that verifying data aggregation is one of the main contributions, which I don’t really agree. It had been shown earlier that data aggregation is useful for extending sensor network lifespan. ---- Synopsis diffusion for robust aggregation in sensor networks, ACM TOSN’08 ---- This paper focused on improving the robustness of data aggregation in sensor networks, while preserving the energy efficiency. Instead of using tree, the authors propose to use multi-ring to improve the topology connectivity. Unlike tree, in multi-ring each node could have more than one parent. Therefore, the proposed topology is expected to have better fault tolerance than tree. However, data traverse multiple path might be double-counted in the higher level, which could corrupt the aggregated result. One simple way to fix this is to embed the complete host information in the partial aggregated results. Unfortunately, this requires considerable space complexity and therefore is prohibited in sensor networks. To deal with this issue, the author uses an exponential hash function to approximate the information about data hosts. This algorithm is adapted by counting distinct elements in a multiset. It can be shown that the average derived by this algorithm is close to the actual mean. Pros: 1. The considered performance metrics in the simulation are sound and complete. Cons: 1. Only averaging has provable performance. For other interesting operations like median, deviation and x-percentile, there is not evaluation to validate that the proposed scheme would work. 2. Ideas are not very novel. The ring structure and exponential hash function had been proposed earlier. 3. They mentioned Gossiping is not energy efficient, which I don’t agree. By changing the parameters in Gossiping, the total amount of data sent could change significantly. Why not just using gossiping and the proposed duplicated-sensitive aggregation? -- Chi-Yao Hong PhD Student, Computer Science University of Illinois at Urbana-Champaign http://hong78.projects.cs.illinois.edu/