This format keeps data at a fixed but platform dependent offset, which +is important when passing a message buffer between two different link layers. If the data payload were at different offsets for different link layers, then passing a packet between two link layers would require a memmove(3) diff --git a/doc/html/tep112.html b/doc/html/tep112.html index 233585f5..fdde709e 100644 --- a/doc/html/tep112.html +++ b/doc/html/tep112.html @@ -303,9 +303,9 @@ ul.auto-toc { Robert Szewczyk, Philip Levis, Martin Turon, Lama Nachman, Philip Buonadonna, Vlado Handziski Draft-Created:19-Sep-2005 -Draft-Version:1.5 +Draft-Version:1.6 -Draft-Modified:2006-12-12 +Draft-Modified:2006-12-20 Draft-Discuss:TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu> @@ -386,7 +386,7 @@ introduce wakeup latency, a factor which could be of interest to higher-level components. While wakeup latency is not a significant issue on very low power microcontrollers, such as the Atmega128 and MSP430, more powerful processors, such as the Xscale family (the basis -of platforms such as the imote2) can power states with wakeup +of platforms such as the imote2) can have power states with wakeup latencies as large as 5ms. For some application domains, this latency could be a serious issue. Higher level components therefore need a way to give the TinyOS microcontroller power manager information on their @@ -577,9 +577,10 @@ timer stack for the Atmega128 microcontroller family.

At the HIL level, TinyOS subsystems generally have a simple, imperative power management interface. Depending on the latencies -involved, this interface is either StdControl or SplitControl. +involved, this interface is either StdControl, SplitControl, +or AsyncStdControl. These interfaces are imperative in that when any component calls -StdControl.stop on another component, it causes the subsystem that +stop on another component, it causes the subsystem that component represents to enter an inactive, low-power state.

