DATA DISSEMINATION
Data dissemination is the process by which queries or data are routed in the sensor network. The data collected by sensor nodes has to be communicated to the BS or to any other node interested in the data. The node that generates data is called a source and the information to be reported is called an event . A node which is interested in an event and seeks information about it is called a sink . Traffic models have been developed for sensor networks such as the data collection and data dissemination (diffusion) models. In the data collection model, the source sends the data it collects to a collection entity such as the BS. This could be periodic or on demand. The data is processed in the central collection entity.
Data diffusion, on the other hand, consists of a two-step process of interest propagation and data propagation. An interest is a descriptor for a particular kind of data or event that a node is interested in, such as temperature, intrusion, or presence of bio-agents. For every event that a sink is interested in, it broadcasts its interest to its neighbors and periodically refreshes its interest. The interest is propagated across the network, and every node maintains an interest cache of all events to be reported. This is similar to a multicast tree formation, rooted at the sink. When an event is detected, it is reported to the interested nodes after referring to the interest cache. Intermediate nodes maintain a data cache and can aggregate the data or modify the rate of reporting data. The paths used for data propagation are modified by preferring the shortest paths and deselecting the weaker or longer paths. The basic idea of diffusion is made efficient and intelligent by different algorithms for interest and data routing.
12.3.1 Flooding
In flooding, each node which receives a packet broadcasts it if the maximum hop count of the packet is not reached and the node itself is not the destination of the packet. This technique does not require complex topology maintenance or route discovery algorithms. But flooding has the following disadvantages [5]:
• Implosion: This is the situation when duplicate messages are sent to the samefnode. This occurs when a node receives copies of the same message fromfmany of its neighbors.
• Overlap: The same event may be sensed by more than one node due to overlappingfregions of coverage. This results in their neighbors receiving duplicatefreports of the same event.
• Resource blindness: The flooding protocol does not consider the availablefenergy at the nodes and results in many redundant transmissions. Hence, itfreduces the network lifetime.
12.3.2 Gossiping
Gossiping is a modified version of flooding, where the nodes do not broadcast a packet, but send it to a randomly selected neighbor. This avoids the problem of implosion, but it takes a long time for a message to propagate throughout the network. Though gossiping has considerably lower overhead than flooding, it does not guarantee that all nodes of the network will receive the message. It relies on the random neighbor selection to eventually propagate the message throughout the network.
12.3.3 Rumor Routing
Rumor routing is an agent-based path creation algorithm [6]. Agents, or “ants,” are long-lived entities created at random by nodes. These are basically packets which are circulated in the network to establish shortest paths to events that they encounter. They can also perform path optimizations at nodes that they visit.
When an agent finds a node whose path to an event is longer than its own, it updates the node’s routing table. Figure 12.4 illustrates the working of the rumor routing algorithm. In Figure 12.4 (a), the agent has initially recorded a path of distance 2 to event E 1. Node A ’s table shows that it is at a distance 3 from event E 1 and a distance 2 from E 2. When the agent visits node A , it updates its own path state information to include the path to event E 2. The updating is with one hop greater distance than what it found in A , to account for the hop between any neighbor of A that the agent will visit next, and A . It also optimizes the path to E 1 recorded at node A to the shorter path through node B . The updated status of the agent and node table is shown in Figure 12.4 (b).
When a query is generated at a sink, it is sent on a random walk with the hope that it will find a path (preestablished by an agent) leading to the required event. This is based on the high probability of two straight lines intersecting on a planar graph, assuming the network topology is like a planar graph, and the paths established can be approximated by straight lines owing to high density of the nodes. If a query does not find an event path, the sink times out and uses flooding as a last resort to propagate the query. For instance, as in Figure 12.4 (c), suppose a query for event E 1 is generated by node P . Through a random walk, it reaches A , where it finds the previously established path to E 1. Hence, the query is directed to E 1 through node B , as indicated by A ’s table.
12.3.4 Sequential Assignment Routing
In [7], a set of algorithms which performs organization and mobility management in sensor networks is proposed. The sequential assignment routing (SAR) algorithm creates multiple trees, where the root of each tree is a one-hop neighbor of the sink.
Each tree grows outward from the sink and avoids nodes with low throughput or high delay. At the end of the procedure, most nodes belong to multiple trees. An instance of tree formation is illustrated in Figure 12.5. The trees rooted at A and B, two of the one-hop neighbors of the sink, are shown. Node C belongs to both trees, and has path lengths of 3 and 5, respectively, to the sink, using the two trees. Each sensor node records two parameters about each path through it: the available energy resources on the path and an additive QoS metric such as delay.
No comments:
Post a Comment