X-Git-Url: https://oss.titaniummirror.com/gitweb/?a=blobdiff_plain;f=doc%2Fhtml%2Ftep119.html;h=5f9a15ef1cb302390b2d6ee0f8098defd6c0fc9a;hb=e9bfab607e051bae6afb47b44892ce37541d1b44;hp=8fcd25be7374e714ba1290a3b06aa097b475c7e5;hpb=8da35bf66fd29352b990b0f7f0db564c7bd64038;p=tinyos-2.x.git diff --git a/doc/html/tep119.html b/doc/html/tep119.html index 8fcd25be..5f9a15ef 100644 --- a/doc/html/tep119.html +++ b/doc/html/tep119.html @@ -3,7 +3,7 @@
- +Type: | Documentary | |
---|---|---|
Status: | -Draft | |
TinyOS-Version: | 2.x | +Final |
TinyOS-Version: | > 2.1 | |
Author: | Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, and Philip Levis |
Note
This memo documents a part of TinyOS for the TinyOS Community, and @@ -314,80 +309,113 @@ requests discussion and suggestions for improvements. Distribution of this memo is unlimited. This memo is in full compliance with TEP 1.
The memo documents the interfaces, components, and semantics used by -collection protocol in TinyOS 2.x. Collection provides a best-effort, -multihop delivery of packets to the root of a tree.
+the collection protocols in TinyOS 2.x. Collection provides +best-effort, multihop delivery of packets to one of a set of +collection points. There may be multiple collection points in a +network, and in this case the semantics are anycast delivery to at +least one of the collection points. A node sending a packet does not +specify which of the collection points the packet is destined to. The +union of the paths from each node to one or more of the collection +points forms a set of trees, and in this document we assume that +collection points are the roots of these trees.Collecting data at a base station is a common requirement of sensor -network applications. The general approach used is to build one -or more collection trees, each of which is rooted at a base -station. When a node has data which needs to be collected, it -sends the data up the tree, and it forwards collection data that -other nodes send to it. Sometimes, depending on the form of data -collection, systems need to be able to inspect packets as they go -by, either to gather statistics, compute aggregates, or suppress -redundant transmissions.
-When a network has multiple base stations that act as root nodes, -rather than one tree, it has a forest of trees. By picking a -parent node, a collection protocol implicitly joins one of these -trees. Collection provides a best-effort, -multihop delivery of packets to one of a network's tree roots: -it is an anycast protocol.
-Given the limited state that nodes can store and a general need -for distributed tree building algorithms, simple collection protocols -encounter several challenges. These challenges are not unique to -collection protocols. Instead, they represent a subset of common -networking algorithmic edge cases that occur in this protocol -family:
+network applications. The general approach used is to build one or +more collection trees, each of which is rooted at a base station. When +a node has data which needs to be collected, it sends the data up the +tree, and it forwards collection data that other nodes send to +it. Sometimes, depending on the form of data collection, systems need +to be able to inspect packets as they go by, either to gather +statistics, compute aggregates, or suppress redundant transmissions. +Collection provides best-effort, multihop delivery of packets to one +of a network's tree roots: it is an anycast protocol. The +semantics are that the protocol will make a reasonable effort to +deliver the message to at least one of the roots in the network. By +picking a parent node, a node implementing the collection protocol +inductively joins the tree its parent has joined. Delivery is best +effort, and there can be duplicates delivered to one or more roots. +Collection provides no ordering or real-time guarantees, although +specific implementations may extend the basic functionality to do +so.
+Given the limited state that nodes can store and a general need for +distributed tree building algorithms, collection protocols encounter +several challenges. These challenges are not unique to collection +protocols. Instead, they represent a subset of common networking +algorithmic edge cases that generally occur in wireless routing:
--
- Loop detection, detecting when a node selects one of its -descendants as a new parent.
-- Duplicate suppression, detecting and dealing with when lost -acknowledgments are causing packets to replicate in the -network, wasting bandwidth.
+- Loop detection, for when a node selects one of its descendants as +a next hop.
+- Duplicate suppression, detecting and dealing with lost +acknowledgments that can cause packets to replicate in the +network, wasting capacity.
- Link estimation, evaluating the link quality to single-hop neighbors.
- Self-interference, preventing forwarding packets along the route from introducing interference for subsequent packets.
The rest of this document describes a set of components and interfaces -for a collection service outlined above.
+While collection protocols can take a wide range of approaches to +address these challenges, the programming interface they provide is +typically independent of these details. The rest of this document +describes a set of components and interfaces for collection services.
A node can perform four different roles in collection: producer, -consumer, snooper, and in-network processor. Depending on their role, -the nodes use different interfaces to interact with the collection -component.
-The nodes that generate data to be sent to the root are -producers. The producers use the Send interface [1] to send -data to the root of the collection tree. The collection tree -identifier is be specified as a parameter to Send during -instantiation.
-Root nodes that receive data from the network are consumers. The -consumers use the Receive interface [1] to receive a message -delivered by collection. The collection tree identifier is be -specified as a parameter to Receive during instantiation.
-The nodes that overhear messages in transit are snoopers. The snoopers -use the Receive interface [1] to receive a snooped message. The -collection tree identifier is be specified as a parameter to Receive -during instantiation.
-The nodes can process a packet that are in transit. These in-network -processors use the Intercept interface [1] to receive and -update a packet. The collection tree identifier is be specified as a -parameter to Intercept during instantiation.
-A node is configured to become a root by using the RootControl -interface. RootControl.setRoot() MUST make the current node a root of -the tree specified during instantiation. RootControl.unsetRoot() MUST -make the current root no longer a root in the tree specified during -instantiation. RootControl.unsetRoot() MAY be called on a node that is -not a root:
+A node can perform four different roles in collection: sender (or +source), snooper, in-network processor, and receiver (or +root). Depending on their role, the nodes use different interfaces to +interact with the collection component.
+The collection infrastructure can be multiplexed among independent +applications, by means of a collection identifier. The collection +identifier is used to identify different data traffic at the sender, +intermediate-nodes, or the receiver, much like port number in TCP. All +data traffic, regardless of the collection identifier, use the same +routing topology.
+The nodes that generate data to be sent to the root are senders. +Senders use the Send interface [1] to send data to the root of +the collection tree. The collection identifier is specified as a +parameter to Send during instantiation.
+The nodes that overhear messages in transit are snoopers. The +snoopers use the Receive interface [1] to receive a snooped +message. The collection identifier is specified as a parameter +to Receive during instantiation.
+The nodes can process a packet that is in transit. These in-network +processors use the Intercept interface to receive and update a +packet. The collection identifier is specified as a parameter to +Intercept during instantiation. The Intercept interface has this +signature:
++interface Intercept { + event bool forward(message_t* msg, void* payload, uint8_t len); +} ++
Intercept has a single event, Intercept.forward(). A collection +service SHOULD signal this event when it receives a packet to forward. +If the return value of the event is FALSE, then the collection layer +MUST NOT forward the packet. The Intercept interface allows a higher +layer to inspect the internals of a packet and suppress it if needed. +Intercept can be used for duplicate suppression, aggregation, and +other higher-level services. As the handler of Intercept.forward() +does not receive ownership of the packet, it MUST NOT modify the +packet and MUST copy data out of the packet which it wishes to use +after the event returns.
+Root nodes that receive data from the network are receivers. Roots +use the Receive interface [1] to receive a message delivered by +collection. The collection identifier is specified as a parameter to +Receive during instantiation.
+The set of all roots and the paths that lead to them form the +collection routing infrastructure in the network. For any connected +set of nodes implementing the collection protocol there is only one +collection infrastructure, i.e., all roots in this set active at the +same time are part of the same infrastructure.
+The RootControl interface configures whether a node is a +root:
interface RootControl { command error_t setRoot(); @@ -395,13 +423,19 @@ interface RootControl { command bool isRoot(); }+
The first two commands MUST return SUCCESS if the node is now in the +specified state, and FAIL otherwise. For example, if a node is already +a root and an application calls RootControl.setRoot(), the call will +return SUCCESS. If setRoot() returns SUCCESS, then a subsequent call +to isRoot() MUST return TRUE. If unsetRoot() returns SUCCESS, then a +subsequent call to isRoot() MUST return FALSE.
A collection service MUST provide one component, TreeCollectionC, +
A collection service MUST provide one component, CollectionC, which has the following signature:
-configuration TreeCollectionC { +configuration CollectionC { provides { interface StdControl; interface Send[uint8_t client]; @@ -411,18 +445,17 @@ configuration TreeCollectionC { interface RootControl; interface Packet; interface CollectionPacket; - interface TreeRoutingInspect; } uses { interface CollectionId[uint8_t client]; } }-
TreeCollectionC MAY have additional interfaces, but they MUST have -default functions on all outgoing invocations (commands for uses, -events for provides) of those interfaces so that it can operate -properly if they are not wired.
-Components SHOULD NOT wire to TreeCollectionC.Send. The generic +
CollectionC MAY have additional interfaces. All outgoing invocations +(commands for uses, events for provides) of those interfaces MUST have +default functions. Those default functions enable CollectionC to +operate properly even when the additional interfaces are not wired.
+Components SHOULD NOT wire to CollectionC.Send. The generic component CollectionSenderC (described in section 3.1) provides a virtualized sending interface.
Receive, Snoop, and Intercept are all parameterized by @@ -430,40 +463,29 @@ collection_id_t. Each collection_id_t corresponds to a different protocol operating on top of collection, in the same way that different am_id_t values represent different protocols operating on top of active messages. All packets sent with a particular -collection_id_t generally have the same payload format, so that -snoopers, intercepters, and receivers can parse it properly.
-Receive.receive MUST NOT be signaled on non-root -nodes. TreeCollectionC MAY signal Receive.receive on a root node when -a data packet successfully arrives at that node. If a root node calls -Send, TreeCollectionC MUST treat it as it if were a received packet. -Note that the buffer swapping semantics of Receive.receive, when -combined with the pass semantics of Send, require that TreeCollectionC -make a copy of the buffer if it signals Receive.receive.
-If TreeCollectionC receives a data packet to forward and it is not a -root node, it MAY signal Intercept.forward.
-If TreeCollectionC receives a data packet that a different node -is supposed to forward, it MAY signal Snoop.receive.
+collection_id_t generally SHOULD have the same payload format, so that +snoopers, intercepters, and receivers can parse them properly. +ColletionC MUST NOT signal Receive.receive on non-root +nodes. CollectionC MUST signal Receive.receive on a root node when a +unique (non-duplicate) data packet successfully arrives at that +node. It MAY signal Receive.receive when a duplicate data packet +successfully arrives. If a root node calls Send, CollectionC MUST +treat it as it if were a received packet. Note that the buffer +swapping semantics of Receive.receive, when combined with the pass +semantics of Send, require that CollectionC make a copy of the buffer +if it signals Receive.receive.
+If CollectionC receives a data packet to forward and it is not a root +node, it MAY signal Intercept.forward. CollectionC MAY signal +Snoop.receive when it hears a packet which a different node is +supposed to forward. For any given packet it receives, CollectionC +MUST NOT signal more than one of the Snoop.receive, Receive.receive, +and Intercept.forward events.
RootControl allows a node to be made a collection tree root. -TreeCollectionC SHOULD NOT configure a node as a root by default.
+CollectionC SHOULD NOT configure a node as a root by default.Packet and CollectionPacket allow components to access collection data packet fields [1].
-TreeRoutingInspect provides information on the current position of -the node in a routing tree:
--interface TreeRoutingInspect { - command error_t getParent(am_addr_t* parent); - command error_t getHopcount(uint8_t* hopcount); - command error_t getMetric(uint16_t* metric); -} --
In each of these commands, if the return value is not SUCCESS, the -value stored in the pointer argument is undefined. The getMetric -command provides a measure of the quality of a node's route to the -base station. This routing metric MUST be monotonically increasing -across hops. In a collection tree, if node A is the parent of node B, -then node B's metric value MUST be greater than node A's.
-Collection has a virtualized sending abstraction, the generic component CollectionSenderC:
@@ -481,164 +503,18 @@ have a single packet format, so that receivers can parse a packet based on its collection ID and contents.
An implementation of this TEP can be found in -tinyos-2.x/tos/lib/net/collection. The implementation consists of -three major components, which are wired together to form a -CollectionC: LinkEstimatorP, TreeRoutingEngineP, and ForwardingEngineP.
-This decomposition tries to encourage evolution of components and ease -of use through modularization. Neighbor management and link estimation -are are decoupled from the routing protocol. Furthermore, the routing -protocol and route selection are decoupled from the forwarding policies, -such as queueing and timing.
-LinkEstimatorP estimates the quality of link to or from each -neighbor. Link estimation can be done in a variety of ways, and we do -not impose one here. It is decoupled from the establishment of -routes. There is a narrow interface (LinkEstimator and -NeighborTableEviction) between the link estimator and the routing -engine. The one requirement is that the quality returned is -standardized. A smaller return value from LinkEstimator.getQuality(), -LinkEstimator.getforwardQuality(), LinkEstimator.getreserveQuality() -MUST imply that the link to the neighbor is estimated to be of a -higher quality than the one that results in a smaller return -value. The range of value SHOULD be [0,255] and the variation in link -quality in that range SHOULD be linear. Radio provided values such as -LQI or RSI, beacon based link estimation to compute ETX, or their -combination are some possible approaches to estimating link -qualities. LinkEstimatorP MAY have its own control messages to compute -bi-directional link qualities. LinkEstimatorP provides calls (txAck(), -txNoAck(), and clearDLQ()) to update the link estimates based on -successful or unsuccessful data transmission to the neighbors. The -user of LinkEstimatorP can call insertNeighbor() to manually insert a -node in the neighbor table, pinNeighbor() to prevent a neighbor from -being evicted, and unpinNeighbor() to restore eviction policy:
--typedef uint16_t neighbor_table_entry_t - -LinkEstimatorP { - provides { - interface StdControl; - interface AMSend as Send; - interface Receive; - interface LinkEstimator; - interface Init; - interface Packet; - interface LinkSrcPacket; - } -} - -interface LinkEstimator { - command uint8_t getLinkQuality(uint16_t neighbor); - command uint8_t getReverseQuality(uint16_t neighbor); - command uint8_t getForwardQuality(uint16_t neighbor); - command error_t insertNeighbor(am_addr_t neighbor); - command error_t pinNeighbor(am_addr_t neighbor); - command error_t unpinNeighbor(am_addr_t neighbor); - command error_t txAck(am_addr_t neighbor); - command error_t txNoAck(am_addr_t neighbor); - command error_t clearDLQ(am_addr_t neighbor); - event void evicted(am_addr_t neighbor); -} - -interface NeighborTableEviction { - event void evicted(uint16_t neighbor) -} -+
Implementations of collection can be found in +tinyos-2.x/tos/lib/net/ctp and tinyos-2.x/tos/lib/net/lqi. +The former is the Collection Tree Protocol (CTP), described in TEP 123 +[2]. The latter is a TinyOS 2.x port of MultihopLqi, a +CC2420-specific collection protocol in TinyOS 1.x.
TreeRoutingEngineP is responsible for computing routes to the roots of a -tree. It uses NeighborTable and LinkEstimator interfaces to learn -about the nodes in the neighbor table maintained by LinkEstimatorP and -the quality of links to and from the neighbors. The routing protocol -on which collection is implemented MUST be a tree-based routing -protocol with a single or multiple roots. TreeRoutingEngineP -allows a node to be configured as a root or a non-root node -dynamically. TreeRoutingEngineP maintains multiple candidate next hops:
--generic module TreeRoutingEngineP(uint8_t routingTableSize) { - provides { - interface UnicastNameFreeRouting as Routing; - interface RootControl; - interface TreeRoutingInspect; - interface StdControl; - interface Init; - } - uses { - interface AMSend as BeaconSend; - interface Receive as BeaconReceive; - interface LinkEstimator; - interface AMPacket; - interface LinkSrcPacket; - interface SplitControl as RadioControl; - interface Timer<TMilli> as BeaconTimer; - interface Random; - interface CollectionDebug; - } -} --
The ForwardingEngineP component provides all the top level interfaces -(except RootControl) which TreeCollectionC provides and an application -uses:
--generic module ForwardingEngineP() { - provides { - interface Init; - interface StdControl; - interface Send[uint8_t client]; - interface Receive[collection_id_t id]; - interface Receive as Snoop[collection_id_t id]; - interface Intercept[collection_id_t id]; - interface Packet; - interface CollectionPacket; - } - uses { - interface AMSend as SubSend; - interface Receive as SubReceive; - interface Receive as SubSnoop; - interface Packet as SubPacket; - interface UnicastNameFreeRouting; - interface SplitControl as RadioControl; - interface Queue<fe_queue_entry_t*> as SendQueue; - interface Pool<fe_queue_entry_t> as QEntryPool; - interface Pool<message_t> as MessagePool; - interface Timer<TMilli> as RetxmitTimer; - interface Cache<uint32_t> as SentCache; - interface TreeRoutingInspect; - interface PacketAcknowledgements; - interface Random; - interface RootControl; - interface CollectionId[uint8_t client]; - interface AMPacket; - interface CollectionDebug; - } -} --
ForwardingEngineP uses a large number of interfaces, which can be -broken up into a few groups of functionality:
----
-- Single hop communication: SubSend, SubReceive, SubSnoop, -SubPacket, PacketAcknowledgments, AMPacket
-- Routing: UnicastNameFreeRouting, TreeRoutingInspect, -RootControl, CollectionId, SentCache
-- Queue and buffer management: SendQueue, MessagePool, -QEntryPool
-- Packet timing: Random, RetxmitTimer
-
[1] | TEP 116: Packet Protocols |
[1] | TEP 116: Packet Protocols. |
[2] | TEP 123: The Collection Tree Protocol (CTP). |