In the second in a four part series on implementation of wireless sensor networks the authors of “Ad hoc wireless networks,” discuss the various protocols required for reliable and fast 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.
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 :
Implosion: This is the situation when duplicate messages are sent to the same node. This occurs when a node receives copies of the same message from many of its neighbors.
Overlap: The same event may be sensed by more than one node due to overlapping regions of coverage. This results in their neighbors receiving duplicate reports of the same event.
Resource blindness: The flooding protocol does not consider the available energy at the nodes and results in many redundant transmissions. Hence, it reduces the network lifetime.
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.
Rumor routing is an agent-based path creation algorithm . 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 below illustrates the working of the rumor routing algorithm.
on image to enlarge.
Figure 12.4. Rumor routing.
In Figure 12.4 (a), the agent has initially recorded a path of distance 2 to event E1. Node A’s table shows that it is at a distance 3 from event E1 and a distance 2 from E2. When the agent visits node A,it updates its own path state information to include the path to event E2.
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 E1recorded 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 E1 is generated by node P. Through a random walk, it reaches A, where it finds the previously established path to E1. Hence, the query is directed to E1 through node B, as indicated by A’s table.