Chapter 2 Literature Survey 24th May

CHAPTER 2 LITERATURE SURVEY A wireless sensor network (WSN) is a wireless network consisting of spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations. The development of wireless sensor networks was originally motivated by military applications such as battlefield surveillance. However, wireless sensor networks are now used in many civilian application areas, including environment and habitat monitoring, healthcare applications, home automation, and traffic control. Each node of the sensor network consists of three subsystems, the sensor subsystem which senses the environment, the processing subsystem which performs local computations on the sensed data, and the communication subsystem which is responsible for message exchange with neighboring sensor nodes. While individual sensors have limited sensing region, processing power, and energy, networking a large number of sensors gives rise to a robust, reliable, and accurate sensor network covering a wider region. The nodes cooperate and collaborate on their data, which leads to accurate sensing of events in the environment. The most important operation in a sensor network are data dissemination, that is, the propagation of data/queries throughout the network, and data gathering, that is, the collection of observed data from individual sensor nodes to a sink. 2.1 DATA DISSEMINATION Data dissemination is the process by which queries or data are routed in the sensor network using directed diffusion protocol. The data collected by the sensor nodes has to be communicated to any other node interested in the data.

Traffic models have been developed for sensor networks such as data collection and data dissemination models. In the data collection model, the source sends the data it collects to a collection entity. This could be periodic or on demand. The data is processed in the central collection entity. Data diffusion 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. For every event the sink interested in, it broadcasts its interest to its neighbors and periodically refreshes the 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. 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. 2.1.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 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 network lifetime

2.1.2 Gossiping Gossiping is a modified version of flooding, where the nodes do not broadcast a packet, but sends 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. 2.1.3 Rumor Routing Rumor routing is an agent-based path creation algorithm [6]. Agents 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 the nodes that they visit. When an agent finds a node whose path to an event is longer than its own, it updates the nodes routing table. When the agent visits a node, it updates its own path state information to include the path to an event. When a query is generated at a sink, it is sent on a random walk with the hope that it will find a path 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 use flooding as a last resort to propagate the query.

2.1.4 Sequential Assignment Routing The sequential assignment routing 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. 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. This allows a node to choose one path from among many to relay its message to the sink. The sequential assignment routing algorithm chooses a path with high estimated energy resources, and provisions can be made to accommodate packets of different priorities. A weighted Qos metric is used to handle prioritized packets, which is computed as a product of priority level and delay. The routing ensures that the same weighted Qos metric is maintained. Thus, higher priority packets take lower delay paths, and lower priority packets have to use the paths of greater delay. Sequential assignment routing algorithm minimizes the Qos metric over the lifetime of the network. The sink periodically triggers a metric update to reflect the changes in available energy resource after some transmissions. 2.1.5 Directed Diffusion Directed diffusion is a communication paradigm used in sensor networks. It is data centric in that all communication is for named data. All nodes in directed diffusion based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths and processing data in-network. It includes following diffusion algorithms, two phase pull diffusion, one phase pull diffusion, push diffusion. Two phase pull diffusion algorithm includes two phases. The initial flooding of the interest, together with the flooding of the exploratory data, constitutes the first

phase. The path reinforcement, and the subsequent transmission of data along reinforced paths, constitutes the second phase. Push diffusion algorithm is similar to that of two phase pull, where the roles of sources and sink are reversed. The source will send an exploratory data, after path reinforcement is set and data is sent. One phase pull diffusion algorithm avoids one of the two phases of flooding present in two phase pull. Here interest is disseminated through the network and the data is sent. The above algorithms are used in routing the data in sensor networks. For reliable data delivery to the sink, we are in need of transport layer protocols. 2.2 TRANSPORT PROTOCOLS FOR SENSOR NETWORKS The transport layer protocols for wireless sensor networks should support reliable message delivery, efficient energy usage, congestion control. The need for reliable message delivery and congestion control suggest that WSNs should have a transport layer, just as 802.3 and 802.11 networks need a transport layer. However, WSNs add a new constraint—energy efficiency. To prolong the lifetime of a WSN, an ideal transport layer needs to support reliable message delivery and provide congestion control in the most energy efficient manner possible. 2.2.1 Tcp/Ip TCP/IP has been used successfully in wired 802.3 and wireless 802.11 networks and has been discussed as a possible transport layer for WSN [14]. Certain attributes, such as IP addressing for individual nodes, unnecessary header overhead for data segments, no support for data centric routing, a heavyweight protocol stack, and an end-to-end reliability scheme that attributes segment losses network congestion, of TCP/IP; however, they make it unsuitable for use in WSNs.

