From mvp9@cornell.edu Wed Oct 9 23:42:29 2002 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.10) with ESMTP id g9A3gTh14424 for ; Wed, 9 Oct 2002 23:42:29 -0400 (EDT) Received: from zoopark.cornell.edu (syr-24-58-46-186.twcny.rr.com [24.58.46.186]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id XAA21266 for ; Wed, 9 Oct 2002 23:42:27 -0400 (EDT) Message-Id: <5.1.0.14.2.20021009233715.01af5f68@postoffice.mail.cornell.edu> X-Sender: mvp9@postoffice.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Wed, 09 Oct 2002 23:42:27 -0400 To: egs@CS.Cornell.EDU From: mike polyakov Subject: 615 PAPER 35 Mime-Version: 1.0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable The Heidemann et al present a simplified and potentially highly efficient system for coordinating sensor networks.  They eliminate the intermediate layer such as IP by substituting application-specific content addressing for topological addressing, and =93directed diffusion=94 for traditional routing; thus a use= r that wishes to query about his interest, and a path gets established to the nodes that can satisfy the interest.  The other main element of their system is the in-network processing.  The reasoning is that bandwidth is far more precious than CPU cycles, and so nodes in the path ought to do maximal processing of the input.  It is accomplished through the use of matching rules, which allow evaluation of the attributes of the packet by the node and filters, that allow nodes to process data when its attributes satisfy some criteria.  Using these techniques data can be aggregated and processed before it is sent to the user to minimize bandwidth consumption.
While replacing IP with content based addressing is only natural, shifting the work from the end points to the network itself is a rather interesting step.  The nested queries are particularly =91cute,=92 as they allow some sensors to turn on others automatically.  However, there are some questions lingering.  What exactly are these gradients and how is the routing actually done with all of these attributes floating around?  From the description, it seems when a user issues a query, all nodes receive it and create these gradients.  How long do they stick around and what happens when there are more than a few users (or when nodes start registering interest) will they have the memory for all this information?  Although there is some experimentation done to show that the techniques implemented by themselves are worthwhile, there is no significant evaluation of what will happen when a large system is actually implemented.
        The authors touch on many types of sensor networks that would be applications.  The actual set up of such a network for a given application is easy  taking for example the submarine detection.  Each node would have an (audio) sensor and some concept of its location, as well as some time mechanism, depending on application. The scale of sensor dispersal and purpose  are we targeting it, or merely want to be aware of its presence  affect how the data is treated.  Suppose we are only interested in noticing the submarine and its direction.  Any sensor registering noise from a submarine (this is assumed to be recognizably distinct from marine life, etc) sends a signal along the gradient path to the registered listener.  The nodes along the path would wait before sending the signal along an amount of time proportional to how far away the sending node is, in hopes of getting other signals to collate with.  So a node 2 hops down will wait x ms, a node 3 hops, x*a ms, where a depends on the speed of the network.  The only data that has to be transmitted is the location of the alerted sensor and number of hops so far, and some time field, so that a node that has received several signals can calculate where the submarine is likely to be and its speed, using the filter.  Both this estimate and the original data are then sent to user, and subsequent nodes can potentially refine the calculation if they receive other signals. From mr228@cornell.edu Thu Oct 10 00:26:52 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9A4Qph25009 for ; Thu, 10 Oct 2002 00:26:51 -0400 (EDT) Received: from cornell.edu (syr-24-58-48-238.twcny.rr.com [24.58.48.238]) by cornell.edu (8.9.3/8.9.3) with ESMTP id AAA21436 for ; Thu, 10 Oct 2002 00:26:50 -0400 (EDT) Message-ID: <3DA501A4.29DD52CF@cornell.edu> Date: Thu, 10 Oct 2002 00:27:16 -0400 From: Mark Robson X-Mailer: Mozilla 4.76 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: egs@CS.Cornell.EDU Subject: 615 PAPER 35 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper discusses an approach to naming (and routing) in Sensor networks. In typical sensor networks it is far more costly to transmit data than it is to process data. Their goal is to produce a system that operates under conditions where transmission is several orders of magnitude more expensive relative to CPU use. To this end, the system they come up with uses a large amount of in-network processing to make smart decisions about how often to forward data to other nodes (and to which nodes to forward to). Their system has three primary components: directed-diffusion, matching rules, and filters. Directed diffusion is briefly described in the paper. It is a mechanism whereby data is sent primarily to interested nodes. All nodes use in-network processing to create and maintain which of their neighbors they should forward certain types of packets to. Nodes express interests in certain types of data, and when nodes (or in this case sensors) collect data relevant to an interest, it is forwarded to neighbors such that the requestor will eventually get the results. These queries, or matching rules, are effectively the names in this system. So they are not naming nodes, but rather it is data (classes of data actually) that gets named. Filters are the final component and they allow for a higher degree of integration with the target application that sensor network is running. Filters are small pieces of code that get run on application specified data types. They assist in diffusion and processing by allowing things such as data aggregation at interior nodes, caching at interior nodes, and they can even alter the nodes which the data will be "diffused" to. The paper then presents an experimental setup and empiricial results of various tests. Their conclusion is that this approach (data aggregation specifically) can reduce traffic by 42% which translates to a substantial savings of total network power. Future work should look more at how specific classes of applications will work with this system. I think there are probably some interesting classes of applications that can benefit tremendously from the tight integration with the diffusiong via the filters. From liuhz@CS.Cornell.EDU Thu Oct 10 01:00:06 2002 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.10) with ESMTP id g9A506h00978 for ; Thu, 10 Oct 2002 01:00:06 -0400 (EDT) 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.5762.3 Subject: 615 PAPER 35 Date: Thu, 10 Oct 2002 01:00:04 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE661@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 35 Thread-Index: AcJwGeWmMvS5qTLuT7+hS3ohGANZHg== From: "Hongzhou Liu" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g9A506h00978 This paper introduces a low-level naming scheme that's external to network topology but relevent to the application. By using attributes with external meaning(such as sensor type and geographical location) at the lowest level of communication, this approach avoids multiple levels of name binding and resolution. Combined with filters, attrbute named data enables in-network processing, supporing aggregation, nested queries and similar techniches which are critical to reduce network traffic and conserve energy. This paper is the first description of the software architecture that supports attribute-named data and in-network processing in an operational, multi-application sensor-network. It is also the first paper that evalutes the performance of aggregation, nested queries and matching in an operational testbed. The communication architecture introduced in this paper contains three components: directed diffusion, matching rules, and filters. Directed diffusion is a data communication mechanism for sensor networks. Data is managed as a list of attribute-value-operation tuples. The sink, the node that is going to request data from sensors, uses the interest, also a list of attribute-value-operation, to describe what kind of data it is interested in. For example, if the sink want to detect the actions of submarines in an acoustic sensor field, it can send an interest like (class IS interest, type EQ submarine-search, interval IS 20ms, duration IS 10s, x GE 0, x LE 100, y GE 0, y LE 200), where x and y attributes are used to limit the range of search. Such interests are broadcast and propagated through the network. Sensors in the network will watch interests in submarines a special kind of interest: interests about interests with attributes (class EQ interest, type IS submarine -search, x IS 50, y IS 50). When the sensors receive the interest from the sink, they will apply the matching rules and see if the interest is the kind of interest they are interested in. If so, the sensor will send back data like(class IS data, type IS submarine-search, ...) to the sink. The data can be cached can processed in the network before it reaches the sink. Filters are application-specific codes that do in-network processing. Before they start working, filters should register interesters that can tell what kind of data(or interests), e.x. type IS submarine-search, they are willing to process. Then when such data(or interest) that matches their interests comes in, the filters are triggerred. Filsters are typically used for in-network aggregation, collaborative signal processing, caching, and etc. They are also usefully for debugging and monitoring. The naming scheme here is similar to that used in INS in some way. In both schemes, the nodes just specify what they want, not where to find it. Both schemes are attribute based. However, the naming scheme here is much simpler. It is not hierarchical and at the low level. we can use the names to route messages directly. No name resolution is necessay and no overlay network (of INRs) to forward messages). However, to discovery and maintain routes in such sensor network, flooding of explorary messages, interests, and reinforcements are necessay, which will certainly waiste the valuable bandwidth. Thus tradeoff must be made between overhead and reliability. Other issues like congestion control, energy aware MAC protocols and filters assisted optimization of routing, and etc are also deserved more attention. From bd39@cornell.edu Thu Oct 10 01:08:27 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9A58Rh02021 for ; Thu, 10 Oct 2002 01:08:27 -0400 (EDT) Received: from boweilaptop.cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id BAA12094 for ; Thu, 10 Oct 2002 01:08:25 -0400 (EDT) Message-Id: <5.1.0.14.2.20021010002101.00b59ff8@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 10 Oct 2002 01:07:00 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 35 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Directed Diffusion The main contribution of this paper is a method of distributing data through a sensor network. The authors note that in sensor network a)bandwidth is a limiting factor in the transport of data, while b)processing power is not and that the c)network stack for sensor networks can be collapsed together for efficiency because of the specificity of their application. They to propose a new naming scheme in which integrates attribute-value based naming directly into the network, which allow data sinks to advertise their desire for data, and for data sources to send data through the network towards the sinks in a distributed way, by using the request as the routing name itself. Directed Diffusion: - Names/Queries consist of attrib/value pairs designated with operators and and'ed together (similar to semantic filesystems) - Queries are flooded through the network from the source. The path from which a node hears the query is designated the gradient path. Imagine a field of vectors pointing towards a the origin of the query. - The first data packets from the sensors is flooded backwards. Nodes then begin limiting the broadcasts by reinforcing preferred neighbors and forwarding data to only their preferred next hop node. Negative reinforcements are sent to nodes from which a node which has found better preferred neighbors. - Along the path of the message, filter (active pieces of code) can be applied to the information to cache/aggregate/select information to be passed along. - Optimization of having a nested query - lesser sensors can trigger a larger sensor to go off. i.e. the main query can be itself be triggered by smaller queries. This can save power by only using expensive sensors when they are truly needed. Not much detail was placing in the description of the directed diffusion routing algorithm. It does not seem to perform very well. With only 1 sensor, the delivery rate is still only 55%. With 4 light sensors, directed diffusion has a delivery rate drops to 30%. It is unfortunate that their MAC layer protocol marrs the data by exacerbating the effect of collisions. (A modification of TORA seems like a good candidate for construction of the gradient.) The use of active code in the network to aggregate or compression information transmitted in the network seems to be a very good idea, given the success rates of their transmission and would reduce the data traffic of the sensor network. Overall the paper introduces a good idea for taking advantage of the characteristics of sensor networks, in which communication occurs to relatively few destinations, where nodes are not peers (in capability) and where perhaps routing metrics such as hop-count/latency are of lesser importance. Issues such as construction of the gradient, and what kind of in-network processing is possible needs to be looked at. (For example, nodes closer to the sink (and farther away from the event) can perform "false alarm" culling by correlating data from geographically close sensors. The in network processing could take advantage of the fact that some nodes are involved with sensing the event, while others are merely ferries of the information. Submarine application: A couple main nodes able to transmit information to a ship, many lesser nodes with sonar sensors. Each node would need to maintain recent sighting (soundings) and have some kind of locational knowledge. In network processing would involve duplicate information culling, certainty factors (elimination of false alarms by correlation of nested queries for example). From hs247@cornell.edu Thu Oct 10 01:24:17 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-0.nyroc.rr.com [24.92.226.125]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9A5OGh04747 for ; Thu, 10 Oct 2002 01:24:16 -0400 (EDT) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout6-0.nyroc.rr.com (8.11.6/RoadRunner 1.20) with ESMTP id g9A5OEL26787 for ; Thu, 10 Oct 2002 01:24:14 -0400 (EDT) Message-Id: <5.1.0.14.2.20021010012406.00b32d20@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 10 Oct 2002 01:24:17 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 35 Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1"; format=flowed Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g9A5OGh04747 So far we have seen many protocols for ad-hoc networks, but none have dealt with naming. The papers that were read last day with attribute-naming on semantic file systems didn’t really deal with naming with ad-hoc / wireless networks. The main contribution of this paper is low-level naming which was especially designed for building efficient wireless sensor networks. The claim of this paper is that with wireless networks, bandwidth is limited but processing resources is plentiful. With this assumption, naming is introduced at the lowest level. Names in this system are attributes (ie. Geographic location). These name are then meaningful external to the system. By having naming at the lowest level, the system doesn’t have to worry about name binding at the higher levels, which protocols like IP use. There are 3 parts to low level naming: Directed Diffusion, matching rules, and filters. Since names are based on attributes, matching rules help identify a name. Directed Diffusion is the method used set up a link between a sink (person requesting data), and its sources. If someone were to request a node between location x and location y, it would forward a interest in which intermediate nodes would forward to or broadcast (if it doesn’t know) to it’s neighbouring nodes until the request has reached a matching source(s). When the request reaches the source(s), the data is then sent back to the sink. Since the naming is in the attributes, (therefore in the data passed back), we need matching rules to identify when the data has reached its destination. Matching rules are operations that define how data interact. Operations can include <, =, > etc… . Filters also use matching rules. If an intermediate node from the source(s) to the sink receive multiple sets of data that can be processed (ie. Be combined,) then processing is done on that node before passing it on (this extra processing reduces bandwidth). The paper goes on to describe several implementation of this work and they found it to reduce traffic by up to 42%. Because of application specific filters and matching rules the efficiency of the protocol depends greatly on how the filters are designed and matching rules work. Potentially, a poorly designed system could just end up with flooding of data (ie. No filtering, uninformed passing of interests). To set up a network to detect submarines, an interested node could first send out a request to all sensors in an area of interest. Then if a node senses something, it can send data back to the requestor. Each sensor node should have an idea of its location, and collect additional data values such as the time it detected a submarine, and if it was really good, the direction and speed. Now if a filter received data from more than one node, it could possibly use that information to process the speed, the path of the submarine before passing the data along (ie. Create a map of sightings). From shafat@CS.Cornell.EDU Thu Oct 10 02:09:37 2002 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.10) with ESMTP id g9A69bh13658 for ; Thu, 10 Oct 2002 02:09:37 -0400 (EDT) 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.5762.3 Subject: 615 PAPER 35 Date: Thu, 10 Oct 2002 02:09:37 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D134FA8@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 35 Thread-Index: AcJvWBACb4Ca6m4TTpqluoDa+ADXRA== From: "Syed Shafat Zaman" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g9A69bh13658 This paper presents a power efficient low-level naming mechanism for wireless sensornetworks. However, rather than using the conventional naming system based on network topology, the low-level communication in this system is based on names that are application relevant. This property, as the paper highlights, reduces extra overhead costs associated with resolving name bindings, and also enables in-network processing. The communication architecture is based on three major components: directed-diffusion, matching rules, and filters. Directed diffusion takes advantage of the in-network processing property of the system, and can diffuse any specific "interest" messages in the network by choosing the next-hop neighbors carefully. The naming is done through attribute-value-operation tuples that form part of a query. Filters can also assist in data aggregation, caching and duplicate suppressions among other things to keep the power consumption as low as possible. Although the concept of using low-level naming is rather interesting, the paper made a number of underlying assumptions that expose possible weaknesses of the system. It did not go into much depth in its discussion on failures in the architecture. Presently, recovery from data loss is left to the application despite the fact that the experimental results showed a high degree of data loss. That however was blamed on the MAC layer protocol used, and is being worked on. The paper also refers more than once to using a geographic topology to locate neighbors. This issue might be quite significant in implementing nested queries, or in mobile wireless networks. However, it hardly talks about an effective way of accomplishing that task. How the attributes are defined from keys drawn from a central authority is also barely touched upon. Then, there is of course the problems of network congestions, and latency due to data aggregation. Overall, I thought the architecture proposed does a commendable job on making the system quite power efficient. This was also verified by the experiments that were carried out. It might actually be a good idea to simulate the system on a suitable simulator and inject a number of monitoring tools to get better test results. A better MAC protocol is probably also a must. A sample application: detecting a submarine in an acoustic sensor field. Firstly, all these sensors have to be placed in a known geographic topology with their locations made available to other sensors. They have to be have a path to any other node in the network (is transmission range underwater different?). A sink (could be a land or ship-based central computer) can periodically subscribe with an "interest" message asking for information within a particular 3d region, providing specific latitudes, longitudes and depth as attribute values. It could also provide a threshold length of object, minimum speed and the amount of EM-waves its radiating (we need more than just acoustic sensors for this though) as attribute values. The "source" sensors would process this information and diffuse it into the network, and hopefully directing it to only the sensors placed in the desired region. Once the data messages are on their way back to the sink, the filters on each node could do some data aggregation, combine reported result from all the previous sensors, and see if a submarine has been detected. As soon as the first sensor figures out that the result is negative, it could end the process there and not propagate the information further to reduce power consumption. From yao@CS.Cornell.EDU Thu Oct 10 02:18:00 2002 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.10) with ESMTP id g9A6I0h15331 for ; Thu, 10 Oct 2002 02:18:00 -0400 (EDT) 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.5762.3 Subject: 615 PAPER 35 Date: Thu, 10 Oct 2002 02:17:59 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302ED4C4C@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 35 Thread-Index: AcJwJMeqwRNUu12tTi6LVaFNSjvXrQ== From: "Yong Yao" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g9A6I0h15331 The paper presents how to use Directed Diffusion to build an efficient wireless sensor network with low level naming. Directed diffusion can be considered as a content-based routing protocol, which has a publish-subscribe interface. Any node that is interested to some special event type can subscirbe to that event type and broadcast an corresponding interest message out. On the other hand, the data sources, or service providers will publish data items they have. If a subscribe request matches a published data, the data will be transfered to the node in control of the gradients saved at internal nodes. A gradient reflects the potential quality of a path to the destination. The gradient of the optimal path will be increased by a reinforcement message; otherwise it will be decreased by a negative reinforcemnt message. In-network processing or aggregation can drop redundant packets. However, direct diffusion has some weakness either. Initially, an interest floods to the whole network, and establishes an gradient between each pair of neighbors. So the first few data packets have to flood to the whole network. Although directed diffusion will finally converge to one or two optimal paths, if the network topology is stable, it still generates redundant packets in lower frequence along other pathes, and depends on them to recover from failures. If the frequence is too high, then a lot of energy is wasted; otherwise, if the frequence is too small, then it takes a long time before the destination receives a backup packet. Directed diffsuion has to make a difficult choice between energy consumption and latency. To use directed diffusion to build a sensor network application to detect objects, sensors can represent object detections as attribute value pairs, for example, . An user query or applications request can be translated as an attribute value pair too. Directed diffusion will automatically forward matching events to the server. In-network processing may include aggregation, which drops redundant detections. For example, an object can be discovered several times at different places, but one report is usually enough. Filters can be installed at internal sensors to perform application specific in-network processing. Yong From xz56@cornell.edu Thu Oct 10 03:38:58 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9A7cwh00950 for ; Thu, 10 Oct 2002 03:38:58 -0400 (EDT) Received: from XIN (dhcp-ece-167.ece.cornell.edu [132.236.232.167]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id DAA16709 for ; Thu, 10 Oct 2002 03:38:56 -0400 (EDT) Message-ID: <008001c27030$16d47a40$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 35 Date: Thu, 10 Oct 2002 03:38:56 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 This paper presents an approach of low-level naming, which is especially suitful for wireless sensor networks with relatively high-speed processor, small bandwidth. Different from higher-level naming, which usu. relies on topological location and can differentiate different users but needs binding services to map to lower-level names, low-level naming is topology-independent. Its key feature is application-specific, so the names are based on things like sensor types (data type) or geographic location (data source). The structure has three components: Direct diffusion, matching, and filters. Direct diffusion is data-centric in that data are independent from the source who collects them and the sink names the data it wants and broadcast its interest in the form of attribute-value pairs. The sensors receiving the interest msg decide whether it should collect data according to Matching rules. When the data are sent back to the sink who named them, they are transmitted in the manner of hop-by-hop and each intermediate node using the Filter to do some in-network processing to decrease the data rate thus lower the channel usage. Also, the sink may use reinforcement/neg-reinforcement to choose the optimal path to communicate with the sources. There are some optimizations in implementation. Opportunistic data aggregation selects sensors who do the data aggregation by geographic attributes. Nested query allows one event triggers another thus reduces the control loads. Evaluations show that the aggregation and nested query have great benefits. However, it's less markable when the number of sources is great because of the collision. So it maybe can be improved by introducing opportunistic sending. If I am going to build a sensor network application to detect submarines in an acoustic sensor field using directed diffusion. The in-network processing component would be a filter? The data values could be: class IS data; task IS "detect submarines"; confidence IS 80; latitude IS 20.0; longitude IS 80.0; target IS "submarine". The filters may look like: task IS "detect submarines"; confidence GT 60; latitude GE 10.0; latitude LE 40.0; longitude GE 70.0; longitude LE 90.0; target IS "submarine". As is mentioned in the paper, the performance of directed diffusion is highly dependent on the specific MAC protocol used, so the future work may be search for some sending strategies that are best suit for the sensor network and explore the performance combined with directed diffusion. From pj39@CS.Cornell.EDU Thu Oct 10 03:47:51 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9A7lph03144 for ; Thu, 10 Oct 2002 03:47:51 -0400 (EDT) Received: from cornell-yb3go20.cornell.edu (syr-24-59-67-50.twcny.rr.com [24.59.67.50]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id DAA25872 for ; Thu, 10 Oct 2002 03:47:49 -0400 (EDT) Message-Id: <5.1.0.14.2.20021010034319.02127448@postoffice2.mail.cornell.edu> X-Sender: pj39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 10 Oct 2002 03:44:59 -0400 To: egs@CS.Cornell.EDU From: Piyoosh Jalan Subject: 615 PAPER 35 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Building Efficient Wireless Sensor Networks with Low-Level Naming This paper describes an emerging class of distributed systems where low level communication is based on attributes external to the network rather than on network topological information. The major contributions of this paper are attribute based naming scheme with flexible matching rules thus enabling application specific, in-network processing. The communication architecture of this scheme is based on three components namely directed diffusion, matching rules and filters. Directed diffusion is a data centric unlike traditional networks which are host based. It establishes an efficient n-way communication between one or more sources. Each node maintains gradient which represents the direction towards which data matching an interest flows and a cache to supress duplicate messages and for in-network processing. Matching rules are based on attribute value pairs related with an operator such as EQ, LE etc. The matching could be one way or a two way complete match and in the case of multiple attributes and operators they are anded together. Filters are used for in-network aggregation and collaborative signal processing, caching and similar tasks. Filters register the kind of data they handle and are invoked to manipulate the data of that kind. Filters thus can process data and purge a few replies and send the relevant ones to the source. Thus filters reduces unnecessary communication and hence greatly extends the systems operational lifetime. The paper describes implementation of this scheme along with other similar implementations such as declarative routing at MIT's Lincoln Lab and micro diffusion for small processors (implemented as component in UCB's tinyos). The authors emphasizes the benefits of aggregation and nested queries which noticeably improves the performance. The paper also discusses the nested query approach in Cornell's Cougar project(sensor database project). Future work could be directed towards making this scheme work for an mobile wireless network. Tools need to be developed to report changin topology observe collision rates and energy consumption. Selection of appropriate MAC protocol is another challenge. Describe how you would build a sensor network application to detect objects (e.g. submarines in an acoustic sensor field) using directed diffusion. What are the in-network processing components ? What are the data values ? What do the filters look like ? What state does each component carry ? To detect objects I would construct a sensor network application as described in this paper with attribute based naming scheme. The primary attribute of interest in this case being the object such as a submarine or a navy warship. The secondary level attribute or interest about interest could be distance, warship capability, current submarine depth, nuclear capability etc. A typical query woule be thus translated into by the interaction of diffusion and attribute matching type EQ submarine depth GE 500 distance LE 1000m interval IS 10s nuclear IS yes In network processing in this case could be that out of many results possible the filter set would start giving most relevant results first submarines which are more nearer are filtered ahead of others and there results are sent to the source every interval in this case ie 10 seconds. From kwalsh@CS.Cornell.EDU Thu Oct 10 10:23:17 2002 Received: from duke.cs.duke.edu (duke.cs.duke.edu [152.3.140.1]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9AENHh01266 for ; Thu, 10 Oct 2002 10:23:17 -0400 (EDT) Received: from localhost (moe.cs.duke.edu [152.3.140.74]) by duke.cs.duke.edu (8.9.3/8.9.3) with ESMTP id KAA02352 for ; Thu, 10 Oct 2002 10:23:12 -0400 (EDT) From: kwalsh@CS.Cornell.EDU Received: from 132.236.29.74 ( [132.236.29.74]) as user walsh@imap.cs.duke.edu by login.cs.duke.edu with HTTP; Thu, 10 Oct 2002 10:23:11 -0400 Message-ID: <1034259791.3da58d4fe065a@login.cs.duke.edu> Date: Thu, 10 Oct 2002 10:23:11 -0400 To: egs@CS.Cornell.EDU Subject: 615 PAPER 35 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.0 X-Originating-IP: 132.236.29.74 Building Efficient Wireless Sensor Networks with Low-Level Naming As an illustration of the funciton of directed diffusion an in-network processing, I will discuss an application in a sensor network. I imagine a sensor network to aid in confirming the existence of the Ivory-billed Woodpecker. The great bird was thought to be extinct, but there have been unconfirmed sightings in remote bayous of southern Louisiana. The bird has a very distinctive call, but only a photo would provide conclusive evidence of existence. A probably sensor deployment would consist of audio sensors, audio recorders, and cameras (still or motion). Any search would likely last for many months (the bird is quite rare, if it exists at all), and the remoteness of the habitat prohibit any infrastructure or direct intervention. The sensors would probably not be mobile, but would need to power up and down for power conservation. One setup might be the following. Audio sensors could routinely listen for sounds. A low-power sensor could be used continuously (no recording, little analysis of data). Upon hearing nominally interesting sounds, the sensor could move to full-power mode, analyzing the audio data and looking for the charactaristic audio profile of the ivory-bill (good recordings exist at Cornell's ornithology lab, providing training data). Interesting events would trigger a nearby recording device (or send the data to the recording device). Some threshold of such audio events would also trigger nearby cameras. At the highest level, remote researchers could query the network gathering audio or camera data, statistics on interesting events, correlations between events, etc. Here, directed diffusion would provide many benefits. Consider the cameras: they initialy publish an interest in nearby high-level audio events (type EQ audio-event, level=2, lat GT 30.410, lat LT 30.418, lon GT -91.549, long LT - 91.543, confidence=60, payload=notification). This sets up a gradient from all sensors (ALL sensors) towards the camera for these events. When an interesting audio event occurs at a high level, the audio sensor publishes this fact as a named packet. This flows to the camera which then can begin recording. In-network aggregation might occur both at the low level (cameras) and the high level (research queries). Audio events in similar geographic regions might be coalesced into a single event with higher confidence value (or perhaps add a frequence IS nnn) field. This would save on network bandwidth, and also allow cameras to gain an automatic thresholding mechanism. This does not match exactly what we want, however, as the camera would still be notified of low- threshold events. Advertising a special interest in only high-level events would ruin the aggregation mechanism. At a high level, a researcher could query for cameras that have taken several pictures recently, or high-confidence audio data. The data could be collected over the network by specifying payload=audio- data, if desired. Again, in-network data processing could compress the audio data at stations that have spare battery power. Or, a few stations could be equipped with extra batteries and faster cpus (or even compression hardware). Data that passes through these stations might be further analyzed, or compressed, before being passed on through the network. A sligtly different scheme would use a nested query: researchers ask for compressed/analyzed data from the special stations, which then ask for uncompressed/unanalyzed data from the rest of the network. This would guarantee that data is first compressed and analyzed before being passed on. From smw17@cornell.edu Thu Oct 10 10:28:12 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9AESCh02802 for ; Thu, 10 Oct 2002 10:28:12 -0400 (EDT) Received: from cornell.edu (syr-24-161-107-202.twcny.rr.com [24.161.107.202]) by cornell.edu (8.9.3/8.9.3) with ESMTP id KAA22215 for ; Thu, 10 Oct 2002 10:28:11 -0400 (EDT) Message-ID: <3DA58D9F.9000604@cornell.edu> Date: Thu, 10 Oct 2002 10:24:31 -0400 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.4.1) Gecko/20020508 Netscape6/6.2.3 X-Accept-Language: en-us MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 35 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Directed Diffusion Directed Diffusion is a communication mechanism intended for use in sensor networks. The specific methodology provided in the paper describes a routing scheme for such networks, with sensor nodes providing the data sources and the viewing nodes the data sinks. The primary operation of the described network is a query-based mechanism, where a data sink must first express an interest in a particular sensor reading before the sensor will transmit the data. Upon origination of a data interest, the data sink transmits an exploratory message that is flooded throughout the network to all appropriate nodes. Each node recieving the exploratory interest message constructs a gradient, essentially setting up a directed link between the recieving node and its neighbor. When a sensor node capable of responding to the interest recieves the interest message and measures data matching the specified interest, the node sends an exploratory data packet. This data packet travels back along the gradient to the originating data sink. The sink then selects one neighbor returning valid data to be its preferred neighbor, reinforcing that gradient as the primary communication route. The selected preferred neighbor then selects its own preferred neighbor, until a path of preferred neighors has been established between data source and data sink. This preferred route is maintained until it breaks, or until a subsequent exploratory message (for path freshness & matinence reasons) detects a superior route. A node may change its preferred neighbor through negative reinforcement when necessary. The data selection is achieved by matching the desired data conditions (equality, inequalities, match all, specified as formal values) with the actual data from the sensors. Multiple specified formal values are treated conjunctively, allowing for the easy specification of a rectangular area or a bounded interval for data values. In addition to the specified interest, it is also possible to create data filters within the sensor network to reduce duplicate reportings where possible and to aggregate multiple sensor readings into a single packet. In addition to data aggregation, they also present the ability to perform nested queries of sensor nodes, where sensor results may trigger measurements on other sensors without direct intervention of the viewing user. This is an attempt to improve localization and reduce the overall bandwidth used in the network by avoiding unnecessary communications. This system was implemented on a real-world system in two different forms. The first form factor was a collection of PC-104 embedded computers (66 MHz x86) equipped with a low frequency (~418 MHz) radio modems with 13kb throughput. This was where the majority of the investigations were done, and does demonstrate the basic functionality of the system. Unfortunately, the limited control over the MAC layer limited the useful power efficiency data that could be determined. Similar problems were evident in the aggregation analysis, but the results do show that data aggregation, especially when added latency can be tolerated, can significantly reduce network traffic. A second form factor was also constructed, running on an 8-bit microcontroller with 8KB of memory. While this was not heavily discussed, and required a very bare-bones version of the protocol described, it does illustrate the scaling of this system to much lower power nodes. In order to design a sensor network to detect an object, I will assume that we are starting with a collection of sensors capable of localizing the desired object within some uncertainty Delta(), and also capable of identifying distinct classes of objects. Assuming that we have configured these sensors into a partition-free network, I would set up the detection system as follows. First, a master node (the primary data sink) would be configured for an interest in a particular object, say object=YellowSubmarine, within a given area. This would generate a query as follows: (type EQ YellowSubmarine, Interval IS 100ms, duration IS 10 minutes, confidence GT 50, x GE -100, x LE 100, Y GE 200, y LE 400, Z GE 0, Z GE 50) This will generate a data stream that will report all objects of type YellowSubmarine ten times per second that fall within the rectangular solid defined by (-100,200,0) and (100,400,50). A potential matching event would be as follows: (type IS YellowSubmarine, Interval LT 120ms, duration GT 2 minutes, confidence IS 95, X IS 0, Y IS 221, Z IS 32) Within the network, I would design a filter to be applied by the sensor nodes that averages data that is within the uncertainty Delta() to aggregate potential sightings from multiple sensor sources into a single, hopefully more accurate sensor response. I would also provide a mechanism to disable filtering if desired, however, should more sophisticated off-line processing be desireable. In such a configuration, the major state present is the gradient information stored in each node for each sink node, the active queries at the appropriate sensor nodes to monitor, and the code for any desired in-network filtering. From tmroeder@CS.Cornell.EDU Thu Oct 10 11:22:47 2002 Received: from dhcp99-233.cs.cornell.edu (dhcp98-88.cs.cornell.edu [128.84.98.88]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9AFMkh18139 for ; Thu, 10 Oct 2002 11:22:47 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp99-233.cs.cornell.edu (8.11.6/8.11.6) id g9AFL2A01235; Thu, 10 Oct 2002 11:21:02 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15781.39645.984100.386072@dhcp99-233.cs.cornell.edu> Date: Thu, 10 Oct 2002 11:21:01 -0400 To: Emin Gun Sirer Subject: 615 PAPER #35 X-Mailer: VM 7.07 under Emacs 21.2.1 This paper builds on past work of the authors to create a routing algorithm for sensor networks which does not rely on the standard IP infrastructure to function correctly (and, in particular, to assign unique names to nodes). Instead of dealing with hosts as the main communication points, they use an attribute model (not unlike INS in some ways) to specify queries which go out over the network. They seek to do more local processing instead of sending bits on the network, since they are using nodes which require much more power to send than to compute. The failings of this system are in part apparent in the actual tests run by the authors. First, the system becomes unusable even with a small number of nodes. They were using 14 nodes on two floors of a building, and found significant congestion problems. They interpret this to be a problem with the MAC protocol that they are using for their nodes (no RTS/CTS or ACK), although it is difficult to tease out the difference between protocol inefficiencies and MAC-layer problems, since they have no techniques for actually measuring power consumption locally at the nodes at runtime. This problem dominates much of the analysis, and makes it difficult to determine if the protocol of directed diffusion in particularly effective. Second, their data shows that unidirectional links are common, at least in their environment. Multipath routing could save hassle here by allowing the packets to return (for example) via a different path than they came. Dropping all of the paths except the reinforced one seems to be wasteful, since they likely will need to be re-established again, given the inconsistency of links in the network. The question we need to answer today is: "How would you build a sensor network application to detect objects (e.g. submarines in an acoustic sensor field) using directed diffusion?". (we will work off the example). Given a sensor field to catch acoustics from subs, we would have only one type of node in the network (the acoustic node), and they would all be sources for our sink. The data would be the strength of the acoustic signal received, the time it was received, and the confidence that it was actually a sub. Each component along the chain back to a given sink (say some monitoring station connects to the nearest sensor and makes it the sink) would do the in-network processing by checking to see if it heard the event at a corresponding time (assuming we know something about where the nodes are distributed with respect to each other; either that this positioning is static or that we have some localization scheme happening), and at what strength. It would then modify the data to include better approximations of the sub's position at that time. It could also wait to aggregate other response that probably came from the same sub (this is (reasonably) assuming low density of subs :-), and then send the improved estimate along the chain. This processing would be triggered by the filter on this particular submarine detection data. Each component would have to recall the recent pieces of data it has heard (for correlation and for aggregation). This is, however, the only state it would need, and it could time it out relatively frequently. From ashieh@CS.Cornell.EDU Thu Oct 10 11:23:52 2002 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.10) with ESMTP id g9AFNph18330 for ; Thu, 10 Oct 2002 11:23:51 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g9AFNpq00168 for ; Thu, 10 Oct 2002 11:23:51 -0400 (EDT) Date: Thu, 10 Oct 2002 11:23:51 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 35 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Detecting objects using directed diffusion: - A subscription is a detection profile describing the objects of interest. E.g. size, estimated value, position, any additional data that should/must be collected. - Each sensor node records state about the detection profiles that clients have subscribed to. It activates the appropriate sensors for performing the detection, optionally powering up only a subset for realizing the "must" discrimination parameters. Once an object is actually detected, it may power up more. - The employed filters depend on the usage model for the network. If many clients are possible, it is probably more efficient for the sensors to propagate very general information, which is likely to be useful to more queries, and then in-network filters somewhere translate the general information into specific information that particular clients are interested in. ** Contributions The central idea of this paper is to name "interesting" nodes using attributes, and integrate the discovery of "interesting" nodes with routing. The effect is that routing and other network activity can be data- and application-dependent at non-endpoint nodes. Nodes are named using an attribute pattern, which may describe either static information about the node, or dynamic sensor information. A nice feature of this naming scheme is that there is a natural way of specifying multiple interesting nodes with the same exploration message. These patterns are used to construct routing information in an manner similar to an on-demand multicast (except with the intended dataflow reversed), namely the subscription of the interesting pattern is broadcast from the interested node. Positive and negative route reinforcement is used to prune redundant routes from the induced routing graph. In-network filters are supported by directed diffusion. These filters allow non-endpoint nodes to perform application-specific actions on matching data, to support aggregation, intelligent query suppression, and distributed signal processing. Aggregation and nested in-network queries are presented as possible filter applications. Nested queries are wired-ANDs of query results from different data sources; in other words, a match on some data source may trigger more processing on a different data source. Filtering allows this join to occur within the network, without having to propagate control and data to the endpoints. The paper also points out that the choice of MAC complicates power (since MAC power usage can potentially swamp any higher-level optimizations) and performance analyses. ** Shortcomings The paper describes the need for reinforcement of routes, but do not describe how this is performed in the analyses, or discuss the interaction of network dynamics (changing latency) with reinforcement. Reinforcement also begs a robustness analysis or discussion; it can both increase (reduce network traffic) and decrease (not enough redundant routes, or not enough negative feedback to prevent congestive collapse) robustness. The performance analysis also lacked direct comparisons to other systems. Of interest are the relative packet and byte overheads of different routing and naming schemes, for the applications that were described. ** Future work - Investigate additional abstractions to help in performing distributed computation/filtering. For instance, it is possible to generalize a two-level query to: 1) Do some processing on this interesting data 2) Send the result to me. Some mechanisms for enabling this may be to automatically generate filters in the network that prevent control/data messages from being propagated beyond sensor nodes that can contribute additional results to the distributed computation. For instance, an object location system can be extended to compute a motion vector by propagating the contact information locally, to a distance limit based on a iteratively refining depth based on the current estimate of the motion (which may change), and an estimate of the detection range of the relevant sensors. In this case, filters are generated and propagated by other filters. - Generalization/simplification abstraction. That is, subscriptions from multiple clients are aggregated & translated into general subscriptions by in-network filters, or at the sensors (which then inject the filters along the backwards route). This reduces the workload on the sensors. On the way back to the clients, the generalization is converted back to the specific, shorter query that clients were interested in. - Dynamically generating filters in response to changing netowrk dynamics (topology, load). - Describe optional matching. Not necessarily an OR, but describing optional additional parameters in the pattern to be returned that might be interesting to the endpoint. From ks238@cornell.edu Thu Oct 10 11:27:40 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9AFReh19453 for ; Thu, 10 Oct 2002 11:27:40 -0400 (EDT) Received: from ks238.cornell.edu (syr-24-24-18-11.twcny.rr.com [24.24.18.11]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA26991 for ; Thu, 10 Oct 2002 11:27:38 -0400 (EDT) Message-Id: <5.1.0.14.2.20021010112536.0215d590@postoffice2.mail.cornell.edu> X-Sender: ks238@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 10 Oct 2002 11:26:28 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 Paper #35 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper examines the implementation of a low-level naming protocol that facilitates communication in ad hoc networks through the use of attributes that are pertinent to the specifications of an application. The authors identify the energy and CPU limitations inherent in ad hoc networks as the significant barrier preventing the implementation of energy intensive naming protocols that rely on topological location. For example, the internet relies on a naming scheme based on topological location, where nodes in close proximity of each other tend to have IP addresses with similar prefixes. However, such networks are expensive to establish and maintain. The primary contribution of this paper is the proposal of an attribute based naming scheme that is completely removed from topological naming schemes (although the attributes may refer to the geographical location of a node). In addition to attribute based features, the protocol also employs in-network processing which uses application-specific code to enable each node to trigger filters within neighboring nodes to activate certain processes and enable data transfers (.e. light and camera example from the paper). The key three features of the protocol's communication architecture are directed diffusion, matching rules and filters. First, data is disseminated through a network using directed diffusion which relies on attributes to decide what data to forward to other nodes. Then, with matching rules nodes are able to process if the correct data has been received and if this kind of data is something they need to process. Finally, through filters, this data can be recognized and processed (in-network processing) and thereby facilitate further diffusion of the data or trigger an appropriate response. In order to detect objects using sensor networks, one may use a similar approach to the one described in the paper for observing animals in a forest. First, an interest is originated at a sink node and then diffused or broadcast to all nodes so that they may become "interest aware" (i.e. aware of the submarines location). This interest then becomes the attribute which the sensor seeks to match. When one of the sensors in the network discovers the submarine, we see that its interest or attibute has been matched. Then, filters within each node will activate in-network processing to take the appropriate steps defined by the original sink node. In our case, in-network processing would trigger other local networks (one hop away) to wake if they are in an idle state and data collection from this subset of the network close the object will begin. The data that is returned by this subset of nodes would correspond to the attributes that have been discovered which satisfy the original interest. Then source nodes merge and aggregate this data based on the original interest and transfer it back to the sink node. From vrg3@cornell.edu Thu Oct 10 11:34:58 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9AFYvh21210 for ; Thu, 10 Oct 2002 11:34:57 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA20093 for ; Thu, 10 Oct 2002 11:34:54 -0400 (EDT) Date: Thu, 10 Oct 2002 11:34:54 -0400 (EDT) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 35 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents a system combining naming with low-level ad-hoc routing especially optimized for a wireless sensor network. In such a network, there are data sources and sinks, plus intermediate routing nodes, and all of these nodes have abundant processing capabilities and limited data transmission capabilities. The directed diffusion method of transferring data uses a technique of naming based on the properties of the data. Data moves through the network based on its attributes and based on interest. Nodes which require data announce that they have an interest in a particular type of data (using equality and inequality operators). Sensor nodes announce that they have an interest in interests in their type of data. Interests are initially flooded through the network but paths are then refined using reinforcement. Intermediate routing nodes use matching rules to determine how to do this directed diffusion. They can also apply filters which process, refine, compress, and/or aggregate the data to improve the efficiency of the network usage. Further, sensors can be turned on based on data from other sensors, allowing low-power sensors to trigger high-power ones. Our example of a field of acoustic sensors meant to detect submarines would involve sensor nodes with passive hydrophones to listen for the presence of a submarine, each with knowledge of its location. Near these hydrophone nodes, perhaps at a lower spatial density, could be more active sensors, such as cameras or active sonar imagers. These would ordinarily be in a low-power standby mode. They would announce interests in acoustic data from any passive listeners in their general vicinity, expressed using inequality comparisons of location. Presumably at some point there would be a node whose purpose was to send alerts to a remote entity; nodes between the sensors and this transmitter would aggregate the data by looking for coherency and reconciling differences. The transmitter would require a good deal of power and would only be interested in data which was already put together and definitively represented the presence of a submarine. From mp98@cornell.edu Thu Oct 10 11:39:21 2002 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.10) with ESMTP id g9AFdKh22191 for ; Thu, 10 Oct 2002 11:39:20 -0400 (EDT) Received: from cornell.edu (r109493.resnet.cornell.edu [128.253.240.252]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA14833 for ; Thu, 10 Oct 2002 11:39:20 -0400 (EDT) From: mp98@cornell.edu Date: Thu, 10 Oct 2002 11:38:49 -0400 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 35 To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <5F5F5C64-DC66-11D6-B57A-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.546) This paper describes a system somewhat similar to INS. Names in the network described in the paper are application specific names giving information like capabilities or location. The system works upon a subscribe-advertisement model. Nodes who desire information flood a subscription encoded as a set of attribute-value pairs and operators through the network through 'directed diffusion'--A system in which nodes maintain soft state about in order to reverse the paths later, a notion of gradients--until it hits a node that matches the subscription request. This node will send an initial data message out, which will reverse the gradients set up during the directed diffusion phase. Subsequent data messages may not necessarily be forwarded on immediately. Instead, they may cache the data in order to combine it with other data or remove the data or modify the data--All based on the notion of in-network filtering. The filtering is implemented fairly low down on the protocol stack in network application specific code, a feature which makes the system less flexible. The motivation is that while filtering may be expensive in CPU cycles, it will cut down on the expense in terms of bandwidth which is more valuable. An example is in-network data aggregation--Rather than having many sensors respond individually to the user, in-network processing will collate the individual sensor information at a central sensor who will respond to the user with a single response. Nested queries are a way to trigger sensors to conserve resources--One may want to get video input, but only when something is happening, so one may have motion sensors trigger the camera sensor. To use such a system to detect submarines or something similar, a user would need a model for how to detect a submarine. Then, the user would have to construct a request which would specify the kind of relevant input (i.e. location, sensor type) for their particular interest and direct diffuse it through the network. For efficiency, implement an in-network system for collating this information (through data aggregation) and processing it at a central node who would run a filter which determined, based upon the algorithms for detecting a submarine, whether or not the inputs did constitute Red October. The sensors would record acoustic information, and they would be characterized by location. The peripheral sensors in this model would only have to collect data blindly and forward it to the central server would who be the one responsible for knowing where to send it and how to process it. From mtp22@cornell.edu Thu Oct 10 11:52:33 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9AFqXh26083 for ; Thu, 10 Oct 2002 11:52:33 -0400 (EDT) Received: from narnia (syr-24-58-57-15.twcny.rr.com [24.58.57.15]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA11341 for ; Thu, 10 Oct 2002 11:52:33 -0400 (EDT) Content-Type: text/plain; charset="iso-8859-1" From: Matt Piotrowski Reply-To: mtp22@cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper 35 Date: Thu, 10 Oct 2002 11:52:55 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02101011525508.00149@narnia> Content-Transfer-Encoding: 8bit This paper describes a system for low-level naming in sensor networks. It's main contribution is that it is developed for sensor networks, so it assumes that bandwidth is scarce as compared to, say, processing power. To accomplish this goal of reducing bandwidth, directed diffusion, matching, data aggregation, and filters are used. Directed diffusion refers to the idea that each sensor remembers where it got a previous query from and remembers the query itself; this way it has a notion of the direction the query is going. Matching refers to the idea that a request for data carries with it certain requirements, such as this data must be of type so and so, and must be greater than this value; there are a number of operators built in to facilitate this: IS, GT, GE, etc. Data aggregation refers to the idea of nodes collecting the data contained in separate packets and putting it together into one packet to save packet overhead. Filters refer to the idea that a node may choose to process data in a certain way, based on the application. For example, a node could filter duplicate responses to a query. To build a network to detect a submarine, we could place a number of sensors on buoys. Each sensor would be pre-programmed with the it's geographic (X, Y) location. And each sensor would be able to detect the presence of a sub, its depth, and its size. When we wanted to know if a sub was in a certain location, we could issue a class sub_present request with X and Y restrictions using GE and LE. Then each sensor that fit the requirements and detected a sub would respond. We could issue a similar sub_depth request, and on this request we could use a filter to avoid duplicate responses because all sensors should detect the sub at the same depth (i.e. receiving multiple responses wouldn't tell us much). A request for the size of a sub would work similarly, but here we could have some data aggregation. Here we assume that any one sensor can only detect two dimensions of a sub, so we could set up the network to collect all three dimensions before returning the data to the sink. From adam@graphics.cornell.edu Thu Oct 10 12:02:20 2002 Received: from bach.graphics.cornell.edu (bach.graphics.cornell.edu [128.84.247.50]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9AG2Kh28568 for ; Thu, 10 Oct 2002 12:02:20 -0400 (EDT) Received: from envy.graphics.cornell.edu (envy.graphics.cornell.edu [128.84.247.206]) by bach.graphics.cornell.edu (8.12.1/8.12.1) with ESMTP id g9AG2E0k089111 for ; Thu, 10 Oct 2002 12:02:14 -0400 (EDT) Date: Thu, 10 Oct 2002 12:02:04 -0400 (EDT) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 PAPER 35 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Builidng Efficient Wireless Sensor Networks w/ Low-Level Naming. This paper's manin contribution is a new approach to naming and communication based on system attributes and not on location (topology) of the network. Concentrating on using available processing power over many radio transmissions (for power efficiency) the idea is to use as few layers of indirection (limiting lookups and resolutions) to route to physical devices interested in information. This paper accomplishes this by providing a 3 step process for building this network: directed diffusion, matching rules, and filters. Directed diffusion is the method in which paths and data are communicated over the networks. It links the source and sink (note there can be many sources) in communication by having the sink forward "interest" in the source(s) in the direction (topological or geographical?) of them. Intermediate nodes would forward or broadcast these interest messages, caching them for later use and using the info to eliminate routing loops. Matching rules build prefered neighbor schemes and can serve to build a path for which messages traverse. This happnes on the back flood of packets from sources back to a sink. Finally filters eliminate duplicate messages, cache important data or select information of "interest". Does this proposal actually work? There seem to be low delivery rates in this paper. It seems that the idea is good, but the implementation may suffer... Since sensors are generally topologically fixed (just temporally up or down) would it make sense to use some sort of algorithm that builds good paths and works in parallel (or under) the low-level routing propsosed here? The submarine problem: I would build a central node (computer) that takes the input off the sensor network... each sensor on the perimeter would be a "higher" power sonar device which would pick up a submarine entering the field. the rest of the sensors (most likely cheaper, smaller but more dense accross the field) would listen (periodically to save power) for the perimeter messages to "wake-up". That way we could turn the sensors on only when they were needed, trying to precompute the direction, speed and next location of the moving target... each sensor would cache it's collected data until the object was out of range (therefore it could get all of its data in one big transmission) and send the information back to the central node for processing. Each node would remember the last few times it saw the oject (submarine) to try and establish some pattern in which to notify other nodes in the network... Upon receiving a diffusion message (intended for it or another node along the line) it could then "spread the word" itself by sending a directed diffusion message in the correct decision. FInall the sensors would filter information based on previous paths, nearness of message propogration (pass on information from geogrpahically close neighbors and cache it to, cache things that are from intermediate (a short geographic distance, but still far enough that other sensors will repeat this message) and kill messages from far distances (such as far the end of the network).... From ag75@cornell.edu Thu Oct 10 12:06:00 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9AG60h29624 for ; Thu, 10 Oct 2002 12:06:00 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id MAA13295 for ; Thu, 10 Oct 2002 12:05:53 -0400 (EDT) Date: Thu, 10 Oct 2002 12:05:53 -0400 (EDT) From: ag75@cornell.edu X-Sender: ag75@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 35 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII In this paper the authors present a protocol for low-level communication that does not rely on network topological location, which is what most other systems use. Instead, low-level communication is based on names that are relevant to the application. Thus, information such as sensor type and geographic location can be used for naming. The authors claim that this naming scheme is good because it eliminates the overhead of communication required for resolving name binding and it allows for application-specific processing to reduce data transmitted near where data is generated. These are good things, but only for the specific type of networks that the authors want to deal with - sensor networks where bandwidth is limited, energy is expensive, and computing power is comparatively plentiful and inexpensive. The authors admit that their protocol would not work very well for systems such as the whole Internet, where this is not the case. The communication protocol is based on three things: directed diffusion, matching rules, and filters. Directed diffusion is used to transmit information through the network using publishers and subscribers to determine where the data should go. Gradients, which indicate the preferred path, are used to determine what path the data should take. Matching rules identify when data has arrived at its destination, or if intermediate filters should process the data to improve efficiency. The simulation results indicate that the algorithm creates a system that is very congested. The authors claim that the MAC protocol that they use exaggerates this problem, but it remains to be seen how much of this congestion is caused by the naming scheme. On the other hand, the authors found that certain techniques do improve performance: aggregation reduces traffic by up to 42% and nested queries reduces loss rates by 1530%. It seems that making a judgement about about the merits of this algorithm should be done when the improvements that the authors talk about are implemented. In order to build a submarine detection sensor network you would probably use many inexpensive sensors that detect submarine movements. If a suspected submarine is detected more complex sensors can be activated to verify that we really did detect a submarine and detailed info can then be sent to the application. From sc329@cornell.edu Thu Oct 10 12:21:06 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9AGL6h03515 for ; Thu, 10 Oct 2002 12:21:06 -0400 (EDT) Received: from sangeeth.cornell.edu (syr-24-58-36-135.twcny.rr.com [24.58.36.135]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA07910 for ; Thu, 10 Oct 2002 12:21:04 -0400 (EDT) Message-Id: <5.1.0.14.2.20021010115738.031661d8@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 10 Oct 2002 12:21:11 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 35 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Submitted by - Sangeeth Chandrakumar Building Efficient Wireless Sensor Networks with Low-Level Naming In this paper the author discuss a new class of distributed systems where low-level communication does not reply on network topology, but are based on attributes relevant in an external frame of reference. This approach is essential for sensor networks where bandwidth and energy are at a premium. Efficient naming based on pre-defined attributes and geographic locations can achieve fewer levels of naming indirection. In-network processing can be used to make the resource constrained sensor network more effective. This paper looks at the architecture of such a system using attribute-based naming scheme with flexible matching rules and performing localized aggregations of data within the network. This communication architecture is based on three main components: directed diffusion, matching rules and filters. Directed diffusion - the goal of this approach is to establish an efficient n-way communication between one or more source and sinks. Directed diffusion explains this notion of "interests", which is a list of attribute-value pairs that describe a task undertaking some task-specific naming scheme. The interest is propagated from neighbor-to-neighbor towards sensor nodes in the specific region. Also, each sensor node is task-aware. Each sensor that receives an interest remembers which neighbor sent it, and sets up a gradient with it, before redistributing the interests to its neighbors. When a sensor node matching the interests is found, the applications activates its local sensors to begin collecting data. Also the architecture supports preferred paths, by reinforcing certain links. Upon link failures, a negative reinforcement propagates neighbor-to-neighbor tearing down an existing path if it is no longer valid. Thus in directed diffusion, every node acts as an "end" in a sensor network. The data is managed as a list of attribute-value-operation tuples. Attributes and matching rules - Attributes are identified by unique keys drawn from a central authority. A matching rule consists of attribute-value pairs and a set of operations between each attribute-value pair.An operator can be used to specify an actual value of used to compare formal parameters. A one-way match occurs between two attribute sets when all the formal parameters matches successfully with the actual values form the second set. Although matching is reasonably powerful, it is hard to describe all the possible scenarios using attributes and values. Filters - Are application-specific code that run in the network assisting discussion and processing. when invoked, a filter can arbitrarily manipulate the message, cache data and influence how it is send onward or generate a new message in response. Thus filtering helps to get rid of unnecessary communication. In the implementation provided, the filters are call-back procedures that is called when the matching data arrives. The techniques described in the paper uses aggregation and nested queries. In aggregation, a node can receive messages from many neighbors and then apply some aggregate function on it and forward only to one of the nodes, thus reducing many of the redundant transmissions. Also by correlating many queries, the network can substantially reduce the energy consumptions. Overall the paper presents a good idea of using topology-independant low level communication. Submarine sensor application : A network of location-aware sensors should be set up first. Then the application, which needs to be detect submarine sends an interest message(eg. class IS interest, type EQ submarine-detection, interval IS 20s, x GE 100, x LE 400, y GT 200, y LT 500) to its neighbors. This interest message would be locally cached and also propagated to all its neighbors till it hits the sensor which matches the attribute rules. When the interest propagates in the network, a gradient back to the source is created which helps in determining the preferred route. Also by using in-network processing, redundant reply messages can be suppressed. From linga@CS.Cornell.EDU Thu Oct 10 12:51:02 2002 Received: from snoball.cs.cornell.edu (snoball.cs.cornell.edu [128.84.96.54]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9AGp2h11237 for ; Thu, 10 Oct 2002 12:51:02 -0400 (EDT) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g9AGp2D19923 for ; Thu, 10 Oct 2002 12:51:02 -0400 (EDT) Date: Thu, 10 Oct 2002 12:51:02 -0400 (EDT) From: Prakash Linga To: Emin Gun Sirer 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 Traditionally naming was topology dependent to enable low-level communication. Sensor networks is an example of a class of distributed systems where low-level communication is based on application-relevant names and not on network topology. This approach to naming (which is the main contribution of this paper) has two main advantages: Eliminates the overhead required for resolving name bindings; enables in-network data processing and data reduction (as the data is now self-identifying). Note that b/w is a scare resource in sensor networks but processing power is abundant. A simple architecture that uses topology-independent application-friendly naming has been proposed in this paper. There are three components to this architecture: directed diffusion, matching rules and filters. Data in this system is managed as a list of attribute-value-operation tuples. Dissemination of information is taken care of by the directed diffusion component. Attributes are used to identify the data provided or required by a node. Matching rules are used to identify data related to a node. For intermediate nodes these matching rules can identify data so that filters can do some processing on this data. Matching rules can also be used to identify when data has arrived at its destination. Authors implemented three independent versions of diffusion (suggesting that both ideas and code is portable). Instead of the tradional co-ordinator approach for data aggregation an oppurtunistic approach has been suggested in this paper. Sensor selection and tasking is achieved by naming nodes using geograhic attributes. Application-specific filters on intermediate nodes identify and cache data. In-network aggregation and nested queries are examples of in-network processing which reduce load (traffic) and loss rates significantly. Aggregation helps in reducing the amount of data being transferred around. Nested queries are to do with one sensor triggering another under some condition. This approach is significantly better than using a central directory of active sensors which takes care of the triggering a sensor based on input from another sensor. Two approaches to cause one sensor trigger another in a network: user queries initial sensors, and queries the triggered sensor when one is triggered; nested approach where user queries the triggered sensor which then sub-tasks the initial sensors. Performance results showing the efficacy of their approach have been presented. Pros: A simple architecture to support a class of distributed-systems where low-level communication is based on application-dependent names has been proposed in this paper. Nested queries as another in-network processing mechanism has been proposed and its utility demonstrated. The approaches discussed in this paper are important and pertinent to wireless sensor networks. Cons: Performance results are minimal. Scalability is an issue. Comments: Acoustic sensors detect submarines based on reflected sound and so need in-network processing elements which can take the time difference samples and calculate the position and velocity of the submarine. Data values would be the position and velocities of the submarines. Filters could check out the data from other sensors and use it to improve their estimates. From vivi@CS.Cornell.EDU Thu Oct 10 14:53:07 2002 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.10) with ESMTP id g9AIr7h14137 for ; Thu, 10 Oct 2002 14:53:07 -0400 (EDT) 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.5762.3 Subject: 615paper35 Date: Thu, 10 Oct 2002 14:53:07 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF8A@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper35 Thread-Index: AcJwjkVsrPSPTv45Tm+PZ1esdMDRFw== From: "Vivek Vishnumurthy" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g9AIr7h14137 This paper describes a mechanism to build a wireless network of sensors using a topology-independent naming scheme for low-level communications. The goal of this system is to minimize inter-node communication and the power used. The communication between the users and the sensors are handled through "Directed Diffusion". In this system a user (the Sink) who wishes to access some data broadcasts an "Interest", which is a list of pairs of value-attribute parameters (Each pair imposes a restriction on the value the attribute can take). This interest is flooded through the network till it reaches a sensor node(the Source) that matches this interest. This sensor then starts collecting data, and sends this data to the user through the reversed path. A key feature of this system is In-network processing to make the communiaction more efficient. In-network processing is achieved through "Filters" that run on all nodes. The filters suppress the data flowing through the node, eliminating duplicate occurences of the same data. Weaknesses --It seems like a new filter will have to be instantiated (on all nodes) for each data type the filter is required to act on. ie., If there are multiple interests which have been broadcast by users, the data returned by the sensors corresponding to these different interests require different filters to act on them. -- There is no "flow-control" in the system. ie., Each transmission of an interest could result in numerous sensors being selected (the system has no way of restricting the number of sensors selected). Each such sensor then starts sending data without any form of confirmation. This could easily lead to congestion throughout the whole network. (Consider a user at the center of the network originating an interest that matches a large number of sensors that lie at the border of the network) The basic problem here is that a sensor that got selected remains selected forever, and it just starts blasting data without checking to see if its data is really required at the sink. Submarines in an acoustic sensor field: --------------------------------------------------- -- The data values: The interest: type IS submarine-search (assuming that sensors can decide if the object is a sub-marine) -- In-network components: If a filter is used: a filter that matches all data with the above attribute. BUT, if a filter is being used, it means that many submarine sightings could be missed, because the data corresponding to different sightings got routed through the same nodes and only one such sighting was reported by that node. This could be disastrous!!! So, the only in-network componments to be used are the ones that prevent rebroadcasts of the same message, and not the ones that prevent more than one message being routed through a single node.(as a filter does) -- State maintained The preferred-gradient information, ie., next hop information at each node pertaining to each interest.