<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" />
</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. 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">
-<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>
+<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
+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