clnnm.nc

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

/* CLNN implmentation */
/* Written by Tatiana Bokareva, Kin Sun Ho (tbokareva,ksho@cse) */
/* Last Modified: 21 August 2005 */

includes Sasha;

module CLNNM
{
  provides interface CLNNlib;
  provides interface StdControl;
  uses {
    interface Timer;
    interface Leds;
    interface Anycastlib;
    interface StdControl as SensorControl;
    interface StdControl as CommControl;
    interface ADC as Sensor;
  }
}

implementation
{
  uint8_t reading;             // raw reading taken to fill buffer <= buffer
  uint8_t training;            // number of training done
  uint16_t buffer[NUM_UNITS];  // buffer to store raw sensor data
  uint32_t s_sum;              // sum of sensor data
  uint32_t s_sum2;             // sum^2 of sensor data
  uint16_t verify;              // verify or training
  uint16_t num_verify;          // num of verify
  uint16_t verify_min, verify_max; //bounds to verify  
  uint16_t verify_fault;          // number of fault discovered
  struct Marzullo *sort[NUM_UNITS*3]; // array to sort Marzullo end points
  struct clnn *ptnn;	       // neural network structure
  
  /* 
     The following print statement is for debugging in tossim
     To run the program in tossim:
     # make pc
     # export DBG=usr1
     # ./build/pc/main.exe 1
  */

  /* prints raw sensor data received */
  void print_raw() {
    uint8_t i=0;
    dbg(DBG_USR1, "Input Vector: ");
    for(i=0; i<NUM_UNITS; i++) {
      dbg(DBG_USR1, "%d ", buffer[i]);
    }
    dbg(DBG_USR1, "\n");
  }
  
  /* prints the weight matrix which is used for training */ 
  void print_weights(){
    uint8_t i=0;
    uint8_t j=0;
    for(i=0; i<NUM_UNITS; i++){
      atomic {
	dbg(DBG_USR1, "WEIGHTS: %u - ", i);
      }
      for(j=0; j< NUM_UNITS; j++){
	dbg(DBG_USR1, "%u ", ptnn->weights[i][j]);
      }
      dbg(DBG_USR1, "\n");
    }
  }
  
  
  /* 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);
  }
  

  /* Perform Marzullo intersection algorithms */
  void doMarzullo() {
    /* variables */
    int8_t j,k;
    int8_t f,i,c;
    uint32_t low,high;
    uint32_t interval;
    uint32_t prob;
    uint32_t sxx;
    uint32_t s2;
    uint32_t sd;
    uint32_t limit;

    j = 0;
    low = 0;
    high = 0;
   
    // create a list of end point values to be sorted with
    atomic {
      for(k=0; k<NUM_UNITS; k++) {
	if(ptnn->clusters[k][2] == 0)
	  continue;
	sort[j]->endpt  = ptnn->clusters[k][0];
	sort[j++]->type = M_START;
	sort[j]->endpt  = (ptnn->clusters[k][0]+ptnn->clusters[k][1])/2;
	sort[j++]->type = M_MID;
	sort[j]->endpt = ptnn->clusters[k][1];
	sort[j++]->type = M_END;
      }
    }

    // perform quicksort on the list 
    quickSort(0,j-1);

    if(j < 6)
      return;
    
    /* 
       Find the best intersection which includes the mean of most intervals 
       N = j/3 = total number of intervals
       f = number of intervals not in marzullo intersection
         = [0..N-1]
       If f=N-1 is returned, it means that no intervals intersect

       Marzullo theory:
      
       1/0 = min pt determinant/max pt value determinant
          
          1/0 ---------------- 3/4
                2/1 ----------- 2/3
                   3/2 ------------ 1/2
                       4/3 ----------- 0/1

       For intervals with N=4, f=0, intersection = [4/3,3/4]
                               f=1, intersection = [3/2,2/3]
			       f=2, intersection = [2/1,1/2]
			       f=3, intersection = [1/0,0/1]
       
       The program will loop thru f=[0..N-1], to find an
       intersection with such that it contains the mean
       of no less than N-f intervals.

       This is done so that when we remove the noise from 
       the clusters, we still keep the majority of data.

       If original marzullo is needed, remove the lines to
       check the mean.
    */

    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++;
      }
      
      // check that the intersection contains the mean of more than f intervals
      if(c <= f)
	break;
    }

    atomic {
      // set the results in the ptnn structure
      ptnn->min  = low;
      ptnn->max  = high;
      ptnn->f    = f;
      ptnn->mean = (int16_t) (s_sum/(10*training));
    }

    dbg(DBG_USR1, "Marzullo (%d,%d,%d)\n",ptnn->min,ptnn->max,ptnn->f);
    
    interval = high-low; // determine the interval length
    prob = 0; // intital probability = 0

    atomic {
      dbg(DBG_USR1, "prob:%d, training: %d, interval: %d\n",
	  prob,training,interval);
      // calculate the final probability
      ptnn->percent = prob; // unused
      
      // determine the normal distribution
      sxx = s_sum2 - (s_sum)*(s_sum)/(10*training);
      s2 = sxx/(10*training-1);
      sd = sqrt(s2);
      
      // 1.96 for 95% CI, change the value for other % of CI
      
      limit = 1.96*sd/sqrt(10*training);
      ptnn->limit = limit;
      ptnn->s2    = s2;

      // Tell Anycast to start sending result to sink
      call Anycastlib.start_timer();
      
      // for debug
      dbg(DBG_USR1, "final prob: %d\n",ptnn->percent);
      dbg(DBG_USR1, "average: %d\n",ptnn->mean);
      dbg(DBG_USR1, "limit: %d\n",ptnn->limit);
      dbg(DBG_USR1, "s_sum2: %d, sxx: %d, s2: %d, sd: %d\n",s_sum2,sxx,s2,sd);
    }
  }
  
  /* prints the clusters */ 
  void print_clusters() {
    uint8_t i=0;
    for(i=0; i<NUM_UNITS; i++){
      dbg(DBG_USR1, "CLUSTERS: %u %u %u %u\n", i, ptnn->clusters[i][0],
	  ptnn->clusters[i][1],ptnn->clusters[i][2]);
    }
  }

  /* asks CLNN reset its weight matrix and all information it have */
  command result_t CLNNlib.reset() {
     /* parameters to assign the weight array */
    uint8_t i=0;
    uint8_t j=0;
    uint16_t step=100;
    uint8_t inc=100;
    
    dbg(DBG_USR1, "CLNN reinitialized\n");
    atomic {
      reading = 0;
      training = 0;
      s_sum = 0;
      //initilise the weights and clusters
      for(i=0; i<NUM_UNITS; i++){	
	for(j=0; j< NUM_UNITS; j++){
	  ptnn->weights[i][j]=step;
	  ptnn->clusters[i][0]=NEGDIST;
	  ptnn->clusters[i][1]=NEGDIST;
	  ptnn->clusters[i][2]=0;
	}
	step=step+inc;
      }
      ptnn->min=0;
      ptnn->max=0;
      ptnn->f=0;
      ptnn->percent=0;
      ptnn->mean=0;
      ptnn->limit=0;
      ptnn->s2=0;
    }
    print_weights();
    return SUCCESS;
  }
  
  // request start training
  command result_t CLNNlib.start_training() {
    verify = 0;
    return call Timer.start(TIMER_REPEAT,SENSOR_PERIOD);
  }

  // request start verify
  command result_t CLNNlib.start_verify(int16_t min,int16_t max) {
    atomic {
      verify = 1;
      verify_min = min;
      verify_max = max;
      num_verify = 0;
      verify_fault = 0;
    }