CTP: Collection Tree Protocol
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 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
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.
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,
Bit Wireless Link Estimation, In Proceedings of the Sixth
Workshop on Hot Topics in Networks (HotNets VI), November 2007. [Slides
from the talk]
- 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
- 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
- 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
- Omprakash Gnawali, Leonidas Guibas, and Philip Levis, A Case
for Evaluating Sensor Network Protocols Concurrently, WiNTECH
- JeongGil Ko, T.Gao, A.Terzis, Empirical Study of a Medical
Sensor Application in an Urban Emergency Department, BodyNets
- Yang Chen, Omprakash Gnawali, Maria Kazandjieva, Philip Levis,
John Regehr, Surviving Sensor Network Software Faults, SOSP
- Muhammad Hamad Alizai, Olaf Landsiedel, Jo Agila Bitsch Link,
Stefan Gotz, and Klaus Wehrle, Bursty traffic over bursty
links, SenSys 2009.
CTP has been tested on 13 different testbeds, seven hardware
platforms, and six different link layers. Here are some
implementations that we know of:
This ETH Zurich Technical Report has an excellent description of TinyOS CTP implementation:
- 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
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]
Omprakash Gnawali (lead), Philip Levis, Rodrigo Fonseca, Kyle
Jamieson, and David Moss.