Chapter 3-directed Diffusion 24th May

CHAPTER 3 DIRECTED DIFFUSION

Directed diffusion is novel communication paradigm for large sensor networks. It supports data-centric routing and application-specific processing inside the network. Directed diffusion is significantly different from IP-style communication where nodes are identified by their end-points, and inter-node communication is layered on an endto-end delivery service provided within the network. Here nodes in the network are application aware as we allow application-specific code to run in the network and assist diffusion in processing messages. It provides robust multi-path delivery, empirically adapt to a small subset of network paths, and achieve significant energy savings when intermediate nodes aggregate responses to queries. Directed diffusion consists of several elements: interests, data messages, gradients, and reinforcements. An interest message is a query or an interrogation which specifies what a receiver needs. Each interest message contains a description of data interested by a user. Typically, data in sensor networks is the collected or processed information of a phenomenon which matches an interest or a request of a user. Such data can be an event which is a short description of the sensed phenomenon. In directed diffusion, data is named using attribute-value pairs. The interest (Figure 3.1) is disseminated throughout the sensor networks to draw named data toward the user. Interest propagation establishes gradients within the network for data propagation. Specifically, a gradient is a direction state created inside each node which receives an interest. The gradient (Figure 3.2) direction is set toward the neighboring node from which the interest is received. Events are propagated toward the interest originators along multiple gradient paths. The sensor network reinforces one or a small number of these paths.

Events

interests Source Sink

Figure 3.1 Interest propagation

Events

Gradients Source Sink

Figure 3.2 Initial gradients set up

Events

Source Sink

Figure 3.3 Data delivery along reinforced path 3.1 INTERESTS AND GRADIENTS The named task description (i.e., the interest) is usually injected into the network at the sink. The sink node creates a task state which will be purged after the time indicated by the duration attribute. For each active task, the sink periodically broadcasts an interest to all its neighbors. Sink periodically refreshes the interest. Every node maintains an interest cache. Each item in the cache corresponds to a distinct interest. Interests do not contain information about the sink but just about the immediately previous hop. An interest entry in the cache consists of several fields. A timestamp field specifies the timestamp of the last received matching interest. The interest entry also contains several gradient fields, up to one per neighbor. Each gradient contains a data rate field, requested by the corresponding neighbor and a duration field. The duration field indicates the approximate lifetime of the gradient and the interest. Gradients are used for data propagation. There are two gradient types: an exploratory gradient and a data gradient. Exploratory gradients are

intended for path setup and repair whereas data gradients are for sending real data. The default gradient type is exploratory. When a node receives an interest, it checks if the interest exists in the cache. If no matching interest exists, the node creates an interest entry and determines each field of the interest entry from the received interest. This entry contains a single gradient toward the neighbor from which the interest was received. Gradient is composed of a value and a direction in which to send events. In our sensor network, the gradient value is the data rate. 3.2 DATA PROPAGATION After a node in the specified region receives an interest, the node tasks its local sensors to collect samples. A sensor node that detects a target searches its interest cache for a matching interest entry. Upon finding the entry, the sensor node computes the highest requested event rate among all its outgoing gradients. The node then tasks its sensor subsystem to generate event samples at this highest event rate. Data can be classified into two types, exploratory and non-exploratory. An event is marked as exploratory if the source has no data gradient or the source has generated no exploratory event within a window of time. Exploratory events are sent along all outgoing gradients whereas non-exploratory events are sent along only data gradients. A node that receives an event from its neighbors also searches its interest cache for a matching interest entry. If no match exists, the event is dropped. If a match exists, the node searches the data cache, associated with the matching interest entry for a matching data entry to detect and to prevent a data loop. If a received event matches a data entry, the event is dropped. Otherwise, the received event is added to the data cache and resent to the node’s neighbors.

A node can also examine its data cache to determine the data rate of received events. To re-send a received event, a node needs to examine the matching interest entry’s gradient list. If gradients are at a data rate that is greater than or equal to the rate of received events, the node may simply send the received event to the corresponding neighbors. However, if gradients are at a lower data rate than others, the node may downconvert to the appropriate gradient. 3.3 REINFORCEMENT FOR PATH ESTABLISHMENT AND PRUNING When sources detect a matching target, they send exploratory events possibly along multiple paths toward the sink. After the sink receives these exploratory events, it reinforces at least one particular neighbor to draw down real data. Events at a higher data rate, allow high quality tracking of targets. The data gradients set up is used for receiving high quality tracking events. . 3.3.1 Path Establishment Using Positive Reinforcement Positive reinforcement is done between source and sink, in response to the exploratory data sent by the source. Path will be established between them. Subsequent transmission data performed along the reinforced path. The reinforcement message is similar to the original interest message except the message type. When the neighboring node receives reinforcement, it notices that it already has a gradient toward the reinforcing node but at lower event rate than the rate specified in this interest. If the new event rate is also higher than that of any existing gradient, the node must also reinforce at least one neighbor. If, this node might select the neighbor from which it first received the latest exploratory event matching the interest. Alternatively, it might select all neighbors from which distinct exploratory events were recently received. Through this sequence of local interactions, at least one data path is established from source to sink.

