X-Git-Url: https://oss.titaniummirror.com/gitweb/?p=tinyos-2.x.git;a=blobdiff_plain;f=doc%2Ftxt%2Ftep124.txt;h=b57e503668d1beaa8f08bba427c1695645ef9396;hp=3a16cfe9128ce91d86f7327015a9af3ee91ba97e;hb=e9bfab607e051bae6afb47b44892ce37541d1b44;hpb=adf1de6c009d13b7b52e68535c63b28f59c97400 diff --git a/doc/txt/tep124.txt b/doc/txt/tep124.txt index 3a16cfe9..b57e5036 100644 --- a/doc/txt/tep124.txt +++ b/doc/txt/tep124.txt @@ -5,8 +5,8 @@ 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 @@ -34,36 +34,33 @@ links to the neighbors. 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 +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. +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 --------------------------------------------------------------------- - -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. - -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 @@ -72,6 +69,17 @@ 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. +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 -------------------------------------------------------------------- @@ -103,7 +111,17 @@ link quality from the transmitter. LEEP MUST transmit Link Information 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 -------------------------------------------------------------------- @@ -179,6 +197,10 @@ the entries to be exchanged that could not fit in the previous LEEP 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 ============================================================================ @@ -195,3 +217,6 @@ sent as a LEEP payload, are sent. ============================================================================ .. [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.