multihopewma.nc

MultiHopEngineM多跳路由邻居表3

// $Id: MultiHopEWMA.nc,v 1.1 2003/11/21 19:47:24 jlhill Exp $

/*									tab:4
 * "Copyright (c) 2000-2003 The Regents of the University  of California.  
 * All rights reserved.
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose, without fee, and without written agreement is
 * hereby granted, provided that the above copyright notice, the following
 * two paragraphs and the author appear in all copies of this software.
 * 
 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
 *
 * Copyright (c) 2002-2003 Intel Corporation
 * All rights reserved.
 *
 * This file is distributed under the terms in the attached INTEL-LICENSE     
 * file. If you do not find these files, copies can be found by writing to
 * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, 
 * 94704.  Attention:  Intel License Inquiry.
 */


includes AM;
includes MultiHop;


#define MULTI_HOP_DEBUG 1

module MultiHopEWMA {

  provides {
    interface StdControl;
    interface RouteSelect;
    interface RouteControl;
  }

  uses {
    interface Timer;
    interface ReceiveMsg;
    interface Intercept as Snoop[uint8_t id];
    interface SendMsg;
    interface Send as DebugSendMsg;
  }
}

implementation {

  enum {
    NBRFLAG_VALID    = 0x01,
    NBRFLAG_NEW      = 0x02,
    NBRFLAG_EST_INIT = 0x04
  };

  enum {
    BASE_STATION_ADDRESS        = 0,
    ROUTE_TABLE_SIZE            = 16,
    ESTIMATE_TO_ROUTE_RATIO     = 5,
    ACCEPTABLE_MISSED           = -20,
    DATA_TO_ROUTE_RATIO         = 2,
    DATA_FREQ                   = 10000,
    SWITCH_THRESHOLD     	= 192,
    MAX_ALLOWABLE_LINK_COST     = 256*6,
    LIVELINESS              	= 2,
    MAX_DESCENDANT		= 5

  };

  enum {
    ROUTE_INVALID    = 0xff
  };

  struct SortEntry {
    uint16_t id;
    uint8_t  receiveEst;
  };

  struct SortDbgEntry {
    uint16_t id;
    uint8_t  sendEst;
    uint8_t  hopcount; 
  };

  typedef struct RPEstEntry {
    uint16_t id;
    uint8_t receiveEst;
  } __attribute__ ((packed)) RPEstEntry;

  typedef struct RoutePacket {
    uint16_t parent;
    uint16_t cost;
    uint8_t estEntries;
    RPEstEntry estList[1];
  } __attribute__ ((packed)) RoutePacket;

  typedef struct TableEntry {
    uint16_t id;  // Node Address
    uint16_t parent;
    uint16_t cost;
    uint8_t childLiveliness;
    uint16_t missed;
    uint16_t received;
    int16_t lastSeqno;
    uint8_t flags;
    uint8_t liveliness;
    uint8_t hop;
    uint8_t receiveEst;
    uint8_t sendEst;
  } TableEntry;

  TOS_Msg debugMsg; 
  TOS_Msg routeMsg; 
  bool gfSendRouteBusy;

  TableEntry BaseStation;
  TableEntry NeighborTbl[ROUTE_TABLE_SIZE];
  TableEntry *gpCurrentParent;
  uint8_t gbCurrentHopCount;
  uint16_t gbCurrentCost;
  int16_t gCurrentSeqNo;
  uint16_t gwEstTicks;
  uint32_t gUpdateInterval;


  /*////////////////////////////////////////////////////////*/
  /**
   * Return index into neighbor table of the given node addr
   * @author terence
   * @param id
   * @return index, if not found return ROUTE_INVALID
   */

  uint8_t findEntry(uint8_t id) {
    uint8_t i = 0;
    for (i = 0; i < ROUTE_TABLE_SIZE; i++) {
      if ((NeighborTbl[i].flags & NBRFLAG_VALID) && NeighborTbl[i].id == id) {
        return i;
      }
    }
    return ROUTE_INVALID;
  }
  /*////////////////////////////////////////////////////////*/
  /**
   * This function determines which entry should be replace
   * in this case, we find the one with the lease send estimate
   * @author terence
   * @param void
   * @return index of the table
   */

  uint8_t findEntryToBeReplaced() {
    uint8_t i = 0;
    uint8_t minSendEst = -1;
    uint8_t minSendEstIndex = ROUTE_INVALID;
    for (i = 0; i < ROUTE_TABLE_SIZE; i++) {
      if ((NeighborTbl[i].flags & NBRFLAG_VALID) == 0) {
        return i;
      }
      if (minSendEst >= NeighborTbl[i].sendEst) {
        minSendEst = NeighborTbl[i].sendEst;
        minSendEstIndex = i;
      }
    }
    return minSendEstIndex;
  }
  /*////////////////////////////////////////////////////////*/
  /**
   * This is going to make a new entry give an index and a id
   * @author terence
   * @param index, the index of the table
   * @param id, the node id 
   * @return void
   */

  void newEntry(uint8_t indes, uint16_t id) {
    NeighborTbl[indes].id = id;
    NeighborTbl[indes].flags = (NBRFLAG_VALID | NBRFLAG_NEW);
    NeighborTbl[indes].liveliness = 0;
    NeighborTbl[indes].parent = ROUTE_INVALID;
    NeighborTbl[indes].cost = ROUTE_INVALID;
    NeighborTbl[indes].childLiveliness = 0;
    NeighborTbl[indes].hop = ROUTE_INVALID;
    NeighborTbl[indes].missed = 0;
    NeighborTbl[indes].received = 0;
    NeighborTbl[indes].receiveEst = 0;
    NeighborTbl[indes].sendEst = 0;
    //call Estimator.clearTrackInfo(NeighborTbl[indes].trackInfo);
  }


  /*////////////////////////////////////////////////////////*/
  /**
   * Get neighbor table entry corresponding to the given address.
   * If current entry doesn't exist, then create one, possibly
   * evicting a previous entry. 
   * XXX - what if it evicts the parent???
   *
   * @author terence
   * @param id, node id
   * @return index
   */

  uint8_t findPreparedIndex(uint16_t id) {
    uint8_t indes = findEntry(id);
    if (indes == (uint8_t) ROUTE_INVALID) {
      indes = findEntryToBeReplaced();
      newEntry(indes, id);
    }
    return indes;
  }


  int sortByReceiveEstFcn(const void *x, const void *y) {
    struct SortEntry *nx = (struct SortEntry *) x;
    struct SortEntry *ny = (struct SortEntry *) y;
    uint8_t xReceiveEst = nx->receiveEst, yReceiveEst = ny->receiveEst;
    if (xReceiveEst > yReceiveEst) return -1;
    if (xReceiveEst == yReceiveEst) return 0;
    if (xReceiveEst < yReceiveEst) return 1;
    return 0; // shouldn't reach here becasue it covers all the cases
  }

  int sortDebugEstFcn(const void *x, const void *y) {
    struct SortDbgEntry *nx = (struct SortDbgEntry *) x;
    struct SortDbgEntry *ny = (struct SortDbgEntry *) y;
    uint8_t xReceiveEst = nx->sendEst, yReceiveEst = ny->sendEst;
    if (xReceiveEst > yReceiveEst) return -1;
    if (xReceiveEst == yReceiveEst) return 0;
    if (xReceiveEst < yReceiveEst) return 1;
    return 0; // shouldn't reach here becasue it covers all the cases
  }

  uint32_t evaluateCost(uint16_t cost, uint8_t sendEst, uint8_t receiveEst) {
    uint32_t transEst = (uint32_t) sendEst * (uint32_t) receiveEst;
    uint32_t immed = ((uint32_t) 1 << 24);

    if (transEst == 0) return ((uint32_t) 1 << (uint32_t) 16);
    // DO NOT change this LINE! mica compiler is WEIRD!
    immed = immed / transEst;
    immed += ((uint32_t) cost << 6);
    return immed;
  }


  void updateEst(TableEntry *Nbr) {
    uint16_t usExpTotal, usActTotal, newAve;

    if (Nbr->flags & NBRFLAG_NEW)
      return;
    
    usExpTotal = ESTIMATE_TO_ROUTE_RATIO;
    //if (pNbr->hop != 0) {
    //  usExpTotal *= (1 + DATA_TO_ROUTE_RATIO);
    //}
    dbg(DBG_ROUTE,"MultiHopEWMA: Updating Nbr %d. ExpTotl = %d, rcvd= %d, missed = %d\n",
        Nbr->id, usExpTotal, Nbr->received, Nbr->missed);

    atomic {
      usActTotal = Nbr->received + Nbr->missed;
      
      if (usActTotal < usExpTotal) {
        usActTotal = usExpTotal;
      }
      
      newAve = ((uint16_t) 255 * (uint16_t)Nbr->received) / (uint16_t)usActTotal;
      Nbr->missed = 0;
      Nbr->received = 0;

      // If we haven't seen a recieveEst for us from our neighbor, decay our sendEst
      // exponentially
      if (Nbr->liveliness  == 0) {
        Nbr->sendEst >>= 1;
      }else{
      	Nbr->liveliness --;
      }
    
    }
 

    if (Nbr->flags & NBRFLAG_EST_INIT) {
      uint16_t tmp;
      tmp = ((2 * ((uint16_t)Nbr->receiveEst) + (uint16_t)newAve * 6) / 8);
      Nbr->receiveEst = (uint8_t)tmp;
    }
    else {
      Nbr->receiveEst = (uint8_t) newAve;
      Nbr->flags ^= NBRFLAG_EST_INIT;
    }

     if(Nbr->childLiveliness > 0) Nbr->childLiveliness --;
  }

  void updateTable() {
    TableEntry *pNbr;
    uint8_t i = 0;

    gwEstTicks++;
    gwEstTicks %= ESTIMATE_TO_ROUTE_RATIO;

    for(i = 0; i < ROUTE_TABLE_SIZE; i++) {
      pNbr = &NeighborTbl[i];
      if (pNbr->flags & NBRFLAG_VALID) {
        if (gwEstTicks == 0) 
          updateEst(pNbr);
      }
    }
  }

  bool updateNbrCounters(uint16_t saddr, int16_t seqno, uint8_t *NbrIndex) {
    TableEntry *pNbr;
    int16_t sDelta;
    uint8_t iNbr;
    bool Result = FALSE;  // Result is TRUE if message is a duplicate

    iNbr = findPreparedIndex(saddr);
    pNbr = &NeighborTbl[iNbr];

    sDelta = (seqno - NeighborTbl[iNbr].lastSeqno - 1);

    if (pNbr->flags & NBRFLAG_NEW) {
      pNbr->received++;
      pNbr->lastSeqno = seqno;
      pNbr->flags ^= NBRFLAG_NEW;
    }
    else if (sDelta >= 0) {
      pNbr->missed += sDelta;
      pNbr->received++;
      pNbr->lastSeqno = seqno;
    }
    else if (sDelta < ACCEPTABLE_MISSED) {
      // Something happend to this node.  Reinitialize it's state
      newEntry(iNbr,saddr);
      pNbr->received++;
      pNbr->lastSeqno = seqno;
      pNbr->flags ^= NBRFLAG_NEW;
    }
    else {
      Result = TRUE;
    }

    *NbrIndex = iNbr;
    return Result;

  }

  void chooseParent() {
    TableEntry *pNbr;
    uint32_t ulNbrLinkCost = (uint32_t) -1;
    uint32_t ulNbrTotalCost = (uint32_t) -1;
    uint32_t oldParentCost = (uint32_t) -1;
    uint32_t oldParentLinkCost = (uint32_t) -1;
    uint32_t ulMinTotalCost = (uint32_t) -1;
    TableEntry* pNewParent = NULL;
    TableEntry* pOldParent = NULL;
    uint8_t i;

    if (TOS_LOCAL_ADDRESS == BASE_STATION_ADDRESS) return;

    // Choose the parent based on minimal hopcount and cost.  
    // There is a special case for choosing a base-station as it's 
    // receiveEst may be zero (it's not sending any packets)

    for (i = 0;i < ROUTE_TABLE_SIZE;i++) {
      pNbr = &NeighborTbl[i];


      if (!(pNbr->flags & NBRFLAG_VALID)) continue;
      if (pNbr->parent == TOS_LOCAL_ADDRESS) continue;
      if (pNbr->parent == ROUTE_INVALID) continue;
      if (pNbr->hop == ROUTE_INVALID) continue;
      if (pNbr->cost == (uint16_t) ROUTE_INVALID) continue;
      if (pNbr->sendEst < 25 || pNbr->receiveEst < 25) continue;
      if (pNbr->childLiveliness > 0) continue;

      ulNbrLinkCost = evaluateCost(0, pNbr->sendEst,pNbr->receiveEst);
      ulNbrTotalCost = evaluateCost(pNbr->cost, pNbr->sendEst,pNbr->receiveEst);


      if (ulNbrLinkCost > MAX_ALLOWABLE_LINK_COST) continue;
      dbg(DBG_ROUTE,"MultiHopEWMA node: %d, Cost %d, link Cost, %d\n", pNbr->id, ulNbrTotalCost, ulNbrLinkCost);
      if (pNbr == gpCurrentParent) {
	pOldParent = pNbr;
  	oldParentCost = ulNbrTotalCost;
  	oldParentLinkCost = ulNbrLinkCost;
  	continue;
      }
      
      if (ulMinTotalCost > ulNbrTotalCost) {
        ulMinTotalCost = ulNbrTotalCost;
        pNewParent = pNbr;
      }

    }