Whenever one path delivers an exploratory event faster than others, the sink attempts to use this path to draw down data. Therefore, the rate of the exploratory event is a tradeoff parameter between reactivity and energy efficiency. The following Figure 3.4 represents the gradients after positive reinforcement.

Events

Gradients Source Sink

Figure 3.4 Gradients after the sink reinforces the empirically lowest delay path.

3.3.2 Local Repair of Failed Paths So far, the reinforcement from sink was discussed, but intermediate nodes on a previously reinforced path can also apply the reinforcement rules. Such reinforcement by intermediate nodes is very useful to enable local recovery of failed or degraded paths caused by several factors like, node energy depletion, obstacle. Consider in the Figure 3.5, the link quality between the source and node C degrades and events are frequently corrupted.

When C detects this degradation either by noticing that the event reporting rate from its upstream neighbor is now lower or by realizing that other neighbors have been transmitting previously unseen location estimates, C can apply the reinforcement rules to discover a new path. However, it is possible that all nodes downstream of the lossy link may initiate reinforcement procedures. As a result, several data paths are established, and resources are wasted. A possible mechanism to avoid implosion of reinforcements is that C may interpolate location estimates from the received events so that downstream nodes still perceive high quality tracking.

Events

C Gradients Source Sink

Figure 3.5 Gradients after local repair caused by connection quality degradation. 3.3.3 Path Pruning and Negative Reinforcement Positive reinforcement can result in more than one reinforced path. Consider in Figure 3.6, if the sink reinforces neighbor A, but then receives a new exploratory event from neighbor B, it will reinforce B .This path may or may not be completely disjoint from the path through neighbor A. If the path through B is consistently better

Events

B

Gradients Source A

Sink

Figure 3.6 Gradients after several rounds of reinforcement, multiple paths. the sink needs a mechanism to degrade or to negatively reinforce the path through A. One mechanism for negative reinforcement is soft state, to time out all data gradients unless they are explicitly reinforced. With this approach, the sink would periodically reinforce B and cease reinforcing A. The path through A would eventually be degraded to being exploratory gradients. Another approach is to explicitly degrade the path through A by sending a negative reinforcement message to A. In the rate-based diffusion, the negative reinforcement is the interest with the lower data rate. For event-triggered applications, a negative reinforcement message is created instead of using the original interest message with the lower data rate. This negative reinforcement message is similar to the original interest message except the message type. When A receives this negative reinforcement, it degrades its gradient toward the sink. Moreover, if now all its gradients are exploratory, A negatively reinforces its neighbors that have been sending data to it. This sequence of local interactions ensures the path through A is degraded rapidly.

3.4 DIRECTED DIFFUSION PROTOCOL FAMILY The Directed Diffusion protocol includes a family of algorithms. They are twophase pull diffusion, push diffusion, one-phase pull diffusion. 3.4.1 Two-Phase Pull Diffusion If a user in the network would like to track an object in some remote subregion. The user would subscribe to that particular object information, specified by a set of attributes. Sensors across the network publish that information. The user’s application subscribes to data using a list of attribute-value pairs that describe a task using some task-specific naming scheme. Intuitively, attributes describe the data that is desired by specifying sensor types and possibly some geographic region. The user’s node becomes a sink, creating an interest of attributes specifying a particular kind of data. The interest (Figure 3.8) is propagated from neighbor-to-neighbor towards sensor nodes in the specified region. A key feature of directed diffusion is that every sensor node can be task aware, that is these nodes can store and interpret interests, rather than simply forwarding them along. Each sensor node that receives an interest remembers which neighbor or neighbors sent it that interest. To each such neighbor, it sets up a gradient. A gradient represents the direction towards which data matching an interest flows, and the status of that demand, whether it is active or inactive and possibly the desired update rate. After setting up a gradient, the sensor node redistributes the interest to its neighbors. When the node can infer where potential sources might be, the interest can be forwarded to a subset of neighbors. Otherwise, it will simply broadcast the interest to all of its neighbors.

