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.
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.
-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 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.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 @@ -359,6 +356,18 @@ qualities. LEEP is the protocol that is used to exchange the in-bound link qualities.
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. One popular way to define the +bi-directional link quality between a node pair (A,B) as the +probability that a packet transmitted by A will be successfully +received and acknowledged by B. This approach computes the +bi-directional link quality of a node pair (A,B) as the product of the +link quality of (A,B) and (B,A).
+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.
@@ -385,7 +394,14 @@ 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.
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:
@@ -427,10 +443,10 @@ Information entry.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 | +-+-+-+-+-+-+-+-+@@ -460,8 +476,11 @@ 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, +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].
| [1] | TEP 123: The Collection Tree Protocol. |
| [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. |