From eyh5@ee.cornell.edu Mon Nov 5 14:03:04 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA5J33R24551 for ; Mon, 5 Nov 2001 14:03:03 -0500 (EST) Received: from photon.ece.cornell.edu (photon.ece.cornell.edu [128.84.81.138]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id fA5J2LJ07423 for ; Mon, 5 Nov 2001 14:02:21 -0500 Date: Mon, 5 Nov 2001 14:02:34 -0500 (EST) From: Edward Hua X-X-Sender: To: Subject: 615 Paper # 35 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Building Efficient Wireless Sensor Networks with Low-Level Naming John Heidemann, Fabio Silva, Chalermek Intanagonwiwat, Ramesh Govindan Deborah Estrin, Deepak Ganespan This paper proposes an attribute-based low-level naming scheme to be used in sensor networks. This type of naming scheme is different from more traditional naming methods in that the names of nodes are external to the network topology but are related to the particular application, which is running on them. That is, the naming of the nodes belongs to a class of attribute-based schemes, the attributes being data type, environmental characteristics, geographic location, etc. This approach eliminates the overhead associated with name-binding resolution, and facilitates in-network, application-specific data processing. To implement this naming scheme, the architecture it requires has three components: directed diffusion, matching rules, and filters. Direct diffusion aims to establish efficient multi-way communication between one or more sources (nodes that disseminate the required information in a sensor network) to the sink (the recipient of this information). Matching rules are used to interpret the actions taken by the attribute-tuples (attribute-value-operation). Filters in the sensory nodes allow application-specific code to run in the network and assist diffusion and processing. As the name suggests, a filter registers what kind of data it handles through matching,it is invoked everytime the matched data enters the node. One of its usages is its ability to suppress multiple copies of the same information from other sensors. The authors detail some applications techniques that may be applied using the proposed scheme in a sensor network. One of them is the in-network data aggregation. In-network data aggregation allows multiple sensory nodes in the network to aggregate the individual data streams into one before transmitting back to the sink. Its advantage is the conservation of power consumption by the nodes of the network, whereas its trade-off is the induced latency due to aggregation. Data aggregation using the proposed attribute-based naming is said to be opportunistic in that sensor selection and tasking is achieved by naming nodes using geographic attributes, and that filters in the intermediate sensors can cache the relevant data when its propagated back to the sink. The benefits are obvious. Filters invoked and activated may inject application-specific code into the network, and they remain inactive, hence, conserving power, until triggered by relevant data; also, filters incur no network costs to interact with directory or mapping services. The attribute-based naming scheme in a sensor network finds its strength in its flexibility of associating underlying data querying from the application that runs atop. The use of filters can be used to control the amount and type of information that is most desired by the sink. The in-network aggregation of data conserves power consumption, as individual sensors can trnasmit their respective data streams to a member among them, which presumably is closer to them than the sink. However, in implementing this technique, care must be taken to ensure that the aggregated data sent back to the sink is still fresh enough. That is, the induced latency does not exceed the required data update interval as stipulated by the sink. Therefore, in actual implementation, this trade-off between the freshness of the information and the amount of aggregated data must be carefully studied. From viran@csl.cornell.edu Mon Nov 5 22:54:31 2001 Return-Path: Received: from moore.csl.cornell.edu (moore.csl.cornell.edu [132.236.71.83]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA63sTR02727 for ; Mon, 5 Nov 2001 22:54:29 -0500 (EST) Received: from localhost (viran@localhost) by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id fA63sOM24951 for ; Mon, 5 Nov 2001 22:54:24 -0500 (EST) (envelope-from viran@moore.csl.cornell.edu) X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs Date: Mon, 5 Nov 2001 22:54:24 -0500 (EST) From: "Virantha N. Ekanayake" To: Subject: 615 Paper 35 Message-ID: <20011105225336.H23282-100000@moore.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents a method of low-level naming of nodes based on attributes such as sensor types or geographic location. Thus the naming can be application dependent, and naming indirection is reduced, leading to better performance on low bandwidth networks. The method presented works by diffusing a request for data (using rule-based system of attributes) throughout the network. The diffusion sets up gradients that are used by nodes that match the rules in the request to send data back. The data can be cached at intermediate nodes for data aggregation or nested queries, and filters applied to the data at intermediate nodes. THe downsides to such a scheme (without a centralized directory) are that nodes have to know the attributes and sensor types available apriori. In addition, data requests need to be flooded throughout the network, thereby eliminating valuable bandwidth. It would have been interesting to see a comparison with directory based naming services to compare the throughput, latency and power consumption of the network. They also state that nodes do not need globally unique identifiers, but just need to distinguish their neighbours -- I fail to see how that does not require unique identifiers, especially if the sensor nodes are not static. Diffusion based discovery also does not work well with asymmetric links, which is something that they need to explore in future. In addition, there wasn't much justification for the benefits of data aggregation (other than just simple duplicate packet removal), and more studies need to be done in terms of ensuring correctness, and bounding the latency. Security is probably an issue as well, since a sensor node could capture a route by re-inforcing it's links and filtering out packets arbitrarily -- This would be fatal for a security sensor network. From gupta@CS.Cornell.EDU Tue Nov 6 11:00:07 2001 Return-Path: Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6G05R24344 for ; Tue, 6 Nov 2001 11:00:05 -0500 (EST) From: Indranil Gupta Received: (from gupta@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id fA6G05a19639 for egs@cs.cornell.edu; Tue, 6 Nov 2001 11:00:05 -0500 (EST) Message-Id: <200111061600.fA6G05a19639@zinger.cs.cornell.edu> Subject: 615 PAPER 35 To: egs@CS.Cornell.EDU Date: Tue, 6 Nov 2001 11:00:05 -0500 (EST) X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Building efficient wireless sensor networks with low-level naming, Heidemann, Silva, Intanagonwiwat, Govindan, Estrin, Ganesan. Reviewer: Indranil Gupta This paper pitches for an application-specific and geographic naming scheme for sensor networks. The authors argue that unlike in the Internet, sensor networks are characterized by low bandwidth to CPU speed ratios. As a result, reducing the amount of communication is paramount - the data-centric naming scheme helps in this direction by allowing data processing within the network. Towards this goal, the authors describe a) a directed diffusion protocol for data flow towards an interested node - 'good' paths are positively reinforced and 'bad' paths are negatively reinforced, and b) an in-network data aggregation protocol (using data attributes) and batching multiple related ('nested') queries into the same packet, in order to reduce loss rates by up to 30%. Comments: - Several ad-hoc routing protocols have been proposed in literature, and it is not clear what added benefits a protocol such as directed diffusion has over these other routing protocols. Data assimilation and aggregation is effectively a converge-cast problem, and any of the ad-hoc multicast routing protocols, turned upside down, could be used for this purpose. A comparison among these protocols would be very interesting work. - On the topic of data aggregation, the algorithms in the paper are mostly 'best-effort', focusing on a reduction in in-network traffic rather than better (close to 100% reliability) in the aggregate estimate. Measuring activity in earthquakes, on ocean-beds, etc., relies on the _accuracy_ of the aggregate data obtained. While the authors' algorithms never achieve over 80% reliability, there has been work here at Cornell [Gupta et al, DSN 2001] that focuses on algorithms for such applications. These algorithms provide probabilistic accuracy in the aggregate estimate, and reduce the resulting communication. From ramasv@CS.Cornell.EDU Tue Nov 6 11:09:35 2001 Return-Path: Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6G9YR25770 for ; Tue, 6 Nov 2001 11:09:34 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Subject: cs615 PAPER 35 Date: Tue, 6 Nov 2001 11:09:34 -0500 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F28B@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 35 Thread-Index: AcFm3WzCczYXbKmbR02jzs+FLFhgzw== From: "Venu Ramasubramanian" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id fA6G9YR25770 Building Efficient Wireless Sensor Networks with Low Level Naming. This paper describes the design and implementation of an architecure for data aggregation and data transfer in sensor networks. Low level names based on attribute-value pairs are used to represent and route data between the sources and the sinks. Data aggregation is possible for efficiency reaons by introducing filter-code at appropriate nodes in the network. A general algorithm to match requests with actual data allows the architecture to allow the name space to vary based on the application. There are three important components to this architecture. The first and most important is a routing scheme called directed diffusion. Directed diffusion scheme builds routes between sensor sources (that detect events) and sinks that request for the event to be reported. A distributed algorithm is then applied to reinforce a single route. AV based naming allows the routing protocol to prevent multiple reports on the same event to the sink. Since each node has access to the data by its attributes multicast routing becomes a part of unicast routing. In general directed diffusion looks very efficient for applications involving event detections and periodic event updates to specific sinks. The second component of the architecture performs matches between the AV pairs in the request and the AV pairs in the data. This involves a simple algorithm that recurses through the AV pairs in the query to perform matching. Sophisticated SQL queries may not be handled and the algorithm is not optimized for performance. Since every data generated has a name and possibly with several AV pairs, this forms a crucial part of the architecture that needs further polishing. The componet involves placing in-processor code components that can be used to aggregate data or filter data. I believe data aggregation is an important component of sensor networks so ability to place filters becomes very important to sensor network applications. This paper discusses a few filters that could improve efficiency of the directed diffusion protocol. However the paper does not discuss dynamic creation and placement of new filters by the applicattion. This could greatly improve the flexibility of the system. From c.tavoularis@utoronto.ca Tue Nov 6 11:16:23 2001 Return-Path: Received: from bureau6.utcc.utoronto.ca (bureau6.utcc.utoronto.ca [128.100.132.16]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6GGLR26699 for ; Tue, 6 Nov 2001 11:16:21 -0500 (EST) Received: from webmail4.ns.utoronto.ca ([128.100.132.34] EHLO webmail4.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 49609]) by bureau6.utcc.utoronto.ca with ESMTP id <238660-7366>; Tue, 6 Nov 2001 11:16:13 -0500 Received: by webmail4.ns.utoronto.ca id <164259-210>; Tue, 6 Nov 2001 11:16:02 -0500 To: COM S 615 Subject: 615 PAPER 35 Message-ID: <1005063360.3be80cc094f6a@webmail.utoronto.ca> Date: Tue, 06 Nov 2001 11:16:00 -0500 (EST) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: IMP/PHP IMAP webmail program 2.2.3 This paper introduces a topology independent naming system for low-level communication. It merges naming and routing, which use application level information to form meaningful attribute-value pairs. This technique provides many advantages for wireless sensor networks by reducing communication overhead and overall energy consumption. Attributes are based on pre-defined attributes and geography. Using these attributes for naming simplifies sensor network applications such as application-related caching, aggregation, and collaborative signal processing. A sink node will use direct diffusion to distribute an interest consisting of attributes throughout the network. Each node that receives the interest stores and interprets the information before forwarding it. This is done for routing purposes to prevent loops, but the node may also use the information. A gradient is set up along the forwarding nodes. When a source node is found that matches the interest, it returns an initial message as exploratory along the matching gradients. Subsequent communication from source to sink follows a single reinforced path. Attribute-matching at each sensor can be either complete (two way logical) or one-way, and is proven to be CPU efficient. Data- specific filters can be added to each sensor node to interpret received data and allow application-specific control over data flowing in the network. Filters are responsible for tasks such as caching and aggregation. This unique naming system is built on top of hop-by-hop communications and intended for sensor networks. I think the routing efficiency can be improved, but is not the main contribution of this paper, and can be replaced. The proposed naming allows the network to work for the application, which reduces back and forth communication and improves overall bandwidth efficiency. I don’t think they consider node mobility and changing topology, which could destroy the effectiveness of their scheme. From ranveer@CS.Cornell.EDU Tue Nov 6 11:25:08 2001 Return-Path: Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6GP6R27951 for ; Tue, 6 Nov 2001 11:25:06 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Subject: 615 PAPER 35 Date: Tue, 6 Nov 2001 11:25:02 -0500 Message-ID: <706871B20764CD449DB0E8E3D81C4D430232E6A7@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 35 Thread-Index: AcFm35XzrNwfY/f6S3K1wZX0Uwq9eg== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id fA6GP6R27951 Building Efficient Wireless Networks with Low level Naming This work build on the previous work on Directed Diffusion in MobiCom 2000. It is proposed to have attribute-based names for sensor networks as opposed to topology-based IP naming over the internet. Advantage is taken of the fact that communication over sensor networks is much more power intensive than computation. The idea is to have attribute based names coupled with in network processing and using directed diffusion, which provides an efficient mechanism for data dissemination and aggregation over sensor networks. The advantage of this scheme is its simplicity in implementation. It is also effective as a means for power conservation. No continuous beaconing is used, excessive and redundant packets are eliminated and only reinforced paths are used. Overall this scheme is very efficient for data gathering over sensor networks. However, this scheme has its own disadvantages. The obvious questions one could ask are: 1) how much extra time does this scheme take for data aggregation. In network processing would mean latency in data delivery. What is this latency for large networks? 2) How does this scheme scale for huge networks? Besides the time taken, how does the attribute-based naming scheme handle addition and deletion of attributes over such networks? 3) Currently, their scheme has no way of handling unidirectional links. In addition no beaconing is used. They also do not use a standard MAC. Broadcasts are also not reliable. A comprehensive architecture for such a system would require support for these features. From teifel@csl.cornell.edu Tue Nov 6 11:30:21 2001 Return-Path: Received: from disney.csl.cornell.edu (disney.csl.cornell.edu [132.236.71.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6GUJR28741 for ; Tue, 6 Nov 2001 11:30:19 -0500 (EST) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id fA6GUEV45858 for ; Tue, 6 Nov 2001 11:30:14 -0500 (EST) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Tue, 6 Nov 2001 11:30:14 -0500 (EST) From: "John R. Teifel" To: Subject: 615 PAPER 35 Message-ID: <20011106112943.G14987-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII BEWSNwLLN: This paper describes a software architecture that supports named data and in-network processing in sensor networks. In-network techniques such as aggregation and nested queries can dramatically improve network performance. In low-level naming schemes such as this, low-level communication is based on attributes relevant to applications, rather than on network topology. The architecture is composed of directed diffusion, matching rules, and filters. Directed diffusion is a data-centric communication mechanism that allows nodes to efficiently transfer information and requires that every sensor node be task-aware and actively process information from other sensors. Filters can operate to process and reduce sensor data. Granted they implemented this system on three different platforms, I was kind of surprised by the limited amount of experimental data that they provided--perhaps I think due to the problems that they mention with actual wireless implementations. Overall it was an interesting application architecture model for sensor networks, but I think it is too preliminary to become excited about it. From daehyun@csl.cornell.edu Tue Nov 6 11:48:11 2001 Return-Path: Received: from wilkes.csl.cornell.edu (wilkes.csl.cornell.edu [132.236.71.69]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6GmAR01194 for ; Tue, 6 Nov 2001 11:48:10 -0500 (EST) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id LAA41268 for egs@cs.cornell.edu; Tue, 6 Nov 2001 11:48:05 -0500 (EST) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200111061648.LAA41268@wilkes.csl.cornell.edu> Subject: 615 PAPER 35 To: egs@CS.Cornell.EDU Date: Tue, 6 Nov 2001 11:48:05 -0500 (EST) X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit This paper presented a network naming method which is designed for wireless sensor network where resources such as bandwidth and energy is limited. Key idea of the low-level naming is that low level communication does not rely on network topological location. Low level communication is based on names that are external to the network topology and relevant to the application. Main benefit of the low-level naming is that it can reduce naming overhead. Typically, multiple level of naming is used in the conventional networks - topological low level naming and location independent high level naming. And naming service provides mapping service between them. But, in low-level naming, there is no such a overhead. (Attribute-Based Naming) Another benefit is that it enables application specific processing inside the network. In low level naming, packets can be identified by its name, so data can be processed during transmission as in active networks. this allows data reduction where data is generated. (In-network Processing) These benefits are good for sensor networks where computation power is enough, but network bandwidth is dear. The proposed network is composed of three components - Directed Diffusion, Matching Rules and Filters. Directed diffusion is a communication mechanism which establish n-way routes between sources and sinks. Each intermediate node does not simply forward packets, but interpret and process them base on the contents. Matching rules identify the messages - attribute-value-operation tuples - and determine if they arrived at the destinations or in-network processing is required. Filters are application specific codes which provide in-network processing. In my opinion, the idea is similar to Active Networks in that it processes packets inside the network. But the proposed scheme is different in that it uses application specific low level naming, where Active Networks are based on conventional multiple naming. I think this low level naming is very nice for sensor networks, though it seems to have limitation for more general networks. From avneesh@csl.cornell.edu Tue Nov 6 11:52:16 2001 Return-Path: Received: from capricorn.ds.csl.cornell.edu (capricorn.csl.cornell.edu [132.236.71.92]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6GqER01860 for ; Tue, 6 Nov 2001 11:52:15 -0500 (EST) Subject: 615 Paper 35 Date: Tue, 6 Nov 2001 11:54:08 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Message-ID: <97C142C1212ED545B0023A177F5349C40A09BC@capricorn.ds.csl.cornell.edu> X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 Paper 35 Thread-Index: AcFm46cGFNdvFdVPRmSI4jrCEk/QMw== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id fA6GqER01860 Building Efficient Wireless Sensor Networks with low level naming Summary/Critique: This paper discusses the development and deployment of an attribute based naming system, with an 'external frame of reference', i.e. pre-defined attributes (which depend upon the sensor type), and the geography. Naming of this kind reduces communication overheads as faced with traditional resolution of name bindings and also allows application specific data processing within the network. The ideas build upon previous naming schemes based on attributes, however the research is visibly offsetted from these schemes, due to the lower bandwidth factor of sensor networks. The main idea is to use the technique of directed diffusion, where the data is represented as attribute-value-operation tuples. With the help of matching rules and intermediate filters within the network, the amount of data transmitted from node to node as well as the overall traffic can be regulated. The terminology used is as follows: a. Sink: This is the requestor of data or information. Hence it is the destination of data. b. Source: Multiple sources provide the data as required by the sink. Directed diffusion works on the principle that each node is task aware, and sets up a gradient towards each neighbor, which is indicative of the direction of data flow and the status of the demand. Based upon gradients, a node can establish 'preferred neighbors' for information flow. Caching is used as an optimization. The first message however (exploratory message), is sent to all neighbors, and the gradient is built gradually as information flows towards the node. Directed diffusion is data-centric, allows neighbor-neighbor communication and does not require nodes to have globally unique identifiers, all of which are important factors in a sensor network, since this removes the above mentioned naming overhead. The basic diffusion APIs are based on a 'publish-subscribe' approach. An interesting point was the development of a micro-diffusion interface, which is optimal for lower capacity devices. In order to further reduce the amount of traffic returned to the sink, the authors suggest techniques of in network aggregation which includes suppression of duplicates and aggregation of data from multiple sources; as well as using nested queries, which further promote in network processing, instead of end to end data processing. In the simulations, the authors evaluate the performance of these techniques and notice that although aggregation is alleviates traffic, it also incurs higher latency which is largely dependent on the aggregation algorithm. By reducing the number of attributes in an attribute set, the runtime costs of matching are also reduced. An interesting observation was that diffusion does not work well with asymmetric links. Hence the idea outlined is to utilize multiple data paths to gain robustness. I think that the paper was quite well written, although I feel that the simulation study could have been a bit more comprehensive. There are some issues that have not really been dealt with: a. Security: how do you ensure that the data that you have received has not been corrupted/replaced by a malicious node. This is actually tied to the issue that how nodes are named in the first place, and how a node joins the 'network'. b. Mobility: Do the proposed gradient and aggregation schemes work when the nodes move, or do gradients have to recalculated again? This actually implies that we may need to send exploratory messages every time the node moves, which increases the control traffic in the network. From papadp@ece.cornell.edu Tue Nov 6 12:15:19 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6HFIR05339 for ; Tue, 6 Nov 2001 12:15:18 -0500 (EST) Received: from kiki.ece.cornell.edu (kiki.ece.cornell.edu [128.84.83.13]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id fA6HEVJ02748; Tue, 6 Nov 2001 12:14:31 -0500 Date: Tue, 6 Nov 2001 12:18:23 -0500 (EST) From: "Panagiotis (Panos) Papadimitratos" To: Emin Gun Sirer cc: papadp@ece.cornell.edu Subject: 615 PAPER 35 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of: "Building Efficient Wireless Sensor Networks with Low-Level Naming," by J.Heidemann et al Panagiotis Papadimtratos papadp@ece.cornell.edu The proposed scheme tagrets a specific instance of ad hoc networking, in the sense that it takes into consideration the pertinent parameters (low bandwidth, high communication cost, relatively cheap computation), and, moreover, is application-centric (collection of data from a deployed set of sensors). The basic elements of this work is the use of a low-level, attribute-based naming scheme, the employment of a data-centric protocol for the dissemination of queries and the respective collection of replies, and the use of mechanisms such as attribute matching and data filtering that enhance its efficiency. Nonetheless, these tools lack sophistication, thanks to the context limitations. The proposed naming scheme avoids the overhead and limitations of any other directory-service based solution, since no indirections, name resolution queries, and additional resource location protocols are required. On the other hand, it lacks the flexibility of generic combinations of addressing/naming schemes, something justified by the assumed application context. The in-network processing techniques (in-network aggregation, nested queries, filtering etc) are also well-placed, but still tied closely to the application semantics. It would be more interesting to investigate whether diffusion can achieve the stated goals (efficiency, responsiveness, etc) in the absence of such strong semantics, i.e., in a context where it would be closer to general-purpose manet routing protocols. From andre@CS.Cornell.EDU Tue Nov 6 12:41:59 2001 Return-Path: Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6HfvR08716; Tue, 6 Nov 2001 12:41:57 -0500 (EST) Received: from khaffy (d7b148.dialup.cornell.edu [128.253.157.148]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA14765; Tue, 6 Nov 2001 12:41:54 -0500 (EST) Received: from andre by khaffy with local (Exim 3.31 #1 (Debian)) id 1614e1-0000HI-00; Tue, 06 Nov 2001 12:43:53 +0100 Date: Tue, 6 Nov 2001 12:43:53 +0100 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: egs@CS.Cornell.EDU Cc: andre@CS.Cornell.EDU Subject: 615 PAPER 35 Message-ID: <20011106124353.A1062@khaffy> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.3.20i Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= Building Efficient Wireless Sensor Networks with Low Level Naming The goal of this paper is towards sensor networks with low bandwith. The idea is not to use a routing scheme using IP or other unique identifyer. Rather, forward data depending on their content. Low level comunications is based on names that are relevant to the application (no need for binding resolution). There are 3 different parts: - Direct Diffusion: messages are propagated to the neighbours. A gradient is set up to know in which direction the packets should go (they didn't not enter in the details. I assume their scheme to work more or less like a reverse Tora). Paths get reinforced or leightened with time by the nodes. For now a query is flood in the network, but future work will address this point, and only send the query to the relevant directions. Following messages are only sent on reinforced paths (avoid unecessay duplicates). - There is a set attributes and binop on them to let the application specify a query (eg: type of animal, confidence, frequency of anwser, duration, IS, GT, etc.). When a sensor detects something matching the query, it sends a message. - Filters: there are filters in all the nodes which may apply to all the messages they receive (in network application). For eg, if a node receive from 2 or more neighbours a massage saying that they have detected an elephant, it doesn't need to transmit this message many times. Once is enough. This can be done by forwarding the first one and discarding the next ones, or waiting for a while to agglomerate the data. Filters can also be used to implement nested queries (turn on sensors of type B when thoses of sensors detect something) without needing to go up to the originating node, then back again. The aggregation of data turns out to be a good idea seen the results of the somilation: the number of messages remains constant when the number of stimulus augment. The losses are much less with nested queries than the normal scheme (their MAC layer was pretty bad, so they had many losses anyway). They need an election scheme for the nested queries, but don't say how this would work. Nor do they really explain their "routing" / reinforcement scheme. But they do have error bars on their graphs! I think is a very interesting piece of research. -- André Allavena (local) 154 A Valentine Place École Centrale Paris (France) Ithaca NY 14850 USA Cornell University (NY) (permanent) 879 Route de Beausoleil PhD in Computer Science 06320 La Turbie FRANCE From wbell@CS.Cornell.EDU Tue Nov 6 13:49:59 2001 Return-Path: Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6InvR17179 for ; Tue, 6 Nov 2001 13:49:57 -0500 (EST) Received: from dhcp-384.rover.cornell.edu (dhcp-384.rover.cornell.edu [128.84.25.128]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id NAA10288 for ; Tue, 6 Nov 2001 13:49:56 -0500 (EST) Subject: 615 PAPER #35 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.16.99+cvs.2001.10.18.15.19 (Preview Release) Date: 06 Nov 2001 13:49:37 -0500 Message-Id: <1005072599.1124.2.camel@brute> Mime-Version: 1.0 35) Building Efficient Wireless Sensor Networks with Low Level Naming This paper discusses a different view of network communication that is geared towards simple devices such as wireless sensor nodes. The overall idea is that globally unique identifiers such as ip addresses just put another level of indirection in the network and need to be resolved from application specific information, which causes network overhead. The goal in this paper is to demonstrate that by avoiding ip style addressing, and instead by introducing a naming scheme based on things such as sensor type and geographic location, one can avoid the overhead of naming via directory based schemes. This reduces network utilization and increases the lifetime of battery powered wireless nodes in a sensor network context. Data communication is done via directed diffusion, in which paths from the source of the data to the interested node are setup via positive and negative reinforcement via a gradient technique, minimizing redundent data transmission. They also present a active networks style filtering/aggregation mechanism which can be used to coordinate sensor nodes and minimize network traffic to a user monitoring the status of the sensor network. In addition, they 'nest' queries in order to remove computational costs by making queries conditional on certain events; essential triggering a transmission in the network based on certain conditions in sensor nodes. The advantage of this is that it moves the computation into the network and away from the user, who would have to wait for the first sensor condition to happen and then trigger the second query manually, which is an inefficient use of network resources. I felt they didn't adequately highlight the issues involved with the attribute based naming and I couldn't get a good handle on the benefits/costs involved; they tended to highlight the benefits while hiding the costs. A useful discussion of the reasonable uses of this style of naming would have been important, as well as motivating the reason why typical ad-hoc networks couldn't be used in this context. Especially since sensor networks are going to tend to be made out of commodity components, it would be useful to use general ad-hoc protocols which will eventually have hardware support versus a specific purpose scheme. From samar@ece.cornell.edu Tue Nov 6 13:56:08 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6Iu6R17847 for ; Tue, 6 Nov 2001 13:56:06 -0500 (EST) Received: from aquinas.ee.cornell.edu (aquinas.ee.cornell.edu [128.84.236.57]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id fA6ItJJ05775 for ; Tue, 6 Nov 2001 13:55:19 -0500 Date: Tue, 6 Nov 2001 13:55:31 -0500 (EST) From: Prince Samar X-Sender: samar@aquinas.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 35 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 35) Building Efficient Wireless Sensor Networks with Low-Level Naming. This paper investigates naming for low-level communication based on application, rather than topology of the node as in conventional networks. This makes the identification of the information easy, allowing in-network processing and thus checking the depletion of network resources. The design of an attribute based naming scheme with flexible matching rules is explained in the paper. This naming enables application specific, in-network processing leading to flexible and energy efficient application design. The architecture of the proposed scheme is based on three components: directed diffusion, matching rules and filters. In directed diffusion, each node is tack aware, storing and interpreting the received data and making certain decisions based on it. Gradients are set up at the nodes as data messages are received. Data is also cached at intermediate nodes as it is propagated, helping in preventing loops and for in-network processing. An exploratory data forms a path along preferred nodes between the source and the sink. Subsequent messages are sent on the reinforced path only. Diffusion messages and application interests are composed of attribute-value-operation tuples. Attributes are identified by unique keys drawn from a central authority. The operation field signifies how the data and the interest interact, using binary functions. Filters are the codes that run in the network depending on the application. Filters are used for in-network aggregation, collaborative signal processing, caching and similar tasks that benefit from control over data movement. The simulation results show significant reduction in traffic and loss rates. One limitation of the scheme is that the sensors have to know the attributes, sensor types etc. beforehand. Also reliance on complete flooding of the network is a drawback, as flooding has been found to be very inefficient in various studies. Also it may be possible to expand the benefits of data aggregation beyond what they have listed. The authors mention that filters could be created dynamically and distributed to the sensors which is a very interesting point as gives a way to change the focus of the network as time progresses. From mh97@cornell.edu Tue Nov 6 14:21:43 2001 Return-Path: Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA6JLgR22124 for ; Tue, 6 Nov 2001 14:21:42 -0500 (EST) Received: from mars (syr-66-24-28-66.twcny.rr.com [66.24.28.66]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id OAA19661 for ; Tue, 6 Nov 2001 14:21:41 -0500 (EST) From: "hao ming" To: Subject: 615 PAPER 35 Date: Tue, 6 Nov 2001 14:21:32 -0500 Message-ID: <000001c166f8$3e9c2e70$6a01a8c0@mars> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2627 Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Building Efficient Wireless Sensor Networks with Low-Level Naming by John Heidemann this paper presents some interesting approaches to the naming of specific sensors networks. it eliminates the service binding by integrating the high level naming, i.e. sevice requests into the low level communication. further, two further optimization, aggregation and nested queries can be provided more easily based on this approcach. the propagation of information is done by directed diffusion while there is no routing within the network. the basic idea is as follows: data is named by a list of attribute-value-operation tuples. matching rules are used to identify the destination or if the intermediate filers should process the data. the operation field include some comparison operators such as GT, LE, and so on. two special ops are EQ_ANY and IS. usually, two sets of attributes should be compared. in that case, any one unmatched attributes causes the failure. the directed diffusion is data centric communication. it works in the req-rep way. in the req stage, the broadcast is used to set up gradients. in the second stage, the gradients are used later used as the path for reply. the data is cached at the intermediate nodes which can be used on different levels. one problem here is that "will sink take advantage of previous req-rep actions? the most interesting part of this paper is in-network processing. as every node interprets the packest, it is possible for it to process the packest. one example is suppressing the same packets sent to sink, which can greatly reduce the traffic. another thing is nested query, which can let some sensors trigger other sensors and sends back the final information to the sever without the involvments of the server. summary, the main contribution of the paper is 1. implementation of delcarative data by adding attri-value-op tuple to the data. 2. adopting nested query into the sensor network. 3. testing the idea with actual testbed. -ming