X-Git-Url: https://oss.titaniummirror.com/gitweb/?a=blobdiff_plain;f=tos%2Flib%2Fnet%2F4bitle%2FLinkEstimatorP.nc;h=130d64159f7f085a3518c91f1f603b6c40cd6f59;hb=5a3ac82923305d21abfc0a924a3621fb34d91245;hp=b35e1f4c2e4f789b1ac6eee444e856ab97a56bca;hpb=731234fa193fbcc7207469e30e696f0eb22747eb;p=tinyos-2.x.git diff --git a/tos/lib/net/4bitle/LinkEstimatorP.nc b/tos/lib/net/4bitle/LinkEstimatorP.nc index b35e1f4c..130d6415 100644 --- a/tos/lib/net/4bitle/LinkEstimatorP.nc +++ b/tos/lib/net/4bitle/LinkEstimatorP.nc @@ -59,18 +59,18 @@ implementation { // If the eetx estimate is below this threshold // do not evict a link EVICT_EETX_THRESHOLD = 55, - // maximum link update rounds before we expire the link - MAX_AGE = 6, // if received sequence number if larger than the last sequence // number by this gap, we reinitialize the link MAX_PKT_GAP = 10, BEST_EETX = 0, INVALID_RVAL = 0xff, INVALID_NEIGHBOR_ADDR = 0xff, - INFINITY = 0xff, + // if we don't know the link quality, we need to return a value so + // large that it will not be used to form paths + VERY_LARGE_EETX_VALUE = 0xff, // decay the link estimate using this alpha // we use a denominator of 10, so this corresponds to 0.2 - ALPHA = 2, + ALPHA = 9, // number of packets to wait before computing a new // DLQ (Data-driven Link Quality) DLQ_PKT_WINDOW = 5, @@ -108,8 +108,8 @@ implementation { // the packet. uint8_t addLinkEstHeaderAndFooter(message_t *msg, uint8_t len) { uint8_t newlen; - linkest_header_t *hdr; - linkest_footer_t *footer; + linkest_header_t * ONE hdr; + linkest_footer_t * ONE footer; uint8_t i, j, k; uint8_t maxEntries, newPrevSentIdx; dbg("LI", "newlen1 = %d\n", len); @@ -129,13 +129,22 @@ implementation { j = 0; newPrevSentIdx = 0; for (i = 0; i < NEIGHBOR_TABLE_SIZE && j < maxEntries; i++) { + uint8_t neighborCount; + neighbor_stat_entry_t * COUNT(neighborCount) neighborLists; + if(maxEntries <= NEIGHBOR_TABLE_SIZE) + neighborCount = maxEntries; + else + neighborCount = NEIGHBOR_TABLE_SIZE; + + neighborLists = TCAST(neighbor_stat_entry_t * COUNT(neighborCount), footer->neighborList); k = (prevSentIdx + i + 1) % NEIGHBOR_TABLE_SIZE; - if (NeighborTable[k].flags & VALID_ENTRY) { - footer->neighborList[j].ll_addr = NeighborTable[k].ll_addr; - footer->neighborList[j].inquality = NeighborTable[k].inquality; + if ((NeighborTable[k].flags & VALID_ENTRY) && + (NeighborTable[k].flags & MATURE_ENTRY)) { + neighborLists[j].ll_addr = NeighborTable[k].ll_addr; + neighborLists[j].inquality = NeighborTable[k].inquality; newPrevSentIdx = k; - dbg("LI", "Loaded on footer: %d %d %d\n", j, footer->neighborList[j].ll_addr, - footer->neighborList[j].inquality); + dbg("LI", "Loaded on footer: %d %d %d\n", j, neighborLists[j].ll_addr, + neighborLists[j].inquality); j++; } } @@ -159,7 +168,6 @@ implementation { ne->rcvcnt = 0; ne->failcnt = 0; ne->flags = (INIT_ENTRY | VALID_ENTRY); - ne->inage = MAX_AGE; ne->inquality = 0; ne->eetx = 0; } @@ -265,7 +273,7 @@ implementation { // called when new beacon estimate is done // also called when new DEETX estimate is done void updateEETX(neighbor_table_entry_t *ne, uint16_t newEst) { - ne->eetx = (ALPHA * ne->eetx + (10 - ALPHA) * newEst)/10; + ne->eetx = (ALPHA * ne->eetx + (10 - ALPHA) * newEst + 5)/10; } @@ -295,11 +303,11 @@ implementation { if (q1 > 0) { q = 2550 / q1 - 10; if (q > 255) { - q = INFINITY; + q = VERY_LARGE_EETX_VALUE; } return (uint8_t)q; } else { - return INFINITY; + return VERY_LARGE_EETX_VALUE; } } @@ -317,33 +325,24 @@ implementation { ne = &NeighborTable[i]; if (ne->ll_addr == n) { if (ne->flags & VALID_ENTRY) { - if (ne->inage > 0) - ne->inage--; - - if (ne->inage == 0) { - ne->flags ^= VALID_ENTRY; - ne->inquality = 0; + dbg("LI", "Making link: %d mature\n", i); + ne->flags |= MATURE_ENTRY; + totalPkt = ne->rcvcnt + ne->failcnt; + dbg("LI", "MinPkt: %d, totalPkt: %d\n", minPkt, totalPkt); + if (totalPkt < minPkt) { + totalPkt = minPkt; + } + if (totalPkt == 0) { + ne->inquality = (ALPHA * ne->inquality) / 10; } else { - dbg("LI", "Making link: %d mature\n", i); - ne->flags |= MATURE_ENTRY; - totalPkt = ne->rcvcnt + ne->failcnt; - dbg("LI", "MinPkt: %d, totalPkt: %d\n", minPkt, totalPkt); - if (totalPkt < minPkt) { - totalPkt = minPkt; - } - if (totalPkt == 0) { - ne->inquality = (ALPHA * ne->inquality) / 10; - } else { - newEst = (255 * ne->rcvcnt) / totalPkt; - dbg("LI,LITest", " %hu: %hhu -> %hhu", ne->ll_addr, ne->inquality, (ALPHA * ne->inquality + (10-ALPHA) * newEst)/10); - ne->inquality = (ALPHA * ne->inquality + (10-ALPHA) * newEst)/10; - } - ne->rcvcnt = 0; - ne->failcnt = 0; + newEst = (255 * ne->rcvcnt) / totalPkt; + dbg("LI,LITest", " %hu: %hhu -> %hhu", ne->ll_addr, ne->inquality, (ALPHA * ne->inquality + (10-ALPHA) * newEst + 5)/10); + ne->inquality = (ALPHA * ne->inquality + (10-ALPHA) * newEst + 5)/10; } + ne->rcvcnt = 0; + ne->failcnt = 0; updateEETX(ne, computeEETX(ne->inquality)); - } - else { + } else { dbg("LI", " - entry %i is invalid.\n", (int)i); } } @@ -368,7 +367,6 @@ implementation { NeighborTable[idx].lastseq, seq, packetGap); NeighborTable[idx].lastseq = seq; NeighborTable[idx].rcvcnt++; - NeighborTable[idx].inage = MAX_AGE; if (packetGap > 0) { NeighborTable[idx].failcnt += packetGap - 1; } @@ -378,7 +376,11 @@ implementation { NeighborTable[idx].inquality = 0; } - if (NeighborTable[idx].rcvcnt >= BLQ_PKT_WINDOW) { + // The or with packetGap >= BLQ_PKT_WINDOW is needed in case + // failcnt gets reset above + + if (((NeighborTable[idx].rcvcnt + NeighborTable[idx].failcnt) >= BLQ_PKT_WINDOW) + || (packetGap >= BLQ_PKT_WINDOW)) { updateNeighborTableEst(NeighborTable[idx].ll_addr); } @@ -393,8 +395,8 @@ implementation { for (i = 0; i < NEIGHBOR_TABLE_SIZE; i++) { ne = &NeighborTable[i]; if (ne->flags & VALID_ENTRY) { - dbg("LI,LITest", "%d:%d inQ=%d, inA=%d, rcv=%d, fail=%d, Q=%d\n", - i, ne->ll_addr, ne->inquality, ne->inage, + dbg("LI,LITest", "%d:%d inQ=%d, rcv=%d, fail=%d, Q=%d\n", + i, ne->ll_addr, ne->inquality, ne->rcvcnt, ne->failcnt, computeEETX(ne->inquality)); } } @@ -441,10 +443,14 @@ implementation { uint8_t idx; idx = findIdx(neighbor); if (idx == INVALID_RVAL) { - return INFINITY; + return VERY_LARGE_EETX_VALUE; } else { - return NeighborTable[idx].eetx; - }; + if (NeighborTable[idx].flags & MATURE_ENTRY) { + return NeighborTable[idx].eetx; + } else { + return VERY_LARGE_EETX_VALUE; + } + } } // insert the neighbor at any cost (if there is a room for it) @@ -559,7 +565,7 @@ implementation { // done sending the message that originated by // the user of this component event void AMSend.sendDone(message_t* msg, error_t error ) { - return signal Send.sendDone(msg, error); + signal Send.sendDone(msg, error); } // cascade the calls down @@ -578,7 +584,7 @@ implementation { // called when link estimator generator packet or // packets from upper layer that are wired to pass through // link estimator is received - void processReceivedMessage(message_t* msg, void* payload, uint8_t len) { + void processReceivedMessage(message_t* ONE msg, void* COUNT_NOK(len) payload, uint8_t len) { uint8_t nidx; uint8_t num_entries; @@ -629,14 +635,20 @@ implementation { initNeighborIdx(nidx, ll_addr); } else { dbg("LI", "No room in the table\n"); - if (signal CompareBit.shouldInsert(msg, - call Packet.getPayload(msg, call Packet.payloadLength(msg)), - call Packet.payloadLength(msg), - call LinkPacketMetadata.highChannelQuality(msg))) { - nidx = findRandomNeighborIdx(); - if (nidx != INVALID_RVAL) { - signal LinkEstimator.evicted(NeighborTable[nidx].ll_addr); - initNeighborIdx(nidx, ll_addr); + + /* if the white bit is set, lets ask the router if the path through + this link is better than at least one known path - if so + lets insert this link into the table. + */ + if (call LinkPacketMetadata.highChannelQuality(msg)) { + if (signal CompareBit.shouldInsert(msg, + call Packet.getPayload(msg, call Packet.payloadLength(msg)), + call Packet.payloadLength(msg))) { + nidx = findRandomNeighborIdx(); + if (nidx != INVALID_RVAL) { + signal LinkEstimator.evicted(NeighborTable[nidx].ll_addr); + initNeighborIdx(nidx, ll_addr); + } } } }