<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.3.6: http://docutils.sourceforge.net/" />
+<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<title>The Link Estimation Exchange Protocol (LEEP)</title>
<meta name="author" content="Omprakash Gnawali" />
<style type="text/css">
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 }
</style>
</head>
<body>
+<div class="document" id="the-link-estimation-exchange-protocol-leep">
<h1 class="title">The Link Estimation Exchange Protocol (LEEP)</h1>
<table class="docinfo" frame="void" rules="none">
<col class="docinfo-name" />
<td>Omprakash Gnawali</td></tr>
<tr class="field"><th class="docinfo-name">Draft-Created:</th><td class="field-body">05-Feb-2006</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.4</td>
+<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.9</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2007-02-28</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2009-01-31</td>
</tr>
<tr class="field"><th class="docinfo-name">Draft-Discuss:</th><td class="field-body">TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu></td>
</tr>
</tbody>
</table>
-<div class="document" id="the-link-estimation-exchange-protocol-leep">
<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" id="abstract">
-<h1><a name="abstract">Abstract</a></h1>
+<div class="section">
+<h1><a id="abstract" name="abstract">Abstract</a></h1>
<p>The memo documents the Link Estimation Exchange Protocol (LEEP). Nodes
use LEEP to estimate and exchange information about the quality of
links to the neighbors.</p>
</div>
-<div class="section" id="introduction">
-<h1><a name="introduction">1. Introduction</a></h1>
+<div class="section">
+<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
<p>Routing protocols often require bi-directional link qualities to
compute the routes. Nodes can estimate the quality of the in-bound
link from a neighbor by estimating the ratio of successfully received
messages and the total transmitted messages. LEEP appends in-bound
-packet reception rate (PRR) estimates to packets. Other nodes hearing
+packet reception rate (PRR) estimates to packets. Other nodes hearing
these packets can combine the in-bound PRR values with their own
-in-bound values to compute bi-directional link quality.</p>
-</div>
-<div class="section" id="definitions">
-<h1><a name="definitions">2. Definitions</a></h1>
-<div class="section" id="link-quality">
-<h2><a name="link-quality">2.1 Link Quality</a></h2>
-<p>The link quality between a directed node pair (A,B) is the probability
-that a packet transmitted by A will be successfully received by B. The
-bidirectional link quality of an undirected node pair (A,B) is the
-product of the link quality of (A,B) and (B,A). This definition
-assumes independent link losses. It also includes the case when
-the link quality of (A,B) and (B,A) are different; this can occur
-due to local interference or noise.</p>
+in-bound values to compute bi-directional link quality. Thus, LEEP is
+a discovery and link table bootstrapping mechanism. The link quality
+is often fine-tuned using different mechanisms.</p>
+<p>Link quality estimates obtained using LEEP are often used as a
+bootstrapping values in the link quality table; data transmission
+statistics can later be used to make these estimates more accurate.</p>
</div>
-<div class="section" id="in-bound-link-quality">
-<h2><a name="in-bound-link-quality">2.2 In-bound Link Quality</a></h2>
+<div class="section">
+<h1><a id="definitions" name="definitions">2. Definitions</a></h1>
+<div class="section">
+<h2><a id="in-bound-link-quality" name="in-bound-link-quality">2.1 In-bound Link Quality</a></h2>
<p>In a node pair (A,B), with B as the node of reference, in-bound link
quality is a value in the range of 0 to 255 that describes the quality
of the link from A to B estimated by B by counting the successfully
-received packets from A among all the transmitted packets or using
-link quality indicators such as LQI and RSSI provided by the radio on
-the node B, or some other methods.</p>
+received packets from A among all the packets transmitted by A. Thus,
+in-bound link quality is the empirical probability that a packet will
+be successfully received on a given link. A value of 255 represents a
+probability of 1 and a value of 0 represents a probability of 0 of
+successfully receiving a packet on a given link.</p>
</div>
-<div class="section" id="out-bound-link-quality">
-<h2><a name="out-bound-link-quality">2.3 Out-bound Link Quality</a></h2>
+<div class="section">
+<h2><a id="out-bound-link-quality" name="out-bound-link-quality">2.2 Out-bound Link Quality</a></h2>
<p>In a node pair (A,B), with B as the node of reference, out-bound link
quality is defined as the quality of the link from B to A. B can
determine the out-bound link quality if A advertises its in-bound link
qualities. LEEP is the protocol that is used to exchange the in-bound
link qualities.</p>
</div>
-<div class="section" id="link-information-entry">
-<h2><a name="link-information-entry">2.4 Link Information Entry</a></h2>
+<div class="section">
+<h2><a id="bi-directional-link-quality" name="bi-directional-link-quality">2.3 Bi-directional Link Quality</a></h2>
+<p>LEEP does not define or compute bi-directional link quality. LEEP
+provides a way to exchange sufficient information to compute in-bound
+and out-bound link qualities. These two link qualities can be used to
+compute the bi-directional link quality. One popular way to define the
+bi-directional link quality between a node pair (A,B) as the
+probability that a packet transmitted by A will be successfully
+received and acknowledged by B. This approach computes the
+bi-directional link quality of a node pair (A,B) as the product of the
+link quality of (A,B) and (B,A).</p>
+</div>
+<div class="section">
+<h2><a id="link-information-entry" name="link-information-entry">2.4 Link Information Entry</a></h2>
<p>Link Information Entry created by node k is a tuple (n,q) where q is
the in-bound link quality from node n to k.</p>
</div>
</div>
-<div class="section" id="id1">
-<h1><a name="id1">3. The Link Estimation Exchange Protocol (LEEP)</a></h1>
-<div class="section" id="assumptions">
-<h2><a name="assumptions">3.1 Assumptions</a></h2>
+<div class="section">
+<h1><a id="id1" name="id1">3. The Link Estimation Exchange Protocol (LEEP)</a></h1>
+<div class="section">
+<h2><a id="assumptions" name="assumptions">3.1 Assumptions</a></h2>
<p>Following are the assumptions made by LEEP:</p>
<p>3.1.1. The data link frame has a single-hop source field.
3.1.2. The data link layer provides a broadcast address.
3.1.3. The data link layer provides the length of the LEEP frame.</p>
</div>
-<div class="section" id="the-protocol">
-<h2><a name="the-protocol">3.2 The Protocol</a></h2>
+<div class="section">
+<h2><a id="the-protocol" name="the-protocol">3.2 The Protocol</a></h2>
<p>To compute the bi-directional link quality, in-bound link quality must
be exchanged among the neighbors. LEEP maintains a sequence number
that is incremented by one for each outgoing LEEP frame. The sequence
entries describing the in-bound link qualities for a subset of its
neighbors. The Link Information entry on the LEEP frame allows the
receiver node to find the out-bound link quality to the transmitter
-node identified by the data link source address.</p>
+node identified by the data link source address. Thus, LEEP is also a
+way for nodes to discover new nodes and links in the network.</p>
+<p>Link quality estimation is inherently imperfect - data transmission
+and link quality estimation might be done at different timescales. The
+PRR for LEEP frames (broadcast) and data frames (unicast) might be
+different. So LEEP is better used as a link quality bootstrapping
+mechanism. The link quality estimate can be made more accurate later
+using data transmission statistics.</p>
</div>
-<div class="section" id="leep-frame">
-<h2><a name="leep-frame">3.3 LEEP Frame</a></h2>
+<div class="section">
+<h2><a id="leep-frame" name="leep-frame">3.3 LEEP Frame</a></h2>
<p>A LEEP frame has a header, the payload, and a footer with the Link
Information (LI) entries as shown in this diagram:</p>
<pre class="literal-block">
allowed by the data link layer. A LEEP frame can have 0 Link
Information entry.</p>
</div>
-<div class="section" id="leep-header">
-<h2><a name="leep-header">3.3.1 LEEP header</a></h2>
+<div class="section">
+<h2><a id="leep-header" name="leep-header">3.3.1 LEEP header</a></h2>
<p>The following diagram shows the LEEP header format:</p>
<pre class="literal-block">
1
- 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-|nentry | rsrvd | seqno |
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+|nentry | rsrvd | seqno |
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
</pre>
<p>Field definitions:</p>
<blockquote>
</ul>
</blockquote>
</div>
-<div class="section" id="id2">
-<h2><a name="id2">3.3.2 Link Information Entry</a></h2>
+<div class="section">
+<h2><a id="id2" name="id2">3.3.2 Link Information Entry</a></h2>
<p>The following diagram shows the Link Information Entry format:</p>
<pre class="literal-block">
1
- 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-| node id |
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+| node id |
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| link quality |
+-+-+-+-+-+-+-+-+
</pre>
</blockquote>
</div>
</div>
-<div class="section" id="implementation">
-<h1><a name="implementation">4. Implementation</a></h1>
+<div class="section">
+<h1><a id="implementation" name="implementation">4. Implementation</a></h1>
<p>The following files in <tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/net/le</span></tt> provide a
reference implementation of LEEP described in this TEP.</p>
<blockquote>
possible data link frame. If there is still not enough room to fit all
the Link Information entries, it uses a round-robin policy to select
the entries to be exchanged that could not fit in the previous LEEP
-frame. The LEEP frames are transmitted whenever the CTP <a class="footnote-reference" href="#id4" id="id3" name="id3">[1]</a> beacons,
+frame. The LEEP frames are transmitted whenever the CTP <a class="footnote-reference" href="#id5" id="id3" name="id3">[1]</a> beacons,
sent as a LEEP payload, are sent.</p>
+<p>Another reference implementation resides in
+<tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/net/4bitle</span></tt>. This implementation is described in
+detail in <a class="footnote-reference" href="#id6" id="id4" name="id4">[2]</a>.</p>
</div>
-<div class="section" id="author-s-address">
-<h1><a name="author-s-address">5. Author's Address</a></h1>
+<div class="section">
+<h1><a id="author-s-address" name="author-s-address">5. Author's Address</a></h1>
<div class="line-block">
<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"><br /></div>
</div>
</div>
-<div class="section" id="citations">
-<h1><a name="citations">6. Citations</a></h1>
-<table class="docutils footnote" frame="void" id="id4" rules="none">
+<div class="section">
+<h1><a id="citations" name="citations">6. Citations</a></h1>
+<table class="docutils footnote" frame="void" id="id5" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a class="fn-backref" href="#id3" name="id5">[1]</a></td><td>TEP 123: The Collection Tree Protocol.</td></tr>
+</tbody>
+</table>
+<table class="docutils footnote" frame="void" id="id6" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
-<tr><td class="label"><a class="fn-backref" href="#id3" name="id4">[1]</a></td><td>TEP 123: The Collection Tree Protocol.</td></tr>
+<tr><td class="label"><a class="fn-backref" href="#id4" name="id6">[2]</a></td><td>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.</td></tr>
</tbody>
</table>
</div>
projects / tinyos-2.x.git / blobdiff