From: Long Hai Vu Sent: Thursday, February 16, 2006 8:57 AM To: Indranil Gupta Cc: Long Vu Subject: cs598ig review 02/16 REVIEW PAPERS CS598IG-Spring06 Name: Long Vu A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks In this paper, authors present the overview of eight routing protocols, then describe and compare their characteristics. The pros and cons of these protocols are also discussed. In addition, they evaluate these protocol based on a set of parameters such availability of routing information, routing philosophy, signaling traffic generated, quality of service support, etc. The experimental results shows that the performance of on-demand routing protocols are better than that of table-driven ones. In the context of table-driven routing protocols, up-to-date routing information from a node is broadcasted to the whole network. This may cause traffic problem as the high communication between nodes. It is obvious that if the wireless network is high mobility, the number of packets sent to keep nodes status consistent floods the network traffic. Moreover, keeping routing information of all nodes in the same network wastes memory. This approach seems also not scalable as a node could not hold all routing information of all nodes in a very huge network. Could we use the idea of Kelips to manage nodes in the wireless network? That is, dividing set of nodes into affinity group (hash location of node to get the affinity group as node is mobile). Each node will keep some contacts of foreign groups. Then, if there is a request, node knows the destination and forwards the request to either corresponding node (if in the same affinity group) or contact (if in different group). Gossiping with constant bandwidth messages could be used to propagate mobility of a node. In this sense, we do not need to keep the whole routing information of all nodes in the network, but we could localize where the destination is to advance routing process. For this approach, we may need to keep the routes between groups as the wireless is limited in distance. To reach a specific group, we need to travel through some intermediate groups. Routing over groups is “cheaper” than that of nodes. Directed Diffusion: A scalable and Robust Communication Paradigm for Sensor Networks In this paper, authors present the idea of directed diffusion for coordination among distributed sensor nodes. To request data, requestor sends interests for named data, then the data matching this interest would be fetched and sent to the requestor. This paradigm is data centric which is generated by sensor node. Moreover, they state in the paper that by using directed diffusion they could achieve robust multi-path delivery, empirically adapt to small subset of network paths and significant energy saving. Directed diffusion has several promising features such as data-centric dissemination, reinforcement-based adaptation to the empirically best path, and in-network data aggregation and caching. The most novel contribution of this paper is representing initial step into the design of diffusion mechanism in which two concepts interests and gradients play very important role. However, they also mentioned in the paper that directed diffusion itself does not limit to one particular usage. That is, there are many other usages in which nodes could propagate data in the absence of interests. From: Mehedi Bakht Sent: Thursday, February 16, 2006 8:55 AM To: Indranil Gupta Subject: 598ig review 02/16 Title: Directed diffusion: A scalable and robust communication paradigm for sensor networks Summary: The paper presents a new data dissemination paradigm for sensor networks call “Directed Diffusion”. It consists of several elements. All data is named using attribute-value pairs. A sensing task is disseminated throughout the sensor network as an “interest” for named data. This dissemination sets up “gradients” within the network designed to “draw” events (data matching the “interest”). Once the sensors perform the task and obtain required data, they send it back to the originator of the “interest” along multiple paths. The sensor network tries to identify the better paths and reinforce them by trying to send data at a higher rate through those better paths. The authors present experimentation results from a small scale implementation of directed diffusion in a sensor network used for animal tracking. The results were compared with flooding and omniscient multicast scheme – and direction diffusion outperformed them in terms of energy efficiency and had an average delay comparable to omniscient multicast. Comments: I felt that the authors have left too many things as “subject of future work”. For example, the concept of reinforced path is one of the main features of directed diffusion strategy. But in current design, the frequency of reinforcement of paths is very reactive to changes in path quality. Whenever the sink finds a path delivering an event faster than others, it will attempt to reinforce that particular path. Such a strategy may result in a lot of waste of resources. Another example is the issue of implementing negative reinforcement - no particular strategy was proposed. In their experiment, the authors chose to negatively reinforce a neighbor from which no new events have been received in 2 seconds. This choice of 2 seconds it both conservative and energy inefficient – as admitted by the authors themselves. But no concrete alternative was suggested. If negative reinforcement is not done in an intelligent way, there may be too many “reinforced” or high data-rate paths in network – resulting in a lot of energy consumption. Title: A review of current routing protocols for ad hoc mobile wireless networks. Summary: This paper provides a survey of existing routing protocols for ad hoc mobile wireless networks. The protocols were divided into two broad categories – table driven routing protocols and source-initiated (demand-driven) routing protocols. The table-driven category comprised of Destination-Sequenced Distance-Vector Routing (DSDV), Clusterhead Gateway Switch Routing (CGSR) and The Wireless Routing Protocol (WRP).On the other hand, source-initiated On-Demand Routing included Ad Hoc On-Demand Distance Vector Routing (AODV), Dynamic Source Routing (DSR), Temporally Ordered Routing Algorithm (TORA), Associativity-Based Routing (ABR), and Signal Stability Routing(SSR). After providing a brief description of all the above mentioned protocols, the authors presents a comparison of the protocols separately under each category. A comparison between the two categories was also presented in the paper. Comments: Evaluation of the protocols under two different category does not seem that intuitive to me. After all, the protocols compete with each other – not only with those that fall under the same category. I would have preferred to see a set of common criteria against which all the protocols can be evaluated. If any of this protocol is to be implemented in a modified manner in a network of sensors or such small devices, then we will also need an evaluation of energy requirements of different protocols. From: ercanucan@gmail.com on behalf of Ercan Ucan Sent: Thursday, February 16, 2006 2:56 AM To: Indranil Gupta Subject: "598ig review 02/16" Directed Diffusion ---------------------- Problem Addressed: In this paper, a new data dissemination paradigm called 'directed diffusion' for coordination to perform distributed sensing of environmental phenomena in a group of small and cheap nodes that have the ability to compute and communicate. Directed diffusion is a data centric approach which means that all the communication that takes place is for named data. All the nodes involved in such directed diffusion based network are application aware which enables to diffusion make empirical/intelligent decisions in sense of path selection and caching. The motivation of the paper is achieving robustness, scaling and energy efficiency. Approach Taken & Comments: The paradigm of directed diffusion is data-centric. That means that data generated by sensor nodes is named by attribute-value pairs. Basically, a node requests data by sending interests(queries) for the named data. Then, as the data matches the interest, it is drawn down towards the sink node, the node that sent the interest. Another important idea here is that all communication is local. This is different from IP style communication where nodes are identified by their end-points, and inter-node communication is layered on an end-to-end delivery service provided within the network. Also, intermediate nodes in directed diffusion can aggregate the data(by combining the reports from several sensors) in order to make the information more accurate. Again, interest, data propagation and aggregation are determined by localized interactions using message exchanges between neighbors or nodes within a vicinity. However, in the paper, authors did not talk about whether there is a specific membership maintenance within the network or not. I think it would be nice if they provided some basic info about how neighborhood is constructed, maintained and etc. After the interest is disseminated throughout the network, gradients are set up. These gradients are designated to draw the data that matches the interest to the sink node. Then the matching data start flowing towards the originators of interests along multiple paths. The sensor network reinforces one or a small subset of these paths. I think the reinforcement(favoring a path) is a really cool idea in terms of experimental adaptation and energy saving. Reinforcement and negative reinforcement are beneficial ideas which also adds fault tolerance(i.e. repairing the path failures) to the system. However, since all the communication is local in the system, the path found might not be the globally best path or energy saved might not be the theoretical maximum energy save possible in the system. Still, in my opinion, this communication style is a good design choice since it really helps the system to scale. As design choices are concerned, I think that the interest propagation scheme, which is currently the flooding, can be improved or replaced with some other type of broadcasting. The first thing I could think of is to use gossip based dissemination algorithms. However, since this is a real-time like application that has strict time constraints(like interest interval etc.) gossip type dissemination might not be the best solution. As future work, I think authors should consider experimenting with the system more and probably try come up with new(in addition to animal tracking) instantiations of the directed diffusion approach. As another future work, they are considering to cull the similarities in some elements of interest propagation into a diffusion substrate at each node so that sensor network designers can use a library of interest propagation, data processing and reinforcement techniques for different types of tasks. Overall, I think there are bunch of good ideas presented in the paper, simple and working well. A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks ----------------------------------------------------------------------------------------------- Problem Addressed: This article examines several routing protocols designed for ad hoc networks. It first describes each protocol and then compares their various characteristics. Basically, two categories of ad hoc routing protocols are presented: Table-driven and Source-initiated (or demand-driven). Article provides an overview of eight different routing protocols by presenting their characteristics and functionality and then evaluates them on certain parameters which I will mention in the next section. Findings & Comments: Table-Driven routing protocols were discussed first in the paper. These kinds of protocols aim to maintain consistent and up-to-date routing information from each node to every node in the network. It is required by such protocols that each node maintains one or more tables to store routing information and they respond to changes in network in order to maintain a consistent network view. I think we can name such protocols as proactive since they are in business all the time trying to have valid and most correct information about the network status. Protocols in this category differ from each other by the number of necessary routing-related tables and the methods by which changes in the network structure are broadcast. The table-driven routing protocols that were discussed go as follows: Destination Sequenced Distance Vector Routing; based on the classical Bellman-Ford routing mechanism. Improvements include freedom from loops in routing tables. Clusterhead Gateway Switch Routing; is similar to the previous protocol but differs from that in the type of addressing and network organization scheme employed. It is a clustered multi-hop mobile wireless network with several heuristic routing schemes. This protocol uses DSDV as the underlying routing scheme and therefore has pretty much the same amount of overhead as DSDV. The Wireless Routing Protocol; aims for maintaining routing information among all nodes in the system. Each node must keep four tables which are distance table, routing table, link-cost table and message retransmission list (MRL) table. It makes use of 'hello' messages which I think is the same thing with heart-beat messaging scheme. Also, solves counting to infinity problem in a novel way. Then source-initiated on-demand routing discussion goes: I think these types of protocols can be names as reactive since these routes are built on demand. Ad Hoc On-Demand Distance Vector Routing; was built on DSDV algorithm that was previously described. AODV is an improvement since it minimizes the number of required broadcasts by creating routes on a demand basis. Mainly uses a path discovery algorithm. Dynamic Source Routing; is based on source routing. Mobile nodes are required to maintain route caches. These caches should contain the source routes of which this mobile node is aware. As new routes are learned, entries in the caches of related mobile nodes are updated. Has two major phases that are route discovery and route maintenance. Temporally Ordered Routing Algorithm; is a highly adaptive loop-free distributed routing algorithm. It uses link reversal and performs three basic functions which are route creation, maintenance and erasure. Associativity Based Routing; is a totally different routing mobile routing protocol that is free from loops, deadlock and packet duplicates. Also it defines a new routing metric for ad hoc networks which is called degree of association stability. Signal Stability Routing; is another different approach in source routing. Unlike the previous algorithms, this algorithm has different criteria in selecting the paths. It selects the routes that have stronger connectivity and mainly consists of two main sub protocols that are dynamic routing protocol and static routing protocol. After this, the comparison sections start. The main idea that we get from the comparisons is that, there is no best routing algorithm among those presented. It all depends on the situation and configuration and needs of the mobile ad hoc wireless network. This is actually what I would expect. Because, if there was a best algorithm among these, it would be the winner and the papers would not be talking about the loser algorithms any more and at the end there will be only one algorithm in the literature. From my point of view, this article can be a nice book chapter. It has a lot of instructive information in it. However, I do not think that this article makes important/novel contributions to the literature of routing algorithms for ad hoc networks. As a result, I should state that, personally, this paper did not get me excited while reading. -- Ercan Ucan - eucan2@uiuc.edu Graduate Student Computer Science Department University of Illinois at Urbana-Champaign ------------------------------------------------------------ From: Hussam Hasan Abu-Libdeh Sent: Thursday, February 16, 2006 2:20 AM To: Indranil Gupta Subject: 598ig review 02/16 The two papers i'd like to review are: 1. Direct Diffusion. 2. Locating and Bypassing Routing Holes in Sensor Networks. Directed Diffusion: This paper proposes a method for sensor nodes to exchange data in a distributed sensor network. Basically, the idea is that if we represent the data in (attribute, value) pairs, we can then have the data sort of diffuse from the center to the requesting node. This approach proposes that intermediate nodes also cache the data which increases energy efficiency for later rounds (no need to transfer the data through alot of nodes in next times). The way that directed diffusion works, is that the sensing task spreads through the network when the requester (the "sink" node) shows its interest in a named-pair at that point it sets up gradient paths in the network to help "draw" the data towards it. The named-pairs contain the following information: * Type / Category of search result * Instance: the actual piece of data that the sink is looking for * Location: the logical location of the sink within the sensing grid * Intensity: (effectively: how bad does the sink want that data!) * Confidence: the sink's confidence of the availability of the data at other nodes * Timestamp: when the event was initiated * Interval: the frequency of sending back data * Duration: the duration of the search * Rect: the logical rectangle in the sensor network layout that contains the affected nodes The paper discusses how the sink node should broadcast its requests with different rates and attribute values (varying as time progresses) in order to create a good enough "force" to pull the data towards it. The paper then goes on to describe how should responding nodes propagate the data. But the interesting part in my opinion is the concept of "Reinforcement". So, basically when the sink starts receiving low data-rate results (in the beginning), it tells some of its neighbors to only forward higher data rate data only. The sink might also need to do negative reinforcement in case it discovers data-paths that are constantly better. The paper then concludes with some experimental results of a tested scenario. Locating and Bypassing Routing Holes in Sensor Networks: So the problem that this paper is addressing is that in many greedy algorithms for routing packets in a sensor network we might get the packets "stuck" in a local minimum along the path and thus never reach its destination. This path discusses an algorithm to route those packages "around" those holes. Packets get stuck at a node whose all of its 1-hop neighbors are actually further away than the ultimate target. And thus, by a greedy routing algorithm, the packet would never get routed from that node. The paper defines two types of stuck nodes: Week stuck nodes, and strong stuck nodes (which are slightly different ;-) ). Next the algorthim of BOUNDHOLE which finds holes in the graph (stuck nodes) and basically the routing proceeds to avoid the return of that algorithm. As most papers, this paper also discusses applications of these algorithms. From: Mike Earnhart [mearnhart@gmail.com] Sent: Thursday, February 16, 2006 12:17 AM To: Indranil Gupta Subject: 598ig review 02/16 Michael Earnhart CS 598 IG 02/16/2006 Summary Directed Diffusion and Locating and Bypassing Routing Holes in Sensor Networks In the Directed Diffusion paper the authors emphasize the need to reduce the energy cost of reporting events in a wireless sensor network. The motivation is to provide a robust, scalable, and energy efficient data dissemination protocol for a system that is clearly energy bound. The difficulties are in the reliability of the protocol to deliver messages given high failure rates. In order to satisfy the requirements they deviated from the standard IP-style communication scheme where inter-node communication is layered on an end to end delivery service within the network. Their system provides end to end communication via multi-path delivery which empirically adapts to subsets of paths that are strong. They use specific terminology such as naming referring to the enumeration of the data which allows for aggregation, interest which specifies topics that need to be reported, and gradients for acquiring data matching interests. The describe in sufficient detail the interaction between these components and how their system will deal with failures, multiple sinks, and various other variables. The strength of this paper is the generic approach allowing Directed Diffusion to extend to many applications and remain effective. Also the attention to very important factors such as resilience, and scalability provide a significantly more important development. The results the produce specifically the 60% less energy dissipation than omniscient multicast were very impressive. Again their analysis of node failure seemed sufficient and proved applicability in hostile environments. The issues I have with this protocol are with their assumptions. First they mention "power-conserving processors clocked at several hundred Mhz" which I do not see happening in the near future. Several hundred Mhz would be 3 8 hundred Mhz and I do not know of any motes that are clocked so fast, also considering that power increases linearly with frequency I doubt this will happen soon. Other issues such as the discussion about asymmetric links and how it could play havoc on their system was not sufficient. They could have used at least a couple simulations to provide some data on what asymmetric links would do to their system. In Locating and Bypassing Routing Holes in Sensor Networks the focus was on defining a stuck node, and developing the boundhole algorithm to route around voids. The fundamental problem that is studied is the "local minimum phenomenon" in geographic forwarding. They also develop a rule known as TENT to identify stuck nodes. The algorithms section is the main focus of the paper and provides proofs of many concepts their boundhole algorithm relys on. In this section they further define a stuck node and provide an additional type: strong stuck nodes. They formally define the TENT rules for identifying the nodes and through a few more proofs are able to show that they can find holes and route around them. The strengths of this paper lye in the extensive proofs and development of their algorithms. Also their common sense approach to debunk old protocol such as those that utilized the right-hand rule. Clearly this provides non-optimal routing if a hole is always circumnavigated counter-clock wise and I appreciated the quick and obvious way it was presented. As for weaknesses in this protocol they rely on interesting yet significantly non-trivial information such as geographic positioning or other positioning services. This as far as I understand is not a completely solved problem hence making this protocol nearly impossible to implement effectively. I often find it a tad strange to put the cart before the horse but it is apparently accepted in the research community. In addition the size of networks they are proposing do not exist in any significant numbers and hence the motivation seems rather weak. The reason networks of such magnitude are not plentiful if the exist at all is because there are much large problems than routing around voids such as the very simple intra-flow interference problem. Again I find they are solving a less fundamental problem and see less value in their solution because of it. From: Ravishankar Sathyam Sent: Wednesday, February 15, 2006 11:51 PM To: Indranil Gupta Subject: 598ig review 2/16 Ravi Sathyam A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks. Summary: This paper goes through various routing protocols for ad hoc wireless networks. There are two such types of protocols – table-driven routing and source-initiated routing protocols. Table-driven routing protocols force each node to maintain one or more tables to store routing information. They maintain network topology by constantly propagating updates throughout the network. Some of the table-driven routing protocols are as follows: Destination-Sequenced Distance-Vector Routing – This protocol is based on the Bellman-Ford routing mechanism described in /Flows in Networks/ by Ford and Fulkerson. The way it works is that each node in the network maintains a routing table in which all of the mobile nodes maintain a routing table containing all the possible destinations within the network and the number of hops to each destination. These entries are marked with sequence numbers which help distinguish stale routes from new ones. Updates are transmitted throughout the network, either in the form of full dump packets carrying all available routing information (and which can require multiple network protocol data units) or incremental packets, which are used to relay information that has changed since the last full dump. New route broadcasts have address of destination, number of hops required to reach it and the sequence number of the information received regarding the destination (the route labeled with the most recent sequence number is always used). Clusterhead Gateway Switch Routing – While, DSDV routing has a flat network, CGSR is a clustered multihop network with several heuristic routing schemes. One can then have a cluster head controlling a group of ad hoc nodes for each cluster. The selection of the cluster head is known as Least Cluster Change (where cluster heads change only when two cluster heads come into contact, or when a node moves out of contact of all other cluster heads). This scheme also uses DSDV as the underlying routing scheme between cluster heads and gateway nodes (which basically connect to other cluster heads). So, each node now has a cluster member table (where each node in the network is mapped to a cluster-head), so that if the node wants to send a packet, it first sends it to the next cluster-head hop, which forwards it to another cluster-head based on the destination, and so forth. Wireless Routing Protocol – Each node in the network maintains four tables – 1) Distance Table, 2) Routing Table, 3) Link-cost Table, and 4) MRL table. The MRL table contains which updates need to be retransmitted and to whom. Link changes are spread throughout the network in the form of update messages (which are sent between neighboring nodes and contain a list of updates). Nodes also learn about their neighbors by the receiving of acknowledgments and other messages. Source-Initiated On-Demand Routing creates routes only when desired by the source node. Some of the Source-Initiated On-Demand Routing protocols are as follows: Ad Hoc On-Demand Distance Vector Routing – The AODV routing protocol is an improvement over DSDV since it minimizes the number of required broadcasts by creating routes on demand. So, if a source node wants to send a message to a destination node but it does not have a valid route to the destination, then it starts a path discovery process to locate the other node (this is done by broadcasting a route request packet to its neighbors, which forwards it to its neighbors and so on, thus establishing a valid link on-demand). Dynamic Source Routing – In the DSR protocol, the mobile nodes maintain route caches that contain the source routes that the mobile is aware of. As new routes are discovered, the entries in the route cache are updated. This protocol consists of two phases – route discovery (which is initiated by broadcasting a route request packets) and route maintenance (which is achieved through sending and receiving route error packets and ACK messages). Temporally Ordered Routing Algorithm – The TORA provides for localization of control messages to a small set of nodes near the occurrence of a topological change. So to do this, each node maintains routing information to adjacent nodes. This protocol consists of three main functions – route creation (done by establishing a DAG in a manner similar to the query/reply process in LMR), route maintenance and route erasure (done by broadcasting a clear packet throughout the network). Associativity-Based Routing – This scheme defines a new routing metric (degree of association stability). Routes are selected based on this metric. Each node has associativity tables,which correspond to the connection stability of a node (demonstrated by each node periodically sending a beacon to signify its existence). ABR has three phases – route discovery (done by broadcasting a query and await-reply cycle), route reconstruction (partial route discovery, invalid route removal, route updates, etc), and route deletion (done by route deletion broadcast for all nodes to update their routing tables). Signal Stability Routing – This scheme selects routes based on the signal strength between nodes as well as a node’s location stability. Hence, routes with stronger connectivity always have higher preference. This SSR can be divided into two protocols – a Dynamic Routing Protocol (which helps maintain the signal stability table and routing table) and the Static Routing Protocol (which uses the routing table to route packets). The paper then goes on to give a brief comparison between the various types of Table-Driven Protocols as well as the Source-Initiated On-Demand Routing Protocols. Moreover, current challenges for ad hoc networks, such as multicast, QoS support, power-aware routing and location-aided routing are also mentioned. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Summary: This paper explores directed diffusion as a coordinated way to sense environmental phenomena. Essentially, a sensor network can be designed such that a user can contact a sensor and ask to sense something – this task is conveyed to other sensor nodes using hop-by-hop wireless communication. Each node can ask its sensors to keep probing if anything meaningful is detected, this data is routed back towards the task originator. Essentially, this paper shows that one way to disseminate meaningful data throughout the network is to use directed diffusion. In this technique, task descriptions have key-value pairs that help describe it. This task description constitutes an interest which is injected into the network through some node (known as the sink). For each task, sinks periodically broadcast interest messages to neighbors (the timestamp attribute increases to counter for unreliability in the network). Each node in the network then has an interest cache. These interests diffuse throughout the network since each node may decide to re-send the interest to some subset of its neighbors (who think that this message is originating from the sending node rather than from some sink somewhere). Choosing such a subset is really application-specific and has tradeoffs of increased energy and overhead versus greater diffusion. If a sensor node detects a target, it searches its interest cache for a matching interest entry. If a match is made, then the node will compute the highest requested event rate amongst all of its outgoing gradients (gradients specify both a data rate and a direction to send events) and asks its sensors to generate event samples at this highest rate. The source then sends to each neighbor for whom it has a gradient an event description. Each node that receives this data message checks to see if its in its own interest and data caches (to prevent loops). If there is no match, or if there is a matching data cache entry, the message is dropped. Otherwise, its forwarded to other neighbors. Once sources start detecting a matching target, they send low-rate events to the sink. Once the sink receives this low-rate events, it reinforces a neighbor in order to pull higher data-rate events (reinforcements are done by sending the same interest message with higher data rates). However, one needs a scheme of negative reinforcement too, for another path can come up with a new event and have a consistently better path. One method of negative reinforcement is to re-send the interest with lower data rates. This same scheme applies for multiple sinks. The paper then goes on to evaluate the directed diffusion scheme in comparison with omniscient multicast. It is observed that directed diffusion has dissipated 60% of the amount of energy dissipated by multicast. In addition, a lot of energy expenditure comes solely from the reinforcement schemes. Also, it is observed that directed diffusion has comparable delay to omniscient multicast. Also, under node failures in the directed diffusion scheme, event delivery ratio, average delay statistics degrade gracefully, while energy dissipation actually improves in some cases (possibly to due failure of some high-quality energy-sapping links). Comments: In the section about broadcasting a newly received interest, it would be helpful to optimize the interest broadcast (currently the new interest will be broadcasted to all neighbors, but this seems energy-sapping) From: Muyuan Wang [mwang2@uiuc.edu] Sent: Wednesday, February 15, 2006 11:08 PM To: Indranil Gupta Subject: 598ig review 02/16 Locating and Bypassing Routing Holes in Sensor Networks Summary: The paper points out that, for sensor network, the most promising routing scheme is greedy forwarding. However, geographic forwarding suffers from the local minimum phenomenon. Thus it gives a definition of 'stuck nodes', where packets may get stuck in greedy multi-hop forwarding. In order to deal with different networks, two types of stuck nodes are defined, 'weak stuck node' and 'strong stuck node'. They suit for applications where routing destinations are always some nodes or not always some nodes, respectively. They develop the TENT rule for each node in the network, to test whether a packet can get stuck at that node. At the same time, it defines the 'hole' in the sensor network, argues that the information about hole will be very useful in some applications. They use different algorithms to discover holes, and an algorithm named 'BoundHole' is used to build routes around holes. Possible usages in applications such as routing, interesting region identification, and supporting path migration are discussed. Comments: As said in the paper, this paper initiates the research on studying the structures in sensor networks, from a view point of graph theory, maybe. The basic ideas are very clearly expressed, although the math will take me much much longer time to understand. I think, following this way, we may not only find more applications based on the notions defined in this paper, but also explore other important features or characteristics which are useful for research and applications. For example, is there a 'highway' or 'bottleneck effect' in the sensor network? What structures can cause these? How can we define them? In a word, this paper is excellent in innovation and it brings us another way of thinking. ----------------------------------------------------------------- Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Summary: This paper aims to solve the problem of coordination between nodes in distributed sensor networks. A scheme named directed diffusion is designed. Directed diffusion consists of several elements: 1. The naming scheme 2. Interests and gradients 3. Data propagation along multiple paths 4. Reinforcement First, data is named using attribute-value pairs. According to the naming, a sensing task is disseminated throughout the sensor network as an 'interest'. The dissemination sets up 'gradients' within the network to draw events. After that, events are propagated towards the originators of interests. The sensor network will 'reinforce' one of the paths. The evaluation is performed on a location tracking sensor network. It is claimed that directed diffusion has the potential for significant energy efficiency. Even with relatively optimized path selection, the results are better than idealized traditional data dissemination scheme such as omniscient multicast. Comments: I am a little skeptical about the naming scheme. How is this kind of naming scheme chosen? As mentioned in the paper, the choice of naming scheme may impact performance of a diffusion algorithm. However, I guess that in most of tasks of current sensor networks, it is difficult to find such a clear and simple scheme. This issue should be discussed more, in order to make the good results more convincing. From: Maifi Khan [maifi.khan@gmail.com] Sent: Wednesday, February 15, 2006 10:17 PM To: Indranil Gupta Subject: 598ig review 02/16 Name: Mohammad Maifi Hasan Khan Course: CS598IG Netid: mmkhan2 Date: Feb 16, 2006 Title: Directed diffusion for wireless sensor networking. Summary: Directed diffusion is a datacentric communication paradigm which uses efficient localized interactions. In this paradigm a user uses 'interest' message where data is named using attribute-value pairs. A receiver creates a gradient towards the immediate neighbor who sends the message. It uses broadcasts periodically for interest propagation. A source reports any observed event if it matches with any stored interests and attach a confidence level and intensity of the observed samples for quality reason. It uses reinforcement to establish a single path with better quality data and negative reinforcements to truncate multiple paths. They exports network routing API and filter API for implementation. Network routing API uses publish/subscribe technique. Filter API is to perform various operation as aggregation on data as it moves through network. They showed that transmitting cost using flooding is significantly higher than proposed technique. Criticism: 1. To specify interest they uses time stamp. In a large sensor network, it is not trivial to synchronize clocks and it can result clock skew problem. 2. As nodes are geographically scattered, to broadcast a interest message to a node who is outside the sensing region is not meaningful. Future work: 1. As nodes are geographically scattered, to broadcast a interest message to a node who is outside the sensing region is not meaningful. For establish path for routing purpose, it can use some other optimized mechanism. It will reduce the uses of transmission power. 2. Sometime it is useful to be able to query about past events. Nodes can cache observed events even though there is no current interest. In that case nodes can query about past events. Title: Locating and bypassing routing holes in sensor networks. Summary: This paper proposes a technique to perform routing in the presence of holes in sensor networks. Holes can be created for many reasons such as power failure, physical damage, obstacles causing transmission blockage etc. To solve the local minimum phenomenon , they classify nodes as stuck nodes where nodes can possibly can get stuck and describe TENT rule to test each node if it is a stuck node or not. To detect a hole the algorithm Boundhole starts from a stuck node and build a boundary by traversing counterclock wise and it terminates when the original packet again reaches the starting stuck node. The algorithm is repeated for every node the packet visited. They show how to use information about holes for efficient path migration in case of moving objects. One of the interesting application of this algorithm is to find the regions of interest which is often the main motivation for deploying sensors in the first place. Criticism: 1. In case of non uniform transmission range, there algorithm is not guaranteed to work to delivery a packet and it may fail though there is a path. 2. Hidden terminal problem can also influence the algorithm. Future work: 1. As holes can be created as time progresses and also can be eliminated by deploying additional sensors, the algorithm has to run periodically. There is a tradeoff how frequently such an expensive algorithm can be run as it costs a lot of power. Further work needs to be done to define the applicability of such an algorithm 2. Scalability of this algorithm also needs to be tested. As network grows, how long it takes to terminate and for real time systems like moving target detection this convergence time can have a major impact on the applicability of the algorithm. From: Raghu Kiran Ganti Sent: Wednesday, February 15, 2006 6:15 PM To: Indranil Gupta Subject: 598ig review 02/16 Review for Sensor net routing (Feb. 16th 2006) --------------------------------------------- Paper title: A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks The above paper can be only summarized as it is already a summary and does not present any new idea or protocol for routing in ad hoc networks. Hence, only the summary sub-header is present without the other usual subsections of main ideas, strengths, weaknesses and future work. Summary: -------- The paper is a simple summary of ad hoc routing protocols in existing literature and covers various such protocols. In particular the paper classifies the ad hoc routing protocols into two categories, which are table driven and on-demand. The table driven techniques attempt to maintain consistent, up-to-date routing information from each node to every other node in the network. Several table based approaches exist and differ in the various tables maintained for achieving the routing! On the other hand, on-demand routing is source-initiated, which creates routes only when desired by the source node. We observe that both techniques have their advantages and disadvantages. The table driven approaches perform better than the on-demand techniques in terms of latency, as the latency overhead in establishing a route by the on-demand protocols is high. But, given that most mobile nodes are limited in battery and bandwidth, on-demand is a better option when it comes to conserving bandwidth and power. A few examples of the table driven approaches include DSDV, CGSR, and WRP. DSDV (Destination-Sequence-Distance-Vector routing) is based on the bellman-ford algorithm to find the shortest paths in a graph. DSDV adds loop freedom and routing tables to maintain the routes in the network. CGSR (Cluster Gateway Switch Routing) differs from DSDV in the type of addressing and network organization scheme. It is not an entirely flat network (like DSDV), because it has clusters and gateways which manage a set of ad hoc nodes and help in routing. Another variation is the WRP, where route information is maintained between all nodes, but the tables used are different. A few examples of the on-demand approaches include AODV, DSR, TORA, ABR, and SSR. Each of them maintains local information, which is used globally to obtain a desired route, when required. For example, Ad Hoc On Demand Distance Vector (AODV) routing protocol maintains the neighbor information in tables and obtains a route by systematically flooding the network for a given destination. DSR is quite close to AODV, it differs in the fact that routes discovered are cached. DSR is not a pure on-demand scheme like AODV. TORA - Temporally Ordered Routing Algorithm, operates in a highly dynamic mobile environment, where nodes maintain the routing information about adjacent nodes. TORA depends on timing and requires the network to be synchronized! ABR - Associativity Based Routing, maintains an associativity index for each neighboring node, a higher associativity index indicates that the neighboring node is stationary, and a lower index indicates higher mobility. SSR - Signal Stability Routing, measures the signal strength of the neighboring nodes and uses it to maintain routes. ******************************************************************************************** Paper title: Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Summary: -------- The paper presents a new data dissemination paradigm for sensor networks, which is the first of data centric paradigm for programming sensor networks. Data generated by sensor nodes is named by an attribute-value pair. A node requests data by sending interests to named data and the data matching this interest is propagated back to the node requesting it. Sensor nodes cannot be addressed with IP like addresses, as these networks are data centric! Hence, the idea of the paper is to use data centric routing. Main ideas: ---------- The main idea of the paper is data centric routing, where requests for data are diffused to the region where data is being generated and then the data is sent back to the source node. There are 2 basic ideas introduced, interest and gradient. Interests indicate what the source node requires, it includes information such as type, are, duration and rate. The gradient specifies a value and direction for the data to be ``pulled'' to the source node. Every node receiving an interest will have a reverse pointer to the node generating the interest and this is annotated with the gradient. To reduce un-necessary propagations, the initial exploratory rate is set to 1 and it is increased when the route gets better. To establish the fact that certain routes are better, reinforcement is used, which is a learning automata based scheme. Strengths: --------- The concept of addressing the nodes in an ad hoc sensor network through data centric scheme is the first of its kind. This paper is a precursor to all the data centric schemes presented in sensor network literature. The completely local scheme, which does not use any source information when diffusing the interest is good for scalability. Weaknesses: ---------- Although, we see that a completely localized protocol is good for scalability, also observe that with information regarding the source, we can route the data back more efficiently. The paper is not very thorough and the protocol spans several protocol layers in a generic OSI stack. It is not clear whether this scheme is a routing protocol, transport layer protocol or application! Future work: ----------- Several data centric paradigms such as TAG, TinyDB are based on the concepts presented in this paper. A complete set of data centric query based programming paradigms have been built on the directed diffusion concept. From: Praveen Jayachandran Sent: Wednesday, February 15, 2006 5:59 PM To: Indranil Gupta Subject: cs598ig review 02/16 CS598IG - Reviews, 02/16/2006 Praveen Jayachandran A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks ------------------------------------------------------------------------- This paper examines routing protocols for ad hoc networks and compares them based on a set of parameters, and identifies the differences between them. The eight protocols considered are classified into two classes, namely, table-driven protocols and source initiated on-demand routing. The table-driven protocols considered are Destination-Sequenced Distance-Vector Routing (DSDV), Clusterhead Gateway Switch Routing (CGSR), and Wireless Routing Protocol (WRP). In the on-demand routing class, they examine Ad Hoc On-Demand Distance Vector (AODV), Dynamic Source Routing (DSR), Temporally Ordered Routing Algorithm (TORA), Associativity-Based Routing, and Signal Stability Routing. A comparison of routing protocols between and across the two classes is presented. Comments: 1. Although a comparison of the routing protocols is presented, there are no conclusions drawn. The paper should have given directions as to which protocol should be used for what kinds of applications and under what considerations. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks ---------------------------------------------------------------- Directed Diffusion is a data-centric communication paradigm, where nodes are addressed through attributes (or data they contain), rather than using Internet-style unique identifiers. This enables several desirable properties such as localized interactions, scalability, energy efficiency, and simplicity. A node that requires data (such as a query for events in a sensor network) diffuses (floods) an interest to the network. Gradients are set up from the data sources towards the node that issued an interest for the data, and data flows along the gradient. A low exploratory rate is used initially. The gradient to the neighbor which provided the data is reinforced, so that in future, that neighbor will be chosen. In time, this will result in identifying a good route and now data can be transmitted at an increased rate. Each intermediate node forwards interests and data to its neighboring nodes without any knowledge about the source or the sink, yielding localized interactions. Intermediate nodes can select empirically good paths and save energy using caching and in-network processing. Negative reinforcement mechanisms can be employed to quickly recover from broken routes. Comments: 1. This paradigm shifts routing to the application domain, resulting in a cross-layer design. This helps in identifying energy efficient paths and will be extremely useful when the application requires periodic data collection. 2. This paper inspired a lot of future research work that aimed at viewing the sensor network as a database. 3. Directed diffusion is shown to outperform the optimal omniscient multicast. This is because they are compared in rather unfair grounds. Directed diffusion suppresses duplicated on common links of multicast trees, while omniscient multicast does not. If both of them do not suppress duplicates, of course omniscient multicast would outperform directed diffusion.