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. 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
+multihop delivery of packets to the root of a tree. There may be
+multiple tree roots in a network, and in this case the semantics
+are *anycast* delivery to at least one of the roots. A node sending
a packet does not specify which root the packet is destined to.
* 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.
2. Collection interfaces
====================================================================
A node can perform four different roles in collection: producer,
-consumer, snooper, and in-network processor. Depending on their role,
+snooper, in-network processor, and consumer. Depending on their role,
the nodes use different interfaces to interact with the collection
component.
-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 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 {
- command error_t setRoot();
- command error_t unsetRoot();
- 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,
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.
+*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. This interface allows a higher layer
+to inspect the internals of a packet and possibly suppress it if
+it is unnecessary or if its contents can be aggregated into an
+existing packet.
+
+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 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();
+ command error_t unsetRoot();
+ command bool isRoot();
+ }
+
+Both 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.
3 Collection Services
====================================================================
}
-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.
+CollectionC MAY have additional interfaces. These additional
+interfaces 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 CollectionC.Send. The generic
component CollectionSenderC (described in section 3.1) provides
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
+ColletionC MUST NOT signal Receive.receive on non-root
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, CollectionC MUST treat it as it if were a received packet.
}
}
-
-
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
====================================================================
An implementation of this TEP can be found in
-``tinyos-2.x/tos/lib/net/ctp`` and ``tinyos-2.x/tos/lib/net/le``, in
+``tinyos-2.x/tos/lib/net/ctp`` and ``tinyos-2.x/tos/lib/net/4bitle``, 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
+a CollectionC: LinkEstimatorP, CtpRoutingEngineP, and
CtpForwardingEngineP.
This decomposition tries to encourage evolution of components and
--------------------------------------------------------------------
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 -- 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.
+neighbor. In this TEP, we briefly describe the reference
+implementation in ''tinyos-2.x/tos/lib/4bitle'' and refer the readers
+to [3]_ for a detailed description of the estimator.
+
+Link estimation is decoupled from the establishment of routes. There
+is a narrow interface -- LinkEstimator and CompareBit -- between the
+link estimator and the routing engine. A smaller return value from
+LinkEstimator.getLinkQuality() implies that the link to the neighbor
+is estimated to be of a higher quality than the one that results in a
+larger return value. 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
+returns (ETX-1)*10 as the link quality. The routing engine instructs
+LinkEstimatorP to insert the neighbor, through which a high quality
+path to the root can be constructed, into the neighbor table by
+returning TRUE when LinkEstimatorP signals Comparebit.shouldInsert()
+for the newly discovered neighbor.
+
+LinkEstimatorP does not generate its own control messages to compute
+link qualities. When a user of LinkEstimatorP (CtpRoutingEngineP, for
+example) sends a packet using the Send interface provided by
+LinkEstimatorP, link estimation information is also sent with the
+packet as described in an upcoming TEP [4_]. LinkEstimatorP provides
+calls (txAck(), txNoAck(), and clearDLQ()) to update the link
+estimates based on successful or unsuccessful data transmission to the
+neighbors. LinkEstimatorP uses the LinkPacketMetadata interface to
+determine if the channel was of high quality when a packet is received
+from a neighbor to consider the link to that neighbor for insertion
+into the neighbor table.
The user of LinkEstimatorP can call insertNeighbor() to manually
insert a node in the neighbor table, pinNeighbor() to prevent a
interface LinkEstimator;
interface Init;
interface Packet;
- interface LinkSrcPacket;
+ interface CompareBit;
+ }
+ uses {
+ interface AMSend;
+ interface AMPacket as SubAMPacket;
+ interface Packet as SubPacket;
+ interface Receive as SubReceive;
+ interface LinkPacketMetadata;
+ interface Random;
}
}
+ interface CompareBit {
+ event bool shouldInsert(message_t *msg, void* payload, uint8_t len, bool white_bit);
+ }
+
interface LinkEstimator {
- command uint8_t getLinkQuality(uint16_t neighbor);
- command uint8_t getReverseQuality(uint16_t neighbor);
- command uint8_t getForwardQuality(uint16_t neighbor);
+ command uint16_t getLinkQuality(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);
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.
+data packets, which is the responsibility of CtpForwardingEngineP.
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. CtpRoutingEngineP
-allows a node to be configured as a root or a non-root node
-dynamically. CtpRoutingEngineP maintains multiple candidate next hops::
+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 computes a routing tree with a single
+or multiple roots. CtpRoutingEngineP allows a node to be configured as
+a root or a non-root node dynamically. CtpRoutingEngineP maintains
+multiple candidate next hops::
generic module CtpRoutingEngineP(uint8_t routingTableSize,
uint16_t minInterval,
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 Comparebit;
}
}
QEntryPool
* Packet timing: Random, RetxmitTimer
+4.4 MultihopLqi
+====================================================================
-5. Author's Address
+There is another implementation of collection in ``tos/lib/net/lqi``.
+Its software structure is similar, with the exception that it does
+not have a separate link estimator. MultihopLqi only works on
+platforms that have a CC2420 radio, as it uses a special piece
+of physical layer data the radio provides (the LQI value).
+The three major components of the MultihopLqi implementation
+are the modules LqiForwardingEngineP and LqiRoutingEngineP, as
+well as the configuration MultihopLqiP.
+
+
+5. Author Addresses
====================================================================
| Rodrigo Fonseca
====================================================================
.. [1] TEP 116: Packet Protocols
-.. [2] TEP 124: The Collection Tree Protocol (CTP) - (upcoming)
-
+
+.. [2] TEP 123: The Collection Tree Protocol (CTP)
+
+.. [3] Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, and Philip Levis. "Four Bit Wireless Link Estimation." In Proceedings of the Sixth Workshop on Hot Topics in Networks (HotNets VI), November 2007
+
+.. [4] TEP 124: The Link Estimation Exchange Protocol (LEEP)
projects / tinyos-2.x.git / blobdiff