From: Andrew Harris [harris78 SpamElide] Sent: Tuesday, March 01, 2011 12:37 PM To: Gupta, Indranil Subject: 525 review 03/01 Review of “Directed diffusion: A scalable and robust communication paradigm for sensor networks” and “Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones” The authors for directed diffusion present a routing algorithm for distributed sensor networks based on flows of information. This proves to be a useful design for event-driven information, which the authors note is an aspect of this particular class of sensor networks that they wished to exploit. Their network topology proves to be at least as efficient as existing work, is resilient against node failure and node slowdown, and is able to dynamically handle both bursty and duplicate data. Furthermore, their design reduces power consumption for their particular implementation needs. Perhaps an obvious limitation to this work is that their system assumes two things: event-driven reporting, and proximity of sink nodes. Addressing the first, their supposed model for operation involved the sensing and tracking of animals. It was not, for instance, a constantly reported set of time series information, and would not perform significantly better than existing implementations for such types of information. Furthermore, their implementation seems to assume large solitary animals, or more generally single unique observations. This allows for the caching and redundancy removal that they implement. Staying with their animal observation example, this would not be suitable for tracking, say, a flock of birds or a pack of rodents, as the system would quickly become overwhelmed with duplicate readings. Their use of flows does not seem entirely novel, although it may be that this was among the first adaptations of flows in a distributed sensor network. This sort of application is among the very design cases for flow diagrams: information needs to pass in an efficient manner from a source to a sink. As such, their choice to build their topology using a flow network is perfectly sound, at least insofar as it concerns suitability for their observation task. The Learn on the Fly team takes a more empirical approach to improving network transmission. Their algorithm uses an active, data-driven protocol to estimate the latency of network links as they are used, comparing this with a known expected latency-per-distance. Route switching is then handled probabilistically based on the updated quality of each known link. By this, the system is able to route around sources of interference dynamically, and accomplishes this with a lower transmission overhead than existing systems. This was actually a very straightforward implementation. It is curious that they would use an 802.11 network, as radios for such are relatively high-consumers of battery power. Nevertheless, their move away from periodic network heartbeats and toward data-rate sampling seems like a no-brainer: it requires little additional overhead both in computation and in transmission, it is quick to adapt to failures in the network, and it scales well for most any arbitrary mesh topology. I would have liked to see an in situ implementation of the LOF system. It is adequate for a first-run of the system to use a prototype testing setup as the group did, the first with a very clear outdoor line-of-sight transmission, the second with a contrived array of nodes. The real test of such a system would be distribution across a very wide area with an erratic terrain, such as a mountainside or a forest. Showing that their system works in a contrived arrangement is a good start; let’s see how it functions for real. As for future implications of both papers, it would be interesting to see how a combination of these technologies would fare in a mesh network. Consider that the data capacity links in the directed diffusion model could be constantly updated per sampling done in the LOF model. One could very directly augment the other, instead of relying on static information or arbitrarily established routes. It would also be interesting to see this implemented with multiple sink nodes, as per the directed diffusion model, where many nodes may function as the end point for data. The active use for this would be nodes on the edge of, say, a forest sensor net which could be sampled by a passing researcher instead of that researcher having to delve into the terrain to find a single sink node.From: yanenli SpamElide on behalf of Yanen Li [yanenli2 SpamElide] Sent: Tuesday, March 01, 2011 12:23 PM To: Gupta, Indranil Subject: 525 review 03/01 Paper review Paper 1. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks summary: This paper proposed Directed Diffusion, a Data-centric Communication Paradigm for Sensor Networks. For sensor networks, there is no notion of central authority, and often resources are constrained. Also, nodes are tied to physical locations; they may not know the topology or move arbitrarily. A major research question is how can we get data from the sensors. Directed Diffusion provides a data-centric communication protocol for sensor sources and sinks. The data routing protocol is as follows: (1) Sinks broadcast interest to neighbors; (2) Interests are cached by neighbors; (3) Gradients are set up pointing back to where interests came from at low data rate; (4) Once a source receives an interest, it routes measurements along gradients. Empirical best path can be found by reinforcement-based adaptation. In-network data aggregation and caching is employed for fast data transferring. Questions and critics: (1) Energy gains are dependent on 802.11 energy assumptions (2) This paper claims that empirically best performing path can be found by reinforcement. Does reinforcement actually work? (3) Can the network always deliver at an interests requested rate? (4) The capacity of such networks is small. How does it behave during overload? Paper 2. Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones For sensor networks, nodes are randomly deployed; we might not know the physical locations of the nodes and the topology of the network. So routing data in sensor networks is a critical problem in sensor networks research. In this paper the authors propose to estimate link quality information from data packets. The metric they use to do the estimation is called "Expected MAC Latency per unit-distance to the Destination" (ELD). To do this, a node first notifies its location to neighbors and learn rough distance from its neighbors at start-up, and does the first estimate of ELD by sending small messages to neighbors. When the node are communicating with others later, it updates the ELD estimate via exponentially weighted moving average on data packets. In this way, the link-quality estimates are up-to-date without much extra effort. And when data pockets need to be forwarded, the neighbor with lowest metric will be chosen as the next-hop forwarder. Pros: (1) A data-driven model for link-quality estimation, which can get up-to-date link-quality information accurately. (2) Since no much extra messages needed to be sent in order to measure the link-quality, energy is saved. Questions and critics: (1) Directly comparing energy efficiency with other methods is more desirable. (2) The nodes need to know their location. GPS functionality is required. (3) The estimation is based on data statistics. However, data statistics might not be accurate/stable when there is not enough data. Can some kind of prior distribution apply to the link-quality estimation? -- Yanen Li Ph.D Candidate Department of Computer Science University of Illinois at Urbana-Champaign Tel: (217)-766-0686 Email: yanenli2 SpamElide From: w SpamElide on behalf of Will Dietz [wdietz2 SpamElide] Sent: Tuesday, March 01, 2011 12:21 PM To: Gupta, Indranil Subject: 525 review 03/01 Will Dietz cs525 3-1-2011 "Directed Diffusion" This paper presents primarily a communication method for sensor networks called 'directed diffusion', which is is a communication 'paradigm' to allow for local decisions on event 'diffusion' as well as routing and aggregation of the data back to the requesting nodes. They way they do this also provides remarkable robustness to node failure, and impressive energy savings. Their 'paradigm' works similar to distance-vector routing, only with frequency on each node, which has the nice property of leveraging multile path selection and robustness to node failures. In addition they use both positive reinforcement and negative bias on less good paths to select at each node the appropriate path and overalll provide the mechanism to 'diffuse' interests and return events back to the sources. Additionally they maintain data caches at each node that provide some interesting features such as loop detection and event aggregation. Both of these can be rather effective in improving the quality of the network. Overall their design allows for a much more ad-hoc sensor network in terms of lack of node configuration and robustness to hetereogeneity of link quality, and node distribution. Pros: +Lower energy costs +Robust to node failure +All 'routing' done locally, no single point of failure. Cons: -Diffusion seems like a glorified broadcast -Possibly excessively redundant traffic Question: How does it compare to favorably to omniscient multicast?! I might misunderstand how omniscient multicast works... ------------ "A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks" This paper did not present a particular new system or algorithm, but rather was an overview of a good number of mobile routing technologies. They classify all the presented algorithms as either 'table-driven' or 'on-demand'. Table-driven routing algorithms (such as DSDV, WRP, and CGSR) attempt to maintain routing tables at each node and have varying methodologies to keep these tables up-to-date as well as other properties like being loop-free or perhaps optimal in some way (generally shortest path). On-demand algorithms on the other hand, do what the name suggests: determine routing on-the-fly, as needed. The way they do this varies a bit more than the table-driven methods but they aim for similar properties of being loop-free. In general the on-demand and table-based routing methods do similar things, try to find shortest path through an ever-changing network that might have failures. However, table-driven is better for maximum throughput on lower-churn networks, which is why it's used in much /wired/ networks today. On-demand on the other hand only creates/discovers the routes that are needed, as they are needed. What this means is that while there might be some latency introduced by discovery of routes, there also is less constant chatter whch is much better for battery/power consumption which is very important in many mobile wireless networks. Overall this paper was useful in learning a number of routing algorithms, and seeing them discussed and compared. I'm curious what it would be like if it were written today as opposed to in 1999? ~Will From: kevin larson [kevinlarson1 SpamElide] Sent: Tuesday, March 01, 2011 12:17 PM To: indy SpamElide Subject: 525 review 03/01 Zhang et al propose a learning algorithm which leverages attributes of the (media-access-control) MAC layer, particularly latency, to build a routing protocol Learn on the Fly (LOF) without the need for beacons. The authors explore the impacts of various types of interference on packet delivery rates and the relative change due to interference on both broadcast and unicast. The authors explore using MAC feedback and GPS information to give the network additional knowledge about the state of the system in order to further aide routing. They explore correlations between distance, mean MAC latency, and effective MAC latency per unit-distance to the destination (ELD). They then give a quick overview of LOF, and present four mechanisms in which LOF learns about the network, issue requests, answer requests, handle announcements, and announce presence. The authors then explain some of the optimizations LOF can apply, such as probabilistic neighbor switching, and proceed to evaluate various forms of LOF against the beacon based systems, ETX and PRD. The paper had thorough analysis, and provided a lot of math related to the algorithms they used in their implementation of LOF. Unfortunately, the authors had a very minimal summary of the existing background in the field and additionally, were quick to delegate further explanations to other works. As a result of this, a reader less knowledgeable in the area of sensor networks would likely have a hard time following the work. Intanagonwiwat et at presented their power efficient routing algorithm, directed diffusion. Directed diffusion is built of the ideas of interests and gradients. Sink nodes are used to propagate interests across a sensor network. Gradients are used to direct information back to the sinks. Source nodes gather information about an event and send it across the gradients. The authors explore the types of data that needs to be send and the implications on power consumption and bandwidth, and determine that the messages need to contain a type, instance, node location, signal intensity, confidence in the match (for type/instance) and a timestamp. This does require the sensor nodes to perform some amount of processing, but the effect of this reduces transmission power sufficiently that that trade off is worth it. The authors explore various transmissions, ranging from single/multi source/sink setups, gradient establishment, reinforcement, and repair. It is evaluated against a popular standard (omniscient multicast) as well as a baseline metric (flooding). Evaluation shows that for power consumption, directed diffusion beats out omniscient multicast by 40%, and flooding by several hundred percent. It performs comparably to omniscient multicast in delay, and again beats flooding by several hundred percent. It is then demonstrated that 10% and 20% node failures do not massively effect energy dissipation, delay or delivery rate. The authors of this paper very thoroughly explained the ideas and algorithm behind directed diffusion and clearly showed how it performed in comparison to the standard techniques. The evaluation showed that while directed diffusion performed pretty well given node failures, it didn’t show how the standard techniques performed in comparable instances of node failure. From: Jason Croft [croft1 SpamElide] Sent: Tuesday, March 01, 2011 12:16 PM To: Gupta, Indranil Subject: 525 review 03/01 A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks This paper examines two classes of routing protocols for ad hoc networks: table- driven and source-initiated on-demand. The three table-driven protocols rely on maintaining consistent and up-to-date tables of nodes in the network and propagating any updates. Destination-Sequence Distance-Vector Routing (DSDV) improves on Bellman-Ford and is loop-free, but can require high overhead to send a full dump of the routing table. Clusterhead Gateway Switch Routing (CGSR) improves on the flat design of DSDV with clustered multihop networks, but frequent changes in the clusterhead can impact performance. In the Wireless Routing Protocol (WRP), each node maintains four tables (distance, routing, link-cost, and message retransmission) and only sends updates to neighboring nodes. However, inactive nodes must send a hello keepalive message to distinguish inactive nodes from link failures. In contrast to table-driven protocols, source-initiated on-demand routing only creates routes when a node wishes to send a message, which requires a method of discovering other nodes. Ad Hoc On-Demand Distance Vector Routing (AODV) improves on DSDV by reducing the number of required broadcasts and uses a route request packet to discover paths. Hello messages can be used but are not required. Dynamic Source Routing (DSR) requires nodes maintain a route cache and uses route discovery and route maintenance phases. Temporally Ordered Routing Algorithm (TORA) is based on link reversal and is designed for highly dynamic mobile environments. Synchronized clocks are important for recovering from link failures. Associativity-Based Routing (ABR) uses a metric called degree of association stability, which is defined by the connection stability of one node with respect to another over time and space. Signal Stability Routing (SSR) selects routes based on signal strength and stability. Overall, this paper provides a decent high-level view of various ad hoc wireless routing protocols. However, the comparison and discussion is not very in-depth or thorough, and does not draw any conclusions about the protocols (e.g., which is best for what purpose?). There is some discussion of applications but not much on which protocols would be best for different types of applications or environments. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Directed diffusion is motivated by the need for a method of disseminating data in a robust, scalable, and energy-efficient manner. It is data-centric; that is, generated data is named by attributed value pairs. Data is requested using an "interest", and intermediate nodes may transform or aggregate any matching data. The authors' design prefers short-range hop-by-hop communication due to power and battery constraints. It also must support multiple concurrent tasks, scale to thousands of sensors, and assume nodes may fail due to battery power. In this design, attribute-value pairs are used to name tasks and specify an interest for data matching the attributes. An interest is injected into the network at a node, known as a sink, and then diffused throughout the network. Sinks periodically broadcast interests to neighbors and nodes can re-send interests to subsets of its neighbors. In choosing paths to send data, the node tries to use the lowest delay path by negatively reinforcing previously reinforced paths. Unlike traditional networks, data diffusion uses only neighbor-to-neighbor communication and sensors do not need globally unique identifiers or addresses. While simulations show energy savings compared to flooding and multicast, and comparable delay to multicast, the authors' design does not seem very complete. A lot of work has been left to future work, such as controlling congestion, naming schemes, geographic routing (limiting scope of the interest diffusion to some subset of the network topology), and efficiently discovering good paths with reinforcement. Also, with the use of timestamps, one would assume all sensors need to be synchronized, but this is never mentioned and does seems non-trivial. Finally, security is not discussed. Can malicious nodes inject any interest into a network? From: Anupam Das [anupam009 SpamElide] Sent: Tuesday, March 01, 2011 12:01 PM To: Gupta, Indranil Subject: 525 review 03/01 I. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks  This paper proposes a scalable and robust data dissemination paradigm called ‘Direct Diffusion’ for sensor networks.  This paradigm is data centric i.e., information generated by the sensors are named using an attribute-value pair. So, when a node wants to retrieve some information from the environment it simply sends out interests (queries) for that certain name data. These interests are then flooded to its 1-hop neighbors who first check their cache to find a match for the interest and depending on the result of the matching process it either forwards the interest to its own neighbors or sends back results to the sink node (interest originator) . After an interest is disseminated throughout the network, gradients are setup. Gradients can be thought of as reverse paths through which matched data are eventually sent back to the sink node. There are usually multiple paths through which matched data can be delivered, but direct diffusion only maintains one or a small subset of these paths by reinforcing only few of them while rejecting the remaining ones through negative reinforcement. By doing so, direct diffusion saves unnecessary energy wastage. Direct diffusion is different from traditional networking in a number of ways. Firstly, in direct diffusion all communications are local and as a result the nodes do not require any globally unique identifier. Secondly, in direct diffusion nodes can aggregate information from their neighbors to provide more accurate information. Lastly, in direct diffusion communication occurs in a hop-to-hop basis and there is not concept of end-to-end service delivery. There are some issues that I would like to comment about- 1. Direct diffusion floods new interests to all its neighbors who can flood it to their neighbors and so on. This flooding mechanism can cause network congestion. Maybe, some smarter forwarding technique can be employed (like sending to nodes in the direction that are more likely to have the answer). 2. Since in Direct diffusion all communications are local, the path used might not necessarily be the globally optimal path. So the energy saved may not necessarily be the optimum. Moreover, in reinforcing path nodes choose the path with the best forwarding rate. And since in a wireless network, the quality of a path often fluctuates rapidly, it may not be useful (might in fact lead to energy wastage) to consistently change this reinforcement choice. 3. Lastly, I am quite surprised to see that direct diffusion out performs Omniscient multicast despite the fact that direct diffusion uses only a local algorithm whereas Omniscient multicast has a global view of the entire system. Maybe some form of the evaluation metric was overlooked. II. A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks This paper provides a survey of some of the existing routing protocols used in ad hoc mobile wireless networks. The paper divides the protocols into two basic classes: Table Driven Routing Protocol and Source Initiated On-Demand Routing Protocol. The table driven category includes Destination-Sequenced Distance-Vector Routing (DSDV), Clusterhead Gateway Switch Routing (CGSR) and The Wireless Routing Protocol (WRP). The source-initiated on-demand routing includes Ad Hoc On-Demand Distance Vector Routing (AODV), Dynamic Source Routing (DSR), Temporally Ordered Routing Algorithm (TORA), Associativity-Based Routing (ABR), and Signal Stability Routing(SSR). The authors briefly describe the working principle of each of the protocols along with their limitations. They also compare the protocols for a set of parameters.  The broad level conclusion from the comparison section is that table driven protocols are more suited to static environments where there are less churns. The reason behind this is that as nodes move or leave/enter the network routing table changes and in case of table driven protocols this update (whole routing table) is flooded out to all neighbors causing a large amount of control traffic. For source routing only updates concerning the current path used is flooded and not the whole routing table. However, source routing requires a waiting time for the protocol to discover alternative routes whereas in table driven protocols alternative paths are readily available. So, the selection of a routing protocol really depends on the application and environment it is going to be deployed in.  Comment: Although the paper compares the protocols under different theoretical parameters, I think it would have been nice if all the protocols were simulated under different scenarios to highlight some of the more important experimental parameters like- throughput, delay and energy. By doing so the authors could have given a guideline as to what protocol performs well under what scenario. This would be really helpful to readers who are thinking of implementing a protocol themselves. Another point, the authors only concentrate on reliability and fault tolerance in the comparison section, but security issues could also have been considered. ----Anupam From: Chi-Yao Hong [cyhong1128 SpamElide] Sent: Tuesday, March 01, 2011 11:57 AM To: Gupta, Indranil Subject: 525 review 03/01 ---- A review of current routing protocols for ad hoc mobile wireless networks, IEEE Personal Communications, 1999 ---- This paper discussed a variety of routing protocols for mobile ad hoc networks. Back to 1999, ad hoc network increasingly became an important research topic because that i) many applications arise, e.g., sensing and military communication that leverage mobile ad hoc network as the communication medium, and ii) the network protocol for mobile ad hoc network was not either been standardized or commonly accepted. This survey paper discussed pros and cons of both table-driven and on-demand routing protocols. The paper comprised a comprehensive comparison across different protocols. The performance metrics include the overhead complexity and soft metrics such as whether the routing is loop-free. Pros: 1. As a survey paper, the authors successfully classify the state-of-the-art routing protocols by the way they maintain their routing table. This classification is natural and easy to follow. 2. The analysis of the protocol properties is sound and complete. Table 1 and Table 2 basically summarize whether the important factors that each routing protocol could support. Cons: 1. The applicability of these routing protocols is questionable. Simply checking the complexity (in time and communication) might not accurately tell how well it could perform in reality. For example, while AODV has exactly the same time and communication complexity as DSR, the control message size in AODV is much smaller than that in DSR. To clarify the applicability, we need a “decision-tree”-like table to help network operator choosing their preferred protocol based on its own requirements and limitations. 2. Some important properties are not even discussed in the paper. For example, by which mobility rate, table-driven protocols will become not useful? What’s the router state (amount of information stored in a node) for each protocol? It is commonly known that routing protocol will become instable when the route changes rapidly. Which protocol under investigate will have instability issues? 3. Energy is a great concern in ad hoc network where the nodes use its own local battery for communications and computations. However, the energy aspect is not addressed in this paper. 4. Protocol complexity is another important factor in ad hoc networks, as some nodes could have little computational power. For example, some sensor nodes have very limited storage and restricted active time. ---- Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks ---- To conduct the sensing process, sensor nodes usually need to disseminate their sensing data frequently. To do this, the human operator requires complicated configuration such that the data aggregation could perform well, in terms of robustness, scaling, and energy efficiency. This paper proposed a new way, called directed diffusion, to propagate out the data in a data-centric manner. In particular, the authors define high-level interfaces to simplify the configuration. For example, a node could send “interests” as a request to ask for collecting data with desired properties (e.g., location, time, etc.). Pros: 1. The use of directed diffusion improves the robustness of the propagation, as they exploit the path diversity by checking multiple in an on-demand fashion. 2. The data aggregation becomes much simple to perform under the proposed paradigm. It can be shown that the proposed data aggregation scheme could significantly reduce the energy consumption. Cons: 1. The flooding could be prohibitive in a large-scale sensor network. However, one of the main contributions of this paper is selecting right path to reduce energy consumption, which nevertheless requires the information attained from flooding. 2. The injected traffic load is stationary. It is questionable that the proposed system would perform well under heavy load. Also, when the interest sending rate varies, the system could easily consume a huge amount of energy for the resource discovery. -- Chi-Yao Hong PhD Student, Computer Science University of Illinois at Urbana-Champaign http://hong78.projects.cs.illinois.edu/ From: muntasir.raihan SpamElide on behalf of muntasir raihan rahman [mrahman2 SpamElide] Sent: Tuesday, March 01, 2011 11:36 AM To: Gupta, Indranil Subject: 525 review 03/01 Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Summary: Directed Diffusion is a novel paradigm for sensor networks that ensures reliable data delivery, scalability and energy efficiency. Compared to traditional end-to-end networking which is not data centric, needs routers and global IP addresses, and has no in-network processing, directed diffusion is data centric and uses in-network processing, and does not need routers or global addressing. The local greedy interactions of the nodes lead to the global sensing task without any network wide optimization scheme. Directed Diffusion has multiple design phases. Initially, interests are generated from sinks and propagated throughout the network. The initial interests are exploratory and they have a lifetime. Gradients are setup to specify a data-rate and a direction to send events. Data propagates in the reverse direction from the source to the sink guided by the gradients setup earlier. Reinforcement occurs when a node receives data which then sends reinforced interests to its neighbors. Negative reinforcement can occur through timeouts due to absence of reinforcement. The paper evaluates directed diffusion against flooding and multi-cast. The average energy dissipation, delay, and event delivery ratio are measured to evaluate the impact of churn dynamics on performance, the impact on MAC layer, and the parameter choice trade-offs. Pros: (1) Robustness, scalability, and energy efficiency. (2) No global addressing scheme. (3) Local greedy actions lead to desired global sensing task. (4) Data centric sensor network processing is also influencing traditional networking, especially in the context of named data networking, and routing on flat labels. Cons: (1) The interest profile seems to simplistic to specify all types of sensing task. (2) This scheme cannot support simultaneous sensing tasks. Future Works: (1) Explore the performance of directed diffusion under high network stress, for example congestion or security attacks. (2) Some theoretical performance analysis would be interesting. However, this is an early paper on sensor networks, so I am sure many authors followed up with mathematical analysis of directed diffusion. Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones Summary: The paper argues that broadcast beacons are not sufficient to accurately estimate link properties and proposes a data driven method to estimate unicast link properties. The authors observe that sensor events are rare, but when an event occurs, there is a burst of traffic. As a result static broadcast beacons that send date in the absence of any traffic activity is wasteful. As a result the authors propose the ELD metric which is computed on the fly when there is actual data transmission and is based on feedback from the MAC layer. The authors also show an associated routing protocol LOF which uses the ELD metric. This is a rigorous statistical approach to link quality estimation, where link assessment starts with initial random sampling and is continuously improved when new packets are sent. Pros: (1) A better link quality estimation technique. (2) Rigorous experimental evaluation using real testbeds. (3) Performs better than ETX and PRD. (4) Energy efficient. Cons: (1) The routing latency might be affected, since it takes time for the link estimation to converge when changes occur. Future Works: (1) It might be interesting to explore the feasibility of an adaptive protocol that combines broadcast beacons and ELD. - Muntasir. From: Long Kai [longkai1 SpamElide] Sent: Tuesday, March 01, 2011 11:31 AM To: Gupta, Indranil Subject: 525 review 03/01 A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks Summary: This paper describes several routing schemes for ad hoc wireless networks. The routing schemes are divided into two categories, table-driven and on-demand. The paper later presents a comparison between each of the schemes and discusses the pros and cons of table-driven schemes and on-demand schemes. According to the paper, table-driven schemes maintain a relatively more consistent routing table. And the routing is path is always available. On-demand schemes, however, have a latency to find required routing path before transferring data. But on-demand schemes save substantial power and network traffic. Periodic signaling in table-driven schemes not only consumes more power, but also causes network congestion. The paper later discusses the possible challenge and application in the future and proposes an interesting idea of coexistence of table-driven and on-demand mechanisms. Thoughts: Mobility and churn are important characteristics of sensor network. In many schemes discussed in the paper, these problems are addressed by using different techniques. However, the application or theoretical results have not been compared. The paper does not provide a measurement for mobility and churn. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Summary: This article proposes a new way of communication for sensor networks. The data is gathered using directed diffusion paradigm. Different from previous protocols, it is a data-centric paradigm. Data generated by sensor nodes is named by attribute-value pairs and a node requests data by sending interests for named data. Each related node send matched data towards the node requesting the data. Several novel features are integrated to the scheme, like reinforcement-based adaptation and in-network data aggregation and caching. Features: > Directed diffusion is more energy saving than previous schemes by selecting empirically good paths and by local caching and processing. > Under network dynamics, directed diffusion mechanisms are still stable. Best, -- Larry From: Simon Krueger [skruege2 SpamElide] Sent: Tuesday, March 01, 2011 11:25 AM To: Gupta, Indranil Subject: 525 review 03/01 A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks, Elizabeth M. Royer, Chai-Keong Toh The core idea of this paper is two present two different routing techniques (table-driven and source-initiated (demand-driven)) for ad-hoc wireless networks. Ad-hoc wireless networks are networks that have no fixed direct path and are often arranged in an arbitrary positions. Table driven approaches try to maintain a routing table that contains routing information to each and every other node. Source-Initiated (On Demand) routing calculates routes from source to destination as they are needed. This paper doesnt mention energy conservation of the routing protocols as this is something that is in important in todays wireless sensor networks research or any other device with a finite power supply. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks, Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin The core idea of this paper is to explore a new communication paradigm for wireless sensor networks called directed diffusion. Directed diffusion is used to relay data centric information to a sink location by aggregating data amongst intermediate nodes. Data to be collected is specified in interests which describe the type of information to collect, the interval, duration and area to sensor. This data is then forwarded back with data containing the specific type found, the location, its intensity, the confidence and a type stamp of when it was found to the sink sight or the one that requested the interest. Simon From: Tengfei Mu [tengfeimu SpamElide] Sent: Tuesday, March 01, 2011 11:17 AM To: Gupta, Indranil Subject: 525 review 03/01 1. A review of current routing protocols for ad hoc mobile wireless network This paper reviews several ad-hoc routing schemes. These schemes fall into two categories: table-driven and source initiated on-demand routing. DSDV, CGSR, and WRP are examples of the table driven routing protocols. AODV, DSR, LMR, TORA, ABR, SSR are examples of the source initiated on-demand routing protocols. The table-driven routing protocols attempts to maintain consistent routing table with periodic route updates. The routing information is up-to-date and always available regardless with need. However, this protocol incurs significant update traffic and power consumption. On the other hand, the source initiated on-demand routing protocols discovers route only when source requires. The route maintains until the destination is inaccessible along every possible path or it is no longer necessary. Pro: This paper gives an comprehensive comparison and analysis of the ad hoc routing methods. Con: 1. This paper is relatively old so that it does not cover many recent routing schemes such as flow-oriented routing, adaptive routing. 2. This paper does not talk about energy efficient routing protocols. 2. Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones This paper proposes the use of data packets to estimate the link characteristics in 802.11b networks. Specifically, it designs a data-driven routing protocol LOF, which estimates link quality based on data traffic, and it chooses routes by way of a locally measurable metric ELD, the expected MAC latency per unit-distance to the destination. The results show that LOF reduces end-to-end MAC latency by a factor of 3 and enhances energy efficiency by a factor up to 2.37. Pro: 1. The paper shows that several factors could affect the quality of the channel estimated in 802.11b networks. 2. LOF is flexible: it can be used either on a beaconless geographic routing with static nodes, or with ETX path metric. It also has the potential to be applied to be applied to other sensor networks such as those using IEEE 802.15.4 radios, since temporal correlation in link properties also leads to estimation inaccuracy in these networks Con: 1. The paper didn’t show that how fast the LOF method can converge in network with loops. From: nicholas.nj.jordan SpamElide on behalf of Nicholas Jordan [njordan3 SpamElide] Sent: Tuesday, March 01, 2011 11:11 AM To: Gupta, Indranil Subject: 525 review 03/01 Nicholas Jordan njordan3 3/1 A review of current routing protocols for ad hoc mobile wireless networks: This paper examines the several techniques to ensure efficient routing in an ad hoc wireless routing setting. The paper divides the routing techniques into two categories table driven and Source – Initiated On-Demand Routing. Table driven protocols are basically allow each node to have a complete view of the best way to get to every other node in the network. Even when the network topology hasn’t changed some still generate network traffic. Also, some of this traffic is updated to destinations that a receiving node doesn’t care about. This scheme consumes unnecessary power in sending and receiving messages. These protocols aren’t suitable for nodes with a power constraint such as motes. One of the schemes is Clusterhead Gateway Switch Routing(CGSR), scheme classifies nodes into three categories cluster head, gateway and regular node. A cluster head node is in charge of the routing for a cluster of nodes. A gateway node is a node that is in communication range of two cluster head nodes and essential links the two clusters. A regular node is neither the above mentioned two. In any given path excluding the source and destination nodes, the intermediate nodes are always cluster head, gateway node, cluster head, gateway and so on. In the paper example of a path from node label 1 to 8. The path is 1,2,3,4,6,7,8. But in this example, it seems to be a better choice to route to 3 from 1 instead of 1,2 and then 3. This scheme doesn’t really take into account individual distance between nodes, and puts a lot of burden on the gateway and cluster head nodes. One metric to take into account when electing cluster head and gateway nodes is battery power left, but you would have to check on some time period, which node has the most power to take on the burden routing messages for a cluster. On the other spectrum is Source-Initiated On-Demand Routing which takes on the two principles discover routes as needed, and delete stale routes. Unlike in the previous table driven class of schemes, these scheme only try to find a route to a destination when it needs it. If A never needs to talk to B then, A will never have an entry in its table. It won’t waste time on finding or updating the best way to get a node its not interested in. Each scheme has a timer on entries in its table, nodes in an ad hoc network change position or could no longer be available. The premise is if an entry is really old, most likely intermediate nodes have changed positions and this route may not be the quickest way to the destination. Because the network traffic is only generated when nodes absolutely need the information, this is better suited for nodes with power constraints. Each scheme accomplishes this is different ways. This category can be broken further into two subcategories, schemes with Qos and non Qos. The schemes that take into account on routing more than just distance such as stability of nodes Associative Based Routing(ABR) and the nodes signal strength Signal Stability Routing(SSR) are the Qos Schemes. SSR first tries to find a route where all the nodes have a strong signal strength and then if can’t find such a route, then allows nodes in the path with a weak signal. If this is in an environment where fast transmission is everything, doing two network discoveries seems wasteful. On the other hand, if a lost transmission due to sending a message through a weak signal node is very costly, this scheme works. They paper didn’t really go into the implementation details of how Temporally Ordered Routing Algorithm(TORA) handles a node link failure. It did mention that TORA assumes all nodes are have synchronized clocks via GPS, and its uses the time outs for count to infinity problem. I feel that is cheating and not solving the core weakness of a routing protocol. Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones: This paper evaluated the effectiveness of determine your neighbor to route to in a wireless sensor network based on an new metric MAC latency instead of the standard beacon broad cast based schemes. The traditional beacon based schemes periodically send out a broadcast and use the response of these broadcasts to determine the which neighbor to route to. The paper explains how poor of a metric this is. The main points are that most sensor networks are event driven. So there will little traffic and then an event triggers a lot of traffic. The beacon based routing, took samples of the network when there was little traffic and this information is not accurate to the conditions of when a burst of network traffic happens. While LOF basically, every time a message is sent, it records the latency of that transmission and fine adjusts its metric to route to that neighbor. As more and more traffic happens, the metric for its neighbors are changed accordingly so the metric is fresh compared to the traffic on the network. When there is no traffic, there is no need to adjust the routing parameter. They proved in another paper that there is a strong relationship between MAC latency, energy consumption and link reliability. Which is interesting and their results back up this claim. Their protocols have 3x less latency their beacon based counterparts and consume 2.37 less energy. The second result follows naturally. I really don’t have any criticism of the way of using MAC latency as guide to determine which neighbor to route to. It’s a natural progression considering the power constraints of motes. The beacon based seems really rigid and not dynamic at all. However, on page 5 the first bullet under remarks they mention that they can’t take into account Reciever Signal Strength Indicatior (RSSI), Link Quality(LQI) and Singal to Noise Ration(SNR). They said that they would like to take into account these metric because they are related to link reliability because its difficult to use them in a precise prediction tool and the receiver can only fetch these parameters. They assume that you have to send it using additional control packets to the sender. However, in this scheme you already send back an ACK packet, that’s how they measure latency. Would it be too much to attach these metrics along with the ACK packet? In the future, work they said that would study the impact of data-driven routing and security. The main reason to use data-driven routing is less power consumption, but you are not sending unnecessary packets across the network to maintain your best routing neighbor information so your network presence is only exposed when your communicate instead of all the time when whether your idle or active. -- Thanks, Nick Jordan From: mdford2 SpamElide Sent: Tuesday, March 01, 2011 10:18 AM To: Gupta, Indranil Subject: 525 review 03/01 A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks The paper splits the routing protocols it reviews into two broad categories; table-driven and source-initiated. Table-based routing: Every node knows the path to every other node, and thus, scaling becomes an issue. Destination-Sequenced Distance-Vector Routing (DSDV) is based on the Bellman-Ford algorithm, but removes loops. Routing tables are periodically updated through a full dump of the table, or via incremental updates. Routing is based on the minimum number of hops to the destination. Clustered Gateway Switch Routing (CGSR) requires nodes to form clusters and route through their cluster head nodes, or gateway nodes between clusters. Using a least cluster change algorithm results in minimal routing changes. This allows for slightly more flexibility, but is just building a hierarchy on top of the underlying issues. Wireless Routing Protocol (WRP) also maintains information for all nodes in the network, but it uses four tables to do so; distance, routing, link-cost and a message retransmission list. Source-initiated routing: Paths are constructed on demand. This reduces the number of table entries, but requires a high link-setup cost. Ad Hoc On-Demand Distance Vector Routing (AODV) is an extension of DSDV that uses path discovery to find routes. Nodes that are not on the selected route do not maintain routing information. Dynamic Source Routing (DSR) caches path information for all nodes that a node is aware of. This can reduce the link start-up cost if another node communicated with the destination and the node is aware of it. Temporally Ordered Routing Algorithm (TORA) is based on link reversal and limits control message spread to nodes that must switch their link direction before an alternate path can be found. Associativity-Based Routing (ABR) defines a new metric; degree of association stability, and routes along paths with a high degree of stability. Signal Stability Routing (SSR) routes based on signal strength and location stability. The authors do a very nice job of summarizing each of the many routing techniques, and their table comparisons are adequate. They refrain from making broad statements or pushing a single routing scheme. Instead, they leave the reader to make the choice based on their domain. Mostly, it feels like a plea for more research in the area. ? Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones Previous routing protocols used broadcast beacon strength to estimate link quality. This is a poor indicator as broadcast and unicast differ in packet size, transmission rate and MAC layer coordination. In short, updating link status information based on measurements made during actual communication provides a better estimation that measurements made during communication for the sake of measurement. The authors suggest a new routing metric; expected MAC latency per unit-distance to the destination. They modify the linux kernel to attain access at the MAC layer, and deploy their system on one indoor and one outdoor testbed. Their revised routing has some interesting advantages such as increased sleep time. Unfortunately, their work requires a very static node layout, and therefore is unsuitable for more mobile applications. Additionally, their node placement is rather suspect. If a node can communicate with 15 of its neighbors, there is a very high probability that messages need not be routed through specific nodes. I don't think that this accurately represents typical use cases, or helps support the algorithm. From: mark overholt [overholt.mark SpamElide] Sent: Tuesday, March 01, 2011 2:21 AM To: Gupta, Indranil Subject: 525 review 03/01 Mark Overholt CS525 03/01/2011 Directed diffusion: A scalable and robust communication paradigm for sensor networks Summary: The paper introduces a new routing paradigm for sensor networks: directed diffusion, a data-centric communication mechanism in which various nodes in the network use attribute-value pairs to determine how data is to be routed in response to an interest. Directed diffusion is an algorithm that labels any data type, and then only tries to send data of that type to nodes that are interested in that data type. This is to prevent nodes from receiving unwanted data, and thereby using resources that they otherwise would not have expended. They are projecting that sensor networks will, in the future, have the capability to run application specific logic, as compared to the current simplistic read and send data to a central content manager. In doing this they allow the nodes to perform on the fly data aggregation to provide the best or most recent information to the requester. The use of application logic in the sensors allows them to create a unique routing scheme, and path reinforcement algorithms. Their evaluation shows that the diffusion paradigm has the potential to provide extensive cost savings as compared to a multicast methodology. Discussion: Pros: Directed diffusion introduces a new communication paradigm in which data is no longer separated from the network, as emphasized by the layered OSI model. It shows that doing this can be an efficient method of transfer of data in sensor networks. Each node in the network is essentially communicating with just its neighbors and there is no concept of end-to-end connectivity. This allows for fast local recovery of links helping in tolerating failures. This paradigm seems to be a robust system, even in light of a 20% node failure rate. Cons: This scheme requires a node which wants to collect the data to express an interest. While this might be suitable for certain applications, it might not be in applications like continuous temperature monitoring (where there is a central node) where expressing interests would just lead to additional overhead. Factors like link quality etc can be taken into account for the reinforcement mechanism which might result in potential benefits and better performance. While the proposed application of the sensor network would benefit from this routing, I don’t believe all sensor networks would see gains from this paradigm. Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones Summary: The authors present a data-driven link estimation algorithm, LOF (Learn on Fly), which aims at estimating link quality and hence taking routing decisions, on the fly, based on data traffic. The authors argue, based on experimental data, that the commonly used technique of estimating unicast links via broadcast beacons fail in case of sensor networks where traffic is mostly in bursts. Hence, they propose relying on MAC feedback when transmitting unicast packets to measure the goodness of a nodes link to its neighbor. To do this, they define a routing metric, ELD (Estimated MAC latency per unit-distance to the destination) based on geographical distances between source and destination. When using this metric, a node tends to choose nodes beyond the reliable communication range as forwarders, and reduce the end to end MAC latency and energy consumption. The nodes initially obtain the geographical location of its neighbors and the base stations. They then perform an initial sampling to learn roughly about the link qualities to their neighbors. The nodes then adapt their routing decision or next hop based on the MAC feedbacks from successful data transmissions to neighboring nodes, when the sensor network is active. The LOF also provides for probabilistic neighbor switching since some good links may be missed because they did not perform well in the initial sampling phase. The authors back up their claims about the energy efficiency and low latency of the algorithm via indoor and outdoor experiments. Discussion: Pros: The routing metric used, MAC latency, takes into account important sources of concern in a sensor network, such as energy efficiency, link reliability and low latency. The paper shows that several factors can affect the quality of the channel estimated in 802.11b networks and thus concludes that using broadcast beacons to measure the quality of the channel experienced by regular data packets would be misleading. Cons: In case of network congestion, the MAC feedbacks may further unnecessarily use up network resources. The nodes have to compute the metric and keep updating its next hop dynamically with each MAC feedback. This may lead to using up a lot of computing resources, which may especially affect nodes with low computing resources such as sensor nodes. From: Shen LI [geminialex007 SpamElide] Sent: Tuesday, March 01, 2011 12:36 AM To: Gupta, Indranil Subject: 525 review 03/01 Name: Shen Li Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks This paper proposes the idea of directed diffusion paradigm for wireless sensor networks. In their design, the network transforms operator's query into interest which will be diffused towards a specific region that the operator cares about. Then, the sensors in that region start detecting corresponding event. When such an event is detected, the information will be sent back along the reverse path of interest propagation. Intermediate nodes might aggregate data to save energy by combine reports from several sensors. One important feature of their approach is that all data propagation and aggregations are processed according to local information only, so that the overhead of such actions can be relatively low. Pro: 1. I am not sure whether it is the first paper to propose the idea of data diffusion. If so, the influence of this paper is profound. It actually inspired the revolution of future Internet which tries to modify the IP based Internet to a data based Internet. About 10 years later since this paper published, we saw researchers publish paper in SIGCOMM[1] and CoNEXT[2] to discuss data-oriented network. Con: 1. Internet researchers also borrow the idea of caching data inside the network proposed in this paper. Actually, I think it is more suitable to do caching in Internet environment rather than sensor network environment. First, due to wireless nature and wild area environment, the link state between two node changes from time to time. So, direct a interest to a neighbour which previous processed corresponding data may not be the best solution at the current time point. Second, as talked in this paper, the event monitoring tasks usually last a short period of time. So the cache neighbour may not be in charge any more. And direct the interest to that node will lead to longer path. References: [1] Data-Oriented Network Architecture (Koponen, SIGCOMM 2007) [2] Networking Named Content (Jacobson, CoNEXT 2009) Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones This paper proposes to estimate unicast link properties directly via data traffic itself instead of using periodic beacons. They introduced a new metric ELD, which is, expected MAC latency per unit-distance to the destination. They argue that optimizing MAC latency would also optimize energy efficiency. Under this metric, every forwarding will make progress by reducing the destination to distance. Each time, the sender will choose the node with lowest delay over distance progress as its forwarder. Pro: 1. According to their argument, using data packets themselves to estimate link quality will both better reflect reality and reduce energy usage. 2. This paper also provides a new metric which focus on energy efficiency instead of the estimated transmission time used by ETX. Cons: 1. Their approach also calls for control packets and sample packets to initialization the network. And as they mentioned, most of the time sensor network will stay in idle status, i.e., no interest event happen and there will be no packet inside the network. So, in this case, the topology build by the initial control packets may be out-of-date. I guess, in real wild area applications, they will also need to employ periodical control beacons to keep the whole network connected. 2. The ELD metric they proposed in this paper calls GPS capable sensors which can be much more expensive than simple wireless motes like Telos or Iris. Question: 1. They mentioned in Section II-B that unicast packet achieves better delivery rate because of retransmission. So, what if the retransmission function is removed. Will the unicast still outperform broadcast? From: trowerm SpamElide on behalf of Matt Trower [mtrower2 SpamElide] Sent: Tuesday, March 01, 2011 12:35 AM To: indy SpamElide Subject: 525 review 03/01 Learn on the Fly Learn on the Fly presents a new link estimation metric and routing protocol for sensor network backbones. The sensor network backbone has higher bandwidth requirements than that of sensor networks which allows for the use of 802.11 rather than the typical 802.15.4 radios. The authors show that for GPS-enabled devices they can provide a 300% improvement in latency for packet delivery. In the first part of the paper, a case is made for the use of in situ link measurements over periodic sampling. Traditionally, broadcast protocols are used to test link qualities for a given node in the network. The argument is based on results that show unicast is more reliable under certain constraints. The results showed this at 3.64 and 5.46 meters. It is not clear this data is meaningful for 802.11 networks which were shown to support reliable transmissions at over 400 meters. Instead of using multicast, latency estimates are derived from MAC layer acknowledgements to data packets. Again an argument is made against RSSI measurements being one way measurements which is also true of the chosen latency measurements, making their choice seem ill-supported. The routing protocol is similar to other geographic routing protocols except that it assumes well connected networks (greedy algorithm). In the results, the MAC layer latency is compared amongst protocols. It isn’t clear that the MAC layer comparison is fair between ETX and LOF. ETX is aimed at 802.15.4 deployments which will beat 802.11 in power every time. The idea of using link estimates already available in the network is nice albeit not new. Review of Routing Protocols for MANET Royer and Toh provide in their paper an overview of the current state of ad hoc mobile wireless routing protocols as of 1999. The paper includes descriptions and comparisons of 8 different protocols and generalizes the protocols into two groups: table-driven and on-demand. A table-driven protocol is similar to traditional wired routing protocols in that a route is computed for all hosts whether it is needed or not and is also commonly known as proactive. This produces high overhead with low latency assuming the network is sufficiently stable. DSDV is the most well-known of these protocols. The second type is source initiated, on-demand or reactive routing. This scheme is based upon nodes building routes when data packets arrive to be routed. This provides the opposite benefits as table routing protocols with low overhead and high latencies. AODV and DSR are the most common incarnations of this philosophy. Many of the protocols try to track the mobility of nodes to balance the tradeoffs between the two design philosophies. This review has grown quite dated and is now missing interesting topics such as power-efficiency, QOS, and geographic routing. Certain protocols also could have been omitted as they add little more than historical perspective. From: Qingxi Li [cs.qingxi.li SpamElide] Sent: Tuesday, March 01, 2011 12:05 AM To: Gupta, Indranil Subject: 525 review 03/01 Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks This paper introduces a data-centric sensor networks. In Directed Diffusion, all the data will be transferred to an object which includes type, instance, location, intensity, confidence, timestamp. The node requests data by generating the interests of data which includes type, interval, duration, rect. Interval is the frequency to send data back and rect is in which rectangle this event happens. This interest will be send to all the nodes in that region and the intermediate nodes will aggregate the data. Up to now, there are two problems. Firstly, all the variables in interests or the detected object need in a value range. This value range cannot be too detail since the sensor cannot detect things very clearly, how can a sensor to separate the tigers and lions. It also cannot be too rough since users need it to describe the events. Authors put this into future work. Another problem is that the intermediate nodes need to store the information of the interests, if there all too many interests, the sensor nodes will run out of their memory as they only has a few tens MB. (Maybe this is not a problem, I’m not sure about that.) For reinforce one path, the start node will broadcast a large interval firstly, then for the path it wants to reinforce, it will give a smaller interval in that path. Interval should be changed carefully; otherwise, two neighbors of one node may always have conflict. Interests are distinct if their type, interval is different or the rect are disjoint. And the same interests can be combined. I think as the combined interests can have different sink node which is the start node, it can also have the different interval. This makes more interests be combined and save the sensors’ memory and search time. Besides this, for the example given in Section 3.2, the expiresAt is much later than it should be. This can increase the cache’s hit rate, however, it wastes a lot energy, time and other resources of the sensors to collect useless data. The node will suppress the data is it recently send a matching interest object. For the interests with same type and different interval, like two interests one with interval as 1s and that of the other one is 2s. The node may only transmit every two event toward the corresponding neighbor or it might interpolate two events as application-specific way. The way the nodes transmits the data back is flooding or by geographic routing. The previous one is cost and the later one need GPS and may not always be successful. A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks Table-Driven Routing Protocol: each node need to maintain tables which store the routing information. Different protocol has different number of routing tables and different ways to broadcast the changes in the network. I think the problem of these protocols is that all the nodes need to stores all the information about the whole network. This will needs a lot of memory and maybe much of this information will be useless for the node. Destination-Sequenced Distance-Vector Routing: (DSDV) basic routing protocols for many other protocols like CGSR. It only has one routing table with all possible destination nodes with the number of hops. Each entry has a sequence number assigned by the destination nodes to avoid routing loops. The update method includes two types of packet, full dump and incremental. Full dump includes all the routing information and be sent less frequently. Incremental only includes the update information and be sent more frequently. New route broadcast with broadcast ID, seq. No. assigned by the destination nodes, destination nodes and the number of hops. Clusterhead Gateway Switch Routing (CGSR): Cluster head will be chosen by a distributed algorithm within the cluster iff two cluster heads come into contact or a node moves out of contact of all other cluster heads. CGSR uses DSDV as the underlying routing scheme. For sending packet, all the packets will be forward to the cluster head and then be sent to the corresponding gateway node which will forward this packet to the next cluster head. Each node should keep a cluster member table which will map node to the cluster head of the cluster it belong to and a routing table which is used for detecting next hop. I wonder whether all the nodes should keep this information. I think only the cluster head need to keep this information. For the normal node, its next hop is always the cluster head and for the gateway node, the next hop can be given by the cluster header. And the cluster member table can only be used by the cluster head node. The Wireless Routing Protocol (WRP): Each node need four tables: distance table routing table, link-cost table, message retransmission list table. A hello message is used to detect whether this link is still working. It forces all the nodes to check the predecessor information reported by all its neighbors to avoid looping. Source-Initiated On-Demand Routing (only include DSR here since not much more space) Dynamic Source Routing (DSR): route discovery: broadcasts a route request packet, includes the address of the destination, source node’s address and a identify number. Each node receives this packet will check whether it has the route to the destination if it didn’t receive it before, if not, adds its address to the route record of the packet and forwards it to neighbors. If have the route to the destination or the node is the destination, returning route reply. This requests symmetric links or the destination node has route to the source, otherwise, it will initial the route discovery. For maintaining route, route error packets are generated if find the transmission error. After route error being generated, the routes include this link will be remove by all the nodes. I think this process will be cost since all the source node whose route has been deleted should reinitialize the route discovery, especially if this link is just unstable, and it comes back to work soon. The failure of the links discover by acknowledgments which includes passive acknowledgment where a node hear its neighbor sending packets. From: Nipun Sehrawat [sehrawa2 SpamElide] Sent: Monday, February 28, 2011 2:51 PM To: Gupta, Indranil Subject: 525 review 03/01 A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks An Ad Hoc network is characterized by set of dynamic nodes, whose location varies with time. This literature review presents various Ad Hoc routing protocols, which are mainly divided into two categories - table-driven protocols and source-initiated on-demand protocols. An important consideration in Ad Hoc networks is to avoid loops in the routes discovered to the destination. Table-driven protocols are characterized by presence of up-to-date routing information at each node, to every other node in the network. Each node in the system maintains a set of "tables" for recording the route information, which is updated periodically. Most of the table-driven protocols are "flat" i.e. no hierarchy is involved in route discovery and maintenance. Cluster-head Gateway Switch Routing (CGSR) is a hierarchical table-driven protocol. Nodes are divided into clusters and each cluster is assigned a cluster head. A cluster head is elected using a distributed algorithm within the cluster. Each cluster also maintains a gateway node. When a node wants to transmit a packet, it sends the packet to its cluster head, which forwards the packet to gateway for the next cluster head en-route the destination's cluster head - the final cluster head has the routing information of the destination node. This protocol might suffer degraded performance if cluster heads are too dynamic - the nodes will be busy selecting a new cluster head most of the times. Destination-Sequenced Distance-Vector Routing (DSDVR) protocol adopts a modified Bellman-Ford algorithm to avoid loops in the routing information. It also uses an anticipatory protocol where nodes do a delayed broadcast of routing updates, hoping that a better route will be discovered in the near future. The Wireless Routing Protocol (WRP) dictates the nodes to send route updates only to their neighbors, instead of broadcasting. WRP avoid the count-to-infinity problem by maintaining the second-to-last hop information for each (destination) node. Source-initiated On-demand routing protocols are characterized by the "on-demand" route discovery by the source node. If the route to a destination node is not known, the source node initiates a route-discovery. It must wait for a discovery reply before sending the data. The Ad Hoc On-Demand Vector Routing (AODV) protocol involves the source node sending a route request packet which is recursively broadcasted by intermediate nodes, until either the destination or the node having the route information to the destination are encountered. TORA is a protocol suited for highly dynamic networks - it tries to localize of control messages to a small set of nodes that are near the occurrence of change in the topology. It operates by forming a DAG rooted the destination node, for route discovery and assumes synchronization of nodes' clock - which might be difficult to achieve. Associativity-Based Routing defines "association stability" as a new metric (each node periodically generates a beacon to show its presence), which is governed by association stability of two nodes over space and time. A high stability indicates a stable neighbor node. The route is chosen to maximize the associativity along the route. Signal Stability routing uses signal strength and node's location stability to select a route with highest connectivity. 1. Table-Driven protocols: Pros: - Routing information is always present, thus reducing the latency to initiate a connection. - Desirable in n/w where most nodes communicate to most other nodes, as route to all other nodes is known beforehand. Cons: - Route updates done periodically, even if nodes not communication - Route to all other nodes calculated, resulting a high nw/ traffic and power consumption. 2. Source initiated On-demand: Pros: - Only paths to frequently communicated nodes are maintained. - It is event-driven and shall be more effective in case of sparse communication Cons: - Source must wait for the route discovery to complete before communicating to a new destination node. ---- Directed Diffusion: A scalable and Robust Communication Paradigm for Sensor Networks This papers studies the case of data-distribution (called directed diffusion) paradigm among a set of sensor nodes collectively performing a distributed sensing. Direct diffusion differs from IP style communication by having a hop-by-hop communication instead of end-to-end one. One of the reasons behind this is to preserve battery power wasted in direct long-range communications. The authors argue for a distributed computing system like sensor network where, for every given task, the nodes collect a reduced rate of samples and exchange information with their neighbors to refine the sampling estimation. The main goals of such a setup are scalability with number of sensing nodes, fault-tolerance in case of failing nodes and to minimize the energy consumption by the sensor nodes involved. "Interests" are defined as task descriptions that specify nodes to gather data matching a given attribute (such as checking for presence of a vehicle). To get information about a particular event, an interest description is created and injected in one of sensor nodes (called the "sink"). The sink node is responsible for broadcasting the interest to its neighbors which themselves might multicast the interest to a set of their neighbors. For the indirect neighbors, the original sink is unknown, resulting in a local interaction. The sampled data flows back to the sink and might be aggregated by intermediate nodes. The sink hands over this data to the querying entity. Such a setup doesn't feature any routers and every participating node (are generally near to the phenomenon to be sensed) can cache, process and aggregate the collected data - leading to a coordinated sensing. Pros: - Nodes don't need to keep track of routes to all other nodes as they only communicate to their neighbors - As done in source-initiated routing, nodes don't need to wait for a path to be setup before communicating to their neighbors. - Dynamic Reinforcement of best performing neighbors results in dynamic adaptation to the empirically best-path for sensing. From: iitb.ankit SpamElide on behalf of Ankit Singla [singla2 SpamElide] Sent: Monday, February 28, 2011 9:11 AM To: Gupta, Indranil Subject: 525 review 01/03 1. Learning on the fly ------------------- Summary: The paper starts out with arguments for why use of probing based estimates of broadband transmission quality between peers is not reflective of the link quality unicast connections will experience under rare, bursty traffic events. This estimation is not only inaccurate, it uses valuable energy resources. They present convincing results about the inaccuracy of the broadcast-based link-quality estimation and instead propose use of data-driven estimation. They use recent MAC-layer history of a connection as an indicator of its performance in the near future, using as a metric the expected MAC latency per unit distance to the destination (referred to as ELD). They use this metric to pick routes to the destination. The metric is updated based on the data traffic’s experienced MAC-layer characteristics. Regularly, paths through other neighbors are tested to check for better routes. Comments: I doubt that their metric will work well in more heterogeneous environments. It might sometimes be beneficial to send the data to a node further away from the destination than the source because this intermediate node might have a better range or quality of transmission to the destination. They do propose another metric (ELR) but show that it is inferior to the ELD metric in their limited experiments. I also wonder how different their approach to path adaptations is from the theoretical model (due to Robert Kleinberg?) named the ‘multi-armed bandit’. 2. Directed Diffusion ----------------------- Summary: This approach to routing is fundamentally different from the host-to-host model around which IP has built its success. Interest packets are flooded to the network and multiple nodes through the network respond to these interests by way of replying with relevant data packets. These data packets can be aggregated, processed, cached etc. by intermediate nodes in the network. Comments: Having followed closely the content-centric networking work by Van Jacobson (who’s acknowledged in this paper), I was somewhat surprised to find that this paper had similar key ideas having appeared almost a decade earlier. I’ll also note that I find their application scenario to be much more realistic than Van Jacobson’s ‘change the Internet’ proposal, primarily because of routing scalability, but also due in large part to the economics issues the latter proposal involves. A major benefit the directed diffusion model has in its relevant setting, is that neighboring sensors are indeed highly likely to see similar events. I’m a little concerned about the timing of events in the network – do intermediate nodes wait for many sensors to respond before they start the aggregation? f so, how do they decide when to stop waiting? Also, there seems to be an issue with caching: which copies of data are the latest? (Unless nodes are synchronized closely, this is not an easy question to answer). While the paper seems to make an argument for energy efficiency, it is unclear to me that flooding interest packets and fetching multiple copies vs. the in-network-aggregation really works out as an energy gain overall. I don’t think the paper’s experiments make a definite case in favor of this argument. Ankit -------------------------------------------------------------------- Ankit Singla Graduate Student, Computer Science University of Illinois at Urbana-Champaign (UIUC) http://www.cs.illinois.edu/homes/singla2/