X-Git-Url: https://oss.titaniummirror.com/gitweb/?a=blobdiff_plain;f=doc%2Ftxt%2Ftep124.txt;h=bfd198ceadf808cb18d2daebe0ec3cd765df6759;hb=7fe813a69b7a6e57f6cea06da19c94438193b701;hp=ab5c8c595370548d1b357248212ac56717ee54d3;hpb=fad2a8b33e63036931c7657c061b19b5bf9f0dc7;p=tinyos-2.x.git diff --git a/doc/txt/tep124.txt b/doc/txt/tep124.txt index ab5c8c59..bfd198ce 100644 --- a/doc/txt/tep124.txt +++ b/doc/txt/tep124.txt @@ -34,34 +34,29 @@ 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. 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 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. 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 a +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. +received packets from A among all the packets transmitted by B. -2.3 Out-bound Link Quality +2.2 Out-bound Link Quality -------------------------------------------------------------------- In a node pair (A,B), with B as the node of reference, out-bound link @@ -70,6 +65,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 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 and +acknowledged 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.4 Link Information Entry -------------------------------------------------------------------- @@ -101,7 +107,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 -------------------------------------------------------------------- @@ -126,10 +142,10 @@ Information entry. 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: @@ -145,10 +161,10 @@ Field definitions: 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 | +-+-+-+-+-+-+-+-+ @@ -177,6 +193,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 ============================================================================ @@ -193,3 +213,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.