multihoplepsm.nc

nesC写的heed算法

          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
#ifdef CLUSTERING_ON
      newEntry(iNbr,saddr,pNbr->CH_type);
#else
	  newEntry(iNbr,saddr,0);
#endif
      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 ulMinLinkCost = (uint32_t) -1;
    TableEntry* pNewParent = NULL;
    uint8_t bNewHopCount = ROUTE_INVALID;
    uint8_t i;

	call Leds.greenOff();
	call Leds.yellowOff();

    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;
#ifdef CLUSTERING_ON
	  if (pNbr->CH_type == NON_CH) continue;
	  if (pNbr->id == BASE_STATION_ADDRESS && CH_type == NON_CH) continue;
#endif
      if (pNbr->parent == TOS_LOCAL_ADDRESS) continue;
      if (pNbr->parent == ROUTE_INVALID) continue;
      if (pNbr->hop == ROUTE_INVALID) continue;
      if (pNbr->sendEst < MIN_SEND_RECEIVE_EST) continue;
      if ((pNbr->hop != 0) && (pNbr->receiveEst < MIN_SEND_RECEIVE_EST)) continue;

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

      if ((pNbr->hop != 0) && (ulNbrLinkCost > MAX_ALLOWABLE_LINK_COST)) continue;
      
      if ((pNbr->hop < bNewHopCount) || 
          ((pNbr->hop == bNewHopCount) && ulMinLinkCost > ulNbrLinkCost)) {
        ulMinLinkCost = ulNbrLinkCost;
        pNewParent = pNbr;
        bNewHopCount = pNbr->hop;
      }

    }
	
    if (pNewParent) {
      atomic {
        gpCurrentParent = pNewParent;
        gbCurrentHopCount = bNewHopCount + 1;
      }
	  //light(pNewParent->id);
    }
  }

/**************************************************************/
#ifdef CLUSTERING_ON

  /*------------------------------*/
  bool symmetricLink(int idx) {
	TableEntry *pNbr = NeighborTbl + idx;

    if (!(pNbr->flags & NBRFLAG_VALID)) return FALSE;
	if (pNbr->sendEst < MIN_SEND_RECEIVE_EST_SYMMETRY) return FALSE;
	if (pNbr->receiveEst < MIN_SEND_RECEIVE_EST_SYMMETRY) return FALSE;
	return TRUE;
  }

  /*------------------------------*/
  uint8_t computeDegree() {
    TableEntry *pNbr;
    uint8_t i, num;

	num = 0;
    if (TOS_LOCAL_ADDRESS == BASE_STATION_ADDRESS) return 0xFF;
	for (i = 0;i < ROUTE_TABLE_SIZE;i++) {
		pNbr = &NeighborTbl[i];
	    if (!(pNbr->flags & NBRFLAG_VALID)) continue;
		if (pNbr->CH_type == FINAL_CH) continue;
		if (!symmetricLink(i)) continue;
		num++;
	}
	return num;
  }

  /*------------------------------*/	
  void joinClusterHead() {
    TableEntry *pNbr;
    uint8_t i, found;

    if (TOS_LOCAL_ADDRESS == BASE_STATION_ADDRESS) return;

	found = FALSE;
	for (i=0; i<ROUTE_TABLE_SIZE && !found; i++) {
		pNbr = &NeighborTbl[i];
		if (!(pNbr->flags & NBRFLAG_VALID)) continue;
		if (pNbr->parent == ROUTE_INVALID) continue;
		if (pNbr->hop == ROUTE_INVALID) continue;
		if (pNbr->CH_type == FINAL_CH && pNbr->id == my_CH) {
			found = TRUE;
			atomic {
				gpCurrentParent = pNbr;
				gbCurrentHopCount = pNbr->hop + 1;
			}
		}
	}
	if (!found) {
		atomic {
			gpCurrentParent = NULL;
			gbCurrentHopCount = ROUTE_INVALID;
		}
	}
  }

#endif

