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

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 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. 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 collection protocols. Instead, they represent a subset of common networking algorithmic edge cases that occur in this protocol 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 network, wasting bandwidth.
• Link estimation, evaluating the link quality to single-hop neighbors.
• Self-interference, preventing forwarding packets along the route from introducing interference for subsequent packets.

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, snooper, in-network processor, and consumer. 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. 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.

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

A collection service MUST provide one component, CollectionC, which has the following signature:

configuration CollectionC {
  provides {
    interface StdControl;
    interface Send[uint8_t client];
    interface Receive[collection_id_t id];
    interface Receive as Snoop[collection_id_t];
    interface Intercept[collection_id_t id];
    interface RootControl;
    interface Packet;
    interface CollectionPacket;
  }
  uses {
    interface CollectionId[uint8_t client];
  }
}

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 a virtualized sending interface.

Receive, Snoop, and Intercept are all parameterized by 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.

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

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. CollectionC SHOULD NOT configure a node as a root by default.

Packet and CollectionPacket allow components to access collection data packet fields [1].

generic configuration CollectionSenderC(collection_id_t collectid) {
  provides {
    interface Send;
    interface Packet;
  }
}

4 Implementation

An implementation of this TEP can be found 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, CtpRoutingEngineP, 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.

typedef uint16_t neighbor_table_entry_t

LinkEstimatorP {
  provides {
    interface StdControl;
    interface AMSend as Send;
    interface Receive;
    interface LinkEstimator;
    interface Init;
    interface Packet;
    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 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);
  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);
}

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 SplitControl as RadioControl;
        interface Timer<TMilli> as BeaconTimer;
        interface Timer<TMilli> as RouteTimer;
        interface Random;
        interface CollectionDebug;
        interface CtpCongestion;
        interface Comparebit;
    }
}

interface UnicastNameFreeRouting {
  command am_addr_t nextHop();

  command bool hasRoute();
  event void routeFound();
  event void noRoute();
}

generic module CtpForwardingEngineP() {
  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;
    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 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 LinkEstimator;
    interface Timer<TMilli> as CongestionTimer;
    interface Cache<message_t*> as SentCache;
    interface CtpInfo;
    interface PacketAcknowledgements;
    interface Random;
    interface RootControl;
    interface CollectionId[uint8_t client];
    interface AMPacket;
    interface CollectionDebug;
  }
}

4.4 MultihopLqi

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

6. Citations