X-Git-Url: https://oss.titaniummirror.com/gitweb/?a=blobdiff_plain;f=doc%2Ftxt%2Ftep124.txt;h=b57e503668d1beaa8f08bba427c1695645ef9396;hb=e9bfab607e051bae6afb47b44892ce37541d1b44;hp=d4d8c94d23000115fc32c7b8434373326b0a2759;hpb=13dee20f87b2d2fb3ad5e94817b8daadb07d35a9;p=tinyos-2.x.git diff --git a/doc/txt/tep124.txt b/doc/txt/tep124.txt index d4d8c94d..b57e5036 100644 --- a/doc/txt/tep124.txt +++ b/doc/txt/tep124.txt @@ -1,12 +1,12 @@ -============================ -Link Quality Exchange Protocol (LQEP) -============================ +============================================================================ +The Link Estimation Exchange Protocol (LEEP) +============================================================================ -:TEP: 114 +: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 @@ -24,9 +24,9 @@ Link Quality Exchange Protocol (LQEP) Abstract ============================================================================ -The memo documents the Link Quality Exchange Protocol (LQEP). Nodes -use LQEP to exchange information about the quality of links to the -neighbors. +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. 1. Introduction ============================================================================ @@ -34,136 +34,174 @@ 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. These in-bound link -qualities are exchanged among the neighbors using LQEP 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. 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 defined as a value ranging from 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 (LQI,RSSI) provided by the radio on -the node B, or some other methods. - -2.3 Out-bound Link Quality +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 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 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. LQEP is the protocol that is used to exchange the in-bound +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 -------------------------------------------------------------------- -Link Information Entry is a tuple (n,q) where q is the in-bound link -quality from the node n. +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. -2. Link Quality Exchange Protocol (LQEP) +3. The Link Estimation Exchange Protocol (LEEP) ============================================================================ -2.1 Assumptions +3.1 Assumptions -------------------------------------------------------------------- -Following are the assumptions made by LQEP: +Following are the assumptions made by LEEP: -2.1.1. The data link frame has a single-hop source field. -2.1.2. The data link layer provides a broadcast address. -2.1.3. The data link layer provides the length of the LQEP frame. +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. -2.2 The Protocol +3.2 The Protocol -------------------------------------------------------------------- To compute the bi-directional link quality, in-bound link quality must -be exchanged among the neighbors. LQEP maintains a sequence number -that is incremented by one for each outgoing LQEP frame. LQEP frame -transmits this sequence number and Link Information entries describing -the in-bound link qualities for a subset of its neighbors. When a node -receives the LQEP frame and finds its node id in one of the Link -Information entries, the node MUST use the second element of that -tuple as its out-bound link quality to the neighbor identified by the -data link source address. The LQEP sequence number SHOULD be used to -estimate the in-bound link quality. - -2.3 LQEP Frame +be exchanged among the neighbors. LEEP maintains a sequence number +that is incremented by one for each outgoing LEEP frame. The sequence +number in the LEEP frame MUST be incremented by one even if the data +link layer retransmits the LEEP frame. The LEEP sequence number MAY be +used to count the number of missing packets to estimate the in-bound +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. 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 LQEP frame has a header, the payload, and a footer with the Link -Information (LI) entries as shown in this diagram: +A LEEP frame has a header, the payload, and a footer with the Link +Information (LI) entries as shown in this diagram:: ------------------------------------------------------------- - | LQEP | Payload | LI Entry | LI Entry | ... | LI Entry | + | LEEP | Payload | LI Entry | LI Entry | ... | LI Entry | | Header | | 1 | 2 | | n | ------------------------------------------------------------- +The number of Link Information entries can be different in each +outgoing LEEP frame. The number of Link Information entries MUST not +increase the size of the LEEP frame beyond the maximum payload length +allowed by the data link layer. A LEEP frame can have 0 Link +Information entry. -2.3.1 LQEP header +3.3.1 LEEP header +-------------------------------------------------------------------- + +The following diagram shows the LEEP header format:: -The following diagram shows the LQEP 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 - LQEP sequence number. -rsrvd - Reserved + * nentry - Number of Link Information entries in the footer + * seqno - LEEP sequence number. + * rsrvd - Reserved and must be set to 0. -2.3.2 Link Information Entry +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 + * 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 -7. Implementation +4. Implementation ============================================================================ -The following files in ``tinyos-2.x/tos/lib/net/le`` provide a reference -implementation of LQEP described in this TEP. +The following files in ``tinyos-2.x/tos/lib/net/le`` provide a +reference implementation of LEEP described in this TEP. + + * ``LinkEstimator.h`` and ``LinkEstimatorP.nc`` - * ``LinkEstimator.h`` and ``LinkEstimatorP`` +The reference implementation uses the LEEP sequence number to count +the number of missing packets to estimate the in-bound link +quality. The implementation tries to append Link Information entry for +all the neighbors in its neighbor table by sending the largest +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 [1]_ beacons, +sent as a LEEP payload, are sent. -The reference implementation uses the LQEP sequence number to estimate -the in-bound link quality. The implementation tries to append Link -Information entry for all the neighbors in its neighbor table by -sending the largest 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 LQEP frame. +Another reference implementation resides in +``tinyos-2.x/tos/lib/net/4bitle``. This implementation is described in +detail in [2]_. -8. Author's Address +5. Author's Address ============================================================================ | Omprakash Gnawali @@ -175,3 +213,10 @@ not fit in the previous LQEP frame. | email - gnawali@usc.edu | +6. Citations +============================================================================ + +.. [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.