<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>The Link Estimation Exchange Protocol (LEEP)</title>
<meta name="author" content="Omprakash Gnawali" />
<style type="text/css">
</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.2</td>
+<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.4</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2007-02-09</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2007-02-28</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">
-<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 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">
-<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
+<div class="section" id="introduction">
+<h1><a 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. These in-bound link
-qualities are exchanged among the neighbors using LEEP to determine
-the out-bound link qualities. Bi-directional link quality is computed
-using thus learned in-bound and out-bound link qualities.</p>
+messages and the total transmitted messages. LEEP appends in-bound
+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">
-<h1><a id="definitions" name="definitions">2. Definitions</a></h1>
-<div class="section">
-<h2><a id="link-quality" name="link-quality">2.1 Link Quality</a></h2>
-<p>Quality of the link between any two nodes describes the probability
-with which data link layer packets can be received without any
-error. This definition assumes uncorrelated link losses. The link
-between the nodes A and B may have different quality in A to B and B
-to A directions.</p>
+<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>
</div>
-<div class="section">
-<h2><a id="in-bound-link-quality" name="in-bound-link-quality">2.2 In-bound Link Quality</a></h2>
+<div class="section" id="in-bound-link-quality">
+<h2><a name="in-bound-link-quality">2.2 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
link quality indicators such as LQI and RSSI provided by the radio on
the node B, or some other methods.</p>
</div>
-<div class="section">
-<h2><a id="out-bound-link-quality" name="out-bound-link-quality">2.3 Out-bound Link Quality</a></h2>
+<div class="section" id="out-bound-link-quality">
+<h2><a name="out-bound-link-quality">2.3 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">
-<h2><a id="link-information-entry" name="link-information-entry">2.4 Link Information Entry</a></h2>
+<div class="section" id="link-information-entry">
+<h2><a 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">
-<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>
+<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>
<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">
-<h2><a id="the-protocol" name="the-protocol">3.2 The Protocol</a></h2>
+<div class="section" id="the-protocol">
+<h2><a 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
receiver node to find the out-bound link quality to the transmitter
node identified by the data link source address.</p>
</div>
-<div class="section">
-<h2><a id="leep-frame" name="leep-frame">3.3 LEEP Frame</a></h2>
+<div class="section" id="leep-frame">
+<h2><a 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">
-<h2><a id="leep-header" name="leep-header">3.3.1 LEEP header</a></h2>
+<div class="section" id="leep-header">
+<h2><a 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
</ul>
</blockquote>
</div>
-<div class="section">
-<h2><a id="id2" name="id2">3.3.2 Link Information Entry</a></h2>
+<div class="section" id="id2">
+<h2><a 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
</blockquote>
</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>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>
frame. The LEEP frames are transmitted whenever the CTP <a class="footnote-reference" href="#id4" id="id3" name="id3">[1]</a> beacons,
sent as a LEEP payload, are sent.</p>
</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">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">
-<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="id4" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
projects / tinyos-2.x.git / blobdiff