Week 5: Presentation and Discussion of "Collection Tree Protocol"

O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis
SenSys 2009


This paper presents a collection tree protocol in wireless sensor networks -- CTP Noe, which has three contributions: first of all, it introduce two key principles, adaptive beaconing and datapath validation, to solve two tricky problems of routing in sensor networks, link dynamics and transient loops; second, it describes the design and implementation of CTP Noe; third, it provides a comparative study by estimating CTP Noe on 12 different testbeds.


We discuss a key problem first -- why collection preforms well in controlled situations yet poorly in practice? To know the reason, the authors have done some previous research on that, e.g., "An Empirical Study of Low Power Wireless" and "Four-bit Wireless Link Estimation". In short, the reason of this problem is that we don't understand low power link layer well or our model about it is impractical. On the one hand, current protocols typically use periodic beacons which can't adapt dynamic low power wireless link. On the other hand, rapid link topology changes bring transient loops which cause losses in data plane or long periods of disconnection. Previous solutions have to discard packets or pause the data transmission until next beaconing period. Why? Because in these solutions, topology repairs happen operates at a time scale orders of magnitude longer than data plane. So the authors' goal is to design a collection tree protocol which can adapt its beaconing rate efficiently and agilely, meanwhile, repair topology rapidly to avoid discarding packets and pausing the data transmission with a long time.


CTP Noe gives us a good solution with two mechanisms: datapath validation and adaptive beaconing. Datapath validation makes sure the routing protocol can update the stale datapath information in good time by using data packets. Adaptive beaconing increases agility and efficiency -- sending very few control beacons when the topology is consistent and quickly adapting when the datapath discovers a possible problem. With these two mechanisms, CTP Noe does not need to directly drop packets or pause a long time when meeting loops. How to achieve that? We discussed the reason at class. When transient loops occur, CTP Noe will decrease its beaconing interval to the lowest immediately which make it can repair the datapath at once. So packets only need to be paused for the length of the minimum beacon interval. However, former protocols, such as MultipleLQI and DSDV, can not achieve this, because fixing the datapath needs a long time. They have no choice: either drop or overflow.


Going in thorough details of implementation, we talked about several components in control plane and data plane. CTP Noe defines three events to trigger the beacon interval resetting: 1. P bit equals one; 2. cost drops significantly; 3. a topology inconsistency has been detected. We discussed the usage of these three events. In data plane design, some students misunderstand the concept of client queues. Actually the client here means an up-layer application or component of current sensor node. While the pool here is used to store coming packets from other sensors. Here the duplicate judgement is important because it decreases large and useless transmissions for duplicate packets from looping and false negatives of ack. For transmit timer, we discussed the reason why it needs at least two packet times between transmissions.


Finally, from all the figures and descriptions in evaluation, we can see that CTP Noe achieve reliability, robustness, efficiency and hardware independence. But in Figure 9, we don't know how to conclude that Channel 1 and 11 are most heavily used by the building occupants. 


Here's a few short descriptions from our reviews:

• The authors performed a good bit of research for the experiment, using a variety of testbeds and modifying the many of the parameters. In future tests, the authors could modify parameters that remained fixed over long periods in their tests. For example, IPI could be modified in tests instead of using fixed value. Also, nodes could be removed and reintroduced, instead of just removed(6.7). Another option is to add new nodes over some of the longer tests and look at delivery ratios.
• What happens in the event that the sink itself is intermittent?  Perhaps in a mobile ad hoc network, the sink leaves the network.  How do the nodes re‐route to a different sink? 
• It achieves the four major goals considerably but the question of this protocol being general to distance vector algorithms still remains to be answered, which on answered in the favor of collection protocols will take these protocol into much wider applications.