CTP: Collection Tree Protocol

Introduction

Most sensor networks are used to collect information from the physical world. Examples include sensor networks deployed to monitor micro-climates in agriculture farms and deployments that measure energy consumption in office or residential buildings. The nodes in these networks collect information about the physical world using their sensors and relay the sensor readings to a central base station or server using multi-hop wireless communication.

Collecting information reliably and efficiently from the nodes in a sensor network is a challenging problem, particularly due to the wireless dynamics. Multihop routing in a dynamic wireless environment requires that a protocol can adapt quickly to the changes in the network (agility) while the energy-constrains of sensor networks dictate that such mechanisms not require too much communication among the nodes (efficiency). CTP is a collection routing protocol, that achieves both agility and efficiency, while offering highly reliable data delivery in sensor networks.

CTP has been used in research, teaching, and in commercial products. Experiences with CTP has also informed the design of the IPv6 Routing Protocol for Low power and Lossy Networks (RPL).

CTP Mechanisms

CTP is a distance vector routing protocol designed for sensor networks. CTP computes the routes from each node in the network to the root (specified destinations) in the network. CTP uses these three mechanisms to overcome the challenges faced by distance vector routing protocol in a highly dynamic wireless network:

Agile and Accurate Link Quality Estimation: The links in a wireless network are highly dynamic and exhibit bursty behavior over short time scales. This property of wireless links suggests that a link quality must be agile for it to be accurate. The four-bit link estimator used in CTP uses information from the physical, data link, and network layers to provide accurate link quality estimates despite these challenges.

Datapath Validation: In a dynamic wireless environment, a routing path that is reliable at one point can become unreliable or even unavailable within a few seconds. Due to changing link qualities, loops can form and cause network congestion and energy drain due to looping packets. Thus, these problems in the routing path must be detected as quickly as they occurr. CTP uses datapath validation to detect these problems at the timescale of data packet transmission (a few tens of milliseconds). It does so by using data packets transmissions and receptions as topology probes and quickly detecting the problem when the packets do not make progress towards the destination in the routing metric space.

Adaptive Beaconing: Routing protocols typically broadcast control packets at a fixed interval (e.g., every 30 seconds). This interval poses a basic tradeoff. A small interval, i.e., frequent beacons, makes the protocol more responsive to the changes in the network, but uses more bandwidth and energy. A large interval uses less bandwidth and energy but can let topological problems persist for a long time. CTP uses adaptive beaconing to break this tradeoff. When the topology is inconsistent and has problems, it sends beacons faster. Otherwise, it decreases the beaconing rate exponentially. Thus, CTP can quickly respond to adverse wireless dynamics while incuring low control overhead in the long term.

Publications

Omprakash Gnawali, Rodrigo Fonseca, Kyle Jamieson, David Moss, and Philip Levis, Collection Tree Protocol, In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems (SenSys), 2009. BibTex [Slides from the talk: PDF PPT]

Experiment logs for the results in the paper is available on the CTP Data page.

CTP uses the four-bit link quality estimator, which is described in this paper:

Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, Philip Levis, Four Bit Wireless Link Estimation, In Proceedings of the Sixth Workshop on Hot Topics in Networks (HotNets VI), November 2007. [Slides from the talk]

Deployments

  • There is a 330-node CTP deployment in China called GreenOrbs. GreenOrbs continuously monitors the environment in a forest. More information available at greenorbs.org.
  • There is a 200-node CTP deployment at Stanford called Powernet. Powernet monitors energy used by computing equipments in the computer science department.
  • Rincon Research deployed CTP for surveillence application.
  • There is a microclimate monitoring company (which declined to be listed on this page) that deploys CTP commercially.
Powernet Deployment map
CTP Routing Topology on Powernet

CTP and the Internet

