The Collection Tree Protocol (CTP)

Fonseca, Gnawali, Jamieson, Kim, Levis, Woo

sensor networking protocols data collection tiny-os

@misc{fonseca:tinyos2007,
  title={The Collection Tree Protocol {(CTP)}},
  author={Rodrigo Fonseca and Omprakash Gnawali and Kyle Jamieson and
          Sukun Kim and Philip Levis and Alec Woo},
  howpublished={\url{http://www.tinyos.net/tinyos-2.x/doc/html/tep123.html}},
  publisher={{TinyOS} Network Working Group},
  month={February},
  year={2007}
}

"Try very hard" best effort anycast datagram service to a collection root in a network

• Some nodes advertise as roots
• Other nodes form a tree to those roots, implicitly defined by next hops

CTP assumes all of the following

• Local broadcast comms
• Synchronous acknowledgments for unicast packets
• Protocol multiplexing from link layer
• Single-hop source and destination IDs on packets
• Estimates of number of transmissions required to successfully unicast to neighbor
• Low traffic rates, possibly not suited for higher traffic rates

ETX is calculated to the root node

• Routing loops are possible in CTP
  • Mechanism 1: Gradient values are included in each frame; if a lower value is seen it is discarded and a beacon generated
  • Mechanism 2: If the ETX goes beyond a reasonable constant the advertisement is dropped

Packet duplication may also occur, when ACKs are not received

• Frames carry originating address, sequence number, and Time Has Lived (THL) values
  • The THL is incremented on each transmission, meaning retransmissions will have the same THL and may be dropped, but a retransmission due to routing loops will have different THLs and won't be dropped (is this a good thing??)
• Maintains a small cache of these packets to check against

Beacons are sent at a dynamic rate very similar to the Trickle protocol (exponentially increasing, among other things)

Link quality estimation is done using both LEEP (estimation via dropped beacons) and direct monitoring of data transmission behavior