marzullom.nc

主要用于无线传感网络的编写的书籍.对于初学者有着很大的用处

/* Marzullo implmentation */
/* Written by Kin Sun Ho (ksho@cse) */
/* Last Modified: 05 September 2005 */

includes Sasha;

module MarzulloM
{
  provides interface Marzullolib;
  provides interface StdControl;
  uses {
    interface Leds;
  }
}

implementation
{
  struct Mote **info; // resizeable array of Mote Info
  struct Marzullo *sort[NUM_UNITS*3]; // array to sort Marzullo end points
  int8_t Nmotes; // number of motes received
  int8_t Mmotes; // number of space allocated in memory

  command result_t Marzullolib.add_mote(CLNNMsg *rmsg) {
    int16_t mote_id;
    int8_t i;

    // find if new mote pkt
    mote_id = rmsg->src;
    for(i=0; i<Nmotes; i++) {
      if(mote_id == info[i]->mote)
	break;
    }
    if(i != Nmotes)
      return FAIL; // drop if not new pkt   

    // drop pkt when full
    if(Nmotes == Mmotes)
      return FAIL;
    
    // if new store result
    atomic {
      info[Nmotes]->mote = mote_id;
      info[Nmotes]->min  = rmsg->min;
      info[Nmotes]->max  = rmsg->max;
      info[Nmotes]->percent = rmsg->percent;
      info[Nmotes]->s2   = rmsg->s2;
      Nmotes++;
    }
    return SUCCESS;
  }

  /* Quicksort Algorithms
     adapted from http://linux.wku.edu/~lamonml/algor/sort/quick.html
  */
  void quickSort(int left, int right) {
    int8_t t_left, t_right;
    int16_t p1;
    int8_t p2;
    int8_t pivot;
    
    atomic {
      t_left = left;
      t_right = right;
      p1 = sort[left]->endpt;
      p2 = sort[left]->type;
    }
    
    while (left < right) {
      
      while ((sort[right]->endpt > p1 || (sort[right]->endpt == p1 && 
	      sort[right]->type >= p2)) && (left < right))
	right--;
      
      if (left != right) {
	atomic {
	  sort[left]->endpt = sort[right]->endpt;
	  sort[left]->type  = sort[right]->type;
	}
	left++;
      }
      
      while ((sort[left]->endpt < p1 || (sort[left]->endpt == p1 && 
	      sort[left]->type < p2)) && (left < right))
	left++;
      
      if (left != right) {
	atomic {
	  sort[right]->endpt = sort[left]->endpt;
	  sort[right]->type  = sort[left]->type;
	}
	right--;
      }
    }
    
    atomic {
      sort[left]->endpt = p1;
      sort[left]->type  = p2;
    }
    pivot = left;
    left  = t_left;
    right = t_right;
    if (left < pivot)
      quickSort(left, pivot-1);
    if (right > pivot)
      quickSort(pivot+1, right);
  }

  // do Simon's Version of Marzullo
  command CLNNMsg * Marzullolib.doMarzullo(CLNNMsg *result) {
    int8_t k;
    int8_t f,i,c;
    uint32_t low,high;
    uint32_t interval;
    uint32_t prob;
    int8_t j=0;
    uint32_t mean_sum;
    uint32_t s2;
    uint32_t sd;
    uint32_t limit;
    uint16_t tmp;

    low=0;
    high=0;
    mean_sum = 0;
    s2=0;
    tmp = 0;
    
    atomic {
      for(k=0; k<Nmotes; k++) {
	sort[j]->endpt  = info[k]->min;
	sort[j++]->type = M_START;
	sort[j]->endpt  = (info[k]->min+info[k]->max)/2;
	mean_sum += sort[j]->endpt;
	s2 += info[k]->s2;
	sort[j++]->type = M_MID;
	sort[j]->endpt  = info[k]->max;
	sort[j++]->type = M_END;
      }
    }

    if(Nmotes < 2) {
      return NULL;
    }
    
    quickSort(0,j-1);

    // Marzullo: refer to CLNNM for more comments
    for(f=0; f<(j/3); f++) {
      // c checks the number of mean learnt not in intersection
      // i checks the value of the end point determinant
      
      c = 0; i = 0; 
      
      // loop from start of the list
      for(k=0; k<j; k++) {
	i -= sort[k]->type; // the first endpt gets i=1 since endpt->type = -1
	low = sort[k]->endpt; // set this as the lower bound
	if(i >= (j/3)-f) break; // break if we have passed N-f of the min endpt
	if(sort[k]->type == 0) c++; // check # of centers not in intersection 
      }
      
      i=0; // reset i=0

      // loop from end of the list
      for(k=j-1; k>=0; k--) {
	i += sort[k]->type; // the first endpt gets i=1 since endpt->type = 1
	high = sort[k]->endpt; // set this as the upper bound
	if(i >= (j/3)-f) break; // break if we have passed N-f of max endpt
	if(sort[k]->type == 0) c++;
      }
      
      // interval found break
      if(c <= f)
	break;
    }
    
    atomic {
      // set the results
      /*
      for(k=0; k<Nmotes; k++) {
      tmp = (info[k]->min+info[k]->max)/2;
      
      if(tmp < low)
      low = tmp;
      if(tmp > high)
      high = tmp;
      }
      */
      result->min   = low;
      result->max   = high;
      result->f     = f;
      interval = high-low;
      prob = 0;
      
      call Leds.yellowToggle();
    }

    atomic {
      result->percent = 0; // unused
      result->mean    = mean_sum/Nmotes;
      sd = sqrt(s2);
      result->s2 = s2;
      
      // 1.96 for 95% CI, change the value for other % of CI
      
      limit = 1.96*sd/sqrt(Nmotes*10*MAX_TRAIN);
      result->limit = limit;
    }
    return result;
  }

  command result_t Marzullolib.reset() {
    Nmotes = 0;
    return SUCCESS;
  }

  command result_t StdControl.init() {
    int8_t i;

    dbg(DBG_USR1,"Marzullo init called\n");

    call Leds.init();
    
    Mmotes = MAX_MOTES;
    Nmotes = 0;

    for(i=0; i<Mmotes*3; i++) {
      sort[i] = (struct Marzullo*) malloc(sizeof(struct Marzullo));
    }

    info = (struct Mote**) malloc(Mmotes*sizeof(struct Mote *));
    
    for(i=0; i<Mmotes; i++) {
      info[i] = (struct Mote*)malloc(sizeof(struct Mote));
      info[i]->mote = i;
    }
    
    for(i=0; i<Mmotes; i++) {
      dbg(DBG_USR1,"i: %d, array: %d \n",i,info[i]->mote);
    }
    
    return SUCCESS;
  }

  command result_t StdControl.start() {
    return SUCCESS;
  }
  
  command result_t StdControl.stop() {
    return SUCCESS;
  }
}