multihoplepsm.nc

nesC写的heed算法

// $Id: MultiHopLEPSM.nc,v 1.5.2.4 2003/08/29 00:46:33 idgay 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;

module MultiHopLEPSM {

  provides {
    interface StdControl;
    interface RouteSelect;
    interface RouteControl;
	/****** HEED code: energy control ***/
	interface EnergyControl;
  }

  uses {
	interface Timer as Timer1;
    interface ReceiveMsg;
    interface Intercept as Snoop[uint8_t id];
    interface SendMsg;

	/***** HEED code: power control ****/
	interface CC1000Control;
	interface Leds;
#ifdef CLUSTERING_ON
	interface Random;
	interface Timer as Timer2;
	interface Timer as Timer3;
#endif
  }
}

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     = 2,	// originally 5
    ACCEPTABLE_MISSED           = -20,
    DATA_TO_ROUTE_RATIO         = 1,    // originally 2 
    DATA_FREQ                   = 10000, 
    MAX_ALLOWABLE_LINK_COST     = 1536,
    MIN_LIVELINESS              = 2,
	MIN_SEND_RECEIVE_EST		= 6	// originally 25
  };

  enum {
    ROUTE_INVALID    = 0xff
  };

  /*** HEED: control constants ******/
  enum {
	MIN_SEND_RECEIVE_EST_SYMMETRY = 5,		// for checking symmetric links
	MIN_REM_POWER			= 300,			// for node death and minimum CH prob. computation
	// Specific power setting and corresponding consumption
	POW_INTER_CLUSTER		= 0x06,			// for setting the register in CC1000.SetRFPower() for cluster heads
	POW_INTRA_CLUSTER		= 0x02,			// for setting the register in CC1000.SetRFPower() for regular nodes
	POW_COST_INTRA_CLUSTER	= 230,			// unit3 of (1 micro Watt), corresponds to current=5.3mA, 29 bytes, 62.4usec/bit
	POW_COST_INTER_CLUSTER	= 291,			// units of (1 micro Watt), corresponds to current=6.7mA, 29 bytes, 62.4usec/bit
	MAX_REM_POWER			= 500000		// units of (1 micro Watt)
  };
#ifdef CLUSTERING_ON
  enum {
	OPERATION_INTERVAL		= 540000,		// msec
	CLUSTERING_SHORT_TIMER	= 11000,		// for internal iteration of the clustering process
	NON_CH					= 0,			// non cluster head
	TENTATIVE_CH			= 1,			// tentative cluster head				
	FINAL_CH				= 2				// final cluster head
  };
#endif

  #define C_PROB	0.03					// initial clustering probability
  /******************************************/

  struct SortEntry {
    uint16_t id;
    uint8_t  receiveEst;
  };

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

  typedef struct RoutePacket {
    uint16_t parent;
    uint8_t estEntries;
#ifdef CLUSTERING_ON
	uint8_t CH_type;			// cluster head type
	uint16_t my_CH;				// my cluster head ID
	uint16_t my_CH_Cost;		// my cluster head cost
#endif
    RPEstEntry estList[1];
  } __attribute__ ((packed)) RoutePacket;

  typedef struct TableEntry {
    uint16_t id;  // Node Address
    uint16_t parent;
    uint16_t missed;
    uint16_t received;
    int16_t lastSeqno;
    uint8_t flags;
    uint8_t liveliness;
    uint8_t hop;
    uint8_t receiveEst;
    uint8_t sendEst;
#ifdef CLUSTERING_ON
	uint8_t CH_type;
	uint16_t my_CH;
	uint16_t my_CH_Cost;
#endif
  } TableEntry;

  TOS_Msg routeMsg; 
  bool gfSendRouteBusy;

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

  /***** HEED code: variables *************/
  uint32_t availablePoints;		// corresponds to remaining energy
  uint32_t overheadPoints;		// corresponds to energy wasted in routing updates and clustering
#ifdef CLUSTERING_ON
  uint16_t CH_type;				// cluster head type (non, tentative, final)
  uint16_t my_CH;				// my cluster head ID (NON_CH if none)
  uint16_t my_CH_Cost;			// cost of my cluster head
  double CH_Prob;				// cluster head probability (for probabilistic clustering)
  bool inClusteringProcess;		// if currently a clustering process is proceeding
  bool was_CH;					// if during a clustering process and was a final_CH before it
  uint16_t my_tent_CH, my_final_CH, my_tent_CH_Cost, my_final_CH_Cost;
  typedef struct CHEntry {
	uint16_t addr;
	uint16_t cost;
  } CHEntry;
  CHEntry finalCH[ROUTE_TABLE_SIZE];	// to keep final CH announcements
  int n_finalCH;
  bool addDummyRound;		// do a dummy round when your CH_prob reaches 1 to compensate 
							// for late FINAL_CH messages and similar starting CH_prob

  result_t is_CH() {
	return (!inClusteringProcess && my_CH == TOS_LOCAL_ADDRESS);
  }

  // for debugging
  void light(uint16_t parent) {
	if (parent == BASE_STATION_ADDRESS) {
		call Leds.greenToggle();
		call Leds.yellowToggle();
		return;
	}
	switch (TOS_LOCAL_ADDRESS) {
	case 1:
		if (parent == 2)
			call Leds.greenToggle();
		else if (parent == 3)
			call Leds.yellowToggle();
		break;
	case 2:
		if (parent == 1)
			call Leds.greenToggle();
		else if (parent == 3)
			call Leds.yellowToggle();
		break;
	case 3:
		if (parent == 1)
			call Leds.greenToggle();
		else if (parent == 2)
			call Leds.yellowToggle();
		break;
	}
  }
#endif

  void turnLedsOff() {
	call Leds.redOff();
	call Leds.greenOff();
	call Leds.yellowOff();
  }

  /*////////////////////////////////////////////////////////*/
  /**
   * 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, uint8_t type) {
    NeighborTbl[indes].id = id;
    NeighborTbl[indes].flags = (NBRFLAG_VALID | NBRFLAG_NEW);
    NeighborTbl[indes].liveliness = 0;
    NeighborTbl[indes].parent = ROUTE_INVALID;
    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);
#ifdef CLUSTERING_ON
	NeighborTbl[indes].CH_type = type;
#endif
  }


  /*////////////////////////////////////////////////////////*/
  /**
   * 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, FALSE);
    }
    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
  }

/**************************************************************/
  uint32_t evaluateCost(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;
    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,"MultiHopLEPSM: 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 < MIN_LIVELINESS) {
        Nbr->sendEst <<= 1;
      }
      Nbr->liveliness = 0;
    
    }
 
    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;
    }

  }

/**************************************************************/
  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)