Methods for Routing Improvement in WSNs

Methods for Routing Improvement in WSNs As was concluded on the first chapter of the work, one of the best routing protocols, which is less energy-intensive and in the same time have other good conditions, like mobility, multipath usability, effective data aggregation, and so on, is Directed-Diffusion. Thus, Directed-Diffusion is chosen as a base protocol for reaching the goals of the dissertation. The importance of the energy-efficiency characteristic in sensor networks has directed many works on Directed-Diffusion and several solutions have been proposed trying to carry out energy efficiency in this paradigm. These solutions suggest various changes in the stages of the paradigm. Directed-Diffusion [84] is one possible realization of publish/subscribe for a wireless sensor network. It is mostly concerned with scalability issues and tries to find solutions that do not depend on network-wide properties like globally unique node identifiers. But rather, the goal is to find solutions that purely rest on local interactions. The most prevalent (albeit not the only) service pattern is subscription to data sources that will publish data at a selectable rate over a selectable duration. The aim of designing the Directed-Diffusion is efficiency in energy consumption, thereby increasing life expectancy network. In order to reduce energy consumption uses, this method uses two ways of compression and processing information within net. But it has limitation because of using the huge diffusion which cause that the resulting overload in this algorithm became too much. In the Directed-Diffusion, a node forms a gradient during the propagation toward all neighbors. These gradients are paths which are used for further data transferring. However, they provide limited information (e.g. a node can recognize the nearest neighbor only) and as a result Directed-Diffusion has some limitations such as traffic collection production which has inefficiency of energy. Directed-Diffusion is very suitable for some of usages, but instead, for some of usages it will work weakly, especially in usages where there are many receivers and references, and when the receivers are related to each other, the volume of traffic data increases. When the sink wants to choose one of the neighbors to strengthen their own path, it selects a neighbor which the first will receive a packet from it. For example, a node can determine which of its neighbors is the nearest. In this method, each node has limited information from its neighbors and has no enough attention for choosing the neighbors without attention to full or empty. Also, it doesn’t consider level of energy and power of neighbor in order to send the main station, which causes some limitations, such as increasing the traffic and reduction of effective relations in network. In the situations when the number of sources is too much, the sink selects only that path of neighbors which give to it the discovered data. But this is not optimum way of data compression in network. Of course, in case that a node can cover information of several sources, it can do an effective work in compression of data in the network. Description of base routing protocol algorithms There are a number of protocol variants that are optimized for different situations and Directed-Diffusion is actually more a design philosophy than a concrete protocol [84]. We start here with the original and basic variant, the â€Å"two phase pull† as is considered in [84]. Two-phase pull Directed-Diffusion: Data distribution in this scheme starts by nodes announcing of their interests in certain kinds of named data, specifying their interests by a set of attribute-value pairs [12, 26] in the publish/subscribe parlance. This corresponds to a subscription to data. These interest messages are distributed through the network and in the simplest case they are flooded. It would be trivial to set up converge cast tree with each node remembering the node from which it has first received the interest message from a given sink, given such an interest flood. Interests to different data and/or from different sinks would result in separate trees being constructed. But such a simple tree construction is faced with a serious impediment. In the absence of globally unique node identifiers, a node in the network cannot distinguish whether different interest messages originated at different data sinks. Thus, it would require the construction of separate converge cast trees to inform all sinks of published data or whether these packets are owing to the same sink and have simply traveled via different paths. This predicament is highlighted on Figure 2.1. For a node X there is, at first, only a single option – remember all neighbors from which an interest message has been received to, later on, once data has been published, forward the actual data to all th ese neighbors. In the Directed-Diffusion terminology, this is the setup of a gradient toward the sender of an interest. For each type of data received in an interest, each node stores in a gradient cache a separate set of gradients, potentially one for each neighbor. Fig. 2.1 Inability of network node X to distinguish interest messages from a single or multiple sinks Unlike the simple parent–child relationship in a tree, gradients often will be set up bidirectional between two neighbors, as both neighbors forward interest messages. In addition, a gradient is not simply a direction, but it also contains a value. This value represents, in a sense, the usefulness or the importance of a given link. It can constitute different semantics depending on the concrete application that Directed-Diffusion is supporting. A typical example is the rate with which data is transmitted over a given link (recall that directed diffusion is geared toward the support of periodic publications of data). Initially, these gradient values are the same for each neighbor. They are modified in the course of the protocol execution. Also, these gradients are initialized to low values, which are used to explore the network. Data can be propagated, once the gradients are set up, even with only preliminary values. A node that can contribute actual data from local measurements becomes a source and starts to send data. It uses the highest rate of all its outgoing gradients to sample and send data. An intermediate node, in the simplest case, would forward all incoming data messages over all its outgoing gradients, potentially suppressing some of the data messages to adapt to the rate of each gradient. However, this simple scheme results in unnecessary overhead in networks like the one shown in Figure 2.2, where data messages are needlessly repeated due to the presence of loops in the gradient graph. Just checking the originator of these data messages is again not feasible because of the lack of globally unique identifiers. Hence, the data cache is introduced, each node stores, for each known interest, the recently received data messages. If the same message comes in again, irrespective of from the same or di fferent originators, it is silently discarded. Figure 2.2 also shows that two copies of the same data message would be delivered to the sink, constituting no negligible overhead. The gradient values, or more specifically the rates associated with the gradients, provide a lever to solve this problem. One idea is to try to limit redundancy in the received data. A neighboring node that contributes new data messages (which cannot be found in the data cache) should be preferred over neighbors that only provide stale copies, or rarely provide new data, or appear to have high error rates, or are otherwise unattractive. This â€Å"preference† of a neighbor can simply be mapped onto the rate of a gradient. A node can reinforce a neighbor by simply sending a new interest message to that neighbor asking for a higher rate of data transmission. If this new, required rate is higher than the data rate which an intermediate node is currently receiving, it in turn can reinforce its best neighbor with this higher rate. In the end, the reinf orcement will percolate to the source(s) of the data messages. The no reinforced gradients can be maintained as backups, they can be actively suppressed, or they can be left to die out in the sense of soft state information. Fig. 2.2 Multiple intersecting paths’ data cache necessity in Directed-Diffusion Thus, these two phases, first, flooding the interest messages to explore the network and then again having information flow from the sink toward the sources during reinforcement, along with the fact that the sinks initiate the â€Å"pulling† of data, explain the classification of this variant as a â€Å"two-phase pull† procedure. These mechanisms of interests, gradients, and reinforcements constitute the pivotal mechanisms in Directed-Diffusion. It is worthwhile to reiterate that all of them are indeed strictly local, dispensing with the need for globally unique identifiers. Reference [62] contains further details how these mechanisms result in loop-free operation and how paths can be maintained in the presence of node or link failure (essentially, the reinforcement mechanism automatically adapts to the new topology). It should also be emphasized that, in principle, Directed-Diffusion in the form described here can handle both multiple sources and multiple sinks of data. The local rules result in a correct but not necessarily optimal flow of data messages. Push diffusion – supporting few senders and many receivers: As Directed-Diffusion represents both an interface/naming concept [63] and a concrete routing implementation (the one described above), it stands to reason that different routing protocols supporting the same interface have been developed. One such alternative routing protocol is the push diffusion [64], which is intended for many receivers and only a few senders. A typical example is an application where sensor nodes cross-subscribe to each other to be informed about local events but where the amount of actual events is quite low. In such a situation, two-phase pull would perform purely, as the sinks would generate a lot of traffic trying to set up (exploratory) gradients. This problem is solved by reversing the roles. Instead of the sinks sending out interests, sources send out exploratory data (i.e. flood it since no gradients exist yet). Once data arrives at interested sinks, they will reinforce these gradients, a nd then, data at higher rate will only follow these reinforced paths. The flooding overhead is justified since the event detection rate of sources is quite small to begin with. One-phase pull – supporting many senders and few receivers: Similar to the above-described push diffusion, pull diffusion [64, 84] is a specific routing protocol for the Directed-Diffusion interface. This one is geared toward many senders and a small number of receivers. As the name indicates, one-phase pull eliminates one of the flooding phases of two-phase pull, which constitute its major overhead. More precisely, interest messages are still flooded in the network (in the absence of recasting options) but the interest messages set up direct parent–child relationships in the network between a node and the node from which it first receives an interest message. As a result, a tree is formed in the network. This is only possible using (e.g. randomized) flow identifiers in the interest messages, which is feasible only for a small number of messages. Moreover, one-phase pull more strongly depends on link symmetry than does two-phase pull. Directed-Diffusion assisted by topology control: Reducing the flooding overhead inherent in two-phase pull [84] is a promising means for improvement. In particular, passive clustering fits well with Directed-Diffusion. In â€Å"Handziskiet at al† [66] is shown how this combination works in detail. In particular, the passive clustering structure is constructed on the fly with the distribution of interest floods. This result not only in better energy efficiency but, particularly, the percentage of actually delivered events is considerably improved, mostly because of easing the contention on the MAC layer. In this sense, this work highlights the need for a careful adjustment of at least three different protocol layers, those are the MAC, topology control, and data-centric routing – for an efficient wireless sensor network. A low-level-naming mechanism: In this approach, content-based addressing is integrated with Directed-Diffusion routing [65, 84]. In a nutshell, in Directed-Diffusion a sink node issues an interest message, specifying a set of attributes to describe the desired data. This message is disseminated into the network. The nodes that can produce sensor data matching the interest are called source nodes. A data packet generated by a source node travels through intermediate nodes to the sink. An intermediate node stores the interest along with (set of) possible upstream neighbors in the interest cache. Upon receiving a data packet, the intermediate node searches its cache for an interest matching the data and forwards the data packet to the associated upstream neighbor. Rumor: A variant of Directed-Diffusion, called Rumor Routing, has been proposed by Braginsky and Estrin [45, 84]. The proposed algorithm is applicable in situations where flooding would generate too much traffic and geographic information is not available. It is a logical compromise between query flooding and event flooding. The key idea is the routing of the queries to the nodes that have detected a particular event rather than flooding the entire network for retrieving information about the occurring events. In order to do this, the algorithm employs particular packets, called agents which are generated by nodes that have observed events. These latter are added to local tables on the nodes, called events tables. In order to disseminate information about local events to distant nodes, agents travel the network. Nodes use their events tables to respond to queries generated by the sinks. In this way, communication overhead is reduced by reducing floods. Gradient based routing: Gradient based routing is a slightly changed version of Directed-Diffusion [83, 67]. When flooding first interest messages, nodes keep the number of hops and calculate parameter called the height of the node. That is the minimum number of hops to the sink. The gradient on path is considered as the difference between of a node’s height and of its neighbor’s height. Then the data messages are forwarded on a path with the largest gradient. This solution uses some techniques such as data aggregation and traffic spreading in order to balance the traffic uniformly, which helps in balancing the load on sensor nodes and increases the network lifetime. GEAR: GEAR (Geographic and Energy Aware Routing) is a diffusion algorithm belonging to the Directed-Diffusion algorithms family [68, 84]. It relies on localized nodes, and provides savings over a complete network flood by limiting the flooding to a geographical region and using energy aware neighbor selection heuristics. To do this, each node in the network keeps two costs called estimated cost and learning cost, which are a combination of remnant energy and distance to destination. These costs are used to route a packet to and within the target region. In case there is no closer neighbor to the target region (a hole), one of the neighbors is picked to forward the packet based on the cost function. Within a region, packets are forwarded using the recursive geographic flooding. In that case, the region is divided into four sub regions and four copies of the packet are created. This process continues until reaching regions with one node (the destination). Scatter Web is an open and fle xible platform for implementing sensor networks [69]. This solution discusses the solar aware routing in sensor networks. The proposed energy aware routing algorithm is similar to Directed-Diffusion and uses the same terminology. However, nodes employed are not only battery-driven and instead, can be powered by solar power (Fig. 2.3). The key idea is to route packets via solar driven nodes since they can receive and transmit packets without consuming battery energy. The algorithm extends the Directed-Diffusion paradigm by adding several fields to the standard Directed-Diffusion headers (number of battery-driven nodes, number of solar-driven nodes, strategy, sequence number and so on). In order to save more energy, the solution proposes a scheme to prevent routing loops. Fig. 2.3 Geographic and Energy Aware Routing