Our work on CTP has informed the work done by the IETF ROLL Working Group standardizing a protocol called RPL, which is an IPv6 routing protocol that will run on low power networks with lossy links, of which sensor network is one example. RPL incorporates two key mechanisms (adaptive beaconing and datapath validation) that were studied and evaluated in our CTP work. Omprakash Gnawali and Philip Levis contributed their experiences from CTP as co-authors of these IETF documents:
  • T. Winter, P. Thubert, A. Brandt, T. Clausen, J. Hui, P. Levis, K. Pister, R. Struik, JP. Vasseur, RPL: IPv6 Routing Protocol for Low power and Lossy Networks (draft-ietf-roll-rpl-19)
  • O. Gnawali, P. Levis, The Minimum Rank Objective Function with Hysteresis (draft-ietf-roll-minrank-hysteresis-of-01)
  • P. Levis, T. Clausen, J. Hui, O. Gnawali, J. Ko, RFC 6206: The Trickle Algorithm (RFC 6206)

CTP as a Benchmark

CTP has become a de-facto standard in collection routing in sensor networks and is used by researchers as a baseline against which new protocol mechanisms or designs are evalauted. Here are some examples:
  • Scott H Moeller, Avinash Sridharan, Bhaskar Krishnamachari, and Omprakash Gnawali, Routing Without Routes: The Backpressure Collection Protocol, IPSN 2010.
  • Hackmann, G., Chipara, O., and Lu, C. 2008, Robust topology control for indoor wireless sensor networks, SenSys 2008.
  • Alizai, M. H., Landsiedel, O., Link, J. A., Gotz, S., and Wehrle, K. 2009. Bursty traffic over bursty links, SenSys 2009.

CTP as an Enabling Research

CTP, by providing a stable code base for a robust and reliable collection routing, has enabled research on mechanisms and systems up the protocol stack and also development of interesting applications and prototypes. Here are some examples:
  • Octav Chipara, Chenyang Lu, homas C. Bailey, Gruia-Catalin Roman, Reliable Clinical Monitoring using Wireless Sensor Networks: Experience in a Step-down Hospital Unit, SenSys 2010.
  • Chieh-Jan Mike Liang, Nissanka B. Priyantha, Jie Liu, Andreas Terzis, Surviving Wi-Fi Interference in Low Power ZigBee Networks, SenSys 2010.
  • Peng Li, John Regehr, T-Check: Bug Finding for Sensor Networks, IPSN 2010.
  • James Horey, Arthur Maccabe and Eric Nelson. Tables: A Spreadsheet-Inspired Programming Model for Sensor Networks, DCOSS 2010.
  • Omprakash Gnawali, Leonidas Guibas, and Philip Levis, A Case for Evaluating Sensor Network Protocols Concurrently, WiNTECH 2010.
  • JeongGil Ko, T.Gao, A.Terzis, Empirical Study of a Medical Sensor Application in an Urban Emergency Department, BodyNets 2009.
  • Yang Chen, Omprakash Gnawali, Maria Kazandjieva, Philip Levis, John Regehr, Surviving Sensor Network Software Faults, SOSP 2009.
  • Muhammad Hamad Alizai, Olaf Landsiedel, Jo Agila Bitsch Link, Stefan Gotz, and Klaus Wehrle, Bursty traffic over bursty links, SenSys 2009.

Implementations

CTP has been tested on 13 different testbeds, seven hardware platforms, and six different link layers. Here are some implementations that we know of:
  • TinyOS includes a nesC implementation of CTP. [Link]
  • Mantis OS includes a C implementation of CTP. [Tarball]
  • There is a Java implementation of CTP for Sun SPOTs at dev.java.net. [Link]
  • There is a C implementation of CTP in Contiki OS.
  • There is a C++ implementation of CTP by Ugo Colesanti and Silvia Santini for Castalia WSN simulator 3.0. [Link to Google Code] [Stanford copy - Zip]
  • There is a CTP implementation on Linux/Click by Jung Il Choi, Mayank Jain, Jung Woo Lee, and Juan Batiz-Benet from Stanford. [Tarball]
This ETH Zurich Technical Report has an excellent description of TinyOS CTP implementation:

Ugo Colesanti, Silvia Santini, The Collection Tree Protocol for the Castalia Wireless Sensor Networks Simulator, Technical Report No. 729, Department of Computer Science, ETH Zurich, Zurich, Switzerland, June 2011. [Stanford copy]

People

Omprakash Gnawali (lead), Philip Levis, Rodrigo Fonseca, Kyle Jamieson, and David Moss.

Last updated: July 15, 2011