-============================
+============================================================================
The Link Estimation Exchange Protocol (LEEP)
-============================
+============================================================================
:TEP: 124
:Group: Network Protocol Working Group
:Type: Documentary
-:Status: Draft
-:TinyOS-Version: 2.x
+:Status: Final
+:TinyOS-Version: > 2.1
:Author: Omprakash Gnawali
:Draft-Created: 05-Feb-2006
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.
+messages to 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. Thus, LEEP is
+a discovery and link table bootstrapping mechanism. The link quality
+is often fine-tuned using different mechanisms.
+
+Link quality estimates obtained using LEEP are often used as
+bootstrapping values in the link quality table; data transmission
+statistics can later be used to make these estimates more accurate.
2. Definitions
============================================================================
-2.1 Link Quality
---------------------------------------------------------------------
-
-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.
-
-2.2 In-bound Link Quality
+2.1 In-bound Link Quality
--------------------------------------------------------------------
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.
-
-2.3 Out-bound Link Quality
+of the link from A to B estimated by B as the ratio of successfully
+received to all 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.
+
+2.2 Out-bound Link Quality
--------------------------------------------------------------------
In a node pair (A,B), with B as the node of reference, out-bound link
qualities. LEEP is the protocol that is used to exchange the in-bound
link qualities.
+2.3 Bi-directional Link Quality
+--------------------------------------------------------------------
+
+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. Routing protocols often
+compute the bi-directional link quality of a node pair (A,B) as a
+function (product, min, etc.) of the link quality of (A,B) and (B,A).
+
+
2.4 Link Information Entry
--------------------------------------------------------------------
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.
+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.
+
+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.
+
+
3.3 LEEP Frame
--------------------------------------------------------------------
A LEEP frame has a header, the payload, and a footer with the Link
-Information (LI) entries as shown in this diagram:
+Information (LI) entries as shown in this diagram::
-------------------------------------------------------------
| LEEP | Payload | LI Entry | LI Entry | ... | LI Entry |
Information entry.
3.3.1 LEEP header
+--------------------------------------------------------------------
+
+The following diagram shows the LEEP header format::
-The following diagram shows the LEEP header format:
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 |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Field definitions:
-nentry - Number of Link Information entries in the footer
-seqno - LEEP sequence number.
-rsrvd - Reserved and must be set to 0.
+ * nentry - Number of Link Information entries in the footer
+ * seqno - LEEP sequence number.
+ * rsrvd - Reserved and must be set to 0.
3.3.2 Link Information Entry
+--------------------------------------------------------------------
+
+The following diagram shows the Link Information Entry format::
-The following diagram shows the Link Information Entry format:
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 |
+-+-+-+-+-+-+-+-+
Field definitions:
-node id: the link layer address of the neighbor
-link quality: The in-bound link quality from the node identified by node id
- to the node that transmits this Link Information entry
+ * node id: the link layer address of the neighbor
+ * link quality: The in-bound link quality from the node identified by node id
+ to the node that transmits this Link Information entry
4. Implementation
frame. The LEEP frames are transmitted whenever the CTP [1]_ beacons,
sent as a LEEP payload, are sent.
+Another reference implementation resides in
+``tinyos-2.x/tos/lib/net/4bitle``. This implementation is described in
+detail in [2]_.
+
5. Author's Address
============================================================================
============================================================================
.. [1] TEP 123: The Collection Tree Protocol.
+.. [2] 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.
projects / tinyos-2.x.git / blobdiff