TCP/IP may not be suitable for standard sensor nodes in a WSN, but may still be used at the sink to communicate with other remote endpoints. Sensor nodes with high robustness, such may use TCP/IP as a virtual sink or proxy between the WSN and the remote host to reduce the number of retransmissions of a data segment by less powerful sensor nodes. 2.2.1.1 Loss Detection/Recovery TCP/IP, by default, uses an ACK-based end-to-end reliability mechanism; however, an end-to-end reliability mechanism is not appropriate for sensor networks, given their high loss rates due to signal attenuation and path loss arising from low power radios and channel contention from dense sensor deployment. The probability of receiving an errored packet increases exponentially with the increase in the number of hops on a WSN. 2.2.2 Pump Slowly, Fetch Quickly (PSFQ) Pump Slowly Fetch Quickly (PSFQ) [7] is a transport layer protocol, designed specifically to meet the unique resource challenges presented by WSNs. Here the data is pumped slowly from a root node into the network. Sensor nodes that experience loss can recover data segments by fetching them quickly from their immediate neighbors on a hop-by-hop basis. To reduce signal overhead, nodes signal the loss of segments using negative acknowledgement, rather than acknowledging each received packet. PSFQ is based on the assumption that a WSN will generate light traffic most of the time; thus, it is designed to avoid loss due to instability of the wireless medium, rather than loss due to network congestion. As such, it does not offer any active congestion control scheme. PSFQ is designed for tasks that require reliable delivery of all message segments. Its focus is on the transport of binary images, such as new sensor control programs used for sensor retasking in the field. Since PSFQ expects low network traffic and does not provide any active congestion control scheme it may not be efficient for reliable transport of data.

2.2.2.1 Loss Detection/Recovery Reliability in PSFQ is achieved with a negative acknowledgement (NACK)based quick fetch mechanism. Loss is detected using gap detection. Each injected message has a sequence number in the message header. If a receiving node determines a gap in sequence number, it begins aggressively broadcasting NACK messages to try to recover the lost message before the injection interval is exceeded, and the next packet is sent. In case a downstream node needs to quickly recover a lost packet, a NACKbased scheme requires upstream nodes to buffer messages that have been sent downstream. A sending node near the receiving node caches message segments it forwards; this recovery scheme is called “local recovery” PSFQ’s assumption that all intermediate nodes store all the segments they forward. A negative acknowledgement gap detection scheme leaves holes at the beginning and end of messages potentially undetected. Detecting dropped segments at the beginning of messages can only be done if one message segment is received downstream. If a message consists of only a single segment, and that segment is somehow dropped on the way downstream, it will not be detected. Likewise, a node cannot detect the loss of the last data segment in a transmission, since it will not be able to tell if the data segment has been lost or has not reached it yet. To address the shortcomings of gap detection, PSFQ uses a “proactive fetch” [7] scheme that allows it to set a timer that starts from the receipt of the last message until the next message is received. This continues while the total size of the received data segments is less than the file size specified in the header field of the inject message. If no message is received from any upstream neighbor before the timer times out, then a downstream sensor node will manually generate and broadcast a NACK event to actively try to recover the segments that were presumably lost. PSFQ will buffer messages received if a gap is detected until the lost data segments have been recovered.

2.2.3 Reliable Multi-Segment Transport (RMST) RMST is a reliable transport layer for WSNs. RMST is meant to operate on top of the gradient mechanism used in directed diffusion. RMST adds two important features to directed diffusion 1. Fragmentation and reassembly of segments, and 2. Reliable message delivery. One of the most intriguing features of RMST is that it is an extension of directed diffusion that can be applied to a sensor node providing reliable data delivery. It includes caching mode and non-caching mode, which provides hop by hop recovery and end to end recovery. 2.2.3.1 Loss Detection/Recovery Mechanisms RMST employs a Negative Acknowledgement (NACK) gap detection to detect and recover lost messages. However, RMST makes no guarantee of in-order message delivery; rendering loss detection is particularly difficult since it is difficult for sensor nodes to determine whether gaps are caused by out-of-order delivery or lost messages. To help assuage this problem RMST creates a “hole map” for detected gaps and assigns a “watchdog” timer to generate an automatic NACK for any segment that has not been received in the timer interval. Multiple fragment numbers can be combined into a single NACK, to cut down on the network traffic generated during message recovery. RMST will be the more energy efficient protocol compared to that of PSFQ, since it can handle out-of-order delivery of segments and has the ability to signal several missing segments with one NACK.