X-Git-Url: https://oss.titaniummirror.com/gitweb/?a=blobdiff_plain;f=doc%2Fhtml%2Ftep119.html;h=5f9a15ef1cb302390b2d6ee0f8098defd6c0fc9a;hb=e9bfab607e051bae6afb47b44892ce37541d1b44;hp=32516a775e15b1933b0a5c6c365bf0a15c6f62b4;hpb=e375f4f25e4f47409d09d6a13f57aff159c20886;p=tinyos-2.x.git diff --git a/doc/html/tep119.html b/doc/html/tep119.html index 32516a77..5f9a15ef 100644 --- a/doc/html/tep119.html +++ b/doc/html/tep119.html @@ -41,11 +41,6 @@ blockquote.epigraph { dd { margin-bottom: 0.5em } -/* Uncomment (& remove this text!) to get bold-faced definition list terms -dt { - font-weight: bold } -*/ - div.abstract { margin: 2em 5em } @@ -296,8 +291,8 @@ ul.auto-toc {
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,38 +463,27 @@ 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 @@ -482,161 +504,15 @@ 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
-