Collection Tree Protocol
The Collection Tree Protocol (CTP) is a routing protocol for wireless sensor networks. It is used for transferring data from one or more sensors to one or more root nodes.
Algorithm
The number of expected transmissions needed to send data between two nodes, ETX, is used as the routing metric. This assumes packets are retransmitted at the link layer. Routes with a lower metric are preferred. In a route that includes multiple hops, the metric is the sum of the ETX of the individual hops.
Each node that wishes to collect data advertises itself as a tree root. Each node sends its data to the tree root to which it is nearest, that is, the tree root from which it is separated by the smallest ETX. A tree root always has an ETX of zero.
- [math]\displaystyle{ \mathrm{ETX_{root}} = 0 }[/math]
- [math]\displaystyle{ \mathrm{ETX_{node}} = \mathrm{ETX_{parent}} + \mathrm{ETX_{link}} }[/math]
Each node only keeps the smallest ETX (to the nearest tree root). The collection of ETX values is known as a gradient, and messages are only sent down the gradient from nodes with higher ETX to nodes with smaller ETX. This kind of forwarding is common to many algorithms and protocols in wireless sensor networks.
Rapidly changing link qualities, for example in sensor networks with moving nodes, cause routing information to become outdated which can lead to routing loops. CTP attempts to address these issues through datapath validation and adaptive beaconing.
Datapath validation
Each packet contains the ETX from the sender to the root. If a node receives a packet with ETX lower than its own this indicates an inconsistency in the tree. This triggers the transmission of a beacon frame. The goal is to have the sender of the packet receive the beacon frame and adjust its ETX accordingly.
Adaptive beaconing
The interval with which nodes broadcast beacons presents a tradeoff. If beacons were sent more frequently the routing information would be up to date more often and the network would respond to changes in topology faster. However, sending beacons more frequently leaves less bandwidth for application level data and uses more energy. To get around this CTP uses adaptive beaconing. It sends beacons faster when it detects problems. If it doesn't detect problems it exponentially decreases the beacon sending rate.
References
- Fonseca, Rodrigo; Gnawali, Omprakash; Jamieson, Kyle; Kim, Sukun; Levis, Philip; Woo, Alec (2006–2007). "CTP". tiny OS. http://www.tinyos.net/tinyos-2.x/doc/html/tep123.html.
- Gnawali, Omprakash; Fonseca, Rodrigo; Jamieson, Kyle; Moss, David; Levis, Philip (2009). "Collection tree protocol". SenSys: 1–14.
 |  |
