<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
-<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
+<meta name="generator" content="Docutils 0.3.6: http://docutils.sourceforge.net/" />
<title>Collection</title>
<meta name="author" content="Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, and Philip Levis" />
<style type="text/css">
</style>
</head>
<body>
-<div class="document" id="collection">
<h1 class="title">Collection</h1>
<table class="docinfo" frame="void" rules="none">
<col class="docinfo-name" />
</tr>
</tbody>
</table>
+<div class="document" id="collection">
<div class="note">
<p class="first admonition-title">Note</p>
<p class="last">This memo documents a part of TinyOS for the TinyOS Community, and
of this memo is unlimited. This memo is in full compliance with
TEP 1.</p>
</div>
-<div class="section">
-<h1><a id="abstract" name="abstract">Abstract</a></h1>
+<div class="section" id="abstract">
+<h1><a name="abstract">Abstract</a></h1>
<p>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.</p>
</div>
-<div class="section">
-<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
+<div class="section" id="introduction">
+<h1><a name="introduction">1. Introduction</a></h1>
<p>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 <em>trees</em>, 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.</p>
<p>When a network has multiple base stations that act as <em>root</em> nodes,
-rather than one tree, it has a <em>forest</em> of trees. By picking a
+rather than one tree, it has a <em>forest</em> 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:
<ul class="simple">
<li>Loop detection, detecting when a node selects one of its
descendants as a new parent.</li>
-<li>Duplicate suppression, detecting and dealing with when lost
-acknowledgments are causing packets to replicate in the
+<li>Duplicate suppression, detecting and dealing with when lost
+acknowledgments are causing packets to replicate in the
network, wasting bandwidth.</li>
<li>Link estimation, evaluating the link quality to single-hop
neighbors.</li>
<p>The rest of this document describes a set of components and interfaces
for a collection service outlined above.</p>
</div>
-<div class="section">
-<h1><a id="collection-interfaces" name="collection-interfaces">2. Collection interfaces</a></h1>
+<div class="section" id="collection-interfaces">
+<h1><a name="collection-interfaces">2. Collection interfaces</a></h1>
<p>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
}
</pre>
</div>
-<div class="section">
-<h1><a id="collection-services" name="collection-services">3 Collection Services</a></h1>
+<div class="section" id="collection-services">
+<h1><a name="collection-services">3 Collection Services</a></h1>
<p>A collection service MUST provide one component, TreeCollectionC,
which has the following signature:</p>
<pre class="literal-block">
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.</p>
-<div class="section">
-<h2><a id="collectionsenderc" name="collectionsenderc">3.1 CollectionSenderC</a></h2>
+<div class="section" id="collectionsenderc">
+<h2><a name="collectionsenderc">3.1 CollectionSenderC</a></h2>
<p>Collection has a virtualized sending abstraction, the generic
component CollectionSenderC:</p>
-<div class="system-message">
-<p class="system-message-title">System Message: WARNING/2 (<tt class="docutils">txt/tep119.txt</tt>, line 198)</p>
-Literal block expected; none found.</div>
-<dl class="docutils">
-<dt>generic configuration CollectionSenderC(collection_id_t collectid) {</dt>
-<dd><dl class="first docutils">
-<dt>provides {</dt>
-<dd>interface Send;
-interface Packet;</dd>
-</dl>
-<div class="system-message">
-<p class="system-message-title">System Message: WARNING/2 (<tt class="docutils">txt/tep119.txt</tt>, line 202)</p>
-Definition list ends without a blank line; unexpected unindent.</div>
-<p class="last">}</p>
-</dd>
-</dl>
-<div class="system-message">
-<p class="system-message-title">System Message: WARNING/2 (<tt class="docutils">txt/tep119.txt</tt>, line 203)</p>
-Definition list ends without a blank line; unexpected unindent.</div>
-<p>}</p>
+<pre class="literal-block">
+generic configuration CollectionSenderC(collection_id_t collectid) {
+ provides {
+ interface Send;
+ interface Packet;
+ }
+}
+</pre>
<p>This abstraction follows a similar virtualization approach to
AMSenderC [<a class="reference" href="#id1">1</a>], 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
based on its collection ID and contents.</p>
</div>
</div>
-<div class="section">
-<h1><a id="implementation" name="implementation">4 Implementation</a></h1>
+<div class="section" id="implementation">
+<h1><a name="implementation">4 Implementation</a></h1>
<p>An implementation of this TEP can be found in
<tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/net/collection</span></tt>. The implementation consists of
three major components, which are wired together to form a
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.</p>
-<div class="section">
-<h2><a id="linkestimatorp" name="linkestimatorp">4.1 LinkEstimatorP</a></h2>
+<div class="section" id="linkestimatorp">
+<h2><a name="linkestimatorp">4.1 LinkEstimatorP</a></h2>
<p>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 larger 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:</p>
+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:</p>
<pre class="literal-block">
-typedef uint16_t neighbor_t
+typedef uint16_t neighbor_table_entry_t
LinkEstimatorP {
provides {
+ interface StdControl;
+ interface AMSend as Send;
+ interface Receive;
interface LinkEstimator;
- interface NeighborTable;
+ interface Init;
+ interface Packet;
+ interface LinkSrcPacket;
}
}
interface LinkEstimator {
- command uint8_t getLinkQuality(neighbot_t neighbor);
- command uint8_t getReverseQuality(neighbot_t neighbor);
- command uint8_t getForwardQuality(neighbot_t neighbor);
+ 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 NeighborTable {
- event void evicted(neighbot_t neighbor)
+interface NeighborTableEviction {
+ event void evicted(uint16_t neighbor)
}
</pre>
</div>
-<div class="section">
-<h2><a id="treeroutingenginep" name="treeroutingenginep">4.2 TreeRoutingEngineP</a></h2>
+<div class="section" id="treeroutingenginep">
+<h2><a name="treeroutingenginep">4.2 TreeRoutingEngineP</a></h2>
<p>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
+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:</p>
<pre class="literal-block">
interface TreeRoutingInspect;
interface StdControl;
interface Init;
- }
+ }
uses {
interface AMSend as BeaconSend;
interface Receive as BeaconReceive;
}
</pre>
</div>
-<div class="section">
-<h2><a id="forwardingenginep" name="forwardingenginep">4.3 ForwardingEngineP</a></h2>
+<div class="section" id="forwardingenginep">
+<h2><a name="forwardingenginep">4.3 ForwardingEngineP</a></h2>
<p>The ForwardingEngineP component provides all the top level interfaces
-(except RootControl) which TreeCollectionC provides and an application
+(except RootControl) which TreeCollectionC provides and an application
uses:</p>
<pre class="literal-block">
generic module ForwardingEngineP() {
<ul class="simple">
<li>Single hop communication: SubSend, SubReceive, SubSnoop,
SubPacket, PacketAcknowledgments, AMPacket</li>
-<li>Routing: UnicastNameFreeRouting, TreeRoutingInspect,
+<li>Routing: UnicastNameFreeRouting, TreeRoutingInspect,
RootControl, CollectionId, SentCache</li>
<li>Queue and buffer management: SendQueue, MessagePool,
QEntryPool</li>
</blockquote>
</div>
</div>
-<div class="section">
-<h1><a id="author-s-address" name="author-s-address">5. Author's Address</a></h1>
+<div class="section" id="author-s-address">
+<h1><a name="author-s-address">5. Author's Address</a></h1>
<div class="line-block">
-<div class="line">Rodrigo Fonseca</div>
+<div class="line">Rodrigo Fonseca </div>
<div class="line">473 Soda Hall</div>
<div class="line">Berkeley, CA 94720-1776</div>
<div class="line"><br /></div>
<div class="line"><br /></div>
<div class="line"><br /></div>
<div class="line">Omprakash Gnawali</div>
-<div class="line">Ronald Tutor Hall (RTH) 418</div>
+<div class="line">Ronald Tutor Hall (RTH) 418 </div>
<div class="line">3710 S. McClintock Avenue</div>
-<div class="line">Los Angeles, CA 90089</div>
+<div class="line">Los Angeles, CA 90089 </div>
<div class="line"><br /></div>
<div class="line">phone - +1 213 821-5627</div>
<div class="line">email - <a class="reference" href="mailto:gnawali@usc.edu">gnawali@usc.edu</a></div>
<div class="line">Kyle Jamieson</div>
<div class="line">The Stata Center</div>
<div class="line">32 Vassar St.</div>
-<div class="line">Cambridge, MA 02139</div>
+<div class="line">Cambridge, MA 02139 </div>
<div class="line"><br /></div>
<div class="line">email - <a class="reference" href="mailto:jamieson@csail.mit.edu">jamieson@csail.mit.edu</a></div>
<div class="line"><br /></div>
<div class="line">email - <a class="reference" href="mailto:pal@cs.stanford.edu">pal@cs.stanford.edu</a></div>
</div>
</div>
-<div class="section">
-<h1><a id="citations" name="citations">6. Citations</a></h1>
+<div class="section" id="citations">
+<h1><a name="citations">6. Citations</a></h1>
<table class="docutils footnote" frame="void" id="id1" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
projects / tinyos-2.x.git / commitdiff