networkm.nc

nesC写的heed算法

      for (i=0; i < NUM_ROOTS; i++) {
	if (mRoots[i] != UNKNOWN_ROOT && mParentIx[mRoots[i]] == idx)
	  return TRUE;
      }
      return FALSE;
    }


    enum {
      CONTENT_SHIFT = 4
    };
    #define MAX(a,b)((a) > (b)?(a):(b))

    command void NetworkMonitor.updateContention(bool failure, int status) {
      if (failure) {
	if (status == SEND_BUSY_FAILURE) //less severe of a failure?
	  mContention++;
	else
	  mContention += 10;
	//if (mContention < 32767 /*&& status == ACK_FAILURE*/) mContention++;
      } else {
	mContention -= (mContention >> CONTENT_SHIFT);
	if (mContention < (1 << CONTENT_SHIFT))
	  mRem += mContention;
	if (mRem > (1 << CONTENT_SHIFT)) {
	  mContention --;
	  mRem -= (1 << CONTENT_SHIFT);
	}
	//if (mContention > 0) mContention--;
      }
    }

	command uint16_t NetworkMonitor.getParent()
	{
		return mRelatives[mParentIx[0]];
	}

	command uint8_t NetworkMonitor.getDepth()
	{
		return myLevel(0);
	}

	command uint8_t NetworkMonitor.getQuality()
	{
		return mCommProb[mParentIx[0]];
	}

	command uint8_t NetworkMonitor.getQueueLength()
	{
		return 0;
	}

	command uint8_t NetworkMonitor.getMHopQueueLength()
	{
		return 0;
	}

	command uint8_t NetworkMonitor.getXmitCount()
	{
		return 0;
	}

    command uint16_t NetworkMonitor.getContention() {
      return mContention;
    }

    //make this link look less attractive, as a result of a dropped
    //message or a failed ack!
    void degradeLinkQuality(short neighborId) {
      int i;
      for (i = 0; i < NUM_RELATIVES;  i++) {
	if (mRelatives[i] == neighborId) {
	  mCommProb[i] = mCommProb[i] - (mCommProb[i] >> NACKALPHA);
	  break;
	}
      }
    }

    // loop through list of relatives looking for match to sender of msg. 
    // If match found, update stats and return index of match.  Else return BAD_IX.
    short tinydbUpdateSenderStats(DbMsgHdr header, short clockCnt, uint8_t rootId)
      {
	int i, j, numDrops;
	unsigned short oldProb;

	for (i = 0; i < NUM_RELATIVES; i++) {
	  oldProb = mCommProb[i];
	  if ((mRelOccupiedBits & (0x1 << i)) 
	      && mRelatives[i] == header.senderid) {
	    // valid match found: update stats for this relative

	    if (header.idx > mLastIdxRelative[i]) {
	      if (mLastIdxRelative[i] == 0)
		numDrops = 0;
	      else
		// the -1 is because the sender's incrementing by 1 is natural
		numDrops = (header.idx - mLastIdxRelative[i] - 1);
	    }
	    else if (mLastIdxRelative[i] >= 0x3f &&
		     header.idx < mLastIdxRelative[i] - 0x3f)
	      // hackety hack: assume wraparound if last Idx was above 128 and
	      // new idx is more than 128 lower than last
	      numDrops = (0x7f - mLastIdxRelative[i]) + header.idx;
	    else
	      // assume received out of order
	      numDrops = -1;


	    if (numDrops >= 0) {
	      if (numDrops > 0)
		dbg(DBG_USR1, "%i: node %i had %i drops\n", TOS_LOCAL_ADDRESS, mRelatives[i], numDrops);
	      // at each epoch i, our weighted moving avg a_i will be calculated
	      // (.75 * a_{i-1}) + (.25 * received)
	      // where received is 1 if we heard in that epoch, else 0
	      // We do this in integer logic in the range [0-255],
	      // so .25 ~= 63
	      for (j = 0; j < numDrops; j++)
		// subtract out 1/4 of the probability per drop
		mCommProb[i] = mCommProb[i] - (mCommProb[i] >> ALPHABITS);

	      // we heard this epoch.
	      // decrement history by a factor of 1/2^ALPHABITS.
	      mCommProb[i] -= (mCommProb[i] >> ALPHABITS);
	      // add in 2^8 * 1/(2^ALPHABITS) -1 = 2^(8-ALPHABITS) - 1
	      mCommProb[i] += (1 << (8-ALPHABITS)) - 1;
	    }
	    else {
	      // we inaccurately claimed not to receive a packet a while ago.
	      // add it back in.  It's hard to weight it appropriately, but
	      // a HACK lets decay it 1 epoch, i.e. add in 1/16 ~= 15
	      mCommProb[i] = (mCommProb[i] - (mCommProb[i] >> ALPHABITS));
	      mCommProb[i] += (1 << (8-2*ALPHABITS)) - 1;
	    }

	    mLastIdxRelative[i] = header.idx;
	    mRelLevel[rootId][i] = header.level;
	  
	    return(i);
	  } 
	}
	return(BAD_IX);
      }

    void tinydbRelativeReplace(DbMsgHdr header, short clockCnt, uint8_t rootId)
      {
	int i;
	short worst;
	unsigned char lowestProb = 255;

	// either put sender in an empty relative slot,
	// or evict worst (which requires a definition of worst)
	// 
	for (i = 0, worst = -1; i < NUM_RELATIVES; i++) {
	  if (!( mRelOccupiedBits & (0x1 << i) )) { // slot is empty, use it
	    worst = i;
	    break;
	  }
	  else { // XXX HACK: for now, always evict based on lowest commProv
	    if ((worst == -1
		 || ((mCommProb[i] < lowestProb)))
		&& (!isParent(i))) {
	      worst = i;
	      lowestProb = mCommProb[i];
	    }
	  }
	}
	mRelOccupiedBits |= (0x1 << worst);
	mRelatives[worst] = header.senderid;
	mLastIdxRelative[worst] = header.idx;
	mCommProb[worst] = 0xff; // ignore 1st message in stats
	mRelLevel[rootId][worst] = header.level;
      }

    void tinydbChooseParent(DbMsgHdr header, short clockCnt, uint8_t rootId, bool lastOk)
      {
	short i, best;
	unsigned char prob, tmpprob;
	short oldparent;
	short oldlevel;
	short any = -1, anylevel = -1;
	
	dbg(DBG_USR1,"%i: lastOk = %i, root = %i, parent = %i\n", TOS_LOCAL_ADDRESS, lastOk, rootId,
	    mRelatives[mParentIx[rootId]]);
	for (i = 0; i < NUM_RELATIVES; i++) {
	  if (mRelOccupiedBits & (0x1 << i))
	    dbg(DBG_USR1, "%i: Neighbor %i, prob = %i, level = %i\n", TOS_LOCAL_ADDRESS, mRelatives[i], mCommProb[i], mRelLevel[rootId][i]);
	}
	for (i = 0,  best = -1, prob=0; i < NUM_RELATIVES; i++) {
	  
	  //find lowest level neighbor that's not our current parent
	  //just so we have something to switch to if lastOk is false...
	  if (mRelOccupiedBits & (0x1 << i) && mParentIx[rootId] != i) {
	    if (any == -1 || mRelLevel[rootId][i] < anylevel) {
	      any = i;
	      dbg(DBG_USR1, "%i: any = %i\n", TOS_LOCAL_ADDRESS, mRelatives[any]);
	      anylevel = mRelLevel[rootId][i];
	    }
	  }

	  // HACK II: to avoid loops, don't choose a parent at a higher level than 
	  // ourselves. At our own level, can choose parents numbered higher than us

	  
	  if (mRelLevel[rootId][i] < myLevel(rootId) 
	      || (mRelLevel[rootId][i] == myLevel(rootId) && mRelatives[i] > TOS_LOCAL_ADDRESS))
	    if (mRelOccupiedBits & (0x1 << i) ) {
	      tmpprob = mCommProb[i];
	      if (tmpprob > prob) { //better level or better prob
		prob = tmpprob;
		best = i;
	      }
	    }
	}
	
	if ((lastOk || any == -1) && best == -1) return; //no good relatives to pick from...
	
	
	// HACK: choose parent based on least mean message arrival
	// set up new parent, and reset for new measurements
	//keep momentum for current parent at same level unless we see someone MUCH better
	// or new parent is at lower level than old parent
	if ((mCommProb[best] - mCommProb[mParentIx[rootId]] > MAX_PROB_THRESH
	     || mCommProb[mParentIx[rootId]] == 0)
	    || mRelLevel[rootId][best] < mRelLevel[rootId][mParentIx[rootId]]){
	  oldlevel = myLevel(rootId);
	  oldparent = mParentIx[rootId];
	  if (oldparent == best && !lastOk && any != -1) {
	    mParentIx[rootId] = any;
	  } else {
	    mParentIx[rootId] = best;
	  }

	  dbg(DBG_USR1,"%d: new parent is %d.  I was at level %d, now at level %d.  She's at level %d\n", 
	      TOS_LOCAL_ADDRESS, mRelatives[best], oldlevel,myLevel(rootId), mRelLevel[rootId][best]);
	} else {
	  if (!lastOk && any != -1) {
	    dbg(DBG_USR1, "%d: switching parents from %d to %d as a last resort.\n", TOS_LOCAL_ADDRESS,
		mRelatives[mParentIx[rootId]], mRelatives[any]);
	    mParentIx[rootId] = any;
	  }
	}



	//synchronize time with new parent (unless parent is root!)
	//  if (MY_LEVEL != 1 
	//	  && mRelatives[mParentIx] == header.senderid) 
	//	TOS_CALL_COMMAND(SET_TIME)(header.sendtime + TIME_OF_FLIGHT);
      }

    /* Do something with the header information in a message
       received from a neighbor / parent (e.g. update 
       routing tables, parent information, etc. )
       
       Return true if the message should be processed by the
       tuple router, or false if it should be rejected
    */
    bool processHeader(DbMsgHdr header,MsgType type, uint8_t rootId) 
      {
	bool wasParent = FALSE;

	if ((!mForceTopology || 
	     header.senderid == mParentCand1 ||
	     header.senderid == mParentCand2 || 
	     header.senderid == mParentCand3 ) &&
	    mRoots[rootId] != TOS_LOCAL_ADDRESS /* are we the root ? */ )
	  {
	    short clockCnt = 0;
	    short match;

	    // ignore our own messages
	    if (header.senderid == TOS_LOCAL_ADDRESS)
	      return FALSE;

	    if (mRelatives[mParentIx[rootId]] == header.senderid) {
	      //parent's level went up! -- reselect parent
	      if (header.level > mRelLevel[rootId][mParentIx[rootId]]) {
		mSendCount += PARENT_LOST_INTERVAL + 1;
	      }  else //parents level wen't down?  that's ok!
		mLastHeard = mSendCount;
	    }

	    //our parent thinks we're his parent -- bad news -- do something
	    if (header.parentid == TOS_LOCAL_ADDRESS && header.senderid == mRelatives[mParentIx[rootId]]) {
	      mSendCount += PARENT_LOST_INTERVAL + 1;
	    }

	    if (mSendCount - mLastHeard < 0)
	      mLastHeard = mSendCount; //handle wraparound

	    //HACK ! if we haven't heard from our parent for awhile, forget
	    //everything we know about our parent
		
	    if (mSendCount - mLastHeard> PARENT_LOST_INTERVAL) {
	      short parent = mParentIx[rootId];
	      mCommProb[mParentIx[rootId]] = 0; //make parent look awful
	      tinydbChooseParent(header, clockCnt,rootId, FALSE);
	      if (parent != mParentIx[rootId]) mLastHeard = mSendCount;

	      //If we pick the same parent again, this is bad news -- 
	      //we'll try to reselect parents again the next time through...
	      //We used to reset the routing state when this happened, 
	      // but resetting the routing state doesn't actually 
	      // seem to do us a lot of good :-)

	    }
			  
		  

	    //TOS_CALL_COMMAND(GET_TIME)(&clockCnt);
	    clockCnt = 0; //hack: clock unused!

	    // Base case: PARENT_UNKNOWN.  Initialize.
	    if (mParentIx[rootId] == PARENT_UNKNOWN) {
	      tinydbParentInit(header, clockCnt, rootId);

	      wasParent = TRUE; // having no parent means this node is our parent
	      mLastHeard = mSendCount;
	    }
	    else { // common case
	      //  Update stats for this sender, if known.
	      match = tinydbUpdateSenderStats(header, clockCnt,rootId);
	      if (match != BAD_IX && match == mParentIx[rootId])
		wasParent = TRUE;
	      else if (match == BAD_IX) {
		// Sender was not known.
		// Decide whether to keep track of this sender (i.e. make
		// it a "relative".)
		tinydbRelativeReplace(header, clockCnt, rootId);
	      }
		    
	      // Decide whether to change parents.
	      if (mSendCount - mLastCheck > PARENT_RESELECT_INTERVAL) {
		tinydbChooseParent(header, clockCnt, rootId,TRUE);
		mLastCheck = mSendCount;
	      }
	    }
	  }

	if (type == DATA_TYPE && header.parentid == TOS_LOCAL_ADDRESS)
	  return TRUE; //handle data messages to us
	else if (type == QUERY_TYPE) { //&& (wasParent || header.senderid == 0)) { /*}*/
	  dbg(DBG_USR1,"%d: GOT QUERY MESSAGE \n", TOS_LOCAL_ADDRESS);
	  return TRUE; 
	} 
	else
	  return FALSE;  //and nothing else
      }

    //alternate parent selection code to constrain the possible
    //set of parents we will select at any one time -- this
    //is to provide a method for fixing the network topology
    void setParentRange()
      {
	short nodes_per_level = 1;
	if (mFanout == 1)
	  {
	    mMinparent = TOS_LOCAL_ADDRESS - 1;
	    mMaxparent = TOS_LOCAL_ADDRESS - 1;
	  }
	else
	  {
	    short minparent = 0;
	    short maxparent = 0;
	    short prevminparent = minparent;
	    short prevmaxparent = maxparent;
	    //WARNING : may hang in an infinite loop if fanout < 0 !
	    while (TOS_LOCAL_ADDRESS > maxparent)
	      {
		prevminparent = minparent;
		prevmaxparent = maxparent;
		minparent = maxparent + 1;
		nodes_per_level *= mFanout;
		maxparent = minparent + nodes_per_level - 1;
	      }
	    mMinparent = prevminparent;
	    mMaxparent = prevmaxparent;
	  }
	// randomly pick three parent candidates between minparent and maxparent
	nodes_per_level = mMaxparent - mMinparent + 1;
	if (nodes_per_level <= 2)
	  {
	    mParentCand1 = mMinparent;
	    mParentCand2 = mParentCand3 = mMaxparent;
	  }
	else
	  {
	    mParentCand1 = mMinparent + call Random.rand() % nodes_per_level;
	    mParentCand2 = mMinparent + call Random.rand()  % nodes_per_level;
	    mParentCand3 = mMinparent + call Random.rand() % nodes_per_level;
	  }
      }

	event result_t CommandUse.commandDone(char *commandName, char *resultBuf, SchemaErrorNo err)
	{
		// XXX ignore command return values for now
		return SUCCESS;
	}

#ifdef kSUPPORTS_EVENTS
	event result_t EventUse.eventDone(char *name, SchemaErrorNo err) {
	  return SUCCESS;
	}
#endif

	event result_t QueryProcessor.queryComplete(ParsedQueryPtr q) {
	  return SUCCESS;
	}
}