From: fariba.mahboobe.khan@gmail.com on behalf of Fariba Khan [fkhan2@uiuc.edu] Sent: Thursday, February 21, 2008 11:09 AM To: Gupta, Indranil Subject: 525 review 02/21 Directed diffusion: A scalable and robust communication paradigm for sensor networks, C. Intanagonwiwat et al, Mobicom 2000 Summary: This paper proposes directed diffusion - a data-centric routing algorithm for sensor network where the nodes are use for data collection such as weather, temperature etc. The idea is that in a sensor network it is more important to know what the node is sensing than the IP or MAC of a node. Each node collects such data and the data is queried by a sink node. The sink uses attribute-value pairs to request its interest in certain kind of data, such as count of some nodes (e.g. elephants). This interest is broadcast over the nodes and any node having such data sends it back on the same path. Once a data-source is established sink and source establish the best path, stop flooding and start using that. They evaluate this protocol in ns2 against flooding and static network multicast and perform better in terms of energy and delay. They also discuss multiple sources, multiple sinks and repair from failure. They also simulate effect of node failure in simulation. Discussion: The idea that sensor nodes mostly "sense" than route, so we can have special purpose routing for them. Lot of details was left out for an actual protocol. Like the schema, query language. Having a higher level abstraction for data (attribute-value) was cool. Data aggregation and Reinforcement is kind of vague (especially for me as I read TAG first). They propose coordinate system in the query which requires GPS. Even in 2007 I do not think that comes cheap. One important point I could not figure out from the paper is that are they assuming immobile nodes? Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones, Hongwei Zhang et al, Infocom 2006 Summary: In this paper authors discuss how link quality is important in wireless sensor networks and propose a data-driven routing protocol Learn on the fly (LOF). LOF estimates link quality based on data traffic rather than traditional methods of periodic beacon broadcast. LOF chooses route by locally measurable expected MAC latency per unit distance to the destination (ELD). MAC latency is the time taken for the MAC to transmit a data frame and they found that it is strongly related to energy consumption and link reliability. ELD is the rank for every neighbor the source node for a destination based on MAC latency and geographic distance between the three (source, neighbor and destination). LOF has two tasks 1. Obtain geo of neighbors 2. Enable node track MC latency (LD). For the second it does initial samplings for estimation, adapts it via MAC feedback for application traffic. It also probabilistically switches next hop node just in case the initial sampling was at a wrong time and thus giving it a more fair chance. Discussion: I think the idea is pretty cool. Don't beacon, estimate when you need-to-know. I cannot comment much on the experimental setup as it is not my domain knowledge, but yet I felt that there should have been analysis and simulations for mobile nodes. --- Fariba From: qwang26@uiuc.edu Sent: Thursday, February 21, 2008 9:56 AM To: Gupta, Indranil Subject: Review: senor net routing 2/21 A review of current routing protocols for ad hoc mobile wireless networks This paper examines routing protocols for ad hoc networks and evaluates these protocols based on a given set of parameters, and also provides an overview of eight different protocols by presenting their characteristics and functionality, and finally provides a comparison and discussion of their merits and drawbacks. Table-driven routing protocols: each node maintains one or more tables to store routing information, and respond to changes in network in order to maintain a consistent network view. One basic table-driven routing protocol is DSDV, which is based on Bellman-Ford algorithm with improvement of freedom from loops in routing tables. Based on DSDV, people propose another table driven routing protocol-CGSR, in which a framework for code separation (among clusters), channel access, routing, and bandwidth allocation can be achieved. However, its disadvantage of having a cluster head scheme is that frequent cluster head changes can adversely affect routing protocol performance. WRP is another table-driven routing protocol with goal of maintaining routing information among all nodes in the network. Each node maintains four tables: distance table, routing table, link-cost table and message retransmission list table. Another class of routing protocols is source-initiated on-demand routing. This type of routing creates routes only when desired by the source node. When a node requires a route to a destination, it initiates a route discovery process within the network. This process is completed once a route is found or all possible route permutations have been examined. 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. AODV is an improvement on DSDV because it typically minimizes the number of required broadcast by creating routes on a demand basis, as opposed to maintaining a complete lost of routes as in DSDV. DSR is another on-demand routing based on the concept of source routing. In DSR, mobile nodes are required to maintain route caches that contain the source routes of which the mobile is aware. TORA is a highly adaptive loop-fr! ee! distributed routing algorithm based on the concept of link reversal. It is proposed to operate in a highly dynamic mobile networking environment. ABR defines a new routing metric for ad hoc mobile networks, which is known ad the degree of association. Learn on the fly: data-driven link estimation and routing in sensor network backbones. This paper discusses the differences between unicast and broadcast link protperties in the context of IEEE 802.11b network testbeds. They show the difficulties in precisely estimating unicast link properties via those of broadcast beacons even if the length and transmission rate of beacons are made the same as those of data packets. To solve this problem, they propose to estimate unicast link properties directly via data traffic itself without using periodic beacons. By suing system facilities, they demonstrate the feasibility as well as potential benefits of data-driven routing by designing protocol LOF. LOF relies on three techniques for link quality estimation and route selection: initial sampling, data-driven adaptation, and probabilistic neighbor switching. In this paper, they focus on data-driven link estimation and routing in 802.11 networks. They find that geography and DATA-ACK handshake make it possible to perform routing without using periodic beacon, in terms of information diffusion and data-driven link quality estimation respectively. They define a new routing metric ELD, the expected MAC latency per unit-distance to the destination. They design a routing protocol LOF which implements the ELD metric without using periodic beacons. Besides saving energy by avoiding periodic beaconing, LOF facilitates greater extent of energy conservation, because LOF does not require a node to be awake unless it is generating or forwarding data traffic. LOF also helps in enhancing network security, due to the network is less exposed. From: Daniel Rebolledo Samper [rebolledodaniel@gmail.com] Sent: Thursday, February 21, 2008 8:44 AM To: Gupta, Indranil Subject: 525 review 02/21 DIRECTED DIFFUSION: A SCALABLE AND ROBUST COMMUNICATION PARADIGM FOR NETWORK SENSORS This paper presents "directed diffusion", a routing algorithm for data acquisition in distributed sensor networks. Contrary to regular routing protocols, directed diffusion is a local protocol: nodes communicate only with their neighbors and do not have a global notion of routing paths. Nonetheless, their experimental evaluation suggests that through local interactions they can obtain global behavior similar to omniscient multicast. The protocol has three main components: interests, gradients and path reinforcement. When a node (called "sink") wants to obtain information from the network, it periodically broadcasts to its nearest neighbors a task description or "interest" describing the data he is interested in, in the form of a series of key-value pairs. The neighbors add this interest to a cache and create a "gradient", that is essentially a pointer to the sink and an application-specific value. They then forward the interest to other nodes and so on. From a receiver's point of view, the sender of an interest is the sink, which is key to the locality property of directed diffusion. The interests eventually arrive at nodes capable of producing relevant data, which they send along the reverse path following the gradients. The originating sink can then send more precise interests to specific neighbors (and so no) to reinforce certain paths: in the end, only a small number of paths from the sources to the sink remain. This article is very interesting in that it tries to tackle the routing problem, which requires global or semi-global information, in a localized way. This is particularly important in sensor networks where communication must be minimized to preserve energy. Likewise, the authors propose in-network processing (for example, data flow down-sampling) to preserve bandwidth and battery life. Finally, the authors are not afraid to discuss controversial or taboo routing topics such as broadcast and loops: instead of forcing the protocol to build routes so as to avoid loops, they accept loops but use a data cache to prevent feedback-type effects where packets get infinitely copied. Likewise, they allow the protocol to transit through a temporary broadcast situation in order to obtain a small number of efficient routes in the end. LEARN ON THE FLY: DATA-DRIVEN LINK ESTIMATION AND ROUTING IN SENSOR NETWORK BACKBONES This paper presents a novel way of estimating link quality not from beacons as is usually done, but from the packets actually being transmitted. The authors first demonstrate through a series of experiments that in many circumstances broadcasting is an inaccurate way of measuring end to end link quality. They then introduce the ELD metric, the expected value of LD ("MAC latency per unit-distance to the destination") and briefly state that minimizing this value not only reduces latency and increases measurement accuracy, but also reduces energy consumption. Through a careful statistical analysis of the latency, they introduce LOF, a protocol that measures link quality and chooses the best next-hop route dynamically: the protocol first gets a rough estimate of link quality during the initial set up, and as it receives packets it measures the latency (using MAC-level ACKs) and adjusts its estimation of LD accordingly. Finally, since this technique may still overlook potentially valuable next-hop candidates, a third probabilistic mechanism is used to periodically switch the next hop. It is important to note that by its very definition the protocol relies on knowing its position, which may not be practical at present for many real-world sensor networks, but they legitimately claim to be tackling the problem of a wireless backbone in a broader sensor network. Such a backbone could presumably afford to have this additional information hand-coded or to include GPS or other positioning devices. The authors' technique of analyzing the statistical properties of the system in order to derive optimizations seems more widely applicable. Likewise, their insight into statistical theory enables them to design accurate estimators that work in practice. Finally, the concept of extracting routing information from the packets themselves is very thought-provoking and it would be interesting to see what results we can obtain by applying this technique elsewhere. From: Rahul Malik [rmalik4@uiuc.edu] Sent: Thursday, February 21, 2008 8:03 AM To: indy@cs.uiuc.edu Subject: 525 review 02/21 A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks SUMMARY: This is an old paper published in 1999. In this paper, authors provide an overview of routing protocols for ad-hoc mobile wireless networks that were available at that time. For the purpose of classification, they have divided the protocols in two categories: table-driven routing protocols and source-initiated on-demand routing protocols. In the paper, they have been explained briefly. It is nice that they are all available at one place for reference. We can see that some of these protocols such as DSDV, AODV, TORA, ABR, etc. are still widely used as routing protocols, while protocols such as CGSR, WRP, etc. are currently out of date. Another interesting thing to notice are the kind of applications that they were thinking of using these protocols. For the purpose of comparisons, authors provide a theoretical comparison among these protocols. They have compared both the protocols separately based on various metrics such as time and communication complexity and also enumerated various features present in those algorithms. PROS: One of the good points about the paper is that they have brought together all the protocols which were existing at that time and compared them theoretically. As a result of which, it is easy for anyone to choose the best protocol needed for the kind of application that one is working on. This also is a good survey paper for the existing protocols for one trying to get an overall idea of the field. CONS: One of the disadvantages of the paper is that they have just provided theoretical comparison of the protocols, while no implementation results have been provided. As a result of which, the results are not very convincing because in various protocols use various sizes of the tables, messages, etc. So, memory and bandwidth requirements can’t be stated in this manner. They have not compared the protocols for energy requirements, which is one of the most critical things in ad-hoc wireless networks. The protocols mentioned in this paper do not take into consideration interference between nodes, which is one of the major concerns in mobile nodes. FUTURE WORK: Now, I think that they can also include new protocols which are currently available in wireless ad-hoc networks. Also, these protocols do not take interference between wireless nodes into consideration. They should include some protocols which do that also. Direct Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks SUMMARY: This is one of the early papers in the filed of distributed sensor networks. In this paper, authors discuss the problem of disseminating data in a sensor network. They adopt a data centric dissemination approach to tackle this problem. In the paper, they have described ways in which data can be named. The named task descriptions constitutes an interest, which is injected in the network by a sink node. Nodes perform local interaction, as a result of which they conserve energy. This design is application aware. As a result, all the nodes know that what are the kinds of values that they need to sense. Gradient values are used to propagate the values in the network. PROS: As already described, the paper is one of the starting papers in sensor networks. The protocol of direct diffusion leads to energy savings as compared to simple multicast algorithms. The data-centric approach taken in this paper is a very novel approach and seems very useful in these kinds of systems. CONS: I feel that the experimental results in this paper are not very clearly explained. Also, the paper is very constraining because the nodes need to be programmed in the beginning about what kinds of objects can they sense. This is a limiting aspect of the paper. The kind of ideas that they use are borrowed from ad-hoc wireless networks, whereas such are not feasible even today. The nodes do not have MAC similar to that. In that sense, there in not much novelty. FUTURE WORK: They should try to use the MAC protocols as they are in use currently by the sensor networks, as opposed to assuming MAC similar to wireless ad-hoc networks. Also, they should perform some studies on an emulator to get actual values needed for various needs. From: Alejandro Gutierrez [agutie01@gmail.com] Sent: Thursday, February 21, 2008 3:19 AM To: Gupta, Indranil Subject: 525 review 02/21 =============================================================== “Directed diffusion: A scalable and robust communication paradigm for sensor networks” by: Chalermek Intanagonwiwt, Ramesh Govindan, Deborah Estrin Reviewed by: ALEJANDRO GUTIERREZ =============================================================== This paper presents an analysis of the directed diffusion paradigm by researchers from USC/Information Sciences Institute. This is considered to be one of the seminal papers in the Sensor Networks Research area. This is a very good paper on interest and data dissemination in sensor networks. It describes the “directed diffusion” paradigm, where “interests” are diffused throughout the network, and paths are “reinforced” to create gradients back to the data sinks. All the communication is local, so nodes don’t have to know the network topology that surrounds them. Unique addresses aren’t needed in the network, but the only constraint is that nodes must be able to distinguish neighbors in some way or another. There’s probably quite a bit of work that could be done in diffusion based networks, such as development of a MAC layer protocol specifically designed for diffusion applications. The advantage is that directed diffusion is energy efficient and it is relatively robust. On the contrary it has the disadvantage that in the scenario where there are multiple different types of tasks going on, an unbalanced load may happen. Also the local storage per node grows with the number of tasks. A problem I had with this protocol is that if we were going to have the task require a global configuration, then this protocol will perform in a non-effective way. =============================================================== “Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones” by: Hongwei Zhang, Anish Arora, and Prasun Sinha Reviewed by: ALEJANDRO GUTIERREZ =============================================================== This paper presents Learn on the Fly (LOF), an algorithm, proposed by researchers from Computer Science and Engineering in Ohio State University. The authors examine the behavior of broadcast beacons used to estimate link properties and conclude that due to inherent differences between unicast and broadcast, broadcast beacons are not good for this task. I liked this paper because it presented in a very subtle way lots of experimental results that I in my opinion are always for the user to conclude the validity of whatever they are claiming. I also like how they outperformed ELD vs. ELR and route selection vs. absolute ELD. Better results and an increase on energy consumption are also very beneficial since they take advantage of MAC feedback. I can see this routing protocol being very successful in a sensor network scenario where there are lots of nodes sleeping. On the other hand measuring link quality by data traffic itself introduces some delay. However, link quality changes a lot in wireless sensor networks. For future research I would be curious to see the performance of such algorithm in an 802.15.4 Zigbee network. A very interesting finding could be modeling the interactions among motes in a particular network. From: Zixia Huang [zhuang21@uiuc.edu] Sent: Thursday, February 21, 2008 2:03 AM To: indy@cs.uiuc.edu Cc: Huang, Zixia Subject: 525 review 02/21 Paper Title: A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Network Author: Elizabeth Royer and Chair-Keong Toh Summary: The main contribution of this paper is to compare the existing routing protocols designed for ad hoc networks. Basically, there are two main broad categories according to the characteristics of these routing protocols. One is the table-driving protocols which main consistent, up-to-date routing information from each node to every other node in the network. The other type is the source-initiated on-demand routing which creates routes only when desired by the source node. For each specific category, different algorithms have been proposed which can achieve different functions. The paper continues by the comparisons of these two protocols. For the on-demand protocol, it requires additional time to discover a route before reaching a new destination. For the table-driven protocols, it requires additional traffic and power to maintain the tables, which becomes a critical issue in mobile systems. Pros: (1) Complete comparisons of different ad hoc routing algorithms Paper Title: Directed Diffusion: A scalable and robust communication paradigm for sensor networks Author: Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin Summary: The main contribution of this paper is to provide a directed diffusion method that can be used in the coordination and communication to perform distributed sensing. The method is selecting empirically good paths and caching and processing data in-network to achieve energy saving. The paper continues by giving a detailed description of the realization of the diffusion and providing a methodology of evaluating this method. One good point is the paper discusses the impact of dynamics when node fails, as it is not a seldom phenomenon in the real distributed system. It also discusses the impact of various other factors. Pros: (1) Discussion of the impact of dynamics of network situation (2) Discussion of the impact of various other factors Cons: (1) Sensor radio MAC layer requires special attention during the design From: ysarwar@gmail.com on behalf of Yusuf Sarwar [mduddin2@uiuc.edu] Sent: Thursday, February 21, 2008 12:26 AM To: Gupta, Indranil Subject: 525 review 02/21 Learn on the Fly: Data-driven link estimation and routing in sensor network backbones Hongwei Zhang, Anish Arora, and Prasun Sinha The paper demonstrates the difficulties of precisely estimating link properties via broadcast beacons and proposes unicast link property estimation via the data traffic itself, using MAC feedback for data transmission. The authors argue that nodes in sensor network usually remain idle in most of times, but when an event happens, lots of data traffic is generated. The authors treats that broadcasting beacon packets for estimating link metrics while not sending any data at all is simply a wastage of energy. That's why they propose an alternative link metric estimation approach where regular beacons are not used, instead link metrics are computed 'on the fly' when data packets are being transmitted, and a complying routing protocol also proposed based on this. The basic idea is to assess the link quality based on MAC layer acknowledgment against the data frame sent, and computation of expected MAC latency per unit length from the information of link delays to neighboring nodes. Link assessment begins with some initial sampling and then being adjusted accordingly when newer packets are sent. Pros: - A useful way of saving energy by reducing idle beacon transmission. - Performs better than some earlier works like ETX and PRD. - Runs live experiments to justify/verify whether a set of assumptions or statements are held in practice. Cons: - Link quality estimation is an important operation of data link layer...and application and all sorts of data transmission suffer if link metrics are not properly computed. LOF leverages link estimation against the energy consumption... It can be wondered whether routing or overall data traffic can suffer for this. =============================== Directed Diffusion:A scalable and robust communication paradigm for sensor networks Chalermek Intanagonwiwat, Ramesh Govindan and Deborah Estrin Directed diffusion is a novel data dissemination technique proposed for sensor networks. In sensor network data communication paradigm is not destination-address centric, that is data is never targeted by addressing to specific sensor nodes, that usually happens in IP-network where application knows whom it wants to communicate. Due to this difference of operation, sensor networks' data delivery technique should significant be different from its IP counterpart. DD addresses this issue. Instead of making end-to-end data delivery, DD introduces a concept of interest propagation to locate potential candidates of data source. That is, when a node intends get information of certain things, it generates an interest and propagates the interest to a set of to be interested nodes (usually specified by geographic zone). Intermediate nodes that receive the interest stores this in them. When a certain node feels that it can serve data to a certain interest, it sends the data back to the interest generator in the reverse path the interest was propagated. This reverse path, known as gradients, are occasionally reinforced positively (make strengthened) or negatively by adjusting some interest attributes. Pros: - Reactive data pulling...data generator does not deliver data until some nodes are interest to consume it..., so unnecessary data flooding is eliminated. - Interest reinforcement eventually chooses the best path over time... and multiple redundant paths can be made active for reliability. - Caching of interests to support abrupt network dynamics. - Network operation can be intentionally partitioned... some interests may correspond to a specific zone, and some may be to others. - It's a communication paradigm, more than a simple protocol..., it somewhat indicates how the information dissemination matter for WSN should look like. Cons: - It is not clear how an interest is created and how to foresee who could be the potential data generator satisfying that certain interest? - Sometimes, some urgent events should be reported promptly, instead of being served against some interest... in that case DD may fail. - What do the those sensors do that haven't received any interest? Do they keep idle and sleep? Or they sense and store the events. - It can happen that the sink could be interested on something from the entire network. In that case, the entire network will be flooded by interests and lots of path will be created to push data back, generating enormous data collision and bandwidth wastage... Comments: Directed diffusion, one of the most cited paper in WSN research, introduced some salient network operations for sensor networks considering energy-efficiency and low duty cycle issues that raised many more research in this field later on. Yusuf Sarwar Graduate Student Department of Computer Science University of Illinois at Urbana-Champaign (UIUC) IL 61801, USA From: Mirko Montanari [mirko.montanari@gmail.com] on behalf of Mirko Montanari [mmontan2@uiuc.edu] Sent: Wednesday, February 20, 2008 11:18 PM To: Gupta, Indranil Subject: 525 review 02/21 "Direct Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks" Direct diffusion is a method for routing query responses in wireless sensor network. This method uses only local information and creates a good path between a source and a sink using dynamic reinforcement of the best paths (ant's colony method). The motivation for its design comes from the application of sensor networks in the monitoring of natural phenomena, where a user is interested in receiving samples every x ms from a particular geographic area. To solve this problem Direct Diffusion works as follow. The query (called "interest") is sent to all the nodes (or just to the particular area is geographic routing is available) with a required sample rate >> x (less sample per second). The nodes that generate samples start sending them to the nodes from which they received the "interest" message. At this point, each of the nodes continue to forward the sample back on the paths from which it received the interest messages. Each node also "reinforce" the path from which it received the response of the query earlier by increasing the required sample rate in the interest message. In this way the protocol reinforces the "best" path by making only local choices. PRO: + The idea of the protocol is very good: it only uses local information to create a global good routing. + It seems to obtain good performances compared to flooding and multicast + automatic adaptability in case of faults CONS: - No theoretical justification of the method. This seems to be a seminal paper in routing in sensor network, so probably the theoretical foundation came later, but some work should definitely address a more theoretical analysis of the protocol. This would also give a way to design how fast reinforcement and suppression should be done. - It seems that the main performance advantage of direct diffusion comes from the ability of doing aggregation. A data-aware multicast algorithm could be able to aggregate data on the intermediate nodes in the network: what would be the advantage of such protocol over direct diffusion? would direct diffusion still be better that the multicast in term of energy? ---- "Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones" This work describes a new way to estimate the quality of links in a wireless sensor network. Estimation of link quality is important in wireless network routing because it can determine which path is taken by the data: a wrong estimation could let to take suboptimal routing paths that can affect performance and energy. Previous work relies on periodic broadcast to estimate the quality of wireless connection and the authors prove that this creates suboptimal quality estimation and wastes energy for sending messages that do not carry information. The main idea of the work is to use the normal transmission of data to estimate the link quality. They defined a quality metric that can be estimated through analyzing the MAC layer. During data transmission the MAC layer response is recorded and the routing is based on this information. To avoid that a bad initial sampling of link quality affects the routing decision indefinitely, the authors propose to randomly send messages through other currently unused links to updated the estimation. PRO: + The idea of estimating quality of the link during the normal data transmission is definitely interesting and it seems to have potential. + I liked that they tested their motivation and proved that the broadcast information does not allow to infer the quality of unicast links. CONS: - The metric that they choose to use is based on geography and static networks. Position of nodes might not be known. - There is not explicit evaluation of the performance of the protocol in case of failure of some of the nodes. The adaptive nature of the protocol seems to be able to adapt to failures, but having an explicit evaluation of this property would be interesting. From: marefin2@uiuc.edu Sent: Wednesday, February 20, 2008 10:16 PM To: Gupta, Indranil Subject: 525 review 02/21 Review 1: Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. C. Intanagonwiwat, R. govindan, D. Estrin This paper describes a new data dissemination protocol in sensor network called directed diffusion. The scheme is data centric. Data is named using attribute vale pairs. A sensing task is disseminated throughout the sensor network as an “interest” for the data. The sink node originates the interest with a lower rate at the beginning. When a node receives an interest it checks if the interest exists in the local cache. If no cache entry for that interest, the node creates a new interest entry. This entry has a single gradient towards the node from which the interest was received. If the node contains an interest entry in the cache, then it adds the gradient with the specific value or updates the existing gradient’s value. When a gradient expires, it is removed from the interest entry. After receiving the interest, a node may try to resend the interest to some subset of its neighbors. Thus, interests diffuse throughout the network. A node may drop a received interest if it recently resent a matching interest. Now, when a node detects a task that matches the interest entry, it selects the highest sample rate of the requesting neighbors. When a node receives a data message, first tries to find the entry in the cache. If no matching exists, the message is dropped. Otherwise, the message is forwarded to the neighboring nodes according to the data rate as stored in the gradient. Thus propagation of data includes loop prevention and down conversion of rate. After the sink starts receiving low rate events, it selects one of its neighbors (who sent the recent new event) and requests the interest with high or desired even rate. That neighbor node then selects another neighbor for sending the updated interest using the same rule. This process is called reinforcement. This protocol uses negative reinforcement for better path selection. Some of the mentionable points about directed diffusion are · Directed diffusion is a data centric solution, especially for sensor network. All communication is neighbor to neighbor instead of end-to-end communication. Any node can send interest and interpret data. · Sensor network is sensitive in case of energy. This proposal is energy efficient. The routing is established on demand. Caching prevents the loop and reinforcement reduces the path cost in turn. · It is better than flooding, multicast. Because the interest propagation or data propagation are limited. A node can drop the message depending on the cache entry instead of flooding in the network. · As sink receives the reply from multiple paths, the protocol can show good robustness against failure. · Karlof et al analyzed the resilience of various routing protocol and showed that Directed Diffusion is vulnerable to sink hole attack. · If the timeout for the event is low (that is used for loop detection) in the cahe entry, there could be a possibility of loop. · It is not sure how the protocol handles or ensures if the requested rate of event doesn’t meet in the network. Review 2: A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Network E. M. Royer, C.K.Toh This paper divides the routing protocol in ad hoc mobile network in two sections, table driven and source driven. Table driven protocol maintains a consistent routing table from each node in the network. In DSDV, each node maintains a routing table with all possible destinations. It uses Bellman-Ford routing mechanism. The Clusterhead Gateway Switch Routing (CGSR) maintains clusters with cluster heads. If clusterhead is changed frequently then this protocol shows lower performance. Messages are routed from one cluster head to a gateway to another clusterhead. The Wireless Routing Protocol (WRP) maintains distance table, routing table, link-cost table and message retransmission list table in each node. Link changes are propagated through the update messages between the neighboring nodes. Source initiated routing is some sort of on-demand routing initiated by the source. One of the most popular source-driven routing protocols is AODV. It is an improvement of DSDV. It minimizes number of broadcast by creating on-demand route. When a node wants to send a message to some other node for which it doesn’t know any route, initiates a path discovery phase. It creates the path from destination to source through which message is transmitted in the data transmission phase. Dynamic Source Routing (DSR) is another source driven routing protocol. It broadcasts route request during the route discovery phase and route maintenance phase handles error packets (in case data link layer encounters an error) and acknowledgement. The Temporarily Ordered Routing Algorithm (TORA) is based on the concept of link reversal. At the rote creation phase, this protocol creates a DAG routed at destination based on height metric. So TORA provides multiple paths to destination. The significant difference of TORA compared to the above protocols is that it assumes the clock synchronization among the nodes. Associativity-Based Routing (ASR) is another source driven routing that is free from loops, deadlock and packet duplication. Each node periodically sends beacon to inform its existence. The route discovery phase is done by broadcast query and wait-reply cycle. Route ReConstruction (RRC) phase ensures invalid route erasure, valid route updates and new route discovery. Signal Stability Routing (SSR) is an adaptive routing protocol. SSR selects route based on signal strength on the route and location stability of the node. Signal strength of each neighboring node is stored by periodic beacon and used during the route request forwarding. Also failure is handled by reporting to the source. The performance of DSDV and CGSR depend on the network diameter, while WRP (flat routing) depends on number of nodes in the network. All three use the shortest path philosophy. The memory requirement in WRP is high compared to DSDV and CGSR. WRP also consumes extra bandwidth but provides good protection against loop. For Source Driven Routing, only AODV could support multicast in the original protocol. DSR shows better performance where node moves at moderate latency compared to data transmission latency. TORA and DSR can support multiple routes. TORA’s assumption about synchronization is one of the drawbacks in application. The technique used by SSR is quite new than the other routing protocol. One of the drawbacks in SSR that intermediate node cannot reply to route request sent toward a destination, this causes a long delay for route discovery. On-demand routing is desirable in the sense that path is created when necessary, which could ensure the availability of the path during the data transmission. But the major drawback compared to table driven is that it requires some setting time before transmitting the actual data. Actually the use of these two types of routing scheme mainly depends on application. This paper describes the mathematical overhead and logical properties of different interesting and classical protocols. Also comparison of propagation latency, bandwidth requirement and robustness among these protocols could be attractive information in mobile ad hoc routing. Arefin From: Riccardo Crepaldi [crepric@gmail.com] Sent: Wednesday, February 20, 2008 9:49 PM To: Gupta, Indranil Subject: 525 review 02/21 Directed Diffusion: a Scalable and Robust Communication Paradigm for Sensor Networks Directed diffusion, the algorithm presented in this paper, is a data- centric dissemination paradigm for sensor networks. This protocol is data-centric in the sense that the communication is based on data flows, and the routes are built based on the type of data that is received. The protocol works by mean of interests disseminated to the network from nodes that want to collect a particular data flow. Data matching the interest is then directed to the node or the nodes that express interest for it. This protocol is very interesting in what it is specifically designed for wireless sensor networks, that usually have not permanent connectivity and don't make use of IP-style communication. It also takes advantage of the shared nature of the channel. The paths between sources and destinations of the data stream are selected depending on how the interest reached the source, and then, through a cache system of received interests (that are cached), a message suppression technique is applied to prevent network congestion. As the author say in the paper the proposed interest dissemination protocol, by mean of caching and gradients, and the suppression techniques are very task-specific, and they think to explore various possibilities in the future. The data propagating protocol is then presented. It also uses caching to prevent loops. The data is sent to the links that expressed interest for that type of flow, but the rate could be different since the interest also specifies that parameter. If this is the case for some link the flows is then downsampled. A reinforcement technique (paired to negative reinforcement) is used to keep paths up-to-date. The main pro of this paper is the intuition that the right approach for a routing algorithm in a WSN has to be data-centric, given that the specific applications for WSN are usually more focused on data that on devices. A simulative data evaluation is then presented, that shows how Directed Diffusion performs wrt multicasting and flooding, and how the network size affect its performance, with different packet losses. The performance of the algorithm seem to be very good, and to fit perfectly in the WSN scenario, while it would not provide big benefits in other wireless networks where the communication is not the biggest source of power drain. However, it would be interesting to see how the protocol behaves in presence of multiple sinks and multiple sources at the same time, and with paths that intersects each other. Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones In this paper the authors analyze the behavior of wireless networks with a good attention, and they prove that some of the assumption that many networking protocols use are very inaccurate. In particular they show how the use of broadcasted small packets to determine channel characteristics that will then be used to adapt the behavior of the networking protocols when sending big unicast packets leads to inefficient channel utilization. The set of experiment they set up shows how the wireless channel behavior is very complicated and there’s a lot of correlation in time and space for errors and packet drops. Additionally the RTS/CTS mechanism and the retransmission procedure in unicast 802.11 make the prediction based on small broadcasts not efficient. The LOF algorithm almost eliminates the use of broadcasts to evaluate the channel (the are used only in the start-up procedure). LOF introduces a new metric, ELD, obtained by information gathered from the 802.11 MAC directly from the hardware. A combination of estimated performance from the network behavior and probabilistic choices are implemented. The paper is presented in a well-organized way, and the implementation shows that the authors’ intuition is correct. Looking back to the assumptions that drove the design of many algorithms in the last years and analyzing the, requires to be far-sighted and critical. However it seems that such algorithm is more addressed to Wireless Sensor Networks than 802.11-based networks. How will the protocol behave in presence of highly variant channels, due to low cost radios but also to mobility? And will the computational cost of the ELD estimation be easily supported by the devices? A testbed based on sensors instead that stargate boards will help answering these questions. From: Anthony Cozzie [acozzie@gmail.com] Sent: Wednesday, February 20, 2008 8:40 PM To: Gupta, Indranil Subject: 525 review 02/21 LOTF: Data Driven Link Estimation Choosing which links to use in an ad-hoc wireless network greatly impacts performance. The standard metric is ETX (measure the packet loss rate over each hop, and choose the path with the expected smallest total number of transmissions). These metrics are combined with some sort of routing protocol (the classic ones being AODV and DSR) that distributes some fraction of the information throughout the network. The paper is built around the idea that link status should be measured by the result of actual data packets, not special beacon packets. They claim using actual packets is both more accurate and more energy efficient. The actual metric they use is MAC latency / unit distance. I do not understand this paper. It seems to me that when forwarding a packet to a destination, the distance is always constant and will therefore fall out of the equation, becoming straightforward MAC latency minimization. Futhermore, it seems to me that MAC latency is essentially equivalent to the number of transmissions, except in extreme contention when exponential backoff might affect things. And yet they claim better results. Perhaps I shall be enlightened tomorrow morning. Directed Diffusion I don't quite understand the point of directed diffusion, either (as compared to something obvious like TAG). Usually the point of these sensor net algorithms is to do something with the (comparatively cheap) processor in order to reduce the number of packets sent. However, DD mainly appears to try to set up a reasonable "reverse multicast" path without a lot of global state. Originally all paths are tried, and then the algorithm gradually converges to one set of (hopefully good) paths. Again, I don't quite understand the point. From: Hengzhi Zhong [hzhong@uiuc.edu] Sent: Wednesday, February 20, 2008 6:06 PM To: Gupta, Indranil Subject: 525 review 02/21 Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Summary: Since we now have many small nodes capable of doing communication and computation, we need to think about how they can be deployed to monitor various phenomena and answer queries. On a query, sensors are asked to collect information. Directed Diffusion is a data-centric approach for answering queries. The goal of diffusion is scale. The other one is it must be robust for failures. Lastly, energy consumption should be minimized. The data are named by attribute-value pairs. Any data propagation and aggregation are localized, so messages are exchanged between neighbors or close nodes. A task is disseminated in the network. The flow is directed to nodes that contain the interest of the query. Basically, diffusion uses nodes’ neighbors to verify their estimation of the query answer and send back the aggregated answer. Pros: 1. It’s a data-centric approach, which means queries are not routed toward individual nodes, but in terms of named data. This saves energy. Cons: 1. The search is by flooding. Flooding is extremely bad when many nodes are connected. 2. There are lots of messages resending. Doesn’t this increase traffic? Further, energy consumption can be dominated by send/receive messages. 3. The experiments only do up to 250 nodes. Sensor networks definitely can have more nodes than this. How can 250 nodes demonstrate scale? Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones Summary: Estimating link quality is important in routing. This paper shows that it is difficult to use broadcast beacons to estimate unicast link quality. However, one can design a routing protocol LOF, which doesn’t use broadcast beacons. Since one cannot directly estimate the unicast link quality, one can estimate via data traffic. This is what it means to be data-driven routing. The routing metric ELD (or ELR) uses MAC feedback. It also assumes nodes are pretty static and geographic locations for nodes are available. LOF uses this metric to choose routes. LOF uses the following to estimate link quality and select routes: sampling on MAC latencies, uses MAC feedback to estimate, and probabilistically switches neighbors. Pros: 1. LOF reduces end-to-end MAC latency, reduces energy consumption, and improves route stability. 2. Uses data traffic itself to estimate link quality. 3. LOF uses MAC feedbacks. They provide better parameters to show link reliability. Cons: 1. The metrics ELD (or ELR) seem to depend on network topology. 2. When a node sees a new neighbor, it takes a few samples of MAC latencies by forwarding data packets to the new neighbor. How accurate is the initial sampling? What if there are some interferences, causing a biased sample? What is the effect of sampling techniques? From: Chandrasekar Ramachandran [cramach2@uiuc.edu] Sent: Wednesday, February 20, 2008 5:29 PM To: indy@cs.uiuc.edu Subject: 525 review 02/21 1.Directed diffusion: A scalable and robust communication paradigm for sensor networks, C. Intanagonwiwat et al, Mobicom 2000 Summary: One of the seminal papers in sensor networks, this paper proposes a novel mechanism of data-focused communication. It uses the concepts of "interests", "aggregates" and so on to enable sinks in the networks to obtain specific data, represented as attribute-value pairs from the network. This paper spawned a variety of research in applications using this type of paradigm and continues to be a standard for evaluating new research papers in this field. Pros: 1. Excellent presentation style which emphasizes the use of examples to explain several aspects of the paper. 2. The relatively good energy-efficiency and the stability exhibited under conditions of stress. 3. The possiblities of building applications using the directed diffusion paradigm are many. Cons: Nothing that I can think of, but sure would help if a systematic evaluation with other related protocols(not merely flooding and Omniscient Multicast) had been done in the paper. 2. Learn on the Fly: Data-driven Link Estimation and Routing in Sensor Network Backbones, Hongwei Zhang et al, Infocom 2006 Summary: A novel method of estimating unicast link properties by analyzing the data traffic is proposed in this paper.By modifying the WLAN driver hostap and the linux kernel, feedback is provided on MAC latency and the status of link transmissions, along with the routing protocol without periodic beacon transmissions.Results show the that LOF outperforms other related protocols in terms of MAC Latency by around 3 times. Also energy efficiency for LOF in terms of number of unicast transmissions received is much better than ETX and PRD, the protocols under evaluation. Pros: 1. Excellent testing and implementation of the protocol in the backbone network of ExScal. 2. Good Energy-efficiency and low latency as compared to other protocols. Cons: 1. More metrics for evaluation like Power consumption etc could be present. Common Themes: Focus on Data-Driven Routing and implementation, suitable for energy-constrained sensor networks. From: emenese2@uiuc.edu Sent: Wednesday, February 20, 2008 3:33 PM To: Gupta, Indranil Subject: 525 review 02/21 Paper: A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks Reviewer: Esteban Meneses (emenese2@uiuc.edu) The paper focuses on infrastructureless networks (known as ad hoc network). These networks have no fixed routers, all nodes can move and route messages and are connected dynamically in an arbitrary manner. The routing problem in this case has been attacked using a couple of different techniques: table driven or demand driven. Table driven protocols aim to maintain consistent and fresh routing information from each node to every other node in the network. These protocols enforce each node to maintain one or more tables to store routing information and changes in the topology propagate updates throughout the network in order to keep a consistent network view. Several algorithms belong to this family. The Destination Sequenced Distance Vector (DSDV) routing is a table driven algorithm based on the Bellman-Ford routing. In this case, every node has a table with the number of hops to reach the destination. Sequence numbers are kept for each route to detect stale ones and chan! ge! s in the topology are broadcast to make tables consistent with this reality. The Clusterhead Gateway Switch Routing (CGSR) differs from DSDV in the way network is structured. CGSR sees the network as clusters, being the head of the cluster the responsible for routing to other nodes. The Wireless Routing Protocol (WRP) is also a table based protocol that uses link state information. Unlike these protocols above, the on demand routing family creates routes only when desired by the source node. The Ad Hoc On Demand Distance Vector (AODV) is based on DSDV and minimizes the broadcast messages by creating routes on a demand basis. Dynamic Source Routing (DSR) is similar to AODV, except that in this case nodes are able to cache routes. Temporally Ordered Routing Algorithm (TORA) is based on the concept of link reversal and it builds a DAG every time a route is requested. Finally, the Associativity Based Routing (ABR) defines a new metric for routing called the degree of association! s! tability and the Signal Stability Routing (SSR) is based on the strength of the signal between a pair of nodes. After an analysis of all the techniques the conclusions are that DSDV is inefficient because of the requirement of periodic update transmissions (regardless of the number of changes in the network topology). DSR has more overhead than AODV, since each packet is DSR carries full routing information. However, DSR doesn't make use of periodic advertisement. AODV supports multicast. TORA is best suited for large dense populations. TORA supports multiple routes. ABR is free from packet duplicates, because the best route is valid, while other routes remain passive. One disadvantage of SSR is that intermediate nodes cannot reply to a route request. The decision between table driven or demand driven routing depends on the inherent features of the network. This is a survey paper and there is a comprehensive summary of the routing techniques for MANETs (Mobile Ad Hoc Networks) up to 1999. Notably, there are more protocols that can be added to the list if the paper were to be written these days. One of such protocols is the location based Greedy Perimeter Stateless Protocol which relies on geographical positioning system to route the messages. Even when these protocols have their own disadvantages, they still offer a chance to route in open environments where every node has a GPS system. On the other side, I believe there is a need for protocols in the MANET world that deal with highly dynamic networks. One example is the vehicular networks, where mobility is constant and churn is enormous. Cars are joining and leaving the network constantly, either because they get in/out of reach or because they are turned on/off. In this cases, there is no much advantage in having a table for all the nodes in the system. The main drawback of the paper is the lack of experiments with real/simulated networks. The analytical results are really interesting, but it is also very useful to have an idea of how well the protocols perform under more realistic environments. Measures like latency, bandwidth consumption, failure tolerance and others are important to measure. Also, the same features of network must be tested: number of nodes, mobility patterns, density of network and so on. Paper: Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Reviewer: Esteban Meneses (emenese2@uiuc.edu) Sensor networks offer an interesting area to test different distributed protocols. The reason relies on the fact that normally this type of networks are deployed is really harsh environments with highly restricted conditions on memory and energy usage, communication range and other node's capabilities. Using this motivation, directed diffusion appears as a paradigm for data dissemination in sensor networks. Directed diffusion is data-centric and data generated by sensor nodes is named by attribute-value pairs. One node that request data (called sink) expresses its interest by sending named data. The idea is also to drawn down towards the node that has data matching the interest. The intermediate nodes can cache or transform data. An important feature of directed diffusion is that interest and data propagation and aggregation are determined by localized interactions (message exchange between nodes in a vicinity). An important point in directed diffusion is that during the ! di! ssemination process, gradients are set up within the network to draw events (data matching the interest). Events start flowing towards the originators of interests along multiple paths. Reinforcement is the process by which the sensor network makes one or a small number of these paths a primary route to the information. A task is defined by a list of attribute-value pairs and the sink periodically broadcast the task as an interest message to each of its neighbors. The message includes a timestamp attribute. Also, every node keeps an interest cache. Each item in the cache corresponds to a distinct interest. Two interests are distinct if their attribute differs. When a node receives an interest, it checks to see if the interest exists in the cache. If no matching interest entry exists, then the node creates one new entry. Once the interests hits a responding node, then the sink starts receiving low data rate events. It reinforces one particular neighbor in order to draw down h! ig! her quality events. The main tradeoff in using directed diffusion strives in the refresh rate for the sink in sending its interests. The higher the rate, the more overhead but also the more robustness to lost. There is no explicit support for moving nodes. If one sensor is in a moving agent, then there is few mechanisms in directed diffusion for dealing with this situation. The problem with mobile agents lies in the fact that they can degrade the cache performance by making stale many entries as they get out of reach. The reinforcement mechanism appears to work well under changing conditions of links in the network. However, it is not possible how to deal explicitly with alternate routes in case of a node failure. The way directed diffusion overcomes a node failure is by reinforcing another route to the source of the interest. It is not clear how to optimize in the case with identical tasks submitted by several sinks if intermediate nodes don't keep the sink identity. I believe this is an interesting paper, given that it proposes an application of several distributed system issues. One thing that comes into my mind is to apply gossiping mechanisms into this protocol. For sharing the states of caches it can be very valuable to gossip partial states of caches between nodes. As energy consumption is an important issue in this case, the gossiping can be made over the message transmission (i.e. by piggybacking cache updates on top of messages). Such optimization can provide more fresh caches into the system. Another enhancement opportunity arises with similar queries into the system. Perhaps nodes A and B are neighbors and both are interested in the same task. By keeping track of the source of the tasks, several bandwidth consumption improvements are possible. For example, given a set of neighboring nodes that are interested in the same issue, we can build a spanning tree that deliver efficiently the answer to all those nodes. The reinforc! em! ent module strengthens the path according to local rules. I wonder whether it is possible to consider locality to reinforce the shortest path to the source. I really didn't understand the figure 5.b. Apparently the curve is really hectic when we change the number of nodes in the network. I guess it shouldn't be like that (I was expecting a smoother curve) or at least it should be an explanation. The proposal doesn't take into account neither mobile agents nor mechanisms to deal with multiple route reinforcement.