From: Giang Nguyen [nguyen59@illinois.edu] Sent: Thursday, February 25, 2010 12:25 PM To: Gupta, Indranil Subject: 525 review 02/25 CS 525 paper review 02/25 Giang Nguyen nguyen59 Directed diffusion: A scalable and robust communication paradigm for sensor networks The authors argue that the communication model of wireless sensor networks is data-centric, and present a a new data dissemination paradigm called directed diffusion, wherein data generated by sensor nodes is named by attribute-value pairs. One of more nodes in the network, called sinks, are interested in such data and send out messages informing other nodes of their interests in data that match a certain pre-configured pattern. The nodes that receive these interest messages, and when they detect an event matching the interested data pattern, they unicast the data towards to nodes from which they received the interest message, those nodes then do the same thing, and the data eventually reaches the original sink node(s). The sink nodes, at this point, initiate “reinforcement”: sending the same interest message but with higher data/interval rate, requesting that their immediate neighbors to send at higher rates, and those neighbors in turn propagate the messages, eventually to the nodes that detect the event, to sample and send data at the higher rates. The intermediate nodes employ optimization techniques to save energy, such as combining multiple data messages and dropping data messages in which they have no interest. The authors use simulation to show that their proposal is better than a flooding scheme and omniscient multicast scheme, in terms of average energy dissipation, delay, etc. They also evaluate those metrics for their proposal in the face of node failures and conclude that their scheme is fairly stable—does not degrade significantly—under node dynamics. Pros: Performs better than flooding and multicast schemes in terms of expended energy and delay. Is robust in the face of 20% node failures. Cons: Only simulation, which modifies the MAC layer to reduce energy model. The examined application is location detection, potentially not applicable to all other sensor network usages. Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones In wireless sensor networks, a typical application is monitoring an environment. When an event occurs, the sensor nodes send and route data messages towards a base station. Route selection depends on accurate estimates of link quality, something the authors show by experiments is difficult to achieve if relying on periodic broadcast. The reason is wireless link quality varies both temporally and spatially in a complex manner as shown by previous research. Therefore the authors propose extracting link quality information from data packets. They propose a metric called “expected MAC latency per unit-distance to the destination” (ELD), based on both the MAC latency and geography. The high level idea is, for a sender S and a neighbor R that is geographically closer to destination D, S calculates the ELD metric of R by dividing the MAC latency between S and R by the “effective geographic progress” towards D (which is distance from R->D subtracted from distance from S->D) if S forwards to R. Then S chooses the neighbor with the lowest metric as the next-hop forwarder. (However, because the MAC latencies are estimates, S also probabilistically switches to other neighbors as next-hop forwarders.) With the metric ELD, the routing protocol (LOF for Learn on the Fly) requires the each node to know its location to know its distance to the base station. The protocol achieves this via a broadcast mechanism each node initiates when it first boots up to announce its presence and also learn the identity and location of neighbors and the base station. Second, since data messages are only sent when there is an event, the protocol needs estimates of the MAC latencies before that. It achieves this via “initial sampling”--sending several unicast data-sized messages to each neighbor the node comes to know about. This gives the node a rough initial estimate of the MAC latencies to its neighbors, allowing it to calculate the neighbors' ELD metrics. These estimates are later kept updated using exponentially weighted moving average when there are data packets. The evaluation focus on two main criteria: end-to-end MAC latency and energy efficiency. The authors use an indoor 195-node grid testbed to compare with distance-vector protocol ETX and geography-aware protocol PRD. For end-to-end MAC latency, LOF is 3 times better than these protocols. In terms of energy, the authors indirectly compare the number of unicast transmissions per “good” received packet, and LOF is 1.5 to 2.4 times better. Cons: Why not directly comparing energy efficiency, instead of indirectly comparing unicast transmissions per received packet? In the MAC latency comparison, the authors have a statement “tend to suggest that the network state is heterogeneous at different locations of the network.” This is not convincing because they are using an indoor grid testbed. Geography-aware routing requires each node to know its location, thus requiring GPS device for increased cost and energy usage. It'd be interesting to study/adapt this protocol on a mobile sensor network, where the nodes move around. From: Ghazale Hosseinabadi [gh.hosseinabadi@gmail.com] Sent: Thursday, February 25, 2010 12:22 PM To: Gupta, Indranil Subject: 525 review 02/25 Paper 1: A Review of Current Routing Protocols Ad Hoc Mobile Wireless Networks In this paper eight routing protocols for ad hoc mobile wireless networks are presented. The protocols presented in this paper are as follows: 1) Destination-sequenced distance vector raouting, 2) Clusterhead gateway switch routing, 3) The wireless routing protocol, 4) Ad hoc on-demand distance vector routing, 5) Dynamic source routing, 6) Temporally ordered routing algorithm, 7) Associativity-based routing, 8) Signal stability routing. The first three protocols are table driven routing protocols while the others are source initiated on-demand routing. Comparison of table-driven protocols is also presented in this paper. The parameters that are compared are as follows: time complexity (both initialization and postfailure), communication complexity (both initialization and postfailure), routing philosophy, being loop-free, supporting multicast, beaconing requirements, multiple route possibilities, routing metric, ... . On-demand protocols are compared based on availability of routing information, routing philosophy, periodic route updates, coping with mobility, QoS support, ... . Pros: This paper presents a survey on well-known routing protocols of ad hoc wireless networks. It also campares them from different aspects. Cons: The protocols are not compared from security point of view. Comparison of power consumption of different protocols is not presented, this comparison is needed in case of sensor networks. How join and leave of nodes effects each routing protocol is also not explained. Paper 2: Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones In this paper a routing protocol called Learn on the Fly (LOF) is presented. In LOF, link quality is estimated considering traffic dynamics. The metric they used is called ELD, which is the expected MAC latency per unit distance to the destination. In previous wors, link properties are estimated considering broadcast beacons. ELD is a locally measurable metirc based on geographic locations of nodes and information related to the links associated with the source. LOF is an on-demqand protocol which is run whenever available data needs to be routed. The presented protocol is implemented on two IEEE 802.11b testbeds (One of them is indoor and the other is outdoor). End-to-end MAC latency and energy efficiency of LOF and other protocols are compared through experiments. Pros: This paper presents a new routing method for sensor networks. Nwe metric for estimating link properties is introduced. The routing method is data driven, so power in consumed because 1) periodic beacon is not sent. 2) node only wakes up only when it is needed for data generation or forwarding. Cons: There is no theoretical analysis proving why ELD performs better comparing with other estimation parameters (such as the well-known SNR method). Link estimation is done so often and in a static network it imposes too much unnecessary overhead. From: Shivaram V [shivaram.smtp@gmail.com] on behalf of Shivaram Venkataraman [venkata4@illinois.edu] Sent: Thursday, February 25, 2010 12:20 PM To: Gupta, Indranil Subject: CS 525 review 02/25 Shivaram Venkataraman 25 Feb 2010 1. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks This paper presents a communication paradigm for sensor networks nodes which is data-centric and helps in saving energy by selecting the good paths and aggregating data in-network. Directed Diffusion treats the data generated by sensor nodes as attribute-value pairs and propagates queries as 'interests' which are matched to nodes which have the data. Tasks in directed diffusion are characterised by their duration and interval at which events need to be recorded. This task is initially diffused as an 'interest' from a node called the 'sink' with an interval larger than that required. This request is forwarded, using gradients, by each node to all its neighbors. Every node maintains an interest cache to ensure that there are no loops. Sensor nodes are application aware and match the interest specified to the data recorded based on attributes like location and type of data requested. Once the data is recorded by a sensor node, it is sent back along the reverse path and the data is cached in the 'data cache'. The cache is useful for robust data delivery and operations for aggregating data can be performed at intermediate nodes. Based on the delay of the responses received, the 'sink' reinforces the 'interest' for a particular neighbor by increasing the interval at which events need to be recorded. This propagates through the network and aids in choosing the best patch from the sink to the source. If an alternate path is found to be better, the sink negatively reinforces the original path while switching to the alternate path. Thus directed diffusion differs from traditional networking by using neighbor-to-neighbor communication unlike the end-to-end nature of traditional networks. Pros: - Simulation results are better than shortest path multicast schemes . - Design choices based on the topology and energy requirements in sensor networks. Cons: - Experiences from real world deployments would be interesting to observe. - Classes of applications that may or may not be able to use intermediate aggregation would be useful. A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks: This paper presents a survey of the routing protocols which are used in ad-hoc wireless networks. The two broad categories of routing protocols used in such networks are Table-driven and Source-initiated. Table-driven protocols maintain information from each node to every other node in a routing table. The important table-driven routing protocols are: a. Destination Sequenced Distance Vector Routing (DSDVR) - This protocol is based on the Bellman-Ford algorithm and every node in the network maintains the number of hops to every other node. The information is versioned using sequence numbers and changes in routes are broadcasted. b. Cluster Gateway Switch Routing (CGSR) - This protocols uses a hierarchical routing strategy with cluster heads controlling a group of ad-hoc nodes. Each node maintains the list of cluster heads and a routing table with the next hop used to reach the destination. The protocol uses DSDVR as the underlying routing scheme. c. Wireless Routing Protocol (WRP) - In this protocol, routing information is exchanged only between neighbors using update messages and nodes calculate paths available for each destination. Node discovery is performed by sending hello messages and WRP avoids the "count-to-infinity" problem by forcing consistency checks. Source Initiated Routing protocols create routes when required by the source node. Some examples are: a. Ad Hoc On-Demand Distance Vector Routing (AODV) - Paths are discovered by forwarding route request (RREQ) packets from the source and sending replies (RREP packets) along the reverse path. AODV only supports symmetric links and routes are maintained by sending failure notification messages upstream to the source. b. Dynamic Source Routing (DSR) - Similar to AODV routes are discovered by sending route request packets, with the small difference that intermediate nodes cache the routes which are formed. Maintenance of routes is through the use of route error packets and acknowledgements are used to verify correct operation. c. Temporally Ordered Routing Algorithm (TORA) - TORA is designed for highly adaptive networks and is based on link reversal. Routes are created using the 'height' metric and links, classified as upstream and downstream, are reversed to react to a link failure. TORA is dependent on all nodes having a synchronized clock. d. Associativity Based Routing (ABR) - This protocol defines a new metric called as degree of association stability which is incremented when a beacon is received from a mobile node. Routes are discovered by broadcast query and await-reply cycles and are maintained using localized queries (LQ) process. e. Signal Stability Routing (SSR)- This protocol routes based on the signal strength between nodes and a node's location stability. Dynamic and static techniques are used for route maintenance. Pros: - Comprehensive survey and detailed explanation of different protocols. Cons: - Example applications for each protocol would have helped in their motivation. From: pooja.agarwal.mit@gmail.com on behalf of pooja agarwal [pagarwl@illinois.edu] Sent: Thursday, February 25, 2010 12:18 PM To: Indranil Gupta Subject: 525 review 02/25 DS REVIEW 02/25 By: Pooja Agarwal Paper – A Review of Current Routing Protocols for AdHoc Mobile Wireless Networks Authors - E Royer, C Toh Conference – IEEE Personal Communications, 1999 Main Idea: This paper presents a survey of routing protocols for ad hoc mobile wireless networks. The authors have classified the routing protocols into two categories : 1) Table based 2) Source/demand driven. The paper covers following protocols: Table Based : 1) Destination Sequenced Distance Vector Routing – basic protocol based on Bellman-Ford routing mechanism, in which routing table containing distance/hops to all the other nodes is maintained. 2) Clusterhead Gateway Switch Routing – a clustered wireless n/w is maintained which uses DSDV as the routing scheme within the clusters. Least cluster change algorithm is used to decide the cluster head, and cluster member table needs to be maintained. 3) Wireless Routing Protocol: maintains routing information among all nodes in the n/w by using 4 tables per node. The routing information is shared with only the neighbours. Source Initiated on demand routing : 1) Ad Hoc on demand distance vector routing – Use of RREQ and RREP messages to locate a path from a source to destination, it is a modification of DSDV requiring lesser traffic for path discovery and routing. Link failure detection information is forwarded via the neighbors to the source so that a path recovery protocol can be initiated. 2) Dynamic Source Routing – Route caches at mobile nodes to enhance route discovery. Route error packets and ack messages used to verify correct operation of links and removal of failed nodes. 3) Temporally Ordered Routing Algorithm – localization of control messages to a very small set of nodes near the occurrence of a topological change. Routing information about one-hop nodes needs to be maintained. Use of DAG, direction and height of tree to form topology graph. 4) Associatively based routing - route formation based on degree of associativity between two nodes. 5) Signal stability routing – route formation based on the quality of the signal strength and node’s location. The paper compares these protocols based on several metrics like time and communication complexity, multicast capability, whether loop-free or not, number of tables, update expense, routing metric, etc. Pros: 1) The performance parameters chosen in the paper are still relevant in the current state of the art ad hoc routing protocols. 2) The critical analysis covered mostly all the pros and cons of different algorithms. 2) Provides brief summary of all the protocols analyzed which makes reading easier for even people with little wireless routing protocols background. General Con: 1) The paper was published in 1999 so there are various other newer sensor network routing protocols which will be good to study. Paper : Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Speaker: C Intanagonwiwat,R Govindan, D Estrin Main Idea: The paper presents a data centric paradigm called Diffusion which exploits communication only between the local nodes to perform wide area sensing tasks. The data is represented using attribute-value pairs and is dealt as an interest. Any node that needs some information translates the task in the form of interests and broadcasts it to it’s neighbors. The neighbors maintain a cache which stores the various interests received from various other neighboring nodes. The interest comprises of data values, interval and duration which classifies the kind of data needed, the rate of sampling and the total duration until needed. The naighbors check their cache and if the interests serves the demand, they send the reply. If the interest is similar to some other interests than aggregation of interests is done at the node’s cache. Each interest is also associated with a gradient specifying the direction of the local node which requested this data. The gradient in a way specifies the data rate and the direction to send the data. The neighbors than contact their neighbors and through local interaction request is diffused through the network. Once the interest reaches the source node, it samples data at max rate demanded by the neighbors. During n/w traversal, the nodes can downsample the rate too to decrease the overhead or eliminate inability to transfer high rate of data. The data message is unicast to relevant neighbors. If the response is not received in a time limit the cached interest is dropped. Once the data reaches the sink(requester), sink decides upon a new sampling rate and which nodes to reinforce depending on the performance of the reply nodes. This allows for dynamic change in rate of requested data leading to both positive and negative reinforcement techniques. For local repair, intermediate nodes can also apply reinforcement techniques. Through local to local routing, the sensors attempt to reduce power, computation, and communication overheads. Pros: 1) Provides a data centric approach for sensor networks. 2) Efficiency depends on the reduction of the number of messages required to send, reduction in routing information maintenance(no global view required), and co-operation and data caching. 3) Adaptive rate control based on the responses received, avoiding unnecessary consumption of bandwidth. 4) Aggregation technique to avoid redundancy in interests jobs, similar jobs get handled together. Cons: 1) It is not clear how efficient it is in terms of hops needed to get a data. The paper does not give any bound on the number of hops needed to get data. 2) It seems there is a relation between resources used for each interest and the number of nodes that needed to be used to get that interest. So, if there are many intermediate nodes between a source and a sink, then effectively to retrieve a data, all these intermediate nodes are spending resources like power and computation for that interest. However, it could be that the net cost after summing the power and computation used by each intermediate node becomes greater than what could have been needed when the sink and source contacted through smaller number of nodes or contacted directly. Hence, some level of global information which can redirect such queries over shorter paths can be explored. 3) The paper mentions various fancy operations like aggregation, reinforcements, broadcasting, re-broadcasting which will be costly in terms of computation and power requirements. From: Kurchi Subhra Hazra [hazra1@illinois.edu] Sent: Thursday, February 25, 2010 11:43 AM To: Gupta, Indranil Subject: 525 review 02/25 Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks --------------------------------------------------------------------------------------------------------------- Summary ------------ This paper presents a new communication paradigm, termed as directed diffusion, for sensor networks involving cheap sensors that perform co-ordinated distributed sensing of environmental phenomena. To illustrate their paradigm, the authors use the example of a sensor bed set up for location tracking. A node, termed as sink, is injected with an interest, or a query for named data. The interest contains attribute-value pairs such as whose location is to be tracked, the region in which to operate, the data sampling interval and duration for which the data is desired. The sink then periodically broadcasts exploratory initial interests with low demand for sampling rate to its neighbours. These neighbours re-broadcast it to their neighbours and so on. Each node also maintains a cache of all the unexpired interests it has seen for the purpose of dropping of duplicate interests and reverse forwarding data messages sent as reply to interests towards the sink. Apart from forwarding interests, a node also activates its local sensors to see if it can sense some data relevant to any interests in its cache. If so, it sends such samples as a reply message back to the sender of the interest, at the highest demanded data rate. This reply message travel back to the sink on one or more paths. The sink will in turn reinforce the paths that give it the best response and send down negative reinforcements along other paths. The authors further present various optimizations that can be performed such as in-network processing. They also demonstrate graphically some experimental results which show the energy efficiency of their paradigm and the low latency that it offers, when compared to other routing technologies such as flooding and omniscient multicast. Pros -------- -- Directed diffusion is ideal is completely distributed and ad-hoc, and requires no central controller. The routing method depends on local interactions among various nodes in order to achieve a global task. As such, it can very well be used in unmanned sensing environments such as war fields and forests. -- Favouring the best paths over others, thus reducing the amount of data received from unfavoured path leads to conservation of energy that is highly critical in sensor networks. -- The paradigm is robust to failures and does not expend too much of energy in adverse circumstances. Cons-- --------- -- The authors have deliberately avoided the study of congestion in such networks. However, in an emergency situation, such as a forest fire, most of these sensors would be highly active and would be broadcasting a lot of messages. A study of congestion and the resultant battery lifetime of the sensors in such a situation would be extremely relevant. -- Security issues are totally neglected. A malicious node could very well advertise false information in this network, defeating the whole purpose of the sensor network. -- Consider two paths A and B from the source to the sink that converge at a point. If A is reinforced whereas B is negatively reinforced, ones effect will be mitigated by the other at the convergence point, which might lead to a failure of a very good path. -- The authors simulate the experiments. However, an actual experiment in an adverse environment would make the results more realistic. -- There are no comments provided on the average lifetime of a node when using such a routing mechanism. -- The experiments assume a constant sensor node density. However, since the routing paradigm depends on local interaction among nodes, varying the density could also have significant effects on the routing paradigm, which has not been investigated. Other thoughts ------------------- The transmission supported by the network is unreliable and results in rebroadcasting of an interest by nodes several times. This leads to wastage of energy and overloading of the network in any case. Hence, introducing acknowledgements to make the communication reliable could also be investigated. Learn on the Fly: Data- Driven Link Estimation and Routing in Sensor Network Backbones ---------------------------------------------------------------------------------------------------------------- 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 bursty. Hence, they propose relying on MAC feedback when transmitting unicast packets to measure the goodness of a nodes link to its neighbour. 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 neighbours and the base stations. They then perform an initial sampling to learn roughly about the link qualities to their neighbours. The nodes then adapt their routing decision or next hop based on the MAC feedbacks from successful data transmissions to neighbouring nodes, when the sensor network is active. The LOF also provides for probabilistic neighbour 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. 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. -- Most claims in the paper have been backed up by experimental results, and are not simply based on intuitions. 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. Thanks, Kurchi Subhra Hazra Graduate Student Department of Computer Science University of Illinois at Urbana-Champaign From: mukherj4@illinois.edu Sent: Thursday, February 25, 2010 10:53 AM To: Gupta, Indranil Subject: 525 Review 02/25 Sensor Net Routing Jayanta Mukherjee NetID: mukherj4 A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks: Royer, M. et al: As suggested by the title, this paper is a review paper. So, it describes different kinds of wireless networks, and the protocols they follow. The two major variations of mobile wireless networks are Infrastructured Network and Ad hoc networks. The article examines the routing protocols designed for the Ad hoc network. The articles presents some qualitative comparisons of the Table-driven protocols followed by Demand driven protocols, also called as Source-initiated protocols. Table driven protocols attempt to maintain consistent up-to-date routing information from each node to every other node in the network. Some of the Table-Driven routing protocols described here are as follows: Destination Sequenced Distance-Vector (DSDV)Routing: Based on Bellman-Ford Routing Algorithm Clusterhead Gateway Switch Routing (CGSR) protocol differs from DSDV in the type of addressing and network organizations Wireless Routing Protocol (WRP): maintain the routing information among all the nodes in the network. Each node is maintaining 4 tables Source-Initiated On-Demand Routing creates routes only when desired by the source node. Once a route has been established, it is maintained by a route-maintenance procedure until either the destination becomes inaccessible along every path from the source or until the route is no longer desired. Ad Hoc On-Demand Distance Vector (AODV) Routing protocol: An improvement over DSDV. AODV utilizes destination sequence numbers to ensure all routes are loop-free. Dynamic Source Routing (DSR) is an On-Demand Source-routing, which consists of 2 major phases: route discovery and route maintenance. The paper also describes Temporally Ordered Routing Algorithm (TORA), Associativity Based Routing (ABR) and Signal Stability Routing (SSR). SSR Algorithm is logical descendent of ABR. It uses new technique of selecting routes based on the signal strength and location stability of nodes along the path. Pros: The paper provides 2 tables of Comparisons. Table:1 provides the comparisons between the characteristics of different Table-Driven Routing Protocols and Table:2 provides similar comparisons between different Source Initiated On-Demand Ad-hoc Routing Protocols. These tables are really useful. The paper presents a comparison of the table-driven and on-demand routing strategy protocols highlighting their features, difference and characteristics. Cons: The organization of the paper is poor. The classification made based on the routing protocols are represented as a part of the Ad hoc Routing Protocols, not the Infrastructured protocols. More figures may reduce the dense text with a better way of representation. Although at the conclusion the authors have mentioned that these protocols have definite advantages and disadvantages, but, in the paper they did not explain the relative advantages and disadvantages of different protocols based on their characteristics. There is no table of comparison between Table-Driven Routing Protocols and On-Demand Ad-hoc Routing Protocols. Comments: The work is not original as it is a review paper. The number of references cited is just 24 and total 8 protocols are described and being compared. So, number of papers referred per protocol is pretty less in order to do any classification or comparisons about their performance base on their characteristics. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks: Intanagonwiwat et al.: The authors explored the Directed Diffusion paradigm for examining the behavior of the coordination between small and cheap nodes capable of sensing, communication and computation and such nodes form a distributed sensing environment. All the nodes in a directed diffusion-based network are application-aware. So, they are also capable of saving energy by selecting empirically good paths and by caching and processing data-in-network. Directed Diffusion is data-centric and significantly different than IP-style communication. In this paper, the authors described directed diffusion and illustrate one instantiation of this paradigm for sensor query dissemination and processing. Here, the authors describe some of the Design choices (like Naming, Interests and Gradients, Data Propagation, Reinforcement) for this sensor network. Pros: The paper described that, using directed diffusion one can realize robust multi-path delivery, empirically adapt to a small subset of network paths and achieve significant energy savings when intermediate nodes aggregate responses. Directed Diffusion based networks perform location tracking. This network (as described by the authors) are useful for interest setup gradients drawing down data. A sensor node can warn other sensor nodes of impending activity. Cons: Possible naming is not being described properly and being deferred as future work. Some of the terms (like Interest, Gradient, reinforcement) referred in this paper are not defined properly. For a work like this where so many new concepts and design ideas are being presented, the terms should have been defined more precisely. Diffused diffusion has the potential for significant energy efficiency In order to achieve its full potential careful attention has to be paid to the design of sensor radio MAC Layers. Comments: There is not much details about the experiments they perform as a proof concepts. The paper lacks self-criticism for the design. The authors did not elaborate how and why their system is better energy efficient than omniscient multicast. How much reliable the experimental result is for a new design on a conventional simulator like NS-2 is also questionable. From: gildong2@gmail.com on behalf of Hyun Duk Kim [hkim277@illinois.edu] Sent: Thursday, February 25, 2010 10:20 AM To: Gupta, Indranil Subject: 525 review 02/25 525 review 02/25 Hyun Duk Kim (hkim277) * A review of current routing protocols for ad hoc mobile wireless networks, E.M. Royer et al, IEEE Personal Communications 1999 This is a survey paper about routing protocols for ad hoc mobile wireless networks. This paper introduces eight protocols and compares them. There are two categories in ad hoc routing protocols; table-driven and source-initiated on-demand protocols. In the table-driven routing protocol category, this paper introduces Destination-Sequenced Distance-Vector Routing (DSDV), Clusterhead Gateway Switch Routing (CGSR) and the Wireless Routing Protocol (WRP). In the source-initiated on-demand routing category, there are Ad Hoc On-Demand Distance Vector Routing (AODV), Dynamic Source Routing (DSR), Temporally Ordered Routing Algorithm (TORA), Associativity-Based Routing (ABR) and Signal Stability Routing (SSR). After introducing each algorithm, this paper compares algorithms within category and between two categories using tables. At the end, this paper makes a conclusion with possible applications and future challenges. This is a very well written survey paper. This paper is even useful for people who are not familiar to the topic. At the beginning, it summarizes the general categorization and relationships among algorithms. Each algorithm is well explained and compared with various aspects. The comparisons are also well summarized as tables. This paper even covered possible applications at the end. Still there are possible suggestions for this paper. Using tree based categorization on the comparison stage could improve understanding. Without knowledge of algorithms, looking categorization figure does not help much. It could be better if the paper reminds and reexplains a categorization tree when they compare algorithms at the later part of the paper. Although they thorough compared algorithms within the same category, they do not show much comparison between two different categories. The comparison between two categories finishes with only two paragraphs. Connecting applications to the introduced algorithms could make this paper more interesting. This paper introduces possible application at the end. However, they do not connect the application to the introduced algorithms. If they connect algorithms to application and even can tell which algorithm can perform well for which application, this discussion could be more interesting. Also, because this paper is written 1999, there can be missing latest algorithms. Explaining similarities to P2P algorithms can be another interesting aspect to discuss. Some of introduced algorithms show many similarities to P2P algorithms. Surely, because ad hoc network and P2P network have common characteristics, comparing them could be also interesting discussion. * Directed diffusion: A scalable and robust communication paradigm for sensor networks, C. Intanagonwiwat et al, Mobicom 2000 This paper introduces directed diffusion paradigm for scalable and robust communication for sensor networks. Data generated by sensors are named by ‘interest’, and data ‘diffuse’ towards destination by ‘localized interaction’. Without centralized coordination, each node finds path and sends message to its neighbor. Directed diffusion is data-centric dissemination, and it has features like reinforcement-based positive/negative adaptation to the empirically best path, and in-network data aggregation and caching. According to the experiment results, directed diffusion shows its energy efficiency, robustness and scalability. This paper introduces a novel sensor network data forwarding method. In addition to the novel localized routing concepts, it suggests techniques for more efficiency such as caching, data aggregation and reinforcement. Experiments with different parameter setting give even more assurance about the stability of the algorithm. In the discussion section of the paper, this paper shows good comparison with other methods and trade-offs in choosing different design decisions. Although directed diffusion considers and achieves energy efficiency, it does not consider fair energy consumption. As it is stated on the paper, limited energy is one of the most important issues in sensor network. If we pursue the best performance, we may consume some specific sensors’ power earlier. If we lose sensors, we may not be able to obtain useful information of the area that died sensor located, and losing bridges may also cause the efficient message routing. Therefore, with message path selection considering remained energy level, consuming power evenly over sensors may help to improve the general network performance. -- Best Regards, Hyun Duk Kim Ph.D. Candidate Computer Science University of Illinois at Urbana-Champaign http://gildong2.com From: arod99@gmail.com on behalf of Wucherl Yoo [wyoo5@illinois.edu] Sent: Thursday, February 25, 2010 10:06 AM To: indy@cs.uiuc.edu Subject: 525 Review 02/23 Sensor Net Routing Review, Wucherl Yoo (wyoo5) A review of current routing protocols for ad hoc mobile wireless networks, E.M. Royer et al, IEEE Personal Communications 1999 Summary: This paper surveys ad-hoc routing protocols. The protocols 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. However, the route discovery incurs considerable latency. Pros: 1. Good comparison table Cons: 1. Lack of discussion about energy-efficiency of the routing protocols Directed diffusion: A scalable and robust communication paradigm for sensor networks, C. Intanagonwiwat et al, Mobicom 2000 Summary: The authors proposed directed diffusion as a data dissemination mechanism for sensor network. The main requirements of the sensor network are scalable for large number of nodes, robust against high failure rates of nodes, and energy-efficient. For meet these requirements, direct diffusion provides by strict local communication setup and message cache for scalability, multi-path delivery for robustness, and aggregation of responses of interests for energy efficiency. The basic idea of directed diffusion is as follows: An interest about sensing data is injected to a node, sink. The sink floods the interest with low data rate and initial large interval. This flooding will discover multi-path from sink to source node. Every node maintains interest cache so that interest can be distinguished and aggregated for energy efficiency. This cache also can potentially prevent of loop. The gradient is established when new interest is received, which points to sending node of the interest with data rate and timeout. The gradient is refreshed by periodical update from the sink of the interest. After receiving low data rate events, the sink reinforces high data rate path with local data driven rule. With sub-optimal local interaction, multi-path is eventually reduced high data rate path with small number of nodes. Without topological information, which helps scalability, every node decides which subset of neighbors to disseminate the interests. Intermediate node also can initiate reinforcement for path recovery. Pros: 1. Novel mechanism that is scalable, energy-efficient, and robust for sensor network 2. Clarification about tradeoff and future works involving with multiple policies Cons: 1. Lack of discussion about congestion 2. Data cache is used to avoid data loop but may not have sufficient size due to constrained memory size if large number of nodes have multiple sinks 3. Fully cooperative model with lack of discussion about malicious node -Wucherl From: Virajith Jalaparti [jalapar1@illinois.edu] Sent: Thursday, February 25, 2010 9:07 AM To: Gupta, Indranil Subject: 525 review 02/25 Review of “Directed diffusion: A scalable and robust communication paradigm for sensor networks”: 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 routed in response to an “interest”. Directed diffusion adopts a reactive mechanism in which data is sent to a particular node only if expresses an “interest” in the data. Infact prior to this, there exists no valid route from a node to the source of the data it is interested in. Initially, the “interest” request is flooded throughout the network, initiated by the source, at a low data rate until the nodes that are required to respond to this interest are reached. During this process, each of the intermediate nodes add the request to their interest cache along with several gradient field which are tagged with the refresh interval and duration of the interest and specify a direction for the route (similar to AODV) and data is routed back to the source of the interests following these gradients. All nodes maintain a data cache which helps them to combine message opportunistically. The paper also presents a concept called reinforcement (can be both +ve and –ve) which causes a certain path to be given higher/lower priority over others. The paper goes on to investigate the impact of using directed diffusion on energy savings, delays and how it is effected by dynamics. 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. - Both +ve and –ve reinforcement help in better communication allowing the existence of multiple paths at each node to reach the source/destination Cons/Comments: - Every new interest requires a setup in which causes potential flooding in the network. Hence this type of architecture potentially would cause performance concerns in which nodes query multiple sensor intermittently at a high rate rather than using the connection regularly at periodic intervals. - 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. - This scheme assumes that geographic routing can be used if flooding is not used. However each node having its own GPS device would make each sensor quite costly. - It might be the case that +ve and –ve reinforcement result in route oscillations; it is not completely clear how this would affect the performance of the system. - Factors like link quality etc can be taken into account for the reinforcement mechanism which might result in potential benefits and better performance. Review of “Learn on the Fly: Data-driven Link Estimation and routing in sensor network backbones”: This paper also proposes the use of data packets to estimate the link characteristics in 802.11b networks. It studies the differences between broadcast and unicast link properties showing that broadcast beacons cannot be used to precisely estimate the link quality for unicast transmissions. It shows that various factors like packet size, interference patterns and type of packet can impact the estimation of the channel characteristics and uses data-driven link quality estimation to overcome the effects of these factors. It proposes a new metric “expected MAC latency per unit-distance to the destination” (ELD) which is used to determine the quality of the links which are to be used for data forwarding. It uses the ability of getting feedback from MACs in sensor networks (which can be obtained because of the use of acknowledgements) and the knowledge of the physical separation of the nodes (by the use of GPS). Using this metric, the paper proposes the LOF protocol which is used for initial sampling of MAC latency (sends probes to do so), adapting estimating of MAC latency (uses EWMA) and switching to a new next hop forwarder (this is done probabilistically). The paper then goes on to compare LOF with ETX and PRD, two earlier proposed metrics, In terms of end-to-end MAC latency and energy efficiency and shows that LOF provides better performance when using its complete design. Pros: - 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. - The paper proposes a new routing metric, ELD, that tries it minimize the total latency experienced by a packet in flight in 802.11b networks. It depends just on the neighborhood of a node and is estimated by the use of data packets as they represent the actual channel conditions encountered by unicast packets. Cons/Comments: - The experimental setups in this paper are quite static and do not take into account the variability of channel conditions in real environments. All the experiments are done in controlled settings (either indoor or outdoor) and the results, though interesting and valid for such environments, may not be representative of real situations. Thus it not clear how much ELD would help in real sensor network environments which tend to typically be dynamic. - The paper assumes that each node in the network has access to information about the distances to its neighbors in the network by the use of GPS. However, having a GPS on each node may not be a feasible idea in sensor networks. - The paper tries to minimize the latency experienced by the data packets in the network. However it is not quite clear if this is of any concern in sensor networks. It doesn’t take into account the channel conditions directly (interference etc.) which might probably be used to achieve greater performance. However, estimation such channel characteristics directly requires a separate sensing/detection mechanism which again may not apply for unicast packets as the paper shows is the case of broadcast beacons. -- Virajith Jalaparti PhD Student, Computer Science University of Illinois at Urbana-Champaign Web: http://www.cs.illinois.edu/homes/jalapar1/ From: Nathan Dautenhahn [dautenh1@illinois.edu] Sent: Thursday, February 25, 2010 7:32 AM To: Gupta, Indranil Subject: 525 review 02/25 Paper Reviews: February 25, 2010 Nathan Dautenhahn 1 Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones Authors: Hongwei Zhang, Anish Arora, and Prasun Sinha 1.1 Problem Standard link quality estimation routing in wireless sensor networks is not optimal, namely, Beacon-based estimation can inaccurately estimate the quality of a link in the face of bursty traffic as well as waste energy by performing routine updates when no routing is required. 1.2 Solution and Contributions The authors suggest the use of geography and DATA-ACK handshakes as parameters that can be used to effectively perform link quality estimation for the purpose of successful routing. They develop a metric called ELD, which measures the expected MAC latency for packets in order to estimate link quality. They then develop a routing protocol, Learn on the Fly (LOF), that uses ELD to perform routing decisions. In addition to the above they provide an in depth study of the current performance of the Beacon-based traffic in order to identify poor capabilities in the protocol. The idea is to take advantage of the bursty nature of wireless sensor networks to save on bandwidth, and use the data being transmitted to provide link estimation to the routing engines. They have deployed their protocol in a real environment, which is a good indicator to its applicability and robustness as a protocol. 1.3 Questions and Comments My concerns are as follows: - I have several questions as to the validity of their sensor network. I’m not from this field so I have little understanding or knowledge about the characteristics of currently deployed systems. With that said I am wondering to what extent the author’s experimental setup reflects currently deployed systems with respect to device space, processing, and power constraints? -I would like to see an estimate of the costs of implementing their mechanisms over the Beacon-based approach. I think they covered this in the broadcast versus unicast experimentation, but I’m thoroughly confused about how data-driven approaches correlate with unicast messages. -They use a lot of experimentation to identify specific parameter values, I wonder if they could use a theory approach to identify these characteristics a priori? Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Authors: Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin 1 2.1 Summary and Overview The authors introduce a new communication paradigm, directed diffusion, for future wireless sensor networks. Directed diffusion is a method by which to provide information dissemination in a sensor network. They provide the following novel features: • data-centric dissemination • reinforcement-based adaptation to the empirically best path • in network data aggregation and caching 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 allow 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. I really liked how they motivated their work. With not current work in this area they created a completely new paradigm, which may be a little odd, but nevertheless the way they wrote the motivation was convincing. I think they did a thorough job of providing sufficient motivation. I also likes how they used concepts such as adaptive route reinforcement to allow the routes to shift to problems in the network. 2.2 Questions, Comments, and Concerns The primary concern I have with this paper is the fact that they did not test their system under heavy load. It is hard to compare two systems when you don’t push them to their limits, especially in this domain. It seems as though this network would operate at a high congestion level due to the nature of the protocol. So it would be nice to see this system pushed to it limits. 3 Common Themes Both of the papers focus on the data centric approach to enable better performance from routing protocols and information diffusion in wireless sensor networks. From: liangliang.cao@gmail.com on behalf of Liangliang Cao [cao4@illinois.edu] Sent: Thursday, February 25, 2010 1:06 AM To: Gupta, Indranil Subject: 525 review 02/25 Paper reviewed by Liangliang Cao (cao4@illinois.edu) for CS525 class on Feb 25, 2010 Paper 1: A review of current routing protocols for ad hoc mobile wireless network, 1999 This paper reviews several routing schemes for ad hoc mobile network. The paper group the routing schemes into two groups: table-driven and on-demand. By comparing the advantages and disadvantages of different routing schemes, this paper gives an impressive comparison of these methods and provides a clear analysis on which method is well suited for certain situations. Pros: • This paper does an elegant work in summarizing and comparing table-driven and on-demand routing: The disadvantages of table driven routing include (1) large amount of data for maintenance, (2) slow reaction on restructuring and failures. On the other hand, the on-demand routing suffers (1) high latency time in route finding (2) excessive flooding can lead to network clogging. • With the developing of Ad hoc network, this paper has inspired a lot of work with different routing strategy. Cons: • This paper is relatively old: it does not cover many recent routing schemes such as flow-oriented routing, adaptive routing. • Table-driven routing and on-demand routing are not necessarily separate. It is possible to combine them into one scheme, say, hybrid routing, which enjoys the advantages of both table-driven routing and on-demand Paper 2: Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones This paper considers the inherent difficulties in precisely estimating unicast link properties via those of broadcast beacons even if we make the length and transmission rate of beacons be the same as those of data packets, and proposes to estimate unicast link properties directly via data traffic itself without. It designs a data-driven routing protocol “Learn on the Fly” (LOF). LOF 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. Pros: • 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 • LOF uses MAC latency until the successful transmission of a packet as link metric, and thus is fit for 802.11b testbed. Cons • It is not clear how fast the LOF method can converge in network with loops. • It seems to me that the selection of parameters might not be an easy task. For different scenarios, we might change the setting for MAC latency, neighborhood size, and also the number of forwarders. From: Shehla Saleem [shehla.saleem@gmail.com] Sent: Wednesday, February 24, 2010 8:38 PM To: Gupta, Indranil Subject: 525 review 02/25 A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks This is a review paper and it talks about many of the popular routing algorithms for wireless mobile ad-hoc networks (MANETs). The paper categorizes them into two main classes based on how the routing protocol builds and maintains routing information i.e. Table driven and source initiated. In the wireless community, these are also termed as proactive and reactive routing protocols respectively. Basically, a table driven routing protocol takes after the common routing paradigm used for wired networks and infrastructured wireless networks. Every node maintains a table with routing information to every other node in the network. Some examples of these protocols include DSDV, CGSR, WRP. The upside of these protocols is that since they are proactive in maintaining routes, data intended for a specific destination can be sent as soon as it arrives. No route discovery etc is needed. However, the downside is the potentially massive size of tables and also the size and frequency of the updates and routing messages in the network that must be used to build/maintain the tables. This is a huge concern for the wireless community since wireless nodes usually run on batteries and power consumption is the highest during transmission and reception. Therefore, unnecessary traffic must be suppressed. Also, wireless is a shared medium. The more traffic there is, the higher is the probability of collisions and message loss. Finally, during high mobility scenarios, routes might become invalid frequently and routing table maintenance incurs significant overheads. Source initiated protocols try to address the above mentioned issues faced by table driven protocols. Some examples considered in the paper are DSR, TORA, ABR and SSR. The intuition is that a route to every other node is just plain unnecessary since every node does not usually transmit to every other node. The principle here is to find a route to a node if there is some data to be sent to it. That’s why they are termed as reactive protocols. One of the biggest advantages is the suppression of any periodic traffic and freedom from maintaining and updating large tables. However, the price paid is in terms of added latency. Finding a route to a node involves sending out some broadcast messages and waiting to receive back replies. This time might be non-trivial for networks with slow links or frequently failing links. Some optimizations include route caching, finding multiple routes etc but all of them suffer from the possibility of routing on stale routes and increased control traffic. The paper provides a brief but quick comparison of many popular routing protocols. It can be a great help for a starter. However, a more quantitative comparison might be much more helpful e.g with some simulation and/or emulation. Also, the paper uses time and communication complexity as metrics to compare the various protocols but a very important concern nowadays is power consumption. A power-aware routing protocol would be very attractive for the wireless community and so power-awareness should also be given weight for comparison of different protocols. The final word on which routing protocol is better, however, is to be said by the application. Different applications are sensitive to different parameters. An application with delay-intolerant traffic e.g. voice/video might prefer a proactive protocol. On the other hand, a power/energy-constrained application e.g. wireless mobile nodes placed in a hard to reach terrain where frequent battery recharges are not feasible, might choose a reactive protocol. Directed diffusion: A scalable and robust communication paradigm for sensor networks This paper presents a robust, power-aware communication paradigm for sensor networks. In principle, it works such that a node wanting some information sends out requests for this information to the network and sensor nodes that might have this information reply to it. More specifically, a requesting node i.e. a sink disseminates a request describing its ‘interests’ in a set of attribute-value pairs e.g the kind of information it needs and the intervals at which it needs them and so on. Receiving sensor nodes cache this information and forward it until a replying node sends back some results. Once these results reach the sink, it decides how to manage the results from potentially multiple paths. It chooses a path that suits its interests best and reinforces it such that it will receive data at higher rates on this reinforced path. It may also choose to negatively reinforce a path to suppress replies on some path. These options provide benefits that are two-fold. First, it can be used to suppress excessive traffic in the network by negatively reinforcing a path. Secondly, it can also be used to provide resilience against faults and failures so that if a preferred path goes down, a sink may positively reinforce an alternative path and start receiving data along that path. Intermediate nodes on the path maintain directed links to the sink from which the request originally came i.e. a reverse path. Another optimization is the ability of intermediate nodes to aggregate data containing similar information. Some of the concerns that might be worth looking at include, first of all, the fact that the algorithm has not been tested on networks under congestion. What happens if the nodes are over-loaded with traffic? How does the algorithm behave under that scenario? Also, the periodic broadcast might be another area worth looking at. Can the frequency of periodic broadcasts be dynamically adjusted to adapt to the load on the network? Also, the paper does not provide any figures on what should be the cache size of the sensor nodes and since quite a lot of parameters are being cached by them, the cache size must not become impractical. Moreover, because of the hop-by-hop communication paradigm, the traffic might end up passing sub-optimal paths and potential power-saving opportunities might be lost. Also, mobility is another factor lacking from the paper. Many sensor networks might involve mobile sensors, and it might be interesting to see how directed diffusion performs under that scenario and if the overheads become prohibitive. Overall though, the paper is very well written, and the evaluation is well executed. From: Ashish Vulimiri [vulimir1@illinois.edu] Sent: Wednesday, February 24, 2010 6:28 PM To: Gupta, Indranil Subject: 525 review 02/25 A review of current routing protocols for ad hoc mobile wireless networks, E.M. Royer et al, IEEE Personal Communications 1999 This paper surveys two classes of routing protocols for ad hoc networks: table-driven protocols and demand-driven protocols. Table-driven protocols operate similarly to the adaptive routing protocols employed in infrastructured networks. Every node in the network maintains information about the state of the network and uses this information to route packets. The routing data is kept current through an information exchange process that all the nodes are required to participate in. While table driven protocols provide fast route lookup and establishment, the overhead involved may be unnecessarily high -- not all the paths in the network will necessarily be used, and propagating information about every single path might be wasteful. Demand-driven protocols optimize for routing information overhead at the cost of route lookup time. Whenever a node using a demand-driven protocol does not know of a path to a destination, it broadcasts a route request through the network that is propagated until it reaches a node that has an available path to the destination. The authors describe several demand-driven protocols that attempt to optimize for different route selection metrics. They also present a qualitative comparison of the described protocols and list some average case time and communication complexity measures for each of them. Comments: * The average case complexity measures might not be completely indicative. The actual performance of any protocol depends on the network-specific distributions of link qualities, which tend to vary a lot between different applications. * The division between ad hoc and infrastructured networks is not always clean. For instance, vehicular ad hoc networks tend to use more structured routing protocols since i) on-road vehicles have relatively predictable movement patterns, and ii) support is occasionally available from infrastructure nodes established at high-traffic junctions. Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones, Hongwei Zhang et al, Infocom 2006 The authors use experimental evidence to argue that the conventional method of using periodic broadcasts to estimate unicast link quality information in wireless networks is flawed. They demonstrate that i) Link quality depends significantly on the characteristics of the traffic being sent (packet length, transmission rate etc), and ii) Even if the routing (broadcast) traffic can somehow emulate data traffic perfectly (difficult since data traffic can be fairly dynamic), the burstiness and temporal correlations in data traffic in some situations (such as wireless sensor networks) can still render estimates from periodic beacons inaccurate They define a new metric, the expected MAC latency per unit-distance to the destination (ELD), that essentially tries to greedily minimize the total end-to-end path latency, and show via an experimental evaluation that using this metric works well in practice. They also demonstrate how this metric can be computed from the data traffic directly, without needing any extra control traffic, when each node has information about the geographical distribution of its neighbours. Comments: * Periodic beacons cannot capture temporal correlations, but what about more complex models? For example, the Internet measurement community used Poisson distributed inter-arrival times for probe packets for just this reason for a while (this was because of what is called the PASTA principle -- "Poisson Arrivals See Time Averages"). * The new metric does not generalize easily to dynamic networks where node locations are more variable (not that the authors claim the generalization is feasible).