/**************************************************************/
  task void SendRouteTask() {
    TOS_MHopMsg *pMHMsg = (TOS_MHopMsg *) &routeMsg.data[0];
    RoutePacket *pRP = (RoutePacket *)&pMHMsg->data[0];
    struct SortEntry sortTbl[ROUTE_TABLE_SIZE];
    uint8_t length = offsetof(TOS_MHopMsg,data) + offsetof(RoutePacket,estList);
    uint8_t maxEstEntries;
    uint8_t i,j;

    if (gfSendRouteBusy) {
      return;
    }

    dbg(DBG_ROUTE,"MultiHopLEPSM Sending route update msg.\n");

    maxEstEntries = TOSH_DATA_LENGTH - length;
    maxEstEntries = maxEstEntries / sizeof(RPEstEntry);

    for (i = 0,j = 0;i < ROUTE_TABLE_SIZE; i++) {
      if (NeighborTbl[i].flags & NBRFLAG_VALID) {
        sortTbl[j].id = NeighborTbl[i].id;
        sortTbl[j].receiveEst = NeighborTbl[i].receiveEst;
        j++;
      }
    }
    qsort (sortTbl,j,sizeof(struct SortEntry),sortByReceiveEstFcn);

    pRP->parent = (gpCurrentParent) ? gpCurrentParent->id : ROUTE_INVALID;
#ifdef CLUSTERING_ON
	pRP->CH_type = CH_type;
	if (CH_type != NON_CH) {
		pRP->my_CH = TOS_LOCAL_ADDRESS;
		pRP->my_CH_Cost = computeDegree();		// the node degree is used as the secondary cost metric
	}
#endif
    //pRP->hop = gbCurrentHopCount;
    //pRP->cost = cost; 
    pRP->estEntries = (j > maxEstEntries) ? maxEstEntries : j;
    for (i = 0; i < pRP->estEntries; i++) {
      pRP->estList[i].id = sortTbl[i].id;
      pRP->estList[i].receiveEst = sortTbl[i].receiveEst;
      length += sizeof(RPEstEntry);
    }

    pMHMsg->sourceaddr = pMHMsg->originaddr = TOS_LOCAL_ADDRESS;
    pMHMsg->hopcount = gbCurrentHopCount;
    pMHMsg->seqno = gCurrentSeqNo++;

    if (call SendMsg.send(TOS_BCAST_ADDR, length, &routeMsg) == SUCCESS) {
      gfSendRouteBusy = TRUE;
    }
  }

/**************************************************************/
  task void Timer1Task() {
    
    dbg(DBG_ROUTE,"MultiHopLEPSM timer task.\n");
    updateTable();

#ifndef NDEBUG
    {
      int i;
      dbg(DBG_ROUTE,"\taddr\tprnt\tmisd\trcvd\tlstS\thop\trEst\tsEst\n");
      for (i = 0;i < ROUTE_TABLE_SIZE;i++) {
        if (NeighborTbl[i].flags) {
          dbg(DBG_ROUTE,"\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",
              NeighborTbl[i].id,
              NeighborTbl[i].parent,
              NeighborTbl[i].missed,
              NeighborTbl[i].received,
              NeighborTbl[i].lastSeqno,
              NeighborTbl[i].hop,
              NeighborTbl[i].receiveEst,
              NeighborTbl[i].sendEst);
        }
      }
      if (gpCurrentParent) {
        dbg(DBG_ROUTE,"MultiHopLEPSM: Parent = %d\n",gpCurrentParent->id);
      }
    }
#endif

#ifdef CLUSTERING_ON
	if (is_CH())
		chooseParent();
	else if (!inClusteringProcess)
		joinClusterHead();
#else
	chooseParent();
#endif

	post SendRouteTask();

  }

/**************************************************************/
#ifdef CLUSTERING_ON

