From: Thadpong Pongthawornkamol Sent: Thursday, September 23, 2004 2:24 PM To: Indranil Gupta Subject: 598ig review 09/23 Sensor network routing A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks As stated as its name, this paper, written by Royer and Toh, presents and compares a set of ad hoc wireless network routing schemes which are currently used. There are two subdivision of ad hoc wireless routing schemes, table-driven and source-initiated (demand-driven) protocol. In table-driven protocol, each node has to maintain network status, member nodes, etc. These tables are periodically synchronized between nodes and their neighbors in order to acquire network consistency. On the other hand, Source-initiated (demand-driven) protocols do not require member nodes to possess such information. However, in order to route a message, an arbitrary node need to perform route request mechanism, which will take more time than table-driven protocols. Generally speaking, a route will be created only when a node wants to send a message. Route discovery mechanism and route maintenance mechanism are required for these algorithms. There are three approaches of table-driven protocols presented in this paper. DSDV routing protocols requires full dump messages flooding for infrequent global status updates and Incremental messages for small changes occur in network. CGRS is the modification of DSDV with hierarchical structure consisting of clusters and gateways. Such idea makes CGRS scalable but it also introduces critical points of failure at cluster nodes. WRP require each node to maintain four tables and use hello packet as a heartbeat signal, which prevents any nodes to go to low-power sleep mode. It also avoids routing loops by consistency checks in each node. There are five approaches of source-driven protocols presented in the paper. AODV is built on DSDV with minimized number of broadcasts. It uses broadcasting request and chain reply to form a route in path discovery process. Once a route is discovered, it can be maintained until a failure is detected in the route. Unlike AODV, DSR generates multiple paths in path discovery process with more overhead. It also supports asymmetric route, which is not available in AODV. TORA is a highly adaptive loop-free approach which can be used in dynamic network. It uses link reversal algorithm, which is suited for dense networks. It also provides multiple routes. However, it needs global clock such as GPS, which prevents scalability. ABR scheme routes packets based on associativity stability. It prefers routes on static nodes which are not likely to move. Such approach makes its route long-lived, resulting in fewer route reinitiations in case of link failures. It is also duplication-free. However, periodical beacon advertisements incur energy and traffic overheads. SSR evolves from ABR, but it uses route based on signal strength. Dynamic part of SSR monitors signal strength between a node and its neighbors and generate strength signal information, which is used by static part of SSR to flood route request through strong links. First incoming route request will be replied from the destination. In conclusion, the paper gives a clear overview and comparison between currently available wireless ad hoc routing schemes. However, it is lacking of proven performance evaluation to support its ideas, which will be very useful for future ad hoc routing applications. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks A paper proposed Intanagonwiwat et al. introduces interest-based information dissemination protocol in sensor networks. The term direct diffusion is defined as a hop-by-hop communication, which each node forms into gradient and transfer events, information specific to any interests that were originated by human operators. In direct diffusion scheme, any data is named by attribute-value pair. A task is given as an interest to an arbitrary sensor node in the network. The first node received an interest is then called a sink node. The sink node then broadcasts and refreshes the interest to other nodes. Each node maintains interest caches for several interests. The concept of aggregation is used to reduce data redundancy by allowing a node to group some of its interest caches into single interest. When a node receives an interest from a neighbor, it sets up a cache entry with a gradient pointed to that neighbor. The node then forward the interest it received to other neighbor nodes based on some policies, such as flooding, geographic routing, or history based routing. Once an interest is forwarded to sensor nodes which are located in the specified area, such nodes will perform as sources to gather events, information that match the interest, and distribute events along with predefined gradient. Data will be collected by observing waveforms from the target. Intermediate nodes then forward the message toward a sink with a rate specified in events. Reinforcement can be used by a sink as a kind of acknowledgement to events and a demand to retrieve events at a higher rate. Moreover, reinforcement can be used by intermediate node to repair failed or degraded paths. A set of evaluations is performed to give a comparison between direct diffusion, flooding, and omniscient routing approaches. The metrics used in the evaluation are dissipated energy, average delay, and event delivery ratio. The results yield direct diffusion’s better performance then the others. Another test is conducted to measure the performance of direct diffusion under network failures. It gives an acceptable result for all three metrics. In conclusion, direct diffusion dissemination protocol achieves a certain level of energy efficiency and reliability. It is recommended to use as a mechanism in sensor network. However, there are some problems to be considered, such as congestion handling in multiple sources or sinks network. Locating and Bypassing Routing Holes in Sensor Networks In this paper, Fang et al. introduce a technique to deal with local minimum problem encountered in greedy forwarding strategies, techniques widely used in sensor networks. In greedy forwarding strategies, an arbitrary sensor node can send messages to any destination in sensor network by sending messages to the 1-hop neighbor that is closer to the destination node than the sender itself. Such technique performs good result in sensor network routing with two major exceptions. First, every sender node has to possess locations of all nodes in the network so that it can calculate next hop destination. Second, such routing mechanism introduces local minimum problem, which is the situation that there is no 1-hop neighbor with closer distance to the destination than the sender itself. Such problem makes the sender stuck because it cannot choose the next hop node to forward the message. This paper gives an algorithm to solve local minimum problem in greedy forwarding strategies. First, the term “strong stuck node” is defined as a node which has a probability to get stuck. Another term, “hole” is defined as an area which a greedy forwarding transmission may encounter the local minimum problem. The paper proves that every strong stuck node must be on the boundary of some holes. A proposed algorithm in the paper can be used by a node to check whether it is strong stuck node. If it is, it can use BOUNDHOLE algorithm presented in the paper to route the message around the hole and finally deliver the message. Thus it can solve the local minimum problem. In conclusion, the concept presented in this paper can alleviate local minimum problem in greedy forwarding strategies. This initiates many new applications which such technique can be applied to. However, there are some cases that a flooding algorithm is still used, and there exists the need for each node to periodically send heartbeat messages and maintain network topology in its memory. Such needs incur memory and network bandwidth overheads, which can affect mobile low-power sensor network. From: Boris Capitanu Sent: Thursday, September 23, 2004 11:03 AM To: Indranil Gupta Subject: 598ig review 09/23 CS598IG Fall 2004 Boris Capitanu Reviews for 09/23 A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks This paper presents an overview of ad hoc routing protocols for mobile wireless networks, along with comparisons between the different schemes. The authors divide the protocols into two camps: table-driven and source-initiated. In the first camp the authors talk about DSDVR, CGSR, and WRP. Destination-Sequenced Distance-Vector Routing is based on the Bellman-Ford routing mechanism and achieves freedom from loops in the routing tables. It uses full-dump and incremental broadcasts to achieve routing table consistency. Route optimizations are done by computing settling time of routes. Clusterhead Gateway Switch Routing is a multi-hop protocol that employs heuristic routing schemes. There is a cluster head selection algorithm that relays messages to other cluster heads via gateways. The disadvantage of this algorithm is that frequent cluster head changes may keep nodes busy with the selection algorithm instead with routing packets. Improvement: Least Cluster Change algorithm - change heads only when two come into contact or there exists a node outside of all clusters. DSDV is used as underlying routing scheme. The Wireless Routing Protocol is the last table-driven protocol the authors look at. In this protocol, nodes maintain 4 tables (distance, routing, link-cost, message retransmission list). MRL keeps track of which updates need to be retransmitted and which neighbors need to ack. Link changes are disseminated through neighboring nodes. Failure of a link triggers the exchange of update messages. Neighbor discovery is done through 'hello' messages or by peeking to traffic. Lack of 'hello' indicates node failure. Given the amount of information that they need to store, table-driven protocols might be too heavyweight for sensor networks, since sensors usually have very limited memory availability. In the source-initiated on-demand routing camp the authors present AODV, DSR, TORA, ABR, and SSR. All these protocols are characterized by a path-discovery process as the main procedure to find a route to a destination. AODV improves on DSDV by minimizing the number of required broadcasts (nodes that are not on a selected path don't store routing information or participate in routing). DSR uses source-caches to maintain information about routes that a particular node is aware of. TORA is based on the concept of link-reversal and maintains 'height' information to create a DAG rooted at the destination. TORA suffers from instability due to partitioning. ABR is a very nice protocol that uses the degree of association stability as metric in determining stable routes (using tick counters). This works quite nice in a stable sensor network where nodes are mostly static. SSR selects routes based on the signal strength between nodes and the location stability of nodes. SSR maintains two tables: signal stability table (SST) and routing table (RT). Strong channels are preferred, but weaker ones can also be used if stronger channels do not exist. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Directed diffusion is a data-centric communication paradigm. A node requiring data uses 'interests' that trigger a data migration process towards the requestor. Intermediate nodes may cache or transform the data (aggregate the data) and may direct interests based on previous cached values. Every data is named using attribute-value pairs that describe a task (interest). The sink node (the originator of the interest) periodically broadcasts an interest message to all its neighbors. Interests are diffused through local interaction (node receiving an interest may re-send the interest to a subset of its neighbors). Gradients are used to specify a data rate and a direction in which to send events. Directed diffusion also describes the process of reinforcement that is used to "draw down" higher data rate events. Negative reinforcement also exists to select between two paths when one is better than the other. Directed diffusion seems to achieve very good energy efficiency, but in order to achieve full potential it needs a carefully designed sensor radio MAC layer. The paper explores a novel approach, but does not discuss aspects such as how it handles congestion - this is important since DD initially floods the network and then reinforces the best path. Scalability might also be an issue - the paper only presents a limited and simple scenario for which it works, but real-life might be totally different. The reinforcement policy is also problematic, while caches also need to be conservative as to not overload the node's memory (which for sensors is quite limited) Locating and Bypassing Routing Holes in Sensor Networks This paper focuses on the local minimum phenomena in sensor networks where nodes might get "stuck", and presents an algorithm that identifies those holes and routes around them. This problem arises in geographic forwarding schemes when a packet gets stuck at a node whose immediate neighbors are all further away from the destination than this node. The paper classifies the stuck nodes as weak and strong, and shows that the weak definition has the limitation that it is not inclusive enough for applications where the destination is not a node in the network. Using the TENT rule the algorithm can find whether a node is a stuck node by checking all local pairs of adjacent nodes of the node in question. The paper further presents BOUNDHOLE, a greedy distributed algorithm that finds the so-called holes (regions with boundaries consisting of all stuck nodes). Using this information routing can be performed initially by greedy forwarding, and in case a packet gets stuck at some node p, then it must be on the boundary of some hole. Knowing the stuck nodes on this boundary, the packet can be routed along this border until it reaches some note u that is closer to the destination than p. When this happens, greedy forwarding can be resumed. If the destination lies inside the hole, the packet will end up at p again since no other node is closer to the destination than p. Using "restricted flooding", each node on the boundary will send packets to all the immediate neighbors who in turn will flood the nodes within the hole. This is a very well written paper with thorough mathematical proofs. Future work needs to look at traffic congestion avoidance. Also, this paper assumes node integrity... I wonder what happens when a node's battery dies out after it relays its message. For example, if node p above dies after sending the message along the border of the hole, the message will never be able to reach p again in case the destination lies inside the hole, in which case their algorithm fails. This can be classified as a best-effort algorithm, with no guarantees of delivery. From: Jin Liang [jinliang@cs.uiuc.edu] Sent: Thursday, September 23, 2004 11:01 AM To: Indranil Gupta Subject: 598ig review 09/23 A review of current routing protocols for ad hoc mobile wireless networks This paper reviews existing routing protocols for mobile ad hoc networks. The protocols are divided into two classes, table driven and on-demand. Each protocol is briefly described, and protocols are compared with each other in terms of overhead, scalability, symmetric link requirement, multicast support, potential problems, etc. Three table driven protocols are described: DSDV, CGSR and WRP. DSDV is a modification of distance vector routing from wired networks, with additions to cope with route loops and incremental updates. CGSR organize nodes into clusters, routing follows a two-level hierarchy. WRP includes second-to-last hop in routing update, which helps to avoid the count to infinity problem. On-demand protocols include AODV, DSR, TORA, ABR and SSR. AODV and DSR are the two most popular ones. Both use flooding to discover routes to a destination on demand. AODV sets up routing state in intermediate nodes while DSR carries path information in the route request/reply packet. As a result, AODV has less overhead and is scalable to large networks. On the other hand, DSR can make use of asymmetric links. ABR and SSR are similar in that they both use link quality (stability or signal strength) to guide route discovery, instead of finding shortest path. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. This paper describes a new data-oriented communication paradigm for sensor networks. In traditional communication networks, communication happens between end points which are uniqued identified by their ID. This paper proposes to name "interests" in data with attribute-value pairs. These interests are flooded to the area specified in the interests. Sensor nodes in that area will detect events that match the interests, and propagate the data along the reverse path to the user. The user (and intermediate sensor nodes) can select good paths by re-inforcing the interests along thoses paths. Under this paradigm, interests in data and the data themselves are named, but individual sensors are not. This solves the ID selection problem for sensor networks, and makes the network more fault-tolerand. It's not clear why their implementation uses rectangles to specify interest area. Why not use a circle. Judging if a point is inside a circle is easier than if it inside a rectangle. Locating and bypassing routing holes in sensor networks. Many routing schemes in sensor networks use greedy forwarding for data delivery. This suffers from the local minimum problem, which means the packet arrives at a node whose neighbors are all farther to the destination than the node itself. This is because sensor networks may not be densely deployed everywhere. So there may be communication holes in the network. This paper proposes an algorithm to locally detect the holes and route the packets around the holes. The basic idea is based on some computational geometry results. The paper also discusses many applications that can make use of the hole detection algorithm From: Pei-Hsi Chen Sent: Thursday, September 23, 2004 9:47 AM To: Indranil Gupta Subject: 598ig review 09/23 Pei-hsi Chen --Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Directed Diffusion, a data-centric communication paradigm, are designed for future sensor networks. Some requirements and characteristics of future sensor networks are 1. Energy efficiency 2. Short-range hop-by-hop communication is preferred 3. Local computation to reduce data before transmission. 4. Task-specific. The dissemination mechanism described in this paper is for a particular instantiation, location tracking. It works as following: A query originated in a sink node starts "interest propagation" to set up state in the network to facilitate "pulling down" data towards the sink. And then once any source node detects a target, "data propagation" is triggered. Data caching and aggregation are associated to facilitate data delivery, and then "reinforcement" leads to discover empirically good paths. The experiment result suggests that the directed diffusion paradigm outperforms traditional data dissemination schemes in energy efficiency. And it is stable at the levels of dynamics considered in this paper. This paper represents a rough design idea of the new dissemination scheme for sensor networks. Those discussions and evaluations are just in the very beginning place, but it provides readers a guide of possible design for future sensor networks. However, some issues not covered are 1. How to store replicas of events in different nodes to improve availability. 2. How to put selected nodes in sleeping mode 3. How to deal with temporarily unreachable nodes and also new join nodes. --A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks There are two subdivisions of ad hoc routing protocols: table-driven routing and source-initiated on-demand routing. Table-driven routing protocols attempt to maintain consistent, up-to-date routing information from each node to every other node in the network. Changes in network structure are propagated throughout the network. Source-initiated on-demand routing creates routes only when desired by the source node. Source node initiates a route discovery process, and once a route has been established, it is maintained by a route maintenance procedure. Generally speaking, table-driven routing approaches have scalability problems due to the requirement of periodic routing information transmissions. On the contrast, on-demand routing protocols produce less signaling traffic and consume less power. However, a route to every other node is always available in the former approaches but is not the case in the latter, which have to wait until such a route can be discovered. From this paper, we can see that each protocol has advantages and disadvantages. Therefore, future study on different applications or scenarios of ad hoc mobile networks may help to develop application-aware ad hoc mobile networks. --Locating and Bypassing Routing Holes in Sensor Networks This paper introduces algorithms of finding stuck nodes where packets may get stuck in greedy multi-hop forwarding. And it also describes a distributed algorithm to build routes around holes, which are connected regions of the network with boundaries consisting of all the stuck nodes. Some questions about this paper are 1. How fast this protocol can converge. 2. How is the network traffic and load balance. More experiments may be needed to address those issues. From: Vartika Bhandari Sent: Thursday, September 23, 2004 10:51 AM To: Indranil Gupta Subject: 598ig review 09/23 A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks This paper presents a survey of various routing protocols for MANETs. The two major classes of protocols viz. table-driven and on-demand are discussed. Protocols reviewed include DSDV, CGSR, WRP, AODV, DSR, TORA, ABR etc. The two classes of protocols are compared with the obvious conclusion that on-demand protocols incur greater latency of route discovery when a new communication begins, but is suited to the ad hoc network paradigm because it saves on control traffic and hence valuable energy resources. Directed Diffusion This paper proposes an approach for data dissemination from sources to sinks in a sensor network. The proposal is data-centric in that sinks express interest in certain types of data using attribute-value pairs that are defined in some sort of code-book. The interests propagate in the network and gradients are set-up in the direction of the sinks. Initially multiple paths get set-up to sources, but a notion of reinforcement is used to strengthen gradients along certain preferred (low-cost) paths, thereby using them more often. The key feature about diffusion is that it is entirely localized in the sense that each node is only aware of its neighbors, and the interests expressed by them could either be their own or on behalf of somebody else (Freenet?) The useful feature of diffusion is that it allows for a lot of redundancy by setting up multiple paths, which is important in a fault-prone system like a sensor network. However the energy consumption issue might not be as straight-forward given the need for periodic refreshing and re-inforcement of interests (the values used for idle, send and receive power are not very accurate). Besides, the proposal as such uses the attribute-value based naming. Of course, they mention other possibilities (and a later work DIFS actually addresses the issue of range queries). However, this is an issue that probably needs further work especially if interests may evolve dynamically, and hence the attribute-set itself might be subject to change. Locating and Bypassing Routing Holes in Sensor Networks This paper addresses the problem of routing holes when geographic forwarding is used in a sensor networks. The routing hole problem pertains to a packet reaching a node which has no neighbors nearer to the destination than itself i.e. a local minimum is reached. Earlier work has attempted to solve the problem using forwarding along the perimeter of the corresponding planar graph. However the authors of this paper point out that the method incurs a lot of overhead. Instead they propose a new definition of strong and weak stuck nodes characterized in terms of Restricted Delaunay Graphs. On the basis of this they propose a TENT rule to detect and bypass holes. A distributed protocol to implement the algorithm is also described. The addressed problem is very similar to the local minimum problem in potential-field based motion planning. Motion planning procedures often deal with the issue by doing simulated annealing i.e. incremental random perturbations are applied in order to escape the minimum. Such a technique might also be relevant in the case of the routing hole problem, if it's occurrence is infrequent (the authors cite Karp et al. as having found that the greedy approach fails very infrequently). From: Jungmin So [jungmin.so@gmail.com] Sent: Thursday, September 23, 2004 10:18 AM To: Indranil Gupta Subject: 598ig review 09/23 Paper Review - Sept. 23 - Jungmin So -------------------------------------------------------------------------------- A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks E.M. Royer et al., IEEE Personal Communications 1999 -------------------------------------------------------------------------------- This paper summarizes the routing protocols for ad hoc networks that are proposed before this summary was written. The routing protocols can be divided into two categories: table-driven and source-initiated. The table driven routing protocols are proactive protocols in that they maintain up-to-date route information to all other nodes in the network. On the other hand, the source-initiated protocols are reactive protocols in that they only establish routes whenever they are needed. There are many variations of routing protocols for each category, and they differ in information stored at each node, information stored at the packet header, contents of control packets, and link metrics. But in general, proactive protocols use more overhead than reactive protocols, but since it maintains up-to-date route, there is no latency in route discovery or route maintenance. On the other hand, reactive routing protocols has less overhead when there is not much traffic in the network, but there is a delay in finding routes and recovering from route errors. This paper was published in 1999, and lots of new routing schemes have been developed after this summary was written. For example, a hybrid approach appeared which combines advantages of proactive and reactive schemes. The Zone Routing Protocol (ZRP) is one of that. Also, numerous routing protocols with different underlying assumptions exist. For example, Location Aided Routing (LAR) makes use of location information to achieve efficiency in route discovery. These routing algorithms share assumptions on underlying physical environment. More specifically, these routing protocols assume at least the followings: - Omni-directional antenna for sending/receiving - Single channel - Fixed transmission power With these assumptions changed, a new routing scheme will be needed to exploit the new physical environment. -------------------------------------------------------------------------------- Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks C. Intanagonwiwat et al., Mobicom 2000 -------------------------------------------------------------------------------- In directed diffusion, a data-centric routing paradigm is used, which is different from address-based routing paradigm. In a sensor network, there are nodes that senses a particular event because they happen to be close to the location of the event. Also, there are nodes that are interested in collecting information on the event, but is too far from the location. The sink, who is interested in collecting information on an event, broadcasts its interest through the network. It is called interest propagation. When a node in a sensing area of the particular event sees the interest, it starts propagating the information through the reverse path that the interest had come. The intermediate nodes may cache the data for robust delivery, and also aggregate data for data reduction. Finally, to increase the packet arrival rate at the sink, a reinforcement mechanism is used which can allow multiple nodes to participate in propagating data. The major contribution of this paper is that it proposed a data-centric routing scheme, which seems to fit well for the sensor network applications. Also, using data aggregation to reduce communication cost is well suited for collecting sensed data. Finally, since sensor network traffic is usually low-rate traffics, the multipath approach can work well without causing too much collision/contention. These characteristics make directed diffusion acheivei higher performance, reliability and scalability over traditional address-based routing schemes. One issue worth considering is the path selection mechanism. Choosing least delay paths does not necessarily help data aggregation, and choosing paths to maximize aggregation may not result in good paths. -------------------------------------------------------------------------------- Locating and Bypassing Routing Holes in Sensor Networks Q. Fang et al., Infocom 2004 -------------------------------------------------------------------------------- This paper presents a scheme for discovering routing holes in the network and algorithm for getting around the hole. The geographic routing uses locations to route packets from the source to the destination. To reach the destination, a node chooses its nexthop has the neighbor node that is closest to the destination node. Since this is a greedy algorithm, it can lead to a local maximum, where the path is stuck at some point and cannot go further. The original paper that proposes a geographic forwarding protocol, GPSR, compute planar graph to get around the holes and guarantee the packet to reach the destination if there is a path. This paper claims that computing planar graph is costly, and so it proposes a scheme for each node to detect whether it is a stuck node (where a packet gets stucked because of the routing hole). Since routing holes can be identified before the actual routing takes place, the routing process can be efficient. With the detecting mechanism, this paper also proposes "boundhole" algorithm, which builds route around the routing holes so that packets do not get stuck on the way. The paper provides formal proofs for the proposed algorithms. It also suggests that the algorithm for detecting route holes can also be used for detecting congested areas or interest zones. From: Thadpong Pongthawornkamol [tpongth2@uiuc.edu] Sent: Thursday, September 23, 2004 10:16 AM To: indy@uiuc.edu Cc: tpongth2@uiuc.edu Subject: 598ig review 09/23 Sensor network routing A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks As stated as its name, this paper, written by Royer and Toh, presents and compares a set of ad hoc wireless network routing schemes which are currently used. There are two subdivision of ad hoc wireless routing schemes, table-driven and source-initiated (demand-driven) protocol. In table-driven protocol, each node has to maintain network status, member nodes, etc. These tables are periodically synchronized between nodes and their neighbors in order to acquire network consistency. On the other hand, Source-initiated (demand-driven) protocols do not require member nodes to possess such information. However, in order to route a message, an arbitrary node need to perform route request mechanism, which will take more time than table-driven protocols. Generally speaking, a route will be created only when a node wants to send a message. Route discovery mechanism and route maintenance mechanism are required for these algorithms. There are three approaches of table-driven protocols presented in this paper. DSDV routing protocols requires full dump messages flooding for infrequent global status updates and Incremental messages for small changes occur in network. CGRS is the modification of DSDV with hierarchical structure consisting of clusters and gateways. Such idea makes CGRS scalable but it also introduces critical points of failure at cluster nodes. WRP require each node to maintain four tables and use hello packet as a heartbeat signal, which prevents any nodes to go to low-power sleep mode. It also avoids routing loops by consistency checks in each node. There are five approaches of source-driven protocols presented in the paper. AODV is built on DSDV with minimized number of broadcasts. It uses broadcasting request and chain reply to form a route in path discovery process. Once a route is discovered, it can be maintained until a failure is detected in the route. Unlike AODV, DSR generates multiple paths in path discovery process with more overhead. It also supports asymmetric route, which is not available in AODV. TORA is a highly adaptive loop-free approach which can be used in dynamic network. It uses link reversal algorithm, which is suited for dense networks. It also provides multiple routes. However, it needs global clock such as GPS, which prevents scalability. ABR scheme routes packets based on associativity stability. It prefers routes on static nodes which are not likely to move. Such approach makes its route long-lived, resulting in fewer route reinitiations in case of link failures. It is also duplication-free. However, periodical beacon advertisements incur energy and traffic overheads. SSR evolves from ABR, but it uses route based on signal strength. Dynamic part of SSR monitors signal strength between a node and its neighbors and generate strength signal information, which is used by static part of SSR to flood route request through strong links. First incoming route request will be replied from the destination. In conclusion, the paper gives a clear overview and comparison between currently available wireless ad hoc routing schemes. However, it is lacking of proven performance evaluation to support its ideas, which will be very useful for future ad hoc routing applications. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks A paper proposed Intanagonwiwat et al. introduces interest-based information dissemination protocol in sensor networks. The term direct diffusion is defined as a hop-by-hop communication, which each node forms into gradient and transfer events, information specific to any interests that were originated by human operators. In direct diffusion scheme, any data is named by attribute-value pair. A task is given as an interest to an arbitrary sensor node in the network. The first node received an interest is then called a sink node. The sink node then broadcasts and refreshes the interest to other nodes. Each node maintains interest caches for several interests. The concept of aggregation is used to reduce data redundancy by allowing a node to group some of its interest caches into single interest. When a node receives an interest from a neighbor, it sets up a cache entry with a gradient pointed to that neighbor. The node then forward the interest it received to other neighbor nodes based on some policies, such as flooding, geographic routing, or history based routing. Once an interest is forwarded to sensor nodes which are located in the specified area, such nodes will perform as sources to gather events, information that match the interest, and distribute events along with predefined gradient. Data will be collected by observing waveforms from the target. Intermediate nodes then forward the message toward a sink with a rate specified in events. Reinforcement can be used by a sink as a kind of acknowledgement to events and a demand to retrieve events at a higher rate. Moreover, reinforcement can be used by intermediate node to repair failed or degraded paths. A set of evaluations is performed to give a comparison between direct diffusion, flooding, and omniscient routing approaches. The metrics used in the evaluation are dissipated energy, average delay, and event delivery ratio. The results yield direct diffusion’s better performance then the others. Another test is conducted to measure the performance of direct diffusion under network failures. It gives an acceptable result for all three metrics. In conclusion, direct diffusion dissemination protocol achieves a certain level of energy efficiency and reliability. It is recommended to use as a mechanism in sensor network. However, there are some problems to be considered, such as congestion handling in multiple sources or sinks network. Locating and Bypassing Routing Holes in Sensor Networks In this paper, Fang et al. introduce a technique to deal with local minimum problem encountered in greedy forwarding strategies, techniques widely used in sensor networks. In greedy forwarding strategies, an arbitrary sensor node can send messages to any destination in sensor network by sending messages to the 1-hop neighbor that is closer to the destination node than the sender itself. Such technique performs good result in sensor network routing with two major exceptions. First, every sender node has to possess locations of all nodes in the network so that it can calculate next hop destination. Second, such routing mechanism introduces local minimum problem, which is the situation that there is no 1-hop neighbor with closer distance to the destination than the sender itself. Such problem makes the sender stuck because it cannot choose the next hop node to forward the message. This paper gives an algorithm to solve local minimum problem in greedy forwarding strategies. First, the term “strong stuck node” is defined as a node which has a probability to get stuck. Another term, “hole” is defined as an area which a greedy forwarding transmission may encounter the local minimum problem. The paper proves that every strong stuck node must be on the boundary of some holes. A proposed algorithm in the paper can be used by a node to check whether it is strong stuck node. If it is, it can use BOUNDHOLE algorithm presented in the paper to route the message around the hole and finally deliver the message. Thus it can solve the local minimum problem. In conclusion, the concept presented in this paper can alleviate local minimum problem in greedy forwarding strategies. This initiates many new applications which such technique can be applied to. However, there are some cases that a flooding algorithm is still used, and there exists the need for each node to periodically send heartbeat messages and maintain network topology in its memory. Such needs incur memory and network bandwidth overheads, which can affect mobile low-power sensor network. From: Jintae Kim Sent: Thursday, September 23, 2004 10:14 AM To: Indranil Gupta Subject: 598ig review 09/23` CS598IG Review 9/23 Jintae Kim (kim28@uiuc.edu) A review of current routing protocols for ad hoc mobile wireless networks, E.M. Royer et al, IEEE Personal Communications 1999 Ad hoc wireless network is an infrastructureless mobile network, where each node, located dynamically and arbitrarily, acts as a router. There exist two types of ad hoc routing protocols at the time of publication: table- driven and demand-driven. Table-driven routing protocol attempts to maintain consistent, up-to-date routing information from each node to every other node in the network. The number of necessary routing-related tables and methods of broadcasting can be different for each different table-driven protocol, which includes DSDV, CGSR, and WRP. On the other hand, source-initiated on-demand routing protocol, which includes AODV, DSR, TORA, ABR, and SSR, initiates a route discovery process within the network, when a node requires a route to a destination. Once a route is established, it is maintained by a route maintenance procedure until either the destination becomes inaccessible or the route is no longer desired. In table-driven protocols, routing information is always available because periodic routing updates are required under the table update mechanism. In on-demand protocols, there is no such mechanism that routing information is available only when needed. Due to this update, table-driven protocols generate greater signaling traffic than on-demand routing, but also it supports better QoS as it mainly guarantees shortest paths. This paper was published five years ago, and so many of the issues and challenges have been handled in the research literature published later. There have also been efforts to hybridize these two classes of routing protocols, ZRP and SHARP in 2001 and 2003, respectively. These protocols employ table-driven protocols in so-called proactive zones and on- demand protocols in other area, and so take strengths of both classes of protocols in moderate situations. Directed diffusion: A scalable and robust communication paradigm for sensor networks, C. Intanagonwiwat et al, Mobicom 2000 Sensor networks are not node-centric, but data-centric. They have no notion of central authority, and are often resource constrained. The motivation of this paper comes from such property of sensor network. Directed diffusion is a data- centric and request-driven dissemination mechanism for tasks and events over sensor networks. The basic concepts of directed diffusion are as follows: Query generates interest for specific data virtually from any node in the network. This interest is diffused locally based on the naming scheme. This sets the initial gradients, which represent both direction towards matching data and status of demand with desired update rate, to draw events matching the interest. After the source send this low-rate data towards sink possibly along multiple paths, sink reinforces one particular neighbor in order to draw down high quality events, which can be achieved by data driven local rules. The main contribution of this paper is, of course, that it successfully presents the technique for coordinating data dissemination and queries in distributed sensor networks. One of some strengths of this technique is that it finds empirically best performing path through reinforcement-based adaptation and perform better than ad-hoc protocols. It also claims to scale to large network sizes, and to be energy- efficient and robust. While this is the first meaningful work on the design of diffusion mechanisms over the sensor networks, I think there are some issues to be resolved, such as how to handle the congestion, scalability and performance under multiple sources and sinks. Locating and bypassing routing holes in sensor networks, Q. Fang et al, Infocom 2004. This paper tries to resolve the “local minimum phenomena” generated by greedy forwarding strategies that many routing algorithms in sensor network employ. The motivation of this paper essentially comes from identifying regions with sparse network connectivity. The authors define stuck nodes where packets can possibly get stuck in greedy multi-hop forwarding. They also develop a local rule called tent rule, to test if each node in the network is stuck or not. BoundHole is a distributed algorithm to find holes, the regions of the network with boundaries consisting of all the stuck nodes. This can be achieved by using the right hand rule. This paper claims that routing with all the holes identified beforehand can be very efficient. One can bypass a hole by the fact that BoundHole returns a cycle including both stuck nodes and non-stuck nodes. This protocol also handles node failures, which may create additional holes in the network. Each node periodically broadcasts to its 1-hop neighbors to detect node failures. This paper is definitely theoretical, in the sense that the authors use only mathematical analysis on their algorithm. While the authors claim that this algorithm is scalable in terms of memory requirement, it would have been better if they could come up with some experimental results that compare the performance of this protocol with those of other routing protocols. From: Michael Treaster [treaster@cs.uiuc.edu] Sent: Thursday, September 23, 2004 10:12 AM To: Indranil Gupta Subject: 598ig review 09/23 Locating and Bypassing Routing Holes Sensor networks can frequently have ``holes'', geographic regions that are out of communication range with other nodes, preventing a message from crossing it directly. It is possible for a greedy routing algorithm to cause messages to get trapped in nodes bordering such a hole. This paper describes an algorithm intended to prevent messages from getting stuck as they are forwarded across the network. It detects holes by locating trapping nodes, then by exploring adjacent nodes in a counterclockwise direction around the hole. Information about the shape and location of the hole is then stored in nodes bordering the hole, such that the knowledge can be exploited for efficient routing when future messages arrive. This hole detection and bypassing algorithm is important for sensor networks, since the holes described in the paper can easily occur, especially since sensor networks typically degrade over time. Although this paper is concerned only with detection and bypassing the holes, the authors suggest that the algorithm might also be applied to solving other issues with sensor networks. One possibility is to use this to detect where sensing coverage might be low or nonexistent for the purpose of deploying new sensors or relocating existing ones, possibly in an automated fashion. One problem with the algorithm is that it does not work when sensors have varying communication ranges. Although the authors mention this weakness, they do not consider the likelihood of this scenario occurring. Although sensors can easily be constructed to meet a particular range specification, as battery power declines this range is liable to decrease. If the sensor population is periodically refreshed with deployments of new sensors as the old ones weaken or expire, the communication ranges will become increasingly heterogeneous as the sensor population comes to possess a wide variety of sensor ages. Directed Diffusion This paper discusses a data-centric approach to communication in a sensor network. The user of the network notifies one or more sensors of his interests, such as movement of pedestrians at an intersection. These sensors share these interests with nearby nodes, which proceed to propagate the interests further across the sensor network in a gossip-like fashion. Nodes in the area of interest collect data, then return the data back along the network towards the originating sensors. At each step of transmission, data can be collated and processed locally before being sent on to nodes closer to the original sensor(s) in order to reduce communication costs or refine the sensing targets. The specified interests combined with the nodes from which interests are received allows a node to construct a gradient of data flow for the interest. The gradient indicates the direction from the region of interest to the node that originated the interest. Although this paper would not be especially interesting if it were published today, given that it was published in 2000 it is extremely valuable. At that time, sensor networks were very new technology and algorithms for routing messages across them had not yet been extensively explored. The authors succeeded in constructing an efficient, robust protocol for sensor network communication, and helped define the direction of sensor network protocol research. Today most sensor network protocols rely on routing messages using limited, highly localized information, and nodes often aggregate data using local processing before forwarding it to another node. Additionally, protocols today typically do not depend on any knowledge of the overall network connectivity. In this paper, the authors assume that a sensor possesses a GPS receiver in order to determine its location. The paper might be improved by modifying the protocol to better exploit this information. As the protocol is designed, nodes expend a lot of energy broadcasting interests to all of their neighbors. If the interests were only broadcast to neighbors roughly in the direction of the region of interest, significant energy savings might be seen. Of course, the modification to the protocol would have to be carefully designed. Otherwise it might encounter new problems like the holes that the Locating and Bypassing Routing Holes paper address. A Review of Current Routing Protocols This paper presents a survey of a variety of routing protocols for ad hoc mobile wireless networks. It describes and compares eight different protocols divided into two categories, table-driven and on-demand protocols. Not surprisingly, the paper concludes that there are pros and cons to each protocols, with some protocols being better suited to some applications than others. Like most survey papers, this paper is heavy on describing existing technology, but it provides no real contributions of its own. This is both a pro and a con of the paper. Survey papers are useful for educating the reader about a particular topic, and this paper fulfills that role very well. The descriptions of protocols and the comparisons between them are reasonable, and they are informative for the student of this field. On the other hand, readers looking for new ideas will not find them here. The paper does describe issues challenging the field and directions in which research might proceed, but it stops short of suggesting any ideas for how these issues might be address or how these directions might be attained. From: Al Harris [aharris@cs.uiuc.edu] Sent: Thursday, September 23, 2004 10:06 AM To: Indranil Gupta Cc: aharris@cs.uiuc.edu Subject: 598ig review 09/23 A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks This is a survey paper that introduces routing protocols for ad hoc wireless networks. The protocols are divided into two main classifications, table-driven and source initiated. Table driven protocols require each node to maintain tables to store routing information. These tables are used to attempt to maintain consistent routing information about the ad hoc network. In the event of a network change, updates are propagated throughout the network. The table driven protocols are DSDV, CGSR, and WRP. As opposed to attempting to keep constant tables of routes to all nodes updated, the other approach, source initiated, is an on-demand approach. Nodes build routes to other nodes on demand using a route discovery process. Routes are only maintained as long as they are needed via some route maintenance protocol. The source initiated routing protocols are AODV, DSR, LMR, TORA, ABR, and SSR. The paper finishes up with some comparisons of each protocol and some general comparisons between the two types of protocols. One thing to notice here is that table-driven routing basically trades of extra traffic for route maintenance with route availability. The frequency that you would need to perform route stability checks is directly related to the amount of mobility in the system. For example, in a fair stable ad hoc system, say a bunch of clients are in a lecture hall, it is possible that the network topology will be the same through-out the meeting. Therefore routes initially discovered will remain. However, as the network gets more dynamic, the overhead to maintain routes becomes larger. At some threshold, it starts to make more sense to do on-demand routing, like AODV. Directed Diffusion: A scalable and robust communication paradigm for sensor networks Directed Diffusion is a routing protocol for sensor networks. The main idea is that energy can be saved if routing is application aware and some data processing and caching happens at the network layer in sensor networks. Communication is data centric in directed diffusion. Each unit of data is named by attribute value pairs. Nodes require data send “interests” for that data. These nodes become sinks. Data then flows down towards these sinks. Directed diffusion also maintains caches of data on intermediate nodes. One obvious comparison is between data diffusion and multicast. Basically we can see all of the sinks as multicast members. Intermediate nodes cache information so that when a new member becomes interested, they can be added locally and requests do not have to flow all the way up to the initial source of the data. Each event has a duration and an interval. Nodes requesting the data send “interests.” In order to keep interests from getting stale, they are periodically refreshed by the sink. Nodes receiving the interests and capable of performing the sensor work required, sense, and then send data back towards the sink. Provisions for node failure are also contained in the directed diffusion algorithms such that paths can be repaired. Directed diffusion is basically an on-demand routing protocol. It begins by sending messages using a “directed flooding” down possibly multiple paths to the receiver. Then it attempts to use “reinforcement” to reduce the number of paths. This paper purposely attempted to design a protocol that did not use any sort of global information. For example, each node upon receiving a piece of data, assumes that data came from its neighbor node. Also, there is no loop detection in directed diffusion, etc. So, it might be interesting to see if some other network metrics could be used to optimize the routes a bit, or speed up reinforcement. Sensor networks are not likely to be general networks, but specialized networks. The problem then is that we really don’t have any specific target for such networks; there is no killer app. So it is hard to see what an actual sensor network will be like, and therefore hard to see what sort of optimizations will actually be possible. Locating and Bypassing Routing Holes in Sensor Networks One main way to route packets through a sensor network is greedy geographic routing. The main idea is to continually forward packets to nodes that are closer to the sink that you are. However, a well known problem is the local minima problem. Packets can get stuck in holes where there are no other nodes closer to the sink than the current node with the packet, but the sink is still out of reach. To solve this, initially, perimeter routing was used. Basically, when a packet got stuck at a local minima, perimeter routing is initiated. The packet is forwarded according to the right-hand rule until it finds a node that is closer to the sink. Once this happens, greedy geographical routing is resumed. While this is effective, it requires quite a bit of state at each node. Since falling into a “routing hole” is an infrequent event, this paper looks at ways to avoid holes without the use of so much state. Basically this paper defines what a routing hole is, then goes on to provide a distributed algorithm BOUNDHOLE to find such holes. Once the location of holes are known, then can be avoided by the routing algorithm. Geographical routing only occurs in sensor networks that have location information onboard each node (for example, via GPS). It is unclear to me whether geographical routing has large advantages over some other sorts of ad hoc routing protocols. Basically sensor networks are ad hoc networks without mobility but with a potentially high node failure rate. From: Yookyung Jo Sent: Thursday, September 23, 2004 9:22 AM To: Indranil Gupta Subject: 598ig review 09/23 A review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks : Summary : Ad Hoc network is a wireless network with no fixed routers (=no base station, <--> infrastructured network). There are two different approaches in Ad Hoc network. Table-driven : maintaining routing info from each node to every other node. On-demand : creating and maintaining only the route from the node that requested it to its destination. The following is a brief review of each protocols in the two families. Table-driven : DSDV is basically distant vector routing. CGSR is similar, but is hierarchical -a cluster consists of one-hop nodes, and routing is controlled by head nodes of clusters -, it has the advantage from hierarchical structure, but incurs network load in electing heads of clusters. On-demand : AODV is distance vector routing based protocol. A source's route request is flooded and when it reaches the destination, a route reply is unicasted reversely, where each intermediate node records its local link info for the route for this source and destination. DSR is similar to AODV. But in DSR, the route request message carries its path information so far(series of nodes), thus the route reply does not need to follow the exact reverse path. So the main difference is that while AODV can be used only for symmetric links, DSR does not have such restriction. On the other hand, DSR's message is heavier, causing more network load. TORA is designed to confine route repair to the location of topology change, to suit the highly dynamic mobile network. Its route is a DAG rooted at the destination. DAG is formed by "height" metric (highest is the destination, lowest is the source). When a node detects the downstream link failure, it adjust its height higher, causing the directed edges of proximity to change directions to reflect the link failure. ABR and SSR use routing metric other than shortest path. In ABR, a node's associativity(higher associativity means low mobility, reliable link) is checked and maintained by its neighbors, and when selecting a route, priority is given to the path involving nodes with high associativity, leading to discovering a longer-lived route. SSR gives additional priority to signal strength in selecting a route. Comments : [C] In designing a network protocol, narrowing down the specific network situation to be addressed and thinking of what constitutes the optimality is crucial and can lead to different protocols. For example, TORA is designed to suit high mobility, and achives it with the sacrifice of synchronization requirement. ABR and SSR are designed with the thought that optimality metrics other than shortest path can practically achive better performance. [C] In CS, many successful approaches follow the steps of 1. discovering a bias or pattern with statistical significance 2. optimize for the statistically significant case to result in global optimality. In ABR, it is assumed that a low mobility node will more likely to remain in low mobility, and the protocol is optimized for this statistically significant assumption. Directed Diffusion : Summary : Directed Diffusion is a data dissemination mechanism in sensor network. Sensor network is highly task-specific. Thus, we can design application-aware( task-specific) routing by embedding query information into data type of the route request. The following is the sketchy of the mechanism. All messages of the sensor network has data type, specifying the kind of information (e.g. : detecting 4-legged animal in a specific region). A node with information need initiates route request with this data type, the request is flooded to neighbors. As a replacement of routing table, nodes have interest (similar to datatype) and associated gradients. The direction of gradient tells to which neighbor the packet with the matching interest should be sent, the value of gradient tells the frequency of information. There could be multiple routes for a single request, but the reinforcement into fewer routes happen only when the requested data is actually generated and transimitted (e.g. : when a 4 legged animal appears in the region); When the data source nodes detect and send back the events, the sink node(initiator) reinforces the good routes (shorter delay). Data is cached in the intermediate nodes. The caching is used for path reinforcement(path with frequent data delivery is reinforced. and the frequency info is stored in cache) and downconversion (data is not delivered to low rate info request, saving energy of networking) other than pure caching. Experiment is done to compare Directed Diffusion with flooding and omniscient multicast. Energy dissipation, delay, loss rate are metrics to be compared, and the experiment is performed for static and dynamic(failure) condition. Directed Diffusion performs good due to in-network aggregation(dropping identical data from multiple sources). Its good performance on node failure is due to reduction of multipath. Comments : [C} Key contribution of the design is the integration of route formation and data communication, which are normally performed in different network layers. The route is data-specific. This is feasible because the query(or task) in sensor network is to be repeatedly performed for time duration. [C] : The analysis and experiment of the paper could be more focused on the contribution of its key idea (integration of routing and data). For example, given a single data need, the route chosen by Directed Diffusion is not going to be any better than the optimal path of application-ignorant routing. Thus, the design does not have much advantage when the sensor network has sparse information need. It is most helpful when a lot of nodes concurrently require and generate the same type data. Also, the experiment is generally focused on how well Directed Diffusion perform. It would be more desirable if they also perform experiment, by first indentifying what are the mechanisms and claims their key idea makes and designin the experiments to verify these fine points. [C]This routing is On-demand routing, but with data- integrated. So, specifically what difference does it have with other on-demand routing? 1. a route is formed at the timepoint when it actually is used(when data transmission starts), 2. data delivery packets are used to form the route as well. [C] A good opportunity to exploit the nature of this design (embeddding application semantic to routing) is the adjustment(merge) of routes for identical data delivery : to design that identical data delivery to different sinks use as much common path as possible, which could be different from individual optimal paths. Could there be some self-reinforcing mechanisms such as in Freenet, if so, with what cost? [C] in-network data aggregation by intermediate node is where the design can boost its performance a lot. The paper only deals with the simplest case of dropping identical data. It is a fruitful direction requring more investigation. Locating and Bypassing Routing Holes in Sensor Networks : Summary : static sensor network can use greedy algorithm instead of flooding, but it can get stuck ( the current node is closest to the destination node, among all its 1-hop neighbors, thus it can't proceed further in greedy algorithm). Exisiting cure : at stuck, perimeter routing on planar graph, and when it gets closer to the destination, resume greedy algorithm. The authors propose new way of cure. Weak stuck nodes are the nodes with potential to get stuck -- if there is a node not reachable from the given node by greedy algorithm (a node is out of 1-hop from the given node, and none of the given node's neighbor is any close to that node.) --. Authors define "strong stuck nodes" as, if there is a region (instead of an actual node) that is not reachable by the node, then the node is strongly stuck. Then it is easy for a node to identify if itself is a strong stuck node by local information. It is verified that a node can at most have 3 stuck direction. Now the remaining job is to find a hole so that if a packet at stuck node follows the perimeter of the hole it could get closer to the destination and resume the greedy forwarding. They show a bounded algorithm for doing this. Hole-finding can be done on-demand, that is, only when it is discovered that a packet is stuck. This is a substantial improvement over the existing planar graph based approach that need to maintain planar graph. Also, their approach identifies fewer false-positive holes. Comments : [C] I like the way they suggest how a seemingly different job (that doesn't seem to be in the scope of the original design) can be done with a twist of thought and parameter adjusting. For example, 1. Their "hole" is to identify the sparse network connectivity. But, it can be used, for example, to identify a region of temperature higher than standard. They do this by testing the neighbor's temperature and if it doesn't pass the local test, the neighbor is regarded non-existent. 2. Their algorithm defined the transmission range of all nodes to be a constant (1) and relied on this in the proof. Thus, it cannot handle heterogeneous transmission range. But, they suggest that two nodes can claim each other as 1-hop neighbor only when they can hear from each other. From: Adeep Singh Cheema Sent: Thursday, September 23, 2004 9:09 AM To: Indranil Gupta Cc: adeep.cheema@gmail.com Subject: 598ig review 09/23 09.21.2004 Cheema, Adeep S Sensor Networks cheema@uiuc.edu A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks An Ad Hoc mobile network is a collection of nodes that are not supported by any additional infrastructure. The connections between these nodes are dynamic and routing protocols are used to discover routes between nodes. The article presents 8 such protocols. High power consumption, low bandwidth and high error rates are some factors of Ad Hoc systems that should influence these protocols. Table-Driven Routing: Each node maintains routing information in tables such that as a whole the protocol can access consistent, up-to-date routing information form each node to every other node. Constant background communication is usually required. Destination-Sequenced Distance-Vector Routing: Complete routing information is stored in each node, which are refreshed based on how stale they are. This data is conveyed [fully/incrementally] to others periodically to ensure consistency. Clusterhead Gateway Switch Routing: Some nodes are Clusterheads and nodes common to two Clusters are Gateways. Clusterhead nodes more information than the rest of the network and messages are routed through them and Gateway nodes. Wireless Routing Protocol: Lots of bookkeeping. Update messages are only sent between neighbors initially. Steps are taken to cut down on background exchanges. Source-Initiated On-Demand Routing: Routes are only discovered once a Source node expresses a desire to communicate with a destination. Once discovered, these routes are maintained either for a time period or till they are no longer needed. Ad-Hoc On-Demand Distance Vector Routing: Paths are discovered/maintained using RREQ packets and established using RREP packets. Supports multicast. Dynamic Source Routing: Similar to AODV except nodes maintain route caches. Temporally Ordered Routing Mechanism: Assumes synchrony. Establishes a DAG with the source as root and reverses links based on “height” metrics [time involved]. Associativity-Based Routing: Optimizes for stability of node connections over time and space. Signal Stability Routing: Routes are optimized for signal strength. (+) Good survey of Ad Hoc Routing options (-) Lacks concrete data on battery consumption/power dissipation – arguably the most important criteria for wireless devices, with respect to the different protocols. Possible are of research. Directed Diffusion – A Scalable and Robust Communication Paradigm for Sensor Networks. Directed Diffusion is a novel protocol for communication is a sensor network, which allows for data collection while conserving resources such as power. All data in Directed Diffusion is named [attribute-value pairs]. A query or interest is introduced into the sensor network at a sink. The query is then diffused into the network as a replica of the initial interest, except with a reduced sampling interval. Interests are cached at nodes to avoid redundancy. For each interest present at a node, a neighbor- specific gradient is established which indicates the rate of data transfer requested by that neighbor as well as the lifetime of the gradient. A locally unique identifier is used to track neighbors. Nodes use their sensing capabilities to collect the data requested by the interest and diffuse it along the gradients they have set up. Typically a small set of source nodes will have access to high quality data. This is detected by the sink, which reinforces the connection to these sources and requests higher data rates. Negative reinforcement is used to curb slow or redundant flows of data. Data caches are set up at nodes and aggregation is also performed if needed. Evaluation: Directed Diffusion performs better than Flooding or Multicast for sensor networks in terms of energy consumption, delay and communication effectiveness with optimizations such as negative reinforcement and duplicate suppression. (+) Clever and unique paradigm for a specialized function (-) Performance study contains certain assumptions regarding radio communication used. (-) Nodes closer to sink may be overloaded; there will be non-uniform consumption of power. Future directions: Introducing specialized nodes into such a sensor network have an impact. Adding loose infrastructure such as nodes that specialize in aggregation and filtering. Locating and Bypassing Routing Holes in Sensor Networks An algorithmic paper which defines the notion of a Stuck Node: A source node such that none of its one hop neighbors are closer to a target node than the source node itself. A protocol for detection of Stuck Nodes and Holes (areas whose boundaries are dotted with Stuck Nodes) as well as bypassing them is provided. BoundHole is an algorithm that attempts to detect and bypass Holes while finding a route from one node to another. Once a Stuck Node is encountered, the algorithm proceeds to sweep its one-hope / accessible neighbors in a counter-clockwise manner in order to find a path along the hole. A proof of correctness is provided with a guarantee of convergence. The protocol allows for node failures as well. (+) BoundHole is an effective and efficient protocol with several practical uses. (+) Algorithm shown to always converge. (-) The protocol assumes that the nodes are homogeneous from a communication standpoint, which is not always the case i.e. different nodes can have different ranges. Future Direction: It may be useful to design a protocol that arrives at the optimal set of k nodes that should be inserted into a system given a system with a Hole and a number k. From: Jigar Harshad Doshi Sent: Thursday, September 23, 2004 3:36 AM To: Indranil Gupta Subject: 598ig review 09/23 This review was written after discussion with ellick chan (emchan) A Review of current routing protocols for mobile Wireless Networks The paper describes routing protocols for mobile ad hoc networks. A number of different routing protocols respresenting various routing strategies are discussed. The protocols are first classified as either table driven or source initiated on demand. Three table driven protocols are discussed namely DSDV, CGSR and WRP. DSDV is a modified version of the distance vector schemes which were applied to fixed networks. It uses sequence numbering to maintain the consistency of routes and also to avoid routing loops. CGSR is a modified version of DSDV which uses a hierarchical scheme with elected cluster heads. WRP on the other hand is a proactive scheme. Part of the novelty of WRP stems from the way it achieves loop freedom. In WRP nodes communicate the distance and the second to last information for each node in the wireless network. Thus it can avoid the count to infinity problem. All these proactive protocols are not really suitable for mobility. Under high mobility the amount of routing information soon exceeds the amount of data traffic. Also it might saturate the wireless channel and cause congestion. The second important classes of routing protocols belong to the source initiated on demand category. These do not store any table information or proactive lists. Rather routes are found as-is and when required. A prime example of this category would be dynamic source routing. DSR sends out a route request to an unknown destination X when data arrives for it. The route request is broadcasted from node to node till either it reaches the destination or a node that reaches the destination. The information of the route is carried in the body of the packet and thus the route is reversed and the packet is returned to the source. A restricted form of route maintenance is then applied. All packets from then on are source routed to the destination. AODV is a protocol which combines the operation of DSDV and DSR. TORA is a protocol which localizes the information dissemination when a route is lost. It does this by a height metric. However its route erasure phase is not very efficient as it involves flooding a broadcast clear packet throughout the network. Also there is a possibility of oscillations. ABR and SSR use the metrics of stability in order to route in adhoc networks. The more stable a route is the less likely it is to move and thus these routes are used more often in routing. SSR uses signal stability as a metric to route. The paper thus concludes with a comparison of the schemes. These routing protocols are designed for the very robust requirements of adhoc networks. These can be applied in other fields too. A network of sensor motes can easily use these protocols for operation. However the requirements of sensor networks are different and these protocols must be tailored for sensor networks. For example the senor networks the topology of the network is not expected to change rapidly and also the processing capabilities are less. Thus a hybrid protocol like CGSR which limits table sizes can be applied. Also P2P networks represent an ideal ground for applying such protocols. Protocols such as AODV + Gossip can be applied to efficiently search p2p networks. Locating and bypassing routing holes in sensor networks This paper concentrates on a problem faced by greedy forwarding strategies in sensor networks. A local minima phenomenon causes packets to get ‘stuck’. These regions are classified as holes and are characterized by sparse network connectivity. Thus any packet which enters the hole at a point cannot get out of it. This problem has been studies before and others have proposed a mechanism to add to the greedy forwarding in order to route around the perimeter of the holes and thus guarantee delivery of the packet. Unfortunately the proposed strategy is inefficient and wasteful. The primary contribution of this paper is a mechanism to route around holes which does not require the maintenance of global topology info. The proposed algorithm works as follows. First the node has to identify whether it itself is stuck. It does this by computing the Delauney graph and then running a check to see if the ‘TENT’ rule is violated. The TENT rule specifies if a node is strongly stuck. The the node can run the bound hole algorithm which passes a packet around the network to mark the boundary of the hole. Special cases to take care of edge intersection are proposed and mechanisms to terminate the algorithm are also given. It has to be noted, however that the algorithm is greedy by nature and may not be optimal in all cases. Mechanisms to handle node failures are proposed. These are simple heartbeat/hello mechanisms like other protocols. One of the key advantages of this protocol is that it is localized and will thus have smaller memory requirements. However there is no analysis at all n the performance of the protocol. There is no data on the amount of messages transferred and the memory requirements etc. These are required to get a better understanding of how the protocol behaves under various stress conditions. Further work on this protocol could involve detailed analysis. The speed of recovery to consistent node failures as in a catastrophic node failure can be improved by pre-emptive mechanisms. Thus as the hole increases, mechanism can be introduced to speedily transfer this information around to increase the size of the perimeter. Also mechanisms can be introduced to coalesce holes into bigger perimeters. Directed Diffusion : Directed diffusion is a data centric mechanism to distribute information in a sensor network. It is strongly application aware to allow optimizations in term of energy usage and performance. Central to the paradigm of directed diffusion, is the concept of interests where a node specifies particularly what information it is interested in. For example a node may be interested in tracking four legged animals. Thus it propagates an ‘interest’ with the appropriate type. An interest also contains a duration and an expiry time. This is very important to control the lifetime of the interest as specified later. The interests are propogated and form a gradient from the sink to the 'source' which is a point of interest. Each node maintains an ‘interest’ cache which is the primary tool to improve performance. However since only local information is maintained, two interests referring to different things might overlap. The dissemination of the interest is left open and can be implemented by a variety of means like directional propagation. Reinforcement is applied since there may be multiple nodes may respond to interests and the sink needs only specific information. The time out field and the duration is used to reinforce the ‘interest’. The biggest contribution of this paper is the fact that the diffusion algorithm is kept generic and so can be made application specific. Another key advantage with this approach is the fact that routing is localized . However it has to be noted that a lot of the proposed mechanisms can be made more efficient by applying techniques like gossiping and multicast. Also some of the techniques like flooding can lead to network congestion. Speed of convergence of the algoirthm can be improved because it seems the time taken to reinforce gradients is a long process. From: Christopher W Banek Sent: Thursday, September 23, 2004 2:30 AM To: Indranil Gupta Subject: 598ig review 09/23 Chris Banek 598ig review 9/23 After reading these three articles about sensor net routing, I feel there are some major similarities and differences between the papers. The first paper by Royer is mainly a summary of the different types of routing and protocols used in ad hoc networks, only some of which I feel really applies to sensor net routing. The paper by Fang et al also discusses some very interesting problems involving sensor net routing, but also could apply to just ad hoc routing problems in general. In the paper by Intanagonwiwat et al, there is a very well formed discussion about the specific differences between sensor networks and other distributed problems, and how to use these differences to come up with more specialized and efficient algorithms. Given that the first of the three papers is more of a summary paper that compares different ad hoc routing protocols with little to no new information, talk of this paper will be brief. I think it presents a good overview of the problems in ad hoc routing by going over the solutions that already exist, and showing how each different protocol overcomes certain issues and raises other ones. Although the discussion of each protocol I feel is too brief to bring a good working knowledge of the material, it does present a way to encourage further learning into the protocols that suit your particular needs. Now I will skip to the last of the three papers, talking about finding holes in ad hoc sensor networks and how to route around them. Not understanding a lot of graph theory, I can't really contend the correctness of the proofs they present, but the findings are quite interesting. With the ability to route around and detect holes, this would improve the greedy algorithm very much in the ways that they present in the paper. Although they do present very valid findings, I feel their experimental data to be a bit lacking. Although they talk about power consumption being a key factor in any sensor net solution, it seems that their algorithms would create a lot of network traffic, taking a lot of battery power for any of the nodes on the network. Also their algorithms use a lot of mathematical and computational power in each round at each node, possibly increasing power consumption from the microprocessor, not to mention requiring just more processing power up front for each node. Last, but certainly not least, this algorithm is totally based around using and improving the greedy algorithm, which is shown in the second paper about directed diffusion, may not be the most efficient or desirable way to route on a sensor network. After reading the paper on directed diffusion I felt very excited about the prospects of sensor networks in general. Very well written and presenting the correct amount of detail, it presents its argument in a very coherent way. One of the important facts is that although many other routing algorithms are based on routing any type of network traffic, this paper discusses the unique situation of sensor networks. By using the facts that sensor networks don't have a lot of power and trying to reduce the amount of radio traffic, as well as trying to aggregate received data and forward it accordingly, I feel that this paper really shows the power of creating more specific algorithms to solve more concrete and specific problems. Also unlike the last paper which is more of an exercise in graph theory, these algorithms are fairly light on the mathematical computation, using probability and statistics to simplify the problem. Although I think much more research and experimental data will be needed to perfect the numbers for certain routing options for different situations, I think this paper has the most promise out of the three. From: William Conner [wconner@glsn33.ews.uiuc.edu] Sent: Thursday, September 23, 2004 1:49 AM To: Indranil Gupta Subject: 598ig review 09/23 A REVIEW OF CURRENT ROUTING PROTOCOLS FOR AD HOC MOBILE WIRELESS NETWORKS This paper provides an overview of different routing protocols for ad hoc mobile wireless networks. These routing protocols fall into two categories: table-driven and source-initiated on-demand. The table-driven approaches usually maintain routing information from each node to every other node in the ad hoc network. This routing information is stored in tables. Any changes in network topology are propagated throughout the network via updates. With source-initiated on-demand approaches, routes are discovered and maintained when they are needed. With this class of routing algorithms, established routes are maintained until they fail or until they are no longer needed. Destination-Sequenced Distance-Vector (DSDV) is a table-driven routing protocol based on the Bellman-Ford algorithm. In DSDV, every node has a routing table with all destinations and number of hops to that destination. Updates can be full dumps containing all available routing information or small incremental packets containing only the new information since the last full dump. Full dumps take several network protocol data units while small incremental packets only take one network protocol data unit. Clusterhead Gateway Switch (CGSR) uses DSDV as the underlying routing scheme, but it uses a hierarchical approach where nodes organize into clusters. To forward a packet, a node sends that packet to its cluster head who then forwards that packet to a gateway. Wireless Routing Protocol (WRP) uses four tables and link changes are propagated through update messages. Updates are only exchanged between neighbors, some of which respond with acknowledgements. Ad Hoc On-Demand Distance Vector (AODV) floods route requests until either the destination or an intermediate node with knowledge of a path to the destination is reached. In Dynamic Source Routing (DSR), a source first checks its cache for a route to a destination. If a route is not found, then route discovery is performed. In DSR, route records are placed in the cache once a route is discovered. Temporally Ordered Routing Algorithms (TORA) provide multiple routes for source and destination pairs. In Associativity-Based Routing (ABR), routes are chosen based on connection stability of one node to another. In Signal Stability Routing (SSR), routes are chosen based on signal strength. One question about the CGSR approach would be whether or not the cluster head is necessary. It seems like it would be better to forward packets immediately to a gateway (which could also take on the other cluster head responsibilities). Even if this scheme caused more gateway/cluster head selections, that overhead might be offset by the elimination of the extra hop on each message from cluster head to gateway. For the ABR and SSR approaches, it's not clear if their metrics are actually good metrics for selecting a path. If a long-lived path is very costly, then it might be better to use several short-lived paths with less cost. LOCATING AND BYPASSING ROUTING HOLES IN SENSOR NETWORKS This paper studies and presents a solution to the local minimum phenomena that occurs in geographical greedy forwarding in wireless sensor networks. Geographical greedy forwarding occurs when the source node knows the location of the destination node and forwards the packet to a 1-hop neighbor that is closer to the destination. The local minimum phenomena occurs when a packet gets stuck at an intermediate node because that node is faced with a situation where none of its 1-hop neighbors are closer to the destination. Previous work on this problem has provided a solution, but that solution requires the maintenance of planar graphs at every node in the network (even the nodes that are not stuck). The major contributions of this paper are the TENT rule and the BOUNDHOLE algorithm. The TENT rule allows each node to determine if it is stuck and in which direction it is stuck. The BOUNDHOLE algorithm finds the boundaries of holes (regions with communcation voids) and these boundaries contain both stuck and non-stuck nodes. A packet can be routed along this boundary until a node is found that is closer. In addition to helping stuck nodes, these algorithms can also be applicable to temperature monitoring and traffic congestion. Although the distributed algorithm is presented and analyzed, this paper would be improved if it had simulations and experiments with results collected and presented in tables and graphs. An implementation and performance evaluation would be future work. DIRECTED DIFFUSION: A SCALABLE AND ROBUST COMMUNICATION PARADIGM FOR SENSOR NETWORKS Directed diffusion is a scalable, robust, and energy efficient approach to data dissemination in wireless sensor networks. It was partly motivated by the authors' observation that a different set of communication primitives that are application-specific and data-centric can lead to more efficient sensor data dissemination when compared to IP and ad hoc routing for wireless sensor networks. Application-specificity can be utilized due to the fact that sensor networks are task-specific when deployed. With directed diffusion, a sink acts as a node where a human injects an interest for sensor data into the network. This injection sets up gradients that send events from event sources toward the sink node. When gradients are set up, multiple paths can exist from event sources to sinks. The path with the highest quality is reinforced. Should another path have higher quality, then it is aggressively reinforced while the old strong path is negatively reinforced in a conservative manner. One question about this scheme is whether or not negative reinforcement should be conservative. If old strongly reinforced paths seldom become high quality paths again in the future, then it might be better to negatively reinforce those paths in a more aggressive fashion. This would eliminate the unnecessary overhead of those paths as they are negatively reinforced in a conservative manner. It would be interesting to see the effect that aggressive negative reinforcement has on energy consumption in the system. From: James Richard Newell Sent: Thursday, September 23, 2004 1:47 AM To: Indranil Gupta Subject: 598ig review 09/23 Sensor Net Routing: A review of Ad Hoc routing, Directed Diffusion, and Routing Holes James Newell 9/22/04 The first paper is titled A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks by Royer and Toh. This paper gives a general overview of current ad hoc-based routing protocols currently researched and attempts to classify them based of similar characteristics. This allows the reader to get a general comparison between the various protocols to evaluate their complexity and assumptions. The paper logically divides the protocols into two main categories: table-driven protocols and source-initiated protocols. The primary difference being the time and frequency at which the paths are being constructed. Table-driven protocols tend to constantly maintain routing information at every node of the network, while source-initiated protocols discover paths to destination nodes "on-demand". Therefore, only "used" routes are cached on the nodes. The table-driven protocols include DSDV, CGSR, and WRP, while the source-initiated protocols include AODV, DSR, TORA, ABR, and SSR. Due to table-driven protocols' requirement of knowledge of all possible paths, they tend to incur a higher overhead than source-initiated protocols. This is because table maintenance information is constantly propagated between nodes. This is really significant to ad-hoc networks where nodes often have minimal resources. However, table-driven protocols are more likely to implement a QoS support to applications. Finally, it was interesting to see a couple of the source-initiated protocols used various non-conventional metrics (such as association stability or signal strength) to determine strong path routes. This paper is difficult to critique because it didn't really provide any new ideas or innovation, but instead allowed the reader a quick snapshot of the status of ad-hoc routing protocols. Therefore, the paper itself is devoted to mildly critiquing these various protocols. I thought the paper was clear and summarized the protocols coherently. I was also easily able to compare the general strengths and pitfalls of the various protocols. Since this paper is over 5-years old (which is significant in the relatively young field of ad-hoc wireless networks), it would have been nice to see an updated version of the paper to see what kind of strides have been made since 1999. The second paper is Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks by Intanagonwiwat, Govindan, and Estrin. This describes a data pulling technique called directed diffusion for sensor networks that is more energy efficient and performs as well as flooding or multicast. Sensor networks are unique in that they are ad-hoc, typically immobile, neighbor/hop-based, and failure-prone. Therefore, protocols need to be designed with these types of characteristics in mind. Directed diffusion is unique in that it incorporates the capability for an expressive data-pulling language into the protocol, which allows flexible data-gathering queries for various purposes. Specifically, a user initiates a task by specifying an interest using attribute-value pairs. Typically, the interest is not ID specific; therefore, the requestor doesn't need to be aware of specific sensors nor the network topology. This interest is passed along the network creating gradients along the way to draw the replies back to the initiator. Eventually, the network is capable of reinforcing one or more of these paths to be the high-throughput routes for the data by sending another interest with a higher data-rate. Furthermore, these strong paths can be changed using various techniques such as negative reinforcement. Caching is used along the back-propagation to the sink to avoid looping of seen messages and interests. It should also be noted that intermediate nodes will opportunistically aggregate or merge data and interests along the way; thereby decreasing load on the network. There are many advantages to the "directed diffusion" paradigm. First, there is no global ID scheme present, so this overcomes a giant mess considering the sheer size of these networks (thousands) in the face of possible mass additions to the network. Furthermore, it is energy efficient which is imperative to increasing the longevity of these resource-starved nodes. Also, as mentioned earlier, the protocol it is expressive and application-specific for data extraction. It is capable of handling multiple sources and sinks, and seems to be fault-tolerant to failing sensors. Its scalability is questionable, however. While it seems to be scalable because it is neighbor-based and does data aggregation, the design doesn't seem to deal with congestion or loss of data. There is much future work to be done with sensor protocols. To quote the paper: "we are with sensor networks where we were with the Internet about 3 decades ago." The last paper Locating and Bypassing Routing Holes in Sensor Networks by Fang, Gao, and Guibas describes a mechanism for testing and overcoming "routing holes" caused by greedy packet forwarding protocols in sensor networks. The greedy algorithm works by passing along the message to a node that is closer to the destination than the current node. However, this can cause a problem called the local minimum phenomenon. This occurs when a packet is stuck at a node where all of the local neighbors are all further away from the destination- stranding the packet. The authors propose the "TENT" rule to determine if a packet is stuck in this situation. The Tent rule basically uses the angle or bisector cone between adjacent 1-hop neighbors to determine if the node is capable of reaching the "black region." Any angle that is smaller than 120 degrees cannot be a stuck node. Next, the authors propose a method "BOUNDHOLE" that allows the network to define the actual boundary of the stuck-node hole. This is done by sweeping around the hole in a counterclockwise fashion by locating the first node outside of the "forbidden region". This process is repeated at each node until it is returned to the original node. Finally, the authors go on to implement their design developing a protocol on a simulator to show the validity of their idea and give various optimizations. This paper provided a simple solution to semi-nasty problem. Although it appears that this can be overcome by using traditional route-discovery mechanisms, this renders the more efficient greedy routing mechanism to be a more usable alternative. The main contributions of the paper seem to be the TENT rule and the BOUNDHOLE algorithm to detect and circumvent blocked nodes/holes. Some future work that can be done include finding the shortest path around holes and the impact of non-uniform sensor networks would have on the above two techniques. From: Ellick M Chan Sent: Thursday, September 23, 2004 12:06 AM To: Indranil Gupta Subject: 598ig review 09/23 Ellick Chan CS598ig Review 09/23/2004 Discussed with Jigar Doshi Locating and Bypassing Routing Holes in Sensor Networks: Sensor networks are vulnerable to node failures from phenomena such as radio blockage, lack of power, or destruction of a node itself. One major class of failure is spatially based, creating “holes” in the network. The authors in this paper describe a distributed algorithm to cheaply detect and route around these holes, while allowing the use of greedy geographically based routing algorithms to optimize for the limited resource on motes. The authors introduced several theorems and a formalization of weak and strong stuck nodes. Through several geometrical and graph theory analyses, they concluded that the definition of strong node implies that for any node p, and neighbors u,v, if the angle formed by upv is less than 120 degrees, p cannot get stuck. Hence, for any node p, there are at most 3 stuck directions. Using this analysis, they conclude that a simple algorithm, which exchanges messages counterclockwise around a hole, will detect it. This finding allows sensor networks to efficiently detect and route around holes without over computation (Delaunay) on any single node or the entire network. The algorithm described in this paper relies on a simple clockwise traversal rule. For any arbitrary shape, intuitively, there should be a solution (not necessarily optimal) found by this procedure because the greedy algorithm only routes towards the point q. One of the troubles is with the detection of the hole. A minor problem with this algorithm is that it requires a message to be passed around a hole back to the originating node. If that node fails, then the procedure must begin again. This may occur due to a fire, or if certain nodes are not exposed to enough sunlight to stay active. One possible (natural) fix is that multiple nearby nodes cooperatively discover the hole. This means that when node p begins a discovery, neighboring nodes are notified to complete the process if p fails. Furthermore, on a network with intermittent failures, it might be helpful to maintain k candidate paths, in case several nodes temporarily fail and restore themselves, or are going to fail soon. A Review of Current Routing Protocols for Ad Hoc Wireless Mesh Networks: This paper is a review of many popular routing protocols to manage ad hoc networks. Depending on the application requirements, the routing algorithm chosen can help optimize for dynamic networks, high performance, or a combination performance and safety to change. Some of the protocols rely on a large routing table; these typically perform well, but are slow when the network topology changes. For the on-demand routing protocols, they are often during operation, but are more resilient to rapid change. Some other protocols offer a mix by caching changes, and propagating these changes to other nodes either differentially or incrementally. Of particular interest is Ad Hoc On-Demand Distance Vector Routing, which minimizes global broadcasting by using on-demand routing. AODV uses several mechanisms such as reverse route propagation, link failure notification, and periodic hello broadcasts to keep a good performance with reasonable memory overhead and good adaptability. Directed Diffusion: Directed Diffusion is a system for nodes to gossip information to each other. Each node can play one of three roles: sink, source, or intermediate. Sources nodes generate data, and sink nodes broadcast interest for data. Intermediate nodes route the data by means of directed diffusion, and cache data that is in their interest table. Directed diffusion is an early model of gossiping ad hoc networks, where certain simple rules are applied to hope to eventually spread data from sources to interested clients. The actual flow of data is actually more coarse and spread out than a direct link. This can lead to network flooding and congestion. Since not all nodes have similar interests, this can lead to a somewhat inefficient system. One interesting feature is the aggregation of information into summaries, which help reduce usage, but at the same time limit sensor granularity. For example, imagine running an application like SETI@home on this, each node group would not be powerful enough to analyze the subtle patterns involved. The loose structure of this system relies on interest, disinterest, and heartbeats to manage gradients. This leads to inefficiencies of multiple paths, and overall higher network usage than is necessary to exchange information. Obvious optimizations would be to build in better routing tables and histories to aid in more fine-grained propagation. This adds extra memory and computation requirements on motes. However, since the nodes are already capable of sensing higher-level activity and processing it, the extra overhead to use more advanced routing algorithms should be minimal. From: Charles Yang [cmyang2@gmail.com] Sent: Wednesday, September 22, 2004 10:44 PM To: Indranil Gupta Subject: 598ig review 09/23 Charles Yang 598ig, Fall 2004 9/23/2004 Sensor Net Routing A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks. E. Royer & C. Toh. The paper gives a survey of current (1999) ad hoc routing protocols. The authors distinguish between two paradigms of ad hoc protocols: 1. table driven and 2. source-initiated. Table Driven (a full set of routes is computed and maintained) --------------------------------------------------------------------------- DSDV (Destination-Sequenced Distance-Vector Routing) * based on Bellman Ford (like Dijkstra's, but allows for negative weights) * 2 routing table update types: 1. full-dump 2. incremental - inefficient due to periodic updates, regardless of changes in topology CGSR (Clusterhead Gateway Switch Routing) * uses DSDV as underlying routing scheme, with some changes (group nodes in clusters; hierarchal) * Clusterheads are elected * routing done via: node -> clusterhead -> gateway -> clusterhead… -> destination - clusterhead churn can adversely affect performance + several heuristics can be employed to improve performance WRP (Wireless Routing Protocol) * 4 tables (distance, routing, link-cost, message retransmission list) * link changed communicated within neighbors via update msgs * hello messages (heart-beat) required - can require substantial memory - hello packets disallow sleeping mode Source-Initiated On-Demand Routing (route is discovered only when needed) ------------------------------------------- AODV (Ad Hoc On-Demand Distance Vector Routing) * path discovery: broadcast route request (RREQ) to neighbors which fwd(with path appended) to neighbors…to destination which in turn route reply (RREP) is sent on reverse path * if node along path moves, it fwds a link failure notification msg all the way down to source, which in turn can reinitiate a new path discovery if it so wishes * hello msgs used, but not reqd (can listen for retransmission from next hop) - requires symmetric links DSR (Dynamic Source Routing) * 2 phases: 1. route discovery and 2. route maintenance * route discovery: checks cache, if route not there then broadcast route request which is fwd once by neighbors while appending the route. One destination receives msg, generates route reply which can be either reversed(if symmetric link is supported) or generates it's own route request with the path from source to dest piggybacked. * route maintenance accomplished via route error packets and acks. + doesn't require useless updates -not scalable to large networks TORA (Temporally Ordered Routing Algorithm) * establish a directed acyclic graph (DAG) rooted at the destination, and direction is assigned to links (according to upstream/downstream) * once a node's downstream link fails, reverse the links upstream - potential for oscillations + support multicast and multi-routes ABR (Associativity-Based routing) * degree of association stability is indicated by ticks which are awarded by beacon frequency * route discovery – broadcast query (BQ) is fwded with ticks appended. Dest node can then decide which path to reply via. + routes tend to be longer lived + free of packet dups - requires periodic beaconing SSR (Signal Stability Routing) * select routes based on signal strength between nodes * Dynamic routing protocol: maintenance of signal stability table and routing table. * Static routing Protocol: look up in RT and fwd, or pass up if is intended dest, otherwise initial route-search - intermediate nodes cannot reply to route requests Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. C. Intanagonwiwat, R. Govindan & D. Estrin. Directed Diffusion is a paradigm for sensor networks that differs from the end-to-end routing prevalent in other protocols. A sensor (sink) can request data by putting out an interest (containing task specific information such as: task type, location desired, intervals, and duration) which is broadcasted and eventually propagates to the intended destination nodes (the nodes that are described by the interest). The destination nodes, in turn, relay their msgs, and the msgs trickle back (while possibly being transformed through intermediary nodes) to the sink node, which in turn can choose to reinforce certain flows, and cutoff other ones. The reinforcement functionality also allows for the network paths to repair. Neighbor nodes msging each other set up a gradient per neighbor that they communicate with for every interest. Gradients are essentially weighted vectors. Directed Diffusion requires that the tasks already be programmed into the sensor nodes prior to deployment, as their task descriptions are basically indexes. The main contribution of the paper is a new paradigm for ad hoc communication: the network traffic is data-centric. In a sense, a node only needs to know about it's neighbors, and the right thing will happen. This is likened to an ant colony where simple behavior on part of the individual can multiply into complex behavior as a whole. The performance of directed diffusion is promising. Energy dissipation is substantially less (60% of omniscient multicasting), and delay is quite comparable to multicast. The paper does not address how diffusion reacts to highly congested networks. It also speculates that TDMA would work better than 802.11 MAC unicast (their simulator ns-2 does not support TDMA). Locating and Bypassing Routing Holes in Sensor Networks. Q. Fang, J. Gao & L. Guibas. Greedy forwarding in sensor networks sometimes results in a packet getting stuck (the local minimum phenomenon) where the packet is stuck at a node where the 1-hop neighboring nodes are all further away from the destination. The paper introduces a better understanding of the underlying geometric properties, as well as algorithms to detect potential holes and how to deal with them. The TENT rule checks if a node is a stuck node, and BOUNDHOLE is a distributed algorithm to locate regions in the network with boundaries of stuck nodes. The algorithms also allow for the discovery and maintenance of holes. The strengths of the algorithms is that only nodes located on the boundaries will need to store more information (that of routing along the perimeter of the hole). However, it is possible that a packet can be sent along a path of O(k^2) for a shortest path of O(k). There are heuristics to improve the path, though. BOUNDHOLE can also be modified to identify regions according to any sort of criteria that is testable locally by a node (such as temperature, gad concentration, etc). Some possible future investigations are network traffic avoidance, avoidance of un-dependable links, or detection of certain physical phenomena. Another place for future application is seeing if it works for 3-D meshes, which could have applications in studying the oceans, or inside of volcanoes. From: Dennis Y Chi Sent: Wednesday, September 22, 2004 6:17 PM To: Indranil Gupta Subject: 598ig review 09/23 Sensor Net Routing A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks Ad hoc routing protocols can be broken up into two categories: table-driven, in which nodes propagate routing information throughout the network to maintain routing tables, and source-initiated on-demand, in which routes are created only when necessary. Table-driven protocols: DSDV may be good for small networks, but is not scalable because each node has to periodically broadcast updates even if the topology has not changed. CGSR may incur too much overhead to maintain cluster heads, but the routing tables are smaller and the hierarchical addressing scheme may be ideal in terms of scalability. WRP deals with link changes better because updates are only sent to neighbors, but hello messages must be periodically sent for failure detection. On-demand protocols: AODV broadcasts messages when a route is needed, and each node along the path keeps track of route entries in tables. DSR differs from AODV because the source stores the entire path of the route, and is advantageous for smaller networks. TORA is good for large, dense networks because it provides multiple routes and updates only need to be sent near the topology change, but it is dependent on node synchronization and may exhibit oscillations. ABR and SSR choose routes based on stability to provide longer-lived routes and higher throughput. This paper does an excellent job of surveying the different types of protocols, but it would be interesting to have a quantitative comparison between these protocols in terms of bandwidth utilization, power consumption, performance under high mobility/failure, etc. Also, these protocols don’t seem suitable for sensor networks that have stationary nodes with limited memory. Future work could be done regarding the flexible ad hoc routing protocol that the paper described. It would be interesting to design a protocol that dynamically changed its routing scheme based on the topology and QoS requirements. This would also require that the protocols used different performance metrics, other than shortest path, to route. Directed Diffusion Sensor networks are very different from traditional networks because they consist of unattended nodes that must dynamically adapt to their environment while conserving energy. This paper proposes a communication paradigm for sensor networks called directed diffusion, which is energy-efficient, robust, and scalable. Directed diffusion is data-centric, such that the network communication is application-aware and specific. The interest propagation stage begins when a node (sink) requests an interest (named data with attribute-value pairs). This interest is periodically broadcast by neighbors, diffusing the interest throughout the network. This diffusion creates a gradient (direction that data should flow) towards the sink. The data propagation stage begins once the interest reaches the source. The source sends data back along the gradient. If the sink receives data from multiple neighbors, it can reinforce one of the neighbors, and reinforcement continues down to the source so that a single high quality path is established from the source to the sink. The sink also has the option to negatively reinforce a path. The results from the paper show that directed diffusion has better energy efficiency than flooding and omniscient multicast, and has delays comparable to omniscient multicast. When the network has failures, average delay slightly increases, while the event delivery ratio and average energy dissipation decreases. Further simulation results show that negative reinforcement and duplicate suppression improve energy dissipation. The paper was interesting because it pointed out that sensor networks should be application specific because they are small, cheap, and can be densely distributed. One of the problems with the paper is that because it is so application-specific, it may be difficult to design a generic interface for this directed diffusion model. Also, the simulation environments were very lightweight, with no congestion. Future work mainly involves developing a generic directed diffusion interface that allows the user to develop different rules for interest and data propagation, reinforcement, and/or gradient setup. For example, some type of gossip routing protocol could be used during the interest propagation phase to conserve more energy. Also, since this model might not work under heavy loads, some type of clustering protocol could be used to create a hierarchical structure that improves scalability. Locating and Bypassing Routing Holes in Sensor Networks Sensor networks that use the greedy forwarding routing protocol must deal with the local minimum phenomenon, in which packets get stuck at nodes whose neighbors are all further away from the destination. Holes, regions that have boundaries of all stuck nodes, must be detected and routed around. This paper proposes a distributed and scalable algorithm for identifying and routing around holes, called BoundHole. Nodes determine if they are stuck by applying a tent rule, in which the node checks if the packet can be stuck there for all pairs of its adjacent neighbors. Once a node determines it is stuck, it runs the BoundHole algorithm. By applying the right hand rule, a node sweeps counterclockwise to find the next node bounding the hole, and this continues until a cycle has been created. All the nodes could possibly run the algorithm simultaneously, so suppression is used to limit the number of messages sent to identify holes. Also, heartbeats and retire timers are used to deal with node failures and repairs. One of the problems with the paper is that the simulation was done only to validate their algorithms and protocols. The BoundHole algorithm is distributed and scales well, but does it provide acceptable energy utilization? What are the performance gains of their algorithm versus GPRS? The authors should have presented some simulation results, or if they were not sufficient, then they could have used ns2, like the Directed Diffusion paper did. The future work should first be focused on determining whether the BoundHole algorithm is the best method of detecting and routing around holes. If so, then as the paper states, many different types of applications can be built on top. This applies more to sensor networks in general, but as sensor networks become more popular, security should become more of an issue. These new sensor network routing protocols will eventually have to address issues regarding malicious nodes, etc. For example, in this protocol, a malicious node could vary its heartbeats, forcing the protocol to continually rerun. This would cause unnecessary traffic, collisions, and energy consumption, and effectively bring down the network. From: Moosa Muhammad Sent: Tuesday, September 21, 2004 3:38 AM To: Indranil Gupta Subject: 598ig review 09/23 (1) Review of "Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks" This paper examines a new data distribution model for sensor networks, which they call directed diffusion. This is a data-centric model, which means that generated data by the sensor nodes is represented by attribute-value pairs. A node can request data by sending interests for named data, which is then routed towards that node. Intermediate nodes can not only cache data, but also have the ability to combine reports from several sensors, in order to return back a more accurate representation of the environment they are monitoring, to the requester. An important feature of directed diffusion is that interest and data propagation/aggregation are determined by exchanging messages b/w neighbors or nodes within some bounds, i.e. through localized interactions. They evaluated the performance of their location tracking sensor network, using the directed diffusion protocol. They compared diffusion to flooding and omniscient multicast mechanisms of disseminating data in networks. Their results showed that the average dissipated energy of diffusion was lower as compared to other protocols, as the network size was increased. When nodes failures was introduced, the energy consumption for diffusion increased, and was higher than compared to others. On the other hand, event delivery ratio (under node failures) was the greatest for diffusion. An interesting future research area would be to investigate/compare various schemes of data naming and attribute-value based interests, in order to quantitatively measure the performance of a diffusion algorithm (based on choosing different schemes). XML is another way of representing attribute-value based interests. Another future area to look into is to explore the behavior of diffusion under network congestion, to evaluate the performance degradation resulting from it. A criticism against this paper is that they perform computationally expensive calculations on sensor nodes, which are not meant to be used in this manner, due to power and bandwidth constraints. This is visible for example when the nodes analyze interest and gradient events, in order to reinforce a path to a neighbor. From their experiments it was clearly shown that with the possibility of nodes failing (the probability of which is high in hostile environments), the energy consumption increases, which can further result in more nodes to die out. This can have a truly adverse effect on the entire sensor network. (2) Review of "A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks" Ad Hoc networks are infrastructureless mobile networks, with no fixed routers. Every node can function as a router, maintaining routes to other nodes in the network. Some applications of it include data acquisition operations in inhospitable terrain, sharing information in meetings, etc. There are two types of ad hoc routing protocols: a) Table-driven, where each node maintains table(s) to store up-to date routing information from itself to other nodes. It is a connectionless approach of forwarding packets. b) Source-Initiated On-Demand Routing works by having the source node create routes, only when desired. Therefore when a node requires a route to a destination, it initiates a route discovery process within the network, to examine all route permutations. Some existing table-driven ad hoc routing protocols include "Destination-Sequenced Distance-Vector Routing", "Clusterhead Gateway Switch Routing", and "Wireless Routing Protocol." As for Source-Initiated On-Demand Routing some protocols like "Ad Hoc On-Demand Distance Vector Routing", "Dynamic Source Routing", "Associativity-Based Routing", and "Signal Stability Routing" exists. Comparison Between Table-driven Protocols: DSDV is inefficient b/c of the requirement of periodic update transmissions, regardless of the number of changes in the network topology, resulting in an overhead that grows O(n). An advantage of CGRS is that its performance can be improved through priority token scheduling mechanism, among others. The advantage that WRP has over others is that it avoids the problem of creating temporary routing loops that these algorithms have through the verification of predecessor information. Comparison Between Source-Initiative On-Demand Routing Protocols: DSR has a larger overhead, in terms of memory utilization, than compared to AODV. DSV can utilize routes with both asymmetric and symmetric links, unlike AODV. DSR also reduces power consumption and bandwidth, by not using periodic routing advertisements. TORA is best suited for networks with large dense population of nodes, through its support for multiple routes. It is not a practical solution, due to its reliance on synchronized clocks, which is impossible to achieve in the Internet and various other p2p applications. A benefit of ABR is that for long-lived routes, it requires fewer route reconstructions and therefore yields higher throughput. But on the other hand, it relies on each node beaconing periodically (resulting in increased power consumption). Some future areas of research include investigating the feasibility and performance of hybrid ad hoc routing algorithms. In general, more research is needed in security, service discovery, and Internet protocol operability, in order to fully utilize the potential of ad hoc mobile networking. (3) Review of "Locating and Bypassing Routing Holes in Sensor Networks" This paper studies a fundamental problem faced by many sensor network routing algorithms that use greedy forwarding strategies to get packets to their destinations. The problem is known as "local minimum phenomena" and can cause packets to get stuck. They also device a rule (called TENT) to test whether a packet can stuck at a particular node. To help a packet get out of stuck nodes, they describe a distributed algorithm called BOUNDHOLE that finds the so-called holes (i.e. regions of the network with boundaries consisting of all the stuck nodes). Holes are usually associated with regions where nodes are depleted or regions that do not have enough nodes due to irregular terrain. BOUNDHOLE algorithm is a distributed algorithm that identifies the stuck nodes for greedy forwarding and connects the stuck nodes possibly along with some non-stuck nodes into cycles encircling areas that are called holes in a network topology. The authors simulated the TENT rule and BOUNDHOLE by a C++ simulator at the topology level, to validate their algorithms and protocols. A possible future area of research and application of the BOUNDHOLE algorithm would be to use it to yield a route for bypassing the congested areas in the network. Another interesting application of the BOUNDHOLE algorithm is to use it to identify particular regions of interest, for example detecting a region with high gas concentration, etc. Other applications of it relate to supporting path migration (where the nodes are moving around, and therefore the communicating path needs constant updates) and routing by means of greedy forwarding, and using this algorithm to overcome the problem of stuck nodes. These applications require further research, in order to fully understand the applicability of this algorithm in these scenarios.