From the perspective of MCU power management, this transition causes a change in status and control registers (e.g., a clock is diff --git a/doc/html/tep114.html b/doc/html/tep114.html index 5476f57c..0716697f 100644 --- a/doc/html/tep114.html +++ b/doc/html/tep114.html @@ -303,9 +303,9 @@ ul.auto-toc { Gilman Tolle, Philip Levis, and David Gay Draft-Created:30-Oct-2005 -Draft-Version:1.1.2.4 +Draft-Version:1.6 -Draft-Modified:2006-08-30 +Draft-Modified:2006-12-12 Draft-Discuss:TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu> @@ -354,12 +354,12 @@ and so could be easily placed in a task.

Finally, the simplicity of the ADC interface has led many sensors to introduce several new ones for calibration and control, such as Mic and MagSetting. Because ADCs generally do not have error conditions, the ADC interface has no way to signal that a sample @@ -422,6 +422,12 @@ fail while a read is pending MUST provide a ReadWrite interface.

If the result parameter of the Read.readDone and ReadWrite.readDone events is not SUCCESS, then the memory of the val parameter MUST be filled with zeroes.

If the call to Read.read has returned SUCCESS, but the +Read.readDone event has not yet been signalled, then a subsequent +call to Read.read MUST not return SUCCESS. This simple locking +technique, as opposed to a more complex system in which multiple +read/readDone pairs may be outstanding, is intended to reduce the +complexity of code that is a client of a SID interface.

Examples of sensors that would be suited to this class of interface include many basic sensors, such as photo, temp, voltage, and ADC readings.

Collection

@@ -306,7 +307,6 @@ ul.auto-toc {

Note

This memo documents a part of TinyOS for the TinyOS Community, and @@ -314,29 +314,36 @@ requests discussion and suggestions for improvements. Distribution of this memo is unlimited. This memo is in full compliance with TEP 1.

Abstract

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.

+multihop delivery of packets to the root of a tree. There may be +multiple roots in a network, and in this case the semantics implemented +are of anycast delivery to at least one of the roots. A node sending +a packet does not specify which root the packet is destined to.

1. Introduction

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 +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 +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.

+it is an anycast protocol. The semantics is that the protocol +will make a reasonable effort to deliver the message to at least +one of the roots in the network. There are however no guarantees of +delivery, and there can be duplicates delivered to one or more +roots. There is also no ordering guarantees.

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 @@ -347,8 +354,8 @@ family:

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 +
Duplicate suppression, detecting and dealing with when lost +acknowledgments are causing packets to replicate in the network, wasting bandwidth.
Link estimation, evaluating the link quality to single-hop neighbors.

The rest of this document describes a set of components and interfaces for a collection service outlined above.

2. Collection interfaces

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 consumer is a root of a tree. 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.

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 +the the collection infrastructure. RootControl.unsetRoot() MUST +make the current root no longer a root in the collection infrastructure. +Both calls are idempotent. +RootControl.setRoot() MAY be called on a node that is already a root, to +no effect. RootControl.unsetRoot() MAY be called on a node that is not a root:

 interface RootControl {
@@ -395,13 +392,33 @@ interface RootControl {
   command bool isRoot();
 }

The collection infrastructure can be multiplexed among independent +applications, by means of a collection identifier. It is important +to note that the data traffic in the protocol is multiplexed, +while the control traffic is not.

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 identifier is 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 identifier is 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 identifier is 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 identifier is specified as a parameter +to Intercept during instantiation.

3 Collection Services

A collection service MUST provide one component, TreeCollectionC, +

3 Collection Services

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 +428,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 +

CollectionC 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 +

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 @@ -433,37 +449,22 @@ 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 +nodes. CollectionC 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. +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 TreeCollectionC +combined with the pass semantics of Send, require that CollectionC make a copy of the buffer if it signals Receive.receive.

If TreeCollectionC receives a data packet to forward and it is not a +

If CollectionC 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 +

If CollectionC receives a data packet that a different node is supposed to forward, it MAY signal Snoop.receive.

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.

3.1 CollectionSenderC

Collection has a virtualized sending abstraction, the generic component CollectionSenderC:

@@ -481,40 +482,47 @@ have a single packet format, so that receivers can parse a packet
 based on its collection ID and contents.

4 Implementation

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.

4.1 LinkEstimatorP

+tinyos-2.x/tos/lib/net/ctp and tinyos-2.x/tos/lib/net/le, in +the CTP protocol. It is beyond the scope of this document to fully +describe CTP, but we outline its main components. CTP will be +described in an upcoming TEP [2]. This implementation is a +reference implementation, and is not the only possibility. It +consists of three major components, which are wired together to form +a CollectionC: LinkEstimatorP, CtpTreeRoutingEngineP, and +CtpForwardingEngineP.

This decomposition tries to encourage evolution of components and +ease of use through modularization. Neighbor management and link +estimation are decoupled from the routing protocol. Furthermore, the +routing protocol and route selection are decoupled from the +forwarding policies, such as queueing and timing.

4.1 LinkEstimatorP

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:

+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 -- 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.getReverseQuality() MUST imply that the link to the +neighbor is estimated to be of a higher quality than the one that +results in a larger 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
 
@@ -542,52 +550,68 @@ interface LinkEstimator {
   command error_t clearDLQ(am_addr_t neighbor);
   event void evicted(am_addr_t neighbor);
 }
-
-interface NeighborTableEviction {
-  event void evicted(uint16_t neighbor)
-}

4.2 TreeRoutingEngineP

TreeRoutingEngineP is responsible for computing routes to the roots of a -tree. It uses NeighborTable and LinkEstimator interfaces to learn +

4.2 CtpRoutingEngineP

CtpRoutingEngineP is responsible for computing routes to the roots of a +tree. In traditional networking terminology, this is part of the +control plane of the network, and is does not directly forward any +data packets, which is the responsibility of CtpForwardingEngine. +The main interface between the two is UnicastNameFreeRouting.

CtpRoutingEngineP uses the LinkEstimator interface 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 +protocol with a single or multiple roots. CtpRoutingEngineP allows a node to be configured as a root or a non-root node -dynamically. TreeRoutingEngineP maintains multiple candidate next hops:

+dynamically. CtpRoutingEngineP 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;
-  }
+generic module CtpRoutingEngineP(uint8_t routingTableSize,
+                                 uint16_t minInterval,
+                                 uint16_t maxInterval) {
+    provides {
+        interface UnicastNameFreeRouting as Routing;
+        interface RootControl;
+        interface CtpInfo;
+        interface StdControl;
+        interface CtpRoutingPacket;
+        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 Timer<TMilli> as RouteTimer;
+        interface Random;
+        interface CollectionDebug;
+        interface CtpCongestion;
+    }
+}
+

+interface UnicastNameFreeRouting {
+  command am_addr_t nextHop();
+
+  command bool hasRoute();
+  event void routeFound();
+  event void noRoute();
 }

4.3 ForwardingEngineP

The ForwardingEngineP component provides all the top level interfaces -(except RootControl) which TreeCollectionC provides and an application -uses:

4.3 CtpForwardingEngineP

The CtpForwardingEngineP component provides all the top level interfaces +(except RootControl) which CollectionC provides and an application +uses. It deals with retransmissions, duplicate suppression, packet +timing, loop detection, and also informs the LinkEstimator of the +outcome of attempted transmissions.:

-generic module ForwardingEngineP() {
+generic module CtpForwardingEngineP() {
   provides {
     interface Init;
     interface StdControl;
@@ -597,20 +621,24 @@ generic module ForwardingEngineP() {
     interface Intercept[collection_id_t id];
     interface Packet;
     interface CollectionPacket;
+    interface CtpPacket;
+    interface CtpCongestion;
   }
   uses {
+    interface SplitControl as RadioControl;
     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 LinkEstimator;
+    interface Timer<TMilli> as CongestionTimer;
+    interface Cache<message_t*> as SentCache;
+    interface CtpInfo;
     interface PacketAcknowledgements;
     interface Random;
     interface RootControl;
@@ -620,14 +648,14 @@ generic module ForwardingEngineP() {
   }
 }

ForwardingEngineP uses a large number of interfaces, which can be +

CtpForwardingEngineP 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
+
Routing: UnicastNameFreeRouting, RootControl, CtpInfo, +CollectionId, SentCache

Queue and buffer management: SendQueue, MessagePool, QEntryPool

Packet timing: Random, RetxmitTimer
@@ -635,10 +663,10 @@ QEntryPool

5. Author's Address

-Rodrigo Fonseca 

+Rodrigo Fonseca
473 Soda Hall
Berkeley, CA 94720-1776

@@ -647,9 +675,9 @@ QEntryPool
 
Omprakash Gnawali

-Ronald Tutor Hall (RTH) 418 

+Ronald Tutor Hall (RTH) 418
3710 S. McClintock Avenue

-Los Angeles, CA 90089 

+Los Angeles, CA 90089

phone - +1 213 821-5627
email - gnawali@usc.edu

@@ -658,7 +686,7 @@ QEntryPool
 Kyle Jamieson
The Stata Center
32 Vassar St.

-Cambridge, MA 02139 

+Cambridge, MA 02139

email - jamieson@csail.mit.edu

@@ -673,14 +701,20 @@ QEntryPool
 email - pal@cs.stanford.edu

6. Citations

[1]	TEP 116: Packet Protocols

+ + + + + +

[2]	TEP 124: The Collection Tree Protocol (CTP) - (upcoming)

diff --git a/doc/txt/tep111.txt b/doc/txt/tep111.txt index 17fe6f61..871a6a07 100644 --- a/doc/txt/tep111.txt +++ b/doc/txt/tep111.txt @@ -144,7 +144,8 @@ message_t structure is defined in ``tos/types/message.h``:: nx_uint8_t metadata[sizeof(message_metadata_t)]; } message_t; -This format keeps data at a fixed offset, which is important when +This format keeps data at a fixed but platform dependent offset, which +is important when passing a message buffer between two different link layers. If the data payload were at different offsets for different link layers, then passing a packet between two link layers would require a ``memmove(3)`` diff --git a/doc/txt/tep112.txt b/doc/txt/tep112.txt index dc5b1e26..8c2cb096 100644 --- a/doc/txt/tep112.txt +++ b/doc/txt/tep112.txt @@ -97,7 +97,7 @@ introduce wakeup latency, a factor which could be of interest to higher-level components. While wakeup latency is not a significant issue on very low power microcontrollers, such as the Atmega128 and MSP430, more powerful processors, such as the Xscale family (the basis -of platforms such as the imote2) can power states with wakeup +of platforms such as the imote2) can have power states with wakeup latencies as large as 5ms. For some application domains, this latency could be a serious issue. Higher level components therefore need a way to give the TinyOS microcontroller power manager information on their @@ -256,9 +256,10 @@ timer stack for the Atmega128 microcontroller family. At the HIL level, TinyOS subsystems generally have a simple, imperative power management interface. Depending on the latencies -involved, this interface is either ``StdControl`` or ``SplitControl``. +involved, this interface is either ``StdControl``, ``SplitControl``, +or ``AsyncStdControl``. These interfaces are imperative in that when any component calls -``StdControl.stop`` on another component, it causes the subsystem that +``stop`` on another component, it causes the subsystem that component represents to enter an inactive, low-power state. From the perspective of MCU power management, this transition causes a diff --git a/doc/txt/tep114.txt b/doc/txt/tep114.txt index 2d4b2bd8..407cb40d 100644 --- a/doc/txt/tep114.txt +++ b/doc/txt/tep114.txt @@ -62,13 +62,13 @@ Additionally, not all sensors require ADC conversions from the MCU. Many sensors today are digital. To sample these sensors, the MCU sends a sample command and receives the corresponding data over a bus (e.g., SPI, I2C). The latency involved, combined with possible Resource -arbitration [_tep108], means that these bus operations are often +arbitration [1]_, means that these bus operations are often synchronous code. In the command direction, this can force a task allocation to convert async to sync; in the event direction, the application has to deal with async code even though the event is, in practice, in a task. -Finallly, the simplicity of the ADC interface has led many sensors to +Finally, the simplicity of the ADC interface has led many sensors to introduce several new ones for calibration and control, such as ``Mic`` and ``MagSetting``. Because ADCs generally do not have error conditions, the ADC interface has no way to signal that a sample @@ -374,3 +374,8 @@ connect a sensor into a more general system. | email - david.e.gay@intel.com | +6. Citations +============================================================================ + +.. [1] TEP 108: Resource Arbitration. + diff --git a/doc/txt/tep119.txt b/doc/txt/tep119.txt index e1b48d18..32cef9f7 100644 --- a/doc/txt/tep119.txt +++ b/doc/txt/tep119.txt @@ -204,8 +204,6 @@ component CollectionSenderC:: } } - - This abstraction follows a similar virtualization approach to AMSenderC [1_], except that it is parameterized by a collection_id_t rather than an am_id_t. As with am_id_t, every collection_id_t SHOULD -- 2.39.2