/*-------------------------*/
  task void Timer3Task() {		// the main clustering process

	double rand_val;
	uint8_t i, iNbr;

	// check cluster head probability
	if (CH_Prob < 1) {
		if (my_tent_CH == NON_CH) {
			rand_val = (call Random.rand()) * 1.0 / ((uint16_t) - 1);
			if (rand_val < CH_Prob) {
				CH_type = TENTATIVE_CH;
				my_tent_CH = TOS_LOCAL_ADDRESS;
				my_tent_CH_Cost = computeDegree();
				post SendRouteTask();
				call Leds.yellowToggle();
			}
		}
		else 
			// check if I have previously elected as a tentative CH
			if (my_tent_CH == TOS_LOCAL_ADDRESS)  {
				post SendRouteTask();
			}
		CH_Prob *= 2;
	}
	// final stage
	// add a dummy round to compensate for late FINAL_CH messages, and similar starting CH_prob
	else {
		if ((my_tent_CH!=TOS_LOCAL_ADDRESS) && (addDummyRound))
			addDummyRound = FALSE;
		else {
			// arbitrate among the finalCH list announcements
			for (i=0; i<n_finalCH; i++) {
				iNbr = findEntry(finalCH[i].addr);
				if (iNbr != ROUTE_INVALID) {
					if (symmetricLink(iNbr) && my_final_CH_Cost > finalCH[i].cost) {
						my_final_CH = finalCH[i].addr;
						my_final_CH_Cost = finalCH[i].cost;
					}
				}
			}
			// choose cluster head
			if (my_final_CH != NON_CH) {
				CH_type = NON_CH;
				my_CH = my_final_CH;
				my_CH_Cost = my_final_CH_Cost;
				call CC1000Control.SetRFPower(POW_INTRA_CLUSTER);
				joinClusterHead();
			}
			else {
				CH_type = FINAL_CH;
				my_CH = my_final_CH = TOS_LOCAL_ADDRESS;
				my_CH_Cost = my_final_CH_Cost = computeDegree();
				call CC1000Control.SetRFPower(POW_INTER_CLUSTER);
				post SendRouteTask();
				call Leds.redOn();
			}
			inClusteringProcess = FALSE;
			was_CH = FALSE;
			call Leds.greenOff();
			call Leds.yellowOff();
			call Timer3.stop();
		}
	}
  }

/*--------------------------*/
  task void Timer2Task() {		// Triggering HEED clustering
	uint8_t orig_state;
	int i;

	if (TOS_LOCAL_ADDRESS == BASE_STATION_ADDRESS)
		return;

	turnLedsOff();
	if (!(call EnergyControl.isAlive())) {
		call StdControl.stop();
		return;
	}

	// start the clustering process
	call Leds.greenToggle();
	orig_state = CH_type;
	n_finalCH = 0;
	atomic {
		CH_type = NON_CH;
		my_tent_CH = my_final_CH = NON_CH;
		my_tent_CH_Cost = my_final_CH_Cost = 0xFFFF;
		gpCurrentParent = NULL;
		gbCurrentHopCount = ROUTE_INVALID;
		for (i = 0;i < ROUTE_TABLE_SIZE;i++) 
			NeighborTbl[i].CH_type = NON_CH;
		if (availablePoints <=0)
			call StdControl.stop();
		if (orig_state == FINAL_CH) {
			was_CH = TRUE;
			post SendRouteTask();
		}
		inClusteringProcess = TRUE;
		addDummyRound = TRUE;
	}
	call CC1000Control.SetRFPower(POW_INTRA_CLUSTER);
	if (availablePoints < MIN_REM_POWER)
		CH_Prob = C_PROB * ((1.0 * MIN_REM_POWER) / MAX_REM_POWER);
	else
		CH_Prob = C_PROB * ((1.0 * availablePoints) / MAX_REM_POWER);

	post Timer3Task();
	call Timer3.start(TIMER_REPEAT,CLUSTERING_SHORT_TIMER);
  }

#endif

/**************************************************************/
  command result_t StdControl.init() {

    memset((void *)NeighborTbl,0,(sizeof(TableEntry) * ROUTE_TABLE_SIZE));
    BaseStation.id = TOS_UART_ADDR;
    BaseStation.parent = TOS_UART_ADDR;
    BaseStation.flags = NBRFLAG_VALID;
    BaseStation.hop = 0;
    gpCurrentParent = NULL;
    gbCurrentHopCount = ROUTE_INVALID;
    gCurrentSeqNo = 0;
    gwEstTicks = 0;
    gUpdateInterval = DATA_TO_ROUTE_RATIO * DATA_FREQ;
    gfSendRouteBusy = FALSE;