Sensors indicate what data they may generate by publishing with an appropriate set of attributes. They thus become potential sources. As interests travel across the network, sensors with matching publications are triggered and the application activates its local sensors to begin collecting data. Prior to activation the node’s sensors would be in a low-power mode. The sensor node then generates data messages matching the interest. In directed diffusion, data is also represented using an attribute-based naming scheme. Data is cached at intermediate nodes as it propagates toward sinks. Cached data is used for several purposes at different levels of diffusion. The core diffusion mechanism uses the cache to suppress duplicate messages and prevent loops, and it can be used to preferentially forward interests. Cached data is also used for application specific, in-network processing. That is, data from detections of a single object by different sensors may be merged to a single response based on sensor-specific criteria. The initial data message from the source is marked as exploratory and is sent to all neighbors for which it has matching gradients. The initial flooding of the interest, together with the flooding of the exploratory data (Figure 3.10), constitutes the first phase of two-phase pull diffusion. If the sink has multiple neighbors, it chooses to receive subsequent data messages for the same interest from a preferred neighbor, that is, the one which delivered the first copy of the data message. The sink reinforces (Figure 3.11) the preferred neighbor, which, in turn reinforces its preferred upstream neighbor, and so on. The sink may also negatively reinforce its current preferred neighbor if another neighbor delivers better lower latency sensor data. This negative reinforcement propagates neighbor-to-neighbor, removing gradients and tearing down and existing path if it is no longer needed. Negative reinforcements suppress loops or duplicate paths that may arise due to changes in network topology.

After the initial exploratory data message, subsequent messages are sent only on reinforced paths. The path reinforcement, and the subsequent transmission of data (Figure 3.12) along reinforced paths, constitutes the second phase of two-phase pull diffusion. Periodically the source sends additional exploratory data messages to adjust gradients in the case of network changes, due to, node failure, energy depletion, or mobility, temporary network partitions, or to recover from lost exploratory messages. Recovery from data loss is left to the application. While simple applications with transient data, such as sensors that report their state periodically, need no additional recovery mechanism, so retransmission scheme for applications that transfer large, persistent data objects is being developed[1].

Network Sink

Source Interest

Figure 3.7 Sink sends interest message in to network

Network Sink

Source Interest

Figure 3.8 Source receiving interest message

Exploratory data

Network

Sink

Source

Figure 3.9 Source sends exploratory data

Exploratory data

Network Sink

Source

Figure 3.10 Sink receiving exploratory data

Reinforcement

Network Sink

Source

Figure 3.11 Sink sending reinforcement message

Data

Network

Sink

Source

Figure 3.12 Source sending data to sink 3.4.2 Push Diffusion Push diffusion is same as two-phase pull diffusion, here the roles of the source and sink are reversed. Sinks become passive, with interest information kept local to the node subscribing to data. Sources become active; exploratory data (Figure 3.14) is sent throughout the network without interest created gradients. When exploratory data arrives at a sink a reinforcement message is generated and it recursively passes back to the source creating a reinforced gradient (Figure 3.15), and non-exploratory data (Figure 3.16) follows only these reinforced gradients. Push is not a good match for applications with many sources continuously generating data since such data would be sent throughout the network even when not needed. A benefit of push diffusion compared to two-phase pull is that it has only one case where information is sent throughout the network (exploratory data) rather than two (interests and exploratory data).The following figures represents the operations in push diffusion.

Network Sink

Source Exploratory data Figure 3.13 Source sends exploratory data

Exploratory data

Network Sink

Source

Figure 3.14 Sink receiving exploratory data

Reinforcement

Network Sink

Source

Figure 3.15 Sink sending reinforcement message

Data

Network Sink

Source

Figure 3.16 Source sending data to sink

3.4.3 One-Phase Pull Diffusion One-phase pull is a subscriber-based system that avoids one of the two phases of flooding present in two-phase pull. The sink sends interest (Figure 3.17) messages that disseminate through the network, establishing gradients. When an interest arrives at a source it does not mark its first data message as exploratory, but instead sends data (Figure 3.18) only on the preferred gradient. The preferred gradient is determined by the neighbor who was the first to send the matching interest, thus suggesting the lowest latency path. Thus one-phase pull does not require reinforcement messages, and the lowest latency path is implicitly reinforced.

Network Sink

Source Interest

Figure 3.17 Source receiving interest message sent by sink

Data

Network Sink

Source

Figure 3.18 Source sending data to sink

By comparison, with two-phase pull uses several control messages to forwad data, which has been reduced in one phase pull. Here the sink sends the interest messages and accordingly the data is sent on the preferred gradient.